bpf: introduce BPF_F_LOCK flag
Subsystems (4)
Alexei Starovoitov
maintainerPATCH v2 6/9 bpf: introduce BPF_F_LOCK flag
Introduce BPF_F_LOCK flag for map_lookup and map_update syscall commands and for map_update() helper function.
In all these cases take a lock of existing element (which was provided in BTF description) before copying (in or out) the rest of map value.
Implementation details that are part of uapi:
Array:
The array map takes the element lock for lookup/update.
Hash:
hash map also takes the lock for lookup/update and tries to avoid the bucket lock. If old element exists it takes the element lock and updates the element in place. If element doesn't exist it allocates new one and inserts into hash table while holding the bucket lock.
In rare case the hashmap has to take both the bucket lock and the element lock to update old value in place.
Cgroup local storage:
It is similar to array. update in place and lookup are done with lock taken.
--- include/linux/bpf.h | 2 ++ include/uapi/linux/bpf.h | 1 + kernel/bpf/arraymap.c | 24 ++++++++++++++-------- kernel/bpf/hashtab.c | 42 +++++++++++++++++++++++++++++++++++--- kernel/bpf/helpers.c | 18 ++++++++++++++++ kernel/bpf/local_storage.c | 14 ++++++++++++- kernel/bpf/syscall.c | 28 +++++++++++++++++++++++-- 7 files changed, 115 insertions(+), 14 deletions(-)
include/linux/bpf.h +2 -0
@@ -119,6 +119,8 @@ static inline void copy_map_value(struct bpf_map *map, void *dst, void *src)memcpy (dst, src, map->value_size); } } +void copy_map_value_locked (struct bpf_map *map,void *dst,void *src, +bool lock_src);struct bpf_offload_dev ;struct bpf_offloaded_map ;
include/uapi/linux/bpf.h +1 -0
@@ -266,6 +266,7 @@ enum bpf_attach_type {#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 */ +#define BPF_F_LOCK 4/* spin_lock-ed map_lookup/map_update */ /* flags for BPF_MAP_CREATE command */ #define BPF_F_NO_PREALLOC (1U << 0)
kernel/bpf/arraymap.c +16 -8
@@ -253,8 +253,9 @@ static int array_map_update_elem(struct bpf_map *map, void *key, void *value, { struct bpf_array *array = container_of(map, struct bpf_array, map);u32 index = *(u32 *)key; +char *val; -if (unlikely (map_flags >BPF_EXIST )) +if (unlikely (map_flags & ~(BPF_F_LOCK |BPF_EXIST |BPF_NOEXIST )))/* unknown flags */ return -EINVAL ;
@@ -262,18 +263,25 @@ static int array_map_update_elem(struct bpf_map *map, void *key, void *value,/* all elements were pre-allocated, cannot insert a new one */ return -E2BIG ; -if (unlikely (map_flags ==BPF_NOEXIST )) +if (unlikely (map_flags &BPF_NOEXIST ))/* all elements already exist */ return -EEXIST ; -if (array->map.map_type ==BPF_MAP_TYPE_PERCPU_ARRAY ) +if (unlikely ((map_flags &BPF_F_LOCK ) && + !map_value_has_spin_lock (map))) +return -EINVAL ; + +if (array->map.map_type ==BPF_MAP_TYPE_PERCPU_ARRAY ) {memcpy (this_cpu_ptr (array->pptrs[index & array->index_mask]), value, map->value_size); -else -copy_map_value (map, - array->value + - array->elem_size * (index & array->index_mask), - value); + }else { + val = array->value + + array->elem_size * (index & array->index_mask); +if (map_flags &BPF_F_LOCK ) +copy_map_value_locked (map, val, value, false); +else +copy_map_value (map, val, value); + }return 0 ; }
kernel/bpf/hashtab.c +39 -3
69 lines not on this page · raw message
kernel/bpf/helpers.c +18 -0
@@ -256,6 +256,24 @@ const struct bpf_func_proto bpf_spin_unlock_proto = { .arg1_type = ARG_PTR_TO_SPIN_LOCK, }; +void copy_map_value_locked (struct bpf_map *map,void *dst,void *src, +bool lock_src) +{ +#if defined(CONFIG_SMP ) +struct qspinlock *qlock; + +if (lock_src) + qlock = src + map->spin_lock_off; +else + qlock = dst + map->spin_lock_off; +queued_spin_lock (qlock); +#endif +copy_map_value (map, dst, src); +#if defined(CONFIG_SMP ) +queued_spin_unlock (qlock); +#endif +} +#ifdef CONFIG_CGROUPS BPF_CALL_0 (bpf_get_current_cgroup_id) {
kernel/bpf/local_storage.c +13 -1
@@ -131,7 +131,14 @@ static int cgroup_storage_update_elem(struct bpf_map *map, void *_key,struct bpf_cgroup_storage *storage;struct bpf_storage_buffer *new; -if (flags !=BPF_ANY && flags !=BPF_EXIST ) +if (unlikely (flags & ~(BPF_F_LOCK |BPF_EXIST |BPF_NOEXIST ))) +return -EINVAL ; + +if (unlikely (flags &BPF_NOEXIST )) +return -EINVAL ; + +if (unlikely ((flags &BPF_F_LOCK ) && + !map_value_has_spin_lock (map)))return -EINVAL ; storage = cgroup_storage_lookup((struct bpf_cgroup_storage_map *)map,
@@ -139,6 +146,11 @@ static int cgroup_storage_update_elem(struct bpf_map *map, void *_key,if (!storage)return -ENOENT ; +if (flags &BPF_F_LOCK ) { +copy_map_value_locked (map, storage->buf->data, value, false); +return 0 ; + } + new = kmalloc_node(sizeof(struct bpf_storage_buffer) + map->value_size, __GFP_ZERO | GFP_ATOMIC | __GFP_NOWARN,
kernel/bpf/syscall.c +26 -2
@@ -682,7 +682,7 @@ static void *__bpf_copy_key(void __user *ukey, u64 key_size) }/* last field in 'union bpf_attr' used by this command */ -#define BPF_MAP_LOOKUP_ELEM_LAST_FIELD value +#define BPF_MAP_LOOKUP_ELEM_LAST_FIELD flagsstatic int map_lookup_elem (union bpf_attr *attr) {
@@ -698,6 +698,9 @@ static int map_lookup_elem(union bpf_attr *attr)if (CHECK_ATTR (BPF_MAP_LOOKUP_ELEM ))return -EINVAL ; +if (attr->flags & ~BPF_F_LOCK ) +return -EINVAL ; + f =fdget (ufd); map =__bpf_map_get (f);if (IS_ERR (map))
@@ -708,6 +711,12 @@ static int map_lookup_elem(union bpf_attr *attr) goto err_put; } +if ((attr->flags &BPF_F_LOCK ) && + !map_value_has_spin_lock (map)) { + err = -EINVAL ; + goto err_put; + } + key =__bpf_copy_key (ukey, map->key_size);if (IS_ERR (key)) { err =PTR_ERR (key);
@@ -758,7 +767,16 @@ static int map_lookup_elem(union bpf_attr *attr) err = -ENOENT ; }else { err =0 ; -copy_map_value (map, value, ptr); +if (attr->flags &BPF_F_LOCK ) { +/* lock 'ptr' elem and copy +* everything but the lock +*/ +copy_map_value_locked (map, value, ptr, true); +/* mask lock, since value was kmalloced */ +check_and_init_map_lock (map, value); + }else { +copy_map_value (map, value, ptr); + } }rcu_read_unlock (); }
@@ -818,6 +836,12 @@ static int map_update_elem(union bpf_attr *attr) goto err_put; } +if ((attr->flags &BPF_F_LOCK ) && + !map_value_has_spin_lock (map)) { + err = -EINVAL ; + goto err_put; + } + key =__bpf_copy_key (ukey, map->key_size);if (IS_ERR (key)) { err =PTR_ERR (key);
Signature · 1 line
2.17.1
Quoted 42 lines · Alexei Starovoitov
Introduce
BPF_F_LOCKflag formap_lookupandmap_updatesyscall commands and formap_update()helper function.
In all these cases take a lock of existing element (which was provided in BTF description) before copying (in or out) the rest of map value.Implementation details that are part of uapi:
Array:
The array map takes the element lock for lookup/update.Hash:
hash map also takes the lock for lookup/update and tries to avoid the bucket lock. If old element exists it takes the element lock and updates the element in place. If element doesn't exist it allocates new one and inserts into hash table while holding the bucket lock.
In rare case the hashmap has to take both the bucket lock and the element lock to update old value in place.Cgroup local storage:
It is similar to array. update in place and lookup are done with lock taken.Signed-off-by Alexei Starovoitov <[email protected]>kernel/bpf/hashtab.c +2
-2@@ -809,11 +809,11 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,static int check_flags (struct bpf_htab *htab,struct htab_elem *l_old,u64 map_flags) { -if (l_old && map_flags ==BPF_NOEXIST ) +if (l_old && (map_flags & ~BPF_F_LOCK ) ==BPF_NOEXIST )/* elem already exists */ return -EEXIST ; -if (!l_old && map_flags ==BPF_EXIST ) +if (!l_old && (map_flags & ~BPF_F_LOCK ) ==BPF_EXIST )/* elem doesn't exist, cannot update it */ return -ENOENT ;
kernel/bpf/hashtab.c static int htab_map_update_elem(struct bpf_map *map, void *key, void *value, · line 837
Quoted 7 lines
kernel/bpf/hashtab.c +1
-1@@ -832,7 +832,7 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value,u32 key_size, hash;int ret; -if (unlikely (map_flags >BPF_EXIST )) +if (unlikely (map_flags & ~(BPF_F_LOCK |BPF_EXIST |BPF_NOEXIST )))/* unknown flags */ return -EINVAL ;
Perhaps we should check for:
hweight(map_flags & (BPF_EXIST | BPF_NOEXIST)) < 2
right now this > BPF_EXIST is a little hacky, as it depends on the fact, that BPF_EXIST is 2.. If I read the code correctly BPF_EXIST | BPF_NOEXIST will be treated as BPF_NOEXIST. Not sure that matters.
Quoted 56 lines
kernel/bpf/hashtab.c +36
-0@@ -845,6 +845,28 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value, b =__select_bucket (htab, hash); head = &b->head; +if (unlikely (map_flags &BPF_F_LOCK )) { +if (unlikely (!map_value_has_spin_lock (map))) +return -EINVAL ; +/* find an element without taking the bucket lock */ + l_old =lookup_nulls_elem_raw (head, hash, key, key_size, + htab->n_buckets); + ret =check_flags (htab, l_old, map_flags); +if (ret) +return ret; +if (l_old) { +/* grab the element lock and update value in place */ +copy_map_value_locked (map, + l_old->key +round_up (key_size,8 ), + value, false); +return 0 ; + } +/* fall through, grab the bucket lock and lookup again. +* 99.9% chance that the element won't be found, +* but second lookup under lock has to be done. +*/ + } +/* bpf_map_update_elem() can be called in_irq() */ raw_spin_lock_irqsave (&b->lock, flags);@@ -854,6 +876,20 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value,if (ret) goto err; +if (unlikely (l_old && (map_flags &BPF_F_LOCK ))) { +/* first lookup without the bucket lock didn't find the element, +* but second lookup with the bucket lock found it. +* This case is highly unlikely, but has to be dealt with: +* grab the element lock in addition to the bucket lock +* and update element in place +*/ +copy_map_value_locked (map, + l_old->key +round_up (key_size,8 ), + value, false); + ret =0 ; + goto err; + } + l_new =alloc_htab_elem (htab, key, value, key_size, hash, false, false, l_old);if (IS_ERR (l_new)) {kernel/bpf/local_storage.c +0
-0
kernel/bpf/local_storage.c static int cgroup_storage_update_elem(struct bpf_map *map, void *_key, · line 138
Quoted 9 lines
kernel/bpf/local_storage.c +5
-1@@ -131,7 +131,14 @@ static int cgroup_storage_update_elem(struct bpf_map *map, void *_key,struct bpf_cgroup_storage *storage;struct bpf_storage_buffer *new; -if (flags !=BPF_ANY && flags !=BPF_EXIST ) +if (unlikely (flags & ~(BPF_F_LOCK |BPF_EXIST |BPF_NOEXIST ))) +return -EINVAL ; + +if (unlikely (flags &BPF_NOEXIST )) +return -EINVAL ;
nit: for arrays we have a different return code with BPF_NOEXIST, but
here its both EINVAL, so perhaps just drop the BPF_NOEXIST from the mask?
Quoted 72 lines
kernel/bpf/local_storage.c +7
-0+if (unlikely ((flags &BPF_F_LOCK ) && + !map_value_has_spin_lock (map)))return -EINVAL ; storage = cgroup_storage_lookup((struct bpf_cgroup_storage_map *)map,@@ -139,6 +146,11 @@ static int cgroup_storage_update_elem(struct bpf_map *map, void *_key,if (!storage)return -ENOENT ; +if (flags &BPF_F_LOCK ) { +copy_map_value_locked (map, storage->buf->data, value, false); +return 0 ; + } + new = kmalloc_node(sizeof(struct bpf_storage_buffer) + map->value_size, __GFP_ZERO | GFP_ATOMIC | __GFP_NOWARN,kernel/bpf/syscall.c +20
-2@@ -682,7 +682,7 @@ static void *__bpf_copy_key(void __user *ukey, u64 key_size) }/* last field in 'union bpf_attr' used by this command */ -#define BPF_MAP_LOOKUP_ELEM_LAST_FIELD value +#define BPF_MAP_LOOKUP_ELEM_LAST_FIELD flagsstatic int map_lookup_elem (union bpf_attr *attr) {@@ -698,6 +698,9 @@ static int map_lookup_elem(union bpf_attr *attr)if (CHECK_ATTR (BPF_MAP_LOOKUP_ELEM ))return -EINVAL ; +if (attr->flags & ~BPF_F_LOCK ) +return -EINVAL ; + f =fdget (ufd); map =__bpf_map_get (f);if (IS_ERR (map))@@ -708,6 +711,12 @@ static int map_lookup_elem(union bpf_attr *attr) goto err_put; } +if ((attr->flags &BPF_F_LOCK ) && + !map_value_has_spin_lock (map)) { + err = -EINVAL ; + goto err_put; + } + key =__bpf_copy_key (ukey, map->key_size);if (IS_ERR (key)) { err =PTR_ERR (key);@@ -758,7 +767,16 @@ static int map_lookup_elem(union bpf_attr *attr) err = -ENOENT ; }else { err =0 ; -copy_map_value (map, value, ptr); +if (attr->flags &BPF_F_LOCK ) { +/* lock 'ptr' elem and copy +* everything but the lock +*/ +copy_map_value_locked (map, value, ptr, true); +/* mask lock, since value was kmalloced */ +check_and_init_map_lock (map, value); + }else { +copy_map_value (map, value, ptr); + } }rcu_read_unlock (); }
kernel/bpf/syscall.c static int map_update_elem(union bpf_attr *attr) · line 840
Quoted 5 lines
kernel/bpf/syscall.c +2
-0@@ -818,6 +836,12 @@ static int map_update_elem(union bpf_attr *attr) goto err_put; } +if ((attr->flags &BPF_F_LOCK ) && + !map_value_has_spin_lock (map)) {
nit: do we need this check in syscall.c for update? Just wondering.
Quoted 7 lines
kernel/bpf/syscall.c +4
-0+ err = -EINVAL ; + goto err_put; + } + key =__bpf_copy_key (ukey, map->key_size);if (IS_ERR (key)) { err =PTR_ERR (key);
Quoted 46 lines · Jakub Kicinski
Quoted 45 lines · Alexei Starovoitov
Introduce
BPF_F_LOCKflag formap_lookupandmap_updatesyscall commands and formap_update()helper function.
In all these cases take a lock of existing element (which was provided in BTF description) before copying (in or out) the rest of map value.Implementation details that are part of uapi:
Array:
The array map takes the element lock for lookup/update.Hash:
hash map also takes the lock for lookup/update and tries to avoid the bucket lock. If old element exists it takes the element lock and updates the element in place. If element doesn't exist it allocates new one and inserts into hash table while holding the bucket lock.
In rare case the hashmap has to take both the bucket lock and the element lock to update old value in place.Cgroup local storage:
It is similar to array. update in place and lookup are done with lock taken.Signed-off-by Alexei Starovoitov <[email protected]>kernel/bpf/hashtab.c +2
-2@@ -809,11 +809,11 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,static int check_flags (struct bpf_htab *htab,struct htab_elem *l_old,u64 map_flags) { -if (l_old && map_flags ==BPF_NOEXIST ) +if (l_old && (map_flags & ~BPF_F_LOCK ) ==BPF_NOEXIST )/* elem already exists */ return -EEXIST ; -if (!l_old && map_flags ==BPF_EXIST ) +if (!l_old && (map_flags & ~BPF_F_LOCK ) ==BPF_EXIST )/* elem doesn't exist, cannot update it */ return -ENOENT ;@@ -832,7 +832,7 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value,u32 key_size, hash;int ret;
Quoted 8 lines
kernel/bpf/hashtab.c static int htab_map_update_elem(struct bpf_map *map, void *key, void *value, · line 837
Quoted 4 lines
kernel/bpf/hashtab.c +1
-1-if (unlikely (map_flags >BPF_EXIST )) +if (unlikely (map_flags & ~(BPF_F_LOCK |BPF_EXIST |BPF_NOEXIST )))/* unknown flags */ return -EINVAL ;Perhaps we should check for:
hweight(map_flags & (BPF_EXIST | BPF_NOEXIST))< 2
hweight in critical path is imo too slow.
Quoted 3 lines
right now this >
BPF_EXISTis a little hacky, as it depends on the fact, thatBPF_EXISTis 2.. If I read the code correctlyBPF_EXIST|BPF_NOEXISTwill be treated asBPF_NOEXIST. Not sure that matters.
#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 */ #define BPF_F_LOCK 4 /* spin_lock-ed map_lookup/map_update */
for all other flags we just 'or' them together and do flag & ~(FLAG1 | FLAG2 | ..)
so it's easy to add new flags later.
Here I'm only skipping BPF_ANY from this practice because it's zero.
Quoted 8 lines
Quoted 8 lines
kernel/bpf/local_storage.c +0
-0@@ -131,7 +131,14 @@ static int cgroup_storage_update_elem(struct bpf_map *map, void *_key,struct bpf_cgroup_storage *storage;struct bpf_storage_buffer *new;
Quoted 10 lines
kernel/bpf/local_storage.c static int cgroup_storage_update_elem(struct bpf_map *map, void *_key, · line 138
Quoted 6 lines
kernel/bpf/local_storage.c +5
-1-if (flags !=BPF_ANY && flags !=BPF_EXIST ) +if (unlikely (flags & ~(BPF_F_LOCK |BPF_EXIST |BPF_NOEXIST ))) +return -EINVAL ; + +if (unlikely (flags &BPF_NOEXIST )) +return -EINVAL ;nit: for arrays we have a different return code with
BPF_NOEXIST, but
here its both EINVAL, so perhaps just drop theBPF_NOEXISTfrom the mask?
I very much prefer compiler to do such optimizations. First line is doing:
flag & ~(FLAG1 | FLAG2 | ..)
like in all other places.
And second check if (unlikely(flags & BPF_NOEXIST)) is specific to this helper.
Quoted 8 lines
kernel/bpf/local_storage.c static int map_update_elem(union bpf_attr *attr) · line 840
Quoted 6 lines
kernel/bpf/local_storage.c +2
-0@@ -818,6 +836,12 @@ static int map_update_elem(union bpf_attr *attr) goto err_put; } +if ((attr->flags &BPF_F_LOCK ) && + !map_value_has_spin_lock (map)) {nit: do we need this check in
syscall.cfor update? Just wondering.
yes. otherwise the flag will be nop for other map types (percpu, lru, etc)