Improve the performance of BTF type lookups with binary search
Subsystems (5)
v7 cover Improve the performance of BTF type lookups with binary search
From: pengdonglin <[email protected]>
This patch series introduces significant performance improvements (~1785x) for BTF type lookups by implementing type permutation and binary search optimizations.
## Overview
The series addresses the performance limitations of linear search in large BTF instances by:
1. Adding BTF permutation support
2. Sorting BTF during the building phase
3. Implementing binary search optimization
## Key Changes
### Patch 1: libbpf: Add BTF permutation support for type reordering
- Introduces btf__permute interface for BTF type reorganization
### Patch 2: selftests/bpf: Add test cases for btf__permute functionality
- Validates functionality across both base BTF and split BTF scenarios
### Patch 3: tools/resolve_btfids: Add --btf_sort option for BTF name sorting
- Implements BTF sorting via resolve_btfids during build process
### Patch 4: libbpf: Optimize type lookup with binary search for sorted BTF
- Implements binary search algorithm for sorted BTF instances
- Maintains linear search fallback for backward compatibility
### Patch 5: libbpf: Implement sorting validation for binary search optimization
- Adds sorting validation during BTF parsing
### Patch 6: btf: Optimize type lookup with binary search
- Ports binary search optimization to kernel-side BTF implementation
### Patch 7: btf: Add sorting validation for binary search
- Implements named type counting for vmlinux and kernel module BTF sorting validation
## Performance Impact Analysis
Repo: https://github.com/pengdonglin137/btf_sort_test
### Lookup Performance Comparison
Test Case: Locate all 58,718 named types in vmlinux BTF Methodology:
./vmtest.sh -- ./test_progs -t btf_permute/perf -v
Results:
| Condition | Lookup Time | Improvement | |--------------------|-------------|--------------| | Unsorted (Linear) | 16,666.5 ms | Baseline | | Sorted (Binary) | 9.3 ms | 1785x faster |
Analysis:
The binary search implementation reduces lookup time from 16.7 seconds to 9.3 milliseconds, achieving a **1785x** speedup for large-scale type queries.
## Changelog
v7:
- btf__permute API refinement: Adjusted id_map and id_map_cnt parameter usage so that for base BTF, id_map[0] now contains the new id of original type id 1 (instead of VOID type id 0), improving logical consistency
- Selftest updates: Modified test cases to align with the API usage changes
- Refactor the code of resolve_btfids
v6:
- Link: https://lore.kernel.org/all/[email protected]/
- ID Map-based reimplementation of btf__permute (Andrii)
- Build-time BTF sorting using resolve_btfids (Alexei, Eduard)
- Binary search method refactoring (Andrii)
- Enhanced selftest coverage
v5:
- Link: https://lore.kernel.org/all/[email protected]/
- Refactor binary search implementation for improved efficiency (Thanks to Andrii and Eduard)
- Extend btf__permute interface with 'ids_sz' parameter to support type dropping feature (suggested by Andrii). Plan subsequent reimplementation of id_map version for comparative analysis with current sequence interface
- Add comprehensive test coverage for type dropping functionality
- Enhance function comment clarity and accuracy
v4:
- Link: https://lore.kernel.org/all/[email protected]/
- Abstracted btf_dedup_remap_types logic into a helper function (suggested by Eduard).
- Removed btf_sort.c and implemented sorting separately for libbpf and kernel (suggested by Andrii).
- Added test cases for both base BTF and split BTF scenarios (suggested by Eduard).
- Added validation for name-only sorting of types (suggested by Andrii)
- Refactored btf__permute implementation to reduce complexity (suggested by Andrii)
- Add doc comments for btf__permute (suggested by Andrii)
v3:
- Link: https://lore.kernel.org/all/[email protected]/
- Remove sorting logic from libbpf and provide a generic btf__permute() interface (suggested by Andrii)
- Omitted the search direction patch to avoid conflicts with base BTF (suggested by Eduard).
- Include btf_sort.c directly in btf.c to reduce function call overhead
v2:
- Link: https://lore.kernel.org/all/[email protected]/
- Moved sorting to the build phase to reduce overhead (suggested by Alexei).
- Integrated sorting into btf_dedup_compact_and_sort_types (suggested by Eduard).
- Added sorting checks during BTF parsing.
- Consolidated common logic into btf_sort.c for sharing (suggested by Alan).
v1:
- Link: https://lore.kernel.org/all/[email protected]/
Donglin Peng (7):
libbpf: Add BTF permutation support for type reordering selftests/bpf: Add test cases for btf__permute functionality tools/resolve_btfids: Add --btf_sort option for BTF name sorting
libbpf: Optimize type lookup with binary search for sorted BTF
libbpf: Implement BTF type sorting validation for binary search
optimization
btf: Optimize type lookup with binary search
btf: Add sorting validation for binary search
kernel/bpf/btf.c | 147 ++++- scripts/Makefile.btf | 2 + scripts/Makefile.modfinal | 1 + scripts/link-vmlinux.sh | 1 + tools/bpf/resolve_btfids/main.c | 200 ++++++ tools/lib/bpf/btf.c | 327 +++++++++- tools/lib/bpf/btf.h | 43 ++ tools/lib/bpf/libbpf.map | 1 + .../selftests/bpf/prog_tests/btf_permute.c | 608 ++++++++++++++++++ 9 files changed, 1298 insertions(+), 32 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.c
Signature · 1 line
2.34.1
RFC PATCH v7 1/7 libbpf: Add BTF permutation support for type reordering
From: Donglin Peng <[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.
--- tools/lib/bpf/btf.c | 166 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 43 ++++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 210 insertions(+)
tools/lib/bpf/btf.c +166 -0
@@ -5829,3 +5829,169 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false;return libbpf_err (err); } + +struct btf_permute { +struct btf *btf; +__u32 *id_map; +}; + +/* Callback function to remap individual type ID references */ +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 or VOID */ +if (new_type_id < p->btf->start_id) +return 0 ; + +/* invalid reference id */ +if (new_type_id >=btf__type_cnt (p->btf)) +return -EINVAL ; + + new_type_id = p->id_map[new_type_id - p->btf->start_id]; +/* reference a dropped type is not allowed */ +if (new_type_id ==0 ) +return -EINVAL ; + + *type_id = new_type_id; +return 0 ; +} + +int btf__permute (struct btf *btf,__u32 *id_map,__u32 id_map_cnt, +const struct btf_permute_opts *opts) +{ +struct btf_permute p; +struct btf_ext *btf_ext; +void *next_type, *end_type; +void *nt, *new_types =NULL ; +int err =0 , i, new_type_len; +__u32 *order_map =NULL ; +__u32 id, new_nr_types =0 ; + +if (!OPTS_VALID (opts, btf_permute_opts) || id_map_cnt != btf->nr_types) +return libbpf_err (-EINVAL ); + +/* used to record the storage sequence of types */ + order_map =calloc (btf->nr_types,sizeof (*id_map)); +if (!order_map) { + err = -ENOMEM ; + goto done; + } + + new_types =calloc (btf->hdr->type_len,1 ); +if (!new_types) { + err = -ENOMEM ; + goto done; + } + +if (btf_ensure_modifiable (btf)) { + err = -ENOMEM ; + goto done; + } + +for (i =0 ; i < id_map_cnt; i++) { + id = id_map[i]; +/* Drop the specified type */ +if (id ==0 ) +continue ; +/* Invalid id */ +if (id < btf->start_id || id >=btf__type_cnt (btf)) { + err = -EINVAL ; + goto done; + } + id -= btf->start_id; +/* Multiple types cannot be mapped to the same ID */ +if (order_map[id]) { + err = -EINVAL ; + goto done; + } + order_map[id] = i + btf->start_id; + new_nr_types =max (id +1 , new_nr_types); + } + +/* Check for missing IDs */ +for (i =0 ; i < new_nr_types; i++) { +if (order_map[i] ==0 ) { + err = -EINVAL ; + goto done; + } + } + + p.btf = btf; + p.id_map = id_map; + nt = new_types; +for (i =0 ; i < new_nr_types; i++) { +struct btf_field_iter it; +const struct btf_type *t; +__u32 *type_id; +int type_size; + + id = order_map[i]; +/* must be a valid type ID */ + t =btf__type_by_id (btf, id); +if (!t) { + err = -EINVAL ; + goto done; + } + type_size =btf_type_size (t); +memcpy (nt, t, type_size); + +/* Fix up referenced IDs for BTF */ + err =btf_field_iter_init (&it, nt,BTF_FIELD_ITER_IDS ); +if (err) + goto done; +while ((type_id =btf_field_iter_next (&it))) { + err =btf_permute_remap_type_id (type_id, &p); +if (err) + goto done; + } + + nt += type_size; + } + +/* Fix up referenced IDs for btf_ext */ + btf_ext =OPTS_GET (opts, btf_ext,NULL ); +if (btf_ext) { + err =btf_ext_visit_type_ids (btf_ext, btf_permute_remap_type_id, &p); +if (err) + goto done; + } + + new_type_len = nt - new_types; + next_type = new_types; + end_type = next_type + new_type_len; + i =0 ; +while (next_type +sizeof (struct btf_type ) <= end_type) { + btf->type_offs[i++] = next_type - new_types; + next_type +=btf_type_size (next_type); + } + +/* Resize */ +if (new_type_len < btf->hdr->type_len) { +void *tmp_types; + + tmp_types =realloc (new_types, new_type_len); +if (new_type_len && !tmp_types) { + err = -ENOMEM ; + goto done; + } + new_types = tmp_types; + btf->nr_types = new_nr_types; + btf->type_offs_cap = btf->nr_types; + btf->types_data_cap = new_type_len; + btf->hdr->type_len = new_type_len; + btf->hdr->str_off = new_type_len; + btf->raw_size = btf->hdr->hdr_len + btf->hdr->type_len + btf->hdr->str_len; + } + +free (order_map); +free (btf->types_data); + btf->types_data = new_types; +return 0 ; + +done: +free (order_map); +free (new_types); +return libbpf_err (err); +}
tools/lib/bpf/btf.h +43 -0
49 lines not on this page · raw message
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 v7 1/7] libbpf: Add BTF permutation support for type reordering
Quoted 42 lines · Donglin Peng
From: Donglin Peng <[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.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]>Cc Xiaoqin Zhang <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 166 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 43 ++++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 210 insertions(+)tools/lib/bpf/btf.c +14
-0@@ -5829,3 +5829,169 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false;return libbpf_err (err); } + +struct btf_permute { +struct btf *btf; +__u32 *id_map; +}; + +/* Callback function to remap individual type ID references */ +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 or VOID */ +if (new_type_id < p->btf->start_id)
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5855
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+return 0 ; + +/* invalid reference id */ +if (new_type_id >=btf__type_cnt (p->btf)) +return -EINVAL ; + + new_type_id = p->id_map[new_type_id - p->btf->start_id]; +/* reference a dropped type is not allowed */ +if (new_type_id ==0 ) +return -EINVAL ;
see below, this shouldn't happen, let's drop redundant check
Quoted 32 lines
tools/lib/bpf/btf.c +32
-0+ + *type_id = new_type_id; +return 0 ; +} + +int btf__permute (struct btf *btf,__u32 *id_map,__u32 id_map_cnt, +const struct btf_permute_opts *opts) +{ +struct btf_permute p; +struct btf_ext *btf_ext; +void *next_type, *end_type; +void *nt, *new_types =NULL ; +int err =0 , i, new_type_len; +__u32 *order_map =NULL ; +__u32 id, new_nr_types =0 ; + +if (!OPTS_VALID (opts, btf_permute_opts) || id_map_cnt != btf->nr_types) +return libbpf_err (-EINVAL ); + +/* used to record the storage sequence of types */ + order_map =calloc (btf->nr_types,sizeof (*id_map)); +if (!order_map) { + err = -ENOMEM ; + goto done; + } + + new_types =calloc (btf->hdr->type_len,1 ); +if (!new_types) { + err = -ENOMEM ; + goto done; + } +
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5897
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+if (btf_ensure_modifiable (btf)) { + err = -ENOMEM ; + goto done; + } + +for (i =0 ; i < id_map_cnt; i++) { + id = id_map[i]; +/* Drop the specified type */ +if (id ==0 ) +continue ;
if we don't allow this (no support for deletion, I wouldn't rush to add that right now)...
pw-bot: cr
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5898
Quoted 1 line
tools/lib/bpf/btf.c +1
-0+/* Invalid id */
obvious statement, IMO, please drop the comment
Quoted 11 lines
tools/lib/bpf/btf.c +11
-0+if (id < btf->start_id || id >=btf__type_cnt (btf)) { + err = -EINVAL ; + goto done; + } + id -= btf->start_id; +/* Multiple types cannot be mapped to the same ID */ +if (order_map[id]) { + err = -EINVAL ; + goto done; + } + order_map[id] = i + btf->start_id;
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5919
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ new_nr_types =max (id +1 , new_nr_types); + } + +/* Check for missing IDs */ +for (i =0 ; i < new_nr_types; i++) { +if (order_map[i] ==0 ) { + err = -EINVAL ; + goto done; + } + }
... then you won't need this check at all, because we enforced that each remapped ID is different and we have exactly nr_types of them. Same for new_nr_types calculation above, seems redundant
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5931
Quoted 12 lines
tools/lib/bpf/btf.c +12
-0+ + p.btf = btf; + p.id_map = id_map; + nt = new_types; +for (i =0 ; i < new_nr_types; i++) { +struct btf_field_iter it; +const struct btf_type *t; +__u32 *type_id; +int type_size; + + id = order_map[i]; +/* must be a valid type ID */
redundant comment, please drop
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5933
Quoted 2 lines
tools/lib/bpf/btf.c +2
-0+ t =btf__type_by_id (btf, id); +if (!t) {
no need to check this, we already validated that all types are valid earlier
Quoted 18 lines
tools/lib/bpf/btf.c +18
-0+ err = -EINVAL ; + goto done; + } + type_size =btf_type_size (t); +memcpy (nt, t, type_size); + +/* Fix up referenced IDs for BTF */ + err =btf_field_iter_init (&it, nt,BTF_FIELD_ITER_IDS ); +if (err) + goto done; +while ((type_id =btf_field_iter_next (&it))) { + err =btf_permute_remap_type_id (type_id, &p); +if (err) + goto done; + } + + nt += type_size; + }
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5961
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ +/* Fix up referenced IDs for btf_ext */ + btf_ext =OPTS_GET (opts, btf_ext,NULL ); +if (btf_ext) { + err =btf_ext_visit_type_ids (btf_ext, btf_permute_remap_type_id, &p); +if (err) + goto done; + } + + new_type_len = nt - new_types;
new_type_len has to be exactly the same as the old size, this is redundant
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5965
Quoted 4 lines
tools/lib/bpf/btf.c +4
-0+ next_type = new_types; + end_type = next_type + new_type_len; + i =0 ; +while (next_type +sizeof (struct btf_type ) <= end_type) {
while (next_type < end_type)?
Reference to struct btf_type is confusing, as generally type is bigger than just sizeof(struct btf_type). But there is no need for this, with correct code next_type < end_type is sufficient check
But really, this can also be written cleanly as a simple for loop
for (i = 0; i < nr_types; i++) {
btf->type_offs[i] = next_type - new_types;
next_type += btf_type_size(next_type);
}tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5970
Quoted 5 lines
tools/lib/bpf/btf.c +5
-0+ btf->type_offs[i++] = next_type - new_types; + next_type +=btf_type_size (next_type); + } + +/* Resize */
there cannot be any resizing, drop this, you only need to reassign btf->types_data, that's all
Quoted 57 lines
tools/lib/bpf/btf.c +27
-0+if (new_type_len < btf->hdr->type_len) { +void *tmp_types; + + tmp_types =realloc (new_types, new_type_len); +if (new_type_len && !tmp_types) { + err = -ENOMEM ; + goto done; + } + new_types = tmp_types; + btf->nr_types = new_nr_types; + btf->type_offs_cap = btf->nr_types; + btf->types_data_cap = new_type_len; + btf->hdr->type_len = new_type_len; + btf->hdr->str_off = new_type_len; + btf->raw_size = btf->hdr->hdr_len + btf->hdr->type_len + btf->hdr->str_len; + } + +free (order_map); +free (btf->types_data); + btf->types_data = new_types; +return 0 ; + +done: +free (order_map); +free (new_types); +return libbpf_err (err); +}tools/lib/bpf/btf.h +22
-0@@ -273,6 +273,49 @@ 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()** performs in-place BTF type rearrangement +* @param btf BTF object to permute +* @param id_map Array mapping original type IDs to new IDs +* @param id_map_cnt Number of elements in @id_map +* @param opts Optional parameters for BTF extension updates +* @return 0 on success, negative error code on failure +* +* **btf__permute()** rearranges BTF types according to the specified ID mapping. +* The @id_map array defines the new type ID for each original type ID. +* +* For **base BTF**: +* - @id_map must include all types from ID 1 to `btf__type_cnt(btf)-1` +* - @id_map_cnt should be `btf__type_cnt(btf) - 1`
tools/lib/bpf/btf.h LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts); · line 307
Quoted 10 lines
tools/lib/bpf/btf.h +10
-0+* - Mapping uses `id_map[original_id - 1] = new_id` +* +* For **split BTF**: +* - @id_map should cover only split types +* - @id_map_cnt should be `btf__type_cnt(btf) - btf__type_cnt(btf__base_btf(btf))` +* - Mapping uses `id_map[original_id - btf__type_cnt(btf__base_btf(btf))] = new_id` +* +* Setting @id_map element to 0 drops the corresponding type. Dropped types must not +* be referenced by any retained types. After permutation, type references in BTF +* data and optional extension are updated automatically.
let's not add deletion support just yet
tools/lib/bpf/btf.h LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts); · line 310
Quoted 3 lines
tools/lib/bpf/btf.h +3
-0+* +* Note: Dropping types may orphan some strings, requiring subsequent **btf__dedup()** +* to clean up unreferenced strings.
one more reason to not add deletion just yet. It's good to have an API that can express this, but we don't have to support deletion just yet.
Quoted 24 lines
tools/lib/bpf/btf.h +8
-0+* +* On error, returns negative error code and sets errno: +* - `-EINVAL`: Invalid parameters or ID mapping (duplicates, out-of-range) +* - `-ENOMEM`: Memory allocation failure +*/ +LIBBPF_API int btf__permute(struct btf *btf, __u32 *id_map, __u32 id_map_cnt, +const struct btf_permute_opts *opts); +struct btf_dump ;struct btf_dump_opts {tools/lib/bpf/libbpf.map +1
-1@@ -451,4 +451,5 @@ LIBBPF_1.7.0 { global: bpf_map__set_exclusive_program; bpf_map__exclusive_program; + btf__permute; } LIBBPF_1.6.0; --2.34.1
Re: [RFC PATCH v7 1/7] libbpf: Add BTF permutation support for type reordering
Quoted 48 lines · Andrii Nakryiko
Quoted 46 lines · Donglin Peng
From: Donglin Peng <[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.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]>Cc Xiaoqin Zhang <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 166 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 43 ++++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 210 insertions(+)tools/lib/bpf/btf.c +18
-0@@ -5829,3 +5829,169 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false;return libbpf_err (err); } + +struct btf_permute { +struct btf *btf; +__u32 *id_map; +}; + +/* Callback function to remap individual type ID references */ +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 or VOID */ +if (new_type_id < p->btf->start_id) +return 0 ; + +/* invalid reference id */ +if (new_type_id >=btf__type_cnt (p->btf))
Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5855
Quoted 6 lines
tools/lib/bpf/btf.c +6
-0+return -EINVAL ; + + new_type_id = p->id_map[new_type_id - p->btf->start_id]; +/* reference a dropped type is not allowed */ +if (new_type_id ==0 ) +return -EINVAL ;see below, this shouldn't happen, let's drop redundant check
Thanks, I will remove it.
Quoted 38 lines
Quoted 38 lines
tools/lib/bpf/btf.c +37
-0+ + *type_id = new_type_id; +return 0 ; +} + +int btf__permute (struct btf *btf,__u32 *id_map,__u32 id_map_cnt, +const struct btf_permute_opts *opts) +{ +struct btf_permute p; +struct btf_ext *btf_ext; +void *next_type, *end_type; +void *nt, *new_types =NULL ; +int err =0 , i, new_type_len; +__u32 *order_map =NULL ; +__u32 id, new_nr_types =0 ; + +if (!OPTS_VALID (opts, btf_permute_opts) || id_map_cnt != btf->nr_types) +return libbpf_err (-EINVAL ); + +/* used to record the storage sequence of types */ + order_map =calloc (btf->nr_types,sizeof (*id_map)); +if (!order_map) { + err = -ENOMEM ; + goto done; + } + + new_types =calloc (btf->hdr->type_len,1 ); +if (!new_types) { + err = -ENOMEM ; + goto done; + } + +if (btf_ensure_modifiable (btf)) { + err = -ENOMEM ; + goto done; + } +
Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5897
Quoted 5 lines
tools/lib/bpf/btf.c +5
-0+for (i =0 ; i < id_map_cnt; i++) { + id = id_map[i]; +/* Drop the specified type */ +if (id ==0 ) +continue ;if we don't allow this (no support for deletion, I wouldn't rush to add that right now)...
Thanks, I will remove it.
Quoted 7 lines
pw-bot: cr
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5898
Quoted 1 line
tools/lib/bpf/btf.c +1
-0+/* Invalid id */ obvious statement, IMO, please drop the comment
Thanks, I will remove it.
Quoted 23 lines
Quoted 12 lines
tools/lib/bpf/btf.c +11
-0+if (id < btf->start_id || id >=btf__type_cnt (btf)) { + err = -EINVAL ; + goto done; + } + id -= btf->start_id; +/* Multiple types cannot be mapped to the same ID */ +if (order_map[id]) { + err = -EINVAL ; + goto done; + } + order_map[id] = i + btf->start_id;tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5919
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ new_nr_types =max (id +1 , new_nr_types); + } + +/* Check for missing IDs */ +for (i =0 ; i < new_nr_types; i++) { +if (order_map[i] ==0 ) { + err = -EINVAL ; + goto done; + } + }
Quoted 3 lines
... then you won't need this check at all, because we enforced that each remapped ID is different and we have exactly
nr_typesof them. Same fornew_nr_typescalculation above, seems redundant
Yes, if we don't support the dropping feature, there's no need to do this. I'll remove it.
Quoted 15 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5931
Quoted 13 lines
tools/lib/bpf/btf.c +12
-0+ + p.btf = btf; + p.id_map = id_map; + nt = new_types; +for (i =0 ; i < new_nr_types; i++) { +struct btf_field_iter it; +const struct btf_type *t; +__u32 *type_id; +int type_size; + + id = order_map[i]; +/* must be a valid type ID */ redundant comment, please drop
Thanks, I will remove it.
Quoted 5 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5933
Quoted 3 lines
tools/lib/bpf/btf.c +2
-0+ t =btf__type_by_id (btf, id); +if (!t) {no need to check this, we already validated that all types are valid earlier
Thanks, I will remove it.
Quoted 24 lines
Quoted 24 lines
tools/lib/bpf/btf.c +23
-0+ err = -EINVAL ; + goto done; + } + type_size =btf_type_size (t); +memcpy (nt, t, type_size); + +/* Fix up referenced IDs for BTF */ + err =btf_field_iter_init (&it, nt,BTF_FIELD_ITER_IDS ); +if (err) + goto done; +while ((type_id =btf_field_iter_next (&it))) { + err =btf_permute_remap_type_id (type_id, &p); +if (err) + goto done; + } + + nt += type_size; + } + +/* Fix up referenced IDs for btf_ext */ + btf_ext =OPTS_GET (opts, btf_ext,NULL ); +if (btf_ext) { + err =btf_ext_visit_type_ids (btf_ext, btf_permute_remap_type_id, &p);
Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5961
Quoted 5 lines
tools/lib/bpf/btf.c +5
-0+if (err) + goto done; + } + + new_type_len = nt - new_types;
new_type_lenhas to be exactly the same as the old size, this is redundant
Yes, if we don't support the dropping feature, there's no need to do this. I'll remove it.
Quoted 12 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5965
Quoted 5 lines
tools/lib/bpf/btf.c +4
-0+ next_type = new_types; + end_type = next_type + new_type_len; + i =0 ; +while (next_type +sizeof (struct btf_type ) <= end_type) {while (
next_type<end_type)?Reference to struct
btf_typeis confusing, as generally type is bigger than justsizeof(struct btf_type). But there is no need for this, with correct codenext_type<end_typeis sufficient check
Quoted 6 lines
But really, this can also be written cleanly as a simple for loop
for (i = 0; i < nr_types; i++) { btf->type_offs[i] = next_type - new_types; next_type += btf_type_size(next_type); }
Great, thanks.
Quoted 9 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5970
Quoted 6 lines
tools/lib/bpf/btf.c +5
-0+ btf->type_offs[i++] = next_type - new_types; + next_type +=btf_type_size (next_type); + } + +/* Resize */ there cannot be any resizing, drop this, you only need to reassign
btf->types_data, that's all
Okay, I will do it.
Quoted 62 lines
Quoted 62 lines
tools/lib/bpf/btf.c +27
-0+if (new_type_len < btf->hdr->type_len) { +void *tmp_types; + + tmp_types =realloc (new_types, new_type_len); +if (new_type_len && !tmp_types) { + err = -ENOMEM ; + goto done; + } + new_types = tmp_types; + btf->nr_types = new_nr_types; + btf->type_offs_cap = btf->nr_types; + btf->types_data_cap = new_type_len; + btf->hdr->type_len = new_type_len; + btf->hdr->str_off = new_type_len; + btf->raw_size = btf->hdr->hdr_len + btf->hdr->type_len + btf->hdr->str_len; + } + +free (order_map); +free (btf->types_data); + btf->types_data = new_types; +return 0 ; + +done: +free (order_map); +free (new_types); +return libbpf_err (err); +}tools/lib/bpf/btf.h +26
-0@@ -273,6 +273,49 @@ 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()** performs in-place BTF type rearrangement +* @param btf BTF object to permute +* @param id_map Array mapping original type IDs to new IDs +* @param id_map_cnt Number of elements in @id_map +* @param opts Optional parameters for BTF extension updates +* @return 0 on success, negative error code on failure +* +* **btf__permute()** rearranges BTF types according to the specified ID mapping. +* The @id_map array defines the new type ID for each original type ID. +* +* For **base BTF**: +* - @id_map must include all types from ID 1 to `btf__type_cnt(btf)-1` +* - @id_map_cnt should be `btf__type_cnt(btf) - 1` +* - Mapping uses `id_map[original_id - 1] = new_id` +* +* For **split BTF**: +* - @id_map should cover only split types
Quoted 8 lines
tools/lib/bpf/btf.h LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts); · line 307
Quoted 6 lines
tools/lib/bpf/btf.h +6
-0+* - @id_map_cnt should be `btf__type_cnt(btf) - btf__type_cnt(btf__base_btf(btf))` +* - Mapping uses `id_map[original_id - btf__type_cnt(btf__base_btf(btf))] = new_id` +* +* Setting @id_map element to 0 drops the corresponding type. Dropped types must not +* be referenced by any retained types. After permutation, type references in BTF +* data and optional extension are updated automatically. let's not add deletion support just yet
Thanks, I will modify the annotations.
Quoted 7 lines
tools/lib/bpf/btf.h LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts); · line 310
Quoted 4 lines
tools/lib/bpf/btf.h +3
-0+* +* Note: Dropping types may orphan some strings, requiring subsequent **btf__dedup()** +* to clean up unreferenced strings. one more reason to not add deletion just yet. It's good to have an API that can express this, but we don't have to support deletion just yet.
Thanks, I will remove it.
Quoted 25 lines
Quoted 25 lines
tools/lib/bpf/btf.h +8
-0+* +* On error, returns negative error code and sets errno: +* - `-EINVAL`: Invalid parameters or ID mapping (duplicates, out-of-range) +* - `-ENOMEM`: Memory allocation failure +*/ +LIBBPF_API int btf__permute(struct btf *btf, __u32 *id_map, __u32 id_map_cnt, +const struct btf_permute_opts *opts); +struct btf_dump ;struct btf_dump_opts {tools/lib/bpf/libbpf.map +1
-1@@ -451,4 +451,5 @@ LIBBPF_1.7.0 { global: bpf_map__set_exclusive_program; bpf_map__exclusive_program; + btf__permute; } LIBBPF_1.6.0; --2.34.1
Eduard Zingerman
maintainerRe: [RFC PATCH v7 1/7] libbpf: Add BTF permutation support for type reordering
In reply to Andrii NakryikoQuoted 1 line · Andrii Nakryiko
On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <[email protected]> wrote:
[...]
Quoted 60 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5931
Quoted 9 lines
tools/lib/bpf/btf.c +9
-0+ nt = new_types; +for (i =0 ; i < new_nr_types; i++) { +struct btf_field_iter it; +const struct btf_type *t; +__u32 *type_id; +int type_size; + + id = order_map[i]; +/* must be a valid type ID */ redundant comment, please drop
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5933
Quoted 2 lines
tools/lib/bpf/btf.c +2
-0+ t =btf__type_by_id (btf, id); +if (!t) {no need to check this, we already validated that all types are valid earlier
Quoted 18 lines
tools/lib/bpf/btf.c +18
-0+ err = -EINVAL ; + goto done; + } + type_size =btf_type_size (t); +memcpy (nt, t, type_size); + +/* Fix up referenced IDs for BTF */ + err =btf_field_iter_init (&it, nt,BTF_FIELD_ITER_IDS ); +if (err) + goto done; +while ((type_id =btf_field_iter_next (&it))) { + err =btf_permute_remap_type_id (type_id, &p); +if (err) + goto done; + } + + nt += type_size; + }tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5961
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ +/* Fix up referenced IDs for btf_ext */ + btf_ext =OPTS_GET (opts, btf_ext,NULL ); +if (btf_ext) { + err =btf_ext_visit_type_ids (btf_ext, btf_permute_remap_type_id, &p); +if (err) + goto done; + } + + new_type_len = nt - new_types;
new_type_lenhas to be exactly the same as the old size, this is redundanttools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5965
Quoted 4 lines
tools/lib/bpf/btf.c +4
-0+ next_type = new_types; + end_type = next_type + new_type_len; + i =0 ; +while (next_type +sizeof (struct btf_type ) <= end_type) {while (
next_type<end_type)?Reference to struct
btf_typeis confusing, as generally type is bigger than justsizeof(struct btf_type). But there is no need for this, with correct codenext_type<end_typeis sufficient check
Quoted 7 lines
But really, this can also be written cleanly as a simple for loop
for (i = 0; i < nr_types; i++) { btf->type_offs[i] = next_type - new_types; next_type += btf_type_size(next_type); }
Adding to what Andrii says, the whole group of assignments is reducible:
+ new_type_len = nt - new_types; + next_type = new_types; + end_type = next_type + new_type_len;
=> end_type = new_types + new_type_len; // subst next_type -> new_types => end_type = new_types + nt - new_types; // subst new_types -> nt - new_types => end_type = nt
Why recomputing it in such a convoluted way?
Quoted 4 lines
Quoted 4 lines
tools/lib/bpf/btf.c +4
-0+ btf->type_offs[i++] = next_type - new_types; + next_type +=btf_type_size (next_type); + } +
[...]
Re: [RFC PATCH v7 1/7] libbpf: Add BTF permutation support for type reordering
Quoted 81 lines · Eduard Zingerman
Quoted 1 line · Andrii Nakryiko
On Tue, Nov 18, 2025 at 7:21 PM Donglin Peng <[email protected]> wrote:
[...]
Quoted 60 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5931
Quoted 9 lines
tools/lib/bpf/btf.c +9
-0+ nt = new_types; +for (i =0 ; i < new_nr_types; i++) { +struct btf_field_iter it; +const struct btf_type *t; +__u32 *type_id; +int type_size; + + id = order_map[i]; +/* must be a valid type ID */ redundant comment, please drop
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5933
Quoted 2 lines
tools/lib/bpf/btf.c +2
-0+ t =btf__type_by_id (btf, id); +if (!t) {no need to check this, we already validated that all types are valid earlier
Quoted 18 lines
tools/lib/bpf/btf.c +18
-0+ err = -EINVAL ; + goto done; + } + type_size =btf_type_size (t); +memcpy (nt, t, type_size); + +/* Fix up referenced IDs for BTF */ + err =btf_field_iter_init (&it, nt,BTF_FIELD_ITER_IDS ); +if (err) + goto done; +while ((type_id =btf_field_iter_next (&it))) { + err =btf_permute_remap_type_id (type_id, &p); +if (err) + goto done; + } + + nt += type_size; + }tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5961
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ +/* Fix up referenced IDs for btf_ext */ + btf_ext =OPTS_GET (opts, btf_ext,NULL ); +if (btf_ext) { + err =btf_ext_visit_type_ids (btf_ext, btf_permute_remap_type_id, &p); +if (err) + goto done; + } + + new_type_len = nt - new_types;
new_type_lenhas to be exactly the same as the old size, this is redundanttools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5965
Quoted 4 lines
tools/lib/bpf/btf.c +4
-0+ next_type = new_types; + end_type = next_type + new_type_len; + i =0 ; +while (next_type +sizeof (struct btf_type ) <= end_type) {while (
next_type<end_type)?Reference to struct
btf_typeis confusing, as generally type is bigger than justsizeof(struct btf_type). But there is no need for this, with correct codenext_type<end_typeis sufficient checkQuoted 7 lines
But really, this can also be written cleanly as a simple for loop
for (i = 0; i < nr_types; i++) { btf->type_offs[i] = next_type - new_types; next_type += btf_type_size(next_type); }Adding to what Andrii says, the whole group of assignments is reducible:
+ new_type_len = nt - new_types; + next_type = new_types; + end_type = next_type + new_type_len;
Quoted 5 lines
=>
end_type=new_types+new_type_len; // substnext_type->new_types=>end_type=new_types+ nt -new_types; // substnew_types-> nt -new_types=>end_type= ntWhy recomputing it in such a convoluted way?
Sorry, I referred to the implementation of btf_parse_type_sec and could have thought more about how to refactor it.
Quoted 7 lines
Quoted 5 lines
Quoted 5 lines
tools/lib/bpf/btf.c +4
-0+ btf->type_offs[i++] = next_type - new_types; + next_type +=btf_type_size (next_type); + } +[...]
RFC PATCH v7 2/7 selftests/bpf: Add test cases for btf__permute functionality
In reply to Donglin PengFrom: Donglin Peng <[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 base BTF
- test_permute_split: Tests permutation on split BTF
- test_permute_drop_base: Validates type dropping on base BTF
- test_permute_drop_split: Tests type dropping on split BTF
- test_permute_drop_dedup: Tests type dropping and deduping
--- .../selftests/bpf/prog_tests/btf_permute.c | 608 ++++++++++++++++++ 1 file changed, 608 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.c
tools/testing/selftests/bpf/prog_tests/btf_permute.c new file +608 -0
@@ -0,0 +1,608 @@ +// 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 start_id =1 ; +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[1 - start_id] =4 ;/* [1] -> [4] */ + permute_ids[2 - start_id] =3 ;/* [2] -> [3] */ + permute_ids[3 - start_id] =5 ;/* [3] -> [5] */ + permute_ids[4 - start_id] =1 ;/* [4] -> [1] */ + permute_ids[5 - start_id] =6 ;/* [5] -> [6] */ + permute_ids[6 - start_id] =2 ;/* [6] -> [2] */ + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_OK (err,"btf__permute_base" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] FUNC 'f' type_id=6 linkage=static" , +"[3] PTR '(anon)' type_id=4" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=3" ); + +/* +* For base BTF, id_map_cnt must equal to the number of types +* include VOID type +*/ + permute_ids[1 - start_id] =4 ;/* [1] -> [4] */ + permute_ids[2 - start_id] =3 ;/* [2] -> [3] */ + permute_ids[3 - start_id] =5 ;/* [3] -> [5] */ + permute_ids[4 - start_id] =1 ;/* [4] -> [1] */ + permute_ids[5 - start_id] =6 ;/* [5] -> [6] */ + permute_ids[6 - start_id] =2 ;/* [6] -> [2] */ + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids) -1 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_base" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] FUNC 'f' type_id=6 linkage=static" , +"[3] PTR '(anon)' type_id=4" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=3" ); + +/* Multiple types can not be mapped to the same ID */ + permute_ids[1 - start_id] =4 ; + permute_ids[2 - start_id] =4 ; + permute_ids[3 - start_id] =5 ; + permute_ids[4 - start_id] =1 ; + permute_ids[5 - start_id] =6 ; + permute_ids[6 - start_id] =2 ; + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_ERR (err,"btf__permute_base" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] FUNC 'f' type_id=6 linkage=static" , +"[3] PTR '(anon)' type_id=4" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=3" ); + +/* Type ID must be valid */ + permute_ids[1 - start_id] =4 ; + permute_ids[2 - start_id] =3 ; + permute_ids[3 - start_id] =5 ; + permute_ids[4 - start_id] =1 ; + permute_ids[5 - start_id] =7 ; + permute_ids[6 - start_id] =2 ; + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_ERR (err,"btf__permute_base" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] FUNC 'f' type_id=6 linkage=static" , +"[3] PTR '(anon)' type_id=4" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=3" ); + +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; +int start_id; + + 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" ); + + start_id =btf__type_cnt (base_btf); + permute_ids[3 - start_id] =6 ;/* [3] -> [6] */ + permute_ids[4 - start_id] =3 ;/* [4] -> [3] */ + permute_ids[5 - start_id] =5 ;/* [5] -> [5] */ + permute_ids[6 - start_id] =4 ;/* [6] -> [4] */ + err =btf__permute (split_btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_OK (err,"btf__permute_split" )) + 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] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[4] FUNC 'f' type_id=5 linkage=static" , +"[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[6] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +/* +* For split BTF, id_map_cnt must equal to the number of types +* added on top of base BTF +*/ + permute_ids[3 - start_id] =4 ; + permute_ids[4 - start_id] =3 ; + permute_ids[5 - start_id] =5 ; + permute_ids[6 - start_id] =6 ; + err =btf__permute (split_btf, permute_ids,3 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_split" )) + 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] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[4] FUNC 'f' type_id=5 linkage=static" , +"[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[6] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +/* Multiple types can not be mapped to the same ID */ + permute_ids[3 - start_id] =4 ; + permute_ids[4 - start_id] =3 ; + permute_ids[5 - start_id] =3 ; + permute_ids[6 - start_id] =6 ; + err =btf__permute (split_btf, permute_ids,4 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_split" )) + 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] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[4] FUNC 'f' type_id=5 linkage=static" , +"[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[6] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +/* Can not map to base ID */ + permute_ids[3 - start_id] =4 ; + permute_ids[4 - start_id] =2 ; + permute_ids[5 - start_id] =5 ; + permute_ids[6 - start_id] =6 ; + err =btf__permute (split_btf, permute_ids,4 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_split" )) + 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] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[4] FUNC 'f' type_id=5 linkage=static" , +"[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[6] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +cleanup: +btf__free (split_btf); +btf__free (base_btf); +} + +/* Verify btf__permute function drops types correctly with base_btf */ +static void test_permute_drop_base (void ) +{ +struct btf *btf; +__u32 permute_ids[6 ]; +int start_id =1 ; +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" ); + +/* Drop ID 4 */ + permute_ids[1 - start_id] =5 ;/* [1] -> [5] */ + permute_ids[2 - start_id] =1 ;/* [2] -> [1] */ + permute_ids[3 - start_id] =2 ;/* [3] -> [2] */ + permute_ids[4 - start_id] =0 ;/* Drop [4] */ + permute_ids[5 - start_id] =3 ;/* [5] -> [3] */ + permute_ids[6 - start_id] =4 ;/* [6] -> [4] */ + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_base" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] PTR '(anon)' type_id=5" , +"[2] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=5 bits_offset=0" , +"[3] FUNC_PROTO '(anon)' ret_type_id=5 vlen=1\n" +"\t'p' type_id=1" , +"[4] FUNC 'f' type_id=3 linkage=static" , +"[5] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" ); + +/* Continue dropping */ + permute_ids[1 - start_id] =1 ;/* [1] -> [1] */ + permute_ids[2 - start_id] =2 ;/* [2] -> [2] */ + permute_ids[3 - start_id] =3 ;/* [3] -> [3] */ + permute_ids[4 - start_id] =0 ;/* Drop [4] */ + permute_ids[5 - start_id] =4 ;/* [5] -> [4] */ + err =btf__permute (btf, permute_ids,5 ,NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_base_fail" )) + goto done; + + +VALIDATE_RAW_BTF ( + btf, +"[1] PTR '(anon)' type_id=4" , +"[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=1" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" ); + +/* Cannot drop the ID referenced by others */ + permute_ids[1 - start_id] =2 ; + permute_ids[2 - start_id] =3 ; + permute_ids[3 - start_id] =1 ; + permute_ids[4 - start_id] =0 ;/* [4] is referenced by others */ + err =btf__permute (btf, permute_ids,4 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_drop_base_fail" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] PTR '(anon)' type_id=4" , +"[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=1" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" ); + +/* Drop 2 IDs at once */ + permute_ids[1 - start_id] =2 ;/* [1] -> [2] */ + permute_ids[2 - start_id] =0 ;/* Drop [2] */ + permute_ids[3 - start_id] =0 ;/* Drop [3] */ + permute_ids[4 - start_id] =1 ;/* [4] -> [1] */ + err =btf__permute (btf, permute_ids,4 ,NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_base_fail" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[2] PTR '(anon)' type_id=1" ); + +/* Drop all IDs */ + permute_ids[1 - start_id] =0 ;/* Drop [1] */ + permute_ids[2 - start_id] =0 ;/* Drop [2] */ + err =btf__permute (btf, permute_ids,2 ,NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_base_fail" )) + goto done; +if (!ASSERT_EQ (btf__type_cnt (btf),1 ,"btf__permute_drop_base all" )) + goto done; + +done: +btf__free (btf); +} + +/* Verify btf__permute function drops types correctly with split BTF */ +static void test_permute_drop_split (void ) +{ +struct btf *split_btf =NULL , *base_btf =NULL ; +__u32 permute_ids[4 ]; +int err; +int start_id; + + 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" ); + + start_id =btf__type_cnt (base_btf); + +/* Drop ID 4 */ + permute_ids[3 - start_id] =5 ;/* [3] -> [5] */ + permute_ids[4 - start_id] =0 ;/* Drop [4] */ + permute_ids[5 - start_id] =3 ;/* [5] -> [3] */ + permute_ids[6 - start_id] =4 ;/* [6] -> [4] */ + err =btf__permute (split_btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_split" )) + 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_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[4] FUNC 'f' type_id=3 linkage=static" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +/* Can not drop the type referenced by others */ + permute_ids[3 - start_id] =0 ;/* [3] is referenced by [4] */ + permute_ids[4 - start_id] =4 ; + permute_ids[5 - start_id] =3 ; + err =btf__permute (split_btf, permute_ids,3 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_drop_split" )) + 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_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[4] FUNC 'f' type_id=3 linkage=static" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +/* Continue dropping */ + permute_ids[3 - start_id] =0 ;/* Drop [3] */ + permute_ids[4 - start_id] =0 ;/* Drop [4] */ + permute_ids[5 - start_id] =3 ;/* [5] -> [3] */ + err =btf__permute (split_btf, permute_ids,3 ,NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_split" )) + 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] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +/* Continue dropping */ + permute_ids[3 - start_id] =0 ;/* Drop [3] */ + err =btf__permute (split_btf, permute_ids,1 ,NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_split" )) + 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" ); + +cleanup: +btf__free (split_btf); +btf__free (base_btf); +} + +/* Verify btf__permute then btf__dedup work correctly */ +static void test_permute_drop_dedup (void ) +{ +struct btf *btf, *new_btf =NULL ; +const struct btf_header *hdr; +const void *btf_data; +char expect_strs[] ="\0int\0s1\0m\0tag1\0tag2\0tag3" ; +char expect_strs_dedupped[] ="\0int\0s1\0m\0tag1" ; +__u32 permute_ids[5 ], btf_size; +int start_id =1 ; +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_struct (btf,"s1" ,4 );/* [2] struct s1 { */ +btf__add_field (btf,"m" ,1 ,0 ,0 );/* int m; */ +/* } */ +btf__add_decl_tag (btf,"tag1" ,2 ,-1 );/* [3] tag -> s1: tag1 */ +btf__add_decl_tag (btf,"tag2" ,2 ,1 );/* [4] tag -> s1/m: tag2 */ +btf__add_decl_tag (btf,"tag3" ,2 ,1 );/* [5] tag -> s1/m: tag3 */ + +VALIDATE_RAW_BTF ( + btf, +"[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[2] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[3] DECL_TAG 'tag1' type_id=2 component_idx=-1" , +"[4] DECL_TAG 'tag2' type_id=2 component_idx=1" , +"[5] DECL_TAG 'tag3' type_id=2 component_idx=1" ); + + btf_data =btf__raw_data (btf, &btf_size); +if (!ASSERT_OK_PTR (btf_data,"btf__raw_data" )) + goto done; + hdr = btf_data; +if (!ASSERT_EQ (hdr->str_len,ARRAY_SIZE (expect_strs),"expect_strs" )) + goto done; + + new_btf =btf__new (btf_data, btf_size); +if (!ASSERT_OK_PTR (new_btf,"btf__new" )) + goto done; + +/* Drop 2 IDs result in unreferenced strings */ + permute_ids[1 - start_id] =3 ;/* [1] -> [3] */ + permute_ids[2 - start_id] =1 ;/* [2] -> [1] */ + permute_ids[3 - start_id] =2 ;/* [3] -> [2] */ + permute_ids[4 - start_id] =0 ;/* Drop result in unreferenced "tag2" */ + permute_ids[5 - start_id] =0 ;/* Drop result in unreferenced "tag3" */ + err =btf__permute (new_btf, permute_ids,5 ,NULL ); +if (!ASSERT_OK (err,"btf__permute" )) + goto done; + +VALIDATE_RAW_BTF ( + new_btf, +"[1] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=3 bits_offset=0" , +"[2] DECL_TAG 'tag1' type_id=1 component_idx=-1" , +"[3] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" ); + + btf_data =btf__raw_data (new_btf, &btf_size); +if (!ASSERT_OK_PTR (btf_data,"btf__raw_data" )) + goto done; + hdr = btf_data; +if (!ASSERT_EQ (hdr->str_len,ARRAY_SIZE (expect_strs),"expect_strs" )) + goto done; + + err =btf__dedup (new_btf,NULL ); +if (!ASSERT_OK (err,"btf__dedup" )) + goto done; + + btf_data =btf__raw_data (new_btf, &btf_size); +if (!ASSERT_OK_PTR (btf_data,"btf__raw_data" )) + goto done; + hdr = btf_data; +if (!ASSERT_EQ (hdr->str_len,ARRAY_SIZE (expect_strs_dedupped),"expect_strs_dedupped" )) + goto done; + +done: +btf__free (btf); +btf__free (new_btf); +} + +void test_btf_permute (void ) +{ +if (test__start_subtest ("permute_base" )) +test_permute_base (); +if (test__start_subtest ("permute_split" )) +test_permute_split (); +if (test__start_subtest ("permute_drop_base" )) +test_permute_drop_base (); +if (test__start_subtest ("permute_drop_split" )) +test_permute_drop_split (); +if (test__start_subtest ("permute_drop_dedup" )) +test_permute_drop_dedup (); +}
Signature · 1 line
2.34.1
Re: [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality
Quoted 90 lines · Donglin Peng
From: Donglin Peng <[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 base BTF
-test_permute_split: Tests permutation on split BTF
-test_permute_drop_base: Validates type dropping on base BTF
-test_permute_drop_split: Tests type dropping on split BTF
-test_permute_drop_dedup: Tests type dropping and dedupingCc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Cc Xiaoqin Zhang <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- .../selftests/bpf/prog_tests/btf_permute.c | 608 ++++++++++++++++++ 1 file changed, 608 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.ctools/testing/selftests/bpf/prog_tests/btf_permute.c new file +59
-0@@ -0,0 +1,608 @@ +// 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 start_id =1 ; +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[1 - start_id] =4 ;/* [1] -> [4] */ + permute_ids[2 - start_id] =3 ;/* [2] -> [3] */ + permute_ids[3 - start_id] =5 ;/* [3] -> [5] */ + permute_ids[4 - start_id] =1 ;/* [4] -> [1] */ + permute_ids[5 - start_id] =6 ;/* [5] -> [6] */ + permute_ids[6 - start_id] =2 ;/* [6] -> [2] */ + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_OK (err,"btf__permute_base" )) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] STRUCT 's2' size=4 vlen=1\n" + "\t'm' type_id=4 bits_offset=0", + "[2] FUNC 'f' type_id=6 linkage=static", + "[3] PTR '(anon)' type_id=4",
tools/testing/selftests/bpf/prog_tests/btf_permute.c line 69
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/btf_permute.c new file +10
-0+"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" + "\t'p' type_id=3"); + +/* +* For base BTF, id_map_cnt must equal to the number of types +* include VOID type +*/
My bad. I will remove those comments.
Quoted 542 lines
tools/testing/selftests/bpf/prog_tests/btf_permute.c new file +539
-1+ permute_ids[1 - start_id] =4 ;/* [1] -> [4] */ + permute_ids[2 - start_id] =3 ;/* [2] -> [3] */ + permute_ids[3 - start_id] =5 ;/* [3] -> [5] */ + permute_ids[4 - start_id] =1 ;/* [4] -> [1] */ + permute_ids[5 - start_id] =6 ;/* [5] -> [6] */ + permute_ids[6 - start_id] =2 ;/* [6] -> [2] */ + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids) -1 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_base" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] FUNC 'f' type_id=6 linkage=static" , +"[3] PTR '(anon)' type_id=4" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=3" ); + +/* Multiple types can not be mapped to the same ID */ + permute_ids[1 - start_id] =4 ; + permute_ids[2 - start_id] =4 ; + permute_ids[3 - start_id] =5 ; + permute_ids[4 - start_id] =1 ; + permute_ids[5 - start_id] =6 ; + permute_ids[6 - start_id] =2 ; + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_ERR (err,"btf__permute_base" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] FUNC 'f' type_id=6 linkage=static" , +"[3] PTR '(anon)' type_id=4" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=3" ); + +/* Type ID must be valid */ + permute_ids[1 - start_id] =4 ; + permute_ids[2 - start_id] =3 ; + permute_ids[3 - start_id] =5 ; + permute_ids[4 - start_id] =1 ; + permute_ids[5 - start_id] =7 ; + permute_ids[6 - start_id] =2 ; + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_ERR (err,"btf__permute_base" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] FUNC 'f' type_id=6 linkage=static" , +"[3] PTR '(anon)' type_id=4" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=3" ); + +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; +int start_id; + + 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" ); + + start_id =btf__type_cnt (base_btf); + permute_ids[3 - start_id] =6 ;/* [3] -> [6] */ + permute_ids[4 - start_id] =3 ;/* [4] -> [3] */ + permute_ids[5 - start_id] =5 ;/* [5] -> [5] */ + permute_ids[6 - start_id] =4 ;/* [6] -> [4] */ + err =btf__permute (split_btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_OK (err,"btf__permute_split" )) + 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] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[4] FUNC 'f' type_id=5 linkage=static" , +"[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[6] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +/* +* For split BTF, id_map_cnt must equal to the number of types +* added on top of base BTF +*/ + permute_ids[3 - start_id] =4 ; + permute_ids[4 - start_id] =3 ; + permute_ids[5 - start_id] =5 ; + permute_ids[6 - start_id] =6 ; + err =btf__permute (split_btf, permute_ids,3 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_split" )) + 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] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[4] FUNC 'f' type_id=5 linkage=static" , +"[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[6] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +/* Multiple types can not be mapped to the same ID */ + permute_ids[3 - start_id] =4 ; + permute_ids[4 - start_id] =3 ; + permute_ids[5 - start_id] =3 ; + permute_ids[6 - start_id] =6 ; + err =btf__permute (split_btf, permute_ids,4 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_split" )) + 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] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[4] FUNC 'f' type_id=5 linkage=static" , +"[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[6] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +/* Can not map to base ID */ + permute_ids[3 - start_id] =4 ; + permute_ids[4 - start_id] =2 ; + permute_ids[5 - start_id] =5 ; + permute_ids[6 - start_id] =6 ; + err =btf__permute (split_btf, permute_ids,4 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_split" )) + 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] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[4] FUNC 'f' type_id=5 linkage=static" , +"[5] FUNC_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[6] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +cleanup: +btf__free (split_btf); +btf__free (base_btf); +} + +/* Verify btf__permute function drops types correctly with base_btf */ +static void test_permute_drop_base (void ) +{ +struct btf *btf; +__u32 permute_ids[6 ]; +int start_id =1 ; +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" ); + +/* Drop ID 4 */ + permute_ids[1 - start_id] =5 ;/* [1] -> [5] */ + permute_ids[2 - start_id] =1 ;/* [2] -> [1] */ + permute_ids[3 - start_id] =2 ;/* [3] -> [2] */ + permute_ids[4 - start_id] =0 ;/* Drop [4] */ + permute_ids[5 - start_id] =3 ;/* [5] -> [3] */ + permute_ids[6 - start_id] =4 ;/* [6] -> [4] */ + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_base" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] PTR '(anon)' type_id=5" , +"[2] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=5 bits_offset=0" , +"[3] FUNC_PROTO '(anon)' ret_type_id=5 vlen=1\n" +"\t'p' type_id=1" , +"[4] FUNC 'f' type_id=3 linkage=static" , +"[5] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" ); + +/* Continue dropping */ + permute_ids[1 - start_id] =1 ;/* [1] -> [1] */ + permute_ids[2 - start_id] =2 ;/* [2] -> [2] */ + permute_ids[3 - start_id] =3 ;/* [3] -> [3] */ + permute_ids[4 - start_id] =0 ;/* Drop [4] */ + permute_ids[5 - start_id] =4 ;/* [5] -> [4] */ + err =btf__permute (btf, permute_ids,5 ,NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_base_fail" )) + goto done; + + +VALIDATE_RAW_BTF ( + btf, +"[1] PTR '(anon)' type_id=4" , +"[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=1" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" ); + +/* Cannot drop the ID referenced by others */ + permute_ids[1 - start_id] =2 ; + permute_ids[2 - start_id] =3 ; + permute_ids[3 - start_id] =1 ; + permute_ids[4 - start_id] =0 ;/* [4] is referenced by others */ + err =btf__permute (btf, permute_ids,4 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_drop_base_fail" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] PTR '(anon)' type_id=4" , +"[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=1" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" ); + +/* Drop 2 IDs at once */ + permute_ids[1 - start_id] =2 ;/* [1] -> [2] */ + permute_ids[2 - start_id] =0 ;/* Drop [2] */ + permute_ids[3 - start_id] =0 ;/* Drop [3] */ + permute_ids[4 - start_id] =1 ;/* [4] -> [1] */ + err =btf__permute (btf, permute_ids,4 ,NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_base_fail" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[2] PTR '(anon)' type_id=1" ); + +/* Drop all IDs */ + permute_ids[1 - start_id] =0 ;/* Drop [1] */ + permute_ids[2 - start_id] =0 ;/* Drop [2] */ + err =btf__permute (btf, permute_ids,2 ,NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_base_fail" )) + goto done; +if (!ASSERT_EQ (btf__type_cnt (btf),1 ,"btf__permute_drop_base all" )) + goto done; + +done: +btf__free (btf); +} + +/* Verify btf__permute function drops types correctly with split BTF */ +static void test_permute_drop_split (void ) +{ +struct btf *split_btf =NULL , *base_btf =NULL ; +__u32 permute_ids[4 ]; +int err; +int start_id; + + 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" ); + + start_id =btf__type_cnt (base_btf); + +/* Drop ID 4 */ + permute_ids[3 - start_id] =5 ;/* [3] -> [5] */ + permute_ids[4 - start_id] =0 ;/* Drop [4] */ + permute_ids[5 - start_id] =3 ;/* [5] -> [3] */ + permute_ids[6 - start_id] =4 ;/* [6] -> [4] */ + err =btf__permute (split_btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_split" )) + 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_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[4] FUNC 'f' type_id=3 linkage=static" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +/* Can not drop the type referenced by others */ + permute_ids[3 - start_id] =0 ;/* [3] is referenced by [4] */ + permute_ids[4 - start_id] =4 ; + permute_ids[5 - start_id] =3 ; + err =btf__permute (split_btf, permute_ids,3 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_drop_split" )) + 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_PROTO '(anon)' ret_type_id=1 vlen=1\n" +"\t'p' type_id=2" , +"[4] FUNC 'f' type_id=3 linkage=static" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +/* Continue dropping */ + permute_ids[3 - start_id] =0 ;/* Drop [3] */ + permute_ids[4 - start_id] =0 ;/* Drop [4] */ + permute_ids[5 - start_id] =3 ;/* [5] -> [3] */ + err =btf__permute (split_btf, permute_ids,3 ,NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_split" )) + 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] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" ); + +/* Continue dropping */ + permute_ids[3 - start_id] =0 ;/* Drop [3] */ + err =btf__permute (split_btf, permute_ids,1 ,NULL ); +if (!ASSERT_OK (err,"btf__permute_drop_split" )) + 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" ); + +cleanup: +btf__free (split_btf); +btf__free (base_btf); +} + +/* Verify btf__permute then btf__dedup work correctly */ +static void test_permute_drop_dedup (void ) +{ +struct btf *btf, *new_btf =NULL ; +const struct btf_header *hdr; +const void *btf_data; +char expect_strs[] ="\0int\0s1\0m\0tag1\0tag2\0tag3" ; +char expect_strs_dedupped[] ="\0int\0s1\0m\0tag1" ; +__u32 permute_ids[5 ], btf_size; +int start_id =1 ; +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_struct (btf,"s1" ,4 );/* [2] struct s1 { */ +btf__add_field (btf,"m" ,1 ,0 ,0 );/* int m; */ +/* } */ +btf__add_decl_tag (btf,"tag1" ,2 ,-1 );/* [3] tag -> s1: tag1 */ +btf__add_decl_tag (btf,"tag2" ,2 ,1 );/* [4] tag -> s1/m: tag2 */ +btf__add_decl_tag (btf,"tag3" ,2 ,1 );/* [5] tag -> s1/m: tag3 */ + +VALIDATE_RAW_BTF ( + btf, +"[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[2] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=1 bits_offset=0" , +"[3] DECL_TAG 'tag1' type_id=2 component_idx=-1" , +"[4] DECL_TAG 'tag2' type_id=2 component_idx=1" , +"[5] DECL_TAG 'tag3' type_id=2 component_idx=1" ); + + btf_data =btf__raw_data (btf, &btf_size); +if (!ASSERT_OK_PTR (btf_data,"btf__raw_data" )) + goto done; + hdr = btf_data; +if (!ASSERT_EQ (hdr->str_len,ARRAY_SIZE (expect_strs),"expect_strs" )) + goto done; + + new_btf =btf__new (btf_data, btf_size); +if (!ASSERT_OK_PTR (new_btf,"btf__new" )) + goto done; + +/* Drop 2 IDs result in unreferenced strings */ + permute_ids[1 - start_id] =3 ;/* [1] -> [3] */ + permute_ids[2 - start_id] =1 ;/* [2] -> [1] */ + permute_ids[3 - start_id] =2 ;/* [3] -> [2] */ + permute_ids[4 - start_id] =0 ;/* Drop result in unreferenced "tag2" */ + permute_ids[5 - start_id] =0 ;/* Drop result in unreferenced "tag3" */ + err =btf__permute (new_btf, permute_ids,5 ,NULL ); +if (!ASSERT_OK (err,"btf__permute" )) + goto done; + +VALIDATE_RAW_BTF ( + new_btf, +"[1] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=3 bits_offset=0" , +"[2] DECL_TAG 'tag1' type_id=1 component_idx=-1" , +"[3] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" ); + + btf_data =btf__raw_data (new_btf, &btf_size); +if (!ASSERT_OK_PTR (btf_data,"btf__raw_data" )) + goto done; + hdr = btf_data; +if (!ASSERT_EQ (hdr->str_len,ARRAY_SIZE (expect_strs),"expect_strs" )) + goto done; + + err =btf__dedup (new_btf,NULL ); +if (!ASSERT_OK (err,"btf__dedup" )) + goto done; + + btf_data =btf__raw_data (new_btf, &btf_size); +if (!ASSERT_OK_PTR (btf_data,"btf__raw_data" )) + goto done; + hdr = btf_data; +if (!ASSERT_EQ (hdr->str_len,ARRAY_SIZE (expect_strs_dedupped),"expect_strs_dedupped" )) + goto done; + +done: +btf__free (btf); +btf__free (new_btf); +} + +void test_btf_permute (void ) +{ +if (test__start_subtest ("permute_base" )) +test_permute_base (); +if (test__start_subtest ("permute_split" )) +test_permute_split (); +if (test__start_subtest ("permute_drop_base" )) +test_permute_drop_base (); +if (test__start_subtest ("permute_drop_split" )) +test_permute_drop_split (); +if (test__start_subtest ("permute_drop_dedup" )) +test_permute_drop_dedup (); +} --2.34.1
Eduard Zingerman
maintainerRe: [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality
In reply to Donglin PengOn Wed, 2025-11-19 at 11:15 +0800, Donglin Peng wrote:
[...]
Quoted 97 lines
tools/testing/selftests/bpf/prog_tests/btf_permute.c new file +91
-0@@ -0,0 +1,608 @@ +// 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 start_id =1 ; +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[1 - start_id] =4 ;/* [1] -> [4] */ + permute_ids[2 - start_id] =3 ;/* [2] -> [3] */ + permute_ids[3 - start_id] =5 ;/* [3] -> [5] */ + permute_ids[4 - start_id] =1 ;/* [4] -> [1] */ + permute_ids[5 - start_id] =6 ;/* [5] -> [6] */ + permute_ids[6 - start_id] =2 ;/* [6] -> [2] */ + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_OK (err,"btf__permute_base" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] FUNC 'f' type_id=6 linkage=static" , +"[3] PTR '(anon)' type_id=4" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=3" ); + +/* +* For base BTF, id_map_cnt must equal to the number of types +* include VOID type +*/ + permute_ids[1 - start_id] =4 ;/* [1] -> [4] */ + permute_ids[2 - start_id] =3 ;/* [2] -> [3] */ + permute_ids[3 - start_id] =5 ;/* [3] -> [5] */ + permute_ids[4 - start_id] =1 ;/* [4] -> [1] */ + permute_ids[5 - start_id] =6 ;/* [5] -> [6] */ + permute_ids[6 - start_id] =2 ;/* [6] -> [2] */ + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids) -1 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_base" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] FUNC 'f' type_id=6 linkage=static" , +"[3] PTR '(anon)' type_id=4" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=3" ); +
tools/testing/selftests/bpf/prog_tests/btf_permute.c line 101
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/btf_permute.c new file +10
-0+/* Multiple types can not be mapped to the same ID */ + permute_ids[1 - start_id] =4 ; + permute_ids[2 - start_id] =4 ; + permute_ids[3 - start_id] =5 ; + permute_ids[4 - start_id] =1 ; + permute_ids[5 - start_id] =6 ; + permute_ids[6 - start_id] =2 ; + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_ERR (err,"btf__permute_base" )) + goto done;
Nit: Maybe extract the VALIDATE_RAW_BTF as a function, so that it is
not repeated? Otherwise it is a bit harder to tell that you are checking for BTF to be intact if error is returned. Same for the test_permute_split() case.
Quoted 12 lines
tools/testing/selftests/bpf/prog_tests/btf_permute.c new file +12
-0+ +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] FUNC 'f' type_id=6 linkage=static" , +"[3] PTR '(anon)' type_id=4" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=3" );
[...]
Re: [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality
Quoted 109 lines · Eduard Zingerman
On Wed, 2025-11-19 at 11:15 +0800, Donglin Peng wrote:
[...]
Quoted 104 lines
tools/testing/selftests/bpf/prog_tests/btf_permute.c new file +98
-0@@ -0,0 +1,608 @@ +// 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 start_id =1 ; +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[1 - start_id] =4 ;/* [1] -> [4] */ + permute_ids[2 - start_id] =3 ;/* [2] -> [3] */ + permute_ids[3 - start_id] =5 ;/* [3] -> [5] */ + permute_ids[4 - start_id] =1 ;/* [4] -> [1] */ + permute_ids[5 - start_id] =6 ;/* [5] -> [6] */ + permute_ids[6 - start_id] =2 ;/* [6] -> [2] */ + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_OK (err,"btf__permute_base" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] FUNC 'f' type_id=6 linkage=static" , +"[3] PTR '(anon)' type_id=4" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=3" ); + +/* +* For base BTF, id_map_cnt must equal to the number of types +* include VOID type +*/ + permute_ids[1 - start_id] =4 ;/* [1] -> [4] */ + permute_ids[2 - start_id] =3 ;/* [2] -> [3] */ + permute_ids[3 - start_id] =5 ;/* [3] -> [5] */ + permute_ids[4 - start_id] =1 ;/* [4] -> [1] */ + permute_ids[5 - start_id] =6 ;/* [5] -> [6] */ + permute_ids[6 - start_id] =2 ;/* [6] -> [2] */ + err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids) -1 ,NULL ); +if (!ASSERT_ERR (err,"btf__permute_base" )) + goto done; + +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] FUNC 'f' type_id=6 linkage=static" , +"[3] PTR '(anon)' type_id=4" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=3" ); + +/* Multiple types can not be mapped to the same ID */ + permute_ids[1 - start_id] =4 ; + permute_ids[2 - start_id] =4 ; + permute_ids[3 - start_id] =5 ; + permute_ids[4 - start_id] =1 ; + permute_ids[5 - start_id] =6 ; + permute_ids[6 - start_id] =2 ;
Quoted 8 lines
tools/testing/selftests/bpf/prog_tests/btf_permute.c line 78
Quoted 3 lines
tools/testing/selftests/bpf/prog_tests/btf_permute.c new file +3
-0+ err =btf__permute (btf, permute_ids,ARRAY_SIZE (permute_ids),NULL ); +if (!ASSERT_ERR (err,"btf__permute_base" )) + goto done;Nit: Maybe extract the
VALIDATE_RAW_BTFas a function, so that it is
not repeated? Otherwise it is a bit harder to tell that you are checking for BTF to be intact if error is returned. Same for thetest_permute_split()case.
Thanks, I will make it more clear.
Quoted 15 lines
Quoted 13 lines
tools/testing/selftests/bpf/prog_tests/btf_permute.c new file +12
-0+ +VALIDATE_RAW_BTF ( + btf, +"[1] STRUCT 's2' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[2] FUNC 'f' type_id=6 linkage=static" , +"[3] PTR '(anon)' type_id=4" , +"[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED" , +"[5] STRUCT 's1' size=4 vlen=1\n" +"\t'm' type_id=4 bits_offset=0" , +"[6] FUNC_PROTO '(anon)' ret_type_id=4 vlen=1\n" +"\t'p' type_id=3" );[...]
Eduard Zingerman
maintainerRe: [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality
In reply to Donglin PengQuoted 12 lines · Donglin Peng
From: Donglin Peng <[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 base BTF
-test_permute_split: Tests permutation on split BTF
-test_permute_drop_base: Validates type dropping on base BTF
-test_permute_drop_split: Tests type dropping on split BTF
-test_permute_drop_dedup: Tests type dropping and deduping
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]>Cc Xiaoqin Zhang <[email protected]>Signed-off-by Donglin Peng <[email protected]>---
Do we have an infrastructure for .btf_ext tests?
[...]
RFC PATCH v7 3/7 tools/resolve_btfids: Add --btf_sort option for BTF name sorting
In reply to Donglin PengFrom: Donglin Peng <[email protected]>
This patch introduces a new --btf_sort option that leverages libbpf's btf__permute interface to reorganize BTF layout. The implementation sorts BTF types by name in ascending order, placing anonymous types at the end to enable efficient binary search lookup.
--- scripts/Makefile.btf | 2 + scripts/Makefile.modfinal | 1 + scripts/link-vmlinux.sh | 1 + tools/bpf/resolve_btfids/main.c | 200 ++++++++++++++++++++++++++++++++ 4 files changed, 204 insertions(+)
scripts/Makefile.btf +2 -0
@@ -27,6 +27,7 @@ pahole-flags-$(call test-ge, $(pahole-ver), 130) += --btf_features=attributes ifneq ($(KBUILD_EXTMOD),) module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base +module-resolve_btfid-flags-y = --distilled_base endif endif
@@ -35,3 +36,4 @@ pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) += --lang_exclude=rust export PAHOLE_FLAGS := $(pahole-flags-y) export MODULE_PAHOLE_FLAGS := $(module-pahole-flags-y) +export MODULE_RESOLVE_BTFID_FLAGS := $(module-resolve_btfid-flags-y)
scripts/Makefile.modfinal +1 -0
@@ -40,6 +40,7 @@ quiet_cmd_btf_ko = BTF [M] $@ printf "Skipping BTF generation for %s due to unavailability of vmlinux\n" $@ 1>&2; \ else \ LLVM_OBJCOPY="$(OBJCOPY)" $(PAHOLE) -J $(PAHOLE_FLAGS) $(MODULE_PAHOLE_FLAGS) --btf_base $(objtree)/vmlinux $@; \ + $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $(MODULE_RESOLVE_BTFID_FLAGS) --btf_sort $@; \ $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $@; \ fi;
scripts/link-vmlinux.sh +1 -0
@@ -288,6 +288,7 @@ if is_enabled CONFIG_DEBUG_INFO_BTF; then if is_enabled CONFIG_WERROR; then RESOLVE_BTFIDS_ARGS=" --fatal_warnings " fi + ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} --btf_sort "${VMLINUX}" ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} "${VMLINUX}" fi
tools/bpf/resolve_btfids/main.c +200 -0
224 lines not on this page · raw message
Signature · 1 line
2.34.1
Ihor Solodrai
reviewerRe: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
Quoted 84 lines · Donglin Peng
From: Donglin Peng <[email protected]>
This patch introduces a new --btf_sort option that leverages libbpf's
btf__permuteinterface to reorganize BTF layout. The implementation sorts BTF types by name in ascending order, placing anonymous types at the end to enable efficient binary search lookup.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]>Cc Xiaoqin Zhang <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- scripts/Makefile.btf | 2 + scripts/Makefile.modfinal | 1 + scripts/link-vmlinux.sh | 1 + tools/bpf/resolve_btfids/main.c | 200 ++++++++++++++++++++++++++++++++ 4 files changed, 204 insertions(+)scripts/Makefile.btf +2
-0@@ -27,6 +27,7 @@ pahole-flags-$(call test-ge, $(pahole-ver), 130) += --btf_features=attributes ifneq ($(KBUILD_EXTMOD),) module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base +module-resolve_btfid-flags-y = --distilled_base endif endif@@ -35,3 +36,4 @@ pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) += --lang_exclude=rust export PAHOLE_FLAGS := $(pahole-flags-y) export MODULE_PAHOLE_FLAGS := $(module-pahole-flags-y) +export MODULE_RESOLVE_BTFID_FLAGS := $(module-resolve_btfid-flags-y)scripts/Makefile.modfinal +1
-0@@ -40,6 +40,7 @@ quiet_cmd_btf_ko = BTF [M] $@ printf "Skipping BTF generation for %s due to unavailability of vmlinux\n" $@ 1>&2; \ else \ LLVM_OBJCOPY="$(OBJCOPY)" $(PAHOLE) -J $(PAHOLE_FLAGS) $(MODULE_PAHOLE_FLAGS) --btf_base $(objtree)/vmlinux $@; \ + $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $(MODULE_RESOLVE_BTFID_FLAGS) --btf_sort $@; \ $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $@; \ fi;scripts/link-vmlinux.sh +1
-0@@ -288,6 +288,7 @@ if is_enabled CONFIG_DEBUG_INFO_BTF; then if is_enabled CONFIG_WERROR; then RESOLVE_BTFIDS_ARGS=" --fatal_warnings " fi + ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} --btf_sort "${VMLINUX}" ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} "${VMLINUX}" fitools/bpf/resolve_btfids/main.c +14
-0@@ -768,6 +768,195 @@ static int symbols_patch(struct object *obj)return err <0 ?-1 :0 ; } +/* Anonymous types (with empty names) are considered greater than named types +* and are sorted after them. Two anonymous types are considered equal. Named +* types are compared lexicographically. +*/ +static int cmp_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)
tools/bpf/resolve_btfids/main.c static int symbols_patch(struct object *obj) · line 794
Quoted 10 lines
tools/bpf/resolve_btfids/main.c +10
-0+return -1 ; +if (!ta->name_off && !tb->name_off) +return 0 ; + + na =btf__str_by_offset (btf, ta->name_off); + nb =btf__str_by_offset (btf, tb->name_off); +return strcmp (na, nb); +} + +static int update_btf_section(const char *path, const struct btf *btf,
Hi Dongling.
Thanks for working on this, it's a great optimization. Just want to give you a heads up that I am preparing a patchset changing resolve_btfids behavior.
In particular, instead of updating the .BTF_ids section (and now with your and upcoming changes the .BTF section) *in-place*, resolve_btfids will only emit the data for the sections. And then it'll be integrated into vmlinux with objcopy and linker. We already do a similar thing with .BTF for vmlinux [1].
For your patchset it means that the parts handling ELF update will be unnecessary.
Also I think the --btf_sort flag is unnecessary. We probably want kernel BTF to always be sorted in this way. And if resolve_btfids will be handling more btf2btf transformation, we should avoid adding a flags for every one of them.
[1] https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/scripts/link-vmlinux.sh#n110
Quoted 200 lines
tools/bpf/resolve_btfids/main.c +176
-0+ const char *btf_secname) +{ +GElf_Shdr shdr_mem, *shdr; +Elf_Data *btf_data =NULL ; +Elf_Scn *scn =NULL ; +Elf *elf =NULL ; +const void *raw_btf_data; +uint32_t raw_btf_size; +int fd, err =-1 ; +size_t strndx; + + fd =open (path,O_RDWR ); +if (fd <0 ) { +pr_err ("FAILED to open %s\n" , path); +return -1 ; + } + +if (elf_version (EV_CURRENT ) ==EV_NONE ) { +pr_err ("FAILED to set libelf version" ); + goto out; + } + + elf =elf_begin (fd,ELF_C_RDWR ,NULL ); +if (elf ==NULL ) { +pr_err ("FAILED to update ELF file" ); + goto out; + } + +elf_flagelf (elf,ELF_C_SET ,ELF_F_LAYOUT ); + +elf_getshdrstrndx (elf, &strndx); +while ((scn =elf_nextscn (elf, scn)) !=NULL ) { +char *secname; + + shdr =gelf_getshdr (scn, &shdr_mem); +if (shdr ==NULL ) +continue ; + secname =elf_strptr (elf, strndx, shdr->sh_name); +if (strcmp (secname, btf_secname) ==0 ) { + btf_data =elf_getdata (scn, btf_data); +break ; + } + } + + raw_btf_data =btf__raw_data (btf, &raw_btf_size); + +if (btf_data) { +if (raw_btf_size != btf_data->d_size) { +pr_err ("FAILED: size mismatch" ); + goto out; + } + + btf_data->d_buf = (void *)raw_btf_data; + btf_data->d_type =ELF_T_WORD ; +elf_flagdata (btf_data,ELF_C_SET ,ELF_F_DIRTY ); + +if (elf_update (elf,ELF_C_WRITE ) >=0 ) + err =0 ; + } + +out: +if (fd !=-1 ) +close (fd); +if (elf) +elf_end (elf); +return err; +} + +static int sort_update_btf (struct object *obj,bool distilled_base) +{ +struct btf *base_btf =NULL ; +struct btf *btf =NULL ; +int start_id =1 , nr_types, id; +int err =0 , i; +__u32 *permute_ids =NULL , *id_map =NULL , btf_size; +const void *btf_data; +int fd; + +if (obj->base_btf_path) { + base_btf =btf__parse (obj->base_btf_path,NULL ); + err =libbpf_get_error (base_btf); +if (err) { +pr_err ("FAILED: load base BTF from %s: %s\n" , + obj->base_btf_path,strerror (-err)); +return -1 ; + } + } + + btf =btf__parse_elf_split (obj->path, base_btf); + err =libbpf_get_error (btf); +if (err) { +pr_err ("FAILED: load BTF from %s: %s\n" , obj->path,strerror (-err)); + goto out; + } + +if (base_btf) + start_id =btf__type_cnt (base_btf); + nr_types =btf__type_cnt (btf) - start_id; +if (nr_types <2 ) + goto out; + + permute_ids =calloc (nr_types,sizeof (*permute_ids)); +if (!permute_ids) { + err = -ENOMEM ; + goto out; + } + + id_map =calloc (nr_types,sizeof (*id_map)); +if (!id_map) { + err = -ENOMEM ; + goto out; + } + +for (i =0 , id = start_id; i < nr_types; i++, id++) + permute_ids[i] = id; + +qsort_r (permute_ids, nr_types,sizeof (*permute_ids), cmp_type_names, btf); + +for (i =0 ; i < nr_types; i++) { + id = permute_ids[i] - start_id; + id_map[id] = i + start_id; + } + + err =btf__permute (btf, id_map, nr_types,NULL ); +if (err) { +pr_err ("FAILED: btf permute: %s\n" ,strerror (-err)); + goto out; + } + +if (distilled_base) { +struct btf *new_btf =NULL , *distilled_base =NULL ; + +if (btf__distill_base (btf, &distilled_base, &new_btf) <0 ) { +pr_err ("FAILED to generate distilled base BTF: %s\n" , +strerror (errno)); + goto out; + } + + err =update_btf_section (obj->path, new_btf,BTF_ELF_SEC ); +if (!err) { + err =update_btf_section (obj->path, distilled_base,BTF_BASE_ELF_SEC ); +if (err <0 ) +pr_err ("FAILED to update '%s'\n" ,BTF_BASE_ELF_SEC ); + }else { +pr_err ("FAILED to update '%s'\n" ,BTF_ELF_SEC ); + } + +btf__free (new_btf); +btf__free (distilled_base); + }else { + err =update_btf_section (obj->path, btf,BTF_ELF_SEC ); +if (err <0 ) { +pr_err ("FAILED to update '%s'\n" ,BTF_ELF_SEC ); + goto out; + } + } + +out: +free (permute_ids); +free (id_map); +btf__free (base_btf); +btf__free (btf); +return err; +} +static const char *const resolve_btfids_usage[] = {"resolve_btfids [<options>] <ELF object>" ,NULL @@ -787,6 +976,8 @@ int main(int argc, const char **argv) .sets = RB_ROOT, };bool fatal_warnings = false; +bool btf_sort = false; +bool distilled_base = false;struct option btfid_options[] = {OPT_INCR ('v' ,"verbose" , &verbose,"be more verbose (show errors, etc)" ),@@ -796,6 +987,10 @@ int main(int argc, const char **argv) "path of file providing base BTF"),OPT_BOOLEAN (0 ,"fatal_warnings" , &fatal_warnings,"turn warnings into errors" ), +OPT_BOOLEAN (0 ,"btf_sort" , &btf_sort, +"sort BTF by name in ascending order" ), +OPT_BOOLEAN (0 ,"distilled_base" , &distilled_base, +"distill base" ), OPT_END() };int err =-1 ;@@ -807,6 +1002,11 @@ int main(int argc, const char **argv) obj.path = argv[0 ]; +if (btf_sort) { + err =sort_update_btf (&obj, distilled_base); + goto out; + } +if (elf_collect (&obj)) goto out;
Ihor Solodrai
reviewerRe: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
Quoted 26 lines · Ihor Solodrai
tools/bpf/resolve_btfids/main.c static int symbols_patch(struct object *obj) · line 794
Quoted 12 lines · Donglin Peng
From: Donglin Peng <[email protected]>
This patch introduces a new --btf_sort option that leverages libbpf's
btf__permuteinterface to reorganize BTF layout. The implementation sorts BTF types by name in ascending order, placing anonymous types at the end to enable efficient binary search lookup.[...]
tools/bpf/resolve_btfids/main.c +3
-0+} + +static int update_btf_section(const char *path, const struct btf *btf,Hi Dongling.
Thanks for working on this, it's a great optimization. Just want to give you a heads up that I am preparing a patchset changing
resolve_btfidsbehavior.In particular, instead of updating the .BTF_ids section (and now with your and upcoming changes the .BTF section) *in-place*,
resolve_btfidswill only emit the data for the sections. And then it'll be integrated into vmlinux with objcopy and linker. We already do a similar thing with .BTF for vmlinux [1].
Quoted 7 lines
For your patchset it means that the parts handling ELF update will be unnecessary.
Also I think the --btf_sort flag is unnecessary. We probably want kernel BTF to always be sorted in this way. And if
resolve_btfidswill be handling more btf2btf transformation, we should avoid adding a flags for every one of them.
The same applies to --distilled_base.
AFAIU we always want to do it, so there is not need for the flag. Unless there is a strong use case for generating module BTF *without* the distilled base that I am not aware of.
Maybe an explicit "--kmodule" flag would be appropriate?.. For resolve_btfids, is it reasonable to assume it's a module if --base is passed in?
Andrii, Eduard, wdyt?
Re: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
In reply to Ihor SolodraiQuoted 99 lines · Ihor Solodrai
Quoted 84 lines · Donglin Peng
From: Donglin Peng <[email protected]>
This patch introduces a new --btf_sort option that leverages libbpf's
btf__permuteinterface to reorganize BTF layout. The implementation sorts BTF types by name in ascending order, placing anonymous types at the end to enable efficient binary search lookup.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]>Cc Xiaoqin Zhang <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- scripts/Makefile.btf | 2 + scripts/Makefile.modfinal | 1 + scripts/link-vmlinux.sh | 1 + tools/bpf/resolve_btfids/main.c | 200 ++++++++++++++++++++++++++++++++ 4 files changed, 204 insertions(+)scripts/Makefile.btf +2
-0@@ -27,6 +27,7 @@ pahole-flags-$(call test-ge, $(pahole-ver), 130) += --btf_features=attributes ifneq ($(KBUILD_EXTMOD),) module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base +module-resolve_btfid-flags-y = --distilled_base endif endif@@ -35,3 +36,4 @@ pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) += --lang_exclude=rust export PAHOLE_FLAGS := $(pahole-flags-y) export MODULE_PAHOLE_FLAGS := $(module-pahole-flags-y) +export MODULE_RESOLVE_BTFID_FLAGS := $(module-resolve_btfid-flags-y)scripts/Makefile.modfinal +1
-0@@ -40,6 +40,7 @@ quiet_cmd_btf_ko = BTF [M] $@ printf "Skipping BTF generation for %s due to unavailability of vmlinux\n" $@ 1>&2; \ else \ LLVM_OBJCOPY="$(OBJCOPY)" $(PAHOLE) -J $(PAHOLE_FLAGS) $(MODULE_PAHOLE_FLAGS) --btf_base $(objtree)/vmlinux $@; \ + $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $(MODULE_RESOLVE_BTFID_FLAGS) --btf_sort $@; \ $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $@; \ fi;scripts/link-vmlinux.sh +1
-0@@ -288,6 +288,7 @@ if is_enabled CONFIG_DEBUG_INFO_BTF; then if is_enabled CONFIG_WERROR; then RESOLVE_BTFIDS_ARGS=" --fatal_warnings " fi + ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} --btf_sort "${VMLINUX}" ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} "${VMLINUX}" fitools/bpf/resolve_btfids/main.c +14
-0@@ -768,6 +768,195 @@ static int symbols_patch(struct object *obj)return err <0 ?-1 :0 ; } +/* Anonymous types (with empty names) are considered greater than named types +* and are sorted after them. Two anonymous types are considered equal. Named +* types are compared lexicographically. +*/ +static int cmp_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)tools/bpf/resolve_btfids/main.c static int symbols_patch(struct object *obj) · line 794
Quoted 10 lines
tools/bpf/resolve_btfids/main.c +10
-0+return -1 ; +if (!ta->name_off && !tb->name_off) +return 0 ; + + na =btf__str_by_offset (btf, ta->name_off); + nb =btf__str_by_offset (btf, tb->name_off); +return strcmp (na, nb); +} + +static int update_btf_section(const char *path, const struct btf *btf,Hi Dongling.
Quoted 3 lines
Thanks for working on this, it's a great optimization. Just want to give you a heads up that I am preparing a patchset changing
resolve_btfidsbehavior.
Thanks. I'm curious about the new behavior of resolve_btfids. Does it replace pahole and generate the sorted .BTF data directly from the DWARF data? Also, does its sorting method differ from the cmp_type_names approach mentioned above — specifically, does it place named types before all anonymous types? I'm asking because the search method needs to be compatible with this sorting approach.
Quoted 219 lines
In particular, instead of updating the .BTF_ids section (and now with your and upcoming changes the .BTF section) *in-place*,
resolve_btfidswill only emit the data for the sections. And then it'll be integrated into vmlinux with objcopy and linker. We already do a similar thing with .BTF for vmlinux [1].For your patchset it means that the parts handling ELF update will be unnecessary.
Also I think the --btf_sort flag is unnecessary. We probably want kernel BTF to always be sorted in this way. And if
resolve_btfidswill be handling more btf2btf transformation, we should avoid adding a flags for every one of them.[1] https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/scripts/link-vmlinux.sh#n110
Quoted 200 lines
tools/bpf/resolve_btfids/main.c +176
-0+ const char *btf_secname) +{ +GElf_Shdr shdr_mem, *shdr; +Elf_Data *btf_data =NULL ; +Elf_Scn *scn =NULL ; +Elf *elf =NULL ; +const void *raw_btf_data; +uint32_t raw_btf_size; +int fd, err =-1 ; +size_t strndx; + + fd =open (path,O_RDWR ); +if (fd <0 ) { +pr_err ("FAILED to open %s\n" , path); +return -1 ; + } + +if (elf_version (EV_CURRENT ) ==EV_NONE ) { +pr_err ("FAILED to set libelf version" ); + goto out; + } + + elf =elf_begin (fd,ELF_C_RDWR ,NULL ); +if (elf ==NULL ) { +pr_err ("FAILED to update ELF file" ); + goto out; + } + +elf_flagelf (elf,ELF_C_SET ,ELF_F_LAYOUT ); + +elf_getshdrstrndx (elf, &strndx); +while ((scn =elf_nextscn (elf, scn)) !=NULL ) { +char *secname; + + shdr =gelf_getshdr (scn, &shdr_mem); +if (shdr ==NULL ) +continue ; + secname =elf_strptr (elf, strndx, shdr->sh_name); +if (strcmp (secname, btf_secname) ==0 ) { + btf_data =elf_getdata (scn, btf_data); +break ; + } + } + + raw_btf_data =btf__raw_data (btf, &raw_btf_size); + +if (btf_data) { +if (raw_btf_size != btf_data->d_size) { +pr_err ("FAILED: size mismatch" ); + goto out; + } + + btf_data->d_buf = (void *)raw_btf_data; + btf_data->d_type =ELF_T_WORD ; +elf_flagdata (btf_data,ELF_C_SET ,ELF_F_DIRTY ); + +if (elf_update (elf,ELF_C_WRITE ) >=0 ) + err =0 ; + } + +out: +if (fd !=-1 ) +close (fd); +if (elf) +elf_end (elf); +return err; +} + +static int sort_update_btf (struct object *obj,bool distilled_base) +{ +struct btf *base_btf =NULL ; +struct btf *btf =NULL ; +int start_id =1 , nr_types, id; +int err =0 , i; +__u32 *permute_ids =NULL , *id_map =NULL , btf_size; +const void *btf_data; +int fd; + +if (obj->base_btf_path) { + base_btf =btf__parse (obj->base_btf_path,NULL ); + err =libbpf_get_error (base_btf); +if (err) { +pr_err ("FAILED: load base BTF from %s: %s\n" , + obj->base_btf_path,strerror (-err)); +return -1 ; + } + } + + btf =btf__parse_elf_split (obj->path, base_btf); + err =libbpf_get_error (btf); +if (err) { +pr_err ("FAILED: load BTF from %s: %s\n" , obj->path,strerror (-err)); + goto out; + } + +if (base_btf) + start_id =btf__type_cnt (base_btf); + nr_types =btf__type_cnt (btf) - start_id; +if (nr_types <2 ) + goto out; + + permute_ids =calloc (nr_types,sizeof (*permute_ids)); +if (!permute_ids) { + err = -ENOMEM ; + goto out; + } + + id_map =calloc (nr_types,sizeof (*id_map)); +if (!id_map) { + err = -ENOMEM ; + goto out; + } + +for (i =0 , id = start_id; i < nr_types; i++, id++) + permute_ids[i] = id; + +qsort_r (permute_ids, nr_types,sizeof (*permute_ids), cmp_type_names, btf); + +for (i =0 ; i < nr_types; i++) { + id = permute_ids[i] - start_id; + id_map[id] = i + start_id; + } + + err =btf__permute (btf, id_map, nr_types,NULL ); +if (err) { +pr_err ("FAILED: btf permute: %s\n" ,strerror (-err)); + goto out; + } + +if (distilled_base) { +struct btf *new_btf =NULL , *distilled_base =NULL ; + +if (btf__distill_base (btf, &distilled_base, &new_btf) <0 ) { +pr_err ("FAILED to generate distilled base BTF: %s\n" , +strerror (errno)); + goto out; + } + + err =update_btf_section (obj->path, new_btf,BTF_ELF_SEC ); +if (!err) { + err =update_btf_section (obj->path, distilled_base,BTF_BASE_ELF_SEC ); +if (err <0 ) +pr_err ("FAILED to update '%s'\n" ,BTF_BASE_ELF_SEC ); + }else { +pr_err ("FAILED to update '%s'\n" ,BTF_ELF_SEC ); + } + +btf__free (new_btf); +btf__free (distilled_base); + }else { + err =update_btf_section (obj->path, btf,BTF_ELF_SEC ); +if (err <0 ) { +pr_err ("FAILED to update '%s'\n" ,BTF_ELF_SEC ); + goto out; + } + } + +out: +free (permute_ids); +free (id_map); +btf__free (base_btf); +btf__free (btf); +return err; +} +static const char *const resolve_btfids_usage[] = {"resolve_btfids [<options>] <ELF object>" ,NULL @@ -787,6 +976,8 @@ int main(int argc, const char **argv) .sets = RB_ROOT, };bool fatal_warnings = false; +bool btf_sort = false; +bool distilled_base = false;struct option btfid_options[] = {OPT_INCR ('v' ,"verbose" , &verbose,"be more verbose (show errors, etc)" ),@@ -796,6 +987,10 @@ int main(int argc, const char **argv) "path of file providing base BTF"),OPT_BOOLEAN (0 ,"fatal_warnings" , &fatal_warnings,"turn warnings into errors" ), +OPT_BOOLEAN (0 ,"btf_sort" , &btf_sort, +"sort BTF by name in ascending order" ), +OPT_BOOLEAN (0 ,"distilled_base" , &distilled_base, +"distill base" ), OPT_END() };int err =-1 ;@@ -807,6 +1002,11 @@ int main(int argc, const char **argv) obj.path = argv[0 ]; +if (btf_sort) { + err =sort_update_btf (&obj, distilled_base); + goto out; + } +if (elf_collect (&obj)) goto out;
Ihor Solodrai
reviewerRe: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
Quoted 18 lines · Donglin Peng
Quoted 9 lines · Ihor Solodrai
Quoted 6 lines · Donglin Peng
From: Donglin Peng <[email protected]>
This patch introduces a new --btf_sort option that leverages libbpf's
btf__permuteinterface to reorganize BTF layout. The implementation sorts BTF types by name in ascending order, placing anonymous types at the end to enable efficient binary search lookup.Quoted 7 lines
[...]
Hi Dongling.
Thanks for working on this, it's a great optimization. Just want to give you a heads up that I am preparing a patchset changing
resolve_btfidsbehavior.
Quoted 6 lines
Thanks. I'm curious about the new behavior of
resolve_btfids. Does it replace pahole and generate the sorted .BTF data directly from the DWARF data? Also, does its sorting method differ from thecmp_type_namesapproach mentioned above — specifically, does it place named types before all anonymous types? I'm asking because the search method needs to be compatible with this sorting approach.
No, replacing pahole entirely isn't really feasible, and unnecessary.
TL;DR is that resolve_btfids will also do kernel-specific btf2btf transformations. The sorting feature is independent, it's relevant only in that it is also a btf2btf transformation and will be included in the pipeline.
I described the approach here:
https://lore.kernel.org/dwarves/[email protected]/
Quoted 18 lines
Quoted 18 lines
In particular, instead of updating the .BTF_ids section (and now with your and upcoming changes the .BTF section) *in-place*,
resolve_btfidswill only emit the data for the sections. And then it'll be integrated into vmlinux with objcopy and linker. We already do a similar thing with .BTF for vmlinux [1].For your patchset it means that the parts handling ELF update will be unnecessary.
Also I think the --btf_sort flag is unnecessary. We probably want kernel BTF to always be sorted in this way. And if
resolve_btfidswill be handling more btf2btf transformation, we should avoid adding a flags for every one of them.[1] https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/scripts/link-vmlinux.sh#n110
Re: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
Quoted 29 lines · Ihor Solodrai
Quoted 18 lines · Donglin Peng
Quoted 9 lines · Ihor Solodrai
Quoted 6 lines · Donglin Peng
From: Donglin Peng <[email protected]>
This patch introduces a new --btf_sort option that leverages libbpf's
btf__permuteinterface to reorganize BTF layout. The implementation sorts BTF types by name in ascending order, placing anonymous types at the end to enable efficient binary search lookup.Quoted 7 lines
[...]
Hi Dongling.
Thanks for working on this, it's a great optimization. Just want to give you a heads up that I am preparing a patchset changing
resolve_btfidsbehavior.Quoted 6 lines
Thanks. I'm curious about the new behavior of
resolve_btfids. Does it replace pahole and generate the sorted .BTF data directly from the DWARF data? Also, does its sorting method differ from thecmp_type_namesapproach mentioned above — specifically, does it place named types before all anonymous types? I'm asking because the search method needs to be compatible with this sorting approach.No, replacing pahole entirely isn't really feasible, and unnecessary.
Quoted 7 lines
TL;DR is that
resolve_btfidswill also do kernel-specific btf2btf transformations. The sorting feature is independent, it's relevant only in that it is also a btf2btf transformation and will be included in the pipeline.I described the approach here:
https://lore.kernel.org/dwarves/[email protected]/
Thanks for the explanation.
Quoted 20 lines
Quoted 20 lines
Quoted 20 lines
In particular, instead of updating the .BTF_ids section (and now with your and upcoming changes the .BTF section) *in-place*,
resolve_btfidswill only emit the data for the sections. And then it'll be integrated into vmlinux with objcopy and linker. We already do a similar thing with .BTF for vmlinux [1].For your patchset it means that the parts handling ELF update will be unnecessary.
Also I think the --btf_sort flag is unnecessary. We probably want kernel BTF to always be sorted in this way. And if
resolve_btfidswill be handling more btf2btf transformation, we should avoid adding a flags for every one of them.[1] https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/scripts/link-vmlinux.sh#n110
Eduard Zingerman
maintainerRe: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
In reply to Donglin PengOn Wed, 2025-11-19 at 11:15 +0800, Donglin Peng wrote:
[...]
scripts/Makefile.btf pahole-flags-$(call test-ge, $(pahole-ver), 130) += --btf_features=attributes · line 30
Quoted 9 lines
scripts/Makefile.btf +1
-0@@ -27,6 +27,7 @@ pahole-flags-$(call test-ge, $(pahole-ver), 130) += --btf_features=attributes ifneq ($(KBUILD_EXTMOD),) module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base +module-resolve_btfid-flags-y = --distilled_base
^^^^^^^^^^^^^^^^
This flag should be guarded by pahole version as well. However, I'd suggest not adding this flag at all, but instead modify resolve_btfids to check for BTF_BASE_ELF_SEC section existence and acting accordingly.
Quoted 13 lines
scripts/Makefile.btf +1
-0endif endif@@ -35,3 +36,4 @@ pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) += --lang_exclude=rust export PAHOLE_FLAGS := $(pahole-flags-y) export MODULE_PAHOLE_FLAGS := $(module-pahole-flags-y) +export MODULE_RESOLVE_BTFID_FLAGS := $(module-resolve_btfid-flags-y)scripts/Makefile.modfinal +0
-0
scripts/Makefile.modfinal quiet_cmd_btf_ko = BTF [M] $@ · line 43
Quoted 4 lines
scripts/Makefile.modfinal +1
-0@@ -40,6 +40,7 @@ quiet_cmd_btf_ko = BTF [M] $@ printf "Skipping BTF generation for %s due to unavailability of vmlinux\n" $@ 1>&2; \ else \ LLVM_OBJCOPY="$(OBJCOPY)" $(PAHOLE) -J $(PAHOLE_FLAGS) $(MODULE_PAHOLE_FLAGS) --btf_base $(objtree)/vmlinux $@; \ + $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $(MODULE_RESOLVE_BTFID_FLAGS) --btf_sort $@; \
^^^^^^^^^^
Agree with Ihor (and off-list discussion with Alexei), this flag appears redundant. Are there situations when one would like to avoid sorting kernel/module BTF?
Quoted 2 lines
scripts/Makefile.modfinal +0
-0$(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $@; \ fi;
[...]
Quoted 4 lines
tools/bpf/resolve_btfids/main.c +0
-0
[...]
Quoted 36 lines
tools/bpf/resolve_btfids/main.c +36
-0+static int update_btf_section (const char *path,const struct btf *btf, +const char *btf_secname) +{ +GElf_Shdr shdr_mem, *shdr; +Elf_Data *btf_data =NULL ; +Elf_Scn *scn =NULL ; +Elf *elf =NULL ; +const void *raw_btf_data; +uint32_t raw_btf_size; +int fd, err =-1 ; +size_t strndx; + + fd =open (path,O_RDWR ); +if (fd <0 ) { +pr_err ("FAILED to open %s\n" , path); +return -1 ; + } + +if (elf_version (EV_CURRENT ) ==EV_NONE ) { +pr_err ("FAILED to set libelf version" ); + goto out; + } + + elf =elf_begin (fd,ELF_C_RDWR ,NULL ); +if (elf ==NULL ) { +pr_err ("FAILED to update ELF file" ); + goto out; + } + +elf_flagelf (elf,ELF_C_SET ,ELF_F_LAYOUT ); + +elf_getshdrstrndx (elf, &strndx); +while ((scn =elf_nextscn (elf, scn)) !=NULL ) { +char *secname; + + shdr =gelf_getshdr (scn, &shdr_mem);
tools/bpf/resolve_btfids/main.c static int symbols_patch(struct object *obj) · line 839
Quoted 10 lines
tools/bpf/resolve_btfids/main.c +10
-0+if (shdr ==NULL ) +continue ; + secname =elf_strptr (elf, strndx, shdr->sh_name); +if (strcmp (secname, btf_secname) ==0 ) { + btf_data =elf_getdata (scn, btf_data); +break ; + } + } + + raw_btf_data =btf__raw_data (btf, &raw_btf_size);
btf__raw_data() can return NULL.
Quoted 22 lines
tools/bpf/resolve_btfids/main.c +22
-0+ +if (btf_data) { +if (raw_btf_size != btf_data->d_size) { +pr_err ("FAILED: size mismatch" ); + goto out; + } + + btf_data->d_buf = (void *)raw_btf_data; + btf_data->d_type =ELF_T_WORD ; +elf_flagdata (btf_data,ELF_C_SET ,ELF_F_DIRTY ); + +if (elf_update (elf,ELF_C_WRITE ) >=0 ) + err =0 ; + } + +out: +if (fd !=-1 ) +close (fd); +if (elf) +elf_end (elf); +return err; +}
[...]
Re: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting
Quoted 11 lines · Eduard Zingerman
On Wed, 2025-11-19 at 11:15 +0800, Donglin Peng wrote:
[...]
Quoted 6 lines
scripts/Makefile.btf +0
-0@@ -27,6 +27,7 @@ pahole-flags-$(call test-ge, $(pahole-ver), 130) += --btf_features=attributes
Quoted 7 lines
scripts/Makefile.btf pahole-flags-$(call test-ge, $(pahole-ver), 130) += --btf_features=attributes · line 30
Quoted 3 lines
scripts/Makefile.btf +1
-0ifneq ($(KBUILD_EXTMOD),) module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base +module-resolve_btfid-flags-y = --distilled_base^^^^^^^^^^^^^^^^This flag should be guarded by pahole version as well. However, I'd suggest not adding this flag at all, but instead modify
resolve_btfidsto check forBTF_BASE_ELF_SECsection existence and acting accordingly.
Thanks, I will remove it in the next version.
Quoted 6 lines
Quoted 6 lines
scripts/Makefile.btf +0
-0endif endif@@ -35,3 +36,4 @@ pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) += --lang_exclude=rust
Quoted 16 lines
scripts/Makefile.modfinal quiet_cmd_btf_ko = BTF [M] $@ · line 43
Quoted 12 lines
scripts/Makefile.btf +1
-0export PAHOLE_FLAGS := $(pahole-flags-y) export MODULE_PAHOLE_FLAGS := $(module-pahole-flags-y) +export MODULE_RESOLVE_BTFID_FLAGS := $(module-resolve_btfid-flags-y)scripts/Makefile.modfinal +1
-0@@ -40,6 +40,7 @@ quiet_cmd_btf_ko = BTF [M] $@ printf "Skipping BTF generation for %s due to unavailability of vmlinux\n" $@ 1>&2; \ else \ LLVM_OBJCOPY="$(OBJCOPY)" $(PAHOLE) -J $(PAHOLE_FLAGS) $(MODULE_PAHOLE_FLAGS) --btf_base $(objtree)/vmlinux $@; \ + $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $(MODULE_RESOLVE_BTFID_FLAGS) --btf_sort $@; \^^^^^^^^^^
Agree with Ihor (and off-list discussion with Alexei), this flag appears redundant. Are there situations when one would like to avoid sorting kernel/module BTF?
Thanks, I will make sorting unconditional.
Quoted 53 lines
Quoted 3 lines
scripts/Makefile.modfinal +0
-0$(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $@; \ fi;[...]
Quoted 4 lines
tools/bpf/resolve_btfids/main.c +0
-0[...]
Quoted 40 lines
tools/bpf/resolve_btfids/main.c +40
-0+static int update_btf_section (const char *path,const struct btf *btf, +const char *btf_secname) +{ +GElf_Shdr shdr_mem, *shdr; +Elf_Data *btf_data =NULL ; +Elf_Scn *scn =NULL ; +Elf *elf =NULL ; +const void *raw_btf_data; +uint32_t raw_btf_size; +int fd, err =-1 ; +size_t strndx; + + fd =open (path,O_RDWR ); +if (fd <0 ) { +pr_err ("FAILED to open %s\n" , path); +return -1 ; + } + +if (elf_version (EV_CURRENT ) ==EV_NONE ) { +pr_err ("FAILED to set libelf version" ); + goto out; + } + + elf =elf_begin (fd,ELF_C_RDWR ,NULL ); +if (elf ==NULL ) { +pr_err ("FAILED to update ELF file" ); + goto out; + } + +elf_flagelf (elf,ELF_C_SET ,ELF_F_LAYOUT ); + +elf_getshdrstrndx (elf, &strndx); +while ((scn =elf_nextscn (elf, scn)) !=NULL ) { +char *secname; + + shdr =gelf_getshdr (scn, &shdr_mem); +if (shdr ==NULL ) +continue ; + secname =elf_strptr (elf, strndx, shdr->sh_name); +if (strcmp (secname, btf_secname) ==0 ) {
Quoted 8 lines
tools/bpf/resolve_btfids/main.c static int symbols_patch(struct object *obj) · line 839
Quoted 6 lines
tools/bpf/resolve_btfids/main.c +6
-0+ btf_data =elf_getdata (scn, btf_data); +break ; + } + } + + raw_btf_data =btf__raw_data (btf, &raw_btf_size);
btf__raw_data()can return NULL.
Thanks, I will fix it.
Quoted 25 lines
Quoted 23 lines
tools/bpf/resolve_btfids/main.c +22
-0+ +if (btf_data) { +if (raw_btf_size != btf_data->d_size) { +pr_err ("FAILED: size mismatch" ); + goto out; + } + + btf_data->d_buf = (void *)raw_btf_data; + btf_data->d_type =ELF_T_WORD ; +elf_flagdata (btf_data,ELF_C_SET ,ELF_F_DIRTY ); + +if (elf_update (elf,ELF_C_WRITE ) >=0 ) + err =0 ; + } + +out: +if (fd !=-1 ) +close (fd); +if (elf) +elf_end (elf); +return err; +}[...]
RFC PATCH v7 4/7 libbpf: Optimize type lookup with binary search for sorted BTF
In reply to Donglin PengFrom: Donglin Peng <[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 | 104 ++++++++++++++++++++++++++++++++++---------- 1 file changed, 81 insertions(+), 23 deletions(-)
tools/lib/bpf/btf.c +81 -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,93 @@ 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) +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name, +__s32 start_id,__s32 end_id) { -__u32 i, nr_types =btf__type_cnt (btf); +const struct btf_type *t; +const char *tname; +__s32 l, r, m; + + l = start_id; + r = end_id; +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; + r = m; + }else { + l = m +1 ; + } + } -if (!strcmp (type_name,"void" )) -return 0 ; +return btf__type_cnt (btf); +} -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); +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 (start_id < btf->start_id) { + err =btf_find_type_by_name_kind (btf->base_btf, start_id, + type_name, kind); +if (err >0 ) + goto out; + start_id = btf->start_id; + } + +if (btf->nr_sorted_types >0 ) { +/* binary search */ +__s32 end_id; +int idx; + + end_id = btf->start_id + btf->nr_sorted_types -1 ; + idx =btf_find_type_by_name_bsearch (btf, type_name, start_id, end_id); +for (; idx <= end_id; idx++) { + t =btf__type_by_id (btf, idx); + tname =btf__str_by_offset (btf, t->name_off); +if (strcmp (tname, type_name)) + goto out; +if (kind ==-1 ||btf_kind (t) == kind) +return idx; + } + }else { +/* linear search */ +__u32 i, total; -if (name && !strcmp (type_name, name)) -return i; + 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,
@@ -1006,6 +1061,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 =0 ;if (base_btf) { btf->base_btf = base_btf;
@@ -1057,6 +1113,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 =0 ;if (base_btf) { btf->base_btf = base_btf;
@@ -1715,6 +1772,7 @@ static void btf_invalidate_raw_data(struct btf *btf)free (btf->raw_data_swapped); btf->raw_data_swapped =NULL ; } + btf->nr_sorted_types =0 ; }/* Ensure BTF is ready to be modified (by splitting into a three memory
Signature · 1 line
2.34.1
[email protected]
AI reviewRe: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF
Can strcmp() handle a NULL tname here? The btf__str_by_offset() function returns NULL when offset is out of range (line 1674 returns "errno = EINVAL, NULL"), but strcmp() requires non-NULL arguments.
Quoted 4 lines
tools/lib/bpf/btf.c +0
-0
[ ... ]
Quoted 10 lines
tools/lib/bpf/btf.c +3
-2@@ -897,44 +903,93 @@ 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) +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name, +__s32 start_id,__s32 end_id) { -__u32 i, nr_types =btf__type_cnt (btf); +const struct btf_type *t;
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 919
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+const char *tname; +__s32 l, r, m; + + l = start_id; + r = end_id; +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 ) {
^^^^^^
Can strcmp() handle a NULL tname here? The btf__str_by_offset() function returns NULL when offset is out of range (line 1674 returns "errno = EINVAL, NULL"), but strcmp() requires non-NULL arguments.
The original linear search code at line 971 checks "if (tname && !strcmp(tname, type_name))" before calling strcmp(). Should the binary search path also check for NULL?
Quoted 27 lines
tools/lib/bpf/btf.c +27
-0+if (l == r) +return r; + r = m; + }else { + l = m +1 ; + } + } + +return btf__type_cnt (btf); +} + +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 (start_id < btf->start_id) { + err =btf_find_type_by_name_kind (btf->base_btf, start_id, + type_name, kind); +if (err >0 ) + goto out; + start_id = btf->start_id; + } + +if (btf->nr_sorted_types >0 ) {
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 956
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+/* binary search */ +__s32 end_id; +int idx; + + end_id = btf->start_id + btf->nr_sorted_types -1 ; + idx =btf_find_type_by_name_bsearch (btf, type_name, start_id, end_id); +for (; idx <= end_id; idx++) { + t =btf__type_by_id (btf, idx); + tname =btf__str_by_offset (btf, t->name_off); +if (strcmp (tname, type_name))
^^^^^^
Same question here - can tname be NULL at this point?
Quoted 8 lines
tools/lib/bpf/btf.c +8
-0+ goto out; +if (kind ==-1 ||btf_kind (t) == kind) +return idx; + } + }else { +/* linear search */ +__u32 i, total; +
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 987
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ 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; + } + }
[ ... ]
---
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/19488781158
Re: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF
Quoted 29 lines · On Wed, Nov 19, 2025 at 12:11 PM <[email protected]> wrote:
Quoted 5 lines
tools/lib/bpf/btf.c +0
-0[ ... ]
Quoted 10 lines
tools/lib/bpf/btf.c +3
-2@@ -897,44 +903,93 @@ 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) +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name, +__s32 start_id,__s32 end_id) { -__u32 i, nr_types =btf__type_cnt (btf); +const struct btf_type *t;tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 919
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+const char *tname; +__s32 l, r, m; + + l = start_id; + r = end_id; +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 ) {^^^^^^
Quoted 7 lines
Can
strcmp()handle a NULL tname here? Thebtf__str_by_offset()function returns NULL when offset is out of range (line 1674 returns "errno = EINVAL, NULL"), butstrcmp()requires non-NULL arguments.The original linear search code at line 971 checks "if (tname && !strcmp(tname,
type_name))" before callingstrcmp(). Should the binary search path also check for NULL?
Thank you. It is unnecessary to check for a NULL type name in this context because the btf_check_sorted function introduced in the subsequent patch ensures that all types accessed via binary search have non-NULL names.
Furthermore, in the current patch, nr_sorted_types is always zero, meaning the binary search path is never exercised.
Quoted 39 lines
Quoted 28 lines
tools/lib/bpf/btf.c +27
-0+if (l == r) +return r; + r = m; + }else { + l = m +1 ; + } + } + +return btf__type_cnt (btf); +} + +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 (start_id < btf->start_id) { + err =btf_find_type_by_name_kind (btf->base_btf, start_id, + type_name, kind); +if (err >0 ) + goto out; + start_id = btf->start_id; + } + +if (btf->nr_sorted_types >0 ) {tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 956
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+/* binary search */ +__s32 end_id; +int idx; + + end_id = btf->start_id + btf->nr_sorted_types -1 ; + idx =btf_find_type_by_name_bsearch (btf, type_name, start_id, end_id); +for (; idx <= end_id; idx++) { + t =btf__type_by_id (btf, idx); + tname =btf__str_by_offset (btf, t->name_off); +if (strcmp (tname, type_name))^^^^^^
Quoted 1 line
Same question here - can tname be NULL at this point?
Ditto.
Quoted 28 lines
Quoted 9 lines
tools/lib/bpf/btf.c +8
-0+ goto out; +if (kind ==-1 ||btf_kind (t) == kind) +return idx; + } + }else { +/* linear search */ +__u32 i, total; +tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 987
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ 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; + } + }[ ... ]
---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/19488781158
Re: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF
In reply to Donglin PengQuoted 22 lines · Donglin Peng
From: Donglin Peng <[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]>Cc Xiaoqin Zhang <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 104 ++++++++++++++++++++++++++++++++++---------- 1 file changed, 81 insertions(+), 23 deletions(-)
[...]
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 940
Quoted 7 lines
tools/lib/bpf/btf.c +7
-0+const struct btf_type *t; +const char *tname; +int err = -ENOENT ; + +if (start_id < btf->start_id) { + err =btf_find_type_by_name_kind (btf->base_btf, start_id, + type_name, kind);
nit: align wrapped args on the second line
also, we expect that err will be set to -ENOENT if we didn't find a match in the base BTF, right? I'm a bit uneasy about this, I'd rather do explicit err = -ENOENT setting for each goto out
Quoted 6 lines
tools/lib/bpf/btf.c +6
-0+if (err >0 ) + goto out; + start_id = btf->start_id; + } + +if (btf->nr_sorted_types >0 ) {
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 956
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+/* binary search */ +__s32 end_id; +int idx; + + end_id = btf->start_id + btf->nr_sorted_types -1 ; + idx =btf_find_type_by_name_bsearch (btf, type_name, start_id, end_id); +for (; idx <= end_id; idx++) { + t =btf__type_by_id (btf, idx); + tname =btf__str_by_offset (btf, t->name_off); +if (strcmp (tname, type_name))
nit: please add explicit != 0 here
also, why not just return -ENOENT;?
Quoted 7 lines
tools/lib/bpf/btf.c +7
-0+ goto out; +if (kind ==-1 ||btf_kind (t) == kind) +return idx; + } + }else { +/* linear search */ +__u32 i, total;
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 +7
-2-if (name && !strcmp (type_name, name)) -return i; + 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))
nit: let's do explicit == 0 for strcmp, please
Quoted 6 lines
tools/lib/bpf/btf.c +3
-1+return i; + } } -return libbpf_err (-ENOENT ); +out:
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 984
Quoted 10 lines
tools/lib/bpf/btf.c +1
-2+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 ;
this is the only thing that btf_find_by_name_kind() does on top of what btf_find_type_by_name_kind(), right? Any reason we can't merge those and keep only btf_find_by_name_kind()?
Quoted 14 lines
tools/lib/bpf/btf.c +2
-10-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)); +}
[...]
Re: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF
Quoted 35 lines · Andrii Nakryiko
Quoted 22 lines · Donglin Peng
From: Donglin Peng <[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]>Cc Xiaoqin Zhang <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 104 ++++++++++++++++++++++++++++++++++---------- 1 file changed, 81 insertions(+), 23 deletions(-)[...]
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 940
Quoted 7 lines
tools/lib/bpf/btf.c +7
-0+const struct btf_type *t; +const char *tname; +int err = -ENOENT ; + +if (start_id < btf->start_id) { + err =btf_find_type_by_name_kind (btf->base_btf, start_id, + type_name, kind);
Quoted 5 lines
nit: align wrapped args on the second line
also, we expect that err will be set to
-ENOENTif we didn't find a match in the base BTF, right? I'm a bit uneasy about this, I'd rather do explicit err =-ENOENTsetting for each goto out
Thanks, I will refactor it.
Quoted 11 lines
Quoted 11 lines
tools/lib/bpf/btf.c +10
-0+if (err >0 ) + goto out; + start_id = btf->start_id; + } + +if (btf->nr_sorted_types >0 ) { +/* binary search */ +__s32 end_id; +int idx; +
Quoted 8 lines
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 956
Quoted 6 lines
tools/lib/bpf/btf.c +6
-0+ end_id = btf->start_id + btf->nr_sorted_types -1 ; + idx =btf_find_type_by_name_bsearch (btf, type_name, start_id, end_id); +for (; idx <= end_id; idx++) { + t =btf__type_by_id (btf, idx); + tname =btf__str_by_offset (btf, t->name_off); +if (strcmp (tname, type_name))nit: please add explicit != 0 here
Thanks. I will fix it.
Quoted 2 lines
also, why not just
return -ENOENT;?
I thought about that, but I feel the function should return from one place. Frankly, just returning -ENOENT is cleaner
Quoted 19 lines
Quoted 8 lines
tools/lib/bpf/btf.c +7
-0+ goto out; +if (kind ==-1 ||btf_kind (t) == kind) +return idx; + } + }else { +/* linear search */ +__u32 i, total;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 +7
-2-if (name && !strcmp (type_name, name)) -return i; + 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))
Quoted 1 line
nit: let's do explicit == 0 for strcmp, please
Thanks, I will fix it.
Quoted 10 lines
Quoted 10 lines
tools/lib/bpf/btf.c +4
-1+return i; + } } -return libbpf_err (-ENOENT ); +out: +return err; }
Quoted 11 lines
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 984
Quoted 7 lines
static
__s32btf_find_by_name_kind(const struct btf *btf, intstart_id,
const char*type_name,__u32kind)
{tools/lib/bpf/btf.c +0
-2-__u32 i, nr_types =btf__type_cnt (btf); -if (kind ==BTF_KIND_UNKN || !strcmp (type_name,"void" ))return 0 ;this is the only thing that
btf_find_by_name_kind()does on top of whatbtf_find_type_by_name_kind(), right? Any reason we can't merge those and keep onlybtf_find_by_name_kind()?
Thanks. The check exists in the original btf_find_by_name_kind. Because btf_find_type_by_name_kind uses recursion, adding the check there would cause it to run multiple times. I'm open to merging the functions if the overhead is acceptable.
Quoted 17 lines
Quoted 15 lines
tools/lib/bpf/btf.c +2
-10-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)); +}[...]
RFC PATCH v7 5/7 libbpf: Implement BTF type sorting validation for binary search optimization
In reply to Donglin PengFrom: Donglin Peng <[email protected]>
This patch adds validation to verify BTF type name sorting, enabling binary search optimization for lookups.
--- tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+)
tools/lib/bpf/btf.c +59 -0
@@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; } +/* Anonymous types (with empty names) are considered greater than named types +* and are sorted after them. Two anonymous types are considered equal. Named +* types are compared lexicographically. +*/ +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 that BTF types are sorted in ascending order according to their +* names, with named types appearing before anonymous types. If the ordering +* is correct, counts the number of named types and updates the BTF object's +* nr_sorted_types field. +*/ +static void btf_check_sorted (struct btf *btf) +{ +const struct btf_type *t; +int i, k =0 , n, nr_sorted_types; + +if (btf->nr_types <2 ) +return ; + + nr_sorted_types =0 ; + n =btf__type_cnt (btf) -1 ; +for (i = btf->start_id; i < n; i++) { + k = i +1 ; +if (btf_compare_type_names (&i, &k, btf) >0 ) +return ; + t =btf_type_by_id (btf, i); +if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; + } + + t =btf_type_by_id (btf, k); +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; +} +static __s32 btf_find_type_by_name_bsearch (const struct btf *btf,const char *name,__s32 start_id,__s32 end_id) {
@@ -1148,6 +1206,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b err = err ?:btf_sanity_check (btf);if (err) goto done; +btf_check_sorted (btf); done:if (err) {
Signature · 1 line
2.34.1
Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
Quoted 38 lines · Donglin Peng
From: Donglin Peng <[email protected]>
This patch adds validation to verify BTF type name sorting, enabling binary search optimization for lookups.
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]>Cc Xiaoqin Zhang <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+)tools/lib/bpf/btf.c +13
-0@@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; } +/* Anonymous types (with empty names) are considered greater than named types +* and are sorted after them. Two anonymous types are considered equal. Named +* types are compared lexicographically. +*/ +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);
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 928
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ 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 ;
any reason to hard-code that anonymous types should come *after* named ones? That requires custom comparison logic here and resolve_btfids, instead of just relying on btf__str_by_offset() returning valid empty string for name_off == 0 and then sorting anon types before named ones, following normal lexicographical sorting rules?
[...]
Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
Quoted 48 lines · Andrii Nakryiko
Quoted 46 lines · Donglin Peng
From: Donglin Peng <[email protected]>
This patch adds validation to verify BTF type name sorting, enabling binary search optimization for lookups.
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]>Cc Xiaoqin Zhang <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+)tools/lib/bpf/btf.c +21
-0@@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; } +/* Anonymous types (with empty names) are considered greater than named types +* and are sorted after them. Two anonymous types are considered equal. Named +* types are compared lexicographically. +*/ +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 ;
Quoted 8 lines
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 928
Quoted 2 lines
tools/lib/bpf/btf.c +2
-0+if (anon_a && anon_b) +return 0 ;any reason to hard-code that anonymous types should come *after* named ones? That requires custom comparison logic here and
resolve_btfids, instead of just relying onbtf__str_by_offset()returning valid empty string forname_off== 0 and then sorting anon types before named ones, following normal lexicographical sorting rules?
Thanks. I found that some kernel functions like btf_find_next_decl_tag, bpf_core_add_cands, find_bpffs_btf_enums, and find_btf_percpu_datasec still use linear search. Putting named types first would also help here, as it allows anonymous types to be skipped naturally during the search. Some of them could be refactored to use btf_find_by_name_kind, but some would not be appropriate, such as btf_find_next_decl_tag, bpf_core_add_cands,find_btf_percpu_datasec.
Additionally, in the linear search branch, I saw there is a NULL check for the name returned by btf__name_by_offset. This suggests that checking name_off == 0 alone may not be sufficient to identify an anonymous type, which is why I used str_is_empty for a more robust check.
Quoted 2 lines
[...]
Eduard Zingerman
maintainerRe: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
Quoted 59 lines · Donglin Peng
Quoted 48 lines · Andrii Nakryiko
Quoted 46 lines · Donglin Peng
From: Donglin Peng <[email protected]>
This patch adds validation to verify BTF type name sorting, enabling binary search optimization for lookups.
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]>Cc Xiaoqin Zhang <[email protected]>Signed-off-by Donglin Peng <[email protected]>---
tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++1 file changed, 59 insertions(+)tools/lib/bpf/btf.c +21
-0@@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id) return type_id; } +/* Anonymous types (with empty names) are considered greater than named types +* and are sorted after them. Two anonymous types are considered equal. Named +* types are compared lexicographically. +*/ +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;Quoted 8 lines
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 928
Quoted 2 lines
tools/lib/bpf/btf.c +2
-0+ if (anon_a && anon_b) + return 0;any reason to hard-code that anonymous types should come *after* named ones? That requires custom comparison logic here and
resolve_btfids, instead of just relying onbtf__str_by_offset()returning valid empty string forname_off== 0 and then sorting anon types before named ones, following normal lexicographical sorting rules?
Quoted 3 lines
Thanks. I found that some kernel functions like
btf_find_next_decl_tag,bpf_core_add_cands,find_bpffs_btf_enums, andfind_btf_percpu_datasecstill use linear search.
- btf_find_next_decl_tag() - this function is called from:
- btf_find_decl_tag_value(), here whole scan over all BTF types is guaranteed to happen (because btf_find_next_decl_tag() is called twice);
- btf_prepare_func_args(), here again whole scan is guaranteed to
happen, because of the while loop starting from id == 0.
- bpf_core_add_cands() this function is called from bpf_core_find_cands(), where it does a linear scan over all types in kernel BTF and then a linear scan over all types in module BTFs. (Because of how targ_start_id parameter is passed).
- find_bpffs_btf_enums() - this function does a linear scan over all types in module BTFs.
- find_btf_percpu_datasec() - this function looks for a DATASEC with name ".data..percpu" and returns as soon as the match is found.
Of the 4 functions above only find_btf_percpu_datasec() will return early if BTF type with specified name is found. And it can be converted to use btf_find_by_name_kind().
So, it appears that there should not be any performance penalty (compared to current state of affairs) if anonymous types are put in front. Wdyt?
Quoted 5 lines
Putting named types first would also help here, as
it allows anonymous types to be skipped naturally during the search. Some of them could be refactored to usebtf_find_by_name_kind, but some would not be appropriate, such asbtf_find_next_decl_tag, bpf_core_add_cands,find_btf_percpu_datasec.
Did you observe any performance issue if anonymous types are put in the front?
Quoted 7 lines
Additionally, in the linear search branch, I saw there is a NULL check for the name returned by
btf__name_by_offset. This suggests that checkingname_off== 0 alone may not be sufficient to identify an anonymous type, which is why I usedstr_is_emptyfor a more robust check.Quoted 2 lines
[...]
Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
Quoted 65 lines · Eduard Zingerman
Quoted 59 lines · Donglin Peng
Quoted 48 lines · Andrii Nakryiko
Quoted 46 lines · Donglin Peng
From: Donglin Peng <[email protected]>
This patch adds validation to verify BTF type name sorting, enabling binary search optimization for lookups.
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]>Cc Xiaoqin Zhang <[email protected]>Signed-off-by Donglin Peng <[email protected]>--- tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+)tools/lib/bpf/btf.c +21
-0@@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)return type_id; } +/* Anonymous types (with empty names) are considered greater than named types +* and are sorted after them. Two anonymous types are considered equal. Named +* types are compared lexicographically. +*/ +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 ;Quoted 8 lines
tools/lib/bpf/btf.c int btf__resolve_type(const struct btf *btf, __u32 type_id) · line 928
Quoted 2 lines
tools/lib/bpf/btf.c +2
-0+if (anon_a && anon_b) +return 0 ;any reason to hard-code that anonymous types should come *after* named ones? That requires custom comparison logic here and
resolve_btfids, instead of just relying onbtf__str_by_offset()returning valid empty string forname_off== 0 and then sorting anon types before named ones, following normal lexicographical sorting rules?Quoted 3 lines
Thanks. I found that some kernel functions like
btf_find_next_decl_tag,bpf_core_add_cands,find_bpffs_btf_enums, andfind_btf_percpu_datasecstill use linear search.
Quoted 6 lines
-
btf_find_next_decl_tag()- this function is called from:
-btf_find_decl_tag_value(), here whole scan over all BTF types is guaranteed to happen (becausebtf_find_next_decl_tag()is called twice);
-btf_prepare_func_args(), here again whole scan is guaranteed tohappen, because of the while loop starting from id == 0.
Right.
Quoted 4 lines
-
bpf_core_add_cands()this function is called frombpf_core_find_cands(), where it does a linear scan over all types in kernel BTF and then a linear scan over all types in module BTFs. (Because of howtarg_start_idparameter is passed).
Right.
Quoted 2 lines
-
find_bpffs_btf_enums()- this function does a linear scan over all types in module BTFs.
I think putting names ahead is helpful here, because there is a check (info->cmd_t && info->map_t && info->prog_t && info->attach_t) to return early. but I think it can be converted to use btf_find_by_name_kind.
Quoted 6 lines
-
find_btf_percpu_datasec()- this function looks for a DATASEC with name ".data..percpu" and returns as soon as the match is found.Of the 4 functions above only
find_btf_percpu_datasec()will return early if BTF type with specified name is found. And it can be converted to usebtf_find_by_name_kind().
Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use btf_find_by_name_kind here because the search scope differs. For a module BTF, find_btf_percpu_datasec only searches within the module’s own BTF, whereas btf_find_by_name_kind prioritizes searching the base BTF first. Thus, placing named types ahead is more effective here. Besides, I found that the '.data..percpu' named type will be placed at [1] for vmlinux BTF because the prefix '.' is smaller than any letter, so the linear search only requires one loop to locate it. However, if we put named types at the end, it will need more than 60,000 loops..
Quoted 5 lines
So, it appears that there should not be any performance penalty (compared to current state of affairs) if anonymous types are put in front. Wdyt?
Quoted 8 lines
Quoted 5 lines
Putting named types first would also help here, as
it allows anonymous types to be skipped naturally during the search. Some of them could be refactored to usebtf_find_by_name_kind, but some would not be appropriate, such asbtf_find_next_decl_tag, bpf_core_add_cands,find_btf_percpu_datasec.Did you observe any performance issue if anonymous types are put in the front?
No, I have not done such a test, but based on the above analysis, the improvement
mainly comes from find_bpffs_btf_enums and find_btf_percpu_datasec.
Quoted 8 lines
Quoted 8 lines
Additionally, in the linear search branch, I saw there is a NULL check for the name returned by
btf__name_by_offset. This suggests that checkingname_off== 0 alone may not be sufficient to identify an anonymous type, which is why I usedstr_is_emptyfor a more robust check.Quoted 2 lines
[...]
Eduard Zingerman
maintainerRe: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
On Sat, 2025-11-22 at 15:19 +0800, Donglin Peng wrote:
[...]
Quoted 6 lines
Quoted 2 lines
-
find_bpffs_btf_enums()- this function does a linear scan over all types in module BTFs.I think putting names ahead is helpful here, because there is a check (
info->cmd_t&&info->map_t&&info->prog_t&&info->attach_t) to return early. but I think it can be converted to usebtf_find_by_name_kind.
Oh, sorry, I somehow missed the early exit here.
But as you say, it is a combination of 4 by-name lookups, essentially. Thus can be converted to btf_find_by_name_kind() trivially.
Quoted 7 lines
Quoted 6 lines
-
find_btf_percpu_datasec()- this function looks for a DATASEC with name ".data..percpu" and returns as soon as the match is found.Of the 4 functions above only
find_btf_percpu_datasec()will return early if BTF type with specified name is found. And it can be converted to usebtf_find_by_name_kind().
Quoted 10 lines
Thanks. I’ve looked into
find_btf_percpu_datasecand we can’t usebtf_find_by_name_kindhere because the search scope differs. For a module BTF,find_btf_percpu_dataseconly searches within the module’s own BTF, whereasbtf_find_by_name_kindprioritizes searching the base BTF first. Thus, placing named types ahead is more effective here. Besides, I found that the '.data..percpu' named type will be placed at [1] for vmlinux BTF because the prefix '.' is smaller than any letter, so the linear search only requires one loop to locate it. However, if we put named types at the end, it will need more than 60,000 loops..
But this can be easily fixed if a variant of btf_find_by_name_kind() is provided that looks for a match only in a specific BTF. Or accepts a start id parameter.
Eduard Zingerman
maintainerRe: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
On Sat, 2025-11-22 at 00:50 -0800, Eduard Zingerman wrote:
[...]
Quoted 11 lines
Quoted 10 lines
Thanks. I’ve looked into
find_btf_percpu_datasecand we can’t usebtf_find_by_name_kindhere because the search scope differs. For a module BTF,find_btf_percpu_dataseconly searches within the module’s own BTF, whereasbtf_find_by_name_kindprioritizes searching the base BTF first. Thus, placing named types ahead is more effective here. Besides, I found that the '.data..percpu' named type will be placed at [1] for vmlinux BTF because the prefix '.' is smaller than any letter, so the linear search only requires one loop to locate it. However, if we put named types at the end, it will need more than 60,000 loops..
Quoted 3 lines
But this can be easily fixed if a variant of
btf_find_by_name_kind()is provided that looks for a match only in a specific BTF. Or accepts a start id parameter.
Also, I double checked, and for my vmlinux the id for '.data..percpu' section is 110864, the last id of all. So, having all anonymous types in front does not change status-quo compared to current implementation.
Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
Quoted 16 lines · Eduard Zingerman
On Sat, 2025-11-22 at 00:50 -0800, Eduard Zingerman wrote:
[...]
Quoted 11 lines
Quoted 10 lines
Thanks. I’ve looked into
find_btf_percpu_datasecand we can’t usebtf_find_by_name_kindhere because the search scope differs. For a module BTF,find_btf_percpu_dataseconly searches within the module’s own BTF, whereasbtf_find_by_name_kindprioritizes searching the base BTF first. Thus, placing named types ahead is more effective here. Besides, I found that the '.data..percpu' named type will be placed at [1] for vmlinux BTF because the prefix '.' is smaller than any letter, so the linear search only requires one loop to locate it. However, if we put named types at the end, it will need more than 60,000 loops..
Quoted 7 lines
Quoted 3 lines
But this can be easily fixed if a variant of
btf_find_by_name_kind()is provided that looks for a match only in a specific BTF. Or accepts a start id parameter.Also, I double checked, and for my vmlinux the id for '.data..percpu' section is 110864, the last id of all. So, having all anonymous types in front does not change status-quo compared to current implementation.
Yes. If types are sorted alphabetically, the '.data..percpu' section will have ID 1 in vmlinux BTF. In this case, linear search performance is optimal when named types are placed ahead of anonymous types.
I would like to understand the benefits of having anonymous types at the front of named types.
Eduard Zingerman
maintainerRe: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
Quoted 25 lines · Donglin Peng
Quoted 16 lines · Eduard Zingerman
On Sat, 2025-11-22 at 00:50 -0800, Eduard Zingerman wrote:
[...]
Quoted 11 lines
Quoted 10 lines
Thanks. I’ve looked into
find_btf_percpu_datasecand we can’t usebtf_find_by_name_kindhere because the search scope differs. For a module BTF,find_btf_percpu_dataseconly searches within the module’s own BTF, whereasbtf_find_by_name_kindprioritizes searching the base BTF first. Thus, placing named types ahead is more effective here. Besides, I found that the '.data..percpu' named type will be placed at [1] for vmlinux BTF because the prefix '.' is smaller than any letter, so the linear search only requires one loop to locate it. However, if we put named types at the end, it will need more than 60,000 loops..Quoted 7 lines
Quoted 3 lines
But this can be easily fixed if a variant of
btf_find_by_name_kind()is provided that looks for a match only in a specific BTF. Or accepts a start id parameter.Also, I double checked, and for my vmlinux the id for '.data..percpu' section is 110864, the last id of all. So, having all anonymous types in front does not change status-quo compared to current implementation.
Quoted 6 lines
Yes. If types are sorted alphabetically, the '.data..percpu' section will have ID 1 in vmlinux BTF. In this case, linear search performance is optimal when named types are placed ahead of anonymous types.
I would like to understand the benefits of having anonymous types at the front of named types.
This will allow using strcmp() instead of btf_compare_type_names(), which we have to copy both in kernel and in libbpf. Reducing the code size and cognitive load.
Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
Quoted 31 lines · Eduard Zingerman
Quoted 29 lines · Donglin Peng
Quoted 16 lines · Eduard Zingerman
On Sat, 2025-11-22 at 00:50 -0800, Eduard Zingerman wrote:
[...]
Quoted 11 lines
Quoted 10 lines
Thanks. I’ve looked into
find_btf_percpu_datasecand we can’t usebtf_find_by_name_kindhere because the search scope differs. For a module BTF,find_btf_percpu_dataseconly searches within the module’s own BTF, whereasbtf_find_by_name_kindprioritizes searching the base BTF first. Thus, placing named types ahead is more effective here. Besides, I found that the '.data..percpu' named type will be placed at [1] for vmlinux BTF because the prefix '.' is smaller than any letter, so the linear search only requires one loop to locate it. However, if we put named types at the end, it will need more than 60,000 loops..Quoted 7 lines
Quoted 3 lines
But this can be easily fixed if a variant of
btf_find_by_name_kind()is provided that looks for a match only in a specific BTF. Or accepts a start id parameter.Also, I double checked, and for my vmlinux the id for '.data..percpu' section is 110864, the last id of all. So, having all anonymous types in front does not change status-quo compared to current implementation.
Yes. If types are sorted alphabetically, the '.data..percpu' section will have ID 1 in vmlinux BTF. In this case, linear search performance is optimal when named types are placed ahead of anonymous types.
Quoted 6 lines
Quoted 2 lines
I would like to understand the benefits of having anonymous types at the front of named types.
This will allow using
strcmp()instead ofbtf_compare_type_names(), which we have to copy both in kernel and in libbpf. Reducing the code size and cognitive load.
Thanks, I will fix it in the next version.
Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
In reply to Eduard ZingermanQuoted 34 lines · Eduard Zingerman
On Sat, 2025-11-22 at 15:19 +0800, Donglin Peng wrote:
[...]
Quoted 6 lines
Quoted 2 lines
-
find_bpffs_btf_enums()- this function does a linear scan over all types in module BTFs.I think putting names ahead is helpful here, because there is a check (
info->cmd_t&&info->map_t&&info->prog_t&&info->attach_t) to return early. but I think it can be converted to usebtf_find_by_name_kind.Oh, sorry, I somehow missed the early exit here.
But as you say, it is a combination of 4 by-name lookups, essentially. Thus can be converted tobtf_find_by_name_kind()trivially.Quoted 7 lines
Quoted 6 lines
-
find_btf_percpu_datasec()- this function looks for a DATASEC with name ".data..percpu" and returns as soon as the match is found.Of the 4 functions above only
find_btf_percpu_datasec()will return early if BTF type with specified name is found. And it can be converted to usebtf_find_by_name_kind().Quoted 10 lines
Thanks. I’ve looked into
find_btf_percpu_datasecand we can’t usebtf_find_by_name_kindhere because the search scope differs. For a module BTF,find_btf_percpu_dataseconly searches within the module’s own BTF, whereasbtf_find_by_name_kindprioritizes searching the base BTF first. Thus, placing named types ahead is more effective here. Besides, I found that the '.data..percpu' named type will be placed at [1] for vmlinux BTF because the prefix '.' is smaller than any letter, so the linear search only requires one loop to locate it. However, if we put named types at the end, it will need more than 60,000 loops..
Quoted 3 lines
But this can be easily fixed if a variant of
btf_find_by_name_kind()is provided that looks for a match only in a specific BTF. Or accepts a start id parameter.
Yes, but I'm not sure it's necessary to add a new parameter to btf_find_by_name_kind for just one use case.
Eduard Zingerman
maintainerRe: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
In reply to Donglin PengOn Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
[...]
Quoted 4 lines
Additionally, in the linear search branch, I saw there is a NULL check for the name returned by
btf__name_by_offset. This suggests that checkingname_off== 0 alone may not be sufficient to identify an anonymous type, which is why I usedstr_is_emptyfor a more robust check.
btf_str_by_offset(btf, offset) returns NULL only when 'offset' is larger then 'btf->hdr.str_len'. However, function btf_check_meta() verifies that this shall not happen by invoking btf_name_offset_valid() check. The btf_check_meta() is invoked for all types by btf_check_all_metas() called from btf_parse_base(), btf_parse_module() and btf_parse_type_sec() -> btf_parse().
So, it appears that kernel protects itself from invalid name_off values at BTF load time.
[...]
Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
Quoted 17 lines · Eduard Zingerman
On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
[...]
Quoted 4 lines
Additionally, in the linear search branch, I saw there is a NULL check for the name returned by
btf__name_by_offset. This suggests that checkingname_off== 0 alone may not be sufficient to identify an anonymous type, which is why I usedstr_is_emptyfor a more robust check.
btf_str_by_offset(btf, offset)returns NULL only when 'offset' is larger then 'btf->hdr.str_len'. However, functionbtf_check_meta()verifies that this shall not happen by invokingbtf_name_offset_valid()check. Thebtf_check_meta()is invoked for all types bybtf_check_all_metas()called frombtf_parse_base(),btf_parse_module()andbtf_parse_type_sec()->btf_parse().
Quoted 2 lines
So, it appears that kernel protects itself from invalid
name_offvalues at BTF load time.
Right. The kernel guarantees that btf_str_by_offsetnever returns NULL, and there is no NULL check performed on the name returned by btf_find_by_name_kind. The NULL check is included in the libbpf version of the function.
Quoted 2 lines
[...]
Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
Quoted 19 lines · Donglin Peng
Quoted 17 lines · Eduard Zingerman
On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
[...]
Quoted 4 lines
Additionally, in the linear search branch, I saw there is a NULL check for the name returned by
btf__name_by_offset. This suggests that checkingname_off== 0 alone may not be sufficient to identify an anonymous type, which is why I usedstr_is_emptyfor a more robust check.
btf_str_by_offset(btf, offset)returns NULL only when 'offset' is larger then 'btf->hdr.str_len'. However, functionbtf_check_meta()verifies that this shall not happen by invokingbtf_name_offset_valid()check. Thebtf_check_meta()is invoked for all types bybtf_check_all_metas()called frombtf_parse_base(),btf_parse_module()andbtf_parse_type_sec()->btf_parse().
Quoted 7 lines
Quoted 2 lines
So, it appears that kernel protects itself from invalid
name_offvalues at BTF load time.Right. The kernel guarantees that
btf_str_by_offsetneverreturns NULL, and there is no NULL check performed on the name returned bybtf_find_by_name_kind. The NULL check is included in the libbpf version of the function.
Sorry — my mistake. There’s no NULL check on the name from btf_str_by_offset in the kernel’s btf_find_by_name_kind. The libbpf version has it.
Quoted 3 lines
Quoted 3 lines
[...]
Eduard Zingerman
maintainerRe: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
Quoted 23 lines · Donglin Peng
Quoted 22 lines · Donglin Peng
Quoted 19 lines · Eduard Zingerman
On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
[...]
Quoted 4 lines
Additionally, in the linear search branch, I saw there is a NULL check for the name returned by
btf__name_by_offset. This suggests that checkingname_off== 0 alone may not be sufficient to identify an anonymous type, which is why I usedstr_is_emptyfor a more robust check.
btf_str_by_offset(btf, offset)returns NULL only when 'offset' is larger then 'btf->hdr.str_len'. However, functionbtf_check_meta()verifies that this shall not happen by invokingbtf_name_offset_valid()check. Thebtf_check_meta()is invoked for all types bybtf_check_all_metas()called frombtf_parse_base(),btf_parse_module()andbtf_parse_type_sec()->btf_parse().So, it appears that kernel protects itself from invalid
name_offvalues at BTF load time.
Quoted 8 lines
Quoted 4 lines
Right. The kernel guarantees that
btf_str_by_offsetneverreturns NULL, and there is no NULL check performed on the name returned bybtf_find_by_name_kind. The NULL check is included in the libbpf version of the function.Sorry — my mistake. There’s no NULL check on the name from
btf_str_by_offsetin the kernel’sbtf_find_by_name_kind. The libbpf version has it.
tools/lib/bpf/btf.c:btf_sanity_check() is called from btf_new(), it calls btf_validate_type(), which does btf_validate_str(). So, ignoring the NULL case on libbpf side should be safe as well.
[...]
Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization
Quoted 30 lines · Eduard Zingerman
Quoted 28 lines · Donglin Peng
Quoted 26 lines · Donglin Peng
Quoted 17 lines · Eduard Zingerman
On Thu, 2025-11-20 at 15:25 +0800, Donglin Peng wrote:
[...]
Quoted 4 lines
Additionally, in the linear search branch, I saw there is a NULL check for the name returned by
btf__name_by_offset. This suggests that checkingname_off== 0 alone may not be sufficient to identify an anonymous type, which is why I usedstr_is_emptyfor a more robust check.
btf_str_by_offset(btf, offset)returns NULL only when 'offset' is larger then 'btf->hdr.str_len'. However, functionbtf_check_meta()verifies that this shall not happen by invokingbtf_name_offset_valid()check. Thebtf_check_meta()is invoked for all types bybtf_check_all_metas()called frombtf_parse_base(),btf_parse_module()andbtf_parse_type_sec()->btf_parse().Quoted 2 lines
So, it appears that kernel protects itself from invalid
name_offvalues at BTF load time.Right. The kernel guarantees that
btf_str_by_offsetneverreturns NULL, and there is no NULL check performed on the name returned bybtf_find_by_name_kind. The NULL check is included in the libbpf version of the function.
Quoted 7 lines
Quoted 3 lines
Sorry — my mistake. There’s no NULL check on the name from
btf_str_by_offsetin the kernel’sbtf_find_by_name_kind. The libbpf version has it.tools/lib/bpf/btf.c:btf_sanity_check() is called from
btf_new(), it callsbtf_validate_type(), which doesbtf_validate_str(). So, ignoring the NULL case on libbpf side should be safe as well.
Thanks, I also noticed that too and will drop the NULL check in the next version.
Quoted 2 lines
[...]
RFC PATCH v7 6/7 btf: Optimize type lookup with binary search
In reply to Donglin PengFrom: Donglin Peng <[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 | 83 ++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 73 insertions(+), 10 deletions(-)
kernel/bpf/btf.c +73 -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,78 @@ u32 btf_nr_types(const struct btf *btf)return total; } +static s32 btf_find_by_name_kind_bsearch (const struct btf *btf,const char *name, +s32 start_id,s32 end_id) +{ +const struct btf_type *t; +const char *tname; +s32 l, r, m; + + l = start_id; + r = end_id; +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) >=0 ) { +if (l == r) +return r; + r = m; + }else { + l = m +1 ; + } + } + +return btf_nr_types (btf); +} +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; -u32 i, total; +int err = -ENOENT ; - 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 ; +if (base_btf) { + err =btf_find_by_name_kind (base_btf, name, kind); +if (err >0 ) + goto out; + } - tname =btf_name_by_offset (btf, t->name_off); -if (!strcmp (tname, name)) -return i; +if (btf->nr_sorted_types >0 ) { +/* binary search */ +s32 start_id, end_id; +u32 idx; + + start_id =btf_start_id (btf); + end_id = start_id + btf->nr_sorted_types -1 ; + idx =btf_find_by_name_kind_bsearch (btf, name, start_id, end_id); +for (; idx <= end_id; idx++) { + t =btf_type_by_id (btf, idx); + tname =btf_name_by_offset (btf, t->name_off); +if (strcmp (tname, name)) + goto out; +if (BTF_INFO_KIND (t->info) == kind) +return idx; + } + }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; + } } -return -ENOENT ; +out: +return err; }s32 bpf_find_btf_id (const char *name,u32 kind,struct btf **btf_p)
@@ -5791,6 +5851,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 =0 ; data =kvmalloc (attr->btf_size,GFP_KERNEL | __GFP_NOWARN);if (!data) {
@@ -6210,6 +6271,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 =0 ;snprintf (btf->name,sizeof (btf->name),"%s" , name); err =btf_parse_hdr (env);
@@ -6327,6 +6389,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 =0 ;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 v7 7/7 btf: Add sorting validation for binary search
In reply to Donglin PengFrom: Donglin Peng <[email protected]>
Implement validation of BTF type ordering to enable efficient binary search for sorted BTF.
--- kernel/bpf/btf.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 64 insertions(+)
kernel/bpf/btf.c +64 -0
@@ -550,6 +550,66 @@ u32 btf_nr_types(const struct btf *btf)return total; } +/* Anonymous types (with empty names) are considered greater than named types +* and are sorted after them. Two anonymous types are considered equal. Named +* types are compared lexicographically. +*/ +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 that BTF types are sorted in ascending order according to their +* names, with named types appearing before anonymous types. If the ordering +* is correct, counts the number of named types and updates the BTF object's +* nr_sorted_types field. Note that vmlinux and kernel module BTFs are sorted +* during the building phase, so the validation logic only needs to count the +* named types. +*/ +static void btf_check_sorted (struct btf *btf) +{ +const struct btf_type *t; +int i, n, k =0 , nr_sorted_types; +bool skip_cmp =btf_is_kernel (btf); + +if (btf->nr_types <2 ) +return ; + + nr_sorted_types =0 ; + n =btf_nr_types (btf) -1 ; +for (i =btf_start_id (btf); i < n; i++) { + k = i +1 ; +if (!skip_cmp &&btf_compare_type_names (&i, &k, btf) >0 ) +return ; + + t =btf_type_by_id (btf, i); +if (t->name_off) + nr_sorted_types++; +else if (skip_cmp) +break ; + } + + t =btf_type_by_id (btf, k); +if (t->name_off) + nr_sorted_types++; +if (nr_sorted_types) + btf->nr_sorted_types = nr_sorted_types; +} +static s32 btf_find_by_name_kind_bsearch (const struct btf *btf,const char *name,s32 start_id,s32 end_id) {
@@ -5885,6 +5945,8 @@ static struct btf *btf_parse(const union bpf_attr *attr, bpfptr_t uattr, u32 uatif (err) goto errout; +btf_check_sorted (btf); + struct_meta_tab =btf_parse_struct_metas (&env->log, btf);if (IS_ERR (struct_meta_tab)) { err =PTR_ERR (struct_meta_tab);
@@ -6292,6 +6354,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *nameif (err) goto errout; +btf_check_sorted (btf);refcount_set (&btf->refcnt,1 );return btf;
@@ -6426,6 +6489,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data, }btf_verifier_env_free (env); +btf_check_sorted (btf);refcount_set (&btf->refcnt,1 );return btf;
Signature · 1 line
2.34.1