* [PATCH V4 8/8] audit: initialize at subsystem time rather than device time
From: Richard Guy Briggs @ 2014-08-21 1:09 UTC (permalink / raw)
To: linux-audit, linux-kernel, containers, linux-api
Cc: Richard Guy Briggs, arozansk, eparis, sgrubb, ebiederm, serge
In-Reply-To: <cover.1408581429.git.rgb@redhat.com>
The audit subsystem should be initialized a bit earlier so that it is in place
in time for initial namespace serial number logging.
---
kernel/audit.c | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/kernel/audit.c b/kernel/audit.c
index 6d95d1c..aa99518 100644
--- a/kernel/audit.c
+++ b/kernel/audit.c
@@ -1186,7 +1186,7 @@ static int __init audit_init(void)
return 0;
}
-__initcall(audit_init);
+subsys_initcall(audit_init);
/* Process kernel command-line parameter at boot time. audit=0 or audit=1. */
static int __init audit_enable(char *str)
--
1.7.1
^ permalink raw reply related
* Re: [PATCH V4 0/8] namespaces: log namespaces per task
From: Aristeu Rozanski @ 2014-08-21 20:05 UTC (permalink / raw)
To: Richard Guy Briggs
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: <cover.1408581429.git.rgb-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org>
Hi Richard,
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? 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.
What you think? Sounds too crazy? :)
--
Aristeu
^ permalink raw reply
* Re: [PATCH V4 3/8] namespaces: expose ns instance serial numbers in proc
From: Andy Lutomirski @ 2014-08-21 21:13 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: <cd6cd0622ce677b639afae18a69ff79c72490bab.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:
>
> 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.
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.
--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
^ permalink raw reply
* 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
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