From nobody Fri Dec 19 09:27:46 2025 Received: from mail-pf1-f170.google.com (mail-pf1-f170.google.com [209.85.210.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9FBBC328B72 for ; Tue, 4 Nov 2025 13:40:44 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762263646; cv=none; b=mr/Ahd4hgkjsF3VD+yRlMbZVza9HGUuhhjzkhPwYovrT/dFo/SKKCOR12vHZbdqjrtQQAPmBBohP16ttDp1SwC7dbq4uC3003dg+/UPo/YyPqWVRKE0muA/3F2nZondIpESx3TP2IWwOs6gKzJN3U716EQyLuB0Ni49rjid8+Dc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762263646; c=relaxed/simple; bh=yaIxRRwhlcK1m3sPDUbZoQhLf3iKQm28n69U+/RZ+kE=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=pJ9DC4okc0zUJ4m6h9thR3EWFSN9ZrSeaIxCaLhFWa1J9WkZ4RDiP0bZiKiHxUpOQOvO+UNu2n+ZDvPFm+gFGHAklq2I6P+QJx5GyeuQkwWFZHiJVQTg9xS8HlHwBPK6eTLr0xlR1eBXwUMEtB2KyjBKl3KkyhhxxPpEdBHEUso= 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=Tr/EG+Zl; arc=none smtp.client-ip=209.85.210.170 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Tr/EG+Zl" Received: by mail-pf1-f170.google.com with SMTP id d2e1a72fcca58-7aa2170adf9so2150042b3a.0 for ; Tue, 04 Nov 2025 05:40:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762263644; x=1762868444; 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=jiW5mEEe27+Ap+irziIB4Nicw97Y/mZ8O72ZFc+O86E=; b=Tr/EG+Zlv10adgqOAUkicKEI7pFlTxOT1DUSBSuPOkCpdowrnFW1w9lSJ4R4TQUwpO VO2y6P2lSbNv21CVXHcUZdUBU1N/2GvhAz1zWqCN7Ey0kXcrNxf6npkuzml1tAh+G7CI EDoigCh9SX20jOKtCiIQqZq+8Gap2KMcWy7VUFxBZtd/xGMQKZhcgmkyuri79mFcnKxK NqWWHNWvbnL11oNLT9xjl7Ct+8NXkyA32XOo6ipoMSn8dlDXyAr1E9rvNwKkjObo3m3O oZCcbIotMGwpDsbCDOUIX3ZT+2ke51Gcn57pH807Om+zjG/P9qyd/n/lp77W8cDVvVR9 u/Og== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762263644; x=1762868444; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=jiW5mEEe27+Ap+irziIB4Nicw97Y/mZ8O72ZFc+O86E=; b=RDdD3whd8fDEhf5oMxOrnWoSNzSiEpFVid/74FykNBssXnGe3JD5TqphUFdYYqq+84 ZE/LC2XP7VrVOofX+s7cz0TKGbEbzctS0SnvZWLHKIwx5kfmqY4arUz7I6lFsqDwR8Zr +BiTMjdsxv9uYe4GLSLXf9qc0q8MoWFCHorudir0qaQj7uJYz43xLaxQkph93ximbo4D lPzRVMlpWsFEmgteMSB1PS7LY9Ihvh9HkUrpwnlDqZaEv7yztMTeAni1v6rfBSa2IcRu 7LpetlrNYzFLzQdvdGkI626B6iDGH4JiQq8eKKYT7QdnvQWyJjIdx0Q+vuVJQ+robJNR IvEw== X-Gm-Message-State: AOJu0YwB6/ugB06iEJWrJCTrPKgonOtenD76VogoUFBEGj8TwwgKHExk 257hRPOtupg4POTiRsDKQVgYx47hQ4aDitRUXI0+qH7+0/HYqYIntFts X-Gm-Gg: ASbGncudMKztOAekhfUZCbBe21iTSyAKjH/TAKcA/Nwbqzgy5bNLGRd7HmVuw4DbXhQ zjaqutXIiGxib+WAe6Ma0hY783RkNTA+6CDDjLcXrj5aCpZmpZGYEbCnCWw3OdERLyOTEByspcB rCSJZ/3THJYNKaXvLaub/kJDcv1COEqWh9vl+o3ooe/RvHGsnvp0nGotOk9/Q08J7/CipHuOQ29 SILmyjYnieKA75TydqAPnmBtVwTSk8wN0FWLkiLnaaIrjx97l0FkSzZMDddlf+AerzTTq+q3F68 JxSmZjV3bLgVBvMot3fFplrvn2KrmWo9c6vCtPx4jrGbV8l23pg1N+zRFo//rWNdFzMKUu8vewy VXekqB1OnLi0a7Uu/nATGCv6RtHazSsQKcRLx+V1tHxGgzQd7f+YAi+nADg0GBy4QMUQGq7I3iX iR23sSteYkA1t+pR6t X-Google-Smtp-Source: AGHT+IGFdsk6TRqmdcrIGyaQa/1gESxA3BTC2WNMvzu/zlLVjYft6vWWfxs6+1Hput4xBW+Irt6MuA== X-Received: by 2002:a05:6a20:7344:b0:311:99:7524 with SMTP id adf61e73a8af0-348ca351af3mr21520348637.18.1762263643767; Tue, 04 Nov 2025 05:40:43 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-ba1f87a7287sm2499238a12.31.2025.11.04.05.40.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 04 Nov 2025 05:40:42 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Eduard Zingerman , Andrii Nakryiko , Alan Maguire , Song Liu , pengdonglin Subject: [RFC PATCH v4 1/7] libbpf: Extract BTF type remapping logic into helper function Date: Tue, 4 Nov 2025 21:40:27 +0800 Message-Id: <20251104134033.344807-2-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251104134033.344807-1-dolinux.peng@gmail.com> References: <20251104134033.344807-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 Refactor btf_dedup_remap_types() by extracting its core logic into a new btf_remap_types() helper function. This eliminates code duplication and improves modularity while maintaining the same functionality. The new function encapsulates iteration over BTF types and BTF ext sections, accepting a callback for flexible type ID remapping. This makes the type remapping logic more maintainable and reusable. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng Reviewed-by: Eduard Zingerman --- tools/lib/bpf/btf.c | 63 +++++++++++++++++---------------- tools/lib/bpf/libbpf_internal.h | 1 + 2 files changed, 33 insertions(+), 31 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 18907f0fcf9f..5e1c09b5dce8 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -3400,6 +3400,37 @@ int btf_ext__set_endianness(struct btf_ext *btf_ext,= enum btf_endianness endian) return 0; } =20 +static int btf_remap_types(struct btf *btf, struct btf_ext *btf_ext, + btf_remap_type_fn visit, void *ctx) +{ + int i, r; + + for (i =3D 0; i < btf->nr_types; i++) { + struct btf_type *t =3D btf_type_by_id(btf, btf->start_id + i); + struct btf_field_iter it; + __u32 *type_id; + + r =3D btf_field_iter_init(&it, t, BTF_FIELD_ITER_IDS); + if (r) + return r; + + while ((type_id =3D btf_field_iter_next(&it))) { + r =3D visit(type_id, ctx); + if (r) + return r; + } + } + + if (!btf_ext) + return 0; + + r =3D btf_ext_visit_type_ids(btf_ext, visit, ctx); + if (r) + return r; + + return 0; +} + struct btf_dedup; =20 static struct btf_dedup *btf_dedup_new(struct btf *btf, const struct btf_d= edup_opts *opts); @@ -5320,37 +5351,7 @@ static int btf_dedup_remap_type_id(__u32 *type_id, v= oid *ctx) */ static int btf_dedup_remap_types(struct btf_dedup *d) { - int i, r; - - for (i =3D 0; i < d->btf->nr_types; i++) { - struct btf_type *t =3D btf_type_by_id(d->btf, d->btf->start_id + i); - struct btf_field_iter it; - __u32 *type_id; - - r =3D btf_field_iter_init(&it, t, BTF_FIELD_ITER_IDS); - if (r) - return r; - - while ((type_id =3D btf_field_iter_next(&it))) { - __u32 resolved_id, new_id; - - resolved_id =3D resolve_type_id(d, *type_id); - new_id =3D d->hypot_map[resolved_id]; - if (new_id > BTF_MAX_NR_TYPES) - return -EINVAL; - - *type_id =3D new_id; - } - } - - if (!d->btf_ext) - return 0; - - r =3D btf_ext_visit_type_ids(d->btf_ext, btf_dedup_remap_type_id, d); - if (r) - return r; - - return 0; + return btf_remap_types(d->btf, d->btf_ext, btf_dedup_remap_type_id, d); } =20 /* diff --git a/tools/lib/bpf/libbpf_internal.h b/tools/lib/bpf/libbpf_interna= l.h index 35b2527bedec..b09d6163f5c3 100644 --- a/tools/lib/bpf/libbpf_internal.h +++ b/tools/lib/bpf/libbpf_internal.h @@ -582,6 +582,7 @@ int btf_ext_visit_type_ids(struct btf_ext *btf_ext, typ= e_id_visit_fn visit, void int btf_ext_visit_str_offs(struct btf_ext *btf_ext, str_off_visit_fn visit= , void *ctx); __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_n= ame, __u32 kind); +typedef int (*btf_remap_type_fn)(__u32 *type_id, void *ctx); =20 /* handle direct returned errors */ static inline int libbpf_err(int ret) --=20 2.34.1 From nobody Fri Dec 19 09:27:46 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 1C0C5329375 for ; Tue, 4 Nov 2025 13:40:47 +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=1762263649; cv=none; b=rtbJL5afIPG9V8m9h0fVLO7FwKjzhjqC3K6OsE7sR0hpJVP6KOpP3iZ/9XpkZFCbgqmAL0wwOT/7mfsB5A4MCH10a0PG9CQ+NPoLmBFcFx412RDj1K12z/A+ydd5fR1BEWfXag5RUjYUrim+/KZtJRbF/dm3S6Tl8mTCE3rlVI8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762263649; c=relaxed/simple; bh=sa1HxtYH0/eacZwbT2sndIG1i6ajxhbyuue/J9blO8k=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=QgvF3+t+O4gHFort7LEz6C06rUMz0CjQVvGtWtp26wdME4NiLrbRA13mnqoUgupsI3mB3SsizjzKSTHXdICDWu5k5P9msOPEH7/VZd6qhatT4uA/sGK/Wb4igjrLDOYEZ2R7EvIs477H6ptdVVBFBKOLHCWYH4IQKgLRgB7/MJ4= 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=IWXYA3cA; 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="IWXYA3cA" Received: by mail-pf1-f178.google.com with SMTP id d2e1a72fcca58-7ad1cd0db3bso576037b3a.1 for ; Tue, 04 Nov 2025 05:40:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762263647; x=1762868447; 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=DkgAadX906NxjuzkPoGZPIWqZ+t9g+NGVEVLREnfGtI=; b=IWXYA3cA6awmPshednZ+0PaiP+FqxD66hafF869r5S5Y5aItoOxBTvHPPDFWNAwlHm Qe3ej5vygdgeK2jYZO9N7nXkKrY1qV4tqKPDWCDAh5rWr+e26ulhcsrOb5qBEZALtJhX wcl30BNTXTE+esssmQ29GUUAH9vnp0OawgZ/+ctgMoAtf/xmyR+7scr5aW2rdLfxYqpk b6EJg5g1zBnAJG5Wr/0WidS/WMujPO5p/ikjADHH8ahfA4bq9FUiYsvInsnC8Sic0web jxJFy1C9T71jQmm8iV5UKbN75PcdvT8cwaZM0Cba1mjj0Ly7pELGmMnoerwbPE5gt9+3 +MXw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762263647; x=1762868447; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=DkgAadX906NxjuzkPoGZPIWqZ+t9g+NGVEVLREnfGtI=; b=o8Q455JiOx0pW97eVghmeH7g70lS48o/Qh0KYOiGtAaXmIJJZPZ8lM2ooIdXeb4JAo QrTxVvjP5X/jL2aTp+K8+ijSNLw0Wf46flXHWgsEw4S/PemIJ9LA6fauhusoXbfOu5dU doQ1spAEUuMmVf6/VW0kk6lp/W8NnfK14dKM6y24G+iw5ko98cCpAm6pJpuW3N/0RGHS +JmggUMx79MhQO1jdv8pWRPRxHPRvmwtcnY3eE0WPgQaRlHri6vnLViwRNLFcXqnAWfu srF4OJ1e+gnLXQbieBj+MN4JKbpRUQdcyVZR9XnoS238T6Mf/7aUmxcGcT7DI7rAp80B 8aLw== X-Gm-Message-State: AOJu0YzTq5NGiMVTyOfcJwgz0loe7W2ES+lmDT9F43ukH7hg/+pPIXml 9NghpN86Y2SiTwLWMNbw5TButHApEQTw8LKyafye9YCOHCk7LZwl00Cz X-Gm-Gg: ASbGnctMtO5l7rA7WVJfbIGBE4INkTgOFm1JobR3T1SA+YsII47Wi3tRbhR2E616ZcS ggziJ+8NbVLgPA9ivrdU+FPWyh5muxGU+P3WYgV/R4+ta8KD9zazAeJf2TBXJoSjEcM7y0fwHsK WBhAHUp7Os3LPWlCl7h0dmyKXibnXLBDnC397DonlK+hhSdMS8lZxljUTAgnWKJ3bgQuzN3VDA8 8l0yKiTR5IrW/U8Q+E8XnrlrsHavnIRrYNPnexGIQM8THOthDZ7o80WYYOJvJ9VQVgnRyHwdTod EoT2oKIb1VpR5nBHutZmKrRZzEEaTG+JzX6u6zfeWfMkVKhQwU0gwY0sbPNTfl3fLVQR8zyaVM7 0cZtEPmIh5axQMtyxEqT7vmYBnkpr7rjHB7OGtJ1HLwCJDyPhsJkJ6yO4az/bvtnqBu2hiRZF3d /S4r0mv+24I0TCQbci X-Google-Smtp-Source: AGHT+IGvrZ0IfTiFVGGZzy9AqFylOrJxoiLe+/NaJrwhGcWgVZ3B+6sZXWpvKl0Du/8Blex1JSR1gw== X-Received: by 2002:a05:6a20:12c3:b0:343:1f71:8179 with SMTP id adf61e73a8af0-348cbda9931mr22173044637.35.1762263647423; Tue, 04 Nov 2025 05:40:47 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-ba1f87a7287sm2499238a12.31.2025.11.04.05.40.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 04 Nov 2025 05:40:46 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Eduard Zingerman , Andrii Nakryiko , Alan Maguire , Song Liu , pengdonglin Subject: [RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering Date: Tue, 4 Nov 2025 21:40:28 +0800 Message-Id: <20251104134033.344807-3-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251104134033.344807-1-dolinux.peng@gmail.com> References: <20251104134033.344807-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. The permutation process involves: 1. Shuffling types into new order based on the provided ID mapping 2. Remapping all type ID references to point to new locations 3. Handling BTF extension data if provided via options This is particularly useful for optimizing type locality after BTF deduplication or for meeting specific layout requirements in specialized use cases. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng Acked-by: Eduard Zingerman --- tools/lib/bpf/btf.c | 161 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 34 +++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 196 insertions(+) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 5e1c09b5dce8..3bc03f7fe31f 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -5830,3 +5830,164 @@ int btf__relocate(struct btf *btf, const struct btf= *base_btf) btf->owns_base =3D false; return libbpf_err(err); } + +struct btf_permute { + /* .BTF section to be permuted in-place */ + struct btf *btf; + struct btf_ext *btf_ext; + /* Array of type IDs used for permutation. The array length must equal + * the number of types in the BTF being permuted, excluding the special + * void type at ID 0. For split BTF, the length corresponds to the + * number of types added on top of the base BTF. + */ + __u32 *ids; + /* Array of type IDs used to map from original type ID to a new permuted + * type ID, its length equals to the above ids */ + __u32 *map; +}; + +static int btf_permute_shuffle_types(struct btf_permute *p); +static int btf_permute_remap_types(struct btf_permute *p); +static int btf_permute_remap_type_id(__u32 *type_id, void *ctx); + +int btf__permute(struct btf *btf, __u32 *ids, const struct btf_permute_opt= s *opts) +{ + struct btf_permute p; + int i, err =3D 0; + __u32 *map =3D NULL; + + if (!OPTS_VALID(opts, btf_permute_opts) || !ids) + return libbpf_err(-EINVAL); + + map =3D calloc(btf->nr_types, sizeof(*map)); + if (!map) { + err =3D -ENOMEM; + goto done; + } + + for (i =3D 0; i < btf->nr_types; i++) + map[i] =3D BTF_UNPROCESSED_ID; + + p.btf =3D btf; + p.btf_ext =3D OPTS_GET(opts, btf_ext, NULL); + p.ids =3D ids; + p.map =3D map; + + if (btf_ensure_modifiable(btf)) { + err =3D -ENOMEM; + goto done; + } + err =3D btf_permute_shuffle_types(&p); + if (err < 0) { + pr_debug("btf_permute_shuffle_types failed: %s\n", errstr(err)); + goto done; + } + err =3D btf_permute_remap_types(&p); + if (err < 0) { + pr_debug("btf_permute_remap_types failed: %s\n", errstr(err)); + goto done; + } + +done: + free(map); + return libbpf_err(err); +} + +/* Shuffle BTF types. + * + * Rearranges types according to the permutation map in p->ids. The p->map + * array stores the mapping from original type IDs to new shuffled IDs, + * which is used in the next phase to update type references. + * + * Validates that all IDs in the permutation array are valid and unique. + */ +static int btf_permute_shuffle_types(struct btf_permute *p) +{ + struct btf *btf =3D p->btf; + const struct btf_type *t; + __u32 *new_offs =3D NULL, *map; + void *nt, *new_types =3D NULL; + int i, id, len, err; + + new_offs =3D calloc(btf->nr_types, sizeof(*new_offs)); + new_types =3D calloc(btf->hdr->type_len, 1); + if (!new_offs || !new_types) { + err =3D -ENOMEM; + goto out_err; + } + + nt =3D new_types; + for (i =3D 0; i < btf->nr_types; i++) { + id =3D p->ids[i]; + /* type IDs from base_btf and the VOID type are not allowed */ + if (id < btf->start_id) { + err =3D -EINVAL; + goto out_err; + } + /* must be a valid type ID */ + t =3D btf__type_by_id(btf, id); + if (!t) { + err =3D -EINVAL; + goto out_err; + } + map =3D &p->map[id - btf->start_id]; + /* duplicate type IDs are not allowed */ + if (*map !=3D BTF_UNPROCESSED_ID) { + err =3D -EINVAL; + goto out_err; + } + len =3D btf_type_size(t); + memcpy(nt, t, len); + new_offs[i] =3D nt - new_types; + *map =3D btf->start_id + i; + nt +=3D len; + } + + free(btf->types_data); + free(btf->type_offs); + btf->types_data =3D new_types; + btf->type_offs =3D new_offs; + return 0; + +out_err: + free(new_offs); + free(new_types); + return err; +} + +/* Callback function to remap individual type ID references + * + * This callback is invoked by btf_remap_types() for each type ID reference + * found in the BTF data. It updates the reference to point to the new + * permuted type ID using the mapping table. + */ +static int btf_permute_remap_type_id(__u32 *type_id, void *ctx) +{ + struct btf_permute *p =3D ctx; + __u32 new_type_id =3D *type_id; + + /* skip references that point into the base BTF */ + if (new_type_id < p->btf->start_id) + return 0; + + new_type_id =3D p->map[*type_id - p->btf->start_id]; + if (new_type_id > BTF_MAX_NR_TYPES) + return -EINVAL; + + *type_id =3D new_type_id; + return 0; +} + +/* Remap referenced type IDs into permuted type IDs. + * + * After BTF types are permuted, their final type IDs may differ from orig= inal + * ones. The map from original to a corresponding permuted type ID is stor= ed + * in btf_permute->map and is populated during shuffle phase. During remap= ping + * phase we are rewriting all type IDs referenced from any BTF type (e.g., + * struct fields, func proto args, etc) to their final deduped type IDs. + */ +static int btf_permute_remap_types(struct btf_permute *p) +{ + return btf_remap_types(p->btf, p->btf_ext, btf_permute_remap_type_id, p); +} + diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h index ccfd905f03df..441f6445d762 100644 --- a/tools/lib/bpf/btf.h +++ b/tools/lib/bpf/btf.h @@ -273,6 +273,40 @@ 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()** rearranges BTF types in-place according to sp= ecified mapping + * @param btf BTF object to permute + * @param ids Array defining new type order. Must contain exactly btf->nr_= types elements, + * each being a valid type ID in range [btf->start_id, btf->start_i= d + btf->nr_types - 1] + * @param opts Optional parameters, including BTF extension data for refer= ence updates + * @return 0 on success, negative error code on failure + * + * **btf__permute()** performs an in-place permutation of BTF types, rearr= anging them + * according to the order specified in @p ids array. After reordering, all= type references + * within the BTF data and optional BTF extension are updated to maintain = consistency. + * + * The permutation process consists of two phases: + * 1. Type shuffling: Physical reordering of type data in memory + * 2. Reference remapping: Updating all type ID references to new locations + * + * This is particularly useful for optimizing type locality after BTF dedu= plication + * or for meeting specific layout requirements in specialized use cases. + * + * On error, negative error code is returned and errno is set appropriatel= y. + * Common error codes include: + * - -EINVAL: Invalid parameters or invalid ID mapping (e.g., duplicate = IDs, out-of-range IDs) + * - -ENOMEM: Memory allocation failure during permutation process + */ +LIBBPF_API int btf__permute(struct btf *btf, __u32 *ids, 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 Fri Dec 19 09:27:46 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 C47C332939C for ; Tue, 4 Nov 2025 13:40:51 +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=1762263653; cv=none; b=Za7q2VI9uhXTo0DGeAjDZLwmislRKuw9gZSsDq8OKHClfzINPIcJ/ad64qAvfoQEIuEB/9xbge6rLILgKw2Nw8dsBzd17BsfMzmJnDwtLuEAwrV4MhEr7iAlVyuJoqaHkS9jE4bUlM6nhrL24Pm5iJRe++COGnLsbvWQ+w9cUjA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762263653; c=relaxed/simple; bh=H8W7FunBp7qoGcxg5bGEeewgRaf3u8ILn6elRUcxoyk=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Y6EyvISrDUqCtYA05RHGp+0e2nSZbViVUZ3L4mj3/iRsW5p93EeB3J4LsSle4KHYG7zhlFewHvEBtLsimTFVDxvkK+Tk+uvwuA7yQKBQvZgXhb0fR4fObafHuRjHJzQI5TpGLcKX9D7X7kwq+XswXX+kpIvtTbx0GG+PM6iCZic= 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=fp8EC5DM; 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="fp8EC5DM" Received: by mail-pf1-f180.google.com with SMTP id d2e1a72fcca58-7a9cdf62d31so3509470b3a.3 for ; Tue, 04 Nov 2025 05:40:51 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762263651; x=1762868451; 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=/NsrgOo4ocG/4BxsQgHROI9+0LDTBXUxvTM9Wy/6b6g=; b=fp8EC5DMdVWJEAgeGKsN9e4KRYvc45KgxM/19sd3yhrebHWvucqSHU6M6SK3xd3GKA wwWMn0XcSHFAX8BitOoPsoX1zcg+Vp/MuCpuUcXTyHqkXkG3LeGueS3WTmuNlvR8k6Vr BKUbFjallSFBgszlDxxddjOLH0OSXF14PQnH6ArcT+W8JTCnTFY6PkNC8jYPMWqOT6CA QcmQXDmbT+Lug4sQZVA/b1f+YHWyGyNRLttNVbSNfOHixeUr8phuH4BTD3WIuk+Zblgs S83jyniCx40JoIWveT9bXnLZJeHOLhByUwT1l6eQD4cQy1zN9erPk8lJcCHggI46eAHF oBvg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762263651; x=1762868451; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=/NsrgOo4ocG/4BxsQgHROI9+0LDTBXUxvTM9Wy/6b6g=; b=FeLtbLhVxYCRCmA1bywZhfboE/uuNCYCYoMQW2inmbWNJh1Uf+Ef1Wnar/7Ofa7AxQ b012VaRkT4rhnzQ0pjHvdnOUrGdAC5IudnIPyDyYOarupqQAmtlgnfaNpAID9Z/hq3Fm 5fy2EtEFfL0gI7G1JpKXS3dWP1Qt+xgm/8beR4elc6lFl4WzD5QITGcIoDC+NKSzzSTB obJ3qs+J/xWmVa7QBfsVbHVTRiCCls3hpQx8vWdRCBPn2adnMZ3/3tQmXryqfxLrS+77 XJaisJF80jzOnVtaCo1C3vHRF4djc2YS+fqQsZ8axC4GbrqANcRjTx4UMcmRlP92btjk nnIw== X-Gm-Message-State: AOJu0YwOfD6g+dizrJgra0KbgJXlxyXlHoemhbhZUEbB39o4aUostggI Tlzw6flCmGypqPvs7R8bV0MVMJ9Bnqi5HsBZliFXjkc1PlVff6ld6C6y X-Gm-Gg: ASbGnctwyL9OJXXRirsOhZVnd3nL12V7sTuWZTVKMXEL2FdYrl3k5nBXN0erydviEQ7 Lng8OnSjOSovcr35c/Tu0AwdR2F96qdEejF/aJuXVHgeVAUVOKBfoLAAnWzTsLbXybsW73i/M3P sOp58s9K3FKT10iYQ0hvkyVnmNyXjPeJS4bJbfK5lutX69Y4C8ID8MU/N1MRPtmNkh5q/Aw2TVt 9mUg+bh8hg3YgxPFcuNY3s1T/2DRX6v99w8KZWnjECrtduLuEcMP3i3mt4Xa0BoGJhze3RB4LSn Xnovo+cfZ6541r0F8Gzmi9x5/a56BmjytshqO1xzky3n2PvHIctOLy3E7Hh/lbto+hndODZRGyB rODv/VoTXe26Jug6XsMdwnhiVZIP+bNUTmd8EiPB9Wg9ZwH7IcWyzawgRvQUe9iq2cH04obKLvf l/rQK6MKLumn8YekK9 X-Google-Smtp-Source: AGHT+IF0jGd0yl4ZUQ5poLvNggv7g7BAW0tkkkPqmp6n4W4vlSXsBr2+elxUCoxY1RlLNu9+9K8/Zw== X-Received: by 2002:a05:6a20:9151:b0:344:b429:fc64 with SMTP id adf61e73a8af0-348ccbfb900mr22350595637.50.1762263650965; Tue, 04 Nov 2025 05:40:50 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-ba1f87a7287sm2499238a12.31.2025.11.04.05.40.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 04 Nov 2025 05:40:49 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Eduard Zingerman , Andrii Nakryiko , Alan Maguire , Song Liu , pengdonglin Subject: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF Date: Tue, 4 Nov 2025 21:40:29 +0800 Message-Id: <20251104134033.344807-4-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251104134033.344807-1-dolinux.peng@gmail.com> References: <20251104134033.344807-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 type names. For unsorted BTF or when nr_sorted_types is zero, the implementation falls back to the original linear search algorithm. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 142 +++++++++++++++++++++++++++++++++++++------- 1 file changed, 119 insertions(+), 23 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 3bc03f7fe31f..5af14304409c 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -92,6 +92,12 @@ struct btf { * - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; + /* number of sorted and named types in this BTF instance: + * - doesn't include special [0] void type; + * - for split BTF counts number of sorted and named types added on + * top of base BTF. + */ + __u32 nr_sorted_types; /* if not NULL, points to the base BTF on top of which the current * split BTF is based */ @@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 t= ype_id) return type_id; } =20 -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +/* + * Find BTF types with matching names within the [left, right] index range. + * On success, updates *left and *right to the boundaries of the matching = range + * and returns the leftmost matching index. + */ +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const ch= ar *name, + __s32 *left, __s32 *right) { - __u32 i, nr_types =3D btf__type_cnt(btf); + const struct btf_type *t; + const char *tname; + __s32 l, r, m, lmost, rmost; + int ret; + + /* found the leftmost btf_type that matches */ + l =3D *left; + r =3D *right; + lmost =3D -1; + 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 - if (!strcmp(type_name, "void")) - return 0; + if (lmost =3D=3D -1) + return -ENOENT; + + /* found the rightmost btf_type that matches */ + l =3D lmost; + r =3D *right; + rmost =3D -1; + 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 <=3D 0) { + if (ret =3D=3D 0) + rmost =3D m; + l =3D m + 1; + } else { + r =3D m - 1; + } + } =20 - for (i =3D 1; i < nr_types; i++) { - const struct btf_type *t =3D btf__type_by_id(btf, i); - const char *name =3D btf__name_by_offset(btf, t->name_off); + *left =3D lmost; + *right =3D rmost; + return lmost; +} + +static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_i= d, + const char *type_name, __u32 kind) +{ + const struct btf_type *t; + const char *tname; + int err =3D -ENOENT; =20 - if (name && !strcmp(type_name, name)) - return i; + if (!btf) + goto out; + + if (start_id < btf->start_id) { + err =3D btf_find_type_by_name_kind(btf->base_btf, start_id, + type_name, kind); + if (err =3D=3D -ENOENT) + start_id =3D btf->start_id; + } + + if (err =3D=3D -ENOENT) { + if (btf->nr_sorted_types) { + /* binary search */ + __s32 l, r; + int ret; + + l =3D start_id; + r =3D start_id + btf->nr_sorted_types - 1; + ret =3D btf_find_type_by_name_bsearch(btf, type_name, &l, &r); + if (ret < 0) + goto out; + /* return the leftmost with maching names and skip kind checking */ + if (kind =3D=3D -1) + return ret; + /* found the leftmost btf_type that matches */ + while (l <=3D r) { + t =3D btf_type_by_id(btf, l); + if (BTF_INFO_KIND(t->info) =3D=3D kind) + return l; + l++; + } + } else { + /* linear search */ + __u32 i, total; + + total =3D btf__type_cnt(btf); + for (i =3D start_id; i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (kind !=3D -1 && btf_kind(t) !=3D kind) + continue; + tname =3D btf__str_by_offset(btf, t->name_off); + if (tname && !strcmp(tname, type_name)) + return i; + } + } } =20 - return libbpf_err(-ENOENT); +out: + return err; } =20 static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id, const char *type_name, __u32 kind) { - __u32 i, nr_types =3D btf__type_cnt(btf); - if (kind =3D=3D BTF_KIND_UNKN || !strcmp(type_name, "void")) return 0; =20 - for (i =3D start_id; i < nr_types; i++) { - const struct btf_type *t =3D btf__type_by_id(btf, i); - const char *name; - - if (btf_kind(t) !=3D kind) - continue; - name =3D btf__name_by_offset(btf, t->name_off); - if (name && !strcmp(type_name, name)) - return i; - } + return libbpf_err(btf_find_type_by_name_kind(btf, start_id, type_name, ki= nd)); +} =20 - return libbpf_err(-ENOENT); +/* the kind value of -1 indicates that kind matching should be skipped */ +__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +{ + return btf_find_by_name_kind(btf, btf->start_id, type_name, -1); } =20 __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_n= ame, --=20 2.34.1 From nobody Fri Dec 19 09:27:46 2025 Received: from mail-pg1-f180.google.com (mail-pg1-f180.google.com [209.85.215.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 1A4C7329C74 for ; Tue, 4 Nov 2025 13:40:54 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762263657; cv=none; b=MV2Ru8SeYT2eUSKza/jgrbX0B0uUYJYpETDK/j8W28+GDkBpFxa37hp9EgDYfghaoHvhpwRL9Qa8ZUPmhDOGMMhEnuJt9iHWK4/tU+admiFBCjMofMkZcd4MIZWGX4dkwdbgsEnlSEzkfZCGywLqrNew1Oy0CYzpedTGrZeqkFE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762263657; c=relaxed/simple; bh=sxhDvggn+kURFLHnP4sKqmyF/xkAhbHmgqNm1FXnJ04=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=hLGb5P5XPZpHBPtD57BZBsUoZsk2+HzCpMKsK7oVnUkZpFcrIq+cyQXzpXNG+G8kxHSqP+3pcfJAOXRJ7pmZ0eHG5KNhci1QxFNKsmoQlENPdcT5hhjUVMcq6LMCkf61+ZhqE6C+ge/U2CuaVv5c4+roE4pZJ++XhEePG+E47p8= 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=QPGPL81c; arc=none smtp.client-ip=209.85.215.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="QPGPL81c" Received: by mail-pg1-f180.google.com with SMTP id 41be03b00d2f7-b6271ea3a6fso3912701a12.0 for ; Tue, 04 Nov 2025 05:40:54 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762263654; x=1762868454; 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=szWsdlIxdc1yPzeQJecGUmp1yECxwvwFo0ocAR3RlqM=; b=QPGPL81cbuiy+9SiLxmDtznC56agh7ujp0MiqXt42qkDiRmOtWUfJ45bXPYKl9ADqf AOaeY/IM9pth1h1LM7geGaRm0DMdy98V4+j2m7700BFSodq9cvL2SLkwKm/nyfoZJdLu oQh7RwL20ZI28en42FA1eTMhFXYTeK0Vr5wyQCkg00baInGa7gK5bqIWbzpI+YVZz/7s 6xAAtxFhhkThy0pHTeeJDZxWYB/VR4IxtQL+gIXLwEX4srjSCtg2RK9+2mCI5YRiBaFS 1a0FqVia99MblNzzXyq/sQvOjF5AXGhro04oYtThWBPdrH1KiBlyIOjDfc8m8mgsVRFJ ocXA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762263654; x=1762868454; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=szWsdlIxdc1yPzeQJecGUmp1yECxwvwFo0ocAR3RlqM=; b=v5Mg0MfzGNc2t6gr7YTxRekbD9K4yGWoXHoV7izwPAr3r0EHJKu20cX7fz2bZcRjZD A/goaS2pgLOwYVNKAkgMYYcSwBkAIwS93zNiVVm1VxU6uFqBK9JEY0hkhFvhELdfacPT EMM/P2Itllxbc+poUvNkzEQGzhynvxMwot1jakKJfPF9ZYdC8dgxr1EWwUpbHW6Z+pJx AoVbDDU5Y3nsJ2rlrZ29p/x1lHxSREsZYKqepQ6JPthcNDL/bdotq/yl9VeKhwaYaTvw hJr+ie+x85HjfdWSf/W8BgPSKSDJgCT2/S5/x+js6Q/ULQYtBcltiUpDCPdpJbs6sQG0 7i+g== X-Gm-Message-State: AOJu0Yzt/aTIc3O8sDj8FSfHt/7URqk6Oi6N/ze1PVmRGk//6nCz6SHL 1PQFojVy89cTxJeKxaft9QspueMYhqiPBy8oBaDbba5P3qL4RHQ1pwo9 X-Gm-Gg: ASbGncsrOpwAu1uBeVt6xVZGGkwbtH9g4tcW7cziP73bvAZafcNYiSWJ58i2X9Zqm3f RoaiVOaVgmFIRLLtwdUHTw7ZXPtFX8wurL3+0SptJwc30Y234ErD8DGrgrWy1Bv8bheYdNB8bSH K5muIbF4strdeVs/gK/A+v5LdOs2Zz3ENnTlvCEqezN+OX5nv4eMDIWtEqIaqzczyWEeV3FVPid 7dVBrDCKILVT6mPHHwP4v9BQom9IN/oqmXswi4o2ezBNmYo5e6Y4k6cAkhu/UtOzli91xuLpw23 1Vq6JDcxXzdNtWBmGzwfqXUiyl0JPGAJ/8PDy+tv3ThbKPdnAcYjF6KtuEsVaReUSx2xBJRExZL tolQcJQaNxOSC2dCPOikQDXGo0sEuucGAZZthTHYhf8kFnbTiqyQoPVLxukHhGtciJdurB5iskw NNktiJ4KIF2zj3DQ2rNBbnutFkHPE= X-Google-Smtp-Source: AGHT+IEqF1jp4cNM46whY+LqclZi/gWKtV/lCipaPe3oBTE3vhRYzKy2GK56YTcG8sUGG+WVznMFEw== X-Received: by 2002:a05:6a20:3d8e:b0:342:9cb7:64a3 with SMTP id adf61e73a8af0-348cbda9bc9mr22112291637.34.1762263654453; Tue, 04 Nov 2025 05:40:54 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-ba1f87a7287sm2499238a12.31.2025.11.04.05.40.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 04 Nov 2025 05:40:53 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Eduard Zingerman , Andrii Nakryiko , Alan Maguire , Song Liu , pengdonglin Subject: [RFC PATCH v4 4/7] libbpf: Implement lazy sorting validation for binary search optimization Date: Tue, 4 Nov 2025 21:40:30 +0800 Message-Id: <20251104134033.344807-5-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251104134033.344807-1-dolinux.peng@gmail.com> References: <20251104134033.344807-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 adds lazy validation of BTF type ordering to determine if types are sorted by name. The check is performed on first access and cached, enabling efficient binary search for sorted BTF while maintaining linear search fallback for unsorted cases. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 76 +++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 74 insertions(+), 2 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 5af14304409c..0ee00cec5c05 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -26,6 +26,10 @@ =20 #define BTF_MAX_NR_TYPES 0x7fffffffU #define BTF_MAX_STR_OFFSET 0x7fffffffU +/* sort verification occurs lazily upon first btf_find_type_by_name_kind() + * call + */ +#define BTF_NEED_SORT_CHECK ((__u32)-1) =20 static struct btf_type btf_void; =20 @@ -96,6 +100,10 @@ struct btf { * - doesn't include special [0] void type; * - for split BTF counts number of sorted and named types added on * top of base BTF. + * - BTF_NEED_SORT_CHECK value indicates sort validation will be perfor= med + * on first call to btf_find_type_by_name_kind. + * - zero value indicates applied sorting check with unsorted BTF or no + * named types. */ __u32 nr_sorted_types; /* if not NULL, points to the base BTF on top of which the current @@ -903,8 +911,67 @@ int btf__resolve_type(const struct btf *btf, __u32 typ= e_id) return type_id; } =20 -/* - * Find BTF types with matching names within the [left, right] index range. +static int btf_compare_type_names(const void *a, const void *b, void *priv) +{ + struct btf *btf =3D (struct btf *)priv; + struct btf_type *ta =3D btf_type_by_id(btf, *(__u32 *)a); + struct btf_type *tb =3D btf_type_by_id(btf, *(__u32 *)b); + const char *na, *nb; + bool anon_a, anon_b; + + na =3D btf__str_by_offset(btf, ta->name_off); + nb =3D btf__str_by_offset(btf, tb->name_off); + anon_a =3D str_is_empty(na); + anon_b =3D str_is_empty(nb); + + if (anon_a && !anon_b) + return 1; + if (!anon_a && anon_b) + return -1; + if (anon_a && anon_b) + return 0; + + return strcmp(na, nb); +} + +/* Verifies BTF type ordering by name and counts named types. + * + * Checks that types are sorted in ascending order with named types + * before anonymous ones. If verified, sets nr_sorted_types to the + * number of named types. + */ +static void btf_check_sorted(struct btf *btf, int start_id) +{ + const struct btf_type *t; + int i, n, nr_sorted_types; + + if (likely(btf->nr_sorted_types !=3D BTF_NEED_SORT_CHECK)) + return; + btf->nr_sorted_types =3D 0; + + if (btf->nr_types < 2) + return; + + nr_sorted_types =3D 0; + n =3D btf__type_cnt(btf); + for (n--, i =3D start_id; i < n; i++) { + int k =3D i + 1; + + if (btf_compare_type_names(&i, &k, btf) > 0) + return; + t =3D btf_type_by_id(btf, k); + if (!str_is_empty(btf__str_by_offset(btf, t->name_off))) + nr_sorted_types++; + } + + t =3D btf_type_by_id(btf, start_id); + if (!str_is_empty(btf__str_by_offset(btf, t->name_off))) + nr_sorted_types++; + if (nr_sorted_types) + btf->nr_sorted_types =3D nr_sorted_types; +} + +/* Find BTF types with matching names within the [left, right] index range. * On success, updates *left and *right to the boundaries of the matching = range * and returns the leftmost matching index. */ @@ -978,6 +1045,8 @@ static __s32 btf_find_type_by_name_kind(const struct b= tf *btf, int start_id, } =20 if (err =3D=3D -ENOENT) { + btf_check_sorted((struct btf *)btf, btf->start_id); + if (btf->nr_sorted_types) { /* binary search */ __s32 l, r; @@ -1102,6 +1171,7 @@ static struct btf *btf_new_empty(struct btf *base_btf) btf->fd =3D -1; btf->ptr_sz =3D sizeof(void *); btf->swapped_endian =3D false; + btf->nr_sorted_types =3D BTF_NEED_SORT_CHECK; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1153,6 +1223,7 @@ static struct btf *btf_new(const void *data, __u32 si= ze, struct btf *base_btf, b btf->start_id =3D 1; btf->start_str_off =3D 0; btf->fd =3D -1; + btf->nr_sorted_types =3D BTF_NEED_SORT_CHECK; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1811,6 +1882,7 @@ static void btf_invalidate_raw_data(struct btf *btf) free(btf->raw_data_swapped); btf->raw_data_swapped =3D NULL; } + btf->nr_sorted_types =3D BTF_NEED_SORT_CHECK; } =20 /* Ensure BTF is ready to be modified (by splitting into a three memory --=20 2.34.1 From nobody Fri Dec 19 09:27:46 2025 Received: from mail-pj1-f44.google.com (mail-pj1-f44.google.com [209.85.216.44]) (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 B0A47329E5F for ; Tue, 4 Nov 2025 13:40:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.44 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762263660; cv=none; b=ZhvZeywIIe3Te1LrS7a1i154KHFAGXpgXI5mXQkfCZfhzKxHpI+PyD7AWgksNes0olLuPhNlF7adJxGIHrtCLbOMDKXfwnGV/LIpourAUvJxlXFvJrHIBckcC6EiQCVy7fdiBmb9B/L4jhL5WJN7Cp79TLOiWBfkRwAX5sYuOYM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762263660; c=relaxed/simple; bh=O6TUJSSCk6Hrp9bJcJkRtQGi3MrZ6klrSIFDZ+Yqcj0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=nKHYaeY3Gnd565tof1gKukN+TLoNN6bnnrEUzc5QKwj3OQ/0D444HFaQNgPGSpOWFTXouLuHHphFSAsCYk7lDUlq/vt5BYU86t/tXl/bM4ex+yysD2Mrh4zC5EoVbHXGDK7ObSNL1SwymH7/abYH+JTjwfHFeoG/J1uhd0ht1fo= 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=dsyeWg5v; arc=none smtp.client-ip=209.85.216.44 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="dsyeWg5v" Received: by mail-pj1-f44.google.com with SMTP id 98e67ed59e1d1-340c680fe8cso2742104a91.0 for ; Tue, 04 Nov 2025 05:40:58 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762263658; x=1762868458; 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=jdH6dhdE/ct/5KpUEPIcc/WirZeO6VXg0US4f0SIffI=; b=dsyeWg5vESLqY1C4wf6DCQ7X2SnLnEJarGtvpuW90ZzO9DvG6Gb+dGTHcST3+aukXE mbrZHcutLkA2PMAfTDtWQqsRakc2aMA0XzofDw8I2plGkOQcVeRBrG4xrTG7nIuP6S+T vOfZMs2+e6vwaNowi/sJm6o5Tr9zqZm7npGtxFnMqrEFuDrMGuFYEuAgaiWlx/XvzTDO vw+SgTk9d+wxyP7VVWaSG8G7+TzsczYjBShbLvHyPt8QV+7M3c/Y9oPnL6oHyqmIeioM 9GLyqQP4rPlwGgvgX1bluEQCL5632H8JPuXHeQY7He3K4c1GNk1yoenByUVSObwAxSiB 1S4w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762263658; x=1762868458; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=jdH6dhdE/ct/5KpUEPIcc/WirZeO6VXg0US4f0SIffI=; b=cBGOaKbDyqIdNad47rppCkQXRRkRbZALNpIEjO+gjP2zpn8aTuC+Zcr2xgbaLaAbhi w27ahgC1XpbVWenMnIzY6w/mATN6EzRMTbUK8+HEPoiQWCXjFItsmrP8h4+4DYjGXtdT Sybi21/IYm0eHj2GAG4OUrTd4HYBky5IiCGx9rfV4u6fGwfNJ7ICL4JOTgqS82qj9+6r 7p2uEN4INFYyayUtdqtyyvRq7PFKTsl51cjptBwSpTn/Z6FUAHjWmf+yLb7KfOM7og8h EAkQlsac87w+u9y7Nkv2ZBsHWFF/l41neI6F925LAJWIqMcETMWmimtDCaEw+/Bpcm8G Qf+g== X-Gm-Message-State: AOJu0YyUJWCQOx4PSRROW5KY93XAmUX0fqRyfr1Mu1RXkCMd13OKmikf a5ETjPfD2tIBMuqqe2QmbVF5yGYYVba+ERCxKX4MuO7s+T21JvU5ca+E X-Gm-Gg: ASbGncuK5PORowMlPJoBMC0XZZipMaOYEVgJmz0l70oo7w3WrBnq6VLUVEqF3YPK24m 9CaUkf4Mre74dwyfdmqbYwki860gE29WTKJzh+biCbT/SvSMAPaaiIunLZ1UWyx5aqqcjm0HOpq HNtrylkfpP5yLjQLQf0uLxpRIQhBfDRrFdxAkkHBNQ+KvMRH6VoNzo8kY/8eLUuQ8Nf3VpYoaie Lr4mX0MXWcPQsU8U3Zjl+CgY3n+TgZv7vaLAJ64kQoqFL50ScRAwspwHNzRBahOHPprkaqx8pac iHnI/vP6BMG9dfZW7AAS2OuUaFIHD++lqN9zHg2iF8ceVdiYc4lTfHBYHAkFO/M6rJT+T2i+n/T Mje3l49ivT2M96SQFmdfxqBx5mQfiA5AouYpHCX5g6UA9oRJ7yuUR67x1mRS1kxtyjxhRrIIxpq kaTAe/u//QwqKbNN1+ X-Google-Smtp-Source: AGHT+IG4CexyTG0Va7f3enA8yUQx0oRFu4DeDd1sF7PSgO2tkGhxl3YEWxrzB4hWgbdaNFwN/l7fMw== X-Received: by 2002:a17:90b:5104:b0:341:88c9:6eb2 with SMTP id 98e67ed59e1d1-34188c96eb7mr1911737a91.1.1762263658014; Tue, 04 Nov 2025 05:40:58 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-ba1f87a7287sm2499238a12.31.2025.11.04.05.40.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 04 Nov 2025 05:40:56 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Eduard Zingerman , Andrii Nakryiko , Alan Maguire , Song Liu , pengdonglin Subject: [RFC PATCH v4 5/7] btf: Optimize type lookup with binary search Date: Tue, 4 Nov 2025 21:40:31 +0800 Message-Id: <20251104134033.344807-6-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251104134033.344807-1-dolinux.peng@gmail.com> References: <20251104134033.344807-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: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- kernel/bpf/btf.c | 111 ++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 101 insertions(+), 10 deletions(-) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 0de8fc8a0e0b..da35d8636b9b 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -259,6 +259,7 @@ struct btf { void *nohdr_data; struct btf_header hdr; u32 nr_types; /* includes VOID for base BTF */ + u32 nr_sorted_types; /* exclude VOID for base BTF */ u32 types_size; u32 data_size; refcount_t refcnt; @@ -494,6 +495,11 @@ static bool btf_type_is_modifier(const struct btf_type= *t) return false; } =20 +static int btf_start_id(const struct btf *btf) +{ + return btf->start_id + (btf->base_btf ? 0 : 1); +} + bool btf_type_is_void(const struct btf_type *t) { return t =3D=3D &btf_void; @@ -544,24 +550,109 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 -s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) +/* Find BTF types with matching names within the [left, right] index range. + * On success, updates *left and *right to the boundaries of the matching = range + * and returns the leftmost matching index. + */ +static s32 btf_find_by_name_kind_bsearch(const struct btf *btf, const char= *name, + s32 *left, s32 *right) { const struct btf_type *t; const char *tname; - u32 i, total; + s32 l, r, m, lmost, rmost; + int ret; =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; + /* found the leftmost btf_type that matches */ + l =3D *left; + r =3D *right; + lmost =3D -1; + 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; + } + } =20 + if (lmost =3D=3D -1) + return -ENOENT; + + /* found the rightmost btf_type that matches */ + l =3D lmost; + r =3D *right; + rmost =3D -1; + while (l <=3D r) { + m =3D l + (r - l) / 2; + t =3D btf_type_by_id(btf, m); tname =3D btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; + ret =3D strcmp(tname, name); + if (ret <=3D 0) { + if (ret =3D=3D 0) + rmost =3D m; + l =3D m + 1; + } else { + r =3D m - 1; + } } =20 - return -ENOENT; + *left =3D lmost; + *right =3D rmost; + 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; + int err =3D -ENOENT; + + if (base_btf) + err =3D btf_find_by_name_kind(base_btf, name, kind); + + if (err =3D=3D -ENOENT) { + if (btf->nr_sorted_types) { + /* binary search */ + s32 l, r; + int ret; + + l =3D btf_start_id(btf); + r =3D l + btf->nr_sorted_types - 1; + ret =3D btf_find_by_name_kind_bsearch(btf, name, &l, &r); + if (ret < 0) + goto out; + /* found the leftmost btf_type that matches */ + while (l <=3D r) { + t =3D btf_type_by_id(btf, l); + if (BTF_INFO_KIND(t->info) =3D=3D kind) + return l; + l++; + } + } else { + /* linear search */ + u32 i, total; + + total =3D btf_nr_types(btf); + for (i =3D btf_start_id(btf); i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (BTF_INFO_KIND(t->info) !=3D kind) + continue; + + tname =3D btf_name_by_offset(btf, t->name_off); + if (!strcmp(tname, name)) + return i; + } + } + } + +out: + return err; } =20 s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p) --=20 2.34.1 From nobody Fri Dec 19 09:27:46 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 310AA329385 for ; Tue, 4 Nov 2025 13:41: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=1762263663; cv=none; b=ClDVqEFatxLtG5k/geQcV0NOUQNEmfurPoWA8Xqkfu5a+2tTMI5/5yRj5JH3dXCiNwrxXJdrStMnMozoFZ739CZU97wZG7ypUJOJaW9G3Bcb9314xISfGwjewRZCivOjMay8TxHKmM7FBevNcuyUhVC2nZwWUXFu9ovB/whSYGM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762263663; c=relaxed/simple; bh=YhPYNJZFXEH3DqLl890OXpoNt5wtfd9zUXgWwSlWmnU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=JNORkpAHg2CCZcDsEJ7tqd6ar6knyNYjYd5zTd1Wzy5YgZQeyw1O7oW8AV7YOx/oEDOhsdzLhVq7xa9YKNqYZHmk5NfzQyOsG6FEVglaaPypZzw3afzBhm7hBXwULTrwtrd4gjiC8jwBgoV2WsjppPyJgEs5zHf4ylYek5FqIas= 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=dfS5D4fc; 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="dfS5D4fc" Received: by mail-pf1-f174.google.com with SMTP id d2e1a72fcca58-77f67ba775aso6889486b3a.3 for ; Tue, 04 Nov 2025 05:41:02 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762263661; x=1762868461; 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=cyvKaozorZTBSzeG44mKs2zUGk0qFaFKA//27+I4xKM=; b=dfS5D4fcrgyqiSQdidiGLa61QLnTQsQJeSHCbxDYhtkwtYJnXOSxXPnJX0ECNB6tbZ kMpQ317Wz0ZxvhitZSXAQmFlJBMz2gQCKbtE2yckAXrqr/pkGhB8CRLe3m3hsgM3roD/ A9K6QWYkR0LhPm3/DAgY4VtleMVpxKImBPuiP15gXsoHiQesJdMMdSEM97xSuHhG6+qY Ie1D9u5XNh1a1WB5gLDKNh18Fb1uDhD1rpyI+tfI53H80gouXd7CGxC4+rIK3k/XHtPe Nh2lo4morJo3d/sXdtpC9gF8LrEjvLNMy89Iw6K+dUy2psRKyMIeAwdp9zDxRSi71vO5 UDKw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762263661; x=1762868461; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=cyvKaozorZTBSzeG44mKs2zUGk0qFaFKA//27+I4xKM=; b=HPfnLHHnkAZthBlZOEBo61eprSAtw3V1f/ivXDqKgsIKQ45G7BxvngF3gWHHNPXMjr 62gHeAzDEfCVhKSAo9KrMxVDhRwRcIohfxsmEG+c55TocjVSmMD01ZgFxlO5Nx7qH8N4 mjicl9w2tdS5pArywSYtd0dvRgx3fXLFKm9O/Pbt0C3R/cut3GWv3AeqRIZbNQcGX7r7 f2/KfrcgBtsaovB+ZFmORYgRKG5Y8CLDzXAUQYEP1yXEqoKziyhuhNrPsZPeuaNdqpcf yFVExZqr4iqnbCTux4a6+QkdwTY8FfPfeTiPZwcC+UKmrps3fPFvRLbH64cHlZ72kwJi 10Aw== X-Gm-Message-State: AOJu0YzySDpf+CAAB7kwJ/LyKmUd1+FHO/T9seFDxUY7G2GI8cUdUZNt ufGCalQDRqmOEGKaAqUqZbbbMkhtlUWjmmXu3YHbcgqMDEUyEk67OwIH X-Gm-Gg: ASbGncsN7ddq3DZvlDTnScMjUQvQRSpJ5sKcisR22Ra1g3btG+Ysy2pCva8U1qLXmqJ E/AWX/jR+cmSN5dwsA9jwfhZlJyvtHKbhT9us9re5sAdWVsBC+apY7/S0ARU5/P7xZ47aH5qfzv /mx5rt+m2PUfWI92aCi2/9zzCSzm7glBRrLDQC5DsF/9onjeRZbqDrBOqkFmHuEnG9X5ypegH6d WlXhc5j5a09XiNWePkibW46PpYIQVpHIUUfVPvQDK0CYy+JbPmbLmRvGG+X6LU1iT5sPT1PpDp1 uAk9pKiS6Zsb/DH+WmZZvWEKc24sXxVG8qiWnVYD8K95Ky+EHuhm0KslFoVpK11AbpnFbr7z4PH zsZ+jeHBqxtUK0DnZ+JIlygtpRi9ZEtMzLiFb6ZUWZSxZFDWncBJuSKVmXLPLdmVslhSk6+G2or s1KO2fRTZZbzihSLYB X-Google-Smtp-Source: AGHT+IH3DRVhPlh4emSZg1dm1+iTAic5V+qWeWDSQkHbTRONigJBsNgybx0L0pzSSZX0CG6cHLsNRg== X-Received: by 2002:a05:6a20:728a:b0:340:f36d:6b03 with SMTP id adf61e73a8af0-348ca15b031mr19019665637.9.1762263661522; Tue, 04 Nov 2025 05:41:01 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-ba1f87a7287sm2499238a12.31.2025.11.04.05.40.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 04 Nov 2025 05:41:00 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Eduard Zingerman , Andrii Nakryiko , Alan Maguire , Song Liu , pengdonglin Subject: [RFC PATCH v4 6/7] btf: Add lazy sorting validation for binary search Date: Tue, 4 Nov 2025 21:40:32 +0800 Message-Id: <20251104134033.344807-7-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251104134033.344807-1-dolinux.peng@gmail.com> References: <20251104134033.344807-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 Implement lazy validation of BTF type ordering to enable efficient binary search for sorted BTF while maintaining linear search fallback for unsorted cases. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- kernel/bpf/btf.c | 66 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index da35d8636b9b..c76d77fd30a7 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -192,6 +192,8 @@ */ #define BTF_MAX_SIZE (16 * 1024 * 1024) =20 +#define BTF_NEED_SORT_CHECK ((u32)-1) + #define for_each_member_from(i, from, struct_type, member) \ for (i =3D from, member =3D btf_type_member(struct_type) + from; \ i < btf_type_vlen(struct_type); \ @@ -550,6 +552,65 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +static int btf_compare_type_names(const void *a, const void *b, void *priv) +{ + struct btf *btf =3D (struct btf *)priv; + const struct btf_type *ta =3D btf_type_by_id(btf, *(__u32 *)a); + const struct btf_type *tb =3D btf_type_by_id(btf, *(__u32 *)b); + const char *na, *nb; + + if (!ta->name_off && tb->name_off) + return 1; + if (ta->name_off && !tb->name_off) + return -1; + if (!ta->name_off && !tb->name_off) + return 0; + + na =3D btf_name_by_offset(btf, ta->name_off); + nb =3D btf_name_by_offset(btf, tb->name_off); + return strcmp(na, nb); +} + +/* Verifies BTF type ordering by name and counts named types. + * + * Checks that types are sorted in ascending order with named types + * before anonymous ones. If verified, sets nr_sorted_types to the + * number of named types. + */ +static void btf_check_sorted(struct btf *btf, int start_id) +{ + const struct btf_type *t; + int i, n, nr_sorted_types; + + if (likely(btf->nr_sorted_types !=3D BTF_NEED_SORT_CHECK)) + return; + + btf->nr_sorted_types =3D 0; + + if (btf->nr_types < 2) + return; + + nr_sorted_types =3D 0; + n =3D btf_nr_types(btf); + for (n--, i =3D start_id; i < n; i++) { + int k =3D i + 1; + + if (btf_compare_type_names(&i, &k, btf) > 0) + return; + + t =3D btf_type_by_id(btf, k); + if (t->name_off) + nr_sorted_types++; + } + + t =3D btf_type_by_id(btf, start_id); + if (t->name_off) + nr_sorted_types++; + + if (nr_sorted_types) + btf->nr_sorted_types =3D nr_sorted_types; +} + /* Find BTF types with matching names within the [left, right] index range. * On success, updates *left and *right to the boundaries of the matching = range * and returns the leftmost matching index. @@ -617,6 +678,8 @@ s32 btf_find_by_name_kind(const struct btf *btf, const = char *name, u8 kind) err =3D btf_find_by_name_kind(base_btf, name, kind); =20 if (err =3D=3D -ENOENT) { + btf_check_sorted((struct btf *)btf, btf_start_id(btf)); + if (btf->nr_sorted_types) { /* binary search */ s32 l, r; @@ -5882,6 +5945,7 @@ static struct btf *btf_parse(const union bpf_attr *at= tr, bpfptr_t uattr, u32 uat goto errout; } env->btf =3D btf; + btf->nr_sorted_types =3D BTF_NEED_SORT_CHECK; =20 data =3D kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN); if (!data) { @@ -6301,6 +6365,7 @@ static struct btf *btf_parse_base(struct btf_verifier= _env *env, const char *name btf->data =3D data; btf->data_size =3D data_size; btf->kernel_btf =3D true; + btf->nr_sorted_types =3D BTF_NEED_SORT_CHECK; snprintf(btf->name, sizeof(btf->name), "%s", name); =20 err =3D btf_parse_hdr(env); @@ -6418,6 +6483,7 @@ static struct btf *btf_parse_module(const char *modul= e_name, const void *data, btf->start_id =3D base_btf->nr_types; btf->start_str_off =3D base_btf->hdr.str_len; btf->kernel_btf =3D true; + btf->nr_sorted_types =3D BTF_NEED_SORT_CHECK; 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 Fri Dec 19 09:27:46 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 E4E1932B9B4 for ; Tue, 4 Nov 2025 13:41:05 +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=1762263667; cv=none; b=Gj/l1ag1UACLumq8weFdMMJIL1B4ix2q5D+w57y9M6A0HqK/tb2d8UwJzlbXn9tm0Q1bk+1WKihSJRIWe6+zdQYGQg0m/uRAMntbabvsuxyzorReOO1w3CH4X+6EBBCx0CGvV3nLF02i+G1LfFNriModWOqSrn4Zs8w6OMyo8vM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762263667; c=relaxed/simple; bh=c1bDDCyExUmNe1HF4xwKZu77IBXLl0MUsBE8BWwSkww=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=u21JxQ/XKxbBi1jrQbtG8dKlRWytjYN+dRKg8fgCsUYf0Uo+ibNdpVSqB2FOWBMMlD10jaBTK8zXjjlft+zGThE6EOP4HwZYdMlWJcGTaXEi/mPFDN9i0sGckD8BEbf3zctFn0Oi9LemHFHG8OXUklDkJg9KApHJfsCM06ya/CA= 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=Jqtc6ou5; 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="Jqtc6ou5" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-294df925292so50419715ad.1 for ; Tue, 04 Nov 2025 05:41:05 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762263665; x=1762868465; 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=5zWSUJxMIOmC96LC4qtuVXdDyNI1GHx9xUdNCaZaj6k=; b=Jqtc6ou5Z2t/2zpzuQ1Tz/XOcuWqGA4VI1n8miVIwGuGBOJHnqSSmLNvDVA6dbA58v 9d0QnjZjJ6t/aitMvzyRloK2i0VRFbx1uYFopzOnx3IMQOt4cBdFphGbwvbNQYzZlOFz jSyGR8LSSmjLXMZbylH783zxxU8D53yBgV9QxGuqbx9/1b5l1qSdB/ucnqnYWboT+ZZb 14p/seKKyY/6DdFbSQKHMT46uEv3guj+gkAYvIDxYQ3S5qDqJvBLo2iN5yLtV4i4NNY2 Rqb9XnREiq6cQlMwtiUEwlay3d+Q6KA/Z4aL+GbI+frpaaV8K3EHnprvgutF9UD+8FS9 A3MQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762263665; x=1762868465; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=5zWSUJxMIOmC96LC4qtuVXdDyNI1GHx9xUdNCaZaj6k=; b=M7lRH6aDbnS6ObDT3GN++eS9UyM9bM0UFc3KNkd2vzQ8Fqak3vitrFf2xL2T03DK7z KGvWnTrl8jd+QD0ZY22tl86ywSQ+f/WGiECb0e1jXHM43hlvJI4iDEL6hIsFdQnvKGv3 qooVIUAEd5a4JuqhPmPyRCEQDra8ffhZAOfQVPVkA8dkO9qUqwhSqNI+BTz0pZlX00xu Eu3DOdXqZxNeCSCVSzfDelYTDMxi961GZZ/uygZv/Qw3jGQH0+1A33X1Rj7Vc3QZrWhd tGL+DoOeAfYvgc5r90C5SL9ZWLsHiCbesaYn8Q6x8PzpX+J60whhLBZY+tJ/qnoIjbPd +fLQ== X-Gm-Message-State: AOJu0YwlbiZrQrooktkvxmcrheZZR2U6YbhvENoM/5NLAP8rmTi/CS9L c/v6R8nAIYixAbu+f2F0rlx9qmfE6tPmyqT1QcX3lUouRYV+BBJlGTSj X-Gm-Gg: ASbGncsrUyqGtdMN/9hzkqMILmPoX1nOExDncgS31Iw6Y3GYGaGAMJauFxoyRSO60Ez l0EbdwpW2YSWyJ5yU0af6nYMMh30nRQrvIZM68mFK/N186oKi9h7X+/YjzSA7+XNmHyNGVvtfXm YS56lQfOFQdWde5FDpEuftlz7P6ihxHPenTPlpAb/SgR7bGBGbqnGG4+pfbcdqdfW6h86WyM4IU DHP/g5mAk0dvmgfpWy6zN4myYWmUXdLZQfzeRZRIee9TBCsw4SF3WU21jNCg0Nr/XwBHGpZoAKx bZ9veAHUa3FRwJKlWfrusC+9gHhTpZFJ5PhNwLrZsHknI9WzAaPCbko5zOCmjSv8+vJ/EeEd3IV HZcO/yZWYFZABo78tsMQuChjx5umUnR0XtP9EqsoEYXj1jTalPYkzME0HABM/l8wMdGjfY1pBjd 5j5hcjYHM9YvTFYFZKgf7C3UMQAcA= X-Google-Smtp-Source: AGHT+IFWF62hNdotUyJIPELOStgUzmKw7yokMkoh5O48MpCq4zaNJbwqAYZ/JVQjN9FFQ3u/A6ecug== X-Received: by 2002:a17:902:f542:b0:295:4d50:aab8 with SMTP id d9443c01a7336-2954d50ac7bmr166644705ad.24.1762263665091; Tue, 04 Nov 2025 05:41:05 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-ba1f87a7287sm2499238a12.31.2025.11.04.05.41.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 04 Nov 2025 05:41:04 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Eduard Zingerman , Andrii Nakryiko , Alan Maguire , Song Liu , pengdonglin Subject: [RFC PATCH v4 7/7] selftests/bpf: Add test cases for btf__permute functionality Date: Tue, 4 Nov 2025 21:40:33 +0800 Message-Id: <20251104134033.344807-8-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251104134033.344807-1-dolinux.peng@gmail.com> References: <20251104134033.344807-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 standalone BTF - test_permute_split: Tests permutation on split BTF with base dependencies Each test verifies that type IDs are correctly rearranged and type references are properly updated after permutation operations. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng Acked-by: Eduard Zingerman --- .../selftests/bpf/prog_tests/btf_permute.c | 142 ++++++++++++++++++ 1 file changed, 142 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..2692cef627ab --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/btf_permute.c @@ -0,0 +1,142 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2025 Xiaomi */ + +#include +#include +#include "btf_helpers.h" + +/* ensure btf__permute work as expected with base_btf */ +static void test_permute_base(void) +{ + struct btf *btf; + __u32 permute_ids[6]; + int err; + + btf =3D btf__new_empty(); + if (!ASSERT_OK_PTR(btf, "empty_main_btf")) + return; + + btf__add_int(btf, "int", 4, BTF_INT_SIGNED); /* [1] int */ + btf__add_ptr(btf, 1); /* [2] ptr to int */ + btf__add_struct(btf, "s1", 4); /* [3] struct s1 { */ + btf__add_field(btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_struct(btf, "s2", 4); /* [4] struct s2 { */ + btf__add_field(btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_func_proto(btf, 1); /* [5] int (*)(int *p); */ + btf__add_func_param(btf, "p", 2); + btf__add_func(btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); */ + + VALIDATE_RAW_BTF( + btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] FUNC 'f' type_id=3D5 linkage=3Dstatic"); + + permute_ids[0] =3D 4; /* struct s2 */ + permute_ids[1] =3D 3; /* struct s1 */ + permute_ids[2] =3D 5; /* int (*)(int *p) */ + permute_ids[3] =3D 1; /* int */ + permute_ids[4] =3D 6; /* int f(int *p) */ + permute_ids[5] =3D 2; /* ptr to int */ + err =3D btf__permute(btf, permute_ids, NULL); + if (!ASSERT_OK(err, "btf__permute")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[2] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[3] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D6", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[5] FUNC 'f' type_id=3D3 linkage=3Dstatic", + "[6] PTR '(anon)' type_id=3D4"); + +done: + btf__free(btf); +} + +/* ensure btf__permute work as expected with split_btf */ +static void test_permute_split(void) +{ + struct btf *split_btf =3D NULL, *base_btf =3D NULL; + __u32 permute_ids[4]; + int err; + + base_btf =3D btf__new_empty(); + if (!ASSERT_OK_PTR(base_btf, "empty_main_btf")) + return; + + btf__add_int(base_btf, "int", 4, BTF_INT_SIGNED); /* [1] int */ + btf__add_ptr(base_btf, 1); /* [2] ptr to int */ + VALIDATE_RAW_BTF( + base_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1"); + split_btf =3D btf__new_empty_split(base_btf); + if (!ASSERT_OK_PTR(split_btf, "empty_split_btf")) + goto cleanup; + btf__add_struct(split_btf, "s1", 4); /* [3] struct s1 { */ + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_struct(split_btf, "s2", 4); /* [4] struct s2 { */ + btf__add_field(split_btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_func_proto(split_btf, 1); /* [5] int (*)(int p); */ + btf__add_func_param(split_btf, "p", 2); + btf__add_func(split_btf, "f", BTF_FUNC_STATIC, 5); /* [6] int f(int *p); = */ + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] FUNC 'f' type_id=3D5 linkage=3Dstatic"); + + permute_ids[0] =3D 6; /* int f(int *p) */ + permute_ids[1] =3D 3; /* struct s1 */ + permute_ids[2] =3D 5; /* int (*)(int *p) */ + permute_ids[3] =3D 4; /* struct s2 */ + err =3D btf__permute(split_btf, permute_ids, NULL); + if (!ASSERT_OK(err, "btf__permute")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] FUNC 'f' type_id=3D5 linkage=3Dstatic", + "[4] STRUCT 's1' 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] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + +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