From owner-svn-src-all@freebsd.org Mon Feb 11 12:08:26 2019 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 A835814D4E09; Mon, 11 Feb 2019 12:08:26 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from mail105.syd.optusnet.com.au (mail105.syd.optusnet.com.au [211.29.132.249]) by mx1.freebsd.org (Postfix) with ESMTP id 136C96AA76; Mon, 11 Feb 2019 12:08:25 +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 mail105.syd.optusnet.com.au (Postfix) with ESMTPS id B7BE0105A556; Mon, 11 Feb 2019 23:08:23 +1100 (AEDT) Date: Mon, 11 Feb 2019 23:08:22 +1100 (EST) From: Bruce Evans X-X-Sender: bde@besplex.bde.org To: Conrad Meyer cc: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: Re: svn commit: r343985 - head/sys/kern In-Reply-To: <20190211141730.Y1118@besplex.bde.org> Message-ID: <20190211224150.R4018@besplex.bde.org> References: <201902102307.x1AN7lj8011617@repo.freebsd.org> <20190211141730.Y1118@besplex.bde.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=P6RKvmIu c=1 sm=1 tr=0 a=PalzARQSbocsUSjMRkwAPg==:117 a=PalzARQSbocsUSjMRkwAPg==:17 a=kj9zAlcOel0A:10 a=20bWB6JnHn-25NKUEkgA:9 a=CjuIK1q_8ugA:10 X-Rspamd-Queue-Id: 136C96AA76 X-Spamd-Bar: ------ Authentication-Results: mx1.freebsd.org X-Spamd-Result: default: False [-6.94 / 15.00]; NEURAL_HAM_MEDIUM(-1.00)[-0.997,0]; NEURAL_HAM_SHORT(-0.94)[-0.942,0]; REPLY(-4.00)[]; NEURAL_HAM_LONG(-1.00)[-1.000,0] X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.29 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: Mon, 11 Feb 2019 12:08:26 -0000 On Mon, 11 Feb 2019, Bruce Evans wrote: > On Sun, 10 Feb 2019, Conrad Meyer wrote: > >> Log: >> Prevent overflow for usertime/systime in caclru1 >> ... >> +static uint64_t >> +mul64_by_fraction(uint64_t a, uint64_t b, uint64_t c) >> +{ >> + /* >> + * Compute floor(a * (b / c)) without overflowing, (b / c) <= 1.0. >> + */ >> + return ((a / c) * b + (a % c) * (b / c) + (a % c) * (b % c) / c); >> +} >> + > > This is the slowest correct fix in the PR followup. kib predicted > that I wouldn't like it. It does 2 64-bit divmods (after optimization) > and many multiplications per call. Times 2 calls. clang will probably > inline this, giving only 3 64-bit divmods instead of 4. > > Better version: > > + /* > + * Subdivide tu. Combine avoiding overflow with reduction to 32-bit > + * operands in the multiplications in the usual case of tu <= > + * UINT32_MAX usec = 4294 seconds. > + */ > + if (__predict_true(tu <= UINT32_MAX && tt <= UINT32_MAX)) { > + uu = ((uint64_t)(uint32_t)tu * (uint32_t)ut) / tt; > + su = ((uint64_t)(uint32_t)tu * (uint32_t)st) / tt; > + } else { > + q = tu / tt; > + r = tu % tt; > + uu = q * ut + (r * ut) / tt; > + su = q * st + (r * st) / tt; > + } I didn't keep the part of your reply to my reply above where you said that you tested over a number of years. I also tested over fake years in a running kernel using a fake cpu_tick freqency of 100000 times smaller. Now I see that all versions still overflow after 388 days with stathz = 128 when tt exceeds UINT32_MAX. Then r can be 1 less than tt, and ut and st can be the same as tt, so one operation is like sqaring tt which overflows when tt is 1 more than UINT32_MAX. There is a PR or 2 about this 388-day limit. I knew about it before I knew about the 105-hour limit fixed in this commit.( Uptimes of a few years are not preposterous, and cpu_idle threads usually have system time of nearly the uptime, so the overflow occurs on most systems after they have been up for 388 days. I'm trying a fix with tt and r divided by 16 in some places. This should work for 17 years with stathz = 128. The thread runtime is more than 388 days when this occurs, so no one would care about differences of even a few days but losing precision in the seconds and microseconds parts is not so good. Bruce