From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-pf1-f173.google.com (mail-pf1-f173.google.com [209.85.210.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 0341919CCFD for ; Wed, 17 Dec 2025 00:48:09 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.173 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765932491; cv=none; b=nB0hMKOAPjNwIParwwmSWkTloXy88hXODaeplyAcK0bcaSCbyWyuOWi8dv/tgWPF9j1Jr9i1RLGDyuuy4T0kEKsQH8Nk0cBXbfAOp9jmjNtyzPjn2IGntKMUyCpQ/GxwgnEIHWojwzp8Fts8T2uh02ycUcGTjJU1YipxaaaEnvM= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765932491; c=relaxed/simple; bh=Ny+yuLc1o/B4ZppOwUSBfovH1Zs+njl9stcHGGsR+/E=; h=Message-ID:Subject:From:To:Cc:Date:In-Reply-To:References: Content-Type:MIME-Version; b=BOtIM4mKZDmw/o+VKneE50gPsECToV0pRZgw74cqNsxAYR0H9Ex71OaugyWUBhXcCoG5j5yMzk0no5Ng8pu4b1BWEIu4Zy2MpoSxn6RdmDEh6N2N4AjXXV/e4v3ag2txSwP9kHMT07A70EOzkS92o2Maz3OOUjdgxZkpzp13rME= 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=PNUiZwLB; arc=none smtp.client-ip=209.85.210.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="PNUiZwLB" Received: by mail-pf1-f173.google.com with SMTP id d2e1a72fcca58-7bf0ad0cb87so6609583b3a.2 for ; Tue, 16 Dec 2025 16:48:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765932489; x=1766537289; darn=vger.kernel.org; h=mime-version:user-agent:content-transfer-encoding:references :in-reply-to:date:cc:to:from:subject:message-id:from:to:cc:subject :date:message-id:reply-to; bh=o1nPJt4pCXiX80ArQ3awzkqjh8BNkySW8GQZrbQCMPk=; b=PNUiZwLBZNpWCTrfKeLPjTuDwSwkxH81uC0DASKJ3j74q1BuF/0QYYzJ53nUbW5F1g WuQtKvQmZUzdqWTt/oFOMXjeRy6bSMdOTIEhsmVAB+PFHGFYNcnydrQXX0Fc5A3F1q/m r7vSdQ7zkPxJmvNtq1SllE9f1mpoTR8zFljEn30/xJZjrtQOkEMHomsZfptYOtje9nCm 9+KUltdBE3djod26U7O1qX8txTqhZq7T8wUcEby6SRnSq8+xODHKDP45UhEgUEdj0eyk UQpr6mDBUSeaiGADNocTsjkPd6Qyh2gSqfXsvcEaO1hsFzKDF0zlJ38vh419IBwFfbmG 4pBw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765932489; x=1766537289; h=mime-version:user-agent:content-transfer-encoding:references :in-reply-to:date:cc:to:from:subject:message-id:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=o1nPJt4pCXiX80ArQ3awzkqjh8BNkySW8GQZrbQCMPk=; b=puTW/rSrzKIZKIloBxEpxrWRkzIXuDpYwQFQc+PUWcZpeeuVElsmsz0Mto+VP0Dnc8 jbLOOvZ0hGgm69vAnkml9HqOM4n1cM+m2mNxzIm7g0tvlZilJdNNsLXXy4CpEpfVQLjV Scjl5CjS5ATjHUtg0h7HhBil87uFFtkPtvEy6F/tTobDcIg3SUAfpMGW3a1AoR3tPHab K7d6uvHyBOBA3Gh25ZS5KQZmDGR+iy3ui7TNXpK9sl2EaQeFGwsjItxyXcneEmKyC9mz 8DAOHUu36H9bxiLnTHkN1oup2p53RK/mugU3Ecit7Cdw90rs4FzOG4HduIMLEaL04uH/ Lxeg== X-Forwarded-Encrypted: i=1; AJvYcCWH4rD3jEuUCYgT2jsIJIodR5/vwwvXeTdTe3MtU8JfPonwp0UGtRZg5QckpLOzkzKu8c24PHng6V3z/x0=@vger.kernel.org X-Gm-Message-State: AOJu0Yzh5V3B/wotDI2YsUp6tWUxfePc4mR8sOX0pA/ve9nQ9SEHba8d LY+IL0VCjsm8EA9F8u8aUCyjubYBV5jy3uZ+hlVEAyTqXdisZqbWR7IE X-Gm-Gg: AY/fxX6f/f4GvXSL1lqM4Rcj2bVSDzkrQmXrHXWpmRSSx6uHLcHGunPjMyeXFCTy9/e 1Qa7wC5N2lDA/wFJHrgxyevZoWOSjEzEJlBhlJbnCyZlU5Uf67zAno4BgGkZ62SVCFTNFpCizR/ D1I5FxjuqWduD5whqW6FX5NmdTzvBb/3awihTrT/vC2QFCIUMUKC0DA8wgeiwLrXQpvfq+cPZtn UM7eMJUNythkHCxvsKMLwMEVHprM1XtXe1ldiNARNno4MYmhIvy7OEJ+oR70ksmsugHSe4aAeMD L/21aqYoNthQ24Li6mQW5ZSF3QXlqKTgXxjTTPXm0oo/f94Sx/75J5wEl4gOoAzcLgGNnzCPTxp g+I3rt8+kx0biZerU8JiFejXUUkVuQycHtv8INiyn1oPlOp8PP1NKK1OmQRnsjzg+zzNyYPNP8S PM9LgMrwKI X-Google-Smtp-Source: AGHT+IEpflpIas9dYPJQ170FD9DjFlBm26hwOIRWcZvtH6OmSzhTumsmrO9irWCJjSK8uwUx7p5Cwg== X-Received: by 2002:a05:6a21:9999:b0:364:13e1:10f0 with SMTP id adf61e73a8af0-369afa0f337mr17403090637.48.1765932489144; Tue, 16 Dec 2025 16:48:09 -0800 (PST) Received: from [192.168.0.226] ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2a10d021c03sm66619955ad.96.2025.12.16.16.48.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 Dec 2025 16:48:08 -0800 (PST) Message-ID: <6eb163ae1dbe8bb44e47f1c1ebc37de34c6b7df5.camel@gmail.com> Subject: Re: [PATCH bpf-next v9 07/10] btf: Verify BTF Sorting From: Eduard Zingerman To: Donglin Peng , ast@kernel.org, andrii.nakryiko@gmail.com Cc: zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Date: Tue, 16 Dec 2025 16:48:05 -0800 In-Reply-To: <20251208062353.1702672-8-dolinux.peng@gmail.com> References: <20251208062353.1702672-1-dolinux.peng@gmail.com> <20251208062353.1702672-8-dolinux.peng@gmail.com> Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable User-Agent: Evolution 3.56.2 (3.56.2-2.fc42) Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 On Mon, 2025-12-08 at 14:23 +0800, Donglin Peng wrote: > From: pengdonglin >=20 > This patch checks whether the BTF is sorted by name in ascending order. > If sorted, binary search will be used when looking up types. >=20 > 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. >=20 > 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(+) >=20 > 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 *pr= iv) > +{ > + 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); Nit: maybe just do a separate loop when btf_is_kernel(btf) =3D=3D true? for (i =3D 0, n =3D btf_nr_types(btf); i < n, i++) { t =3D btf_type_by_id(btf, i); if (t->name_off) { btf->sorted_start_id =3D i; return; } } return; > + 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 *n= ame, > s32 start_id, s32 end_id) > { > @@ -5889,6 +5943,8 @@ static struct btf *btf_parse(const union bpf_attr *= attr, 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_verifi= er_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 *mod= ule_name, const void *data, > } > =20 > btf_verifier_env_free(env); > + btf_check_sorted(btf); > refcount_set(&btf->refcnt, 1); > return btf; > =20