From nobody Tue Dec 2 02:42:12 2025 Received: from mail-pl1-f178.google.com (mail-pl1-f178.google.com [209.85.214.178]) (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 280F02EA168 for ; Wed, 19 Nov 2025 03:21:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522515; cv=none; b=TfZyofPoZ/fmzsIm8/PRVuYbHCsZB1VwRDePmBTCyo/TxaOtb8smhAzyPeBnee/DbCIxp64ZzP0aADTQX47xHY7Q02qSeTq8J5UmSbXVSMIFRHsqw11Wc1otdVHZSVrBqpaLeSPiodve8dNivpdwEbBkEAMqt360/SGJnt4oj4A= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522515; c=relaxed/simple; bh=pRQusZkSLe1fwc7vB/uN8SQmj+69/j5iu2aOU15S3L4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=mLiv8EDEoWteES7t4Ift8Ax0THSR4MeLQOzzphIYdv07siIPEsMjCFqNi6lonjyBqPvv82d7wITafMSXomJd3kd/ozzyfOYKpHWoZO8MOGjB88XsybpM2009asoFCuwLVkvrx/mrUklavT/SipEtNL6ZebIUKqtQ63qdFPpf/s4= 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=MeAp0qNH; arc=none smtp.client-ip=209.85.214.178 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="MeAp0qNH" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-299d40b0845so53804735ad.3 for ; Tue, 18 Nov 2025 19:21:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763522513; x=1764127313; 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=z+FkS3xOd3KY3Oh85nihoYx6o93mfmCHv+PUDaVgOok=; b=MeAp0qNHN/n5zj4FNV0Ezs1VuC7VueWWTg7oSv+y8vCAdJ11O3ZtAQ0F5pBKfv8ZCd FU9Fqg4WtcIlb7On/uV3vnuKM3jfYVzV3BVcip+hVvoafeG1KGHoY4j0NLS9yqDjWyr+ xLAsnwVizWqJ3U9I1T8GOQtTLer8TmC4Ex7WI9+oGvjZFLrwnCQcv28hQwvJ1ie6REhI xxjn2G31lAKU6VqtXLUNQVEeagtM/smIHWnW7SloSqZjFCRBzG95s1Csu2UI72qs0weH PW4QQOlP7d9lsZW45ECRTPJo47wlg3wbGS84Uc/4ERi0Ar0mBqKaH+/9t0W8829SYkFW xChA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763522513; x=1764127313; 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=z+FkS3xOd3KY3Oh85nihoYx6o93mfmCHv+PUDaVgOok=; b=qtOmKjTkeACT9Y6ZqTyGK1931rpAMea14svXMUoSZTCBLZDojLp3negJDC5g+/FuQk hyTRO3etfcs8BB8eJi7tayjx5LNYcmfbkX0GU5v+TwjAkhZno552fJ2igwKJicgHfPkR DpsuNcPNRWIRsKk0gGJ/9fdELt5wgYDjY2NTjS63U3ecgN4b3sr49jjsCN7ftmvWdDAt YOpOSg/7iATe2+r0nGNIhB5pIVgp6wpU/zO2wLkpN5z2s+bymtLbP7K7LBEJKjFtdmvD bDwRizhltmQezMtmnC3e9V1a+Ww1pjlJmWkI9cxWLN4PQ8sEwPotl4Q1FwlQuhA37ao1 4BLw== X-Forwarded-Encrypted: i=1; AJvYcCWQ02Kpy9ZRiahQ3UFBGsThqGHj8U6gBNUzU4r14/+nOxz7cOcqPJVIB6PVLmxv2uYrmNDzF+QT1H6y2KM=@vger.kernel.org X-Gm-Message-State: AOJu0Ywa1Kpmr6xwDBqN3SF74ouV9j4o+OEvj2OdzrwYc9YlmEJbRRuZ bdW/OUCgPIftk9ONUjpGs/oHio1+2Ue8jP1bjlF38Y8YTerx6MpK9/1q X-Gm-Gg: ASbGnct+Vp7ur7femdBOMzr6OHN0RNxOANwMbPE4lSKaO16aodMyENZl6ZaoX9jqRhC OUPqtTRHsyvfnCWL7X5fH134UWyNJZ/Y7lEP4rQcq19audOndsCLbUx5bAiScA4yFlctPq4HNii M8jSPVYLplZp8OlG9cTJDzKhyUILdDWR91RCypo3DWmJPtUVDjlra5nmrLfx83yACEWPGo4mKIe W5ES+f9QbyXGoTm/s0hix27SuaAuydW/1H+FKHENx+mvwzcoPbjAc4RLfUwTNljg3mTpvG2qCOL obuQW7RXizGnACJMLX6kY9UnqNnowRqRrh3JQpES1t8Ilrd8v386dLmT9C8FGLs+jKQJ+zwfusC +vXN/AScDCnkFtmHCsKCO4YErQiUiC+gZzoJ6OjLShOrmBoF2T9OJUU76H4njalaYQLic9ssTPU YaWPbfni8l1Ah5JNP9RekKL2R3g/eeoY7ZQ6hCZw== X-Google-Smtp-Source: AGHT+IFUoGb4wi50+IfBdQ0MktBJM2JOUYOy3xmChyxxc0HHiTUr7XweRhKfvx+O/GiZMLxsvLk7Xg== X-Received: by 2002:a17:903:1b2c:b0:297:fc22:3ab2 with SMTP id d9443c01a7336-2986a73aefdmr216874545ad.36.1763522513507; Tue, 18 Nov 2025 19:21:53 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2985c2bed5asm188352485ad.88.2025.11.18.19.21.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 18 Nov 2025 19:21:52 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF Date: Wed, 19 Nov 2025 11:15:28 +0800 Message-Id: <20251119031531.1817099-5-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251119031531.1817099-1-dolinux.peng@gmail.com> References: <20251119031531.1817099-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: Donglin Peng This patch introduces binary search optimization for BTF type lookups when the BTF instance contains sorted types. The optimization significantly improves performance when searching for types in large BTF instances with sorted type names. For unsorted BTF or when nr_sorted_types is zero, the implementation falls back to the original linear search algorithm. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 104 ++++++++++++++++++++++++++++++++++---------- 1 file changed, 81 insertions(+), 23 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index ab95ff19fde3..1d19d95da1d0 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -92,6 +92,12 @@ struct btf { * - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; + /* number of sorted and named types in this BTF instance: + * - doesn't include special [0] void type; + * - for split BTF counts number of sorted and named types added on + * top of base BTF. + */ + __u32 nr_sorted_types; /* if not NULL, points to the base BTF on top of which the current * split BTF is based */ @@ -897,44 +903,93 @@ int btf__resolve_type(const struct btf *btf, __u32 ty= pe_id) return type_id; } =20 -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const ch= ar *name, + __s32 start_id, __s32 end_id) { - __u32 i, nr_types =3D btf__type_cnt(btf); + const struct btf_type *t; + const char *tname; + __s32 l, r, m; + + l =3D start_id; + r =3D end_id; + while (l <=3D r) { + m =3D l + (r - l) / 2; + t =3D btf_type_by_id(btf, m); + tname =3D btf__str_by_offset(btf, t->name_off); + if (strcmp(tname, name) >=3D 0) { + if (l =3D=3D r) + return r; + r =3D m; + } else { + l =3D m + 1; + } + } =20 - if (!strcmp(type_name, "void")) - return 0; + return btf__type_cnt(btf); +} =20 - for (i =3D 1; i < nr_types; i++) { - const struct btf_type *t =3D btf__type_by_id(btf, i); - const char *name =3D btf__name_by_offset(btf, t->name_off); +static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_i= d, + const char *type_name, __u32 kind) +{ + const struct btf_type *t; + const char *tname; + int err =3D -ENOENT; + + if (start_id < btf->start_id) { + err =3D btf_find_type_by_name_kind(btf->base_btf, start_id, + type_name, kind); + if (err > 0) + goto out; + start_id =3D btf->start_id; + } + + if (btf->nr_sorted_types > 0) { + /* binary search */ + __s32 end_id; + int idx; + + end_id =3D btf->start_id + btf->nr_sorted_types - 1; + idx =3D btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id); + for (; idx <=3D end_id; idx++) { + t =3D btf__type_by_id(btf, idx); + tname =3D btf__str_by_offset(btf, t->name_off); + if (strcmp(tname, type_name)) + goto out; + if (kind =3D=3D -1 || btf_kind(t) =3D=3D kind) + return idx; + } + } else { + /* linear search */ + __u32 i, total; =20 - if (name && !strcmp(type_name, name)) - return i; + total =3D btf__type_cnt(btf); + for (i =3D start_id; i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (kind !=3D -1 && btf_kind(t) !=3D kind) + continue; + tname =3D btf__str_by_offset(btf, t->name_off); + if (tname && !strcmp(tname, type_name)) + return i; + } } =20 - return libbpf_err(-ENOENT); +out: + return err; } =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; =20 - 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(btf_find_type_by_name_kind(btf, start_id, type_name, ki= nd)); +} =20 - return libbpf_err(-ENOENT); +/* the kind value of -1 indicates that kind matching should be skipped */ +__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +{ + return btf_find_by_name_kind(btf, btf->start_id, type_name, -1); } =20 __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_n= ame, @@ -1006,6 +1061,7 @@ static struct btf *btf_new_empty(struct btf *base_btf) btf->fd =3D -1; btf->ptr_sz =3D sizeof(void *); btf->swapped_endian =3D false; + btf->nr_sorted_types =3D 0; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1057,6 +1113,7 @@ static struct btf *btf_new(const void *data, __u32 si= ze, struct btf *base_btf, b btf->start_id =3D 1; btf->start_str_off =3D 0; btf->fd =3D -1; + btf->nr_sorted_types =3D 0; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1715,6 +1772,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 --=20 2.34.1