From: Hou Tao <houtao1@xxxxxxxxxx>
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 4 now. And 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 the 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 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.
The patch set is structured as follow:
Patch #1~#5 introduce BPF_F_DYNPTR_IN_KEY map flag, parse the bpf_dynptr
in the map key and verify the use of bpf_dynptr in map related helpers.
Patch #6~#10 introduce bpf_dynptr_user, support the use of
bpf_dynptr_user in bpf syscall for map lookup, lookup_delete, update,
delete and get_next_key operations.
Patch #11~#15 update the lookup, lookup_delete, update, delete and
get_next_key callback correspondingly to support key with bpf_dynptr for
hash map.
Patch #16 adds positive and negative test cases for hash map with dynptr
key support.
The following are the benchmark results on hash map with dynptr key.
(1) the benchmark compares the performance and memory usage between
normal hash map and dynptr-keyed hash map.
The key definitions for these two maps are show below:
struct norm_key {
__u64 cookie;
unsigned char desc[MAX_LEN];
};
struct dynptr_key {
__u64 cookie;
struct bpf_dynptr_user desc;
};
When the max length of desc 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 | 12.1 M/s (? MB) | 7.5 M/s (? MB) |
| 128 | 7.5 M/s (? MB) | 6.3 M/s (? MB)
| 256 | 4.6 M/s (4.9 MB) | 4.9 M/s (? MB) |
| 512 | 2.6 M/s (8.9 MB) | 3.5 M/s (4.6 MB) |
| 1024 | 1.3 M/s (17 MB) | 2.2 M/s (7.4 MB) |
| 2048 | 0.6 M/s (33 MB) | 1.2 M/s (13 MB) |
| 4096 | 0.3 M/s (65 MB) | 0.6 M/s (24 MB) |
| string in file | normal hash-map | dynptr hash-map |
| --- | --- | --- |
| kallsyms | 5.4 M/s (32 MB) | 5.4 M/s (25 MB) |
| string in BTF | 6.8 M/s (23 MB) | 6.8 M/s (17 MB) |
| alexa top 1M sites | 3.2 M/s (192 MB) | 3.0 M/s (139 MB) |
b) update and delete operation
max_entries = 8K (randomly generated data set)
| max length of desc | normal hash-map | dynptr hash-map |
| --- | --- | --- |
| 64 | 4.3 M/s | 3.2 M/s |
| 128 | 3.6 M/s | 2.9 M/s |
| 256 | 2.8 M/s | 2.6 M/s |
| 512 | 1.9 M/s | 2.0 M/s |
| 1024 | 1.0 M/s | 1.3 M/s |
| 2048 | 0.5 M/s | 0.8 M/s |
| 4096 | 0.3 M/s | 0.5 M/s |
| strings in file | normal hash-map | dynptr hash-map |
| --- | --- | --- |
| kallsyms | 3.0 M/s | 2.0 M/s |
| strings in BTF | 3.9 M/s | 3.0 M/s |
| alexa top 1M sites | 2.4 M/s | 2.3 M/s |
(2) the benchmark uses map_perf_test under samples/bpf to test the
overhead of adding dynptr key support in hash map. The test is conducted
on a Intel Xeon CPU and the base kernel version is v6.11.
It seems adding dynptr key support in hash map degrades the lookup
performance about 12% and degrades the update performance about 7%. Will
investigate these degradation first.
a) lookup
max_entries = 8K
before:
0:hash_lookup 72347325 lookups per sec
after:
0:hash_lookup 64758890 lookups per sec
b) update/delete/lookup
max_entries = 8K
before:
0:hash_map_perf pre-alloc 675275 events per sec
0:hash_map_perf kmalloc 666535 events per sec
after:
0:hash_map_perf pre-alloc 626563 events per sec
0:hash_map_perf kmalloc 617234 events per sec
As usual, comments and suggestions are always welcome.
[1]: https://lore.kernel.org/bpf/CAADnVQJWaBRB=P-ZNkppwm=0tZaT3qP8PKLLJ2S5SSA2-S8mxg@xxxxxxxxxxxxxx/
Hou Tao (16):
bpf: Introduce map flag BPF_F_DYNPTR_IN_KEY
bpf: Add two helpers to facilitate the btf parsing of bpf_dynptr
bpf: Parse bpf_dynptr in map key
bpf: Pass flags instead of bool to check_helper_mem_access()
bpf: Support map key with dynptr in verifier
bpf: Introduce bpf_dynptr_user
libbpf: Add helpers for bpf_dynptr_user
bpf: Handle bpf_dynptr_user in bpf syscall when it is used as input
bpf: Handle bpf_dynptr_user in bpf syscall when it is used as output
bpf: Disable unsupported functionalities for map with dynptr key
bpf: Add bpf_mem_alloc_check_size() helper
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: Enable BPF_F_DYNPTR_IN_KEY for hash map
selftests/bpf: Add test cases for hash map with dynptr key
include/linux/bpf.h | 22 +-
include/linux/bpf_mem_alloc.h | 3 +
include/linux/btf.h | 2 +
include/uapi/linux/bpf.h | 9 +
kernel/bpf/btf.c | 46 +-
kernel/bpf/hashtab.c | 314 ++++++++++--
kernel/bpf/helpers.c | 2 +-
kernel/bpf/map_in_map.c | 19 +-
kernel/bpf/memalloc.c | 14 +-
kernel/bpf/syscall.c | 222 ++++++++-
kernel/bpf/verifier.c | 183 ++++++-
tools/include/uapi/linux/bpf.h | 9 +
tools/lib/bpf/bpf.h | 27 ++
.../bpf/prog_tests/htab_dynkey_test.c | 451 ++++++++++++++++++
.../bpf/progs/htab_dynkey_test_failure.c | 270 +++++++++++
.../bpf/progs/htab_dynkey_test_success.c | 399 ++++++++++++++++
16 files changed, 1902 insertions(+), 90 deletions(-)
create mode 100644 tools/testing/selftests/bpf/prog_tests/htab_dynkey_test.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
--
2.44.0
