[PATCH] rhashtable: specialize default comparison for constant parameters

[PATCH] rhashtable: specialize default comparison for constant parameters

[Usama Arif]

The inline lookup and insert helpers receive the rhashtable parameters by
value. With a static const parameter block, key_offset and key_len are
compile-time constants at the call site.

The default comparison throws that information away by reading both fields
back from ht->p. Fixed-size keys consequently load the parameters and call
bcmp() for every object in the bucket, even when the compiler could use
scalar comparisons instead.

The commit "sched_ext: Specialize the DSQ hashtable compare" [1] resulted
in a 2.9x faster DSQ lookup after replacing this path for its u64 key
with a scalar comparison. Doing that through obj_cmpfn requires every
fixed-key user to provide its own callback.

Pass the call-site parameters to rhashtable_compare(), as
rht_key_get_hash() already does. Use them when key_len is a compile-time
constant. Retain the ht->p path for dynamic parameter blocks. A constant
zero key_len continues to take the runtime length from ht->p.key_len.

This specializes the default comparison for all fixed-size users. With
Clang 22 on x86-64, bcmp() disappears from sched_ext, mac80211, NFSd,
TIPC, NFQUEUE, VFS superblock, pidfs, SysV IPC and hardware-breakpoint
table paths. The affected build_policy.o, sta_info.o and nfsd filecache.o
text shrinks by 512, 400 and 352 bytes respectively. Four- and eight-byte
keys become direct scalar comparisons; six-byte MAC addresses become a
four-byte and a two-byte comparison.

Measure the VFS case with ustat() on a mounted ramfs. This exercises
user_get_super() and its super_dev lookup. Across ten interleaved baseline
and patched VM boot pairs, with five 3 million call samples per boot, the
average per-boot median latency drops from 477.2 to 462.6 ns per call, or
3.0%. All ten pairs improved.

No functional change intended.

[1] https://lore.kernel.org/all/20260921171928.1639407-1-usama.arif@linux.dev/

Suggested-by: Mykola Lysenko <nickolay.lysenko@gmail.com>
Signed-off-by: Usama Arif <usama.arif@linux.dev>
---
 include/linux/rhashtable.h | 20 +++++++++++++++-----
 lib/rhashtable.c           |  5 +++--
 2 files changed, 18 insertions(+), 7 deletions(-)

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 57a2a29bef0e8..c9872965b753c 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -598,13 +598,23 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
 	for (pos = list; pos && rht_entry(tpos, pos, member);		\
 	     pos = rcu_dereference_all(pos->next))
 
-static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
-				     const void *obj)
+/*
+ * Use constant params from inlined callers to specialize memcmp(). If params
+ * isn't constant, it must be equal to ht->p.
+ */
+static __always_inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
+					      const void *obj,
+					      const struct rhashtable_params params)
 {
 	struct rhashtable *ht = arg->ht;
 	const char *ptr = obj;
 
-	return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
+	if (!__builtin_constant_p(params.key_len))
+		return memcmp(ptr + ht->p.key_offset, arg->key,
+			      ht->p.key_len);
+
+	return memcmp(ptr + params.key_offset, arg->key,
+		      params.key_len ? : ht->p.key_len);
 }
 
 /* Internal function, do not use. */
@@ -632,7 +642,7 @@ static __always_inline struct rhash_head *__rhashtable_lookup(
 		rht_for_each_rcu_from(he, __rht_ptr_rcu(bkt, freq), tbl, hash) {
 			if (params.obj_cmpfn ?
 			    params.obj_cmpfn(&arg, rht_obj(ht, he)) :
-			    rhashtable_compare(&arg, rht_obj(ht, he)))
+			    rhashtable_compare(&arg, rht_obj(ht, he), params))
 				continue;
 			return he;
 		}
@@ -797,7 +807,7 @@ static __always_inline void *__rhashtable_insert_fast(
 		if (!key ||
 		    (params.obj_cmpfn ?
 		     params.obj_cmpfn(&arg, rht_obj(ht, head)) :
-		     rhashtable_compare(&arg, rht_obj(ht, head)))) {
+		     rhashtable_compare(&arg, rht_obj(ht, head), params))) {
 			pprev = &head->next;
 			continue;
 		}
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 6362896e4f099..9d9f03b59c823 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -548,7 +548,7 @@ static void *rhashtable_lookup_one(struct rhashtable *ht,
 		if (!key ||
 		    (ht->p.obj_cmpfn ?
 		     ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) :
-		     rhashtable_compare(&arg, rht_obj(ht, head)))) {
+		     rhashtable_compare(&arg, rht_obj(ht, head), ht->p))) {
 			pprev = &head->next;
 			continue;
 		}
@@ -710,7 +710,8 @@ static struct rhash_head *__rhashtable_next_in_table(
 		rht_for_each_rcu(he, tbl, b) {
 			bool match = params.obj_cmpfn
 				     ? !params.obj_cmpfn(&arg, rht_obj(ht, he))
-				     : !rhashtable_compare(&arg, rht_obj(ht, he));
+				     : !rhashtable_compare(&arg, rht_obj(ht, he),
+						   params);
 			if (found) {
 				if (match)
 					continue;
-- 
2.53.0-Meta

Re: [PATCH] rhashtable: specialize default comparison for constant parameters

[Tejun Heo]

On Thu, Sep 24, 2026 at 11:47:33AM -0700, Usama Arif wrote:
> The inline lookup and insert helpers receive the rhashtable parameters by
> value. With a static const parameter block, key_offset and key_len are
> compile-time constants at the call site.
> 
> The default comparison throws that information away by reading both fields
> back from ht->p. Fixed-size keys consequently load the parameters and call
> bcmp() for every object in the bucket, even when the compiler could use
> scalar comparisons instead.
> 
> The commit "sched_ext: Specialize the DSQ hashtable compare" [1] resulted
> in a 2.9x faster DSQ lookup after replacing this path for its u64 key
> with a scalar comparison. Doing that through obj_cmpfn requires every
> fixed-key user to provide its own callback.
> 
> Pass the call-site parameters to rhashtable_compare(), as
> rht_key_get_hash() already does. Use them when key_len is a compile-time
> constant. Retain the ht->p path for dynamic parameter blocks. A constant
> zero key_len continues to take the runtime length from ht->p.key_len.
> 
> This specializes the default comparison for all fixed-size users. With
> Clang 22 on x86-64, bcmp() disappears from sched_ext, mac80211, NFSd,
> TIPC, NFQUEUE, VFS superblock, pidfs, SysV IPC and hardware-breakpoint
> table paths. The affected build_policy.o, sta_info.o and nfsd filecache.o
> text shrinks by 512, 400 and 352 bytes respectively. Four- and eight-byte
> keys become direct scalar comparisons; six-byte MAC addresses become a
> four-byte and a two-byte comparison.
> 
> Measure the VFS case with ustat() on a mounted ramfs. This exercises
> user_get_super() and its super_dev lookup. Across ten interleaved baseline
> and patched VM boot pairs, with five 3 million call samples per boot, the
> average per-boot median latency drops from 477.2 to 462.6 ns per call, or
> 3.0%. All ten pairs improved.
> 
> No functional change intended.
> 
> [1] https://lore.kernel.org/all/20260921171928.1639407-1-usama.arif@linux.dev/
> 
> Suggested-by: Mykola Lysenko <nickolay.lysenko@gmail.com>
> Signed-off-by: Usama Arif <usama.arif@linux.dev>

This is great.

Acked-by: Tejun Heo <tj@kernel.org>

Thanks.

-- 
tejun

Re: [PATCH] rhashtable: specialize default comparison for constant parameters

[David Laight]

On Thu, 24 Sep 2026 11:47:33 -0700
Usama Arif <usama.arif@linux.dev> wrote:

> The inline lookup and insert helpers receive the rhashtable parameters by
> value. With a static const parameter block, key_offset and key_len are
> compile-time constants at the call site.
> 
> The default comparison throws that information away by reading both fields
> back from ht->p. Fixed-size keys consequently load the parameters and call
> bcmp() for every object in the bucket, even when the compiler could use
> scalar comparisons instead.
> 
> The commit "sched_ext: Specialize the DSQ hashtable compare" [1] resulted
> in a 2.9x faster DSQ lookup after replacing this path for its u64 key
> with a scalar comparison. Doing that through obj_cmpfn requires every
> fixed-key user to provide its own callback.
> 
> Pass the call-site parameters to rhashtable_compare(), as
> rht_key_get_hash() already does. Use them when key_len is a compile-time
> constant. Retain the ht->p path for dynamic parameter blocks. A constant
> zero key_len continues to take the runtime length from ht->p.key_len.
> 
> This specializes the default comparison for all fixed-size users. With
> Clang 22 on x86-64, bcmp() disappears from sched_ext, mac80211, NFSd,
> TIPC, NFQUEUE, VFS superblock, pidfs, SysV IPC and hardware-breakpoint
> table paths. The affected build_policy.o, sta_info.o and nfsd filecache.o
> text shrinks by 512, 400 and 352 bytes respectively. Four- and eight-byte
> keys become direct scalar comparisons; six-byte MAC addresses become a
> four-byte and a two-byte comparison.
> 
> Measure the VFS case with ustat() on a mounted ramfs. This exercises
> user_get_super() and its super_dev lookup. Across ten interleaved baseline
> and patched VM boot pairs, with five 3 million call samples per boot, the
> average per-boot median latency drops from 477.2 to 462.6 ns per call, or
> 3.0%. All ten pairs improved.
> 
> No functional change intended.
> 
> [1] https://lore.kernel.org/all/20260921171928.1639407-1-usama.arif@linux.dev/
> 
> Suggested-by: Mykola Lysenko <nickolay.lysenko@gmail.com>
> Signed-off-by: Usama Arif <usama.arif@linux.dev>
> ---
>  include/linux/rhashtable.h | 20 +++++++++++++++-----
>  lib/rhashtable.c           |  5 +++--
>  2 files changed, 18 insertions(+), 7 deletions(-)
> 
> diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
> index 57a2a29bef0e8..c9872965b753c 100644
> --- a/include/linux/rhashtable.h
> +++ b/include/linux/rhashtable.h
> @@ -598,13 +598,23 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
>  	for (pos = list; pos && rht_entry(tpos, pos, member);		\
>  	     pos = rcu_dereference_all(pos->next))
>  
> -static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
> -				     const void *obj)
> +/*
> + * Use constant params from inlined callers to specialize memcmp(). If params
> + * isn't constant, it must be equal to ht->p.
> + */
> +static __always_inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
> +					      const void *obj,
> +					      const struct rhashtable_params params)
>  {
>  	struct rhashtable *ht = arg->ht;
>  	const char *ptr = obj;
>  
> -	return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
> +	if (!__builtin_constant_p(params.key_len))
> +		return memcmp(ptr + ht->p.key_offset, arg->key,
> +			      ht->p.key_len);
> +
> +	return memcmp(ptr + params.key_offset, arg->key,
> +		      params.key_len ? : ht->p.key_len);

That looks strange to me.
If ht->p.key_len/offset can be different from params.key_len/offset I can't
see why that shouldn't happen when params is constant.
If ht->p is likely to be a pointer to the associated params, you are passed
the params, they match and params is constant then you can optimise.
But that needs the address compare in the calling code (outside any look).

David 

>  }
>  
>  /* Internal function, do not use. */
> @@ -632,7 +642,7 @@ static __always_inline struct rhash_head *__rhashtable_lookup(
>  		rht_for_each_rcu_from(he, __rht_ptr_rcu(bkt, freq), tbl, hash) {
>  			if (params.obj_cmpfn ?
>  			    params.obj_cmpfn(&arg, rht_obj(ht, he)) :
> -			    rhashtable_compare(&arg, rht_obj(ht, he)))
> +			    rhashtable_compare(&arg, rht_obj(ht, he), params))
>  				continue;
>  			return he;
>  		}
> @@ -797,7 +807,7 @@ static __always_inline void *__rhashtable_insert_fast(
>  		if (!key ||
>  		    (params.obj_cmpfn ?
>  		     params.obj_cmpfn(&arg, rht_obj(ht, head)) :
> -		     rhashtable_compare(&arg, rht_obj(ht, head)))) {
> +		     rhashtable_compare(&arg, rht_obj(ht, head), params))) {
>  			pprev = &head->next;
>  			continue;
>  		}
> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
> index 6362896e4f099..9d9f03b59c823 100644
> --- a/lib/rhashtable.c
> +++ b/lib/rhashtable.c
> @@ -548,7 +548,7 @@ static void *rhashtable_lookup_one(struct rhashtable *ht,
>  		if (!key ||
>  		    (ht->p.obj_cmpfn ?
>  		     ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) :
> -		     rhashtable_compare(&arg, rht_obj(ht, head)))) {
> +		     rhashtable_compare(&arg, rht_obj(ht, head), ht->p))) {
>  			pprev = &head->next;
>  			continue;
>  		}
> @@ -710,7 +710,8 @@ static struct rhash_head *__rhashtable_next_in_table(
>  		rht_for_each_rcu(he, tbl, b) {
>  			bool match = params.obj_cmpfn
>  				     ? !params.obj_cmpfn(&arg, rht_obj(ht, he))
> -				     : !rhashtable_compare(&arg, rht_obj(ht, he));
> +				     : !rhashtable_compare(&arg, rht_obj(ht, he),
> +						   params);
>  			if (found) {
>  				if (match)
>  					continue;

Re: [PATCH] rhashtable: specialize default comparison for constant parameters

[Herbert Xu]

On Thu, Sep 24, 2026 at 11:47:33AM -0700, Usama Arif wrote:
> The inline lookup and insert helpers receive the rhashtable parameters by
> value. With a static const parameter block, key_offset and key_len are
> compile-time constants at the call site.
> 
> The default comparison throws that information away by reading both fields
> back from ht->p. Fixed-size keys consequently load the parameters and call
> bcmp() for every object in the bucket, even when the compiler could use
> scalar comparisons instead.
> 
> The commit "sched_ext: Specialize the DSQ hashtable compare" [1] resulted
> in a 2.9x faster DSQ lookup after replacing this path for its u64 key
> with a scalar comparison. Doing that through obj_cmpfn requires every
> fixed-key user to provide its own callback.
> 
> Pass the call-site parameters to rhashtable_compare(), as
> rht_key_get_hash() already does. Use them when key_len is a compile-time
> constant. Retain the ht->p path for dynamic parameter blocks. A constant
> zero key_len continues to take the runtime length from ht->p.key_len.
> 
> This specializes the default comparison for all fixed-size users. With
> Clang 22 on x86-64, bcmp() disappears from sched_ext, mac80211, NFSd,
> TIPC, NFQUEUE, VFS superblock, pidfs, SysV IPC and hardware-breakpoint
> table paths. The affected build_policy.o, sta_info.o and nfsd filecache.o
> text shrinks by 512, 400 and 352 bytes respectively. Four- and eight-byte
> keys become direct scalar comparisons; six-byte MAC addresses become a
> four-byte and a two-byte comparison.
> 
> Measure the VFS case with ustat() on a mounted ramfs. This exercises
> user_get_super() and its super_dev lookup. Across ten interleaved baseline
> and patched VM boot pairs, with five 3 million call samples per boot, the
> average per-boot median latency drops from 477.2 to 462.6 ns per call, or
> 3.0%. All ten pairs improved.
> 
> No functional change intended.
> 
> [1] https://lore.kernel.org/all/20260921171928.1639407-1-usama.arif@linux.dev/
> 
> Suggested-by: Mykola Lysenko <nickolay.lysenko@gmail.com>
> Signed-off-by: Usama Arif <usama.arif@linux.dev>
> ---
>  include/linux/rhashtable.h | 20 +++++++++++++++-----
>  lib/rhashtable.c           |  5 +++--
>  2 files changed, 18 insertions(+), 7 deletions(-)

Nice work, I'm glad that someone is looking at the assembly :)

> diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
> index 57a2a29bef0e8..c9872965b753c 100644
> --- a/include/linux/rhashtable.h
> +++ b/include/linux/rhashtable.h
> @@ -598,13 +598,23 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
>  	for (pos = list; pos && rht_entry(tpos, pos, member);		\
>  	     pos = rcu_dereference_all(pos->next))
>  
> -static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
> -				     const void *obj)
> +/*
> + * Use constant params from inlined callers to specialize memcmp(). If params
> + * isn't constant, it must be equal to ht->p.
> + */
> +static __always_inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
> +					      const void *obj,
> +					      const struct rhashtable_params params)
>  {
>  	struct rhashtable *ht = arg->ht;
>  	const char *ptr = obj;
>  
> -	return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
> +	if (!__builtin_constant_p(params.key_len))
> +		return memcmp(ptr + ht->p.key_offset, arg->key,
> +			      ht->p.key_len);
> +
> +	return memcmp(ptr + params.key_offset, arg->key,
> +		      params.key_len ? : ht->p.key_len);

If there is no obj_cmpfn then there is no obj_hashfn.  If there
is no obj_hashfn then params.key_len must be non-zero.  So this
could become unconditional, perhaps with a comment.

Thanks,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] rhashtable: specialize default comparison for constant parameters

[Usama Arif]

On 24/09/2026 22:14, David Laight wrote:
> On Thu, 24 Sep 2026 11:47:33 -0700
> Usama Arif <usama.arif@linux.dev> wrote:
> 
>> The inline lookup and insert helpers receive the rhashtable parameters by
>> value. With a static const parameter block, key_offset and key_len are
>> compile-time constants at the call site.
>>
>> The default comparison throws that information away by reading both fields
>> back from ht->p. Fixed-size keys consequently load the parameters and call
>> bcmp() for every object in the bucket, even when the compiler could use
>> scalar comparisons instead.
>>
>> The commit "sched_ext: Specialize the DSQ hashtable compare" [1] resulted
>> in a 2.9x faster DSQ lookup after replacing this path for its u64 key
>> with a scalar comparison. Doing that through obj_cmpfn requires every
>> fixed-key user to provide its own callback.
>>
>> Pass the call-site parameters to rhashtable_compare(), as
>> rht_key_get_hash() already does. Use them when key_len is a compile-time
>> constant. Retain the ht->p path for dynamic parameter blocks. A constant
>> zero key_len continues to take the runtime length from ht->p.key_len.
>>
>> This specializes the default comparison for all fixed-size users. With
>> Clang 22 on x86-64, bcmp() disappears from sched_ext, mac80211, NFSd,
>> TIPC, NFQUEUE, VFS superblock, pidfs, SysV IPC and hardware-breakpoint
>> table paths. The affected build_policy.o, sta_info.o and nfsd filecache.o
>> text shrinks by 512, 400 and 352 bytes respectively. Four- and eight-byte
>> keys become direct scalar comparisons; six-byte MAC addresses become a
>> four-byte and a two-byte comparison.
>>
>> Measure the VFS case with ustat() on a mounted ramfs. This exercises
>> user_get_super() and its super_dev lookup. Across ten interleaved baseline
>> and patched VM boot pairs, with five 3 million call samples per boot, the
>> average per-boot median latency drops from 477.2 to 462.6 ns per call, or
>> 3.0%. All ten pairs improved.
>>
>> No functional change intended.
>>
>> [1] https://lore.kernel.org/all/20260921171928.1639407-1-usama.arif@linux.dev/
>>
>> Suggested-by: Mykola Lysenko <nickolay.lysenko@gmail.com>
>> Signed-off-by: Usama Arif <usama.arif@linux.dev>
>> ---
>>  include/linux/rhashtable.h | 20 +++++++++++++++-----
>>  lib/rhashtable.c           |  5 +++--
>>  2 files changed, 18 insertions(+), 7 deletions(-)
>>
>> diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
>> index 57a2a29bef0e8..c9872965b753c 100644
>> --- a/include/linux/rhashtable.h
>> +++ b/include/linux/rhashtable.h
>> @@ -598,13 +598,23 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
>>  	for (pos = list; pos && rht_entry(tpos, pos, member);		\
>>  	     pos = rcu_dereference_all(pos->next))
>>  
>> -static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
>> -				     const void *obj)
>> +/*
>> + * Use constant params from inlined callers to specialize memcmp(). If params
>> + * isn't constant, it must be equal to ht->p.
>> + */
>> +static __always_inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
>> +					      const void *obj,
>> +					      const struct rhashtable_params params)
>>  {
>>  	struct rhashtable *ht = arg->ht;
>>  	const char *ptr = obj;
>>  
>> -	return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
>> +	if (!__builtin_constant_p(params.key_len))
>> +		return memcmp(ptr + ht->p.key_offset, arg->key,
>> +			      ht->p.key_len);
>> +
>> +	return memcmp(ptr + params.key_offset, arg->key,
>> +		      params.key_len ? : ht->p.key_len);
> 
> That looks strange to me.
> If ht->p.key_len/offset can be different from params.key_len/offset I can't
> see why that shouldn't happen when params is constant.

Hi David,

Thanks for taking a look!

They mustn't differ: the inline helpers take the same params that were
passed to rhashtable_init(). The only exception is a constant key_len of
0, which means the length is only known at init time (the BPF resizable
hashmap does this). That's why the constant arm has "?: ht->p.key_len".

So both arms compare the same bytes, and the split only tells the
compiler which copy to read. rht_key_get_hash() has done the same since
de91b25c8011 from Herbert.

> If ht->p is likely to be a pointer to the associated params, you are passed
> the params, they match and params is constant then you can optimise.
> But that needs the address compare in the calling code (outside any look).
> 

ht->p is a copy embedded in struct rhashtable, not a pointer, so there's
no address to compare. __builtin_constant_p() is resolved at compile
time, so there's no runtime branch either.


> David 
> 
>>  }
>>  
>>  /* Internal function, do not use. */
>> @@ -632,7 +642,7 @@ static __always_inline struct rhash_head *__rhashtable_lookup(
>>  		rht_for_each_rcu_from(he, __rht_ptr_rcu(bkt, freq), tbl, hash) {
>>  			if (params.obj_cmpfn ?
>>  			    params.obj_cmpfn(&arg, rht_obj(ht, he)) :
>> -			    rhashtable_compare(&arg, rht_obj(ht, he)))
>> +			    rhashtable_compare(&arg, rht_obj(ht, he), params))
>>  				continue;
>>  			return he;
>>  		}
>> @@ -797,7 +807,7 @@ static __always_inline void *__rhashtable_insert_fast(
>>  		if (!key ||
>>  		    (params.obj_cmpfn ?
>>  		     params.obj_cmpfn(&arg, rht_obj(ht, head)) :
>> -		     rhashtable_compare(&arg, rht_obj(ht, head)))) {
>> +		     rhashtable_compare(&arg, rht_obj(ht, head), params))) {
>>  			pprev = &head->next;
>>  			continue;
>>  		}
>> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
>> index 6362896e4f099..9d9f03b59c823 100644
>> --- a/lib/rhashtable.c
>> +++ b/lib/rhashtable.c
>> @@ -548,7 +548,7 @@ static void *rhashtable_lookup_one(struct rhashtable *ht,
>>  		if (!key ||
>>  		    (ht->p.obj_cmpfn ?
>>  		     ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) :
>> -		     rhashtable_compare(&arg, rht_obj(ht, head)))) {
>> +		     rhashtable_compare(&arg, rht_obj(ht, head), ht->p))) {
>>  			pprev = &head->next;
>>  			continue;
>>  		}
>> @@ -710,7 +710,8 @@ static struct rhash_head *__rhashtable_next_in_table(
>>  		rht_for_each_rcu(he, tbl, b) {
>>  			bool match = params.obj_cmpfn
>>  				     ? !params.obj_cmpfn(&arg, rht_obj(ht, he))
>> -				     : !rhashtable_compare(&arg, rht_obj(ht, he));
>> +				     : !rhashtable_compare(&arg, rht_obj(ht, he),
>> +						   params);
>>  			if (found) {
>>  				if (match)
>>  					continue;
> 

Re: [PATCH] rhashtable: specialize default comparison for constant parameters

[Usama Arif]

On 25/09/2026 01:04, Herbert Xu wrote:
> On Thu, Sep 24, 2026 at 11:47:33AM -0700, Usama Arif wrote:
>> The inline lookup and insert helpers receive the rhashtable parameters by
>> value. With a static const parameter block, key_offset and key_len are
>> compile-time constants at the call site.
>>
>> The default comparison throws that information away by reading both fields
>> back from ht->p. Fixed-size keys consequently load the parameters and call
>> bcmp() for every object in the bucket, even when the compiler could use
>> scalar comparisons instead.
>>
>> The commit "sched_ext: Specialize the DSQ hashtable compare" [1] resulted
>> in a 2.9x faster DSQ lookup after replacing this path for its u64 key
>> with a scalar comparison. Doing that through obj_cmpfn requires every
>> fixed-key user to provide its own callback.
>>
>> Pass the call-site parameters to rhashtable_compare(), as
>> rht_key_get_hash() already does. Use them when key_len is a compile-time
>> constant. Retain the ht->p path for dynamic parameter blocks. A constant
>> zero key_len continues to take the runtime length from ht->p.key_len.
>>
>> This specializes the default comparison for all fixed-size users. With
>> Clang 22 on x86-64, bcmp() disappears from sched_ext, mac80211, NFSd,
>> TIPC, NFQUEUE, VFS superblock, pidfs, SysV IPC and hardware-breakpoint
>> table paths. The affected build_policy.o, sta_info.o and nfsd filecache.o
>> text shrinks by 512, 400 and 352 bytes respectively. Four- and eight-byte
>> keys become direct scalar comparisons; six-byte MAC addresses become a
>> four-byte and a two-byte comparison.
>>
>> Measure the VFS case with ustat() on a mounted ramfs. This exercises
>> user_get_super() and its super_dev lookup. Across ten interleaved baseline
>> and patched VM boot pairs, with five 3 million call samples per boot, the
>> average per-boot median latency drops from 477.2 to 462.6 ns per call, or
>> 3.0%. All ten pairs improved.
>>
>> No functional change intended.
>>
>> [1] https://lore.kernel.org/all/20260921171928.1639407-1-usama.arif@linux.dev/
>>
>> Suggested-by: Mykola Lysenko <nickolay.lysenko@gmail.com>
>> Signed-off-by: Usama Arif <usama.arif@linux.dev>
>> ---
>>  include/linux/rhashtable.h | 20 +++++++++++++++-----
>>  lib/rhashtable.c           |  5 +++--
>>  2 files changed, 18 insertions(+), 7 deletions(-)
> 
> Nice work, I'm glad that someone is looking at the assembly :)

Hi Herbert,

Thanks!

> 
>> diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
>> index 57a2a29bef0e8..c9872965b753c 100644
>> --- a/include/linux/rhashtable.h
>> +++ b/include/linux/rhashtable.h
>> @@ -598,13 +598,23 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
>>  	for (pos = list; pos && rht_entry(tpos, pos, member);		\
>>  	     pos = rcu_dereference_all(pos->next))
>>  
>> -static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
>> -				     const void *obj)
>> +/*
>> + * Use constant params from inlined callers to specialize memcmp(). If params
>> + * isn't constant, it must be equal to ht->p.
>> + */
>> +static __always_inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
>> +					      const void *obj,
>> +					      const struct rhashtable_params params)
>>  {
>>  	struct rhashtable *ht = arg->ht;
>>  	const char *ptr = obj;
>>  
>> -	return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
>> +	if (!__builtin_constant_p(params.key_len))
>> +		return memcmp(ptr + ht->p.key_offset, arg->key,
>> +			      ht->p.key_len);
>> +
>> +	return memcmp(ptr + params.key_offset, arg->key,
>> +		      params.key_len ? : ht->p.key_len);
> 
> If there is no obj_cmpfn then there is no obj_hashfn.  If there
> is no obj_hashfn then params.key_len must be non-zero.  So this
> could become unconditional, perhaps with a comment.

That holds for the params given to rhashtable_init(), but not for the
params passed to the fast-path helpers. The BPF resizable hashmap
passes a constant template with no key_len and no obj_cmpfn
(rhtab_params in kernel/bpf/hashtab.c), and sets key_len only in the
copy it gives to rhashtable_init(). Without the "?: ht->p.key_len",
its lookups would memcmp() zero bytes and return the first object in
the bucket. rht_key_get_hash() has the same fallback for this user,
see c9429bf56405a. (I added Mykyta the author of that patch in CC.)


> 
> Thanks,