kernel/cgroup/cpuset.c | 117 +++++++++++++++++++++++------------------ 1 file changed, 66 insertions(+), 51 deletions(-)
The process of constructing scheduling domains involves multiple loops
and repeated evaluations, leading to numerous redundant and ineffective
assessments that impact code efficiency.
Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.
Signed-off-by: Xavier <ghostxavier@sina.com>
---
kernel/cgroup/cpuset.c | 117 +++++++++++++++++++++++------------------
1 file changed, 66 insertions(+), 51 deletions(-)
diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index c12b9fdb2..4bea1c2db 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -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);
--
2.34.1On 5/30/24 22:48, Xavier wrote:
> The process of constructing scheduling domains involves multiple loops
> and repeated evaluations, leading to numerous redundant and ineffective
> assessments that impact code efficiency.
>
> Here, we use Union-Find to optimize the merging of cpumasks. By employing
> path compression and union by rank, we effectively reduce the number of
> lookups and merge comparisons.
>
> Signed-off-by: Xavier <ghostxavier@sina.com>
> ---
> kernel/cgroup/cpuset.c | 117 +++++++++++++++++++++++------------------
> 1 file changed, 66 insertions(+), 51 deletions(-)
>
> diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
> index c12b9fdb2..4bea1c2db 100644
> --- a/kernel/cgroup/cpuset.c
> +++ b/kernel/cgroup/cpuset.c
> @@ -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);
>
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
The process of constructing scheduling domains involves multiple loops
and repeated evaluations, leading to numerous redundant and ineffective
assessments that impact code efficiency.
Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.
Signed-off-by: Xavier <ghostxavier@sina.com>
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(-)
diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index c12b9fdb2..c2d030a30 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -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);
--
2.34.1Hi 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 "ghostxavier@sina.com" to "xavier_qy@163.com" 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 -- 2.45.2
This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.
Signed-off-by: Xavier <xavier_qy@163.com>
---
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
diff --git a/MAINTAINERS b/MAINTAINERS
index d6c90161c7..602d8c6f42 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23054,6 +23054,13 @@ F: drivers/cdrom/cdrom.c
F: include/linux/cdrom.h
F: include/uapi/linux/cdrom.h
+UNION-FIND
+M: Xavier <xavier_qy@163.com>
+L: linux-kernel@vger.kernel.org
+S: Maintained
+F: include/linux/union_find.h
+F: lib/union_find.c
+
UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
R: Alim Akhtar <alim.akhtar@samsung.com>
R: Avri Altman <avri.altman@wdc.com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..67e9f62bb3
--- /dev/null
+++ b/include/linux/union_find.h
@@ -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*/
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
nmi_backtrace.o win_minmax.o memcat_p.o \
- buildid.o objpool.o
+ buildid.o objpool.o union_find.o
lib-$(CONFIG_PRINTK) += dump_stack.o
lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..2f77bae1ca
--- /dev/null
+++ b/lib/union_find.c
@@ -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++;
+ }
+ }
+}
--
2.45.2On 6/20/24 04:52, Xavier wrote:
> This patch implements a union-find data structure in the kernel library,
> which includes operations for allocating nodes, freeing nodes,
> finding the root of a node, and merging two nodes.
>
> Signed-off-by: Xavier <xavier_qy@163.com>
> ---
> 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
>
> diff --git a/MAINTAINERS b/MAINTAINERS
> index d6c90161c7..602d8c6f42 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -23054,6 +23054,13 @@ F: drivers/cdrom/cdrom.c
> F: include/linux/cdrom.h
> F: include/uapi/linux/cdrom.h
>
> +UNION-FIND
> +M: Xavier <xavier_qy@163.com>
> +L: linux-kernel@vger.kernel.org
> +S: Maintained
> +F: include/linux/union_find.h
> +F: lib/union_find.c
> +
> UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
> R: Alim Akhtar <alim.akhtar@samsung.com>
> R: Avri Altman <avri.altman@wdc.com>
> diff --git a/include/linux/union_find.h b/include/linux/union_find.h
> new file mode 100644
> index 0000000000..67e9f62bb3
> --- /dev/null
> +++ b/include/linux/union_find.h
> @@ -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*/
> diff --git a/lib/Makefile b/lib/Makefile
> index 3b17690456..e1769e6f03 100644
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
> is_single_threaded.o plist.o decompress.o kobject_uevent.o \
> earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
> nmi_backtrace.o win_minmax.o memcat_p.o \
> - buildid.o objpool.o
> + buildid.o objpool.o union_find.o
>
> lib-$(CONFIG_PRINTK) += dump_stack.o
> lib-$(CONFIG_SMP) += cpumask.o
> diff --git a/lib/union_find.c b/lib/union_find.c
> new file mode 100644
> index 0000000000..2f77bae1ca
> --- /dev/null
> +++ b/lib/union_find.c
> @@ -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
> +
> +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++;
> + }
> + }
> +}
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 -- 2.45.2
This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.
Signed-off-by: Xavier <xavier_qy@163.com>
---
Documentation/core-api/union_find.rst | 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
diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst
new file mode 100644
index 0000000000..7109ad608a
--- /dev/null
+++ b/Documentation/core-api/union_find.rst
@@ -0,0 +1,110 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <xavier_qy@163.com>
+
+What is Union-Find, and what is it used for?
+------------------------------------------------
+
+Union-Find is a data structure used to handle the merging and querying
+of disjoint sets. The primary operations supported by Union-Find are:
+
+ Initialization: Resetting each element as an individual set, with
+ each set's initial parent node pointing to itself.
+ Find: Determine which set a particular element belongs to, usually by
+ returning a “representative element” of that set. This operation
+ is used to check if two elements are in the same set.
+ Union: Merge two sets into one.
+
+As a data structure used to maintain sets (groups), Union-Find is commonly
+utilized to solve problems related to offline queries, dynamic connectivity,
+and graph theory. It is also a key component in Kruskal's algorithm for
+computing the minimum spanning tree, which is crucial in scenarios like
+network routing. Consequently, Union-Find is widely referenced. Additionally,
+Union-Find has applications in symbolic computation, register allocation,
+and more.
+
+Space Complexity: O(n), where n is the number of nodes.
+
+Time Complexity: Using path compression can reduce the time complexity of
+the find operation, and using union by rank can reduce the time complexity
+of the union operation. These optimizations reduce the average time
+complexity of each find and union operation to O(α(n)), where α(n) is the
+inverse Ackermann function. This can be roughly considered a constant time
+complexity for practical purposes.
+
+This document covers use of the Linux union-find implementation. For more
+information on the nature and implementation of Union-Find, see:
+
+ Wikipedia entry on union-find
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+Linux implementation of union-find
+-----------------------------------
+
+Linux's union-find implementation resides in the file "lib/union_find.c".
+To use it, "#include <linux/union_find.h>".
+
+The Union-Find data structure is defined as follows::
+
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+
+In this structure, parent points to the parent node of the current node.
+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]);
diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Documentation/translations/zh_CN/core-api/union_find.rst
new file mode 100644
index 0000000000..071818e7db
--- /dev/null
+++ b/Documentation/translations/zh_CN/core-api/union_find.rst
@@ -0,0 +1,87 @@
+.. SPDX-License-Identifier: GPL-2.0
+.. include:: ../disclaimer-zh_CN.rst
+
+:Original: Documentation/core-api/union_find.rst
+
+===========================
+Linux中的并查集（Union-Find）
+===========================
+
+
+:日期: 2024年6月21日
+:作者: Xavier <xavier_qy@163.com>
+
+何为并查集，它有什么用？
+---------------------
+
+并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：
+ 初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身
+ 查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为
+ 了判断两个元素是否在同一个集合之中。
+ 合并：将两个集合合并为一个。
+
+并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和
+图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在
+网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分
+配等方面也有应用。
+
+空间复杂度: O(n)，n为节点数。
+
+时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的
+时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿
+克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。
+
+本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：
+
+ 维基百科并查集词条
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+并查集的Linux实现
+----------------
+
+Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需要
+“#include <linux/union_find.h>”。
+
+并查集的数据结构定义如下::
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+其中parent为当前节点的父节点，为了提高效率，初始化时为空，并在第一次查找时指向自身，
+rank为当前树的高度，在合并时将rank小的节点接到rank大的节点下面以增加平衡性。
+
+创建并查集
+---------
+
+创建并查集时只需要传入并查集的节点个数即可，无需额外初始化，返回节点数组指针。
+示例::
+ struct uf_node *my_node = uf_nodes_alloc(num);
+
+销毁并查集
+---------
+
+销毁并查集时，只需传入创建时返回的节点数组指针即可。
+示例::
+ uf_nodes_free(my_node);
+
+查找并查集的根节点
+----------------
+
+主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中
+会对路径进行压缩，提高后续查找效率。
+示例::
+ int connected;
+ struct uf_node *root1 = uf_find(&my_node[0]);
+ struct uf_node *root2 = uf_find(&my_node[1]);
+ if (root1 == root2)
+ connected = 1;
+ else
+ connected = 0;
+
+合并两个并查集
+-------------
+
+对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的
+节点连接到大的节点下面。
+示例::
+ uf_union(&my_node[0], &my_node[1]);
diff --git a/MAINTAINERS b/MAINTAINERS
index d6c90161c7..a1a467c591 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23054,6 +23054,15 @@ F: drivers/cdrom/cdrom.c
F: include/linux/cdrom.h
F: include/uapi/linux/cdrom.h
+UNION-FIND
+M: Xavier <xavier_qy@163.com>
+L: linux-kernel@vger.kernel.org
+S: Maintained
+F: Documentation/core-api/union_find.rst
+F: Documentation/translations/zh_CN/core-api/union_find.rst
+F: include/linux/union_find.h
+F: lib/union_find.c
+
UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
R: Alim Akhtar <alim.akhtar@samsung.com>
R: Avri Altman <avri.altman@wdc.com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..67e9f62bb3
--- /dev/null
+++ b/include/linux/union_find.h
@@ -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*/
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
nmi_backtrace.o win_minmax.o memcat_p.o \
- buildid.o objpool.o
+ buildid.o objpool.o union_find.o
lib-$(CONFIG_PRINTK) += dump_stack.o
lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..2f77bae1ca
--- /dev/null
+++ b/lib/union_find.c
@@ -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++;
+ }
+ }
+}
--
2.45.2
Hello,
On Fri, Jun 21, 2024 at 04:49:51PM +0800, Xavier wrote:
> +/* 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.
> +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++;
> + }
> + }
> +}
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
<torvalds@linux-foundation.org> and Andrew Morton
<akpm@linux-foundation.org> and point to some other possible usages in
kernel?
Thanks.
--
tejun
Hi all, Add a Union-Find data structure in library, and use it to to optimize the merging of cpumasks. It could potentially be used in network configuration and topology management to manage the connectivity between different devices or nodes, as well as in managing the merging and lookup operations of certain complex file clusters or blocks. To Tejun, Since union_find operation does not require contiguous physical memory, I have replaced the previous allocation method with vzalloc. To Longman, Based on your patch, the overlapping check and merge operations for cpusets are skipped in the case of cgroup v2. Kindly review. Best Regards, Xavier Xavier (2): Union-Find: add a new module in kernel library cpuset: use Union-Find to optimize the merging of cpumasks Documentation/core-api/union_find.rst | 110 ++++++++++++++++++ .../zh_CN/core-api/union_find.rst | 87 ++++++++++++++ MAINTAINERS | 9 ++ include/linux/union_find.h | 30 +++++ kernel/cgroup/cpuset.c | 97 ++++++--------- lib/Makefile | 2 +- lib/union_find.c | 38 ++++++ 7 files changed, 313 insertions(+), 60 deletions(-) create mode 100644 Documentation/core-api/union_find.rst create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst create mode 100644 include/linux/union_find.h create mode 100644 lib/union_find.c -- 2.45.2
Hello, Xavier. On Sat, Jun 22, 2024 at 03:14:22PM +0800, Xavier wrote: > To Tejun, > Since union_find operation does not require contiguous physical memory, I > have replaced the previous allocation method with vzalloc. Oh, that's not what I meant. Sorry about not being clearer. What I was trying to say was that requiring consecutive allocation whether kzalloc or vzalloc is unlikely to work for kernel data structures. The reason why I mentioned vmalloc was because it's easy to end up in sizes that require vmalloc with consecutive allocations and vmallocs are rather expensive and not that great - ie. having to use vmalloc may negate the benefits of better algorithm in most cases. Skimming the code, there's nothing requiring consecutive allocations. Is there a reason why this can't follow the usual convention that kernel data structures follow (e.g. list, rbtree) where allocation is left to the users? Thanks. -- tejun
Hi Tejun, I think I understand your point now. I have modified the Union-Find implementation so that the allocation and deallocation are handled by the user, providing only the initialization interface. Thanks for your suggestion. Kindly review. Best Regards, Xavier Xavier (2): Union-Find: add a new module in kernel library cpuset: use Union-Find to optimize the merging of cpumasks Documentation/core-api/union_find.rst | 101 ++++++++++++++++++ .../zh_CN/core-api/union_find.rst | 86 +++++++++++++++ MAINTAINERS | 9 ++ include/linux/union_find.h | 24 +++++ kernel/cgroup/cpuset.c | 99 +++++++---------- lib/Makefile | 2 +- lib/union_find.c | 33 ++++++ 7 files changed, 295 insertions(+), 59 deletions(-) create mode 100644 Documentation/core-api/union_find.rst create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst create mode 100644 include/linux/union_find.h create mode 100644 lib/union_find.c -- 2.45.2
Hello, Xavier. On Sun, Jun 23, 2024 at 10:38:59AM +0800, Xavier wrote: > I think I understand your point now. I have modified the Union-Find > implementation so that the allocation and deallocation are handled by the > user, providing only the initialization interface. Thanks for your > suggestion. I recommend spending more time studying the existing data structures. The pattern is pretty universal. The element is often embedded in a containing structure. Macros and init methods are provided to initialize the element along with operations which implement the data structure operations, and then we use container_of() to obtain the embedding structure. We very rarely allocate data structure members by themselves. Also, the cleanup in cpuset seems nice but, if you can think of other use cases, that'd be great too. Thanks. -- tejun
Hi Tejun, Thank you for your suggestion. I agree with your point that it is indeed more appropriate to place it within the cpuset structure, and I have already made the modification. Additionally, I looked into the relevant modules of the kernel, and it seems that the union-find data structure may have optimization potential in network topology management and the Open vSwitch module. I will further investigate this in the future. Kindly review. Xavier (2): Union-Find: add a new module in kernel library cpuset: use Union-Find to optimize the merging of cpumasks Documentation/core-api/union_find.rst | 101 ++++++++++++++++++ .../zh_CN/core-api/union_find.rst | 86 +++++++++++++++ MAINTAINERS | 9 ++ include/linux/union_find.h | 24 +++++ kernel/cgroup/cpuset.c | 96 +++++++---------- lib/Makefile | 2 +- lib/union_find.c | 33 ++++++ 7 files changed, 291 insertions(+), 60 deletions(-) create mode 100644 Documentation/core-api/union_find.rst create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst create mode 100644 include/linux/union_find.h create mode 100644 lib/union_find.c -- 2.45.2
This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.
Signed-off-by: Xavier <xavier_qy@163.com>
---
Documentation/core-api/union_find.rst | 101 ++++++++++++++++++
.../zh_CN/core-api/union_find.rst | 86 +++++++++++++++
MAINTAINERS | 9 ++
include/linux/union_find.h | 24 +++++
lib/Makefile | 2 +-
lib/union_find.c | 33 ++++++
6 files changed, 254 insertions(+), 1 deletion(-)
create mode 100644 Documentation/core-api/union_find.rst
create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
create mode 100644 include/linux/union_find.h
create mode 100644 lib/union_find.c
diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst
new file mode 100644
index 0000000000..38d63b16e5
--- /dev/null
+++ b/Documentation/core-api/union_find.rst
@@ -0,0 +1,101 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <xavier_qy@163.com>
+
+What is Union-Find, and what is it used for?
+------------------------------------------------
+
+Union-Find is a data structure used to handle the merging and querying
+of disjoint sets. The primary operations supported by Union-Find are:
+
+ Initialization: Resetting each element as an individual set, with
+ each set's initial parent node pointing to itself.
+ Find: Determine which set a particular element belongs to, usually by
+ returning a “representative element” of that set. This operation
+ is used to check if two elements are in the same set.
+ Union: Merge two sets into one.
+
+As a data structure used to maintain sets (groups), Union-Find is commonly
+utilized to solve problems related to offline queries, dynamic connectivity,
+and graph theory. It is also a key component in Kruskal's algorithm for
+computing the minimum spanning tree, which is crucial in scenarios like
+network routing. Consequently, Union-Find is widely referenced. Additionally,
+Union-Find has applications in symbolic computation, register allocation,
+and more.
+
+Space Complexity: O(n), where n is the number of nodes.
+
+Time Complexity: Using path compression can reduce the time complexity of
+the find operation, and using union by rank can reduce the time complexity
+of the union operation. These optimizations reduce the average time
+complexity of each find and union operation to O(α(n)), where α(n) is the
+inverse Ackermann function. This can be roughly considered a constant time
+complexity for practical purposes.
+
+This document covers use of the Linux union-find implementation. For more
+information on the nature and implementation of Union-Find, see:
+
+ Wikipedia entry on union-find
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+Linux implementation of union-find
+-----------------------------------
+
+Linux's union-find implementation resides in the file "lib/union_find.c".
+To use it, "#include <linux/union_find.h>".
+
+The Union-Find data structure is defined as follows::
+
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+
+In this structure, parent points to the parent node of the current node.
+The rank field represents the height of the current tree. During a union
+operation, the tree with the smaller rank is attached under the tree with the
+larger rank to maintain balance.
+
+Initializing Union-Find
+--------------------
+
+When initializing the Union-Find data structure, a single pointer to the
+Union-Find instance needs to be passed. Initialize the parent pointer to point
+to itself and set the rank to 0.
+Example::
+
+ struct uf_node *my_node = vzalloc(sizeof(struct uf_node));
+ uf_nodes_init(my_node);
+
+Find the Root Node of Union-Find
+--------------------------------
+
+This operation is mainly used to determine whether two nodes belong to the same
+set in the Union-Find. If they have the same root, they are in the same set.
+During the find operation, path compression is performed to improve the
+efficiency of subsequent find operations.
+Example::
+
+ int connected;
+ struct uf_node *root1 = uf_find(&my_node[0]);
+ struct uf_node *root2 = uf_find(&my_node[1]);
+ if (root1 == root2)
+ connected = 1;
+ else
+ connected = 0;
+
+Union Two Sets in Union-Find
+----------------------------
+
+To union two sets in the Union-Find, you first find their respective root nodes
+and then link the smaller node to the larger node based on the rank of the root
+nodes.
+Example::
+
+ uf_union(&my_node[0], &my_node[1]);
diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Documentation/translations/zh_CN/core-api/union_find.rst
new file mode 100644
index 0000000000..e1b5ae88da
--- /dev/null
+++ b/Documentation/translations/zh_CN/core-api/union_find.rst
@@ -0,0 +1,86 @@
+.. SPDX-License-Identifier: GPL-2.0
+.. include:: ../disclaimer-zh_CN.rst
+
+:Original: Documentation/core-api/union_find.rst
+
+===========================
+Linux中的并查集（Union-Find）
+===========================
+
+
+:日期: 2024年6月21日
+:作者: Xavier <xavier_qy@163.com>
+
+何为并查集，它有什么用？
+---------------------
+
+并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：
+ 初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身
+ 查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为
+ 了判断两个元素是否在同一个集合之中。
+ 合并：将两个集合合并为一个。
+
+并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和
+图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在
+网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分
+配等方面也有应用。
+
+空间复杂度: O(n)，n为节点数。
+
+时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的
+时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿
+克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。
+
+本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：
+
+ 维基百科并查集词条
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+并查集的Linux实现
+----------------
+
+Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需要
+“#include <linux/union_find.h>”。
+
+并查集的数据结构定义如下::
+
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大
+的节点下面以增加平衡性。
+
+初始化并查集
+---------
+
+初始化并查集时需要传入并查集实例的一个指针。初始化时，parent 指针指向自身，rank 设置
+为 0。
+示例::
+
+ struct uf_node *my_node = vzalloc(sizeof(struct uf_node));
+ uf_nodes_init(my_node);
+
+查找并查集的根节点
+----------------
+
+主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中
+会对路径进行压缩，提高后续查找效率。
+示例::
+
+ int connected;
+ struct uf_node *root1 = uf_find(&my_node[0]);
+ struct uf_node *root2 = uf_find(&my_node[1]);
+ if (root1 == root2)
+ connected = 1;
+ else
+ connected = 0;
+
+合并两个并查集
+-------------
+
+对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的
+节点连接到大的节点下面。
+示例::
+
+ uf_union(&my_node[0], &my_node[1]);
diff --git a/MAINTAINERS b/MAINTAINERS
index 2ca8f35dfe..16171dbca3 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23051,6 +23051,15 @@ F: drivers/cdrom/cdrom.c
F: include/linux/cdrom.h
F: include/uapi/linux/cdrom.h
+UNION-FIND
+M: Xavier <xavier_qy@163.com>
+L: linux-kernel@vger.kernel.org
+S: Maintained
+F: Documentation/core-api/union_find.rst
+F: Documentation/translations/zh_CN/core-api/union_find.rst
+F: include/linux/union_find.h
+F: lib/union_find.c
+
UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
R: Alim Akhtar <alim.akhtar@samsung.com>
R: Avri Altman <avri.altman@wdc.com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..56571c93a5
--- /dev/null
+++ b/include/linux/union_find.h
@@ -0,0 +1,24 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+
+/* Define a union-find node struct */
+struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+};
+
+/* Allocate nodes and initialize to 0 */
+static inline void uf_nodes_init(struct uf_node *node)
+{
+ node->parent = node;
+ node->rank = 0;
+}
+
+/* find the root of a node*/
+struct uf_node *uf_find(struct uf_node *node);
+
+/* Merge two intersecting nodes */
+void uf_union(struct uf_node *node1, struct uf_node *node2);
+
+#endif /*__LINUX_UNION_FIND_H*/
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
nmi_backtrace.o win_minmax.o memcat_p.o \
- buildid.o objpool.o
+ buildid.o objpool.o union_find.o
lib-$(CONFIG_PRINTK) += dump_stack.o
lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..bb48b4b129
--- /dev/null
+++ b/lib/union_find.c
@@ -0,0 +1,33 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+struct uf_node *uf_find(struct uf_node *node)
+{
+ struct uf_node *parent;
+
+ /*Find the root node and perform path compression at the same time*/
+ while (node->parent != node) {
+ parent = node->parent;
+ node->parent = parent->parent;
+ node = parent;
+ }
+ return node;
+}
+
+/*Function to merge two sets, using union by rank*/
+void uf_union(struct uf_node *node1, struct uf_node *node2)
+{
+ struct uf_node *root1 = uf_find(node1);
+ struct uf_node *root2 = uf_find(node2);
+
+ if (root1 != root2) {
+ if (root1->rank < root2->rank) {
+ root1->parent = root2;
+ } else if (root1->rank > root2->rank) {
+ root2->parent = root1;
+ } else {
+ root2->parent = root1;
+ root1->rank++;
+ }
+ }
+}
--
2.45.2
Hello, Xavier.
On Sat, Jun 29, 2024 at 12:13:01AM +0800, Xavier wrote:
...
> +Initializing Union-Find
> +--------------------
> +
> +When initializing the Union-Find data structure, a single pointer to the
> +Union-Find instance needs to be passed. Initialize the parent pointer to point
> +to itself and set the rank to 0.
> +Example::
> +
> + struct uf_node *my_node = vzalloc(sizeof(struct uf_node));
> + uf_nodes_init(my_node);
It'd be better to replace the example with something which follows typical
kernel usage.
> diff --git a/include/linux/union_find.h b/include/linux/union_find.h
> new file mode 100644
> index 0000000000..56571c93a5
> --- /dev/null
> +++ b/include/linux/union_find.h
> @@ -0,0 +1,24 @@
> +/* SPDX-License-Identifier: GPL-2.0 */
It'd probably be useful to have a brief overview of what this is about and
point to the documentation here.
> +/* Define a union-find node struct */
I don't think the comment is contributing anything.
> +struct uf_node {
> + struct uf_node *parent;
> + unsigned int rank;
> +};
> +
> +/* Allocate nodes and initialize to 0 */
and this comment doesn't match what the code is doing. It's neither
allocating or setting everything to zero. Also, please use function comment
style (w/ /** and @ arg descriptions).
> +static inline void uf_nodes_init(struct uf_node *node)
> +{
> + node->parent = node;
> + node->rank = 0;
> +}
We'd also need an initializer for static cases.
> +/* find the root of a node*/
> +struct uf_node *uf_find(struct uf_node *node);
> +
> +/* Merge two intersecting nodes */
> +void uf_union(struct uf_node *node1, struct uf_node *node2);
Please use function comment style comments above the implementatino of each
function.
> +struct uf_node *uf_find(struct uf_node *node)
> +{
> + struct uf_node *parent;
> +
> + /*Find the root node and perform path compression at the same time*/
Spaces?
> + while (node->parent != node) {
> + parent = node->parent;
> + node->parent = parent->parent;
> + node = parent;
> + }
> + return node;
> +}
> +
> +/*Function to merge two sets, using union by rank*/
Ditto.
Overall, this looks okay to me and the cgroup conversion does look nice.
However, it'd be really nice if you could find another place where this can
be applied.
Thanks.
--
tejun
Hi Tejun, Thank you for thoroughly reviewing the code and pointing out the issues. I have made the necessary changes to the code, comments, and documentation based on your suggestions. Kindly review. Xavier (2): Union-Find: add a new module in kernel library cpuset: use Union-Find to optimize the merging of cpumasks Documentation/core-api/union_find.rst | 102 ++++++++++++++++++ .../zh_CN/core-api/union_find.rst | 87 +++++++++++++++ MAINTAINERS | 9 ++ include/linux/union_find.h | 41 +++++++ kernel/cgroup/cpuset.c | 95 +++++++--------- lib/Makefile | 2 +- lib/union_find.c | 48 +++++++++ 7 files changed, 324 insertions(+), 60 deletions(-) create mode 100644 Documentation/core-api/union_find.rst create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst create mode 100644 include/linux/union_find.h create mode 100644 lib/union_find.c -- 2.45.0
On Tue, Jul 02, 2024 at 06:50:08PM +0800, Xavier wrote: > Hi Tejun, > > Thank you for thoroughly reviewing the code and pointing out the issues. > I have made the necessary changes to the code, comments, and documentation > based on your suggestions. Looks fine to me. Once Waiman is okay with it, I can carry it through the cgroup tree. Andrew, any objections? Xavier, it'd really great if you can do more conversions so that it's not a single use thing. Thanks. -- tejun
Hi all, All the pointed out comment issues have been addressed. Moving forward, I will continue to look for applications of the union-find algorithm in other parts of the kernel. Kindly review. Xavier (2): Union-Find: add a new module in kernel library cpuset: use Union-Find to optimize the merging of cpumasks Documentation/core-api/union_find.rst | 102 ++++++++++++++++ .../zh_CN/core-api/union_find.rst | 87 +++++++++++++ MAINTAINERS | 9 ++ include/linux/union_find.h | 41 +++++++ kernel/cgroup/cpuset.c | 114 +++++++----------- lib/Makefile | 2 +- lib/union_find.c | 48 ++++++++ 7 files changed, 332 insertions(+), 71 deletions(-) create mode 100644 Documentation/core-api/union_find.rst create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst create mode 100644 include/linux/union_find.h create mode 100644 lib/union_find.c -- 2.45.0
This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.
Signed-off-by: Xavier <xavier_qy@163.com>
---
Documentation/core-api/union_find.rst | 102 ++++++++++++++++++
.../zh_CN/core-api/union_find.rst | 87 +++++++++++++++
MAINTAINERS | 9 ++
include/linux/union_find.h | 41 +++++++
lib/Makefile | 2 +-
lib/union_find.c | 48 +++++++++
6 files changed, 288 insertions(+), 1 deletion(-)
create mode 100644 Documentation/core-api/union_find.rst
create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
create mode 100644 include/linux/union_find.h
create mode 100644 lib/union_find.c
diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst
new file mode 100644
index 0000000000..be9f68fd6d
--- /dev/null
+++ b/Documentation/core-api/union_find.rst
@@ -0,0 +1,102 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <xavier_qy@163.com>
+
+What is Union-Find, and what is it used for?
+------------------------------------------------
+
+Union-Find is a data structure used to handle the merging and querying
+of disjoint sets. The primary operations supported by Union-Find are:
+
+ Initialization: Resetting each element as an individual set, with
+ each set's initial parent node pointing to itself.
+ Find: Determine which set a particular element belongs to, usually by
+ returning a “representative element” of that set. This operation
+ is used to check if two elements are in the same set.
+ Union: Merge two sets into one.
+
+As a data structure used to maintain sets (groups), Union-Find is commonly
+utilized to solve problems related to offline queries, dynamic connectivity,
+and graph theory. It is also a key component in Kruskal's algorithm for
+computing the minimum spanning tree, which is crucial in scenarios like
+network routing. Consequently, Union-Find is widely referenced. Additionally,
+Union-Find has applications in symbolic computation, register allocation,
+and more.
+
+Space Complexity: O(n), where n is the number of nodes.
+
+Time Complexity: Using path compression can reduce the time complexity of
+the find operation, and using union by rank can reduce the time complexity
+of the union operation. These optimizations reduce the average time
+complexity of each find and union operation to O(α(n)), where α(n) is the
+inverse Ackermann function. This can be roughly considered a constant time
+complexity for practical purposes.
+
+This document covers use of the Linux union-find implementation. For more
+information on the nature and implementation of Union-Find, see:
+
+ Wikipedia entry on union-find
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+Linux implementation of union-find
+-----------------------------------
+
+Linux's union-find implementation resides in the file "lib/union_find.c".
+To use it, "#include <linux/union_find.h>".
+
+The Union-Find data structure is defined as follows::
+
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+
+In this structure, parent points to the parent node of the current node.
+The rank field represents the height of the current tree. During a union
+operation, the tree with the smaller rank is attached under the tree with the
+larger rank to maintain balance.
+
+Initializing Union-Find
+--------------------
+
+You can complete the initialization using either static or initialization
+interface. Initialize the parent pointer to point to itself and set the rank
+to 0.
+Example::
+
+ struct uf_node my_node = UF_INIT_NODE(my_node);
+or
+ uf_node_init(&my_node);
+
+Find the Root Node of Union-Find
+--------------------------------
+
+This operation is mainly used to determine whether two nodes belong to the same
+set in the Union-Find. If they have the same root, they are in the same set.
+During the find operation, path compression is performed to improve the
+efficiency of subsequent find operations.
+Example::
+
+ int connected;
+ struct uf_node *root1 = uf_find(&node_1);
+ struct uf_node *root2 = uf_find(&node_2);
+ if (root1 == root2)
+ connected = 1;
+ else
+ connected = 0;
+
+Union Two Sets in Union-Find
+----------------------------
+
+To union two sets in the Union-Find, you first find their respective root nodes
+and then link the smaller node to the larger node based on the rank of the root
+nodes.
+Example::
+
+ uf_union(&node_1, &node_2);
diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Documentation/translations/zh_CN/core-api/union_find.rst
new file mode 100644
index 0000000000..a56de57147
--- /dev/null
+++ b/Documentation/translations/zh_CN/core-api/union_find.rst
@@ -0,0 +1,87 @@
+.. SPDX-License-Identifier: GPL-2.0
+.. include:: ../disclaimer-zh_CN.rst
+
+:Original: Documentation/core-api/union_find.rst
+
+===========================
+Linux中的并查集（Union-Find）
+===========================
+
+
+:日期: 2024年6月21日
+:作者: Xavier <xavier_qy@163.com>
+
+何为并查集，它有什么用？
+---------------------
+
+并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：
+ 初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身
+ 查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为
+ 了判断两个元素是否在同一个集合之中。
+ 合并：将两个集合合并为一个。
+
+并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和
+图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在
+网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分
+配等方面也有应用。
+
+空间复杂度: O(n)，n为节点数。
+
+时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的
+时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿
+克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。
+
+本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：
+
+ 维基百科并查集词条
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+并查集的Linux实现
+----------------
+
+Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需要
+“#include <linux/union_find.h>”。
+
+并查集的数据结构定义如下::
+
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大
+的节点下面以增加平衡性。
+
+初始化并查集
+---------
+
+可以采用静态或初始化接口完成初始化操作。初始化时，parent 指针指向自身，rank 设置
+为 0。
+示例::
+
+ struct uf_node my_node = UF_INIT_NODE(my_node);
+或
+ uf_node_init(&my_node);
+
+查找并查集的根节点
+----------------
+
+主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中
+会对路径进行压缩，提高后续查找效率。
+示例::
+
+ int connected;
+ struct uf_node *root1 = uf_find(&node_1);
+ struct uf_node *root2 = uf_find(&node_2);
+ if (root1 == root2)
+ connected = 1;
+ else
+ connected = 0;
+
+合并两个并查集
+-------------
+
+对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的
+节点连接到大的节点下面。
+示例::
+
+ uf_union(&node_1, &node_2);
diff --git a/MAINTAINERS b/MAINTAINERS
index 2ca8f35dfe..16171dbca3 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23051,6 +23051,15 @@ F: drivers/cdrom/cdrom.c
F: include/linux/cdrom.h
F: include/uapi/linux/cdrom.h
+UNION-FIND
+M: Xavier <xavier_qy@163.com>
+L: linux-kernel@vger.kernel.org
+S: Maintained
+F: Documentation/core-api/union_find.rst
+F: Documentation/translations/zh_CN/core-api/union_find.rst
+F: include/linux/union_find.h
+F: lib/union_find.c
+
UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
R: Alim Akhtar <alim.akhtar@samsung.com>
R: Avri Altman <avri.altman@wdc.com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..f127cf9b8d
--- /dev/null
+++ b/include/linux/union_find.h
@@ -0,0 +1,41 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+/**
+ * union_find.h - Union-Find data structure implementation
+ *
+ * This header provides functions and structures to implement the Union-Find
+ * data structure. The Union-Find data structure is used to manage disjoint
+ * sets and supports efficient union and find operations.
+ *
+ * See Documentation/core-api/union_find.rst for documentation and samples.
+ */
+
+struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+};
+
+/* This macro is used for static initialization of a union-find node. */
+#define UF_INIT_NODE(node) {.parent = &node, .rank = 0}
+
+/**
+ * uf_node_init - Initialize a union-find node
+ * @node: pointer to the union-find node to be initialized
+ *
+ * This function sets the parent of the node to itself and
+ * initializes its rank to 0.
+ */
+static inline void uf_node_init(struct uf_node *node)
+{
+ node->parent = node;
+ node->rank = 0;
+}
+
+/* find the root of a node */
+struct uf_node *uf_find(struct uf_node *node);
+
+/* Merge two intersecting nodes */
+void uf_union(struct uf_node *node1, struct uf_node *node2);
+
+#endif /* __LINUX_UNION_FIND_H */
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
nmi_backtrace.o win_minmax.o memcat_p.o \
- buildid.o objpool.o
+ buildid.o objpool.o union_find.o
lib-$(CONFIG_PRINTK) += dump_stack.o
lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..bec574ad24
--- /dev/null
+++ b/lib/union_find.c
@@ -0,0 +1,48 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+/**
+ * uf_find - Find the root of a node and perform path compression
+ * @node: the node to find the root of
+ *
+ * This function returns the root of the node by following the parent
+ * pointers. It also performs path compression, making the tree shallower.
+ *
+ * Returns the root node of the set containing node.
+ */
+struct uf_node *uf_find(struct uf_node *node)
+{
+ struct uf_node *parent;
+
+ while (node->parent != node) {
+ parent = node->parent;
+ node->parent = parent->parent;
+ node = parent;
+ }
+ return node;
+}
+
+/**
+ * uf_union - Merge two sets, using union by rank
+ * @node1: the first node
+ * @node2: the second node
+ *
+ * This function merges the sets containing node1 and node2, by comparing
+ * the ranks to keep the tree balanced.
+ */
+void uf_union(struct uf_node *node1, struct uf_node *node2)
+{
+ struct uf_node *root1 = uf_find(node1);
+ struct uf_node *root2 = uf_find(node2);
+
+ if (root1 != root2) {
+ if (root1->rank < root2->rank) {
+ root1->parent = root2;
+ } else if (root1->rank > root2->rank) {
+ root2->parent = root1;
+ } else {
+ root2->parent = root1;
+ root1->rank++;
+ }
+ }
+}
--
2.45.0
On Wed, Jul 03, 2024 at 02:37:26PM GMT, Xavier <xavier_qy@163.com> wrote:
> This patch implements a union-find data structure in the kernel library,
> which includes operations for allocating nodes, freeing nodes,
> finding the root of a node, and merging two nodes.
>
> Signed-off-by: Xavier <xavier_qy@163.com>
> ---
> Documentation/core-api/union_find.rst | 102 ++++++++++++++++++
> .../zh_CN/core-api/union_find.rst | 87 +++++++++++++++
> MAINTAINERS | 9 ++
> include/linux/union_find.h | 41 +++++++
> lib/Makefile | 2 +-
> lib/union_find.c | 48 +++++++++
> 6 files changed, 288 insertions(+), 1 deletion(-)
> create mode 100644 Documentation/core-api/union_find.rst
> create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
> create mode 100644 include/linux/union_find.h
> create mode 100644 lib/union_find.c
>
Nice.
I'd so s/Union-Find/union-find/ both in the docs and the code
(comments), I didn't find any rule why two capitalizations are used.
> +struct uf_node {
> + struct uf_node *parent;
> + unsigned int rank;
> +};
> +
> +/* This macro is used for static initialization of a union-find node. */
> +#define UF_INIT_NODE(node) {.parent = &node, .rank = 0}
> +
> +/**
> + * uf_node_init - Initialize a union-find node
> + * @node: pointer to the union-find node to be initialized
> + *
> + * This function sets the parent of the node to itself and
> + * initializes its rank to 0.
> + */
> +static inline void uf_node_init(struct uf_node *node)
> +{
> + node->parent = node;
> + node->rank = 0;
> +}
Xavier, not sure if you responded to my suggestion of considered zeroed
object a valid initialized one. That could save some init work (and
move it to alternative uf_find, see below).
> + * This function returns the root of the node by following the parent
> + * pointers. It also performs path compression, making the tree shallower.
> + *
> + * Returns the root node of the set containing node.
> + */
> +struct uf_node *uf_find(struct uf_node *node)
> +{
> + struct uf_node *parent;
> +
With uf_find body checking for NULL:
while (node->parent != node) {
parent = node->parent;
node->parent = parent ? parent->parent : node;
node = node->parent;
}
> +/**
> + * uf_union - Merge two sets, using union by rank
> + * @node1: the first node
> + * @node2: the second node
> + *
> + * This function merges the sets containing node1 and node2, by comparing
> + * the ranks to keep the tree balanced.
> + */
> +void uf_union(struct uf_node *node1, struct uf_node *node2)
> +{
> + struct uf_node *root1 = uf_find(node1);
> + struct uf_node *root2 = uf_find(node2);
> +
> + if (root1 != root2) {
if (root1 == root2)
return;
then the rest can be one level less nested ;-)
Michal
Hi Michal,
At 2024-07-03 17:40:25, "Michal Koutný" <mkoutny@suse.com> wrote:
>On Wed, Jul 03, 2024 at 02:37:26PM GMT, Xavier <xavier_qy@163.com> wrote:
>> This patch implements a union-find data structure in the kernel library,
>> which includes operations for allocating nodes, freeing nodes,
>> finding the root of a node, and merging two nodes.
>>
>> Signed-off-by: Xavier <xavier_qy@163.com>
>> ---
>> Documentation/core-api/union_find.rst | 102 ++++++++++++++++++
>> .../zh_CN/core-api/union_find.rst | 87 +++++++++++++++
>> MAINTAINERS | 9 ++
>> include/linux/union_find.h | 41 +++++++
>> lib/Makefile | 2 +-
>> lib/union_find.c | 48 +++++++++
>> 6 files changed, 288 insertions(+), 1 deletion(-)
>> create mode 100644 Documentation/core-api/union_find.rst
>> create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
>> create mode 100644 include/linux/union_find.h
>> create mode 100644 lib/union_find.c
>>
>
>Nice.
>I'd so s/Union-Find/union-find/ both in the docs and the code
>(comments), I didn't find any rule why two capitalizations are used.
Union-Find only appears in the patch description or title; in the main text, we consistently
use union-find. This will be corrected in the next version.
>> +struct uf_node {
>> + struct uf_node *parent;
>> + unsigned int rank;
>> +};
>> +
>> +/* This macro is used for static initialization of a union-find node. */
>> +#define UF_INIT_NODE(node) {.parent = &node, .rank = 0}
>> +
>> +/**
>> + * uf_node_init - Initialize a union-find node
>> + * @node: pointer to the union-find node to be initialized
>> + *
>> + * This function sets the parent of the node to itself and
>> + * initializes its rank to 0.
>> + */
>> +static inline void uf_node_init(struct uf_node *node)
>> +{
>> + node->parent = node;
>> + node->rank = 0;
>> +}
>
>Xavier, not sure if you responded to my suggestion of considered zeroed
>object a valid initialized one. That could save some init work (and
>move it to alternative uf_find, see below).
>
>With uf_find body checking for NULL:
>
> while (node->parent != node) {
> parent = node->parent;
> node->parent = parent ? parent->parent : node;
> node = node->parent;
> }
Yes, I noticed your suggestion. In patch v4, I implemented it by initializing to 0
and adding a check for whether the parent is 0 in uf_find. However, later,
when I was reviewing the algorithm's documentation, I noticed it requires
initialization to itself. Moreover, uf_find is a high-frequency operation, if we
add a parent check within it, the efficiency impact each time would be more
significant than initializing once. Therefore, I adhered to the initialization
to itself approach.
>> +/**
>> + * uf_union - Merge two sets, using union by rank
>> + * @node1: the first node
>> + * @node2: the second node
>> + *
>> + * This function merges the sets containing node1 and node2, by comparing
>> + * the ranks to keep the tree balanced.
>> + */
>> +void uf_union(struct uf_node *node1, struct uf_node *node2)
>> +{
>> + struct uf_node *root1 = uf_find(node1);
>> + struct uf_node *root2 = uf_find(node2);
>> +
>> + if (root1 != root2) {
>
>if (root1 == root2)
> return;
>then the rest can be one level less nested ;-)
>
Of course, this change makes it look clearer.
--
Best Regards,
Xavier
On Wed, Jul 03, 2024 at 07:20:09PM GMT, Xavier <xavier_qy@163.com> wrote:
> >Xavier, not sure if you responded to my suggestion of considered zeroed
> >object a valid initialized one. That could save some init work (and
> >move it to alternative uf_find, see below).
> >
> >With uf_find body checking for NULL:
> >
> > while (node->parent != node) {
> > parent = node->parent;
> > node->parent = parent ? parent->parent : node;
> > node = node->parent;
> > }
>
> Yes, I noticed your suggestion. In patch v4, I implemented it by
> initializing to 0 and adding a check for whether the parent is 0 in
> uf_find.
Ah, I didn't read all versions. (You may consider adding a short
changelog when sending a new version of patches where main evolution
points are summed up. ;-))
> However, later, when I was reviewing the algorithm's documentation, I
> noticed it requires initialization to itself.
Well, that's not a hard requirement.
> Moreover, uf_find is a high-frequency operation, if we add a parent
> check within it, the efficiency impact each time would be more
> significant than initializing once. Therefore, I adhered to the
> initialization to itself approach.
I see, thanks for the clarifications,
Michal
The process of constructing scheduling domains
involves multiple loops and repeated evaluations, leading to numerous
redundant and ineffective assessments that impact code efficiency.
Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.
Signed-off-by: Xavier <xavier_qy@163.com>
---
kernel/cgroup/cpuset.c | 114 ++++++++++++++++-------------------------
1 file changed, 44 insertions(+), 70 deletions(-)
diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index fe76045aa5..88c2171361 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -45,6 +45,7 @@
#include <linux/cgroup.h>
#include <linux/wait.h>
#include <linux/workqueue.h>
+#include <linux/union_find.h>
DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
@@ -172,9 +173,6 @@ struct cpuset {
*/
int attach_in_progress;
- /* partition number for rebuild_sched_domains() */
- int pn;
-
/* for custom sched domain */
int relax_domain_level;
@@ -208,6 +206,9 @@ struct cpuset {
/* Remote partition silbling list anchored at remote_children */
struct list_head remote_sibling;
+
+ /* Used to merge intersecting subsets for generate_sched_domains */
+ struct uf_node node;
};
/*
@@ -988,18 +989,15 @@ static inline int nr_cpusets(void)
* were changed (added or removed.)
*
* Finding the best partition (set of domains):
- * The triple nested loops below over i, j, k scan over the
- * load balanced cpusets (using the array of cpuset pointers in
- * csa[]) looking for pairs of cpusets that have overlapping
- * cpus_allowed, but which don't have the same 'pn' partition
- * number and gives them in the same partition number. It keeps
- * looping on the 'restart' label until it can no longer find
- * any such pairs.
+ * The double nested loops below over i, j scan over the load
+ * balanced cpusets (using the array of cpuset pointers in csa[])
+ * looking for pairs of cpusets that have overlapping cpus_allowed
+ * and merging them using a union-find algorithm.
+ *
+ * The union of the cpus_allowed masks from the set of all cpusets
+ * having the same root then form the one element of the partition
+ * (one sched domain) to be passed to partition_sched_domains().
*
- * The union of the cpus_allowed masks from the set of
- * all cpusets having the same 'pn' value then form the one
- * element of the partition (one sched domain) to be passed to
- * partition_sched_domains().
*/
static int generate_sched_domains(cpumask_var_t **domains,
struct sched_domain_attr **attributes)
@@ -1007,7 +1005,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
struct cpuset *cp; /* top-down scan of cpusets */
struct cpuset **csa; /* array of all cpuset ptrs */
int csn; /* how many cpuset ptrs in csa so far */
- int i, j, k; /* indices for partition finding loops */
+ int i, j; /* indices for partition finding loops */
cpumask_var_t *doms; /* resulting partition; i.e. sched domains */
struct sched_domain_attr *dattr; /* attributes for custom domains */
int ndoms = 0; /* number of sched domains in result */
@@ -1015,6 +1013,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
struct cgroup_subsys_state *pos_css;
bool root_load_balance = is_sched_load_balance(&top_cpuset);
bool cgrpv2 = cgroup_subsys_on_dfl(cpuset_cgrp_subsys);
+ int nslot_update;
doms = NULL;
dattr = NULL;
@@ -1102,31 +1101,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
if (root_load_balance && (csn == 1))
goto single_root_domain;
- for (i = 0; i < csn; i++)
- csa[i]->pn = i;
- ndoms = csn;
-
-restart:
- /* Find the best partition (set of sched domains) */
- for (i = 0; i < csn; i++) {
- struct cpuset *a = csa[i];
- int apn = a->pn;
-
- for (j = 0; j < csn; j++) {
- struct cpuset *b = csa[j];
- int bpn = b->pn;
-
- if (apn != bpn && cpusets_overlap(a, b)) {
- for (k = 0; k < csn; k++) {
- struct cpuset *c = csa[k];
+ if (!cgrpv2) {
+ for (i = 0; i < csn; i++)
+ uf_node_init(&csa[i]->node);
- if (c->pn == bpn)
- c->pn = apn;
- }
- ndoms--; /* one less element */
- goto restart;
+ /* Merge overlapping cpusets */
+ for (i = 0; i < csn; i++) {
+ for (j = i + 1; j < csn; j++) {
+ if (cpusets_overlap(csa[i], csa[j]))
+ uf_union(&csa[i]->node, &csa[j]->node);
}
}
+
+ /* Count the total number of domains */
+ for (i = 0; i < csn; i++) {
+ if (csa[i]->node.parent == &csa[i]->node)
+ ndoms++;
+ }
+ } else {
+ ndoms = csn;
}
/*
@@ -1159,44 +1152,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
}
for (nslot = 0, i = 0; i < csn; i++) {
- struct cpuset *a = csa[i];
- struct cpumask *dp;
- int apn = a->pn;
-
- if (apn < 0) {
- /* Skip completed partitions */
- continue;
- }
-
- dp = doms[nslot];
-
- if (nslot == ndoms) {
- static int warnings = 10;
- if (warnings) {
- pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
- nslot, ndoms, csn, i, apn);
- warnings--;
- }
- continue;
- }
-
- cpumask_clear(dp);
- if (dattr)
- *(dattr + nslot) = SD_ATTR_INIT;
+ nslot_update = 0;
for (j = i; j < csn; j++) {
- struct cpuset *b = csa[j];
-
- if (apn == b->pn) {
- cpumask_or(dp, dp, b->effective_cpus);
+ if (uf_find(&csa[j]->node) == &csa[i]->node) {
+ struct cpumask *dp = doms[nslot];
+
+ if (i == j) {
+ nslot_update = 1;
+ cpumask_clear(dp);
+ if (dattr)
+ *(dattr + nslot) = SD_ATTR_INIT;
+ }
+ cpumask_or(dp, dp, csa[j]->effective_cpus);
cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN));
if (dattr)
- update_domain_attr_tree(dattr + nslot, b);
-
- /* Done with this partition */
- b->pn = -1;
+ update_domain_attr_tree(dattr + nslot, csa[j]);
}
}
- nslot++;
+ if (nslot_update)
+ nslot++;
}
BUG_ON(nslot != ndoms);
--
2.45.0On Wed, Jul 03, 2024 at 02:37:27PM GMT, Xavier <xavier_qy@163.com> wrote:
> @@ -1102,31 +1101,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
> if (root_load_balance && (csn == 1))
> goto single_root_domain;
>
> - for (i = 0; i < csn; i++)
> - csa[i]->pn = i;
> - ndoms = csn;
> -
> -restart:
> - /* Find the best partition (set of sched domains) */
> - for (i = 0; i < csn; i++) {
> - struct cpuset *a = csa[i];
> - int apn = a->pn;
> -
> - for (j = 0; j < csn; j++) {
> - struct cpuset *b = csa[j];
> - int bpn = b->pn;
> -
> - if (apn != bpn && cpusets_overlap(a, b)) {
> - for (k = 0; k < csn; k++) {
> - struct cpuset *c = csa[k];
> + if (!cgrpv2) {
I'm surprised that original code wasn't branched on this on you add it
here. Why is UF used only for v1 code?
> + for (i = 0; i < csn; i++)
> + uf_node_init(&csa[i]->node);
>
> - if (c->pn == bpn)
> - c->pn = apn;
> - }
> - ndoms--; /* one less element */
> - goto restart;
> + /* Merge overlapping cpusets */
> + for (i = 0; i < csn; i++) {
> + for (j = i + 1; j < csn; j++) {
> + if (cpusets_overlap(csa[i], csa[j]))
> + uf_union(&csa[i]->node, &csa[j]->node);
> }
> }
> +
> + /* Count the total number of domains */
> + for (i = 0; i < csn; i++) {
> + if (csa[i]->node.parent == &csa[i]->node)
> + ndoms++;
The naked parent access doesn't hide the UF abstraction well.
I'd consider uf_find(&csa[i]->node) == &csa[i]->node or a specific
helper like uf_is_representant(&csa[i]->node).
Thanks,
Michal
Hi Michal and Longman,
Please confirm my explanation about cgroup v2 below.
At 2024-07-03 17:40:49, "Michal Koutný" <mkoutny@suse.com> wrote:
>On Wed, Jul 03, 2024 at 02:37:27PM GMT, Xavier <xavier_qy@163.com> wrote:
>> @@ -1102,31 +1101,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
>> if (root_load_balance && (csn == 1))
>> goto single_root_domain;
>>
>> - for (i = 0; i < csn; i++)
>> - csa[i]->pn = i;
>> - ndoms = csn;
>> -
>> -restart:
>> - /* Find the best partition (set of sched domains) */
>> - for (i = 0; i < csn; i++) {
>> - struct cpuset *a = csa[i];
>> - int apn = a->pn;
>> -
>> - for (j = 0; j < csn; j++) {
>> - struct cpuset *b = csa[j];
>> - int bpn = b->pn;
>> -
>> - if (apn != bpn && cpusets_overlap(a, b)) {
>> - for (k = 0; k < csn; k++) {
>> - struct cpuset *c = csa[k];
>> + if (!cgrpv2) {
>
>I'm surprised that original code wasn't branched on this on you add it
>here. Why is UF used only for v1 code?
>
In the Patch v6, I explained to Longman that based on his new patch, the overlapping check and
merge operations for cpusets are skipped in the case of cgroup v2. Because for cgroup v2,
doms[i] is merely copied from csa[i] rather than merged.
This needs further confirmation from Longman.
if (cgrpv2) {
for (i = 0; i < ndoms; i++) {
cpumask_copy(doms[i], csa[i]->effective_cpus);
if (dattr)
dattr[i] = SD_ATTR_INIT;
}
goto done;
}
>> + for (i = 0; i < csn; i++)
>> + uf_node_init(&csa[i]->node);
>>
>> - if (c->pn == bpn)
>> - c->pn = apn;
>> - }
>> - ndoms--; /* one less element */
>> - goto restart;
>> + /* Merge overlapping cpusets */
>> + for (i = 0; i < csn; i++) {
>> + for (j = i + 1; j < csn; j++) {
>> + if (cpusets_overlap(csa[i], csa[j]))
>> + uf_union(&csa[i]->node, &csa[j]->node);
>> }
>> }
>> +
>> + /* Count the total number of domains */
>> + for (i = 0; i < csn; i++) {
>> + if (csa[i]->node.parent == &csa[i]->node)
>> + ndoms++;
>
>The naked parent access doesn't hide the UF abstraction well.
>I'd consider uf_find(&csa[i]->node) == &csa[i]->node or a specific
>helper like uf_is_representant(&csa[i]->node).
This can be optimized here. I will change it to the first method you mentioned in the next patch.
Best Regards,
Xavier
On 7/3/24 06:49, Xavier wrote:
>
> Hi Michal and Longman,
>
> Please confirm my explanation about cgroup v2 below.
>
>
> At 2024-07-03 17:40:49, "Michal Koutný" <mkoutny@suse.com> wrote:
>> On Wed, Jul 03, 2024 at 02:37:27PM GMT, Xavier <xavier_qy@163.com> wrote:
>>> @@ -1102,31 +1101,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
>>> if (root_load_balance && (csn == 1))
>>> goto single_root_domain;
>>>
>>> - for (i = 0; i < csn; i++)
>>> - csa[i]->pn = i;
>>> - ndoms = csn;
>>> -
>>> -restart:
>>> - /* Find the best partition (set of sched domains) */
>>> - for (i = 0; i < csn; i++) {
>>> - struct cpuset *a = csa[i];
>>> - int apn = a->pn;
>>> -
>>> - for (j = 0; j < csn; j++) {
>>> - struct cpuset *b = csa[j];
>>> - int bpn = b->pn;
>>> -
>>> - if (apn != bpn && cpusets_overlap(a, b)) {
>>> - for (k = 0; k < csn; k++) {
>>> - struct cpuset *c = csa[k];
>>> + if (!cgrpv2) {
>> I'm surprised that original code wasn't branched on this on you add it
>> here. Why is UF used only for v1 code?
>>
> In the Patch v6, I explained to Longman that based on his new patch, the overlapping check and
> merge operations for cpusets are skipped in the case of cgroup v2. Because for cgroup v2,
> doms[i] is merely copied from csa[i] rather than merged.
> This needs further confirmation from Longman.
Actually, I would like to keep the cpuset merging part for both cgroup
v1 and v2. I did notice that the hotplug code path can sometimes cause
overlapping partition roots in some intermediate states. I will try to
get it of that and use the merging part to verify that all partition
roots are mutually exclusive.
Cheers,
Longman
Hi all, Based on Michal's suggestion, the following changes were made: 1. Changed Union-Find to union-find in all places except the title. 2. Optimized the logic of the uf_union function. 3. Modified places where csa[i]->node.parent was used directly. To Longman, Regarding the modifications for supporting cpuset merging in both cgroup v1 and v2, do you mean that you will continue to complete them after my patch is merged? Kindly review. Xavier (2): Union-Find: add a new module in kernel library cpuset: use Union-Find to optimize the merging of cpumasks Documentation/core-api/union_find.rst | 102 ++++++++++++++++ .../zh_CN/core-api/union_find.rst | 87 +++++++++++++ MAINTAINERS | 9 ++ include/linux/union_find.h | 41 +++++++ kernel/cgroup/cpuset.c | 114 +++++++----------- lib/Makefile | 2 +- lib/union_find.c | 49 ++++++++ 7 files changed, 333 insertions(+), 71 deletions(-) create mode 100644 Documentation/core-api/union_find.rst create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst create mode 100644 include/linux/union_find.h create mode 100644 lib/union_find.c -- 2.45.0
On 7/4/24 02:24, Xavier wrote: > Hi all, > > Based on Michal's suggestion, the following changes were made: > 1. Changed Union-Find to union-find in all places except the title. > 2. Optimized the logic of the uf_union function. > 3. Modified places where csa[i]->node.parent was used directly. > > To Longman, > Regarding the modifications for supporting cpuset merging in both cgroup > v1 and v2, do you mean that you will continue to complete them after my > patch is merged? Yes. > > Kindly review. > > Xavier (2): > Union-Find: add a new module in kernel library > cpuset: use Union-Find to optimize the merging of cpumasks > > Documentation/core-api/union_find.rst | 102 ++++++++++++++++ > .../zh_CN/core-api/union_find.rst | 87 +++++++++++++ > MAINTAINERS | 9 ++ > include/linux/union_find.h | 41 +++++++ > kernel/cgroup/cpuset.c | 114 +++++++----------- > lib/Makefile | 2 +- > lib/union_find.c | 49 ++++++++ > 7 files changed, 333 insertions(+), 71 deletions(-) > create mode 100644 Documentation/core-api/union_find.rst > create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst > create mode 100644 include/linux/union_find.h > create mode 100644 lib/union_find.c > The patch series looks good to me. However, it is a still major change in the domain generation algorithm and it is too late for v6.11. I would also like it to spend more time in linux-next as I don't have a good set of cgroup v1 test. I will support merging this for v6.12. Acked-by: Waiman Long <longman@redhat.com>
On Sun, Jul 07, 2024 at 09:59:55PM -0400, Waiman Long wrote: > The patch series looks good to me. However, it is a still major change in > the domain generation algorithm and it is too late for v6.11. I would also > like it to spend more time in linux-next as I don't have a good set of > cgroup v1 test. I will support merging this for v6.12. > > Acked-by: Waiman Long <longman@redhat.com> Xavier, as we're pretty close to the merge window, I think it'd be best to do this in the next merge window as Waiman said. Can you please ping me once v6.11-rc1 is cut? I'll apply the two patches on cgroup/for-6.12. Thanks. -- tejun
Hi Tejun, I saw on kernel.org that v6.11-rc1 has been released. It might be time to start merging this patch. By the way, I have submitted an optimization patch for RT group scheduling, but after two rounds of communication, I haven't received any further responses. Could you provide me with some advice? https://lore.kernel.org/all/20240627172156.235421-1-xavier_qy@163.com/ Thanks. At 2024-07-09 02:38:33, "Tejun Heo" <tj@kernel.org> wrote: >On Sun, Jul 07, 2024 at 09:59:55PM -0400, Waiman Long wrote: >> The patch series looks good to me. However, it is a still major change in >> the domain generation algorithm and it is too late for v6.11. I would also >> like it to spend more time in linux-next as I don't have a good set of >> cgroup v1 test. I will support merging this for v6.12. >> >> Acked-by: Waiman Long <longman@redhat.com> > >Xavier, as we're pretty close to the merge window, I think it'd be best to >do this in the next merge window as Waiman said. Can you please ping me once >v6.11-rc1 is cut? I'll apply the two patches on cgroup/for-6.12. > -- Best Regards, Xavier
Hello, On Mon, Jul 29, 2024 at 10:44:08AM +0800, Xavier wrote: > I saw on kernel.org that v6.11-rc1 has been released. It might be time to start merging > this patch. Merged two patches. > By the way, I have submitted an optimization patch for RT group scheduling, but after > two rounds of communication, I haven't received any further responses. Could you > provide me with some advice? > > https://lore.kernel.org/all/20240627172156.235421-1-xavier_qy@163.com/ I'm not sure I have a useful advice other than just pinging again. Thanks. -- tejun
Hi tejun, Sure, that works. We can wait to merge it into the cgroup/for-6.12 branch. I will ping you once v6.11-rc1 is cut. Thank you. -- Best Regards, Xavier At 2024-07-09 02:38:33, "Tejun Heo" <tj@kernel.org> wrote: >On Sun, Jul 07, 2024 at 09:59:55PM -0400, Waiman Long wrote: >> The patch series looks good to me. However, it is a still major change in >> the domain generation algorithm and it is too late for v6.11. I would also >> like it to spend more time in linux-next as I don't have a good set of >> cgroup v1 test. I will support merging this for v6.12. >> >> Acked-by: Waiman Long <longman@redhat.com> > >Xavier, as we're pretty close to the merge window, I think it'd be best to >do this in the next merge window as Waiman said. Can you please ping me once >v6.11-rc1 is cut? I'll apply the two patches on cgroup/for-6.12. > >Thanks. > >-- >tejun
This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.
Signed-off-by: Xavier <xavier_qy@163.com>
---
Documentation/core-api/union_find.rst | 102 ++++++++++++++++++
.../zh_CN/core-api/union_find.rst | 87 +++++++++++++++
MAINTAINERS | 9 ++
include/linux/union_find.h | 41 +++++++
lib/Makefile | 2 +-
lib/union_find.c | 49 +++++++++
6 files changed, 289 insertions(+), 1 deletion(-)
create mode 100644 Documentation/core-api/union_find.rst
create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
create mode 100644 include/linux/union_find.h
create mode 100644 lib/union_find.c
diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst
new file mode 100644
index 0000000000..2bf0290c91
--- /dev/null
+++ b/Documentation/core-api/union_find.rst
@@ -0,0 +1,102 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <xavier_qy@163.com>
+
+What is union-find, and what is it used for?
+------------------------------------------------
+
+Union-find is a data structure used to handle the merging and querying
+of disjoint sets. The primary operations supported by union-find are:
+
+ Initialization: Resetting each element as an individual set, with
+ each set's initial parent node pointing to itself.
+ Find: Determine which set a particular element belongs to, usually by
+ returning a “representative element” of that set. This operation
+ is used to check if two elements are in the same set.
+ Union: Merge two sets into one.
+
+As a data structure used to maintain sets (groups), union-find is commonly
+utilized to solve problems related to offline queries, dynamic connectivity,
+and graph theory. It is also a key component in Kruskal's algorithm for
+computing the minimum spanning tree, which is crucial in scenarios like
+network routing. Consequently, union-find is widely referenced. Additionally,
+union-find has applications in symbolic computation, register allocation,
+and more.
+
+Space Complexity: O(n), where n is the number of nodes.
+
+Time Complexity: Using path compression can reduce the time complexity of
+the find operation, and using union by rank can reduce the time complexity
+of the union operation. These optimizations reduce the average time
+complexity of each find and union operation to O(α(n)), where α(n) is the
+inverse Ackermann function. This can be roughly considered a constant time
+complexity for practical purposes.
+
+This document covers use of the Linux union-find implementation. For more
+information on the nature and implementation of union-find, see:
+
+ Wikipedia entry on union-find
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+Linux implementation of union-find
+-----------------------------------
+
+Linux's union-find implementation resides in the file "lib/union_find.c".
+To use it, "#include <linux/union_find.h>".
+
+The union-find data structure is defined as follows::
+
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+
+In this structure, parent points to the parent node of the current node.
+The rank field represents the height of the current tree. During a union
+operation, the tree with the smaller rank is attached under the tree with the
+larger rank to maintain balance.
+
+Initializing union-find
+--------------------
+
+You can complete the initialization using either static or initialization
+interface. Initialize the parent pointer to point to itself and set the rank
+to 0.
+Example::
+
+ struct uf_node my_node = UF_INIT_NODE(my_node);
+or
+ uf_node_init(&my_node);
+
+Find the Root Node of union-find
+--------------------------------
+
+This operation is mainly used to determine whether two nodes belong to the same
+set in the union-find. If they have the same root, they are in the same set.
+During the find operation, path compression is performed to improve the
+efficiency of subsequent find operations.
+Example::
+
+ int connected;
+ struct uf_node *root1 = uf_find(&node_1);
+ struct uf_node *root2 = uf_find(&node_2);
+ if (root1 == root2)
+ connected = 1;
+ else
+ connected = 0;
+
+Union Two Sets in union-find
+----------------------------
+
+To union two sets in the union-find, you first find their respective root nodes
+and then link the smaller node to the larger node based on the rank of the root
+nodes.
+Example::
+
+ uf_union(&node_1, &node_2);
diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Documentation/translations/zh_CN/core-api/union_find.rst
new file mode 100644
index 0000000000..a56de57147
--- /dev/null
+++ b/Documentation/translations/zh_CN/core-api/union_find.rst
@@ -0,0 +1,87 @@
+.. SPDX-License-Identifier: GPL-2.0
+.. include:: ../disclaimer-zh_CN.rst
+
+:Original: Documentation/core-api/union_find.rst
+
+===========================
+Linux中的并查集（Union-Find）
+===========================
+
+
+:日期: 2024年6月21日
+:作者: Xavier <xavier_qy@163.com>
+
+何为并查集，它有什么用？
+---------------------
+
+并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：
+ 初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身
+ 查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为
+ 了判断两个元素是否在同一个集合之中。
+ 合并：将两个集合合并为一个。
+
+并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和
+图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在
+网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分
+配等方面也有应用。
+
+空间复杂度: O(n)，n为节点数。
+
+时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的
+时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿
+克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。
+
+本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：
+
+ 维基百科并查集词条
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+并查集的Linux实现
+----------------
+
+Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需要
+“#include <linux/union_find.h>”。
+
+并查集的数据结构定义如下::
+
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大
+的节点下面以增加平衡性。
+
+初始化并查集
+---------
+
+可以采用静态或初始化接口完成初始化操作。初始化时，parent 指针指向自身，rank 设置
+为 0。
+示例::
+
+ struct uf_node my_node = UF_INIT_NODE(my_node);
+或
+ uf_node_init(&my_node);
+
+查找并查集的根节点
+----------------
+
+主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中
+会对路径进行压缩，提高后续查找效率。
+示例::
+
+ int connected;
+ struct uf_node *root1 = uf_find(&node_1);
+ struct uf_node *root2 = uf_find(&node_2);
+ if (root1 == root2)
+ connected = 1;
+ else
+ connected = 0;
+
+合并两个并查集
+-------------
+
+对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的
+节点连接到大的节点下面。
+示例::
+
+ uf_union(&node_1, &node_2);
diff --git a/MAINTAINERS b/MAINTAINERS
index 2ca8f35dfe..16171dbca3 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23051,6 +23051,15 @@ F: drivers/cdrom/cdrom.c
F: include/linux/cdrom.h
F: include/uapi/linux/cdrom.h
+UNION-FIND
+M: Xavier <xavier_qy@163.com>
+L: linux-kernel@vger.kernel.org
+S: Maintained
+F: Documentation/core-api/union_find.rst
+F: Documentation/translations/zh_CN/core-api/union_find.rst
+F: include/linux/union_find.h
+F: lib/union_find.c
+
UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
R: Alim Akhtar <alim.akhtar@samsung.com>
R: Avri Altman <avri.altman@wdc.com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..cfd49263c1
--- /dev/null
+++ b/include/linux/union_find.h
@@ -0,0 +1,41 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+/**
+ * union_find.h - union-find data structure implementation
+ *
+ * This header provides functions and structures to implement the union-find
+ * data structure. The union-find data structure is used to manage disjoint
+ * sets and supports efficient union and find operations.
+ *
+ * See Documentation/core-api/union_find.rst for documentation and samples.
+ */
+
+struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+};
+
+/* This macro is used for static initialization of a union-find node. */
+#define UF_INIT_NODE(node) {.parent = &node, .rank = 0}
+
+/**
+ * uf_node_init - Initialize a union-find node
+ * @node: pointer to the union-find node to be initialized
+ *
+ * This function sets the parent of the node to itself and
+ * initializes its rank to 0.
+ */
+static inline void uf_node_init(struct uf_node *node)
+{
+ node->parent = node;
+ node->rank = 0;
+}
+
+/* find the root of a node */
+struct uf_node *uf_find(struct uf_node *node);
+
+/* Merge two intersecting nodes */
+void uf_union(struct uf_node *node1, struct uf_node *node2);
+
+#endif /* __LINUX_UNION_FIND_H */
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
nmi_backtrace.o win_minmax.o memcat_p.o \
- buildid.o objpool.o
+ buildid.o objpool.o union_find.o
lib-$(CONFIG_PRINTK) += dump_stack.o
lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..413b0f8adf
--- /dev/null
+++ b/lib/union_find.c
@@ -0,0 +1,49 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+/**
+ * uf_find - Find the root of a node and perform path compression
+ * @node: the node to find the root of
+ *
+ * This function returns the root of the node by following the parent
+ * pointers. It also performs path compression, making the tree shallower.
+ *
+ * Returns the root node of the set containing node.
+ */
+struct uf_node *uf_find(struct uf_node *node)
+{
+ struct uf_node *parent;
+
+ while (node->parent != node) {
+ parent = node->parent;
+ node->parent = parent->parent;
+ node = parent;
+ }
+ return node;
+}
+
+/**
+ * uf_union - Merge two sets, using union by rank
+ * @node1: the first node
+ * @node2: the second node
+ *
+ * This function merges the sets containing node1 and node2, by comparing
+ * the ranks to keep the tree balanced.
+ */
+void uf_union(struct uf_node *node1, struct uf_node *node2)
+{
+ struct uf_node *root1 = uf_find(node1);
+ struct uf_node *root2 = uf_find(node2);
+
+ if (root1 == root2)
+ return;
+
+ if (root1->rank < root2->rank) {
+ root1->parent = root2;
+ } else if (root1->rank > root2->rank) {
+ root2->parent = root1;
+ } else {
+ root2->parent = root1;
+ root1->rank++;
+ }
+}
--
2.45.0
On Thu, Jul 04, 2024 at 02:24:43PM +0800, Xavier wrote: > This patch implements a union-find data structure in the kernel library, > which includes operations for allocating nodes, freeing nodes, > finding the root of a node, and merging two nodes. > > Signed-off-by: Xavier <xavier_qy@163.com> Applied to cgroup/for-6.12. Thanks. -- tejun
The process of constructing scheduling domains
involves multiple loops and repeated evaluations, leading to numerous
redundant and ineffective assessments that impact code efficiency.
Here, we use union-find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.
Signed-off-by: Xavier <xavier_qy@163.com>
---
kernel/cgroup/cpuset.c | 114 ++++++++++++++++-------------------------
1 file changed, 44 insertions(+), 70 deletions(-)
diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index fe76045aa5..0037371986 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -45,6 +45,7 @@
#include <linux/cgroup.h>
#include <linux/wait.h>
#include <linux/workqueue.h>
+#include <linux/union_find.h>
DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
@@ -172,9 +173,6 @@ struct cpuset {
*/
int attach_in_progress;
- /* partition number for rebuild_sched_domains() */
- int pn;
-
/* for custom sched domain */
int relax_domain_level;
@@ -208,6 +206,9 @@ struct cpuset {
/* Remote partition silbling list anchored at remote_children */
struct list_head remote_sibling;
+
+ /* Used to merge intersecting subsets for generate_sched_domains */
+ struct uf_node node;
};
/*
@@ -988,18 +989,15 @@ static inline int nr_cpusets(void)
* were changed (added or removed.)
*
* Finding the best partition (set of domains):
- * The triple nested loops below over i, j, k scan over the
- * load balanced cpusets (using the array of cpuset pointers in
- * csa[]) looking for pairs of cpusets that have overlapping
- * cpus_allowed, but which don't have the same 'pn' partition
- * number and gives them in the same partition number. It keeps
- * looping on the 'restart' label until it can no longer find
- * any such pairs.
+ * The double nested loops below over i, j scan over the load
+ * balanced cpusets (using the array of cpuset pointers in csa[])
+ * looking for pairs of cpusets that have overlapping cpus_allowed
+ * and merging them using a union-find algorithm.
+ *
+ * The union of the cpus_allowed masks from the set of all cpusets
+ * having the same root then form the one element of the partition
+ * (one sched domain) to be passed to partition_sched_domains().
*
- * The union of the cpus_allowed masks from the set of
- * all cpusets having the same 'pn' value then form the one
- * element of the partition (one sched domain) to be passed to
- * partition_sched_domains().
*/
static int generate_sched_domains(cpumask_var_t **domains,
struct sched_domain_attr **attributes)
@@ -1007,7 +1005,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
struct cpuset *cp; /* top-down scan of cpusets */
struct cpuset **csa; /* array of all cpuset ptrs */
int csn; /* how many cpuset ptrs in csa so far */
- int i, j, k; /* indices for partition finding loops */
+ int i, j; /* indices for partition finding loops */
cpumask_var_t *doms; /* resulting partition; i.e. sched domains */
struct sched_domain_attr *dattr; /* attributes for custom domains */
int ndoms = 0; /* number of sched domains in result */
@@ -1015,6 +1013,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
struct cgroup_subsys_state *pos_css;
bool root_load_balance = is_sched_load_balance(&top_cpuset);
bool cgrpv2 = cgroup_subsys_on_dfl(cpuset_cgrp_subsys);
+ int nslot_update;
doms = NULL;
dattr = NULL;
@@ -1102,31 +1101,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
if (root_load_balance && (csn == 1))
goto single_root_domain;
- for (i = 0; i < csn; i++)
- csa[i]->pn = i;
- ndoms = csn;
-
-restart:
- /* Find the best partition (set of sched domains) */
- for (i = 0; i < csn; i++) {
- struct cpuset *a = csa[i];
- int apn = a->pn;
-
- for (j = 0; j < csn; j++) {
- struct cpuset *b = csa[j];
- int bpn = b->pn;
-
- if (apn != bpn && cpusets_overlap(a, b)) {
- for (k = 0; k < csn; k++) {
- struct cpuset *c = csa[k];
+ if (!cgrpv2) {
+ for (i = 0; i < csn; i++)
+ uf_node_init(&csa[i]->node);
- if (c->pn == bpn)
- c->pn = apn;
- }
- ndoms--; /* one less element */
- goto restart;
+ /* Merge overlapping cpusets */
+ for (i = 0; i < csn; i++) {
+ for (j = i + 1; j < csn; j++) {
+ if (cpusets_overlap(csa[i], csa[j]))
+ uf_union(&csa[i]->node, &csa[j]->node);
}
}
+
+ /* Count the total number of domains */
+ for (i = 0; i < csn; i++) {
+ if (uf_find(&csa[i]->node) == &csa[i]->node)
+ ndoms++;
+ }
+ } else {
+ ndoms = csn;
}
/*
@@ -1159,44 +1152,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
}
for (nslot = 0, i = 0; i < csn; i++) {
- struct cpuset *a = csa[i];
- struct cpumask *dp;
- int apn = a->pn;
-
- if (apn < 0) {
- /* Skip completed partitions */
- continue;
- }
-
- dp = doms[nslot];
-
- if (nslot == ndoms) {
- static int warnings = 10;
- if (warnings) {
- pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
- nslot, ndoms, csn, i, apn);
- warnings--;
- }
- continue;
- }
-
- cpumask_clear(dp);
- if (dattr)
- *(dattr + nslot) = SD_ATTR_INIT;
+ nslot_update = 0;
for (j = i; j < csn; j++) {
- struct cpuset *b = csa[j];
-
- if (apn == b->pn) {
- cpumask_or(dp, dp, b->effective_cpus);
+ if (uf_find(&csa[j]->node) == &csa[i]->node) {
+ struct cpumask *dp = doms[nslot];
+
+ if (i == j) {
+ nslot_update = 1;
+ cpumask_clear(dp);
+ if (dattr)
+ *(dattr + nslot) = SD_ATTR_INIT;
+ }
+ cpumask_or(dp, dp, csa[j]->effective_cpus);
cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN));
if (dattr)
- update_domain_attr_tree(dattr + nslot, b);
-
- /* Done with this partition */
- b->pn = -1;
+ update_domain_attr_tree(dattr + nslot, csa[j]);
}
}
- nslot++;
+ if (nslot_update)
+ nslot++;
}
BUG_ON(nslot != ndoms);
--
2.45.0On Thu, Jul 04, 2024 at 02:24:44PM +0800, Xavier wrote: > The process of constructing scheduling domains > involves multiple loops and repeated evaluations, leading to numerous > redundant and ineffective assessments that impact code efficiency. > > Here, we use union-find to optimize the merging of cpumasks. By employing > path compression and union by rank, we effectively reduce the number of > lookups and merge comparisons. > > Signed-off-by: Xavier <xavier_qy@163.com> Applied to cgroup/for-6.12. Thanks. -- tejun
On Tue, 2 Jul 2024 09:22:44 -1000 Tejun Heo <tj@kernel.org> wrote: > On Tue, Jul 02, 2024 at 06:50:08PM +0800, Xavier wrote: > > Hi Tejun, > > > > Thank you for thoroughly reviewing the code and pointing out the issues. > > I have made the necessary changes to the code, comments, and documentation > > based on your suggestions. > > Looks fine to me. Once Waiman is okay with it, I can carry it through the > cgroup tree. Andrew, any objections? Xavier, it'd really great if you can do > more conversions so that it's not a single use thing. > OK by me. cpuset patches live in the cgroup tree, no? Nit: if there is to be another spin /* please do this */ /*and not this*/
Hello, On Tue, Jul 02, 2024 at 05:31:37PM -0700, Andrew Morton wrote: > OK by me. cpuset patches live in the cgroup tree, no? Yeah, so, if the cpuset conversion part looks okay, it'd make the sense to route it through the cgroup tree. Otherwise, we can also route the cpuset conversion through -mm too. Either way sounds fine to me. Thanks. -- tejun
This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.
Signed-off-by: Xavier <xavier_qy@163.com>
---
Documentation/core-api/union_find.rst | 102 ++++++++++++++++++
.../zh_CN/core-api/union_find.rst | 87 +++++++++++++++
MAINTAINERS | 9 ++
include/linux/union_find.h | 41 +++++++
lib/Makefile | 2 +-
lib/union_find.c | 48 +++++++++
6 files changed, 288 insertions(+), 1 deletion(-)
create mode 100644 Documentation/core-api/union_find.rst
create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
create mode 100644 include/linux/union_find.h
create mode 100644 lib/union_find.c
diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst
new file mode 100644
index 0000000000..be9f68fd6d
--- /dev/null
+++ b/Documentation/core-api/union_find.rst
@@ -0,0 +1,102 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <xavier_qy@163.com>
+
+What is Union-Find, and what is it used for?
+------------------------------------------------
+
+Union-Find is a data structure used to handle the merging and querying
+of disjoint sets. The primary operations supported by Union-Find are:
+
+ Initialization: Resetting each element as an individual set, with
+ each set's initial parent node pointing to itself.
+ Find: Determine which set a particular element belongs to, usually by
+ returning a “representative element” of that set. This operation
+ is used to check if two elements are in the same set.
+ Union: Merge two sets into one.
+
+As a data structure used to maintain sets (groups), Union-Find is commonly
+utilized to solve problems related to offline queries, dynamic connectivity,
+and graph theory. It is also a key component in Kruskal's algorithm for
+computing the minimum spanning tree, which is crucial in scenarios like
+network routing. Consequently, Union-Find is widely referenced. Additionally,
+Union-Find has applications in symbolic computation, register allocation,
+and more.
+
+Space Complexity: O(n), where n is the number of nodes.
+
+Time Complexity: Using path compression can reduce the time complexity of
+the find operation, and using union by rank can reduce the time complexity
+of the union operation. These optimizations reduce the average time
+complexity of each find and union operation to O(α(n)), where α(n) is the
+inverse Ackermann function. This can be roughly considered a constant time
+complexity for practical purposes.
+
+This document covers use of the Linux union-find implementation. For more
+information on the nature and implementation of Union-Find, see:
+
+ Wikipedia entry on union-find
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+Linux implementation of union-find
+-----------------------------------
+
+Linux's union-find implementation resides in the file "lib/union_find.c".
+To use it, "#include <linux/union_find.h>".
+
+The Union-Find data structure is defined as follows::
+
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+
+In this structure, parent points to the parent node of the current node.
+The rank field represents the height of the current tree. During a union
+operation, the tree with the smaller rank is attached under the tree with the
+larger rank to maintain balance.
+
+Initializing Union-Find
+--------------------
+
+You can complete the initialization using either static or initialization
+interface. Initialize the parent pointer to point to itself and set the rank
+to 0.
+Example::
+
+ struct uf_node my_node = UF_INIT_NODE(my_node);
+or
+ uf_node_init(&my_node);
+
+Find the Root Node of Union-Find
+--------------------------------
+
+This operation is mainly used to determine whether two nodes belong to the same
+set in the Union-Find. If they have the same root, they are in the same set.
+During the find operation, path compression is performed to improve the
+efficiency of subsequent find operations.
+Example::
+
+ int connected;
+ struct uf_node *root1 = uf_find(&node_1);
+ struct uf_node *root2 = uf_find(&node_2);
+ if (root1 == root2)
+ connected = 1;
+ else
+ connected = 0;
+
+Union Two Sets in Union-Find
+----------------------------
+
+To union two sets in the Union-Find, you first find their respective root nodes
+and then link the smaller node to the larger node based on the rank of the root
+nodes.
+Example::
+
+ uf_union(&node_1, &node_2);
diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Documentation/translations/zh_CN/core-api/union_find.rst
new file mode 100644
index 0000000000..a56de57147
--- /dev/null
+++ b/Documentation/translations/zh_CN/core-api/union_find.rst
@@ -0,0 +1,87 @@
+.. SPDX-License-Identifier: GPL-2.0
+.. include:: ../disclaimer-zh_CN.rst
+
+:Original: Documentation/core-api/union_find.rst
+
+===========================
+Linux中的并查集（Union-Find）
+===========================
+
+
+:日期: 2024年6月21日
+:作者: Xavier <xavier_qy@163.com>
+
+何为并查集，它有什么用？
+---------------------
+
+并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：
+ 初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身
+ 查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为
+ 了判断两个元素是否在同一个集合之中。
+ 合并：将两个集合合并为一个。
+
+并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和
+图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在
+网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分
+配等方面也有应用。
+
+空间复杂度: O(n)，n为节点数。
+
+时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的
+时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿
+克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。
+
+本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：
+
+ 维基百科并查集词条
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+并查集的Linux实现
+----------------
+
+Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需要
+“#include <linux/union_find.h>”。
+
+并查集的数据结构定义如下::
+
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大
+的节点下面以增加平衡性。
+
+初始化并查集
+---------
+
+可以采用静态或初始化接口完成初始化操作。初始化时，parent 指针指向自身，rank 设置
+为 0。
+示例::
+
+ struct uf_node my_node = UF_INIT_NODE(my_node);
+或
+ uf_node_init(&my_node);
+
+查找并查集的根节点
+----------------
+
+主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中
+会对路径进行压缩，提高后续查找效率。
+示例::
+
+ int connected;
+ struct uf_node *root1 = uf_find(&node_1);
+ struct uf_node *root2 = uf_find(&node_2);
+ if (root1 == root2)
+ connected = 1;
+ else
+ connected = 0;
+
+合并两个并查集
+-------------
+
+对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的
+节点连接到大的节点下面。
+示例::
+
+ uf_union(&node_1, &node_2);
diff --git a/MAINTAINERS b/MAINTAINERS
index 2ca8f35dfe..16171dbca3 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23051,6 +23051,15 @@ F: drivers/cdrom/cdrom.c
F: include/linux/cdrom.h
F: include/uapi/linux/cdrom.h
+UNION-FIND
+M: Xavier <xavier_qy@163.com>
+L: linux-kernel@vger.kernel.org
+S: Maintained
+F: Documentation/core-api/union_find.rst
+F: Documentation/translations/zh_CN/core-api/union_find.rst
+F: include/linux/union_find.h
+F: lib/union_find.c
+
UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
R: Alim Akhtar <alim.akhtar@samsung.com>
R: Avri Altman <avri.altman@wdc.com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..45b7aa66a6
--- /dev/null
+++ b/include/linux/union_find.h
@@ -0,0 +1,41 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+/**
+ * union_find.h - Union-Find data structure implementation
+ *
+ * This header provides functions and structures to implement the Union-Find
+ * data structure. The Union-Find data structure is used to manage disjoint
+ * sets and supports efficient union and find operations.
+ *
+ * See Documentation/core-api/union_find.rst for documentation and samples.
+ */
+
+struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+};
+
+/* This macro is used for static initialization of a union-find node. */
+#define UF_INIT_NODE(node) {.parent = &node, .rank = 0}
+
+/**
+ * uf_node_init - Initialize a union-find node
+ * @node: pointer to the union-find node to be initialized
+ *
+ * This function sets the parent of the node to itself and
+ * initializes its rank to 0.
+ */
+static inline void uf_node_init(struct uf_node *node)
+{
+ node->parent = node;
+ node->rank = 0;
+}
+
+/* find the root of a node*/
+struct uf_node *uf_find(struct uf_node *node);
+
+/* Merge two intersecting nodes */
+void uf_union(struct uf_node *node1, struct uf_node *node2);
+
+#endif /*__LINUX_UNION_FIND_H*/
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
nmi_backtrace.o win_minmax.o memcat_p.o \
- buildid.o objpool.o
+ buildid.o objpool.o union_find.o
lib-$(CONFIG_PRINTK) += dump_stack.o
lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..bec574ad24
--- /dev/null
+++ b/lib/union_find.c
@@ -0,0 +1,48 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+/**
+ * uf_find - Find the root of a node and perform path compression
+ * @node: the node to find the root of
+ *
+ * This function returns the root of the node by following the parent
+ * pointers. It also performs path compression, making the tree shallower.
+ *
+ * Returns the root node of the set containing node.
+ */
+struct uf_node *uf_find(struct uf_node *node)
+{
+ struct uf_node *parent;
+
+ while (node->parent != node) {
+ parent = node->parent;
+ node->parent = parent->parent;
+ node = parent;
+ }
+ return node;
+}
+
+/**
+ * uf_union - Merge two sets, using union by rank
+ * @node1: the first node
+ * @node2: the second node
+ *
+ * This function merges the sets containing node1 and node2, by comparing
+ * the ranks to keep the tree balanced.
+ */
+void uf_union(struct uf_node *node1, struct uf_node *node2)
+{
+ struct uf_node *root1 = uf_find(node1);
+ struct uf_node *root2 = uf_find(node2);
+
+ if (root1 != root2) {
+ if (root1->rank < root2->rank) {
+ root1->parent = root2;
+ } else if (root1->rank > root2->rank) {
+ root2->parent = root1;
+ } else {
+ root2->parent = root1;
+ root1->rank++;
+ }
+ }
+}
--
2.45.0
The process of constructing scheduling domains
involves multiple loops and repeated evaluations, leading to numerous
redundant and ineffective assessments that impact code efficiency.
Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.
Signed-off-by: Xavier <xavier_qy@163.com>
---
kernel/cgroup/cpuset.c | 95 ++++++++++++++++--------------------------
1 file changed, 36 insertions(+), 59 deletions(-)
diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index fe76045aa5..4d32cd1407 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -45,6 +45,7 @@
#include <linux/cgroup.h>
#include <linux/wait.h>
#include <linux/workqueue.h>
+#include <linux/union_find.h>
DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
@@ -172,9 +173,6 @@ struct cpuset {
*/
int attach_in_progress;
- /* partition number for rebuild_sched_domains() */
- int pn;
-
/* for custom sched domain */
int relax_domain_level;
@@ -208,6 +206,9 @@ struct cpuset {
/* Remote partition silbling list anchored at remote_children */
struct list_head remote_sibling;
+
+ /* Used to merge intersecting subsets for generate_sched_domains*/
+ struct uf_node node;
};
/*
@@ -1007,7 +1008,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
struct cpuset *cp; /* top-down scan of cpusets */
struct cpuset **csa; /* array of all cpuset ptrs */
int csn; /* how many cpuset ptrs in csa so far */
- int i, j, k; /* indices for partition finding loops */
+ int i, j; /* indices for partition finding loops */
cpumask_var_t *doms; /* resulting partition; i.e. sched domains */
struct sched_domain_attr *dattr; /* attributes for custom domains */
int ndoms = 0; /* number of sched domains in result */
@@ -1015,6 +1016,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
struct cgroup_subsys_state *pos_css;
bool root_load_balance = is_sched_load_balance(&top_cpuset);
bool cgrpv2 = cgroup_subsys_on_dfl(cpuset_cgrp_subsys);
+ int nslot_update;
doms = NULL;
dattr = NULL;
@@ -1102,31 +1104,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
if (root_load_balance && (csn == 1))
goto single_root_domain;
- for (i = 0; i < csn; i++)
- csa[i]->pn = i;
- ndoms = csn;
-
-restart:
- /* Find the best partition (set of sched domains) */
- for (i = 0; i < csn; i++) {
- struct cpuset *a = csa[i];
- int apn = a->pn;
+ if (!cgrpv2) {
+ for (i = 0; i < csn; i++)
+ uf_node_init(&csa[i]->node);
- for (j = 0; j < csn; j++) {
- struct cpuset *b = csa[j];
- int bpn = b->pn;
-
- if (apn != bpn && cpusets_overlap(a, b)) {
- for (k = 0; k < csn; k++) {
- struct cpuset *c = csa[k];
-
- if (c->pn == bpn)
- c->pn = apn;
- }
- ndoms--; /* one less element */
- goto restart;
+ /* Merge overlapping cpusets */
+ for (i = 0; i < csn; i++) {
+ for (j = i + 1; j < csn; j++) {
+ if (cpusets_overlap(csa[i], csa[j]))
+ uf_union(&csa[i]->node, &csa[j]->node);
}
}
+
+ /* Count the total number of domains */
+ for (i = 0; i < csn; i++) {
+ if (csa[i]->node.parent == &csa[i]->node)
+ ndoms++;
+ }
+ } else {
+ ndoms = csn;
}
/*
@@ -1159,44 +1155,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
}
for (nslot = 0, i = 0; i < csn; i++) {
- struct cpuset *a = csa[i];
- struct cpumask *dp;
- int apn = a->pn;
-
- if (apn < 0) {
- /* Skip completed partitions */
- continue;
- }
-
- dp = doms[nslot];
-
- if (nslot == ndoms) {
- static int warnings = 10;
- if (warnings) {
- pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
- nslot, ndoms, csn, i, apn);
- warnings--;
- }
- continue;
- }
-
- cpumask_clear(dp);
- if (dattr)
- *(dattr + nslot) = SD_ATTR_INIT;
+ nslot_update = 0;
for (j = i; j < csn; j++) {
- struct cpuset *b = csa[j];
-
- if (apn == b->pn) {
- cpumask_or(dp, dp, b->effective_cpus);
+ if (uf_find(&csa[j]->node) == &csa[i]->node) {
+ struct cpumask *dp = doms[nslot];
+
+ if (i == j) {
+ nslot_update = 1;
+ cpumask_clear(dp);
+ if (dattr)
+ *(dattr + nslot) = SD_ATTR_INIT;
+ }
+ cpumask_or(dp, dp, csa[j]->effective_cpus);
cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN));
if (dattr)
- update_domain_attr_tree(dattr + nslot, b);
-
- /* Done with this partition */
- b->pn = -1;
+ update_domain_attr_tree(dattr + nslot, csa[j]);
}
}
- nslot++;
+ if (nslot_update)
+ nslot++;
}
BUG_ON(nslot != ndoms);
--
2.45.0On 7/2/24 06:50, Xavier wrote:
> The process of constructing scheduling domains
> involves multiple loops and repeated evaluations, leading to numerous
> redundant and ineffective assessments that impact code efficiency.
>
> Here, we use Union-Find to optimize the merging of cpumasks. By employing
> path compression and union by rank, we effectively reduce the number of
> lookups and merge comparisons.
>
> Signed-off-by: Xavier <xavier_qy@163.com>
> ---
> kernel/cgroup/cpuset.c | 95 ++++++++++++++++--------------------------
> 1 file changed, 36 insertions(+), 59 deletions(-)
>
> diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
> index fe76045aa5..4d32cd1407 100644
> --- a/kernel/cgroup/cpuset.c
> +++ b/kernel/cgroup/cpuset.c
> @@ -45,6 +45,7 @@
> #include <linux/cgroup.h>
> #include <linux/wait.h>
> #include <linux/workqueue.h>
> +#include <linux/union_find.h>
>
> DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
> DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
> @@ -172,9 +173,6 @@ struct cpuset {
> */
> int attach_in_progress;
>
> - /* partition number for rebuild_sched_domains() */
> - int pn;
> -
> /* for custom sched domain */
> int relax_domain_level;
>
> @@ -208,6 +206,9 @@ struct cpuset {
>
> /* Remote partition silbling list anchored at remote_children */
> struct list_head remote_sibling;
> +
> + /* Used to merge intersecting subsets for generate_sched_domains*/
> + struct uf_node node;
> };
>
> /*
> @@ -1007,7 +1008,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
> struct cpuset *cp; /* top-down scan of cpusets */
> struct cpuset **csa; /* array of all cpuset ptrs */
> int csn; /* how many cpuset ptrs in csa so far */
> - int i, j, k; /* indices for partition finding loops */
> + int i, j; /* indices for partition finding loops */
> cpumask_var_t *doms; /* resulting partition; i.e. sched domains */
> struct sched_domain_attr *dattr; /* attributes for custom domains */
> int ndoms = 0; /* number of sched domains in result */
> @@ -1015,6 +1016,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
> struct cgroup_subsys_state *pos_css;
> bool root_load_balance = is_sched_load_balance(&top_cpuset);
> bool cgrpv2 = cgroup_subsys_on_dfl(cpuset_cgrp_subsys);
> + int nslot_update;
>
> doms = NULL;
> dattr = NULL;
> @@ -1102,31 +1104,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
> if (root_load_balance && (csn == 1))
> goto single_root_domain;
>
> - for (i = 0; i < csn; i++)
> - csa[i]->pn = i;
> - ndoms = csn;
> -
> -restart:
> - /* Find the best partition (set of sched domains) */
> - for (i = 0; i < csn; i++) {
> - struct cpuset *a = csa[i];
> - int apn = a->pn;
> + if (!cgrpv2) {
> + for (i = 0; i < csn; i++)
> + uf_node_init(&csa[i]->node);
>
> - for (j = 0; j < csn; j++) {
> - struct cpuset *b = csa[j];
> - int bpn = b->pn;
> -
> - if (apn != bpn && cpusets_overlap(a, b)) {
> - for (k = 0; k < csn; k++) {
> - struct cpuset *c = csa[k];
> -
> - if (c->pn == bpn)
> - c->pn = apn;
> - }
> - ndoms--; /* one less element */
> - goto restart;
> + /* Merge overlapping cpusets */
> + for (i = 0; i < csn; i++) {
> + for (j = i + 1; j < csn; j++) {
> + if (cpusets_overlap(csa[i], csa[j]))
> + uf_union(&csa[i]->node, &csa[j]->node);
> }
> }
> +
> + /* Count the total number of domains */
> + for (i = 0; i < csn; i++) {
> + if (csa[i]->node.parent == &csa[i]->node)
> + ndoms++;
> + }
> + } else {
> + ndoms = csn;
> }
>
> /*
> @@ -1159,44 +1155,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
> }
>
> for (nslot = 0, i = 0; i < csn; i++) {
> - struct cpuset *a = csa[i];
> - struct cpumask *dp;
> - int apn = a->pn;
> -
> - if (apn < 0) {
> - /* Skip completed partitions */
> - continue;
> - }
> -
> - dp = doms[nslot];
> -
> - if (nslot == ndoms) {
> - static int warnings = 10;
> - if (warnings) {
> - pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
> - nslot, ndoms, csn, i, apn);
> - warnings--;
> - }
> - continue;
> - }
> -
> - cpumask_clear(dp);
> - if (dattr)
> - *(dattr + nslot) = SD_ATTR_INIT;
> + nslot_update = 0;
> for (j = i; j < csn; j++) {
> - struct cpuset *b = csa[j];
> -
> - if (apn == b->pn) {
> - cpumask_or(dp, dp, b->effective_cpus);
> + if (uf_find(&csa[j]->node) == &csa[i]->node) {
> + struct cpumask *dp = doms[nslot];
> +
> + if (i == j) {
> + nslot_update = 1;
> + cpumask_clear(dp);
> + if (dattr)
> + *(dattr + nslot) = SD_ATTR_INIT;
> + }
> + cpumask_or(dp, dp, csa[j]->effective_cpus);
> cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN));
> if (dattr)
> - update_domain_attr_tree(dattr + nslot, b);
> -
> - /* Done with this partition */
> - b->pn = -1;
> + update_domain_attr_tree(dattr + nslot, csa[j]);
> }
> }
> - nslot++;
> + if (nslot_update)
> + nslot++;
> }
> BUG_ON(nslot != ndoms);
>
The code change looks OK to me. However, the following comment above
generate_sched_domains() describes the generation process.
* Finding the best partition (set of domains):
* The triple nested loops below over i, j, k scan over the
* load balanced cpusets (using the array of cpuset pointers in
* csa[]) looking for pairs of cpusets that have overlapping
* cpus_allowed, but which don't have the same 'pn' partition
* number and gives them in the same partition number. It keeps
* looping on the 'restart' label until it can no longer find
* any such pairs.
*
* The union of the cpus_allowed masks from the set of
* all cpusets having the same 'pn' value then form the one
* element of the partition (one sched domain) to be passed to
* partition_sched_domains().
This part is no longer correct with your patch. Would you mind updating
it to match what your new patch is doing?
BTW, please also incorporate the Andrew's suggestion about the kernel
convention of writing comments.
Thanks,
Longman
The process of constructing scheduling domains
involves multiple loops and repeated evaluations, leading to numerous
redundant and ineffective assessments that impact code efficiency.
Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.
Signed-off-by: Xavier <xavier_qy@163.com>
---
kernel/cgroup/cpuset.c | 96 ++++++++++++++++--------------------------
1 file changed, 37 insertions(+), 59 deletions(-)
diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index fe76045aa5..c435814ba8 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -45,6 +45,8 @@
#include <linux/cgroup.h>
#include <linux/wait.h>
#include <linux/workqueue.h>
+#include <linux/union_find.h>
+#include <linux/vmalloc.h>
DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
@@ -172,9 +174,6 @@ struct cpuset {
*/
int attach_in_progress;
- /* partition number for rebuild_sched_domains() */
- int pn;
-
/* for custom sched domain */
int relax_domain_level;
@@ -208,6 +207,9 @@ struct cpuset {
/* Remote partition silbling list anchored at remote_children */
struct list_head remote_sibling;
+
+ /* Used to merge intersecting subsets for generate_sched_domains*/
+ struct uf_node node;
};
/*
@@ -1007,7 +1009,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
struct cpuset *cp; /* top-down scan of cpusets */
struct cpuset **csa; /* array of all cpuset ptrs */
int csn; /* how many cpuset ptrs in csa so far */
- int i, j, k; /* indices for partition finding loops */
+ int i, j; /* indices for partition finding loops */
cpumask_var_t *doms; /* resulting partition; i.e. sched domains */
struct sched_domain_attr *dattr; /* attributes for custom domains */
int ndoms = 0; /* number of sched domains in result */
@@ -1015,6 +1017,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
struct cgroup_subsys_state *pos_css;
bool root_load_balance = is_sched_load_balance(&top_cpuset);
bool cgrpv2 = cgroup_subsys_on_dfl(cpuset_cgrp_subsys);
+ int nslot_update;
doms = NULL;
dattr = NULL;
@@ -1102,31 +1105,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
if (root_load_balance && (csn == 1))
goto single_root_domain;
- for (i = 0; i < csn; i++)
- csa[i]->pn = i;
- ndoms = csn;
-
-restart:
- /* Find the best partition (set of sched domains) */
- for (i = 0; i < csn; i++) {
- struct cpuset *a = csa[i];
- int apn = a->pn;
+ if (!cgrpv2) {
+ for (i = 0; i < csn; i++)
+ uf_nodes_init(&csa[i]->node);
- for (j = 0; j < csn; j++) {
- struct cpuset *b = csa[j];
- int bpn = b->pn;
-
- if (apn != bpn && cpusets_overlap(a, b)) {
- for (k = 0; k < csn; k++) {
- struct cpuset *c = csa[k];
-
- if (c->pn == bpn)
- c->pn = apn;
- }
- ndoms--; /* one less element */
- goto restart;
+ /* Merge overlapping cpusets */
+ for (i = 0; i < csn; i++) {
+ for (j = i + 1; j < csn; j++) {
+ if (cpusets_overlap(csa[i], csa[j]))
+ uf_union(&csa[i]->node, &csa[j]->node);
}
}
+
+ /* Count the total number of domains */
+ for (i = 0; i < csn; i++) {
+ if (csa[i]->node.parent == &csa[i]->node)
+ ndoms++;
+ }
+ } else {
+ ndoms = csn;
}
/*
@@ -1159,44 +1156,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
}
for (nslot = 0, i = 0; i < csn; i++) {
- struct cpuset *a = csa[i];
- struct cpumask *dp;
- int apn = a->pn;
-
- if (apn < 0) {
- /* Skip completed partitions */
- continue;
- }
-
- dp = doms[nslot];
-
- if (nslot == ndoms) {
- static int warnings = 10;
- if (warnings) {
- pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
- nslot, ndoms, csn, i, apn);
- warnings--;
- }
- continue;
- }
-
- cpumask_clear(dp);
- if (dattr)
- *(dattr + nslot) = SD_ATTR_INIT;
+ nslot_update = 0;
for (j = i; j < csn; j++) {
- struct cpuset *b = csa[j];
-
- if (apn == b->pn) {
- cpumask_or(dp, dp, b->effective_cpus);
+ if (uf_find(&csa[j]->node) == &csa[i]->node) {
+ struct cpumask *dp = doms[nslot];
+
+ if (i == j) {
+ nslot_update = 1;
+ cpumask_clear(dp);
+ if (dattr)
+ *(dattr + nslot) = SD_ATTR_INIT;
+ }
+ cpumask_or(dp, dp, csa[j]->effective_cpus);
cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN));
if (dattr)
- update_domain_attr_tree(dattr + nslot, b);
-
- /* Done with this partition */
- b->pn = -1;
+ update_domain_attr_tree(dattr + nslot, csa[j]);
}
}
- nslot++;
+ if (nslot_update)
+ nslot++;
}
BUG_ON(nslot != ndoms);
--
2.45.2On Sat, Jun 29, 2024 at 12:13:02AM +0800, Xavier wrote: > The process of constructing scheduling domains > involves multiple loops and repeated evaluations, leading to numerous > redundant and ineffective assessments that impact code efficiency. > > Here, we use Union-Find to optimize the merging of cpumasks. By employing > path compression and union by rank, we effectively reduce the number of > lookups and merge comparisons. > > Signed-off-by: Xavier <xavier_qy@163.com> Waiman, how do you like this conversion? Thanks. -- tejun
This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.
Signed-off-by: Xavier <xavier_qy@163.com>
---
Documentation/core-api/union_find.rst | 101 ++++++++++++++++++
.../zh_CN/core-api/union_find.rst | 86 +++++++++++++++
MAINTAINERS | 9 ++
include/linux/union_find.h | 24 +++++
lib/Makefile | 2 +-
lib/union_find.c | 33 ++++++
6 files changed, 254 insertions(+), 1 deletion(-)
create mode 100644 Documentation/core-api/union_find.rst
create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst
create mode 100644 include/linux/union_find.h
create mode 100644 lib/union_find.c
diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst
new file mode 100644
index 0000000000..38d63b16e5
--- /dev/null
+++ b/Documentation/core-api/union_find.rst
@@ -0,0 +1,101 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <xavier_qy@163.com>
+
+What is Union-Find, and what is it used for?
+------------------------------------------------
+
+Union-Find is a data structure used to handle the merging and querying
+of disjoint sets. The primary operations supported by Union-Find are:
+
+ Initialization: Resetting each element as an individual set, with
+ each set's initial parent node pointing to itself.
+ Find: Determine which set a particular element belongs to, usually by
+ returning a “representative element” of that set. This operation
+ is used to check if two elements are in the same set.
+ Union: Merge two sets into one.
+
+As a data structure used to maintain sets (groups), Union-Find is commonly
+utilized to solve problems related to offline queries, dynamic connectivity,
+and graph theory. It is also a key component in Kruskal's algorithm for
+computing the minimum spanning tree, which is crucial in scenarios like
+network routing. Consequently, Union-Find is widely referenced. Additionally,
+Union-Find has applications in symbolic computation, register allocation,
+and more.
+
+Space Complexity: O(n), where n is the number of nodes.
+
+Time Complexity: Using path compression can reduce the time complexity of
+the find operation, and using union by rank can reduce the time complexity
+of the union operation. These optimizations reduce the average time
+complexity of each find and union operation to O(α(n)), where α(n) is the
+inverse Ackermann function. This can be roughly considered a constant time
+complexity for practical purposes.
+
+This document covers use of the Linux union-find implementation. For more
+information on the nature and implementation of Union-Find, see:
+
+ Wikipedia entry on union-find
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+Linux implementation of union-find
+-----------------------------------
+
+Linux's union-find implementation resides in the file "lib/union_find.c".
+To use it, "#include <linux/union_find.h>".
+
+The Union-Find data structure is defined as follows::
+
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+
+In this structure, parent points to the parent node of the current node.
+The rank field represents the height of the current tree. During a union
+operation, the tree with the smaller rank is attached under the tree with the
+larger rank to maintain balance.
+
+Initializing Union-Find
+--------------------
+
+When initializing the Union-Find data structure, a single pointer to the
+Union-Find instance needs to be passed. Initialize the parent pointer to point
+to itself and set the rank to 0.
+Example::
+
+ struct uf_node *my_node = vzalloc(sizeof(struct uf_node));
+ uf_nodes_init(my_node);
+
+Find the Root Node of Union-Find
+--------------------------------
+
+This operation is mainly used to determine whether two nodes belong to the same
+set in the Union-Find. If they have the same root, they are in the same set.
+During the find operation, path compression is performed to improve the
+efficiency of subsequent find operations.
+Example::
+
+ int connected;
+ struct uf_node *root1 = uf_find(&my_node[0]);
+ struct uf_node *root2 = uf_find(&my_node[1]);
+ if (root1 == root2)
+ connected = 1;
+ else
+ connected = 0;
+
+Union Two Sets in Union-Find
+----------------------------
+
+To union two sets in the Union-Find, you first find their respective root nodes
+and then link the smaller node to the larger node based on the rank of the root
+nodes.
+Example::
+
+ uf_union(&my_node[0], &my_node[1]);
diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Documentation/translations/zh_CN/core-api/union_find.rst
new file mode 100644
index 0000000000..e1b5ae88da
--- /dev/null
+++ b/Documentation/translations/zh_CN/core-api/union_find.rst
@@ -0,0 +1,86 @@
+.. SPDX-License-Identifier: GPL-2.0
+.. include:: ../disclaimer-zh_CN.rst
+
+:Original: Documentation/core-api/union_find.rst
+
+===========================
+Linux中的并查集（Union-Find）
+===========================
+
+
+:日期: 2024年6月21日
+:作者: Xavier <xavier_qy@163.com>
+
+何为并查集，它有什么用？
+---------------------
+
+并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：
+ 初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身
+ 查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为
+ 了判断两个元素是否在同一个集合之中。
+ 合并：将两个集合合并为一个。
+
+并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和
+图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在
+网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分
+配等方面也有应用。
+
+空间复杂度: O(n)，n为节点数。
+
+时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的
+时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿
+克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。
+
+本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：
+
+ 维基百科并查集词条
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+并查集的Linux实现
+----------------
+
+Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需要
+“#include <linux/union_find.h>”。
+
+并查集的数据结构定义如下::
+
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+其中parent为当前节点的父节点，rank为当前树的高度，在合并时将rank小的节点接到rank大
+的节点下面以增加平衡性。
+
+初始化并查集
+---------
+
+初始化并查集时需要传入并查集实例的一个指针。初始化时，parent 指针指向自身，rank 设置
+为 0。
+示例::
+
+ struct uf_node *my_node = vzalloc(sizeof(struct uf_node));
+ uf_nodes_init(my_node);
+
+查找并查集的根节点
+----------------
+
+主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中
+会对路径进行压缩，提高后续查找效率。
+示例::
+
+ int connected;
+ struct uf_node *root1 = uf_find(&my_node[0]);
+ struct uf_node *root2 = uf_find(&my_node[1]);
+ if (root1 == root2)
+ connected = 1;
+ else
+ connected = 0;
+
+合并两个并查集
+-------------
+
+对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的
+节点连接到大的节点下面。
+示例::
+
+ uf_union(&my_node[0], &my_node[1]);
diff --git a/MAINTAINERS b/MAINTAINERS
index d6c90161c7..a1a467c591 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23054,6 +23054,15 @@ F: drivers/cdrom/cdrom.c
F: include/linux/cdrom.h
F: include/uapi/linux/cdrom.h
+UNION-FIND
+M: Xavier <xavier_qy@163.com>
+L: linux-kernel@vger.kernel.org
+S: Maintained
+F: Documentation/core-api/union_find.rst
+F: Documentation/translations/zh_CN/core-api/union_find.rst
+F: include/linux/union_find.h
+F: lib/union_find.c
+
UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
R: Alim Akhtar <alim.akhtar@samsung.com>
R: Avri Altman <avri.altman@wdc.com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..56571c93a5
--- /dev/null
+++ b/include/linux/union_find.h
@@ -0,0 +1,24 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __LINUX_UNION_FIND_H
+#define __LINUX_UNION_FIND_H
+
+/* Define a union-find node struct */
+struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+};
+
+/* Allocate nodes and initialize to 0 */
+static inline void uf_nodes_init(struct uf_node *node)
+{
+ node->parent = node;
+ node->rank = 0;
+}
+
+/* find the root of a node*/
+struct uf_node *uf_find(struct uf_node *node);
+
+/* Merge two intersecting nodes */
+void uf_union(struct uf_node *node1, struct uf_node *node2);
+
+#endif /*__LINUX_UNION_FIND_H*/
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
nmi_backtrace.o win_minmax.o memcat_p.o \
- buildid.o objpool.o
+ buildid.o objpool.o union_find.o
lib-$(CONFIG_PRINTK) += dump_stack.o
lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..bb48b4b129
--- /dev/null
+++ b/lib/union_find.c
@@ -0,0 +1,33 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/union_find.h>
+
+struct uf_node *uf_find(struct uf_node *node)
+{
+ struct uf_node *parent;
+
+ /*Find the root node and perform path compression at the same time*/
+ while (node->parent != node) {
+ parent = node->parent;
+ node->parent = parent->parent;
+ node = parent;
+ }
+ return node;
+}
+
+/*Function to merge two sets, using union by rank*/
+void uf_union(struct uf_node *node1, struct uf_node *node2)
+{
+ struct uf_node *root1 = uf_find(node1);
+ struct uf_node *root2 = uf_find(node2);
+
+ if (root1 != root2) {
+ if (root1->rank < root2->rank) {
+ root1->parent = root2;
+ } else if (root1->rank > root2->rank) {
+ root2->parent = root1;
+ } else {
+ root2->parent = root1;
+ root1->rank++;
+ }
+ }
+}
--
2.45.2
The process of constructing scheduling domains
involves multiple loops and repeated evaluations, leading to numerous
redundant and ineffective assessments that impact code efficiency.
Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.
Signed-off-by: Xavier <xavier_qy@163.com>
---
kernel/cgroup/cpuset.c | 99 +++++++++++++++++-------------------------
1 file changed, 41 insertions(+), 58 deletions(-)
diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index fe76045aa5..d459cfddcb 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -45,6 +45,8 @@
#include <linux/cgroup.h>
#include <linux/wait.h>
#include <linux/workqueue.h>
+#include <linux/union_find.h>
+#include <linux/vmalloc.h>
DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
@@ -172,9 +174,6 @@ struct cpuset {
*/
int attach_in_progress;
- /* partition number for rebuild_sched_domains() */
- int pn;
-
/* for custom sched domain */
int relax_domain_level;
@@ -1007,7 +1006,7 @@ static int generate_sched_domains(cpumask_var_t **domains,
struct cpuset *cp; /* top-down scan of cpusets */
struct cpuset **csa; /* array of all cpuset ptrs */
int csn; /* how many cpuset ptrs in csa so far */
- int i, j, k; /* indices for partition finding loops */
+ int i, j; /* indices for partition finding loops */
cpumask_var_t *doms; /* resulting partition; i.e. sched domains */
struct sched_domain_attr *dattr; /* attributes for custom domains */
int ndoms = 0; /* number of sched domains in result */
@@ -1015,6 +1014,8 @@ static int generate_sched_domains(cpumask_var_t **domains,
struct cgroup_subsys_state *pos_css;
bool root_load_balance = is_sched_load_balance(&top_cpuset);
bool cgrpv2 = cgroup_subsys_on_dfl(cpuset_cgrp_subsys);
+ struct uf_node *nodes = NULL;
+ int nslot_update;
doms = NULL;
dattr = NULL;
@@ -1102,31 +1103,29 @@ static int generate_sched_domains(cpumask_var_t **domains,
if (root_load_balance && (csn == 1))
goto single_root_domain;
- for (i = 0; i < csn; i++)
- csa[i]->pn = i;
- ndoms = csn;
-
-restart:
- /* Find the best partition (set of sched domains) */
- for (i = 0; i < csn; i++) {
- struct cpuset *a = csa[i];
- int apn = a->pn;
-
- for (j = 0; j < csn; j++) {
- struct cpuset *b = csa[j];
- int bpn = b->pn;
+ if (!cgrpv2) {
+ nodes = vzalloc(sizeof(struct uf_node) * csn);
+ if (!nodes)
+ goto done;
- if (apn != bpn && cpusets_overlap(a, b)) {
- for (k = 0; k < csn; k++) {
- struct cpuset *c = csa[k];
+ for (i = 0; i < csn; i++)
+ uf_nodes_init(&nodes[i]);
- if (c->pn == bpn)
- c->pn = apn;
- }
- ndoms--; /* one less element */
- goto restart;
+ /* Merge overlapping cpusets */
+ for (i = 0; i < csn; i++) {
+ for (j = i + 1; j < csn; j++) {
+ if (cpusets_overlap(csa[i], csa[j]))
+ uf_union(&nodes[i], &nodes[j]);
}
}
+
+ /* Count the total number of domains */
+ for (i = 0; i < csn; i++) {
+ if (nodes[i].parent == &nodes[i])
+ ndoms++;
+ }
+ } else {
+ ndoms = csn;
}
/*
@@ -1159,48 +1158,32 @@ static int generate_sched_domains(cpumask_var_t **domains,
}
for (nslot = 0, i = 0; i < csn; i++) {
- struct cpuset *a = csa[i];
- struct cpumask *dp;
- int apn = a->pn;
-
- if (apn < 0) {
- /* Skip completed partitions */
- continue;
- }
-
- dp = doms[nslot];
-
- if (nslot == ndoms) {
- static int warnings = 10;
- if (warnings) {
- pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
- nslot, ndoms, csn, i, apn);
- warnings--;
- }
- continue;
- }
-
- cpumask_clear(dp);
- if (dattr)
- *(dattr + nslot) = SD_ATTR_INIT;
+ nslot_update = 0;
for (j = i; j < csn; j++) {
- struct cpuset *b = csa[j];
-
- if (apn == b->pn) {
- cpumask_or(dp, dp, b->effective_cpus);
+ if (uf_find(&nodes[j]) == &nodes[i]) {
+ struct cpumask *dp = doms[nslot];
+
+ if (i == j) {
+ nslot_update = 1;
+ cpumask_clear(dp);
+ if (dattr)
+ *(dattr + nslot) = SD_ATTR_INIT;
+ }
+ cpumask_or(dp, dp, csa[j]->effective_cpus);
cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN));
if (dattr)
- update_domain_attr_tree(dattr + nslot, b);
-
- /* Done with this partition */
- b->pn = -1;
+ update_domain_attr_tree(dattr + nslot, csa[j]);
}
}
- nslot++;
+ if (nslot_update)
+ nslot++;
}
BUG_ON(nslot != ndoms);
done:
+ if (nodes)
+ vfree(nodes);
+
kfree(csa);
/*
--
2.45.2This patch implements a union-find data structure in the kernel library,
which includes operations for allocating nodes, freeing nodes,
finding the root of a node, and merging two nodes.
Signed-off-by: Xavier <xavier_qy@163.com>
---
Documentation/core-api/union_find.rst | 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
diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst
new file mode 100644
index 0000000000..7109ad608a
--- /dev/null
+++ b/Documentation/core-api/union_find.rst
@@ -0,0 +1,110 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+====================
+Union-Find in Linux
+====================
+
+
+:Date: June 21, 2024
+:Author: Xavier <xavier_qy@163.com>
+
+What is Union-Find, and what is it used for?
+------------------------------------------------
+
+Union-Find is a data structure used to handle the merging and querying
+of disjoint sets. The primary operations supported by Union-Find are:
+
+ Initialization: Resetting each element as an individual set, with
+ each set's initial parent node pointing to itself.
+ Find: Determine which set a particular element belongs to, usually by
+ returning a “representative element” of that set. This operation
+ is used to check if two elements are in the same set.
+ Union: Merge two sets into one.
+
+As a data structure used to maintain sets (groups), Union-Find is commonly
+utilized to solve problems related to offline queries, dynamic connectivity,
+and graph theory. It is also a key component in Kruskal's algorithm for
+computing the minimum spanning tree, which is crucial in scenarios like
+network routing. Consequently, Union-Find is widely referenced. Additionally,
+Union-Find has applications in symbolic computation, register allocation,
+and more.
+
+Space Complexity: O(n), where n is the number of nodes.
+
+Time Complexity: Using path compression can reduce the time complexity of
+the find operation, and using union by rank can reduce the time complexity
+of the union operation. These optimizations reduce the average time
+complexity of each find and union operation to O(α(n)), where α(n) is the
+inverse Ackermann function. This can be roughly considered a constant time
+complexity for practical purposes.
+
+This document covers use of the Linux union-find implementation. For more
+information on the nature and implementation of Union-Find, see:
+
+ Wikipedia entry on union-find
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+Linux implementation of union-find
+-----------------------------------
+
+Linux's union-find implementation resides in the file "lib/union_find.c".
+To use it, "#include <linux/union_find.h>".
+
+The Union-Find data structure is defined as follows::
+
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+
+In this structure, parent points to the parent node of the current node.
+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]);
diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Documentation/translations/zh_CN/core-api/union_find.rst
new file mode 100644
index 0000000000..071818e7db
--- /dev/null
+++ b/Documentation/translations/zh_CN/core-api/union_find.rst
@@ -0,0 +1,87 @@
+.. SPDX-License-Identifier: GPL-2.0
+.. include:: ../disclaimer-zh_CN.rst
+
+:Original: Documentation/core-api/union_find.rst
+
+===========================
+Linux中的并查集（Union-Find）
+===========================
+
+
+:日期: 2024年6月21日
+:作者: Xavier <xavier_qy@163.com>
+
+何为并查集，它有什么用？
+---------------------
+
+并查集是一种数据结构，用于处理一些不交集的合并及查询问题。并查集支持的主要操作：
+ 初始化：将每个元素初始化为单独的集合，每个集合的初始父节点指向自身
+ 查询：查询某个元素属于哪个集合，通常是返回集合中的一个“代表元素”。这个操作是为
+ 了判断两个元素是否在同一个集合之中。
+ 合并：将两个集合合并为一个。
+
+并查集作为一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和
+图论等相关问题，同时也是用于计算最小生成树的克鲁斯克尔算法中的关键，由于最小生成树在
+网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分
+配等方面也有应用。
+
+空间复杂度: O(n)，n为节点数。
+
+时间复杂度：使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的
+时间复杂度，使得并查集每个查询和合并操作的平均时间复杂度仅为O(α(n))，其中α(n)是反阿
+克曼函数，可以粗略地认为并查集的操作有常数的时间复杂度。
+
+本文档涵盖了对Linux并查集实现的使用方法。更多关于并查集的性质和实现的信息，参见：
+
+ 维基百科并查集词条
+ https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+
+并查集的Linux实现
+----------------
+
+Linux的并查集实现在文件“lib/union_find.c”中。要使用它，需要
+“#include <linux/union_find.h>”。
+
+并查集的数据结构定义如下::
+ struct uf_node {
+ struct uf_node *parent;
+ unsigned int rank;
+ };
+其中parent为当前节点的父节点，为了提高效率，初始化时为空，并在第一次查找时指向自身，
+rank为当前树的高度，在合并时将rank小的节点接到rank大的节点下面以增加平衡性。
+
+创建并查集
+---------
+
+创建并查集时只需要传入并查集的节点个数即可，无需额外初始化，返回节点数组指针。
+示例::
+ struct uf_node *my_node = uf_nodes_alloc(num);
+
+销毁并查集
+---------
+
+销毁并查集时，只需传入创建时返回的节点数组指针即可。
+示例::
+ uf_nodes_free(my_node);
+
+查找并查集的根节点
+----------------
+
+主要用于判断两个并查集是否属于一个集合，如果根相同，那么他们就是一个集合。在查找过程中
+会对路径进行压缩，提高后续查找效率。
+示例::
+ int connected;
+ struct uf_node *root1 = uf_find(&my_node[0]);
+ struct uf_node *root2 = uf_find(&my_node[1]);
+ if (root1 == root2)
+ connected = 1;
+ else
+ connected = 0;
+
+合并两个并查集
+-------------
+
+对于两个相交的并查集进行合并，会首先查找它们各自的根节点，然后根据根节点秩大小，将小的
+节点连接到大的节点下面。
+示例::
+ uf_union(&my_node[0], &my_node[1]);
diff --git a/MAINTAINERS b/MAINTAINERS
index d6c90161c7..a1a467c591 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -23054,6 +23054,15 @@ F: drivers/cdrom/cdrom.c
F: include/linux/cdrom.h
F: include/uapi/linux/cdrom.h
+UNION-FIND
+M: Xavier <xavier_qy@163.com>
+L: linux-kernel@vger.kernel.org
+S: Maintained
+F: Documentation/core-api/union_find.rst
+F: Documentation/translations/zh_CN/core-api/union_find.rst
+F: include/linux/union_find.h
+F: lib/union_find.c
+
UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
R: Alim Akhtar <alim.akhtar@samsung.com>
R: Avri Altman <avri.altman@wdc.com>
diff --git a/include/linux/union_find.h b/include/linux/union_find.h
new file mode 100644
index 0000000000..ca806f1531
--- /dev/null
+++ b/include/linux/union_find.h
@@ -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*/
diff --git a/lib/Makefile b/lib/Makefile
index 3b17690456..e1769e6f03 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
nmi_backtrace.o win_minmax.o memcat_p.o \
- buildid.o objpool.o
+ buildid.o objpool.o union_find.o
lib-$(CONFIG_PRINTK) += dump_stack.o
lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/union_find.c b/lib/union_find.c
new file mode 100644
index 0000000000..2f77bae1ca
--- /dev/null
+++ b/lib/union_find.c
@@ -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++;
+ }
+ }
+}
--
2.45.2
The process of constructing scheduling domains
involves multiple loops and repeated evaluations, leading to numerous
redundant and ineffective assessments that impact code efficiency.
Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.
Signed-off-by: Xavier <xavier_qy@163.com>
---
kernel/cgroup/cpuset.c | 97 +++++++++++++++++-------------------------
1 file changed, 38 insertions(+), 59 deletions(-)
diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index fe76045aa5..98e9df57c4 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -45,6 +45,7 @@
#include <linux/cgroup.h>
#include <linux/wait.h>
#include <linux/workqueue.h>
+#include <linux/union_find.h>
DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
@@ -172,9 +173,6 @@ struct cpuset {
*/
int attach_in_progress;
- /* partition number for rebuild_sched_domains() */
- int pn;
-
/* for custom sched domain */
int relax_domain_level;
@@ -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);
/*
--
2.45.2The process of constructing scheduling domains
involves multiple loops and repeated evaluations, leading to numerous
redundant and ineffective assessments that impact code efficiency.
Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.
Signed-off-by: Xavier <xavier_qy@163.com>
---
kernel/cgroup/cpuset.c | 95 +++++++++++++++---------------------------
1 file changed, 34 insertions(+), 61 deletions(-)
diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index fe76045aa5..7e527530f8 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -45,6 +45,7 @@
#include <linux/cgroup.h>
#include <linux/wait.h>
#include <linux/workqueue.h>
+#include <linux/union_find.h>
DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
@@ -172,9 +173,6 @@ struct cpuset {
*/
int attach_in_progress;
- /* partition number for rebuild_sched_domains() */
- int pn;
-
/* for custom sched domain */
int relax_domain_level;
@@ -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);
--
2.45.2The process of constructing scheduling domains
involves multiple loops and repeated evaluations, leading to numerous
redundant and ineffective assessments that impact code efficiency.
Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.
Signed-off-by: Xavier <xavier_qy@163.com>
---
kernel/cgroup/cpuset.c | 95 +++++++++++++++---------------------------
1 file changed, 34 insertions(+), 61 deletions(-)
diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index fe76045aa5..7e527530f8 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -45,6 +45,7 @@
#include <linux/cgroup.h>
#include <linux/wait.h>
#include <linux/workqueue.h>
+#include <linux/union_find.h>
DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key);
DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key);
@@ -172,9 +173,6 @@ struct cpuset {
*/
int attach_in_progress;
- /* partition number for rebuild_sched_domains() */
- int pn;
-
/* for custom sched domain */
int relax_domain_level;
@@ -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);
--
2.45.2Hello.
On Mon, Jun 03, 2024 at 08:31:01PM GMT, Xavier <ghostxavier@sina.com> wrote:
> The process of constructing scheduling domains involves multiple loops
> and repeated evaluations, leading to numerous redundant and ineffective
> assessments that impact code efficiency.
>
> Here, we use Union-Find to optimize the merging of cpumasks. By employing
> path compression and union by rank, we effectively reduce the number of
> lookups and merge comparisons.
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.
> +/*define a union find node struct*/
> +struct uf_node {
> + int parent;
I think this would be better as `struct uf_node *`.
> + int rank;
> +};
`unsigned int` if rank cannot be negative?
> + /* 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
On 6/3/24 08:31, Xavier wrote: > The process of constructing scheduling domains involves multiple loops > and repeated evaluations, leading to numerous redundant and ineffective > assessments that impact code efficiency. > > Here, we use Union-Find to optimize the merging of cpumasks. By employing > path compression and union by rank, we effectively reduce the number of > lookups and merge comparisons. > > Signed-off-by: Xavier <ghostxavier@sina.com> > > 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. 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. > > 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
© 2016 - 2025 Red Hat, Inc.