RFR: JDK-8310913 Move ReferencedKeyMap to jdk.internal so it may be shared [v10]

[Jim Laskey]

On Sat, 3 Feb 2024 07:20:14 GMT, ExE Boss <duke at openjdk.org> wrote:

>> Jim Laskey has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains 17 commits:
>> 
>>  - Merge branch 'master' into 8310913
>>  - Update implNote for intern
>>  - Merge branch 'master' into 8310913
>>  - Requested changes.
>>    
>>    Added intern with UnaryOperator<T> interning function to prepare key before adding to set.
>>  - Update test to check for gc.
>>  - Update ReferencedKeyTest.java
>>  - Simple versions of create
>>  - Add flag for reference queue type
>>  - Merge branch 'master' into 8310913
>>  - Update to use VirtualThread friendly stale queue.
>>  - ... and 7 more: https://git.openjdk.org/jdk/compare/408987e1...af95e5ae
>
> src/java.base/share/classes/jdk/internal/util/ReferencedKeySet.java line 151:
> 
>> 149:     @Override
>> 150:     public boolean add(T e) {
>> 151:         return intern(e) == null;
> 
> This line is wrong, as `intern(…)` will never return `null`.
> 
> --------------------------------------------------------------------------------
> 
> This is the closest to the correct implementation,
> Suggestion:
> 
>         return !contains(e) & intern(e) == e;
> 
> 
> but may incorrectly return `true` in case of the following data race, assuming `t1e == t2e`:
> 
> 1. **Thread 1** calls `contains(t1e)` and gets `false`.
> 2. **Thread 2** calls `intern(t2e)` and successfully adds `t2e`.
> 3. **Thread 1** calls `intern(t1e)` and gets back `t2e`, which is `==` to `t1e`.
> 4. **Thread 1** returns `true`, even though it was **Thread 2** which modified the `ReferencedKeySet`.

Good catch. Your solution might be correct but I think `!contains(e)` is redundant since that is how intern starts out.


   static <T> T intern(ReferencedKeyMap<T, ReferenceKey<T>> setMap, T key, UnaryOperator<T> interner) {
        T value = existingKey(setMap, key);
        if (value != null) {
            return value;
        }
        key = interner.apply(key);
        return internKey(setMap, key);
    }


Agree? So changing to `return intern(e) == e;` should be sufficient.

The other aspect of this is that `internKey` uses `putIfAbsent` which should prevent the race (assuming `ConcurrentHashMap`).


    /**
     * Attempt to add key to map.
     *
     * @param setMap    {@link ReferencedKeyMap} where interning takes place
     * @param key       key to add
     *
     * @param <T> type of key
     *
     * @return the old key instance if found otherwise the new key instance
     */
    private static <T> T internKey(ReferencedKeyMap<T, ReferenceKey<T>> setMap, T key) {
        ReferenceKey<T> entryKey = setMap.entryKey(key);
        T interned;
        do {
            setMap.removeStaleReferences();
            ReferenceKey<T> existing = setMap.map.putIfAbsent(entryKey, entryKey);
            if (existing == null) {
                return key;
            } else {
                // If {@code putIfAbsent} returns non-null then was actually a
                // {@code replace} and older key was used. In that case the new
                // key was not used and the reference marked stale.
                interned = existing.get();
                if (interned != null) {
                    entryKey.unused();
                }
            }
        } while (interned == null);
        return interned;
    }


Agree? Anyone else want to pipe in?

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/14684#discussion_r1478137517