| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <CAErzpmuVM4p3AxB5OTEOTNrtuv+BM+kFVXQ2w6qmBCwFky466Q@mail.gmail.com>
Date: Wed, 22 Oct 2025 12:47:00 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Alan Maguire <alan.maguire@...cle.com>
Cc: ast@...nel.org, linux-kernel@...r.kernel.org, bpf@...r.kernel.org,
Eduard Zingerman <eddyz87@...il.com>, Andrii Nakryiko <andrii.nakryiko@...il.com>,
Song Liu <song@...nel.org>, pengdonglin <pengdonglin@...omi.com>
Subject: Re: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable
binary search
On Wed, Oct 22, 2025 at 1:25 AM Alan Maguire <alan.maguire@...cle.com> wrote:
>
> On 20/10/2025 10:39, Donglin Peng wrote:
> > 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.
> >
>
> this looks great! one thing that might make libbpf integration easier
> though (and Andrii can probably best answer if it's actually a problem)
> - would it be possible to separate the libbpf and non-libbpf parts here;
> i.e have a patch that adds the libbpf stuff first, then re-use it in a
> separate patch for kernel sorting?
Thanks for the suggestion, I will split it in the next version.
>
> > Cc: Eduard Zingerman <eddyz87@...il.com>
> > Cc: Alexei Starovoitov <ast@...nel.org>
> > Cc: Andrii Nakryiko <andrii.nakryiko@...il.com>
> > Cc: Alan Maguire <alan.maguire@...cle.com>
> > Cc: Song Liu <song@...nel.org>
> > Co-developed-by: Eduard Zingerman <eddyz87@...il.com>
> > Signed-off-by: pengdonglin <pengdonglin@...omi.com>
> > Signed-off-by: Donglin Peng <dolinux.peng@...il.com>
> > ---
> > 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 <byteswap.h>
> > #include <endian.h>
> > #include <stdio.h>
> > @@ -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 <linux/bpf.h>
> > +#include <linux/btf.h>
> > +#include <linux/string.h>
> > +
> > +#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)
> > {
>
Powered by blists - more mailing lists