From owner-svn-src-all@freebsd.org Mon Feb 11 05:18:03 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 5F86314E8FBB; Mon, 11 Feb 2019 05:18:03 +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 532C383F21; Mon, 11 Feb 2019 05:18:02 +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 1A8A41057C2D; Mon, 11 Feb 2019 16:17:58 +1100 (AEDT) Date: Mon, 11 Feb 2019 16:17:57 +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: <201902102307.x1AN7lj8011617@repo.freebsd.org> Message-ID: <20190211141730.Y1118@besplex.bde.org> References: <201902102307.x1AN7lj8011617@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=FNpr/6gs c=1 sm=1 tr=0 a=PalzARQSbocsUSjMRkwAPg==:117 a=PalzARQSbocsUSjMRkwAPg==:17 a=kj9zAlcOel0A:10 a=8CGCo7kxAAAA:8 a=UhgyTraLAAAA:8 a=AA-rp-4oXAJj9xe1gjMA:9 a=CjuIK1q_8ugA:10 a=uyKDLsAT3yn652Fg1vMC:22 a=WPR-7A3s_xU2s7D-tfWM:22 X-Rspamd-Queue-Id: 532C383F21 X-Spamd-Bar: ------ Authentication-Results: mx1.freebsd.org X-Spamd-Result: default: False [-6.80 / 15.00]; NEURAL_HAM_MEDIUM(-1.00)[-0.996,0]; NEURAL_HAM_SHORT(-0.80)[-0.799,0]; NEURAL_HAM_LONG(-1.00)[-1.000,0]; REPLY(-4.00)[] 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 05:18:03 -0000 On Sun, 10 Feb 2019, Conrad Meyer wrote: > Log: > Prevent overflow for usertime/systime in caclru1 > > PR: 76972 and duplicates > Reported by: Dr. Christopher Landauer , > Steinar Haug > Submitted by: Andrey Zonov (earlier version) > MFC after: 2 weeks kib asked me to fix this a couple of days ago. I wrote a much better version, following the hints in my review of PR 76972. > Modified: head/sys/kern/kern_resource.c > ============================================================================== > --- head/sys/kern/kern_resource.c Sun Feb 10 22:33:41 2019 (r343984) > +++ head/sys/kern/kern_resource.c Sun Feb 10 23:07:46 2019 (r343985) > @@ -863,6 +863,15 @@ rufetchtd(struct thread *td, struct rusage *ru) > calcru1(p, &td->td_rux, &ru->ru_utime, &ru->ru_stime); > } > > +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; + } This does 2 32-bit divisions in the usual case, and 1 64-bit divmod and 2 64-bit divs in the slow case. The second clause is directly from Landauer's version. The a = b * q + r method is much easier to understand when written using assignments to variables named q and r. The first clause is from Landauer's version with less magic numbers. I over-optimized it a little and am going to remove the casts. They are only a small optimization for the 32-bit case, and compilers can do them anyway, and the 32-bit udiv/mod libcalls can get closer to doing them. I wrote further fixes and optimizations: - restore the invariant that user + sys time doesn't exceed total time - restore monotonicity of interrupt time (this implies the previous invariant) - merge interrupt time into sys time and make interrupt time 0. Everything becomes simpler and faster and less buggy. - optimize udiv/mod for usec to timeval conversions. Interrupt times became worse than useless with ithreads in SMPng. Sys time for ithreads gives a much better place to record interrupt time than scattered interrupt times in all threads. Interrupt times are now stored in all threads indirectly as tu - uu - su. They are always 0 for non-ithreads, except for bugs. One of the bugs is that rounding down uu and su makes the indirect interrupt time tu - uu - su often 1 (usec) instead of 0. Versions without bugs in invariants and monotonictity had to do complicated adjustments on many later calls to preserve this value as 1. Versions with these bugs have a sticky off-by-1 error instead. I thought that I might have written this overflow bug, but actually it was in 4.4BSD-Lite and I didn't notice it when I cleaned that up. Lite2 does: XX u = sec * 1000000 + usec; XX st = (u * st) / tot; XX [... similarly for other 2 times] Overflow here. The 64-bit tick counters are useless except for them not needing upcasts here, since they although they don't overflow for billions of years, calculations like this overflow after 108 hours. FreeBSD-1 (Net/2?) doesn't have this problem, since it maintains the times as timevals (very inaccurately but obviously monotonically by incrementing the times in hardclock()). It has lots of overflow bugs 248 days from using signed int tick counters and hz = 100. Bruce