svn commit: r335242 - head/sys/kern

[Bruce Evans]

On Fri, 15 Jun 2018, Gleb Smirnoff wrote:

> Log:
>  Since 'ticks' is an int, it may wrap around and cr_ticks at a certain
>  counter_rate will be greater than ticks, resulting in counter_ratecheck()
>  failure. To fix this take an absolute value of the difference between
>  ticks and cr_ticks.

This only works accidentally, and only half as well as possible.  It is
much easier to see that the normal method to u_int works as well as possible,
esepecially for cases where it doesn't work.

> Modified: head/sys/kern/subr_counter.c
> ==============================================================================
> --- head/sys/kern/subr_counter.c	Fri Jun 15 21:23:03 2018	(r335241)
> +++ head/sys/kern/subr_counter.c	Fri Jun 15 21:36:16 2018	(r335242)
> @@ -140,7 +140,7 @@ counter_ratecheck(struct counter_rate *cr, int64_t lim
> 	val = cr->cr_over;
> 	now = ticks;
>
> -	if (now - cr->cr_ticks >= hz) {
> +	if (abs(now - cr->cr_ticks) >= hz) {
> 		/*
> 		 * Time to clear the structure, we are in the next second.
> 		 * First try unlocked read, and then proceed with atomic.

The normal way writing this is '(u_int)(now - cr->cr_ticks) >= hz'.

Networking code has hundreds of examples of this just in the SEQ_* macros.
The SEQ_*() macros handle signed differences of unsigned sequence numbers.
Sequence numbers that need to be compared must be kept closer together than
their full unsigned range for this to work.

Here we want unsigned difference of (bogusly) signed tick counts, and the
full unsigned range is available, but was not used (giving large bugs).
The tick counts are usually kept close together by resetting cr_ticks
often, but when this function is not called for a long time (~2**31 ticks)
cr_ticks has not been reset, and then the check for resetting it remains
broken for another long time (~2**31 ticks).  Overflow of 'ticks' itself
eventually accidentally fixes the brokenness of the check.  The cycle
repeats every 2**32 ticks.

The only correct (not so quick) ways to fix this are to enlarge tick
counters so that overflow never occurs, or to arrange to call this
function more often (for every counter).  Otherwise, undetectable wrap
occurs whenever the function is not called for 2**32 ticks.  Then further
calls are incorrectly rate-limited for the next second.  With hz = 1000,
this only happens every 49.7 days, so isn't much of a problem.

This commit fixes the larger problem that detectable but undetected overflow
occurs whenever the function is not called for 2**31 ticks.  Then further
calls are incorrectly rate-limited for the next 2**31 ticks,  With hz = 1000,
this gives 24.8 days of brokeness which is too much.

But using abs() only works accidentally.  It gives 2 more intervals of
brokenness every 2**32 ticks.  These intervals happen to be short, so aren't
much of a problem, but understanding this is harder:
- when the unsigned difference (mod 2**32) is INT32_MAX + 1U, the signed
   difference is INT32_MIN.  abs() on this overflows to INT32_MIN.  The
   check misclassifies this and gives another tick of rate limiting every
   cycle.  1 tick of brokenness is not very long.
- when the unsigned difference (mod 2**32) is >= UINT32_MAX - hz and <=
   UINT32_MAX, the signed difference is >= 1 - hz and <= -1.  abs() on this
   gives a value between 1 and hz - 1.  The check misclassifies this and
   gives another tick of rate limiting every cycle.  abs() essentially gives
   a complement of the correct value, and the range here is almost a
   reflection of the range from 2**32 to 2**32 + hz - 1 starting 1 tick
   higher.  1 second (less 1 tick) of brokenness is a bit too long, but we
   already have to put up with 1 second of brokenness after undetectable
   wrap.
- when the unsigned difference (mod 2**32) is >= INT32_MAX + 2U and <
   UINT32_MAX - hz, the value given by abs() happens to be >= hz, so the
   check accidentally does the correct classification.  This fixes most
   broken cases.

Bruce