MAINTAINERS | 2 ++ include/linux/union_find.h | 2 +- kernel/cgroup/cpuset.c | 10 ++---- lib/Kconfig.debug | 12 +++++++ lib/Makefile | 1 + lib/union_find.c | 22 +++++++++--- lib/union_find_kunit.c | 74 ++++++++++++++++++++++++++++++++++++++ 7 files changed, 110 insertions(+), 13 deletions(-) create mode 100644 lib/union_find_kunit.c
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. Regards, Kuan-Wei --- Changes in v2: - Modify uf_find() to compare with root instead of node in the while loop - s/Union-Find/union-find/ - Add myself to MAINTAINERS v1: https://lore.kernel.org/lkml/20241005214938.2147393-1-visitorckw@gmail.com/ Kuan-Wei Chiu (6): lib/union_find: Add EXPORT_SYMBOL() for uf_find() and uf_union() lib/union_find: Change uf_union() return type to bool lib: Add KUnit tests for union-find implementation lib/union_find: Optimize uf_find() with enhanced path compression cgroup/cpuset: Optimize domain counting using updated uf_union() MAINTAINERS: Add Kuan-Wei as co-maintainer for union-find MAINTAINERS | 2 ++ include/linux/union_find.h | 2 +- kernel/cgroup/cpuset.c | 10 ++---- lib/Kconfig.debug | 12 +++++++ lib/Makefile | 1 + lib/union_find.c | 22 +++++++++--- lib/union_find_kunit.c | 74 ++++++++++++++++++++++++++++++++++++++ 7 files changed, 110 insertions(+), 13 deletions(-) create mode 100644 lib/union_find_kunit.c -- 2.34.1
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. Given that this fairly special union find code is obly used in the cpuset code, please move the code there rather adding more exports. Even as-is it is bloating every kernel build even without cgroups for no good reason.
On Wed, Oct 09, 2024 at 02:09:51AM -0700, Christoph Hellwig 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. > > Given that this fairly special union find code is obly used in the > cpuset code, please move the code there rather adding more exports. > Even as-is it is bloating every kernel build even without cgroups > for no good reason. > I noticed that it was Michal who originally suggested putting the union-find code to lib/ in an earlier email thread [1]. Before I send a v3 patch moving it to cpuset, I'd like to hear Michal, Tejun, and Waiman’s thoughts on this change. [1]: https://lore.kernel.org/lkml/wu4m2m5igc752s5vrmtsnd7ekaq6opeqdtrzegs7oxlwgypdcx@qhcnow5txxiv/ Regards, Kuan-Wei
On 10/9/24 10:13 AM, Kuan-Wei Chiu wrote: > On Wed, Oct 09, 2024 at 02:09:51AM -0700, Christoph Hellwig 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. >> Given that this fairly special union find code is obly used in the >> cpuset code, please move the code there rather adding more exports. >> Even as-is it is bloating every kernel build even without cgroups >> for no good reason. >> > I noticed that it was Michal who originally suggested putting the > union-find code to lib/ in an earlier email thread [1]. Before I send a v3 > patch moving it to cpuset, I'd like to hear Michal, Tejun, and Waiman’s > thoughts on this change. > > [1]: https://lore.kernel.org/lkml/wu4m2m5igc752s5vrmtsnd7ekaq6opeqdtrzegs7oxlwgypdcx@qhcnow5txxiv/ > > Regards, > Kuan-Wei The current union_find code is pretty small. Putting it there in lib allows it to be used by other kernel subsystems when needed. I believe it should stay in lib. If a slight increase in kernel size is a concern, we can update the Makefile to make its build depend on CONFIG_CPUSETS which can be taken out when it is being used by another kernel subsystem. Cheers, Longman
On Wed, Oct 09, 2024 at 10:53:08AM -0400, Waiman Long wrote: > The current union_find code is pretty small. Putting it there in lib allows > it to be used by other kernel subsystems when needed. I believe it should > stay in lib. If a slight increase in kernel size is a concern, we can update > the Makefile to make its build depend on CONFIG_CPUSETS which can be taken > out when it is being used by another kernel subsystem. Yeah, let's CONFIG it for nwo and see whether there are more use cases. If that doesn't happen, we can fold it back into cpuset. Thanks. -- tejun
On Wed, Oct 09, 2024 at 02:09:51AM -0700, Christoph Hellwig 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. > > Given that this fairly special union find code is obly used in the > cpuset code, please move the code there rather adding more exports. > Even as-is it is bloating every kernel build even without cgroups > for no good reason. > I agree that moving the union-find code to cpuset is a reasonable approach until we have more users. I could submit a v3 to do that. Regards, Kuan-Wei
Hello, 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. Thanks. -- tejun
Hi Tejun, On Mon, Oct 07, 2024 at 06:19:10AM -1000, Tejun Heo wrote: > Hello, > > 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. > I hesitated for a while before sending this patch series, as I was unsure if these optimizations were worthwhile. As you pointed out, it is only used in cpuset and isn't in a performance-critical path. However, since the union-find implementation is placed under lib/, I thought this suggested an expectation of more potential users in the future (otherwise, it might have been placed directly within cpuset). These patches might eventually benefit other users down the line. Additionally, except for the patch that adds kunit tests, the rest involve only small changes of fewer than 10 lines each. That’s why I decided to go ahead and submit them. I agree that these changes would be more meaningful if more users could benefit from them, and I'll try to explore further use cases. I understand maintainers are busy, and if this patch series seems like unnecessary changes, I apologize for any wasted time. Regards, Kuan-Wei
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
On Thu, Oct 17, 2024 at 03:10:50PM +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.
>
> 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.
>
From a quick glance, it seems that there are still some differences
between update_loop_entry() and uf_union(). If we want to use
lib/union_find.c, we would need a new union function to ensure the
merge order, i.e., ensuring that a.parent = b but not b.parent = a.
Additionally, used_as_loop_entry can be replaced with
uf_find(a) == a && a->rank != 1.
However, I'm not entirely sure if this would make the code easier to
understand compared to the current implementation.
Regards,
Kuan-Wei
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
On Thu, Oct 17, 2024 at 1:09 AM Eduard Zingerman <eddyz87@gmail.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.
© 2016 - 2024 Red Hat, Inc.