Skip to contentSkip to conversation

lib/group_cpus: make group CPU cluster aware

PATCH Applied Wangyang Guo 3 participants 5 messages Jan 13 – Aug 5

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

PATCH v2 1/1 lib/group_cpus: make group CPU cluster aware

As CPU core counts increase, the number of NVMe IRQs may be smaller than the total number of CPUs. This forces multiple CPUs to share the same IRQ. If the IRQ affinity and the CPU’s cluster do not align, a performance penalty can be observed on some platforms.

This patch improves IRQ affinity by grouping CPUs by cluster within each NUMA domain, ensuring better locality between CPUs and their assigned NVMe IRQs.

Details:

Intel Xeon E platform packs 4 CPU cores as 1 module (cluster) and share the L2 cache. Let's say, if there are 40 CPUs in 1 NUMA domain and 11 IRQs to dispatch. The existing algorithm will map first 7 IRQs each with 4 CPUs and remained 4 IRQs each with 3 CPUs. The last 4 IRQs may have cross cluster issue. For example, the 9th IRQ which pinned to CPU32, then for CPU31, it will have cross L2 memory access.

CPU |28 29 30 31|32 33 34 35|36 ...

     -------- -------- --------

IRQ 8 9 10

If this patch applied, then first 2 IRQs each mapped with 2 CPUs and rest 9 IRQs each mapped with 4 CPUs, which avoids the cross cluster memory access.

CPU |00 01 02 03|04 05 06 07|08 09 10 11| ...

     ----- ----- ----------- -----------

IRQ 1 2 3 4

As a result, 15%+ performance difference is observed in FIO libaio/randread/bs=8k.

Changes since V1:
- Add more performance details in commit messages.
- Fix endless loop when topology_cluster_cpumask return invalid mask.

History:
v1: https://lore.kernel.org/all/[email protected]/
v1 [RESEND]: https://lore.kernel.org/all/[email protected]/

---
 lib/group_cpus.c | 271 +++++++++++++++++++++++++++++++++++------------
 1 file changed, 206 insertions(+), 65 deletions(-)
lib/group_cpus.c +206 -65
index 6d08ac05f371..a93df70919df 100644
@@ -114,48 +114,15 @@ static int ncpus_cmp_func(const void *l, const void *r)
 	return ln->ncpus - rn->ncpus;
 }
 
-/*
- * Allocate group number for each node, so that for each node:
- *
- * 1) the allocated number is >= 1
- *
- * 2) the allocated number is <= active CPU number of this node
- *
- * The actual allocated total groups may be less than @numgrps when
- * active total CPU number is less than @numgrps.
- *
- * Active CPUs means the CPUs in '@cpu_mask AND @node_to_cpumask[]'
- * for each node.
- */
-static void alloc_nodes_groups(unsigned int numgrps,
-			       cpumask_var_t *node_to_cpumask,
-			       const struct cpumask *cpu_mask,
-			       const nodemask_t nodemsk,
-			       struct cpumask *nmsk,
-			       struct node_groups *node_groups)
+static void alloc_groups_to_nodes(unsigned int numgrps,
+				  unsigned int numcpus,
+				  struct node_groups *node_groups,
+				  unsigned int num_nodes)
 {
-	unsigned n, remaining_ncpus = 0;
-
-	for (n = 0; n < nr_node_ids; n++) {
-		node_groups[n].id = n;
-		node_groups[n].ncpus = UINT_MAX;
-	}
-
-	for_each_node_mask(n, nodemsk) {
-		unsigned ncpus;
-
-		cpumask_and(nmsk, cpu_mask, node_to_cpumask[n]);
-		ncpus = cpumask_weight(nmsk);
-
-		if (!ncpus)
-			continue;
-		remaining_ncpus += ncpus;
-		node_groups[n].ncpus = ncpus;
-	}
+	unsigned int n, remaining_ncpus = numcpus;
+	unsigned int  ngroups, ncpus;
 
-	numgrps = min_t(unsigned, remaining_ncpus, numgrps);
-
-	sort(node_groups, nr_node_ids, sizeof(node_groups[0]),
+	sort(node_groups, num_nodes, sizeof(node_groups[0]),
 	     ncpus_cmp_func, NULL);
 
 	/*
@@ -226,9 +193,8 @@ static void alloc_nodes_groups(unsigned int numgrps,
 	 * finally for each node X: grps(X) <= ncpu(X).
 	 *
 	 */
-	for (n = 0; n < nr_node_ids; n++) {
-		unsigned ngroups, ncpus;
 
+	for (n = 0; n < num_nodes; n++) {
 		if (node_groups[n].ncpus == UINT_MAX)
 			continue;
 
@@ -246,12 +212,201 @@ static void alloc_nodes_groups(unsigned int numgrps,
 	}
 }
 
+/*
+ * Allocate group number for each node, so that for each node:
+ *
+ * 1) the allocated number is >= 1
+ *
+ * 2) the allocated number is <= active CPU number of this node
+ *
+ * The actual allocated total groups may be less than @numgrps when
+ * active total CPU number is less than @numgrps.
+ *
+ * Active CPUs means the CPUs in '@cpu_mask AND @node_to_cpumask[]'
+ * for each node.
+ */
+static void alloc_nodes_groups(unsigned int numgrps,
+			       cpumask_var_t *node_to_cpumask,
+			       const struct cpumask *cpu_mask,
+			       const nodemask_t nodemsk,
+			       struct cpumask *nmsk,
+			       struct node_groups *node_groups)
+{
+	unsigned int n, numcpus = 0;
+
+	for (n = 0; n < nr_node_ids; n++) {
+		node_groups[n].id = n;
+		node_groups[n].ncpus = UINT_MAX;
+	}
+
+	for_each_node_mask(n, nodemsk) {
+		unsigned int ncpus;
+
+		cpumask_and(nmsk, cpu_mask, node_to_cpumask[n]);
+		ncpus = cpumask_weight(nmsk);
+
+		if (!ncpus)
+			continue;
+		numcpus += ncpus;
+		node_groups[n].ncpus = ncpus;
+	}
+
+	numgrps = min_t(unsigned int, numcpus, numgrps);
+	alloc_groups_to_nodes(numgrps, numcpus, node_groups, nr_node_ids);
+}
+
+static void assign_cpus_to_groups(unsigned int ncpus,
+				  struct cpumask *nmsk,
+				  struct node_groups *nv,
+				  struct cpumask *masks,
+				  unsigned int *curgrp,
+				  unsigned int last_grp)
+{
+	unsigned int v, cpus_per_grp, extra_grps;
+	/* Account for rounding errors */
+	extra_grps = ncpus - nv->ngroups * (ncpus / nv->ngroups);
+
+	/* Spread allocated groups on CPUs of the current node */
+	for (v = 0; v < nv->ngroups; v++, *curgrp += 1) {
+		cpus_per_grp = ncpus / nv->ngroups;
+
+		/* Account for extra groups to compensate rounding errors */
+		if (extra_grps) {
+			cpus_per_grp++;
+			--extra_grps;
+		}
+
+		/*
+		 * wrapping has to be considered given 'startgrp'
+		 * may start anywhere
+		 */
+		if (*curgrp >= last_grp)
+			*curgrp = 0;
+		grp_spread_init_one(&masks[*curgrp], nmsk, cpus_per_grp);
+	}
+}
+
+static int alloc_cluster_groups(unsigned int ncpus,
+				unsigned int ngroups,
+				struct cpumask *node_cpumask,
+				cpumask_var_t msk,
+				const struct cpumask ***clusters_ptr,
+				struct node_groups **cluster_groups_ptr)
+{
+	unsigned int ncluster = 0;
+	unsigned int cpu, nc, n;
+	const struct cpumask *cluster_mask;
+	const struct cpumask **clusters;
+	struct node_groups *cluster_groups;
+
+	cpumask_copy(msk, node_cpumask);
+
+	/* Probe how many clusters in this node. */
+	while (1) {
+		cpu = cpumask_first(msk);
+		if (cpu >= nr_cpu_ids)
+			break;
+
+		cluster_mask = topology_cluster_cpumask(cpu);
+		if (!cpumask_weight(cluster_mask))
+			goto no_cluster;
+		/* Clean out CPUs on the same cluster. */
+		cpumask_andnot(msk, msk, cluster_mask);
+		ncluster++;
+	}
+
+	/* If ngroups < ncluster, cross cluster is inevitable, skip. */
+	if (ncluster == 0 || ncluster > ngroups)
+		goto no_cluster;
+
+	/* Allocate memory based on cluster number. */
+	clusters = kcalloc(ncluster, sizeof(struct cpumask *), GFP_KERNEL);
+	if (!clusters)
+		goto no_cluster;
+	cluster_groups = kcalloc(ncluster, sizeof(struct node_groups), GFP_KERNEL);
+	if (!cluster_groups)
+		goto fail_cluster_groups;
+
+	/* Filling cluster info for later process. */
+	cpumask_copy(msk, node_cpumask);
+	for (n = 0; n < ncluster; n++) {
+		cpu = cpumask_first(msk);
+		cluster_mask = topology_cluster_cpumask(cpu);
+		nc = cpumask_weight_and(cluster_mask, node_cpumask);
+		clusters[n] = cluster_mask;
+		cluster_groups[n].id = n;
+		cluster_groups[n].ncpus = nc;
+		cpumask_andnot(msk, msk, cluster_mask);
+	}
+
+	alloc_groups_to_nodes(ngroups, ncpus, cluster_groups, ncluster);
+
+	*clusters_ptr = clusters;
+	*cluster_groups_ptr = cluster_groups;
+	return ncluster;
+
+ fail_cluster_groups:
+	kfree(clusters);
+ no_cluster:
+	return 0;
+}
+
+/*
+ * Try group CPUs evenly for cluster locality within a NUMA node.
+ *
+ * Return: true if success, false otherwise.
+ */
+static bool __try_group_cluster_cpus(unsigned int ncpus,
+				     unsigned int ngroups,
+				     struct cpumask *node_cpumask,
+				     struct cpumask *masks,
+				     unsigned int *curgrp,
+				     unsigned int last_grp)
+{
+	struct node_groups *cluster_groups;
+	const struct cpumask **clusters;
+	unsigned int ncluster;
+	bool ret = false;
+	cpumask_var_t nmsk;
+	unsigned int i, nc;
+
+	if (!zalloc_cpumask_var(&nmsk, GFP_KERNEL))
+		goto fail_nmsk_alloc;
+
+	ncluster = alloc_cluster_groups(ncpus, ngroups, node_cpumask, nmsk,
+					&clusters, &cluster_groups);
+
+	if (ncluster == 0)
+		goto fail_no_clusters;
+
+	for (i = 0; i < ncluster; i++) {
+		struct node_groups *nv = &cluster_groups[i];
+
+		/* Get the cpus on this cluster. */
+		cpumask_and(nmsk, node_cpumask, clusters[nv->id]);
+		nc = cpumask_weight(nmsk);
+		if (!nc)
+			continue;
+		WARN_ON_ONCE(nv->ngroups > nc);
+
+		assign_cpus_to_groups(nc, nmsk, nv, masks, curgrp, last_grp);
+	}
+
+	ret = true;
+	kfree(cluster_groups);
+	kfree(clusters);
+ fail_no_clusters:
+	free_cpumask_var(nmsk);
+ fail_nmsk_alloc:
+	return ret;
+}
+
 static int __group_cpus_evenly(unsigned int startgrp, unsigned int numgrps,
 			       cpumask_var_t *node_to_cpumask,
 			       const struct cpumask *cpu_mask,
 			       struct cpumask *nmsk, struct cpumask *masks)
 {
-	unsigned int i, n, nodes, cpus_per_grp, extra_grps, done = 0;
+	unsigned int i, n, nodes, done = 0;
 	unsigned int last_grp = numgrps;
 	unsigned int curgrp = startgrp;
 	nodemask_t nodemsk = NODE_MASK_NONE;
@@ -287,7 +442,7 @@ static int __group_cpus_evenly(unsigned int startgrp, unsigned int numgrps,
 	alloc_nodes_groups(numgrps, node_to_cpumask, cpu_mask,
 			   nodemsk, nmsk, node_groups);
 	for (i = 0; i < nr_node_ids; i++) {
-		unsigned int ncpus, v;
+		unsigned int ncpus;
 		struct node_groups *nv = &node_groups[i];
 
 		if (nv->ngroups == UINT_MAX)
@@ -301,28 +456,14 @@ static int __group_cpus_evenly(unsigned int startgrp, unsigned int numgrps,
 
 		WARN_ON_ONCE(nv->ngroups > ncpus);
 
-		/* Account for rounding errors */
-		extra_grps = ncpus - nv->ngroups * (ncpus / nv->ngroups);
-
-		/* Spread allocated groups on CPUs of the current node */
-		for (v = 0; v < nv->ngroups; v++, curgrp++) {
-			cpus_per_grp = ncpus / nv->ngroups;
-
-			/* Account for extra groups to compensate rounding errors */
-			if (extra_grps) {
-				cpus_per_grp++;
-				--extra_grps;
-			}
-
-			/*
-			 * wrapping has to be considered given 'startgrp'
-			 * may start anywhere
-			 */
-			if (curgrp >= last_grp)
-				curgrp = 0;
-			grp_spread_init_one(&masks[curgrp], nmsk,
-						cpus_per_grp);
+		if (__try_group_cluster_cpus(ncpus, nv->ngroups, nmsk,
+					     masks, &curgrp, last_grp)) {
+			done += nv->ngroups;
+			continue;
 		}
+
+		assign_cpus_to_groups(ncpus, nmsk, nv, masks, &curgrp,
+				      last_grp);
 		done += nv->ngroups;
 	}
 	kfree(node_groups);
Signature · 1 line
2.47.3
#1 lore raw

For higher number of jobs(>=64), we are seeing ~8% regression with this patch.

Tool: fio with io_uring engine [1]

+------------+------------+-------------------+  
| numjobs    | before     | after patch       |  
+------------+------------+-------------------+  
| 1          | 89         | 88.8 (-0.22%)     |  
| 2          | 169        | 168 (-0.59%)      |  
| 4          | 338        | 337 (-0.30%)      |  
| 8          | 533        | 533 (0.00%)       |  
| 16         | 538        | 541 (+0.56%)      |  
| 32         | 685        | 716 (+4.53%)      |  
| 64         | 933        | 859 (-7.93%)      |  
| 128        | 941        | 867 (-7.86%)      |  
+------------+------------+-------------------+  
* Metric: IOPS (K) (Block device, QD = 1, bs = 4K, Random Read)  

As shown in the table above, while performance is comparable at low job counts, there is a drop starting from 64 jobs after this patch.

HW info:
Intel(R) Core(TM) Ultra 7 265K
CPU=20
IRQ-CPU are 1:1 mapped.

[1] fio -filename=/dev/nvme0n1 -direct=1 -size=4g -rw=randread \
-numjobs=$(numjobs) -bs=4096 -ioengine=io_uring -iodepth=1 \
-name=uring_test --registerfiles=1 --ramp_time=5 \
--group_reporting --thread

#2 lore raw
Quoted 6 lines

For higher number of jobs(>=64), we are seeing ~8% regression with this patch.

HW info:
Intel(R) Core(TM) Ultra 7 265K
CPU=20
IRQ-CPU are 1:1 mapped.

If IRQ and CPUs are 1:1 mapping (20 IRQs/20 CPUs), the patch would not change anything. Every group is exactly 1 CPU, same as before.

#3 lore raw
Quoted 8 lines · Wangyang
Quoted 6 lines

For higher number of jobs(>=64), we are seeing ~8% regression with this patch.

HW info:
Intel(R) Core(TM) Ultra 7 265K
CPU=20
IRQ-CPU are 1:1 mapped.

If IRQ and CPUs are 1:1 mapping (20 IRQs/20 CPUs), the patch would not change anything. Every group is exactly 1 CPU, same as before.

We see its not the case, before this patch, irqs smp_allowed_list was sequential, but after the patch this changes.

Hardware:
Intel(R) Core(TM) Ultra 7 265K
- 8 P-cores (each its own cluster, own L2)
- 12 E-cores (3 clusters of 4 CPUs sharing L2)
- 1 NUMA node, 20 CPUs total, 21 NVMe queues(admin+io)

Cluster topology (from cluster_cpus_list):
{0} {1} {2} {3} {4} {5} {6} {7} {8-11} {12-15} {16-19}

Before:
/proc/irq/168/smp_affinity_list:0
/proc/irq/169/smp_affinity_list:1
/proc/irq/170/smp_affinity_list:2
/proc/irq/171/smp_affinity_list:3
/proc/irq/172/smp_affinity_list:4
/proc/irq/173/smp_affinity_list:5
/proc/irq/174/smp_affinity_list:6
/proc/irq/175/smp_affinity_list:7
/proc/irq/176/smp_affinity_list:8
/proc/irq/177/smp_affinity_list:9
/proc/irq/178/smp_affinity_list:10
/proc/irq/179/smp_affinity_list:11
/proc/irq/180/smp_affinity_list:12
/proc/irq/181/smp_affinity_list:13
/proc/irq/182/smp_affinity_list:14
/proc/irq/183/smp_affinity_list:15
/proc/irq/184/smp_affinity_list:16
/proc/irq/185/smp_affinity_list:17
/proc/irq/186/smp_affinity_list:18
/proc/irq/187/smp_affinity_list:19

After patch:
/proc/irq/168/smp_affinity_list:1
/proc/irq/169/smp_affinity_list:4
/proc/irq/170/smp_affinity_list:0
/proc/irq/171/smp_affinity_list:5
/proc/irq/172/smp_affinity_list:6
/proc/irq/173/smp_affinity_list:7
/proc/irq/174/smp_affinity_list:3
/proc/irq/175/smp_affinity_list:2
/proc/irq/176/smp_affinity_list:8
/proc/irq/177/smp_affinity_list:9
/proc/irq/178/smp_affinity_list:10
/proc/irq/179/smp_affinity_list:11
/proc/irq/180/smp_affinity_list:12
/proc/irq/181/smp_affinity_list:13
/proc/irq/182/smp_affinity_list:14
/proc/irq/183/smp_affinity_list:15
/proc/irq/184/smp_affinity_list:16
/proc/irq/185/smp_affinity_list:17
/proc/irq/186/smp_affinity_list:18
/proc/irq/187/smp_affinity_list:19

I think this has to do with cache locality effects, when tasks run on "wrong" CPUs. If you want us to check perf data, we can run that.

Below patch[1] fixes the issue for us. Basically keep the cpu order if resources are equal, meanwhile keeping the benefit of your patches for clustering.

[1]

lib/group_cpus.c +0 -0
@@ -109,7 +109,11 @@ static int ncpus_cmp_func(const void *l, const void *r)
{
	const struct node_groups *ln = l;
	const struct node_groups *rn = r;

- return ln->ncpus - rn->ncpus;
+ if (ln->ncpus != rn->ncpus)
+ return ln->ncpus - rn->ncpus;
+
+ /* Tie-break by id so equal-ncpus clusters keep discovery order */
+ return ln->id - rn->id;
}

Regards,
-Nitesh

#4 lore raw
Quoted 2 lines

We see its not the case, before this patch, irqs smp_allowed_list was sequential, but after the patch this changes. I think this has to do with cache locality effects, when tasks run on "wrong" CPUs. If you want us to check perf data, we can run that.

Nice catch. However, if this is indeed a cache locality issue, I would expect the performance impact to be more consistent. The results show a 4% performance improvement at jobs=32, which seems to contradict that explanation.

Quoted 1 line

Below patch[1] fixes the issue for us. Basically keep the cpu order if resources are equal, meanwhile keeping the benefit of your patches for clustering.

Yes, this is related to stable sorting, such change can preserve the order.