Re: [PATCH bpf-next v3 02/10] rhashtable: Add rhashtable_walk_enter_from()

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

On 5/7/26 9:26 AM, Herbert Xu wrote:
> On Tue, May 05, 2026 at 05:57:41PM +0100, Mykyta Yatsenko wrote:
>>
>> We brainstormed with Alexei on how to integrate rhashtable better,
>> as a BPF map, we have the next proposal:
>>
>> Introduce rhashtable_next_key() API
>> ```
>> static inline struct rhash_head *rhashtable_next_key(
>> 	struct rhashtable *ht, const void *prev_key,
>> 	const struct rhashtable_params params);
>> ```
>>
>> It returns the next element, by finding prev_key in the tbl chain
>> and returning the next element in whatever tbl the prev one is.
>> This way we keep rhashtable API tight, less surface, not exposing unnecessary
>> details, although, this new API will have the same issues with full
>> iteration support (which we fine to deal with on userspace side).
>> Appreciate if you share your opinion on this.
> 
> Can you please show me how this gets used? Basically send me the
> patch 03 from your v3 series with this new interface.
> 
> Thanks,

Below is the example of the get_next_key() from BPF using rhashtable_next_key(),
I also included an implementation from rhashtable.

hashtab.c:
==========

static int rhtab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
	__must_hold_shared(RCU)
{
	struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
	struct rhtab_elem *elem;

	elem = rhashtable_next_key(&rhtab->ht, key, rhtab->params);

	/* if not found, return the first key */
	if (PTR_ERR(elem) == -ENOENT)
		elem = rhashtable_next_key(&rhtab->ht, NULL, rhtab->params);

	if (!elem)
		return -ENOENT;

	memcpy(next_key, elem->data, map->key_size);
	return 0;
}

rhashtable.h:
=============

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) {
			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;
		}
		if (!found)
			return ERR_PTR(-ENOENT);
		b++;
	}

	for (; b < tbl->size; b++)
		rht_for_each_rcu(he, tbl, b)
			return he;
	return NULL;
}

/**
 * rhashtable_next_key - return next element after a given key
 * @ht:		hash table
 * @prev_key:	pointer to previous key, or NULL for the first element
 * @params:	hash table parameters
 *
 * Returns the next element in best-effort iteration order, walking the
 * @tbl chain (including any future_tbl in flight). Caller must hold RCU.
 *
 * Pass @prev_key == NULL to obtain the first element. To iterate, set
 * @prev_key to the key of the previously returned element on each call,
 * and stop when NULL is returned.
 *
 * Best-effort semantics:
 *   - Across the tbl->future_tbl chain, an element being migrated may
 *     transiently appear in both tables and be observed twice.
 *   - Concurrent inserts may or may not be observed.
 *   - Termination of a full iteration loop is NOT guaranteed under
 *     adversarial continuous rehash; callers MUST tolerate skips and
 *     repeats and SHOULD bound their loop externally.
 *   - If prev_key was concurrently deleted and is not present in any
 *     in-flight table, returns ERR_PTR(-ENOENT).
 *
 * Returns entry of the next element, or NULL when iteration is exhausted
 * or ERR_PTR(-ENOENT) if prev_key is not found.
 */
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);
	for (; tbl; tbl = rht_dereference_rcu(tbl->future_tbl, ht)) {
		he = __rhashtable_next_in_table(ht, tbl, prev_key, params);
		if (!he)
			/*
			 * this table is exhausted, try the next one from
			 * the beginning
			 */
			prev_key = NULL;
		else if (!IS_ERR(he))
			return rht_obj(ht, he);
	}
	return he; /* NULL or -ENOENT */
}