Understanding code of ConcurrentHashMap compute method

Question

Just found this strange code in ConcurrentHashMap compute method: (line 1847)

public V compute(K key,
                 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    ...
    Node<K,V> r = new ReservationNode<K,V>();
    synchronized (r) {   <--- what is this?
        if (casTabAt(tab, i, null, r)) {
            binCount = 1;
            Node<K,V> node = null;

So the code performs synchronization on a new variable that is available only to current thread. That means there's no other thread to compete for this lock or to cause memory barries effects.

What is the point of this action? Is it a mistake or it causes some unobvious side effects I am not aware about?

p.s. jdk1.8.0_131

Answer 1

While r is a new variable at that point, it gets put in the internal table immediately through if (casTabAt(tab, i, null, r)) at which point another thread is able to access it in different parts of the code.

An internal non-javadoc comment describes it thusly

Insertion (via put or its variants) of the first node in an empty bin is performed by just CASing it to the bin. This is by far the most common case for put operations under most key/hash distributions. Other update operations (insert, delete, and replace) require locks. We do not want to waste the space required to associate a distinct lock object with each bin, so instead use the first node of a bin list itself as a lock. Locking support for these locks relies on builtin "synchronized" monitors.

Answer 2

casTabAt(tab, i, null, r) 

is publishing the reference to r.

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,                                     Node<K,V> c, Node<K,V> v) {     return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v); } 

Because c is being put into tab, it is possible that it is accessed by another thread, e.g. in putVal. As such, this synchronized block is necessary to exclude other threads from doing other synchronized things with that Node.

Answer 3

Just 0.02$ here

What you have shown there is actually just the ReservationNode - meaning that the bin is empty and that a reservation of some Node is made. Notice that this method later replaces this Node with a real one :

 setTabAt(tab, i, node);

So this is done in order for the replace to be atomic as far as I understand. Once published via casTabAt and if other threads see it - they can't synchronize on it since the lock is already held.

Also notice that when there is an Entry in a bin, that first Node is used to synchronize on (it's further down in the method):

boolean added = false;
            synchronized (f) { // locks the bin on the first Node
                if (tabAt(tab, i) == f) {
......

As as side node, this method has changed in 9, since 8. For example running this code:

 map.computeIfAbsent("KEY", s -> {
    map.computeIfAbsent("KEY"), s -> {
        return 2;
    }
 })

would never finish in 8, but would throw a Recursive Update in 9.