* Re: [PATCH V4 1/8] namespaces: assign each namespace instance a serial number
From: Andy Lutomirski @ 2014-08-21 21:22 UTC (permalink / raw)
To: Richard Guy Briggs
Cc: Eric W. Biederman, Eric Paris, Steve Grubb,
arozansk-H+wXaHxf7aLQT0dZR+AlfA,
linux-audit-H+wXaHxf7aLQT0dZR+AlfA, Linux API, Linux Containers,
Serge E. Hallyn,
linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
In-Reply-To: <d5bfd81a219c5c45c910494d6a3478ce83052e1f.1408581429.git.rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
On Aug 20, 2014 8:12 PM, "Richard Guy Briggs" <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
>
> Generate and assign a serial number per namespace instance since boot.
>
> Use a serial number per namespace (unique across one boot of one kernel)
> instead of the inode number (which is claimed to have had the right to change
> reserved and is not necessarily unique if there is more than one proc fs) to
> uniquely identify it per kernel boot.
>
> Signed-off-by: Richard Guy Briggs <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
> ---
> fs/mount.h | 1 +
> fs/namespace.c | 1 +
> include/linux/ipc_namespace.h | 1 +
> include/linux/nsproxy.h | 8 ++++++++
> include/linux/pid_namespace.h | 1 +
> include/linux/user_namespace.h | 1 +
> include/linux/utsname.h | 1 +
> include/net/net_namespace.h | 1 +
> init/version.c | 1 +
> ipc/msgutil.c | 1 +
> ipc/namespace.c | 2 ++
> kernel/nsproxy.c | 17 +++++++++++++++++
> kernel/pid.c | 1 +
> kernel/pid_namespace.c | 2 ++
> kernel/user.c | 1 +
> kernel/user_namespace.c | 2 ++
> kernel/utsname.c | 2 ++
> net/core/net_namespace.c | 8 +++++++-
> 18 files changed, 51 insertions(+), 1 deletions(-)
>
> diff --git a/fs/mount.h b/fs/mount.h
> index d55297f..c076f99 100644
> --- a/fs/mount.h
> +++ b/fs/mount.h
> @@ -5,6 +5,7 @@
> struct mnt_namespace {
> atomic_t count;
> unsigned int proc_inum;
> + long long serial_num;
> struct mount * root;
> struct list_head list;
> struct user_namespace *user_ns;
> diff --git a/fs/namespace.c b/fs/namespace.c
> index 182bc41..9af49ff 100644
> --- a/fs/namespace.c
> +++ b/fs/namespace.c
> @@ -2486,6 +2486,7 @@ static struct mnt_namespace *alloc_mnt_ns(struct user_namespace *user_ns)
> kfree(new_ns);
> return ERR_PTR(ret);
> }
> + new_ns->serial_num = ns_serial();
> new_ns->seq = atomic64_add_return(1, &mnt_ns_seq);
> atomic_set(&new_ns->count, 1);
> new_ns->root = NULL;
> diff --git a/include/linux/ipc_namespace.h b/include/linux/ipc_namespace.h
> index 35e7eca..8ccfb2d 100644
> --- a/include/linux/ipc_namespace.h
> +++ b/include/linux/ipc_namespace.h
> @@ -69,6 +69,7 @@ struct ipc_namespace {
> struct user_namespace *user_ns;
>
> unsigned int proc_inum;
> + long long serial_num;
> };
>
> extern struct ipc_namespace init_ipc_ns;
> diff --git a/include/linux/nsproxy.h b/include/linux/nsproxy.h
> index b4ec59d..8e5fe0d 100644
> --- a/include/linux/nsproxy.h
> +++ b/include/linux/nsproxy.h
> @@ -66,6 +66,14 @@ static inline struct nsproxy *task_nsproxy(struct task_struct *tsk)
> return rcu_dereference(tsk->nsproxy);
> }
>
> +long long ns_serial(void);
> +enum {
> + NS_IPC_INIT_SN = 1,
> + NS_UTS_INIT_SN = 2,
> + NS_USER_INIT_SN = 3,
> + NS_PID_INIT_SN = 4,
Please add an extra value here for the first dynamic value...
> +/**
> + * ns_serial - compute a serial number for the namespace
> + *
> + * Compute a serial number for the namespace to uniquely identify it in
> + * audit records.
> + */
> +long long ns_serial(void)
> +{
> + static atomic64_t serial = ATOMIC_INIT(4); /* reserved for IPC, UTS, user, PID */
...and use it here.
Also, does this work on all architectures?
--Andy
^ permalink raw reply
* Re: [PATCH V4 1/8] namespaces: assign each namespace instance a serial number
From: Richard Guy Briggs @ 2014-08-21 21:28 UTC (permalink / raw)
To: Andy Lutomirski
Cc: Eric W. Biederman, Eric Paris, Steve Grubb,
arozansk-H+wXaHxf7aLQT0dZR+AlfA,
linux-audit-H+wXaHxf7aLQT0dZR+AlfA, Linux API, Linux Containers,
Serge E. Hallyn,
linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
In-Reply-To: <CALCETrW+vtPnB47aCxfKFxkmKxZS2QsWCkazCc776yg0aPPidA-JsoAwUIsXosN+BqQ9rBEUg@public.gmane.org>
On 14/08/21, Andy Lutomirski wrote:
> On Aug 20, 2014 8:12 PM, "Richard Guy Briggs" <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> >
> > Generate and assign a serial number per namespace instance since boot.
> >
> > Use a serial number per namespace (unique across one boot of one kernel)
> > instead of the inode number (which is claimed to have had the right to change
> > reserved and is not necessarily unique if there is more than one proc fs) to
> > uniquely identify it per kernel boot.
> >
> > Signed-off-by: Richard Guy Briggs <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
> > ---
> > fs/mount.h | 1 +
> > fs/namespace.c | 1 +
> > include/linux/ipc_namespace.h | 1 +
> > include/linux/nsproxy.h | 8 ++++++++
> > include/linux/pid_namespace.h | 1 +
> > include/linux/user_namespace.h | 1 +
> > include/linux/utsname.h | 1 +
> > include/net/net_namespace.h | 1 +
> > init/version.c | 1 +
> > ipc/msgutil.c | 1 +
> > ipc/namespace.c | 2 ++
> > kernel/nsproxy.c | 17 +++++++++++++++++
> > kernel/pid.c | 1 +
> > kernel/pid_namespace.c | 2 ++
> > kernel/user.c | 1 +
> > kernel/user_namespace.c | 2 ++
> > kernel/utsname.c | 2 ++
> > net/core/net_namespace.c | 8 +++++++-
> > 18 files changed, 51 insertions(+), 1 deletions(-)
> >
> > diff --git a/fs/mount.h b/fs/mount.h
> > index d55297f..c076f99 100644
> > --- a/fs/mount.h
> > +++ b/fs/mount.h
> > @@ -5,6 +5,7 @@
> > struct mnt_namespace {
> > atomic_t count;
> > unsigned int proc_inum;
> > + long long serial_num;
> > struct mount * root;
> > struct list_head list;
> > struct user_namespace *user_ns;
> > diff --git a/fs/namespace.c b/fs/namespace.c
> > index 182bc41..9af49ff 100644
> > --- a/fs/namespace.c
> > +++ b/fs/namespace.c
> > @@ -2486,6 +2486,7 @@ static struct mnt_namespace *alloc_mnt_ns(struct user_namespace *user_ns)
> > kfree(new_ns);
> > return ERR_PTR(ret);
> > }
> > + new_ns->serial_num = ns_serial();
> > new_ns->seq = atomic64_add_return(1, &mnt_ns_seq);
> > atomic_set(&new_ns->count, 1);
> > new_ns->root = NULL;
> > diff --git a/include/linux/ipc_namespace.h b/include/linux/ipc_namespace.h
> > index 35e7eca..8ccfb2d 100644
> > --- a/include/linux/ipc_namespace.h
> > +++ b/include/linux/ipc_namespace.h
> > @@ -69,6 +69,7 @@ struct ipc_namespace {
> > struct user_namespace *user_ns;
> >
> > unsigned int proc_inum;
> > + long long serial_num;
> > };
> >
> > extern struct ipc_namespace init_ipc_ns;
> > diff --git a/include/linux/nsproxy.h b/include/linux/nsproxy.h
> > index b4ec59d..8e5fe0d 100644
> > --- a/include/linux/nsproxy.h
> > +++ b/include/linux/nsproxy.h
> > @@ -66,6 +66,14 @@ static inline struct nsproxy *task_nsproxy(struct task_struct *tsk)
> > return rcu_dereference(tsk->nsproxy);
> > }
> >
> > +long long ns_serial(void);
> > +enum {
> > + NS_IPC_INIT_SN = 1,
> > + NS_UTS_INIT_SN = 2,
> > + NS_USER_INIT_SN = 3,
> > + NS_PID_INIT_SN = 4,
>
> Please add an extra value here for the first dynamic value...
> > +/**
> > + * ns_serial - compute a serial number for the namespace
> > + *
> > + * Compute a serial number for the namespace to uniquely identify it in
> > + * audit records.
> > + */
> > +long long ns_serial(void)
> > +{
> > + static atomic64_t serial = ATOMIC_INIT(4); /* reserved for IPC, UTS, user, PID */
>
> ...and use it here.
Yup, good idea. Thanks.
> Also, does this work on all architectures?
I only know for certain x86_64. There is discussion elsewhere about
changing ns_serial from returning a long long to returning a u64. That
should help. I can run standard compile and boot tests on several
others, but won't be able to check output.
> --Andy
- RGB
--
Richard Guy Briggs <rbriggs-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
Senior Software Engineer, Kernel Security, AMER ENG Base Operating Systems, Red Hat
Remote, Ottawa, Canada
Voice: +1.647.777.2635, Internal: (81) 32635, Alt: +1.613.693.0684x3545
^ permalink raw reply
* Re: [PATCH V4 1/8] namespaces: assign each namespace instance a serial number
From: Andy Lutomirski @ 2014-08-21 21:30 UTC (permalink / raw)
To: Richard Guy Briggs
Cc: Linux API, Linux Containers,
linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org, Eric Paris,
linux-audit-H+wXaHxf7aLQT0dZR+AlfA, Eric W. Biederman,
Steve Grubb
In-Reply-To: <20140821212820.GD20529-bcJWsdo4jJjeVoXN4CMphl7TgLCtbB0G@public.gmane.org>
On Thu, Aug 21, 2014 at 2:28 PM, Richard Guy Briggs <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> On 14/08/21, Andy Lutomirski wrote:
>> On Aug 20, 2014 8:12 PM, "Richard Guy Briggs" <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
>> >
>> > Generate and assign a serial number per namespace instance since boot.
>> >
>> > Use a serial number per namespace (unique across one boot of one kernel)
>> > instead of the inode number (which is claimed to have had the right to change
>> > reserved and is not necessarily unique if there is more than one proc fs) to
>> > uniquely identify it per kernel boot.
>> >
>> > Signed-off-by: Richard Guy Briggs <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
>> > ---
>> > fs/mount.h | 1 +
>> > fs/namespace.c | 1 +
>> > include/linux/ipc_namespace.h | 1 +
>> > include/linux/nsproxy.h | 8 ++++++++
>> > include/linux/pid_namespace.h | 1 +
>> > include/linux/user_namespace.h | 1 +
>> > include/linux/utsname.h | 1 +
>> > include/net/net_namespace.h | 1 +
>> > init/version.c | 1 +
>> > ipc/msgutil.c | 1 +
>> > ipc/namespace.c | 2 ++
>> > kernel/nsproxy.c | 17 +++++++++++++++++
>> > kernel/pid.c | 1 +
>> > kernel/pid_namespace.c | 2 ++
>> > kernel/user.c | 1 +
>> > kernel/user_namespace.c | 2 ++
>> > kernel/utsname.c | 2 ++
>> > net/core/net_namespace.c | 8 +++++++-
>> > 18 files changed, 51 insertions(+), 1 deletions(-)
>> >
>> > diff --git a/fs/mount.h b/fs/mount.h
>> > index d55297f..c076f99 100644
>> > --- a/fs/mount.h
>> > +++ b/fs/mount.h
>> > @@ -5,6 +5,7 @@
>> > struct mnt_namespace {
>> > atomic_t count;
>> > unsigned int proc_inum;
>> > + long long serial_num;
>> > struct mount * root;
>> > struct list_head list;
>> > struct user_namespace *user_ns;
>> > diff --git a/fs/namespace.c b/fs/namespace.c
>> > index 182bc41..9af49ff 100644
>> > --- a/fs/namespace.c
>> > +++ b/fs/namespace.c
>> > @@ -2486,6 +2486,7 @@ static struct mnt_namespace *alloc_mnt_ns(struct user_namespace *user_ns)
>> > kfree(new_ns);
>> > return ERR_PTR(ret);
>> > }
>> > + new_ns->serial_num = ns_serial();
>> > new_ns->seq = atomic64_add_return(1, &mnt_ns_seq);
>> > atomic_set(&new_ns->count, 1);
>> > new_ns->root = NULL;
>> > diff --git a/include/linux/ipc_namespace.h b/include/linux/ipc_namespace.h
>> > index 35e7eca..8ccfb2d 100644
>> > --- a/include/linux/ipc_namespace.h
>> > +++ b/include/linux/ipc_namespace.h
>> > @@ -69,6 +69,7 @@ struct ipc_namespace {
>> > struct user_namespace *user_ns;
>> >
>> > unsigned int proc_inum;
>> > + long long serial_num;
>> > };
>> >
>> > extern struct ipc_namespace init_ipc_ns;
>> > diff --git a/include/linux/nsproxy.h b/include/linux/nsproxy.h
>> > index b4ec59d..8e5fe0d 100644
>> > --- a/include/linux/nsproxy.h
>> > +++ b/include/linux/nsproxy.h
>> > @@ -66,6 +66,14 @@ static inline struct nsproxy *task_nsproxy(struct task_struct *tsk)
>> > return rcu_dereference(tsk->nsproxy);
>> > }
>> >
>> > +long long ns_serial(void);
>> > +enum {
>> > + NS_IPC_INIT_SN = 1,
>> > + NS_UTS_INIT_SN = 2,
>> > + NS_USER_INIT_SN = 3,
>> > + NS_PID_INIT_SN = 4,
>>
>> Please add an extra value here for the first dynamic value...
>> > +/**
>> > + * ns_serial - compute a serial number for the namespace
>> > + *
>> > + * Compute a serial number for the namespace to uniquely identify it in
>> > + * audit records.
>> > + */
>> > +long long ns_serial(void)
>> > +{
>> > + static atomic64_t serial = ATOMIC_INIT(4); /* reserved for IPC, UTS, user, PID */
>>
>> ...and use it here.
>
> Yup, good idea. Thanks.
>
>> Also, does this work on all architectures?
>
> I only know for certain x86_64. There is discussion elsewhere about
> changing ns_serial from returning a long long to returning a u64. That
> should help. I can run standard compile and boot tests on several
> others, but won't be able to check output.
I was thinking of atomic64. I guess there's a generic implementation
that works everywhere, if somewhat slowly.
--Andy
^ permalink raw reply
* Re: [PATCH V4 1/8] namespaces: assign each namespace instance a serial number
From: Richard Guy Briggs @ 2014-08-21 22:15 UTC (permalink / raw)
To: Andy Lutomirski
Cc: Eric W. Biederman, Eric Paris, Steve Grubb,
arozansk-H+wXaHxf7aLQT0dZR+AlfA,
linux-audit-H+wXaHxf7aLQT0dZR+AlfA, Linux API, Linux Containers,
Serge E. Hallyn,
linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
In-Reply-To: <CALCETrXUTTo5MN=bRM96Kos5JueWED5Rhr7SB2dgzTdy7bw5cw-JsoAwUIsXosN+BqQ9rBEUg@public.gmane.org>
On 14/08/21, Andy Lutomirski wrote:
> On Thu, Aug 21, 2014 at 2:28 PM, Richard Guy Briggs <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> > On 14/08/21, Andy Lutomirski wrote:
> >> On Aug 20, 2014 8:12 PM, "Richard Guy Briggs" <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> >> >
> >> > Generate and assign a serial number per namespace instance since boot.
> >> >
> >> > Use a serial number per namespace (unique across one boot of one kernel)
> >> > instead of the inode number (which is claimed to have had the right to change
> >> > reserved and is not necessarily unique if there is more than one proc fs) to
> >> > uniquely identify it per kernel boot.
> >> >
> >> > Signed-off-by: Richard Guy Briggs <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
> >> > ---
> >> > fs/mount.h | 1 +
> >> > fs/namespace.c | 1 +
> >> > include/linux/ipc_namespace.h | 1 +
> >> > include/linux/nsproxy.h | 8 ++++++++
> >> > include/linux/pid_namespace.h | 1 +
> >> > include/linux/user_namespace.h | 1 +
> >> > include/linux/utsname.h | 1 +
> >> > include/net/net_namespace.h | 1 +
> >> > init/version.c | 1 +
> >> > ipc/msgutil.c | 1 +
> >> > ipc/namespace.c | 2 ++
> >> > kernel/nsproxy.c | 17 +++++++++++++++++
> >> > kernel/pid.c | 1 +
> >> > kernel/pid_namespace.c | 2 ++
> >> > kernel/user.c | 1 +
> >> > kernel/user_namespace.c | 2 ++
> >> > kernel/utsname.c | 2 ++
> >> > net/core/net_namespace.c | 8 +++++++-
> >> > 18 files changed, 51 insertions(+), 1 deletions(-)
> >> >
> >> > diff --git a/fs/mount.h b/fs/mount.h
> >> > index d55297f..c076f99 100644
> >> > --- a/fs/mount.h
> >> > +++ b/fs/mount.h
> >> > @@ -5,6 +5,7 @@
> >> > struct mnt_namespace {
> >> > atomic_t count;
> >> > unsigned int proc_inum;
> >> > + long long serial_num;
> >> > struct mount * root;
> >> > struct list_head list;
> >> > struct user_namespace *user_ns;
> >> > diff --git a/fs/namespace.c b/fs/namespace.c
> >> > index 182bc41..9af49ff 100644
> >> > --- a/fs/namespace.c
> >> > +++ b/fs/namespace.c
> >> > @@ -2486,6 +2486,7 @@ static struct mnt_namespace *alloc_mnt_ns(struct user_namespace *user_ns)
> >> > kfree(new_ns);
> >> > return ERR_PTR(ret);
> >> > }
> >> > + new_ns->serial_num = ns_serial();
> >> > new_ns->seq = atomic64_add_return(1, &mnt_ns_seq);
> >> > atomic_set(&new_ns->count, 1);
> >> > new_ns->root = NULL;
> >> > diff --git a/include/linux/ipc_namespace.h b/include/linux/ipc_namespace.h
> >> > index 35e7eca..8ccfb2d 100644
> >> > --- a/include/linux/ipc_namespace.h
> >> > +++ b/include/linux/ipc_namespace.h
> >> > @@ -69,6 +69,7 @@ struct ipc_namespace {
> >> > struct user_namespace *user_ns;
> >> >
> >> > unsigned int proc_inum;
> >> > + long long serial_num;
> >> > };
> >> >
> >> > extern struct ipc_namespace init_ipc_ns;
> >> > diff --git a/include/linux/nsproxy.h b/include/linux/nsproxy.h
> >> > index b4ec59d..8e5fe0d 100644
> >> > --- a/include/linux/nsproxy.h
> >> > +++ b/include/linux/nsproxy.h
> >> > @@ -66,6 +66,14 @@ static inline struct nsproxy *task_nsproxy(struct task_struct *tsk)
> >> > return rcu_dereference(tsk->nsproxy);
> >> > }
> >> >
> >> > +long long ns_serial(void);
> >> > +enum {
> >> > + NS_IPC_INIT_SN = 1,
> >> > + NS_UTS_INIT_SN = 2,
> >> > + NS_USER_INIT_SN = 3,
> >> > + NS_PID_INIT_SN = 4,
> >>
> >> Please add an extra value here for the first dynamic value...
> >> > +/**
> >> > + * ns_serial - compute a serial number for the namespace
> >> > + *
> >> > + * Compute a serial number for the namespace to uniquely identify it in
> >> > + * audit records.
> >> > + */
> >> > +long long ns_serial(void)
> >> > +{
> >> > + static atomic64_t serial = ATOMIC_INIT(4); /* reserved for IPC, UTS, user, PID */
> >>
> >> ...and use it here.
> >
> > Yup, good idea. Thanks.
> >
> >> Also, does this work on all architectures?
> >
> > I only know for certain x86_64. There is discussion elsewhere about
> > changing ns_serial from returning a long long to returning a u64. That
> > should help. I can run standard compile and boot tests on several
> > others, but won't be able to check output.
>
> I was thinking of atomic64. I guess there's a generic implementation
> that works everywhere, if somewhat slowly.
Yup.
>From include/linux/types.h:
#ifdef CONFIG_64BIT
typedef struct {
long counter;
} atomic64_t;
#endif
>From include/asm-generic/atomic64.h:
typedef struct {
long long counter;
} atomic64_t;
and for non-x86, there is lib/atomic64.c:
atomic64_add_return()
which is in C while the x86_64 version is in ASM.
> --Andy
- RGB
--
Richard Guy Briggs <rbriggs-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
Senior Software Engineer, Kernel Security, AMER ENG Base Operating Systems, Red Hat
Remote, Ottawa, Canada
Voice: +1.647.777.2635, Internal: (81) 32635, Alt: +1.613.693.0684x3545
^ permalink raw reply
* Re: [PATCH V4 0/8] namespaces: log namespaces per task
From: Richard Guy Briggs @ 2014-08-21 22:32 UTC (permalink / raw)
To: Aristeu Rozanski
Cc: linux-api-u79uwXL29TY76Z2rM5mHXA,
containers-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA,
linux-kernel-u79uwXL29TY76Z2rM5mHXA,
eparis-H+wXaHxf7aLQT0dZR+AlfA, linux-audit-H+wXaHxf7aLQT0dZR+AlfA,
ebiederm-aS9lmoZGLiVWk0Htik3J/w, sgrubb-H+wXaHxf7aLQT0dZR+AlfA
In-Reply-To: <20140821200555.GK5620-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
On 14/08/21, Aristeu Rozanski wrote:
> Hi Richard,
Hi Aris,
> On Wed, Aug 20, 2014 at 09:09:33PM -0400, Richard Guy Briggs wrote:
> > Is there a way to link serial numbers of namespaces involved in migration of a
> > container to another kernel? It sounds like what is needed is a part of a
> > mangement application that is able to pull the audit records from constituent
> > hosts to build an audit trail of a container.
>
> since you're introducing a brand new serial number to make it unique
> across different procfs mounts, why not instead of a simple counter,
> use the hash output of say, $hostname-$creation_time-$random?
I had thought of this earlier on, but I could see many VMs started up
from an identical image, making the resulting hash possibly identical.
Besides, hostname isn't known yet when we are creating initial
namespaces.
> Or perhaps
> get a short hash of the hostname (generated once whenever hostname is
> set) and append the serial number you're implementing? It'd be way less human
> readable than your current proposal but it'd be unique "globally" (as long you
> don't have machines with the same hostname migrating containers between them),
> allowing the migrated namespaces to retain their unique identification across
> audit logs. It'd of course be way more costly than just using an atomic counter,
> but could be useful to anything that needs to refer to a namespace and could be
> migrated to another machine.
This also means that any namespace that is migrated would have to be
recreated on another host and inject an existing ID into it rather than
have the host creating it generate that ID. Some namespaces are peers
that take the kernel default, while others are hierarchical and inherit
from their creating namespaces.
It was much easier at my layer to punt that management to a higher
layer that already knew about the other hosts in play and to manage that
information as it saw fit.
> What you think? Sounds too crazy? :)
Yup. I was hoping there would be some kind of unique identifier per
running kernel, including CPU_ID (which may not exist or may be shut
off), RTC boot value (which may be identical for VMs), or initial random
state (which could be identical for VMs).
> Aristeu
- RGB
--
Richard Guy Briggs <rbriggs-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
Senior Software Engineer, Kernel Security, AMER ENG Base Operating Systems, Red Hat
Remote, Ottawa, Canada
Voice: +1.647.777.2635, Internal: (81) 32635, Alt: +1.613.693.0684x3545
^ permalink raw reply
* Re: [PATCH V4 3/8] namespaces: expose ns instance serial numbers in proc
From: Richard Guy Briggs @ 2014-08-22 1:58 UTC (permalink / raw)
To: Andy Lutomirski
Cc: Eric W. Biederman, Eric Paris, Steve Grubb,
arozansk-H+wXaHxf7aLQT0dZR+AlfA,
linux-audit-H+wXaHxf7aLQT0dZR+AlfA, Linux API, Linux Containers,
Serge E. Hallyn,
linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
In-Reply-To: <CALCETrUnzG1V8w+H9ctAJP+Hvo8LQax=dhLG4bBpBKmVi+C1cQ-JsoAwUIsXosN+BqQ9rBEUg@public.gmane.org>
On 14/08/21, Andy Lutomirski wrote:
> On Aug 20, 2014 8:12 PM, "Richard Guy Briggs" <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> > Expose the namespace instace serial numbers in the proc filesystem at
> > /proc/<pid>/ns/<ns>_snum. The link text gives the serial number in hex.
>
> What's the use case?
>
> I understand the utility of giving unique numbers to the audit code,
> but I don't think this part is necessary for that, and I'd like to
> understand what else will use this before committing to a duplicative
> API like this.
How does a container manager get those numbers? It could provoke a task
to cause an audit event that emits a NS_INFO message, or it could run a
task in that container to report its namespace serial numbers directly
from its /proc mount.
The discussion in this thread touches on the use cases:
https://lkml.org/lkml/2014/4/22/662
> Note that this API is thoroughly incompatible with CRIU. If we do
> this, someone will ask for a namespace number namespace, and that way
> lies madness.
I had a very brief look at CRIU, but not enough to understand the issue.
Others have hinted at this problem.
Do you have a suggestion of a different approach that would be
compatible with CRIU?
I'd originally considered some sort of UUID that would be globally
unique, but that would be very hard to devise or guarantee, and besides,
namespaces aren't only used by containers and could be shared in other
ways. Tracking the usage and migration of namespaces should be the task
of an upper layer.
> --Andy
>
> >
> > "snum" was chosen instead of "seq" for consistency with inum and there are a
> > number of other uses of "seq" in the namespace code.
> >
> > Suggested-by: Serge E. Hallyn <serge-A9i7LUbDfNHQT0dZR+AlfA@public.gmane.org>
> > Signed-off-by: Richard Guy Briggs <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
> > ---
> > fs/proc/namespaces.c | 33 +++++++++++++++++++++++++--------
> > 1 files changed, 25 insertions(+), 8 deletions(-)
> >
> > diff --git a/fs/proc/namespaces.c b/fs/proc/namespaces.c
> > index 8902609..e953e0a 100644
> > --- a/fs/proc/namespaces.c
> > +++ b/fs/proc/namespaces.c
> > @@ -47,12 +47,15 @@ static char *ns_dname(struct dentry *dentry, char *buffer, int buflen)
> > struct inode *inode = dentry->d_inode;
> > const struct proc_ns_operations *ns_ops = PROC_I(inode)->ns.ns_ops;
> >
> > - return dynamic_dname(dentry, buffer, buflen, "%s:[%lu]",
> > - ns_ops->name, inode->i_ino);
> > + if (strstr(dentry->d_iname, "_snum"))
> > + return dynamic_dname(dentry, buffer, buflen, "%s_snum:[%llx]",
> > + ns_ops->name, ns_ops->snum(PROC_I(inode)->ns.ns));
> > + else
> > + return dynamic_dname(dentry, buffer, buflen, "%s:[%lu]",
> > + ns_ops->name, inode->i_ino);
> > }
> >
> > -const struct dentry_operations ns_dentry_operations =
> > -{
> > +const struct dentry_operations ns_dentry_operations = {
> > .d_delete = always_delete_dentry,
> > .d_dname = ns_dname,
> > };
> > @@ -160,7 +163,10 @@ static int proc_ns_readlink(struct dentry *dentry, char __user *buffer, int bufl
> > if (!ns)
> > goto out_put_task;
> >
> > - snprintf(name, sizeof(name), "%s:[%u]", ns_ops->name, ns_ops->inum(ns));
> > + if (strstr(dentry->d_iname, "_snum"))
> > + snprintf(name, sizeof(name), "%s_snum:[%llx]", ns_ops->name, ns_ops->snum(ns));
> > + else
> > + snprintf(name, sizeof(name), "%s:[%u]", ns_ops->name, ns_ops->inum(ns));
> > res = readlink_copy(buffer, buflen, name);
> > ns_ops->put(ns);
> > out_put_task:
> > @@ -210,16 +216,23 @@ static int proc_ns_dir_readdir(struct file *file, struct dir_context *ctx)
> >
> > if (!dir_emit_dots(file, ctx))
> > goto out;
> > - if (ctx->pos >= 2 + ARRAY_SIZE(ns_entries))
> > + if (ctx->pos >= 2 + 2 * ARRAY_SIZE(ns_entries))
> > goto out;
> > entry = ns_entries + (ctx->pos - 2);
> > last = &ns_entries[ARRAY_SIZE(ns_entries) - 1];
> > while (entry <= last) {
> > const struct proc_ns_operations *ops = *entry;
> > + char name[50];
> > +
> > if (!proc_fill_cache(file, ctx, ops->name, strlen(ops->name),
> > proc_ns_instantiate, task, ops))
> > break;
> > ctx->pos++;
> > + snprintf(name, sizeof(name), "%s_snum", ops->name);
> > + if (!proc_fill_cache(file, ctx, name, strlen(name),
> > + proc_ns_instantiate, task, ops))
> > + break;
> > + ctx->pos++;
> > entry++;
> > }
> > out:
> > @@ -247,9 +260,13 @@ static struct dentry *proc_ns_dir_lookup(struct inode *dir,
> >
> > last = &ns_entries[ARRAY_SIZE(ns_entries)];
> > for (entry = ns_entries; entry < last; entry++) {
> > - if (strlen((*entry)->name) != len)
> > + char name[50];
> > +
> > + snprintf(name, sizeof(name), "%s_snum", (*entry)->name);
> > + if (strlen((*entry)->name) != len && strlen(name) != len)
> > continue;
> > - if (!memcmp(dentry->d_name.name, (*entry)->name, len))
> > + if (!memcmp(dentry->d_name.name, (*entry)->name, len)
> > + || !memcmp(dentry->d_name.name, name, len))
> > break;
> > }
> > if (entry == last)
> > --
> > 1.7.1
> >
> > --
> > To unsubscribe from this list: send the line "unsubscribe linux-api" in
> > the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> > More majordomo info at http://vger.kernel.org/majordomo-info.html
- RGB
--
Richard Guy Briggs <rbriggs-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
Senior Software Engineer, Kernel Security, AMER ENG Base Operating Systems, Red Hat
Remote, Ottawa, Canada
Voice: +1.647.777.2635, Internal: (81) 32635, Alt: +1.613.693.0684x3545
^ permalink raw reply
* Pharmacy international
From: Sebastian Carson @ 2014-08-22 13:23 UTC (permalink / raw)
To: linux-acpi-u79uwXL29TY76Z2rM5mHXA,
linux-alpha-u79uwXL29TY76Z2rM5mHXA,
linux-api-u79uwXL29TY76Z2rM5mHXA,
linux-arch-u79uwXL29TY76Z2rM5mHXA,
linux-arm-msm-u79uwXL29TY76Z2rM5mHXA
Cc: linux-bluetooth-u79uwXL29TY76Z2rM5mHXA,
linux-btrfs-u79uwXL29TY76Z2rM5mHXA,
linux-cifs-u79uwXL29TY76Z2rM5mHXA,
linux-crypto-u79uwXL29TY76Z2rM5mHXA,
linux-doc-u79uwXL29TY76Z2rM5mHXA,
linux-edac-u79uwXL29TY76Z2rM5mHXA
Cheap medications you can find here
http://doctornnek.cn.com
^ permalink raw reply
* Re: [PATCH V4 1/8] namespaces: assign each namespace instance a serial number
From: Eric W. Biederman @ 2014-08-23 12:05 UTC (permalink / raw)
To: Richard Guy Briggs
Cc: linux-api-u79uwXL29TY76Z2rM5mHXA,
containers-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA,
linux-kernel-u79uwXL29TY76Z2rM5mHXA,
eparis-H+wXaHxf7aLQT0dZR+AlfA, Andy Lutomirski,
linux-audit-H+wXaHxf7aLQT0dZR+AlfA, sgrubb-H+wXaHxf7aLQT0dZR+AlfA
In-Reply-To: <d5bfd81a219c5c45c910494d6a3478ce83052e1f.1408581429.git.rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
Richard Guy Briggs <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> writes:
> Generate and assign a serial number per namespace instance since boot.
>
> Use a serial number per namespace (unique across one boot of one kernel)
> instead of the inode number (which is claimed to have had the right to change
> reserved and is not necessarily unique if there is more than one proc fs) to
> uniquely identify it per kernel boot.
This approach is just broken.
For this to work with migration (aka criu) you need to implement a
namespace of namespaces. You haven't done this, and therefore
such an interface will break existing userspace.
Inside of audit I can understand not caring about these issues,
but you go foward and expose these serial numbers in proc,
and generally make this infrastructure available to others.
The deep issue with migration is that we move tasks from one machine
from another and on the destination machine we need to have all of the
same global identifiers for software to function properly.
My weasel words around the proc inode numbers is to preserve to allow us
room to be able to restore those ids if it every becomes relevant for
migration.
That is the proc inode numbers (technically) live in a pid namespace,
(aka a mount of proc). So depending on the pid namespace you are in
or the mount of proc you look in the numbers could change.
Qualifications like that must exist to have a prayer of ever supporting
process migration in the crazy corner cases where people start caring
about inode numbers.
We currently don't and inode numbers for a namespace will never change
after a namespace is created. So I think you really are ok using the
proc inode numbers. I am happy declaring by fiat that the inode numbers
that audit uses are the numbers connected to the initial pid namespace.
At a fairly basic level anything that is used to identify namespaces for
any general purpose use needs to have most if not all of the same
properties of the proc inode numbers. The most important of which is
being tied to some context/namespace so there is a ability if we ever
need it to migrate those numbers from one machine to another.
Eric
> diff --git a/kernel/nsproxy.c b/kernel/nsproxy.c
> index 8e78110..93cb380 100644
> --- a/kernel/nsproxy.c
> +++ b/kernel/nsproxy.c
> @@ -41,6 +41,23 @@ struct nsproxy init_nsproxy = {
> #endif
> };
>
> +/**
> + * ns_serial - compute a serial number for the namespace
> + *
> + * Compute a serial number for the namespace to uniquely identify it in
> + * audit records.
> + */
> +long long ns_serial(void)
> +{
> + static atomic64_t serial = ATOMIC_INIT(4); /* reserved for IPC, UTS, user, PID */
> + long long ret;
> +
> + ret = atomic64_add_return(1, &serial);
> + BUG_ON(!ret);
> +
> + return ret;
> +}
> +
> static inline struct nsproxy *create_nsproxy(void)
> {
> struct nsproxy *nsproxy;
^ permalink raw reply
* Re: [PATCH V4 3/8] namespaces: expose ns instance serial numbers in proc
From: Andy Lutomirski @ 2014-08-24 17:52 UTC (permalink / raw)
To: Richard Guy Briggs
Cc: Eric W. Biederman, Eric Paris, Steve Grubb,
arozansk-H+wXaHxf7aLQT0dZR+AlfA,
linux-audit-H+wXaHxf7aLQT0dZR+AlfA, Linux API, Linux Containers,
Serge E. Hallyn,
linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
In-Reply-To: <20140822015803.GG20529-bcJWsdo4jJjeVoXN4CMphl7TgLCtbB0G@public.gmane.org>
On Thu, Aug 21, 2014 at 6:58 PM, Richard Guy Briggs <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> On 14/08/21, Andy Lutomirski wrote:
>> On Aug 20, 2014 8:12 PM, "Richard Guy Briggs" <rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
>> > Expose the namespace instace serial numbers in the proc filesystem at
>> > /proc/<pid>/ns/<ns>_snum. The link text gives the serial number in hex.
>>
>> What's the use case?
>>
>> I understand the utility of giving unique numbers to the audit code,
>> but I don't think this part is necessary for that, and I'd like to
>> understand what else will use this before committing to a duplicative
>> API like this.
>
> How does a container manager get those numbers? It could provoke a task
> to cause an audit event that emits a NS_INFO message, or it could run a
> task in that container to report its namespace serial numbers directly
> from its /proc mount.
Why does a container manager need them? Is there any reason that
keeping them entirely contained within the audit system would be a
problem?
>
> The discussion in this thread touches on the use cases:
> https://lkml.org/lkml/2014/4/22/662
>
>> Note that this API is thoroughly incompatible with CRIU. If we do
>> this, someone will ask for a namespace number namespace, and that way
>> lies madness.
>
> I had a very brief look at CRIU, but not enough to understand the issue.
> Others have hinted at this problem.
>
> Do you have a suggestion of a different approach that would be
> compatible with CRIU?
>
> I'd originally considered some sort of UUID that would be globally
> unique, but that would be very hard to devise or guarantee, and besides,
> namespaces aren't only used by containers and could be shared in other
> ways. Tracking the usage and migration of namespaces should be the task
> of an upper layer.
>
CRIU wants to save the complete state of a namespace and then restore
it. For that to work, any information exposed to things in the
namespace *cannot* be globally unique or unique per boot, since CRIU
needs to arrange for that information to match whatever it was when
CRIU saved it.
Also, I think that code running in a namespace has no business even
knowing a unique identity of that namespace from the perspective of
the host.
Here's a specific use case for *not* exposing this: Tor. Ideally, Tor
clients would run in a namespace that does not know about any global
identity. That means no IP addresses, but it also means no global
namespace serial numbers.
--Andy
^ permalink raw reply
* [PATCH v5 net-next 00/29] BPF syscall, maps, verifier, samples, llvm
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api, netdev, linux-kernel
Hi All,
enough RFCs, let's finalize it...
Andy, Kees, please take a look at verifier and syscall API once again.
I hope I addressed all of your comments.
Peter, I played with 'lea [%rip+off]' tricks in JIT as suggested by Andy, but
there was no performance gain and JIT main loop got quite complicated, so
I left it as-is with movabsq. I hope you're ok for now. Let's revisit it later.
Steven, Namhyung, please review the way it attaches to tracing
(tracepoint, syscalls, kprobe)
Brendan, I've added example#3 which is heavily influenced by your heatmap graphs
and ACM paper. It measures disk IO latency and prints heatmap in text terminal
using shades of gray. Looks cool. I've wasted a day trying to make heatmap
be as fancy as on your slides, but I guess my SSDs are too predicatable :)
Fully tested on x64 and i386.
Build/boot tested on arm/sparc with NET and NET-less configs.
(There are warning regarding unimplemented syscall, of course)
V4->V5:
- while playing with tracing examples Brendan noticed that x64 JIT missed
'shift by register' support. fixed and added to testsuite (patch 0001)
- fixed BPF_LD_IMM64 encoding (as suggested by Andy) (patch 0002)
and added verifier tests for this insn (patch 0024)
- enabled bpf syscall on i386 as well (patch 0005)
- added more comments to verifier around bounds checking,
since the logic was confusing to Kees earlier (patch 0014)
- split eBPF out of NET via hidden CONFIG_BPF (patch 0017)
- added bpf_ktime_get_ns() and tracing example#3 (as suggested by Brendan)
(patch 0021 and 0029)
- added a bunch more verifier tests. 42 tests so far (patch 0024)
- dropped ebpf+sockets patch and examples, there was not enough public
discussions on it whereas ebpf+tracing got a lot of mileage
I still owe Brendan better strings support and map[stack()]++ so that
'flame graphs' can work :)
Right now I'd like to focus on getting the current set in, since it's
very useful for performance analysis already.
Steven, if you don't like access to trace_printk() from eBPF programs,
I can drop patch 0019 for now, but we'd need to think of a way to print
things from programs and trace_printk() looks like the best fit.
Netdev folks, this patch doesn't affect any networking bits, but
obviously I would like to apply the technology in the networking space.
Where and how, is tbd. We're still discussing ovs+bpf.
All, most of the diff is LLVM backend (patch 0025), I think it makes
sense to keep it in kernel tree for now. Once backend is upstreamed
we can remove it from here.
IMO this is pretty solid base for all sorts of things.
previous V4 discussion:
https://lkml.org/lkml/2014/8/13/111
V3->V4:
- introduced 'load 64-bit immediate' eBPF instruction
- use BPF_LD_IMM64 in LLVM, verifier, programs
- got rid of 'fixup' section in eBPF programs
- got rid of map IDR and internal map_id
- split verifier into 6 patches and added verifier testsuite
- add verifier check for reserved instruction fields
- fixed bug in LLVM eBPF backend (it was miscompiling __builtin_expect)
- fixed race condition in htab_map_update_elem()
- tracing filters can now attach to tracepoint, syscall, kprobe events
- improved C examples
V2->V3:
- fixed verifier register range bug and addressed other comments (Thanks Kees!)
- re-added LLVM eBPF backend
- added two examples in C
- user space ELF parser and loader example
V1->V2:
- got rid of global id, everything now FD based (Thanks Andy!)
- split type enum in verifier (as suggested by Andy and Namhyung)
- switched gpl enforcement to be kmod like (as suggested by Andy and David)
- addressed feedback from Namhyung, Chema, Joe
- added more comments to verifier
- renamed sock_filter_int -> bpf_insn
- rebased on net-next
As always all patches are available at:
git://git.kernel.org/pub/scm/linux/kernel/git/ast/bpf master
------
Alexei Starovoitov (29):
bpf: x86: add missing 'shift by register' instructions to x64 eBPF
JIT
net: filter: add "load 64-bit immediate" eBPF instruction
net: filter: split filter.h and expose eBPF to user space
bpf: introduce syscall(BPF, ...) and BPF maps
bpf: enable bpf syscall on x64 and i386
bpf: add lookup/update/delete/iterate methods to BPF maps
bpf: add hashtable type of BPF maps
bpf: expand BPF syscall with program load/unload
bpf: handle pseudo BPF_CALL insn
bpf: verifier (add docs)
bpf: verifier (add ability to receive verification log)
bpf: handle pseudo BPF_LD_IMM64 insn
bpf: verifier (add branch/goto checks)
bpf: verifier (add verifier core)
bpf: verifier (add state prunning optimization)
bpf: allow eBPF programs to use maps
bpf: split eBPF out of NET
tracing: allow eBPF programs to be attached to events
tracing: allow eBPF programs call printk()
tracing: allow eBPF programs to be attached to kprobe/kretprobe
tracing: allow eBPF programs to call ktime_get_ns() and get_current()
samples: bpf: add mini eBPF library to manipulate maps and programs
samples: bpf: example of tracing filters with eBPF
bpf: verifier test
bpf: llvm backend
samples: bpf: elf file loader
samples: bpf: eBPF example in C
samples: bpf: counting eBPF example in C
samples: bpf: IO latency analysis (iosnoop/heatmap)
Documentation/networking/filter.txt | 309 +++-
arch/Kconfig | 4 +
arch/x86/net/bpf_jit_comp.c | 59 +
arch/x86/syscalls/syscall_32.tbl | 1 +
arch/x86/syscalls/syscall_64.tbl | 1 +
fs/btrfs/super.c | 3 +
include/linux/bpf.h | 140 ++
include/linux/filter.h | 303 +---
include/linux/ftrace_event.h | 5 +
include/linux/syscalls.h | 3 +-
include/trace/bpf_trace.h | 23 +
include/trace/ftrace.h | 25 +
include/uapi/asm-generic/unistd.h | 4 +-
include/uapi/linux/Kbuild | 1 +
include/uapi/linux/bpf.h | 424 +++++
kernel/Makefile | 2 +-
kernel/bpf/Makefile | 2 +-
kernel/bpf/core.c | 17 +
kernel/bpf/hashtab.c | 372 ++++
kernel/bpf/syscall.c | 658 +++++++
kernel/bpf/verifier.c | 1911 ++++++++++++++++++++
kernel/sys_ni.c | 3 +
kernel/trace/Kconfig | 1 +
kernel/trace/Makefile | 1 +
kernel/trace/bpf_trace.c | 264 +++
kernel/trace/trace.h | 3 +
kernel/trace/trace_events.c | 41 +-
kernel/trace/trace_events_filter.c | 72 +-
kernel/trace/trace_kprobe.c | 28 +
kernel/trace/trace_syscalls.c | 32 +
lib/test_bpf.c | 59 +
net/Kconfig | 1 +
net/core/filter.c | 2 +
samples/bpf/Makefile | 28 +
samples/bpf/bpf_helpers.h | 27 +
samples/bpf/bpf_load.c | 234 +++
samples/bpf/bpf_load.h | 26 +
samples/bpf/dropmon.c | 122 ++
samples/bpf/ex1_kern.c | 27 +
samples/bpf/ex1_user.c | 24 +
samples/bpf/ex2_kern.c | 73 +
samples/bpf/ex2_user.c | 94 +
samples/bpf/ex3_kern.c | 104 ++
samples/bpf/ex3_user.c | 149 ++
samples/bpf/libbpf.c | 138 ++
samples/bpf/libbpf.h | 21 +
samples/bpf/test_verifier.c | 599 ++++++
tools/bpf/llvm/.gitignore | 54 +
tools/bpf/llvm/LICENSE.TXT | 70 +
tools/bpf/llvm/Makefile.rules | 641 +++++++
tools/bpf/llvm/README.txt | 23 +
tools/bpf/llvm/bld/Makefile | 27 +
tools/bpf/llvm/bld/Makefile.common | 14 +
tools/bpf/llvm/bld/Makefile.config | 124 ++
.../llvm/bld/include/llvm/Config/AsmParsers.def | 8 +
.../llvm/bld/include/llvm/Config/AsmPrinters.def | 9 +
.../llvm/bld/include/llvm/Config/Disassemblers.def | 8 +
tools/bpf/llvm/bld/include/llvm/Config/Targets.def | 9 +
.../bpf/llvm/bld/include/llvm/Support/DataTypes.h | 96 +
tools/bpf/llvm/bld/lib/Makefile | 11 +
.../llvm/bld/lib/Target/BPF/InstPrinter/Makefile | 10 +
.../llvm/bld/lib/Target/BPF/MCTargetDesc/Makefile | 11 +
tools/bpf/llvm/bld/lib/Target/BPF/Makefile | 17 +
.../llvm/bld/lib/Target/BPF/TargetInfo/Makefile | 10 +
tools/bpf/llvm/bld/lib/Target/Makefile | 11 +
tools/bpf/llvm/bld/tools/Makefile | 12 +
tools/bpf/llvm/bld/tools/llc/Makefile | 15 +
tools/bpf/llvm/lib/Target/BPF/BPF.h | 28 +
tools/bpf/llvm/lib/Target/BPF/BPF.td | 29 +
tools/bpf/llvm/lib/Target/BPF/BPFAsmPrinter.cpp | 100 +
tools/bpf/llvm/lib/Target/BPF/BPFCallingConv.td | 24 +
tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.cpp | 36 +
tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.h | 35 +
tools/bpf/llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp | 182 ++
tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.cpp | 683 +++++++
tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.h | 105 ++
tools/bpf/llvm/lib/Target/BPF/BPFInstrFormats.td | 29 +
tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.cpp | 162 ++
tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.h | 53 +
tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.td | 498 +++++
tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.cpp | 77 +
tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.h | 40 +
tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.cpp | 122 ++
tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.h | 65 +
tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.td | 39 +
tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.cpp | 23 +
tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.h | 33 +
tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.cpp | 66 +
tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.h | 69 +
.../lib/Target/BPF/InstPrinter/BPFInstPrinter.cpp | 81 +
.../lib/Target/BPF/InstPrinter/BPFInstPrinter.h | 34 +
.../lib/Target/BPF/MCTargetDesc/BPFAsmBackend.cpp | 89 +
.../llvm/lib/Target/BPF/MCTargetDesc/BPFBaseInfo.h | 33 +
.../Target/BPF/MCTargetDesc/BPFELFObjectWriter.cpp | 56 +
.../lib/Target/BPF/MCTargetDesc/BPFMCAsmInfo.h | 34 +
.../Target/BPF/MCTargetDesc/BPFMCCodeEmitter.cpp | 167 ++
.../Target/BPF/MCTargetDesc/BPFMCTargetDesc.cpp | 115 ++
.../lib/Target/BPF/MCTargetDesc/BPFMCTargetDesc.h | 56 +
.../lib/Target/BPF/TargetInfo/BPFTargetInfo.cpp | 13 +
tools/bpf/llvm/tools/llc/llc.cpp | 381 ++++
100 files changed, 10875 insertions(+), 302 deletions(-)
create mode 100644 include/linux/bpf.h
create mode 100644 include/trace/bpf_trace.h
create mode 100644 include/uapi/linux/bpf.h
create mode 100644 kernel/bpf/hashtab.c
create mode 100644 kernel/bpf/syscall.c
create mode 100644 kernel/bpf/verifier.c
create mode 100644 kernel/trace/bpf_trace.c
create mode 100644 samples/bpf/Makefile
create mode 100644 samples/bpf/bpf_helpers.h
create mode 100644 samples/bpf/bpf_load.c
create mode 100644 samples/bpf/bpf_load.h
create mode 100644 samples/bpf/dropmon.c
create mode 100644 samples/bpf/ex1_kern.c
create mode 100644 samples/bpf/ex1_user.c
create mode 100644 samples/bpf/ex2_kern.c
create mode 100644 samples/bpf/ex2_user.c
create mode 100644 samples/bpf/ex3_kern.c
create mode 100644 samples/bpf/ex3_user.c
create mode 100644 samples/bpf/libbpf.c
create mode 100644 samples/bpf/libbpf.h
create mode 100644 samples/bpf/test_verifier.c
create mode 100644 tools/bpf/llvm/.gitignore
create mode 100644 tools/bpf/llvm/LICENSE.TXT
create mode 100644 tools/bpf/llvm/Makefile.rules
create mode 100644 tools/bpf/llvm/README.txt
create mode 100644 tools/bpf/llvm/bld/Makefile
create mode 100644 tools/bpf/llvm/bld/Makefile.common
create mode 100644 tools/bpf/llvm/bld/Makefile.config
create mode 100644 tools/bpf/llvm/bld/include/llvm/Config/AsmParsers.def
create mode 100644 tools/bpf/llvm/bld/include/llvm/Config/AsmPrinters.def
create mode 100644 tools/bpf/llvm/bld/include/llvm/Config/Disassemblers.def
create mode 100644 tools/bpf/llvm/bld/include/llvm/Config/Targets.def
create mode 100644 tools/bpf/llvm/bld/include/llvm/Support/DataTypes.h
create mode 100644 tools/bpf/llvm/bld/lib/Makefile
create mode 100644 tools/bpf/llvm/bld/lib/Target/BPF/InstPrinter/Makefile
create mode 100644 tools/bpf/llvm/bld/lib/Target/BPF/MCTargetDesc/Makefile
create mode 100644 tools/bpf/llvm/bld/lib/Target/BPF/Makefile
create mode 100644 tools/bpf/llvm/bld/lib/Target/BPF/TargetInfo/Makefile
create mode 100644 tools/bpf/llvm/bld/lib/Target/Makefile
create mode 100644 tools/bpf/llvm/bld/tools/Makefile
create mode 100644 tools/bpf/llvm/bld/tools/llc/Makefile
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPF.h
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPF.td
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFAsmPrinter.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFCallingConv.td
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.h
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.h
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFInstrFormats.td
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.h
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.td
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.h
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.h
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.td
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.h
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.h
create mode 100644 tools/bpf/llvm/lib/Target/BPF/InstPrinter/BPFInstPrinter.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/InstPrinter/BPFInstPrinter.h
create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFAsmBackend.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFBaseInfo.h
create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFELFObjectWriter.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCAsmInfo.h
create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCCodeEmitter.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCTargetDesc.cpp
create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCTargetDesc.h
create mode 100644 tools/bpf/llvm/lib/Target/BPF/TargetInfo/BPFTargetInfo.cpp
create mode 100644 tools/bpf/llvm/tools/llc/llc.cpp
--
1.7.9.5
^ permalink raw reply
* [PATCH v5 net-next 01/29] bpf: x86: add missing 'shift by register' instructions to x64 eBPF JIT
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api, netdev, linux-kernel
In-Reply-To: <1408911690-7598-1-git-send-email-ast@plumgrid.com>
'shift by register' operations are supported by eBPF interpreter, but were
accidently left out of x64 JIT compiler. Fix it and add a testcase.
Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
---
arch/x86/net/bpf_jit_comp.c | 42 ++++++++++++++++++++++++++++++++++++++++++
lib/test_bpf.c | 38 ++++++++++++++++++++++++++++++++++++++
2 files changed, 80 insertions(+)
diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index 5c8cb8043c5a..b08a98c59530 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -515,6 +515,48 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
EMIT3(0xC1, add_1reg(b3, dst_reg), imm32);
break;
+ case BPF_ALU | BPF_LSH | BPF_X:
+ case BPF_ALU | BPF_RSH | BPF_X:
+ case BPF_ALU | BPF_ARSH | BPF_X:
+ case BPF_ALU64 | BPF_LSH | BPF_X:
+ case BPF_ALU64 | BPF_RSH | BPF_X:
+ case BPF_ALU64 | BPF_ARSH | BPF_X:
+
+ /* check for bad case when dst_reg == rcx */
+ if (dst_reg == BPF_REG_4) {
+ /* mov r11, dst_reg */
+ EMIT_mov(AUX_REG, dst_reg);
+ dst_reg = AUX_REG;
+ }
+
+ if (src_reg != BPF_REG_4) { /* common case */
+ EMIT1(0x51); /* push rcx */
+
+ /* mov rcx, src_reg */
+ EMIT_mov(BPF_REG_4, src_reg);
+ }
+
+ /* shl %rax, %cl | shr %rax, %cl | sar %rax, %cl */
+ if (BPF_CLASS(insn->code) == BPF_ALU64)
+ EMIT1(add_1mod(0x48, dst_reg));
+ else if (is_ereg(dst_reg))
+ EMIT1(add_1mod(0x40, dst_reg));
+
+ switch (BPF_OP(insn->code)) {
+ case BPF_LSH: b3 = 0xE0; break;
+ case BPF_RSH: b3 = 0xE8; break;
+ case BPF_ARSH: b3 = 0xF8; break;
+ }
+ EMIT2(0xD3, add_1reg(b3, dst_reg));
+
+ if (src_reg != BPF_REG_4)
+ EMIT1(0x59); /* pop rcx */
+
+ if (insn->dst_reg == BPF_REG_4)
+ /* mov dst_reg, r11 */
+ EMIT_mov(insn->dst_reg, AUX_REG);
+ break;
+
case BPF_ALU | BPF_END | BPF_FROM_BE:
switch (imm32) {
case 16:
diff --git a/lib/test_bpf.c b/lib/test_bpf.c
index 89e0345733bd..8c66c6aace04 100644
--- a/lib/test_bpf.c
+++ b/lib/test_bpf.c
@@ -1342,6 +1342,44 @@ static struct bpf_test tests[] = {
{ { 0, -1 } }
},
{
+ "INT: shifts by register",
+ .u.insns_int = {
+ BPF_MOV64_IMM(R0, -1234),
+ BPF_MOV64_IMM(R1, 1),
+ BPF_ALU32_REG(BPF_RSH, R0, R1),
+ BPF_JMP_IMM(BPF_JEQ, R0, 0x7ffffd97, 1),
+ BPF_EXIT_INSN(),
+ BPF_MOV64_IMM(R2, 1),
+ BPF_ALU64_REG(BPF_LSH, R0, R2),
+ BPF_MOV32_IMM(R4, -1234),
+ BPF_JMP_REG(BPF_JEQ, R0, R4, 1),
+ BPF_EXIT_INSN(),
+ BPF_ALU64_IMM(BPF_AND, R4, 63),
+ BPF_ALU64_REG(BPF_LSH, R0, R4), /* R0 <= 46 */
+ BPF_MOV64_IMM(R3, 47),
+ BPF_ALU64_REG(BPF_ARSH, R0, R3),
+ BPF_JMP_IMM(BPF_JEQ, R0, -617, 1),
+ BPF_EXIT_INSN(),
+ BPF_MOV64_IMM(R2, 1),
+ BPF_ALU64_REG(BPF_LSH, R4, R2), /* R4 = 46 << 1 */
+ BPF_JMP_IMM(BPF_JEQ, R4, 92, 1),
+ BPF_EXIT_INSN(),
+ BPF_MOV64_IMM(R4, 4),
+ BPF_ALU64_REG(BPF_LSH, R4, R4), /* R4 = 4 << 4 */
+ BPF_JMP_IMM(BPF_JEQ, R4, 64, 1),
+ BPF_EXIT_INSN(),
+ BPF_MOV64_IMM(R4, 5),
+ BPF_ALU32_REG(BPF_LSH, R4, R4), /* R4 = 5 << 5 */
+ BPF_JMP_IMM(BPF_JEQ, R4, 160, 1),
+ BPF_EXIT_INSN(),
+ BPF_MOV64_IMM(R0, -1),
+ BPF_EXIT_INSN(),
+ },
+ INTERNAL,
+ { },
+ { { 0, -1 } }
+ },
+ {
"INT: DIV + ABS",
.u.insns_int = {
BPF_ALU64_REG(BPF_MOV, R6, R1),
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 02/29] net: filter: add "load 64-bit immediate" eBPF instruction
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api, netdev, linux-kernel
In-Reply-To: <1408911690-7598-1-git-send-email-ast@plumgrid.com>
add BPF_LD_IMM64 instruction to load 64-bit immediate value into a register.
All previous instructions were 8-byte. This is first 16-byte instruction.
Two consecutive 'struct bpf_insn' blocks are interpreted as single instruction:
insn[0].code = BPF_LD | BPF_DW | BPF_IMM
insn[0].dst_reg = destination register
insn[0].imm = lower 32-bit
insn[1].code = 0
insn[1].imm = upper 32-bit
All unused fields must be zero.
Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM
which loads 32-bit immediate value into a register.
x64 JITs it as single 'movabsq %rax, imm64'
arm64 may JIT as sequence of four 'movk x0, #imm16, lsl #shift' insn
Note that old eBPF programs are binary compatible with new interpreter.
In the following patches this instruction is used to store eBPF map pointers:
BPF_LD_IMM64(R1, const_imm_map_ptr)
BPF_CALL(BPF_FUNC_map_lookup_elem)
and verifier is introduced to check validity of the programs.
Later LLVM compiler is using this insn as generic load of 64-bit immediate
constant and as a load of map pointer with relocation.
Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
---
Documentation/networking/filter.txt | 8 +++++++-
arch/x86/net/bpf_jit_comp.c | 17 +++++++++++++++++
include/linux/filter.h | 18 ++++++++++++++++++
kernel/bpf/core.c | 5 +++++
lib/test_bpf.c | 21 +++++++++++++++++++++
5 files changed, 68 insertions(+), 1 deletion(-)
diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt
index c48a9704bda8..81916ab5d96f 100644
--- a/Documentation/networking/filter.txt
+++ b/Documentation/networking/filter.txt
@@ -951,7 +951,7 @@ Size modifier is one of ...
Mode modifier is one of:
- BPF_IMM 0x00 /* classic BPF only, reserved in eBPF */
+ BPF_IMM 0x00 /* used for 32-bit mov in classic BPF and 64-bit in eBPF */
BPF_ABS 0x20
BPF_IND 0x40
BPF_MEM 0x60
@@ -995,6 +995,12 @@ BPF_XADD | BPF_DW | BPF_STX: lock xadd *(u64 *)(dst_reg + off16) += src_reg
Where size is one of: BPF_B or BPF_H or BPF_W or BPF_DW. Note that 1 and
2 byte atomic increments are not supported.
+eBPF has one 16-byte instruction: BPF_LD | BPF_DW | BPF_IMM which consists
+of two consecutive 'struct bpf_insn' 8-byte blocks and interpreted as single
+instruction that loads 64-bit immediate value into a dst_reg.
+Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads
+32-bit immediate value into a register.
+
Testing
-------
diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index b08a98c59530..98837147ee57 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -393,6 +393,23 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
EMIT1_off32(add_1reg(0xB8, dst_reg), imm32);
break;
+ case BPF_LD | BPF_IMM | BPF_DW:
+ if (insn[1].code != 0 || insn[1].src_reg != 0 ||
+ insn[1].dst_reg != 0 || insn[1].off != 0) {
+ /* verifier must catch invalid insns */
+ pr_err("invalid BPF_LD_IMM64 insn\n");
+ return -EINVAL;
+ }
+
+ /* movabsq %rax, imm64 */
+ EMIT2(add_1mod(0x48, dst_reg), add_1reg(0xB8, dst_reg));
+ EMIT(insn[0].imm, 4);
+ EMIT(insn[1].imm, 4);
+
+ insn++;
+ i++;
+ break;
+
/* dst %= src, dst /= src, dst %= imm32, dst /= imm32 */
case BPF_ALU | BPF_MOD | BPF_X:
case BPF_ALU | BPF_DIV | BPF_X:
diff --git a/include/linux/filter.h b/include/linux/filter.h
index a5227ab8ccb1..f3262b598262 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -161,6 +161,24 @@ enum {
.off = 0, \
.imm = IMM })
+/* BPF_LD_IMM64 macro encodes single 'load 64-bit immediate' insn */
+#define BPF_LD_IMM64(DST, IMM) \
+ BPF_LD_IMM64_RAW(DST, 0, IMM)
+
+#define BPF_LD_IMM64_RAW(DST, SRC, IMM) \
+ ((struct bpf_insn) { \
+ .code = BPF_LD | BPF_DW | BPF_IMM, \
+ .dst_reg = DST, \
+ .src_reg = SRC, \
+ .off = 0, \
+ .imm = (__u32) (IMM) }), \
+ ((struct bpf_insn) { \
+ .code = 0, /* zero is reserved opcode */ \
+ .dst_reg = 0, \
+ .src_reg = 0, \
+ .off = 0, \
+ .imm = ((__u64) (IMM)) >> 32 })
+
/* Short form of mov based on type, BPF_X: dst_reg = src_reg, BPF_K: dst_reg = imm32 */
#define BPF_MOV64_RAW(TYPE, DST, SRC, IMM) \
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 7f0dbcbb34af..0434c2170f2b 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -180,6 +180,7 @@ static unsigned int __bpf_prog_run(void *ctx, const struct bpf_insn *insn)
[BPF_LD | BPF_IND | BPF_W] = &&LD_IND_W,
[BPF_LD | BPF_IND | BPF_H] = &&LD_IND_H,
[BPF_LD | BPF_IND | BPF_B] = &&LD_IND_B,
+ [BPF_LD | BPF_IMM | BPF_DW] = &&LD_IMM_DW,
};
void *ptr;
int off;
@@ -239,6 +240,10 @@ select_insn:
ALU64_MOV_K:
DST = IMM;
CONT;
+ LD_IMM_DW:
+ DST = (u64) (u32) insn[0].imm | ((u64) (u32) insn[1].imm) << 32;
+ insn++;
+ CONT;
ALU64_ARSH_X:
(*(s64 *) &DST) >>= SRC;
CONT;
diff --git a/lib/test_bpf.c b/lib/test_bpf.c
index 8c66c6aace04..46ab1a7ef135 100644
--- a/lib/test_bpf.c
+++ b/lib/test_bpf.c
@@ -1735,6 +1735,27 @@ static struct bpf_test tests[] = {
{ },
{ { 1, 0 } },
},
+ {
+ "load 64-bit immediate",
+ .u.insns_int = {
+ BPF_LD_IMM64(R1, 0x567800001234L),
+ BPF_MOV64_REG(R2, R1),
+ BPF_MOV64_REG(R3, R2),
+ BPF_ALU64_IMM(BPF_RSH, R2, 32),
+ BPF_ALU64_IMM(BPF_LSH, R3, 32),
+ BPF_ALU64_IMM(BPF_RSH, R3, 32),
+ BPF_ALU64_IMM(BPF_MOV, R0, 0),
+ BPF_JMP_IMM(BPF_JEQ, R2, 0x5678, 1),
+ BPF_EXIT_INSN(),
+ BPF_JMP_IMM(BPF_JEQ, R3, 0x1234, 1),
+ BPF_EXIT_INSN(),
+ BPF_ALU64_IMM(BPF_MOV, R0, 1),
+ BPF_EXIT_INSN(),
+ },
+ INTERNAL,
+ { },
+ { { 0, 1 } }
+ },
};
static struct net_device dev;
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 03/29] net: filter: split filter.h and expose eBPF to user space
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api, netdev, linux-kernel
In-Reply-To: <1408911690-7598-1-git-send-email-ast@plumgrid.com>
eBPF can be used from user space.
uapi/linux/bpf.h: eBPF instruction set definition
linux/filter.h: the rest
This patch only moves macro definitions, but practically it freezes existing
eBPF instruction set, though new instructions can still be added in the future.
These eBPF definitions cannot go into uapi/linux/filter.h, since the names
may conflict with existing applications.
Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
---
include/linux/filter.h | 312 +------------------------------------------
include/uapi/linux/Kbuild | 1 +
include/uapi/linux/bpf.h | 321 +++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 323 insertions(+), 311 deletions(-)
create mode 100644 include/uapi/linux/bpf.h
diff --git a/include/linux/filter.h b/include/linux/filter.h
index f3262b598262..f04793474d16 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -9,322 +9,12 @@
#include <linux/skbuff.h>
#include <linux/workqueue.h>
#include <uapi/linux/filter.h>
-
-/* Internally used and optimized filter representation with extended
- * instruction set based on top of classic BPF.
- */
-
-/* instruction classes */
-#define BPF_ALU64 0x07 /* alu mode in double word width */
-
-/* ld/ldx fields */
-#define BPF_DW 0x18 /* double word */
-#define BPF_XADD 0xc0 /* exclusive add */
-
-/* alu/jmp fields */
-#define BPF_MOV 0xb0 /* mov reg to reg */
-#define BPF_ARSH 0xc0 /* sign extending arithmetic shift right */
-
-/* change endianness of a register */
-#define BPF_END 0xd0 /* flags for endianness conversion: */
-#define BPF_TO_LE 0x00 /* convert to little-endian */
-#define BPF_TO_BE 0x08 /* convert to big-endian */
-#define BPF_FROM_LE BPF_TO_LE
-#define BPF_FROM_BE BPF_TO_BE
-
-#define BPF_JNE 0x50 /* jump != */
-#define BPF_JSGT 0x60 /* SGT is signed '>', GT in x86 */
-#define BPF_JSGE 0x70 /* SGE is signed '>=', GE in x86 */
-#define BPF_CALL 0x80 /* function call */
-#define BPF_EXIT 0x90 /* function return */
-
-/* Register numbers */
-enum {
- BPF_REG_0 = 0,
- BPF_REG_1,
- BPF_REG_2,
- BPF_REG_3,
- BPF_REG_4,
- BPF_REG_5,
- BPF_REG_6,
- BPF_REG_7,
- BPF_REG_8,
- BPF_REG_9,
- BPF_REG_10,
- __MAX_BPF_REG,
-};
-
-/* BPF has 10 general purpose 64-bit registers and stack frame. */
-#define MAX_BPF_REG __MAX_BPF_REG
-
-/* ArgX, context and stack frame pointer register positions. Note,
- * Arg1, Arg2, Arg3, etc are used as argument mappings of function
- * calls in BPF_CALL instruction.
- */
-#define BPF_REG_ARG1 BPF_REG_1
-#define BPF_REG_ARG2 BPF_REG_2
-#define BPF_REG_ARG3 BPF_REG_3
-#define BPF_REG_ARG4 BPF_REG_4
-#define BPF_REG_ARG5 BPF_REG_5
-#define BPF_REG_CTX BPF_REG_6
-#define BPF_REG_FP BPF_REG_10
-
-/* Additional register mappings for converted user programs. */
-#define BPF_REG_A BPF_REG_0
-#define BPF_REG_X BPF_REG_7
-#define BPF_REG_TMP BPF_REG_8
-
-/* BPF program can access up to 512 bytes of stack space. */
-#define MAX_BPF_STACK 512
-
-/* Helper macros for filter block array initializers. */
-
-/* ALU ops on registers, bpf_add|sub|...: dst_reg += src_reg */
-
-#define BPF_ALU64_REG(OP, DST, SRC) \
- ((struct bpf_insn) { \
- .code = BPF_ALU64 | BPF_OP(OP) | BPF_X, \
- .dst_reg = DST, \
- .src_reg = SRC, \
- .off = 0, \
- .imm = 0 })
-
-#define BPF_ALU32_REG(OP, DST, SRC) \
- ((struct bpf_insn) { \
- .code = BPF_ALU | BPF_OP(OP) | BPF_X, \
- .dst_reg = DST, \
- .src_reg = SRC, \
- .off = 0, \
- .imm = 0 })
-
-/* ALU ops on immediates, bpf_add|sub|...: dst_reg += imm32 */
-
-#define BPF_ALU64_IMM(OP, DST, IMM) \
- ((struct bpf_insn) { \
- .code = BPF_ALU64 | BPF_OP(OP) | BPF_K, \
- .dst_reg = DST, \
- .src_reg = 0, \
- .off = 0, \
- .imm = IMM })
-
-#define BPF_ALU32_IMM(OP, DST, IMM) \
- ((struct bpf_insn) { \
- .code = BPF_ALU | BPF_OP(OP) | BPF_K, \
- .dst_reg = DST, \
- .src_reg = 0, \
- .off = 0, \
- .imm = IMM })
-
-/* Endianess conversion, cpu_to_{l,b}e(), {l,b}e_to_cpu() */
-
-#define BPF_ENDIAN(TYPE, DST, LEN) \
- ((struct bpf_insn) { \
- .code = BPF_ALU | BPF_END | BPF_SRC(TYPE), \
- .dst_reg = DST, \
- .src_reg = 0, \
- .off = 0, \
- .imm = LEN })
-
-/* Short form of mov, dst_reg = src_reg */
-
-#define BPF_MOV64_REG(DST, SRC) \
- ((struct bpf_insn) { \
- .code = BPF_ALU64 | BPF_MOV | BPF_X, \
- .dst_reg = DST, \
- .src_reg = SRC, \
- .off = 0, \
- .imm = 0 })
-
-#define BPF_MOV32_REG(DST, SRC) \
- ((struct bpf_insn) { \
- .code = BPF_ALU | BPF_MOV | BPF_X, \
- .dst_reg = DST, \
- .src_reg = SRC, \
- .off = 0, \
- .imm = 0 })
-
-/* Short form of mov, dst_reg = imm32 */
-
-#define BPF_MOV64_IMM(DST, IMM) \
- ((struct bpf_insn) { \
- .code = BPF_ALU64 | BPF_MOV | BPF_K, \
- .dst_reg = DST, \
- .src_reg = 0, \
- .off = 0, \
- .imm = IMM })
-
-#define BPF_MOV32_IMM(DST, IMM) \
- ((struct bpf_insn) { \
- .code = BPF_ALU | BPF_MOV | BPF_K, \
- .dst_reg = DST, \
- .src_reg = 0, \
- .off = 0, \
- .imm = IMM })
-
-/* BPF_LD_IMM64 macro encodes single 'load 64-bit immediate' insn */
-#define BPF_LD_IMM64(DST, IMM) \
- BPF_LD_IMM64_RAW(DST, 0, IMM)
-
-#define BPF_LD_IMM64_RAW(DST, SRC, IMM) \
- ((struct bpf_insn) { \
- .code = BPF_LD | BPF_DW | BPF_IMM, \
- .dst_reg = DST, \
- .src_reg = SRC, \
- .off = 0, \
- .imm = (__u32) (IMM) }), \
- ((struct bpf_insn) { \
- .code = 0, /* zero is reserved opcode */ \
- .dst_reg = 0, \
- .src_reg = 0, \
- .off = 0, \
- .imm = ((__u64) (IMM)) >> 32 })
-
-/* Short form of mov based on type, BPF_X: dst_reg = src_reg, BPF_K: dst_reg = imm32 */
-
-#define BPF_MOV64_RAW(TYPE, DST, SRC, IMM) \
- ((struct bpf_insn) { \
- .code = BPF_ALU64 | BPF_MOV | BPF_SRC(TYPE), \
- .dst_reg = DST, \
- .src_reg = SRC, \
- .off = 0, \
- .imm = IMM })
-
-#define BPF_MOV32_RAW(TYPE, DST, SRC, IMM) \
- ((struct bpf_insn) { \
- .code = BPF_ALU | BPF_MOV | BPF_SRC(TYPE), \
- .dst_reg = DST, \
- .src_reg = SRC, \
- .off = 0, \
- .imm = IMM })
-
-/* Direct packet access, R0 = *(uint *) (skb->data + imm32) */
-
-#define BPF_LD_ABS(SIZE, IMM) \
- ((struct bpf_insn) { \
- .code = BPF_LD | BPF_SIZE(SIZE) | BPF_ABS, \
- .dst_reg = 0, \
- .src_reg = 0, \
- .off = 0, \
- .imm = IMM })
-
-/* Indirect packet access, R0 = *(uint *) (skb->data + src_reg + imm32) */
-
-#define BPF_LD_IND(SIZE, SRC, IMM) \
- ((struct bpf_insn) { \
- .code = BPF_LD | BPF_SIZE(SIZE) | BPF_IND, \
- .dst_reg = 0, \
- .src_reg = SRC, \
- .off = 0, \
- .imm = IMM })
-
-/* Memory load, dst_reg = *(uint *) (src_reg + off16) */
-
-#define BPF_LDX_MEM(SIZE, DST, SRC, OFF) \
- ((struct bpf_insn) { \
- .code = BPF_LDX | BPF_SIZE(SIZE) | BPF_MEM, \
- .dst_reg = DST, \
- .src_reg = SRC, \
- .off = OFF, \
- .imm = 0 })
-
-/* Memory store, *(uint *) (dst_reg + off16) = src_reg */
-
-#define BPF_STX_MEM(SIZE, DST, SRC, OFF) \
- ((struct bpf_insn) { \
- .code = BPF_STX | BPF_SIZE(SIZE) | BPF_MEM, \
- .dst_reg = DST, \
- .src_reg = SRC, \
- .off = OFF, \
- .imm = 0 })
-
-/* Memory store, *(uint *) (dst_reg + off16) = imm32 */
-
-#define BPF_ST_MEM(SIZE, DST, OFF, IMM) \
- ((struct bpf_insn) { \
- .code = BPF_ST | BPF_SIZE(SIZE) | BPF_MEM, \
- .dst_reg = DST, \
- .src_reg = 0, \
- .off = OFF, \
- .imm = IMM })
-
-/* Conditional jumps against registers, if (dst_reg 'op' src_reg) goto pc + off16 */
-
-#define BPF_JMP_REG(OP, DST, SRC, OFF) \
- ((struct bpf_insn) { \
- .code = BPF_JMP | BPF_OP(OP) | BPF_X, \
- .dst_reg = DST, \
- .src_reg = SRC, \
- .off = OFF, \
- .imm = 0 })
-
-/* Conditional jumps against immediates, if (dst_reg 'op' imm32) goto pc + off16 */
-
-#define BPF_JMP_IMM(OP, DST, IMM, OFF) \
- ((struct bpf_insn) { \
- .code = BPF_JMP | BPF_OP(OP) | BPF_K, \
- .dst_reg = DST, \
- .src_reg = 0, \
- .off = OFF, \
- .imm = IMM })
-
-/* Function call */
-
-#define BPF_EMIT_CALL(FUNC) \
- ((struct bpf_insn) { \
- .code = BPF_JMP | BPF_CALL, \
- .dst_reg = 0, \
- .src_reg = 0, \
- .off = 0, \
- .imm = ((FUNC) - __bpf_call_base) })
-
-/* Raw code statement block */
-
-#define BPF_RAW_INSN(CODE, DST, SRC, OFF, IMM) \
- ((struct bpf_insn) { \
- .code = CODE, \
- .dst_reg = DST, \
- .src_reg = SRC, \
- .off = OFF, \
- .imm = IMM })
-
-/* Program exit */
-
-#define BPF_EXIT_INSN() \
- ((struct bpf_insn) { \
- .code = BPF_JMP | BPF_EXIT, \
- .dst_reg = 0, \
- .src_reg = 0, \
- .off = 0, \
- .imm = 0 })
-
-#define bytes_to_bpf_size(bytes) \
-({ \
- int bpf_size = -EINVAL; \
- \
- if (bytes == sizeof(u8)) \
- bpf_size = BPF_B; \
- else if (bytes == sizeof(u16)) \
- bpf_size = BPF_H; \
- else if (bytes == sizeof(u32)) \
- bpf_size = BPF_W; \
- else if (bytes == sizeof(u64)) \
- bpf_size = BPF_DW; \
- \
- bpf_size; \
-})
+#include <uapi/linux/bpf.h>
/* Macro to invoke filter function. */
#define SK_RUN_FILTER(filter, ctx) \
(*filter->prog->bpf_func)(ctx, filter->prog->insnsi)
-struct bpf_insn {
- __u8 code; /* opcode */
- __u8 dst_reg:4; /* dest register */
- __u8 src_reg:4; /* source register */
- __s16 off; /* signed offset */
- __s32 imm; /* signed immediate constant */
-};
-
#ifdef CONFIG_COMPAT
/* A struct sock_filter is architecture independent. */
struct compat_sock_fprog {
diff --git a/include/uapi/linux/Kbuild b/include/uapi/linux/Kbuild
index 24e9033f8b3f..fb3f7b675229 100644
--- a/include/uapi/linux/Kbuild
+++ b/include/uapi/linux/Kbuild
@@ -67,6 +67,7 @@ header-y += bfs_fs.h
header-y += binfmts.h
header-y += blkpg.h
header-y += blktrace_api.h
+header-y += bpf.h
header-y += bpqether.h
header-y += bsg.h
header-y += btrfs.h
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
new file mode 100644
index 000000000000..45a09b46c578
--- /dev/null
+++ b/include/uapi/linux/bpf.h
@@ -0,0 +1,321 @@
+/* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General Public
+ * License as published by the Free Software Foundation.
+ */
+#ifndef _UAPI__LINUX_BPF_H__
+#define _UAPI__LINUX_BPF_H__
+
+#include <linux/types.h>
+
+/* Extended instruction set based on top of classic BPF */
+
+/* instruction classes */
+#define BPF_ALU64 0x07 /* alu mode in double word width */
+
+/* ld/ldx fields */
+#define BPF_DW 0x18 /* double word */
+#define BPF_XADD 0xc0 /* exclusive add */
+
+/* alu/jmp fields */
+#define BPF_MOV 0xb0 /* mov reg to reg */
+#define BPF_ARSH 0xc0 /* sign extending arithmetic shift right */
+
+/* change endianness of a register */
+#define BPF_END 0xd0 /* flags for endianness conversion: */
+#define BPF_TO_LE 0x00 /* convert to little-endian */
+#define BPF_TO_BE 0x08 /* convert to big-endian */
+#define BPF_FROM_LE BPF_TO_LE
+#define BPF_FROM_BE BPF_TO_BE
+
+#define BPF_JNE 0x50 /* jump != */
+#define BPF_JSGT 0x60 /* SGT is signed '>', GT in x86 */
+#define BPF_JSGE 0x70 /* SGE is signed '>=', GE in x86 */
+#define BPF_CALL 0x80 /* function call */
+#define BPF_EXIT 0x90 /* function return */
+
+/* Register numbers */
+enum {
+ BPF_REG_0 = 0,
+ BPF_REG_1,
+ BPF_REG_2,
+ BPF_REG_3,
+ BPF_REG_4,
+ BPF_REG_5,
+ BPF_REG_6,
+ BPF_REG_7,
+ BPF_REG_8,
+ BPF_REG_9,
+ BPF_REG_10,
+ __MAX_BPF_REG,
+};
+
+/* BPF has 10 general purpose 64-bit registers and stack frame. */
+#define MAX_BPF_REG __MAX_BPF_REG
+
+/* ArgX, context and stack frame pointer register positions. Note,
+ * Arg1, Arg2, Arg3, etc are used as argument mappings of function
+ * calls in BPF_CALL instruction.
+ */
+#define BPF_REG_ARG1 BPF_REG_1
+#define BPF_REG_ARG2 BPF_REG_2
+#define BPF_REG_ARG3 BPF_REG_3
+#define BPF_REG_ARG4 BPF_REG_4
+#define BPF_REG_ARG5 BPF_REG_5
+#define BPF_REG_CTX BPF_REG_6
+#define BPF_REG_FP BPF_REG_10
+
+/* Additional register mappings for converted user programs. */
+#define BPF_REG_A BPF_REG_0
+#define BPF_REG_X BPF_REG_7
+#define BPF_REG_TMP BPF_REG_8
+
+/* BPF program can access up to 512 bytes of stack space. */
+#define MAX_BPF_STACK 512
+
+/* Helper macros for filter block array initializers. */
+
+/* ALU ops on registers, bpf_add|sub|...: dst_reg += src_reg */
+
+#define BPF_ALU64_REG(OP, DST, SRC) \
+ ((struct bpf_insn) { \
+ .code = BPF_ALU64 | BPF_OP(OP) | BPF_X, \
+ .dst_reg = DST, \
+ .src_reg = SRC, \
+ .off = 0, \
+ .imm = 0 })
+
+#define BPF_ALU32_REG(OP, DST, SRC) \
+ ((struct bpf_insn) { \
+ .code = BPF_ALU | BPF_OP(OP) | BPF_X, \
+ .dst_reg = DST, \
+ .src_reg = SRC, \
+ .off = 0, \
+ .imm = 0 })
+
+/* ALU ops on immediates, bpf_add|sub|...: dst_reg += imm32 */
+
+#define BPF_ALU64_IMM(OP, DST, IMM) \
+ ((struct bpf_insn) { \
+ .code = BPF_ALU64 | BPF_OP(OP) | BPF_K, \
+ .dst_reg = DST, \
+ .src_reg = 0, \
+ .off = 0, \
+ .imm = IMM })
+
+#define BPF_ALU32_IMM(OP, DST, IMM) \
+ ((struct bpf_insn) { \
+ .code = BPF_ALU | BPF_OP(OP) | BPF_K, \
+ .dst_reg = DST, \
+ .src_reg = 0, \
+ .off = 0, \
+ .imm = IMM })
+
+/* Endianess conversion, cpu_to_{l,b}e(), {l,b}e_to_cpu() */
+
+#define BPF_ENDIAN(TYPE, DST, LEN) \
+ ((struct bpf_insn) { \
+ .code = BPF_ALU | BPF_END | BPF_SRC(TYPE), \
+ .dst_reg = DST, \
+ .src_reg = 0, \
+ .off = 0, \
+ .imm = LEN })
+
+/* Short form of mov, dst_reg = src_reg */
+
+#define BPF_MOV64_REG(DST, SRC) \
+ ((struct bpf_insn) { \
+ .code = BPF_ALU64 | BPF_MOV | BPF_X, \
+ .dst_reg = DST, \
+ .src_reg = SRC, \
+ .off = 0, \
+ .imm = 0 })
+
+#define BPF_MOV32_REG(DST, SRC) \
+ ((struct bpf_insn) { \
+ .code = BPF_ALU | BPF_MOV | BPF_X, \
+ .dst_reg = DST, \
+ .src_reg = SRC, \
+ .off = 0, \
+ .imm = 0 })
+
+/* Short form of mov, dst_reg = imm32 */
+
+#define BPF_MOV64_IMM(DST, IMM) \
+ ((struct bpf_insn) { \
+ .code = BPF_ALU64 | BPF_MOV | BPF_K, \
+ .dst_reg = DST, \
+ .src_reg = 0, \
+ .off = 0, \
+ .imm = IMM })
+
+#define BPF_MOV32_IMM(DST, IMM) \
+ ((struct bpf_insn) { \
+ .code = BPF_ALU | BPF_MOV | BPF_K, \
+ .dst_reg = DST, \
+ .src_reg = 0, \
+ .off = 0, \
+ .imm = IMM })
+
+/* BPF_LD_IMM64 macro encodes single 'load 64-bit immediate' insn */
+#define BPF_LD_IMM64(DST, IMM) \
+ BPF_LD_IMM64_RAW(DST, 0, IMM)
+
+#define BPF_LD_IMM64_RAW(DST, SRC, IMM) \
+ ((struct bpf_insn) { \
+ .code = BPF_LD | BPF_DW | BPF_IMM, \
+ .dst_reg = DST, \
+ .src_reg = SRC, \
+ .off = 0, \
+ .imm = (__u32) (IMM) }), \
+ ((struct bpf_insn) { \
+ .code = 0, /* zero is reserved opcode */ \
+ .dst_reg = 0, \
+ .src_reg = 0, \
+ .off = 0, \
+ .imm = ((__u64) (IMM)) >> 32 })
+
+/* Short form of mov based on type, BPF_X: dst_reg = src_reg, BPF_K: dst_reg = imm32 */
+
+#define BPF_MOV64_RAW(TYPE, DST, SRC, IMM) \
+ ((struct bpf_insn) { \
+ .code = BPF_ALU64 | BPF_MOV | BPF_SRC(TYPE), \
+ .dst_reg = DST, \
+ .src_reg = SRC, \
+ .off = 0, \
+ .imm = IMM })
+
+#define BPF_MOV32_RAW(TYPE, DST, SRC, IMM) \
+ ((struct bpf_insn) { \
+ .code = BPF_ALU | BPF_MOV | BPF_SRC(TYPE), \
+ .dst_reg = DST, \
+ .src_reg = SRC, \
+ .off = 0, \
+ .imm = IMM })
+
+/* Direct packet access, R0 = *(uint *) (skb->data + imm32) */
+
+#define BPF_LD_ABS(SIZE, IMM) \
+ ((struct bpf_insn) { \
+ .code = BPF_LD | BPF_SIZE(SIZE) | BPF_ABS, \
+ .dst_reg = 0, \
+ .src_reg = 0, \
+ .off = 0, \
+ .imm = IMM })
+
+/* Indirect packet access, R0 = *(uint *) (skb->data + src_reg + imm32) */
+
+#define BPF_LD_IND(SIZE, SRC, IMM) \
+ ((struct bpf_insn) { \
+ .code = BPF_LD | BPF_SIZE(SIZE) | BPF_IND, \
+ .dst_reg = 0, \
+ .src_reg = SRC, \
+ .off = 0, \
+ .imm = IMM })
+
+/* Memory load, dst_reg = *(uint *) (src_reg + off16) */
+
+#define BPF_LDX_MEM(SIZE, DST, SRC, OFF) \
+ ((struct bpf_insn) { \
+ .code = BPF_LDX | BPF_SIZE(SIZE) | BPF_MEM, \
+ .dst_reg = DST, \
+ .src_reg = SRC, \
+ .off = OFF, \
+ .imm = 0 })
+
+/* Memory store, *(uint *) (dst_reg + off16) = src_reg */
+
+#define BPF_STX_MEM(SIZE, DST, SRC, OFF) \
+ ((struct bpf_insn) { \
+ .code = BPF_STX | BPF_SIZE(SIZE) | BPF_MEM, \
+ .dst_reg = DST, \
+ .src_reg = SRC, \
+ .off = OFF, \
+ .imm = 0 })
+
+/* Memory store, *(uint *) (dst_reg + off16) = imm32 */
+
+#define BPF_ST_MEM(SIZE, DST, OFF, IMM) \
+ ((struct bpf_insn) { \
+ .code = BPF_ST | BPF_SIZE(SIZE) | BPF_MEM, \
+ .dst_reg = DST, \
+ .src_reg = 0, \
+ .off = OFF, \
+ .imm = IMM })
+
+/* Conditional jumps against registers, if (dst_reg 'op' src_reg) goto pc + off16 */
+
+#define BPF_JMP_REG(OP, DST, SRC, OFF) \
+ ((struct bpf_insn) { \
+ .code = BPF_JMP | BPF_OP(OP) | BPF_X, \
+ .dst_reg = DST, \
+ .src_reg = SRC, \
+ .off = OFF, \
+ .imm = 0 })
+
+/* Conditional jumps against immediates, if (dst_reg 'op' imm32) goto pc + off16 */
+
+#define BPF_JMP_IMM(OP, DST, IMM, OFF) \
+ ((struct bpf_insn) { \
+ .code = BPF_JMP | BPF_OP(OP) | BPF_K, \
+ .dst_reg = DST, \
+ .src_reg = 0, \
+ .off = OFF, \
+ .imm = IMM })
+
+/* Function call */
+
+#define BPF_EMIT_CALL(FUNC) \
+ ((struct bpf_insn) { \
+ .code = BPF_JMP | BPF_CALL, \
+ .dst_reg = 0, \
+ .src_reg = 0, \
+ .off = 0, \
+ .imm = ((FUNC) - __bpf_call_base) })
+
+/* Raw code statement block */
+
+#define BPF_RAW_INSN(CODE, DST, SRC, OFF, IMM) \
+ ((struct bpf_insn) { \
+ .code = CODE, \
+ .dst_reg = DST, \
+ .src_reg = SRC, \
+ .off = OFF, \
+ .imm = IMM })
+
+/* Program exit */
+
+#define BPF_EXIT_INSN() \
+ ((struct bpf_insn) { \
+ .code = BPF_JMP | BPF_EXIT, \
+ .dst_reg = 0, \
+ .src_reg = 0, \
+ .off = 0, \
+ .imm = 0 })
+
+#define bytes_to_bpf_size(bytes) \
+({ \
+ int bpf_size = -EINVAL; \
+ \
+ if (bytes == sizeof(u8)) \
+ bpf_size = BPF_B; \
+ else if (bytes == sizeof(u16)) \
+ bpf_size = BPF_H; \
+ else if (bytes == sizeof(u32)) \
+ bpf_size = BPF_W; \
+ else if (bytes == sizeof(u64)) \
+ bpf_size = BPF_DW; \
+ \
+ bpf_size; \
+})
+
+struct bpf_insn {
+ __u8 code; /* opcode */
+ __u8 dst_reg:4; /* dest register */
+ __u8 src_reg:4; /* source register */
+ __s16 off; /* signed offset */
+ __s32 imm; /* signed immediate constant */
+};
+
+#endif /* _UAPI__LINUX_BPF_H__ */
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 04/29] bpf: introduce syscall(BPF, ...) and BPF maps
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api, netdev, linux-kernel
In-Reply-To: <1408911690-7598-1-git-send-email-ast@plumgrid.com>
BPF syscall is a demux for different BPF releated commands.
'maps' is a generic storage of different types for sharing data between kernel
and userspace.
The maps can be created from user space via BPF syscall:
- create a map with given type and attributes
fd = bpf_map_create(map_type, struct nlattr *attr, int len)
returns fd or negative error
- close(fd) deletes the map
Next patch allows userspace programs to populate/read maps that eBPF programs
are concurrently updating.
maps can have different types: hash, bloom filter, radix-tree, etc.
The map is defined by:
. type
. max number of elements
. key size in bytes
. value size in bytes
This patch establishes core infrastructure for BPF maps.
Next patches implement lookup/update and hashtable type.
More map types can be added in the future.
syscall is using type-length-value style of passing arguments to be backwards
compatible with future extensions to map attributes. Different map types may
use different attributes as well.
The concept of type-lenght-value is borrowed from netlink, but netlink itself
is not applicable here, since BPF programs and maps can be used in NET-less
configurations.
Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
---
Documentation/networking/filter.txt | 71 ++++++++++++++++
include/linux/bpf.h | 42 ++++++++++
include/uapi/linux/bpf.h | 24 ++++++
kernel/bpf/Makefile | 2 +-
kernel/bpf/syscall.c | 156 +++++++++++++++++++++++++++++++++++
5 files changed, 294 insertions(+), 1 deletion(-)
create mode 100644 include/linux/bpf.h
create mode 100644 kernel/bpf/syscall.c
diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt
index 81916ab5d96f..27a0a6c6acb4 100644
--- a/Documentation/networking/filter.txt
+++ b/Documentation/networking/filter.txt
@@ -1001,6 +1001,77 @@ instruction that loads 64-bit immediate value into a dst_reg.
Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads
32-bit immediate value into a register.
+eBPF maps
+---------
+'maps' is a generic storage of different types for sharing data between kernel
+and userspace.
+
+The maps are accessed from user space via BPF syscall, which has commands:
+- create a map with given type and attributes
+ map_fd = bpf_map_create(map_type, struct nlattr *attr, int len)
+ returns process-local file descriptor or negative error
+
+- lookup key in a given map
+ err = bpf_map_lookup_elem(int fd, void *key, void *value)
+ returns zero and stores found elem into value or negative error
+
+- create or update key/value pair in a given map
+ err = bpf_map_update_elem(int fd, void *key, void *value)
+ returns zero or negative error
+
+- find and delete element by key in a given map
+ err = bpf_map_delete_elem(int fd, void *key)
+
+- to delete map: close(fd)
+ Exiting process will delete maps automatically
+
+userspace programs uses this API to create/populate/read maps that eBPF programs
+are concurrently updating.
+
+maps can have different types: hash, array, bloom filter, radix-tree, etc.
+
+The map is defined by:
+ . type
+ . max number of elements
+ . key size in bytes
+ . value size in bytes
+
+The maps are accesible from eBPF program with API:
+ void * bpf_map_lookup_elem(u32 map_fd, void *key);
+ int bpf_map_update_elem(u32 map_fd, void *key, void *value);
+ int bpf_map_delete_elem(u32 map_fd, void *key);
+
+The kernel replaces process-local map_fd with kernel internal map pointer,
+while loading eBPF program.
+
+If eBPF verifier is configured to recognize extra calls in the program
+bpf_map_lookup_elem() and bpf_map_update_elem() then access to maps looks like:
+ ...
+ ptr_to_value = bpf_map_lookup_elem(map_fd, key)
+ access memory range [ptr_to_value, ptr_to_value + value_size_in_bytes)
+ ...
+ prepare key2 and value2 on stack of key_size and value_size
+ err = bpf_map_update_elem(map_fd, key2, value2)
+ ...
+
+eBPF program cannot create or delete maps
+(such calls will be unknown to verifier)
+
+During program loading the refcnt of used maps is incremented, so they don't get
+deleted while program is running
+
+bpf_map_update_elem() can fail if maximum number of elements reached.
+if key2 already exists, bpf_map_update_elem() replaces it with value2 atomically
+
+bpf_map_lookup_elem() returns NULL or ptr_to_value, so program must do
+if (ptr_to_value != NULL) check before accessing it.
+NULL means that element with given 'key' was not found.
+
+The verifier will check that the program accesses map elements within specified
+size. It will not let programs pass junk values to bpf_map_*_elem() functions,
+so these functions (implemented in C inside kernel) can safely access
+the pointers in all cases.
+
Testing
-------
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
new file mode 100644
index 000000000000..607ca53fe2af
--- /dev/null
+++ b/include/linux/bpf.h
@@ -0,0 +1,42 @@
+/* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General Public
+ * License as published by the Free Software Foundation.
+ */
+#ifndef _LINUX_BPF_H
+#define _LINUX_BPF_H 1
+
+#include <uapi/linux/bpf.h>
+#include <linux/workqueue.h>
+
+struct bpf_map;
+struct nlattr;
+
+/* map is generic key/value storage optionally accesible by eBPF programs */
+struct bpf_map_ops {
+ /* funcs callable from userspace (via syscall) */
+ struct bpf_map *(*map_alloc)(struct nlattr *attrs[BPF_MAP_ATTR_MAX + 1]);
+ void (*map_free)(struct bpf_map *);
+};
+
+struct bpf_map {
+ atomic_t refcnt;
+ enum bpf_map_type map_type;
+ u32 key_size;
+ u32 value_size;
+ u32 max_entries;
+ struct bpf_map_ops *ops;
+ struct work_struct work;
+};
+
+struct bpf_map_type_list {
+ struct list_head list_node;
+ struct bpf_map_ops *ops;
+ enum bpf_map_type type;
+};
+
+void bpf_register_map_type(struct bpf_map_type_list *tl);
+void bpf_map_put(struct bpf_map *map);
+
+#endif /* _LINUX_BPF_H */
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index 45a09b46c578..de21c8ecf0bb 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -318,4 +318,28 @@ struct bpf_insn {
__s32 imm; /* signed immediate constant */
};
+/* BPF syscall commands */
+enum bpf_cmd {
+ /* create a map with given type and attributes
+ * fd = bpf_map_create(bpf_map_type, struct nlattr *attr, int len)
+ * returns fd or negative error
+ * map is deleted when fd is closed
+ */
+ BPF_MAP_CREATE,
+};
+
+enum bpf_map_attributes {
+ BPF_MAP_UNSPEC,
+ BPF_MAP_KEY_SIZE, /* size of key in bytes */
+ BPF_MAP_VALUE_SIZE, /* size of value in bytes */
+ BPF_MAP_MAX_ENTRIES, /* maximum number of entries in a map */
+ __BPF_MAP_ATTR_MAX,
+};
+#define BPF_MAP_ATTR_MAX (__BPF_MAP_ATTR_MAX - 1)
+#define BPF_MAP_MAX_ATTR_SIZE 65535
+
+enum bpf_map_type {
+ BPF_MAP_TYPE_UNSPEC,
+};
+
#endif /* _UAPI__LINUX_BPF_H__ */
diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
index 6a71145e2769..e9f7334ed07a 100644
--- a/kernel/bpf/Makefile
+++ b/kernel/bpf/Makefile
@@ -1 +1 @@
-obj-y := core.o
+obj-y := core.o syscall.o
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
new file mode 100644
index 000000000000..04cdf7948f8f
--- /dev/null
+++ b/kernel/bpf/syscall.c
@@ -0,0 +1,156 @@
+/* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General Public
+ * License as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ */
+#include <linux/bpf.h>
+#include <linux/syscalls.h>
+#include <net/netlink.h>
+#include <linux/anon_inodes.h>
+
+static LIST_HEAD(bpf_map_types);
+
+static struct bpf_map *find_and_alloc_map(enum bpf_map_type type,
+ struct nlattr *tb[BPF_MAP_ATTR_MAX + 1])
+{
+ struct bpf_map_type_list *tl;
+ struct bpf_map *map;
+
+ list_for_each_entry(tl, &bpf_map_types, list_node) {
+ if (tl->type == type) {
+ map = tl->ops->map_alloc(tb);
+ if (IS_ERR(map))
+ return map;
+ map->ops = tl->ops;
+ map->map_type = type;
+ return map;
+ }
+ }
+ return ERR_PTR(-EINVAL);
+}
+
+/* boot time registration of different map implementations */
+void bpf_register_map_type(struct bpf_map_type_list *tl)
+{
+ list_add(&tl->list_node, &bpf_map_types);
+}
+
+/* called from workqueue */
+static void bpf_map_free_deferred(struct work_struct *work)
+{
+ struct bpf_map *map = container_of(work, struct bpf_map, work);
+
+ /* implementation dependent freeing */
+ map->ops->map_free(map);
+}
+
+/* decrement map refcnt and schedule it for freeing via workqueue
+ * (unrelying map implementation ops->map_free() might sleep)
+ */
+void bpf_map_put(struct bpf_map *map)
+{
+ if (atomic_dec_and_test(&map->refcnt)) {
+ INIT_WORK(&map->work, bpf_map_free_deferred);
+ schedule_work(&map->work);
+ }
+}
+
+static int bpf_map_release(struct inode *inode, struct file *filp)
+{
+ struct bpf_map *map = filp->private_data;
+
+ bpf_map_put(map);
+ return 0;
+}
+
+static const struct file_operations bpf_map_fops = {
+ .release = bpf_map_release,
+};
+
+static const struct nla_policy map_policy[BPF_MAP_ATTR_MAX + 1] = {
+ [BPF_MAP_KEY_SIZE] = { .type = NLA_U32 },
+ [BPF_MAP_VALUE_SIZE] = { .type = NLA_U32 },
+ [BPF_MAP_MAX_ENTRIES] = { .type = NLA_U32 },
+};
+
+/* called via syscall */
+static int map_create(enum bpf_map_type type, struct nlattr __user *uattr, int len)
+{
+ struct nlattr *tb[BPF_MAP_ATTR_MAX + 1];
+ struct bpf_map *map;
+ struct nlattr *attr;
+ int err;
+
+ if (len <= 0 || len > BPF_MAP_MAX_ATTR_SIZE)
+ return -EINVAL;
+
+ attr = kmalloc(len, GFP_USER);
+ if (!attr)
+ return -ENOMEM;
+
+ /* copy map attributes from user space */
+ err = -EFAULT;
+ if (copy_from_user(attr, uattr, len) != 0)
+ goto free_attr;
+
+ /* perform basic validation */
+ err = nla_parse(tb, BPF_MAP_ATTR_MAX, attr, len, map_policy);
+ if (err < 0)
+ goto free_attr;
+
+ /* find map type and init map: hashtable vs rbtree vs bloom vs ... */
+ map = find_and_alloc_map(type, tb);
+ if (IS_ERR(map)) {
+ err = PTR_ERR(map);
+ goto free_attr;
+ }
+
+ atomic_set(&map->refcnt, 1);
+
+ err = anon_inode_getfd("bpf-map", &bpf_map_fops, map, O_RDWR | O_CLOEXEC);
+
+ if (err < 0)
+ /* failed to allocate fd */
+ goto free_map;
+
+ /* user supplied array of map attributes is no longer needed */
+ kfree(attr);
+
+ return err;
+
+free_map:
+ map->ops->map_free(map);
+free_attr:
+ kfree(attr);
+ return err;
+}
+
+SYSCALL_DEFINE5(bpf, int, cmd, unsigned long, arg2, unsigned long, arg3,
+ unsigned long, arg4, unsigned long, arg5)
+{
+ /* eBPF syscall is limited to root temporarily. This restriction will
+ * be lifted when verifier has enough mileage and security audit is
+ * clean. Note that tracing/networking analytics use cases will be
+ * turning off 'secure' mode of verifier, since they need to pass
+ * kernel data back to user space
+ */
+ if (!capable(CAP_SYS_ADMIN))
+ return -EPERM;
+
+ if (arg5 != 0)
+ return -EINVAL;
+
+ switch (cmd) {
+ case BPF_MAP_CREATE:
+ return map_create((enum bpf_map_type) arg2,
+ (struct nlattr __user *) arg3, (int) arg4);
+ default:
+ return -EINVAL;
+ }
+}
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 05/29] bpf: enable bpf syscall on x64 and i386
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api-u79uwXL29TY76Z2rM5mHXA,
netdev-u79uwXL29TY76Z2rM5mHXA,
linux-kernel-u79uwXL29TY76Z2rM5mHXA
In-Reply-To: <1408911690-7598-1-git-send-email-ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org>
done as separate commit to ease conflict resolution
Signed-off-by: Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org>
---
arch/x86/syscalls/syscall_32.tbl | 1 +
arch/x86/syscalls/syscall_64.tbl | 1 +
include/linux/syscalls.h | 3 ++-
include/uapi/asm-generic/unistd.h | 4 +++-
kernel/sys_ni.c | 3 +++
5 files changed, 10 insertions(+), 2 deletions(-)
diff --git a/arch/x86/syscalls/syscall_32.tbl b/arch/x86/syscalls/syscall_32.tbl
index 028b78168d85..9fe1b5d002f0 100644
--- a/arch/x86/syscalls/syscall_32.tbl
+++ b/arch/x86/syscalls/syscall_32.tbl
@@ -363,3 +363,4 @@
354 i386 seccomp sys_seccomp
355 i386 getrandom sys_getrandom
356 i386 memfd_create sys_memfd_create
+357 i386 bpf sys_bpf
diff --git a/arch/x86/syscalls/syscall_64.tbl b/arch/x86/syscalls/syscall_64.tbl
index 35dd922727b9..281150b539a2 100644
--- a/arch/x86/syscalls/syscall_64.tbl
+++ b/arch/x86/syscalls/syscall_64.tbl
@@ -327,6 +327,7 @@
318 common getrandom sys_getrandom
319 common memfd_create sys_memfd_create
320 common kexec_file_load sys_kexec_file_load
+321 common bpf sys_bpf
#
# x32-specific system call numbers start at 512 to avoid cache impact
diff --git a/include/linux/syscalls.h b/include/linux/syscalls.h
index 0f86d85a9ce4..61bc112b9fa5 100644
--- a/include/linux/syscalls.h
+++ b/include/linux/syscalls.h
@@ -875,5 +875,6 @@ asmlinkage long sys_seccomp(unsigned int op, unsigned int flags,
const char __user *uargs);
asmlinkage long sys_getrandom(char __user *buf, size_t count,
unsigned int flags);
-
+asmlinkage long sys_bpf(int cmd, unsigned long arg2, unsigned long arg3,
+ unsigned long arg4, unsigned long arg5);
#endif
diff --git a/include/uapi/asm-generic/unistd.h b/include/uapi/asm-generic/unistd.h
index 11d11bc5c78f..22749c134117 100644
--- a/include/uapi/asm-generic/unistd.h
+++ b/include/uapi/asm-generic/unistd.h
@@ -705,9 +705,11 @@ __SYSCALL(__NR_seccomp, sys_seccomp)
__SYSCALL(__NR_getrandom, sys_getrandom)
#define __NR_memfd_create 279
__SYSCALL(__NR_memfd_create, sys_memfd_create)
+#define __NR_bpf 280
+__SYSCALL(__NR_bpf, sys_bpf)
#undef __NR_syscalls
-#define __NR_syscalls 280
+#define __NR_syscalls 281
/*
* All syscalls below here should go away really,
diff --git a/kernel/sys_ni.c b/kernel/sys_ni.c
index 391d4ddb6f4b..b4b5083f5f5e 100644
--- a/kernel/sys_ni.c
+++ b/kernel/sys_ni.c
@@ -218,3 +218,6 @@ cond_syscall(sys_kcmp);
/* operate on Secure Computing state */
cond_syscall(sys_seccomp);
+
+/* access BPF programs and maps */
+cond_syscall(sys_bpf);
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 06/29] bpf: add lookup/update/delete/iterate methods to BPF maps
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api-u79uwXL29TY76Z2rM5mHXA,
netdev-u79uwXL29TY76Z2rM5mHXA,
linux-kernel-u79uwXL29TY76Z2rM5mHXA
In-Reply-To: <1408911690-7598-1-git-send-email-ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org>
'maps' is a generic storage of different types for sharing data between kernel
and userspace.
The maps are accessed from user space via BPF syscall, which has commands:
- create a map with given type and attributes
fd = bpf_map_create(map_type, struct nlattr *attr, int len)
returns fd or negative error
- lookup key in a given map referenced by fd
err = bpf_map_lookup_elem(int fd, void *key, void *value)
returns zero and stores found elem into value or negative error
- create or update key/value pair in a given map
err = bpf_map_update_elem(int fd, void *key, void *value)
returns zero or negative error
- find and delete element by key in a given map
err = bpf_map_delete_elem(int fd, void *key)
- iterate map elements (based on input key return next_key)
err = bpf_map_get_next_key(int fd, void *key, void *next_key)
- close(fd) deletes the map
Signed-off-by: Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org>
---
include/linux/bpf.h | 8 ++
include/uapi/linux/bpf.h | 25 ++++++
kernel/bpf/syscall.c | 198 ++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 231 insertions(+)
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 607ca53fe2af..fd1ac4b5ba8b 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -9,6 +9,7 @@
#include <uapi/linux/bpf.h>
#include <linux/workqueue.h>
+#include <linux/file.h>
struct bpf_map;
struct nlattr;
@@ -18,6 +19,12 @@ struct bpf_map_ops {
/* funcs callable from userspace (via syscall) */
struct bpf_map *(*map_alloc)(struct nlattr *attrs[BPF_MAP_ATTR_MAX + 1]);
void (*map_free)(struct bpf_map *);
+ int (*map_get_next_key)(struct bpf_map *map, void *key, void *next_key);
+
+ /* funcs callable from userspace and from eBPF programs */
+ void *(*map_lookup_elem)(struct bpf_map *map, void *key);
+ int (*map_update_elem)(struct bpf_map *map, void *key, void *value);
+ int (*map_delete_elem)(struct bpf_map *map, void *key);
};
struct bpf_map {
@@ -38,5 +45,6 @@ struct bpf_map_type_list {
void bpf_register_map_type(struct bpf_map_type_list *tl);
void bpf_map_put(struct bpf_map *map);
+struct bpf_map *bpf_map_get(struct fd f);
#endif /* _LINUX_BPF_H */
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index de21c8ecf0bb..f68edb2681f8 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -326,6 +326,31 @@ enum bpf_cmd {
* map is deleted when fd is closed
*/
BPF_MAP_CREATE,
+
+ /* lookup key in a given map
+ * err = bpf_map_lookup_elem(int fd, void *key, void *value)
+ * returns zero and stores found elem into value
+ * or negative error
+ */
+ BPF_MAP_LOOKUP_ELEM,
+
+ /* create or update key/value pair in a given map
+ * err = bpf_map_update_elem(int fd, void *key, void *value)
+ * returns zero or negative error
+ */
+ BPF_MAP_UPDATE_ELEM,
+
+ /* find and delete elem by key in a given map
+ * err = bpf_map_delete_elem(int fd, void *key)
+ * returns zero or negative error
+ */
+ BPF_MAP_DELETE_ELEM,
+
+ /* lookup key in a given map and return next key
+ * err = bpf_map_get_elem(int fd, void *key, void *next_key)
+ * returns zero and stores next key or negative error
+ */
+ BPF_MAP_GET_NEXT_KEY,
};
enum bpf_map_attributes {
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index 04cdf7948f8f..45e100ece1b7 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -13,6 +13,7 @@
#include <linux/syscalls.h>
#include <net/netlink.h>
#include <linux/anon_inodes.h>
+#include <linux/file.h>
static LIST_HEAD(bpf_map_types);
@@ -131,6 +132,189 @@ free_attr:
return err;
}
+/* if error is returned, fd is released.
+ * On success caller should complete fd access with matching fdput()
+ */
+struct bpf_map *bpf_map_get(struct fd f)
+{
+ struct bpf_map *map;
+
+ if (!f.file)
+ return ERR_PTR(-EBADF);
+
+ if (f.file->f_op != &bpf_map_fops) {
+ fdput(f);
+ return ERR_PTR(-EINVAL);
+ }
+
+ map = f.file->private_data;
+
+ return map;
+}
+
+static int map_lookup_elem(int ufd, void __user *ukey, void __user *uvalue)
+{
+ struct fd f = fdget(ufd);
+ struct bpf_map *map;
+ void *key, *value;
+ int err;
+
+ map = bpf_map_get(f);
+ if (IS_ERR(map))
+ return PTR_ERR(map);
+
+ err = -ENOMEM;
+ key = kmalloc(map->key_size, GFP_USER);
+ if (!key)
+ goto err_put;
+
+ err = -EFAULT;
+ if (copy_from_user(key, ukey, map->key_size) != 0)
+ goto free_key;
+
+ err = -ESRCH;
+ rcu_read_lock();
+ value = map->ops->map_lookup_elem(map, key);
+ if (!value)
+ goto err_unlock;
+
+ err = -EFAULT;
+ if (copy_to_user(uvalue, value, map->value_size) != 0)
+ goto err_unlock;
+
+ err = 0;
+
+err_unlock:
+ rcu_read_unlock();
+free_key:
+ kfree(key);
+err_put:
+ fdput(f);
+ return err;
+}
+
+static int map_update_elem(int ufd, void __user *ukey, void __user *uvalue)
+{
+ struct fd f = fdget(ufd);
+ struct bpf_map *map;
+ void *key, *value;
+ int err;
+
+ map = bpf_map_get(f);
+ if (IS_ERR(map))
+ return PTR_ERR(map);
+
+ err = -ENOMEM;
+ key = kmalloc(map->key_size, GFP_USER);
+ if (!key)
+ goto err_put;
+
+ err = -EFAULT;
+ if (copy_from_user(key, ukey, map->key_size) != 0)
+ goto free_key;
+
+ err = -ENOMEM;
+ value = kmalloc(map->value_size, GFP_USER);
+ if (!value)
+ goto free_key;
+
+ err = -EFAULT;
+ if (copy_from_user(value, uvalue, map->value_size) != 0)
+ goto free_value;
+
+ /* eBPF program that use maps are running under rcu_read_lock(),
+ * therefore all map accessors rely on this fact, so do the same here
+ */
+ rcu_read_lock();
+ err = map->ops->map_update_elem(map, key, value);
+ rcu_read_unlock();
+
+free_value:
+ kfree(value);
+free_key:
+ kfree(key);
+err_put:
+ fdput(f);
+ return err;
+}
+
+static int map_delete_elem(int ufd, void __user *ukey)
+{
+ struct fd f = fdget(ufd);
+ struct bpf_map *map;
+ void *key;
+ int err;
+
+ map = bpf_map_get(f);
+ if (IS_ERR(map))
+ return PTR_ERR(map);
+
+ err = -ENOMEM;
+ key = kmalloc(map->key_size, GFP_USER);
+ if (!key)
+ goto err_put;
+
+ err = -EFAULT;
+ if (copy_from_user(key, ukey, map->key_size) != 0)
+ goto free_key;
+
+ rcu_read_lock();
+ err = map->ops->map_delete_elem(map, key);
+ rcu_read_unlock();
+
+free_key:
+ kfree(key);
+err_put:
+ fdput(f);
+ return err;
+}
+
+static int map_get_next_key(int ufd, void __user *ukey, void __user *unext_key)
+{
+ struct fd f = fdget(ufd);
+ struct bpf_map *map;
+ void *key, *next_key;
+ int err;
+
+ map = bpf_map_get(f);
+ if (IS_ERR(map))
+ return PTR_ERR(map);
+
+ err = -ENOMEM;
+ key = kmalloc(map->key_size, GFP_USER);
+ if (!key)
+ goto err_put;
+
+ err = -EFAULT;
+ if (copy_from_user(key, ukey, map->key_size) != 0)
+ goto free_key;
+
+ err = -ENOMEM;
+ next_key = kmalloc(map->key_size, GFP_USER);
+ if (!next_key)
+ goto free_key;
+
+ rcu_read_lock();
+ err = map->ops->map_get_next_key(map, key, next_key);
+ rcu_read_unlock();
+ if (err)
+ goto free_next_key;
+
+ err = -EFAULT;
+ if (copy_to_user(unext_key, next_key, map->key_size) != 0)
+ goto free_next_key;
+
+ err = 0;
+
+free_next_key:
+ kfree(next_key);
+free_key:
+ kfree(key);
+err_put:
+ fdput(f);
+ return err;
+}
+
SYSCALL_DEFINE5(bpf, int, cmd, unsigned long, arg2, unsigned long, arg3,
unsigned long, arg4, unsigned long, arg5)
{
@@ -150,6 +334,20 @@ SYSCALL_DEFINE5(bpf, int, cmd, unsigned long, arg2, unsigned long, arg3,
case BPF_MAP_CREATE:
return map_create((enum bpf_map_type) arg2,
(struct nlattr __user *) arg3, (int) arg4);
+ case BPF_MAP_LOOKUP_ELEM:
+ return map_lookup_elem((int) arg2, (void __user *) arg3,
+ (void __user *) arg4);
+ case BPF_MAP_UPDATE_ELEM:
+ return map_update_elem((int) arg2, (void __user *) arg3,
+ (void __user *) arg4);
+ case BPF_MAP_DELETE_ELEM:
+ if (arg4 != 0)
+ return -EINVAL;
+ return map_delete_elem((int) arg2, (void __user *) arg3);
+
+ case BPF_MAP_GET_NEXT_KEY:
+ return map_get_next_key((int) arg2, (void __user *) arg3,
+ (void __user *) arg4);
default:
return -EINVAL;
}
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 07/29] bpf: add hashtable type of BPF maps
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api-u79uwXL29TY76Z2rM5mHXA,
netdev-u79uwXL29TY76Z2rM5mHXA,
linux-kernel-u79uwXL29TY76Z2rM5mHXA
In-Reply-To: <1408911690-7598-1-git-send-email-ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org>
add new map type: BPF_MAP_TYPE_HASH
and its simple (not auto resizeable) hash table implementation
Signed-off-by: Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org>
---
include/uapi/linux/bpf.h | 1 +
kernel/bpf/Makefile | 2 +-
kernel/bpf/hashtab.c | 372 ++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 374 insertions(+), 1 deletion(-)
create mode 100644 kernel/bpf/hashtab.c
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index f68edb2681f8..8069ab7b64cf 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -365,6 +365,7 @@ enum bpf_map_attributes {
enum bpf_map_type {
BPF_MAP_TYPE_UNSPEC,
+ BPF_MAP_TYPE_HASH,
};
#endif /* _UAPI__LINUX_BPF_H__ */
diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
index e9f7334ed07a..558e12712ebc 100644
--- a/kernel/bpf/Makefile
+++ b/kernel/bpf/Makefile
@@ -1 +1 @@
-obj-y := core.o syscall.o
+obj-y := core.o syscall.o hashtab.o
diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
new file mode 100644
index 000000000000..bc8d32f0f720
--- /dev/null
+++ b/kernel/bpf/hashtab.c
@@ -0,0 +1,372 @@
+/* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General Public
+ * License as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ */
+#include <linux/bpf.h>
+#include <net/netlink.h>
+#include <linux/jhash.h>
+
+struct bpf_htab {
+ struct bpf_map map;
+ struct hlist_head *buckets;
+ struct kmem_cache *elem_cache;
+ spinlock_t lock;
+ u32 count; /* number of elements in this hashtable */
+ u32 n_buckets; /* number of hash buckets */
+ u32 elem_size; /* size of each element in bytes */
+};
+
+/* each htab element is struct htab_elem + key + value */
+struct htab_elem {
+ struct hlist_node hash_node;
+ struct rcu_head rcu;
+ struct bpf_htab *htab;
+ u32 hash;
+ u32 pad;
+ char key[0];
+};
+
+#define HASH_MAX_BUCKETS 1024
+#define BPF_MAP_MAX_KEY_SIZE 256
+static struct bpf_map *htab_map_alloc(struct nlattr *attr[BPF_MAP_ATTR_MAX + 1])
+{
+ struct bpf_htab *htab;
+ int err, i;
+
+ htab = kzalloc(sizeof(*htab), GFP_USER);
+ if (!htab)
+ return ERR_PTR(-ENOMEM);
+
+ /* look for mandatory map attributes */
+ err = -EINVAL;
+ if (!attr[BPF_MAP_KEY_SIZE])
+ goto free_htab;
+ htab->map.key_size = nla_get_u32(attr[BPF_MAP_KEY_SIZE]);
+
+ if (!attr[BPF_MAP_VALUE_SIZE])
+ goto free_htab;
+ htab->map.value_size = nla_get_u32(attr[BPF_MAP_VALUE_SIZE]);
+
+ if (!attr[BPF_MAP_MAX_ENTRIES])
+ goto free_htab;
+ htab->map.max_entries = nla_get_u32(attr[BPF_MAP_MAX_ENTRIES]);
+
+ htab->n_buckets = (htab->map.max_entries <= HASH_MAX_BUCKETS) ?
+ htab->map.max_entries : HASH_MAX_BUCKETS;
+
+ /* hash table size must be power of 2 */
+ if ((htab->n_buckets & (htab->n_buckets - 1)) != 0)
+ goto free_htab;
+
+ err = -E2BIG;
+ if (htab->map.key_size > BPF_MAP_MAX_KEY_SIZE)
+ goto free_htab;
+
+ err = -ENOMEM;
+ htab->buckets = kmalloc_array(htab->n_buckets,
+ sizeof(struct hlist_head), GFP_USER);
+
+ if (!htab->buckets)
+ goto free_htab;
+
+ for (i = 0; i < htab->n_buckets; i++)
+ INIT_HLIST_HEAD(&htab->buckets[i]);
+
+ spin_lock_init(&htab->lock);
+ htab->count = 0;
+
+ htab->elem_size = sizeof(struct htab_elem) +
+ round_up(htab->map.key_size, 8) +
+ htab->map.value_size;
+
+ htab->elem_cache = kmem_cache_create("bpf_htab", htab->elem_size, 0, 0,
+ NULL);
+ if (!htab->elem_cache)
+ goto free_buckets;
+
+ return &htab->map;
+
+free_buckets:
+ kfree(htab->buckets);
+free_htab:
+ kfree(htab);
+ return ERR_PTR(err);
+}
+
+static inline u32 htab_map_hash(const void *key, u32 key_len)
+{
+ return jhash(key, key_len, 0);
+}
+
+static inline struct hlist_head *select_bucket(struct bpf_htab *htab, u32 hash)
+{
+ return &htab->buckets[hash & (htab->n_buckets - 1)];
+}
+
+static struct htab_elem *lookup_elem_raw(struct hlist_head *head, u32 hash,
+ void *key, u32 key_size)
+{
+ struct htab_elem *l;
+
+ hlist_for_each_entry_rcu(l, head, hash_node) {
+ if (l->hash == hash && !memcmp(&l->key, key, key_size))
+ return l;
+ }
+ return NULL;
+}
+
+/* Must be called with rcu_read_lock. */
+static void *htab_map_lookup_elem(struct bpf_map *map, void *key)
+{
+ struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
+ struct hlist_head *head;
+ struct htab_elem *l;
+ u32 hash, key_size;
+
+ WARN_ON_ONCE(!rcu_read_lock_held());
+
+ key_size = map->key_size;
+
+ hash = htab_map_hash(key, key_size);
+
+ head = select_bucket(htab, hash);
+
+ l = lookup_elem_raw(head, hash, key, key_size);
+
+ if (l)
+ return l->key + round_up(map->key_size, 8);
+ else
+ return NULL;
+}
+
+/* Must be called with rcu_read_lock. */
+static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
+{
+ struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
+ struct hlist_head *head;
+ struct htab_elem *l, *next_l;
+ u32 hash, key_size;
+ int i;
+
+ WARN_ON_ONCE(!rcu_read_lock_held());
+
+ key_size = map->key_size;
+
+ hash = htab_map_hash(key, key_size);
+
+ head = select_bucket(htab, hash);
+
+ /* lookup the key */
+ l = lookup_elem_raw(head, hash, key, key_size);
+
+ if (!l) {
+ i = 0;
+ goto find_first_elem;
+ }
+
+ /* key was found, get next key in the same bucket */
+ next_l = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(&l->hash_node)),
+ struct htab_elem, hash_node);
+
+ if (next_l) {
+ /* if next elem in this hash list is non-zero, just return it */
+ memcpy(next_key, next_l->key, key_size);
+ return 0;
+ } else {
+ /* no more elements in this hash list, go to the next bucket */
+ i = hash & (htab->n_buckets - 1);
+ i++;
+ }
+
+find_first_elem:
+ /* iterate over buckets */
+ for (; i < htab->n_buckets; i++) {
+ head = select_bucket(htab, i);
+
+ /* pick first element in the bucket */
+ next_l = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),
+ struct htab_elem, hash_node);
+ if (next_l) {
+ /* if it's not empty, just return it */
+ memcpy(next_key, next_l->key, key_size);
+ return 0;
+ }
+ }
+
+ /* itereated over all buckets and all elements */
+ return -ENOENT;
+}
+
+static struct htab_elem *htab_alloc_elem(struct bpf_htab *htab)
+{
+ void *l;
+
+ l = kmem_cache_alloc(htab->elem_cache, GFP_ATOMIC);
+ if (!l)
+ return ERR_PTR(-ENOMEM);
+ return l;
+}
+
+static void free_htab_elem_rcu(struct rcu_head *rcu)
+{
+ struct htab_elem *l = container_of(rcu, struct htab_elem, rcu);
+
+ kmem_cache_free(l->htab->elem_cache, l);
+}
+
+static void release_htab_elem(struct bpf_htab *htab, struct htab_elem *l)
+{
+ l->htab = htab;
+ call_rcu(&l->rcu, free_htab_elem_rcu);
+}
+
+/* Must be called with rcu_read_lock. */
+static int htab_map_update_elem(struct bpf_map *map, void *key, void *value)
+{
+ struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
+ struct htab_elem *l_new, *l_old;
+ struct hlist_head *head;
+ unsigned long flags;
+ u32 key_size;
+
+ WARN_ON_ONCE(!rcu_read_lock_held());
+
+ l_new = htab_alloc_elem(htab);
+ if (IS_ERR(l_new))
+ return -ENOMEM;
+
+ key_size = map->key_size;
+
+ memcpy(l_new->key, key, key_size);
+ memcpy(l_new->key + round_up(key_size, 8), value, map->value_size);
+
+ l_new->hash = htab_map_hash(l_new->key, key_size);
+
+ /* bpf_map_update_elem() can be called in_irq() as well, so
+ * spin_lock() or spin_lock_bh() cannot be used
+ */
+ spin_lock_irqsave(&htab->lock, flags);
+
+ head = select_bucket(htab, l_new->hash);
+
+ l_old = lookup_elem_raw(head, l_new->hash, key, key_size);
+
+ if (!l_old && unlikely(htab->count >= map->max_entries)) {
+ /* if elem with this 'key' doesn't exist and we've reached
+ * max_entries limit, fail insertion of new elem
+ */
+ spin_unlock_irqrestore(&htab->lock, flags);
+ kmem_cache_free(htab->elem_cache, l_new);
+ return -EFBIG;
+ }
+
+ /* add new element to the head of the list, so that concurrent
+ * search will find it before old elem
+ */
+ hlist_add_head_rcu(&l_new->hash_node, head);
+ if (l_old) {
+ hlist_del_rcu(&l_old->hash_node);
+ release_htab_elem(htab, l_old);
+ } else {
+ htab->count++;
+ }
+ spin_unlock_irqrestore(&htab->lock, flags);
+
+ return 0;
+}
+
+/* Must be called with rcu_read_lock. */
+static int htab_map_delete_elem(struct bpf_map *map, void *key)
+{
+ struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
+ struct hlist_head *head;
+ struct htab_elem *l;
+ unsigned long flags;
+ u32 hash, key_size;
+ int ret = -ESRCH;
+
+ WARN_ON_ONCE(!rcu_read_lock_held());
+
+ key_size = map->key_size;
+
+ hash = htab_map_hash(key, key_size);
+
+ spin_lock_irqsave(&htab->lock, flags);
+
+ head = select_bucket(htab, hash);
+
+ l = lookup_elem_raw(head, hash, key, key_size);
+
+ if (l) {
+ hlist_del_rcu(&l->hash_node);
+ htab->count--;
+ release_htab_elem(htab, l);
+ ret = 0;
+ }
+
+ spin_unlock_irqrestore(&htab->lock, flags);
+ return ret;
+}
+
+static void delete_all_elements(struct bpf_htab *htab)
+{
+ int i;
+
+ for (i = 0; i < htab->n_buckets; i++) {
+ struct hlist_head *head = select_bucket(htab, i);
+ struct hlist_node *n;
+ struct htab_elem *l;
+
+ hlist_for_each_entry_safe(l, n, head, hash_node) {
+ hlist_del_rcu(&l->hash_node);
+ htab->count--;
+ kmem_cache_free(htab->elem_cache, l);
+ }
+ }
+}
+
+/* called when map->refcnt goes to zero */
+static void htab_map_free(struct bpf_map *map)
+{
+ struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
+
+ /* wait for all outstanding updates to complete */
+ synchronize_rcu();
+
+ /* kmem_cache_free all htab elements */
+ delete_all_elements(htab);
+
+ /* and destroy cache, which might sleep */
+ kmem_cache_destroy(htab->elem_cache);
+
+ kfree(htab->buckets);
+ kfree(htab);
+}
+
+static struct bpf_map_ops htab_ops = {
+ .map_alloc = htab_map_alloc,
+ .map_free = htab_map_free,
+ .map_get_next_key = htab_map_get_next_key,
+ .map_lookup_elem = htab_map_lookup_elem,
+ .map_update_elem = htab_map_update_elem,
+ .map_delete_elem = htab_map_delete_elem,
+};
+
+static struct bpf_map_type_list tl = {
+ .ops = &htab_ops,
+ .type = BPF_MAP_TYPE_HASH,
+};
+
+static int __init register_htab_map(void)
+{
+ bpf_register_map_type(&tl);
+ return 0;
+}
+late_initcall(register_htab_map);
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 08/29] bpf: expand BPF syscall with program load/unload
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api-u79uwXL29TY76Z2rM5mHXA,
netdev-u79uwXL29TY76Z2rM5mHXA,
linux-kernel-u79uwXL29TY76Z2rM5mHXA
In-Reply-To: <1408911690-7598-1-git-send-email-ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org>
eBPF programs are safe run-to-completion functions with load/unload
methods from userspace similar to kernel modules.
User space API:
- load eBPF program
fd = bpf_prog_load(bpf_prog_type, struct nlattr *prog, int len)
where 'prog' is a sequence of sections (TEXT, LICENSE)
TEXT - array of eBPF instructions
LICENSE - must be GPL compatible to call helper functions marked gpl_only
- unload eBPF program
close(fd)
User space example of syscall(__NR_bpf, BPF_PROG_LOAD, prog_type, ...)
follows in later patches
Signed-off-by: Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org>
---
include/linux/bpf.h | 36 +++++++++
include/linux/filter.h | 9 ++-
include/uapi/linux/bpf.h | 28 +++++++
kernel/bpf/syscall.c | 196 ++++++++++++++++++++++++++++++++++++++++++++++
net/core/filter.c | 2 +
5 files changed, 269 insertions(+), 2 deletions(-)
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index fd1ac4b5ba8b..ac6320f44812 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -47,4 +47,40 @@ void bpf_register_map_type(struct bpf_map_type_list *tl);
void bpf_map_put(struct bpf_map *map);
struct bpf_map *bpf_map_get(struct fd f);
+/* eBPF function prototype used by verifier to allow BPF_CALLs from eBPF programs
+ * to in-kernel helper functions and for adjusting imm32 field in BPF_CALL
+ * instructions after verifying
+ */
+struct bpf_func_proto {
+ u64 (*func)(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5);
+ bool gpl_only;
+};
+
+struct bpf_verifier_ops {
+ /* return eBPF function prototype for verification */
+ const struct bpf_func_proto *(*get_func_proto)(enum bpf_func_id func_id);
+};
+
+struct bpf_prog_type_list {
+ struct list_head list_node;
+ struct bpf_verifier_ops *ops;
+ enum bpf_prog_type type;
+};
+
+void bpf_register_prog_type(struct bpf_prog_type_list *tl);
+
+struct bpf_prog_info {
+ atomic_t refcnt;
+ bool is_gpl_compatible;
+ enum bpf_prog_type prog_type;
+ struct bpf_verifier_ops *ops;
+ struct bpf_map **used_maps;
+ u32 used_map_cnt;
+};
+
+struct bpf_prog;
+
+void bpf_prog_put(struct bpf_prog *prog);
+struct bpf_prog *bpf_prog_get(u32 ufd);
+
#endif /* _LINUX_BPF_H */
diff --git a/include/linux/filter.h b/include/linux/filter.h
index f04793474d16..f06913b29861 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -31,11 +31,16 @@ struct sock_fprog_kern {
struct sk_buff;
struct sock;
struct seccomp_data;
+struct bpf_prog_info;
struct bpf_prog {
u32 jited:1, /* Is our filter JIT'ed? */
- len:31; /* Number of filter blocks */
- struct sock_fprog_kern *orig_prog; /* Original BPF program */
+ has_info:1, /* whether 'info' is valid */
+ len:30; /* Number of filter blocks */
+ union {
+ struct sock_fprog_kern *orig_prog; /* Original BPF program */
+ struct bpf_prog_info *info;
+ };
unsigned int (*bpf_func)(const struct sk_buff *skb,
const struct bpf_insn *filter);
union {
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index 8069ab7b64cf..7468fe55db7b 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -351,6 +351,13 @@ enum bpf_cmd {
* returns zero and stores next key or negative error
*/
BPF_MAP_GET_NEXT_KEY,
+
+ /* verify and load eBPF program
+ * prog_id = bpf_prog_load(bpf_prog_type, struct nlattr *prog, int len)
+ * prog is a sequence of sections
+ * returns fd or negative error
+ */
+ BPF_PROG_LOAD,
};
enum bpf_map_attributes {
@@ -368,4 +375,25 @@ enum bpf_map_type {
BPF_MAP_TYPE_HASH,
};
+enum bpf_prog_attributes {
+ BPF_PROG_UNSPEC,
+ BPF_PROG_TEXT, /* array of eBPF instructions */
+ BPF_PROG_LICENSE, /* license string */
+ __BPF_PROG_ATTR_MAX,
+};
+#define BPF_PROG_ATTR_MAX (__BPF_PROG_ATTR_MAX - 1)
+#define BPF_PROG_MAX_ATTR_SIZE 65535
+
+enum bpf_prog_type {
+ BPF_PROG_TYPE_UNSPEC,
+};
+
+/* integer value in 'imm' field of BPF_CALL instruction selects which helper
+ * function eBPF program intends to call
+ */
+enum bpf_func_id {
+ BPF_FUNC_unspec,
+ __BPF_FUNC_MAX_ID,
+};
+
#endif /* _UAPI__LINUX_BPF_H__ */
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index 45e100ece1b7..4c5f5169f6fc 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -14,6 +14,8 @@
#include <net/netlink.h>
#include <linux/anon_inodes.h>
#include <linux/file.h>
+#include <linux/license.h>
+#include <linux/filter.h>
static LIST_HEAD(bpf_map_types);
@@ -315,6 +317,197 @@ err_put:
return err;
}
+static LIST_HEAD(bpf_prog_types);
+
+static int find_prog_type(enum bpf_prog_type type, struct bpf_prog *prog)
+{
+ struct bpf_prog_type_list *tl;
+
+ list_for_each_entry(tl, &bpf_prog_types, list_node) {
+ if (tl->type == type) {
+ prog->info->ops = tl->ops;
+ prog->info->prog_type = type;
+ return 0;
+ }
+ }
+ return -EINVAL;
+}
+
+void bpf_register_prog_type(struct bpf_prog_type_list *tl)
+{
+ list_add(&tl->list_node, &bpf_prog_types);
+}
+
+/* drop refcnt on maps used by eBPF program and free auxilary data */
+static void free_bpf_prog_info(struct bpf_prog_info *info)
+{
+ int i;
+
+ for (i = 0; i < info->used_map_cnt; i++)
+ bpf_map_put(info->used_maps[i]);
+
+ kfree(info->used_maps);
+ kfree(info);
+}
+
+void bpf_prog_put(struct bpf_prog *prog)
+{
+ BUG_ON(!prog->has_info);
+ if (atomic_dec_and_test(&prog->info->refcnt)) {
+ free_bpf_prog_info(prog->info);
+ bpf_prog_free(prog);
+ }
+}
+
+static int bpf_prog_release(struct inode *inode, struct file *filp)
+{
+ struct bpf_prog *prog = filp->private_data;
+
+ bpf_prog_put(prog);
+ return 0;
+}
+
+static const struct file_operations bpf_prog_fops = {
+ .release = bpf_prog_release,
+};
+
+static struct bpf_prog *get_prog(struct fd f)
+{
+ struct bpf_prog *prog;
+
+ if (!f.file)
+ return ERR_PTR(-EBADF);
+
+ if (f.file->f_op != &bpf_prog_fops) {
+ fdput(f);
+ return ERR_PTR(-EINVAL);
+ }
+
+ prog = f.file->private_data;
+
+ return prog;
+}
+
+/* called by sockets/tracing/seccomp before attaching program to an event
+ * pairs with bpf_prog_put()
+ */
+struct bpf_prog *bpf_prog_get(u32 ufd)
+{
+ struct fd f = fdget(ufd);
+ struct bpf_prog *prog;
+
+ prog = get_prog(f);
+
+ if (IS_ERR(prog))
+ return prog;
+
+ atomic_inc(&prog->info->refcnt);
+ fdput(f);
+ return prog;
+}
+
+static const struct nla_policy prog_policy[BPF_PROG_ATTR_MAX + 1] = {
+ [BPF_PROG_TEXT] = { .type = NLA_BINARY },
+ [BPF_PROG_LICENSE] = { .type = NLA_NUL_STRING },
+};
+
+static int bpf_prog_load(enum bpf_prog_type type, struct nlattr __user *uattr,
+ int len)
+{
+ struct nlattr *tb[BPF_PROG_ATTR_MAX + 1];
+ struct bpf_prog *prog;
+ struct nlattr *attr;
+ size_t insn_len;
+ int err;
+ bool is_gpl;
+
+ if (len <= 0 || len > BPF_PROG_MAX_ATTR_SIZE)
+ return -EINVAL;
+
+ attr = kmalloc(len, GFP_USER);
+ if (!attr)
+ return -ENOMEM;
+
+ /* copy eBPF program from user space */
+ err = -EFAULT;
+ if (copy_from_user(attr, uattr, len) != 0)
+ goto free_attr;
+
+ /* perform basic validation */
+ err = nla_parse(tb, BPF_PROG_ATTR_MAX, attr, len, prog_policy);
+ if (err < 0)
+ goto free_attr;
+
+ err = -EINVAL;
+ /* look for mandatory license string */
+ if (!tb[BPF_PROG_LICENSE])
+ goto free_attr;
+
+ /* eBPF programs must be GPL compatible to use GPL-ed functions */
+ is_gpl = license_is_gpl_compatible(nla_data(tb[BPF_PROG_LICENSE]));
+
+ /* look for mandatory array of eBPF instructions */
+ if (!tb[BPF_PROG_TEXT])
+ goto free_attr;
+
+ insn_len = nla_len(tb[BPF_PROG_TEXT]);
+ if (insn_len % sizeof(struct bpf_insn) != 0 || insn_len <= 0)
+ goto free_attr;
+
+ /* plain bpf_prog allocation */
+ err = -ENOMEM;
+ prog = kmalloc(bpf_prog_size(insn_len), GFP_USER);
+ if (!prog)
+ goto free_attr;
+
+ prog->len = insn_len / sizeof(struct bpf_insn);
+ memcpy(prog->insns, nla_data(tb[BPF_PROG_TEXT]), insn_len);
+ prog->orig_prog = NULL;
+ prog->jited = 0;
+ prog->has_info = 0;
+
+ /* allocate eBPF related auxilary data */
+ prog->info = kzalloc(sizeof(struct bpf_prog_info), GFP_USER);
+ if (!prog->info)
+ goto free_prog;
+ prog->has_info = 1;
+ atomic_set(&prog->info->refcnt, 1);
+ prog->info->is_gpl_compatible = is_gpl;
+
+ /* find program type: socket_filter vs tracing_filter */
+ err = find_prog_type(type, prog);
+ if (err < 0)
+ goto free_prog_info;
+
+ /* run eBPF verifier */
+ /* err = bpf_check(prog, tb); */
+
+ if (err < 0)
+ goto free_prog_info;
+
+ /* eBPF program is ready to be JITed */
+ bpf_prog_select_runtime(prog);
+
+ err = anon_inode_getfd("bpf-prog", &bpf_prog_fops, prog, O_RDWR | O_CLOEXEC);
+
+ if (err < 0)
+ /* failed to allocate fd */
+ goto free_prog_info;
+
+ /* user supplied eBPF prog attributes are no longer needed */
+ kfree(attr);
+
+ return err;
+
+free_prog_info:
+ free_bpf_prog_info(prog->info);
+free_prog:
+ bpf_prog_free(prog);
+free_attr:
+ kfree(attr);
+ return err;
+}
+
SYSCALL_DEFINE5(bpf, int, cmd, unsigned long, arg2, unsigned long, arg3,
unsigned long, arg4, unsigned long, arg5)
{
@@ -348,6 +541,9 @@ SYSCALL_DEFINE5(bpf, int, cmd, unsigned long, arg2, unsigned long, arg3,
case BPF_MAP_GET_NEXT_KEY:
return map_get_next_key((int) arg2, (void __user *) arg3,
(void __user *) arg4);
+ case BPF_PROG_LOAD:
+ return bpf_prog_load((enum bpf_prog_type) arg2,
+ (struct nlattr __user *) arg3, (int) arg4);
default:
return -EINVAL;
}
diff --git a/net/core/filter.c b/net/core/filter.c
index d814b8a89d0f..ed15874a9beb 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -835,6 +835,7 @@ static void bpf_release_orig_filter(struct bpf_prog *fp)
{
struct sock_fprog_kern *fprog = fp->orig_prog;
+ BUG_ON(fp->has_info);
if (fprog) {
kfree(fprog->filter);
kfree(fprog);
@@ -973,6 +974,7 @@ static struct bpf_prog *bpf_prepare_filter(struct bpf_prog *fp)
fp->bpf_func = NULL;
fp->jited = 0;
+ fp->has_info = 0;
err = bpf_check_classic(fp->insns, fp->len);
if (err) {
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 09/29] bpf: handle pseudo BPF_CALL insn
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api-u79uwXL29TY76Z2rM5mHXA,
netdev-u79uwXL29TY76Z2rM5mHXA,
linux-kernel-u79uwXL29TY76Z2rM5mHXA
In-Reply-To: <1408911690-7598-1-git-send-email-ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org>
in native eBPF programs userspace is using pseudo BPF_CALL instructions
which encode one of 'enum bpf_func_id' inside insn->imm field.
Verifier checks that program using correct function arguments to given func_id.
If all checks passed, kernel needs to fixup BPF_CALL->imm fields by
replacing func_id with in-kernel function pointer.
eBPF interpreter just calls the function.
In-kernel eBPF users continue to use generic BPF_CALL.
Signed-off-by: Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org>
---
kernel/bpf/syscall.c | 37 +++++++++++++++++++++++++++++++++++++
1 file changed, 37 insertions(+)
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index 4c5f5169f6fc..5a336af61858 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -338,6 +338,40 @@ void bpf_register_prog_type(struct bpf_prog_type_list *tl)
list_add(&tl->list_node, &bpf_prog_types);
}
+/* fixup insn->imm field of bpf_call instructions:
+ * if (insn->imm == BPF_FUNC_map_lookup_elem)
+ * insn->imm = bpf_map_lookup_elem - __bpf_call_base;
+ * else if (insn->imm == BPF_FUNC_map_update_elem)
+ * insn->imm = bpf_map_update_elem - __bpf_call_base;
+ * else ...
+ *
+ * this function is called after eBPF program passed verification
+ */
+static void fixup_bpf_calls(struct bpf_prog *prog)
+{
+ const struct bpf_func_proto *fn;
+ int i;
+
+ for (i = 0; i < prog->len; i++) {
+ struct bpf_insn *insn = &prog->insnsi[i];
+
+ if (insn->code == (BPF_JMP | BPF_CALL)) {
+ /* we reach here when program has bpf_call instructions
+ * and it passed bpf_check(), means that
+ * ops->get_func_proto must have been supplied, check it
+ */
+ BUG_ON(!prog->info->ops->get_func_proto);
+
+ fn = prog->info->ops->get_func_proto(insn->imm);
+ /* all functions that have prototype and verifier allowed
+ * programs to call them, must be real in-kernel functions
+ */
+ BUG_ON(!fn->func);
+ insn->imm = fn->func - __bpf_call_base;
+ }
+ }
+}
+
/* drop refcnt on maps used by eBPF program and free auxilary data */
static void free_bpf_prog_info(struct bpf_prog_info *info)
{
@@ -485,6 +519,9 @@ static int bpf_prog_load(enum bpf_prog_type type, struct nlattr __user *uattr,
if (err < 0)
goto free_prog_info;
+ /* fixup BPF_CALL->imm field */
+ fixup_bpf_calls(prog);
+
/* eBPF program is ready to be JITed */
bpf_prog_select_runtime(prog);
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 10/29] bpf: verifier (add docs)
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api, netdev, linux-kernel
In-Reply-To: <1408911690-7598-1-git-send-email-ast@plumgrid.com>
this patch adds all of eBPF verfier documentation and empty bpf_check()
The end goal for the verifier is to statically check safety of the program.
Verifier will catch:
- loops
- out of range jumps
- unreachable instructions
- invalid instructions
- uninitialized register access
- uninitialized stack access
- misaligned stack access
- out of range stack access
- invalid calling convention
More details in Documentation/networking/filter.txt
Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
---
Documentation/networking/filter.txt | 230 +++++++++++++++++++++++++++++++++++
include/linux/bpf.h | 2 +
kernel/bpf/Makefile | 2 +-
kernel/bpf/syscall.c | 2 +-
kernel/bpf/verifier.c | 152 +++++++++++++++++++++++
5 files changed, 386 insertions(+), 2 deletions(-)
create mode 100644 kernel/bpf/verifier.c
diff --git a/Documentation/networking/filter.txt b/Documentation/networking/filter.txt
index 27a0a6c6acb4..b121b01c3af4 100644
--- a/Documentation/networking/filter.txt
+++ b/Documentation/networking/filter.txt
@@ -1001,6 +1001,105 @@ instruction that loads 64-bit immediate value into a dst_reg.
Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads
32-bit immediate value into a register.
+eBPF verifier
+-------------
+The safety of the eBPF program is determined in two steps.
+
+First step does DAG check to disallow loops and other CFG validation.
+In particular it will detect programs that have unreachable instructions.
+(though classic BPF checker allows them)
+
+Second step starts from the first insn and descends all possible paths.
+It simulates execution of every insn and observes the state change of
+registers and stack.
+
+At the start of the program the register R1 contains a pointer to context
+and has type PTR_TO_CTX.
+If verifier sees an insn that does R2=R1, then R2 has now type
+PTR_TO_CTX as well and can be used on the right hand side of expression.
+If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=UNKNOWN_VALUE,
+since addition of two valid pointers makes invalid pointer.
+(In 'secure' mode verifier will reject any type of pointer arithmetic to make
+sure that kernel addresses don't leak to unprivileged users)
+
+If register was never written to, it's not readable:
+ bpf_mov R0 = R2
+ bpf_exit
+will be rejected, since R2 is unreadable at the start of the program.
+
+After kernel function call, R1-R5 are reset to unreadable and
+R0 has a return type of the function.
+
+Since R6-R9 are callee saved, their state is preserved across the call.
+ bpf_mov R6 = 1
+ bpf_call foo
+ bpf_mov R0 = R6
+ bpf_exit
+is a correct program. If there was R1 instead of R6, it would have
+been rejected.
+
+Classic BPF register X is mapped to eBPF register R7 inside sk_convert_filter(),
+so that its state is preserved across calls.
+
+load/store instructions are allowed only with registers of valid types, which
+are PTR_TO_CTX, PTR_TO_MAP, FRAME_PTR. They are bounds and alignment checked.
+For example:
+ bpf_mov R1 = 1
+ bpf_mov R2 = 2
+ bpf_xadd *(u32 *)(R1 + 3) += R2
+ bpf_exit
+will be rejected, since R1 doesn't have a valid pointer type at the time of
+execution of instruction bpf_xadd.
+
+At the start R1 contains pointer to ctx and R1 type is PTR_TO_CTX.
+ctx is generic. verifier is configured to known what context is for particular
+class of bpf programs. For example, context == skb (for socket filters) and
+ctx == seccomp_data for seccomp filters.
+A callback is used to customize verifier to restrict eBPF program access to only
+certain fields within ctx structure with specified size and alignment.
+
+For example, the following insn:
+ bpf_ld R0 = *(u32 *)(R6 + 8)
+intends to load a word from address R6 + 8 and store it into R0
+If R6=PTR_TO_CTX, via is_valid_access() callback the verifier will know
+that offset 8 of size 4 bytes can be accessed for reading, otherwise
+the verifier will reject the program.
+If R6=FRAME_PTR, then access should be aligned and be within
+stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8,
+so it will fail verification, since it's out of bounds.
+
+The verifier will allow eBPF program to read data from stack only after
+it wrote into it.
+Classic BPF verifier does similar check with M[0-15] memory slots.
+For example:
+ bpf_ld R0 = *(u32 *)(R10 - 4)
+ bpf_exit
+is invalid program.
+Though R10 is correct read-only register and has type FRAME_PTR
+and R10 - 4 is within stack bounds, there were no stores into that location.
+
+Pointer register spill/fill is tracked as well, since four (R6-R9)
+callee saved registers may not be enough for some programs.
+
+Allowed function calls are customized with bpf_verifier_ops->get_func_proto()
+The eBPF verifier will check that registers match argument constraints.
+After the call register R0 will be set to return type of the function.
+
+Function calls is a main mechanism to extend functionality of eBPF programs.
+Socket filters may let programs to call one set of functions, whereas tracing
+filters may allow completely different set.
+
+If a function made accessible to eBPF program, it needs to be thought through
+from security point of view. The verifier will guarantee that the function is
+called with valid arguments.
+
+seccomp vs socket filters have different security restrictions for classic BPF.
+Seccomp solves this by two stage verifier: classic BPF verifier is followed
+by seccomp verifier. In case of eBPF one configurable verifier is shared for
+all use cases.
+
+See details of eBPF verifier in kernel/bpf/verifier.c
+
eBPF maps
---------
'maps' is a generic storage of different types for sharing data between kernel
@@ -1072,6 +1171,137 @@ size. It will not let programs pass junk values to bpf_map_*_elem() functions,
so these functions (implemented in C inside kernel) can safely access
the pointers in all cases.
+Understanding eBPF verifier messages
+------------------------------------
+
+The following are few examples of invalid eBPF programs and verifier error
+messages as seen in the log:
+
+Program with unreachable instructions:
+static struct bpf_insn prog[] = {
+ BPF_EXIT_INSN(),
+ BPF_EXIT_INSN(),
+};
+Error:
+ unreachable insn 1
+
+Program that reads uninitialized register:
+ BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
+ BPF_EXIT_INSN(),
+Error:
+ 0: (bf) r0 = r2
+ R2 !read_ok
+
+Program that doesn't initialize R0 before exiting:
+ BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
+ BPF_EXIT_INSN(),
+Error:
+ 0: (bf) r2 = r1
+ 1: (95) exit
+ R0 !read_ok
+
+Program that accesses stack out of bounds:
+ BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
+ BPF_EXIT_INSN(),
+Error:
+ 0: (7a) *(u64 *)(r10 +8) = 0
+ invalid stack off=8 size=8
+
+Program that doesn't initialize stack before passing its address into function:
+ BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+ BPF_LD_MAP_FD(BPF_REG_1, 0),
+ BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+ BPF_EXIT_INSN(),
+Error:
+ 0: (bf) r2 = r10
+ 1: (07) r2 += -8
+ 2: (b7) r1 = 0x0
+ 3: (85) call 1
+ invalid indirect read from stack off -8+0 size 8
+
+Program that uses invalid map_fd=0 while calling to map_lookup_elem() function:
+ BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+ BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+ BPF_LD_MAP_FD(BPF_REG_1, 0),
+ BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+ BPF_EXIT_INSN(),
+Error:
+ 0: (7a) *(u64 *)(r10 -8) = 0
+ 1: (bf) r2 = r10
+ 2: (07) r2 += -8
+ 3: (b7) r1 = 0x0
+ 4: (85) call 1
+ fd 0 is not pointing to valid bpf_map
+
+Program that doesn't check return value of map_lookup_elem() before accessing
+map element:
+ BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+ BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+ BPF_LD_MAP_FD(BPF_REG_1, 0),
+ BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+ BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
+ BPF_EXIT_INSN(),
+Error:
+ 0: (7a) *(u64 *)(r10 -8) = 0
+ 1: (bf) r2 = r10
+ 2: (07) r2 += -8
+ 3: (b7) r1 = 0x0
+ 4: (85) call 1
+ 5: (7a) *(u64 *)(r0 +0) = 0
+ R0 invalid mem access 'map_value_or_null'
+
+Program that correctly checks map_lookup_elem() returned value for NULL, but
+accesses the memory with incorrect alignment:
+ BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+ BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+ BPF_LD_MAP_FD(BPF_REG_1, 0),
+ BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+ BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
+ BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
+ BPF_EXIT_INSN(),
+Error:
+ 0: (7a) *(u64 *)(r10 -8) = 0
+ 1: (bf) r2 = r10
+ 2: (07) r2 += -8
+ 3: (b7) r1 = 1
+ 4: (85) call 1
+ 5: (15) if r0 == 0x0 goto pc+1
+ R0=map_ptr R10=fp
+ 6: (7a) *(u64 *)(r0 +4) = 0
+ misaligned access off 4 size 8
+
+Program that correctly checks map_lookup_elem() returned value for NULL and
+accesses memory with correct alignment in one side of 'if' branch, but fails
+to do so in the other side of 'if' branch:
+ BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+ BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+ BPF_LD_MAP_FD(BPF_REG_1, 0),
+ BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+ BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
+ BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
+ BPF_EXIT_INSN(),
+ BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
+ BPF_EXIT_INSN(),
+Error:
+ 0: (7a) *(u64 *)(r10 -8) = 0
+ 1: (bf) r2 = r10
+ 2: (07) r2 += -8
+ 3: (b7) r1 = 1
+ 4: (85) call 1
+ 5: (15) if r0 == 0x0 goto pc+2
+ R0=map_ptr R10=fp
+ 6: (7a) *(u64 *)(r0 +0) = 0
+ 7: (95) exit
+
+ from 5 to 8: R0=imm0 R10=fp
+ 8: (7a) *(u64 *)(r0 +0) = 1
+ R0 invalid mem access 'imm'
+
Testing
-------
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index ac6320f44812..d818e473d12c 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -82,5 +82,7 @@ struct bpf_prog;
void bpf_prog_put(struct bpf_prog *prog);
struct bpf_prog *bpf_prog_get(u32 ufd);
+/* verify correctness of eBPF program */
+int bpf_check(struct bpf_prog *fp, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1]);
#endif /* _LINUX_BPF_H */
diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
index 558e12712ebc..95a9035e0f29 100644
--- a/kernel/bpf/Makefile
+++ b/kernel/bpf/Makefile
@@ -1 +1 @@
-obj-y := core.o syscall.o hashtab.o
+obj-y := core.o syscall.o hashtab.o verifier.o
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index 5a336af61858..a3581646ee11 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -514,7 +514,7 @@ static int bpf_prog_load(enum bpf_prog_type type, struct nlattr __user *uattr,
goto free_prog_info;
/* run eBPF verifier */
- /* err = bpf_check(prog, tb); */
+ err = bpf_check(prog, tb);
if (err < 0)
goto free_prog_info;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
new file mode 100644
index 000000000000..c1dc2441994a
--- /dev/null
+++ b/kernel/bpf/verifier.c
@@ -0,0 +1,152 @@
+/* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General Public
+ * License as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ */
+#include <linux/kernel.h>
+#include <linux/types.h>
+#include <linux/slab.h>
+#include <linux/bpf.h>
+#include <linux/filter.h>
+#include <net/netlink.h>
+#include <linux/file.h>
+#include <linux/vmalloc.h>
+
+/* bpf_check() is a static code analyzer that walks eBPF program
+ * instruction by instruction and updates register/stack state.
+ * All paths of conditional branches are analyzed until 'bpf_exit' insn.
+ *
+ * At the first pass depth-first-search verifies that the BPF program is a DAG.
+ * It rejects the following programs:
+ * - larger than BPF_MAXINSNS insns
+ * - if loop is present (detected via back-edge)
+ * - unreachable insns exist (shouldn't be a forest. program = one function)
+ * - out of bounds or malformed jumps
+ * The second pass is all possible path descent from the 1st insn.
+ * Conditional branch target insns keep a link list of verifier states.
+ * If the state already visited, this path can be pruned.
+ * If it wasn't a DAG, such state prunning would be incorrect, since it would
+ * skip cycles. Since it's analyzing all pathes through the program,
+ * the length of the analysis is limited to 32k insn, which may be hit even
+ * if insn_cnt < 4K, but there are too many branches that change stack/regs.
+ * Number of 'branches to be analyzed' is limited to 1k
+ *
+ * On entry to each instruction, each register has a type, and the instruction
+ * changes the types of the registers depending on instruction semantics.
+ * If instruction is BPF_MOV64_REG(BPF_REG_1, BPF_REG_5), then type of R5 is
+ * copied to R1.
+ *
+ * All registers are 64-bit (even on 32-bit arch)
+ * R0 - return register
+ * R1-R5 argument passing registers
+ * R6-R9 callee saved registers
+ * R10 - frame pointer read-only
+ *
+ * At the start of BPF program the register R1 contains a pointer to bpf_context
+ * and has type PTR_TO_CTX.
+ *
+ * Most of the time the registers have UNKNOWN_VALUE type, which
+ * means the register has some value, but it's not a valid pointer.
+ * Verifier doesn't attemp to track all arithmetic operations on pointers.
+ * The only special case is the sequence:
+ * BPF_MOV64_REG(BPF_REG_1, BPF_REG_10),
+ * BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -20),
+ * 1st insn copies R10 (which has FRAME_PTR) type into R1
+ * and 2nd arithmetic instruction is pattern matched to recognize
+ * that it wants to construct a pointer to some element within stack.
+ * So after 2nd insn, the register R1 has type PTR_TO_STACK
+ * (and -20 constant is saved for further stack bounds checking).
+ * Meaning that this reg is a pointer to stack plus known immediate constant.
+ *
+ * When program is doing load or store insns the type of base register can be:
+ * PTR_TO_MAP_VALUE, PTR_TO_CTX, FRAME_PTR. These are three pointer types recognized
+ * by check_mem_access() function.
+ *
+ * PTR_TO_MAP_VALUE means that this register is pointing to 'map element value'
+ * and the range of [ptr, ptr + map's value_size) is accessible.
+ *
+ * registers used to pass pointers to function calls are verified against
+ * function prototypes
+ *
+ * ARG_PTR_TO_MAP_KEY is a function argument constraint.
+ * It means that the register type passed to this function must be
+ * PTR_TO_STACK and it will be used inside the function as
+ * 'pointer to map element key'
+ *
+ * For example the argument constraints for bpf_map_lookup_elem():
+ * .ret_type = RET_PTR_TO_MAP_VALUE_OR_NULL,
+ * .arg1_type = ARG_CONST_MAP_ID,
+ * .arg2_type = ARG_PTR_TO_MAP_KEY,
+ *
+ * ret_type says that this function returns 'pointer to map elem value or null'
+ * 1st argument is a 'const immediate' value which must be one of valid map_ids.
+ * 2nd argument is a pointer to stack, which will be used inside the function as
+ * a pointer to map element key.
+ *
+ * On the kernel side the helper function looks like:
+ * u64 bpf_map_lookup_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5)
+ * {
+ * struct bpf_map *map;
+ * int map_id = r1;
+ * void *key = (void *) (unsigned long) r2;
+ * void *value;
+ *
+ * here kernel can access 'key' pointer safely, knowing that
+ * [key, key + map->key_size) bytes are valid and were initialized on
+ * the stack of eBPF program.
+ * }
+ *
+ * Corresponding eBPF program looked like:
+ * BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), // after this insn R2 type is FRAME_PTR
+ * BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), // after this insn R2 type is PTR_TO_STACK
+ * BPF_MOV64_IMM(BPF_REG_1, MAP_ID), // after this insn R1 type is CONST_ARG
+ * BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+ * here verifier looks a prototype of map_lookup_elem and sees:
+ * .arg1_type == ARG_CONST_MAP_ID and R1->type == CONST_ARG, which is ok so far,
+ * then it goes and finds a map with map_id equal to R1->imm value.
+ * Now verifier knows that this map has key of key_size bytes
+ *
+ * Then .arg2_type == ARG_PTR_TO_MAP_KEY and R2->type == PTR_TO_STACK, ok so far,
+ * Now verifier checks that [R2, R2 + map's key_size) are within stack limits
+ * and were initialized prior to this call.
+ * If it's ok, then verifier allows this BPF_CALL insn and looks at
+ * .ret_type which is RET_PTR_TO_MAP_VALUE_OR_NULL, so it sets
+ * R0->type = PTR_TO_MAP_VALUE_OR_NULL which means bpf_map_lookup_elem() function
+ * returns ether pointer to map value or NULL.
+ *
+ * When type PTR_TO_MAP_VALUE_OR_NULL passes through 'if (reg != 0) goto +off'
+ * insn, the register holding that pointer in the true branch changes state to
+ * PTR_TO_MAP_VALUE and the same register changes state to CONST_IMM in the false
+ * branch. See check_cond_jmp_op().
+ *
+ * After the call R0 is set to return type of the function and registers R1-R5
+ * are set to NOT_INIT to indicate that they are no longer readable.
+ *
+ * load/store alignment is checked:
+ * BPF_STX_MEM(BPF_DW, dest_reg, src_reg, 3)
+ * is rejected, because it's misaligned
+ *
+ * load/store to stack are bounds checked and register spill is tracked
+ * BPF_STX_MEM(BPF_B, BPF_REG_10, src_reg, 0)
+ * is rejected, because it's out of bounds
+ *
+ * load/store to map are bounds checked:
+ * BPF_STX_MEM(BPF_H, dest_reg, src_reg, 8)
+ * is ok, if dest_reg->type == PTR_TO_MAP_VALUE and
+ * 8 + sizeof(u16) <= map_info->value_size
+ *
+ * load/store to bpf_context are checked against known fields
+ */
+
+int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
+{
+ int ret = -EINVAL;
+
+ return ret;
+}
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 11/29] bpf: verifier (add ability to receive verification log)
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api, netdev, linux-kernel
In-Reply-To: <1408911690-7598-1-git-send-email-ast@plumgrid.com>
add optional attributes for BPF_PROG_LOAD syscall:
BPF_PROG_LOG_LEVEL, /* verbosity level of eBPF verifier */
BPF_PROG_LOG_BUF, /* user supplied buffer */
BPF_PROG_LOG_SIZE, /* size of user buffer */
In such case the verifier will return its verification log in the user
supplied buffer which can be used by humans to analyze why verifier
rejected given program
Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
---
include/uapi/linux/bpf.h | 4 +
kernel/bpf/syscall.c | 3 +
kernel/bpf/verifier.c | 236 ++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 243 insertions(+)
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index 7468fe55db7b..d280acad4b28 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -379,6 +379,10 @@ enum bpf_prog_attributes {
BPF_PROG_UNSPEC,
BPF_PROG_TEXT, /* array of eBPF instructions */
BPF_PROG_LICENSE, /* license string */
+ /* optional program attributes */
+ BPF_PROG_LOG_LEVEL, /* verbosity level of eBPF verifier */
+ BPF_PROG_LOG_BUF, /* user supplied buffer */
+ BPF_PROG_LOG_SIZE, /* size of user buffer */
__BPF_PROG_ATTR_MAX,
};
#define BPF_PROG_ATTR_MAX (__BPF_PROG_ATTR_MAX - 1)
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index a3581646ee11..60cb760cb423 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -443,6 +443,9 @@ struct bpf_prog *bpf_prog_get(u32 ufd)
static const struct nla_policy prog_policy[BPF_PROG_ATTR_MAX + 1] = {
[BPF_PROG_TEXT] = { .type = NLA_BINARY },
[BPF_PROG_LICENSE] = { .type = NLA_NUL_STRING },
+ [BPF_PROG_LOG_LEVEL] = { .type = NLA_U32 },
+ [BPF_PROG_LOG_BUF] = { .len = sizeof(void *) },
+ [BPF_PROG_LOG_SIZE] = { .type = NLA_U32 },
};
static int bpf_prog_load(enum bpf_prog_type type, struct nlattr __user *uattr,
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index c1dc2441994a..2484a3387ca2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -144,9 +144,245 @@
* load/store to bpf_context are checked against known fields
*/
+/* single container for all structs
+ * one verifier_env per bpf_check() call
+ */
+struct verifier_env {
+};
+
+/* verbose verifier prints what it's seeing
+ * bpf_check() is called under lock, so no race to access these global vars
+ */
+static u32 log_level, log_size, log_len;
+static void *log_buf;
+
+static DEFINE_MUTEX(bpf_verifier_lock);
+
+/* log_level controls verbosity level of eBPF verifier.
+ * verbose() is used to dump the verification trace to the log, so the user
+ * can figure out what's wrong with the program
+ */
+static void verbose(const char *fmt, ...)
+{
+ va_list args;
+
+ if (log_level == 0 || log_len >= log_size - 1)
+ return;
+
+ va_start(args, fmt);
+ log_len += vscnprintf(log_buf + log_len, log_size - log_len, fmt, args);
+ va_end(args);
+}
+
+static const char *const bpf_class_string[] = {
+ [BPF_LD] = "ld",
+ [BPF_LDX] = "ldx",
+ [BPF_ST] = "st",
+ [BPF_STX] = "stx",
+ [BPF_ALU] = "alu",
+ [BPF_JMP] = "jmp",
+ [BPF_RET] = "BUG",
+ [BPF_ALU64] = "alu64",
+};
+
+static const char *const bpf_alu_string[] = {
+ [BPF_ADD >> 4] = "+=",
+ [BPF_SUB >> 4] = "-=",
+ [BPF_MUL >> 4] = "*=",
+ [BPF_DIV >> 4] = "/=",
+ [BPF_OR >> 4] = "|=",
+ [BPF_AND >> 4] = "&=",
+ [BPF_LSH >> 4] = "<<=",
+ [BPF_RSH >> 4] = ">>=",
+ [BPF_NEG >> 4] = "neg",
+ [BPF_MOD >> 4] = "%=",
+ [BPF_XOR >> 4] = "^=",
+ [BPF_MOV >> 4] = "=",
+ [BPF_ARSH >> 4] = "s>>=",
+ [BPF_END >> 4] = "endian",
+};
+
+static const char *const bpf_ldst_string[] = {
+ [BPF_W >> 3] = "u32",
+ [BPF_H >> 3] = "u16",
+ [BPF_B >> 3] = "u8",
+ [BPF_DW >> 3] = "u64",
+};
+
+static const char *const bpf_jmp_string[] = {
+ [BPF_JA >> 4] = "jmp",
+ [BPF_JEQ >> 4] = "==",
+ [BPF_JGT >> 4] = ">",
+ [BPF_JGE >> 4] = ">=",
+ [BPF_JSET >> 4] = "&",
+ [BPF_JNE >> 4] = "!=",
+ [BPF_JSGT >> 4] = "s>",
+ [BPF_JSGE >> 4] = "s>=",
+ [BPF_CALL >> 4] = "call",
+ [BPF_EXIT >> 4] = "exit",
+};
+
+static void print_bpf_insn(struct bpf_insn *insn)
+{
+ u8 class = BPF_CLASS(insn->code);
+
+ if (class == BPF_ALU || class == BPF_ALU64) {
+ if (BPF_SRC(insn->code) == BPF_X)
+ verbose("(%02x) %sr%d %s %sr%d\n",
+ insn->code, class == BPF_ALU ? "(u32) " : "",
+ insn->dst_reg,
+ bpf_alu_string[BPF_OP(insn->code) >> 4],
+ class == BPF_ALU ? "(u32) " : "",
+ insn->src_reg);
+ else
+ verbose("(%02x) %sr%d %s %s%d\n",
+ insn->code, class == BPF_ALU ? "(u32) " : "",
+ insn->dst_reg,
+ bpf_alu_string[BPF_OP(insn->code) >> 4],
+ class == BPF_ALU ? "(u32) " : "",
+ insn->imm);
+ } else if (class == BPF_STX) {
+ if (BPF_MODE(insn->code) == BPF_MEM)
+ verbose("(%02x) *(%s *)(r%d %+d) = r%d\n",
+ insn->code,
+ bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+ insn->dst_reg,
+ insn->off, insn->src_reg);
+ else if (BPF_MODE(insn->code) == BPF_XADD)
+ verbose("(%02x) lock *(%s *)(r%d %+d) += r%d\n",
+ insn->code,
+ bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+ insn->dst_reg, insn->off,
+ insn->src_reg);
+ else
+ verbose("BUG_%02x\n", insn->code);
+ } else if (class == BPF_ST) {
+ if (BPF_MODE(insn->code) != BPF_MEM) {
+ verbose("BUG_st_%02x\n", insn->code);
+ return;
+ }
+ verbose("(%02x) *(%s *)(r%d %+d) = %d\n",
+ insn->code,
+ bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+ insn->dst_reg,
+ insn->off, insn->imm);
+ } else if (class == BPF_LDX) {
+ if (BPF_MODE(insn->code) != BPF_MEM) {
+ verbose("BUG_ldx_%02x\n", insn->code);
+ return;
+ }
+ verbose("(%02x) r%d = *(%s *)(r%d %+d)\n",
+ insn->code, insn->dst_reg,
+ bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+ insn->src_reg, insn->off);
+ } else if (class == BPF_LD) {
+ if (BPF_MODE(insn->code) == BPF_ABS) {
+ verbose("(%02x) r0 = *(%s *)skb[%d]\n",
+ insn->code,
+ bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+ insn->imm);
+ } else if (BPF_MODE(insn->code) == BPF_IND) {
+ verbose("(%02x) r0 = *(%s *)skb[r%d + %d]\n",
+ insn->code,
+ bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
+ insn->src_reg, insn->imm);
+ } else if (BPF_MODE(insn->code) == BPF_IMM) {
+ verbose("(%02x) r%d = 0x%x\n",
+ insn->code, insn->dst_reg, insn->imm);
+ } else {
+ verbose("BUG_ld_%02x\n", insn->code);
+ return;
+ }
+ } else if (class == BPF_JMP) {
+ u8 opcode = BPF_OP(insn->code);
+
+ if (opcode == BPF_CALL) {
+ verbose("(%02x) call %d\n", insn->code, insn->imm);
+ } else if (insn->code == (BPF_JMP | BPF_JA)) {
+ verbose("(%02x) goto pc%+d\n",
+ insn->code, insn->off);
+ } else if (insn->code == (BPF_JMP | BPF_EXIT)) {
+ verbose("(%02x) exit\n", insn->code);
+ } else if (BPF_SRC(insn->code) == BPF_X) {
+ verbose("(%02x) if r%d %s r%d goto pc%+d\n",
+ insn->code, insn->dst_reg,
+ bpf_jmp_string[BPF_OP(insn->code) >> 4],
+ insn->src_reg, insn->off);
+ } else {
+ verbose("(%02x) if r%d %s 0x%x goto pc%+d\n",
+ insn->code, insn->dst_reg,
+ bpf_jmp_string[BPF_OP(insn->code) >> 4],
+ insn->imm, insn->off);
+ }
+ } else {
+ verbose("(%02x) %s\n", insn->code, bpf_class_string[class]);
+ }
+}
+
int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
{
+ void __user *log_ubuf = NULL;
+ struct verifier_env *env;
int ret = -EINVAL;
+ if (prog->len <= 0 || prog->len > BPF_MAXINSNS)
+ return -E2BIG;
+
+ /* 'struct verifier_env' can be global, but since it's not small,
+ * allocate/free it every time bpf_check() is called
+ */
+ env = kzalloc(sizeof(struct verifier_env), GFP_KERNEL);
+ if (!env)
+ return -ENOMEM;
+
+ /* grab the mutex to protect few globals used by verifier */
+ mutex_lock(&bpf_verifier_lock);
+
+ if (tb[BPF_PROG_LOG_LEVEL] && tb[BPF_PROG_LOG_BUF] &&
+ tb[BPF_PROG_LOG_SIZE]) {
+ /* user requested verbose verifier output
+ * and supplied buffer to store the verification trace
+ */
+ log_level = nla_get_u32(tb[BPF_PROG_LOG_LEVEL]);
+ log_ubuf = *(void __user **) nla_data(tb[BPF_PROG_LOG_BUF]);
+ log_size = nla_get_u32(tb[BPF_PROG_LOG_SIZE]);
+ log_len = 0;
+
+ ret = -EINVAL;
+ /* log_* values have to be sane */
+ if (log_size < 128 || log_size > UINT_MAX >> 8 ||
+ log_level == 0 || log_ubuf == NULL)
+ goto free_env;
+
+ ret = -ENOMEM;
+ log_buf = vmalloc(log_size);
+ if (!log_buf)
+ goto free_env;
+ } else {
+ log_level = 0;
+ }
+
+ /* ret = do_check(env); */
+
+ if (log_level && log_len >= log_size - 1) {
+ BUG_ON(log_len >= log_size);
+ /* verifier log exceeded user supplied buffer */
+ ret = -ENOSPC;
+ /* fall through to return what was recorded */
+ }
+
+ /* copy verifier log back to user space including trailing zero */
+ if (log_level && copy_to_user(log_ubuf, log_buf, log_len + 1) != 0) {
+ ret = -EFAULT;
+ goto free_log_buf;
+ }
+
+
+free_log_buf:
+ if (log_level)
+ vfree(log_buf);
+free_env:
+ kfree(env);
+ mutex_unlock(&bpf_verifier_lock);
return ret;
}
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 12/29] bpf: handle pseudo BPF_LD_IMM64 insn
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api-u79uwXL29TY76Z2rM5mHXA,
netdev-u79uwXL29TY76Z2rM5mHXA,
linux-kernel-u79uwXL29TY76Z2rM5mHXA
In-Reply-To: <1408911690-7598-1-git-send-email-ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org>
eBPF programs passed from userspace are using pseudo BPF_LD_IMM64 instructions
to refer to process-local map_fd. Scan the program for such instructions and
if FDs are valid, convert them to 'struct bpf_map' pointers which will be used
by verifier to check access to maps in bpf_map_lookup/update() calls.
If program passes verifier, convert pseudo BPF_LD_IMM64 into generic by dropping
BPF_PSEUDO_MAP_FD flag.
Note that eBPF interpreter is generic and knows nothing about pseudo insns.
Signed-off-by: Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/w@public.gmane.org>
---
include/uapi/linux/bpf.h | 6 ++
kernel/bpf/verifier.c | 147 ++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 153 insertions(+)
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index d280acad4b28..2f4d92df4fbe 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -176,6 +176,12 @@ enum {
.off = 0, \
.imm = ((__u64) (IMM)) >> 32 })
+#define BPF_PSEUDO_MAP_FD 1
+
+/* pseudo BPF_LD_IMM64 insn used to refer to process-local map_fd */
+#define BPF_LD_MAP_FD(DST, MAP_FD) \
+ BPF_LD_IMM64_RAW(DST, BPF_PSEUDO_MAP_FD, MAP_FD)
+
/* Short form of mov based on type, BPF_X: dst_reg = src_reg, BPF_K: dst_reg = imm32 */
#define BPF_MOV64_RAW(TYPE, DST, SRC, IMM) \
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2484a3387ca2..28ce2cfa49db 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -144,10 +144,15 @@
* load/store to bpf_context are checked against known fields
*/
+#define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
+
/* single container for all structs
* one verifier_env per bpf_check() call
*/
struct verifier_env {
+ struct bpf_prog *prog; /* eBPF program being verified */
+ struct bpf_map *used_maps[MAX_USED_MAPS]; /* array of map's used by eBPF program */
+ u32 used_map_cnt; /* number of used maps */
};
/* verbose verifier prints what it's seeing
@@ -319,6 +324,115 @@ static void print_bpf_insn(struct bpf_insn *insn)
}
}
+/* return the map pointer stored inside BPF_LD_IMM64 instruction */
+static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn)
+{
+ u64 imm64 = ((u64) (u32) insn[0].imm) | ((u64) (u32) insn[1].imm) << 32;
+
+ return (struct bpf_map *) (unsigned long) imm64;
+}
+
+/* look for pseudo eBPF instructions that access map FDs and
+ * replace them with actual map pointers
+ */
+static int replace_map_fd_with_map_ptr(struct verifier_env *env)
+{
+ struct bpf_insn *insn = env->prog->insnsi;
+ int insn_cnt = env->prog->len;
+ int i, j;
+
+ for (i = 0; i < insn_cnt; i++, insn++) {
+ if (insn[0].code == (BPF_LD | BPF_IMM | BPF_DW)) {
+ struct bpf_map *map;
+ struct fd f;
+
+ if (i == insn_cnt - 1 || insn[1].code != 0 ||
+ insn[1].dst_reg != 0 || insn[1].src_reg != 0 ||
+ insn[1].off != 0) {
+ verbose("invalid bpf_ld_imm64 insn\n");
+ return -EINVAL;
+ }
+
+ if (insn->src_reg == 0)
+ /* valid generic load 64-bit imm */
+ goto next_insn;
+
+ if (insn->src_reg != BPF_PSEUDO_MAP_FD) {
+ verbose("unrecognized bpf_ld_imm64 insn\n");
+ return -EINVAL;
+ }
+
+ f = fdget(insn->imm);
+
+ map = bpf_map_get(f);
+ if (IS_ERR(map)) {
+ verbose("fd %d is not pointing to valid bpf_map\n",
+ insn->imm);
+ fdput(f);
+ return PTR_ERR(map);
+ }
+
+ /* store map pointer inside BPF_LD_IMM64 instruction */
+ insn[0].imm = (u32) (unsigned long) map;
+ insn[1].imm = ((u64) (unsigned long) map) >> 32;
+
+ /* check whether we recorded this map already */
+ for (j = 0; j < env->used_map_cnt; j++)
+ if (env->used_maps[j] == map) {
+ fdput(f);
+ goto next_insn;
+ }
+
+ if (env->used_map_cnt >= MAX_USED_MAPS) {
+ fdput(f);
+ return -E2BIG;
+ }
+
+ /* remember this map */
+ env->used_maps[env->used_map_cnt++] = map;
+
+ /* hold the map. If the program is rejected by verifier,
+ * the map will be released by release_maps() or it
+ * will be used by the valid program until it's unloaded
+ * and all maps are released in free_bpf_prog_info()
+ */
+ atomic_inc(&map->refcnt);
+
+ fdput(f);
+next_insn:
+ insn++;
+ i++;
+ }
+ }
+
+ /* now all pseudo BPF_LD_IMM64 instructions load valid
+ * 'struct bpf_map *' into a register instead of user map_fd.
+ * These pointers will be used later by verifier to validate map access.
+ */
+ return 0;
+}
+
+/* drop refcnt of maps used by the rejected program */
+static void release_maps(struct verifier_env *env)
+{
+ int i;
+
+ for (i = 0; i < env->used_map_cnt; i++)
+ bpf_map_put(env->used_maps[i]);
+}
+
+/* convert pseudo BPF_LD_IMM64 into generic BPF_LD_IMM64 */
+static void convert_pseudo_ld_imm64(struct verifier_env *env)
+{
+ struct bpf_insn *insn = env->prog->insnsi;
+ int insn_cnt = env->prog->len;
+ int i;
+
+ for (i = 0; i < insn_cnt; i++, insn++)
+ if (insn->code == (BPF_LD | BPF_IMM | BPF_DW))
+ insn->src_reg = 0;
+}
+
int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
{
void __user *log_ubuf = NULL;
@@ -335,6 +449,8 @@ int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
if (!env)
return -ENOMEM;
+ env->prog = prog;
+
/* grab the mutex to protect few globals used by verifier */
mutex_lock(&bpf_verifier_lock);
@@ -362,8 +478,14 @@ int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
log_level = 0;
}
+ ret = replace_map_fd_with_map_ptr(env);
+ if (ret < 0)
+ goto skip_full_check;
+
/* ret = do_check(env); */
+skip_full_check:
+
if (log_level && log_len >= log_size - 1) {
BUG_ON(log_len >= log_size);
/* verifier log exceeded user supplied buffer */
@@ -377,11 +499,36 @@ int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
goto free_log_buf;
}
+ if (ret == 0 && env->used_map_cnt) {
+ /* if program passed verifier, update used_maps in bpf_prog_info */
+ prog->info->used_maps = kmalloc_array(env->used_map_cnt,
+ sizeof(env->used_maps[0]),
+ GFP_KERNEL);
+
+ if (!prog->info->used_maps) {
+ ret = -ENOMEM;
+ goto free_log_buf;
+ }
+
+ memcpy(prog->info->used_maps, env->used_maps,
+ sizeof(env->used_maps[0]) * env->used_map_cnt);
+ prog->info->used_map_cnt = env->used_map_cnt;
+
+ /* program is valid. Convert pseudo bpf_ld_imm64 into generic
+ * bpf_ld_imm64 instructions
+ */
+ convert_pseudo_ld_imm64(env);
+ }
free_log_buf:
if (log_level)
vfree(log_buf);
free_env:
+ if (!prog->info->used_maps)
+ /* if we didn't copy map pointers into bpf_prog_info, release
+ * them now. Otherwise free_bpf_prog_info() will release them.
+ */
+ release_maps(env);
kfree(env);
mutex_unlock(&bpf_verifier_lock);
return ret;
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 13/29] bpf: verifier (add branch/goto checks)
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api, netdev, linux-kernel
In-Reply-To: <1408911690-7598-1-git-send-email-ast@plumgrid.com>
check that control flow graph of eBPF program is a directed acyclic graph
check_cfg() does:
- detect loops
- detect unreachable instructions
- check that program terminates with BPF_EXIT insn
- check that all branches are within program boundary
Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
---
kernel/bpf/verifier.c | 183 +++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 183 insertions(+)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 28ce2cfa49db..454079b145b2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -332,6 +332,185 @@ static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn)
return (struct bpf_map *) (unsigned long) imm64;
}
+/* non-recursive DFS pseudo code
+ * 1 procedure DFS-iterative(G,v):
+ * 2 label v as discovered
+ * 3 let S be a stack
+ * 4 S.push(v)
+ * 5 while S is not empty
+ * 6 t <- S.pop()
+ * 7 if t is what we're looking for:
+ * 8 return t
+ * 9 for all edges e in G.adjacentEdges(t) do
+ * 10 if edge e is already labelled
+ * 11 continue with the next edge
+ * 12 w <- G.adjacentVertex(t,e)
+ * 13 if vertex w is not discovered and not explored
+ * 14 label e as tree-edge
+ * 15 label w as discovered
+ * 16 S.push(w)
+ * 17 continue at 5
+ * 18 else if vertex w is discovered
+ * 19 label e as back-edge
+ * 20 else
+ * 21 // vertex w is explored
+ * 22 label e as forward- or cross-edge
+ * 23 label t as explored
+ * 24 S.pop()
+ *
+ * convention:
+ * 0x10 - discovered
+ * 0x11 - discovered and fall-through edge labelled
+ * 0x12 - discovered and fall-through and branch edges labelled
+ * 0x20 - explored
+ */
+
+enum {
+ DISCOVERED = 0x10,
+ EXPLORED = 0x20,
+ FALLTHROUGH = 1,
+ BRANCH = 2,
+};
+
+#define PUSH_INT(I) \
+ do { \
+ if (cur_stack >= insn_cnt) { \
+ ret = -E2BIG; \
+ goto free_st; \
+ } \
+ stack[cur_stack++] = I; \
+ } while (0)
+
+#define PEEK_INT() \
+ ({ \
+ int _ret; \
+ if (cur_stack == 0) \
+ _ret = -1; \
+ else \
+ _ret = stack[cur_stack - 1]; \
+ _ret; \
+ })
+
+#define POP_INT() \
+ ({ \
+ int _ret; \
+ if (cur_stack == 0) \
+ _ret = -1; \
+ else \
+ _ret = stack[--cur_stack]; \
+ _ret; \
+ })
+
+#define PUSH_INSN(T, W, E) \
+ do { \
+ int w = W; \
+ if (E == FALLTHROUGH && st[T] >= (DISCOVERED | FALLTHROUGH)) \
+ break; \
+ if (E == BRANCH && st[T] >= (DISCOVERED | BRANCH)) \
+ break; \
+ if (w < 0 || w >= insn_cnt) { \
+ verbose("jump out of range from insn %d to %d\n", T, w); \
+ ret = -EINVAL; \
+ goto free_st; \
+ } \
+ if (st[w] == 0) { \
+ /* tree-edge */ \
+ st[T] = DISCOVERED | E; \
+ st[w] = DISCOVERED; \
+ PUSH_INT(w); \
+ goto peek_stack; \
+ } else if ((st[w] & 0xF0) == DISCOVERED) { \
+ verbose("back-edge from insn %d to %d\n", T, w); \
+ ret = -EINVAL; \
+ goto free_st; \
+ } else if (st[w] == EXPLORED) { \
+ /* forward- or cross-edge */ \
+ st[T] = DISCOVERED | E; \
+ } else { \
+ verbose("insn state internal bug\n"); \
+ ret = -EFAULT; \
+ goto free_st; \
+ } \
+ } while (0)
+
+/* non-recursive depth-first-search to detect loops in BPF program
+ * loop == back-edge in directed graph
+ */
+static int check_cfg(struct verifier_env *env)
+{
+ struct bpf_insn *insns = env->prog->insnsi;
+ int insn_cnt = env->prog->len;
+ int cur_stack = 0;
+ int *stack;
+ int ret = 0;
+ int *st;
+ int i, t;
+
+ st = kzalloc(sizeof(int) * insn_cnt, GFP_KERNEL);
+ if (!st)
+ return -ENOMEM;
+
+ stack = kzalloc(sizeof(int) * insn_cnt, GFP_KERNEL);
+ if (!stack) {
+ kfree(st);
+ return -ENOMEM;
+ }
+
+ st[0] = DISCOVERED; /* mark 1st insn as discovered */
+ PUSH_INT(0);
+
+peek_stack:
+ while ((t = PEEK_INT()) != -1) {
+ if (BPF_CLASS(insns[t].code) == BPF_JMP) {
+ u8 opcode = BPF_OP(insns[t].code);
+
+ if (opcode == BPF_EXIT) {
+ goto mark_explored;
+ } else if (opcode == BPF_CALL) {
+ PUSH_INSN(t, t + 1, FALLTHROUGH);
+ } else if (opcode == BPF_JA) {
+ if (BPF_SRC(insns[t].code) != BPF_K) {
+ ret = -EINVAL;
+ goto free_st;
+ }
+ /* unconditional jump with single edge */
+ PUSH_INSN(t, t + insns[t].off + 1, FALLTHROUGH);
+ } else {
+ /* conditional jump with two edges */
+ PUSH_INSN(t, t + 1, FALLTHROUGH);
+ PUSH_INSN(t, t + insns[t].off + 1, BRANCH);
+ }
+ } else {
+ /* all other non-branch instructions with single
+ * fall-through edge
+ */
+ PUSH_INSN(t, t + 1, FALLTHROUGH);
+ }
+
+mark_explored:
+ st[t] = EXPLORED;
+ if (POP_INT() == -1) {
+ verbose("pop_int internal bug\n");
+ ret = -EFAULT;
+ goto free_st;
+ }
+ }
+
+
+ for (i = 0; i < insn_cnt; i++) {
+ if (st[i] != EXPLORED) {
+ verbose("unreachable insn %d\n", i);
+ ret = -EINVAL;
+ goto free_st;
+ }
+ }
+
+free_st:
+ kfree(st);
+ kfree(stack);
+ return ret;
+}
+
/* look for pseudo eBPF instructions that access map FDs and
* replace them with actual map pointers
*/
@@ -482,6 +661,10 @@ int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
if (ret < 0)
goto skip_full_check;
+ ret = check_cfg(env);
+ if (ret < 0)
+ goto skip_full_check;
+
/* ret = do_check(env); */
skip_full_check:
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 14/29] bpf: verifier (add verifier core)
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api, netdev, linux-kernel
In-Reply-To: <1408911690-7598-1-git-send-email-ast@plumgrid.com>
This patch adds verifier core which simulates execution of every insn and
records the state of registers and program stack. Every branch instruction seen
during simulation is pushed into state stack. When verifier reaches BPF_EXIT,
it pops the state from the stack and continues until it reaches BPF_EXIT again.
For program:
1: bpf_mov r1, xxx
2: if (r1 == 0) goto 5
3: bpf_mov r0, 1
4: goto 6
5: bpf_mov r0, 2
6: bpf_exit
The verifier will walk insns: 1, 2, 3, 4, 6
then it will pop the state recorded at insn#2 and will continue: 5, 6
This way it walks all possible paths through the program and checks all
possible values of registers. While doing so, it checks for:
- invalid instructions
- uninitialized register access
- uninitialized stack access
- misaligned stack access
- out of range stack access
- invalid calling convention
- BPF_LD_ABS|IND instructions are only used in socket filters
- instruction encoding is not using reserved fields
Kernel subsystem configures the verifier with two callbacks:
- bool (*is_valid_access)(int off, int size, enum bpf_access_type type);
that provides information to the verifer which fields of 'ctx'
are accessible (remember 'ctx' is the first argument to eBPF program)
- const struct bpf_func_proto *(*get_func_proto)(enum bpf_func_id func_id);
returns argument constraints of kernel helper functions that eBPF program
may call, so that verifier can checks that R1-R5 types match the prototype
More details in Documentation/networking/filter.txt and in kernel/bpf/verifier.c
Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
---
include/linux/bpf.h | 47 ++
include/uapi/linux/bpf.h | 1 +
kernel/bpf/verifier.c | 1061 +++++++++++++++++++++++++++++++++++++++++++++-
3 files changed, 1108 insertions(+), 1 deletion(-)
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index d818e473d12c..4d99c62c6cea 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -47,6 +47,31 @@ void bpf_register_map_type(struct bpf_map_type_list *tl);
void bpf_map_put(struct bpf_map *map);
struct bpf_map *bpf_map_get(struct fd f);
+/* function argument constraints */
+enum bpf_arg_type {
+ ARG_ANYTHING = 0, /* any argument is ok */
+
+ /* the following constraints used to prototype
+ * bpf_map_lookup/update/delete_elem() functions
+ */
+ ARG_CONST_MAP_PTR, /* const argument used as pointer to bpf_map */
+ ARG_PTR_TO_MAP_KEY, /* pointer to stack used as map key */
+ ARG_PTR_TO_MAP_VALUE, /* pointer to stack used as map value */
+
+ /* the following constraints used to prototype bpf_memcmp() and other
+ * functions that access data on eBPF program stack
+ */
+ ARG_PTR_TO_STACK, /* any pointer to eBPF program stack */
+ ARG_CONST_STACK_SIZE, /* number of bytes accessed from stack */
+};
+
+/* type of values returned from helper functions */
+enum bpf_return_type {
+ RET_INTEGER, /* function returns integer */
+ RET_VOID, /* function doesn't return anything */
+ RET_PTR_TO_MAP_VALUE_OR_NULL, /* returns a pointer to map elem value or NULL */
+};
+
/* eBPF function prototype used by verifier to allow BPF_CALLs from eBPF programs
* to in-kernel helper functions and for adjusting imm32 field in BPF_CALL
* instructions after verifying
@@ -54,11 +79,33 @@ struct bpf_map *bpf_map_get(struct fd f);
struct bpf_func_proto {
u64 (*func)(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5);
bool gpl_only;
+ enum bpf_return_type ret_type;
+ enum bpf_arg_type arg1_type;
+ enum bpf_arg_type arg2_type;
+ enum bpf_arg_type arg3_type;
+ enum bpf_arg_type arg4_type;
+ enum bpf_arg_type arg5_type;
+};
+
+/* bpf_context is intentionally undefined structure. Pointer to bpf_context is
+ * the first argument to eBPF programs.
+ * For socket filters: 'struct bpf_context *' == 'struct sk_buff *'
+ */
+struct bpf_context;
+
+enum bpf_access_type {
+ BPF_READ = 1,
+ BPF_WRITE = 2
};
struct bpf_verifier_ops {
/* return eBPF function prototype for verification */
const struct bpf_func_proto *(*get_func_proto)(enum bpf_func_id func_id);
+
+ /* return true if 'size' wide access at offset 'off' within bpf_context
+ * with 'type' (read or write) is allowed
+ */
+ bool (*is_valid_access)(int off, int size, enum bpf_access_type type);
};
struct bpf_prog_type_list {
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index 2f4d92df4fbe..63284088aa48 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -396,6 +396,7 @@ enum bpf_prog_attributes {
enum bpf_prog_type {
BPF_PROG_TYPE_UNSPEC,
+ BPF_PROG_TYPE_SOCKET_FILTER,
};
/* integer value in 'imm' field of BPF_CALL instruction selects which helper
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 454079b145b2..14a0262b101c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -144,6 +144,72 @@
* load/store to bpf_context are checked against known fields
*/
+#define _(OP) ({ int ret = (OP); if (ret < 0) return ret; })
+
+/* types of values stored in eBPF registers */
+enum bpf_reg_type {
+ NOT_INIT = 0, /* nothing was written into register */
+ UNKNOWN_VALUE, /* reg doesn't contain a valid pointer */
+ PTR_TO_CTX, /* reg points to bpf_context */
+ CONST_PTR_TO_MAP, /* reg points to struct bpf_map */
+ PTR_TO_MAP_VALUE, /* reg points to map element value */
+ PTR_TO_MAP_VALUE_OR_NULL,/* points to map elem value or NULL */
+ FRAME_PTR, /* reg == frame_pointer */
+ PTR_TO_STACK, /* reg == frame_pointer + imm */
+ CONST_IMM, /* constant integer value */
+};
+
+struct reg_state {
+ enum bpf_reg_type type;
+ union {
+ /* valid when type == CONST_IMM | PTR_TO_STACK */
+ int imm;
+
+ /* valid when type == CONST_PTR_TO_MAP | PTR_TO_MAP_VALUE |
+ * PTR_TO_MAP_VALUE_OR_NULL
+ */
+ struct bpf_map *map_ptr;
+ };
+};
+
+enum bpf_stack_slot_type {
+ STACK_INVALID, /* nothing was stored in this stack slot */
+ STACK_SPILL, /* 1st byte of register spilled into stack */
+ STACK_SPILL_PART, /* other 7 bytes of register spill */
+ STACK_MISC /* BPF program wrote some data into this slot */
+};
+
+struct bpf_stack_slot {
+ enum bpf_stack_slot_type stype;
+ struct reg_state reg_st;
+};
+
+/* state of the program:
+ * type of all registers and stack info
+ */
+struct verifier_state {
+ struct reg_state regs[MAX_BPF_REG];
+ struct bpf_stack_slot stack[MAX_BPF_STACK];
+};
+
+/* linked list of verifier states used to prune search */
+struct verifier_state_list {
+ struct verifier_state state;
+ struct verifier_state_list *next;
+};
+
+/* verifier_state + insn_idx are pushed to stack when branch is encountered */
+struct verifier_stack_elem {
+ /* verifer state is 'st'
+ * before processing instruction 'insn_idx'
+ * and after processing instruction 'prev_insn_idx'
+ */
+ struct verifier_state st;
+ int insn_idx;
+ int prev_insn_idx;
+ struct verifier_stack_elem *next;
+};
+
#define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
/* single container for all structs
@@ -151,6 +217,9 @@
*/
struct verifier_env {
struct bpf_prog *prog; /* eBPF program being verified */
+ struct verifier_stack_elem *head; /* stack of verifier states to be processed */
+ int stack_size; /* number of states to be processed */
+ struct verifier_state cur_state; /* current verifier state */
struct bpf_map *used_maps[MAX_USED_MAPS]; /* array of map's used by eBPF program */
u32 used_map_cnt; /* number of used maps */
};
@@ -179,6 +248,45 @@ static void verbose(const char *fmt, ...)
va_end(args);
}
+/* string representation of 'enum bpf_reg_type' */
+static const char * const reg_type_str[] = {
+ [NOT_INIT] = "?",
+ [UNKNOWN_VALUE] = "inv",
+ [PTR_TO_CTX] = "ctx",
+ [CONST_PTR_TO_MAP] = "map_ptr",
+ [PTR_TO_MAP_VALUE] = "map_value",
+ [PTR_TO_MAP_VALUE_OR_NULL] = "map_value_or_null",
+ [FRAME_PTR] = "fp",
+ [PTR_TO_STACK] = "fp",
+ [CONST_IMM] = "imm",
+};
+
+static void print_verifier_state(struct verifier_env *env)
+{
+ enum bpf_reg_type t;
+ int i;
+
+ for (i = 0; i < MAX_BPF_REG; i++) {
+ t = env->cur_state.regs[i].type;
+ if (t == NOT_INIT)
+ continue;
+ verbose(" R%d=%s", i, reg_type_str[t]);
+ if (t == CONST_IMM || t == PTR_TO_STACK)
+ verbose("%d", env->cur_state.regs[i].imm);
+ else if (t == CONST_PTR_TO_MAP || t == PTR_TO_MAP_VALUE ||
+ t == PTR_TO_MAP_VALUE_OR_NULL)
+ verbose("(ks=%d,vs=%d)",
+ env->cur_state.regs[i].map_ptr->key_size,
+ env->cur_state.regs[i].map_ptr->value_size);
+ }
+ for (i = 0; i < MAX_BPF_STACK; i++) {
+ if (env->cur_state.stack[i].stype == STACK_SPILL)
+ verbose(" fp%d=%s", -MAX_BPF_STACK + i,
+ reg_type_str[env->cur_state.stack[i].reg_st.type]);
+ }
+ verbose("\n");
+}
+
static const char *const bpf_class_string[] = {
[BPF_LD] = "ld",
[BPF_LDX] = "ldx",
@@ -324,6 +432,695 @@ static void print_bpf_insn(struct bpf_insn *insn)
}
}
+static int pop_stack(struct verifier_env *env, int *prev_insn_idx)
+{
+ struct verifier_stack_elem *elem;
+ int insn_idx;
+
+ if (env->head == NULL)
+ return -1;
+
+ memcpy(&env->cur_state, &env->head->st, sizeof(env->cur_state));
+ insn_idx = env->head->insn_idx;
+ if (prev_insn_idx)
+ *prev_insn_idx = env->head->prev_insn_idx;
+ elem = env->head->next;
+ kfree(env->head);
+ env->head = elem;
+ env->stack_size--;
+ return insn_idx;
+}
+
+static struct verifier_state *push_stack(struct verifier_env *env, int insn_idx,
+ int prev_insn_idx)
+{
+ struct verifier_stack_elem *elem;
+
+ elem = kmalloc(sizeof(struct verifier_stack_elem), GFP_KERNEL);
+ if (!elem)
+ goto err;
+
+ memcpy(&elem->st, &env->cur_state, sizeof(env->cur_state));
+ elem->insn_idx = insn_idx;
+ elem->prev_insn_idx = prev_insn_idx;
+ elem->next = env->head;
+ env->head = elem;
+ env->stack_size++;
+ if (env->stack_size > 1024) {
+ verbose("BPF program is too complex\n");
+ goto err;
+ }
+ return &elem->st;
+err:
+ /* pop all elements and return */
+ while (pop_stack(env, NULL) >= 0);
+ return NULL;
+}
+
+#define CALLER_SAVED_REGS 6
+static const int caller_saved[CALLER_SAVED_REGS] = {
+ BPF_REG_0, BPF_REG_1, BPF_REG_2, BPF_REG_3, BPF_REG_4, BPF_REG_5
+};
+
+static void init_reg_state(struct reg_state *regs)
+{
+ int i;
+
+ for (i = 0; i < MAX_BPF_REG; i++) {
+ regs[i].type = NOT_INIT;
+ regs[i].imm = 0;
+ regs[i].map_ptr = NULL;
+ }
+
+ /* frame pointer */
+ regs[BPF_REG_FP].type = FRAME_PTR;
+
+ /* 1st arg to a function */
+ regs[BPF_REG_1].type = PTR_TO_CTX;
+}
+
+static void mark_reg_unknown_value(struct reg_state *regs, u32 regno)
+{
+ BUG_ON(regno >= MAX_BPF_REG);
+ regs[regno].type = UNKNOWN_VALUE;
+ regs[regno].imm = 0;
+ regs[regno].map_ptr = NULL;
+}
+
+enum reg_arg_type {
+ SRC_OP, /* register is used as source operand */
+ DST_OP, /* register is used as destination operand */
+ DST_OP_NO_MARK /* same as above, check only, don't mark */
+};
+
+static int check_reg_arg(struct reg_state *regs, u32 regno,
+ enum reg_arg_type t)
+{
+ if (regno >= MAX_BPF_REG) {
+ verbose("R%d is invalid\n", regno);
+ return -EINVAL;
+ }
+
+ if (t == SRC_OP) {
+ /* check whether register used as source operand can be read */
+ if (regs[regno].type == NOT_INIT) {
+ verbose("R%d !read_ok\n", regno);
+ return -EACCES;
+ }
+ } else {
+ /* check whether register used as dest operand can be written to */
+ if (regno == BPF_REG_FP) {
+ verbose("frame pointer is read only\n");
+ return -EACCES;
+ }
+ if (t == DST_OP)
+ mark_reg_unknown_value(regs, regno);
+ }
+ return 0;
+}
+
+static int bpf_size_to_bytes(int bpf_size)
+{
+ if (bpf_size == BPF_W)
+ return 4;
+ else if (bpf_size == BPF_H)
+ return 2;
+ else if (bpf_size == BPF_B)
+ return 1;
+ else if (bpf_size == BPF_DW)
+ return 8;
+ else
+ return -EINVAL;
+}
+
+/* check_stack_read/write functions track spill/fill of registers,
+ * stack boundary and alignment are checked in check_mem_access()
+ */
+static int check_stack_write(struct verifier_state *state, int off, int size,
+ int value_regno)
+{
+ struct bpf_stack_slot *slot;
+ int i;
+
+ if (value_regno >= 0 &&
+ (state->regs[value_regno].type == PTR_TO_MAP_VALUE ||
+ state->regs[value_regno].type == PTR_TO_STACK ||
+ state->regs[value_regno].type == PTR_TO_CTX)) {
+
+ /* register containing pointer is being spilled into stack */
+ if (size != 8) {
+ verbose("invalid size of register spill\n");
+ return -EACCES;
+ }
+
+ slot = &state->stack[MAX_BPF_STACK + off];
+ slot->stype = STACK_SPILL;
+ /* save register state */
+ slot->reg_st = state->regs[value_regno];
+ for (i = 1; i < 8; i++) {
+ slot = &state->stack[MAX_BPF_STACK + off + i];
+ slot->stype = STACK_SPILL_PART;
+ slot->reg_st.type = UNKNOWN_VALUE;
+ slot->reg_st.map_ptr = NULL;
+ }
+ } else {
+
+ /* regular write of data into stack */
+ for (i = 0; i < size; i++) {
+ slot = &state->stack[MAX_BPF_STACK + off + i];
+ slot->stype = STACK_MISC;
+ slot->reg_st.type = UNKNOWN_VALUE;
+ slot->reg_st.map_ptr = NULL;
+ }
+ }
+ return 0;
+}
+
+static int check_stack_read(struct verifier_state *state, int off, int size,
+ int value_regno)
+{
+ int i;
+ struct bpf_stack_slot *slot;
+
+ slot = &state->stack[MAX_BPF_STACK + off];
+
+ if (slot->stype == STACK_SPILL) {
+ if (size != 8) {
+ verbose("invalid size of register spill\n");
+ return -EACCES;
+ }
+ for (i = 1; i < 8; i++) {
+ if (state->stack[MAX_BPF_STACK + off + i].stype !=
+ STACK_SPILL_PART) {
+ verbose("corrupted spill memory\n");
+ return -EACCES;
+ }
+ }
+
+ if (value_regno >= 0)
+ /* restore register state from stack */
+ state->regs[value_regno] = slot->reg_st;
+ return 0;
+ } else {
+ for (i = 0; i < size; i++) {
+ if (state->stack[MAX_BPF_STACK + off + i].stype !=
+ STACK_MISC) {
+ verbose("invalid read from stack off %d+%d size %d\n",
+ off, i, size);
+ return -EACCES;
+ }
+ }
+ if (value_regno >= 0)
+ /* have read misc data from the stack */
+ mark_reg_unknown_value(state->regs, value_regno);
+ return 0;
+ }
+}
+
+/* check read/write into map element returned by bpf_map_lookup_elem() */
+static int check_map_access(struct verifier_env *env, u32 regno, int off,
+ int size)
+{
+ struct bpf_map *map = env->cur_state.regs[regno].map_ptr;
+
+ if (off < 0 || off + size > map->value_size) {
+ verbose("invalid access to map value, value_size=%d off=%d size=%d\n",
+ map->value_size, off, size);
+ return -EACCES;
+ }
+ return 0;
+}
+
+/* check access to 'struct bpf_context' fields */
+static int check_ctx_access(struct verifier_env *env, int off, int size,
+ enum bpf_access_type t)
+{
+ if (env->prog->info->ops->is_valid_access &&
+ env->prog->info->ops->is_valid_access(off, size, t))
+ return 0;
+
+ verbose("invalid bpf_context access off=%d size=%d\n", off, size);
+ return -EACCES;
+}
+
+/* check whether memory at (regno + off) is accessible for t = (read | write)
+ * if t==write, value_regno is a register which value is stored into memory
+ * if t==read, value_regno is a register which will receive the value from memory
+ * if t==write && value_regno==-1, some unknown value is stored into memory
+ * if t==read && value_regno==-1, don't care what we read from memory
+ */
+static int check_mem_access(struct verifier_env *env, u32 regno, int off,
+ int bpf_size, enum bpf_access_type t,
+ int value_regno)
+{
+ struct verifier_state *state = &env->cur_state;
+ int size;
+
+ _(size = bpf_size_to_bytes(bpf_size));
+
+ if (off % size != 0) {
+ verbose("misaligned access off %d size %d\n", off, size);
+ return -EACCES;
+ }
+
+ if (state->regs[regno].type == PTR_TO_MAP_VALUE) {
+ _(check_map_access(env, regno, off, size));
+ if (t == BPF_READ && value_regno >= 0)
+ mark_reg_unknown_value(state->regs, value_regno);
+
+ } else if (state->regs[regno].type == PTR_TO_CTX) {
+ _(check_ctx_access(env, off, size, t));
+ if (t == BPF_READ && value_regno >= 0)
+ mark_reg_unknown_value(state->regs, value_regno);
+
+ } else if (state->regs[regno].type == FRAME_PTR) {
+ if (off >= 0 || off < -MAX_BPF_STACK) {
+ verbose("invalid stack off=%d size=%d\n", off, size);
+ return -EACCES;
+ }
+ if (t == BPF_WRITE)
+ _(check_stack_write(state, off, size, value_regno));
+ else
+ _(check_stack_read(state, off, size, value_regno));
+ } else {
+ verbose("R%d invalid mem access '%s'\n",
+ regno, reg_type_str[state->regs[regno].type]);
+ return -EACCES;
+ }
+ return 0;
+}
+
+static int check_xadd(struct verifier_env *env, struct bpf_insn *insn)
+{
+ struct reg_state *regs = env->cur_state.regs;
+
+ if ((BPF_SIZE(insn->code) != BPF_W && BPF_SIZE(insn->code) != BPF_DW) ||
+ insn->imm != 0) {
+ verbose("BPF_XADD uses reserved fields\n");
+ return -EINVAL;
+ }
+
+ /* check src1 operand */
+ _(check_reg_arg(regs, insn->src_reg, SRC_OP));
+ /* check src2 operand */
+ _(check_reg_arg(regs, insn->dst_reg, SRC_OP));
+
+ /* check whether atomic_add can read the memory */
+ _(check_mem_access(env, insn->dst_reg, insn->off,
+ BPF_SIZE(insn->code), BPF_READ, -1));
+
+ /* check whether atomic_add can write into the same memory */
+ _(check_mem_access(env, insn->dst_reg, insn->off,
+ BPF_SIZE(insn->code), BPF_WRITE, -1));
+ return 0;
+}
+
+/* when register 'regno' is passed into function that will read 'access_size'
+ * bytes from that pointer, make sure that it's within stack boundary
+ * and all elements of stack are initialized
+ */
+static int check_stack_boundary(struct verifier_env *env,
+ int regno, int access_size)
+{
+ struct verifier_state *state = &env->cur_state;
+ struct reg_state *regs = state->regs;
+ int off, i;
+
+ if (regs[regno].type != PTR_TO_STACK)
+ return -EACCES;
+
+ off = regs[regno].imm;
+ if (off >= 0 || off < -MAX_BPF_STACK || off + access_size > 0 ||
+ access_size <= 0) {
+ verbose("invalid stack type R%d off=%d access_size=%d\n",
+ regno, off, access_size);
+ return -EACCES;
+ }
+
+ for (i = 0; i < access_size; i++) {
+ if (state->stack[MAX_BPF_STACK + off + i].stype != STACK_MISC) {
+ verbose("invalid indirect read from stack off %d+%d size %d\n",
+ off, i, access_size);
+ return -EACCES;
+ }
+ }
+ return 0;
+}
+
+static int check_func_arg(struct verifier_env *env, u32 regno,
+ enum bpf_arg_type arg_type, struct bpf_map **mapp)
+{
+ struct reg_state *reg = env->cur_state.regs + regno;
+ enum bpf_reg_type expected_type;
+
+ if (arg_type == ARG_ANYTHING)
+ return 0;
+
+ if (reg->type == NOT_INIT) {
+ verbose("R%d !read_ok\n", regno);
+ return -EACCES;
+ }
+
+ if (arg_type == ARG_PTR_TO_STACK || arg_type == ARG_PTR_TO_MAP_KEY ||
+ arg_type == ARG_PTR_TO_MAP_VALUE) {
+ expected_type = PTR_TO_STACK;
+ } else if (arg_type == ARG_CONST_STACK_SIZE) {
+ expected_type = CONST_IMM;
+ } else if (arg_type == ARG_CONST_MAP_PTR) {
+ expected_type = CONST_PTR_TO_MAP;
+ } else {
+ verbose("unsupported arg_type %d\n", arg_type);
+ return -EFAULT;
+ }
+
+ if (reg->type != expected_type) {
+ verbose("R%d type=%s expected=%s\n", regno,
+ reg_type_str[reg->type], reg_type_str[expected_type]);
+ return -EACCES;
+ }
+
+ if (arg_type == ARG_CONST_MAP_PTR) {
+ /* bpf_map_xxx(map_ptr) call: remember that map_ptr */
+ *mapp = reg->map_ptr;
+
+ } else if (arg_type == ARG_PTR_TO_MAP_KEY) {
+ /* bpf_map_xxx(..., map_ptr, ..., key) call:
+ * check that [key, key + map->key_size) are within
+ * stack limits and initialized
+ */
+ if (!*mapp) {
+ /* in function declaration map_ptr must come before
+ * map_key or map_elem, so that it's verified
+ * and known before we have to check map_key here.
+ * It means that kernel subsystem misconfigured verifier
+ */
+ verbose("invalid map_ptr to access map->key\n");
+ return -EACCES;
+ }
+ _(check_stack_boundary(env, regno, (*mapp)->key_size));
+
+ } else if (arg_type == ARG_PTR_TO_MAP_VALUE) {
+ /* bpf_map_xxx(..., map_ptr, ..., value) call:
+ * check [value, value + map->value_size) validity
+ */
+ if (!*mapp) {
+ /* kernel subsystem misconfigured verifier */
+ verbose("invalid map_ptr to access map->elem\n");
+ return -EACCES;
+ }
+ _(check_stack_boundary(env, regno, (*mapp)->value_size));
+
+ } else if (arg_type == ARG_CONST_STACK_SIZE) {
+ /* bpf_xxx(..., buf, len) call will access 'len' bytes
+ * from stack pointer 'buf'. Check it
+ * note: regno == len, regno - 1 == buf
+ */
+ if (regno == 0) {
+ /* kernel subsystem misconfigured verifier */
+ verbose("ARG_CONST_STACK_SIZE cannot be first argument\n");
+ return -EACCES;
+ }
+ _(check_stack_boundary(env, regno - 1, reg->imm));
+ }
+
+ return 0;
+}
+
+static int check_call(struct verifier_env *env, int func_id)
+{
+ struct verifier_state *state = &env->cur_state;
+ const struct bpf_func_proto *fn = NULL;
+ struct reg_state *regs = state->regs;
+ struct bpf_map *map = NULL;
+ struct reg_state *reg;
+ int i;
+
+ /* find function prototype */
+ if (func_id <= 0 || func_id >= __BPF_FUNC_MAX_ID) {
+ verbose("invalid func %d\n", func_id);
+ return -EINVAL;
+ }
+
+ if (env->prog->info->ops->get_func_proto)
+ fn = env->prog->info->ops->get_func_proto(func_id);
+
+ if (!fn) {
+ verbose("unknown func %d\n", func_id);
+ return -EINVAL;
+ }
+
+ /* eBPF programs must be GPL compatible to use GPL-ed functions */
+ if (!env->prog->info->is_gpl_compatible && fn->gpl_only) {
+ verbose("cannot call GPL only function from proprietary program\n");
+ return -EINVAL;
+ }
+
+ /* check args */
+ _(check_func_arg(env, BPF_REG_1, fn->arg1_type, &map));
+ _(check_func_arg(env, BPF_REG_2, fn->arg2_type, &map));
+ _(check_func_arg(env, BPF_REG_3, fn->arg3_type, &map));
+ _(check_func_arg(env, BPF_REG_4, fn->arg4_type, &map));
+ _(check_func_arg(env, BPF_REG_5, fn->arg5_type, &map));
+
+ /* reset caller saved regs */
+ for (i = 0; i < CALLER_SAVED_REGS; i++) {
+ reg = regs + caller_saved[i];
+ reg->type = NOT_INIT;
+ reg->imm = 0;
+ }
+
+ /* update return register */
+ if (fn->ret_type == RET_INTEGER) {
+ regs[BPF_REG_0].type = UNKNOWN_VALUE;
+ } else if (fn->ret_type == RET_VOID) {
+ regs[BPF_REG_0].type = NOT_INIT;
+ } else if (fn->ret_type == RET_PTR_TO_MAP_VALUE_OR_NULL) {
+ regs[BPF_REG_0].type = PTR_TO_MAP_VALUE_OR_NULL;
+ /* remember map_ptr, so that check_map_access()
+ * can check 'value_size' boundary of memory access
+ * to map element returned from bpf_map_lookup_elem()
+ */
+ if (map == NULL) {
+ verbose("kernel subsystem misconfigured verifier\n");
+ return -EINVAL;
+ }
+ regs[BPF_REG_0].map_ptr = map;
+ } else {
+ verbose("unknown return type %d of func %d\n",
+ fn->ret_type, func_id);
+ return -EINVAL;
+ }
+ return 0;
+}
+
+/* check validity of 32-bit and 64-bit arithmetic operations */
+static int check_alu_op(struct reg_state *regs, struct bpf_insn *insn)
+{
+ u8 opcode = BPF_OP(insn->code);
+
+ if (opcode == BPF_END || opcode == BPF_NEG) {
+ if (opcode == BPF_NEG) {
+ if (BPF_SRC(insn->code) != 0 ||
+ insn->src_reg != BPF_REG_0 ||
+ insn->off != 0 || insn->imm != 0) {
+ verbose("BPF_NEG uses reserved fields\n");
+ return -EINVAL;
+ }
+ } else {
+ if (insn->src_reg != BPF_REG_0 || insn->off != 0 ||
+ (insn->imm != 16 && insn->imm != 32 && insn->imm != 64)) {
+ verbose("BPF_END uses reserved fields\n");
+ return -EINVAL;
+ }
+ }
+
+ /* check src operand */
+ _(check_reg_arg(regs, insn->dst_reg, SRC_OP));
+
+ /* check dest operand */
+ _(check_reg_arg(regs, insn->dst_reg, DST_OP));
+
+ } else if (opcode == BPF_MOV) {
+
+ if (BPF_SRC(insn->code) == BPF_X) {
+ if (insn->imm != 0 || insn->off != 0) {
+ verbose("BPF_MOV uses reserved fields\n");
+ return -EINVAL;
+ }
+
+ /* check src operand */
+ _(check_reg_arg(regs, insn->src_reg, SRC_OP));
+ } else {
+ if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
+ verbose("BPF_MOV uses reserved fields\n");
+ return -EINVAL;
+ }
+ }
+
+ /* check dest operand */
+ _(check_reg_arg(regs, insn->dst_reg, DST_OP));
+
+ if (BPF_SRC(insn->code) == BPF_X) {
+ if (BPF_CLASS(insn->code) == BPF_ALU64) {
+ /* case: R1 = R2
+ * copy register state to dest reg
+ */
+ regs[insn->dst_reg] = regs[insn->src_reg];
+ } else {
+ regs[insn->dst_reg].type = UNKNOWN_VALUE;
+ regs[insn->dst_reg].map_ptr = NULL;
+ }
+ } else {
+ /* case: R = imm
+ * remember the value we stored into this reg
+ */
+ regs[insn->dst_reg].type = CONST_IMM;
+ regs[insn->dst_reg].imm = insn->imm;
+ }
+
+ } else if (opcode > BPF_END) {
+ verbose("invalid BPF_ALU opcode %x\n", opcode);
+ return -EINVAL;
+
+ } else { /* all other ALU ops: and, sub, xor, add, ... */
+
+ bool stack_relative = false;
+
+ if (BPF_SRC(insn->code) == BPF_X) {
+ if (insn->imm != 0 || insn->off != 0) {
+ verbose("BPF_ALU uses reserved fields\n");
+ return -EINVAL;
+ }
+ /* check src1 operand */
+ _(check_reg_arg(regs, insn->src_reg, SRC_OP));
+ } else {
+ if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
+ verbose("BPF_ALU uses reserved fields\n");
+ return -EINVAL;
+ }
+ }
+
+ /* check src2 operand */
+ _(check_reg_arg(regs, insn->dst_reg, SRC_OP));
+
+ if ((opcode == BPF_MOD || opcode == BPF_DIV) &&
+ BPF_SRC(insn->code) == BPF_K && insn->imm == 0) {
+ verbose("div by zero\n");
+ return -EINVAL;
+ }
+
+ /* pattern match 'bpf_add Rx, imm' instruction */
+ if (opcode == BPF_ADD && BPF_CLASS(insn->code) == BPF_ALU64 &&
+ regs[insn->dst_reg].type == FRAME_PTR &&
+ BPF_SRC(insn->code) == BPF_K)
+ stack_relative = true;
+
+ /* check dest operand */
+ _(check_reg_arg(regs, insn->dst_reg, DST_OP));
+
+ if (stack_relative) {
+ regs[insn->dst_reg].type = PTR_TO_STACK;
+ regs[insn->dst_reg].imm = insn->imm;
+ }
+ }
+
+ return 0;
+}
+
+static int check_cond_jmp_op(struct verifier_env *env,
+ struct bpf_insn *insn, int *insn_idx)
+{
+ struct reg_state *regs = env->cur_state.regs;
+ struct verifier_state *other_branch;
+ u8 opcode = BPF_OP(insn->code);
+
+ if (opcode > BPF_EXIT) {
+ verbose("invalid BPF_JMP opcode %x\n", opcode);
+ return -EINVAL;
+ }
+
+ if (BPF_SRC(insn->code) == BPF_X) {
+ if (insn->imm != 0) {
+ verbose("BPF_JMP uses reserved fields\n");
+ return -EINVAL;
+ }
+
+ /* check src1 operand */
+ _(check_reg_arg(regs, insn->src_reg, SRC_OP));
+ } else {
+ if (insn->src_reg != BPF_REG_0) {
+ verbose("BPF_JMP uses reserved fields\n");
+ return -EINVAL;
+ }
+ }
+
+ /* check src2 operand */
+ _(check_reg_arg(regs, insn->dst_reg, SRC_OP));
+
+ /* detect if R == 0 where R was initialized to zero earlier */
+ if (BPF_SRC(insn->code) == BPF_K &&
+ (opcode == BPF_JEQ || opcode == BPF_JNE) &&
+ regs[insn->dst_reg].type == CONST_IMM &&
+ regs[insn->dst_reg].imm == insn->imm) {
+ if (opcode == BPF_JEQ) {
+ /* if (imm == imm) goto pc+off;
+ * only follow the goto, ignore fall-through
+ */
+ *insn_idx += insn->off;
+ return 0;
+ } else {
+ /* if (imm != imm) goto pc+off;
+ * only follow fall-through branch, since
+ * that's where the program will go
+ */
+ return 0;
+ }
+ }
+
+ other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx);
+ if (!other_branch)
+ return -EFAULT;
+
+ /* detect if R == 0 where R is returned value from bpf_map_lookup_elem() */
+ if (BPF_SRC(insn->code) == BPF_K &&
+ insn->imm == 0 && (opcode == BPF_JEQ ||
+ opcode == BPF_JNE) &&
+ regs[insn->dst_reg].type == PTR_TO_MAP_VALUE_OR_NULL) {
+ if (opcode == BPF_JEQ) {
+ /* next fallthrough insn can access memory via
+ * this register
+ */
+ regs[insn->dst_reg].type = PTR_TO_MAP_VALUE;
+ /* branch targer cannot access it, since reg == 0 */
+ other_branch->regs[insn->dst_reg].type = CONST_IMM;
+ other_branch->regs[insn->dst_reg].imm = 0;
+ } else {
+ other_branch->regs[insn->dst_reg].type = PTR_TO_MAP_VALUE;
+ regs[insn->dst_reg].type = CONST_IMM;
+ regs[insn->dst_reg].imm = 0;
+ }
+ } else if (BPF_SRC(insn->code) == BPF_K &&
+ (opcode == BPF_JEQ || opcode == BPF_JNE)) {
+
+ if (opcode == BPF_JEQ) {
+ /* detect if (R == imm) goto
+ * and in the target state recognize that R = imm
+ */
+ other_branch->regs[insn->dst_reg].type = CONST_IMM;
+ other_branch->regs[insn->dst_reg].imm = insn->imm;
+ } else {
+ /* detect if (R != imm) goto
+ * and in the fall-through state recognize that R = imm
+ */
+ regs[insn->dst_reg].type = CONST_IMM;
+ regs[insn->dst_reg].imm = insn->imm;
+ }
+ }
+ if (log_level)
+ print_verifier_state(env);
+ return 0;
+}
+
/* return the map pointer stored inside BPF_LD_IMM64 instruction */
static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn)
{
@@ -332,6 +1129,93 @@ static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn)
return (struct bpf_map *) (unsigned long) imm64;
}
+/* verify BPF_LD_IMM64 instruction */
+static int check_ld_imm(struct verifier_env *env, struct bpf_insn *insn)
+{
+ struct reg_state *regs = env->cur_state.regs;
+
+ if (BPF_SIZE(insn->code) != BPF_DW) {
+ verbose("invalid BPF_LD_IMM insn\n");
+ return -EINVAL;
+ }
+ if (insn->off != 0) {
+ verbose("BPF_LD_IMM64 uses reserved fields\n");
+ return -EINVAL;
+ }
+
+ _(check_reg_arg(regs, insn->dst_reg, DST_OP));
+
+ if (insn->src_reg == 0)
+ /* generic move 64-bit immediate into a register */
+ return 0;
+
+ /* replace_map_fd_with_map_ptr() should have caught bad ld_imm64 */
+ BUG_ON(insn->src_reg != BPF_PSEUDO_MAP_FD);
+
+ regs[insn->dst_reg].type = CONST_PTR_TO_MAP;
+ regs[insn->dst_reg].map_ptr = ld_imm64_to_map_ptr(insn);
+ return 0;
+}
+
+/* verify safety of LD_ABS|LD_IND instructions:
+ * - they can only appear in the programs where ctx == skb
+ * - since they are wrappers of function calls, they scratch R1-R5 registers,
+ * preserve R6-R9, and store return value into R0
+ *
+ * Implicit input:
+ * ctx == skb == R6 == CTX
+ *
+ * Explicit input:
+ * SRC == any register
+ * IMM == 32-bit immediate
+ *
+ * Output:
+ * R0 - 8/16/32-bit skb data converted to cpu endianness
+ */
+static int check_ld_abs(struct verifier_env *env, struct bpf_insn *insn)
+{
+ struct reg_state *regs = env->cur_state.regs;
+ u8 mode = BPF_MODE(insn->code);
+ struct reg_state *reg;
+ int i;
+
+ if (env->prog->info->prog_type != BPF_PROG_TYPE_SOCKET_FILTER) {
+ verbose("BPF_LD_ABS|IND instructions are only allowed in socket filters\n");
+ return -EINVAL;
+ }
+
+ if (insn->dst_reg != BPF_REG_0 || insn->off != 0 ||
+ (mode == BPF_ABS && insn->src_reg != BPF_REG_0)) {
+ verbose("BPF_LD_ABS uses reserved fields\n");
+ return -EINVAL;
+ }
+
+ /* check whether implicit source operand (register R6) is readable */
+ _(check_reg_arg(regs, BPF_REG_6, SRC_OP));
+
+ if (regs[BPF_REG_6].type != PTR_TO_CTX) {
+ verbose("at the time of BPF_LD_ABS|IND R6 != pointer to skb\n");
+ return -EINVAL;
+ }
+
+ if (mode == BPF_IND)
+ /* check explicit source operand */
+ _(check_reg_arg(regs, insn->src_reg, SRC_OP));
+
+ /* reset caller saved regs to unreadable */
+ for (i = 0; i < CALLER_SAVED_REGS; i++) {
+ reg = regs + caller_saved[i];
+ reg->type = NOT_INIT;
+ reg->imm = 0;
+ }
+
+ /* mark destination R0 register as readable, since it contains
+ * the value fetched from the packet
+ */
+ regs[BPF_REG_0].type = UNKNOWN_VALUE;
+ return 0;
+}
+
/* non-recursive DFS pseudo code
* 1 procedure DFS-iterative(G,v):
* 2 label v as discovered
@@ -511,6 +1395,180 @@ free_st:
return ret;
}
+static int do_check(struct verifier_env *env)
+{
+ struct verifier_state *state = &env->cur_state;
+ struct bpf_insn *insns = env->prog->insnsi;
+ struct reg_state *regs = state->regs;
+ int insn_cnt = env->prog->len;
+ int insn_idx, prev_insn_idx = 0;
+ int insn_processed = 0;
+ bool do_print_state = false;
+
+ init_reg_state(regs);
+ insn_idx = 0;
+ for (;;) {
+ struct bpf_insn *insn;
+ u8 class;
+
+ if (insn_idx >= insn_cnt) {
+ verbose("invalid insn idx %d insn_cnt %d\n",
+ insn_idx, insn_cnt);
+ return -EFAULT;
+ }
+
+ insn = &insns[insn_idx];
+ class = BPF_CLASS(insn->code);
+
+ if (++insn_processed > 32768) {
+ verbose("BPF program is too large. Proccessed %d insn\n",
+ insn_processed);
+ return -E2BIG;
+ }
+
+ if (log_level && do_print_state) {
+ verbose("\nfrom %d to %d:", prev_insn_idx, insn_idx);
+ print_verifier_state(env);
+ do_print_state = false;
+ }
+
+ if (log_level) {
+ verbose("%d: ", insn_idx);
+ print_bpf_insn(insn);
+ }
+
+ if (class == BPF_ALU || class == BPF_ALU64) {
+ _(check_alu_op(regs, insn));
+
+ } else if (class == BPF_LDX) {
+ if (BPF_MODE(insn->code) != BPF_MEM ||
+ insn->imm != 0) {
+ verbose("BPF_LDX uses reserved fields\n");
+ return -EINVAL;
+ }
+ /* check src operand */
+ _(check_reg_arg(regs, insn->src_reg, SRC_OP));
+
+ _(check_reg_arg(regs, insn->dst_reg, DST_OP_NO_MARK));
+
+ /* check that memory (src_reg + off) is readable,
+ * the state of dst_reg will be updated by this func
+ */
+ _(check_mem_access(env, insn->src_reg, insn->off,
+ BPF_SIZE(insn->code), BPF_READ,
+ insn->dst_reg));
+
+ } else if (class == BPF_STX) {
+ if (BPF_MODE(insn->code) == BPF_XADD) {
+ _(check_xadd(env, insn));
+ insn_idx++;
+ continue;
+ }
+
+ if (BPF_MODE(insn->code) != BPF_MEM ||
+ insn->imm != 0) {
+ verbose("BPF_STX uses reserved fields\n");
+ return -EINVAL;
+ }
+ /* check src1 operand */
+ _(check_reg_arg(regs, insn->src_reg, SRC_OP));
+ /* check src2 operand */
+ _(check_reg_arg(regs, insn->dst_reg, SRC_OP));
+
+ /* check that memory (dst_reg + off) is writeable */
+ _(check_mem_access(env, insn->dst_reg, insn->off,
+ BPF_SIZE(insn->code), BPF_WRITE,
+ insn->src_reg));
+
+ } else if (class == BPF_ST) {
+ if (BPF_MODE(insn->code) != BPF_MEM ||
+ insn->src_reg != BPF_REG_0) {
+ verbose("BPF_ST uses reserved fields\n");
+ return -EINVAL;
+ }
+ /* check src operand */
+ _(check_reg_arg(regs, insn->dst_reg, SRC_OP));
+
+ /* check that memory (dst_reg + off) is writeable */
+ _(check_mem_access(env, insn->dst_reg, insn->off,
+ BPF_SIZE(insn->code), BPF_WRITE,
+ -1));
+
+ } else if (class == BPF_JMP) {
+ u8 opcode = BPF_OP(insn->code);
+
+ if (opcode == BPF_CALL) {
+ if (BPF_SRC(insn->code) != BPF_K ||
+ insn->off != 0 ||
+ insn->src_reg != BPF_REG_0 ||
+ insn->dst_reg != BPF_REG_0) {
+ verbose("BPF_CALL uses reserved fields\n");
+ return -EINVAL;
+ }
+
+ _(check_call(env, insn->imm));
+
+ } else if (opcode == BPF_JA) {
+ if (BPF_SRC(insn->code) != BPF_K ||
+ insn->imm != 0 ||
+ insn->src_reg != BPF_REG_0 ||
+ insn->dst_reg != BPF_REG_0) {
+ verbose("BPF_JA uses reserved fields\n");
+ return -EINVAL;
+ }
+
+ insn_idx += insn->off + 1;
+ continue;
+
+ } else if (opcode == BPF_EXIT) {
+ if (BPF_SRC(insn->code) != BPF_K ||
+ insn->imm != 0 ||
+ insn->src_reg != BPF_REG_0 ||
+ insn->dst_reg != BPF_REG_0) {
+ verbose("BPF_EXIT uses reserved fields\n");
+ return -EINVAL;
+ }
+
+ /* eBPF calling convetion is such that R0 is used
+ * to return the value from eBPF program.
+ * Make sure that it's readable at this time
+ * of bpf_exit, which means that program wrote
+ * something into it earlier
+ */
+ _(check_reg_arg(regs, BPF_REG_0, SRC_OP));
+ insn_idx = pop_stack(env, &prev_insn_idx);
+ if (insn_idx < 0) {
+ break;
+ } else {
+ do_print_state = true;
+ continue;
+ }
+ } else {
+ _(check_cond_jmp_op(env, insn, &insn_idx));
+ }
+ } else if (class == BPF_LD) {
+ u8 mode = BPF_MODE(insn->code);
+
+ if (mode == BPF_ABS || mode == BPF_IND) {
+ _(check_ld_abs(env, insn));
+ } else if (mode == BPF_IMM) {
+ _(check_ld_imm(env, insn));
+ insn_idx++;
+ } else {
+ verbose("invalid BPF_LD mode\n");
+ return -EINVAL;
+ }
+ } else {
+ verbose("unknown insn class %d\n", class);
+ return -EINVAL;
+ }
+
+ insn_idx++;
+ }
+
+ return 0;
+}
+
/* look for pseudo eBPF instructions that access map FDs and
* replace them with actual map pointers
*/
@@ -665,9 +1723,10 @@ int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
if (ret < 0)
goto skip_full_check;
- /* ret = do_check(env); */
+ ret = do_check(env);
skip_full_check:
+ while (pop_stack(env, NULL) >= 0);
if (log_level && log_len >= log_size - 1) {
BUG_ON(log_len >= log_size);
--
1.7.9.5
^ permalink raw reply related
* [PATCH v5 net-next 15/29] bpf: verifier (add state prunning optimization)
From: Alexei Starovoitov @ 2014-08-24 20:21 UTC (permalink / raw)
To: David S. Miller
Cc: Ingo Molnar, Linus Torvalds, Andy Lutomirski, Steven Rostedt,
Daniel Borkmann, Chema Gonzalez, Eric Dumazet, Peter Zijlstra,
Brendan Gregg, Namhyung Kim, H. Peter Anvin, Andrew Morton,
Kees Cook, linux-api, netdev, linux-kernel
In-Reply-To: <1408911690-7598-1-git-send-email-ast@plumgrid.com>
since verifier walks all possible paths it's important to recognize
equivalent verifier states to speed up verification.
If one of the old states is more strict than the current state, it means
the current state doesn't need to be explored further, since verifier already
concluded that more strict state leads to valid bpf_exit.
Signed-off-by: Alexei Starovoitov <ast@plumgrid.com>
---
kernel/bpf/verifier.c | 134 +++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 134 insertions(+)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 14a0262b101c..49374066a5bd 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -220,6 +220,7 @@ struct verifier_env {
struct verifier_stack_elem *head; /* stack of verifier states to be processed */
int stack_size; /* number of states to be processed */
struct verifier_state cur_state; /* current verifier state */
+ struct verifier_state_list **branch_landing; /* search prunning optimization */
struct bpf_map *used_maps[MAX_USED_MAPS]; /* array of map's used by eBPF program */
u32 used_map_cnt; /* number of used maps */
};
@@ -1256,6 +1257,8 @@ enum {
BRANCH = 2,
};
+#define STATE_END ((struct verifier_state_list *) -1L)
+
#define PUSH_INT(I) \
do { \
if (cur_stack >= insn_cnt) { \
@@ -1297,6 +1300,9 @@ enum {
ret = -EINVAL; \
goto free_st; \
} \
+ if (E == BRANCH) \
+ /* mark branch target for state pruning */ \
+ env->branch_landing[w] = STATE_END; \
if (st[w] == 0) { \
/* tree-edge */ \
st[T] = DISCOVERED | E; \
@@ -1364,6 +1370,10 @@ peek_stack:
PUSH_INSN(t, t + 1, FALLTHROUGH);
PUSH_INSN(t, t + insns[t].off + 1, BRANCH);
}
+ /* tell verifier to check for equivalent verifier states
+ * after every call and jump
+ */
+ env->branch_landing[t + 1] = STATE_END;
} else {
/* all other non-branch instructions with single
* fall-through edge
@@ -1395,6 +1405,88 @@ free_st:
return ret;
}
+/* compare two verifier states
+ *
+ * all states stored in state_list are known to be valid, since
+ * verifier reached 'bpf_exit' instruction through them
+ *
+ * this function is called when verifier exploring different branches of
+ * execution popped from the state stack. If it sees an old state that has
+ * more strict register state and more strict stack state then this execution
+ * branch doesn't need to be explored further, since verifier already
+ * concluded that more strict state leads to valid finish.
+ *
+ * Therefore two states are equivalent if register state is more conservative
+ * and explored stack state is more conservative than the current one.
+ * Example:
+ * explored current
+ * (slot1=INV slot2=MISC) == (slot1=MISC slot2=MISC)
+ * (slot1=MISC slot2=MISC) != (slot1=INV slot2=MISC)
+ *
+ * In other words if current stack state (one being explored) has more
+ * valid slots than old one that already passed validation, it means
+ * the verifier can stop exploring and conclude that current state is valid too
+ *
+ * Similarly with registers. If explored state has register type as invalid
+ * whereas register type in current state is meaningful, it means that
+ * the current state will reach 'bpf_exit' instruction safely
+ */
+static bool states_equal(struct verifier_state *old, struct verifier_state *cur)
+{
+ int i;
+
+ for (i = 0; i < MAX_BPF_REG; i++) {
+ if (memcmp(&old->regs[i], &cur->regs[i],
+ sizeof(old->regs[0])) != 0) {
+ if (old->regs[i].type == NOT_INIT ||
+ old->regs[i].type == UNKNOWN_VALUE)
+ continue;
+ return false;
+ }
+ }
+
+ for (i = 0; i < MAX_BPF_STACK; i++) {
+ if (memcmp(&old->stack[i], &cur->stack[i],
+ sizeof(old->stack[0])) != 0) {
+ if (old->stack[i].stype == STACK_INVALID)
+ continue;
+ return false;
+ }
+ }
+ return true;
+}
+
+static int is_state_visited(struct verifier_env *env, int insn_idx)
+{
+ struct verifier_state_list *new_sl;
+ struct verifier_state_list *sl;
+
+ sl = env->branch_landing[insn_idx];
+ if (!sl)
+ /* no branch jump to this insn, ignore it */
+ return 0;
+
+ while (sl != STATE_END) {
+ if (states_equal(&sl->state, &env->cur_state))
+ /* reached equivalent register/stack state,
+ * prune the search
+ */
+ return 1;
+ sl = sl->next;
+ }
+ new_sl = kmalloc(sizeof(struct verifier_state_list), GFP_KERNEL);
+
+ if (!new_sl)
+ /* ignore ENOMEM, it doesn't affect correctness */
+ return 0;
+
+ /* add new state to the head of linked list */
+ memcpy(&new_sl->state, &env->cur_state, sizeof(env->cur_state));
+ new_sl->next = env->branch_landing[insn_idx];
+ env->branch_landing[insn_idx] = new_sl;
+ return 0;
+}
+
static int do_check(struct verifier_env *env)
{
struct verifier_state *state = &env->cur_state;
@@ -1426,6 +1518,17 @@ static int do_check(struct verifier_env *env)
return -E2BIG;
}
+ if (is_state_visited(env, insn_idx)) {
+ if (log_level) {
+ if (do_print_state)
+ verbose("\nfrom %d to %d: safe\n",
+ prev_insn_idx, insn_idx);
+ else
+ verbose("%d: safe\n", insn_idx);
+ }
+ goto process_bpf_exit;
+ }
+
if (log_level && do_print_state) {
verbose("\nfrom %d to %d:", prev_insn_idx, insn_idx);
print_verifier_state(env);
@@ -1536,6 +1639,7 @@ static int do_check(struct verifier_env *env)
* something into it earlier
*/
_(check_reg_arg(regs, BPF_REG_0, SRC_OP));
+process_bpf_exit:
insn_idx = pop_stack(env, &prev_insn_idx);
if (insn_idx < 0) {
break;
@@ -1670,6 +1774,28 @@ static void convert_pseudo_ld_imm64(struct verifier_env *env)
insn->src_reg = 0;
}
+static void free_states(struct verifier_env *env)
+{
+ struct verifier_state_list *sl, *sln;
+ int i;
+
+ if (!env->branch_landing)
+ return;
+
+ for (i = 0; i < env->prog->len; i++) {
+ sl = env->branch_landing[i];
+
+ if (sl)
+ while (sl != STATE_END) {
+ sln = sl->next;
+ kfree(sl);
+ sl = sln;
+ }
+ }
+
+ kfree(env->branch_landing);
+}
+
int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
{
void __user *log_ubuf = NULL;
@@ -1719,6 +1845,13 @@ int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
if (ret < 0)
goto skip_full_check;
+ env->branch_landing = kcalloc(prog->len,
+ sizeof(struct verifier_state_list *),
+ GFP_KERNEL);
+ ret = -ENOMEM;
+ if (!env->branch_landing)
+ goto skip_full_check;
+
ret = check_cfg(env);
if (ret < 0)
goto skip_full_check;
@@ -1727,6 +1860,7 @@ int bpf_check(struct bpf_prog *prog, struct nlattr *tb[BPF_PROG_ATTR_MAX + 1])
skip_full_check:
while (pop_stack(env, NULL) >= 0);
+ free_states(env);
if (log_level && log_len >= log_size - 1) {
BUG_ON(log_len >= log_size);
--
1.7.9.5
^ permalink raw reply related
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).