From nobody Wed Dec 17 05:07:43 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 934133126B5 for ; Mon, 8 Dec 2025 06:24:13 +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=1765175055; cv=none; b=RjxaoZPrml+pDO/6jLuuORaG1zSl1hm0GQgu+dZdoU+yagsOyyRaBRQ8t6NQ/cMBURM1Vqocoi8RZKUyrD1Oiy9uFAPVNwtlSzVJ1DL8CoOgAXHZd2XBIuHJpNsPChy3MU63GYgZTwF+Puq8HNR1dionrlE+3VjDOzh4jzsW1TQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765175055; c=relaxed/simple; bh=d3DscDcBlQkBeK2zxMbgxBMfQr0YMduHtPVlM/+IxLc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=odhnGgU+pOghkwKVVSGPvSISKVAryDAgBQcheAxokQKHOKseLltc+OMFaxdon4iG+KPCueUyG5ALf9XU/NMp+eeOwzz3B8H0bKjtWMNYIXzgQjCgVduHBuKAkcU/J3vFJ9lP6ut8c+IWHJF3F82KZ3XUV4GzC7UXKJuTckK3j7M= 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=ATfACYKh; 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="ATfACYKh" Received: by mail-pf1-f180.google.com with SMTP id d2e1a72fcca58-7b9c17dd591so3717525b3a.3 for ; Sun, 07 Dec 2025 22:24:13 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765175053; x=1765779853; 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=ATfACYKh0KmfZyazUaUgBUYGLQAdvuT69fn4lsx5rk9mTgT6rCO0Plqkumwxt6CzaI uPcvWLN54kSABX/rt9s6DQZz+Y9WMCZnZEYLF0CLT2pvKKffM7RMROOuU7eQ31Ro6WqI MIXxpxq+ZMthz96pwediia9HCW4bSF65cBCguMet9vPzc/RAz+58JyrmRWVZjSqjxSEN p2OGQV9S4p/cea2CdDcgsm21jIMjbYd1Br5YF72JSNbh7bWPxBIKPtN7F869p9lMc81Y cxjUCSMYsG2t/gOv8rky71+O29NPA7JFW6fpwv6JZ6gEUhZCBQzELchZHbNDXZib8V4D CJEA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765175053; x=1765779853; 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=rtDZ6FUgvGp0jmrN2qfg4tKYYTy0PUltwNaGJOiiXeX5DAwtqq8mhmii3pxd1eR64c RES2A14JQBwM2e9VmP7YPofMakuFe521RyUxLbY4h4ITz/iZY0Eujj65gV3e//O2YOqe 7wd9uzABvBHcSWbvz8dPmnziqamhDcvr9nfGHcRCSr14A50L3px0jwAXaafDDd/kC2SD Pn/aptSyKlaofA60G2SX9huYBjwLWLR8nrd9TFSRJZ/pjaqm72RbPBiXYhrD4HL6YvUM QgOKbGTXT/pgWnzb6E4emXQ+Z1xwAIFyEwrHwIxTUIF0E1qBDYch1je5tTTAw1LWaqkh R0/A== X-Forwarded-Encrypted: i=1; AJvYcCW9aHNjAco4FXXNKsYs4m1Ui66vxeWkaV7TlEgDioc/hP/qLCRnFjEFts52K7EdcLCA5y8X8ASpjCA7F0Y=@vger.kernel.org X-Gm-Message-State: AOJu0YzdqSi8AvqqjYZMAS8nrk9EE1+H0qX1qPp/Bgv7UnYHY1dsXQk0 5/fLO7QEBfVPvfa52gu89KJTYyCqFaijksAXUxbBRoAL2gdxK6kKDt1p X-Gm-Gg: ASbGncscjnEvCz3DbPlWTKa67QPyedeqMMw8Soaocbe44x0npDsJko6zRnAJJqnURiu BmXmETNnf2iuBg1bK7NtMOaSDkRk9GGCvJKCWXnx9MZCAFIwufklYnR/8PtpfQwwQdl8cNhlK1T dDMbQBPpqfXw6lcZHBidl21xeeXqJJPptJ1nTweZC+/qztjFVHOlP6RtDleYRE8kL1uFGQ5aY/i RMHCta7bYBTdlKZkP2DasvMwYvys90dTjptN8jQ5f7KOgavXOE7QzVJmhm5lgujiXOnbmlGIQz6 w3vxILAW7LH755fByHG7NADfDdxtc9kXw/LpT1YumZLfttmkQpbvAHQ7anJSl8sZzVT9MScIRDw lt5uDFnQlFnmnHStE/hEu+OH3nLnfY2R215hemb/h0zX7HCWVqyMslHXSaeLXHCTwWEgTMp1lul 7mBttH1ikMNVq2DrblPy//fEoa3oE= X-Google-Smtp-Source: AGHT+IHNagrkdB1dXKmAfAxFX7NHUjkLDIJK+H77kgo1bz0xfXRjOReqMV8tPTqftsQHvcAYdui28g== X-Received: by 2002:a05:6a21:6d89:b0:366:14b2:30a with SMTP id adf61e73a8af0-3661801fc52mr7083372637.61.1765175052779; Sun, 07 Dec 2025 22:24:12 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-29dae49ca1esm112555855ad.2.2025.12.07.22.24.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 07 Dec 2025 22:24:11 -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: [PATCH bpf-next v9 04/10] libbpf: Optimize type lookup with binary search for sorted BTF Date: Mon, 8 Dec 2025 14:23:47 +0800 Message-Id: <20251208062353.1702672-5-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251208062353.1702672-1-dolinux.peng@gmail.com> References: <20251208062353.1702672-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