From nobody Mon Feb 9 09:50:46 2026 Received: from mail-pf1-f179.google.com (mail-pf1-f179.google.com [209.85.210.179]) (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 9FC7228726D for ; Thu, 8 Jan 2026 03:17:10 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1767842232; cv=none; b=FRvjhpHvCi81VdnxPeCha+H9LJZi+NfDzPjqmewno+jlkkNynnSbentBN80ugTxfQY0sJjP1Ni/t790ZaqQ2XhkMkKF980HlxrNweLb596sQCtm7xO0rFnYszPxYF3GYuv0eLG6QMYilyRyUwhkWTVJdj/Xa610Eyr/o789OqGw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1767842232; c=relaxed/simple; bh=c745HJ4eBL9O6dcjNGxahlJgFWWLs7lhqs1RisTI0i8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=cFsJ/7G+kb5WDKLyFmQCy7hXl08NH0kNQN3VF5lIFF1sTHlTBLzU6BZOC7tnSJjTfl55vQEsxS6kr+vXosc9VIg7npNYETqd9BAJIA5uVctWVBZZjk+XMwAC+ICY2wxOd4vuI59WOsdg3EJvmDwEujH1GipBD92IdnzeGXXX88E= 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=XIWJglGa; arc=none smtp.client-ip=209.85.210.179 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="XIWJglGa" Received: by mail-pf1-f179.google.com with SMTP id d2e1a72fcca58-7b80fed1505so2018000b3a.3 for ; Wed, 07 Jan 2026 19:17:10 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1767842230; x=1768447030; 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=QQrwHecK7iJFotsalH69RC9yNT/x39b0nH1K09oW1Js=; b=XIWJglGaS33yu28VmoRDhibmZorvC5zlVvIRKkfDSZuXHOD0i3H+x2vzqhCY5YXTPp J55tPNsz6C9T4Km1s/FTOYKbgNYBfUKip19fRS0Q4SZOnXP3CAdfpt3wpw8+mB3kNthL qwrfn1jp9Bw+vi0anMXkVjpEfD+CsHFnjCM9jCiVYmN0PjyYuutPqWWxFYFDbVhqrKCo 0AZD4O1dBDREJmz4fIiaRiUCSjihOPBdgpvqbP4Qv9WR6dz+JU27YsPtaz1Sb0tIROd0 oQYYUSAcBNXN1Cu/MCgwfwb/HShdId0nTB3zySYn3wM1Kuz4gpQkGVu9zARvuJXj3KoJ XELQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1767842230; x=1768447030; 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=QQrwHecK7iJFotsalH69RC9yNT/x39b0nH1K09oW1Js=; b=iI4BQ33M2XBCj8n4d2PDbIvsPGpwBdpwHeT9u9sLk7MwlNOVGqzBAggfNUSDL164kh UFaSFqJzJrQj6GA2BVtUm1NolQmgWuq9kbt4bz7bWOCqYskbcha1boHPDPnIzKocr8hw MIHcaB4A+peGRHJppJiDRj6ni1Pt7URwJrurLluiw1PBzyivm3vcJvrb7Zt1qRijXGqa GLuIBkOlWgH5/cAc1BQgm3NoVrFbvECybcd8UiIo+QwnYrTYYhsFbEwVauz05gYqlLQf dDnp3UkY7eulW9fBWfWJ5BKE+bl2wuds+lP9wRTOh5l4XCfTOig1Zn4yNk6WRpvOpNEU GTSw== X-Forwarded-Encrypted: i=1; AJvYcCWXleHVIHmVibwjKf5pgA934tNUdYyYIUp4gJnp69cVXNi1yfv7gVgDade5NWIGPGllpwmGi+0TUZfoBJA=@vger.kernel.org X-Gm-Message-State: AOJu0YzKvQj72AboCI6Hmm6t9Qkt2u6PmidEatRHk0Usk7RBeUfglkkf sKjqIblBnfZkK6YLBTzKI6kiCgpYZS4EiTi/lC1qABPo712nXAaG0KBV X-Gm-Gg: AY/fxX5KgoElPS1bgQ6doXR9Htyag4uf8S3ZnRYlqSLeEqiFAULGfxEXwEvcgjoc7rG hNW8QhiJxfEAdi7L3QA/d5Et6WEzzavOZjCnPHjb2tS9QxsoHn2Ev+a2s1ePThArjsJD25F+qps ftAukVnxLP8JvSOBpBNrAKxHTe0VraDZEm9CRv6vmjjXBM2x3r92dq0edRHlcU/sKbt/YksXWUd F3N/eB/a3hAbbWGEbsTVxANww5CBiDDkLI5VFjL4J1tTgbHUqfXIPiTixwxXxkQjryawc3UH2Ni H+vatzkzEAAaabR10Tx3dWTxwMgmVARKNRwJe3FAvpfLTzHlVwc7FL+SiWmnS0wH6qN35PJgZ91 33SDEpc2jpK2k44bPkIYbh649V9a2U5xl49ADA+uEBdl8eA+vZdw9qoR6EftorEtShk77N2IWUf 6AAhf+JS09jTorEcYbSzHC38bnKrg= X-Google-Smtp-Source: AGHT+IG6VmaJGUutpIyeyvJlJbHM3t8zY9VuCBzH5ppbJhqIHdZT2QK6JoML3+Lr+VD5o+fEXKe/zQ== X-Received: by 2002:a05:6a00:340a:b0:7f6:e75d:8efa with SMTP id d2e1a72fcca58-81b7de58e2bmr4118281b3a.17.1767842229910; Wed, 07 Jan 2026 19:17:09 -0800 (PST) Received: from pengdl-pc.mioffice.cn ([43.224.245.249]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-819c5de655bsm6134860b3a.60.2026.01.07.19.17.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 07 Jan 2026 19:17:09 -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 v11 06/11] btf: Optimize type lookup with binary search Date: Thu, 8 Jan 2026 11:16:40 +0800 Message-Id: <20260108031645.1350069-7-dolinux.peng@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20260108031645.1350069-1-dolinux.peng@gmail.com> References: <20260108031645.1350069-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: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- include/linux/btf.h | 1 + kernel/bpf/btf.c | 91 ++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 83 insertions(+), 9 deletions(-) diff --git a/include/linux/btf.h b/include/linux/btf.h index 691f09784933..78dc79810c7d 100644 --- a/include/linux/btf.h +++ b/include/linux/btf.h @@ -219,6 +219,7 @@ bool btf_is_module(const struct btf *btf); bool btf_is_vmlinux(const struct btf *btf); struct module *btf_try_get_module(const struct btf *btf); u32 btf_nr_types(const struct btf *btf); +u32 btf_named_start_id(const struct btf *btf, bool own); struct btf *btf_base_btf(const struct btf *btf); bool btf_type_is_i32(const struct btf_type *t); bool btf_type_is_i64(const struct btf_type *t); diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 539c9fdea41d..d1f4b984100d 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 named_start_id; 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,21 +550,85 @@ u32 btf_nr_types(const struct btf *btf) return total; } =20 +/* btf_named_start_id - Get the named starting ID for the BTF + * @btf: Pointer to the target BTF object + * @own: Flag indicating whether to query only the current BTF (true =3D c= urrent BTF only, + * false =3D recursively traverse the base BTF chain) + * + * Return value rules: + * 1. For a sorted btf, return its named_start_id + * 2. Else for a split BTF, return its start_id + * 3. Else for a base BTF, return 1 + */ +u32 btf_named_start_id(const struct btf *btf, bool own) +{ + const struct btf *base_btf =3D btf; + + while (!own && base_btf->base_btf) + base_btf =3D base_btf->base_btf; + + return base_btf->named_start_id ?: (base_btf->start_id ?: 1); +} + +static s32 btf_find_by_name_kind_bsearch(const struct btf *btf, const char= *name) +{ + const struct btf_type *t; + const char *tname; + s32 l, r, m; + + l =3D btf_named_start_id(btf, true); + r =3D btf_nr_types(btf) - 1; + 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; + s32 idx; =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) { + idx =3D btf_find_by_name_kind(base_btf, name, kind); + if (idx > 0) + return idx; + } =20 - tname =3D btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; + if (btf->named_start_id > 0 && name[0]) { + idx =3D btf_find_by_name_kind_bsearch(btf, name); + for (; idx < btf_nr_types(btf); idx++) { + t =3D btf_type_by_id(btf, idx); + tname =3D btf_name_by_offset(btf, t->name_off); + if (strcmp(tname, name) !=3D 0) + return -ENOENT; + if (BTF_INFO_KIND(t->info) =3D=3D kind) + return idx; + } + } else { + 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) =3D=3D 0) + return i; + } } =20 return -ENOENT; @@ -5791,6 +5861,7 @@ static struct btf *btf_parse(const union bpf_attr *at= tr, bpfptr_t uattr, u32 uat goto errout; } env->btf =3D btf; + btf->named_start_id =3D 0; =20 data =3D kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN); if (!data) { @@ -6210,6 +6281,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->named_start_id =3D 0; snprintf(btf->name, sizeof(btf->name), "%s", name); =20 err =3D btf_parse_hdr(env); @@ -6327,6 +6399,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->named_start_id =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