Skip to contentSkip to conversation

implementation of eBPF maps

PATCH In review Alexei Starovoitov 3 participants 16 messages Nov 14, 2014 – Nov 18, 2014

Subsystems (5)
Networking Network drivers BPF BPF core +1 more subsystems
lore
Share & tools
lore

Alexei Starovoitov

author
#0 lore raw

v2 cover implementation of eBPF maps

Hi All,

v1->v2:
renamed flags for MAP_UPDATE_ELEM command to be more concise, clarified commit logs and improved comments in patches 1,3,7 per discussions with Daniel

Old v1 cover:

this set of patches adds implementation of HASH and ARRAY types of eBPF maps which were described in manpage in commit b4fc1a460f30("Merge branch 'bpf-next'")

The difference vs previous version of these patches from August:
- added 'flags' attribute to BPF_MAP_UPDATE_ELEM
- in HASH type implementation removed per-map kmem_cache.
I was doing kmem_cache_create() for every map to enable selective slub debugging to check for overflows and leaks. Now it's not needed, so just use normal kmalloc() for map elements.
- added ARRAY type which was mentioned in manpage, but wasn't public yet
- added map testsuite and removed temporary bits from test_stubs

Note, eBPF programs cannot be attached to events yet. It will come in the next set.

Alexei Starovoitov (7):
bpf: add 'flags' attribute to BPF_MAP_UPDATE_ELEM command
bpf: add hashtable type of eBPF maps
bpf: add array type of eBPF maps
bpf: fix BPF_MAP_LOOKUP_ELEM command return code
bpf: add a testsuite for eBPF maps
bpf: allow eBPF programs to use maps
bpf: remove test map scaffolding and user proper types

 include/linux/bpf.h         |    7 +-
 include/uapi/linux/bpf.h    |   13 +-
 kernel/bpf/Makefile         |    2 +-
 kernel/bpf/arraymap.c       |  151 ++++++++++++++++++
 kernel/bpf/hashtab.c        |  362 +++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/helpers.c        |   89 +++++++++++
 kernel/bpf/syscall.c        |    6 +-
 kernel/bpf/test_stub.c      |   56 ++-----
 samples/bpf/Makefile        |    3 +-
 samples/bpf/libbpf.c        |    3 +-
 samples/bpf/libbpf.h        |    2 +-
 samples/bpf/test_maps.c     |  291 ++++++++++++++++++++++++++++++++++
 samples/bpf/test_verifier.c |   14 +-
 13 files changed, 936 insertions(+), 63 deletions(-)
 create mode 100644 kernel/bpf/arraymap.c
 create mode 100644 kernel/bpf/hashtab.c
 create mode 100644 kernel/bpf/helpers.c
 create mode 100644 samples/bpf/test_maps.c
Signature · 1 line
1.7.9.5
author
#1 lore raw

PATCH v2 1/7 bpf: add 'flags' attribute to BPF_MAP_UPDATE_ELEM command

the current meaning of BPF_MAP_UPDATE_ELEM syscall command is:
either update existing map element or create a new one. Initially the plan was to add a new command to handle the case of 'create new element if it didn't exist', but 'flags' style looks cleaner and overall diff is much smaller (more code reused), so add 'flags' attribute to BPF_MAP_UPDATE_ELEM command with the following meaning:
#define BPF_ANY 0 /* create new element or update existing */
#define BPF_NOEXIST 1 /* create new element if it didn't exist */
#define BPF_EXIST 2 /* update existing element */

bpf_update_elem(fd, key, value, BPF_NOEXIST) call can fail with EEXIST if element already exists.

bpf_update_elem(fd, key, value, BPF_EXIST) can fail with ENOENT if element doesn't exist.

Userspace will call it as:
int bpf_update_elem(int fd, void *key, void *value, __u64 flags)

{
    union bpf_attr attr = {
        .map_fd = fd,
        .key = ptr_to_u64(key),
        .value = ptr_to_u64(value),
        .flags = flags;
    };

    return bpf(BPF_MAP_UPDATE_ELEM, &attr, sizeof(attr));
}

First two bits of 'flags' are used to encode style of bpf_update_elem() command. Bits 2-63 are reserved for future use.

Signed-off-by Alexei Starovoitov <[email protected]>

---

patch 5 of this set includes tests of bpf_update_elem() with these flags

 include/linux/bpf.h      |    2 +-
 include/uapi/linux/bpf.h |    8 +++++++-
 kernel/bpf/syscall.c     |    4 ++--
 3 files changed, 10 insertions(+), 4 deletions(-)
include/linux/bpf.h +1 -1
index 3cf91754a957..51e9242e4803 100644
@@ -22,7 +22,7 @@ struct bpf_map_ops {
 
 	/* 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_update_elem)(struct bpf_map *map, void *key, void *value, u64 flags);
 	int (*map_delete_elem)(struct bpf_map *map, void *key);
 };
include/uapi/linux/bpf.h +7 -1
index d18316f9e9c4..3e9e1b77f29d 100644
@@ -82,7 +82,7 @@ enum bpf_cmd {
 
 	/* create or update key/value pair in a given map
 	 * err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size)
-	 * Using attr->map_fd, attr->key, attr->value
+	 * Using attr->map_fd, attr->key, attr->value, attr->flags
 	 * returns zero or negative error
 	 */
 	BPF_MAP_UPDATE_ELEM,

@@ -117,6 +117,11 @@ enum bpf_prog_type {
 	BPF_PROG_TYPE_UNSPEC,
 };
 
+/* flags for BPF_MAP_UPDATE_ELEM command */
+#define BPF_ANY		0 /* create new element or update existing */
+#define BPF_NOEXIST	1 /* create new element if it didn't exist */
+#define BPF_EXIST	2 /* update existing element */
+
 union bpf_attr {
 	struct { /* anonymous struct used by BPF_MAP_CREATE command */
 		__u32	map_type;	/* one of enum bpf_map_type */

@@ -132,6 +137,7 @@ union bpf_attr {
 			__aligned_u64 value;
 			__aligned_u64 next_key;
 		};
+		__u64		flags;
 	};
 
 	struct { /* anonymous struct used by BPF_PROG_LOAD command */
kernel/bpf/syscall.c +2 -2
index ba61c8c16032..c0d03bf317a2 100644
@@ -190,7 +190,7 @@ err_put:
 	return err;
 }
 
-#define BPF_MAP_UPDATE_ELEM_LAST_FIELD value
+#define BPF_MAP_UPDATE_ELEM_LAST_FIELD flags
 
 static int map_update_elem(union bpf_attr *attr)
 {

@@ -231,7 +231,7 @@ static int map_update_elem(union bpf_attr *attr)
 	 * 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);
+	err = map->ops->map_update_elem(map, key, value, attr->flags);
 	rcu_read_unlock();
 
 free_value:
Signature · 1 line
1.7.9.5
#2 lore raw

Re: [PATCH v2 net-next 1/7] bpf: add 'flags' attribute to BPF_MAP_UPDATE_ELEM command

Quoted 9 lines · Alexei Starovoitov

the current meaning of BPF_MAP_UPDATE_ELEM syscall command is:
either update existing map element or create a new one. Initially the plan was to add a new command to handle the case of 'create new element if it didn't exist', but 'flags' style looks cleaner and overall diff is much smaller (more code reused), so add 'flags' attribute to BPF_MAP_UPDATE_ELEM command with the following meaning:
#define BPF_ANY 0 /* create new element or update existing */
#define BPF_NOEXIST 1 /* create new element if it didn't exist */
#define BPF_EXIST 2 /* update existing element */

Would a cmpxchg-alike function be handy here?

Bye,
Hannes

author
#3 lore raw

Re: [PATCH v2 net-next 1/7] bpf: add 'flags' attribute to BPF_MAP_UPDATE_ELEM command

Quoted 11 lines · Hannes Frederic Sowa
Quoted 9 lines · Alexei Starovoitov

the current meaning of BPF_MAP_UPDATE_ELEM syscall command is:
either update existing map element or create a new one. Initially the plan was to add a new command to handle the case of 'create new element if it didn't exist', but 'flags' style looks cleaner and overall diff is much smaller (more code reused), so add 'flags' attribute to BPF_MAP_UPDATE_ELEM command with the following meaning:

 #define BPF_ANY      0 /* create new element or update existing */
 #define BPF_NOEXIST  1 /* create new element if it didn't exist */
 #define BPF_EXIST    2 /* update existing element */
Quoted 1 line

Would a cmpxchg-alike function be handy here?

you mean cmpxchg command in addition to
update() command ?
May be... it will have an extra 'value' argument
(key, old_value, new_value)
I don't have a use case for it yet though.

#4 lore raw

Re: [PATCH v2 net-next 1/7] bpf: add 'flags' attribute to BPF_MAP_UPDATE_ELEM command

Quoted 13 lines · Alexei Starovoitov
Quoted 11 lines · Hannes Frederic Sowa
Quoted 9 lines · Alexei Starovoitov

the current meaning of BPF_MAP_UPDATE_ELEM syscall command is:
either update existing map element or create a new one. Initially the plan was to add a new command to handle the case of 'create new element if it didn't exist', but 'flags' style looks cleaner and overall diff is much smaller (more code reused), so add 'flags' attribute to BPF_MAP_UPDATE_ELEM command with the following meaning:

 #define BPF_ANY      0 /* create new element or update existing */
 #define BPF_NOEXIST  1 /* create new element if it didn't exist */
 #define BPF_EXIST    2 /* update existing element */
Quoted 7 lines
Quoted 1 line

Would a cmpxchg-alike function be handy here?

you mean cmpxchg command in addition to
update() command ?
May be... it will have an extra 'value' argument
(key, old_value, new_value)
I don't have a use case for it yet though.

I don't neither. ;)

I just wanted to bring this up before user space api might get public and the additional argument might make problems.

Bye,
Hannes

author
#5 lore raw

Re: [PATCH v2 net-next 1/7] bpf: add 'flags' attribute to BPF_MAP_UPDATE_ELEM command

Quoted 22 lines · Hannes Frederic Sowa
Quoted 13 lines · Alexei Starovoitov
Quoted 11 lines · Hannes Frederic Sowa
Quoted 9 lines · Alexei Starovoitov

the current meaning of BPF_MAP_UPDATE_ELEM syscall command is:
either update existing map element or create a new one. Initially the plan was to add a new command to handle the case of 'create new element if it didn't exist', but 'flags' style looks cleaner and overall diff is much smaller (more code reused), so add 'flags' attribute to BPF_MAP_UPDATE_ELEM command with the following meaning:

 #define BPF_ANY      0 /* create new element or update existing */
 #define BPF_NOEXIST  1 /* create new element if it didn't exist */
 #define BPF_EXIST    2 /* update existing element */
Quoted 7 lines
Quoted 1 line

Would a cmpxchg-alike function be handy here?

you mean cmpxchg command in addition to
update() command ?
May be... it will have an extra 'value' argument
(key, old_value, new_value)
I don't have a use case for it yet though.

Quoted 4 lines

I don't neither. ;)

I just wanted to bring this up before user space api might get public and the additional argument might make problems.

addition of cmpxchg command won't be a problem obviously. (just another 'new_value' field in existing struct inside bpf_attr union).

author
#6 lore raw

PATCH v2 2/7 bpf: add hashtable type of eBPF maps

In reply to Alexei Starovoitov

add new map type BPF_MAP_TYPE_HASH and its implementation

- maps are created/destroyed by userspace. Both userspace and eBPF programs can lookup/update/delete elements from the map

- eBPF programs can be called in_irq(), so use spin_lock_irqsave() mechanism for concurrent updates

- key/value are opaque range of bytes (aligned to 8 bytes)

- user space provides 3 configuration attributes via BPF syscall:
key_size, value_size, max_entries

- map takes care of allocating/freeing key/value pairs

- map_update_elem() must fail to insert new element when max_entries limit is reached to make sure that eBPF programs cannot exhaust memory

- map_update_elem() replaces elements in an atomic way

- optimized for speed of lookup() which can be called multiple times from eBPF program which itself is triggered by high volume of events . in the future JIT compiler may recognize lookup() call and optimize it further, since key_size is constant for life of eBPF program

Signed-off-by Alexei Starovoitov <[email protected]>
---
 include/uapi/linux/bpf.h |    1 +
 kernel/bpf/Makefile      |    2 +-
 kernel/bpf/hashtab.c     |  362 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 364 insertions(+), 1 deletion(-)
 create mode 100644 kernel/bpf/hashtab.c
include/uapi/linux/bpf.h +1 -0
index 3e9e1b77f29d..03a01fd609aa 100644
@@ -111,6 +111,7 @@ enum bpf_cmd {
 
 enum bpf_map_type {
 	BPF_MAP_TYPE_UNSPEC,
+	BPF_MAP_TYPE_HASH,
 };
 
 enum bpf_prog_type {
kernel/bpf/Makefile +1 -1
index 0daf7f6ae7df..2c0ec7f9da78 100644
@@ -1,5 +1,5 @@
 obj-y := core.o
-obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o
+obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o hashtab.o
 ifdef CONFIG_TEST_BPF
 obj-$(CONFIG_BPF_SYSCALL) += test_stub.o
 endif
kernel/bpf/hashtab.c new file +362 -0

362 lines not on this page · raw message

Signature · 1 line
1.7.9.5
author
#7 lore raw

PATCH v2 3/7 bpf: add array type of eBPF maps

In reply to Alexei Starovoitov

add new map type BPF_MAP_TYPE_ARRAY and its implementation

- optimized for fastest possible lookup()
. in the future verifier/JIT may recognize lookup() with constant key
and optimize it into constant pointer. Can optimize non-constant key into direct pointer arithmetic as well, since pointers and value_size are constant for the life of the eBPF program. In other words array_map_lookup_elem() may be 'inlined' by verifier/JIT while preserving concurrent access to this map from user space

- two main use cases for array type:
. 'global' eBPF variables: array of 1 element with key=0 and value is a
collection of 'global' variables which programs can use to keep the state between events
. aggregation of tracing events into fixed set of buckets

- all array elements pre-allocated and zero initialized at init time

- key as an index in array and can only be 4 byte

- map_delete_elem() returns EINVAL, since elements cannot be deleted

- map_update_elem() replaces elements in an non-atomic way (for atomic updates hashtable type should be used instead)

Signed-off-by Alexei Starovoitov <[email protected]>

---

Note, from eBPF program and from user space, all map types are accessed through the same API.

Example of using array type for 'global' variables from eBPF program:

struct globals {
    u64 lat_ave;
    u64 lat_sum;
    u64 missed;
    u64 max_lat;
    int num_samples;
};

struct bpf_map_def SEC("maps") global_map = {
.type = BPF_MAP_TYPE_ARRAY,
.key_size = sizeof(int),
.value_size = sizeof(struct globals),
.max_entries = 1,
};

int bpf_prog(struct bpf_context *ctx)

{
    ...
    int ind = 0;
    struct globals *g = bpf_map_lookup_elem(&global_map, &ind);
    if (!g)
            return 0;
    if (g->lat_ave == 0) {
            g->num_samples++;
            g->lat_sum += delta;
            if (g->num_samples >= 100) {
                    g->lat_ave = g->lat_sum / g->num_samples;
    ...

The future verifier/JIT optimization will replace bpf_map_lookup_elem() call inside eBPF program with const pointer to element value of key=0, so that eBPF program will have no penalty whatsoever to access such 'global' variables.
At the same time user space can access this 'globals' via common map API.

Full example of both kernel and user side follows in later patches.

The array map is like C array of structures. Nothing protects concurrent access. It's used in the cases where accuracy is not needed or when there is no concurrent access. To compute a histogram of events in tracing the array of integers is used. Every integer is a counter. Program increments it (may be without using xadd) and user space periodically reads it back. map_update_elem() is called by userspace once to initialize it if zero-init is not enough. Programs do lookup() and modify the values.
For array type update() method is used rarely, delete() is never used and get_next() is needed for completeness to browse maps through common map API.

 include/uapi/linux/bpf.h |    1 +
 kernel/bpf/Makefile      |    2 +-
 kernel/bpf/arraymap.c    |  151 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 153 insertions(+), 1 deletion(-)
 create mode 100644 kernel/bpf/arraymap.c
include/uapi/linux/bpf.h +1 -0
index 03a01fd609aa..0d662fe75df5 100644
@@ -112,6 +112,7 @@ enum bpf_cmd {
 enum bpf_map_type {
 	BPF_MAP_TYPE_UNSPEC,
 	BPF_MAP_TYPE_HASH,
+	BPF_MAP_TYPE_ARRAY,
 };
 
 enum bpf_prog_type {
kernel/bpf/Makefile +1 -1
index 2c0ec7f9da78..72ec98ba2d42 100644
@@ -1,5 +1,5 @@
 obj-y := core.o
-obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o hashtab.o
+obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o hashtab.o arraymap.o
 ifdef CONFIG_TEST_BPF
 obj-$(CONFIG_BPF_SYSCALL) += test_stub.o
 endif
kernel/bpf/arraymap.c new file +151 -0

151 lines not on this page · raw message

Signature · 1 line
1.7.9.5
author
#8 lore raw

PATCH v2 4/7 bpf: fix BPF_MAP_LOOKUP_ELEM command return code

In reply to Alexei Starovoitov

fix errno of BPF_MAP_LOOKUP_ELEM command as bpf manpage described it in commit b4fc1a460f30("Merge branch 'bpf-next'"):
-----
BPF_MAP_LOOKUP_ELEM

    int bpf_lookup_elem(int fd, void *key, void *value)
    {
        union bpf_attr attr = {
            .map_fd = fd,
            .key = ptr_to_u64(key),
            .value = ptr_to_u64(value),
        };

        return bpf(BPF_MAP_LOOKUP_ELEM, &attr, sizeof(attr));
    }
    bpf() syscall looks up an element with given key in  a  map  fd.
    If  element  is found it returns zero and stores element's value
    into value.  If element is not found  it  returns  -1  and  sets
    errno to ENOENT.

and further down in manpage:

ENOENT For BPF_MAP_LOOKUP_ELEM or BPF_MAP_DELETE_ELEM, indicates that
element with given key was not found.
-----

In general all BPF commands return ENOENT when map element is not found (including BPF_MAP_GET_NEXT_KEY and BPF_MAP_UPDATE_ELEM with
flags == BPF_MAP_UPDATE_ONLY)

Subsequent patch adds a testsuite to check return values for all of these combinations.

Signed-off-by Alexei Starovoitov <[email protected]>

---

I don't think this patch is needed for 'net', since 'net' has syscall shell only. Actual map types and their implementations are being introduced by this set of patches.

 kernel/bpf/syscall.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/syscall.c +1 -1
index c0d03bf317a2..088ac0b1b106 100644
@@ -169,7 +169,7 @@ static int map_lookup_elem(union bpf_attr *attr)
 	if (copy_from_user(key, ukey, map->key_size) != 0)
 		goto free_key;
 
-	err = -ESRCH;
+	err = -ENOENT;
 	rcu_read_lock();
 	value = map->ops->map_lookup_elem(map, key);
 	if (!value)
Signature · 1 line
1.7.9.5
author
#9 lore raw

PATCH v2 5/7 bpf: add a testsuite for eBPF maps

In reply to Alexei Starovoitov

. check error conditions and sanity of hash and array map APIs
. check large maps (that kernel gracefully switches to vmalloc from kmalloc) . check multi-process parallel access and stress test

Signed-off-by Alexei Starovoitov <[email protected]>

---
Eventually it can be moved tools/testing/selftests/bpf/, but for now keep it in samples/bpf/, since that's where all subsequent samples are coming to.

 samples/bpf/Makefile    |    3 +-
 samples/bpf/libbpf.c    |    3 +-
 samples/bpf/libbpf.h    |    2 +-
 samples/bpf/test_maps.c |  291 +++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 296 insertions(+), 3 deletions(-)
 create mode 100644 samples/bpf/test_maps.c
samples/bpf/Makefile +2 -1
index 634391797856..0718d9ce4619 100644
@@ -2,9 +2,10 @@
 obj- := dummy.o
 
 # List of programs to build
-hostprogs-y := test_verifier
+hostprogs-y := test_verifier test_maps
 
 test_verifier-objs := test_verifier.o libbpf.o
+test_maps-objs := test_maps.o libbpf.o
 
 # Tell kbuild to always build the programs
 always := $(hostprogs-y)
samples/bpf/libbpf.c +2 -1
index ff6504420738..17bb520eb57f 100644
@@ -27,12 +27,13 @@ int bpf_create_map(enum bpf_map_type map_type, int key_size, int value_size,
 	return syscall(__NR_bpf, BPF_MAP_CREATE, &attr, sizeof(attr));
 }
 
-int bpf_update_elem(int fd, void *key, void *value)
+int bpf_update_elem(int fd, void *key, void *value, unsigned long long flags)
 {
 	union bpf_attr attr = {
 		.map_fd = fd,
 		.key = ptr_to_u64(key),
 		.value = ptr_to_u64(value),
+		.flags = flags,
 	};
 
 	return syscall(__NR_bpf, BPF_MAP_UPDATE_ELEM, &attr, sizeof(attr));
samples/bpf/libbpf.h +1 -1
index 8a31babeca5d..f8678e5f48bf 100644
@@ -6,7 +6,7 @@ struct bpf_insn;
 
 int bpf_create_map(enum bpf_map_type map_type, int key_size, int value_size,
 		   int max_entries);
-int bpf_update_elem(int fd, void *key, void *value);
+int bpf_update_elem(int fd, void *key, void *value, unsigned long long flags);
 int bpf_lookup_elem(int fd, void *key, void *value);
 int bpf_delete_elem(int fd, void *key);
 int bpf_get_next_key(int fd, void *key, void *next_key);
samples/bpf/test_maps.c new file +291 -0

291 lines not on this page · raw message

Signature · 1 line
1.7.9.5
author
#10 lore raw

PATCH v2 6/7 bpf: allow eBPF programs to use maps

In reply to Alexei Starovoitov

expose bpf_map_lookup_elem(), bpf_map_update_elem(), bpf_map_delete_elem() map accessors to eBPF programs

Signed-off-by Alexei Starovoitov <[email protected]>

---
Note, these helpers are exposed as '.gpl_only = false', so non-GPL eBPF programs can use them. That was requested by AndyL and DavidL before.

 include/linux/bpf.h      |    5 +++
 include/uapi/linux/bpf.h |    3 ++
 kernel/bpf/Makefile      |    2 +-
 kernel/bpf/helpers.c     |   89 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 98 insertions(+), 1 deletion(-)
 create mode 100644 kernel/bpf/helpers.c
include/linux/bpf.h +5 -0
index 51e9242e4803..75e94eaa228b 100644
@@ -133,4 +133,9 @@ struct bpf_prog *bpf_prog_get(u32 ufd);
 /* verify correctness of eBPF program */
 int bpf_check(struct bpf_prog *fp, union bpf_attr *attr);
 
+/* verifier prototypes for helper functions called from eBPF programs */
+extern struct bpf_func_proto bpf_map_lookup_elem_proto;
+extern struct bpf_func_proto bpf_map_update_elem_proto;
+extern struct bpf_func_proto bpf_map_delete_elem_proto;
+
 #endif /* _LINUX_BPF_H */
include/uapi/linux/bpf.h +3 -0
index 0d662fe75df5..4a3d0f84f178 100644
@@ -158,6 +158,9 @@ union bpf_attr {
  */
 enum bpf_func_id {
 	BPF_FUNC_unspec,
+	BPF_FUNC_map_lookup_elem, /* void *map_lookup_elem(&map, &key) */
+	BPF_FUNC_map_update_elem, /* int map_update_elem(&map, &key, &value, flags) */
+	BPF_FUNC_map_delete_elem, /* int map_delete_elem(&map, &key) */
 	__BPF_FUNC_MAX_ID,
 };
kernel/bpf/Makefile +1 -1
index 72ec98ba2d42..a5ae60f0b0a2 100644
@@ -1,5 +1,5 @@
 obj-y := core.o
-obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o hashtab.o arraymap.o
+obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o hashtab.o arraymap.o helpers.o
 ifdef CONFIG_TEST_BPF
 obj-$(CONFIG_BPF_SYSCALL) += test_stub.o
 endif
kernel/bpf/helpers.c new file +89 -0

89 lines not on this page · raw message

Signature · 1 line
1.7.9.5
maintainer
#11 lore raw

Re: [PATCH v2 net-next 6/7] bpf: allow eBPF programs to use maps

From: Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/[email protected]>
Date: Thu, 13 Nov 2014 17:36:49 -0800

Quoted 9 lines
kernel/bpf/helpers.c new file +9 -0
+static u64 bpf_map_lookup_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5)
+{
+	/* verifier checked that R1 contains a valid pointer to bpf_map
+	 * and R2 points to a program stack and map->key_size bytes were
+	 * initialized
+	 */
+	struct bpf_map *map = (struct bpf_map *) (unsigned long) r1;
+	void *key = (void *) (unsigned long) r2;
+	void *value;

kernel/bpf/helpers.c line 42

Quoted 10 lines
kernel/bpf/helpers.c new file +10 -0
+
+	WARN_ON_ONCE(!rcu_read_lock_held());
+
+	value = map->ops->map_lookup_elem(map, key);
+
+	/* lookup() returns either pointer to element value or NULL
+	 * which is the meaning of PTR_TO_MAP_VALUE_OR_NULL type
+	 */
+	return (unsigned long) value;
+}

You should translate this into a true boolean '1' or '0' value so that kernel pointers don't propagate to the user or his eBPF programs.

author
#12 lore raw

Re: [PATCH v2 net-next 6/7] bpf: allow eBPF programs to use maps

Quoted 17 lines · David Miller

From: Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/[email protected]>
Date: Thu, 13 Nov 2014 17:36:49 -0800

Quoted 14 lines
kernel/bpf/helpers.c new file +14 -0
+static u64 bpf_map_lookup_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5)
+{
+     /* verifier checked that R1 contains a valid pointer to bpf_map
+      * and R2 points to a program stack and map->key_size bytes were
+      * initialized
+      */
+     struct bpf_map *map = (struct bpf_map *) (unsigned long) r1;
+     void *key = (void *) (unsigned long) r2;
+     void *value;
+
+     WARN_ON_ONCE(!rcu_read_lock_held());
+
+     value = map->ops->map_lookup_elem(map, key);
+
Quoted 8 lines

kernel/bpf/helpers.c line 42

Quoted 5 lines
kernel/bpf/helpers.c new file +5 -0
+     /* lookup() returns either pointer to element value or NULL
+      * which is the meaning of PTR_TO_MAP_VALUE_OR_NULL type
+      */
+     return (unsigned long) value;
+}

You should translate this into a true boolean '1' or '0' value so that kernel pointers don't propagate to the user or his eBPF programs.

that won't work. eBPF programs have to see all sorts of kernel pointers. In this case it's a pointer to map element value or NULL. There are pointers to stack, pointers to map root, pointers to context, etc. Programs can read pointers from other data structures. And in the case of tracing they can pretty much access any kernel memory in read only way. Just like 'perf probe' filters.
The requirement that _unprivileged_ programs should not be able to pass all these pointers back to user is well understood and was discussed in detail several month back. It's verifier that will prevent leaking of kernel addresses. Today, the whole thing is for root only. When the infra is ready for non-root I will add a pass to verifier, that will kick in only for unprivileged programs. Verifier already tracks all pointers and can prevent passing them to user. In this case verifier knows that register R0 after a call to bpf_map_lookup_elem() is
"either pointer to element value or NULL",
so it will prevent storing it into any memory or doing arithmetic on it, so that user space cannot see the pointer, whereas eBPF program can use
it to access map element value.

maintainer
#13 lore raw

Re: [PATCH v2 net-next 6/7] bpf: allow eBPF programs to use maps

From: Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/[email protected]>
Date: Sun, 16 Nov 2014 13:24:53 -0800

Quoted 5 lines

The requirement that _unprivileged_ programs should not be able to pass all these pointers back to user is well understood and was discussed in detail several month back. It's verifier that will prevent leaking of kernel addresses.

Ok, fair enough.

author
#14 lore raw

PATCH v2 7/7 bpf: remove test map scaffolding and user proper types

In reply to Alexei Starovoitov

proper types and function helpers are ready. Use them in verifier testsuite. Remove temporary stubs

Signed-off-by Alexei Starovoitov <[email protected]>
---
 kernel/bpf/test_stub.c      |   56 +++++++------------------------------------
 samples/bpf/test_verifier.c |   14 +++++------
 2 files changed, 16 insertions(+), 54 deletions(-)
kernel/bpf/test_stub.c +9 -47
index fcaddff4003e..0ceae1e6e8b5 100644
@@ -18,26 +18,18 @@ struct bpf_context {
 	u64 arg2;
 };
 
-static u64 test_func(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5)
-{
-	return 0;
-}
-
-static struct bpf_func_proto test_funcs[] = {
-	[BPF_FUNC_unspec] = {
-		.func = test_func,
-		.gpl_only = true,
-		.ret_type = RET_PTR_TO_MAP_VALUE_OR_NULL,
-		.arg1_type = ARG_CONST_MAP_PTR,
-		.arg2_type = ARG_PTR_TO_MAP_KEY,
-	},
-};
-
 static const struct bpf_func_proto *test_func_proto(enum bpf_func_id func_id)
 {
-	if (func_id < 0 || func_id >= ARRAY_SIZE(test_funcs))
+	switch (func_id) {
+	case BPF_FUNC_map_lookup_elem:
+		return &bpf_map_lookup_elem_proto;
+	case BPF_FUNC_map_update_elem:
+		return &bpf_map_update_elem_proto;
+	case BPF_FUNC_map_delete_elem:
+		return &bpf_map_delete_elem_proto;
+	default:
 		return NULL;
-	return &test_funcs[func_id];
+	}
 }
 
 static const struct bpf_context_access {

@@ -78,38 +70,8 @@ static struct bpf_prog_type_list tl_prog = {
 	.type = BPF_PROG_TYPE_UNSPEC,
 };
 
-static struct bpf_map *test_map_alloc(union bpf_attr *attr)
-{
-	struct bpf_map *map;
-
-	map = kzalloc(sizeof(*map), GFP_USER);
-	if (!map)
-		return ERR_PTR(-ENOMEM);
-
-	map->key_size = attr->key_size;
-	map->value_size = attr->value_size;
-	map->max_entries = attr->max_entries;
-	return map;
-}
-
-static void test_map_free(struct bpf_map *map)
-{
-	kfree(map);
-}
-
-static struct bpf_map_ops test_map_ops = {
-	.map_alloc = test_map_alloc,
-	.map_free = test_map_free,
-};
-
-static struct bpf_map_type_list tl_map = {
-	.ops = &test_map_ops,
-	.type = BPF_MAP_TYPE_UNSPEC,
-};
-
 static int __init register_test_ops(void)
 {
-	bpf_register_map_type(&tl_map);
 	bpf_register_prog_type(&tl_prog);
 	return 0;
 }
samples/bpf/test_verifier.c +7 -7
index 63402742345e..b96175e90363 100644
@@ -261,7 +261,7 @@ static struct bpf_test tests[] = {
 			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_unspec),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
 			BPF_EXIT_INSN(),
 		},
 		.fixup = {2},

@@ -417,7 +417,7 @@ static struct bpf_test tests[] = {
 			BPF_ALU64_REG(BPF_MOV, 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_unspec),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_delete_elem),
 			BPF_EXIT_INSN(),
 		},
 		.errstr = "fd 0 is not pointing to valid bpf_map",

@@ -430,7 +430,7 @@ static struct bpf_test tests[] = {
 			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_unspec),
+			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(),
 		},

@@ -445,7 +445,7 @@ static struct bpf_test tests[] = {
 			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_unspec),
+			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(),

@@ -461,7 +461,7 @@ static struct bpf_test tests[] = {
 			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_unspec),
+			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(),

@@ -548,7 +548,7 @@ static struct bpf_test tests[] = {
 			BPF_ST_MEM(BPF_DW, BPF_REG_2, -56, 0),
 			BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -56),
 			BPF_LD_MAP_FD(BPF_REG_1, 0),
-			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_unspec),
+			BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_delete_elem),
 			BPF_EXIT_INSN(),
 		},
 		.fixup = {24},

@@ -659,7 +659,7 @@ static int create_map(void)
 	long long key, value = 0;
 	int map_fd;
 
-	map_fd = bpf_create_map(BPF_MAP_TYPE_UNSPEC, sizeof(key), sizeof(value), 1024);
+	map_fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value), 1024);
 	if (map_fd < 0) {
 		printf("failed to create map '%s'\n", strerror(errno));
 	}
Signature · 1 line
1.7.9.5
maintainer
#15 lore raw
In reply to Alexei Starovoitov

From: Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/[email protected]>
Date: Thu, 13 Nov 2014 17:36:43 -0800

Quoted 19 lines

v1->v2:
renamed flags for MAP_UPDATE_ELEM command to be more concise, clarified commit logs and improved comments in patches 1,3,7 per discussions with Daniel

Old v1 cover:

this set of patches adds implementation of HASH and ARRAY types of eBPF maps which were described in manpage in commit b4fc1a460f30("Merge branch 'bpf-next'")

The difference vs previous version of these patches from August:
- added 'flags' attribute to BPF_MAP_UPDATE_ELEM
- in HASH type implementation removed per-map kmem_cache.
I was doing kmem_cache_create() for every map to enable selective slub debugging to check for overflows and leaks. Now it's not needed, so just use normal kmalloc() for map elements.
- added ARRAY type which was mentioned in manpage, but wasn't public yet
- added map testsuite and removed temporary bits from test_stubs

Quoted 2 lines

Note, eBPF programs cannot be attached to events yet. It will come in the next set.

Series applied, thanks Alexei.