Re: RFR: JDK-8310913 Move ReferencedKeyMap to jdk.internal so it may be shared [v10]
On Mon, 5 Feb 2024 16:59:51 GMT, Jim Laskey wrote: >> ok, `intern(e) == e` is sufficient. > > Created https://bugs.openjdk.org/browse/JDK-8325255 While `intern(e) == e` is (mostly) sufficient, it will return a false positive when `add(e)` is called and `e` is already present in the map, the correctest implementation would be some internal API in `ReferencedKeyMap` for implementing `ReferencedKeySet::add`. - PR Review Comment: https://git.openjdk.org/jdk/pull/14684#discussion_r1485634936
Re: RFR: JDK-8310913 Move ReferencedKeyMap to jdk.internal so it may be shared [v10]
On Mon, 5 Feb 2024 16:38:59 GMT, Roger Riggs wrote:
>> Good catch. Your solution might be correct but I think `!contains(e)` is
>> redundant since that is how intern starts out.
>>
>>
>>static T intern(ReferencedKeyMap> setMap, T key,
>> UnaryOperator 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 type of key
>> *
>> * @return the old key instance if found otherwise the new key instance
>> */
>> private static T internKey(ReferencedKeyMap>
>> setMap, T key) {
>> ReferenceKey entryKey = setMap.entryKey(key);
>> T interned;
>> do {
>> setMap.removeStaleReferences();
>> ReferenceKey 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.
Created https://bugs.openjdk.org/browse/JDK-8325255
-
PR Review Comment: https://git.openjdk.org/jdk/pull/14684#discussion_r1478583967
Re: RFR: JDK-8310913 Move ReferencedKeyMap to jdk.internal so it may be shared [v10]
On Mon, 5 Feb 2024 12:34:02 GMT, Jim Laskey 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 intern(ReferencedKeyMap> setMap, T key,
> UnaryOperator 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 type of key
> *
> * @return the old key instance if found otherwise the new key instance
> */
> private static T internKey(ReferencedKeyMap>
> setMap, T key) {
> ReferenceKey entryKey = setMap.entryKey(key);
> T interned;
> do {
> setMap.removeStaleReferences();
> ReferenceKey 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
Re: RFR: JDK-8310913 Move ReferencedKeyMap to jdk.internal so it may be shared [v10]
On Sat, 3 Feb 2024 07:20:14 GMT, ExE Boss 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 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 intern(ReferencedKeyMap> setMap, T key,
UnaryOperator 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 type of key
*
* @return the old key instance if found otherwise the new key instance
*/
private static T internKey(ReferencedKeyMap> setMap,
T key) {
ReferenceKey entryKey = setMap.entryKey(key);
T interned;
do {
setMap.removeStaleReferences();
ReferenceKey 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
Re: RFR: JDK-8310913 Move ReferencedKeyMap to jdk.internal so it may be shared [v10]
On Mon, 31 Jul 2023 13:34:30 GMT, Jim Laskey wrote:
>> java.lang.runtime.ReferencedKeyMap was introduced to provide a concurrent
>> caching scheme for Carrier objects. The technique used is generally useful
>> for a variety of caching schemes and is being moved to be shared in other
>> parts of the jdk. The MethodType interning case is one example.
>
> 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 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`.
-
PR Review Comment: https://git.openjdk.org/jdk/pull/14684#discussion_r1477004059
Re: RFR: JDK-8310913 Move ReferencedKeyMap to jdk.internal so it may be shared [v10]
> java.lang.runtime.ReferencedKeyMap was introduced to provide a concurrent > caching scheme for Carrier objects. The technique used is generally useful > for a variety of caching schemes and is being moved to be shared in other > parts of the jdk. The MethodType interning case is one example. 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 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 - Changes: https://git.openjdk.org/jdk/pull/14684/files Webrev: https://webrevs.openjdk.org/?repo=jdk=14684=09 Stats: 1520 lines in 13 files changed: 887 ins; 625 del; 8 mod Patch: https://git.openjdk.org/jdk/pull/14684.diff Fetch: git fetch https://git.openjdk.org/jdk.git pull/14684/head:pull/14684 PR: https://git.openjdk.org/jdk/pull/14684
