linux-kernel - [RFC PATCH v3 0/3] 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: <20251027135423.3098490-1-dolinux.peng@gmail.com>
Date: Mon, 27 Oct 2025 21:54:20 +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 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/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