[RFC PATCH v3 0/3] Significantly Improve BTF Type Lookup Performance

[Donglin Peng <dolinux.peng@gmail.com>]

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/20251020093941.548058-1-dolinux.peng@gmail.com/

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

-- 
2.34.1