[PATCH v1 5/8] sched/topology: Avoid redundant O(N^3) group capacity walks and unused allocations in build_sched_domains()

[K Prateek Nayak]

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.

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?

>                 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(?)

> +       }
> 
> -       /*
> -        * 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