On Mon, 5 Feb 2024 12:34:02 GMT, Jim Laskey <jlas...@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
