Re: [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@soleen.com>]

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
>