linux-kernel - Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation for binary search optimization

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: <CAErzpmsOXDe++K4sPhT=KOaumZ4HNP-cNidFaLSt9fr1tRzDKg@mail.gmail.com>
Date: Tue, 25 Nov 2025 18:53:29 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Eduard Zingerman <eddyz87@...il.com>
Cc: Andrii Nakryiko <andrii.nakryiko@...il.com>, ast@...nel.org, zhangxiaoqin@...omi.com, 
	linux-kernel@...r.kernel.org, bpf@...r.kernel.org, 
	Donglin Peng <pengdonglin@...omi.com>, Alan Maguire <alan.maguire@...cle.com>, 
	Song Liu <song@...nel.org>
Subject: Re: [RFC PATCH v7 5/7] libbpf: Implement BTF type sorting validation
 for binary search optimization

On Tue, Nov 25, 2025 at 2:16 AM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Sat, 2025-11-22 at 23:45 +0800, Donglin Peng wrote:
> > On Sat, Nov 22, 2025 at 5:05 PM Eduard Zingerman <eddyz87@...il.com> wrote:
> > >
> > > On Sat, 2025-11-22 at 00:50 -0800, Eduard Zingerman wrote:
> > >
> > > [...]
> > >
> > > > > Thanks. I’ve looked into find_btf_percpu_datasec and we can’t use
> > > > > btf_find_by_name_kind here because the search scope differs. For
> > > > > a module BTF, find_btf_percpu_datasec only searches within the
> > > > > module’s own BTF, whereas btf_find_by_name_kind prioritizes
> > > > > searching the base BTF first. Thus, placing named types ahead is
> > > > > more effective here. Besides, I found that the '.data..percpu' named
> > > > > type will be placed at [1] for vmlinux BTF because the prefix '.' is
> > > > > smaller than any letter, so the linear search only requires one loop to
> > > > > locate it. However, if we put named types at the end, it will need more
> > > > > than 60,000 loops..
> > > >
> > > > But this can be easily fixed if a variant of btf_find_by_name_kind()
> > > > is provided that looks for a match only in a specific BTF. Or accepts
> > > > a start id parameter.
> > >
> > > Also, I double checked, and for my vmlinux the id for '.data..percpu'
> > > section is 110864, the last id of all. So, having all anonymous types
> > > in front does not change status-quo compared to current implementation.
> >
> > Yes. If types are sorted alphabetically, the '.data..percpu' section will
> > have ID 1 in vmlinux BTF. In this case, linear search performance is
> > optimal when named types are placed ahead of anonymous types.
> >
> > I would like to understand the benefits of having anonymous types at the
> > front of named types.
>
> This will allow using strcmp() instead of btf_compare_type_names(),
> which we have to copy both in kernel and in libbpf. Reducing the code
> size and cognitive load.

Thanks, I will fix it in the next version.