libbpf: BTF performance optimizations with permutation and binary search

[RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Donglin Peng 1 month, 2 weeks ago

From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
Cc: Alexei Starovoitov <ast@kernel.org>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc: Alan Maguire <alan.maguire@oracle.com>
Cc: Song Liu <song@kernel.org>
Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
---
 tools/lib/bpf/btf.c | 142 +++++++++++++++++++++++++++++++++++++-------
 1 file changed, 119 insertions(+), 23 deletions(-)

diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index 3bc03f7fe31f..5af14304409c 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,134 @@ 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)
+/*
+ * Find BTF types with matching names within the [left, right] index range.
+ * On success, updates *left and *right to the boundaries of the matching range
+ * and returns the leftmost matching index.
+ */
+static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
+						__s32 *left, __s32 *right)
 {
-	__u32 i, nr_types = btf__type_cnt(btf);
+	const struct btf_type *t;
+	const char *tname;
+	__s32 l, r, m, lmost, rmost;
+	int ret;
+
+	/* found the leftmost btf_type that matches */
+	l = *left;
+	r = *right;
+	lmost = -1;
+	while (l <= r) {
+		m = l + (r - l) / 2;
+		t = btf_type_by_id(btf, m);
+		tname = btf__str_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;
+		}
+	}
 
-	if (!strcmp(type_name, "void"))
-		return 0;
+	if (lmost == -1)
+		return -ENOENT;
+
+	/* found the rightmost btf_type that matches */
+	l = lmost;
+	r = *right;
+	rmost = -1;
+	while (l <= r) {
+		m = l + (r - l) / 2;
+		t = btf_type_by_id(btf, m);
+		tname = btf__str_by_offset(btf, t->name_off);
+		ret = strcmp(tname, name);
+		if (ret <= 0) {
+			if (ret == 0)
+				rmost = m;
+			l = m + 1;
+		} else {
+			r = m - 1;
+		}
+	}
 
-	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);
+	*left = lmost;
+	*right = rmost;
+	return lmost;
+}
+
+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 (name && !strcmp(type_name, name))
-			return i;
+	if (!btf)
+		goto out;
+
+	if (start_id < btf->start_id) {
+		err = btf_find_type_by_name_kind(btf->base_btf, start_id,
+						 type_name, kind);
+		if (err == -ENOENT)
+			start_id = btf->start_id;
+	}
+
+	if (err == -ENOENT) {
+		if (btf->nr_sorted_types) {
+			/* binary search */
+			__s32 l, r;
+			int ret;
+
+			l = start_id;
+			r = start_id + btf->nr_sorted_types - 1;
+			ret = btf_find_type_by_name_bsearch(btf, type_name, &l, &r);
+			if (ret < 0)
+				goto out;
+			/* return the leftmost with maching names and skip kind checking */
+			if (kind == -1)
+				return ret;
+			/* found the leftmost btf_type that matches */
+			while (l <= r) {
+				t = btf_type_by_id(btf, l);
+				if (BTF_INFO_KIND(t->info) == kind)
+					return l;
+				l++;
+			}
+		} else {
+			/* linear search */
+			__u32 i, total;
+
+			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,
-- 
2.34.1

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Andrii Nakryiko 1 month, 2 weeks ago

On Tue, Nov 4, 2025 at 5:40 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
> Cc: Alexei Starovoitov <ast@kernel.org>
> Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Cc: Alan Maguire <alan.maguire@oracle.com>
> Cc: Song Liu <song@kernel.org>
> Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> ---
>  tools/lib/bpf/btf.c | 142 +++++++++++++++++++++++++++++++++++++-------
>  1 file changed, 119 insertions(+), 23 deletions(-)
>
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 3bc03f7fe31f..5af14304409c 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;

we don't need to know the count of sorted types, all we need is a
tristate value: a) data is sorted, b) data is not sorted, c) we don't
know yet. And zero should be treated as "we don't know yet". This is
trivial to do with an enum.

>         /* if not NULL, points to the base BTF on top of which the current
>          * split BTF is based
>          */
> @@ -897,44 +903,134 @@ 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)
> +/*
> + * Find BTF types with matching names within the [left, right] index range.
> + * On success, updates *left and *right to the boundaries of the matching range
> + * and returns the leftmost matching index.
> + */
> +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> +                                               __s32 *left, __s32 *right)

I thought we discussed this, why do you need "right"? Two binary
searches where one would do just fine.


Also this isn't quite the same approach as in find_linfo() in
kernel/bpf/log.c, that one doesn't have extra ret == 0 condition

pw-bot: cr

>  {
> -       __u32 i, nr_types = btf__type_cnt(btf);
> +       const struct btf_type *t;
> +       const char *tname;
> +       __s32 l, r, m, lmost, rmost;
> +       int ret;
> +

[...]

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Eduard Zingerman 1 month, 2 weeks ago

On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:

[...]

> > @@ -897,44 +903,134 @@ 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)
> > +/*
> > + * Find BTF types with matching names within the [left, right] index range.
> > + * On success, updates *left and *right to the boundaries of the matching range
> > + * and returns the leftmost matching index.
> > + */
> > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > +                                               __s32 *left, __s32 *right)
> 
> I thought we discussed this, why do you need "right"? Two binary
> searches where one would do just fine.

I think the idea is that there would be less strcmp's if there is a
long sequence of items with identical names.

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Andrii Nakryiko 1 month, 2 weeks ago

On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
>
> [...]
>
> > > @@ -897,44 +903,134 @@ 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)
> > > +/*
> > > + * Find BTF types with matching names within the [left, right] index range.
> > > + * On success, updates *left and *right to the boundaries of the matching range
> > > + * and returns the leftmost matching index.
> > > + */
> > > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > > +                                               __s32 *left, __s32 *right)
> >
> > I thought we discussed this, why do you need "right"? Two binary
> > searches where one would do just fine.
>
> I think the idea is that there would be less strcmp's if there is a
> long sequence of items with identical names.

Sure, it's a tradeoff. But how long is the set of duplicate name
entries we expect in kernel BTF? Additional O(logN) over 70K+ types
with high likelihood will take more comparisons.

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Eduard Zingerman 1 month, 2 weeks ago

On Tue, 2025-11-04 at 16:54 -0800, Andrii Nakryiko wrote:
> On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
> >
> > [...]
> >
> > > > @@ -897,44 +903,134 @@ 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)
> > > > +/*
> > > > + * Find BTF types with matching names within the [left, right] index range.
> > > > + * On success, updates *left and *right to the boundaries of the matching range
> > > > + * and returns the leftmost matching index.
> > > > + */
> > > > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > > > +                                               __s32 *left, __s32 *right)
> > >
> > > I thought we discussed this, why do you need "right"? Two binary
> > > searches where one would do just fine.
> >
> > I think the idea is that there would be less strcmp's if there is a
> > long sequence of items with identical names.
>
> Sure, it's a tradeoff. But how long is the set of duplicate name
> entries we expect in kernel BTF? Additional O(logN) over 70K+ types
> with high likelihood will take more comparisons.

$ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head
  51737 '(anon)'
    277 'bpf_kfunc'
      4 'long
      3 'perf_aux_event'
      3 'workspace'
      2 'ata_acpi_gtm'
      2 'avc_cache_stats'
      2 'bh_accounting'
      2 'bp_cpuinfo'
      2 'bpf_fastcall'

'bpf_kfunc' is probably for decl_tags.
So I agree with you regarding the second binary search, it is not
necessary.  But skipping all anonymous types (and thus having to
maintain nr_sorted_types) might be useful, on each search two
iterations would be wasted to skip those.

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Donglin Peng 1 month, 1 week ago

On Wed, Nov 5, 2025 at 9:17 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2025-11-04 at 16:54 -0800, Andrii Nakryiko wrote:
> > On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
> > >
> > > [...]
> > >
> > > > > @@ -897,44 +903,134 @@ 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)
> > > > > +/*
> > > > > + * Find BTF types with matching names within the [left, right] index range.
> > > > > + * On success, updates *left and *right to the boundaries of the matching range
> > > > > + * and returns the leftmost matching index.
> > > > > + */
> > > > > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > > > > +                                               __s32 *left, __s32 *right)
> > > >
> > > > I thought we discussed this, why do you need "right"? Two binary
> > > > searches where one would do just fine.
> > >
> > > I think the idea is that there would be less strcmp's if there is a
> > > long sequence of items with identical names.
> >
> > Sure, it's a tradeoff. But how long is the set of duplicate name
> > entries we expect in kernel BTF? Additional O(logN) over 70K+ types
> > with high likelihood will take more comparisons.
>
> $ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head
>   51737 '(anon)'
>     277 'bpf_kfunc'
>       4 'long
>       3 'perf_aux_event'
>       3 'workspace'
>       2 'ata_acpi_gtm'
>       2 'avc_cache_stats'
>       2 'bh_accounting'
>       2 'bp_cpuinfo'
>       2 'bpf_fastcall'
>
> 'bpf_kfunc' is probably for decl_tags.
> So I agree with you regarding the second binary search, it is not
> necessary.  But skipping all anonymous types (and thus having to
> maintain nr_sorted_types) might be useful, on each search two
> iterations would be wasted to skip those.

Thank you. After removing the redundant iterations, performance increased
significantly compared with two iterations.

Test Case: Locate all 58,719 named types in vmlinux BTF
Methodology:
./vmtest.sh -- ./test_progs -t btf_permute/perf -v

Two iterations:
| Condition          | Lookup Time | Improvement |
|--------------------|-------------|-------------|
| Unsorted (Linear)  | 17,282 ms   | Baseline    |
| Sorted (Binary)    | 19 ms       | 909x faster |

One iteration:
Results:
| Condition          | Lookup Time | Improvement |
|--------------------|-------------|-------------|
| Unsorted (Linear)  | 17,619 ms   | Baseline    |
| Sorted (Binary)    | 10 ms       | 1762x faster |

Here is the code implementation with a single iteration approach.
I believe this scenario differs from find_linfo because we cannot
determine in advance whether the specified type name will be found.
Please correct me if I've misunderstood anything, and I welcome any
guidance on this matter.

static __s32 btf_find_type_by_name_bsearch(const struct btf *btf,
const char *name,
                                                __s32 start_id)
{
        const struct btf_type *t;
        const char *tname;
        __s32 l, r, m, lmost = -ENOENT;
        int ret;

        /* found the leftmost btf_type that matches */
        l = start_id;
        r = btf__type_cnt(btf) - 1;
        while (l <= r) {
                m = l + (r - l) / 2;
                t = btf_type_by_id(btf, m);
                if (!t->name_off) {
                        ret = 1;
                } else {
                        tname = btf__str_by_offset(btf, t->name_off);
                        ret = !tname ? 1 : strcmp(tname, name);
                }
                if (ret < 0) {
                        l = m + 1;
                } else {
                        if (ret == 0)
                                lmost = m;
                        r = m - 1;
                }
        }

        return lmost;
}

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;
        __u32 total;

        if (!btf)
                goto out;

        if (start_id < btf->start_id) {
                err = btf_find_type_by_name_kind(btf->base_btf, start_id,
                                                 type_name, kind);
                if (err == -ENOENT)
                        start_id = btf->start_id;
        }

        if (err == -ENOENT) {
                if (btf_check_sorted((struct btf *)btf)) {
                        /* binary search */
                        bool skip_first;
                        int ret;

                        /* return the leftmost with maching names */
                        ret = btf_find_type_by_name_bsearch(btf,
type_name, start_id);
                        if (ret < 0)
                                goto out;
                        /* skip kind checking */
                        if (kind == -1)
                                return ret;
                        total = btf__type_cnt(btf);
                        skip_first = true;
                        do {
                                t = btf_type_by_id(btf, ret);
                                if (btf_kind(t) != kind) {
                                        if (skip_first) {
                                                skip_first = false;
                                                continue;
                                        }
                                } else if (skip_first) {
                                        return ret;
                                }
                                if (!t->name_off)
                                        break;
                                tname = btf__str_by_offset(btf, t->name_off);
                                if (tname && !strcmp(tname, type_name))
                                        return ret;
                                else
                                        break;
                        } while (++ret < total);
                } else {
                        /* linear search */
...
                }
        }

out:
        return err;
}

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Andrii Nakryiko 1 month, 1 week ago

On Wed, Nov 5, 2025 at 5:48 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> On Wed, Nov 5, 2025 at 9:17 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Tue, 2025-11-04 at 16:54 -0800, Andrii Nakryiko wrote:
> > > On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > >
> > > > On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
> > > >
> > > > [...]
> > > >
> > > > > > @@ -897,44 +903,134 @@ 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)
> > > > > > +/*
> > > > > > + * Find BTF types with matching names within the [left, right] index range.
> > > > > > + * On success, updates *left and *right to the boundaries of the matching range
> > > > > > + * and returns the leftmost matching index.
> > > > > > + */
> > > > > > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > > > > > +                                               __s32 *left, __s32 *right)
> > > > >
> > > > > I thought we discussed this, why do you need "right"? Two binary
> > > > > searches where one would do just fine.
> > > >
> > > > I think the idea is that there would be less strcmp's if there is a
> > > > long sequence of items with identical names.
> > >
> > > Sure, it's a tradeoff. But how long is the set of duplicate name
> > > entries we expect in kernel BTF? Additional O(logN) over 70K+ types
> > > with high likelihood will take more comparisons.
> >
> > $ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head
> >   51737 '(anon)'
> >     277 'bpf_kfunc'
> >       4 'long
> >       3 'perf_aux_event'
> >       3 'workspace'
> >       2 'ata_acpi_gtm'
> >       2 'avc_cache_stats'
> >       2 'bh_accounting'
> >       2 'bp_cpuinfo'
> >       2 'bpf_fastcall'
> >
> > 'bpf_kfunc' is probably for decl_tags.
> > So I agree with you regarding the second binary search, it is not
> > necessary.  But skipping all anonymous types (and thus having to
> > maintain nr_sorted_types) might be useful, on each search two
> > iterations would be wasted to skip those.

fair enough, eliminating a big chunk of anonymous types is useful, let's do this

>
> Thank you. After removing the redundant iterations, performance increased
> significantly compared with two iterations.
>
> Test Case: Locate all 58,719 named types in vmlinux BTF
> Methodology:
> ./vmtest.sh -- ./test_progs -t btf_permute/perf -v
>
> Two iterations:
> | Condition          | Lookup Time | Improvement |
> |--------------------|-------------|-------------|
> | Unsorted (Linear)  | 17,282 ms   | Baseline    |
> | Sorted (Binary)    | 19 ms       | 909x faster |
>
> One iteration:
> Results:
> | Condition          | Lookup Time | Improvement |
> |--------------------|-------------|-------------|
> | Unsorted (Linear)  | 17,619 ms   | Baseline    |
> | Sorted (Binary)    | 10 ms       | 1762x faster |
>
> Here is the code implementation with a single iteration approach.
> I believe this scenario differs from find_linfo because we cannot
> determine in advance whether the specified type name will be found.
> Please correct me if I've misunderstood anything, and I welcome any
> guidance on this matter.
>
> static __s32 btf_find_type_by_name_bsearch(const struct btf *btf,
> const char *name,
>                                                 __s32 start_id)
> {
>         const struct btf_type *t;
>         const char *tname;
>         __s32 l, r, m, lmost = -ENOENT;
>         int ret;
>
>         /* found the leftmost btf_type that matches */
>         l = start_id;
>         r = btf__type_cnt(btf) - 1;
>         while (l <= r) {
>                 m = l + (r - l) / 2;
>                 t = btf_type_by_id(btf, m);
>                 if (!t->name_off) {
>                         ret = 1;
>                 } else {
>                         tname = btf__str_by_offset(btf, t->name_off);
>                         ret = !tname ? 1 : strcmp(tname, name);
>                 }
>                 if (ret < 0) {
>                         l = m + 1;
>                 } else {
>                         if (ret == 0)
>                                 lmost = m;
>                         r = m - 1;
>                 }
>         }
>
>         return lmost;
> }

There are different ways to implement this. At the highest level,
implementation below just searches for leftmost element that has name
>= the one we are searching for. One complication is that such element
might not event exists. We can solve that checking ahead of time
whether the rightmost type satisfied the condition, or we could do
something similar to what I do in the loop below, where I allow l == r
and then if that element has name >= to what we search, we exit
because we found it. And if not, l will become larger than r, we'll
break out of the loop and we'll know that we couldn't find the
element. I haven't tested it, but please take a look and if you decide
to go with such approach, do test it for edge cases, of course.

/*
 * We are searching for the smallest r such that type #r's name is >= name.
 * It might not exist, in which case we'll have l == r + 1.
 */
l = start_id;
r = btf__type_cnt(btf) - 1;
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; /* found it! */
        r = m;
    } else {
        l = m + 1;
    }
}
/* here we know given element doesn't exist, return index beyond end of types */
return btf__type_cnt(btf);


We could have checked instead whether strcmp(btf__str_by_offset(btf,
btf__type_by_id(btf, btf__type_cnt() - 1)->name_off), name) < 0 and
exit early. That's just a bit more code duplication of essentially
what we do inside the loop, so that if (l == r) seems fine to me, but
I'm not married to this.

>
> 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;
>         __u32 total;
>
>         if (!btf)
>                 goto out;
>
>         if (start_id < btf->start_id) {
>                 err = btf_find_type_by_name_kind(btf->base_btf, start_id,
>                                                  type_name, kind);
>                 if (err == -ENOENT)
>                         start_id = btf->start_id;
>         }
>
>         if (err == -ENOENT) {
>                 if (btf_check_sorted((struct btf *)btf)) {
>                         /* binary search */
>                         bool skip_first;
>                         int ret;
>
>                         /* return the leftmost with maching names */
>                         ret = btf_find_type_by_name_bsearch(btf,
> type_name, start_id);
>                         if (ret < 0)
>                                 goto out;
>                         /* skip kind checking */
>                         if (kind == -1)
>                                 return ret;
>                         total = btf__type_cnt(btf);
>                         skip_first = true;
>                         do {
>                                 t = btf_type_by_id(btf, ret);
>                                 if (btf_kind(t) != kind) {
>                                         if (skip_first) {
>                                                 skip_first = false;
>                                                 continue;
>                                         }
>                                 } else if (skip_first) {
>                                         return ret;
>                                 }
>                                 if (!t->name_off)
>                                         break;
>                                 tname = btf__str_by_offset(btf, t->name_off);
>                                 if (tname && !strcmp(tname, type_name))
>                                         return ret;
>                                 else
>                                         break;
>                         } while (++ret < total);
>                 } else {
>                         /* linear search */
> ...
>                 }
>         }
>
> out:
>         return err;
> }

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Donglin Peng 1 month, 1 week ago

On Thu, Nov 6, 2025 at 2:11 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Wed, Nov 5, 2025 at 5:48 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > On Wed, Nov 5, 2025 at 9:17 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > On Tue, 2025-11-04 at 16:54 -0800, Andrii Nakryiko wrote:
> > > > On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > >
> > > > > On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
> > > > >
> > > > > [...]
> > > > >
> > > > > > > @@ -897,44 +903,134 @@ 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)
> > > > > > > +/*
> > > > > > > + * Find BTF types with matching names within the [left, right] index range.
> > > > > > > + * On success, updates *left and *right to the boundaries of the matching range
> > > > > > > + * and returns the leftmost matching index.
> > > > > > > + */
> > > > > > > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > > > > > > +                                               __s32 *left, __s32 *right)
> > > > > >
> > > > > > I thought we discussed this, why do you need "right"? Two binary
> > > > > > searches where one would do just fine.
> > > > >
> > > > > I think the idea is that there would be less strcmp's if there is a
> > > > > long sequence of items with identical names.
> > > >
> > > > Sure, it's a tradeoff. But how long is the set of duplicate name
> > > > entries we expect in kernel BTF? Additional O(logN) over 70K+ types
> > > > with high likelihood will take more comparisons.
> > >
> > > $ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head
> > >   51737 '(anon)'
> > >     277 'bpf_kfunc'
> > >       4 'long
> > >       3 'perf_aux_event'
> > >       3 'workspace'
> > >       2 'ata_acpi_gtm'
> > >       2 'avc_cache_stats'
> > >       2 'bh_accounting'
> > >       2 'bp_cpuinfo'
> > >       2 'bpf_fastcall'
> > >
> > > 'bpf_kfunc' is probably for decl_tags.
> > > So I agree with you regarding the second binary search, it is not
> > > necessary.  But skipping all anonymous types (and thus having to
> > > maintain nr_sorted_types) might be useful, on each search two
> > > iterations would be wasted to skip those.
>
> fair enough, eliminating a big chunk of anonymous types is useful, let's do this
>
> >
> > Thank you. After removing the redundant iterations, performance increased
> > significantly compared with two iterations.
> >
> > Test Case: Locate all 58,719 named types in vmlinux BTF
> > Methodology:
> > ./vmtest.sh -- ./test_progs -t btf_permute/perf -v
> >
> > Two iterations:
> > | Condition          | Lookup Time | Improvement |
> > |--------------------|-------------|-------------|
> > | Unsorted (Linear)  | 17,282 ms   | Baseline    |
> > | Sorted (Binary)    | 19 ms       | 909x faster |
> >
> > One iteration:
> > Results:
> > | Condition          | Lookup Time | Improvement |
> > |--------------------|-------------|-------------|
> > | Unsorted (Linear)  | 17,619 ms   | Baseline    |
> > | Sorted (Binary)    | 10 ms       | 1762x faster |
> >
> > Here is the code implementation with a single iteration approach.
> > I believe this scenario differs from find_linfo because we cannot
> > determine in advance whether the specified type name will be found.
> > Please correct me if I've misunderstood anything, and I welcome any
> > guidance on this matter.
> >
> > static __s32 btf_find_type_by_name_bsearch(const struct btf *btf,
> > const char *name,
> >                                                 __s32 start_id)
> > {
> >         const struct btf_type *t;
> >         const char *tname;
> >         __s32 l, r, m, lmost = -ENOENT;
> >         int ret;
> >
> >         /* found the leftmost btf_type that matches */
> >         l = start_id;
> >         r = btf__type_cnt(btf) - 1;
> >         while (l <= r) {
> >                 m = l + (r - l) / 2;
> >                 t = btf_type_by_id(btf, m);
> >                 if (!t->name_off) {
> >                         ret = 1;
> >                 } else {
> >                         tname = btf__str_by_offset(btf, t->name_off);
> >                         ret = !tname ? 1 : strcmp(tname, name);
> >                 }
> >                 if (ret < 0) {
> >                         l = m + 1;
> >                 } else {
> >                         if (ret == 0)
> >                                 lmost = m;
> >                         r = m - 1;
> >                 }
> >         }
> >
> >         return lmost;
> > }
>
> There are different ways to implement this. At the highest level,
> implementation below just searches for leftmost element that has name
> >= the one we are searching for. One complication is that such element
> might not event exists. We can solve that checking ahead of time
> whether the rightmost type satisfied the condition, or we could do
> something similar to what I do in the loop below, where I allow l == r
> and then if that element has name >= to what we search, we exit
> because we found it. And if not, l will become larger than r, we'll
> break out of the loop and we'll know that we couldn't find the
> element. I haven't tested it, but please take a look and if you decide
> to go with such approach, do test it for edge cases, of course.
>
> /*
>  * We are searching for the smallest r such that type #r's name is >= name.
>  * It might not exist, in which case we'll have l == r + 1.
>  */
> l = start_id;
> r = btf__type_cnt(btf) - 1;
> 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; /* found it! */

It seems that this if condition will never hold, because a while(l < r) loop
is used. Moreover, even if the condition were to hold, it wouldn't guarantee
a successful search.

>         r = m;
>     } else {
>         l = m + 1;
>     }
> }
> /* here we know given element doesn't exist, return index beyond end of types */
> return btf__type_cnt(btf);

I think that return -ENOENT seems more reasonable.

>
>
> We could have checked instead whether strcmp(btf__str_by_offset(btf,
> btf__type_by_id(btf, btf__type_cnt() - 1)->name_off), name) < 0 and
> exit early. That's just a bit more code duplication of essentially
> what we do inside the loop, so that if (l == r) seems fine to me, but
> I'm not married to this.

Sorry, I believe that even if strcmp(btf__str_by_offset(btf,
btf__type_by_id(btf,
btf__type_cnt() - 1)->name_off), name) >= 0, it still doesn't seem to
guarantee that the search will definitely succeed.

>
> >
> > 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;
> >         __u32 total;
> >
> >         if (!btf)
> >                 goto out;
> >
> >         if (start_id < btf->start_id) {
> >                 err = btf_find_type_by_name_kind(btf->base_btf, start_id,
> >                                                  type_name, kind);
> >                 if (err == -ENOENT)
> >                         start_id = btf->start_id;
> >         }
> >
> >         if (err == -ENOENT) {
> >                 if (btf_check_sorted((struct btf *)btf)) {
> >                         /* binary search */
> >                         bool skip_first;
> >                         int ret;
> >
> >                         /* return the leftmost with maching names */
> >                         ret = btf_find_type_by_name_bsearch(btf,
> > type_name, start_id);
> >                         if (ret < 0)
> >                                 goto out;
> >                         /* skip kind checking */
> >                         if (kind == -1)
> >                                 return ret;
> >                         total = btf__type_cnt(btf);
> >                         skip_first = true;
> >                         do {
> >                                 t = btf_type_by_id(btf, ret);
> >                                 if (btf_kind(t) != kind) {
> >                                         if (skip_first) {
> >                                                 skip_first = false;
> >                                                 continue;
> >                                         }
> >                                 } else if (skip_first) {
> >                                         return ret;
> >                                 }
> >                                 if (!t->name_off)
> >                                         break;
> >                                 tname = btf__str_by_offset(btf, t->name_off);
> >                                 if (tname && !strcmp(tname, type_name))
> >                                         return ret;
> >                                 else
> >                                         break;
> >                         } while (++ret < total);
> >                 } else {
> >                         /* linear search */
> > ...
> >                 }
> >         }
> >
> > out:
> >         return err;
> > }

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Andrii Nakryiko 1 month, 1 week ago

On Wed, Nov 5, 2025 at 11:49 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> On Thu, Nov 6, 2025 at 2:11 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Wed, Nov 5, 2025 at 5:48 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > >
> > > On Wed, Nov 5, 2025 at 9:17 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > >
> > > > On Tue, 2025-11-04 at 16:54 -0800, Andrii Nakryiko wrote:
> > > > > On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > > >
> > > > > > On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
> > > > > >
> > > > > > [...]
> > > > > >
> > > > > > > > @@ -897,44 +903,134 @@ 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)
> > > > > > > > +/*
> > > > > > > > + * Find BTF types with matching names within the [left, right] index range.
> > > > > > > > + * On success, updates *left and *right to the boundaries of the matching range
> > > > > > > > + * and returns the leftmost matching index.
> > > > > > > > + */
> > > > > > > > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > > > > > > > +                                               __s32 *left, __s32 *right)
> > > > > > >
> > > > > > > I thought we discussed this, why do you need "right"? Two binary
> > > > > > > searches where one would do just fine.
> > > > > >
> > > > > > I think the idea is that there would be less strcmp's if there is a
> > > > > > long sequence of items with identical names.
> > > > >
> > > > > Sure, it's a tradeoff. But how long is the set of duplicate name
> > > > > entries we expect in kernel BTF? Additional O(logN) over 70K+ types
> > > > > with high likelihood will take more comparisons.
> > > >
> > > > $ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head
> > > >   51737 '(anon)'
> > > >     277 'bpf_kfunc'
> > > >       4 'long
> > > >       3 'perf_aux_event'
> > > >       3 'workspace'
> > > >       2 'ata_acpi_gtm'
> > > >       2 'avc_cache_stats'
> > > >       2 'bh_accounting'
> > > >       2 'bp_cpuinfo'
> > > >       2 'bpf_fastcall'
> > > >
> > > > 'bpf_kfunc' is probably for decl_tags.
> > > > So I agree with you regarding the second binary search, it is not
> > > > necessary.  But skipping all anonymous types (and thus having to
> > > > maintain nr_sorted_types) might be useful, on each search two
> > > > iterations would be wasted to skip those.
> >
> > fair enough, eliminating a big chunk of anonymous types is useful, let's do this
> >
> > >
> > > Thank you. After removing the redundant iterations, performance increased
> > > significantly compared with two iterations.
> > >
> > > Test Case: Locate all 58,719 named types in vmlinux BTF
> > > Methodology:
> > > ./vmtest.sh -- ./test_progs -t btf_permute/perf -v
> > >
> > > Two iterations:
> > > | Condition          | Lookup Time | Improvement |
> > > |--------------------|-------------|-------------|
> > > | Unsorted (Linear)  | 17,282 ms   | Baseline    |
> > > | Sorted (Binary)    | 19 ms       | 909x faster |
> > >
> > > One iteration:
> > > Results:
> > > | Condition          | Lookup Time | Improvement |
> > > |--------------------|-------------|-------------|
> > > | Unsorted (Linear)  | 17,619 ms   | Baseline    |
> > > | Sorted (Binary)    | 10 ms       | 1762x faster |
> > >
> > > Here is the code implementation with a single iteration approach.
> > > I believe this scenario differs from find_linfo because we cannot
> > > determine in advance whether the specified type name will be found.
> > > Please correct me if I've misunderstood anything, and I welcome any
> > > guidance on this matter.
> > >
> > > static __s32 btf_find_type_by_name_bsearch(const struct btf *btf,
> > > const char *name,
> > >                                                 __s32 start_id)
> > > {
> > >         const struct btf_type *t;
> > >         const char *tname;
> > >         __s32 l, r, m, lmost = -ENOENT;
> > >         int ret;
> > >
> > >         /* found the leftmost btf_type that matches */
> > >         l = start_id;
> > >         r = btf__type_cnt(btf) - 1;
> > >         while (l <= r) {
> > >                 m = l + (r - l) / 2;
> > >                 t = btf_type_by_id(btf, m);
> > >                 if (!t->name_off) {
> > >                         ret = 1;
> > >                 } else {
> > >                         tname = btf__str_by_offset(btf, t->name_off);
> > >                         ret = !tname ? 1 : strcmp(tname, name);
> > >                 }
> > >                 if (ret < 0) {
> > >                         l = m + 1;
> > >                 } else {
> > >                         if (ret == 0)
> > >                                 lmost = m;
> > >                         r = m - 1;
> > >                 }
> > >         }
> > >
> > >         return lmost;
> > > }
> >
> > There are different ways to implement this. At the highest level,
> > implementation below just searches for leftmost element that has name
> > >= the one we are searching for. One complication is that such element
> > might not event exists. We can solve that checking ahead of time
> > whether the rightmost type satisfied the condition, or we could do
> > something similar to what I do in the loop below, where I allow l == r
> > and then if that element has name >= to what we search, we exit
> > because we found it. And if not, l will become larger than r, we'll
> > break out of the loop and we'll know that we couldn't find the
> > element. I haven't tested it, but please take a look and if you decide
> > to go with such approach, do test it for edge cases, of course.
> >
> > /*
> >  * We are searching for the smallest r such that type #r's name is >= name.
> >  * It might not exist, in which case we'll have l == r + 1.
> >  */
> > l = start_id;
> > r = btf__type_cnt(btf) - 1;
> > 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; /* found it! */
>
> It seems that this if condition will never hold, because a while(l < r) loop

It should be `while (l <= r)`, I forgot to update it, but I mentioned
that I do want to allow l == r condition.

> is used. Moreover, even if the condition were to hold, it wouldn't guarantee
> a successful search.

Elaborate please on "wouldn't guarantee a successful search".

>
> >         r = m;
> >     } else {
> >         l = m + 1;
> >     }
> > }
> > /* here we know given element doesn't exist, return index beyond end of types */
> > return btf__type_cnt(btf);
>
> I think that return -ENOENT seems more reasonable.

Think how you will be using this inside btf_find_type_by_name_kind():


int idx = btf_find_by_name_bsearch(btf, name);

for (int n = btf__type_cnt(btf); idx < n; idx++) {
    struct btf_type *t = btf__type_by_id(btf, idx);
    const char *tname = btf__str_by_offset(btf, t->name_off);
    if (strcmp(tname, name) != 0)
        return -ENOENT;
    if (btf_kind(t) == kind)
        return idx;
}
return -ENOENT;


Having btf_find_by_name_bsearch() return -ENOENT instead of
btf__type_cnt() just will require extra explicit -ENOENT handling. And
given the function now can return "error", we'd need to either handle
other non-ENOENT errors, to at least leave comment that this should
never happen, though interface itself looks like it could.

This is relatively minor and its all internal implementation, so we
can change that later. But I'm explaining my reasons for why I'd
return index of non-existing type after the end, just like you'd do
with pointer-based interfaces that return pointer after the last
element.


>
> >
> >
> > We could have checked instead whether strcmp(btf__str_by_offset(btf,
> > btf__type_by_id(btf, btf__type_cnt() - 1)->name_off), name) < 0 and
> > exit early. That's just a bit more code duplication of essentially
> > what we do inside the loop, so that if (l == r) seems fine to me, but
> > I'm not married to this.
>
> Sorry, I believe that even if strcmp(btf__str_by_offset(btf,
> btf__type_by_id(btf,
> btf__type_cnt() - 1)->name_off), name) >= 0, it still doesn't seem to
> guarantee that the search will definitely succeed.

If the last element has >= name, search will definitely find at least
that element. What do you mean by "succeed"? All I care about here is
that binary search loop doesn't loop forever and it returns correct
index (or detects that no element can be found).

>
> >
> > >
> > > 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;
> > >         __u32 total;
> > >
> > >         if (!btf)
> > >                 goto out;
> > >
> > >         if (start_id < btf->start_id) {
> > >                 err = btf_find_type_by_name_kind(btf->base_btf, start_id,
> > >                                                  type_name, kind);
> > >                 if (err == -ENOENT)
> > >                         start_id = btf->start_id;
> > >         }
> > >
> > >         if (err == -ENOENT) {
> > >                 if (btf_check_sorted((struct btf *)btf)) {
> > >                         /* binary search */
> > >                         bool skip_first;
> > >                         int ret;
> > >
> > >                         /* return the leftmost with maching names */
> > >                         ret = btf_find_type_by_name_bsearch(btf,
> > > type_name, start_id);
> > >                         if (ret < 0)
> > >                                 goto out;
> > >                         /* skip kind checking */
> > >                         if (kind == -1)
> > >                                 return ret;
> > >                         total = btf__type_cnt(btf);
> > >                         skip_first = true;
> > >                         do {
> > >                                 t = btf_type_by_id(btf, ret);
> > >                                 if (btf_kind(t) != kind) {
> > >                                         if (skip_first) {
> > >                                                 skip_first = false;
> > >                                                 continue;
> > >                                         }
> > >                                 } else if (skip_first) {
> > >                                         return ret;
> > >                                 }
> > >                                 if (!t->name_off)
> > >                                         break;
> > >                                 tname = btf__str_by_offset(btf, t->name_off);
> > >                                 if (tname && !strcmp(tname, type_name))
> > >                                         return ret;
> > >                                 else
> > >                                         break;
> > >                         } while (++ret < total);
> > >                 } else {
> > >                         /* linear search */
> > > ...
> > >                 }
> > >         }
> > >
> > > out:
> > >         return err;
> > > }

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Donglin Peng 1 month, 1 week ago

On Fri, Nov 7, 2025 at 1:31 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Wed, Nov 5, 2025 at 11:49 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > On Thu, Nov 6, 2025 at 2:11 AM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Wed, Nov 5, 2025 at 5:48 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > > >
> > > > On Wed, Nov 5, 2025 at 9:17 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > >
> > > > > On Tue, 2025-11-04 at 16:54 -0800, Andrii Nakryiko wrote:
> > > > > > On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > > > >
> > > > > > > On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
> > > > > > >
> > > > > > > [...]
> > > > > > >
> > > > > > > > > @@ -897,44 +903,134 @@ 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)
> > > > > > > > > +/*
> > > > > > > > > + * Find BTF types with matching names within the [left, right] index range.
> > > > > > > > > + * On success, updates *left and *right to the boundaries of the matching range
> > > > > > > > > + * and returns the leftmost matching index.
> > > > > > > > > + */
> > > > > > > > > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > > > > > > > > +                                               __s32 *left, __s32 *right)
> > > > > > > >
> > > > > > > > I thought we discussed this, why do you need "right"? Two binary
> > > > > > > > searches where one would do just fine.
> > > > > > >
> > > > > > > I think the idea is that there would be less strcmp's if there is a
> > > > > > > long sequence of items with identical names.
> > > > > >
> > > > > > Sure, it's a tradeoff. But how long is the set of duplicate name
> > > > > > entries we expect in kernel BTF? Additional O(logN) over 70K+ types
> > > > > > with high likelihood will take more comparisons.
> > > > >
> > > > > $ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head
> > > > >   51737 '(anon)'
> > > > >     277 'bpf_kfunc'
> > > > >       4 'long
> > > > >       3 'perf_aux_event'
> > > > >       3 'workspace'
> > > > >       2 'ata_acpi_gtm'
> > > > >       2 'avc_cache_stats'
> > > > >       2 'bh_accounting'
> > > > >       2 'bp_cpuinfo'
> > > > >       2 'bpf_fastcall'
> > > > >
> > > > > 'bpf_kfunc' is probably for decl_tags.
> > > > > So I agree with you regarding the second binary search, it is not
> > > > > necessary.  But skipping all anonymous types (and thus having to
> > > > > maintain nr_sorted_types) might be useful, on each search two
> > > > > iterations would be wasted to skip those.
> > >
> > > fair enough, eliminating a big chunk of anonymous types is useful, let's do this
> > >
> > > >
> > > > Thank you. After removing the redundant iterations, performance increased
> > > > significantly compared with two iterations.
> > > >
> > > > Test Case: Locate all 58,719 named types in vmlinux BTF
> > > > Methodology:
> > > > ./vmtest.sh -- ./test_progs -t btf_permute/perf -v
> > > >
> > > > Two iterations:
> > > > | Condition          | Lookup Time | Improvement |
> > > > |--------------------|-------------|-------------|
> > > > | Unsorted (Linear)  | 17,282 ms   | Baseline    |
> > > > | Sorted (Binary)    | 19 ms       | 909x faster |
> > > >
> > > > One iteration:
> > > > Results:
> > > > | Condition          | Lookup Time | Improvement |
> > > > |--------------------|-------------|-------------|
> > > > | Unsorted (Linear)  | 17,619 ms   | Baseline    |
> > > > | Sorted (Binary)    | 10 ms       | 1762x faster |
> > > >
> > > > Here is the code implementation with a single iteration approach.
> > > > I believe this scenario differs from find_linfo because we cannot
> > > > determine in advance whether the specified type name will be found.
> > > > Please correct me if I've misunderstood anything, and I welcome any
> > > > guidance on this matter.
> > > >
> > > > static __s32 btf_find_type_by_name_bsearch(const struct btf *btf,
> > > > const char *name,
> > > >                                                 __s32 start_id)
> > > > {
> > > >         const struct btf_type *t;
> > > >         const char *tname;
> > > >         __s32 l, r, m, lmost = -ENOENT;
> > > >         int ret;
> > > >
> > > >         /* found the leftmost btf_type that matches */
> > > >         l = start_id;
> > > >         r = btf__type_cnt(btf) - 1;
> > > >         while (l <= r) {
> > > >                 m = l + (r - l) / 2;
> > > >                 t = btf_type_by_id(btf, m);
> > > >                 if (!t->name_off) {
> > > >                         ret = 1;
> > > >                 } else {
> > > >                         tname = btf__str_by_offset(btf, t->name_off);
> > > >                         ret = !tname ? 1 : strcmp(tname, name);
> > > >                 }
> > > >                 if (ret < 0) {
> > > >                         l = m + 1;
> > > >                 } else {
> > > >                         if (ret == 0)
> > > >                                 lmost = m;
> > > >                         r = m - 1;
> > > >                 }
> > > >         }
> > > >
> > > >         return lmost;
> > > > }
> > >
> > > There are different ways to implement this. At the highest level,
> > > implementation below just searches for leftmost element that has name
> > > >= the one we are searching for. One complication is that such element
> > > might not event exists. We can solve that checking ahead of time
> > > whether the rightmost type satisfied the condition, or we could do
> > > something similar to what I do in the loop below, where I allow l == r
> > > and then if that element has name >= to what we search, we exit
> > > because we found it. And if not, l will become larger than r, we'll
> > > break out of the loop and we'll know that we couldn't find the
> > > element. I haven't tested it, but please take a look and if you decide
> > > to go with such approach, do test it for edge cases, of course.
> > >
> > > /*
> > >  * We are searching for the smallest r such that type #r's name is >= name.
> > >  * It might not exist, in which case we'll have l == r + 1.
> > >  */
> > > l = start_id;
> > > r = btf__type_cnt(btf) - 1;
> > > 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; /* found it! */
> >
> > It seems that this if condition will never hold, because a while(l < r) loop
>
> It should be `while (l <= r)`, I forgot to update it, but I mentioned
> that I do want to allow l == r condition.
>
> > is used. Moreover, even if the condition were to hold, it wouldn't guarantee
> > a successful search.
>
> Elaborate please on "wouldn't guarantee a successful search".

I think a successful search is that we can successfully find the element that
we want.

>
> >
> > >         r = m;
> > >     } else {
> > >         l = m + 1;
> > >     }
> > > }
> > > /* here we know given element doesn't exist, return index beyond end of types */
> > > return btf__type_cnt(btf);
> >
> > I think that return -ENOENT seems more reasonable.
>
> Think how you will be using this inside btf_find_type_by_name_kind():
>
>
> int idx = btf_find_by_name_bsearch(btf, name);
>
> for (int n = btf__type_cnt(btf); idx < n; idx++) {
>     struct btf_type *t = btf__type_by_id(btf, idx);
>     const char *tname = btf__str_by_offset(btf, t->name_off);
>     if (strcmp(tname, name) != 0)
>         return -ENOENT;
>     if (btf_kind(t) == kind)
>         return idx;
> }
> return -ENOENT;

Thanks, it seems cleaner.

>
>
> Having btf_find_by_name_bsearch() return -ENOENT instead of
> btf__type_cnt() just will require extra explicit -ENOENT handling. And
> given the function now can return "error", we'd need to either handle
> other non-ENOENT errors, to at least leave comment that this should
> never happen, though interface itself looks like it could.
>
> This is relatively minor and its all internal implementation, so we
> can change that later. But I'm explaining my reasons for why I'd
> return index of non-existing type after the end, just like you'd do
> with pointer-based interfaces that return pointer after the last
> element.

Thanks, I see.

>
>
> >
> > >
> > >
> > > We could have checked instead whether strcmp(btf__str_by_offset(btf,
> > > btf__type_by_id(btf, btf__type_cnt() - 1)->name_off), name) < 0 and
> > > exit early. That's just a bit more code duplication of essentially
> > > what we do inside the loop, so that if (l == r) seems fine to me, but
> > > I'm not married to this.
> >
> > Sorry, I believe that even if strcmp(btf__str_by_offset(btf,
> > btf__type_by_id(btf,
> > btf__type_cnt() - 1)->name_off), name) >= 0, it still doesn't seem to
> > guarantee that the search will definitely succeed.
>
> If the last element has >= name, search will definitely find at least
> that element. What do you mean by "succeed"? All I care about here is

Thank you. By "successful search," I mean finding the exact matching
element we're looking for—not just the first element that meets the "≥"
condition.

Here's a concrete example to illustrate the issue:

Base BTF contains: {"A", "C", "E", "F"}
Split BTF contains: {"B", "D"}
Target search: "D" in split BTF

The current implementation recursively searches from the base BTF first.
While "D" is lexicographically ≤ "F" (the last element in base BTF), "D" doesn't
actually exist in the base BTF. When the binary search reaches the l
== r condition,
it returns the index of "E" instead.

This requires an extra name comparison check after btf_find_by_name_bsearch
returns, which could be avoided in the first loop iteration if the
search directly
identified exact matches.

int idx = btf_find_by_name_bsearch(btf, name);

for (int n = btf__type_cnt(btf); idx < n; idx++) {
    struct btf_type *t = btf__type_by_id(btf, idx);
    const char *tname = btf__str_by_offset(btf, t->name_off);
    if (strcmp(tname, name) != 0)  <<< This check is redundant on the first loop
                                                            iteration
when a matching index is found
        return -ENOENT;
    if (btf_kind(t) == kind)
        return idx;
}
return -ENOENT;

I tested this with a simple program searching for 3 in {0, 1, 2, 4, 5}:

int main(int argc, char *argv[])
{
        int values[] = {0, 1, 2, 4, 5};
        int to_find;
        int i;

        to_find = atoi(argv[1]);;

        for (i = 0; i < ARRAY_SIZE(values); i++)
                printf("[%d] = %d\n", i , values[i]);

        printf("To Find %d\n", to_find);

        {
                int l, m, r;

                l = 0;
                r = ARRAY_SIZE(values) - 1;

                while (l <= r) {
                        m = l + (r- l) / 2;
                        if (values[m] >= to_find) {
                                if (l == r) {
                                        printf("!!!! Found: [%d] ==>
%d\n", r, values[r]);
                                        break;
                                }
                                r = m;
                        } else {
                                l = m + 1;
                        }
                }

                printf("END: l: %d, r: %d\n", l, r);
        }

        return 0;
}

Output:
[0] = 0
[1] = 1
[2] = 2
[3] = 4
[4] = 5
To Find 3
!!!! Found: [3] ==> 4
END: l: 3, r: 3

The search returns index 3 (value 4), which is the first value ≥ 3,
but since 4 ≠ 3,
it's not an exact match. Thus, the algorithm cannot guarantee a
successful search
for the exact element without additional checks.

> that binary search loop doesn't loop forever and it returns correct
> index (or detects that no element can be found).
>
> >
> > >
> > > >
> > > > 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;
> > > >         __u32 total;
> > > >
> > > >         if (!btf)
> > > >                 goto out;
> > > >
> > > >         if (start_id < btf->start_id) {
> > > >                 err = btf_find_type_by_name_kind(btf->base_btf, start_id,
> > > >                                                  type_name, kind);
> > > >                 if (err == -ENOENT)
> > > >                         start_id = btf->start_id;
> > > >         }
> > > >
> > > >         if (err == -ENOENT) {
> > > >                 if (btf_check_sorted((struct btf *)btf)) {
> > > >                         /* binary search */
> > > >                         bool skip_first;
> > > >                         int ret;
> > > >
> > > >                         /* return the leftmost with maching names */
> > > >                         ret = btf_find_type_by_name_bsearch(btf,
> > > > type_name, start_id);
> > > >                         if (ret < 0)
> > > >                                 goto out;
> > > >                         /* skip kind checking */
> > > >                         if (kind == -1)
> > > >                                 return ret;
> > > >                         total = btf__type_cnt(btf);
> > > >                         skip_first = true;
> > > >                         do {
> > > >                                 t = btf_type_by_id(btf, ret);
> > > >                                 if (btf_kind(t) != kind) {
> > > >                                         if (skip_first) {
> > > >                                                 skip_first = false;
> > > >                                                 continue;
> > > >                                         }
> > > >                                 } else if (skip_first) {
> > > >                                         return ret;
> > > >                                 }
> > > >                                 if (!t->name_off)
> > > >                                         break;
> > > >                                 tname = btf__str_by_offset(btf, t->name_off);
> > > >                                 if (tname && !strcmp(tname, type_name))
> > > >                                         return ret;
> > > >                                 else
> > > >                                         break;
> > > >                         } while (++ret < total);
> > > >                 } else {
> > > >                         /* linear search */
> > > > ...
> > > >                 }
> > > >         }
> > > >
> > > > out:
> > > >         return err;
> > > > }

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Andrii Nakryiko 1 month, 1 week ago

On Thu, Nov 6, 2025 at 8:57 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
>
> On Fri, Nov 7, 2025 at 1:31 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Wed, Nov 5, 2025 at 11:49 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > >
> > > On Thu, Nov 6, 2025 at 2:11 AM Andrii Nakryiko
> > > <andrii.nakryiko@gmail.com> wrote:
> > > >
> > > > On Wed, Nov 5, 2025 at 5:48 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > > > >
> > > > > On Wed, Nov 5, 2025 at 9:17 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > > >
> > > > > > On Tue, 2025-11-04 at 16:54 -0800, Andrii Nakryiko wrote:
> > > > > > > On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > > > > >
> > > > > > > > On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
> > > > > > > >
> > > > > > > > [...]
> > > > > > > >
> > > > > > > > > > @@ -897,44 +903,134 @@ 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)
> > > > > > > > > > +/*
> > > > > > > > > > + * Find BTF types with matching names within the [left, right] index range.
> > > > > > > > > > + * On success, updates *left and *right to the boundaries of the matching range
> > > > > > > > > > + * and returns the leftmost matching index.
> > > > > > > > > > + */
> > > > > > > > > > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > > > > > > > > > +                                               __s32 *left, __s32 *right)
> > > > > > > > >
> > > > > > > > > I thought we discussed this, why do you need "right"? Two binary
> > > > > > > > > searches where one would do just fine.
> > > > > > > >
> > > > > > > > I think the idea is that there would be less strcmp's if there is a
> > > > > > > > long sequence of items with identical names.
> > > > > > >
> > > > > > > Sure, it's a tradeoff. But how long is the set of duplicate name
> > > > > > > entries we expect in kernel BTF? Additional O(logN) over 70K+ types
> > > > > > > with high likelihood will take more comparisons.
> > > > > >
> > > > > > $ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head
> > > > > >   51737 '(anon)'
> > > > > >     277 'bpf_kfunc'
> > > > > >       4 'long
> > > > > >       3 'perf_aux_event'
> > > > > >       3 'workspace'
> > > > > >       2 'ata_acpi_gtm'
> > > > > >       2 'avc_cache_stats'
> > > > > >       2 'bh_accounting'
> > > > > >       2 'bp_cpuinfo'
> > > > > >       2 'bpf_fastcall'
> > > > > >
> > > > > > 'bpf_kfunc' is probably for decl_tags.
> > > > > > So I agree with you regarding the second binary search, it is not
> > > > > > necessary.  But skipping all anonymous types (and thus having to
> > > > > > maintain nr_sorted_types) might be useful, on each search two
> > > > > > iterations would be wasted to skip those.
> > > >
> > > > fair enough, eliminating a big chunk of anonymous types is useful, let's do this
> > > >
> > > > >
> > > > > Thank you. After removing the redundant iterations, performance increased
> > > > > significantly compared with two iterations.
> > > > >
> > > > > Test Case: Locate all 58,719 named types in vmlinux BTF
> > > > > Methodology:
> > > > > ./vmtest.sh -- ./test_progs -t btf_permute/perf -v
> > > > >
> > > > > Two iterations:
> > > > > | Condition          | Lookup Time | Improvement |
> > > > > |--------------------|-------------|-------------|
> > > > > | Unsorted (Linear)  | 17,282 ms   | Baseline    |
> > > > > | Sorted (Binary)    | 19 ms       | 909x faster |
> > > > >
> > > > > One iteration:
> > > > > Results:
> > > > > | Condition          | Lookup Time | Improvement |
> > > > > |--------------------|-------------|-------------|
> > > > > | Unsorted (Linear)  | 17,619 ms   | Baseline    |
> > > > > | Sorted (Binary)    | 10 ms       | 1762x faster |
> > > > >
> > > > > Here is the code implementation with a single iteration approach.
> > > > > I believe this scenario differs from find_linfo because we cannot
> > > > > determine in advance whether the specified type name will be found.
> > > > > Please correct me if I've misunderstood anything, and I welcome any
> > > > > guidance on this matter.
> > > > >
> > > > > static __s32 btf_find_type_by_name_bsearch(const struct btf *btf,
> > > > > const char *name,
> > > > >                                                 __s32 start_id)
> > > > > {
> > > > >         const struct btf_type *t;
> > > > >         const char *tname;
> > > > >         __s32 l, r, m, lmost = -ENOENT;
> > > > >         int ret;
> > > > >
> > > > >         /* found the leftmost btf_type that matches */
> > > > >         l = start_id;
> > > > >         r = btf__type_cnt(btf) - 1;
> > > > >         while (l <= r) {
> > > > >                 m = l + (r - l) / 2;
> > > > >                 t = btf_type_by_id(btf, m);
> > > > >                 if (!t->name_off) {
> > > > >                         ret = 1;
> > > > >                 } else {
> > > > >                         tname = btf__str_by_offset(btf, t->name_off);
> > > > >                         ret = !tname ? 1 : strcmp(tname, name);
> > > > >                 }
> > > > >                 if (ret < 0) {
> > > > >                         l = m + 1;
> > > > >                 } else {
> > > > >                         if (ret == 0)
> > > > >                                 lmost = m;
> > > > >                         r = m - 1;
> > > > >                 }
> > > > >         }
> > > > >
> > > > >         return lmost;
> > > > > }
> > > >
> > > > There are different ways to implement this. At the highest level,
> > > > implementation below just searches for leftmost element that has name
> > > > >= the one we are searching for. One complication is that such element
> > > > might not event exists. We can solve that checking ahead of time
> > > > whether the rightmost type satisfied the condition, or we could do
> > > > something similar to what I do in the loop below, where I allow l == r
> > > > and then if that element has name >= to what we search, we exit
> > > > because we found it. And if not, l will become larger than r, we'll
> > > > break out of the loop and we'll know that we couldn't find the
> > > > element. I haven't tested it, but please take a look and if you decide
> > > > to go with such approach, do test it for edge cases, of course.
> > > >
> > > > /*
> > > >  * We are searching for the smallest r such that type #r's name is >= name.
> > > >  * It might not exist, in which case we'll have l == r + 1.
> > > >  */
> > > > l = start_id;
> > > > r = btf__type_cnt(btf) - 1;
> > > > 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; /* found it! */
> > >
> > > It seems that this if condition will never hold, because a while(l < r) loop
> >
> > It should be `while (l <= r)`, I forgot to update it, but I mentioned
> > that I do want to allow l == r condition.
> >
> > > is used. Moreover, even if the condition were to hold, it wouldn't guarantee
> > > a successful search.
> >
> > Elaborate please on "wouldn't guarantee a successful search".
>
> I think a successful search is that we can successfully find the element that
> we want.
>

Ok, I never intended to find exact match with that leftmost >= element
as a primitive.

> >
> > >
> > > >         r = m;
> > > >     } else {
> > > >         l = m + 1;
> > > >     }
> > > > }
> > > > /* here we know given element doesn't exist, return index beyond end of types */
> > > > return btf__type_cnt(btf);
> > >
> > > I think that return -ENOENT seems more reasonable.
> >
> > Think how you will be using this inside btf_find_type_by_name_kind():
> >
> >
> > int idx = btf_find_by_name_bsearch(btf, name);
> >
> > for (int n = btf__type_cnt(btf); idx < n; idx++) {
> >     struct btf_type *t = btf__type_by_id(btf, idx);
> >     const char *tname = btf__str_by_offset(btf, t->name_off);
> >     if (strcmp(tname, name) != 0)
> >         return -ENOENT;
> >     if (btf_kind(t) == kind)
> >         return idx;
> > }
> > return -ENOENT;
>
> Thanks, it seems cleaner.

ok, great

>
> >
> >
> > Having btf_find_by_name_bsearch() return -ENOENT instead of
> > btf__type_cnt() just will require extra explicit -ENOENT handling. And
> > given the function now can return "error", we'd need to either handle
> > other non-ENOENT errors, to at least leave comment that this should
> > never happen, though interface itself looks like it could.
> >
> > This is relatively minor and its all internal implementation, so we
> > can change that later. But I'm explaining my reasons for why I'd
> > return index of non-existing type after the end, just like you'd do
> > with pointer-based interfaces that return pointer after the last
> > element.
>
> Thanks, I see.
>
> >
> >
> > >
> > > >
> > > >
> > > > We could have checked instead whether strcmp(btf__str_by_offset(btf,
> > > > btf__type_by_id(btf, btf__type_cnt() - 1)->name_off), name) < 0 and
> > > > exit early. That's just a bit more code duplication of essentially
> > > > what we do inside the loop, so that if (l == r) seems fine to me, but
> > > > I'm not married to this.
> > >
> > > Sorry, I believe that even if strcmp(btf__str_by_offset(btf,
> > > btf__type_by_id(btf,
> > > btf__type_cnt() - 1)->name_off), name) >= 0, it still doesn't seem to
> > > guarantee that the search will definitely succeed.
> >
> > If the last element has >= name, search will definitely find at least
> > that element. What do you mean by "succeed"? All I care about here is
>
> Thank you. By "successful search," I mean finding the exact matching
> element we're looking for—not just the first element that meets the "≥"
> condition.

We don't have to find the exact match, just the leftmost >= element.
For search by name+kind you will have to do linear search *anyways*
and compare name for every single potential candidate (Except maybe
the very first one as micro-optimization and complication, if we had
exact matching leftmost element; but I don't care about that
complication). So leftmost >= element is a universal "primitive" that
allows you to implement exact by name or exact by name+kind search in
exactly the same fashion.

>
> Here's a concrete example to illustrate the issue:
>
> Base BTF contains: {"A", "C", "E", "F"}
> Split BTF contains: {"B", "D"}
> Target search: "D" in split BTF
>
> The current implementation recursively searches from the base BTF first.
> While "D" is lexicographically ≤ "F" (the last element in base BTF), "D" doesn't
> actually exist in the base BTF. When the binary search reaches the l
> == r condition,
> it returns the index of "E" instead.
>
> This requires an extra name comparison check after btf_find_by_name_bsearch
> returns, which could be avoided in the first loop iteration if the
> search directly
> identified exact matches.

See above, I think this is misguided. There is nothing wrong with
checking after bsearch returns *candidate* index, and you cannot avoid
that for name+kind search.

>
> int idx = btf_find_by_name_bsearch(btf, name);
>
> for (int n = btf__type_cnt(btf); idx < n; idx++) {
>     struct btf_type *t = btf__type_by_id(btf, idx);
>     const char *tname = btf__str_by_offset(btf, t->name_off);
>     if (strcmp(tname, name) != 0)  <<< This check is redundant on the first loop
>                                                             iteration

Yes, I think this is absolutely OK and acceptable. Are you worried
about the overhead of a single strcmp()? See below for notes on having
single overall name and name+kind implementation using this approach.

> when a matching index is found
>         return -ENOENT;
>     if (btf_kind(t) == kind)
>         return idx;
> }
> return -ENOENT;
>
> I tested this with a simple program searching for 3 in {0, 1, 2, 4, 5}:
>
> int main(int argc, char *argv[])
> {
>         int values[] = {0, 1, 2, 4, 5};
>         int to_find;
>         int i;
>
>         to_find = atoi(argv[1]);;
>
>         for (i = 0; i < ARRAY_SIZE(values); i++)
>                 printf("[%d] = %d\n", i , values[i]);
>
>         printf("To Find %d\n", to_find);
>
>         {
>                 int l, m, r;
>
>                 l = 0;
>                 r = ARRAY_SIZE(values) - 1;
>
>                 while (l <= r) {
>                         m = l + (r- l) / 2;
>                         if (values[m] >= to_find) {
>                                 if (l == r) {
>                                         printf("!!!! Found: [%d] ==>
> %d\n", r, values[r]);
>                                         break;
>                                 }
>                                 r = m;
>                         } else {
>                                 l = m + 1;
>                         }
>                 }
>
>                 printf("END: l: %d, r: %d\n", l, r);
>         }
>
>         return 0;
> }
>
> Output:
> [0] = 0
> [1] = 1
> [2] = 2
> [3] = 4
> [4] = 5
> To Find 3
> !!!! Found: [3] ==> 4
> END: l: 3, r: 3
>
> The search returns index 3 (value 4), which is the first value ≥ 3,
> but since 4 ≠ 3,
> it's not an exact match. Thus, the algorithm cannot guarantee a
> successful search
> for the exact element without additional checks.

It was never a goal to find an exact match, yes, additional checks
after the search is necessary to confirm name or name+kind match (and
the latter will have to check name for every single item, except maybe
the first one if we had exact match "guarantee", but I think this is
absolutely unnecessary). And this is unavoidable for name+kind search.
So instead of optimizing one extra strcmp() let's have uniform
implementation for both name and name+kind searches. In fact, you can
even have the same universal implementation of both if you treat kind
== 0 as "don't care about kind".


>
> > that binary search loop doesn't loop forever and it returns correct
> > index (or detects that no element can be found).
> >
> > >
> > > >
> > > > >
> > > > > 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;
> > > > >         __u32 total;
> > > > >
> > > > >         if (!btf)
> > > > >                 goto out;
> > > > >
> > > > >         if (start_id < btf->start_id) {
> > > > >                 err = btf_find_type_by_name_kind(btf->base_btf, start_id,
> > > > >                                                  type_name, kind);
> > > > >                 if (err == -ENOENT)
> > > > >                         start_id = btf->start_id;
> > > > >         }
> > > > >
> > > > >         if (err == -ENOENT) {
> > > > >                 if (btf_check_sorted((struct btf *)btf)) {
> > > > >                         /* binary search */
> > > > >                         bool skip_first;
> > > > >                         int ret;
> > > > >
> > > > >                         /* return the leftmost with maching names */
> > > > >                         ret = btf_find_type_by_name_bsearch(btf,
> > > > > type_name, start_id);
> > > > >                         if (ret < 0)
> > > > >                                 goto out;
> > > > >                         /* skip kind checking */
> > > > >                         if (kind == -1)
> > > > >                                 return ret;
> > > > >                         total = btf__type_cnt(btf);
> > > > >                         skip_first = true;
> > > > >                         do {
> > > > >                                 t = btf_type_by_id(btf, ret);
> > > > >                                 if (btf_kind(t) != kind) {
> > > > >                                         if (skip_first) {
> > > > >                                                 skip_first = false;
> > > > >                                                 continue;
> > > > >                                         }
> > > > >                                 } else if (skip_first) {
> > > > >                                         return ret;
> > > > >                                 }
> > > > >                                 if (!t->name_off)
> > > > >                                         break;
> > > > >                                 tname = btf__str_by_offset(btf, t->name_off);
> > > > >                                 if (tname && !strcmp(tname, type_name))
> > > > >                                         return ret;
> > > > >                                 else
> > > > >                                         break;
> > > > >                         } while (++ret < total);
> > > > >                 } else {
> > > > >                         /* linear search */
> > > > > ...
> > > > >                 }
> > > > >         }
> > > > >
> > > > > out:
> > > > >         return err;
> > > > > }

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Donglin Peng 1 month, 1 week ago

On Sat, Nov 8, 2025 at 1:01 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Thu, Nov 6, 2025 at 8:57 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> >
> > On Fri, Nov 7, 2025 at 1:31 AM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Wed, Nov 5, 2025 at 11:49 PM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > > >
> > > > On Thu, Nov 6, 2025 at 2:11 AM Andrii Nakryiko
> > > > <andrii.nakryiko@gmail.com> wrote:
> > > > >
> > > > > On Wed, Nov 5, 2025 at 5:48 AM Donglin Peng <dolinux.peng@gmail.com> wrote:
> > > > > >
> > > > > > On Wed, Nov 5, 2025 at 9:17 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > > > >
> > > > > > > On Tue, 2025-11-04 at 16:54 -0800, Andrii Nakryiko wrote:
> > > > > > > > On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > > > > > >
> > > > > > > > > On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
> > > > > > > > >
> > > > > > > > > [...]
> > > > > > > > >
> > > > > > > > > > > @@ -897,44 +903,134 @@ 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)
> > > > > > > > > > > +/*
> > > > > > > > > > > + * Find BTF types with matching names within the [left, right] index range.
> > > > > > > > > > > + * On success, updates *left and *right to the boundaries of the matching range
> > > > > > > > > > > + * and returns the leftmost matching index.
> > > > > > > > > > > + */
> > > > > > > > > > > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > > > > > > > > > > +                                               __s32 *left, __s32 *right)
> > > > > > > > > >
> > > > > > > > > > I thought we discussed this, why do you need "right"? Two binary
> > > > > > > > > > searches where one would do just fine.
> > > > > > > > >
> > > > > > > > > I think the idea is that there would be less strcmp's if there is a
> > > > > > > > > long sequence of items with identical names.
> > > > > > > >
> > > > > > > > Sure, it's a tradeoff. But how long is the set of duplicate name
> > > > > > > > entries we expect in kernel BTF? Additional O(logN) over 70K+ types
> > > > > > > > with high likelihood will take more comparisons.
> > > > > > >
> > > > > > > $ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head
> > > > > > >   51737 '(anon)'
> > > > > > >     277 'bpf_kfunc'
> > > > > > >       4 'long
> > > > > > >       3 'perf_aux_event'
> > > > > > >       3 'workspace'
> > > > > > >       2 'ata_acpi_gtm'
> > > > > > >       2 'avc_cache_stats'
> > > > > > >       2 'bh_accounting'
> > > > > > >       2 'bp_cpuinfo'
> > > > > > >       2 'bpf_fastcall'
> > > > > > >
> > > > > > > 'bpf_kfunc' is probably for decl_tags.
> > > > > > > So I agree with you regarding the second binary search, it is not
> > > > > > > necessary.  But skipping all anonymous types (and thus having to
> > > > > > > maintain nr_sorted_types) might be useful, on each search two
> > > > > > > iterations would be wasted to skip those.
> > > > >
> > > > > fair enough, eliminating a big chunk of anonymous types is useful, let's do this
> > > > >
> > > > > >
> > > > > > Thank you. After removing the redundant iterations, performance increased
> > > > > > significantly compared with two iterations.
> > > > > >
> > > > > > Test Case: Locate all 58,719 named types in vmlinux BTF
> > > > > > Methodology:
> > > > > > ./vmtest.sh -- ./test_progs -t btf_permute/perf -v
> > > > > >
> > > > > > Two iterations:
> > > > > > | Condition          | Lookup Time | Improvement |
> > > > > > |--------------------|-------------|-------------|
> > > > > > | Unsorted (Linear)  | 17,282 ms   | Baseline    |
> > > > > > | Sorted (Binary)    | 19 ms       | 909x faster |
> > > > > >
> > > > > > One iteration:
> > > > > > Results:
> > > > > > | Condition          | Lookup Time | Improvement |
> > > > > > |--------------------|-------------|-------------|
> > > > > > | Unsorted (Linear)  | 17,619 ms   | Baseline    |
> > > > > > | Sorted (Binary)    | 10 ms       | 1762x faster |
> > > > > >
> > > > > > Here is the code implementation with a single iteration approach.
> > > > > > I believe this scenario differs from find_linfo because we cannot
> > > > > > determine in advance whether the specified type name will be found.
> > > > > > Please correct me if I've misunderstood anything, and I welcome any
> > > > > > guidance on this matter.
> > > > > >
> > > > > > static __s32 btf_find_type_by_name_bsearch(const struct btf *btf,
> > > > > > const char *name,
> > > > > >                                                 __s32 start_id)
> > > > > > {
> > > > > >         const struct btf_type *t;
> > > > > >         const char *tname;
> > > > > >         __s32 l, r, m, lmost = -ENOENT;
> > > > > >         int ret;
> > > > > >
> > > > > >         /* found the leftmost btf_type that matches */
> > > > > >         l = start_id;
> > > > > >         r = btf__type_cnt(btf) - 1;
> > > > > >         while (l <= r) {
> > > > > >                 m = l + (r - l) / 2;
> > > > > >                 t = btf_type_by_id(btf, m);
> > > > > >                 if (!t->name_off) {
> > > > > >                         ret = 1;
> > > > > >                 } else {
> > > > > >                         tname = btf__str_by_offset(btf, t->name_off);
> > > > > >                         ret = !tname ? 1 : strcmp(tname, name);
> > > > > >                 }
> > > > > >                 if (ret < 0) {
> > > > > >                         l = m + 1;
> > > > > >                 } else {
> > > > > >                         if (ret == 0)
> > > > > >                                 lmost = m;
> > > > > >                         r = m - 1;
> > > > > >                 }
> > > > > >         }
> > > > > >
> > > > > >         return lmost;
> > > > > > }
> > > > >
> > > > > There are different ways to implement this. At the highest level,
> > > > > implementation below just searches for leftmost element that has name
> > > > > >= the one we are searching for. One complication is that such element
> > > > > might not event exists. We can solve that checking ahead of time
> > > > > whether the rightmost type satisfied the condition, or we could do
> > > > > something similar to what I do in the loop below, where I allow l == r
> > > > > and then if that element has name >= to what we search, we exit
> > > > > because we found it. And if not, l will become larger than r, we'll
> > > > > break out of the loop and we'll know that we couldn't find the
> > > > > element. I haven't tested it, but please take a look and if you decide
> > > > > to go with such approach, do test it for edge cases, of course.
> > > > >
> > > > > /*
> > > > >  * We are searching for the smallest r such that type #r's name is >= name.
> > > > >  * It might not exist, in which case we'll have l == r + 1.
> > > > >  */
> > > > > l = start_id;
> > > > > r = btf__type_cnt(btf) - 1;
> > > > > 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; /* found it! */
> > > >
> > > > It seems that this if condition will never hold, because a while(l < r) loop
> > >
> > > It should be `while (l <= r)`, I forgot to update it, but I mentioned
> > > that I do want to allow l == r condition.
> > >
> > > > is used. Moreover, even if the condition were to hold, it wouldn't guarantee
> > > > a successful search.
> > >
> > > Elaborate please on "wouldn't guarantee a successful search".
> >
> > I think a successful search is that we can successfully find the element that
> > we want.
> >
>
> Ok, I never intended to find exact match with that leftmost >= element
> as a primitive.
>
> > >
> > > >
> > > > >         r = m;
> > > > >     } else {
> > > > >         l = m + 1;
> > > > >     }
> > > > > }
> > > > > /* here we know given element doesn't exist, return index beyond end of types */
> > > > > return btf__type_cnt(btf);
> > > >
> > > > I think that return -ENOENT seems more reasonable.
> > >
> > > Think how you will be using this inside btf_find_type_by_name_kind():
> > >
> > >
> > > int idx = btf_find_by_name_bsearch(btf, name);
> > >
> > > for (int n = btf__type_cnt(btf); idx < n; idx++) {
> > >     struct btf_type *t = btf__type_by_id(btf, idx);
> > >     const char *tname = btf__str_by_offset(btf, t->name_off);
> > >     if (strcmp(tname, name) != 0)
> > >         return -ENOENT;
> > >     if (btf_kind(t) == kind)
> > >         return idx;
> > > }
> > > return -ENOENT;
> >
> > Thanks, it seems cleaner.
>
> ok, great
>
> >
> > >
> > >
> > > Having btf_find_by_name_bsearch() return -ENOENT instead of
> > > btf__type_cnt() just will require extra explicit -ENOENT handling. And
> > > given the function now can return "error", we'd need to either handle
> > > other non-ENOENT errors, to at least leave comment that this should
> > > never happen, though interface itself looks like it could.
> > >
> > > This is relatively minor and its all internal implementation, so we
> > > can change that later. But I'm explaining my reasons for why I'd
> > > return index of non-existing type after the end, just like you'd do
> > > with pointer-based interfaces that return pointer after the last
> > > element.
> >
> > Thanks, I see.
> >
> > >
> > >
> > > >
> > > > >
> > > > >
> > > > > We could have checked instead whether strcmp(btf__str_by_offset(btf,
> > > > > btf__type_by_id(btf, btf__type_cnt() - 1)->name_off), name) < 0 and
> > > > > exit early. That's just a bit more code duplication of essentially
> > > > > what we do inside the loop, so that if (l == r) seems fine to me, but
> > > > > I'm not married to this.
> > > >
> > > > Sorry, I believe that even if strcmp(btf__str_by_offset(btf,
> > > > btf__type_by_id(btf,
> > > > btf__type_cnt() - 1)->name_off), name) >= 0, it still doesn't seem to
> > > > guarantee that the search will definitely succeed.
> > >
> > > If the last element has >= name, search will definitely find at least
> > > that element. What do you mean by "succeed"? All I care about here is
> >
> > Thank you. By "successful search," I mean finding the exact matching
> > element we're looking for—not just the first element that meets the "≥"
> > condition.
>
> We don't have to find the exact match, just the leftmost >= element.
> For search by name+kind you will have to do linear search *anyways*
> and compare name for every single potential candidate (Except maybe
> the very first one as micro-optimization and complication, if we had
> exact matching leftmost element; but I don't care about that
> complication). So leftmost >= element is a universal "primitive" that
> allows you to implement exact by name or exact by name+kind search in
> exactly the same fashion.
>
> >
> > Here's a concrete example to illustrate the issue:
> >
> > Base BTF contains: {"A", "C", "E", "F"}
> > Split BTF contains: {"B", "D"}
> > Target search: "D" in split BTF
> >
> > The current implementation recursively searches from the base BTF first.
> > While "D" is lexicographically ≤ "F" (the last element in base BTF), "D" doesn't
> > actually exist in the base BTF. When the binary search reaches the l
> > == r condition,
> > it returns the index of "E" instead.
> >
> > This requires an extra name comparison check after btf_find_by_name_bsearch
> > returns, which could be avoided in the first loop iteration if the
> > search directly
> > identified exact matches.
>
> See above, I think this is misguided. There is nothing wrong with
> checking after bsearch returns *candidate* index, and you cannot avoid
> that for name+kind search.
>
> >
> > int idx = btf_find_by_name_bsearch(btf, name);
> >
> > for (int n = btf__type_cnt(btf); idx < n; idx++) {
> >     struct btf_type *t = btf__type_by_id(btf, idx);
> >     const char *tname = btf__str_by_offset(btf, t->name_off);
> >     if (strcmp(tname, name) != 0)  <<< This check is redundant on the first loop
> >                                                             iteration
>
> Yes, I think this is absolutely OK and acceptable. Are you worried
> about the overhead of a single strcmp()? See below for notes on having
> single overall name and name+kind implementation using this approach.
>
> > when a matching index is found
> >         return -ENOENT;
> >     if (btf_kind(t) == kind)
> >         return idx;
> > }
> > return -ENOENT;
> >
> > I tested this with a simple program searching for 3 in {0, 1, 2, 4, 5}:
> >
> > int main(int argc, char *argv[])
> > {
> >         int values[] = {0, 1, 2, 4, 5};
> >         int to_find;
> >         int i;
> >
> >         to_find = atoi(argv[1]);;
> >
> >         for (i = 0; i < ARRAY_SIZE(values); i++)
> >                 printf("[%d] = %d\n", i , values[i]);
> >
> >         printf("To Find %d\n", to_find);
> >
> >         {
> >                 int l, m, r;
> >
> >                 l = 0;
> >                 r = ARRAY_SIZE(values) - 1;
> >
> >                 while (l <= r) {
> >                         m = l + (r- l) / 2;
> >                         if (values[m] >= to_find) {
> >                                 if (l == r) {
> >                                         printf("!!!! Found: [%d] ==>
> > %d\n", r, values[r]);
> >                                         break;
> >                                 }
> >                                 r = m;
> >                         } else {
> >                                 l = m + 1;
> >                         }
> >                 }
> >
> >                 printf("END: l: %d, r: %d\n", l, r);
> >         }
> >
> >         return 0;
> > }
> >
> > Output:
> > [0] = 0
> > [1] = 1
> > [2] = 2
> > [3] = 4
> > [4] = 5
> > To Find 3
> > !!!! Found: [3] ==> 4
> > END: l: 3, r: 3
> >
> > The search returns index 3 (value 4), which is the first value ≥ 3,
> > but since 4 ≠ 3,
> > it's not an exact match. Thus, the algorithm cannot guarantee a
> > successful search
> > for the exact element without additional checks.
>
> It was never a goal to find an exact match, yes, additional checks
> after the search is necessary to confirm name or name+kind match (and
> the latter will have to check name for every single item, except maybe
> the first one if we had exact match "guarantee", but I think this is
> absolutely unnecessary). And this is unavoidable for name+kind search.
> So instead of optimizing one extra strcmp() let's have uniform
> implementation for both name and name+kind searches. In fact, you can
> even have the same universal implementation of both if you treat kind
> == 0 as "don't care about kind".

Thanks, I'll apply this suggestion in the next version.

>
>
> >
> > > that binary search loop doesn't loop forever and it returns correct
> > > index (or detects that no element can be found).
> > >
> > > >
> > > > >
> > > > > >
> > > > > > 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;
> > > > > >         __u32 total;
> > > > > >
> > > > > >         if (!btf)
> > > > > >                 goto out;
> > > > > >
> > > > > >         if (start_id < btf->start_id) {
> > > > > >                 err = btf_find_type_by_name_kind(btf->base_btf, start_id,
> > > > > >                                                  type_name, kind);
> > > > > >                 if (err == -ENOENT)
> > > > > >                         start_id = btf->start_id;
> > > > > >         }
> > > > > >
> > > > > >         if (err == -ENOENT) {
> > > > > >                 if (btf_check_sorted((struct btf *)btf)) {
> > > > > >                         /* binary search */
> > > > > >                         bool skip_first;
> > > > > >                         int ret;
> > > > > >
> > > > > >                         /* return the leftmost with maching names */
> > > > > >                         ret = btf_find_type_by_name_bsearch(btf,
> > > > > > type_name, start_id);
> > > > > >                         if (ret < 0)
> > > > > >                                 goto out;
> > > > > >                         /* skip kind checking */
> > > > > >                         if (kind == -1)
> > > > > >                                 return ret;
> > > > > >                         total = btf__type_cnt(btf);
> > > > > >                         skip_first = true;
> > > > > >                         do {
> > > > > >                                 t = btf_type_by_id(btf, ret);
> > > > > >                                 if (btf_kind(t) != kind) {
> > > > > >                                         if (skip_first) {
> > > > > >                                                 skip_first = false;
> > > > > >                                                 continue;
> > > > > >                                         }
> > > > > >                                 } else if (skip_first) {
> > > > > >                                         return ret;
> > > > > >                                 }
> > > > > >                                 if (!t->name_off)
> > > > > >                                         break;
> > > > > >                                 tname = btf__str_by_offset(btf, t->name_off);
> > > > > >                                 if (tname && !strcmp(tname, type_name))
> > > > > >                                         return ret;
> > > > > >                                 else
> > > > > >                                         break;
> > > > > >                         } while (++ret < total);
> > > > > >                 } else {
> > > > > >                         /* linear search */
> > > > > > ...
> > > > > >                 }
> > > > > >         }
> > > > > >
> > > > > > out:
> > > > > >         return err;
> > > > > > }

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Eduard Zingerman 1 month, 1 week ago

On Wed, 2025-11-05 at 21:48 +0800, Donglin Peng wrote:
> On Wed, Nov 5, 2025 at 9:17 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > On Tue, 2025-11-04 at 16:54 -0800, Andrii Nakryiko wrote:
> > > On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > 
> > > > On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
> > > > 
> > > > [...]
> > > > 
> > > > > > @@ -897,44 +903,134 @@ 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)
> > > > > > +/*
> > > > > > + * Find BTF types with matching names within the [left, right] index range.
> > > > > > + * On success, updates *left and *right to the boundaries of the matching range
> > > > > > + * and returns the leftmost matching index.
> > > > > > + */
> > > > > > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > > > > > +                                               __s32 *left, __s32 *right)
> > > > > 
> > > > > I thought we discussed this, why do you need "right"? Two binary
> > > > > searches where one would do just fine.
> > > > 
> > > > I think the idea is that there would be less strcmp's if there is a
> > > > long sequence of items with identical names.
> > > 
> > > Sure, it's a tradeoff. But how long is the set of duplicate name
> > > entries we expect in kernel BTF? Additional O(logN) over 70K+ types
> > > with high likelihood will take more comparisons.
> > 
> > $ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head
> >   51737 '(anon)'
> >     277 'bpf_kfunc'
> >       4 'long
> >       3 'perf_aux_event'
> >       3 'workspace'
> >       2 'ata_acpi_gtm'
> >       2 'avc_cache_stats'
> >       2 'bh_accounting'
> >       2 'bp_cpuinfo'
> >       2 'bpf_fastcall'
> > 
> > 'bpf_kfunc' is probably for decl_tags.
> > So I agree with you regarding the second binary search, it is not
> > necessary.  But skipping all anonymous types (and thus having to
> > maintain nr_sorted_types) might be useful, on each search two
> > iterations would be wasted to skip those.
> 
> Thank you. After removing the redundant iterations, performance increased
> significantly compared with two iterations.
> 
> Test Case: Locate all 58,719 named types in vmlinux BTF
> Methodology:
> ./vmtest.sh -- ./test_progs -t btf_permute/perf -v
> 
> Two iterations:
> > Condition          | Lookup Time | Improvement |
> > --------------------|-------------|-------------|
> > Unsorted (Linear)  | 17,282 ms   | Baseline    |
> > Sorted (Binary)    | 19 ms       | 909x faster |
> 
> One iteration:
> Results:
> > Condition          | Lookup Time | Improvement |
> > --------------------|-------------|-------------|
> > Unsorted (Linear)  | 17,619 ms   | Baseline    |
> > Sorted (Binary)    | 10 ms       | 1762x faster |
> 
> Here is the code implementation with a single iteration approach.

Could you please also check if there is a difference between having
nr_sorted_types as is and having it equal to nr_types?
Want to understand if this optimization is necessary.

[...]

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Donglin Peng 1 month, 1 week ago

On Thu, Nov 6, 2025 at 12:52 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2025-11-05 at 21:48 +0800, Donglin Peng wrote:
> > On Wed, Nov 5, 2025 at 9:17 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > On Tue, 2025-11-04 at 16:54 -0800, Andrii Nakryiko wrote:
> > > > On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > >
> > > > > On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
> > > > >
> > > > > [...]
> > > > >
> > > > > > > @@ -897,44 +903,134 @@ 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)
> > > > > > > +/*
> > > > > > > + * Find BTF types with matching names within the [left, right] index range.
> > > > > > > + * On success, updates *left and *right to the boundaries of the matching range
> > > > > > > + * and returns the leftmost matching index.
> > > > > > > + */
> > > > > > > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > > > > > > +                                               __s32 *left, __s32 *right)
> > > > > >
> > > > > > I thought we discussed this, why do you need "right"? Two binary
> > > > > > searches where one would do just fine.
> > > > >
> > > > > I think the idea is that there would be less strcmp's if there is a
> > > > > long sequence of items with identical names.
> > > >
> > > > Sure, it's a tradeoff. But how long is the set of duplicate name
> > > > entries we expect in kernel BTF? Additional O(logN) over 70K+ types
> > > > with high likelihood will take more comparisons.
> > >
> > > $ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head
> > >   51737 '(anon)'
> > >     277 'bpf_kfunc'
> > >       4 'long
> > >       3 'perf_aux_event'
> > >       3 'workspace'
> > >       2 'ata_acpi_gtm'
> > >       2 'avc_cache_stats'
> > >       2 'bh_accounting'
> > >       2 'bp_cpuinfo'
> > >       2 'bpf_fastcall'
> > >
> > > 'bpf_kfunc' is probably for decl_tags.
> > > So I agree with you regarding the second binary search, it is not
> > > necessary.  But skipping all anonymous types (and thus having to
> > > maintain nr_sorted_types) might be useful, on each search two
> > > iterations would be wasted to skip those.
> >
> > Thank you. After removing the redundant iterations, performance increased
> > significantly compared with two iterations.
> >
> > Test Case: Locate all 58,719 named types in vmlinux BTF
> > Methodology:
> > ./vmtest.sh -- ./test_progs -t btf_permute/perf -v
> >
> > Two iterations:
> > > Condition          | Lookup Time | Improvement |
> > > --------------------|-------------|-------------|
> > > Unsorted (Linear)  | 17,282 ms   | Baseline    |
> > > Sorted (Binary)    | 19 ms       | 909x faster |
> >
> > One iteration:
> > Results:
> > > Condition          | Lookup Time | Improvement |
> > > --------------------|-------------|-------------|
> > > Unsorted (Linear)  | 17,619 ms   | Baseline    |
> > > Sorted (Binary)    | 10 ms       | 1762x faster |
> >
> > Here is the code implementation with a single iteration approach.
>
> Could you please also check if there is a difference between having
> nr_sorted_types as is and having it equal to nr_types?
> Want to understand if this optimization is necessary.

Yes, here is the result:

| Condition                                       | Lookup Time   |
Improvement  |
|----------------------------------------------|------------------
--|------------------|
| Unsorted (Linear)                          | 16666461 us   | Baseline       |
| Sorted (Binary) nr__types             | 9957 us           | 1673x faster |
| Sorted (Binary) nr_sorted_types   | 9337 us           | 1785x faster |

Using nr_sorted_types provides an additional 6% performance improvement
over nr_types.

>
> [...]

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by Eduard Zingerman 1 month, 2 weeks ago

On Tue, 2025-11-04 at 21:40 +0800, Donglin Peng wrote:
> From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
> Cc: Alexei Starovoitov <ast@kernel.org>
> Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Cc: Alan Maguire <alan.maguire@oracle.com>
> Cc: Song Liu <song@kernel.org>
> Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> Signed-off-by: Donglin Peng <dolinux.peng@gmail.com>
> ---

lgtm, have two nits.

>  tools/lib/bpf/btf.c | 142 +++++++++++++++++++++++++++++++++++++-------
>  1 file changed, 119 insertions(+), 23 deletions(-)
> 
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 3bc03f7fe31f..5af14304409c 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;

Silly question: why is this __u32 and not just a flag?

>  	/* if not NULL, points to the base BTF on top of which the current
>  	 * split BTF is based
>  	 */
> @@ -897,44 +903,134 @@ 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)
> +/*
> + * Find BTF types with matching names within the [left, right] index range.
> + * On success, updates *left and *right to the boundaries of the matching range
> + * and returns the leftmost matching index.
> + */
> +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> +						__s32 *left, __s32 *right)
>  {
> -	__u32 i, nr_types = btf__type_cnt(btf);
> +	const struct btf_type *t;
> +	const char *tname;
> +	__s32 l, r, m, lmost, rmost;
> +	int ret;
> +
> +	/* found the leftmost btf_type that matches */
> +	l = *left;
> +	r = *right;
> +	lmost = -1;
> +	while (l <= r) {
> +		m = l + (r - l) / 2;
> +		t = btf_type_by_id(btf, m);
> +		tname = btf__str_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;
> +		}
> +	}

Nit: I think Andrii's point was that this can be written a tad shorter, e.g.:
     https://elixir.bootlin.com/linux/v6.18-rc4/source/kernel/bpf/verifier.c#L2952

>  
> -	if (!strcmp(type_name, "void"))
> -		return 0;
> +	if (lmost == -1)
> +		return -ENOENT;
> +
> +	/* found the rightmost btf_type that matches */
> +	l = lmost;
> +	r = *right;
> +	rmost = -1;
> +	while (l <= r) {
> +		m = l + (r - l) / 2;
> +		t = btf_type_by_id(btf, m);
> +		tname = btf__str_by_offset(btf, t->name_off);
> +		ret = strcmp(tname, name);
> +		if (ret <= 0) {
> +			if (ret == 0)
> +				rmost = m;
> +			l = m + 1;
> +		} else {
> +			r = m - 1;
> +		}
> +	}
>  
> -	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);
> +	*left = lmost;
> +	*right = rmost;
> +	return lmost;
> +}

[...]

Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

Posted by bot+bpf-ci@kernel.org 1 month, 2 weeks ago

> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 3bc03f7fe..5af143044 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;

Where is this field initialized? I searched the entire codebase and
found no assignments to nr_sorted_types. Since struct btf is allocated
with calloc() in btf__new() and other allocation functions, this field
will always be zero.

This means the binary search optimization added below will never execute
because the check at btf_find_type_by_name_kind() tests:

    if (btf->nr_sorted_types) {
        /* binary search */
        ...
    }

With nr_sorted_types always zero, the optimization appears to be
completely non-functional in this commit.

>  	/* if not NULL, points to the base BTF on top of which the current
>  	 * split BTF is based
>  	 */

[ ... ]

> @@ -897,44 +903,134 @@ 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)
> +/*
> + * Find BTF types with matching names within the [left, right] index range.
> + * On success, updates *left and *right to the boundaries of the matching range
> + * and returns the leftmost matching index.
> + */
> +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> +						__s32 *left, __s32 *right)
>  {
> -	__u32 i, nr_types = btf__type_cnt(btf);
> +	const struct btf_type *t;
> +	const char *tname;
> +	__s32 l, r, m, lmost, rmost;
> +	int ret;
> +
> +	/* found the leftmost btf_type that matches */
> +	l = *left;
> +	r = *right;
> +	lmost = -1;
> +	while (l <= r) {
> +		m = l + (r - l) / 2;
> +		t = btf_type_by_id(btf, m);
> +		tname = btf__str_by_offset(btf, t->name_off);
> +		ret = strcmp(tname, name);

Can strcmp() crash with a NULL tname here? btf__str_by_offset() can
return NULL when offset is invalid (see line 1713 in btf.c). The old
code had a NULL check: "if (name && !strcmp(type_name, name))" and the
new linear search path also checks: "if (tname && !strcmp(tname,
type_name))", but this binary search path calls strcmp() directly.

Though currently unreachable due to nr_sorted_types being zero, if that
initialization issue is fixed, this could dereference NULL.

> +		if (ret < 0) {
> +			l = m + 1;
> +		} else {
> +			if (ret == 0)
> +				lmost = m;
> +			r = m - 1;
> +		}
> +	}
> +
> +	if (lmost == -1)
> +		return -ENOENT;
> +
> +	/* found the rightmost btf_type that matches */
> +	l = lmost;
> +	r = *right;
> +	rmost = -1;
> +	while (l <= r) {
> +		m = l + (r - l) / 2;
> +		t = btf_type_by_id(btf, m);
> +		tname = btf__str_by_offset(btf, t->name_off);
> +		ret = strcmp(tname, name);

Same potential NULL dereference issue here.

> +		if (ret <= 0) {
> +			if (ret == 0)
> +				rmost = m;
> +			l = m + 1;
> +		} else {
> +			r = m - 1;
> +		}
> +	}
> +
> +	*left = lmost;
> +	*right = rmost;
> +	return lmost;
> +}

[ ... ]


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/19070905166

[RFC PATCH v4 1/7] libbpf: Extract BTF type remapping logic into helper function
[RFC PATCH v4 2/7] libbpf: Add BTF permutation support for type reordering
[RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF
[RFC PATCH v4 4/7] libbpf: Implement lazy sorting validation for binary search optimization
[RFC PATCH v4 5/7] btf: Optimize type lookup with binary search
[RFC PATCH v4 6/7] btf: Add lazy sorting validation for binary search
[RFC PATCH v4 7/7] selftests/bpf: Add test cases for btf__permute functionality