Building Slate VM with Microsoft Visual C++ under Windows XP

[Brian T. Rice]

Thanks, I'm forwarding this on to the list now.

Jaco van der Merwe <jjnvdm at yahoo.co.uk> said:

> 
> Hi Brian
> 
> Once again I'm sending this email to you so you can
> post it on the Slate mailing list. Sorry for the
> inconvenience, but once my problems with the list have
> been resolved I can continue posting on my own :(
> 
> I have good news! I've managed to find the problem
> that caused the release build of the VM to crash
> thanks to the excellent debugging tools in Visual
> Studio. Note that this problem is not specific to the
> Visual C compiler or even Windows - it is a bug in the
> code. It will surface one way or another on all
> operating systems and compilers. The fact that the
> code worked at all is a small miracle. Note that this
> bug may also explain the fairly random nature of
> problems reported by other users of Slate.
> 
> While trying to debug the crash I noticed that the VM
> built with the MINGW GCC compiler (both the release
> and debug builds) crashed at the same point where the
> release build of Visual C crashed. My original
> suspicion proved to be correct, i.e., that somewhere
> uninitialised memory was being accessed. When you see
> different execution behaviour between release and
> debug builds with the Visual C compiler that is the
> case most of the time. Ok, I won't keep you in
> suspense any longer. Here is the function that causes
> the problem (file "vm.c', line 1214):
> 
> ObjectPointer PSObjectHeap_remapOop_(struct ObjectHeap
> * oh, ObjectPointer oop)
> {
>   unsigned long int pivot;
>   unsigned long int low;
>   unsigned long int high;
> 
>   low = 0;
>   high = oh->breakTableSize - 1;
>   pivot = (low + high) / 2;
>   while ((high - low) > 1)
>   {
>     if (oop < ((oh->breakTable)[pivot]).oldAddress)
>       high = pivot - 1;
>     else
>       low = pivot;
>     pivot = (low + high) / 2;
>   }
>   if (oop >= ((oh->breakTable)[pivot + 1]).oldAddress) // *
>     pivot = pivot + 1; // **
>   return (oop - ((oh->breakTable)[pivot]).oldAddress)
> + ((oh->breakTable)[pivot]).newAddress; // ***
> }
> 
> The bug happens in the last 3 lines of code in the
> above function, which I've commented with *, ** and
> ***. Note that line * accesses the element at index
> (pivot + 1) of the (oh->breakTable) array. Note what
> happens when (oh->breakTableSize) = 1. Then low = 0,
> high = 0, and pivot = 0. Then in line * the element
> (oh->breakTable)[1] is accessed, but this array has
> only one element, which means that it is accessing an
> element one beyond the end of the array. This element
> is uninitialised and may contain anything! Even worse,
> if it just so happens that the contents of the
> uninitialised element is such that the condition of
> the if statement in line * is true, then pivot(which =
> 0 at this point in time) will be incremented by 1 in
> line **, and then used to access the uninitialised
> element at index 1 again in line ***. By stepping
> through the code I've noticed that the case of
> low=high=0 happens very frequently. The mere fact that
> this code worked at all is a small miracle. In a debug
> build with Visual C the elements of an uninitialised
> array are all initialised to 0xcccccccc, which just by
> coincidence caused the code to work. However, in the
> release build the contents if the array is truly
> uninitialised and caused a failure fairly quickly. The
> fact that this worked on Linux with GCC also points to
> the fact that the uninitialised entries just happened
> to be large enough.
> 
> Note that the function PSObjectHeap_remapOop_() above
> is called at line 2324 in "vm.c":
> 
> *(oh->rootStack)[index] = PSObjectHeap_remapOop_(oh,
> *(oh->rootStack)[index]);
> 
> Because of the incorrect return value it wrote the
> wrong value in the field oh->specialObjectsOop in the
> above line of code, and soon after that things start
> going awry.
> 
> Ok, so the error in the above function is rooted in
> the incorrect assumptiom that (pivot + 1) will always
> be less than (oh->breakTableSize), which is clearly
> not the case. I don't quite understand the reasoning
> behing this pivoting algorithm and I'm not sure
> whether corner cases other than low=high=0 will cause
> this problem to surface. I would suggest that the
> author of this function, which obviously understands
> the reasoning behind the algorithm the best, should
> investigate this code and make it work under all
> cases.
> 
> My quick fix (or should I rather say hack?), which may
> be incorrect, but which seems to work for both the
> debug and release builds is the following (my changes
> are commented with JJN):
> 
> ObjectPointer PSObjectHeap_remapOop_(struct ObjectHeap
> * oh, ObjectPointer oop)
> {
>   unsigned long int pivot;
>   unsigned long int low;
>   unsigned long int high;
>   unsigned long int idx; // JJN: new
> 
>   low = 0;
>   high = oh->breakTableSize - 1;
>   pivot = (low + high) / 2;
>   while ((high - low) > 1)
>   {
>     if (oop < ((oh->breakTable)[pivot]).oldAddress)
>       high = pivot - 1;
>     else
>       low = pivot;
>     pivot = (low + high) / 2;
>   }
>   idx = pivot + 1;
>   if (idx > (oh->breakTableSize - 1)) // JJN: new
>    idx = (oh->breakTableSize - 1); // JJN: new
> //  if (oop >= ((oh->breakTable)[pivot +
> 1]).oldAddress) // JJN: replaced below
>   if (oop >= ((oh->breakTable)[idx]).oldAddress) //
> JJN: modified
>     pivot = pivot + 1;
>   if (pivot > (oh->breakTableSize - 1)) // JJN: new
>    pivot = (oh->breakTableSize - 1); // JJN: new
>   return (oop - ((oh->breakTable)[pivot]).oldAddress)
> + ((oh->breakTable)[pivot]).newAddress;
> }
> 
> Regards
> Jaco