Re: [PATCH bpf-next v3 1/2] bpf: htab: Split htab_elem_lru and htab_elem_pcpu off of htab_elem

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

On 8/5/26 11:35 PM, T.J. Mercier wrote:
> The htab_elem struct is used as the per-element type for all BPF hash
> map types and includes bpf_lru_node in a union with a ptr_to_pptr
> pointer. For standard (non-LRU, non-PCPU) hash maps, the 24 byte union
> allocated for every element is entirely unused. For non-preallocated
> PCPU maps, ptr_to_pptr only requires 8 bytes, leaving 16 bytes of unused
> overhead in the union. For preallocated PCPU maps ptr_to_pptr is unused
> since elements are freed to the PCPU freelist.
> 
> Eliminate this per-element memory overhead by splitting htab_elem into
> dedicated structures for each map type:
>    - struct htab_elem: Minimal structure for standard hash maps and
>      preallocated PCPU maps (saves 24 bytes per element).
>    - struct htab_elem_pcpu: Structure for non-preallocated PCPU maps
>      containing ptr_to_pptr (saves 16 bytes per element).
>    - struct htab_elem_lru: Retains struct bpf_lru_node for LRU maps.
> 
> Because element sizes now vary by map type, add key_offset to struct
> bpf_htab to track the dynamic key offset. Update helper accessors and
> lookups to compute key and value offsets using htab->key_offset.
> 
> Pointers to struct htab_elem in the existing code (e.g. htab_elem_hash)
> serve as generic base element pointers. This is possible because
> htab_elem, htab_elem_pcpu, and htab_elem_lru share a common initial
> sequence, making pointer casts safe.
> 
> Signed-off-by: T.J. Mercier <tjmercier@google.com>
> ---
>  kernel/bpf/hashtab.c    | 362 +++++++++++++++++++++++++---------------
>  kernel/bpf/map_in_map.c |  13 ++
>  kernel/bpf/map_in_map.h |   2 +
>  3 files changed, 242 insertions(+), 135 deletions(-)
> 
> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> index 9f394e1aa2e8..f54366da459f 100644
> --- a/kernel/bpf/hashtab.c
> +++ b/kernel/bpf/hashtab.c
> @@ -102,11 +102,13 @@ struct bpf_htab {
>  	bool use_percpu_counter;
>  	u32 n_buckets;	/* number of hash buckets */
>  	u32 elem_size;	/* size of each element in bytes */
> +	u32 key_offset;	/* offset of key in bytes */
>  	u32 hashrnd;
>  };
>  
>  /* each htab element is struct htab_elem + key + value */
> -struct htab_elem {
> +struct htab_elem;
> +struct htab_node {
>  	union {
>  		struct hlist_nulls_node hash_node;
>  		struct {
> @@ -117,11 +119,27 @@ struct htab_elem {
>  			};
>  		};
>  	};
> -	union {
> -		/* pointer to per-cpu pointer */
> -		void *ptr_to_pptr;
> -		struct bpf_lru_node lru_node;
> -	};
> +};
> +
> +struct htab_elem {
> +	struct htab_node node;
> +	u32 hash;
> +	char key[] __aligned(8);
> +};
> +
> +struct htab_elem_lru {
> +	struct htab_node node;
> +	struct bpf_lru_node lru_node;
> +	u32 hash;
> +	char key[] __aligned(8);
> +};
> +
> +/* Only for non-preallocated PCPU maps. Preallocated PCPU maps don't need
> + * ptr_to_pptr, and use htab_elem.
> + */
> +struct htab_elem_pcpu {
> +	struct htab_node node;
> +	void *ptr_to_pptr;
>  	u32 hash;
>  	char key[] __aligned(8);
>  };
> @@ -136,6 +154,21 @@ static inline bool htab_is_prealloc(const struct bpf_htab *htab)
>  	return !(htab->map.map_flags & BPF_F_NO_PREALLOC);
>  }
>  
> +static inline struct bpf_lru_node *htab_elem_lru_node(struct htab_elem *l)
> +{
> +	return &((struct htab_elem_lru *)l)->lru_node;
> +}
> +
> +static inline void *htab_elem_get_ptr_to_pptr(struct htab_elem *l)
> +{
> +	return ((struct htab_elem_pcpu *)l)->ptr_to_pptr;
> +}
> +
> +static inline void htab_elem_set_ptr_to_pptr(struct htab_elem *l, void *ptr)
> +{
> +	((struct htab_elem_pcpu *)l)->ptr_to_pptr = ptr;
> +}
> +
>  static void htab_init_buckets(struct bpf_htab *htab)
>  {
>  	unsigned int i;
> @@ -183,25 +216,30 @@ static inline bool is_fd_htab(const struct bpf_htab *htab)
>  	return htab->map.map_type == BPF_MAP_TYPE_HASH_OF_MAPS;
>  }
>  
> -static inline void *htab_elem_value(struct htab_elem *l, u32 key_size)
> +static inline void *htab_elem_key(struct bpf_htab *htab, struct htab_elem *l)
> +{
> +	return (void *)l + htab->key_offset;
> +}
> +
> +static inline void *htab_elem_value(struct bpf_htab *htab, struct htab_elem *l)
>  {
> -	return l->key + round_up(key_size, 8);
> +	return htab_elem_key(htab, l) + round_up(htab->map.key_size, 8);
>  }
>  
> -static inline void htab_elem_set_ptr(struct htab_elem *l, u32 key_size,
> +static inline void htab_elem_set_ptr(struct bpf_htab *htab, struct htab_elem *l,
>  				     void __percpu *pptr)
>  {
> -	*(void __percpu **)htab_elem_value(l, key_size) = pptr;
> +	*(void __percpu **)htab_elem_value(htab, l) = pptr;
>  }
>  
> -static inline void __percpu *htab_elem_get_ptr(struct htab_elem *l, u32 key_size)
> +static inline void __percpu *htab_elem_get_ptr(struct bpf_htab *htab, struct htab_elem *l)
>  {
> -	return *(void __percpu **)htab_elem_value(l, key_size);
> +	return *(void __percpu **)htab_elem_value(htab, l);
>  }
>  
> -static void *fd_htab_map_get_ptr(const struct bpf_map *map, struct htab_elem *l)
> +static void *fd_htab_map_get_ptr(struct bpf_htab *htab, struct htab_elem *l)
>  {
> -	return *(void **)htab_elem_value(l, map->key_size);
> +	return *(void **)htab_elem_value(htab, l);
>  }
>  
>  static struct htab_elem *get_htab_elem(struct bpf_htab *htab, int i)
> @@ -209,6 +247,26 @@ static struct htab_elem *get_htab_elem(struct bpf_htab *htab, int i)
>  	return (struct htab_elem *) (htab->elems + i * (u64)htab->elem_size);
>  }
>  
> +static inline u32 htab_elem_hash(struct bpf_htab *htab, struct htab_elem *l)
> +{
> +	if (htab_is_lru(htab))
> +		return ((struct htab_elem_lru *)l)->hash;
> +	else if (htab_is_percpu(htab) && !htab_is_prealloc(htab))
> +		return ((struct htab_elem_pcpu *)l)->hash;

These casts in getter/setter are a bit annoying, not sure if there is a way to
get rid of them.

> +	else
> +		return l->hash;
> +}
> +
> +static inline void htab_elem_set_hash(struct bpf_htab *htab, struct htab_elem *l, u32 hash)
> +{
> +	if (htab_is_lru(htab))
> +		((struct htab_elem_lru *)l)->hash = hash;
> +	else if (htab_is_percpu(htab) && !htab_is_prealloc(htab))
> +		((struct htab_elem_pcpu *)l)->hash = hash;
> +	else
> +		l->hash = hash;
> +}
> +
...
>  	htab->extra_elems = pptr;
> @@ -425,8 +481,8 @@ static int htab_map_alloc_check(union bpf_attr *attr)
>  	bool zero_seed = (attr->map_flags & BPF_F_ZERO_SEED);
>  	int numa_node = bpf_map_attr_numa_node(attr);
>  
> -	BUILD_BUG_ON(offsetof(struct htab_elem, fnode.next) !=
> -		     offsetof(struct htab_elem, hash_node.pprev));
> +	BUILD_BUG_ON(offsetof(struct htab_node, fnode.next) !=
> +		     offsetof(struct htab_node, hash_node.pprev));
>  
>  	if (zero_seed && !capable(CAP_SYS_ADMIN))
>  		/* Guard against local DoS, and discourage production use. */
> @@ -476,7 +532,7 @@ static void htab_mem_dtor(void *obj, void *ctx)
>  	if (IS_ERR_OR_NULL(hrec->record))
>  		return;
>  
> -	map_value = htab_elem_value(elem, hrec->key_size);
> +	map_value = (void *)elem + sizeof(struct htab_elem) + round_up(hrec->key_size, 8);

Why this can't be htab_elem_value()?

>  	bpf_obj_free_fields(hrec->record, map_value);
>  }
>  
> @@ -583,8 +639,14 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
>  
>  	htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);
>  
> -	htab->elem_size = sizeof(struct htab_elem) +
> -			  round_up(htab->map.key_size, 8);
> +	if (htab_is_lru(htab))
> +		htab->key_offset = sizeof(struct htab_elem_lru);

nit: I think it'll be nicer to use explicit offsetof().

> +	else if (percpu && !prealloc)
> +		htab->key_offset = sizeof(struct htab_elem_pcpu);
> +	else
> +		htab->key_offset = sizeof(struct htab_elem);
> +
> +	htab->elem_size = htab->key_offset + round_up(htab->map.key_size, 8);
>  	if (percpu)
>  		htab->elem_size += sizeof(void *);
>  	else
> @@ -692,14 +754,16 @@ static inline struct hlist_nulls_head *select_bucket(struct bpf_htab *htab, u32
>  }
>  
...
> @@ -912,18 +982,19 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
>  	head = select_bucket(htab, hash);
>  
>  	/* lookup the key */
> -	l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);
> +	l = lookup_nulls_elem_raw(htab, head, hash, key, key_size, htab->n_buckets);
>  
>  	if (!l)
>  		goto find_first_elem;
>  
>  	/* key was found, get next key in the same bucket */
> -	next_l = hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_next_rcu(&l->hash_node)),
> -				  struct htab_elem, hash_node);
> +	next_l = hlist_nulls_entry_safe(
> +			rcu_dereference_raw(hlist_nulls_next_rcu(&l->node.hash_node)),

nit: I think this line has not changed.

> +			struct htab_elem, node.hash_node);
>  
>  	if (next_l) {
>  		/* if next elem in this hash list is non-zero, just return it */
> -		memcpy(next_key, next_l->key, key_size);
> +		memcpy(next_key, htab_elem_key(htab, next_l), key_size);
>  		return 0;
>  	}
>  ...