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

[T.J. Mercier]

On Thu, Jul 23, 2026 at 7:12 AM Mykyta Yatsenko
<mykyta.yatsenko5@xxxxxxxxx> wrote:
>
>
>
> On 7/22/26 9:38 PM, T.J. Mercier wrote:
> > For standard and PCPU (non-LRU) hash maps with small key sizes (<= 8
> > bytes), comparing keys requires only an 8 byte compare. Storing a cached
> > 32-bit hash value to shortcut full key comparisons provides no
> > performance advantage for small keys, and consumes memory for every
> > element.
> >
> > This memory can be saved by eliminating hash along with its associated
> > 4 byte padding before the key, reducing the elem_size (and key_offset)
> > by 8 bytes for standard and PCPU maps.
> >
> > Introduce htab_has_hash() to check whether a map requires a cached hash
> > field. Update htab_elem_set_hash(), lookup_elem_raw(), and
> > lookup_nulls_elem_raw() to conditionally bypass hash checking and
> > storage when htab_has_hash() is false.
> >
> > Together with the previous patch, this reduces the minimum standard and
> > preallocated hash map element size from 64 bytes down to 32 bytes, and
> > non-preallocated per-CPU element size from 64 bytes down to 40 bytes.
> >
> > Signed-off-by: T.J. Mercier <tjmercier@xxxxxxxxxx>
> > ---
> >  kernel/bpf/hashtab.c                          | 35 +++++++++++++------
> >  .../selftests/bpf/progs/map_ptr_kern.c        |  2 +-
> >  2 files changed, 25 insertions(+), 12 deletions(-)
> >
> > diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> > index 57729c3dff3d..b8c30d402958 100644
> > --- a/kernel/bpf/hashtab.c
> > +++ b/kernel/bpf/hashtab.c
> ...
> >
> >       hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
> > -             if (htab_elem_hash(htab, l) == hash &&
> > +             if ((!htab_has_hash(htab) || htab_elem_hash(htab, l) == hash) &&
> >                   !memcmp(htab_elem_key(htab, l), key, key_size))
> >                       return l;
> >
> > @@ -812,7 +825,7 @@ static struct htab_elem *lookup_nulls_elem_raw(struct bpf_htab *htab,
> >
> >  again:
> >       hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
> > -             if (htab_elem_hash(htab, l) == hash &&
> > +             if ((!htab_has_hash(htab) || htab_elem_hash(htab, l) == hash) &&
>
> htab_has_hash() is constant for any concrete map, maybe we can store it in the
> struct bpf_htab (it has few holes) and we already describe layout there,
> or at least not calculate on each element in the bucket in the loop.

Ah, that's true. There's already a htab dereference anyway to read the
map_type and key_size, so might as well use a byte in bpf_htab to read
a new has_hash directly.


>
> >                   !memcmp(htab_elem_key(htab, l), key, key_size))
> >                       return l;
> >
> > @@ -3219,7 +3232,7 @@ static int rhtab_map_check_btf(struct bpf_map *map, const struct btf *btf,
> >  {
> >       struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
> >
> > -     return bpf_ma_set_dtor(map, &rhtab->ma, rhtab_mem_dtor);
> > +     return bpf_ma_set_dtor(map, &rhtab->ma, rhtab_mem_dtor, offsetof(struct rhtab_elem, data));
> >  }
> >
> >  static void rhtab_map_free_internal_structs(struct bpf_map *map)
> > diff --git a/tools/testing/selftests/bpf/progs/map_ptr_kern.c b/tools/testing/selftests/bpf/progs/map_ptr_kern.c
> > index 373c8d17ea55..6bd4cb68c20c 100644
> > --- a/tools/testing/selftests/bpf/progs/map_ptr_kern.c
> > +++ b/tools/testing/selftests/bpf/progs/map_ptr_kern.c
> > @@ -114,7 +114,7 @@ static inline int check_hash(void)
> >       VERIFY(check_default_noinline(&hash->map, map));
> >
> >       VERIFY(hash->n_buckets == MAX_ENTRIES);
> > -     VERIFY(hash->elem_size == 64);
> > +     VERIFY(hash->elem_size == 32);
> >
> >       VERIFY(hash->count.counter == 0);
> >       VERIFY(bpf_map_sum_elem_count(map) == 0);
>