[Vm-dev] 3 Bugs in LargeInteger primitives

David T. Lewis lewis at mail.msen.com
Sat Sep 1 14:14:14 UTC 2012


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.

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]].

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