From nobody Mon Dec 1 23:33:22 2025 Received: from mail-pf1-f172.google.com (mail-pf1-f172.google.com [209.85.210.172]) (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 71E533164A9 for ; Wed, 26 Nov 2025 08:50:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147038; cv=none; b=Erl/PbhCrsd7g4qqkLUy3igB6eaghRQSCj/oRcCSjynxtvlqPnmECgkJw/9QnZMsKvZ+tSQ90BMV5OkWhNhNiaUgbcU0PuRfNehSnIQ2CnPRKK7rT+lsEIRL/4dwdzU1Jqi+e4irXs1szAMb03S05cxgpbPqGdBDtm5e1okVt5s= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147038; c=relaxed/simple; bh=YJNPYvfz/GxoZXv79UmIYENyuKk2IR71wtQ8M88Szf8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=tWYsaDrXuRtKDANIf0S6AwbwKNcb9rBbboRtJPlid+IjvzZiNfTvvnqqXBrnjsI7hXjtOX0ACF/TSgNXBqnFB0S55ASLg141Y7jE2f7QQxY4z5LtzG0C76v/zTLupAdwiFxaUKcA5wsNCdUO4LG3m+69HrKlc/QAnxYyUE5oVvk= 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=LMenimB+; arc=none smtp.client-ip=209.85.210.172 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="LMenimB+" Received: by mail-pf1-f172.google.com with SMTP id d2e1a72fcca58-7bb710d1d1dso9809709b3a.1 for ; Wed, 26 Nov 2025 00:50:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1764147036; x=1764751836; 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=LMenimB+wyVQQmyBG71lF/9Nv1Wuudu14lRXLsJ0OQh2Q7VeAMO3c9bPrRzcPhUPlJ pUwDVSyf4l96H50Asxl8MeLcn/GoCspflqPB62WIt8BvjaqdD2J227lrNw00wBM4XKB9 TzRvvuRNZVyuYtDC66B+BtZwrsTieqg684OL4pM5GW3YcGMe606WPNfHZ+/szs6uDN9R wVHuEg/N+qwZcscxw0RvPRWXfUhKNBGVsZI+/1BXGFxbcUYxtmkgx122lAkVX2589ScJ SB0UxIHmjKycruGvjo0Ax2+v7UeaLEWrPBeNOl3VKflxxEmbOnqOihjN0jkq3jBnyWZW KcuQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764147036; x=1764751836; 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=FOdJiwxRUbn7cTlLjwL1339jlOeLvMlQVZpLdUDLI4FSPhKWqdlPZjRGqE6Nnsg8qj za75Me43zYffPXLujiJnl463XgS5dV5PR1d8HEc/OCHCXY7jh6+y7EIOayNHTjGu1CoV 1dMQa5sARPZXjZQ+cOzIKjZzofunRJkL9IMQyRj6LUkpOzg+Rj4rAmVTDpD1iFWkUDmm ZgKYx+BfMCoPTkPicESJrgd7Tv1BkUW/CS58H1MsP3JlJ6VAwW9fnLBgrqRGSE+29Qvz gJF4NGS1eooYDMMw55EtNR5qEMrH1ktI4X901pHFz3b80sZ1+3GVvimrEm+hYukqCjJW tFiA== X-Forwarded-Encrypted: i=1; AJvYcCU6uQGlxz7TSAhbeZ5KoaHbk6FQaUDm+FWZv372QZHdhvWE9sMAkZGAs+9A39nPyHf/NI3/12CEbZRsmq0=@vger.kernel.org X-Gm-Message-State: AOJu0YzUwJo6CbQu+XKD8K910monW+cwY/ujuszrcalk1uizsuT2A2p8 K8t3pMmSLwWMrOQtjZ7uNKsp+FzCeJbtjvZDkfwTB/lu7rICmr1BtDpz X-Gm-Gg: ASbGnctzq42AuyH1wf34DeO54QiXpcx/JJkLPnWDoQ8xtBDedlibEs1KQ0DmvM1O8vv H9ojn+YTNFlPTkgMvFz3JuZX0D0FU96KuvpARYbZ0K7skML1hVwjckCVAkJJZ+7Gx0rhAbWb9IY 1aII2HHlewyvxcqmd/HXuoi18O+CCkTpaeAP8Wz2owOo8e0fc+H8nddcxQlRXfi9VTmHa4/i1xO DeoikoXmZsrIR3M/zAKxrue2T0JLK+QSBtvqTd7aLFRJaim4ZtkLVk0itLKNKBfsXQxgHpnrd4B Y3Gfr/vsDlnaGuXxbKfM3gWnZyenZ9Fd9A/UT5eRbjiEThKDmjBm99XV6yyS3whqjLcQOMRRx8k N8elOJdOOAABEHIdgGX5lKRp/eA3/+laU+O7nTVQBTc3+dMTm2gl3lOuCSPewsYB4n4Kh1ihuXg nbPCiTzzb0yJ+LiwApvzdcWKWhNic= X-Google-Smtp-Source: AGHT+IHKWn9NWkYUvRb9WwqZogORsd/GfhCKitXLaO71Cj/o/bBaypLjOcJ6zUVdxpMAoqry3FCk4Q== X-Received: by 2002:a05:6a00:b53:b0:7ab:5e68:e204 with SMTP id d2e1a72fcca58-7ca8a043bb8mr6202036b3a.29.1764147035605; Wed, 26 Nov 2025 00:50:35 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7c3f023fd82sm20885721b3a.42.2025.11.26.00.50.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Nov 2025 00:50:34 -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: [RFC bpf-next v8 1/9] libbpf: Add BTF permutation support for type reordering Date: Wed, 26 Nov 2025 16:50:17 +0800 Message-Id: <20251126085025.784288-2-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251126085025.784288-1-dolinux.peng@gmail.com> References: <20251126085025.784288-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 Mon Dec 1 23:33:22 2025 Received: from mail-pf1-f169.google.com (mail-pf1-f169.google.com [209.85.210.169]) (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 A2C6E31C584 for ; Wed, 26 Nov 2025 08:50:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147041; cv=none; b=NnKRDrho1Dh+KH75M1Y9u6Ee9pwpnFKlx0dBGiXpSNW2NzbEWD23LhkLSs1IFMaV63l5MGyJ84MGujqavHlcS5QQeAeHlWTt1YXEQ/+uTKEucWACoWbiQJH+bDQas6FUhsBU0xFbCjeHUw9uE+IZKVI5QQcU9xaMEAhXsNfQozM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147041; c=relaxed/simple; bh=7ngEULL678quRrsmJ39omINLf8wh8oMlVDKhnztkP/E=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=teknj2gcSYSp69ozWkHzqFjOa7iHTsMcnKD81Pd01rMUwTUzE5yZ+hyGVY0CkvP6ptVZ8CCEoasjiXlddSt2mIm4owRyriTcUrnYayegaCH78n/uIHOXGWa2VC6pSJwBUYdoUI9GIffe0/ChUaQn6I2Gg2ygM3KNYLyMzDcva3w= 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=cPvyhXsn; arc=none smtp.client-ip=209.85.210.169 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="cPvyhXsn" Received: by mail-pf1-f169.google.com with SMTP id d2e1a72fcca58-7b9c17dd591so5680951b3a.3 for ; Wed, 26 Nov 2025 00:50:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1764147039; x=1764751839; 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=cPvyhXsnzE7RioeKynOfRhL8tOXWtpCqlRdEkdyslycqWPZCNN4pubWDC9xnJBFWW4 9bdKMU+5tmiWgRJJ5rAdfpWkR8kCVHnyx1EE3+P3zUpogqWFsnEcVU+Nc7uFmJQflq85 aqVBBnhO21CWZhDWO+f+jvW4XES8kxJwCbuhzxQrqP+4IqhSwjxBtNj8Qsfr9w+RW/uU qjsZA78pP1kzzLKiCqlRX0bCB6DgpLd29F6mg2w79boTMqqaVpA0gl6zmChEOloK/7yJ m1g58KONwQ+NXAsPQgT6vTGqwDmyOQQ0d3W+Hoo6TN2lJ45drW9V31WukXexVTYyk2c+ sf+w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764147039; x=1764751839; 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=t6rTx0ut9xP3n1/0TNtJd+5nr30m+5hLofYyMoncgej+b5Xx9k1fOy/AsPjCpUcBzE WOHLLErhRhxjepwwUkhxDcrOgIAag1J7GJg4oGMdRIWi7PnBc1Y4riv7J5xcQYMXmvA7 CSAPZ5xuNzE4N+drYeErH+Bc9nflUuQ3sCeY1KPNPoYIRF6fJROXqU29RR4pima9nNqk ptKuGDo19oVSiLoVNoUEbaXSPQ7xTPgo/I+n+CcvRVCMB+jKiQHN1y/4ux90xkLULIh/ m9/WOp9FdIAH3u1s3Y3H8sEu9OFE0E9DqYBwaM/AhW6rkFYiRZOuhLF1OhwASKqXhKfM EHSw== X-Forwarded-Encrypted: i=1; AJvYcCWYav5BieyGtwsp7vheOjvK5CrnQGRwvECWGGBR4c0tsqPirxLRHEGmLfJHs9m5DlIRMljaq32/qD1cbKU=@vger.kernel.org X-Gm-Message-State: AOJu0YzxhnfFp+BkY0xxtC7m7HtGTPI8udBiibkpFSQRIqD5Spw1XPvN Egw+sTj3oc44jaZ1eh7J+AYqjWlpMKen5UnqgGctVVqTfUDnKfxu4q0t X-Gm-Gg: ASbGnct26sraYQJXLqTeyP042XskoV1kijQPCrC/kcvX2tlB1dWUBTRa+Cm60KtkvcC /ukMD2ySYIokauWraXQJwqS/Lv/i4GaXOzxiBxdbOnUiy5DX+zoSyilfB+nDOI9RZvZIChOUbrz C0Q/5TzR1X1Pq5lqBniDZOrZgz9BDZwN7prB4H5PcsaOnN/cHGKKnOzGifmo24gGg9qs/UKQzez 7Z9RGDgCgBF1cj3C07hTZUndVMt2bUZwQBL4FlJeEO0ZXsyZ645nee1hW+gMdGXBAnLn9aAbskt CSwqJ2hdoVXgxN/Wh1y9SjHHeT228pQLNHCJNuxynAqV827jHDByWysW214LNq8F+78kjLhSnTj m084BPSMvrzopGQYWhMKdU9lMTcYwZMw9Yw82zLqPZt//6qREWYwI5C3nNnD6WPw4Wn2EfL47H9 sfA71+ZqIntmPLL4fQi7OaFirrdjQ= X-Google-Smtp-Source: AGHT+IHqvZLYppoBK2yVx1vDc9XKQk7gBLgQKYgen0ASnKXiIzwkQYbXBtvlVFuNZZBz+61W4qzx4w== X-Received: by 2002:a05:6a00:c83:b0:7b9:7f18:c716 with SMTP id d2e1a72fcca58-7ca8740ef7emr6830252b3a.1.1764147038864; Wed, 26 Nov 2025 00:50:38 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7c3f023fd82sm20885721b3a.42.2025.11.26.00.50.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Nov 2025 00:50:37 -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: [RFC bpf-next v8 2/9] selftests/bpf: Add test cases for btf__permute functionality Date: Wed, 26 Nov 2025 16:50:18 +0800 Message-Id: <20251126085025.784288-3-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251126085025.784288-1-dolinux.peng@gmail.com> References: <20251126085025.784288-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 Mon Dec 1 23:33:22 2025 Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.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 1C8F13164A9 for ; Wed, 26 Nov 2025 08:50:42 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147045; cv=none; b=SjhG8gTkOmLVH5DvkCTwrr5Bil6NBgrfCrUYJUBJqXqEJsvZ67cvFxi9w7dAbhM/XcPg9WSp/6TV1JZV9RgCPCzCULXBuSdvdkBiX5CEGK9sWcha6QRhrgvq4onB6hOgWwBqJsVAcaGMxUsyjr9yOSHhAVr/AuhXnkPcAj1JOUg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147045; c=relaxed/simple; bh=M/VgPIqfRWvPIYxFG70p0tBc3APY/ResOI4iwLeo1GA=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=U1RIubeRf9DW8O/1N3tys+fd7S+emg9nkgPHuS30j9SpqLvCBhIcq6fXLUMJ6jprfgBXZwNwQZ1xvb4AeaXQl5yV/4iYgKZJKnl+8a95DBkW3p0yKE6Ccm/1w9e9AjpxwgJrOSuLUxUgs4wwlRbAzgymggRnb2rOluiWhelpDdA= 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=Q6KvvDyn; arc=none smtp.client-ip=209.85.214.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="Q6KvvDyn" Received: by mail-pl1-f182.google.com with SMTP id d9443c01a7336-29558061c68so86218095ad.0 for ; Wed, 26 Nov 2025 00:50:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1764147042; x=1764751842; 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=PIDDUYkGHJz7WnHdi/CS+AAzIaF6rwKCgn01mtFAMbA=; b=Q6KvvDynZ3Ig/iK9bEbb3g8Nd4jO+eedRGYggeG6oHDbnnUDMqFBZOlpaZkctxJKKx 1Ybnw9TH5LBZEnBcd1zyGwJl1180DM+IhqEmiIGDvALgzefYRcWOV7kBjkeZJoU0Ztm9 AYFBgD2AZVnCZfPQl3zKqOYXfGxyNaMKiDwGJC2A+MEOfqimMTyjI6Dt4sJNdaenzF99 Jx2feDmgVrNVRq2PKXtbVV383p2a+atdS8xWKTQmzSznOPju/JgPQIn9jjz5cUW1Oqnp NxTPateei+EOEZ5X+CRAM6jtWXnvhDRQ6+ZjLOy+MWBgiFvGw9f3UC2M09zCyR7eZ212 hI4w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764147042; x=1764751842; 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=PIDDUYkGHJz7WnHdi/CS+AAzIaF6rwKCgn01mtFAMbA=; b=AwhMtnTYyqNsrjg5mR+vQSqJIiXDw4S6eNOMrSPduqn7VhQlO8f8mSugJYF///OXCv xZXY0jNszRHBrlUP+vnmK3KiKm38FHMPKSVBuQFkEIRWNchd+3IIrCjG1/9gthBY96WE vGn2RXRshqB5l6TzBcxHPeldUUjXfqwmEihdv2/UliMCLy+6A6PDo4yVskiwQpX5q5Xu 9R86XGbLIj1/O3dwhLOzN6vlOZHjn1F/+Xl/lq+ITrqCkuO+IyCC5N+Gb7ziUUxF7khh hd/NmZh52iVPDqpPb8iNtqAonTVoT+ImbkGzaQ6UlYrzjS+UlHhmiMxeOtzy7pL6gHIS smlQ== X-Forwarded-Encrypted: i=1; AJvYcCVq3LPER2+4U88O+Q5Ne4zjErSg4hmMBlu7iDzrwpCJ2YpIB1mdUyekeZQ7RtoGC4EZMMfWED7CkQE3S1A=@vger.kernel.org X-Gm-Message-State: AOJu0Ywbx4q+gHGePvNwIQCSP+JjAUT5r7rS2aaBoYPWQSDFOmyeDdLA YrVs2hE1MdP+bOBcpFVGpiz4P+d8PWQOp2RmmyDJ1yVrT/4FAaFBxdND X-Gm-Gg: ASbGnctCVs3Fep8qMFg/a4oljoz5UfYxuI0awKz+/1Mm0jUEN4uooGYk+i07H9NI4Zg zIrZO7YHljOW7pfnvrRrMpiLHP7zpOPsxcgvfcOQgTu4Zz1nO7ais0rMd9StdK3InO7/Y3/aUAT bI3gwRRPrudd6NeA4BEmOisbnpQgn5v4fB6iZ2V857w1VkihHTnX1Nhvqo8QDGIE5Zns9XZij51 BDVm8fqM+UXkJkgz9ypH/n6+bCR9u1OFRyOqxoJ7Hp85LoDOcQfVV0YAPs7N5LiMKV41yW9VHLB TxmeBeVAL4gaWwiw2Bq1zWjkyfP0zop0TAT6mjlo2BKPSu8PzxAfLyrCQeL9hSOb2lLDu+eNnl7 AVyreHZhkkylzikeiZ20E6QQZGsgEXrLd4agVw6DneLLz1KgH1VLlc8iwBouSC/XYzoCLfxJwCP lWNyv2eEVxtj1krCaPsmqs9bpotoc= X-Google-Smtp-Source: AGHT+IHvlil1iO59w6L02UVKaswg4buo1LY0f0OcMcJNxORcAcKjg5GLGp3oWtBsyoFormU2mRxlpw== X-Received: by 2002:a17:903:11cd:b0:298:68e:4057 with SMTP id d9443c01a7336-29b6bfadca0mr207376675ad.59.1764147042164; Wed, 26 Nov 2025 00:50:42 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7c3f023fd82sm20885721b3a.42.2025.11.26.00.50.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Nov 2025 00:50:41 -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: [RFC bpf-next v8 3/9] tools/resolve_btfids: Support BTF sorting feature Date: Wed, 26 Nov 2025 16:50:19 +0800 Message-Id: <20251126085025.784288-4-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251126085025.784288-1-dolinux.peng@gmail.com> References: <20251126085025.784288-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 4faf16b1ba6b..1d2b08bbd8c2 100644 --- a/tools/bpf/resolve_btfids/main.c +++ b/tools/bpf/resolve_btfids/main.c @@ -857,6 +857,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 const char * const resolve_btfids_usage[] =3D { "resolve_btfids [] ", NULL @@ -900,6 +965,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 Mon Dec 1 23:33:22 2025 Received: from mail-pl1-f177.google.com (mail-pl1-f177.google.com [209.85.214.177]) (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 3BF9B31ED81 for ; Wed, 26 Nov 2025 08:50:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147048; cv=none; b=BCYv9qJcrfdqoIo4OKIya7RovKlniTf7YBKVMaOnObbaxyzjJi4BIlLjHYpeeqkcI5XRiwp7UOQfgB5L3ExkDXt/XbJsogUjdBO5BCB8iN9CaJyof6545v7LEXRJWuXAY6TLPJrqMtEqXJkTtZltM6snNsOznAo+y8ont+TyDLA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147048; c=relaxed/simple; bh=d3DscDcBlQkBeK2zxMbgxBMfQr0YMduHtPVlM/+IxLc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=aMYXLoqJPpAelgDc4lDM/pI4gpTVEXbdIzOjRjQ7XWb3tgIQ/K/BYlLXkbu52KZGeAo7PXzyfuxvn85pV1IZ3rFyf0u5ji2+htF9glCtXZBXnbWpGz7Mli17bNwIWquVaBzc0rLWqVVDNimtAuatzsCU8tfiuRPfltzUHfpMBnc= 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=d1LRS1SB; arc=none smtp.client-ip=209.85.214.177 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="d1LRS1SB" Received: by mail-pl1-f177.google.com with SMTP id d9443c01a7336-298039e00c2so91338105ad.3 for ; Wed, 26 Nov 2025 00:50:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1764147045; x=1764751845; 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=d1LRS1SBFqIAw/EWNAYYzaxruahY8jlP5abN/EruKq00prRiIoJBgJfjgteOl9E5nB kOsIGAlDrqZSxDaYkrMyb4oyAvt5D0B7yNxqTaH2QHU0E6YjZAtpzLYUTHaKTE1JkRhd Ia4MHCjEuRRp+2X6Vmu1/f500aFlW8cEdim8jd6+4ZftZWp2fl6AoWFCKuARuEtihiD4 tqrrYnI91m+rFXyo6Wp5w/aJlzuvOwsVfDofjmsa9oF2I7lay5fZWkEsGxjrXPmVaCH5 Xnj+oOtt0yEPu00XlqfxWtOJ/pCnpKtEqcKp4w+VNsNKhWQKjxRCMZ2WQxeOJNOVjdWk 2xGw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764147045; x=1764751845; 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=prSB0fcCV9qyvYyq+plwYcGJJc1t/a2781RR8iKy7pLLPGLLhshoebBUkPdHiZXg10 legfp/ndfKwwo5kSYPOn/C+x0FWwJPjX7+GOSzxV1oSdPZTWAXb1w50LdDPLuDGQpsXY y7Wv1UHEszSfk3lUm/NsLs+nHNJG/NOlP8jWV6+C+BDMtRgIzKl7wP5eRds42RnoDODu wcjHRsXUUAPYPhdFjLng9PC/jsWiUtxeRVS3N8v7qQLPB85suNSzrMlyGKNz8IjfoFNK e0+JiNvUXjLWZHBRFhXKZv4TlFmuzsY2zkyPsRUBMRf0AgpxAFZYL/RVJzn6ysBAjDNz 3E8Q== X-Forwarded-Encrypted: i=1; AJvYcCXCGxryjFZpZ9AqGm6CBlRCAvra5NC/mo7C5shny+p26tluMW8C5SV9iyEmV6zpBxYA+mJBWMHnqD70rfQ=@vger.kernel.org X-Gm-Message-State: AOJu0Yw5cJXENl34l2YbnR8K6ieXfxT0Hq/867AM1DGue0MF/oK0y0ia p7/dCoiD9mZwm91LJ0tIMgL/iVW80wKq8oH3aDXH/NpPUWvmKTdW2wW4tjvwpVPgF40= X-Gm-Gg: ASbGncua7zySLIC+y4e/XfBTIG0/0UIRpwppeSup6QGBnVYngbwGUDbx2ERpatgmFNm La6EG1nApi3GJiNOjKV5ryIif7ud6Hpx4ECf0qlwuh5FYHpmbMvLdMk+jl656SWY+Fhl3OrCt86 I2KtTe5KAkB0Imas1o9y0pZMQW1SYHK6hBe8z/n2qPYcaKMMavSGje1dmWpmIYkUvS1uFR/7LDt qUehRhpwGwurn84fjSA9z8Ps3kiDCRG1ohcVpeOBrQrNwvb39cWXd3BQWrc/I1rPfRWlJrEz8E7 eOQ8DSG/Wx3FCeFwjl44tG9z7jpsxv0UuPZ4b6u6MgPmvvzJctY9uu9CWFghWtz0gq7mKsobiEQ aJqUCud5hgQsRBDg8rHxbMPutYnqiIjIENl8/kfv5A16Ki1r2dixd+HLsA2l/EDJywlU6N0Gzjj ZaWvx3G6RM8BPignM0ybJnboIM6dM= X-Google-Smtp-Source: AGHT+IExZ5vV40jQbHSa6VDCuGIq7XV7fGyz1t0658/NLZTAynNpqwve20+hXuyWBrgSMrtQ3opEpQ== X-Received: by 2002:a17:903:38c5:b0:298:1f9c:e0a2 with SMTP id d9443c01a7336-29b6bf804b1mr226373385ad.54.1764147045527; Wed, 26 Nov 2025 00:50:45 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7c3f023fd82sm20885721b3a.42.2025.11.26.00.50.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Nov 2025 00:50:44 -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: [RFC bpf-next v8 4/9] libbpf: Optimize type lookup with binary search for sorted BTF Date: Wed, 26 Nov 2025 16:50:20 +0800 Message-Id: <20251126085025.784288-5-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251126085025.784288-1-dolinux.peng@gmail.com> References: <20251126085025.784288-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 Mon Dec 1 23:33:22 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 9BDBA3164A9 for ; Wed, 26 Nov 2025 08:50:49 +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=1764147051; cv=none; b=ldEfMdzIKZyqoqnwNugxoIl41O0mKjr4sCwoYzv6oH38akM1gshzQVIEsBCpjsJ373AmiigF6Y5FQbUjsLJOAnSd3E8e99oIFXj+af6h/o5oSotbJd25iSoMUD1qX3VyF7QLINC4lc52kBDVqLeMPhkFUaSg66e6KD5ZerEX3Zg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147051; c=relaxed/simple; bh=8hsjVTc4iHNm8LdtJrSwh8RnQyLo12TybfR54C1ppls=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=BAkvGs5V8UWhrQQTGr0kh/URsJ8JMIYcwTouFEJe2Bb8vneH0WxwkAcND04ORiLcjTR7mO7VPDT7Li272jpbDs7ieas3KRno7oMrZf7e6F1mC0+Af6E410mFypCf7s8vJ+UIoHOJlu4B89ZvO283SzSMnLaIahox2oYC7YIKdLI= 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=Q95TwzBI; 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="Q95TwzBI" Received: by mail-pf1-f178.google.com with SMTP id d2e1a72fcca58-7bb710d1d1dso9810153b3a.1 for ; Wed, 26 Nov 2025 00:50:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1764147049; x=1764751849; 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=Q95TwzBIWLoIWY7yGyjEa+OiZMKCMGMTCqr+Xo09xos5bty7k+aaFtgOY1KTaE/Uc0 2EjysvwZIaV4MVwRQ6onn9pTtu+sOVmMWJfiFOf90mPP1Sw/2NlJw7qQbyuJqQJPkGZu O/YPGWHyzQifVhml2fS6GP8OaHkEeSF630FpCX0GZpQle2Wxcb5RQhL2hFnG/uygpKLZ r1SKSx/rWu+SkEt38J3yK7EKs6Y3aQ7Dd5dQLHT7fZIuZy+maDE2Se0RKlcgEIIK5v2Y d3H2RmzItsQLSlww+3tcwJCboizjvhrRjfOuuGVUZcUpG9FaKDfA0o0YEq/CplATngkO tjdw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764147049; x=1764751849; 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=fxVqtT9dj3eGKlvM6i7+9H/lpC6lymsI4X35qYR3POrFaeBRD8kqIq2jDOZ3PPFdYr rn2oP6CncIXz9QFkTlabfyHhVgbmmPZKS6OT1xOefmgBw+6Pa8Ds7yt26xciHRV1UYK9 SVdMehKMgshQ5CVU+E3k3w+vb62g8wL7+VtnG+ToyhqBIDPMXlqzaow55VE16vFHUv++ oUp2I6+S1uMV7aKK9ktlIXQMROhfvqrwswptIX72iWSUf0F+9TchFKN5BmT/ZFXT149P P4sUZG7ZpGop6d2jroaS8KI1hIgtpB1v5a170AtOAhWUqHrYIh5557vv9uHqe/UM5uaG pjdg== X-Forwarded-Encrypted: i=1; AJvYcCWhBak8AkIp37gr63Om1EYszNo/F3h5UiE2Nvbc5FCmc8XDhM347hJZm8QGQ7jvXvPK1cjesHvK9IbdfmI=@vger.kernel.org X-Gm-Message-State: AOJu0YwkO0fVvhdwSIG4BM1uCOwuGM5Nt1MuPeJQPHO4m5upujkiIoE7 MwmkiuZJDu5xXesU3fP7aryJtFe3cC0IdHaNVNKwcFuBHNMdnQUbX12b X-Gm-Gg: ASbGncsKztbC3Nd7IYbkiM1M/lEurbIBqjMsK5dOk7uOOrRWb/Z/O+iJ5rEsHSyGbDs tDAV+C42NNaK34E7OGb4d8RJvb8B8K6fhR3rx0e8GHM+LzG0yF6KGw4Gu+XqTLOjeIueLcYUEDi bxqoB+gkRvwunA7G7sK4aoZf3XJFNKU4W6ouUjqDsH1qlLqeDLiQAeVYK7KEAYnFaGOOfqKl0ja +bbb2J0AeVFGg8Nbu3kc7ATqZ/dJK4gsJbWbqKvYqeYXKHHDqRBqTQmlyWB/otZPlmlIkbo/2s3 Hz+pdUT/b3afr/D9eo/1kMmqxOHOYum7gPk70w+ZG0PF+fFeDNVPPQa/rrfMImo/kQm3LCmPg/+ eUErJAoaAelXCAbsKK9dq8frvctCClIWvvQPedipRf+RqbjGINbCv8b/GzjRcwkKhH+BfTFYiiS bpP5FeXkcKvRQVvKScncd2MGC7nZA= X-Google-Smtp-Source: AGHT+IGq8Oo2JKr1dmJgr6hMlqWRYmEBgM0iCXG7gLktRGpc3fCfrvlGdc+e2qanX74xdGTGMMUy8w== X-Received: by 2002:a05:6a00:21c1:b0:7ab:653a:ca0e with SMTP id d2e1a72fcca58-7ca89a6c262mr5965607b3a.23.1764147048836; Wed, 26 Nov 2025 00:50:48 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7c3f023fd82sm20885721b3a.42.2025.11.26.00.50.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Nov 2025 00:50:47 -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: [RFC bpf-next v8 5/9] libbpf: Verify BTF Sorting Date: Wed, 26 Nov 2025 16:50:21 +0800 Message-Id: <20251126085025.784288-6-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251126085025.784288-1-dolinux.peng@gmail.com> References: <20251126085025.784288-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 Mon Dec 1 23:33:22 2025 Received: from mail-pf1-f179.google.com (mail-pf1-f179.google.com [209.85.210.179]) (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 E096B31ED81 for ; Wed, 26 Nov 2025 08:50:52 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147054; cv=none; b=ONvG/offIcpXFcWJFFwyEVkyWqxRUZkQ+NQw0YM27f5yFpxhlYl7rSlnY9RiHQBDGFVLt42m4KCu/lk+pWbZ4otgWwaGqEgwkP6P0Gv0jyT3SPrFIN9WZ12EKgwYwFerD70Lrjo3LLK4Y9NyJnX49M09A128uxDLunyQWGeaEYI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147054; c=relaxed/simple; bh=0kgEQtgvPa55pKXFrtj7srWoStjEyAoMQzDyIdaQ2pI=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=JbVs2Kmpvlb0td6a5iuxAuCzl4z/0f/9z31Rha52G1vYtHEYtR+3sJJyyRdjg6Sz7An0SM7u/yGV9nMaa0JjVwGYDQHqXJ4UlOUJhJjdv5PIpAXziRQe1rpgqknyx5iD4DrM4IvHLvx8pvxgtSqwTQDWbeQG8BPrOKC2h23OAQ8= 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=DyW+p2ev; arc=none smtp.client-ip=209.85.210.179 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="DyW+p2ev" Received: by mail-pf1-f179.google.com with SMTP id d2e1a72fcca58-7bb710d1d1dso9810205b3a.1 for ; Wed, 26 Nov 2025 00:50:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1764147052; x=1764751852; 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=DyW+p2evw6yBS3tsjQXxaAzDW1Y1+Lnmth8Lk2r6jrfyEkemBv33aCKMDu/xkR1vQ+ Xd6aAlZZDD3f+wHiykwxpjzSpfdAQ0IrSctL/B0ehyvK8qYXsLV1l7kt2KboW8pihr1i 5VMAfdBjxBteYHqnFLbd0WTapseNl2+0/D94EXTq08hKJx0wlnzS/a6SmXDoa4JEsCh0 fdoXYYflgWW8kdm6yJsOl4+NwKP2Ih50qLpkejl+gnjnLAC4sVtvR5URyluu20cEGM0w Dl6El4aeJ0PLcmOMKAUTAwOo/ZORychQLV4isyLP32wfTQprmY63/l24neoNNXsqcSVb lNgQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764147052; x=1764751852; 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=BYEntPcyAyjTyzBTzGLxDi74AVmrYm3cMMli8rBAWIKiNneTUaeYPNka/uacrc/fVJ yRcRydKM956WiPnxxqy+4PDBg2wHBZleMg1zA1pLwXovjAbYQalxl++1kM0gONoXXquX 7rCC5aa3skG72FhAyFBS/B6yRuzr51fPiOniTHH1o0pwMuSOnZTLAF3AqnVC/EdvmN8X re0Ke1xngtFdgos6fmmRvRENd7crS2qvnsjIvDwonJ/7w0Z6XYdxIVXMQhMtS4uulfuF QFaXPgHL4xf8mKBphYHvTziaC4X7f4Tz7zm/X4Ixw++vg3DHWEaBBSbcW8Fr9cqKBPp/ k5pg== X-Forwarded-Encrypted: i=1; AJvYcCVFs4G4QfdnqDtDXLkDFqltl6vHMDoboLU5HEn74NCdMpWED3D0Y7L7IyrNk3+645U32UZgXQy6it7d5yc=@vger.kernel.org X-Gm-Message-State: AOJu0YyQlhcHiqbDnY/J/cc3lF2POuMnXvnymulBVX6c3j+gyb8OlMQz ucEJn8yJwovOMJHtLkm5cBqV/M3R5dVW+IDqn6XssEpLR12fJwJ6kYZr X-Gm-Gg: ASbGncsr8sbuCgDYDIk63drBM7bEYMAvZXTeDt3pt+g7wd/RXMiSbGvbhNGVz+m6G/C uQHDA4sGeefZn/wVWty78XbMUmo1UaMBdlI7uayQIczmobtDmTpTbEwlKdFOpVLN8ji7q6eZ8+w HUJyVgqA0/Mgf2oV8MOLHel9NMSPBSfg2lEGMtKjlBwT0Sd+U+u3Esk80fWDa8g3C5tPlk7coF1 t2GKYT8WoBPMCeYpUTARcWG7TWmnT7+kPk5aIyFktZCOY13MC/17updXuvP5X7hyzGZZ5aQpUwI Cu4GUj9UIFokzR6lKYtagZB6DrNMPj8hwNLBBwZlk8ZYk8ftKjdhkcrhARkEUJW6/tcM2eBv/PT DTbbARiHsLqfgO7pYMrybVl6U3tMwG11DzCEpSNI7YEy2aqVdiWM2tNbtSpedZ+OMc/Zm5prIYH IwB+4RJxl0ErD0LeHzkoloepWVvSE= X-Google-Smtp-Source: AGHT+IFs6pLfGprWWWpfV4uPUwFHD5qyL94NbyLWxHqsqV9ucC0hIrcGzqA9thasWaM1KDvECSl8tQ== X-Received: by 2002:a05:6a20:430b:b0:341:c4e5:f626 with SMTP id adf61e73a8af0-3637db254efmr6304165637.7.1764147052098; Wed, 26 Nov 2025 00:50:52 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7c3f023fd82sm20885721b3a.42.2025.11.26.00.50.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Nov 2025 00:50:51 -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: [RFC bpf-next v8 6/9] btf: Optimize type lookup with binary search Date: Wed, 26 Nov 2025 16:50:22 +0800 Message-Id: <20251126085025.784288-7-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251126085025.784288-1-dolinux.peng@gmail.com> References: <20251126085025.784288-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 Mon Dec 1 23:33:22 2025 Received: from mail-pf1-f181.google.com (mail-pf1-f181.google.com [209.85.210.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 2A45132145A for ; Wed, 26 Nov 2025 08:50:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147057; cv=none; b=PlXeCqxcLJMl7uFpQBWJpkm1giBnBTlGLyeefhPzhf8XwCaYUGkvcVif766QcD37cof2AgIeOrPpNCK/dNWsvLSqGIAAkqK+RpTVBjjsBY70vCaOnX3QUUcLLgHg9Tg9Bo3zdzO0WcyjDQ13wPjQufMnbeasEKWXzRuB42ifCvE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147057; c=relaxed/simple; bh=SkiiMl3aCQEr+d5U8ft32wOaTMUA9E4gZBiYCpbgSZ8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=AZSJUzS8fwrMZqrJ6rxNkteHrHnK8dYzY6fnDfoZ2Fk3aN4ZpvzLgNZ9ghsCea2VjFmIFtBvpwvMWb4nlgfBvEGt1WXlkmbclA8efQ8KpS4dp7+rOTyKkWkjFjv97iAhrl/qSi65C3kRJlS+QWlcsMtSOa+7/Mq0RvKpgR22G/o= 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=hmW18q3w; arc=none smtp.client-ip=209.85.210.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="hmW18q3w" Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-7b9387df58cso10234208b3a.3 for ; Wed, 26 Nov 2025 00:50:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1764147055; x=1764751855; 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=hmW18q3wDsJHOXz68dAzlRC0fNduPF93cVq+J9aJmBID50Re1Vh72VD28qolB9Jdjc NxxPsiZgWqViI9yeZpBLXXZggdJ02kOoq884KzSXFdSq5u9hHe5XjsDSjhNHIAP1o+Zg JmLllg4qqW/C4QVMVcB57cER8ttVQEzet3UY4+bFEFRwA5g1YItaNmi7HL5z8+868fvW A0fbxmEtl+hx3atmjWaO4HUAO3qchh3TYnYj5iMskWLJbatg9qzSmgRfJEetSYPXPx/I f5nt5q8/gB6CGJWtTVXi8y4vHGRADFnFSyiZCJTaE7edSOL9fG0IdVPY61Lsns9sTAHL wdXw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764147055; x=1764751855; 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=cDXGLJaznvoUidLkG8A1f1BBT8RQ90rVQAxGcYio2GQFGxcz40zM/BCwvDSAKWinjZ D2mFdGGcmNU18jY8SavluGz/4hVwhPLb8HAIeSd6lyZTdkrDTEYE+bglycQDOEQmLB/H GvHFj8D8q4aBKsgLA3m8fY2W+CKsGP6Ik3mjAoLi6cQFMndyDP6Elw+nrtcb0q5JFVz/ zk6STR8hR04GbGYnEsNoZ0INTibasyEve5NRTtmVcBLBnaizOzP1ILm8JaTI6nxVsMex oDU8LOGGXtY2z/O4Gvvkvw1R0HTY57q7dDc3ssCpnk8n1rK/f69Yo8tpMciOcoK2EDdM VVzQ== X-Forwarded-Encrypted: i=1; AJvYcCVgHzLE6e93fh4nkcaVLsKsukvajAfooFjWd1CXKtcmfEX0D04t8/bYqfcdINH0196HhYsBd+WwdMiSqXo=@vger.kernel.org X-Gm-Message-State: AOJu0YxeWVy1s6KBq7FCUGtmQmNyJTkFPie9glERzGlQPZKeEOoZDTTl 325S8h372iyER8nEg7LYjJgvluUSf09c1DiuoONpI2/dB6e+BQzBwN49 X-Gm-Gg: ASbGncuF4BBm0C+qF87e2pRCAXKirsk0haGtip519I0B872pOabv6xRedfJZUko6yv6 ShMeMRzk7kfP4rV9PIJ0qdHj0SfHMkMKzoiXfEYCq7xjdsxYQObX7/pb+pXMtr0ZsQVbdtw+hYW 8LXvVejOxfEOGvSiswBU5ccjkdqUHHa3QzScNp8JuX0iQW6LGBw74tQdh2bkkviP9Iimk4WkEPn cJDBMtyirjuKE0on1jXKvaCVKblO/JJEsyt9VoTGvD+rMZWGQTk49EjU+pYqNzbePJhPH05ysFP 3M1Si0mceDKOjhrC4Fsupu15gM0XnjHM8md1W8dhpqxGSy3ps4ikNtnsMvi7ONrbtIen7zz2FTF vv4HKs28MsiCmMdB2nA+JrctCHSA0SIGoSwPn93/UMLNfEMWgCJMC2CT8GwODvJIp1joA+LyU92 tUL/f/Egb51tHa4iqgaFNtyduaWd0= X-Google-Smtp-Source: AGHT+IEc75RcYRzyB2QjrAR9JxTghgDBcvpbAyHuxNPUY2qamQHEbD1gRabTOEt/ypeNrmjMsOdUGA== X-Received: by 2002:a05:6a20:748e:b0:35d:6bbc:e9ce with SMTP id adf61e73a8af0-3637db64599mr7017524637.16.1764147055433; Wed, 26 Nov 2025 00:50:55 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7c3f023fd82sm20885721b3a.42.2025.11.26.00.50.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Nov 2025 00:50:54 -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: [RFC bpf-next v8 7/9] btf: Verify BTF Sorting Date: Wed, 26 Nov 2025 16:50:23 +0800 Message-Id: <20251126085025.784288-8-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251126085025.784288-1-dolinux.peng@gmail.com> References: <20251126085025.784288-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 Mon Dec 1 23:33:22 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 8F6C0322A27 for ; Wed, 26 Nov 2025 08:50:59 +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=1764147061; cv=none; b=kmUbJ6HfSp4StpZ0TStWJxBNNjM7txF19DKgcGj/eY3F5nU1viPtAXs5G4ko/r36CODffbLOBp5SQXSE6s9E4UVgPjnrzPAXCk4jW/khHi1ADkRIZd3iaJ+a9xvqExydYEk437MzyFXQFIhRj+M4eNvNfgHP3BL5lo54UvJULKo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147061; c=relaxed/simple; bh=PzKDskgzZMerL2L2GaEKme4Emf7+T6L2i2C5wE8wtz4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=YjsHRjig2JhCQbMgSMpujalqapfTnSIfm1k9kq+4jCV2U9mPoiN5Tdq4FgiR3oAb1h8Xe7OE/p/bMkJZSMQawvrl6HbSf5Y9DzjxI62D+omh23muRPCGUISjOpXGWG5JyBE/mBzCk8KM/wyb462/k5NcBY9vn6IfAVACn+VWaQg= 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=IQzOZLhS; 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="IQzOZLhS" Received: by mail-pf1-f176.google.com with SMTP id d2e1a72fcca58-7a9cdf62d31so7755249b3a.3 for ; Wed, 26 Nov 2025 00:50:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1764147059; x=1764751859; 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=58hD1y77fUWt+lA48dDAWZ48XqtnjLY8s5Dj8Cad7ik=; b=IQzOZLhScUsnyC9jpg2HSJBkX6IsLKg5UT0cc1IlnC/JCJ1t9QOC0uFyvBjVx4GQjf B3p/8Wcy0ZZhzVRB9zJpvf45dUaYbRoVLO58cD26IA8MudTPAfRu9eb8QlyfRfCNnnM0 sNgmoBUF+6B8ihr4NPb2ajPmxgun+CvQnVY7u7LtdJ99iyTEFS8Z9XyEYEHX4SZUCgiO DcJm45Rgknq3IcxYbYcq4uqo6UeV90vgsTyFlRj2KPN4rxlshzuXO1/RyZ8tPar1a0b/ zmt9zWG8heDpTua/lMoGrtbH0QIHtsvopIiqIpIsOEK//TE8n8nvDrTGeGzzg8kionth Otgg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764147059; x=1764751859; 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=58hD1y77fUWt+lA48dDAWZ48XqtnjLY8s5Dj8Cad7ik=; b=RRmJ8pYa2fgli0Tjsz9q6Eo+htILVlC3fmQGObp7QC00guOYKqyhIC3c80BQoc8kNg GD3OZ3gCf3ZNKBYxlSGXU+lXD1LzNrDTfXQsFzdpnoaJVV9YsC6HhnhAQzjSREwkSL7Q sc0EC7YelMESYSej2hBSAhO9h7m5X/wEKtrvgt303mUEMAoURHwv/uCk7FvvTW1k5ZfE vJ3cmCsbsqHkksJGFBu6puWQOLzeZZeP/zSWQj1ERcXIQYeFAVUX/XicgZKaRe6z8pJI TJSlG8Jv27gyEWY6Xw3WVCbNN3grBpdOHH6GUerQ8YyfCV5f8qGdckCIlx+/1394SXWY jqDw== X-Forwarded-Encrypted: i=1; AJvYcCWmYpW68dFNgZSc6VBslQnbpBcuGdAQ5GHSWo78yrCNvyhrHvKYutDB2JVfjHTP8ViOLNflbThn0SiPaLo=@vger.kernel.org X-Gm-Message-State: AOJu0YxNHAuDtgyR2nDRoXaGipIH4yVL0vbOAFqd0aMSSHlNaqc/6wbl 55OEJL1U+SLoo92iV9R0smtu+vFZj6EYR4G929CwPQWtU2aiQx+WwEjy X-Gm-Gg: ASbGncsiwsk8HnKzSvrCxjn4xKa+ehxp0UqTPfYMr0tyeFemkKM7asvwZ2Vb++uIb4J uN8VDGjT+NVPt+G/wMwVP6Tmk4xbXk1ZTuQhP429IwmuIOt38GSk9N1U9RZrPDVsUkJxAmtqvls OzKmaReKB6RioQU+I6jO0gu/eUl4BF2lPrysQLZ985HYdTi+4JhLwrrxl+OaM6G4gilzX68QlQG nucwu7hf3TsfPjz+Dh9CzRhS2R2gbNu122XxKd9HIZ0oNBeBvKZdZ5JF4BYT1UefY8UJ9QxWZqV T1E1LIcCLzG7i5X+kbbIRw6Xj8ehWBheRppl8fJt0RsGP5FOzsh9pqBemJCj9Afs8dj41PqC3RN 96HACekW1hgkw0JKXshdx807cmR8WQ1PSur3ukpFiwyl6YWCClrrSJuqP2aHKGPvTkSEW5KZasn 3HnziEDNGygwcXB6es6ciYBjCJbN8= X-Google-Smtp-Source: AGHT+IGr8biMRq+KgsRojAjkXMzOBT3BE61S5XBhKzO5zm4iKipVa4IvOpq4czkvkA1GovFn4zZogg== X-Received: by 2002:a05:6a00:10c6:b0:7aa:d1d4:bb68 with SMTP id d2e1a72fcca58-7c58e112cb4mr17345530b3a.20.1764147058760; Wed, 26 Nov 2025 00:50:58 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7c3f023fd82sm20885721b3a.42.2025.11.26.00.50.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Nov 2025 00:50:57 -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: [RFC bpf-next v8 8/9] bpf: Optimize the performance of find_btf_percpu_datasec Date: Wed, 26 Nov 2025 16:50:24 +0800 Message-Id: <20251126085025.784288-9-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251126085025.784288-1-dolinux.peng@gmail.com> References: <20251126085025.784288-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 | 5 +++++ kernel/bpf/verifier.c | 7 +------ 3 files changed, 7 insertions(+), 6 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..205b9c3bf194 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. */ diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 10d24073c692..367699591fb0 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -20576,12 +20576,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 Mon Dec 1 23:33:22 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 ADDB8322C99 for ; Wed, 26 Nov 2025 08:51:02 +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=1764147064; cv=none; b=j7pxwbBr3J6RqK+ideCzIcLV8MTIbm/h/zCCjyQcfnrONz2mYuDw/ZBxdL+ekhfv5Nv7wk1bkIJ0HHQYFw5zFQ4iM7rGxK95Huu5k3rfmPwnkfjPAZ6hJC0b0/a+iuhY1tkGT3WXIK048e+MQDHGNHxEbNdHe4IGFe/I+OMjNOM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147064; c=relaxed/simple; bh=n+zH9plFFMUYGIEcY3wzYO3Lyz+b74AkBCCdAEyYNdU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=BXvW3bdC4dBOiGR81k2SR9KN/uxUnS+mbcxtt4vJIsagoN85k23euJxwEJXoAVpL7KxpMlSlU/hLP3QWS9ZVgvRTizHa3yexf1QLk3BWM4xXBc9JK5+2No4Wh1jHJ6186KvQLr5dli5/4so+7FOe6t1L/KpZj+qYv+zYk5OJX4o= 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=W40X1mE1; 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="W40X1mE1" Received: by mail-pf1-f174.google.com with SMTP id d2e1a72fcca58-7baf61be569so7853126b3a.3 for ; Wed, 26 Nov 2025 00:51:02 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1764147062; x=1764751862; 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=W40X1mE1wHj00OK86wwq/JvcjMFvIb9GrNK94IItOm6DanbO/vl8X78KBNuGlgrkKv h2uGDVem9XuxbPtfuRY03Nsf08BLxdg/H+6CIIgNDLXSKW4aUGsKiXbwGJTPiPtj1KnU VfAZv6i2hECQTrPG8E/dY2Fi8mME1iFhIMWrQdV+lbEYYQQX/rtZKKW4whm2EYI7Pf3w 4PgICSJz0wbijVy9SNOBIaiJVjpc//7Dxqmfa/XSatWj8QSvUygUcd5NeECbgKmf/nic 7CAP+1ee+V0YiS4pKMFzztM+y02DK6XRV1K1NofzoGEZAVTBNHNZN7ldpBZgUIMgXNal TH4A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764147062; x=1764751862; 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=T+3xGZV2Hsy5ac1R5M+Jjl5EGDPFrKZQIJYL60gjbAXgK14ffhw2gfDrGIgGx5COwi qzzQwqsgrLE3xs7hDUr1zS1deVxTiH4m91dAGwVd+LAY2wf/8lOUZKzAlT+3OoNSTnoh 9zC7JWpncFOleCG2a71HBvUqoTZ0xv+ooJHe9dnWp2ykjXRCglmXOWiJHoXsPR0U8yNi 1quSNpBH4iKnmi0frnMYyx0whRyRUlVd5kxXutaRivQWF7xUxBPsLMOIqavEiAlxAykG FVlZnFxAwnAu4bDDJ9GxG19F7ogx8NcDJ2wrEgOw8b+zoGaQZbWw0yz+T+9touftG+fN jZsQ== X-Forwarded-Encrypted: i=1; AJvYcCUYo3XFi4ZvuWCoevqiSAmCXRAM0GMx23LXbTvSpI1xuHYZzJt048ERmTInwhOPy5oFa9mc/7xUKYeCojg=@vger.kernel.org X-Gm-Message-State: AOJu0YxSWr4xnFwrSotOVsHMSKJdD5Hta0DxsPKtXw//s7spZw5UhTKj syDAlLPOJnFVH+USHwd258LW/z4WPIodSRM2qOv6XthcwBNhF29Cth4Vp/XCK5Sa0FA= X-Gm-Gg: ASbGnct8albME14UMmC/ZtWYhRYbhyTVByvSZ00bvrVN5mz0vR1ILGNHZvzPw/l8l5t 2IjaSq8wuM5LojL8jPzuvv7U7PH0dSsOa42RoBVVH0bhzSNY6VEHAHYICVWgdPSbNAizLwjELoe AmS9+yBj8gejKfr7GpXNn60T9ROQMe+gtaHxgYIUpHyYjcWako+kc+aRI+xR2ErsfMLYJZtUzXN z++X91//n8+vTljOuqP0Iyv7QpmbJZi9nmrqfKrCzTCD8rKXYhwCbzQ0gfzsuMnVLjEryvq6tW5 akVS1ekDdibSH0dAiAwMAxQqmKGOXM1B6yuQiIW+Q0bxiuDII60ZQICjTdN6tWQooADRBjPU2PL Q1+yryW2/6SBX0AnAP162gYgwvpU6gpy0MjYWHa5TsU+aXOnzaOZOMM4QzwV97GdnBbKq7yrZsb TV3nE0piN8RV0NhlrDTMFDilMzKI8= X-Google-Smtp-Source: AGHT+IEgDYcBhYjre0eraoB995A3V+FOhafJa61gSS23jqt0ReQdbQw0qAwBnAgVbqm2O94A3uyrCA== X-Received: by 2002:a05:6a00:1793:b0:7ab:78be:3212 with SMTP id d2e1a72fcca58-7c58e0170admr17529785b3a.19.1764147062054; Wed, 26 Nov 2025 00:51:02 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7c3f023fd82sm20885721b3a.42.2025.11.26.00.50.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Nov 2025 00:51: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: [RFC bpf-next v8 9/9] bpf: Optimize the performance of find_bpffs_btf_enums Date: Wed, 26 Nov 2025 16:50:25 +0800 Message-Id: <20251126085025.784288-10-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251126085025.784288-1-dolinux.peng@gmail.com> References: <20251126085025.784288-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