Skip to contentSkip to conversation

bpf: bound resizable hash map iteration

PATCH Superseded Hui Su 3 participants 4 messages Aug 28

Subsystems (3)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Hui Su

author
#0 lore raw

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

Signature · 1 line
2.54.0
author
#1 lore raw

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

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.

---
 .../testing/selftests/bpf/prog_tests/rhash.c  | 97 +++++++++++++++++++
 tools/testing/selftests/bpf/progs/rhash.c     | 36 +++++++
 2 files changed, 133 insertions(+)
tools/testing/selftests/bpf/prog_tests/rhash.c +97 -0
index 98bb66907b7f..a2ecd7e7905f 100644
@@ -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();
+
 }
tools/testing/selftests/bpf/progs/rhash.c +36 -0
index fc2dac3a719e..eca428db1fbc 100644
@@ -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;
+}
Signature · 1 line
2.54.0
#2 lore raw

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

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)…
Quoted 8 lines
tools/testing/selftests/bpf/prog_tests/rhash.c +0 -0
index 98bb66907b7f..a2ecd7e7905f 100644
@@ -3,12 +3,17 @@
 #include <test_progs.h>
 #include <string.h>
 #include <stdio.h>

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

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/rhash.c +4 -0
+#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?

Quoted 3 lines
tools/testing/selftests/bpf/prog_tests/rhash.c +0 -0
 static void rhash_run(const char *prog_name)
 {

[ ... ]

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

tools/testing/selftests/bpf/prog_tests/rhash.c static int rhash_map_create(__u32 max_entries, __u64 map_extra) · line 142

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/rhash.c +10 -0
+	}
+
+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?

Quoted 5 lines
tools/testing/selftests/bpf/prog_tests/rhash.c +5 -0
+	printf("stress max callback visits: %llu (limit %u)\n",
+	       (unsigned long long)skel->bss->stress_max_visits, max_entries);
+cleanup:
+	rhash__destroy(skel);
+}

[ ... ]

Quoted 4 lines
tools/testing/selftests/bpf/progs/rhash.c +0 -0
index fc2dac3a719e..eca428db1fbc 100644

[ ... ]

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

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

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

#3 lore raw
In reply to Hui Su
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:

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 <[email protected]>

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.

Quoted 4 lines
kernel/bpf/hashtab.c +0 -0
index d40cb5dd446ca..3772e63f2f12f 100644

[ ... ]

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

Quoted 7 lines
kernel/bpf/hashtab.c +2 -1
@@ -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?

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1