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

[Mykyta Yatsenko <mykyta.yatsenko5@gmail.com>]

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