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]

Padauk

Do you have the thread dump? – Affiliate

@John W.: good point. I will post it as soon as I can get it off the server. – Padauk

Is there any other part of the thread dump that shows which thread actually owns the lock? These thread are simply waiting to acquire. Finding out what they are waiting on can help. – Affiliate

There are no other references to the lock object (<0x00002aaaf1207b40>) in the thread dump – Padauk

Answer 1

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

Test6471091.java hangs on Solaris-i586

Leftwards

This related bug looks pretty close too: bugs.sun.com/bugdatabase/view_bug.do?bug_id=6822370. We will try upgrading to the latest Java 6 version, as supposedly the latter bug is fixed. Thanks for posting this. – Padauk

Also, this bug plays a role in stopping Minecraft 1.13.2 from running on IKVM.NET, since IKVM.NET have a flawed lock implementation. – Polytonality

Answer 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.

Orobanchaceous

Since he's not calling #compute, this isn't related to the issue – Personify

Answer 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).

Garcia

Answer 4

I was capable to cause deadlock using .clear() inside .compute using at least two threads, see a MRE.

Explanation

• Thread 1 acquires lock on key 1 by using computemethod
• Thread 2 acquires lock on key 2 by using computemethod
• Thread 1 call clear method to clear the cache, now waiting for thread 2 to exit compute method
• Thread 2 call clear method, now waiting on thread 1 to exit compute and clear methods
• Deadlock :/

this.store.compute(key, (k, v) -> {

  log("status=computing, key=%s", key);

  sleep(1_000);

  if (r.nextBoolean()) {
    log("status=clearing, key=%s", key);
    this.store.clear();
  }

  if (isEmpty(v)) {
    log("status=computed, key=%s", key);
    return r.nextBoolean();
  }

  return v;
});

  Number of locked synchronizers = 1
  - java.util.concurrent.ThreadPoolExecutor$Worker@378bf509

Overleap