[RFC PATCH v7 0/7] Improve the performance of BTF type lookups with binary search

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

From: pengdonglin <pengdonglin@xiaomi.com>

This patch series introduces significant performance improvements (~1785x) for BTF
type lookups by implementing type permutation and binary search optimizations.

## Overview

The series addresses the performance limitations of linear search in large
BTF instances by:

1. Adding BTF permutation support
2. Sorting BTF during the building phase
3. Implementing binary search optimization

## Key Changes

### Patch 1: libbpf: Add BTF permutation support for type reordering
- Introduces btf__permute interface for BTF type reorganization

### Patch 2: selftests/bpf: Add test cases for btf__permute functionality
- Validates functionality across both base BTF and split BTF scenarios

### Patch 3: tools/resolve_btfids: Add --btf_sort option for BTF name sorting
- Implements BTF sorting via resolve_btfids during build process

### Patch 4: libbpf: Optimize type lookup with binary search for sorted BTF
- Implements binary search algorithm for sorted BTF instances
- Maintains linear search fallback for backward compatibility

### Patch 5: libbpf: Implement sorting validation for binary search optimization
- Adds sorting validation during BTF parsing

### Patch 6: btf: Optimize type lookup with binary search
- Ports binary search optimization to kernel-side BTF implementation

### Patch 7: btf: Add sorting validation for binary search
- Implements named type counting for vmlinux and kernel module BTF sorting validation

## Performance Impact Analysis

Repo: https://github.com/pengdonglin137/btf_sort_test

### Lookup Performance Comparison
Test Case: Locate all 58,718 named types in vmlinux BTF
Methodology:
./vmtest.sh -- ./test_progs -t btf_permute/perf -v

Results:
| Condition          | Lookup Time | Improvement  |
|--------------------|-------------|--------------|
| Unsorted (Linear)  | 16,666.5 ms | Baseline     |
| Sorted (Binary)    |      9.3 ms | 1785x faster |

Analysis:
The binary search implementation reduces lookup time from 16.7 seconds to 9.3 milliseconds,
achieving a **1785x** speedup for large-scale type queries.

## Changelog
v7:
- 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/

Donglin Peng (7):
  libbpf: Add BTF permutation support for type reordering
  selftests/bpf: Add test cases for btf__permute functionality
  tools/resolve_btfids: Add --btf_sort option for BTF name sorting
  libbpf: Optimize type lookup with binary search for sorted BTF
  libbpf: Implement BTF type sorting validation for binary search
    optimization
  btf: Optimize type lookup with binary search
  btf: Add sorting validation for binary search

 kernel/bpf/btf.c                              | 147 ++++-
 scripts/Makefile.btf                          |   2 +
 scripts/Makefile.modfinal                     |   1 +
 scripts/link-vmlinux.sh                       |   1 +
 tools/bpf/resolve_btfids/main.c               | 200 ++++++
 tools/lib/bpf/btf.c                           | 327 +++++++++-
 tools/lib/bpf/btf.h                           |  43 ++
 tools/lib/bpf/libbpf.map                      |   1 +
 .../selftests/bpf/prog_tests/btf_permute.c    | 608 ++++++++++++++++++
 9 files changed, 1298 insertions(+), 32 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.c

-- 
2.34.1