ConcurrentMap::compute clarification

[Timo Kinnunen]

Yes, I think the containsKey check is just not appropriate here. Doing the check means the information gained from reading oldValue becomes immediately stale. This means oldValue has to be read again. But reading oldValue means the information received from the check on whether the loop has to repeated now becomes stale. So in the end no new information is gained but one extra loop will be performed. If there’s a devious Maxwell’s daemon thread which keeps adding and removing a key-value mapping at just the right times around the containsKey check then the compute method will loop forever without the value the daemon is using ever being observable.

This could be simulated by having the containsKey method return true for any key in every case where it is the sole party to an atomic operation.



-- 
Have a nice day, 
Timo

Sent from Mail for Windows 10



From: Paul Sandoz
Sent: Wednesday, December 9, 2015 12:22
To: Jaromir Hamala
Cc: core-libs-dev at openjdk.java.net
Subject: Re: ConcurrentMap::compute clarification


Hi Jaromir,

Thanks, you found a bug, seems to be a hangover from the Map default implementation.

One fix might be:

if (oldValue != null) {
    // something to remove
    if (remove(key, oldValue)) {
        // removed the old value as expected
        return null;
    }

    // some other value replaced old value. try again.
    oldValue = get(key);
} else if (contains(key)) {
    // a mapping was added after obtaining the old value, try again
    oldValue = get(key);
} else {
    // nothing to do. Leave things as they were.
    return null;
}

Although i am somewhat inclined to do away with the contains check (given nulls are not supported), so things are just left alone.

Do you wanna report the issue here:

  http://bugreport.java.com/

Thanks,
Paul.

> On 8 Dec 2015, at 11:12, Jaromir Hamala <jaromir.hamala at gmail.com> wrote:
> 
> Hi,
> 
> I stumbled upon an interesting issue with default implementation of
> `compute(K key, BiFunction<? super K, ? super V, ? extends V>
> remappingFunction)` in JDK8 `ConcurrentMap`.
> According to its contract the default method implementation assumes map
> implementations do not support null values.
> 
> This is the begin of the default implementation:
> 
> default V compute(K key, BiFunction<? super K, ? super V, ? extends V>
> remappingFunction) {
>        Objects.requireNonNull(remappingFunction);
>        V oldValue = get(key);
>        for(;;) {
>            V newValue = remappingFunction.apply(key, oldValue);
>            if (newValue == null) {
>                // delete mapping
>                if (oldValue != null || containsKey(key)) {
>                    // something to remove
>                    if (remove(key, oldValue)) {
> [...]
> 
> 
> Let's say we have an empty map and 2 threads:
> T1 is calling the `compute('foo', someFunction)`
> T2 is concurrently calling calling `put('foo', 'bar');`
> 
> so the T1 will get `oldValue = null`, but `containsKey()` will return
> `true` - because T2 already created the mapping `foo -> bar`. Hence T1 will
> call `remove('foo', null)` !
> 
> Contract of `remove()` says: `throws NullPointerException if the specified
> key or value is null, and this map does not permit null keys or values
> optional.` -> the T1 will throw NPE.
> Is it a bug in default method impl or do I understand it wrong?
> 
> Cheers,
> Jaromir
> 
> --
> “Perfection is achieved, not when there is nothing more to add, but when
> there is nothing left to take away.”
> Antoine de Saint Exupéry