Significantly Improve BTF Type Lookup Performance
Subsystems (4)
v3 cover Significantly Improve BTF Type Lookup Performance
The funcgraph-args feature frequently calls btf_find_by_name_kind(), which currently uses a linear search algorithm. With large BTF datasets like vmlinux
(containing over 80,000 named types), this causes significant performance overhead.
This patch series introduces a new libbpf interface btf__permute(), which allows tools like pahole to sort BTF types by kind and name. After generating a sorted type ID array, these tools can invoke the new interface to perform in-place BTF sorting. During BTF parsing, btf_check_sorted() verifies whether the types are sorted.
Performance testing shows dramatic improvement after sorting by kind and name, as demonstrated below:
# echo 1 > options/funcgraph-args # echo function_graph > current_tracer
Before:
# time cat trace | wc -l 58098
real 0m7.514s user 0m0.010s sys 0m7.374s
After:
# time cat trace | wc -l 58837
real 0m0.371s user 0m0.000s sys 0m0.383s
This represents about 20x performance improvement for BTF type lookups.
v2:
https://lore.kernel.org/all/[email protected]/
v2 -> v3:
- Remove sorting logic from libbpf and provide a generic btf__permute() interface
- Remove the search direction patch since sorted lookup provides sufficient performance and changing search order could cause conflicts between BTF and base BTF
- Include btf_sort.c directly in btf.c to reduce function call overhead
Donglin Peng (3):
btf: implement BTF type sorting for accelerated lookups selftests/bpf: add tests for BTF type permutation
btf: Reuse libbpf code for BTF type sorting verification and binary
search
kernel/bpf/btf.c | 34 +-- tools/lib/bpf/btf.c | 262 +++++++++++++++++-- tools/lib/bpf/btf.h | 17 ++ tools/lib/bpf/btf_sort.c | 174 ++++++++++++ tools/lib/bpf/btf_sort.h | 11 + tools/lib/bpf/libbpf.map | 6 + tools/lib/bpf/libbpf_version.h | 2 +- tools/testing/selftests/bpf/prog_tests/btf.c | 109 ++++++-- 8 files changed, 559 insertions(+), 56 deletions(-) create mode 100644 tools/lib/bpf/btf_sort.c create mode 100644 tools/lib/bpf/btf_sort.h
Signature · 1 line
2.34.1
RFC PATCH v3 1/3 btf: implement BTF type sorting for accelerated lookups
This patch introduces a new libbpf interface btf__permute() to reorganize BTF types according to a provided mapping. The BTF lookup mechanism is enhanced with binary search capability, significantly improving lookup performance for large type sets.
The pahole tool can invoke this interface with a sorted type ID array, enabling binary search in both user space and kernel. To share core logic between kernel and libbpf, common sorting functionality is implemented in a new btf_sort.c source file.
---v2->v3:
- Remove sorting logic from libbpf and provide a generic btf__permute() interface
- Remove the search direction patch since sorted lookup provides sufficient performance and changing search order could cause conflicts between BTF and base BTF
- Include btf_sort.c directly in btf.c to reduce function call overhead
--- tools/lib/bpf/btf.c | 262 ++++++++++++++++++++++++++++++--- tools/lib/bpf/btf.h | 17 +++ tools/lib/bpf/btf_sort.c | 174 ++++++++++++++++++++++ tools/lib/bpf/btf_sort.h | 11 ++ tools/lib/bpf/libbpf.map | 6 + tools/lib/bpf/libbpf_version.h | 2 +- 6 files changed, 447 insertions(+), 25 deletions(-) create mode 100644 tools/lib/bpf/btf_sort.c create mode 100644 tools/lib/bpf/btf_sort.h
tools/lib/bpf/btf.c +238 -24
@@ -23,6 +23,7 @@#include "libbpf_internal.h" #include "hashmap.h" #include "strset.h" +#include "btf_sort.h" #define BTF_MAX_NR_TYPES 0x7fffffffU#define BTF_MAX_STR_OFFSET 0x7fffffffU
@@ -92,6 +93,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 */
@@ -624,6 +631,11 @@ const struct btf *btf__base_btf(const struct btf *btf)return btf->base_btf; } +__u32 btf__start_id (const struct btf *btf) +{ +return btf->start_id; +} +/* internal helper returning non-const pointer to a type */ struct btf_type *btf_type_by_id (const struct btf *btf,__u32 type_id) {
@@ -915,38 +927,16 @@ __s32 btf__find_by_name(const struct btf *btf, const char *type_name)return libbpf_err (-ENOENT ); } -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 (-ENOENT ); -} -__s32 btf__find_by_name_kind_own (const struct btf *btf,const char *type_name,__u32 kind) { -return btf_find_by_name_kind (btf, btf->start_id, type_name, kind); +return _btf_find_by_name_kind (btf, btf->start_id, type_name, kind); }__s32 btf__find_by_name_kind (const struct btf *btf,const char *type_name,__u32 kind) { -return btf_find_by_name_kind (btf,1 , type_name, kind); +return _btf_find_by_name_kind (btf,1 , type_name, kind); }static bool btf_is_modifiable (const struct btf *btf)
@@ -1091,6 +1081,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, btf->start_id); done:if (err) {
@@ -1715,6 +1706,8 @@ static void btf_invalidate_raw_data(struct btf *btf)free (btf->raw_data_swapped); btf->raw_data_swapped =NULL ; } +if (btf->nr_sorted_types) + btf->nr_sorted_types =0 ; }/* Ensure BTF is ready to be modified (by splitting into a three memory
@@ -5829,3 +5822,224 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false;return libbpf_err (err); } + +struct btf_permute ; + +static struct btf_permute *btf_permute_new (struct btf *btf,const struct btf_permute_opts *opts); +static void btf_permute_free (struct btf_permute *p); +static int btf_permute_shuffle_types (struct btf_permute *p); +static int btf_permute_remap_types (struct btf_permute *p); +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx); + +/* +* Permute BTF types in-place using the ID mapping from btf_permute_opts->ids. +* After permutation, all type ID references are updated to reflect the new +* ordering. If a struct btf_ext (representing '.BTF.ext' section) is provided, +* type ID references within the BTF extension data are also updated. +*/ +int btf__permute (struct btf *btf,const struct btf_permute_opts *opts) +{ +struct btf_permute *p; +int err =0 ; + +if (!OPTS_VALID (opts, btf_permute_opts)) +return libbpf_err (-EINVAL ); + + p =btf_permute_new (btf, opts); +if (!p) { +pr_debug ("btf_permute_new failed: %ld\n" ,PTR_ERR (p)); +return libbpf_err (-EINVAL ); + } + +if (btf_ensure_modifiable (btf)) { + err = -ENOMEM ; + goto done; + } + + err =btf_permute_shuffle_types (p); +if (err <0 ) { +pr_debug ("btf_permute_shuffle_types failed: %s\n" ,errstr (err)); + goto done; + } + err =btf_permute_remap_types (p); +if (err) { +pr_debug ("btf_permute_remap_types failed: %s\n" ,errstr (err)); + goto done; + } + +done: +btf_permute_free (p); +return libbpf_err (err); +} + +struct btf_permute { +/* .BTF section to be permuted in-place */ +struct btf *btf; +struct btf_ext *btf_ext; +/* Array of type IDs used for permutation. The array length must equal +* the number of types in the BTF being permuted, excluding the special +* void type at ID 0. For split BTF, the length corresponds to the +* number of types added on top of the base BTF. +*/ +__u32 *ids; +/* Array of type IDs used to map from original type ID to a new permuted +* type ID, its length equals to the above ids */ +__u32 *map; +}; + +static struct btf_permute *btf_permute_new (struct btf *btf,const struct btf_permute_opts *opts) +{ +struct btf_permute *p =calloc (1 ,sizeof (struct btf_permute )); +__u32 *map; +int err =0 ; + +if (!p) +return ERR_PTR (-ENOMEM ); + + p->btf = btf; + p->btf_ext =OPTS_GET (opts, btf_ext,NULL ); + p->ids =OPTS_GET (opts, ids,NULL ); +if (!p->ids) { + err = -EINVAL ; + goto done; + } + + map =calloc (btf->nr_types,sizeof (*map)); +if (!map) { + err = -ENOMEM ; + goto done; + } + p->map = map; + +done: +if (err) { +btf_permute_free (p); +return ERR_PTR (err); + } + +return p; +} + +static void btf_permute_free (struct btf_permute *p) +{ +if (p->map) { +free (p->map); + p->map =NULL ; + } +free (p); +} + +/* +* Shuffle BTF types. +* +* Rearranges types according to the permutation map in p->ids. The p->map +* array stores the mapping from original type IDs to new shuffled IDs, +* which is used in the next phase to update type references. +*/ +static int btf_permute_shuffle_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +const struct btf_type *t; +__u32 *new_offs =NULL ; +void *l, *new_types =NULL ; +int i, id, len, err; + + new_offs =calloc (btf->nr_types,sizeof (*new_offs)); + new_types =calloc (btf->hdr->type_len,1 ); +if (!new_types || !new_offs) { + err = -ENOMEM ; + goto out_err; + } + + l = new_types; +for (i =0 ; i < btf->nr_types; i++) { + id = p->ids[i]; + t =btf__type_by_id (btf, id); + len =btf_type_size (t); +memcpy (l, t, len); + new_offs[i] = l - new_types; + p->map[id - btf->start_id] = btf->start_id + i; + l += len; + } + +free (btf->types_data); +free (btf->type_offs); + btf->types_data = new_types; + btf->type_offs = new_offs; +return 0 ; + +out_err: +return err; +} + +/* +* Remap referenced type IDs into permuted type IDs. +* +* After BTF types are permuted, their final type IDs may differ from original +* ones. The map from original to a corresponding permuted type ID is stored +* in btf_permute->map and is populated during shuffle phase. During remapping +* phase we are rewriting all type IDs referenced from any BTF type (e.g., +* struct fields, func proto args, etc) to their final deduped type IDs. +*/ +static int btf_permute_remap_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +int i, r; + +for (i =0 ; i < btf->nr_types; i++) { +struct btf_type *t =btf_type_by_id (btf, btf->start_id + i); +struct btf_field_iter it; +__u32 *type_id; + + r =btf_field_iter_init (&it, t,BTF_FIELD_ITER_IDS ); +if (r) +return r; + +while ((type_id =btf_field_iter_next (&it))) { +__u32 new_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_id < btf->start_id) +continue ; + + new_id = p->map[new_id - btf->start_id]; +if (new_id >BTF_MAX_NR_TYPES ) +return -EINVAL ; + + *type_id = new_id; + } + } + +if (!p->btf_ext) +return 0 ; + + r =btf_ext_visit_type_ids (p->btf_ext, btf_permute_remap_type_id, p); +if (r) +return r; + +return 0 ; +} + +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; + + new_type_id = p->map[*type_id - p->btf->start_id]; +if (new_type_id >BTF_MAX_NR_TYPES ) +return -EINVAL ; + + *type_id = new_type_id; +return 0 ; +} + +/* +* btf_sort.c is included directly to avoid function call overhead +* when accessing BTF private data, as this file is shared between +* libbpf and kernel and may be called frequently. +*/ +#include "./btf_sort.c"
tools/lib/bpf/btf.h +17 -0
@@ -149,6 +149,7 @@ LIBBPF_API __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name, __u32 kind); LIBBPF_API __u32 btf__type_cnt(const struct btf *btf); LIBBPF_API const struct btf *btf__base_btf(const struct btf *btf); +LIBBPF_API __u32 btf__start_id(const struct btf *btf); LIBBPF_API const struct btf_type *btf__type_by_id(const struct btf *btf,__u32 id); LIBBPF_API size_t btf__pointer_size(const struct btf *btf);
@@ -273,6 +274,22 @@ 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; +/* Array of type IDs used for permutation. The array length must equal +* the number of types in the BTF being permuted, excluding the special +* void type at ID 0. For split BTF, the length corresponds to the +* number of types added on top of the base BTF. +*/ +__u32 *ids; + size_t :0; +}; +#define btf_permute_opts__last_field ids + +LIBBPF_API int btf__permute(struct btf *btf, const struct btf_permute_opts *opts); +struct btf_dump ;struct btf_dump_opts {
tools/lib/bpf/btf_sort.c new file +174 -0
174 lines not on this page · raw message
tools/lib/bpf/btf_sort.h new file +11 -0
@@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) */ +/* Copyright (c) 2025 Xiaomi */ + +#ifndef __BTF_SORT_H +#define __BTF_SORT_H + +static __s32 _btf_find_by_name_kind (const struct btf *btf,int start_id,const char *type_name,__u32 kind); +static int btf_compare_type_kinds_names (const void *a,const void *b,void *priv); +static void btf_check_sorted (struct btf *btf,int start_id); + +#endif
tools/lib/bpf/libbpf.map +6 -0
@@ -452,3 +452,9 @@ LIBBPF_1.7.0 { bpf_map__set_exclusive_program; bpf_map__exclusive_program; } LIBBPF_1.6.0; + +LIBBPF_1.8.0 { + global: + btf__start_id; + btf__permute; +} LIBBPF_1.7.0;
tools/lib/bpf/libbpf_version.h +1 -1
@@ -4,6 +4,6 @@#define __LIBBPF_VERSION_H#define LIBBPF_MAJOR_VERSION 1 -#define LIBBPF_MINOR_VERSION 7 +#define LIBBPF_MINOR_VERSION 8#endif /* __LIBBPF_VERSION_H */
Signature · 1 line
2.34.1
[email protected]
AI reviewRe: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
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
``` commit 1fada9fa20ae7a48b4ba2dd189d4d2dd29878ad2 Author: Donglin Peng <[email protected]> btf: implement BTF type sorting for accelerated lookups This patch introduces a new libbpf interface btf__permute() to reorganize BTF types according to a provided mapping, with binary search capability for accelerated lookups in large type sets. > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c > index 18907f0fc..d20bf81a2 100644 > --- a/tools/lib/bpf/btf.c > +++ b/tools/lib/bpf/btf.c [ ... ] > +/* > + * Shuffle BTF types. > + * > + * Rearranges types according to the permutation map in p->ids. The p->map > + * array stores the mapping from original type IDs to new shuffled IDs, > + * which is used in the next phase to update type references. > + */ > +static int btf_permute_shuffle_types(struct btf_permute *p) > +{ > + struct btf *btf = p->btf; > + const struct btf_type *t; > + __u32 *new_offs = NULL; > + void *l, *new_types = NULL; > + int i, id, len, err; > + > + new_offs = calloc(btf->nr_types, sizeof(*new_offs)); > + new_types = calloc(btf->hdr->type_len, 1); > + if (!new_types || !new_offs) { > + err = -ENOMEM; > + goto out_err; > + } Can btf_permute_shuffle_types() leak new_offs? If the first calloc() succeeds but the second fails, the function jumps to out_err which returns without freeing new_offs. > + > + l = new_types; > + for (i = 0; i < btf->nr_types; i++) { > + id = p->ids[i]; > + t = btf__type_by_id(btf, id); Can invalid type IDs from p->ids[] crash btf__type_by_id()? The ids array comes from user input via btf__permute() opts, but there's no validation that the IDs are within the valid range before passing them to btf__type_by_id(). If a user provides an out-of-range type ID, this could access invalid memory. > + len = btf_type_size(t); > + memcpy(l, t, len); > + new_offs[i] = l - new_types; > + p->map[id - btf->start_id] = btf->start_id + i; > + l += len; > + } > + > + free(btf->types_data); > + free(btf->type_offs); > + btf->types_data = new_types; > + btf->type_offs = new_offs; > + return 0; > + > +out_err: > + return err; > +} [ ... ] ```
---
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
In-Reply-To-Subject: btf: implement BTF type sorting for accelerated lookups CI run summary: https://github.com/kernel-patches/bpf/actions/runs/18843706931
Eduard Zingerman
maintainerRe: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
In reply to Donglin PengQuoted 18 lines · Donglin Peng
This patch introduces a new libbpf interface
btf__permute()to reorganize BTF types according to a provided mapping. The BTF lookup mechanism is enhanced with binary search capability, significantly improving lookup performance for large type sets.The pahole tool can invoke this interface with a sorted type ID array, enabling binary search in both user space and kernel. To share core logic between kernel and libbpf, common sorting functionality is implemented in a new
btf_sort.csource file.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]>Co-developed-by Eduard Zingerman <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>
Quoted 7 lines
---
v2->v3:
- Remove sorting logic from libbpf and provide a genericbtf__permute()interface
- Remove the search direction patch since sorted lookup provides sufficient performance and changing search order could cause conflicts between BTF and base BTF
- Includebtf_sort.cdirectly inbtf.cto reduce function call overhead
---
Could you please split this in two commits:
- one handling BTF sortedness
- another handling btf__permute()
?
Quoted 117 lines
tools/lib/bpf/btf.c | 262 ++++++++++++++++++++++++++++++--- tools/lib/bpf/btf.h | 17 +++ tools/lib/bpf/btf_sort.c | 174 ++++++++++++++++++++++ tools/lib/bpf/btf_sort.h | 11 ++ tools/lib/bpf/libbpf.map | 6 + tools/lib/bpf/libbpf_version.h | 2 +- 6 files changed, 447 insertions(+), 25 deletions(-) create mode 100644 tools/lib/bpf/btf_sort.c create mode 100644 tools/lib/bpf/btf_sort.htools/lib/bpf/btf.c +25
-24@@ -23,6 +23,7 @@#include "libbpf_internal.h" #include "hashmap.h" #include "strset.h" +#include "btf_sort.h" #define BTF_MAX_NR_TYPES 0x7fffffffU#define BTF_MAX_STR_OFFSET 0x7fffffffU@@ -92,6 +93,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 */ @@ -624,6 +631,11 @@ const struct btf *btf__base_btf(const struct btf *btf)return btf->base_btf; } +__u32 btf__start_id (const struct btf *btf) +{ +return btf->start_id; +} +/* internal helper returning non-const pointer to a type */ struct btf_type *btf_type_by_id (const struct btf *btf,__u32 type_id) {@@ -915,38 +927,16 @@ __s32 btf__find_by_name(const struct btf *btf, const char *type_name)return libbpf_err (-ENOENT ); } -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 (-ENOENT ); -} -__s32 btf__find_by_name_kind_own (const struct btf *btf,const char *type_name,__u32 kind) { -return btf_find_by_name_kind (btf, btf->start_id, type_name, kind); +return _btf_find_by_name_kind (btf, btf->start_id, type_name, kind); }__s32 btf__find_by_name_kind (const struct btf *btf,const char *type_name,__u32 kind) { -return btf_find_by_name_kind (btf,1 , type_name, kind); +return _btf_find_by_name_kind (btf,1 , type_name, kind); }static bool btf_is_modifiable (const struct btf *btf)@@ -1091,6 +1081,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, btf->start_id); done:if (err) {@@ -1715,6 +1706,8 @@ static void btf_invalidate_raw_data(struct btf *btf)free (btf->raw_data_swapped); btf->raw_data_swapped =NULL ; } +if (btf->nr_sorted_types) + btf->nr_sorted_types =0 ; }/* Ensure BTF is ready to be modified (by splitting into a three memory @@ -5829,3 +5822,224 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false;return libbpf_err (err); } + +struct btf_permute ; + +static struct btf_permute *btf_permute_new (struct btf *btf,const struct btf_permute_opts *opts); +static void btf_permute_free (struct btf_permute *p); +static int btf_permute_shuffle_types (struct btf_permute *p); +static int btf_permute_remap_types (struct btf_permute *p); +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx);
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5842
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ +/* +* Permute BTF types in-place using the ID mapping from btf_permute_opts->ids. +* After permutation, all type ID references are updated to reflect the new +* ordering. If a struct btf_ext (representing '.BTF.ext' section) is provided, +* type ID references within the BTF extension data are also updated. +*/ +int btf__permute (struct btf *btf,const struct btf_permute_opts *opts) +{ +struct btf_permute *p;
Maybe allocate this on stack?
(Or just use btf_permute_opts directly and have 'map' as local variable?).
Quoted 146 lines
tools/lib/bpf/btf.c +146
-0+int err =0 ; + +if (!OPTS_VALID (opts, btf_permute_opts)) +return libbpf_err (-EINVAL ); + + p =btf_permute_new (btf, opts); +if (!p) { +pr_debug ("btf_permute_new failed: %ld\n" ,PTR_ERR (p)); +return libbpf_err (-EINVAL ); + } + +if (btf_ensure_modifiable (btf)) { + err = -ENOMEM ; + goto done; + } + + err =btf_permute_shuffle_types (p); +if (err <0 ) { +pr_debug ("btf_permute_shuffle_types failed: %s\n" ,errstr (err)); + goto done; + } + err =btf_permute_remap_types (p); +if (err) { +pr_debug ("btf_permute_remap_types failed: %s\n" ,errstr (err)); + goto done; + } + +done: +btf_permute_free (p); +return libbpf_err (err); +} + +struct btf_permute { +/* .BTF section to be permuted in-place */ +struct btf *btf; +struct btf_ext *btf_ext; +/* Array of type IDs used for permutation. The array length must equal +* the number of types in the BTF being permuted, excluding the special +* void type at ID 0. For split BTF, the length corresponds to the +* number of types added on top of the base BTF. +*/ +__u32 *ids; +/* Array of type IDs used to map from original type ID to a new permuted +* type ID, its length equals to the above ids */ +__u32 *map; +}; + +static struct btf_permute *btf_permute_new (struct btf *btf,const struct btf_permute_opts *opts) +{ +struct btf_permute *p =calloc (1 ,sizeof (struct btf_permute )); +__u32 *map; +int err =0 ; + +if (!p) +return ERR_PTR (-ENOMEM ); + + p->btf = btf; + p->btf_ext =OPTS_GET (opts, btf_ext,NULL ); + p->ids =OPTS_GET (opts, ids,NULL ); +if (!p->ids) { + err = -EINVAL ; + goto done; + } + + map =calloc (btf->nr_types,sizeof (*map)); +if (!map) { + err = -ENOMEM ; + goto done; + } + p->map = map; + +done: +if (err) { +btf_permute_free (p); +return ERR_PTR (err); + } + +return p; +} + +static void btf_permute_free (struct btf_permute *p) +{ +if (p->map) { +free (p->map); + p->map =NULL ; + } +free (p); +} + +/* +* Shuffle BTF types. +* +* Rearranges types according to the permutation map in p->ids. The p->map +* array stores the mapping from original type IDs to new shuffled IDs, +* which is used in the next phase to update type references. +*/ +static int btf_permute_shuffle_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +const struct btf_type *t; +__u32 *new_offs =NULL ; +void *l, *new_types =NULL ; +int i, id, len, err; + + new_offs =calloc (btf->nr_types,sizeof (*new_offs)); + new_types =calloc (btf->hdr->type_len,1 ); +if (!new_types || !new_offs) { + err = -ENOMEM ; + goto out_err; + } + + l = new_types; +for (i =0 ; i < btf->nr_types; i++) { + id = p->ids[i]; + t =btf__type_by_id (btf, id); + len =btf_type_size (t); +memcpy (l, t, len); + new_offs[i] = l - new_types; + p->map[id - btf->start_id] = btf->start_id + i; + l += len; + } + +free (btf->types_data); +free (btf->type_offs); + btf->types_data = new_types; + btf->type_offs = new_offs; +return 0 ; + +out_err: +return err; +} + +/* +* Remap referenced type IDs into permuted type IDs. +* +* After BTF types are permuted, their final type IDs may differ from original +* ones. The map from original to a corresponding permuted type ID is stored +* in btf_permute->map and is populated during shuffle phase. During remapping +* phase we are rewriting all type IDs referenced from any BTF type (e.g., +* struct fields, func proto args, etc) to their final deduped type IDs. +*/ +static int btf_permute_remap_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +int i, r; +
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5998
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+for (i =0 ; i < btf->nr_types; i++) { +struct btf_type *t =btf_type_by_id (btf, btf->start_id + i); +struct btf_field_iter it; +__u32 *type_id; + + r =btf_field_iter_init (&it, t,BTF_FIELD_ITER_IDS ); +if (r) +return r; + +while ((type_id =btf_field_iter_next (&it))) {
The code below repeats logic it btf_permute_remap_type_id(), please use it here. Better yet, generalize btf_dedup_remap_types() and avoid a copy-paste altogether.
Quoted 284 lines
tools/lib/bpf/btf.c +47
-0+__u32 new_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_id < btf->start_id) +continue ; + + new_id = p->map[new_id - btf->start_id]; +if (new_id >BTF_MAX_NR_TYPES ) +return -EINVAL ; + + *type_id = new_id; + } + } + +if (!p->btf_ext) +return 0 ; + + r =btf_ext_visit_type_ids (p->btf_ext, btf_permute_remap_type_id, p); +if (r) +return r; + +return 0 ; +} + +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; + + new_type_id = p->map[*type_id - p->btf->start_id]; +if (new_type_id >BTF_MAX_NR_TYPES ) +return -EINVAL ; + + *type_id = new_type_id; +return 0 ; +} + +/* +* btf_sort.c is included directly to avoid function call overhead +* when accessing BTF private data, as this file is shared between +* libbpf and kernel and may be called frequently. +*/ +#include "./btf_sort.c" tools/lib/bpf/btf.h +17
-0@@ -149,6 +149,7 @@ LIBBPF_API __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name, __u32 kind); LIBBPF_API __u32 btf__type_cnt(const struct btf *btf); LIBBPF_API const struct btf *btf__base_btf(const struct btf *btf); +LIBBPF_API __u32 btf__start_id(const struct btf *btf); LIBBPF_API const struct btf_type *btf__type_by_id(const struct btf *btf,__u32 id); LIBBPF_API size_t btf__pointer_size(const struct btf *btf);@@ -273,6 +274,22 @@ 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; +/* Array of type IDs used for permutation. The array length must equal +* the number of types in the BTF being permuted, excluding the special +* void type at ID 0. For split BTF, the length corresponds to the +* number of types added on top of the base BTF. +*/ +__u32 *ids; + size_t :0; +}; +#define btf_permute_opts__last_field ids + +LIBBPF_API int btf__permute(struct btf *btf, const struct btf_permute_opts *opts); +struct btf_dump ;struct btf_dump_opts {tools/lib/bpf/btf_sort.c new file +174
-0@@ -0,0 +1,174 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) +/* Copyright (c) 2025 Xiaomi */ + +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif + +#ifdef __KERNEL__ + +#define btf_type_by_id (struct btf_type *)btf_type_by_id +#define btf__str_by_offset btf_str_by_offset +#define btf__type_cnt btf_nr_types +#define btf__start_id btf_start_id +#define libbpf_err (x) x + +#else + +#define notrace + +#endif /* __KERNEL__ */ + +/* +* Skip the sorted check if the number of BTF types is below this threshold. +* The value 4 is chosen based on the theoretical break-even point where +* linear search (N/2) and binary search (LOG2(N)) require approximately +* the same number of comparisons. +*/ +#define BTF_CHECK_SORT_THRESHOLD 4 + +struct btf ; + +static int cmp_btf_kind_name (int ka,const char *na,int kb,const char *nb) +{ +return (ka - kb) ?:strcmp (na, nb); +} + +/* +* Sort BTF types by kind and name in ascending order, placing named types +* before anonymous ones. +*/ +static int btf_compare_type_kinds_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; +int ka, kb; + + 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); + +/* ta w/o name is greater than tb */ +if (anon_a && !anon_b) +return 1 ; +/* tb w/o name is smaller than ta */ +if (!anon_a && anon_b) +return -1 ; + + ka =btf_kind (ta); + kb =btf_kind (tb); + +if (anon_a && anon_b) +return ka - kb; + +return cmp_btf_kind_name (ka, na, kb, nb); +} + +static __s32 notrace __btf_find_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 (!btf) + goto out; + +if (start_id <btf__start_id (btf)) { + err =__btf_find_by_name_kind (btf->base_btf, start_id, type_name, kind); +if (err == -ENOENT ) + start_id =btf__start_id (btf); + } + +if (err == -ENOENT ) { +if (btf->nr_sorted_types) { +/* binary search */ +__s32 start, end, mid, found =-1 ; +int ret; + + start = start_id; + end = start + btf->nr_sorted_types -1 ; +/* found the leftmost btf_type that matches */ +while (start <= end) { + mid = start + (end - start) /2 ; + t =btf_type_by_id (btf, mid); + tname =btf__str_by_offset (btf, t->name_off); + ret =cmp_btf_kind_name (BTF_INFO_KIND (t->info), tname, + kind, type_name); +if (ret <0 ) + start = mid +1 ; +else { +if (ret ==0 ) + found = mid; + end = mid -1 ; + } + } + +if (found !=-1 ) +return found; + }else { +/* linear search */ +__u32 i, total; + + total =btf__type_cnt (btf); +for (i = start_id; i < total; i++) { + t =btf_type_by_id (btf, i); +if (btf_kind (t) != kind) +continue ; + + tname =btf__str_by_offset (btf, t->name_off); +if (tname && !strcmp (tname, type_name)) +return i; + } + } + } + +out: +return err; +} + +/* start_id specifies the starting BTF to search */ +static __s32 notrace _btf_find_by_name_kind(const struct btf *btf, int start_id, +const char *type_name,__u32 kind) +{ +if (kind ==BTF_KIND_UNKN || !strcmp (type_name,"void" )) +return 0 ; + +return libbpf_err (__btf_find_by_name_kind (btf, start_id, type_name, kind)); +} + +static void btf_check_sorted (struct btf *btf,int start_id) +{ +const struct btf_type *t; +int i, n, nr_sorted_types; + + n =btf__type_cnt (btf); +if (btf->nr_types <BTF_CHECK_SORT_THRESHOLD ) +return ; + + n--; + nr_sorted_types =0 ; +for (i = start_id; i < n; i++) { +int k = i +1 ; + +if (btf_compare_type_kinds_names (&i, &k, btf) >0 ) +return ; + + t =btf_type_by_id (btf, k); +if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; + } + + t =btf_type_by_id (btf, start_id); +if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; + +if (nr_sorted_types <BTF_CHECK_SORT_THRESHOLD ) +return ; + + btf->nr_sorted_types = nr_sorted_types; +}tools/lib/bpf/btf_sort.h new file +11
-0@@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) */ +/* Copyright (c) 2025 Xiaomi */ + +#ifndef __BTF_SORT_H +#define __BTF_SORT_H + +static __s32 _btf_find_by_name_kind (const struct btf *btf,int start_id,const char *type_name,__u32 kind); +static int btf_compare_type_kinds_names (const void *a,const void *b,void *priv); +static void btf_check_sorted (struct btf *btf,int start_id); + +#endif tools/lib/bpf/libbpf.map +0
-0
tools/lib/bpf/libbpf.map LIBBPF_1.7.0 { · line 456
Quoted 5 lines
tools/lib/bpf/libbpf.map +2
-0@@ -452,3 +452,9 @@ LIBBPF_1.7.0 { bpf_map__set_exclusive_program; bpf_map__exclusive_program; } LIBBPF_1.6.0; + +LIBBPF_1.8.0 {
I think we are still at 1.7.
Quoted 16 lines
tools/lib/bpf/libbpf.map +4
-0+ global: + btf__start_id; + btf__permute; +} LIBBPF_1.7.0;tools/lib/bpf/libbpf_version.h +1
-1@@ -4,6 +4,6 @@#define __LIBBPF_VERSION_H#define LIBBPF_MAJOR_VERSION 1 -#define LIBBPF_MINOR_VERSION 7 +#define LIBBPF_MINOR_VERSION 8#endif /* __LIBBPF_VERSION_H */
Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
Quoted 29 lines · Eduard Zingerman
Quoted 18 lines · Donglin Peng
This patch introduces a new libbpf interface
btf__permute()to reorganize BTF types according to a provided mapping. The BTF lookup mechanism is enhanced with binary search capability, significantly improving lookup performance for large type sets.The pahole tool can invoke this interface with a sorted type ID array, enabling binary search in both user space and kernel. To share core logic between kernel and libbpf, common sorting functionality is implemented in a new
btf_sort.csource file.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]>Co-developed-by Eduard Zingerman <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>Quoted 7 lines
---
v2->v3:
- Remove sorting logic from libbpf and provide a genericbtf__permute()interface
- Remove the search direction patch since sorted lookup provides sufficient performance and changing search order could cause conflicts between BTF and base BTF
- Includebtf_sort.cdirectly inbtf.cto reduce function call overhead
---
Quoted 4 lines
Could you please split this in two commits:
- one handling BTF sortedness
- another handlingbtf__permute()
?
Thanks, I will split it in the next version.
Quoted 122 lines
Quoted 122 lines
tools/lib/bpf/btf.c | 262 ++++++++++++++++++++++++++++++--- tools/lib/bpf/btf.h | 17 +++ tools/lib/bpf/btf_sort.c | 174 ++++++++++++++++++++++ tools/lib/bpf/btf_sort.h | 11 ++ tools/lib/bpf/libbpf.map | 6 + tools/lib/bpf/libbpf_version.h | 2 +- 6 files changed, 447 insertions(+), 25 deletions(-) create mode 100644 tools/lib/bpf/btf_sort.c create mode 100644 tools/lib/bpf/btf_sort.htools/lib/bpf/btf.c +29
-24@@ -23,6 +23,7 @@#include "libbpf_internal.h" #include "hashmap.h" #include "strset.h" +#include "btf_sort.h" #define BTF_MAX_NR_TYPES 0x7fffffffU#define BTF_MAX_STR_OFFSET 0x7fffffffU@@ -92,6 +93,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 */ @@ -624,6 +631,11 @@ const struct btf *btf__base_btf(const struct btf *btf)return btf->base_btf; } +__u32 btf__start_id (const struct btf *btf) +{ +return btf->start_id; +} +/* internal helper returning non-const pointer to a type */ struct btf_type *btf_type_by_id (const struct btf *btf,__u32 type_id) {@@ -915,38 +927,16 @@ __s32 btf__find_by_name(const struct btf *btf, const char *type_name)return libbpf_err (-ENOENT ); } -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 (-ENOENT ); -} -__s32 btf__find_by_name_kind_own (const struct btf *btf,const char *type_name,__u32 kind) { -return btf_find_by_name_kind (btf, btf->start_id, type_name, kind); +return _btf_find_by_name_kind (btf, btf->start_id, type_name, kind); }__s32 btf__find_by_name_kind (const struct btf *btf,const char *type_name,__u32 kind) { -return btf_find_by_name_kind (btf,1 , type_name, kind); +return _btf_find_by_name_kind (btf,1 , type_name, kind); }static bool btf_is_modifiable (const struct btf *btf)@@ -1091,6 +1081,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, btf->start_id); done:if (err) {@@ -1715,6 +1706,8 @@ static void btf_invalidate_raw_data(struct btf *btf)free (btf->raw_data_swapped); btf->raw_data_swapped =NULL ; } +if (btf->nr_sorted_types) + btf->nr_sorted_types =0 ; }/* Ensure BTF is ready to be modified (by splitting into a three memory @@ -5829,3 +5822,224 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false;return libbpf_err (err); } + +struct btf_permute ; + +static struct btf_permute *btf_permute_new (struct btf *btf,const struct btf_permute_opts *opts); +static void btf_permute_free (struct btf_permute *p); +static int btf_permute_shuffle_types (struct btf_permute *p); +static int btf_permute_remap_types (struct btf_permute *p); +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx); + +/* +* Permute BTF types in-place using the ID mapping from btf_permute_opts->ids. +* After permutation, all type ID references are updated to reflect the new
Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5842
Quoted 6 lines
tools/lib/bpf/btf.c +6
-0+* ordering. If a struct btf_ext (representing '.BTF.ext' section) is provided, +* type ID references within the BTF extension data are also updated. +*/ +int btf__permute (struct btf *btf,const struct btf_permute_opts *opts) +{ +struct btf_permute *p;Maybe allocate this on stack?
Thanks, I will fix it in the next version.
Quoted 1 line
(Or just use
btf_permute_optsdirectly and have 'map' as local variable?).
Thanks. I think maintaining a separate struct btf_permute that combines both user options and internal state is preferable, as it follows the same pattern established by btf_dedup_remap_types.
Quoted 153 lines
Quoted 153 lines
tools/lib/bpf/btf.c +152
-0+int err =0 ; + +if (!OPTS_VALID (opts, btf_permute_opts)) +return libbpf_err (-EINVAL ); + + p =btf_permute_new (btf, opts); +if (!p) { +pr_debug ("btf_permute_new failed: %ld\n" ,PTR_ERR (p)); +return libbpf_err (-EINVAL ); + } + +if (btf_ensure_modifiable (btf)) { + err = -ENOMEM ; + goto done; + } + + err =btf_permute_shuffle_types (p); +if (err <0 ) { +pr_debug ("btf_permute_shuffle_types failed: %s\n" ,errstr (err)); + goto done; + } + err =btf_permute_remap_types (p); +if (err) { +pr_debug ("btf_permute_remap_types failed: %s\n" ,errstr (err)); + goto done; + } + +done: +btf_permute_free (p); +return libbpf_err (err); +} + +struct btf_permute { +/* .BTF section to be permuted in-place */ +struct btf *btf; +struct btf_ext *btf_ext; +/* Array of type IDs used for permutation. The array length must equal +* the number of types in the BTF being permuted, excluding the special +* void type at ID 0. For split BTF, the length corresponds to the +* number of types added on top of the base BTF. +*/ +__u32 *ids; +/* Array of type IDs used to map from original type ID to a new permuted +* type ID, its length equals to the above ids */ +__u32 *map; +}; + +static struct btf_permute *btf_permute_new (struct btf *btf,const struct btf_permute_opts *opts) +{ +struct btf_permute *p =calloc (1 ,sizeof (struct btf_permute )); +__u32 *map; +int err =0 ; + +if (!p) +return ERR_PTR (-ENOMEM ); + + p->btf = btf; + p->btf_ext =OPTS_GET (opts, btf_ext,NULL ); + p->ids =OPTS_GET (opts, ids,NULL ); +if (!p->ids) { + err = -EINVAL ; + goto done; + } + + map =calloc (btf->nr_types,sizeof (*map)); +if (!map) { + err = -ENOMEM ; + goto done; + } + p->map = map; + +done: +if (err) { +btf_permute_free (p); +return ERR_PTR (err); + } + +return p; +} + +static void btf_permute_free (struct btf_permute *p) +{ +if (p->map) { +free (p->map); + p->map =NULL ; + } +free (p); +} + +/* +* Shuffle BTF types. +* +* Rearranges types according to the permutation map in p->ids. The p->map +* array stores the mapping from original type IDs to new shuffled IDs, +* which is used in the next phase to update type references. +*/ +static int btf_permute_shuffle_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +const struct btf_type *t; +__u32 *new_offs =NULL ; +void *l, *new_types =NULL ; +int i, id, len, err; + + new_offs =calloc (btf->nr_types,sizeof (*new_offs)); + new_types =calloc (btf->hdr->type_len,1 ); +if (!new_types || !new_offs) { + err = -ENOMEM ; + goto out_err; + } + + l = new_types; +for (i =0 ; i < btf->nr_types; i++) { + id = p->ids[i]; + t =btf__type_by_id (btf, id); + len =btf_type_size (t); +memcpy (l, t, len); + new_offs[i] = l - new_types; + p->map[id - btf->start_id] = btf->start_id + i; + l += len; + } + +free (btf->types_data); +free (btf->type_offs); + btf->types_data = new_types; + btf->type_offs = new_offs; +return 0 ; + +out_err: +return err; +} + +/* +* Remap referenced type IDs into permuted type IDs. +* +* After BTF types are permuted, their final type IDs may differ from original +* ones. The map from original to a corresponding permuted type ID is stored +* in btf_permute->map and is populated during shuffle phase. During remapping +* phase we are rewriting all type IDs referenced from any BTF type (e.g., +* struct fields, func proto args, etc) to their final deduped type IDs. +*/ +static int btf_permute_remap_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +int i, r; + +for (i =0 ; i < btf->nr_types; i++) { +struct btf_type *t =btf_type_by_id (btf, btf->start_id + i); +struct btf_field_iter it; +__u32 *type_id; + + r =btf_field_iter_init (&it, t,BTF_FIELD_ITER_IDS );
Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5998
Quoted 4 lines
tools/lib/bpf/btf.c +4
-0+if (r) +return r; + +while ((type_id =btf_field_iter_next (&it))) {The code below repeats logic it
btf_permute_remap_type_id(), please use it here. Better yet, generalizebtf_dedup_remap_types()and avoid a copy-paste altogether.
Good catch, thanks. I will fix it in the next version.
Quoted 284 lines
Quoted 284 lines
tools/lib/bpf/btf.c +47
-0+__u32 new_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_id < btf->start_id) +continue ; + + new_id = p->map[new_id - btf->start_id]; +if (new_id >BTF_MAX_NR_TYPES ) +return -EINVAL ; + + *type_id = new_id; + } + } + +if (!p->btf_ext) +return 0 ; + + r =btf_ext_visit_type_ids (p->btf_ext, btf_permute_remap_type_id, p); +if (r) +return r; + +return 0 ; +} + +static int btf_permute_remap_type_id (__u32 *type_id,void *ctx) +{ +struct btf_permute *p = ctx; +__u32 new_type_id = *type_id; + +/* skip references that point into the base BTF */ +if (new_type_id < p->btf->start_id) +return 0 ; + + new_type_id = p->map[*type_id - p->btf->start_id]; +if (new_type_id >BTF_MAX_NR_TYPES ) +return -EINVAL ; + + *type_id = new_type_id; +return 0 ; +} + +/* +* btf_sort.c is included directly to avoid function call overhead +* when accessing BTF private data, as this file is shared between +* libbpf and kernel and may be called frequently. +*/ +#include "./btf_sort.c" tools/lib/bpf/btf.h +17
-0@@ -149,6 +149,7 @@ LIBBPF_API __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name, __u32 kind); LIBBPF_API __u32 btf__type_cnt(const struct btf *btf); LIBBPF_API const struct btf *btf__base_btf(const struct btf *btf); +LIBBPF_API __u32 btf__start_id(const struct btf *btf); LIBBPF_API const struct btf_type *btf__type_by_id(const struct btf *btf,__u32 id); LIBBPF_API size_t btf__pointer_size(const struct btf *btf);@@ -273,6 +274,22 @@ 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; +/* Array of type IDs used for permutation. The array length must equal +* the number of types in the BTF being permuted, excluding the special +* void type at ID 0. For split BTF, the length corresponds to the +* number of types added on top of the base BTF. +*/ +__u32 *ids; + size_t :0; +}; +#define btf_permute_opts__last_field ids + +LIBBPF_API int btf__permute(struct btf *btf, const struct btf_permute_opts *opts); +struct btf_dump ;struct btf_dump_opts {tools/lib/bpf/btf_sort.c new file +174
-0@@ -0,0 +1,174 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) +/* Copyright (c) 2025 Xiaomi */ + +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif + +#ifdef __KERNEL__ + +#define btf_type_by_id (struct btf_type *)btf_type_by_id +#define btf__str_by_offset btf_str_by_offset +#define btf__type_cnt btf_nr_types +#define btf__start_id btf_start_id +#define libbpf_err (x) x + +#else + +#define notrace + +#endif /* __KERNEL__ */ + +/* +* Skip the sorted check if the number of BTF types is below this threshold. +* The value 4 is chosen based on the theoretical break-even point where +* linear search (N/2) and binary search (LOG2(N)) require approximately +* the same number of comparisons. +*/ +#define BTF_CHECK_SORT_THRESHOLD 4 + +struct btf ; + +static int cmp_btf_kind_name (int ka,const char *na,int kb,const char *nb) +{ +return (ka - kb) ?:strcmp (na, nb); +} + +/* +* Sort BTF types by kind and name in ascending order, placing named types +* before anonymous ones. +*/ +static int btf_compare_type_kinds_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; +int ka, kb; + + 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); + +/* ta w/o name is greater than tb */ +if (anon_a && !anon_b) +return 1 ; +/* tb w/o name is smaller than ta */ +if (!anon_a && anon_b) +return -1 ; + + ka =btf_kind (ta); + kb =btf_kind (tb); + +if (anon_a && anon_b) +return ka - kb; + +return cmp_btf_kind_name (ka, na, kb, nb); +} + +static __s32 notrace __btf_find_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 (!btf) + goto out; + +if (start_id <btf__start_id (btf)) { + err =__btf_find_by_name_kind (btf->base_btf, start_id, type_name, kind); +if (err == -ENOENT ) + start_id =btf__start_id (btf); + } + +if (err == -ENOENT ) { +if (btf->nr_sorted_types) { +/* binary search */ +__s32 start, end, mid, found =-1 ; +int ret; + + start = start_id; + end = start + btf->nr_sorted_types -1 ; +/* found the leftmost btf_type that matches */ +while (start <= end) { + mid = start + (end - start) /2 ; + t =btf_type_by_id (btf, mid); + tname =btf__str_by_offset (btf, t->name_off); + ret =cmp_btf_kind_name (BTF_INFO_KIND (t->info), tname, + kind, type_name); +if (ret <0 ) + start = mid +1 ; +else { +if (ret ==0 ) + found = mid; + end = mid -1 ; + } + } + +if (found !=-1 ) +return found; + }else { +/* linear search */ +__u32 i, total; + + total =btf__type_cnt (btf); +for (i = start_id; i < total; i++) { + t =btf_type_by_id (btf, i); +if (btf_kind (t) != kind) +continue ; + + tname =btf__str_by_offset (btf, t->name_off); +if (tname && !strcmp (tname, type_name)) +return i; + } + } + } + +out: +return err; +} + +/* start_id specifies the starting BTF to search */ +static __s32 notrace _btf_find_by_name_kind(const struct btf *btf, int start_id, +const char *type_name,__u32 kind) +{ +if (kind ==BTF_KIND_UNKN || !strcmp (type_name,"void" )) +return 0 ; + +return libbpf_err (__btf_find_by_name_kind (btf, start_id, type_name, kind)); +} + +static void btf_check_sorted (struct btf *btf,int start_id) +{ +const struct btf_type *t; +int i, n, nr_sorted_types; + + n =btf__type_cnt (btf); +if (btf->nr_types <BTF_CHECK_SORT_THRESHOLD ) +return ; + + n--; + nr_sorted_types =0 ; +for (i = start_id; i < n; i++) { +int k = i +1 ; + +if (btf_compare_type_kinds_names (&i, &k, btf) >0 ) +return ; + + t =btf_type_by_id (btf, k); +if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; + } + + t =btf_type_by_id (btf, start_id); +if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; + +if (nr_sorted_types <BTF_CHECK_SORT_THRESHOLD ) +return ; + + btf->nr_sorted_types = nr_sorted_types; +}tools/lib/bpf/btf_sort.h new file +11
-0@@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) */ +/* Copyright (c) 2025 Xiaomi */ + +#ifndef __BTF_SORT_H +#define __BTF_SORT_H + +static __s32 _btf_find_by_name_kind (const struct btf *btf,int start_id,const char *type_name,__u32 kind); +static int btf_compare_type_kinds_names (const void *a,const void *b,void *priv); +static void btf_check_sorted (struct btf *btf,int start_id); + +#endif tools/lib/bpf/libbpf.map +0
-0
Quoted 8 lines
tools/lib/bpf/libbpf.map LIBBPF_1.7.0 { · line 456
Quoted 6 lines
tools/lib/bpf/libbpf.map +2
-0@@ -452,3 +452,9 @@ LIBBPF_1.7.0 { bpf_map__set_exclusive_program; bpf_map__exclusive_program; } LIBBPF_1.6.0; + +LIBBPF_1.8.0 {I think we are still at 1.7.
Thanks, I will fix it in the next version.
Quoted 17 lines
Quoted 17 lines
tools/lib/bpf/libbpf.map +4
-0+ global: + btf__start_id; + btf__permute; +} LIBBPF_1.7.0;tools/lib/bpf/libbpf_version.h +1
-1@@ -4,6 +4,6 @@#define __LIBBPF_VERSION_H#define LIBBPF_MAJOR_VERSION 1 -#define LIBBPF_MINOR_VERSION 7 +#define LIBBPF_MINOR_VERSION 8#endif /* __LIBBPF_VERSION_H */
Eduard Zingerman
maintainerRe: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
In reply to Donglin PengOn Mon, 2025-10-27 at 21:54 +0800, Donglin Peng wrote:
[...]
Question to Andrii, I think.
It looks a bit asymmetrical, that there is btf_check_sorted() in libbpf, but library does not provide comparison or sorting function. Wdyt?
Quoted 18 lines
tools/lib/bpf/btf_sort.c new file +18
-0+static void btf_check_sorted (struct btf *btf,int start_id) +{ +const struct btf_type *t; +int i, n, nr_sorted_types; + + n =btf__type_cnt (btf); +if (btf->nr_types <BTF_CHECK_SORT_THRESHOLD ) +return ; + + n--; + nr_sorted_types =0 ; +for (i = start_id; i < n; i++) { +int k = i +1 ; + +if (btf_compare_type_kinds_names (&i, &k, btf) >0 ) +return ; + + t =btf_type_by_id (btf, k);
tools/lib/bpf/btf_sort.c line 171
Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10
-0+if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; + } + + t =btf_type_by_id (btf, start_id); +if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; + +if (nr_sorted_types <BTF_CHECK_SORT_THRESHOLD ) +return ;
Nit: Still think that this is not needed. It trades a couple of CPU
cycles for this check and a big comment on the top, about why it's needed.
Quoted 3 lines
tools/lib/bpf/btf_sort.c new file +3
-0+ + btf->nr_sorted_types = nr_sorted_types; +}
[...]
Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
Quoted 34 lines · Eduard Zingerman
On Mon, 2025-10-27 at 21:54 +0800, Donglin Peng wrote:
[...]
Question to Andrii, I think.
It looks a bit asymmetrical, that there isbtf_check_sorted()in libbpf, but library does not provide comparison or sorting function. Wdyt?Quoted 24 lines
tools/lib/bpf/btf_sort.c new file +24
-0+static void btf_check_sorted (struct btf *btf,int start_id) +{ +const struct btf_type *t; +int i, n, nr_sorted_types; + + n =btf__type_cnt (btf); +if (btf->nr_types <BTF_CHECK_SORT_THRESHOLD ) +return ; + + n--; + nr_sorted_types =0 ; +for (i = start_id; i < n; i++) { +int k = i +1 ; + +if (btf_compare_type_kinds_names (&i, &k, btf) >0 ) +return ; + + t =btf_type_by_id (btf, k); +if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; + } + + t =btf_type_by_id (btf, start_id); +if (!str_is_empty (btf__str_by_offset (btf, t->name_off)))
Quoted 8 lines
tools/lib/bpf/btf_sort.c line 171
Quoted 4 lines
tools/lib/bpf/btf_sort.c new file +4
-0+ nr_sorted_types++; + +if (nr_sorted_types <BTF_CHECK_SORT_THRESHOLD ) +return ;Nit: Still think that this is not needed. It trades a couple of CPU
cycles for this check and a big comment on the top, about why it's needed.
Thanks, I will remove it in the next version.
Quoted 6 lines
Quoted 4 lines
tools/lib/bpf/btf_sort.c new file +3
-0+ + btf->nr_sorted_types = nr_sorted_types; +}[...]
Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
In reply to Eduard ZingermanQuoted 9 lines · Eduard Zingerman
On Mon, 2025-10-27 at 21:54 +0800, Donglin Peng wrote:
[...]
Question to Andrii, I think.
It looks a bit asymmetrical, that there isbtf_check_sorted()in libbpf, but library does not provide comparison or sorting function. Wdyt?
I feel like it's fine. libbpf will opportunistically use sorted-by-name property (because it checks that), but it doesn't dictate exact sorting rules within groups of types with the same name. I don't want to get into that business. So no, I don't think it's bad. If names form alphabetic order -- great, take advantage. If not, great as well, linear search (or if we want in the future, create our own sorted index on top).
Quoted 39 lines
Quoted 19 lines
tools/lib/bpf/btf_sort.c new file +18
-0+static void btf_check_sorted (struct btf *btf,int start_id) +{ +const struct btf_type *t; +int i, n, nr_sorted_types; + + n =btf__type_cnt (btf); +if (btf->nr_types <BTF_CHECK_SORT_THRESHOLD ) +return ; + + n--; + nr_sorted_types =0 ; +for (i = start_id; i < n; i++) { +int k = i +1 ; + +if (btf_compare_type_kinds_names (&i, &k, btf) >0 ) +return ; + + t =btf_type_by_id (btf, k);tools/lib/bpf/btf_sort.c line 171
Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10
-0+if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; + } + + t =btf_type_by_id (btf, start_id); +if (!str_is_empty (btf__str_by_offset (btf, t->name_off))) + nr_sorted_types++; + +if (nr_sorted_types <BTF_CHECK_SORT_THRESHOLD ) +return ;Nit: Still think that this is not needed. It trades a couple of CPU
cycles for this check and a big comment on the top, about why it's needed.Quoted 3 lines
tools/lib/bpf/btf_sort.c new file +3
-0+ + btf->nr_sorted_types = nr_sorted_types; +}[...]
Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
In reply to Donglin PengQuoted 25 lines · Donglin Peng
This patch introduces a new libbpf interface
btf__permute()to reorganize BTF types according to a provided mapping. The BTF lookup mechanism is enhanced with binary search capability, significantly improving lookup performance for large type sets.The pahole tool can invoke this interface with a sorted type ID array, enabling binary search in both user space and kernel. To share core logic between kernel and libbpf, common sorting functionality is implemented in a new
btf_sort.csource file.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]>Co-developed-by Eduard Zingerman <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>---
v2->v3:
- Remove sorting logic from libbpf and provide a genericbtf__permute()interface
- Remove the search direction patch since sorted lookup provides sufficient performance and changing search order could cause conflicts between BTF and base BTF
- Includebtf_sort.cdirectly inbtf.cto reduce function call overhead
Quoted 11 lines
--- tools/lib/bpf/btf.c | 262 ++++++++++++++++++++++++++++++--- tools/lib/bpf/btf.h | 17 +++ tools/lib/bpf/btf_sort.c | 174 ++++++++++++++++++++++ tools/lib/bpf/btf_sort.h | 11 ++ tools/lib/bpf/libbpf.map | 6 + tools/lib/bpf/libbpf_version.h | 2 +- 6 files changed, 447 insertions(+), 25 deletions(-) create mode 100644 tools/lib/bpf/btf_sort.c create mode 100644 tools/lib/bpf/btf_sort.h
This looks a bit over-engineered, let's try to simplify and have more succinct implementation
pw-bot: cr
Quoted 26 lines
tools/lib/bpf/btf.c +7
-0@@ -23,6 +23,7 @@#include "libbpf_internal.h" #include "hashmap.h" #include "strset.h" +#include "btf_sort.h" #define BTF_MAX_NR_TYPES 0x7fffffffU#define BTF_MAX_STR_OFFSET 0x7fffffffU@@ -92,6 +93,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 */
tools/lib/bpf/btf.c const struct btf *btf__base_btf(const struct btf *btf) · line 637
Quoted 7 lines
tools/lib/bpf/btf.c +4
-0@@ -624,6 +631,11 @@ const struct btf *btf__base_btf(const struct btf *btf)return btf->base_btf; } +__u32 btf__start_id (const struct btf *btf) +{ +return btf->start_id; +}
this can already be determined using btf__base_btf() (and then getting its btf__type_cnt()), but I guess I don't mind having a small dedicated API for this. But please add it as a separate patch
Quoted 32 lines
tools/lib/bpf/btf.c +1
-22+/* internal helper returning non-const pointer to a type */ struct btf_type *btf_type_by_id (const struct btf *btf,__u32 type_id) {@@ -915,38 +927,16 @@ __s32 btf__find_by_name(const struct btf *btf, const char *type_name)return libbpf_err (-ENOENT ); } -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 (-ENOENT ); -} -__s32 btf__find_by_name_kind_own (const struct btf *btf,const char *type_name,__u32 kind)
tools/lib/bpf/btf.c __s32 btf__find_by_name(const struct btf *btf, const char *type_name) · line 939
Quoted 10 lines
tools/lib/bpf/btf.c +2
-2{ -return btf_find_by_name_kind (btf, btf->start_id, type_name, kind); +return _btf_find_by_name_kind (btf, btf->start_id, type_name, kind); }__s32 btf__find_by_name_kind (const struct btf *btf,const char *type_name,__u32 kind) { -return btf_find_by_name_kind (btf,1 , type_name, kind); +return _btf_find_by_name_kind (btf,1 , type_name, kind);
nit: please avoid using underscore-prefixed names
tools/lib/bpf/btf.c static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b · line 1084
Quoted 8 lines
tools/lib/bpf/btf.c +1
-0}static bool btf_is_modifiable (const struct btf *btf)@@ -1091,6 +1081,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, btf->start_id);
let's do this lazily when we actually need to search by name, that will also work better with invalidation (currently you don't recheck sortedness after invalidation)
[...]
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5839
Quoted 6 lines
tools/lib/bpf/btf.c +6
-0+/* +* Permute BTF types in-place using the ID mapping from btf_permute_opts->ids. +* After permutation, all type ID references are updated to reflect the new +* ordering. If a struct btf_ext (representing '.BTF.ext' section) is provided, +* type ID references within the BTF extension data are also updated. +*/
See how we provide doc comment for public APIs and do the same with btf__permute
Quoted 1 line
+int
btf__permute(struct btf *btf, const struct btf_permute_opts *opts)
id map array is mandatory parameter which will always be specified, make it a fixed argument. We use opts for something that's optional and/or infrequently used. btf_ext being part of opts makes total sense, though.
Quoted 14 lines
tools/lib/bpf/btf.c +14
-0+{ +struct btf_permute *p; +int err =0 ; + +if (!OPTS_VALID (opts, btf_permute_opts)) +return libbpf_err (-EINVAL ); + + p =btf_permute_new (btf, opts); +if (!p) { +pr_debug ("btf_permute_new failed: %ld\n" ,PTR_ERR (p)); +return libbpf_err (-EINVAL ); + } + +if (btf_ensure_modifiable (btf)) {
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5864
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+ err = -ENOMEM ; + goto done; + } + + err =btf_permute_shuffle_types (p); +if (err <0 ) { +pr_debug ("btf_permute_shuffle_types failed: %s\n" ,errstr (err)); + goto done; + } + err =btf_permute_remap_types (p);
can't we remap IDs as we shuffle and move types around? I'm not sure we need entire struct btf_permute to keep track of all of this, this can be a local state in a single function
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+if (err) { +pr_debug ("btf_permute_remap_types failed: %s\n" ,errstr (err)); + goto done; + } + +done: +btf_permute_free (p); +return libbpf_err (err); +} +
[...]
Quoted 13 lines
tools/lib/bpf/btf.c +13
-0+/* +* Shuffle BTF types. +* +* Rearranges types according to the permutation map in p->ids. The p->map +* array stores the mapping from original type IDs to new shuffled IDs, +* which is used in the next phase to update type references. +*/ +static int btf_permute_shuffle_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +const struct btf_type *t; +__u32 *new_offs =NULL ; +void *l, *new_types =NULL ;
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5954
Quoted 10 lines
tools/lib/bpf/btf.c +10
-0+int i, id, len, err; + + new_offs =calloc (btf->nr_types,sizeof (*new_offs)); + new_types =calloc (btf->hdr->type_len,1 ); +if (!new_types || !new_offs) { + err = -ENOMEM ; + goto out_err; + } + + l = new_types;
What does "l" refer to in this name? It rings no bells for me...
Quoted 1 line
+ for (i = 0; i <
btf->nr_types; i++) {
this won't work with split BTF, no?
Quoted 15 lines
tools/lib/bpf/btf.c +15
-0+ id = p->ids[i]; + t =btf__type_by_id (btf, id); + len =btf_type_size (t); +memcpy (l, t, len); + new_offs[i] = l - new_types; + p->map[id - btf->start_id] = btf->start_id + i; + l += len; + } + +free (btf->types_data); +free (btf->type_offs); + btf->types_data = new_types; + btf->type_offs = new_offs; +return 0 ; +
[...]
tools/lib/bpf/btf_sort.c
Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +0
-0
why does this have to be a separate file? can't it be part of btf.c?
Quoted 19 lines
tools/lib/bpf/btf_sort.c new file +18
-0@@ -0,0 +1,174 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) +/* Copyright (c) 2025 Xiaomi */ + +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif + +#ifdef __KERNEL__ + +#define btf_type_by_id (struct btf_type *)btf_type_by_id +#define btf__str_by_offset btf_str_by_offset +#define btf__type_cnt btf_nr_types +#define btf__start_id btf_start_id +#define libbpf_err (x) x + +#else + +#define notrace
tools/lib/bpf/btf_sort.c line 28
Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10
-0+ +#endif /* __KERNEL__ */ + +/* +* Skip the sorted check if the number of BTF types is below this threshold. +* The value 4 is chosen based on the theoretical break-even point where +* linear search (N/2) and binary search (LOG2(N)) require approximately +* the same number of comparisons. +*/ +#define BTF_CHECK_SORT_THRESHOLD 4
I agree with Eduard, it seems like an overkill. For small BTFs this all doesn't matter anyways.
Quoted 31 lines
tools/lib/bpf/btf_sort.c new file +31
-0+ +struct btf ; + +static int cmp_btf_kind_name (int ka,const char *na,int kb,const char *nb) +{ +return (ka - kb) ?:strcmp (na, nb); +} + +/* +* Sort BTF types by kind and name in ascending order, placing named types +* before anonymous ones. +*/ +static int btf_compare_type_kinds_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; +int ka, kb; + + 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); + +/* ta w/o name is greater than tb */ +if (anon_a && !anon_b) +return 1 ; +/* tb w/o name is smaller than ta */ +if (!anon_a && anon_b)
tools/lib/bpf/btf_sort.c line 69
Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10
-0+return -1 ; + + ka =btf_kind (ta); + kb =btf_kind (tb); + +if (anon_a && anon_b) +return ka - kb; + +return cmp_btf_kind_name (ka, na, kb, nb); +}
I think we should keep it simple and only use sorted-by-name property. Within the same name, we can just search linearly for necessary kind.
Quoted 18 lines
tools/lib/bpf/btf_sort.c new file +18
-0+ +static __s32 notrace __btf_find_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 (!btf) + goto out; + +if (start_id <btf__start_id (btf)) { + err =__btf_find_by_name_kind (btf->base_btf, start_id, type_name, kind); +if (err == -ENOENT ) + start_id =btf__start_id (btf); + } + +if (err == -ENOENT ) {
tools/lib/bpf/btf_sort.c line 97
Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10
-0+if (btf->nr_sorted_types) { +/* binary search */ +__s32 start, end, mid, found =-1 ; +int ret; + + start = start_id; + end = start + btf->nr_sorted_types -1 ; +/* found the leftmost btf_type that matches */ +while (start <= end) { + mid = start + (end - start) /2 ;
nit: binary search is, IMO, where succinct names like "l", "r", "m" are good and actually help keeping algorithm code more succinct without making it more obscure
Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +5
-0+ t =btf_type_by_id (btf, mid); + tname =btf__str_by_offset (btf, t->name_off); + ret =cmp_btf_kind_name (BTF_INFO_KIND (t->info), tname, + kind, type_name); +if (ret <0 )
tools/lib/bpf/btf_sort.c line 112
Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10
-0+ start = mid +1 ; + else { +if (ret ==0 ) + found = mid; + end = mid -1 ; + } + } + +if (found !=-1 ) +return found;
please check find_linfo() in kernel/bpf/log.c for a very succinct implementation of binary search where we look not for exact match, but rather leftmost or rightmost element satisfying some condition. find_linfo() is actually looking for leftmost element (despite what comment says :) ), so I think can be followed very closely.
Quoted 17 lines
tools/lib/bpf/btf_sort.c new file +17
-0+ }else { +/* linear search */ +__u32 i, total; + + total =btf__type_cnt (btf); +for (i = start_id; i < total; i++) { + t =btf_type_by_id (btf, i); +if (btf_kind (t) != kind) +continue ; + + tname =btf__str_by_offset (btf, t->name_off); +if (tname && !strcmp (tname, type_name)) +return i; + } + } + } +
[...]
Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
Quoted 39 lines · Andrii Nakryiko
Quoted 25 lines · Donglin Peng
This patch introduces a new libbpf interface
btf__permute()to reorganize BTF types according to a provided mapping. The BTF lookup mechanism is enhanced with binary search capability, significantly improving lookup performance for large type sets.The pahole tool can invoke this interface with a sorted type ID array, enabling binary search in both user space and kernel. To share core logic between kernel and libbpf, common sorting functionality is implemented in a new
btf_sort.csource file.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]>Co-developed-by Eduard Zingerman <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>---
v2->v3:
- Remove sorting logic from libbpf and provide a genericbtf__permute()interface
- Remove the search direction patch since sorted lookup provides sufficient performance and changing search order could cause conflicts between BTF and base BTF
- Includebtf_sort.cdirectly inbtf.cto reduce function call overheadQuoted 11 lines
--- tools/lib/bpf/btf.c | 262 ++++++++++++++++++++++++++++++--- tools/lib/bpf/btf.h | 17 +++ tools/lib/bpf/btf_sort.c | 174 ++++++++++++++++++++++ tools/lib/bpf/btf_sort.h | 11 ++ tools/lib/bpf/libbpf.map | 6 + tools/lib/bpf/libbpf_version.h | 2 +- 6 files changed, 447 insertions(+), 25 deletions(-) create mode 100644 tools/lib/bpf/btf_sort.c create mode 100644 tools/lib/bpf/btf_sort.h
Quoted 2 lines
This looks a bit over-engineered, let's try to simplify and have more succinct implementation
Thanks, I will simplify it.
Quoted 32 lines
pw-bot: cr
Quoted 29 lines
tools/lib/bpf/btf.c +7
-0@@ -23,6 +23,7 @@#include "libbpf_internal.h" #include "hashmap.h" #include "strset.h" +#include "btf_sort.h" #define BTF_MAX_NR_TYPES 0x7fffffffU#define BTF_MAX_STR_OFFSET 0x7fffffffU@@ -92,6 +93,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 */ @@ -624,6 +631,11 @@ const struct btf *btf__base_btf(const struct btf *btf)return btf->base_btf; }
Quoted 7 lines
tools/lib/bpf/btf.c const struct btf *btf__base_btf(const struct btf *btf) · line 637
Quoted 4 lines
tools/lib/bpf/btf.c +4
-0+__u32 btf__start_id (const struct btf *btf) +{ +return btf->start_id; +}this can already be determined using
btf__base_btf()(and then getting itsbtf__type_cnt()), but I guess I don't mind having a small
Yes, you're right. The calculation is sufficient:
- If base_btf is NULL, start_id = 1
- If base_btf is not NULL, start_id = btf__type_cnt(base_btf)
Quoted 39 lines
dedicated API for this. But please add it as a separate patch
Quoted 37 lines
tools/lib/bpf/btf.c +2
-23+/* internal helper returning non-const pointer to a type */ struct btf_type *btf_type_by_id (const struct btf *btf,__u32 type_id) {@@ -915,38 +927,16 @@ __s32 btf__find_by_name(const struct btf *btf, const char *type_name)return libbpf_err (-ENOENT ); } -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 (-ENOENT ); -} -__s32 btf__find_by_name_kind_own (const struct btf *btf,const char *type_name,__u32 kind) { -return btf_find_by_name_kind (btf, btf->start_id, type_name, kind); +return _btf_find_by_name_kind (btf, btf->start_id, type_name, kind); }
Quoted 7 lines
tools/lib/bpf/btf.c __s32 btf__find_by_name(const struct btf *btf, const char *type_name) · line 939
Quoted 5 lines
tools/lib/bpf/btf.c +1
-1__s32 btf__find_by_name_kind (const struct btf *btf,const char *type_name,__u32 kind) { -return btf_find_by_name_kind (btf,1 , type_name, kind); +return _btf_find_by_name_kind (btf,1 , type_name, kind);nit: please avoid using underscore-prefixed names
Thanks. I will fix it in the next version.
Quoted 13 lines
tools/lib/bpf/btf.c static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b · line 1084
Quoted 9 lines
tools/lib/bpf/btf.c +1
-0}static bool btf_is_modifiable (const struct btf *btf)@@ -1091,6 +1081,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, btf->start_id);let's do this lazily when we actually need to search by name, that will also work better with invalidation (currently you don't recheck sortedness after invalidation)
Thanks. I'll defer the call to btf_check_sorted until the first invocation of btf__find_by_name_kind.
Quoted 11 lines
[...]
Quoted 6 lines
+/*
+ * Permute BTF types in-place using the ID mapping frombtf_permute_opts->ids.
+ * After permutation, all type ID references are updated to reflect the new
+ * ordering. If a structbtf_ext(representing '.BTF.ext' section) is provided,
+ * type ID references within the BTF extension data are also updated.
+ */See how we provide doc comment for public APIs and do the same with
btf__permute
Thanks, I will fix it in the next version.
Quoted 7 lines
Quoted 2 lines
+int
btf__permute(struct btf *btf, const struct btf_permute_opts *opts)id map array is mandatory parameter which will always be specified, make it a fixed argument. We use opts for something that's optional and/or infrequently used.
btf_extbeing part of opts makes total sense, though.
Thanks, I will fix it in the next version, like:
int btf__permute(struct btf *btf, __u32 *id_map, const struct btf_permute_opts *opts)
Quoted 19 lines
Quoted 19 lines
tools/lib/bpf/btf.c +18
-0+{ +struct btf_permute *p; +int err =0 ; + +if (!OPTS_VALID (opts, btf_permute_opts)) +return libbpf_err (-EINVAL ); + + p =btf_permute_new (btf, opts); +if (!p) { +pr_debug ("btf_permute_new failed: %ld\n" ,PTR_ERR (p)); +return libbpf_err (-EINVAL ); + } + +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 5864
Quoted 6 lines
tools/lib/bpf/btf.c +6
-0+ err =btf_permute_shuffle_types (p); +if (err <0 ) { +pr_debug ("btf_permute_shuffle_types failed: %s\n" ,errstr (err)); + goto done; + } + err =btf_permute_remap_types (p);can't we remap IDs as we shuffle and move types around? I'm not sure
This approach appears infeasible, as it necessitates first generating a complete type ID mapping (similar to btf_dedup's hypot_map) to translate original IDs to new IDs for all referenced types, followed by executing the remapping phase.
Quoted 2 lines
we need entire struct
btf_permuteto keep track of all of this, this can be a local state in a single function
Thank you. I think that a btf_permute function may be necessary. As Eduard suggested, we can generalize btf_dedup_remap_types into a reusable function, which would require a dedicated structure to encapsulate all necessary parameters.
Quoted 31 lines
Quoted 11 lines
tools/lib/bpf/btf.c +10
-0+if (err) { +pr_debug ("btf_permute_remap_types failed: %s\n" ,errstr (err)); + goto done; + } + +done: +btf_permute_free (p); +return libbpf_err (err); +} +[...]
Quoted 17 lines
tools/lib/bpf/btf.c +17
-0+/* +* Shuffle BTF types. +* +* Rearranges types according to the permutation map in p->ids. The p->map +* array stores the mapping from original type IDs to new shuffled IDs, +* which is used in the next phase to update type references. +*/ +static int btf_permute_shuffle_types (struct btf_permute *p) +{ +struct btf *btf = p->btf; +const struct btf_type *t; +__u32 *new_offs =NULL ; +void *l, *new_types =NULL ; +int i, id, len, err; + + new_offs =calloc (btf->nr_types,sizeof (*new_offs)); + new_types =calloc (btf->hdr->type_len,1 );
Quoted 8 lines
tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5954
Quoted 6 lines
tools/lib/bpf/btf.c +6
-0+if (!new_types || !new_offs) { + err = -ENOMEM ; + goto out_err; + } + + l = new_types;What does "l" refer to in this name? It rings no bells for me...
Would the name "nt" be acceptable?
Quoted 4 lines
Quoted 2 lines
+ for (i = 0; i <
btf->nr_types; i++) {this won't work with split BTF, no?
The ids array in btf_permute stores type IDs for split BTF. Local testing confirms that kernel module BTF is properly pre-sorted during build using a patched pahole version.
Example usage in pahole:
static int btf_encoder__sort(struct btf *btf)
{
LIBBPF_OPTS(btf_permute_opts, opts);
int start_id = btf__start_id(btf);
int nr_types = btf__type_cnt(btf) - start_id;
__u32 *permute_ids;
int i, id, err = 0;
if (nr_types < 2)
return 0;
permute_ids = calloc(nr_types, sizeof(*permute_ids));
if (!permute_ids) {
err = -ENOMEM;
goto out_free;
}
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_types_kinds_names, btf);
opts.ids = permute_ids;
err = btf__permute(btf, &opts);
if (err)
goto out_free;out_free:
if (permute_ids)
free(permute_ids);
return err;
}Quoted 19 lines
Quoted 16 lines
tools/lib/bpf/btf.c +15
-0+ id = p->ids[i]; + t =btf__type_by_id (btf, id); + len =btf_type_size (t); +memcpy (l, t, len); + new_offs[i] = l - new_types; + p->map[id - btf->start_id] = btf->start_id + i; + l += len; + } + +free (btf->types_data); +free (btf->type_offs); + btf->types_data = new_types; + btf->type_offs = new_offs; +return 0 ; +[...]
Quoted 7 lines
tools/lib/bpf/btf_sort.c
Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +0
-0why does this have to be a separate file? can't it be part of
btf.c?
Thanks. The kernel can leverage existing common infrastructure, similar to the approach used in bpf_relocate.c. If this shared approach isn't acceptable, I'm prepared to implement separate versions for both libbpf and the kernel.
https://lore.kernel.org/all/[email protected]/#t
https://lore.kernel.org/all/[email protected]/
Quoted 25 lines
Quoted 25 lines
tools/lib/bpf/btf_sort.c new file +23
-0@@ -0,0 +1,174 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) +/* Copyright (c) 2025 Xiaomi */ + +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif + +#ifdef __KERNEL__ + +#define btf_type_by_id (struct btf_type *)btf_type_by_id +#define btf__str_by_offset btf_str_by_offset +#define btf__type_cnt btf_nr_types +#define btf__start_id btf_start_id +#define libbpf_err (x) x + +#else + +#define notrace + +#endif /* __KERNEL__ */ + +/* +* Skip the sorted check if the number of BTF types is below this threshold.
Quoted 8 lines
tools/lib/bpf/btf_sort.c line 28
Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +5
-0+* The value 4 is chosen based on the theoretical break-even point where +* linear search (N/2) and binary search (LOG2(N)) require approximately +* the same number of comparisons. +*/ +#define BTF_CHECK_SORT_THRESHOLD 4I agree with Eduard, it seems like an overkill. For small BTFs this all doesn't matter anyways.
Thanks, I will remove it in the next version.
Quoted 37 lines
Quoted 37 lines
tools/lib/bpf/btf_sort.c new file +36
-0+ +struct btf ; + +static int cmp_btf_kind_name (int ka,const char *na,int kb,const char *nb) +{ +return (ka - kb) ?:strcmp (na, nb); +} + +/* +* Sort BTF types by kind and name in ascending order, placing named types +* before anonymous ones. +*/ +static int btf_compare_type_kinds_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; +int ka, kb; + + 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); + +/* ta w/o name is greater than tb */ +if (anon_a && !anon_b) +return 1 ; +/* tb w/o name is smaller than ta */ +if (!anon_a && anon_b) +return -1 ; + + ka =btf_kind (ta); + kb =btf_kind (tb); +
Quoted 8 lines
tools/lib/bpf/btf_sort.c line 69
Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +5
-0+if (anon_a && anon_b) +return ka - kb; + +return cmp_btf_kind_name (ka, na, kb, nb); +}I think we should keep it simple and only use sorted-by-name property. Within the same name, we can just search linearly for necessary kind.
This approach is feasible, though it may introduce some overhead in the search function. I previously implemented a hybrid method that first sorts types by name
and then combines binary search with linear search for handling collisions.
https://lore.kernel.org/all/[email protected]/
id = btf_find_by_name_bsearch(btf, name, &start, &end);
if (id > 0) {
while (start <= end) {
t = btf_type_by_id(btf, start);
if (BTF_INFO_KIND(t->info) == kind)
return start;
start++;
}
}Could this be acceptable?
Quoted 25 lines
Quoted 25 lines
tools/lib/bpf/btf_sort.c new file +24
-0+ +static __s32 notrace __btf_find_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 (!btf) + goto out; + +if (start_id <btf__start_id (btf)) { + err =__btf_find_by_name_kind (btf->base_btf, start_id, type_name, kind); +if (err == -ENOENT ) + start_id =btf__start_id (btf); + } + +if (err == -ENOENT ) { +if (btf->nr_sorted_types) { +/* binary search */ +__s32 start, end, mid, found =-1 ; +int ret; + + start = start_id;
Quoted 8 lines
tools/lib/bpf/btf_sort.c line 97
Quoted 4 lines
tools/lib/bpf/btf_sort.c new file +4
-0+ end = start + btf->nr_sorted_types -1 ; +/* found the leftmost btf_type that matches */ +while (start <= end) { + mid = start + (end - start) /2 ;nit: binary search is, IMO, where succinct names like "l", "r", "m" are good and actually help keeping algorithm code more succinct without making it more obscure
Thanks, I will fix it in the next version.
Quoted 17 lines
Quoted 6 lines
tools/lib/bpf/btf_sort.c new file +5
-0+ t =btf_type_by_id (btf, mid); + tname =btf__str_by_offset (btf, t->name_off); + ret =cmp_btf_kind_name (BTF_INFO_KIND (t->info), tname, + kind, type_name); +if (ret <0 )tools/lib/bpf/btf_sort.c line 112
Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10
-0+ start = mid +1 ; + else { +if (ret ==0 ) + found = mid; + end = mid -1 ; + } + } + +if (found !=-1 ) +return found;
Quoted 5 lines
please check
find_linfo()inkernel/bpf/log.cfor a very succinct implementation of binary search where we look not for exact match, but rather leftmost or rightmost element satisfying some condition.find_linfo()is actually looking for leftmost element (despite what comment says :) ), so I think can be followed very closely.
Thank you for the suggestion. If we sort types solely by name as proposed, we would need to first identify the leftmost and rightmost bounds of the matching name range (similar to find_linfo's approach), then perform a linear search within that range to find the first type with a matching kind.
Quoted 20 lines
Quoted 18 lines
tools/lib/bpf/btf_sort.c new file +17
-0+ }else { +/* linear search */ +__u32 i, total; + + total =btf__type_cnt (btf); +for (i = start_id; i < total; i++) { + t =btf_type_by_id (btf, i); +if (btf_kind (t) != kind) +continue ; + + tname =btf__str_by_offset (btf, t->name_off); +if (tname && !strcmp (tname, type_name)) +return i; + } + } + } +[...]
RFC PATCH v3 2/3 selftests/bpf: add tests for BTF type permutation
In reply to Donglin PengVerify that BTF type permutation functionality works correctly.
--- tools/testing/selftests/bpf/prog_tests/btf.c | 109 ++++++++++++++++--- 1 file changed, 94 insertions(+), 15 deletions(-)
tools/testing/selftests/bpf/prog_tests/btf.c +94 -15
@@ -6935,14 +6935,18 @@ struct btf_raw_data {__u32 str_sec_size; }; -struct btf_dedup_test { +struct btf_dedup_permute_test {const char *descr;struct btf_raw_data input;struct btf_raw_data expect; -struct btf_dedup_opts opts; +bool permute; +struct btf_dedup_opts dedup_opts; +struct btf_permute_opts permute_opts; }; -static struct btf_dedup_test dedup_tests[] = { +static __u32 permute_ids_sort_by_kind_name[] = {3 ,4 ,5 ,8 ,11 ,14 ,6 ,9 ,12 ,15 ,7 ,10 ,13 ,16 ,1 ,2 }; + +static struct btf_dedup_permute_test dedup_permute_tests[] = { { .descr ="dedup: unused strings filtering" ,
@@ -7105,7 +7109,7 @@ static struct btf_dedup_test dedup_tests[] = { }, BTF_STR_SEC("\0s\0x"), }, - .opts = { + .dedup_opts = { .force_collisions = true, /* force hash collisions */ }, },
@@ -7151,7 +7155,7 @@ static struct btf_dedup_test dedup_tests[] = { }, BTF_STR_SEC("\0s\0x"), }, - .opts = { + .dedup_opts = { .force_collisions = true, /* force hash collisions */ }, },
@@ -7354,7 +7358,7 @@ static struct btf_dedup_test dedup_tests[] = { }, BTF_STR_SEC("\0.bss\0t"), }, - .opts = { + .dedup_opts = { .force_collisions = true }, },
@@ -8022,6 +8026,72 @@ static struct btf_dedup_test dedup_tests[] = { BTF_STR_SEC("\0foo\0x\0y\0foo_ptr"), }, }, +{ + .descr = "permute: func/func_param/struct/struct_member tags", + .input = { + .raw_types = { + /* int */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ +/* void f(int a1, int a2) */ + BTF_FUNC_PROTO_ENC(0, 2), /* [2] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 1), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1), + BTF_FUNC_ENC(NAME_NTH(3), 2), /* [3] */ +/* struct t {int m1; int m2;} */ + BTF_STRUCT_ENC(NAME_NTH(4), 2, 8), /* [4] */ + BTF_MEMBER_ENC(NAME_NTH(5), 1, 0), + BTF_MEMBER_ENC(NAME_NTH(6), 1, 32), +/* tag -> f: tag1, tag2, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(7), 3, -1), /* [5] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 3, -1), /* [6] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 3, -1), /* [7] */ +/* tag -> f/a2: tag1, tag2, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(7), 3, 1), /* [8] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 3, 1), /* [9] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 3, 1), /* [10] */ +/* tag -> t: tag1, tag2, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(7), 4, -1), /* [11] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 4, -1), /* [12] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 4, -1), /* [13] */ +/* tag -> t/m2: tag1, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(7), 4, 1), /* [14] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 4, 1), /* [15] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 4, 1), /* [16] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"), + }, + .expect = { + .raw_types = { +BTF_FUNC_ENC (NAME_NTH (3 ),16 ),/* [1] */ +BTF_STRUCT_ENC (NAME_NTH (4 ),2 ,8 ),/* [2] */ +BTF_MEMBER_ENC (NAME_NTH (5 ),15 ,0 ), +BTF_MEMBER_ENC (NAME_NTH (6 ),15 ,32 ), +BTF_DECL_TAG_ENC (NAME_NTH (7 ),1 ,-1 ),/* [3] */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),1 ,1 ),/* [4] */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),2 ,-1 ),/* [5] */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),2 ,1 ),/* [6] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),1 ,-1 ),/* [7] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),1 ,1 ),/* [8] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),2 ,-1 ),/* [9] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),2 ,1 ),/* [10] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),1 ,-1 ),/* [11] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),1 ,1 ),/* [12] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),2 ,-1 ),/* [13] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),2 ,1 ),/* [14] */ +BTF_TYPE_INT_ENC (0 ,BTF_INT_SIGNED ,0 ,32 ,4 ),/* [15] */ +BTF_FUNC_PROTO_ENC (0 ,2 ),/* [16] */ +BTF_FUNC_PROTO_ARG_ENC (NAME_NTH (1 ),15 ), +BTF_FUNC_PROTO_ARG_ENC (NAME_NTH (2 ),15 ), +BTF_END_RAW , + }, + BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"), + }, + .permute = true, + .permute_opts = { + .ids = permute_ids_sort_by_kind_name, + }, +}, };static int btf_type_size (const struct btf_type *t)
@@ -8078,9 +8148,9 @@ static void dump_btf_strings(const char *strs, __u32 len) } } -static void do_test_dedup (unsigned int test_num) +static void do_test_dedup_permute (unsigned int test_num) { -struct btf_dedup_test *test = &dedup_tests[test_num -1 ]; +struct btf_dedup_permute_test *test = &dedup_permute_tests[test_num -1 ];__u32 test_nr_types, expect_nr_types, test_btf_size, expect_btf_size;const struct btf_header *test_hdr, *expect_hdr;struct btf *test_btf =NULL , *expect_btf =NULL ;
@@ -8124,11 +8194,20 @@ static void do_test_dedup(unsigned int test_num) goto done; } - test->opts.sz =sizeof (test->opts); - err =btf__dedup (test_btf, &test->opts); -if (CHECK (err,"btf_dedup failed errno:%d" , err)) { - err =-1 ; - goto done; +if (test->permute) { + test->permute_opts.sz =sizeof (test->permute_opts); + err =btf__permute (test_btf, &test->permute_opts); +if (CHECK (err,"btf_permute failed errno:%d" , err)) { + err =-1 ; + goto done; + } + }else { + test->dedup_opts.sz =sizeof (test->dedup_opts); + err =btf__dedup (test_btf, &test->dedup_opts); +if (CHECK (err,"btf_dedup failed errno:%d" , err)) { + err =-1 ; + goto done; + } } test_btf_data =btf__raw_data (test_btf, &test_btf_size);
@@ -8249,7 +8328,7 @@ void test_btf(void)do_test_file (i);for (i =1 ; i <=ARRAY_SIZE (info_raw_tests); i++)do_test_info_raw (i); -for (i =1 ; i <=ARRAY_SIZE (dedup_tests); i++) -do_test_dedup (i); +for (i =1 ; i <=ARRAY_SIZE (dedup_permute_tests); i++) +do_test_dedup_permute (i);test_pprint (); }
Signature · 1 line
2.34.1
Eduard Zingerman
maintainerRe: [RFC PATCH v3 2/3] selftests/bpf: add tests for BTF type permutation
Quoted 10 lines · Donglin Peng
Verify that BTF type permutation functionality works correctly.
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>---
Do we need a test case for split btf?
We probably do, as there is index arithmetic etc.
[...]
Quoted 29 lines
tools/testing/selftests/bpf/prog_tests/btf.c +25
-0@@ -8022,6 +8026,72 @@ static struct btf_dedup_test dedup_tests[] = { BTF_STR_SEC("\0foo\0x\0y\0foo_ptr"), }, }, +{ + .descr = "permute: func/func_param/struct/struct_member tags", + .input = { + .raw_types = { +/* int */ +BTF_TYPE_INT_ENC (0 ,BTF_INT_SIGNED ,0 ,32 ,4 ),/* [1] */ +/* void f(int a1, int a2) */ +BTF_FUNC_PROTO_ENC (0 ,2 ),/* [2] */ +BTF_FUNC_PROTO_ARG_ENC (NAME_NTH (1 ),1 ), +BTF_FUNC_PROTO_ARG_ENC (NAME_NTH (2 ),1 ), +BTF_FUNC_ENC (NAME_NTH (3 ),2 ),/* [3] */ +/* struct t {int m1; int m2;} */ +BTF_STRUCT_ENC (NAME_NTH (4 ),2 ,8 ),/* [4] */ +BTF_MEMBER_ENC (NAME_NTH (5 ),1 ,0 ), +BTF_MEMBER_ENC (NAME_NTH (6 ),1 ,32 ), +/* tag -> f: tag1, tag2, tag3 */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),3 ,-1 ),/* [5] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),3 ,-1 ),/* [6] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),3 ,-1 ),/* [7] */ +/* tag -> f/a2: tag1, tag2, tag3 */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),3 ,1 ),/* [8] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),3 ,1 ),/* [9] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),3 ,1 ),/* [10] */ +/* tag -> t: tag1, tag2, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(7), 4, -1), /* [11] */
tools/testing/selftests/bpf/prog_tests/btf.c static struct btf_dedup_test dedup_tests[] = { · line 8063
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/btf.c +10
-0+ BTF_DECL_TAG_ENC(NAME_NTH(8), 4, -1), /* [12] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 4, -1), /* [13] */ +/* tag -> t/m2: tag1, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(7), 4, 1), /* [14] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 4, 1), /* [15] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 4, 1), /* [16] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"), + },
Nit: I think that this test is a bit too large.
Having fewer decl_tags would still test what we want to test.
Quoted 32 lines
tools/testing/selftests/bpf/prog_tests/btf.c +31
-0+ .expect = { + .raw_types = { +BTF_FUNC_ENC (NAME_NTH (3 ),16 ),/* [1] */ +BTF_STRUCT_ENC (NAME_NTH (4 ),2 ,8 ),/* [2] */ +BTF_MEMBER_ENC (NAME_NTH (5 ),15 ,0 ), +BTF_MEMBER_ENC (NAME_NTH (6 ),15 ,32 ), +BTF_DECL_TAG_ENC (NAME_NTH (7 ),1 ,-1 ),/* [3] */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),1 ,1 ),/* [4] */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),2 ,-1 ),/* [5] */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),2 ,1 ),/* [6] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),1 ,-1 ),/* [7] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),1 ,1 ),/* [8] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),2 ,-1 ),/* [9] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),2 ,1 ),/* [10] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),1 ,-1 ),/* [11] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),1 ,1 ),/* [12] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),2 ,-1 ),/* [13] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),2 ,1 ),/* [14] */ +BTF_TYPE_INT_ENC (0 ,BTF_INT_SIGNED ,0 ,32 ,4 ),/* [15] */ +BTF_FUNC_PROTO_ENC (0 ,2 ),/* [16] */ +BTF_FUNC_PROTO_ARG_ENC (NAME_NTH (1 ),15 ), +BTF_FUNC_PROTO_ARG_ENC (NAME_NTH (2 ),15 ), +BTF_END_RAW , + }, + BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"), + }, + .permute = true, + .permute_opts = { + .ids = permute_ids_sort_by_kind_name, + }, +}, };
[...]
Re: [RFC PATCH v3 2/3] selftests/bpf: add tests for BTF type permutation
Quoted 13 lines · Eduard Zingerman
Quoted 10 lines · Donglin Peng
Verify that BTF type permutation functionality works correctly.
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>---
Quoted 2 lines
Do we need a test case for split btf?
We probably do, as there is index arithmetic etc.
Thanks, I will add a test case for split btf.
Quoted 37 lines
[...]
Quoted 34 lines
tools/testing/selftests/bpf/prog_tests/btf.c +30
-0@@ -8022,6 +8026,72 @@ static struct btf_dedup_test dedup_tests[] = { BTF_STR_SEC("\0foo\0x\0y\0foo_ptr"), }, }, +{ + .descr = "permute: func/func_param/struct/struct_member tags", + .input = { + .raw_types = { +/* int */ +BTF_TYPE_INT_ENC (0 ,BTF_INT_SIGNED ,0 ,32 ,4 ),/* [1] */ +/* void f(int a1, int a2) */ +BTF_FUNC_PROTO_ENC (0 ,2 ),/* [2] */ +BTF_FUNC_PROTO_ARG_ENC (NAME_NTH (1 ),1 ), +BTF_FUNC_PROTO_ARG_ENC (NAME_NTH (2 ),1 ), +BTF_FUNC_ENC (NAME_NTH (3 ),2 ),/* [3] */ +/* struct t {int m1; int m2;} */ +BTF_STRUCT_ENC (NAME_NTH (4 ),2 ,8 ),/* [4] */ +BTF_MEMBER_ENC (NAME_NTH (5 ),1 ,0 ), +BTF_MEMBER_ENC (NAME_NTH (6 ),1 ,32 ), +/* tag -> f: tag1, tag2, tag3 */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),3 ,-1 ),/* [5] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),3 ,-1 ),/* [6] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),3 ,-1 ),/* [7] */ +/* tag -> f/a2: tag1, tag2, tag3 */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),3 ,1 ),/* [8] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),3 ,1 ),/* [9] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),3 ,1 ),/* [10] */ +/* tag -> t: tag1, tag2, tag3 */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),4 ,-1 ),/* [11] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),4 ,-1 ),/* [12] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),4 ,-1 ),/* [13] */ +/* tag -> t/m2: tag1, tag3 */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),4 ,1 ),/* [14] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 4, 1), /* [15] */
Quoted 8 lines
tools/testing/selftests/bpf/prog_tests/btf.c static struct btf_dedup_test dedup_tests[] = { · line 8063
Quoted 5 lines
tools/testing/selftests/bpf/prog_tests/btf.c +5
-0+ BTF_DECL_TAG_ENC(NAME_NTH(9), 4, 1), /* [16] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"), + },Nit: I think that this test is a bit too large.
Having fewerdecl_tagswould still test what we want to test.
Thanks, I agree, I will clean it up.
Quoted 35 lines
Quoted 33 lines
tools/testing/selftests/bpf/prog_tests/btf.c +31
-0+ .expect = { + .raw_types = { +BTF_FUNC_ENC (NAME_NTH (3 ),16 ),/* [1] */ +BTF_STRUCT_ENC (NAME_NTH (4 ),2 ,8 ),/* [2] */ +BTF_MEMBER_ENC (NAME_NTH (5 ),15 ,0 ), +BTF_MEMBER_ENC (NAME_NTH (6 ),15 ,32 ), +BTF_DECL_TAG_ENC (NAME_NTH (7 ),1 ,-1 ),/* [3] */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),1 ,1 ),/* [4] */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),2 ,-1 ),/* [5] */ +BTF_DECL_TAG_ENC (NAME_NTH (7 ),2 ,1 ),/* [6] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),1 ,-1 ),/* [7] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),1 ,1 ),/* [8] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),2 ,-1 ),/* [9] */ +BTF_DECL_TAG_ENC (NAME_NTH (8 ),2 ,1 ),/* [10] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),1 ,-1 ),/* [11] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),1 ,1 ),/* [12] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),2 ,-1 ),/* [13] */ +BTF_DECL_TAG_ENC (NAME_NTH (9 ),2 ,1 ),/* [14] */ +BTF_TYPE_INT_ENC (0 ,BTF_INT_SIGNED ,0 ,32 ,4 ),/* [15] */ +BTF_FUNC_PROTO_ENC (0 ,2 ),/* [16] */ +BTF_FUNC_PROTO_ARG_ENC (NAME_NTH (1 ),15 ), +BTF_FUNC_PROTO_ARG_ENC (NAME_NTH (2 ),15 ), +BTF_END_RAW , + }, + BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"), + }, + .permute = true, + .permute_opts = { + .ids = permute_ids_sort_by_kind_name, + }, +}, };[...]
RFC PATCH v3 3/3 btf: Reuse libbpf code for BTF type sorting verification and binary search
In reply to Donglin PengThe previous commit implemented BTF sorting verification and binary search algorithm in libbpf. This patch enables this functionality in the kernel.
---v2->v3:
- Include btf_sort.c directly in btf.c to reduce function call overhead
--- kernel/bpf/btf.c | 34 ++++++++++++++++++---------------- 1 file changed, 18 insertions(+), 16 deletions(-)
kernel/bpf/btf.c +18 -16
@@ -33,6 +33,7 @@#include <net/sock.h> #include <net/xdp.h> #include "../tools/lib/bpf/relo_core.h" +#include "../tools/lib/bpf/btf_sort.h" /* BTF (BPF Type Format) is the meta data format which describes * the data types of BPF program/map. Hence, it basically focus
@@ -259,6 +260,7 @@ struct btf {void *nohdr_data;struct btf_header hdr;u32 nr_types;/* includes VOID for base BTF */ +u32 nr_sorted_types;/* All named types in the sorted BTF instance */ u32 types_size;u32 data_size;refcount_t refcnt;
@@ -527,6 +529,11 @@ static bool btf_type_is_decl_tag_target(const struct btf_type *t)btf_type_is_var (t) ||btf_type_is_typedef (t); } +static u32 btf_start_id (const struct btf *btf) +{ +return btf->start_id + (btf->base_btf ?0 :1 ); +} +bool btf_is_vmlinux (const struct btf *btf) {return btf->kernel_btf && !btf->base_btf;
@@ -546,22 +553,7 @@ u32 btf_nr_types(const struct btf *btf)s32 btf_find_by_name_kind (const struct btf *btf,const char *name,u8 kind) { -const struct btf_type *t; -const char *tname; -u32 i, total; - - 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 ; - - tname =btf_name_by_offset (btf, t->name_off); -if (!strcmp (tname, name)) -return i; - } - -return -ENOENT ; +return _btf_find_by_name_kind (btf,1 , name, kind); }s32 bpf_find_btf_id (const char *name,u32 kind,struct btf **btf_p)
@@ -6230,6 +6222,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *nameif (err) goto errout; +btf_check_sorted (btf,1 );refcount_set (&btf->refcnt,1 );return btf;
@@ -6362,6 +6355,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data, base_btf = vmlinux_btf; } +btf_check_sorted (btf,btf_nr_types (base_btf));btf_verifier_env_free (env);refcount_set (&btf->refcnt,1 );return btf;
@@ -9577,3 +9571,11 @@ bool btf_param_match_suffix(const struct btf *btf, param_name += len - suffix_len;return !strncmp (param_name, suffix, suffix_len); } + +/* +* btf_sort.c is included directly to avoid function call overhead +* when accessing BTF private data, as this file is shared between +* libbpf and kernel and may be called frequently (especially when +* funcgraph-args or func-args tracing options are enabled). +*/ +#include "../../tools/lib/bpf/btf_sort.c"
Signature · 1 line
2.34.1
Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search
kernel/bpf/btf.c bool btf_param_match_suffix(const struct btf *btf, · line 9581
Quoted 9 lines · Donglin Peng
kernel/bpf/btf.c +8
-0+ +/* +* btf_sort.c is included directly to avoid function call overhead +* when accessing BTF private data, as this file is shared between +* libbpf and kernel and may be called frequently (especially when +* funcgraph-args or func-args tracing options are enabled). +*/ +#include "../../tools/lib/bpf/btf_sort.c"
function call overhead? I don't believe it's measurable.
Don't do it on libbpf side either.
pw-bot: cr
Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search
Quoted 13 lines · Alexei Starovoitov
kernel/bpf/btf.c bool btf_param_match_suffix(const struct btf *btf, · line 9581
Quoted 9 lines · Donglin Peng
kernel/bpf/btf.c +8
-0+ +/* +* btf_sort.c is included directly to avoid function call overhead +* when accessing BTF private data, as this file is shared between +* libbpf and kernel and may be called frequently (especially when +* funcgraph-args or func-args tracing options are enabled). +*/ +#include "../../tools/lib/bpf/btf_sort.c" function call overhead? I don't believe it's measurable.
Thank you. Since the overhead is primarily due to the function graph tracer, I have reverted to the v2 approach and added the notrace attribute to the relevant functions.
Quoted 2 lines
Don't do it on libbpf side either.
Yes.
Quoted 2 lines
pw-bot: cr
Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search
In reply to Donglin PengQuoted 24 lines · Donglin Peng
The previous commit implemented BTF sorting verification and binary search algorithm in libbpf. This patch enables this functionality in the kernel.
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>---
v2->v3:
- Includebtf_sort.cdirectly inbtf.cto reduce function call overhead--- kernel/bpf/btf.c | 34 ++++++++++++++++++---------------- 1 file changed, 18 insertions(+), 16 deletions(-)kernel/bpf/btf.c +0
-0
kernel/bpf/btf.c line 36
Quoted 4 lines
kernel/bpf/btf.c +1
-0@@ -33,6 +33,7 @@#include <net/sock.h> #include <net/xdp.h> #include "../tools/lib/bpf/relo_core.h" +#include "../tools/lib/bpf/btf_sort.h"
I don't believe in code reuse for the sake of code reuse. This code sharing just makes everything more entangled and complicated. Reimplementing binary search is totally fine, IMO.
[...]
Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search
Quoted 21 lines · Andrii Nakryiko
Quoted 19 lines · Donglin Peng
The previous commit implemented BTF sorting verification and binary search algorithm in libbpf. This patch enables this functionality in the kernel.
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>---
v2->v3:
- Includebtf_sort.cdirectly inbtf.cto reduce function call overhead--- kernel/bpf/btf.c | 34 ++++++++++++++++++---------------- 1 file changed, 18 insertions(+), 16 deletions(-)
Quoted 13 lines
kernel/bpf/btf.c line 36
Quoted 9 lines
kernel/bpf/btf.c +1
-0@@ -33,6 +33,7 @@#include <net/sock.h> #include <net/xdp.h> #include "../tools/lib/bpf/relo_core.h" +#include "../tools/lib/bpf/btf_sort.h" I don't believe in code reuse for the sake of code reuse. This code sharing just makes everything more entangled and complicated. Reimplementing binary search is totally fine, IMO.
Thanks. Would you be open to the approach from v2, where we place the common code in btf_sort.c and compile it separately rather than including it directly?
Quoted 2 lines
[...]
Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search
Quoted 38 lines · Donglin Peng
Quoted 21 lines · Andrii Nakryiko
Quoted 19 lines · Donglin Peng
The previous commit implemented BTF sorting verification and binary search algorithm in libbpf. This patch enables this functionality in the kernel.
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>---
v2->v3:
- Includebtf_sort.cdirectly inbtf.cto reduce function call overhead--- kernel/bpf/btf.c | 34 ++++++++++++++++++---------------- 1 file changed, 18 insertions(+), 16 deletions(-)Quoted 13 lines
kernel/bpf/btf.c line 36
Quoted 9 lines
kernel/bpf/btf.c +1
-0@@ -33,6 +33,7 @@#include <net/sock.h> #include <net/xdp.h> #include "../tools/lib/bpf/relo_core.h" +#include "../tools/lib/bpf/btf_sort.h" I don't believe in code reuse for the sake of code reuse. This code sharing just makes everything more entangled and complicated. Reimplementing binary search is totally fine, IMO.
Quoted 4 lines
Thanks. Would you be open to the approach from v2, where we place the common code in
btf_sort.cand compile it separately rather than including it directly?
No, the code is too trivial to try to reuse it. Kernel and user space libbpf code are run with different constraints, sharing it is necessary evil (like for BPF CO-RE relocations), not something that should be encouraged.
Quoted 2 lines
Quoted 2 lines
[...]
Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search
Quoted 45 lines · Andrii Nakryiko
Quoted 38 lines · Donglin Peng
Quoted 21 lines · Andrii Nakryiko
Quoted 19 lines · Donglin Peng
The previous commit implemented BTF sorting verification and binary search algorithm in libbpf. This patch enables this functionality in the kernel.
Cc Eduard Zingerman <[email protected]>Cc Alexei Starovoitov <[email protected]>Cc Andrii Nakryiko <[email protected]>Cc Alan Maguire <[email protected]>Cc Song Liu <[email protected]>Signed-off-by pengdonglin <[email protected]>Signed-off-by Donglin Peng <[email protected]>---
v2->v3:
- Includebtf_sort.cdirectly inbtf.cto reduce function call overhead--- kernel/bpf/btf.c | 34 ++++++++++++++++++---------------- 1 file changed, 18 insertions(+), 16 deletions(-)Quoted 13 lines
kernel/bpf/btf.c line 36
Quoted 9 lines
kernel/bpf/btf.c +1
-0@@ -33,6 +33,7 @@#include <net/sock.h> #include <net/xdp.h> #include "../tools/lib/bpf/relo_core.h" +#include "../tools/lib/bpf/btf_sort.h" I don't believe in code reuse for the sake of code reuse. This code sharing just makes everything more entangled and complicated. Reimplementing binary search is totally fine, IMO.
Quoted 4 lines
Thanks. Would you be open to the approach from v2, where we place the common code in
btf_sort.cand compile it separately rather than including it directly?
Quoted 4 lines
No, the code is too trivial to try to reuse it. Kernel and user space libbpf code are run with different constraints, sharing it is necessary evil (like for BPF CO-RE relocations), not something that should be encouraged.
Thanks, I will implement it separately as recommended.
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
[...]