From nobody Sun Feb 8 21:28:13 2026 Received: from mail-pf1-f177.google.com (mail-pf1-f177.google.com [209.85.210.177]) (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 0B3A628726D for ; Thu, 8 Jan 2026 03:17:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1767842226; cv=none; b=gGJB1BmCmTkynemEfG3Ou4Z9gVD9uS+41QDHUYS3EDuZFc+j0nOlW2tIjATaeTYA6hctadJOkQdf194+4lKSahguhdvU9rrb7lCuPrxeaePzuyAqm4segTKwQtFy/Z3YTURiKNSZl6zmY5lGfFZIpeYvyIqpG8gHoEL70fJHlE8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1767842226; c=relaxed/simple; bh=ZOq8fJcGVS/fCpvZMwV/P+/0vrcfuhuBwBc7kMUvfWk=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=c94+l7+Vw08UhbRIotluQPWU4R+YvGS3gGnAnprvteLbgLDu/7ATBSaE8Ijl43rLwTpkM42KB0w7YteOBeeXyv6XX2pmsRjiDwguCMCQ49VweA3uDiBuWMk/ouVCCyA+aak3Xt+f1uQsdeVPiJLGuujN7o0rSsoC8v8PZb5lf68= 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=Lw/12P0x; arc=none smtp.client-ip=209.85.210.177 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="Lw/12P0x" Received: by mail-pf1-f177.google.com with SMTP id d2e1a72fcca58-803474aaa8bso826658b3a.0 for ; Wed, 07 Jan 2026 19:17:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1767842224; x=1768447024; 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=s8++2dvjEi+Fcakj7nAgD/5PeeKaHx/ulT/qgv8H064=; b=Lw/12P0xtRGABs9Y4UcApVxlTn+szjObplaqbaP7nv4jZGXX54i+VEGI55nSn2u71/ vsnLhdlb9E2OcpEMg3rBGV19iUSyllXdHwc5WH8EFxRVKYyJpqi6dl9Aj1Tze5jfqB0+ SuqTsOkUNFFWG2OrCCHFgE+sc+Px0Ts8fJPkvWDX6PUg+zmnggaKM4eqwPDsk8useEIo uAlgF8VRKlk5GgTjXS/UIJfe0LI5PFDbMNvLzyBzIONNJRI1DLEFrc3raYKiE7yeFLWY CXq1R8YvBnaZFDYJz4YuZJEJRdHtPw/KphpX1w7Fje25MefWNij0dOSknRWvtAslw4Dy oNeA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1767842224; x=1768447024; 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=s8++2dvjEi+Fcakj7nAgD/5PeeKaHx/ulT/qgv8H064=; b=UA51sM09LY0MUGcPg2Bo20YsVHCV+ypyj2yXwVU6d+Z+lNd+0+dFEYael9FbSzbMg2 c9pQovChzLLiQoz2u/J2W/xu/1PkU7rzdIJb5h/vFLH2jw1HUqoAiTbnCQqCx9PPrY8c SdHvokQrBPgNpTbkRKDynYJfcpTeH2K6GL2F7V5Cv0Pk4BexeE8JJPOa7fLcuwaYbLUq Kd7jOfoZR6SfQ1x78IVu7+Qby6NEX2z16rlk+CqI5tDZ5JqDJudC+doxpUQl5K+/agpq 0C9kfJ0TwRShyG4Gk96AKdvdvRDI0EXuYluRSwBSesQigrVDOo+qgeSgK3gbNTc0vziM gLdg== X-Forwarded-Encrypted: i=1; AJvYcCVVRR4HbXlSU/Kc8UZ8T6dQ0RCwDke3MHnSg9OjXGeMiXvpPacegLk22Fxc36kGnjnPM2lTWAo0SJ8V7js=@vger.kernel.org X-Gm-Message-State: AOJu0Yz2VjnTqTCInM3R8bdGXB6rNjLE5TS4NCQYy3BBJJRVRJRSHUIW +l88BvVErwrHveWPKr4L9uDQb4RSKUmQN/66V3YugZ0wYKYThN4grCS1 X-Gm-Gg: AY/fxX6XomK5495JJicuxyCac2Q5VlkstOY+JFeocX67VNIDfp8NAfoQUx/KGW51nHp aDg1z1f1tt6JkrAFqMNkMzQCrjsdjovAw+M2KPSVkuskCj7wPOEAF1TR9QHtIDI+XYTlyPOAG/Q VoIiIU35UizEm2FbFXfpjSfTtArUIEHLJoEZsLQSy5MmEOAJBi3gcDmpozFOmIdDUt4LddVfO0m oxvPqur2eC78uavDRh1dY6V1Pv+0jEjkwrZFL2erJEjN5Z+viZ75WtV4DJMa2oFyYoAUHRwLIfJ 7LpzPlnKogdSnVS2rUt7fWSPVQ/gIKeapp6cOAnhlRRj9W9oppneznj3HC77IF9PEewThzI/a6y 1Er/wQ1Reor/m267FOWHn4rnWxDGgsMUXoIz0amSXOJ5YisAJVPeGg81Xrv7s/xVumm7P80Z3G6 xcWzbkxTRC9mR8OwPeWuSqiBth9L2aaWxPcWDXMg== X-Google-Smtp-Source: AGHT+IFGwdUyqDwaYlBr4lLMYhoJJzPw06Sbar1py7DjIxEkSI4qkacyGr98gxp0p7UuMGdseTWxoA== X-Received: by 2002:a05:6a00:408c:b0:7a9:f465:f29 with SMTP id d2e1a72fcca58-81b7684e6a1mr4560405b3a.10.1767842224292; Wed, 07 Jan 2026 19:17:04 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-819c5de655bsm6134860b3a.60.2026.01.07.19.17.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 07 Jan 2026 19:17:03 -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, Donglin Peng , Alan Maguire Subject: [PATCH bpf-next v11 04/11] libbpf: Optimize type lookup with binary search for sorted BTF Date: Thu, 8 Jan 2026 11:16:38 +0800 Message-Id: <20260108031645.1350069-5-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20260108031645.1350069-1-dolinux.peng@gmail.com> References: <20260108031645.1350069-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 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: Donglin Peng --- tools/lib/bpf/btf.c | 90 +++++++++++++++++++++++++++++++++------------ 1 file changed, 66 insertions(+), 24 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index bf75f770d29a..60ff8eafea83 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 named_start_id; /* if not NULL, points to the base BTF on top of which the current * split BTF is based */ @@ -897,46 +899,83 @@ 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) { - __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; + + l =3D start_id; + r =3D btf__type_cnt(btf) - 1; + 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 - return libbpf_err(-ENOENT); + return btf__type_cnt(btf); } =20 static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id, - const char *type_name, __u32 kind) + const char *type_name, __s32 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->named_start_id > 0 && type_name[0]) { + start_id =3D max(start_id, btf->named_start_id); + idx =3D btf_find_type_by_name_bsearch(btf, type_name, start_id); + for (; idx < btf__type_cnt(btf); 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 (kind < 0 || 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 > 0 && 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 +1045,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->named_start_id =3D 0; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1057,6 +1097,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->named_start_id =3D 0; =20 if (base_btf) { btf->base_btf =3D base_btf; @@ -1715,6 +1756,7 @@ static void btf_invalidate_raw_data(struct btf *btf) free(btf->raw_data_swapped); btf->raw_data_swapped =3D NULL; } + btf->named_start_id =3D 0; } =20 /* Ensure BTF is ready to be modified (by splitting into a three memory --=20 2.34.1