[PATCH v2 5/8] sched/topology: Avoid redundant O(N^3) group capacity walks and unused allocations in build_sched_domains()
From: Pasha Tatashin
Date: Sun Oct 18 2026 - 21:18:35 EST
During sequential CPU hotplug on large systems, build_sched_domains() is
invoked for every CPU offline and online step. Two bottlenecks in the
domain construction path scale poorly with CPU count:
1. On non-overlapping topology levels, all CPUs sharing a domain span
share the same circular ring of sched_group instances, and on
overlapping NUMA levels, groups with identical spans share
sched_group_capacity (sgc). However, init_sched_groups_capacity()
walks the entire group ring for every CPU in the domain and repeatedly
recomputes group_weight, cores (walking the group cpumask and clearing
cpu_smt_mask), and asym_prefer_cpu (O(N^3) bitmap operations per
hotplug step). Similarly, init_overlap_sched_group() recomputes
build_balance_mask() and cpumask_weight(sg_span) even when the shared
sgc was already initialized.
2. __sdt_alloc() and __sds_alloc() upfront-allocate a sched_group,
sched_group_capacity, and sched_domain_shared for every CPU in cpu_map
at every topology level, even though get_group() only uses the entry
for the first CPU of each child domain and d.sds is only used once per
LLC (plus at most once per SD_ASYM_CPUCAPACITY_FULL domain). All other
per-CPU allocations are immediately freed unused by
__free_domain_allocs().
Cache group_weight, cores, and asym_prefer_cpu on struct
sched_group_capacity so init_sched_groups_capacity() computes them once
per shared group capacity, reuse already-initialized sgc instances in
init_overlap_sched_group(), and allocate sdd->sg, sdd->sgc, and d->sds
lazily on demand.
2-socket, 480-CPU Intel Xeon 6985P-C (N=479, mean of 10 runs):
Offline: 9.85 s -> 5.15 s (-47.7%)
Online: 8.69 s -> 4.05 s (-53.4%)
Total: 18.54 s -> 9.20 s (-50.4%)
build_sched_domains() (cpu479 offline / online):
35.65 ms -> 10.39 ms (-70.9%) / 35.68 ms -> 9.58 ms (-73.2%)
2-socket, 512-CPU AMD EPYC 9B45 (N=511, mean of 10 runs):
Offline: 4.51 s -> 3.26 s (-27.7%)
Online: 3.15 s -> 2.03 s (-35.6%)
Total: 7.66 s -> 5.29 s (-30.9%)
build_sched_domains() (cpu511 offline / online):
11.69 ms -> 5.61 ms (-52.0%) / 12.24 ms -> 5.84 ms (-52.3%)
Signed-off-by: Pasha Tatashin <pasha.tatashin@xxxxxxxxxx>
---
kernel/sched/sched.h | 9 ++
kernel/sched/topology.c | 218 ++++++++++++++++++++++++++--------------
2 files changed, 150 insertions(+), 77 deletions(-)
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 499a5649582e..314fcad94668 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -2262,6 +2262,15 @@ struct sched_group_capacity {
int id;
+ /*
+ * Build-time cache shared by all groups using this sgc while
+ * build_sched_domains() runs; not maintained afterwards (e.g. by
+ * sched_update_asym_prefer_cpu()). Use the sched_group copies.
+ */
+ unsigned int group_weight;
+ unsigned int cores;
+ int asym_prefer_cpu;
+
unsigned long cpumask[]; /* Balance mask */
};
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 919d0fb00bd9..a5a5d1378ce2 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -1207,6 +1207,33 @@ int group_balance_cpu(struct sched_group *sg)
*/
+/* Find the group_balance_cpu() */
+static int find_group_balance_cpu(struct sched_domain *sd, struct sched_group *sg)
+{
+ const struct cpumask *sg_span = sched_group_span(sg);
+ struct sd_data *sdd = sd->private;
+ struct sched_domain *sibling;
+ int i;
+
+ for_each_cpu(i, sg_span) {
+ sibling = *per_cpu_ptr(sdd->sd, i);
+
+ /*
+ * Can happen in the asymmetric case, where these siblings are
+ * unused. The mask will not be empty because those CPUs that
+ * do have the top domain _should_ span the domain.
+ */
+ if (!sibling->child)
+ continue;
+
+ /* If we would not end up here, we can't continue from here */
+ if (cpumask_equal(sg_span, sched_domain_span(sibling->child)))
+ return i;
+ }
+
+ return nr_cpu_ids;
+}
+
/*
* Build the balance mask; it contains only those CPUs that can arrive at this
* group and should be considered to continue balancing.
@@ -1216,17 +1243,19 @@ int group_balance_cpu(struct sched_group *sg)
* can fully construct this using the sched_domain bits (which are already
* complete).
*/
-static void
-build_balance_mask(struct sched_domain *sd, struct sched_group *sg, struct cpumask *mask)
+static void build_balance_mask(int group_balance_cpu,
+ struct sched_domain *sd,
+ struct sched_group *sg,
+ struct cpumask *mask)
{
const struct cpumask *sg_span = sched_group_span(sg);
struct sd_data *sdd = sd->private;
struct sched_domain *sibling;
- int i;
+ int i = group_balance_cpu;
cpumask_clear(mask);
- for_each_cpu(i, sg_span) {
+ for_each_cpu_from(i, sg_span) {
sibling = *per_cpu_ptr(sdd->sd, i);
/*
@@ -1277,32 +1306,51 @@ build_group_from_child_sched_domain(struct sched_domain *sd, int cpu)
return sg;
}
-static void init_overlap_sched_group(struct sched_domain *sd,
- struct sched_group *sg)
+static int init_overlap_sched_group(struct sched_domain *sd,
+ struct sched_group *sg)
{
struct cpumask *mask = sched_domains_tmpmask2;
struct sd_data *sdd = sd->private;
- struct cpumask *sg_span;
+ struct cpumask *sg_span = sched_group_span(sg);
+ struct sched_group_capacity *sgc;
int cpu;
- build_balance_mask(sd, sg, mask);
- cpu = cpumask_first(mask);
+ cpu = find_group_balance_cpu(sd, sg);
+ if (WARN_ON_ONCE(cpu >= nr_cpu_ids))
+ return -ENOENT;
- sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);
- if (atomic_inc_return(&sg->sgc->ref) == 1)
- cpumask_copy(group_balance_mask(sg), mask);
- else
- WARN_ON_ONCE(!cpumask_equal(group_balance_mask(sg), mask));
+ sgc = *per_cpu_ptr(sdd->sgc, cpu);
+ if (sgc && atomic_read(&sgc->ref)) {
+ atomic_inc(&sgc->ref);
+ sg->sgc = sgc;
+ return 0;
+ }
+
+ if (!sgc) {
+ sgc = kzalloc_node(sizeof(*sgc) + cpumask_size(),
+ GFP_KERNEL, cpu_to_node(cpu));
+ if (!sgc)
+ return -ENOMEM;
+ sgc->id = cpu;
+ *per_cpu_ptr(sdd->sgc, cpu) = sgc;
+ }
+
+ build_balance_mask(cpu, sd, sg, mask);
+
+ sg->sgc = sgc;
+ atomic_set(&sgc->ref, 1);
+ cpumask_copy(group_balance_mask(sg), mask);
/*
* Initialize sgc->capacity such that even if we mess up the
* domains and no possible iteration will get us here, we won't
* die on a /0 trap.
*/
- sg_span = sched_group_span(sg);
- sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sg_span);
- sg->sgc->min_capacity = SCHED_CAPACITY_SCALE;
- sg->sgc->max_capacity = SCHED_CAPACITY_SCALE;
+ sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sg_span);
+ sgc->min_capacity = SCHED_CAPACITY_SCALE;
+ sgc->max_capacity = SCHED_CAPACITY_SCALE;
+
+ return 0;
}
static struct sched_domain *
@@ -1405,7 +1453,10 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu)
sg_span = sched_group_span(sg);
cpumask_or(covered, covered, sg_span);
- init_overlap_sched_group(sibling, sg);
+ if (init_overlap_sched_group(sibling, sg)) {
+ kfree(sg);
+ goto fail;
+ }
if (!first)
first = sg;
@@ -1507,6 +1558,25 @@ static struct sched_group *get_group(int cpu, struct sd_data *sdd)
cpu = cpumask_first(sched_domain_span(child));
sg = *per_cpu_ptr(sdd->sg, cpu);
+ if (!sg) {
+ sg = kzalloc_node(sizeof(*sg) + cpumask_size(),
+ GFP_KERNEL, cpu_to_node(cpu));
+ if (!sg)
+ return NULL;
+ sg->next = sg;
+ *per_cpu_ptr(sdd->sg, cpu) = sg;
+ }
+
+ if (!*per_cpu_ptr(sdd->sgc, cpu)) {
+ struct sched_group_capacity *sgc;
+
+ sgc = kzalloc_node(sizeof(*sgc) + cpumask_size(),
+ GFP_KERNEL, cpu_to_node(cpu));
+ if (!sgc)
+ return NULL;
+ sgc->id = cpu;
+ *per_cpu_ptr(sdd->sgc, cpu) = sgc;
+ }
sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);
/* Increase refcounts for claim_allocations: */
@@ -1562,6 +1632,8 @@ build_sched_groups(struct sched_domain *sd, int cpu)
continue;
sg = get_group(i, sdd);
+ if (!sg)
+ return -ENOMEM;
cpumask_or(covered, covered, sched_group_span(sg));
@@ -1595,27 +1667,40 @@ static void init_sched_groups_capacity(int cpu, struct sched_domain *sd)
WARN_ON(!sg);
do {
- int cpu, cores = 0, max_cpu = -1;
+ int i, cores = 0, max_cpu = -1;
+
+ if (sg->group_weight)
+ goto next;
+
+ if (sg->sgc->group_weight) {
+ sg->group_weight = sg->sgc->group_weight;
+ sg->cores = sg->sgc->cores;
+ sg->asym_prefer_cpu = sg->sgc->asym_prefer_cpu;
+ goto next;
+ }
sg->group_weight = cpumask_weight(sched_group_span(sg));
cpumask_copy(mask, sched_group_span(sg));
- for_each_cpu(cpu, mask) {
+ for_each_cpu(i, mask) {
cores++;
- cpumask_andnot(mask, mask, cpu_smt_mask(cpu));
+ cpumask_andnot(mask, mask, cpu_smt_mask(i));
}
sg->cores = cores;
- if (!(sd->flags & SD_ASYM_PACKING))
- goto next;
-
- for_each_cpu(cpu, sched_group_span(sg)) {
- if (max_cpu < 0)
- max_cpu = cpu;
- else if (sched_asym_prefer(cpu, max_cpu))
- max_cpu = cpu;
+ if (sd->flags & SD_ASYM_PACKING) {
+ for_each_cpu(i, sched_group_span(sg)) {
+ if (max_cpu < 0)
+ max_cpu = i;
+ else if (sched_asym_prefer(i, max_cpu))
+ max_cpu = i;
+ }
+ sg->asym_prefer_cpu = max_cpu;
}
- sg->asym_prefer_cpu = max_cpu;
+
+ sg->sgc->group_weight = sg->group_weight;
+ sg->sgc->cores = sg->cores;
+ sg->sgc->asym_prefer_cpu = sg->asym_prefer_cpu;
next:
sg = sg->next;
@@ -1889,7 +1974,8 @@ static void claim_allocations(int cpu, struct s_data *d)
{
struct sched_domain *sd;
- if (atomic_read(&(*per_cpu_ptr(d->sds, cpu))->ref))
+ if (*per_cpu_ptr(d->sds, cpu) &&
+ atomic_read(&(*per_cpu_ptr(d->sds, cpu))->ref))
*per_cpu_ptr(d->sds, cpu) = NULL;
for (sd = *per_cpu_ptr(d->sd, cpu); sd; sd = sd->parent) {
@@ -1898,10 +1984,12 @@ static void claim_allocations(int cpu, struct s_data *d)
WARN_ON_ONCE(*per_cpu_ptr(sdd->sd, cpu) != sd);
*per_cpu_ptr(sdd->sd, cpu) = NULL;
- if (atomic_read(&(*per_cpu_ptr(sdd->sg, cpu))->ref))
+ if (*per_cpu_ptr(sdd->sg, cpu) &&
+ atomic_read(&(*per_cpu_ptr(sdd->sg, cpu))->ref))
*per_cpu_ptr(sdd->sg, cpu) = NULL;
- if (atomic_read(&(*per_cpu_ptr(sdd->sgc, cpu))->ref))
+ if (*per_cpu_ptr(sdd->sgc, cpu) &&
+ atomic_read(&(*per_cpu_ptr(sdd->sgc, cpu))->ref))
*per_cpu_ptr(sdd->sgc, cpu) = NULL;
}
}
@@ -2700,8 +2788,6 @@ static int __sdt_alloc(const struct cpumask *cpu_map)
for_each_cpu(j, cpu_map) {
struct sched_domain *sd;
- struct sched_group *sg;
- struct sched_group_capacity *sgc;
sd = kzalloc_node(sizeof(struct sched_domain) + cpumask_size(),
GFP_KERNEL, cpu_to_node(j));
@@ -2709,24 +2795,6 @@ static int __sdt_alloc(const struct cpumask *cpu_map)
return -ENOMEM;
*per_cpu_ptr(sdd->sd, j) = sd;
-
- sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
- GFP_KERNEL, cpu_to_node(j));
- if (!sg)
- return -ENOMEM;
-
- sg->next = sg;
-
- *per_cpu_ptr(sdd->sg, j) = sg;
-
- sgc = kzalloc_node(sizeof(struct sched_group_capacity) + cpumask_size(),
- GFP_KERNEL, cpu_to_node(j));
- if (!sgc)
- return -ENOMEM;
-
- sgc->id = j;
-
- *per_cpu_ptr(sdd->sgc, j) = sgc;
}
}
@@ -2767,23 +2835,10 @@ static void __sdt_free(const struct cpumask *cpu_map)
static int __sds_alloc(struct s_data *d, const struct cpumask *cpu_map)
{
- int j;
-
d->sds = alloc_percpu(struct sched_domain_shared *);
if (!d->sds)
return -ENOMEM;
- for_each_cpu(j, cpu_map) {
- struct sched_domain_shared *sds;
-
- sds = kzalloc_node(sizeof(struct sched_domain_shared),
- GFP_KERNEL, cpu_to_node(j));
- if (!sds)
- return -ENOMEM;
-
- *per_cpu_ptr(d->sds, j) = sds;
- }
-
return 0;
}
@@ -2954,7 +3009,7 @@ static void adjust_numa_imbalance(struct sched_domain *sd_llc)
}
}
-static void
+static int
init_sched_domain_shared(struct s_data *d, struct sched_domain *sd, int flags)
{
struct sched_domain_shared *sds = NULL;
@@ -2976,6 +3031,13 @@ init_sched_domain_shared(struct s_data *d, struct sched_domain *sd, int flags)
*/
for_each_cpu(cpu, sched_domain_span(sd)) {
sds = *per_cpu_ptr(d->sds, cpu);
+ if (!sds) {
+ sds = kzalloc_node(sizeof(*sds),
+ GFP_KERNEL, cpu_to_node(cpu));
+ if (!sds)
+ return -ENOMEM;
+ *per_cpu_ptr(d->sds, cpu) = sds;
+ }
if (!sds->alloc_flags ||
sd->span_weight == 1 ||
@@ -3000,6 +3062,8 @@ init_sched_domain_shared(struct s_data *d, struct sched_domain *sd, int flags)
*/
atomic_set(&sd->shared->nr_busy_cpus, sd->span_weight);
atomic_inc(&sd->shared->ref);
+
+ return 0;
}
/*
@@ -3015,25 +3079,24 @@ init_sched_domain_shared(struct s_data *d, struct sched_domain *sd, int flags)
* degenerate into a single-capacity group. The relevant edge cases are instead
* covered by the caveats above.
*
- * Return true if this CPU's asym path claimed sd->shared, false otherwise.
+ * Return 0 on success or if not claimed, -ENOMEM on allocation failure.
*/
-static bool claim_asym_sched_domain_shared(struct s_data *d, int cpu)
+static int claim_asym_sched_domain_shared(struct s_data *d, int cpu)
{
struct sched_domain *sd = *per_cpu_ptr(d->sd, cpu);
struct sched_domain *sd_asym;
if (!sd)
- return false;
+ return 0;
sd_asym = sd;
while (sd_asym && !(sd_asym->flags & SD_ASYM_CPUCAPACITY_FULL))
sd_asym = sd_asym->parent;
if (!sd_asym || (sd_asym->flags & SD_NUMA))
- return false;
+ return 0;
- init_sched_domain_shared(d, sd_asym, SD_ASYM_CPUCAPACITY);
- return true;
+ return init_sched_domain_shared(d, sd_asym, SD_ASYM_CPUCAPACITY);
}
static int __sched_domains_alloc_llc_id(void)
@@ -3179,15 +3242,16 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
if (!sd)
continue;
- if (has_asym)
- claim_asym_sched_domain_shared(&d, i);
+ if (has_asym && claim_asym_sched_domain_shared(&d, i))
+ goto error;
/* First, find the topmost SD_SHARE_LLC domain */
while (sd->parent && (sd->parent->flags & SD_SHARE_LLC))
sd = sd->parent;
if (sd->flags & SD_SHARE_LLC) {
- init_sched_domain_shared(&d, sd, SD_SHARE_LLC);
+ if (init_sched_domain_shared(&d, sd, SD_SHARE_LLC))
+ goto error;
/*
* In presence of higher domains, adjust the
--
2.56.0.176.g3575e65682-goog