* [RFC PATCH v3 0/3] Significantly Improve BTF Type Lookup Performance
@ 2025-10-27 13:54 Donglin Peng
2025-10-27 13:54 ` [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups Donglin Peng
` (2 more replies)
0 siblings, 3 replies; 19+ messages in thread
From: Donglin Peng @ 2025-10-27 13:54 UTC (permalink / raw)
To: ast; +Cc: linux-kernel, bpf, Donglin Peng
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/20251020093941.548058-1-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
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
--
2.34.1
^ permalink raw reply [flat|nested] 19+ messages in thread
* [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
2025-10-27 13:54 [RFC PATCH v3 0/3] Significantly Improve BTF Type Lookup Performance Donglin Peng
@ 2025-10-27 13:54 ` Donglin Peng
2025-10-27 14:20 ` bot+bpf-ci
` (3 more replies)
2025-10-27 13:54 ` [RFC PATCH v3 2/3] selftests/bpf: add tests for BTF type permutation Donglin Peng
2025-10-27 13:54 ` [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search Donglin Peng
2 siblings, 4 replies; 19+ messages in thread
From: Donglin Peng @ 2025-10-27 13:54 UTC (permalink / raw)
To: ast
Cc: linux-kernel, bpf, Donglin Peng, Eduard Zingerman,
Andrii Nakryiko, Alan Maguire, Song Liu, pengdonglin
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.1
^ permalink raw reply related [flat|nested] 19+ messages in thread
* [RFC PATCH v3 2/3] selftests/bpf: add tests for BTF type permutation
2025-10-27 13:54 [RFC PATCH v3 0/3] Significantly Improve BTF Type Lookup Performance Donglin Peng
2025-10-27 13:54 ` [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups Donglin Peng
@ 2025-10-27 13:54 ` Donglin Peng
2025-10-27 18:53 ` Eduard Zingerman
2025-10-27 13:54 ` [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search Donglin Peng
2 siblings, 1 reply; 19+ messages in thread
From: Donglin Peng @ 2025-10-27 13:54 UTC (permalink / raw)
To: ast
Cc: linux-kernel, bpf, Donglin Peng, Eduard Zingerman,
Andrii Nakryiko, Alan Maguire, Song Liu, pengdonglin
Verify that BTF type permutation functionality works correctly.
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>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
---
tools/testing/selftests/bpf/prog_tests/btf.c | 109 ++++++++++++++++---
1 file changed, 94 insertions(+), 15 deletions(-)
diff --git a/tools/testing/selftests/bpf/prog_tests/btf.c b/tools/testing/selftests/bpf/prog_tests/btf.c
index 8a9ba4292109..0688449613d4 100644
--- a/tools/testing/selftests/bpf/prog_tests/btf.c
+++ b/tools/testing/selftests/bpf/prog_tests/btf.c
@@ -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();
}
--
2.34.1
^ permalink raw reply related [flat|nested] 19+ messages in thread
* [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search
2025-10-27 13:54 [RFC PATCH v3 0/3] Significantly Improve BTF Type Lookup Performance Donglin Peng
2025-10-27 13:54 ` [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups Donglin Peng
2025-10-27 13:54 ` [RFC PATCH v3 2/3] selftests/bpf: add tests for BTF type permutation Donglin Peng
@ 2025-10-27 13:54 ` Donglin Peng
2025-10-27 19:55 ` Alexei Starovoitov
2025-10-28 18:40 ` Andrii Nakryiko
2 siblings, 2 replies; 19+ messages in thread
From: Donglin Peng @ 2025-10-27 13:54 UTC (permalink / raw)
To: ast
Cc: linux-kernel, bpf, Donglin Peng, Eduard Zingerman,
Andrii Nakryiko, Alan Maguire, Song Liu, pengdonglin
The previous commit implemented BTF sorting verification and binary
search algorithm in libbpf. This patch enables this functionality in
the kernel.
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>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
---
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(-)
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 0de8fc8a0e0b..df258815a6ca 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -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 *name
if (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"
--
2.34.1
^ permalink raw reply related [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
2025-10-27 13:54 ` [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups Donglin Peng
@ 2025-10-27 14:20 ` bot+bpf-ci
2025-10-27 18:40 ` Eduard Zingerman
` (2 subsequent siblings)
3 siblings, 0 replies; 19+ messages in thread
From: bot+bpf-ci @ 2025-10-27 14:20 UTC (permalink / raw)
To: dolinux.peng, ast
Cc: linux-kernel, bpf, dolinux.peng, eddyz87, andrii.nakryiko,
alan.maguire, song, pengdonglin, ast, andrii, daniel, martin.lau,
eddyz87, yonghong.song, clm, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 2441 bytes --]
```
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
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
2025-10-27 13:54 ` [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups Donglin Peng
2025-10-27 14:20 ` bot+bpf-ci
@ 2025-10-27 18:40 ` Eduard Zingerman
2025-10-28 2:15 ` Donglin Peng
2025-10-27 19:06 ` Eduard Zingerman
2025-10-28 18:38 ` Andrii Nakryiko
3 siblings, 1 reply; 19+ messages in thread
From: Eduard Zingerman @ 2025-10-27 18:40 UTC (permalink / raw)
To: Donglin Peng, ast
Cc: linux-kernel, bpf, Andrii Nakryiko, Alan Maguire, Song Liu,
pengdonglin
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 */
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 2/3] selftests/bpf: add tests for BTF type permutation
2025-10-27 13:54 ` [RFC PATCH v3 2/3] selftests/bpf: add tests for BTF type permutation Donglin Peng
@ 2025-10-27 18:53 ` Eduard Zingerman
2025-10-28 2:23 ` Donglin Peng
0 siblings, 1 reply; 19+ messages in thread
From: Eduard Zingerman @ 2025-10-27 18:53 UTC (permalink / raw)
To: Donglin Peng, ast
Cc: linux-kernel, bpf, Andrii Nakryiko, Alan Maguire, Song Liu,
pengdonglin
On Mon, 2025-10-27 at 21:54 +0800, Donglin Peng wrote:
> Verify that BTF type permutation functionality works correctly.
>
> 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>
> Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> ---
Do we need a test case for split btf?
We probably do, as there is index arithmetic etc.
[...]
> @@ -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"),
> + },
Nit: I think that this test is a bit too large.
Having fewer decl_tags would still test what we want to test.
> + .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,
> + },
> +},
> };
[...]
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
2025-10-27 13:54 ` [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups Donglin Peng
2025-10-27 14:20 ` bot+bpf-ci
2025-10-27 18:40 ` Eduard Zingerman
@ 2025-10-27 19:06 ` Eduard Zingerman
2025-10-28 2:18 ` Donglin Peng
2025-10-28 18:15 ` Andrii Nakryiko
2025-10-28 18:38 ` Andrii Nakryiko
3 siblings, 2 replies; 19+ messages in thread
From: Eduard Zingerman @ 2025-10-27 19:06 UTC (permalink / raw)
To: Donglin Peng, ast, Andrii Nakryiko
Cc: linux-kernel, bpf, Alan Maguire, Song Liu, pengdonglin
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;
> +}
[...]
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search
2025-10-27 13:54 ` [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search Donglin Peng
@ 2025-10-27 19:55 ` Alexei Starovoitov
2025-10-29 1:57 ` Donglin Peng
2025-10-28 18:40 ` Andrii Nakryiko
1 sibling, 1 reply; 19+ messages in thread
From: Alexei Starovoitov @ 2025-10-27 19:55 UTC (permalink / raw)
To: Donglin Peng
Cc: Alexei Starovoitov, LKML, bpf, Eduard Zingerman, Andrii Nakryiko,
Alan Maguire, Song Liu, pengdonglin
On Mon, Oct 27, 2025 at 6:54 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> +
> +/*
> + * 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
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
2025-10-27 18:40 ` Eduard Zingerman
@ 2025-10-28 2:15 ` Donglin Peng
0 siblings, 0 replies; 19+ messages in thread
From: Donglin Peng @ 2025-10-28 2:15 UTC (permalink / raw)
To: Eduard Zingerman
Cc: ast, linux-kernel, bpf, Andrii Nakryiko, Alan Maguire, Song Liu,
pengdonglin
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 */
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
2025-10-27 19:06 ` Eduard Zingerman
@ 2025-10-28 2:18 ` Donglin Peng
2025-10-28 18:15 ` Andrii Nakryiko
1 sibling, 0 replies; 19+ messages in thread
From: Donglin Peng @ 2025-10-28 2:18 UTC (permalink / raw)
To: Eduard Zingerman
Cc: ast, Andrii Nakryiko, linux-kernel, bpf, Alan Maguire, Song Liu,
pengdonglin
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;
> > +}
>
> [...]
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 2/3] selftests/bpf: add tests for BTF type permutation
2025-10-27 18:53 ` Eduard Zingerman
@ 2025-10-28 2:23 ` Donglin Peng
0 siblings, 0 replies; 19+ messages in thread
From: Donglin Peng @ 2025-10-28 2:23 UTC (permalink / raw)
To: Eduard Zingerman
Cc: ast, linux-kernel, bpf, Andrii Nakryiko, Alan Maguire, Song Liu,
pengdonglin
On Tue, Oct 28, 2025 at 2:53 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2025-10-27 at 21:54 +0800, Donglin Peng wrote:
> > Verify that BTF type permutation functionality works correctly.
> >
> > 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>
> > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> > ---
>
> 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.
>
> [...]
>
> > @@ -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"),
> > + },
>
> Nit: I think that this test is a bit too large.
> Having fewer decl_tags would still test what we want to test.
Thanks, I agree, I will clean it up.
>
> > + .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,
> > + },
> > +},
> > };
>
> [...]
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
2025-10-27 19:06 ` Eduard Zingerman
2025-10-28 2:18 ` Donglin Peng
@ 2025-10-28 18:15 ` Andrii Nakryiko
1 sibling, 0 replies; 19+ messages in thread
From: Andrii Nakryiko @ 2025-10-28 18:15 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Donglin Peng, ast, linux-kernel, bpf, Alan Maguire, Song Liu,
pengdonglin
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;
> > +}
>
> [...]
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
2025-10-27 13:54 ` [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups Donglin Peng
` (2 preceding siblings ...)
2025-10-27 19:06 ` Eduard Zingerman
@ 2025-10-28 18:38 ` Andrii Nakryiko
2025-10-29 5:04 ` Donglin Peng
3 siblings, 1 reply; 19+ messages in thread
From: Andrii Nakryiko @ 2025-10-28 18:38 UTC (permalink / raw)
To: Donglin Peng
Cc: ast, linux-kernel, bpf, Eduard Zingerman, Alan Maguire, Song Liu,
pengdonglin
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
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;
> + }
> + }
> + }
> +
[...]
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search
2025-10-27 13:54 ` [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search Donglin Peng
2025-10-27 19:55 ` Alexei Starovoitov
@ 2025-10-28 18:40 ` Andrii Nakryiko
2025-10-29 2:03 ` Donglin Peng
1 sibling, 1 reply; 19+ messages in thread
From: Andrii Nakryiko @ 2025-10-28 18:40 UTC (permalink / raw)
To: Donglin Peng
Cc: ast, linux-kernel, bpf, Eduard Zingerman, Alan Maguire, Song Liu,
pengdonglin
On Mon, Oct 27, 2025 at 6:54 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> The previous commit implemented BTF sorting verification and binary
> search algorithm in libbpf. This patch enables this functionality in
> the kernel.
>
> 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>
> Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> ---
> 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(-)
>
> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> index 0de8fc8a0e0b..df258815a6ca 100644
> --- a/kernel/bpf/btf.c
> +++ b/kernel/bpf/btf.c
> @@ -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.
[...]
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search
2025-10-27 19:55 ` Alexei Starovoitov
@ 2025-10-29 1:57 ` Donglin Peng
0 siblings, 0 replies; 19+ messages in thread
From: Donglin Peng @ 2025-10-29 1:57 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Alexei Starovoitov, LKML, bpf, Eduard Zingerman, Andrii Nakryiko,
Alan Maguire, Song Liu, pengdonglin
On Tue, Oct 28, 2025 at 3:56 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Mon, Oct 27, 2025 at 6:54 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > +
> > +/*
> > + * 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.
>
> Don't do it on libbpf side either.
Yes.
>
> pw-bot: cr
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search
2025-10-28 18:40 ` Andrii Nakryiko
@ 2025-10-29 2:03 ` Donglin Peng
2025-10-31 16:50 ` Andrii Nakryiko
0 siblings, 1 reply; 19+ messages in thread
From: Donglin Peng @ 2025-10-29 2:03 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: ast, linux-kernel, bpf, Eduard Zingerman, Alan Maguire, Song Liu,
pengdonglin
On Wed, Oct 29, 2025 at 2:40 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, Oct 27, 2025 at 6:54 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > The previous commit implemented BTF sorting verification and binary
> > search algorithm in libbpf. This patch enables this functionality in
> > the kernel.
> >
> > 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>
> > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> > ---
> > 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(-)
> >
> > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > index 0de8fc8a0e0b..df258815a6ca 100644
> > --- a/kernel/bpf/btf.c
> > +++ b/kernel/bpf/btf.c
> > @@ -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?
>
> [...]
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups
2025-10-28 18:38 ` Andrii Nakryiko
@ 2025-10-29 5:04 ` Donglin Peng
0 siblings, 0 replies; 19+ messages in thread
From: Donglin Peng @ 2025-10-29 5:04 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: ast, linux-kernel, bpf, Eduard Zingerman, Alan Maguire, Song Liu,
pengdonglin
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;
> > + }
> > + }
> > + }
> > +
>
> [...]
^ permalink raw reply [flat|nested] 19+ messages in thread
* Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search
2025-10-29 2:03 ` Donglin Peng
@ 2025-10-31 16:50 ` Andrii Nakryiko
0 siblings, 0 replies; 19+ messages in thread
From: Andrii Nakryiko @ 2025-10-31 16:50 UTC (permalink / raw)
To: Donglin Peng
Cc: ast, linux-kernel, bpf, Eduard Zingerman, Alan Maguire, Song Liu,
pengdonglin
On Tue, Oct 28, 2025 at 7:03 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> On Wed, Oct 29, 2025 at 2:40 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Mon, Oct 27, 2025 at 6:54 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > >
> > > The previous commit implemented BTF sorting verification and binary
> > > search algorithm in libbpf. This patch enables this functionality in
> > > the kernel.
> > >
> > > 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>
> > > Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> > > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> > > ---
> > > 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(-)
> > >
> > > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > > index 0de8fc8a0e0b..df258815a6ca 100644
> > > --- a/kernel/bpf/btf.c
> > > +++ b/kernel/bpf/btf.c
> > > @@ -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?
>
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.
> >
> > [...]
^ permalink raw reply [flat|nested] 19+ messages in thread
end of thread, other threads:[~2025-10-31 16:51 UTC | newest]
Thread overview: 19+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-10-27 13:54 [RFC PATCH v3 0/3] Significantly Improve BTF Type Lookup Performance Donglin Peng
2025-10-27 13:54 ` [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups Donglin Peng
2025-10-27 14:20 ` bot+bpf-ci
2025-10-27 18:40 ` Eduard Zingerman
2025-10-28 2:15 ` Donglin Peng
2025-10-27 19:06 ` Eduard Zingerman
2025-10-28 2:18 ` Donglin Peng
2025-10-28 18:15 ` Andrii Nakryiko
2025-10-28 18:38 ` Andrii Nakryiko
2025-10-29 5:04 ` Donglin Peng
2025-10-27 13:54 ` [RFC PATCH v3 2/3] selftests/bpf: add tests for BTF type permutation Donglin Peng
2025-10-27 18:53 ` Eduard Zingerman
2025-10-28 2:23 ` Donglin Peng
2025-10-27 13:54 ` [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search Donglin Peng
2025-10-27 19:55 ` Alexei Starovoitov
2025-10-29 1:57 ` Donglin Peng
2025-10-28 18:40 ` Andrii Nakryiko
2025-10-29 2:03 ` Donglin Peng
2025-10-31 16:50 ` Andrii Nakryiko
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).