From nobody Wed Dec 17 05:07:45 2025 Received: from mail-pl1-f176.google.com (mail-pl1-f176.google.com [209.85.214.176]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id F0DF8313E2E for ; Mon, 8 Dec 2025 06:24:24 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175066; cv=none; b=fcP1PwbMrcgeA1bAGwiP5Xe+sIkvxM/jQ5SWkdLuTdlnMVLq5Q9efiFaVTXmaktfRkAlVjh7wWJf9vPFPd2Mb+bLLEzsanXSqJAYNzdLAgEek3jOxKeIrDH4OkeaQQn+8EvHPusTl7+2p4a1Wf8opuacvz8ujZZCYBm5wCW96mU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175066; c=relaxed/simple; bh=SkiiMl3aCQEr+d5U8ft32wOaTMUA9E4gZBiYCpbgSZ8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=PUhk3V1BRCYzRyEVrDH0RT1pEoExbWSBzrxBXdjYmO4PtqCwwKtEhFJd3pcOCA8sqstnj0DmVKJr/ciQJrO+avKlo1JquTnqap671iPsG67PYgyD0+izVosG7p6rHwmKMo/vYHhK839xPnGA22G7cgiX8lxtmy4Z3hDWRx0pizE= 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=h/CtXLsL; arc=none smtp.client-ip=209.85.214.176 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="h/CtXLsL" Received: by mail-pl1-f176.google.com with SMTP id d9443c01a7336-297d4a56f97so53235345ad.1 for ; Sun, 07 Dec 2025 22:24:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765175064; x=1765779864; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=7QTcvpacDQDrdV3P23xBsLkdItSxCnXjFnIjmUhrbpI=; b=h/CtXLsL+tWIp47DX3VHrKi3BH9HPSPsQtJRjIgvUDH2yGIQ9nfeSlma9K5WDU4rye PUu21qHX2q4hMWNHkpQFSqhY5v0xc93eJzA8xVnS1CGDKF89ZDFnMIFqoxu3C82TmO6e z2j4IxQG5C40kdsq3jrYI1z8+goxxRSeML0MQQDaed4aPbUbkKvuEptZcDFDPhps4XCr AGEej6AkgY1ZvPJDO9ZV7ZXTpMLP3b6jDmk8SzqEobC+lFLL3soRJHzXJZTPhoyOENq9 wKOpJ+qyUVLb1CBOs3J3YQ5WBnRRG6P/PB8OwcgjV0zn4WzuSBOOYu40QwXb0KKj2jGx wtQQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765175064; x=1765779864; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=7QTcvpacDQDrdV3P23xBsLkdItSxCnXjFnIjmUhrbpI=; b=MPZN63pdMd6gX8HNHDhalRYE3hPKbxqrauViSq1BfPQd+4dkwFbhYc4vRY63W2Umsj zWEhJxOqahgGe8VMCoqiX745Tx9NnY66mEvK2L4lNFZrH1zGt+0NRZM7jbZBcNTQm64G IWemKdJAkfT6FAmIZXhQLcq+LxMEDLnOsQfY8Pv7iPya+0M6RYQj17V4vmfFfWJIZZZZ sZSpOqZKcknVjgmuY/cEeslpJV1yVGFbnXgMHYHl0ixfri9tYWdhnZA8l2fq+NxmP++f bF74qX1gyUzn8SVDqoalQime7yixSygF94nIMgU3MU+i6Fx1NC8+7wWa1nm7rY2yOZK3 v9wg== X-Forwarded-Encrypted: i=1; AJvYcCULvSd8AvRtjR0NXhzjh0O1AVcYfQqprDu7SWuyzbra14nwaAURdd+MZL8d29cvHZdeVCROpKEbJyeOX0o=@vger.kernel.org X-Gm-Message-State: AOJu0Yzoh7B7p704oDqiZBp3DuBWpPBJ72jGAXQQiO3sWW0u+4a9cD2l zat9ABs3HlWgcMqEtgQaDCYz9U40z+xe80eCpDXizTB1zzSye7jbK3lZ X-Gm-Gg: ASbGncunNI8A2YjdXpbc6v8N9AIH9udOzZpFSn+k01Cp/PU6u/YGA9LyX5CJrK6Yx0C UpQrdPag+BRpaKexhtIyyT8qtrdTq4mClD3DbNldoCVykl7np5g/u2mElm5nkm78LBdHCsne9t6 j+3bBwDo1xIejrezaLAbQq9NqOx68tIb+yvxGkyy1jn+IwBPCap8JrDFSoaSj2cMUc6MxcCffDt 7XNE8sC5GsOaTcUoE2oIopaV1hvxBiNqaDPMdejutw+xwaKgUa9dYqpHc9R5L+o2QwKscGbuPRe 475p+ngct+v5k5WaZ80eKR6+QU5lp3on9sA7LbkD6Uob26Csp68bb281LOTU5vm2PR0pOt57pl1 h0yM0EhrltWCP9nwGYQO0IM7O2tBnDlHPvrNzV5E1mjs48pQJRoYBcpQ5SfMhtejiKCGNnx7rh0 I0CCHeUhgDAs849v6G/hgPT+lC7B8= X-Google-Smtp-Source: AGHT+IGy9ZHkYoDCeMBMkITpN3+AePbwh+IYnfo+UR/72sgLY/5EfSwCwoF5HbXDJD2v4dWdOPEYQA== X-Received: by 2002:a17:902:cf0f:b0:295:1277:7920 with SMTP id d9443c01a7336-29df5dc065dmr62398555ad.28.1765175064159; Sun, 07 Dec 2025 22:24:24 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-29dae49ca1esm112555855ad.2.2025.12.07.22.24.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 07 Dec 2025 22:24:23 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [PATCH bpf-next v9 07/10] btf: Verify BTF Sorting Date: Mon, 8 Dec 2025 14:23:50 +0800 Message-Id: <20251208062353.1702672-8-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251208062353.1702672-1-dolinux.peng@gmail.com> References: <20251208062353.1702672-1-dolinux.peng@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" From: pengdonglin This patch checks whether the BTF is sorted by name in ascending order. If sorted, binary search will be used when looking up types. Specifically, vmlinux and kernel module BTFs are always sorted during the build phase with anonymous types placed before named types, so we only need to identify the starting ID of named types. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin --- kernel/bpf/btf.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 58 insertions(+) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 842f9c0200e4..925cb524f3a8 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -550,6 +550,60 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +/* + * Assuming that types are sorted by name in ascending order. + */ +static int btf_compare_type_names(const void *a, const void *b, void *priv) +{ + struct btf *btf =3D (struct btf *)priv; + const struct btf_type *ta =3D btf_type_by_id(btf, *(__u32 *)a); + const struct btf_type *tb =3D btf_type_by_id(btf, *(__u32 *)b); + const char *na, *nb; + + na =3D btf_name_by_offset(btf, ta->name_off); + nb =3D btf_name_by_offset(btf, tb->name_off); + return strcmp(na, nb); +} + +/* Note that vmlinux and kernel module BTFs are always sorted + * during the building phase. + */ +static void btf_check_sorted(struct btf *btf) +{ + const struct btf_type *t; + bool skip_cmp =3D btf_is_kernel(btf); + u32 sorted_start_id =3D 0; + int i, n, k =3D 0; + + if (btf->nr_types < 2) + return; + + n =3D btf_nr_types(btf) - 1; + for (i =3D btf_start_id(btf); i < n; i++) { + k =3D i + 1; + if (!skip_cmp && + btf_compare_type_names(&i, &k, btf) > 0) + return; + + if (sorted_start_id =3D=3D 0) { + t =3D btf_type_by_id(btf, i); + if (t->name_off) { + sorted_start_id =3D i; + if (skip_cmp) + break; + } + } + } + + if (sorted_start_id =3D=3D 0) { + t =3D btf_type_by_id(btf, k); + if (t->name_off) + sorted_start_id =3D k; + } + if (sorted_start_id) + btf->sorted_start_id =3D sorted_start_id; +} + static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *nam= e, s32 start_id, s32 end_id) { @@ -5889,6 +5943,8 @@ static struct btf *btf_parse(const union bpf_attr *at= tr, bpfptr_t uattr, u32 uat if (err) goto errout; =20 + btf_check_sorted(btf); + struct_meta_tab =3D btf_parse_struct_metas(&env->log, btf); if (IS_ERR(struct_meta_tab)) { err =3D PTR_ERR(struct_meta_tab); @@ -6296,6 +6352,7 @@ static struct btf *btf_parse_base(struct btf_verifier= _env *env, const char *name if (err) goto errout; =20 + btf_check_sorted(btf); refcount_set(&btf->refcnt, 1); =20 return btf; @@ -6430,6 +6487,7 @@ static struct btf *btf_parse_module(const char *modul= e_name, const void *data, } =20 btf_verifier_env_free(env); + btf_check_sorted(btf); refcount_set(&btf->refcnt, 1); return btf; =20 --=20 2.34.1