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