From nobody Fri Feb 13 03:07:11 2026 Received: from r3-19.sinamail.sina.com.cn (r3-19.sinamail.sina.com.cn [202.108.3.19]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 1C4A4126F2A for ; Mon, 3 Jun 2024 12:31:44 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=202.108.3.19 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717417910; cv=none; b=Oha+iFdf/euvQTjrDT0cmiSeeEjyn3enJdiXxkBvqq0lOCCXeo/O4Q0Z7vVmWaanoGEE//3Pvgv81gNbTCC0GZhamT4RNGNhyAE4OAT3WSM/GuBR8FzK8BECogu+dq/xTldmv5qDJa1bPvy/cXV4JBBJw9X/f+We+1T+NfYRM60= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717417910; c=relaxed/simple; bh=F0Jf8OiTTvwdi30OQ3QHk+13cYz4+woNcq0c6+ItnoY=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=mRsxsf6m//jD1E7oVJ8VGpuLdeqd5mHFigovaCv4P+Rhws7+jwvcAs1moUI5Qq/oUeUWteXH01LqiaAKyeePDs7qhqxEsJ8s9OM+fGMqXAXVLpgwmLcOC5kfmDvTsz32GKO347z362yUPA2/Y9u4iZxGdW8UjkK3QE8cTD9nmHg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=sina.com; spf=pass smtp.mailfrom=sina.com; arc=none smtp.client-ip=202.108.3.19 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=sina.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=sina.com X-SMAIL-HELO: localhost Received: from unknown (HELO localhost)([101.132.132.191]) by sina.com (10.182.253.24) with ESMTP id 665DB788000035BE; Mon, 3 Jun 2024 20:31:05 +0800 (CST) X-Sender: ghostxavier@sina.com X-Auth-ID: ghostxavier@sina.com Authentication-Results: sina.com; spf=none smtp.mailfrom=ghostxavier@sina.com; dkim=none header.i=none; dmarc=none action=none header.from=ghostxavier@sina.com X-SMAIL-MID: 4516241049099 X-SMAIL-UIID: 12FB1F5EF9944B87A4329F8B41F467E7-20240603-203105-1 From: Xavier To: longman@redhat.com Cc: lizefan.x@bytedance.com, tj@kernel.org, hannes@cmpxchg.org, cgroups@vger.kernel.org, linux-kernel@vger.kernel.org, Xavier Subject: [PATCH v3] cpuset: use Union-Find to optimize the merging of cpumasks Date: Mon, 3 Jun 2024 20:31:01 +0800 Message-Id: <20240603123101.590760-1-ghostxavier@sina.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240531024837.255293-1-ghostxavier@sina.com> References: <20240531024837.255293-1-ghostxavier@sina.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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 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.=20 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 fixin= g 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 scena= rios locally to test, so the testing scope is limited. Thank you for provid= ing the test cases. I have reproduced and resolved the issue, and have pass= ed several other test cases in CGroup. But currently, I only have QEMU simu= lation environment, so my testing ability is limited. I hope you can help m= e with some comprehensive testing of my new version patch. Thank you very m= uch. 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; } =20 +/*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 =3D x; + int parent; + + /*Find the root node and perform path compression at the same time*/ + while (nodes[root].parent !=3D root) { + parent =3D nodes[root].parent; + nodes[root].parent =3D nodes[parent].parent; + root =3D 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 =3D find_root(nodes, a); + int root_b =3D find_root(nodes, b); + + if (root_a !=3D root_b) { + if (nodes[root_a].rank < nodes[root_b].rank) { + nodes[root_a].parent =3D root_b; + } else if (nodes[root_a].rank > nodes[root_b].rank) { + nodes[root_b].parent =3D root_a; + } else { + nodes[root_b].parent =3D 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 **dom= ains, 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 =3D 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 =3D is_sched_load_balance(&top_cpuset); + struct uf_node *nodes; + int nslot_update; =20 doms =3D NULL; dattr =3D NULL; @@ -1022,40 +1058,38 @@ static int generate_sched_domains(cpumask_var_t **d= omains, } rcu_read_unlock(); =20 - for (i =3D 0; i < csn; i++) - csa[i]->pn =3D i; - ndoms =3D csn; - -restart: - /* Find the best partition (set of sched domains) */ - for (i =3D 0; i < csn; i++) { - struct cpuset *a =3D csa[i]; - int apn =3D a->pn; + nodes =3D kmalloc_array(csn, sizeof(struct uf_node), GFP_KERNEL); + if (!nodes) + goto done; =20 - for (j =3D 0; j < csn; j++) { - struct cpuset *b =3D csa[j]; - int bpn =3D b->pn; =20 - if (apn !=3D bpn && cpusets_overlap(a, b)) { - for (k =3D 0; k < csn; k++) { - struct cpuset *c =3D csa[k]; + /* Each node is initially its own parent */ + for (i =3D 0; i < csn; i++) { + nodes[i].parent =3D i; + nodes[i].rank =3D 0; + } =20 - if (c->pn =3D=3D bpn) - c->pn =3D apn; - } - ndoms--; /* one less element */ - goto restart; - } + /* Merge overlapping cpusets */ + for (i =3D 0; i < csn; i++) { + for (j =3D i + 1; j < csn; j++) { + if (cpusets_overlap(csa[i], csa[j])) + union_sets(nodes, i, j); } } =20 + /* Calculate the number of domains after merging */ + for (i =3D 0; i < csn; i++) { + if (nodes[i].parent =3D=3D i) + ndoms++; + } + /* * Now we know how many domains to create. * Convert to and populate cpu masks. */ doms =3D alloc_sched_domains(ndoms); if (!doms) - goto done; + goto free; =20 /* * The rest of the code, including the scheduler, can deal with @@ -1065,47 +1099,29 @@ static int generate_sched_domains(cpumask_var_t **d= omains, GFP_KERNEL); =20 for (nslot =3D 0, i =3D 0; i < csn; i++) { - struct cpuset *a =3D csa[i]; - struct cpumask *dp; - int apn =3D a->pn; - - if (apn < 0) { - /* Skip completed partitions */ - continue; - } - - dp =3D doms[nslot]; - - if (nslot =3D=3D ndoms) { - static int warnings =3D 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) =3D SD_ATTR_INIT; + nslot_update =3D 0; for (j =3D i; j < csn; j++) { - struct cpuset *b =3D csa[j]; - - if (apn =3D=3D b->pn) { - cpumask_or(dp, dp, b->effective_cpus); + if (find_root(nodes, j) =3D=3D i) { + struct cpumask *dp =3D doms[nslot]; + + if (i =3D=3D j) { + nslot_update =3D 1; + cpumask_clear(dp); + if (dattr) + *(dattr + nslot) =3D 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 =3D -1; + update_domain_attr_tree(dattr + nslot, csa[j]); } } - nslot++; + if (nslot_update) + nslot++; } BUG_ON(nslot !=3D ndoms); - +free: + kfree(nodes); done: kfree(csa); =20 --=20 2.34.1