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

[T.J. Mercier]

On Fri, Aug 7, 2026 at 8:25 AM Mykyta Yatsenko
<mykyta.yatsenko5@xxxxxxxxx> wrote:
>
> 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@xxxxxxxxxx>
> > ---
> >  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.

Since this is only called for element types that have hashes, we can
use the fact that htab_elem_key() is always exactly 8 bytes after the
the hash.

return *(u32 *)(htab_elem_key(htab, l) - 8);

Gets rid of the branching too! But sorry, there is still some casting.
And void* arithmetic without even more casting.

> > +     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()?

htab_elem_value() requires a struct bpf_htab pointer, but we can't use
that here because it might have already been freed.

> >       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().

Yeah it does get changed to offsetof(data) in the second patch, but
I'll change it to offsetof(key) here in the first patch too.

> > +     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.

->hash_node got changed to ->node.hash_node putting the line width
over 100 chars, so I wrapped it.


> > +                     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;
> >       }
> >  ...