Message-Id: <20251117132623.3807094-1-dolinux.peng@gmail.com>
Date: Mon, 17 Nov 2025 21:26:16 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: ast@...nel.org
Cc: eddyz87@...il.com,
	andrii.nakryiko@...il.com,
	zhangxiaoqin@...omi.com,
	linux-kernel@...r.kernel.org,
	bpf@...r.kernel.org,
	Donglin Peng <pengdonglin@...omi.com>
Subject: [RFC PATCH v6 0/7] BTF performance optimizations with permutation and binary search

From: Donglin Peng <pengdonglin@...omi.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
v6:
- 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               | 203 ++++++
 tools/lib/bpf/btf.c                           | 353 +++++++++-
 tools/lib/bpf/btf.h                           |  43 ++
 tools/lib/bpf/libbpf.map                      |   1 +
 .../selftests/bpf/prog_tests/btf_permute.c    | 632 ++++++++++++++++++
 9 files changed, 1351 insertions(+), 32 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.c

-- 
2.34.1

Powered by blists - more mailing lists