Skip to content

RFC Significantly Improve BTF Type Lookup Performance

Donglin Peng bpf lkml 2 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v3 RFC Latest3 patches 15 repliesIn review
  2. 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 filesSizeRepliesApplied
1/3btf: implement BTF type sorting for accelerated lookupstools/lib/bpf/btf.c tools/lib/bpf/btf.h tools/lib/bpf/btf_sort.c +3 more+447 -257 replies
2/3selftests/bpf: add tests for BTF type permutationtools/testing/selftests/bpf/prog_tests/btf.c+94 -152 replies
3/3btf: Reuse libbpf code for BTF type sorting verification and binary searchkernel/bpf/btf.c+18 -166 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v3 yet.

Read the v3 thread

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