Summary:  [kernel] [patch] 64bit integer overflow computing user cpu time in calcru() in kern_resource.c  

Product:  Base System  Reporter:  cal <cal>  
Component:  kern  Assignee:  Conrad Meyer <cem>  
Status:  Closed FIXED  
Severity:  Affects Only Me  CC:  acid, ben, emaste, kees, pi, sthaug  
Priority:  Normal  Keywords:  patch, patchready  
Version:  unspecified  
Hardware:  Any  
OS:  Any  
See Also:  https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=227689  
Attachments: 

Description
cal
20050201 17:30:17 UTC
On Tue, 1 Feb 2005, Chris Landauer wrote: > >Description: > in FreeBSD 5.1RELEASE (and 5.2.1R, and 5.3R, and 4.10R), in file > /usr/src/sys/kern/kern_resource.c, lines 657750 define a function calcru() > ("calculate resource usage"), and there is a bug in that function  line 713 > in that file is > > uu = (tu * ut) / tt; > > which is trying to compute user cpu time (uu) as a proportion (since ut<=tt) > of total cpu time (tu), based on the fraction of statclock ticks (ut / tt) > that occur in user time  the problem is that for my application, the values > of tt and ut (which are counts of statclock ticks) are very large and the > value of the intermediate product overflows, even with 64bit arithmetic, > leading to incorrect values (i reported the symptoms to freebsdhackers and a > very helpful description and localization of the problem to calcru() was > provided by peter jeremy, who also wrote that it is a very old problem, but > only partly known because it is so rarely encountered) PR 17842 is about this too. It has the 105 hours magic number but otherwise less detail, so I superseded it by this PR. > >Fix: > <mostly> > ... > this problem can be fixed (more completely) by replacing those same lines with > the following lines: > > /* Subdivide tu. be careful of overflow */ > /* we know 0 <= st, it, ut <= tt and 1 <= tt = st+it+ut */ > #define TOOBIG 48592008 /* 2^35 * sqrt(2) / 10^3 */ > if (tt >= TOOBIG && tu >= tt) > { > u_int64_t q, r; > q = tu / tt; > r = tu % tt; > su = (q * st) + (r * st) / tt; > iu = (q * it) + (r * it) / tt; > } > else { > su = (tu * st) / tt; > iu = (tu * it) / tt; > } > uu = tu  (su + iu); Seems basically OK. > the constant TOOBIG is designed so the calcru() function does not use the > complicated form of the equations when the numbers are guaranteed to be small > enough not to overflow in the intermediate products I think you should use 2^32 for TOOBIG so that the only assumption on stathz is that it is <= 10^6. 2^32 microseconds is a bit over an hour and most programs won't run that long. The tu >= tt check is automatically satisfied if stathz <= 10^6 (less epsilon?), but it is reasonable to check that both terms of the multiplication are < 2^32. You can even make the fix have negative inefficiency for the usual case on 32bit machines by casting the terms down to uint32_t when they are < 2^32. For i386's in particular, 32x32>64 bit multiplication is a single instruction and gcc would use it if the terms were uint32_t. > ... > my assumptions for the analysis are as follows (if any of them is incorrect, > please tell me): > tu is total time in microseconds > tt is total 128hz ticks (tt = ut + st + it) > st is system 128hz ticks > it is interrupt 128hz ticks > ut is user 128hz ticks > i assume that all of these counters are nonnegative and increasing throughout > the life of the process  > i assume therefore that (i use "~" to mean "very roughly near") > tu ~ tt * 10^6/128 > strictly because of the clock rates (machines with other kinds of clock rate > ratios will need a different analysis, but the same kind of idea should work > there, too, possibly with different constant values for TOOBIG)  Seems OK. stathz is machinedependent  better avoid tricky assumptions about it (see above). It seems to be the same as hz on sparc64's, so it might be much larger than 128 (however, the scheduler depends on it being about 128). > for long programs (that is, programs that take more than 388 days or so of > either system or interrupt cpu time), this change may not help, and will > certainly not help after long enough, as shown in the analysis Hmm, 388 days is 2^32 statclock ticks at 128Hz and the limit of 2^32 is sort of new. BTW, I've always thought it stupid that it is stupid for the tick counters to be 64 bits. Values larger than 2^32 in them never came close to actually working, since overflow occurs in the multiplication by a factor of (388 days) / (105 hours) sooner than 32bit counters would overflow. The counters are only (?) used by calcru(), so their 64bitness is not useful anywhere. Bruce Hi, I stepped on this sometime ago. I suggest simple patch that fixed problem for me. $ ps o lstart,time,systime,usertime p 63292 STARTED TIME SYSTIME USERTIME Sat Jun 16 13:49:20 2012 1017686:25.32 67:05.75 1017619:19.56  Andrey Zonov For bugs matching the following criteria: Status: In Progress Changed: (is less than) 20140601 Reset to default assignee and clear inprogress tags. Mail being skipped *** Bug 17842 has been marked as a duplicate of this bug. *** *** Bug 78957 has been marked as a duplicate of this bug. *** I wrote a small program to empirically validate the proposed patch under some assumptions. "tu" (total time in microseconds) is drawn from [1, ~1000 years] (0 is uninteresting). "tt" (total time in ticks) is tu / 1000. "ut" or "st" is <= tt. With randomly drawn tu and ut/st in the given ranges (not precisely uniform due to lack of arc4random_uniform64, but close to uniform distribution), I observe overflow in something like 99.999976% of the input range with the current algorithm and 0% (absolutely zero) instances of overflow with the proposed patch. Also, the result is correct, and not truncated, in all cases with the bounds given above. I believe it fixes the issue and can be committed. (It can be found at https://people.freebsd.org/~cem/pr76972_test.c . If I made any mistake, let me know.) *** Bug 227689 has been marked as a duplicate of this bug. *** (In reply to Conrad Meyer from comment #6) Intuitively, b/c is in the (real) range [0, 1], so floor(a*b/c) should be always be representable without overflow. The trick is mostly in not losing all precision (i.e., a*(b/c) = 0 or a). A commit references this bug: Author: cem Date: Sun Feb 10 23:07:47 UTC 2019 New revision: 343985 URL: https://svnweb.freebsd.org/changeset/base/343985 Log: Prevent overflow for usertime/systime in caclru1 PR: 76972 and duplicates Reported by: Dr. Christopher Landauer <cal AT aero.org>, Steinar Haug <sthaug AT nethelp.no> Submitted by: Andrey Zonov <andrey AT zonov.org> (earlier version) MFC after: 2 weeks Changes: head/sys/kern/kern_resource.c A commit references this bug: Author: bde Date: Thu Feb 14 19:07:09 UTC 2019 New revision: 344133 URL: https://svnweb.freebsd.org/changeset/base/344133 Log: Finish the fix for overflow in calcru1(). The previous fix was unnecessarily very slow up to 105 hours where the simple formula used previously worked, and unnecessarily slow by a factor of about 5/3 up to 388 days, and didn't work above 388 days. 388 days is not a long time, since it is a reasonable uptime, and for processes the times being calculated are aggregated over all threads, so with N CPUs running the same thread a runtime of 388 days is reachable after only 388 / N physical days. The PRs document overflow at 388 days, but don't try to fix it. Use the simple formula up to 76 hours. Then use a complicated general method that reduces to the simple formula up to a bit less than 105 hours, then reduces to the previous method without its extra work up to almost 388 days, then does more complicated reductions, usually many bits at a time so that this is not slow. This works up to half of maximum representable time (292271 years), with accumulated rounding errors of at most 32 usec. amd64 can do all this with no avoidable rounding errors in an inline asm with 2 instructions, but this is too special to use. __uint128_t can do the same with 100's of instructions on 64bit arches. Long doubles with at least 64 bits of precision are the easiest method to use on i386 userland, but are hard to use in the kernel. PR: 76972 and duplicates Reviewed by: kib Changes: head/sys/kern/kern_resource.c 