From nobody Tue Dec 2 02:41:07 2025 Received: from mail-pl1-f169.google.com (mail-pl1-f169.google.com [209.85.214.169]) (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 CEF352FD66E for ; Wed, 19 Nov 2025 03:22:00 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522522; cv=none; b=OPvcjrOTAWQcd0PoXTrnPa3KzTnCe2/6pMT7ZDxw0rP7fcfuK6B8Umzxp/hmtbY3hSrfZN/fbSgaqBEi17GeHVrffZdTSg4Bjrqg2GP7ImZFgjjnkBfXTwRXt0m8iXfeawR71R1c4OFruPB+H1TR6zWQh9XUoqGj+wPSBb3L7S0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763522522; c=relaxed/simple; bh=1JCm2gAw7szR6coFfKCMu4oP2N4ZVTGa8uyyO11FaJ8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=R+HTiMLyPYn3ULkpCQ2nUQkDZabQLwol8yKRDeUibvK8D7aNBC1olpwM68vRnDG20Xa8vCUepI2uj3Il39ELFQnrKcX982IeXjoK5ixxuazk6vXEevfn1wOCNgVR3/9VbKUhlKFHjStNbMlMIBaxu/GWtz+AgvdGXF0sWpQLgoQ= 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=k9dE0G4a; arc=none smtp.client-ip=209.85.214.169 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="k9dE0G4a" Received: by mail-pl1-f169.google.com with SMTP id d9443c01a7336-29845b06dd2so71553615ad.2 for ; Tue, 18 Nov 2025 19:22:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763522520; x=1764127320; 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=Rljz3QHqavQzM2+LGEfUj2V9NIFH9chI7oYU2DEYmt8=; b=k9dE0G4ag5Fnx9SS5p3L8YYXjqV+wx0Bzsa/FfYdvx83lFSAJuwAeSZ94/nmlGWASO 73RJMuRdlhdrwmndRSiqcLWD84irgrOPkMmACK4USkLgGjAbJ5SraLKR7e/yDfsTA24k e0zVuBTNRfRTOzSBL5Wov01PRKu/PB4lpQt8kU3zgT9mMuNozyQe8NYCQSNNi/NyzK0i 8IVPe9vx1L1fcshIMbwrBhse/kEPT8AJE+dMkBskkmsZzGE5PG7d7soPfUxR8Pa6zSM4 31hgW4/2IpHni4PbldFqDCZ5d02TyPUda1lk3AuzuT2zGtFMC+ycNe9K+0m/EZyGHksv nuNA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763522520; x=1764127320; 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=Rljz3QHqavQzM2+LGEfUj2V9NIFH9chI7oYU2DEYmt8=; b=wP7y1cuNm4N1GDEzu89oj0ZDxlHUpgcP4By03dSfOSwhi6o0FaRs6tCSShAM65u4fO otoL1ZwDaVDO6iXlubI9H0VcKiS3kZPXH11BxjOf4sSh1gMGUvrKjH5kQkDkSCaHMREO y0wfMWbRzacEuzLEZT34C/cTjzcz9GgiyRwxVzkDyRlFStI4eLVZ2hg8/iPWkW6cxoi6 pp00tp73B5niDb8kOCxsuyZvTJkKbMArdeItpMExDEP6+ewuKCu+6nRBxdzQ1xNecQTl rkOR++quZqK6qks3oGT/cRSE64BCb+m3gwP7jQVhPAv/4BUy9VjOoMBzt7QuWCyAbiGM 4gNw== X-Forwarded-Encrypted: i=1; AJvYcCXNE8a55hg9kjD18xQdGw+2n+a/YSUcYiJMGCcQawHHcfA3Anf3ODUrHZ3xObF3KDBmcxJecmCwZCcSp7A=@vger.kernel.org X-Gm-Message-State: AOJu0YylsnTpwFS+XXKHvoyuAG4KkfI13vLeAfGYzBR5J7magbE7uhDs H8kUOvWoiV8JRrrAxA8arIaHpSYwXtEnJV6V5C0il8Q69YzV3JBgaZ9Q X-Gm-Gg: ASbGncsJLs6+Q6NpM5JHpg0IPe6FPYH+kPnrPr67NPqAzbpSU5FSre8RPmx9LKgtQFa DI29TOlZfD0Re86oL3Q7mJCcMkssEXJKVm3TLZmxtrxb7svyjUm6qUof9PlhwE8621o/3BMiEJM HrqMI+7cTHPFN6G93KDtTIONpdpG01MHsmM/AgEVvxH+rXpZPZsIT5JfD/TU2Hxt+70z1sMc6lA AKCaFOqF8X5AZtLPyn266LGGk+4kuhoDMun688LuTaJTA1zIkCr2qm/cpO8fSUHZ0nxiuD4fYfs Z0UpVJWWdw0DTHYth+Wv2f4TwQ7M8AzVnUVndbFHgB7HY2fPh25XqMrnXOjjMDUzkfzx6XugA/E 7UkKSbY/GKpig8qzJtOOnE9xflu4XhjEJutaUZdqn4p03Q9TmieFjU1mlpCFPD0+kLt7GAvw5Hn Utbl7JSmVR2UAPHeO/AaWWwVhkkW9zmzK2TBtNog== X-Google-Smtp-Source: AGHT+IGMGm4ssuCAcSuhBLMTVMUN9IlTul3KIQyJF8pQPYcJbxELNk2HFjnnrYFBfI+sDmaW0pEWCA== X-Received: by 2002:a17:902:cf43:b0:248:ff5a:b768 with SMTP id d9443c01a7336-2986a6abcb9mr216810575ad.10.1763522520091; Tue, 18 Nov 2025 19:22:00 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2985c2bed5asm188352485ad.88.2025.11.18.19.21.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 18 Nov 2025 19:21:59 -0800 (PST) From: Donglin Peng To: ast@kernel.org, andrii.nakryiko@gmail.com Cc: eddyz87@gmail.com, zhangxiaoqin@xiaomi.com, linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Donglin Peng , Alan Maguire , Song Liu Subject: [RFC PATCH v7 6/7] btf: Optimize type lookup with binary search Date: Wed, 19 Nov 2025 11:15:30 +0800 Message-Id: <20251119031531.1817099-7-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251119031531.1817099-1-dolinux.peng@gmail.com> References: <20251119031531.1817099-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 Improve btf_find_by_name_kind() performance by adding binary search support for sorted types. Falls back to linear search for compatibility. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- kernel/bpf/btf.c | 83 ++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 73 insertions(+), 10 deletions(-) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 0de8fc8a0e0b..5dd2c40d4874 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -259,6 +259,7 @@ struct btf { void *nohdr_data; struct btf_header hdr; u32 nr_types; /* includes VOID for base BTF */ + u32 nr_sorted_types; /* exclude VOID for base BTF */ u32 types_size; u32 data_size; refcount_t refcnt; @@ -494,6 +495,11 @@ static bool btf_type_is_modifier(const struct btf_type= *t) return false; } =20 +static int btf_start_id(const struct btf *btf) +{ + return btf->start_id + (btf->base_btf ? 0 : 1); +} + bool btf_type_is_void(const struct btf_type *t) { return t =3D=3D &btf_void; @@ -544,24 +550,78 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +static s32 btf_find_by_name_kind_bsearch(const struct btf *btf, const char= *name, + s32 start_id, s32 end_id) +{ + const struct btf_type *t; + const char *tname; + s32 l, r, m; + + 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_name_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; + } + } + + return btf_nr_types(btf); +} + s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) { + const struct btf *base_btf =3D btf_base_btf(btf); const struct btf_type *t; const char *tname; - u32 i, total; + int err =3D -ENOENT; =20 - total =3D btf_nr_types(btf); - for (i =3D 1; i < total; i++) { - t =3D btf_type_by_id(btf, i); - if (BTF_INFO_KIND(t->info) !=3D kind) - continue; + if (base_btf) { + err =3D btf_find_by_name_kind(base_btf, name, kind); + if (err > 0) + goto out; + } =20 - tname =3D btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; + if (btf->nr_sorted_types > 0) { + /* binary search */ + s32 start_id, end_id; + u32 idx; + + start_id =3D btf_start_id(btf); + end_id =3D start_id + btf->nr_sorted_types - 1; + idx =3D btf_find_by_name_kind_bsearch(btf, name, start_id, end_id); + for (; idx <=3D end_id; idx++) { + t =3D btf_type_by_id(btf, idx); + tname =3D btf_name_by_offset(btf, t->name_off); + if (strcmp(tname, name)) + goto out; + if (BTF_INFO_KIND(t->info) =3D=3D kind) + return idx; + } + } else { + /* linear search */ + u32 i, total; + + total =3D btf_nr_types(btf); + for (i =3D btf_start_id(btf); i < total; i++) { + t =3D btf_type_by_id(btf, i); + if (BTF_INFO_KIND(t->info) !=3D kind) + continue; + + tname =3D btf_name_by_offset(btf, t->name_off); + if (!strcmp(tname, name)) + return i; + } } =20 - return -ENOENT; +out: + return err; } =20 s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p) @@ -5791,6 +5851,7 @@ static struct btf *btf_parse(const union bpf_attr *at= tr, bpfptr_t uattr, u32 uat goto errout; } env->btf =3D btf; + btf->nr_sorted_types =3D 0; =20 data =3D kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN); if (!data) { @@ -6210,6 +6271,7 @@ static struct btf *btf_parse_base(struct btf_verifier= _env *env, const char *name btf->data =3D data; btf->data_size =3D data_size; btf->kernel_btf =3D true; + btf->nr_sorted_types =3D 0; snprintf(btf->name, sizeof(btf->name), "%s", name); =20 err =3D btf_parse_hdr(env); @@ -6327,6 +6389,7 @@ static struct btf *btf_parse_module(const char *modul= e_name, const void *data, btf->start_id =3D base_btf->nr_types; btf->start_str_off =3D base_btf->hdr.str_len; btf->kernel_btf =3D true; + btf->nr_sorted_types =3D 0; snprintf(btf->name, sizeof(btf->name), "%s", module_name); =20 btf->data =3D kvmemdup(data, data_size, GFP_KERNEL | __GFP_NOWARN); --=20 2.34.1