Skip to contentSkip to conversation

cpuset: Optimize the number of iterations in the scheduling domain construction process

PATCH In review Xavier 6 participants 52 messages May 31, 2024 – Jul 30, 2024

Subsystems (6)
lore
Share & tools
lore

Xavier

author
#0 lore raw

PATCH v2 1/1 cpuset: Optimize the number of iterations in the scheduling domain construction process

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.

---
 kernel/cgroup/cpuset.c | 117 +++++++++++++++++++++++------------------
 1 file changed, 66 insertions(+), 51 deletions(-)
kernel/cgroup/cpuset.c +66 -51
index c12b9fdb2..4bea1c2db 100644
@@ -891,6 +891,44 @@ static inline int nr_cpusets(void)
 	return static_key_count(&cpusets_enabled_key.key) + 1;
 }
 
+/*define a union find node struct*/
+struct uf_node {
+	int parent;
+	int rank;
+};
+
+static int find_root(struct uf_node *nodes, int x)
+{
+	int root = x;
+	int parent;
+
+	/*Find the root node and perform path compression at the same time*/
+	while (nodes[root].parent != root) {
+		parent = nodes[root].parent;
+		nodes[root].parent = nodes[parent].parent;
+		root = parent;
+	}
+	return root;
+}
+
+/*Function to merge two sets, using union by rank*/
+static void union_sets(struct uf_node *nodes, int a, int b)
+{
+	int root_a = find_root(nodes, a);
+	int root_b = find_root(nodes, b);
+
+	if (root_a != root_b) {
+		if (nodes[root_a].rank < nodes[root_b].rank) {
+			nodes[root_a].parent = root_b;
+		} else if (nodes[root_a].rank > nodes[root_b].rank) {
+			nodes[root_b].parent = root_a;
+		} else {
+			nodes[root_b].parent = root_a;
+			nodes[root_a].rank++;
+		}
+	}
+}
+
 /*
  * generate_sched_domains()
  *
@@ -950,13 +988,14 @@ 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 */
 	int nslot;		/* next empty doms[] struct cpumask slot */
 	struct cgroup_subsys_state *pos_css;
 	bool root_load_balance = is_sched_load_balance(&top_cpuset);
+	struct uf_node *nodes;
 
 	doms = NULL;
 	dattr = NULL;
@@ -1022,33 +1061,31 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	}
 	rcu_read_unlock();
 
-	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;
+	nodes = kmalloc_array(csn, sizeof(struct uf_node), GFP_KERNEL);
+	if (!nodes)
+		goto done;
 
-		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];
+	/* Each node is initially its own parent */
+	for (i = 0; i < csn; i++) {
+		nodes[i].parent = i;
+		nodes[i].rank = 0;
+	}
 
-					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]))
+				union_sets(nodes, i, j);
 		}
 	}
 
+	/* Calculate the number of domains after merging */
+	for (i = 0; i < csn; i++) {
+		if (nodes[i].parent == i)
+			ndoms++;
+	}
+
 	/*
 	 * Now we know how many domains to create.
 	 * Convert <csn, csa> to <ndoms, doms> and populate cpu masks.
@@ -1065,47 +1102,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
 			      GFP_KERNEL);
 
 	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;
-		}
+		struct cpumask *dp = doms[nslot];
 
 		cpumask_clear(dp);
 		if (dattr)
 			*(dattr + nslot) = SD_ATTR_INIT;
 		for (j = i; j < csn; j++) {
-			struct cpuset *b = csa[j];
+			if (find_root(nodes, j) == i) {
+				if (i == j)
+					nslot++;
 
-			if (apn == b->pn) {
-				cpumask_or(dp, dp, b->effective_cpus);
+				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++;
 	}
 	BUG_ON(nslot != ndoms);
-
+	kfree(nodes);
 done:
 	kfree(csa);
 
Signature · 1 line
2.34.1
maintainer
#1 lore raw
Quoted 176 lines · Xavier

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.

---
  kernel/cgroup/cpuset.c | 117 +++++++++++++++++++++++------------------
  1 file changed, 66 insertions(+), 51 deletions(-)
kernel/cgroup/cpuset.c +65 -49
index c12b9fdb2..4bea1c2db 100644
@@ -891,6 +891,44 @@ static inline int nr_cpusets(void)
  	return static_key_count(&cpusets_enabled_key.key) + 1;
  }
 
+/*define a union find node struct*/
+struct uf_node {
+	int parent;
+	int rank;
+};
+
+static int find_root(struct uf_node *nodes, int x)
+{
+	int root = x;
+	int parent;
+
+	/*Find the root node and perform path compression at the same time*/
+	while (nodes[root].parent != root) {
+		parent = nodes[root].parent;
+		nodes[root].parent = nodes[parent].parent;
+		root = parent;
+	}
+	return root;
+}
+
+/*Function to merge two sets, using union by rank*/
+static void union_sets(struct uf_node *nodes, int a, int b)
+{
+	int root_a = find_root(nodes, a);
+	int root_b = find_root(nodes, b);
+
+	if (root_a != root_b) {
+		if (nodes[root_a].rank < nodes[root_b].rank) {
+			nodes[root_a].parent = root_b;
+		} else if (nodes[root_a].rank > nodes[root_b].rank) {
+			nodes[root_b].parent = root_a;
+		} else {
+			nodes[root_b].parent = root_a;
+			nodes[root_a].rank++;
+		}
+	}
+}
+
  /*
   * generate_sched_domains()
   *
@@ -950,13 +988,14 @@ 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 */
  	int nslot;		/* next empty doms[] struct cpumask slot */
  	struct cgroup_subsys_state *pos_css;
  	bool root_load_balance = is_sched_load_balance(&top_cpuset);
+	struct uf_node *nodes;
 
  	doms = NULL;
  	dattr = NULL;
@@ -1022,33 +1061,31 @@ static int generate_sched_domains(cpumask_var_t **domains,
  	}
  	rcu_read_unlock();
 
-	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;
+	nodes = kmalloc_array(csn, sizeof(struct uf_node), GFP_KERNEL);
+	if (!nodes)
+		goto done;
 
-		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];
+	/* Each node is initially its own parent */
+	for (i = 0; i < csn; i++) {
+		nodes[i].parent = i;
+		nodes[i].rank = 0;
+	}
 
-					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]))
+				union_sets(nodes, i, j);
  		}
  	}
 
+	/* Calculate the number of domains after merging */
+	for (i = 0; i < csn; i++) {
+		if (nodes[i].parent == i)
+			ndoms++;
+	}
+
  	/*
  	 * Now we know how many domains to create.
  	 * Convert <csn, csa> to <ndoms, doms> and populate cpu masks.
@@ -1065,47 +1102,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
  			      GFP_KERNEL);
 
  	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;
-		}
+		struct cpumask *dp = doms[nslot];
 
  		cpumask_clear(dp);
  		if (dattr)
  			*(dattr + nslot) = SD_ATTR_INIT;
  		for (j = i; j < csn; j++) {
-			struct cpuset *b = csa[j];
+			if (find_root(nodes, j) == i) {
+				if (i == j)
+					nslot++;
 
-			if (apn == b->pn) {
-				cpumask_or(dp, dp, b->effective_cpus);
+				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]);

kernel/cgroup/cpuset.c static int generate_sched_domains(cpumask_var_t **domains, · line 1126

Quoted 10 lines
kernel/cgroup/cpuset.c +1 -2
  			}
  		}
-		nslot++;
  	}
  	BUG_ON(nslot != ndoms);
-
+	kfree(nodes);
  done:
  	kfree(csa);
 

I have several issues with this patch.

1) The function comment describes the algorithm to find the set of domains. If you change the algorithm, you have to update the comment as well.

2) generate_sched_domains() is not in a performance critical path, so its performance is not as important. Also the csn array is typically not that big. Changing the algorithm may introduce new bugs which leads to the next point.

3) How do you test your code to ensure its correctness?

I applied your patch and run the ./test_cpuset_prs.sh got the following:

[   87.850866] BUG: kernel NULL pointer dereference, address: 0000000000000000
[   87.857832] #PF: supervisor write access in kernel mode
[   87.863067] #PF: error_code(0x0002) - not-present page
[   87.868203] PGD 0 P4D 0
[   87.870745] Oops: 0002 [#1] PREEMPT SMP NOPTI
[   87.875105] CPU: 34 PID: 8789 Comm: test_cpuset_prs Kdump: loaded Not tainted 6.9.0-rc2-test+ #12
[   87.883976] Hardware name: Intel Corporation S2600WFD/S2600WFD, BIOS SE5C620.86B.0X.02.0001.043020191705 04/30/2019
[   87.894402] RIP: 0010:memset_orig+0x72/0xb0
[   87.898597] Code: 47 28 48 89 47 30 48 89 47 38 48 8d 7f 40 75 d8 0f 1f 84 00 00 00 00 00 89 d1 83 e1 38 74 14 c1 e9 03 66 0f 1f 44 00 00 ff c9 <48> 89 07 48 8d 7f 08 75 f5 83 e2 07 74 0a ff ca 88 07 48 8d 7f 01 [   87.917343] RSP: 0018:ffffa1b2a29b7d28 EFLAGS: 00010202
[   87.922568] RAX: 0000000000000000 RBX: 0000000000000002 RCX: 0000000000000001
[   87.929701] RDX: 0000000000000010 RSI: 0000000000000000 RDI: 0000000000000000
[   87.936834] RBP: ffff9184d9647620 R08: 0000000000000008 R09: 0000000000000000
[   87.943967] R10: 0000000000000000 R11: 0000000000000001 R12: 0000000000000002
[   87.951100] R13: 0000000000000000 R14: ffff9184ccca5798 R15: 0000000000000003
[   87.958231] FS:  00007fb51944a740(0000) GS:ffff91947eb00000(0000) knlGS:0000000000000000
[   87.966316] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[   87.972061] CR2: 0000000000000000 CR3: 000000109627c005 CR4: 00000000007706f0
[   87.979194] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
[   87.986327] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
[   87.993460] PKRU: 55555554
[   87.996174] Call Trace:
[   87.998626]  <TASK>
[   88.000733]  ? __die+0x24/0x70
[   88.003802]  ? page_fault_oops+0x14a/0x510
[   88.007909]  ? __schedule+0x3d1/0x1710
[   88.011659]  ? exc_page_fault+0x77/0x170
[   88.015584]  ? asm_exc_page_fault+0x26/0x30
[   88.019772]  ? memset_orig+0x72/0xb0
[   88.023349]  rebuild_sched_domains_locked+0x4f5/0x920
[   88.028403]  update_prstate+0x137/0x4e0
[   88.032245]  sched_partition_write+0x96/0x180
[   88.036613]  kernfs_fop_write_iter+0x12c/0x1c0
[   88.041067]  vfs_write+0x30c/0x430
[   88.044481]  ksys_write+0x63/0xe0
[   88.047801]  do_syscall_64+0x87/0x170
[   88.051474]  ? exc_page_fault+0x77/0x170
[   88.055400]  entry_SYSCALL_64_after_hwframe+0x71/0x79
[   88.060453] RIP: 0033:0x7fb5192fda57
[   88.064047] Code: 0f 00 f7 d8 64 89 02 48 c7 c0 ff ff ff ff eb b7 0f 1f 00 f3 0f 1e fa 64 8b 04 25 18 00 00 00 85 c0 75 10 b8 01 00 00 00 0f 05 <48> 3d 00 f0 ff ff 77 51 c3 48 83 ec 28 48 89 54 24 18 48 89 74 24 [   88.082794] RSP: 002b:00007ffc6e57d2d8 EFLAGS: 00000246 ORIG_RAX: 0000000000000001
[   88.090361] RAX: ffffffffffffffda RBX: 0000000000000007 RCX: 00007fb5192fda57
[   88.097490] RDX: 0000000000000007 RSI: 000055aee3c38f40 RDI: 0000000000000001
[   88.104623] RBP: 000055aee3c38f40 R08: 0000000000000000 R09: 00007fb5193b14e0
[   88.111757] R10: 00007fb5193b13e0 R11: 0000000000000246 R12: 0000000000000007
[   88.118890] R13: 00007fb5193fb780 R14: 0000000000000007 R15: 00007fb5193f69e0
[   88.126024]  </TASK>

So it is not ready for prime time yet.

Regards,
Longman

author
#2 lore raw

PATCH v3 1/1 cpuset: use Union-Find to optimize the merging of cpumasks

In reply to Xavier

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.

Hi Longman,

Thank you for your feedback on the previous version of the patch.

Now I will respond to the three questions you raised:
1) The function comment describes the algorithm to find the set of domains. If you change the algorithm, you have to update the comment as well.

Reply: Sorry for not paying attention to the comments before. The new patch (v3) has updated the comment content.

2) generate_sched_domains() is not in a performance critical path, so its performance is not as important. Also the csn array is typically not that big. Changing the algorithm may introduce new bugs which leads to the next point.

Reply: Indeed, this function is not a critical path impacting performance, but it's always good to optimize efficiency. The optimization is limited to the internals of this function and does not affect other modules, so fixing the internal bug should have manageable risks.

3) How do you test your code to ensure its correctness?
I applied your patch and run the ./test_cpuset_prs.sh got the following...

Reply: I'm very sorry, this is my first time submitting a kernel patch and I don't know which test cases need to be run. I just constructed some scenarios locally to test, so the testing scope is limited. Thank you for providing the test cases. I have reproduced and resolved the issue, and have passed several other test cases in CGroup. But currently, I only have QEMU simulation environment, so my testing ability is limited. I hope you can help me with some comprehensive testing of my new version patch. Thank you very much.

I hope you can pay further attention to the new patch.

Best regards,
Xavier

---
 kernel/cgroup/cpuset.c | 148 +++++++++++++++++++++++------------------
 1 file changed, 82 insertions(+), 66 deletions(-)
kernel/cgroup/cpuset.c +82 -66
index c12b9fdb2..c2d030a30 100644
@@ -891,6 +891,44 @@ static inline int nr_cpusets(void)
 	return static_key_count(&cpusets_enabled_key.key) + 1;
 }
 
+/*define a union find node struct*/
+struct uf_node {
+	int parent;
+	int rank;
+};
+
+static int find_root(struct uf_node *nodes, int x)
+{
+	int root = x;
+	int parent;
+
+	/*Find the root node and perform path compression at the same time*/
+	while (nodes[root].parent != root) {
+		parent = nodes[root].parent;
+		nodes[root].parent = nodes[parent].parent;
+		root = parent;
+	}
+	return root;
+}
+
+/*Function to merge two sets, using union by rank*/
+static void union_sets(struct uf_node *nodes, int a, int b)
+{
+	int root_a = find_root(nodes, a);
+	int root_b = find_root(nodes, b);
+
+	if (root_a != root_b) {
+		if (nodes[root_a].rank < nodes[root_b].rank) {
+			nodes[root_a].parent = root_b;
+		} else if (nodes[root_a].rank > nodes[root_b].rank) {
+			nodes[root_b].parent = root_a;
+		} else {
+			nodes[root_b].parent = root_a;
+			nodes[root_a].rank++;
+		}
+	}
+}
+
 /*
  * generate_sched_domains()
  *
@@ -930,17 +968,13 @@ static inline int nr_cpusets(void)
  *	   value to determine what partition elements (sched domains)
  *	   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.
+ *  By creating a union-find data structure for all load-balanced cpusets,
+ *  cpusets with overlapping cpus_allowed are found and marked with the
+ *  same parent node. Path compression is performed during the search to
+ *  improve comparison efficiency.
  *
  *	The union of the cpus_allowed masks from the set of
- *	all cpusets having the same 'pn' value then form the one
+ *	all cpusets having the same parent then form the one
  *	element of the partition (one sched domain) to be passed to
  *	partition_sched_domains().
  */
@@ -950,13 +984,15 @@ 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 */
 	int nslot;		/* next empty doms[] struct cpumask slot */
 	struct cgroup_subsys_state *pos_css;
 	bool root_load_balance = is_sched_load_balance(&top_cpuset);
+	struct uf_node *nodes;
+	int nslot_update;
 
 	doms = NULL;
 	dattr = NULL;
@@ -1022,40 +1058,38 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	}
 	rcu_read_unlock();
 
-	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;
+	nodes = kmalloc_array(csn, sizeof(struct uf_node), GFP_KERNEL);
+	if (!nodes)
+		goto done;
 
-		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];
+	/* Each node is initially its own parent */
+	for (i = 0; i < csn; i++) {
+		nodes[i].parent = i;
+		nodes[i].rank = 0;
+	}
 
-					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]))
+				union_sets(nodes, i, j);
 		}
 	}
 
+	/* Calculate the number of domains after merging */
+	for (i = 0; i < csn; i++) {
+		if (nodes[i].parent == i)
+			ndoms++;
+	}
+
 	/*
 	 * Now we know how many domains to create.
 	 * Convert <csn, csa> to <ndoms, doms> and populate cpu masks.
 	 */
 	doms = alloc_sched_domains(ndoms);
 	if (!doms)
-		goto done;
+		goto free;
 
 	/*
 	 * The rest of the code, including the scheduler, can deal with
@@ -1065,47 +1099,29 @@ static int generate_sched_domains(cpumask_var_t **domains,
 			      GFP_KERNEL);
 
 	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 (find_root(nodes, j) == 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);
-
+free:
+	kfree(nodes);
 done:
 	kfree(csa);
 
Signature · 1 line
2.34.1
maintainer
#3 lore raw

Re: [PATCH v3] cpuset: use Union-Find to optimize the merging of cpumasks

Quoted 19 lines · Xavier

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.

Hi Longman,

Thank you for your feedback on the previous version of the patch.

Now I will respond to the three questions you raised:
1) The function comment describes the algorithm to find the set of domains. If you change the algorithm, you have to update the comment as well.

Quoted 8 lines

Reply: Sorry for not paying attention to the comments before. The new patch (v3) has updated the comment content.

2) generate_sched_domains() is not in a performance critical path, so its performance is not as important. Also the csn array is typically not that big. Changing the algorithm may introduce new bugs which leads to the next point.

Reply: Indeed, this function is not a critical path impacting performance, but it's always good to optimize efficiency. The optimization is limited to the internals of this function and does not affect other modules, so fixing the internal bug should have manageable risks.

In term of efficiency, your patch does eliminate the third iteration (k) in the csn iteration loop. However the new union_sets() function may go up the node hierarchy which can considered a third iteration in some way. So there is some saving, but not as significant as it looks. It does simplify the code and make it a bit easier to read.

Quoted 7 lines

3) How do you test your code to ensure its correctness?
I applied your patch and run the ./test_cpuset_prs.sh got the following...

Reply: I'm very sorry, this is my first time submitting a kernel patch and I don't know which test cases need to be run. I just constructed some scenarios locally to test, so the testing scope is limited. Thank you for providing the test cases. I have reproduced and resolved the issue, and have passed several other test cases in CGroup. But currently, I only have QEMU simulation environment, so my testing ability is limited. I hope you can help me with some comprehensive testing of my new version patch. Thank you very much.

I hope you can pay further attention to the new patch.

Also your patch eliminates all the use of the cpuset->pn variable. So you cab remove it as it is no longer needed.

After a harder look at the generate_sched_domains() code, I have found a bug in the code with respect to the support of remote partition. I will send another patch to fix it. I also realize that the function was originally designed to support v1 cpuset. v2 cpuset is quite different and the code can be simplified for the v2 use case.

You are welcome to send a v4 patch on top of the new cpuset code base.

Thanks,
Longman

maintainer
#4 lore raw

Re: [PATCH v3] cpuset: use Union-Find to optimize the merging of cpumasks

In reply to Xavier

Hello.

Quoted 7 lines · Xavier

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.

Nice that you found such an application. (As Waiman wrote, the efficiency is not so important here and it may not be dencreased but I still think it makes the code more understandable by using standard data structures.)

Have you looked whether there are other instances of U-F in the kernel? (My quick search didn't show any.) Still, I think it'd be a good idea to decouple this into two commits -- 1) implementation of the new U-F (into lib/), 2) application within cpuset.

kernel/cgroup/cpuset.c static inline int nr_cpusets(void) · line 896

Quoted 3 lines
kernel/cgroup/cpuset.c +3 -0
+/*define a union find node struct*/
+struct uf_node {
+	int parent;

I think this would be better as struct uf_node *.

kernel/cgroup/cpuset.c static inline int nr_cpusets(void) · line 898

Quoted 2 lines
kernel/cgroup/cpuset.c +2 -0
+	int rank;
+};

unsigned int if rank cannot be negative?

kernel/cgroup/cpuset.c static int generate_sched_domains(cpumask_var_t **domains, · line 1070

Quoted 5 lines
kernel/cgroup/cpuset.c +5 -0
+	/* Each node is initially its own parent */
+	for (i = 0; i < csn; i++) {
+		nodes[i].parent = i;
+		nodes[i].rank = 0;
+	}

With the suggestion above, nodes could start with parent = NULL and self-parent be corrected during the first find_root -- thus whole array could be simply init'd to zeroes with kzalloc.

My 0.02€,
Michal

maintainer
#5 lore raw

v4 cover cpuset: use Union-Find to optimize

In reply to Xavier

Hi all,

According to Michal's suggestion, I have divided the patch into two
separate submissions.
Kindly review.

By the way,I changed my email from "[email protected]" to "[email protected]" because the previous one was inconvenient to use.

Best Regards,
Xavier

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

 MAINTAINERS                |  7 +++
 include/linux/union_find.h | 30 ++++++++++++
 kernel/cgroup/cpuset.c     | 95 ++++++++++++++------------------------
 lib/Makefile               |  2 +-
 lib/union_find.c           | 38 +++++++++++++++
 5 files changed, 110 insertions(+), 62 deletions(-)
 create mode 100644 include/linux/union_find.h
 create mode 100644 lib/union_find.c
Signature · 1 line
2.45.2
maintainer
#6 lore raw

PATCH v4 1/2 Union-Find: add a new module in kernel library

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.

---
 MAINTAINERS                |  7 +++++++
 include/linux/union_find.h | 30 ++++++++++++++++++++++++++++++
 lib/Makefile               |  2 +-
 lib/union_find.c           | 38 ++++++++++++++++++++++++++++++++++++++
 4 files changed, 76 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/union_find.h
 create mode 100644 lib/union_find.c
MAINTAINERS +7 -0
index d6c90161c7..602d8c6f42 100644
@@ -23054,6 +23054,13 @@ F:	drivers/cdrom/cdrom.c
 F:	include/linux/cdrom.h
 F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <[email protected]>
+L:	[email protected]
+S:	Maintained
+F:	include/linux/union_find.h
+F:	lib/union_find.c
+
 UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
 R:	Alim Akhtar <[email protected]>
 R:	Avri Altman <[email protected]>
include/linux/union_find.h new file +30 -0
new file mode 100644
index 0000000000..67e9f62bb3
@@ -0,0 +1,30 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+#include <linux/slab.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 struct uf_node *uf_nodes_alloc(unsigned int node_num)
+{
+	return kzalloc(sizeof(struct uf_node) * node_num, GFP_KERNEL);
+}
+
+/* Free nodes*/
+static inline void uf_nodes_free(struct uf_node *nodes)
+{
+	kfree(nodes);
+}
+
+/* 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*/
lib/Makefile +1 -1
index 3b17690456..e1769e6f03 100644
@@ -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
lib/union_find.c new file +38 -0
new file mode 100644
index 0000000000..2f77bae1ca
@@ -0,0 +1,38 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+struct uf_node *uf_find(struct uf_node *node)
+{
+	struct uf_node *parent;
+
+	if (!node->parent) {
+		node->parent = node;
+		return node;
+	}
+
+	/*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++;
+		}
+	}
+}
Signature · 1 line
2.45.2
maintainer
#7 lore raw

Re: [PATCH v4 v4 1/2] Union-Find: add a new module in kernel library

Quoted 87 lines · Xavier

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.

---
  MAINTAINERS                |  7 +++++++
  include/linux/union_find.h | 30 ++++++++++++++++++++++++++++++
  lib/Makefile               |  2 +-
  lib/union_find.c           | 38 ++++++++++++++++++++++++++++++++++++++
  4 files changed, 76 insertions(+), 1 deletion(-)

create mode 100644 include/linux/union_find.h
create mode 100644 lib/union_find.c

MAINTAINERS +7 -0
index d6c90161c7..602d8c6f42 100644
@@ -23054,6 +23054,13 @@ F:	drivers/cdrom/cdrom.c
  F:	include/linux/cdrom.h
  F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <[email protected]>
+L:	[email protected]
+S:	Maintained
+F:	include/linux/union_find.h
+F:	lib/union_find.c
+
  UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
  R:	Alim Akhtar <[email protected]>
  R:	Avri Altman <[email protected]>
include/linux/union_find.h new file +30 -0
new file mode 100644
index 0000000000..67e9f62bb3
@@ -0,0 +1,30 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+#include <linux/slab.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 struct uf_node *uf_nodes_alloc(unsigned int node_num)
+{
+	return kzalloc(sizeof(struct uf_node) * node_num, GFP_KERNEL);
+}
+
+/* Free nodes*/
+static inline void uf_nodes_free(struct uf_node *nodes)
+{
+	kfree(nodes);
+}
+
+/* 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*/
lib/Makefile +1 -1
index 3b17690456..e1769e6f03 100644
@@ -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
lib/union_find.c new file +0 -0
new file mode 100644
index 0000000000..2f77bae1ca

lib/union_find.c line 2

Quoted 2 lines
lib/union_find.c new file +2 -0
@@ -0,0 +1,38 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>

I would suggest that you briefly document what is a union-find algorithm and data structure and what is it good for.

Cheers,
Longman

Quoted 36 lines
lib/union_find.c new file +36 -0
+
+struct uf_node *uf_find(struct uf_node *node)
+{
+	struct uf_node *parent;
+
+	if (!node->parent) {
+		node->parent = node;
+		return node;
+	}
+
+	/*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++;
+		}
+	}
+}
maintainer
#8 lore raw

v5 cover cpuset: use Union-Find to optimize

Hi all,

According to Longman's suggestion, I have added documentation describing Union-Find. 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                        |  95 ++++++---------
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  38 ++++++
 7 files changed, 309 insertions(+), 62 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
Signature · 1 line
2.45.2
maintainer
#9 lore raw

PATCH v5 1/2 Union-Find: add a new module in kernel library

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.

---
 Documentation/core-api/union_find.rst         | 110 ++++++++++++++++++
 .../zh_CN/core-api/union_find.rst             |  87 ++++++++++++++
 MAINTAINERS                                   |   9 ++
 include/linux/union_find.h                    |  30 +++++
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  38 ++++++
 6 files changed, 275 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
Documentation/core-api/union_find.rst new file +110 -0
new file mode 100644
index 0000000000..7109ad608a
@@ -0,0 +1,110 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <[email protected]>
+
+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.
+For efficiency, it is initialized to NULL and is assigned to point to itself
+during the first find operation. 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.
+
+Creating Union-Find
+--------------------
+
+To create a Union-Find structure, you only need to pass the number of nodes in
+the Union-Find. No additional initialization is required, and it returns a
+pointer to the node array.
+Example::
+
+	struct uf_node *my_node = uf_nodes_alloc(num);
+
+Destroying Union-Find
+---------------------
+
+To destroy the Union-Find structure, just pass the node pointer that was
+returned during creation.
+Example::
+
+	uf_nodes_free(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]);
Documentation/translations/zh_CN/core-api/union_find.rst new file +87 -0

87 lines not on this page · raw message

MAINTAINERS +9 -0
index d6c90161c7..a1a467c591 100644
@@ -23054,6 +23054,15 @@ F:	drivers/cdrom/cdrom.c
 F:	include/linux/cdrom.h
 F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <[email protected]>
+L:	[email protected]
+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 <[email protected]>
 R:	Avri Altman <[email protected]>
include/linux/union_find.h new file +30 -0
new file mode 100644
index 0000000000..67e9f62bb3
@@ -0,0 +1,30 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+#include <linux/slab.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 struct uf_node *uf_nodes_alloc(unsigned int node_num)
+{
+	return kzalloc(sizeof(struct uf_node) * node_num, GFP_KERNEL);
+}
+
+/* Free nodes*/
+static inline void uf_nodes_free(struct uf_node *nodes)
+{
+	kfree(nodes);
+}
+
+/* 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*/
lib/Makefile +1 -1
index 3b17690456..e1769e6f03 100644
@@ -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
lib/union_find.c new file +38 -0
new file mode 100644
index 0000000000..2f77bae1ca
@@ -0,0 +1,38 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+struct uf_node *uf_find(struct uf_node *node)
+{
+	struct uf_node *parent;
+
+	if (!node->parent) {
+		node->parent = node;
+		return node;
+	}
+
+	/*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++;
+		}
+	}
+}
Signature · 1 line
2.45.2
maintainer
#10 lore raw

Re: [PATCH-cpuset v5 1/2] Union-Find: add a new module in kernel library

Hello,

include/linux/union_find.h line 16

Quoted 11 lines · Xavier
include/linux/union_find.h new file +11 -0
+/* Define a union-find node struct */
+struct uf_node {
+	struct uf_node *parent;
+	unsigned int rank;
+};
+
+/* Allocate nodes and initialize to 0 */
+static inline struct uf_node *uf_nodes_alloc(unsigned int node_num)
+{
+	return kzalloc(sizeof(struct uf_node) * node_num, GFP_KERNEL);
+}

This is a very unusual pattern for kernel data structure. Most data structures allow the member entry to be embedded in other structs or allocated in user-defined ways. Do they need to be allocated consecutively? If so, this might be problematic as e.g. 4096 entries, which doesn't sound too high, would already require consecutive 64k allocation, which is getting close to vmalloc territory if not already there.

Quoted 25 lines
lib/union_find.c new file +25 -0
+struct uf_node *uf_find(struct uf_node *node)
+{
+	struct uf_node *parent;
+
+	if (!node->parent) {
+		node->parent = node;
+		return node;
+	}
+
+	/*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) {

lib/union_find.c line 38

Quoted 10 lines
lib/union_find.c new file +10 -0
+		if (root1->rank < root2->rank) {
+			root1->parent = root2;
+		} else if (root1->rank > root2->rank) {
+			root2->parent = root1;
+		} else {
+			root2->parent = root1;
+			root1->rank++;
+		}
+	}
+}

Code doesn't seem to suggest allocation needs to be consecutive tho. This is a bit too generic to route through the cgroup tree without wider reviews. When you post the next revision, can you please include Linus Torvalds <[email protected]> and Andrew Morton <[email protected]> and point to some other possible usages in kernel?

Thanks.

Signature · 1 line
tejun
maintainer
#11 lore raw

v6 cover Add Union-Find and use it to optimize cpuset

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
Signature · 1 line
2.45.2
maintainer
#12 lore raw

PATCH v6 1/2 Union-Find: add a new module in kernel library

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.

---
 Documentation/core-api/union_find.rst         | 110 ++++++++++++++++++
 .../zh_CN/core-api/union_find.rst             |  87 ++++++++++++++
 MAINTAINERS                                   |   9 ++
 include/linux/union_find.h                    |  30 +++++
 lib/Makefile                                  |   2 +-
 lib/union_find.c                              |  38 ++++++
 6 files changed, 275 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
Documentation/core-api/union_find.rst new file +110 -0
new file mode 100644
index 0000000000..7109ad608a
@@ -0,0 +1,110 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <[email protected]>
+
+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.
+For efficiency, it is initialized to NULL and is assigned to point to itself
+during the first find operation. 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.
+
+Creating Union-Find
+--------------------
+
+To create a Union-Find structure, you only need to pass the number of nodes in
+the Union-Find. No additional initialization is required, and it returns a
+pointer to the node array.
+Example::
+
+	struct uf_node *my_node = uf_nodes_alloc(num);
+
+Destroying Union-Find
+---------------------
+
+To destroy the Union-Find structure, just pass the node pointer that was
+returned during creation.
+Example::
+
+	uf_nodes_free(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]);
Documentation/translations/zh_CN/core-api/union_find.rst new file +87 -0

87 lines not on this page · raw message

MAINTAINERS +9 -0
index d6c90161c7..a1a467c591 100644
@@ -23054,6 +23054,15 @@ F:	drivers/cdrom/cdrom.c
 F:	include/linux/cdrom.h
 F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <[email protected]>
+L:	[email protected]
+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 <[email protected]>
 R:	Avri Altman <[email protected]>
include/linux/union_find.h new file +30 -0
new file mode 100644
index 0000000000..ca806f1531
@@ -0,0 +1,30 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+#include <linux/vmalloc.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 struct uf_node *uf_nodes_alloc(unsigned int node_num)
+{
+	return vzalloc(sizeof(struct uf_node) * node_num);
+}
+
+/* Free nodes*/
+static inline void uf_nodes_free(struct uf_node *nodes)
+{
+	vfree(nodes);
+}
+
+/* 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*/
lib/Makefile +1 -1
index 3b17690456..e1769e6f03 100644
@@ -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
lib/union_find.c new file +38 -0
new file mode 100644
index 0000000000..2f77bae1ca
@@ -0,0 +1,38 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+struct uf_node *uf_find(struct uf_node *node)
+{
+	struct uf_node *parent;
+
+	if (!node->parent) {
+		node->parent = node;
+		return node;
+	}
+
+	/*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++;
+		}
+	}
+}
Signature · 1 line
2.45.2
maintainer
#13 lore raw

PATCH v6 2/2 cpuset: use Union-Find to optimize the merging of cpumasks

In reply to Xavier

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.

---
 kernel/cgroup/cpuset.c | 97 +++++++++++++++++-------------------------
 1 file changed, 38 insertions(+), 59 deletions(-)
kernel/cgroup/cpuset.c +38 -59
index fe76045aa5..98e9df57c4 100644
@@ -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;
 
@@ -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,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 +1102,26 @@ 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) {
+		nodes = uf_nodes_alloc(csn);
+		if (!nodes)
+			goto done;
 
-					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]) || !nodes[i].parent)
+				ndoms++;
+		}
+	} else {
+		ndoms = csn;
 	}
 
 	/*
@@ -1159,48 +1154,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)
+		uf_nodes_free(nodes);
+
 	kfree(csa);
 
 	/*
Signature · 1 line
2.45.2
maintainer
#14 lore raw

Re: [PATCH-cpuset v6 0/2] Add Union-Find and use it to optimize cpuset

In reply to Xavier

Hello, Xavier.

Quoted 3 lines · Xavier

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.

Signature · 1 line
tejun
maintainer
#15 lore raw

v7 cover Add Union-Find and use it to optimize cpuset

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
Signature · 1 line
2.45.2
maintainer
#16 lore raw

PATCH v7 1/2 Union-Find: add a new module in kernel library

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.

---
 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
Documentation/core-api/union_find.rst new file +101 -0
new file mode 100644
index 0000000000..38d63b16e5
@@ -0,0 +1,101 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <[email protected]>
+
+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]);
Documentation/translations/zh_CN/core-api/union_find.rst new file +86 -0

86 lines not on this page · raw message

MAINTAINERS +9 -0
index d6c90161c7..a1a467c591 100644
@@ -23054,6 +23054,15 @@ F:	drivers/cdrom/cdrom.c
 F:	include/linux/cdrom.h
 F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <[email protected]>
+L:	[email protected]
+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 <[email protected]>
 R:	Avri Altman <[email protected]>
include/linux/union_find.h new file +24 -0
new file mode 100644
index 0000000000..56571c93a5
@@ -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*/
lib/Makefile +1 -1
index 3b17690456..e1769e6f03 100644
@@ -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
lib/union_find.c new file +33 -0
new file mode 100644
index 0000000000..bb48b4b129
@@ -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++;
+		}
+	}
+}
Signature · 1 line
2.45.2
maintainer
#17 lore raw

PATCH v7 2/2 cpuset: use Union-Find to optimize the merging of cpumasks

In reply to Xavier

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.

---
 kernel/cgroup/cpuset.c | 99 +++++++++++++++++-------------------------
 1 file changed, 41 insertions(+), 58 deletions(-)
kernel/cgroup/cpuset.c +41 -58
index fe76045aa5..d459cfddcb 100644
@@ -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);
 
 	/*
Signature · 1 line
2.45.2
maintainer
#18 lore raw

Re: [PATCH-cpuset v7 0/2] Add Union-Find and use it to optimize cpuset

In reply to Xavier

Hello, Xavier.

Quoted 4 lines · Xavier

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.

Signature · 1 line
tejun
maintainer
#19 lore raw

v8 cover Add Union-Find and use it to optimize cpuset

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
Signature · 1 line
2.45.2
maintainer
#20 lore raw

PATCH v8 1/2 Union-Find: add a new module in kernel library

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.

---
 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
Documentation/core-api/union_find.rst new file +101 -0
new file mode 100644
index 0000000000..38d63b16e5
@@ -0,0 +1,101 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <[email protected]>
+
+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]);
Documentation/translations/zh_CN/core-api/union_find.rst new file +86 -0

86 lines not on this page · raw message

MAINTAINERS +9 -0
index 2ca8f35dfe..16171dbca3 100644
@@ -23051,6 +23051,15 @@ F:	drivers/cdrom/cdrom.c
 F:	include/linux/cdrom.h
 F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <[email protected]>
+L:	[email protected]
+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 <[email protected]>
 R:	Avri Altman <[email protected]>
include/linux/union_find.h new file +24 -0
new file mode 100644
index 0000000000..56571c93a5
@@ -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*/
lib/Makefile +1 -1
index 3b17690456..e1769e6f03 100644
@@ -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
lib/union_find.c new file +33 -0
new file mode 100644
index 0000000000..bb48b4b129
@@ -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++;
+		}
+	}
+}
Signature · 1 line
2.45.2
maintainer
#21 lore raw

Re: [PATCH-cpuset v8 1/2] Union-Find: add a new module in kernel library

Hello, Xavier.

On Sat, Jun 29, 2024 at 12:13:01AM +0800, Xavier wrote:
...

Documentation/core-api/union_find.rst line 74

Quoted 10 lines
Documentation/core-api/union_find.rst new file +10 -0
+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.

include/linux/union_find.h line 1

Quoted 7 lines
include/linux/union_find.h new file +1 -0
new file mode 100644
index 0000000000..56571c93a5
@@ -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.

include/linux/union_find.h line 5

Quoted 1 line
include/linux/union_find.h new file +1 -0
+/* Define a union-find node struct */

I don't think the comment is contributing anything.

include/linux/union_find.h line 11

Quoted 6 lines
include/linux/union_find.h new file +6 -0
+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).

include/linux/union_find.h line 16

Quoted 5 lines
include/linux/union_find.h new file +5 -0
+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.

include/linux/union_find.h line 22

Quoted 5 lines
include/linux/union_find.h new file +5 -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);

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

include/linux/union_find.h line 23

Quoted 5 lines
include/linux/union_find.h new file +5 -0
+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?

include/linux/union_find.h

Quoted 9 lines
include/linux/union_find.h new file +9 -0
+	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.

Signature · 1 line
tejun
maintainer
#22 lore raw

v9 cover Add Union-Find and use it to optimize cpuset

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
Signature · 1 line
2.45.0
maintainer
#23 lore raw

PATCH v9 1/2 Union-Find: add a new module in kernel library

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.

---
 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
Documentation/core-api/union_find.rst new file +102 -0
new file mode 100644
index 0000000000..be9f68fd6d
@@ -0,0 +1,102 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <[email protected]>
+
+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);
Documentation/translations/zh_CN/core-api/union_find.rst new file +87 -0

87 lines not on this page · raw message

MAINTAINERS +9 -0
index 2ca8f35dfe..16171dbca3 100644
@@ -23051,6 +23051,15 @@ F:	drivers/cdrom/cdrom.c
 F:	include/linux/cdrom.h
 F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <[email protected]>
+L:	[email protected]
+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 <[email protected]>
 R:	Avri Altman <[email protected]>
include/linux/union_find.h new file +41 -0

41 lines not on this page · raw message

lib/Makefile +1 -1
index 3b17690456..e1769e6f03 100644
@@ -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
lib/union_find.c new file +48 -0

48 lines not on this page · raw message

Signature · 1 line
2.45.0
maintainer
#24 lore raw

PATCH v9 2/2 cpuset: use Union-Find to optimize the merging of cpumasks

In reply to Xavier

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.

---
 kernel/cgroup/cpuset.c | 95 ++++++++++++++++--------------------------
 1 file changed, 36 insertions(+), 59 deletions(-)
kernel/cgroup/cpuset.c +36 -59
index fe76045aa5..4d32cd1407 100644
@@ -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);
 
Signature · 1 line
2.45.0
maintainer
#25 lore raw

Re: [PATCH-cpuset v9 2/2] cpuset: use Union-Find to optimize the merging of cpumasks

Quoted 159 lines · Xavier

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.

---
  kernel/cgroup/cpuset.c | 95 ++++++++++++++++--------------------------
  1 file changed, 36 insertions(+), 59 deletions(-)
kernel/cgroup/cpuset.c +33 -57
index fe76045aa5..4d32cd1407 100644
@@ -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 */

kernel/cgroup/cpuset.c static int generate_sched_domains(cpumask_var_t **domains, · line 1179

Quoted 10 lines
kernel/cgroup/cpuset.c +3 -2
-				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

maintainer
#26 lore raw

Re: [PATCH-cpuset v9 0/2] Add Union-Find and use it to optimize cpuset

In reply to Xavier
Quoted 5 lines · Xavier

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.

Signature · 1 line
tejun
maintainer
#27 lore raw

Re: [PATCH-cpuset v9 0/2] Add Union-Find and use it to optimize cpuset

Quoted 11 lines · On Tue, 2 Jul 2024 09:22:44 -1000 Tejun Heo <[email protected]> wrote:
Quoted 5 lines · Xavier

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*/
maintainer
#28 lore raw

Re: [PATCH-cpuset v9 0/2] Add Union-Find and use it to optimize cpuset

Hello,

Quoted 1 line · Andrew Morton

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.

Signature · 1 line
tejun
maintainer
#29 lore raw

v10 cover Add Union-Find and use it to optimize cpuset

In reply to Tejun Heo

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
Signature · 1 line
2.45.0
maintainer
#30 lore raw

PATCH v10 1/2 Union-Find: add a new module in kernel library

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.

---
 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
Documentation/core-api/union_find.rst new file +102 -0
new file mode 100644
index 0000000000..be9f68fd6d
@@ -0,0 +1,102 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <[email protected]>
+
+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);
Documentation/translations/zh_CN/core-api/union_find.rst new file +87 -0

87 lines not on this page · raw message

MAINTAINERS +9 -0
index 2ca8f35dfe..16171dbca3 100644
@@ -23051,6 +23051,15 @@ F:	drivers/cdrom/cdrom.c
 F:	include/linux/cdrom.h
 F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <[email protected]>
+L:	[email protected]
+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 <[email protected]>
 R:	Avri Altman <[email protected]>
include/linux/union_find.h new file +41 -0

41 lines not on this page · raw message

lib/Makefile +1 -1
index 3b17690456..e1769e6f03 100644
@@ -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
lib/union_find.c new file +48 -0

48 lines not on this page · raw message

Signature · 1 line
2.45.0
maintainer
#31 lore raw

Re: [PATCH-cpuset v10 1/2] Union-Find: add a new module in kernel library

Quoted 5 lines · Xavier

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.

Quoted 13 lines
---
 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.

Quoted 10 lines
include/linux/union_find.h new file +10 -0
+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

include/linux/union_find.h line 33

Quoted 10 lines
include/linux/union_find.h new file +10 -0
+ * @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).

lib/union_find.c line 16

Quoted 9 lines

+ * 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.
+ */

lib/union_find.c new file +4 -0
+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;
	}
Quoted 4 lines
lib/union_find.c new file +4 -0
+/**
+ * uf_union - Merge two sets, using union by rank
+ * @node1: the first node
+ * @node2: the second node

lib/union_find.c line 38

Quoted 10 lines
lib/union_find.c new file +10 -0
+ *
+ * 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

maintainer
#32 lore raw

Re:Re: [PATCH-cpuset v10 1/2] Union-Find: add a new module in kernel library

Hi Michal,

Quoted 20 lines · Michal Koutný
Quoted 5 lines · Xavier

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.

Quoted 13 lines
---
 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
Quoted 3 lines

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.

Quoted 25 lines
Quoted 10 lines
include/linux/union_find.h new file +10 -0
+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

include/linux/union_find.h line 33

Quoted 10 lines
include/linux/union_find.h new file +10 -0
+ * @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).

Quoted 7 lines

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.

Quoted 16 lines
Quoted 4 lines
lib/union_find.c new file +4 -0
+/**
+ * uf_union - Merge two sets, using union by rank
+ * @node1: the first node
+ * @node2: the second node

lib/union_find.c line 38

Quoted 10 lines
lib/union_find.c new file +10 -0
+ *
+ * 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)

Quoted 3 lines
	return;

then the rest can be one level less nested ;-)

Of course, this change makes it look clearer.

--
Best Regards,
Xavier

maintainer
#33 lore raw

Re: [PATCH-cpuset v10 1/2] Union-Find: add a new module in kernel library

Quoted 12 lines · Xavier
Quoted 11 lines

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;
	}
Quoted 3 lines

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

Quoted 2 lines

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

Well, that's not a hard requirement.

Quoted 4 lines

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

maintainer
#34 lore raw

PATCH v10 2/2 cpuset: use Union-Find to optimize the merging of cpumasks

In reply to Xavier

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.

---
 kernel/cgroup/cpuset.c | 114 ++++++++++++++++-------------------------
 1 file changed, 44 insertions(+), 70 deletions(-)
kernel/cgroup/cpuset.c +44 -70
index fe76045aa5..88c2171361 100644
@@ -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);
 
Signature · 1 line
2.45.0
maintainer
#35 lore raw

Re: [PATCH-cpuset v10 2/2] cpuset: use Union-Find to optimize the merging of cpumasks

Quoted 12 lines · Xavier
kernel/cgroup/cpuset.c +0 -8
@@ -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];

kernel/cgroup/cpuset.c static int generate_sched_domains(cpumask_var_t **domains, · line 1104

Quoted 10 lines
kernel/cgroup/cpuset.c +1 -9
-		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?

Quoted 10 lines
kernel/cgroup/cpuset.c +4 -5
+		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++) {

kernel/cgroup/cpuset.c static int generate_sched_domains(cpumask_var_t **domains, · line 1119

Quoted 10 lines
kernel/cgroup/cpuset.c +8 -0
+			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

maintainer
#36 lore raw

Re:Re: [PATCH-cpuset v10 2/2] cpuset: use Union-Find to optimize the merging of cpumasks

Hi Michal and Longman,

Please confirm my explanation about cgroup v2 below.

Quoted 18 lines · Michal Koutný
Quoted 17 lines · Xavier
kernel/cgroup/cpuset.c +0 -13
@@ -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;
Quoted 9 lines

kernel/cgroup/cpuset.c static int generate_sched_domains(cpumask_var_t **domains, · line 1104

Quoted 5 lines
kernel/cgroup/cpuset.c +1 -4
-
-			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;
	}
Quoted 16 lines
Quoted 16 lines
kernel/cgroup/cpuset.c +8 -5
+		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);
 			}
 		}
+
Quoted 8 lines

kernel/cgroup/cpuset.c static int generate_sched_domains(cpumask_var_t **domains, · line 1119

Quoted 4 lines
kernel/cgroup/cpuset.c +4 -0
+		/* 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

maintainer
#37 lore raw

Re: [PATCH-cpuset v10 2/2] cpuset: use Union-Find to optimize the merging of cpumasks

Quoted 33 lines · Xavier

Hi Michal and Longman,

Please confirm my explanation about cgroup v2 below.

Quoted 17 lines · Michal Koutný
Quoted 16 lines · Xavier
kernel/cgroup/cpuset.c +0 -12
@@ -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];
Quoted 9 lines

kernel/cgroup/cpuset.c static int generate_sched_domains(cpumask_var_t **domains, · line 1104

Quoted 6 lines
kernel/cgroup/cpuset.c +1 -5
-			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?

Quoted 4 lines

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

maintainer
#38 lore raw

v11 cover Add Union-Find and use it to optimize cpuset

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
Signature · 1 line
2.45.0
maintainer
#39 lore raw

PATCH v11 1/2 Union-Find: add a new module in kernel library

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.

---
 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
Documentation/core-api/union_find.rst new file +102 -0
new file mode 100644
index 0000000000..2bf0290c91
@@ -0,0 +1,102 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <[email protected]>
+
+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);
Documentation/translations/zh_CN/core-api/union_find.rst new file +87 -0

87 lines not on this page · raw message

MAINTAINERS +9 -0
index 2ca8f35dfe..16171dbca3 100644
@@ -23051,6 +23051,15 @@ F:	drivers/cdrom/cdrom.c
 F:	include/linux/cdrom.h
 F:	include/uapi/linux/cdrom.h
 
+UNION-FIND
+M:	Xavier <[email protected]>
+L:	[email protected]
+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 <[email protected]>
 R:	Avri Altman <[email protected]>
include/linux/union_find.h new file +41 -0

41 lines not on this page · raw message

lib/Makefile +1 -1
index 3b17690456..e1769e6f03 100644
@@ -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
lib/union_find.c new file +49 -0

49 lines not on this page · raw message

Signature · 1 line
2.45.0
maintainer Applied
#40 lore raw

Re: [PATCH-cpuset v11 1/2] Union-Find: add a new module in kernel library

Quoted 5 lines · Xavier

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.

Applied to cgroup/for-6.12.

Thanks.

Signature · 1 line
tejun
maintainer
#41 lore raw

PATCH v11 2/2 cpuset: use Union-Find to optimize the merging of cpumasks

In reply to Xavier

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.

---
 kernel/cgroup/cpuset.c | 114 ++++++++++++++++-------------------------
 1 file changed, 44 insertions(+), 70 deletions(-)
kernel/cgroup/cpuset.c +44 -70
index fe76045aa5..0037371986 100644
@@ -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);
 
Signature · 1 line
2.45.0
maintainer Applied
#42 lore raw

Re: [PATCH-cpuset v11 2/2] cpuset: use Union-Find to optimize the merging of cpumasks

Quoted 9 lines · Xavier

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.

Applied to cgroup/for-6.12.

Thanks.

Signature · 1 line
tejun
maintainer Acked-by on the v11 series
#43 lore raw

Re: [PATCH-cpuset v11 0/2] Add Union-Find and use it to optimize cpuset

In reply to Xavier
Quoted 11 lines · Xavier

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.

Quoted 15 lines

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(-)
Quoted 5 lines

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.

maintainer
#44 lore raw

Re: [PATCH-cpuset v11 0/2] Add Union-Find and use it to optimize cpuset

Quoted 6 lines · Waiman Long

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.

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.

Signature · 1 line
tejun
maintainer
#45 lore raw

Re:Re: [PATCH-cpuset v11 0/2] Add Union-Find and use it to optimize cpuset

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

Quoted 16 lines · Tejun Heo
Quoted 6 lines · Waiman Long

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.

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.

Signature · 1 line
tejun
maintainer
#46 lore raw

Re:Re: [PATCH-cpuset v11 0/2] Add Union-Find and use it to optimize cpuset

In reply to Tejun Heo

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/[email protected]/

Thanks.

Quoted 6 lines · Tejun Heo
Quoted 5 lines · Waiman Long

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.

Quoted 6 lines
Quoted 1 line

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

maintainer
#47 lore raw

Re: Re: [PATCH-cpuset v11 0/2] Add Union-Find and use it to optimize cpuset

Hello,

Quoted 2 lines · Xavier

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

Merged two patches.

Quoted 5 lines

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/[email protected]/

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

Thanks.

Signature · 1 line
tejun
maintainer
#48 lore raw

PATCH v8 2/2 cpuset: use Union-Find to optimize the merging of cpumasks

In reply to Xavier

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.

---
 kernel/cgroup/cpuset.c | 96 ++++++++++++++++--------------------------
 1 file changed, 37 insertions(+), 59 deletions(-)
kernel/cgroup/cpuset.c +37 -59
index fe76045aa5..c435814ba8 100644
@@ -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);
 
Signature · 1 line
2.45.2
maintainer
#49 lore raw

Re: [PATCH-cpuset v8 2/2] cpuset: use Union-Find to optimize the merging of cpumasks

Quoted 9 lines · Xavier

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.

Waiman, how do you like this conversion?

Thanks.

Signature · 1 line
tejun
maintainer
#50 lore raw

PATCH v5 2/2 cpuset: use Union-Find to optimize the merging of cpumasks

In reply to Xavier

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.

---
 kernel/cgroup/cpuset.c | 95 +++++++++++++++---------------------------
 1 file changed, 34 insertions(+), 61 deletions(-)
kernel/cgroup/cpuset.c +34 -61
index fe76045aa5..7e527530f8 100644
@@ -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;
 
@@ -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,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;
+	int nslot_update;
 
 	doms = NULL;
 	dattr = NULL;
@@ -1102,40 +1102,31 @@ 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;
+	nodes = uf_nodes_alloc(csn);
+	if (!nodes)
+		goto done;
 
-restart:
-	/* Find the best partition (set of sched domains) */
+	/* Merge overlapping cpusets */
 	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 (c->pn == bpn)
-						c->pn = apn;
-				}
-				ndoms--;	/* one less element */
-				goto restart;
-			}
+		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]) || !nodes[i].parent)
+			ndoms++;
+	}
+
 	/*
 	 * Now we know how many domains to create.
 	 * Convert <csn, csa> to <ndoms, doms> and populate cpu masks.
 	 */
 	doms = alloc_sched_domains(ndoms);
 	if (!doms)
-		goto done;
+		goto free;
 
 	/*
 	 * The rest of the code, including the scheduler, can deal with
@@ -1159,47 +1150,29 @@ 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);
-
+free:
+	uf_nodes_free(nodes);
 done:
 	kfree(csa);
 
Signature · 1 line
2.45.2
maintainer
#51 lore raw

PATCH v4 2/2 cpuset: use Union-Find to optimize the merging of cpumasks

In reply to Xavier

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.

---
 kernel/cgroup/cpuset.c | 95 +++++++++++++++---------------------------
 1 file changed, 34 insertions(+), 61 deletions(-)
kernel/cgroup/cpuset.c +34 -61
index fe76045aa5..7e527530f8 100644
@@ -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;
 
@@ -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,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;
+	int nslot_update;
 
 	doms = NULL;
 	dattr = NULL;
@@ -1102,40 +1102,31 @@ 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;
+	nodes = uf_nodes_alloc(csn);
+	if (!nodes)
+		goto done;
 
-restart:
-	/* Find the best partition (set of sched domains) */
+	/* Merge overlapping cpusets */
 	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 (c->pn == bpn)
-						c->pn = apn;
-				}
-				ndoms--;	/* one less element */
-				goto restart;
-			}
+		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]) || !nodes[i].parent)
+			ndoms++;
+	}
+
 	/*
 	 * Now we know how many domains to create.
 	 * Convert <csn, csa> to <ndoms, doms> and populate cpu masks.
 	 */
 	doms = alloc_sched_domains(ndoms);
 	if (!doms)
-		goto done;
+		goto free;
 
 	/*
 	 * The rest of the code, including the scheduler, can deal with
@@ -1159,47 +1150,29 @@ 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);
-
+free:
+	uf_nodes_free(nodes);
 done:
 	kfree(csa);
 
Signature · 1 line
2.45.2