From nobody Mon Dec 1 23:59:47 2025 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 3BF9B31ED81 for ; Wed, 26 Nov 2025 08:50:46 +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=1764147048; cv=none; b=BCYv9qJcrfdqoIo4OKIya7RovKlniTf7YBKVMaOnObbaxyzjJi4BIlLjHYpeeqkcI5XRiwp7UOQfgB5L3ExkDXt/XbJsogUjdBO5BCB8iN9CaJyof6545v7LEXRJWuXAY6TLPJrqMtEqXJkTtZltM6snNsOznAo+y8ont+TyDLA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764147048; c=relaxed/simple; bh=d3DscDcBlQkBeK2zxMbgxBMfQr0YMduHtPVlM/+IxLc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=aMYXLoqJPpAelgDc4lDM/pI4gpTVEXbdIzOjRjQ7XWb3tgIQ/K/BYlLXkbu52KZGeAo7PXzyfuxvn85pV1IZ3rFyf0u5ji2+htF9glCtXZBXnbWpGz7Mli17bNwIWquVaBzc0rLWqVVDNimtAuatzsCU8tfiuRPfltzUHfpMBnc= 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=d1LRS1SB; 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="d1LRS1SB" Received: by mail-pl1-f177.google.com with SMTP id d9443c01a7336-298039e00c2so91338105ad.3 for ; Wed, 26 Nov 2025 00:50:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1764147045; x=1764751845; 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=Ay7fnOLJudeGNu6Y3I2222JeR4NzT0GvBbta2hSfvtU=; b=d1LRS1SBFqIAw/EWNAYYzaxruahY8jlP5abN/EruKq00prRiIoJBgJfjgteOl9E5nB kOsIGAlDrqZSxDaYkrMyb4oyAvt5D0B7yNxqTaH2QHU0E6YjZAtpzLYUTHaKTE1JkRhd Ia4MHCjEuRRp+2X6Vmu1/f500aFlW8cEdim8jd6+4ZftZWp2fl6AoWFCKuARuEtihiD4 tqrrYnI91m+rFXyo6Wp5w/aJlzuvOwsVfDofjmsa9oF2I7lay5fZWkEsGxjrXPmVaCH5 Xnj+oOtt0yEPu00XlqfxWtOJ/pCnpKtEqcKp4w+VNsNKhWQKjxRCMZ2WQxeOJNOVjdWk 2xGw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764147045; x=1764751845; 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=Ay7fnOLJudeGNu6Y3I2222JeR4NzT0GvBbta2hSfvtU=; b=prSB0fcCV9qyvYyq+plwYcGJJc1t/a2781RR8iKy7pLLPGLLhshoebBUkPdHiZXg10 legfp/ndfKwwo5kSYPOn/C+x0FWwJPjX7+GOSzxV1oSdPZTWAXb1w50LdDPLuDGQpsXY y7Wv1UHEszSfk3lUm/NsLs+nHNJG/NOlP8jWV6+C+BDMtRgIzKl7wP5eRds42RnoDODu wcjHRsXUUAPYPhdFjLng9PC/jsWiUtxeRVS3N8v7qQLPB85suNSzrMlyGKNz8IjfoFNK e0+JiNvUXjLWZHBRFhXKZv4TlFmuzsY2zkyPsRUBMRf0AgpxAFZYL/RVJzn6ysBAjDNz 3E8Q== X-Forwarded-Encrypted: i=1; AJvYcCXCGxryjFZpZ9AqGm6CBlRCAvra5NC/mo7C5shny+p26tluMW8C5SV9iyEmV6zpBxYA+mJBWMHnqD70rfQ=@vger.kernel.org X-Gm-Message-State: AOJu0Yw5cJXENl34l2YbnR8K6ieXfxT0Hq/867AM1DGue0MF/oK0y0ia p7/dCoiD9mZwm91LJ0tIMgL/iVW80wKq8oH3aDXH/NpPUWvmKTdW2wW4tjvwpVPgF40= X-Gm-Gg: ASbGncua7zySLIC+y4e/XfBTIG0/0UIRpwppeSup6QGBnVYngbwGUDbx2ERpatgmFNm La6EG1nApi3GJiNOjKV5ryIif7ud6Hpx4ECf0qlwuh5FYHpmbMvLdMk+jl656SWY+Fhl3OrCt86 I2KtTe5KAkB0Imas1o9y0pZMQW1SYHK6hBe8z/n2qPYcaKMMavSGje1dmWpmIYkUvS1uFR/7LDt qUehRhpwGwurn84fjSA9z8Ps3kiDCRG1ohcVpeOBrQrNwvb39cWXd3BQWrc/I1rPfRWlJrEz8E7 eOQ8DSG/Wx3FCeFwjl44tG9z7jpsxv0UuPZ4b6u6MgPmvvzJctY9uu9CWFghWtz0gq7mKsobiEQ aJqUCud5hgQsRBDg8rHxbMPutYnqiIjIENl8/kfv5A16Ki1r2dixd+HLsA2l/EDJywlU6N0Gzjj ZaWvx3G6RM8BPignM0ybJnboIM6dM= X-Google-Smtp-Source: AGHT+IExZ5vV40jQbHSa6VDCuGIq7XV7fGyz1t0658/NLZTAynNpqwve20+hXuyWBrgSMrtQ3opEpQ== X-Received: by 2002:a17:903:38c5:b0:298:1f9c:e0a2 with SMTP id d9443c01a7336-29b6bf804b1mr226373385ad.54.1764147045527; Wed, 26 Nov 2025 00:50:45 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7c3f023fd82sm20885721b3a.42.2025.11.26.00.50.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Nov 2025 00:50:44 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, ihor.solodrai@linux.dev, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, pengdonglin , Alan Maguire Subject: [RFC bpf-next v8 4/9] libbpf: Optimize type lookup with binary search for sorted BTF Date: Wed, 26 Nov 2025 16:50:20 +0800 Message-Id: <20251126085025.784288-5-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251126085025.784288-1-dolinux.peng@gmail.com> References: <20251126085025.784288-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 --- 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 26ebc0234b9b..7f150c869bf6 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) { + __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 (tname && 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