Re: [PATCH 2/2] sched/fair: Randomize equally shallow slow-path candidates

[Christian Loehle <christian.loehle@arm.com>]

On 9/16/26 11:01, Christian Loehle wrote:
> Picking the first eligible idle CPU leaves a scan-order bias. Concurrent
> slow-path selectors can choose the same CPU before either task is enqueued.
> 
> Use reservoir sampling in the tie branch, resetting the candidate count
> when a lower advertised exit latency is found. Use the per-CPU scheduler
> PRNG and reciprocal_scale() to avoid variable division or a second scan.
> 
> This reduces deterministic convergence without reserving the chosen CPU.
> 
> Signed-off-by: Christian Loehle <christian.loehle@arm.com>
> ---
>  kernel/sched/fair.c | 11 ++++++++---
>  1 file changed, 8 insertions(+), 3 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index ff5793bddc35..6836a8364440 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -24,6 +24,7 @@
>  #include <linux/mmap_lock.h>
>  #include <linux/hugetlb_inline.h>
>  #include <linux/jiffies.h>
> +#include <linux/math.h>
>  #include <linux/mm_api.h>
>  #include <linux/highmem.h>
>  #include <linux/hrtimer.h>
> @@ -8459,6 +8460,7 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
>  {
>  	unsigned long load, min_load = ULONG_MAX;
>  	unsigned int min_exit_latency = UINT_MAX;
> +	unsigned int nr_candidates = 0;
>  	int least_loaded_cpu = this_cpu;
>  	int shallowest_idle_cpu = -1;
>  	int i;
> @@ -8482,9 +8484,12 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
>  			if (idle && idle->exit_latency < min_exit_latency) {
>  				min_exit_latency = idle->exit_latency;
>  				shallowest_idle_cpu = i;
> +				nr_candidates = 1;
> -			} else if ((!idle || idle->exit_latency == min_exit_latency) &&
> -				   shallowest_idle_cpu == -1) {
> -				shallowest_idle_cpu = i;
> +			} else if (!idle || idle->exit_latency == min_exit_latency) {


Sashiko:
"Can this branch cause the CPU picker to replace an optimal idle CPU with
a non-idle CPU?
In sched_balance_find_dst_group_cpu(), if a !idle CPU is scanned after an
idle CPU has already been found, min_exit_latency will be < UINT_MAX.
However, the condition !idle || idle->exit_latency == min_exit_latency
unconditionally evaluates to true for !idle CPUs.
This allows the !idle CPU to increment nr_candidates and enter the
reservoir, treating its unknown latency as a tie with the optimal known
latency. It then has a 1/nr_candidates chance to overwrite the optimal
shallowest_idle_cpu choice.
Doesn't this reintroduce a scan-order bias during normal load balancing where
non-idle CPUs can replace optimal idle CPUs just because they appear later
in the scan?"

Disagree, this is in the if block of if (available_idle_cpu(i)), so except for
the obvious race which is deliberately taken in the original code too, this
can't be right?

> +				nr_candidates++;
> +				if (nr_candidates == 1 ||
> +				    !reciprocal_scale(sched_rng(), nr_candidates))
> +					shallowest_idle_cpu = i;
>  			}
>  		} else if (shallowest_idle_cpu == -1) {
>  			load = cpu_load(cpu_rq(i));