linux-kernel - 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: <aci6pn57bqjfcshbak7ekxb7zr5zz72u3rxyu4zbp5w3mvljx2@b4rn2e4rb4rl>
Date: Thu, 17 Oct 2024 15:10:50 +0800
From: Shung-Hsi Yu <shung-hsi.yu@...e.com>
To: Kuan-Wei Chiu <visitorckw@...il.com>, bpf@...r.kernel.org, 
	Eduard Zingerman <eddyz87@...il.com>
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>
Subject: Using union-find in BPF verifier (was: Enhance union-find with KUnit
 tests and optimization improvements)

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.

In BPF verifier we do the following to identify the outermost loop in a
BPF program.

	static struct bpf_verifier_state *get_loop_entry(struct bpf_verifier_state *st)
	{
		struct bpf_verifier_state *topmost = st->loop_entry, *old;

		while (topmost && topmost->loop_entry && topmost != topmost->loop_entry)
			topmost = topmost->loop_entry;

		while (st && st->loop_entry != topmost) {
			old = st->loop_entry;
			st->loop_entry = topmost;
			st = old;
		}
		return topmost;
	}

	static void update_loop_entry(struct bpf_verifier_state *cur, struct bpf_verifier_state *hdr)
	{
		struct bpf_verifier_state *cur1, *hdr1;

		cur1 = get_loop_entry(cur) ?: cur;
		hdr1 = get_loop_entry(hdr) ?: hdr;

		if (hdr1->branches && hdr1->dfs_depth <= cur1->dfs_depth) {
			cur->loop_entry = hdr;
			hdr->used_as_loop_entry = true;
		}
	}

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.

---

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).

	r0 = random();
	r1 = r0; /* r1 is the same as r0 */

However it doesn't seem like union-find would be as useful here, because
1. registers might later be reassigned
2. in addition to equivalence, BPF verifier also track whether content
of two register differs by some value (see sync_linked_regs()).

	r0 = random();
	r1 = r0 + 1; /* r1 differs r0 by 1 */

So maybe not here, at least I don't see how union-find can make things
simpler. But data structure and algorithm really isn't my strength and
I'm happy to be proven wrong.

Shung-Hsi