| Message ID | 20241008091501.8302-1-houtao@huaweicloud.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | Support dynptr key for hash map | expand |
On Tue, 2024-10-08 at 17:14 +0800, Hou Tao wrote:
[...]
> As usual, comments and suggestions are always welcome.
fwiw, I've read through the patches in the series and code changes
seem all to make sense. Executing selftests with KASAN enabled also
does not show any issues.
Maybe add benchmarks in v2?
Hi, On 10/12/2024 6:11 AM, Eduard Zingerman wrote: > On Tue, 2024-10-08 at 17:14 +0800, Hou Tao wrote: > > [...] > >> As usual, comments and suggestions are always welcome. > fwiw, I've read through the patches in the series and code changes > seem all to make sense. Executing selftests with KASAN enabled also > does not show any issues. Thanks for the review and test. > > Maybe add benchmarks in v2? I have written a benchmark to compare the performance between the normal hash table and the dynptr-key hash map (this is the source of the benchmark data in cover letter). However, it was not polished when I posted v1. Will include it in v2.
From: Hou Tao <houtao1@huawei.com> 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@mail.gmail.com/ 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