[PATCH 0/2] sched/fair: Load balance improvements

[PATCH 0/2] sched/fair: Load balance improvements

[Pierre Gondois]

The first patch is a resend from:
https://lore.kernel.org/all/20241001134603.2758480-1-pierre.gondois@arm.com/#t

The second patch aims to balance the ratio of #Tasks/#CPUs
between groups if the busiest group has no idle CPUs.

Pierre Gondois (2):
  sched/fair: Fix integer underflow
  sched/fair: Balance #Tasks/#CPUs if busiest group has no idle CPU

 kernel/sched/fair.c | 14 ++++++--------
 1 file changed, 6 insertions(+), 8 deletions(-)

--
2.43.0

[PATCH 1/2] sched/fair: Fix integer underflow

[Pierre Gondois]

(struct sg_lb_stats).idle_cpus is of type 'unsigned int'.
(local->idle_cpus - busiest->idle_cpus) can underflow to UINT_MAX
for instance, and max_t(long, 0, UINT_MAX) will output UINT_MAX.

Use lsub_positive() instead of max_t().

Fixes: 16b0a7a1a0af ("sched/fair: Ensure tasks spreading in LLC during LB")
cc: stable@vger.kernel.org
Signed-off-by: Pierre Gondois <pierre.gondois@arm.com>
Reviewed-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index da46c31645378..aa14a9982b9f1 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -11249,8 +11249,8 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
 			 * idle CPUs.
 			 */
 			env->migration_type = migrate_task;
-			env->imbalance = max_t(long, 0,
-					       (local->idle_cpus - busiest->idle_cpus));
+			env->imbalance = local->idle_cpus;
+			lsub_positive(&env->imbalance, busiest->idle_cpus);
 		}
 
 #ifdef CONFIG_NUMA
-- 
2.43.0

[PATCH 2/2] sched/fair: Balance #Tasks/#CPUs if busiest group has no idle CPU

[Pierre Gondois]

Balancing the number of idle CPUs between groups is done if:
- the busiest group is overloaded: sum_nr_running > #CPUs
- the local group has spare capacity: sum_nr_running <= #CPUs

To avoid pulling too many tasks and moving the imbalance to the
local group, the number of task pulled is half of:
  (local->idle_cpus - busiest->idle_cpus)

Halving the imbalance currently lead to the following scenario.
On a Juno with 2 clusters: CLU0: 4 CPUs and CLU1: 2 CPUs, with
6 long running tasks:
- 1 task on the 2-CPUs cluster
- 5 Tasks run in the 4-CPUs cluster
Running the load balancer from the idle CPU (in CLU1):
- Local group: CLU1: idle_cpus=1; nr_running=1; type=group_has_spare
- Busiest group: CLU0 idle_cpus=0; nr_running=5 type=group_overloaded
Half of (local->idle_cpus - busiest->idle_cpus) is 0.
No task is migrated and the task placement persists.

Balancing number of idle CPUs is only relevant if the busiest group
has idle CPUs. Otherwise it is better to have an equal ratio
of #tasks / #CPUs.

sibling_imbalance() was also introduced to cope with groups with
asymmetric sizes. This is also the case here.
commit 7ff1693236f5 ("sched/fair: Implement prefer sibling
imbalance calculation between asymmetric groups")

Try to stay conservative and only balance the ratio
of #Tasks / #CPUs if the busiest group has no idle CPUs.
Note that a similar check present in update_pick_idlest()
is not updated.

Signed-off-by: Pierre Gondois <pierre.gondois@arm.com>
---
 kernel/sched/fair.c | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index aa14a9982b9f1..9dac3536d9c19 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -11235,20 +11235,18 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
 			return;
 		}
 
-		if (busiest->group_weight == 1 || sds->prefer_sibling) {
+		env->migration_type = migrate_task;
+		if (busiest->group_weight == 1 || sds->prefer_sibling || !busiest->idle_cpus) {
 			/*
-			 * When prefer sibling, evenly spread running tasks on
-			 * groups.
+			 * When prefer sibling, or when busiest has no idle CPU,
+			 * evenly spread running tasks on groups.
 			 */
-			env->migration_type = migrate_task;
 			env->imbalance = sibling_imbalance(env, sds, busiest, local);
 		} else {
-
 			/*
 			 * If there is no overload, we just want to even the number of
 			 * idle CPUs.
 			 */
-			env->migration_type = migrate_task;
 			env->imbalance = local->idle_cpus;
 			lsub_positive(&env->imbalance, busiest->idle_cpus);
 		}
-- 
2.43.0

Re: [PATCH 2/2] sched/fair: Balance #Tasks/#CPUs if busiest group has no idle CPU

[K Prateek Nayak]

Hello Pierre,

On 2/5/2026 8:38 PM, Pierre Gondois wrote:
> Halving the imbalance currently lead to the following scenario.
> On a Juno with 2 clusters: CLU0: 4 CPUs and CLU1: 2 CPUs, with
> 6 long running tasks:
> - 1 task on the 2-CPUs cluster
> - 5 Tasks run in the 4-CPUs cluster
> Running the load balancer from the idle CPU (in CLU1):
> - Local group: CLU1: idle_cpus=1; nr_running=1; type=group_has_spare
> - Busiest group: CLU0 idle_cpus=0; nr_running=5 type=group_overloaded
> Half of (local->idle_cpus - busiest->idle_cpus) is 0.
> No task is migrated and the task placement persists.

...

> ---
>  kernel/sched/fair.c | 10 ++++------
>  1 file changed, 4 insertions(+), 6 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index aa14a9982b9f1..9dac3536d9c19 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -11235,20 +11235,18 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
>  			return;
>  		}
>  
> -		if (busiest->group_weight == 1 || sds->prefer_sibling) {
> +		env->migration_type = migrate_task;
> +		if (busiest->group_weight == 1 || sds->prefer_sibling || !busiest->idle_cpus) {

I suppose you also have SD_ASYM_CPUCAPACITY set on your sd which is why
"sds->prefer_sibling" is false here.

Instead of checking for "busiest->idle_cpus", would it make sense to
enter this case for sibling_imbalance() when we have:

    capacity_greater(capacity_of(env->dst_cpu), sds->busiest->sgc->min_capacity)

since it could very well be the case that the smaller cluster is
actually idle since task_fits_cpu() returned false for CPUs there?

I couldn't actually spot any case where we compare the capacities
of local and busiest group for <= fully_loaded but let me know if
I've missed something.

>  			/*
> -			 * When prefer sibling, evenly spread running tasks on
> -			 * groups.
> +			 * When prefer sibling, or when busiest has no idle CPU,
> +			 * evenly spread running tasks on groups.
>  			 */
> -			env->migration_type = migrate_task;
>  			env->imbalance = sibling_imbalance(env, sds, busiest, local);

I'm slightly skeptical of spreading the tasks evenly without considering
the capacity difference when we are on SD_ASYM_CPUCAPACITY. I suppose
we'll filter out the target in sched_balance_find_src_rq() and bail out
if we have only see lower capacity CPUs on the busiest group.

>  		} else {
> -
>  			/*
>  			 * If there is no overload, we just want to even the number of
>  			 * idle CPUs.
>  			 */
> -			env->migration_type = migrate_task;
>  			env->imbalance = local->idle_cpus;
>  			lsub_positive(&env->imbalance, busiest->idle_cpus);
>  		}

-- 
Thanks and Regards,
Prateek

Re: [PATCH 1/2] sched/fair: Fix integer underflow

[K Prateek Nayak]

Hello Pierre,

On 2/5/2026 8:38 PM, Pierre Gondois wrote:
> (struct sg_lb_stats).idle_cpus is of type 'unsigned int'.
> (local->idle_cpus - busiest->idle_cpus) can underflow to UINT_MAX
> for instance, and max_t(long, 0, UINT_MAX) will output UINT_MAX.
> 
> Use lsub_positive() instead of max_t().
> 
> Fixes: 16b0a7a1a0af ("sched/fair: Ensure tasks spreading in LLC during LB")

Should this be commit 0b0695f2b34a ("sched/fair: Rework load_balance()")
since I could spot the max_t usage all the way back to to it?

Apart from that, feel free to include:

Reviewed-by: K Prateek Nayak <kprateek.nayak@amd.com>

> cc: stable@vger.kernel.org
> Signed-off-by: Pierre Gondois <pierre.gondois@arm.com>
> Reviewed-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---
>  kernel/sched/fair.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index da46c31645378..aa14a9982b9f1 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -11249,8 +11249,8 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
>  			 * idle CPUs.
>  			 */
>  			env->migration_type = migrate_task;
> -			env->imbalance = max_t(long, 0,
> -					       (local->idle_cpus - busiest->idle_cpus));
> +			env->imbalance = local->idle_cpus;
> +			lsub_positive(&env->imbalance, busiest->idle_cpus);
>  		}
>  
>  #ifdef CONFIG_NUMA

-- 
Thanks and Regards,
Prateek