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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-Id: <20251020093941.548058-1-dolinux.peng@gmail.com>
Date: Mon, 20 Oct 2025 17:39:36 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: ast@...nel.org
Cc: linux-kernel@...r.kernel.org,
	bpf@...r.kernel.org,
	Donglin Peng <dolinux.peng@...il.com>
Subject: [RFC PATCH v2 0/5] Significantly Improve BTF Type Lookup Performance

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