[PATCH 0/2] sched/psi: fix trigger window arithmetic

[PATCH 0/2] sched/psi: fix trigger window arithmetic

[Tao Cui]

From: Tao Cui <cuitao@kylinos.cn>

Two narrow numeric bugs in the PSI trigger-window arithmetic, both from
the original psi monitor (0e94682b73bf) and both only visible for trigger
windows larger than ~4.29s (UINT32_MAX ns).

1/2 window_update() estimates the stall growth inside a partially-elapsed
   window as `prev_growth * remaining / size`.  `remaining` is a u32 but
   win->size is a u64 and may be up to 10s (1e10 ns), so for large windows
   it truncates and the interpolation collapses; `prev_growth * remaining`
   can also overflow u64.  Use a u64 `remaining` and mul_u64_u64_div_u64().

2/2 psi_trigger_create() scales window/threshold us->ns with
   `* NSEC_PER_USEC`.  NSEC_PER_USEC is `long`, so on 32-bit the multiply
   wraps for multi-second windows (a 10s window is stored as ~1.41s).
   Cast to u64 first.

Neither path is the scheduler hot path (update_triggers() runs at
trigger-evaluation rate), and small-window triggers are numerically
unchanged.

Demo of 1/2 -- 10s window, previous window was 100% stall, polled each
1s, trigger "some 5s 10s".  Estimated growth (seconds) inside the window:

    elapsed  current(u32)  fixed(u64)
    1        1             10
    2        2             10
    3        3             10
    4        5             10

With the current code the trigger waits for the actual stall to reach the
5s threshold (~4s in) instead of firing once the run-rate predicts it
(~1s in): a ~3s delay on the first window of a stall.

Tao Cui (2):
  sched/psi: fix trigger window growth interpolation for large windows
  sched/psi: convert trigger window/threshold to ns in u64

 kernel/sched/psi.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

-- 
2.43.0

[PATCH 1/2] sched/psi: fix trigger window growth interpolation for large windows

[Tao Cui]

From: Tao Cui <cuitao@kylinos.cn>

window_update() estimates the stall growth inside a partially elapsed
trigger window as

    growth += win->prev_growth * remaining / win->size

with `remaining = win->size - elapsed`.  The local `remaining` is a u32,
but win->size is a u64 and may be as large as WINDOW_MAX_US (10s = 10^10
ns), which exceeds UINT32_MAX (~4.29s).  For trigger windows larger than
~4.29s the assignment truncates `remaining`, the linear interpolation
collapses, and growth is heavily underestimated.

For a 10s window polled once per second with prev_growth equal to a full
window of stall, the estimate one second in is ~1.4s instead of 10s.  A
trigger configured as "some 5s 10s" then waits until the actual stall
reaches the threshold (~4s in) instead of firing as soon as the run-rate
predicts it (~1s in): a multi-second delay on the first window of a
stall.

Use a u64 `remaining` and mul_u64_u64_div_u64() for the product, which
also avoids the u64 overflow of `prev_growth * remaining` under heavy
pressure.  This runs in update_triggers() at trigger-evaluation rate (at
most a few times per second), not the scheduler hot path, so the helper's
cost is immaterial.

Fixes: 0e94682b73bf ("psi: introduce psi monitor")
Signed-off-by: Tao Cui <cuitao@kylinos.cn>
---
 kernel/sched/psi.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/psi.c b/kernel/sched/psi.c
index 4e152410653d..6514b44222cf 100644
--- a/kernel/sched/psi.c
+++ b/kernel/sched/psi.c
@@ -451,10 +451,11 @@ static u64 window_update(struct psi_window *win, u64 now, u64 value)
 	if (elapsed > win->size)
 		window_reset(win, now, value, growth);
 	else {
-		u32 remaining;
+		u64 remaining;
 
 		remaining = win->size - elapsed;
-		growth += div64_u64(win->prev_growth * remaining, win->size);
+		growth += mul_u64_u64_div_u64(win->prev_growth, remaining,
+					      win->size);
 	}
 
 	return growth;
-- 
2.43.0

[PATCH 2/2] sched/psi: convert trigger window/threshold to ns in u64

[Tao Cui]

From: Tao Cui <cuitao@kylinos.cn>

psi_trigger_create() scales the trigger threshold and window from
microseconds to nanoseconds as

    t->threshold = threshold_us * NSEC_PER_USEC;
    t->win.size  = window_us   * NSEC_PER_USEC;

NSEC_PER_USEC is 1000L, so on 32-bit the multiply is done in 32 bits and
wraps for windows larger than ~4.29s (WINDOW_MAX_US is 10s): a 10s window
is stored as ~1.41s and the trigger fires much too eagerly.  Cast to u64
before multiplying.

Fixes: 0e94682b73bf ("psi: introduce psi monitor")
Signed-off-by: Tao Cui <cuitao@kylinos.cn>
---
 kernel/sched/psi.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/psi.c b/kernel/sched/psi.c
index 6514b44222cf..7fbe9b94fafa 100644
--- a/kernel/sched/psi.c
+++ b/kernel/sched/psi.c
@@ -1390,8 +1390,8 @@ struct psi_trigger *psi_trigger_create(struct psi_group *group, char *buf,
 
 	t->group = group;
 	t->state = state;
-	t->threshold = threshold_us * NSEC_PER_USEC;
-	t->win.size = window_us * NSEC_PER_USEC;
+	t->threshold = (u64)threshold_us * NSEC_PER_USEC;
+	t->win.size = (u64)window_us * NSEC_PER_USEC;
 	window_reset(&t->win, sched_clock(),
 			group->total[PSI_POLL][t->state], 0);
 
-- 
2.43.0