[Vm-dev] 3 Bugs in LargeInteger primitives

Levente Uzonyi leves at elte.hu
Sat Sep 1 14:44:21 UTC 2012


On Sat, 1 Sep 2012, David T. Lewis wrote:

>
> I have integrated these fixes into trunk VMMaker for testing. The
> new #testMinimumNegativeIntegerArithmetic unit test passes, and a VM
> compiled in 64-bit mode no longer crashed. I can find no significant
> change in performance with these changes applied. This looks really
> good to me, and if there are no other comments or issues I will go
> ahead and post the update to trunk VMMaker.

That sounds great, thanks Dave.

>
> Here are the performance measurements that I did to compare VM performance
> before and after applying the changes. This is done with an interpreter
> VM compiled in 64 bit mode on Linux:
>
>
>  testBlock := [(1 to: 1000000) do: [:e | | largeNegativeInt |
> 		largeNegativeInt := -9223372036854775808 + e.
> 		largeNegativeInt >> 3.
> 		largeNegativeInt + 1.
> 		largeNegativeInt - -1.
> 		largeNegativeInt // -1.
> 		largeNegativeInt \\ -1.
> 		largeNegativeInt rem: -1.
> 		largeNegativeInt quo: -1.
> 		largeNegativeInt * -1.
> 		largeNegativeInt / -1]].

What's the reason for using #to: and #do: instead of #to:do:? The latter 
seems to be much more appropriate in such tests, because it doesn't create 
any objects and message sends, so garbage collection has less effect on 
the measurements.


Levente

>
> Before Nicolas' changes:
>
>  (LargeNegativeIntegerTest selector: #testMinimumNegativeIntegerArithmetic) run
>     ==> 1 run, 0 passes, 0 expected failures, 1 failures, 0 errors, 0 unexpected passes
>
>  Time millisecondsToRun: [(1 to: 1000000) do: [:e | e + -9223372036854775808 // -1]] ==> 1565
>  Time millisecondsToRun: [(1 to: 1000000) do: [:e | e + -9223372036854775808 // -1]] ==> 1550
>  Time millisecondsToRun: [(1 to: 1000000) do: [:e | e + -9223372036854775808 // -1]] ==> 1544
>
>  0 tinyBenchmarks ==> '437981180 bytecodes/sec; 14163414 sends/sec'
>  0 tinyBenchmarks ==> '442141623 bytecodes/sec; 14141708 sends/sec'
>  0 tinyBenchmarks ==> '442141623 bytecodes/sec; 14120068 sends/sec'
>  0 tinyBenchmarks ==> '440240756 bytecodes/sec; 14163414 sends/sec'
>  0 tinyBenchmarks ==> '442141623 bytecodes/sec; 14823236 sends/sec'
>
>  Time millisecondsToRun: testBlock ==> 4698
>  Time millisecondsToRun: testBlock ==> 4671
>  Time millisecondsToRun: testBlock ==> 4668
>  Time millisecondsToRun: testBlock ==> 4612
>  Time millisecondsToRun: testBlock ==> 4657
>
> After applying the fixes:
>
>  (LargeNegativeIntegerTest selector: #testMinimumNegativeIntegerArithmetic) run
>     ==> 1 run, 1 passes, 0 expected failures, 0 failures, 0 errors, 0 unexpected passes
>
>  Time millisecondsToRun: [(1 to: 1000000) do: [:e | e + -9223372036854775808 // -1]] ==> 1616
>  Time millisecondsToRun: [(1 to: 1000000) do: [:e | e + -9223372036854775808 // -1]] ==> 1581
>  Time millisecondsToRun: [(1 to: 1000000) do: [:e | e + -9223372036854775808 // -1]] ==> 1577
>
>  0 tinyBenchmarks ==> '456735057 bytecodes/sec; 14002222 sends/sec'
>  0 tinyBenchmarks ==> '461677186 bytecodes/sec; 14023502 sends/sec'
>  0 tinyBenchmarks ==> '462929475 bytecodes/sec; 14002222 sends/sec'
>  0 tinyBenchmarks ==> '459192825 bytecodes/sec; 14002222 sends/sec'
>  0 tinyBenchmarks ==> '458781362 bytecodes/sec; 13970423 sends/sec'
>
>  Time millisecondsToRun: testBlock ==> 4680
>  Time millisecondsToRun: testBlock ==> 4672
>  Time millisecondsToRun: testBlock ==> 4722
>  Time millisecondsToRun: testBlock ==> 4675
>  Time millisecondsToRun: testBlock ==> 4679
>
> Dave
>
>
> On Thu, Aug 30, 2012 at 01:14:54AM +0200, Nicolas Cellier wrote:
>>
>> See also http://code.google.com/p/cog/issues/detail?id=92 where I
>> attached a fix for large int
>> It's untested yet and to review carefully !
>>
>> As Stefan told, there is UB-reliance in SmallInteger primitives too,
>> but I did not fix them.
>> We should simply compute result as signed 64 bits as proposed by
>> Stefan (except bitShift)
>>
>> Nicolas
>>
>> 2012/8/30 David T. Lewis <lewis at mail.msen.com>:
>>>
>>> This is on Mantis at http://bugs.squeak.org/view.php?id=7705
>>>
>>> Note last comment in related issue 6987.
>>>
>>> This issue will crash the VM when compiled for 64-bit platforms.
>>>
>>> Dave
>>>
>>> On Wed, Aug 29, 2012 at 12:18:28PM +0200, Nicolas Cellier wrote:
>>>>
>>>> As posted on squeak-dev
>>>> http://lists.squeakfoundation.org/pipermail/squeak-dev/2012-August/165608.html
>>>> 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-overflow-in-c-c
>>>> And various links like
>>>> https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow?showComments=false
>>>>
>>>> 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
>


More information about the Vm-dev mailing list