Is it possible for ConcurrentHashMap to "deadlock"?

Question

We have come across a strange issue with ConcurrentHashMap, where two threads appears to be calling put(), and then waiting forever inside the method Unsafe.park(). From the outside, it looks like a deadlock inside ConcurrentHashMap.

We have only seen this happen once so far.

Can anyone think of anything that could cause these symptoms?

EDIT: The thread dump for the relevant threads is here:

"[redacted] Thread 2" prio=10 tid=0x000000005bbbc800 nid=0x921 waiting on condition [0x0000000040e93000]
   java.lang.Thread.State: WAITING (parking)
    at sun.misc.Unsafe.park(Native Method)
    - parking to wait for  <0x00002aaaf1207b40> (a java.util.concurrent.locks.ReentrantLock$NonfairSync)
    at java.util.concurrent.locks.LockSupport.park(LockSupport.java:158)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:747)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:778)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1114)
    at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(ReentrantLock.java:186)
    at java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:262)
    at java.util.concurrent.ConcurrentHashMap$Segment.put(ConcurrentHashMap.java:417)
    at java.util.concurrent.ConcurrentHashMap.put(ConcurrentHashMap.java:883)
    at [redacted]


"[redacted] Thread 0" prio=10 tid=0x000000005bf38000 nid=0x91f waiting on condition [0x000000004151d000]
   java.lang.Thread.State: WAITING (parking)
    at sun.misc.Unsafe.park(Native Method)
    - parking to wait for  <0x00002aaaf1207b40> (a java.util.concurrent.locks.ReentrantLock$NonfairSync)
    at java.util.concurrent.locks.LockSupport.park(LockSupport.java:158)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:747)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:778)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1114)
    at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(ReentrantLock.java:186)
    at java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:262)
    at java.util.concurrent.ConcurrentHashMap$Segment.put(ConcurrentHashMap.java:417)
    at java.util.concurrent.ConcurrentHashMap.put(ConcurrentHashMap.java:883)
    at [redacted]

Solution 1

Maybe not the answer you want, but this may be a JVM bug. See

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6865591

Solution 2

I don't think this is what's happening in your case, but it is possible to write a deadlock with a single instance of ConcurrentHashMap, and it only needs one thread! Kept me stuck for quite a while.

Let's say you're using a ConcurrentHashMap<String, Integer> to calculate a histogram. You might do something like this:

int count = map.compute(key, (k, oldValue) -> {
    return oldValue == null ? 1 : oldValue + 1;
});

Which works just fine.

But let's say you decide instead to write it like this:

int count = map.compute(key, (k, oldValue) -> {
    return map.putIfAbsent(k, 0) + 1;
});

You will now get a 1-thread deadlock with a stack like this:

Thread [main] (Suspended)   
    owns: ConcurrentHashMap$ReservationNode<K,V>  (id=25)   
    ConcurrentHashMap<K,V>.putVal(K, V, boolean) line: not available    
    ConcurrentHashMap<K,V>.putIfAbsent(K, V) line: not available    
    ConcurrentHashMapDeadlock.lambda$0(ConcurrentHashMap, String, Integer) line: 32 
    1613255205.apply(Object, Object) line: not available    
    ConcurrentHashMap<K,V>.compute(K, BiFunction<? super K,? super V,? extends V>) line: not available  

In the example above, it's easy to see that we're attempting to modify the map inside of an atomic modification, which seems like a bad idea. However, if there are a hundred stack frames of event-callbacks between the call to map.compute and map.putIfAbsent, then it can be quite difficult to track down.

Solution 3

Package Unsafe is native, an implementation depends on a platform.

Abrupt termination of third thread (on platform level, excepion is not a problem) which acquired a lock on map can cause such situation - state of lock is broken, two other threads are disabled and waiting for someone to call Unsafe.unpark() (And that will never happen).