| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <20251106131956.1222864-6-dolinux.peng@gmail.com>
Date: Thu, 6 Nov 2025 21:19:54 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: ast@...nel.org
Cc: eddyz87@...il.com,
andrii.nakryiko@...il.com,
zhangxiaoqin@...omi.com,
linux-kernel@...r.kernel.org,
bpf@...r.kernel.org,
Donglin Peng <dolinux.peng@...il.com>,
Alan Maguire <alan.maguire@...cle.com>,
Song Liu <song@...nel.org>,
Donglin Peng <pengdonglin@...omi.com>
Subject: [PATCH v5 5/7] btf: Optimize type lookup with binary search
From: Donglin Peng <pengdonglin@...omi.com>
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 <eddyz87@...il.com>
Cc: Alexei Starovoitov <ast@...nel.org>
Cc: Andrii Nakryiko <andrii.nakryiko@...il.com>
Cc: Alan Maguire <alan.maguire@...cle.com>
Cc: Song Liu <song@...nel.org>
Cc: Xiaoqin Zhang <zhangxiaoqin@...omi.com>
Signed-off-by: Donglin Peng <pengdonglin@...omi.com>
Signed-off-by: Donglin Peng <dolinux.peng@...il.com>
---
kernel/bpf/btf.c | 117 +++++++++++++++++++++++++++++++++++++++++++----
1 file changed, 107 insertions(+), 10 deletions(-)
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 0de8fc8a0e0b..66cb739a0598 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -192,6 +192,8 @@
*/
#define BTF_MAX_SIZE (16 * 1024 * 1024)
+#define BTF_NEED_SORT_CHECK ((u32)-1)
+
#define for_each_member_from(i, from, struct_type, member) \
for (i = from, member = btf_type_member(struct_type) + from; \
i < btf_type_vlen(struct_type); \
@@ -259,6 +261,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 +497,11 @@ static bool btf_type_is_modifier(const struct btf_type *t)
return false;
}
+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 == &btf_void;
@@ -544,24 +552,110 @@ u32 btf_nr_types(const struct btf *btf)
return total;
}
+/* Performs binary search within specified type ID range to find the leftmost
+ * BTF type matching the given name. The search assumes types are sorted by
+ * name in lexicographical order within the specified range.
+ *
+ * Return: Type ID of leftmost matching type, or -ENOENT if not found
+ */
+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, lmost = -ENOENT;
+ int ret;
+
+ l = start_id;
+ r = end_id;
+ while (l <= r) {
+ m = l + (r - l) / 2;
+ t = btf_type_by_id(btf, m);
+ tname = btf_name_by_offset(btf, t->name_off);
+ ret = strcmp(tname, name);
+ if (ret < 0) {
+ l = m + 1;
+ } else {
+ if (ret == 0)
+ lmost = m;
+ r = m - 1;
+ }
+ }
+
+ return lmost;
+}
+
+/* Searches for a BTF type with the specified name and kind. The function
+ * first recursively searches in the base BTF (if present), then searches
+ * in the current BTF using either binary search (if types are sorted)
+ * or linear search.
+ *
+ * Binary search is used when types are name-sorted (nr_sorted_types > 0).
+ * After finding a name match, it scans forward to find the first type
+ * that also matches the specified kind. Linear search is used for unsorted
+ * types, checking each type sequentially.
+ *
+ * Return: Type ID of matching type on success, -ENOENT if not found
+ */
s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
{
+ const struct btf *base_btf = btf_base_btf(btf);;
const struct btf_type *t;
const char *tname;
- u32 i, total;
+ int err = -ENOENT;
- total = btf_nr_types(btf);
- for (i = 1; i < total; i++) {
- t = btf_type_by_id(btf, i);
- if (BTF_INFO_KIND(t->info) != kind)
- continue;
+ if (base_btf) {
+ err = btf_find_by_name_kind(base_btf, name, kind);
+ if (err > 0)
+ goto out;
+ }
- tname = btf_name_by_offset(btf, t->name_off);
- if (!strcmp(tname, name))
- return i;
+ if (btf->nr_sorted_types != BTF_NEED_SORT_CHECK) {
+ /* binary search */
+ bool skip_first;
+ s32 start_id, end_id;;
+ int ret;
+
+ start_id = btf_start_id(btf);
+ end_id = start_id + btf->nr_sorted_types - 1;
+ ret = btf_find_by_name_kind_bsearch(btf, name, start_id, end_id);
+ if (ret < 0)
+ goto out;
+ skip_first = true;
+ do {
+ t = btf_type_by_id(btf, ret);
+ if (BTF_INFO_KIND(t->info) != kind) {
+ if (skip_first) {
+ skip_first = false;
+ continue;
+ }
+ } else if (skip_first) {
+ return ret;
+ }
+ tname = btf_name_by_offset(btf, t->name_off);
+ if (!strcmp(tname, name))
+ return ret;
+ else
+ break;
+ } while (++ret <= end_id);
+ } else {
+ /* linear search */
+ u32 i, total;
+
+ total = btf_nr_types(btf);
+ for (i = btf_start_id(btf); i < total; i++) {
+ t = btf_type_by_id(btf, i);
+ if (BTF_INFO_KIND(t->info) != kind)
+ continue;
+
+ tname = btf_name_by_offset(btf, t->name_off);
+ if (!strcmp(tname, name))
+ return i;
+ }
}
- return -ENOENT;
+out:
+ return err;
}
s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p)
@@ -5791,6 +5885,7 @@ static struct btf *btf_parse(const union bpf_attr *attr, bpfptr_t uattr, u32 uat
goto errout;
}
env->btf = btf;
+ btf->nr_sorted_types = BTF_NEED_SORT_CHECK;
data = kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN);
if (!data) {
@@ -6210,6 +6305,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
btf->data = data;
btf->data_size = data_size;
btf->kernel_btf = true;
+ btf->nr_sorted_types = BTF_NEED_SORT_CHECK;
snprintf(btf->name, sizeof(btf->name), "%s", name);
err = btf_parse_hdr(env);
@@ -6327,6 +6423,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
btf->start_id = base_btf->nr_types;
btf->start_str_off = base_btf->hdr.str_len;
btf->kernel_btf = true;
+ btf->nr_sorted_types = BTF_NEED_SORT_CHECK;
snprintf(btf->name, sizeof(btf->name), "%s", module_name);
btf->data = kvmemdup(data, data_size, GFP_KERNEL | __GFP_NOWARN);
--
2.34.1
Powered by blists - more mailing lists