[PATCH v3] sched/fair: Replace random newidle_balance with Bresenham accumulator

[Qing Wang <wangqing7171@gmail.com>]

The current NI_RANDOM implementation uses a random dice roll to allow
newidle_balance attempts according to the success rate. There is a better
way to implement it.

Replace the random dice with a Bresenham accumulator that distributes the
allowed attempts uniformly across a 1024-step window:

Each step does the following:
  - Accumulate (1 + newidle_ratio) into newidle_window_pos.
  - If the accumulator reaches 1024, allow the balance attempt and
    subtract 1024.

This guarantees exactly (1 + newidle_ratio) newidle_balance operations per
1024 steps, uniformly spaced for any ratio in [0, 1023].

Tested-by: K Prateek Nayak <kprateek.nayak@amd.com>
Signed-off-by: Qing Wang <wangqing7171@gmail.com>
---
v2:
Removed sched_rnd_state and sched_rng() since they are no longer used.

v3:
Corrected the code comments.

Performance testing results from Prateek using tbench
(most sensitive workload for newidle balance):

    Clients:        tip                  bresenham_accm
        1      321.65 (0.00 pct)       313.97 (-2.38 pct)
        2      641.92 (0.00 pct)       638.74 (-0.49 pct)
        4     1245.65 (0.00 pct)      1237.26 (-0.67 pct)
        8     2435.80 (0.00 pct)      2442.23 ( 0.26 pct)
       16     4717.66 (0.00 pct)      4688.19 (-0.62 pct)
       32     9303.53 (0.00 pct)      9390.71 ( 0.93 pct)
       64    18002.57 (0.00 pct)     17911.56 (-0.50 pct)
      128    27729.26 (0.00 pct)     27621.95 (-0.38 pct)
      256    47134.77 (0.00 pct)     46137.36 (-2.11 pct)
      512    43179.41 (0.00 pct)     43277.53 ( 0.22 pct)
     1024    40339.30 (0.00 pct)     40176.49 (-0.40 pct)

The %diff is within the noise range, indicating no performance regression.


 include/linux/sched/topology.h |  1 +
 kernel/sched/core.c            |  3 ---
 kernel/sched/fair.c            | 19 ++++++++++++++-----
 kernel/sched/sched.h           |  6 ------
 kernel/sched/topology.c        |  1 +
 5 files changed, 16 insertions(+), 14 deletions(-)

diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
index f96812d71c51..e951d6f3fb0d 100644
--- a/include/linux/sched/topology.h
+++ b/include/linux/sched/topology.h
@@ -113,6 +113,7 @@ struct sched_domain {
 	unsigned int newidle_call;
 	unsigned int newidle_success;
 	unsigned int newidle_ratio;
+	unsigned int newidle_window_pos;
 	u64 newidle_stamp;
 	u64 max_newidle_lb_cost;
 	unsigned long last_decay_max_lb_cost;
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 1754d9f95f2c..4d764e68897c 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -128,7 +128,6 @@ EXPORT_TRACEPOINT_SYMBOL_GPL(sched_dl_server_start_tp);
 EXPORT_TRACEPOINT_SYMBOL_GPL(sched_dl_server_stop_tp);
 
 DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
-DEFINE_PER_CPU(struct rnd_state, sched_rnd_state);
 
 #ifdef CONFIG_SCHED_PROXY_EXEC
 DEFINE_STATIC_KEY_TRUE(__sched_proxy_exec);
@@ -8927,8 +8926,6 @@ void __init sched_init_smp(void)
 {
 	sched_init_numa(NUMA_NO_NODE);
 
-	prandom_init_once(&sched_rnd_state);
-
 	/*
 	 * There's no userspace yet to cause hotplug operations; hence all the
 	 * CPU masks are stable and all blatant races in the below code cannot
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 0f2364479f9d..172c4b53c11a 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -14198,6 +14198,7 @@ static inline void update_newidle_stats(struct sched_domain *sd, unsigned int su
 		ratio += sd->newidle_success;
 
 		sd->newidle_ratio = min(1024, ratio);
+		sd->newidle_window_pos = 0;
 		sd->newidle_call /= 2;
 		sd->newidle_success /= 2;
 	}
@@ -14928,16 +14929,24 @@ static int sched_balance_newidle(struct rq *this_rq, struct rq_flags *rf)
 
 			if (sched_feat(NI_RANDOM) && sd->newidle_ratio < 1024) {
 				/*
-				 * Throw a 1k sided dice; and only run
-				 * newidle_balance according to the success
-				 * rate.
+				 * Bresenham's line algorithm based accumulator
+				 *
+				 * At each invocation, the ratio is added to an
+				 * accumulator. A balance is triggered whenever
+				 * the sum >= 1024.
+				 *
+				 * This guarantees exactly 'ratio' balance
+				 * operations per 1024 calls, distributing them
+				 * as uniformly as possible across the interval.
 				 */
-				u32 d1k = sched_rng() % 1024;
 				weight = 1 + sd->newidle_ratio;
-				if (d1k > weight) {
+
+				sd->newidle_window_pos += weight;
+				if (sd->newidle_window_pos < 1024) {
 					update_newidle_stats(sd, 0);
 					continue;
 				}
+				sd->newidle_window_pos -= 1024;
 				weight = (1024 + weight/2) / weight;
 			}
 
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 4c25fbe84fb5..210aa35b5720 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1424,12 +1424,6 @@ static inline bool is_migration_disabled(struct task_struct *p)
 }
 
 DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
-DECLARE_PER_CPU(struct rnd_state, sched_rnd_state);
-
-static inline u32 sched_rng(void)
-{
-	return prandom_u32_state(this_cpu_ptr(&sched_rnd_state));
-}
 
 static __always_inline struct rq *__this_rq(void)
 {
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 3dab0253976f..8cc5315a6945 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -1984,6 +1984,7 @@ sd_init(struct sched_domain_topology_level *tl,
 		.newidle_call		= 512,
 		.newidle_success	= 256,
 		.newidle_ratio		= 512,
+		.newidle_window_pos	= 0,
 		.newidle_stamp		= now,
 
 		.max_newidle_lb_cost	= 0,
-- 
2.34.1