[PATCH v1 5/8] sched/topology: Avoid redundant O(N^3) group capacity walks and unused allocations in build_sched_domains()
Pasha Tatashin
pasha.tatashin at soleen.com
Thu Oct 15 08:33:28 PDT 2026
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 at soleen.com>
---
kernel/sched/sched.h | 9 ++
kernel/sched/topology.c | 183 ++++++++++++++++++++++++----------------
2 files changed, 117 insertions(+), 75 deletions(-)
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index e656c7059bf86..b76e2cd695025 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -2261,6 +2261,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 0248227d983a7..02c38089a80c9 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -1259,32 +1259,49 @@ 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;
- int cpu;
+ struct cpumask *sg_span = sched_group_span(sg);
+ struct sched_group_capacity *sgc;
+ int cpu = cpumask_first(sg_span);
+ struct sched_domain *first_sd = *per_cpu_ptr(sdd->sd, cpu);
+
+ sgc = *per_cpu_ptr(sdd->sgc, cpu);
+ if (sgc && atomic_read(&sgc->ref) > 0 &&
+ first_sd && first_sd->child &&
+ cpumask_equal(sg_span, sched_domain_span(first_sd->child))) {
+ atomic_inc(&sgc->ref);
+ sg->sgc = sgc;
+ return 0;
+ }
build_balance_mask(sd, sg, mask);
cpu = cpumask_first(mask);
- sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);
- if (atomic_inc_return(&sg->sgc->ref) == 1)
+ sgc = *per_cpu_ptr(sdd->sgc, cpu);
+ 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;
+ }
+
+ sg->sgc = sgc;
+ if (atomic_inc_return(&sg->sgc->ref) == 1) {
cpumask_copy(group_balance_mask(sg), mask);
- else
+ sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sg_span);
+ sg->sgc->min_capacity = SCHED_CAPACITY_SCALE;
+ sg->sgc->max_capacity = SCHED_CAPACITY_SCALE;
+ } else {
WARN_ON_ONCE(!cpumask_equal(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;
+ return 0;
}
static struct sched_domain *
@@ -1387,7 +1404,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;
@@ -1489,6 +1509,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: */
@@ -1544,6 +1583,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));
@@ -1577,27 +1618,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;
@@ -1871,7 +1925,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) {
@@ -1880,10 +1935,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;
}
}
@@ -2678,8 +2735,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));
@@ -2687,24 +2742,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;
}
}
@@ -2745,23 +2782,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;
}
@@ -2932,7 +2956,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;
@@ -2954,6 +2978,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 ||
@@ -2978,6 +3009,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;
}
/*
@@ -2993,25 +3026,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)
@@ -3157,15 +3189,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.385.gd3acb90ef8-goog
More information about the kexec
mailing list