Compute priority with an intermediate widening to prevent overflow

[jhibbits]

Summary

It's possible to overflow an integer when rounding up a near-UINT_MAX value. To
prevent overflow in this intermediary rounded value, widen the type to hold 33
bits.

[markj]

sys/kern/sched_ule.c

169

Sorry if I'm misunderstanding, but I don't see what this fixes. The cast back to int might truncate the value of roundup(SCHED_TICK_TOTAL(ts), SCHED_PRI_RANGE). If the truncated value is smaller than SCHED_PRI_RANGE, we'll get a divide-by-zero.

[jhibbits]

The cast to int should be of the full result, not just the roundup().

[jhibbits]

sys/kern/sched_ule.c

169

D'oh, this was a manual copy from my internal repo, so missed the parentheses to cast the full result, instead of just the roundup().

[kib]

Perhaps s/33/32/ in the message ? Or am I missing something ?

That said, SCHED_TICK_TOTAL() is already defined as max(ts_ltick-ts_ftick, hz), and max() casts its arguments to u_int. Isn't it too late to cast SCHED_TICK_TOTAL() to uintmax_t ?

[jhibbits]

In D12984#270029, @kib wrote:

Perhaps s/33/32/ in the message ? Or am I missing something ?

Nope, the intermediate type has to hold 33 bits, for the rounding (round up to 2**32), but it gets dropped back down to 32 bits after the divide.

That said, SCHED_TICK_TOTAL() is already defined as max(ts_ltick-ts_ftick, hz), and max() casts its arguments to u_int. Isn't it too late to cast SCHED_TICK_TOTAL() to uintmax_t ?

I debated which would be best, and figured if it overflows as the max() arguments (which would need additional casting), it would return hz, which though possibly not desirable won't panic with a divide by zero.

[markj]

This looks ok to me. I'm not really sure that it's the best way to address the overflow - I think this solution is making assumptions about how roundup() is implemented. I don't have a better suggestion though.

[jhibbits]

Cast the tick difference to uintmax_t earlier on, instead of in the roundup() argument list.

[markj]

In D12984#272210, @jhibbits wrote:

Cast the tick difference to uintmax_t earlier on, instead of in the roundup() argument list.

Taking a step back, the problem occurs when roundup(SCHED_TICK_TOTAL(ts), SCHED_PRI_RANGE) ends up in the interval (-SCHED_PRI_RANGE, SCHED_PRI_RANGE), right? SCHED_TICK_TOTAL(ts) is max(ts->ts_ltick - ts->ts_ftick, hz); note that max()'s return value is an unsigned int. So, to hit the bug, that difference needs to be quite large, i.e., close to INT_MAX.

ftick and ltick are the boundaries of the %CPU sliding window for the thread, and are updated in sched_pctcpu_update(). In particular, that difference ltick - ftick is supposed to be no larger than SCHED_TICK_MAX = 11 * hz. In r314625 I fixed a bug which caused us to stop updating ts_ftick for a thread if it had not run in a long time. So how else are we getting that large difference? Is it possible that your bug is already fixed by the above-mentioned revision?

[jhibbits]

In D12984#274132, @markj wrote:

In D12984#272210, @jhibbits wrote:

Cast the tick difference to uintmax_t earlier on, instead of in the roundup() argument list.

Taking a step back, the problem occurs when roundup(SCHED_TICK_TOTAL(ts), SCHED_PRI_RANGE) ends up in the interval (-SCHED_PRI_RANGE, SCHED_PRI_RANGE), right? SCHED_TICK_TOTAL(ts) is max(ts->ts_ltick - ts->ts_ftick, hz); note that max()'s return value is an unsigned int. So, to hit the bug, that difference needs to be quite large, i.e., close to INT_MAX.

ftick and ltick are the boundaries of the %CPU sliding window for the thread, and are updated in sched_pctcpu_update(). In particular, that difference ltick - ftick is supposed to be no larger than SCHED_TICK_MAX = 11 * hz. In r314625 I fixed a bug which caused us to stop updating ts_ftick for a thread if it had not run in a long time. So how else are we getting that large difference? Is it possible that your bug is already fixed by the above-mentioned revision?

Reviewing the change in r314625, and the code surrounding it, I think r314625 fixes the bug completely, by keeping the ticks within the window. Dropping this as unnecessary now.