[PATCH v7 bpf-next 0/3] Add lookup_and_delete_elem support to BPF hash map types

[PATCH v7 bpf-next 0/3] Add lookup_and_delete_elem support to BPF hash map types

[Denis Salopek]

This patch series extends the existing bpf_map_lookup_and_delete_elem()
functionality with 4 more map types:
 - BPF_MAP_TYPE_HASH,
 - BPF_MAP_TYPE_PERCPU_HASH,
 - BPF_MAP_TYPE_LRU_HASH and
 - BPF_MAP_TYPE_LRU_PERCPU_HASH.

Patch 1 adds most of its functionality and logic as well as
documentation.

As it was previously limited to only stacks and queues which do not
support the BPF_F_LOCK flag, patch 2 enables its usage by adding a new
libbpf API bpf_map_lookup_and_delete_elem_flags() based on the existing
bpf_map_lookup_elem_flags().

Patch 3 adds selftests for lookup_and_delete_elem().

Changes in patch 1:
v7: Minor formating nits, add Acked-by.
v6: Remove unneeded flag check, minor code/format fixes.
v5: Split patch to 3 patches. Extend BPF_MAP_LOOKUP_AND_DELETE_ELEM
documentation with this changes.
v4: Fix the return value for unsupported map types.
v3: Add bpf_map_lookup_and_delete_elem_flags() and enable BPF_F_LOCK
flag, change CHECKs to ASSERT_OKs, initialize variables to 0.
v2: Add functionality for LRU/per-CPU, add test_progs tests.

Changes in patch 2:
v7: No change.
v6: Add Acked-by.
v5: Move to the newest libbpf version (0.4.0).

Changes in patch 3:
v7: Remove ASSERT_GE macro which is already added in some other commit,
change ASSERT_OK to ASSERT_OK_PTR, add Acked-by.
v6: Remove PERCPU macros, add ASSERT_GE macro to test_progs.h, remove
leftover code.
v5: Use more appropriate macros. Better check for changed value.

Denis Salopek (3):
  bpf: add lookup_and_delete_elem support to hashtab
  bpf: extend libbpf with bpf_map_lookup_and_delete_elem_flags
  selftests/bpf: add bpf_lookup_and_delete_elem tests

 include/linux/bpf.h                           |   2 +
 include/uapi/linux/bpf.h                      |  13 +
 kernel/bpf/hashtab.c                          |  98 ++++++
 kernel/bpf/syscall.c                          |  34 ++-
 tools/include/uapi/linux/bpf.h                |  13 +
 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        | 288 ++++++++++++++++++
 .../bpf/progs/test_lookup_and_delete.c        |  26 ++
 tools/testing/selftests/bpf/test_lru_map.c    |   8 +
 tools/testing/selftests/bpf/test_maps.c       |  17 ++
 12 files changed, 511 insertions(+), 4 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

-- 
2.26.2

[PATCH v7 bpf-next 1/3] bpf: add lookup_and_delete_elem support to hashtab

[Denis Salopek]

Extend the existing bpf_map_lookup_and_delete_elem() functionality to
hashtab map types, 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.

Cc: Juraj Vijtiuk <juraj.vijtiuk@sartura.hr>
Cc: Luka Oreskovic <luka.oreskovic@sartura.hr>
Cc: Luka Perkov <luka.perkov@sartura.hr>
Cc: Yonghong Song <yhs@fb.com>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Denis Salopek <denis.salopek@sartura.hr>
Acked-by: Yonghong Song <yhs@fb.com>
---
 include/linux/bpf.h            |  2 +
 include/uapi/linux/bpf.h       | 13 +++++
 kernel/bpf/hashtab.c           | 98 ++++++++++++++++++++++++++++++++++
 kernel/bpf/syscall.c           | 34 ++++++++++--
 tools/include/uapi/linux/bpf.h | 13 +++++
 5 files changed, 156 insertions(+), 4 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 02b02cb29ce2..9da98d98db25 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -69,6 +69,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);
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index ec6d85a81744..c10ba06af69e 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -527,6 +527,15 @@ union bpf_iter_link_info {
  *		Look up an element with the given *key* in the map referred to
  *		by the file descriptor *fd*, and if found, delete the element.
  *
+ *		For **BPF_MAP_TYPE_QUEUE** and **BPF_MAP_TYPE_STACK** map
+ *		types, the *flags* argument needs to be set to 0, but for other
+ *		map types, it may be specified as:
+ *
+ *		**BPF_F_LOCK**
+ *			Look up and delete the value of a spin-locked map
+ *			without returning the lock. This must be specified if
+ *			the elements contain a spinlock.
+ *
  *		The **BPF_MAP_TYPE_QUEUE** and **BPF_MAP_TYPE_STACK** map types
  *		implement this command as a "pop" operation, deleting the top
  *		element rather than one corresponding to *key*.
@@ -536,6 +545,10 @@ union bpf_iter_link_info {
  *		This command is only valid for the following map types:
  *		* **BPF_MAP_TYPE_QUEUE**
  *		* **BPF_MAP_TYPE_STACK**
+ *		* **BPF_MAP_TYPE_HASH**
+ *		* **BPF_MAP_TYPE_PERCPU_HASH**
+ *		* **BPF_MAP_TYPE_LRU_HASH**
+ *		* **BPF_MAP_TYPE_LRU_PERCPU_HASH**
  *
  *	Return
  *		Returns zero on success. On error, -1 is returned and *errno*
diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index d7ebb12ffffc..9da0a0413a53 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -1401,6 +1401,100 @@ 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, u64 flags)
+{
+	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
+	struct hlist_nulls_head *head;
+	unsigned long bflags;
+	struct htab_elem *l;
+	u32 hash, key_size;
+	struct bucket *b;
+	int ret;
+
+	key_size = map->key_size;
+
+	hash = htab_map_hash(key, key_size, htab->hashrnd);
+	b = __select_bucket(htab, hash);
+	head = &b->head;
+
+	ret = htab_lock_bucket(htab, b, hash, &bflags);
+	if (ret)
+		return ret;
+
+	l = lookup_elem_raw(head, hash, key, key_size);
+	if (!l) {
+		ret = -ENOENT;
+	} else {
+		if (is_percpu) {
+			u32 roundup_value_size = round_up(map->value_size, 8);
+			void __percpu *pptr;
+			int off = 0, cpu;
+
+			pptr = htab_elem_get_ptr(l, key_size);
+			for_each_possible_cpu(cpu) {
+				bpf_long_memcpy(value + off,
+						per_cpu_ptr(pptr, cpu),
+						roundup_value_size);
+				off += roundup_value_size;
+			}
+		} else {
+			u32 roundup_key_size = round_up(map->key_size, 8);
+
+			if (flags & BPF_F_LOCK)
+				copy_map_value_locked(map, value, l->key +
+						      roundup_key_size,
+						      true);
+			else
+				copy_map_value(map, value, l->key +
+					       roundup_key_size);
+			check_and_init_map_lock(map, value);
+		}
+
+		hlist_nulls_del_rcu(&l->hash_node);
+		if (!is_lru_map)
+			free_htab_elem(htab, l);
+	}
+
+	htab_unlock_bucket(htab, b, hash, bflags);
+
+	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, u64 flags)
+{
+	return __htab_map_lookup_and_delete_elem(map, key, value, false, false,
+						 flags);
+}
+
+static int htab_percpu_map_lookup_and_delete_elem(struct bpf_map *map,
+						  void *key, void *value,
+						  u64 flags)
+{
+	return __htab_map_lookup_and_delete_elem(map, key, value, false, true,
+						 flags);
+}
+
+static int htab_lru_map_lookup_and_delete_elem(struct bpf_map *map, void *key,
+					       void *value, u64 flags)
+{
+	return __htab_map_lookup_and_delete_elem(map, key, value, true, false,
+						 flags);
+}
+
+static int htab_lru_percpu_map_lookup_and_delete_elem(struct bpf_map *map,
+						      void *key, void *value,
+						      u64 flags)
+{
+	return __htab_map_lookup_and_delete_elem(map, key, value, true, true,
+						 flags);
+}
+
 static int
 __htab_map_lookup_and_delete_batch(struct bpf_map *map,
 				   const union bpf_attr *attr,
@@ -1934,6 +2028,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 +2049,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 +2173,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 +2193,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,
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index 941ca06d9dfa..d1c51da2f477 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -1468,7 +1468,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)
 {
@@ -1484,6 +1484,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))
@@ -1494,24 +1497,47 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr)
 		goto err_put;
 	}
 
+	if (attr->flags &&
+	    (map->map_type == BPF_MAP_TYPE_QUEUE ||
+	     map->map_type == BPF_MAP_TYPE_STACK)) {
+		err = -EINVAL;
+		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);
 	if (!value)
 		goto free_key;
 
+	err = -ENOTSUPP;
 	if (map->map_type == BPF_MAP_TYPE_QUEUE ||
 	    map->map_type == BPF_MAP_TYPE_STACK) {
 		err = map->ops->map_pop_elem(map, value);
-	} else {
-		err = -ENOTSUPP;
+	} 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();
+		}
 	}
 
 	if (err)
diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index ec6d85a81744..c10ba06af69e 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h
@@ -527,6 +527,15 @@ union bpf_iter_link_info {
  *		Look up an element with the given *key* in the map referred to
  *		by the file descriptor *fd*, and if found, delete the element.
  *
+ *		For **BPF_MAP_TYPE_QUEUE** and **BPF_MAP_TYPE_STACK** map
+ *		types, the *flags* argument needs to be set to 0, but for other
+ *		map types, it may be specified as:
+ *
+ *		**BPF_F_LOCK**
+ *			Look up and delete the value of a spin-locked map
+ *			without returning the lock. This must be specified if
+ *			the elements contain a spinlock.
+ *
  *		The **BPF_MAP_TYPE_QUEUE** and **BPF_MAP_TYPE_STACK** map types
  *		implement this command as a "pop" operation, deleting the top
  *		element rather than one corresponding to *key*.
@@ -536,6 +545,10 @@ union bpf_iter_link_info {
  *		This command is only valid for the following map types:
  *		* **BPF_MAP_TYPE_QUEUE**
  *		* **BPF_MAP_TYPE_STACK**
+ *		* **BPF_MAP_TYPE_HASH**
+ *		* **BPF_MAP_TYPE_PERCPU_HASH**
+ *		* **BPF_MAP_TYPE_LRU_HASH**
+ *		* **BPF_MAP_TYPE_LRU_PERCPU_HASH**
  *
  *	Return
  *		Returns zero on success. On error, -1 is returned and *errno*
-- 
2.26.2

[PATCH v7 bpf-next 2/3] bpf: extend libbpf with bpf_map_lookup_and_delete_elem_flags

[Denis Salopek]

Add bpf_map_lookup_and_delete_elem_flags() libbpf API in order to use
the BPF_F_LOCK flag with the map_lookup_and_delete_elem() function.

Cc: Juraj Vijtiuk <juraj.vijtiuk@sartura.hr>
Cc: Luka Oreskovic <luka.oreskovic@sartura.hr>
Cc: Luka Perkov <luka.perkov@sartura.hr>
Cc: Yonghong Song <yhs@fb.com>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Denis Salopek <denis.salopek@sartura.hr>
Acked-by: Yonghong Song <yhs@fb.com>
---
 tools/lib/bpf/bpf.c      | 13 +++++++++++++
 tools/lib/bpf/bpf.h      |  2 ++
 tools/lib/bpf/libbpf.map |  1 +
 3 files changed, 16 insertions(+)

diff --git a/tools/lib/bpf/bpf.c b/tools/lib/bpf/bpf.c
index bba48ff4c5c0..b7c2cc12034c 100644
--- a/tools/lib/bpf/bpf.c
+++ b/tools/lib/bpf/bpf.c
@@ -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;
diff --git a/tools/lib/bpf/bpf.h b/tools/lib/bpf/bpf.h
index 875dde20d56e..4f758f8f50cd 100644
--- a/tools/lib/bpf/bpf.h
+++ b/tools/lib/bpf/bpf.h
@@ -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);
diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map
index b9b29baf1df8..6c06267c020e 100644
--- a/tools/lib/bpf/libbpf.map
+++ b/tools/lib/bpf/libbpf.map
@@ -360,5 +360,6 @@ LIBBPF_0.4.0 {
 		bpf_linker__free;
 		bpf_linker__new;
 		bpf_map__inner_map;
+		bpf_map_lookup_and_delete_elem_flags;
 		bpf_object__set_kversion;
 } LIBBPF_0.3.0;
-- 
2.26.2

[PATCH v7 bpf-next 3/3] selftests/bpf: add bpf_lookup_and_delete_elem tests

[Denis Salopek]

Add bpf selftests and extend existing ones for a new function
bpf_lookup_and_delete_elem() for (percpu) hash and (percpu) LRU hash map
types.
In test_lru_map and test_maps we add an element, lookup_and_delete it,
then check whether it's deleted.
The newly added lookup_and_delete prog tests practically do the same
thing but additionally use a BPF program to change the value of the
element for LRU maps.

Cc: Juraj Vijtiuk <juraj.vijtiuk@sartura.hr>
Cc: Luka Oreskovic <luka.oreskovic@sartura.hr>
Cc: Luka Perkov <luka.perkov@sartura.hr>
Cc: Yonghong Song <yhs@fb.com>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Denis Salopek <denis.salopek@sartura.hr>
Acked-by: Yonghong Song <yhs@fb.com>
---
 .../bpf/prog_tests/lookup_and_delete.c        | 288 ++++++++++++++++++
 .../bpf/progs/test_lookup_and_delete.c        |  26 ++
 tools/testing/selftests/bpf/test_lru_map.c    |   8 +
 tools/testing/selftests/bpf/test_maps.c       |  17 ++
 4 files changed, 339 insertions(+)
 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

diff --git a/tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c b/tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c
new file mode 100644
index 000000000000..beebfa9730e1
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c
@@ -0,0 +1,288 @@
+// 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;
+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 (!ASSERT_OK(err, "bpf_map_update_elem"))
+			return -1;
+	}
+
+	return 0;
+}
+
+static int fill_values_percpu(int map_fd)
+{
+	__u64 key, value[nr_cpus];
+	int i, err;
+
+	for (i = 0; i < nr_cpus; i++)
+		value[i] = START_VALUE;
+
+	for (key = 1; key < MAX_ENTRIES + 1; key++) {
+		err = bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST);
+		if (!ASSERT_OK(err, "bpf_map_update_elem"))
+			return -1;
+	}
+
+	return 0;
+}
+
+static struct test_lookup_and_delete *setup_prog(enum bpf_map_type map_type,
+						 int *map_fd)
+{
+	struct test_lookup_and_delete *skel;
+	int err;
+
+	skel = test_lookup_and_delete__open();
+	if (!ASSERT_OK_PTR(skel, "test_lookup_and_delete__open"))
+		return NULL;
+
+	err = bpf_map__set_type(skel->maps.hash_map, map_type);
+	if (!ASSERT_OK(err, "bpf_map__set_type"))
+		goto cleanup;
+
+	err = bpf_map__set_max_entries(skel->maps.hash_map, MAX_ENTRIES);
+	if (!ASSERT_OK(err, "bpf_map__set_max_entries"))
+		goto cleanup;
+
+	err = test_lookup_and_delete__load(skel);
+	if (!ASSERT_OK(err, "test_lookup_and_delete__load"))
+		goto cleanup;
+
+	*map_fd = bpf_map__fd(skel->maps.hash_map);
+	if (!ASSERT_GE(*map_fd, 0, "bpf_map__fd"))
+		goto cleanup;
+
+	return skel;
+
+cleanup:
+	test_lookup_and_delete__destroy(skel);
+	return NULL;
+}
+
+/* Triggers BPF program that updates map with given key and value */
+static int trigger_tp(struct test_lookup_and_delete *skel, __u64 key,
+		      __u64 value)
+{
+	int err;
+
+	skel->bss->set_pid = getpid();
+	skel->bss->set_key = key;
+	skel->bss->set_value = value;
+
+	err = test_lookup_and_delete__attach(skel);
+	if (!ASSERT_OK(err, "test_lookup_and_delete__attach"))
+		return -1;
+
+	syscall(__NR_getpgid);
+
+	test_lookup_and_delete__detach(skel);
+
+	return 0;
+}
+
+static void test_lookup_and_delete_hash(void)
+{
+	struct test_lookup_and_delete *skel;
+	__u64 key, value;
+	int map_fd, err;
+
+	/* Setup program and fill the map. */
+	skel = setup_prog(BPF_MAP_TYPE_HASH, &map_fd);
+	if (!ASSERT_OK_PTR(skel, "setup_prog"))
+		return;
+
+	err = fill_values(map_fd);
+	if (!ASSERT_OK(err, "fill_values"))
+		goto cleanup;
+
+	/* Lookup and delete element. */
+	key = 1;
+	err = bpf_map_lookup_and_delete_elem(map_fd, &key, &value);
+	if (!ASSERT_OK(err, "bpf_map_lookup_and_delete_elem"))
+		goto cleanup;
+
+	/* Fetched value should match the initially set value. */
+	if (CHECK(value != START_VALUE, "bpf_map_lookup_and_delete_elem",
+		  "unexpected value=%lld\n", value))
+		goto cleanup;
+
+	/* Check that the entry is non existent. */
+	err = bpf_map_lookup_elem(map_fd, &key, &value);
+	if (!ASSERT_ERR(err, "bpf_map_lookup_elem"))
+		goto cleanup;
+
+cleanup:
+	test_lookup_and_delete__destroy(skel);
+}
+
+static void test_lookup_and_delete_percpu_hash(void)
+{
+	struct test_lookup_and_delete *skel;
+	__u64 key, val, value[nr_cpus];
+	int map_fd, err, i;
+
+	/* Setup program and fill the map. */
+	skel = setup_prog(BPF_MAP_TYPE_PERCPU_HASH, &map_fd);
+	if (!ASSERT_OK_PTR(skel, "setup_prog"))
+		return;
+
+	err = fill_values_percpu(map_fd);
+	if (!ASSERT_OK(err, "fill_values_percpu"))
+		goto cleanup;
+
+	/* Lookup and delete element. */
+	key = 1;
+	err = bpf_map_lookup_and_delete_elem(map_fd, &key, value);
+	if (!ASSERT_OK(err, "bpf_map_lookup_and_delete_elem"))
+		goto cleanup;
+
+	for (i = 0; i < nr_cpus; i++) {
+		val = value[i];
+
+		/* Fetched value should match the initially set value. */
+		if (CHECK(val != START_VALUE, "map value",
+			  "unexpected for cpu %d: %lld\n", i, val))
+			goto cleanup;
+	}
+
+	/* Check that the entry is non existent. */
+	err = bpf_map_lookup_elem(map_fd, &key, value);
+	if (!ASSERT_ERR(err, "bpf_map_lookup_elem"))
+		goto cleanup;
+
+cleanup:
+	test_lookup_and_delete__destroy(skel);
+}
+
+static void test_lookup_and_delete_lru_hash(void)
+{
+	struct test_lookup_and_delete *skel;
+	__u64 key, value;
+	int map_fd, err;
+
+	/* Setup program and fill the LRU map. */
+	skel = setup_prog(BPF_MAP_TYPE_LRU_HASH, &map_fd);
+	if (!ASSERT_OK_PTR(skel, "setup_prog"))
+		return;
+
+	err = fill_values(map_fd);
+	if (!ASSERT_OK(err, "fill_values"))
+		goto cleanup;
+
+	/* Insert new element at key=3, should reuse LRU element. */
+	key = 3;
+	err = trigger_tp(skel, key, NEW_VALUE);
+	if (!ASSERT_OK(err, "trigger_tp"))
+		goto cleanup;
+
+	/* Lookup and delete element 3. */
+	err = bpf_map_lookup_and_delete_elem(map_fd, &key, &value);
+	if (!ASSERT_OK(err, "bpf_map_lookup_and_delete_elem"))
+		goto cleanup;
+
+	/* Value should match the new value. */
+	if (CHECK(value != NEW_VALUE, "bpf_map_lookup_and_delete_elem",
+		  "unexpected value=%lld\n", value))
+		goto cleanup;
+
+	/* Check that entries 3 and 1 are non existent. */
+	err = bpf_map_lookup_elem(map_fd, &key, &value);
+	if (!ASSERT_ERR(err, "bpf_map_lookup_elem"))
+		goto cleanup;
+
+	key = 1;
+	err = bpf_map_lookup_elem(map_fd, &key, &value);
+	if (!ASSERT_ERR(err, "bpf_map_lookup_elem"))
+		goto cleanup;
+
+cleanup:
+	test_lookup_and_delete__destroy(skel);
+}
+
+static void test_lookup_and_delete_lru_percpu_hash(void)
+{
+	struct test_lookup_and_delete *skel;
+	__u64 key, val, value[nr_cpus];
+	int map_fd, err, i, cpucnt = 0;
+
+	/* Setup program and fill the LRU map. */
+	skel = setup_prog(BPF_MAP_TYPE_LRU_PERCPU_HASH, &map_fd);
+	if (!ASSERT_OK_PTR(skel, "setup_prog"))
+		return;
+
+	err = fill_values_percpu(map_fd);
+	if (!ASSERT_OK(err, "fill_values_percpu"))
+		goto cleanup;
+
+	/* Insert new element at key=3, should reuse LRU element 1. */
+	key = 3;
+	err = trigger_tp(skel, key, NEW_VALUE);
+	if (!ASSERT_OK(err, "trigger_tp"))
+		goto cleanup;
+
+	/* Clean value. */
+	for (i = 0; i < nr_cpus; i++)
+		value[i] = 0;
+
+	/* Lookup and delete element 3. */
+	err = bpf_map_lookup_and_delete_elem(map_fd, &key, value);
+	if (!ASSERT_OK(err, "bpf_map_lookup_and_delete_elem")) {
+		goto cleanup;
+	}
+
+	/* Check if only one CPU has set the value. */
+	for (i = 0; i < nr_cpus; i++) {
+		val = value[i];
+		if (val) {
+			if (CHECK(val != NEW_VALUE, "map value",
+				  "unexpected for cpu %d: %lld\n", i, val))
+				goto cleanup;
+			cpucnt++;
+		}
+	}
+	if (CHECK(cpucnt != 1, "map value", "set for %d CPUs instead of 1!\n",
+		  cpucnt))
+		goto cleanup;
+
+	/* Check that entries 3 and 1 are non existent. */
+	err = bpf_map_lookup_elem(map_fd, &key, &value);
+	if (!ASSERT_ERR(err, "bpf_map_lookup_elem"))
+		goto cleanup;
+
+	key = 1;
+	err = bpf_map_lookup_elem(map_fd, &key, &value);
+	if (!ASSERT_ERR(err, "bpf_map_lookup_elem"))
+		goto cleanup;
+
+cleanup:
+	test_lookup_and_delete__destroy(skel);
+}
+
+void test_lookup_and_delete(void)
+{
+	nr_cpus = bpf_num_possible_cpus();
+
+	if (test__start_subtest("lookup_and_delete"))
+		test_lookup_and_delete_hash();
+	if (test__start_subtest("lookup_and_delete_percpu"))
+		test_lookup_and_delete_percpu_hash();
+	if (test__start_subtest("lookup_and_delete_lru"))
+		test_lookup_and_delete_lru_hash();
+	if (test__start_subtest("lookup_and_delete_lru_percpu"))
+		test_lookup_and_delete_lru_percpu_hash();
+}
diff --git a/tools/testing/selftests/bpf/progs/test_lookup_and_delete.c b/tools/testing/selftests/bpf/progs/test_lookup_and_delete.c
new file mode 100644
index 000000000000..3a193f42c7e7
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/test_lookup_and_delete.c
@@ -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";
diff --git a/tools/testing/selftests/bpf/test_lru_map.c b/tools/testing/selftests/bpf/test_lru_map.c
index 6a5349f9eb14..7e9049fa3edf 100644
--- a/tools/testing/selftests/bpf/test_lru_map.c
+++ b/tools/testing/selftests/bpf/test_lru_map.c
@@ -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=1 and delete it, then 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);
diff --git a/tools/testing/selftests/bpf/test_maps.c b/tools/testing/selftests/bpf/test_maps.c
index 51adc42b2b40..8410a730c82f 100644
--- a/tools/testing/selftests/bpf/test_maps.c
+++ b/tools/testing/selftests/bpf/test_maps.c
@@ -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);
 
@@ -166,6 +173,16 @@ static void test_hashmap_percpu(unsigned int task, void *data)
 	/* 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(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. */
-- 
2.26.2

Re: [PATCH v7 bpf-next 0/3] Add lookup_and_delete_elem support to BPF hash map types

[Andrii Nakryiko]

On Tue, May 11, 2021 at 2:01 PM Denis Salopek <denis.salopek@sartura.hr> wrote:
>
> This patch series extends the existing bpf_map_lookup_and_delete_elem()
> functionality with 4 more map types:
>  - BPF_MAP_TYPE_HASH,
>  - BPF_MAP_TYPE_PERCPU_HASH,
>  - BPF_MAP_TYPE_LRU_HASH and
>  - BPF_MAP_TYPE_LRU_PERCPU_HASH.
>
> Patch 1 adds most of its functionality and logic as well as
> documentation.
>
> As it was previously limited to only stacks and queues which do not
> support the BPF_F_LOCK flag, patch 2 enables its usage by adding a new
> libbpf API bpf_map_lookup_and_delete_elem_flags() based on the existing
> bpf_map_lookup_elem_flags().
>
> Patch 3 adds selftests for lookup_and_delete_elem().
>
> Changes in patch 1:
> v7: Minor formating nits, add Acked-by.
> v6: Remove unneeded flag check, minor code/format fixes.
> v5: Split patch to 3 patches. Extend BPF_MAP_LOOKUP_AND_DELETE_ELEM
> documentation with this changes.
> v4: Fix the return value for unsupported map types.
> v3: Add bpf_map_lookup_and_delete_elem_flags() and enable BPF_F_LOCK
> flag, change CHECKs to ASSERT_OKs, initialize variables to 0.
> v2: Add functionality for LRU/per-CPU, add test_progs tests.
>
> Changes in patch 2:
> v7: No change.
> v6: Add Acked-by.
> v5: Move to the newest libbpf version (0.4.0).
>
> Changes in patch 3:
> v7: Remove ASSERT_GE macro which is already added in some other commit,
> change ASSERT_OK to ASSERT_OK_PTR, add Acked-by.
> v6: Remove PERCPU macros, add ASSERT_GE macro to test_progs.h, remove
> leftover code.
> v5: Use more appropriate macros. Better check for changed value.
>
> Denis Salopek (3):
>   bpf: add lookup_and_delete_elem support to hashtab
>   bpf: extend libbpf with bpf_map_lookup_and_delete_elem_flags
>   selftests/bpf: add bpf_lookup_and_delete_elem tests
>
>  include/linux/bpf.h                           |   2 +
>  include/uapi/linux/bpf.h                      |  13 +
>  kernel/bpf/hashtab.c                          |  98 ++++++
>  kernel/bpf/syscall.c                          |  34 ++-
>  tools/include/uapi/linux/bpf.h                |  13 +
>  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        | 288 ++++++++++++++++++
>  .../bpf/progs/test_lookup_and_delete.c        |  26 ++
>  tools/testing/selftests/bpf/test_lru_map.c    |   8 +
>  tools/testing/selftests/bpf/test_maps.c       |  17 ++
>  12 files changed, 511 insertions(+), 4 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
>
> --
> 2.26.2
>

Patchbot is having a bad day...

Applied to bpf-next, thanks. Fixed up a small merge conflict in libbpf.map.

Re: [PATCH v7 bpf-next 0/3] Add lookup_and_delete_elem support to BPF hash map types

[Andrii Nakryiko]

On Mon, May 24, 2021 at 3:02 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Tue, May 11, 2021 at 2:01 PM Denis Salopek <denis.salopek@sartura.hr> wrote:
> >
> > This patch series extends the existing bpf_map_lookup_and_delete_elem()
> > functionality with 4 more map types:
> >  - BPF_MAP_TYPE_HASH,
> >  - BPF_MAP_TYPE_PERCPU_HASH,
> >  - BPF_MAP_TYPE_LRU_HASH and
> >  - BPF_MAP_TYPE_LRU_PERCPU_HASH.
> >
> > Patch 1 adds most of its functionality and logic as well as
> > documentation.
> >
> > As it was previously limited to only stacks and queues which do not
> > support the BPF_F_LOCK flag, patch 2 enables its usage by adding a new
> > libbpf API bpf_map_lookup_and_delete_elem_flags() based on the existing
> > bpf_map_lookup_elem_flags().
> >
> > Patch 3 adds selftests for lookup_and_delete_elem().
> >
> > Changes in patch 1:
> > v7: Minor formating nits, add Acked-by.
> > v6: Remove unneeded flag check, minor code/format fixes.
> > v5: Split patch to 3 patches. Extend BPF_MAP_LOOKUP_AND_DELETE_ELEM
> > documentation with this changes.
> > v4: Fix the return value for unsupported map types.
> > v3: Add bpf_map_lookup_and_delete_elem_flags() and enable BPF_F_LOCK
> > flag, change CHECKs to ASSERT_OKs, initialize variables to 0.
> > v2: Add functionality for LRU/per-CPU, add test_progs tests.
> >
> > Changes in patch 2:
> > v7: No change.
> > v6: Add Acked-by.
> > v5: Move to the newest libbpf version (0.4.0).
> >
> > Changes in patch 3:
> > v7: Remove ASSERT_GE macro which is already added in some other commit,
> > change ASSERT_OK to ASSERT_OK_PTR, add Acked-by.
> > v6: Remove PERCPU macros, add ASSERT_GE macro to test_progs.h, remove
> > leftover code.
> > v5: Use more appropriate macros. Better check for changed value.
> >
> > Denis Salopek (3):
> >   bpf: add lookup_and_delete_elem support to hashtab
> >   bpf: extend libbpf with bpf_map_lookup_and_delete_elem_flags
> >   selftests/bpf: add bpf_lookup_and_delete_elem tests
> >

Hey Denis,

I've noticed a new failure for the tests you added:

setup_prog:PASS:test_lookup_and_delete__open 0 nsec
setup_prog:PASS:bpf_map__set_type 0 nsec
setup_prog:PASS:bpf_map__set_max_entries 0 nsec
setup_prog:PASS:test_lookup_and_delete__load 0 nsec
setup_prog:PASS:bpf_map__fd 0 nsec
test_lookup_and_delete_lru_hash:PASS:setup_prog 0 nsec
fill_values:PASS:bpf_map_update_elem 0 nsec
fill_values:PASS:bpf_map_update_elem 0 nsec
test_lookup_and_delete_lru_hash:PASS:fill_values 0 nsec
trigger_tp:PASS:test_lookup_and_delete__attach 0 nsec
test_lookup_and_delete_lru_hash:PASS:trigger_tp 0 nsec
test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_and_delete_elem 0 nsec
test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_and_delete_elem 0 nsec
test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_elem 0 nsec
test_lookup_and_delete_lru_hash:FAIL:bpf_map_lookup_elem unexpected success: 0
#67/3 lookup_and_delete_lru:FAIL

I haven't seen this before, probably some timing assumptions or
something. Can you please check and see if there is anything we can do
to make the test more reliable?

See https://app.travis-ci.com/github/kernel-patches/bpf/builds/233733889
for the complete test run log. Thanks!


> >  include/linux/bpf.h                           |   2 +
> >  include/uapi/linux/bpf.h                      |  13 +
> >  kernel/bpf/hashtab.c                          |  98 ++++++
> >  kernel/bpf/syscall.c                          |  34 ++-
> >  tools/include/uapi/linux/bpf.h                |  13 +
> >  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        | 288 ++++++++++++++++++
> >  .../bpf/progs/test_lookup_and_delete.c        |  26 ++
> >  tools/testing/selftests/bpf/test_lru_map.c    |   8 +
> >  tools/testing/selftests/bpf/test_maps.c       |  17 ++
> >  12 files changed, 511 insertions(+), 4 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
> >
> > --
> > 2.26.2
> >
>
> Patchbot is having a bad day...
>
> Applied to bpf-next, thanks. Fixed up a small merge conflict in libbpf.map.

Re: [PATCH v7 bpf-next 0/3] Add lookup_and_delete_elem support to BPF hash map types

[Andrii Nakryiko]

On Tue, Jul 27, 2021 at 11:10 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, May 24, 2021 at 3:02 PM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Tue, May 11, 2021 at 2:01 PM Denis Salopek <denis.salopek@sartura.hr> wrote:
> > >
> > > This patch series extends the existing bpf_map_lookup_and_delete_elem()
> > > functionality with 4 more map types:
> > >  - BPF_MAP_TYPE_HASH,
> > >  - BPF_MAP_TYPE_PERCPU_HASH,
> > >  - BPF_MAP_TYPE_LRU_HASH and
> > >  - BPF_MAP_TYPE_LRU_PERCPU_HASH.
> > >
> > > Patch 1 adds most of its functionality and logic as well as
> > > documentation.
> > >
> > > As it was previously limited to only stacks and queues which do not
> > > support the BPF_F_LOCK flag, patch 2 enables its usage by adding a new
> > > libbpf API bpf_map_lookup_and_delete_elem_flags() based on the existing
> > > bpf_map_lookup_elem_flags().
> > >
> > > Patch 3 adds selftests for lookup_and_delete_elem().
> > >
> > > Changes in patch 1:
> > > v7: Minor formating nits, add Acked-by.
> > > v6: Remove unneeded flag check, minor code/format fixes.
> > > v5: Split patch to 3 patches. Extend BPF_MAP_LOOKUP_AND_DELETE_ELEM
> > > documentation with this changes.
> > > v4: Fix the return value for unsupported map types.
> > > v3: Add bpf_map_lookup_and_delete_elem_flags() and enable BPF_F_LOCK
> > > flag, change CHECKs to ASSERT_OKs, initialize variables to 0.
> > > v2: Add functionality for LRU/per-CPU, add test_progs tests.
> > >
> > > Changes in patch 2:
> > > v7: No change.
> > > v6: Add Acked-by.
> > > v5: Move to the newest libbpf version (0.4.0).
> > >
> > > Changes in patch 3:
> > > v7: Remove ASSERT_GE macro which is already added in some other commit,
> > > change ASSERT_OK to ASSERT_OK_PTR, add Acked-by.
> > > v6: Remove PERCPU macros, add ASSERT_GE macro to test_progs.h, remove
> > > leftover code.
> > > v5: Use more appropriate macros. Better check for changed value.
> > >
> > > Denis Salopek (3):
> > >   bpf: add lookup_and_delete_elem support to hashtab
> > >   bpf: extend libbpf with bpf_map_lookup_and_delete_elem_flags
> > >   selftests/bpf: add bpf_lookup_and_delete_elem tests
> > >
>
> Hey Denis,
>
> I've noticed a new failure for the tests you added:
>
> setup_prog:PASS:test_lookup_and_delete__open 0 nsec
> setup_prog:PASS:bpf_map__set_type 0 nsec
> setup_prog:PASS:bpf_map__set_max_entries 0 nsec
> setup_prog:PASS:test_lookup_and_delete__load 0 nsec
> setup_prog:PASS:bpf_map__fd 0 nsec
> test_lookup_and_delete_lru_hash:PASS:setup_prog 0 nsec
> fill_values:PASS:bpf_map_update_elem 0 nsec
> fill_values:PASS:bpf_map_update_elem 0 nsec
> test_lookup_and_delete_lru_hash:PASS:fill_values 0 nsec
> trigger_tp:PASS:test_lookup_and_delete__attach 0 nsec
> test_lookup_and_delete_lru_hash:PASS:trigger_tp 0 nsec
> test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_and_delete_elem 0 nsec
> test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_and_delete_elem 0 nsec
> test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_elem 0 nsec
> test_lookup_and_delete_lru_hash:FAIL:bpf_map_lookup_elem unexpected success: 0
> #67/3 lookup_and_delete_lru:FAIL
>
> I haven't seen this before, probably some timing assumptions or
> something. Can you please check and see if there is anything we can do
> to make the test more reliable?
>
> See https://app.travis-ci.com/github/kernel-patches/bpf/builds/233733889
> for the complete test run log. Thanks!
>

Ping.

>
> > >  include/linux/bpf.h                           |   2 +
> > >  include/uapi/linux/bpf.h                      |  13 +
> > >  kernel/bpf/hashtab.c                          |  98 ++++++
> > >  kernel/bpf/syscall.c                          |  34 ++-
> > >  tools/include/uapi/linux/bpf.h                |  13 +
> > >  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        | 288 ++++++++++++++++++
> > >  .../bpf/progs/test_lookup_and_delete.c        |  26 ++
> > >  tools/testing/selftests/bpf/test_lru_map.c    |   8 +
> > >  tools/testing/selftests/bpf/test_maps.c       |  17 ++
> > >  12 files changed, 511 insertions(+), 4 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
> > >
> > > --
> > > 2.26.2
> > >
> >
> > Patchbot is having a bad day...
> >
> > Applied to bpf-next, thanks. Fixed up a small merge conflict in libbpf.map.

Re: [PATCH v7 bpf-next 0/3] Add lookup_and_delete_elem support to BPF hash map types

[Denis Salopek]

On Tue, Jul 27, 2021 at 11:10:12AM -0700, Andrii Nakryiko wrote:
> On Mon, May 24, 2021 at 3:02 PM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Tue, May 11, 2021 at 2:01 PM Denis Salopek <denis.salopek@sartura.hr> wrote:
> > >
> > > This patch series extends the existing bpf_map_lookup_and_delete_elem()
> > > functionality with 4 more map types:
> > >  - BPF_MAP_TYPE_HASH,
> > >  - BPF_MAP_TYPE_PERCPU_HASH,
> > >  - BPF_MAP_TYPE_LRU_HASH and
> > >  - BPF_MAP_TYPE_LRU_PERCPU_HASH.
> > >
> > > Patch 1 adds most of its functionality and logic as well as
> > > documentation.
> > >
> > > As it was previously limited to only stacks and queues which do not
> > > support the BPF_F_LOCK flag, patch 2 enables its usage by adding a new
> > > libbpf API bpf_map_lookup_and_delete_elem_flags() based on the existing
> > > bpf_map_lookup_elem_flags().
> > >
> > > Patch 3 adds selftests for lookup_and_delete_elem().
> > >
> > > Changes in patch 1:
> > > v7: Minor formating nits, add Acked-by.
> > > v6: Remove unneeded flag check, minor code/format fixes.
> > > v5: Split patch to 3 patches. Extend BPF_MAP_LOOKUP_AND_DELETE_ELEM
> > > documentation with this changes.
> > > v4: Fix the return value for unsupported map types.
> > > v3: Add bpf_map_lookup_and_delete_elem_flags() and enable BPF_F_LOCK
> > > flag, change CHECKs to ASSERT_OKs, initialize variables to 0.
> > > v2: Add functionality for LRU/per-CPU, add test_progs tests.
> > >
> > > Changes in patch 2:
> > > v7: No change.
> > > v6: Add Acked-by.
> > > v5: Move to the newest libbpf version (0.4.0).
> > >
> > > Changes in patch 3:
> > > v7: Remove ASSERT_GE macro which is already added in some other commit,
> > > change ASSERT_OK to ASSERT_OK_PTR, add Acked-by.
> > > v6: Remove PERCPU macros, add ASSERT_GE macro to test_progs.h, remove
> > > leftover code.
> > > v5: Use more appropriate macros. Better check for changed value.
> > >
> > > Denis Salopek (3):
> > >   bpf: add lookup_and_delete_elem support to hashtab
> > >   bpf: extend libbpf with bpf_map_lookup_and_delete_elem_flags
> > >   selftests/bpf: add bpf_lookup_and_delete_elem tests
> > >
> 
> Hey Denis,
> 
> I've noticed a new failure for the tests you added:
> 
> setup_prog:PASS:test_lookup_and_delete__open 0 nsec
> setup_prog:PASS:bpf_map__set_type 0 nsec
> setup_prog:PASS:bpf_map__set_max_entries 0 nsec
> setup_prog:PASS:test_lookup_and_delete__load 0 nsec
> setup_prog:PASS:bpf_map__fd 0 nsec
> test_lookup_and_delete_lru_hash:PASS:setup_prog 0 nsec
> fill_values:PASS:bpf_map_update_elem 0 nsec
> fill_values:PASS:bpf_map_update_elem 0 nsec
> test_lookup_and_delete_lru_hash:PASS:fill_values 0 nsec
> trigger_tp:PASS:test_lookup_and_delete__attach 0 nsec
> test_lookup_and_delete_lru_hash:PASS:trigger_tp 0 nsec
> test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_and_delete_elem 0 nsec
> test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_and_delete_elem 0 nsec
> test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_elem 0 nsec
> test_lookup_and_delete_lru_hash:FAIL:bpf_map_lookup_elem unexpected success: 0
> #67/3 lookup_and_delete_lru:FAIL
> 
> I haven't seen this before, probably some timing assumptions or
> something. Can you please check and see if there is anything we can do
> to make the test more reliable?
> 
> See https://app.travis-ci.com/github/kernel-patches/bpf/builds/233733889
> for the complete test run log. Thanks!

Hello Andrii,

I figured the LRU tests would go like this:
1. We create LRU hash map with 2 elements.
2. We fill both of those elements with a default value (1234) at keys 1
and 2.
3. We trigger the outside BPF program that sets the element at key 3 to
a new value (4321). My initial presumption was that since the map is
full, the new element will cause the 'oldest' one (key = 1) to be
deleted and add the new one, leaving only keys 2 and 3 in the map.
4. We lookup_and_delete the newly added element at key = 3 (so only key
= 2 remains in the map).
5. We check whether key = 3 exists in the map -> it shouldn't and it
doesn't.
6. We check whether key = 1 exists in the map -> it shouldn't, but it
does.

So, the LRU test fails at the last check.

The lookup_and_deleted element at key = 3 is really deleted, as the test
gives us PASS (one line before FAIL), and as that is the point of this
test, I guess we can just skip the last check for the deleted LRU
element?

The LRU_PERCPU test (which passes, by the way) does the same thing as
the LRU test, so we can make the same changes on both of them, if you
agree with the above.

Kind regards,
Denis

> 
> 
> > >  include/linux/bpf.h                           |   2 +
> > >  include/uapi/linux/bpf.h                      |  13 +
> > >  kernel/bpf/hashtab.c                          |  98 ++++++
> > >  kernel/bpf/syscall.c                          |  34 ++-
> > >  tools/include/uapi/linux/bpf.h                |  13 +
> > >  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        | 288 ++++++++++++++++++
> > >  .../bpf/progs/test_lookup_and_delete.c        |  26 ++
> > >  tools/testing/selftests/bpf/test_lru_map.c    |   8 +
> > >  tools/testing/selftests/bpf/test_maps.c       |  17 ++
> > >  12 files changed, 511 insertions(+), 4 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
> > >
> > > --
> > > 2.26.2
> > >
> >
> > Patchbot is having a bad day...
> >
> > Applied to bpf-next, thanks. Fixed up a small merge conflict in libbpf.map.

Re: [PATCH v7 bpf-next 0/3] Add lookup_and_delete_elem support to BPF hash map types

[Andrii Nakryiko]

On Fri, Aug 6, 2021 at 4:29 AM Denis Salopek <denis.salopek@sartura.hr> wrote:
>
> On Tue, Jul 27, 2021 at 11:10:12AM -0700, Andrii Nakryiko wrote:
> > On Mon, May 24, 2021 at 3:02 PM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Tue, May 11, 2021 at 2:01 PM Denis Salopek <denis.salopek@sartura.hr> wrote:
> > > >
> > > > This patch series extends the existing bpf_map_lookup_and_delete_elem()
> > > > functionality with 4 more map types:
> > > >  - BPF_MAP_TYPE_HASH,
> > > >  - BPF_MAP_TYPE_PERCPU_HASH,
> > > >  - BPF_MAP_TYPE_LRU_HASH and
> > > >  - BPF_MAP_TYPE_LRU_PERCPU_HASH.
> > > >
> > > > Patch 1 adds most of its functionality and logic as well as
> > > > documentation.
> > > >
> > > > As it was previously limited to only stacks and queues which do not
> > > > support the BPF_F_LOCK flag, patch 2 enables its usage by adding a new
> > > > libbpf API bpf_map_lookup_and_delete_elem_flags() based on the existing
> > > > bpf_map_lookup_elem_flags().
> > > >
> > > > Patch 3 adds selftests for lookup_and_delete_elem().
> > > >
> > > > Changes in patch 1:
> > > > v7: Minor formating nits, add Acked-by.
> > > > v6: Remove unneeded flag check, minor code/format fixes.
> > > > v5: Split patch to 3 patches. Extend BPF_MAP_LOOKUP_AND_DELETE_ELEM
> > > > documentation with this changes.
> > > > v4: Fix the return value for unsupported map types.
> > > > v3: Add bpf_map_lookup_and_delete_elem_flags() and enable BPF_F_LOCK
> > > > flag, change CHECKs to ASSERT_OKs, initialize variables to 0.
> > > > v2: Add functionality for LRU/per-CPU, add test_progs tests.
> > > >
> > > > Changes in patch 2:
> > > > v7: No change.
> > > > v6: Add Acked-by.
> > > > v5: Move to the newest libbpf version (0.4.0).
> > > >
> > > > Changes in patch 3:
> > > > v7: Remove ASSERT_GE macro which is already added in some other commit,
> > > > change ASSERT_OK to ASSERT_OK_PTR, add Acked-by.
> > > > v6: Remove PERCPU macros, add ASSERT_GE macro to test_progs.h, remove
> > > > leftover code.
> > > > v5: Use more appropriate macros. Better check for changed value.
> > > >
> > > > Denis Salopek (3):
> > > >   bpf: add lookup_and_delete_elem support to hashtab
> > > >   bpf: extend libbpf with bpf_map_lookup_and_delete_elem_flags
> > > >   selftests/bpf: add bpf_lookup_and_delete_elem tests
> > > >
> >
> > Hey Denis,
> >
> > I've noticed a new failure for the tests you added:
> >
> > setup_prog:PASS:test_lookup_and_delete__open 0 nsec
> > setup_prog:PASS:bpf_map__set_type 0 nsec
> > setup_prog:PASS:bpf_map__set_max_entries 0 nsec
> > setup_prog:PASS:test_lookup_and_delete__load 0 nsec
> > setup_prog:PASS:bpf_map__fd 0 nsec
> > test_lookup_and_delete_lru_hash:PASS:setup_prog 0 nsec
> > fill_values:PASS:bpf_map_update_elem 0 nsec
> > fill_values:PASS:bpf_map_update_elem 0 nsec
> > test_lookup_and_delete_lru_hash:PASS:fill_values 0 nsec
> > trigger_tp:PASS:test_lookup_and_delete__attach 0 nsec
> > test_lookup_and_delete_lru_hash:PASS:trigger_tp 0 nsec
> > test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_and_delete_elem 0 nsec
> > test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_and_delete_elem 0 nsec
> > test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_elem 0 nsec
> > test_lookup_and_delete_lru_hash:FAIL:bpf_map_lookup_elem unexpected success: 0
> > #67/3 lookup_and_delete_lru:FAIL
> >
> > I haven't seen this before, probably some timing assumptions or
> > something. Can you please check and see if there is anything we can do
> > to make the test more reliable?
> >
> > See https://app.travis-ci.com/github/kernel-patches/bpf/builds/233733889
> > for the complete test run log. Thanks!
>
> Hello Andrii,
>
> I figured the LRU tests would go like this:
> 1. We create LRU hash map with 2 elements.
> 2. We fill both of those elements with a default value (1234) at keys 1
> and 2.
> 3. We trigger the outside BPF program that sets the element at key 3 to
> a new value (4321). My initial presumption was that since the map is
> full, the new element will cause the 'oldest' one (key = 1) to be
> deleted and add the new one, leaving only keys 2 and 3 in the map.
> 4. We lookup_and_delete the newly added element at key = 3 (so only key
> = 2 remains in the map).
> 5. We check whether key = 3 exists in the map -> it shouldn't and it
> doesn't.
> 6. We check whether key = 1 exists in the map -> it shouldn't, but it
> does.
>
> So, the LRU test fails at the last check.
>
> The lookup_and_deleted element at key = 3 is really deleted, as the test
> gives us PASS (one line before FAIL), and as that is the point of this
> test, I guess we can just skip the last check for the deleted LRU
> element?

Of course not. The test that wasn't supposed to fail fails, we can't
just remove "inconvenient" check. Checking kernel code it's not clear
how we might end up with "resurrected" element. Very strange. This
doesn't happen often, so I'll keep the test as is. If we get this
again, we should look into this much more.

Thanks for investigating!

>
> The LRU_PERCPU test (which passes, by the way) does the same thing as
> the LRU test, so we can make the same changes on both of them, if you
> agree with the above.
>
> Kind regards,
> Denis
>
> >
> >
> > > >  include/linux/bpf.h                           |   2 +
> > > >  include/uapi/linux/bpf.h                      |  13 +
> > > >  kernel/bpf/hashtab.c                          |  98 ++++++
> > > >  kernel/bpf/syscall.c                          |  34 ++-
> > > >  tools/include/uapi/linux/bpf.h                |  13 +
> > > >  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        | 288 ++++++++++++++++++
> > > >  .../bpf/progs/test_lookup_and_delete.c        |  26 ++
> > > >  tools/testing/selftests/bpf/test_lru_map.c    |   8 +
> > > >  tools/testing/selftests/bpf/test_maps.c       |  17 ++
> > > >  12 files changed, 511 insertions(+), 4 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
> > > >
> > > > --
> > > > 2.26.2
> > > >
> > >
> > > Patchbot is having a bad day...
> > >
> > > Applied to bpf-next, thanks. Fixed up a small merge conflict in libbpf.map.