Hi all,

Add a Union-Find data structure in library, and use it to to optimize the
merging of cpumasks. It could potentially be used in network configuration
and topology management to manage the connectivity between different devices
or nodes, as well as in managing the merging and lookup operations of certain
complex file clusters or blocks.

To Tejun,
Since union_find operation does not require contiguous physical memory, I
have replaced the previous allocation method with vzalloc.

To Longman,
Based on your patch, the overlapping check and merge operations for cpusets are
skipped in the case of cgroup v2.

Kindly review.

Best Regards,
Xavier

Xavier (2):
  Union-Find: add a new module in kernel library
  cpuset: use Union-Find to optimize the merging of cpumasks

 Documentation/core-api/union_find.rst         | 110 ++++++++++++++++++
 .../zh_CN/core-api/union_find.rst             |  87 ++++++++++++++
 MAINTAINERS                                   |   9 ++
 include/linux/union_find.h                    |  30 +++++
 kernel/cgroup/cpuset.c                        |  97 ++++++---------
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  38 ++++++
 7 files changed, 313 insertions(+), 60 deletions(-)
 create mode 100644 Documentation/core-api/union_find.rst
 create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
 create mode 100644 include/linux/union_find.h
 create mode 100644 lib/union_find.c

-- 
2.45.2

Hello, Xavier.

On Sat, Jun 22, 2024 at 03:14:22PM +0800, Xavier wrote:
> To Tejun,
> Since union_find operation does not require contiguous physical memory, I
> have replaced the previous allocation method with vzalloc.

Oh, that's not what I meant. Sorry about not being clearer. What I was
trying to say was that requiring consecutive allocation whether kzalloc or
vzalloc is unlikely to work for kernel data structures. The reason why I
mentioned vmalloc was because it's easy to end up in sizes that require
vmalloc with consecutive allocations and vmallocs are rather expensive and
not that great - ie. having to use vmalloc may negate the benefits of better
algorithm in most cases.

Skimming the code, there's nothing requiring consecutive allocations. Is
there a reason why this can't follow the usual convention that kernel data
structures follow (e.g. list, rbtree) where allocation is left to the users?

Thanks.

-- 
tejun

Hi Tejun,

I think I understand your point now. I have modified the Union-Find
implementation so that the allocation and deallocation are handled by the
user, providing only the initialization interface. Thanks for your
suggestion.

Kindly review.

Best Regards,
Xavier


Xavier (2):
  Union-Find: add a new module in kernel library
  cpuset: use Union-Find to optimize the merging of cpumasks

 Documentation/core-api/union_find.rst         | 101 ++++++++++++++++++
 .../zh_CN/core-api/union_find.rst             |  86 +++++++++++++++
 MAINTAINERS                                   |   9 ++
 include/linux/union_find.h                    |  24 +++++
 kernel/cgroup/cpuset.c                        |  99 +++++++----------
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  33 ++++++
 7 files changed, 295 insertions(+), 59 deletions(-)
 create mode 100644 Documentation/core-api/union_find.rst
 create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
 create mode 100644 include/linux/union_find.h
 create mode 100644 lib/union_find.c

-- 
2.45.2

Hello, Xavier.

On Sun, Jun 23, 2024 at 10:38:59AM +0800, Xavier wrote:
> I think I understand your point now. I have modified the Union-Find
> implementation so that the allocation and deallocation are handled by the
> user, providing only the initialization interface. Thanks for your
> suggestion.

I recommend spending more time studying the existing data structures. The
pattern is pretty universal. The element is often embedded in a containing
structure. Macros and init methods are provided to initialize the element
along with operations which implement the data structure operations, and
then we use container_of() to obtain the embedding structure. We very rarely
allocate data structure members by themselves.

Also, the cleanup in cpuset seems nice but, if you can think of other use
cases, that'd be great too.

Thanks.

-- 
tejun

Hi Tejun,

Thank you for your suggestion. I agree with your point that it is indeed more
appropriate to place it within the cpuset structure, and I have already made
the modification. Additionally, I looked into the relevant modules of the
kernel, and it seems that the union-find data structure may have optimization
potential in network topology management and the Open vSwitch module. I will
further investigate this in the future.

Kindly review.

Xavier (2):
  Union-Find: add a new module in kernel library
  cpuset: use Union-Find to optimize the merging of cpumasks

 Documentation/core-api/union_find.rst         | 101 ++++++++++++++++++
 .../zh_CN/core-api/union_find.rst             |  86 +++++++++++++++
 MAINTAINERS                                   |   9 ++
 include/linux/union_find.h                    |  24 +++++
 kernel/cgroup/cpuset.c                        |  96 +++++++----------
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  33 ++++++
 7 files changed, 291 insertions(+), 60 deletions(-)
 create mode 100644 Documentation/core-api/union_find.rst
 create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
 create mode 100644 include/linux/union_find.h
 create mode 100644 lib/union_find.c

-- 
2.45.2

This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.

Signed-off-by: Xavier <xavier_qy@163.com>
---
 Documentation/core-api/union_find.rst         | 101 ++++++++++++++++++
 .../zh_CN/core-api/union_find.rst             |  86 +++++++++++++++
 MAINTAINERS                                   |   9 ++
 include/linux/union_find.h                    |  24 +++++
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  33 ++++++
 6 files changed, 254 insertions(+), 1 deletion(-)
 create mode 100644 Documentation/core-api/union_find.rst
 create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
 create mode 100644 include/linux/union_find.h
 create mode 100644 lib/union_find.c

diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst
new file mode 100644
index 0000000000..38d63b16e5
--- /dev/null
+++ b/Documentation/core-api/union_find.rst
@@ -0,0 +1,101 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <xavier_qy@163.com>
+
+What is Union-Find, and what is it used for?
+------------------------------------------------
+
+Union-Find is a data structure used to handle the merging and querying
+of disjoint sets. The primary operations supported by Union-Find are:
+
+	Initialization: Resetting each element as an individual set, with
+		each set's initial parent node pointing to itself.
+	Find: Determine which set a particular element belongs to, usually by
+		returning a “representative element” of that set. This operation
+		is used to check if two elements are in the same set.
+	Union: Merge two sets into one.
+
+As a data structure used to maintain sets (groups), Union-Find is commonly
+utilized to solve problems related to offline queries, dynamic connectivity,
+and graph theory. It is also a key component in Kruskal's algorithm for
+computing the minimum spanning tree, which is crucial in scenarios like
+network routing. Consequently, Union-Find is widely referenced. Additionally,
+Union-Find has applications in symbolic computation, register allocation,
+and more.
+
+Space Complexity: O(n), where n is the number of nodes.
+
+Time Complexity: Using path compression can reduce the time complexity of
+the find operation, and using union by rank can reduce the time complexity
+of the union operation. These optimizations reduce the average time
+complexity of each find and union operation to O(α(n)), where α(n) is the
+inverse Ackermann function. This can be roughly considered a constant time
+complexity for practical purposes.
+
+This document covers use of the Linux union-find implementation.  For more
+information on the nature and implementation of Union-Find,  see:
+
+  Wikipedia entry on union-find
+    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+Linux implementation of union-find
+-----------------------------------
+
+Linux's union-find implementation resides in the file "lib/union_find.c".
+To use it, "#include <linux/union_find.h>".
+
+The Union-Find data structure is defined as follows::
+
+	struct uf_node {
+		struct uf_node *parent;
+		unsigned int rank;
+	};
+
+In this structure, parent points to the parent node of the current node.
+The rank field represents the height of the current tree. During a union
+operation, the tree with the smaller rank is attached under the tree with the
+larger rank to maintain balance.
+
+Initializing Union-Find
+--------------------
+
+When initializing the Union-Find data structure, a single pointer to the
+Union-Find instance needs to be passed. Initialize the parent pointer to point
+to itself and set the rank to 0.
+Example::
+
+	struct uf_node *my_node = vzalloc(sizeof(struct uf_node));
+	uf_nodes_init(my_node);
+
+Find the Root Node of Union-Find
+--------------------------------
+
+This operation is mainly used to determine whether two nodes belong to the same
+set in the Union-Find. If they have the same root, they are in the same set.
+During the find operation, path compression is performed to improve the
+efficiency of subsequent find operations.
+Example::
+
+	int connected;
+	struct uf_node *root1 = uf_find(&my_node[0]);
+	struct uf_node *root2 = uf_find(&my_node[1]);
+	if (root1 == root2)
+		connected = 1;
+	else
+		connected = 0;
+
+Union Two Sets in Union-Find
+----------------------------
+
+To union two sets in the Union-Find, you first find their respective root nodes
+and then link the smaller node to the larger node based on the rank of the root
+nodes.
+Example::
+
+	uf_union(&my_node[0], &my_node[1]);
diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Documentation/translations/zh_CN/core-api/union_find.rst
new file mode 100644
index 0000000000..e1b5ae88da
--- /dev/null
+++ b/Documentation/translations/zh_CN/core-api/union_find.rst
@@ -0,0 +1,86 @@
+.. SPDX-License-Identifier: GPL-2.0
+.. include:: ../disclaimer-zh_CN.rst
+
+:Original: Documentation/core-api/union_find.rst
+
+===========================
+Linux中的并查集（Union-Find）
+===========================
+
+
+:日期: 2024年6月21日
+:作者: Xavier <xavier_qy@163.com>
+
+何为并查集，它有什么用？
+---------------------
+
+并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：
+	初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身
+	查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为
+		了判断两个元素是否在同一个集合之中。
+	合并：将两个集合合并为一个。
+
+并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和
+图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在
+网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分
+配等方面也有应用。
+
+空间复杂度: O(n)，n为节点数。
+
+时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的
+时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿
+克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。
+
+本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：
+
+  维基百科并查集词条
+    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+并查集的Linux实现
+----------------
+
+Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需要
+“#include <linux/union_find.h>”。
+
+并查集的数据结构定义如下::
+
+	struct uf_node {
+		struct uf_node *parent;
+		unsigned int rank;
+	};
+其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大
+的节点下面以增加平衡性。
+
+初始化并查集
+---------
+
+初始化并查集时需要传入并查集实例的一个指针。初始化时，parent 指针指向自身，rank 设置
+为 0。
+示例::
+
+	struct uf_node *my_node = vzalloc(sizeof(struct uf_node));
+	uf_nodes_init(my_node);
+
+查找并查集的根节点
+----------------
+
+主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中
+会对路径进行压缩，提高后续查找效率。
+示例::
+
+	int connected;
+	struct uf_node *root1 = uf_find(&my_node[0]);
+	struct uf_node *root2 = uf_find(&my_node[1]);
+	if (root1 == root2)
+		connected = 1;
+	else
+		connected = 0;
+
+合并两个并查集
+-------------
+
+对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的
+节点连接到大的节点下面。
+示例::
+
+	uf_union(&my_node[0], &my_node[1]);
diff --git a/MAINTAINERS b/MAINTAINERS
index 2ca8f35dfe..16171dbca3 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23051,6 +23051,15 @@ F:	drivers/cdrom/cdrom.c
 F:	include/linux/cdrom.h
 F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <xavier_qy@163.com>
+L:	linux-kernel@vger.kernel.org
+S:	Maintained
+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
+
 UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
 R:	Alim Akhtar <alim.akhtar@samsung.com>
 R:	Avri Altman <avri.altman@wdc.com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..56571c93a5
--- /dev/null
+++ b/include/linux/union_find.h
@@ -0,0 +1,24 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+
+/* Define a union-find node struct */
+struct uf_node {
+	struct uf_node *parent;
+	unsigned int rank;
+};
+
+/* Allocate nodes and initialize to 0 */
+static inline void uf_nodes_init(struct uf_node *node)
+{
+	node->parent = node;
+	node->rank = 0;
+}
+
+/* find the root of a 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);
+
+#endif /*__LINUX_UNION_FIND_H*/
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 is_single_threaded.o plist.o decompress.o kobject_uevent.o \
 	 earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
 	 nmi_backtrace.o win_minmax.o memcat_p.o \
-	 buildid.o objpool.o
+	 buildid.o objpool.o union_find.o
 
 lib-$(CONFIG_PRINTK) += dump_stack.o
 lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..bb48b4b129
--- /dev/null
+++ b/lib/union_find.c
@@ -0,0 +1,33 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+struct uf_node *uf_find(struct uf_node *node)
+{
+	struct uf_node *parent;
+
+	/*Find the root node and perform path compression at the same time*/
+	while (node->parent != node) {
+		parent = node->parent;
+		node->parent = parent->parent;
+		node = parent;
+	}
+	return node;
+}
+
+/*Function to merge two sets, using union by rank*/
+void 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) {
+		if (root1->rank < root2->rank) {
+			root1->parent = root2;
+		} else if (root1->rank > root2->rank) {
+			root2->parent = root1;
+		} else {
+			root2->parent = root1;
+			root1->rank++;
+		}
+	}
+}
-- 
2.45.2

Hello, Xavier.

On Sat, Jun 29, 2024 at 12:13:01AM +0800, Xavier wrote:
...
> +Initializing Union-Find
> +--------------------
> +
> +When initializing the Union-Find data structure, a single pointer to the
> +Union-Find instance needs to be passed. Initialize the parent pointer to point
> +to itself and set the rank to 0.
> +Example::
> +
> +	struct uf_node *my_node = vzalloc(sizeof(struct uf_node));
> +	uf_nodes_init(my_node);

It'd be better to replace the example with something which follows typical
kernel usage.

> diff --git a/include/linux/union_find.h b/include/linux/union_find.h
> new file mode 100644
> index 0000000000..56571c93a5
> --- /dev/null
> +++ b/include/linux/union_find.h
> @@ -0,0 +1,24 @@
> +/* SPDX-License-Identifier: GPL-2.0 */

It'd probably be useful to have a brief overview of what this is about and
point to the documentation here.

> +/* Define a union-find node struct */

I don't think the comment is contributing anything.

> +struct uf_node {
> +	struct uf_node *parent;
> +	unsigned int rank;
> +};
> +
> +/* Allocate nodes and initialize to 0 */

and this comment doesn't match what the code is doing. It's neither
allocating or setting everything to zero. Also, please use function comment
style (w/ /** and @ arg descriptions).

> +static inline void uf_nodes_init(struct uf_node *node)
> +{
> +	node->parent = node;
> +	node->rank = 0;
> +}

We'd also need an initializer for static cases.

> +/* find the root of a 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);

Please use function comment style comments above the implementatino of each
function.

> +struct uf_node *uf_find(struct uf_node *node)
> +{
> +	struct uf_node *parent;
> +
> +	/*Find the root node and perform path compression at the same time*/

Spaces?

> +	while (node->parent != node) {
> +		parent = node->parent;
> +		node->parent = parent->parent;
> +		node = parent;
> +	}
> +	return node;
> +}
> +
> +/*Function to merge two sets, using union by rank*/

Ditto.

Overall, this looks okay to me and the cgroup conversion does look nice.
However, it'd be really nice if you could find another place where this can
be applied.

Thanks.

-- 
tejun

Hi Tejun,

Thank you for thoroughly reviewing the code and pointing out the issues.
I have made the necessary changes to the code, comments, and documentation
based on your suggestions.

Kindly review.

Xavier (2):
  Union-Find: add a new module in kernel library
  cpuset: use Union-Find to optimize the merging of cpumasks

 Documentation/core-api/union_find.rst         | 102 ++++++++++++++++++
 .../zh_CN/core-api/union_find.rst             |  87 +++++++++++++++
 MAINTAINERS                                   |   9 ++
 include/linux/union_find.h                    |  41 +++++++
 kernel/cgroup/cpuset.c                        |  95 +++++++---------
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  48 +++++++++
 7 files changed, 324 insertions(+), 60 deletions(-)
 create mode 100644 Documentation/core-api/union_find.rst
 create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
 create mode 100644 include/linux/union_find.h
 create mode 100644 lib/union_find.c

-- 
2.45.0

On Tue, Jul 02, 2024 at 06:50:08PM +0800, Xavier wrote:
> Hi Tejun,
> 
> Thank you for thoroughly reviewing the code and pointing out the issues.
> I have made the necessary changes to the code, comments, and documentation
> based on your suggestions.

Looks fine to me. Once Waiman is okay with it, I can carry it through the
cgroup tree. Andrew, any objections? Xavier, it'd really great if you can do
more conversions so that it's not a single use thing.

Thanks.

-- 
tejun

Hi all,

All the pointed out comment issues have been addressed. Moving forward, I will
continue to look for applications of the union-find algorithm in other parts
of the kernel.

Kindly review.

Xavier (2):
  Union-Find: add a new module in kernel library
  cpuset: use Union-Find to optimize the merging of cpumasks

 Documentation/core-api/union_find.rst         | 102 ++++++++++++++++
 .../zh_CN/core-api/union_find.rst             |  87 +++++++++++++
 MAINTAINERS                                   |   9 ++
 include/linux/union_find.h                    |  41 +++++++
 kernel/cgroup/cpuset.c                        | 114 +++++++-----------
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  48 ++++++++
 7 files changed, 332 insertions(+), 71 deletions(-)
 create mode 100644 Documentation/core-api/union_find.rst
 create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
 create mode 100644 include/linux/union_find.h
 create mode 100644 lib/union_find.c

-- 
2.45.0

This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.

Signed-off-by: Xavier <xavier_qy@163.com>
---
 Documentation/core-api/union_find.rst         | 102 ++++++++++++++++++
 .../zh_CN/core-api/union_find.rst             |  87 +++++++++++++++
 MAINTAINERS                                   |   9 ++
 include/linux/union_find.h                    |  41 +++++++
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  48 +++++++++
 6 files changed, 288 insertions(+), 1 deletion(-)
 create mode 100644 Documentation/core-api/union_find.rst
 create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
 create mode 100644 include/linux/union_find.h
 create mode 100644 lib/union_find.c

diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst
new file mode 100644
index 0000000000..be9f68fd6d
--- /dev/null
+++ b/Documentation/core-api/union_find.rst
@@ -0,0 +1,102 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <xavier_qy@163.com>
+
+What is Union-Find, and what is it used for?
+------------------------------------------------
+
+Union-Find is a data structure used to handle the merging and querying
+of disjoint sets. The primary operations supported by Union-Find are:
+
+	Initialization: Resetting each element as an individual set, with
+		each set's initial parent node pointing to itself.
+	Find: Determine which set a particular element belongs to, usually by
+		returning a “representative element” of that set. This operation
+		is used to check if two elements are in the same set.
+	Union: Merge two sets into one.
+
+As a data structure used to maintain sets (groups), Union-Find is commonly
+utilized to solve problems related to offline queries, dynamic connectivity,
+and graph theory. It is also a key component in Kruskal's algorithm for
+computing the minimum spanning tree, which is crucial in scenarios like
+network routing. Consequently, Union-Find is widely referenced. Additionally,
+Union-Find has applications in symbolic computation, register allocation,
+and more.
+
+Space Complexity: O(n), where n is the number of nodes.
+
+Time Complexity: Using path compression can reduce the time complexity of
+the find operation, and using union by rank can reduce the time complexity
+of the union operation. These optimizations reduce the average time
+complexity of each find and union operation to O(α(n)), where α(n) is the
+inverse Ackermann function. This can be roughly considered a constant time
+complexity for practical purposes.
+
+This document covers use of the Linux union-find implementation.  For more
+information on the nature and implementation of Union-Find,  see:
+
+  Wikipedia entry on union-find
+    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+Linux implementation of union-find
+-----------------------------------
+
+Linux's union-find implementation resides in the file "lib/union_find.c".
+To use it, "#include <linux/union_find.h>".
+
+The Union-Find data structure is defined as follows::
+
+	struct uf_node {
+		struct uf_node *parent;
+		unsigned int rank;
+	};
+
+In this structure, parent points to the parent node of the current node.
+The rank field represents the height of the current tree. During a union
+operation, the tree with the smaller rank is attached under the tree with the
+larger rank to maintain balance.
+
+Initializing Union-Find
+--------------------
+
+You can complete the initialization using either static or initialization
+interface. Initialize the parent pointer to point to itself and set the rank
+to 0.
+Example::
+
+	struct uf_node my_node = UF_INIT_NODE(my_node);
+or
+	uf_node_init(&my_node);
+
+Find the Root Node of Union-Find
+--------------------------------
+
+This operation is mainly used to determine whether two nodes belong to the same
+set in the Union-Find. If they have the same root, they are in the same set.
+During the find operation, path compression is performed to improve the
+efficiency of subsequent find operations.
+Example::
+
+	int connected;
+	struct uf_node *root1 = uf_find(&node_1);
+	struct uf_node *root2 = uf_find(&node_2);
+	if (root1 == root2)
+		connected = 1;
+	else
+		connected = 0;
+
+Union Two Sets in Union-Find
+----------------------------
+
+To union two sets in the Union-Find, you first find their respective root nodes
+and then link the smaller node to the larger node based on the rank of the root
+nodes.
+Example::
+
+	uf_union(&node_1, &node_2);
diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Documentation/translations/zh_CN/core-api/union_find.rst
new file mode 100644
index 0000000000..a56de57147
--- /dev/null
+++ b/Documentation/translations/zh_CN/core-api/union_find.rst
@@ -0,0 +1,87 @@
+.. SPDX-License-Identifier: GPL-2.0
+.. include:: ../disclaimer-zh_CN.rst
+
+:Original: Documentation/core-api/union_find.rst
+
+===========================
+Linux中的并查集（Union-Find）
+===========================
+
+
+:日期: 2024年6月21日
+:作者: Xavier <xavier_qy@163.com>
+
+何为并查集，它有什么用？
+---------------------
+
+并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：
+	初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身
+	查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为
+		了判断两个元素是否在同一个集合之中。
+	合并：将两个集合合并为一个。
+
+并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和
+图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在
+网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分
+配等方面也有应用。
+
+空间复杂度: O(n)，n为节点数。
+
+时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的
+时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿
+克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。
+
+本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：
+
+  维基百科并查集词条
+    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+并查集的Linux实现
+----------------
+
+Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需要
+“#include <linux/union_find.h>”。
+
+并查集的数据结构定义如下::
+
+	struct uf_node {
+		struct uf_node *parent;
+		unsigned int rank;
+	};
+其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大
+的节点下面以增加平衡性。
+
+初始化并查集
+---------
+
+可以采用静态或初始化接口完成初始化操作。初始化时，parent 指针指向自身，rank 设置
+为 0。
+示例::
+
+	struct uf_node my_node = UF_INIT_NODE(my_node);
+或
+	uf_node_init(&my_node);
+
+查找并查集的根节点
+----------------
+
+主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中
+会对路径进行压缩，提高后续查找效率。
+示例::
+
+	int connected;
+	struct uf_node *root1 = uf_find(&node_1);
+	struct uf_node *root2 = uf_find(&node_2);
+	if (root1 == root2)
+		connected = 1;
+	else
+		connected = 0;
+
+合并两个并查集
+-------------
+
+对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的
+节点连接到大的节点下面。
+示例::
+
+	uf_union(&node_1, &node_2);
diff --git a/MAINTAINERS b/MAINTAINERS
index 2ca8f35dfe..16171dbca3 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23051,6 +23051,15 @@ F:	drivers/cdrom/cdrom.c
 F:	include/linux/cdrom.h
 F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <xavier_qy@163.com>
+L:	linux-kernel@vger.kernel.org
+S:	Maintained
+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
+
 UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
 R:	Alim Akhtar <alim.akhtar@samsung.com>
 R:	Avri Altman <avri.altman@wdc.com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..f127cf9b8d
--- /dev/null
+++ b/include/linux/union_find.h
@@ -0,0 +1,41 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+/**
+ * union_find.h - Union-Find data structure implementation
+ *
+ * This header provides functions and structures to implement the Union-Find
+ * data structure. The Union-Find data structure is used to manage disjoint
+ * sets and supports efficient union and find operations.
+ *
+ * See Documentation/core-api/union_find.rst for documentation and samples.
+ */
+
+struct uf_node {
+	struct uf_node *parent;
+	unsigned int rank;
+};
+
+/* This macro is used for static initialization of a union-find node. */
+#define UF_INIT_NODE(node)	{.parent = &node, .rank = 0}
+
+/**
+ * uf_node_init - Initialize a union-find node
+ * @node: pointer to the union-find node to be initialized
+ *
+ * This function sets the parent of the node to itself and
+ * initializes its rank to 0.
+ */
+static inline void uf_node_init(struct uf_node *node)
+{
+	node->parent = node;
+	node->rank = 0;
+}
+
+/* find the root of a 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);
+
+#endif /* __LINUX_UNION_FIND_H */
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 is_single_threaded.o plist.o decompress.o kobject_uevent.o \
 	 earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
 	 nmi_backtrace.o win_minmax.o memcat_p.o \
-	 buildid.o objpool.o
+	 buildid.o objpool.o union_find.o
 
 lib-$(CONFIG_PRINTK) += dump_stack.o
 lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..bec574ad24
--- /dev/null
+++ b/lib/union_find.c
@@ -0,0 +1,48 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+/**
+ * uf_find - Find the root of a node and perform path compression
+ * @node: the node to find the root of
+ *
+ * This function returns the root of the node by following the parent
+ * pointers. It also performs path compression, making the tree shallower.
+ *
+ * Returns the root node of the set containing node.
+ */
+struct uf_node *uf_find(struct uf_node *node)
+{
+	struct uf_node *parent;
+
+	while (node->parent != node) {
+		parent = node->parent;
+		node->parent = parent->parent;
+		node = parent;
+	}
+	return node;
+}
+
+/**
+ * uf_union - Merge two sets, using union by rank
+ * @node1: the first node
+ * @node2: the second node
+ *
+ * This function merges the sets containing node1 and node2, by comparing
+ * the ranks to keep the tree balanced.
+ */
+void 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) {
+		if (root1->rank < root2->rank) {
+			root1->parent = root2;
+		} else if (root1->rank > root2->rank) {
+			root2->parent = root1;
+		} else {
+			root2->parent = root1;
+			root1->rank++;
+		}
+	}
+}
-- 
2.45.0

On Wed, Jul 03, 2024 at 02:37:26PM GMT, Xavier <xavier_qy@163.com> wrote:
> This patch implements a union-find data structure in the kernel library,
> which includes operations for allocating nodes, freeing nodes,
> finding the root of a node, and merging two nodes.
> 
> Signed-off-by: Xavier <xavier_qy@163.com>
> ---
>  Documentation/core-api/union_find.rst         | 102 ++++++++++++++++++
>  .../zh_CN/core-api/union_find.rst             |  87 +++++++++++++++
>  MAINTAINERS                                   |   9 ++
>  include/linux/union_find.h                    |  41 +++++++
>  lib/Makefile                                  |   2 +-
>  lib/union_find.c                              |  48 +++++++++
>  6 files changed, 288 insertions(+), 1 deletion(-)
>  create mode 100644 Documentation/core-api/union_find.rst
>  create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
>  create mode 100644 include/linux/union_find.h
>  create mode 100644 lib/union_find.c
> 

Nice.
I'd so s/Union-Find/union-find/ both in the docs and the code
(comments), I didn't find any rule why two capitalizations are used.

> +struct uf_node {
> +	struct uf_node *parent;
> +	unsigned int rank;
> +};
> +
> +/* This macro is used for static initialization of a union-find node. */
> +#define UF_INIT_NODE(node)	{.parent = &node, .rank = 0}
> +
> +/**
> + * uf_node_init - Initialize a union-find node
> + * @node: pointer to the union-find node to be initialized
> + *
> + * This function sets the parent of the node to itself and
> + * initializes its rank to 0.
> + */
> +static inline void uf_node_init(struct uf_node *node)
> +{
> +	node->parent = node;
> +	node->rank = 0;
> +}

Xavier, not sure if you responded to my suggestion of considered zeroed
object a valid initialized one. That could save some init work (and
move it to alternative uf_find, see below).

> + * This function returns the root of the node by following the parent
> + * pointers. It also performs path compression, making the tree shallower.
> + *
> + * Returns the root node of the set containing node.
> + */
> +struct uf_node *uf_find(struct uf_node *node)
> +{
> +	struct uf_node *parent;
> +

With uf_find body checking for NULL:

	while (node->parent != node) {
		parent = node->parent;
		node->parent = parent ? parent->parent : node;
		node = node->parent;
	}

> +/**
> + * uf_union - Merge two sets, using union by rank
> + * @node1: the first node
> + * @node2: the second node
> + *
> + * This function merges the sets containing node1 and node2, by comparing
> + * the ranks to keep the tree balanced.
> + */
> +void 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) {

if (root1 == root2)
	return;
then the rest can be one level less nested ;-)

Michal

Hi Michal,

At 2024-07-03 17:40:25, "Michal Koutný" <mkoutny@suse.com> wrote:
>On Wed, Jul 03, 2024 at 02:37:26PM GMT, Xavier <xavier_qy@163.com> wrote:
>> This patch implements a union-find data structure in the kernel library,
>> which includes operations for allocating nodes, freeing nodes,
>> finding the root of a node, and merging two nodes.
>> 
>> Signed-off-by: Xavier <xavier_qy@163.com>
>> ---
>>  Documentation/core-api/union_find.rst         | 102 ++++++++++++++++++
>>  .../zh_CN/core-api/union_find.rst             |  87 +++++++++++++++
>>  MAINTAINERS                                   |   9 ++
>>  include/linux/union_find.h                    |  41 +++++++
>>  lib/Makefile                                  |   2 +-
>>  lib/union_find.c                              |  48 +++++++++
>>  6 files changed, 288 insertions(+), 1 deletion(-)
>>  create mode 100644 Documentation/core-api/union_find.rst
>>  create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
>>  create mode 100644 include/linux/union_find.h
>>  create mode 100644 lib/union_find.c
>> 
>
>Nice.
>I'd so s/Union-Find/union-find/ both in the docs and the code
>(comments), I didn't find any rule why two capitalizations are used.

Union-Find only appears in the patch description or title; in the main text, we consistently
use union-find. This will be corrected in the next version.

>> +struct uf_node {
>> +	struct uf_node *parent;
>> +	unsigned int rank;
>> +};
>> +
>> +/* This macro is used for static initialization of a union-find node. */
>> +#define UF_INIT_NODE(node)	{.parent = &node, .rank = 0}
>> +
>> +/**
>> + * uf_node_init - Initialize a union-find node
>> + * @node: pointer to the union-find node to be initialized
>> + *
>> + * This function sets the parent of the node to itself and
>> + * initializes its rank to 0.
>> + */
>> +static inline void uf_node_init(struct uf_node *node)
>> +{
>> +	node->parent = node;
>> +	node->rank = 0;
>> +}
>
>Xavier, not sure if you responded to my suggestion of considered zeroed
>object a valid initialized one. That could save some init work (and
>move it to alternative uf_find, see below).
>
>With uf_find body checking for NULL:
>
>	while (node->parent != node) {
>		parent = node->parent;
>		node->parent = parent ? parent->parent : node;
>		node = node->parent;
>	}

Yes, I noticed your suggestion. In patch v4, I implemented it by initializing to 0
and adding a check for whether the parent is 0 in uf_find. However, later,
when I was reviewing the algorithm's documentation, I noticed it requires
initialization to itself. Moreover, uf_find is a high-frequency operation, if we
add a parent check within it, the efficiency impact each time would be more
significant than initializing once. Therefore, I adhered to the initialization
to itself approach.

>> +/**
>> + * uf_union - Merge two sets, using union by rank
>> + * @node1: the first node
>> + * @node2: the second node
>> + *
>> + * This function merges the sets containing node1 and node2, by comparing
>> + * the ranks to keep the tree balanced.
>> + */
>> +void 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) {
>
>if (root1 == root2)
>	return;
>then the rest can be one level less nested ;-)
>
Of course, this change makes it look clearer.

--
Best Regards,
Xavier

On Wed, Jul 03, 2024 at 07:20:09PM GMT, Xavier <xavier_qy@163.com> wrote:
> >Xavier, not sure if you responded to my suggestion of considered zeroed
> >object a valid initialized one. That could save some init work (and
> >move it to alternative uf_find, see below).
> >
> >With uf_find body checking for NULL:
> >
> >	while (node->parent != node) {
> >		parent = node->parent;
> >		node->parent = parent ? parent->parent : node;
> >		node = node->parent;
> >	}
> 
> Yes, I noticed your suggestion. In patch v4, I implemented it by
> initializing to 0 and adding a check for whether the parent is 0 in
> uf_find.

Ah, I didn't read all versions. (You may consider adding a short
changelog when sending a new version of patches where main evolution
points are summed up. ;-))

> However, later, when I was reviewing the algorithm's documentation, I
> noticed it requires initialization to itself.

Well, that's not a hard requirement.

> Moreover, uf_find is a high-frequency operation, if we add a parent
> check within it, the efficiency impact each time would be more
> significant than initializing once. Therefore, I adhered to the
> initialization to itself approach.

I see, thanks for the clarifications,
Michal

The process of constructing scheduling domains
 involves multiple loops and repeated evaluations, leading to numerous
 redundant and ineffective assessments that impact code efficiency.

Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.

Signed-off-by: Xavier <xavier_qy@163.com>
---
 kernel/cgroup/cpuset.c | 114 ++++++++++++++++-------------------------
 1 file changed, 44 insertions(+), 70 deletions(-)

diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index fe76045aa5..88c2171361 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -45,6 +45,7 @@
 #include <linux/cgroup.h>
 #include <linux/wait.h>
 #include <linux/workqueue.h>
+#include <linux/union_find.h>
 
 DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
 DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
@@ -172,9 +173,6 @@ struct cpuset {
 	 */
 	int attach_in_progress;
 
-	/* partition number for rebuild_sched_domains() */
-	int pn;
-
 	/* for custom sched domain */
 	int relax_domain_level;
 
@@ -208,6 +206,9 @@ struct cpuset {
 
 	/* Remote partition silbling list anchored at remote_children */
 	struct list_head remote_sibling;
+
+	/* Used to merge intersecting subsets for generate_sched_domains */
+	struct uf_node node;
 };
 
 /*
@@ -988,18 +989,15 @@ static inline int nr_cpusets(void)
  *	   were changed (added or removed.)
  *
  * Finding the best partition (set of domains):
- *	The triple nested loops below over i, j, k scan over the
- *	load balanced cpusets (using the array of cpuset pointers in
- *	csa[]) looking for pairs of cpusets that have overlapping
- *	cpus_allowed, but which don't have the same 'pn' partition
- *	number and gives them in the same partition number.  It keeps
- *	looping on the 'restart' label until it can no longer find
- *	any such pairs.
+ *	The double nested loops below over i, j scan over the load
+ *	balanced cpusets (using the array of cpuset pointers in csa[])
+ *	looking for pairs of cpusets that have overlapping cpus_allowed
+ *	and merging them using a union-find algorithm.
+ *
+ *	The union of the cpus_allowed masks from the set of all cpusets
+ *	having the same root then form the one element of the partition
+ *	(one sched domain) to be passed to partition_sched_domains().
  *
- *	The union of the cpus_allowed masks from the set of
- *	all cpusets having the same 'pn' value then form the one
- *	element of the partition (one sched domain) to be passed to
- *	partition_sched_domains().
  */
 static int generate_sched_domains(cpumask_var_t **domains,
 			struct sched_domain_attr **attributes)
@@ -1007,7 +1005,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	struct cpuset *cp;	/* top-down scan of cpusets */
 	struct cpuset **csa;	/* array of all cpuset ptrs */
 	int csn;		/* how many cpuset ptrs in csa so far */
-	int i, j, k;		/* indices for partition finding loops */
+	int i, j;		/* indices for partition finding loops */
 	cpumask_var_t *doms;	/* resulting partition; i.e. sched domains */
 	struct sched_domain_attr *dattr;  /* attributes for custom domains */
 	int ndoms = 0;		/* number of sched domains in result */
@@ -1015,6 +1013,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	struct cgroup_subsys_state *pos_css;
 	bool root_load_balance = is_sched_load_balance(&top_cpuset);
 	bool cgrpv2 = cgroup_subsys_on_dfl(cpuset_cgrp_subsys);
+	int nslot_update;
 
 	doms = NULL;
 	dattr = NULL;
@@ -1102,31 +1101,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	if (root_load_balance && (csn == 1))
 		goto single_root_domain;
 
-	for (i = 0; i < csn; i++)
-		csa[i]->pn = i;
-	ndoms = csn;
-
-restart:
-	/* Find the best partition (set of sched domains) */
-	for (i = 0; i < csn; i++) {
-		struct cpuset *a = csa[i];
-		int apn = a->pn;
-
-		for (j = 0; j < csn; j++) {
-			struct cpuset *b = csa[j];
-			int bpn = b->pn;
-
-			if (apn != bpn && cpusets_overlap(a, b)) {
-				for (k = 0; k < csn; k++) {
-					struct cpuset *c = csa[k];
+	if (!cgrpv2) {
+		for (i = 0; i < csn; i++)
+			uf_node_init(&csa[i]->node);
 
-					if (c->pn == bpn)
-						c->pn = apn;
-				}
-				ndoms--;	/* one less element */
-				goto restart;
+		/* Merge overlapping cpusets */
+		for (i = 0; i < csn; i++) {
+			for (j = i + 1; j < csn; j++) {
+				if (cpusets_overlap(csa[i], csa[j]))
+					uf_union(&csa[i]->node, &csa[j]->node);
 			}
 		}
+
+		/* Count the total number of domains */
+		for (i = 0; i < csn; i++) {
+			if (csa[i]->node.parent == &csa[i]->node)
+				ndoms++;
+		}
+	} else {
+		ndoms = csn;
 	}
 
 	/*
@@ -1159,44 +1152,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	}
 
 	for (nslot = 0, i = 0; i < csn; i++) {
-		struct cpuset *a = csa[i];
-		struct cpumask *dp;
-		int apn = a->pn;
-
-		if (apn < 0) {
-			/* Skip completed partitions */
-			continue;
-		}
-
-		dp = doms[nslot];
-
-		if (nslot == ndoms) {
-			static int warnings = 10;
-			if (warnings) {
-				pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
-					nslot, ndoms, csn, i, apn);
-				warnings--;
-			}
-			continue;
-		}
-
-		cpumask_clear(dp);
-		if (dattr)
-			*(dattr + nslot) = SD_ATTR_INIT;
+		nslot_update = 0;
 		for (j = i; j < csn; j++) {
-			struct cpuset *b = csa[j];
-
-			if (apn == b->pn) {
-				cpumask_or(dp, dp, b->effective_cpus);
+			if (uf_find(&csa[j]->node) == &csa[i]->node) {
+				struct cpumask *dp = doms[nslot];
+
+				if (i == j) {
+					nslot_update = 1;
+					cpumask_clear(dp);
+					if (dattr)
+						*(dattr + nslot) = SD_ATTR_INIT;
+				}
+				cpumask_or(dp, dp, csa[j]->effective_cpus);
 				cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN));
 				if (dattr)
-					update_domain_attr_tree(dattr + nslot, b);
-
-				/* Done with this partition */
-				b->pn = -1;
+					update_domain_attr_tree(dattr + nslot, csa[j]);
 			}
 		}
-		nslot++;
+		if (nslot_update)
+			nslot++;
 	}
 	BUG_ON(nslot != ndoms);
 
-- 
2.45.0

On Wed, Jul 03, 2024 at 02:37:27PM GMT, Xavier <xavier_qy@163.com> wrote:
> @@ -1102,31 +1101,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
>  	if (root_load_balance && (csn == 1))
>  		goto single_root_domain;
>  
> -	for (i = 0; i < csn; i++)
> -		csa[i]->pn = i;
> -	ndoms = csn;
> -
> -restart:
> -	/* Find the best partition (set of sched domains) */
> -	for (i = 0; i < csn; i++) {
> -		struct cpuset *a = csa[i];
> -		int apn = a->pn;
> -
> -		for (j = 0; j < csn; j++) {
> -			struct cpuset *b = csa[j];
> -			int bpn = b->pn;
> -
> -			if (apn != bpn && cpusets_overlap(a, b)) {
> -				for (k = 0; k < csn; k++) {
> -					struct cpuset *c = csa[k];
> +	if (!cgrpv2) {

I'm surprised that original code wasn't branched on this on you add it
here. Why is UF used only for v1 code?

> +		for (i = 0; i < csn; i++)
> +			uf_node_init(&csa[i]->node);
>  
> -					if (c->pn == bpn)
> -						c->pn = apn;
> -				}
> -				ndoms--;	/* one less element */
> -				goto restart;
> +		/* Merge overlapping cpusets */
> +		for (i = 0; i < csn; i++) {
> +			for (j = i + 1; j < csn; j++) {
> +				if (cpusets_overlap(csa[i], csa[j]))
> +					uf_union(&csa[i]->node, &csa[j]->node);
>  			}
>  		}
> +
> +		/* Count the total number of domains */
> +		for (i = 0; i < csn; i++) {
> +			if (csa[i]->node.parent == &csa[i]->node)
> +				ndoms++;

The naked parent access doesn't hide the UF abstraction well.
I'd consider uf_find(&csa[i]->node) == &csa[i]->node or a specific
helper like uf_is_representant(&csa[i]->node).

Thanks,
Michal

Hi Michal and Longman,

Please confirm my explanation about cgroup v2 below.


At 2024-07-03 17:40:49, "Michal Koutný" <mkoutny@suse.com> wrote:
>On Wed, Jul 03, 2024 at 02:37:27PM GMT, Xavier <xavier_qy@163.com> wrote:
>> @@ -1102,31 +1101,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
>>  	if (root_load_balance && (csn == 1))
>>  		goto single_root_domain;
>>  
>> -	for (i = 0; i < csn; i++)
>> -		csa[i]->pn = i;
>> -	ndoms = csn;
>> -
>> -restart:
>> -	/* Find the best partition (set of sched domains) */
>> -	for (i = 0; i < csn; i++) {
>> -		struct cpuset *a = csa[i];
>> -		int apn = a->pn;
>> -
>> -		for (j = 0; j < csn; j++) {
>> -			struct cpuset *b = csa[j];
>> -			int bpn = b->pn;
>> -
>> -			if (apn != bpn && cpusets_overlap(a, b)) {
>> -				for (k = 0; k < csn; k++) {
>> -					struct cpuset *c = csa[k];
>> +	if (!cgrpv2) {
>
>I'm surprised that original code wasn't branched on this on you add it
>here. Why is UF used only for v1 code?
>

In the Patch v6, I explained to Longman that based on his new patch, the overlapping check and
merge operations for cpusets are skipped in the case of cgroup v2. Because for cgroup v2,
doms[i] is merely copied from csa[i] rather than merged.
This needs further confirmation from Longman.

	if (cgrpv2) {
		for (i = 0; i < ndoms; i++) {
			cpumask_copy(doms[i], csa[i]->effective_cpus);
			if (dattr)
				dattr[i] = SD_ATTR_INIT;
		}
		goto done;
	}


>> +		for (i = 0; i < csn; i++)
>> +			uf_node_init(&csa[i]->node);
>>  
>> -					if (c->pn == bpn)
>> -						c->pn = apn;
>> -				}
>> -				ndoms--;	/* one less element */
>> -				goto restart;
>> +		/* Merge overlapping cpusets */
>> +		for (i = 0; i < csn; i++) {
>> +			for (j = i + 1; j < csn; j++) {
>> +				if (cpusets_overlap(csa[i], csa[j]))
>> +					uf_union(&csa[i]->node, &csa[j]->node);
>>  			}
>>  		}
>> +
>> +		/* Count the total number of domains */
>> +		for (i = 0; i < csn; i++) {
>> +			if (csa[i]->node.parent == &csa[i]->node)
>> +				ndoms++;
>
>The naked parent access doesn't hide the UF abstraction well.
>I'd consider uf_find(&csa[i]->node) == &csa[i]->node or a specific
>helper like uf_is_representant(&csa[i]->node).

This can be optimized here. I will change it to the first method you mentioned in the next patch.

Best Regards,
Xavier

On 7/3/24 06:49, Xavier wrote:
>
> Hi Michal and Longman,
>
> Please confirm my explanation about cgroup v2 below.
>
>
> At 2024-07-03 17:40:49, "Michal Koutný" <mkoutny@suse.com> wrote:
>> On Wed, Jul 03, 2024 at 02:37:27PM GMT, Xavier <xavier_qy@163.com> wrote:
>>> @@ -1102,31 +1101,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
>>>   	if (root_load_balance && (csn == 1))
>>>   		goto single_root_domain;
>>>   
>>> -	for (i = 0; i < csn; i++)
>>> -		csa[i]->pn = i;
>>> -	ndoms = csn;
>>> -
>>> -restart:
>>> -	/* Find the best partition (set of sched domains) */
>>> -	for (i = 0; i < csn; i++) {
>>> -		struct cpuset *a = csa[i];
>>> -		int apn = a->pn;
>>> -
>>> -		for (j = 0; j < csn; j++) {
>>> -			struct cpuset *b = csa[j];
>>> -			int bpn = b->pn;
>>> -
>>> -			if (apn != bpn && cpusets_overlap(a, b)) {
>>> -				for (k = 0; k < csn; k++) {
>>> -					struct cpuset *c = csa[k];
>>> +	if (!cgrpv2) {
>> I'm surprised that original code wasn't branched on this on you add it
>> here. Why is UF used only for v1 code?
>>
> In the Patch v6, I explained to Longman that based on his new patch, the overlapping check and
> merge operations for cpusets are skipped in the case of cgroup v2. Because for cgroup v2,
> doms[i] is merely copied from csa[i] rather than merged.
> This needs further confirmation from Longman.

Actually, I would like to keep the cpuset merging part for both cgroup 
v1 and v2. I did notice that the hotplug code path can sometimes cause 
overlapping partition roots in some intermediate states. I will try to 
get it of that and use the merging part to verify that all partition 
roots are mutually exclusive.

Cheers,
Longman

Hi all,

Based on Michal's suggestion, the following changes were made:
1. Changed Union-Find to union-find in all places except the title.
2. Optimized the logic of the uf_union function.
3. Modified places where csa[i]->node.parent was used directly.

To Longman,
Regarding the modifications for supporting cpuset merging in both cgroup
v1 and v2, do you mean that you will continue to complete them after my
patch is merged?

Kindly review.

Xavier (2):
  Union-Find: add a new module in kernel library
  cpuset: use Union-Find to optimize the merging of cpumasks

 Documentation/core-api/union_find.rst         | 102 ++++++++++++++++
 .../zh_CN/core-api/union_find.rst             |  87 +++++++++++++
 MAINTAINERS                                   |   9 ++
 include/linux/union_find.h                    |  41 +++++++
 kernel/cgroup/cpuset.c                        | 114 +++++++-----------
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  49 ++++++++
 7 files changed, 333 insertions(+), 71 deletions(-)
 create mode 100644 Documentation/core-api/union_find.rst
 create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
 create mode 100644 include/linux/union_find.h
 create mode 100644 lib/union_find.c

-- 
2.45.0

On 7/4/24 02:24, Xavier wrote:
> Hi all,
>
> Based on Michal's suggestion, the following changes were made:
> 1. Changed Union-Find to union-find in all places except the title.
> 2. Optimized the logic of the uf_union function.
> 3. Modified places where csa[i]->node.parent was used directly.
>
> To Longman,
> Regarding the modifications for supporting cpuset merging in both cgroup
> v1 and v2, do you mean that you will continue to complete them after my
> patch is merged?
Yes.
>
> Kindly review.
>
> Xavier (2):
>    Union-Find: add a new module in kernel library
>    cpuset: use Union-Find to optimize the merging of cpumasks
>
>   Documentation/core-api/union_find.rst         | 102 ++++++++++++++++
>   .../zh_CN/core-api/union_find.rst             |  87 +++++++++++++
>   MAINTAINERS                                   |   9 ++
>   include/linux/union_find.h                    |  41 +++++++
>   kernel/cgroup/cpuset.c                        | 114 +++++++-----------
>   lib/Makefile                                  |   2 +-
>   lib/union_find.c                              |  49 ++++++++
>   7 files changed, 333 insertions(+), 71 deletions(-)
>   create mode 100644 Documentation/core-api/union_find.rst
>   create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
>   create mode 100644 include/linux/union_find.h
>   create mode 100644 lib/union_find.c
>
The patch series looks good to me. However, it is a still major change 
in the domain generation algorithm and it is too late for v6.11. I would 
also like it to spend more time in linux-next as I don't have a good set 
of cgroup v1 test. I will support merging this for v6.12.

Acked-by: Waiman Long <longman@redhat.com>

On Sun, Jul 07, 2024 at 09:59:55PM -0400, Waiman Long wrote:
> The patch series looks good to me. However, it is a still major change in
> the domain generation algorithm and it is too late for v6.11. I would also
> like it to spend more time in linux-next as I don't have a good set of
> cgroup v1 test. I will support merging this for v6.12.
> 
> Acked-by: Waiman Long <longman@redhat.com>

Xavier, as we're pretty close to the merge window, I think it'd be best to
do this in the next merge window as Waiman said. Can you please ping me once
v6.11-rc1 is cut? I'll apply the two patches on cgroup/for-6.12.

Thanks.

-- 
tejun

Hi Tejun,

I saw on kernel.org that v6.11-rc1 has been released. It might be time to start merging
this patch. 

By the way,  I have submitted an optimization patch for RT group scheduling, but after
two rounds of communication, I haven't received any further responses. Could you
provide me with some advice?

https://lore.kernel.org/all/20240627172156.235421-1-xavier_qy@163.com/

Thanks.


At 2024-07-09 02:38:33, "Tejun Heo" <tj@kernel.org> wrote:
>On Sun, Jul 07, 2024 at 09:59:55PM -0400, Waiman Long wrote:
>> The patch series looks good to me. However, it is a still major change in
>> the domain generation algorithm and it is too late for v6.11. I would also
>> like it to spend more time in linux-next as I don't have a good set of
>> cgroup v1 test. I will support merging this for v6.12.
>> 
>> Acked-by: Waiman Long <longman@redhat.com>
>
>Xavier, as we're pretty close to the merge window, I think it'd be best to
>do this in the next merge window as Waiman said. Can you please ping me once
>v6.11-rc1 is cut? I'll apply the two patches on cgroup/for-6.12.
>



--
Best Regards,
Xavier

Hello,

On Mon, Jul 29, 2024 at 10:44:08AM +0800, Xavier wrote:
> I saw on kernel.org that v6.11-rc1 has been released. It might be time to start merging
> this patch. 

Merged two patches.

> By the way,  I have submitted an optimization patch for RT group scheduling, but after
> two rounds of communication, I haven't received any further responses. Could you
> provide me with some advice?
> 
> https://lore.kernel.org/all/20240627172156.235421-1-xavier_qy@163.com/

I'm not sure I have a useful advice other than just pinging again.

Thanks.

-- 
tejun

Hi tejun,


Sure, that works. We can wait to merge it into the cgroup/for-6.12 branch. I will ping you once v6.11-rc1 is cut.
Thank you.


--
Best Regards,
Xavier




At 2024-07-09 02:38:33, "Tejun Heo" <tj@kernel.org> wrote:
>On Sun, Jul 07, 2024 at 09:59:55PM -0400, Waiman Long wrote:
>> The patch series looks good to me. However, it is a still major change in
>> the domain generation algorithm and it is too late for v6.11. I would also
>> like it to spend more time in linux-next as I don't have a good set of
>> cgroup v1 test. I will support merging this for v6.12.
>> 
>> Acked-by: Waiman Long <longman@redhat.com>
>
>Xavier, as we're pretty close to the merge window, I think it'd be best to
>do this in the next merge window as Waiman said. Can you please ping me once
>v6.11-rc1 is cut? I'll apply the two patches on cgroup/for-6.12.
>
>Thanks.
>
>-- 
>tejun

This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.

Signed-off-by: Xavier <xavier_qy@163.com>
---
 Documentation/core-api/union_find.rst         | 102 ++++++++++++++++++
 .../zh_CN/core-api/union_find.rst             |  87 +++++++++++++++
 MAINTAINERS                                   |   9 ++
 include/linux/union_find.h                    |  41 +++++++
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  49 +++++++++
 6 files changed, 289 insertions(+), 1 deletion(-)
 create mode 100644 Documentation/core-api/union_find.rst
 create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
 create mode 100644 include/linux/union_find.h
 create mode 100644 lib/union_find.c

diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst
new file mode 100644
index 0000000000..2bf0290c91
--- /dev/null
+++ b/Documentation/core-api/union_find.rst
@@ -0,0 +1,102 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <xavier_qy@163.com>
+
+What is union-find, and what is it used for?
+------------------------------------------------
+
+Union-find is a data structure used to handle the merging and querying
+of disjoint sets. The primary operations supported by union-find are:
+
+	Initialization: Resetting each element as an individual set, with
+		each set's initial parent node pointing to itself.
+	Find: Determine which set a particular element belongs to, usually by
+		returning a “representative element” of that set. This operation
+		is used to check if two elements are in the same set.
+	Union: Merge two sets into one.
+
+As a data structure used to maintain sets (groups), union-find is commonly
+utilized to solve problems related to offline queries, dynamic connectivity,
+and graph theory. It is also a key component in Kruskal's algorithm for
+computing the minimum spanning tree, which is crucial in scenarios like
+network routing. Consequently, union-find is widely referenced. Additionally,
+union-find has applications in symbolic computation, register allocation,
+and more.
+
+Space Complexity: O(n), where n is the number of nodes.
+
+Time Complexity: Using path compression can reduce the time complexity of
+the find operation, and using union by rank can reduce the time complexity
+of the union operation. These optimizations reduce the average time
+complexity of each find and union operation to O(α(n)), where α(n) is the
+inverse Ackermann function. This can be roughly considered a constant time
+complexity for practical purposes.
+
+This document covers use of the Linux union-find implementation.  For more
+information on the nature and implementation of union-find,  see:
+
+  Wikipedia entry on union-find
+    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+Linux implementation of union-find
+-----------------------------------
+
+Linux's union-find implementation resides in the file "lib/union_find.c".
+To use it, "#include <linux/union_find.h>".
+
+The union-find data structure is defined as follows::
+
+	struct uf_node {
+		struct uf_node *parent;
+		unsigned int rank;
+	};
+
+In this structure, parent points to the parent node of the current node.
+The rank field represents the height of the current tree. During a union
+operation, the tree with the smaller rank is attached under the tree with the
+larger rank to maintain balance.
+
+Initializing union-find
+--------------------
+
+You can complete the initialization using either static or initialization
+interface. Initialize the parent pointer to point to itself and set the rank
+to 0.
+Example::
+
+	struct uf_node my_node = UF_INIT_NODE(my_node);
+or
+	uf_node_init(&my_node);
+
+Find the Root Node of union-find
+--------------------------------
+
+This operation is mainly used to determine whether two nodes belong to the same
+set in the union-find. If they have the same root, they are in the same set.
+During the find operation, path compression is performed to improve the
+efficiency of subsequent find operations.
+Example::
+
+	int connected;
+	struct uf_node *root1 = uf_find(&node_1);
+	struct uf_node *root2 = uf_find(&node_2);
+	if (root1 == root2)
+		connected = 1;
+	else
+		connected = 0;
+
+Union Two Sets in union-find
+----------------------------
+
+To union two sets in the union-find, you first find their respective root nodes
+and then link the smaller node to the larger node based on the rank of the root
+nodes.
+Example::
+
+	uf_union(&node_1, &node_2);
diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Documentation/translations/zh_CN/core-api/union_find.rst
new file mode 100644
index 0000000000..a56de57147
--- /dev/null
+++ b/Documentation/translations/zh_CN/core-api/union_find.rst
@@ -0,0 +1,87 @@
+.. SPDX-License-Identifier: GPL-2.0
+.. include:: ../disclaimer-zh_CN.rst
+
+:Original: Documentation/core-api/union_find.rst
+
+===========================
+Linux中的并查集（Union-Find）
+===========================
+
+
+:日期: 2024年6月21日
+:作者: Xavier <xavier_qy@163.com>
+
+何为并查集，它有什么用？
+---------------------
+
+并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：
+	初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身
+	查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为
+		了判断两个元素是否在同一个集合之中。
+	合并：将两个集合合并为一个。
+
+并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和
+图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在
+网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分
+配等方面也有应用。
+
+空间复杂度: O(n)，n为节点数。
+
+时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的
+时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿
+克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。
+
+本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：
+
+  维基百科并查集词条
+    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+并查集的Linux实现
+----------------
+
+Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需要
+“#include <linux/union_find.h>”。
+
+并查集的数据结构定义如下::
+
+	struct uf_node {
+		struct uf_node *parent;
+		unsigned int rank;
+	};
+其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大
+的节点下面以增加平衡性。
+
+初始化并查集
+---------
+
+可以采用静态或初始化接口完成初始化操作。初始化时，parent 指针指向自身，rank 设置
+为 0。
+示例::
+
+	struct uf_node my_node = UF_INIT_NODE(my_node);
+或
+	uf_node_init(&my_node);
+
+查找并查集的根节点
+----------------
+
+主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中
+会对路径进行压缩，提高后续查找效率。
+示例::
+
+	int connected;
+	struct uf_node *root1 = uf_find(&node_1);
+	struct uf_node *root2 = uf_find(&node_2);
+	if (root1 == root2)
+		connected = 1;
+	else
+		connected = 0;
+
+合并两个并查集
+-------------
+
+对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的
+节点连接到大的节点下面。
+示例::
+
+	uf_union(&node_1, &node_2);
diff --git a/MAINTAINERS b/MAINTAINERS
index 2ca8f35dfe..16171dbca3 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23051,6 +23051,15 @@ F:	drivers/cdrom/cdrom.c
 F:	include/linux/cdrom.h
 F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <xavier_qy@163.com>
+L:	linux-kernel@vger.kernel.org
+S:	Maintained
+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
+
 UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
 R:	Alim Akhtar <alim.akhtar@samsung.com>
 R:	Avri Altman <avri.altman@wdc.com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..cfd49263c1
--- /dev/null
+++ b/include/linux/union_find.h
@@ -0,0 +1,41 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+/**
+ * union_find.h - union-find data structure implementation
+ *
+ * This header provides functions and structures to implement the union-find
+ * data structure. The union-find data structure is used to manage disjoint
+ * sets and supports efficient union and find operations.
+ *
+ * See Documentation/core-api/union_find.rst for documentation and samples.
+ */
+
+struct uf_node {
+	struct uf_node *parent;
+	unsigned int rank;
+};
+
+/* This macro is used for static initialization of a union-find node. */
+#define UF_INIT_NODE(node)	{.parent = &node, .rank = 0}
+
+/**
+ * uf_node_init - Initialize a union-find node
+ * @node: pointer to the union-find node to be initialized
+ *
+ * This function sets the parent of the node to itself and
+ * initializes its rank to 0.
+ */
+static inline void uf_node_init(struct uf_node *node)
+{
+	node->parent = node;
+	node->rank = 0;
+}
+
+/* find the root of a 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);
+
+#endif /* __LINUX_UNION_FIND_H */
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 is_single_threaded.o plist.o decompress.o kobject_uevent.o \
 	 earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
 	 nmi_backtrace.o win_minmax.o memcat_p.o \
-	 buildid.o objpool.o
+	 buildid.o objpool.o union_find.o
 
 lib-$(CONFIG_PRINTK) += dump_stack.o
 lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..413b0f8adf
--- /dev/null
+++ b/lib/union_find.c
@@ -0,0 +1,49 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+/**
+ * uf_find - Find the root of a node and perform path compression
+ * @node: the node to find the root of
+ *
+ * This function returns the root of the node by following the parent
+ * pointers. It also performs path compression, making the tree shallower.
+ *
+ * Returns the root node of the set containing node.
+ */
+struct uf_node *uf_find(struct uf_node *node)
+{
+	struct uf_node *parent;
+
+	while (node->parent != node) {
+		parent = node->parent;
+		node->parent = parent->parent;
+		node = parent;
+	}
+	return node;
+}
+
+/**
+ * uf_union - Merge two sets, using union by rank
+ * @node1: the first node
+ * @node2: the second node
+ *
+ * This function merges the sets containing node1 and node2, by comparing
+ * the ranks to keep the tree balanced.
+ */
+void 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;
+
+	if (root1->rank < root2->rank) {
+		root1->parent = root2;
+	} else if (root1->rank > root2->rank) {
+		root2->parent = root1;
+	} else {
+		root2->parent = root1;
+		root1->rank++;
+	}
+}
-- 
2.45.0

On Thu, Jul 04, 2024 at 02:24:43PM +0800, Xavier wrote:
> This patch implements a union-find data structure in the kernel library,
> which includes operations for allocating nodes, freeing nodes,
> finding the root of a node, and merging two nodes.
> 
> Signed-off-by: Xavier <xavier_qy@163.com>

Applied to cgroup/for-6.12.

Thanks.

-- 
tejun

The process of constructing scheduling domains
 involves multiple loops and repeated evaluations, leading to numerous
 redundant and ineffective assessments that impact code efficiency.

Here, we use union-find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.

Signed-off-by: Xavier <xavier_qy@163.com>
---
 kernel/cgroup/cpuset.c | 114 ++++++++++++++++-------------------------
 1 file changed, 44 insertions(+), 70 deletions(-)

diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index fe76045aa5..0037371986 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -45,6 +45,7 @@
 #include <linux/cgroup.h>
 #include <linux/wait.h>
 #include <linux/workqueue.h>
+#include <linux/union_find.h>
 
 DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
 DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
@@ -172,9 +173,6 @@ struct cpuset {
 	 */
 	int attach_in_progress;
 
-	/* partition number for rebuild_sched_domains() */
-	int pn;
-
 	/* for custom sched domain */
 	int relax_domain_level;
 
@@ -208,6 +206,9 @@ struct cpuset {
 
 	/* Remote partition silbling list anchored at remote_children */
 	struct list_head remote_sibling;
+
+	/* Used to merge intersecting subsets for generate_sched_domains */
+	struct uf_node node;
 };
 
 /*
@@ -988,18 +989,15 @@ static inline int nr_cpusets(void)
  *	   were changed (added or removed.)
  *
  * Finding the best partition (set of domains):
- *	The triple nested loops below over i, j, k scan over the
- *	load balanced cpusets (using the array of cpuset pointers in
- *	csa[]) looking for pairs of cpusets that have overlapping
- *	cpus_allowed, but which don't have the same 'pn' partition
- *	number and gives them in the same partition number.  It keeps
- *	looping on the 'restart' label until it can no longer find
- *	any such pairs.
+ *	The double nested loops below over i, j scan over the load
+ *	balanced cpusets (using the array of cpuset pointers in csa[])
+ *	looking for pairs of cpusets that have overlapping cpus_allowed
+ *	and merging them using a union-find algorithm.
+ *
+ *	The union of the cpus_allowed masks from the set of all cpusets
+ *	having the same root then form the one element of the partition
+ *	(one sched domain) to be passed to partition_sched_domains().
  *
- *	The union of the cpus_allowed masks from the set of
- *	all cpusets having the same 'pn' value then form the one
- *	element of the partition (one sched domain) to be passed to
- *	partition_sched_domains().
  */
 static int generate_sched_domains(cpumask_var_t **domains,
 			struct sched_domain_attr **attributes)
@@ -1007,7 +1005,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	struct cpuset *cp;	/* top-down scan of cpusets */
 	struct cpuset **csa;	/* array of all cpuset ptrs */
 	int csn;		/* how many cpuset ptrs in csa so far */
-	int i, j, k;		/* indices for partition finding loops */
+	int i, j;		/* indices for partition finding loops */
 	cpumask_var_t *doms;	/* resulting partition; i.e. sched domains */
 	struct sched_domain_attr *dattr;  /* attributes for custom domains */
 	int ndoms = 0;		/* number of sched domains in result */
@@ -1015,6 +1013,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	struct cgroup_subsys_state *pos_css;
 	bool root_load_balance = is_sched_load_balance(&top_cpuset);
 	bool cgrpv2 = cgroup_subsys_on_dfl(cpuset_cgrp_subsys);
+	int nslot_update;
 
 	doms = NULL;
 	dattr = NULL;
@@ -1102,31 +1101,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	if (root_load_balance && (csn == 1))
 		goto single_root_domain;
 
-	for (i = 0; i < csn; i++)
-		csa[i]->pn = i;
-	ndoms = csn;
-
-restart:
-	/* Find the best partition (set of sched domains) */
-	for (i = 0; i < csn; i++) {
-		struct cpuset *a = csa[i];
-		int apn = a->pn;
-
-		for (j = 0; j < csn; j++) {
-			struct cpuset *b = csa[j];
-			int bpn = b->pn;
-
-			if (apn != bpn && cpusets_overlap(a, b)) {
-				for (k = 0; k < csn; k++) {
-					struct cpuset *c = csa[k];
+	if (!cgrpv2) {
+		for (i = 0; i < csn; i++)
+			uf_node_init(&csa[i]->node);
 
-					if (c->pn == bpn)
-						c->pn = apn;
-				}
-				ndoms--;	/* one less element */
-				goto restart;
+		/* Merge overlapping cpusets */
+		for (i = 0; i < csn; i++) {
+			for (j = i + 1; j < csn; j++) {
+				if (cpusets_overlap(csa[i], csa[j]))
+					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++;
+		}
+	} else {
+		ndoms = csn;
 	}
 
 	/*
@@ -1159,44 +1152,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	}
 
 	for (nslot = 0, i = 0; i < csn; i++) {
-		struct cpuset *a = csa[i];
-		struct cpumask *dp;
-		int apn = a->pn;
-
-		if (apn < 0) {
-			/* Skip completed partitions */
-			continue;
-		}
-
-		dp = doms[nslot];
-
-		if (nslot == ndoms) {
-			static int warnings = 10;
-			if (warnings) {
-				pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
-					nslot, ndoms, csn, i, apn);
-				warnings--;
-			}
-			continue;
-		}
-
-		cpumask_clear(dp);
-		if (dattr)
-			*(dattr + nslot) = SD_ATTR_INIT;
+		nslot_update = 0;
 		for (j = i; j < csn; j++) {
-			struct cpuset *b = csa[j];
-
-			if (apn == b->pn) {
-				cpumask_or(dp, dp, b->effective_cpus);
+			if (uf_find(&csa[j]->node) == &csa[i]->node) {
+				struct cpumask *dp = doms[nslot];
+
+				if (i == j) {
+					nslot_update = 1;
+					cpumask_clear(dp);
+					if (dattr)
+						*(dattr + nslot) = SD_ATTR_INIT;
+				}
+				cpumask_or(dp, dp, csa[j]->effective_cpus);
 				cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN));
 				if (dattr)
-					update_domain_attr_tree(dattr + nslot, b);
-
-				/* Done with this partition */
-				b->pn = -1;
+					update_domain_attr_tree(dattr + nslot, csa[j]);
 			}
 		}
-		nslot++;
+		if (nslot_update)
+			nslot++;
 	}
 	BUG_ON(nslot != ndoms);
 
-- 
2.45.0

On Thu, Jul 04, 2024 at 02:24:44PM +0800, Xavier wrote:
> The process of constructing scheduling domains
>  involves multiple loops and repeated evaluations, leading to numerous
>  redundant and ineffective assessments that impact code efficiency.
> 
> Here, we use union-find to optimize the merging of cpumasks. By employing
> path compression and union by rank, we effectively reduce the number of
> lookups and merge comparisons.
> 
> Signed-off-by: Xavier <xavier_qy@163.com>

Applied to cgroup/for-6.12.

Thanks.

-- 
tejun

On Tue, 2 Jul 2024 09:22:44 -1000 Tejun Heo <tj@kernel.org> wrote:

> On Tue, Jul 02, 2024 at 06:50:08PM +0800, Xavier wrote:
> > Hi Tejun,
> > 
> > Thank you for thoroughly reviewing the code and pointing out the issues.
> > I have made the necessary changes to the code, comments, and documentation
> > based on your suggestions.
> 
> Looks fine to me. Once Waiman is okay with it, I can carry it through the
> cgroup tree. Andrew, any objections? Xavier, it'd really great if you can do
> more conversions so that it's not a single use thing.
> 

OK by me.  cpuset patches live in the cgroup tree, no?

Nit: if there is to be another spin

	/* please do this */
	/*and not this*/

Hello,

On Tue, Jul 02, 2024 at 05:31:37PM -0700, Andrew Morton wrote:
> OK by me.  cpuset patches live in the cgroup tree, no?

Yeah, so, if the cpuset conversion part looks okay, it'd make the sense to
route it through the cgroup tree. Otherwise, we can also route the cpuset
conversion through -mm too. Either way sounds fine to me.

Thanks.

-- 
tejun

This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.

Signed-off-by: Xavier <xavier_qy@163.com>
---
 Documentation/core-api/union_find.rst         | 102 ++++++++++++++++++
 .../zh_CN/core-api/union_find.rst             |  87 +++++++++++++++
 MAINTAINERS                                   |   9 ++
 include/linux/union_find.h                    |  41 +++++++
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  48 +++++++++
 6 files changed, 288 insertions(+), 1 deletion(-)
 create mode 100644 Documentation/core-api/union_find.rst
 create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
 create mode 100644 include/linux/union_find.h
 create mode 100644 lib/union_find.c

diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst
new file mode 100644
index 0000000000..be9f68fd6d
--- /dev/null
+++ b/Documentation/core-api/union_find.rst
@@ -0,0 +1,102 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <xavier_qy@163.com>
+
+What is Union-Find, and what is it used for?
+------------------------------------------------
+
+Union-Find is a data structure used to handle the merging and querying
+of disjoint sets. The primary operations supported by Union-Find are:
+
+	Initialization: Resetting each element as an individual set, with
+		each set's initial parent node pointing to itself.
+	Find: Determine which set a particular element belongs to, usually by
+		returning a “representative element” of that set. This operation
+		is used to check if two elements are in the same set.
+	Union: Merge two sets into one.
+
+As a data structure used to maintain sets (groups), Union-Find is commonly
+utilized to solve problems related to offline queries, dynamic connectivity,
+and graph theory. It is also a key component in Kruskal's algorithm for
+computing the minimum spanning tree, which is crucial in scenarios like
+network routing. Consequently, Union-Find is widely referenced. Additionally,
+Union-Find has applications in symbolic computation, register allocation,
+and more.
+
+Space Complexity: O(n), where n is the number of nodes.
+
+Time Complexity: Using path compression can reduce the time complexity of
+the find operation, and using union by rank can reduce the time complexity
+of the union operation. These optimizations reduce the average time
+complexity of each find and union operation to O(α(n)), where α(n) is the
+inverse Ackermann function. This can be roughly considered a constant time
+complexity for practical purposes.
+
+This document covers use of the Linux union-find implementation.  For more
+information on the nature and implementation of Union-Find,  see:
+
+  Wikipedia entry on union-find
+    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+Linux implementation of union-find
+-----------------------------------
+
+Linux's union-find implementation resides in the file "lib/union_find.c".
+To use it, "#include <linux/union_find.h>".
+
+The Union-Find data structure is defined as follows::
+
+	struct uf_node {
+		struct uf_node *parent;
+		unsigned int rank;
+	};
+
+In this structure, parent points to the parent node of the current node.
+The rank field represents the height of the current tree. During a union
+operation, the tree with the smaller rank is attached under the tree with the
+larger rank to maintain balance.
+
+Initializing Union-Find
+--------------------
+
+You can complete the initialization using either static or initialization
+interface. Initialize the parent pointer to point to itself and set the rank
+to 0.
+Example::
+
+	struct uf_node my_node = UF_INIT_NODE(my_node);
+or
+	uf_node_init(&my_node);
+
+Find the Root Node of Union-Find
+--------------------------------
+
+This operation is mainly used to determine whether two nodes belong to the same
+set in the Union-Find. If they have the same root, they are in the same set.
+During the find operation, path compression is performed to improve the
+efficiency of subsequent find operations.
+Example::
+
+	int connected;
+	struct uf_node *root1 = uf_find(&node_1);
+	struct uf_node *root2 = uf_find(&node_2);
+	if (root1 == root2)
+		connected = 1;
+	else
+		connected = 0;
+
+Union Two Sets in Union-Find
+----------------------------
+
+To union two sets in the Union-Find, you first find their respective root nodes
+and then link the smaller node to the larger node based on the rank of the root
+nodes.
+Example::
+
+	uf_union(&node_1, &node_2);
diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Documentation/translations/zh_CN/core-api/union_find.rst
new file mode 100644
index 0000000000..a56de57147
--- /dev/null
+++ b/Documentation/translations/zh_CN/core-api/union_find.rst
@@ -0,0 +1,87 @@
+.. SPDX-License-Identifier: GPL-2.0
+.. include:: ../disclaimer-zh_CN.rst
+
+:Original: Documentation/core-api/union_find.rst
+
+===========================
+Linux中的并查集（Union-Find）
+===========================
+
+
+:日期: 2024年6月21日
+:作者: Xavier <xavier_qy@163.com>
+
+何为并查集，它有什么用？
+---------------------
+
+并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：
+	初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身
+	查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为
+		了判断两个元素是否在同一个集合之中。
+	合并：将两个集合合并为一个。
+
+并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和
+图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在
+网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分
+配等方面也有应用。
+
+空间复杂度: O(n)，n为节点数。
+
+时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的
+时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿
+克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。
+
+本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：
+
+  维基百科并查集词条
+    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+并查集的Linux实现
+----------------
+
+Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需要
+“#include <linux/union_find.h>”。
+
+并查集的数据结构定义如下::
+
+	struct uf_node {
+		struct uf_node *parent;
+		unsigned int rank;
+	};
+其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大
+的节点下面以增加平衡性。
+
+初始化并查集
+---------
+
+可以采用静态或初始化接口完成初始化操作。初始化时，parent 指针指向自身，rank 设置
+为 0。
+示例::
+
+	struct uf_node my_node = UF_INIT_NODE(my_node);
+或
+	uf_node_init(&my_node);
+
+查找并查集的根节点
+----------------
+
+主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中
+会对路径进行压缩，提高后续查找效率。
+示例::
+
+	int connected;
+	struct uf_node *root1 = uf_find(&node_1);
+	struct uf_node *root2 = uf_find(&node_2);
+	if (root1 == root2)
+		connected = 1;
+	else
+		connected = 0;
+
+合并两个并查集
+-------------
+
+对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的
+节点连接到大的节点下面。
+示例::
+
+	uf_union(&node_1, &node_2);
diff --git a/MAINTAINERS b/MAINTAINERS
index 2ca8f35dfe..16171dbca3 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23051,6 +23051,15 @@ F:	drivers/cdrom/cdrom.c
 F:	include/linux/cdrom.h
 F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <xavier_qy@163.com>
+L:	linux-kernel@vger.kernel.org
+S:	Maintained
+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
+
 UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
 R:	Alim Akhtar <alim.akhtar@samsung.com>
 R:	Avri Altman <avri.altman@wdc.com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..45b7aa66a6
--- /dev/null
+++ b/include/linux/union_find.h
@@ -0,0 +1,41 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+/**
+ * union_find.h - Union-Find data structure implementation
+ *
+ * This header provides functions and structures to implement the Union-Find
+ * data structure. The Union-Find data structure is used to manage disjoint
+ * sets and supports efficient union and find operations.
+ *
+ * See Documentation/core-api/union_find.rst for documentation and samples.
+ */
+
+struct uf_node {
+	struct uf_node *parent;
+	unsigned int rank;
+};
+
+/* This macro is used for static initialization of a union-find node. */
+#define UF_INIT_NODE(node)	{.parent = &node, .rank = 0}
+
+/**
+ * uf_node_init - Initialize a union-find node
+ * @node: pointer to the union-find node to be initialized
+ *
+ * This function sets the parent of the node to itself and
+ * initializes its rank to 0.
+ */
+static inline void uf_node_init(struct uf_node *node)
+{
+	node->parent = node;
+	node->rank = 0;
+}
+
+/* find the root of a 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);
+
+#endif /*__LINUX_UNION_FIND_H*/
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 is_single_threaded.o plist.o decompress.o kobject_uevent.o \
 	 earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
 	 nmi_backtrace.o win_minmax.o memcat_p.o \
-	 buildid.o objpool.o
+	 buildid.o objpool.o union_find.o
 
 lib-$(CONFIG_PRINTK) += dump_stack.o
 lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..bec574ad24
--- /dev/null
+++ b/lib/union_find.c
@@ -0,0 +1,48 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+/**
+ * uf_find - Find the root of a node and perform path compression
+ * @node: the node to find the root of
+ *
+ * This function returns the root of the node by following the parent
+ * pointers. It also performs path compression, making the tree shallower.
+ *
+ * Returns the root node of the set containing node.
+ */
+struct uf_node *uf_find(struct uf_node *node)
+{
+	struct uf_node *parent;
+
+	while (node->parent != node) {
+		parent = node->parent;
+		node->parent = parent->parent;
+		node = parent;
+	}
+	return node;
+}
+
+/**
+ * uf_union - Merge two sets, using union by rank
+ * @node1: the first node
+ * @node2: the second node
+ *
+ * This function merges the sets containing node1 and node2, by comparing
+ * the ranks to keep the tree balanced.
+ */
+void 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) {
+		if (root1->rank < root2->rank) {
+			root1->parent = root2;
+		} else if (root1->rank > root2->rank) {
+			root2->parent = root1;
+		} else {
+			root2->parent = root1;
+			root1->rank++;
+		}
+	}
+}
-- 
2.45.0

The process of constructing scheduling domains
 involves multiple loops and repeated evaluations, leading to numerous
 redundant and ineffective assessments that impact code efficiency.

Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.

Signed-off-by: Xavier <xavier_qy@163.com>
---
 kernel/cgroup/cpuset.c | 95 ++++++++++++++++--------------------------
 1 file changed, 36 insertions(+), 59 deletions(-)

diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index fe76045aa5..4d32cd1407 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -45,6 +45,7 @@
 #include <linux/cgroup.h>
 #include <linux/wait.h>
 #include <linux/workqueue.h>
+#include <linux/union_find.h>
 
 DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
 DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
@@ -172,9 +173,6 @@ struct cpuset {
 	 */
 	int attach_in_progress;
 
-	/* partition number for rebuild_sched_domains() */
-	int pn;
-
 	/* for custom sched domain */
 	int relax_domain_level;
 
@@ -208,6 +206,9 @@ struct cpuset {
 
 	/* Remote partition silbling list anchored at remote_children */
 	struct list_head remote_sibling;
+
+	/* Used to merge intersecting subsets for generate_sched_domains*/
+	struct uf_node node;
 };
 
 /*
@@ -1007,7 +1008,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	struct cpuset *cp;	/* top-down scan of cpusets */
 	struct cpuset **csa;	/* array of all cpuset ptrs */
 	int csn;		/* how many cpuset ptrs in csa so far */
-	int i, j, k;		/* indices for partition finding loops */
+	int i, j;		/* indices for partition finding loops */
 	cpumask_var_t *doms;	/* resulting partition; i.e. sched domains */
 	struct sched_domain_attr *dattr;  /* attributes for custom domains */
 	int ndoms = 0;		/* number of sched domains in result */
@@ -1015,6 +1016,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	struct cgroup_subsys_state *pos_css;
 	bool root_load_balance = is_sched_load_balance(&top_cpuset);
 	bool cgrpv2 = cgroup_subsys_on_dfl(cpuset_cgrp_subsys);
+	int nslot_update;
 
 	doms = NULL;
 	dattr = NULL;
@@ -1102,31 +1104,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	if (root_load_balance && (csn == 1))
 		goto single_root_domain;
 
-	for (i = 0; i < csn; i++)
-		csa[i]->pn = i;
-	ndoms = csn;
-
-restart:
-	/* Find the best partition (set of sched domains) */
-	for (i = 0; i < csn; i++) {
-		struct cpuset *a = csa[i];
-		int apn = a->pn;
+	if (!cgrpv2) {
+		for (i = 0; i < csn; i++)
+			uf_node_init(&csa[i]->node);
 
-		for (j = 0; j < csn; j++) {
-			struct cpuset *b = csa[j];
-			int bpn = b->pn;
-
-			if (apn != bpn && cpusets_overlap(a, b)) {
-				for (k = 0; k < csn; k++) {
-					struct cpuset *c = csa[k];
-
-					if (c->pn == bpn)
-						c->pn = apn;
-				}
-				ndoms--;	/* one less element */
-				goto restart;
+		/* Merge overlapping cpusets */
+		for (i = 0; i < csn; i++) {
+			for (j = i + 1; j < csn; j++) {
+				if (cpusets_overlap(csa[i], csa[j]))
+					uf_union(&csa[i]->node, &csa[j]->node);
 			}
 		}
+
+		/* Count the total number of domains */
+		for (i = 0; i < csn; i++) {
+			if (csa[i]->node.parent == &csa[i]->node)
+				ndoms++;
+		}
+	} else {
+		ndoms = csn;
 	}
 
 	/*
@@ -1159,44 +1155,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	}
 
 	for (nslot = 0, i = 0; i < csn; i++) {
-		struct cpuset *a = csa[i];
-		struct cpumask *dp;
-		int apn = a->pn;
-
-		if (apn < 0) {
-			/* Skip completed partitions */
-			continue;
-		}
-
-		dp = doms[nslot];
-
-		if (nslot == ndoms) {
-			static int warnings = 10;
-			if (warnings) {
-				pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
-					nslot, ndoms, csn, i, apn);
-				warnings--;
-			}
-			continue;
-		}
-
-		cpumask_clear(dp);
-		if (dattr)
-			*(dattr + nslot) = SD_ATTR_INIT;
+		nslot_update = 0;
 		for (j = i; j < csn; j++) {
-			struct cpuset *b = csa[j];
-
-			if (apn == b->pn) {
-				cpumask_or(dp, dp, b->effective_cpus);
+			if (uf_find(&csa[j]->node) == &csa[i]->node) {
+				struct cpumask *dp = doms[nslot];
+
+				if (i == j) {
+					nslot_update = 1;
+					cpumask_clear(dp);
+					if (dattr)
+						*(dattr + nslot) = SD_ATTR_INIT;
+				}
+				cpumask_or(dp, dp, csa[j]->effective_cpus);
 				cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN));
 				if (dattr)
-					update_domain_attr_tree(dattr + nslot, b);
-
-				/* Done with this partition */
-				b->pn = -1;
+					update_domain_attr_tree(dattr + nslot, csa[j]);
 			}
 		}
-		nslot++;
+		if (nslot_update)
+			nslot++;
 	}
 	BUG_ON(nslot != ndoms);
 
-- 
2.45.0

On 7/2/24 06:50, Xavier wrote:
> The process of constructing scheduling domains
>   involves multiple loops and repeated evaluations, leading to numerous
>   redundant and ineffective assessments that impact code efficiency.
>
> Here, we use Union-Find to optimize the merging of cpumasks. By employing
> path compression and union by rank, we effectively reduce the number of
> lookups and merge comparisons.
>
> Signed-off-by: Xavier <xavier_qy@163.com>
> ---
>   kernel/cgroup/cpuset.c | 95 ++++++++++++++++--------------------------
>   1 file changed, 36 insertions(+), 59 deletions(-)
>
> diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
> index fe76045aa5..4d32cd1407 100644
> --- a/kernel/cgroup/cpuset.c
> +++ b/kernel/cgroup/cpuset.c
> @@ -45,6 +45,7 @@
>   #include <linux/cgroup.h>
>   #include <linux/wait.h>
>   #include <linux/workqueue.h>
> +#include <linux/union_find.h>
>   
>   DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
>   DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
> @@ -172,9 +173,6 @@ struct cpuset {
>   	 */
>   	int attach_in_progress;
>   
> -	/* partition number for rebuild_sched_domains() */
> -	int pn;
> -
>   	/* for custom sched domain */
>   	int relax_domain_level;
>   
> @@ -208,6 +206,9 @@ struct cpuset {
>   
>   	/* Remote partition silbling list anchored at remote_children */
>   	struct list_head remote_sibling;
> +
> +	/* Used to merge intersecting subsets for generate_sched_domains*/
> +	struct uf_node node;
>   };
>   
>   /*
> @@ -1007,7 +1008,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
>   	struct cpuset *cp;	/* top-down scan of cpusets */
>   	struct cpuset **csa;	/* array of all cpuset ptrs */
>   	int csn;		/* how many cpuset ptrs in csa so far */
> -	int i, j, k;		/* indices for partition finding loops */
> +	int i, j;		/* indices for partition finding loops */
>   	cpumask_var_t *doms;	/* resulting partition; i.e. sched domains */
>   	struct sched_domain_attr *dattr;  /* attributes for custom domains */
>   	int ndoms = 0;		/* number of sched domains in result */
> @@ -1015,6 +1016,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
>   	struct cgroup_subsys_state *pos_css;
>   	bool root_load_balance = is_sched_load_balance(&top_cpuset);
>   	bool cgrpv2 = cgroup_subsys_on_dfl(cpuset_cgrp_subsys);
> +	int nslot_update;
>   
>   	doms = NULL;
>   	dattr = NULL;
> @@ -1102,31 +1104,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
>   	if (root_load_balance && (csn == 1))
>   		goto single_root_domain;
>   
> -	for (i = 0; i < csn; i++)
> -		csa[i]->pn = i;
> -	ndoms = csn;
> -
> -restart:
> -	/* Find the best partition (set of sched domains) */
> -	for (i = 0; i < csn; i++) {
> -		struct cpuset *a = csa[i];
> -		int apn = a->pn;
> +	if (!cgrpv2) {
> +		for (i = 0; i < csn; i++)
> +			uf_node_init(&csa[i]->node);
>   
> -		for (j = 0; j < csn; j++) {
> -			struct cpuset *b = csa[j];
> -			int bpn = b->pn;
> -
> -			if (apn != bpn && cpusets_overlap(a, b)) {
> -				for (k = 0; k < csn; k++) {
> -					struct cpuset *c = csa[k];
> -
> -					if (c->pn == bpn)
> -						c->pn = apn;
> -				}
> -				ndoms--;	/* one less element */
> -				goto restart;
> +		/* Merge overlapping cpusets */
> +		for (i = 0; i < csn; i++) {
> +			for (j = i + 1; j < csn; j++) {
> +				if (cpusets_overlap(csa[i], csa[j]))
> +					uf_union(&csa[i]->node, &csa[j]->node);
>   			}
>   		}
> +
> +		/* Count the total number of domains */
> +		for (i = 0; i < csn; i++) {
> +			if (csa[i]->node.parent == &csa[i]->node)
> +				ndoms++;
> +		}
> +	} else {
> +		ndoms = csn;
>   	}
>   
>   	/*
> @@ -1159,44 +1155,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
>   	}
>   
>   	for (nslot = 0, i = 0; i < csn; i++) {
> -		struct cpuset *a = csa[i];
> -		struct cpumask *dp;
> -		int apn = a->pn;
> -
> -		if (apn < 0) {
> -			/* Skip completed partitions */
> -			continue;
> -		}
> -
> -		dp = doms[nslot];
> -
> -		if (nslot == ndoms) {
> -			static int warnings = 10;
> -			if (warnings) {
> -				pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
> -					nslot, ndoms, csn, i, apn);
> -				warnings--;
> -			}
> -			continue;
> -		}
> -
> -		cpumask_clear(dp);
> -		if (dattr)
> -			*(dattr + nslot) = SD_ATTR_INIT;
> +		nslot_update = 0;
>   		for (j = i; j < csn; j++) {
> -			struct cpuset *b = csa[j];
> -
> -			if (apn == b->pn) {
> -				cpumask_or(dp, dp, b->effective_cpus);
> +			if (uf_find(&csa[j]->node) == &csa[i]->node) {
> +				struct cpumask *dp = doms[nslot];
> +
> +				if (i == j) {
> +					nslot_update = 1;
> +					cpumask_clear(dp);
> +					if (dattr)
> +						*(dattr + nslot) = SD_ATTR_INIT;
> +				}
> +				cpumask_or(dp, dp, csa[j]->effective_cpus);
>   				cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN));
>   				if (dattr)
> -					update_domain_attr_tree(dattr + nslot, b);
> -
> -				/* Done with this partition */
> -				b->pn = -1;
> +					update_domain_attr_tree(dattr + nslot, csa[j]);
>   			}
>   		}
> -		nslot++;
> +		if (nslot_update)
> +			nslot++;
>   	}
>   	BUG_ON(nslot != ndoms);
>   

The code change looks OK to me. However, the following comment above 
generate_sched_domains() describes the generation process.

  * Finding the best partition (set of domains):
  *      The triple nested loops below over i, j, k scan over the
  *      load balanced cpusets (using the array of cpuset pointers in
  *      csa[]) looking for pairs of cpusets that have overlapping
  *      cpus_allowed, but which don't have the same 'pn' partition
  *      number and gives them in the same partition number.  It keeps
  *      looping on the 'restart' label until it can no longer find
  *      any such pairs.
  *
  *      The union of the cpus_allowed masks from the set of
  *      all cpusets having the same 'pn' value then form the one
  *      element of the partition (one sched domain) to be passed to
  *      partition_sched_domains().

This part is no longer correct with your patch. Would you mind updating 
it to match what your new patch is doing?

BTW, please also incorporate the Andrew's suggestion about the kernel 
convention of writing comments.

Thanks,
Longman

The process of constructing scheduling domains
 involves multiple loops and repeated evaluations, leading to numerous
 redundant and ineffective assessments that impact code efficiency.

Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.

Signed-off-by: Xavier <xavier_qy@163.com>
---
 kernel/cgroup/cpuset.c | 96 ++++++++++++++++--------------------------
 1 file changed, 37 insertions(+), 59 deletions(-)

diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index fe76045aa5..c435814ba8 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -45,6 +45,8 @@
 #include <linux/cgroup.h>
 #include <linux/wait.h>
 #include <linux/workqueue.h>
+#include <linux/union_find.h>
+#include <linux/vmalloc.h>
 
 DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
 DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
@@ -172,9 +174,6 @@ struct cpuset {
 	 */
 	int attach_in_progress;
 
-	/* partition number for rebuild_sched_domains() */
-	int pn;
-
 	/* for custom sched domain */
 	int relax_domain_level;
 
@@ -208,6 +207,9 @@ struct cpuset {
 
 	/* Remote partition silbling list anchored at remote_children */
 	struct list_head remote_sibling;
+
+	/* Used to merge intersecting subsets for generate_sched_domains*/
+	struct uf_node node;
 };
 
 /*
@@ -1007,7 +1009,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	struct cpuset *cp;	/* top-down scan of cpusets */
 	struct cpuset **csa;	/* array of all cpuset ptrs */
 	int csn;		/* how many cpuset ptrs in csa so far */
-	int i, j, k;		/* indices for partition finding loops */
+	int i, j;		/* indices for partition finding loops */
 	cpumask_var_t *doms;	/* resulting partition; i.e. sched domains */
 	struct sched_domain_attr *dattr;  /* attributes for custom domains */
 	int ndoms = 0;		/* number of sched domains in result */
@@ -1015,6 +1017,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	struct cgroup_subsys_state *pos_css;
 	bool root_load_balance = is_sched_load_balance(&top_cpuset);
 	bool cgrpv2 = cgroup_subsys_on_dfl(cpuset_cgrp_subsys);
+	int nslot_update;
 
 	doms = NULL;
 	dattr = NULL;
@@ -1102,31 +1105,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	if (root_load_balance && (csn == 1))
 		goto single_root_domain;
 
-	for (i = 0; i < csn; i++)
-		csa[i]->pn = i;
-	ndoms = csn;
-
-restart:
-	/* Find the best partition (set of sched domains) */
-	for (i = 0; i < csn; i++) {
-		struct cpuset *a = csa[i];
-		int apn = a->pn;
+	if (!cgrpv2) {
+		for (i = 0; i < csn; i++)
+			uf_nodes_init(&csa[i]->node);
 
-		for (j = 0; j < csn; j++) {
-			struct cpuset *b = csa[j];
-			int bpn = b->pn;
-
-			if (apn != bpn && cpusets_overlap(a, b)) {
-				for (k = 0; k < csn; k++) {
-					struct cpuset *c = csa[k];
-
-					if (c->pn == bpn)
-						c->pn = apn;
-				}
-				ndoms--;	/* one less element */
-				goto restart;
+		/* Merge overlapping cpusets */
+		for (i = 0; i < csn; i++) {
+			for (j = i + 1; j < csn; j++) {
+				if (cpusets_overlap(csa[i], csa[j]))
+					uf_union(&csa[i]->node, &csa[j]->node);
 			}
 		}
+
+		/* Count the total number of domains */
+		for (i = 0; i < csn; i++) {
+			if (csa[i]->node.parent == &csa[i]->node)
+				ndoms++;
+		}
+	} else {
+		ndoms = csn;
 	}
 
 	/*
@@ -1159,44 +1156,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	}
 
 	for (nslot = 0, i = 0; i < csn; i++) {
-		struct cpuset *a = csa[i];
-		struct cpumask *dp;
-		int apn = a->pn;
-
-		if (apn < 0) {
-			/* Skip completed partitions */
-			continue;
-		}
-
-		dp = doms[nslot];
-
-		if (nslot == ndoms) {
-			static int warnings = 10;
-			if (warnings) {
-				pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
-					nslot, ndoms, csn, i, apn);
-				warnings--;
-			}
-			continue;
-		}
-
-		cpumask_clear(dp);
-		if (dattr)
-			*(dattr + nslot) = SD_ATTR_INIT;
+		nslot_update = 0;
 		for (j = i; j < csn; j++) {
-			struct cpuset *b = csa[j];
-
-			if (apn == b->pn) {
-				cpumask_or(dp, dp, b->effective_cpus);
+			if (uf_find(&csa[j]->node) == &csa[i]->node) {
+				struct cpumask *dp = doms[nslot];
+
+				if (i == j) {
+					nslot_update = 1;
+					cpumask_clear(dp);
+					if (dattr)
+						*(dattr + nslot) = SD_ATTR_INIT;
+				}
+				cpumask_or(dp, dp, csa[j]->effective_cpus);
 				cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN));
 				if (dattr)
-					update_domain_attr_tree(dattr + nslot, b);
-
-				/* Done with this partition */
-				b->pn = -1;
+					update_domain_attr_tree(dattr + nslot, csa[j]);
 			}
 		}
-		nslot++;
+		if (nslot_update)
+			nslot++;
 	}
 	BUG_ON(nslot != ndoms);
 
-- 
2.45.2

On Sat, Jun 29, 2024 at 12:13:02AM +0800, Xavier wrote:
> The process of constructing scheduling domains
>  involves multiple loops and repeated evaluations, leading to numerous
>  redundant and ineffective assessments that impact code efficiency.
> 
> Here, we use Union-Find to optimize the merging of cpumasks. By employing
> path compression and union by rank, we effectively reduce the number of
> lookups and merge comparisons.
> 
> Signed-off-by: Xavier <xavier_qy@163.com>

Waiman, how do you like this conversion?

Thanks.

-- 
tejun

This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.

Signed-off-by: Xavier <xavier_qy@163.com>
---
 Documentation/core-api/union_find.rst         | 101 ++++++++++++++++++
 .../zh_CN/core-api/union_find.rst             |  86 +++++++++++++++
 MAINTAINERS                                   |   9 ++
 include/linux/union_find.h                    |  24 +++++
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  33 ++++++
 6 files changed, 254 insertions(+), 1 deletion(-)
 create mode 100644 Documentation/core-api/union_find.rst
 create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
 create mode 100644 include/linux/union_find.h
 create mode 100644 lib/union_find.c

diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst
new file mode 100644
index 0000000000..38d63b16e5
--- /dev/null
+++ b/Documentation/core-api/union_find.rst
@@ -0,0 +1,101 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <xavier_qy@163.com>
+
+What is Union-Find, and what is it used for?
+------------------------------------------------
+
+Union-Find is a data structure used to handle the merging and querying
+of disjoint sets. The primary operations supported by Union-Find are:
+
+	Initialization: Resetting each element as an individual set, with
+		each set's initial parent node pointing to itself.
+	Find: Determine which set a particular element belongs to, usually by
+		returning a “representative element” of that set. This operation
+		is used to check if two elements are in the same set.
+	Union: Merge two sets into one.
+
+As a data structure used to maintain sets (groups), Union-Find is commonly
+utilized to solve problems related to offline queries, dynamic connectivity,
+and graph theory. It is also a key component in Kruskal's algorithm for
+computing the minimum spanning tree, which is crucial in scenarios like
+network routing. Consequently, Union-Find is widely referenced. Additionally,
+Union-Find has applications in symbolic computation, register allocation,
+and more.
+
+Space Complexity: O(n), where n is the number of nodes.
+
+Time Complexity: Using path compression can reduce the time complexity of
+the find operation, and using union by rank can reduce the time complexity
+of the union operation. These optimizations reduce the average time
+complexity of each find and union operation to O(α(n)), where α(n) is the
+inverse Ackermann function. This can be roughly considered a constant time
+complexity for practical purposes.
+
+This document covers use of the Linux union-find implementation.  For more
+information on the nature and implementation of Union-Find,  see:
+
+  Wikipedia entry on union-find
+    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+Linux implementation of union-find
+-----------------------------------
+
+Linux's union-find implementation resides in the file "lib/union_find.c".
+To use it, "#include <linux/union_find.h>".
+
+The Union-Find data structure is defined as follows::
+
+	struct uf_node {
+		struct uf_node *parent;
+		unsigned int rank;
+	};
+
+In this structure, parent points to the parent node of the current node.
+The rank field represents the height of the current tree. During a union
+operation, the tree with the smaller rank is attached under the tree with the
+larger rank to maintain balance.
+
+Initializing Union-Find
+--------------------
+
+When initializing the Union-Find data structure, a single pointer to the
+Union-Find instance needs to be passed. Initialize the parent pointer to point
+to itself and set the rank to 0.
+Example::
+
+	struct uf_node *my_node = vzalloc(sizeof(struct uf_node));
+	uf_nodes_init(my_node);
+
+Find the Root Node of Union-Find
+--------------------------------
+
+This operation is mainly used to determine whether two nodes belong to the same
+set in the Union-Find. If they have the same root, they are in the same set.
+During the find operation, path compression is performed to improve the
+efficiency of subsequent find operations.
+Example::
+
+	int connected;
+	struct uf_node *root1 = uf_find(&my_node[0]);
+	struct uf_node *root2 = uf_find(&my_node[1]);
+	if (root1 == root2)
+		connected = 1;
+	else
+		connected = 0;
+
+Union Two Sets in Union-Find
+----------------------------
+
+To union two sets in the Union-Find, you first find their respective root nodes
+and then link the smaller node to the larger node based on the rank of the root
+nodes.
+Example::
+
+	uf_union(&my_node[0], &my_node[1]);
diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Documentation/translations/zh_CN/core-api/union_find.rst
new file mode 100644
index 0000000000..e1b5ae88da
--- /dev/null
+++ b/Documentation/translations/zh_CN/core-api/union_find.rst
@@ -0,0 +1,86 @@
+.. SPDX-License-Identifier: GPL-2.0
+.. include:: ../disclaimer-zh_CN.rst
+
+:Original: Documentation/core-api/union_find.rst
+
+===========================
+Linux中的并查集（Union-Find）
+===========================
+
+
+:日期: 2024年6月21日
+:作者: Xavier <xavier_qy@163.com>
+
+何为并查集，它有什么用？
+---------------------
+
+并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：
+	初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身
+	查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为
+		了判断两个元素是否在同一个集合之中。
+	合并：将两个集合合并为一个。
+
+并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和
+图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在
+网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分
+配等方面也有应用。
+
+空间复杂度: O(n)，n为节点数。
+
+时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的
+时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿
+克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。
+
+本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：
+
+  维基百科并查集词条
+    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+并查集的Linux实现
+----------------
+
+Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需要
+“#include <linux/union_find.h>”。
+
+并查集的数据结构定义如下::
+
+	struct uf_node {
+		struct uf_node *parent;
+		unsigned int rank;
+	};
+其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大
+的节点下面以增加平衡性。
+
+初始化并查集
+---------
+
+初始化并查集时需要传入并查集实例的一个指针。初始化时，parent 指针指向自身，rank 设置
+为 0。
+示例::
+
+	struct uf_node *my_node = vzalloc(sizeof(struct uf_node));
+	uf_nodes_init(my_node);
+
+查找并查集的根节点
+----------------
+
+主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中
+会对路径进行压缩，提高后续查找效率。
+示例::
+
+	int connected;
+	struct uf_node *root1 = uf_find(&my_node[0]);
+	struct uf_node *root2 = uf_find(&my_node[1]);
+	if (root1 == root2)
+		connected = 1;
+	else
+		connected = 0;
+
+合并两个并查集
+-------------
+
+对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的
+节点连接到大的节点下面。
+示例::
+
+	uf_union(&my_node[0], &my_node[1]);
diff --git a/MAINTAINERS b/MAINTAINERS
index d6c90161c7..a1a467c591 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23054,6 +23054,15 @@ F:	drivers/cdrom/cdrom.c
 F:	include/linux/cdrom.h
 F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <xavier_qy@163.com>
+L:	linux-kernel@vger.kernel.org
+S:	Maintained
+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
+
 UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
 R:	Alim Akhtar <alim.akhtar@samsung.com>
 R:	Avri Altman <avri.altman@wdc.com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..56571c93a5
--- /dev/null
+++ b/include/linux/union_find.h
@@ -0,0 +1,24 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+
+/* Define a union-find node struct */
+struct uf_node {
+	struct uf_node *parent;
+	unsigned int rank;
+};
+
+/* Allocate nodes and initialize to 0 */
+static inline void uf_nodes_init(struct uf_node *node)
+{
+	node->parent = node;
+	node->rank = 0;
+}
+
+/* find the root of a 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);
+
+#endif /*__LINUX_UNION_FIND_H*/
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 is_single_threaded.o plist.o decompress.o kobject_uevent.o \
 	 earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
 	 nmi_backtrace.o win_minmax.o memcat_p.o \
-	 buildid.o objpool.o
+	 buildid.o objpool.o union_find.o
 
 lib-$(CONFIG_PRINTK) += dump_stack.o
 lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..bb48b4b129
--- /dev/null
+++ b/lib/union_find.c
@@ -0,0 +1,33 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+struct uf_node *uf_find(struct uf_node *node)
+{
+	struct uf_node *parent;
+
+	/*Find the root node and perform path compression at the same time*/
+	while (node->parent != node) {
+		parent = node->parent;
+		node->parent = parent->parent;
+		node = parent;
+	}
+	return node;
+}
+
+/*Function to merge two sets, using union by rank*/
+void 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) {
+		if (root1->rank < root2->rank) {
+			root1->parent = root2;
+		} else if (root1->rank > root2->rank) {
+			root2->parent = root1;
+		} else {
+			root2->parent = root1;
+			root1->rank++;
+		}
+	}
+}
-- 
2.45.2

The process of constructing scheduling domains
 involves multiple loops and repeated evaluations, leading to numerous
 redundant and ineffective assessments that impact code efficiency.

Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.

Signed-off-by: Xavier <xavier_qy@163.com>
---
 kernel/cgroup/cpuset.c | 99 +++++++++++++++++-------------------------
 1 file changed, 41 insertions(+), 58 deletions(-)

diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index fe76045aa5..d459cfddcb 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -45,6 +45,8 @@
 #include <linux/cgroup.h>
 #include <linux/wait.h>
 #include <linux/workqueue.h>
+#include <linux/union_find.h>
+#include <linux/vmalloc.h>
 
 DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
 DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
@@ -172,9 +174,6 @@ struct cpuset {
 	 */
 	int attach_in_progress;
 
-	/* partition number for rebuild_sched_domains() */
-	int pn;
-
 	/* for custom sched domain */
 	int relax_domain_level;
 
@@ -1007,7 +1006,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	struct cpuset *cp;	/* top-down scan of cpusets */
 	struct cpuset **csa;	/* array of all cpuset ptrs */
 	int csn;		/* how many cpuset ptrs in csa so far */
-	int i, j, k;		/* indices for partition finding loops */
+	int i, j;		/* indices for partition finding loops */
 	cpumask_var_t *doms;	/* resulting partition; i.e. sched domains */
 	struct sched_domain_attr *dattr;  /* attributes for custom domains */
 	int ndoms = 0;		/* number of sched domains in result */
@@ -1015,6 +1014,8 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	struct cgroup_subsys_state *pos_css;
 	bool root_load_balance = is_sched_load_balance(&top_cpuset);
 	bool cgrpv2 = cgroup_subsys_on_dfl(cpuset_cgrp_subsys);
+	struct uf_node *nodes = NULL;
+	int nslot_update;
 
 	doms = NULL;
 	dattr = NULL;
@@ -1102,31 +1103,29 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	if (root_load_balance && (csn == 1))
 		goto single_root_domain;
 
-	for (i = 0; i < csn; i++)
-		csa[i]->pn = i;
-	ndoms = csn;
-
-restart:
-	/* Find the best partition (set of sched domains) */
-	for (i = 0; i < csn; i++) {
-		struct cpuset *a = csa[i];
-		int apn = a->pn;
-
-		for (j = 0; j < csn; j++) {
-			struct cpuset *b = csa[j];
-			int bpn = b->pn;
+	if (!cgrpv2) {
+		nodes = vzalloc(sizeof(struct uf_node) * csn);
+		if (!nodes)
+			goto done;
 
-			if (apn != bpn && cpusets_overlap(a, b)) {
-				for (k = 0; k < csn; k++) {
-					struct cpuset *c = csa[k];
+		for (i = 0; i < csn; i++)
+			uf_nodes_init(&nodes[i]);
 
-					if (c->pn == bpn)
-						c->pn = apn;
-				}
-				ndoms--;	/* one less element */
-				goto restart;
+		/* Merge overlapping cpusets */
+		for (i = 0; i < csn; i++) {
+			for (j = i + 1; j < csn; j++) {
+				if (cpusets_overlap(csa[i], csa[j]))
+					uf_union(&nodes[i], &nodes[j]);
 			}
 		}
+
+		/* Count the total number of domains */
+		for (i = 0; i < csn; i++) {
+			if (nodes[i].parent == &nodes[i])
+				ndoms++;
+		}
+	} else {
+		ndoms = csn;
 	}
 
 	/*
@@ -1159,48 +1158,32 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	}
 
 	for (nslot = 0, i = 0; i < csn; i++) {
-		struct cpuset *a = csa[i];
-		struct cpumask *dp;
-		int apn = a->pn;
-
-		if (apn < 0) {
-			/* Skip completed partitions */
-			continue;
-		}
-
-		dp = doms[nslot];
-
-		if (nslot == ndoms) {
-			static int warnings = 10;
-			if (warnings) {
-				pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
-					nslot, ndoms, csn, i, apn);
-				warnings--;
-			}
-			continue;
-		}
-
-		cpumask_clear(dp);
-		if (dattr)
-			*(dattr + nslot) = SD_ATTR_INIT;
+		nslot_update = 0;
 		for (j = i; j < csn; j++) {
-			struct cpuset *b = csa[j];
-
-			if (apn == b->pn) {
-				cpumask_or(dp, dp, b->effective_cpus);
+			if (uf_find(&nodes[j]) == &nodes[i]) {
+				struct cpumask *dp = doms[nslot];
+
+				if (i == j) {
+					nslot_update = 1;
+					cpumask_clear(dp);
+					if (dattr)
+						*(dattr + nslot) = SD_ATTR_INIT;
+				}
+				cpumask_or(dp, dp, csa[j]->effective_cpus);
 				cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN));
 				if (dattr)
-					update_domain_attr_tree(dattr + nslot, b);
-
-				/* Done with this partition */
-				b->pn = -1;
+					update_domain_attr_tree(dattr + nslot, csa[j]);
 			}
 		}
-		nslot++;
+		if (nslot_update)
+			nslot++;
 	}
 	BUG_ON(nslot != ndoms);
 
 done:
+	if (nodes)
+		vfree(nodes);
+
 	kfree(csa);
 
 	/*
-- 
2.45.2