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.
Cc: Eduard Zingerman <eddyz87@gmail.com>
Cc: Alexei Starovoitov <ast@kernel.org>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc: Alan Maguire <alan.maguire@oracle.com>
Cc: Song Liu <song@kernel.org>
Co-developed-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
---
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
diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index 18907f0fcf9f..d20bf81a21ce 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -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"
diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
index ccfd905f03df..3aac0a729bd5 100644
--- a/tools/lib/bpf/btf.h
+++ b/tools/lib/bpf/btf.h
@@ -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 {
diff --git a/tools/lib/bpf/btf_sort.c b/tools/lib/bpf/btf_sort.c
new file mode 100644
index 000000000000..553c5f5e61bd
--- /dev/null
+++ b/tools/lib/bpf/btf_sort.c
@@ -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;
+}
diff --git a/tools/lib/bpf/btf_sort.h b/tools/lib/bpf/btf_sort.h
new file mode 100644
index 000000000000..4dedc67286d9
--- /dev/null
+++ b/tools/lib/bpf/btf_sort.h
@@ -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
diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map
index 8ed8749907d4..8ce7b1d08650 100644
--- a/tools/lib/bpf/libbpf.map
+++ b/tools/lib/bpf/libbpf.map
@@ -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;
diff --git a/tools/lib/bpf/libbpf_version.h b/tools/lib/bpf/libbpf_version.h
index 99331e317dee..c446c0cd8cf9 100644
--- a/tools/lib/bpf/libbpf_version.h
+++ b/tools/lib/bpf/libbpf_version.h
@@ -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 */
--
2.34.1On Mon, Oct 27, 2025 at 6:54 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> 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.
>
> Cc: Eduard Zingerman <eddyz87@gmail.com>
> Cc: Alexei Starovoitov <ast@kernel.org>
> Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Cc: Alan Maguire <alan.maguire@oracle.com>
> Cc: Song Liu <song@kernel.org>
> Co-developed-by: Eduard Zingerman <eddyz87@gmail.com>
> Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> ---
> 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
>
This looks a bit over-engineered, let's try to simplify and have more
succinct implementation
pw-bot: cr
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 18907f0fcf9f..d20bf81a21ce 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -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;
> +}
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
> +
> /* 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);
nit: please avoid using underscore-prefixed names
> }
>
> 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)
[...]
> +/*
> + * 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
> +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.
> +{
> + 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);
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
> + if (err) {
> + pr_debug("btf_permute_remap_types failed: %s\n", errstr(err));
> + goto done;
> + }
> +
> +done:
> + btf_permute_free(p);
> + return libbpf_err(err);
> +}
> +
[...]
> +/*
> + * Shuffle BTF types.
> + *
> + * Rearranges types according to the permutation map in p->ids. The p->map
> + * array stores the mapping from original type IDs to new shuffled IDs,
> + * which is used in the next phase to update type references.
> + */
> +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;
What does "l" refer to in this name? It rings no bells for me...
> + for (i = 0; i < btf->nr_types; i++) {
this won't work with split BTF, no?
> + 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;
> +
[...]
> diff --git a/tools/lib/bpf/btf_sort.c b/tools/lib/bpf/btf_sort.c
> new file mode 100644
> index 000000000000..553c5f5e61bd
> --- /dev/null
> +++ b/tools/lib/bpf/btf_sort.c
why does this have to be a separate file? can't it be part of btf.c?
> @@ -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
I agree with Eduard, it seems like an overkill. For small BTFs this
all doesn't matter anyways.
> +
> +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);
> +}
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.
> +
> +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;
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
> + 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;
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.
> + } 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;
> + }
> + }
> + }
> +
[...]
On Wed, Oct 29, 2025 at 2:38 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, Oct 27, 2025 at 6:54 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > 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.
> >
> > Cc: Eduard Zingerman <eddyz87@gmail.com>
> > Cc: Alexei Starovoitov <ast@kernel.org>
> > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > Cc: Alan Maguire <alan.maguire@oracle.com>
> > Cc: Song Liu <song@kernel.org>
> > Co-developed-by: Eduard Zingerman <eddyz87@gmail.com>
> > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> > ---
> > 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
> >
>
> This looks a bit over-engineered, let's try to simplify and have more
> succinct implementation
Thanks, I will simplify it.
>
> pw-bot: cr
>
> > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > index 18907f0fcf9f..d20bf81a21ce 100644
> > --- a/tools/lib/bpf/btf.c
> > +++ b/tools/lib/bpf/btf.c
> > @@ -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;
> > +}
>
> 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
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)
> dedicated API for this. But please add it as a separate patch
>
> > +
> > /* 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);
>
> nit: please avoid using underscore-prefixed names
Thanks. I will fix it in the next version.
>
> > }
> >
> > 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.
>
> [...]
>
> > +/*
> > + * 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
Thanks, I will fix it in the next version.
>
> > +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.
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)
>
> > +{
> > + 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);
>
> 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.
> we need entire struct btf_permute to 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.
>
> > + if (err) {
> > + pr_debug("btf_permute_remap_types failed: %s\n", errstr(err));
> > + goto done;
> > + }
> > +
> > +done:
> > + btf_permute_free(p);
> > + return libbpf_err(err);
> > +}
> > +
>
> [...]
>
> > +/*
> > + * Shuffle BTF types.
> > + *
> > + * Rearranges types according to the permutation map in p->ids. The p->map
> > + * array stores the mapping from original type IDs to new shuffled IDs,
> > + * which is used in the next phase to update type references.
> > + */
> > +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;
>
> What does "l" refer to in this name? It rings no bells for me...
Would the name "nt" be acceptable?
>
> > + 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;
}
>
> > + 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;
> > +
>
> [...]
>
> > diff --git a/tools/lib/bpf/btf_sort.c b/tools/lib/bpf/btf_sort.c
> > new file mode 100644
> > index 000000000000..553c5f5e61bd
> > --- /dev/null
> > +++ b/tools/lib/bpf/btf_sort.c
>
> why 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/34a168e2-204d-47e2-9923-82d8ad645273@oracle.com/#t
https://lore.kernel.org/all/7f770a27-6ca6-463f-9145-5c795e0b3f40@oracle.com/
>
> > @@ -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
>
> I 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.
>
> > +
> > +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);
> > +}
>
> 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/20240608140835.965949-1-dolinux.peng@gmail.com/
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?
>
> > +
> > +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;
>
> 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.
>
> > + 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;
>
> 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.
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.
>
> > + } 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;
> > + }
> > + }
> > + }
> > +
>
> [...]
On 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?
> +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;
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.
> +
> + btf->nr_sorted_types = nr_sorted_types;
> +}
[...]
On Mon, Oct 27, 2025 at 12:06 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On 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?
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).
>
> > +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;
>
> 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.
>
> > +
> > + btf->nr_sorted_types = nr_sorted_types;
> > +}
>
> [...]
On Tue, Oct 28, 2025 at 3:06 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On 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?
>
> > +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;
>
> 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.
>
> > +
> > + btf->nr_sorted_types = nr_sorted_types;
> > +}
>
> [...]
On Mon, 2025-10-27 at 21:54 +0800, Donglin Peng wrote:
> 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.
>
> Cc: Eduard Zingerman <eddyz87@gmail.com>
> Cc: Alexei Starovoitov <ast@kernel.org>
> Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Cc: Alan Maguire <alan.maguire@oracle.com>
> Cc: Song Liu <song@kernel.org>
> Co-developed-by: Eduard Zingerman <eddyz87@gmail.com>
> Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> ---
> 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
> ---
Could you please split this in two commits:
- one handling BTF sortedness
- another handling btf__permute()
?
> 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
>
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 18907f0fcf9f..d20bf81a21ce 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -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;
Maybe allocate this on stack?
(Or just use btf_permute_opts directly and have 'map' as local variable?).
> + 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))) {
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.
> + __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"
> diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
> index ccfd905f03df..3aac0a729bd5 100644
> --- a/tools/lib/bpf/btf.h
> +++ b/tools/lib/bpf/btf.h
> @@ -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 {
> diff --git a/tools/lib/bpf/btf_sort.c b/tools/lib/bpf/btf_sort.c
> new file mode 100644
> index 000000000000..553c5f5e61bd
> --- /dev/null
> +++ b/tools/lib/bpf/btf_sort.c
> @@ -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;
> +}
> diff --git a/tools/lib/bpf/btf_sort.h b/tools/lib/bpf/btf_sort.h
> new file mode 100644
> index 000000000000..4dedc67286d9
> --- /dev/null
> +++ b/tools/lib/bpf/btf_sort.h
> @@ -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
> diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map
> index 8ed8749907d4..8ce7b1d08650 100644
> --- a/tools/lib/bpf/libbpf.map
> +++ b/tools/lib/bpf/libbpf.map
> @@ -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.
> + global:
> + btf__start_id;
> + btf__permute;
> +} LIBBPF_1.7.0;
> diff --git a/tools/lib/bpf/libbpf_version.h b/tools/lib/bpf/libbpf_version.h
> index 99331e317dee..c446c0cd8cf9 100644
> --- a/tools/lib/bpf/libbpf_version.h
> +++ b/tools/lib/bpf/libbpf_version.h
> @@ -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 */
On Tue, Oct 28, 2025 at 2:40 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2025-10-27 at 21:54 +0800, Donglin Peng wrote:
> > 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.
> >
> > Cc: Eduard Zingerman <eddyz87@gmail.com>
> > Cc: Alexei Starovoitov <ast@kernel.org>
> > Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > Cc: Alan Maguire <alan.maguire@oracle.com>
> > Cc: Song Liu <song@kernel.org>
> > Co-developed-by: Eduard Zingerman <eddyz87@gmail.com>
> > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> > ---
> > 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
> > ---
>
>
> Could you please split this in two commits:
> - one handling BTF sortedness
> - another handling btf__permute()
> ?
Thanks, I will split it in the next version.
>
> > 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
> >
> > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > index 18907f0fcf9f..d20bf81a21ce 100644
> > --- a/tools/lib/bpf/btf.c
> > +++ b/tools/lib/bpf/btf.c
> > @@ -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;
>
> Maybe allocate this on stack?
Thanks, I will fix it in the next version.
> (Or just use btf_permute_opts directly 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`.
>
> > + 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))) {
>
> 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.
Good catch, thanks. I will fix it in the next version.
>
> > + __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"
> > diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
> > index ccfd905f03df..3aac0a729bd5 100644
> > --- a/tools/lib/bpf/btf.h
> > +++ b/tools/lib/bpf/btf.h
> > @@ -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 {
> > diff --git a/tools/lib/bpf/btf_sort.c b/tools/lib/bpf/btf_sort.c
> > new file mode 100644
> > index 000000000000..553c5f5e61bd
> > --- /dev/null
> > +++ b/tools/lib/bpf/btf_sort.c
> > @@ -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;
> > +}
> > diff --git a/tools/lib/bpf/btf_sort.h b/tools/lib/bpf/btf_sort.h
> > new file mode 100644
> > index 000000000000..4dedc67286d9
> > --- /dev/null
> > +++ b/tools/lib/bpf/btf_sort.h
> > @@ -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
> > diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map
> > index 8ed8749907d4..8ce7b1d08650 100644
> > --- a/tools/lib/bpf/libbpf.map
> > +++ b/tools/lib/bpf/libbpf.map
> > @@ -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.
>
> > + global:
> > + btf__start_id;
> > + btf__permute;
> > +} LIBBPF_1.7.0;
> > diff --git a/tools/lib/bpf/libbpf_version.h b/tools/lib/bpf/libbpf_version.h
> > index 99331e317dee..c446c0cd8cf9 100644
> > --- a/tools/lib/bpf/libbpf_version.h
> > +++ b/tools/lib/bpf/libbpf_version.h
> > @@ -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 */
```
commit 1fada9fa20ae7a48b4ba2dd189d4d2dd29878ad2
Author: Donglin Peng <dolinux.peng@gmail.com>
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
© 2016 - 2026 Red Hat, Inc.