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(-)
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. 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 -- 2.55.0.229.g6434b31f56-goog
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. > 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
On Thu, Jul 23, 2026 at 7:11 AM Mykyta Yatsenko <mykyta.yatsenko5@gmail.com> 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.) > > 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 >
On 7/23/26 6:22 PM, T.J. Mercier wrote: > On Thu, Jul 23, 2026 at 7:11 AM Mykyta Yatsenko > <mykyta.yatsenko5@gmail.com> 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@meta.com/ > > > >>> 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 >>
© 2016 - 2026 Red Hat, Inc.