linux-kernel - Re: Using union-find in BPF verifier (was: Enhance union-find with KUnit tests and optimization improvements)

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: <CAADnVQLSU5WDkjtFVLYqj8+AOUCz-Pi6v4VaexviQPy7DKtXDw@mail.gmail.com>
Date: Mon, 21 Oct 2024 10:14:39 -0700
From: Alexei Starovoitov <alexei.starovoitov@...il.com>
To: Eduard Zingerman <eddyz87@...il.com>
Cc: Shung-Hsi Yu <shung-hsi.yu@...e.com>, Kuan-Wei Chiu <visitorckw@...il.com>, 
	bpf <bpf@...r.kernel.org>, Tejun Heo <tj@...nel.org>, xavier_qy@....com, 
	Waiman Long <longman@...hat.com>, Zefan Li <lizefan.x@...edance.com>, 
	Johannes Weiner <hannes@...xchg.org>, Michal Koutný <mkoutny@...e.com>, 
	Andrew Morton <akpm@...ux-foundation.org>, jserv@...s.ncku.edu.tw, 
	LKML <linux-kernel@...r.kernel.org>, 
	"open list:CONTROL GROUP (CGROUP)" <cgroups@...r.kernel.org>, Christoph Hellwig <hch@...radead.org>, 
	Alexei Starovoitov <ast@...nel.org>, Andrii Nakryiko <andrii@...nel.org>, Mykola Lysenko <mykolal@...com>
Subject: Re: Using union-find in BPF verifier (was: Enhance union-find with
 KUnit tests and optimization improvements)

On Thu, Oct 17, 2024 at 1:09 AM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Thu, 2024-10-17 at 15:10 +0800, Shung-Hsi Yu wrote:
> > Michal mentioned lib/union_find.c during a discussion. I think we may
> > have a use for in BPF verifier (kernel/bpf/verifier.c) that could
> > further simplify the code. Eduard (who wrote the code shown below)
> > probably would have a better idea.
> >
> > On Mon, Oct 07, 2024 at 06:19:10AM GMT, Tejun Heo wrote:
> > > On Mon, Oct 07, 2024 at 11:28:27PM +0800, Kuan-Wei Chiu wrote:
> > > > This patch series adds KUnit tests for the union-find implementation
> > > > and optimizes the path compression in the uf_find() function to achieve
> > > > a lower tree height and improved efficiency. Additionally, it modifies
> > > > uf_union() to return a boolean value indicating whether a merge
> > > > occurred, enhancing the process of calculating the number of groups in
> > > > the cgroup cpuset.
> > >
> > > I'm not necessarily against the patchset but this probably is becoming too
> > > much polishing for something which is only used by cpuset in a pretty cold
> > > path. It probably would be a good idea to concentrate on finding more use
> > > cases.
>
> Hi Shung-Hsi,
>
> [...]
>
> > Squinting a bit get_loop_entry() looks quite like uf_find() and
> > update_loop_entry() looks quite link uf_union(). So perhaps we could get
> > a straight-forward conversion here.
>
> I'll reply tomorrow, need to sleep on it.

I don't like the idea.
Let's keep get_loop_entry/update_loop_entry as-is.