Message-Id: <200901031346.01325.rob@landley.net>
Date:	Sat, 3 Jan 2009 13:46:00 -0600
From:	Rob Landley <rob@...dley.net>
To:	Matthieu CASTET <matthieu.castet@...rot.com>
Cc:	Arkadiusz Miskiewicz <a.miskiewicz@...il.com>,
	linux-kernel@...r.kernel.org,
	Embedded Linux mailing list <linux-embedded@...r.kernel.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	"H. Peter Anvin" <hpa@...or.com>, Sam Ravnborg <sam@...nborg.org>
Subject: Re: PATCH [0/3]: Simplify the kernel build by removing perl.

On Friday 02 January 2009 10:04:08 Matthieu CASTET wrote:
> Rob Landley a écrit :
> > On Friday 02 January 2009 03:26:37 Arkadiusz Miskiewicz wrote:
> >> On Friday 02 of January 2009, Rob Landley wrote:
> >>
> >> Heh,
> >
> > I believe all three scripts run under dash and busybox ash.  (The
> > timeconst.sh one needs 64 bit math which dash only provides on 64 bit
> > hosts, which is a regression from Red Hat 9 in 2003 by the way.
>
> With dash 0.5.4-12 (from debian sid), I seems I got the 64 bit math for
> 32 bit hosts :
> $ uname -m
> i686
> $ dash -c 'echo $((1<<32))'
> 4294967296

Cool.

The "relatively recent" 32 bit image I have lying around for testing purposes 
is xubuntu 7.10, and when dash was first introduced into ubuntu it had 
_buckets_ of bugs.  (If you backgrounded a task with & and then hit ctrl-z on 
the command line, it would suspend the backgrounded task.  It was Not Ready 
for Prime Time in a big way.)  Lack of 64 bit math could easily be one more.  
(It _is_ a regression vs Red Hat 9.)

The dash in ubuntu 8.10 seems to have a lot of the more obvious problems 
worked out.  Good to know. :)

That said, while testing the new round of patches against various shells and 
making it reproduce the full set of time constants that the old perl script 
kept cached values for (24, 32, 48, 64, 100, 122, 128, 200, 250, 256, 300, 
512, 1000, 1024, and 1200 hz), I found a bug.

The first patch is  miscalculating USEC_TO_HZ_ADJ32 for 24 HZ and 122 HZ.  All 
the other values are fine.)  It's an integer overflow.  The GCD of 24 and 
1000000 is 8, so that's 17 significant bits with a shift of 47... which is 
exactly 64 bits, but the math is _signed_, so it goes boing.

For the record, the reason I can't just pregenerate all these suckers on a 
system that's got an arbitrary precision calculator (ala dc) and then just 
ship the resulting header files (more or less the what the first version of 
that first patch did) is that some architectures (arm omap and and arm at91) 
allow you to enter arbitrary HZ values in kconfig.  (Their help text says that 
in many cases values that aren't powers of two won't work, but nothing 
enforces this.)  So if we didn't have the capability to dynamically generate 
these, you could enter a .config value that would break the build.

I'd be willing to use dc in the script if A) it was mentioned in SUSv3 (it's 
not, although bc is), B) the version of dc in busybox wasn't crap (it's 
floating point rather than arbitrary precision, and doesn't implement the left 
shift operator).  The reason I'm not looking more closely at what SUSv3 has to 
say about bc is that A) it claims to be an entire programming language, which 
is definitely overkill for this B) busybox hasn't bothered to implement it so 
it can't be all that widely used anymore.

I'll fix this and resubmit, it just wasn't ready last night.  (If the merge 
window is closing soon I could resubmit the other two with Sam's suggestions 
and resubmit this one next time 'round, but it was only a couple days to write 
in the first place, once I finally figured out what the perl version was 
trying to _do_...)

I believe ADJ32 is the only operation with any potential to overflow.  The 
pathological case for SHIFT is HZ 1, which for USEC conversions would give a 
shift around 52 (32 significant bits plus 20 bits to divide by 1000000), but 
MUL32 still wouldn't overflow because the shift loop stops when it finds 32 
significant bits, and any larger HZ value would produce a smaller shift.  The 
problem with ADJ32 is it uses the MUL32 shift value, so a small $TO (24 HZ) 
with a big $FROM (1000000 USEC, 19 signficant bits) and a small Greatest 
Common Denominator (in this case 8) can overflow 64 bits.  Pathological case 
is still HZ 1.  (Or any other smallish prime number.)  If I make that work, 
everything else has to.

So anyway, it's not _arbitrary_ precision math.  It's more like 32+20+20=72 
bits, and I can probably fake that pretty easily by breaking a couple of 
operations into two stages...

Fallen a bit behind on the thread since I noticed this and went off to code, 
I'll try to catch up later today.

Rob
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists