Skip to contentSkip to conversation

bpf: add lookup_and_delete_elem support to hashtab

PATCH Superseded Denis Salopek 2 participants 3 messages Mar 16, 2021 – Mar 22, 2021

Subsystems (5)
Kselftest BPF BPF selftests BPF core +1 more subsystems

v3 of 7 Superseded Latest is v7 →

lore
Share & tools
lore
#0 lore raw

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.

Cc Juraj Vijtiuk <[email protected]>
Cc Luka Oreskovic <[email protected]>
Cc Luka Perkov <[email protected]>

---
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
index a25730eaa148..9e07fc7312c0 100644
@@ -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
index c859bc46d06c..36f65b589b82 100644
@@ -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 flags
 
 static 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
index bba48ff4c5c0..b7c2cc12034c 100644
@@ -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
index 875dde20d56e..4f758f8f50cd 100644
@@ -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
index ec898f464ab9..f4d3cbd8193b 100644
@@ -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
new file mode 100644
index 000000000000..3a193f42c7e7
@@ -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
index 6a5349f9eb14..f33fb6de76bc 100644
@@ -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
index 51adc42b2b40..dbd5f95e8bde 100644
@@ -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
maintainer
#1 lore raw

On 3/16/21 6:44 PM, Denis Salopek wrote:
[...]

Quoted 45 lines
kernel/bpf/syscall.c +11 -2
index c859bc46d06c..36f65b589b82 100644
@@ -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 flags
 
  static 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;
  	}
#2 lore raw
Quoted 45 lines · Daniel Borkmann

On 3/16/21 6:44 PM, Denis Salopek wrote:
[...]

Quoted 43 lines
kernel/bpf/syscall.c +12 -2
index c859bc46d06c..36f65b589b82 100644
@@ -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 flags
  static 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 -ENOMEM error 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;
  	}