From nobody Tue Dec 2 02:32:13 2025 Received: from mail-pl1-f171.google.com (mail-pl1-f171.google.com [209.85.214.171]) (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 573552E9ED8 for ; Wed, 19 Nov 2025 03:21:44 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522507; cv=none; b=nB8iOE4XdIgGc5JOgsD7uZWdNZAdtb+KrcAKD9Dts9aoA3022mjYhazxtjArj3leIUl8TEBeN5YuCDtpIOP4paURL3lxVsnsul5poDVDzezPMQDyafqK+xFTmh/DYlk9q7acK/N1RfYCbLwyaAhZxpT05RkKgLgVHFuwPRZmZT8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522507; c=relaxed/simple; bh=H01WYWTjit4IDrTI6i2QFoyvRtKnaGfvGo11pfu3UXc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=WqoCROlQFBLQAXuIrzlzfymAwmJ6OwPUFCRbK1656TOVmjZgwwijK01CTSw2XtvPtPKZLuOGABolgExXKorhtI0k3h5tFpXdKkqZ0l7PDEGF0DlPSBvLv7TfJbiv0b4Lq0vKUzivK3IfVSaVg+Vk1KnkgC3V5Y6Y4yzGF2CyQoo= 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=KNRXtCgG; arc=none smtp.client-ip=209.85.214.171 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="KNRXtCgG" Received: by mail-pl1-f171.google.com with SMTP id d9443c01a7336-2980d9b7df5so66644495ad.3 for ; Tue, 18 Nov 2025 19:21:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763522503; x=1764127303; 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=j4Efz0DfhwaNbhU/ThUpGlzfbjEU0d17SrWYpmaJZf4=; b=KNRXtCgGAohG0AR7pskH6uDdatdM/pyuADSf7/3J8gz+ZlS91zMi85lbCZw0Ywa9W1 7K4TZJGgx/DdZCmn5PhDCooyZhjiXAZ5lkXugP5ET55Izf96hWQt0jzYXU7VlMYsd8oO lYJbO4uqWiqqa3aE4Z+gB0ecj/ZalXpVUcLbSh/8xHm104NYjQCqckZBbM6aT0XKONAO 0FKahA1/9uHLnZrCVRHtxxAUpFKIW/nP+GASSxdhZGFJsRaNERrd/Po5UCJ/prtWu/So kLe2E+DOUQ99MZgi1xaoJMBGw56QRRLYiikmtrvBUuF5ZXQZtvlKNnEAqZtB5D/m1lYq cX7A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763522503; x=1764127303; 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=j4Efz0DfhwaNbhU/ThUpGlzfbjEU0d17SrWYpmaJZf4=; b=copzkuyCmj834abLnaiEIWzsDJiyPKkk3K1zU6tu5SJ8qkT3gsMR+M8+wGVCN773dz 4YwRHWE6Xl72dpZthYB0Ip60ZCCidKO0j1+s7oUwXmZWtKb7sfNxyVL8QG+aeVyHE/dT 9IJUUzm9EhJzHnQOwMTPa1OzmlYFTGAiqu+eMNJd1mxNeqtQKpk9hutvQuKw0/j0YxEx hxzvJBzwMGmiQeMLxcLwV1s7dOlZ/T5ZmRExa4NT3RQY2SdoAF3kjKMwNaJNvYy8kaKd RsNT+jUapQYkC1BhKwSzFk8HZy85Lq7g1huyREF5q/uTOjxyb9gGhAr2Ilm+9gTeOcVi i8qg== X-Forwarded-Encrypted: i=1; AJvYcCUzMjDEWQrKUlJeTDrqfbuTKaLQI/PlDqZ0WNL5OZi1px9k0PFnKzi+zWxRqe/AVvvexsaFjAxcz3eWtnM=@vger.kernel.org X-Gm-Message-State: AOJu0YwnBe+OTS5rpcJ7zlcZKSexfrpy6abyOf9Sp9GA1VGNabSD27Vf anyzEGeRTTMZ+00rd4CxcVlxMLtfsHFcApXRJnTsfWtJeo9qycjcG01h X-Gm-Gg: ASbGncs7EYWqOhr2Bl8TwRFGert0zhAhkF3pqQbpo86TCLi0JUfynJs+wtVUJNHuTwW 5uOdLKij2SCPnWgY8OH4swIePrps+8uzmPpKMH/og7GiVtedjioAWS/UDrfHNVaJAEpG45lXh/y AKkXnj1KEMhwz/B2OTElMHRKP5WjQDRCdLNmacyrbB+9d+Dw8OtJ+p2CRY9X9mm5GVE2UarDTbJ OBpbH9vMKp2rgVX/snlLOERBhEIJRhSDCMzJIAVt64Qk+zT+uDmVFjnP0+Oag5kCbvX1PX+9cDC Qkrwq1oYcud3i34fam462Ds0eseoGfBc7qHrQO9FDPZ1o9zfCFnBhnv1ncSrBsChLc2KexCHQAb 1uTXBK/q2Ng6sdQkBv67CQs0jpveQDx0dj6hCzUcx7/00RP1kqeI8T2bXt9EtDTcsxhdGcFKiHK F0dS9LHTKni+73gDgIciRJxZIN1c3krCx7cwx8Pw== X-Google-Smtp-Source: AGHT+IEhg8XZRWBMSEKpku63c8O1q1ZZte16uMZdW/35liLEU8vQeK8GgJdwK6G0silDHSovmO93kw== X-Received: by 2002:a17:903:18c:b0:297:df8f:b056 with SMTP id d9443c01a7336-2986a6ba482mr241202595ad.11.1763522503541; Tue, 18 Nov 2025 19:21:43 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2985c2bed5asm188352485ad.88.2025.11.18.19.21.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 18 Nov 2025 19:21:42 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v7 1/7] libbpf: Add BTF permutation support for type reordering Date: Wed, 19 Nov 2025 11:15:25 +0800 Message-Id: <20251119031531.1817099-2-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251119031531.1817099-1-dolinux.peng@gmail.com> References: <20251119031531.1817099-1-dolinux.peng@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" From: Donglin Peng Introduce btf__permute() API to allow in-place rearrangement of BTF types. This function reorganizes BTF type order according to a provided array of type IDs, updating all type references to maintain consistency. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 166 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 43 ++++++++++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 210 insertions(+) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 18907f0fcf9f..ab95ff19fde3 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -5829,3 +5829,169 @@ 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; + + /* skip references that point into the base BTF or VOID */ + if (new_type_id < p->btf->start_id) + return 0; + + /* invalid reference id */ + if (new_type_id >=3D btf__type_cnt(p->btf)) + return -EINVAL; + + new_type_id =3D p->id_map[new_type_id - p->btf->start_id]; + /* reference a dropped type is not allowed */ + if (new_type_id =3D=3D 0) + return -EINVAL; + + *type_id =3D new_type_id; + return 0; +} + +int btf__permute(struct btf *btf, __u32 *id_map, __u32 id_map_cnt, + const struct btf_permute_opts *opts) +{ + struct btf_permute p; + struct btf_ext *btf_ext; + void *next_type, *end_type; + void *nt, *new_types =3D NULL; + int err =3D 0, i, new_type_len; + __u32 *order_map =3D NULL; + __u32 id, new_nr_types =3D 0; + + if (!OPTS_VALID(opts, btf_permute_opts) || id_map_cnt !=3D btf->nr_types) + return libbpf_err(-EINVAL); + + /* used to record the storage sequence of types */ + order_map =3D calloc(btf->nr_types, 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]; + /* Drop the specified type */ + if (id =3D=3D 0) + continue; + /* Invalid id */ + if (id < btf->start_id || id >=3D btf__type_cnt(btf)) { + err =3D -EINVAL; + goto done; + } + id -=3D btf->start_id; + /* Multiple types cannot be mapped to the same ID */ + if (order_map[id]) { + err =3D -EINVAL; + goto done; + } + order_map[id] =3D i + btf->start_id; + new_nr_types =3D max(id + 1, new_nr_types); + } + + /* Check for missing IDs */ + for (i =3D 0; i < new_nr_types; i++) { + if (order_map[i] =3D=3D 0) { + err =3D -EINVAL; + goto done; + } + } + + p.btf =3D btf; + p.id_map =3D id_map; + nt =3D new_types; + for (i =3D 0; i < new_nr_types; i++) { + struct btf_field_iter it; + const struct btf_type *t; + __u32 *type_id; + int type_size; + + id =3D order_map[i]; + /* must be a valid type ID */ + t =3D btf__type_by_id(btf, id); + if (!t) { + err =3D -EINVAL; + goto done; + } + type_size =3D btf_type_size(t); + memcpy(nt, t, type_size); + + /* Fix up referenced IDs for BTF */ + err =3D btf_field_iter_init(&it, nt, BTF_FIELD_ITER_IDS); + if (err) + goto done; + while ((type_id =3D btf_field_iter_next(&it))) { + err =3D btf_permute_remap_type_id(type_id, &p); + if (err) + goto done; + } + + nt +=3D type_size; + } + + /* Fix up referenced IDs for btf_ext */ + btf_ext =3D OPTS_GET(opts, btf_ext, NULL); + if (btf_ext) { + err =3D btf_ext_visit_type_ids(btf_ext, btf_permute_remap_type_id, &p); + if (err) + goto done; + } + + new_type_len =3D nt - new_types; + next_type =3D new_types; + end_type =3D next_type + new_type_len; + i =3D 0; + while (next_type + sizeof(struct btf_type) <=3D end_type) { + btf->type_offs[i++] =3D next_type - new_types; + next_type +=3D btf_type_size(next_type); + } + + /* Resize */ + if (new_type_len < btf->hdr->type_len) { + void *tmp_types; + + tmp_types =3D realloc(new_types, new_type_len); + if (new_type_len && !tmp_types) { + err =3D -ENOMEM; + goto done; + } + new_types =3D tmp_types; + btf->nr_types =3D new_nr_types; + btf->type_offs_cap =3D btf->nr_types; + btf->types_data_cap =3D new_type_len; + btf->hdr->type_len =3D new_type_len; + btf->hdr->str_off =3D new_type_len; + btf->raw_size =3D btf->hdr->hdr_len + btf->hdr->type_len + btf->hdr->str= _len; + } + + free(order_map); + free(btf->types_data); + btf->types_data =3D new_types; + return 0; + +done: + free(order_map); + free(new_types); + return libbpf_err(err); +} diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h index ccfd905f03df..e63dcce531b3 100644 --- a/tools/lib/bpf/btf.h +++ b/tools/lib/bpf/btf.h @@ -273,6 +273,49 @@ LIBBPF_API int btf__dedup(struct btf *btf, const struc= t btf_dedup_opts *opts); */ LIBBPF_API int btf__relocate(struct btf *btf, const struct btf *base_btf); =20 +struct btf_permute_opts { + size_t sz; + /* optional .BTF.ext info along the main BTF info */ + struct btf_ext *btf_ext; + size_t :0; +}; +#define btf_permute_opts__last_field btf_ext + +/** + * @brief **btf__permute()** performs in-place BTF type rearrangement + * @param btf BTF object to permute + * @param id_map Array mapping original type IDs to new IDs + * @param id_map_cnt Number of elements in @id_map + * @param opts Optional parameters for BTF extension updates + * @return 0 on success, negative error code on failure + * + * **btf__permute()** rearranges BTF types according to the specified ID m= apping. + * The @id_map array defines the new type ID for each original type ID. + * + * For **base BTF**: + * - @id_map must include all types from ID 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` + * + * Setting @id_map element to 0 drops the corresponding type. Dropped type= s must not + * be referenced by any retained types. After permutation, type references= in BTF + * data and optional extension are updated automatically. + * + * Note: Dropping types may orphan some strings, requiring subsequent **bt= f__dedup()** + * to clean up unreferenced strings. + * + * On error, returns negative error code and sets errno: + * - `-EINVAL`: Invalid parameters or ID mapping (duplicates, out-of-ran= ge) + * - `-ENOMEM`: Memory allocation failure + */ +LIBBPF_API int btf__permute(struct btf *btf, __u32 *id_map, __u32 id_map_c= nt, + const struct btf_permute_opts *opts); + struct btf_dump; =20 struct btf_dump_opts { diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map index 8ed8749907d4..b778e5a5d0a8 100644 --- a/tools/lib/bpf/libbpf.map +++ b/tools/lib/bpf/libbpf.map @@ -451,4 +451,5 @@ LIBBPF_1.7.0 { global: bpf_map__set_exclusive_program; bpf_map__exclusive_program; + btf__permute; } LIBBPF_1.6.0; --=20 2.34.1 From nobody Tue Dec 2 02:32:13 2025 Received: from mail-pl1-f175.google.com (mail-pl1-f175.google.com [209.85.214.175]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C4D922F25F0 for ; Wed, 19 Nov 2025 03:21:47 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522510; cv=none; b=gDytlzR7kxW9j0C5qSFAoLbJgNOEd1/lLyjmBlFpMuEjh0GX0PKMEYiUziU+5mNvIfYREx8XERQitMzTCJxJm2GQu9nwmhK1I3bBNGdTGqiZ3uTw0d8ikCmhtz9Aga8y5Xx8iE6RUbAXXAdZ/32ep2uQAr1eh7BEmPMp2yC2Oh8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522510; c=relaxed/simple; bh=GBVX+ySw7NWLKgKlhE+nzNCRnzQLuGUfC1XtdwTzftw=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=gW/92MYSzsTj4+dLWwwtA6rRh1y4WJxB/GFZ/Va8X6rnM56EjaURsA2ZweLaQK84WHD9kv6seLs12TFweNXBvVFMB5fSfKd4JRjj1sh5uQZIP9VQL8LqSVD+Edt/5n2QB7Hebpfre45sQNe+M3BkprbTaiP3lLIdVcR+9XGyg6Y= 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=bYPeDfSa; arc=none smtp.client-ip=209.85.214.175 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="bYPeDfSa" Received: by mail-pl1-f175.google.com with SMTP id d9443c01a7336-29853ec5b8cso71491795ad.3 for ; Tue, 18 Nov 2025 19:21:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763522507; x=1764127307; 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=W5lRC+ms5uVQta4Fss1sLWV8MDgW3AK2UQU+qT8gzRo=; b=bYPeDfSa2ocdlm6kCmmk0N6I/SFEVNnhx6vb0ot0G6NYOJc4wLuBoXjiWjoRLqe6oW +Fzogri80+kyDUxOMYA9aKfot8920MBQECj+SPjiesoABbWjVHw5WTqBLULAbuxeBs8N qoqo1qv3yk26SFF1eR76Lk0XN8j5VYFXhKtwarJnF2YEzolLvb7hKtJ5Re1h2aLI7/U2 PcC4D2Tc4VZwwqsotfTAeUFO5OFaZaDsNDmxdnybDslonUtZcf+7ZSpssyMIh6/WzTKM UDy+KlgrCEcOLQfbYr3qzz/+3JtvBy6zRRaWk6Hv6PLPBlWyRkTJRZW6VBh1HbMiIQTL 72VA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763522507; x=1764127307; 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=W5lRC+ms5uVQta4Fss1sLWV8MDgW3AK2UQU+qT8gzRo=; b=G1whnNv/8dRn7n/+AxsJk9imKEmX+dXBzcHNp7aLkKwrZM7fFUuu3eXbGqhhYEvRjH h3kHur78NCdCUcKUHC75G6KQpsaO11MILfU9rX2GZP0oxfy0ENfLNyvTYihucTT2Yy0A wY42BmzNrxYZyUqrZ0spah4Q2iERL4IXw4O45JWIttBfqKoaTvG+Ych8bQOyegEef0y0 pfMquvBs5EvuJiTbX4v+zgo9MqP1mR4hJoFc4w7NReeuxdsXsN4E0SmhjIh9SCfeu+0N Xf/Jjnty4G/xA3DL0gYYQaNnlQrEGMho4+rCOwIw8CbmvMcKXNDpDeMUBsPRF5ltekIZ 4XDA== X-Forwarded-Encrypted: i=1; AJvYcCUOI06fUL8UFEIJsIu97o9DtXpjE09SSzeMI4fFLjXY54S7/oJuP7VxVJBuJO83Ge/wbGmgAfnID947sEI=@vger.kernel.org X-Gm-Message-State: AOJu0YxM77TXwBBnx5r62MRNqCP8c4J33IZYiJXRSrZFKTjv8mYOZ87Q FH9YVgOKp/zhEu4vJl4J6F75IRkAROGckt6rI+xxTsLTNN4VHq+h6LDv X-Gm-Gg: ASbGncuNgC5hIVh9Fv4MDaIM2aDKS8kBGSSAfEssqlcJzCkCgNU7vq7WXQ+gb6pBb5Z ZUTzrrI9SSLBmR2jgXDBQYNTHbdbVrvg4DDzNs1vaDeBihuSuQvHVzzV7/c+2HYcRhEYCwepN0y 9PuvqSYwlRtH78ZxCdUP7ilUpwa6xyMhMxEARoB4QZt6S4uoPFZ/oDhVjCcwBp2ZAPu47omCgTQ GfM2hFssZzXKgDMzzl3jZspMPQpAyemG7Euvq5PNDxabd3w0vwyfCSrC8i37ZzwN5oaevH+M/wu YFpMM9AkB7AhEuH+y/+ZcpB9ookUx9aUwHsZnVmN7g3rDdhqipJFUo/8t3AuClA+QDeiqDWuZdo 8XRFhEYl6pRGnzIWTGyU8iStL9XiH3jV/US3DpioVvwYz7hJYUNg88OAoAg7d29WlR6LkP9EXOL EbxXXxP8yQk7+Z5WmknZy+azik9Vk= X-Google-Smtp-Source: AGHT+IHgHrD8Lvmo2Cb3OBfOs4eI3ypnKdfjJJNaWHpXUJTYK/FeVBtZRHJINlqTh4sRCgOXuzHXdw== X-Received: by 2002:a17:903:3bc7:b0:290:9a74:a8ad with SMTP id d9443c01a7336-2986a76f2b7mr216940455ad.53.1763522506914; Tue, 18 Nov 2025 19:21:46 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2985c2bed5asm188352485ad.88.2025.11.18.19.21.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 18 Nov 2025 19:21:45 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v7 2/7] selftests/bpf: Add test cases for btf__permute functionality Date: Wed, 19 Nov 2025 11:15:26 +0800 Message-Id: <20251119031531.1817099-3-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251119031531.1817099-1-dolinux.peng@gmail.com> References: <20251119031531.1817099-1-dolinux.peng@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" From: Donglin Peng This patch introduces test cases for the btf__permute function to ensure it works correctly with both base BTF and split BTF scenarios. The test suite includes: - test_permute_base: Validates permutation on base BTF - test_permute_split: Tests permutation on split BTF - test_permute_drop_base: Validates type dropping on base BTF - test_permute_drop_split: Tests type dropping on split BTF - test_permute_drop_dedup: Tests type dropping and deduping Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- .../selftests/bpf/prog_tests/btf_permute.c | 608 ++++++++++++++++++ 1 file changed, 608 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..f67bf89519b3 --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/btf_permute.c @@ -0,0 +1,608 @@ +// 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 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; + + VALIDATE_RAW_BTF( + btf, + "[1] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[2] FUNC 'f' type_id=3D6 linkage=3Dstatic", + "[3] PTR '(anon)' type_id=3D4", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[5] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[6] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D3"); + + /* + * For base BTF, id_map_cnt must equal to the number of types + * include VOID type + */ + permute_ids[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; + + VALIDATE_RAW_BTF( + btf, + "[1] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[2] FUNC 'f' type_id=3D6 linkage=3Dstatic", + "[3] PTR '(anon)' type_id=3D4", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[5] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[6] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D3"); + + /* Multiple types can not be mapped to the same ID */ + permute_ids[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; + + VALIDATE_RAW_BTF( + btf, + "[1] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[2] FUNC 'f' type_id=3D6 linkage=3Dstatic", + "[3] PTR '(anon)' type_id=3D4", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[5] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[6] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D3"); + + /* Type ID must be valid */ + permute_ids[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; + + VALIDATE_RAW_BTF( + btf, + "[1] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[2] FUNC 'f' type_id=3D6 linkage=3Dstatic", + "[3] PTR '(anon)' type_id=3D4", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[5] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[6] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D3"); + +done: + btf__free(btf); +} + +/* Ensure btf__permute work as expected with split BTF */ +static void test_permute_split(void) +{ + struct btf *split_btf =3D NULL, *base_btf =3D NULL; + __u32 permute_ids[4]; + int err; + 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; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] FUNC 'f' type_id=3D5 linkage=3Dstatic", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + + /* + * For split BTF, id_map_cnt must equal to the number of types + * added on top of base BTF + */ + permute_ids[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; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] FUNC 'f' type_id=3D5 linkage=3Dstatic", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + + /* Multiple types can not be mapped to the same ID */ + permute_ids[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; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] FUNC 'f' type_id=3D5 linkage=3Dstatic", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + + /* Can not map to base ID */ + permute_ids[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; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's2' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[4] FUNC 'f' type_id=3D5 linkage=3Dstatic", + "[5] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[6] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + +cleanup: + btf__free(split_btf); + btf__free(base_btf); +} + +/* Verify btf__permute function drops types correctly with base_btf */ +static void test_permute_drop_base(void) +{ + struct btf *btf; + __u32 permute_ids[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"); + + /* Drop ID 4 */ + permute_ids[1 - start_id] =3D 5; /* [1] -> [5] */ + permute_ids[2 - start_id] =3D 1; /* [2] -> [1] */ + permute_ids[3 - start_id] =3D 2; /* [3] -> [2] */ + permute_ids[4 - start_id] =3D 0; /* Drop [4] */ + permute_ids[5 - start_id] =3D 3; /* [5] -> [3] */ + permute_ids[6 - start_id] =3D 4; /* [6] -> [4] */ + err =3D btf__permute(btf, permute_ids, ARRAY_SIZE(permute_ids), NULL); + if (!ASSERT_OK(err, "btf__permute_drop_base")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] PTR '(anon)' type_id=3D5", + "[2] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D5 bits_offset=3D0", + "[3] FUNC_PROTO '(anon)' ret_type_id=3D5 vlen=3D1\n" + "\t'p' type_id=3D1", + "[4] FUNC 'f' type_id=3D3 linkage=3Dstatic", + "[5] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED"); + + /* Continue dropping */ + permute_ids[1 - start_id] =3D 1; /* [1] -> [1] */ + permute_ids[2 - start_id] =3D 2; /* [2] -> [2] */ + permute_ids[3 - start_id] =3D 3; /* [3] -> [3] */ + permute_ids[4 - start_id] =3D 0; /* Drop [4] */ + permute_ids[5 - start_id] =3D 4; /* [5] -> [4] */ + err =3D btf__permute(btf, permute_ids, 5, NULL); + if (!ASSERT_OK(err, "btf__permute_drop_base_fail")) + goto done; + + + VALIDATE_RAW_BTF( + btf, + "[1] PTR '(anon)' type_id=3D4", + "[2] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[3] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D1", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED"); + + /* Cannot drop the ID referenced by others */ + permute_ids[1 - start_id] =3D 2; + permute_ids[2 - start_id] =3D 3; + permute_ids[3 - start_id] =3D 1; + permute_ids[4 - start_id] =3D 0; /* [4] is referenced by others */ + err =3D btf__permute(btf, permute_ids, 4, NULL); + if (!ASSERT_ERR(err, "btf__permute_drop_base_fail")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] PTR '(anon)' type_id=3D4", + "[2] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D4 bits_offset=3D0", + "[3] FUNC_PROTO '(anon)' ret_type_id=3D4 vlen=3D1\n" + "\t'p' type_id=3D1", + "[4] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED"); + + /* Drop 2 IDs at once */ + permute_ids[1 - start_id] =3D 2; /* [1] -> [2] */ + permute_ids[2 - start_id] =3D 0; /* Drop [2] */ + permute_ids[3 - start_id] =3D 0; /* Drop [3] */ + permute_ids[4 - start_id] =3D 1; /* [4] -> [1] */ + err =3D btf__permute(btf, permute_ids, 4, NULL); + if (!ASSERT_OK(err, "btf__permute_drop_base_fail")) + goto done; + + VALIDATE_RAW_BTF( + btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1"); + + /* Drop all IDs */ + permute_ids[1 - start_id] =3D 0; /* Drop [1] */ + permute_ids[2 - start_id] =3D 0; /* Drop [2] */ + err =3D btf__permute(btf, permute_ids, 2, NULL); + if (!ASSERT_OK(err, "btf__permute_drop_base_fail")) + goto done; + if (!ASSERT_EQ(btf__type_cnt(btf), 1, "btf__permute_drop_base all")) + goto done; + +done: + btf__free(btf); +} + +/* Verify btf__permute function drops types correctly with split BTF */ +static void test_permute_drop_split(void) +{ + struct btf *split_btf =3D NULL, *base_btf =3D NULL; + __u32 permute_ids[4]; + int err; + 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); + + /* Drop ID 4 */ + permute_ids[3 - start_id] =3D 5; /* [3] -> [5] */ + permute_ids[4 - start_id] =3D 0; /* Drop [4] */ + permute_ids[5 - start_id] =3D 3; /* [5] -> [3] */ + 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_drop_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[4] FUNC 'f' type_id=3D3 linkage=3Dstatic", + "[5] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + + /* Can not drop the type referenced by others */ + permute_ids[3 - start_id] =3D 0; /* [3] is referenced by [4] */ + permute_ids[4 - start_id] =3D 4; + permute_ids[5 - start_id] =3D 3; + err =3D btf__permute(split_btf, permute_ids, 3, NULL); + if (!ASSERT_ERR(err, "btf__permute_drop_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] FUNC_PROTO '(anon)' ret_type_id=3D1 vlen=3D1\n" + "\t'p' type_id=3D2", + "[4] FUNC 'f' type_id=3D3 linkage=3Dstatic", + "[5] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + + /* Continue dropping */ + permute_ids[3 - start_id] =3D 0; /* Drop [3] */ + permute_ids[4 - start_id] =3D 0; /* Drop [4] */ + permute_ids[5 - start_id] =3D 3; /* [5] -> [3] */ + err =3D btf__permute(split_btf, permute_ids, 3, NULL); + if (!ASSERT_OK(err, "btf__permute_drop_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1", + "[3] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0"); + + /* Continue dropping */ + permute_ids[3 - start_id] =3D 0; /* Drop [3] */ + err =3D btf__permute(split_btf, permute_ids, 1, NULL); + if (!ASSERT_OK(err, "btf__permute_drop_split")) + goto cleanup; + + VALIDATE_RAW_BTF( + split_btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] PTR '(anon)' type_id=3D1"); + +cleanup: + btf__free(split_btf); + btf__free(base_btf); +} + +/* Verify btf__permute then btf__dedup work correctly */ +static void test_permute_drop_dedup(void) +{ + struct btf *btf, *new_btf =3D NULL; + const struct btf_header *hdr; + const void *btf_data; + char expect_strs[] =3D "\0int\0s1\0m\0tag1\0tag2\0tag3"; + char expect_strs_dedupped[] =3D "\0int\0s1\0m\0tag1"; + __u32 permute_ids[5], btf_size; + 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_struct(btf, "s1", 4); /* [2] struct s1 { */ + btf__add_field(btf, "m", 1, 0, 0); /* int m; */ + /* } */ + btf__add_decl_tag(btf, "tag1", 2, -1); /* [3] tag -> s1: tag1 */ + btf__add_decl_tag(btf, "tag2", 2, 1); /* [4] tag -> s1/m: tag2 */ + btf__add_decl_tag(btf, "tag3", 2, 1); /* [5] tag -> s1/m: tag3 */ + + VALIDATE_RAW_BTF( + btf, + "[1] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED", + "[2] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D1 bits_offset=3D0", + "[3] DECL_TAG 'tag1' type_id=3D2 component_idx=3D-1", + "[4] DECL_TAG 'tag2' type_id=3D2 component_idx=3D1", + "[5] DECL_TAG 'tag3' type_id=3D2 component_idx=3D1"); + + btf_data =3D btf__raw_data(btf, &btf_size); + if (!ASSERT_OK_PTR(btf_data, "btf__raw_data")) + goto done; + hdr =3D btf_data; + if (!ASSERT_EQ(hdr->str_len, ARRAY_SIZE(expect_strs), "expect_strs")) + goto done; + + new_btf =3D btf__new(btf_data, btf_size); + if (!ASSERT_OK_PTR(new_btf, "btf__new")) + goto done; + + /* Drop 2 IDs result in unreferenced strings */ + permute_ids[1 - start_id] =3D 3; /* [1] -> [3] */ + permute_ids[2 - start_id] =3D 1; /* [2] -> [1] */ + permute_ids[3 - start_id] =3D 2; /* [3] -> [2] */ + permute_ids[4 - start_id] =3D 0; /* Drop result in unreferenced "tag2" */ + permute_ids[5 - start_id] =3D 0; /* Drop result in unreferenced "tag3" */ + err =3D btf__permute(new_btf, permute_ids, 5, NULL); + if (!ASSERT_OK(err, "btf__permute")) + goto done; + + VALIDATE_RAW_BTF( + new_btf, + "[1] STRUCT 's1' size=3D4 vlen=3D1\n" + "\t'm' type_id=3D3 bits_offset=3D0", + "[2] DECL_TAG 'tag1' type_id=3D1 component_idx=3D-1", + "[3] INT 'int' size=3D4 bits_offset=3D0 nr_bits=3D32 encoding=3DSIGNED"); + + btf_data =3D btf__raw_data(new_btf, &btf_size); + if (!ASSERT_OK_PTR(btf_data, "btf__raw_data")) + goto done; + hdr =3D btf_data; + if (!ASSERT_EQ(hdr->str_len, ARRAY_SIZE(expect_strs), "expect_strs")) + goto done; + + err =3D btf__dedup(new_btf, NULL); + if (!ASSERT_OK(err, "btf__dedup")) + goto done; + + btf_data =3D btf__raw_data(new_btf, &btf_size); + if (!ASSERT_OK_PTR(btf_data, "btf__raw_data")) + goto done; + hdr =3D btf_data; + if (!ASSERT_EQ(hdr->str_len, ARRAY_SIZE(expect_strs_dedupped), "expect_st= rs_dedupped")) + goto done; + +done: + btf__free(btf); + btf__free(new_btf); +} + +void test_btf_permute(void) +{ + if (test__start_subtest("permute_base")) + test_permute_base(); + if (test__start_subtest("permute_split")) + test_permute_split(); + if (test__start_subtest("permute_drop_base")) + test_permute_drop_base(); + if (test__start_subtest("permute_drop_split")) + test_permute_drop_split(); + if (test__start_subtest("permute_drop_dedup")) + test_permute_drop_dedup(); +} --=20 2.34.1 From nobody Tue Dec 2 02:32:13 2025 Received: from mail-pl1-f180.google.com (mail-pl1-f180.google.com [209.85.214.180]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id EE2312F3C0F for ; Wed, 19 Nov 2025 03:21:50 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522512; cv=none; b=SW/CKvXrtfxXTQ+z5ss4adJdenl/pcp/oNIwOAh8FRAi8ROeroZ8LK5qU+QdCYYthG12/Xi88Ja39MqTHaSh5n44bRTsF3szXIeUQUKE9+cHBK+tmrOdW5J2a4LD5/yUgtcF0EhyjYHQtV3ewbInAE3bZRKSm7LKeOUclhpdtuA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522512; c=relaxed/simple; bh=ATdrgW6KFELBRafH05kQcV6AsqpZhc9TKNlK93XOfh8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=B1l2Rr/7u55jsnmheZkMW16TSOH/RWUnvhsSFBKwFh0FBTzzSguGOHeYKVJPZcG4lI9djPyMpgKh6xL0f6ibyypgJQObL6i40A2z90GaWgoWaxU+UaHe+arlkEjO8qWv4pQwwpq9nuD6P/90vc8b5TW+ajnCH2nPIkV0jrUsoN0= 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=TTi6vDp/; arc=none smtp.client-ip=209.85.214.180 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="TTi6vDp/" Received: by mail-pl1-f180.google.com with SMTP id d9443c01a7336-2955623e6faso57439685ad.1 for ; Tue, 18 Nov 2025 19:21:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763522510; x=1764127310; 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=kiOGMko7D822DO4lbsrwsnsdnh27mz9D9I0b0hHBK4I=; b=TTi6vDp/6tE8bT1rf/j67kJqK/ckszuy+NCIASbOT4VoNQeAe4SK8zewDOShJ5GNWW LFx5kJHKmfMaOqYh3rf43x1vY9fT1aLM/YlZG2ErVE3nK1Ka7CCu5At9OGqhMmDLZtzx XrWwMTn1RehL23LFZdiQZQREn4g2QC8DJejBILAbpuc60TcibFw6QVUqueJAVUoY0VrJ 7DxFLvgyh6b2aqYmHs4s2R+hRM+owr0LHjHSZKcDQctMz6Fsr7B8NrKUnT4CyFM1otYN SicUC7xt+eZqM90+QXI88itzxn1bdr80e8KIn/QMi59q5MgVMvnofsWmSNvbIrQHgtyF +10w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763522510; x=1764127310; 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=kiOGMko7D822DO4lbsrwsnsdnh27mz9D9I0b0hHBK4I=; b=i70dEMBX7wTuv0ijZYvcNvmhcKFiEKbGQJhg1F4Q+7d+1xl4/+3NCrFDfkgawpmARc 6Nu3iDBpntEMhzE+4i9mmxBG+0pKLq3j0qQHdm8gLPmYIOAM5M8pZzV5MgiATfob9dV/ lhJUvxW5uetOMXVCzzg8aQTwMPONlz7ZiwDvVZ+DTG+7zTES71wtwtedG3uiBJ1cpOk/ kTiE7esztQ8LlcNW9pnJ9ruqrjLRd8L6zKML9m3cPSQCFHVFNrpMqT1z/Km3Jp7UnY88 FcG8vBbpns9ZLx/uX+ZCalU/hsqdzvkmZV5JYtYgNl7bNuBmCqP7/TPWkTdaw1/atXmB kdsQ== X-Forwarded-Encrypted: i=1; AJvYcCWjDRZkx9+dan1pzp4t5By3aoGIfkxoMRxTNMYM/VFtAKAwHRgJ6pKy4JLhdHLb4skmcsNAaTICciKOq4w=@vger.kernel.org X-Gm-Message-State: AOJu0YzvGsrygzsv6eiVl/atG3ItBMi+6staPkjAOAOs7/vTr66fYbv8 t1HVSzL0sTVVWkDzvV3rox+u+NrZNtcdIF3Hkq29DkdPi4zT8RrHXHy6 X-Gm-Gg: ASbGnct73l3+EklP1VuRLxKCQphwyNEkH9NjevsZDOLDkqY2zSLdwkhaGjcnN1p7oCY l7iLJtIlFsBTUZKhIe8B7EMMB8W5kM4EwG4bcGt8NsUnszIytTwzNKcW5Qdx1DvB1DzMPaq98Ex xwsa8mbaMjEzfCiSX6ZIExKWoRwcdpxvcJe0tGjpXurjEOWZXcjD8N4jxJ8Ira63i8FVe7RRtE2 FXg+AJxxhWYVI3z88kGM9eFqXPPkCgX2DlMtGu4AYpsPt93B8wjakU/0Iuh2RWIgtGkC7G7WzE2 euO3lpXEdyUXekM9eQ31yxBwH4OwyPe24NkAUxrHpHi84CqVb3NmWuFqbVyciFtLCQsJN+fh+tV iCp+NRDo6vWSiNX/qFhNuEu2u3y5CLf/Epn3bgf+6+FCLa5itWwsGpVLrPdfYjVD+CzEvtT9tsN hOeZcervQvEojz7J2BHSslUZgRxEyXYlrJT2UFLQ== X-Google-Smtp-Source: AGHT+IEvN38EIx6thP5o+/I1V8gBpMiGFxMzyd6hdKQk9DOpl4hluxga4rzDLLd9AUDpzqL+YKAcQQ== X-Received: by 2002:a17:902:d54c:b0:295:ed6:4625 with SMTP id d9443c01a7336-2986a74f5ffmr216927215ad.47.1763522510224; Tue, 18 Nov 2025 19:21:50 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2985c2bed5asm188352485ad.88.2025.11.18.19.21.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 18 Nov 2025 19:21:49 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v7 3/7] tools/resolve_btfids: Add --btf_sort option for BTF name sorting Date: Wed, 19 Nov 2025 11:15:27 +0800 Message-Id: <20251119031531.1817099-4-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251119031531.1817099-1-dolinux.peng@gmail.com> References: <20251119031531.1817099-1-dolinux.peng@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" From: Donglin Peng This patch introduces a new --btf_sort option that leverages libbpf's btf__permute interface to reorganize BTF layout. The implementation sorts BTF types by name in ascending order, placing anonymous types at the end to enable efficient binary search lookup. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- scripts/Makefile.btf | 2 + scripts/Makefile.modfinal | 1 + scripts/link-vmlinux.sh | 1 + tools/bpf/resolve_btfids/main.c | 200 ++++++++++++++++++++++++++++++++ 4 files changed, 204 insertions(+) diff --git a/scripts/Makefile.btf b/scripts/Makefile.btf index db76335dd917..d5eb4ee70e88 100644 --- a/scripts/Makefile.btf +++ b/scripts/Makefile.btf @@ -27,6 +27,7 @@ pahole-flags-$(call test-ge, $(pahole-ver), 130) +=3D --b= tf_features=3Dattributes =20 ifneq ($(KBUILD_EXTMOD),) module-pahole-flags-$(call test-ge, $(pahole-ver), 128) +=3D --btf_feature= s=3Ddistilled_base +module-resolve_btfid-flags-y =3D --distilled_base endif =20 endif @@ -35,3 +36,4 @@ pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) +=3D --la= ng_exclude=3Drust =20 export PAHOLE_FLAGS :=3D $(pahole-flags-y) export MODULE_PAHOLE_FLAGS :=3D $(module-pahole-flags-y) +export MODULE_RESOLVE_BTFID_FLAGS :=3D $(module-resolve_btfid-flags-y) diff --git a/scripts/Makefile.modfinal b/scripts/Makefile.modfinal index 542ba462ed3e..4481dda2f485 100644 --- a/scripts/Makefile.modfinal +++ b/scripts/Makefile.modfinal @@ -40,6 +40,7 @@ quiet_cmd_btf_ko =3D BTF [M] $@ printf "Skipping BTF generation for %s due to unavailability of vmlinux\= n" $@ 1>&2; \ else \ LLVM_OBJCOPY=3D"$(OBJCOPY)" $(PAHOLE) -J $(PAHOLE_FLAGS) $(MODULE_PAHOLE= _FLAGS) --btf_base $(objtree)/vmlinux $@; \ + $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $(MODULE_RESOLVE_BTFID_FLAGS) --= btf_sort $@; \ $(RESOLVE_BTFIDS) -b $(objtree)/vmlinux $@; \ fi; =20 diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh index 433849ff7529..f21f6300815b 100755 --- a/scripts/link-vmlinux.sh +++ b/scripts/link-vmlinux.sh @@ -288,6 +288,7 @@ if is_enabled CONFIG_DEBUG_INFO_BTF; then if is_enabled CONFIG_WERROR; then RESOLVE_BTFIDS_ARGS=3D" --fatal_warnings " fi + ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} --btf_sort "${VMLINUX}" ${RESOLVE_BTFIDS} ${RESOLVE_BTFIDS_ARGS} "${VMLINUX}" fi =20 diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/mai= n.c index d47191c6e55e..dc0badd6f375 100644 --- a/tools/bpf/resolve_btfids/main.c +++ b/tools/bpf/resolve_btfids/main.c @@ -768,6 +768,195 @@ static int symbols_patch(struct object *obj) return err < 0 ? -1 : 0; } =20 +/* Anonymous types (with empty names) are considered greater than named ty= pes + * and are sorted after them. Two anonymous types are considered equal. Na= med + * types are compared lexicographically. + */ +static int cmp_type_names(const void *a, const void *b, void *priv) +{ + struct btf *btf =3D (struct btf *)priv; + const struct btf_type *ta =3D btf__type_by_id(btf, *(__u32 *)a); + const struct btf_type *tb =3D btf__type_by_id(btf, *(__u32 *)b); + const char *na, *nb; + + if (!ta->name_off && tb->name_off) + return 1; + if (ta->name_off && !tb->name_off) + return -1; + if (!ta->name_off && !tb->name_off) + return 0; + + na =3D btf__str_by_offset(btf, ta->name_off); + nb =3D btf__str_by_offset(btf, tb->name_off); + return strcmp(na, nb); +} + +static int update_btf_section(const char *path, const struct btf *btf, + const char *btf_secname) +{ + GElf_Shdr shdr_mem, *shdr; + Elf_Data *btf_data =3D NULL; + Elf_Scn *scn =3D NULL; + Elf *elf =3D NULL; + const void *raw_btf_data; + uint32_t raw_btf_size; + int fd, err =3D -1; + size_t strndx; + + fd =3D open(path, O_RDWR); + if (fd < 0) { + pr_err("FAILED to open %s\n", path); + return -1; + } + + if (elf_version(EV_CURRENT) =3D=3D EV_NONE) { + pr_err("FAILED to set libelf version"); + goto out; + } + + elf =3D elf_begin(fd, ELF_C_RDWR, NULL); + if (elf =3D=3D NULL) { + pr_err("FAILED to update ELF file"); + goto out; + } + + elf_flagelf(elf, ELF_C_SET, ELF_F_LAYOUT); + + elf_getshdrstrndx(elf, &strndx); + while ((scn =3D elf_nextscn(elf, scn)) !=3D NULL) { + char *secname; + + shdr =3D gelf_getshdr(scn, &shdr_mem); + if (shdr =3D=3D NULL) + continue; + secname =3D elf_strptr(elf, strndx, shdr->sh_name); + if (strcmp(secname, btf_secname) =3D=3D 0) { + btf_data =3D elf_getdata(scn, btf_data); + break; + } + } + + raw_btf_data =3D btf__raw_data(btf, &raw_btf_size); + + if (btf_data) { + if (raw_btf_size !=3D btf_data->d_size) { + pr_err("FAILED: size mismatch"); + goto out; + } + + btf_data->d_buf =3D (void *)raw_btf_data; + btf_data->d_type =3D ELF_T_WORD; + elf_flagdata(btf_data, ELF_C_SET, ELF_F_DIRTY); + + if (elf_update(elf, ELF_C_WRITE) >=3D 0) + err =3D 0; + } + +out: + if (fd !=3D -1) + close(fd); + if (elf) + elf_end(elf); + return err; +} + +static int sort_update_btf(struct object *obj, bool distilled_base) +{ + struct btf *base_btf =3D NULL; + struct btf *btf =3D NULL; + int start_id =3D 1, nr_types, id; + int err =3D 0, i; + __u32 *permute_ids =3D NULL, *id_map =3D NULL, btf_size; + const void *btf_data; + int fd; + + if (obj->base_btf_path) { + base_btf =3D btf__parse(obj->base_btf_path, NULL); + err =3D libbpf_get_error(base_btf); + if (err) { + pr_err("FAILED: load base BTF from %s: %s\n", + obj->base_btf_path, strerror(-err)); + return -1; + } + } + + btf =3D btf__parse_elf_split(obj->path, base_btf); + err =3D libbpf_get_error(btf); + if (err) { + pr_err("FAILED: load BTF from %s: %s\n", obj->path, strerror(-err)); + goto out; + } + + if (base_btf) + start_id =3D btf__type_cnt(base_btf); + nr_types =3D btf__type_cnt(btf) - start_id; + if (nr_types < 2) + goto out; + + 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)); + goto out; + } + + if (distilled_base) { + struct btf *new_btf =3D NULL, *distilled_base =3D NULL; + + if (btf__distill_base(btf, &distilled_base, &new_btf) < 0) { + pr_err("FAILED to generate distilled base BTF: %s\n", + strerror(errno)); + goto out; + } + + err =3D update_btf_section(obj->path, new_btf, BTF_ELF_SEC); + if (!err) { + err =3D update_btf_section(obj->path, distilled_base, BTF_BASE_ELF_SEC); + if (err < 0) + pr_err("FAILED to update '%s'\n", BTF_BASE_ELF_SEC); + } else { + pr_err("FAILED to update '%s'\n", BTF_ELF_SEC); + } + + btf__free(new_btf); + btf__free(distilled_base); + } else { + err =3D update_btf_section(obj->path, btf, BTF_ELF_SEC); + if (err < 0) { + pr_err("FAILED to update '%s'\n", BTF_ELF_SEC); + goto out; + } + } + +out: + free(permute_ids); + free(id_map); + btf__free(base_btf); + btf__free(btf); + return err; +} + static const char * const resolve_btfids_usage[] =3D { "resolve_btfids [] ", NULL @@ -787,6 +976,8 @@ int main(int argc, const char **argv) .sets =3D RB_ROOT, }; bool fatal_warnings =3D false; + bool btf_sort =3D false; + bool distilled_base =3D false; struct option btfid_options[] =3D { OPT_INCR('v', "verbose", &verbose, "be more verbose (show errors, etc)"), @@ -796,6 +987,10 @@ int main(int argc, const char **argv) "path of file providing base BTF"), OPT_BOOLEAN(0, "fatal_warnings", &fatal_warnings, "turn warnings into errors"), + OPT_BOOLEAN(0, "btf_sort", &btf_sort, + "sort BTF by name in ascending order"), + OPT_BOOLEAN(0, "distilled_base", &distilled_base, + "distill base"), OPT_END() }; int err =3D -1; @@ -807,6 +1002,11 @@ int main(int argc, const char **argv) =20 obj.path =3D argv[0]; =20 + if (btf_sort) { + err =3D sort_update_btf(&obj, distilled_base); + goto out; + } + if (elf_collect(&obj)) goto out; =20 --=20 2.34.1 From nobody Tue Dec 2 02:32:13 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 280F02EA168 for ; Wed, 19 Nov 2025 03:21:53 +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=1763522515; cv=none; b=TfZyofPoZ/fmzsIm8/PRVuYbHCsZB1VwRDePmBTCyo/TxaOtb8smhAzyPeBnee/DbCIxp64ZzP0aADTQX47xHY7Q02qSeTq8J5UmSbXVSMIFRHsqw11Wc1otdVHZSVrBqpaLeSPiodve8dNivpdwEbBkEAMqt360/SGJnt4oj4A= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522515; c=relaxed/simple; bh=pRQusZkSLe1fwc7vB/uN8SQmj+69/j5iu2aOU15S3L4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=mLiv8EDEoWteES7t4Ift8Ax0THSR4MeLQOzzphIYdv07siIPEsMjCFqNi6lonjyBqPvv82d7wITafMSXomJd3kd/ozzyfOYKpHWoZO8MOGjB88XsybpM2009asoFCuwLVkvrx/mrUklavT/SipEtNL6ZebIUKqtQ63qdFPpf/s4= 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=MeAp0qNH; 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="MeAp0qNH" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-299d40b0845so53804735ad.3 for ; Tue, 18 Nov 2025 19:21:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763522513; x=1764127313; 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=z+FkS3xOd3KY3Oh85nihoYx6o93mfmCHv+PUDaVgOok=; b=MeAp0qNHN/n5zj4FNV0Ezs1VuC7VueWWTg7oSv+y8vCAdJ11O3ZtAQ0F5pBKfv8ZCd FU9Fqg4WtcIlb7On/uV3vnuKM3jfYVzV3BVcip+hVvoafeG1KGHoY4j0NLS9yqDjWyr+ xLAsnwVizWqJ3U9I1T8GOQtTLer8TmC4Ex7WI9+oGvjZFLrwnCQcv28hQwvJ1ie6REhI xxjn2G31lAKU6VqtXLUNQVEeagtM/smIHWnW7SloSqZjFCRBzG95s1Csu2UI72qs0weH PW4QQOlP7d9lsZW45ECRTPJo47wlg3wbGS84Uc/4ERi0Ar0mBqKaH+/9t0W8829SYkFW xChA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763522513; x=1764127313; 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=z+FkS3xOd3KY3Oh85nihoYx6o93mfmCHv+PUDaVgOok=; b=qtOmKjTkeACT9Y6ZqTyGK1931rpAMea14svXMUoSZTCBLZDojLp3negJDC5g+/FuQk hyTRO3etfcs8BB8eJi7tayjx5LNYcmfbkX0GU5v+TwjAkhZno552fJ2igwKJicgHfPkR DpsuNcPNRWIRsKk0gGJ/9fdELt5wgYDjY2NTjS63U3ecgN4b3sr49jjsCN7ftmvWdDAt YOpOSg/7iATe2+r0nGNIhB5pIVgp6wpU/zO2wLkpN5z2s+bymtLbP7K7LBEJKjFtdmvD bDwRizhltmQezMtmnC3e9V1a+Ww1pjlJmWkI9cxWLN4PQ8sEwPotl4Q1FwlQuhA37ao1 4BLw== X-Forwarded-Encrypted: i=1; AJvYcCWQ02Kpy9ZRiahQ3UFBGsThqGHj8U6gBNUzU4r14/+nOxz7cOcqPJVIB6PVLmxv2uYrmNDzF+QT1H6y2KM=@vger.kernel.org X-Gm-Message-State: AOJu0Ywa1Kpmr6xwDBqN3SF74ouV9j4o+OEvj2OdzrwYc9YlmEJbRRuZ bdW/OUCgPIftk9ONUjpGs/oHio1+2Ue8jP1bjlF38Y8YTerx6MpK9/1q X-Gm-Gg: ASbGnct+Vp7ur7femdBOMzr6OHN0RNxOANwMbPE4lSKaO16aodMyENZl6ZaoX9jqRhC OUPqtTRHsyvfnCWL7X5fH134UWyNJZ/Y7lEP4rQcq19audOndsCLbUx5bAiScA4yFlctPq4HNii M8jSPVYLplZp8OlG9cTJDzKhyUILdDWR91RCypo3DWmJPtUVDjlra5nmrLfx83yACEWPGo4mKIe W5ES+f9QbyXGoTm/s0hix27SuaAuydW/1H+FKHENx+mvwzcoPbjAc4RLfUwTNljg3mTpvG2qCOL obuQW7RXizGnACJMLX6kY9UnqNnowRqRrh3JQpES1t8Ilrd8v386dLmT9C8FGLs+jKQJ+zwfusC +vXN/AScDCnkFtmHCsKCO4YErQiUiC+gZzoJ6OjLShOrmBoF2T9OJUU76H4njalaYQLic9ssTPU YaWPbfni8l1Ah5JNP9RekKL2R3g/eeoY7ZQ6hCZw== X-Google-Smtp-Source: AGHT+IFUoGb4wi50+IfBdQ0MktBJM2JOUYOy3xmChyxxc0HHiTUr7XweRhKfvx+O/GiZMLxsvLk7Xg== X-Received: by 2002:a17:903:1b2c:b0:297:fc22:3ab2 with SMTP id d9443c01a7336-2986a73aefdmr216874545ad.36.1763522513507; Tue, 18 Nov 2025 19:21:53 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2985c2bed5asm188352485ad.88.2025.11.18.19.21.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 18 Nov 2025 19:21:52 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF Date: Wed, 19 Nov 2025 11:15:28 +0800 Message-Id: <20251119031531.1817099-5-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251119031531.1817099-1-dolinux.peng@gmail.com> References: <20251119031531.1817099-1-dolinux.peng@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" From: Donglin Peng This patch introduces binary search optimization for BTF type lookups when the BTF instance contains sorted types. The optimization significantly improves performance when searching for types in large BTF instances with sorted type names. For unsorted BTF or when nr_sorted_types is zero, the implementation falls back to the original linear search algorithm. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 104 ++++++++++++++++++++++++++++++++++---------- 1 file changed, 81 insertions(+), 23 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index ab95ff19fde3..1d19d95da1d0 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -92,6 +92,12 @@ struct btf { * - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; + /* number of sorted and named types in this BTF instance: + * - doesn't include special [0] void type; + * - for split BTF counts number of sorted and named types added on + * top of base BTF. + */ + __u32 nr_sorted_types; /* if not NULL, points to the base BTF on top of which the current * split BTF is based */ @@ -897,44 +903,93 @@ int btf__resolve_type(const struct btf *btf, __u32 ty= pe_id) return type_id; } =20 -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const ch= ar *name, + __s32 start_id, __s32 end_id) { - __u32 i, nr_types =3D btf__type_cnt(btf); + const struct btf_type *t; + const char *tname; + __s32 l, r, m; + + l =3D start_id; + r =3D end_id; + while (l <=3D r) { + m =3D l + (r - l) / 2; + t =3D btf_type_by_id(btf, m); + tname =3D btf__str_by_offset(btf, t->name_off); + if (strcmp(tname, name) >=3D 0) { + if (l =3D=3D r) + return r; + r =3D m; + } else { + l =3D m + 1; + } + } =20 - if (!strcmp(type_name, "void")) - return 0; + return btf__type_cnt(btf); +} =20 - for (i =3D 1; i < nr_types; i++) { - const struct btf_type *t =3D btf__type_by_id(btf, i); - const char *name =3D btf__name_by_offset(btf, t->name_off); +static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_i= d, + const char *type_name, __u32 kind) +{ + const struct btf_type *t; + const char *tname; + int err =3D -ENOENT; + + if (start_id < btf->start_id) { + err =3D btf_find_type_by_name_kind(btf->base_btf, start_id, + type_name, kind); + if (err > 0) + goto out; + start_id =3D btf->start_id; + } + + if (btf->nr_sorted_types > 0) { + /* binary search */ + __s32 end_id; + int idx; + + end_id =3D btf->start_id + btf->nr_sorted_types - 1; + idx =3D btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id); + for (; idx <=3D end_id; idx++) { + t =3D btf__type_by_id(btf, idx); + tname =3D btf__str_by_offset(btf, t->name_off); + if (strcmp(tname, type_name)) + goto out; + if (kind =3D=3D -1 || btf_kind(t) =3D=3D kind) + return idx; + } + } else { + /* linear search */ + __u32 i, total; =20 - if (name && !strcmp(type_name, name)) - return i; + total =3D btf__type_cnt(btf); + for (i =3D start_id; i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (kind !=3D -1 && btf_kind(t) !=3D kind) + continue; + tname =3D btf__str_by_offset(btf, t->name_off); + if (tname && !strcmp(tname, type_name)) + return i; + } } =20 - return libbpf_err(-ENOENT); +out: + return err; } =20 static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id, const char *type_name, __u32 kind) { - __u32 i, nr_types =3D btf__type_cnt(btf); - if (kind =3D=3D BTF_KIND_UNKN || !strcmp(type_name, "void")) return 0; =20 - for (i =3D start_id; i < nr_types; i++) { - const struct btf_type *t =3D btf__type_by_id(btf, i); - const char *name; - - if (btf_kind(t) !=3D kind) - continue; - name =3D btf__name_by_offset(btf, t->name_off); - if (name && !strcmp(type_name, name)) - return i; - } + return libbpf_err(btf_find_type_by_name_kind(btf, start_id, type_name, ki= nd)); +} =20 - return libbpf_err(-ENOENT); +/* the kind value of -1 indicates that kind matching should be skipped */ +__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +{ + return btf_find_by_name_kind(btf, btf->start_id, type_name, -1); } =20 __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_n= ame, @@ -1006,6 +1061,7 @@ static struct btf *btf_new_empty(struct btf *base_btf) btf->fd =3D -1; btf->ptr_sz =3D sizeof(void *); btf->swapped_endian =3D false; + btf->nr_sorted_types =3D 0; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1057,6 +1113,7 @@ static struct btf *btf_new(const void *data, __u32 si= ze, struct btf *base_btf, b btf->start_id =3D 1; btf->start_str_off =3D 0; btf->fd =3D -1; + btf->nr_sorted_types =3D 0; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1715,6 +1772,7 @@ static void btf_invalidate_raw_data(struct btf *btf) free(btf->raw_data_swapped); btf->raw_data_swapped =3D NULL; } + btf->nr_sorted_types =3D 0; } =20 /* Ensure BTF is ready to be modified (by splitting into a three memory --=20 2.34.1 From nobody Tue Dec 2 02:32:13 2025 Received: from mail-pl1-f171.google.com (mail-pl1-f171.google.com [209.85.214.171]) (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 86C8B2EA176 for ; Wed, 19 Nov 2025 03:21:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522519; cv=none; b=QsSEXvSJn/En7aqYegOZBQ8jHYaE4n0h1UQQEg3edKx8dfl81hisJYwmRTUqK4Gs98RDtoXsdH0S+x3IztwhcODtqCdCTJALyEDnI4K4pzrv6bPSFE769GJsYj7DaXVhlK7qhUkoAlH3HYbF3iWvcaJie0fhxRoz63+NdRM+/38= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522519; c=relaxed/simple; bh=0hqy/1YltC7K45hUu+cIK8psLGyQ0+7iQdqAXZ3z9pU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=B0rgwvRXrCgAhXyAiZ8l1/LFYE9lQL//Dzb+D/Mv2e6AXDettlMB0/zogY1Oui888tB8WYzUKjniuqGxXPUxYIlDBgBXtwmkxijKGZC9IyPeD7Qc/r2z/0CzVqNo4yyAGOHwUI2g6bNuYj0Du3fdNejhJD9alvmVCQSYtO2Bzk0= 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=IjgvL3Fw; arc=none smtp.client-ip=209.85.214.171 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="IjgvL3Fw" Received: by mail-pl1-f171.google.com with SMTP id d9443c01a7336-2958db8ae4fso57898275ad.2 for ; Tue, 18 Nov 2025 19:21:57 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763522517; x=1764127317; 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=MrUjlXbQpuT/rGn9ebhDAet+g15u+mqlf//GGNvk5as=; b=IjgvL3FwsC3dy9Rj81fTOmvf5ibdXlJz3HGTR9RtXiDc47YeowyXizA+ml+dP6aCta fmjsLOQ241rcGThMk8esXSzWQfWfi0mCsr1AWzxbk1UGRAltYtc0CadROB1MAcno81p2 NKSipfrPT9cyRsyClR6PD4/6iz1QKLZcO6Du0XrZ+O3lO21cvrMtDjsTspqd42T6s7y8 iifHkbkQyzHs1Q5lKc+L78Ql4hRKSG3RPw6iepbtXr6NCo1wvAV+5MEESUCjj6l+056B HtwfLeIB8lTZH8uv74P6OkCIZ+d6pZAXbJta68swjONOCru6fviLmjwr6pEqswUojkG4 k7eQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763522517; x=1764127317; 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=MrUjlXbQpuT/rGn9ebhDAet+g15u+mqlf//GGNvk5as=; b=XZ0ddsgUKac1rywK83XL2reEbT9PNp4L+f4t0pM7eesyqV9DrAqwQkA4apE7F6EiuL lbRyJgFu5NeSyyN02HbF6isumwOr1MZsEy/w3Qe5lnD0wySDqO3hJs8LP6sW5lV3s+G3 mOv8qaSfyFovrlub6CcZnNiC3Q7V78QYG1tRQuVvcfmu8Lv4f6bTAwdrWPNnmNniWSYh btWXB9C7DttUs9ndOp+yGhDJZ8p96mx4yC794ER5KYCZiZJexhCFMdtEJHXUYPm3BN45 SG9X5VUs1KdOzY8vNE+D/D5EOgc2Kr3jwu1dC7dgeZTDmLKzlBF9hn+ZzWbafjw2wYdp /8UQ== X-Forwarded-Encrypted: i=1; AJvYcCVka4bEIymCfMCHIGWj/5MTkslGDmFbCT6kJemLz38T1GgAJRSApHut/NmbXuNC9esKfzDxEcB/3FdawjE=@vger.kernel.org X-Gm-Message-State: AOJu0Yy/MzUgVN99LmKHNeP4AwKTTHG7/Yxe5PweqE+NyxNsc+NmIzFz fp4F0XlyIQxNWTG4mnf4QMB7GQPSXDS6OZNfcY3+5cc54C1hmsI48v7l X-Gm-Gg: ASbGncvjkYksEbBGQ39DVhntuEz9MxNQYQFLgUDm5j9JHMj6qaJmDn7xd3Nv0JlhfTz xytGUAHqQ9155EvG/qQ0ssX86UzYCOiqDPMFXwrp7tKIdaJ94dT3LR3ArtUHn4ZihQAGYuxEvGV P6m/lT127mhucROEVo3/mI6TKQx0sPxCl8tY2sEiYkseZ24oZRQx1fBUtCDJJkoiQYJ46RbJr62 K7aa264bsrymmatgSUtntG/gu9rGviLV0YnI3wjbmTkCFo81KVUythtQ28LTmo6AgNZWkq9qWzu F9xtyzf9BoBRbuf8HYNMTlYZNdYI7HpE7ST0Fxb+Ko9eGVBzXVtLpggbRy9/7UQdPSunU6th1YZ okMLHbZlZ848M9C0L6er/YyAna8Gq36+7MHFiw2b13V0hKl8f3gJpJaCMZRF+sIijdEiplIj7/Y jMlBXkz9tNwuutQtWXTbLcizrIySA= X-Google-Smtp-Source: AGHT+IEeqtmqV6MAaO/aC4GZwvfG+fRBuBRuioDCvJVWhMVtIzDtCsYz46QorBFw4vp/021FCzUk1g== X-Received: by 2002:a17:902:da48:b0:295:9e4e:4090 with SMTP id d9443c01a7336-2986a766ba1mr199517065ad.52.1763522516753; Tue, 18 Nov 2025 19:21:56 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2985c2bed5asm188352485ad.88.2025.11.18.19.21.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 18 Nov 2025 19:21:55 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization Date: Wed, 19 Nov 2025 11:15:29 +0800 Message-Id: <20251119031531.1817099-6-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251119031531.1817099-1-dolinux.peng@gmail.com> References: <20251119031531.1817099-1-dolinux.peng@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" From: Donglin Peng This patch adds validation to verify BTF type name sorting, enabling binary search optimization for lookups. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 1d19d95da1d0..d872abff42e1 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 typ= e_id) return type_id; } =20 +/* Anonymous types (with empty names) are considered greater than named ty= pes + * and are sorted after them. Two anonymous types are considered equal. Na= med + * types are compared lexicographically. + */ +static int btf_compare_type_names(const void *a, const void *b, void *priv) +{ + struct btf *btf =3D (struct btf *)priv; + struct btf_type *ta =3D btf_type_by_id(btf, *(__u32 *)a); + struct btf_type *tb =3D btf_type_by_id(btf, *(__u32 *)b); + const char *na, *nb; + bool anon_a, anon_b; + + na =3D btf__str_by_offset(btf, ta->name_off); + nb =3D btf__str_by_offset(btf, tb->name_off); + anon_a =3D str_is_empty(na); + anon_b =3D str_is_empty(nb); + + if (anon_a && !anon_b) + return 1; + if (!anon_a && anon_b) + return -1; + if (anon_a && anon_b) + return 0; + + return strcmp(na, nb); +} + +/* Verifies that BTF types are sorted in ascending order according to their + * names, with named types appearing before anonymous types. If the orderi= ng + * is correct, counts the number of named types and updates the BTF object= 's + * nr_sorted_types field. + */ +static void btf_check_sorted(struct btf *btf) +{ + const struct btf_type *t; + int i, k =3D 0, n, nr_sorted_types; + + if (btf->nr_types < 2) + return; + + nr_sorted_types =3D 0; + n =3D btf__type_cnt(btf) - 1; + for (i =3D btf->start_id; i < n; i++) { + k =3D i + 1; + if (btf_compare_type_names(&i, &k, btf) > 0) + return; + t =3D btf_type_by_id(btf, i); + if (!str_is_empty(btf__str_by_offset(btf, t->name_off))) + nr_sorted_types++; + } + + t =3D btf_type_by_id(btf, k); + if (!str_is_empty(btf__str_by_offset(btf, t->name_off))) + nr_sorted_types++; + if (nr_sorted_types) + btf->nr_sorted_types =3D nr_sorted_types; +} + static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const ch= ar *name, __s32 start_id, __s32 end_id) { @@ -1148,6 +1206,7 @@ static struct btf *btf_new(const void *data, __u32 si= ze, struct btf *base_btf, b err =3D err ?: btf_sanity_check(btf); if (err) goto done; + btf_check_sorted(btf); =20 done: if (err) { --=20 2.34.1 From nobody Tue Dec 2 02:32:13 2025 Received: from mail-pl1-f169.google.com (mail-pl1-f169.google.com [209.85.214.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 CEF352FD66E for ; Wed, 19 Nov 2025 03:22:00 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522522; cv=none; b=OPvcjrOTAWQcd0PoXTrnPa3KzTnCe2/6pMT7ZDxw0rP7fcfuK6B8Umzxp/hmtbY3hSrfZN/fbSgaqBEi17GeHVrffZdTSg4Bjrqg2GP7ImZFgjjnkBfXTwRXt0m8iXfeawR71R1c4OFruPB+H1TR6zWQh9XUoqGj+wPSBb3L7S0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522522; c=relaxed/simple; bh=1JCm2gAw7szR6coFfKCMu4oP2N4ZVTGa8uyyO11FaJ8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=R+HTiMLyPYn3ULkpCQ2nUQkDZabQLwol8yKRDeUibvK8D7aNBC1olpwM68vRnDG20Xa8vCUepI2uj3Il39ELFQnrKcX982IeXjoK5ixxuazk6vXEevfn1wOCNgVR3/9VbKUhlKFHjStNbMlMIBaxu/GWtz+AgvdGXF0sWpQLgoQ= 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=k9dE0G4a; arc=none smtp.client-ip=209.85.214.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="k9dE0G4a" Received: by mail-pl1-f169.google.com with SMTP id d9443c01a7336-29845b06dd2so71553615ad.2 for ; Tue, 18 Nov 2025 19:22:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763522520; x=1764127320; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Rljz3QHqavQzM2+LGEfUj2V9NIFH9chI7oYU2DEYmt8=; b=k9dE0G4ag5Fnx9SS5p3L8YYXjqV+wx0Bzsa/FfYdvx83lFSAJuwAeSZ94/nmlGWASO 73RJMuRdlhdrwmndRSiqcLWD84irgrOPkMmACK4USkLgGjAbJ5SraLKR7e/yDfsTA24k e0zVuBTNRfRTOzSBL5Wov01PRKu/PB4lpQt8kU3zgT9mMuNozyQe8NYCQSNNi/NyzK0i 8IVPe9vx1L1fcshIMbwrBhse/kEPT8AJE+dMkBskkmsZzGE5PG7d7soPfUxR8Pa6zSM4 31hgW4/2IpHni4PbldFqDCZ5d02TyPUda1lk3AuzuT2zGtFMC+ycNe9K+0m/EZyGHksv nuNA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763522520; x=1764127320; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=Rljz3QHqavQzM2+LGEfUj2V9NIFH9chI7oYU2DEYmt8=; b=wP7y1cuNm4N1GDEzu89oj0ZDxlHUpgcP4By03dSfOSwhi6o0FaRs6tCSShAM65u4fO otoL1ZwDaVDO6iXlubI9H0VcKiS3kZPXH11BxjOf4sSh1gMGUvrKjH5kQkDkSCaHMREO y0wfMWbRzacEuzLEZT34C/cTjzcz9GgiyRwxVzkDyRlFStI4eLVZ2hg8/iPWkW6cxoi6 pp00tp73B5niDb8kOCxsuyZvTJkKbMArdeItpMExDEP6+ewuKCu+6nRBxdzQ1xNecQTl rkOR++quZqK6qks3oGT/cRSE64BCb+m3gwP7jQVhPAv/4BUy9VjOoMBzt7QuWCyAbiGM 4gNw== X-Forwarded-Encrypted: i=1; AJvYcCXNE8a55hg9kjD18xQdGw+2n+a/YSUcYiJMGCcQawHHcfA3Anf3ODUrHZ3xObF3KDBmcxJecmCwZCcSp7A=@vger.kernel.org X-Gm-Message-State: AOJu0YylsnTpwFS+XXKHvoyuAG4KkfI13vLeAfGYzBR5J7magbE7uhDs H8kUOvWoiV8JRrrAxA8arIaHpSYwXtEnJV6V5C0il8Q69YzV3JBgaZ9Q X-Gm-Gg: ASbGncsJLs6+Q6NpM5JHpg0IPe6FPYH+kPnrPr67NPqAzbpSU5FSre8RPmx9LKgtQFa DI29TOlZfD0Re86oL3Q7mJCcMkssEXJKVm3TLZmxtrxb7svyjUm6qUof9PlhwE8621o/3BMiEJM HrqMI+7cTHPFN6G93KDtTIONpdpG01MHsmM/AgEVvxH+rXpZPZsIT5JfD/TU2Hxt+70z1sMc6lA AKCaFOqF8X5AZtLPyn266LGGk+4kuhoDMun688LuTaJTA1zIkCr2qm/cpO8fSUHZ0nxiuD4fYfs Z0UpVJWWdw0DTHYth+Wv2f4TwQ7M8AzVnUVndbFHgB7HY2fPh25XqMrnXOjjMDUzkfzx6XugA/E 7UkKSbY/GKpig8qzJtOOnE9xflu4XhjEJutaUZdqn4p03Q9TmieFjU1mlpCFPD0+kLt7GAvw5Hn Utbl7JSmVR2UAPHeO/AaWWwVhkkW9zmzK2TBtNog== X-Google-Smtp-Source: AGHT+IGMGm4ssuCAcSuhBLMTVMUN9IlTul3KIQyJF8pQPYcJbxELNk2HFjnnrYFBfI+sDmaW0pEWCA== X-Received: by 2002:a17:902:cf43:b0:248:ff5a:b768 with SMTP id d9443c01a7336-2986a6abcb9mr216810575ad.10.1763522520091; Tue, 18 Nov 2025 19:22:00 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2985c2bed5asm188352485ad.88.2025.11.18.19.21.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 18 Nov 2025 19:21:59 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v7 6/7] btf: Optimize type lookup with binary search Date: Wed, 19 Nov 2025 11:15:30 +0800 Message-Id: <20251119031531.1817099-7-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251119031531.1817099-1-dolinux.peng@gmail.com> References: <20251119031531.1817099-1-dolinux.peng@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" From: Donglin Peng Improve btf_find_by_name_kind() performance by adding binary search support for sorted types. Falls back to linear search for compatibility. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- kernel/bpf/btf.c | 83 ++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 73 insertions(+), 10 deletions(-) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 0de8fc8a0e0b..5dd2c40d4874 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -259,6 +259,7 @@ struct btf { void *nohdr_data; struct btf_header hdr; u32 nr_types; /* includes VOID for base BTF */ + u32 nr_sorted_types; /* exclude VOID for base BTF */ u32 types_size; u32 data_size; refcount_t refcnt; @@ -494,6 +495,11 @@ static bool btf_type_is_modifier(const struct btf_type= *t) return false; } =20 +static int btf_start_id(const struct btf *btf) +{ + return btf->start_id + (btf->base_btf ? 0 : 1); +} + bool btf_type_is_void(const struct btf_type *t) { return t =3D=3D &btf_void; @@ -544,24 +550,78 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +static s32 btf_find_by_name_kind_bsearch(const struct btf *btf, const char= *name, + s32 start_id, s32 end_id) +{ + const struct btf_type *t; + const char *tname; + s32 l, r, m; + + l =3D start_id; + r =3D end_id; + while (l <=3D r) { + m =3D l + (r - l) / 2; + t =3D btf_type_by_id(btf, m); + tname =3D btf_name_by_offset(btf, t->name_off); + if (strcmp(tname, name) >=3D 0) { + if (l =3D=3D r) + return r; + r =3D m; + } else { + l =3D m + 1; + } + } + + return btf_nr_types(btf); +} + s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) { + const struct btf *base_btf =3D btf_base_btf(btf); const struct btf_type *t; const char *tname; - u32 i, total; + int err =3D -ENOENT; =20 - total =3D btf_nr_types(btf); - for (i =3D 1; i < total; i++) { - t =3D btf_type_by_id(btf, i); - if (BTF_INFO_KIND(t->info) !=3D kind) - continue; + if (base_btf) { + err =3D btf_find_by_name_kind(base_btf, name, kind); + if (err > 0) + goto out; + } =20 - tname =3D btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; + if (btf->nr_sorted_types > 0) { + /* binary search */ + s32 start_id, end_id; + u32 idx; + + start_id =3D btf_start_id(btf); + end_id =3D start_id + btf->nr_sorted_types - 1; + idx =3D btf_find_by_name_kind_bsearch(btf, name, start_id, end_id); + for (; idx <=3D end_id; idx++) { + t =3D btf_type_by_id(btf, idx); + tname =3D btf_name_by_offset(btf, t->name_off); + if (strcmp(tname, name)) + goto out; + if (BTF_INFO_KIND(t->info) =3D=3D kind) + return idx; + } + } else { + /* linear search */ + u32 i, total; + + total =3D btf_nr_types(btf); + for (i =3D btf_start_id(btf); i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (BTF_INFO_KIND(t->info) !=3D kind) + continue; + + tname =3D btf_name_by_offset(btf, t->name_off); + if (!strcmp(tname, name)) + return i; + } } =20 - return -ENOENT; +out: + return err; } =20 s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p) @@ -5791,6 +5851,7 @@ static struct btf *btf_parse(const union bpf_attr *at= tr, bpfptr_t uattr, u32 uat goto errout; } env->btf =3D btf; + btf->nr_sorted_types =3D 0; =20 data =3D kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN); if (!data) { @@ -6210,6 +6271,7 @@ static struct btf *btf_parse_base(struct btf_verifier= _env *env, const char *name btf->data =3D data; btf->data_size =3D data_size; btf->kernel_btf =3D true; + btf->nr_sorted_types =3D 0; snprintf(btf->name, sizeof(btf->name), "%s", name); =20 err =3D btf_parse_hdr(env); @@ -6327,6 +6389,7 @@ static struct btf *btf_parse_module(const char *modul= e_name, const void *data, btf->start_id =3D base_btf->nr_types; btf->start_str_off =3D base_btf->hdr.str_len; btf->kernel_btf =3D true; + btf->nr_sorted_types =3D 0; snprintf(btf->name, sizeof(btf->name), "%s", module_name); =20 btf->data =3D kvmemdup(data, data_size, GFP_KERNEL | __GFP_NOWARN); --=20 2.34.1 From nobody Tue Dec 2 02:32:13 2025 Received: from mail-pl1-f173.google.com (mail-pl1-f173.google.com [209.85.214.173]) (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 20E532FDC29 for ; Wed, 19 Nov 2025 03:22:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522525; cv=none; b=HKqcP600dt9wdWJbgu8vZhxojwQKlaNypH/jWRylzO3ztnglmGK//mVjUQdLnUcvZCLzyZwaohpWkv71dG7zWgQT1fWeOFrdw8+iiq7cZ3i31w9W/EcLfFhJ4RBv5ADHI4R6ioDQW07hXJhRvVupRIyGbuW4lHvOuvFPDdowpyo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522525; c=relaxed/simple; bh=ZUKwweoi/8nzVzk7XZ/MU1Z+niGdx/B7murw68s/Bp4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=KP17U07kp36j4qYqBe/XjzSHgIi4f5B8GwBXJD9Mwpl6b3jlyihiTHxa8ROsB2Ck65d+Ojw8GzkS895n/GuxRu4lMJbJe9I8cv3Kn9U/IAaSn9Mlzs60fyFd4FVp49atFsL75wv5e0CH1bth+bIzxxCsF5mq/3LUl8kgKdFcV7M= 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=NdGVl9Zs; arc=none smtp.client-ip=209.85.214.173 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="NdGVl9Zs" Received: by mail-pl1-f173.google.com with SMTP id d9443c01a7336-2955623e6faso57441025ad.1 for ; Tue, 18 Nov 2025 19:22:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763522523; x=1764127323; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=kUmHdLag/Zwi31gDv/2YF21TbKhBrlOl+Tx3LANhSGo=; b=NdGVl9ZsbbzDLLmFX26258QD7CmpTG/7tlEiiG5O/z8FeYhd3AlnkQknAlp+vPz5uB m5ouEedomubjMf6fslIsBRWESdnwiwld5G8pE/IlXeVQgRCArkEsafz+PIlrbYaq1faA gxj6koyT9AYzEItxchEwJ/5UgOGZXuTUF2mNcTXuVRGJgtr7y+rrWTv/EQ53VbP+EZna iysw0NnTwK0WmsTmdiMJ1zVCEUntWOtiXjj0lkGLrTQXlSy4ceKdJX+cTmWyCWySjY8n 9ysnWnXbFDSZZzJe8srS6LzQFsfTWCoTgVK1hAidPDI7TPOsAH7jn4PkXCetjUq5VgDJ zT9Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763522523; x=1764127323; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=kUmHdLag/Zwi31gDv/2YF21TbKhBrlOl+Tx3LANhSGo=; b=H0adMARW850ikcOERfZ+oCjYF18+kBzB1cmGDzr7QqYn9IyLwZLWZMZxjY9L56STMB 1biupn7wpz+CsYEAuK1QgUZEKozUv37qhncMEgHLuy9Rr+rtC68rDneJwDu/3qtko0VP l2I+yObtgTulrQafECDQInjwgr79JKYM96wdn6WRkBk6TQjlU9+tdQOFNV0PcaXVe6i5 6z6CrqmD/N7XL89ENEj90ze/D5ged2wIvfvXak6jZ2zsjZCTAUZ8UZ4zlCN/tlAVmtFi APj2FG7mxzyL6ho4uFExQ1FJmUccG8Xi0rleiY7GJ2evjK600UVjoFTmqxuO+Zv2nU/7 3nLA== X-Forwarded-Encrypted: i=1; AJvYcCWjeRsIWCx8zOTkIjYp9UTYd59hDJrPpn/tLBEkSk4MxqnrNLKcEICmbh0PNUUrrDpjeMHwIMQ4mIRSMTE=@vger.kernel.org X-Gm-Message-State: AOJu0YwBOC4Dn9f1XHFiL8ptHemKQO6IF7KfwsxOFGb/7vRST4ZluXg0 mVWiAMjlnW7z359beQ54NPK1zCYHT4Kj6TiXAvMGTZ/GHbnk8yp19vSp X-Gm-Gg: ASbGncsetLL39l8AfpoOBtaxMAuQ1MsXjVY3TW749wHsSPeQ7SQQ9EF9qjpNPjld/Et QBIolvF16DTgtPPY7cBdVxUgvpyOfFAuWXBoe5Y1ciLADApENflG/otE9MSe/bdaJa8af9czqcl 9j8nvpwSzgZkISYRqCyKRcYa+c57bVj605NzoNy0k2BoH89DFjPgq3aG74ON7bjl3SKCTXMPWsz f5vZetg8Wr50TL+alkgt+aSsAokVwE7mDrdVXUyTnVfBSqz6lU2sWYnUV3MBaaTme+/EtZhGy0q z8QfIykbPafNIlFoH5dTseTmB33ZpRlzVks69HSL0cFXvNVNhaIK4St7CmbK8OP1dAh6+7aJwIk p4sH/EJ9WyFlDDiPdE04dyNW5BK+/Uaw8a3IpYxoybKMH95bXjaFgrIXTXfHFgZinLIl9qKd/yt 3SFkg5L8LzcdVV4MuC6NxqOE9pIN8= X-Google-Smtp-Source: AGHT+IHpy1Aqpxs2EzkI3ifWZtaJJdDt7GcvJc8PdwkSqxfsWG9Ez6wqPI7Bjanrx6M+nXK35mM94Q== X-Received: by 2002:a17:903:2309:b0:298:34b:492c with SMTP id d9443c01a7336-2986a768210mr245315575ad.54.1763522523402; Tue, 18 Nov 2025 19:22:03 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2985c2bed5asm188352485ad.88.2025.11.18.19.22.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 18 Nov 2025 19:22:02 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v7 7/7] btf: Add sorting validation for binary search Date: Wed, 19 Nov 2025 11:15:31 +0800 Message-Id: <20251119031531.1817099-8-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251119031531.1817099-1-dolinux.peng@gmail.com> References: <20251119031531.1817099-1-dolinux.peng@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" From: Donglin Peng Implement validation of BTF type ordering to enable efficient binary search for sorted BTF. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- kernel/bpf/btf.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 64 insertions(+) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 5dd2c40d4874..e9d102360292 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -550,6 +550,66 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +/* Anonymous types (with empty names) are considered greater than named ty= pes + * and are sorted after them. Two anonymous types are considered equal. Na= med + * types are compared lexicographically. + */ +static int btf_compare_type_names(const void *a, const void *b, void *priv) +{ + struct btf *btf =3D (struct btf *)priv; + const struct btf_type *ta =3D btf_type_by_id(btf, *(__u32 *)a); + const struct btf_type *tb =3D btf_type_by_id(btf, *(__u32 *)b); + const char *na, *nb; + + if (!ta->name_off && tb->name_off) + return 1; + if (ta->name_off && !tb->name_off) + return -1; + if (!ta->name_off && !tb->name_off) + return 0; + + na =3D btf_name_by_offset(btf, ta->name_off); + nb =3D btf_name_by_offset(btf, tb->name_off); + return strcmp(na, nb); +} + +/* Verifies that BTF types are sorted in ascending order according to their + * names, with named types appearing before anonymous types. If the orderi= ng + * is correct, counts the number of named types and updates the BTF object= 's + * nr_sorted_types field. Note that vmlinux and kernel module BTFs are sor= ted + * during the building phase, so the validation logic only needs to count = the + * named types. + */ +static void btf_check_sorted(struct btf *btf) +{ + const struct btf_type *t; + int i, n, k =3D 0, nr_sorted_types; + bool skip_cmp =3D btf_is_kernel(btf); + + if (btf->nr_types < 2) + return; + + nr_sorted_types =3D 0; + n =3D btf_nr_types(btf) - 1; + for (i =3D btf_start_id(btf); i < n; i++) { + k =3D i + 1; + if (!skip_cmp && btf_compare_type_names(&i, &k, btf) > 0) + return; + + t =3D btf_type_by_id(btf, i); + if (t->name_off) + nr_sorted_types++; + else if (skip_cmp) + break; + } + + t =3D btf_type_by_id(btf, k); + if (t->name_off) + nr_sorted_types++; + if (nr_sorted_types) + btf->nr_sorted_types =3D nr_sorted_types; +} + static s32 btf_find_by_name_kind_bsearch(const struct btf *btf, const char= *name, s32 start_id, s32 end_id) { @@ -5885,6 +5945,8 @@ static struct btf *btf_parse(const union bpf_attr *at= tr, bpfptr_t uattr, u32 uat if (err) goto errout; =20 + btf_check_sorted(btf); + struct_meta_tab =3D btf_parse_struct_metas(&env->log, btf); if (IS_ERR(struct_meta_tab)) { err =3D PTR_ERR(struct_meta_tab); @@ -6292,6 +6354,7 @@ static struct btf *btf_parse_base(struct btf_verifier= _env *env, const char *name if (err) goto errout; =20 + btf_check_sorted(btf); refcount_set(&btf->refcnt, 1); =20 return btf; @@ -6426,6 +6489,7 @@ static struct btf *btf_parse_module(const char *modul= e_name, const void *data, } =20 btf_verifier_env_free(env); + btf_check_sorted(btf); refcount_set(&btf->refcnt, 1); return btf; =20 --=20 2.34.1