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

[PATCH bpf v2 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. Sample
rhashtable's current element count and use it as the iteration budget.
This keeps the bound proportional to current occupancy instead of the
potentially much larger map capacity.

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>
---
Changes in v2:
- Bound the walk by the sampled rhashtable element count instead of
  map->max_entries, keeping the budget proportional to occupancy.

Link: https://lore.kernel.org/bpf/20260828183326.3330530-1-sh_def@163.com/
---
 kernel/bpf/hashtab.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index d40cb5dd446c..2cad67c90154 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -3198,7 +3198,8 @@ 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 visit_budget;
+	u32 num_elems = 0;
 	u64 ret = 0;
 
 	cant_migrate();
@@ -3212,7 +3213,9 @@ 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))) {
+	visit_budget = atomic_read(&rhtab->ht.nelems);
+	while (num_elems < visit_budget &&
+	       (elem = rhashtable_next_key(&rhtab->ht, prev_key))) {
 		if (IS_ERR(elem))
 			break;
 		num_elems++;

base-commit: c20313e98b04ce543936431b6122dd639d3a8346
-- 
2.54.0

[PATCH bpf v2 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.

Use a large map capacity and a smaller working set so the test also
covers sparse maps where max_entries greatly exceeds current occupancy.
Concurrent rehashing may cause duplicate visits, which are permitted by
RHASH's best-effort iteration semantics. Verify that
bpf_for_each_map_elem() does not exceed the working set in one walk and
that at least one walk consumes the full working-set-sized budget.

Signed-off-by: Hui Su <sh_def@163.com>
---
Changes in v2:
- Use a large map capacity and a smaller BPF rodata working set.
- Skip the stress test when fewer than two CPUs are available.
- Avoid result assertions unless a program run completed successfully.
- Record full walks to make vacuous stress passes less likely.
- Use the BPF rodata working set as the single source of truth.

Link: https://lore.kernel.org/bpf/20260828183326.3330530-2-sh_def@163.com/
---
 .../testing/selftests/bpf/prog_tests/rhash.c  | 113 ++++++++++++++++++
 tools/testing/selftests/bpf/progs/rhash.c     |  41 +++++++
 2 files changed, 154 insertions(+)

diff --git a/tools/testing/selftests/bpf/prog_tests/rhash.c b/tools/testing/selftests/bpf/prog_tests/rhash.c
index 98bb66907b7f..f1a0a8e3fc1a 100644
--- a/tools/testing/selftests/bpf/prog_tests/rhash.c
+++ b/tools/testing/selftests/bpf/prog_tests/rhash.c
@@ -3,12 +3,16 @@
 #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_DURATION_NS	(3ULL * 1000000000ULL)
+
 static void rhash_run(const char *prog_name)
 {
 	struct rhash *skel;
@@ -53,6 +57,112 @@ 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 nr_keys;
+	__u32 seed;
+};
+
+static void *rhash_stress_update(void *data)
+{
+	struct rhash_stress_arg *arg = data;
+	__u64 value = 0;
+	__u32 key;
+	__u32 i;
+
+	while (!atomic_load(arg->stop)) {
+		for (i = 0; i < arg->nr_keys && !atomic_load(arg->stop); i++) {
+			key = ((__u32)i * 2654435761U + arg->seed) % arg->nr_keys;
+			bpf_map_update_elem(arg->map_fd, &key, &value, BPF_ANY);
+		}
+		for (i = 0; i < arg->nr_keys && !atomic_load(arg->stop); i++) {
+			key = ((__u32)i * 2654435761U + arg->seed) % arg->nr_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;
+	bool ran = false;
+	__u64 start;
+	pthread_t threads[2];
+	bool created[2] = {};
+	struct bpf_program *prog;
+	int nr_cpus;
+	__u32 working_set;
+	int map_fd, err, i;
+
+	nr_cpus = libbpf_num_possible_cpus();
+	if (!ASSERT_GT(nr_cpus, 0, "num_possible_cpus"))
+		return;
+	if (nr_cpus < 2) {
+		test__skip();
+		return;
+	}
+
+	skel = rhash__open();
+	if (!ASSERT_OK_PTR(skel, "rhash__open stress"))
+		return;
+	working_set = skel->rodata->stress_working_set;
+
+	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);
+	for (i = 0; i < ARRAY_SIZE(threads); i++) {
+		args[i].map_fd = map_fd;
+		args[i].stop = &stop;
+		args[i].nr_keys = working_set;
+		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"))
+			goto stop_threads;
+		ran = true;
+	}
+
+stop_threads:
+	atomic_store(&stop, true);
+	for (i = 0; i < ARRAY_SIZE(threads); i++)
+		if (created[i])
+			pthread_join(threads[i], NULL);
+
+	if (err || !ran)
+		goto cleanup;
+
+	ASSERT_GT(skel->bss->stress_max_visits, 0, "stress callback visits");
+	ASSERT_GT(skel->bss->stress_full_walks, 0, "stress full walks");
+	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,
+	       working_set);
+cleanup:
+	rhash__destroy(skel);
+}
+
 static void rhash_map_extra_presize(void)
 {
 	const __u32 max_entries = 1024;
@@ -180,4 +290,7 @@ 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..3d7201430bab 100644
--- a/tools/testing/selftests/bpf/progs/rhash.c
+++ b/tools/testing/selftests/bpf/progs/rhash.c
@@ -9,11 +9,18 @@
 
 #define ENOENT 2
 #define EEXIST 17
+#define RHASH_STRESS_MAX_ENTRIES (1U << 20)
 
 char _license[] SEC("license") = "GPL";
 
 int err;
 
+const volatile __u32 stress_working_set = 4096;
+
+volatile __u64 stress_max_visits;
+volatile __u64 stress_overruns;
+volatile __u64 stress_full_walks;
+
 struct elem {
 	char arr[128];
 	int val;
@@ -27,6 +34,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 +267,23 @@ 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 > stress_working_set)
+		stress_overruns++;
+	if (visits == stress_working_set)
+		stress_full_walks++;
+	return 0;
+}
-- 
2.54.0

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

[Mykyta Yatsenko]

On 8/31/26 3:01 PM, Hui Su wrote:
> 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. Sample
> rhashtable's current element count and use it as the iteration budget.
> This keeps the bound proportional to current occupancy instead of the
> potentially much larger map capacity.
> 
> 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>
> ---
> Changes in v2:
> - Bound the walk by the sampled rhashtable element count instead of
>   map->max_entries, keeping the budget proportional to occupancy.
> 
> Link: https://lore.kernel.org/bpf/20260828183326.3330530-1-sh_def@163.com/
> ---

Thanks for sending the patch. I'm not sure if this change fixes anything,
the main issue of walking concurrently modified rhashtable is not changed: you
still may miss elements or visit same elements multiple times. In some scenarios
this can make things worse: imagine you start iterating with small map 
(visit_budget = 10), then 1000000 elements are inserted concurrently with walk,
so you'll miss at least 1000000 - 10. To me this is a trade off/taste 
thing, rather than bug fix.
The change is compact, though, I'm not against it.

>  kernel/bpf/hashtab.c | 7 +++++--
>  1 file changed, 5 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> index d40cb5dd446c..2cad67c90154 100644
> --- a/kernel/bpf/hashtab.c
> +++ b/kernel/bpf/hashtab.c
> @@ -3198,7 +3198,8 @@ 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 visit_budget;
> +	u32 num_elems = 0;
>  	u64 ret = 0;
>  
>  	cant_migrate();
> @@ -3212,7 +3213,9 @@ 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))) {
> +	visit_budget = atomic_read(&rhtab->ht.nelems);
> +	while (num_elems < visit_budget &&
> +	       (elem = rhashtable_next_key(&rhtab->ht, prev_key))) {
>  		if (IS_ERR(elem))
>  			break;
>  		num_elems++;
> 
> base-commit: c20313e98b04ce543936431b6122dd639d3a8346

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

[Hui Su]

On Thu, Sep 3, 2026 at 5:43 PM, Mykyta Yatsenko wrote:
> I'm not sure if this change fixes anything, the main issue of walking
> concurrently modified rhashtable is not changed: you still may miss
> elements or visit same elements multiple times.
>
> In some scenarios this can make things worse: imagine you start
> iterating with small map (visit_budget = 10), then 1000000 elements
> are inserted concurrently with walk, so you'll miss at least
> 1000000 - 10.
>
> To me this is a trade off/taste thing, rather than bug fix. The
> change is compact, though, I'm not against it.

Thanks for the review.

I agree that this change does not, and is not intended to, make
concurrent rhashtable iteration complete or duplicate-free. Missed and
duplicate elements remain part of the existing best-effort semantics.

The narrower issue I am trying to address is that bpf_each_rhash_elem()
currently keeps calling rhashtable_next_key() until it returns NULL.
The rhashtable_next_key() documentation states that a full iteration
may not terminate under adversarial or sustained rehashing, and
recommends that callers bound such walks externally.

The purpose of this change is therefore not to make the iteration
complete, but to provide a finite upper bound on callback invocations
under sustained rehashing.

I agree that taking a snapshot of ht.nelems makes the bound insensitive
to elements inserted after the walk starts. In the example you gave, the
walk could stop after the initial occupancy and miss most newly inserted
elements.

Using map->max_entries would preserve more of the existing behavior
under concurrent growth, at the cost of allowing a much longer walk for
a sparsely populated map.

Would map->max_entries be a more appropriate bound in your view?

Also, if you consider adding such a bound useful but not a bug fix,
would bpf-next be a more appropriate target for this change?

Thanks,
Hui