From nobody Fri Dec 19 11:21:45 2025 Received: from mail-pf1-f180.google.com (mail-pf1-f180.google.com [209.85.210.180]) (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 C47C332939C for ; Tue, 4 Nov 2025 13:40:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762263653; cv=none; b=Za7q2VI9uhXTo0DGeAjDZLwmislRKuw9gZSsDq8OKHClfzINPIcJ/ad64qAvfoQEIuEB/9xbge6rLILgKw2Nw8dsBzd17BsfMzmJnDwtLuEAwrV4MhEr7iAlVyuJoqaHkS9jE4bUlM6nhrL24Pm5iJRe++COGnLsbvWQ+w9cUjA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762263653; c=relaxed/simple; bh=H8W7FunBp7qoGcxg5bGEeewgRaf3u8ILn6elRUcxoyk=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Y6EyvISrDUqCtYA05RHGp+0e2nSZbViVUZ3L4mj3/iRsW5p93EeB3J4LsSle4KHYG7zhlFewHvEBtLsimTFVDxvkK+Tk+uvwuA7yQKBQvZgXhb0fR4fObafHuRjHJzQI5TpGLcKX9D7X7kwq+XswXX+kpIvtTbx0GG+PM6iCZic= 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=fp8EC5DM; arc=none smtp.client-ip=209.85.210.180 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="fp8EC5DM" Received: by mail-pf1-f180.google.com with SMTP id d2e1a72fcca58-7a9cdf62d31so3509470b3a.3 for ; Tue, 04 Nov 2025 05:40:51 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1762263651; x=1762868451; 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=/NsrgOo4ocG/4BxsQgHROI9+0LDTBXUxvTM9Wy/6b6g=; b=fp8EC5DMdVWJEAgeGKsN9e4KRYvc45KgxM/19sd3yhrebHWvucqSHU6M6SK3xd3GKA wwWMn0XcSHFAX8BitOoPsoX1zcg+Vp/MuCpuUcXTyHqkXkG3LeGueS3WTmuNlvR8k6Vr BKUbFjallSFBgszlDxxddjOLH0OSXF14PQnH6ArcT+W8JTCnTFY6PkNC8jYPMWqOT6CA QcmQXDmbT+Lug4sQZVA/b1f+YHWyGyNRLttNVbSNfOHixeUr8phuH4BTD3WIuk+Zblgs S83jyniCx40JoIWveT9bXnLZJeHOLhByUwT1l6eQD4cQy1zN9erPk8lJcCHggI46eAHF oBvg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762263651; x=1762868451; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=/NsrgOo4ocG/4BxsQgHROI9+0LDTBXUxvTM9Wy/6b6g=; b=FeLtbLhVxYCRCmA1bywZhfboE/uuNCYCYoMQW2inmbWNJh1Uf+Ef1Wnar/7Ofa7AxQ b012VaRkT4rhnzQ0pjHvdnOUrGdAC5IudnIPyDyYOarupqQAmtlgnfaNpAID9Z/hq3Fm 5fy2EtEFfL0gI7G1JpKXS3dWP1Qt+xgm/8beR4elc6lFl4WzD5QITGcIoDC+NKSzzSTB obJ3qs+J/xWmVa7QBfsVbHVTRiCCls3hpQx8vWdRCBPn2adnMZ3/3tQmXryqfxLrS+77 XJaisJF80jzOnVtaCo1C3vHRF4djc2YS+fqQsZ8axC4GbrqANcRjTx4UMcmRlP92btjk nnIw== X-Gm-Message-State: AOJu0YwOfD6g+dizrJgra0KbgJXlxyXlHoemhbhZUEbB39o4aUostggI Tlzw6flCmGypqPvs7R8bV0MVMJ9Bnqi5HsBZliFXjkc1PlVff6ld6C6y X-Gm-Gg: ASbGnctwyL9OJXXRirsOhZVnd3nL12V7sTuWZTVKMXEL2FdYrl3k5nBXN0erydviEQ7 Lng8OnSjOSovcr35c/Tu0AwdR2F96qdEejF/aJuXVHgeVAUVOKBfoLAAnWzTsLbXybsW73i/M3P sOp58s9K3FKT10iYQ0hvkyVnmNyXjPeJS4bJbfK5lutX69Y4C8ID8MU/N1MRPtmNkh5q/Aw2TVt 9mUg+bh8hg3YgxPFcuNY3s1T/2DRX6v99w8KZWnjECrtduLuEcMP3i3mt4Xa0BoGJhze3RB4LSn Xnovo+cfZ6541r0F8Gzmi9x5/a56BmjytshqO1xzky3n2PvHIctOLy3E7Hh/lbto+hndODZRGyB rODv/VoTXe26Jug6XsMdwnhiVZIP+bNUTmd8EiPB9Wg9ZwH7IcWyzawgRvQUe9iq2cH04obKLvf l/rQK6MKLumn8YekK9 X-Google-Smtp-Source: AGHT+IF0jGd0yl4ZUQ5poLvNggv7g7BAW0tkkkPqmp6n4W4vlSXsBr2+elxUCoxY1RlLNu9+9K8/Zw== X-Received: by 2002:a05:6a20:9151:b0:344:b429:fc64 with SMTP id adf61e73a8af0-348ccbfb900mr22350595637.50.1762263650965; Tue, 04 Nov 2025 05:40:50 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-ba1f87a7287sm2499238a12.31.2025.11.04.05.40.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 04 Nov 2025 05:40:49 -0800 (PST) From: Donglin Peng To: ast@kernel.org Cc: linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Eduard Zingerman , Andrii Nakryiko , Alan Maguire , Song Liu , pengdonglin Subject: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF Date: Tue, 4 Nov 2025 21:40:29 +0800 Message-Id: <20251104134033.344807-4-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251104134033.344807-1-dolinux.peng@gmail.com> References: <20251104134033.344807-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 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 Signed-off-by: pengdonglin Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 142 +++++++++++++++++++++++++++++++++++++------- 1 file changed, 119 insertions(+), 23 deletions(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 3bc03f7fe31f..5af14304409c 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,134 @@ int btf__resolve_type(const struct btf *btf, __u32 t= ype_id) return type_id; } =20 -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +/* + * Find BTF types with matching names within the [left, right] index range. + * On success, updates *left and *right to the boundaries of the matching = range + * and returns the leftmost matching index. + */ +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const ch= ar *name, + __s32 *left, __s32 *right) { - __u32 i, nr_types =3D btf__type_cnt(btf); + const struct btf_type *t; + const char *tname; + __s32 l, r, m, lmost, rmost; + int ret; + + /* found the leftmost btf_type that matches */ + l =3D *left; + r =3D *right; + lmost =3D -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); + 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 - if (!strcmp(type_name, "void")) - return 0; + if (lmost =3D=3D -1) + return -ENOENT; + + /* found the rightmost btf_type that matches */ + l =3D lmost; + r =3D *right; + rmost =3D -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); + ret =3D strcmp(tname, name); + if (ret <=3D 0) { + if (ret =3D=3D 0) + rmost =3D m; + l =3D m + 1; + } else { + r =3D m - 1; + } + } =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); + *left =3D lmost; + *right =3D rmost; + return lmost; +} + +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; =20 - if (name && !strcmp(type_name, name)) - return i; + if (!btf) + goto out; + + if (start_id < btf->start_id) { + err =3D btf_find_type_by_name_kind(btf->base_btf, start_id, + type_name, kind); + if (err =3D=3D -ENOENT) + start_id =3D btf->start_id; + } + + if (err =3D=3D -ENOENT) { + if (btf->nr_sorted_types) { + /* binary search */ + __s32 l, r; + int ret; + + l =3D start_id; + r =3D start_id + btf->nr_sorted_types - 1; + ret =3D btf_find_type_by_name_bsearch(btf, type_name, &l, &r); + if (ret < 0) + goto out; + /* return the leftmost with maching names and skip kind checking */ + if (kind =3D=3D -1) + return ret; + /* found the leftmost btf_type that matches */ + while (l <=3D r) { + t =3D btf_type_by_id(btf, l); + if (BTF_INFO_KIND(t->info) =3D=3D kind) + return l; + l++; + } + } else { + /* linear search */ + __u32 i, total; + + 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, --=20 2.34.1