RFC Significantly Improve BTF Type Lookup Performance
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v3 RFC Latest3 patches 15 repliesIn review
- v2 RFC5 patches 26 repliesSuperseded
Changes in v3 from the cover letter
- Remove sorting logic from libbpf and provide a generic btf__permute() interface
- Remove the search direction patch since sorted lookup provides sufficient performance and changing search order could cause conflicts between BTF and base BTF
- Include btf_sort.c directly in btf.c to reduce function call overhead
Patches in v3 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/3 | btf: implement BTF type sorting for accelerated lookupstools/ tools/ tools/ +3 more | +447 | 7 replies | |
| 2/3 | selftests/bpf: add tests for BTF type permutationtools/ | +94 | 2 replies | |
| 3/3 | btf: Reuse libbpf code for BTF type sorting verification and binary searchkernel/ | +18 | 6 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v3 yet.
Cover letter [RFC PATCH v3 0/3] Significantly Improve BTF Type Lookup Performance
The funcgraph-args feature frequently calls btf_find_by_name_kind(), which currently uses a linear search algorithm. With large BTF datasets like vmlinux
(containing over 80,000 named types), this causes significant performance overhead.
This patch series introduces a new libbpf interface btf__permute(), which allows tools like pahole to sort BTF types by kind and name. After generating a sorted type ID array, these tools can invoke the new interface to perform in-place BTF sorting. During BTF parsing, btf_check_sorted() verifies whether the types are sorted.
Performance testing shows dramatic improvement after sorting by kind and name, as demonstrated below:
# echo 1 > options/funcgraph-args # echo function_graph > current_tracer
Before:
# time cat trace | wc -l 58098
real 0m7.514s user 0m0.010s sys 0m7.374s
After:
# time cat trace | wc -l 58837
real 0m0.371s user 0m0.000s sys 0m0.383s
This represents about 20x performance improvement for BTF type lookups.
v2:
https://lore.kernel.org/all/[email protected]/
v2 -> v3:
- Remove sorting logic from libbpf and provide a generic btf__permute() interface
- Remove the search direction patch since sorted lookup provides sufficient performance and changing search order could cause conflicts between BTF and base BTF
- Include btf_sort.c directly in btf.c to reduce function call overhead
Donglin Peng (3):
btf: implement BTF type sorting for accelerated lookups selftests/bpf: add tests for BTF type permutation
btf: Reuse libbpf code for BTF type sorting verification and binary
search
kernel/bpf/btf.c | 34 +-- tools/lib/bpf/btf.c | 262 +++++++++++++++++-- tools/lib/bpf/btf.h | 17 ++ tools/lib/bpf/btf_sort.c | 174 ++++++++++++ tools/lib/bpf/btf_sort.h | 11 + tools/lib/bpf/libbpf.map | 6 + tools/lib/bpf/libbpf_version.h | 2 +- tools/testing/selftests/bpf/prog_tests/btf.c | 109 ++++++-- 8 files changed, 559 insertions(+), 56 deletions(-) create mode 100644 tools/lib/bpf/btf_sort.c create mode 100644 tools/lib/bpf/btf_sort.h
Signature · 1 line
2.34.1