sched/psi: fix trigger window arithmetic
Subsystems (2)
cover sched/psi: fix trigger window arithmetic
From: Tao Cui <[email protected]>
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 10With 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(-)
Signature · 1 line
2.43.0
PATCH 1/2 sched/psi: fix trigger window growth interpolation for large windows
From: Tao Cui <[email protected]>
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.
--- kernel/sched/psi.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-)
kernel/sched/psi.c +3 -2
@@ -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;
Signature · 1 line
2.43.0
PATCH 2/2 sched/psi: convert trigger window/threshold to ns in u64
In reply to Tao CuiFrom: Tao Cui <[email protected]>
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.
--- kernel/sched/psi.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
kernel/sched/psi.c +2 -2
@@ -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 );
Signature · 1 line
2.43.0
Suren Baghdasaryan
maintainerQuoted 31 lines · Tao Cui
From: Tao Cui <[email protected]>
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_MAXns).1/2
window_update()estimates the stall growth inside a partially-elapsed
window asprev_growth * remaining / size.remainingis a u32 butwin->sizeis a u64 and may be up to 10s (1e10 ns), so for large windows it truncates and the interpolation collapses;prev_growth * remainingcan also overflow u64. Use a u64remainingandmul_u64_u64_div_u64().2/2
psi_trigger_create()scales window/thresholdus->nswith
* NSEC_PER_USEC.NSEC_PER_USECislong, 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
Quoted 3 lines
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.
This looks like a duplicate of the series posted by your collegue at
https://lore.kernel.org/all/[email protected]/
Quoted 11 lines
Tao Cui (2):
sched/psi: fix trigger window growth interpolation for large windows sched/psi: convert trigger window/threshold to ns in u64kernel/sched/psi.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-)--
2.43.0
Quoted 32 lines · Suren Baghdasaryan
Quoted 31 lines · Tao Cui
From: Tao Cui <[email protected]>
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_MAXns).1/2
window_update()estimates the stall growth inside a partially-elapsed
window asprev_growth * remaining / size.remainingis a u32 butwin->sizeis a u64 and may be up to 10s (1e10 ns), so for large windows it truncates and the interpolation collapses;prev_growth * remainingcan also overflow u64. Use a u64remainingandmul_u64_u64_div_u64().2/2
psi_trigger_create()scales window/thresholdus->nswith
* NSEC_PER_USEC.NSEC_PER_USECislong, 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
Quoted 7 lines
Quoted 3 lines
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.
This looks like a duplicate of the series posted by your collegue at
https://lore.kernel.org/all/[email protected]/
Hi Suren,
You're right -- this duplicates Guopeng's series. He and I found this issue together a while back, and his submission already covers it, so I'm withdrawing mine. Sorry for the extra noise.
Thanks,
Tao
Quoted 11 lines
Quoted 11 lines
Tao Cui (2):
sched/psi: fix trigger window growth interpolation for large windows sched/psi: convert trigger window/threshold to ns in u64kernel/sched/psi.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-)--
2.43.0