| 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: <20251117132623.3807094-5-dolinux.peng@gmail.com>
Date: Mon, 17 Nov 2025 21:26:20 +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 <pengdonglin@...omi.com>,
Alan Maguire <alan.maguire@...cle.com>,
Song Liu <song@...nel.org>
Subject: [RFC PATCH v6 4/7] libbpf: Optimize type lookup with binary search for sorted BTF
From: Donglin Peng <pengdonglin@...omi.com>
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 <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>
---
tools/lib/bpf/btf.c | 104 ++++++++++++++++++++++++++++++++++----------
1 file changed, 81 insertions(+), 23 deletions(-)
diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index e3aa31c735c8..bb77e6c762cc 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,93 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
return type_id;
}
-__s32 btf__find_by_name(const struct btf *btf, const char *type_name)
+static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
+ __s32 start_id, __s32 end_id)
{
- __u32 i, nr_types = btf__type_cnt(btf);
+ const struct btf_type *t;
+ const char *tname;
+ __s32 l, r, m;
+
+ l = start_id;
+ r = end_id;
+ while (l <= r) {
+ m = l + (r - l) / 2;
+ t = btf_type_by_id(btf, m);
+ tname = btf__str_by_offset(btf, t->name_off);
+ if (strcmp(tname, name) >= 0) {
+ if (l == r)
+ return r;
+ r = m;
+ } else {
+ l = m + 1;
+ }
+ }
- if (!strcmp(type_name, "void"))
- return 0;
+ return btf__type_cnt(btf);
+}
- for (i = 1; i < nr_types; i++) {
- const struct btf_type *t = btf__type_by_id(btf, i);
- const char *name = btf__name_by_offset(btf, t->name_off);
+static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_id,
+ const char *type_name, __u32 kind)
+{
+ const struct btf_type *t;
+ const char *tname;
+ int err = -ENOENT;
+
+ if (start_id < btf->start_id) {
+ err = btf_find_type_by_name_kind(btf->base_btf, start_id,
+ type_name, kind);
+ if (err > 0)
+ goto out;
+ start_id = btf->start_id;
+ }
+
+ if (btf->nr_sorted_types > 0) {
+ /* binary search */
+ __s32 end_id;
+ int idx;
+
+ end_id = btf->start_id + btf->nr_sorted_types - 1;
+ idx = btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id);
+ for (; idx <= end_id; idx++) {
+ t = btf__type_by_id(btf, idx);
+ tname = btf__str_by_offset(btf, t->name_off);
+ if (strcmp(tname, type_name))
+ goto out;
+ if (kind == -1 || btf_kind(t) == kind)
+ return idx;
+ }
+ } else {
+ /* linear search */
+ __u32 i, total;
- if (name && !strcmp(type_name, name))
- return i;
+ total = btf__type_cnt(btf);
+ for (i = start_id; i < total; i++) {
+ t = btf_type_by_id(btf, i);
+ if (kind != -1 && btf_kind(t) != kind)
+ continue;
+ tname = btf__str_by_offset(btf, t->name_off);
+ if (tname && !strcmp(tname, type_name))
+ return i;
+ }
}
- return libbpf_err(-ENOENT);
+out:
+ return err;
}
static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
const char *type_name, __u32 kind)
{
- __u32 i, nr_types = btf__type_cnt(btf);
-
if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
return 0;
- for (i = start_id; i < nr_types; i++) {
- const struct btf_type *t = btf__type_by_id(btf, i);
- const char *name;
-
- if (btf_kind(t) != kind)
- continue;
- name = 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, kind));
+}
- 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);
}
__s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
@@ -1006,6 +1061,7 @@ static struct btf *btf_new_empty(struct btf *base_btf)
btf->fd = -1;
btf->ptr_sz = sizeof(void *);
btf->swapped_endian = false;
+ btf->nr_sorted_types = 0;
if (base_btf) {
btf->base_btf = base_btf;
@@ -1057,6 +1113,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
btf->start_id = 1;
btf->start_str_off = 0;
btf->fd = -1;
+ btf->nr_sorted_types = 0;
if (base_btf) {
btf->base_btf = base_btf;
@@ -1715,6 +1772,7 @@ static void btf_invalidate_raw_data(struct btf *btf)
free(btf->raw_data_swapped);
btf->raw_data_swapped = NULL;
}
+ btf->nr_sorted_types = 0;
}
/* Ensure BTF is ready to be modified (by splitting into a three memory
--
2.34.1
Powered by blists - more mailing lists