Begin forwarded message:
From: Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> Subject: [Vm-dev] 3 Bugs in LargeInteger primitives Date: August 29, 2012 12:18:28 PM GMT+02:00 To: Squeak Virtual Machine Development Discussion <vm-dev@lists.squeakfoundation.org> Reply-To: Squeak Virtual Machine Development Discussion <vm-dev@lists.squeakfoundation.org>
As posted on squeak-dev http://lists.squeakfoundation.org/pipermail/squeak-dev/2012-August/165608.ht... I found 3 bugs in LargeInteger primitives
(1<<63) negated quo: -1. (1<<63) negated / -1. (1<<63) negated * -1.
They are all related to the impossible task of taking absolute value of INT_MIN (or more exactly it's 64 bits equivalent). Currently, it takes the form (0 - INT_MIN) whose behaviour is undefined according to C standards but generally answer INT_MIN. See for example http://stackoverflow.com/questions/2539178/why-is-abs0x80000000-0x80000000
Surprisingly this one works: (1<<63) negated // -1.
Most probably because gcc has a license to ignore undefined behaviour and perform some optimizations that don't take overflow side effects into account. For example 0 - (0 - a)/b can be simplified into a/b, UB case of INT_MIN apart...
---------------------------------
Beside these bugs, when I read the code, I'm quite sure it's a nest of future bugs because there are many other attempts to catch overflow in post-condition (like testing that addition of two positive is negative when an underflow occurs) that technically rely on explicitely Undefined Behaviour (UB). OK, by now many Arithmetic Units do behave like exploited in these post-conditions, though it's not strictly future-proof. But we unfortunately rely on optimizing C compilers, and its behaviour is much more fragile than hardware...
I invite every VM hacker to read http://stackoverflow.com/questions/199333/best-way-to-detect-integer-overflo... And various links like https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure...
For example, in large integer subtract, we have a protection against (0 - INT_MIN) like: y = 0 - x; if ( y==x ) { primitiveFail(); } an optimizing compiler having a licence to ignore INT_MIN Undefined Behaviour case could mathematically solve the equation as x==0, y==0 and transform code into if( ! (y=0-x) ) { primitiveFail(); } (directly use a jz and save a comparison)
or if we have such branch c = a + b; if( a >0) { if(b > 0) { if (c < 0 ) { primitiveFail(); } } } Again, a good compiler could remove the if( c < 0) test, since it does not have to care about UB...
OK, pragmatically, most of these post-condition hacks are fast and work with some version of gcc, but think about portability (llvm ?) and future pain (you can debug such code only at asembler level).
Do it right > do it fast.
Nicolas