From 8f4fa9f89b72845fa8ac956bff2e1d2ba5722f2e Mon Sep 17 00:00:00 2001 From: Mykyta Yatsenko Date: Fri, 5 Jun 2026 04:41:18 -0700 Subject: rhashtable: Add rhashtable_next_key() API MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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. void *rhashtable_next_key(struct rhashtable *ht, const void *prev_key); Caller holds RCU; passes NULL prev_key for the first element or the previously returned key to advance. Walks tbl->future_tbl chain so in-flight rehashes are observed. Best-effort: in case of concurrent resize, provides no guarantees: - may produce duplicate elements - may skip any amount of elements - termination of the loop is not guaranteed in case of sustained rehash. Callers are advised to bound loop externally or avoid inserting new elements during such loop. Returns ERR_PTR(-ENOENT) if prev_key is not found. Behavior on tables with duplicate keys is undefined. rhltable is not supported — returns ERR_PTR(-EOPNOTSUPP). Signed-off-by: Mykyta Yatsenko Acked-by: Herbert Xu Link: https://lore.kernel.org/r/20260605-rhash-v7-1-5b8e05f8630d@meta.com Signed-off-by: Alexei Starovoitov --- include/linux/rhashtable.h | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) (limited to 'include/linux/rhashtable.h') diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h index ef5230cece36..6f3aea498515 100644 --- a/include/linux/rhashtable.h +++ b/include/linux/rhashtable.h @@ -650,6 +650,46 @@ restart: 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 + * + * WARNING: this walk is highly unstable. Unlike rhashtable_walk_*(), + * it cannot detect a concurrent resize or rehash, so a full iteration + * is NOT guaranteed to terminate under adversarial or sustained + * rehashing. Callers MUST tolerate skipped and duplicated elements and + * SHOULD bound their loop externally. + * + * 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. + * - Behavior on tables that contain duplicate keys is undefined: + * duplicates may be skipped, repeated, or trap the walk in a + * cycle. Callers requiring duplicate-key iteration must use + * rhashtable_walk_*() instead. + * - rhltable instances are not supported and return + * ERR_PTR(-EOPNOTSUPP). + * - 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, or + * ERR_PTR(-EOPNOTSUPP) if @ht is an rhltable. + */ +void *rhashtable_next_key(struct rhashtable *ht, const void *prev_key); + /** * rhashtable_lookup - search hash table * @ht: hash table -- cgit v1.2.3 From 46730ee6e884be667365e4d3a380ac504697559a Mon Sep 17 00:00:00 2001 From: Herbert Xu Date: Fri, 5 Jun 2026 04:41:20 -0700 Subject: rhashtable: Use irq work for shrinking Use irq work for automatic shrinking so that this may be called in NMI context. Signed-off-by: Herbert Xu Signed-off-by: Mykyta Yatsenko Link: https://lore.kernel.org/r/20260605-rhash-v7-3-5b8e05f8630d@meta.com Signed-off-by: Alexei Starovoitov --- include/linux/rhashtable.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include/linux/rhashtable.h') diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h index 6f3aea498515..3de3412d53c8 100644 --- a/include/linux/rhashtable.h +++ b/include/linux/rhashtable.h @@ -1157,7 +1157,7 @@ unlocked: atomic_dec(&ht->nelems); if (unlikely(ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl))) - schedule_work(&ht->run_work); + irq_work_queue(&ht->run_irq_work); err = 0; } -- cgit v1.2.3 From 1444ee886e6fedf20b9c5bc74a273c6b7d100fdc Mon Sep 17 00:00:00 2001 From: Mykyta Yatsenko Date: Sat, 6 Jun 2026 10:30:32 -0700 Subject: rhashtable: Fix rhashtable_next_key() build warnings rhashtable.o builds with warnings as rhashtable_next_key() kdoc from lib/rhashtable.c does not have the arguments descriptions. Move rhashtable_next_key() kdoc from header to c file, matching other functions. Move rhashtable_next_key() next to the other forward declarations in the header file. Reported-by: kernel test robot Closes: https://lore.kernel.org/oe-kbuild-all/202606061925.WI4bYI8k-lkp@intel.com/ Fixes: 8f4fa9f89b72 ("rhashtable: Add rhashtable_next_key() API") Signed-off-by: Mykyta Yatsenko Link: https://lore.kernel.org/r/20260606-rhash_fixes_1-v1-1-932ab036e6bc@meta.com Signed-off-by: Alexei Starovoitov --- include/linux/rhashtable.h | 42 ++---------------------------------------- lib/rhashtable.c | 35 ++++++++++++++++++++++++++++++++++- 2 files changed, 36 insertions(+), 41 deletions(-) (limited to 'include/linux/rhashtable.h') diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h index 3de3412d53c8..79f83b6eec27 100644 --- a/include/linux/rhashtable.h +++ b/include/linux/rhashtable.h @@ -263,6 +263,8 @@ struct rhash_lock_head __rcu **__rht_bucket_nested( struct rhash_lock_head __rcu **rht_bucket_nested_insert( struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash); +void *rhashtable_next_key(struct rhashtable *ht, const void *prev_key); + #define rht_dereference(p, ht) \ rcu_dereference_protected(p, lockdep_rht_mutex_is_held(ht)) @@ -650,46 +652,6 @@ restart: 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 - * - * WARNING: this walk is highly unstable. Unlike rhashtable_walk_*(), - * it cannot detect a concurrent resize or rehash, so a full iteration - * is NOT guaranteed to terminate under adversarial or sustained - * rehashing. Callers MUST tolerate skipped and duplicated elements and - * SHOULD bound their loop externally. - * - * 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. - * - Behavior on tables that contain duplicate keys is undefined: - * duplicates may be skipped, repeated, or trap the walk in a - * cycle. Callers requiring duplicate-key iteration must use - * rhashtable_walk_*() instead. - * - rhltable instances are not supported and return - * ERR_PTR(-EOPNOTSUPP). - * - 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, or - * ERR_PTR(-EOPNOTSUPP) if @ht is an rhltable. - */ -void *rhashtable_next_key(struct rhashtable *ht, const void *prev_key); - /** * rhashtable_lookup - search hash table * @ht: hash table diff --git a/lib/rhashtable.c b/lib/rhashtable.c index dd6eaa09c55d..907637967c0b 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -730,8 +730,41 @@ static struct rhash_head *__rhashtable_next_in_table( /** * 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 * - * See include/linux/rhashtable.h for the full contract. + * WARNING: this walk is highly unstable. Unlike rhashtable_walk_*(), + * it cannot detect a concurrent resize or rehash, so a full iteration + * is NOT guaranteed to terminate under adversarial or sustained + * rehashing. Callers MUST tolerate skipped and duplicated elements and + * SHOULD bound their loop externally. + * + * 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. + * - Behavior on tables that contain duplicate keys is undefined: + * duplicates may be skipped, repeated, or trap the walk in a + * cycle. Callers requiring duplicate-key iteration must use + * rhashtable_walk_*() instead. + * - rhltable instances are not supported and return + * ERR_PTR(-EOPNOTSUPP). + * - 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, or + * ERR_PTR(-EOPNOTSUPP) if @ht is an rhltable. */ void *rhashtable_next_key(struct rhashtable *ht, const void *prev_key) { -- cgit v1.2.3