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 Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Co-developed-by: Eduard Zingerman Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- v2->v3: - Remove sorting logic from libbpf and provide a generic btf__permute() interface - Remove the search direction patch since sorted lookup provides sufficient performance and changing search order could cause conflicts between BTF and base BTF - Include btf_sort.c directly in btf.c to reduce function call overhead --- tools/lib/bpf/btf.c | 262 ++++++++++++++++++++++++++++++--- tools/lib/bpf/btf.h | 17 +++ tools/lib/bpf/btf_sort.c | 174 ++++++++++++++++++++++ tools/lib/bpf/btf_sort.h | 11 ++ tools/lib/bpf/libbpf.map | 6 + tools/lib/bpf/libbpf_version.h | 2 +- 6 files changed, 447 insertions(+), 25 deletions(-) create mode 100644 tools/lib/bpf/btf_sort.c create mode 100644 tools/lib/bpf/btf_sort.h diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 18907f0fcf9f..d20bf81a21ce 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -23,6 +23,7 @@ #include "libbpf_internal.h" #include "hashmap.h" #include "strset.h" +#include "btf_sort.h" #define BTF_MAX_NR_TYPES 0x7fffffffU #define BTF_MAX_STR_OFFSET 0x7fffffffU @@ -92,6 +93,12 @@ struct btf { * - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; + /* number of sorted and named types in this BTF instance: + * - doesn't include special [0] void type; + * - for split BTF counts number of sorted and named types added on + * top of base BTF. + */ + __u32 nr_sorted_types; /* if not NULL, points to the base BTF on top of which the current * split BTF is based */ @@ -624,6 +631,11 @@ const struct btf *btf__base_btf(const struct btf *btf) return btf->base_btf; } +__u32 btf__start_id(const struct btf *btf) +{ + return btf->start_id; +} + /* internal helper returning non-const pointer to a type */ struct btf_type *btf_type_by_id(const struct btf *btf, __u32 type_id) { @@ -915,38 +927,16 @@ __s32 btf__find_by_name(const struct btf *btf, const char *type_name) return libbpf_err(-ENOENT); } -static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id, - const char *type_name, __u32 kind) -{ - __u32 i, nr_types = btf__type_cnt(btf); - - if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void")) - return 0; - - for (i = start_id; i < nr_types; i++) { - const struct btf_type *t = btf__type_by_id(btf, i); - const char *name; - - if (btf_kind(t) != kind) - continue; - name = btf__name_by_offset(btf, t->name_off); - if (name && !strcmp(type_name, name)) - return i; - } - - return libbpf_err(-ENOENT); -} - __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name, __u32 kind) { - return btf_find_by_name_kind(btf, btf->start_id, type_name, kind); + return _btf_find_by_name_kind(btf, btf->start_id, type_name, kind); } __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name, __u32 kind) { - return btf_find_by_name_kind(btf, 1, type_name, kind); + return _btf_find_by_name_kind(btf, 1, type_name, kind); } static bool btf_is_modifiable(const struct btf *btf) @@ -1091,6 +1081,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b err = err ?: btf_sanity_check(btf); if (err) goto done; + btf_check_sorted(btf, btf->start_id); done: if (err) { @@ -1715,6 +1706,8 @@ static void btf_invalidate_raw_data(struct btf *btf) free(btf->raw_data_swapped); btf->raw_data_swapped = NULL; } + if (btf->nr_sorted_types) + btf->nr_sorted_types = 0; } /* Ensure BTF is ready to be modified (by splitting into a three memory @@ -5829,3 +5822,224 @@ int btf__relocate(struct btf *btf, const struct btf *base_btf) btf->owns_base = false; return libbpf_err(err); } + +struct btf_permute; + +static struct btf_permute *btf_permute_new(struct btf *btf, const struct btf_permute_opts *opts); +static void btf_permute_free(struct btf_permute *p); +static int btf_permute_shuffle_types(struct btf_permute *p); +static int btf_permute_remap_types(struct btf_permute *p); +static int btf_permute_remap_type_id(__u32 *type_id, void *ctx); + +/* + * Permute BTF types in-place using the ID mapping from btf_permute_opts->ids. + * After permutation, all type ID references are updated to reflect the new + * ordering. If a struct btf_ext (representing '.BTF.ext' section) is provided, + * type ID references within the BTF extension data are also updated. + */ +int btf__permute(struct btf *btf, const struct btf_permute_opts *opts) +{ + struct btf_permute *p; + int err = 0; + + if (!OPTS_VALID(opts, btf_permute_opts)) + return libbpf_err(-EINVAL); + + p = btf_permute_new(btf, opts); + if (!p) { + pr_debug("btf_permute_new failed: %ld\n", PTR_ERR(p)); + return libbpf_err(-EINVAL); + } + + if (btf_ensure_modifiable(btf)) { + err = -ENOMEM; + goto done; + } + + err = btf_permute_shuffle_types(p); + if (err < 0) { + pr_debug("btf_permute_shuffle_types failed: %s\n", errstr(err)); + goto done; + } + err = btf_permute_remap_types(p); + if (err) { + pr_debug("btf_permute_remap_types failed: %s\n", errstr(err)); + goto done; + } + +done: + btf_permute_free(p); + return libbpf_err(err); +} + +struct btf_permute { + /* .BTF section to be permuted in-place */ + struct btf *btf; + struct btf_ext *btf_ext; + /* Array of type IDs used for permutation. The array length must equal + * the number of types in the BTF being permuted, excluding the special + * void type at ID 0. For split BTF, the length corresponds to the + * number of types added on top of the base BTF. + */ + __u32 *ids; + /* Array of type IDs used to map from original type ID to a new permuted + * type ID, its length equals to the above ids */ + __u32 *map; +}; + +static struct btf_permute *btf_permute_new(struct btf *btf, const struct btf_permute_opts *opts) +{ + struct btf_permute *p = calloc(1, sizeof(struct btf_permute)); + __u32 *map; + int err = 0; + + if (!p) + return ERR_PTR(-ENOMEM); + + p->btf = btf; + p->btf_ext = OPTS_GET(opts, btf_ext, NULL); + p->ids = OPTS_GET(opts, ids, NULL); + if (!p->ids) { + err = -EINVAL; + goto done; + } + + map = calloc(btf->nr_types, sizeof(*map)); + if (!map) { + err = -ENOMEM; + goto done; + } + p->map = map; + +done: + if (err) { + btf_permute_free(p); + return ERR_PTR(err); + } + + return p; +} + +static void btf_permute_free(struct btf_permute *p) +{ + if (p->map) { + free(p->map); + p->map = NULL; + } + free(p); +} + +/* + * Shuffle BTF types. + * + * Rearranges types according to the permutation map in p->ids. The p->map + * array stores the mapping from original type IDs to new shuffled IDs, + * which is used in the next phase to update type references. + */ +static int btf_permute_shuffle_types(struct btf_permute *p) +{ + struct btf *btf = p->btf; + const struct btf_type *t; + __u32 *new_offs = NULL; + void *l, *new_types = NULL; + int i, id, len, err; + + new_offs = calloc(btf->nr_types, sizeof(*new_offs)); + new_types = calloc(btf->hdr->type_len, 1); + if (!new_types || !new_offs) { + err = -ENOMEM; + goto out_err; + } + + l = new_types; + for (i = 0; i < btf->nr_types; i++) { + id = p->ids[i]; + t = btf__type_by_id(btf, id); + len = btf_type_size(t); + memcpy(l, t, len); + new_offs[i] = l - new_types; + p->map[id - btf->start_id] = btf->start_id + i; + l += len; + } + + free(btf->types_data); + free(btf->type_offs); + btf->types_data = new_types; + btf->type_offs = new_offs; + return 0; + +out_err: + return err; +} + +/* + * Remap referenced type IDs into permuted type IDs. + * + * After BTF types are permuted, their final type IDs may differ from original + * ones. The map from original to a corresponding permuted type ID is stored + * in btf_permute->map and is populated during shuffle phase. During remapping + * phase we are rewriting all type IDs referenced from any BTF type (e.g., + * struct fields, func proto args, etc) to their final deduped type IDs. + */ +static int btf_permute_remap_types(struct btf_permute *p) +{ + struct btf *btf = p->btf; + int i, r; + + for (i = 0; i < btf->nr_types; i++) { + struct btf_type *t = btf_type_by_id(btf, btf->start_id + i); + struct btf_field_iter it; + __u32 *type_id; + + r = btf_field_iter_init(&it, t, BTF_FIELD_ITER_IDS); + if (r) + return r; + + while ((type_id = btf_field_iter_next(&it))) { + __u32 new_id = *type_id; + + /* skip references that point into the base BTF */ + if (new_id < btf->start_id) + continue; + + new_id = p->map[new_id - btf->start_id]; + if (new_id > BTF_MAX_NR_TYPES) + return -EINVAL; + + *type_id = new_id; + } + } + + if (!p->btf_ext) + return 0; + + r = btf_ext_visit_type_ids(p->btf_ext, btf_permute_remap_type_id, p); + if (r) + return r; + + return 0; +} + +static int btf_permute_remap_type_id(__u32 *type_id, void *ctx) +{ + struct btf_permute *p = ctx; + __u32 new_type_id = *type_id; + + /* skip references that point into the base BTF */ + if (new_type_id < p->btf->start_id) + return 0; + + new_type_id = p->map[*type_id - p->btf->start_id]; + if (new_type_id > BTF_MAX_NR_TYPES) + return -EINVAL; + + *type_id = new_type_id; + return 0; +} + +/* + * btf_sort.c is included directly to avoid function call overhead + * when accessing BTF private data, as this file is shared between + * libbpf and kernel and may be called frequently. + */ +#include "./btf_sort.c" diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h index ccfd905f03df..3aac0a729bd5 100644 --- a/tools/lib/bpf/btf.h +++ b/tools/lib/bpf/btf.h @@ -149,6 +149,7 @@ LIBBPF_API __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name, __u32 kind); LIBBPF_API __u32 btf__type_cnt(const struct btf *btf); LIBBPF_API const struct btf *btf__base_btf(const struct btf *btf); +LIBBPF_API __u32 btf__start_id(const struct btf *btf); LIBBPF_API const struct btf_type *btf__type_by_id(const struct btf *btf, __u32 id); LIBBPF_API size_t btf__pointer_size(const struct btf *btf); @@ -273,6 +274,22 @@ LIBBPF_API int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts); */ LIBBPF_API int btf__relocate(struct btf *btf, const struct btf *base_btf); +struct btf_permute_opts { + size_t sz; + /* optional .BTF.ext info along the main BTF info */ + struct btf_ext *btf_ext; + /* Array of type IDs used for permutation. The array length must equal + * the number of types in the BTF being permuted, excluding the special + * void type at ID 0. For split BTF, the length corresponds to the + * number of types added on top of the base BTF. + */ + __u32 *ids; + size_t :0; +}; +#define btf_permute_opts__last_field ids + +LIBBPF_API int btf__permute(struct btf *btf, const struct btf_permute_opts *opts); + struct btf_dump; struct btf_dump_opts { diff --git a/tools/lib/bpf/btf_sort.c b/tools/lib/bpf/btf_sort.c new file mode 100644 index 000000000000..553c5f5e61bd --- /dev/null +++ b/tools/lib/bpf/btf_sort.c @@ -0,0 +1,174 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) +/* Copyright (c) 2025 Xiaomi */ + +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif + +#ifdef __KERNEL__ + +#define btf_type_by_id (struct btf_type *)btf_type_by_id +#define btf__str_by_offset btf_str_by_offset +#define btf__type_cnt btf_nr_types +#define btf__start_id btf_start_id +#define libbpf_err(x) x + +#else + +#define notrace + +#endif /* __KERNEL__ */ + +/* + * Skip the sorted check if the number of BTF types is below this threshold. + * The value 4 is chosen based on the theoretical break-even point where + * linear search (N/2) and binary search (LOG2(N)) require approximately + * the same number of comparisons. + */ +#define BTF_CHECK_SORT_THRESHOLD 4 + +struct btf; + +static int cmp_btf_kind_name(int ka, const char *na, int kb, const char *nb) +{ + return (ka - kb) ?: strcmp(na, nb); +} + +/* + * Sort BTF types by kind and name in ascending order, placing named types + * before anonymous ones. + */ +static int btf_compare_type_kinds_names(const void *a, const void *b, void *priv) +{ + struct btf *btf = (struct btf *)priv; + struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a); + struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b); + const char *na, *nb; + bool anon_a, anon_b; + int ka, kb; + + na = btf__str_by_offset(btf, ta->name_off); + nb = btf__str_by_offset(btf, tb->name_off); + anon_a = str_is_empty(na); + anon_b = str_is_empty(nb); + + /* ta w/o name is greater than tb */ + if (anon_a && !anon_b) + return 1; + /* tb w/o name is smaller than ta */ + if (!anon_a && anon_b) + return -1; + + ka = btf_kind(ta); + kb = btf_kind(tb); + + if (anon_a && anon_b) + return ka - kb; + + return cmp_btf_kind_name(ka, na, kb, nb); +} + +static __s32 notrace __btf_find_by_name_kind(const struct btf *btf, int start_id, + const char *type_name, __u32 kind) +{ + const struct btf_type *t; + const char *tname; + int err = -ENOENT; + + if (!btf) + goto out; + + if (start_id < btf__start_id(btf)) { + err = __btf_find_by_name_kind(btf->base_btf, start_id, type_name, kind); + if (err == -ENOENT) + start_id = btf__start_id(btf); + } + + if (err == -ENOENT) { + if (btf->nr_sorted_types) { + /* binary search */ + __s32 start, end, mid, found = -1; + int ret; + + start = start_id; + end = start + btf->nr_sorted_types - 1; + /* found the leftmost btf_type that matches */ + while(start <= end) { + mid = start + (end - start) / 2; + t = btf_type_by_id(btf, mid); + tname = btf__str_by_offset(btf, t->name_off); + ret = cmp_btf_kind_name(BTF_INFO_KIND(t->info), tname, + kind, type_name); + if (ret < 0) + start = mid + 1; + else { + if (ret == 0) + found = mid; + end = mid - 1; + } + } + + if (found != -1) + return found; + } else { + /* linear search */ + __u32 i, total; + + total = btf__type_cnt(btf); + for (i = start_id; i < total; i++) { + t = btf_type_by_id(btf, i); + if (btf_kind(t) != kind) + continue; + + tname = btf__str_by_offset(btf, t->name_off); + if (tname && !strcmp(tname, type_name)) + return i; + } + } + } + +out: + return err; +} + +/* start_id specifies the starting BTF to search */ +static __s32 notrace _btf_find_by_name_kind(const struct btf *btf, int start_id, + const char *type_name, __u32 kind) +{ + if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void")) + return 0; + + return libbpf_err(__btf_find_by_name_kind(btf, start_id, type_name, kind)); +} + +static void btf_check_sorted(struct btf *btf, int start_id) +{ + const struct btf_type *t; + int i, n, nr_sorted_types; + + n = btf__type_cnt(btf); + if (btf->nr_types < BTF_CHECK_SORT_THRESHOLD) + return; + + n--; + nr_sorted_types = 0; + for (i = start_id; i < n; i++) { + int k = i + 1; + + if (btf_compare_type_kinds_names(&i, &k, btf) > 0) + return; + + t = btf_type_by_id(btf, k); + if (!str_is_empty(btf__str_by_offset(btf, t->name_off))) + nr_sorted_types++; + } + + t = btf_type_by_id(btf, start_id); + if (!str_is_empty(btf__str_by_offset(btf, t->name_off))) + nr_sorted_types++; + + if (nr_sorted_types < BTF_CHECK_SORT_THRESHOLD) + return; + + btf->nr_sorted_types = nr_sorted_types; +} diff --git a/tools/lib/bpf/btf_sort.h b/tools/lib/bpf/btf_sort.h new file mode 100644 index 000000000000..4dedc67286d9 --- /dev/null +++ b/tools/lib/bpf/btf_sort.h @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) */ +/* Copyright (c) 2025 Xiaomi */ + +#ifndef __BTF_SORT_H +#define __BTF_SORT_H + +static __s32 _btf_find_by_name_kind(const struct btf *btf, int start_id, const char *type_name, __u32 kind); +static int btf_compare_type_kinds_names(const void *a, const void *b, void *priv); +static void btf_check_sorted(struct btf *btf, int start_id); + +#endif diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map index 8ed8749907d4..8ce7b1d08650 100644 --- a/tools/lib/bpf/libbpf.map +++ b/tools/lib/bpf/libbpf.map @@ -452,3 +452,9 @@ LIBBPF_1.7.0 { bpf_map__set_exclusive_program; bpf_map__exclusive_program; } LIBBPF_1.6.0; + +LIBBPF_1.8.0 { + global: + btf__start_id; + btf__permute; +} LIBBPF_1.7.0; diff --git a/tools/lib/bpf/libbpf_version.h b/tools/lib/bpf/libbpf_version.h index 99331e317dee..c446c0cd8cf9 100644 --- a/tools/lib/bpf/libbpf_version.h +++ b/tools/lib/bpf/libbpf_version.h @@ -4,6 +4,6 @@ #define __LIBBPF_VERSION_H #define LIBBPF_MAJOR_VERSION 1 -#define LIBBPF_MINOR_VERSION 7 +#define LIBBPF_MINOR_VERSION 8 #endif /* __LIBBPF_VERSION_H */ -- 2.34.1 Verify that BTF type permutation functionality works correctly. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- tools/testing/selftests/bpf/prog_tests/btf.c | 109 ++++++++++++++++--- 1 file changed, 94 insertions(+), 15 deletions(-) diff --git a/tools/testing/selftests/bpf/prog_tests/btf.c b/tools/testing/selftests/bpf/prog_tests/btf.c index 8a9ba4292109..0688449613d4 100644 --- a/tools/testing/selftests/bpf/prog_tests/btf.c +++ b/tools/testing/selftests/bpf/prog_tests/btf.c @@ -6935,14 +6935,18 @@ struct btf_raw_data { __u32 str_sec_size; }; -struct btf_dedup_test { +struct btf_dedup_permute_test { const char *descr; struct btf_raw_data input; struct btf_raw_data expect; - struct btf_dedup_opts opts; + bool permute; + struct btf_dedup_opts dedup_opts; + struct btf_permute_opts permute_opts; }; -static struct btf_dedup_test dedup_tests[] = { +static __u32 permute_ids_sort_by_kind_name[] = {3, 4, 5, 8, 11, 14, 6, 9, 12, 15, 7, 10, 13, 16, 1, 2}; + +static struct btf_dedup_permute_test dedup_permute_tests[] = { { .descr = "dedup: unused strings filtering", @@ -7105,7 +7109,7 @@ static struct btf_dedup_test dedup_tests[] = { }, BTF_STR_SEC("\0s\0x"), }, - .opts = { + .dedup_opts = { .force_collisions = true, /* force hash collisions */ }, }, @@ -7151,7 +7155,7 @@ static struct btf_dedup_test dedup_tests[] = { }, BTF_STR_SEC("\0s\0x"), }, - .opts = { + .dedup_opts = { .force_collisions = true, /* force hash collisions */ }, }, @@ -7354,7 +7358,7 @@ static struct btf_dedup_test dedup_tests[] = { }, BTF_STR_SEC("\0.bss\0t"), }, - .opts = { + .dedup_opts = { .force_collisions = true }, }, @@ -8022,6 +8026,72 @@ static struct btf_dedup_test dedup_tests[] = { BTF_STR_SEC("\0foo\0x\0y\0foo_ptr"), }, }, +{ + .descr = "permute: func/func_param/struct/struct_member tags", + .input = { + .raw_types = { + /* int */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ + /* void f(int a1, int a2) */ + BTF_FUNC_PROTO_ENC(0, 2), /* [2] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 1), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1), + BTF_FUNC_ENC(NAME_NTH(3), 2), /* [3] */ + /* struct t {int m1; int m2;} */ + BTF_STRUCT_ENC(NAME_NTH(4), 2, 8), /* [4] */ + BTF_MEMBER_ENC(NAME_NTH(5), 1, 0), + BTF_MEMBER_ENC(NAME_NTH(6), 1, 32), + /* tag -> f: tag1, tag2, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(7), 3, -1), /* [5] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 3, -1), /* [6] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 3, -1), /* [7] */ + /* tag -> f/a2: tag1, tag2, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(7), 3, 1), /* [8] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 3, 1), /* [9] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 3, 1), /* [10] */ + /* tag -> t: tag1, tag2, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(7), 4, -1), /* [11] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 4, -1), /* [12] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 4, -1), /* [13] */ + /* tag -> t/m2: tag1, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(7), 4, 1), /* [14] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 4, 1), /* [15] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 4, 1), /* [16] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"), + }, + .expect = { + .raw_types = { + BTF_FUNC_ENC(NAME_NTH(3), 16), /* [1] */ + BTF_STRUCT_ENC(NAME_NTH(4), 2, 8), /* [2] */ + BTF_MEMBER_ENC(NAME_NTH(5), 15, 0), + BTF_MEMBER_ENC(NAME_NTH(6), 15, 32), + BTF_DECL_TAG_ENC(NAME_NTH(7), 1, -1), /* [3] */ + BTF_DECL_TAG_ENC(NAME_NTH(7), 1, 1), /* [4] */ + BTF_DECL_TAG_ENC(NAME_NTH(7), 2, -1), /* [5] */ + BTF_DECL_TAG_ENC(NAME_NTH(7), 2, 1), /* [6] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 1, -1), /* [7] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 1, 1), /* [8] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 2, -1), /* [9] */ + BTF_DECL_TAG_ENC(NAME_NTH(8), 2, 1), /* [10] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 1, -1), /* [11] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 1, 1), /* [12] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 2, -1), /* [13] */ + BTF_DECL_TAG_ENC(NAME_NTH(9), 2, 1), /* [14] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [15] */ + BTF_FUNC_PROTO_ENC(0, 2), /* [16] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 15), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 15), + BTF_END_RAW, + }, + BTF_STR_SEC("\0a1\0a2\0f\0t\0m1\0m2\0tag1\0tag2\0tag3"), + }, + .permute = true, + .permute_opts = { + .ids = permute_ids_sort_by_kind_name, + }, +}, }; static int btf_type_size(const struct btf_type *t) @@ -8078,9 +8148,9 @@ static void dump_btf_strings(const char *strs, __u32 len) } } -static void do_test_dedup(unsigned int test_num) +static void do_test_dedup_permute(unsigned int test_num) { - struct btf_dedup_test *test = &dedup_tests[test_num - 1]; + struct btf_dedup_permute_test *test = &dedup_permute_tests[test_num - 1]; __u32 test_nr_types, expect_nr_types, test_btf_size, expect_btf_size; const struct btf_header *test_hdr, *expect_hdr; struct btf *test_btf = NULL, *expect_btf = NULL; @@ -8124,11 +8194,20 @@ static void do_test_dedup(unsigned int test_num) goto done; } - test->opts.sz = sizeof(test->opts); - err = btf__dedup(test_btf, &test->opts); - if (CHECK(err, "btf_dedup failed errno:%d", err)) { - err = -1; - goto done; + if (test->permute) { + test->permute_opts.sz = sizeof(test->permute_opts); + err = btf__permute(test_btf, &test->permute_opts); + if (CHECK(err, "btf_permute failed errno:%d", err)) { + err = -1; + goto done; + } + } else { + test->dedup_opts.sz = sizeof(test->dedup_opts); + err = btf__dedup(test_btf, &test->dedup_opts); + if (CHECK(err, "btf_dedup failed errno:%d", err)) { + err = -1; + goto done; + } } test_btf_data = btf__raw_data(test_btf, &test_btf_size); @@ -8249,7 +8328,7 @@ void test_btf(void) do_test_file(i); for (i = 1; i <= ARRAY_SIZE(info_raw_tests); i++) do_test_info_raw(i); - for (i = 1; i <= ARRAY_SIZE(dedup_tests); i++) - do_test_dedup(i); + for (i = 1; i <= ARRAY_SIZE(dedup_permute_tests); i++) + do_test_dedup_permute(i); test_pprint(); } -- 2.34.1 The previous commit implemented BTF sorting verification and binary search algorithm in libbpf. This patch enables this functionality in the kernel. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- v2->v3: - Include btf_sort.c directly in btf.c to reduce function call overhead --- kernel/bpf/btf.c | 34 ++++++++++++++++++---------------- 1 file changed, 18 insertions(+), 16 deletions(-) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 0de8fc8a0e0b..df258815a6ca 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -33,6 +33,7 @@ #include #include #include "../tools/lib/bpf/relo_core.h" +#include "../tools/lib/bpf/btf_sort.h" /* BTF (BPF Type Format) is the meta data format which describes * the data types of BPF program/map. Hence, it basically focus @@ -259,6 +260,7 @@ struct btf { void *nohdr_data; struct btf_header hdr; u32 nr_types; /* includes VOID for base BTF */ + u32 nr_sorted_types; /* All named types in the sorted BTF instance */ u32 types_size; u32 data_size; refcount_t refcnt; @@ -527,6 +529,11 @@ static bool btf_type_is_decl_tag_target(const struct btf_type *t) btf_type_is_var(t) || btf_type_is_typedef(t); } +static u32 btf_start_id(const struct btf *btf) +{ + return btf->start_id + (btf->base_btf ? 0 : 1); +} + bool btf_is_vmlinux(const struct btf *btf) { return btf->kernel_btf && !btf->base_btf; @@ -546,22 +553,7 @@ u32 btf_nr_types(const struct btf *btf) s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) { - const struct btf_type *t; - const char *tname; - u32 i, total; - - total = btf_nr_types(btf); - for (i = 1; i < total; i++) { - t = btf_type_by_id(btf, i); - if (BTF_INFO_KIND(t->info) != kind) - continue; - - tname = btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; - } - - return -ENOENT; + return _btf_find_by_name_kind(btf, 1, name, kind); } s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p) @@ -6230,6 +6222,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name if (err) goto errout; + btf_check_sorted(btf, 1); refcount_set(&btf->refcnt, 1); return btf; @@ -6362,6 +6355,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data, base_btf = vmlinux_btf; } + btf_check_sorted(btf, btf_nr_types(base_btf)); btf_verifier_env_free(env); refcount_set(&btf->refcnt, 1); return btf; @@ -9577,3 +9571,11 @@ bool btf_param_match_suffix(const struct btf *btf, param_name += len - suffix_len; return !strncmp(param_name, suffix, suffix_len); } + +/* + * btf_sort.c is included directly to avoid function call overhead + * when accessing BTF private data, as this file is shared between + * libbpf and kernel and may be called frequently (especially when + * funcgraph-args or func-args tracing options are enabled). + */ +#include "../../tools/lib/bpf/btf_sort.c" -- 2.34.1