From owner-svn-src-all@freebsd.org Sat Jun 16 05:39:39 2018 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 940A6100A89B; Sat, 16 Jun 2018 05:39:39 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from mail108.syd.optusnet.com.au (mail108.syd.optusnet.com.au [211.29.132.59]) by mx1.freebsd.org (Postfix) with ESMTP id 9E75374F95; Sat, 16 Jun 2018 05:39:38 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from [192.168.0.102] (c110-21-101-228.carlnfd1.nsw.optusnet.com.au [110.21.101.228]) by mail108.syd.optusnet.com.au (Postfix) with ESMTPS id A2E1D1A087B; Sat, 16 Jun 2018 15:39:27 +1000 (AEST) Date: Sat, 16 Jun 2018 15:39:24 +1000 (EST) From: Bruce Evans X-X-Sender: bde@besplex.bde.org To: Gleb Smirnoff cc: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: Re: svn commit: r335242 - head/sys/kern In-Reply-To: <201806152136.w5FLaGCP074334@repo.freebsd.org> Message-ID: <20180616123220.K976@besplex.bde.org> References: <201806152136.w5FLaGCP074334@repo.freebsd.org> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Optus-CM-Score: 0 X-Optus-CM-Analysis: v=2.2 cv=cIaQihWN c=1 sm=1 tr=0 a=PalzARQSbocsUSjMRkwAPg==:117 a=PalzARQSbocsUSjMRkwAPg==:17 a=kj9zAlcOel0A:10 a=H_4jZ2QBzDgs3DYR_ncA:9 a=CjuIK1q_8ugA:10 X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.26 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 16 Jun 2018 05:39:39 -0000 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