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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <7c77c74a761486c694eba763f9d0371e5c354d31.camel@gmail.com>
Date: Tue, 04 Nov 2025 17:17:10 -0800
From: Eduard Zingerman <eddyz87@...il.com>
To: Andrii Nakryiko <andrii.nakryiko@...il.com>
Cc: Donglin Peng <dolinux.peng@...il.com>, ast@...nel.org, 
	linux-kernel@...r.kernel.org, bpf@...r.kernel.org, Alan Maguire
	 <alan.maguire@...cle.com>, Song Liu <song@...nel.org>, pengdonglin
	 <pengdonglin@...omi.com>
Subject: Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary
 search for sorted BTF

On Tue, 2025-11-04 at 16:54 -0800, Andrii Nakryiko wrote:
> On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@...il.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.