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

[Roger Riggs]

On Mon, 5 Feb 2024 12:34:02 GMT, Jim Laskey <jlaskey at openjdk.org> wrote:

>> 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?

ok, `intern(e) == e` is sufficient.

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

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