Skip to contentSkip to conversation

bpf: Introduce resizable hash map

RFC PATCH Superseded Mykyta Yatsenko 3 participants 19 messages Feb 5 – Feb 11

Subsystems (7)
Kselftest BPF BPF selftests BPF core +3 more subsystems

v1 of 7 Superseded Latest is v7 →

lore
Share & tools
lore
#0 lore raw

cover bpf: Introduce resizable hash map

This patch series introduces BPF_MAP_TYPE_RHASH, a new hash map type that leverages the kernel's rhashtable to provide resizable hash map for BPF.

The existing BPF_MAP_TYPE_HASH uses a fixed number of buckets determined at map creation time. While this works well for many use cases, it presents challenges when:

1. The number of elements is unknown at creation time
2. The element count varies significantly during runtime
3. Memory efficiency is important (over-provisioning wastes memory, under-provisioning hurts performance)

BPF_MAP_TYPE_RHASH addresses these issues by using rhashtable, which automatically grows and shrinks based on load factor.

The implementation wraps the kernel's rhashtable with BPF map operations:

- Uses bpf_mem_alloc for RCU-safe memory management
- Supports all standard map operations (lookup, update, delete, get_next_key)
- Supports batch operations (lookup_batch, lookup_and_delete_batch)
- Supports BPF iterators for traversal
- Supports BPF_F_LOCK for spin locks in values
- Requires BPF_F_NO_PREALLOC flag (elements allocated on demand)
- max_entries serves as a hard limit, not bucket count

The series includes comprehensive tests:
- Basic operations in test_maps (lookup, update, delete, get_next_key)
- BPF program tests for lookup/update/delete semantics
- BPF_F_LOCK tests with concurrent access
- Stress tests for get_next_key during concurrent resize operations
- Seq file tests

---
Mykyta Yatsenko (12):
bpf: Register rhash map
bpf: Implement basic functions for resizable hashtab
bpf: Implement batch ops and BPF iterator for resizable hashtab
bpf: Reject resizable hash map in tracing progs
libbpf: Support resizable hashtable
selftests/bpf: Add basic tests for resizable hash map selftests/bpf: Support resizable hashtab in test_maps selftests/bpf: Resizable hashtab BPF_F_LOCK tests selftests/bpf: Add stress tests for resizable hash get_next_key selftests/bpf: Add BPF iterator tests for resizable hash map selftests/bpf: Verify resizable hash map is rejected in tracing progs
bpftool: Add rhash map documentation

 include/linux/bpf_types.h                          |   1 +
 include/uapi/linux/bpf.h                           |   1 +
 kernel/bpf/hashtab.c                               | 717 +++++++++++++++++++++
 kernel/bpf/map_iter.c                              |   3 +-
 kernel/bpf/syscall.c                               |   3 +
 kernel/bpf/verifier.c                              |   8 +
 tools/bpf/bpftool/Documentation/bpftool-map.rst    |   2 +-
 tools/bpf/bpftool/map.c                            |   2 +-
 tools/include/uapi/linux/bpf.h                     |   1 +
 tools/lib/bpf/libbpf.c                             |   1 +
 tools/lib/bpf/libbpf_probes.c                      |   3 +
 .../selftests/bpf/map_tests/htab_map_batch_ops.c   |  22 +-
 tools/testing/selftests/bpf/prog_tests/rhash.c     | 485 ++++++++++++++
 tools/testing/selftests/bpf/prog_tests/verifier.c  |   2 +
 .../selftests/bpf/progs/bpf_iter_bpf_rhash_map.c   |  75 +++
 tools/testing/selftests/bpf/progs/rhash.c          | 292 +++++++++
 tools/testing/selftests/bpf/progs/verifier_rhash.c | 112 ++++
 tools/testing/selftests/bpf/test_maps.c            | 107 ++-
 18 files changed, 1802 insertions(+), 35 deletions(-)

---
base-commit: 75cd3beb64d0977009e3d1a2d0c03715d3e5e156
change-id: 20251103-rhash-7b70069923d8

Best regards,

Signature · 1 line
Mykyta Yatsenko <[email protected]>
#1 lore raw

RFC PATCH 1/12 bpf: Register rhash map

From: Mykyta Yatsenko <[email protected]>

Add resizable hash map into enums where it is needed.

---
 include/linux/bpf_types.h      | 1 +
 include/uapi/linux/bpf.h       | 1 +
 kernel/bpf/map_iter.c          | 3 ++-
 kernel/bpf/syscall.c           | 3 +++
 kernel/bpf/verifier.c          | 1 +
 tools/include/uapi/linux/bpf.h | 1 +
 6 files changed, 9 insertions(+), 1 deletion(-)
include/linux/bpf_types.h +1 -0
index b13de31e163f84ca81967e0ee91b290ad4082917..56e4c3f983d34a7efc6d0f3fecf2ae001dfac059 100644
@@ -134,6 +134,7 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_BLOOM_FILTER, bloom_filter_map_ops)
 BPF_MAP_TYPE(BPF_MAP_TYPE_USER_RINGBUF, user_ringbuf_map_ops)
 BPF_MAP_TYPE(BPF_MAP_TYPE_ARENA, arena_map_ops)
 BPF_MAP_TYPE(BPF_MAP_TYPE_INSN_ARRAY, insn_array_map_ops)
+BPF_MAP_TYPE(BPF_MAP_TYPE_RHASH, rhtab_map_ops)
 
 BPF_LINK_TYPE(BPF_LINK_TYPE_RAW_TRACEPOINT, raw_tracepoint)
 BPF_LINK_TYPE(BPF_LINK_TYPE_TRACING, tracing)
include/uapi/linux/bpf.h +1 -0
index c8d400b7680a81236f1b352b38fef4bdc099cfb5..8910270fa9bcdc68f4b5636e4992850a9eb98542 100644
@@ -1046,6 +1046,7 @@ enum bpf_map_type {
 	BPF_MAP_TYPE_CGRP_STORAGE,
 	BPF_MAP_TYPE_ARENA,
 	BPF_MAP_TYPE_INSN_ARRAY,
+	BPF_MAP_TYPE_RHASH,
 	__MAX_BPF_MAP_TYPE
 };
 
kernel/bpf/map_iter.c +2 -1
index 261a03ea73d3497e9b56a4e587b651aaa55aa32d..4a2aafbe28b4affeb7e12560396262da9f732051 100644
@@ -119,7 +119,8 @@ static int bpf_iter_attach_map(struct bpf_prog *prog,
 		is_percpu = true;
 	else if (map->map_type != BPF_MAP_TYPE_HASH &&
 		 map->map_type != BPF_MAP_TYPE_LRU_HASH &&
-		 map->map_type != BPF_MAP_TYPE_ARRAY)
+		 map->map_type != BPF_MAP_TYPE_ARRAY &&
+		 map->map_type != BPF_MAP_TYPE_RHASH)
 		goto put_map;
 
 	key_acc_size = prog->aux->max_rdonly_access;
kernel/bpf/syscall.c +3 -0
index 5f59dd47a5b1c3b80652dabd64ad7853ac1db083..40c58957ac5bf36b2e6c6d765329fcfb5b4f6d3d 100644
@@ -1286,6 +1286,7 @@ static int map_check_btf(struct bpf_map *map, struct bpf_token *token,
 			case BPF_SPIN_LOCK:
 			case BPF_RES_SPIN_LOCK:
 				if (map->map_type != BPF_MAP_TYPE_HASH &&
+				    map->map_type != BPF_MAP_TYPE_RHASH &&
 				    map->map_type != BPF_MAP_TYPE_ARRAY &&
 				    map->map_type != BPF_MAP_TYPE_CGROUP_STORAGE &&
 				    map->map_type != BPF_MAP_TYPE_SK_STORAGE &&
@@ -1463,6 +1464,7 @@ static int map_create(union bpf_attr *attr, bpfptr_t uattr)
 	case BPF_MAP_TYPE_CGROUP_ARRAY:
 	case BPF_MAP_TYPE_ARRAY_OF_MAPS:
 	case BPF_MAP_TYPE_HASH:
+	case BPF_MAP_TYPE_RHASH:
 	case BPF_MAP_TYPE_PERCPU_HASH:
 	case BPF_MAP_TYPE_HASH_OF_MAPS:
 	case BPF_MAP_TYPE_RINGBUF:
@@ -2198,6 +2200,7 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr)
 		   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 ||
+		   map->map_type == BPF_MAP_TYPE_RHASH ||
 		   map->map_type == BPF_MAP_TYPE_STACK_TRACE) {
 		if (!bpf_map_is_offloaded(map)) {
 			bpf_disable_instrumentation();
kernel/bpf/verifier.c +1 -0
index edf5342b982f676567579ed6349ccd5391eee7c8..0803dca3d93f9e912824aa89951cb5b65e961af9 100644
@@ -21558,6 +21558,7 @@ static int check_map_prog_compatibility(struct bpf_verifier_env *env,
 	if (prog->sleepable)
 		switch (map->map_type) {
 		case BPF_MAP_TYPE_HASH:
+		case BPF_MAP_TYPE_RHASH:
 		case BPF_MAP_TYPE_LRU_HASH:
 		case BPF_MAP_TYPE_ARRAY:
 		case BPF_MAP_TYPE_PERCPU_HASH:
tools/include/uapi/linux/bpf.h +1 -0
index 5e38b4887de6ae59fe0a62511757be2d1019eded..7e158396ca42f295b7c7358d74e860564ceaf2bb 100644
@@ -1046,6 +1046,7 @@ enum bpf_map_type {
 	BPF_MAP_TYPE_CGRP_STORAGE,
 	BPF_MAP_TYPE_ARENA,
 	BPF_MAP_TYPE_INSN_ARRAY,
+	BPF_MAP_TYPE_RHASH,
 	__MAX_BPF_MAP_TYPE
 };
 
Signature · 1 line
2.53.0
#2 lore raw

Re: [PATCH RFC bpf-next 01/12] bpf: Register rhash map

This references rhtab_map_ops which is not defined until the next commit (f027f41d1 "bpf: Implement basic functions for resizable hashtab").

include/linux/bpf_types.h BPF_MAP_TYPE(BPF_MAP_TYPE_BLOOM_FILTER, bloom_filter_map_ops) · line 137

Quoted 9 lines
include/linux/bpf_types.h +1 -0
index b13de31e1..56e4c3f98 100644
@@ -134,6 +134,7 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_BLOOM_FILTER, bloom_filter_map_ops)
 BPF_MAP_TYPE(BPF_MAP_TYPE_USER_RINGBUF, user_ringbuf_map_ops)
 BPF_MAP_TYPE(BPF_MAP_TYPE_ARENA, arena_map_ops)
 BPF_MAP_TYPE(BPF_MAP_TYPE_INSN_ARRAY, insn_array_map_ops)
+BPF_MAP_TYPE(BPF_MAP_TYPE_RHASH, rhtab_map_ops)

This references rhtab_map_ops which is not defined until the next commit (f027f41d1 "bpf: Implement basic functions for resizable hashtab").

The BPF_MAP_TYPE macro expands to an array initializer in kernel/bpf/syscall.c:

    #define BPF_MAP_TYPE(_id, _ops) \
        [_id] = &_ops,
    #include <linux/bpf_types.h>

This causes a build failure at this commit due to the undefined symbol. Should this commit be reordered to come after the one that defines rhtab_map_ops to maintain bisectability?

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/21727734472

AI-authorship-score: low
AI-authorship-explanation: The commit message is characteristically terse in kernel style, and the code changes are simple mechanical additions following existing patterns, consistent with experienced kernel developer practices.
issues-found: 1
issue-severity-score: medium
issue-severity-explanation: Build breakage due to undefined symbol rhtab_map_ops breaks bisectability, though it is fixed in the immediately following commit in the series.

#3 lore raw

RFC PATCH 2/12 bpf: Implement basic functions for resizable hashtab

In reply to Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

Introduce basic operations for BPF_MAP_TYPE_RHASH, a new hash map type built on top of the kernel's rhashtable.

Key implementation details:
- Uses rhashtable for automatic resizing with RCU-safe operations
- Elements allocated via bpf_mem_alloc for lock-free allocation
- Supports BPF_F_LOCK for spin_lock protected values
- Requires BPF_F_NO_PREALLOC

Implemented map operations:
* map_alloc/map_free: Initialize and destroy the rhashtable
* map_lookup_elem: RCU-protected lookup via rhashtable_lookup
* map_update_elem: Insert or update with BPF_NOEXIST/EXIST/ANY
* map_delete_elem: Remove element with RCU-deferred freeing
* map_get_next_key: Returns the next key in the table
* map_release_uref: Free internal structs (timers, workqueues)

Other operations (batch, seq file) are implemented in the next patch

---
 kernel/bpf/hashtab.c | 502 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 502 insertions(+)
kernel/bpf/hashtab.c +502 -0
index 3b9d297a53bee5b3d1c6001ed12b55b4b1a6b6d1..917f8f7d70c9ce265c13751e17e3b0bb4b598c45 100644
@@ -9,6 +9,7 @@
 #include <linux/rculist_nulls.h>
 #include <linux/rcupdate_wait.h>
 #include <linux/random.h>
+#include <linux/rhashtable.h>
 #include <uapi/linux/btf.h>
 #include <linux/rcupdate_trace.h>
 #include <linux/btf_ids.h>
@@ -413,6 +414,7 @@ static int htab_map_alloc_check(union bpf_attr *attr)
 	bool percpu_lru = (attr->map_flags & BPF_F_NO_COMMON_LRU);
 	bool prealloc = !(attr->map_flags & BPF_F_NO_PREALLOC);
 	bool zero_seed = (attr->map_flags & BPF_F_ZERO_SEED);
+	bool resizable = attr->map_type == BPF_MAP_TYPE_RHASH;
 	int numa_node = bpf_map_attr_numa_node(attr);
 
 	BUILD_BUG_ON(offsetof(struct htab_elem, fnode.next) !=
@@ -454,6 +456,9 @@ static int htab_map_alloc_check(union bpf_attr *attr)
 	if (percpu && round_up(attr->value_size, 8) > PCPU_MIN_UNIT_SIZE)
 		return -E2BIG;
 
+	if (resizable && percpu_lru)
+		return -EINVAL;
+
 	return 0;
 }
 
@@ -2649,3 +2654,500 @@ const struct bpf_map_ops htab_of_maps_map_ops = {
 	BATCH_OPS(htab),
 	.map_btf_id = &htab_map_btf_ids[0],
 };
+
+struct rhtab_elem {
+	struct rhash_head node;
+	u32 key_len;
+	/* key bytes, then value bytes follow */
+	u8 data[] __aligned(8);
+};
+
+struct bpf_rhtab {
+	struct bpf_map map;
+	struct rhashtable ht;
+	struct rhashtable_params params;
+	struct bpf_mem_alloc ma;
+	u32 elem_size;
+};
+
+static inline void *rhtab_elem_value(struct rhtab_elem *l)
+{
+	return l->data + round_up(l->key_len, 8);
+}
+
+static void rhtab_read_elem_value(struct bpf_map *map, void *dst, struct rhtab_elem *elem,
+				  u64 flags)
+{
+	void *src = rhtab_elem_value(elem);
+
+	if (flags & BPF_F_LOCK)
+		copy_map_value_locked(map, dst, src, true);
+	else
+		copy_map_value(map, dst, src);
+}
+
+static int rhtab_delete_elem(struct bpf_rhtab *rhtab, struct rhtab_elem *elem)
+{
+	int err;
+
+	err = rhashtable_remove_fast(&rhtab->ht, &elem->node, rhtab->params);
+	if (err)
+		return err;
+
+	bpf_map_free_internal_structs(&rhtab->map, rhtab_elem_value(elem));
+	bpf_mem_cache_free_rcu(&rhtab->ma, elem);
+	return 0;
+}
+
+static u32 bpf_rhtab_hash_obj(const void *obj, u32 len, u32 seed)
+{
+	const struct rhtab_elem *e = obj;
+
+	return jhash(e->data, e->key_len, seed);
+}
+
+static u32 bpf_rhtab_hash_key(const void *obj, u32 len, u32 seed)
+{
+	return jhash(obj, len, seed);
+}
+
+static int bpf_rhtab_cmp(struct rhashtable_compare_arg *arg, const void *obj)
+{
+	const struct rhtab_elem *e = obj;
+
+	return memcmp(e->data, arg->key, e->key_len);
+}
+
+/* Helper to get next element, handling -EAGAIN during resize */
+static struct rhtab_elem *rhtab_iter_next(struct rhashtable_iter *iter)
+{
+	struct rhtab_elem *elem;
+
+	while ((elem = rhashtable_walk_next(iter))) {
+		if (IS_ERR(elem)) {
+			if (PTR_ERR(elem) == -EAGAIN)
+				continue;
+			return NULL;
+		}
+		return elem;
+	}
+
+	return NULL;
+}
+
+static int rhtab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
+{
+	struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
+	struct rhash_head *he;
+	unsigned int slot;
+	struct rhtab_elem *elem;
+	bool found = false;
+	struct bucket_table *tbl;
+
+	guard(rcu)();
+
+	tbl = rht_dereference_rcu(rhtab->ht.tbl, &rhtab->ht);
+restart:
+	if (!tbl)
+		return -ENOENT;
+
+	slot = (key && !found) ? rht_key_hashfn(&rhtab->ht, tbl, key, rhtab->params) : 0;
+	for (; slot < tbl->size; ++slot) {
+		rht_for_each_rcu(he, tbl, slot) {
+			elem = container_of(he, struct rhtab_elem, node);
+			if (found || !key) {
+				memcpy(next_key, elem->data, map->key_size);
+				return 0;
+			} else if (memcmp(elem->data, key, map->key_size) == 0) {
+				found = true;
+			}
+		}
+		/* if key is not found in this table, search future_tbl */
+		if (key && !found)
+			break;
+	}
+	tbl = rht_dereference_rcu(tbl->future_tbl, &rhtab->ht);
+	if (tbl)
+		goto restart;
+
+	/* Key not found, wrap to first element */
+	if (key && !found) {
+		tbl = rht_dereference_rcu(rhtab->ht.tbl, &rhtab->ht);
+		key = NULL;
+		goto restart;
+	}
+
+	return -ENOENT;
+}
+
+static struct bpf_map *rhtab_map_alloc(union bpf_attr *attr)
+{
+	struct bpf_rhtab *rhtab;
+	int err = 0;
+
+	rhtab = bpf_map_area_alloc(sizeof(*rhtab), NUMA_NO_NODE);
+	if (!rhtab)
+		return ERR_PTR(-ENOMEM);
+
+	bpf_map_init_from_attr(&rhtab->map, attr);
+
+	if (rhtab->map.max_entries > 1UL << 31) {
+		err = -E2BIG;
+		goto free_rhtab;
+	}
+
+	rhtab->elem_size = sizeof(struct rhtab_elem) + round_up(rhtab->map.key_size, 8) +
+			   round_up(rhtab->map.value_size, 8);
+
+	rhtab->params.head_offset = offsetof(struct rhtab_elem, node);
+	rhtab->params.hashfn = bpf_rhtab_hash_key;
+	rhtab->params.obj_hashfn = bpf_rhtab_hash_obj;
+	rhtab->params.obj_cmpfn = bpf_rhtab_cmp;
+	rhtab->params.key_len = rhtab->map.key_size;
+
+	err = rhashtable_init(&rhtab->ht, &rhtab->params);
+	if (err)
+		goto free_rhtab;
+
+	/* Set max_elems after rhashtable_init() since init zeroes the struct */
+	rhtab->ht.max_elems = rhtab->map.max_entries;
+
+	err = bpf_mem_alloc_init(&rhtab->ma, rhtab->elem_size, false);
+	if (err)
+		goto destroy_rhtab;
+
+	return &rhtab->map;
+
+destroy_rhtab:
+	rhashtable_destroy(&rhtab->ht);
+free_rhtab:
+	bpf_map_area_free(rhtab);
+	return ERR_PTR(err);
+}
+
+static void rhtab_free_elem(void *ptr, void *arg)
+{
+	struct bpf_rhtab *rhtab = arg;
+	struct rhtab_elem *elem = ptr;
+
+	bpf_map_free_internal_structs(&rhtab->map, rhtab_elem_value(elem));
+	bpf_mem_cache_free_rcu(&rhtab->ma, elem);
+}
+
+static void rhtab_map_free(struct bpf_map *map)
+{
+	struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
+
+	rhashtable_free_and_destroy(&rhtab->ht, rhtab_free_elem, rhtab);
+	bpf_mem_alloc_destroy(&rhtab->ma);
+	bpf_map_area_free(rhtab);
+}
+
+static void *__rhtab_map_lookup_elem(struct bpf_map *map, void *key)
+{
+	struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
+
+	return rhashtable_lookup_fast(&rhtab->ht, key, rhtab->params);
+}
+
+static void *rhtab_map_lookup_elem(struct bpf_map *map, void *key) __must_hold(RCU)
+{
+	struct rhtab_elem *l;
+
+	l = __rhtab_map_lookup_elem(map, key);
+	return l ? rhtab_elem_value(l) : NULL;
+}
+
+static int rhtab_map_alloc_check(union bpf_attr *attr)
+{
+	if (!(attr->map_flags & BPF_F_NO_PREALLOC))
+		return -EINVAL;
+
+	return htab_map_alloc_check(attr);
+}
+
+static void rhtab_map_free_internal_structs(struct bpf_map *map)
+{
+	struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
+	struct rhtab_elem *elem;
+	struct bucket_table *tbl;
+	struct rhash_head *he;
+	unsigned int slot;
+
+	if (!bpf_map_has_internal_structs(map))
+		return;
+
+	guard(rcu)();
+
+	/*
+	 * An element can be processed twice if rhashtable resized concurrently
+	 * Special structs freeing handles duplicate cancel_and_free.
+	 */
+
+	tbl = rht_dereference_rcu(rhtab->ht.tbl, &rhtab->ht);
+restart:
+	for (slot = 0; slot < tbl->size; ++slot) {
+		rht_for_each_rcu(he, tbl, slot) {
+			elem = container_of(he, struct rhtab_elem, node);
+			bpf_map_free_internal_structs(map, rhtab_elem_value(elem));
+		}
+	}
+	tbl = rht_dereference_rcu(tbl->future_tbl, &rhtab->ht);
+	if (tbl)
+		goto restart;
+}
+
+static int rhtab_map_lookup_and_delete_elem(struct bpf_map *map, void *key, void *value, u64 flags)
+{
+	struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
+	struct rhtab_elem *l;
+
+	if ((flags & ~BPF_F_LOCK) ||
+	    ((flags & BPF_F_LOCK) && !btf_record_has_field(map->record, BPF_SPIN_LOCK)))
+		return -EINVAL;
+
+	/* Make sure element is not deleted between lookup and copy */
+	guard(rcu)();
+
+	l = __rhtab_map_lookup_elem(map, key);
+	if (!l)
+		return -ENOENT;
+
+	rhtab_read_elem_value(map, value, l, flags);
+	check_and_init_map_value(map, value);
+
+	return rhtab_delete_elem(rhtab, l);
+}
+
+static long rhtab_map_update_existing(struct bpf_map *map, struct rhtab_elem *elem, void *value,
+				      u64 map_flags)
+{
+	if (map_flags & BPF_NOEXIST)
+		return -EEXIST;
+
+	if (map_flags & BPF_F_LOCK)
+		copy_map_value_locked(map, rhtab_elem_value(elem), value, false);
+	else
+		copy_map_value(map, rhtab_elem_value(elem), value);
+	return 0;
+}
+
+static long rhtab_map_update_elem(struct bpf_map *map, void *key, void *value, u64 map_flags)
+{
+	struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
+	struct rhtab_elem *elem, *tmp;
+
+	if (unlikely((map_flags & ~BPF_F_LOCK) > BPF_EXIST))
+		return -EINVAL;
+
+	if ((map_flags & BPF_F_LOCK) && !btf_record_has_field(map->record, BPF_SPIN_LOCK))
+		return -EINVAL;
+
+	guard(rcu)();
+	elem = __rhtab_map_lookup_elem(map, key);
+	if (elem)
+		return rhtab_map_update_existing(map, elem, value, map_flags);
+
+	if (map_flags & BPF_EXIST)
+		return -ENOENT;
+
+	/* Check max_entries limit before inserting new element */
+	if (atomic_read(&rhtab->ht.nelems) >= map->max_entries)
+		return -E2BIG;
+
+	elem = bpf_mem_cache_alloc(&rhtab->ma);
+	if (!elem)
+		return -ENOMEM;
+
+	elem->key_len = map->key_size;
+	memcpy(elem->data, key, map->key_size);
+	copy_map_value(map, rhtab_elem_value(elem), value);
+
+	tmp = rhashtable_lookup_get_insert_key(&rhtab->ht, key, &elem->node, rhtab->params);
+	if (tmp) {
+		bpf_mem_cache_free(&rhtab->ma, elem);
+		if (IS_ERR(tmp))
+			return PTR_ERR(tmp);
+
+		return rhtab_map_update_existing(map, tmp, value, map_flags);
+	}
+
+	return 0;
+}
+
+static long rhtab_map_delete_elem(struct bpf_map *map, void *key)
+{
+	struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
+	struct rhtab_elem *l;
+
+	guard(rcu)();
+	l = __rhtab_map_lookup_elem(map, key);
+	return l ? rhtab_delete_elem(rhtab, l) : -ENOENT;
+}
+
+static int rhtab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
+{
+	struct bpf_insn *insn = insn_buf;
+	const int ret = BPF_REG_0;
+
+	BUILD_BUG_ON(!__same_type(&__rhtab_map_lookup_elem,
+				  (void *(*)(struct bpf_map *map, void *key)) NULL));
+	*insn++ = BPF_EMIT_CALL(__rhtab_map_lookup_elem);
+	*insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1);
+	*insn++ = BPF_ALU64_IMM(BPF_ADD, ret,
+				offsetof(struct rhtab_elem, data) + round_up(map->key_size, 8));
+
+	return insn - insn_buf;
+}
+
+static void rhtab_map_seq_show_elem(struct bpf_map *map, void *key, struct seq_file *m)
+{
+	void *value;
+
+	/* Guarantee that hashtab value is not freed */
+	guard(rcu)();
+
+	value = rhtab_map_lookup_elem(map, key);
+	if (!value)
+		return;
+
+	btf_type_seq_show(map->btf, map->btf_key_type_id, key, m);
+	seq_puts(m, ": ");
+	btf_type_seq_show(map->btf, map->btf_value_type_id, value, m);
+	seq_putc(m, '\n');
+}
+
+static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn, void *callback_ctx,
+				u64 flags)
+{
+	struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
+	struct bucket_table *tbl;
+	struct rhtab_elem *elem;
+	struct rhash_head *he;
+	int num_elems = 0;
+	unsigned int slot;
+	void *key, *val;
+	u64 ret = 0;
+
+	cant_migrate();
+
+	if (flags)
+		return -EINVAL;
+
+	guard(rcu)();
+
+	/*
+	 * An element can be processed twice or skipped,
+	 * if hash map is being resized concurrently
+	 */
+
+	tbl = rht_dereference_rcu(rhtab->ht.tbl, &rhtab->ht);
+retry:
+	for (slot = 0; slot < tbl->size; slot++) {
+		rht_for_each_rcu(he, tbl, slot) {
+			elem = container_of(he, struct rhtab_elem, node);
+			key = elem->data;
+			val = rhtab_elem_value(elem);
+			num_elems++;
+			ret = callback_fn((u64)(long)map, (u64)(long)key, (u64)(long)val,
+					  (u64)(long)callback_ctx, 0);
+			/* return value: 0 - continue, 1 - stop and return */
+			if (ret)
+				return num_elems;
+		}
+	}
+	tbl = rht_dereference_rcu(tbl->future_tbl, &rhtab->ht);
+	if (tbl)
+		goto retry;
+
+	return num_elems;
+}
+
+static u64 rhtab_map_mem_usage(const struct bpf_map *map)
+{
+	return 0;
+}
+
+static int rhtab_map_lookup_batch(struct bpf_map *map, const union bpf_attr *attr,
+				  union bpf_attr __user *uattr)
+{
+	return 0;
+}
+
+static int rhtab_map_lookup_and_delete_batch(struct bpf_map *map, const union bpf_attr *attr,
+					     union bpf_attr __user *uattr)
+{
+	return 0;
+}
+
+struct bpf_iter_seq_rhash_map_info {
+	struct bpf_map *map;
+	struct bpf_rhtab *rhtab;
+	struct rhashtable_iter iter;
+	u32 skip_elems;
+	bool iter_active;
+};
+
+static void *bpf_rhash_map_seq_start(struct seq_file *seq, loff_t *pos)
+{
+	return NULL;
+}
+
+static void *bpf_rhash_map_seq_next(struct seq_file *seq, void *v, loff_t *pos)
+{
+	return NULL;
+}
+
+static int bpf_rhash_map_seq_show(struct seq_file *seq, void *v)
+{
+	return 0;
+}
+
+static void bpf_rhash_map_seq_stop(struct seq_file *seq, void *v)
+{
+}
+
+static int bpf_iter_init_rhash_map(void *priv_data, struct bpf_iter_aux_info *aux)
+{
+	return 0;
+}
+
+static void bpf_iter_fini_rhash_map(void *priv_data)
+{
+}
+
+static const struct seq_operations bpf_rhash_map_seq_ops = {
+	.start = bpf_rhash_map_seq_start,
+	.next = bpf_rhash_map_seq_next,
+	.stop = bpf_rhash_map_seq_stop,
+	.show = bpf_rhash_map_seq_show,
+};
+
+static const struct bpf_iter_seq_info rhash_iter_seq_info = {
+	.seq_ops = &bpf_rhash_map_seq_ops,
+	.init_seq_private = bpf_iter_init_rhash_map,
+	.fini_seq_private = bpf_iter_fini_rhash_map,
+	.seq_priv_size = sizeof(struct bpf_iter_seq_rhash_map_info),
+};
+
+BTF_ID_LIST_SINGLE(rhtab_map_btf_ids, struct, bpf_rhtab)
+const struct bpf_map_ops rhtab_map_ops = {
+	.map_meta_equal = bpf_map_meta_equal,
+	.map_alloc_check = rhtab_map_alloc_check,
+	.map_alloc = rhtab_map_alloc,
+	.map_free = rhtab_map_free,
+	.map_get_next_key = rhtab_map_get_next_key,
+	.map_release_uref = rhtab_map_free_internal_structs,
+	.map_lookup_elem = rhtab_map_lookup_elem,
+	.map_lookup_and_delete_elem = rhtab_map_lookup_and_delete_elem,
+	.map_update_elem = rhtab_map_update_elem,
+	.map_delete_elem = rhtab_map_delete_elem,
+	.map_gen_lookup = rhtab_map_gen_lookup,
+	.map_seq_show_elem = rhtab_map_seq_show_elem,
+	.map_set_for_each_callback_args = map_set_for_each_callback_args,
+	.map_for_each_callback = bpf_each_rhash_elem,
+	.map_mem_usage = rhtab_map_mem_usage,
+	BATCH_OPS(rhtab),
+	.map_btf_id = &rhtab_map_btf_ids[0],
+	.iter_seq_info = &rhash_iter_seq_info,
+};
Signature · 1 line
2.53.0
#4 lore raw

Re: [PATCH RFC bpf-next 02/12] bpf: Implement basic functions for resizable hashtab

Quoted 8 lines · Mykyta Yatsenko
kernel/bpf/hashtab.c +7 -0
+
+/* Helper to get next element, handling -EAGAIN during resize */
+static struct rhtab_elem *rhtab_iter_next(struct rhashtable_iter *iter)
+{
+       struct rhtab_elem *elem;
+
+       while ((elem = rhashtable_walk_next(iter))) {

kernel/bpf/hashtab.c const struct bpf_map_ops htab_of_maps_map_ops = { · line 2736

Quoted 10 lines
kernel/bpf/hashtab.c +10 -0
+               if (IS_ERR(elem)) {
+                       if (PTR_ERR(elem) == -EAGAIN)
+                               continue;
+                       return NULL;
+               }
+               return elem;
+       }
+
+       return NULL;
+}

This helper is not used until the next patch. Move it there.

Quoted 32 lines
kernel/bpf/hashtab.c +32 -0
+
+static int rhtab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
+{
+       struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
+       struct rhash_head *he;
+       unsigned int slot;
+       struct rhtab_elem *elem;
+       bool found = false;
+       struct bucket_table *tbl;
+
+       guard(rcu)();
+
+       tbl = rht_dereference_rcu(rhtab->ht.tbl, &rhtab->ht);
+restart:
+       if (!tbl)
+               return -ENOENT;
+
+       slot = (key && !found) ? rht_key_hashfn(&rhtab->ht, tbl, key, rhtab->params) : 0;
+       for (; slot < tbl->size; ++slot) {
+               rht_for_each_rcu(he, tbl, slot) {
+                       elem = container_of(he, struct rhtab_elem, node);
+                       if (found || !key) {
+                               memcpy(next_key, elem->data, map->key_size);
+                               return 0;
+                       } else if (memcmp(elem->data, key, map->key_size) == 0) {
+                               found = true;
+                       }
+               }
+               /* if key is not found in this table, search future_tbl */
+               if (key && !found)
+                       break;
+       }

kernel/bpf/hashtab.c const struct bpf_map_ops htab_of_maps_map_ops = { · line 2778

Quoted 10 lines
kernel/bpf/hashtab.c +10 -0
+       tbl = rht_dereference_rcu(tbl->future_tbl, &rhtab->ht);
+       if (tbl)
+               goto restart;
+
+       /* Key not found, wrap to first element */
+       if (key && !found) {
+               tbl = rht_dereference_rcu(rhtab->ht.tbl, &rhtab->ht);
+               key = NULL;
+               goto restart;
+       }

Two restarts? Looks odd.
This is a tricky logic and it's open coded 3 times with small differences. I think it's better be in rhashtable.h

I think we have to treat 'struct bucket_table' as internal. Outside of rhashtable only nfsd is using it, but that's not right either.

Some kind of for_each macro or always_inline function in rhashtable.h should do it. cc Herbert Xu, of course.

Does any of it need to deal with nested table?
I mean, rhashtable can become nested when table grows and kVmalloc is not available, so it will be a bunch of kmalloc-s that will create a slower nested table.
See rht_bucket(). Once nested the bucket selection is complicated.

#5 lore raw

RFC PATCH 3/12 bpf: Implement batch ops and BPF iterator for resizable hashtab

In reply to Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

Add batch operations and BPF iterator support for BPF_MAP_TYPE_RHASH.

Batch operations:
* rhtab_map_lookup_batch: Bulk lookup of elements by bucket
* rhtab_map_lookup_and_delete_batch: Atomic bulk lookup and delete

The batch implementation iterates through buckets under RCU protection, copying keys and values to userspace buffers. When the buffer fills mid-bucket, it rolls back to the bucket boundary so the next call can retry that bucket completely.

BPF iterator:
* Uses rhashtable_walk_* API for safe iteration
* Handles -EAGAIN during table resize transparently
* Tracks skip_elems to resume iteration across read() calls

Also implements rhtab_map_mem_usage() to report memory consumption.

---
 kernel/bpf/hashtab.c | 227 +++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 221 insertions(+), 6 deletions(-)
kernel/bpf/hashtab.c +221 -6
index 917f8f7d70c9ce265c13751e17e3b0bb4b598c45..142e5cf3be17c74d29ef1623be4ed3923c97dd2e 100644
@@ -3065,19 +3065,159 @@ static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn,
 
 static u64 rhtab_map_mem_usage(const struct bpf_map *map)
 {
-	return 0;
+	struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
+	struct bucket_table *tbl, *future_tbl;
+	u64 num_entries;
+	u64 usage = sizeof(struct bpf_rhtab);
+
+	num_entries = atomic_read(&rhtab->ht.nelems);
+	usage += rhtab->elem_size * num_entries;
+
+	/* Add rhashtable internal overhead: bucket_table + buckets array */
+	guard(rcu)();
+	tbl = rcu_dereference(rhtab->ht.tbl);
+	usage += sizeof(struct bucket_table) +
+		 sizeof(struct rhash_lock_head *) * tbl->size;
+
+	/* Account for future_tbl during resize */
+	future_tbl = rcu_dereference(tbl->future_tbl);
+	if (future_tbl)
+		usage += sizeof(struct bucket_table) +
+			 sizeof(struct rhash_lock_head *) * future_tbl->size;
+
+	return usage;
+}
+
+static int __rhtab_map_lookup_and_delete_batch(struct bpf_map *map,
+					       const union bpf_attr *attr,
+					       union bpf_attr __user *uattr,
+					       bool do_delete)
+{
+	struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
+	void __user *uvalues = u64_to_user_ptr(attr->batch.values);
+	void __user *ukeys = u64_to_user_ptr(attr->batch.keys);
+	void __user *ubatch = u64_to_user_ptr(attr->batch.in_batch);
+	void *keys = NULL, *values = NULL, *dst_key, *dst_val;
+	struct rhtab_elem **del_elems = NULL;
+	u32 slot, max_count, total, key_size, value_size, i;
+	struct bucket_table *tbl;
+	struct rhtab_elem *elem;
+	struct rhash_head *he;
+	u64 elem_map_flags, map_flags;
+	int ret = 0;
+
+	elem_map_flags = attr->batch.elem_flags;
+	if ((elem_map_flags & ~BPF_F_LOCK) ||
+	    ((elem_map_flags & BPF_F_LOCK) &&
+	     !btf_record_has_field(map->record, BPF_SPIN_LOCK)))
+		return -EINVAL;
+
+	map_flags = attr->batch.flags;
+	if (map_flags)
+		return -EINVAL;
+
+	max_count = attr->batch.count;
+	if (!max_count)
+		return 0;
+
+	if (put_user(0, &uattr->batch.count))
+		return -EFAULT;
+
+	slot = 0;
+	if (ubatch && copy_from_user(&slot, ubatch, sizeof(slot)))
+		return -EFAULT;
+
+	key_size = map->key_size;
+	value_size = map->value_size;
+
+	keys = kvmalloc_array(max_count, key_size, GFP_USER | __GFP_NOWARN);
+	values = kvmalloc_array(max_count, value_size, GFP_USER | __GFP_NOWARN);
+	if (do_delete)
+		del_elems = kvmalloc_array(max_count, sizeof(void *), GFP_USER | __GFP_NOWARN);
+
+	if (!keys || !values || (do_delete && !del_elems)) {
+		ret = -ENOMEM;
+		goto out;
+	}
+
+	dst_key = keys;
+	dst_val = values;
+	total = 0;
+
+	rcu_read_lock();
+	tbl = rht_dereference_rcu(rhtab->ht.tbl, &rhtab->ht);
+
+	if (slot >= tbl->size) {
+		rcu_read_unlock();
+		ret = -ENOENT;
+		goto out;
+	}
+
+	for (; slot < tbl->size; slot++) {
+		u32 bucket_start = total;
+
+		rht_for_each_rcu(he, tbl, slot) {
+			/*
+			 * If buffer is full mid-bucket, undo this partial bucket
+			 * so next call retries it. I this is the first bucket return -ENOSPC
+			 */
+			if (total >= max_count) {
+				if (bucket_start == 0)
+					ret = -ENOSPC;
+				dst_key -= (total - bucket_start) * key_size;
+				dst_val -= (total - bucket_start) * value_size;
+				total = bucket_start;
+				goto done;
+			}
+			elem = container_of(he, struct rhtab_elem, node);
+			memcpy(dst_key, elem->data, key_size);
+			rhtab_read_elem_value(map, dst_val, elem, elem_map_flags);
+			check_and_init_map_value(map, dst_val);
+
+			if (do_delete)
+				del_elems[total] = elem;
+
+			dst_key += key_size;
+			dst_val += value_size;
+			total++;
+		}
+	}
+done:
+
+	if (do_delete) {
+		for (i = 0; i < total; i++)
+			rhtab_delete_elem(rhtab, del_elems[i]);
+	}
+
+	rcu_read_unlock();
+
+	if (total == 0)
+		goto out;
+
+	ret = copy_to_user(ukeys, keys, total * key_size);
+	ret = ret ? : copy_to_user(uvalues, values, total * value_size);
+	ret = ret ? : put_user(total, &uattr->batch.count);
+	ret = ret ? : copy_to_user(u64_to_user_ptr(attr->batch.out_batch), &slot, sizeof(slot));
+	if (ret)
+		ret = -EFAULT;
+
+out:
+	kvfree(keys);
+	kvfree(values);
+	kvfree(del_elems);
+	return ret;
 }
 
 static int rhtab_map_lookup_batch(struct bpf_map *map, const union bpf_attr *attr,
 				  union bpf_attr __user *uattr)
 {
-	return 0;
+	return __rhtab_map_lookup_and_delete_batch(map, attr, uattr, false);
 }
 
 static int rhtab_map_lookup_and_delete_batch(struct bpf_map *map, const union bpf_attr *attr,
 					     union bpf_attr __user *uattr)
 {
-	return 0;
+	return __rhtab_map_lookup_and_delete_batch(map, attr, uattr, true);
 }
 
 struct bpf_iter_seq_rhash_map_info {
@@ -3090,30 +3230,105 @@ struct bpf_iter_seq_rhash_map_info {
 
 static void *bpf_rhash_map_seq_start(struct seq_file *seq, loff_t *pos)
 {
-	return NULL;
+	struct bpf_iter_seq_rhash_map_info *info = seq->private;
+	struct rhtab_elem *elem;
+	u32 skip = info->skip_elems;
+
+	rhashtable_walk_enter(&info->rhtab->ht, &info->iter);
+	rhashtable_walk_start(&info->iter);
+	info->iter_active = true;
+
+	/* Skip elements we've already processed in previous read calls */
+	while (skip > 0) {
+		elem = rhtab_iter_next(&info->iter);
+		if (!elem)
+			return NULL;
+		skip--;
+	}
+
+	elem = rhtab_iter_next(&info->iter);
+	if (!elem)
+		return NULL;
+	/*
+	 * if *pos is not 0, previously iteration failed on this elem,
+	 * so we are restarting it. That's why no need to increment *pos.
+	 */
+	if (*pos == 0)
+		++*pos;
+	return elem;
 }
 
 static void *bpf_rhash_map_seq_next(struct seq_file *seq, void *v, loff_t *pos)
 {
-	return NULL;
+	struct bpf_iter_seq_rhash_map_info *info = seq->private;
+
+	++*pos;
+	++info->skip_elems;
+
+	return rhtab_iter_next(&info->iter);
+}
+
+static int __bpf_rhash_map_seq_show(struct seq_file *seq,
+				    struct rhtab_elem *elem)
+{
+	struct bpf_iter_seq_rhash_map_info *info = seq->private;
+	struct bpf_iter__bpf_map_elem ctx = {};
+	struct bpf_iter_meta meta;
+	struct bpf_prog *prog;
+	int ret = 0;
+
+	meta.seq = seq;
+	prog = bpf_iter_get_info(&meta, elem == NULL);
+	if (prog) {
+		ctx.meta = &meta;
+		ctx.map = info->map;
+		if (elem) {
+			ctx.key = elem->data;
+			ctx.value = rhtab_elem_value(elem);
+		}
+		ret = bpf_iter_run_prog(prog, &ctx);
+	}
+
+	return ret;
 }
 
 static int bpf_rhash_map_seq_show(struct seq_file *seq, void *v)
 {
-	return 0;
+	return __bpf_rhash_map_seq_show(seq, v);
 }
 
 static void bpf_rhash_map_seq_stop(struct seq_file *seq, void *v)
 {
+	struct bpf_iter_seq_rhash_map_info *info = seq->private;
+
+	if (!v)
+		(void)__bpf_rhash_map_seq_show(seq, NULL);
+
+	if (info->iter_active) {
+		rhashtable_walk_stop(&info->iter);
+		rhashtable_walk_exit(&info->iter);
+		info->iter_active = false;
+	}
 }
 
 static int bpf_iter_init_rhash_map(void *priv_data, struct bpf_iter_aux_info *aux)
 {
+	struct bpf_iter_seq_rhash_map_info *info = priv_data;
+	struct bpf_map *map = aux->map;
+
+	bpf_map_inc_with_uref(map);
+	info->map = map;
+	info->rhtab = container_of(map, struct bpf_rhtab, map);
+	info->skip_elems = 0;
+	info->iter_active = false;
 	return 0;
 }
 
 static void bpf_iter_fini_rhash_map(void *priv_data)
 {
+	struct bpf_iter_seq_rhash_map_info *info = priv_data;
+
+	bpf_map_put_with_uref(info->map);
 }
 
 static const struct seq_operations bpf_rhash_map_seq_ops = {
Signature · 1 line
2.53.0
#6 lore raw

Re: [PATCH RFC bpf-next 03/12] bpf: Implement batch ops and BPF iterator for resizable hashtab

This isn't a bug, but there's a typo: "I this" should be "If this".
Quoted 4 lines
kernel/bpf/hashtab.c +0 -0
index 917f8f7d7..142e5cf3b 100644

[ ... ]

kernel/bpf/hashtab.c static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn, · line 3162

Quoted 7 lines
kernel/bpf/hashtab.c +7 -0
+	for (; slot < tbl->size; slot++) {
+		u32 bucket_start = total;
+
+		rht_for_each_rcu(he, tbl, slot) {
+			/*
+			 * If buffer is full mid-bucket, undo this partial bucket
+			 * so next call retries it. I this is the first bucket return -ENOSPC
                                            ^

This isn't a bug, but there's a typo: "I this" should be "If this".

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/21727734472

AI-authorship-score: low
AI-authorship-explanation: The commit follows standard kernel development practices with technically accurate descriptions and proper code patterns consistent with human kernel developers.
issues-found: 1
issue-severity-score: low
issue-severity-explanation: A minor typo in a comment does not affect functionality or system stability.

#7 lore raw

RFC PATCH 4/12 bpf: Reject resizable hash map in tracing progs

In reply to Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

Resizable hash map uses spin lock per bucket, which makes it not possible to use in NMI or IRQ contexts. Reject in verifier.

---
 kernel/bpf/verifier.c | 7 +++++++
 1 file changed, 7 insertions(+)
kernel/bpf/verifier.c +7 -0
index 0803dca3d93f9e912824aa89951cb5b65e961af9..a5560ce436fc75237536b17fa845b9f7a278de30 100644
@@ -21544,6 +21544,13 @@ static int check_map_prog_compatibility(struct bpf_verifier_env *env,
 		}
 	}
 
+	if (map->map_type == BPF_MAP_TYPE_RHASH) {
+		if (is_tracing_prog_type(prog_type)) {
+			verbose(env, "tracing progs cannot use resizable hash maps yet\n");
+			return -EINVAL;
+		}
+	}
+
 	if ((bpf_prog_is_offloaded(prog->aux) || bpf_map_is_offloaded(map)) &&
 	    !bpf_offload_prog_map_match(prog, map)) {
 		verbose(env, "offload device mismatch between prog and map\n");
Signature · 1 line
2.53.0
#8 lore raw

Re: [PATCH RFC bpf-next 04/12] bpf: Reject resizable hash map in tracing progs

Quoted 5 lines · Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

Resizable hash map uses spin lock per bucket, which makes it not possible to use in NMI or IRQ contexts. Reject in verifier.

It uses irq protected bit lock.

kernel/bpf/verifier.c static int check_map_prog_compatibility(struct bpf_verifier_env *env, · line 21551

Quoted 5 lines
kernel/bpf/verifier.c +5 -0
+       if (map->map_type == BPF_MAP_TYPE_RHASH) {
+               if (is_tracing_prog_type(prog_type)) {
+                       verbose(env, "tracing progs cannot use resizable hash maps yet\n");
+                       return -EINVAL;
+               }

This is too restrictive. lookup is lockless and update/delete are using bitlock with irqsave,
so we can do if (irqs_disabled()) return -EBUSY in map_update/delete helpers.

Also please add it to selftest/bpf/bench and compare it to regular hashmap. It's likely slower, but how much?

#9 lore raw

RFC PATCH 5/12 libbpf: Support resizable hashtable

In reply to Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

---
 tools/lib/bpf/libbpf.c        | 1 +
 tools/lib/bpf/libbpf_probes.c | 3 +++
 2 files changed, 4 insertions(+)
tools/lib/bpf/libbpf.c +1 -0
index 0c8bf0b5cce44462414e99a958260e940148e818..7651c80a72cbc30cc42c0c3f4b5dea1427b810be 100644
@@ -192,6 +192,7 @@ static const char * const map_type_name[] = {
 	[BPF_MAP_TYPE_CGRP_STORAGE]		= "cgrp_storage",
 	[BPF_MAP_TYPE_ARENA]			= "arena",
 	[BPF_MAP_TYPE_INSN_ARRAY]		= "insn_array",
+	[BPF_MAP_TYPE_RHASH]			= "rhash",
 };
 
 static const char * const prog_type_name[] = {
tools/lib/bpf/libbpf_probes.c +3 -0
index bccf4bb747e1d97b7d0408c9f97528b88c73281b..995b3883889dfea8dd77daacdac49828743f87ed 100644
@@ -299,6 +299,9 @@ static int probe_map_create(enum bpf_map_type map_type)
 		value_size	= sizeof(__u64);
 		opts.map_flags	= BPF_F_NO_PREALLOC;
 		break;
+	case BPF_MAP_TYPE_RHASH:
+		opts.map_flags	= BPF_F_NO_PREALLOC;
+		break;
 	case BPF_MAP_TYPE_CGROUP_STORAGE:
 	case BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE:
 		key_size	= sizeof(struct bpf_cgroup_storage_key);
Signature · 1 line
2.53.0
#10 lore raw

RFC PATCH 6/12 selftests/bpf: Add basic tests for resizable hash map

In reply to Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

Test basic map operations (lookup, update, delete) for BPF_MAP_TYPE_RHASH including boundary conditions like duplicate key insertion and deletion of nonexistent keys.

---
 tools/testing/selftests/bpf/prog_tests/rhash.c |  62 ++++++
 tools/testing/selftests/bpf/progs/rhash.c      | 249 +++++++++++++++++++++++++
 2 files changed, 311 insertions(+)
tools/testing/selftests/bpf/prog_tests/rhash.c new file +62 -0
new file mode 100644
index 0000000000000000000000000000000000000000..be6e5e01bde6b127268f313d0ef25dcb33373b97
@@ -0,0 +1,62 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2025 Meta Platforms, Inc. and affiliates. */
+#include <test_progs.h>
+#include <string.h>
+#include <stdio.h>
+#include "rhash.skel.h"
+#include <linux/bpf.h>
+#include <linux/perf_event.h>
+#include <sys/syscall.h>
+
+static void rhash_run(const char *prog_name)
+{
+	struct rhash *skel;
+	struct bpf_program *prog;
+	LIBBPF_OPTS(bpf_test_run_opts, opts);
+	int err;
+
+	skel = rhash__open();
+	if (!ASSERT_OK_PTR(skel, "rhash__open"))
+		return;
+
+	prog = bpf_object__find_program_by_name(skel->obj, prog_name);
+	bpf_program__set_autoload(prog, true);
+
+	err = rhash__load(skel);
+	if (!ASSERT_OK(err, "skel_load"))
+		goto cleanup;
+
+	err = bpf_prog_test_run_opts(bpf_program__fd(prog), &opts);
+	if (!ASSERT_OK(err, "prog run"))
+		goto cleanup;
+
+	if (!ASSERT_OK(skel->bss->err, "bss->err"))
+		goto cleanup;
+
+cleanup:
+	rhash__destroy(skel);
+}
+
+void test_rhash(void)
+{
+	if (test__start_subtest("test_rhash_lookup_update"))
+		rhash_run("test_rhash_lookup_update");
+
+	if (test__start_subtest("test_rhash_update_delete"))
+		rhash_run("test_rhash_update_delete");
+
+	if (test__start_subtest("test_rhash_update_elements"))
+		rhash_run("test_rhash_update_elements");
+
+	if (test__start_subtest("test_rhash_update_exist"))
+		rhash_run("test_rhash_update_exist");
+
+	if (test__start_subtest("test_rhash_update_any"))
+		rhash_run("test_rhash_update_any");
+
+	if (test__start_subtest("test_rhash_noexist_duplicate"))
+		rhash_run("test_rhash_noexist_duplicate");
+
+	if (test__start_subtest("test_rhash_delete_nonexistent"))
+		rhash_run("test_rhash_delete_nonexistent");
+}
tools/testing/selftests/bpf/progs/rhash.c new file +249 -0

249 lines not on this page · raw message

Signature · 1 line
2.53.0
#11 lore raw

Re: [PATCH RFC bpf-next 06/12] selftests/bpf: Add basic tests for resizable hash map

Should there be a NULL check for prog here? bpf_object__find_program_by_name() can return NULL if the program name is not found, and bpf_program__set_autoload() will dereference prog->obj without…
Quoted 6 lines
tools/testing/selftests/bpf/prog_tests/rhash.c new file +0 -0
new file mode 100644
index 000000000..be6e5e01b
@@ -0,0 +1,62 @@

[ ... ]

tools/testing/selftests/bpf/prog_tests/rhash.c line 23

Quoted 13 lines
tools/testing/selftests/bpf/prog_tests/rhash.c new file +13 -0
+static void rhash_run(const char *prog_name)
+{
+	struct rhash *skel;
+	struct bpf_program *prog;
+	LIBBPF_OPTS(bpf_test_run_opts, opts);
+	int err;
+
+	skel = rhash__open();
+	if (!ASSERT_OK_PTR(skel, "rhash__open"))
+		return;
+
+	prog = bpf_object__find_program_by_name(skel->obj, prog_name);
+	bpf_program__set_autoload(prog, true);

Should there be a NULL check for prog here? bpf_object__find_program_by_name() can return NULL if the program name is not found, and bpf_program__set_autoload() will dereference prog->obj without checking.

Other selftests follow this pattern:

    prog = bpf_object__find_program_by_name(skel->obj, prog_name);
    if (!ASSERT_OK_PTR(prog, "bpf_object__find_program_by_name"))
        goto cleanup;

See for example tracing_failure.c and type_cast.c.

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/21727734472

AI-authorship-score: low
AI-authorship-explanation: Debug print statements with cryptic identifiers (kkl 2, kkl 3) suggest human iterative debugging rather than AI generation.
issues-found: 1
issue-severity-score: low
issue-severity-explanation: Missing NULL check in test code can cause crash during test development but does not affect production kernel stability.

#12 lore raw

RFC PATCH 7/12 selftests/bpf: Support resizable hashtab in test_maps

In reply to Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

---
 .../selftests/bpf/map_tests/htab_map_batch_ops.c   |  22 ++++-
 tools/testing/selftests/bpf/test_maps.c            | 107 +++++++++++++++------
 2 files changed, 97 insertions(+), 32 deletions(-)
tools/testing/selftests/bpf/map_tests/htab_map_batch_ops.c +17 -5
index 5da493b94ae2573c50e0f0eccadb577d549062a0..e8e83bf95be478eaaad35309e1268c5053a4135d 100644
@@ -74,10 +74,11 @@ static void map_batch_verify(int *visited, __u32 max_entries,
 	}
 }
 
-void __test_map_lookup_and_delete_batch(bool is_pcpu)
+void __test_map_lookup_and_delete_batch(enum bpf_map_type map_type)
 {
 	__u32 batch, count, total, total_success;
 	typedef BPF_DECLARE_PERCPU(int, value);
+	bool is_pcpu = (map_type == BPF_MAP_TYPE_PERCPU_HASH);
 	int map_fd, *keys, *visited, key;
 	const __u32 max_entries = 10;
 	value pcpu_values[max_entries];
@@ -88,9 +89,13 @@ void __test_map_lookup_and_delete_batch(bool is_pcpu)
 		.elem_flags = 0,
 		.flags = 0,
 	);
+	struct bpf_map_create_opts map_opts = {
+		.sz = sizeof(map_opts),
+		.map_flags = (map_type == BPF_MAP_TYPE_RHASH) ? BPF_F_NO_PREALLOC : 0,
+	};
 
-	map_fd = bpf_map_create(is_pcpu ? BPF_MAP_TYPE_PERCPU_HASH : BPF_MAP_TYPE_HASH,
-				"hash_map", sizeof(int), sizeof(int), max_entries, NULL);
+	map_fd = bpf_map_create(map_type, "hash_map", sizeof(int), sizeof(int),
+				max_entries, &map_opts);
 	CHECK(map_fd == -1,
 	      "bpf_map_create()", "error:%s\n", strerror(errno));
 
@@ -261,13 +266,19 @@ void __test_map_lookup_and_delete_batch(bool is_pcpu)
 
 void htab_map_batch_ops(void)
 {
-	__test_map_lookup_and_delete_batch(false);
+	__test_map_lookup_and_delete_batch(BPF_MAP_TYPE_HASH);
 	printf("test_%s:PASS\n", __func__);
 }
 
 void htab_percpu_map_batch_ops(void)
 {
-	__test_map_lookup_and_delete_batch(true);
+	__test_map_lookup_and_delete_batch(BPF_MAP_TYPE_PERCPU_HASH);
+	printf("test_%s:PASS\n", __func__);
+}
+
+void rhtab_map_batch_ops(void)
+{
+	__test_map_lookup_and_delete_batch(BPF_MAP_TYPE_RHASH);
 	printf("test_%s:PASS\n", __func__);
 }
 
@@ -275,4 +286,5 @@ void test_htab_map_batch_ops(void)
 {
 	htab_map_batch_ops();
 	htab_percpu_map_batch_ops();
+	rhtab_map_batch_ops();
 }
tools/testing/selftests/bpf/test_maps.c +80 -27

246 lines not on this page · raw message

Signature · 1 line
2.53.0
#13 lore raw

RFC PATCH 8/12 selftests/bpf: Resizable hashtab BPF_F_LOCK tests

In reply to Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

Add tests validating resizable hash map handles BPF_F_LOCK flag as expected.

---
 tools/testing/selftests/bpf/prog_tests/rhash.c | 99 ++++++++++++++++++++++++++
 tools/testing/selftests/bpf/progs/rhash.c      | 35 +++++++++
 2 files changed, 134 insertions(+)
tools/testing/selftests/bpf/prog_tests/rhash.c +99 -0
index be6e5e01bde6b127268f313d0ef25dcb33373b97..d1557405e062851ba2ad3d7378049c93395e7943 100644
@@ -7,6 +7,7 @@
 #include <linux/bpf.h>
 #include <linux/perf_event.h>
 #include <sys/syscall.h>
+#include <network_helpers.h>
 
 static void rhash_run(const char *prog_name)
 {
@@ -37,6 +38,100 @@ static void rhash_run(const char *prog_name)
 	rhash__destroy(skel);
 }
 
+struct lock_thread_args {
+	int prog_fd;
+	int map_fd;
+};
+
+struct lock_elem {
+	struct bpf_spin_lock lock;
+	int var[16];
+};
+
+static void *spin_lock_thread(void *arg)
+{
+	struct lock_thread_args *args = arg;
+	LIBBPF_OPTS(bpf_test_run_opts, topts,
+		.data_in = &pkt_v4,
+		.data_size_in = sizeof(pkt_v4),
+		.repeat = 10000,
+	);
+	int err;
+
+	err = bpf_prog_test_run_opts(args->prog_fd, &topts);
+	if (err || topts.retval)
+		return (void *)1;
+
+	return (void *)0;
+}
+
+static void *parallel_map_access(void *arg)
+{
+	struct lock_thread_args *args = arg;
+	int i, j, key = 0;
+	int err;
+	struct lock_elem val;
+
+	for (i = 0; i < 10000; i++) {
+		err = bpf_map_lookup_elem_flags(args->map_fd, &key, &val, BPF_F_LOCK);
+		if (err)
+			return (void *)1;
+		if (val.lock.val)
+			return (void *)1;
+		for (j = 1; j < 16; j++) {
+			if (val.var[j] != val.var[0])
+				return (void *)1;
+		}
+	}
+
+	return (void *)0;
+}
+
+static void rhash_spin_lock_test(void)
+{
+	struct lock_thread_args args;
+	struct rhash *skel;
+	struct lock_elem val = {};
+	pthread_t thread_id[4];
+	int err, key = 0, i;
+	void *ret;
+
+	skel = rhash__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "rhash__open_and_load"))
+		return;
+
+	args.prog_fd = bpf_program__fd(skel->progs.test_rhash_spin_lock);
+	args.map_fd = bpf_map__fd(skel->maps.rhmap_lock);
+
+	/* Insert initial element with BPF_F_LOCK */
+	err = bpf_map_update_elem(args.map_fd, &key, &val, BPF_F_LOCK);
+	if (!ASSERT_OK(err, "initial update"))
+		goto cleanup;
+
+	/* Spawn 2 threads running BPF program (uses bpf_spin_lock) */
+	for (i = 0; i < 2; i++)
+		if (!ASSERT_OK(pthread_create(&thread_id[i], NULL,
+					      &spin_lock_thread, &args),
+			       "pthread_create spin_lock"))
+			goto cleanup;
+
+	/* Spawn 2 threads doing parallel map access with BPF_F_LOCK */
+	for (i = 2; i < 4; i++)
+		if (!ASSERT_OK(pthread_create(&thread_id[i], NULL,
+					      &parallel_map_access, &args),
+			       "pthread_create parallel_map_access"))
+			goto cleanup;
+
+	/* Wait for all threads */
+	for (i = 0; i < 4; i++)
+		if (!ASSERT_OK(pthread_join(thread_id[i], &ret), "pthread_join") ||
+		    !ASSERT_OK((long)ret, "thread ret"))
+			goto cleanup;
+
+cleanup:
+	rhash__destroy(skel);
+}
+
 void test_rhash(void)
 {
 	if (test__start_subtest("test_rhash_lookup_update"))
@@ -59,4 +154,8 @@ void test_rhash(void)
 
 	if (test__start_subtest("test_rhash_delete_nonexistent"))
 		rhash_run("test_rhash_delete_nonexistent");
+
+	if (test__start_subtest("test_rhash_spin_lock"))
+		rhash_spin_lock_test();
 }
+
tools/testing/selftests/bpf/progs/rhash.c +35 -0
index 246cc4538c493902c720498bf7ab9bc5587d4643..fba55b5d9ed2575a1a31c4d2247c1d76f10d6bb1 100644
@@ -247,3 +247,38 @@ int test_rhash_delete_nonexistent(void *ctx)
 	return 0;
 }
 
+#define VAR_NUM 16
+
+struct lock_elem {
+	struct bpf_spin_lock lock;
+	int var[VAR_NUM];
+};
+
+struct {
+	__uint(type, BPF_MAP_TYPE_RHASH);
+	__uint(map_flags, BPF_F_NO_PREALLOC);
+	__uint(max_entries, 1);
+	__type(key, __u32);
+	__type(value, struct lock_elem);
+} rhmap_lock SEC(".maps");
+
+SEC("cgroup/skb")
+int test_rhash_spin_lock(struct __sk_buff *skb)
+{
+	struct lock_elem *val;
+	int rnd = bpf_get_prandom_u32();
+	int key = 0, i;
+
+	val = bpf_map_lookup_elem(&rhmap_lock, &key);
+	if (!val)
+		return 1;
+
+	/* spin_lock in resizable hash map */
+	bpf_spin_lock(&val->lock);
+	for (i = 0; i < VAR_NUM; i++)
+		val->var[i] = rnd;
+	bpf_spin_unlock(&val->lock);
+
+	return 0;
+}
+
Signature · 1 line
2.53.0
#14 lore raw

RFC PATCH 9/12 selftests/bpf: Add stress tests for resizable hash get_next_key

In reply to Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

Test get_next_key behavior under concurrent modification:
* Resize test: verify all elements visited after resize trigger
* Stress test: concurrent iterators and modifiers to detect races

---
 tools/testing/selftests/bpf/prog_tests/rhash.c | 156 +++++++++++++++++++++++++
 tools/testing/selftests/bpf/progs/rhash.c      |   8 ++
 2 files changed, 164 insertions(+)
tools/testing/selftests/bpf/prog_tests/rhash.c +156 -0
index d1557405e062851ba2ad3d7378049c93395e7943..689ba6d73a724e94c3845acaeca3c0a7b45a8c6d 100644
@@ -132,6 +132,156 @@ static void rhash_spin_lock_test(void)
 	rhash__destroy(skel);
 }
 
+struct iter_thread_args {
+	int map_fd;
+	int stop;
+	int error;
+};
+
+static void *get_next_key_thread(void *arg)
+{
+	struct iter_thread_args *args = arg;
+	int key, next_key;
+	int i = 0;
+
+	for (i = 0; i < 1000; i++) {
+		if (READ_ONCE(args->stop))
+			break;
+
+		if (bpf_map_get_next_key(args->map_fd, NULL, &next_key) != 0) {
+			WRITE_ONCE(args->error, 1);
+			continue;
+		}
+
+		key = next_key;
+		while (bpf_map_get_next_key(args->map_fd, &key, &next_key) == 0)
+			key = next_key;
+	}
+
+	return (void *)0;
+}
+
+static void *modifier_thread(void *arg)
+{
+	struct iter_thread_args *args = arg;
+	int key, value;
+	int i;
+
+	for (i = 0; i < 10000; i++) {
+		if (READ_ONCE(args->stop))
+			break;
+
+		key = i;
+		value = i;
+		if (bpf_map_update_elem(args->map_fd, &key, &value, BPF_ANY))
+			WRITE_ONCE(args->error, 1);
+	}
+
+	return (void *)0;
+}
+
+static void rhash_get_next_key_stress_test(void)
+{
+	struct iter_thread_args args = {};
+	struct rhash *skel;
+	pthread_t iter_threads[2];
+	pthread_t mod_threads[2];
+	int key, value;
+	int err, i;
+	void *ret;
+
+	skel = rhash__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "rhash__open_and_load"))
+		return;
+
+	args.map_fd = bpf_map__fd(skel->maps.rhmap_iter);
+	args.stop = 0;
+	args.error = 0;
+
+	/* Pre-populate map */
+	for (i = 0; i < 50; i++) {
+		key = i;
+		value = i;
+		err = bpf_map_update_elem(args.map_fd, &key, &value, BPF_NOEXIST);
+		if (!ASSERT_OK(err, "initial insert"))
+			goto cleanup;
+	}
+
+	/* Iterator threads */
+	for (i = 0; i < 2; i++)
+		if (!ASSERT_OK(pthread_create(&iter_threads[i], NULL,
+					      &get_next_key_thread, &args),
+			       "pthread_create iter"))
+			goto cleanup;
+
+	/* Modifier threads */
+	for (i = 0; i < 2; i++)
+		if (!ASSERT_OK(pthread_create(&mod_threads[i], NULL,
+					      &modifier_thread, &args),
+			       "pthread_create mod"))
+			goto cleanup;
+
+	/* Wait for modifier threads to finish */
+	for (i = 0; i < 2; i++)
+		pthread_join(mod_threads[i], &ret);
+
+	/* Signal iterator threads to stop */
+	WRITE_ONCE(args.stop, 1);
+
+	/* Wait for iterator threads */
+	for (i = 0; i < 2; i++)
+		if (!ASSERT_OK(pthread_join(iter_threads[i], &ret), "pthread_join iter") ||
+		    !ASSERT_OK((long)ret, "iter thread ret"))
+			goto cleanup;
+
+	ASSERT_EQ(args.error, 0, "no infinite loop");
+
+cleanup:
+	rhash__destroy(skel);
+}
+
+static void rhash_get_next_key_resize_test(void)
+{
+	struct rhash *skel;
+	int key, next_key, value;
+	int visited[128] = {0};
+	int map_fd;
+	int err, i;
+
+	skel = rhash__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "rhash__open_and_load"))
+		return;
+
+	map_fd = bpf_map__fd(skel->maps.rhmap_iter);
+
+	/* Insert 100 elements - triggers resize */
+	for (i = 0; i < 100; i++) {
+		key = i;
+		value = i;
+		err = bpf_map_update_elem(map_fd, &key, &value, BPF_NOEXIST);
+		if (!ASSERT_OK(err, "insert elem"))
+			goto cleanup;
+	}
+
+	/* Iterate all elements */
+	err = bpf_map_get_next_key(map_fd, NULL, &next_key);
+	if (!ASSERT_OK(err, "get first key"))
+		goto cleanup;
+
+	do {
+		key = next_key;
+		ASSERT_NEQ(visited[key], 1, "unique keys");
+		visited[key] = 1;
+	} while (bpf_map_get_next_key(map_fd, &key, &next_key) == 0);
+
+	/* Verify all elements visited */
+	for (i = 0; i < 100; i++)
+		ASSERT_TRUE(visited[i], "element visited");
+
+cleanup:
+	rhash__destroy(skel);
+}
+
 void test_rhash(void)
 {
 	if (test__start_subtest("test_rhash_lookup_update"))
@@ -157,5 +307,11 @@ void test_rhash(void)
 
 	if (test__start_subtest("test_rhash_spin_lock"))
 		rhash_spin_lock_test();
+
+	if (test__start_subtest("test_rhash_get_next_key_resize"))
+		rhash_get_next_key_resize_test();
+
+	if (test__start_subtest("test_rhash_get_next_key_stress"))
+		rhash_get_next_key_stress_test();
 }
 
tools/testing/selftests/bpf/progs/rhash.c +8 -0
index fba55b5d9ed2575a1a31c4d2247c1d76f10d6bb1..61eda618cf55dfd4938c818eb4db41a842869599 100644
@@ -262,6 +262,14 @@ struct {
 	__type(value, struct lock_elem);
 } rhmap_lock SEC(".maps");
 
+struct {
+	__uint(type, BPF_MAP_TYPE_RHASH);
+	__uint(map_flags, BPF_F_NO_PREALLOC);
+	__uint(max_entries, 65536);
+	__type(key, int);
+	__type(value, int);
+} rhmap_iter SEC(".maps");
+
 SEC("cgroup/skb")
 int test_rhash_spin_lock(struct __sk_buff *skb)
 {
Signature · 1 line
2.53.0
#15 lore raw

RFC PATCH 10/12 selftests/bpf: Add BPF iterator tests for resizable hash map

In reply to Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

Test BPF iterator functionality for BPF_MAP_TYPE_RHASH:
* Basic iteration verifying all elements are visited
* Overflow test triggering seq_file restart, validating correct
resume behavior via skip_elems tracking

---
 tools/testing/selftests/bpf/prog_tests/rhash.c     | 168 +++++++++++++++++++++
 .../selftests/bpf/progs/bpf_iter_bpf_rhash_map.c   |  75 +++++++++
 2 files changed, 243 insertions(+)
tools/testing/selftests/bpf/prog_tests/rhash.c +168 -0
index 689ba6d73a724e94c3845acaeca3c0a7b45a8c6d..ee8f4181d501df8d31223bff72d4e551a903de4d 100644
@@ -4,6 +4,7 @@
 #include <string.h>
 #include <stdio.h>
 #include "rhash.skel.h"
+#include "bpf_iter_bpf_rhash_map.skel.h"
 #include <linux/bpf.h>
 #include <linux/perf_event.h>
 #include <sys/syscall.h>
@@ -282,6 +283,167 @@ static void rhash_get_next_key_resize_test(void)
 	rhash__destroy(skel);
 }
 
+static void rhash_iter_test(void)
+{
+	DECLARE_LIBBPF_OPTS(bpf_iter_attach_opts, opts);
+	struct bpf_iter_bpf_rhash_map *skel;
+	int err, i, len, map_fd, iter_fd;
+	union bpf_iter_link_info linfo;
+	u32 expected_key_sum = 0, key;
+	struct bpf_link *link;
+	u64 val = 0;
+	char buf[64];
+
+	skel = bpf_iter_bpf_rhash_map__open();
+	if (!ASSERT_OK_PTR(skel, "bpf_iter_bpf_rhash_map__open"))
+		return;
+
+	err = bpf_iter_bpf_rhash_map__load(skel);
+	if (!ASSERT_OK(err, "bpf_iter_bpf_rhash_map__load"))
+		goto out;
+
+	map_fd = bpf_map__fd(skel->maps.rhashmap);
+
+	/* Populate map with test data */
+	for (i = 0; i < 64; i++) {
+		key = i + 1;
+		expected_key_sum += key;
+
+		err = bpf_map_update_elem(map_fd, &key, &val, BPF_NOEXIST);
+		if (!ASSERT_OK(err, "map_update"))
+			goto out;
+	}
+
+	memset(&linfo, 0, sizeof(linfo));
+	linfo.map.map_fd = map_fd;
+	opts.link_info = &linfo;
+	opts.link_info_len = sizeof(linfo);
+
+	link = bpf_program__attach_iter(skel->progs.dump_bpf_rhash_map, &opts);
+	if (!ASSERT_OK_PTR(link, "attach_iter"))
+		goto out;
+
+	iter_fd = bpf_iter_create(bpf_link__fd(link));
+	if (!ASSERT_GE(iter_fd, 0, "create_iter"))
+		goto free_link;
+
+	do {
+		len = read(iter_fd, buf, sizeof(buf));
+	} while (len > 0);
+
+	ASSERT_EQ(skel->bss->key_sum, expected_key_sum, "key_sum");
+	ASSERT_EQ(skel->bss->elem_count, 64, "elem_count");
+
+	close(iter_fd);
+
+free_link:
+	bpf_link__destroy(link);
+out:
+	bpf_iter_bpf_rhash_map__destroy(skel);
+}
+
+static void rhash_iter_overflow_test(void)
+{
+	DECLARE_LIBBPF_OPTS(bpf_iter_attach_opts, opts);
+	struct bpf_iter_bpf_rhash_map *skel;
+	u32 total_read_len, expected_read_len, write_len, num_elems = 64;
+	u64 seen_values = 0;
+	int err, i, j, len, map_fd, iter_fd;
+	union bpf_iter_link_info linfo;
+	struct bpf_link *link;
+	char *buf;
+
+	skel = bpf_iter_bpf_rhash_map__open();
+	if (!ASSERT_OK_PTR(skel, "bpf_iter_bpf_rhash_map__open"))
+		return;
+
+	/*
+	 * Configure print_count so that output for each element almost fills
+	 * the seq_file buffer (8 pages). With multiple elements, this will
+	 * trigger buffer overflow and restart.
+	 */
+	write_len = sysconf(_SC_PAGE_SIZE) * 8;
+	skel->bss->print_count = (write_len - 8) / 8;
+	expected_read_len = num_elems * (write_len - 8);
+
+	err = bpf_iter_bpf_rhash_map__load(skel);
+	if (!ASSERT_OK(err, "bpf_iter_bpf_rhash_map__load"))
+		goto out;
+
+	map_fd = bpf_map__fd(skel->maps.rhashmap);
+
+	/* Populate map with test data */
+	for (i = 0; i < num_elems; i++) {
+		__u64 val = i;
+
+		err = bpf_map_update_elem(map_fd, &i, &val, BPF_NOEXIST);
+		if (!ASSERT_OK(err, "map_update"))
+			goto out;
+	}
+
+	memset(&linfo, 0, sizeof(linfo));
+	linfo.map.map_fd = map_fd;
+	opts.link_info = &linfo;
+	opts.link_info_len = sizeof(linfo);
+
+	link = bpf_program__attach_iter(skel->progs.dump_bpf_rhash_map_overflow, &opts);
+	if (!ASSERT_OK_PTR(link, "attach_iter"))
+		goto out;
+
+	iter_fd = bpf_iter_create(bpf_link__fd(link));
+	if (!ASSERT_GE(iter_fd, 0, "create_iter"))
+		goto free_link;
+
+	buf = malloc(expected_read_len);
+	if (!ASSERT_OK_PTR(buf, "malloc"))
+		goto close_iter;
+
+	/* Read all data - this should trigger multiple overflows/restarts */
+	total_read_len = 0;
+	while ((len = read(iter_fd, buf + total_read_len, expected_read_len - total_read_len)) > 0)
+		total_read_len += len;
+
+	ASSERT_OK(err, "err");
+	ASSERT_EQ(total_read_len, expected_read_len, "total_read_len");
+	ASSERT_EQ(skel->bss->unique_elem_count, num_elems, "unique_elem_count");
+
+	/*
+	 * Verify overflow actually happened: if total_visits > unique_elem_count,
+	 * some elements were visited multiple times due to seq_file restart.
+	 */
+	ASSERT_GT(skel->bss->total_visits, skel->bss->unique_elem_count, "overflow_occurred");
+
+	/*
+	 * Verify:
+	 * 1. Each chunk of print_count size has same values
+	 * 2. All values 0 to num_elems-1 appear exactly once
+	 */
+	for (i = 0; i < num_elems; i++) {
+		__u64 *val = ((__u64 *)buf) + i * skel->bss->print_count;
+
+		ASSERT_GE(val[0], 0, "value_greater_or_eq_zero");
+		ASSERT_LT(val[0], num_elems, "value_in_range");
+
+		/* Verify all copies in this chunk are consistent */
+		for (j = 1; j < skel->bss->print_count; j++)
+			ASSERT_EQ(val[0], val[j], "consistent_value");
+
+		/* Track which values we've seen */
+		seen_values |= (1ULL << val[0]);
+	}
+
+	/* Verify all values 0 to num_elems-1 were present */
+	ASSERT_EQ(seen_values, ~0ULL, "all_values_seen");
+
+	free(buf);
+close_iter:
+	close(iter_fd);
+free_link:
+	bpf_link__destroy(link);
+out:
+	bpf_iter_bpf_rhash_map__destroy(skel);
+}
+
 void test_rhash(void)
 {
 	if (test__start_subtest("test_rhash_lookup_update"))
@@ -313,5 +475,11 @@ void test_rhash(void)
 
 	if (test__start_subtest("test_rhash_get_next_key_stress"))
 		rhash_get_next_key_stress_test();
+
+	if (test__start_subtest("test_rhash_iter"))
+		rhash_iter_test();
+
+	if (test__start_subtest("test_rhash_iter_overflow"))
+		rhash_iter_overflow_test();
 }
 
tools/testing/selftests/bpf/progs/bpf_iter_bpf_rhash_map.c new file +75 -0

75 lines not on this page · raw message

Signature · 1 line
2.53.0
#16 lore raw

Re: [PATCH RFC bpf-next 10/12] selftests/bpf: Add BPF iterator tests for resizable hash map

Should this be checking len instead of err? The err variable was last set during the map population loop above and isn't updated by the read loop. At this point err is always 0 if we got here…
Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/rhash.c +0 -0
index 689ba6d73..ee8f4181d 100644

[ ... ]

Quoted 2 lines
tools/testing/selftests/bpf/prog_tests/rhash.c +2 -0
+static void rhash_iter_overflow_test(void)
+{

[ ... ]

Quoted 8 lines
tools/testing/selftests/bpf/prog_tests/rhash.c +8 -0
+	/* Populate map with test data */
+	for (i = 0; i < num_elems; i++) {
+		__u64 val = i;
+
+		err = bpf_map_update_elem(map_fd, &i, &val, BPF_NOEXIST);
+		if (!ASSERT_OK(err, "map_update"))
+			goto out;
+	}

[ ... ]

tools/testing/selftests/bpf/prog_tests/rhash.c static void rhash_get_next_key_resize_test(void) · line 406

Quoted 6 lines
tools/testing/selftests/bpf/prog_tests/rhash.c +6 -0
+	/* Read all data - this should trigger multiple overflows/restarts */
+	total_read_len = 0;
+	while ((len = read(iter_fd, buf + total_read_len, expected_read_len - total_read_len)) > 0)
+		total_read_len += len;
+
+	ASSERT_OK(err, "err");
            ^^^

Should this be checking len instead of err? The err variable was last set during the map population loop above and isn't updated by the read loop. At this point err is always 0 if we got here successfully, so this assertion provides no validation of the read operations.

Quoted 1 line
tools/testing/selftests/bpf/prog_tests/rhash.c +1 -0
+	ASSERT_EQ(total_read_len, expected_read_len, "total_read_len");

[ ... ]

tools/testing/selftests/bpf/prog_tests/rhash.c static void rhash_get_next_key_resize_test(void) · line 424

Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/rhash.c +4 -0
+	for (i = 0; i < num_elems; i++) {
+		__u64 *val = ((__u64 *)buf) + i * skel->bss->print_count;
+
+		ASSERT_GE(val[0], 0, "value_greater_or_eq_zero");
                        ^^^

This isn't a bug, but val[0] is __u64 (unsigned), so this comparison with 0 is always true. The assertion provides no validation.

Quoted 1 line
tools/testing/selftests/bpf/prog_tests/rhash.c +1 -0
+		ASSERT_LT(val[0], num_elems, "value_in_range");

[ ... ]

Quoted 5 lines
tools/testing/selftests/bpf/progs/bpf_iter_bpf_rhash_map.c new file +0 -0
new file mode 100644
index 000000000..2de69f983

[ ... ]

Quoted 6 lines
tools/testing/selftests/bpf/progs/bpf_iter_bpf_rhash_map.c new file +6 -0
+SEC("iter/bpf_map_elem")
+int dump_bpf_rhash_map_overflow(struct bpf_iter__bpf_map_elem *ctx)
+{
+	struct seq_file *seq = ctx->meta->seq;
+	__u32 *key = ctx->key;
+	__u64 *val = ctx->value;

[ ... ]

tools/testing/selftests/bpf/progs/bpf_iter_bpf_rhash_map.c line 58

Quoted 2 lines
tools/testing/selftests/bpf/progs/bpf_iter_bpf_rhash_map.c new file +2 -0
+	/* Validate key value are as expected */
+	if (*key != *val || *key < 0 || *key > 64) {
                          ^^^^^^^^^^

This isn't a bug, but *key is __u32 (unsigned), so *key < 0 is always false.

tools/testing/selftests/bpf/progs/bpf_iter_bpf_rhash_map.c line 61

Quoted 3 lines
tools/testing/selftests/bpf/progs/bpf_iter_bpf_rhash_map.c new file +3 -0
+		err = 1;
+		return 0;
+	}

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/21727734472

AI-authorship-score: low
AI-authorship-explanation: The code follows standard BPF selftest patterns with appropriate test structure and naming conventions typical of human-authored kernel tests.
issues-found: 3
issue-severity-score: low
issue-severity-explanation: All issues are minor code quality concerns in test code: a stale variable assertion and unsigned comparisons with zero that are always true/false.

#17 lore raw

RFC PATCH 11/12 selftests/bpf: Verify resizable hash map is rejected in tracing progs

In reply to Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

Verify that resizable hash map can't be used in tracing progs, as it uses bit_spin_lock for per-bucket locking which can deadlock in NMI context.

---
 tools/testing/selftests/bpf/prog_tests/verifier.c  |   2 +
 tools/testing/selftests/bpf/progs/verifier_rhash.c | 112 +++++++++++++++++++++
 2 files changed, 114 insertions(+)
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
index 302286a80154d37e1e81bef405c2806d1310c252..ef42781a9c1856600a52b4d04f78fb0fd7b54bfb 100644
@@ -79,6 +79,7 @@
 #include "verifier_reg_equal.skel.h"
 #include "verifier_ref_tracking.skel.h"
 #include "verifier_regalloc.skel.h"
+#include "verifier_rhash.skel.h"
 #include "verifier_ringbuf.skel.h"
 #include "verifier_runtime_jit.skel.h"
 #include "verifier_scalar_ids.skel.h"
@@ -222,6 +223,7 @@ void test_verifier_raw_tp_writable(void)      { RUN(verifier_raw_tp_writable); }
 void test_verifier_reg_equal(void)            { RUN(verifier_reg_equal); }
 void test_verifier_ref_tracking(void)         { RUN(verifier_ref_tracking); }
 void test_verifier_regalloc(void)             { RUN(verifier_regalloc); }
+void test_verifier_rhash(void)                { RUN(verifier_rhash); }
 void test_verifier_ringbuf(void)              { RUN(verifier_ringbuf); }
 void test_verifier_runtime_jit(void)          { RUN(verifier_runtime_jit); }
 void test_verifier_scalar_ids(void)           { RUN(verifier_scalar_ids); }
tools/testing/selftests/bpf/progs/verifier_rhash.c new file +112 -0

112 lines not on this page · raw message

Signature · 1 line
2.53.0
#18 lore raw

RFC PATCH 12/12 bpftool: Add rhash map documentation

In reply to Mykyta Yatsenko

From: Mykyta Yatsenko <[email protected]>

Make bpftool documentation aware of the resizable hash map.

---
 tools/bpf/bpftool/Documentation/bpftool-map.rst | 2 +-
 tools/bpf/bpftool/map.c                         | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)
tools/bpf/bpftool/Documentation/bpftool-map.rst +1 -1
index 1af3305ea2b2e396be9873483ef24877bc80b9e6..5daf3de5c7446a5b32328887ae7efcb2cbc36993 100644
@@ -56,7 +56,7 @@ MAP COMMANDS
 |     | **cgroup_storage** | **reuseport_sockarray** | **percpu_cgroup_storage**
 |     | **queue** | **stack** | **sk_storage** | **struct_ops** | **ringbuf** | **inode_storage**
 |     | **task_storage** | **bloom_filter** | **user_ringbuf** | **cgrp_storage** | **arena**
-|     | **insn_array** }
+|     | **insn_array** | **rhash** }
 
 DESCRIPTION
 ===========
tools/bpf/bpftool/map.c +1 -1
index 7ebf7dbcfba4ff62b63c84d3de1f95f540fe09e6..71a45d96617edbb85244260c05e572abb17369ea 100644
@@ -1478,7 +1478,7 @@ static int do_help(int argc, char **argv)
 		"                 cgroup_storage | reuseport_sockarray | percpu_cgroup_storage |\n"
 		"                 queue | stack | sk_storage | struct_ops | ringbuf | inode_storage |\n"
 		"                 task_storage | bloom_filter | user_ringbuf | cgrp_storage | arena |\n"
-		"                 insn_array }\n"
+		"                 insn_array | rhash }\n"
 		"       " HELP_SPEC_OPTIONS " |\n"
 		"                    {-f|--bpffs} | {-n|--nomount} }\n"
 		"",
Signature · 1 line
2.53.0