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
