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

Tue Jun 21 21:32:27 UTC 2011

Hi again,

For completeness. Here is the graph for sorting maximum length arrays on 
Linux x64 (run on my laptop). These runs show that my implementation 
takes twice as long as the stdlib version. I am not happy about that, 
but I don't know how much effort it is worth to optimize for this case.

Bengt

On 2011-06-21 14:50, 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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: linux_x64_quicksort-perf.png
Type: image/png
Size: 21477 bytes
Desc: not available
URL: <https://mail.openjdk.org/pipermail/hotspot-gc-dev/attachments/20110621/51404556/linux_x64_quicksort-perf.png>