From nobody Sun Feb 8 17:24:07 2026 Received: from mail-pj1-f54.google.com (mail-pj1-f54.google.com [209.85.216.54]) (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 E999831A55B for ; Thu, 18 Dec 2025 11:31:25 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.54 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1766057488; cv=none; b=WwgfC/SYnWwUd3kvQaHx5uLeVfYteYW8C/GSE/HEOBmlqx7e5aTDCcsjVjcqr2NMxwMGyXBjJzVGR/X9gwxnvpXReAtEBQviMp1eZ/9D8a7r7DK3wGCJqksU091hOCF60k8iFa5QSR6GqyZ0nTGXGf8/E+HepZWZW2Tf9csbWsI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1766057488; c=relaxed/simple; bh=KxIYguLp8SeaWQeT350BLkiIGq16X2SfqmN1sIZpyfc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=b329IhsWu0T/89y9BOhGxsbKX+DJFGPml+SLAlttALDRmh2JrDPMPFMXk8d6qjZnLzGMe3O3pKhPipsVYtnzK+FfjFUMNbCDWgP6/hWC86gEv0PhQU57oco52abgyNqNRPg0tZ6wHz9WZdycXo//qhUpJG7vCYzVqc90uQWbWUs= 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=JgZQyF3f; arc=none smtp.client-ip=209.85.216.54 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="JgZQyF3f" Received: by mail-pj1-f54.google.com with SMTP id 98e67ed59e1d1-34c21417781so567722a91.3 for ; Thu, 18 Dec 2025 03:31:25 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1766057485; x=1766662285; 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=HWTU7YkYZsUgcIcDiO47eImJA4XqxyXz+O3bx1BiSAI=; b=JgZQyF3fxE4Ww+8kagYtHQzz5EnMPdE0L+pEyP+Ntyy4ahwQXUlOzZlt+m5YoreW2F ryLnsq2yOjryOE6+81HRuTwDUVypgcmiwMRhf7/s5hPjbBaAJfG9BbDfrboeO9zblo6T 0ONpx+Q2zQqzJ+Lq4q10bXa6Bq1Gyzz5SqHWu4HA/NJ/5mrTh7Yjo0XcmPs6VQ1H7L1Y MT7Ju1Ib/JWpTmqVo6nkbOOAf8DwSKXzTl//1fcY/GbNntCaITGB4M/6B4eUeqFA4rRd EUojXJ8rTQnt10bC4tX+VPk5qmr0rMqsKBfOrWjbPTfQywSW7fabdxpTKABdmR0vGmfQ 6UaQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1766057485; x=1766662285; 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=HWTU7YkYZsUgcIcDiO47eImJA4XqxyXz+O3bx1BiSAI=; b=MFujYAWjTxoVGOgFG7U7v28vuFtgeP+3TqytRJwOQOtr7hFRpxYGQYrEh1T0Cz58sn QN8kK3y+rS9lHzpmNTOb9ntuGUiYV0sqfLc9vi5SFcFc9YfP2u68LYAbrkbzZld3qWnS F1YSe42oIf+fu3d+gP2d8jhiGLqzzbSi/JeWLK3aYxM45pdO/OTBiQezJs1qlx8HGClw hoKQzjWcExHjD3krO9oA6byqSomVaslqFoFsfKZHOJSWtul7c7oCmdp5xy5rrqQe9hc9 BRAYIFpWPdELX6aSaxz94xrWfEMibJAAqEEGmt70FuMgHZfcGXBiiC0ZQxZ0aVi2g5rE anvw== X-Forwarded-Encrypted: i=1; AJvYcCXMaRikk0rC1D4SeQQ/THigY8wyFlVXK6k5QczSWC16LkjRpNUMpdaD5MuDOWSBsaEDopsdQD2+0vkVs1I=@vger.kernel.org X-Gm-Message-State: AOJu0YxUtYnk2pBMnB7sko3Btf0bBYsCJO+Ykngyxgs28mA/9fi3CrVn E/0MYDjH0NVGstvDQ5fvzj2/iR9eAeJpNsdX0vBiSlAyAtHCAFOe5xxO X-Gm-Gg: AY/fxX6vN8703+D/NBbRbpYI/DYzIzEu7KGKeTe4mWWLXjAcuUG1j6Nbe/th9lbvkGT z1dkvLGvvfwRapPJLsMZzbnu17zdX6EGec5VzyUHtjQOc2JPv9yJ5HC2YagfsNzRo6olTFtFwCM Pqh/XGlgaBoZ+aVE/oR7KL8keXkAIFSxcvmdaK5ZaUl8uz6SDbRdmb6jMzqBKifaFedHuBwhuxN nvwek8CdAla7IsWKcWbJDWuJJZEtZDiVaN6oN21YJddLGzey2nC8OLCSGDL8xmjrxsQfSPqHn13 UdgaAaGN1EnjfVajFicC9DY3bMHVJVfxW16uqkuk8qbJW4CbNPlNPb5DvQfEyMxulFo/CcI+5dQ C6J4EXagA+Kbo9wgWuDsgxnNYt7W2w8CAd6wJArFJgIHxJSclnDDzpCYqI4jO6NJnxkIa64bO/8 F+zq3eItIYzvsHBD8M8L4qcptb1QU= X-Google-Smtp-Source: AGHT+IG1ZcmxKj9qrvybSbwP+Nq1gJqIR5zkosJ2g86tGdi05X+iVwrfRUtxZQJU9Q4Rbw4XJYSBnA== X-Received: by 2002:a17:90b:48c4:b0:34c:a35d:de16 with SMTP id 98e67ed59e1d1-34ca35de0bamr11166928a91.11.1766057484998; Thu, 18 Dec 2025 03:31:24 -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.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 18 Dec 2025 03:31:23 -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 04/13] libbpf: Optimize type lookup with binary search for sorted BTF Date: Thu, 18 Dec 2025 19:30:42 +0800 Message-Id: <20251218113051.455293-5-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 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 types. For unsorted BTF, the implementation falls back to the original linear search. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin Acked-by: Eduard Zingerman --- tools/lib/bpf/btf.c | 103 ++++++++++++++++++++++++++++++++++---------- 1 file changed, 80 insertions(+), 23 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index ab204ca403dc..2facb57d7e5f 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -92,6 +92,8 @@ struct btf { * - for split BTF counts number of types added on top of base BTF. */ __u32 nr_types; + /* the start IDs of named types in sorted BTF */ + int sorted_start_id; /* if not NULL, points to the base BTF on top of which the current * split BTF is based */ @@ -897,46 +899,98 @@ 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_by_name_bsearch(const struct btf *btf, const char *n= ame, + __s32 start_id, __s32 end_id) { - __u32 i, nr_types =3D btf__type_cnt(btf); - - if (!strcmp(type_name, "void")) - return 0; - - 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); - - if (name && !strcmp(type_name, name)) - return i; + const struct btf_type *t; + const char *tname; + __s32 l, r, m, lmost =3D -ENOENT; + int ret; + + 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); + ret =3D strcmp(tname, name); + if (ret < 0) { + l =3D m + 1; + } else { + if (ret =3D=3D 0) + lmost =3D m; + r =3D m - 1; + } } =20 - return libbpf_err(-ENOENT); + return lmost; } =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); + const struct btf_type *t; + const char *tname; + __s32 idx; + + if (start_id < btf->start_id) { + idx =3D btf_find_by_name_kind(btf->base_btf, start_id, + type_name, kind); + if (idx >=3D 0) + return idx; + start_id =3D btf->start_id; + } =20 - if (kind =3D=3D BTF_KIND_UNKN || !strcmp(type_name, "void")) + if (kind =3D=3D BTF_KIND_UNKN || strcmp(type_name, "void") =3D=3D 0) 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->sorted_start_id > 0 && type_name[0]) { + __s32 end_id =3D btf__type_cnt(btf) - 1; + + /* skip anonymous types */ + start_id =3D max(start_id, btf->sorted_start_id); + idx =3D btf_find_by_name_bsearch(btf, type_name, start_id, end_id); + if (unlikely(idx < 0)) + return libbpf_err(-ENOENT); + + if (unlikely(kind =3D=3D -1)) + return idx; + + t =3D btf_type_by_id(btf, idx); + if (likely(BTF_INFO_KIND(t->info) =3D=3D kind)) + return idx; + + for (idx++; 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) !=3D 0) + return libbpf_err(-ENOENT); + if (btf_kind(t) =3D=3D kind) + return idx; + } + } else { + __u32 i, total; =20 - 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; + 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 (strcmp(tname, type_name) =3D=3D 0) + return i; + } } =20 return libbpf_err(-ENOENT); } =20 +/* 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); +} + __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_n= ame, __u32 kind) { @@ -1006,6 +1060,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->sorted_start_id =3D 0; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1057,6 +1112,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->sorted_start_id =3D 0; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1715,6 +1771,7 @@ static void btf_invalidate_raw_data(struct btf *btf) free(btf->raw_data_swapped); btf->raw_data_swapped =3D NULL; } + btf->sorted_start_id =3D 0; } =20 /* Ensure BTF is ready to be modified (by splitting into a three memory --=20 2.34.1