[RFC PATCH v2 0/5] Significantly Improve BTF Type Lookup Performance

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

The funcgraph-args feature currently invokes btf_find_by_name_kind()
frequently, which uses a linear search algorithm. With large BTF data
sets like vmlinux (containing over 80,000 named types), this results
in significant performance overhead.

This patch series optimizes btf_find_by_name_kind() by:
1. Sorting BTF types by kind and name to enable binary search
2. Changing the search order to check local BTF before base BTF

Performance testing shows dramatic improvement:

 # echo 1 > options/funcgraph-args
 # echo function_graph > current_tracer

Before:
 # time cat trace | wc -l
 124176
 real    0m16.154s
 user    0m0.000s
 sys     0m15.962s

After:
 # time cat trace | wc -l
 124176
 real    0m0.948s
 user    0m0.000s
 sys     0m0.973s

This represents over 20x performance improvement for BTF type lookups.


Donglin Peng (5):
  btf: search local BTF before base BTF
  btf: sort BTF types by kind and name to enable binary search
  libbpf: check if BTF is sorted to enable binary search
  selftests/bpf: add tests for BTF deduplication and sorting
  btf: add CONFIG_BPF_SORT_BTF_BY_KIND_NAME

 include/linux/btf.h                          |  21 ++-
 kernel/bpf/Kconfig                           |   8 +
 kernel/bpf/Makefile                          |   1 +
 kernel/bpf/btf.c                             |  36 ++--
 kernel/bpf/btf_sort.c                        |   2 +
 scripts/Makefile.btf                         |   5 +
 tools/lib/bpf/Build                          |   2 +-
 tools/lib/bpf/btf.c                          | 169 +++++++++++++++---
 tools/lib/bpf/btf.h                          |   2 +
 tools/lib/bpf/btf_sort.c                     | 159 +++++++++++++++++
 tools/lib/bpf/libbpf_internal.h              |   6 +
 tools/testing/selftests/bpf/prog_tests/btf.c | 171 +++++++++++++++++++
 12 files changed, 541 insertions(+), 41 deletions(-)
 create mode 100644 kernel/bpf/btf_sort.c
 create mode 100644 tools/lib/bpf/btf_sort.c

-- 
2.34.1