Skip to contentSkip to conversation

bpf: bound resizable hash map iteration

PATCH In review Hui Su 3 participants 5 messages Aug 31 – Sep 4

Subsystems (3)
lore
Share & tools
lore

Hui Su

author
#0 lore raw

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

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")

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

---
 kernel/bpf/hashtab.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
kernel/bpf/hashtab.c +5 -2
index d40cb5dd446c..2cad67c90154 100644
@@ -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

Signature · 1 line
2.54.0
author
#1 lore raw

PATCH v2 2/2 selftests/bpf: add RHASH iteration stress test

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.

---
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.

---
 .../testing/selftests/bpf/prog_tests/rhash.c  | 113 ++++++++++++++++++
 tools/testing/selftests/bpf/progs/rhash.c     |  41 +++++++
 2 files changed, 154 insertions(+)
tools/testing/selftests/bpf/prog_tests/rhash.c +113 -0
index 98bb66907b7f..f1a0a8e3fc1a 100644
@@ -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();
 }
tools/testing/selftests/bpf/progs/rhash.c +41 -0

61 lines not on this page · raw message

Signature · 1 line
2.54.0
#2 lore raw

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

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider: - [Medium] Missing Error Check / Integer Signedness Bug in BPF map iteration - [Medium] Flawed test logic…

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [Medium] Missing Error Check / Integer Signedness Bug in BPF map iteration
- [Medium] Flawed test logic caps maximum iterations at working set size, causing flaky failures on valid duplicate visits --

commit a9ec4aae45f967791f38abbe6d019f58ee4a93fe
Author: Hui Su <[email protected]>

selftests/bpf: add RHASH iteration stress test

This commit adds a stress test for bpf_for_each_map_elem() on BPF_MAP_TYPE_RHASH. It concurrently updates and deletes entries from two threads while repeatedly invoking the BPF callback to verify that the map iterator handles concurrent rehashing correctly.

Quoted 3 lines
tools/testing/selftests/bpf/progs/rhash.c +0 -0

[ ... ]

Quoted 8 lines
tools/testing/selftests/bpf/progs/rhash.c +4 -0
@@ -246,3 +267,23 @@ int test_rhash_delete_nonexistent(void *ctx)
 	err = 0;
 	return 0;
 }
+
+SEC("syscall")
+int test_rhash_iter_stress(void *ctx)
+{

tools/testing/selftests/bpf/progs/rhash.c int test_rhash_delete_nonexistent(void *ctx) · line 283

Quoted 10 lines
tools/testing/selftests/bpf/progs/rhash.c +10 -0
+	/*
+	 * 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;

[Severity: Medium]
What happens if bpf_for_each_map_elem() encounters an error and returns a negative error code like -EINVAL?

Because visits is a signed long and stress_max_visits is a volatile __u64, the C integer promotion rules will convert the negative error code into a large positive unsigned value (e.g., ~1.84e19).

Does this missing error check regression corrupt the stress_max_visits state and mask the failure as a massive success count?

tools/testing/selftests/bpf/progs/rhash.c int test_rhash_delete_nonexistent(void *ctx) · line 285

Quoted 2 lines
tools/testing/selftests/bpf/progs/rhash.c +2 -0
+	if (visits > stress_working_set)
+		stress_overruns++;

[Severity: Medium]
Could this condition cause sporadic test failures by incorrectly flagging legitimate runtime behavior as an overrun?

The commit message notes that concurrent rehashing may cause duplicate visits, which are permitted by RHASH's best-effort iteration semantics. If a walk occurs when the map is fully populated with 4096 elements and encounters even one permitted duplicate visit (e.g., due to a rehash moving a visited element into a remaining bucket), the callback count will be 4097.

Since 4097 strictly exceeds stress_working_set (4096), stress_overruns will increment, which will then cause the userspace assertion ASSERT_EQ(skel->bss->stress_overruns, 0) in rhash_iter_stress() to fail.

Should there be headroom allowed above the working set size to account for these permitted duplicate visits?

Quoted 4 lines
tools/testing/selftests/bpf/progs/rhash.c +4 -0
+	if (visits == stress_working_set)
+		stress_full_walks++;
+	return 0;
+}
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
#3 lore raw
In reply to Hui Su
Quoted 22 lines · 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")
Quoted 7 lines

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

---

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.

Quoted 30 lines
 kernel/bpf/hashtab.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
kernel/bpf/hashtab.c +5 -2
index d40cb5dd446c..2cad67c90154 100644
@@ -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

author
#4 lore raw
Quoted 11 lines · Mykyta Yatsenko

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