Re: [PATCH 0/2] bpf: htab: Reduce memory use of hash maps

[Mykyta Yatsenko]

On 7/23/26 6:22 PM, T.J. Mercier wrote:
> On Thu, Jul 23, 2026 at 7:11 AM Mykyta Yatsenko
> <mykyta.yatsenko5@xxxxxxxxx> wrote:
>>
>> On 7/22/26 9:37 PM, T.J. Mercier wrote:
>>> Memory is expensive and scarce these days. This series reduces the
>>> memory use of BPF hash maps by eliminating the per-element overheads
>>> below. This saves up to 50% of per-element memory use for standard and
>>> PCPU hash maps. The memory use of LRU hash maps is unaffected.
>>>
>>
>> I understand that these savings calculations do not account for the element
>> value overhead of per-CPU maps, which make up most of the map memory
>> consumption. Realistically we won't see any memory savings for per-CPU maps.
> 
> Yes, I did not look at BPF_MAP_TYPE_PERCPU_ARRAY at all. 95% of the
> memory used by all of our BPF maps comes from hashmaps affected by
> these changes. We only have 7 BPF_MAP_TYPE_PERCPU_ARRAY maps and they
> consume only about 12 KiB. (I know a few of those PCPU arrays are just
> to avoid 128 / 256 byte BPF stack allocations.)
> 
> 

BTW, did you look into BPF_MAP_TYPE_RHASH? It does not
yield much memory savings compared to normal hashmap, but performance
is better in some scenarios.

Link: https://lore.kernel.org/all/20260605-rhash-v7-0-5b8e05f8630d@xxxxxxxx/

> 
> 
> 
>>> Map Type & Configuration            | Old size | New size | Savings
>>> ------------------------------------|----------|----------|--------
>>> Standard (key <= 8 B, val <= 8 B)   |   64 B   |   32 B   | 50.0%
>>> Per-CPU (prealloc) (key <= 8 B)     |   64 B   |   32 B   | 50.0%
>>> Per-CPU (non-prealloc) (key <= 8 B) |   64 B   |   40 B   | 37.5%
>>> LRU (Any key/value size)            |    -     |    -     | 00.0%
>>>
>>> 1) Unused LRU / PCPU fields in standard and PCPU hash maps (patch 1)
>>> struct htab_elem is used for all hash map types, and includes fields
>>> that are not always used (bpf_lru_node, ptr_to_pptr). For standard
>>> (non-LRU, non-PCPU) hash maps the 24 bytes for the bpf_lru_node (union)
>>> are entirely overhead and can be eliminated. Non-preallocated PCPU maps
>>> only need the 8 byte ptr_to_pptr which is currently unioned with the
>>> unneeded 24 byte bpf_lru_node, so 16 bytes of overhead can be
>>> eliminated. Preallocated PCPU maps don't need ptr_to_pptr, so 24 bytes
>>> of overhead can be saved.
>>>
>>> 2) Hash caching for small keys (patch 2)
>>> For hash maps with small key sizes (<= 8 bytes), comparing keys only
>>> requires a single instruction (64 bit), or a few (32 bit). Currently the
>>> 4 byte hash value (8 byte aligned) is used for this, but offers no
>>> performance advantage in this case and can be eliminated.
>>>
>>> The implementation splits htab_elem into dedicated structures for the
>>> different map types (htab_elem_lru, htab_elem_pcpu, htab_elem) which
>>> share a common initial sequence, but contain additional map-type
>>> specific fields where necessary. This means the placement of the key for
>>> each element varies with the map type, and key_offset is added to
>>> bpf_htab for this purpose.
>>>
>>> While using key_offset and conditional hash checks adds new pointer
>>> dereferences and branching during element traversal,
>>> run_bench_htab_mem.sh shows no significant performance regression across
>>> 10 runs on my 3995WX.
>>>
>>> Benchmark (all in kops/sec)  | Avg. Before | StDev | Avg. After | StDev
>>> -----------------------------|-------------|-------|------------|------
>>> prealloc overwrite           | 115.11      | 4.10  | 115.45     | 5.24
>>> prealloc batch_add_batch_del | 127.14      | 4.32  | 127.06     | 2.32
>>> prealloc add_del_on_diff_cpu | 23.22       | 0.93  | 22.91      | 1.60
>>> normal overwrite             | 78.52       | 3.05  | 80.40      | 3.25
>>> normal batch_add_batch_del   | 45.37       | 0.69  | 47.71      | 0.66
>>> normal add_del_on_diff_cpu   | 12.02       | 0.73  | 12.48      | 0.70
>>>
>>> T.J. Mercier (2):
>>>   bpf: htab: Split htab_elem_lru and htab_elem_pcpu off of htab_elem
>>>   bpf: htab: Reduce elem_size by 8 bytes for small key sizes
>>>
>>>  kernel/bpf/hashtab.c                          | 339 ++++++++++++------
>>>  kernel/bpf/map_in_map.c                       |  13 +
>>>  kernel/bpf/map_in_map.h                       |   2 +
>>>  .../selftests/bpf/progs/map_ptr_kern.c        |   2 +-
>>>  4 files changed, 252 insertions(+), 104 deletions(-)
>>>
>>>
>>> base-commit: cfce77b63375dac81d53f2f85593c548415206b7
>>