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 --- 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