From nobody Fri Dec 19 11:21:44 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