From nobody Sun Feb 8 20:00:04 2026 Received: from mail-pl1-f177.google.com (mail-pl1-f177.google.com [209.85.214.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 646FB35BDCD for ; Fri, 9 Jan 2026 13:00:22 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1767963623; cv=none; b=e6uvpgdfcM3z1cFl4mqGoMxPUE/ta3QKHTBvstqA+npZx94/7hrVN5zmjSHG4kmKqAPFIbWf50LBYK9adn/kJo6TcovS/P3+4TKBuLXqeL+siN5pS7WSZVpH3JCtwrZkrFwQI53YdFFREioTzmDeYBC5YG2COs5mrA7HSDSuQoQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1767963623; c=relaxed/simple; bh=salwZKOMcBbCVPLM3tI/7wuQ2DcFj21LFNsKb4W+7sA=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=XcrvEhGmHoaQPoheFfhJMc6te4za3tivIzxsfAKPHZim5sggTSiYeZbnA7rXX5z+lcBBU4vqobLo7bn/I3ShzTtNbxKDd7qYSuBE6QCyW00iHmj+tGrU0I/1lbcixsKBxm6l03qme7hLLM+LZZ0mmPvPmBDE6AW+tkUTr1XqicI= 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=R+/zgCh3; arc=none smtp.client-ip=209.85.214.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="R+/zgCh3" Received: by mail-pl1-f177.google.com with SMTP id d9443c01a7336-29efd139227so31757575ad.1 for ; Fri, 09 Jan 2026 05:00:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1767963622; x=1768568422; 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=EerJzBZqmLkKlZXphUYi7qXcnVy2FMOdkloJx1qklEI=; b=R+/zgCh3qzw93v2PGsDPOwE4NovWoM7ZBNmnYWi74G2BWHRDBOEM2/Xv5xyY+vgyx6 utMxvs5GZzWY6dILXlcMdFN+CiIFztp7G1fvNcpusAvYmrOeCVMAGH0EkJtuxCOnnv0x cNRadA4pbgVZoOXlaaQROf8+6ghWP173yN5rRCaqOIhyJYNhBdhCb0mc/TIWXAeXC/FL dcPeX62EwrY7tt6ji3ItwnPkGoSh4t7RHpcTYErzFbjd7NvauXmfKJZLh6jwAJkzDfU6 +/OD3usd3tYMEL/GgC8PedPxDJqNuPUzte0+rwWlkzlwIDp74soxpLZMWY9/6GMQZPAP ivuQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1767963622; x=1768568422; 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=EerJzBZqmLkKlZXphUYi7qXcnVy2FMOdkloJx1qklEI=; b=vm/rdgrAWOGXMqyX30KpCeGwGezupaMQQD0vrJEBZooX7yY7sqntEaVdttPEQv52Du SFcqVBdknvDkjNEC3ueJ2/QPAG0Q3+3cFvh+1NQ9Lk31cYGKQA42xpHFq2tVomOThAe8 1DQoe41S4VbBBhO9lkBmVqazwXaCBuSEXIpMmHzpxity2A8KbX+oPo/Di4cerAN1ut1w 8q5k1agZgXYIJYLiGc+tRqEPn9zc+RIwxFkitRDf1AX0Q4jo8Ibo7M4Zj44ki9BQ3BLc 25JB6hffVUE/d5YTphiJvQPO1zz4QYuV4hoZaf5ND32nIbB/wEPkMAjamYUIatEamRj6 AO/Q== X-Forwarded-Encrypted: i=1; AJvYcCXQtACyYakLoVHoODzXJlGDEmRZBYhif+PvSezEsSrAia9A/NylKHEL7z2v1R2/GevaOZjCoWksxnkKpqk=@vger.kernel.org X-Gm-Message-State: AOJu0Yx2waLo/ln/ud0nFG2E7kmSF6XGysQ1bj1I5me/7/0SU/HH/2wX rwZWA646vxkgopyFwkqmDAZvRZ7nMDF3BJ2LzQ3/GbDF5734i8JtDWi/ X-Gm-Gg: AY/fxX5r7P1u4KRRkk5suOBcPoOW/MVJTdRKYRVVabbyTz8UZVxYPF/2X60nSFzLbyb tUyB6tl4Kv73EvLF+9VNiBdqh0zZMa3YqLvcydZNTk7zJKINej5bNbR/QVlMASVQUHOd7s3LRe7 WbX12y/5WE9rN5b+KyXo5aSTVrQ80/fj0fRG1KJ+rMnPmbmyq4VHP9DYQgWYXcVz4tS4B9Mlp/l AnRA+wTBIMWJ1nbFqXfR3OUjP/xVHJM9Kx9S/PmP6V6t7EgofwlvbSkldhKG7nzvu6xTJ28Sdgd SyR3NG8xls4iamTBkyYlKwiMUUkKSj1m2761rw0U47YGOI0gToMomgCYiuSJ5MSFLVV8H9xbD8H f33hRaVfRZP7X99bbaiVaAm34JZFCRnw1nIDQehjGC8RaMkqHLPlPL9W2y1/ACH8sQJamnqwN7/ +h+HNRlONYDGb3q2hdllUNBIzi+DM= X-Google-Smtp-Source: AGHT+IHP0XZhJSwwQ1Pk21yDA+jtoIk8CxB90/Dh6t68iDw/EvtSrmz3Jthw2DPZIVW703U7HsaegA== X-Received: by 2002:a17:902:e743:b0:2a1:e19:ff4 with SMTP id d9443c01a7336-2a3ee4b750amr103993545ad.29.1767963621346; Fri, 09 Jan 2026 05:00:21 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2a3e3c3a328sm104927325ad.4.2026.01.09.05.00.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 09 Jan 2026 05:00:20 -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 v12 04/11] libbpf: Optimize type lookup with binary search for sorted BTF Date: Fri, 9 Jan 2026 20:59:56 +0800 Message-Id: <20260109130003.3313716-5-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20260109130003.3313716-1-dolinux.peng@gmail.com> References: <20260109130003.3313716-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..02407a022afb 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, 1, 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