Re: [PATCH bpf-next v5 01/11] rhashtable: Add rhashtable_next_key() API

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

On 5/28/26 7:16 PM, sashiko-bot@kernel.org wrote:
> Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider:
> - [Critical] rhashtable_next_key completely skips unmigrated elements if prev_key has already been migrated during a concurrent rehash.
> - [High] rhashtable_next_key enters an infinite loop if the hash table contains duplicate keys.
> - [High] Concurrent deletion of the prev_key element aborts the iteration prematurely and returns a dangerous ERR_PTR(-ENOENT) pointer.
> - [High] rhashtable_next_key silently ignores all duplicate elements when used on rhlist-enabled tables.
> --
> 
> commit 2aba1f7c85d79ee4c37a0c5013226a79bf52f189
> Author: Mykyta Yatsenko <yatsenko@meta.com>
> Subject: rhashtable: Add rhashtable_next_key() API
> 
> Introduce a simpler iteration mechanism for rhashtable that lets
> the caller continue from an arbitrary position by supplying the
> previous key, without the per-iterator state of the
> rhashtable_walk_* API.
> 
>> diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
>> index ef5230cece364..d6eb3ba476ea2 100644
>> --- a/include/linux/rhashtable.h
>> +++ b/include/linux/rhashtable.h
>> @@ -650,6 +650,97 @@ static __always_inline struct rhash_head *__rhashtable_lookup(
>>  	return NULL;
>>  }
>>  
>> +/* Internal: scan one element forward from prev_key's position.
>> + * Returns first rhash_head whose bucket >= prev_key's bucket and
>> + * (if within prev_key's bucket) appears after prev_key in chain.
>> + * Returns first element if prev_key is NULL or ERR_PTR(-ENOENT) if prev_key
>> + * is not found.
>> + */
>> +static __always_inline struct rhash_head *__rhashtable_next_in_table(
>> +	struct rhashtable *ht, struct bucket_table *tbl,
>> +	const void *prev_key, const struct rhashtable_params params)
>> +	__must_hold_shared(RCU)
>> +{
>> +	struct rhashtable_compare_arg arg = { .ht = ht, .key = prev_key };
>> +	struct rhash_head *he;
>> +	unsigned int b = 0;
>> +	bool found = false;
>> +
>> +	if (prev_key) {
>> +		b = rht_key_hashfn(ht, tbl, prev_key, params);
>> +		rht_for_each_rcu(he, tbl, b) {
> 
> [Severity: High]
> Does this silently skip duplicate elements when the table is configured with
> rhlist = true?
> 
> For rhlist-enabled tables (like rhltable), the primary hash chain only connects
> the first element of each unique key group, while duplicates are stored in
> secondary linked lists via the rhlist_head structure.
> 
> Since this iteration relies exclusively on rht_for_each_rcu() and doesn't
> traverse those secondary lists, it seems it will only yield the most recently
> inserted element for each unique key.
> 

rhltable is not supported, I can return -EOPNOTSUPP for it:
if (unlikely(ht->rhlist))
    return ERR_PTR(-EOPNOTSUPP);

>> +			if (found)
>> +				return he;
>> +			if (params.obj_cmpfn ?
>> +			    !params.obj_cmpfn(&arg, rht_obj(ht, he)) :
>> +			    !rhashtable_compare(&arg, rht_obj(ht, he)))
>> +				found = true;
> 
> [Severity: High]
> Can this lead to an infinite loop and RCU stall if the hash table contains
> duplicate keys?
> 
> Since standard rhashtables permit duplicate keys, rhashtable_compare() will
> match the first occurrence of prev_key in the chain and then yield the
> immediate next element.
> 
> If the next element is also a duplicate of prev_key, when the caller resumes
> iteration with it, the search restarts from the bucket head, matches the
> first occurrence again, and repeatedly yields the same second duplicate
> without making forward progress.
> 

good point, This code can be modified to skip duplicate keys. For BPF
codepaths duplicate keys are not possible, though.

>> +		}
>> +		if (!found)
>> +			return ERR_PTR(-ENOENT);
> 
> [Severity: High]
> Is it safe to return ERR_PTR(-ENOENT) if prev_key is concurrently deleted?
> 
> Unlike standard rhashtable iterators, this abruptly aborts the iteration if the
> element is removed, missing the remainder of the map.
> 
> Additionally, generic callers utilizing standard loop termination checks
> (e.g., while (obj)) could inadvertently dereference this error pointer and
> cause a kernel panic.

users should use IS_ERR_OR_NULL() instead of just checking for NULL.

> 
>> +		b++;
>> +	}
>> +
>> +	for (; b < tbl->size; b++)
>> +		rht_for_each_rcu(he, tbl, b)
>> +			return he;
>> +	return NULL;
>> +}
> 
> [ ... ]
> 
>> +static inline void *rhashtable_next_key(
>> +	struct rhashtable *ht, const void *prev_key,
>> +	const struct rhashtable_params params)
>> +	__must_hold_shared(RCU)
>> +{
>> +	struct bucket_table *tbl;
>> +	struct rhash_head *he;
>> +
>> +	tbl = rht_dereference_rcu(ht->tbl, ht);
>> +	do {
>> +		he = __rhashtable_next_in_table(ht, tbl, prev_key, params);
>> +		if (!IS_ERR_OR_NULL(he))
>> +			return rht_obj(ht, he);
>> +		if (!he)
>> +			prev_key = NULL;
>> +		/* Ensure we see any new future_tbl attached during a rehash. */
>> +		smp_rmb();
>> +		tbl = rht_dereference_rcu(tbl->future_tbl, ht);
> 
> [Severity: Critical]
> Does this logic completely skip unmigrated elements if prev_key has already been
> migrated during a concurrent rehash?
> 
> If prev_key was migrated, __rhashtable_next_in_table() will fail to find it in
> the old table and return ERR_PTR(-ENOENT).
> 
> The code then falls back to searching future_tbl where it finds the key and
> continues. However, by jumping to future_tbl, the iterator permanently abandons
> the old table (ht->tbl) and will never visit its remaining unmigrated buckets,
> causing significant data omission.
> 

Yes, this is a limitation we have to deal with when using rhashtable.

>> +	} while (tbl);
>> +	return he; /* NULL or -ENOENT */
>> +}
>