From nobody Mon Dec 1 23:59:48 2025 Received: from mail-pf1-f181.google.com (mail-pf1-f181.google.com [209.85.210.181]) (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 2A45132145A for ; Wed, 26 Nov 2025 08:50:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147057; cv=none; b=PlXeCqxcLJMl7uFpQBWJpkm1giBnBTlGLyeefhPzhf8XwCaYUGkvcVif766QcD37cof2AgIeOrPpNCK/dNWsvLSqGIAAkqK+RpTVBjjsBY70vCaOnX3QUUcLLgHg9Tg9Bo3zdzO0WcyjDQ13wPjQufMnbeasEKWXzRuB42ifCvE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147057; c=relaxed/simple; bh=SkiiMl3aCQEr+d5U8ft32wOaTMUA9E4gZBiYCpbgSZ8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=AZSJUzS8fwrMZqrJ6rxNkteHrHnK8dYzY6fnDfoZ2Fk3aN4ZpvzLgNZ9ghsCea2VjFmIFtBvpwvMWb4nlgfBvEGt1WXlkmbclA8efQ8KpS4dp7+rOTyKkWkjFjv97iAhrl/qSi65C3kRJlS+QWlcsMtSOa+7/Mq0RvKpgR22G/o= 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=hmW18q3w; arc=none smtp.client-ip=209.85.210.181 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="hmW18q3w" Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-7b9387df58cso10234208b3a.3 for ; Wed, 26 Nov 2025 00:50:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1764147055; x=1764751855; 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=hmW18q3wDsJHOXz68dAzlRC0fNduPF93cVq+J9aJmBID50Re1Vh72VD28qolB9Jdjc NxxPsiZgWqViI9yeZpBLXXZggdJ02kOoq884KzSXFdSq5u9hHe5XjsDSjhNHIAP1o+Zg JmLllg4qqW/C4QVMVcB57cER8ttVQEzet3UY4+bFEFRwA5g1YItaNmi7HL5z8+868fvW A0fbxmEtl+hx3atmjWaO4HUAO3qchh3TYnYj5iMskWLJbatg9qzSmgRfJEetSYPXPx/I f5nt5q8/gB6CGJWtTVXi8y4vHGRADFnFSyiZCJTaE7edSOL9fG0IdVPY61Lsns9sTAHL wdXw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764147055; x=1764751855; 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=cDXGLJaznvoUidLkG8A1f1BBT8RQ90rVQAxGcYio2GQFGxcz40zM/BCwvDSAKWinjZ D2mFdGGcmNU18jY8SavluGz/4hVwhPLb8HAIeSd6lyZTdkrDTEYE+bglycQDOEQmLB/H GvHFj8D8q4aBKsgLA3m8fY2W+CKsGP6Ik3mjAoLi6cQFMndyDP6Elw+nrtcb0q5JFVz/ zk6STR8hR04GbGYnEsNoZ0INTibasyEve5NRTtmVcBLBnaizOzP1ILm8JaTI6nxVsMex oDU8LOGGXtY2z/O4Gvvkvw1R0HTY57q7dDc3ssCpnk8n1rK/f69Yo8tpMciOcoK2EDdM VVzQ== X-Forwarded-Encrypted: i=1; AJvYcCVgHzLE6e93fh4nkcaVLsKsukvajAfooFjWd1CXKtcmfEX0D04t8/bYqfcdINH0196HhYsBd+WwdMiSqXo=@vger.kernel.org X-Gm-Message-State: AOJu0YxeWVy1s6KBq7FCUGtmQmNyJTkFPie9glERzGlQPZKeEOoZDTTl 325S8h372iyER8nEg7LYjJgvluUSf09c1DiuoONpI2/dB6e+BQzBwN49 X-Gm-Gg: ASbGncuF4BBm0C+qF87e2pRCAXKirsk0haGtip519I0B872pOabv6xRedfJZUko6yv6 ShMeMRzk7kfP4rV9PIJ0qdHj0SfHMkMKzoiXfEYCq7xjdsxYQObX7/pb+pXMtr0ZsQVbdtw+hYW 8LXvVejOxfEOGvSiswBU5ccjkdqUHHa3QzScNp8JuX0iQW6LGBw74tQdh2bkkviP9Iimk4WkEPn cJDBMtyirjuKE0on1jXKvaCVKblO/JJEsyt9VoTGvD+rMZWGQTk49EjU+pYqNzbePJhPH05ysFP 3M1Si0mceDKOjhrC4Fsupu15gM0XnjHM8md1W8dhpqxGSy3ps4ikNtnsMvi7ONrbtIen7zz2FTF vv4HKs28MsiCmMdB2nA+JrctCHSA0SIGoSwPn93/UMLNfEMWgCJMC2CT8GwODvJIp1joA+LyU92 tUL/f/Egb51tHa4iqgaFNtyduaWd0= X-Google-Smtp-Source: AGHT+IEc75RcYRzyB2QjrAR9JxTghgDBcvpbAyHuxNPUY2qamQHEbD1gRabTOEt/ypeNrmjMsOdUGA== X-Received: by 2002:a05:6a20:748e:b0:35d:6bbc:e9ce with SMTP id adf61e73a8af0-3637db64599mr7017524637.16.1764147055433; Wed, 26 Nov 2025 00:50:55 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7c3f023fd82sm20885721b3a.42.2025.11.26.00.50.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Nov 2025 00:50:54 -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: [RFC bpf-next v8 7/9] btf: Verify BTF Sorting Date: Wed, 26 Nov 2025 16:50:23 +0800 Message-Id: <20251126085025.784288-8-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251126085025.784288-1-dolinux.peng@gmail.com> References: <20251126085025.784288-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