public inbox for linux-kernel@vger.kernel.org
 help / color / mirror / Atom feed
* [PATCH bpf-next v10 00/13] Improve the performance of BTF type lookups with binary search
@ 2025-12-18 11:30 Donglin Peng
  2025-12-18 11:30 ` [PATCH bpf-next v10 01/13] libbpf: Add BTF permutation support for type reordering Donglin Peng
                   ` (12 more replies)
  0 siblings, 13 replies; 72+ messages in thread
From: Donglin Peng @ 2025-12-18 11:30 UTC (permalink / raw)
  To: ast, andrii.nakryiko, eddyz87
  Cc: zhangxiaoqin, ihor.solodrai, linux-kernel, bpf, pengdonglin

From: pengdonglin <pengdonglin@xiaomi.com>

The series addresses the performance limitations of linear search in large
BTFs by:
1. Adding BTF permutation support
2. Using resolve_btfids to sort BTF during the build phase
3. Checking BTF sorting
4. Using binary search when looking up types

Patch #1 introduces an interface for btf__permute in libbpf to relay out BTF.
Patch #2 adds test cases to validate the functionality of btf__permute in base
and split BTF scenarios.
Patch #3 introduces a new phase in the resolve_btfids tool to sort BTF by name
in ascending order.
Patches #4-#7 implement the sorting check and binary search.
Patches #8-#10 optimize type lookup performance of some functions by skipping
anonymous types or invoking btf_find_by_name_kind.
Patches #11-#12 introduce btf_is_sorted and btf_sorted_start_id for clarity.
Patch #13 refactors the code by calling str_is_empty.

Here is a simple performance test result [1] for lookups to find 87,584 named
types in vmlinux BTF:

./vmtest.sh -- ./test_progs -t btf_permute/perf -v

Results:
| Condition          | Lookup Time | Improvement  |
|--------------------|-------------|--------------|
| Unsorted (Linear)  |  36,534 ms  | Baseline     |
| Sorted (Binary)    |      15 ms  | 2437x faster |

The binary search implementation reduces lookup time from 36.5 seconds to 15
milliseconds, achieving a **2437x** speedup for large-scale type queries.

Changelog:
v10:
- Improve btf__permute() documentation (Eduard)
- Fall back to linear search when locating anonymous types (Eduard)
- Remove redundant NULL name check in libbpf's linear search path (Eduard)
- Simplify btf_check_sorted() implementation (Eduard)
- Treat kernel modules as unsorted by default
- Introduce btf_is_sorted and btf_sorted_start_id for clarity (Eduard)
- Fix optimizations in btf_find_decl_tag_value() and btf_prepare_func_args()
  to support split BTF
- Remove linear search branch in determine_ptr_size()
- Rebase onto Ihor's v4 patch series [4]

v9:
- Link: https://lore.kernel.org/bpf/20251208062353.1702672-1-dolinux.peng@gmail.com/
- Optimize the performance of the function determine_ptr_size by invoking
  btf__find_by_name_kind
- Optimize the performance of btf_find_decl_tag_value/btf_prepare_func_args/
  bpf_core_add_cands by skipping anonymous types
- Rebase the patch series onto Ihor's v3 patch series [3]

v8
- Link: https://lore.kernel.org/bpf/20251126085025.784288-1-dolinux.peng@gmail.com/
- Remove the type dropping feature of btf__permute (Andrii)
- Refactor the code of btf__permute (Andrii, Eduard)
- Make the self-test code cleaner (Eduard)
- Reconstruct the BTF sorting patch based on Ihor's patch series [2]
- Simplify the sorting logic and place anonymous types before named types
  (Andrii, Eduard)
- Optimize type lookup performance of two kernel functions
- Refactoring the binary search and type lookup logic achieves a 4.2%
  performance gain, reducing the average lookup time (via the perf test
  code in [1] for 60,995 named types in vmlinux BTF) from 10,217 us (v7) to
  9,783 us (v8).

v7:
- Link: https://lore.kernel.org/all/20251119031531.1817099-1-dolinux.peng@gmail.com/
- btf__permute API refinement: Adjusted id_map and id_map_cnt parameter
  usage so that for base BTF, id_map[0] now contains the new id of original
  type id 1 (instead of VOID type id 0), improving logical consistency
- Selftest updates: Modified test cases to align with the API usage changes
- Refactor the code of resolve_btfids

v6:
- Link: https://lore.kernel.org/all/20251117132623.3807094-1-dolinux.peng@gmail.com/
- ID Map-based reimplementation of btf__permute (Andrii)
- Build-time BTF sorting using resolve_btfids (Alexei, Eduard)
- Binary search method refactoring (Andrii)
- Enhanced selftest coverage

v5:
- Link: https://lore.kernel.org/all/20251106131956.1222864-1-dolinux.peng@gmail.com/
- Refactor binary search implementation for improved efficiency
  (Thanks to Andrii and Eduard)
- Extend btf__permute interface with 'ids_sz' parameter to support
  type dropping feature (suggested by Andrii). Plan subsequent reimplementation of
  id_map version for comparative analysis with current sequence interface
- Add comprehensive test coverage for type dropping functionality
- Enhance function comment clarity and accuracy

v4:
- Link: https://lore.kernel.org/all/20251104134033.344807-1-dolinux.peng@gmail.com/
- Abstracted btf_dedup_remap_types logic into a helper function (suggested by Eduard).
- Removed btf_sort.c and implemented sorting separately for libbpf and kernel (suggested by Andrii).
- Added test cases for both base BTF and split BTF scenarios (suggested by Eduard).
- Added validation for name-only sorting of types (suggested by Andrii)
- Refactored btf__permute implementation to reduce complexity (suggested by Andrii)
- Add doc comments for btf__permute (suggested by Andrii)

v3:
- Link: https://lore.kernel.org/all/20251027135423.3098490-1-dolinux.peng@gmail.com/
- Remove sorting logic from libbpf and provide a generic btf__permute() interface (suggested
  by Andrii)
- Omitted the search direction patch to avoid conflicts with base BTF (suggested by Eduard).
- Include btf_sort.c directly in btf.c to reduce function call overhead

v2:
- Link: https://lore.kernel.org/all/20251020093941.548058-1-dolinux.peng@gmail.com/
- Moved sorting to the build phase to reduce overhead (suggested by Alexei).
- Integrated sorting into btf_dedup_compact_and_sort_types (suggested by Eduard).
- Added sorting checks during BTF parsing.
- Consolidated common logic into btf_sort.c for sharing (suggested by Alan).

v1:
- Link: https://lore.kernel.org/all/20251013131537.1927035-1-dolinux.peng@gmail.com/

[1] https://github.com/pengdonglin137/btf_sort_test
[2] https://lore.kernel.org/bpf/20251126012656.3546071-1-ihor.solodrai@linux.dev/
[3] https://lore.kernel.org/bpf/20251205223046.4155870-1-ihor.solodrai@linux.dev/
[4] https://lore.kernel.org/bpf/20251218003314.260269-1-ihor.solodrai@linux.dev/

pengdonglin (13):
  libbpf: Add BTF permutation support for type reordering
  selftests/bpf: Add test cases for btf__permute functionality
  tools/resolve_btfids: Support BTF sorting feature
  libbpf: Optimize type lookup with binary search for sorted BTF
  libbpf: Verify BTF Sorting
  btf: Optimize type lookup with binary search
  btf: Verify BTF Sorting
  bpf: Skip anonymous types in type lookup for performance
  bpf: Optimize the performance of find_bpffs_btf_enums
  libbpf: Optimize the performance of determine_ptr_size
  libbpf: Add btf_is_sorted and btf_sorted_start_id helpers to refactor
    the code
  btf: Add btf_is_sorted to refactor the code
  btf: Refactor the code by calling str_is_empty

 include/linux/btf.h                           |   2 +
 kernel/bpf/btf.c                              | 170 +++++++++-
 kernel/bpf/inode.c                            |  42 ++-
 kernel/bpf/verifier.c                         |   7 +-
 tools/bpf/resolve_btfids/main.c               |  68 ++++
 tools/lib/bpf/btf.c                           | 321 +++++++++++++++---
 tools/lib/bpf/btf.h                           |  36 ++
 tools/lib/bpf/libbpf.c                        |   4 +-
 tools/lib/bpf/libbpf.map                      |   1 +
 tools/lib/bpf/libbpf_internal.h               |   2 +
 .../selftests/bpf/prog_tests/btf_permute.c    | 228 +++++++++++++
 11 files changed, 786 insertions(+), 95 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.c

-- 
2.34.1


^ permalink raw reply	[flat|nested] 72+ messages in thread

end of thread, other threads:[~2026-01-08  1:50 UTC | newest]

Thread overview: 72+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-12-18 11:30 [PATCH bpf-next v10 00/13] Improve the performance of BTF type lookups with binary search Donglin Peng
2025-12-18 11:30 ` [PATCH bpf-next v10 01/13] libbpf: Add BTF permutation support for type reordering Donglin Peng
2025-12-18 23:02   ` Andrii Nakryiko
2025-12-19  3:14     ` Donglin Peng
2025-12-19  3:16       ` Donglin Peng
2025-12-19 17:07       ` Andrii Nakryiko
2025-12-20  8:39         ` Donglin Peng
2025-12-18 11:30 ` [PATCH bpf-next v10 02/13] selftests/bpf: Add test cases for btf__permute functionality Donglin Peng
2025-12-18 23:03   ` Andrii Nakryiko
2025-12-19  3:30     ` Donglin Peng
2025-12-18 11:30 ` [PATCH bpf-next v10 03/13] tools/resolve_btfids: Support BTF sorting feature Donglin Peng
2025-12-18 23:09   ` Andrii Nakryiko
2025-12-19  3:42     ` Donglin Peng
2025-12-19 17:12       ` Andrii Nakryiko
2025-12-20  8:44         ` Donglin Peng
2025-12-18 11:30 ` [PATCH bpf-next v10 04/13] libbpf: Optimize type lookup with binary search for sorted BTF Donglin Peng
2025-12-18 19:32   ` Eduard Zingerman
2025-12-18 23:29   ` Andrii Nakryiko
2025-12-19  0:13     ` Eduard Zingerman
2025-12-19  0:19       ` Andrii Nakryiko
2025-12-19  0:24         ` Eduard Zingerman
2025-12-19  1:01           ` Andrii Nakryiko
2025-12-19  2:53     ` Donglin Peng
2025-12-19 17:28       ` Andrii Nakryiko
2025-12-20  9:38         ` Donglin Peng
2025-12-22  1:58           ` Donglin Peng
2026-01-06  0:38             ` Andrii Nakryiko
2026-01-06  2:42               ` Donglin Peng
2026-01-06  0:36           ` Andrii Nakryiko
2026-01-06  2:50             ` Donglin Peng
2025-12-18 11:30 ` [PATCH bpf-next v10 05/13] libbpf: Verify BTF Sorting Donglin Peng
2025-12-18 19:38   ` Eduard Zingerman
2025-12-18 23:44   ` Andrii Nakryiko
2025-12-19  5:06     ` Donglin Peng
2025-12-19 17:33       ` Andrii Nakryiko
     [not found]         ` <CAErzpmsvirekLBRrJYVgmRC0YKWCbo7OyRQXgNYrk83aF-Wz2Q@mail.gmail.com>
2026-01-07  3:45           ` Donglin Peng
2026-01-07 21:50             ` Andrii Nakryiko
2026-01-08  1:50               ` Donglin Peng
2025-12-18 11:30 ` [PATCH bpf-next v10 06/13] btf: Optimize type lookup with binary search Donglin Peng
2025-12-18 21:38   ` Eduard Zingerman
2025-12-19  5:07     ` Donglin Peng
2025-12-18 11:30 ` [PATCH bpf-next v10 07/13] btf: Verify BTF Sorting Donglin Peng
2025-12-18 21:43   ` Eduard Zingerman
2025-12-19  5:10     ` Donglin Peng
2025-12-18 23:46   ` Andrii Nakryiko
2025-12-19  5:10     ` Donglin Peng
2025-12-18 11:30 ` [PATCH bpf-next v10 08/13] bpf: Skip anonymous types in type lookup for performance Donglin Peng
2025-12-18 22:21   ` Eduard Zingerman
2025-12-18 23:59     ` Andrii Nakryiko
2025-12-19  5:40       ` Donglin Peng
2025-12-18 22:24   ` Eduard Zingerman
2025-12-18 11:30 ` [PATCH bpf-next v10 09/13] bpf: Optimize the performance of find_bpffs_btf_enums Donglin Peng
2025-12-19  0:01   ` Andrii Nakryiko
2025-12-19  5:41     ` Donglin Peng
2025-12-20 14:27       ` Donglin Peng
2025-12-18 11:30 ` [PATCH bpf-next v10 10/13] libbpf: Optimize the performance of determine_ptr_size Donglin Peng
2025-12-18 22:27   ` Eduard Zingerman
2025-12-19  0:03   ` Andrii Nakryiko
2025-12-19  5:42     ` Donglin Peng
2025-12-18 11:30 ` [PATCH bpf-next v10 11/13] libbpf: Add btf_is_sorted and btf_sorted_start_id helpers to refactor the code Donglin Peng
2025-12-18 22:33   ` Eduard Zingerman
2025-12-19  5:49     ` Donglin Peng
2025-12-19  0:05   ` Andrii Nakryiko
2025-12-19  5:51     ` Donglin Peng
2025-12-19 17:35       ` Andrii Nakryiko
2025-12-20 14:27         ` Donglin Peng
2025-12-18 11:30 ` [PATCH bpf-next v10 12/13] btf: Add btf_is_sorted " Donglin Peng
2025-12-18 22:30   ` Eduard Zingerman
2025-12-19  0:05   ` Andrii Nakryiko
2025-12-20 14:25     ` Donglin Peng
2025-12-18 11:30 ` [PATCH bpf-next v10 13/13] btf: Refactor the code by calling str_is_empty Donglin Peng
2025-12-18 22:34   ` Eduard Zingerman

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox