Re: [PATCH bpf-next v8 2/2] bpf: htab: Reduce elem_size by 8 bytes for small key sizes

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [High] bpf: htab: lockless reader incorrectly matches recycled element for small keys
- [Medium] bpf: htab: missing memory barriers in lockless key publication
--

commit 835130c656673de5df7faec10778663616293463
Author: T.J. Mercier <tjmercier@google.com>

bpf: htab: Reduce elem_size by 8 bytes for small key sizes

This commit removes the cached 32-bit hash value from struct htab_elem for
hash maps with small key sizes, reducing the element size. It relies on a
single atomic compare for the key instead of the hash, and updates allocation
and lookup paths to accommodate the omitted hash.

> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> index 4df6ae1fa722a..610e9051e373d 100644
> --- a/kernel/bpf/hashtab.c
> +++ b/kernel/bpf/hashtab.c

[ ... ]

> @@ -739,35 +789,60 @@ static inline struct hlist_nulls_head *select_bucket(struct bpf_htab *htab, u32
>  	return &__select_bucket(htab, hash)->head;
>  }
>  
> -/* this lookup function can only be called with bucket lock taken */
> -static struct htab_elem *lookup_elem_raw(struct hlist_nulls_head *head, u32 hash,
> -					 void *key, u32 key_size)
> +static __always_inline struct htab_elem *
> +__lookup_elem_raw(struct bpf_htab *htab, struct hlist_nulls_head *head,
> +		  u32 hash, void *key, u32 key_size,
> +		  struct hlist_nulls_node **out_n)
>  {
>  	struct hlist_nulls_node *n;
>  	struct htab_elem *l;
>  
> -	hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
> -		if (l->hash == hash && !memcmp(&l->key, key, key_size))
> -			return l;
> +	if (htab_has_hash(htab)) {
> +		hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
> +			if (htab_elem_hash(l) == hash &&
> +			    !memcmp(&l->key, key, key_size))
> +				return l;
> +	} else {
> +		/*
> +		 * When hash is omitted, key comparisons must be atomic. Zero extend
> +		 * the caller's key to the word size to support an atomic compare.
> +		 */
> +		unsigned long k = 0;
> +
> +		memcpy(&k, key, key_size);
> +		hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
> +			if (READ_ONCE(*(unsigned long *)l->key) == k)

[Severity: Medium]
Does this lockless key read require smp_load_acquire()?

On weakly ordered architectures, reading the key with READ_ONCE() could allow
speculative execution to load the element's value before the key check is
fully resolved, potentially leading to reading a stale or uninitialized value.

[Severity: High]
Could a lockless RCU reader incorrectly match a recycled element here?

When an element is recycled in alloc_htab_elem() and it has a small key,
the old key remains visible until after the new value is initialized. A reader
searching for the deleted old key could see it match here and incorrectly read
the newly inserted value (or a partially written value) instead of failing
the lookup.

> +				return l;
> +	}

[ ... ]

> @@ -1194,7 +1269,9 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,
>  		l_new = container + htab->elem_offset;
>  	}
>  
> -	memcpy(l_new->key, key, key_size);
> +	if (htab_has_hash(htab))
> +		memcpy(l_new->key, key, key_size);
> +

[Severity: High]
Is there a race condition with lockless readers by not updating the key early?

For maps with small keys, the element's key field retains its previous value
when recycled. As noted above, this leaves a window where a concurrent
lookup for the old key can falsely succeed while the new value is being set
up.

>  	if (percpu) {
>  		if (prealloc) {
>  			pptr = htab_elem_get_ptr(l_new, key_size);

[ ... ]

> @@ -1226,7 +1303,18 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,
>  		copy_map_value(&htab->map, htab_elem_value(l_new, key_size), value);
>  	}
>  
> -	l_new->hash = hash;
> +	if (htab_has_hash(htab)) {
> +		htab_elem_set_hash(l_new, hash);
> +	} else {
> +		/*
> +		 * Zero-extend key into k for an atomic write to support
> +		 * lockless RCU readers.
> +		 */
> +		unsigned long k = 0;
> +
> +		memcpy(&k, key, key_size);
> +		WRITE_ONCE(*(unsigned long *)l_new->key, k);

[Severity: Medium]
Should this use smp_store_release() instead of WRITE_ONCE()?

Writing the key locklessly without smp_store_release() might allow the CPU
to reorder this write before the element's value is fully updated. A lockless
reader could then observe the new key but read an uninitialized or stale
value.

> +	}
>  	return l_new;
>  dec_count:
>  	dec_elem_count(htab);

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261002161738.621133-1-tjmercier@google.com?part=2