linux-kernel - Re: [PATCH v5 6/7] btf: Add lazy sorting validation for binary search

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] [day] [month] [year] [list]

Message-ID: <CAErzpmtViehGv3uLMFwv5bnRJi4HJu=wE6an6S0Gv2up3vncgA@mail.gmail.com>
Date: Mon, 10 Nov 2025 09:42:44 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Eduard Zingerman <eddyz87@...il.com>, Alexei Starovoitov <alexei.starovoitov@...il.com>, 
	Andrii Nakryiko <andrii.nakryiko@...il.com>, Ihor Solodrai <ihor.solodrai@...ux.dev>
Cc: bot+bpf-ci@...nel.org, Alexei Starovoitov <ast@...nel.org>, zhangxiaoqin@...omi.com, 
	LKML <linux-kernel@...r.kernel.org>, bpf <bpf@...r.kernel.org>, 
	Alan Maguire <alan.maguire@...cle.com>, Song Liu <song@...nel.org>, 
	pengdonglin <pengdonglin@...omi.com>, Andrii Nakryiko <andrii@...nel.org>, 
	Daniel Borkmann <daniel@...earbox.net>, Martin KaFai Lau <martin.lau@...nel.org>, 
	Yonghong Song <yonghong.song@...ux.dev>, Chris Mason <clm@...a.com>
Subject: Re: [PATCH v5 6/7] btf: Add lazy sorting validation for binary search

On Sat, Nov 8, 2025 at 3:51 AM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Fri, 2025-11-07 at 11:01 -0800, Alexei Starovoitov wrote:
> > On Fri, Nov 7, 2025 at 10:58 AM Eduard Zingerman <eddyz87@...il.com>
> > wrote:
> > >
> > > On Fri, 2025-11-07 at 10:54 -0800, Alexei Starovoitov wrote:
> > >
> > > [...]
> > >
> > > > > > > > @@ -610,7 +674,7 @@ s32 btf_find_by_name_kind(const
> > > > > > > > struct
> > > > > > > > btf
> > > > > > > > *btf, const char *name, u8 kind)
> > > > > > > >                       goto out;
> > > > > > > >       }
> > > > > > > >
> > > > > > > > -     if (btf->nr_sorted_types != BTF_NEED_SORT_CHECK) {
> > > > > > > > +     if (btf_check_sorted((struct btf *)btf)) {
> > > > > > >                                   ^
> > > > > > >
> > > > > > > The const cast here enables the concurrent writes discussed
> > > > > > > above.
> > > > > > > Is
> > > > > > > there a reason to mark the btf parameter as const if we're
> > > > > > > modifying it?
> > > > > >
> > > > > > Hi team, is casting away const an acceptable approach for our
> > > > > > codebase?
> > > > >
> > > > > Casting away const is undefined behaviour, e.g. see paragraph
> > > > > 6.7.3.6
> > > > > N1570 ISO/IEC 9899:201x Programming languages — C.
> > > > >
> > > > > Both of the problems above can be avoided if kernel will do
> > > > > sorted
> > > > > check non-lazily. But Andrii and Alexei seem to like that
> > > > > property.
> > > >
> > > > Ihor is going to move BTF manipulations into resolve_btfid.
> > > > Sorting of BTF should be in resolve_btfid as well.
> > > > This way the build process will guarantee that BTF is sorted
> > > > to the kernel liking. So the kernel doesn't even need to check
> > > > that BTF is sorted.
> > >
> > > This would be great.
> > > Does this imply that module BTFs are sorted too?
> >
> > Yes. The module build is supposed to use the kernel build tree where
> > kernel BTF expectations will match resolve_btfid actions.
> > Just like compiler and config flags should be the same.
>
> There is also program BTF. E.g. btf_find_by_name_kind() is called for
> program BTF in bpf_check_attach_target(). I think it would be fine to
> check program BTF for being sorted at the BTF load time.

[[Resending in plain text format - previous HTML email was rejected]

Thanks for the feedback. Based on the previous discussions, I plan
to implement the following changes in the next version:

1. Modify the btf__permute interface to adopt the ID map approach, as
    suggested by Andrii.

2. Remove the lazy sort check and move the verification to the BTF
    parsing phase. This addresses two concerns: potential race conditions
    with write operations and const-cast issues. The overhead is negligible
     (approximately 1.4ms for vmlinux BTF).

3. Invoke the btf__permute interface to implement BTF sorting in resolve_btfids.

I welcome any further suggestions.

Thanks,
Donglin