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

There is a comment block around line 740 which might shed some light on why that is done as it is. As I understand it, the node is swapped with `tab` variable via `Unsafe` operation, so at that point all threads might start to see it, and it should at that point be locked by thread that created the node, so other threads must wait to do anything with the node. Otherwise, there is a possibility of entering a race right after the swap happens. — M. Prokhorov, Dec 11 '17 at 12:33

Andy Turner · Accepted Answer · 2017-12-11T15:58:00.823

40

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.

edited Dec 11 '17 at 15:58

answered Dec 11 '17 at 12:33

Andy Turner

137,514
11
162
243

1

Not sure that "leaking" is the right verb. "Leak" usually implies an accident, but it's no accident that the code makes the node visible to other threads. – Solomon Slow Dec 11 '17 at 14:43
5

"exposing" is probably a better choice here – Caleth Dec 11 '17 at 15:51
2

@Caleth I was already thinking of changing it to "publishing", as in "unsafe publication" (although it's not "unsafe" in this context; merely that's a well-known term for making a reference available outside the current thread of execution). – Andy Turner Dec 11 '17 at 15:57

score 16 · Answer 2 · answered Dec 11 '17 at 12:35

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.

Eugene · Answer 3 · 2017-12-11T13:55:34.373

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.

Understanding code of ConcurrentHashMap compute method

3 Answers3