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

[Christian Loehle]

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;
-			} 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) {
+				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));
-- 
2.34.1