[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
Sun Oct 18 07:35:19 PDT 2026
On 10-16 11:53, K Prateek Nayak wrote:
> Hello Pasha,
>
> On 10/15/2026 9:03 PM, Pasha Tatashin wrote:
> > 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;
> > + }
>
>
> This insanely specific check perhaps can be something like:
>
> diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
> index 06cc9f6397bd..a7d7a3b51c71 100644
> --- a/kernel/sched/topology.c
> +++ b/kernel/sched/topology.c
> @@ -1203,6 +1203,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.
> @@ -1212,17 +1239,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);
>
> /*
> @@ -1281,7 +1310,17 @@ static int init_overlap_sched_group(struct sched_domain *sd,
> struct cpumask *sg_span;
> int cpu;
>
> - build_balance_mask(sd, sg, 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 (sg->sgc && atomic_read(&sg->sgc->ref)) {
> + atomic_inc(&sg->sgc->ref);
> + return 0;
> + }
> +
> + build_balance_mask(cpu, sd, sg, mask);
> cpu = cpumask_first(mask);
>
> sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);
> ---
>
> We just find the first CPU and reuse the scg. Otherwise, build the
> balance mask.
Yes, this is cleaner, thank you.
>
> With those changes ...
>
> >
> > 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) {
>
> ... we can be sure this is a new sgc and just do an
> atomic_set(&sg->sgc->ref, 1) here and initialize the rest of the
> fields.
>
> Thoughts?
+1, Since sgc is lazily allocated on demand in this patch, reaching
the slow path guarantees we are initializing it for the first time.
> > 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));
>
> Do note this check will be lost with the optimization for the
> fast-path case but that should be okay(?)
Yes, that is fine: find_group_balance_cpu() already verifies that
sg_span equals sched_domain_span(sibling->child) for cpu.
I will fold this into v2.
Thanks,
Pasha
>
> > + }
> >
> > - /*
> > - * 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;
> > }
> --
> Thanks and Regards,
> Prateek
>
More information about the kexec
mailing list