bpf: add lookup_and_delete_elem support to hashtab
Subsystems (5)
PATCH v3 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.
Add bpf_map_lookup_and_delete_elem_flags() libbpf API in order to use the BPF_F_LOCK flag.
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.
v3: Add bpf_map_lookup_and_delete_elem_flags() and enable BPF_F_LOCK flag, change CHECKs to ASSERT_OKs, initialize variables to 0.
--- include/linux/bpf.h | 2 + kernel/bpf/hashtab.c | 97 ++++++ kernel/bpf/syscall.c | 24 +- tools/lib/bpf/bpf.c | 13 + tools/lib/bpf/bpf.h | 2 + tools/lib/bpf/libbpf.map | 1 + .../bpf/prog_tests/lookup_and_delete.c | 279 ++++++++++++++++++ .../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 +- 10 files changed, 468 insertions(+), 3 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,u64 flags);int (*map_lookup_and_delete_batch)(struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr);
kernel/bpf/hashtab.c +97 -0
127 lines not on this page · raw message
kernel/bpf/syscall.c +22 -2
@@ -1463,7 +1463,7 @@ int generic_map_lookup_batch(struct bpf_map *map,return err; } -#define BPF_MAP_LOOKUP_AND_DELETE_ELEM_LAST_FIELD value +#define BPF_MAP_LOOKUP_AND_DELETE_ELEM_LAST_FIELD flagsstatic int map_lookup_and_delete_elem (union bpf_attr *attr) {
@@ -1479,6 +1479,9 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr)if (CHECK_ATTR (BPF_MAP_LOOKUP_AND_DELETE_ELEM ))return -EINVAL ; +if (attr->flags & ~BPF_F_LOCK ) +return -EINVAL ; + f =fdget (ufd); map =__bpf_map_get (f);if (IS_ERR (map))
@@ -1489,13 +1492,19 @@ static int map_lookup_and_delete_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); 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 +1514,17 @@ 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, attr->flags); +rcu_read_unlock (); +bpf_enable_instrumentation (); + } }else { err = -ENOTSUPP ; }
tools/lib/bpf/bpf.c +13 -0
@@ -458,6 +458,19 @@ int bpf_map_lookup_and_delete_elem(int fd, const void *key, void *value)return sys_bpf (BPF_MAP_LOOKUP_AND_DELETE_ELEM , &attr,sizeof (attr)); } +int bpf_map_lookup_and_delete_elem_flags (int fd,const void *key,void *value,__u64 flags) +{ +union bpf_attr attr; + +memset (&attr,0 ,sizeof (attr)); + attr.map_fd = fd; + attr.key =ptr_to_u64 (key); + attr.value =ptr_to_u64 (value); + attr.flags = flags; + +return sys_bpf (BPF_MAP_LOOKUP_AND_DELETE_ELEM , &attr,sizeof (attr)); +} +int bpf_map_delete_elem (int fd,const void *key) {union bpf_attr attr;
tools/lib/bpf/bpf.h +2 -0
@@ -124,6 +124,8 @@ 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); +LIBBPF_API int bpf_map_lookup_and_delete_elem_flags(int fd, const void *key, +void *value,__u64 flags); LIBBPF_API int bpf_map_delete_elem(int fd, const void *key); LIBBPF_API int bpf_map_get_next_key(int fd, const void *key, void *next_key); LIBBPF_API int bpf_map_freeze(int fd);
tools/lib/bpf/libbpf.map +1 -0
@@ -132,6 +132,7 @@ LIBBPF_0.0.2 { bpf_probe_prog_type; bpf_map__resize; bpf_map_lookup_elem_flags; + bpf_map_lookup_and_delete_elem_flags; bpf_object__btf; bpf_object__find_map_fd_by_name; bpf_get_link_xdp_id;
tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c new file +279 -0
279 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 =0 ; +__u64 set_key =0 ; +__u64 set_value =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";
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
Daniel Borkmann
maintainerOn 3/16/21 6:44 PM, Denis Salopek wrote:
[...]
Quoted 45 lines
kernel/bpf/syscall.c +11
-2@@ -1463,7 +1463,7 @@ int generic_map_lookup_batch(struct bpf_map *map,return err; } -#define BPF_MAP_LOOKUP_AND_DELETE_ELEM_LAST_FIELD value +#define BPF_MAP_LOOKUP_AND_DELETE_ELEM_LAST_FIELD flagsstatic int map_lookup_and_delete_elem (union bpf_attr *attr) {@@ -1479,6 +1479,9 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr)if (CHECK_ATTR (BPF_MAP_LOOKUP_AND_DELETE_ELEM ))return -EINVAL ; +if (attr->flags & ~BPF_F_LOCK ) +return -EINVAL ; + f =fdget (ufd); map =__bpf_map_get (f);if (IS_ERR (map))@@ -1489,13 +1492,19 @@ static int map_lookup_and_delete_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); 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);
kernel/bpf/syscall.c static int map_lookup_and_delete_elem(union bpf_attr *attr) · line 1521
Quoted 8 lines
kernel/bpf/syscall.c +5
-0@@ -1505,6 +1514,17 @@ 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)) {
I think you probably rather meant to fold the above !bpf_map_is_dev_bound(map) condition into the higher level 'else if', right? Otherwise for dev bound maps you'll always end up with -ENOMEM error rather than -ENOTSUPP.
Quoted 9 lines
kernel/bpf/syscall.c +6
-0+bpf_disable_instrumentation (); +rcu_read_lock (); + err = map->ops->map_lookup_and_delete_elem (map, key, value, attr->flags); +rcu_read_unlock (); +bpf_enable_instrumentation (); + } }else { err = -ENOTSUPP ; }
Quoted 45 lines · Daniel Borkmann
On 3/16/21 6:44 PM, Denis Salopek wrote:
[...]Quoted 43 lines
kernel/bpf/syscall.c +12
-2@@ -1463,7 +1463,7 @@ int generic_map_lookup_batch(struct bpf_map *map,return err; } -#define BPF_MAP_LOOKUP_AND_DELETE_ELEM_LAST_FIELD value +#define BPF_MAP_LOOKUP_AND_DELETE_ELEM_LAST_FIELD flagsstatic int map_lookup_and_delete_elem (union bpf_attr *attr) {@@ -1479,6 +1479,9 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr)if (CHECK_ATTR (BPF_MAP_LOOKUP_AND_DELETE_ELEM ))return -EINVAL ; +if (attr->flags & ~BPF_F_LOCK ) +return -EINVAL ; + f =fdget (ufd); map =__bpf_map_get (f);if (IS_ERR (map))@@ -1489,13 +1492,19 @@ static int map_lookup_and_delete_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); 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 +1514,17 @@ 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 ||
Quoted 9 lines
kernel/bpf/syscall.c static int map_lookup_and_delete_elem(union bpf_attr *attr) · line 1521
Quoted 4 lines
kernel/bpf/syscall.c +4
-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)) {I think you probably rather meant to fold the above !bpf_map_is_dev_bound(map) condition into the higher level 'else if', right? Otherwise for dev bound maps you'll always end up with
-ENOMEMerror rather than-ENOTSUPP.
Yes, you're right, thank you. How about setting the err to -ENOTSUPP before the 'if' and just drop the else altogether?
Quoted 9 lines
Quoted 9 lines
kernel/bpf/syscall.c +6
-0+bpf_disable_instrumentation (); +rcu_read_lock (); + err = map->ops->map_lookup_and_delete_elem (map, key, value, attr->flags); +rcu_read_unlock (); +bpf_enable_instrumentation (); + } }else { err = -ENOTSUPP ; }