Skip to contentSkip to conversation

Significantly Improve BTF Type Lookup Performance

RFC PATCH In review Donglin Peng 5 participants 20 messages Oct 27, 2025 – Nov 3, 2025

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

v3 cover Significantly Improve BTF Type Lookup Performance

The funcgraph-args feature frequently calls btf_find_by_name_kind(), which currently uses a linear search algorithm. With large BTF datasets like vmlinux
(containing over 80,000 named types), this causes significant performance overhead.

This patch series introduces a new libbpf interface btf__permute(), which allows tools like pahole to sort BTF types by kind and name. After generating a sorted type ID array, these tools can invoke the new interface to perform in-place BTF sorting. During BTF parsing, btf_check_sorted() verifies whether the types are sorted.

Performance testing shows dramatic improvement after sorting by kind and name, as demonstrated below:

# echo 1 > options/funcgraph-args
# echo function_graph > current_tracer

Before:

# time cat trace | wc -l
58098
real    0m7.514s
user    0m0.010s
sys     0m7.374s

After:

# time cat trace | wc -l
58837
real    0m0.371s
user    0m0.000s
sys     0m0.383s

This represents about 20x performance improvement for BTF type lookups.

v2:
https://lore.kernel.org/all/[email protected]/

v2 -> v3:
- Remove sorting logic from libbpf and provide a generic btf__permute() interface
- Remove the search direction patch since sorted lookup provides sufficient performance and changing search order could cause conflicts between BTF and base BTF
- Include btf_sort.c directly in btf.c to reduce function call overhead

Donglin Peng (3):
btf: implement BTF type sorting for accelerated lookups selftests/bpf: add tests for BTF type permutation
btf: Reuse libbpf code for BTF type sorting verification and binary
search

 kernel/bpf/btf.c                             |  34 +--
 tools/lib/bpf/btf.c                          | 262 +++++++++++++++++--
 tools/lib/bpf/btf.h                          |  17 ++
 tools/lib/bpf/btf_sort.c                     | 174 ++++++++++++
 tools/lib/bpf/btf_sort.h                     |  11 +
 tools/lib/bpf/libbpf.map                     |   6 +
 tools/lib/bpf/libbpf_version.h               |   2 +-
 tools/testing/selftests/bpf/prog_tests/btf.c | 109 ++++++--
 8 files changed, 559 insertions(+), 56 deletions(-)
 create mode 100644 tools/lib/bpf/btf_sort.c
 create mode 100644 tools/lib/bpf/btf_sort.h
Signature · 1 line
2.34.1
#1 lore raw

RFC PATCH v3 1/3 btf: implement BTF type sorting for accelerated lookups

This patch introduces a new libbpf interface btf__permute() to reorganize BTF types according to a provided mapping. The BTF lookup mechanism is enhanced with binary search capability, significantly improving lookup performance for large type sets.

The pahole tool can invoke this interface with a sorted type ID array, enabling binary search in both user space and kernel. To share core logic between kernel and libbpf, common sorting functionality is implemented in a new btf_sort.c source file.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>

---
v2->v3:
- Remove sorting logic from libbpf and provide a generic btf__permute() interface
- Remove the search direction patch since sorted lookup provides sufficient performance and changing search order could cause conflicts between BTF and base BTF
- Include btf_sort.c directly in btf.c to reduce function call overhead

---
 tools/lib/bpf/btf.c            | 262 ++++++++++++++++++++++++++++++---
 tools/lib/bpf/btf.h            |  17 +++
 tools/lib/bpf/btf_sort.c       | 174 ++++++++++++++++++++++
 tools/lib/bpf/btf_sort.h       |  11 ++
 tools/lib/bpf/libbpf.map       |   6 +
 tools/lib/bpf/libbpf_version.h |   2 +-
 6 files changed, 447 insertions(+), 25 deletions(-)
 create mode 100644 tools/lib/bpf/btf_sort.c
 create mode 100644 tools/lib/bpf/btf_sort.h
tools/lib/bpf/btf.c +238 -24
index 18907f0fcf9f..d20bf81a21ce 100644
@@ -23,6 +23,7 @@
 #include "libbpf_internal.h"
 #include "hashmap.h"
 #include "strset.h"
+#include "btf_sort.h"
 
 #define BTF_MAX_NR_TYPES 0x7fffffffU
 #define BTF_MAX_STR_OFFSET 0x7fffffffU
@@ -92,6 +93,12 @@ struct btf {
 	 *   - for split BTF counts number of types added on top of base BTF.
 	 */
 	__u32 nr_types;
+	/* number of sorted and named types in this BTF instance:
+	 *   - doesn't include special [0] void type;
+	 *   - for split BTF counts number of sorted and named types added on
+	 *     top of base BTF.
+	 */
+	__u32 nr_sorted_types;
 	/* if not NULL, points to the base BTF on top of which the current
 	 * split BTF is based
 	 */
@@ -624,6 +631,11 @@ const struct btf *btf__base_btf(const struct btf *btf)
 	return btf->base_btf;
 }
 
+__u32 btf__start_id(const struct btf *btf)
+{
+	return btf->start_id;
+}
+
 /* internal helper returning non-const pointer to a type */
 struct btf_type *btf_type_by_id(const struct btf *btf, __u32 type_id)
 {
@@ -915,38 +927,16 @@ __s32 btf__find_by_name(const struct btf *btf, const char *type_name)
 	return libbpf_err(-ENOENT);
 }
 
-static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
-				   const char *type_name, __u32 kind)
-{
-	__u32 i, nr_types = btf__type_cnt(btf);
-
-	if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
-		return 0;
-
-	for (i = start_id; i < nr_types; i++) {
-		const struct btf_type *t = btf__type_by_id(btf, i);
-		const char *name;
-
-		if (btf_kind(t) != kind)
-			continue;
-		name = btf__name_by_offset(btf, t->name_off);
-		if (name && !strcmp(type_name, name))
-			return i;
-	}
-
-	return libbpf_err(-ENOENT);
-}
-
 __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
 				 __u32 kind)
 {
-	return btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
+	return _btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
 }
 
 __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name,
 			     __u32 kind)
 {
-	return btf_find_by_name_kind(btf, 1, type_name, kind);
+	return _btf_find_by_name_kind(btf, 1, type_name, kind);
 }
 
 static bool btf_is_modifiable(const struct btf *btf)
@@ -1091,6 +1081,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
 	err = err ?: btf_sanity_check(btf);
 	if (err)
 		goto done;
+	btf_check_sorted(btf, btf->start_id);
 
 done:
 	if (err) {
@@ -1715,6 +1706,8 @@ static void btf_invalidate_raw_data(struct btf *btf)
 		free(btf->raw_data_swapped);
 		btf->raw_data_swapped = NULL;
 	}
+	if (btf->nr_sorted_types)
+		btf->nr_sorted_types = 0;
 }
 
 /* Ensure BTF is ready to be modified (by splitting into a three memory
@@ -5829,3 +5822,224 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf)
 		btf->owns_base = false;
 	return libbpf_err(err);
 }
+
+struct btf_permute;
+
+static struct btf_permute *btf_permute_new(struct btf *btf, const struct btf_permute_opts *opts);
+static void btf_permute_free(struct btf_permute *p);
+static int btf_permute_shuffle_types(struct btf_permute *p);
+static int btf_permute_remap_types(struct btf_permute *p);
+static int btf_permute_remap_type_id(__u32 *type_id, void *ctx);
+
+/*
+ * Permute BTF types in-place using the ID mapping from btf_permute_opts->ids.
+ * After permutation, all type ID references are updated to reflect the new
+ * ordering. If a struct btf_ext (representing '.BTF.ext' section) is provided,
+ * type ID references within the BTF extension data are also updated.
+ */
+int btf__permute(struct btf *btf, const struct btf_permute_opts *opts)
+{
+	struct btf_permute *p;
+	int err = 0;
+
+	if (!OPTS_VALID(opts, btf_permute_opts))
+		return libbpf_err(-EINVAL);
+
+	p = btf_permute_new(btf, opts);
+	if (!p) {
+		pr_debug("btf_permute_new failed: %ld\n", PTR_ERR(p));
+		return libbpf_err(-EINVAL);
+	}
+
+	if (btf_ensure_modifiable(btf)) {
+		err = -ENOMEM;
+		goto done;
+	}
+
+	err = btf_permute_shuffle_types(p);
+	if (err < 0) {
+		pr_debug("btf_permute_shuffle_types failed: %s\n", errstr(err));
+		goto done;
+	}
+	err = btf_permute_remap_types(p);
+	if (err) {
+		pr_debug("btf_permute_remap_types failed: %s\n", errstr(err));
+		goto done;
+	}
+
+done:
+	btf_permute_free(p);
+	return libbpf_err(err);
+}
+
+struct btf_permute {
+	/* .BTF section to be permuted in-place */
+	struct btf *btf;
+	struct btf_ext *btf_ext;
+	/* Array of type IDs used for permutation. The array length must equal
+	 * the number of types in the BTF being permuted, excluding the special
+	 * void type at ID 0. For split BTF, the length corresponds to the
+	 * number of types added on top of the base BTF.
+	 */
+	__u32 *ids;
+	/* Array of type IDs used to map from original type ID to a new permuted
+	 * type ID, its length equals to the above ids */
+	__u32 *map;
+};
+
+static struct btf_permute *btf_permute_new(struct btf *btf, const struct btf_permute_opts *opts)
+{
+	struct btf_permute *p = calloc(1, sizeof(struct btf_permute));
+	__u32 *map;
+	int err = 0;
+
+	if (!p)
+		return ERR_PTR(-ENOMEM);
+
+	p->btf = btf;
+	p->btf_ext = OPTS_GET(opts, btf_ext, NULL);
+	p->ids = OPTS_GET(opts, ids, NULL);
+	if (!p->ids) {
+		err = -EINVAL;
+		goto done;
+	}
+
+	map = calloc(btf->nr_types, sizeof(*map));
+	if (!map) {
+		err = -ENOMEM;
+		goto done;
+	}
+	p->map = map;
+
+done:
+	if (err) {
+		btf_permute_free(p);
+		return ERR_PTR(err);
+	}
+
+	return p;
+}
+
+static void btf_permute_free(struct btf_permute *p)
+{
+	if (p->map) {
+		free(p->map);
+		p->map = NULL;
+	}
+	free(p);
+}
+
+/*
+ * Shuffle BTF types.
+ *
+ * Rearranges types according to the permutation map in p->ids. The p->map
+ * array stores the mapping from original type IDs to new shuffled IDs,
+ * which is used in the next phase to update type references.
+ */
+static int btf_permute_shuffle_types(struct btf_permute *p)
+{
+	struct btf *btf = p->btf;
+	const struct btf_type *t;
+	__u32 *new_offs = NULL;
+	void *l, *new_types = NULL;
+	int i, id, len, err;
+
+	new_offs = calloc(btf->nr_types, sizeof(*new_offs));
+	new_types = calloc(btf->hdr->type_len, 1);
+	if (!new_types || !new_offs) {
+		err = -ENOMEM;
+		goto out_err;
+	}
+
+	l = new_types;
+	for (i = 0; i < btf->nr_types; i++) {
+		id = p->ids[i];
+		t = btf__type_by_id(btf, id);
+		len = btf_type_size(t);
+		memcpy(l, t, len);
+		new_offs[i] = l - new_types;
+		p->map[id - btf->start_id] = btf->start_id + i;
+		l += len;
+	}
+
+	free(btf->types_data);
+	free(btf->type_offs);
+	btf->types_data = new_types;
+	btf->type_offs = new_offs;
+	return 0;
+
+out_err:
+	return err;
+}
+
+/*
+ * Remap referenced type IDs into permuted type IDs.
+ *
+ * After BTF types are permuted, their final type IDs may differ from original
+ * ones. The map from original to a corresponding permuted type ID is stored
+ * in btf_permute->map and is populated during shuffle phase. During remapping
+ * phase we are rewriting all type IDs  referenced from any BTF type (e.g.,
+ * struct fields, func proto args, etc) to their final deduped type IDs.
+ */
+static int btf_permute_remap_types(struct btf_permute *p)
+{
+	struct btf *btf = p->btf;
+	int i, r;
+
+	for (i = 0; i < btf->nr_types; i++) {
+		struct btf_type *t = btf_type_by_id(btf, btf->start_id + i);
+		struct btf_field_iter it;
+		__u32 *type_id;
+
+		r = btf_field_iter_init(&it, t, BTF_FIELD_ITER_IDS);
+		if (r)
+			return r;
+
+		while ((type_id = btf_field_iter_next(&it))) {
+			__u32 new_id = *type_id;
+
+			/* skip references that point into the base BTF */
+			if (new_id < btf->start_id)
+				continue;
+
+			new_id = p->map[new_id - btf->start_id];
+			if (new_id > BTF_MAX_NR_TYPES)
+				return -EINVAL;
+
+			*type_id = new_id;
+		}
+	}
+
+	if (!p->btf_ext)
+		return 0;
+
+	r = btf_ext_visit_type_ids(p->btf_ext, btf_permute_remap_type_id, p);
+	if (r)
+		return r;
+
+	return 0;
+}
+
+static int btf_permute_remap_type_id(__u32 *type_id, void *ctx)
+{
+	struct btf_permute *p = ctx;
+	__u32 new_type_id = *type_id;
+
+	/* skip references that point into the base BTF */
+	if (new_type_id < p->btf->start_id)
+		return 0;
+
+	new_type_id = p->map[*type_id - p->btf->start_id];
+	if (new_type_id > BTF_MAX_NR_TYPES)
+		return -EINVAL;
+
+	*type_id = new_type_id;
+	return 0;
+}
+
+/*
+ * btf_sort.c is included directly to avoid function call overhead
+ * when accessing BTF private data, as this file is shared between
+ * libbpf and kernel and may be called frequently.
+ */
+#include "./btf_sort.c"
tools/lib/bpf/btf.h +17 -0
index ccfd905f03df..3aac0a729bd5 100644
@@ -149,6 +149,7 @@ LIBBPF_API __s32 btf__find_by_name_kind(const struct btf *btf,
 					const char *type_name, __u32 kind);
 LIBBPF_API __u32 btf__type_cnt(const struct btf *btf);
 LIBBPF_API const struct btf *btf__base_btf(const struct btf *btf);
+LIBBPF_API __u32 btf__start_id(const struct btf *btf);
 LIBBPF_API const struct btf_type *btf__type_by_id(const struct btf *btf,
 						  __u32 id);
 LIBBPF_API size_t btf__pointer_size(const struct btf *btf);
@@ -273,6 +274,22 @@ LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts);
  */
 LIBBPF_API int btf__relocate(struct btf *btf, const struct btf *base_btf);
 
+struct btf_permute_opts {
+	size_t sz;
+	/* optional .BTF.ext info along the main BTF info */
+	struct btf_ext *btf_ext;
+	/* Array of type IDs used for permutation. The array length must equal
+	 * the number of types in the BTF being permuted, excluding the special
+	 * void type at ID 0. For split BTF, the length corresponds to the
+	 * number of types added on top of the base BTF.
+	 */
+	__u32 *ids;
+	size_t :0;
+};
+#define btf_permute_opts__last_field ids
+
+LIBBPF_API int btf__permute(struct btf *btf, const struct btf_permute_opts *opts);
+
 struct btf_dump;
 
 struct btf_dump_opts {
tools/lib/bpf/btf_sort.c new file +174 -0

174 lines not on this page · raw message

tools/lib/bpf/btf_sort.h new file +11 -0
new file mode 100644
index 000000000000..4dedc67286d9
@@ -0,0 +1,11 @@
+/* SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) */
+/* Copyright (c) 2025 Xiaomi */
+
+#ifndef __BTF_SORT_H
+#define __BTF_SORT_H
+
+static __s32 _btf_find_by_name_kind(const struct btf *btf, int start_id, const char *type_name, __u32 kind);
+static int btf_compare_type_kinds_names(const void *a, const void *b, void *priv);
+static void btf_check_sorted(struct btf *btf, int start_id);
+
+#endif
tools/lib/bpf/libbpf.map +6 -0
index 8ed8749907d4..8ce7b1d08650 100644
@@ -452,3 +452,9 @@ LIBBPF_1.7.0 {
 		bpf_map__set_exclusive_program;
 		bpf_map__exclusive_program;
 } LIBBPF_1.6.0;
+
+LIBBPF_1.8.0 {
+	global:
+		btf__start_id;
+		btf__permute;
+} LIBBPF_1.7.0;
tools/lib/bpf/libbpf_version.h +1 -1
index 99331e317dee..c446c0cd8cf9 100644
@@ -4,6 +4,6 @@
 #define __LIBBPF_VERSION_H
 
 #define LIBBPF_MAJOR_VERSION 1
-#define LIBBPF_MINOR_VERSION 7
+#define LIBBPF_MINOR_VERSION 8
 
 #endif /* __LIBBPF_VERSION_H */
Signature · 1 line
2.34.1
#2 lore raw

Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups

AI reviewed your patch. Please fix the bug or email reply why it's not a bug. See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
```
commit 1fada9fa20ae7a48b4ba2dd189d4d2dd29878ad2
Author: Donglin Peng <[email protected]>

btf: implement BTF type sorting for accelerated lookups

This patch introduces a new libbpf interface btf__permute() to reorganize
BTF types according to a provided mapping, with binary search capability
for accelerated lookups in large type sets.

> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 18907f0fc..d20bf81a2 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c

[ ... ]

> +/*
> + * Shuffle BTF types.
> + *
> + * Rearranges types according to the permutation map in p->ids. The p->map
> + * array stores the mapping from original type IDs to new shuffled IDs,
> + * which is used in the next phase to update type references.
> + */
> +static int btf_permute_shuffle_types(struct btf_permute *p)
> +{
> +	struct btf *btf = p->btf;
> +	const struct btf_type *t;
> +	__u32 *new_offs = NULL;
> +	void *l, *new_types = NULL;
> +	int i, id, len, err;
> +
> +	new_offs = calloc(btf->nr_types, sizeof(*new_offs));
> +	new_types = calloc(btf->hdr->type_len, 1);
> +	if (!new_types || !new_offs) {
> +		err = -ENOMEM;
> +		goto out_err;
> +	}

Can btf_permute_shuffle_types() leak new_offs? If the first calloc()
succeeds but the second fails, the function jumps to out_err which
returns without freeing new_offs.

> +
> +	l = new_types;
> +	for (i = 0; i < btf->nr_types; i++) {
> +		id = p->ids[i];
> +		t = btf__type_by_id(btf, id);

Can invalid type IDs from p->ids[] crash btf__type_by_id()? The ids
array comes from user input via btf__permute() opts, but there's no
validation that the IDs are within the valid range before passing them
to btf__type_by_id(). If a user provides an out-of-range type ID, this
could access invalid memory.

> +		len = btf_type_size(t);
> +		memcpy(l, t, len);
> +		new_offs[i] = l - new_types;
> +		p->map[id - btf->start_id] = btf->start_id + i;
> +		l += len;
> +	}
> +
> +	free(btf->types_data);
> +	free(btf->type_offs);
> +	btf->types_data = new_types;
> +	btf->type_offs = new_offs;
> +	return 0;
> +
> +out_err:
> +	return err;
> +}

[ ... ]


```

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

In-Reply-To-Subject: btf: implement BTF type sorting for accelerated lookups CI run summary: https://github.com/kernel-patches/bpf/actions/runs/18843706931

maintainer
#3 lore raw

Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups

In reply to Donglin Peng
Quoted 18 lines · Donglin Peng

This patch introduces a new libbpf interface btf__permute() to reorganize BTF types according to a provided mapping. The BTF lookup mechanism is enhanced with binary search capability, significantly improving lookup performance for large type sets.

The pahole tool can invoke this interface with a sorted type ID array, enabling binary search in both user space and kernel. To share core logic between kernel and libbpf, common sorting functionality is implemented in a new btf_sort.c source file.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>
Quoted 7 lines

---
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()
?

Quoted 117 lines
 tools/lib/bpf/btf.c            | 262 ++++++++++++++++++++++++++++++---
 tools/lib/bpf/btf.h            |  17 +++
 tools/lib/bpf/btf_sort.c       | 174 ++++++++++++++++++++++
 tools/lib/bpf/btf_sort.h       |  11 ++
 tools/lib/bpf/libbpf.map       |   6 +
 tools/lib/bpf/libbpf_version.h |   2 +-
 6 files changed, 447 insertions(+), 25 deletions(-)
 create mode 100644 tools/lib/bpf/btf_sort.c
 create mode 100644 tools/lib/bpf/btf_sort.h
tools/lib/bpf/btf.c +25 -24
index 18907f0fcf9f..d20bf81a21ce 100644
@@ -23,6 +23,7 @@
 #include "libbpf_internal.h"
 #include "hashmap.h"
 #include "strset.h"
+#include "btf_sort.h"
 
 #define BTF_MAX_NR_TYPES 0x7fffffffU
 #define BTF_MAX_STR_OFFSET 0x7fffffffU
@@ -92,6 +93,12 @@ struct btf {
 	 *   - for split BTF counts number of types added on top of base BTF.
 	 */
 	__u32 nr_types;
+	/* number of sorted and named types in this BTF instance:
+	 *   - doesn't include special [0] void type;
+	 *   - for split BTF counts number of sorted and named types added on
+	 *     top of base BTF.
+	 */
+	__u32 nr_sorted_types;
 	/* if not NULL, points to the base BTF on top of which the current
 	 * split BTF is based
 	 */
@@ -624,6 +631,11 @@ const struct btf *btf__base_btf(const struct btf *btf)
 	return btf->base_btf;
 }
 
+__u32 btf__start_id(const struct btf *btf)
+{
+	return btf->start_id;
+}
+
 /* internal helper returning non-const pointer to a type */
 struct btf_type *btf_type_by_id(const struct btf *btf, __u32 type_id)
 {
@@ -915,38 +927,16 @@ __s32 btf__find_by_name(const struct btf *btf, const char *type_name)
 	return libbpf_err(-ENOENT);
 }
 
-static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
-				   const char *type_name, __u32 kind)
-{
-	__u32 i, nr_types = btf__type_cnt(btf);
-
-	if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
-		return 0;
-
-	for (i = start_id; i < nr_types; i++) {
-		const struct btf_type *t = btf__type_by_id(btf, i);
-		const char *name;
-
-		if (btf_kind(t) != kind)
-			continue;
-		name = btf__name_by_offset(btf, t->name_off);
-		if (name && !strcmp(type_name, name))
-			return i;
-	}
-
-	return libbpf_err(-ENOENT);
-}
-
 __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
 				 __u32 kind)
 {
-	return btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
+	return _btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
 }
 
 __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name,
 			     __u32 kind)
 {
-	return btf_find_by_name_kind(btf, 1, type_name, kind);
+	return _btf_find_by_name_kind(btf, 1, type_name, kind);
 }
 
 static bool btf_is_modifiable(const struct btf *btf)
@@ -1091,6 +1081,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
 	err = err ?: btf_sanity_check(btf);
 	if (err)
 		goto done;
+	btf_check_sorted(btf, btf->start_id);
 
 done:
 	if (err) {
@@ -1715,6 +1706,8 @@ static void btf_invalidate_raw_data(struct btf *btf)
 		free(btf->raw_data_swapped);
 		btf->raw_data_swapped = NULL;
 	}
+	if (btf->nr_sorted_types)
+		btf->nr_sorted_types = 0;
 }
 
 /* Ensure BTF is ready to be modified (by splitting into a three memory
@@ -5829,3 +5822,224 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf)
 		btf->owns_base = false;
 	return libbpf_err(err);
 }
+
+struct btf_permute;
+
+static struct btf_permute *btf_permute_new(struct btf *btf, const struct btf_permute_opts *opts);
+static void btf_permute_free(struct btf_permute *p);
+static int btf_permute_shuffle_types(struct btf_permute *p);
+static int btf_permute_remap_types(struct btf_permute *p);
+static int btf_permute_remap_type_id(__u32 *type_id, void *ctx);

tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5842

Quoted 10 lines
tools/lib/bpf/btf.c +10 -0
+
+/*
+ * Permute BTF types in-place using the ID mapping from btf_permute_opts->ids.
+ * After permutation, all type ID references are updated to reflect the new
+ * ordering. If a struct btf_ext (representing '.BTF.ext' section) is provided,
+ * type ID references within the BTF extension data are also updated.
+ */
+int btf__permute(struct btf *btf, const struct btf_permute_opts *opts)
+{
+	struct btf_permute *p;

Maybe allocate this on stack?
(Or just use btf_permute_opts directly and have 'map' as local variable?).

Quoted 146 lines
tools/lib/bpf/btf.c +146 -0
+	int err = 0;
+
+	if (!OPTS_VALID(opts, btf_permute_opts))
+		return libbpf_err(-EINVAL);
+
+	p = btf_permute_new(btf, opts);
+	if (!p) {
+		pr_debug("btf_permute_new failed: %ld\n", PTR_ERR(p));
+		return libbpf_err(-EINVAL);
+	}
+
+	if (btf_ensure_modifiable(btf)) {
+		err = -ENOMEM;
+		goto done;
+	}
+
+	err = btf_permute_shuffle_types(p);
+	if (err < 0) {
+		pr_debug("btf_permute_shuffle_types failed: %s\n", errstr(err));
+		goto done;
+	}
+	err = btf_permute_remap_types(p);
+	if (err) {
+		pr_debug("btf_permute_remap_types failed: %s\n", errstr(err));
+		goto done;
+	}
+
+done:
+	btf_permute_free(p);
+	return libbpf_err(err);
+}
+
+struct btf_permute {
+	/* .BTF section to be permuted in-place */
+	struct btf *btf;
+	struct btf_ext *btf_ext;
+	/* Array of type IDs used for permutation. The array length must equal
+	 * the number of types in the BTF being permuted, excluding the special
+	 * void type at ID 0. For split BTF, the length corresponds to the
+	 * number of types added on top of the base BTF.
+	 */
+	__u32 *ids;
+	/* Array of type IDs used to map from original type ID to a new permuted
+	 * type ID, its length equals to the above ids */
+	__u32 *map;
+};
+
+static struct btf_permute *btf_permute_new(struct btf *btf, const struct btf_permute_opts *opts)
+{
+	struct btf_permute *p = calloc(1, sizeof(struct btf_permute));
+	__u32 *map;
+	int err = 0;
+
+	if (!p)
+		return ERR_PTR(-ENOMEM);
+
+	p->btf = btf;
+	p->btf_ext = OPTS_GET(opts, btf_ext, NULL);
+	p->ids = OPTS_GET(opts, ids, NULL);
+	if (!p->ids) {
+		err = -EINVAL;
+		goto done;
+	}
+
+	map = calloc(btf->nr_types, sizeof(*map));
+	if (!map) {
+		err = -ENOMEM;
+		goto done;
+	}
+	p->map = map;
+
+done:
+	if (err) {
+		btf_permute_free(p);
+		return ERR_PTR(err);
+	}
+
+	return p;
+}
+
+static void btf_permute_free(struct btf_permute *p)
+{
+	if (p->map) {
+		free(p->map);
+		p->map = NULL;
+	}
+	free(p);
+}
+
+/*
+ * Shuffle BTF types.
+ *
+ * Rearranges types according to the permutation map in p->ids. The p->map
+ * array stores the mapping from original type IDs to new shuffled IDs,
+ * which is used in the next phase to update type references.
+ */
+static int btf_permute_shuffle_types(struct btf_permute *p)
+{
+	struct btf *btf = p->btf;
+	const struct btf_type *t;
+	__u32 *new_offs = NULL;
+	void *l, *new_types = NULL;
+	int i, id, len, err;
+
+	new_offs = calloc(btf->nr_types, sizeof(*new_offs));
+	new_types = calloc(btf->hdr->type_len, 1);
+	if (!new_types || !new_offs) {
+		err = -ENOMEM;
+		goto out_err;
+	}
+
+	l = new_types;
+	for (i = 0; i < btf->nr_types; i++) {
+		id = p->ids[i];
+		t = btf__type_by_id(btf, id);
+		len = btf_type_size(t);
+		memcpy(l, t, len);
+		new_offs[i] = l - new_types;
+		p->map[id - btf->start_id] = btf->start_id + i;
+		l += len;
+	}
+
+	free(btf->types_data);
+	free(btf->type_offs);
+	btf->types_data = new_types;
+	btf->type_offs = new_offs;
+	return 0;
+
+out_err:
+	return err;
+}
+
+/*
+ * Remap referenced type IDs into permuted type IDs.
+ *
+ * After BTF types are permuted, their final type IDs may differ from original
+ * ones. The map from original to a corresponding permuted type ID is stored
+ * in btf_permute->map and is populated during shuffle phase. During remapping
+ * phase we are rewriting all type IDs  referenced from any BTF type (e.g.,
+ * struct fields, func proto args, etc) to their final deduped type IDs.
+ */
+static int btf_permute_remap_types(struct btf_permute *p)
+{
+	struct btf *btf = p->btf;
+	int i, r;
+

tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5998

Quoted 10 lines
tools/lib/bpf/btf.c +10 -0
+	for (i = 0; i < btf->nr_types; i++) {
+		struct btf_type *t = btf_type_by_id(btf, btf->start_id + i);
+		struct btf_field_iter it;
+		__u32 *type_id;
+
+		r = btf_field_iter_init(&it, t, BTF_FIELD_ITER_IDS);
+		if (r)
+			return r;
+
+		while ((type_id = btf_field_iter_next(&it))) {

The code below repeats logic it btf_permute_remap_type_id(), please use it here. Better yet, generalize btf_dedup_remap_types() and avoid a copy-paste altogether.

Quoted 284 lines
tools/lib/bpf/btf.c +47 -0
+			__u32 new_id = *type_id;
+
+			/* skip references that point into the base BTF */
+			if (new_id < btf->start_id)
+				continue;
+
+			new_id = p->map[new_id - btf->start_id];
+			if (new_id > BTF_MAX_NR_TYPES)
+				return -EINVAL;
+
+			*type_id = new_id;
+		}
+	}
+
+	if (!p->btf_ext)
+		return 0;
+
+	r = btf_ext_visit_type_ids(p->btf_ext, btf_permute_remap_type_id, p);
+	if (r)
+		return r;
+
+	return 0;
+}
+
+static int btf_permute_remap_type_id(__u32 *type_id, void *ctx)
+{
+	struct btf_permute *p = ctx;
+	__u32 new_type_id = *type_id;
+
+	/* skip references that point into the base BTF */
+	if (new_type_id < p->btf->start_id)
+		return 0;
+
+	new_type_id = p->map[*type_id - p->btf->start_id];
+	if (new_type_id > BTF_MAX_NR_TYPES)
+		return -EINVAL;
+
+	*type_id = new_type_id;
+	return 0;
+}
+
+/*
+ * btf_sort.c is included directly to avoid function call overhead
+ * when accessing BTF private data, as this file is shared between
+ * libbpf and kernel and may be called frequently.
+ */
+#include "./btf_sort.c"
tools/lib/bpf/btf.h +17 -0
index ccfd905f03df..3aac0a729bd5 100644
@@ -149,6 +149,7 @@ LIBBPF_API __s32 btf__find_by_name_kind(const struct btf *btf,
 					const char *type_name, __u32 kind);
 LIBBPF_API __u32 btf__type_cnt(const struct btf *btf);
 LIBBPF_API const struct btf *btf__base_btf(const struct btf *btf);
+LIBBPF_API __u32 btf__start_id(const struct btf *btf);
 LIBBPF_API const struct btf_type *btf__type_by_id(const struct btf *btf,
 						  __u32 id);
 LIBBPF_API size_t btf__pointer_size(const struct btf *btf);
@@ -273,6 +274,22 @@ LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts);
  */
 LIBBPF_API int btf__relocate(struct btf *btf, const struct btf *base_btf);
 
+struct btf_permute_opts {
+	size_t sz;
+	/* optional .BTF.ext info along the main BTF info */
+	struct btf_ext *btf_ext;
+	/* Array of type IDs used for permutation. The array length must equal
+	 * the number of types in the BTF being permuted, excluding the special
+	 * void type at ID 0. For split BTF, the length corresponds to the
+	 * number of types added on top of the base BTF.
+	 */
+	__u32 *ids;
+	size_t :0;
+};
+#define btf_permute_opts__last_field ids
+
+LIBBPF_API int btf__permute(struct btf *btf, const struct btf_permute_opts *opts);
+
 struct btf_dump;
 
 struct btf_dump_opts {
tools/lib/bpf/btf_sort.c new file +174 -0
new file mode 100644
index 000000000000..553c5f5e61bd
@@ -0,0 +1,174 @@
+// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
+/* Copyright (c) 2025 Xiaomi */
+
+#ifndef _GNU_SOURCE
+#define _GNU_SOURCE
+#endif
+
+#ifdef __KERNEL__
+
+#define btf_type_by_id				(struct btf_type *)btf_type_by_id
+#define btf__str_by_offset			btf_str_by_offset
+#define btf__type_cnt				btf_nr_types
+#define btf__start_id				btf_start_id
+#define libbpf_err(x)				x
+
+#else
+
+#define notrace
+
+#endif /* __KERNEL__ */
+
+/*
+ * Skip the sorted check if the number of BTF types is below this threshold.
+ * The value 4 is chosen based on the theoretical break-even point where
+ * linear search (N/2) and binary search (LOG2(N)) require approximately
+ * the same number of comparisons.
+ */
+#define BTF_CHECK_SORT_THRESHOLD  4
+
+struct btf;
+
+static int cmp_btf_kind_name(int ka, const char *na, int kb, const char *nb)
+{
+	return (ka - kb) ?: strcmp(na, nb);
+}
+
+/*
+ * Sort BTF types by kind and name in ascending order, placing named types
+ * before anonymous ones.
+ */
+static int btf_compare_type_kinds_names(const void *a, const void *b, void *priv)
+{
+	struct btf *btf = (struct btf *)priv;
+	struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
+	struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b);
+	const char *na, *nb;
+	bool anon_a, anon_b;
+	int ka, kb;
+
+	na = btf__str_by_offset(btf, ta->name_off);
+	nb = btf__str_by_offset(btf, tb->name_off);
+	anon_a = str_is_empty(na);
+	anon_b = str_is_empty(nb);
+
+	/* ta w/o name is greater than tb */
+	if (anon_a && !anon_b)
+		return 1;
+	/* tb w/o name is smaller than ta */
+	if (!anon_a && anon_b)
+		return -1;
+
+	ka = btf_kind(ta);
+	kb = btf_kind(tb);
+
+	if (anon_a && anon_b)
+		return ka - kb;
+
+	return cmp_btf_kind_name(ka, na, kb, nb);
+}
+
+static __s32 notrace __btf_find_by_name_kind(const struct btf *btf, int start_id,
+				   const char *type_name, __u32 kind)
+{
+	const struct btf_type *t;
+	const char *tname;
+	int err = -ENOENT;
+
+	if (!btf)
+		goto out;
+
+	if (start_id < btf__start_id(btf)) {
+		err = __btf_find_by_name_kind(btf->base_btf, start_id, type_name, kind);
+		if (err == -ENOENT)
+			start_id = btf__start_id(btf);
+	}
+
+	if (err == -ENOENT) {
+		if (btf->nr_sorted_types) {
+			/* binary search */
+			__s32 start, end, mid, found = -1;
+			int ret;
+
+			start = start_id;
+			end = start + btf->nr_sorted_types - 1;
+			/* found the leftmost btf_type that matches */
+			while(start <= end) {
+				mid = start + (end - start) / 2;
+				t = btf_type_by_id(btf, mid);
+				tname = btf__str_by_offset(btf, t->name_off);
+				ret = cmp_btf_kind_name(BTF_INFO_KIND(t->info), tname,
+							kind, type_name);
+				if (ret < 0)
+					start = mid + 1;
+				else {
+					if (ret == 0)
+						found = mid;
+					end = mid - 1;
+				}
+			}
+
+			if (found != -1)
+				return found;
+		} else {
+			/* linear search */
+			__u32 i, total;
+
+			total = btf__type_cnt(btf);
+			for (i = start_id; i < total; i++) {
+				t = btf_type_by_id(btf, i);
+				if (btf_kind(t) != kind)
+					continue;
+
+				tname = btf__str_by_offset(btf, t->name_off);
+				if (tname && !strcmp(tname, type_name))
+					return i;
+			}
+		}
+	}
+
+out:
+	return err;
+}
+
+/* start_id specifies the starting BTF to search */
+static __s32 notrace _btf_find_by_name_kind(const struct btf *btf, int start_id,
+				   const char *type_name, __u32 kind)
+{
+	if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
+		return 0;
+
+	return libbpf_err(__btf_find_by_name_kind(btf, start_id, type_name, kind));
+}
+
+static void btf_check_sorted(struct btf *btf, int start_id)
+{
+	const struct btf_type *t;
+	int i, n, nr_sorted_types;
+
+	n = btf__type_cnt(btf);
+	if (btf->nr_types < BTF_CHECK_SORT_THRESHOLD)
+		return;
+
+	n--;
+	nr_sorted_types = 0;
+	for (i = start_id; i < n; i++) {
+		int k = i + 1;
+
+		if (btf_compare_type_kinds_names(&i, &k, btf) > 0)
+			return;
+
+		t = btf_type_by_id(btf, k);
+		if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
+			nr_sorted_types++;
+	}
+
+	t = btf_type_by_id(btf, start_id);
+	if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
+		nr_sorted_types++;
+
+	if (nr_sorted_types < BTF_CHECK_SORT_THRESHOLD)
+		return;
+
+	btf->nr_sorted_types = nr_sorted_types;
+}
tools/lib/bpf/btf_sort.h new file +11 -0
new file mode 100644
index 000000000000..4dedc67286d9
@@ -0,0 +1,11 @@
+/* SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) */
+/* Copyright (c) 2025 Xiaomi */
+
+#ifndef __BTF_SORT_H
+#define __BTF_SORT_H
+
+static __s32 _btf_find_by_name_kind(const struct btf *btf, int start_id, const char *type_name, __u32 kind);
+static int btf_compare_type_kinds_names(const void *a, const void *b, void *priv);
+static void btf_check_sorted(struct btf *btf, int start_id);
+
+#endif
tools/lib/bpf/libbpf.map +0 -0
index 8ed8749907d4..8ce7b1d08650 100644

tools/lib/bpf/libbpf.map LIBBPF_1.7.0 { · line 456

Quoted 5 lines
tools/lib/bpf/libbpf.map +2 -0
@@ -452,3 +452,9 @@ LIBBPF_1.7.0 {
 		bpf_map__set_exclusive_program;
 		bpf_map__exclusive_program;
 } LIBBPF_1.6.0;
+
+LIBBPF_1.8.0 {

I think we are still at 1.7.

Quoted 16 lines
tools/lib/bpf/libbpf.map +4 -0
+	global:
+		btf__start_id;
+		btf__permute;
+} LIBBPF_1.7.0;
tools/lib/bpf/libbpf_version.h +1 -1
index 99331e317dee..c446c0cd8cf9 100644
@@ -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 */
#4 lore raw

Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups

Quoted 29 lines · Eduard Zingerman
Quoted 18 lines · Donglin Peng

This patch introduces a new libbpf interface btf__permute() to reorganize BTF types according to a provided mapping. The BTF lookup mechanism is enhanced with binary search capability, significantly improving lookup performance for large type sets.

The pahole tool can invoke this interface with a sorted type ID array, enabling binary search in both user space and kernel. To share core logic between kernel and libbpf, common sorting functionality is implemented in a new btf_sort.c source file.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>
Quoted 7 lines

---
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
---

Quoted 4 lines

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.

Quoted 122 lines
Quoted 122 lines
 tools/lib/bpf/btf.c            | 262 ++++++++++++++++++++++++++++++---
 tools/lib/bpf/btf.h            |  17 +++
 tools/lib/bpf/btf_sort.c       | 174 ++++++++++++++++++++++
 tools/lib/bpf/btf_sort.h       |  11 ++
 tools/lib/bpf/libbpf.map       |   6 +
 tools/lib/bpf/libbpf_version.h |   2 +-
 6 files changed, 447 insertions(+), 25 deletions(-)
 create mode 100644 tools/lib/bpf/btf_sort.c
 create mode 100644 tools/lib/bpf/btf_sort.h
tools/lib/bpf/btf.c +29 -24
index 18907f0fcf9f..d20bf81a21ce 100644
@@ -23,6 +23,7 @@
 #include "libbpf_internal.h"
 #include "hashmap.h"
 #include "strset.h"
+#include "btf_sort.h"
 
 #define BTF_MAX_NR_TYPES 0x7fffffffU
 #define BTF_MAX_STR_OFFSET 0x7fffffffU
@@ -92,6 +93,12 @@ struct btf {
       *   - for split BTF counts number of types added on top of base BTF.
       */
      __u32 nr_types;
+     /* number of sorted and named types in this BTF instance:
+      *   - doesn't include special [0] void type;
+      *   - for split BTF counts number of sorted and named types added on
+      *     top of base BTF.
+      */
+     __u32 nr_sorted_types;
      /* if not NULL, points to the base BTF on top of which the current
       * split BTF is based
       */
@@ -624,6 +631,11 @@ const struct btf *btf__base_btf(const struct btf *btf)
      return btf->base_btf;
 }
 
+__u32 btf__start_id(const struct btf *btf)
+{
+     return btf->start_id;
+}
+
 /* internal helper returning non-const pointer to a type */
 struct btf_type *btf_type_by_id(const struct btf *btf, __u32 type_id)
 {
@@ -915,38 +927,16 @@ __s32 btf__find_by_name(const struct btf *btf, const char *type_name)
      return libbpf_err(-ENOENT);
 }
 
-static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
-                                const char *type_name, __u32 kind)
-{
-     __u32 i, nr_types = btf__type_cnt(btf);
-
-     if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
-             return 0;
-
-     for (i = start_id; i < nr_types; i++) {
-             const struct btf_type *t = btf__type_by_id(btf, i);
-             const char *name;
-
-             if (btf_kind(t) != kind)
-                     continue;
-             name = btf__name_by_offset(btf, t->name_off);
-             if (name && !strcmp(type_name, name))
-                     return i;
-     }
-
-     return libbpf_err(-ENOENT);
-}
-
 __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
                               __u32 kind)
 {
-     return btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
+     return _btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
 }
 
 __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name,
                           __u32 kind)
 {
-     return btf_find_by_name_kind(btf, 1, type_name, kind);
+     return _btf_find_by_name_kind(btf, 1, type_name, kind);
 }
 
 static bool btf_is_modifiable(const struct btf *btf)
@@ -1091,6 +1081,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
      err = err ?: btf_sanity_check(btf);
      if (err)
              goto done;
+     btf_check_sorted(btf, btf->start_id);
 
 done:
      if (err) {
@@ -1715,6 +1706,8 @@ static void btf_invalidate_raw_data(struct btf *btf)
              free(btf->raw_data_swapped);
              btf->raw_data_swapped = NULL;
      }
+     if (btf->nr_sorted_types)
+             btf->nr_sorted_types = 0;
 }
 
 /* Ensure BTF is ready to be modified (by splitting into a three memory
@@ -5829,3 +5822,224 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf)
              btf->owns_base = false;
      return libbpf_err(err);
 }
+
+struct btf_permute;
+
+static struct btf_permute *btf_permute_new(struct btf *btf, const struct btf_permute_opts *opts);
+static void btf_permute_free(struct btf_permute *p);
+static int btf_permute_shuffle_types(struct btf_permute *p);
+static int btf_permute_remap_types(struct btf_permute *p);
+static int btf_permute_remap_type_id(__u32 *type_id, void *ctx);
+
+/*
+ * Permute BTF types in-place using the ID mapping from btf_permute_opts->ids.
+ * After permutation, all type ID references are updated to reflect the new
Quoted 8 lines

tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5842

Quoted 6 lines
tools/lib/bpf/btf.c +6 -0
+ * ordering. If a struct btf_ext (representing '.BTF.ext' section) is provided,
+ * type ID references within the BTF extension data are also updated.
+ */
+int btf__permute(struct btf *btf, const struct btf_permute_opts *opts)
+{
+     struct btf_permute *p;

Maybe allocate this on stack?

Thanks, I will fix it in the next version.

Quoted 1 line

(Or just use btf_permute_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.

Quoted 153 lines
Quoted 153 lines
tools/lib/bpf/btf.c +152 -0
+     int err = 0;
+
+     if (!OPTS_VALID(opts, btf_permute_opts))
+             return libbpf_err(-EINVAL);
+
+     p = btf_permute_new(btf, opts);
+     if (!p) {
+             pr_debug("btf_permute_new failed: %ld\n", PTR_ERR(p));
+             return libbpf_err(-EINVAL);
+     }
+
+     if (btf_ensure_modifiable(btf)) {
+             err = -ENOMEM;
+             goto done;
+     }
+
+     err = btf_permute_shuffle_types(p);
+     if (err < 0) {
+             pr_debug("btf_permute_shuffle_types failed: %s\n", errstr(err));
+             goto done;
+     }
+     err = btf_permute_remap_types(p);
+     if (err) {
+             pr_debug("btf_permute_remap_types failed: %s\n", errstr(err));
+             goto done;
+     }
+
+done:
+     btf_permute_free(p);
+     return libbpf_err(err);
+}
+
+struct btf_permute {
+     /* .BTF section to be permuted in-place */
+     struct btf *btf;
+     struct btf_ext *btf_ext;
+     /* Array of type IDs used for permutation. The array length must equal
+      * the number of types in the BTF being permuted, excluding the special
+      * void type at ID 0. For split BTF, the length corresponds to the
+      * number of types added on top of the base BTF.
+      */
+     __u32 *ids;
+     /* Array of type IDs used to map from original type ID to a new permuted
+      * type ID, its length equals to the above ids */
+     __u32 *map;
+};
+
+static struct btf_permute *btf_permute_new(struct btf *btf, const struct btf_permute_opts *opts)
+{
+     struct btf_permute *p = calloc(1, sizeof(struct btf_permute));
+     __u32 *map;
+     int err = 0;
+
+     if (!p)
+             return ERR_PTR(-ENOMEM);
+
+     p->btf = btf;
+     p->btf_ext = OPTS_GET(opts, btf_ext, NULL);
+     p->ids = OPTS_GET(opts, ids, NULL);
+     if (!p->ids) {
+             err = -EINVAL;
+             goto done;
+     }
+
+     map = calloc(btf->nr_types, sizeof(*map));
+     if (!map) {
+             err = -ENOMEM;
+             goto done;
+     }
+     p->map = map;
+
+done:
+     if (err) {
+             btf_permute_free(p);
+             return ERR_PTR(err);
+     }
+
+     return p;
+}
+
+static void btf_permute_free(struct btf_permute *p)
+{
+     if (p->map) {
+             free(p->map);
+             p->map = NULL;
+     }
+     free(p);
+}
+
+/*
+ * Shuffle BTF types.
+ *
+ * Rearranges types according to the permutation map in p->ids. The p->map
+ * array stores the mapping from original type IDs to new shuffled IDs,
+ * which is used in the next phase to update type references.
+ */
+static int btf_permute_shuffle_types(struct btf_permute *p)
+{
+     struct btf *btf = p->btf;
+     const struct btf_type *t;
+     __u32 *new_offs = NULL;
+     void *l, *new_types = NULL;
+     int i, id, len, err;
+
+     new_offs = calloc(btf->nr_types, sizeof(*new_offs));
+     new_types = calloc(btf->hdr->type_len, 1);
+     if (!new_types || !new_offs) {
+             err = -ENOMEM;
+             goto out_err;
+     }
+
+     l = new_types;
+     for (i = 0; i < btf->nr_types; i++) {
+             id = p->ids[i];
+             t = btf__type_by_id(btf, id);
+             len = btf_type_size(t);
+             memcpy(l, t, len);
+             new_offs[i] = l - new_types;
+             p->map[id - btf->start_id] = btf->start_id + i;
+             l += len;
+     }
+
+     free(btf->types_data);
+     free(btf->type_offs);
+     btf->types_data = new_types;
+     btf->type_offs = new_offs;
+     return 0;
+
+out_err:
+     return err;
+}
+
+/*
+ * Remap referenced type IDs into permuted type IDs.
+ *
+ * After BTF types are permuted, their final type IDs may differ from original
+ * ones. The map from original to a corresponding permuted type ID is stored
+ * in btf_permute->map and is populated during shuffle phase. During remapping
+ * phase we are rewriting all type IDs  referenced from any BTF type (e.g.,
+ * struct fields, func proto args, etc) to their final deduped type IDs.
+ */
+static int btf_permute_remap_types(struct btf_permute *p)
+{
+     struct btf *btf = p->btf;
+     int i, r;
+
+     for (i = 0; i < btf->nr_types; i++) {
+             struct btf_type *t = btf_type_by_id(btf, btf->start_id + i);
+             struct btf_field_iter it;
+             __u32 *type_id;
+
+             r = btf_field_iter_init(&it, t, BTF_FIELD_ITER_IDS);
Quoted 8 lines

tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5998

Quoted 4 lines
tools/lib/bpf/btf.c +4 -0
+             if (r)
+                     return r;
+
+             while ((type_id = btf_field_iter_next(&it))) {

The code below repeats logic it btf_permute_remap_type_id(), please use it here. Better yet, generalize btf_dedup_remap_types() and avoid a copy-paste altogether.

Good catch, thanks. I will fix it in the next version.

Quoted 284 lines
Quoted 284 lines
tools/lib/bpf/btf.c +47 -0
+                     __u32 new_id = *type_id;
+
+                     /* skip references that point into the base BTF */
+                     if (new_id < btf->start_id)
+                             continue;
+
+                     new_id = p->map[new_id - btf->start_id];
+                     if (new_id > BTF_MAX_NR_TYPES)
+                             return -EINVAL;
+
+                     *type_id = new_id;
+             }
+     }
+
+     if (!p->btf_ext)
+             return 0;
+
+     r = btf_ext_visit_type_ids(p->btf_ext, btf_permute_remap_type_id, p);
+     if (r)
+             return r;
+
+     return 0;
+}
+
+static int btf_permute_remap_type_id(__u32 *type_id, void *ctx)
+{
+     struct btf_permute *p = ctx;
+     __u32 new_type_id = *type_id;
+
+     /* skip references that point into the base BTF */
+     if (new_type_id < p->btf->start_id)
+             return 0;
+
+     new_type_id = p->map[*type_id - p->btf->start_id];
+     if (new_type_id > BTF_MAX_NR_TYPES)
+             return -EINVAL;
+
+     *type_id = new_type_id;
+     return 0;
+}
+
+/*
+ * btf_sort.c is included directly to avoid function call overhead
+ * when accessing BTF private data, as this file is shared between
+ * libbpf and kernel and may be called frequently.
+ */
+#include "./btf_sort.c"
tools/lib/bpf/btf.h +17 -0
index ccfd905f03df..3aac0a729bd5 100644
@@ -149,6 +149,7 @@ LIBBPF_API __s32 btf__find_by_name_kind(const struct btf *btf,
                                      const char *type_name, __u32 kind);
 LIBBPF_API __u32 btf__type_cnt(const struct btf *btf);
 LIBBPF_API const struct btf *btf__base_btf(const struct btf *btf);
+LIBBPF_API __u32 btf__start_id(const struct btf *btf);
 LIBBPF_API const struct btf_type *btf__type_by_id(const struct btf *btf,
                                                __u32 id);
 LIBBPF_API size_t btf__pointer_size(const struct btf *btf);
@@ -273,6 +274,22 @@ LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts);
  */
 LIBBPF_API int btf__relocate(struct btf *btf, const struct btf *base_btf);
 
+struct btf_permute_opts {
+     size_t sz;
+     /* optional .BTF.ext info along the main BTF info */
+     struct btf_ext *btf_ext;
+     /* Array of type IDs used for permutation. The array length must equal
+      * the number of types in the BTF being permuted, excluding the special
+      * void type at ID 0. For split BTF, the length corresponds to the
+      * number of types added on top of the base BTF.
+      */
+     __u32 *ids;
+     size_t :0;
+};
+#define btf_permute_opts__last_field ids
+
+LIBBPF_API int btf__permute(struct btf *btf, const struct btf_permute_opts *opts);
+
 struct btf_dump;
 
 struct btf_dump_opts {
tools/lib/bpf/btf_sort.c new file +174 -0
new file mode 100644
index 000000000000..553c5f5e61bd
@@ -0,0 +1,174 @@
+// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
+/* Copyright (c) 2025 Xiaomi */
+
+#ifndef _GNU_SOURCE
+#define _GNU_SOURCE
+#endif
+
+#ifdef __KERNEL__
+
+#define btf_type_by_id                               (struct btf_type *)btf_type_by_id
+#define btf__str_by_offset                   btf_str_by_offset
+#define btf__type_cnt                                btf_nr_types
+#define btf__start_id                                btf_start_id
+#define libbpf_err(x)                                x
+
+#else
+
+#define notrace
+
+#endif /* __KERNEL__ */
+
+/*
+ * Skip the sorted check if the number of BTF types is below this threshold.
+ * The value 4 is chosen based on the theoretical break-even point where
+ * linear search (N/2) and binary search (LOG2(N)) require approximately
+ * the same number of comparisons.
+ */
+#define BTF_CHECK_SORT_THRESHOLD  4
+
+struct btf;
+
+static int cmp_btf_kind_name(int ka, const char *na, int kb, const char *nb)
+{
+     return (ka - kb) ?: strcmp(na, nb);
+}
+
+/*
+ * Sort BTF types by kind and name in ascending order, placing named types
+ * before anonymous ones.
+ */
+static int btf_compare_type_kinds_names(const void *a, const void *b, void *priv)
+{
+     struct btf *btf = (struct btf *)priv;
+     struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
+     struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b);
+     const char *na, *nb;
+     bool anon_a, anon_b;
+     int ka, kb;
+
+     na = btf__str_by_offset(btf, ta->name_off);
+     nb = btf__str_by_offset(btf, tb->name_off);
+     anon_a = str_is_empty(na);
+     anon_b = str_is_empty(nb);
+
+     /* ta w/o name is greater than tb */
+     if (anon_a && !anon_b)
+             return 1;
+     /* tb w/o name is smaller than ta */
+     if (!anon_a && anon_b)
+             return -1;
+
+     ka = btf_kind(ta);
+     kb = btf_kind(tb);
+
+     if (anon_a && anon_b)
+             return ka - kb;
+
+     return cmp_btf_kind_name(ka, na, kb, nb);
+}
+
+static __s32 notrace __btf_find_by_name_kind(const struct btf *btf, int start_id,
+                                const char *type_name, __u32 kind)
+{
+     const struct btf_type *t;
+     const char *tname;
+     int err = -ENOENT;
+
+     if (!btf)
+             goto out;
+
+     if (start_id < btf__start_id(btf)) {
+             err = __btf_find_by_name_kind(btf->base_btf, start_id, type_name, kind);
+             if (err == -ENOENT)
+                     start_id = btf__start_id(btf);
+     }
+
+     if (err == -ENOENT) {
+             if (btf->nr_sorted_types) {
+                     /* binary search */
+                     __s32 start, end, mid, found = -1;
+                     int ret;
+
+                     start = start_id;
+                     end = start + btf->nr_sorted_types - 1;
+                     /* found the leftmost btf_type that matches */
+                     while(start <= end) {
+                             mid = start + (end - start) / 2;
+                             t = btf_type_by_id(btf, mid);
+                             tname = btf__str_by_offset(btf, t->name_off);
+                             ret = cmp_btf_kind_name(BTF_INFO_KIND(t->info), tname,
+                                                     kind, type_name);
+                             if (ret < 0)
+                                     start = mid + 1;
+                             else {
+                                     if (ret == 0)
+                                             found = mid;
+                                     end = mid - 1;
+                             }
+                     }
+
+                     if (found != -1)
+                             return found;
+             } else {
+                     /* linear search */
+                     __u32 i, total;
+
+                     total = btf__type_cnt(btf);
+                     for (i = start_id; i < total; i++) {
+                             t = btf_type_by_id(btf, i);
+                             if (btf_kind(t) != kind)
+                                     continue;
+
+                             tname = btf__str_by_offset(btf, t->name_off);
+                             if (tname && !strcmp(tname, type_name))
+                                     return i;
+                     }
+             }
+     }
+
+out:
+     return err;
+}
+
+/* start_id specifies the starting BTF to search */
+static __s32 notrace _btf_find_by_name_kind(const struct btf *btf, int start_id,
+                                const char *type_name, __u32 kind)
+{
+     if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
+             return 0;
+
+     return libbpf_err(__btf_find_by_name_kind(btf, start_id, type_name, kind));
+}
+
+static void btf_check_sorted(struct btf *btf, int start_id)
+{
+     const struct btf_type *t;
+     int i, n, nr_sorted_types;
+
+     n = btf__type_cnt(btf);
+     if (btf->nr_types < BTF_CHECK_SORT_THRESHOLD)
+             return;
+
+     n--;
+     nr_sorted_types = 0;
+     for (i = start_id; i < n; i++) {
+             int k = i + 1;
+
+             if (btf_compare_type_kinds_names(&i, &k, btf) > 0)
+                     return;
+
+             t = btf_type_by_id(btf, k);
+             if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
+                     nr_sorted_types++;
+     }
+
+     t = btf_type_by_id(btf, start_id);
+     if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
+             nr_sorted_types++;
+
+     if (nr_sorted_types < BTF_CHECK_SORT_THRESHOLD)
+             return;
+
+     btf->nr_sorted_types = nr_sorted_types;
+}
tools/lib/bpf/btf_sort.h new file +11 -0
new file mode 100644
index 000000000000..4dedc67286d9
@@ -0,0 +1,11 @@
+/* SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) */
+/* Copyright (c) 2025 Xiaomi */
+
+#ifndef __BTF_SORT_H
+#define __BTF_SORT_H
+
+static __s32 _btf_find_by_name_kind(const struct btf *btf, int start_id, const char *type_name, __u32 kind);
+static int btf_compare_type_kinds_names(const void *a, const void *b, void *priv);
+static void btf_check_sorted(struct btf *btf, int start_id);
+
+#endif
tools/lib/bpf/libbpf.map +0 -0
index 8ed8749907d4..8ce7b1d08650 100644
Quoted 8 lines

tools/lib/bpf/libbpf.map LIBBPF_1.7.0 { · line 456

Quoted 6 lines
tools/lib/bpf/libbpf.map +2 -0
@@ -452,3 +452,9 @@ LIBBPF_1.7.0 {
              bpf_map__set_exclusive_program;
              bpf_map__exclusive_program;
 } LIBBPF_1.6.0;
+
+LIBBPF_1.8.0 {

I think we are still at 1.7.

Thanks, I will fix it in the next version.

Quoted 17 lines
Quoted 17 lines
tools/lib/bpf/libbpf.map +4 -0
+     global:
+             btf__start_id;
+             btf__permute;
+} LIBBPF_1.7.0;
tools/lib/bpf/libbpf_version.h +1 -1
index 99331e317dee..c446c0cd8cf9 100644
@@ -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 */
maintainer
#5 lore raw

Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups

In reply to Donglin Peng

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?

Quoted 18 lines
tools/lib/bpf/btf_sort.c new file +18 -0
+static void btf_check_sorted(struct btf *btf, int start_id)
+{
+	const struct btf_type *t;
+	int i, n, nr_sorted_types;
+
+	n = btf__type_cnt(btf);
+	if (btf->nr_types < BTF_CHECK_SORT_THRESHOLD)
+		return;
+
+	n--;
+	nr_sorted_types = 0;
+	for (i = start_id; i < n; i++) {
+		int k = i + 1;
+
+		if (btf_compare_type_kinds_names(&i, &k, btf) > 0)
+			return;
+
+		t = btf_type_by_id(btf, k);

tools/lib/bpf/btf_sort.c line 171

Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10 -0
+		if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
+			nr_sorted_types++;
+	}
+
+	t = btf_type_by_id(btf, start_id);
+	if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
+		nr_sorted_types++;
+
+	if (nr_sorted_types < BTF_CHECK_SORT_THRESHOLD)
+		return;

Nit: Still think that this is not needed. It trades a couple of CPU
cycles for this check and a big comment on the top, about why it's needed.

Quoted 3 lines
tools/lib/bpf/btf_sort.c new file +3 -0
+
+	btf->nr_sorted_types = nr_sorted_types;
+}

[...]

#6 lore raw

Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups

Quoted 34 lines · Eduard Zingerman

On Mon, 2025-10-27 at 21:54 +0800, Donglin Peng wrote:

[...]

Question to Andrii, I think.
It looks a bit asymmetrical, that there is btf_check_sorted() in libbpf, but library does not provide comparison or sorting function. Wdyt?

Quoted 24 lines
tools/lib/bpf/btf_sort.c new file +24 -0
+static void btf_check_sorted(struct btf *btf, int start_id)
+{
+     const struct btf_type *t;
+     int i, n, nr_sorted_types;
+
+     n = btf__type_cnt(btf);
+     if (btf->nr_types < BTF_CHECK_SORT_THRESHOLD)
+             return;
+
+     n--;
+     nr_sorted_types = 0;
+     for (i = start_id; i < n; i++) {
+             int k = i + 1;
+
+             if (btf_compare_type_kinds_names(&i, &k, btf) > 0)
+                     return;
+
+             t = btf_type_by_id(btf, k);
+             if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
+                     nr_sorted_types++;
+     }
+
+     t = btf_type_by_id(btf, start_id);
+     if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
Quoted 8 lines

tools/lib/bpf/btf_sort.c line 171

Quoted 4 lines
tools/lib/bpf/btf_sort.c new file +4 -0
+             nr_sorted_types++;
+
+     if (nr_sorted_types < BTF_CHECK_SORT_THRESHOLD)
+             return;

Nit: Still think that this is not needed. It trades a couple of CPU
cycles for this check and a big comment on the top, about why it's needed.

Thanks, I will remove it in the next version.

Quoted 6 lines
Quoted 4 lines
tools/lib/bpf/btf_sort.c new file +3 -0
+
+     btf->nr_sorted_types = nr_sorted_types;
+}

[...]

#7 lore raw

Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups

In reply to Eduard Zingerman
Quoted 9 lines · Eduard Zingerman

On Mon, 2025-10-27 at 21:54 +0800, Donglin Peng wrote:

[...]

Question to Andrii, I think.
It looks a bit asymmetrical, that there 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).

Quoted 39 lines
Quoted 19 lines
tools/lib/bpf/btf_sort.c new file +18 -0
+static void btf_check_sorted(struct btf *btf, int start_id)
+{
+     const struct btf_type *t;
+     int i, n, nr_sorted_types;
+
+     n = btf__type_cnt(btf);
+     if (btf->nr_types < BTF_CHECK_SORT_THRESHOLD)
+             return;
+
+     n--;
+     nr_sorted_types = 0;
+     for (i = start_id; i < n; i++) {
+             int k = i + 1;
+
+             if (btf_compare_type_kinds_names(&i, &k, btf) > 0)
+                     return;
+
+             t = btf_type_by_id(btf, k);

tools/lib/bpf/btf_sort.c line 171

Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10 -0
+             if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
+                     nr_sorted_types++;
+     }
+
+     t = btf_type_by_id(btf, start_id);
+     if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
+             nr_sorted_types++;
+
+     if (nr_sorted_types < BTF_CHECK_SORT_THRESHOLD)
+             return;

Nit: Still think that this is not needed. It trades a couple of CPU
cycles for this check and a big comment on the top, about why it's needed.

Quoted 3 lines
tools/lib/bpf/btf_sort.c new file +3 -0
+
+     btf->nr_sorted_types = nr_sorted_types;
+}

[...]

#8 lore raw

Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups

In reply to Donglin Peng
Quoted 25 lines · Donglin Peng

This patch introduces a new libbpf interface btf__permute() to reorganize BTF types according to a provided mapping. The BTF lookup mechanism is enhanced with binary search capability, significantly improving lookup performance for large type sets.

The pahole tool can invoke this interface with a sorted type ID array, enabling binary search in both user space and kernel. To share core logic between kernel and libbpf, common sorting functionality is implemented in a new btf_sort.c source file.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>

---
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

Quoted 11 lines
---
 tools/lib/bpf/btf.c            | 262 ++++++++++++++++++++++++++++++---
 tools/lib/bpf/btf.h            |  17 +++
 tools/lib/bpf/btf_sort.c       | 174 ++++++++++++++++++++++
 tools/lib/bpf/btf_sort.h       |  11 ++
 tools/lib/bpf/libbpf.map       |   6 +
 tools/lib/bpf/libbpf_version.h |   2 +-
 6 files changed, 447 insertions(+), 25 deletions(-)
 create mode 100644 tools/lib/bpf/btf_sort.c
 create mode 100644 tools/lib/bpf/btf_sort.h

This looks a bit over-engineered, let's try to simplify and have more succinct implementation

pw-bot: cr

Quoted 26 lines
tools/lib/bpf/btf.c +7 -0
index 18907f0fcf9f..d20bf81a21ce 100644
@@ -23,6 +23,7 @@
 #include "libbpf_internal.h"
 #include "hashmap.h"
 #include "strset.h"
+#include "btf_sort.h"
 
 #define BTF_MAX_NR_TYPES 0x7fffffffU
 #define BTF_MAX_STR_OFFSET 0x7fffffffU
@@ -92,6 +93,12 @@ struct btf {
         *   - for split BTF counts number of types added on top of base BTF.
         */
        __u32 nr_types;
+       /* number of sorted and named types in this BTF instance:
+        *   - doesn't include special [0] void type;
+        *   - for split BTF counts number of sorted and named types added on
+        *     top of base BTF.
+        */
+       __u32 nr_sorted_types;
        /* if not NULL, points to the base BTF on top of which the current
         * split BTF is based
         */

tools/lib/bpf/btf.c const struct btf *btf__base_btf(const struct btf *btf) · line 637

Quoted 7 lines
tools/lib/bpf/btf.c +4 -0
@@ -624,6 +631,11 @@ const struct btf *btf__base_btf(const struct btf *btf)
        return btf->base_btf;
 }
 
+__u32 btf__start_id(const struct btf *btf)
+{
+       return btf->start_id;
+}

this can already be determined using btf__base_btf() (and then getting its btf__type_cnt()), but I guess I don't mind having a small dedicated API for this. But please add it as a separate patch

Quoted 32 lines
tools/lib/bpf/btf.c +1 -22
+
 /* internal helper returning non-const pointer to a type */
 struct btf_type *btf_type_by_id(const struct btf *btf, __u32 type_id)
 {
@@ -915,38 +927,16 @@ __s32 btf__find_by_name(const struct btf *btf, const char *type_name)
        return libbpf_err(-ENOENT);
 }
 
-static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
-                                  const char *type_name, __u32 kind)
-{
-       __u32 i, nr_types = btf__type_cnt(btf);
-
-       if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
-               return 0;
-
-       for (i = start_id; i < nr_types; i++) {
-               const struct btf_type *t = btf__type_by_id(btf, i);
-               const char *name;
-
-               if (btf_kind(t) != kind)
-                       continue;
-               name = btf__name_by_offset(btf, t->name_off);
-               if (name && !strcmp(type_name, name))
-                       return i;
-       }
-
-       return libbpf_err(-ENOENT);
-}
-
 __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
                                 __u32 kind)

tools/lib/bpf/btf.c __s32 btf__find_by_name(const struct btf *btf, const char *type_name) · line 939

Quoted 10 lines
tools/lib/bpf/btf.c +2 -2
 {
-       return btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
+       return _btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
 }
 
 __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name,
                             __u32 kind)
 {
-       return btf_find_by_name_kind(btf, 1, type_name, kind);
+       return _btf_find_by_name_kind(btf, 1, type_name, kind);

nit: please avoid using underscore-prefixed names

tools/lib/bpf/btf.c static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b · line 1084

Quoted 8 lines
tools/lib/bpf/btf.c +1 -0
 }
 
 static bool btf_is_modifiable(const struct btf *btf)
@@ -1091,6 +1081,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
        err = err ?: btf_sanity_check(btf);
        if (err)
                goto done;
+       btf_check_sorted(btf, btf->start_id);

let's do this lazily when we actually need to search by name, that will also work better with invalidation (currently you don't recheck sortedness after invalidation)

[...]

tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5839

Quoted 6 lines
tools/lib/bpf/btf.c +6 -0
+/*
+ * Permute BTF types in-place using the ID mapping from btf_permute_opts->ids.
+ * After permutation, all type ID references are updated to reflect the new
+ * ordering. If a struct btf_ext (representing '.BTF.ext' section) is provided,
+ * type ID references within the BTF extension data are also updated.
+ */

See how we provide doc comment for public APIs and do the same with btf__permute

Quoted 1 line

+int btf__permute(struct btf *btf, const struct btf_permute_opts *opts)

id map array is mandatory parameter which will always be specified, make it a fixed argument. We use opts for something that's optional and/or infrequently used. btf_ext being part of opts makes total sense, though.

Quoted 14 lines
tools/lib/bpf/btf.c +14 -0
+{
+       struct btf_permute *p;
+       int err = 0;
+
+       if (!OPTS_VALID(opts, btf_permute_opts))
+               return libbpf_err(-EINVAL);
+
+       p = btf_permute_new(btf, opts);
+       if (!p) {
+               pr_debug("btf_permute_new failed: %ld\n", PTR_ERR(p));
+               return libbpf_err(-EINVAL);
+       }
+
+       if (btf_ensure_modifiable(btf)) {

tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5864

Quoted 10 lines
tools/lib/bpf/btf.c +10 -0
+               err = -ENOMEM;
+               goto done;
+       }
+
+       err = btf_permute_shuffle_types(p);
+       if (err < 0) {
+               pr_debug("btf_permute_shuffle_types failed: %s\n", errstr(err));
+               goto done;
+       }
+       err = btf_permute_remap_types(p);

can't we remap IDs as we shuffle and move types around? I'm not sure we need entire struct btf_permute to keep track of all of this, this can be a local state in a single function

Quoted 10 lines
tools/lib/bpf/btf.c +10 -0
+       if (err) {
+               pr_debug("btf_permute_remap_types failed: %s\n", errstr(err));
+               goto done;
+       }
+
+done:
+       btf_permute_free(p);
+       return libbpf_err(err);
+}
+

[...]

Quoted 13 lines
tools/lib/bpf/btf.c +13 -0
+/*
+ * Shuffle BTF types.
+ *
+ * Rearranges types according to the permutation map in p->ids. The p->map
+ * array stores the mapping from original type IDs to new shuffled IDs,
+ * which is used in the next phase to update type references.
+ */
+static int btf_permute_shuffle_types(struct btf_permute *p)
+{
+       struct btf *btf = p->btf;
+       const struct btf_type *t;
+       __u32 *new_offs = NULL;
+       void *l, *new_types = NULL;

tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5954

Quoted 10 lines
tools/lib/bpf/btf.c +10 -0
+       int i, id, len, err;
+
+       new_offs = calloc(btf->nr_types, sizeof(*new_offs));
+       new_types = calloc(btf->hdr->type_len, 1);
+       if (!new_types || !new_offs) {
+               err = -ENOMEM;
+               goto out_err;
+       }
+
+       l = new_types;

What does "l" refer to in this name? It rings no bells for me...

Quoted 1 line

+ for (i = 0; i < btf->nr_types; i++) {

this won't work with split BTF, no?

Quoted 15 lines
tools/lib/bpf/btf.c +15 -0
+               id = p->ids[i];
+               t = btf__type_by_id(btf, id);
+               len = btf_type_size(t);
+               memcpy(l, t, len);
+               new_offs[i] = l - new_types;
+               p->map[id - btf->start_id] = btf->start_id + i;
+               l += len;
+       }
+
+       free(btf->types_data);
+       free(btf->type_offs);
+       btf->types_data = new_types;
+       btf->type_offs = new_offs;
+       return 0;
+

[...]

tools/lib/bpf/btf_sort.c

Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +0 -0
new file mode 100644
index 000000000000..553c5f5e61bd

why does this have to be a separate file? can't it be part of btf.c?

Quoted 19 lines
tools/lib/bpf/btf_sort.c new file +18 -0
@@ -0,0 +1,174 @@
+// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
+/* Copyright (c) 2025 Xiaomi */
+
+#ifndef _GNU_SOURCE
+#define _GNU_SOURCE
+#endif
+
+#ifdef __KERNEL__
+
+#define btf_type_by_id                         (struct btf_type *)btf_type_by_id
+#define btf__str_by_offset                     btf_str_by_offset
+#define btf__type_cnt                          btf_nr_types
+#define btf__start_id                          btf_start_id
+#define libbpf_err(x)                          x
+
+#else
+
+#define notrace

tools/lib/bpf/btf_sort.c line 28

Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10 -0
+
+#endif /* __KERNEL__ */
+
+/*
+ * Skip the sorted check if the number of BTF types is below this threshold.
+ * The value 4 is chosen based on the theoretical break-even point where
+ * linear search (N/2) and binary search (LOG2(N)) require approximately
+ * the same number of comparisons.
+ */
+#define BTF_CHECK_SORT_THRESHOLD  4

I agree with Eduard, it seems like an overkill. For small BTFs this all doesn't matter anyways.

Quoted 31 lines
tools/lib/bpf/btf_sort.c new file +31 -0
+
+struct btf;
+
+static int cmp_btf_kind_name(int ka, const char *na, int kb, const char *nb)
+{
+       return (ka - kb) ?: strcmp(na, nb);
+}
+
+/*
+ * Sort BTF types by kind and name in ascending order, placing named types
+ * before anonymous ones.
+ */
+static int btf_compare_type_kinds_names(const void *a, const void *b, void *priv)
+{
+       struct btf *btf = (struct btf *)priv;
+       struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
+       struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b);
+       const char *na, *nb;
+       bool anon_a, anon_b;
+       int ka, kb;
+
+       na = btf__str_by_offset(btf, ta->name_off);
+       nb = btf__str_by_offset(btf, tb->name_off);
+       anon_a = str_is_empty(na);
+       anon_b = str_is_empty(nb);
+
+       /* ta w/o name is greater than tb */
+       if (anon_a && !anon_b)
+               return 1;
+       /* tb w/o name is smaller than ta */
+       if (!anon_a && anon_b)

tools/lib/bpf/btf_sort.c line 69

Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10 -0
+               return -1;
+
+       ka = btf_kind(ta);
+       kb = btf_kind(tb);
+
+       if (anon_a && anon_b)
+               return ka - kb;
+
+       return cmp_btf_kind_name(ka, na, kb, nb);
+}

I think we should keep it simple and only use sorted-by-name property. Within the same name, we can just search linearly for necessary kind.

Quoted 18 lines
tools/lib/bpf/btf_sort.c new file +18 -0
+
+static __s32 notrace __btf_find_by_name_kind(const struct btf *btf, int start_id,
+                                  const char *type_name, __u32 kind)
+{
+       const struct btf_type *t;
+       const char *tname;
+       int err = -ENOENT;
+
+       if (!btf)
+               goto out;
+
+       if (start_id < btf__start_id(btf)) {
+               err = __btf_find_by_name_kind(btf->base_btf, start_id, type_name, kind);
+               if (err == -ENOENT)
+                       start_id = btf__start_id(btf);
+       }
+
+       if (err == -ENOENT) {

tools/lib/bpf/btf_sort.c line 97

Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10 -0
+               if (btf->nr_sorted_types) {
+                       /* binary search */
+                       __s32 start, end, mid, found = -1;
+                       int ret;
+
+                       start = start_id;
+                       end = start + btf->nr_sorted_types - 1;
+                       /* found the leftmost btf_type that matches */
+                       while(start <= end) {
+                               mid = start + (end - start) / 2;

nit: binary search is, IMO, where succinct names like "l", "r", "m" are good and actually help keeping algorithm code more succinct without making it more obscure

Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +5 -0
+                               t = btf_type_by_id(btf, mid);
+                               tname = btf__str_by_offset(btf, t->name_off);
+                               ret = cmp_btf_kind_name(BTF_INFO_KIND(t->info), tname,
+                                                       kind, type_name);
+                               if (ret < 0)

tools/lib/bpf/btf_sort.c line 112

Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10 -0
+                                       start = mid + 1;
+                               else {
+                                       if (ret == 0)
+                                               found = mid;
+                                       end = mid - 1;
+                               }
+                       }
+
+                       if (found != -1)
+                               return found;

please check find_linfo() in kernel/bpf/log.c for a very succinct implementation of binary search where we look not for exact match, but rather leftmost or rightmost element satisfying some condition. find_linfo() is actually looking for leftmost element (despite what comment says :) ), so I think can be followed very closely.

Quoted 17 lines
tools/lib/bpf/btf_sort.c new file +17 -0
+               } else {
+                       /* linear search */
+                       __u32 i, total;
+
+                       total = btf__type_cnt(btf);
+                       for (i = start_id; i < total; i++) {
+                               t = btf_type_by_id(btf, i);
+                               if (btf_kind(t) != kind)
+                                       continue;
+
+                               tname = btf__str_by_offset(btf, t->name_off);
+                               if (tname && !strcmp(tname, type_name))
+                                       return i;
+                       }
+               }
+       }
+

[...]

#9 lore raw

Re: [RFC PATCH v3 1/3] btf: implement BTF type sorting for accelerated lookups

Quoted 39 lines · Andrii Nakryiko
Quoted 25 lines · Donglin Peng

This patch introduces a new libbpf interface btf__permute() to reorganize BTF types according to a provided mapping. The BTF lookup mechanism is enhanced with binary search capability, significantly improving lookup performance for large type sets.

The pahole tool can invoke this interface with a sorted type ID array, enabling binary search in both user space and kernel. To share core logic between kernel and libbpf, common sorting functionality is implemented in a new btf_sort.c source file.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>

---
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

Quoted 11 lines
---
 tools/lib/bpf/btf.c            | 262 ++++++++++++++++++++++++++++++---
 tools/lib/bpf/btf.h            |  17 +++
 tools/lib/bpf/btf_sort.c       | 174 ++++++++++++++++++++++
 tools/lib/bpf/btf_sort.h       |  11 ++
 tools/lib/bpf/libbpf.map       |   6 +
 tools/lib/bpf/libbpf_version.h |   2 +-
 6 files changed, 447 insertions(+), 25 deletions(-)
 create mode 100644 tools/lib/bpf/btf_sort.c
 create mode 100644 tools/lib/bpf/btf_sort.h
Quoted 2 lines

This looks a bit over-engineered, let's try to simplify and have more succinct implementation

Thanks, I will simplify it.

Quoted 32 lines

pw-bot: cr

Quoted 29 lines
tools/lib/bpf/btf.c +7 -0
index 18907f0fcf9f..d20bf81a21ce 100644
@@ -23,6 +23,7 @@
 #include "libbpf_internal.h"
 #include "hashmap.h"
 #include "strset.h"
+#include "btf_sort.h"
 
 #define BTF_MAX_NR_TYPES 0x7fffffffU
 #define BTF_MAX_STR_OFFSET 0x7fffffffU
@@ -92,6 +93,12 @@ struct btf {
         *   - for split BTF counts number of types added on top of base BTF.
         */
        __u32 nr_types;
+       /* number of sorted and named types in this BTF instance:
+        *   - doesn't include special [0] void type;
+        *   - for split BTF counts number of sorted and named types added on
+        *     top of base BTF.
+        */
+       __u32 nr_sorted_types;
        /* if not NULL, points to the base BTF on top of which the current
         * split BTF is based
         */
@@ -624,6 +631,11 @@ const struct btf *btf__base_btf(const struct btf *btf)
        return btf->base_btf;
 }
 
Quoted 7 lines

tools/lib/bpf/btf.c const struct btf *btf__base_btf(const struct btf *btf) · line 637

Quoted 4 lines
tools/lib/bpf/btf.c +4 -0
+__u32 btf__start_id(const struct btf *btf)
+{
+       return btf->start_id;
+}

this can already be determined using btf__base_btf() (and then getting 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)

Quoted 39 lines

dedicated API for this. But please add it as a separate patch

Quoted 37 lines
tools/lib/bpf/btf.c +2 -23
+
 /* internal helper returning non-const pointer to a type */
 struct btf_type *btf_type_by_id(const struct btf *btf, __u32 type_id)
 {
@@ -915,38 +927,16 @@ __s32 btf__find_by_name(const struct btf *btf, const char *type_name)
        return libbpf_err(-ENOENT);
 }
 
-static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
-                                  const char *type_name, __u32 kind)
-{
-       __u32 i, nr_types = btf__type_cnt(btf);
-
-       if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
-               return 0;
-
-       for (i = start_id; i < nr_types; i++) {
-               const struct btf_type *t = btf__type_by_id(btf, i);
-               const char *name;
-
-               if (btf_kind(t) != kind)
-                       continue;
-               name = btf__name_by_offset(btf, t->name_off);
-               if (name && !strcmp(type_name, name))
-                       return i;
-       }
-
-       return libbpf_err(-ENOENT);
-}
-
 __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
                                 __u32 kind)
 {
-       return btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
+       return _btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
 }
 
Quoted 7 lines

tools/lib/bpf/btf.c __s32 btf__find_by_name(const struct btf *btf, const char *type_name) · line 939

Quoted 5 lines
tools/lib/bpf/btf.c +1 -1
 __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name,
                             __u32 kind)
 {
-       return btf_find_by_name_kind(btf, 1, type_name, kind);
+       return _btf_find_by_name_kind(btf, 1, type_name, kind);

nit: please avoid using underscore-prefixed names

Thanks. I will fix it in the next version.

Quoted 13 lines

tools/lib/bpf/btf.c static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b · line 1084

Quoted 9 lines
tools/lib/bpf/btf.c +1 -0
 }
 
 static bool btf_is_modifiable(const struct btf *btf)
@@ -1091,6 +1081,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
        err = err ?: btf_sanity_check(btf);
        if (err)
                goto done;
+       btf_check_sorted(btf, btf->start_id);

let's do this lazily when we actually need to search by name, that will also work better with invalidation (currently you don't recheck sortedness after invalidation)

Thanks. I'll defer the call to btf_check_sorted until the first invocation of btf__find_by_name_kind.

Quoted 11 lines

[...]

Quoted 6 lines

+/*
+ * Permute BTF types in-place using the ID mapping 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.

Quoted 7 lines
Quoted 2 lines

+int btf__permute(struct btf *btf, const struct btf_permute_opts *opts)

id map array is mandatory parameter which will always be specified, make it a fixed argument. We use opts for something that's optional and/or infrequently used. btf_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)

Quoted 19 lines
Quoted 19 lines
tools/lib/bpf/btf.c +18 -0
+{
+       struct btf_permute *p;
+       int err = 0;
+
+       if (!OPTS_VALID(opts, btf_permute_opts))
+               return libbpf_err(-EINVAL);
+
+       p = btf_permute_new(btf, opts);
+       if (!p) {
+               pr_debug("btf_permute_new failed: %ld\n", PTR_ERR(p));
+               return libbpf_err(-EINVAL);
+       }
+
+       if (btf_ensure_modifiable(btf)) {
+               err = -ENOMEM;
+               goto done;
+       }
+
Quoted 8 lines

tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5864

Quoted 6 lines
tools/lib/bpf/btf.c +6 -0
+       err = btf_permute_shuffle_types(p);
+       if (err < 0) {
+               pr_debug("btf_permute_shuffle_types failed: %s\n", errstr(err));
+               goto done;
+       }
+       err = btf_permute_remap_types(p);

can't we remap IDs as we shuffle and move types around? I'm not sure

This approach appears infeasible, as it necessitates first generating a complete type ID mapping (similar to btf_dedup's hypot_map) to translate original IDs to new IDs for all referenced types, followed by executing the remapping phase.

Quoted 2 lines

we need entire struct btf_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.

Quoted 31 lines
Quoted 11 lines
tools/lib/bpf/btf.c +10 -0
+       if (err) {
+               pr_debug("btf_permute_remap_types failed: %s\n", errstr(err));
+               goto done;
+       }
+
+done:
+       btf_permute_free(p);
+       return libbpf_err(err);
+}
+

[...]

Quoted 17 lines
tools/lib/bpf/btf.c +17 -0
+/*
+ * Shuffle BTF types.
+ *
+ * Rearranges types according to the permutation map in p->ids. The p->map
+ * array stores the mapping from original type IDs to new shuffled IDs,
+ * which is used in the next phase to update type references.
+ */
+static int btf_permute_shuffle_types(struct btf_permute *p)
+{
+       struct btf *btf = p->btf;
+       const struct btf_type *t;
+       __u32 *new_offs = NULL;
+       void *l, *new_types = NULL;
+       int i, id, len, err;
+
+       new_offs = calloc(btf->nr_types, sizeof(*new_offs));
+       new_types = calloc(btf->hdr->type_len, 1);
Quoted 8 lines

tools/lib/bpf/btf.c int btf__relocate(struct btf *btf, const struct btf *base_btf) · line 5954

Quoted 6 lines
tools/lib/bpf/btf.c +6 -0
+       if (!new_types || !new_offs) {
+               err = -ENOMEM;
+               goto out_err;
+       }
+
+       l = new_types;

What does "l" refer to in this name? It rings no bells for me...

Would the name "nt" be acceptable?

Quoted 4 lines
Quoted 2 lines

+ for (i = 0; i < btf->nr_types; i++) {

this won't work with split BTF, no?

The ids array in btf_permute stores type IDs for split BTF. Local testing confirms that kernel module BTF is properly pre-sorted during build using a patched pahole version.

Example usage in pahole:

static int btf_encoder__sort(struct btf *btf)

{
       LIBBPF_OPTS(btf_permute_opts, opts);
       int start_id = btf__start_id(btf);
       int nr_types = btf__type_cnt(btf) - start_id;
       __u32 *permute_ids;
       int i, id, err = 0;

       if (nr_types < 2)
               return 0;

       permute_ids = calloc(nr_types, sizeof(*permute_ids));
       if (!permute_ids) {
               err = -ENOMEM;
               goto out_free;
       }

       for (i = 0, id = start_id; i < nr_types; i++, id++)
               permute_ids[i] = id;

       qsort_r(permute_ids, nr_types, sizeof(*permute_ids),
               cmp_types_kinds_names, btf);

       opts.ids = permute_ids;
       err = btf__permute(btf, &opts);
       if (err)
               goto out_free;

out_free:

       if (permute_ids)
               free(permute_ids);
       return err;
}
Quoted 19 lines
Quoted 16 lines
tools/lib/bpf/btf.c +15 -0
+               id = p->ids[i];
+               t = btf__type_by_id(btf, id);
+               len = btf_type_size(t);
+               memcpy(l, t, len);
+               new_offs[i] = l - new_types;
+               p->map[id - btf->start_id] = btf->start_id + i;
+               l += len;
+       }
+
+       free(btf->types_data);
+       free(btf->type_offs);
+       btf->types_data = new_types;
+       btf->type_offs = new_offs;
+       return 0;
+

[...]

Quoted 7 lines

tools/lib/bpf/btf_sort.c

Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +0 -0
new file mode 100644
index 000000000000..553c5f5e61bd

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/[email protected]/#t
https://lore.kernel.org/all/[email protected]/

Quoted 25 lines
Quoted 25 lines
tools/lib/bpf/btf_sort.c new file +23 -0
@@ -0,0 +1,174 @@
+// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
+/* Copyright (c) 2025 Xiaomi */
+
+#ifndef _GNU_SOURCE
+#define _GNU_SOURCE
+#endif
+
+#ifdef __KERNEL__
+
+#define btf_type_by_id                         (struct btf_type *)btf_type_by_id
+#define btf__str_by_offset                     btf_str_by_offset
+#define btf__type_cnt                          btf_nr_types
+#define btf__start_id                          btf_start_id
+#define libbpf_err(x)                          x
+
+#else
+
+#define notrace
+
+#endif /* __KERNEL__ */
+
+/*
+ * Skip the sorted check if the number of BTF types is below this threshold.
Quoted 8 lines

tools/lib/bpf/btf_sort.c line 28

Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +5 -0
+ * The value 4 is chosen based on the theoretical break-even point where
+ * linear search (N/2) and binary search (LOG2(N)) require approximately
+ * the same number of comparisons.
+ */
+#define BTF_CHECK_SORT_THRESHOLD  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.

Quoted 37 lines
Quoted 37 lines
tools/lib/bpf/btf_sort.c new file +36 -0
+
+struct btf;
+
+static int cmp_btf_kind_name(int ka, const char *na, int kb, const char *nb)
+{
+       return (ka - kb) ?: strcmp(na, nb);
+}
+
+/*
+ * Sort BTF types by kind and name in ascending order, placing named types
+ * before anonymous ones.
+ */
+static int btf_compare_type_kinds_names(const void *a, const void *b, void *priv)
+{
+       struct btf *btf = (struct btf *)priv;
+       struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
+       struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b);
+       const char *na, *nb;
+       bool anon_a, anon_b;
+       int ka, kb;
+
+       na = btf__str_by_offset(btf, ta->name_off);
+       nb = btf__str_by_offset(btf, tb->name_off);
+       anon_a = str_is_empty(na);
+       anon_b = str_is_empty(nb);
+
+       /* ta w/o name is greater than tb */
+       if (anon_a && !anon_b)
+               return 1;
+       /* tb w/o name is smaller than ta */
+       if (!anon_a && anon_b)
+               return -1;
+
+       ka = btf_kind(ta);
+       kb = btf_kind(tb);
+
Quoted 8 lines

tools/lib/bpf/btf_sort.c line 69

Quoted 5 lines
tools/lib/bpf/btf_sort.c new file +5 -0
+       if (anon_a && anon_b)
+               return ka - kb;
+
+       return cmp_btf_kind_name(ka, na, kb, nb);
+}

I think we should keep it simple and only use sorted-by-name property. Within the same name, we can just search linearly for necessary kind.

This approach is feasible, though it may introduce some overhead in the search function. I previously implemented a hybrid method that first sorts types by name
and then combines binary search with linear search for handling collisions.

https://lore.kernel.org/all/[email protected]/

id = btf_find_by_name_bsearch(btf, name, &start, &end);

if (id > 0) {
    while (start <= end) {
        t = btf_type_by_id(btf, start);
        if (BTF_INFO_KIND(t->info) == kind)
            return start;
        start++;
        }
}

Could this be acceptable?

Quoted 25 lines
Quoted 25 lines
tools/lib/bpf/btf_sort.c new file +24 -0
+
+static __s32 notrace __btf_find_by_name_kind(const struct btf *btf, int start_id,
+                                  const char *type_name, __u32 kind)
+{
+       const struct btf_type *t;
+       const char *tname;
+       int err = -ENOENT;
+
+       if (!btf)
+               goto out;
+
+       if (start_id < btf__start_id(btf)) {
+               err = __btf_find_by_name_kind(btf->base_btf, start_id, type_name, kind);
+               if (err == -ENOENT)
+                       start_id = btf__start_id(btf);
+       }
+
+       if (err == -ENOENT) {
+               if (btf->nr_sorted_types) {
+                       /* binary search */
+                       __s32 start, end, mid, found = -1;
+                       int ret;
+
+                       start = start_id;
Quoted 8 lines

tools/lib/bpf/btf_sort.c line 97

Quoted 4 lines
tools/lib/bpf/btf_sort.c new file +4 -0
+                       end = start + btf->nr_sorted_types - 1;
+                       /* found the leftmost btf_type that matches */
+                       while(start <= end) {
+                               mid = start + (end - start) / 2;

nit: binary search is, IMO, where succinct names like "l", "r", "m" are good and actually help keeping algorithm code more succinct without making it more obscure

Thanks, I will fix it in the next version.

Quoted 17 lines
Quoted 6 lines
tools/lib/bpf/btf_sort.c new file +5 -0
+                               t = btf_type_by_id(btf, mid);
+                               tname = btf__str_by_offset(btf, t->name_off);
+                               ret = cmp_btf_kind_name(BTF_INFO_KIND(t->info), tname,
+                                                       kind, type_name);
+                               if (ret < 0)

tools/lib/bpf/btf_sort.c line 112

Quoted 10 lines
tools/lib/bpf/btf_sort.c new file +10 -0
+                                       start = mid + 1;
+                               else {
+                                       if (ret == 0)
+                                               found = mid;
+                                       end = mid - 1;
+                               }
+                       }
+
+                       if (found != -1)
+                               return found;
Quoted 5 lines

please check find_linfo() 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.

Quoted 20 lines
Quoted 18 lines
tools/lib/bpf/btf_sort.c new file +17 -0
+               } else {
+                       /* linear search */
+                       __u32 i, total;
+
+                       total = btf__type_cnt(btf);
+                       for (i = start_id; i < total; i++) {
+                               t = btf_type_by_id(btf, i);
+                               if (btf_kind(t) != kind)
+                                       continue;
+
+                               tname = btf__str_by_offset(btf, t->name_off);
+                               if (tname && !strcmp(tname, type_name))
+                                       return i;
+                       }
+               }
+       }
+

[...]

#10 lore raw

RFC PATCH v3 2/3 selftests/bpf: add tests for BTF type permutation

In reply to Donglin Peng

Verify that BTF type permutation functionality works correctly.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>
---
 tools/testing/selftests/bpf/prog_tests/btf.c | 109 ++++++++++++++++---
 1 file changed, 94 insertions(+), 15 deletions(-)
tools/testing/selftests/bpf/prog_tests/btf.c +94 -15
index 8a9ba4292109..0688449613d4 100644
@@ -6935,14 +6935,18 @@ struct btf_raw_data {
 	__u32 str_sec_size;
 };
 
-struct btf_dedup_test {
+struct btf_dedup_permute_test {
 	const char *descr;
 	struct btf_raw_data input;
 	struct btf_raw_data expect;
-	struct btf_dedup_opts opts;
+	bool permute;
+	struct btf_dedup_opts dedup_opts;
+	struct btf_permute_opts permute_opts;
 };
 
-static struct btf_dedup_test dedup_tests[] = {
+static __u32 permute_ids_sort_by_kind_name[] = {3, 4, 5, 8, 11, 14, 6, 9, 12, 15, 7, 10, 13, 16, 1, 2};
+
+static struct btf_dedup_permute_test dedup_permute_tests[] = {
 
 {
 	.descr = "dedup: unused strings filtering",
@@ -7105,7 +7109,7 @@ static struct btf_dedup_test dedup_tests[] = {
 		},
 		BTF_STR_SEC("\0s\0x"),
 	},
-	.opts = {
+	.dedup_opts = {
 		.force_collisions = true, /* force hash collisions */
 	},
 },
@@ -7151,7 +7155,7 @@ static struct btf_dedup_test dedup_tests[] = {
 		},
 		BTF_STR_SEC("\0s\0x"),
 	},
-	.opts = {
+	.dedup_opts = {
 		.force_collisions = true, /* force hash collisions */
 	},
 },
@@ -7354,7 +7358,7 @@ static struct btf_dedup_test dedup_tests[] = {
 		},
 		BTF_STR_SEC("\0.bss\0t"),
 	},
-	.opts = {
+	.dedup_opts = {
 		.force_collisions = true
 	},
 },
@@ -8022,6 +8026,72 @@ static struct btf_dedup_test dedup_tests[] = {
 		BTF_STR_SEC("\0foo\0x\0y\0foo_ptr"),
 	},
 },
+{
+	.descr = "permute: func/func_param/struct/struct_member tags",
+	.input = {
+		.raw_types = {
+			/* int */
+			BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [1] */
+			/* void f(int a1, int a2) */
+			BTF_FUNC_PROTO_ENC(0, 2),			/* [2] */
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 1),
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1),
+			BTF_FUNC_ENC(NAME_NTH(3), 2),			/* [3] */
+			/* struct t {int m1; int m2;} */
+			BTF_STRUCT_ENC(NAME_NTH(4), 2, 8),		/* [4] */
+				BTF_MEMBER_ENC(NAME_NTH(5), 1, 0),
+				BTF_MEMBER_ENC(NAME_NTH(6), 1, 32),
+			/* tag -> f: tag1, tag2, tag3 */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 3, -1),		/* [5] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 3, -1),		/* [6] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 3, -1),		/* [7] */
+			/* tag -> f/a2: tag1, tag2, tag3 */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 3, 1),		/* [8] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 3, 1),		/* [9] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 3, 1),		/* [10] */
+			/* tag -> t: tag1, tag2, tag3 */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 4, -1),		/* [11] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 4, -1),		/* [12] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 4, -1),		/* [13] */
+			/* tag -> t/m2: tag1, tag3 */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 4, 1),		/* [14] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 4, 1),		/* [15] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 4, 1),		/* [16] */
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"),
+	},
+	.expect = {
+		.raw_types = {
+			BTF_FUNC_ENC(NAME_NTH(3), 16),			/* [1] */
+			BTF_STRUCT_ENC(NAME_NTH(4), 2, 8),		/* [2] */
+				BTF_MEMBER_ENC(NAME_NTH(5), 15, 0),
+				BTF_MEMBER_ENC(NAME_NTH(6), 15, 32),
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 1, -1),		/* [3] */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 1,  1),		/* [4] */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 2, -1),		/* [5] */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 2,  1),		/* [6] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 1, -1),		/* [7] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 1,  1),		/* [8] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 2, -1),		/* [9] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 2,  1),		/* [10] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 1, -1),		/* [11] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 1,  1),		/* [12] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 2, -1),		/* [13] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 2,  1),		/* [14] */
+			BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [15] */
+			BTF_FUNC_PROTO_ENC(0, 2),			/* [16] */
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 15),
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 15),
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"),
+	},
+	.permute = true,
+	.permute_opts = {
+		.ids = permute_ids_sort_by_kind_name,
+	},
+},
 };
 
 static int btf_type_size(const struct btf_type *t)
@@ -8078,9 +8148,9 @@ static void dump_btf_strings(const char *strs, __u32 len)
 	}
 }
 
-static void do_test_dedup(unsigned int test_num)
+static void do_test_dedup_permute(unsigned int test_num)
 {
-	struct btf_dedup_test *test = &dedup_tests[test_num - 1];
+	struct btf_dedup_permute_test *test = &dedup_permute_tests[test_num - 1];
 	__u32 test_nr_types, expect_nr_types, test_btf_size, expect_btf_size;
 	const struct btf_header *test_hdr, *expect_hdr;
 	struct btf *test_btf = NULL, *expect_btf = NULL;
@@ -8124,11 +8194,20 @@ static void do_test_dedup(unsigned int test_num)
 		goto done;
 	}
 
-	test->opts.sz = sizeof(test->opts);
-	err = btf__dedup(test_btf, &test->opts);
-	if (CHECK(err, "btf_dedup failed errno:%d", err)) {
-		err = -1;
-		goto done;
+	if (test->permute) {
+		test->permute_opts.sz = sizeof(test->permute_opts);
+		err = btf__permute(test_btf, &test->permute_opts);
+		if (CHECK(err, "btf_permute failed errno:%d", err)) {
+			err = -1;
+			goto done;
+		}
+	} else {
+		test->dedup_opts.sz = sizeof(test->dedup_opts);
+		err = btf__dedup(test_btf, &test->dedup_opts);
+		if (CHECK(err, "btf_dedup failed errno:%d", err)) {
+			err = -1;
+			goto done;
+		}
 	}
 
 	test_btf_data = btf__raw_data(test_btf, &test_btf_size);
@@ -8249,7 +8328,7 @@ void test_btf(void)
 		do_test_file(i);
 	for (i = 1; i <= ARRAY_SIZE(info_raw_tests); i++)
 		do_test_info_raw(i);
-	for (i = 1; i <= ARRAY_SIZE(dedup_tests); i++)
-		do_test_dedup(i);
+	for (i = 1; i <= ARRAY_SIZE(dedup_permute_tests); i++)
+		do_test_dedup_permute(i);
 	test_pprint();
 }
Signature · 1 line
2.34.1
maintainer
#11 lore raw

Re: [RFC PATCH v3 2/3] selftests/bpf: add tests for BTF type permutation

Quoted 10 lines · Donglin Peng

Verify that BTF type permutation functionality works correctly.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>

---

Do we need a test case for split btf?
We probably do, as there is index arithmetic etc.

[...]

Quoted 29 lines
tools/testing/selftests/bpf/prog_tests/btf.c +25 -0
@@ -8022,6 +8026,72 @@ static struct btf_dedup_test dedup_tests[] = {
 		BTF_STR_SEC("\0foo\0x\0y\0foo_ptr"),
 	},
 },
+{
+	.descr = "permute: func/func_param/struct/struct_member tags",
+	.input = {
+		.raw_types = {
+			/* int */
+			BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [1] */
+			/* void f(int a1, int a2) */
+			BTF_FUNC_PROTO_ENC(0, 2),			/* [2] */
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 1),
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1),
+			BTF_FUNC_ENC(NAME_NTH(3), 2),			/* [3] */
+			/* struct t {int m1; int m2;} */
+			BTF_STRUCT_ENC(NAME_NTH(4), 2, 8),		/* [4] */
+				BTF_MEMBER_ENC(NAME_NTH(5), 1, 0),
+				BTF_MEMBER_ENC(NAME_NTH(6), 1, 32),
+			/* tag -> f: tag1, tag2, tag3 */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 3, -1),		/* [5] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 3, -1),		/* [6] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 3, -1),		/* [7] */
+			/* tag -> f/a2: tag1, tag2, tag3 */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 3, 1),		/* [8] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 3, 1),		/* [9] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 3, 1),		/* [10] */
+			/* tag -> t: tag1, tag2, tag3 */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 4, -1),		/* [11] */

tools/testing/selftests/bpf/prog_tests/btf.c static struct btf_dedup_test dedup_tests[] = { · line 8063

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/btf.c +10 -0
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 4, -1),		/* [12] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 4, -1),		/* [13] */
+			/* tag -> t/m2: tag1, tag3 */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 4, 1),		/* [14] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 4, 1),		/* [15] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 4, 1),		/* [16] */
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"),
+	},

Nit: I think that this test is a bit too large.
Having fewer decl_tags would still test what we want to test.

Quoted 32 lines
tools/testing/selftests/bpf/prog_tests/btf.c +31 -0
+	.expect = {
+		.raw_types = {
+			BTF_FUNC_ENC(NAME_NTH(3), 16),			/* [1] */
+			BTF_STRUCT_ENC(NAME_NTH(4), 2, 8),		/* [2] */
+				BTF_MEMBER_ENC(NAME_NTH(5), 15, 0),
+				BTF_MEMBER_ENC(NAME_NTH(6), 15, 32),
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 1, -1),		/* [3] */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 1,  1),		/* [4] */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 2, -1),		/* [5] */
+			BTF_DECL_TAG_ENC(NAME_NTH(7), 2,  1),		/* [6] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 1, -1),		/* [7] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 1,  1),		/* [8] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 2, -1),		/* [9] */
+			BTF_DECL_TAG_ENC(NAME_NTH(8), 2,  1),		/* [10] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 1, -1),		/* [11] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 1,  1),		/* [12] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 2, -1),		/* [13] */
+			BTF_DECL_TAG_ENC(NAME_NTH(9), 2,  1),		/* [14] */
+			BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [15] */
+			BTF_FUNC_PROTO_ENC(0, 2),			/* [16] */
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 15),
+				BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 15),
+			BTF_END_RAW,
+		},
+		BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"),
+	},
+	.permute = true,
+	.permute_opts = {
+		.ids = permute_ids_sort_by_kind_name,
+	},
+},
 };

[...]

#12 lore raw

Re: [RFC PATCH v3 2/3] selftests/bpf: add tests for BTF type permutation

Quoted 13 lines · Eduard Zingerman
Quoted 10 lines · Donglin Peng

Verify that BTF type permutation functionality works correctly.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>

---

Quoted 2 lines

Do we need a test case for split btf?
We probably do, as there is index arithmetic etc.

Thanks, I will add a test case for split btf.

Quoted 37 lines

[...]

Quoted 34 lines
tools/testing/selftests/bpf/prog_tests/btf.c +30 -0
@@ -8022,6 +8026,72 @@ static struct btf_dedup_test dedup_tests[] = {
              BTF_STR_SEC("\0foo\0x\0y\0foo_ptr"),
      },
 },
+{
+     .descr = "permute: func/func_param/struct/struct_member tags",
+     .input = {
+             .raw_types = {
+                     /* int */
+                     BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),  /* [1] */
+                     /* void f(int a1, int a2) */
+                     BTF_FUNC_PROTO_ENC(0, 2),                       /* [2] */
+                             BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 1),
+                             BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1),
+                     BTF_FUNC_ENC(NAME_NTH(3), 2),                   /* [3] */
+                     /* struct t {int m1; int m2;} */
+                     BTF_STRUCT_ENC(NAME_NTH(4), 2, 8),              /* [4] */
+                             BTF_MEMBER_ENC(NAME_NTH(5), 1, 0),
+                             BTF_MEMBER_ENC(NAME_NTH(6), 1, 32),
+                     /* tag -> f: tag1, tag2, tag3 */
+                     BTF_DECL_TAG_ENC(NAME_NTH(7), 3, -1),           /* [5] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(8), 3, -1),           /* [6] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(9), 3, -1),           /* [7] */
+                     /* tag -> f/a2: tag1, tag2, tag3 */
+                     BTF_DECL_TAG_ENC(NAME_NTH(7), 3, 1),            /* [8] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(8), 3, 1),            /* [9] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(9), 3, 1),            /* [10] */
+                     /* tag -> t: tag1, tag2, tag3 */
+                     BTF_DECL_TAG_ENC(NAME_NTH(7), 4, -1),           /* [11] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(8), 4, -1),           /* [12] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(9), 4, -1),           /* [13] */
+                     /* tag -> t/m2: tag1, tag3 */
+                     BTF_DECL_TAG_ENC(NAME_NTH(7), 4, 1),            /* [14] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(8), 4, 1),            /* [15] */
Quoted 8 lines

tools/testing/selftests/bpf/prog_tests/btf.c static struct btf_dedup_test dedup_tests[] = { · line 8063

Quoted 5 lines
tools/testing/selftests/bpf/prog_tests/btf.c +5 -0
+                     BTF_DECL_TAG_ENC(NAME_NTH(9), 4, 1),            /* [16] */
+                     BTF_END_RAW,
+             },
+             BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"),
+     },

Nit: I think that this test is a bit too large.
Having fewer decl_tags would still test what we want to test.

Thanks, I agree, I will clean it up.

Quoted 35 lines
Quoted 33 lines
tools/testing/selftests/bpf/prog_tests/btf.c +31 -0
+     .expect = {
+             .raw_types = {
+                     BTF_FUNC_ENC(NAME_NTH(3), 16),                  /* [1] */
+                     BTF_STRUCT_ENC(NAME_NTH(4), 2, 8),              /* [2] */
+                             BTF_MEMBER_ENC(NAME_NTH(5), 15, 0),
+                             BTF_MEMBER_ENC(NAME_NTH(6), 15, 32),
+                     BTF_DECL_TAG_ENC(NAME_NTH(7), 1, -1),           /* [3] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(7), 1,  1),           /* [4] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(7), 2, -1),           /* [5] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(7), 2,  1),           /* [6] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(8), 1, -1),           /* [7] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(8), 1,  1),           /* [8] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(8), 2, -1),           /* [9] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(8), 2,  1),           /* [10] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(9), 1, -1),           /* [11] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(9), 1,  1),           /* [12] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(9), 2, -1),           /* [13] */
+                     BTF_DECL_TAG_ENC(NAME_NTH(9), 2,  1),           /* [14] */
+                     BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),  /* [15] */
+                     BTF_FUNC_PROTO_ENC(0, 2),                       /* [16] */
+                             BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 15),
+                             BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 15),
+                     BTF_END_RAW,
+             },
+             BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"),
+     },
+     .permute = true,
+     .permute_opts = {
+             .ids = permute_ids_sort_by_kind_name,
+     },
+},
 };

[...]

#13 lore raw

RFC PATCH v3 3/3 btf: Reuse libbpf code for BTF type sorting verification and binary search

In reply to Donglin Peng

The previous commit implemented BTF sorting verification and binary search algorithm in libbpf. This patch enables this functionality in the kernel.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>

---
v2->v3:
- Include btf_sort.c directly in btf.c to reduce function call overhead

---
 kernel/bpf/btf.c | 34 ++++++++++++++++++----------------
 1 file changed, 18 insertions(+), 16 deletions(-)
kernel/bpf/btf.c +18 -16
index 0de8fc8a0e0b..df258815a6ca 100644
@@ -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"
Signature · 1 line
2.34.1
#14 lore raw

Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search

kernel/bpf/btf.c bool btf_param_match_suffix(const struct btf *btf, · line 9581

Quoted 9 lines · Donglin Peng
kernel/bpf/btf.c +8 -0
+
+/*
+ * btf_sort.c is included directly to avoid function call overhead
+ * when accessing BTF private data, as this file is shared between
+ * libbpf and kernel and may be called frequently (especially when
+ * funcgraph-args or func-args tracing options are enabled).
+ */
+#include "../../tools/lib/bpf/btf_sort.c"

function call overhead? I don't believe it's measurable.

Don't do it on libbpf side either.

pw-bot: cr

#15 lore raw

Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search

Quoted 13 lines · Alexei Starovoitov

kernel/bpf/btf.c bool btf_param_match_suffix(const struct btf *btf, · line 9581

Quoted 9 lines · Donglin Peng
kernel/bpf/btf.c +8 -0
+
+/*
+ * btf_sort.c is included directly to avoid function call overhead
+ * when accessing BTF private data, as this file is shared between
+ * libbpf and kernel and may be called frequently (especially when
+ * funcgraph-args or func-args tracing options are enabled).
+ */
+#include "../../tools/lib/bpf/btf_sort.c"

function call overhead? I don't believe it's measurable.

Thank you. Since the overhead is primarily due to the function graph tracer, I have reverted to the v2 approach and added the notrace attribute to the relevant functions.

Quoted 2 lines

Don't do it on libbpf side either.

Yes.

Quoted 2 lines

pw-bot: cr

#16 lore raw

Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search

In reply to Donglin Peng
Quoted 24 lines · Donglin Peng

The previous commit implemented BTF sorting verification and binary search algorithm in libbpf. This patch enables this functionality in the kernel.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>

---
v2->v3:
- Include btf_sort.c directly in btf.c to reduce function call overhead

---
 kernel/bpf/btf.c | 34 ++++++++++++++++++----------------
 1 file changed, 18 insertions(+), 16 deletions(-)
kernel/bpf/btf.c +0 -0
index 0de8fc8a0e0b..df258815a6ca 100644

kernel/bpf/btf.c line 36

Quoted 4 lines
kernel/bpf/btf.c +1 -0
@@ -33,6 +33,7 @@
 #include <net/sock.h>
 #include <net/xdp.h>
 #include "../tools/lib/bpf/relo_core.h"
+#include "../tools/lib/bpf/btf_sort.h"

I don't believe in code reuse for the sake of code reuse. This code sharing just makes everything more entangled and complicated. Reimplementing binary search is totally fine, IMO.

[...]

#17 lore raw

Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search

Quoted 21 lines · Andrii Nakryiko
Quoted 19 lines · Donglin Peng

The previous commit implemented BTF sorting verification and binary search algorithm in libbpf. This patch enables this functionality in the kernel.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>

---
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(-)
Quoted 13 lines

kernel/bpf/btf.c line 36

Quoted 9 lines
kernel/bpf/btf.c +1 -0
index 0de8fc8a0e0b..df258815a6ca 100644
@@ -33,6 +33,7 @@
 #include <net/sock.h>
 #include <net/xdp.h>
 #include "../tools/lib/bpf/relo_core.h"
+#include "../tools/lib/bpf/btf_sort.h"

I don't believe in code reuse for the sake of code reuse. This code sharing just makes everything more entangled and complicated. Reimplementing binary search is totally fine, IMO.

Thanks. Would you be open to the approach from v2, where we place the common code in btf_sort.c and compile it separately rather than including it directly?

Quoted 2 lines

[...]

#18 lore raw

Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search

Quoted 38 lines · Donglin Peng
Quoted 21 lines · Andrii Nakryiko
Quoted 19 lines · Donglin Peng

The previous commit implemented BTF sorting verification and binary search algorithm in libbpf. This patch enables this functionality in the kernel.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>

---
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(-)
Quoted 13 lines

kernel/bpf/btf.c line 36

Quoted 9 lines
kernel/bpf/btf.c +1 -0
index 0de8fc8a0e0b..df258815a6ca 100644
@@ -33,6 +33,7 @@
 #include <net/sock.h>
 #include <net/xdp.h>
 #include "../tools/lib/bpf/relo_core.h"
+#include "../tools/lib/bpf/btf_sort.h"

I don't believe in code reuse for the sake of code reuse. This code sharing just makes everything more entangled and complicated. Reimplementing binary search is totally fine, IMO.

Quoted 4 lines

Thanks. Would you be open to the approach from v2, where we place the common code in btf_sort.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.

Quoted 2 lines
Quoted 2 lines

[...]

#19 lore raw

Re: [RFC PATCH v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search

Quoted 45 lines · Andrii Nakryiko
Quoted 38 lines · Donglin Peng
Quoted 21 lines · Andrii Nakryiko
Quoted 19 lines · Donglin Peng

The previous commit implemented BTF sorting verification and binary search algorithm in libbpf. This patch enables this functionality in the kernel.

Cc Eduard Zingerman <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Alan Maguire <[email protected]>
Cc Song Liu <[email protected]>

---
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(-)
Quoted 13 lines

kernel/bpf/btf.c line 36

Quoted 9 lines
kernel/bpf/btf.c +1 -0
index 0de8fc8a0e0b..df258815a6ca 100644
@@ -33,6 +33,7 @@
 #include <net/sock.h>
 #include <net/xdp.h>
 #include "../tools/lib/bpf/relo_core.h"
+#include "../tools/lib/bpf/btf_sort.h"

I don't believe in code reuse for the sake of code reuse. This code sharing just makes everything more entangled and complicated. Reimplementing binary search is totally fine, IMO.

Quoted 4 lines

Thanks. Would you be open to the approach from v2, where we place the common code in btf_sort.c and compile it separately rather than including it directly?

Quoted 4 lines

No, the code is too trivial to try to reuse it. Kernel and user space libbpf code are run with different constraints, sharing it is necessary evil (like for BPF CO-RE relocations), not something that should be encouraged.

Thanks, I will implement it separately as recommended.

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

[...]