From nobody Sat Feb 7 12:19:39 2026 Received: from mail-pf1-f179.google.com (mail-pf1-f179.google.com [209.85.210.179]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2D95B2F7453 for ; Mon, 20 Oct 2025 09:39:52 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760953194; cv=none; b=O2wQGVEVD3tndjCmLVNoQoyq3+plxxd4KHRwDmoXNJfDUA/+VITDmoqLgSTqvZ2qSC/AGS+UNHOu6/eFCfoz3SinVgIBQdauqtWWqGFkbKrqqPsMYaW6MTVUQ+h4s08rPdwuGthnbvncmQj+4dEmS1UlaDBRFwAi4nSnn7uN9js= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760953194; c=relaxed/simple; bh=ugDn8c1lW1orwqdqhvNXZZRri40gpMmMmMcEemnXh6c=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=pgjeYT/7wRC60hXhoYkTWxGi0WfzNb301Daut0HkqAIwHMAaRgENjoOVih4Xco1oiDYvzfB/ufj4viU6GjOUIztgcOVB8NwLIM0vprJXh4Q9qVudIXhavdHeSqcEi9yXuX15sh14cuT0Y0Z6wKIVdzMyExKaYE5OegfzPbceGGs= 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=j4aL8M+I; arc=none smtp.client-ip=209.85.210.179 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="j4aL8M+I" Received: by mail-pf1-f179.google.com with SMTP id d2e1a72fcca58-781db5068b8so3164485b3a.0 for ; Mon, 20 Oct 2025 02:39:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1760953192; x=1761557992; 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=52FJ4sV7PeUmrKe+3MVtvr5aRK62gcaubO05HKMB1Gs=; b=j4aL8M+I7seDFaslC8lfK/X/ytzafCZqx9oyZh55DmhKKDex5Px24Hq+tBP9nVdG1w BcdlRMuQJ/EyQaY9jcJBkDahPjP7wIKxPDgeYjQ/0RleJh8KUqJ5Uw5h2F8iwbO42Urj qQcyaUVY6n/5NYlSjvvK3M2C7R0pdt2kz1o90JWLPZe+vbZpcqtgNSb+v5DvZgrUW7Yy oyWkN1Zn/54FhKNpxNMAzO9QjYQqjccW9+P5ELQLaMMg2qI1gnprkW5BYE2ed4woWIa3 LEmlyIZcvuPO+M25ZefidjWaBT/390sP0A70UqUzJk9Q/QsCSpz7eeThJ0LQbFaxuyLc 4Q7g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1760953192; x=1761557992; 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=52FJ4sV7PeUmrKe+3MVtvr5aRK62gcaubO05HKMB1Gs=; b=IEh54pLrk7OzaQptD+0WbggAFHsgA2QpLdo3kmwcbkrn6zNwP4HSIlHrHbx/3TRLLN xODsw7upNaO3BZHHhlSqgpKHmi/6zZf6k95uxtt9JzfYdUfWjd4pCjrLFpFM2HUxaZZw 7jnwOjMk+qXniDkIQ2PT/DBLwYEo96safo+Bu8r/vJ6ZgG2nP2MyXvH5lwQZjQEwWMJD wPDPLV6dCVIw6PdKbwkM8CDke14xi2RWM+BVVBvRfePmvAMMjIl2vhdYi0/4qCUxx6zx qvFS1j7UR2cN1FYvpt9Zt6UaZwDkVCpTOZg50O1lW1+3OgxlYZAx2BzmpXQKHzNF0kul RceA== X-Gm-Message-State: AOJu0Yyf7PGLjer/zyNypMBEQyMMlykojqcT0/uqphg0Mhdac9FFFCr2 7FNEl+Bklzlh8ycktkQ64e54hu6ME3SB5lT4yMc8r5m05JNS4IM25QQL X-Gm-Gg: ASbGncvY8we4S19bUCdNw+v6Wq/FdOBfR7nwk+3huPhLlRIySNdIdyW9Oi80/BYEENQ 6iiGAtEQZM6pWG0oswsN9t5pK+ca8kK47VLFPrtswPZehiUYeYKRoXP+RphoJ8Ccq+Vam0YPqVG rcd3XQDQKah7AraQ63ekb2FEGRo74HFHNHWaxeYRq1azvX/r/prhGiu6LlwcMmAaVi+EgBUA/aU H4EEUk8WWBDY8WaOXgzsBTKua4ZqzYRlPC8y7Ssnv+6WLL1R3RR0H9/TCy4/c/m7W4H2JXEdil2 GMyhHxSkwAeeX5JMJw8EOEV0scyWAWfDnb2MJ1zz2Qzd/kFVET4uZ2yffMJpfJkgSP1ZGNQG9eQ ZL12sAvKw4LrYmUbxefZZQWXYM0BUy+8auqArPe8Jv1EkDJlThr0K4zVoZuEX8lBguf/H++QaRi wtLcncvvqKMPSVwTVGexQNOo6x1Zo= X-Google-Smtp-Source: AGHT+IEchgGNOZqdezdEtqnT/rI36dWl4KIQU1k/DQ/xqsCVOOSCdlbhYXFAwti9fT8qv9KnNzaQvQ== X-Received: by 2002:a17:90b:3dcb:b0:32e:b87e:a961 with SMTP id 98e67ed59e1d1-33bcf85b526mr14610819a91.5.1760953192310; Mon, 20 Oct 2025 02:39:52 -0700 (PDT) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-33d5de8091fsm7617200a91.19.2025.10.20.02.39.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 20 Oct 2025 02:39:51 -0700 (PDT) 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 v2 1/5] btf: search local BTF before base BTF Date: Mon, 20 Oct 2025 17:39:37 +0800 Message-Id: <20251020093941.548058-2-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251020093941.548058-1-dolinux.peng@gmail.com> References: <20251020093941.548058-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" Change btf_find_by_name_kind() to search the local BTF first, then fall back to the base BTF. This can skip traversing the large vmlinux BTF when the target type resides in a kernel module's BTF, thereby significantly improving lookup performance. In a test searching for the btf_type of function ext2_new_inode located in the ext2 kernel module: Before: 408631 ns After: 499 ns Performance improvement: ~819x faster Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- include/linux/btf.h | 1 + kernel/bpf/btf.c | 27 ++++++++++++++++++--------- 2 files changed, 19 insertions(+), 9 deletions(-) diff --git a/include/linux/btf.h b/include/linux/btf.h index f06976ffb63f..ddc53a7ac7cd 100644 --- a/include/linux/btf.h +++ b/include/linux/btf.h @@ -220,6 +220,7 @@ bool btf_is_module(const struct btf *btf); bool btf_is_vmlinux(const struct btf *btf); struct module *btf_try_get_module(const struct btf *btf); u32 btf_nr_types(const struct btf *btf); +u32 btf_type_cnt(const struct btf *btf); struct btf *btf_base_btf(const struct btf *btf); bool btf_type_is_i32(const struct btf_type *t); bool btf_type_is_i64(const struct btf_type *t); diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 0de8fc8a0e0b..c414cf37e1bd 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -544,22 +544,31 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +u32 btf_type_cnt(const struct btf *btf) +{ + return btf->start_id + btf->nr_types; +} + s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) { const struct btf_type *t; const char *tname; u32 i, total; =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; + do { + total =3D btf_type_cnt(btf); + for (i =3D btf->start_id; i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (BTF_INFO_KIND(t->info) !=3D kind) + continue; =20 - tname =3D btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; - } + tname =3D btf_name_by_offset(btf, t->name_off); + if (!strcmp(tname, name)) + return i; + } + + btf =3D btf->base_btf; + } while (btf); =20 return -ENOENT; } --=20 2.34.1 From nobody Sat Feb 7 12:19:39 2026 Received: from mail-pj1-f49.google.com (mail-pj1-f49.google.com [209.85.216.49]) (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 200C82F83AB for ; Mon, 20 Oct 2025 09:39:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.49 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760953199; cv=none; b=jADRhRh0YQu8R0tqbgFbkYTm/xjV+zp3rGnmuxkBDSp5ZxLm8pXY/zxNY/hlOeQMYIvFd2CSOhuRLjXMfU4DiY2td0XiDz4pOlRak5gUYfVO8GKNOsK9QWzUZcC89wlId5oazfExGbSdb5Sc+WcCZEvGEwfKxuiIoPDaW1xXx88= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760953199; c=relaxed/simple; bh=48MK3IVfFVIaq7wrnsVF/K0MzzVMTV/KG7hzT0Z3/M8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=fXj9AY2A339CBLXlifMyYV57t1K/SlKG6sJsn6vPKQwXBRoUEu9RjvpWpQ8bUgdR3HFJ8DgCgozw2aj26HgIjSRNEdiqDD0OvzF10W6bjg0po+M0s62+y98wDp8AlYdIXiymj83oQ+PJBguIlgBgnLlR05o+NUSuo04xWbpYs4A= 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=k4V9tj2K; arc=none smtp.client-ip=209.85.216.49 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="k4V9tj2K" Received: by mail-pj1-f49.google.com with SMTP id 98e67ed59e1d1-339d53f4960so4185549a91.3 for ; Mon, 20 Oct 2025 02:39:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1760953196; x=1761557996; 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=mnQBz8V7xJnhNMAVJ8Qx/WiCqXppL5cjjvDtlWap4Rc=; b=k4V9tj2Kgt391tuMso8RQF7TVzNCmuZcFgDNDzuW3jiNVLGsCjkHzE2Nkw9UQIx/+g GK3OfWFQJc3oHLvN+dwIpHN0U/z9bXykyWNAA4bPQo/TVatCs7NNUIs9k5ymWNhvTL0Q VtEThZQqQqxl5WzFTcU+kr22BesP41jm5o0y3kPuJItMiyFVogXdtRtAJmjCytmEX7fY MFHHgmtnXWZf6tf7nmxVxnPrYRueLjwwpvHFq+se8eRUZGIt7ciwMeM2D29UF26PqW8o W9uW1nGmEwntJeRblsF4aJ4dyrpuH1kV4lzFZeajLeKC9MwLFGgkeyUV7RXfokE0a+Ei tr5A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1760953196; x=1761557996; 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=mnQBz8V7xJnhNMAVJ8Qx/WiCqXppL5cjjvDtlWap4Rc=; b=d6igQoiPhZayS7amVXfmAFtOaihKsEm0ZmJE4JEav0QvN1gIw/StC4mRjkDGeT/WyD wpLZlR0Vjhq5IxGqeH9uSJy97gyqU05kC/leTyu6dE+B/352yM1RCI+etMluQIXBzKKL wc2g29+MOGsUwrucIOLOdYNFoo9jFuHho+4/gWStCA5NdCDjN7FeRWXEBr7UuIfWSkO3 HK9y0KppeSooSIIitfx4+YoX0nh1CGNXmdSrMvcm6/cJcE7ohlwf875F8kruLRsPQitS gZjT0zTLaf9Yv1z8OQKrNbnqEV47KfFAPcY0+30NAlgXzh+10o7Bxh2QozWo8+XvB0BV GO8g== X-Gm-Message-State: AOJu0YystyoUJrQyV92ZaWTsKiLAw+TKso16iYEhH09FjEnUcMmEpvbP qG1j14X0RuX5QPFhEXl3fZDdQV98FXmV2bXNaEBv5i6H0WTT55rXEw6r X-Gm-Gg: ASbGncsH7UYhrlAcV/lMz5S7T2i2AC3Z5dkMRv3WyuwsrvEF1Y+oHAQBeRuveOKxSDN gg7Yb9XTGN+FyuxQAuZJQuys/T1RPq/niec5JhKbaAmsT+Ld5y8DFVsk3bqBxIuyvoPdzqBEdBF DFnVlc/gcUErtJjl/fD/eQaM4l3efLEUe2l3x2kugR7y5AyF4sHozsBVfEe1gbMRmEyfrB3uL09 ktZn7KDZC+ZrixWgSrLhcs8div8b8YtZlsoEjppR+5p7yAsJmQTqMEVREV54Wc9aC6p8qiwgSDZ K3pUXc/lISvxUzQ2Di4XER3o7WPcllaIqKCVWp25YYoxJzN0gjVBVUhqBc4raKDwVKMUAcFVYWH v0vVfBJ7yBn3p/4IDt9IZV6booP6FsfeJxL/wuQIoTpda2WbDRKBRMysX9/eNM8ji1W83KZVYBX NeLwKzeN3vJeZaVXNWkN0nm7iZSKc= X-Google-Smtp-Source: AGHT+IFq4jAfdunN994zMtpGY6z7ZtgIpa/ZkkUYRiTLUokYOLHEZQIi0txVjYjHlZ2s2/heMjdjUQ== X-Received: by 2002:a17:90b:3d8a:b0:330:6f16:c4e0 with SMTP id 98e67ed59e1d1-33bcf87f43dmr18355066a91.12.1760953196306; Mon, 20 Oct 2025 02:39:56 -0700 (PDT) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-33d5de8091fsm7617200a91.19.2025.10.20.02.39.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 20 Oct 2025 02:39:55 -0700 (PDT) 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 v2 2/5] btf: sort BTF types by kind and name to enable binary search Date: Mon, 20 Oct 2025 17:39:38 +0800 Message-Id: <20251020093941.548058-3-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251020093941.548058-1-dolinux.peng@gmail.com> References: <20251020093941.548058-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" This patch implements sorting of BTF types by their kind and name, enabling the use of binary search for type lookups. To share logic between kernel and libbpf, a new btf_sort.c file is introduced containing common sorting functionality. The sorting is performed during btf__dedup() when the new sort_by_kind_name option in btf_dedup_opts is enabled. For vmlinux and kernel module BTF, btf_check_sorted() verifies whether the types are sorted and binary search can be used. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Co-developed-by: Eduard Zingerman Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- include/linux/btf.h | 20 +++- kernel/bpf/Makefile | 1 + kernel/bpf/btf.c | 39 ++++---- kernel/bpf/btf_sort.c | 2 + tools/lib/bpf/Build | 2 +- tools/lib/bpf/btf.c | 163 +++++++++++++++++++++++++++----- tools/lib/bpf/btf.h | 2 + tools/lib/bpf/btf_sort.c | 159 +++++++++++++++++++++++++++++++ tools/lib/bpf/libbpf_internal.h | 6 ++ 9 files changed, 347 insertions(+), 47 deletions(-) create mode 100644 kernel/bpf/btf_sort.c create mode 100644 tools/lib/bpf/btf_sort.c diff --git a/include/linux/btf.h b/include/linux/btf.h index ddc53a7ac7cd..c6fe5e689ab9 100644 --- a/include/linux/btf.h +++ b/include/linux/btf.h @@ -221,7 +221,10 @@ bool btf_is_vmlinux(const struct btf *btf); struct module *btf_try_get_module(const struct btf *btf); u32 btf_nr_types(const struct btf *btf); u32 btf_type_cnt(const struct btf *btf); -struct btf *btf_base_btf(const struct btf *btf); +u32 btf_start_id(const struct btf *btf); +u32 btf_nr_sorted_types(const struct btf *btf); +void btf_set_nr_sorted_types(struct btf *btf, u32 nr); +struct btf* btf_base_btf(const struct btf *btf); bool btf_type_is_i32(const struct btf_type *t); bool btf_type_is_i64(const struct btf_type *t); bool btf_type_is_primitive(const struct btf_type *t); @@ -595,6 +598,10 @@ int get_kern_ctx_btf_id(struct bpf_verifier_log *log, = enum bpf_prog_type prog_ty bool btf_types_are_same(const struct btf *btf1, u32 id1, const struct btf *btf2, u32 id2); int btf_check_iter_arg(struct btf *btf, const struct btf_type *func, int a= rg_idx); +int btf_compare_type_kinds_names(const void *a, const void *b, void *priv); +s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const char = *type_name, + u32 kind); +void btf_check_sorted(struct btf *btf, int start_id); =20 static inline bool btf_type_is_struct_ptr(struct btf *btf, const struct bt= f_type *t) { @@ -683,5 +690,16 @@ static inline int btf_check_iter_arg(struct btf *btf, = const struct btf_type *fun { return -EOPNOTSUPP; } +static inline int btf_compare_type_kinds_names(const void *a, const void *= b, void *priv) +{ + return -EOPNOTSUPP; +} +static inline s32 find_btf_by_name_kind(const struct btf *btf, int start_i= d, const char *type_name, + u32 kind) +{ + return -EOPNOTSUPP; +} +static inline void btf_check_sorted(struct btf *btf, int start_id); +{} #endif #endif diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile index 7fd0badfacb1..c9d8f986c7e1 100644 --- a/kernel/bpf/Makefile +++ b/kernel/bpf/Makefile @@ -56,6 +56,7 @@ obj-$(CONFIG_BPF_SYSCALL) +=3D kmem_cache_iter.o ifeq ($(CONFIG_DMA_SHARED_BUFFER),y) obj-$(CONFIG_BPF_SYSCALL) +=3D dmabuf_iter.o endif +obj-$(CONFIG_BPF_SYSCALL) +=3D btf_sort.o =20 CFLAGS_REMOVE_percpu_freelist.o =3D $(CC_FLAGS_FTRACE) CFLAGS_REMOVE_bpf_lru_list.o =3D $(CC_FLAGS_FTRACE) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index c414cf37e1bd..11b05f4eb07d 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; u32 types_size; u32 data_size; refcount_t refcnt; @@ -544,33 +545,29 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 -u32 btf_type_cnt(const struct btf *btf) +u32 btf_start_id(const struct btf *btf) { - return btf->start_id + btf->nr_types; + return btf->start_id; } =20 -s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) +u32 btf_nr_sorted_types(const struct btf *btf) { - const struct btf_type *t; - const char *tname; - u32 i, total; - - do { - total =3D btf_type_cnt(btf); - for (i =3D btf->start_id; i < total; i++) { - t =3D btf_type_by_id(btf, i); - if (BTF_INFO_KIND(t->info) !=3D kind) - continue; + return btf->nr_sorted_types; +} =20 - tname =3D btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; - } +void btf_set_nr_sorted_types(struct btf *btf, u32 nr) +{ + btf->nr_sorted_types =3D nr; +} =20 - btf =3D btf->base_btf; - } while (btf); +u32 btf_type_cnt(const struct btf *btf) +{ + return btf->start_id + btf->nr_types; +} =20 - return -ENOENT; +s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) +{ + return find_btf_by_name_kind(btf, 1, name, kind); } =20 s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p) @@ -6239,6 +6236,7 @@ static struct btf *btf_parse_base(struct btf_verifier= _env *env, const char *name if (err) goto errout; =20 + btf_check_sorted(btf, 1); refcount_set(&btf->refcnt, 1); =20 return btf; @@ -6371,6 +6369,7 @@ static struct btf *btf_parse_module(const char *modul= e_name, const void *data, base_btf =3D vmlinux_btf; } =20 + btf_check_sorted(btf, btf_nr_types(base_btf)); btf_verifier_env_free(env); refcount_set(&btf->refcnt, 1); return btf; diff --git a/kernel/bpf/btf_sort.c b/kernel/bpf/btf_sort.c new file mode 100644 index 000000000000..898f9189952c --- /dev/null +++ b/kernel/bpf/btf_sort.c @@ -0,0 +1,2 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) +#include "../../tools/lib/bpf/btf_sort.c" diff --git a/tools/lib/bpf/Build b/tools/lib/bpf/Build index c80204bb72a2..ed7c2506e22d 100644 --- a/tools/lib/bpf/Build +++ b/tools/lib/bpf/Build @@ -1,4 +1,4 @@ libbpf-y :=3D libbpf.o bpf.o nlattr.o btf.o libbpf_utils.o \ netlink.o bpf_prog_linfo.o libbpf_probes.o hashmap.o \ btf_dump.o ringbuf.o strset.o linker.o gen_loader.o relo_core.o \ - usdt.o zip.o elf.o features.o btf_iter.o btf_relocate.o + usdt.o zip.o elf.o features.o btf_iter.o btf_relocate.o btf_sort.o diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 18907f0fcf9f..87e47f0b78ba 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -1,6 +1,9 @@ // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) /* Copyright (c) 2018 Facebook */ =20 +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif #include #include #include @@ -92,6 +95,9 @@ struct btf { * - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; + /* number of named types in this BTF instance for binary search + */ + __u32 nr_sorted_types; /* if not NULL, points to the base BTF on top of which the current * split BTF is based */ @@ -619,6 +625,21 @@ __u32 btf__type_cnt(const struct btf *btf) return btf->start_id + btf->nr_types; } =20 +__u32 btf__start_id(const struct btf *btf) +{ + return btf->start_id; +} + +__u32 btf__nr_sorted_types(const struct btf *btf) +{ + return btf->nr_sorted_types; +} + +void btf__set_nr_sorted_types(struct btf *btf, __u32 nr) +{ + btf->nr_sorted_types =3D nr; +} + const struct btf *btf__base_btf(const struct btf *btf) { return btf->base_btf; @@ -915,38 +936,16 @@ __s32 btf__find_by_name(const struct btf *btf, const = char *type_name) return libbpf_err(-ENOENT); } =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; - - 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(-ENOENT); -} - __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_n= ame, __u32 kind) { - return btf_find_by_name_kind(btf, btf->start_id, type_name, kind); + return find_btf_by_name_kind(btf, btf->start_id, type_name, kind); } =20 __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name, __u32 kind) { - return btf_find_by_name_kind(btf, 1, type_name, kind); + return find_btf_by_name_kind(btf, 1, type_name, kind); } =20 static bool btf_is_modifiable(const struct btf *btf) @@ -3411,6 +3410,7 @@ static int btf_dedup_struct_types(struct btf_dedup *d= ); static int btf_dedup_ref_types(struct btf_dedup *d); static int btf_dedup_resolve_fwds(struct btf_dedup *d); static int btf_dedup_compact_types(struct btf_dedup *d); +static int btf_dedup_compact_and_sort_types(struct btf_dedup *d); static int btf_dedup_remap_types(struct btf_dedup *d); =20 /* @@ -3600,7 +3600,7 @@ int btf__dedup(struct btf *btf, const struct btf_dedu= p_opts *opts) pr_debug("btf_dedup_ref_types failed: %s\n", errstr(err)); goto done; } - err =3D btf_dedup_compact_types(d); + err =3D btf_dedup_compact_and_sort_types(d); if (err < 0) { pr_debug("btf_dedup_compact_types failed: %s\n", errstr(err)); goto done; @@ -3649,6 +3649,8 @@ struct btf_dedup { * BTF is considered to be immutable. */ bool hypot_adjust_canon; + /* Sort btf_types by kind and time */ + bool sort_by_kind_name; /* Various option modifying behavior of algorithm */ struct btf_dedup_opts opts; /* temporary strings deduplication state */ @@ -3741,6 +3743,7 @@ static struct btf_dedup *btf_dedup_new(struct btf *bt= f, const struct btf_dedup_o =20 d->btf =3D btf; d->btf_ext =3D OPTS_GET(opts, btf_ext, NULL); + d->sort_by_kind_name =3D OPTS_GET(opts, sort_by_kind_name, false); =20 d->dedup_table =3D hashmap__new(hash_fn, btf_dedup_equal_fn, NULL); if (IS_ERR(d->dedup_table)) { @@ -5288,6 +5291,116 @@ static int btf_dedup_compact_types(struct btf_dedup= *d) return 0; } =20 +static __u32 *get_sorted_canon_types(struct btf_dedup *d, __u32 *cnt) +{ + int i, j, id, types_cnt =3D 0; + __u32 *sorted_ids; + + for (i =3D 0, id =3D d->btf->start_id; i < d->btf->nr_types; i++, id++) + if (d->map[id] =3D=3D id) + ++types_cnt; + + sorted_ids =3D calloc(types_cnt, sizeof(*sorted_ids)); + if (!sorted_ids) + return NULL; + + for (j =3D 0, i =3D 0, id =3D d->btf->start_id; i < d->btf->nr_types; i++= , id++) + if (d->map[id] =3D=3D id) + sorted_ids[j++] =3D id; + + qsort_r(sorted_ids, types_cnt, sizeof(*sorted_ids), + btf_compare_type_kinds_names, d->btf); + + *cnt =3D types_cnt; + + return sorted_ids; +} + +/* + * Compact and sort BTF types. + * + * Similar to btf_dedup_compact_types, but additionally sorts the btf_type= s. + */ +static int btf__dedup_compact_and_sort_types(struct btf_dedup *d) +{ + __u32 canon_types_cnt =3D 0, canon_types_len =3D 0; + __u32 *new_offs =3D NULL, *canon_types =3D NULL; + const struct btf_type *t; + void *p, *new_types =3D NULL; + int i, id, len, err; + + /* we are going to reuse hypot_map to store compaction remapping */ + d->hypot_map[0] =3D 0; + /* base BTF types are not renumbered */ + for (id =3D 1; id < d->btf->start_id; id++) + d->hypot_map[id] =3D id; + for (i =3D 0, id =3D d->btf->start_id; i < d->btf->nr_types; i++, id++) + d->hypot_map[id] =3D BTF_UNPROCESSED_ID; + + canon_types =3D get_sorted_canon_types(d, &canon_types_cnt); + if (!canon_types) { + err =3D -ENOMEM; + goto out_err; + } + + for (i =3D 0; i < canon_types_cnt; i++) { + id =3D canon_types[i]; + t =3D btf__type_by_id(d->btf, id); + len =3D btf_type_size(t); + if (len < 0) { + err =3D len; + goto out_err; + } + canon_types_len +=3D len; + } + + new_offs =3D calloc(canon_types_cnt, sizeof(*new_offs)); + new_types =3D calloc(canon_types_len, 1); + if (!new_types || !new_offs) { + err =3D -ENOMEM; + goto out_err; + } + + p =3D new_types; + + for (i =3D 0; i < canon_types_cnt; i++) { + id =3D canon_types[i]; + t =3D btf__type_by_id(d->btf, id); + len =3D btf_type_size(t); + memcpy(p, t, len); + d->hypot_map[id] =3D d->btf->start_id + i; + new_offs[i] =3D p - new_types; + p +=3D len; + } + + /* shrink struct btf's internal types index and update btf_header */ + free(d->btf->types_data); + free(d->btf->type_offs); + d->btf->types_data =3D new_types; + d->btf->type_offs =3D new_offs; + d->btf->types_data_cap =3D canon_types_len; + d->btf->type_offs_cap =3D canon_types_cnt; + d->btf->nr_types =3D canon_types_cnt; + d->btf->hdr->type_len =3D canon_types_len; + d->btf->hdr->str_off =3D d->btf->hdr->type_len; + d->btf->raw_size =3D d->btf->hdr->hdr_len + d->btf->hdr->type_len + d->bt= f->hdr->str_len; + free(canon_types); + return 0; + +out_err: + free(canon_types); + free(new_types); + free(new_offs); + return err; +} + +static int btf_dedup_compact_and_sort_types(struct btf_dedup *d) +{ + if (d->sort_by_kind_name) + return btf__dedup_compact_and_sort_types(d); + return btf_dedup_compact_types(d); +} + /* * Figure out final (deduplicated and compacted) type ID for provided orig= inal * `type_id` by first resolving it into corresponding canonical type ID and diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h index ccfd905f03df..9a7cfe6b4bb3 100644 --- a/tools/lib/bpf/btf.h +++ b/tools/lib/bpf/btf.h @@ -251,6 +251,8 @@ struct btf_dedup_opts { size_t sz; /* optional .BTF.ext info to dedup along the main BTF info */ struct btf_ext *btf_ext; + /* Sort btf_types by kind and name */ + bool sort_by_kind_name; /* force hash collisions (used for testing) */ bool force_collisions; size_t :0; diff --git a/tools/lib/bpf/btf_sort.c b/tools/lib/bpf/btf_sort.c new file mode 100644 index 000000000000..2ad4a56f1c08 --- /dev/null +++ b/tools/lib/bpf/btf_sort.c @@ -0,0 +1,159 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) + +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif + +#ifdef __KERNEL__ +#include +#include +#include + +#define btf_type_by_id (struct btf_type *)btf_type_by_id +#define btf__str_by_offset btf_str_by_offset +#define btf__name_by_offset btf_name_by_offset +#define btf__type_cnt btf_nr_types +#define btf__start_id btf_start_id +#define btf__nr_sorted_types btf_nr_sorted_types +#define btf__set_nr_sorted_types btf_set_nr_sorted_types +#define btf__base_btf btf_base_btf +#define libbpf_err(x) x + +#else + +#include "btf.h" +#include "bpf.h" +#include "libbpf.h" +#include "libbpf_internal.h" + +#endif /* __KERNEL__ */ + +/* Skip the sorted check if number of btf_types is below threshold + */ +#define BTF_CHECK_SORT_THRESHOLD 8 + +struct btf; + +static int cmp_btf_kind_name(int ka, const char *na, int kb, const char *n= b) +{ + return (ka - kb) ?: strcmp(na, nb); +} + +/* + * Sort BTF types by kind and name in ascending order, placing named types + * before anonymous ones. + */ +int btf_compare_type_kinds_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; + int ka, kb; + + /* ta w/o name is greater than tb */ + if (!ta->name_off && tb->name_off) + return 1; + /* tb w/o name is smaller than ta */ + if (ta->name_off && !tb->name_off) + return -1; + + ka =3D btf_kind(ta); + kb =3D btf_kind(tb); + na =3D btf__str_by_offset(btf, ta->name_off); + nb =3D btf__str_by_offset(btf, tb->name_off); + + return cmp_btf_kind_name(ka, na, kb, nb); +} + +__s32 find_btf_by_name_kind(const struct btf *btf, int start_id, + const char *type_name, __u32 kind) +{ + const struct btf_type *t; + const char *tname; + __u32 i, total; + + if (kind =3D=3D BTF_KIND_UNKN || !strcmp(type_name, "void")) + return 0; + + do { + if (btf__nr_sorted_types(btf)) { + /* binary search */ + __s32 start, end, mid, found =3D -1; + int ret; + + start =3D btf__start_id(btf); + end =3D start + btf__nr_sorted_types(btf) - 1; + /* found the leftmost btf_type that matches */ + while(start <=3D end) { + mid =3D start + (end - start) / 2; + t =3D btf_type_by_id(btf, mid); + tname =3D btf__name_by_offset(btf, t->name_off); + ret =3D cmp_btf_kind_name(BTF_INFO_KIND(t->info), tname, + kind, type_name); + if (ret =3D=3D 0) + found =3D mid; + if (ret < 0) + start =3D mid + 1; + else if (ret >=3D 0) + end =3D mid - 1; + } + + if (found !=3D -1) + return found; + } else { + /* linear search */ + total =3D btf__type_cnt(btf); + for (i =3D btf__start_id(btf); i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (btf_kind(t) !=3D kind) + continue; + + tname =3D btf__name_by_offset(btf, t->name_off); + if (tname && !strcmp(tname, type_name)) + return i; + } + } + + btf =3D btf__base_btf(btf); + } while (btf && btf__start_id(btf) >=3D start_id); + + return libbpf_err(-ENOENT); +} + +void btf_check_sorted(struct btf *btf, int start_id) +{ + const struct btf_type *t; + int i, n, nr_sorted_types; + + n =3D btf__type_cnt(btf); + if ((n - start_id) < BTF_CHECK_SORT_THRESHOLD) + return; + + n--; + nr_sorted_types =3D 0; + for (i =3D start_id; i < n; i++) { + int k =3D i + 1; + + t =3D btf_type_by_id(btf, i); + if (!btf__str_by_offset(btf, t->name_off)) + return; + + t =3D btf_type_by_id(btf, k); + if (!btf__str_by_offset(btf, t->name_off)) + return; + + if (btf_compare_type_kinds_names(&i, &k, btf) > 0) + return; + + if (t->name_off) + nr_sorted_types++; + } + + t =3D btf_type_by_id(btf, start_id); + if (t->name_off) + nr_sorted_types++; + if (nr_sorted_types >=3D BTF_CHECK_SORT_THRESHOLD) + btf__set_nr_sorted_types(btf, nr_sorted_types); +} + diff --git a/tools/lib/bpf/libbpf_internal.h b/tools/lib/bpf/libbpf_interna= l.h index 35b2527bedec..f71f3e70c51c 100644 --- a/tools/lib/bpf/libbpf_internal.h +++ b/tools/lib/bpf/libbpf_internal.h @@ -248,6 +248,12 @@ const struct btf_type *skip_mods_and_typedefs(const st= ruct btf *btf, __u32 id, _ const struct btf_header *btf_header(const struct btf *btf); void btf_set_base_btf(struct btf *btf, const struct btf *base_btf); int btf_relocate(struct btf *btf, const struct btf *base_btf, __u32 **id_m= ap); +int btf_compare_type_kinds_names(const void *a, const void *b, void *priv); +__s32 find_btf_by_name_kind(const struct btf *btf, int start_id, const cha= r *type_name, __u32 kind); +void btf_check_sorted(struct btf *btf, int start_id); +__u32 btf__start_id(const struct btf *btf); +__u32 btf__nr_sorted_types(const struct btf *btf); +void btf__set_nr_sorted_types(struct btf *btf, __u32 nr); =20 static inline enum btf_func_linkage btf_func_linkage(const struct btf_type= *t) { --=20 2.34.1 From nobody Sat Feb 7 12:19:39 2026 Received: from mail-pj1-f45.google.com (mail-pj1-f45.google.com [209.85.216.45]) (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 8434A2F83C9 for ; Mon, 20 Oct 2025 09:40:00 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.45 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760953202; cv=none; b=XCyojrMM/3jCLnKCrnekuG2kTD4BQm8tpjD7TsojOe9/0iNchFI3KsN8Rj/ZeJsxV6Oft4HI+87+VplACLQZ69QqrzMDXkNjRBNVwVllJ9U7axTc3vSvr54mSUXs0uDwv5MLhiJY93qZXebUx///o6Jvbvo/BbshHZZwJB5i+oQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760953202; c=relaxed/simple; bh=JiMogRgbGInBSVOsYygafwOmjgI5Wy/DT/oysvwSgB0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=b+/UX7DEqXRSMDidfEvqimXsvt6E1YrFE+5pEIThuL8cJOOeEqszM9JQ3rN9GLbJKzlG6Xwhoaj45bboOYQAEKxoN16uMhsX0xaCt+TOD3YD/sQFAlA0WTdl5O/iSeNpknV1JAVsE8AbCo/3B90opfgS2z4J2DQBwlsXbIgwmqg= 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=GtfMpC4h; arc=none smtp.client-ip=209.85.216.45 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="GtfMpC4h" Received: by mail-pj1-f45.google.com with SMTP id 98e67ed59e1d1-339d7c4039aso3619078a91.0 for ; Mon, 20 Oct 2025 02:40:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1760953200; x=1761558000; 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=e+GuI+F+NaWE59KJ/k9RtDwOss9C7K5SDMuWex2KGKo=; b=GtfMpC4hrDbaFi6uNcfeZGjQ10k2P6U0iAPd6ePnvnDhCSnPp9TT5+mbGx3gY5qhw0 dSX0RH9WywbL6x4hhnUh6bNsLpqj9LL/TY9GAqrhXoNRjdNQDaxch4PIS7PYiUIixWmU mOJ9/+AZTsD4Y6nRt1OakoibY7/wTjCjtQKHZM0V6A+wHOBOF6J3jP2lTjZPZ+Ptxjq9 NSYB4h+oXpKjdUgJ3OBLtXODaxA163vOLy8xubv7LXlv1qfgQhOvn40Oyi4OfMM6AHws ISuU51VDn1WGh8b/bLr6QV3r3hjTHRoOxmj3vUv51AjfBzey8ttEtUBL2Oc00f4key7V YHbA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1760953200; x=1761558000; 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=e+GuI+F+NaWE59KJ/k9RtDwOss9C7K5SDMuWex2KGKo=; b=knQvlyl/V5vX85i6+RV289mDX35UyohgqMfhnRI9PDBNhfk0lrNzO0AHoaE7Ve5P2w cIRJaJbQWKiWasJgRGcY7NIKtWDLskmvSeplTnMLG/iQ6+X1rbHYGUReoK6gZN0Fj1c+ tQgjqkBezmXQ5bG2n0B4K4FR3hv7SqgHD2LJhRSlWOvNyUSZC6GJW03zzINUlIn5i7j2 jagwqyyD4xlR1kQN3KvVWe4NzNljZaVQq7JK5/kHwQC75Mz1m1Uus2oO/et+Q5JD7pOw AgFe5zL1PaUy7qjk2vQMeB2e9TsUxoMNOBhrM0haszysx+rloSEgiweTyRqp2aGUx76h +tuQ== X-Gm-Message-State: AOJu0Yxt2d7BfRSw83eYS/rmV3FLDLOY3tKIGWRSTYw67sizugtTlD+5 k6Mn482dVS++wnLDyFYlMKMCzFwrYaR+4PV6WtnliuPMC35RelqP8l+t X-Gm-Gg: ASbGncsRcnBi3tEWJRFjZWtVp7dwd1fBXf1mm1pFNGt7l9v7UlkG6Ret550g4YLeZ5U 6kbOG4j4M683pSch3A8IlNtcZK3rFI49W4njL/2pWm6Ut6cXXQwU9oMN3yC3BmihFapuc4aLyPM jEgu+/bm4h1SSIFfQX8dr8M6ZH4YAureclFNxJ5070+gT8NkMeYuNWCYBLngdI+aALW/rrcwsB0 tYPVfp2GltDeVdkzWu6dv9nayHrWUMhI+kDPOef7L5zVp3PX//k3yF/YG2B222KWzLfqa/zbXsO TBkpfM2PEuWExDLrhnxNrdPVEzR5QNWC9UJAZXSPp/RuZXEnB1xPQzK8qbbj7+dgih8paSGHTMr xQSnv6Gb0Rte4MawhNOe/JjMoqkzsz/XcE9Nv7E1Cl6nGUY6oN3c3tHXANTCa38EvuMujgnbLMB O5A24hiRIcbS/lqfBpWD6hrxfy5WU= X-Google-Smtp-Source: AGHT+IGe3SkLpqxFGaI/6R57SnMYrFhU59st2Lrt2ihDY77Hqt1qbILgggp368MUDEPo1pjndWr6mA== X-Received: by 2002:a17:90b:1dc6:b0:339:a4ef:c8b1 with SMTP id 98e67ed59e1d1-33bcf8f7802mr16406334a91.22.1760953199716; Mon, 20 Oct 2025 02:39:59 -0700 (PDT) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-33d5de8091fsm7617200a91.19.2025.10.20.02.39.56 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 20 Oct 2025 02:39:58 -0700 (PDT) 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 v2 3/5] libbpf: check if BTF is sorted to enable binary search Date: Mon, 20 Oct 2025 17:39:39 +0800 Message-Id: <20251020093941.548058-4-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251020093941.548058-1-dolinux.peng@gmail.com> References: <20251020093941.548058-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" Now that libbpf supports sorted BTF types, add a check to determine whether binary search can be used for type lookups. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 6 ++++++ 1 file changed, 6 insertions(+) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 87e47f0b78ba..92c370fe9b79 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -1091,6 +1091,8 @@ static struct btf *btf_new(const void *data, __u32 si= ze, struct btf *base_btf, b if (err) goto done; =20 + btf_check_sorted(btf, btf->start_id); + done: if (err) { btf__free(btf); @@ -1714,6 +1716,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 @@ -5456,6 +5459,9 @@ static int btf_dedup_remap_types(struct btf_dedup *d) } } =20 + if (d->sort_by_kind_name) + btf_check_sorted(d->btf, d->btf->start_id); + if (!d->btf_ext) return 0; =20 --=20 2.34.1 From nobody Sat Feb 7 12:19:39 2026 Received: from mail-pj1-f46.google.com (mail-pj1-f46.google.com [209.85.216.46]) (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 D693C2FC02F for ; Mon, 20 Oct 2025 09:40:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.46 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760953205; cv=none; b=Zg0ofNMGVZxNkxVqkuKwaItEOSpfZ1KOrsqZ/ow6LL5WXk7GnGftg9L5K4BK+5fTbIImXg7I02gt7LPCfMvGLJwjQsILUQvtu0qpgL/u2lABreUSO2J37InGWUdlTGnzogQ6IRaw/k7bGw75OLYUEG0WbMYhSGUSCXCA8BMvRWo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760953205; c=relaxed/simple; bh=IjQMbN4uCocfVUDwL6EFxw7Rsgugh4x1pA9jRrVt/Oc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=pnO+/PzzBur1mv+DRmcRStGdjtLfeZShVaICuqknv9mI/aVRYmefYjKRn3uvdT7wNgBJjYNLo+exc5opSz5PWZsHeGWdAq8C0NJ7rTQAoir9fbYVePnhoIUuLGewj+7cMTY74+b8GhTWbvQ50ZLC7/i6AR6z1e6MsyuvccddnWg= 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=iIS5eU18; arc=none smtp.client-ip=209.85.216.46 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="iIS5eU18" Received: by mail-pj1-f46.google.com with SMTP id 98e67ed59e1d1-33ba5fc3359so4166837a91.3 for ; Mon, 20 Oct 2025 02:40:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1760953203; x=1761558003; 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=EbdHx55SiKCSzxbktDjMMd1XTHiIoKRKCPe02b30DtY=; b=iIS5eU1862GCrN+GBMRS3jh5jMZ8B0OuN3zFdi79yU5Un4Ns0DL/fPnYQ+dIQLgiGN TlTo4use5Uu3AoqTjaLML2+PCJA9Hp1wkJNZVieq/2jw10k8KvKYM7EPLw7+MoNK9BC9 L4eL895ZfK6F4edmmKQx0OGn3LPOFn2JDL8TrGvFUz/TilEe6Bt5OA6kCMZc/11WYycI Y7kCpNs9OtEnLCc95QJ7cP3ztrvgG8yNQXw1hSBSagiqq+m3Ol0Y0VojWa7O4HrpMCVZ 01WQrHoYzKINw8LxdylanYVcpydnQhfkwBHMJpeUhk3I8rf2zsFGalahrTl592WFY8Ml rArw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1760953203; x=1761558003; 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=EbdHx55SiKCSzxbktDjMMd1XTHiIoKRKCPe02b30DtY=; b=Vc+KQJS+1MO+xfGE1Kxk6WkQywsfpL9rcIs+AMk+CzAIyoQ2qjxDnSv4Hl+dC2ES9J OQSFv/kHz7u92BZuUHPaQhKV68ucV/uojsMXqLZZKfzMU1kJw6//719I+MrLm2eEnCRP 5V48CO9SYa13SxxWEiOOOQdq3YNSxidfXG4VdZr2MvQPxaizo/U8XuJbaquRkaTjnPot szMCNxGcFockAmeRTemLC4h8Nws86Y27BNGkjpM35oJh1rJQcrAZelWyxmCF+YU4qYjN YDDx74rXsQLlQLr/UJ1Ulf44+SBsRn0kVjvIJmBvr7RLa4swL1N+cX8HQWmYTPejbHZ3 f/wA== X-Gm-Message-State: AOJu0YzBcLfotnPoO61U77QbtwG2fV6Up4yLvrHzGgar1c3PdLE8ccYb 0O7wf3LDznC6LwZMYC0VXQZcesb7ZjcEN+Q6NooxuWG8WPmhR03bEQPX X-Gm-Gg: ASbGnctBKeQzvYXvx5+GQjRgOPDPADQuOGLJyOmTmO+fHZ959tB+2ybpx/7ejjEiLNW r3TxolPg+fVutoFgCQWn1cp9QF3b0aEjyg+LszirNKU4FMeOhB6syhcDU5AVSFr1RLAqIlnUJBm xafg+kpK+ueDubH0mrnF4lP5Uj4foaZL0qSDibuiF3WO4r8Vgw4QmIc5+OWiKc5h36fUqVLBM3i QGCvtpSj8RhOo6F4tnwlQLly/DXruMyTpOElzF1SJLN/1uADd4P5/Rcc3wYFx4dm12MAFCM27oa nhmqadFubc/udAeS6cyzX4527nTaCXBr65B3m+BPwaxv/uhnZe/Q/+2JkFk07EBtWtGVvEXmquD nKR4HVC6msYaxxxM1ggEWJlJZ1Uhgntg71JwS4TCDqVIp8zoK840P8+EyfyatlTkpgjeRXt0GDl M9sxn7OV0Wtgsz7PK1 X-Google-Smtp-Source: AGHT+IEef+qwgEeNZVUN3VcFN6oO7HlMYKL9/C161d0EvJAlwLbLhLAwqNLQboqPu0GGG05sCHS84Q== X-Received: by 2002:a17:90b:3d8a:b0:338:3156:fc43 with SMTP id 98e67ed59e1d1-33bcf8740f8mr16528326a91.11.1760953203119; Mon, 20 Oct 2025 02:40:03 -0700 (PDT) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-33d5de8091fsm7617200a91.19.2025.10.20.02.40.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 20 Oct 2025 02:40:02 -0700 (PDT) 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 v2 4/5] selftests/bpf: add tests for BTF deduplication and sorting Date: Mon, 20 Oct 2025 17:39:40 +0800 Message-Id: <20251020093941.548058-5-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251020093941.548058-1-dolinux.peng@gmail.com> References: <20251020093941.548058-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" Verify that BTF deduplication and sorting functionality works correctly Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- tools/testing/selftests/bpf/prog_tests/btf.c | 171 +++++++++++++++++++ 1 file changed, 171 insertions(+) diff --git a/tools/testing/selftests/bpf/prog_tests/btf.c b/tools/testing/s= elftests/bpf/prog_tests/btf.c index 8a9ba4292109..244f9d535bc2 100644 --- a/tools/testing/selftests/bpf/prog_tests/btf.c +++ b/tools/testing/selftests/bpf/prog_tests/btf.c @@ -8022,6 +8022,177 @@ static struct btf_dedup_test dedup_tests[] =3D { BTF_STR_SEC("\0foo\0x\0y\0foo_ptr"), }, }, +{ + .descr =3D "dedup_sort: strings deduplication", + .input =3D { + .raw_types =3D { + BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 4), + BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 64, 8), + BTF_TYPE_INT_ENC(NAME_NTH(3), BTF_INT_SIGNED, 0, 32, 4), + BTF_TYPE_INT_ENC(NAME_NTH(4), BTF_INT_SIGNED, 0, 64, 8), + BTF_TYPE_INT_ENC(NAME_NTH(5), BTF_INT_SIGNED, 0, 32, 4), + BTF_END_RAW, + }, + BTF_STR_SEC("\0int\0long int\0int\0long int\0int"), + }, + .expect =3D { + .raw_types =3D { + BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 4), + BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 64, 8), + BTF_END_RAW, + }, + BTF_STR_SEC("\0int\0long int"), + }, + .opts =3D { + .sort_by_kind_name =3D true, + }, +}, +{ + .descr =3D "dedup_sort: func/func_arg/var tags", + .input =3D { + .raw_types =3D { + /* int */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ + /* static int t */ + BTF_VAR_ENC(NAME_NTH(1), 1, 0), /* [2] */ + /* void f(int a1, int a2) */ + BTF_FUNC_PROTO_ENC(0, 2), /* [3] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(3), 1), + BTF_FUNC_ENC(NAME_NTH(4), 3), /* [4] */ + /* tag -> t */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [5] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [6] */ + /* tag -> func */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 4, -1), /* [7] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 4, -1), /* [8] */ + /* tag -> func arg a1 */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 4, 1), /* [9] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 4, 1), /* [10] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0t\0a1\0a2\0f\0tag"), + }, + .expect =3D { + .raw_types =3D { + BTF_FUNC_ENC(NAME_NTH(4), 7), /* [1] */ + BTF_VAR_ENC(NAME_NTH(1), 6, 0), /* [2] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [3] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1), /* [4] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1), /* [5] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [6] */ + BTF_FUNC_PROTO_ENC(0, 2), /* [7] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 6), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(3), 6), + BTF_END_RAW, + }, + BTF_STR_SEC("\0t\0a1\0a2\0f\0tag"), + }, + .opts =3D { + .sort_by_kind_name =3D true, + }, +}, +{ + .descr =3D "dedup_sort: func/func_param tags", + .input =3D { + .raw_types =3D { + /* int */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ + /* void f(int a1, int a2) */ + BTF_FUNC_PROTO_ENC(0, 2), /* [2] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 1), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1), + BTF_FUNC_ENC(NAME_NTH(3), 2), /* [3] */ + /* void f(int a1, int a2) */ + BTF_FUNC_PROTO_ENC(0, 2), /* [4] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 1), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1), + BTF_FUNC_ENC(NAME_NTH(3), 4), /* [5] */ + /* tag -> f: tag1, tag2 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 3, -1), /* [6] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 3, -1), /* [7] */ + /* tag -> f/a2: tag1, tag2 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 3, 1), /* [8] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 3, 1), /* [9] */ + /* tag -> f: tag1, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 5, -1), /* [10] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 5, -1), /* [11] */ + /* tag -> f/a2: tag1, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 5, 1), /* [12] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 5, 1), /* [13] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0a1\0a2\0f\0tag1\0tag2\0tag3"), + }, + .expect =3D { + .raw_types =3D { + BTF_FUNC_ENC(NAME_NTH(3), 9), /* [1] */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, -1), /* [2] */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, 1), /* [3] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1), /* [4] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1), /* [5] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, -1), /* [6] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, 1), /* [7] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [8] */ + BTF_FUNC_PROTO_ENC(0, 2), /* [9] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 8), + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 8), + BTF_END_RAW, + }, + BTF_STR_SEC("\0a1\0a2\0f\0tag1\0tag2\0tag3"), + }, + .opts =3D { + .sort_by_kind_name =3D true, + }, +}, +{ + .descr =3D "dedup_sort: struct/struct_member tags", + .input =3D { + .raw_types =3D { + /* int */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ + BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [2] */ + BTF_MEMBER_ENC(NAME_NTH(2), 1, 0), + BTF_MEMBER_ENC(NAME_NTH(3), 1, 32), + BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [3] */ + BTF_MEMBER_ENC(NAME_NTH(2), 1, 0), + BTF_MEMBER_ENC(NAME_NTH(3), 1, 32), + /* tag -> t: tag1, tag2 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 2, -1), /* [4] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [5] */ + /* tag -> t/m2: tag1, tag2 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 2, 1), /* [6] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 2, 1), /* [7] */ + /* tag -> t: tag1, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 3, -1), /* [8] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 3, -1), /* [9] */ + /* tag -> t/m2: tag1, tag3 */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 3, 1), /* [10] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 3, 1), /* [11] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0t\0m1\0m2\0tag1\0tag2\0tag3"), + }, + .expect =3D { + .raw_types =3D { + BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [1] */ + BTF_MEMBER_ENC(NAME_NTH(2), 8, 0), + BTF_MEMBER_ENC(NAME_NTH(3), 8, 32), + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, -1), /* [2] */ + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, 1), /* [3] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1), /* [4] */ + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1), /* [5] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, -1), /* [6] */ + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, 1), /* [7] */ + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [8] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0t\0m1\0m2\0tag1\0tag2\0tag3"), + }, + .opts =3D { + .sort_by_kind_name =3D true, + }, +}, }; =20 static int btf_type_size(const struct btf_type *t) --=20 2.34.1 From nobody Sat Feb 7 12:19:39 2026 Received: from mail-pj1-f46.google.com (mail-pj1-f46.google.com [209.85.216.46]) (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 55BE82FCC17 for ; Mon, 20 Oct 2025 09:40:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.46 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760953208; cv=none; b=iHLgXrp0BfpmUvAKmJ3e6YYYimJ9HZT8IPBEB4KUfCst0wibDmRJp6YJ83EpphTVyXCiT2itT+JcI7vtJfkgn7CB4SmRW3q3m7RpV6lNH+4KzyeZG0dAnvy20awsYXH1JtFBATeQtfdh7htGwlyZv1FZDEJ3RtGuhTqiTHLbkrY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760953208; c=relaxed/simple; bh=UMitIlA2M4WXFaslfg7FKwsyM5qUsWB8ogi61DvsqC0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=p6ZOiO4CrKiGQIfjR1IclWB3z66aUfDb7NQvJqI+2K1Q3jwwY5RHmT3F5GUN/v9jvQevkKl2OM+E7aNaS16sg6YGFqCLBTf53lOtNSMp32aakjM7Cr8bsGLbuumDoZ8Z1AmdMpUfwxaHpejodO7y+HaYHGDBpBdIb8T8cARVYVU= 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=RYC0cjCO; arc=none smtp.client-ip=209.85.216.46 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="RYC0cjCO" Received: by mail-pj1-f46.google.com with SMTP id 98e67ed59e1d1-33b5a3e8ae2so4205381a91.1 for ; Mon, 20 Oct 2025 02:40:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1760953206; x=1761558006; 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=kH/+6EWs5O6C4gBrSqboPsAfsrt+0avNoGpNPf0X1zc=; b=RYC0cjCOXkoKU/JgkO2g2RDERiSW6ZAvMJagsFWwZesmcfiTypv5D/BzrVx797HsdG bGFYdhvKyHJVvO9dgOSCCLWFqwCurM2z8mVC+f5mi06Ox/mhTx49/AJMes4F7i6ROT8+ agRMvZtXnGGn4w4oXj2aLRNr/GYIgBjRdbkaU2ZZhyfRdWjVnEC338OlnAFQW8hDDZI1 9hAHlFK2dGBoLwJE47iHW89mugfQls0tKFy7sJwVvYv5R8dZGSg12laoLNpxSkb03/RF 5g8hY4UWTJYdhN0BCcubuiKRw1ANf4URl1O9nyOBxqq6EcIZO+ul76F/hfytzwOwXQJh M1uA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1760953206; x=1761558006; 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=kH/+6EWs5O6C4gBrSqboPsAfsrt+0avNoGpNPf0X1zc=; b=MxR0yu4DWXyB4tGR87bI7BgX3pl0675XP8VC6cR1yx7Ha6yRPgNai2XDqw9rvxlKrq 0aYnflPWF2ABhsRPrEb/0zP+DjTzpgr1mZURxxF3dxMWQWKdrwa5tiQYyfS2BiKA2E/n hHVm0VBX2SSd384ojkDxyqD78iIFY/PU6diu4ut5eRX/tO8Q+2tjWRsWi9qkLJMuQpd7 Umq3BEZ/KobF/EOij3/ZreWJ6xQMqy2lFqW5Ut4iLIZSc2qbrPSmYghdej39ASNVM5Nw 5vREuuUm/dLv4u50axMUP3PyCqm1YIZA7cd+FcxS25/rrQcYk9FrgHBmfufH5JzSyCrU Z8Vw== X-Gm-Message-State: AOJu0Yx6YSe/8SKGMuzGmU5gBUeKZF1V9zJnG8zEVUHE4d3vBYsVjhtj zb8rVzCqVOBId+XujKwugZTMmlrWAAkYJ7LbyHuio6V9GtWvYgCgNeWP X-Gm-Gg: ASbGnctzFLfynSd3Dj4f0dgz9uUbLzyBZjliVufnzfMJ9saHKfh41qKyGPPslCFJTY7 GatEZTtYSpwEukYatE6z0tSApj7ew+s9gCn+g/8nXvtrqKGawyoNA/Bkj6aZ/U//HuQKGx8YEgQ oXhXLjGrGu6QETZHK7ojV/yqkZCmE4P6oLdO8I8cnzUSlFf/I7gfHnAxiUECU3L3nTbmpkoED+V G5GT/uY1Nf9MOx5zCFhBiBkZsDU66jpUBnD45R9rV3SlinJ/i8AKVEQ4BOyhp+gWTLszZFajXLm Bs60aZABsO84WQPwRzHEcr/Jpi3GCBHqgtZQyLIUvHtufZdGwosObQtk5/Uh9/iUBAMO+H3AU38 j1oIYgCsquxxOuhdPQzib45HI0s2eKnIiZuj2HUc29Hid4ZyO6/IrMv/vwj51gNr5hQpz9SDnTe gH9nPtua9TPbhzEDCSr70LER/A20A= X-Google-Smtp-Source: AGHT+IG2Wxz9mrCktw0rxT6tFvVvYsqONsh7h6jzym46SEzftpP3aJXfFuuE4RwM1VODUU/DgDWoJg== X-Received: by 2002:a17:90b:2882:b0:33b:d8ad:b69c with SMTP id 98e67ed59e1d1-33bd8adc731mr14497209a91.3.1760953206522; Mon, 20 Oct 2025 02:40:06 -0700 (PDT) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-33d5de8091fsm7617200a91.19.2025.10.20.02.40.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 20 Oct 2025 02:40:05 -0700 (PDT) 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 v2 5/5] btf: add CONFIG_BPF_SORT_BTF_BY_KIND_NAME Date: Mon, 20 Oct 2025 17:39:41 +0800 Message-Id: <20251020093941.548058-6-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251020093941.548058-1-dolinux.peng@gmail.com> References: <20251020093941.548058-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" Pahole v1.32 and later supports BTF sorting. Add a new configuration option to control whether to enable this feature for vmlinux and kernel modules. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- kernel/bpf/Kconfig | 8 ++++++++ scripts/Makefile.btf | 5 +++++ 2 files changed, 13 insertions(+) diff --git a/kernel/bpf/Kconfig b/kernel/bpf/Kconfig index eb3de35734f0..08251a250f06 100644 --- a/kernel/bpf/Kconfig +++ b/kernel/bpf/Kconfig @@ -101,4 +101,12 @@ config BPF_LSM =20 If you are unsure how to answer this question, answer N. =20 +config BPF_SORT_BTF_BY_KIND_NAME + bool "Sort BTF types by kind and name" + depends on BPF_SYSCALL + help + This option sorts BTF types in vmlinux and kernel modules by their + kind and name, enabling binary search for btf_find_by_name_kind() + and significantly improving its lookup performance. + endmenu # "BPF subsystem" diff --git a/scripts/Makefile.btf b/scripts/Makefile.btf index db76335dd917..3f1a0b3c3f3f 100644 --- a/scripts/Makefile.btf +++ b/scripts/Makefile.btf @@ -29,6 +29,11 @@ ifneq ($(KBUILD_EXTMOD),) module-pahole-flags-$(call test-ge, $(pahole-ver), 128) +=3D --btf_feature= s=3Ddistilled_base endif =20 +ifeq ($(call test-ge, $(pahole-ver), 132),y) +pahole-flags-$(CONFIG_BPF_SORT_BTF_BY_KIND_NAME) +=3D --btf_features=3Dso= rt +module-pahole-flags-$(CONFIG_BPF_SORT_BTF_BY_KIND_NAME) +=3D --btf_feature= s=3Dsort +endif + endif =20 pahole-flags-$(CONFIG_PAHOLE_HAS_LANG_EXCLUDE) +=3D --lang_exclude=3Drust --=20 2.34.1