[RFC PATCH] sched/topology: Avoid overlapping NUMA groups when possible

[Fengyu Wang(Hygon)]

A four-node ring illustrates overlapping NUMA sched groups:

node distances:
node   0   1   2   3
  0:  10  20  30  20
  1:  20  10  20  30
  2:  30  20  10  20
  3:  20  30  20  10

At distance 30, a CPU on node 0 sees these groups, using node IDs to
abbreviate their CPU masks:

  local:  {0,1,3}
  remote: {1,2,3}

Summing group load and capacity counts nodes 1 and 3 twice, but nodes
0 and 2 only once. Dividing by the summed capacity does not cancel this
unequal weighting, so the domain average can be biased.

With equal node capacities, the shared load on nodes 1 and 3 cancels
out of the group load difference, leaving the difference between nodes
0 and 2. However, source-rq selection can pull from nodes 1 or 3 instead
of node 2, changing placement inside the local group without directly
reducing the load on node 2.

Keep the local child span and descend overlapping remote candidates to
smaller NUMA child domains. Accept a candidate when its child is disjoint
from the CPUs already covered, without descending into node-internal
levels. Here, the groups become {0,1,3} and {2}, so each CPU contributes
once and the remote source group excludes shared CPUs.

Preserve valid, non-overlapping candidates and the existing out-of-domain
fixup. Retain the original grouping where shrinking would lose coverage
or no disjoint candidate can be found within NUMA levels.

Tested by building an x86_64 kernel and booting it under QEMU/KVM
with NUMA nodes and distance tables supplied through -numa node and
-numa dist. Parse the sched_verbose boot output to check that group
masks cover each domain without overlap, and compare domain spans and
local groups against the unpatched kernel.

The six symmetric fixtures cover a 12-node topology and an 8-node
EPYC-style topology, each with one CPU per node and two interleaved
CPUs per node, plus a four-node ring and an unequal-depth topology.
All 350 domains pass; EPYC group masks are unchanged. A seventh boot
with an asymmetric SLIT verifies complete coverage and preservation of
the baseline groups for CPUs 0 and 2.

A userspace harness compiles the extracted topology C functions with
UBSan and exercises malformed cross-node SMT, checking that the original
groups and nonempty balance masks are retained. This is not an arm64
boot test. Workload performance and fork-placement effects have not
been measured.

Assisted-by: LLM
Signed-off-by: Fengyu Wang(Hygon) <fengyuwangsjtu@xxxxxxxxxxx>
---
 kernel/sched/topology.c | 50 ++++++++++++++++++++++++++++++++++-------
 1 file changed, 42 insertions(+), 8 deletions(-)

diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 0248227d983a..9cb87b49aa00 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -1119,7 +1119,7 @@ int group_balance_cpu(struct sched_group *sg)
  * For the above NUMA topology that gives 3 levels:
  *
  * NUMA-2	0-3		0-3		0-3		0-3
- *  groups:	{0-1,3},{1-3}	{0-2},{0,2-3}	{1-3},{0-1,3}	{0,2-3},{0-2}
+ *  groups:	{0-1,3},{2}	{0-2},{3}	{1-3},{0}	{0,2-3},{1}
  *
  * NUMA-1	0-1,3		0-2		1-3		0,2-3
  *  groups:	{0},{1},{3}	{0},{1},{2}	{1},{2},{3}	{0},{2},{3}
@@ -1133,18 +1133,27 @@ int group_balance_cpu(struct sched_group *sg)
  * the topology.
  *
  * In order to minimize this overlap, we only build enough groups to cover the
- * domain. For instance Node-0 NUMA-2 would only get groups: 0-1,3 and 1-3.
+ * domain, and descend remote groups to smaller NUMA child domains to avoid
+ * CPUs that are already covered. For instance Node-0 NUMA-2 would only get
+ * groups: 0-1,3 and 2.
  *
  * Because:
  *
  *  - the first group of each domain is its child domain; this
  *    gets us the first 0-1,3
- *  - the only uncovered node is 2, who's child domain is 1-3.
+ *  - the only uncovered node is 2, who's child domain is 1-3; that overlaps
+ *    0-1,3, so we descend to node 2's NODE domain and get 2.
  *
- * However, because of the overlap, computing a unique CPU for each group is
- * more complicated. Consider for instance the groups of NODE-1 NUMA-2, both
- * groups include the CPUs of Node-0, while those CPUs would not in fact ever
- * end up at those groups (they would end up in group: 0-1,3).
+ * Only NUMA child domains are descended; node-internal domains are not split
+ * further. If the node-sized child still overlaps, the original candidate is
+ * kept. The original groups are also kept when a CPU outside the local child
+ * has no domain at this level, since shrinking a remote group could otherwise
+ * leave that CPU uncovered.
+ *
+ * However, computing a unique CPU for each group is still more complicated.
+ * Consider for instance the first group of NODE-1 NUMA-2, 0-2: it includes
+ * the CPUs of Node-0, while those CPUs would not in fact ever end up at that
+ * group (they would end up in group: 0-1,3).
  *
  * To correct this we have to introduce the group balance mask. This mask
  * will contain those CPUs in the group that can reach this group given the
@@ -1180,7 +1189,7 @@ int group_balance_cpu(struct sched_group *sg)
  * not of the same number for each CPU. Consider:
  *
  * NUMA-2	0-3						0-3
- *  groups:	{0-2},{1-3}					{1-3},{0-2}
+ *  groups:	{0-2},{3}					{1-3},{0}
  *
  * NUMA-1	0-2		0-3		0-3		1-3
  *
@@ -1320,8 +1329,20 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu)
 	struct cpumask *covered = sched_domains_tmpmask;
 	struct sd_data *sdd = sd->private;
 	struct sched_domain *sibling;
+	bool shrink = !!sd->child;
 	int i;
 
+	/* Do not shrink groups needed to cover CPUs missing this level. */
+	if (shrink) {
+		for_each_cpu_andnot(i, span, sched_domain_span(sd->child)) {
+			sibling = *per_cpu_ptr(sdd->sd, i);
+			if (!cpumask_test_cpu(i, sched_domain_span(sibling))) {
+				shrink = false;
+				break;
+			}
+		}
+	}
+
 	cpumask_clear(covered);
 
 	for_each_cpu_wrap(i, span, cpu) {
@@ -1380,6 +1401,19 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu)
 		    !cpumask_subset(sched_domain_span(sibling->child), span))
 			sibling = find_descended_sibling(sd, sibling);
 
+		if (shrink) {
+			struct sched_domain *tmp;
+
+			for (tmp = sibling; tmp->child; tmp = tmp->child) {
+				if (!cpumask_intersects(sched_domain_span(tmp->child), covered)) {
+					sibling = tmp;
+					break;
+				}
+				if (!(tmp->child->flags & SD_NUMA))
+					break;
+			}
+		}
+
 		sg = build_group_from_child_sched_domain(sibling, cpu);
 		if (!sg)
 			goto fail;

base-commit: f0100363d8c374bd8e9ea7c9ba02744f0b802ca4
-- 
2.48.1