Request for review (M): 7016112 CMS: crash during promotion testing

[Bengt Rutisson]

Hi Tom,

Thanks for the review!

> Overall this looks fine to me.  quicksort should really be QuickSort since its a class name and normally we'd make it inherit from AllStatic to indicate that's just a collection of functions.  method names should be lower case with underscores though that isn't universally followed.

Good points. I am still getting used to the coding standard. I made the 
changes you proposed. Here is a new webrev:

http://cr.openjdk.java.net/~brutisso/7016112/webrev.02/

FYI: I changed the name of the files quicksort.cpp/hpp to 
quickSort.cpp/hpp. This is not trivial on Windows, since it does not 
care about case in file names. I got mercurial, Visual Studio and the 
file system to accept my change.  But for some reason webrev still 
thinks the files are named with all lower case. I'll make sure they are 
correctly named when I push.

> I assume we need to keep the idempotent stuff for the original reasons stated in that comment.  We could leave the bubble sort in place or just do some measurement to decide if it's really worth it.  It would be nice to get rid of it though.

Just to be clear; What I proposed was not to remove the idempotent 
sorting but to remove the parameter for it and always sort in an 
idempotent way. I have not seen any performance issues with always 
sorting with idempotent=true. On the other hand I am still a bit 
uncertain about performance so it might be best to keep it.

Bengt

> tom
>
> On Jun 21, 2011, at 5:50 AM, Bengt Rutisson wrote:
>
>> Hi Runtime and GC,
>>
>> Sending this review request to both groups. I fixed a GC bug, but the changes are in runtime code.
>>
>> The bug that I fixed is this one:
>> 7016112 CMS: crash during promotion testing
>> http://monaco.sfbay.sun.com/detail.jsf?cr=7016112
>>
>> And here is the webrev:
>> http://cr.openjdk.java.net/~brutisso/7016112/webrev.01/
>>
>> The investigation to find the root of the crashes reported in 7016112 was quite lengthy. It is not that easy to read the CR and figure out what is going on, so here is some background:
>>
>> When we load classes we store references to the methods of a class in an object array. When we have loaded all methods we sort the object array to allow binary search within the array. To do this sort we use stdlib::qsort(), which is the standard library quicksort implementation.
>>
>> If we are using CMS we might be doing concurrent marking while we are sorting the object array. The object array can be found by the concurrent marking code and it may start iterating over the array while we are sorting it. The problem is that on Windows the stdlib::qsort() is not implemented to do atomic updates of elements in the array that it sorts. Instead it does a byte-by-byte swap when it needs to swap two values. That is an easy way to implement different element widths, but it means that at some point in time one element may contain a few bytes from the element above or below. If this happens at the same time as the marking code is trying to read that element, we will be marking some random address and not the method that was supposed to be marked.
>>
>> On Solaris and Linux the stdlib::qsort() implementations try to swap as wide data types as possible so this issue should not occur there. On the other hand we have no guarantees that this will always be how stdlib::qsort() is implemented.
>>
>> After some discussions about different ways of solving this we came to the conclusion that the simplest way is to implement our own quicksort that operates on the correct pointer width (oop or narrowOop).
>>
>> So, this is what I have done to fix this bug.
>>
>> Also, it is likely that this problem will go away when the perm gen removal project is finished. Right now it looks like we will not be tracing and marking methods at all after that change.
>>
>> * Questions *
>>
>> - Should we keep the bubble sort that is done before calling quicksort in methodOopDesc::sort_methods() ?
>>
>> - Should we keep the idempotent option or should we try to always use idempotent sorting (see performance test below)?
>>
>> - What is the best way to handle unit tests? I added a flag called ExecuteInternalVMTests to run unit tests. This is in line with the existing ErrorHandlerTest flag. My thought is that we can use this same flag for other unit tests than just the quicksort tests. Would be good if we could get these tests executed by JPRT as well. I simply run these with "java -XX:+ExecuteInternalVMTests -version".
>>
>>
>> * Testing *
>>
>> Did the obvious testing: Ran JPRT with the changes in the webrev and ran the failing nsk test from the bug (nsk/sysdict/vm/stress/jck12a/sysdictj12a008) repeatedly for sevaral days without failing.
>>
>> I created some unit tests for the quicksort implementation and they all pass.
>>
>> I also made a build that sorts both with my own quicksort and with stdlib::qsort and then compares that the arrays have the same sort order. Ran this through JPRT and it seems to work on all platforms. That run also included the unit tests. If anybody wants to see how this testing was done, there is a separate webrev for that build. The interesting code is in methodOop.cpp:
>>
>> http://cr.openjdk.java.net/~brutisso/7016112/webrev-verify-sorting/
>>
>> * Performance *
>>
>> I am a bit unsure how to get any relevant performance data for this change. What I have done so far is to create a class that has 65535 methods (which is the maximum - the length of the method array is u2) and I have measured how long it takes to sort this method array. The methods have random names but every hundredth method has 4 overloaded version. This makes sure that there are some duplicates in the array.
>>
>> For now I have run this on my Windows x64 work station with 4 cpus and on a Solaris Sparc machine with 2 cpus (uname says: SunOS sthsparc24 5.10 Generic_139555-08 sun4us sparc FJSV,GPUZC-M Solaris).
>>
>> I am attaching graphs for the results. The Y-axis has time in nano seconds. Judging by this my quicksort is a bit faster on Windows and a bit slower on Solaris. But the interesting thing is that the idempotent version is faster than the default behavior on Windows and on par with the default on Solaris. I assume that this is due to the fact that some stores can be avoided if we don't do swap of duplicates. This means that (at least on Windows) swap is more expensive than compare. If this is true we should probably remove the special treatment of idempotent.
>>
>> I could run this on more machines, but I am not sure how relevant this type of data is. Most method arrays will be much shorter and compared to reading the class from a file the sort will be in the noise.
>>
>> Long email...I hope I covered most of the issues here. Let me know if you have any questions.
>>
>> Thanks,
>> Bengt
>> <win_x64_quicksort-perf.png><sparc_quicksort-perf.png>