[9] RFR(L) 8013267 : move MemberNameTable from native code to Java heap, use to intern MemberNames

David Chase david.r.chase at oracle.com
Thu Oct 30 21:17:50 UTC 2014

New webrevs:

Changes since last RFR:

1) hotspot, the method-renamer has been modified to iterate all the way to the end,
(a) a method can be repeated with different attributes (invokespecial vs invokevirtual)
(b) because of rare-but-possible races between Java and Jvm, an entry may temporarily appear twice.

2) jdk:
Class.internMemberName was made non-public, exposed through JavaLangAccess

Class.classRedefinedCount was made package-visible, exposed through JavaLangAccess.

ClassData.intern was modified to be race-safe with class redefinition.  The code “borrowed”
from ArrayList was mostly removed, and the call to parallelSort was removed; instead, the
array is “expanded” by duplicating the last element, increasing the size, and sliding elements
up by one to open a hole for insertion of the new element.  This ensures that existing
MemberNames are never accidentally hidden, and that the jvm side never sees nulls.

The intern code in ClassData and MemberName had a redefined_count “transaction token”
added so that races between redefinition and membername interning could be detected
and the intern retried after a new resolution.

A “transaction” object was added for use by the MemberName-allocating factory methods
because the race-detection code was fiddly and ugly, and appeared in several places.

The clone+changeReferenceKind+intern idiom was replaced with a method
cloneAndChangeReferenceKindAndIntern that included the race detection (slightly
less ugly in the case that a membername merely has its reference kind changed).

MemberName.compareTo was “enhanced” to try much harder to return a sensible
answer — where it would previously, in theory never, return a bogus answer, it
now, in theory never, works harder to return a correct answer.  It now also compares
hashCodes correctly (they are integers, possibly negative, subtraction is NOT how
you obtain a -/0/+ comparison result).

Still to do — convert RedefineMethodUsedByMultipleMethodHandles into a jtreg test.

Passes RedefineMethodUsedByMultipleMethodHandles, passes the failing tests in ute.
Passes jtreg of hotspot/{compiler, runtime, gc} and jdk/vm and jdk/sun/{misc,reflect,invoke}

Possible concerns:

0) The code that guards against concurrent redefinition has some stores that should not
be reordered by the (hotspot) compiler.  They take the form:
   A : store
   B : volatile store
   C : store
Am I okay?  Or do I need to do more than just a volatile store in the middle?  (A and C are
stores to array elements, so I can’t trivially make them volatile.)  Yes, there is a big wordy
comment where this happens.

1)  the comparison function is completely, bizarrely ad hoc, and essentially impossible
to reproduce on the jvm side.  That’s not a problem right now, but...

2) Class redefinition is potentially quadratic in the number of methods in a class, if all the
methods of that class are unreflected into MethodHandles.  Do we think this is a problem?

3) MemberName insertion is expected O(N) where N is the number of MemberNames already
interned (unless they are inserted in sorted order, where the sort order is defined by the

However, MemberName lookup is O(log N).

4) I need to look into the possible performance regression that Chris and Serguei were talking about. 
I’m not sure that the old fix will work here at all.

Do we need a cleverer data structure?  One Java-side option is to create a custom within-array
hashtable that would make lookup and insertion O(1) (the JVM should be modified to tolerate nulls,
in the array, which is clearly possible).  If a hashcode were defined that was easily accessed or
understood by the JVM, that would permit faster method redefinition, too.


For reference, here is the class introduced to avoid repetition of the redefinition-detection ugliness:

    static class InternTransaction {
        Class<?> tx_class;
        int txn_token;

        InternTransaction(Class<?> tx_class) {
            this.tx_class = tx_class;
            this.txn_token = internTxnToken(tx_class);

         * If member_name is not resolved, returns member_name; if is resolved,
         * attempts to intern member_name (once) while checking for races.
         * @param member_name
         * @return member_name if not resolved, null if racing, otherwise
         *         value of interned member_name.
        MemberName tryIntern(MemberName member_name) {
            if (member_name.isResolved()) {
                if (member_name.getClass() != tx_class) {
                    Class prev_tx_class = tx_class;
                    int prev_txn_token = txn_token;
                    tx_class = member_name.getClass();
                    txn_token = internTxnToken(tx_class);
                    // Zero is a special case.
                    if (txn_token != 0 ||
                        prev_txn_token != internTxnToken(prev_tx_class)) {
                        // Resolved class is different and at least one
                        // redef of it occurred, therefore repeat with
                        // proper class for race consistency checking.
                        return null;
                return member_name.intern(txn_token);
            } else {
                return member_name;

And the code that tap-dances around races with Class redefinition:

        private <E extends Comparable<? super E>> E add(Class<?> klass, int index, E e, int redefined_count) {
            int oldCapacity = size;
            Comparable<?>[] element_data = elementData;
            if (oldCapacity + 1 > element_data.length ) {
                // Replacing array with a copy is safe; elements are identical.
                grow(oldCapacity + 1);
                element_data = elementData;
             * Careful dance to insert an element.
             * Wish to ensure that we do not hide an element of
             * the array; must also ensure that visible-to-jvm
             * portion of array never contains nulls; also ensure
             * that array remains sorted.
             * Note that taking a safepoint is also a barrier.
            if (oldCapacity >  0) {
                element_data[oldCapacity] = element_data[oldCapacity - 1];
                // all array elements are non-null and sorted, increase size.
                // if store to element_data above floats below
                // store to size on the next line, that will be
                // inconsistent to the VM if a safepoint occurs here.
                size += 1;
                for (int i = oldCapacity; i > index; i--) {
                    // pre: element_data[i] is duplicated at [i+1]
                    element_data[i] = element_data[i - 1];
                    // post: element_data[i-1] is duplicated at [i]
                // element_data[index] is duplicated at [index+1]
                element_data[index] = (Comparable<?>) e;
            } else {
                element_data[index] = (Comparable<?>) e;
                // Don't want store to element_data[index] above
                // to float past store to size below, otherwise
                // VM might see inconsistent state.
                size += 1;
            if (redefined_count == klass.classRedefinedCount()) {
                return e;
            /* The race was lost, must undo insertion and retry the intern
             * with a new resolution.
            for (int i = index; i < oldCapacity; i++) {
                element_data[i] = element_data[i+1];
            size -= 1;
            return null;

On 2014-10-23, at 7:00 PM, John Rose <john.r.rose at oracle.com> wrote:

> On Oct 17, 2014, at 11:16 AM, David Chase <david.r.chase at oracle.com> wrote:
>> bug: https://bugs.openjdk.java.net/browse/JDK-8013267
>> webrevs:
>> http://cr.openjdk.java.net/~drchase/8013267/jdk.03/
>> http://cr.openjdk.java.net/~drchase/8013267/hotspot.03/
>> related bug: https://bugs.openjdk.java.net/browse/JDK-8042235
> This is a big 'un.  Now that we can modify hotspot and jdk together more easily, it's more feasible to work on.  I'm glad to see you taking this on.
> A few comments for background:
> This is a case where more logic should go at the JDK layer, where we can work on it and understand it more readily.
> The JVM layer should supply only a few things for this:
> - A mapping from symbolic references to resolved references
> - A mapping from reflective stuff (jlr.Method) to resolved references
> - A bulk query from a class to its resolved references
> The common thread is that only the JVM knows how to inject metadata into the MemberName type.  Other logic, such as caching or interning or registration, is best handled by Java code.
> To complicate things, the JVM also needs to (very infrequently) visit the set of all MemberName's in the world.  (Or else we need a turtle under the MN turtle, which we are not doing, thankfully.)  That's why there needs to be a coupling where the JVM can "see" the Class.ClassData fields.
>> 1) on the hotspot side, code to adjust the membername table needed to check
>>   that the data for the membername table was actually allocated (one goal of this
>>   rfe was to avoid allocating that table) else it would null deref and crash.
> Nice catch.  C code doesn't do NPEs very well.
>> 2) on the jdk side, fencepost error in the membername table insertion; the first
>>   entry could be duplicated (  “if index > 0” wrong, should be “if index >= 0”).
> Good.
>> 3) on the jdk side, several of the constructors for MemberNames needed to be
>>   replaced with factories that would consult the MemberNameTable and avoid
>>   creating duplicates; again, that was the entire point of this fix.  *NOT ALL
>>   CONSTRUCTORS WERE MODIFIED LIKE THIS”, and there was one curious
>>   piece of code where it seemed that this might not be what was desired, but it
>>   was unclear how this would behave in the face of method redefinition.
> Maybe this was a place where the patch was incomplete.
> Since the MemberName type is *private* to the java.lang.invoke package, public constructors are tolerable.  (Some or all of them could be made non-public or private, if that makes the code easier to reason about.)
> But among the non-private constructors there is a deep difference between constructors which create an unresolved symbolic reference and constructors which somehow create a MN which is resolved from the start.  The former are needed to compose a query to the resolve (and possibly intern) functions.  The latter are special cases needed by the user-visible unreflectFoo methods.
>> From 
>> http://cr.openjdk.java.net/~drchase/8013267/jdk.03/src/java.base/share/classes/java/lang/invoke/MemberName.java.html
>> 1047         private MemberName resolve(byte refKind, MemberName ref, Class<?> lookupClass) {
>> 1048             MemberName m = ref.clone();  // JVM will side-effect the ref
>> 1049             assert(refKind == m.getReferenceKind());
>> 1050             try {
>> 1051                 m = MethodHandleNatives.resolve(m, lookupClass);
>> 1052                 m.checkForTypeAlias();
>> 1053                 m.resolution = null;
>> 1054                 m.intern();
>> Note that this performs an “intern” that ignores what is already found in the table
>> and may not place m in the table if a duplicate name is already there. ?????????
> That is:
> + m.intern();   // FIXME:  Here's where we stopped work the last time around.
> I would try, first:
> + m = m.intern();
>> testing:
>> jtreg:
>> hotspot/{compiler,runtime,gc}
>> jdk/{vm,jdk,sun/{invoke,misc,reflect}
>> by-hand: verified that the crash example for 8042235 still crash in an unmodified VM and does not crash  in a modified VM.
>> Modified and retested
>> https://bugs.openjdk.java.net/secure/attachment/20184/RedefineMethodUsedByMultipleMethodHandles.java
>> Old:
>>       // Calling fooMH1.vmtarget crashes the VM
>>       System.out.println("fooMH1.invoke = " + fooMH1.invokeExact());
>> New:
>>       // Calling fooMH1.vmtarget crashes the VM
>>       System.out.println("fooMH1.invoke = " + fooMH1.invokeExact());
>>       System.out.println("fooMH2.invoke = " + fooMH2.invokeExact());
>> This turned out to be a reasonable thing to do, since the added line caused a crash till further corrections were made.
>> (See fixes 2 and 3 above).
>> Should RedefineMethodUsedByMultipleMethodHandles.java also be added as a test?
> I would say yes, though I'd defer to an SQE or Serguei on that.
>> Are there other tests that would be good to run ?(and if they are ute tests, the more
>> detailed the instructions for how to run them, the better.)
> (Same deference.)
> — John

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20141030/cceb6ece/signature-0001.asc>

More information about the hotspot-compiler-dev mailing list