[bpf-next,v3,00/16] Support dynptr key for hash map

Message

Hou Tao March 27, 2025, 8:34 a.m. UTC

From: Hou Tao <[e-mail]>

Hi,

The patch set aims to add the basic dynptr key support for hash map as
discussed in [1]. The main motivation is to fully utilize the BTF info
of the map key and to support variable-length key (e.g., string or any
byte stream) for bpf map. The patch set uses bpf_dynptr to represent the
variable-length part in the map key and the total number of
variable-length parts in the map key is limited as 2 now. Due to the
limitation in bpf memory allocator, the max size of dynptr in map key is
limited as 4088 bytes. Beside the variable-length parts (dynptr parts),
the fixed-size part in map key is still allowed, so all of these
following map key definitions are valid:

	struct bpf_dynptr;

	struct map_key_1 {
		struct bpf_dynptr name;
	};
	struct map_key_2 {
		int pid;
		struct bpf_dynptr name;
	};
	struct map_key_3 {
		struct map_key_2 f1;
		unsigned long when;
                struct bpf_dynptr tag;
	};

The patch set supports lookup, update, delete operations on normal hash
map with dynptr key for both bpf program and bpf syscall. It also
supports lookup_and_delete and get_next_key operations on dynptr map key
for bpf syscall.

However the following operations have not been fully supported yet on a
hash map with dynptr key:

1) batched map operation through bpf syscall
2) the memory accounting for dynptr (aka .htab_map_mem_usage)
3) btf print for the dynptr in map key
4) bpftool support
5) the iteration of elements through bpf program
When a bpf program iterates the element in a hash map with dynptr key
(e.g., bpf_for_each_map_elem() helper or map element iterator), the
dynptr in the map key has not been specially treated yet and the dynptr
is only treated as a read-only 16-bytes buffer, therefore the iteration
of dynptr-keyed map is disabled.

The patch set is structured as follow:

Patch #1~#2 introduce BPF_DYNPTR in btf_field_type and parse the
bpf_dynptr in the map key.

Patch #3 introduce a helper to check whether the map supports dynptr in
its map key or not.

Patch #4~#5 refactor check_stack_range_initialized() and support
dynptr-keyed map in verifier.

Patch #6~#8 updates the definition of bpf_dynptr, support the use of
bpf_dynptr in bpf syscall for map lookup, lookup_delete, update, delete
and get_next_key operations.

Patch #9~#13 update the lookup, lookup_delete, update, delete and
get_next_key callback correspondingly to support dynptr-keyed hash map.

Patch #14~#15 add positive and negative test cases for hash map with
dynptr key support.

Patch #16 adds the benchmark to compare the lookup and update
performance between normal hash map and dynptr-keyed hash map.

When the max length of str is greater than 256, the lookup performance
of dynptr hash-map will be better than the normal hash map. When the max
length is greater than 512, the update performance of dynptr hash map
will be better than the normal hash map. And the memory consumption of
hash-map with dynptr key is smaller compared with normal hash map.

a) lookup operation

max_entries = 8K (randomly generated data set)
| max length of desc | normal hash-map    | dynptr hash-map   |
| ---                |  ---               | ---               |
|  64                | 11.2 M/s (1.7 MB)  | 8.2 M/s (1.4 MB)  |
| 128                |  6.6 M/s (2.2 MB)  | 6.6 M/s (1.7 MB)  |
| 256                |  3.7 M/s (4.2 MB)  | 4.8 M/s (2.3 MB)  |
| 512                |  2.1 M/s (8.2 MB)  | 3.1 M/s (3.8 MB)  |
| 1024               |  1.1 M/s (16 MB)   | 1.9 M/s (6.5 MB)  |
| 2048               |  0.6 M/s (32 MB)   | 1.1 M/s (12 MB)   |
| 4096               |  0.3 M/s (64 MB)   | 0.6 M/s (23 MB)   |

| string in file     | normal hash-map    | dynptr hash-map   |
| ---                |  ---               | ---               |
| kallsyms           |  6.8 M/s (29 MB)   | 6.0 M/s (23 MB)   |
| string in BTF      |  7.2 M/s (22 MB)   | 6.9 M/s (16 MB)   |
| alexa top 1M sites |  2.7 M/s (191 MB)  | 3.1 M/s (138 MB)  |

b) update and delete operation

max_entries = 8K (randomly generated data set)
| max length of desc | normal hash-map    | dynptr hash-map   |
| ---                |  ---               | ---               |
|  64                |  5.0 M/s           | 3.5 M/s           |
| 128                |  3.8 M/s           | 3.3 M/s           |
| 256                |  2.7 M/s           | 2.7 M/s           |
| 512                |  1.7 M/s           | 2.0 M/s           |
| 1024               |  0.9 M/s           | 1.4 M/s           |
| 2048               |  0.5 M/s           | 0.8 M/s           |
| 4096               |  0.l M/s           | 0.5 M/s           |

| strings in file    | normal hash-map    | dynptr hash-map   |
| ---                |  ---               | ---               |
| kallsyms           |  3.3 M/s           | 2.6 M/s           |
| strings in BTF     |  3.7 M/s           | 3.0 M/s           |
| alexa top 1M sites |  2.3 M/s           | 2.2 M/s           |

As usual, comments and suggestions are always welcome.

---

Change Log:

v3: mainly address comments and suggestions from Alexei
 * use ->map_check_btf callback to check whether the map attributes
   are valid for dynptr-key map and to initialize the allocator for
   dynptr
 * don't use map_extra for hash map with dynptr key.
 * don't increase BTF_FIELDS_MAX
 * lift the max number of bpf_dynptr in map key from 1 to 2
 * merge the definition of bpf_dynptr_user into bpf_dynptr
 * disable the support of the iteration of dynptr-keyed map
 * add negative lookup test in benchmark
 * move the definition of bpf_dynptr_user_init from bpf_util to
   testing_helpers.h, otherwise it will break the build of samples/bpf
 * update benchmark result based on bpf_next/master
 * rebased on bpf_next/for-next

v2: https://lore.kernel.org/bpf/[e-mail]/
  * remove the need to set BPF_F_DYNPTR_IN_KEY flag explicitly
  * remove bpf_dynptr_user helpers from libbpf
  * support dynptr-keyed map in verifier in a less-intrusive way
  * handle the return value of kvmemdup_bpfptr() correctly
  * add necessary comments for ->record and ->key_record
  * use __bpf_md_ptr to define the data field of bpf_dynptr_user
  * add always_inline for lookup_{nulls_elem|elem}_raw
  * add benchmark patch for dynptr-keyed hash map

v1: https://lore.kernel.org/bpf/[e-mail]/

[1]: https://lore.kernel.org/bpf/CAADnVQJWaBRB=P-ZNkppwm=[e-mail]/

Hou Tao (16):
  bpf: Introduce BPF_DYNPTR and helpers to facilitate its parsing
  bpf: Parse bpf_dynptr in map key
  bpf: Add helper bpf_map_has_dynptr_key()
  bpf: Split check_stack_range_initialized() into small functions
  bpf: Support map key with dynptr in verifier
  bpf: Reuse bpf_dynptr for userspace application use case
  bpf: Handle bpf_dynptr in bpf syscall when it is used as input
  bpf: Handle bpf_dynptr in bpf syscall when it is used as output
  bpf: Support basic operations for dynptr key in hash map
  bpf: Export bpf_dynptr_set_size
  bpf: Support get_next_key operation for dynptr key in hash map
  bpf: Disable unsupported operations for map with dynptr key
  bpf: Enable the creation of hash map with dynptr key
  selftests/bpf: Add bpf_dynptr_user_init() helper
  selftests/bpf: Add test cases for hash map with dynptr key
  selftests/bpf: Add benchmark for dynptr key support in hash map

 include/linux/bpf.h                           |  22 +-
 include/linux/btf.h                           |   2 +
 include/uapi/linux/bpf.h                      |  11 +-
 kernel/bpf/btf.c                              |  46 +-
 kernel/bpf/hashtab.c                          | 330 ++++++++-
 kernel/bpf/helpers.c                          |   2 +-
 kernel/bpf/map_in_map.c                       |  21 +-
 kernel/bpf/map_iter.c                         |   3 +
 kernel/bpf/syscall.c                          | 216 +++++-
 kernel/bpf/verifier.c                         | 392 ++++++++---
 tools/include/uapi/linux/bpf.h                |  11 +-
 tools/testing/selftests/bpf/Makefile          |   2 +
 tools/testing/selftests/bpf/bench.c           |  14 +
 .../selftests/bpf/benchs/bench_dynptr_key.c   | 648 ++++++++++++++++++
 .../bpf/benchs/run_bench_dynptr_key.sh        |  51 ++
 .../bpf/prog_tests/htab_dynkey_test.c         | 446 ++++++++++++
 .../selftests/bpf/progs/dynptr_key_bench.c    | 249 +++++++
 .../bpf/progs/htab_dynkey_test_failure.c      | 266 +++++++
 .../bpf/progs/htab_dynkey_test_success.c      | 382 +++++++++++
 tools/testing/selftests/bpf/testing_helpers.h |   9 +
 20 files changed, 2958 insertions(+), 165 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_dynptr_key.c
 create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_dynptr_key.sh
 create mode 100644 tools/testing/selftests/bpf/prog_tests/htab_dynkey_test.c
 create mode 100644 tools/testing/selftests/bpf/progs/dynptr_key_bench.c
 create mode 100644 tools/testing/selftests/bpf/progs/htab_dynkey_test_failure.c
 create mode 100644 tools/testing/selftests/bpf/progs/htab_dynkey_test_success.c