From nobody Sun Feb 8 17:36:45 2026 Received: from mail-pj1-f49.google.com (mail-pj1-f49.google.com [209.85.216.49]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 200C82F83AB for ; Mon, 20 Oct 2025 09:39:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.49 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760953199; cv=none; b=jADRhRh0YQu8R0tqbgFbkYTm/xjV+zp3rGnmuxkBDSp5ZxLm8pXY/zxNY/hlOeQMYIvFd2CSOhuRLjXMfU4DiY2td0XiDz4pOlRak5gUYfVO8GKNOsK9QWzUZcC89wlId5oazfExGbSdb5Sc+WcCZEvGEwfKxuiIoPDaW1xXx88= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760953199; c=relaxed/simple; bh=48MK3IVfFVIaq7wrnsVF/K0MzzVMTV/KG7hzT0Z3/M8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=fXj9AY2A339CBLXlifMyYV57t1K/SlKG6sJsn6vPKQwXBRoUEu9RjvpWpQ8bUgdR3HFJ8DgCgozw2aj26HgIjSRNEdiqDD0OvzF10W6bjg0po+M0s62+y98wDp8AlYdIXiymj83oQ+PJBguIlgBgnLlR05o+NUSuo04xWbpYs4A= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=k4V9tj2K; arc=none smtp.client-ip=209.85.216.49 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="k4V9tj2K" Received: by mail-pj1-f49.google.com with SMTP id 98e67ed59e1d1-339d53f4960so4185549a91.3 for ; Mon, 20 Oct 2025 02:39:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1760953196; x=1761557996; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=mnQBz8V7xJnhNMAVJ8Qx/WiCqXppL5cjjvDtlWap4Rc=; b=k4V9tj2Kgt391tuMso8RQF7TVzNCmuZcFgDNDzuW3jiNVLGsCjkHzE2Nkw9UQIx/+g GK3OfWFQJc3oHLvN+dwIpHN0U/z9bXykyWNAA4bPQo/TVatCs7NNUIs9k5ymWNhvTL0Q VtEThZQqQqxl5WzFTcU+kr22BesP41jm5o0y3kPuJItMiyFVogXdtRtAJmjCytmEX7fY MFHHgmtnXWZf6tf7nmxVxnPrYRueLjwwpvHFq+se8eRUZGIt7ciwMeM2D29UF26PqW8o W9uW1nGmEwntJeRblsF4aJ4dyrpuH1kV4lzFZeajLeKC9MwLFGgkeyUV7RXfokE0a+Ei tr5A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1760953196; x=1761557996; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=mnQBz8V7xJnhNMAVJ8Qx/WiCqXppL5cjjvDtlWap4Rc=; b=d6igQoiPhZayS7amVXfmAFtOaihKsEm0ZmJE4JEav0QvN1gIw/StC4mRjkDGeT/WyD wpLZlR0Vjhq5IxGqeH9uSJy97gyqU05kC/leTyu6dE+B/352yM1RCI+etMluQIXBzKKL wc2g29+MOGsUwrucIOLOdYNFoo9jFuHho+4/gWStCA5NdCDjN7FeRWXEBr7UuIfWSkO3 HK9y0KppeSooSIIitfx4+YoX0nh1CGNXmdSrMvcm6/cJcE7ohlwf875F8kruLRsPQitS gZjT0zTLaf9Yv1z8OQKrNbnqEV47KfFAPcY0+30NAlgXzh+10o7Bxh2QozWo8+XvB0BV GO8g== X-Gm-Message-State: AOJu0YystyoUJrQyV92ZaWTsKiLAw+TKso16iYEhH09FjEnUcMmEpvbP qG1j14X0RuX5QPFhEXl3fZDdQV98FXmV2bXNaEBv5i6H0WTT55rXEw6r X-Gm-Gg: ASbGncsH7UYhrlAcV/lMz5S7T2i2AC3Z5dkMRv3WyuwsrvEF1Y+oHAQBeRuveOKxSDN gg7Yb9XTGN+FyuxQAuZJQuys/T1RPq/niec5JhKbaAmsT+Ld5y8DFVsk3bqBxIuyvoPdzqBEdBF DFnVlc/gcUErtJjl/fD/eQaM4l3efLEUe2l3x2kugR7y5AyF4sHozsBVfEe1gbMRmEyfrB3uL09 ktZn7KDZC+ZrixWgSrLhcs8div8b8YtZlsoEjppR+5p7yAsJmQTqMEVREV54Wc9aC6p8qiwgSDZ K3pUXc/lISvxUzQ2Di4XER3o7WPcllaIqKCVWp25YYoxJzN0gjVBVUhqBc4raKDwVKMUAcFVYWH v0vVfBJ7yBn3p/4IDt9IZV6booP6FsfeJxL/wuQIoTpda2WbDRKBRMysX9/eNM8ji1W83KZVYBX NeLwKzeN3vJeZaVXNWkN0nm7iZSKc= X-Google-Smtp-Source: AGHT+IFq4jAfdunN994zMtpGY6z7ZtgIpa/ZkkUYRiTLUokYOLHEZQIi0txVjYjHlZ2s2/heMjdjUQ== X-Received: by 2002:a17:90b:3d8a:b0:330:6f16:c4e0 with SMTP id 98e67ed59e1d1-33bcf87f43dmr18355066a91.12.1760953196306; Mon, 20 Oct 2025 02:39:56 -0700 (PDT) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-33d5de8091fsm7617200a91.19.2025.10.20.02.39.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 20 Oct 2025 02:39:55 -0700 (PDT) From: Donglin Peng To: ast@kernel.org Cc: linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Eduard Zingerman , Andrii Nakryiko , Alan Maguire , Song Liu , pengdonglin Subject: [RFC PATCH v2 2/5] btf: sort BTF types by kind and name to enable binary search Date: Mon, 20 Oct 2025 17:39:38 +0800 Message-Id: <20251020093941.548058-3-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251020093941.548058-1-dolinux.peng@gmail.com> References: <20251020093941.548058-1-dolinux.peng@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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 a= rg_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); =20 static inline bool btf_type_is_struct_ptr(struct btf *btf, const struct bt= f_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_i= d, 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) +=3D kmem_cache_iter.o ifeq ($(CONFIG_DMA_SHARED_BUFFER),y) obj-$(CONFIG_BPF_SYSCALL) +=3D dmabuf_iter.o endif +obj-$(CONFIG_BPF_SYSCALL) +=3D btf_sort.o =20 CFLAGS_REMOVE_percpu_freelist.o =3D $(CC_FLAGS_FTRACE) CFLAGS_REMOVE_bpf_lru_list.o =3D $(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; } =20 -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; } =20 -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 =3D btf_type_cnt(btf); - for (i =3D btf->start_id; i < total; i++) { - t =3D btf_type_by_id(btf, i); - if (BTF_INFO_KIND(t->info) !=3D kind) - continue; + return btf->nr_sorted_types; +} =20 - tname =3D 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 =3D nr; +} =20 - btf =3D btf->base_btf; - } while (btf); +u32 btf_type_cnt(const struct btf *btf) +{ + return btf->start_id + btf->nr_types; +} =20 - 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); } =20 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; =20 + btf_check_sorted(btf, 1); refcount_set(&btf->refcnt, 1); =20 return btf; @@ -6371,6 +6369,7 @@ static struct btf *btf_parse_module(const char *modul= e_name, const void *data, base_btf =3D vmlinux_btf; } =20 + 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 :=3D 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 */ =20 +#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; } =20 +__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 =3D 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); } =20 -static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id, - const char *type_name, __u32 kind) -{ - __u32 i, nr_types =3D btf__type_cnt(btf); - - if (kind =3D=3D BTF_KIND_UNKN || !strcmp(type_name, "void")) - return 0; - - for (i =3D start_id; i < nr_types; i++) { - const struct btf_type *t =3D btf__type_by_id(btf, i); - const char *name; - - if (btf_kind(t) !=3D kind) - continue; - name =3D 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_n= ame, __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); } =20 __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); } =20 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); =20 /* @@ -3600,7 +3600,7 @@ int btf__dedup(struct btf *btf, const struct btf_dedu= p_opts *opts) pr_debug("btf_dedup_ref_types failed: %s\n", errstr(err)); goto done; } - err =3D btf_dedup_compact_types(d); + err =3D 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 *bt= f, const struct btf_dedup_o =20 d->btf =3D btf; d->btf_ext =3D OPTS_GET(opts, btf_ext, NULL); + d->sort_by_kind_name =3D OPTS_GET(opts, sort_by_kind_name, false); =20 d->dedup_table =3D 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; } =20 +static __u32 *get_sorted_canon_types(struct btf_dedup *d, __u32 *cnt) +{ + int i, j, id, types_cnt =3D 0; + __u32 *sorted_ids; + + for (i =3D 0, id =3D d->btf->start_id; i < d->btf->nr_types; i++, id++) + if (d->map[id] =3D=3D id) + ++types_cnt; + + sorted_ids =3D calloc(types_cnt, sizeof(*sorted_ids)); + if (!sorted_ids) + return NULL; + + for (j =3D 0, i =3D 0, id =3D d->btf->start_id; i < d->btf->nr_types; i++= , id++) + if (d->map[id] =3D=3D id) + sorted_ids[j++] =3D id; + + qsort_r(sorted_ids, types_cnt, sizeof(*sorted_ids), + btf_compare_type_kinds_names, d->btf); + + *cnt =3D types_cnt; + + return sorted_ids; +} + +/* + * Compact and sort BTF types. + * + * Similar to btf_dedup_compact_types, but additionally sorts the btf_type= s. + */ +static int btf__dedup_compact_and_sort_types(struct btf_dedup *d) +{ + __u32 canon_types_cnt =3D 0, canon_types_len =3D 0; + __u32 *new_offs =3D NULL, *canon_types =3D NULL; + const struct btf_type *t; + void *p, *new_types =3D NULL; + int i, id, len, err; + + /* we are going to reuse hypot_map to store compaction remapping */ + d->hypot_map[0] =3D 0; + /* base BTF types are not renumbered */ + for (id =3D 1; id < d->btf->start_id; id++) + d->hypot_map[id] =3D id; + for (i =3D 0, id =3D d->btf->start_id; i < d->btf->nr_types; i++, id++) + d->hypot_map[id] =3D BTF_UNPROCESSED_ID; + + canon_types =3D get_sorted_canon_types(d, &canon_types_cnt); + if (!canon_types) { + err =3D -ENOMEM; + goto out_err; + } + + for (i =3D 0; i < canon_types_cnt; i++) { + id =3D canon_types[i]; + t =3D btf__type_by_id(d->btf, id); + len =3D btf_type_size(t); + if (len < 0) { + err =3D len; + goto out_err; + } + canon_types_len +=3D len; + } + + new_offs =3D calloc(canon_types_cnt, sizeof(*new_offs)); + new_types =3D calloc(canon_types_len, 1); + if (!new_types || !new_offs) { + err =3D -ENOMEM; + goto out_err; + } + + p =3D new_types; + + for (i =3D 0; i < canon_types_cnt; i++) { + id =3D canon_types[i]; + t =3D btf__type_by_id(d->btf, id); + len =3D btf_type_size(t); + memcpy(p, t, len); + d->hypot_map[id] =3D d->btf->start_id + i; + new_offs[i] =3D p - new_types; + p +=3D 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 =3D new_types; + d->btf->type_offs =3D new_offs; + d->btf->types_data_cap =3D canon_types_len; + d->btf->type_offs_cap =3D canon_types_cnt; + d->btf->nr_types =3D canon_types_cnt; + d->btf->hdr->type_len =3D canon_types_len; + d->btf->hdr->str_off =3D d->btf->hdr->type_len; + d->btf->raw_size =3D d->btf->hdr->hdr_len + d->btf->hdr->type_len + d->bt= f->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 orig= inal * `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 *n= b) +{ + 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 =3D (struct btf *)priv; + struct btf_type *ta =3D btf_type_by_id(btf, *(__u32 *)a); + struct btf_type *tb =3D 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 =3D btf_kind(ta); + kb =3D btf_kind(tb); + na =3D btf__str_by_offset(btf, ta->name_off); + nb =3D 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 =3D=3D BTF_KIND_UNKN || !strcmp(type_name, "void")) + return 0; + + do { + if (btf__nr_sorted_types(btf)) { + /* binary search */ + __s32 start, end, mid, found =3D -1; + int ret; + + start =3D btf__start_id(btf); + end =3D start + btf__nr_sorted_types(btf) - 1; + /* found the leftmost btf_type that matches */ + while(start <=3D end) { + mid =3D start + (end - start) / 2; + t =3D btf_type_by_id(btf, mid); + tname =3D btf__name_by_offset(btf, t->name_off); + ret =3D cmp_btf_kind_name(BTF_INFO_KIND(t->info), tname, + kind, type_name); + if (ret =3D=3D 0) + found =3D mid; + if (ret < 0) + start =3D mid + 1; + else if (ret >=3D 0) + end =3D mid - 1; + } + + if (found !=3D -1) + return found; + } else { + /* linear search */ + total =3D btf__type_cnt(btf); + for (i =3D btf__start_id(btf); i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (btf_kind(t) !=3D kind) + continue; + + tname =3D btf__name_by_offset(btf, t->name_off); + if (tname && !strcmp(tname, type_name)) + return i; + } + } + + btf =3D btf__base_btf(btf); + } while (btf && btf__start_id(btf) >=3D 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 =3D btf__type_cnt(btf); + if ((n - start_id) < BTF_CHECK_SORT_THRESHOLD) + return; + + n--; + nr_sorted_types =3D 0; + for (i =3D start_id; i < n; i++) { + int k =3D i + 1; + + t =3D btf_type_by_id(btf, i); + if (!btf__str_by_offset(btf, t->name_off)) + return; + + t =3D 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 =3D btf_type_by_id(btf, start_id); + if (t->name_off) + nr_sorted_types++; + if (nr_sorted_types >=3D 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_interna= l.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 st= ruct 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_m= ap); +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 cha= r *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); =20 static inline enum btf_func_linkage btf_func_linkage(const struct btf_type= *t) { --=20 2.34.1