libbpf: BTF performance optimizations with permutation and binary search
Subsystems (4)
v4 cover libbpf: BTF performance optimizations with permutation and binary search
This patch series introduces significant performance improvements 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 - Allows rearranging BTF types
2. Implementing binary search optimization - Dramatically improves lookup performance for sorted BTF types
## Key Changes
### Patch 1: libbpf: Extract BTF type remapping logic into helper function
- Refactors existing code to eliminate duplication
- Improves modularity and maintainability
- Prepares foundation for permutation functionality
### Patch 2: libbpf: Add BTF permutation support for type reordering
- Introduces btf__permute() API for in-place type rearrangement
- Handles both main BTF and extension data
- Maintains type reference consistency after permutation
### Patch 3: libbpf: Optimize type lookup with binary search for sorted BTF
- Implements binary search algorithm for sorted BTF instances
- Maintains linear search fallback for compatibility
- Significant performance improvement for large BTF with sorted types
### Patch 4: libbpf: Implement lazy sorting validation for binary search optimization
- Adds on-demand sorting verification
- Caches results for efficient repeated lookups
### Patch 5: btf: Optimize type lookup with binary search
- Ports binary search optimization to kernel-side BTF implementation
- Maintains full backward compatibility
### Patch 6: btf: Add lazy sorting validation for binary search
- Implements kernel-side lazy sorting detection
- Mirrors user-space implementation for consistency
### Patch 7: selftests/bpf: Add test cases for btf__permute functionality
- Validates both base BTF and split BTF scenarios
## Performance Impact Analysis
Repo: https://github.com/pengdonglin137/btf_sort_test
### 1. Sorting Validation Overhead
Test Environment: Local KVM virtual machine
Results:
- Total BTF types: 143,467
- Sorting validation time: 1.451 ms
*Note: This represents the maximum observed overhead during initial BTF loading.*
### 2. 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) | 17,282 ms | Baseline | | Sorted (Binary) | 19 ms | 909x faster |
Analysis:
The binary search implementation reduces lookup time from 17.3 seconds to 19 milliseconds, achieving a **909x** speedup for large-scale type queries.
## Changelog
v4:
- 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:
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:
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:
https://lore.kernel.org/all/[email protected]/
Donglin Peng (7):
libbpf: Extract BTF type remapping logic into helper function
libbpf: Add BTF permutation support for type reordering
libbpf: Optimize type lookup with binary search for sorted BTF
libbpf: Implement lazy sorting validation for binary search
optimization
btf: Optimize type lookup with binary search
btf: Add lazy sorting validation for binary search selftests/bpf: Add test cases for btf__permute functionality
kernel/bpf/btf.c | 177 ++++++- tools/lib/bpf/btf.c | 436 +++++++++++++++--- tools/lib/bpf/btf.h | 34 ++ tools/lib/bpf/libbpf.map | 1 + tools/lib/bpf/libbpf_internal.h | 1 + .../selftests/bpf/prog_tests/btf_permute.c | 142 ++++++ 6 files changed, 728 insertions(+), 63 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.c
Signature · 1 line
2.34.1
RFC PATCH v4 1/7 libbpf: Extract BTF type remapping logic into helper function
From: pengdonglin <[email protected]>
Refactor btf_dedup_remap_types() by extracting its core logic into a new btf_remap_types() helper function. This eliminates code duplication and improves modularity while maintaining the same functionality.
The new function encapsulates iteration over BTF types and BTF ext sections, accepting a callback for flexible type ID remapping. This makes the type remapping logic more maintainable and reusable.
--- tools/lib/bpf/btf.c | 63 +++++++++++++++++---------------- tools/lib/bpf/libbpf_internal.h | 1 + 2 files changed, 33 insertions(+), 31 deletions(-)
tools/lib/bpf/btf.c +32 -31
@@ -3400,6 +3400,37 @@ int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian)return 0 ; } +static int btf_remap_types (struct btf *btf,struct btf_ext *btf_ext, +btf_remap_type_fn visit,void *ctx) +{ +int i, r; + +for (i =0 ; i < btf->nr_types; i++) { +struct btf_type *t =btf_type_by_id (btf, btf->start_id + i); +struct btf_field_iter it; +__u32 *type_id; + + r =btf_field_iter_init (&it, t,BTF_FIELD_ITER_IDS ); +if (r) +return r; + +while ((type_id =btf_field_iter_next (&it))) { + r =visit (type_id, ctx); +if (r) +return r; + } + } + +if (!btf_ext) +return 0 ; + + r =btf_ext_visit_type_ids (btf_ext, visit, ctx); +if (r) +return r; + +return 0 ; +} +struct btf_dedup ;static struct btf_dedup *btf_dedup_new (struct btf *btf,const struct btf_dedup_opts *opts);
@@ -5320,37 +5351,7 @@ static int btf_dedup_remap_type_id(__u32 *type_id, void *ctx)*/ static int btf_dedup_remap_types (struct btf_dedup *d) { -int i, r; - -for (i =0 ; i < d->btf->nr_types; i++) { -struct btf_type *t =btf_type_by_id (d->btf, d->btf->start_id + i); -struct btf_field_iter it; -__u32 *type_id; - - r =btf_field_iter_init (&it, t,BTF_FIELD_ITER_IDS ); -if (r) -return r; - -while ((type_id =btf_field_iter_next (&it))) { -__u32 resolved_id, new_id; - - resolved_id =resolve_type_id (d, *type_id); - new_id = d->hypot_map[resolved_id]; -if (new_id >BTF_MAX_NR_TYPES ) -return -EINVAL ; - - *type_id = new_id; - } - } - -if (!d->btf_ext) -return 0 ; - - r =btf_ext_visit_type_ids (d->btf_ext, btf_dedup_remap_type_id, d); -if (r) -return r; - -return 0 ; +return btf_remap_types (d->btf, d->btf_ext, btf_dedup_remap_type_id, d); }/*
tools/lib/bpf/libbpf_internal.h +1 -0
@@ -582,6 +582,7 @@ int btf_ext_visit_type_ids(struct btf_ext *btf_ext, type_id_visit_fn visit, voidint btf_ext_visit_str_offs (struct btf_ext *btf_ext,str_off_visit_fn visit,void *ctx);__s32 btf__find_by_name_kind_own (const struct btf *btf,const char *type_name,__u32 kind); +typedef int (*btf_remap_type_fn )(__u32 *type_id,void *ctx);/* handle direct returned errors */ static inline int libbpf_err (int ret)
Signature · 1 line
2.34.1
Re: [RFC PATCH v4 1/7] libbpf: Extract BTF type remapping logic into helper function
Quoted 10 lines · Donglin Peng
From: pengdonglin <[email protected]>
Refactor
btf_dedup_remap_types()by extracting its core logic into a newbtf_remap_types()helper function. This eliminates code duplication and improves modularity while maintaining the same functionality.The new function encapsulates iteration over BTF types and BTF ext sections, accepting a callback for flexible type ID remapping. This makes the type remapping logic more maintainable and reusable.
Quoted 8 lines
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>---
Quoted 9 lines
tools/lib/bpf/btf.c | 63 +++++++++++++++++---------------- tools/lib/bpf/libbpf_internal.h | 1 + 2 files changed, 33 insertions(+), 31 deletions(-)tools/lib/bpf/btf.c +0
-0
tools/lib/bpf/btf.c int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian) · line 3404
Quoted 5 lines
tools/lib/bpf/btf.c +2
-0@@ -3400,6 +3400,37 @@ int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian)return 0 ; } +static int btf_remap_types (struct btf *btf,struct btf_ext *btf_ext, +btf_remap_type_fn visit,void *ctx)
^^^^^^^^^^^^^^^^^
Nit: there is already 'type_id_visit_fn', no need to add new type.
Quoted 32 lines
tools/lib/bpf/btf.c +29
-0+{ +int i, r; + +for (i =0 ; i < btf->nr_types; i++) { +struct btf_type *t =btf_type_by_id (btf, btf->start_id + i); +struct btf_field_iter it; +__u32 *type_id; + + r =btf_field_iter_init (&it, t,BTF_FIELD_ITER_IDS ); +if (r) +return r; + +while ((type_id =btf_field_iter_next (&it))) { + r =visit (type_id, ctx); +if (r) +return r; + } + } + +if (!btf_ext) +return 0 ; + + r =btf_ext_visit_type_ids (btf_ext, visit, ctx); +if (r) +return r; + +return 0 ; +} +struct btf_dedup ;static struct btf_dedup *btf_dedup_new (struct btf *btf,const struct btf_dedup_opts *opts);
[...]
Re: [RFC PATCH v4 1/7] libbpf: Extract BTF type remapping logic into helper function
In reply to Donglin PengQuoted 11 lines · Donglin Peng
From: pengdonglin <[email protected]>
Refactor
btf_dedup_remap_types()by extracting its core logic into a newbtf_remap_types()helper function. This eliminates code duplication and improves modularity while maintaining the same functionality.The new function encapsulates iteration over BTF types and BTF ext sections, accepting a callback for flexible type ID remapping. This makes the type remapping logic more maintainable and reusable.
Quoted 6 lines
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>
Signed-off-by is supposed to have properly spelled and capitalized real name of the contributor
Quoted 11 lines
Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 63 +++++++++++++++++---------------- tools/lib/bpf/libbpf_internal.h | 1 + 2 files changed, 33 insertions(+), 31 deletions(-)tools/lib/bpf/btf.c +0
-0
tools/lib/bpf/btf.c int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian) · line 3404
Quoted 5 lines
tools/lib/bpf/btf.c +2
-0@@ -3400,6 +3400,37 @@ int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian)return 0 ; } +static int btf_remap_types (struct btf *btf,struct btf_ext *btf_ext, +btf_remap_type_fn visit,void *ctx)
tbh, my goal is to reduce the amount of callback usage within libbpf, not add more of it...
I don't like this refactoring. We should convert btf_ext_visit_type_ids() into iterators, have btf_field_iter_init + btf_field_iter_next usable in for_each() form, and not try to reuse 5 lines of code. See my comments in the next patch.
Quoted 86 lines
tools/lib/bpf/btf.c +30
-31+{ +int i, r; + +for (i =0 ; i < btf->nr_types; i++) { +struct btf_type *t =btf_type_by_id (btf, btf->start_id + i); +struct btf_field_iter it; +__u32 *type_id; + + r =btf_field_iter_init (&it, t,BTF_FIELD_ITER_IDS ); +if (r) +return r; + +while ((type_id =btf_field_iter_next (&it))) { + r =visit (type_id, ctx); +if (r) +return r; + } + } + +if (!btf_ext) +return 0 ; + + r =btf_ext_visit_type_ids (btf_ext, visit, ctx); +if (r) +return r; + +return 0 ; +} +struct btf_dedup ;static struct btf_dedup *btf_dedup_new (struct btf *btf,const struct btf_dedup_opts *opts);@@ -5320,37 +5351,7 @@ static int btf_dedup_remap_type_id(__u32 *type_id, void *ctx)*/ static int btf_dedup_remap_types (struct btf_dedup *d) { -int i, r; - -for (i =0 ; i < d->btf->nr_types; i++) { -struct btf_type *t =btf_type_by_id (d->btf, d->btf->start_id + i); -struct btf_field_iter it; -__u32 *type_id; - - r =btf_field_iter_init (&it, t,BTF_FIELD_ITER_IDS ); -if (r) -return r; - -while ((type_id =btf_field_iter_next (&it))) { -__u32 resolved_id, new_id; - - resolved_id =resolve_type_id (d, *type_id); - new_id = d->hypot_map[resolved_id]; -if (new_id >BTF_MAX_NR_TYPES ) -return -EINVAL ; - - *type_id = new_id; - } - } - -if (!d->btf_ext) -return 0 ; - - r =btf_ext_visit_type_ids (d->btf_ext, btf_dedup_remap_type_id, d); -if (r) -return r; - -return 0 ; +return btf_remap_types (d->btf, d->btf_ext, btf_dedup_remap_type_id, d); }/* tools/lib/bpf/libbpf_internal.h +1
-1@@ -582,6 +582,7 @@ int btf_ext_visit_type_ids(struct btf_ext *btf_ext, type_id_visit_fn visit, voidint btf_ext_visit_str_offs (struct btf_ext *btf_ext,str_off_visit_fn visit,void *ctx);__s32 btf__find_by_name_kind_own (const struct btf *btf,const char *type_name,__u32 kind); +typedef int (*btf_remap_type_fn )(__u32 *type_id,void *ctx);/* handle direct returned errors */ static inline int libbpf_err (int ret) --2.34.1
Eduard Zingerman
maintainerRe: [RFC PATCH v4 1/7] libbpf: Extract BTF type remapping logic into helper function
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 10 lines
tools/lib/bpf/btf.c int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian) · line 3404
Quoted 6 lines
tools/lib/bpf/btf.c +2
-0@@ -3400,6 +3400,37 @@ int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian)return 0 ; } +static int btf_remap_types (struct btf *btf,struct btf_ext *btf_ext, +btf_remap_type_fn visit,void *ctx)tbh, my goal is to reduce the amount of callback usage within libbpf, not add more of it...
Quoted 4 lines
I don't like this refactoring. We should convert
btf_ext_visit_type_ids()into iterators, havebtf_field_iter_init+btf_field_iter_nextusable infor_each()form, and not try to reuse 5 lines of code. See my comments in the next patch.
Remapping types is a concept.
I hate duplicating code for concepts.
Similarly, having patch #3 == patch #5 and patch #4 == patch #6 is plain ugly. Just waiting for a bug because we changed the one but forgot to change another in a year or two.
[...]
Re: [RFC PATCH v4 1/7] libbpf: Extract BTF type remapping logic into helper function
Quoted 20 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 10 lines
tools/lib/bpf/btf.c int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian) · line 3404
Quoted 6 lines
tools/lib/bpf/btf.c +2
-0@@ -3400,6 +3400,37 @@ int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian)return 0 ; } +static int btf_remap_types (struct btf *btf,struct btf_ext *btf_ext, +btf_remap_type_fn visit,void *ctx)tbh, my goal is to reduce the amount of callback usage within libbpf, not add more of it...
Quoted 4 lines
I don't like this refactoring. We should convert
btf_ext_visit_type_ids()into iterators, havebtf_field_iter_init+btf_field_iter_nextusable infor_each()form, and not try to reuse 5 lines of code. See my comments in the next patch.
Quoted 5 lines
Remapping types is a concept.
I hate duplicating code for concepts.
Similarly, having patch #3 == patch #5 and patch #4 == patch #6 is plain ugly. Just waiting for a bug because we changed the one but forgot to change another in a year or two.
Tricky and evolving part (iterating all type ID fields) is abstracted behind the iterator (and we should do the same for btf_ext). Iterating types is not something tricky or requiring constant maintenance.
Same for binary search, I don't see why we'd need to adjust it. So no, I don't want to share code between kernel and libbpf just to reuse binary search implementation, sorry.
Quoted 2 lines
[...]
Eduard Zingerman
maintainerRe: [RFC PATCH v4 1/7] libbpf: Extract BTF type remapping logic into helper function
Quoted 27 lines · Andrii Nakryiko
Quoted 20 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 10 lines
tools/lib/bpf/btf.c int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian) · line 3404
Quoted 6 lines
tools/lib/bpf/btf.c +2
-0@@ -3400,6 +3400,37 @@ int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian)return 0 ; } +static int btf_remap_types (struct btf *btf,struct btf_ext *btf_ext, +btf_remap_type_fn visit,void *ctx)tbh, my goal is to reduce the amount of callback usage within libbpf, not add more of it...
Quoted 4 lines
I don't like this refactoring. We should convert
btf_ext_visit_type_ids()into iterators, havebtf_field_iter_init+btf_field_iter_nextusable infor_each()form, and not try to reuse 5 lines of code. See my comments in the next patch.Quoted 5 lines
Remapping types is a concept.
I hate duplicating code for concepts.
Similarly, having patch #3 == patch #5 and patch #4 == patch #6 is plain ugly. Just waiting for a bug because we changed the one but forgot to change another in a year or two.
Quoted 7 lines
Tricky and evolving part (iterating all type ID fields) is abstracted behind the iterator (and we should do the same for
btf_ext). Iterating types is not something tricky or requiring constant maintenance.Same for binary search, I don't see why we'd need to adjust it. So no, I don't want to share code between kernel and libbpf just to reuse binary search implementation, sorry.
<rant>
Sure binary search is trivial, but did you count how many times you asked people to re-implement binary search as in [1]?
[1] https://elixir.bootlin.com/linux/v6.18-rc4/source/kernel/bpf/verifier.c#L2952
</rant>
Re: [RFC PATCH v4 1/7] libbpf: Extract BTF type remapping logic into helper function
Quoted 33 lines · Eduard Zingerman
Quoted 31 lines · Andrii Nakryiko
Quoted 20 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 10 lines
tools/lib/bpf/btf.c int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian) · line 3404
Quoted 6 lines
tools/lib/bpf/btf.c +2
-0@@ -3400,6 +3400,37 @@ int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian)return 0 ; } +static int btf_remap_types (struct btf *btf,struct btf_ext *btf_ext, +btf_remap_type_fn visit,void *ctx)tbh, my goal is to reduce the amount of callback usage within libbpf, not add more of it...
Quoted 4 lines
I don't like this refactoring. We should convert
btf_ext_visit_type_ids()into iterators, havebtf_field_iter_init+btf_field_iter_nextusable infor_each()form, and not try to reuse 5 lines of code. See my comments in the next patch.Quoted 5 lines
Remapping types is a concept.
I hate duplicating code for concepts.
Similarly, having patch #3 == patch #5 and patch #4 == patch #6 is plain ugly. Just waiting for a bug because we changed the one but forgot to change another in a year or two.Tricky and evolving part (iterating all type ID fields) is abstracted behind the iterator (and we should do the same for
btf_ext). Iterating types is not something tricky or requiring constant maintenance.
Quoted 8 lines
Quoted 3 lines
Same for binary search, I don't see why we'd need to adjust it. So no, I don't want to share code between kernel and libbpf just to reuse binary search implementation, sorry.
<rant>
Sure binary search is trivial, but did you count how many times you asked people to re-implement binary search as in [1]?
Exact match binary search can be called trivial, yes. Lower/upper bound binary search looks deceivingly simple, but it requires attention to every single line of code. But the end result is simple and straightforward, yes.
I'm not sure what point you are trying to make, though. Yes, I've asked people many times to implement upper/lower bound binary search similarly to the one in find_linfo(), because usually people have various unnecessary checks, keeping track not just of bounds, but also remembering some element that we know satisfied the condition at some point before, etc. It's not elegant, harder to reason about, and can be done more succinctly.
You don't like that I ask people to improve implementation? You don't like the implementation itself? Or are you suggesting that we should add a "generic" C implementation of lower_bound/upper_bound and use callbacks for comparison logic? What are you ranting about, exactly?
As I said, once binary search (of whatever kind, bounds or exact) is written for something like this, it doesn't have to ever be modified. I don't see this as a maintainability hurdle at all. But sharing code between libbpf and kernel is something to be avoided. Look at #ifdef __KERNEL__ sections of relo_core.c as one reason why.
Quoted 4 lines
[1] https://elixir.bootlin.com/linux/v6.18-rc4/source/kernel/bpf/verifier.c#L2952
</rant>
Eduard Zingerman
maintainerRe: [RFC PATCH v4 1/7] libbpf: Extract BTF type remapping logic into helper function
On Wed, 2025-11-05 at 10:20 -0800, Andrii Nakryiko wrote:
[...]
Quoted 1 line
You don't like that I ask people to improve implementation?
Not at all.
Quoted 4 lines
You don't like the implementation itself? Or are you suggesting that we should add a "generic" C implementation of lower_bound/upper_bound and use callbacks for comparison logic? What are you ranting about, exactly?
Actually, having it as a static inline function in a header would be nice. I just tried that, and gcc is perfectly capable of inlining the comparison function in -O2 mode.
I'm ranting about patch #5 being 101 insertions(+), 10 deletions(-) and patch #4 being 119 insertions(+), 23 deletions(-), while doing exactly the same thing.
And yes, this copy of binary search routine probably won't ever change. But changes to the comparator logic are pretty much possible, if we decide to include 'kind' as a secondary key one day. And that change will have to happen twice.
Quoted 5 lines
As I said, once binary search (of whatever kind, bounds or exact) is written for something like this, it doesn't have to ever be modified. I don't see this as a maintainability hurdle at all. But sharing code between libbpf and kernel is something to be avoided. Look at #ifdef
__KERNEL__sections ofrelo_core.cas one reason why.
Re: [RFC PATCH v4 1/7] libbpf: Extract BTF type remapping logic into helper function
Quoted 9 lines · Eduard Zingerman
On Wed, 2025-11-05 at 10:20 -0800, Andrii Nakryiko wrote:
[...]
Quoted 1 line
You don't like that I ask people to improve implementation?
Not at all.
Quoted 8 lines
Quoted 4 lines
You don't like the implementation itself? Or are you suggesting that we should add a "generic" C implementation of lower_bound/upper_bound and use callbacks for comparison logic? What are you ranting about, exactly?
Actually, having it as a static inline function in a header would be nice. I just tried that, and gcc is perfectly capable of inlining the comparison function in -O2 mode.
I dislike callbacks in principle, but I don't mind having such a reusable primitive, if it's reasonably abstracted. Do it.
Quoted 4 lines
I'm ranting about patch #5 being 101 insertions(+), 10 deletions(-) and patch #4 being 119 insertions(+), 23 deletions(-), while doing exactly the same thing.
Understandable, but code reuse is not (at least it should not be) the goal for its own sake. It should help manage complexity and improve maintainability. Code sharing is not all pros, it creates unnecessary entanglement and dependencies.
I don't think sharing this code between libbpf and kernel is justified here. 100 lines of code is not a big deal, IMO.
Quoted 11 lines
And yes, this copy of binary search routine probably won't ever change. But changes to the comparator logic are pretty much possible, if we decide to include 'kind' as a secondary key one day. And that change will have to happen twice.
Quoted 5 lines
As I said, once binary search (of whatever kind, bounds or exact) is written for something like this, it doesn't have to ever be modified. I don't see this as a maintainability hurdle at all. But sharing code between libbpf and kernel is something to be avoided. Look at #ifdef
__KERNEL__sections ofrelo_core.cas one reason why.
RFC PATCH v4 2/7 libbpf: Add BTF permutation support for type reordering
In reply to Donglin PengFrom: pengdonglin <[email protected]>
Introduce btf__permute() API to allow in-place rearrangement of BTF types. This function reorganizes BTF type order according to a provided array of type IDs, updating all type references to maintain consistency.
The permutation process involves:
1. Shuffling types into new order based on the provided ID mapping
2. Remapping all type ID references to point to new locations
3. Handling BTF extension data if provided via options
This is particularly useful for optimizing type locality after BTF deduplication or for meeting specific layout requirements in specialized use cases.
--- tools/lib/bpf/btf.c | 161 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 34 +++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 196 insertions(+)
tools/lib/bpf/btf.c +161 -0
@@ -5830,3 +5830,164 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false;return libbpf_err (err); } + +struct btf_permute { +/* .BTF section to be permuted in-place */ +struct btf *btf; +struct btf_ext *btf_ext; +/* Array of type IDs used for permutation. The array length must equal +* the number of types in the BTF being permuted, excluding the special +* void type at ID 0. For split BTF, the length corresponds to the +* number of types added on top of the base BTF. +*/ +__u32 *ids; +/* Array of type IDs used to map from original type ID to a new permuted +* type ID, its length equals to the above ids */ +__u32 *map; +}; + +static int btf_permute_shuffle_types (struct btf_permute *p); +static int btf_permute_remap_types (struct btf_permute *p); +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx); + +int btf__permute (struct btf *btf,__u32 *ids,const struct btf_permute_opts *opts) +{ +struct btf_permute p; +int i, err =0 ; +__u32 *map =NULL ; + +if (!OPTS_VALID (opts, btf_permute_opts) || !ids) +return libbpf_err (-EINVAL ); + + map =calloc (btf->nr_types,sizeof (*map)); +if (!map) { + err = -ENOMEM ; + goto done; + } + +for (i =0 ; i < btf->nr_types; i++) + map[i] =BTF_UNPROCESSED_ID ; + + p.btf = btf; + p.btf_ext =OPTS_GET (opts, btf_ext,NULL ); + p.ids = ids; + p.map = map; + +if (btf_ensure_modifiable (btf)) { + err = -ENOMEM ; + goto done; + } + err =btf_permute_shuffle_types (&p); +if (err <0 ) { +pr_debug ("btf_permute_shuffle_types failed: %s\n" ,errstr (err)); + goto done; + } + err =btf_permute_remap_types (&p); +if (err <0 ) { +pr_debug ("btf_permute_remap_types failed: %s\n" ,errstr (err)); + goto done; + } + +done: +free (map); +return libbpf_err (err); +} + +/* Shuffle BTF types. +* +* Rearranges types according to the permutation map in p->ids. The p->map +* array stores the mapping from original type IDs to new shuffled IDs, +* which is used in the next phase to update type references. +* +* Validates that all IDs in the permutation array are valid and unique. +*/ +static int btf_permute_shuffle_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +const struct btf_type *t; +__u32 *new_offs =NULL , *map; +void *nt, *new_types =NULL ; +int i, id, len, err; + + new_offs =calloc (btf->nr_types,sizeof (*new_offs)); + new_types =calloc (btf->hdr->type_len,1 ); +if (!new_offs || !new_types) { + err = -ENOMEM ; + goto out_err; + } + + nt = new_types; +for (i =0 ; i < btf->nr_types; i++) { + id = p->ids[i]; +/* type IDs from base_btf and the VOID type are not allowed */ +if (id < btf->start_id) { + err = -EINVAL ; + goto out_err; + } +/* must be a valid type ID */ + t =btf__type_by_id (btf, id); +if (!t) { + err = -EINVAL ; + goto out_err; + } + map = &p->map[id - btf->start_id]; +/* duplicate type IDs are not allowed */ +if (*map !=BTF_UNPROCESSED_ID ) { + err = -EINVAL ; + goto out_err; + } + len =btf_type_size (t); +memcpy (nt, t, len); + new_offs[i] = nt - new_types; + *map = btf->start_id + i; + nt += len; + } + +free (btf->types_data); +free (btf->type_offs); + btf->types_data = new_types; + btf->type_offs = new_offs; +return 0 ; + +out_err: +free (new_offs); +free (new_types); +return err; +} + +/* Callback function to remap individual type ID references +* +* This callback is invoked by btf_remap_types() for each type ID reference +* found in the BTF data. It updates the reference to point to the new +* permuted type ID using the mapping table. +*/ +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; + + new_type_id = p->map[*type_id - p->btf->start_id]; +if (new_type_id >BTF_MAX_NR_TYPES ) +return -EINVAL ; + + *type_id = new_type_id; +return 0 ; +} + +/* Remap referenced type IDs into permuted type IDs. +* +* After BTF types are permuted, their final type IDs may differ from original +* ones. The map from original to a corresponding permuted type ID is stored +* in btf_permute->map and is populated during shuffle phase. During remapping +* phase we are rewriting all type IDs referenced from any BTF type (e.g., +* struct fields, func proto args, etc) to their final deduped type IDs. +*/ +static int btf_permute_remap_types (struct btf_permute *p) +{ +return btf_remap_types (p->btf, p->btf_ext, btf_permute_remap_type_id, p); +} +
tools/lib/bpf/btf.h +34 -0
@@ -273,6 +273,40 @@ LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts);*/ LIBBPF_API int btf__relocate(struct btf *btf, const struct btf *base_btf); +struct btf_permute_opts { +size_t sz; +/* optional .BTF.ext info along the main BTF info */ +struct btf_ext *btf_ext; + size_t :0; +}; +#define btf_permute_opts__last_field btf_ext + +/** +* @brief **btf__permute()** rearranges BTF types in-place according to specified mapping +* @param btf BTF object to permute +* @param ids Array defining new type order. Must contain exactly btf->nr_types elements, +* each being a valid type ID in range [btf->start_id, btf->start_id + btf->nr_types - 1] +* @param opts Optional parameters, including BTF extension data for reference updates +* @return 0 on success, negative error code on failure +* +* **btf__permute()** performs an in-place permutation of BTF types, rearranging them +* according to the order specified in @p ids array. After reordering, all type references +* within the BTF data and optional BTF extension are updated to maintain consistency. +* +* The permutation process consists of two phases: +* 1. Type shuffling: Physical reordering of type data in memory +* 2. Reference remapping: Updating all type ID references to new locations +* +* This is particularly useful for optimizing type locality after BTF deduplication +* or for meeting specific layout requirements in specialized use cases. +* +* On error, negative error code is returned and errno is set appropriately. +* Common error codes include: +* - -EINVAL: Invalid parameters or invalid ID mapping (e.g., duplicate IDs, out-of-range IDs) +* - -ENOMEM: Memory allocation failure during permutation process +*/ +LIBBPF_API int btf__permute(struct btf *btf, __u32 *ids, const struct btf_permute_opts *opts); +struct btf_dump ;struct btf_dump_opts {
tools/lib/bpf/libbpf.map +1 -0
@@ -451,4 +451,5 @@ LIBBPF_1.7.0 { global: bpf_map__set_exclusive_program; bpf_map__exclusive_program; + btf__permute; } LIBBPF_1.6.0;
Signature · 1 line
2.34.1
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
Quoted 15 lines · Donglin Peng
From: pengdonglin <[email protected]>
Introduce
btf__permute()API to allow in-place rearrangement of BTF types. This function reorganizes BTF type order according to a provided array of type IDs, updating all type references to maintain consistency.The permutation process involves:
1. Shuffling types into new order based on the provided ID mapping
2. Remapping all type ID references to point to new locations
3. Handling BTF extension data if provided via optionsThis is particularly useful for optimizing type locality after BTF deduplication or for meeting specific layout requirements in specialized use cases.
Quoted 7 lines
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>
[...]
Quoted 19 lines
tools/lib/bpf/btf.h +13
-0@@ -273,6 +273,40 @@ LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts);*/ LIBBPF_API int btf__relocate(struct btf *btf, const struct btf *base_btf); +struct btf_permute_opts { +size_t sz; +/* optional .BTF.ext info along the main BTF info */ +struct btf_ext *btf_ext; + size_t :0; +}; +#define btf_permute_opts__last_field btf_ext + +/** +* @brief **btf__permute()** rearranges BTF types in-place according to specified mapping +* @param btf BTF object to permute +* @param ids Array defining new type order. Must contain exactly btf->nr_types elements, +* each being a valid type ID in range [btf->start_id, btf->start_id + btf->nr_types - 1]
tools/lib/bpf/btf.h LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts); · line 298
Quoted 10 lines
tools/lib/bpf/btf.h +10
-0+* @param opts Optional parameters, including BTF extension data for reference updates +* @return 0 on success, negative error code on failure +* +* **btf__permute()** performs an in-place permutation of BTF types, rearranging them +* according to the order specified in @p ids array. After reordering, all type references +* within the BTF data and optional BTF extension are updated to maintain consistency. +* +* The permutation process consists of two phases: +* 1. Type shuffling: Physical reordering of type data in memory +* 2. Reference remapping: Updating all type ID references to new locations
Nit: Please drop this paragraph: it is an implementation detail, not
user-facing behavior, and it is obvious from the function code.
tools/lib/bpf/btf.h LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts); · line 301
Quoted 3 lines
tools/lib/bpf/btf.h +3
-0+* +* This is particularly useful for optimizing type locality after BTF deduplication +* or for meeting specific layout requirements in specialized use cases.
Nit: Please drop this paragraph as well.
Quoted 11 lines
tools/lib/bpf/btf.h +8
-0+* +* On error, negative error code is returned and errno is set appropriately. +* Common error codes include: +* - -EINVAL: Invalid parameters or invalid ID mapping (e.g., duplicate IDs, out-of-range IDs) +* - -ENOMEM: Memory allocation failure during permutation process +*/ +LIBBPF_API int btf__permute(struct btf *btf, __u32 *ids, const struct btf_permute_opts *opts); +struct btf_dump ;struct btf_dump_opts {
[...]
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
Quoted 53 lines · Eduard Zingerman
Quoted 15 lines · Donglin Peng
From: pengdonglin <[email protected]>
Introduce
btf__permute()API to allow in-place rearrangement of BTF types. This function reorganizes BTF type order according to a provided array of type IDs, updating all type references to maintain consistency.The permutation process involves:
1. Shuffling types into new order based on the provided ID mapping
2. Remapping all type ID references to point to new locations
3. Handling BTF extension data if provided via optionsThis is particularly useful for optimizing type locality after BTF deduplication or for meeting specific layout requirements in specialized use cases.
Quoted 7 lines
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>Acked-by Eduard Zingerman <[email protected]>[...]
Quoted 24 lines
tools/lib/bpf/btf.h +18
-0@@ -273,6 +273,40 @@ LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts);*/ LIBBPF_API int btf__relocate(struct btf *btf, const struct btf *base_btf); +struct btf_permute_opts { +size_t sz; +/* optional .BTF.ext info along the main BTF info */ +struct btf_ext *btf_ext; + size_t :0; +}; +#define btf_permute_opts__last_field btf_ext + +/** +* @brief **btf__permute()** rearranges BTF types in-place according to specified mapping +* @param btf BTF object to permute +* @param ids Array defining new type order. Must contain exactly btf->nr_types elements, +* each being a valid type ID in range [btf->start_id, btf->start_id + btf->nr_types - 1] +* @param opts Optional parameters, including BTF extension data for reference updates +* @return 0 on success, negative error code on failure +* +* **btf__permute()** performs an in-place permutation of BTF types, rearranging them +* according to the order specified in @p ids array. After reordering, all type references
Quoted 8 lines
tools/lib/bpf/btf.h LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts); · line 298
Quoted 5 lines
tools/lib/bpf/btf.h +5
-0+* within the BTF data and optional BTF extension are updated to maintain consistency. +* +* The permutation process consists of two phases: +* 1. Type shuffling: Physical reordering of type data in memory +* 2. Reference remapping: Updating all type ID references to new locations Nit: Please drop this paragraph: it is an implementation detail, not
user-facing behavior, and it is obvious from the function code.
Thanks, I will fix it in the next version.
Quoted 6 lines
tools/lib/bpf/btf.h LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts); · line 301
Quoted 4 lines
tools/lib/bpf/btf.h +3
-0+* +* This is particularly useful for optimizing type locality after BTF deduplication +* or for meeting specific layout requirements in specialized use cases. Nit: Please drop this paragraph as well.
Thanks, I will fix it in the next version.
Quoted 14 lines
Quoted 12 lines
tools/lib/bpf/btf.h +8
-0+* +* On error, negative error code is returned and errno is set appropriately. +* Common error codes include: +* - -EINVAL: Invalid parameters or invalid ID mapping (e.g., duplicate IDs, out-of-range IDs) +* - -ENOMEM: Memory allocation failure during permutation process +*/ +LIBBPF_API int btf__permute(struct btf *btf, __u32 *ids, const struct btf_permute_opts *opts); +struct btf_dump ;struct btf_dump_opts {[...]
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
In reply to Donglin PengQuoted 34 lines · Donglin Peng
From: pengdonglin <[email protected]>
Introduce
btf__permute()API to allow in-place rearrangement of BTF types. This function reorganizes BTF type order according to a provided array of type IDs, updating all type references to maintain consistency.The permutation process involves:
1. Shuffling types into new order based on the provided ID mapping
2. Remapping all type ID references to point to new locations
3. Handling BTF extension data if provided via optionsThis is particularly useful for optimizing type locality after BTF deduplication or for meeting specific layout requirements in specialized use cases.
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 161 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 34 +++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 196 insertions(+)tools/lib/bpf/btf.c +0
-0
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5838
Quoted 9 lines
tools/lib/bpf/btf.c +6
-0@@ -5830,3 +5830,164 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false;return libbpf_err (err); } + +struct btf_permute { +/* .BTF section to be permuted in-place */ +struct btf *btf; +struct btf_ext *btf_ext; +/* Array of type IDs used for permutation. The array length must equal
/*
* Use this comment style
*/
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5841
Quoted 3 lines
tools/lib/bpf/btf.c +3
-0+* the number of types in the BTF being permuted, excluding the special +* void type at ID 0. For split BTF, the length corresponds to the +* number of types added on top of the base BTF.
many words, but what exactly ids[i] means is still not clear, actually...
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5845
Quoted 4 lines
tools/lib/bpf/btf.c +4
-0+*/ +__u32 *ids; +/* Array of type IDs used to map from original type ID to a new permuted +* type ID, its length equals to the above ids */
wrong comment style
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5846
Quoted 1 line
tools/lib/bpf/btf.c +1
-0+__u32 *map;
"map" is a bit generic. What if we use s/ids/id_map/ and s/map/id_map_rev/ (for reverse)? I'd use "id_map" naming in the public API to make it clear that it's a mapping of IDs, not just some array of IDs.
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5853
Quoted 7 lines
tools/lib/bpf/btf.c +7
-0+}; + +static int btf_permute_shuffle_types (struct btf_permute *p); +static int btf_permute_remap_types (struct btf_permute *p); +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx); + +int btf__permute (struct btf *btf,__u32 *ids,const struct btf_permute_opts *opts)
Let's require user to pass id_map_cnt in addition to id_map itself. It's easy to get this wrong (especially with that special VOID 0 type that has to be excluded, which I can't even make up my mind if that's a good idea or not), so having user explicitly say what they think is necessary for permutation is good.
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5859
Quoted 6 lines
tools/lib/bpf/btf.c +6
-0+{ +struct btf_permute p; +int i, err =0 ; +__u32 *map =NULL ; + +if (!OPTS_VALID (opts, btf_permute_opts) || !ids)
libbpf doesn't protect against NULL passed for mandatory parameters, please drop !ids check
Quoted 13 lines
tools/lib/bpf/btf.c +13
-0+return libbpf_err (-EINVAL ); + + map =calloc (btf->nr_types,sizeof (*map)); +if (!map) { + err = -ENOMEM ; + goto done; + } + +for (i =0 ; i < btf->nr_types; i++) + map[i] =BTF_UNPROCESSED_ID ; + + p.btf = btf; + p.btf_ext =OPTS_GET (opts, btf_ext,NULL );
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5882
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ p.ids = ids; + p.map = map; + +if (btf_ensure_modifiable (btf)) { + err = -ENOMEM ; + goto done; + } + err =btf_permute_shuffle_types (&p); +if (err <0 ) { +pr_debug ("btf_permute_shuffle_types failed: %s\n" ,errstr (err));
let's drop these pr_debug(), I don't think it's something we expect to ever see
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5887
Quoted 5 lines
tools/lib/bpf/btf.c +5
-0+ goto done; + } + err =btf_permute_remap_types (&p); +if (err <0 ) { +pr_debug ("btf_permute_remap_types failed: %s\n" ,errstr (err));
ditto
Quoted 15 lines
tools/lib/bpf/btf.c +15
-0+ goto done; + } + +done: +free (map); +return libbpf_err (err); +} + +/* Shuffle BTF types. +* +* Rearranges types according to the permutation map in p->ids. The p->map +* array stores the mapping from original type IDs to new shuffled IDs, +* which is used in the next phase to update type references. +* +* Validates that all IDs in the permutation array are valid and unique.
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5912
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+*/ +static int btf_permute_shuffle_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +const struct btf_type *t; +__u32 *new_offs =NULL , *map; +void *nt, *new_types =NULL ; +int i, id, len, err; + + new_offs =calloc (btf->nr_types,sizeof (*new_offs));
we don't really need to allocate memory and maintain this, we can just shift types around and then do what btf_parse_type_sec() does -- just go over types one by one and calculate offsets, and update them in-place inside btf->type_offs
Quoted 13 lines
tools/lib/bpf/btf.c +13
-0+ new_types =calloc (btf->hdr->type_len,1 ); +if (!new_offs || !new_types) { + err = -ENOMEM ; + goto out_err; + } + + nt = new_types; +for (i =0 ; i < btf->nr_types; i++) { + id = p->ids[i]; +/* type IDs from base_btf and the VOID type are not allowed */ +if (id < btf->start_id) { + err = -EINVAL ; + goto out_err;
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5935
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ } +/* must be a valid type ID */ + t =btf__type_by_id (btf, id); +if (!t) { + err = -EINVAL ; + goto out_err; + } + map = &p->map[id - btf->start_id]; +/* duplicate type IDs are not allowed */ +if (*map !=BTF_UNPROCESSED_ID ) {
there is no need for BTF_UNPROCESSED_ID, zero is a perfectly valid value to use as "not yet set" value, as we don't allow remapping VOID 0 to anything anyways.
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5940
Quoted 5 lines
tools/lib/bpf/btf.c +5
-0+ err = -EINVAL ; + goto out_err; + } + len =btf_type_size (t); +memcpy (nt, t, len);
once you memcpy() data, you can use that btf_field_iter_init + btf_field_iter_next to *trivially* remap all IDs, no need for patch 1 refactoring, IMO. And no need for two-phase approach either.
Quoted 23 lines
tools/lib/bpf/btf.c +23
-0+ new_offs[i] = nt - new_types; + *map = btf->start_id + i; + nt += len; + } + +free (btf->types_data); +free (btf->type_offs); + btf->types_data = new_types; + btf->type_offs = new_offs; +return 0 ; + +out_err: +free (new_offs); +free (new_types); +return err; +} + +/* Callback function to remap individual type ID references +* +* This callback is invoked by btf_remap_types() for each type ID reference +* found in the BTF data. It updates the reference to point to the new +* permuted type ID using the mapping table. +*/
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5973
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; + + new_type_id = p->map[*type_id - p->btf->start_id];
I'm actually confused, I thought p->ids would be the mapping from original type ID (minus start_id, of course) to a new desired ID, but it looks to be the other way? ids is a desired resulting *sequence* of types identified by their original ID. I find it quite confusing. I think about permutation as a mapping from original type ID to a new type ID, am I confused?
Quoted 6 lines
tools/lib/bpf/btf.c +6
-0+if (new_type_id >BTF_MAX_NR_TYPES ) +return -EINVAL ; + + *type_id = new_type_id; +return 0 ; +}
[...]
Eduard Zingerman
maintainerRe: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 9 lines
Quoted 9 lines
tools/lib/bpf/btf.c +9
-0+static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; +
Quoted 8 lines
Quoted 1 line
+
new_type_id= p->map[*type_id -p->btf->start_id];I'm actually confused, I thought
p->idswould be the mapping from original type ID (minusstart_id, of course) to a new desired ID, but it looks to be the other way? ids is a desired resulting *sequence* of types identified by their original ID. I find it quite confusing. I think about permutation as a mapping from original type ID to a new type ID, am I confused?
Yes, it is a desired sequence, not mapping.
I guess its a bit simpler to use for sorting use-case, as you can just swap ids while sorting.
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
Quoted 23 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 9 lines
Quoted 9 lines
tools/lib/bpf/btf.c +9
-0+static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; +Quoted 8 lines
Quoted 1 line
+
new_type_id= p->map[*type_id -p->btf->start_id];I'm actually confused, I thought
p->idswould be the mapping from original type ID (minusstart_id, of course) to a new desired ID, but it looks to be the other way? ids is a desired resulting *sequence* of types identified by their original ID. I find it quite confusing. I think about permutation as a mapping from original type ID to a new type ID, am I confused?
Quoted 3 lines
Yes, it is a desired sequence, not mapping.
I guess its a bit simpler to use for sorting use-case, as you can just swap ids while sorting.
The question is really what makes most sense as an interface. Because for sorting cases it's just the matter of a two-line for() loop to create ID mapping once types are sorted.
I have slight preference for id_map approach because it is easy to extend to the case of selectively dropping some types. We can just define that such IDs should be mapped to zero. This will work as a natural extension. With the desired end sequence of IDs, it's less natural and will require more work to determine which IDs are missing from the sequence.
So unless there is some really good and strong reason, shall we go with the ID mapping approach?
Eduard Zingerman
maintainerRe: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
Quoted 39 lines · Andrii Nakryiko
Quoted 23 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 9 lines
Quoted 9 lines
tools/lib/bpf/btf.c +9
-0+static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; +Quoted 8 lines
Quoted 1 line
+
new_type_id= p->map[*type_id -p->btf->start_id];I'm actually confused, I thought
p->idswould be the mapping from original type ID (minusstart_id, of course) to a new desired ID, but it looks to be the other way? ids is a desired resulting *sequence* of types identified by their original ID. I find it quite confusing. I think about permutation as a mapping from original type ID to a new type ID, am I confused?Quoted 3 lines
Yes, it is a desired sequence, not mapping.
I guess its a bit simpler to use for sorting use-case, as you can just swap ids while sorting.The question is really what makes most sense as an interface. Because for sorting cases it's just the matter of a two-line
for()loop to create ID mapping once types are sorted.I have slight preference for
id_mapapproach because it is easy to extend to the case of selectively dropping some types. We can just define that such IDs should be mapped to zero. This will work as a natural extension. With the desired end sequence of IDs, it's less natural and will require more work to determine which IDs are missing from the sequence.
Quoted 2 lines
So unless there is some really good and strong reason, shall we go with the ID mapping approach?
If the interface is extended with types_cnt, as you suggest, deleting types is trivial with sequence interface as well. At-least the way it is implemented by this patch, you just copy elements from 'ids' one by one.
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
Quoted 41 lines · Eduard Zingerman
Quoted 39 lines · Andrii Nakryiko
Quoted 23 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 9 lines
Quoted 9 lines
tools/lib/bpf/btf.c +9
-0+static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; +Quoted 8 lines
Quoted 1 line
+
new_type_id= p->map[*type_id -p->btf->start_id];I'm actually confused, I thought
p->idswould be the mapping from original type ID (minusstart_id, of course) to a new desired ID, but it looks to be the other way? ids is a desired resulting *sequence* of types identified by their original ID. I find it quite confusing. I think about permutation as a mapping from original type ID to a new type ID, am I confused?Quoted 3 lines
Yes, it is a desired sequence, not mapping.
I guess its a bit simpler to use for sorting use-case, as you can just swap ids while sorting.The question is really what makes most sense as an interface. Because for sorting cases it's just the matter of a two-line
for()loop to create ID mapping once types are sorted.I have slight preference for
id_mapapproach because it is easy to extend to the case of selectively dropping some types. We can just define that such IDs should be mapped to zero. This will work as a natural extension. With the desired end sequence of IDs, it's less natural and will require more work to determine which IDs are missing from the sequence.
Quoted 7 lines
Quoted 2 lines
So unless there is some really good and strong reason, shall we go with the ID mapping approach?
If the interface is extended with
types_cnt, as you suggest, deleting types is trivial with sequence interface as well. At-least the way it is implemented by this patch, you just copy elements from 'ids' one by one.
Thank you. I also favor the sequence interface approach. if I understand correctly, using the ID mapping method would require creating an additional ID array to cache the ordering for each type, which appears more complex. Furthermore, generating an ID map might not be straightforward for end users in the sorting scenario, IMO.
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
Quoted 51 lines · Donglin Peng
Quoted 41 lines · Eduard Zingerman
Quoted 39 lines · Andrii Nakryiko
Quoted 23 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 9 lines
Quoted 9 lines
tools/lib/bpf/btf.c +9
-0+static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; +Quoted 8 lines
Quoted 1 line
+
new_type_id= p->map[*type_id -p->btf->start_id];I'm actually confused, I thought
p->idswould be the mapping from original type ID (minusstart_id, of course) to a new desired ID, but it looks to be the other way? ids is a desired resulting *sequence* of types identified by their original ID. I find it quite confusing. I think about permutation as a mapping from original type ID to a new type ID, am I confused?Quoted 3 lines
Yes, it is a desired sequence, not mapping.
I guess its a bit simpler to use for sorting use-case, as you can just swap ids while sorting.The question is really what makes most sense as an interface. Because for sorting cases it's just the matter of a two-line
for()loop to create ID mapping once types are sorted.I have slight preference for
id_mapapproach because it is easy to extend to the case of selectively dropping some types. We can just define that such IDs should be mapped to zero. This will work as a natural extension. With the desired end sequence of IDs, it's less natural and will require more work to determine which IDs are missing from the sequence.Quoted 7 lines
Quoted 2 lines
So unless there is some really good and strong reason, shall we go with the ID mapping approach?
If the interface is extended with
types_cnt, as you suggest, deleting types is trivial with sequence interface as well. At-least the way it is implemented by this patch, you just copy elements from 'ids' one by one.
Quoted 5 lines
Thank you. I also favor the sequence interface approach. if I understand correctly, using the ID mapping method would require creating an additional ID array to cache the ordering for each type, which appears more complex. Furthermore, generating an ID map might not be straightforward for end users in the sorting scenario, IMO.
Additional array on user side or inside libbpf's implementation? But even if on the user side, a few temporary extra kilobytes to sort BTF doesn't seem like a big limitation (definitely not for pahole, for example).
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
In reply to Eduard ZingermanQuoted 41 lines · Eduard Zingerman
Quoted 39 lines · Andrii Nakryiko
Quoted 23 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 9 lines
Quoted 9 lines
tools/lib/bpf/btf.c +9
-0+static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; +Quoted 8 lines
Quoted 1 line
+
new_type_id= p->map[*type_id -p->btf->start_id];I'm actually confused, I thought
p->idswould be the mapping from original type ID (minusstart_id, of course) to a new desired ID, but it looks to be the other way? ids is a desired resulting *sequence* of types identified by their original ID. I find it quite confusing. I think about permutation as a mapping from original type ID to a new type ID, am I confused?Quoted 3 lines
Yes, it is a desired sequence, not mapping.
I guess its a bit simpler to use for sorting use-case, as you can just swap ids while sorting.The question is really what makes most sense as an interface. Because for sorting cases it's just the matter of a two-line
for()loop to create ID mapping once types are sorted.I have slight preference for
id_mapapproach because it is easy to extend to the case of selectively dropping some types. We can just define that such IDs should be mapped to zero. This will work as a natural extension. With the desired end sequence of IDs, it's less natural and will require more work to determine which IDs are missing from the sequence.
Quoted 7 lines
Quoted 2 lines
So unless there is some really good and strong reason, shall we go with the ID mapping approach?
If the interface is extended with
types_cnt, as you suggest, deleting types is trivial with sequence interface as well. At-least the way it is implemented by this patch, you just copy elements from 'ids' one by one.
But it is way less explicit and obvious way to delete element. With ID map it is obvious, that type will be mapped to zero. With list of IDs, you effectively search for elements that are missing, which IMO is way less optimal an interface.
So I still favor the ID map approach.
Eduard Zingerman
maintainerRe: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
Quoted 50 lines · Andrii Nakryiko
Quoted 41 lines · Eduard Zingerman
Quoted 39 lines · Andrii Nakryiko
Quoted 23 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 9 lines
Quoted 9 lines
tools/lib/bpf/btf.c +9
-0+static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; +Quoted 8 lines
Quoted 1 line
+
new_type_id= p->map[*type_id -p->btf->start_id];I'm actually confused, I thought
p->idswould be the mapping from original type ID (minusstart_id, of course) to a new desired ID, but it looks to be the other way? ids is a desired resulting *sequence* of types identified by their original ID. I find it quite confusing. I think about permutation as a mapping from original type ID to a new type ID, am I confused?Quoted 3 lines
Yes, it is a desired sequence, not mapping.
I guess its a bit simpler to use for sorting use-case, as you can just swap ids while sorting.The question is really what makes most sense as an interface. Because for sorting cases it's just the matter of a two-line
for()loop to create ID mapping once types are sorted.I have slight preference for
id_mapapproach because it is easy to extend to the case of selectively dropping some types. We can just define that such IDs should be mapped to zero. This will work as a natural extension. With the desired end sequence of IDs, it's less natural and will require more work to determine which IDs are missing from the sequence.Quoted 7 lines
Quoted 2 lines
So unless there is some really good and strong reason, shall we go with the ID mapping approach?
If the interface is extended with
types_cnt, as you suggest, deleting types is trivial with sequence interface as well. At-least the way it is implemented by this patch, you just copy elements from 'ids' one by one.
Quoted 6 lines
But it is way less explicit and obvious way to delete element. With ID map it is obvious, that type will be mapped to zero. With list of IDs, you effectively search for elements that are missing, which IMO is way less optimal an interface.
So I still favor the ID map approach.
You don't need to search for deleted elements with current implementation (assuming the ids_cnt parameter is added). Suppose there are 4 types + void in BTF and the 'ids' sequence looks as follows: {1, 3, 4}, current implementation will:
- iterate over 'ids':
- copy 1 to new_types, remember to remap 1 to 1
- copy 3 to new_types, remember to remap 3 to 2
- copy 4 to new_types, remember to remap 4 to 3
- do the remapping.
Consider the sorting use-case:
- If 'ids' is the desired final order of types, libbpf needs to allocate the mapping from old id to new id, as described above.
- If 'ids' is a map from old id to new id:
- libbpf will have to allocate a temporary array to hold the desired
id sequence, to know in which order to copy the types;
- user will have to allocate the array for mapping.
So, for id map approach it is one more allocation for no benefit.
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
Quoted 59 lines · Eduard Zingerman
Quoted 50 lines · Andrii Nakryiko
Quoted 41 lines · Eduard Zingerman
Quoted 39 lines · Andrii Nakryiko
Quoted 23 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 9 lines
Quoted 9 lines
(quoted diff) +9
-0+static int btf_permute_remap_type_id(__u32 *type_id, void *ctx) +{ + struct btf_permute *p = ctx; + __u32 new_type_id = *type_id; + + /* skip references that point into the base BTF */ + if (new_type_id < p->btf->start_id) + return 0; +Quoted 8 lines
Quoted 1 line
+
new_type_id= p->map[*type_id -p->btf->start_id];I'm actually confused, I thought
p->idswould be the mapping from original type ID (minusstart_id, of course) to a new desired ID, but it looks to be the other way? ids is a desired resulting *sequence* of types identified by their original ID. I find it quite confusing. I think about permutation as a mapping from original type ID to a new type ID, am I confused?Quoted 3 lines
Yes, it is a desired sequence, not mapping.
I guess its a bit simpler to use for sorting use-case, as you can just swap ids while sorting.The question is really what makes most sense as an interface. Because for sorting cases it's just the matter of a two-line
for()loop to create ID mapping once types are sorted.I have slight preference for
id_mapapproach because it is easy to extend to the case of selectively dropping some types. We can just define that such IDs should be mapped to zero. This will work as a natural extension. With the desired end sequence of IDs, it's less natural and will require more work to determine which IDs are missing from the sequence.Quoted 7 lines
Quoted 2 lines
So unless there is some really good and strong reason, shall we go with the ID mapping approach?
If the interface is extended with
types_cnt, as you suggest, deleting types is trivial with sequence interface as well. At-least the way it is implemented by this patch, you just copy elements from 'ids' one by one.Quoted 6 lines
But it is way less explicit and obvious way to delete element. With ID map it is obvious, that type will be mapped to zero. With list of IDs, you effectively search for elements that are missing, which IMO is way less optimal an interface.
So I still favor the ID map approach.
Quoted 9 lines
You don't need to search for deleted elements with current implementation (assuming the
ids_cntparameter is added). Suppose there are 4 types + void in BTF and the 'ids' sequence looks as follows: {1, 3, 4}, current implementation will:
- iterate over 'ids':
- copy 1 tonew_types, remember to remap 1 to 1
- copy 3 tonew_types, remember to remap 3 to 2
- copy 4 tonew_types, remember to remap 4 to 3
- do the remapping.
Eduard, from API perspective I very much do not like saying that "if type ID is missing from the list -- drop it". I very much prefer "map type you want to delete to zero". How can I be more clear about this? I didn't even talk about implementation, I was talking about API.
Quoted 10 lines
Consider the sorting use-case:
- If 'ids' is the desired final order of types, libbpf needs to allocate the mapping from old id to new id, as described above.
- If 'ids' is a map from old id to new id:
- libbpf will have to allocate a temporary array to hold the desiredid sequence, to know in which order to copy the types;- user will have to allocate the array for mapping.
So, for id map approach it is one more allocation for no benefit.
On the libbpf side - no difference in terms of memory use. On the user side, worst case, N * sizeof(int) temporary allocation for ID mapping. 400KB at most to resort 100K of BTF types, which takes megabytes anyways. I don't even want to talk about the amount of memory pahole will waste on DWARF information processing. And depending on what data structures user code keeps for sorting indexing, this allocation might be necessary anyways with either approach.
But this is all irrelevant. I care about the interface way more than temporary 400KB of memory usage.
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
In reply to Andrii NakryikoQuoted 51 lines · Andrii Nakryiko
Quoted 41 lines · Eduard Zingerman
Quoted 39 lines · Andrii Nakryiko
Quoted 23 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 9 lines
Quoted 9 lines
tools/lib/bpf/btf.c +9
-0+static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; +Quoted 8 lines
Quoted 1 line
+
new_type_id= p->map[*type_id -p->btf->start_id];I'm actually confused, I thought
p->idswould be the mapping from original type ID (minusstart_id, of course) to a new desired ID, but it looks to be the other way? ids is a desired resulting *sequence* of types identified by their original ID. I find it quite confusing. I think about permutation as a mapping from original type ID to a new type ID, am I confused?Quoted 3 lines
Yes, it is a desired sequence, not mapping.
I guess its a bit simpler to use for sorting use-case, as you can just swap ids while sorting.The question is really what makes most sense as an interface. Because for sorting cases it's just the matter of a two-line
for()loop to create ID mapping once types are sorted.I have slight preference for
id_mapapproach because it is easy to extend to the case of selectively dropping some types. We can just define that such IDs should be mapped to zero. This will work as a natural extension. With the desired end sequence of IDs, it's less natural and will require more work to determine which IDs are missing from the sequence.Quoted 7 lines
Quoted 2 lines
So unless there is some really good and strong reason, shall we go with the ID mapping approach?
If the interface is extended with
types_cnt, as you suggest, deleting types is trivial with sequence interface as well. At-least the way it is implemented by this patch, you just copy elements from 'ids' one by one.
Quoted 6 lines
But it is way less explicit and obvious way to delete element. With ID map it is obvious, that type will be mapped to zero. With list of IDs, you effectively search for elements that are missing, which IMO is way less optimal an interface.
So I still favor the ID map approach.
Hi Andrii,
I've submitted v5 implementing the sequence-based approach, and I plan to introduce
the ID map approach in v6. However, I have a few remaining questions that need clarification:
1. ID Map Array Semantics:
- When the ID map array specifies [2] = 4, does this indicate
that the original type
at start_id + 2 should be remapped to position start_id + 4?
Should the following
mapping attempts be rejected:
a) If the target index 4 exceeds the total number of types (nr_types)?
b) If multiple source types map to the same target location
(e.g., both [1] = 3
and `[2] = 3`)?
- If [3] = 0, does this indicate that the type at start_id + 3 should be dropped?
- Does this also imply that the VOID type (ID 0) cannot be remapped and must always remain unchanged?
2. ID Map Array Size:
- Must the ID map array size <= the number of BTF types? If the array is smaller, should any missing types be automatically dropped?
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
Quoted 68 lines · Donglin Peng
Quoted 51 lines · Andrii Nakryiko
Quoted 41 lines · Eduard Zingerman
Quoted 39 lines · Andrii Nakryiko
Quoted 23 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 9 lines
Quoted 9 lines
(quoted diff) +9
-0+static int btf_permute_remap_type_id(__u32 *type_id, void *ctx) +{ + struct btf_permute *p = ctx; + __u32 new_type_id = *type_id; + + /* skip references that point into the base BTF */ + if (new_type_id < p->btf->start_id) + return 0; +Quoted 8 lines
Quoted 1 line
+
new_type_id= p->map[*type_id -p->btf->start_id];I'm actually confused, I thought
p->idswould be the mapping from original type ID (minusstart_id, of course) to a new desired ID, but it looks to be the other way? ids is a desired resulting *sequence* of types identified by their original ID. I find it quite confusing. I think about permutation as a mapping from original type ID to a new type ID, am I confused?Quoted 3 lines
Yes, it is a desired sequence, not mapping.
I guess its a bit simpler to use for sorting use-case, as you can just swap ids while sorting.The question is really what makes most sense as an interface. Because for sorting cases it's just the matter of a two-line
for()loop to create ID mapping once types are sorted.I have slight preference for
id_mapapproach because it is easy to extend to the case of selectively dropping some types. We can just define that such IDs should be mapped to zero. This will work as a natural extension. With the desired end sequence of IDs, it's less natural and will require more work to determine which IDs are missing from the sequence.Quoted 7 lines
Quoted 2 lines
So unless there is some really good and strong reason, shall we go with the ID mapping approach?
If the interface is extended with
types_cnt, as you suggest, deleting types is trivial with sequence interface as well. At-least the way it is implemented by this patch, you just copy elements from 'ids' one by one.Quoted 6 lines
But it is way less explicit and obvious way to delete element. With ID map it is obvious, that type will be mapped to zero. With list of IDs, you effectively search for elements that are missing, which IMO is way less optimal an interface.
So I still favor the ID map approach.
Hi Andrii,
I've submitted v5 implementing the sequence-based approach, and I plan to introduce
the ID map approach in v6. However, I have a few remaining questions that need clarification:
Quoted 5 lines
1. ID Map Array Semantics:
- When the ID map array specifies
[2] = 4, does this indicate
that the original type
atstart_id + 2should be remapped to positionstart_id + 4?
I'd say that 4 should be "absolute type ID" for simplicity. Because that's what users work with. I'd say the position ([2]) should also map to type ID for non-split case. So for base BTF I'd require [0]=0, i.e., id_map count should be btf__type_cnt() sized. (I can be convinced that's wrong and inconvenient) For split BTF the situation is of course more complicated, because requiring btf__type_cnt()-sized array for just split BTF would be super wasteful. So for split BTF [2] would be as you say 3rd type within split BTF, that is type #(btf__start_id() + 2), yes.
Quoted 3 lines
Should the following
mapping attempts be rejected:
a) If the target index4exceeds the total number of types (nr_types)?
yes
Quoted 3 lines
b) If multiple source types map to the same target location
(e.g., both[1] = 3and `[2] = 3`)?
yes (at least for now, we can lift this if we ever have a good reason by adding some option)
Quoted 3 lines
- If [3] = 0, does this indicate that the type at
start_id+ 3 should be dropped?
yes, but let's not worry about deletion right now and just reject this. I'd like to keep this option for the future, but right now we should reject such case.
Quoted 3 lines
- Does this also imply that the VOID type (ID 0) cannot be remapped and must always remain unchanged?
yes, it must be always be zero, it's baked into BTF
Quoted 6 lines
2. ID Map Array Size:
- Must the ID map array size <= the number of BTF types? If the array is smaller, should any missing types be automatically dropped?
no, it's an error, id_map size should match the number of types. For base it should be btf__type_cnt(), for split BTF it should be btf__type_cnt() - btf__type_cnt(btf__base_btf(split_btf)). (That's one of the reasons I think we should have [0] = 0 for base, to keep this consistent).
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
In reply to Andrii NakryikoQuoted 41 lines · Andrii Nakryiko
Quoted 39 lines · Donglin Peng
From: pengdonglin <[email protected]>
Introduce
btf__permute()API to allow in-place rearrangement of BTF types. This function reorganizes BTF type order according to a provided array of type IDs, updating all type references to maintain consistency.The permutation process involves:
1. Shuffling types into new order based on the provided ID mapping
2. Remapping all type ID references to point to new locations
3. Handling BTF extension data if provided via optionsThis is particularly useful for optimizing type locality after BTF deduplication or for meeting specific layout requirements in specialized use cases.
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 161 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 34 +++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 196 insertions(+)tools/lib/bpf/btf.c +2
-0@@ -5830,3 +5830,164 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false;return libbpf_err (err); } + +struct btf_permute {
Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5838
Quoted 4 lines
tools/lib/bpf/btf.c +4
-0+/* .BTF section to be permuted in-place */ +struct btf *btf; +struct btf_ext *btf_ext; +/* Array of type IDs used for permutation. The array length must equal /*
* Use this comment style
*/
Thanks.
Quoted 6 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5841
Quoted 4 lines
tools/lib/bpf/btf.c +3
-0+* the number of types in the BTF being permuted, excluding the special +* void type at ID 0. For split BTF, the length corresponds to the +* number of types added on top of the base BTF. many words, but what exactly ids[i] means is still not clear, actually...
Thanks. I'll clarify the description. Is the following parameter explanation acceptable?
@param ids Array containing original type IDs (excluding VOID type ID
0) in user-defined order.
The array size must match btf->nr_types, which
also excludes VOID type ID 0.
Quoted 7 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5845
Quoted 5 lines
tools/lib/bpf/btf.c +4
-0+*/ +__u32 *ids; +/* Array of type IDs used to map from original type ID to a new permuted +* type ID, its length equals to the above ids */ wrong comment style
Thanks, I will fix it in the next version.
Quoted 7 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5846
Quoted 2 lines
tools/lib/bpf/btf.c +1
-0+__u32 *map;"map" is a bit generic. What if we use s/ids/id_map/ and s/map/id_map_rev/ (for reverse)? I'd use "
id_map" naming in the public API to make it clear that it's a mapping of IDs, not just some array of IDs.
Thank you for the suggestion. While I agree that renaming 'map' to 'id_map' makes sense for clarity, but 'ids' seems correct as it denotes a collection of IDs, not a mapping structure.
Quoted 14 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5853
Quoted 8 lines
tools/lib/bpf/btf.c +7
-0+}; + +static int btf_permute_shuffle_types (struct btf_permute *p); +static int btf_permute_remap_types (struct btf_permute *p); +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx); + +int btf__permute (struct btf *btf,__u32 *ids,const struct btf_permute_opts *opts)Let's require user to pass
id_map_cntin addition toid_mapitself. It's easy to get this wrong (especially with that special VOID 0 type that has to be excluded, which I can't even make up my mind if that's a good idea or not), so having user explicitly say what they think is necessary for permutation is good.
Thank you for your suggestion. However, I am concerned that introducing an additional id_map_cnt parameter could increase complexity. Specifically, if id_map_cnt is less than btf->nr_types, we might need to consider whether to resize the BTF. This could lead to missing types, potential ID remapping failures, or even require BTF re-deduplication if certain name strings are no longer referenced by any types.
Quoted 10 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5859
Quoted 7 lines
tools/lib/bpf/btf.c +6
-0+{ +struct btf_permute p; +int i, err =0 ; +__u32 *map =NULL ; + +if (!OPTS_VALID (opts, btf_permute_opts) || !ids)libbpf doesn't protect against NULL passed for mandatory parameters, please drop !ids check
Thanks, I will fix it.
Quoted 18 lines
Quoted 18 lines
tools/lib/bpf/btf.c +17
-0+return libbpf_err (-EINVAL ); + + map =calloc (btf->nr_types,sizeof (*map)); +if (!map) { + err = -ENOMEM ; + goto done; + } + +for (i =0 ; i < btf->nr_types; i++) + map[i] =BTF_UNPROCESSED_ID ; + + p.btf = btf; + p.btf_ext =OPTS_GET (opts, btf_ext,NULL ); + p.ids = ids; + p.map = map; + +if (btf_ensure_modifiable (btf)) {
Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5882
Quoted 6 lines
tools/lib/bpf/btf.c +6
-0+ err = -ENOMEM ; + goto done; + } + err =btf_permute_shuffle_types (&p); +if (err <0 ) { +pr_debug ("btf_permute_shuffle_types failed: %s\n" ,errstr (err));let's drop these
pr_debug(), I don't think it's something we expect to ever see
Thanks, I will remove it.
Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5887
Quoted 6 lines
tools/lib/bpf/btf.c +5
-0+ goto done; + } + err =btf_permute_remap_types (&p); +if (err <0 ) { +pr_debug ("btf_permute_remap_types failed: %s\n" ,errstr (err));ditto
Thanks, I will remove it.
Quoted 23 lines
Quoted 23 lines
tools/lib/bpf/btf.c +22
-0+ goto done; + } + +done: +free (map); +return libbpf_err (err); +} + +/* Shuffle BTF types. +* +* Rearranges types according to the permutation map in p->ids. The p->map +* array stores the mapping from original type IDs to new shuffled IDs, +* which is used in the next phase to update type references. +* +* Validates that all IDs in the permutation array are valid and unique. +*/ +static int btf_permute_shuffle_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +const struct btf_type *t; +__u32 *new_offs =NULL , *map; +void *nt, *new_types =NULL ;
Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5912
Quoted 3 lines
tools/lib/bpf/btf.c +3
-0+int i, id, len, err; + + new_offs =calloc (btf->nr_types,sizeof (*new_offs));we don't really need to allocate memory and maintain this, we can just shift types around and then do what
btf_parse_type_sec()does -- just go over types one by one and calculate offsets, and update them in-place insidebtf->type_offs
Thank you for the suggestion. However, this approach is not viable because the btf__type_by_id() function relies critically on the integrity of the btf->type_offs data structure. Attempting to modify type_offs through in-place operations could corrupt memory and lead to segmentation faults due to invalid pointer dereferencing.
Quoted 25 lines
Quoted 14 lines
tools/lib/bpf/btf.c +13
-0+ new_types =calloc (btf->hdr->type_len,1 ); +if (!new_offs || !new_types) { + err = -ENOMEM ; + goto out_err; + } + + nt = new_types; +for (i =0 ; i < btf->nr_types; i++) { + id = p->ids[i]; +/* type IDs from base_btf and the VOID type are not allowed */ +if (id < btf->start_id) { + err = -EINVAL ; + goto out_err;tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5935
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ } +/* must be a valid type ID */ + t =btf__type_by_id (btf, id); +if (!t) { + err = -EINVAL ; + goto out_err; + } + map = &p->map[id - btf->start_id]; +/* duplicate type IDs are not allowed */ +if (*map !=BTF_UNPROCESSED_ID ) {
Quoted 3 lines
there is no need for
BTF_UNPROCESSED_ID, zero is a perfectly valid value to use as "not yet set" value, as we don't allow remapping VOID 0 to anything anyways.
Thanks, I will fix it.
Quoted 61 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5940
Quoted 6 lines
tools/lib/bpf/btf.c +5
-0+ err = -EINVAL ; + goto out_err; + } + len =btf_type_size (t); +memcpy (nt, t, len);once you
memcpy()data, you can use thatbtf_field_iter_init+btf_field_iter_nextto *trivially* remap all IDs, no need for patch 1 refactoring, IMO. And no need for two-phase approach either.Quoted 23 lines
tools/lib/bpf/btf.c +23
-0+ new_offs[i] = nt - new_types; + *map = btf->start_id + i; + nt += len; + } + +free (btf->types_data); +free (btf->type_offs); + btf->types_data = new_types; + btf->type_offs = new_offs; +return 0 ; + +out_err: +free (new_offs); +free (new_types); +return err; +} + +/* Callback function to remap individual type ID references +* +* This callback is invoked by btf_remap_types() for each type ID reference +* found in the BTF data. It updates the reference to point to the new +* permuted type ID using the mapping table. +*/ tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5973
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; + + new_type_id = p->map[*type_id - p->btf->start_id];I'm actually confused, I thought
p->idswould be the mapping from original type ID (minusstart_id, of course) to a new desired ID, but it looks to be the other way? ids is a desired resulting *sequence* of types identified by their original ID. I find it quite confusing. I think about permutation as a mapping from original type ID to a new type ID, am I confused?Quoted 6 lines
tools/lib/bpf/btf.c +6
-0+if (new_type_id >BTF_MAX_NR_TYPES ) +return -EINVAL ; + + *type_id = new_type_id; +return 0 ; +}[...]
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
Quoted 60 lines · Donglin Peng
Quoted 41 lines · Andrii Nakryiko
Quoted 39 lines · Donglin Peng
From: pengdonglin <[email protected]>
Introduce
btf__permute()API to allow in-place rearrangement of BTF types. This function reorganizes BTF type order according to a provided array of type IDs, updating all type references to maintain consistency.The permutation process involves:
1. Shuffling types into new order based on the provided ID mapping
2. Remapping all type ID references to point to new locations
3. Handling BTF extension data if provided via optionsThis is particularly useful for optimizing type locality after BTF deduplication or for meeting specific layout requirements in specialized use cases.
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 161 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 34 +++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 196 insertions(+)tools/lib/bpf/btf.c +2
-0@@ -5830,3 +5830,164 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false;return libbpf_err (err); } + +struct btf_permute {Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5838
Quoted 4 lines
tools/lib/bpf/btf.c +4
-0+/* .BTF section to be permuted in-place */ +struct btf *btf; +struct btf_ext *btf_ext; +/* Array of type IDs used for permutation. The array length must equal /*
* Use this comment style
*/Thanks.
Quoted 5 lines
Quoted 4 lines
tools/lib/bpf/btf.c +3
-0+* the number of types in the BTF being permuted, excluding the special +* void type at ID 0. For split BTF, the length corresponds to the +* number of types added on top of the base BTF.
Quoted 8 lines
Quoted 1 line
many words, but what exactly ids[i] means is still not clear, actually...
Thanks. I'll clarify the description. Is the following parameter explanation acceptable?
@param ids Array containing original type IDs (excluding VOID type ID
0) in user-defined order.The array size must match btf->nr_types, which
Users don't have access to btf->nr_types, so referring to it in API description seems wrong.
But also, this all will change if we allow removing types, because then array size might be smaller. But is it intentionally smaller or user made a mistake? Let's go with the ID map approach, please.
Quoted 40 lines
also excludes VOID type ID 0.
Quoted 7 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5845
Quoted 5 lines
tools/lib/bpf/btf.c +4
-0+*/ +__u32 *ids; +/* Array of type IDs used to map from original type ID to a new permuted +* type ID, its length equals to the above ids */ wrong comment style
Thanks, I will fix it in the next version.
Quoted 7 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5846
Quoted 2 lines
tools/lib/bpf/btf.c +1
-0+__u32 *map;"map" is a bit generic. What if we use s/ids/id_map/ and s/map/id_map_rev/ (for reverse)? I'd use "
id_map" naming in the public API to make it clear that it's a mapping of IDs, not just some array of IDs.Thank you for the suggestion. While I agree that renaming 'map' to '
id_map' makes sense for clarity, but 'ids' seems correct as it denotes a collection of IDs, not a mapping structure.Quoted 14 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5853
Quoted 8 lines
tools/lib/bpf/btf.c +7
-0+}; + +static int btf_permute_shuffle_types (struct btf_permute *p); +static int btf_permute_remap_types (struct btf_permute *p); +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx); + +int btf__permute (struct btf *btf,__u32 *ids,const struct btf_permute_opts *opts)Let's require user to pass
id_map_cntin addition toid_mapitself. It's easy to get this wrong (especially with that special VOID 0 type that has to be excluded, which I can't even make up my mind if that's a good idea or not), so having user explicitly say what they think is necessary for permutation is good.
Quoted 7 lines
Thank you for your suggestion. However, I am concerned that introducing an additional
id_map_cntparameter could increase complexity. Specifically, ifid_map_cntis less thanbtf->nr_types, we might need to consider whether to resize the BTF. This could lead to missing types, potential ID remapping failures, or even require BTF re-deduplication if certain name strings are no longer referenced by any types.
No, if the user provided a wrong id_map_cnt, it's an error and we return -EINVAL. No resizing.
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
tools/lib/bpf/btf.c +6
-0+{ +struct btf_permute p; +int i, err =0 ; +__u32 *map =NULL ; + +if (!OPTS_VALID (opts, btf_permute_opts) || !ids)
[...]
Quoted 31 lines
Quoted 22 lines
Quoted 22 lines
tools/lib/bpf/btf.c +22
-0+ goto done; + } + +done: +free (map); +return libbpf_err (err); +} + +/* Shuffle BTF types. +* +* Rearranges types according to the permutation map in p->ids. The p->map +* array stores the mapping from original type IDs to new shuffled IDs, +* which is used in the next phase to update type references. +* +* Validates that all IDs in the permutation array are valid and unique. +*/ +static int btf_permute_shuffle_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +const struct btf_type *t; +__u32 *new_offs =NULL , *map; +void *nt, *new_types =NULL ;Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5912
Quoted 3 lines
tools/lib/bpf/btf.c +3
-0+int i, id, len, err; + + new_offs =calloc (btf->nr_types,sizeof (*new_offs));we don't really need to allocate memory and maintain this, we can just shift types around and then do what
btf_parse_type_sec()does -- just go over types one by one and calculate offsets, and update them in-place insidebtf->type_offs
Quoted 5 lines
Thank you for the suggestion. However, this approach is not viable because the
btf__type_by_id()function relies critically on the integrity of thebtf->type_offsdata structure. Attempting to modifytype_offsthrough in-place operations could corrupt memory and lead to segmentation faults due to invalid pointer dereferencing.
Huh? By the time this API returns, we'll fix up type_offs, users will never notice. And to recalculate new type_offs we don't need type_offs. One of us is missing something important, what is it?
[...]
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
Quoted 71 lines · Andrii Nakryiko
Quoted 60 lines · Donglin Peng
Quoted 41 lines · Andrii Nakryiko
Quoted 39 lines · Donglin Peng
From: pengdonglin <[email protected]>
Introduce
btf__permute()API to allow in-place rearrangement of BTF types. This function reorganizes BTF type order according to a provided array of type IDs, updating all type references to maintain consistency.The permutation process involves:
1. Shuffling types into new order based on the provided ID mapping
2. Remapping all type ID references to point to new locations
3. Handling BTF extension data if provided via optionsThis is particularly useful for optimizing type locality after BTF deduplication or for meeting specific layout requirements in specialized use cases.
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 161 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 34 +++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 196 insertions(+)tools/lib/bpf/btf.c +2
-0@@ -5830,3 +5830,164 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false;return libbpf_err (err); } + +struct btf_permute {Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5838
Quoted 4 lines
tools/lib/bpf/btf.c +4
-0+/* .BTF section to be permuted in-place */ +struct btf *btf; +struct btf_ext *btf_ext; +/* Array of type IDs used for permutation. The array length must equal /*
* Use this comment style
*/Thanks.
Quoted 5 lines
Quoted 4 lines
tools/lib/bpf/btf.c +3
-0+* the number of types in the BTF being permuted, excluding the special +* void type at ID 0. For split BTF, the length corresponds to the +* number of types added on top of the base BTF. Quoted 8 lines
Quoted 1 line
many words, but what exactly ids[i] means is still not clear, actually...
Thanks. I'll clarify the description. Is the following parameter explanation acceptable?
@param ids Array containing original type IDs (excluding VOID type ID
0) in user-defined order.The array size must match btf->nr_types, which
Quoted 6 lines
Users don't have access to
btf->nr_types, so referring to it in API description seems wrong.But also, this all will change if we allow removing types, because then array size might be smaller. But is it intentionally smaller or user made a mistake? Let's go with the ID map approach, please.
Thanks. I can implement both approaches, then we can assess their pros and cons.
Quoted 100 lines
Quoted 41 lines
also excludes VOID type ID 0.
Quoted 7 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5845
Quoted 5 lines
tools/lib/bpf/btf.c +4
-0+*/ +__u32 *ids; +/* Array of type IDs used to map from original type ID to a new permuted +* type ID, its length equals to the above ids */ wrong comment style
Thanks, I will fix it in the next version.
Quoted 7 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5846
Quoted 2 lines
tools/lib/bpf/btf.c +1
-0+__u32 *map;"map" is a bit generic. What if we use s/ids/id_map/ and s/map/id_map_rev/ (for reverse)? I'd use "
id_map" naming in the public API to make it clear that it's a mapping of IDs, not just some array of IDs.Thank you for the suggestion. While I agree that renaming 'map' to '
id_map' makes sense for clarity, but 'ids' seems correct as it denotes a collection of IDs, not a mapping structure.Quoted 14 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5853
Quoted 8 lines
tools/lib/bpf/btf.c +7
-0+}; + +static int btf_permute_shuffle_types (struct btf_permute *p); +static int btf_permute_remap_types (struct btf_permute *p); +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx); + +int btf__permute (struct btf *btf,__u32 *ids,const struct btf_permute_opts *opts)Let's require user to pass
id_map_cntin addition toid_mapitself. It's easy to get this wrong (especially with that special VOID 0 type that has to be excluded, which I can't even make up my mind if that's a good idea or not), so having user explicitly say what they think is necessary for permutation is good.Quoted 7 lines
Thank you for your suggestion. However, I am concerned that introducing an additional
id_map_cntparameter could increase complexity. Specifically, ifid_map_cntis less thanbtf->nr_types, we might need to consider whether to resize the BTF. This could lead to missing types, potential ID remapping failures, or even require BTF re-deduplication if certain name strings are no longer referenced by any types.No, if the user provided a wrong
id_map_cnt, it's an error and we return-EINVAL. No resizing.Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
tools/lib/bpf/btf.c +6
-0+{ +struct btf_permute p; +int i, err =0 ; +__u32 *map =NULL ; + +if (!OPTS_VALID (opts, btf_permute_opts) || !ids)[...]
Quoted 31 lines
Quoted 22 lines
Quoted 22 lines
tools/lib/bpf/btf.c +22
-0+ goto done; + } + +done: +free (map); +return libbpf_err (err); +} + +/* Shuffle BTF types. +* +* Rearranges types according to the permutation map in p->ids. The p->map +* array stores the mapping from original type IDs to new shuffled IDs, +* which is used in the next phase to update type references. +* +* Validates that all IDs in the permutation array are valid and unique. +*/ +static int btf_permute_shuffle_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +const struct btf_type *t; +__u32 *new_offs =NULL , *map; +void *nt, *new_types =NULL ;Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5912
Quoted 3 lines
tools/lib/bpf/btf.c +3
-0+int i, id, len, err; + + new_offs =calloc (btf->nr_types,sizeof (*new_offs));we don't really need to allocate memory and maintain this, we can just shift types around and then do what
btf_parse_type_sec()does -- just go over types one by one and calculate offsets, and update them in-place insidebtf->type_offsQuoted 5 lines
Thank you for the suggestion. However, this approach is not viable because the
btf__type_by_id()function relies critically on the integrity of thebtf->type_offsdata structure. Attempting to modifytype_offsthrough in-place operations could corrupt memory and lead to segmentation faults due to invalid pointer dereferencing.
Quoted 3 lines
Huh? By the time this API returns, we'll fix up
type_offs, users will never notice. And to recalculate newtype_offswe don't needtype_offs. One of us is missing something important, what is it?
Thanks, however the bad news is that the btf__type_by_id is indeed called within the API.
static int btf_permute_shuffle_types(struct btf_permute *p)
{
struct btf *btf = p->btf;
const struct btf_type *t;
__u32 *new_offs = NULL, *ids_map;
void *nt, *new_types = NULL;
int i, id, len, err;
new_offs = calloc(btf->nr_types, sizeof(*new_offs));
new_types = calloc(btf->hdr->type_len, 1);
......
nt = new_types;
for (i = 0; i < btf->nr_types; i++) {
id = p->ids[i];
......
/* must be a valid type ID */
t = btf__type_by_id(btf, id); <<<<<<<<<<<<<
......
len = btf_type_size(t);
memcpy(nt, t, len);
new_offs[i] = nt - new_types;
*ids_map = btf->start_id + i;
nt += len;
}......
}
Quoted 2 lines
[...]
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
Quoted 192 lines · Donglin Peng
Quoted 71 lines · Andrii Nakryiko
Quoted 60 lines · Donglin Peng
Quoted 41 lines · Andrii Nakryiko
Quoted 39 lines · Donglin Peng
From: pengdonglin <[email protected]>
Introduce
btf__permute()API to allow in-place rearrangement of BTF types. This function reorganizes BTF type order according to a provided array of type IDs, updating all type references to maintain consistency.The permutation process involves:
1. Shuffling types into new order based on the provided ID mapping
2. Remapping all type ID references to point to new locations
3. Handling BTF extension data if provided via optionsThis is particularly useful for optimizing type locality after BTF deduplication or for meeting specific layout requirements in specialized use cases.
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 161 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 34 +++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 196 insertions(+)tools/lib/bpf/btf.c +2
-0@@ -5830,3 +5830,164 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false;return libbpf_err (err); } + +struct btf_permute {Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5838
Quoted 4 lines
tools/lib/bpf/btf.c +4
-0+/* .BTF section to be permuted in-place */ +struct btf *btf; +struct btf_ext *btf_ext; +/* Array of type IDs used for permutation. The array length must equal /*
* Use this comment style
*/Thanks.
Quoted 5 lines
Quoted 4 lines
tools/lib/bpf/btf.c +3
-0+* the number of types in the BTF being permuted, excluding the special +* void type at ID 0. For split BTF, the length corresponds to the +* number of types added on top of the base BTF. Quoted 8 lines
Quoted 1 line
many words, but what exactly ids[i] means is still not clear, actually...
Thanks. I'll clarify the description. Is the following parameter explanation acceptable?
@param ids Array containing original type IDs (excluding VOID type ID
0) in user-defined order.The array size must match btf->nr_types, whichQuoted 6 lines
Users don't have access to
btf->nr_types, so referring to it in API description seems wrong.But also, this all will change if we allow removing types, because then array size might be smaller. But is it intentionally smaller or user made a mistake? Let's go with the ID map approach, please.
Thanks. I can implement both approaches, then we can assess their pros and cons.
Quoted 100 lines
Quoted 41 lines
also excludes VOID type ID 0.
Quoted 7 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5845
Quoted 5 lines
tools/lib/bpf/btf.c +4
-0+*/ +__u32 *ids; +/* Array of type IDs used to map from original type ID to a new permuted +* type ID, its length equals to the above ids */ wrong comment style
Thanks, I will fix it in the next version.
Quoted 7 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5846
Quoted 2 lines
tools/lib/bpf/btf.c +1
-0+__u32 *map;"map" is a bit generic. What if we use s/ids/id_map/ and s/map/id_map_rev/ (for reverse)? I'd use "
id_map" naming in the public API to make it clear that it's a mapping of IDs, not just some array of IDs.Thank you for the suggestion. While I agree that renaming 'map' to '
id_map' makes sense for clarity, but 'ids' seems correct as it denotes a collection of IDs, not a mapping structure.Quoted 14 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5853
Quoted 8 lines
tools/lib/bpf/btf.c +7
-0+}; + +static int btf_permute_shuffle_types (struct btf_permute *p); +static int btf_permute_remap_types (struct btf_permute *p); +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx); + +int btf__permute (struct btf *btf,__u32 *ids,const struct btf_permute_opts *opts)Let's require user to pass
id_map_cntin addition toid_mapitself. It's easy to get this wrong (especially with that special VOID 0 type that has to be excluded, which I can't even make up my mind if that's a good idea or not), so having user explicitly say what they think is necessary for permutation is good.Quoted 7 lines
Thank you for your suggestion. However, I am concerned that introducing an additional
id_map_cntparameter could increase complexity. Specifically, ifid_map_cntis less thanbtf->nr_types, we might need to consider whether to resize the BTF. This could lead to missing types, potential ID remapping failures, or even require BTF re-deduplication if certain name strings are no longer referenced by any types.No, if the user provided a wrong
id_map_cnt, it's an error and we return-EINVAL. No resizing.Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
tools/lib/bpf/btf.c +6
-0+{ +struct btf_permute p; +int i, err =0 ; +__u32 *map =NULL ; + +if (!OPTS_VALID (opts, btf_permute_opts) || !ids)[...]
Quoted 31 lines
Quoted 22 lines
Quoted 22 lines
tools/lib/bpf/btf.c +22
-0+ goto done; + } + +done: +free (map); +return libbpf_err (err); +} + +/* Shuffle BTF types. +* +* Rearranges types according to the permutation map in p->ids. The p->map +* array stores the mapping from original type IDs to new shuffled IDs, +* which is used in the next phase to update type references. +* +* Validates that all IDs in the permutation array are valid and unique. +*/ +static int btf_permute_shuffle_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +const struct btf_type *t; +__u32 *new_offs =NULL , *map; +void *nt, *new_types =NULL ;Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5912
Quoted 3 lines
tools/lib/bpf/btf.c +3
-0+int i, id, len, err; + + new_offs =calloc (btf->nr_types,sizeof (*new_offs));we don't really need to allocate memory and maintain this, we can just shift types around and then do what
btf_parse_type_sec()does -- just go over types one by one and calculate offsets, and update them in-place insidebtf->type_offsQuoted 5 lines
Thank you for the suggestion. However, this approach is not viable because the
btf__type_by_id()function relies critically on the integrity of thebtf->type_offsdata structure. Attempting to modifytype_offsthrough in-place operations could corrupt memory and lead to segmentation faults due to invalid pointer dereferencing.Quoted 3 lines
Huh? By the time this API returns, we'll fix up
type_offs, users will never notice. And to recalculate newtype_offswe don't needtype_offs. One of us is missing something important, what is it?Thanks, however the bad news is that the
btf__type_by_idis indeed called within the API.static int
btf_permute_shuffle_types(struct btf_permute *p)
Quoted 16 lines
{
struct btf *btf = p->btf;
const struct btf_type *t;
__u32 *new_offs = NULL, *ids_map;
void *nt, *new_types = NULL;
int i, id, len, err;
new_offs = calloc(btf->nr_types, sizeof(*new_offs));
new_types = calloc(btf->hdr->type_len, 1);
......
nt = new_types;
for (i = 0; i < btf->nr_types; i++) {
id = p->ids[i];
......
/* must be a valid type ID */
t = btf__type_by_id(btf, id); <<<<<<<<<<<<<You are still on the old types layout and old type_offs at that point. You are not using your new_offs here *anyways*
Quoted 8 lines
...... len = btf_type_size(t); memcpy(nt, t, len); new_offs[i] = nt - new_types; *ids_map = btf->start_id + i; nt += len; }......
... you will recalculate and update type_offs here ... well past btf__type_by_id() usage ...
Quoted 4 lines
}
Quoted 2 lines
[...]
Re: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
Quoted 223 lines · Andrii Nakryiko
Quoted 192 lines · Donglin Peng
Quoted 71 lines · Andrii Nakryiko
Quoted 60 lines · Donglin Peng
Quoted 41 lines · Andrii Nakryiko
Quoted 39 lines · Donglin Peng
From: pengdonglin <[email protected]>
Introduce
btf__permute()API to allow in-place rearrangement of BTF types. This function reorganizes BTF type order according to a provided array of type IDs, updating all type references to maintain consistency.The permutation process involves:
1. Shuffling types into new order based on the provided ID mapping
2. Remapping all type ID references to point to new locations
3. Handling BTF extension data if provided via optionsThis is particularly useful for optimizing type locality after BTF deduplication or for meeting specific layout requirements in specialized use cases.
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 161 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 34 +++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 196 insertions(+)tools/lib/bpf/btf.c +2
-0@@ -5830,3 +5830,164 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false;return libbpf_err (err); } + +struct btf_permute {Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5838
Quoted 4 lines
tools/lib/bpf/btf.c +4
-0+/* .BTF section to be permuted in-place */ +struct btf *btf; +struct btf_ext *btf_ext; +/* Array of type IDs used for permutation. The array length must equal /*
* Use this comment style
*/Thanks.
Quoted 5 lines
Quoted 4 lines
tools/lib/bpf/btf.c +3
-0+* the number of types in the BTF being permuted, excluding the special +* void type at ID 0. For split BTF, the length corresponds to the +* number of types added on top of the base BTF. Quoted 8 lines
Quoted 1 line
many words, but what exactly ids[i] means is still not clear, actually...
Thanks. I'll clarify the description. Is the following parameter explanation acceptable?
@param ids Array containing original type IDs (excluding VOID type ID
0) in user-defined order.The array size must match btf->nr_types, whichQuoted 6 lines
Users don't have access to
btf->nr_types, so referring to it in API description seems wrong.But also, this all will change if we allow removing types, because then array size might be smaller. But is it intentionally smaller or user made a mistake? Let's go with the ID map approach, please.
Thanks. I can implement both approaches, then we can assess their pros and cons.
Quoted 100 lines
Quoted 41 lines
also excludes VOID type ID 0.
Quoted 7 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5845
Quoted 5 lines
tools/lib/bpf/btf.c +4
-0+*/ +__u32 *ids; +/* Array of type IDs used to map from original type ID to a new permuted +* type ID, its length equals to the above ids */ wrong comment style
Thanks, I will fix it in the next version.
Quoted 7 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5846
Quoted 2 lines
tools/lib/bpf/btf.c +1
-0+__u32 *map;"map" is a bit generic. What if we use s/ids/id_map/ and s/map/id_map_rev/ (for reverse)? I'd use "
id_map" naming in the public API to make it clear that it's a mapping of IDs, not just some array of IDs.Thank you for the suggestion. While I agree that renaming 'map' to '
id_map' makes sense for clarity, but 'ids' seems correct as it denotes a collection of IDs, not a mapping structure.Quoted 14 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5853
Quoted 8 lines
tools/lib/bpf/btf.c +7
-0+}; + +static int btf_permute_shuffle_types (struct btf_permute *p); +static int btf_permute_remap_types (struct btf_permute *p); +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx); + +int btf__permute (struct btf *btf,__u32 *ids,const struct btf_permute_opts *opts)Let's require user to pass
id_map_cntin addition toid_mapitself. It's easy to get this wrong (especially with that special VOID 0 type that has to be excluded, which I can't even make up my mind if that's a good idea or not), so having user explicitly say what they think is necessary for permutation is good.Quoted 7 lines
Thank you for your suggestion. However, I am concerned that introducing an additional
id_map_cntparameter could increase complexity. Specifically, ifid_map_cntis less thanbtf->nr_types, we might need to consider whether to resize the BTF. This could lead to missing types, potential ID remapping failures, or even require BTF re-deduplication if certain name strings are no longer referenced by any types.No, if the user provided a wrong
id_map_cnt, it's an error and we return-EINVAL. No resizing.Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
tools/lib/bpf/btf.c +6
-0+{ +struct btf_permute p; +int i, err =0 ; +__u32 *map =NULL ; + +if (!OPTS_VALID (opts, btf_permute_opts) || !ids)[...]
Quoted 31 lines
Quoted 22 lines
Quoted 22 lines
tools/lib/bpf/btf.c +22
-0+ goto done; + } + +done: +free (map); +return libbpf_err (err); +} + +/* Shuffle BTF types. +* +* Rearranges types according to the permutation map in p->ids. The p->map +* array stores the mapping from original type IDs to new shuffled IDs, +* which is used in the next phase to update type references. +* +* Validates that all IDs in the permutation array are valid and unique. +*/ +static int btf_permute_shuffle_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +const struct btf_type *t; +__u32 *new_offs =NULL , *map; +void *nt, *new_types =NULL ;Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5912
Quoted 3 lines
tools/lib/bpf/btf.c +3
-0+int i, id, len, err; + + new_offs =calloc (btf->nr_types,sizeof (*new_offs));we don't really need to allocate memory and maintain this, we can just shift types around and then do what
btf_parse_type_sec()does -- just go over types one by one and calculate offsets, and update them in-place insidebtf->type_offsQuoted 5 lines
Thank you for the suggestion. However, this approach is not viable because the
btf__type_by_id()function relies critically on the integrity of thebtf->type_offsdata structure. Attempting to modifytype_offsthrough in-place operations could corrupt memory and lead to segmentation faults due to invalid pointer dereferencing.Quoted 3 lines
Huh? By the time this API returns, we'll fix up
type_offs, users will never notice. And to recalculate newtype_offswe don't needtype_offs. One of us is missing something important, what is it?Thanks, however the bad news is that the
btf__type_by_idis indeed called within the API.static int
btf_permute_shuffle_types(struct btf_permute *p)Quoted 16 lines
{ struct btf *btf = p->btf; const struct btf_type *t; __u32 *new_offs = NULL, *ids_map; void *nt, *new_types = NULL; int i, id, len, err; new_offs = calloc(btf->nr_types, sizeof(*new_offs)); new_types = calloc(btf->hdr->type_len, 1); ...... nt = new_types; for (i = 0; i < btf->nr_types; i++) { id = p->ids[i]; ...... /* must be a valid type ID */ t = btf__type_by_id(btf, id); <<<<<<<<<<<<<You are still on the old types layout and old
type_offsat that point. You are not using yournew_offshere *anyways*Quoted 8 lines
...... len = btf_type_size(t); memcpy(nt, t, len); new_offs[i] = nt - new_types; *ids_map = btf->start_id + i; nt += len; }......
Quoted 2 lines
... you will recalculate and update
type_offshere ... well pastbtf__type_by_id()usage ...
Thanks, I see. We need to add another for loop for this update, but the cost is minimal compared to the memory savings. I will fix it in v6.
Quoted 5 lines
Quoted 5 lines
}
Quoted 2 lines
[...]
RFC PATCH v4 3/7 libbpf: Optimize type lookup with binary search for sorted BTF
In reply to Donglin PengFrom: pengdonglin <[email protected]>
This patch introduces binary search optimization for BTF type lookups when the BTF instance contains sorted types.
The optimization significantly improves performance when searching for types in large BTF instances with sorted type names. For unsorted BTF or when nr_sorted_types is zero, the implementation falls back to the original linear search algorithm.
--- tools/lib/bpf/btf.c | 142 +++++++++++++++++++++++++++++++++++++------- 1 file changed, 119 insertions(+), 23 deletions(-)
tools/lib/bpf/btf.c +119 -23
@@ -92,6 +92,12 @@ struct btf {* - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; +/* number of sorted and named types in this BTF instance: +* - doesn't include special [0] void type; +* - for split BTF counts number of sorted and named types added on +* top of base BTF. +*/ +__u32 nr_sorted_types;/* if not NULL, points to the base BTF on top of which the current * split BTF is based */
@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; } -__s32 btf__find_by_name (const struct btf *btf,const char *type_name) +/* +* Find BTF types with matching names within the [left, right] index range. +* On success, updates *left and *right to the boundaries of the matching range +* and returns the leftmost matching index. +*/ +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name, +__s32 *left,__s32 *right) { -__u32 i, nr_types =btf__type_cnt (btf); +const struct btf_type *t; +const char *tname; +__s32 l, r, m, lmost, rmost; +int ret; + +/* found the leftmost btf_type that matches */ + l = *left; + r = *right; + lmost =-1 ; +while (l <= r) { + m = l + (r - l) /2 ; + t =btf_type_by_id (btf, m); + tname =btf__str_by_offset (btf, t->name_off); + ret =strcmp (tname, name); +if (ret <0 ) { + l = m +1 ; + }else { +if (ret ==0 ) + lmost = m; + r = m -1 ; + } + } -if (!strcmp (type_name,"void" )) -return 0 ; +if (lmost ==-1 ) +return -ENOENT ; + +/* found the rightmost btf_type that matches */ + l = lmost; + r = *right; + rmost =-1 ; +while (l <= r) { + m = l + (r - l) /2 ; + t =btf_type_by_id (btf, m); + tname =btf__str_by_offset (btf, t->name_off); + ret =strcmp (tname, name); +if (ret <=0 ) { +if (ret ==0 ) + rmost = m; + l = m +1 ; + }else { + r = m -1 ; + } + } -for (i =1 ; i < nr_types; i++) { -const struct btf_type *t =btf__type_by_id (btf, i); -const char *name =btf__name_by_offset (btf, t->name_off); + *left = lmost; + *right = rmost; +return lmost; +} + +static __s32 btf_find_type_by_name_kind (const struct btf *btf,int start_id, +const char *type_name,__u32 kind) +{ +const struct btf_type *t; +const char *tname; +int err = -ENOENT ; -if (name && !strcmp (type_name, name)) -return i; +if (!btf) + goto out; + +if (start_id < btf->start_id) { + err =btf_find_type_by_name_kind (btf->base_btf, start_id, + type_name, kind); +if (err == -ENOENT ) + start_id = btf->start_id; + } + +if (err == -ENOENT ) { +if (btf->nr_sorted_types) { +/* binary search */ +__s32 l, r; +int ret; + + l = start_id; + r = start_id + btf->nr_sorted_types -1 ; + ret =btf_find_type_by_name_bsearch (btf, type_name, &l, &r); +if (ret <0 ) + goto out; +/* return the leftmost with maching names and skip kind checking */ +if (kind ==-1 ) +return ret; +/* found the leftmost btf_type that matches */ +while (l <= r) { + t =btf_type_by_id (btf, l); +if (BTF_INFO_KIND (t->info) == kind) +return l; + l++; + } + }else { +/* linear search */ +__u32 i, total; + + total =btf__type_cnt (btf); +for (i = start_id; i < total; i++) { + t =btf_type_by_id (btf, i); +if (kind !=-1 &&btf_kind (t) != kind) +continue ; + tname =btf__str_by_offset (btf, t->name_off); +if (tname && !strcmp (tname, type_name)) +return i; + } + } } -return libbpf_err (-ENOENT ); +out: +return err; }static __s32 btf_find_by_name_kind (const struct btf *btf,int start_id,const char *type_name,__u32 kind) { -__u32 i, nr_types =btf__type_cnt (btf); -if (kind ==BTF_KIND_UNKN || !strcmp (type_name,"void" ))return 0 ; -for (i = start_id; i < nr_types; i++) { -const struct btf_type *t =btf__type_by_id (btf, i); -const char *name; - -if (btf_kind (t) != kind) -continue ; - name =btf__name_by_offset (btf, t->name_off); -if (name && !strcmp (type_name, name)) -return i; - } +return libbpf_err (btf_find_type_by_name_kind (btf, start_id, type_name, kind)); +} -return libbpf_err (-ENOENT ); +/* the kind value of -1 indicates that kind matching should be skipped */ +__s32 btf__find_by_name (const struct btf *btf,const char *type_name) +{ +return btf_find_by_name_kind (btf, btf->start_id, type_name,-1 ); } __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
Signature · 1 line
2.34.1
[email protected]
AI reviewRe: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
Where is this field initialized? I searched the entire codebase and found no assignments to nr_sorted_types. Since struct btf is allocated with calloc() in btf__new() and other allocation functions…
Quoted 5 lines
tools/lib/bpf/btf.c +0
-0
tools/lib/bpf/btf.c struct btf { · line 100
Quoted 9 lines
tools/lib/bpf/btf.c +6
-0@@ -92,6 +92,12 @@ struct btf {* - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; +/* number of sorted and named types in this BTF instance: +* - doesn't include special [0] void type; +* - for split BTF counts number of sorted and named types added on +* top of base BTF. +*/ +__u32 nr_sorted_types;
Where is this field initialized? I searched the entire codebase and found no assignments to nr_sorted_types. Since struct btf is allocated with calloc() in btf__new() and other allocation functions, this field will always be zero.
This means the binary search optimization added below will never execute because the check at btf_find_type_by_name_kind() tests:
if (btf->nr_sorted_types) {
/* binary search */
...
}With nr_sorted_types always zero, the optimization appears to be completely non-functional in this commit.
Quoted 3 lines
tools/lib/bpf/btf.c +0
-0/* if not NULL, points to the base BTF on top of which the current * split BTF is based */
[ ... ]
Quoted 18 lines
tools/lib/bpf/btf.c +11
-2@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; } -__s32 btf__find_by_name (const struct btf *btf,const char *type_name) +/* +* Find BTF types with matching names within the [left, right] index range. +* On success, updates *left and *right to the boundaries of the matching range +* and returns the leftmost matching index. +*/ +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name, +__s32 *left,__s32 *right) { -__u32 i, nr_types =btf__type_cnt (btf); +const struct btf_type *t; +const char *tname; +__s32 l, r, m, lmost, rmost; +int ret;
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 927
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ +/* found the leftmost btf_type that matches */ + l = *left; + r = *right; + lmost =-1 ; +while (l <= r) { + m = l + (r - l) /2 ; + t =btf_type_by_id (btf, m); + tname =btf__str_by_offset (btf, t->name_off); + ret =strcmp (tname, name);
Can strcmp() crash with a NULL tname here? btf__str_by_offset() can return NULL when offset is invalid (see line 1713 in btf.c). The old code had a NULL check: "if (name && !strcmp(type_name, name))" and the new linear search path also checks: "if (tname && !strcmp(tname, type_name))", but this binary search path calls strcmp() directly.
Though currently unreachable due to nr_sorted_types being zero, if that initialization issue is fixed, this could dereference NULL.
Quoted 11 lines
tools/lib/bpf/btf.c +11
-0+if (ret <0 ) { + l = m +1 ; + }else { +if (ret ==0 ) + lmost = m; + r = m -1 ; + } + } + +if (lmost ==-1 ) +return -ENOENT ;
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 948
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ +/* found the rightmost btf_type that matches */ + l = lmost; + r = *right; + rmost =-1 ; +while (l <= r) { + m = l + (r - l) /2 ; + t =btf_type_by_id (btf, m); + tname =btf__str_by_offset (btf, t->name_off); + ret =strcmp (tname, name);
Same potential NULL dereference issue here.
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 978
Quoted 13 lines
tools/lib/bpf/btf.c +13
-0+if (ret <=0 ) { +if (ret ==0 ) + rmost = m; + l = m +1 ; + }else { + r = m -1 ; + } + } + + *left = lmost; + *right = rmost; +return lmost; +}
[ ... ]
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/19070905166
Eduard Zingerman
maintainerRe: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
In reply to Donglin PengQuoted 10 lines · Donglin Peng
From: pengdonglin <[email protected]>
This patch introduces binary search optimization for BTF type lookups when the BTF instance contains sorted types.
The optimization significantly improves performance when searching for types in large BTF instances with sorted type names. For unsorted BTF or when
nr_sorted_typesis zero, the implementation falls back to the original linear search algorithm.
Quoted 8 lines
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>---
lgtm, have two nits.
Quoted 8 lines
tools/lib/bpf/btf.c | 142 +++++++++++++++++++++++++++++++++++++------- 1 file changed, 119 insertions(+), 23 deletions(-)tools/lib/bpf/btf.c +0
-0
tools/lib/bpf/btf.c struct btf { · line 100
Quoted 9 lines
tools/lib/bpf/btf.c +6
-0@@ -92,6 +92,12 @@ struct btf {* - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; +/* number of sorted and named types in this BTF instance: +* - doesn't include special [0] void type; +* - for split BTF counts number of sorted and named types added on +* top of base BTF. +*/ +__u32 nr_sorted_types;
Silly question: why is this __u32 and not just a flag?
Quoted 29 lines
tools/lib/bpf/btf.c +19
-2/* if not NULL, points to the base BTF on top of which the current * split BTF is based */ @@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; } -__s32 btf__find_by_name (const struct btf *btf,const char *type_name) +/* +* Find BTF types with matching names within the [left, right] index range. +* On success, updates *left and *right to the boundaries of the matching range +* and returns the leftmost matching index. +*/ +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name, +__s32 *left,__s32 *right) { -__u32 i, nr_types =btf__type_cnt (btf); +const struct btf_type *t; +const char *tname; +__s32 l, r, m, lmost, rmost; +int ret; + +/* found the leftmost btf_type that matches */ + l = *left; + r = *right; + lmost =-1 ; +while (l <= r) { + m = l + (r - l) /2 ; + t =btf_type_by_id (btf, m);
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 935
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ tname =btf__str_by_offset (btf, t->name_off); + ret =strcmp (tname, name); +if (ret <0 ) { + l = m +1 ; + }else { +if (ret ==0 ) + lmost = m; + r = m -1 ; + } + }
Nit: I think Andrii's point was that this can be written a tad shorter, e.g.:
https://elixir.bootlin.com/linux/v6.18-rc4/source/kernel/bpf/verifier.c#L2952
Quoted 31 lines
tools/lib/bpf/btf.c +24
-5-if (!strcmp (type_name,"void" )) -return 0 ; +if (lmost ==-1 ) +return -ENOENT ; + +/* found the rightmost btf_type that matches */ + l = lmost; + r = *right; + rmost =-1 ; +while (l <= r) { + m = l + (r - l) /2 ; + t =btf_type_by_id (btf, m); + tname =btf__str_by_offset (btf, t->name_off); + ret =strcmp (tname, name); +if (ret <=0 ) { +if (ret ==0 ) + rmost = m; + l = m +1 ; + }else { + r = m -1 ; + } + } -for (i =1 ; i < nr_types; i++) { -const struct btf_type *t =btf__type_by_id (btf, i); -const char *name =btf__name_by_offset (btf, t->name_off); + *left = lmost; + *right = rmost; +return lmost; +}
[...]
Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
In reply to Donglin PengQuoted 27 lines · Donglin Peng
From: pengdonglin <[email protected]>
This patch introduces binary search optimization for BTF type lookups when the BTF instance contains sorted types.
The optimization significantly improves performance when searching for types in large BTF instances with sorted type names. For unsorted BTF or when
nr_sorted_typesis zero, the implementation falls back to the original linear search algorithm.Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 142 +++++++++++++++++++++++++++++++++++++------- 1 file changed, 119 insertions(+), 23 deletions(-)tools/lib/bpf/btf.c +0
-0
tools/lib/bpf/btf.c struct btf { · line 100
Quoted 9 lines
tools/lib/bpf/btf.c +6
-0@@ -92,6 +92,12 @@ struct btf {* - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; +/* number of sorted and named types in this BTF instance: +* - doesn't include special [0] void type; +* - for split BTF counts number of sorted and named types added on +* top of base BTF. +*/ +__u32 nr_sorted_types;
we don't need to know the count of sorted types, all we need is a tristate value: a) data is sorted, b) data is not sorted, c) we don't know yet. And zero should be treated as "we don't know yet". This is trivial to do with an enum.
Quoted 5 lines
tools/lib/bpf/btf.c +0
-0/* if not NULL, points to the base BTF on top of which the current * split BTF is based */ @@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id;
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 912
Quoted 10 lines
tools/lib/bpf/btf.c +7
-1} -__s32 btf__find_by_name (const struct btf *btf,const char *type_name) +/* +* Find BTF types with matching names within the [left, right] index range. +* On success, updates *left and *right to the boundaries of the matching range +* and returns the leftmost matching index. +*/ +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name, +__s32 *left,__s32 *right)
I thought we discussed this, why do you need "right"? Two binary searches where one would do just fine.
Also this isn't quite the same approach as in find_linfo() in kernel/bpf/log.c, that one doesn't have extra ret == 0 condition
pw-bot: cr
Quoted 7 lines
tools/lib/bpf/btf.c +5
-1{ -__u32 i, nr_types =btf__type_cnt (btf); +const struct btf_type *t; +const char *tname; +__s32 l, r, m, lmost, rmost; +int ret; +
[...]
Eduard Zingerman
maintainerRe: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 4 lines
Quoted 4 lines
tools/lib/bpf/btf.c +0
-0@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; }
Quoted 11 lines
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 912
Quoted 8 lines
tools/lib/bpf/btf.c +7
-1-__s32 btf__find_by_name (const struct btf *btf,const char *type_name) +/* +* Find BTF types with matching names within the [left, right] index range. +* On success, updates *left and *right to the boundaries of the matching range +* and returns the leftmost matching index. +*/ +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name, +__s32 *left,__s32 *right)I thought we discussed this, why do you need "right"? Two binary searches where one would do just fine.
I think the idea is that there would be less strcmp's if there is a long sequence of items with identical names.
Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
Quoted 21 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 4 lines
Quoted 4 lines
tools/lib/bpf/btf.c +0
-0@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; }Quoted 11 lines
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 912
Quoted 8 lines
tools/lib/bpf/btf.c +7
-1-__s32 btf__find_by_name (const struct btf *btf,const char *type_name) +/* +* Find BTF types with matching names within the [left, right] index range. +* On success, updates *left and *right to the boundaries of the matching range +* and returns the leftmost matching index. +*/ +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name, +__s32 *left,__s32 *right)I thought we discussed this, why do you need "right"? Two binary searches where one would do just fine.
Quoted 2 lines
I think the idea is that there would be less strcmp's if there is a long sequence of items with identical names.
Sure, it's a tradeoff. But how long is the set of duplicate name entries we expect in kernel BTF? Additional O(logN) over 70K+ types with high likelihood will take more comparisons.
Eduard Zingerman
maintainerRe: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
Quoted 22 lines · Andrii Nakryiko
Quoted 21 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 15 lines
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 912
Quoted 12 lines
tools/lib/bpf/btf.c +7
-1@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; } -__s32 btf__find_by_name (const struct btf *btf,const char *type_name) +/* +* Find BTF types with matching names within the [left, right] index range. +* On success, updates *left and *right to the boundaries of the matching range +* and returns the leftmost matching index. +*/ +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name, +__s32 *left,__s32 *right)I thought we discussed this, why do you need "right"? Two binary searches where one would do just fine.
Quoted 6 lines
Quoted 2 lines
I think the idea is that there would be less strcmp's if there is a long sequence of items with identical names.
Sure, it's a tradeoff. But how long is the set of duplicate name entries we expect in kernel BTF? Additional O(logN) over 70K+ types with high likelihood will take more comparisons.
$ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head
51737 '(anon)'
277 'bpf_kfunc'
4 'long
3 'perf_aux_event'
3 'workspace'
2 'ata_acpi_gtm'
2 'avc_cache_stats'
2 'bh_accounting'
2 'bp_cpuinfo'
2 'bpf_fastcall''bpf_kfunc' is probably for decl_tags.
So I agree with you regarding the second binary search, it is not necessary. But skipping all anonymous types (and thus having to maintain nr_sorted_types) might be useful, on each search two iterations would be wasted to skip those.
Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
Quoted 43 lines · Eduard Zingerman
Quoted 22 lines · Andrii Nakryiko
Quoted 21 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 15 lines
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 912
Quoted 12 lines
tools/lib/bpf/btf.c +7
-1@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; } -__s32 btf__find_by_name (const struct btf *btf,const char *type_name) +/* +* Find BTF types with matching names within the [left, right] index range. +* On success, updates *left and *right to the boundaries of the matching range +* and returns the leftmost matching index. +*/ +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name, +__s32 *left,__s32 *right)I thought we discussed this, why do you need "right"? Two binary searches where one would do just fine.
Quoted 6 lines
Quoted 2 lines
I think the idea is that there would be less strcmp's if there is a long sequence of items with identical names.
Sure, it's a tradeoff. But how long is the set of duplicate name entries we expect in kernel BTF? Additional O(logN) over 70K+ types with high likelihood will take more comparisons.
$ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head 51737 '(anon)' 277 'bpf_kfunc' 4 'long 3 'perf_aux_event' 3 'workspace' 2 'ata_acpi_gtm' 2 'avc_cache_stats' 2 'bh_accounting' 2 'bp_cpuinfo' 2 'bpf_fastcall'
Quoted 5 lines
'
bpf_kfunc' is probably fordecl_tags.
So I agree with you regarding the second binary search, it is not necessary. But skipping all anonymous types (and thus having to maintainnr_sorted_types) might be useful, on each search two iterations would be wasted to skip those.
Thank you. After removing the redundant iterations, performance increased significantly compared with two iterations.
Test Case: Locate all 58,719 named types in vmlinux BTF Methodology:
./vmtest.sh -- ./test_progs -t btf_permute/perf -v
Two iterations:
| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,282 ms | Baseline | | Sorted (Binary) | 19 ms | 909x faster |
One iteration:
Results:
| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,619 ms | Baseline | | Sorted (Binary) | 10 ms | 1762x faster |
Here is the code implementation with a single iteration approach. I believe this scenario differs from find_linfo because we cannot determine in advance whether the specified type name will be found. Please correct me if I've misunderstood anything, and I welcome any guidance on this matter.
static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
__s32 start_id)
{
const struct btf_type *t;
const char *tname;
__s32 l, r, m, lmost = -ENOENT;
int ret;
/* found the leftmost btf_type that matches */
l = start_id;
r = btf__type_cnt(btf) - 1;
while (l <= r) {
m = l + (r - l) / 2;
t = btf_type_by_id(btf, m);
if (!t->name_off) {
ret = 1;
} else {
tname = btf__str_by_offset(btf, t->name_off);
ret = !tname ? 1 : strcmp(tname, name);
}
if (ret < 0) {
l = m + 1;
} else {
if (ret == 0)
lmost = m;
r = m - 1;
}
}
return lmost;
}static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_id,
const char *type_name, __u32 kind)
{
const struct btf_type *t;
const char *tname;
int err = -ENOENT;
__u32 total;
if (!btf)
goto out;
if (start_id < btf->start_id) {
err = btf_find_type_by_name_kind(btf->base_btf, start_id,
type_name, kind);
if (err == -ENOENT)
start_id = btf->start_id;
}
if (err == -ENOENT) {
if (btf_check_sorted((struct btf *)btf)) {
/* binary search */
bool skip_first;
int ret;
/* return the leftmost with maching names */
ret = btf_find_type_by_name_bsearch(btf,
type_name, start_id);
if (ret < 0)
goto out;
/* skip kind checking */
if (kind == -1)
return ret;
total = btf__type_cnt(btf);
skip_first = true;
do {
t = btf_type_by_id(btf, ret);
if (btf_kind(t) != kind) {
if (skip_first) {
skip_first = false;
continue;
}
} else if (skip_first) {
return ret;
}
if (!t->name_off)
break;
tname = btf__str_by_offset(btf, t->name_off);
if (tname && !strcmp(tname, type_name))
return ret;
else
break;
} while (++ret < total);
} else {
/* linear search */
...
}
}out:
return err; }
Eduard Zingerman
maintainerRe: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
Quoted 63 lines · Donglin Peng
Quoted 43 lines · Eduard Zingerman
Quoted 22 lines · Andrii Nakryiko
Quoted 21 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 15 lines
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 912
Quoted 12 lines
tools/lib/bpf/btf.c +7
-1@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; } -__s32 btf__find_by_name (const struct btf *btf,const char *type_name) +/* +* Find BTF types with matching names within the [left, right] index range. +* On success, updates *left and *right to the boundaries of the matching range +* and returns the leftmost matching index. +*/ +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name, +__s32 *left,__s32 *right)I thought we discussed this, why do you need "right"? Two binary searches where one would do just fine.
Quoted 6 lines
Quoted 2 lines
I think the idea is that there would be less strcmp's if there is a long sequence of items with identical names.
Sure, it's a tradeoff. But how long is the set of duplicate name entries we expect in kernel BTF? Additional O(logN) over 70K+ types with high likelihood will take more comparisons.
$ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head 51737 '(anon)' 277 'bpf_kfunc' 4 'long 3 'perf_aux_event' 3 'workspace' 2 'ata_acpi_gtm' 2 'avc_cache_stats' 2 'bh_accounting' 2 'bp_cpuinfo' 2 'bpf_fastcall'Quoted 5 lines
'
bpf_kfunc' is probably fordecl_tags.
So I agree with you regarding the second binary search, it is not necessary. But skipping all anonymous types (and thus having to maintainnr_sorted_types) might be useful, on each search two iterations would be wasted to skip those.Thank you. After removing the redundant iterations, performance increased significantly compared with two iterations.
Test Case: Locate all 58,719 named types in vmlinux BTF Methodology:
./vmtest.sh -- ./test_progs -t btf_permute/perf -vTwo iterations:
Quoted 4 lines
Condition | Lookup Time | Improvement |
--------------------|-------------|-------------|Unsorted (Linear) | 17,282 ms | Baseline | Sorted (Binary) | 19 ms | 909x faster |
Quoted 8 lines
One iteration:
Results:Quoted 4 lines
Condition | Lookup Time | Improvement |
--------------------|-------------|-------------|Unsorted (Linear) | 17,619 ms | Baseline | Sorted (Binary) | 10 ms | 1762x faster |Here is the code implementation with a single iteration approach.
Could you please also check if there is a difference between having nr_sorted_types as is and having it equal to nr_types? Want to understand if this optimization is necessary.
[...]
Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
Quoted 72 lines · Eduard Zingerman
Quoted 70 lines · Donglin Peng
Quoted 43 lines · Eduard Zingerman
Quoted 22 lines · Andrii Nakryiko
Quoted 21 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 15 lines
Review int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 912
Quoted 12 lines
(quoted diff) +7
-1@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id) return type_id; } -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +/* + * Find BTF types with matching names within the [left, right] index range. + * On success, updates *left and *right to the boundaries of the matching range + * and returns the leftmost matching index. + */ +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name, + __s32 *left, __s32 *right)I thought we discussed this, why do you need "right"? Two binary searches where one would do just fine.
Quoted 6 lines
Quoted 2 lines
I think the idea is that there would be less strcmp's if there is a long sequence of items with identical names.
Sure, it's a tradeoff. But how long is the set of duplicate name entries we expect in kernel BTF? Additional O(logN) over 70K+ types with high likelihood will take more comparisons.
$ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head 51737 '(anon)' 277 'bpf_kfunc' 4 'long 3 'perf_aux_event' 3 'workspace' 2 'ata_acpi_gtm' 2 'avc_cache_stats' 2 'bh_accounting' 2 'bp_cpuinfo' 2 'bpf_fastcall'Quoted 5 lines
'
bpf_kfunc' is probably fordecl_tags.
So I agree with you regarding the second binary search, it is not necessary. But skipping all anonymous types (and thus having to maintainnr_sorted_types) might be useful, on each search two iterations would be wasted to skip those.Thank you. After removing the redundant iterations, performance increased significantly compared with two iterations.
Test Case: Locate all 58,719 named types in vmlinux BTF Methodology:
./vmtest.sh -- ./test_progs -t btf_permute/perf -vTwo iterations:
Quoted 4 lines
Condition | Lookup Time | Improvement |
--------------------|-------------|-------------|Unsorted (Linear) | 17,282 ms | Baseline | Sorted (Binary) | 19 ms | 909x faster |One iteration:
Results:Quoted 4 lines
Condition | Lookup Time | Improvement |
--------------------|-------------|-------------|Unsorted (Linear) | 17,619 ms | Baseline | Sorted (Binary) | 10 ms | 1762x faster |
Quoted 5 lines
Quoted 1 line
Here is the code implementation with a single iteration approach.
Could you please also check if there is a difference between having
nr_sorted_typesas is and having it equal tonr_types? Want to understand if this optimization is necessary.
Yes, here is the result:
| Condition | Lookup Time | Improvement | |----------------------------------------------|------------------ --|------------------| | Unsorted (Linear) | 16666461 us | Baseline | | Sorted (Binary) nr__types | 9957 us | 1673x faster | | Sorted (Binary) nr_sorted_types | 9337 us | 1785x faster |
Using nr_sorted_types provides an additional 6% performance improvement over nr_types.
Quoted 2 lines
[...]
Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
In reply to Donglin PengQuoted 45 lines · Donglin Peng
Quoted 43 lines · Eduard Zingerman
Quoted 22 lines · Andrii Nakryiko
Quoted 21 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 15 lines
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 912
Quoted 12 lines
tools/lib/bpf/btf.c +7
-1@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; } -__s32 btf__find_by_name (const struct btf *btf,const char *type_name) +/* +* Find BTF types with matching names within the [left, right] index range. +* On success, updates *left and *right to the boundaries of the matching range +* and returns the leftmost matching index. +*/ +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name, +__s32 *left,__s32 *right)I thought we discussed this, why do you need "right"? Two binary searches where one would do just fine.
Quoted 6 lines
Quoted 2 lines
I think the idea is that there would be less strcmp's if there is a long sequence of items with identical names.
Sure, it's a tradeoff. But how long is the set of duplicate name entries we expect in kernel BTF? Additional O(logN) over 70K+ types with high likelihood will take more comparisons.
$ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head 51737 '(anon)' 277 'bpf_kfunc' 4 'long 3 'perf_aux_event' 3 'workspace' 2 'ata_acpi_gtm' 2 'avc_cache_stats' 2 'bh_accounting' 2 'bp_cpuinfo' 2 'bpf_fastcall'
Quoted 5 lines
Quoted 5 lines
'
bpf_kfunc' is probably fordecl_tags.
So I agree with you regarding the second binary search, it is not necessary. But skipping all anonymous types (and thus having to maintainnr_sorted_types) might be useful, on each search two iterations would be wasted to skip those.
fair enough, eliminating a big chunk of anonymous types is useful, let's do this
Quoted 51 lines
Thank you. After removing the redundant iterations, performance increased significantly compared with two iterations.
Test Case: Locate all 58,719 named types in vmlinux BTF Methodology:
./vmtest.sh -- ./test_progs -t btf_permute/perf -vTwo iterations:
| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,282 ms | Baseline | | Sorted (Binary) | 19 ms | 909x faster |One iteration:
Results:| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,619 ms | Baseline | | Sorted (Binary) | 10 ms | 1762x faster |Here is the code implementation with a single iteration approach. I believe this scenario differs from
find_linfobecause we cannot determine in advance whether the specified type name will be found. Please correct me if I've misunderstood anything, and I welcome any guidance on this matter.static
__s32btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,__s32 start_id) { const struct btf_type *t; const char *tname; __s32 l, r, m, lmost = -ENOENT; int ret; /* found the leftmost btf_type that matches */ l = start_id; r = btf__type_cnt(btf) - 1; while (l <= r) { m = l + (r - l) / 2; t = btf_type_by_id(btf, m); if (!t->name_off) { ret = 1; } else { tname = btf__str_by_offset(btf, t->name_off); ret = !tname ? 1 : strcmp(tname, name); } if (ret < 0) { l = m + 1; } else {
Quoted 8 lines
if (ret == 0)
lmost = m;
r = m - 1;
}
}
return lmost;
}There are different ways to implement this. At the highest level, implementation below just searches for leftmost element that has name
Quoted 1 line
= the one we are searching for. One complication is that such element
might not event exists. We can solve that checking ahead of time whether the rightmost type satisfied the condition, or we could do something similar to what I do in the loop below, where I allow l == r and then if that element has name >= to what we search, we exit because we found it. And if not, l will become larger than r, we'll break out of the loop and we'll know that we couldn't find the element. I haven't tested it, but please take a look and if you decide to go with such approach, do test it for edge cases, of course.
/*
* We are searching for the smallest r such that type #r's name is >= name.
* It might not exist, in which case we'll have l == r + 1.
*/
l = start_id;
r = btf__type_cnt(btf) - 1;
while (l < r) {
m = l + (r - l) / 2;
t = btf_type_by_id(btf, m);
tname = btf__str_by_offset(btf, t->name_off);
if (strcmp(tname, name) >= 0) {
if (l == r)
return r; /* found it! */
r = m;
} else {
l = m + 1;
}
}/* here we know given element doesn't exist, return index beyond end of types */ return btf__type_cnt(btf);
We could have checked instead whether strcmp(btf__str_by_offset(btf, btf__type_by_id(btf, btf__type_cnt() - 1)->name_off), name) < 0 and exit early. That's just a bit more code duplication of essentially what we do inside the loop, so that if (l == r) seems fine to me, but I'm not married to this.
Quoted 62 lines
static
__s32btf_find_type_by_name_kind(const struct btf *btf, intstart_id,
const char*type_name,__u32kind){ const struct btf_type *t; const char *tname; int err = -ENOENT; __u32 total; if (!btf) goto out; if (start_id < btf->start_id) { err = btf_find_type_by_name_kind(btf->base_btf, start_id, type_name, kind); if (err == -ENOENT) start_id = btf->start_id; } if (err == -ENOENT) { if (btf_check_sorted((struct btf *)btf)) { /* binary search */ bool skip_first; int ret; /* return the leftmost with maching names */ ret = btf_find_type_by_name_bsearch(btf, type_name, start_id); if (ret < 0) goto out; /* skip kind checking */ if (kind == -1) return ret; total = btf__type_cnt(btf); skip_first = true; do { t = btf_type_by_id(btf, ret); if (btf_kind(t) != kind) { if (skip_first) { skip_first = false; continue; } } else if (skip_first) { return ret; } if (!t->name_off) break; tname = btf__str_by_offset(btf, t->name_off); if (tname && !strcmp(tname, type_name)) return ret; else break; } while (++ret < total); } else { /* linear search */ ... } }out:
return err; }
Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
Quoted 133 lines · Andrii Nakryiko
Quoted 45 lines · Donglin Peng
Quoted 43 lines · Eduard Zingerman
Quoted 22 lines · Andrii Nakryiko
Quoted 21 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 15 lines
Review int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 912
Quoted 12 lines
(quoted diff) +7
-1@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id) return type_id; } -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +/* + * Find BTF types with matching names within the [left, right] index range. + * On success, updates *left and *right to the boundaries of the matching range + * and returns the leftmost matching index. + */ +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name, + __s32 *left, __s32 *right)I thought we discussed this, why do you need "right"? Two binary searches where one would do just fine.
Quoted 6 lines
Quoted 2 lines
I think the idea is that there would be less strcmp's if there is a long sequence of items with identical names.
Sure, it's a tradeoff. But how long is the set of duplicate name entries we expect in kernel BTF? Additional O(logN) over 70K+ types with high likelihood will take more comparisons.
$ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head 51737 '(anon)' 277 'bpf_kfunc' 4 'long 3 'perf_aux_event' 3 'workspace' 2 'ata_acpi_gtm' 2 'avc_cache_stats' 2 'bh_accounting' 2 'bp_cpuinfo' 2 'bpf_fastcall'Quoted 5 lines
Quoted 5 lines
'
bpf_kfunc' is probably fordecl_tags.
So I agree with you regarding the second binary search, it is not necessary. But skipping all anonymous types (and thus having to maintainnr_sorted_types) might be useful, on each search two iterations would be wasted to skip those.fair enough, eliminating a big chunk of anonymous types is useful, let's do this
Quoted 51 lines
Thank you. After removing the redundant iterations, performance increased significantly compared with two iterations.
Test Case: Locate all 58,719 named types in vmlinux BTF Methodology:
./vmtest.sh -- ./test_progs -t btf_permute/perf -vTwo iterations:
| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,282 ms | Baseline | | Sorted (Binary) | 19 ms | 909x faster |One iteration:
Results:| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,619 ms | Baseline | | Sorted (Binary) | 10 ms | 1762x faster |Here is the code implementation with a single iteration approach. I believe this scenario differs from
find_linfobecause we cannot determine in advance whether the specified type name will be found. Please correct me if I've misunderstood anything, and I welcome any guidance on this matter.static
__s32btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,__s32 start_id) { const struct btf_type *t; const char *tname; __s32 l, r, m, lmost = -ENOENT; int ret; /* found the leftmost btf_type that matches */ l = start_id; r = btf__type_cnt(btf) - 1; while (l <= r) { m = l + (r - l) / 2; t = btf_type_by_id(btf, m); if (!t->name_off) { ret = 1; } else { tname = btf__str_by_offset(btf, t->name_off); ret = !tname ? 1 : strcmp(tname, name); } if (ret < 0) { l = m + 1; } else {Quoted 8 lines
if (ret == 0) lmost = m; r = m - 1; } } return lmost; }There are different ways to implement this. At the highest level, implementation below just searches for leftmost element that has name
Quoted 1 line
= the one we are searching for. One complication is that such element
might not event exists. We can solve that checking ahead of time whether the rightmost type satisfied the condition, or we could do something similar to what I do in the loop below, where I allow l == r and then if that element has name >= to what we search, we exit because we found it. And if not, l will become larger than r, we'll break out of the loop and we'll know that we couldn't find the element. I haven't tested it, but please take a look and if you decide to go with such approach, do test it for edge cases, of course.
/*
* We are searching for the smallest r such that type #r's name is >= name.
* It might not exist, in which case we'll have l == r + 1.
*/
l =start_id;
r =btf__type_cnt(btf)- 1;
Quoted 8 lines
while (l < r) {
m = l + (r - l) / 2;
t = btf_type_by_id(btf, m);
tname = btf__str_by_offset(btf, t->name_off);
if (strcmp(tname, name) >= 0) {
if (l == r)
return r; /* found it! */It seems that this if condition will never hold, because a while(l < r) loop is used. Moreover, even if the condition were to hold, it wouldn't guarantee a successful search.
Quoted 7 lines
r = m; } else { l = m + 1; } }/* here we know given element doesn't exist, return index beyond end of types */ return
btf__type_cnt(btf);
I think that return -ENOENT seems more reasonable.
Quoted 7 lines
We could have checked instead whether
strcmp(btf__str_by_offset(btf, btf__type_by_id(btf, btf__type_cnt() - 1)->name_off), name)< 0 and exit early. That's just a bit more code duplication of essentially what we do inside the loop, so that if (l == r) seems fine to me, but I'm not married to this.
Sorry, I believe that even if strcmp(btf__str_by_offset(btf, btf__type_by_id(btf,btf__type_cnt() - 1)->name_off), name) >= 0, it still doesn't seem to guarantee that the search will definitely succeed.
Quoted 63 lines
Quoted 63 lines
static
__s32btf_find_type_by_name_kind(const struct btf *btf, intstart_id,
const char*type_name,__u32kind){ const struct btf_type *t; const char *tname; int err = -ENOENT; __u32 total; if (!btf) goto out; if (start_id < btf->start_id) { err = btf_find_type_by_name_kind(btf->base_btf, start_id, type_name, kind); if (err == -ENOENT) start_id = btf->start_id; } if (err == -ENOENT) { if (btf_check_sorted((struct btf *)btf)) { /* binary search */ bool skip_first; int ret; /* return the leftmost with maching names */ ret = btf_find_type_by_name_bsearch(btf, type_name, start_id); if (ret < 0) goto out; /* skip kind checking */ if (kind == -1) return ret; total = btf__type_cnt(btf); skip_first = true; do { t = btf_type_by_id(btf, ret); if (btf_kind(t) != kind) { if (skip_first) { skip_first = false; continue; } } else if (skip_first) { return ret; } if (!t->name_off) break; tname = btf__str_by_offset(btf, t->name_off); if (tname && !strcmp(tname, type_name)) return ret; else break; } while (++ret < total); } else { /* linear search */ ... } }out:
return err; }
Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
Quoted 141 lines · Donglin Peng
Quoted 138 lines · Andrii Nakryiko
Quoted 45 lines · Donglin Peng
Quoted 43 lines · Eduard Zingerman
Quoted 22 lines · Andrii Nakryiko
Quoted 21 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 15 lines
Review int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 912
Quoted 12 lines
(quoted diff) +7
-1@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id) return type_id; } -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +/* + * Find BTF types with matching names within the [left, right] index range. + * On success, updates *left and *right to the boundaries of the matching range + * and returns the leftmost matching index. + */ +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name, + __s32 *left, __s32 *right)I thought we discussed this, why do you need "right"? Two binary searches where one would do just fine.
Quoted 6 lines
Quoted 2 lines
I think the idea is that there would be less strcmp's if there is a long sequence of items with identical names.
Sure, it's a tradeoff. But how long is the set of duplicate name entries we expect in kernel BTF? Additional O(logN) over 70K+ types with high likelihood will take more comparisons.
$ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head 51737 '(anon)' 277 'bpf_kfunc' 4 'long 3 'perf_aux_event' 3 'workspace' 2 'ata_acpi_gtm' 2 'avc_cache_stats' 2 'bh_accounting' 2 'bp_cpuinfo' 2 'bpf_fastcall'Quoted 5 lines
Quoted 5 lines
'
bpf_kfunc' is probably fordecl_tags.
So I agree with you regarding the second binary search, it is not necessary. But skipping all anonymous types (and thus having to maintainnr_sorted_types) might be useful, on each search two iterations would be wasted to skip those.fair enough, eliminating a big chunk of anonymous types is useful, let's do this
Quoted 51 lines
Thank you. After removing the redundant iterations, performance increased significantly compared with two iterations.
Test Case: Locate all 58,719 named types in vmlinux BTF Methodology:
./vmtest.sh -- ./test_progs -t btf_permute/perf -vTwo iterations:
| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,282 ms | Baseline | | Sorted (Binary) | 19 ms | 909x faster |One iteration:
Results:| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,619 ms | Baseline | | Sorted (Binary) | 10 ms | 1762x faster |Here is the code implementation with a single iteration approach. I believe this scenario differs from
find_linfobecause we cannot determine in advance whether the specified type name will be found. Please correct me if I've misunderstood anything, and I welcome any guidance on this matter.static
__s32btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,__s32 start_id) { const struct btf_type *t; const char *tname; __s32 l, r, m, lmost = -ENOENT; int ret; /* found the leftmost btf_type that matches */ l = start_id; r = btf__type_cnt(btf) - 1; while (l <= r) { m = l + (r - l) / 2; t = btf_type_by_id(btf, m); if (!t->name_off) { ret = 1; } else { tname = btf__str_by_offset(btf, t->name_off); ret = !tname ? 1 : strcmp(tname, name); } if (ret < 0) { l = m + 1; } else {Quoted 8 lines
if (ret == 0) lmost = m; r = m - 1; } } return lmost; }There are different ways to implement this. At the highest level, implementation below just searches for leftmost element that has name
Quoted 1 line
= the one we are searching for. One complication is that such element
might not event exists. We can solve that checking ahead of time whether the rightmost type satisfied the condition, or we could do something similar to what I do in the loop below, where I allow l == r and then if that element has name >= to what we search, we exit because we found it. And if not, l will become larger than r, we'll break out of the loop and we'll know that we couldn't find the element. I haven't tested it, but please take a look and if you decide to go with such approach, do test it for edge cases, of course.
/*
* We are searching for the smallest r such that type #r's name is >= name.
* It might not exist, in which case we'll have l == r + 1.
*/
l =start_id;
r =btf__type_cnt(btf)- 1;while (l < r) { m = l + (r - l) / 2; t = btf_type_by_id(btf, m); tname = btf__str_by_offset(btf, t->name_off);
Quoted 5 lines
Quoted 3 lines
if (strcmp(tname, name) >= 0) { if (l == r) return r; /* found it! */It seems that this if condition will never hold, because a while(l < r) loop
It should be while (l <= r), I forgot to update it, but I mentioned that I do want to allow l == r condition.
Quoted 2 lines
is used. Moreover, even if the condition were to hold, it wouldn't guarantee a successful search.
Elaborate please on "wouldn't guarantee a successful search".
Quoted 10 lines
Quoted 8 lines
r = m; } else { l = m + 1; } }/* here we know given element doesn't exist, return index beyond end of types */ return
btf__type_cnt(btf);I think that return
-ENOENTseems more reasonable.
Think how you will be using this inside btf_find_type_by_name_kind():
int idx = btf_find_by_name_bsearch(btf, name);
for (int n = btf__type_cnt(btf); idx < n; idx++) {
struct btf_type *t = btf__type_by_id(btf, idx);
const char *tname = btf__str_by_offset(btf, t->name_off);
if (strcmp(tname, name) != 0)
return -ENOENT;
if (btf_kind(t) == kind)
return idx;
}return -ENOENT;
Having btf_find_by_name_bsearch() return -ENOENT instead of btf__type_cnt() just will require extra explicit -ENOENT handling. And given the function now can return "error", we'd need to either handle other non-ENOENT errors, to at least leave comment that this should never happen, though interface itself looks like it could.
This is relatively minor and its all internal implementation, so we can change that later. But I'm explaining my reasons for why I'd return index of non-existing type after the end, just like you'd do with pointer-based interfaces that return pointer after the last element.
Quoted 9 lines
Quoted 8 lines
We could have checked instead whether
strcmp(btf__str_by_offset(btf, btf__type_by_id(btf, btf__type_cnt() - 1)->name_off), name)< 0 and exit early. That's just a bit more code duplication of essentially what we do inside the loop, so that if (l == r) seems fine to me, but I'm not married to this.
Quoted 4 lines
Sorry, I believe that even if strcmp(btf__str_by_offset(btf, btf__type_by_id(btf,
btf__type_cnt()- 1)->name_off), name) >= 0, it still doesn't seem to guarantee that the search will definitely succeed.
If the last element has >= name, search will definitely find at least that element. What do you mean by "succeed"? All I care about here is that binary search loop doesn't loop forever and it returns correct index (or detects that no element can be found).
Quoted 64 lines
Quoted 64 lines
Quoted 64 lines
static
__s32btf_find_type_by_name_kind(const struct btf *btf, intstart_id,
const char*type_name,__u32kind){ const struct btf_type *t; const char *tname; int err = -ENOENT; __u32 total; if (!btf) goto out; if (start_id < btf->start_id) { err = btf_find_type_by_name_kind(btf->base_btf, start_id, type_name, kind); if (err == -ENOENT) start_id = btf->start_id; } if (err == -ENOENT) { if (btf_check_sorted((struct btf *)btf)) { /* binary search */ bool skip_first; int ret; /* return the leftmost with maching names */ ret = btf_find_type_by_name_bsearch(btf, type_name, start_id); if (ret < 0) goto out; /* skip kind checking */ if (kind == -1) return ret; total = btf__type_cnt(btf); skip_first = true; do { t = btf_type_by_id(btf, ret); if (btf_kind(t) != kind) { if (skip_first) { skip_first = false; continue; } } else if (skip_first) { return ret; } if (!t->name_off) break; tname = btf__str_by_offset(btf, t->name_off); if (tname && !strcmp(tname, type_name)) return ret; else break; } while (++ret < total); } else { /* linear search */ ... } }out:
return err; }
Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
Quoted 149 lines · Andrii Nakryiko
Quoted 141 lines · Donglin Peng
Quoted 138 lines · Andrii Nakryiko
Quoted 45 lines · Donglin Peng
Quoted 43 lines · Eduard Zingerman
Quoted 22 lines · Andrii Nakryiko
Quoted 21 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 15 lines
Review int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 912
Quoted 12 lines
(quoted diff) +7
-1@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id) return type_id; } -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +/* + * Find BTF types with matching names within the [left, right] index range. + * On success, updates *left and *right to the boundaries of the matching range + * and returns the leftmost matching index. + */ +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name, + __s32 *left, __s32 *right)I thought we discussed this, why do you need "right"? Two binary searches where one would do just fine.
Quoted 6 lines
Quoted 2 lines
I think the idea is that there would be less strcmp's if there is a long sequence of items with identical names.
Sure, it's a tradeoff. But how long is the set of duplicate name entries we expect in kernel BTF? Additional O(logN) over 70K+ types with high likelihood will take more comparisons.
$ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head 51737 '(anon)' 277 'bpf_kfunc' 4 'long 3 'perf_aux_event' 3 'workspace' 2 'ata_acpi_gtm' 2 'avc_cache_stats' 2 'bh_accounting' 2 'bp_cpuinfo' 2 'bpf_fastcall'Quoted 5 lines
Quoted 5 lines
'
bpf_kfunc' is probably fordecl_tags.
So I agree with you regarding the second binary search, it is not necessary. But skipping all anonymous types (and thus having to maintainnr_sorted_types) might be useful, on each search two iterations would be wasted to skip those.fair enough, eliminating a big chunk of anonymous types is useful, let's do this
Quoted 51 lines
Thank you. After removing the redundant iterations, performance increased significantly compared with two iterations.
Test Case: Locate all 58,719 named types in vmlinux BTF Methodology:
./vmtest.sh -- ./test_progs -t btf_permute/perf -vTwo iterations:
| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,282 ms | Baseline | | Sorted (Binary) | 19 ms | 909x faster |One iteration:
Results:| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,619 ms | Baseline | | Sorted (Binary) | 10 ms | 1762x faster |Here is the code implementation with a single iteration approach. I believe this scenario differs from
find_linfobecause we cannot determine in advance whether the specified type name will be found. Please correct me if I've misunderstood anything, and I welcome any guidance on this matter.static
__s32btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,__s32 start_id) { const struct btf_type *t; const char *tname; __s32 l, r, m, lmost = -ENOENT; int ret; /* found the leftmost btf_type that matches */ l = start_id; r = btf__type_cnt(btf) - 1; while (l <= r) { m = l + (r - l) / 2; t = btf_type_by_id(btf, m); if (!t->name_off) { ret = 1; } else { tname = btf__str_by_offset(btf, t->name_off); ret = !tname ? 1 : strcmp(tname, name); } if (ret < 0) { l = m + 1; } else {Quoted 8 lines
if (ret == 0) lmost = m; r = m - 1; } } return lmost; }There are different ways to implement this. At the highest level, implementation below just searches for leftmost element that has name
Quoted 1 line
= the one we are searching for. One complication is that such element
might not event exists. We can solve that checking ahead of time whether the rightmost type satisfied the condition, or we could do something similar to what I do in the loop below, where I allow l == r and then if that element has name >= to what we search, we exit because we found it. And if not, l will become larger than r, we'll break out of the loop and we'll know that we couldn't find the element. I haven't tested it, but please take a look and if you decide to go with such approach, do test it for edge cases, of course.
/*
* We are searching for the smallest r such that type #r's name is >= name.
* It might not exist, in which case we'll have l == r + 1.
*/
l =start_id;
r =btf__type_cnt(btf)- 1;while (l < r) { m = l + (r - l) / 2; t = btf_type_by_id(btf, m); tname = btf__str_by_offset(btf, t->name_off);Quoted 5 lines
Quoted 3 lines
if (strcmp(tname, name) >= 0) { if (l == r) return r; /* found it! */It seems that this if condition will never hold, because a while(l < r) loop
Quoted 7 lines
It should be
while (l <= r), I forgot to update it, but I mentioned that I do want to allow l == r condition.Quoted 2 lines
is used. Moreover, even if the condition were to hold, it wouldn't guarantee a successful search.
Elaborate please on "wouldn't guarantee a successful search".
I think a successful search is that we can successfully find the element that we want.
Quoted 25 lines
Quoted 11 lines
Quoted 9 lines
r = m; } else { l = m + 1; } }/* here we know given element doesn't exist, return index beyond end of types */ return
btf__type_cnt(btf);I think that return
-ENOENTseems more reasonable.Think how you will be using this inside
btf_find_type_by_name_kind():int idx =
btf_find_by_name_bsearch(btf, name);for (int n = btf__type_cnt(btf); idx < n; idx++) { struct btf_type *t = btf__type_by_id(btf, idx); const char *tname = btf__str_by_offset(btf, t->name_off); if (strcmp(tname, name) != 0) return -ENOENT; if (btf_kind(t) == kind) return idx; }
Quoted 1 line
return
-ENOENT;
Thanks, it seems cleaner.
Quoted 8 lines
Having
btf_find_by_name_bsearch()return-ENOENTinstead ofbtf__type_cnt()just will require extra explicit-ENOENThandling. And given the function now can return "error", we'd need to either handle other non-ENOENT errors, to at least leave comment that this should never happen, though interface itself looks like it could.
Quoted 5 lines
This is relatively minor and its all internal implementation, so we can change that later. But I'm explaining my reasons for why I'd return index of non-existing type after the end, just like you'd do with pointer-based interfaces that return pointer after the last element.
Thanks, I see.
Quoted 11 lines
Quoted 11 lines
Quoted 10 lines
We could have checked instead whether
strcmp(btf__str_by_offset(btf, btf__type_by_id(btf, btf__type_cnt() - 1)->name_off), name)< 0 and exit early. That's just a bit more code duplication of essentially what we do inside the loop, so that if (l == r) seems fine to me, but I'm not married to this.
Quoted 7 lines
Quoted 4 lines
Sorry, I believe that even if strcmp(btf__str_by_offset(btf, btf__type_by_id(btf,
btf__type_cnt()- 1)->name_off), name) >= 0, it still doesn't seem to guarantee that the search will definitely succeed.If the last element has >= name, search will definitely find at least that element. What do you mean by "succeed"? All I care about here is
Thank you. By "successful search," I mean finding the exact matching element we're looking for—not just the first element that meets the "≥" condition.
Here's a concrete example to illustrate the issue:
Base BTF contains: {"A", "C", "E", "F"}
Split BTF contains: {"B", "D"}
Target search: "D" in split BTF
The current implementation recursively searches from the base BTF first. While "D" is lexicographically ≤ "F" (the last element in base BTF), "D" doesn't actually exist in the base BTF. When the binary search reaches the l == r condition,
it returns the index of "E" instead.
This requires an extra name comparison check after btf_find_by_name_bsearch returns, which could be avoided in the first loop iteration if the search directly
identified exact matches.
int idx = btf_find_by_name_bsearch(btf, name);
for (int n = btf__type_cnt(btf); idx < n; idx++) {
struct btf_type *t = btf__type_by_id(btf, idx);
const char *tname = btf__str_by_offset(btf, t->name_off);
if (strcmp(tname, name) != 0) <<< This check is redundant on the first loop
iteration
when a matching index is found
return -ENOENT;
if (btf_kind(t) == kind)
return idx;
}return -ENOENT;
I tested this with a simple program searching for 3 in {0, 1, 2, 4, 5}:
int main(int argc, char *argv[])
{
int values[] = {0, 1, 2, 4, 5};
int to_find;
int i;
to_find = atoi(argv[1]);;
for (i = 0; i < ARRAY_SIZE(values); i++)
printf("[%d] = %d\n", i , values[i]);
printf("To Find %d\n", to_find);
{
int l, m, r;
l = 0;
r = ARRAY_SIZE(values) - 1;
while (l <= r) {
m = l + (r- l) / 2;
if (values[m] >= to_find) {
if (l == r) {
printf("!!!! Found: [%d] ==>
%d\n", r, values[r]);
break;
}
r = m;
} else {
l = m + 1;
}
}
printf("END: l: %d, r: %d\n", l, r);
}
return 0;
}Output:
[0] = 0
[1] = 1
[2] = 2
[3] = 4
[4] = 5
To Find 3
!!!! Found: [3] ==> 4
END: l: 3, r: 3
The search returns index 3 (value 4), which is the first value ≥ 3, but since 4 ≠ 3,
it's not an exact match. Thus, the algorithm cannot guarantee a successful search
for the exact element without additional checks.
Quoted 67 lines
that binary search loop doesn't loop forever and it returns correct index (or detects that no element can be found).
Quoted 64 lines
Quoted 64 lines
Quoted 64 lines
static
__s32btf_find_type_by_name_kind(const struct btf *btf, intstart_id,
const char*type_name,__u32kind){ const struct btf_type *t; const char *tname; int err = -ENOENT; __u32 total; if (!btf) goto out; if (start_id < btf->start_id) { err = btf_find_type_by_name_kind(btf->base_btf, start_id, type_name, kind); if (err == -ENOENT) start_id = btf->start_id; } if (err == -ENOENT) { if (btf_check_sorted((struct btf *)btf)) { /* binary search */ bool skip_first; int ret; /* return the leftmost with maching names */ ret = btf_find_type_by_name_bsearch(btf, type_name, start_id); if (ret < 0) goto out; /* skip kind checking */ if (kind == -1) return ret; total = btf__type_cnt(btf); skip_first = true; do { t = btf_type_by_id(btf, ret); if (btf_kind(t) != kind) { if (skip_first) { skip_first = false; continue; } } else if (skip_first) { return ret; } if (!t->name_off) break; tname = btf__str_by_offset(btf, t->name_off); if (tname && !strcmp(tname, type_name)) return ret; else break; } while (++ret < total); } else { /* linear search */ ... } }out:
return err; }
Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
Quoted 155 lines · Donglin Peng
Quoted 152 lines · Andrii Nakryiko
Quoted 141 lines · Donglin Peng
Quoted 138 lines · Andrii Nakryiko
Quoted 45 lines · Donglin Peng
Quoted 43 lines · Eduard Zingerman
Quoted 22 lines · Andrii Nakryiko
Quoted 21 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 15 lines
Review int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 912
Quoted 12 lines
(quoted diff) +7
-1@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id) return type_id; } -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +/* + * Find BTF types with matching names within the [left, right] index range. + * On success, updates *left and *right to the boundaries of the matching range + * and returns the leftmost matching index. + */ +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name, + __s32 *left, __s32 *right)I thought we discussed this, why do you need "right"? Two binary searches where one would do just fine.
Quoted 6 lines
Quoted 2 lines
I think the idea is that there would be less strcmp's if there is a long sequence of items with identical names.
Sure, it's a tradeoff. But how long is the set of duplicate name entries we expect in kernel BTF? Additional O(logN) over 70K+ types with high likelihood will take more comparisons.
$ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head 51737 '(anon)' 277 'bpf_kfunc' 4 'long 3 'perf_aux_event' 3 'workspace' 2 'ata_acpi_gtm' 2 'avc_cache_stats' 2 'bh_accounting' 2 'bp_cpuinfo' 2 'bpf_fastcall'Quoted 5 lines
Quoted 5 lines
'
bpf_kfunc' is probably fordecl_tags.
So I agree with you regarding the second binary search, it is not necessary. But skipping all anonymous types (and thus having to maintainnr_sorted_types) might be useful, on each search two iterations would be wasted to skip those.fair enough, eliminating a big chunk of anonymous types is useful, let's do this
Quoted 51 lines
Thank you. After removing the redundant iterations, performance increased significantly compared with two iterations.
Test Case: Locate all 58,719 named types in vmlinux BTF Methodology:
./vmtest.sh -- ./test_progs -t btf_permute/perf -vTwo iterations:
| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,282 ms | Baseline | | Sorted (Binary) | 19 ms | 909x faster |One iteration:
Results:| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,619 ms | Baseline | | Sorted (Binary) | 10 ms | 1762x faster |Here is the code implementation with a single iteration approach. I believe this scenario differs from
find_linfobecause we cannot determine in advance whether the specified type name will be found. Please correct me if I've misunderstood anything, and I welcome any guidance on this matter.static
__s32btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,__s32 start_id) { const struct btf_type *t; const char *tname; __s32 l, r, m, lmost = -ENOENT; int ret; /* found the leftmost btf_type that matches */ l = start_id; r = btf__type_cnt(btf) - 1; while (l <= r) { m = l + (r - l) / 2; t = btf_type_by_id(btf, m); if (!t->name_off) { ret = 1; } else { tname = btf__str_by_offset(btf, t->name_off); ret = !tname ? 1 : strcmp(tname, name); } if (ret < 0) { l = m + 1; } else {Quoted 8 lines
if (ret == 0) lmost = m; r = m - 1; } } return lmost; }There are different ways to implement this. At the highest level, implementation below just searches for leftmost element that has name
Quoted 1 line
= the one we are searching for. One complication is that such element
might not event exists. We can solve that checking ahead of time whether the rightmost type satisfied the condition, or we could do something similar to what I do in the loop below, where I allow l == r and then if that element has name >= to what we search, we exit because we found it. And if not, l will become larger than r, we'll break out of the loop and we'll know that we couldn't find the element. I haven't tested it, but please take a look and if you decide to go with such approach, do test it for edge cases, of course.
/*
* We are searching for the smallest r such that type #r's name is >= name.
* It might not exist, in which case we'll have l == r + 1.
*/
l =start_id;
r =btf__type_cnt(btf)- 1;while (l < r) { m = l + (r - l) / 2; t = btf_type_by_id(btf, m); tname = btf__str_by_offset(btf, t->name_off);Quoted 5 lines
Quoted 3 lines
if (strcmp(tname, name) >= 0) { if (l == r) return r; /* found it! */It seems that this if condition will never hold, because a while(l < r) loop
It should be
while (l <= r), I forgot to update it, but I mentioned that I do want to allow l == r condition.
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
is used. Moreover, even if the condition were to hold, it wouldn't guarantee a successful search.
Elaborate please on "wouldn't guarantee a successful search".
I think a successful search is that we can successfully find the element that we want.
Ok, I never intended to find exact match with that leftmost >= element as a primitive.
Quoted 27 lines
Quoted 25 lines
Quoted 11 lines
Quoted 9 lines
r = m; } else { l = m + 1; } }/* here we know given element doesn't exist, return index beyond end of types */ return
btf__type_cnt(btf);I think that return
-ENOENTseems more reasonable.Think how you will be using this inside
btf_find_type_by_name_kind():int idx =
btf_find_by_name_bsearch(btf, name);for (int n = btf__type_cnt(btf); idx < n; idx++) { struct btf_type *t = btf__type_by_id(btf, idx); const char *tname = btf__str_by_offset(btf, t->name_off); if (strcmp(tname, name) != 0) return -ENOENT; if (btf_kind(t) == kind) return idx; }Quoted 1 line
return
-ENOENT;
Quoted 1 line
Thanks, it seems cleaner.
ok, great
Quoted 33 lines
Quoted 9 lines
Having
btf_find_by_name_bsearch()return-ENOENTinstead ofbtf__type_cnt()just will require extra explicit-ENOENThandling. And given the function now can return "error", we'd need to either handle other non-ENOENT errors, to at least leave comment that this should never happen, though interface itself looks like it could.Quoted 5 lines
This is relatively minor and its all internal implementation, so we can change that later. But I'm explaining my reasons for why I'd return index of non-existing type after the end, just like you'd do with pointer-based interfaces that return pointer after the last element.
Thanks, I see.
Quoted 16 lines
Quoted 15 lines
Quoted 10 lines
We could have checked instead whether
strcmp(btf__str_by_offset(btf, btf__type_by_id(btf, btf__type_cnt() - 1)->name_off), name)< 0 and exit early. That's just a bit more code duplication of essentially what we do inside the loop, so that if (l == r) seems fine to me, but I'm not married to this.Sorry, I believe that even if strcmp(btf__str_by_offset(btf, btf__type_by_id(btf,
btf__type_cnt()- 1)->name_off), name) >= 0, it still doesn't seem to guarantee that the search will definitely succeed.
Quoted 6 lines
Quoted 2 lines
If the last element has >= name, search will definitely find at least that element. What do you mean by "succeed"? All I care about here is
Thank you. By "successful search," I mean finding the exact matching element we're looking for—not just the first element that meets the "≥" condition.
We don't have to find the exact match, just the leftmost >= element. For search by name+kind you will have to do linear search *anyways* and compare name for every single potential candidate (Except maybe the very first one as micro-optimization and complication, if we had exact matching leftmost element; but I don't care about that complication). So leftmost >= element is a universal "primitive" that allows you to implement exact by name or exact by name+kind search in exactly the same fashion.
Quoted 13 lines
Here's a concrete example to illustrate the issue:
Base BTF contains: {"A", "C", "E", "F"}
Split BTF contains: {"B", "D"}
Target search: "D" in split BTFThe current implementation recursively searches from the base BTF first. While "D" is lexicographically ≤ "F" (the last element in base BTF), "D" doesn't actually exist in the base BTF. When the binary search reaches the l == r condition,
it returns the index of "E" instead.
Quoted 4 lines
This requires an extra name comparison check after
btf_find_by_name_bsearchreturns, which could be avoided in the first loop iteration if the search directly
identified exact matches.
See above, I think this is misguided. There is nothing wrong with checking after bsearch returns *candidate* index, and you cannot avoid that for name+kind search.
Quoted 8 lines
int idx =
btf_find_by_name_bsearch(btf, name);for (int n = btf__type_cnt(btf); idx < n; idx++) { struct btf_type *t = btf__type_by_id(btf, idx); const char *tname = btf__str_by_offset(btf, t->name_off); if (strcmp(tname, name) != 0) <<< This check is redundant on the first loop iteration
Yes, I think this is absolutely OK and acceptable. Are you worried about the overhead of a single strcmp()? See below for notes on having single overall name and name+kind implementation using this approach.
Quoted 58 lines
when a matching index is found
return -ENOENT; if (btf_kind(t) == kind) return idx; }return
-ENOENT;I tested this with a simple program searching for 3 in {0, 1, 2, 4, 5}:
int
main(int argc, char *argv[]){ int values[] = {0, 1, 2, 4, 5}; int to_find; int i; to_find = atoi(argv[1]);; for (i = 0; i < ARRAY_SIZE(values); i++) printf("[%d] = %d\n", i , values[i]); printf("To Find %d\n", to_find); { int l, m, r; l = 0; r = ARRAY_SIZE(values) - 1; while (l <= r) { m = l + (r- l) / 2; if (values[m] >= to_find) { if (l == r) { printf("!!!! Found: [%d] ==> %d\n", r, values[r]); break; } r = m; } else { l = m + 1; } } printf("END: l: %d, r: %d\n", l, r); } return 0; }Output:
[0] = 0
[1] = 1
[2] = 2
[3] = 4
[4] = 5
To Find 3
!!!! Found: [3] ==> 4
END: l: 3, r: 3
Quoted 5 lines
The search returns index 3 (value 4), which is the first value ≥ 3, but since 4 ≠ 3,
it's not an exact match. Thus, the algorithm cannot guarantee a successful search
for the exact element without additional checks.
It was never a goal to find an exact match, yes, additional checks after the search is necessary to confirm name or name+kind match (and the latter will have to check name for every single item, except maybe the first one if we had exact match "guarantee", but I think this is absolutely unnecessary). And this is unavoidable for name+kind search. So instead of optimizing one extra strcmp() let's have uniform implementation for both name and name+kind searches. In fact, you can even have the same universal implementation of both if you treat kind == 0 as "don't care about kind".
Quoted 68 lines
Quoted 68 lines
that binary search loop doesn't loop forever and it returns correct index (or detects that no element can be found).
Quoted 64 lines
Quoted 64 lines
Quoted 64 lines
static
__s32btf_find_type_by_name_kind(const struct btf *btf, intstart_id,
const char*type_name,__u32kind){ const struct btf_type *t; const char *tname; int err = -ENOENT; __u32 total; if (!btf) goto out; if (start_id < btf->start_id) { err = btf_find_type_by_name_kind(btf->base_btf, start_id, type_name, kind); if (err == -ENOENT) start_id = btf->start_id; } if (err == -ENOENT) { if (btf_check_sorted((struct btf *)btf)) { /* binary search */ bool skip_first; int ret; /* return the leftmost with maching names */ ret = btf_find_type_by_name_bsearch(btf, type_name, start_id); if (ret < 0) goto out; /* skip kind checking */ if (kind == -1) return ret; total = btf__type_cnt(btf); skip_first = true; do { t = btf_type_by_id(btf, ret); if (btf_kind(t) != kind) { if (skip_first) { skip_first = false; continue; } } else if (skip_first) { return ret; } if (!t->name_off) break; tname = btf__str_by_offset(btf, t->name_off); if (tname && !strcmp(tname, type_name)) return ret; else break; } while (++ret < total); } else { /* linear search */ ... } }out:
return err; }
Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
Quoted 348 lines · Andrii Nakryiko
Quoted 155 lines · Donglin Peng
Quoted 152 lines · Andrii Nakryiko
Quoted 141 lines · Donglin Peng
Quoted 138 lines · Andrii Nakryiko
Quoted 45 lines · Donglin Peng
Quoted 43 lines · Eduard Zingerman
Quoted 22 lines · Andrii Nakryiko
Quoted 21 lines · Eduard Zingerman
On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
[...]
Quoted 15 lines
Review int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 912
Quoted 12 lines
(quoted diff) +7
-1@@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id) return type_id; } -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +/* + * Find BTF types with matching names within the [left, right] index range. + * On success, updates *left and *right to the boundaries of the matching range + * and returns the leftmost matching index. + */ +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name, + __s32 *left, __s32 *right)I thought we discussed this, why do you need "right"? Two binary searches where one would do just fine.
Quoted 6 lines
Quoted 2 lines
I think the idea is that there would be less strcmp's if there is a long sequence of items with identical names.
Sure, it's a tradeoff. But how long is the set of duplicate name entries we expect in kernel BTF? Additional O(logN) over 70K+ types with high likelihood will take more comparisons.
$ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head 51737 '(anon)' 277 'bpf_kfunc' 4 'long 3 'perf_aux_event' 3 'workspace' 2 'ata_acpi_gtm' 2 'avc_cache_stats' 2 'bh_accounting' 2 'bp_cpuinfo' 2 'bpf_fastcall'Quoted 5 lines
Quoted 5 lines
'
bpf_kfunc' is probably fordecl_tags.
So I agree with you regarding the second binary search, it is not necessary. But skipping all anonymous types (and thus having to maintainnr_sorted_types) might be useful, on each search two iterations would be wasted to skip those.fair enough, eliminating a big chunk of anonymous types is useful, let's do this
Quoted 51 lines
Thank you. After removing the redundant iterations, performance increased significantly compared with two iterations.
Test Case: Locate all 58,719 named types in vmlinux BTF Methodology:
./vmtest.sh -- ./test_progs -t btf_permute/perf -vTwo iterations:
| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,282 ms | Baseline | | Sorted (Binary) | 19 ms | 909x faster |One iteration:
Results:| Condition | Lookup Time | Improvement | |--------------------|-------------|-------------| | Unsorted (Linear) | 17,619 ms | Baseline | | Sorted (Binary) | 10 ms | 1762x faster |Here is the code implementation with a single iteration approach. I believe this scenario differs from
find_linfobecause we cannot determine in advance whether the specified type name will be found. Please correct me if I've misunderstood anything, and I welcome any guidance on this matter.static
__s32btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,__s32 start_id) { const struct btf_type *t; const char *tname; __s32 l, r, m, lmost = -ENOENT; int ret; /* found the leftmost btf_type that matches */ l = start_id; r = btf__type_cnt(btf) - 1; while (l <= r) { m = l + (r - l) / 2; t = btf_type_by_id(btf, m); if (!t->name_off) { ret = 1; } else { tname = btf__str_by_offset(btf, t->name_off); ret = !tname ? 1 : strcmp(tname, name); } if (ret < 0) { l = m + 1; } else {Quoted 8 lines
if (ret == 0) lmost = m; r = m - 1; } } return lmost; }There are different ways to implement this. At the highest level, implementation below just searches for leftmost element that has name
Quoted 1 line
= the one we are searching for. One complication is that such element
might not event exists. We can solve that checking ahead of time whether the rightmost type satisfied the condition, or we could do something similar to what I do in the loop below, where I allow l == r and then if that element has name >= to what we search, we exit because we found it. And if not, l will become larger than r, we'll break out of the loop and we'll know that we couldn't find the element. I haven't tested it, but please take a look and if you decide to go with such approach, do test it for edge cases, of course.
/*
* We are searching for the smallest r such that type #r's name is >= name.
* It might not exist, in which case we'll have l == r + 1.
*/
l =start_id;
r =btf__type_cnt(btf)- 1;while (l < r) { m = l + (r - l) / 2; t = btf_type_by_id(btf, m); tname = btf__str_by_offset(btf, t->name_off);Quoted 5 lines
Quoted 3 lines
if (strcmp(tname, name) >= 0) { if (l == r) return r; /* found it! */It seems that this if condition will never hold, because a while(l < r) loop
It should be
while (l <= r), I forgot to update it, but I mentioned that I do want to allow l == r condition.Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
is used. Moreover, even if the condition were to hold, it wouldn't guarantee a successful search.
Elaborate please on "wouldn't guarantee a successful search".
I think a successful search is that we can successfully find the element that we want.
Ok, I never intended to find exact match with that leftmost >= element as a primitive.
Quoted 27 lines
Quoted 25 lines
Quoted 11 lines
Quoted 9 lines
r = m; } else { l = m + 1; } }/* here we know given element doesn't exist, return index beyond end of types */ return
btf__type_cnt(btf);I think that return
-ENOENTseems more reasonable.Think how you will be using this inside
btf_find_type_by_name_kind():int idx =
btf_find_by_name_bsearch(btf, name);for (int n = btf__type_cnt(btf); idx < n; idx++) { struct btf_type *t = btf__type_by_id(btf, idx); const char *tname = btf__str_by_offset(btf, t->name_off); if (strcmp(tname, name) != 0) return -ENOENT; if (btf_kind(t) == kind) return idx; }Quoted 1 line
return
-ENOENT;Quoted 1 line
Thanks, it seems cleaner.
ok, great
Quoted 33 lines
Quoted 9 lines
Having
btf_find_by_name_bsearch()return-ENOENTinstead ofbtf__type_cnt()just will require extra explicit-ENOENThandling. And given the function now can return "error", we'd need to either handle other non-ENOENT errors, to at least leave comment that this should never happen, though interface itself looks like it could.Quoted 5 lines
This is relatively minor and its all internal implementation, so we can change that later. But I'm explaining my reasons for why I'd return index of non-existing type after the end, just like you'd do with pointer-based interfaces that return pointer after the last element.
Thanks, I see.
Quoted 16 lines
Quoted 15 lines
Quoted 10 lines
We could have checked instead whether
strcmp(btf__str_by_offset(btf, btf__type_by_id(btf, btf__type_cnt() - 1)->name_off), name)< 0 and exit early. That's just a bit more code duplication of essentially what we do inside the loop, so that if (l == r) seems fine to me, but I'm not married to this.Sorry, I believe that even if strcmp(btf__str_by_offset(btf, btf__type_by_id(btf,
btf__type_cnt()- 1)->name_off), name) >= 0, it still doesn't seem to guarantee that the search will definitely succeed.Quoted 6 lines
Quoted 2 lines
If the last element has >= name, search will definitely find at least that element. What do you mean by "succeed"? All I care about here is
Thank you. By "successful search," I mean finding the exact matching element we're looking for—not just the first element that meets the "≥" condition.
We don't have to find the exact match, just the leftmost >= element. For search by name+kind you will have to do linear search *anyways* and compare name for every single potential candidate (Except maybe the very first one as micro-optimization and complication, if we had exact matching leftmost element; but I don't care about that complication). So leftmost >= element is a universal "primitive" that allows you to implement exact by name or exact by name+kind search in exactly the same fashion.
Quoted 13 lines
Here's a concrete example to illustrate the issue:
Base BTF contains: {"A", "C", "E", "F"}
Split BTF contains: {"B", "D"}
Target search: "D" in split BTFThe current implementation recursively searches from the base BTF first. While "D" is lexicographically ≤ "F" (the last element in base BTF), "D" doesn't actually exist in the base BTF. When the binary search reaches the l == r condition,
it returns the index of "E" instead.Quoted 4 lines
This requires an extra name comparison check after
btf_find_by_name_bsearchreturns, which could be avoided in the first loop iteration if the search directly
identified exact matches.See above, I think this is misguided. There is nothing wrong with checking after bsearch returns *candidate* index, and you cannot avoid that for name+kind search.
Quoted 8 lines
int idx =
btf_find_by_name_bsearch(btf, name);for (int n = btf__type_cnt(btf); idx < n; idx++) { struct btf_type *t = btf__type_by_id(btf, idx); const char *tname = btf__str_by_offset(btf, t->name_off); if (strcmp(tname, name) != 0) <<< This check is redundant on the first loop iterationYes, I think this is absolutely OK and acceptable. Are you worried about the overhead of a single
strcmp()? See below for notes on having single overall name and name+kind implementation using this approach.Quoted 58 lines
when a matching index is found
return -ENOENT; if (btf_kind(t) == kind) return idx; }return
-ENOENT;I tested this with a simple program searching for 3 in {0, 1, 2, 4, 5}:
int
main(int argc, char *argv[]){ int values[] = {0, 1, 2, 4, 5}; int to_find; int i; to_find = atoi(argv[1]);; for (i = 0; i < ARRAY_SIZE(values); i++) printf("[%d] = %d\n", i , values[i]); printf("To Find %d\n", to_find); { int l, m, r; l = 0; r = ARRAY_SIZE(values) - 1; while (l <= r) { m = l + (r- l) / 2; if (values[m] >= to_find) { if (l == r) { printf("!!!! Found: [%d] ==> %d\n", r, values[r]); break; } r = m; } else { l = m + 1; } } printf("END: l: %d, r: %d\n", l, r); } return 0; }Output:
[0] = 0
[1] = 1
[2] = 2
[3] = 4
[4] = 5
To Find 3
!!!! Found: [3] ==> 4
END: l: 3, r: 3Quoted 5 lines
The search returns index 3 (value 4), which is the first value ≥ 3, but since 4 ≠ 3,
it's not an exact match. Thus, the algorithm cannot guarantee a successful search
for the exact element without additional checks.
Quoted 9 lines
It was never a goal to find an exact match, yes, additional checks after the search is necessary to confirm name or name+kind match (and the latter will have to check name for every single item, except maybe the first one if we had exact match "guarantee", but I think this is absolutely unnecessary). And this is unavoidable for name+kind search. So instead of optimizing one extra
strcmp()let's have uniform implementation for both name and name+kind searches. In fact, you can even have the same universal implementation of both if you treat kind == 0 as "don't care about kind".
Thanks, I'll apply this suggestion in the next version.
Quoted 70 lines
Quoted 70 lines
Quoted 70 lines
that binary search loop doesn't loop forever and it returns correct index (or detects that no element can be found).
Quoted 64 lines
Quoted 64 lines
Quoted 64 lines
static
__s32btf_find_type_by_name_kind(const struct btf *btf, intstart_id,
const char*type_name,__u32kind){ const struct btf_type *t; const char *tname; int err = -ENOENT; __u32 total; if (!btf) goto out; if (start_id < btf->start_id) { err = btf_find_type_by_name_kind(btf->base_btf, start_id, type_name, kind); if (err == -ENOENT) start_id = btf->start_id; } if (err == -ENOENT) { if (btf_check_sorted((struct btf *)btf)) { /* binary search */ bool skip_first; int ret; /* return the leftmost with maching names */ ret = btf_find_type_by_name_bsearch(btf, type_name, start_id); if (ret < 0) goto out; /* skip kind checking */ if (kind == -1) return ret; total = btf__type_cnt(btf); skip_first = true; do { t = btf_type_by_id(btf, ret); if (btf_kind(t) != kind) { if (skip_first) { skip_first = false; continue; } } else if (skip_first) { return ret; } if (!t->name_off) break; tname = btf__str_by_offset(btf, t->name_off); if (tname && !strcmp(tname, type_name)) return ret; else break; } while (++ret < total); } else { /* linear search */ ... } }out:
return err; }
RFC PATCH v4 4/7 libbpf: Implement lazy sorting validation for binary search optimization
In reply to Donglin PengFrom: pengdonglin <[email protected]>
This patch adds lazy validation of BTF type ordering to determine if types are sorted by name. The check is performed on first access and cached, enabling efficient binary search for sorted BTF while maintaining linear search fallback for unsorted cases.
--- tools/lib/bpf/btf.c | 76 +++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 74 insertions(+), 2 deletions(-)
tools/lib/bpf/btf.c +74 -2
@@ -26,6 +26,10 @@#define BTF_MAX_NR_TYPES 0x7fffffffU#define BTF_MAX_STR_OFFSET 0x7fffffffU +/* sort verification occurs lazily upon first btf_find_type_by_name_kind() +* call +*/ +#define BTF_NEED_SORT_CHECK ((__u32)-1)static struct btf_type btf_void;
@@ -96,6 +100,10 @@ struct btf {* - doesn't include special [0] void type; * - for split BTF counts number of sorted and named types added on * top of base BTF. +* - BTF_NEED_SORT_CHECK value indicates sort validation will be performed +* on first call to btf_find_type_by_name_kind. +* - zero value indicates applied sorting check with unsorted BTF or no +* named types. */ __u32 nr_sorted_types;/* if not NULL, points to the base BTF on top of which the current
@@ -903,8 +911,67 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; } -/* -* Find BTF types with matching names within the [left, right] index range. +static int btf_compare_type_names (const void *a,const void *b,void *priv) +{ +struct btf *btf = (struct btf *)priv; +struct btf_type *ta =btf_type_by_id (btf, *(__u32 *)a); +struct btf_type *tb =btf_type_by_id (btf, *(__u32 *)b); +const char *na, *nb; +bool anon_a, anon_b; + + na =btf__str_by_offset (btf, ta->name_off); + nb =btf__str_by_offset (btf, tb->name_off); + anon_a =str_is_empty (na); + anon_b =str_is_empty (nb); + +if (anon_a && !anon_b) +return 1 ; +if (!anon_a && anon_b) +return -1 ; +if (anon_a && anon_b) +return 0 ; + +return strcmp (na, nb); +} + +/* Verifies BTF type ordering by name and counts named types. +* +* Checks that types are sorted in ascending order with named types +* before anonymous ones. If verified, sets nr_sorted_types to the +* number of named types. +*/ +static void btf_check_sorted (struct btf *btf,int start_id) +{ +const struct btf_type *t; +int i, n, nr_sorted_types; + +if (likely (btf->nr_sorted_types !=BTF_NEED_SORT_CHECK )) +return ; + btf->nr_sorted_types =0 ; + +if (btf->nr_types <2 ) +return ; + + nr_sorted_types =0 ; + n =btf__type_cnt (btf); +for (n--, i = start_id; i < n; i++) { +int k = i +1 ; + +if (btf_compare_type_names (&i, &k, btf) >0 ) +return ; + t =btf_type_by_id (btf, k); +if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; + } + + t =btf_type_by_id (btf, start_id); +if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; +if (nr_sorted_types) + btf->nr_sorted_types = nr_sorted_types; +} + +/* Find BTF types with matching names within the [left, right] index range. * On success, updates *left and *right to the boundaries of the matching range * and returns the leftmost matching index. */
@@ -978,6 +1045,8 @@ static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_id, }if (err == -ENOENT ) { +btf_check_sorted ((struct btf *)btf, btf->start_id); +if (btf->nr_sorted_types) {/* binary search */ __s32 l, r;
@@ -1102,6 +1171,7 @@ static struct btf *btf_new_empty(struct btf *base_btf) btf->fd =-1 ; btf->ptr_sz =sizeof (void *); btf->swapped_endian = false; + btf->nr_sorted_types =BTF_NEED_SORT_CHECK ;if (base_btf) { btf->base_btf = base_btf;
@@ -1153,6 +1223,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b btf->start_id =1 ; btf->start_str_off =0 ; btf->fd =-1 ; + btf->nr_sorted_types =BTF_NEED_SORT_CHECK ;if (base_btf) { btf->base_btf = base_btf;
@@ -1811,6 +1882,7 @@ static void btf_invalidate_raw_data(struct btf *btf)free (btf->raw_data_swapped); btf->raw_data_swapped =NULL ; } + btf->nr_sorted_types =BTF_NEED_SORT_CHECK ; }/* Ensure BTF is ready to be modified (by splitting into a three memory
Signature · 1 line
2.34.1
Eduard Zingerman
maintainerRe: [RFC PATCH v4 4/7] libbpf: Implement lazy sorting validation for binary search optimization
Quoted 34 lines · Donglin Peng
From: pengdonglin <[email protected]>
This patch adds lazy validation of BTF type ordering to determine if types are sorted by name. The check is performed on first access and cached, enabling efficient binary search for sorted BTF while maintaining linear search fallback for unsorted cases.
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 76 +++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 74 insertions(+), 2 deletions(-)tools/lib/bpf/btf.c +4
-0@@ -26,6 +26,10 @@#define BTF_MAX_NR_TYPES 0x7fffffffU#define BTF_MAX_STR_OFFSET 0x7fffffffU +/* sort verification occurs lazily upon first btf_find_type_by_name_kind() +* call +*/ +#define BTF_NEED_SORT_CHECK ((__u32)-1)static struct btf_type btf_void;
tools/lib/bpf/btf.c struct btf { · line 106
Quoted 7 lines
tools/lib/bpf/btf.c +4
-0@@ -96,6 +100,10 @@ struct btf {* - doesn't include special [0] void type; * - for split BTF counts number of sorted and named types added on * top of base BTF. +* - BTF_NEED_SORT_CHECK value indicates sort validation will be performed +* on first call to btf_find_type_by_name_kind. +* - zero value indicates applied sorting check with unsorted BTF or no +* named types.
And this can be another flag.
Quoted 43 lines
tools/lib/bpf/btf.c +34
-2*/ __u32 nr_sorted_types;/* if not NULL, points to the base BTF on top of which the current @@ -903,8 +911,67 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; } -/* -* Find BTF types with matching names within the [left, right] index range. +static int btf_compare_type_names (const void *a,const void *b,void *priv) +{ +struct btf *btf = (struct btf *)priv; +struct btf_type *ta =btf_type_by_id (btf, *(__u32 *)a); +struct btf_type *tb =btf_type_by_id (btf, *(__u32 *)b); +const char *na, *nb; +bool anon_a, anon_b; + + na =btf__str_by_offset (btf, ta->name_off); + nb =btf__str_by_offset (btf, tb->name_off); + anon_a =str_is_empty (na); + anon_b =str_is_empty (nb); + +if (anon_a && !anon_b) +return 1 ; +if (!anon_a && anon_b) +return -1 ; +if (anon_a && anon_b) +return 0 ; + +return strcmp (na, nb); +} + +/* Verifies BTF type ordering by name and counts named types. +* +* Checks that types are sorted in ascending order with named types +* before anonymous ones. If verified, sets nr_sorted_types to the +* number of named types. +*/ +static void btf_check_sorted (struct btf *btf,int start_id) +{ +const struct btf_type *t; +int i, n, nr_sorted_types; +
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 957
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+if (likely (btf->nr_sorted_types !=BTF_NEED_SORT_CHECK )) +return ; + btf->nr_sorted_types =0 ; + +if (btf->nr_types <2 ) +return ; + + nr_sorted_types =0 ; + n =btf__type_cnt (btf); +for (n--, i = start_id; i < n; i++) {
^^^
why not -1 one line before?
Quoted 4 lines
tools/lib/bpf/btf.c +4
-0+int k = i +1 ; + +if (btf_compare_type_names (&i, &k, btf) >0 ) +return ;
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 971
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ t =btf_type_by_id (btf, k); +if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; + } + + t =btf_type_by_id (btf, start_id); +if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; +if (nr_sorted_types) + btf->nr_sorted_types = nr_sorted_types;
I think that maintaining nr_sorted_types only for named types is an unnecessary complication. Binary search will skip those anyway, probably in one iteration.
Quoted 39 lines
tools/lib/bpf/btf.c +8
-0+} + +/* Find BTF types with matching names within the [left, right] index range. * On success, updates *left and *right to the boundaries of the matching range * and returns the leftmost matching index. */ @@ -978,6 +1045,8 @@ static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_id, }if (err == -ENOENT ) { +btf_check_sorted ((struct btf *)btf, btf->start_id); +if (btf->nr_sorted_types) {/* binary search */ __s32 l, r;@@ -1102,6 +1171,7 @@ static struct btf *btf_new_empty(struct btf *base_btf) btf->fd =-1 ; btf->ptr_sz =sizeof (void *); btf->swapped_endian = false; + btf->nr_sorted_types =BTF_NEED_SORT_CHECK ;if (base_btf) { btf->base_btf = base_btf;@@ -1153,6 +1223,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b btf->start_id =1 ; btf->start_str_off =0 ; btf->fd =-1 ; + btf->nr_sorted_types =BTF_NEED_SORT_CHECK ;if (base_btf) { btf->base_btf = base_btf;@@ -1811,6 +1882,7 @@ static void btf_invalidate_raw_data(struct btf *btf)free (btf->raw_data_swapped); btf->raw_data_swapped =NULL ; } + btf->nr_sorted_types =BTF_NEED_SORT_CHECK ; }/* Ensure BTF is ready to be modified (by splitting into a three memory
RFC PATCH v4 5/7 btf: Optimize type lookup with binary search
In reply to Donglin PengFrom: pengdonglin <[email protected]>
Improve btf_find_by_name_kind() performance by adding binary search support for sorted types. Falls back to linear search for compatibility.
--- kernel/bpf/btf.c | 111 ++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 101 insertions(+), 10 deletions(-)
kernel/bpf/btf.c +101 -10
@@ -259,6 +259,7 @@ struct btf {void *nohdr_data;struct btf_header hdr;u32 nr_types;/* includes VOID for base BTF */ +u32 nr_sorted_types;/* exclude VOID for base BTF */ u32 types_size;u32 data_size;refcount_t refcnt;
@@ -494,6 +495,11 @@ static bool btf_type_is_modifier(const struct btf_type *t)return false; } +static int btf_start_id (const struct btf *btf) +{ +return btf->start_id + (btf->base_btf ?0 :1 ); +} +bool btf_type_is_void (const struct btf_type *t) {return t == &btf_void;
@@ -544,24 +550,109 @@ u32 btf_nr_types(const struct btf *btf)return total; } -s32 btf_find_by_name_kind (const struct btf *btf,const char *name,u8 kind) +/* Find BTF types with matching names within the [left, right] index range. +* On success, updates *left and *right to the boundaries of the matching range +* and returns the leftmost matching index. +*/ +static s32 btf_find_by_name_kind_bsearch (const struct btf *btf,const char *name, +s32 *left,s32 *right) {const struct btf_type *t;const char *tname; -u32 i, total; +s32 l, r, m, lmost, rmost; +int ret; - total =btf_nr_types (btf); -for (i =1 ; i < total; i++) { - t =btf_type_by_id (btf, i); -if (BTF_INFO_KIND (t->info) != kind) -continue ; +/* found the leftmost btf_type that matches */ + l = *left; + r = *right; + lmost =-1 ; +while (l <= r) { + m = l + (r - l) /2 ; + t =btf_type_by_id (btf, m); + tname =btf_name_by_offset (btf, t->name_off); + ret =strcmp (tname, name); +if (ret <0 ) { + l = m +1 ; + }else { +if (ret ==0 ) + lmost = m; + r = m -1 ; + } + } +if (lmost ==-1 ) +return -ENOENT ; + +/* found the rightmost btf_type that matches */ + l = lmost; + r = *right; + rmost =-1 ; +while (l <= r) { + m = l + (r - l) /2 ; + t =btf_type_by_id (btf, m); tname =btf_name_by_offset (btf, t->name_off); -if (!strcmp (tname, name)) -return i; + ret =strcmp (tname, name); +if (ret <=0 ) { +if (ret ==0 ) + rmost = m; + l = m +1 ; + }else { + r = m -1 ; + } } -return -ENOENT ; + *left = lmost; + *right = rmost; +return lmost; +} + +s32 btf_find_by_name_kind (const struct btf *btf,const char *name,u8 kind) +{ +const struct btf *base_btf =btf_base_btf (btf);; +const struct btf_type *t; +const char *tname; +int err = -ENOENT ; + +if (base_btf) + err =btf_find_by_name_kind (base_btf, name, kind); + +if (err == -ENOENT ) { +if (btf->nr_sorted_types) { +/* binary search */ +s32 l, r; +int ret; + + l =btf_start_id (btf); + r = l + btf->nr_sorted_types -1 ; + ret =btf_find_by_name_kind_bsearch (btf, name, &l, &r); +if (ret <0 ) + goto out; +/* found the leftmost btf_type that matches */ +while (l <= r) { + t =btf_type_by_id (btf, l); +if (BTF_INFO_KIND (t->info) == kind) +return l; + l++; + } + }else { +/* linear search */ +u32 i, total; + + total =btf_nr_types (btf); +for (i =btf_start_id (btf); i < total; i++) { + t =btf_type_by_id (btf, i); +if (BTF_INFO_KIND (t->info) != kind) +continue ; + + tname =btf_name_by_offset (btf, t->name_off); +if (!strcmp (tname, name)) +return i; + } + } + } + +out: +return err; }s32 bpf_find_btf_id (const char *name,u32 kind,struct btf **btf_p)
Signature · 1 line
2.34.1
Re: [RFC PATCH v4 5/7] btf: Optimize type lookup with binary search
Quoted 112 lines · Donglin Peng
From: pengdonglin <[email protected]>
Improve
btf_find_by_name_kind()performance by adding binary search support for sorted types. Falls back to linear search for compatibility.Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- kernel/bpf/btf.c | 111 ++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 101 insertions(+), 10 deletions(-)kernel/bpf/btf.c +55
-10@@ -259,6 +259,7 @@ struct btf {void *nohdr_data;struct btf_header hdr;u32 nr_types;/* includes VOID for base BTF */ +u32 nr_sorted_types;/* exclude VOID for base BTF */ u32 types_size;u32 data_size;refcount_t refcnt;@@ -494,6 +495,11 @@ static bool btf_type_is_modifier(const struct btf_type *t)return false; } +static int btf_start_id (const struct btf *btf) +{ +return btf->start_id + (btf->base_btf ?0 :1 ); +} +bool btf_type_is_void (const struct btf_type *t) {return t == &btf_void;@@ -544,24 +550,109 @@ u32 btf_nr_types(const struct btf *btf)return total; } -s32 btf_find_by_name_kind (const struct btf *btf,const char *name,u8 kind) +/* Find BTF types with matching names within the [left, right] index range. +* On success, updates *left and *right to the boundaries of the matching range +* and returns the leftmost matching index. +*/ +static s32 btf_find_by_name_kind_bsearch (const struct btf *btf,const char *name, +s32 *left,s32 *right) {const struct btf_type *t;const char *tname; -u32 i, total; +s32 l, r, m, lmost, rmost; +int ret; - total =btf_nr_types (btf); -for (i =1 ; i < total; i++) { - t =btf_type_by_id (btf, i); -if (BTF_INFO_KIND (t->info) != kind) -continue ; +/* found the leftmost btf_type that matches */ + l = *left; + r = *right; + lmost =-1 ; +while (l <= r) { + m = l + (r - l) /2 ; + t =btf_type_by_id (btf, m); + tname =btf_name_by_offset (btf, t->name_off); + ret =strcmp (tname, name); +if (ret <0 ) { + l = m +1 ; + }else { +if (ret ==0 ) + lmost = m; + r = m -1 ; + } + } +if (lmost ==-1 ) +return -ENOENT ; + +/* found the rightmost btf_type that matches */ + l = lmost; + r = *right; + rmost =-1 ; +while (l <= r) { + m = l + (r - l) /2 ; + t =btf_type_by_id (btf, m); tname =btf_name_by_offset (btf, t->name_off); -if (!strcmp (tname, name)) -return i; + ret =strcmp (tname, name); +if (ret <=0 ) { +if (ret ==0 ) + rmost = m; + l = m +1 ; + }else { + r = m -1 ; + } } -return -ENOENT ; + *left = lmost; + *right = rmost; +return lmost; +} + +s32 btf_find_by_name_kind (const struct btf *btf,const char *name,u8 kind)
kernel/bpf/btf.c u32 btf_nr_types(const struct btf *btf) · line 619
Quoted 10 lines
kernel/bpf/btf.c +10
-0+{ +const struct btf *base_btf =btf_base_btf (btf);; +const struct btf_type *t; +const char *tname; +int err = -ENOENT ; + +if (base_btf) + err =btf_find_by_name_kind (base_btf, name, kind); + +if (err == -ENOENT ) {
Please avoid the needless indent.
kernel/bpf/btf.c u32 btf_nr_types(const struct btf *btf) · line 620
Quoted 1 line
kernel/bpf/btf.c +1
-0+if (btf->nr_sorted_types) {
looks buggy,
since you init it to btf->nr_sorted_types = BTF_NEED_SORT_CHECK;
Also AI is right. Init the field in the same patch.
pw-bot: cr
Re: [RFC PATCH v4 5/7] btf: Optimize type lookup with binary search
Quoted 118 lines · Alexei Starovoitov
Quoted 116 lines · Donglin Peng
From: pengdonglin <[email protected]>
Improve
btf_find_by_name_kind()performance by adding binary search support for sorted types. Falls back to linear search for compatibility.Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- kernel/bpf/btf.c | 111 ++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 101 insertions(+), 10 deletions(-)kernel/bpf/btf.c +59
-10@@ -259,6 +259,7 @@ struct btf {void *nohdr_data;struct btf_header hdr;u32 nr_types;/* includes VOID for base BTF */ +u32 nr_sorted_types;/* exclude VOID for base BTF */ u32 types_size;u32 data_size;refcount_t refcnt;@@ -494,6 +495,11 @@ static bool btf_type_is_modifier(const struct btf_type *t)return false; } +static int btf_start_id (const struct btf *btf) +{ +return btf->start_id + (btf->base_btf ?0 :1 ); +} +bool btf_type_is_void (const struct btf_type *t) {return t == &btf_void;@@ -544,24 +550,109 @@ u32 btf_nr_types(const struct btf *btf)return total; } -s32 btf_find_by_name_kind (const struct btf *btf,const char *name,u8 kind) +/* Find BTF types with matching names within the [left, right] index range. +* On success, updates *left and *right to the boundaries of the matching range +* and returns the leftmost matching index. +*/ +static s32 btf_find_by_name_kind_bsearch (const struct btf *btf,const char *name, +s32 *left,s32 *right) {const struct btf_type *t;const char *tname; -u32 i, total; +s32 l, r, m, lmost, rmost; +int ret; - total =btf_nr_types (btf); -for (i =1 ; i < total; i++) { - t =btf_type_by_id (btf, i); -if (BTF_INFO_KIND (t->info) != kind) -continue ; +/* found the leftmost btf_type that matches */ + l = *left; + r = *right; + lmost =-1 ; +while (l <= r) { + m = l + (r - l) /2 ; + t =btf_type_by_id (btf, m); + tname =btf_name_by_offset (btf, t->name_off); + ret =strcmp (tname, name); +if (ret <0 ) { + l = m +1 ; + }else { +if (ret ==0 ) + lmost = m; + r = m -1 ; + } + } +if (lmost ==-1 ) +return -ENOENT ; + +/* found the rightmost btf_type that matches */ + l = lmost; + r = *right; + rmost =-1 ; +while (l <= r) { + m = l + (r - l) /2 ; + t =btf_type_by_id (btf, m); tname =btf_name_by_offset (btf, t->name_off); -if (!strcmp (tname, name)) -return i; + ret =strcmp (tname, name); +if (ret <=0 ) { +if (ret ==0 ) + rmost = m; + l = m +1 ; + }else { + r = m -1 ; + } } -return -ENOENT ; + *left = lmost; + *right = rmost; +return lmost; +} + +s32 btf_find_by_name_kind (const struct btf *btf,const char *name,u8 kind) +{ +const struct btf *base_btf =btf_base_btf (btf);; +const struct btf_type *t; +const char *tname;
Quoted 8 lines
kernel/bpf/btf.c u32 btf_nr_types(const struct btf *btf) · line 619
Quoted 6 lines
kernel/bpf/btf.c +6
-0+int err = -ENOENT ; + +if (base_btf) + err =btf_find_by_name_kind (base_btf, name, kind); + +if (err == -ENOENT ) {Please avoid the needless indent.
Thanks. I will fix it.
Quoted 7 lines
kernel/bpf/btf.c u32 btf_nr_types(const struct btf *btf) · line 620
Quoted 2 lines
kernel/bpf/btf.c +1
-0+if (btf->nr_sorted_types) {looks buggy,
since you init it tobtf->nr_sorted_types=BTF_NEED_SORT_CHECK;Also AI is right. Init the field in the same patch.
Thanks. I will fix it.
Quoted 2 lines
pw-bot: cr
RFC PATCH v4 6/7 btf: Add lazy sorting validation for binary search
In reply to Donglin PengFrom: pengdonglin <[email protected]>
Implement lazy validation of BTF type ordering to enable efficient binary search for sorted BTF while maintaining linear search fallback for unsorted cases.
--- kernel/bpf/btf.c | 66 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+)
kernel/bpf/btf.c +66 -0
@@ -192,6 +192,8 @@*/ #define BTF_MAX_SIZE (16 * 1024 * 1024) +#define BTF_NEED_SORT_CHECK ((u32)-1) +#define for_each_member_from (i, from, struct_type, member) \ for (i = from, member = btf_type_member(struct_type) + from; \ i < btf_type_vlen(struct_type); \
@@ -550,6 +552,65 @@ u32 btf_nr_types(const struct btf *btf)return total; } +static int btf_compare_type_names (const void *a,const void *b,void *priv) +{ +struct btf *btf = (struct btf *)priv; +const struct btf_type *ta =btf_type_by_id (btf, *(__u32 *)a); +const struct btf_type *tb =btf_type_by_id (btf, *(__u32 *)b); +const char *na, *nb; + +if (!ta->name_off && tb->name_off) +return 1 ; +if (ta->name_off && !tb->name_off) +return -1 ; +if (!ta->name_off && !tb->name_off) +return 0 ; + + na =btf_name_by_offset (btf, ta->name_off); + nb =btf_name_by_offset (btf, tb->name_off); +return strcmp (na, nb); +} + +/* Verifies BTF type ordering by name and counts named types. +* +* Checks that types are sorted in ascending order with named types +* before anonymous ones. If verified, sets nr_sorted_types to the +* number of named types. +*/ +static void btf_check_sorted (struct btf *btf,int start_id) +{ +const struct btf_type *t; +int i, n, nr_sorted_types; + +if (likely (btf->nr_sorted_types !=BTF_NEED_SORT_CHECK )) +return ; + + btf->nr_sorted_types =0 ; + +if (btf->nr_types <2 ) +return ; + + nr_sorted_types =0 ; + n =btf_nr_types (btf); +for (n--, i = start_id; i < n; i++) { +int k = i +1 ; + +if (btf_compare_type_names (&i, &k, btf) >0 ) +return ; + + t =btf_type_by_id (btf, k); +if (t->name_off) + nr_sorted_types++; + } + + t =btf_type_by_id (btf, start_id); +if (t->name_off) + nr_sorted_types++; + +if (nr_sorted_types) + btf->nr_sorted_types = nr_sorted_types; +} +/* Find BTF types with matching names within the [left, right] index range. * On success, updates *left and *right to the boundaries of the matching range * and returns the leftmost matching index.
@@ -617,6 +678,8 @@ s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) err =btf_find_by_name_kind (base_btf, name, kind);if (err == -ENOENT ) { +btf_check_sorted ((struct btf *)btf,btf_start_id (btf)); +if (btf->nr_sorted_types) {/* binary search */ s32 l, r;
@@ -5882,6 +5945,7 @@ static struct btf *btf_parse(const union bpf_attr *attr, bpfptr_t uattr, u32 uat goto errout; } env->btf = btf; + btf->nr_sorted_types =BTF_NEED_SORT_CHECK ; data =kvmalloc (attr->btf_size,GFP_KERNEL | __GFP_NOWARN);if (!data) {
@@ -6301,6 +6365,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name btf->data = data; btf->data_size = data_size; btf->kernel_btf = true; + btf->nr_sorted_types =BTF_NEED_SORT_CHECK ;snprintf (btf->name,sizeof (btf->name),"%s" , name); err =btf_parse_hdr (env);
@@ -6418,6 +6483,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data, btf->start_id = base_btf->nr_types; btf->start_str_off = base_btf->hdr.str_len; btf->kernel_btf = true; + btf->nr_sorted_types =BTF_NEED_SORT_CHECK ;snprintf (btf->name,sizeof (btf->name),"%s" , module_name); btf->data =kvmemdup (data, data_size,GFP_KERNEL | __GFP_NOWARN);
Signature · 1 line
2.34.1
RFC PATCH v4 7/7 selftests/bpf: Add test cases for btf__permute functionality
In reply to Donglin PengFrom: pengdonglin <[email protected]>
This patch introduces test cases for the btf__permute function to ensure it works correctly with both base BTF and split BTF scenarios.
The test suite includes:
- test_permute_base: Validates permutation on standalone BTF
- test_permute_split: Tests permutation on split BTF with base dependencies
Each test verifies that type IDs are correctly rearranged and type references are properly updated after permutation operations.
--- .../selftests/bpf/prog_tests/btf_permute.c | 142 ++++++++++++++++++ 1 file changed, 142 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.c
tools/testing/selftests/bpf/prog_tests/btf_permute.c new file +142 -0
@@ -0,0 +1,142 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2025 Xiaomi */ + +#include <test_progs.h> +#include <bpf/btf.h> +#include "btf_helpers.h" + +/* ensure btf__permute work as expected with base_btf */ +static void test_permute_base (void ) +{ +struct btf *btf; +__u32 permute_ids[6 ]; +int err; + + btf =btf__new_empty (); +if (!ASSERT_OK_PTR (btf,"empty_main_btf" )) +return ; + +btf__add_int (btf,"int" ,4 ,BTF_INT_SIGNED );/* [1] int */ +btf__add_ptr (btf,1 );/* [2] ptr to int */ +btf__add_struct (btf,"s1" ,4 );/* [3] struct s1 { */ +btf__add_field (btf,"m" ,1 ,0 ,0 );/* int m; */ +/* } */ +btf__add_struct (btf,"s2" ,4 );/* [4] struct s2 { */ +btf__add_field (btf,"m" ,1 ,0 ,0 );/* int m; */ +/* } */ +btf__add_func_proto (btf,1 );/* [5] int (*)(int *p); */ +btf__add_func_param (btf,"p" ,2 ); +btf__add_func (btf,"f" ,BTF_FUNC_STATIC ,5 );/* [6] int f(int *p); */ + +VALIDATE_RAW_BTF ( + btf, +"[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[2] PTR '(anon)' type_id=1" , +"[3] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[4] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[6] FUNC 'f' type_id=5 linkage=static" ); + + permute_ids[0 ] =4 ;/* struct s2 */ + permute_ids[1 ] =3 ;/* struct s1 */ + permute_ids[2 ] =5 ;/* int (*)(int *p) */ + permute_ids[3 ] =1 ;/* int */ + permute_ids[4 ] =6 ;/* int f(int *p) */ + permute_ids[5 ] =2 ;/* ptr to int */ + err =btf__permute (btf, permute_ids,NULL ); +if (!ASSERT_OK (err,"btf__permute" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[3] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=6" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] FUNC 'f' type_id=3 linkage=static" , +"[6] PTR '(anon)' type_id=4" ); + +done: +btf__free (btf); +} + +/* ensure btf__permute work as expected with split_btf */ +static void test_permute_split (void ) +{ +struct btf *split_btf =NULL , *base_btf =NULL ; +__u32 permute_ids[4 ]; +int err; + + base_btf =btf__new_empty (); +if (!ASSERT_OK_PTR (base_btf,"empty_main_btf" )) +return ; + +btf__add_int (base_btf,"int" ,4 ,BTF_INT_SIGNED );/* [1] int */ +btf__add_ptr (base_btf,1 );/* [2] ptr to int */ +VALIDATE_RAW_BTF ( + base_btf, +"[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[2] PTR '(anon)' type_id=1" ); + split_btf =btf__new_empty_split (base_btf); +if (!ASSERT_OK_PTR (split_btf,"empty_split_btf" )) + goto cleanup; +btf__add_struct (split_btf,"s1" ,4 );/* [3] struct s1 { */ +btf__add_field (split_btf,"m" ,1 ,0 ,0 );/* int m; */ +/* } */ +btf__add_struct (split_btf,"s2" ,4 );/* [4] struct s2 { */ +btf__add_field (split_btf,"m" ,1 ,0 ,0 );/* int m; */ +/* } */ +btf__add_func_proto (split_btf,1 );/* [5] int (*)(int p); */ +btf__add_func_param (split_btf,"p" ,2 ); +btf__add_func (split_btf,"f" ,BTF_FUNC_STATIC ,5 );/* [6] int f(int *p); */ + +VALIDATE_RAW_BTF ( + split_btf, +"[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[2] PTR '(anon)' type_id=1" , +"[3] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[4] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[6] FUNC 'f' type_id=5 linkage=static" ); + + permute_ids[0 ] =6 ;/* int f(int *p) */ + permute_ids[1 ] =3 ;/* struct s1 */ + permute_ids[2 ] =5 ;/* int (*)(int *p) */ + permute_ids[3 ] =4 ;/* struct s2 */ + err =btf__permute (split_btf, permute_ids,NULL ); +if (!ASSERT_OK (err,"btf__permute" )) + goto cleanup; + +VALIDATE_RAW_BTF ( + split_btf, +"[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[2] PTR '(anon)' type_id=1" , +"[3] FUNC 'f' type_id=5 linkage=static" , +"[4] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[6] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +cleanup: +btf__free (split_btf); +btf__free (base_btf); +} + +void test_btf_permute (void ) +{ +if (test__start_subtest ("permute_base" )) +test_permute_base (); +if (test__start_subtest ("permute_split" )) +test_permute_split (); +}
Signature · 1 line
2.34.1
Re: [RFC PATCH v4 7/7] selftests/bpf: Add test cases for btf__permute functionality
Quoted 12 lines · Donglin Peng
From: pengdonglin <[email protected]>
This patch introduces test cases for the
btf__permutefunction to ensure it works correctly with both base BTF and split BTF scenarios.The test suite includes:
-test_permute_base: Validates permutation on standalone BTF
-test_permute_split: Tests permutation on split BTF with base dependenciesEach test verifies that type IDs are correctly rearranged and type references are properly updated after permutation operations.
Quoted 8 lines
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>---
[...]