sched/psi: Fix trigger time arithmetic
Subsystems (2)
cover sched/psi: Fix trigger time arithmetic
From: Guopeng Zhang <[email protected]>
PSI trigger time handling has two integer-width bugs. Long windows can be truncated during growth interpolation, and the multiplication used for the interpolation can overflow before the division. Separately, the microsecond-to-nanosecond conversion can wrap on 32-bit systems before the result is stored in a u64.
Fix the two issues independently.
Guopeng Zhang (2):
sched/psi: Fix long-window growth interpolation sched/psi: Fix overflow in trigger time conversion on 32-bit
kernel/sched/psi.c | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-)
base-commit: 1a1757b76427f6201bfe0bf1bea9f7574f332a93
Signature · 1 line
2.43.0
PATCH 1/2 sched/psi: Fix long-window growth interpolation
From: Guopeng Zhang <[email protected]>
PSI trigger windows are stored in nanoseconds and can be up to 10 seconds, but window_update() stores the remaining interval in a u32. For example, after 2 seconds have elapsed in a 10-second window, the remaining 8,000,000,000 ns is truncated to 3,705,032,704 ns.
Making remaining a u64 avoids the truncation, but the multiplication can still overflow before the division. Both win->prev_growth and remaining can be close to 10,000,000,000, so their product can exceed U64_MAX.
Store the remaining interval in a u64 and use mul_u64_u64_div_u64() to calculate the interpolation without overflowing the intermediate product.
--- kernel/sched/psi.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)
kernel/sched/psi.c +4 -2
@@ -137,6 +137,7 @@* sampling of the aggregate task states would be. */ #include <linux/sched/clock.h> +#include <linux/math64.h> #include <linux/workqueue.h> #include <linux/psi.h> #include "sched.h"
@@ -451,10 +452,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: Fix overflow in trigger time conversion on 32-bit
In reply to Guopeng ZhangFrom: Guopeng Zhang <[email protected]>
threshold_us and window_us are u32, while NSEC_PER_USEC is 1000L. On 32-bit architectures, multiplication by NSEC_PER_USEC is evaluated using 32-bit unsigned arithmetic and can wrap before the result is assigned to the u64 trigger fields.
For a valid 4,000,000 us threshold and 6,000,000 us window, the threshold is stored as 4,000,000,000 ns, while the window wraps to 1,705,032,704 ns. The stored window is therefore shorter than the threshold, so the trigger no longer monitors the requested 4-second threshold over a 6-second window.
Cast both values to u64 before the multiplication so that the conversion to nanoseconds is performed using 64-bit arithmetic.
--- kernel/sched/psi.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
kernel/sched/psi.c +2 -2
@@ -1391,8 +1391,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
Re: [PATCH 1/2] sched/psi: Fix long-window growth interpolation
In reply to Guopeng ZhangQuoted 13 lines · Guopeng Zhang
From: Guopeng Zhang <[email protected]>
PSI trigger windows are stored in nanoseconds and can be up to 10 seconds, but
window_update()stores the remaining interval in a u32. For example, after 2 seconds have elapsed in a 10-second window, the remaining 8,000,000,000 ns is truncated to 3,705,032,704 ns.Making remaining a u64 avoids the truncation, but the multiplication can still overflow before the division. Both
win->prev_growthand remaining can be close to 10,000,000,000, so their product can exceedU64_MAX.
Quoted 6 lines
Store the remaining interval in a u64 and use
mul_u64_u64_div_u64()to calculate the interpolation without overflowing the intermediate product.Fixes 0e94682b73bf ("psi: introduce psi monitor")Signed-off-by Guopeng Zhang <[email protected]>
Sorry for the delay in reviewing these fixes. The fix looks correct to me.
Quoted 32 lines
--- kernel/sched/psi.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)kernel/sched/psi.c +4
-3@@ -137,6 +137,7 @@* sampling of the aggregate task states would be. */ #include <linux/sched/clock.h> +#include <linux/math64.h> #include <linux/workqueue.h> #include <linux/psi.h> #include "sched.h" @@ -451,10 +452,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
Re: [PATCH 2/2] sched/psi: Fix overflow in trigger time conversion on 32-bit
In reply to Guopeng ZhangQuoted 14 lines · Guopeng Zhang
From: Guopeng Zhang <[email protected]>
threshold_usandwindow_usare u32, whileNSEC_PER_USECis 1000L. On 32-bit architectures, multiplication byNSEC_PER_USECis evaluated using 32-bit unsigned arithmetic and can wrap before the result is assigned to the u64 trigger fields.For a valid 4,000,000 us threshold and 6,000,000 us window, the threshold is stored as 4,000,000,000 ns, while the window wraps to 1,705,032,704 ns. The stored window is therefore shorter than the threshold, so the trigger no longer monitors the requested 4-second threshold over a 6-second window.
Quoted 5 lines
Cast both values to u64 before the multiplication so that the conversion to nanoseconds is performed using 64-bit arithmetic.
Fixes 0e94682b73bf ("psi: introduce psi monitor")Signed-off-by Guopeng Zhang <[email protected]>
Quoted 21 lines
--- kernel/sched/psi.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)kernel/sched/psi.c +2
-3@@ -1391,8 +1391,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
Re: [PATCH 1/2] sched/psi: Fix long-window growth interpolation
In reply to Guopeng ZhangFrom: Tao Cui <[email protected]>
Quoted 13 lines · Guopeng Zhang
From: Guopeng Zhang <[email protected]>
PSI trigger windows are stored in nanoseconds and can be up to 10 seconds, but
window_update()stores the remaining interval in a u32. For example, after 2 seconds have elapsed in a 10-second window, the remaining 8,000,000,000 ns is truncated to 3,705,032,704 ns.Making remaining a u64 avoids the truncation, but the multiplication can still overflow before the division. Both
win->prev_growthand remaining can be close to 10,000,000,000, so their product can exceedU64_MAX.
Quoted 6 lines
Store the remaining interval in a u64 and use
mul_u64_u64_div_u64()to calculate the interpolation without overflowing the intermediate product.Fixes 0e94682b73bf ("psi: introduce psi monitor")Signed-off-by Guopeng Zhang <[email protected]>
Re: [PATCH 2/2] sched/psi: Fix overflow in trigger time conversion on 32-bit
In reply to Guopeng ZhangFrom: Tao Cui <[email protected]>
Quoted 14 lines · Guopeng Zhang
From: Guopeng Zhang <[email protected]>
threshold_usandwindow_usare u32, whileNSEC_PER_USECis 1000L. On 32-bit architectures, multiplication byNSEC_PER_USECis evaluated using 32-bit unsigned arithmetic and can wrap before the result is assigned to the u64 trigger fields.For a valid 4,000,000 us threshold and 6,000,000 us window, the threshold is stored as 4,000,000,000 ns, while the window wraps to 1,705,032,704 ns. The stored window is therefore shorter than the threshold, so the trigger no longer monitors the requested 4-second threshold over a 6-second window.
Quoted 5 lines
Cast both values to u64 before the multiplication so that the conversion to nanoseconds is performed using 64-bit arithmetic.
Fixes 0e94682b73bf ("psi: introduce psi monitor")Signed-off-by Guopeng Zhang <[email protected]>