Skip to content

bpf: htab: Reduce memory use of hash maps

T.J. Mercier bpf lkml 9 versions – Applied

Status from this message: This series was applied to bpf/bpf-next.git (master)

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v9 Latest2 patches 0 repliesApplied 2/2
  2. v82 patches 2 repliesSuperseded
  3. v72 patches 5 repliesSuperseded
Earlier versions · 6
VersionPostedPatchesRepliesStatus
v62 patches0 repliesSuperseded
v52 patches4 repliesSuperseded
v42 patches5 repliesSuperseded
v32 patches4 repliesSuperseded
v22 patches1 replySuperseded
v12 patches9 repliesSuperseded

Changes in v9 from the cover letter

- Rebase on bpf-next/for-next. Resolved conflicts with ab39974240a0 ("bpf: Hold map BTF for the memory allocator destructor record")

- Eliminate warnings from old GCC versions about possible OOB memcpy for key zero-extension on 32-bit by using min_t with sizeof(dest) for the dead (runtime) !htab_has_hash() branch in __lookup_elem_raw. Now elem_has_hash replaces htab_has_hash() and no code is generated for that dead branch.
https://lore.kernel.org/all/[email protected]/

- Return struct hlist_nulls_node * from __lookup_elem_raw.
On W=2 builds, the following warning occurred:
include/linux/list_nulls.h:57:17: warning: ‘n’ may be used uninitialized [-Wmaybe-uninitialized]
57 | return ((unsigned long)ptr) >> 1;
| ~^~~~~~~~~~~~~~~~~~~
kernel/bpf/hashtab.c: In function ‘__htab_map_lookup_elem_u64’:
kernel/bpf/hashtab.c:871:34: note: ‘n’ was declared here
871 | struct hlist_nulls_node *n;

Patches in v9 All 2 applied

#Subject and filesSizeRepliesApplied
1/2bpf: htab: Split htab_elem_lru and htab_elem_pcpu off of htab_elemkernel/bpf/hashtab.c tools/testing/selftests/bpf/progs/map_ptr_kern.c+92 -500 repliesApplied
2/2bpf: htab: Reduce elem_size by 8 bytes for small key sizeskernel/bpf/hashtab.c tools/testing/selftests/bpf/progs/map_ptr_kern.c+166 -650 repliesApplied

Reviews trailers per patch

1 of 2 patches has a Reviewed-by or Acked-by.

PatchMykyta Yatsenko
1/2A-b
2/2

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v9 thread

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

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 v9:
- Rebase on bpf-next/for-next. Resolved conflicts with ab39974240a0 ("bpf: Hold map BTF for the memory allocator destructor record")

- Eliminate warnings from old GCC versions about possible OOB memcpy for key zero-extension on 32-bit by using min_t with sizeof(dest) for the dead (runtime) !htab_has_hash() branch in __lookup_elem_raw. Now elem_has_hash replaces htab_has_hash() and no code is generated for that dead branch.
https://lore.kernel.org/all/[email protected]/

- Return struct hlist_nulls_node * from __lookup_elem_raw.
On W=2 builds, the following warning occurred:
include/linux/list_nulls.h:57:17: warning: ‘n’ may be used uninitialized [-Wmaybe-uninitialized]
57 | return ((unsigned long)ptr) >> 1;
| ~^~~~~~~~~~~~~~~~~~~
kernel/bpf/hashtab.c: In function ‘__htab_map_lookup_elem_u64’:
kernel/bpf/hashtab.c:871:34: note: ‘n’ was declared here
871 | struct hlist_nulls_node *n;

That is because the compiler cannot prove that __lookup_elem_raw()'s out_n pointer is always initialized when the if(l) branch is skipped in lookup_nulls_elem_raw(). Returning struct hlist_nulls_node * allows the compiler to see that n will always be initialized, and also that is_a_nulls(n) is always true for fallthrough case. This also eliminates the redundant !is_a_nulls(n) check that hlist_nulls_for_each_entry_rcu() already runs.

- Deduplicate key zero-extension with new htab_zero_extend_key helper.

- Update htab_elem_pcpu / htab_elem_pcpu_hashed docs to clarify the unhashed variant is for small keys, and the hashed variant is for large keys.

Changes in v8:
- Add htab_elem_lru_node (Sashiko)

- Add Mykyta's Ack

Changes in v7:
- Rebase on bpf-next/for-next. Resolve conflicts with 63b13537e6b2 ("bpf: Speed up htab lookups for u32/u64 keys")

Changes in v6:
- Make htab_elem_set_hash branchless like htab_elem_hash

From Alexei Starovoitov:
- Drop smp_wmb/smp_rmb and WRITE_ONCE/READ_ONCE on hash
- Drop map size check changes (just use sizeof(struct htab_elem_lru))
- Drop BUILD_BUG_ON on elem_offset

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

base-commit: e1d84a37cba984388988d2f1ddc84561413f0db2

Signature · 1 line
2.56.0.385.gd3acb90ef8-goog