From nobody Tue Dec 2 02:52:23 2025 Received: from mail-pf1-f182.google.com (mail-pf1-f182.google.com [209.85.210.182]) (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 333343328EC for ; Mon, 17 Nov 2025 13:26:34 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763385995; cv=none; b=M12qJTDD3FFRF4RWzrbGx3U25DM3rAgSeGYvtBZp08aionRIp+AxK8HYQS7S4xpyotdmRyAcjm8ZeOLqcJEJBBGx3VVmwhny2Otzh+g1OGd4JvMzh6aLnOgtBoyBmkgiXqXRxLakq0bKgeYmzj32yFMU+CgW0EsiEezuW6Vr/ko= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763385995; c=relaxed/simple; bh=6VBbAusWLjZvaGOC/+K+V+im/qf4tqKKK59Uc/T8Ph0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=VLDpnNC30Kr0GxTmweVvsdiWm3iyA8P/jNpArz9ACH1jmgHgtrC8m+ouutIzRFDjpQM3IzqYc2PdEVuyu2y7nx8WitwBGXjRmMlWmRmzQvnxz4DiUF2SIpt7gswJt/O2KJ7H9Zoh3JqCAfAErJjtKnmhXNBjpgZTYqqtZIAhAOM= 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=Hff5GoYR; arc=none smtp.client-ip=209.85.210.182 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="Hff5GoYR" Received: by mail-pf1-f182.google.com with SMTP id d2e1a72fcca58-7aad4823079so3841614b3a.0 for ; Mon, 17 Nov 2025 05:26:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763385993; x=1763990793; 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=DBbxUx6nVTODhi42u5LXpziwCIk3CPqNxfSqUe5bn+c=; b=Hff5GoYRLNJS2BQp8bczKrl6ga8Z1VxA67Zyl9XibD6T74RYge340yv+LKxOlnjK4m RxRYjEYfiGf9BcDcbxdMPEPckM3C8jAt46ljcZ3zZsPCnmy6Qw9u7eDpUClGcodW62pA Abosi7oOSH9rIGVvhjYVUvmolmmxh/ky/rXvjLbvfHaL6laFtnCLr5kdwApvTrNBSn2j ngsG9PA1rTCtyYNntu4Jk1f2NlAGUmDxRN/2IiwtRNCgvkhjVYZaqiHJ5JDK6n48Zihw KYHgI5l1GweU3yNJhaEB9DpwVRZ+zTavsxX712DhHI1+u58gxLm5vBcaDGbwoV6eaLyV zylw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763385993; x=1763990793; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=DBbxUx6nVTODhi42u5LXpziwCIk3CPqNxfSqUe5bn+c=; b=HTf6Iau/Z2FYwnbOG04swSzK6d/IHxCW5aGUICCGnHwyLUt2VcuLGRQZJTqKT2NajW Rxj76fHqurKPQcRtAEEsCv5Q/Lhsy9LBC8pkJ4P6vgheqhhDluqMmlgsC9UGy+uFuBmn VuDWzbN2WDHind15CtFUTwY5v7CuQfDSPvFtZ3y1B6EajEvg7He4eCIxiiUAuOjIjyzd EnKnrx5v2XWN2BbH2a6EODO+Dhs6toXpqM7KpisnfscbJ5lyLY0JC8KJHIKX1FFaEg1D Bit2J2PUIM36W3Omo5DJih58bjcJczGFyPgYvkzRUZB0KFd5fkzxtE9jr0zIx+C1yx4t a+Cg== X-Forwarded-Encrypted: i=1; AJvYcCVa21TukH1JNMEEzPm2G9QQNdF/aUrRO2Hf08MTaoWiwfqN1KEmvLV+oFR3j3zr67feSZIEj/N8OtlkO+k=@vger.kernel.org X-Gm-Message-State: AOJu0YxVGlAptOHuQnCgulpZcybq5ohnqt+7xZYQDYK7Npx/tWwt1ObD EATC4Y5GwUjsuNHa9xbxThV5vhWK9QWjqUPOfHcnCjTStmaYKH28GMRd X-Gm-Gg: ASbGncvEq9lPWuGd7Bey+XErtYvGCyPU8QHzCaiHeqCfSHDTkm8MoFx9x4bBUKZjYvN chjV4B2vqvuj0mpYy3gLNHQWhx9EuXnmEXfU2pthSohMe2iRXZRV6wII9+zzM2wYp2Pfr162j3/ Fs6wKllQjjKVPZhH+jt1gJUP9h63NSUJ2xCno5gqh+H0eLK5MfIofefQ8mJUhBOZu/QCtrag7hC ZSzPX0auPzXfuPkD6/K4sWbxe2atyPm8bh/5IYW63MvZVm0t/H7WCbeLyds5uILNolhIMBO1a7f Wqxifb9dCIBqrRAu5qpCsSUKne25yprBUpbNUqbqt1ND9r49JOU2eUGeQ/gjhF/1JSNmbnv/9lx yIkBuzu0A3zCHFo55AwAAfXluSGIgYph+ErXGQbYmc4x536NqawqPLIkzquQEHnrG1RO0z5K+2X F19k0F5w108wzLWEumCPtGMSCyybM= X-Google-Smtp-Source: AGHT+IGbXFMdLTSTTZa1RPQl3rBb9sfz0EW9VgsJegiZI/gWTT/GjQE/NwLRF8MyNLpZwsf2nDRPyQ== X-Received: by 2002:a05:6a20:729d:b0:360:1b2e:5257 with SMTP id adf61e73a8af0-3601b2e54e1mr2570118637.2.1763385993351; Mon, 17 Nov 2025 05:26:33 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7b924cd89bcsm13220953b3a.15.2025.11.17.05.26.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Nov 2025 05:26:32 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v6 1/7] libbpf: Add BTF permutation support for type reordering Date: Mon, 17 Nov 2025 21:26:17 +0800 Message-Id: <20251117132623.3807094-2-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251117132623.3807094-1-dolinux.peng@gmail.com> References: <20251117132623.3807094-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" From: Donglin Peng Introduce btf__permute() API to allow in-place rearrangement of BTF types. This function reorganizes BTF type order according to a provided array of type IDs, updating all type references to maintain consistency. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 191 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 43 +++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 235 insertions(+) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 18907f0fcf9f..e3aa31c735c8 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -5829,3 +5829,194 @@ int btf__relocate(struct btf *btf, const struct btf= *base_btf) btf->owns_base =3D false; return libbpf_err(err); } + +struct btf_permute { + struct btf *btf; + __u32 *id_map; + __u32 offs; +}; + +/* Callback function to remap individual type ID references */ +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; + + /* invalid reference id */ + if (new_type_id >=3D btf__type_cnt(p->btf)) + return -EINVAL; + + new_type_id =3D p->id_map[new_type_id - p->offs]; + /* reference a dropped type is not allowed */ + if (new_type_id =3D=3D 0) + return -EINVAL; + + *type_id =3D new_type_id; + return 0; +} + +int btf__permute(struct btf *btf, __u32 *id_map, __u32 id_map_cnt, + const struct btf_permute_opts *opts) +{ + struct btf_permute p; + struct btf_ext *btf_ext; + void *next_type, *end_type; + void *nt, *new_types =3D NULL; + int err =3D 0, n, i, new_type_len; + __u32 *order_map =3D NULL; + __u32 offs, id, new_nr_types =3D 0; + + if (!OPTS_VALID(opts, btf_permute_opts)) + return libbpf_err(-EINVAL); + + if (btf__base_btf(btf)) { + /* + * For split BTF, the number of types added on the + * top of base BTF + */ + n =3D btf->nr_types; + offs =3D btf->start_id; + } else if (id_map[0] !=3D 0) { + /* id_map[0] must be 0 for base BTF */ + err =3D -EINVAL; + goto done; + } else { + /* include VOID type 0 for base BTF */ + n =3D btf__type_cnt(btf); + offs =3D 0; + } + + if (id_map_cnt !=3D n) + return libbpf_err(-EINVAL); + + /* used to record the storage sequence of types */ + order_map =3D calloc(n, sizeof(*id_map)); + if (!order_map) { + err =3D -ENOMEM; + goto done; + } + + new_types =3D calloc(btf->hdr->type_len, 1); + if (!new_types) { + err =3D -ENOMEM; + goto done; + } + + if (btf_ensure_modifiable(btf)) { + err =3D -ENOMEM; + goto done; + } + + for (i =3D 0; i < id_map_cnt; i++) { + id =3D id_map[i]; + /* + * 0: Drop the specified type (exclude base BTF type 0). + * For base BTF, type 0 is always preserved. + */ + if (id =3D=3D 0) + continue; + /* Invalid id */ + if (id < btf->start_id || id >=3D btf__type_cnt(btf)) { + err =3D -EINVAL; + goto done; + } + id -=3D offs; + /* Multiple types cannot be mapped to the same ID */ + if (order_map[id]) { + err =3D -EINVAL; + goto done; + } + order_map[id] =3D i + offs; + new_nr_types =3D max(id + 1, new_nr_types); + } + + /* Check for missing IDs */ + for (i =3D offs ? 0 : 1; i < new_nr_types; i++) { + if (order_map[i] =3D=3D 0) { + err =3D -EINVAL; + goto done; + } + } + + p.btf =3D btf; + p.id_map =3D id_map; + p.offs =3D offs; + nt =3D new_types; + for (i =3D offs ? 0 : 1; i < new_nr_types; i++) { + struct btf_field_iter it; + const struct btf_type *t; + __u32 *type_id; + int type_size; + + id =3D order_map[i]; + /* must be a valid type ID */ + t =3D btf__type_by_id(btf, id); + if (!t) { + err =3D -EINVAL; + goto done; + } + type_size =3D btf_type_size(t); + memcpy(nt, t, type_size); + + /* Fix up referenced IDs for BTF */ + err =3D btf_field_iter_init(&it, nt, BTF_FIELD_ITER_IDS); + if (err) + goto done; + while ((type_id =3D btf_field_iter_next(&it))) { + err =3D btf_permute_remap_type_id(type_id, &p); + if (err) + goto done; + } + + nt +=3D type_size; + } + + /* Fix up referenced IDs for btf_ext */ + btf_ext =3D OPTS_GET(opts, btf_ext, NULL); + if (btf_ext) { + err =3D btf_ext_visit_type_ids(btf_ext, btf_permute_remap_type_id, &p); + if (err) + goto done; + } + + new_type_len =3D nt - new_types; + next_type =3D new_types; + end_type =3D next_type + new_type_len; + i =3D 0; + while (next_type + sizeof(struct btf_type) <=3D end_type) { + btf->type_offs[i++] =3D next_type - new_types; + next_type +=3D btf_type_size(next_type); + } + + /* Resize */ + if (new_type_len < btf->hdr->type_len) { + void *tmp_types; + + tmp_types =3D realloc(new_types, new_type_len); + if (new_type_len && !tmp_types) { + err =3D -ENOMEM; + goto done; + } + new_types =3D tmp_types; + btf->nr_types =3D new_nr_types - (offs ? 0 : 1); + btf->type_offs_cap =3D btf->nr_types; + btf->types_data_cap =3D new_type_len; + btf->hdr->type_len =3D new_type_len; + btf->hdr->str_off =3D new_type_len; + btf->raw_size =3D btf->hdr->hdr_len + btf->hdr->type_len + btf->hdr->str= _len; + } + + free(order_map); + free(btf->types_data); + btf->types_data =3D new_types; + return 0; + +done: + free(order_map); + free(new_types); + return libbpf_err(err); +} diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h index ccfd905f03df..ec4e31e918c3 100644 --- a/tools/lib/bpf/btf.h +++ b/tools/lib/bpf/btf.h @@ -273,6 +273,49 @@ 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; + size_t :0; +}; +#define btf_permute_opts__last_field btf_ext + +/** + * @brief **btf__permute()** performs in-place BTF type rearrangement + * @param btf BTF object to permute + * @param id_map Array mapping original type IDs to new IDs + * @param id_map_cnt Number of elements in @id_map + * @param opts Optional parameters for BTF extension updates + * @return 0 on success, negative error code on failure + * + * **btf__permute()** rearranges BTF types according to the specified ID m= apping. + * The @id_map array defines the new type ID for each original type ID. + * + * For **base BTF**: + * - @id_map must include all types from ID 0 to `btf__type_cnt(btf)-1` + * - @id_map_cnt should be `btf__type_cnt(btf)` + * - Mapping uses `id_map[original_id] =3D new_id` + * + * For **split BTF**: + * - @id_map should cover only split types + * - @id_map_cnt should be `btf__type_cnt(btf) - btf__type_cnt(btf__base_b= tf(btf))` + * - Mapping uses `id_map[original_id - btf__type_cnt(btf__base_btf(btf))]= =3D new_id` + * + * Setting @id_map element to 0 (except `id_map[0]` for base BTF) drops th= e corresponding type. + * Dropped types must not be referenced by any retained types. After permu= tation, + * type references in BTF data and optional extension are updated automati= cally. + * + * Note: Dropping types may orphan some strings, requiring subsequent **bt= f__dedup()** + * to clean up unreferenced strings. + * + * On error, returns negative error code and sets errno: + * - `-EINVAL`: Invalid parameters or ID mapping (duplicates, out-of-ran= ge) + * - `-ENOMEM`: Memory allocation failure + */ +LIBBPF_API int btf__permute(struct btf *btf, __u32 *id_map, __u32 id_map_c= nt, + const struct btf_permute_opts *opts); + struct btf_dump; =20 struct btf_dump_opts { diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map index 8ed8749907d4..b778e5a5d0a8 100644 --- a/tools/lib/bpf/libbpf.map +++ b/tools/lib/bpf/libbpf.map @@ -451,4 +451,5 @@ LIBBPF_1.7.0 { global: bpf_map__set_exclusive_program; bpf_map__exclusive_program; + btf__permute; } LIBBPF_1.6.0; --=20 2.34.1 From nobody Tue Dec 2 02:52:23 2025 Received: from mail-pf1-f178.google.com (mail-pf1-f178.google.com [209.85.210.178]) (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 A9A4633290D for ; Mon, 17 Nov 2025 13:26:37 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763385999; cv=none; b=ab9DYEZko1AWG0fsUuYS7WYjs7mvfsWEP2quNilYLSb7zakVu68z5zqvKqmReo0HQWBExiLm3yYzxwXuLK8VI30IDYXVwjlqlzmcRdvNotNLppBWSmr/W661wIP54B9sHeeIi5CqzjpOfEGRgeaj4/PSYGLEV6YerLzwo5cW7NI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763385999; c=relaxed/simple; bh=fKl3CjkwUAvLf00MO5NwlJbM77gTj4jLjJopoNuYY3k=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=WPRSL+MBHd0uGClfCnGQnUJM4kQ3syhZOtOcv55ZMxJ6oe1gaA84JVVkSyNDhUP0/yMtljZ7Bc6ugD3qD3MejDudmXEd99D/T+70TkNJx/kBWcSptoQtK3RAWZxQUfyk7D0m3h6NsPurEV1RM5jllB19lRpM8X4CpqYB/AkX71s= 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=RTwk0+Zo; arc=none smtp.client-ip=209.85.210.178 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="RTwk0+Zo" Received: by mail-pf1-f178.google.com with SMTP id d2e1a72fcca58-7bab7c997eeso2891967b3a.0 for ; Mon, 17 Nov 2025 05:26:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763385997; x=1763990797; 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=KIFYlXOHz5whi3PfXinpEu8mupdZxU5ceyDILBZSC4o=; b=RTwk0+ZoTLLyy1LznHpukZKWcKj5E5vrIt9ohyGzNFE/NcRYrP4P8n5NpNBvMkIMYi ZqVsT9nygAzy/XKlYOS0dBbLEEXk5QK0eHIudd/vuQR1rz3mk2ksMFauyWu5MFPnDj6F bm+z5pwVMdUvXN+5F6kmvvMsG5Rj6Kgx9dXufrxIhU2U3/0tbmzrgTZe7TwlXy8jciRr XpEz+k6a8pLiEj+qXVXqV2rbjHSln9dEI+Bwlugtouo4gfZN2WH1+UnAO6HJ68ED7N69 d//FFPkO5U7J9qoz71joLfUXkx1jDKZ39ca8bQdUKKtKWEvdgQ9ccfEuv0nV78YBnhKV SrOA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763385997; x=1763990797; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=KIFYlXOHz5whi3PfXinpEu8mupdZxU5ceyDILBZSC4o=; b=R9fkQiKGdBywc70/tyCltNPCSfVDL+tf5T8485aASYecSFF1MRabFnzQLZqSqswBYw hOPOn8Ae4y+T8zBnQyhT078POSIYoWj7vzDFGnMyN07htfGQsdg7APFB0tb2vFF81YsD +hmCUB6DC4DlT4zSVqv2yZAOgrTRHrab62aA0RHCP+J4ZAKNGx/DEu8SJilXeJc0F32M TPpnZCgTLeiwlgUncBA4fU9uHaXI4UVYicR7Kc7iGX8mRcaxGZqNT3iIv1FjUghK2YB8 X2ArUKT3HCLDRtYaB5N7bmDdcZYOkCSuWK5OAkCYhL4Hf3+AHo5XrQMZ5BWGJCO3c0Iz mISA== X-Forwarded-Encrypted: i=1; AJvYcCXrSrY3rAxTx0gq9HiHVpKGwdTZ4KiKRqHBh3d8HFF44H3CAdM2FOZQtt0A+DsuopGQv7Q9q/qL0to5FYY=@vger.kernel.org X-Gm-Message-State: AOJu0YwXqs98fdTH3Tn2hNBVG/JxpJxWkRIIbTLSOoEcbPRNzfyOCv9D NYtRir8vtdFFzb76pqSq/Rx8ZMt/kjUJZVgrdn2bSelEKRj4nEIYOqxi X-Gm-Gg: ASbGncuh1FC8NiAJJ112VLCJGgZ+4G6kTexzAyf+kby3uFg9Dwb97/+0gwbLnDt92FP f60QsKwwpcLJk34ZZwzsOd+CCeuBLVS5vs8KXO8Jf/SRqmCHuy3xiDDejsikBqZa57wFYyoi0bn RKaGQqz3JC+oN333rnTfvuEQaWA/qKQOwsFnl2ayHw7vqrQm8zMT+oTHoPGjJ+q+b2HlDhzb7rN lMGmiVzzPbCUFWBIGipD32AyEm/lgzguZdIMl405Viskeg7RgAwu49JI0ohNa58PSlzUEhZdtop uyR+YP3YVwM7zI7ioRa+sdPfuZEWaVOYobXIGyo9L8JLbXyXd2euRXQsCjlksdhDCnm9XL6oIDC TN8FyzXWS79HKXPbScI+8y9xSKzEt+1pruxAsXvRVNJIiLlg9OKJhoVl4YDLJWbvrLF4jQG0s0Q p3dtCYWFohKmRTlEwT X-Google-Smtp-Source: AGHT+IHdTnYzPJpDm8dxpyzjmpKTz4z28CIouriXEG9ikH1xw0E4XaaZizSOWoHVGZw2NDZ+1IEN2g== X-Received: by 2002:a05:6a00:2194:b0:7a4:1880:e25e with SMTP id d2e1a72fcca58-7ba3ca60000mr13431081b3a.30.1763385996792; Mon, 17 Nov 2025 05:26:36 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7b924cd89bcsm13220953b3a.15.2025.11.17.05.26.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Nov 2025 05:26:35 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v6 2/7] selftests/bpf: Add test cases for btf__permute functionality Date: Mon, 17 Nov 2025 21:26:18 +0800 Message-Id: <20251117132623.3807094-3-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251117132623.3807094-1-dolinux.peng@gmail.com> References: <20251117132623.3807094-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" From: Donglin Peng This patch introduces test cases for the btf__permute function to ensure it works correctly with both base BTF and split BTF scenarios. The test suite includes: - test_permute_base: Validates permutation on base BTF - test_permute_split: Tests permutation on split BTF - test_permute_drop_base: Validates type dropping on base BTF - test_permute_drop_split: Tests type dropping on split BTF - test_permute_drop_dedup: Tests type dropping and deduping Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- .../selftests/bpf/prog_tests/btf_permute.c | 632 ++++++++++++++++++ 1 file changed, 632 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_permute.c diff --git a/tools/testing/selftests/bpf/prog_tests/btf_permute.c b/tools/t= esting/selftests/bpf/prog_tests/btf_permute.c new file mode 100644 index 000000000000..fccbf3744e5e --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/btf_permute.c @@ -0,0 +1,632 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2025 Xiaomi */ + +#include +#include +#include "btf_helpers.h" + +/* Ensure btf__permute work as expected with base BTF */ +static void test_permute_base(void) +{ + struct btf *btf; + __u32 permute_ids[7]; + int err; + + btf =3D btf__new_empty(); + if (!ASSERT_OK_PTR(btf, "empty_main_btf")) + return; + + btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */ + btf__add_ptr(btf, 1); /* [2] ptr to int */ + btf__add_struct(btf, "s1", 4); /* [3] struct s1 { */ + btf__add_field(btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_struct(btf, "s2", 4); /* [4] struct s2 { */ + btf__add_field(btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_func_proto(btf, 1); /* [5] int (*)(int *p); */ + btf__add_func_param(btf, "p", 2); + btf__add_func(btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */ + + VALIDATE_RAW_BTF( + btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] FUNC 'f' type_id=3D5 linkage=3Dstatic"); + + permute_ids[0] =3D 0; + permute_ids[1] =3D 4; /* [1] -> [4] */ + permute_ids[2] =3D 3; /* [2] -> [3] */ + permute_ids[3] =3D 5; /* [3] -> [5] */ + permute_ids[4] =3D 1; /* [4] -> [1] */ + permute_ids[5] =3D 6; /* [5] -> [6] */ + permute_ids[6] =3D 2; /* [6] -> [2] */ + err =3D btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL); + if (!ASSERT_OK(err, "btf__permute_base")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[2] FUNC 'f' type_id=3D6 linkage=3Dstatic", + "[3] PTR '(anon)' type_id=3D4", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[5] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[6] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D3"); + + /* For base BTF, id_map[0] must be 0 */ + permute_ids[0] =3D 4; + permute_ids[1] =3D 0; + permute_ids[2] =3D 3; + permute_ids[3] =3D 5; + permute_ids[4] =3D 1; + permute_ids[5] =3D 6; + permute_ids[6] =3D 2; + err =3D btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL); + if (!ASSERT_ERR(err, "btf__permute_base")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[2] FUNC 'f' type_id=3D6 linkage=3Dstatic", + "[3] PTR '(anon)' type_id=3D4", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[5] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[6] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D3"); + + /* + * For base BTF, id_map_cnt must equal to the number of types + * include VOID type + */ + permute_ids[0] =3D 4; + permute_ids[1] =3D 0; + permute_ids[2] =3D 3; + permute_ids[3] =3D 5; + permute_ids[4] =3D 1; + permute_ids[5] =3D 6; + err =3D btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids) - 1, NULL); + if (!ASSERT_ERR(err, "btf__permute_base")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[2] FUNC 'f' type_id=3D6 linkage=3Dstatic", + "[3] PTR '(anon)' type_id=3D4", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[5] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[6] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D3"); + + /* Multiple types can not be mapped to the same ID */ + permute_ids[0] =3D 0; + permute_ids[1] =3D 4; + permute_ids[2] =3D 4; + permute_ids[3] =3D 5; + permute_ids[4] =3D 1; + permute_ids[5] =3D 6; + permute_ids[6] =3D 2; + err =3D btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL); + if (!ASSERT_ERR(err, "btf__permute_base")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[2] FUNC 'f' type_id=3D6 linkage=3Dstatic", + "[3] PTR '(anon)' type_id=3D4", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[5] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[6] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D3"); + + /* Type ID must be valid */ + permute_ids[0] =3D 0; + permute_ids[1] =3D 4; + permute_ids[2] =3D 3; + permute_ids[3] =3D 5; + permute_ids[4] =3D 1; + permute_ids[5] =3D 7; + permute_ids[6] =3D 2; + err =3D btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL); + if (!ASSERT_ERR(err, "btf__permute_base")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[2] FUNC 'f' type_id=3D6 linkage=3Dstatic", + "[3] PTR '(anon)' type_id=3D4", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[5] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[6] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D3"); + +done: + btf__free(btf); +} + +/* Ensure btf__permute work as expected with split BTF */ +static void test_permute_split(void) +{ + struct btf *split_btf =3D NULL, *base_btf =3D NULL; + __u32 permute_ids[4]; + int err; + + base_btf =3D btf__new_empty(); + if (!ASSERT_OK_PTR(base_btf, "empty_main_btf")) + return; + + btf__add_int(base_btf, "int", 4, BTF_INT_SIGNED); /* [1] int */ + btf__add_ptr(base_btf, 1); /* [2] ptr to int */ + VALIDATE_RAW_BTF( + base_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1"); + split_btf =3D btf__new_empty_split(base_btf); + if (!ASSERT_OK_PTR(split_btf, "empty_split_btf")) + goto cleanup; + btf__add_struct(split_btf, "s1", 4); /* [3] struct s1 { */ + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_struct(split_btf, "s2", 4); /* [4] struct s2 { */ + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_func_proto(split_btf, 1); /* [5] int (*)(int p); */ + btf__add_func_param(split_btf, "p", 2); + btf__add_func(split_btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); = */ + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] FUNC 'f' type_id=3D5 linkage=3Dstatic"); + + permute_ids[0] =3D 6; /* [3] -> [6] */ + permute_ids[1] =3D 3; /* [4] -> [3] */ + permute_ids[2] =3D 5; /* [5] -> [5] */ + permute_ids[3] =3D 4; /* [6] -> [4] */ + err =3D btf__permute(split_btf, permute_ids, ARRAY_SIZE(permute_ids), NUL= L); + if (!ASSERT_OK(err, "btf__permute_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] FUNC 'f' type_id=3D5 linkage=3Dstatic", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + + /* + * For split BTF, id_map_cnt must equal to the number of types + * added on top of base BTF + */ + permute_ids[0] =3D 4; + permute_ids[1] =3D 3; + permute_ids[2] =3D 5; + permute_ids[3] =3D 6; + err =3D btf__permute(split_btf, permute_ids, 3, NULL); + if (!ASSERT_ERR(err, "btf__permute_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] FUNC 'f' type_id=3D5 linkage=3Dstatic", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + + /* Multiple types can not be mapped to the same ID */ + permute_ids[0] =3D 4; + permute_ids[1] =3D 3; + permute_ids[2] =3D 3; + permute_ids[3] =3D 6; + err =3D btf__permute(split_btf, permute_ids, 4, NULL); + if (!ASSERT_ERR(err, "btf__permute_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] FUNC 'f' type_id=3D5 linkage=3Dstatic", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + + /* Can not map to base ID */ + permute_ids[0] =3D 4; + permute_ids[1] =3D 2; + permute_ids[2] =3D 5; + permute_ids[3] =3D 6; + err =3D btf__permute(split_btf, permute_ids, 4, NULL); + if (!ASSERT_ERR(err, "btf__permute_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] FUNC 'f' type_id=3D5 linkage=3Dstatic", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + +cleanup: + btf__free(split_btf); + btf__free(base_btf); +} + +/* Verify btf__permute function drops types correctly with base_btf */ +static void test_permute_drop_base(void) +{ + struct btf *btf; + __u32 permute_ids[7]; + int err; + + btf =3D btf__new_empty(); + if (!ASSERT_OK_PTR(btf, "empty_main_btf")) + return; + + btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */ + btf__add_ptr(btf, 1); /* [2] ptr to int */ + btf__add_struct(btf, "s1", 4); /* [3] struct s1 { */ + btf__add_field(btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_struct(btf, "s2", 4); /* [4] struct s2 { */ + btf__add_field(btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_func_proto(btf, 1); /* [5] int (*)(int *p); */ + btf__add_func_param(btf, "p", 2); + btf__add_func(btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */ + + VALIDATE_RAW_BTF( + btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] FUNC 'f' type_id=3D5 linkage=3Dstatic"); + + /* Drop ID 4 */ + permute_ids[0] =3D 0; + permute_ids[1] =3D 5; /* [1] -> [5] */ + permute_ids[2] =3D 1; /* [2] -> [1] */ + permute_ids[3] =3D 2; /* [3] -> [2] */ + permute_ids[4] =3D 0; /* Drop [4] */ + permute_ids[5] =3D 3; /* [5] -> [3] */ + permute_ids[6] =3D 4; /* [6] -> [4] */ + err =3D btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL); + if (!ASSERT_OK(err, "btf__permute_drop_base")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] PTR '(anon)' type_id=3D5", + "[2] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D5 bits_offset=3D0", + "[3] FUNC_PROTO '(anon)' ret_type_id=3D5 vlen=3D1\n" + "\t'p' type_id=3D1", + "[4] FUNC 'f' type_id=3D3 linkage=3Dstatic", + "[5] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED"); + + /* Continue dropping */ + permute_ids[0] =3D 0; + permute_ids[1] =3D 1; /* [1] -> [1] */ + permute_ids[2] =3D 2; /* [2] -> [2] */ + permute_ids[3] =3D 3; /* [3] -> [3] */ + permute_ids[4] =3D 0; /* Drop [4] */ + permute_ids[5] =3D 4; /* [5] -> [4] */ + err =3D btf__permute(btf, permute_ids, 6, NULL); + if (!ASSERT_OK(err, "btf__permute_drop_base_fail")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] PTR '(anon)' type_id=3D4", + "[2] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[3] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D1", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED"); + + /* Cannot drop the ID referenced by others */ + permute_ids[0] =3D 0; + permute_ids[1] =3D 2; + permute_ids[2] =3D 3; + permute_ids[3] =3D 1; + permute_ids[4] =3D 0; /* [4] is referenced by others */ + err =3D btf__permute(btf, permute_ids, 5, NULL); + if (!ASSERT_ERR(err, "btf__permute_drop_base_fail")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] PTR '(anon)' type_id=3D4", + "[2] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[3] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D1", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED"); + + /* Drop 2 IDs at once */ + permute_ids[0] =3D 0; + permute_ids[1] =3D 2; /* [1] -> [2] */ + permute_ids[2] =3D 0; /* Drop [2] */ + permute_ids[3] =3D 0; /* Drop [3] */ + permute_ids[4] =3D 1; /* [4] -> [1] */ + err =3D btf__permute(btf, permute_ids, 5, NULL); + if (!ASSERT_OK(err, "btf__permute_drop_base_fail")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1"); + + /* Drop all IDs */ + permute_ids[0] =3D 0; + permute_ids[1] =3D 0; /* Drop [1] */ + permute_ids[2] =3D 0; /* Drop [2] */ + err =3D btf__permute(btf, permute_ids, 3, NULL); + if (!ASSERT_OK(err, "btf__permute_drop_base_fail")) + goto done; + if (!ASSERT_EQ(btf__type_cnt(btf), 0, "btf__permute_drop_split all")) + goto done; + +done: + btf__free(btf); +} + +/* Verify btf__permute function drops types correctly with split BTF */ +static void test_permute_drop_split(void) +{ + struct btf *split_btf =3D NULL, *base_btf =3D NULL; + __u32 permute_ids[4]; + int err; + + base_btf =3D btf__new_empty(); + if (!ASSERT_OK_PTR(base_btf, "empty_main_btf")) + return; + + btf__add_int(base_btf, "int", 4, BTF_INT_SIGNED); /* [1] int */ + btf__add_ptr(base_btf, 1); /* [2] ptr to int */ + VALIDATE_RAW_BTF( + base_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1"); + split_btf =3D btf__new_empty_split(base_btf); + if (!ASSERT_OK_PTR(split_btf, "empty_split_btf")) + goto cleanup; + btf__add_struct(split_btf, "s1", 4); /* [3] struct s1 { */ + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_struct(split_btf, "s2", 4); /* [4] struct s2 { */ + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_func_proto(split_btf, 1); /* [5] int (*)(int p); */ + btf__add_func_param(split_btf, "p", 2); + btf__add_func(split_btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); = */ + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] FUNC 'f' type_id=3D5 linkage=3Dstatic"); + + /* Drop ID 4 */ + permute_ids[0] =3D 5; /* [3] -> [5] */ + permute_ids[1] =3D 0; /* Drop [4] */ + permute_ids[2] =3D 3; /* [5] -> [3] */ + permute_ids[3] =3D 4; /* [6] -> [4] */ + err =3D btf__permute(split_btf, permute_ids, ARRAY_SIZE(permute_ids), NUL= L); + if (!ASSERT_OK(err, "btf__permute_drop_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[4] FUNC 'f' type_id=3D3 linkage=3Dstatic", + "[5] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + + /* Can not drop the type referenced by others */ + permute_ids[0] =3D 0; /* [3] is referenced by [4] */ + permute_ids[1] =3D 4; + permute_ids[2] =3D 3; + err =3D btf__permute(split_btf, permute_ids, 3, NULL); + if (!ASSERT_ERR(err, "btf__permute_drop_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[4] FUNC 'f' type_id=3D3 linkage=3Dstatic", + "[5] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + + /* Continue dropping */ + permute_ids[0] =3D 0; /* Drop [3] */ + permute_ids[1] =3D 0; /* Drop [4] */ + permute_ids[2] =3D 3; /* [5] -> [3] */ + err =3D btf__permute(split_btf, permute_ids, 3, NULL); + if (!ASSERT_OK(err, "btf__permute_drop_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + + /* Continue dropping */ + permute_ids[0] =3D 0; /* Drop [3] */ + err =3D btf__permute(split_btf, permute_ids, 1, NULL); + if (!ASSERT_OK(err, "btf__permute_drop_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1"); + +cleanup: + btf__free(split_btf); + btf__free(base_btf); +} + +/* Verify btf__permute then btf__dedup work correctly */ +static void test_permute_drop_dedup(void) +{ + struct btf *btf, *new_btf =3D NULL; + const struct btf_header *hdr; + const void *btf_data; + char expect_strs[] =3D "\0int\0s1\0m\0tag1\0tag2\0tag3"; + char expect_strs_dedupped[] =3D "\0int\0s1\0m\0tag1"; + __u32 permute_ids[6], btf_size; + int err; + + btf =3D btf__new_empty(); + if (!ASSERT_OK_PTR(btf, "empty_main_btf")) + return; + + btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */ + btf__add_struct(btf, "s1", 4); /* [2] struct s1 { */ + btf__add_field(btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_decl_tag(btf, "tag1", 2, -1); /* [3] tag -> s1: tag1 */ + btf__add_decl_tag(btf, "tag2", 2, 1); /* [4] tag -> s1/m: tag2 */ + btf__add_decl_tag(btf, "tag3", 2, 1); /* [5] tag -> s1/m: tag3 */ + + VALIDATE_RAW_BTF( + btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[3] DECL_TAG 'tag1' type_id=3D2 component_idx=3D-1", + "[4] DECL_TAG 'tag2' type_id=3D2 component_idx=3D1", + "[5] DECL_TAG 'tag3' type_id=3D2 component_idx=3D1"); + + btf_data =3D btf__raw_data(btf, &btf_size); + if (!ASSERT_OK_PTR(btf_data, "btf__raw_data")) + goto done; + hdr =3D btf_data; + if (!ASSERT_EQ(hdr->str_len, ARRAY_SIZE(expect_strs), "expect_strs")) + goto done; + + new_btf =3D btf__new(btf_data, btf_size); + if (!ASSERT_OK_PTR(new_btf, "btf__new")) + goto done; + + /* Drop 2 IDs result in unreferenced strings */ + permute_ids[0] =3D 0; + permute_ids[1] =3D 3; /* [1] -> [3] */ + permute_ids[2] =3D 1; /* [2] -> [1] */ + permute_ids[3] =3D 2; /* [3] -> [2] */ + permute_ids[4] =3D 0; /* Drop result in unreferenced "tag2" */ + permute_ids[5] =3D 0; /* Drop result in unreferenced "tag3" */ + err =3D btf__permute(new_btf, permute_ids, ARRAY_SIZE(permute_ids), NULL); + if (!ASSERT_OK(err, "btf__permute")) + goto done; + + VALIDATE_RAW_BTF( + new_btf, + "[1] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D3 bits_offset=3D0", + "[2] DECL_TAG 'tag1' type_id=3D1 component_idx=3D-1", + "[3] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED"); + + btf_data =3D btf__raw_data(new_btf, &btf_size); + if (!ASSERT_OK_PTR(btf_data, "btf__raw_data")) + goto done; + hdr =3D btf_data; + if (!ASSERT_EQ(hdr->str_len, ARRAY_SIZE(expect_strs), "expect_strs")) + goto done; + + err =3D btf__dedup(new_btf, NULL); + if (!ASSERT_OK(err, "btf__dedup")) + goto done; + + btf_data =3D btf__raw_data(new_btf, &btf_size); + if (!ASSERT_OK_PTR(btf_data, "btf__raw_data")) + goto done; + hdr =3D btf_data; + if (!ASSERT_EQ(hdr->str_len, ARRAY_SIZE(expect_strs_dedupped), "expect_st= rs_dedupped")) + goto done; + +done: + btf__free(btf); + btf__free(new_btf); +} + +void test_btf_permute(void) +{ + if (test__start_subtest("permute_base")) + test_permute_base(); + if (test__start_subtest("permute_split")) + test_permute_split(); + if (test__start_subtest("permute_drop_base")) + test_permute_drop_base(); + if (test__start_subtest("permute_drop_split")) + test_permute_drop_split(); + if (test__start_subtest("permute_drop_dedup")) + test_permute_drop_dedup(); +} --=20 2.34.1 From nobody Tue Dec 2 02:52:23 2025 Received: from mail-pj1-f46.google.com (mail-pj1-f46.google.com [209.85.216.46]) (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 E063A332ED9 for ; Mon, 17 Nov 2025 13:26:40 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.46 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763386002; cv=none; b=nqAI6ZF0ALT+Pw7RPGE/axArjk3xrCRzaCxdcBtPmrCzVovNmJCGziFPgikwieGqqV29gHqOvV5aMjxeRvIqFpVRunw3eRmLUBq8il0Ue4ro/0e85eCyL0xmlu+CPsbpCd1G5IN4Izbmi4EMLBd8fKh/6+6dSkYZ6tLtxvNwSB8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763386002; c=relaxed/simple; bh=gKhZlZG9Uptrdn86em/7HgNFouQXhzpq2vdn6XCl1dw=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=ghAFcC9zKAr7gIetZp13kz15yyMRkSXqKLOx0F1+aYME2gfeDCw91UHQ/U5dcnj+yftyxZMuxWByRyYEbhm4t4uohndZNfsKuNFvW+PS12Krk1DyyX6xt/q3MCifNeeI+vEI4RG2EByg0BUJbwHEPy628xFMciKw3A3N5yHIEmM= 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=KZoXMYHy; arc=none smtp.client-ip=209.85.216.46 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="KZoXMYHy" Received: by mail-pj1-f46.google.com with SMTP id 98e67ed59e1d1-3410c86070dso3212624a91.1 for ; Mon, 17 Nov 2025 05:26:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763386000; x=1763990800; 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=mjdSgxLBu++Fq6ABtVyHLvDR0wgeK7sjNIs7L3tmdN8=; b=KZoXMYHygxsgjfcj3iiWtF3l0jGoAHL4DA0/mT/F+49ky2EP7wefpHtKNVBe5kO5HR 9H2LgG+qGuG1cVk+Naah/JXTF6hgyad/La8MwCto3PwTtdTpHauDh/Q4yuoJh0qu55m+ Py1IJ22QqMit+hBEzg/nccf8zHL8HhoU7TFB78hNZdAxzRS4XTQsO1MHrH/+JGPI1hxY /B60ne+TPKGZQ9WCl6Zzi1MviMNbkRGOraQtEOnc1pIMSnXKGzUKDpmnGTx4Wt5v6YHy 3BaE9xuGDJMpnx/unqkA7dfpPuKUjkMzveJp0NpMxaJbZkoEz17UdE8/+T8YKm+Ux8CI u2Nw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763386000; x=1763990800; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=mjdSgxLBu++Fq6ABtVyHLvDR0wgeK7sjNIs7L3tmdN8=; b=cKftMgH/2/cxC91pjBMy60F+N9ueyYyIYzb2QVG/+7CfWK7S7CAegthA37BY6QT4ha tcvQO0Uys6MAy3eZ0uyfhH7t4Cy2fc/95OFKOtW5VWY8kSO3whxlDpGf2JnYiLp5V2ih wBd7c75Ay4YBHr4VDkHtD+0yYdruIMsD2ii36Io/+H6HvEz8JsVntp1o/GazNbHVqQ9G CI609vhMsLg2O7H72TvpkNUN0/jcOi3XfyA4x4sm9ChL5Qo5TZPzAP2Dkd6EKlrPNhWg vv+XkwGwPo2ddvsoBfAROhK4plWWr4jNQJTYy7LRCw48+nI6FwV16UI/HLn37FfriwVY Q/cw== X-Forwarded-Encrypted: i=1; AJvYcCXVevS6lwk2rDXBMsrmf7sUNcLnzYHyRCgkqpd06OCGb54t/tpMbwHWEnwSCuLcDbLE/QstAbSQtLdfCWw=@vger.kernel.org X-Gm-Message-State: AOJu0Yx3z/S/l7Cbq67/+KYxJBripxTkmnl98koCySuYJvLe/Zn2TBIm dq5PPIlMaJ3uxk6aMEw+h4/7/lBIyHwB4kBkDoosi/wQP2hOet77X+7N X-Gm-Gg: ASbGncv3Hzac5EpB6dJ4U+zR31DOpSBSiuLDpazSWAXIHjQbTzAwkdgrpYTGpSfU8mk 8brlxeCqgHAj9zrkwgFNTuL0uSbUWNiLrWv0FQLBj77MzV5aFJ7gic2xSASCElBdOfh+IIgIQXo 21mt02Ew2eekx9dlMnpxWIih3NMzmY9e4EvZhoLUkBEwxKbxukjU7Fx0hs2Wf4bDmVY3xeQpktz wSxNdG0TcHLTcoc1uFkg7JGueGALwIuGiPbKrAeY0kOMQl8JAmMJztI0YUB0w2HIxJQvh8wcSGh avR4dq0bwaeRzUxaaJHaIfUq6sPtxcpll9r7fM7Mzd+0uFFqBZUXvIQB5k+QTt5IbuCE6FhzeVV Omp4d3nwb1rDWjhdhGnSSKV8OVxncmnDFQpsor+XsVF6++FwAmoQ6w9saXYkhHIj+7AhrSI/PBn pGt69F0k9AuhEIv46r X-Google-Smtp-Source: AGHT+IEhHi7O4yt0EMTyloFaD8KlYsdb2aEOshF+gKxXsgJ79nlgnHKhh5nGs3RcG3o+qFAumLcqCw== X-Received: by 2002:a17:90b:1807:b0:340:ac7c:6387 with SMTP id 98e67ed59e1d1-343f9e90659mr16368075a91.7.1763386000187; Mon, 17 Nov 2025 05:26:40 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7b924cd89bcsm13220953b3a.15.2025.11.17.05.26.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Nov 2025 05:26:39 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v6 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting Date: Mon, 17 Nov 2025 21:26:19 +0800 Message-Id: <20251117132623.3807094-4-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251117132623.3807094-1-dolinux.peng@gmail.com> References: <20251117132623.3807094-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" From: Donglin Peng This patch introduces a new --btf_sort option that leverages libbpf's btf__permute interface to reorganize BTF layout. The implementation sorts BTF types by name in ascending order, placing anonymous types at the end to enable efficient binary search lookup. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- scripts/Makefile.btf | 2 + scripts/Makefile.modfinal | 1 + scripts/link-vmlinux.sh | 1 + tools/bpf/resolve_btfids/main.c | 203 ++++++++++++++++++++++++++++++++ 4 files changed, 207 insertions(+) diff --git a/scripts/Makefile.btf b/scripts/Makefile.btf index db76335dd917..d5eb4ee70e88 100644 --- a/scripts/Makefile.btf +++ b/scripts/Makefile.btf @@ -27,6 +27,7 @@ pahole-flags-$(call test-ge, $(pahole-ver), 130) +=3D --b= tf_features=3Dattributes =20 ifneq ($(KBUILD_EXTMOD),) module-pahole-flags-$(call test-ge, $(pahole-ver), 128) +=3D --btf_feature= s=3Ddistilled_base +module-resolve_btfid-flags-y =3D --distilled_base endif =20 endif @@ -35,3 +36,4 @@ pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) +=3D --la= ng_exclude=3Drust =20 export PAHOLE_FLAGS :=3D $(pahole-flags-y) export MODULE_PAHOLE_FLAGS :=3D $(module-pahole-flags-y) +export MODULE_RESOLVE_BTFID_FLAGS :=3D $(module-resolve_btfid-flags-y) diff --git a/scripts/Makefile.modfinal b/scripts/Makefile.modfinal index 542ba462ed3e..4481dda2f485 100644 --- a/scripts/Makefile.modfinal +++ b/scripts/Makefile.modfinal @@ -40,6 +40,7 @@ quiet_cmd_btf_ko =3D BTF [M] $@ printf "Skipping BTF generation for %s due to unavailability of vmlinux\= n" $@ 1>&2; \ else \ LLVM_OBJCOPY=3D"$(OBJCOPY)" $(PAHOLE) -J $(PAHOLE_FLAGS) $(MODULE_PAHOLE= _FLAGS) --btf_base $(objtree)/vmlinux $@; \ + $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $(MODULE_RESOLVE_BTFID_FLAGS) --= btf_sort $@; \ $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $@; \ fi; =20 diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh index 433849ff7529..f21f6300815b 100755 --- a/scripts/link-vmlinux.sh +++ b/scripts/link-vmlinux.sh @@ -288,6 +288,7 @@ if is_enabled CONFIG_DEBUG_INFO_BTF; then if is_enabled CONFIG_WERROR; then RESOLVE_BTFIDS_ARGS=3D" --fatal_warnings " fi + ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} --btf_sort "${VMLINUX}" ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} "${VMLINUX}" fi =20 diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/mai= n.c index d47191c6e55e..778909fe2faa 100644 --- a/tools/bpf/resolve_btfids/main.c +++ b/tools/bpf/resolve_btfids/main.c @@ -768,6 +768,198 @@ static int symbols_patch(struct object *obj) return err < 0 ? -1 : 0; } =20 +/* Anonymous types (with empty names) are considered greater than named ty= pes + * and are sorted after them. Two anonymous types are considered equal. Na= med + * types are compared lexicographically. + */ +static int cmp_type_names(const void *a, const void *b, void *priv) +{ + struct btf *btf =3D (struct btf *)priv; + const struct btf_type *ta =3D btf__type_by_id(btf, *(__u32 *)a); + const struct btf_type *tb =3D btf__type_by_id(btf, *(__u32 *)b); + const char *na, *nb; + + if (!ta->name_off && tb->name_off) + return 1; + if (ta->name_off && !tb->name_off) + return -1; + if (!ta->name_off && !tb->name_off) + return 0; + + na =3D btf__str_by_offset(btf, ta->name_off); + nb =3D btf__str_by_offset(btf, tb->name_off); + return strcmp(na, nb); +} + +static int update_elf(const char *path, const struct btf *btf, + const char *btf_secname) +{ + GElf_Shdr shdr_mem, *shdr; + Elf_Data *btf_data =3D NULL; + Elf_Scn *scn =3D NULL; + Elf *elf =3D NULL; + const void *raw_btf_data; + uint32_t raw_btf_size; + int fd, err =3D -1; + size_t strndx; + + fd =3D open(path, O_RDWR); + if (fd < 0) { + pr_err("FAILED to open %s\n", path); + return -1; + } + + if (elf_version(EV_CURRENT) =3D=3D EV_NONE) { + pr_err("FAILED to set libelf version"); + goto out; + } + + elf =3D elf_begin(fd, ELF_C_RDWR, NULL); + if (elf =3D=3D NULL) { + pr_err("FAILED to update ELF file"); + goto out; + } + + elf_flagelf(elf, ELF_C_SET, ELF_F_LAYOUT); + + elf_getshdrstrndx(elf, &strndx); + while ((scn =3D elf_nextscn(elf, scn)) !=3D NULL) { + char *secname; + + shdr =3D gelf_getshdr(scn, &shdr_mem); + if (shdr =3D=3D NULL) + continue; + secname =3D elf_strptr(elf, strndx, shdr->sh_name); + if (strcmp(secname, btf_secname) =3D=3D 0) { + btf_data =3D elf_getdata(scn, btf_data); + break; + } + } + + raw_btf_data =3D btf__raw_data(btf, &raw_btf_size); + + if (btf_data) { + if (raw_btf_size !=3D btf_data->d_size) { + pr_err("FAILED: size mismatch"); + goto out; + } + + btf_data->d_buf =3D (void *)raw_btf_data; + btf_data->d_type =3D ELF_T_WORD; + elf_flagdata(btf_data, ELF_C_SET, ELF_F_DIRTY); + + if (elf_update(elf, ELF_C_WRITE) >=3D 0) + err =3D 0; + } + +out: + if (fd !=3D -1) + close(fd); + if (elf) + elf_end(elf); + return err; +} + +static int sort_update_btf(struct object *obj, bool distilled_base) +{ + struct btf *base_btf =3D NULL; + struct btf *btf =3D NULL; + int start_id =3D 0, nr_types, id; + int err =3D 0, offs, i; + __u32 *permute_ids =3D NULL, *id_map =3D NULL, btf_size; + const void *btf_data; + int fd; + + if (obj->base_btf_path) { + base_btf =3D btf__parse(obj->base_btf_path, NULL); + err =3D libbpf_get_error(base_btf); + if (err) { + pr_err("FAILED: load base BTF from %s: %s\n", + obj->base_btf_path, strerror(-err)); + return -1; + } + } + + btf =3D btf__parse_elf_split(obj->path, base_btf); + err =3D libbpf_get_error(btf); + if (err) { + pr_err("FAILED: load BTF from %s: %s\n", obj->path, strerror(-err)); + goto out; + } + + if (base_btf) + start_id =3D btf__type_cnt(base_btf); + nr_types =3D btf__type_cnt(btf) - start_id; + if (nr_types < 2) + goto out; + + offs =3D base_btf ? 0 : 1; + + permute_ids =3D calloc(nr_types, sizeof(*permute_ids)); + if (!permute_ids) { + err =3D -ENOMEM; + goto out; + } + + id_map =3D calloc(nr_types, sizeof(*id_map)); + if (!id_map) { + err =3D -ENOMEM; + goto out; + } + + for (i =3D 0, id =3D start_id; i < nr_types; i++, id++) + permute_ids[i] =3D id; + + qsort_r(permute_ids + offs, nr_types - offs, sizeof(*permute_ids), + cmp_type_names, btf); + + for (i =3D 0; i < nr_types; i++) { + id =3D permute_ids[i] - start_id; + id_map[id] =3D i + start_id; + } + + err =3D btf__permute(btf, id_map, nr_types, NULL); + if (err) { + pr_err("FAILED: btf permute: %s\n", strerror(-err)); + goto out; + } + + if (distilled_base) { + struct btf *new_btf =3D NULL, *distilled_base =3D NULL; + + if (btf__distill_base(btf, &distilled_base, &new_btf) < 0) { + pr_err("FAILED to generate distilled base BTF: %s\n", + strerror(errno)); + goto out; + } + + err =3D update_elf(obj->path, new_btf, BTF_ELF_SEC); + if (!err) { + err =3D update_elf(obj->path, distilled_base, BTF_BASE_ELF_SEC); + if (err < 0) + pr_err("FAILED to update '%s'\n", BTF_BASE_ELF_SEC); + } else { + pr_err("FAILED to update '%s'\n", BTF_ELF_SEC); + } + + btf__free(new_btf); + btf__free(distilled_base); + } else { + err =3D update_elf(obj->path, btf, BTF_ELF_SEC); + if (err < 0) { + pr_err("FAILED to update '%s'\n", BTF_ELF_SEC); + goto out; + } + } + +out: + free(permute_ids); + free(id_map); + btf__free(base_btf); + btf__free(btf); + return err; +} + static const char * const resolve_btfids_usage[] =3D { "resolve_btfids [] ", NULL @@ -787,6 +979,8 @@ int main(int argc, const char **argv) .sets =3D RB_ROOT, }; bool fatal_warnings =3D false; + bool btf_sort =3D false; + bool distilled_base =3D false; struct option btfid_options[] =3D { OPT_INCR('v', "verbose", &verbose, "be more verbose (show errors, etc)"), @@ -796,6 +990,10 @@ int main(int argc, const char **argv) "path of file providing base BTF"), OPT_BOOLEAN(0, "fatal_warnings", &fatal_warnings, "turn warnings into errors"), + OPT_BOOLEAN(0, "btf_sort", &btf_sort, + "sort BTF by name"), + OPT_BOOLEAN(0, "distilled_base", &distilled_base, + "update distilled base"), OPT_END() }; int err =3D -1; @@ -807,6 +1005,11 @@ int main(int argc, const char **argv) =20 obj.path =3D argv[0]; =20 + if (btf_sort) { + err =3D sort_update_btf(&obj, distilled_base); + goto out; + } + if (elf_collect(&obj)) goto out; =20 --=20 2.34.1 From nobody Tue Dec 2 02:52:23 2025 Received: from mail-pf1-f176.google.com (mail-pf1-f176.google.com [209.85.210.176]) (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 5C5F8334686 for ; Mon, 17 Nov 2025 13:26:44 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763386006; cv=none; b=rZ7a3TGMyL6p2zWkdW/2sTraja3kz8ap/ZI09x78zhnXpcxB0fjV8l4+NZLmNcW7bVfr89Z1ATsD9yv5O+62oACQsfck/7A8AFaTxRuLjIKTU2EQOSBVpz1y2XfEKNAOVsU86p4obp+NyA/stxoESTNBIvHP6yS5vN7+4rxXMjE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763386006; c=relaxed/simple; bh=JLTGVx4UZtjRB1mVuoBOiHsEz9/Yagm9RBlqqg5WwaY=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=fq6BqH5SsUnDEPq80qiR8kDdSoxhrkU9XJGsMDvL9SVrBoe7Y2gppjZ+ITRv7qPEPcb+Iuq720ZmkGl4PM1l9h7O5Nt59t8T1kV9gnQFlHYdSA6zuFjmj1cEzONM5wuOdUHZR90MgmK/+ZawCqV7edq3c00H/obbLbztvNLz8Z4= 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=X0wBnSbY; arc=none smtp.client-ip=209.85.210.176 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="X0wBnSbY" Received: by mail-pf1-f176.google.com with SMTP id d2e1a72fcca58-7aae5f2633dso4805071b3a.3 for ; Mon, 17 Nov 2025 05:26:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763386004; x=1763990804; 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=kDnX3/9BOxi6Gb6RG2mMeJXGvVBir6Y+siDzZkdeaTk=; b=X0wBnSbYgbm5aXREpeVRWkwSdB4qG5nl5ftbSg4CslIdKmSJa6jKgQGZevn8tounjT bo6acLsLtuaaJ3Ymyqrc3hux2zPEWsffGyff13iXCbYylf9EDFhbBWxOBgR5JDRH2Hfj 6NmzM2BQVryHgV82sdzl4n7tftAuZB93HOu9UlooQQcvcikXhrTmOqzu1m0UldpcfR/U 9hPLCbP1W++GZfjfOEO2WJO85v/dHKT/ACsMCe9m7rrxjSmWmdNvrRG9lemOUIbA1gki H9h/aKTw087MuFKcf97YlDk1Cbk9lRNKvMTVNc/RjwhzElI4NZOXztYi86O+1oyxHKsk VRHw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763386004; x=1763990804; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=kDnX3/9BOxi6Gb6RG2mMeJXGvVBir6Y+siDzZkdeaTk=; b=Yx6eENuNgggLc25JEJV43xWRtnxZtEAa2rlm1CcgCYhdG7fD8CQ/Ao+JNIARz1FwT+ 1PA5rtqT8R7MhAppmVhYcGpy3tCdKVWj5eVRsI4y0dj0p1H547nMmcQoKpePUFkTz4Zq AaEcdPMEiFrfyBDh8y5Ra95V8pXCyhBEq3IzLCvEgpHrsrZnm8wYIOfOUptCUfDXkw3r ShxwASoSJ0viZlrvmNaI8L5OHFu9DIIvc+L2+GAlzyXCXEv0k1xAY9JRoyU2sP0p5+jo tNWgcB4s2rco2QN3ImNAnusozKcSlYomZ6OMaZryAtjZQavl4yk0Rb+X8bM3uZhpuX1d BG4w== X-Forwarded-Encrypted: i=1; AJvYcCW+5KUJ/rbr65CanY3CXIdyuULNKusF0wi8cZhmfGD+jEKjNleMtNy4mmoVn/tAh7CfQD08613UJbNI/bs=@vger.kernel.org X-Gm-Message-State: AOJu0YwWJh1sCGG4mjGd15CZwaZ/9A7948ndjou/c6hHkwulkYy5Aue7 tqveXTkszMOJQddJjKrfrGlalCdRBNOGMRsEoy+S6hHjhrSrn7OTh61D X-Gm-Gg: ASbGncsWBxmPy/TMgdT6cZ2FuCUfRU/P5ZZlhQCIUK9FijQkIkKSgxRwuB6+psaG2kM ykPRvkSQIyaL19+mPQmREWdVuS+lP/30+uVLSt6+/oCREuWvTDyITNdU+MNiH8qEd+4jOKKin6j GW9D4fDdyU5OTW6oYkUUnGnhAKqmGnbFbIW915B3IDAI2HUezMv4Qsw+Gfc9vhmc6l4yrrOycIY IfJhFqqz6E/EaeE5j6iMRc0/p9hF76qduEILqtAzDHgkbShS/3FwI45iqx9oDByJvn0HHbXbBtw e0eomTY4apGwRtkpmKm5/5TyCdk1qUkR5nI1kbW239fJAv0zkBVRWpQiJLxUfI/jFeN5GSS/Ag6 09daFfxW5fZY5vj+5ni8P98Y8YCL2vD0JFnz/Z7Ly1qAVjMVy2gHF7jEkBCruwdxnEbIKGr4r+2 lXJMIH8G31arhNAQBD X-Google-Smtp-Source: AGHT+IGZzgzGPA7A8TF1YDSWzknuJkYXs5j8CBMMrMfBosuB5NpJMGFxMPwzRtMqYCAJYGp+hc7eOg== X-Received: by 2002:a05:6a00:270a:b0:7bf:1a4b:1675 with SMTP id d2e1a72fcca58-7bf1a4b18e8mr4299493b3a.28.1763386003583; Mon, 17 Nov 2025 05:26:43 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7b924cd89bcsm13220953b3a.15.2025.11.17.05.26.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Nov 2025 05:26:42 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v6 4/7] libbpf: Optimize type lookup with binary search for sorted BTF Date: Mon, 17 Nov 2025 21:26:20 +0800 Message-Id: <20251117132623.3807094-5-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251117132623.3807094-1-dolinux.peng@gmail.com> References: <20251117132623.3807094-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" From: Donglin Peng This patch introduces binary search optimization for BTF type lookups when the BTF instance contains sorted types. The optimization significantly improves performance when searching for types in large BTF instances with sorted type names. For unsorted BTF or when nr_sorted_types is zero, the implementation falls back to the original linear search algorithm. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 104 ++++++++++++++++++++++++++++++++++---------- 1 file changed, 81 insertions(+), 23 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index e3aa31c735c8..bb77e6c762cc 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -92,6 +92,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 */ @@ -897,44 +903,93 @@ int btf__resolve_type(const struct btf *btf, __u32 ty= pe_id) return type_id; } =20 -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const ch= ar *name, + __s32 start_id, __s32 end_id) { - __u32 i, nr_types =3D btf__type_cnt(btf); + const struct btf_type *t; + const char *tname; + __s32 l, r, m; + + l =3D start_id; + r =3D end_id; + while (l <=3D r) { + m =3D l + (r - l) / 2; + t =3D btf_type_by_id(btf, m); + tname =3D btf__str_by_offset(btf, t->name_off); + if (strcmp(tname, name) >=3D 0) { + if (l =3D=3D r) + return r; + r =3D m; + } else { + l =3D m + 1; + } + } =20 - if (!strcmp(type_name, "void")) - return 0; + return btf__type_cnt(btf); +} =20 - for (i =3D 1; i < nr_types; i++) { - const struct btf_type *t =3D btf__type_by_id(btf, i); - const char *name =3D btf__name_by_offset(btf, t->name_off); +static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_i= d, + const char *type_name, __u32 kind) +{ + const struct btf_type *t; + const char *tname; + int err =3D -ENOENT; + + if (start_id < btf->start_id) { + err =3D btf_find_type_by_name_kind(btf->base_btf, start_id, + type_name, kind); + if (err > 0) + goto out; + start_id =3D btf->start_id; + } + + if (btf->nr_sorted_types > 0) { + /* binary search */ + __s32 end_id; + int idx; + + end_id =3D btf->start_id + btf->nr_sorted_types - 1; + idx =3D btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id); + for (; idx <=3D end_id; idx++) { + t =3D btf__type_by_id(btf, idx); + tname =3D btf__str_by_offset(btf, t->name_off); + if (strcmp(tname, type_name)) + goto out; + if (kind =3D=3D -1 || btf_kind(t) =3D=3D kind) + return idx; + } + } else { + /* linear search */ + __u32 i, total; =20 - if (name && !strcmp(type_name, name)) - return i; + total =3D btf__type_cnt(btf); + for (i =3D start_id; i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (kind !=3D -1 && btf_kind(t) !=3D kind) + continue; + tname =3D btf__str_by_offset(btf, t->name_off); + if (tname && !strcmp(tname, type_name)) + return i; + } } =20 - return libbpf_err(-ENOENT); +out: + return err; } =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; =20 - 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(btf_find_type_by_name_kind(btf, start_id, type_name, ki= nd)); +} =20 - return libbpf_err(-ENOENT); +/* the kind value of -1 indicates that kind matching should be skipped */ +__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +{ + return btf_find_by_name_kind(btf, btf->start_id, type_name, -1); } =20 __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_n= ame, @@ -1006,6 +1061,7 @@ static struct btf *btf_new_empty(struct btf *base_btf) btf->fd =3D -1; btf->ptr_sz =3D sizeof(void *); btf->swapped_endian =3D false; + btf->nr_sorted_types =3D 0; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1057,6 +1113,7 @@ static struct btf *btf_new(const void *data, __u32 si= ze, struct btf *base_btf, b btf->start_id =3D 1; btf->start_str_off =3D 0; btf->fd =3D -1; + btf->nr_sorted_types =3D 0; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1715,6 +1772,7 @@ static void btf_invalidate_raw_data(struct btf *btf) free(btf->raw_data_swapped); btf->raw_data_swapped =3D NULL; } + btf->nr_sorted_types =3D 0; } =20 /* Ensure BTF is ready to be modified (by splitting into a three memory --=20 2.34.1 From nobody Tue Dec 2 02:52:23 2025 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 D12C7333434 for ; Mon, 17 Nov 2025 13:26:47 +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=1763386009; cv=none; b=NzV0m6eKy6mXIjGMPKwxeFxFyn2J6ocQ4/W270ee37zwOb/gR+bm7/2c8Kp5sZRK5VBZw6OsznpPrCEB6FI1R8vbwE2GQfDTTSFFaC2/a2fcSxn6nfWnqBeBkDnuWSeod43H9QOaGs4R4pqWss5LPQsxQ5XRkC1jjVI/M+dhZpo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763386009; c=relaxed/simple; bh=TlQb3BbQR+c28ZRJL32xlMCjA7W2OgjyhhJH/DnySmY=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=PENvg1Et9DO7e8sLiOaBOg58rL6WP3cupKbMXrLYpXij8Tsdj5K/Rtesqco8UXEpcZq7A02oe4r+l4FrDlajWUAlMKsMcg/XDD55NHPeO7qMi6kFva7BRABvQpsMEe2hdap64D8AnBDBRHl6k4TGBHrn/KqYsTA3eYTwH3+6KW8= 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=PC/QqyE5; 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="PC/QqyE5" Received: by mail-pf1-f174.google.com with SMTP id d2e1a72fcca58-7aa2170adf9so3615639b3a.0 for ; Mon, 17 Nov 2025 05:26:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763386007; x=1763990807; 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=yJ9pJtF62LZXJAT0luPwqHz3BLuxpObXSz+phDq9x5Q=; b=PC/QqyE5zN22D8dOTrnhkoppHyu+e3svsKIjw1gY+npQ8G89b9K+BLmackOVu/tF0A xE9r9vxpoGSCHqHiJVQRG2mEpj5nvTb7bsXQsFcQrSWvADfIUdpe8AapF340axIwZuBE 07Cl0fkZMI099Mdc0VyFfepUdILa0nNHO5ma7mYg6nFXkAbVYzuOoy+sqJOgRYedHdzq mJdKiuuYeAWX+8J+/kU2NV6/vnF1yOtmCRc81iumW3AfALe0W0BguWi4HGaOdSfiUC6f y3iYO5nFMmwAusx24joYg4GcjeqqCSvezyadETGwlZrbfM7DZhtCIFoev0Fz0rzjoYUM /FdQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763386007; x=1763990807; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=yJ9pJtF62LZXJAT0luPwqHz3BLuxpObXSz+phDq9x5Q=; b=WmyWHvfoHP6StRuK9hDAFBda9yZisSUifqgjkBPM9B0BNqWlGEw+uS6FyVzwdvhYU1 7vTokGvq1rPz00q3JIjarW2xWnlyJeP1vFGJAwuJ9oY8OBD6JNDDkgmYY3fl34vI+WYX Cywc6AXRzruGMuUPOUm8EEjc/FMiUoAfQOdogNjPg3k6U77rfAV2m9caVSJ3zDYQVNXU kwAcyuZ7g5cW557mLq0hb7pyR+3UBfdrg+3xZZZ8FfRKZuZh2Ci9GL5roQm9EAQRf+25 QAMRE54SgjA2u/W+vxRfiIXsQOxP9heH93lVzq4z8bIQ7V02N1zSo/XOoGXN6Li6mOj3 yR6A== X-Forwarded-Encrypted: i=1; AJvYcCU897tVTUQ0YsvV7/xYbz/kvBkl1jWqL4ECQgVK0h70jP+ZEhg/mpe4btniU9wxWlq4WzS7nmr/cBFUJyA=@vger.kernel.org X-Gm-Message-State: AOJu0YyPcpjHE/Ejl5gnK05IzUUzf60lO+KxLFRy0s6IpqdwlXMWCWE5 pNH9ARhR/IFMNeyE7ONM7oATzLfyaliD2yY7hhYZe2fydqCdiIJbU1Lk X-Gm-Gg: ASbGncuYrtML4Dy830ZtKbQpwC7+j2fREIv1g0W8+no25lT46D8br27gsocxUp/ACpx +DlSgqCREampQXb1kc5cMdh3sup9ek7YeaoikGMFIXGYCEGbv572tcHiQMilctvTXpTRHg4l4Wm a/46yna3n9rVw0ViW3KdY8s6YWmPIgPh+v/eE4GMMAkvhkdC/+opP4FfubsAznugKLwL74cHjn9 m9pu+Ns2jxFSQfyHIV+caig2iald7fq0BO2IXB61s/pjYUTPgLkh8NS8qqHFf0O7dMvTDWN8C3D l1nUp4278VQzMMUdTdI9NsfR5DAdU8MorilZ59Gd/onuwaH7EImuew5t0WUSv1y+tGQwfToJPbh Pa8xRPLD96evdJ98cNjb4I3BM5O78Qu/8YNDiS1tkd/P4toiTHuSjTXDmdzfLWXMPhrwHS2UJI6 U1vveNBAOOr2umlLFhLcR9VUq16tc= X-Google-Smtp-Source: AGHT+IHA5iK4wG/HkFcfe0rJP4GZNcbweMfRLzaI9ghvyze6nCPnMhT+DU1blJmo3HvsWVSmn7L5KQ== X-Received: by 2002:a05:6a00:991:b0:7aa:5053:f42d with SMTP id d2e1a72fcca58-7ba3c665a52mr12595036b3a.22.1763386007052; Mon, 17 Nov 2025 05:26:47 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7b924cd89bcsm13220953b3a.15.2025.11.17.05.26.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Nov 2025 05:26:46 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v6 5/7] libbpf: Implement BTF type sorting validation for binary search optimization Date: Mon, 17 Nov 2025 21:26:21 +0800 Message-Id: <20251117132623.3807094-6-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251117132623.3807094-1-dolinux.peng@gmail.com> References: <20251117132623.3807094-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" From: Donglin Peng This patch adds validation to verify BTF type name sorting, enabling binary search optimization for lookups. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 60 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 60 insertions(+) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index bb77e6c762cc..b29f5859c10b 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 typ= e_id) return type_id; } =20 +/* Anonymous types (with empty names) are considered greater than named ty= pes + * and are sorted after them. Two anonymous types are considered equal. Na= med + * types are compared lexicographically. + */ +static int btf_compare_type_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; + + 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); + + if (anon_a && !anon_b) + return 1; + if (!anon_a && anon_b) + return -1; + if (anon_a && anon_b) + return 0; + + return strcmp(na, nb); +} + +/* Verifies that BTF types are sorted in ascending order according to their + * names, with named types appearing before anonymous types. If the orderi= ng + * is correct, counts the number of named types and updates the BTF object= 's + * nr_sorted_types field. + */ +static void btf_check_sorted(struct btf *btf) +{ + const struct btf_type *t; + int i, k =3D 0, n, nr_sorted_types; + + if (btf->nr_types < 2) + return; + + nr_sorted_types =3D 0; + n =3D btf__type_cnt(btf) - 1; + for (i =3D btf->start_id; i < n; i++) { + k =3D i + 1; + if (btf_compare_type_names(&i, &k, btf) > 0) + return; + t =3D btf_type_by_id(btf, i); + if (!str_is_empty(btf__str_by_offset(btf, t->name_off))) + nr_sorted_types++; + } + + t =3D btf_type_by_id(btf, k); + if (!str_is_empty(btf__str_by_offset(btf, t->name_off))) + nr_sorted_types++; + if (nr_sorted_types) + btf->nr_sorted_types =3D nr_sorted_types; +} + static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const ch= ar *name, __s32 start_id, __s32 end_id) { @@ -1148,6 +1206,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); =20 done: if (err) { @@ -1332,6 +1391,7 @@ static struct btf *btf_parse_elf(const char *path, st= ruct btf *base_btf, } else if (btf_ext) { *btf_ext =3D NULL; } + done: if (elf) elf_end(elf); --=20 2.34.1 From nobody Tue Dec 2 02:52:23 2025 Received: from mail-pf1-f170.google.com (mail-pf1-f170.google.com [209.85.210.170]) (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 25708335099 for ; Mon, 17 Nov 2025 13:26:50 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763386012; cv=none; b=sFnePnqzZKyS4KlZpXjLnJV3bRuVE0sV1bBIz75jXJ3S4uzFRyJkdFI/iII8b2LGhbeRr1g3+5BMOrrA7NL7u3GFUIC0DTPO/rOGGwpAL5TVSacyes2leWdfbvRxWyeoP9CoP3WNAG50f84BnYdGpa7JuTyIvJXQSjT4xMmfHtQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763386012; c=relaxed/simple; bh=1JCm2gAw7szR6coFfKCMu4oP2N4ZVTGa8uyyO11FaJ8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=HIHlAtXfPoYxo4m7XHdYlHxyTrh2fLa0mCOvw/Ps/FRChWMWAXuiIpBz6jb4aMm/aC0dT3ZvQpNtXUGRG0CHv2lNQrFSPH9X6lzjOiKDjPl2GJpIoCSe/0OTAFSNDKrfif6XUmAeS2uXu/CUxuPxPju1+kX1VDihk+XAtuD8qkI= 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=PHsqQuDl; arc=none smtp.client-ip=209.85.210.170 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="PHsqQuDl" Received: by mail-pf1-f170.google.com with SMTP id d2e1a72fcca58-7aa9be9f03aso3643632b3a.2 for ; Mon, 17 Nov 2025 05:26:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763386010; x=1763990810; 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=Rljz3QHqavQzM2+LGEfUj2V9NIFH9chI7oYU2DEYmt8=; b=PHsqQuDlNwAY1elomuaDEy31MbeeCCU1SuzOYsSJQJffwr+CpisCQCp7+g2XWq+UZH laLnj9Rr0BZ0pkt2XUJHJfeAr1ewJyqdpGwydJx4SbEH9FPB2Y0YOrxUG3V4hYQg133o iAaqLwuDwJESm3nvzWg8UdvYarnBxN6JTxW4t1Qs/OodcnVwF386H67tWnKnBGfsLqOo AMrjsLpKqc6Dz78yx5a36y1/gqbzvtL4uidDTsvGUHP4/27fF7vOnCkihQzNIzb3P3T6 t2sVKR83Dy+dtB0NyjU0YeU4lFjrEk7jTQf6ipF87S1WBglEOsksz+F7CjHtifQUiGhT eKBQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763386010; x=1763990810; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=Rljz3QHqavQzM2+LGEfUj2V9NIFH9chI7oYU2DEYmt8=; b=BBIKf/ulNbvxO0/iramF1UFc0+SVl13TwBRj6/KKN+g+Ch1UgSQCbr2j7zjpRQRvaw MzBTIaLwk/3K/tBKcQOQuBAl7Mcu1/U9myNXemwT9+DTgfh81JS4CGbwJmt6LJxj6iCs wREYPSduOwmOLQH6ambLnXXRMJenpxLxbxxfm0fneUVPM2+qDTuMPV8khOE/MH/lH1MU 6JCn9J+ozNrCxU3FYZovhnDCIknxDdc007RDltgJAQTNfeMQIEQ+E1kRfqvqRYXacIkt gJnnTraArQrJ7sqv/K4ZBTWvBkwihgCcbaShdS34LXlR1JEbT4MMKox/AaCDOkon1LZR n54Q== X-Forwarded-Encrypted: i=1; AJvYcCVlCRuzUe2pO12IrZa0xEVwHkt9Gh3aJxulvjkT/btR3L92K130buxw2yo+dSvmnvwhnjKMsBA/I1t9zRE=@vger.kernel.org X-Gm-Message-State: AOJu0YxD473bW/PrEivZAy9ZrePt9V09qJa8MBJ6f2qgH9AKer1nx46J ZaXMpHWygPs0bmKv1n1OWQVKuQQioPT97Fo8DcTxV5FysC9ZksH8SZ0K X-Gm-Gg: ASbGncuQQ1UtX8G8FT17OOdDY4hsI4N31RadCW1mJVKWJViez5uXXx/sn/9qaBlvdfB QfojtQEqyOunJPajrEPN+UjJMmQ/gTzg75yIe71PAR1qVOSyF8JS6xJFaXeTzcZicTg/88P2tzW taEWTN/SpUug1ep5PZs9zzaSmBkx/Ys7BKdut7Y2Lrfh3NfUvILdGNrdY35lCsis966FO4wjn9z KNo45HflrFDwkQ4rfhqt3U5IyxCXdcsD96IUZtNcBn0EzU3vs/RgzOcBS9sAAdp/cQ8/D1k6d2A K3RrPsuYmyadrOU0ecp8ecNA3xckQSWmWhuXDwUFaYAQq/iA1BcI4GdhXJnspIEdVDTByXdcxXr X4jptkVLsLtxNFhPtZnQpgtUNU12qU65YNnwiLFy+0ft39Yoa1CnsQjZiSzN0OeRuIVQXN55yMc cDUgu/oI1lno6CrM96lnU5KvW/k8fbFu7PAydVcA== X-Google-Smtp-Source: AGHT+IGP4GB/9/Y0zdSNgB4qCkHmeHyFO+LhNquHKW9wAN7N3l8vdfqdun9eXlCf+F53CHCFa5G+Xw== X-Received: by 2002:a05:6a20:6a05:b0:344:bf35:2bfa with SMTP id adf61e73a8af0-35ba22a50b8mr13339782637.33.1763386010418; Mon, 17 Nov 2025 05:26:50 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7b924cd89bcsm13220953b3a.15.2025.11.17.05.26.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Nov 2025 05:26:49 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v6 6/7] btf: Optimize type lookup with binary search Date: Mon, 17 Nov 2025 21:26:22 +0800 Message-Id: <20251117132623.3807094-7-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251117132623.3807094-1-dolinux.peng@gmail.com> References: <20251117132623.3807094-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" From: Donglin Peng Improve btf_find_by_name_kind() performance by adding binary search support for sorted types. Falls back to linear search for compatibility. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- kernel/bpf/btf.c | 83 ++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 73 insertions(+), 10 deletions(-) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 0de8fc8a0e0b..5dd2c40d4874 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; /* exclude VOID for base BTF */ u32 types_size; u32 data_size; refcount_t refcnt; @@ -494,6 +495,11 @@ static bool btf_type_is_modifier(const struct btf_type= *t) return false; } =20 +static int btf_start_id(const struct btf *btf) +{ + return btf->start_id + (btf->base_btf ? 0 : 1); +} + bool btf_type_is_void(const struct btf_type *t) { return t =3D=3D &btf_void; @@ -544,24 +550,78 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +static s32 btf_find_by_name_kind_bsearch(const struct btf *btf, const char= *name, + s32 start_id, s32 end_id) +{ + const struct btf_type *t; + const char *tname; + s32 l, r, m; + + l =3D start_id; + r =3D end_id; + while (l <=3D r) { + m =3D l + (r - l) / 2; + t =3D btf_type_by_id(btf, m); + tname =3D btf_name_by_offset(btf, t->name_off); + if (strcmp(tname, name) >=3D 0) { + if (l =3D=3D r) + return r; + r =3D m; + } else { + l =3D m + 1; + } + } + + return btf_nr_types(btf); +} + s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) { + const struct btf *base_btf =3D btf_base_btf(btf); const struct btf_type *t; const char *tname; - u32 i, total; + int err =3D -ENOENT; =20 - 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; + if (base_btf) { + err =3D btf_find_by_name_kind(base_btf, name, kind); + if (err > 0) + goto out; + } =20 - tname =3D btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; + if (btf->nr_sorted_types > 0) { + /* binary search */ + s32 start_id, end_id; + u32 idx; + + start_id =3D btf_start_id(btf); + end_id =3D start_id + btf->nr_sorted_types - 1; + idx =3D btf_find_by_name_kind_bsearch(btf, name, start_id, end_id); + for (; idx <=3D end_id; idx++) { + t =3D btf_type_by_id(btf, idx); + tname =3D btf_name_by_offset(btf, t->name_off); + if (strcmp(tname, name)) + goto out; + if (BTF_INFO_KIND(t->info) =3D=3D kind) + return idx; + } + } else { + /* linear search */ + u32 i, total; + + total =3D btf_nr_types(btf); + for (i =3D btf_start_id(btf); 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; + } } =20 - return -ENOENT; +out: + return err; } =20 s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p) @@ -5791,6 +5851,7 @@ static struct btf *btf_parse(const union bpf_attr *at= tr, bpfptr_t uattr, u32 uat goto errout; } env->btf =3D btf; + btf->nr_sorted_types =3D 0; =20 data =3D kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN); if (!data) { @@ -6210,6 +6271,7 @@ static struct btf *btf_parse_base(struct btf_verifier= _env *env, const char *name btf->data =3D data; btf->data_size =3D data_size; btf->kernel_btf =3D true; + btf->nr_sorted_types =3D 0; snprintf(btf->name, sizeof(btf->name), "%s", name); =20 err =3D btf_parse_hdr(env); @@ -6327,6 +6389,7 @@ static struct btf *btf_parse_module(const char *modul= e_name, const void *data, btf->start_id =3D base_btf->nr_types; btf->start_str_off =3D base_btf->hdr.str_len; btf->kernel_btf =3D true; + btf->nr_sorted_types =3D 0; snprintf(btf->name, sizeof(btf->name), "%s", module_name); =20 btf->data =3D kvmemdup(data, data_size, GFP_KERNEL | __GFP_NOWARN); --=20 2.34.1 From nobody Tue Dec 2 02:52:23 2025 Received: from mail-pf1-f175.google.com (mail-pf1-f175.google.com [209.85.210.175]) (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 7E2A633557D for ; Mon, 17 Nov 2025 13:26:54 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763386016; cv=none; b=p/Qk1D+H12jLnlsVyNSGtRlHSUld8tyJMKgjPqmxLchUxruSSgaQd1mllYskgwW8Q4Ax7/v4jvDIwDjzD2slnNsnrm2nPChSZ3M1swRAghl8l+ReiI+UeuF7J/uFq6CO0jiXVnk/RQy0fmnpiVtET5IQUFHTdzDw2pXw5dtuUao= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763386016; c=relaxed/simple; bh=ZUKwweoi/8nzVzk7XZ/MU1Z+niGdx/B7murw68s/Bp4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=kqVy6u6tCbJu7amTBAh36Kr6Fxjvfnck83e1mXU2wAhkjb8zlvlXt91MEiadwQonQO8AXyakIJBgm1bAzD1CLIROEnwNgdZQV8MOxjLXM/36NozCbkHlp1B0Vy3KnL4BLgidx/dZbxZfg4/wo0Eg4Vn4CzkdGsuAJfdgzuAGZcA= 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=OWaGHIDX; arc=none smtp.client-ip=209.85.210.175 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="OWaGHIDX" Received: by mail-pf1-f175.google.com with SMTP id d2e1a72fcca58-7aa2170adf9so3615745b3a.0 for ; Mon, 17 Nov 2025 05:26:54 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763386014; x=1763990814; 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=kUmHdLag/Zwi31gDv/2YF21TbKhBrlOl+Tx3LANhSGo=; b=OWaGHIDXAP7OGBMnmHhGk1TqhZNjmHjYNuPNG0QIJshfjw+bU0Zqif9IUUJYE5lQwE 9iuW0MnbiiPcc8UZ/yClPlE9FbvxWulDNeB1T5dc0yzsq7YIs37VW28afkIxV84QiblA yLsoQhzpXzjvkyrcPXQSH6MRtjZzCrXrcSdZzIVX8rPRY8d1so3PQClHd9wo5HJZkA4e Ke00994j/pWIp8j9v9t/aaeEb3befwYT9DFi9ltCbjvaUQXGSgqBTT7PixKPRy0uRJWn u2/fxAqq0pxFbt82dOWYU0bBLR9hh15fxgnut+sVRy3A9tn5RS3lHFDIkfFp0v4WHFKz ihYA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763386014; x=1763990814; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=kUmHdLag/Zwi31gDv/2YF21TbKhBrlOl+Tx3LANhSGo=; b=nnmcbFP3nx6zS9JNk39WmRwbWOVeN43SjIMuS3nsD9cASlkd2oUSsojDpLult2LgDi XzLPQOAsOj0pz54lhwUTmdd/e/f94stXPxPqXOlvtm4NIofOgUKDB35QgYWMZlg7+nCU TdGZyzsvkobIW2lQNM6kPfG3fiVK4EGD8MfaOU9jvC0QQzAVWRlG7wg/kJOYnlDnOQzM nyDvDfz9R5ab/mQmj9UWGQBM3oeEOrlAbEvmjWkbw+w5bPswSFt0cSbLX+oi/Y1MpiPL r9EEUq9+27npCyHN2h2DNLWeHsU12UoxuAvrpx3SsGYjBy3499ypWpfAgS10AjqM+TNk wafg== X-Forwarded-Encrypted: i=1; AJvYcCWsZbmv0FVn037AiZZUwfayHWugcH4j6wAbkunQSGCLRs8/At/bcv9NeyJqFiMUyj+g/IF7U+QlVr4gBdM=@vger.kernel.org X-Gm-Message-State: AOJu0YxD3MhAN+8CtociXlaSFly9rKmZ8EsXy1E2J22OtmZrgMP0G5Zb eyaw4xXWG8nwxf3fXA+x9tEi8ddTL4LB1qqKEppn20Ra6hvgZB79YwNE X-Gm-Gg: ASbGncuQouh4cn0zBbQMjJJdRaYR7cWPP/xohOrRwgMPFBqFmA6ee5c8AB4I1C40qvU qJp/tUqSqCS+8/azVlMUFq5nN0usY5uLx73p9zfRJzHhTOaSXfecRUKSLEw+1hptUnFw/NCwW5E vtF8jeUw1tdEaGEtUsHfoNkZlNApr9ZJe00W2SqfZKv+eFJqdbsMA3VFj24o1kw/dpZ38/eDPA4 ttW/5SORCtfKdxDY8pVrUVn83vNwJxsTnVhn8ocuv07AmB4ldbTBFIRXzHBY5LuBIc/wR2eT+iS YZTWyZYwSTAakMnRvx8LgHNLvCLhvg2t41Ktm+6Z1wP5BcgvRdtJicLwJ4Hgt8uLruVDlMSDjG6 Z2jQmA1mMa8BHjJ4rIBfS+4kS+/dznxPxeXgGtrT7hW6UvHPBHVQHEJsg5Eudy6DwBoxLBNZbIf DY1RqNvmd65GA2Xfe/g7Q3IBjvEEM= X-Google-Smtp-Source: AGHT+IH7nNeUVTI5MtzgwWkfmohW7BLPU8Ki2zP/T6SA+lyofQHTyXWYuBQSpmsX91Ot+Ie2xHqq2g== X-Received: by 2002:a05:6a20:9389:b0:35d:6b4e:91f1 with SMTP id adf61e73a8af0-35d6b4eb84amr8682137637.34.1763386013790; Mon, 17 Nov 2025 05:26:53 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7b924cd89bcsm13220953b3a.15.2025.11.17.05.26.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Nov 2025 05:26:52 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: eddyz87@gmail.com, andrii.nakryiko@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v6 7/7] btf: Add sorting validation for binary search Date: Mon, 17 Nov 2025 21:26:23 +0800 Message-Id: <20251117132623.3807094-8-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251117132623.3807094-1-dolinux.peng@gmail.com> References: <20251117132623.3807094-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" From: Donglin Peng Implement validation of BTF type ordering to enable efficient binary search for sorted BTF. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- kernel/bpf/btf.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 64 insertions(+) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 5dd2c40d4874..e9d102360292 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -550,6 +550,66 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +/* Anonymous types (with empty names) are considered greater than named ty= pes + * and are sorted after them. Two anonymous types are considered equal. Na= med + * types are compared lexicographically. + */ +static int btf_compare_type_names(const void *a, const void *b, void *priv) +{ + struct btf *btf =3D (struct btf *)priv; + const struct btf_type *ta =3D btf_type_by_id(btf, *(__u32 *)a); + const struct btf_type *tb =3D btf_type_by_id(btf, *(__u32 *)b); + const char *na, *nb; + + if (!ta->name_off && tb->name_off) + return 1; + if (ta->name_off && !tb->name_off) + return -1; + if (!ta->name_off && !tb->name_off) + return 0; + + na =3D btf_name_by_offset(btf, ta->name_off); + nb =3D btf_name_by_offset(btf, tb->name_off); + return strcmp(na, nb); +} + +/* Verifies that BTF types are sorted in ascending order according to their + * names, with named types appearing before anonymous types. If the orderi= ng + * is correct, counts the number of named types and updates the BTF object= 's + * nr_sorted_types field. Note that vmlinux and kernel module BTFs are sor= ted + * during the building phase, so the validation logic only needs to count = the + * named types. + */ +static void btf_check_sorted(struct btf *btf) +{ + const struct btf_type *t; + int i, n, k =3D 0, nr_sorted_types; + bool skip_cmp =3D btf_is_kernel(btf); + + if (btf->nr_types < 2) + return; + + nr_sorted_types =3D 0; + n =3D btf_nr_types(btf) - 1; + for (i =3D btf_start_id(btf); i < n; i++) { + k =3D i + 1; + if (!skip_cmp && btf_compare_type_names(&i, &k, btf) > 0) + return; + + t =3D btf_type_by_id(btf, i); + if (t->name_off) + nr_sorted_types++; + else if (skip_cmp) + break; + } + + t =3D btf_type_by_id(btf, k); + if (t->name_off) + nr_sorted_types++; + if (nr_sorted_types) + btf->nr_sorted_types =3D nr_sorted_types; +} + static s32 btf_find_by_name_kind_bsearch(const struct btf *btf, const char= *name, s32 start_id, s32 end_id) { @@ -5885,6 +5945,8 @@ static struct btf *btf_parse(const union bpf_attr *at= tr, bpfptr_t uattr, u32 uat if (err) goto errout; =20 + btf_check_sorted(btf); + struct_meta_tab =3D btf_parse_struct_metas(&env->log, btf); if (IS_ERR(struct_meta_tab)) { err =3D PTR_ERR(struct_meta_tab); @@ -6292,6 +6354,7 @@ static struct btf *btf_parse_base(struct btf_verifier= _env *env, const char *name if (err) goto errout; =20 + btf_check_sorted(btf); refcount_set(&btf->refcnt, 1); =20 return btf; @@ -6426,6 +6489,7 @@ static struct btf *btf_parse_module(const char *modul= e_name, const void *data, } =20 btf_verifier_env_free(env); + btf_check_sorted(btf); refcount_set(&btf->refcnt, 1); return btf; =20 --=20 2.34.1