Change btf_find_by_name_kind() to search the local BTF first, then fall back to the base BTF. This can skip traversing the large vmlinux BTF when the target type resides in a kernel module's BTF, thereby significantly improving lookup performance. In a test searching for the btf_type of function ext2_new_inode located in the ext2 kernel module: Before: 408631 ns After: 499 ns Performance improvement: ~819x faster Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- include/linux/btf.h | 1 + kernel/bpf/btf.c | 27 ++++++++++++++++++--------- 2 files changed, 19 insertions(+), 9 deletions(-) diff --git a/include/linux/btf.h b/include/linux/btf.h index f06976ffb63f..ddc53a7ac7cd 100644 --- a/include/linux/btf.h +++ b/include/linux/btf.h @@ -220,6 +220,7 @@ bool btf_is_module(const struct btf *btf); bool btf_is_vmlinux(const struct btf *btf); struct module *btf_try_get_module(const struct btf *btf); u32 btf_nr_types(const struct btf *btf); +u32 btf_type_cnt(const struct btf *btf); struct btf *btf_base_btf(const struct btf *btf); bool btf_type_is_i32(const struct btf_type *t); bool btf_type_is_i64(const struct btf_type *t); diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 0de8fc8a0e0b..c414cf37e1bd 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -544,22 +544,31 @@ u32 btf_nr_types(const struct btf *btf) return total; } +u32 btf_type_cnt(const struct btf *btf) +{ + return btf->start_id + btf->nr_types; +} + 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; + do { + total = btf_type_cnt(btf); + for (i = btf->start_id; 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; - } + tname = btf_name_by_offset(btf, t->name_off); + if (!strcmp(tname, name)) + return i; + } + + btf = btf->base_btf; + } while (btf); return -ENOENT; } -- 2.34.1 This patch implements sorting of BTF types by their kind and name, enabling the use of binary search for type lookups. To share logic between kernel and libbpf, a new btf_sort.c file is introduced containing common sorting functionality. The sorting is performed during btf__dedup() when the new sort_by_kind_name option in btf_dedup_opts is enabled. For vmlinux and kernel module BTF, btf_check_sorted() verifies whether the types are sorted and binary search can be used. 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 --- include/linux/btf.h | 20 +++- kernel/bpf/Makefile | 1 + kernel/bpf/btf.c | 39 ++++---- kernel/bpf/btf_sort.c | 2 + tools/lib/bpf/Build | 2 +- tools/lib/bpf/btf.c | 163 +++++++++++++++++++++++++++----- tools/lib/bpf/btf.h | 2 + tools/lib/bpf/btf_sort.c | 159 +++++++++++++++++++++++++++++++ tools/lib/bpf/libbpf_internal.h | 6 ++ 9 files changed, 347 insertions(+), 47 deletions(-) create mode 100644 kernel/bpf/btf_sort.c create mode 100644 tools/lib/bpf/btf_sort.c diff --git a/include/linux/btf.h b/include/linux/btf.h index ddc53a7ac7cd..c6fe5e689ab9 100644 --- a/include/linux/btf.h +++ b/include/linux/btf.h @@ -221,7 +221,10 @@ bool btf_is_vmlinux(const struct btf *btf); struct module *btf_try_get_module(const struct btf *btf); u32 btf_nr_types(const struct btf *btf); u32 btf_type_cnt(const struct btf *btf); -struct btf *btf_base_btf(const struct btf *btf); +u32 btf_start_id(const struct btf *btf); +u32 btf_nr_sorted_types(const struct btf *btf); +void btf_set_nr_sorted_types(struct btf *btf, u32 nr); +struct btf* btf_base_btf(const struct btf *btf); bool btf_type_is_i32(const struct btf_type *t); bool btf_type_is_i64(const struct btf_type *t); bool btf_type_is_primitive(const struct btf_type *t); @@ -595,6 +598,10 @@ int get_kern_ctx_btf_id(struct bpf_verifier_log *log, enum bpf_prog_type prog_ty bool btf_types_are_same(const struct btf *btf1, u32 id1, const struct btf *btf2, u32 id2); int btf_check_iter_arg(struct btf *btf, const struct btf_type *func, int arg_idx); +int btf_compare_type_kinds_names(const void *a, const void *b, void *priv); +s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name, + u32 kind); +void btf_check_sorted(struct btf *btf, int start_id); static inline bool btf_type_is_struct_ptr(struct btf *btf, const struct btf_type *t) { @@ -683,5 +690,16 @@ static inline int btf_check_iter_arg(struct btf *btf, const struct btf_type *fun { return -EOPNOTSUPP; } +static inline int btf_compare_type_kinds_names(const void *a, const void *b, void *priv) +{ + return -EOPNOTSUPP; +} +static inline s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name, + u32 kind) +{ + return -EOPNOTSUPP; +} +static inline void btf_check_sorted(struct btf *btf, int start_id); +{} #endif #endif diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile index 7fd0badfacb1..c9d8f986c7e1 100644 --- a/kernel/bpf/Makefile +++ b/kernel/bpf/Makefile @@ -56,6 +56,7 @@ obj-$(CONFIG_BPF_SYSCALL) += kmem_cache_iter.o ifeq ($(CONFIG_DMA_SHARED_BUFFER),y) obj-$(CONFIG_BPF_SYSCALL) += dmabuf_iter.o endif +obj-$(CONFIG_BPF_SYSCALL) += btf_sort.o CFLAGS_REMOVE_percpu_freelist.o = $(CC_FLAGS_FTRACE) CFLAGS_REMOVE_bpf_lru_list.o = $(CC_FLAGS_FTRACE) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index c414cf37e1bd..11b05f4eb07d 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -259,6 +259,7 @@ struct btf { void *nohdr_data; struct btf_header hdr; u32 nr_types; /* includes VOID for base BTF */ + u32 nr_sorted_types; u32 types_size; u32 data_size; refcount_t refcnt; @@ -544,33 +545,29 @@ u32 btf_nr_types(const struct btf *btf) return total; } -u32 btf_type_cnt(const struct btf *btf) +u32 btf_start_id(const struct btf *btf) { - return btf->start_id + btf->nr_types; + return btf->start_id; } -s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) +u32 btf_nr_sorted_types(const struct btf *btf) { - const struct btf_type *t; - const char *tname; - u32 i, total; - - do { - total = btf_type_cnt(btf); - for (i = btf->start_id; i < total; i++) { - t = btf_type_by_id(btf, i); - if (BTF_INFO_KIND(t->info) != kind) - continue; + return btf->nr_sorted_types; +} - tname = btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; - } +void btf_set_nr_sorted_types(struct btf *btf, u32 nr) +{ + btf->nr_sorted_types = nr; +} - btf = btf->base_btf; - } while (btf); +u32 btf_type_cnt(const struct btf *btf) +{ + return btf->start_id + btf->nr_types; +} - return -ENOENT; +s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) +{ + return find_btf_by_name_kind(btf, 1, name, kind); } s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p) @@ -6239,6 +6236,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; @@ -6371,6 +6369,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; diff --git a/kernel/bpf/btf_sort.c b/kernel/bpf/btf_sort.c new file mode 100644 index 000000000000..898f9189952c --- /dev/null +++ b/kernel/bpf/btf_sort.c @@ -0,0 +1,2 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) +#include "../../tools/lib/bpf/btf_sort.c" diff --git a/tools/lib/bpf/Build b/tools/lib/bpf/Build index c80204bb72a2..ed7c2506e22d 100644 --- a/tools/lib/bpf/Build +++ b/tools/lib/bpf/Build @@ -1,4 +1,4 @@ libbpf-y := libbpf.o bpf.o nlattr.o btf.o libbpf_utils.o \ netlink.o bpf_prog_linfo.o libbpf_probes.o hashmap.o \ btf_dump.o ringbuf.o strset.o linker.o gen_loader.o relo_core.o \ - usdt.o zip.o elf.o features.o btf_iter.o btf_relocate.o + usdt.o zip.o elf.o features.o btf_iter.o btf_relocate.o btf_sort.o diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 18907f0fcf9f..87e47f0b78ba 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -1,6 +1,9 @@ // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) /* Copyright (c) 2018 Facebook */ +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif #include #include #include @@ -92,6 +95,9 @@ struct btf { * - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; + /* number of named types in this BTF instance for binary search + */ + __u32 nr_sorted_types; /* if not NULL, points to the base BTF on top of which the current * split BTF is based */ @@ -619,6 +625,21 @@ __u32 btf__type_cnt(const struct btf *btf) return btf->start_id + btf->nr_types; } +__u32 btf__start_id(const struct btf *btf) +{ + return btf->start_id; +} + +__u32 btf__nr_sorted_types(const struct btf *btf) +{ + return btf->nr_sorted_types; +} + +void btf__set_nr_sorted_types(struct btf *btf, __u32 nr) +{ + btf->nr_sorted_types = nr; +} + const struct btf *btf__base_btf(const struct btf *btf) { return btf->base_btf; @@ -915,38 +936,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 find_btf_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 find_btf_by_name_kind(btf, 1, type_name, kind); } static bool btf_is_modifiable(const struct btf *btf) @@ -3411,6 +3410,7 @@ static int btf_dedup_struct_types(struct btf_dedup *d); static int btf_dedup_ref_types(struct btf_dedup *d); static int btf_dedup_resolve_fwds(struct btf_dedup *d); static int btf_dedup_compact_types(struct btf_dedup *d); +static int btf_dedup_compact_and_sort_types(struct btf_dedup *d); static int btf_dedup_remap_types(struct btf_dedup *d); /* @@ -3600,7 +3600,7 @@ int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts) pr_debug("btf_dedup_ref_types failed: %s\n", errstr(err)); goto done; } - err = btf_dedup_compact_types(d); + err = btf_dedup_compact_and_sort_types(d); if (err < 0) { pr_debug("btf_dedup_compact_types failed: %s\n", errstr(err)); goto done; @@ -3649,6 +3649,8 @@ struct btf_dedup { * BTF is considered to be immutable. */ bool hypot_adjust_canon; + /* Sort btf_types by kind and time */ + bool sort_by_kind_name; /* Various option modifying behavior of algorithm */ struct btf_dedup_opts opts; /* temporary strings deduplication state */ @@ -3741,6 +3743,7 @@ static struct btf_dedup *btf_dedup_new(struct btf *btf, const struct btf_dedup_o d->btf = btf; d->btf_ext = OPTS_GET(opts, btf_ext, NULL); + d->sort_by_kind_name = OPTS_GET(opts, sort_by_kind_name, false); d->dedup_table = hashmap__new(hash_fn, btf_dedup_equal_fn, NULL); if (IS_ERR(d->dedup_table)) { @@ -5288,6 +5291,116 @@ static int btf_dedup_compact_types(struct btf_dedup *d) return 0; } +static __u32 *get_sorted_canon_types(struct btf_dedup *d, __u32 *cnt) +{ + int i, j, id, types_cnt = 0; + __u32 *sorted_ids; + + for (i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++) + if (d->map[id] == id) + ++types_cnt; + + sorted_ids = calloc(types_cnt, sizeof(*sorted_ids)); + if (!sorted_ids) + return NULL; + + for (j = 0, i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++) + if (d->map[id] == id) + sorted_ids[j++] = id; + + qsort_r(sorted_ids, types_cnt, sizeof(*sorted_ids), + btf_compare_type_kinds_names, d->btf); + + *cnt = types_cnt; + + return sorted_ids; +} + +/* + * Compact and sort BTF types. + * + * Similar to btf_dedup_compact_types, but additionally sorts the btf_types. + */ +static int btf__dedup_compact_and_sort_types(struct btf_dedup *d) +{ + __u32 canon_types_cnt = 0, canon_types_len = 0; + __u32 *new_offs = NULL, *canon_types = NULL; + const struct btf_type *t; + void *p, *new_types = NULL; + int i, id, len, err; + + /* we are going to reuse hypot_map to store compaction remapping */ + d->hypot_map[0] = 0; + /* base BTF types are not renumbered */ + for (id = 1; id < d->btf->start_id; id++) + d->hypot_map[id] = id; + for (i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++) + d->hypot_map[id] = BTF_UNPROCESSED_ID; + + canon_types = get_sorted_canon_types(d, &canon_types_cnt); + if (!canon_types) { + err = -ENOMEM; + goto out_err; + } + + for (i = 0; i < canon_types_cnt; i++) { + id = canon_types[i]; + t = btf__type_by_id(d->btf, id); + len = btf_type_size(t); + if (len < 0) { + err = len; + goto out_err; + } + canon_types_len += len; + } + + new_offs = calloc(canon_types_cnt, sizeof(*new_offs)); + new_types = calloc(canon_types_len, 1); + if (!new_types || !new_offs) { + err = -ENOMEM; + goto out_err; + } + + p = new_types; + + for (i = 0; i < canon_types_cnt; i++) { + id = canon_types[i]; + t = btf__type_by_id(d->btf, id); + len = btf_type_size(t); + memcpy(p, t, len); + d->hypot_map[id] = d->btf->start_id + i; + new_offs[i] = p - new_types; + p += len; + } + + /* shrink struct btf's internal types index and update btf_header */ + free(d->btf->types_data); + free(d->btf->type_offs); + d->btf->types_data = new_types; + d->btf->type_offs = new_offs; + d->btf->types_data_cap = canon_types_len; + d->btf->type_offs_cap = canon_types_cnt; + d->btf->nr_types = canon_types_cnt; + d->btf->hdr->type_len = canon_types_len; + d->btf->hdr->str_off = d->btf->hdr->type_len; + d->btf->raw_size = d->btf->hdr->hdr_len + d->btf->hdr->type_len + d->btf->hdr->str_len; + free(canon_types); + return 0; + +out_err: + free(canon_types); + free(new_types); + free(new_offs); + return err; +} + +static int btf_dedup_compact_and_sort_types(struct btf_dedup *d) +{ + if (d->sort_by_kind_name) + return btf__dedup_compact_and_sort_types(d); + return btf_dedup_compact_types(d); +} + /* * Figure out final (deduplicated and compacted) type ID for provided original * `type_id` by first resolving it into corresponding canonical type ID and diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h index ccfd905f03df..9a7cfe6b4bb3 100644 --- a/tools/lib/bpf/btf.h +++ b/tools/lib/bpf/btf.h @@ -251,6 +251,8 @@ struct btf_dedup_opts { size_t sz; /* optional .BTF.ext info to dedup along the main BTF info */ struct btf_ext *btf_ext; + /* Sort btf_types by kind and name */ + bool sort_by_kind_name; /* force hash collisions (used for testing) */ bool force_collisions; size_t :0; diff --git a/tools/lib/bpf/btf_sort.c b/tools/lib/bpf/btf_sort.c new file mode 100644 index 000000000000..2ad4a56f1c08 --- /dev/null +++ b/tools/lib/bpf/btf_sort.c @@ -0,0 +1,159 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) + +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif + +#ifdef __KERNEL__ +#include +#include +#include + +#define btf_type_by_id (struct btf_type *)btf_type_by_id +#define btf__str_by_offset btf_str_by_offset +#define btf__name_by_offset btf_name_by_offset +#define btf__type_cnt btf_nr_types +#define btf__start_id btf_start_id +#define btf__nr_sorted_types btf_nr_sorted_types +#define btf__set_nr_sorted_types btf_set_nr_sorted_types +#define btf__base_btf btf_base_btf +#define libbpf_err(x) x + +#else + +#include "btf.h" +#include "bpf.h" +#include "libbpf.h" +#include "libbpf_internal.h" + +#endif /* __KERNEL__ */ + +/* Skip the sorted check if number of btf_types is below threshold + */ +#define BTF_CHECK_SORT_THRESHOLD 8 + +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. + */ +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; + int ka, kb; + + /* ta w/o name is greater than tb */ + if (!ta->name_off && tb->name_off) + return 1; + /* tb w/o name is smaller than ta */ + if (ta->name_off && !tb->name_off) + return -1; + + ka = btf_kind(ta); + kb = btf_kind(tb); + na = btf__str_by_offset(btf, ta->name_off); + nb = btf__str_by_offset(btf, tb->name_off); + + return cmp_btf_kind_name(ka, na, kb, nb); +} + +__s32 find_btf_by_name_kind(const struct btf *btf, int start_id, + const char *type_name, __u32 kind) +{ + const struct btf_type *t; + const char *tname; + __u32 i, total; + + if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void")) + return 0; + + do { + if (btf__nr_sorted_types(btf)) { + /* binary search */ + __s32 start, end, mid, found = -1; + int ret; + + start = btf__start_id(btf); + end = start + btf__nr_sorted_types(btf) - 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__name_by_offset(btf, t->name_off); + ret = cmp_btf_kind_name(BTF_INFO_KIND(t->info), tname, + kind, type_name); + if (ret == 0) + found = mid; + if (ret < 0) + start = mid + 1; + else if (ret >= 0) + end = mid - 1; + } + + if (found != -1) + return found; + } else { + /* linear search */ + total = btf__type_cnt(btf); + for (i = btf__start_id(btf); i < total; i++) { + t = btf_type_by_id(btf, i); + if (btf_kind(t) != kind) + continue; + + tname = btf__name_by_offset(btf, t->name_off); + if (tname && !strcmp(tname, type_name)) + return i; + } + } + + btf = btf__base_btf(btf); + } while (btf && btf__start_id(btf) >= start_id); + + return libbpf_err(-ENOENT); +} + +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 ((n - start_id) < BTF_CHECK_SORT_THRESHOLD) + return; + + n--; + nr_sorted_types = 0; + for (i = start_id; i < n; i++) { + int k = i + 1; + + t = btf_type_by_id(btf, i); + if (!btf__str_by_offset(btf, t->name_off)) + return; + + t = btf_type_by_id(btf, k); + if (!btf__str_by_offset(btf, t->name_off)) + return; + + if (btf_compare_type_kinds_names(&i, &k, btf) > 0) + return; + + if (t->name_off) + nr_sorted_types++; + } + + t = btf_type_by_id(btf, start_id); + if (t->name_off) + nr_sorted_types++; + if (nr_sorted_types >= BTF_CHECK_SORT_THRESHOLD) + btf__set_nr_sorted_types(btf, nr_sorted_types); +} + diff --git a/tools/lib/bpf/libbpf_internal.h b/tools/lib/bpf/libbpf_internal.h index 35b2527bedec..f71f3e70c51c 100644 --- a/tools/lib/bpf/libbpf_internal.h +++ b/tools/lib/bpf/libbpf_internal.h @@ -248,6 +248,12 @@ const struct btf_type *skip_mods_and_typedefs(const struct btf *btf, __u32 id, _ const struct btf_header *btf_header(const struct btf *btf); void btf_set_base_btf(struct btf *btf, const struct btf *base_btf); int btf_relocate(struct btf *btf, const struct btf *base_btf, __u32 **id_map); +int btf_compare_type_kinds_names(const void *a, const void *b, void *priv); +__s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char *type_name, __u32 kind); +void btf_check_sorted(struct btf *btf, int start_id); +__u32 btf__start_id(const struct btf *btf); +__u32 btf__nr_sorted_types(const struct btf *btf); +void btf__set_nr_sorted_types(struct btf *btf, __u32 nr); static inline enum btf_func_linkage btf_func_linkage(const struct btf_type *t) { -- 2.34.1 Now that libbpf supports sorted BTF types, add a check to determine whether binary search can be used for type lookups. 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/lib/bpf/btf.c | 6 ++++++ 1 file changed, 6 insertions(+) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 87e47f0b78ba..92c370fe9b79 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -1091,6 +1091,8 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b if (err) goto done; + btf_check_sorted(btf, btf->start_id); + done: if (err) { btf__free(btf); @@ -1714,6 +1716,7 @@ static void btf_invalidate_raw_data(struct btf *btf) free(btf->raw_data_swapped); btf->raw_data_swapped = NULL; } + btf->nr_sorted_types = 0; } /* Ensure BTF is ready to be modified (by splitting into a three memory @@ -5456,6 +5459,9 @@ static int btf_dedup_remap_types(struct btf_dedup *d) } } + if (d->sort_by_kind_name) + btf_check_sorted(d->btf, d->btf->start_id); + if (!d->btf_ext) return 0; -- 2.34.1 Verify that BTF deduplication and sorting 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 | 171 +++++++++++++++++++ 1 file changed, 171 insertions(+) diff --git a/tools/testing/selftests/bpf/prog_tests/btf.c b/tools/testing/selftests/bpf/prog_tests/btf.c index 8a9ba4292109..244f9d535bc2 100644 --- a/tools/testing/selftests/bpf/prog_tests/btf.c +++ b/tools/testing/selftests/bpf/prog_tests/btf.c @@ -8022,6 +8022,177 @@ static struct btf_dedup_test dedup_tests[] = { BTF_STR_SEC("\0foo\0x\0y\0foo_ptr"), }, }, +{ + .descr = "dedup_sort: strings deduplication", + .input = { + .raw_types = { + BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 4), + BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 64, 8), + BTF_TYPE_INT_ENC(NAME_NTH(3), BTF_INT_SIGNED, 0, 32, 4), + BTF_TYPE_INT_ENC(NAME_NTH(4), BTF_INT_SIGNED, 0, 64, 8), + BTF_TYPE_INT_ENC(NAME_NTH(5), BTF_INT_SIGNED, 0, 32, 4), + BTF_END_RAW, + }, + BTF_STR_SEC("\0int\0long int\0int\0long int\0int"), + }, + .expect = { + .raw_types = { + BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 4), + BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 64, 8), + BTF_END_RAW, + }, + BTF_STR_SEC("\0int\0long int"), + }, + .opts = { + .sort_by_kind_name = true, + }, +}, +{ + .descr = "dedup_sort: func/func_arg/var tags", + .input = { + .raw_types = { + /* int */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ + /* static int t */ + BTF_VAR_ENC(NAME_NTH(1), 1, 0), /* [2] */ + /* void f(int a1, int a2) */ + BTF_FUNC_PROTO_ENC(0, 2), /* [3] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(3), 1), + BTF_FUNC_ENC(NAME_NTH(4), 3), /* [4] */ + /* tag -> t */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [5] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [6] */ + /* tag -> func */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 4, -1), /* [7] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 4, -1), /* [8] */ + /* tag -> func arg a1 */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 4, 1), /* [9] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 4, 1), /* [10] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0t\0a1\0a2\0f\0tag"), + }, + .expect = { + .raw_types = { + BTF_FUNC_ENC(NAME_NTH(4), 7), /* [1] */ + BTF_VAR_ENC(NAME_NTH(1), 6, 0), /* [2] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [3] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1), /* [4] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1), /* [5] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [6] */ + BTF_FUNC_PROTO_ENC(0, 2), /* [7] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 6), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(3), 6), + BTF_END_RAW, + }, + BTF_STR_SEC("\0t\0a1\0a2\0f\0tag"), + }, + .opts = { + .sort_by_kind_name = true, + }, +}, +{ + .descr = "dedup_sort: func/func_param 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] */ + /* void f(int a1, int a2) */ + BTF_FUNC_PROTO_ENC(0, 2), /* [4] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 1), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1), + BTF_FUNC_ENC(NAME_NTH(3), 4), /* [5] */ + /* tag -> f: tag1, tag2 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 3, -1), /* [6] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 3, -1), /* [7] */ + /* tag -> f/a2: tag1, tag2 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 3, 1), /* [8] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 3, 1), /* [9] */ + /* tag -> f: tag1, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 5, -1), /* [10] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 5, -1), /* [11] */ + /* tag -> f/a2: tag1, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 5, 1), /* [12] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 5, 1), /* [13] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0a1\0a2\0f\0tag1\0tag2\0tag3"), + }, + .expect = { + .raw_types = { + BTF_FUNC_ENC(NAME_NTH(3), 9), /* [1] */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, -1), /* [2] */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, 1), /* [3] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1), /* [4] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1), /* [5] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, -1), /* [6] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, 1), /* [7] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [8] */ + BTF_FUNC_PROTO_ENC(0, 2), /* [9] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 8), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 8), + BTF_END_RAW, + }, + BTF_STR_SEC("\0a1\0a2\0f\0tag1\0tag2\0tag3"), + }, + .opts = { + .sort_by_kind_name = true, + }, +}, +{ + .descr = "dedup_sort: struct/struct_member tags", + .input = { + .raw_types = { + /* int */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ + BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [2] */ + BTF_MEMBER_ENC(NAME_NTH(2), 1, 0), + BTF_MEMBER_ENC(NAME_NTH(3), 1, 32), + BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [3] */ + BTF_MEMBER_ENC(NAME_NTH(2), 1, 0), + BTF_MEMBER_ENC(NAME_NTH(3), 1, 32), + /* tag -> t: tag1, tag2 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 2, -1), /* [4] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [5] */ + /* tag -> t/m2: tag1, tag2 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 2, 1), /* [6] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 2, 1), /* [7] */ + /* tag -> t: tag1, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 3, -1), /* [8] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 3, -1), /* [9] */ + /* tag -> t/m2: tag1, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 3, 1), /* [10] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 3, 1), /* [11] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0t\0m1\0m2\0tag1\0tag2\0tag3"), + }, + .expect = { + .raw_types = { + BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [1] */ + BTF_MEMBER_ENC(NAME_NTH(2), 8, 0), + BTF_MEMBER_ENC(NAME_NTH(3), 8, 32), + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, -1), /* [2] */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, 1), /* [3] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1), /* [4] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1), /* [5] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, -1), /* [6] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, 1), /* [7] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [8] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0t\0m1\0m2\0tag1\0tag2\0tag3"), + }, + .opts = { + .sort_by_kind_name = true, + }, +}, }; static int btf_type_size(const struct btf_type *t) -- 2.34.1 Pahole v1.32 and later supports BTF sorting. Add a new configuration option to control whether to enable this feature for vmlinux and kernel modules. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- kernel/bpf/Kconfig | 8 ++++++++ scripts/Makefile.btf | 5 +++++ 2 files changed, 13 insertions(+) diff --git a/kernel/bpf/Kconfig b/kernel/bpf/Kconfig index eb3de35734f0..08251a250f06 100644 --- a/kernel/bpf/Kconfig +++ b/kernel/bpf/Kconfig @@ -101,4 +101,12 @@ config BPF_LSM If you are unsure how to answer this question, answer N. +config BPF_SORT_BTF_BY_KIND_NAME + bool "Sort BTF types by kind and name" + depends on BPF_SYSCALL + help + This option sorts BTF types in vmlinux and kernel modules by their + kind and name, enabling binary search for btf_find_by_name_kind() + and significantly improving its lookup performance. + endmenu # "BPF subsystem" diff --git a/scripts/Makefile.btf b/scripts/Makefile.btf index db76335dd917..3f1a0b3c3f3f 100644 --- a/scripts/Makefile.btf +++ b/scripts/Makefile.btf @@ -29,6 +29,11 @@ ifneq ($(KBUILD_EXTMOD),) module-pahole-flags-$(call test-ge, $(pahole-ver), 128) += --btf_features=distilled_base endif +ifeq ($(call test-ge, $(pahole-ver), 132),y) +pahole-flags-$(CONFIG_BPF_SORT_BTF_BY_KIND_NAME) += --btf_features=sort +module-pahole-flags-$(CONFIG_BPF_SORT_BTF_BY_KIND_NAME) += --btf_features=sort +endif + endif pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) += --lang_exclude=rust -- 2.34.1