From nobody Sat Feb 7 12:19:38 2026 Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) (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 B36B0307481 for ; Mon, 27 Oct 2025 13:54:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.48 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761573278; cv=none; b=lYI8SV8GxYLUFvw+z+qbl0i4QhJDkWAx9CRLecpX7K4NoxR1otRk+IXQUFUQRYfxUjts/kQVKgfL65h71NbUhMflifGXL/etIyqycm+iF2dUHeWWmf1qsdPsWc2PRL4wR8XcsCduFnn9e0oFpC+ytRzPyrlv2N+WhWrRe2gVQ0c= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761573278; c=relaxed/simple; bh=kTJF/ccwNDazzGvPAMxXtm7s7Se9RjNlffjPWzGQmjg=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=u9PgsIFoPePeRq3F0QAMhOeeQ7G4B6RmVRE8x4K2bIR2iWRFS2HtJm4FikMCo9KCJO8ARdhAvu7pr92BRVAQ3VKGll9fL1OyPViULS2Ep02hqvXuxPAR2eIqgrRE6f0OmMNxYZ9W4MmgrC/zsafn3nQ9kdfHE0raqPjdKxe1VUs= 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=mlvpf7ul; arc=none smtp.client-ip=209.85.216.48 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="mlvpf7ul" Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-33bafd5d2adso4464217a91.3 for ; Mon, 27 Oct 2025 06:54:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1761573276; x=1762178076; 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=9OlcMMK8Cd+16DJOp+mJkp5fktcMj5EaiRx1/DUOfXA=; b=mlvpf7ulFCtL/oaJn6oOkQfZjjqKo7zW9nCF8rP0jeqigmP22QQ+pxHCmY4rmEmGs8 SVcrddNztJ+TP9xj2Rb7a2LIfu7x1SLfUxswprdwEh2tLwMgSSeoAFE8wnI11NEUg9j/ Y2Fj7jWn0syjb3cFVwl8Y2Oo1xcnKCt7DyVGvzDsrX7xC6b/wQ5g3NLmvQ1tf+RMMasv hsWBJxg3qKwXn4bpoNzVRiO+vC6vvY6u5/Oz9iO65ydXjIbalKRxuhzri3oDVcnIyoEO xV2FgmS2Z0g7Kx7ALA13swYLsYKi00JY66xTLtBuMynfy1PliEjF9JdItGxI/zv4kfe1 mm+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761573276; x=1762178076; 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=9OlcMMK8Cd+16DJOp+mJkp5fktcMj5EaiRx1/DUOfXA=; b=Bg3EY7Ft44I8nvvEEy23zX8C+AB0aHlG/F+/rxexyfilRIvEz3nf8kA8GH4tp1RAK+ 4m7JusxJ3GOD2i0VBvnyOxq68+ftPZNs+XDvYm/rN0VfJhvquLBViiz9ugNZHz96np9m V7ldjM//0u+W6Ifkmi8fUfVrpr6qb3VJjWeme/ckiP0yFBKlzt+5f9BtRxqbFYdvTLVS egruqFpsV6NTF+s9VlumaYWres/VpUPxV+I++6dzhEhekhWPeGuqsEi0gHxEYj8BtuYs 821CkH8T65xK7Fwic3KailxdsFYTg425Mx7Z/kaafYvuBZXPfx++r6cQQPt0CrzKe7rs GIZA== X-Gm-Message-State: AOJu0Yz70dCJ5+gb0quj2IgvS7xBvtde2/vHHgihMmxnDsdt4v8nSwlj Yf/d0RHDS7rPINFZJkZ6ZZBBgL7A/FrY1rRbz/y127GsZYtJQJUJmEYH X-Gm-Gg: ASbGncsNDdWsc3PaGWpRu43lCWjGeQojj4M2L7UXpXi+G2MrdMZpLDDwR+2J6D1EGWf 26wudtIzW+pZPxlbqISnR9qNYi8EDkHS5UepyIRCvEKYN4cpYv9k8AZM3oMzrjSTqOfQ1bs/iWa dPbCGv6zIUyXO5IN2fot7T4B6hcQx08TnQxwbFB1TaPakh5skS0uZGEyqb/RIaOGEWdLsHmU07b 3IQGQ991RPE2Na+TWP4LYv3lMY30jgRqs1kLD6TFQmNVhmpo3qp80RX/ORuLFY60d+8eYF+BrKB kfv3Lmtw8VPab77V/3AEfy5vKaqvLfaPwp+TfvpDeUSMAAFu/FIKGu/h8WbDN9GTyzAraFuSwKv VIAXH715MwieLZCVkr8EXmVzc8UneQpiz7bkaFcS0h0rDMBBMovR8mMuNRL0LqRnEecSyM+1xSS Kq/mlB7Ysyun/mG8if X-Google-Smtp-Source: AGHT+IEX5c4gQQrdCPE+LcKI9qXW9JDLRDKeH4KCfWLifwt768E51P1orSn78v1yDOwdfFDfTJyNmg== X-Received: by 2002:a17:90b:3c42:b0:33b:ae28:5eae with SMTP id 98e67ed59e1d1-33bcf87ac11mr43573347a91.14.1761573275831; Mon, 27 Oct 2025 06:54:35 -0700 (PDT) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-33fed70a83csm8574361a91.4.2025.10.27.06.54.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 27 Oct 2025 06:54:34 -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 v3 1/3] btf: implement BTF type sorting for accelerated lookups Date: Mon, 27 Oct 2025 21:54:21 +0800 Message-Id: <20251027135423.3098490-2-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251027135423.3098490-1-dolinux.peng@gmail.com> References: <20251027135423.3098490-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 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() int= erface - 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" =20 #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; } =20 +__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); } =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 _btf_find_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 _btf_find_by_name_kind(btf, 1, type_name, kind); } =20 static bool btf_is_modifiable(const struct btf *btf) @@ -1091,6 +1081,7 @@ static struct btf *btf_new(const void *data, __u32 si= ze, struct btf *base_btf, b err =3D err ?: btf_sanity_check(btf); if (err) goto done; + btf_check_sorted(btf, btf->start_id); =20 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 =3D NULL; } + if (btf->nr_sorted_types) + btf->nr_sorted_types =3D 0; } =20 /* 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 =3D false; return libbpf_err(err); } + +struct btf_permute; + +static struct btf_permute *btf_permute_new(struct btf *btf, const struct b= tf_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 prov= ided, + * 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 =3D 0; + + if (!OPTS_VALID(opts, btf_permute_opts)) + return libbpf_err(-EINVAL); + + p =3D 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 =3D -ENOMEM; + goto done; + } + + err =3D btf_permute_shuffle_types(p); + if (err < 0) { + pr_debug("btf_permute_shuffle_types failed: %s\n", errstr(err)); + goto done; + } + err =3D 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 b= tf_permute_opts *opts) +{ + struct btf_permute *p =3D calloc(1, sizeof(struct btf_permute)); + __u32 *map; + int err =3D 0; + + if (!p) + return ERR_PTR(-ENOMEM); + + p->btf =3D btf; + p->btf_ext =3D OPTS_GET(opts, btf_ext, NULL); + p->ids =3D OPTS_GET(opts, ids, NULL); + if (!p->ids) { + err =3D -EINVAL; + goto done; + } + + map =3D calloc(btf->nr_types, sizeof(*map)); + if (!map) { + err =3D -ENOMEM; + goto done; + } + p->map =3D 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 =3D 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 =3D p->btf; + const struct btf_type *t; + __u32 *new_offs =3D NULL; + void *l, *new_types =3D NULL; + int i, id, len, err; + + new_offs =3D calloc(btf->nr_types, sizeof(*new_offs)); + new_types =3D calloc(btf->hdr->type_len, 1); + if (!new_types || !new_offs) { + err =3D -ENOMEM; + goto out_err; + } + + l =3D new_types; + for (i =3D 0; i < btf->nr_types; i++) { + id =3D p->ids[i]; + t =3D btf__type_by_id(btf, id); + len =3D btf_type_size(t); + memcpy(l, t, len); + new_offs[i] =3D l - new_types; + p->map[id - btf->start_id] =3D btf->start_id + i; + l +=3D len; + } + + free(btf->types_data); + free(btf->type_offs); + btf->types_data =3D new_types; + btf->type_offs =3D 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 orig= inal + * ones. The map from original to a corresponding permuted type ID is stor= ed + * in btf_permute->map and is populated during shuffle phase. During remap= ping + * 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 =3D p->btf; + int i, r; + + for (i =3D 0; i < btf->nr_types; i++) { + struct btf_type *t =3D btf_type_by_id(btf, btf->start_id + i); + struct btf_field_iter it; + __u32 *type_id; + + r =3D btf_field_iter_init(&it, t, BTF_FIELD_ITER_IDS); + if (r) + return r; + + while ((type_id =3D btf_field_iter_next(&it))) { + __u32 new_id =3D *type_id; + + /* skip references that point into the base BTF */ + if (new_id < btf->start_id) + continue; + + new_id =3D p->map[new_id - btf->start_id]; + if (new_id > BTF_MAX_NR_TYPES) + return -EINVAL; + + *type_id =3D new_id; + } + } + + if (!p->btf_ext) + return 0; + + r =3D 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 =3D ctx; + __u32 new_type_id =3D *type_id; + + /* skip references that point into the base BTF */ + if (new_type_id < p->btf->start_id) + return 0; + + new_type_id =3D p->map[*type_id - p->btf->start_id]; + if (new_type_id > BTF_MAX_NR_TYPES) + return -EINVAL; + + *type_id =3D 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 bt= f *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 struc= t btf_dedup_opts *opts); */ LIBBPF_API int btf__relocate(struct btf *btf, const struct btf *base_btf); =20 +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; =20 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 threshol= d. + * 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 *n= b) +{ + 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 =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; + bool anon_a, anon_b; + int ka, kb; + + na =3D btf__str_by_offset(btf, ta->name_off); + nb =3D btf__str_by_offset(btf, tb->name_off); + anon_a =3D str_is_empty(na); + anon_b =3D 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 =3D btf_kind(ta); + kb =3D 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 st= art_id, + const char *type_name, __u32 kind) +{ + const struct btf_type *t; + const char *tname; + int err =3D -ENOENT; + + if (!btf) + goto out; + + if (start_id < btf__start_id(btf)) { + err =3D __btf_find_by_name_kind(btf->base_btf, start_id, type_name, kind= ); + if (err =3D=3D -ENOENT) + start_id =3D btf__start_id(btf); + } + + if (err =3D=3D -ENOENT) { + if (btf->nr_sorted_types) { + /* binary search */ + __s32 start, end, mid, found =3D -1; + int ret; + + start =3D start_id; + end =3D start + btf->nr_sorted_types - 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__str_by_offset(btf, t->name_off); + ret =3D cmp_btf_kind_name(BTF_INFO_KIND(t->info), tname, + kind, type_name); + if (ret < 0) + start =3D mid + 1; + else { + if (ret =3D=3D 0) + found =3D mid; + end =3D mid - 1; + } + } + + if (found !=3D -1) + return found; + } else { + /* linear search */ + __u32 i, total; + + total =3D btf__type_cnt(btf); + for (i =3D start_id; i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (btf_kind(t) !=3D kind) + continue; + + tname =3D 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 sta= rt_id, + const char *type_name, __u32 kind) +{ + if (kind =3D=3D 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 =3D btf__type_cnt(btf); + if (btf->nr_types < BTF_CHECK_SORT_THRESHOLD) + return; + + n--; + nr_sorted_types =3D 0; + for (i =3D start_id; i < n; i++) { + int k =3D i + 1; + + if (btf_compare_type_kinds_names(&i, &k, btf) > 0) + return; + + t =3D btf_type_by_id(btf, k); + if (!str_is_empty(btf__str_by_offset(btf, t->name_off))) + nr_sorted_types++; + } + + t =3D 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 =3D 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, c= onst 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 =20 #define LIBBPF_MAJOR_VERSION 1 -#define LIBBPF_MINOR_VERSION 7 +#define LIBBPF_MINOR_VERSION 8 =20 #endif /* __LIBBPF_VERSION_H */ --=20 2.34.1 From nobody Sat Feb 7 12:19:38 2026 Received: from mail-pf1-f174.google.com (mail-pf1-f174.google.com [209.85.210.174]) (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 1E12B3081CD for ; Mon, 27 Oct 2025 13:54:40 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761573281; cv=none; b=Rp/ExVhRPHb94fA8TBoNgJZDMerAONEFHMN8N+oYpO2ZLxIU6pCDppOxKc5lNmGVE3Ph2jvy8j/P5sLhjtZ0axJ01lsFvsFk/b9jvNwPy/u1VsZ+iRlxPCxb09O5z/0Kv8KHaye0d74Pe9gOyhrQL03t9m/B3VLBl+kHMyYZNzc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761573281; c=relaxed/simple; bh=a2vWknJBLfGI/zn/aoQrvNPJmduxdpV0+V2L95agYGo=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=JQMIT3N778TRNT+qKUytU99A15k1f3KWqyjxs298R/aIDk6E9jckHXjQpzopdSSZON9qOS23WcnRZH99xDty+cBVQoIkDpUsvUYWL9jI+hkczDLLUWVuaWjvTQCWNjtpNe8Lh0RgLS103U51IdmZOCu/1RlzLn+AY+eVjdhNWV4= 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=ls/pWkuR; arc=none smtp.client-ip=209.85.210.174 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="ls/pWkuR" Received: by mail-pf1-f174.google.com with SMTP id d2e1a72fcca58-78125ed4052so5594907b3a.0 for ; Mon, 27 Oct 2025 06:54:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1761573279; x=1762178079; 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=PULKnB7zB8mjvxqnQKYFYWmpI5jL7Y4AmR36CypPlxc=; b=ls/pWkuRZfztTsMi4aUO50AvMIAijbkkP/kRisxGBVOsHTaPaJHH9LBkTp631SuEmU pHCpY3gPUjve8lYVxW4intZyqtm7mkWoEWO8FxA9aNkHC6wqdI2FMuJkyKer29au5QDN 4SHlTPUaZbbIPfnV4iwa7+KrARyzFUKxDOy+ewPM1laabpdbUELYr0DH8YBRGJ0cQAjp 8mVBH/+wz0nv2PY25+3TsEOwJr5lXoP/p+9iCr3C3d57TSwxhd7lP+08pDd2yB5/d9BZ AdJWgMEPCve6xsZiSYZiGcdem43CffR+DlBGdT/a4mrESScxyL9wjleQAyNX0oWucQor N9Kw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761573279; x=1762178079; 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=PULKnB7zB8mjvxqnQKYFYWmpI5jL7Y4AmR36CypPlxc=; b=ayWYSDPgP/7zUTZjSkGXjj5RbP3EkVEiMjr0020xTQ0ftktiUc6Mn+JUAXGKcs0Dng pag12dFS5XU+Gd0vb9Aa0Q4rc2+1nXGEkk73LMoyHFOyFwO5uoheSBboIuHHaJogl76t YSvqScfhy5XwHzi/gmMMjh034pp2I8VKh+jCe9ztKerVcyOrYjbIPJQImVwkkvWXFqZY 2h1kBymz3xdY0eUxdVATJSAX3CsMQg7bgplWxk6QQR+N0MCyCUetDI7sBHueCaxo1cP1 SDvww73exTST6UC7K4/v8rresXUkN913otmq2duT2/DdPSRs7xYBuA6epERz/fysgOVH SCCQ== X-Gm-Message-State: AOJu0Yy8Pi72v0LiBf9QL3j5SXZoqmjMAC/Asv20o78sMtsknzLEBSrb I6Ja+XkqOKQCFDprXGkP+SdHzxhvFR/C9xgQgff7BD3h+GCDSIWj5E9YERn6hESy X-Gm-Gg: ASbGncvhb89BihQ8AovlBXGynmwjAcAqag86PajJymMy4kr/ckhD1SrP8bR6xyWfIct fCoiXH/MbILGJD71+h4kclnptQ0kSM5G3DWm/qYZ6sRq/IzcjjE4ANvcN/jpqdDLKH00xTXYTNX PI0Z5a7Hyf0xZcDKyJQWF3VhkqI9tiGhQ6l07AQKmc/ky6FU1P+zbJI1CJ8Wx39RylFSoZN5oZi pHico4RPz7miTRlIuaszv3qPvztrXk/+kL/ovNRDuREKyUliqDwlf5KGBYmeEoULOTn2e2ImdQc FpVuz0ThVFmPQ6emnzbH4u1SR5AxV72AXiBiV8+TN3mrc5ir4qICfFGjlcmUT4sOVu5wpc5ka1F dCpb3+B3ROB+e6Ok7ZVjKoP/pGraOpIoT6JuA+GKZn0s63QV5+w/a6yJyYfpujqwB0ICTQi3Fh2 ZoIDbli640QUZECUKXbpVuxqgvHDQ= X-Google-Smtp-Source: AGHT+IFnV9PyudavkwUaPZ+kQ2ILlWTFIEiZjdh7kZ2svze02eKMLqOGH6tVrMcgIL5JQBCMaj65Ug== X-Received: by 2002:a05:6a20:918c:b0:33d:5411:261b with SMTP id adf61e73a8af0-33d54112630mr16917813637.26.1761573279427; Mon, 27 Oct 2025 06:54:39 -0700 (PDT) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-33fed70a83csm8574361a91.4.2025.10.27.06.54.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 27 Oct 2025 06:54:38 -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 v3 2/3] selftests/bpf: add tests for BTF type permutation Date: Mon, 27 Oct 2025 21:54:22 +0800 Message-Id: <20251027135423.3098490-3-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251027135423.3098490-1-dolinux.peng@gmail.com> References: <20251027135423.3098490-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" 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/s= elftests/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; }; =20 -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; }; =20 -static struct btf_dedup_test dedup_tests[] =3D { +static __u32 permute_ids_sort_by_kind_name[] =3D {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[] =3D { =20 { .descr =3D "dedup: unused strings filtering", @@ -7105,7 +7109,7 @@ static struct btf_dedup_test dedup_tests[] =3D { }, BTF_STR_SEC("\0s\0x"), }, - .opts =3D { + .dedup_opts =3D { .force_collisions =3D true, /* force hash collisions */ }, }, @@ -7151,7 +7155,7 @@ static struct btf_dedup_test dedup_tests[] =3D { }, BTF_STR_SEC("\0s\0x"), }, - .opts =3D { + .dedup_opts =3D { .force_collisions =3D true, /* force hash collisions */ }, }, @@ -7354,7 +7358,7 @@ static struct btf_dedup_test dedup_tests[] =3D { }, BTF_STR_SEC("\0.bss\0t"), }, - .opts =3D { + .dedup_opts =3D { .force_collisions =3D true }, }, @@ -8022,6 +8026,72 @@ static struct btf_dedup_test dedup_tests[] =3D { BTF_STR_SEC("\0foo\0x\0y\0foo_ptr"), }, }, +{ + .descr =3D "permute: func/func_param/struct/struct_member tags", + .input =3D { + .raw_types =3D { + /* 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 =3D { + .raw_types =3D { + 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 =3D true, + .permute_opts =3D { + .ids =3D permute_ids_sort_by_kind_name, + }, +}, }; =20 static int btf_type_size(const struct btf_type *t) @@ -8078,9 +8148,9 @@ static void dump_btf_strings(const char *strs, __u32 = len) } } =20 -static void do_test_dedup(unsigned int test_num) +static void do_test_dedup_permute(unsigned int test_num) { - struct btf_dedup_test *test =3D &dedup_tests[test_num - 1]; + struct btf_dedup_permute_test *test =3D &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 =3D NULL, *expect_btf =3D NULL; @@ -8124,11 +8194,20 @@ static void do_test_dedup(unsigned int test_num) goto done; } =20 - test->opts.sz =3D sizeof(test->opts); - err =3D btf__dedup(test_btf, &test->opts); - if (CHECK(err, "btf_dedup failed errno:%d", err)) { - err =3D -1; - goto done; + if (test->permute) { + test->permute_opts.sz =3D sizeof(test->permute_opts); + err =3D btf__permute(test_btf, &test->permute_opts); + if (CHECK(err, "btf_permute failed errno:%d", err)) { + err =3D -1; + goto done; + } + } else { + test->dedup_opts.sz =3D sizeof(test->dedup_opts); + err =3D btf__dedup(test_btf, &test->dedup_opts); + if (CHECK(err, "btf_dedup failed errno:%d", err)) { + err =3D -1; + goto done; + } } =20 test_btf_data =3D btf__raw_data(test_btf, &test_btf_size); @@ -8249,7 +8328,7 @@ void test_btf(void) do_test_file(i); for (i =3D 1; i <=3D ARRAY_SIZE(info_raw_tests); i++) do_test_info_raw(i); - for (i =3D 1; i <=3D ARRAY_SIZE(dedup_tests); i++) - do_test_dedup(i); + for (i =3D 1; i <=3D ARRAY_SIZE(dedup_permute_tests); i++) + do_test_dedup_permute(i); test_pprint(); } --=20 2.34.1 From nobody Sat Feb 7 12:19:38 2026 Received: from mail-pj1-f50.google.com (mail-pj1-f50.google.com [209.85.216.50]) (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 D0C3B3064AA for ; Mon, 27 Oct 2025 13:54:43 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.50 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761573285; cv=none; b=F0b9ejGrPVg7XniaEpedKaeXnrIuKyMezQTsxSpiGjw1Cov27YU6tfvq28a9/PAiKLNj6tP93Zzvo9KoYI+Oq2azGxec/nwyy6qvdXs37zmal+BFebEFEko9Okm11IQ61j2ybcL6FnB37dZDsqk5s+Zut2/Qe8EnS4aCnRxTrpc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761573285; c=relaxed/simple; bh=Cjh5/g2g/jA0t8pIW0Qr1oO+2rUFIay2nimYcNijtxc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=UyHmaw4YlMjMde8Tnk2ukZtb3TN1+MMeTZU09At4UcUWkfcppNNa8P5zPAqJtIfkVbTypEssBzs+SatCKuIzek1IJr3E4NmsvK5b0lv6xdrwZBBZckOfaoguD8pQAg3O8m7tPfGQXukaWCWwbs+ur/Hxq1rinylKqPBVHcI5zWE= 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=UEe77FDh; arc=none smtp.client-ip=209.85.216.50 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="UEe77FDh" Received: by mail-pj1-f50.google.com with SMTP id 98e67ed59e1d1-33d28dbced5so5840276a91.2 for ; Mon, 27 Oct 2025 06:54:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1761573283; x=1762178083; 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=bYRuzhTmcuAouHjw8Rk9AXVRkzW/8jCaMjKPsnybwR4=; b=UEe77FDhBefI1TZyhPC+L7bujvwCmN9JFl5N/ynlvMW9Yta2uM1ParX99BgOL0/diF Pl9Zhjh/awViZmb01clgiupNu14ok8fjpri6B+shjdTsyvLi0T1aRrjvlgP5JfeqbVKZ w5wLTQTmVJDlVnOhJ49U3R9GkiXzmhz3t5vckp2ij/hezQNgftHwz6CwoWfFKxM/tzRa Hj2bmeCv7jLfviSk9y3Yi8fOlBDQ9mePfc3r0a5dCOjViRjMbDJ9Y09bRchkMLcarHkW 5B9YD1aNRckoY9GlY41uRuTvBWkWZkrc8ZiO5L2OoeBcDe62qMhnpGj4ykw/3f0gg8zY CLzw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761573283; x=1762178083; 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=bYRuzhTmcuAouHjw8Rk9AXVRkzW/8jCaMjKPsnybwR4=; b=P8OwvY89anS5B+AVBhiM3RPPpHS0e7k/ZI74dPP0oezx8rFeUCZ/U/lYDE2QGjWQEx 9bZxN4KRgf4eX7OD/V10TFCHUi11rD4A663kduGuCXbItKyIP6pkW4wgqswqVS9Li0sH KwXdQMOwvWxI2a5ufewQU88N2drav85tvcUuxgvsa7koCqz4jUohaROK5nw2UHUD70E7 LxoXcwrOardJBOOEFQBYdc0J1D4DLsAGdQj2+J0k8YMdperjibeimjj2J/dLVBenys0q 4EdkPMQD98dxOSHFrt/AP7zWPsbvyVlYeosfuxlrk39U+olSdbOmruCsRA6l4UM0ECmT 4XJA== X-Gm-Message-State: AOJu0YxdhX+gm4kQW2yTJgYYbCVbPHMMTWmukefMytydXbtAqF/GinGF aLt8l/kkyVbX3WpiBWKQnV2n3lDlcZfy6Fmg2Zn8KJf8yRGY+9rQDM33/dTR9eXh X-Gm-Gg: ASbGncu1RGBpCQbY9+VmHqWQUusNud+mEYdpiPZ6TCbKPDEhCJ1m/HO6j6+LGWz0Eyi 4qB+mgIQdO8VG24n3VWpc9guSWG8iUDSDdLG74fuz7UMIU1fexCFw+r/FfCYMcHDHcdQT3NiHXy 5p865KH48WpX+ocfhj2WT6J5jEU0CvFzKiUVaqj7xjehur12GYSLh7u6dGD3oP+YKbxj/8aBoD8 9kWSUm3R8hkVsLS/c+fT7qJ9ngnoBvgDOxddejE/rpmsdkg3tnkIVZGy8f/G+yI7tLtUaxYuH/b k06RMUKitpopOZjKFn+2vlhsixtlcP9t/xIYHHx324OEz2ausor71kewTfceWnWX89TXGU38Y7A k6fz2PD1Xi7Ti8ni8pe2hWC4JQwp5nzyRx7nwj4UmxYqB85iIq4OMhPrFMqfN4aRBX9bcWrj/x/ sJQvvrf+m+FWqi992E X-Google-Smtp-Source: AGHT+IHwNYL6A4DZns7ec+5bESV0e3nM9DzapwGirzgHfVhHI6fBerJH30YECQ5BiM9K/Yykza1d3g== X-Received: by 2002:a17:90b:5908:b0:33f:ee05:56e7 with SMTP id 98e67ed59e1d1-33fee0557f7mr10189589a91.16.1761573282951; Mon, 27 Oct 2025 06:54:42 -0700 (PDT) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-33fed70a83csm8574361a91.4.2025.10.27.06.54.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 27 Oct 2025 06:54:41 -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 v3 3/3] btf: Reuse libbpf code for BTF type sorting verification and binary search Date: Mon, 27 Oct 2025 21:54:23 +0800 Message-Id: <20251027135423.3098490-4-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251027135423.3098490-1-dolinux.peng@gmail.com> References: <20251027135423.3098490-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" 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" =20 /* 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 b= tf_type *t) btf_type_is_var(t) || btf_type_is_typedef(t); } =20 +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) =20 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 =3D btf_nr_types(btf); - for (i =3D 1; i < total; i++) { - t =3D btf_type_by_id(btf, i); - if (BTF_INFO_KIND(t->info) !=3D kind) - continue; - - tname =3D 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); } =20 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; =20 + btf_check_sorted(btf, 1); refcount_set(&btf->refcnt, 1); =20 return btf; @@ -6362,6 +6355,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; @@ -9577,3 +9571,11 @@ bool btf_param_match_suffix(const struct btf *btf, param_name +=3D 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" --=20 2.34.1