From nobody Mon Feb 9 11:11:40 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 63048303A07 for ; Thu, 18 Dec 2025 11:31:36 +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=1766057498; cv=none; b=ApvQAOR12LA9tMTbvGrIMY3CyHTWtlb9DqpScSaAew3VTlOYExjZx2eMlFvW6NzDJdB02yIf7bv6/qj3PnEsbGOV+bTFwv/TZIri88UGpqHe/UCggipzR3aNlW5cPnXOjZixO/y+MjP5Da+ycUMfuY/WOBaM3ie/63qaU6AF74k= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1766057498; c=relaxed/simple; bh=KvaJlRaiUe8MkAKXREkrMgArNu7n4FxcgCEAlQluXAg=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=FNDDqY+h6iTmKHBSqHrEfDeaJGGE5Tpe05+Z3FsLYu+tRFlGBBhlX7tujDHAWEzh+PyjoHkuabYmZMD4CHcicZ4+xxZQuY1+nhbD2KYR5Gvy+RqIbZRUMKl+7bsZn0ztasow6L67IMHkydu5U4RC7WaSV8YD79u/e9yXrbGpWi4= 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=WASuQfaY; 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="WASuQfaY" Received: by mail-pj1-f46.google.com with SMTP id 98e67ed59e1d1-34ca40c1213so459512a91.0 for ; Thu, 18 Dec 2025 03:31:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1766057495; x=1766662295; 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=/9wcZC55VqhhbPSAYuLEBFuNZUpMeWvJuY6oSbLgmgg=; b=WASuQfaY20GsSj3jQzEUzF4td6Z9F0w2pz+IhqUr3HUOL6AYPlKtBqwEdh0MmhtnPs bkxYpWKFoYzuw5DJy7p1gYv9phTkSpr62aPzfHhC+7HlYnLoK+1lGdfPPXc+k2t92BSr 6ZQc/J+Did3outr/Bs21TSiboUp/loJqiz3WKJ1bRCm6TkUA8QzMEUzc5uUZnQR32SXw t0FlZGc6gJJSSmLyZkPq60BRN9RkD3dX5BiGyEZsNWgPlTZPKgy8pLmMByV3nmDMTrze T1eIQfT+9KG/ht+AsLMf3cV8b1Bm4w0BRcFXaIu6QKE/W1r2eakjO/zOhKQDyuG/tDLp Z+/g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1766057495; x=1766662295; 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=/9wcZC55VqhhbPSAYuLEBFuNZUpMeWvJuY6oSbLgmgg=; b=Q6keZ+7EOwMd/BUVTSlt9wsFwUHQ13UW0ofY0pTCdbtcf0U/AXBJKirWTOUBDbHvSQ fm7Pal8X6ZlDqo5qkRCRqPq1OrGRXWpjhzsMIkVKm0BQ8PKM+t5Kh9HDXoYS7qL5FBBU ft01l1T3iMZAbAuRJz84lwsUBpgcQNUQJj20CKKTpvB+XO4WrRXClpN1O/6xoH8WZGWB +S8ljYdjZFJ/vbIIqXAaN21ONdNv9hRwXpdfDabAq2DYe03dqEsaXU4fW9hFPx807uaH 5WBrJBZ+B9M5b539IkrexUCuxty2rABZoMnJq9mz/+NAIkwCzg0xoxnFnNPpILeCMJ7r DcPQ== X-Forwarded-Encrypted: i=1; AJvYcCXHmf4wWwxkFbe4qw7YRQNn6sK2xFvjlvPl6/oeN7pVNaMUUjCLOZ51GIE7wtj/YmkZJxR7yehaEp1Qe2Y=@vger.kernel.org X-Gm-Message-State: AOJu0Yy3lv2eNOyP76oqxmocBr/i3lyhTwFCdQ9SZZzA2xxUvw9OM2rJ hl9p2/OjTrQ0fLTnTmiz6NxRxpfo7pPPmOKq/Ape2hhwKz1Z67VQNKkc X-Gm-Gg: AY/fxX4PORs39naHssnVm3KBPaQ9znSEV83kRDbFMpwNzNmxViq88m/42AN/GFGo+Qn lDVCnKJVNoUhbIqr6JC/AZD35xbp0w7Kr5eiEUrrDci3fpUZVQbtVGMPLRR4XuVfD4I0uKbLyEz wGOVsStSeNoJ4Z4X6Elsuwlj9sWMd6EOvJNUqU2RvyIcUJ8jSFBop6wcEh1CdMwCbSatsFTzx9i ioj5hu8xAXP19AGHC44RsVm0m3lJsBvM/e23166L6QgBl2nXxFYoe7ygC1fbO2ggILsSdzhOxn6 t0kXUT/UPJR2ilfnnhTPwqHuuaNnVazwbnn8G9jkFqslVaT2QqWhfFCVtNebAK4zCW+jPG/rKI7 JJ6Y9xwAU5JfLoxj5qxXP9Hf00aMi6iIfTWZd7dTexgbfxBGeTg0V6uYKc23hlmdmezsxKZQPKm NAGrGvDYeY6KEOtNcOrLIWLgnE9Aw= X-Google-Smtp-Source: AGHT+IH6ci0tvt9FeyZRLVqlq2jq6tgQFC7Z53yosxENZOca7GsIes90pwCI3Ro/ideYOeQxsqwwwg== X-Received: by 2002:a17:90b:5109:b0:340:c4dc:4b8b with SMTP id 98e67ed59e1d1-34abe3feccbmr19217290a91.10.1766057495472; Thu, 18 Dec 2025 03:31:35 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-34e70d4f887sm2328237a91.3.2025.12.18.03.31.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 18 Dec 2025 03:31:34 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com, eddyz87@gmail.com Cc: zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [PATCH bpf-next v10 07/13] btf: Verify BTF Sorting Date: Thu, 18 Dec 2025 19:30:45 +0800 Message-Id: <20251218113051.455293-8-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251218113051.455293-1-dolinux.peng@gmail.com> References: <20251218113051.455293-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 | 56 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 56 insertions(+) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 0394f0c8ef74..a9e2345558c0 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(u32 *a, u32 *b, const struct btf *btf) +{ + const struct btf_type *ta =3D btf_type_by_id(btf, *a); + const struct btf_type *tb =3D btf_type_by_id(btf, *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; + u32 sorted_start_id; + u32 i, n, k; + + if (btf_is_kernel(btf) && !btf_is_module(btf)) { + for (i =3D btf_start_id(btf); i < n; i++) { + t =3D btf_type_by_id(btf, i); + if (t->name_off) { + btf->sorted_start_id =3D i; + return; + } + } + } + + if (btf->nr_types < 2) + return; + + sorted_start_id =3D 0; + n =3D btf_nr_types(btf); + for (i =3D btf_start_id(btf); i < n; i++) { + k =3D i + 1; + if (k < n && 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 (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) { @@ -6296,6 +6350,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 +6485,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