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

[Vincent Guittot]

On Thu, 17 Sept 2026 at 17:41, Christian Loehle
<christian.loehle@xxxxxxx> 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 for equal exit latencies, resetting the candidate
> count when a shallower candidate appears. Use the per-CPU scheduler PRNG
> and reciprocal_scale() to avoid variable division or a second scan.
>
> Use a u64 latency key with U64_MAX for unpublished states. Published
> states take precedence; when none are found, sample among the idle CPUs
> without a published state.
>
> Signed-off-by: Christian Loehle <christian.loehle@xxxxxxx>

Reviewed-by: Vincent Guittot <vincent.guittot@xxxxxxxxxx>

> ---
>  kernel/sched/fair.c | 18 ++++++++++++------
>  1 file changed, 12 insertions(+), 6 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index ff5793bddc35..810343f40316 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>
> @@ -8458,7 +8459,8 @@ static int
>  sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
>  {
>         unsigned long load, min_load = ULONG_MAX;
> -       unsigned int min_exit_latency = UINT_MAX;
> +       u64 min_exit_latency = U64_MAX;
> +       unsigned int nr_candidates = 0;
>         int least_loaded_cpu = this_cpu;
>         int shallowest_idle_cpu = -1;
>         int i;
> @@ -8479,12 +8481,16 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
>
>                 if (available_idle_cpu(i)) {
>                         struct cpuidle_state *idle = idle_get_state(rq);
> -                       if (idle && idle->exit_latency < min_exit_latency) {
> -                               min_exit_latency = idle->exit_latency;
> -                               shallowest_idle_cpu = i;
> -                       } else if ((!idle || idle->exit_latency == min_exit_latency) &&
> -                                  shallowest_idle_cpu == -1) {
> +                       u64 exit_latency = idle ? idle->exit_latency : U64_MAX;
> +
> +                       if (shallowest_idle_cpu == -1 || exit_latency < min_exit_latency) {
> +                               min_exit_latency = exit_latency;
>                                 shallowest_idle_cpu = i;
> +                               nr_candidates = 1;
> +                       } else if (exit_latency == min_exit_latency) {
> +                               nr_candidates++;
> +                               if (!reciprocal_scale(sched_rng(), nr_candidates))
> +                                       shallowest_idle_cpu = i;
>                         }
>                 } else if (shallowest_idle_cpu == -1) {
>                         load = cpu_load(cpu_rq(i));
> --
> 2.34.1
>