bpf: bound resizable hash map iteration
Subsystems (3)
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.
--- kernel/bpf/hashtab.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-)
kernel/bpf/hashtab.c +3 -2
@@ -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
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
@@ -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
@@ -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
[email protected]
AI reviewRe: [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@@ -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
-0static 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
[ ... ]
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
[email protected]
AI reviewThank 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
[ ... ]
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