[PATCH bpf-next v5 0/2] bpf: htab: Reduce memory use of hash maps

[T.J. Mercier]

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 (≤ word size), comparing keys only
requires a single instruction. Currently the 4 byte hash value (8 byte
aligned and padded) 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, htab_elem_pcpu, htab_elem_lru with
hashed and unhashed variants) so that the map-type specific fields
exist only in structures where they are necessary. In all hashed
variants, the hash is always at a -8 byte offset from the start of
htab_elem. The elem_offset map field supports the different sized
element headers, and allows dynamic offsets to be kept out of the hot
lookup path. It is used primarliy for allocation / free, and indexing
preallocated elements.

run_bench_htab_mem.sh shows the following changes across 10 runs on my
3995WX.

Benchmark (all in kops/sec)  |  Avg. Before  |  Avg. After  | Delta
-----------------------------|---------------|--------------|--------
prealloc overwrite           | 116.26 ± 4.3  | 118.81 ± 4.2 | +2.19%
prealloc batch_add_batch_del | 128.43 ± 3.6  | 128.89 ± 2.9 | +0.35%
prealloc add_del_on_diff_cpu | 22.91 ± 0.69  | 22.44 ± 0.62 | -2.07%
normal overwrite             | 72.43 ± 3.13  | 81.06 ± 1.49 | +11.9%
normal batch_add_batch_del   | 45.20 ± 0.78  | 50.09 ± 0.56 | +10.8%
normal add_del_on_diff_cpu   | 12.02 ± 0.24  | 12.80 ± 0.18 | +6.49%

---
Changes in v5:
Rebase on top of bpf-next/for-next

Update elem_size check in map_ptr_kern selftest to 40 in first patch
(Sashiko)

Place hash at constant compile-time offset before htab_elem, to allow
removal of key_offset. (Andrii Nakryiko)
This avoids dynamic htab->key_offset load and pointer arithmetic. The
struct declarations got reworked to implement this, and htab_node was
dropped. All map_in_map changes became unnecessary and were dropped.

Fix key update before pptr, value initialization for recycled elements
and lockless readers. (Sashiko finding on internal run)
Read / write memory barriers and READ_ONCE() / WRITE_ONCE() were added
for this.

Combine rhtab_mem_dtor() and htab_mem_dtor() implementations.

Fixed the KMALLOC_MAX_SIZE overflow check since sizeof(struct htab_elem)
shrinks in both patches.

Changes in v4:
Removed inline from new functions per BPF CI (netdev/source_inline).

>From Mykyta Yatsenko:
Factor out duplicate lookup_elem code into __lookup_elem_raw.
Use offsetof instead of sizeof for key_offset assignments in
htab_map_alloc (patch 1).
Eliminate branching and htab_elem casting in htab_elem_hash /
htab_elem_set_hash.

Changes in v3:
>From Sashiko on torn reads/writes:
Use a local unsigned long and READ_ONCE / WRITE_ONCE instead of memcmp /
memcpy for atomic key comparisons for hashless elements.

Changes in v2:
Make maximum key_size for !has_hash depend on word size for atomicity
on 32-bit.

>From Mykyta Yatsenko:
Put the htab_elem* common initial sequence in its own struct (htab_node)
and reuse it across all element types that share it. Eliminate
associated BUILD_BUG_ON additions.
Replace both the hash and key fields with data[].
Store has_hash in struct bpf_htab, and avoid per-element reads of it.

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                          | 351 +++++++++++++-----
 .../selftests/bpf/progs/map_ptr_kern.c        |   2 +-
 2 files changed, 255 insertions(+), 98 deletions(-)


base-commit: b99f71407ce529ba01a9392f477522d2e76c6613
-- 
2.55.0.1082.g2b9226bbc0-goog