[PATCH v2 0/6] Enhance union-find with KUnit tests and optimization improvements

[PATCH v2 0/6] Enhance union-find with KUnit tests and optimization improvements

[Kuan-Wei Chiu]

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

[PATCH v2 1/6] lib/union_find: Add EXPORT_SYMBOL() for uf_find() and uf_union()

[Kuan-Wei Chiu]

Add EXPORT_SYMBOL() for the uf_find() and uf_union() functions to allow
kernel modules, including the KUnit tests for the union-find data
structure, to use these functions. This enhances the usability of the
union-find implementation in a modular context, facilitating easier
testing and integration.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 lib/union_find.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/lib/union_find.c b/lib/union_find.c
index 413b0f8adf7a..c9fd30b8059c 100644
--- a/lib/union_find.c
+++ b/lib/union_find.c
@@ -1,4 +1,5 @@
 // SPDX-License-Identifier: GPL-2.0
+#include <linux/export.h>
 #include <linux/union_find.h>
 
 /**
@@ -21,6 +22,7 @@ struct uf_node *uf_find(struct uf_node *node)
 	}
 	return node;
 }
+EXPORT_SYMBOL(uf_find);
 
 /**
  * uf_union - Merge two sets, using union by rank
@@ -47,3 +49,4 @@ void uf_union(struct uf_node *node1, struct uf_node *node2)
 		root1->rank++;
 	}
 }
+EXPORT_SYMBOL(uf_union);
-- 
2.34.1

Re: [PATCH v2 1/6] lib/union_find: Add EXPORT_SYMBOL() for uf_find() and uf_union()

[Waiman Long]

On 10/7/24 11:28 AM, Kuan-Wei Chiu wrote:
> Add EXPORT_SYMBOL() for the uf_find() and uf_union() functions to allow
> kernel modules, including the KUnit tests for the union-find data
> structure, to use these functions. This enhances the usability of the
> union-find implementation in a modular context, facilitating easier
> testing and integration.
>
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
>   lib/union_find.c | 3 +++
>   1 file changed, 3 insertions(+)
>
> diff --git a/lib/union_find.c b/lib/union_find.c
> index 413b0f8adf7a..c9fd30b8059c 100644
> --- a/lib/union_find.c
> +++ b/lib/union_find.c
> @@ -1,4 +1,5 @@
>   // SPDX-License-Identifier: GPL-2.0
> +#include <linux/export.h>
>   #include <linux/union_find.h>
>   
>   /**
> @@ -21,6 +22,7 @@ struct uf_node *uf_find(struct uf_node *node)
>   	}
>   	return node;
>   }
> +EXPORT_SYMBOL(uf_find);
>   
>   /**
>    * uf_union - Merge two sets, using union by rank
> @@ -47,3 +49,4 @@ void uf_union(struct uf_node *node1, struct uf_node *node2)
>   		root1->rank++;
>   	}
>   }
> +EXPORT_SYMBOL(uf_union);

BTW, we don't need to export these functions until the time a kernel 
module starts to use it. That is the usual rule.

Cheers,
Longman

[PATCH v2 2/6] lib/union_find: Change uf_union() return type to bool

[Kuan-Wei Chiu]

Modify the uf_union() function to return a bool indicating whether a
merge occurred. If the two nodes belong to the same set, the function
returns false, indicating no merge took place. Otherwise, it completes
the merge and returns true. This change allows the caller to easily
determine the number of distinct groups by tracking successful merges,
enhancing the usability of the union-find implementation.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 include/linux/union_find.h | 2 +-
 lib/union_find.c           | 8 ++++++--
 2 files changed, 7 insertions(+), 3 deletions(-)

diff --git a/include/linux/union_find.h b/include/linux/union_find.h
index cfd49263c138..45c1a6fc6574 100644
--- a/include/linux/union_find.h
+++ b/include/linux/union_find.h
@@ -36,6 +36,6 @@ static inline void uf_node_init(struct uf_node *node)
 struct uf_node *uf_find(struct uf_node *node);
 
 /* Merge two intersecting nodes */
-void uf_union(struct uf_node *node1, struct uf_node *node2);
+bool uf_union(struct uf_node *node1, struct uf_node *node2);
 
 #endif /* __LINUX_UNION_FIND_H */
diff --git a/lib/union_find.c b/lib/union_find.c
index c9fd30b8059c..a20678da0220 100644
--- a/lib/union_find.c
+++ b/lib/union_find.c
@@ -31,14 +31,16 @@ EXPORT_SYMBOL(uf_find);
  *
  * This function merges the sets containing node1 and node2, by comparing
  * the ranks to keep the tree balanced.
+ *
+ * Returns true if the sets were merged, false if they were already in the same set.
  */
-void uf_union(struct uf_node *node1, struct uf_node *node2)
+bool uf_union(struct uf_node *node1, struct uf_node *node2)
 {
 	struct uf_node *root1 = uf_find(node1);
 	struct uf_node *root2 = uf_find(node2);
 
 	if (root1 == root2)
-		return;
+		return false;
 
 	if (root1->rank < root2->rank) {
 		root1->parent = root2;
@@ -48,5 +50,7 @@ void uf_union(struct uf_node *node1, struct uf_node *node2)
 		root2->parent = root1;
 		root1->rank++;
 	}
+
+	return true;
 }
 EXPORT_SYMBOL(uf_union);
-- 
2.34.1

[PATCH v2 3/6] lib: Add KUnit tests for union-find implementation

[Kuan-Wei Chiu]

Introduce a KUnit test suite for the union-find data structure. The
tests verify the functionality and correctness of the union and find
operations, including edge cases such as handling duplicate unions.
The addition of KUnit tests enhances the robustness of the union-find
implementation by ensuring its correctness under various scenarios.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 MAINTAINERS            |  1 +
 lib/Kconfig.debug      | 12 +++++++
 lib/Makefile           |  1 +
 lib/union_find_kunit.c | 74 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 88 insertions(+)
 create mode 100644 lib/union_find_kunit.c

diff --git a/MAINTAINERS b/MAINTAINERS
index a097afd76ded..e503802c1549 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23801,6 +23801,7 @@ F:	Documentation/core-api/union_find.rst
 F:	Documentation/translations/zh_CN/core-api/union_find.rst
 F:	include/linux/union_find.h
 F:	lib/union_find.c
+F:	lib/union_find_kunit.c
 
 UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
 R:	Alim Akhtar <alim.akhtar@samsung.com>
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 7315f643817a..f8c09dd0590b 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2841,6 +2841,18 @@ config SIPHASH_KUNIT_TEST
 	  This is intended to help people writing architecture-specific
 	  optimized versions.  If unsure, say N.
 
+config UNION_FIND_KUNIT_TEST
+	tristate "KUnit Test for Union find"
+	depends on KUNIT
+	default KUNIT_ALL_TESTS
+	help
+	  This option enables the KUnit tests for the union-find data structure.
+	  These tests verify the functionality and correctness of the union-find
+	  implementation, including union and find operations, as well as
+	  edge cases such as handling of duplicate unions.
+
+	  If unsure, say N
+
 config USERCOPY_KUNIT_TEST
 	tristate "KUnit Test for user/kernel boundary protections"
 	depends on KUNIT
diff --git a/lib/Makefile b/lib/Makefile
index 773adf88af41..03da92faf9b8 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -388,6 +388,7 @@ CFLAGS_fortify_kunit.o += $(call cc-disable-warning, stringop-truncation)
 CFLAGS_fortify_kunit.o += $(DISABLE_STRUCTLEAK_PLUGIN)
 obj-$(CONFIG_FORTIFY_KUNIT_TEST) += fortify_kunit.o
 obj-$(CONFIG_SIPHASH_KUNIT_TEST) += siphash_kunit.o
+obj-$(CONFIG_UNION_FIND_KUNIT_TEST) += union_find_kunit.o
 obj-$(CONFIG_USERCOPY_KUNIT_TEST) += usercopy_kunit.o
 
 obj-$(CONFIG_GENERIC_LIB_DEVMEM_IS_ALLOWED) += devmem_is_allowed.o
diff --git a/lib/union_find_kunit.c b/lib/union_find_kunit.c
new file mode 100644
index 000000000000..9bdf9e0e455e
--- /dev/null
+++ b/lib/union_find_kunit.c
@@ -0,0 +1,74 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+#include <kunit/test.h>
+#include <linux/module.h>
+#include <linux/union_find.h>
+
+static void test_union_and_find(struct kunit *test)
+{
+	struct uf_node node1, node2, node3;
+	struct uf_node *root1, *root2, *root3;
+	bool merged;
+
+	/* Initialize the nodes */
+	uf_node_init(&node1);
+	uf_node_init(&node2);
+	uf_node_init(&node3);
+
+	/* Check the initial parent and rank */
+	KUNIT_ASSERT_PTR_EQ(test, uf_find(&node1), &node1);
+	KUNIT_ASSERT_PTR_EQ(test, uf_find(&node2), &node2);
+	KUNIT_ASSERT_PTR_EQ(test, uf_find(&node3), &node3);
+	KUNIT_ASSERT_EQ(test, node1.rank, 0);
+	KUNIT_ASSERT_EQ(test, node2.rank, 0);
+	KUNIT_ASSERT_EQ(test, node3.rank, 0);
+
+	/* Union node1 and node2 */
+	merged = uf_union(&node1, &node2);
+	KUNIT_ASSERT_TRUE(test, merged);
+
+	/* Assert that one of the nodes is now the parent of the other */
+	root1 = uf_find(&node1);
+	root2 = uf_find(&node2);
+	KUNIT_ASSERT_PTR_EQ(test, root1, root2);
+
+	/* Check rank after the first union */
+	if (root1 == &node1) {
+		KUNIT_ASSERT_EQ(test, node1.rank, 1);
+		KUNIT_ASSERT_EQ(test, node2.rank, 0);
+	} else {
+		KUNIT_ASSERT_EQ(test, node1.rank, 0);
+		KUNIT_ASSERT_EQ(test, node2.rank, 1);
+	}
+
+	/* Attempt to union node1 and node2 again and check for false return */
+	merged = uf_union(&node1, &node2);
+	KUNIT_ASSERT_FALSE(test, merged);
+
+	/* Union node3 with the result of the previous union (node1 and node2) */
+	uf_union(&node1, &node3);
+
+	/* Assert that all nodes have the same root */
+	root3 = uf_find(&node3);
+	KUNIT_ASSERT_PTR_EQ(test, root1, root3);
+
+	/* Check rank after the second union */
+	KUNIT_ASSERT_EQ(test, root1->rank, 1);
+	KUNIT_ASSERT_EQ(test, node3.rank, 0);
+}
+
+static struct kunit_case union_find_test_cases[] = {
+	KUNIT_CASE(test_union_and_find),
+	{}
+};
+
+static struct kunit_suite union_find_test_suite = {
+	.name = "union_find_test_suite",
+	.test_cases = union_find_test_cases,
+};
+
+kunit_test_suites(&union_find_test_suite);
+
+MODULE_AUTHOR("Kuan-Wei Chiu <visitorckw@gmail.com>");
+MODULE_DESCRIPTION("Union-find KUnit test suite");
+MODULE_LICENSE("GPL");
-- 
2.34.1

[PATCH v2 4/6] lib/union_find: Optimize uf_find() with enhanced path compression

[Kuan-Wei Chiu]

Optimize the uf_find() function to enhance its efficiency by
implementing a more effective path compression strategy. The original
implementation only updated the parent pointer of the current node to
its grandparent, resulting in a relatively shallow tree.

In the updated version, once the root of the node is identified, all
nodes along the search path are updated to directly point to the root.
This change minimizes the height of the tree and improves the
efficiency for subsequent find operations, providing better performance
for the union-find data structure.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
Note: Tested with the KUnit tests introduced in the previous patch.

 lib/union_find.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

diff --git a/lib/union_find.c b/lib/union_find.c
index a20678da0220..d2b79065cbc8 100644
--- a/lib/union_find.c
+++ b/lib/union_find.c
@@ -13,14 +13,19 @@
  */
 struct uf_node *uf_find(struct uf_node *node)
 {
+	struct uf_node *root = node;
 	struct uf_node *parent;
 
-	while (node->parent != node) {
+	while (root->parent != root)
+		root = root->parent;
+
+	while (node->parent != root) {
 		parent = node->parent;
-		node->parent = parent->parent;
+		node->parent = root;
 		node = parent;
 	}
-	return node;
+
+	return root;
 }
 EXPORT_SYMBOL(uf_find);
 
-- 
2.34.1

[PATCH v2 5/6] cgroup/cpuset: Optimize domain counting using updated uf_union()

[Kuan-Wei Chiu]

Improve the efficiency of calculating the total number of scheduling
domains by using the updated uf_union function, which now returns a
boolean to indicate if a merge occurred. Previously, an additional loop
was needed to count root nodes for distinct groups. With this change,
each successful merge reduces the domain count (ndoms) directly,
eliminating the need for the final loop and enhancing performance.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
Note: Tested with test_cpuset_prs.sh

Side note: I know this optimization provides limited efficiency
improvements in this case, but since the union-find code is in the
library and other users may need group counting in the future, and
the required code change is minimal, I think it's still worthwhile.

 kernel/cgroup/cpuset.c | 10 +++-------
 1 file changed, 3 insertions(+), 7 deletions(-)

diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index a4dd285cdf39..5e9301550d43 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -817,6 +817,8 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	if (root_load_balance && (csn == 1))
 		goto single_root_domain;
 
+	ndoms = csn;
+
 	for (i = 0; i < csn; i++)
 		uf_node_init(&csa[i]->node);
 
@@ -829,17 +831,11 @@ static int generate_sched_domains(cpumask_var_t **domains,
 				 * partition root cpusets.
 				 */
 				WARN_ON_ONCE(cgrpv2);
-				uf_union(&csa[i]->node, &csa[j]->node);
+				ndoms -= uf_union(&csa[i]->node, &csa[j]->node);
 			}
 		}
 	}
 
-	/* Count the total number of domains */
-	for (i = 0; i < csn; i++) {
-		if (uf_find(&csa[i]->node) == &csa[i]->node)
-			ndoms++;
-	}
-
 	/*
 	 * Now we know how many domains to create.
 	 * Convert <csn, csa> to <ndoms, doms> and populate cpu masks.
-- 
2.34.1

Re: [PATCH v2 5/6] cgroup/cpuset: Optimize domain counting using updated uf_union()

[Waiman Long]

On 10/7/24 11:28 AM, Kuan-Wei Chiu wrote:
> Improve the efficiency of calculating the total number of scheduling
> domains by using the updated uf_union function, which now returns a
> boolean to indicate if a merge occurred. Previously, an additional loop
> was needed to count root nodes for distinct groups. With this change,
> each successful merge reduces the domain count (ndoms) directly,
> eliminating the need for the final loop and enhancing performance.
>
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
> Note: Tested with test_cpuset_prs.sh
>
> Side note: I know this optimization provides limited efficiency
> improvements in this case, but since the union-find code is in the
> library and other users may need group counting in the future, and
> the required code change is minimal, I think it's still worthwhile.
>
>   kernel/cgroup/cpuset.c | 10 +++-------
>   1 file changed, 3 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
> index a4dd285cdf39..5e9301550d43 100644
> --- a/kernel/cgroup/cpuset.c
> +++ b/kernel/cgroup/cpuset.c
> @@ -817,6 +817,8 @@ static int generate_sched_domains(cpumask_var_t **domains,
>   	if (root_load_balance && (csn == 1))
>   		goto single_root_domain;
>   
> +	ndoms = csn;
> +
>   	for (i = 0; i < csn; i++)
>   		uf_node_init(&csa[i]->node);
>   
> @@ -829,17 +831,11 @@ static int generate_sched_domains(cpumask_var_t **domains,
>   				 * partition root cpusets.
>   				 */
>   				WARN_ON_ONCE(cgrpv2);
> -				uf_union(&csa[i]->node, &csa[j]->node);
> +				ndoms -= uf_union(&csa[i]->node, &csa[j]->node);

You are taking the implicit assumption that a boolean true is casted to 
int 1. That is the usual practice, but it is not part of the C standard 
itself though it is for C++.  I will be more comfortable with the "if 
(cond) ndoms++" form. It will also be more clear.

Cheers,
Longman

Re: [PATCH v2 5/6] cgroup/cpuset: Optimize domain counting using updated uf_union()

[Kuan-Wei Chiu]

On Tue, Oct 08, 2024 at 10:02:23AM -0400, Waiman Long wrote:
> On 10/7/24 11:28 AM, Kuan-Wei Chiu wrote:
> > Improve the efficiency of calculating the total number of scheduling
> > domains by using the updated uf_union function, which now returns a
> > boolean to indicate if a merge occurred. Previously, an additional loop
> > was needed to count root nodes for distinct groups. With this change,
> > each successful merge reduces the domain count (ndoms) directly,
> > eliminating the need for the final loop and enhancing performance.
> > 
> > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> > ---
> > Note: Tested with test_cpuset_prs.sh
> > 
> > Side note: I know this optimization provides limited efficiency
> > improvements in this case, but since the union-find code is in the
> > library and other users may need group counting in the future, and
> > the required code change is minimal, I think it's still worthwhile.
> > 
> >   kernel/cgroup/cpuset.c | 10 +++-------
> >   1 file changed, 3 insertions(+), 7 deletions(-)
> > 
> > diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
> > index a4dd285cdf39..5e9301550d43 100644
> > --- a/kernel/cgroup/cpuset.c
> > +++ b/kernel/cgroup/cpuset.c
> > @@ -817,6 +817,8 @@ static int generate_sched_domains(cpumask_var_t **domains,
> >   	if (root_load_balance && (csn == 1))
> >   		goto single_root_domain;
> > +	ndoms = csn;
> > +
> >   	for (i = 0; i < csn; i++)
> >   		uf_node_init(&csa[i]->node);
> > @@ -829,17 +831,11 @@ static int generate_sched_domains(cpumask_var_t **domains,
> >   				 * partition root cpusets.
> >   				 */
> >   				WARN_ON_ONCE(cgrpv2);
> > -				uf_union(&csa[i]->node, &csa[j]->node);
> > +				ndoms -= uf_union(&csa[i]->node, &csa[j]->node);
> 
> You are taking the implicit assumption that a boolean true is casted to int
> 1. That is the usual practice, but it is not part of the C standard itself
> though it is for C++.  I will be more comfortable with the "if (cond)
> ndoms++" form. It will also be more clear.
>
Thanks for your feedback. I appreciate your point regarding the implicit
casting of boolean values. And changing the code to:

if (uf_union(&csa[i]->node, &csa[j]->node))
    --ndoms;

would also enhance clarity and readability.

Would you like me to resend v3? I'm asking because I suspect Tejun may
want to see more user cases before considering such optimizations.

Regards,
Kuan-Wei

Re: [PATCH v2 5/6] cgroup/cpuset: Optimize domain counting using updated uf_union()

[Waiman Long]

On 10/8/24 12:45 PM, Kuan-Wei Chiu wrote:
> On Tue, Oct 08, 2024 at 10:02:23AM -0400, Waiman Long wrote:
>> On 10/7/24 11:28 AM, Kuan-Wei Chiu wrote:
>>> Improve the efficiency of calculating the total number of scheduling
>>> domains by using the updated uf_union function, which now returns a
>>> boolean to indicate if a merge occurred. Previously, an additional loop
>>> was needed to count root nodes for distinct groups. With this change,
>>> each successful merge reduces the domain count (ndoms) directly,
>>> eliminating the need for the final loop and enhancing performance.
>>>
>>> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
>>> ---
>>> Note: Tested with test_cpuset_prs.sh
>>>
>>> Side note: I know this optimization provides limited efficiency
>>> improvements in this case, but since the union-find code is in the
>>> library and other users may need group counting in the future, and
>>> the required code change is minimal, I think it's still worthwhile.
>>>
>>>    kernel/cgroup/cpuset.c | 10 +++-------
>>>    1 file changed, 3 insertions(+), 7 deletions(-)
>>>
>>> diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
>>> index a4dd285cdf39..5e9301550d43 100644
>>> --- a/kernel/cgroup/cpuset.c
>>> +++ b/kernel/cgroup/cpuset.c
>>> @@ -817,6 +817,8 @@ static int generate_sched_domains(cpumask_var_t **domains,
>>>    	if (root_load_balance && (csn == 1))
>>>    		goto single_root_domain;
>>> +	ndoms = csn;
>>> +
>>>    	for (i = 0; i < csn; i++)
>>>    		uf_node_init(&csa[i]->node);
>>> @@ -829,17 +831,11 @@ static int generate_sched_domains(cpumask_var_t **domains,
>>>    				 * partition root cpusets.
>>>    				 */
>>>    				WARN_ON_ONCE(cgrpv2);
>>> -				uf_union(&csa[i]->node, &csa[j]->node);
>>> +				ndoms -= uf_union(&csa[i]->node, &csa[j]->node);
>> You are taking the implicit assumption that a boolean true is casted to int
>> 1. That is the usual practice, but it is not part of the C standard itself
>> though it is for C++.  I will be more comfortable with the "if (cond)
>> ndoms++" form. It will also be more clear.
>>
> Thanks for your feedback. I appreciate your point regarding the implicit
> casting of boolean values. And changing the code to:
>
> if (uf_union(&csa[i]->node, &csa[j]->node))
>      --ndoms;
>
> would also enhance clarity and readability.
>
> Would you like me to resend v3? I'm asking because I suspect Tejun may
> want to see more user cases before considering such optimizations.

I agreed with Tejun that union-find performance is not that important 
for the cpuset use case which is also the only use case at the moment. I 
will support a v3 if you can find another use case where performance is 
more important.

Cheers,
Longman

[PATCH v2 6/6] MAINTAINERS: Add Kuan-Wei as co-maintainer for union-find

[Kuan-Wei Chiu]

I'm happy to help maintain and review patches for the union-find data
structure. Add myself as a union-find maintainer.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 MAINTAINERS | 1 +
 1 file changed, 1 insertion(+)

diff --git a/MAINTAINERS b/MAINTAINERS
index e503802c1549..c3b1a5641765 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23795,6 +23795,7 @@ F:	include/uapi/linux/cdrom.h
 
 UNION-FIND
 M:	Xavier <xavier_qy@163.com>
+M:	Kuan-Wei Chiu <visitorckw@gmail.com>
 L:	linux-kernel@vger.kernel.org
 S:	Maintained
 F:	Documentation/core-api/union_find.rst
-- 
2.34.1

Re: [PATCH v2 0/6] Enhance union-find with KUnit tests and optimization improvements

[Tejun Heo]

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

Re: [PATCH v2 0/6] Enhance union-find with KUnit tests and optimization improvements

[Kuan-Wei Chiu]

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

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

[Shung-Hsi Yu]

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

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

[Eduard Zingerman]

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

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

[Alexei Starovoitov]

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.

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

[Kuan-Wei Chiu]

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

Re: [PATCH v2 0/6] Enhance union-find with KUnit tests and optimization improvements

[Christoph Hellwig]

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.

Re: [PATCH v2 0/6] Enhance union-find with KUnit tests and optimization improvements

[Kuan-Wei Chiu]

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

Re: [PATCH v2 0/6] Enhance union-find with KUnit tests and optimization improvements

[Kuan-Wei Chiu]

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

Re: [PATCH v2 0/6] Enhance union-find with KUnit tests and optimization improvements

[Waiman Long]

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

Re: [PATCH v2 0/6] Enhance union-find with KUnit tests and optimization improvements

[Tejun Heo]

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