Skip to content

Improve the performance of BTF type lookups with binary search

Donglin Peng bpf lkml 9 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v12 Latest11 patches 11 repliesIn review 7 of 11 applied
  2. v1111 patches 1 replySuperseded
  3. v1013 patches 58 repliesSuperseded
Earlier versions · 6
VersionPostedPatchesRepliesStatus
v910 patches25 repliesSuperseded
v8 RFC9 patches0 repliesSuperseded
v7 RFC7 patches33 repliesSuperseded
v6 RFC7 patches0 repliesSuperseded
v57 patches11 repliesSuperseded
v4 RFC7 patches44 repliesSuperseded

Changes in v12 from the cover letter

- Set the start_id to 1 instead of btf->start_id in the btf__find_by_name (AI)

Patches in v12 7 of 11 applied

#Subject and filesSizeRepliesApplied
1/11libbpf: Add BTF permutation support for type reorderingtools/lib/bpf/btf.c tools/lib/bpf/btf.h tools/lib/bpf/libbpf.map+176 -00 repliesApplied
2/11selftests/bpf: Add test cases for btf__permute functionalitytools/testing/selftests/bpf/prog_tests/btf_permute.c+244 -00 repliesApplied
3/11tools/resolve_btfids: Support BTF sorting featuretools/bpf/resolve_btfids/main.c+64 -02 repliesApplied
4/11libbpf: Optimize type lookup with binary search for sorted BTFtools/lib/bpf/btf.c+66 -243 replies
5/11libbpf: Verify BTF sortingtools/lib/bpf/btf.c+25 -00 repliesApplied
6/11btf: Optimize type lookup with binary searchinclude/linux/btf.h kernel/bpf/btf.c+83 -92 replies
7/11btf: Verify BTF sortingkernel/bpf/btf.c+42 -02 replies
8/11bpf: Skip anonymous types in type lookup for performancekernel/bpf/btf.c kernel/bpf/verifier.c+7 -100 repliesApplied
9/11bpf: Optimize the performance of find_bpffs_btf_enumskernel/bpf/inode.c+17 -250 repliesApplied
10/11libbpf: Optimize the performance of determine_ptr_sizetools/lib/bpf/btf.c+6 -142 replies
11/11btf: Refactor the code by calling str_is_emptytools/lib/bpf/btf.c tools/lib/bpf/libbpf.c+19 -190 repliesApplied

Reviews trailers per patch

8 of 11 patches have a Reviewed-by or Acked-by.

PatchEduard ZingermanAndrii Nakryiko
1/11A-b
2/11A-b
3/11A-b
4/11
5/11A-b
6/11
7/11
8/11A-b
9/11A-b
10/11A-b A-b
11/11A-b

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v12 thread

Cover letter [PATCH bpf-next v12 00/11] Improve the performance of BTF type lookups with binary search

From: Donglin Peng <[email protected]>

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.
Patch #11 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:
v12:
- Set the start_id to 1 instead of btf->start_id in the btf__find_by_name (AI)

v11:
- Link: https://lore.kernel.org/bpf/[email protected]/
- PATCH #1: Modify implementation of btf__permute: id_map[0] must be 0 for base BTF (Andrii)
- PATCH #3: Refactor the code (Andrii)
- PATCH #4~8:
- Revert to using the binary search in v7 to simplify the code (Andrii)
- Refactor the code of btf_check_sorted (Andrii, Eduard)
- Rename sorted_start_id to named_start_id
- Rename btf_sorted_start_id to btf_named_start_id, and add comments (Andrii, Eduard)

v10:
- Link: https://lore.kernel.org/all/[email protected]/
- 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/[email protected]/
- 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/[email protected]/
- 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/[email protected]/
- 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/[email protected]/
- 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/[email protected]/
- 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/[email protected]/
- 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/[email protected]/
- 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/[email protected]/
- 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/[email protected]/

[1] https://github.com/pengdonglin137/btf_sort_test
[2] https://lore.kernel.org/bpf/[email protected]/
[3] https://lore.kernel.org/bpf/[email protected]/
[4] https://lore.kernel.org/bpf/[email protected]/

Donglin Peng (11):
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
btf: Refactor the code by calling str_is_empty

 include/linux/btf.h                           |   1 +
 kernel/bpf/btf.c                              | 143 ++++++++-
 kernel/bpf/inode.c                            |  42 +--
 kernel/bpf/verifier.c                         |   7 +-
 tools/bpf/resolve_btfids/main.c               |  64 ++++
 tools/lib/bpf/btf.c                           | 296 +++++++++++++++---
 tools/lib/bpf/btf.h                           |  42 +++
 tools/lib/bpf/libbpf.c                        |   4 +-
 tools/lib/bpf/libbpf.map                      |   1 +
 .../selftests/bpf/prog_tests/btf_permute.c    | 244 +++++++++++++++
 10 files changed, 746 insertions(+), 98 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.c
Signature · 1 line
2.34.1