Is it possible to get a deadlock with ConcurrentHashMap in this circumstance?

Question

I'm reading the source code of ConcurrentHashMap in JDK8, notice that TreeBin uses a 'read-write' lock to prevent concurrent read and write.

Read threads will go through TreeNodes if there's no concurrent write thread trying to modify the tree structure. When the 'find' operation is done, read thread may:

(1)'CAS' the lockState and 'unpark' the waiter(writer) thread if it exists.

Following is the 'find()' method in source code.

final Node<K,V> find(int h, Object k) {
            if (k != null) {
                for (Node<K,V> e = first; e != null; ) {
                    int s; K ek;
                    if (((s = lockState) & (WAITER|WRITER)) != 0) {
                        if (e.hash == h &&
                            ((ek = e.key) == k || (ek != null && k.equals(ek))))
                            return e;
                        e = e.next;
                    }
                    else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                                                 s + READER)) {
                        TreeNode<K,V> r, p;
                        try {
                            p = ((r = root) == null ? null :
                                 r.findTreeNode(h, k, null));
                        } finally {
                            Thread w;
                            // (1)if no more readers, try to unpark the waiter if it exists
                            if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                                (READER|WAITER) && (w = waiter) != null)
                                LockSupport.unpark(w);
                        }
                        return p;
                    }
                }
            }
            return null;
        }

on the other hand, writer thread may:

(2) adding the WAITER state to lockState with 'CAS' operation.
(3) set itself to waiter variable.
(4) 'park' itself.

here's the writer's code:

        private final void contendedLock() {
            boolean waiting = false;
            for (int s;;) {
                if (((s = lockState) & ~WAITER) == 0) {
                    if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
                        if (waiting)
                            waiter = null;
                        return;
                    }
                }
                else if ((s & WAITER) == 0) {
                    if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
                        waiting = true;
                        waiter = Thread.currentThread();
                    }
                }
                else if (waiting)
                    LockSupport.park(this);
            }
        }

HERE IS MY CONFUSION:

If the four operation above run in this order (2) (1) (3) (4), the operation (1) won't unpark anything because 'waiter' was null at that moment.

Then the waiter will park forever without anyone who can unpark it.

The subsequent writes will be all blocked on the intrinsic lock held by the 'parked' thread.

IS THIS A CHANCE OF DEADLOCK ?

I'm really confused about this. I think perhaps I've missed something in the source code. Need your help if you are familiar with it.

Also, can please someone explain to me this line in find: if (((s = lockState) & (WAITER|WRITER)) != 0)? Why there is no synchronization here and in its block? — user2956272
@dyukha It means if any waiter or writer here, just go through the tree by 'next' references (like a linked-list). Because every time you add a node into the linked-list, you actually add it at the 'first' position which does not disturb your read threads to go through the other nodes in the list. So no locks needed here — Kyne Xiao

rmunge rmunge · Accepted Answer · 2020-05-28T18:28:23

The question is more than one year old. But it's such a nice puzzle. Here's the answer:

After (2) (1) (3) execution in contendedLock() continues as follows:

if (((s = lockState) & ~WAITER) == 0) is true because (1) was executed

if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) is also true, because (3) was executed before (s = lockState) and not after it

Since waiting was set to true before the execution of (3) the third if statements is also true. Therefore waiter is set to null and we exit the loop. (4) is never executed.

To sum it up: After (2) (1) (3) operation (4) will never be executed. So there is no chance of deadlock and we can all continue to use ConcurrentHashMap without qualms ;-)

Is it possible to get a deadlock with ConcurrentHashMap in this circumstance?

1 Answers