bpf: add lookup_and_delete_elem support to hashtab
Subsystems (4)
PATCH v2 1/1 bpf: add lookup_and_delete_elem support to hashtab
Extend the existing bpf_map_lookup_and_delete_elem() functionality to hashtab maps, in addition to stacks and queues.
Create a new hashtab bpf_map_ops function that does lookup and deletion of the element under the same bucket lock and add the created map_ops to bpf.h.
Add the appropriate test cases to 'maps' and 'lru_map' selftests accompanied with new test_progs.
---
v2: Add functionality for LRU/per-CPU, add test_progs tests.
--- include/linux/bpf.h | 2 + kernel/bpf/hashtab.c | 80 +++++ kernel/bpf/syscall.c | 14 +- .../bpf/prog_tests/lookup_and_delete.c | 283 ++++++++++++++++++ .../bpf/progs/test_lookup_and_delete.c | 26 ++ tools/testing/selftests/bpf/test_lru_map.c | 8 + tools/testing/selftests/bpf/test_maps.c | 19 +- 7 files changed, 430 insertions(+), 2 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c create mode 100644 tools/testing/selftests/bpf/progs/test_lookup_and_delete.c
include/linux/bpf.h +2 -0
@@ -67,6 +67,8 @@ struct bpf_map_ops {void *(*map_lookup_elem_sys_only)(struct bpf_map *map,void *key);int (*map_lookup_batch)(struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr); +int (*map_lookup_and_delete_elem)(struct bpf_map *map,void *key, +void *value);int (*map_lookup_and_delete_batch)(struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr);
kernel/bpf/hashtab.c +80 -0
110 lines not on this page · raw message
kernel/bpf/syscall.c +13 -1
@@ -1495,7 +1495,7 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr) goto err_put; } - value_size = map->value_size; + value_size =bpf_map_value_size (map); err = -ENOMEM ; value =kmalloc (value_size,GFP_USER | __GFP_NOWARN);
@@ -1505,6 +1505,18 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr)if (map->map_type ==BPF_MAP_TYPE_QUEUE || map->map_type ==BPF_MAP_TYPE_STACK ) { err = map->ops->map_pop_elem (map, value); + }else if (map->map_type ==BPF_MAP_TYPE_HASH || + map->map_type ==BPF_MAP_TYPE_PERCPU_HASH || + map->map_type ==BPF_MAP_TYPE_LRU_HASH || + map->map_type ==BPF_MAP_TYPE_LRU_PERCPU_HASH ) { +if (!bpf_map_is_dev_bound (map)) { +bpf_disable_instrumentation (); +rcu_read_lock (); + err = map->ops->map_lookup_and_delete_elem (map, key, value); +rcu_read_unlock (); +bpf_enable_instrumentation (); +maybe_wait_bpf_programs (map); + } }else { err = -ENOTSUPP ; }
tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c new file +283 -0
283 lines not on this page · raw message
tools/testing/selftests/bpf/progs/test_lookup_and_delete.c new file +26 -0
@@ -0,0 +1,26 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> + +__u32 set_pid; +__u64 set_key; +__u64 set_value; + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __uint(max_entries, 2); + __type(key, __u64); + __type(value, __u64); +} hash_map SEC(".maps"); + +SEC("tp/syscalls/sys_enter_getpgid") +int bpf_lookup_and_delete_test (const void *ctx) +{ +if (set_pid ==bpf_get_current_pid_tgid () >>32 ) +bpf_map_update_elem (&hash_map, &set_key, &set_value,BPF_NOEXIST ); + +return 0 ; +} + +char _license[] SEC("license") = "GPL";
tools/testing/selftests/bpf/test_lru_map.c +8 -0
@@ -231,6 +231,14 @@ static void test_lru_sanity0(int map_type, int map_flags)assert (bpf_map_lookup_elem (lru_map_fd, &key, value) ==-1 && errno ==ENOENT ); +/* lookup elem key=3 and delete it, than check it doesn't exist */ + key =1 ; +assert (!bpf_map_lookup_and_delete_elem (lru_map_fd, &key, &value)); +assert (value[0 ] ==1234 ); + +/* remove the same element from the expected map */ +assert (!bpf_map_delete_elem (expected_map_fd, &key)); +assert (map_equal (lru_map_fd, expected_map_fd));close (expected_map_fd);
tools/testing/selftests/bpf/test_maps.c +18 -1
@@ -65,6 +65,13 @@ static void test_hashmap(unsigned int task, void *data)assert (bpf_map_lookup_elem (fd, &key, &value) ==0 && value ==1234 ); key =2 ; + value =1234 ; +/* Insert key=2 element. */ +assert (bpf_map_update_elem (fd, &key, &value,BPF_ANY ) ==0 ); + +/* Check that key=2 matches the value and delete it */ +assert (bpf_map_lookup_and_delete_elem (fd, &key, &value) ==0 && value ==1234 ); +/* Check that key=2 is not found. */ assert (bpf_map_lookup_elem (fd, &key, &value) ==-1 && errno ==ENOENT );
@@ -164,8 +171,18 @@ static void test_hashmap_percpu(unsigned int task, void *data) key =1 ;/* Insert key=1 element. */ -assert (!(expected_key_mask & key));assert (bpf_map_update_elem (fd, &key, value,BPF_ANY ) ==0 ); + +/* Lookup and delete elem key=1 and check value. */ +assert (bpf_map_lookup_and_delete_elem (fd, &key, value) ==0 && +bpf_percpu (value,0 ) ==100 ); + +for (i =0 ; i < nr_cpus; i++) +bpf_percpu (value, i) = i +100 ; + +/* Insert key=1 element which should not exist. */ +assert (!(expected_key_mask & key)); +assert (bpf_map_update_elem (fd, &key, value,BPF_NOEXIST ) ==0 ); expected_key_mask |= key;/* BPF_NOEXIST means add new element if it doesn't exist. */
Signature · 1 line
2.26.2
Quoted 73 lines · Denis Salopek
Extend the existing
bpf_map_lookup_and_delete_elem()functionality to hashtab maps, in addition to stacks and queues.
Create a new hashtabbpf_map_opsfunction that does lookup and deletion of the element under the same bucket lock and add the createdmap_opstobpf.h.
Add the appropriate test cases to 'maps' and 'lru_map' selftests accompanied with newtest_progs.Cc Juraj Vijtiuk <[email protected]>Cc Luka Oreskovic <[email protected]>Cc Luka Perkov <[email protected]>Signed-off-by Denis Salopek <[email protected]>---
v2: Add functionality for LRU/per-CPU, addtest_progstests.--- include/linux/bpf.h | 2 + kernel/bpf/hashtab.c | 80 +++++ kernel/bpf/syscall.c | 14 +- .../bpf/prog_tests/lookup_and_delete.c | 283 ++++++++++++++++++ .../bpf/progs/test_lookup_and_delete.c | 26 ++ tools/testing/selftests/bpf/test_lru_map.c | 8 + tools/testing/selftests/bpf/test_maps.c | 19 +- 7 files changed, 430 insertions(+), 2 deletions(-)create mode 100644
tools/testing/selftests/bpf/prog_tests/lookup_and_delete.ccreate mode 100644tools/testing/selftests/bpf/progs/test_lookup_and_delete.cinclude/linux/bpf.h +2
-0@@ -67,6 +67,8 @@ struct bpf_map_ops {void *(*map_lookup_elem_sys_only)(struct bpf_map *map,void *key);int (*map_lookup_batch)(struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr); +int (*map_lookup_and_delete_elem)(struct bpf_map *map,void *key, +void *value);int (*map_lookup_and_delete_batch)(struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr);kernel/bpf/hashtab.c +26
-0@@ -1401,6 +1401,82 @@ static void htab_map_seq_show_elem(struct bpf_map *map, void *key,rcu_read_unlock (); } +static int __htab_map_lookup_and_delete_elem (struct bpf_map *map,void *key, +void *value,bool is_lru_map, +bool is_percpu) +{ + struct bpf_htab *htab = container_of(map, struct bpf_htab, map); +u32 hash, key_size, value_size; +struct hlist_nulls_head *head; +int cpu, off =0 , ret; +struct htab_elem *l; +unsigned long flags; +void __percpu *pptr; +struct bucket *b; + + key_size = map->key_size; + value_size =round_up (map->value_size,8 ); + + hash =htab_map_hash (key, key_size, htab->hashrnd); + b =__select_bucket (htab, hash); + head = &b->head; + + ret =htab_lock_bucket (htab, b, hash, &flags); +if (ret) +return ret; + + l =lookup_elem_raw (head, hash, key, key_size); +if (l) {
kernel/bpf/hashtab.c static void htab_map_seq_show_elem(struct bpf_map *map, void *key, · line 1439
Quoted 10 lines
kernel/bpf/hashtab.c +10
-0+if (is_percpu) { + pptr =htab_elem_get_ptr (l, key_size); +for_each_possible_cpu (cpu) { +bpf_long_memcpy (value + off, +per_cpu_ptr (pptr, cpu), + value_size); + off += value_size; + } + }else { +copy_map_value (map, value, l->key +round_up (key_size,8 ));
For hashtab lookup elem, BPF_F_LOCK flag may be set by user, I think hashtab lookup_and_delete_elem should also support this flag, so user can ensure they always get a lock protected sane value.
We have the following libbpf APIs.
LIBBPF_API int bpf_map_lookup_elem(int fd, const void *key, void *value); LIBBPF_API int bpf_map_lookup_elem_flags(int fd, const void *key, void *value,
__u64 flags);
LIBBPF_API int bpf_map_lookup_and_delete_elem(int fd, const void *key,
void *value);Previously, bpf_map_lookup_and_delete_elem only supports queue/stack, which does not need flags as it does not support BPF_F_LOCK so we are fine.
Maybe similar to bpf_map_lookup_elem_flags() we add a bpf_map_lookup_and_delete_elem_flags()? Maybe libbpf v1.0 can consolidate into a better uniform api.
Quoted 93 lines
kernel/bpf/hashtab.c +44
-0+ } + +hlist_nulls_del_rcu (&l->hash_node); +if (!is_lru_map) +free_htab_elem (htab, l); + }else + ret = -ENOENT ; + +htab_unlock_bucket (htab, b, hash, flags); + +if (is_lru_map && l) +bpf_lru_push_free (&htab->lru, &l->lru_node); + +return ret; +} + +static int htab_map_lookup_and_delete_elem (struct bpf_map *map, +void *key,void *value) +{ +return __htab_map_lookup_and_delete_elem (map, key, value, false, false); +} + +static int htab_percpu_map_lookup_and_delete_elem (struct bpf_map *map, +void *key,void *value) +{ +return __htab_map_lookup_and_delete_elem (map, key, value, false, true); +} + +static int htab_lru_map_lookup_and_delete_elem (struct bpf_map *map,void *key, +void *value) +{ +return __htab_map_lookup_and_delete_elem (map, key, value, true, false); +} + +static int htab_lru_percpu_map_lookup_and_delete_elem (struct bpf_map *map, +void *key,void *value) +{ +return __htab_map_lookup_and_delete_elem (map, key, value, true, true); +} + static int __htab_map_lookup_and_delete_batch(struct bpf_map *map, const union bpf_attr *attr,@@ -1934,6 +2010,7 @@ const struct bpf_map_ops htab_map_ops = { .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_map_lookup_elem, + .map_lookup_and_delete_elem = htab_map_lookup_and_delete_elem, .map_update_elem = htab_map_update_elem, .map_delete_elem = htab_map_delete_elem, .map_gen_lookup = htab_map_gen_lookup,@@ -1954,6 +2031,7 @@ const struct bpf_map_ops htab_lru_map_ops = { .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_lru_map_lookup_elem, + .map_lookup_and_delete_elem = htab_lru_map_lookup_and_delete_elem, .map_lookup_elem_sys_only = htab_lru_map_lookup_elem_sys, .map_update_elem = htab_lru_map_update_elem, .map_delete_elem = htab_lru_map_delete_elem,@@ -2077,6 +2155,7 @@ const struct bpf_map_ops htab_percpu_map_ops = { .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_percpu_map_lookup_elem, + .map_lookup_and_delete_elem = htab_percpu_map_lookup_and_delete_elem, .map_update_elem = htab_percpu_map_update_elem, .map_delete_elem = htab_map_delete_elem, .map_seq_show_elem = htab_percpu_map_seq_show_elem,@@ -2096,6 +2175,7 @@ const struct bpf_map_ops htab_lru_percpu_map_ops = { .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_lru_percpu_map_lookup_elem, + .map_lookup_and_delete_elem = htab_lru_percpu_map_lookup_and_delete_elem, .map_update_elem = htab_lru_percpu_map_update_elem, .map_delete_elem = htab_lru_map_delete_elem, .map_seq_show_elem = htab_percpu_map_seq_show_elem,kernel/bpf/syscall.c +2
-1@@ -1495,7 +1495,7 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr) goto err_put; } - value_size = map->value_size; + value_size =bpf_map_value_size (map); err = -ENOMEM ; value =kmalloc (value_size,GFP_USER | __GFP_NOWARN);@@ -1505,6 +1505,18 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr)if (map->map_type ==BPF_MAP_TYPE_QUEUE || map->map_type ==BPF_MAP_TYPE_STACK ) { err = map->ops->map_pop_elem (map, value); + } else if (map->map_type == BPF_MAP_TYPE_HASH ||
kernel/bpf/syscall.c static int map_lookup_and_delete_elem(union bpf_attr *attr) · line 1518
Quoted 10 lines
kernel/bpf/syscall.c +10
-0+ map->map_type == BPF_MAP_TYPE_PERCPU_HASH || + map->map_type == BPF_MAP_TYPE_LRU_HASH || + map->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) { +if (!bpf_map_is_dev_bound (map)) { +bpf_disable_instrumentation (); +rcu_read_lock (); + err = map->ops->map_lookup_and_delete_elem (map, key, value); +rcu_read_unlock (); +bpf_enable_instrumentation (); +maybe_wait_bpf_programs (map);
maybe_wait_bpf_programs(map) is mostly for map-in-map. but I think it is okay to put it here in case in the future we will support map-in-map here. If maybe_wait_bpf_programs() get inlined which mostly likely is the case, the compiler should be able to optimize it away.
Quoted 20 lines
kernel/bpf/syscall.c +1
-0+ } }else { err = -ENOTSUPP ; }tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c new file +10
-0@@ -0,0 +1,283 @@ +// SPDX-License-Identifier: GPL-2.0-only + +#include <test_progs.h> +#include "test_lookup_and_delete.skel.h" + +#define START_VALUE 1234 +#define NEW_VALUE 4321 +#define MAX_ENTRIES 2 + +static int duration;
tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c line 20
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c new file +10
-0+static int nr_cpus; + +static int fill_values (int map_fd) +{ +__u64 key, value =START_VALUE ; +int err; + +for (key =1 ; key <MAX_ENTRIES +1 ; key++) { + err =bpf_map_update_elem (map_fd, &key, &value,BPF_NOEXIST ); +if (CHECK (err,"bpf_map_update_elem" ,"failed\n" ))
You can use
if (!ASSERT_OK(err, "bpf_map_update_elem"))
to save you from explicit "failed" string.
The same for some later other CHECK usages.
Quoted 24 lines
tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c new file +24
-0+return -1 ; + } + +return 0 ; +} + +static int fill_values_percpu (int map_fd) +{ +BPF_DECLARE_PERCPU (__u64, value); +int i, err; +u64 key; + +for (i =0 ; i < nr_cpus; i++) +bpf_percpu (value, i) =START_VALUE ; + +for (key =1 ; key <MAX_ENTRIES +1 ; key++) { + err =bpf_map_update_elem (map_fd, &key, value,BPF_NOEXIST ); +if (CHECK (err,"bpf_map_update_elem" ,"failed\n" )) +return -1 ; + } + +return 0 ; +} +
[...]
Quoted 6 lines
tools/testing/selftests/bpf/progs/test_lookup_and_delete.c new file +0
-0
tools/testing/selftests/bpf/progs/test_lookup_and_delete.c line 8
Quoted 8 lines
tools/testing/selftests/bpf/progs/test_lookup_and_delete.c new file +8
-0@@ -0,0 +1,26 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> + +__u32 set_pid; +__u64 set_key; +__u64 set_value;
Please add "= 0" to the above declaration to make
it llvm10 friendly.
Quoted 18 lines
tools/testing/selftests/bpf/progs/test_lookup_and_delete.c new file +18
-0+ +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __uint(max_entries, 2); + __type(key, __u64); + __type(value, __u64); +} hash_map SEC(".maps"); + +SEC("tp/syscalls/sys_enter_getpgid") +int bpf_lookup_and_delete_test (const void *ctx) +{ +if (set_pid ==bpf_get_current_pid_tgid () >>32 ) +bpf_map_update_elem (&hash_map, &set_key, &set_value,BPF_NOEXIST ); + +return 0 ; +} + +char _license[] SEC("license") = "GPL";
[...]
Hello,
Thank you for your feedback and comments.
Quoted 100 lines · Yonghong Song
Quoted 73 lines · Denis Salopek
Extend the existing
bpf_map_lookup_and_delete_elem()functionality to hashtab maps, in addition to stacks and queues.
Create a new hashtabbpf_map_opsfunction that does lookup and deletion of the element under the same bucket lock and add the createdmap_opstobpf.h.
Add the appropriate test cases to 'maps' and 'lru_map' selftests accompanied with newtest_progs.Cc Juraj Vijtiuk <[email protected]>Cc Luka Oreskovic <[email protected]>Cc Luka Perkov <[email protected]>Signed-off-by Denis Salopek <[email protected]>---
v2: Add functionality for LRU/per-CPU, addtest_progstests.--- include/linux/bpf.h | 2 + kernel/bpf/hashtab.c | 80 +++++ kernel/bpf/syscall.c | 14 +- .../bpf/prog_tests/lookup_and_delete.c | 283 ++++++++++++++++++ .../bpf/progs/test_lookup_and_delete.c | 26 ++ tools/testing/selftests/bpf/test_lru_map.c | 8 + tools/testing/selftests/bpf/test_maps.c | 19 +- 7 files changed, 430 insertions(+), 2 deletions(-)create mode 100644
tools/testing/selftests/bpf/prog_tests/lookup_and_delete.ccreate mode 100644tools/testing/selftests/bpf/progs/test_lookup_and_delete.cinclude/linux/bpf.h +2
-0@@ -67,6 +67,8 @@ struct bpf_map_ops {void *(*map_lookup_elem_sys_only)(struct bpf_map *map,void *key);int (*map_lookup_batch)(struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr); +int (*map_lookup_and_delete_elem)(struct bpf_map *map,void *key, +void *value);int (*map_lookup_and_delete_batch)(struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr);kernel/bpf/hashtab.c +26
-0@@ -1401,6 +1401,82 @@ static void htab_map_seq_show_elem(struct bpf_map *map, void *key,rcu_read_unlock (); } +static int __htab_map_lookup_and_delete_elem (struct bpf_map *map,void *key, +void *value,bool is_lru_map, +bool is_percpu) +{ + struct bpf_htab *htab = container_of(map, struct bpf_htab, map); +u32 hash, key_size, value_size; +struct hlist_nulls_head *head; +int cpu, off =0 , ret; +struct htab_elem *l; +unsigned long flags; +void __percpu *pptr; +struct bucket *b; + + key_size = map->key_size; + value_size =round_up (map->value_size,8 ); + + hash =htab_map_hash (key, key_size, htab->hashrnd); + b =__select_bucket (htab, hash); + head = &b->head; + + ret =htab_lock_bucket (htab, b, hash, &flags); +if (ret) +return ret; + + l =lookup_elem_raw (head, hash, key, key_size); +if (l) {kernel/bpf/hashtab.c static void htab_map_seq_show_elem(struct bpf_map *map, void *key, · line 1439
Quoted 10 lines
kernel/bpf/hashtab.c +10
-0+if (is_percpu) { + pptr =htab_elem_get_ptr (l, key_size); +for_each_possible_cpu (cpu) { +bpf_long_memcpy (value + off, +per_cpu_ptr (pptr, cpu), + value_size); + off += value_size; + } + }else { +copy_map_value (map, value, l->key +round_up (key_size,8 ));For hashtab lookup elem,
BPF_F_LOCKflag may be set by user, I think hashtablookup_and_delete_elemshould also support this flag, so user can ensure they always get a lock protected sane value.We have the following libbpf APIs.
LIBBPF_APIintbpf_map_lookup_elem(int fd, const void *key, void *value);LIBBPF_APIint bpf_map_lookup_elem_flags(int fd, const void *key, void *value,__u64 flags); LIBBPF_API int bpf_map_lookup_and_delete_elem(int fd, const void *key, void *value);
Quoted 8 lines
Previously,
bpf_map_lookup_and_delete_elemonly supports queue/stack, which does not need flags as it does not supportBPF_F_LOCKso we are fine.Maybe similar to
bpf_map_lookup_elem_flags()we add abpf_map_lookup_and_delete_elem_flags()? Maybe libbpf v1.0 can consolidate into a better uniform api.
If I understood correctly, there shouldn't be much changes for this addition:
- add LIBBPF_API prototype and function in bpf.[hc] - those are practically the same as bpf_map_lookup_elem_flags() but we call BPF_LOOKUP_AND_DELETE_ELEM syscall,
- add global declaration for bpf_map_lookup_elem_flags() in libbpf.map,
- make the necessary checks for flags and the lock in the functions,
- call copy_map_value_locked() if BPF_F_LOCK is set,
- mask lock with check_and_init_map_lock().
Is this right or is there anything else I've missed?
Quoted 101 lines
Quoted 101 lines
kernel/bpf/hashtab.c +44
-0+ } + +hlist_nulls_del_rcu (&l->hash_node); +if (!is_lru_map) +free_htab_elem (htab, l); + }else + ret = -ENOENT ; + +htab_unlock_bucket (htab, b, hash, flags); + +if (is_lru_map && l) +bpf_lru_push_free (&htab->lru, &l->lru_node); + +return ret; +} + +static int htab_map_lookup_and_delete_elem (struct bpf_map *map, +void *key,void *value) +{ +return __htab_map_lookup_and_delete_elem (map, key, value, false, false); +} + +static int htab_percpu_map_lookup_and_delete_elem (struct bpf_map *map, +void *key,void *value) +{ +return __htab_map_lookup_and_delete_elem (map, key, value, false, true); +} + +static int htab_lru_map_lookup_and_delete_elem (struct bpf_map *map,void *key, +void *value) +{ +return __htab_map_lookup_and_delete_elem (map, key, value, true, false); +} + +static int htab_lru_percpu_map_lookup_and_delete_elem (struct bpf_map *map, +void *key,void *value) +{ +return __htab_map_lookup_and_delete_elem (map, key, value, true, true); +} + static int __htab_map_lookup_and_delete_batch(struct bpf_map *map, const union bpf_attr *attr,@@ -1934,6 +2010,7 @@ const struct bpf_map_ops htab_map_ops = { .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_map_lookup_elem, + .map_lookup_and_delete_elem = htab_map_lookup_and_delete_elem, .map_update_elem = htab_map_update_elem, .map_delete_elem = htab_map_delete_elem, .map_gen_lookup = htab_map_gen_lookup,@@ -1954,6 +2031,7 @@ const struct bpf_map_ops htab_lru_map_ops = { .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_lru_map_lookup_elem, + .map_lookup_and_delete_elem = htab_lru_map_lookup_and_delete_elem, .map_lookup_elem_sys_only = htab_lru_map_lookup_elem_sys, .map_update_elem = htab_lru_map_update_elem, .map_delete_elem = htab_lru_map_delete_elem,@@ -2077,6 +2155,7 @@ const struct bpf_map_ops htab_percpu_map_ops = { .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_percpu_map_lookup_elem, + .map_lookup_and_delete_elem = htab_percpu_map_lookup_and_delete_elem, .map_update_elem = htab_percpu_map_update_elem, .map_delete_elem = htab_map_delete_elem, .map_seq_show_elem = htab_percpu_map_seq_show_elem,@@ -2096,6 +2175,7 @@ const struct bpf_map_ops htab_lru_percpu_map_ops = { .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_lru_percpu_map_lookup_elem, + .map_lookup_and_delete_elem = htab_lru_percpu_map_lookup_and_delete_elem, .map_update_elem = htab_lru_percpu_map_update_elem, .map_delete_elem = htab_lru_map_delete_elem, .map_seq_show_elem = htab_percpu_map_seq_show_elem,kernel/bpf/syscall.c +10
-1@@ -1495,7 +1495,7 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr) goto err_put; } - value_size = map->value_size; + value_size =bpf_map_value_size (map); err = -ENOMEM ; value =kmalloc (value_size,GFP_USER | __GFP_NOWARN);@@ -1505,6 +1505,18 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr)if (map->map_type ==BPF_MAP_TYPE_QUEUE || map->map_type ==BPF_MAP_TYPE_STACK ) { err = map->ops->map_pop_elem (map, value); + }else if (map->map_type ==BPF_MAP_TYPE_HASH || + map->map_type ==BPF_MAP_TYPE_PERCPU_HASH || + map->map_type ==BPF_MAP_TYPE_LRU_HASH || + map->map_type ==BPF_MAP_TYPE_LRU_PERCPU_HASH ) { +if (!bpf_map_is_dev_bound (map)) { +bpf_disable_instrumentation (); +rcu_read_lock (); + err = map->ops->map_lookup_and_delete_elem (map, key, value); +rcu_read_unlock ();
Quoted 9 lines
kernel/bpf/syscall.c static int map_lookup_and_delete_elem(union bpf_attr *attr) · line 1518
Quoted 2 lines
kernel/bpf/syscall.c +2
-0+bpf_enable_instrumentation (); +maybe_wait_bpf_programs (map);
maybe_wait_bpf_programs(map)is mostly for map-in-map. but I think it is okay to put it here in case in the future we will support map-in-map here. Ifmaybe_wait_bpf_programs()get inlined which mostly likely is the case, the compiler should be able to optimize it away.
I didn't realise at first it's only for map-in-map and forgot to remove it later, so I can remove this if you think it's better?
Quoted 32 lines
Quoted 20 lines
kernel/bpf/syscall.c +1
-0+ } }else { err = -ENOTSUPP ; }tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c new file +10
-0@@ -0,0 +1,283 @@ +// SPDX-License-Identifier: GPL-2.0-only + +#include <test_progs.h> +#include "test_lookup_and_delete.skel.h" + +#define START_VALUE 1234 +#define NEW_VALUE 4321 +#define MAX_ENTRIES 2 + +static int duration;tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c line 20
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c new file +10
-0+static int nr_cpus; + +static int fill_values (int map_fd) +{ +__u64 key, value =START_VALUE ; +int err; + +for (key =1 ; key <MAX_ENTRIES +1 ; key++) { + err =bpf_map_update_elem (map_fd, &key, &value,BPF_NOEXIST ); +if (CHECK (err,"bpf_map_update_elem" ,"failed\n" ))You can use
Quoted 4 lines
if (!ASSERT_OK(err, "bpf_map_update_elem"))to save you from explicit "failed" string.
The same for some later other CHECK usages.
Ok.
Quoted 34 lines
Quoted 24 lines
tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c new file +24
-0+return -1 ; + } + +return 0 ; +} + +static int fill_values_percpu (int map_fd) +{ +BPF_DECLARE_PERCPU (__u64, value); +int i, err; +u64 key; + +for (i =0 ; i < nr_cpus; i++) +bpf_percpu (value, i) =START_VALUE ; + +for (key =1 ; key <MAX_ENTRIES +1 ; key++) { + err =bpf_map_update_elem (map_fd, &key, value,BPF_NOEXIST ); +if (CHECK (err,"bpf_map_update_elem" ,"failed\n" )) +return -1 ; + } + +return 0 ; +} +[...]
Quoted 9 lines
tools/testing/selftests/bpf/progs/test_lookup_and_delete.c new file +3
-0@@ -0,0 +1,26 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include "vmlinux.h"
Quoted 9 lines
tools/testing/selftests/bpf/progs/test_lookup_and_delete.c line 8
Quoted 5 lines
tools/testing/selftests/bpf/progs/test_lookup_and_delete.c new file +5
-0+#include <bpf/bpf_helpers.h> + +__u32 set_pid; +__u64 set_key; +__u64 set_value;Please add "= 0" to the above declaration to make
it llvm10 friendly.
Ok, I'll add this. Sorry, checkpatch.pl gave me an error with it, that's why I removed it.
Quoted 19 lines
Quoted 18 lines
tools/testing/selftests/bpf/progs/test_lookup_and_delete.c new file +18
-0+ +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __uint(max_entries, 2); + __type(key, __u64); + __type(value, __u64); +} hash_map SEC(".maps"); + +SEC("tp/syscalls/sys_enter_getpgid") +int bpf_lookup_and_delete_test (const void *ctx) +{ +if (set_pid ==bpf_get_current_pid_tgid () >>32 ) +bpf_map_update_elem (&hash_map, &set_key, &set_value,BPF_NOEXIST ); + +return 0 ; +} + +char _license[] SEC("license") = "GPL";[...]
Quoted 114 lines · Denis Salopek
Hello,
Thank you for your feedback and comments.
Quoted 100 lines · Yonghong Song
Quoted 73 lines · Denis Salopek
Extend the existing
bpf_map_lookup_and_delete_elem()functionality to hashtab maps, in addition to stacks and queues.
Create a new hashtabbpf_map_opsfunction that does lookup and deletion of the element under the same bucket lock and add the createdmap_opstobpf.h.
Add the appropriate test cases to 'maps' and 'lru_map' selftests accompanied with newtest_progs.Cc Juraj Vijtiuk <[email protected]>Cc Luka Oreskovic <[email protected]>Cc Luka Perkov <[email protected]>Signed-off-by Denis Salopek <[email protected]>---
v2: Add functionality for LRU/per-CPU, addtest_progstests.--- include/linux/bpf.h | 2 + kernel/bpf/hashtab.c | 80 +++++ kernel/bpf/syscall.c | 14 +- .../bpf/prog_tests/lookup_and_delete.c | 283 ++++++++++++++++++ .../bpf/progs/test_lookup_and_delete.c | 26 ++ tools/testing/selftests/bpf/test_lru_map.c | 8 + tools/testing/selftests/bpf/test_maps.c | 19 +- 7 files changed, 430 insertions(+), 2 deletions(-)create mode 100644
tools/testing/selftests/bpf/prog_tests/lookup_and_delete.ccreate mode 100644tools/testing/selftests/bpf/progs/test_lookup_and_delete.cinclude/linux/bpf.h +2
-0@@ -67,6 +67,8 @@ struct bpf_map_ops {void *(*map_lookup_elem_sys_only)(struct bpf_map *map,void *key);int (*map_lookup_batch)(struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr); +int (*map_lookup_and_delete_elem)(struct bpf_map *map,void *key, +void *value);int (*map_lookup_and_delete_batch)(struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr);kernel/bpf/hashtab.c +26
-0@@ -1401,6 +1401,82 @@ static void htab_map_seq_show_elem(struct bpf_map *map, void *key,rcu_read_unlock (); } +static int __htab_map_lookup_and_delete_elem (struct bpf_map *map,void *key, +void *value,bool is_lru_map, +bool is_percpu) +{ + struct bpf_htab *htab = container_of(map, struct bpf_htab, map); +u32 hash, key_size, value_size; +struct hlist_nulls_head *head; +int cpu, off =0 , ret; +struct htab_elem *l; +unsigned long flags; +void __percpu *pptr; +struct bucket *b; + + key_size = map->key_size; + value_size =round_up (map->value_size,8 ); + + hash =htab_map_hash (key, key_size, htab->hashrnd); + b =__select_bucket (htab, hash); + head = &b->head; + + ret =htab_lock_bucket (htab, b, hash, &flags); +if (ret) +return ret; + + l =lookup_elem_raw (head, hash, key, key_size); +if (l) {kernel/bpf/hashtab.c static void htab_map_seq_show_elem(struct bpf_map *map, void *key, · line 1439
Quoted 10 lines
kernel/bpf/hashtab.c +10
-0+if (is_percpu) { + pptr =htab_elem_get_ptr (l, key_size); +for_each_possible_cpu (cpu) { +bpf_long_memcpy (value + off, +per_cpu_ptr (pptr, cpu), + value_size); + off += value_size; + } + }else { +copy_map_value (map, value, l->key +round_up (key_size,8 ));For hashtab lookup elem,
BPF_F_LOCKflag may be set by user, I think hashtablookup_and_delete_elemshould also support this flag, so user can ensure they always get a lock protected sane value.We have the following libbpf APIs.
LIBBPF_APIintbpf_map_lookup_elem(int fd, const void *key, void *value);LIBBPF_APIint bpf_map_lookup_elem_flags(int fd, const void *key, void *value,__u64 flags); LIBBPF_API int bpf_map_lookup_and_delete_elem(int fd, const void *key, void *value);Quoted 8 lines
Previously,
bpf_map_lookup_and_delete_elemonly supports queue/stack, which does not need flags as it does not supportBPF_F_LOCKso we are fine.Maybe similar to
bpf_map_lookup_elem_flags()we add abpf_map_lookup_and_delete_elem_flags()? Maybe libbpf v1.0 can consolidate into a better uniform api.
Quoted 5 lines
If I understood correctly, there shouldn't be much changes for this addition:
- addLIBBPF_APIprototype and function in bpf.[hc] - those are practically the same asbpf_map_lookup_elem_flags()but we callBPF_LOOKUP_AND_DELETE_ELEMsyscall,
yes.
Quoted 1 line
- add global declaration for
bpf_map_lookup_elem_flags()in libbpf.map,
bpf_map_lookup_and_delete_elem_flags()
Quoted 1 line
- make the necessary checks for flags and the lock in the functions,
yes.
Quoted 1 line
- call
copy_map_value_locked()ifBPF_F_LOCKis set,
yes.
Quoted 1 line
- mask lock with
check_and_init_map_lock().
not sure about, current implementation is supposed to already take care of this, but please double check.
Quoted 2 lines
Is this right or is there anything else I've missed?
yes, almost right except some minor comments above.
Quoted 112 lines
Quoted 102 lines
Quoted 102 lines
kernel/bpf/hashtab.c +44
-0+ } + +hlist_nulls_del_rcu (&l->hash_node); +if (!is_lru_map) +free_htab_elem (htab, l); + }else + ret = -ENOENT ; + +htab_unlock_bucket (htab, b, hash, flags); + +if (is_lru_map && l) +bpf_lru_push_free (&htab->lru, &l->lru_node); + +return ret; +} + +static int htab_map_lookup_and_delete_elem (struct bpf_map *map, +void *key,void *value) +{ +return __htab_map_lookup_and_delete_elem (map, key, value, false, false); +} + +static int htab_percpu_map_lookup_and_delete_elem (struct bpf_map *map, +void *key,void *value) +{ +return __htab_map_lookup_and_delete_elem (map, key, value, false, true); +} + +static int htab_lru_map_lookup_and_delete_elem (struct bpf_map *map,void *key, +void *value) +{ +return __htab_map_lookup_and_delete_elem (map, key, value, true, false); +} + +static int htab_lru_percpu_map_lookup_and_delete_elem (struct bpf_map *map, +void *key,void *value) +{ +return __htab_map_lookup_and_delete_elem (map, key, value, true, true); +} + static int __htab_map_lookup_and_delete_batch(struct bpf_map *map, const union bpf_attr *attr,@@ -1934,6 +2010,7 @@ const struct bpf_map_ops htab_map_ops = { .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_map_lookup_elem, + .map_lookup_and_delete_elem = htab_map_lookup_and_delete_elem, .map_update_elem = htab_map_update_elem, .map_delete_elem = htab_map_delete_elem, .map_gen_lookup = htab_map_gen_lookup,@@ -1954,6 +2031,7 @@ const struct bpf_map_ops htab_lru_map_ops = { .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_lru_map_lookup_elem, + .map_lookup_and_delete_elem = htab_lru_map_lookup_and_delete_elem, .map_lookup_elem_sys_only = htab_lru_map_lookup_elem_sys, .map_update_elem = htab_lru_map_update_elem, .map_delete_elem = htab_lru_map_delete_elem,@@ -2077,6 +2155,7 @@ const struct bpf_map_ops htab_percpu_map_ops = { .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_percpu_map_lookup_elem, + .map_lookup_and_delete_elem = htab_percpu_map_lookup_and_delete_elem, .map_update_elem = htab_percpu_map_update_elem, .map_delete_elem = htab_map_delete_elem, .map_seq_show_elem = htab_percpu_map_seq_show_elem,@@ -2096,6 +2175,7 @@ const struct bpf_map_ops htab_lru_percpu_map_ops = { .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_lru_percpu_map_lookup_elem, + .map_lookup_and_delete_elem = htab_lru_percpu_map_lookup_and_delete_elem, .map_update_elem = htab_lru_percpu_map_update_elem, .map_delete_elem = htab_lru_map_delete_elem, .map_seq_show_elem = htab_percpu_map_seq_show_elem,kernel/bpf/syscall.c +10
-1@@ -1495,7 +1495,7 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr) goto err_put; } - value_size = map->value_size; + value_size =bpf_map_value_size (map); err = -ENOMEM ; value =kmalloc (value_size,GFP_USER | __GFP_NOWARN);@@ -1505,6 +1505,18 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr)if (map->map_type ==BPF_MAP_TYPE_QUEUE || map->map_type ==BPF_MAP_TYPE_STACK ) { err = map->ops->map_pop_elem (map, value); + }else if (map->map_type ==BPF_MAP_TYPE_HASH || + map->map_type ==BPF_MAP_TYPE_PERCPU_HASH || + map->map_type ==BPF_MAP_TYPE_LRU_HASH || + map->map_type ==BPF_MAP_TYPE_LRU_PERCPU_HASH ) { +if (!bpf_map_is_dev_bound (map)) { +bpf_disable_instrumentation (); +rcu_read_lock (); + err = map->ops->map_lookup_and_delete_elem (map, key, value); +rcu_read_unlock ();Quoted 9 lines
kernel/bpf/syscall.c static int map_lookup_and_delete_elem(union bpf_attr *attr) · line 1518
Quoted 2 lines
kernel/bpf/syscall.c +2
-0+bpf_enable_instrumentation (); +maybe_wait_bpf_programs (map);
maybe_wait_bpf_programs(map)is mostly for map-in-map. but I think it is okay to put it here in case in the future we will support map-in-map here. Ifmaybe_wait_bpf_programs()get inlined which mostly likely is the case, the compiler should be able to optimize it away.
Quoted 2 lines
I didn't realise at first it's only for map-in-map and forgot to remove it later, so I can remove this if you think it's better?
Originally I thought to keep it as the compiler should be able to optimize it away. But since there is no immediate use case yet for lookup-and-delete for hash of map-in-maps, so let us remove maybe_wait_bpf_programs() to avoid confusion. We can add it later if BPF_MAP_TYPE_HASH_OF_MAPS is added.
Quoted 84 lines
Quoted 33 lines
Quoted 21 lines
kernel/bpf/syscall.c +1
-0+ } }else { err = -ENOTSUPP ; }tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c new file +10
-0@@ -0,0 +1,283 @@ +// SPDX-License-Identifier: GPL-2.0-only + +#include <test_progs.h> +#include "test_lookup_and_delete.skel.h" + +#define START_VALUE 1234 +#define NEW_VALUE 4321 +#define MAX_ENTRIES 2 + +static int duration;tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c line 20
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c new file +10
-0+static int nr_cpus; + +static int fill_values (int map_fd) +{ +__u64 key, value =START_VALUE ; +int err; + +for (key =1 ; key <MAX_ENTRIES +1 ; key++) { + err =bpf_map_update_elem (map_fd, &key, &value,BPF_NOEXIST ); +if (CHECK (err,"bpf_map_update_elem" ,"failed\n" ))You can use
Quoted 4 lines
if (!ASSERT_OK(err, "bpf_map_update_elem"))to save you from explicit "failed" string.
The same for some later other CHECK usages.Ok.
Quoted 34 lines
Quoted 24 lines
tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c new file +24
-0+return -1 ; + } + +return 0 ; +} + +static int fill_values_percpu (int map_fd) +{ +BPF_DECLARE_PERCPU (__u64, value); +int i, err; +u64 key; + +for (i =0 ; i < nr_cpus; i++) +bpf_percpu (value, i) =START_VALUE ; + +for (key =1 ; key <MAX_ENTRIES +1 ; key++) { + err =bpf_map_update_elem (map_fd, &key, value,BPF_NOEXIST ); +if (CHECK (err,"bpf_map_update_elem" ,"failed\n" )) +return -1 ; + } + +return 0 ; +} +[...]
Quoted 9 lines
tools/testing/selftests/bpf/progs/test_lookup_and_delete.c new file +3
-0@@ -0,0 +1,26 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include "vmlinux.h" Quoted 9 lines
tools/testing/selftests/bpf/progs/test_lookup_and_delete.c line 8
Quoted 5 lines
tools/testing/selftests/bpf/progs/test_lookup_and_delete.c new file +5
-0+#include <bpf/bpf_helpers.h> + +__u32 set_pid; +__u64 set_key; +__u64 set_value;Please add "= 0" to the above declaration to make
it llvm10 friendly.
Quoted 2 lines
Ok, I'll add this. Sorry, checkpatch.pl gave me an error with it, that's why I removed it.
Song Liu recently added a patch to suppress the warning:
commit 5b8f82e1a17695c9e5fec5842b234967782d7e5b
Author: Song Liu <[email protected]>
Date: Thu Feb 25 17:22:08 2021 -0800
checkpatch: do not apply "initialise globals to 0" check to BPF progs
You should be good now.
Quoted 20 lines
Quoted 20 lines
Quoted 19 lines
tools/testing/selftests/bpf/progs/test_lookup_and_delete.c new file +18
-0+ +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __uint(max_entries, 2); + __type(key, __u64); + __type(value, __u64); +} hash_map SEC(".maps"); + +SEC("tp/syscalls/sys_enter_getpgid") +int bpf_lookup_and_delete_test (const void *ctx) +{ +if (set_pid ==bpf_get_current_pid_tgid () >>32 ) +bpf_map_update_elem (&hash_map, &set_key, &set_value,BPF_NOEXIST ); + +return 0 ; +} + +char _license[] SEC("license") = "GPL";[...]