During CPU hotplug, build_sched_domains() is invoked on every CPU activation and deactivation. Profiling build_sched_domains() on a 480-CPU Intel Xeon 6985P-C and a 512-CPU AMD EPYC 9B45 shows several sources of avoidable O(N^2) and O(N) work per step: 1. build_sched_groups() and build_overlap_sched_groups() iterate over every bit of sched_domain_span(sd) via for_each_cpu_wrap(i, span, cpu) and check cpumask_test_cpu(i, covered) one CPU at a time, even after entire child groups (e.g., 120-CPU NUMA nodes) have been added to covered. Instead, track the remaining uncovered CPUs (cpumask_copy(uncovered, span)), clear each built group's span with cpumask_andnot(), and advance directly to the next uncovered CPU. 2. __visit_domain_allocation_hell() and __free_domain_allocs() allocate and free 3 * nr_levels + 2 temporary per-CPU pointer arrays via alloc_percpu() / free_percpu() on every domain rebuild. Reuse the per-CPU pointer arrays across domain rebuilds (serialized by sched_domains_mutex), clearing entries in __free_domain_allocs() and only freeing the topology-level arrays when sched_domain_topology is replaced in sched_init_numa() / sched_reset_numa() (serialized against domain rebuilds by the CPU hotplug lock). 3. sd_init() already computes sd_weight = cpumask_weight(sd_span), so initialize sd->span_weight directly in sd_init() and reuse child->span_weight in get_group() instead of recomputing cpumask_weight() across all domains and groups. 4. Reuse the first LLC sibling's computed llc_bytes in alloc_sd_llc() and sched_update_llc_bytes(). 2-socket, 480-CPU Intel Xeon 6985P-C (N=479, mean of 10 runs): Offline: 3.88 s -> 3.37 s (-13.1%) Online: 2.51 s -> 2.06 s (-17.9%) Total: 6.39 s -> 5.43 s (-15.0%) build_sched_domains() (cpu479 offline / online): 7.91 ms -> 3.96 ms (-50.0%) / 7.51 ms -> 4.26 ms (-43.3%) 2-socket, 512-CPU AMD EPYC 9B45 (N=511, mean of 10 runs): Offline: 2.77 s -> 2.34 s (-15.5%) Online: 1.53 s -> 1.12 s (-26.8%) Total: 4.30 s -> 3.46 s (-19.5%) build_sched_domains() (cpu511 offline / online): 6.55 ms -> 3.04 ms (-53.7%) / 5.28 ms -> 3.20 ms (-39.4%) Signed-off-by: Pasha Tatashin --- kernel/sched/topology.c | 171 ++++++++++++++++++++++++++++------------ 1 file changed, 122 insertions(+), 49 deletions(-) diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c index b5dec7f486b5..33210fd9dc2c 100644 --- a/kernel/sched/topology.c +++ b/kernel/sched/topology.c @@ -917,9 +917,15 @@ static bool alloc_sd_llc(const struct cpumask *cpu_map, top_llc = parent; if (top_llc->flags & SD_SHARE_LLC) { + int first = cpumask_first(sched_domain_span(top_llc)); + sd->llc_max = max_lid + 1; sd->llc_counts = p; - sd->llc_bytes = get_effective_llc_bytes(i, top_llc); + /* All CPUs in top_llc share the same LLC size and weight. */ + if (first < i) + sd->llc_bytes = (*per_cpu_ptr(d->sd, first))->llc_bytes; + else + sd->llc_bytes = get_effective_llc_bytes(i, top_llc); } else { /* avoid memory leak */ kfree(p); @@ -1018,12 +1024,20 @@ void sched_update_llc_bytes(const struct cpumask *cpus) * own LLC domain to scale its share of the physical cache. */ for_each_cpu(i, cpus) { + int first; + sdp = rcu_dereference_sched_domain(per_cpu(sd_llc, i)); if (!sdp) continue; sd = rcu_dereference_sched_domain(cpu_rq(i)->sd); - if (sd) + if (!sd) + continue; + + first = cpumask_first(sched_domain_span(sdp)); + if (first < i) + sd->llc_bytes = rcu_dereference_sched_domain(cpu_rq(first)->sd)->llc_bytes; + else sd->llc_bytes = get_effective_llc_bytes(i, sdp); } @@ -1370,19 +1384,18 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu) { struct sched_group *first = NULL, *last = NULL, *sg; const struct cpumask *span = sched_domain_span(sd); - struct cpumask *covered = sched_domains_tmpmask; + struct cpumask *uncovered = sched_domains_tmpmask; struct sd_data *sdd = sd->private; struct sched_domain *sibling; int i; - cpumask_clear(covered); + cpumask_copy(uncovered, span); - for_each_cpu_wrap(i, span, cpu) { + for (i = cpu; i < nr_cpu_ids; + i = cpumask_next(i, uncovered), + i = i < nr_cpu_ids ? i : cpumask_first(uncovered)) { struct cpumask *sg_span; - if (cpumask_test_cpu(i, covered)) - continue; - sibling = *per_cpu_ptr(sdd->sd, i); /* @@ -1395,8 +1408,10 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu) * Domains should always include the CPU they're built on, so * check that. */ - if (!cpumask_test_cpu(i, sched_domain_span(sibling))) + if (!cpumask_test_cpu(i, sched_domain_span(sibling))) { + __cpumask_clear_cpu(i, uncovered); continue; + } /* * Usually we build sched_group by sibling's child sched_domain @@ -1438,7 +1453,7 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu) goto fail; sg_span = sched_group_span(sg); - cpumask_or(covered, covered, sg_span); + cpumask_andnot(uncovered, uncovered, sg_span); if (init_overlap_sched_group(sibling, sg)) { kfree(sg); @@ -1579,12 +1594,13 @@ static struct sched_group *get_group(int cpu, struct sd_data *sdd) cpumask_copy(sched_group_span(sg), sched_domain_span(child)); cpumask_copy(group_balance_mask(sg), sched_group_span(sg)); sg->flags = child->flags; + sg->sgc->capacity = SCHED_CAPACITY_SCALE * child->span_weight; } else { cpumask_set_cpu(cpu, sched_group_span(sg)); cpumask_set_cpu(cpu, group_balance_mask(sg)); + sg->sgc->capacity = SCHED_CAPACITY_SCALE; } - sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sched_group_span(sg)); sg->sgc->min_capacity = SCHED_CAPACITY_SCALE; sg->sgc->max_capacity = SCHED_CAPACITY_SCALE; @@ -1604,25 +1620,24 @@ build_sched_groups(struct sched_domain *sd, int cpu) struct sched_group *first = NULL, *last = NULL; struct sd_data *sdd = sd->private; const struct cpumask *span = sched_domain_span(sd); - struct cpumask *covered; + struct cpumask *uncovered; int i; lockdep_assert_held(&sched_domains_mutex); - covered = sched_domains_tmpmask; + uncovered = sched_domains_tmpmask; - cpumask_clear(covered); + cpumask_copy(uncovered, span); - for_each_cpu_wrap(i, span, cpu) { + for (i = cpu; i < nr_cpu_ids; + i = cpumask_next(i, uncovered), + i = i < nr_cpu_ids ? i : cpumask_first(uncovered)) { struct sched_group *sg; - if (cpumask_test_cpu(i, covered)) - continue; - sg = get_group(i, sdd); if (!sg) return -ENOMEM; - cpumask_or(covered, covered, sched_group_span(sg)); + cpumask_andnot(uncovered, uncovered, sched_group_span(sg)); if (!first) first = sg; @@ -1911,16 +1926,21 @@ static int __sdt_alloc(const struct cpumask *cpu_map); static void __sds_free(struct s_data *d, const struct cpumask *cpu_map); static int __sds_alloc(struct s_data *d, const struct cpumask *cpu_map); +static struct sched_domain * __percpu *sched_domains_sd; + static void __free_domain_allocs(struct s_data *d, enum s_alloc what, const struct cpumask *cpu_map) { + int j; + switch (what) { case sa_rootdomain: if (!atomic_read(&d->rd->refcount)) free_rootdomain(&d->rd->rcu); fallthrough; case sa_sd: - free_percpu(d->sd); + for_each_cpu(j, cpu_map) + *per_cpu_ptr(d->sd, j) = NULL; fallthrough; case sa_sd_shared: __sds_free(d, cpu_map); @@ -1942,9 +1962,12 @@ __visit_domain_allocation_hell(struct s_data *d, const struct cpumask *cpu_map) return sa_sd_storage; if (__sds_alloc(d, cpu_map)) return sa_sd_shared; - d->sd = alloc_percpu(struct sched_domain *); - if (!d->sd) - return sa_sd_shared; + if (!sched_domains_sd) { + sched_domains_sd = alloc_percpu(struct sched_domain *); + if (!sched_domains_sd) + return sa_sd_shared; + } + d->sd = sched_domains_sd; d->rd = alloc_rootdomain(); if (!d->rd) return sa_sd; @@ -2072,6 +2095,7 @@ sd_init(struct sched_domain_topology_level *tl, .last_balance = jiffies, .balance_interval = sd_weight, + .span_weight = sd_weight, /* 50% success rate */ .newidle_call = 512, @@ -2212,6 +2236,24 @@ void __init set_sched_topology(struct sched_domain_topology_level *tl) } #ifdef CONFIG_NUMA +static void __sdt_free_percpu(void) +{ + struct sched_domain_topology_level *tl; + + lockdep_assert_cpus_held(); + + for_each_sd_topology(tl) { + struct sd_data *sdd = &tl->data; + + free_percpu(sdd->sd); + sdd->sd = NULL; + free_percpu(sdd->sg); + sdd->sg = NULL; + free_percpu(sdd->sgc); + sdd->sgc = NULL; + } +} + static int cpu_numa_flags(void) { return SD_NUMA; @@ -2502,6 +2544,7 @@ void sched_init_numa(int offline_node) /* * Copy the default topology bits.. */ + __sdt_free_percpu(); for (i = 0; sched_domain_topology[i].mask; i++) tl[i] = sched_domain_topology[i]; @@ -2560,6 +2603,7 @@ static void sched_reset_numa(void) kfree(masks); } if (sched_domain_topology_saved) { + __sdt_free_percpu(); kfree(sched_domain_topology); sched_domain_topology = sched_domain_topology_saved; sched_domain_topology_saved = NULL; @@ -2761,21 +2805,38 @@ static int __sdt_alloc(const struct cpumask *cpu_map) for_each_sd_topology(tl) { struct sd_data *sdd = &tl->data; - sdd->sd = alloc_percpu(struct sched_domain *); - if (!sdd->sd) - return -ENOMEM; + if (!sdd->sd) { + sdd->sd = alloc_percpu(struct sched_domain *); + if (!sdd->sd) + return -ENOMEM; + } - sdd->sg = alloc_percpu(struct sched_group *); - if (!sdd->sg) - return -ENOMEM; + if (!sdd->sg) { + sdd->sg = alloc_percpu(struct sched_group *); + if (!sdd->sg) + return -ENOMEM; + } - sdd->sgc = alloc_percpu(struct sched_group_capacity *); - if (!sdd->sgc) - return -ENOMEM; + if (!sdd->sgc) { + sdd->sgc = alloc_percpu(struct sched_group_capacity *); + if (!sdd->sgc) + return -ENOMEM; + } + /* + * The slot arrays are kept between builds. Every slot for a CPU + * in cpu_map must be NULL here; lazy allocation treats NULL as + * "not allocated in this build". claim_allocations() and + * __sdt_free()/__sds_free() clear the slots, but only for + * cpu_map, so a build must not fill slots outside cpu_map. + */ for_each_cpu(j, cpu_map) { struct sched_domain *sd; + WARN_ON_ONCE(*per_cpu_ptr(sdd->sd, j) || + *per_cpu_ptr(sdd->sg, j) || + *per_cpu_ptr(sdd->sgc, j)); + sd = kzalloc_node(sizeof(struct sched_domain) + cpumask_size(), GFP_KERNEL, cpu_to_node(j)); if (!sd) @@ -2801,30 +2862,41 @@ static void __sdt_free(const struct cpumask *cpu_map) if (sdd->sd) { sd = *per_cpu_ptr(sdd->sd, j); - if (sd && (sd->flags & SD_NUMA)) - free_sched_groups(sd->groups, 0); - kfree(*per_cpu_ptr(sdd->sd, j)); + if (sd) { + if (sd->flags & SD_NUMA) + free_sched_groups(sd->groups, 0); + kfree(sd); + *per_cpu_ptr(sdd->sd, j) = NULL; + } } - if (sdd->sg) + if (sdd->sg) { kfree(*per_cpu_ptr(sdd->sg, j)); - if (sdd->sgc) + *per_cpu_ptr(sdd->sg, j) = NULL; + } + if (sdd->sgc) { kfree(*per_cpu_ptr(sdd->sgc, j)); + *per_cpu_ptr(sdd->sgc, j) = NULL; + } } - free_percpu(sdd->sd); - sdd->sd = NULL; - free_percpu(sdd->sg); - sdd->sg = NULL; - free_percpu(sdd->sgc); - sdd->sgc = NULL; } } +static struct sched_domain_shared * __percpu *sched_domains_sds; + static int __sds_alloc(struct s_data *d, const struct cpumask *cpu_map) { - d->sds = alloc_percpu(struct sched_domain_shared *); - if (!d->sds) - return -ENOMEM; + int j; + + if (!sched_domains_sds) { + sched_domains_sds = alloc_percpu(struct sched_domain_shared *); + if (!sched_domains_sds) + return -ENOMEM; + } + d->sds = sched_domains_sds; + + for_each_cpu(j, cpu_map) + WARN_ON_ONCE(*per_cpu_ptr(d->sds, j)); return 0; } @@ -2836,10 +2908,11 @@ static void __sds_free(struct s_data *d, const struct cpumask *cpu_map) if (!d->sds) return; - for_each_cpu(j, cpu_map) + for_each_cpu(j, cpu_map) { kfree(*per_cpu_ptr(d->sds, j)); + *per_cpu_ptr(d->sds, j) = NULL; + } - free_percpu(d->sds); d->sds = NULL; } @@ -2863,6 +2936,7 @@ static struct sched_domain *build_sched_domain(struct sched_domain_topology_leve cpumask_or(sched_domain_span(sd), sched_domain_span(sd), sched_domain_span(child)); + sd->span_weight = cpumask_weight(sched_domain_span(sd)); } } @@ -3213,7 +3287,6 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att /* Build the groups for the domains */ for_each_cpu(i, cpu_map) { for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) { - sd->span_weight = cpumask_weight(sched_domain_span(sd)); if (sd->flags & SD_NUMA) { if (build_overlap_sched_groups(sd, i)) goto error; -- 2.56.0.176.g3575e65682-goog