From nobody Tue Dec 16 13:22:08 2025 Received: from mail-pl1-f178.google.com (mail-pl1-f178.google.com [209.85.214.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 4EF3E3112C9 for ; Mon, 8 Dec 2025 06:24:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175044; cv=none; b=fxCEoWqz5vbx6simvn1Sv3+SZUDrQ5+MYlinzn2Zr1wICo7DDCMeqHRJr0uRGSFZa1rUI9nEL5moT7O6ItY0WxmjKe23rGnkjUMdPHeLxwIahtU/A6lDdPgnmBzpOny09vPdjeqUjwnbjubKta8ZR30TkEXLcQlpdJ5tVqypua0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175044; c=relaxed/simple; bh=YJNPYvfz/GxoZXv79UmIYENyuKk2IR71wtQ8M88Szf8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=BVtTItHtCsQVtmIaVQrZQtz8vsYWDdzHzmk+gTdD2OXs3KiYCPmAcVpeRKGAtuws/N2ANLMII/Ym2NMZKrUR+PvadStMBkhlYomAObRBtOM+s2nXcP49P9mZIYDyWpTIHkxjtbck3C0NxBUeefZ8qN9kNCVrr3aOMa51PP9pijg= 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=Inscpo3i; arc=none smtp.client-ip=209.85.214.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="Inscpo3i" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-298145fe27eso63661575ad.1 for ; Sun, 07 Dec 2025 22:24:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765175042; x=1765779842; 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=a4S21SvMIVWAPa44TWVxWwB/nChiaz6KYgp24im87ZU=; b=Inscpo3i+e7+hcrXGUjDbYmK2EgvOjf3TpzoG2alf8+Ih3hY8y76kTXcux+zI0CsRT UVNAACh5kfYpgGG6OmPlIoGNa2dA0zsfp7ZyvD4/t743MLOKmvAoNLZMOG/TlT9dyEXN OUEYa66k/IQ9z+AXToX0w6rM/6Cc+qKIP+Idrr6eMypif5cS/bbtPFtuGyFxLYFZrqNZ KKSiaUQkpjqJnfJ5BUOAQ5fpeQWi7kA+kshIA4WU/jMQ0erM1hPHDlBPm8AzIz3+Qb1v EuD3HWK7luOBG3aCzGNbGnrpplY9fmELCtlxqEYzG5gPJp2+i/Zza50fsScuLk3Q3pGR y/CA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765175042; x=1765779842; 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=a4S21SvMIVWAPa44TWVxWwB/nChiaz6KYgp24im87ZU=; b=mFx9SJpwbt6nLuULckM4zOiu5k9izEpfXg8SOUHaQnK+POC/UkrXPb+vkCEs5tRcyO Yf4YdR2z1VbavHQLxEy+q/x1UQWra7cC8k0/6iy/cIbmg1KeVlU5MhYu3TLd6nmBPMtw amyNIigSuHDrXS9XRiGeH8qIuoz/X3irHJXOe0lFbzJ8IaI0Fs1mLZKX7UCVFQZ1mWka lTsOZlnpOu54Qn22K9Gw9ifTFU+W3kVI+FfdUmrkJOwLyKdLsbHYq9lDmOxU/6aGwV++ jsc5Pgitwj7X+0fqNBUiiAFWD4ovTkoli9m7f2BW+kOApE9oNDOFUwBdBpuzTn3O2olJ +sug== X-Forwarded-Encrypted: i=1; AJvYcCW52ymvBb4J6KOzcgyyoj4dOxSHt+uZlDdEKhgsnoGb1xW3oOF9v1earpdvaIJvGEKFly4lNHkEH8xv7lA=@vger.kernel.org X-Gm-Message-State: AOJu0YzJ6v6t0Vy3DNMxLnGNvtsxqbpALshBZ6O/IHlj4FsW9RBsg66V C/Ovb2OH+5mJQkdaXe5daTcXUef/cAshcBvo/XLdiFTIWT6RKIMjWLlN X-Gm-Gg: ASbGncsMGm87YQn0jwXHM6LF2040lR8PkLAsq7P+60QywTpJuXmtuBykYzwdG0ZZR1o gtUNcIVoRkq0OZIs15iMzuLPA6/bPq7VvwI+1U8ayh6YilI+D2f5RePtbcPvI7lg55pcDpfW9U3 /+9UjWDtI04SDWyJJXJc0G8HYiPFriJC2Al8+C+4OPIRRibIX+BeUwhmnYqvQt7fewzAqrflhJa LjL072tP+16MZii0HxbApjFD7YefTp148sLTTVCgmXxfFs4BknvTvj01LvQjn11C+DYOVAN6nqE r7JzC2FThjzkHXTiaRy+gkJEiqw6uQ/MxivcKWOo9HTslUnucPIJGSVYXFDNjZFdf1imYEVstuF sb1iNdYSk2SdMPqV1QxGh2wBRkQjZI/T58ejTBYMpAVHcYRLHhIwfxNdwVbHdoPxf3WBsaJKj6R I33wGz60I60o/bHV9RZV6QIYv3lAeOVOcmOdwOMg== X-Google-Smtp-Source: AGHT+IESItLESSFpTG1CYIdpiSzT8flxRzcPch7BNYUfij3sEBe7Ci9gXvzRv/G+40+kodvXfyshTQ== X-Received: by 2002:a17:903:294b:b0:29b:e342:3e3c with SMTP id d9443c01a7336-29df5684a61mr40322655ad.21.1765175042517; Sun, 07 Dec 2025 22:24:02 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-29dae49ca1esm112555855ad.2.2025.12.07.22.23.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 07 Dec 2025 22:24:01 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [PATCH bpf-next v9 01/10] libbpf: Add BTF permutation support for type reordering Date: Mon, 8 Dec 2025 14:23:44 +0800 Message-Id: <20251208062353.1702672-2-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251208062353.1702672-1-dolinux.peng@gmail.com> References: <20251208062353.1702672-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: pengdonglin 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: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin --- tools/lib/bpf/btf.c | 119 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 36 ++++++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 156 insertions(+) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 84a4b0abc8be..26ebc0234b9b 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -5868,3 +5868,122 @@ 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; +}; + +/* 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; + + /* refer to the base BTF or VOID type */ + if (new_type_id < p->btf->start_id) + return 0; + + if (new_type_id >=3D btf__type_cnt(p->btf)) + return -EINVAL; + + *type_id =3D p->id_map[new_type_id - p->btf->start_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 *nt, *new_types =3D NULL; + __u32 *order_map =3D NULL; + int err =3D 0, i; + __u32 id; + + if (!OPTS_VALID(opts, btf_permute_opts) || id_map_cnt !=3D btf->nr_types) + return libbpf_err(-EINVAL); + + /* record the sequence of types */ + order_map =3D calloc(id_map_cnt, 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]; + if (id < btf->start_id || id >=3D btf__type_cnt(btf)) { + err =3D -EINVAL; + goto done; + } + id -=3D btf->start_id; + /* cannot be mapped to the same ID */ + if (order_map[id]) { + err =3D -EINVAL; + goto done; + } + order_map[id] =3D i + btf->start_id; + } + + p.btf =3D btf; + p.id_map =3D id_map; + nt =3D new_types; + for (i =3D 0; i < id_map_cnt; i++) { + struct btf_field_iter it; + const struct btf_type *t; + __u32 *type_id; + int type_size; + + id =3D order_map[i]; + t =3D btf__type_by_id(btf, id); + 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; + } + + for (nt =3D new_types, i =3D 0; i < id_map_cnt; i++) { + btf->type_offs[i] =3D nt - new_types; + nt +=3D btf_type_size(nt); + } + + 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 cc01494d6210..ba67e5457e3a 100644 --- a/tools/lib/bpf/btf.h +++ b/tools/lib/bpf/btf.h @@ -281,6 +281,42 @@ 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 1 to `btf__type_cnt(btf)-1` + * - @id_map_cnt should be `btf__type_cnt(btf) - 1` + * - Mapping uses `id_map[original_id - 1] =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` + * + * 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 16 13:22:08 2025 Received: from mail-pl1-f174.google.com (mail-pl1-f174.google.com [209.85.214.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 86EC33126B5 for ; Mon, 8 Dec 2025 06:24:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175048; cv=none; b=QiCzHq9sbFzVDIAQEDJK3xwQ15rXSumfSDfv1ASU9QprvpMRdwwbKIXz8eGMGl9trjxHh5Rpka4D1jEgx3sI7pCPgLMe7ciC4cCX0rm6C/BuUgtsx4NNcAW798FauhVuKEaVHDPA+cO8cH1X2TJPAf+Ez9HYNTc2T671eLQiw7Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175048; c=relaxed/simple; bh=7ngEULL678quRrsmJ39omINLf8wh8oMlVDKhnztkP/E=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=nejVd1LKy5+M75wvMafuaky1hyx9D/7BVJCulNHye5VHC1dAnYPgii6hhBMz8uFMPR9dGKWSWo9XdpIB8s4HeHvGdLz+6wGaFNEcYwjqdHVJ1hKeFPkqow4yKLYHCEsv+yVBCZSm6pYfpo0BYrK8Uf9a+9H2XEbKhiD/azaaXek= 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=nj31hE65; arc=none smtp.client-ip=209.85.214.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="nj31hE65" Received: by mail-pl1-f174.google.com with SMTP id d9443c01a7336-29568d93e87so37342405ad.2 for ; Sun, 07 Dec 2025 22:24:06 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765175046; x=1765779846; 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=9qbxRcU+iIJswxukru9rEL0qIQsiT5P658wY0LXDT54=; b=nj31hE651SuQWFv6TNcZkwiCRP8BO6KFIg4XxO5uqBQEPsv3aqkHf3UG0AAtFPWbPb oyblZjQ5wrTR1h7sZBqZOoQqndqSQcX/0UZBNnV+jUPMUqWqI/Fwg5b2OlssiyL36tMV 2pzEtXGf5m+owB2FtlyU3zA9hzgxABzKFIKxM6WG0tLgu0bpZRQmJ2hrzIY4dmXMiGl2 uSiWr26oszLmsYQ6zL+rsNSeXmTndMqqvdovTKOv5A1l4M2hv3FiLp8XjgA38ay5tQZ2 4XADNuYeMcAfn9g9o0XZqcELP+iwt3RpcOFaTEWOF/0gatFzfj5fyozMOFh7QbT4MF9c /psg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765175046; x=1765779846; 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=9qbxRcU+iIJswxukru9rEL0qIQsiT5P658wY0LXDT54=; b=tvvCC0kTjdq4H6BltE8/KjOIWP+hFHhKBk7saSpnRBDpdu0NEeDSH6rVP3ENFpK2ao z22BrVrRIGGunv62EeoHN5z6gcIiAid3KDjX7/WP7Te6BxoLzSWjilTlyqIu4z7IN2Td Pv9GKmPvIiBq6lGLQ/jflhqkRFzIu0WBU9dRCdHgcsX7ieVmRvbwi/PI7YwTbFQmrjq8 Kqw+7eaV15nAyjDnquVNjZe6ds7c0AQQ4ODb2yIhytXg2MvGAuZkmn+9Azov4JxS1YZN JNQaCjavOx8Pd0Brq8wf+CHxCXzHRiTQiOFx0LJFuo/AfRvNxgaXyR0lxpHuOV9MBWas JIdQ== X-Forwarded-Encrypted: i=1; AJvYcCX6+yTYh5SjQ17zAXjAI6A1cXoJEnSpGvSmQ5UlFNF7Rb1u9XTJXL/PQdAcU/9f+qg5/VT5OQ1dPSK7y7U=@vger.kernel.org X-Gm-Message-State: AOJu0YxdrSsuqMjDKVOGE1DxVxSSy5xJJsCc50h5sNAUykhM5w/NmAi4 R0IJUv6waHGgR3cbUY3S9G4r2YrdMN9prFiUcoK8VyPdBpGafPK+wyWu X-Gm-Gg: ASbGncsXdrnQ6F/O/sQqMt2WzuEUyLHKe2KckY6w1xI12/sG/EqFnnPoyYp7jEorbC3 Jwl17v/iQ0I+M6PbmoB5PLc6Co8PPB7LeqsLa6kG1e0AHV4HA4kTd8DjIu7os5Y0y18qv9GshKT Lufvw8UlOEhKox1TKsZVJHLgAkkHr8LsPnOGC3MPJeqtqC16vig3NexcEf0KzD6aiWQF2R+zZb5 EUXdCYoF1Mv14bk96LIMVoh2Rih4JGj93i/5qLHjPm3Psbx2FA2F1JaOkU6A1hGpSEVUnebQEYS big9azmAcz27Bqu5ZGRvJPmxlOLWwLVAjqnpoFQwpdFYrzCYy2VPg292eg4f2AyHPxrzJ5wU3dO 55zwY8JRbB9QZYTpfw2EQuJnkII/1YhP73QAYR9PTAFOuzaUKeJpJN7dbfz7mbVXdxVNMz4ze1F jLLCi9M3tRySgYyrDy+mewnvak1wk= X-Google-Smtp-Source: AGHT+IERiY+8ZnMLvZa+B1nEe/0Kkuwb7fx53ZHc+psgLhl1HZsx4sl76ERZ0/x9WuEX8c0sMUxeIQ== X-Received: by 2002:a17:903:2c0d:b0:295:c2e7:7199 with SMTP id d9443c01a7336-29df610eabcmr60906455ad.29.1765175045916; Sun, 07 Dec 2025 22:24:05 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-29dae49ca1esm112555855ad.2.2025.12.07.22.24.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 07 Dec 2025 22:24:04 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [PATCH bpf-next v9 02/10] selftests/bpf: Add test cases for btf__permute functionality Date: Mon, 8 Dec 2025 14:23:45 +0800 Message-Id: <20251208062353.1702672-3-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251208062353.1702672-1-dolinux.peng@gmail.com> References: <20251208062353.1702672-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: pengdonglin 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 Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin --- .../selftests/bpf/prog_tests/btf_permute.c | 228 ++++++++++++++++++ 1 file changed, 228 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..9aa71cdf984a --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/btf_permute.c @@ -0,0 +1,228 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2025 Xiaomi */ + +#include +#include +#include "btf_helpers.h" + +static void permute_base_check(struct btf *btf) +{ + 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"); +} + +/* Ensure btf__permute work as expected with base BTF */ +static void test_permute_base(void) +{ + struct btf *btf; + __u32 permute_ids[6]; + int start_id =3D 1; + 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[1 - start_id] =3D 4; /* [1] -> [4] */ + permute_ids[2 - start_id] =3D 3; /* [2] -> [3] */ + permute_ids[3 - start_id] =3D 5; /* [3] -> [5] */ + permute_ids[4 - start_id] =3D 1; /* [4] -> [1] */ + permute_ids[5 - start_id] =3D 6; /* [5] -> [6] */ + permute_ids[6 - start_id] =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; + permute_base_check(btf); + + /* id_map_cnt is invalid */ + permute_ids[1 - start_id] =3D 4; /* [1] -> [4] */ + permute_ids[2 - start_id] =3D 3; /* [2] -> [3] */ + permute_ids[3 - start_id] =3D 5; /* [3] -> [5] */ + permute_ids[4 - start_id] =3D 1; /* [4] -> [1] */ + permute_ids[5 - start_id] =3D 6; /* [5] -> [6] */ + permute_ids[6 - start_id] =3D 2; /* [6] -> [2] */ + err =3D btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids) - 1, NULL); + if (!ASSERT_ERR(err, "btf__permute_base")) + goto done; + /* BTF is not modified */ + permute_base_check(btf); + + /* Multiple types can not be mapped to the same ID */ + permute_ids[1 - start_id] =3D 4; + permute_ids[2 - start_id] =3D 4; + permute_ids[3 - start_id] =3D 5; + permute_ids[4 - start_id] =3D 1; + permute_ids[5 - start_id] =3D 6; + permute_ids[6 - start_id] =3D 2; + err =3D btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL); + if (!ASSERT_ERR(err, "btf__permute_base")) + goto done; + /* BTF is not modified */ + permute_base_check(btf); + + /* Type ID must be valid */ + permute_ids[1 - start_id] =3D 4; + permute_ids[2 - start_id] =3D 3; + permute_ids[3 - start_id] =3D 5; + permute_ids[4 - start_id] =3D 1; + permute_ids[5 - start_id] =3D 7; + permute_ids[6 - start_id] =3D 2; + err =3D btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL); + if (!ASSERT_ERR(err, "btf__permute_base")) + goto done; + /* BTF is not modified */ + permute_base_check(btf); + +done: + btf__free(btf); +} + +static void permute_split_check(struct btf *btf) +{ + 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 '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"); +} + +/* 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; + int start_id; + + 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"); + + start_id =3D btf__type_cnt(base_btf); + permute_ids[3 - start_id] =3D 6; /* [3] -> [6] */ + permute_ids[4 - start_id] =3D 3; /* [4] -> [3] */ + permute_ids[5 - start_id] =3D 5; /* [5] -> [5] */ + permute_ids[6 - start_id] =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; + permute_split_check(split_btf); + + /* + * For split BTF, id_map_cnt must equal to the number of types + * added on top of base BTF + */ + permute_ids[3 - start_id] =3D 4; + permute_ids[4 - start_id] =3D 3; + permute_ids[5 - start_id] =3D 5; + permute_ids[6 - start_id] =3D 6; + err =3D btf__permute(split_btf, permute_ids, 3, NULL); + if (!ASSERT_ERR(err, "btf__permute_split")) + goto cleanup; + /* BTF is not modified */ + permute_split_check(split_btf); + + /* Multiple types can not be mapped to the same ID */ + permute_ids[3 - start_id] =3D 4; + permute_ids[4 - start_id] =3D 3; + permute_ids[5 - start_id] =3D 3; + permute_ids[6 - start_id] =3D 6; + err =3D btf__permute(split_btf, permute_ids, 4, NULL); + if (!ASSERT_ERR(err, "btf__permute_split")) + goto cleanup; + /* BTF is not modified */ + permute_split_check(split_btf); + + /* Can not map to base ID */ + permute_ids[3 - start_id] =3D 4; + permute_ids[4 - start_id] =3D 2; + permute_ids[5 - start_id] =3D 5; + permute_ids[6 - start_id] =3D 6; + err =3D btf__permute(split_btf, permute_ids, 4, NULL); + if (!ASSERT_ERR(err, "btf__permute_split")) + goto cleanup; + /* BTF is not modified */ + permute_split_check(split_btf); + +cleanup: + btf__free(split_btf); + btf__free(base_btf); +} + +void test_btf_permute(void) +{ + if (test__start_subtest("permute_base")) + test_permute_base(); + if (test__start_subtest("permute_split")) + test_permute_split(); +} --=20 2.34.1 From nobody Tue Dec 16 13:22:08 2025 Received: from mail-pj1-f52.google.com (mail-pj1-f52.google.com [209.85.216.52]) (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 1CCDB31283C for ; Mon, 8 Dec 2025 06:24:09 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.52 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175051; cv=none; b=MNlTUQntxo9EtPLBGoatN+VmLzxHOn4GBIh2ydH7zcbhFgbNY0LJDKPsd+z2NqDXJP3TKsyvAFXlpHpTBaxti35AySCP7/nSwtZ/c4iwNtJbDvlZtSiDqor9v1uWs31obw2ZOmDJldJo3Wb1LqClMaC9wzDMGEMuo3pgRUOI8Z0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175051; c=relaxed/simple; bh=3rLB0CW9qfHiGp6ErABQKSZNXCfm5echOS1kCj5vYuQ=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=JPQiBIsFpfotiJSeCTNKyeslu9RFHhxUBqMblNBr/roSb98WJl73hILW7T+DUB6NCyNTrWph5gMEr2F3slkqG0VCj5uiNjN+98xAy7vaak+1uqMVSAkbF9tPrwK4vCrAFpk1kBgKYAZ4UWE5YmKexCD8UBcC2ZFR7RTIiLz+sxY= 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=fj7VFaED; arc=none smtp.client-ip=209.85.216.52 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="fj7VFaED" Received: by mail-pj1-f52.google.com with SMTP id 98e67ed59e1d1-349bb6f9c86so1782764a91.0 for ; Sun, 07 Dec 2025 22:24:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765175049; x=1765779849; 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=EY1TWHNFPcsVIc12Ea6xmmHpfxEDNasl0yTuoxu3Vmk=; b=fj7VFaEDprC/BgNDn2oPTo+YhqQNO3X60sVic1QNd//WmYPx/Dna4sSwphu6QaeQiJ KdK/fS63i4IeCrTusVXkFt+4ZVTaCOTGlseGu99rJjAVVwPWQLnJI/LsCj8VgIXH7Idd bE/5lJbwErc8t3NcsAaORlbVIzgo1cJG62P16hgTHfgjr/G4GeE3/4pGQ5d/g6A8ZFP0 10ibizOq1nBBFyiLF+e+k+FCx+PRV/+BdBc/qhgTXNEsNMSgdbCzN6UfWRiT8nTL3sus eqiZRBtpr88tYr8TMUwT8co65FlcbR3GjnvwC82Qv3YHwbTbGeIkC6kJmMX47LuAKk/r 12Rg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765175049; x=1765779849; 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=EY1TWHNFPcsVIc12Ea6xmmHpfxEDNasl0yTuoxu3Vmk=; b=FgTzhpopChEE1E7bGcbpe15VL7Tfu56ffWA2K1GqB04Me/FHpZgUxq3qTBEZ7O034A j22gtlAugJ7bV5+fRuftlh0Ft458AJpSboQXnmSs0wS8E5Ub/h9eiP0Ir5oaGeSGr3xR uVNAFskWn347uE+lbvi8vFfUcbbvj3M0NYnoiVpxyrullyoxtfUxacr21qEBd0Co8M3d qoRjJUuEjjUopmMo5HNV+pkfDzmXf5aUX2pDEFNN4XehyLBEYbySY2Ek4rFdMmkiqaLl 5krDdl2ToaZp5c3Rp850IwVmDk+fXccmMPhLjurdHHztE6QXVLP+NFGdxYJ5XXNFkCPW 946Q== X-Forwarded-Encrypted: i=1; AJvYcCXglprFE9Rb0+QHT6/yHxdhXUPqAUvICA5WaifgdBmf9meI7SmUeY37DYkDYFxC6DRHE8ZPqGBMiOCJD/0=@vger.kernel.org X-Gm-Message-State: AOJu0YyM69+7YUhsY44b+mDFzXJbNoB4i9fmKw/GbpysrnkFQEb7YceY w0D3iEyMsVCoACDqm+dZFFl2p6nN8C340AKxsuArJ8imWTVJ9tOIotWi X-Gm-Gg: ASbGnctdaFgRVxS03A/bUd295XIMoC5xCTFz/NcWnKsWsJ+QrIt0Tv/oerw8ewbPsfH QmJ3oqtA7M6D3G8Uj+r+fPqlF10v4nk/Re8xu2OFs+3e5lYWISfLFhJMruw6hNPFVae6DA3ZMdJ eRqOvwMNHNYgbVH4v6ASt9D3MrHTX5GmmJglfDI3jYgeD4AE36MSgHnD5JOGkxW5JqzT4K+xitN kXLwqAfXHemkGIk5tqtukWRuKXFhAhU2q9Wzfa/X8AvX/shmI1WcD855/1JCOO4xheG9T9L+qM8 i+5jpYM3V5BEMjm/4x4Juse1vVXlJOPZmDAUrlvZvp/DiNGUaPYJg7dRINyRTmD4BgcBag4sSs8 TjAea03IRLMoGd00lh1LxVdVbA8MhOV+s78Ed8Nc+sjYmJzp2jR3UoUvmIa1sSauw6VjUtEFpA2 D8+QWGi0pzMN0IoUaKJHH6sgOLxzU= X-Google-Smtp-Source: AGHT+IF9+KuXLJhhdEAvE3hYuv26uDkEHScuCmf/MnF4W8DJO/REbJbcGF8slRlk9j+3UTPcjBmJhw== X-Received: by 2002:a17:90b:5144:b0:340:d81d:7874 with SMTP id 98e67ed59e1d1-349a262ddaemr5369756a91.26.1765175049325; Sun, 07 Dec 2025 22:24:09 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-29dae49ca1esm112555855ad.2.2025.12.07.22.24.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 07 Dec 2025 22:24:08 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [PATCH bpf-next v9 03/10] tools/resolve_btfids: Support BTF sorting feature Date: Mon, 8 Dec 2025 14:23:46 +0800 Message-Id: <20251208062353.1702672-4-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251208062353.1702672-1-dolinux.peng@gmail.com> References: <20251208062353.1702672-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: pengdonglin This introduces a new BTF sorting phase that specifically sorts BTF types by name in ascending order, so that the binary search can be used to look up types. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin --- tools/bpf/resolve_btfids/main.c | 68 +++++++++++++++++++++++++++++++++ 1 file changed, 68 insertions(+) diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/mai= n.c index e0e792017e77..b4ec3b556518 100644 --- a/tools/bpf/resolve_btfids/main.c +++ b/tools/bpf/resolve_btfids/main.c @@ -846,6 +846,71 @@ static int dump_raw_btf(struct btf *btf, const char *o= ut_path) return 0; } =20 +/* + * Sort types by name in ascending order resulting in all + * anonymous types being placed before named types. + */ +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; + + 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 sort_btf_by_name(struct btf *btf) +{ + __u32 *permute_ids =3D NULL, *id_map =3D NULL; + int nr_types, i, err =3D 0; + __u32 start_id =3D 1, id; + + if (btf__base_btf(btf)) + start_id =3D btf__type_cnt(btf__base_btf(btf)); + nr_types =3D btf__type_cnt(btf) - start_id; + if (nr_types < 2) + goto out; + + 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, nr_types, 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)); + +out: + free(permute_ids); + free(id_map); + return err; +} + +static int btf2btf(struct object *obj) +{ + return sort_btf_by_name(obj->btf); +} + static inline int make_out_path(char *buf, const char *in_path, const char= *suffix) { int len =3D snprintf(buf, PATH_MAX, "%s%s", in_path, suffix); @@ -904,6 +969,9 @@ int main(int argc, const char **argv) if (load_btf(&obj)) goto out; =20 + if (btf2btf(&obj)) + goto out; + if (elf_collect(&obj)) goto out; =20 --=20 2.34.1 From nobody Tue Dec 16 13:22:08 2025 Received: from mail-pf1-f180.google.com (mail-pf1-f180.google.com [209.85.210.180]) (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 934133126B5 for ; Mon, 8 Dec 2025 06:24:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175055; cv=none; b=RjxaoZPrml+pDO/6jLuuORaG1zSl1hm0GQgu+dZdoU+yagsOyyRaBRQ8t6NQ/cMBURM1Vqocoi8RZKUyrD1Oiy9uFAPVNwtlSzVJ1DL8CoOgAXHZd2XBIuHJpNsPChy3MU63GYgZTwF+Puq8HNR1dionrlE+3VjDOzh4jzsW1TQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175055; c=relaxed/simple; bh=d3DscDcBlQkBeK2zxMbgxBMfQr0YMduHtPVlM/+IxLc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=odhnGgU+pOghkwKVVSGPvSISKVAryDAgBQcheAxokQKHOKseLltc+OMFaxdon4iG+KPCueUyG5ALf9XU/NMp+eeOwzz3B8H0bKjtWMNYIXzgQjCgVduHBuKAkcU/J3vFJ9lP6ut8c+IWHJF3F82KZ3XUV4GzC7UXKJuTckK3j7M= 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=ATfACYKh; arc=none smtp.client-ip=209.85.210.180 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="ATfACYKh" Received: by mail-pf1-f180.google.com with SMTP id d2e1a72fcca58-7b9c17dd591so3717525b3a.3 for ; Sun, 07 Dec 2025 22:24:13 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765175053; x=1765779853; 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=Ay7fnOLJudeGNu6Y3I2222JeR4NzT0GvBbta2hSfvtU=; b=ATfACYKh0KmfZyazUaUgBUYGLQAdvuT69fn4lsx5rk9mTgT6rCO0Plqkumwxt6CzaI uPcvWLN54kSABX/rt9s6DQZz+Y9WMCZnZEYLF0CLT2pvKKffM7RMROOuU7eQ31Ro6WqI MIXxpxq+ZMthz96pwediia9HCW4bSF65cBCguMet9vPzc/RAz+58JyrmRWVZjSqjxSEN p2OGQV9S4p/cea2CdDcgsm21jIMjbYd1Br5YF72JSNbh7bWPxBIKPtN7F869p9lMc81Y cxjUCSMYsG2t/gOv8rky71+O29NPA7JFW6fpwv6JZ6gEUhZCBQzELchZHbNDXZib8V4D CJEA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765175053; x=1765779853; 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=Ay7fnOLJudeGNu6Y3I2222JeR4NzT0GvBbta2hSfvtU=; b=rtDZ6FUgvGp0jmrN2qfg4tKYYTy0PUltwNaGJOiiXeX5DAwtqq8mhmii3pxd1eR64c RES2A14JQBwM2e9VmP7YPofMakuFe521RyUxLbY4h4ITz/iZY0Eujj65gV3e//O2YOqe 7wd9uzABvBHcSWbvz8dPmnziqamhDcvr9nfGHcRCSr14A50L3px0jwAXaafDDd/kC2SD Pn/aptSyKlaofA60G2SX9huYBjwLWLR8nrd9TFSRJZ/pjaqm72RbPBiXYhrD4HL6YvUM QgOKbGTXT/pgWnzb6E4emXQ+Z1xwAIFyEwrHwIxTUIF0E1qBDYch1je5tTTAw1LWaqkh R0/A== X-Forwarded-Encrypted: i=1; AJvYcCW9aHNjAco4FXXNKsYs4m1Ui66vxeWkaV7TlEgDioc/hP/qLCRnFjEFts52K7EdcLCA5y8X8ASpjCA7F0Y=@vger.kernel.org X-Gm-Message-State: AOJu0YzdqSi8AvqqjYZMAS8nrk9EE1+H0qX1qPp/Bgv7UnYHY1dsXQk0 5/fLO7QEBfVPvfa52gu89KJTYyCqFaijksAXUxbBRoAL2gdxK6kKDt1p X-Gm-Gg: ASbGncscjnEvCz3DbPlWTKa67QPyedeqMMw8Soaocbe44x0npDsJko6zRnAJJqnURiu BmXmETNnf2iuBg1bK7NtMOaSDkRk9GGCvJKCWXnx9MZCAFIwufklYnR/8PtpfQwwQdl8cNhlK1T dDMbQBPpqfXw6lcZHBidl21xeeXqJJPptJ1nTweZC+/qztjFVHOlP6RtDleYRE8kL1uFGQ5aY/i RMHCta7bYBTdlKZkP2DasvMwYvys90dTjptN8jQ5f7KOgavXOE7QzVJmhm5lgujiXOnbmlGIQz6 w3vxILAW7LH755fByHG7NADfDdxtc9kXw/LpT1YumZLfttmkQpbvAHQ7anJSl8sZzVT9MScIRDw lt5uDFnQlFnmnHStE/hEu+OH3nLnfY2R215hemb/h0zX7HCWVqyMslHXSaeLXHCTwWEgTMp1lul 7mBttH1ikMNVq2DrblPy//fEoa3oE= X-Google-Smtp-Source: AGHT+IHNagrkdB1dXKmAfAxFX7NHUjkLDIJK+H77kgo1bz0xfXRjOReqMV8tPTqftsQHvcAYdui28g== X-Received: by 2002:a05:6a21:6d89:b0:366:14b2:30a with SMTP id adf61e73a8af0-3661801fc52mr7083372637.61.1765175052779; Sun, 07 Dec 2025 22:24:12 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-29dae49ca1esm112555855ad.2.2025.12.07.22.24.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 07 Dec 2025 22:24:11 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [PATCH bpf-next v9 04/10] libbpf: Optimize type lookup with binary search for sorted BTF Date: Mon, 8 Dec 2025 14:23:47 +0800 Message-Id: <20251208062353.1702672-5-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251208062353.1702672-1-dolinux.peng@gmail.com> References: <20251208062353.1702672-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: pengdonglin 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 types. For unsorted BTF, the implementation falls back to the original linear search. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin --- tools/lib/bpf/btf.c | 103 ++++++++++++++++++++++++++++++++++---------- 1 file changed, 80 insertions(+), 23 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 26ebc0234b9b..7f150c869bf6 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -92,6 +92,8 @@ struct btf { * - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; + /* the start IDs of named types in sorted BTF */ + int sorted_start_id; /* if not NULL, points to the base BTF on top of which the current * split BTF is based */ @@ -897,46 +899,98 @@ 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_by_name_bsearch(const struct btf *btf, const char *n= ame, + __s32 start_id, __s32 end_id) { - __u32 i, nr_types =3D btf__type_cnt(btf); - - if (!strcmp(type_name, "void")) - return 0; - - 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); - - if (name && !strcmp(type_name, name)) - return i; + const struct btf_type *t; + const char *tname; + __s32 l, r, m, lmost =3D -ENOENT; + int ret; + + 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); + ret =3D strcmp(tname, name); + if (ret < 0) { + l =3D m + 1; + } else { + if (ret =3D=3D 0) + lmost =3D m; + r =3D m - 1; + } } =20 - return libbpf_err(-ENOENT); + return lmost; } =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); + const struct btf_type *t; + const char *tname; + __s32 idx; + + if (start_id < btf->start_id) { + idx =3D btf_find_by_name_kind(btf->base_btf, start_id, + type_name, kind); + if (idx >=3D 0) + return idx; + start_id =3D btf->start_id; + } =20 - if (kind =3D=3D BTF_KIND_UNKN || !strcmp(type_name, "void")) + if (kind =3D=3D BTF_KIND_UNKN || strcmp(type_name, "void") =3D=3D 0) 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->sorted_start_id > 0) { + __s32 end_id =3D btf__type_cnt(btf) - 1; + + /* skip anonymous types */ + start_id =3D max(start_id, btf->sorted_start_id); + idx =3D btf_find_by_name_bsearch(btf, type_name, start_id, end_id); + if (unlikely(idx < 0)) + return libbpf_err(-ENOENT); + + if (unlikely(kind =3D=3D -1)) + return idx; + + t =3D btf_type_by_id(btf, idx); + if (likely(BTF_INFO_KIND(t->info) =3D=3D kind)) + return idx; + + for (idx++; 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) !=3D 0) + return libbpf_err(-ENOENT); + if (btf_kind(t) =3D=3D kind) + return idx; + } + } else { + __u32 i, total; =20 - 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; + 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) =3D=3D 0) + return i; + } } =20 return libbpf_err(-ENOENT); } =20 +/* 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); +} + __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_n= ame, __u32 kind) { @@ -1006,6 +1060,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->sorted_start_id =3D 0; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1057,6 +1112,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->sorted_start_id =3D 0; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1715,6 +1771,7 @@ static void btf_invalidate_raw_data(struct btf *btf) free(btf->raw_data_swapped); btf->raw_data_swapped =3D NULL; } + btf->sorted_start_id =3D 0; } =20 /* Ensure BTF is ready to be modified (by splitting into a three memory --=20 2.34.1 From nobody Tue Dec 16 13:22:08 2025 Received: from mail-pl1-f174.google.com (mail-pl1-f174.google.com [209.85.214.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 E85B0313534 for ; Mon, 8 Dec 2025 06:24:17 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175059; cv=none; b=sVqX9sZtA3YI5315UgdNenTuPgy7F1tfe60bI7WNw67F1yGgN3OzpLHgVBcgTy4UMdGtCJb0t5Cp3WwzxPoVzGtp03lOAS0VGKQjxyEEYvH8IS1G7J+lS9V3ujrwa6Z0skPrhdxEpwPH9oRAq8VXpyDOOt2LDhk1A60qRIqtvEg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175059; c=relaxed/simple; bh=8hsjVTc4iHNm8LdtJrSwh8RnQyLo12TybfR54C1ppls=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=BXKoi+iRXNPF93W7En3H9nOpbPVcloy+NkufbK3N5qbmVpwgD6Xf1u5E0oLQctY7CZqsV+lqsY3uKdcqERQw9XPHCmKbNzZITjSzbwXUkO/vXZMIvtzEVIeBGYd1jgO+Lhatbbxyd72avfP1e6iOXJnzI+k83y6bJ20QeOoiow0= 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=YYUWxGDO; arc=none smtp.client-ip=209.85.214.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="YYUWxGDO" Received: by mail-pl1-f174.google.com with SMTP id d9443c01a7336-297e239baecso37713385ad.1 for ; Sun, 07 Dec 2025 22:24:17 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765175057; x=1765779857; 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=xAB27SW8ze5pe2PA9+A7ZhKextxDBm6v0Soq1ZoL2Ng=; b=YYUWxGDO1vJ0tq4hnYCw3RgR0onyHkO/7yCOOwiusJrR0XTPvcVksqdiY6tD8WHzCe zVe1WAXdN+CjuWVTrkvdYoWCj1bCrzoSCe26kLxUAAzoABvZp2cdzlA9zpFKsnbbgDlU 1YkBwHLhAOcfIyjA2aDpiWlWU2Vs4vUMzfpl5wXuuovqiKwzhqU6biWVU3AYItsb2v3O NqOmGUr8u7Jwbd7t+rX0V7gKCibdcd6B59ArUoT5jOVFE+u6Izrmf5/rQ1MCouQ9q/sk S+LGsEDayugxdbrrf93+oVIXLoatd8da4zDHeaSEvGzm/f1QlEvnqp5dopACwoo8ol27 RmdQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765175057; x=1765779857; 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=xAB27SW8ze5pe2PA9+A7ZhKextxDBm6v0Soq1ZoL2Ng=; b=OY/YUAxf2AKTOyy3JRBTW7vpKKQmxdlnbEchwk9Up2FyrNuo4cR/HAe65+a6/4fKqt 4X5p6YjGGs+KCQUT3uvqa4mt/L9MgOVh/kyL7tmWd9o8sbWaZ923coIU7ZLfe4aYhytS /Z/fJHk7pBW/mYiNzfqYl7a2c1foedG9LeWBm9R8RLRFXardiLEprYPZvp0FDbRLspAN q6cB5OF4Xb+r/WIQWgvGl0Rns1M61Pw0x4DlKi05VUFmFo3PIE3wTU9pyUDs3bD+HXHi Nshk389rtBOVXhcqpRSqRacecNs6lb3t1JEZo4AFcg2X99hXVxmf+eI2I67cwhp8r5cO AA4w== X-Forwarded-Encrypted: i=1; AJvYcCUp00Q6vr8IrYTHLfrdvbr9oNnuUT9qy0oulMxKroe3kkIUu9zxYmcQZM7JI7WnDR5pQPLk3ABBxhFnZWk=@vger.kernel.org X-Gm-Message-State: AOJu0YxJ0vKY4RbxwhA6X52771SP1UM2WD8ykwBhHVFu3JTeDYNYamCC XFGupLxJ3qtcJ84NErjsPKu5PzmeLFA0NiPL7YbSAk8ApR2DNtyDmDSw X-Gm-Gg: ASbGncv9ZI96VqqnCrE8h7FWBuAUC4NZsQ3M6pwb7qI8P+QvgL/AXV+mTPcY/QnIkV5 zUAuLzwcES7l809dMrhJjhZkfHNLdpS/Ub4G81ATNxRX4OunbClKyPhyGWzTBvmXxfw1+0zmGG2 /0EdeZrBhhM6MjaS3tj547a7AurfiyGB03i8HHrqD5dlwrWJ0wrJC6bP9YGImlJvKDDn3aC9Ho8 h4+SYgBez9J+YH3vdosgJd1ffPGPu0nPk0+loSpXPuKMMf7tr/cabvN4amDpQAH2UKRvG6KJeA/ 8wvVOGw3Kq9job7mowWASAfogeJEw1W170qXQ738OoXZb2Sbu0PbLediDKp5PRXAW4nStWUE1x/ 25Z/NPFEzUCYsYdNSZ4Mt7ALyZ7HhffffaymCo0hpmJUfNJj2Tvlzy1ERwO/h0yuEguOErCqvAq iQ2PNV3YaH+oT7yRrOujFGadUMtXg= X-Google-Smtp-Source: AGHT+IE+5YDDDuQsk4AB/Xv49ebPh4yjqmdlSSxW7j/cMhZAbaKPySX/s4q4XWI8x+qvn7t4NxuZzg== X-Received: by 2002:a17:902:fc46:b0:297:eafd:5c19 with SMTP id d9443c01a7336-29d9ec50fbfmr143611025ad.10.1765175057265; Sun, 07 Dec 2025 22:24:17 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-29dae49ca1esm112555855ad.2.2025.12.07.22.24.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 07 Dec 2025 22:24:15 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [PATCH bpf-next v9 05/10] libbpf: Verify BTF Sorting Date: Mon, 8 Dec 2025 14:23:48 +0800 Message-Id: <20251208062353.1702672-6-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251208062353.1702672-1-dolinux.peng@gmail.com> References: <20251208062353.1702672-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: pengdonglin This patch checks whether the BTF is sorted by name in ascending order. If sorted, binary search will be used when looking up types. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin --- tools/lib/bpf/btf.c | 46 ++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 45 insertions(+), 1 deletion(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 7f150c869bf6..a53d24704857 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -899,6 +899,49 @@ int btf__resolve_type(const struct btf *btf, __u32 typ= e_id) return type_id; } =20 +/* + * Assuming that types are sorted by name in ascending order. + */ +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; + + 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 void btf_check_sorted(struct btf *btf) +{ + const struct btf_type *t; + int i, k =3D 0, n; + __u32 sorted_start_id =3D 0; + + if (btf->nr_types < 2) + return; + + 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 (sorted_start_id =3D=3D 0 && + !str_is_empty(btf__str_by_offset(btf, t->name_off))) + sorted_start_id =3D i; + } + + t =3D btf_type_by_id(btf, k); + if (sorted_start_id =3D=3D 0 && + !str_is_empty(btf__str_by_offset(btf, t->name_off))) + sorted_start_id =3D k; + if (sorted_start_id) + btf->sorted_start_id =3D sorted_start_id; +} + static __s32 btf_find_by_name_bsearch(const struct btf *btf, const char *n= ame, __s32 start_id, __s32 end_id) { @@ -935,7 +978,7 @@ static __s32 btf_find_by_name_kind(const struct btf *bt= f, int start_id, =20 if (start_id < btf->start_id) { idx =3D btf_find_by_name_kind(btf->base_btf, start_id, - type_name, kind); + type_name, kind); if (idx >=3D 0) return idx; start_id =3D btf->start_id; @@ -1147,6 +1190,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) { --=20 2.34.1 From nobody Tue Dec 16 13:22:08 2025 Received: from mail-pl1-f178.google.com (mail-pl1-f178.google.com [209.85.214.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 60678313E0A for ; Mon, 8 Dec 2025 06:24:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175062; cv=none; b=Y23nHJkeBYQom9wDOrM1ZR2AHeRIN4hcxsS/7LCzt8jhelIq0W/bWTim6w6MD2d+nIFYxotaUDAZU9FBDRArzmCJg70cNujhzgSC4b76WccSUMiizlX+FEDJDYc7kCkUZtEWavhk5jDGrpzdSULfQoRr0VshJ7fxjIPDesa3fWY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175062; c=relaxed/simple; bh=0kgEQtgvPa55pKXFrtj7srWoStjEyAoMQzDyIdaQ2pI=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=D9TYIpp6h69A0915431bxABqXSLrTSzFlBq2hsmuSfJ2/meiGk1dNGCQaaqsaO1rsX1QgOCc+njmMbPr3FG9/EjsZhcn58qEB5O2GyP50669kv11k+EPLQWKxQcUoLiSl2QODdQllvVEhNN7gJ+3NvDPJyCJKoz/Du/jo8TJZMw= 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=CQJ60Lnb; arc=none smtp.client-ip=209.85.214.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="CQJ60Lnb" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-29586626fbeso48508185ad.0 for ; Sun, 07 Dec 2025 22:24:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765175061; x=1765779861; 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=mgDV1ROzgzpe5gCmmSbOnsLIyQpLC/h36ENHoKlfvVE=; b=CQJ60LnbKPu9bRhsOvempKpwtVkZuuwxSdJQeZcoeapgmDUrB+H9Ugn2zk+6/xAbml MwQnI5IAp4YWNygmpHEfPopeknHGIYfWxPu9xvc86A+eQ3dA/AW3knfsBCdH/uiYC54K 3kURlKtZr6x2e2xztLNYFOjhk9QjYJLvh9bM3DCjy/g8rt8Xy+HrokXE4zVyECFlbkPs +s45EhBWEa+XZUolagBl1EnImbKYdWyGwTnRs5XkFdRIWMDOa+8T94ckHONyqjW/2HIk O3OUzCOuDJJM5Pvwhof5vgdNJeoOI/USh0ZxFtVoJw9vWlvUKbYuwcPohbDfn6ziU+7e ZCNw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765175061; x=1765779861; 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=mgDV1ROzgzpe5gCmmSbOnsLIyQpLC/h36ENHoKlfvVE=; b=rm7yvfKtFSTMgwFqdNoWi1cXd78vNQKba4Cick9Y+NX/pTm62b0rOWWEUsgLlI9Xjz dD2W0HywhPuOYItSa9HClo8/5qgk8dLYqiwyeqEZa2kIdJLV2paAaWlzIppAqhpoYS/F NFD/pzTBLc6kVfbTOxlkCf8WDG0igU1d7E7DQK2rS4t7Ji0cq1ril/S3HIn0S5GWsKvy wKsAGzWK8+mQ2AnT5IRN1mm7nWsTLTjYe3/lUrJGXS/cKwMvhbcBOeQl2GpqQ/VpoBFN jQ7cEzVCDeZ5d4b9J0q5bAu0L+BsqU4pwjONCiZvvvydWSp2C4ybDkW9xZ7kAgNIDNcC x2Kg== X-Forwarded-Encrypted: i=1; AJvYcCW0ROGEb+6fqugDLddkhA/kXOKs3eDvNqA2X6F/GW+FtFXrR57wnn0FsB4dNdp4pKLz88sID2juqlLzFco=@vger.kernel.org X-Gm-Message-State: AOJu0YyPR0gFpZqQQ4bywgj8groYkHisHGoEYrURtQFZWpQlmv2stDP7 L3RIy19/gJ9De1xbk3tIYOirecr1IVhzMQy9hCxreGsRHyGoBinmGEOE X-Gm-Gg: ASbGnctAXHF+ohD7FmvdDc/XX+41CXbxpHwjt3J2xI9IECKyEc2VLlYsycEoaf58Z2/ aVsl9IBGcaQM4Ya1N3WWN7Sd2qyb43NiTVvjiKnP4FSi8gDx6yC9BP1kwa9E57RB2guZUP8dsO9 Yizgnwffe3HTkhczU2d9KJTmuLguR02zLjOMkoCmJDBtWfHLCIskCFNT33qTUePZaznT6Q2MXvs Ca1t/sPGGGkvtOVsCOpTDVBWif+Z+rKGQIZ2WqZnZwKkut8ZmtHLXO3K0kiC4A03TGvCoQjt0Zk g0dqSCzoEqwBZhfR5p/hsiQxWDH6WfjWVS3Xvt6TXCDT+vnY6N7i9ppQpf3lnCEpqN3RsZcdtKs q+M3XKv9dIAMCtSnaJx/ZrMQKlYr+HWSgWjrjEAy6iJJejX+BCicxdDAmn6xD5O5CrLJt29wW6K lPZQ22QUh45VXWjC1WUABgaGQvu3ie9U66t/cOig== X-Google-Smtp-Source: AGHT+IG6L+lPfbNCKWoFS4rN4KY/rh99CfbKovxPed4KtXlkFy6JUwLMvGN1EclnhEJL5Apqnbgs1g== X-Received: by 2002:a17:903:1b6c:b0:295:6a9:cb62 with SMTP id d9443c01a7336-29df5e1c234mr68591085ad.35.1765175060725; Sun, 07 Dec 2025 22:24:20 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-29dae49ca1esm112555855ad.2.2025.12.07.22.24.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 07 Dec 2025 22:24:19 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [PATCH bpf-next v9 06/10] btf: Optimize type lookup with binary search Date: Mon, 8 Dec 2025 14:23:49 +0800 Message-Id: <20251208062353.1702672-7-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251208062353.1702672-1-dolinux.peng@gmail.com> References: <20251208062353.1702672-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: pengdonglin 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: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin --- kernel/bpf/btf.c | 85 +++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 76 insertions(+), 9 deletions(-) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 0de8fc8a0e0b..842f9c0200e4 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 sorted_start_id; 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,21 +550,79 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *nam= e, + s32 start_id, s32 end_id) +{ + const struct btf_type *t; + const char *tname; + s32 l, r, m, lmost =3D -ENOENT; + int ret; + + 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); + ret =3D strcmp(tname, name); + if (ret < 0) { + l =3D m + 1; + } else { + if (ret =3D=3D 0) + lmost =3D m; + r =3D m - 1; + } + } + + return lmost; +} + 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; + s32 idx; =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) { + idx =3D btf_find_by_name_kind(base_btf, name, kind); + if (idx > 0) + return idx; + } =20 - tname =3D btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; + if (btf->sorted_start_id > 0) { + /* skip anonymous types */ + s32 start_id =3D btf->sorted_start_id; + s32 end_id =3D btf_nr_types(btf) - 1; + + idx =3D btf_find_by_name_bsearch(btf, name, start_id, end_id); + if (idx < 0) + return -ENOENT; + + t =3D btf_type_by_id(btf, idx); + if (BTF_INFO_KIND(t->info) =3D=3D kind) + return idx; + + for (idx++; 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) !=3D 0) + return -ENOENT; + if (BTF_INFO_KIND(t->info) =3D=3D kind) + return idx; + } + } else { + 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) =3D=3D 0) + return i; + } } =20 return -ENOENT; @@ -5791,6 +5855,7 @@ static struct btf *btf_parse(const union bpf_attr *at= tr, bpfptr_t uattr, u32 uat goto errout; } env->btf =3D btf; + btf->sorted_start_id =3D 0; =20 data =3D kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN); if (!data) { @@ -6210,6 +6275,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->sorted_start_id =3D 0; snprintf(btf->name, sizeof(btf->name), "%s", name); =20 err =3D btf_parse_hdr(env); @@ -6327,6 +6393,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->sorted_start_id =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 16 13:22:08 2025 Received: from mail-pl1-f176.google.com (mail-pl1-f176.google.com [209.85.214.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 F0DF8313E2E for ; Mon, 8 Dec 2025 06:24:24 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175066; cv=none; b=fcP1PwbMrcgeA1bAGwiP5Xe+sIkvxM/jQ5SWkdLuTdlnMVLq5Q9efiFaVTXmaktfRkAlVjh7wWJf9vPFPd2Mb+bLLEzsanXSqJAYNzdLAgEek3jOxKeIrDH4OkeaQQn+8EvHPusTl7+2p4a1Wf8opuacvz8ujZZCYBm5wCW96mU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175066; c=relaxed/simple; bh=SkiiMl3aCQEr+d5U8ft32wOaTMUA9E4gZBiYCpbgSZ8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=PUhk3V1BRCYzRyEVrDH0RT1pEoExbWSBzrxBXdjYmO4PtqCwwKtEhFJd3pcOCA8sqstnj0DmVKJr/ciQJrO+avKlo1JquTnqap671iPsG67PYgyD0+izVosG7p6rHwmKMo/vYHhK839xPnGA22G7cgiX8lxtmy4Z3hDWRx0pizE= 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=h/CtXLsL; arc=none smtp.client-ip=209.85.214.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="h/CtXLsL" Received: by mail-pl1-f176.google.com with SMTP id d9443c01a7336-297d4a56f97so53235345ad.1 for ; Sun, 07 Dec 2025 22:24:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765175064; x=1765779864; 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=7QTcvpacDQDrdV3P23xBsLkdItSxCnXjFnIjmUhrbpI=; b=h/CtXLsL+tWIp47DX3VHrKi3BH9HPSPsQtJRjIgvUDH2yGIQ9nfeSlma9K5WDU4rye PUu21qHX2q4hMWNHkpQFSqhY5v0xc93eJzA8xVnS1CGDKF89ZDFnMIFqoxu3C82TmO6e z2j4IxQG5C40kdsq3jrYI1z8+goxxRSeML0MQQDaed4aPbUbkKvuEptZcDFDPhps4XCr AGEej6AkgY1ZvPJDO9ZV7ZXTpMLP3b6jDmk8SzqEobC+lFLL3soRJHzXJZTPhoyOENq9 wKOpJ+qyUVLb1CBOs3J3YQ5WBnRRG6P/PB8OwcgjV0zn4WzuSBOOYu40QwXb0KKj2jGx wtQQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765175064; x=1765779864; 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=7QTcvpacDQDrdV3P23xBsLkdItSxCnXjFnIjmUhrbpI=; b=MPZN63pdMd6gX8HNHDhalRYE3hPKbxqrauViSq1BfPQd+4dkwFbhYc4vRY63W2Umsj zWEhJxOqahgGe8VMCoqiX745Tx9NnY66mEvK2L4lNFZrH1zGt+0NRZM7jbZBcNTQm64G IWemKdJAkfT6FAmIZXhQLcq+LxMEDLnOsQfY8Pv7iPya+0M6RYQj17V4vmfFfWJIZZZZ sZSpOqZKcknVjgmuY/cEeslpJV1yVGFbnXgMHYHl0ixfri9tYWdhnZA8l2fq+NxmP++f bF74qX1gyUzn8SVDqoalQime7yixSygF94nIMgU3MU+i6Fx1NC8+7wWa1nm7rY2yOZK3 v9wg== X-Forwarded-Encrypted: i=1; AJvYcCULvSd8AvRtjR0NXhzjh0O1AVcYfQqprDu7SWuyzbra14nwaAURdd+MZL8d29cvHZdeVCROpKEbJyeOX0o=@vger.kernel.org X-Gm-Message-State: AOJu0Yzoh7B7p704oDqiZBp3DuBWpPBJ72jGAXQQiO3sWW0u+4a9cD2l zat9ABs3HlWgcMqEtgQaDCYz9U40z+xe80eCpDXizTB1zzSye7jbK3lZ X-Gm-Gg: ASbGncunNI8A2YjdXpbc6v8N9AIH9udOzZpFSn+k01Cp/PU6u/YGA9LyX5CJrK6Yx0C UpQrdPag+BRpaKexhtIyyT8qtrdTq4mClD3DbNldoCVykl7np5g/u2mElm5nkm78LBdHCsne9t6 j+3bBwDo1xIejrezaLAbQq9NqOx68tIb+yvxGkyy1jn+IwBPCap8JrDFSoaSj2cMUc6MxcCffDt 7XNE8sC5GsOaTcUoE2oIopaV1hvxBiNqaDPMdejutw+xwaKgUa9dYqpHc9R5L+o2QwKscGbuPRe 475p+ngct+v5k5WaZ80eKR6+QU5lp3on9sA7LbkD6Uob26Csp68bb281LOTU5vm2PR0pOt57pl1 h0yM0EhrltWCP9nwGYQO0IM7O2tBnDlHPvrNzV5E1mjs48pQJRoYBcpQ5SfMhtejiKCGNnx7rh0 I0CCHeUhgDAs849v6G/hgPT+lC7B8= X-Google-Smtp-Source: AGHT+IGy9ZHkYoDCeMBMkITpN3+AePbwh+IYnfo+UR/72sgLY/5EfSwCwoF5HbXDJD2v4dWdOPEYQA== X-Received: by 2002:a17:902:cf0f:b0:295:1277:7920 with SMTP id d9443c01a7336-29df5dc065dmr62398555ad.28.1765175064159; Sun, 07 Dec 2025 22:24:24 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-29dae49ca1esm112555855ad.2.2025.12.07.22.24.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 07 Dec 2025 22:24:23 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [PATCH bpf-next v9 07/10] btf: Verify BTF Sorting Date: Mon, 8 Dec 2025 14:23:50 +0800 Message-Id: <20251208062353.1702672-8-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251208062353.1702672-1-dolinux.peng@gmail.com> References: <20251208062353.1702672-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: pengdonglin This patch checks whether the BTF is sorted by name in ascending order. If sorted, binary search will be used when looking up types. Specifically, vmlinux and kernel module BTFs are always sorted during the build phase with anonymous types placed before named types, so we only need to identify the starting ID of named types. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin --- kernel/bpf/btf.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 58 insertions(+) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 842f9c0200e4..925cb524f3a8 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -550,6 +550,60 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +/* + * Assuming that types are sorted by name in ascending order. + */ +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; + + na =3D btf_name_by_offset(btf, ta->name_off); + nb =3D btf_name_by_offset(btf, tb->name_off); + return strcmp(na, nb); +} + +/* Note that vmlinux and kernel module BTFs are always sorted + * during the building phase. + */ +static void btf_check_sorted(struct btf *btf) +{ + const struct btf_type *t; + bool skip_cmp =3D btf_is_kernel(btf); + u32 sorted_start_id =3D 0; + int i, n, k =3D 0; + + if (btf->nr_types < 2) + return; + + 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; + + if (sorted_start_id =3D=3D 0) { + t =3D btf_type_by_id(btf, i); + if (t->name_off) { + sorted_start_id =3D i; + if (skip_cmp) + break; + } + } + } + + if (sorted_start_id =3D=3D 0) { + t =3D btf_type_by_id(btf, k); + if (t->name_off) + sorted_start_id =3D k; + } + if (sorted_start_id) + btf->sorted_start_id =3D sorted_start_id; +} + static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *nam= e, s32 start_id, s32 end_id) { @@ -5889,6 +5943,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); @@ -6296,6 +6352,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; @@ -6430,6 +6487,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 From nobody Tue Dec 16 13:22:08 2025 Received: from mail-pl1-f181.google.com (mail-pl1-f181.google.com [209.85.214.181]) (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 535BA313E3A for ; Mon, 8 Dec 2025 06:24:28 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175069; cv=none; b=sk2bME5gqsDD0AhtI9WGM25iM4C5ebe50dIlRxZERpQicONrx6lteMqyhHqicczeR29iWz1Aa73criPyekuW9m8iar/fD1O76G7czM0Ps9AUWJ/R0eFBaeb/XHf5ySdVDRcv0eGEDJt4W3bOkSxnpD5aRMMktMHVXj5Vpe1MJQ0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175069; c=relaxed/simple; bh=i7QanyYSi/r+PgBdCryQh6I5m7xPTm9Iqix4Q3VKzZ4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=qb/rUdz95Qhz1FSZpSn40sr+04x1CikmTTcUhEaXO+sIffVljyljXWyPYINVWzDv1oKkMAB6BbJufRy+M4O2B6vywSQIjBgSlEDpZo+TMswZjG4DA3ZeChbJ6WcNBp4+cNE0pq6dxRfeVKeP0ALrukIeXZ7nKHnGpuiym6JhsIM= 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=TnMuIIdP; arc=none smtp.client-ip=209.85.214.181 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="TnMuIIdP" Received: by mail-pl1-f181.google.com with SMTP id d9443c01a7336-29812589890so57424075ad.3 for ; Sun, 07 Dec 2025 22:24:28 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765175068; x=1765779868; 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=s9Fz+H+Y9xd77iPc8boezvXQ6uLdCfh3xlXlYrH3URU=; b=TnMuIIdPju7kQMGEpbUgDAf/1Z0KOEki1Oxanpm//yDE4+UylorsFk53GZJXotAJ3T GKAufyO04eAOeuBHBFOO1LlmOu5Y92sSU/AZI/gMlYAMb0XyUwFx15wtSc9SpQgSsGnM HLyalj3qmcsWUPYFNhZ6aiWZcG+Q4jyo3i8YinJYlPJZcQs4or2JVg9TdrvO1P4zoRVf VAOvpHrvNtfLdQW/+57+DPbzrNr3jGv4FXB7Da/DmWAlKCc8kB/3FjHa/rCQXZpkr8II 3rPj/uuoLF/RVQj53zwZf4byQ7bOrif+hIv1wopg11bTkkFjlGLvDA1GcKADz1tlMAoE PzJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765175068; x=1765779868; 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=s9Fz+H+Y9xd77iPc8boezvXQ6uLdCfh3xlXlYrH3URU=; b=kUWLttxuNRISkZGm70XIkB9+AqSiugQLsq3Nx8InMiJxhgSSsLmCJmC1gvnl3CApiG 4sCM8lLzafPqRQ3Qh0kBAznSi/O3ifcotX+dIasi5bMcvhhZFgiceJXWGi5EhvYw4OUT 0M64EjAgzHvnjxFSJ3ykMhty3myMnS279M86dU5VKOqdM6rmudRVUoYnfqJKbcZuaFiI //THpT1CwKvFoogqfkPFjgr9h0Wsqd/X7M4aoiK30GgAooncD7sFWdSz0roara78Wuss hj7r+guAowCA3a5L/VTiTDldHDvblH897Sm3loK27gC+LVzTJANX6fqdCs7BXc+WoCJR SQJQ== X-Forwarded-Encrypted: i=1; AJvYcCWx7hIsRavX3JXiqlTEM25pJvl4bZ+iWvW+LEuh2BsO0pGRm+n23D8Cxg/XcMprQZH8Eg1zJ3QJ9rSOnkw=@vger.kernel.org X-Gm-Message-State: AOJu0YzOg/RQHnpD/e8udR0EjdAmNT2o3tmlV13IB90mPbSdx26uVR54 bYBWyWN5l6VPQ0e4c08oIx0jLN8jB3XRIqB8i8Xq3gjEOLdmgMe+Y8TF X-Gm-Gg: ASbGncvROhoiop+vC7MLpXrg4zk4ciTp91LiVL2GZanocQ+F08oh8MLMxVZ7+7OnzYz gllYPJ+N5lBYU8OS8xrDvc8AzFeuvNTCdSBLno8mtNjOYxUk01kW8o4CRP0hc6i365apqoehdzx Wrve1WVPPaC8aoYzHseqa1lZujQDwHfBO+xsoiDxjDagYfbH2L13h9/Lg4F2fCP8P/7iol8vCsa Uu/nb9TjUYa7q7hNGk4TayKj0RdhfnVYSsxY8O9AeQgLrVrJQq+B75ZKqV/U12LJoJRDqUj5ooO HItl4c2EelpePFJK/w6c916EC/UtS9pmov05cHZ30y+rlgAY/LdvGITwjckzctr0mV2xGPsuhBr lkKjUX5/gJLOPrUz9TD79giqKt8Wzo0+mS5/YiggBiqHxgvDCKRaK5Q2RjffLYgoL31uV13n/Co kGJ1vQAOl2pILvkxu0vQLwAHsLRWE= X-Google-Smtp-Source: AGHT+IEcsc2LtgH3QM15NWRvotNsGzkF1f7ECf0FET9aNq28ZN1vpLBBARPtfOIx4sM9uf1KOSiEow== X-Received: by 2002:a17:903:41c7:b0:298:ea9:5732 with SMTP id d9443c01a7336-29df5db8441mr55529665ad.41.1765175067626; Sun, 07 Dec 2025 22:24:27 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-29dae49ca1esm112555855ad.2.2025.12.07.22.24.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 07 Dec 2025 22:24:26 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [PATCH bpf-next v9 08/10] bpf: Skip anonymous types in type lookup for performance Date: Mon, 8 Dec 2025 14:23:51 +0800 Message-Id: <20251208062353.1702672-9-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251208062353.1702672-1-dolinux.peng@gmail.com> References: <20251208062353.1702672-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: pengdonglin Currently, vmlinux and kernel module BTFs are unconditionally sorted during the build phase, with named types placed at the end. Thus, anonymous types should be skipped when starting the search. In my vmlinux BTF, the number of anonymous types is 61,747, which means the loop count can be reduced by 61,747. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin --- include/linux/btf.h | 1 + kernel/bpf/btf.c | 15 ++++++++++----- kernel/bpf/verifier.c | 7 +------ 3 files changed, 12 insertions(+), 11 deletions(-) diff --git a/include/linux/btf.h b/include/linux/btf.h index f06976ffb63f..2d28f2b22ae5 100644 --- a/include/linux/btf.h +++ b/include/linux/btf.h @@ -220,6 +220,7 @@ bool btf_is_module(const struct btf *btf); bool btf_is_vmlinux(const struct btf *btf); struct module *btf_try_get_module(const struct btf *btf); u32 btf_nr_types(const struct btf *btf); +u32 btf_sorted_start_id(const struct btf *btf); struct btf *btf_base_btf(const struct btf *btf); bool btf_type_is_i32(const struct btf_type *t); bool btf_type_is_i64(const struct btf_type *t); diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 925cb524f3a8..5f4f51b0acf4 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -550,6 +550,11 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +u32 btf_sorted_start_id(const struct btf *btf) +{ + return btf->sorted_start_id ?: (btf->start_id ?: 1); +} + /* * Assuming that types are sorted by name in ascending order. */ @@ -3540,9 +3545,9 @@ const char *btf_find_decl_tag_value(const struct btf = *btf, const struct btf_type { const char *value =3D NULL; const struct btf_type *t; - int len, id; + int len, id =3D btf->sorted_start_id > 0 ? btf->sorted_start_id - 1 : 0; =20 - id =3D btf_find_next_decl_tag(btf, pt, comp_idx, tag_key, 0); + id =3D btf_find_next_decl_tag(btf, pt, comp_idx, tag_key, id); if (id < 0) return ERR_PTR(id); =20 @@ -7859,7 +7864,7 @@ int btf_prepare_func_args(struct bpf_verifier_env *en= v, int subprog) */ for (i =3D 0; i < nargs; i++) { u32 tags =3D 0; - int id =3D 0; + int id =3D btf->sorted_start_id > 0 ? btf->sorted_start_id - 1 : 0; =20 /* 'arg:' decl_tag takes precedence over derivation of * register type from BTF type itself @@ -9340,7 +9345,7 @@ bpf_core_find_cands(struct bpf_core_ctx *ctx, u32 loc= al_type_id) } =20 /* Attempt to find target candidates in vmlinux BTF first */ - cands =3D bpf_core_add_cands(cands, main_btf, 1); + cands =3D bpf_core_add_cands(cands, main_btf, main_btf->sorted_start_id); if (IS_ERR(cands)) return ERR_CAST(cands); =20 @@ -9372,7 +9377,7 @@ bpf_core_find_cands(struct bpf_core_ctx *ctx, u32 loc= al_type_id) */ btf_get(mod_btf); spin_unlock_bh(&btf_idr_lock); - cands =3D bpf_core_add_cands(cands, mod_btf, btf_nr_types(main_btf)); + cands =3D bpf_core_add_cands(cands, mod_btf, mod_btf->sorted_start_id); btf_put(mod_btf); if (IS_ERR(cands)) return ERR_CAST(cands); diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index f0ca69f888fa..2ae87075db6a 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -20655,12 +20655,7 @@ static int find_btf_percpu_datasec(struct btf *btf) * types to look at only module's own BTF types. */ n =3D btf_nr_types(btf); - if (btf_is_module(btf)) - i =3D btf_nr_types(btf_vmlinux); - else - i =3D 1; - - for(; i < n; i++) { + for (i =3D btf_sorted_start_id(btf); i < n; i++) { t =3D btf_type_by_id(btf, i); if (BTF_INFO_KIND(t->info) !=3D BTF_KIND_DATASEC) continue; --=20 2.34.1 From nobody Tue Dec 16 13:22:08 2025 Received: from mail-pl1-f180.google.com (mail-pl1-f180.google.com [209.85.214.180]) (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 ABF3A2D781B for ; Mon, 8 Dec 2025 06:24:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175073; cv=none; b=kpGv8/zzU30gQDUAg2AZVJNej82D9C2O+NQXDWi9erh5zzGBng+C3vvXqQp7BKqI50+8RvsWbSTa7pj9/CNgh2Uup8FWWJm/n1Nb8NjSecKtnm8JYTNgA3bNuqH0p50QtKW9qwfpljp3WhkjmFfTRHeeBzLaZK/0hW36oQeCpwg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175073; c=relaxed/simple; bh=n+zH9plFFMUYGIEcY3wzYO3Lyz+b74AkBCCdAEyYNdU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=rO37sezWgquHQ2JPKNGIKl1cbTmh5JeaUO5RYwlJaYjP4zWq/2oZSXzxELc0kp10Wivwcmi+AB6HQ6Zs0qHNk3+1uC30pZmOT8TUAvqTkht6qOPP9UJwEMYTmNwk5Ykpn2w+mIN7jOZavHFpRwjeoUdWvmTtE0iFqm4yNwS+jh8= 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=FRq2ZUIy; arc=none smtp.client-ip=209.85.214.180 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="FRq2ZUIy" Received: by mail-pl1-f180.google.com with SMTP id d9443c01a7336-29d7b019e0eso45920355ad.2 for ; Sun, 07 Dec 2025 22:24:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765175071; x=1765779871; 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=FhW1CqQDAMm+jon2EpWEcUDvYwGJtYovETBfwMR4CKg=; b=FRq2ZUIytvXvDl26mA7isN6ZU5/nswqMrx0c+aN/gElKSswZop6qpecrd32cwrL+Rr s5vcItJdZpbNzPPujX2nV6pbhRKNO0Sap+s+DfeUjb0PBEYLUlEzFhJfyhu4/dEgNGQU L6JHt2TA7rMjdHgw2aMCPDcCVrXEE7llRwMjXu11NeZeR/Fb7HUok4P/KvOFhLlirruC H3hor+9zJF8Oxi5NyVucW220Y4CN3+DxTYenBOdttrKCFCMYU03MmwXXbXfauIsPW8JS pzruoIMdN2pzCmnwnsj14OtDAMN9eFoqVTS7IRCbK1yEiSiplI8vcGGzKBPQjGxVphp6 88yQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765175071; x=1765779871; 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=FhW1CqQDAMm+jon2EpWEcUDvYwGJtYovETBfwMR4CKg=; b=Qko+TlJ0UdFozWdGOUP+dXcfJROvYoVakCaCYl0kDxXtkQUsErJe/ajc/jl7hKjsLh OX/3jEOK/y43pUKTxLk7VNZuF86rg2Q6yIYeVXs6GuhFpznBzlOpEb1pAaPqXVZzqaxf 2GBd0IRs2Ca8YPj35kuywY1GG0/sy7NsjdU6PScSitWpa+yoXZCuO/z7FU3YKGsVIGs+ Ay3cJ6Hj7NH28kWjAnOPbye8csrdMya+no4k4Ymzwhvbwc9A79desMCj3kUc6fN32vS8 r4WJyKs9TvuJUbghIv8qzHVSCV22T1H9HQVK7jqjqmYFzTrGqEkHe2vo5eag6o6GToli fMYg== X-Forwarded-Encrypted: i=1; AJvYcCUqv74H4DW3D656iYUQFsGk4cwFJzbaw6i42+o+1+Fx5jeIUkPPk9IMTEJ4aX4idV7eCBQI4MfwIyqnsVY=@vger.kernel.org X-Gm-Message-State: AOJu0YxHYIA2oDvU1AJfgiRD8uN3BEqxgq9YPWxlbS0KDgfJ6UR2Cemy csSdkILhxcT5LQ1sQrszoAFsY5/GTmnl8RGZX2D27SOqJD6YE8YSoklf X-Gm-Gg: ASbGnctiRwxc8zgifzNXIoV7+btBuYvlUn9HL/jMi+dWAJAuq4sJ9goAO8ZNRd4u9YZ gXVtEhoBnYyWbzpnyuAZQaN2xkh2cocSwD3oTq6voIPVpSl9uhA0oUeq32k/YOpGuhCl7xWPkpG YUhLwxRx01/1MJPPEio5jmFw5veKzGUbshSJD0imv5QJTCEJ//iZho0taAQF1wsk+gdCvQ1CJbH eHhimFydXF4xc/7WZ8dZ+wXRCyONkYG+xY/zq4ajqtMJtXGdsxkwobEIAzY5ooad1dP2xHNB8Uy XGUC1YBAHwKI2oItjCYVrvcZZ9EHL+yZN6Uj4x85RJe5+niAS0aj8GqzEVtfcEMvuDJ1dl8CpjT ayjegmH5qe4mrt9Apd0mM+s7Ep1ttfqlmkUaNfQrC3z171NpOpax8sb34vy/HEzskzQoVyrcdaH GP7WLUmAzV8I9FNaxf3AufiucLL6jTiuqRjqP4PQ== X-Google-Smtp-Source: AGHT+IFsht3tx4iyxceDrOoGzxGYBI5zLO8cdj3CemmPxNI1cuQpObayIm/IsNw4CmeT4+GU/dZGgA== X-Received: by 2002:a17:902:da8a:b0:295:2cb6:f4a8 with SMTP id d9443c01a7336-29df5e0f345mr46986745ad.51.1765175070919; Sun, 07 Dec 2025 22:24:30 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-29dae49ca1esm112555855ad.2.2025.12.07.22.24.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 07 Dec 2025 22:24:29 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [PATCH bpf-next v9 09/10] bpf: Optimize the performance of find_bpffs_btf_enums Date: Mon, 8 Dec 2025 14:23:52 +0800 Message-Id: <20251208062353.1702672-10-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251208062353.1702672-1-dolinux.peng@gmail.com> References: <20251208062353.1702672-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: pengdonglin Currently, vmlinux BTF is unconditionally sorted during the build phase. The function btf_find_by_name_kind executes the binary search branch, so find_bpffs_btf_enums can be optimized by using btf_find_by_name_kind. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin --- kernel/bpf/inode.c | 42 +++++++++++++++++++----------------------- 1 file changed, 19 insertions(+), 23 deletions(-) diff --git a/kernel/bpf/inode.c b/kernel/bpf/inode.c index 81780bcf8d25..781c2c3181a4 100644 --- a/kernel/bpf/inode.c +++ b/kernel/bpf/inode.c @@ -605,10 +605,18 @@ struct bpffs_btf_enums { =20 static int find_bpffs_btf_enums(struct bpffs_btf_enums *info) { + struct { + const struct btf_type **type; + const char *name; + } btf_enums[] =3D { + {&info->cmd_t, "bpf_cmd"}, + {&info->map_t, "bpf_map_type"}, + {&info->prog_t, "bpf_prog_type"}, + {&info->attach_t, "bpf_attach_type"}, + }; const struct btf *btf; const struct btf_type *t; - const char *name; - int i, n; + int i, id; =20 memset(info, 0, sizeof(*info)); =20 @@ -620,30 +628,18 @@ static int find_bpffs_btf_enums(struct bpffs_btf_enum= s *info) =20 info->btf =3D btf; =20 - for (i =3D 1, n =3D btf_nr_types(btf); i < n; i++) { - t =3D btf_type_by_id(btf, i); - if (!btf_type_is_enum(t)) - continue; + for (i =3D 0; i < ARRAY_SIZE(btf_enums); i++) { + id =3D btf_find_by_name_kind(btf, btf_enums[i].name, + BTF_KIND_ENUM); + if (id < 0) + goto out; =20 - name =3D btf_name_by_offset(btf, t->name_off); - if (!name) - continue; - - if (strcmp(name, "bpf_cmd") =3D=3D 0) - info->cmd_t =3D t; - else if (strcmp(name, "bpf_map_type") =3D=3D 0) - info->map_t =3D t; - else if (strcmp(name, "bpf_prog_type") =3D=3D 0) - info->prog_t =3D t; - else if (strcmp(name, "bpf_attach_type") =3D=3D 0) - info->attach_t =3D t; - else - continue; - - if (info->cmd_t && info->map_t && info->prog_t && info->attach_t) - return 0; + t =3D btf_type_by_id(btf, id); + *btf_enums[i].type =3D t; } =20 + return 0; +out: return -ESRCH; } =20 --=20 2.34.1 From nobody Tue Dec 16 13:22:08 2025 Received: from mail-pl1-f181.google.com (mail-pl1-f181.google.com [209.85.214.181]) (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 3A31F314A9E for ; Mon, 8 Dec 2025 06:24:35 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175076; cv=none; b=BYmw8engb2z8m/FvAdztL1JAeyXMzJIdfhh8zjjwLH85JgJmIpIAdzwcBgsfSetVeAevhqMzZnbwmnwBdFPcxm+YqCgow+AgHx/trolkrDQyoAjroeBcjzRyo0BZlMAOl1n7w6XBrxleMdMD9nRT2StNnkRx/g/YiW/Y5+mbqDo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175076; c=relaxed/simple; bh=aZ4yetfrgeTYuAXSDNT9Lk9SPyXMTL1bFvrnSHmEhiA=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=f53QaggjVMVxJ7sQ+nQgviO10LtLergNBcdT0DbaXyOCSBTOXvxKwN88iPud2x9YcguEDtd45vlyU2GKE7SOwMOFNcwimdNkT9CT/A0EN6nZ/Zq2RvNbLumiGoEO3Im8AaCf+7kiXPtKkjcTwDRYZV5G5PD+ytHOa+Or4RMzbPI= 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=IFb+6lpe; arc=none smtp.client-ip=209.85.214.181 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="IFb+6lpe" Received: by mail-pl1-f181.google.com with SMTP id d9443c01a7336-29d7b8bd6b0so23258025ad.0 for ; Sun, 07 Dec 2025 22:24:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765175074; x=1765779874; 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=XTMvg0fLdGjE7sVVu3PqfAO/yQP0TQsUYxQ40b0xGyw=; b=IFb+6lpeYsu3pPUeyxTsfWJ0uhrGInWoiL2BTyDDuQFeXQDARrFncY4sEMgawGWjyf DHfmJTdgcWWNbAJHViOfyL/HTv+cse/OF9tAwmPC4INTZSLtxMemBcRymZJpZWm+74lG /AQz6Bks8nQi7k5nk7PHM+r6UaOOsN2X6boOjTgIUaxJKn9WAFSlP11ol35+L+GBooS0 JagThz7kCzpjeg9w6mo/2hfA71xtg6TColeKZZ1UZ0PcDlftBojgoRWTKjiyufeMxFNt MWK9/aL9dd3fxsUf9FexH0OqXl1nwLg0uWjKV0HPhAt1sCzxZTg6znazWv2MiM9PAX1D xyvw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765175074; x=1765779874; 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=XTMvg0fLdGjE7sVVu3PqfAO/yQP0TQsUYxQ40b0xGyw=; b=Rak3goGnnbSj6nzj6TFRzVssmb2edfMXhKfD5uA6lZBng36iTBgUyVNjLwfCRM9qLo EIkuLRWVW7ybZzyMeqE2aiSyR2mwY8Vly8ZHH0zuOaJbG7WVLG7RhrvBHzoCrbNdD8gn UjxBgIfUKFMRgTdEVBCdd0Fc7TcMclGGZ/xjEuCj3hFeSM4sQfzrlR9DkBNlQjUdvyyO WsouVd5RCSY9tc62psOwHIkqySZUcF6eUZ8IXCEgrVIZsOEY3bYgKO6021Xf34ztWXu4 ZF7sVPIFlox2Q8S2kTztDFtPeDSGCZaF57aNl0K8XxdOkTyzfjQ8fVUsQvW6VsUJ/rMs HgkQ== X-Forwarded-Encrypted: i=1; AJvYcCWLsOMKBHLU7Chjtp7TUDPIeC0Z268pNY5rejK3TVGy9RhUzJAglUDN/fzwZQLHEenV/veptoJM8oj5d+4=@vger.kernel.org X-Gm-Message-State: AOJu0Yx8nwU93gcHSUm4qwTjyY0p2DypppxcJr8jbTlJLYC3PoQNSeP0 ANdePu+vaCWq+SBumEn+dOC4AwEOKr2WSeOhfYtO5RgIO5PKoo2SJyzU X-Gm-Gg: ASbGncurn81MV0+B7cjurlWsKwn7rUKtkFOo5VNtTyitiqL2nRjsZDzuiY5yPQezogT Nkl0B/Lti1rnh3Ad7Ah4Iq86sleWiSNJ+elCwi24EMpCYlHXdlS9Jib1kVxS76ZkvJu96Sokvge bvJ8FxgzAHTc7mIAqpHyjoDPcUr1JYFford02tzdhtBuDzGFCymEinqNS1ZbJ5RTlwRE+RzPpvI 5mdXuzHHDDzpK/kbMeuE4eKQnHKVQ1GO/4IBwlOL0gRWpkBSM7YOssR8efns1jvjqRPQCFK1KWp Tp8IyO93aswhFJQtApo9BFC7K0sAf/E3uZS/aRwyPk9ZRfSGMB1wMcDt0uoMcKVnL8sE5VN3jxV Aah+8KYepMECHUqOB0WlU9VecP3hpNo5fqrTNa+TpmKXh5sBtvgeVvlhFgCTGvgKuZn0Khj3ale NeZOp53nOC8+W0a5H+GQqvWMdBcF0= X-Google-Smtp-Source: AGHT+IGGZHqqBgW/F+zVLF/26I23JIOf9IQ8quQP7sidM29+pxTZMtUSFKegS5r6qu6MW13OooRSew== X-Received: by 2002:a17:903:3312:b0:29a:4a5:d688 with SMTP id d9443c01a7336-29d9ed0b507mr118197205ad.15.1765175074367; Sun, 07 Dec 2025 22:24:34 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-29dae49ca1esm112555855ad.2.2025.12.07.22.24.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 07 Dec 2025 22:24:33 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [PATCH bpf-next v9 10/10] libbpf: Optimize the performance of determine_ptr_size Date: Mon, 8 Dec 2025 14:23:53 +0800 Message-Id: <20251208062353.1702672-11-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251208062353.1702672-1-dolinux.peng@gmail.com> References: <20251208062353.1702672-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: pengdonglin Leverage the performance improvement of btf__find_by_name_kind() when BTF is sorted. For sorted BTF, the function uses binary search with O(log n) complexity instead of linear search, providing significant performance benefits, especially for large BTF like vmlinux. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin --- tools/lib/bpf/btf.c | 42 ++++++++++++++++++++++++++++-------------- 1 file changed, 28 insertions(+), 14 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index a53d24704857..6de09a5c4334 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -660,27 +660,41 @@ static int determine_ptr_size(const struct btf *btf) }; const struct btf_type *t; const char *name; - int i, j, n; + int i, j, n, id; =20 if (btf->base_btf && btf->base_btf->ptr_sz > 0) return btf->base_btf->ptr_sz; =20 - n =3D btf__type_cnt(btf); - for (i =3D 1; i < n; i++) { - t =3D btf__type_by_id(btf, i); - if (!btf_is_int(t)) - continue; + if (btf->sorted_start_id > 0) { + for (i =3D 0; i < ARRAY_SIZE(long_aliases); i++) { + id =3D btf__find_by_name_kind(btf, long_aliases[i], BTF_KIND_INT); + if (id < 0) + continue; =20 - if (t->size !=3D 4 && t->size !=3D 8) - continue; + t =3D btf__type_by_id(btf, id); + if (t->size !=3D 4 && t->size !=3D 8) + continue; =20 - name =3D btf__name_by_offset(btf, t->name_off); - if (!name) - continue; + return t->size; + } + } else { + n =3D btf__type_cnt(btf); + for (i =3D 1; i < n; i++) { + t =3D btf__type_by_id(btf, i); + if (!btf_is_int(t)) + continue; + + if (t->size !=3D 4 && t->size !=3D 8) + continue; =20 - for (j =3D 0; j < ARRAY_SIZE(long_aliases); j++) { - if (strcmp(name, long_aliases[j]) =3D=3D 0) - return t->size; + name =3D btf__name_by_offset(btf, t->name_off); + if (!name) + continue; + + for (j =3D 0; j < ARRAY_SIZE(long_aliases); j++) { + if (strcmp(name, long_aliases[j]) =3D=3D 0) + return t->size; + } } } =20 --=20 2.34.1