From nobody Thu Dec 18 05:08:56 2025 Received: from m15.mail.163.com (m15.mail.163.com [45.254.50.220]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 0AC453BB50; Thu, 20 Jun 2024 08:55:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=45.254.50.220 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1718873710; cv=none; b=mfXaDD3deuzvwC7SjjXiL3hO5opBd76Bpwna4H82wY5pvuFNTRPROIjuiXC9dN5HaxGy9B5iRW3gzR+e3m6Z5wkn1aNW5G/ih8207MvgaDnMuKgtIcSoH7bqhjBzE8FEtt9W1hxQ3zUSSldc77QSl996aqo5X9BeUHpWb+O2Aw4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1718873710; c=relaxed/simple; bh=jHWt+oS0pQA+C3uyXiXZ+VQ20jbeR+O/U+jRyfrwnbM=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=p3zmlRAZyfxshK8ehpQFNBgPkMPjob0PSZYiwnkpbGxxHX+FG4I7GtU6ikPEUv28/MkBMJkfjAQpaEXvJx1JwK8pDgzu81nqvRUObAFCpvNfYQD8mkpF0Dltz6nUBQXxvo06TcO1TIWwk+tDH5Ba5RFCxAS4hAbZxsKjK8yBaYo= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=163.com; spf=pass smtp.mailfrom=163.com; dkim=pass (1024-bit key) header.d=163.com header.i=@163.com header.b=EVQqJgvM; arc=none smtp.client-ip=45.254.50.220 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=163.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=163.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=163.com header.i=@163.com header.b="EVQqJgvM" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=163.com; s=s110527; h=From:Subject:Date:Message-Id:MIME-Version; bh=P+H56 2k2vggjvg30NvL8+mRhFD6CP57Wnu7B+p9noDY=; b=EVQqJgvM9XACxbAJMl/nN Hy/AdSnGvjwIU0FL9ioSHHjT0l1CF4GJpBWGJg+nXUk74XIT2Qi42UyMCZAJDLkN nsQJr+hFCj7en5ac+BlfwYrgqw+8XPO33iTqVQVv9vePqx1uijrH6d6Tm72S6YQw Y6iGSqAXJT52SORmoZxeeU= Received: from localhost (unknown [101.132.132.191]) by gzga-smtp-mta-g0-1 (Coremail) with SMTP id _____wDnLzzU7XNmxZGiDw--.17631S2; Thu, 20 Jun 2024 16:52:36 +0800 (CST) From: Xavier To: longman@redhat.com, mkoutny@suse.com Cc: lizefan.x@bytedance.com, tj@kernel.org, hannes@cmpxchg.org, cgroups@vger.kernel.org, linux-kernel@vger.kernel.org, Xavier Subject: [PATCH v4 v4 1/2] Union-Find: add a new module in kernel library Date: Thu, 20 Jun 2024 16:52:32 +0800 Message-Id: <20240620085233.205690-2-xavier_qy@163.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240620085233.205690-1-xavier_qy@163.com> References: <20240603123101.590760-1-ghostxavier@sina.com> <20240620085233.205690-1-xavier_qy@163.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 X-CM-TRANSID: _____wDnLzzU7XNmxZGiDw--.17631S2 X-Coremail-Antispam: 1Uf129KBjvJXoWxJF4UZFWDtr48Gry7tr1xGrg_yoW5KF48pF 45GryfCrs7Jry7Cr9akFWFyw4Sva1rGrWUuFWxGw4rArn5tr10qF1qvryFyrn3Jr4xCFW7 XF4agr13CrWUJ3DanT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDUYxBIdaVFxhVjvjDU0xZFpf9x07U7kucUUUUU= X-CM-SenderInfo: 50dyxvpubt5qqrwthudrp/1tbiZRYEEGXAmg963AAAsx Content-Type: text/plain; charset="utf-8" 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 --- 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 =20 +UNION-FIND +M: Xavier +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 R: Avri Altman 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 + +/* 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 :=3D 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 =20 lib-$(CONFIG_PRINTK) +=3D dump_stack.o lib-$(CONFIG_SMP) +=3D 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 + +struct uf_node *uf_find(struct uf_node *node) +{ + struct uf_node *parent; + + if (!node->parent) { + node->parent =3D node; + return node; + } + + /*Find the root node and perform path compression at the same time*/ + while (node->parent !=3D node) { + parent =3D node->parent; + node->parent =3D parent->parent; + node =3D 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 =3D uf_find(node1); + struct uf_node *root2 =3D uf_find(node2); + + if (root1 !=3D root2) { + if (root1->rank < root2->rank) { + root1->parent =3D root2; + } else if (root1->rank > root2->rank) { + root2->parent =3D root1; + } else { + root2->parent =3D root1; + root1->rank++; + } + } +} --=20 2.45.2 From nobody Thu Dec 18 05:08:56 2025 Received: from m15.mail.163.com (m15.mail.163.com [45.254.50.220]) by smtp.subspace.kernel.org (Postfix) with ESMTP id F282C2D05D; Thu, 20 Jun 2024 08:55:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=45.254.50.220 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1718873711; cv=none; b=hHb3gnO8ky92uN3dIJLGYaytf0G/6wyC0EzIef88UoyUtbsYQ0c3uazFABvcQGP83k4yidlm7b1uDyV72WXXCfSsfplOa7Iv8suCcFkdwWs0wjk86BPz2sqVENRRj8e0KQTLn3qBZ7Wbby0m3LvknjKGwQTwAKnlLDYgNZcHYqU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1718873711; c=relaxed/simple; bh=Zte5JUNqWfYMzsUShAtYW3hHHTnmNIinQoLo7kExpMU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=GtG8cK/C837sqeZR9DdBToo5bUxPY0cjCoEksrJQHobg3k0/KSElqTibHDw6deFgkFBsCpwSqVhOu85WJIySs4KeHfdrf/6933qPlYTQKfWFV/Kb56xUpVktEOxr+46FpNuNJuWD0JlS2kffBXODINI/Vq/KHRUQ7nqh/MSCiiE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=163.com; spf=pass smtp.mailfrom=163.com; dkim=pass (1024-bit key) header.d=163.com header.i=@163.com header.b=BZf2uBSZ; arc=none smtp.client-ip=45.254.50.220 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=163.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=163.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=163.com header.i=@163.com header.b="BZf2uBSZ" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=163.com; s=s110527; h=From:Subject:Date:Message-Id:MIME-Version; bh=f4H86 bcCOfTgkY5Xt2BTUJ/8giKcEdQStQuqAfO5dp8=; b=BZf2uBSZXrBHtEgFYvLkO nVgboCNiFOQHEnRh0IDaI9uvdRMjLNQRHr8wVn0h5+NMF24f7KjCdhpH9rrf/AnX 1tqNoUnjJhEphMmmFo5UUhejiLXjck4cBmhG65OLhIU0cXTLnqFs4nRoKi7uaUUE c0+AOWFqk9kJPXT6Hy66Rg= Received: from localhost (unknown [101.132.132.191]) by gzga-smtp-mta-g0-4 (Coremail) with SMTP id _____wDn5JjV7XNmrecAJA--.9351S2; Thu, 20 Jun 2024 16:52:38 +0800 (CST) From: Xavier To: longman@redhat.com, mkoutny@suse.com Cc: lizefan.x@bytedance.com, tj@kernel.org, hannes@cmpxchg.org, cgroups@vger.kernel.org, linux-kernel@vger.kernel.org, Xavier Subject: [PATCH v4 v4 2/2] cpuset: use Union-Find to optimize the merging of cpumasks Date: Thu, 20 Jun 2024 16:52:33 +0800 Message-Id: <20240620085233.205690-3-xavier_qy@163.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240620085233.205690-1-xavier_qy@163.com> References: <20240603123101.590760-1-ghostxavier@sina.com> <20240620085233.205690-1-xavier_qy@163.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 X-CM-TRANSID: _____wDn5JjV7XNmrecAJA--.9351S2 X-Coremail-Antispam: 1Uf129KBjvJXoWxAFWfur4kKFyUZFWUJrW3Awb_yoWrurW5pF s3Cay2qrWrJryUGwsYk3y8Z34SkaykJa1Utw13Gw1fArnrA3Z29a40qFs5KayUuFyDCr1U uF9xKr47Wr1UKFDanT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDUYxBIdaVFxhVjvjDU0xZFpf9x07UadgZUUUUU= X-CM-SenderInfo: 50dyxvpubt5qqrwthudrp/1tbiZRYEEGXAmg963wABsz 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 --- 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 #include #include +#include =20 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; =20 - /* partition number for rebuild_sched_domains() */ - int pn; - /* for custom sched domain */ int relax_domain_level; =20 @@ -1007,7 +1005,7 @@ 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 */ @@ -1015,6 +1013,8 @@ static int generate_sched_domains(cpumask_var_t **dom= ains, struct cgroup_subsys_state *pos_css; bool root_load_balance =3D is_sched_load_balance(&top_cpuset); bool cgrpv2 =3D cgroup_subsys_on_dfl(cpuset_cgrp_subsys); + struct uf_node *nodes; + int nslot_update; =20 doms =3D NULL; dattr =3D NULL; @@ -1102,40 +1102,31 @@ static int generate_sched_domains(cpumask_var_t **d= omains, if (root_load_balance && (csn =3D=3D 1)) goto single_root_domain; =20 - for (i =3D 0; i < csn; i++) - csa[i]->pn =3D i; - ndoms =3D csn; + nodes =3D uf_nodes_alloc(csn); + if (!nodes) + goto done; =20 -restart: - /* Find the best partition (set of sched domains) */ + /* Merge overlapping cpusets */ for (i =3D 0; i < csn; i++) { - struct cpuset *a =3D csa[i]; - int apn =3D a->pn; - - for (j =3D 0; j < csn; j++) { - struct cpuset *b =3D csa[j]; - int bpn =3D b->pn; - - if (apn !=3D bpn && cpusets_overlap(a, b)) { - for (k =3D 0; k < csn; k++) { - struct cpuset *c =3D csa[k]; - - if (c->pn =3D=3D bpn) - c->pn =3D apn; - } - ndoms--; /* one less element */ - goto restart; - } + for (j =3D i + 1; j < csn; j++) { + if (cpusets_overlap(csa[i], csa[j])) + uf_union(&nodes[i], &nodes[j]); } } =20 + /* Count the total number of domains */ + for (i =3D 0; i < csn; i++) { + if ((nodes[i].parent =3D=3D &nodes[i]) || !nodes[i].parent) + 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 @@ -1159,47 +1150,29 @@ static int generate_sched_domains(cpumask_var_t **d= omains, } =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 (uf_find(&nodes[j]) =3D=3D &nodes[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: + uf_nodes_free(nodes); done: kfree(csa); =20 --=20 2.45.2