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

Message-ID: <af842df1791423386f3aef25f3f94c5b39b5e332.camel@gmail.com>
Date: Thu, 17 Oct 2024 01:08:54 -0700
From: Eduard Zingerman <eddyz87@...il.com>
To: Shung-Hsi Yu <shung-hsi.yu@...e.com>, Kuan-Wei Chiu
 <visitorckw@...il.com>,  bpf@...r.kernel.org
Cc: Tejun Heo <tj@...nel.org>, xavier_qy@....com, longman@...hat.com, 
 lizefan.x@...edance.com, hannes@...xchg.org, mkoutny@...e.com, 
 akpm@...ux-foundation.org, jserv@...s.ncku.edu.tw,
 linux-kernel@...r.kernel.org,  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, 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.

> ---
> 
> Another (comparatively worst) idea is to use it for tracking whether two
> register has the same content (this is currently done with struct
> bpf_reg_state.id).

Given that union-find data structure does not support element deletion
and only accumulates merged groups, for the following code:

  0: r0 = random()
  1: r1 = r0
  2: r0 = random()

It would be necessary to re-build sets of equivalent registers at
instruction (2). I'm not sure about this use case, tbh.

[...]

Thanks,
Eduard