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

[Christian Loehle]

On 9/17/26 16:08, Vincent Guittot wrote:
> On Thu, 17 Sept 2026 at 16:22, Christian Loehle
> <christian.loehle@xxxxxxx> wrote:
>>
>> On 9/17/26 15:08, Vincent Guittot wrote:
>>> On Wed, 16 Sept 2026 at 12:01, 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 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@xxxxxxx>
>>>> ---
>>>>  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;
>>>
>>> You clear the number of candidate when you find a lower exit_latency
>>> but !idle CPUs that have already been checked will be cleared whereas
>>> they still get a chance if they are checked later.
>> That is correct. Is this a problem?
> 
> I would say we should try to be consistent

Ack

> 
>> (Again, mirroring what upstream currently does, let's say exit_latency(CPU0)=100, exit_latency(CPU2)=1
>> !idle at CPU3 trumps CPU2 (assuming recent idle_stamp), !idle at CPU1 doesn't trump CPU2, i.e.
>> the inconsistency around !idle is already there?)
> 
> Fair enough but the idle_stamp was also in the party
> 
>> And I'm assuming we really don't wanna keep a cpumask of !idle CPUs, if anything we may just ignore
>> them completely, given how unlikely it they are to be observed.
> 
> We must keep them when there is no cpuidle driver, i.e. until we find
> a CPU with an idle state

Alright let me make a it a U64_MAX reservoir.
Thanks for reviewing Vincent!