[PATCH bpf 1/2] bpf: bound resizable hash map iteration

[PATCH bpf 1/2] bpf: bound resizable hash map iteration

[Hui Su]

rhashtable_next_key() provides a best-effort walk that may revisit
entries and is not guaranteed to terminate under sustained rehashing.
Callers performing a full iteration are expected to bound the walk
externally.

bpf_each_rhash_elem() currently loops until rhashtable_next_key()
returns NULL, leaving callback execution without a finite bound. Bound
one walk by map->max_entries while preserving the existing best-effort
semantics.

Use map->max_entries as the iteration budget. Duplicate visits may
consume the budget and cause the walk to stop before all keys are
observed, but RHASH iteration already permits missed elements under
concurrent mutation.

This is reproducible with concurrent updates and deletes triggering
rehash. With max_entries=4096, one walk invoked the callback 5239 times
on an unpatched kernel. With the bound in place, callback invocations did
not exceed 4096 in the same stress test.

Fixes: 818e00848227 ("bpf: Implement iteration ops for resizable hashtab")
Signed-off-by: Hui Su <sh_def@163.com>
---
 kernel/bpf/hashtab.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index d40cb5dd446c..3772e63f2f12 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -3198,7 +3198,7 @@ static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn,
 	struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
 	void *prev_key = NULL;
 	struct rhtab_elem *elem;
-	int num_elems = 0;
+	u32 num_elems = 0;
 	u64 ret = 0;
 
 	cant_migrate();
@@ -3212,7 +3212,8 @@ static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn,
 	 * elements are deleted/inserted, there may be missed or duplicate
 	 * elements visited.
 	 */
-	while ((elem = rhashtable_next_key(&rhtab->ht, prev_key))) {
+	while (num_elems < map->max_entries &&
+	       (elem = rhashtable_next_key(&rhtab->ht, prev_key))) {
 		if (IS_ERR(elem))
 			break;
 		num_elems++;

base-commit: c20313e98b04ce543936431b6122dd639d3a8346
-- 
2.54.0

[PATCH bpf 2/2] selftests/bpf: add RHASH iteration stress test

[Hui Su]

Add a stress test for bpf_for_each_map_elem() on
BPF_MAP_TYPE_RHASH. Update and delete entries from two threads while
repeatedly running the BPF callback, and record the maximum number of
callback invocations in one walk.

Concurrent rehashing may cause duplicate visits, which are permitted by
RHASH's best-effort iteration semantics. Verify that
bpf_for_each_map_elem() nevertheless limits one walk to at most
map->max_entries callback invocations.

Signed-off-by: Hui Su <sh_def@163.com>
---
 .../testing/selftests/bpf/prog_tests/rhash.c  | 97 +++++++++++++++++++
 tools/testing/selftests/bpf/progs/rhash.c     | 36 +++++++
 2 files changed, 133 insertions(+)

diff --git a/tools/testing/selftests/bpf/prog_tests/rhash.c b/tools/testing/selftests/bpf/prog_tests/rhash.c
index 98bb66907b7f..a2ecd7e7905f 100644
--- a/tools/testing/selftests/bpf/prog_tests/rhash.c
+++ b/tools/testing/selftests/bpf/prog_tests/rhash.c
@@ -3,12 +3,17 @@
 #include <test_progs.h>
 #include <string.h>
 #include <stdio.h>
+#include <pthread.h>
+#include <stdatomic.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>
 
+#define RHASH_STRESS_KEYS		4096
+#define RHASH_STRESS_DURATION_NS	(3ULL * 1000000000ULL)
+
 static void rhash_run(const char *prog_name)
 {
 	struct rhash *skel;
@@ -53,6 +58,94 @@ static int rhash_map_create(__u32 max_entries, __u64 map_extra)
 			      sizeof(__u32), sizeof(__u64), max_entries, &opts);
 }
 
+struct rhash_stress_arg {
+	int map_fd;
+	atomic_bool *stop;
+	__u32 seed;
+};
+
+static void *rhash_stress_update(void *data)
+{
+	struct rhash_stress_arg *arg = data;
+	__u64 value = 0;
+	__u32 key;
+	int i;
+
+	while (!atomic_load(arg->stop)) {
+		for (i = 0; i < RHASH_STRESS_KEYS && !atomic_load(arg->stop); i++) {
+			key = ((__u32)i * 2654435761U + arg->seed) % RHASH_STRESS_KEYS;
+			bpf_map_update_elem(arg->map_fd, &key, &value, BPF_ANY);
+		}
+		for (i = 0; i < RHASH_STRESS_KEYS && !atomic_load(arg->stop); i++) {
+			key = ((__u32)i * 2654435761U + arg->seed) % RHASH_STRESS_KEYS;
+			bpf_map_delete_elem(arg->map_fd, &key);
+		}
+	}
+
+	return NULL;
+}
+
+static void rhash_iter_stress(void)
+{
+	struct rhash *skel = NULL;
+	struct rhash_stress_arg args[2];
+	LIBBPF_OPTS(bpf_test_run_opts, opts);
+	atomic_bool stop = false;
+	__u64 start;
+	__u32 max_entries;
+	pthread_t threads[2];
+	bool created[2] = {};
+	struct bpf_program *prog;
+	int map_fd, err, i;
+
+	skel = rhash__open();
+	if (!ASSERT_OK_PTR(skel, "rhash__open stress"))
+		return;
+
+	prog = bpf_object__find_program_by_name(skel->obj,
+						"test_rhash_iter_stress");
+	if (!ASSERT_OK_PTR(prog, "find stress program"))
+		goto cleanup;
+	bpf_program__set_autoload(prog, true);
+
+	err = rhash__load(skel);
+	if (!ASSERT_OK(err, "stress skel_load"))
+		goto cleanup;
+
+	map_fd = bpf_map__fd(skel->maps.stress_rhmap);
+	max_entries = bpf_map__max_entries(skel->maps.stress_rhmap);
+	for (i = 0; i < ARRAY_SIZE(threads); i++) {
+		args[i].map_fd = map_fd;
+		args[i].stop = &stop;
+		args[i].seed = i * 977;
+		err = pthread_create(&threads[i], NULL, rhash_stress_update,
+				     &args[i]);
+		if (!ASSERT_OK(err, "pthread_create"))
+			goto stop_threads;
+		created[i] = true;
+	}
+
+	start = get_time_ns();
+	while (get_time_ns() - start < RHASH_STRESS_DURATION_NS) {
+		err = bpf_prog_test_run_opts(bpf_program__fd(prog), &opts);
+		if (!ASSERT_OK(err, "stress prog run"))
+			break;
+	}
+
+stop_threads:
+	atomic_store(&stop, true);
+	for (i = 0; i < ARRAY_SIZE(threads); i++)
+		if (created[i])
+			pthread_join(threads[i], NULL);
+
+	ASSERT_GT(skel->bss->stress_max_visits, 0, "stress callback visits");
+	ASSERT_EQ(skel->bss->stress_overruns, 0, "stress callback bound");
+	printf("stress max callback visits: %llu (limit %u)\n",
+	       (unsigned long long)skel->bss->stress_max_visits, max_entries);
+cleanup:
+	rhash__destroy(skel);
+}
+
 static void rhash_map_extra_presize(void)
 {
 	const __u32 max_entries = 1024;
@@ -180,4 +273,8 @@ void test_rhash(void)
 
 	if (test__start_subtest("test_rhash_iter"))
 		rhash_iter_test();
+
+	if (test__start_subtest("test_rhash_iter_stress"))
+		rhash_iter_stress();
+
 }
diff --git a/tools/testing/selftests/bpf/progs/rhash.c b/tools/testing/selftests/bpf/progs/rhash.c
index fc2dac3a719e..eca428db1fbc 100644
--- a/tools/testing/selftests/bpf/progs/rhash.c
+++ b/tools/testing/selftests/bpf/progs/rhash.c
@@ -9,11 +9,15 @@
 
 #define ENOENT 2
 #define EEXIST 17
+#define RHASH_STRESS_MAX_ENTRIES 4096
 
 char _license[] SEC("license") = "GPL";
 
 int err;
 
+volatile __u64 stress_max_visits;
+volatile __u64 stress_overruns;
+
 struct elem {
 	char arr[128];
 	int val;
@@ -27,6 +31,20 @@ struct {
 	__type(value, struct elem);
 } rhmap SEC(".maps");
 
+struct {
+	__uint(type, BPF_MAP_TYPE_RHASH);
+	__uint(map_flags, BPF_F_NO_PREALLOC);
+	__uint(max_entries, RHASH_STRESS_MAX_ENTRIES);
+	__type(key, __u32);
+	__type(value, __u64);
+} stress_rhmap SEC(".maps");
+
+static __u64 stress_iter_cb(struct bpf_map *map, __u32 *key, __u64 *val,
+			    void *ctx)
+{
+	return 0;
+}
+
 SEC("syscall")
 int test_rhash_lookup_update(void *ctx)
 {
@@ -246,3 +264,21 @@ int test_rhash_delete_nonexistent(void *ctx)
 	err = 0;
 	return 0;
 }
+
+SEC("syscall")
+int test_rhash_iter_stress(void *ctx)
+{
+	/*
+	 * Concurrent rehash may produce duplicate visits. Check that the
+	 * helper still gives one walk a finite callback bound; no snapshot
+	 * or unique-visit guarantee is expected here.
+	 */
+	long visits;
+
+	visits = bpf_for_each_map_elem(&stress_rhmap, stress_iter_cb, NULL, 0);
+	if (visits > stress_max_visits)
+		stress_max_visits = visits;
+	if (visits > RHASH_STRESS_MAX_ENTRIES)
+		stress_overruns++;
+	return 0;
+}
-- 
2.54.0

Re: [PATCH bpf 1/2] bpf: bound resizable hash map iteration

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:

Pre-existing issues:
- [High] The iteration budget `map->max_entries` is insufficient to prevent severe RCU stalls because RHASH maps decouple `max_entries` from memory constraints.
--

commit e7196eb4e04d6b29df6a798ca5bcbe264c41d6e2
Author: Hui Su <sh_def@163.com>

bpf: bound resizable hash map iteration

This patch attempts to fix an unbounded iteration loop in bpf_each_rhash_elem
by using map->max_entries as an iteration budget. Duplicate visits consume the
budget to ensure termination under concurrent mutations.

> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> index d40cb5dd446ca..3772e63f2f12f 100644
> --- a/kernel/bpf/hashtab.c
> +++ b/kernel/bpf/hashtab.c

[ ... ]

> @@ -3212,7 +3212,8 @@ static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn,
>  	 * elements are deleted/inserted, there may be missed or duplicate
>  	 * elements visited.
>  	 */
> -	while ((elem = rhashtable_next_key(&rhtab->ht, prev_key))) {
> +	while (num_elems < map->max_entries &&
> +	       (elem = rhashtable_next_key(&rhtab->ht, prev_key))) {

[Severity: High]
This is a pre-existing issue, but will this bound be sufficient to prevent
RCU stalls if max_entries is set to its maximum limit?

For a BPF_MAP_TYPE_RHASH map, max_entries can be up to 1UL << 31 
(2.14 billion) because the map requires BPF_F_NO_PREALLOC. This decouples 
max_entries from memory constraints, meaning a user can instantly create a 
map with the maximum limit using negligible memory.

If a user invokes the bpf_for_each_map_elem helper on this map while
concurrently mutating it from user space, the loop could repeatedly yield
duplicate elements.

Executing this callback 2.14 billion times inside an rcu_read_lock section 
without cond_resched() will still take dozens of seconds. This easily 
eclipses the standard 21-second RCU stall or 20-second soft lockup 
thresholds, allowing a Denial of Service.

Could a smaller, fixed iteration limit or a time-based check be used here 
instead to ensure the loop terminates before a stall occurs?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260828183326.3330530-1-sh_def@163.com?part=1

Re: [PATCH bpf 2/2] selftests/bpf: add RHASH iteration stress test

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 6896 bytes --]

> diff --git a/tools/testing/selftests/bpf/prog_tests/rhash.c b/tools/testing/selftests/bpf/prog_tests/rhash.c
> index 98bb66907b7f..a2ecd7e7905f 100644
> --- a/tools/testing/selftests/bpf/prog_tests/rhash.c
> +++ b/tools/testing/selftests/bpf/prog_tests/rhash.c
> @@ -3,12 +3,17 @@
>  #include <test_progs.h>
>  #include <string.h>
>  #include <stdio.h>
> +#include <pthread.h>
> +#include <stdatomic.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>
>
> +#define RHASH_STRESS_KEYS		4096
> +#define RHASH_STRESS_DURATION_NS	(3ULL * 1000000000ULL)
                                       ^^^^

A subsystem pattern flags this as potentially concerning: the userspace
RHASH_STRESS_KEYS (4096) has to stay equal to stress_rhmap's
max_entries (RHASH_STRESS_MAX_ENTRIES, 4096 in progs/rhash.c:12) for
the test to keep its meaning. The point of the stress driver is to keep
the map at its capacity so that rehashing happens and a walk has enough
elements to exceed the budget. These are two independent literals in two
different files with no compile-time or run-time tie, so raising the map
size in the BPF object silently leaves the userspace threads churning
only the first 4096 keys.

The function fetches the authoritative value at line 113
(max_entries = bpf_map__max_entries(skel->maps.stress_rhmap);)
but uses it only for the printf() at line 144, so the key range could be
driven from max_entries instead of a duplicated literal.

Could the value that gates the assertion (RHASH_STRESS_MAX_ENTRIES) be
used both for max_entries and for the overrun threshold to avoid drift,
or could the userspace key range be driven from the fetched max_entries?

>
>  static void rhash_run(const char *prog_name)
>  {

[ ... ]

> +static void rhash_iter_stress(void)
> +{
> +	struct rhash *skel = NULL;
> +	struct rhash_stress_arg args[2];
> +	LIBBPF_OPTS(bpf_test_run_opts, opts);
> +	atomic_bool stop = false;
> +	__u64 start;
> +	__u32 max_entries;
> +	pthread_t threads[2];
> +	bool created[2] = {};
> +	struct bpf_program *prog;
> +	int map_fd, err, i;
> +
> +	skel = rhash__open();
> +	if (!ASSERT_OK_PTR(skel, "rhash__open stress"))
> +		return;
> +
> +	prog = bpf_object__find_program_by_name(skel->obj,
> +						"test_rhash_iter_stress");
> +	if (!ASSERT_OK_PTR(prog, "find stress program"))
> +		goto cleanup;
> +	bpf_program__set_autoload(prog, true);
> +
> +	err = rhash__load(skel);
> +	if (!ASSERT_OK(err, "stress skel_load"))
> +		goto cleanup;
> +
> +	map_fd = bpf_map__fd(skel->maps.stress_rhmap);
> +	max_entries = bpf_map__max_entries(skel->maps.stress_rhmap);
> +	for (i = 0; i < ARRAY_SIZE(threads); i++) {
> +		args[i].map_fd = map_fd;
> +		args[i].stop = &stop;
> +		args[i].seed = i * 977;
> +		err = pthread_create(&threads[i], NULL, rhash_stress_update,
> +				     &args[i]);
> +		if (!ASSERT_OK(err, "pthread_create"))
> +			goto stop_threads;
> +		created[i] = true;
> +	}
> +
> +	start = get_time_ns();
> +	while (get_time_ns() - start < RHASH_STRESS_DURATION_NS) {
> +		err = bpf_prog_test_run_opts(bpf_program__fd(prog), &opts);
> +		if (!ASSERT_OK(err, "stress prog run"))
> +			break;
> +	}
> +
> +stop_threads:
> +	atomic_store(&stop, true);
> +	for (i = 0; i < ARRAY_SIZE(threads); i++)
> +		if (created[i])
> +			pthread_join(threads[i], NULL);
> +
> +	ASSERT_GT(skel->bss->stress_max_visits, 0, "stress callback visits");
> +	ASSERT_EQ(skel->bss->stress_overruns, 0, "stress callback bound");
        ^^^^

Does the stop_threads label fall straight through into the result
assertions? If pthread_create() fails for i == 0 the BPF program is
never run, so skel->bss->stress_max_visits is still 0 and
ASSERT_GT(skel->bss->stress_max_visits, 0, ...) emits a second,
misleading failure (unexpected stress callback visits: actual 0 <=
expected 0) on top of the real pthread_create failure. The printf()
then reports "stress max callback visits: 0 (limit 4096)" as if a
measurement had been taken.

The same fall-through happens when bpf_prog_test_run_opts() fails on
the very first iteration (break out of the timing loop). Every other
error path in the function uses goto cleanup to skip the result checks.

Should the thread-creation path goto cleanup, or should the two result
assertions be guarded by a flag recording that at least one prog run
completed?

A subsystem pattern flags this as potentially concerning: the
load-bearing assertion is ASSERT_EQ(skel->bss->stress_overruns, 0),
i.e. no single walk returned more than max_entries. On a kernel without
the iteration bound fix, the walk still terminates naturally after
visiting roughly nelems (<= 4096) entries whenever the
rehash-during-walk race does not fire, so stress_overruns stays 0 and
the subtest reports PASS on the unfixed kernel.

Nothing in the test reports whether the race was actually exercised:
bpf_each_rhash_elem() runs under migrate_disable() + rcu_read_lock(), so
on a 1-vCPU CI VM the two updater threads cannot mutate the table during
a walk at all and the test can never detect the bug there, yet it still
passes.

The companion liveness check, ASSERT_GT(skel->bss->stress_max_visits,
0), is satisfied by a single visited element, and stress_max_visits
reads ~4096 both when the budget clamped a duplicate-heavy walk and when
a quiescent walk simply covered the whole table, so the printed number
cannot distinguish a real pass from a vacuous one either.

This isn't a bug, but would it be worth recording something that proves
the stress happened, such as a count of walks that consumed the full
max_entries budget, or a skip/warning when libbpf_num_possible_cpus()
is 1?

> +	printf("stress max callback visits: %llu (limit %u)\n",
> +	       (unsigned long long)skel->bss->stress_max_visits, max_entries);
> +cleanup:
> +	rhash__destroy(skel);
> +}

[ ... ]

> diff --git a/tools/testing/selftests/bpf/progs/rhash.c b/tools/testing/selftests/bpf/progs/rhash.c
> index fc2dac3a719e..eca428db1fbc 100644
> --- a/tools/testing/selftests/bpf/progs/rhash.c
> +++ b/tools/testing/selftests/bpf/progs/rhash.c

[ ... ]

> +SEC("syscall")
> +int test_rhash_iter_stress(void *ctx)
> +{
> +	/*
> +	 * Concurrent rehash may produce duplicate visits. Check that the
> +	 * helper still gives one walk a finite callback bound; no snapshot
> +	 * or unique-visit guarantee is expected here.
> +	 */
> +	long visits;
> +
> +	visits = bpf_for_each_map_elem(&stress_rhmap, stress_iter_cb, NULL, 0);
> +	if (visits > stress_max_visits)
> +		stress_max_visits = visits;
> +	if (visits > RHASH_STRESS_MAX_ENTRIES)
> +		stress_overruns++;
> +	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/33200467478