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

[Qing Wang]

The current NI_RANDOM implementation uses a random dice roll to allow
newidle_balance attempts according to the success rate. This can be
replaced with a Bresenham accumulator.

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

Why Bresenham:
1. It is deterministic and reproducible. For a given ratio, the
   balance frequency is exact and not subject to random variance,
   which makes the behavior predictable when debugging or tracing.
2. Bresenham spaces the attempts evenly; the random dice can go for
   a long stretch without balancing or fire several times in a row,
   especially at low ratios.

A quick simulation where the ratio jumps to a random value in
[0, 1023] every 512 calls (20000 windows):

                      Bresenham      random dice
max per-window error  0.5 attempts   41 attempts

The max per-window error is the max difference between the actual
and expected number of attempts within a window; Bresenham's error
is much smaller.

Signed-off-by: Qing Wang <wangqing7171@xxxxxxxxx>
---
v1: https://lore.kernel.org/all/20260506024455.2799069-1-wangqing7171@xxxxxxxxx/

v2: https://lore.kernel.org/all/20260602054619.637201-1-wangqing7171@xxxxxxxxx/
Removed sched_rnd_state and sched_rng() since they are no longer used.

v3: https://lore.kernel.org/all/20261028034449.2368071-1-wangqing7171@xxxxxxxxx/
Corrected the code comments.

v4:
Recovered sched_rnd_state and sched_rng().

 include/linux/sched/topology.h |  1 +
 kernel/sched/fair.c            | 18 +++++++++++++-----
 kernel/sched/topology.c        |  1 +
 3 files changed, 15 insertions(+), 5 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/fair.c b/kernel/sched/fair.c
index cfc982205b98..b2661448759c 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -14931,16 +14931,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/topology.c b/kernel/sched/topology.c
index 919d0fb00bd9..79c477b47510 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -2002,6 +2002,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