Deadlock in NamespacedHierarchicalStore.computeIfAbsent() #5346
Description
#5231 introduced a deadlock in NamespacedHierarchicalStory.computeIfAbsent(). I observed the following thread states when running tests concurrently on JUnit 6.0.2:
Thread A:
java.lang.Thread.State: BLOCKED (on object monitor)
at java.util.concurrent.ConcurrentHashMap.transfer([email protected]/ConcurrentHashMap.java:2483)
- waiting to lock <0x00000000820f3f10> (a java.util.concurrent.ConcurrentHashMap$Node)
at java.util.concurrent.ConcurrentHashMap.addCount([email protected]/ConcurrentHashMap.java:2354)
at java.util.concurrent.ConcurrentHashMap.compute([email protected]/ConcurrentHashMap.java:2002)
at org.junit.platform.engine.support.store.NamespacedHierarchicalStore.computeIfAbsent(NamespacedHierarchicalStore.java:272)
at org.junit.platform.engine.support.store.NamespacedHierarchicalStore.computeIfAbsent(NamespacedHierarchicalStore.java:353)
at org.junit.jupiter.engine.execution.NamespaceAwareStore.lambda$computeIfAbsent$1(NamespaceAwareStore.java:92)
at org.junit.jupiter.engine.execution.NamespaceAwareStore$$Lambda/0x000001e4d52e50c0.get(Unknown Source)
at org.junit.jupiter.engine.execution.NamespaceAwareStore.accessStore(NamespaceAwareStore.java:120)
at org.junit.jupiter.engine.execution.NamespaceAwareStore.computeIfAbsent(NamespaceAwareStore.java:93)
at org.junit.jupiter.engine.extension.TimeoutExtension.getGlobalTimeoutConfiguration(TimeoutExtension.java:174)
Thread B:
java.lang.Thread.State: WAITING (parking)
at jdk.internal.misc.Unsafe.park([email protected]/Native Method)
- parking to wait for <0x000000008cb5ee90> (a java.util.concurrent.FutureTask)
at java.util.concurrent.locks.LockSupport.park([email protected]/LockSupport.java:221)
at java.util.concurrent.FutureTask.awaitDone([email protected]/FutureTask.java:500)
at java.util.concurrent.FutureTask.get([email protected]/FutureTask.java:190)
at org.junit.platform.engine.support.store.NamespacedHierarchicalStore$DeferredSupplier.get(NamespacedHierarchicalStore.java:643)
at org.junit.platform.engine.support.store.NamespacedHierarchicalStore$StoredValue$DeferredOptionalValue.evaluate(NamespacedHierarchicalStore.java:575)
at org.junit.platform.engine.support.store.NamespacedHierarchicalStore$StoredValue.evaluateIfNotNull(NamespacedHierarchicalStore.java:492)
at org.junit.platform.engine.support.store.NamespacedHierarchicalStore.lambda$computeIfAbsent$1(NamespacedHierarchicalStore.java:275)
at org.junit.platform.engine.support.store.NamespacedHierarchicalStore$$Lambda/0x000001e4d52e7578.apply(Unknown Source)
at java.util.concurrent.ConcurrentHashMap.compute([email protected]/ConcurrentHashMap.java:1940)
- locked <0x00000000820f3f10> (a java.util.concurrent.ConcurrentHashMap$Node)
at org.junit.platform.engine.support.store.NamespacedHierarchicalStore.computeIfAbsent(NamespacedHierarchicalStore.java:272)
at org.junit.platform.engine.support.store.NamespacedHierarchicalStore.computeIfAbsent(NamespacedHierarchicalStore.java:353)
at org.junit.jupiter.engine.execution.NamespaceAwareStore.lambda$computeIfAbsent$1(NamespaceAwareStore.java:92)
at org.junit.jupiter.engine.execution.NamespaceAwareStore$$Lambda/0x000001e4d52e50c0.get(Unknown Source)
at org.junit.jupiter.engine.execution.NamespaceAwareStore.accessStore(NamespaceAwareStore.java:120)
at org.junit.jupiter.engine.execution.NamespaceAwareStore.computeIfAbsent(NamespaceAwareStore.java:93)
at org.junit.jupiter.engine.extension.TimeoutExtension.getGlobalTimeoutConfiguration(TimeoutExtension.java:174)
Analysis
The following appears to have happened:
- Thread A started executing
ConcurrentHashMap.compute(), called the passed lambda function and inserted the element into the map. At this point, it does not hold any lock insideConcurrentHashMap. - Thread B acquired the the lock on the
ConcurrentHashMap-internal node next and called the passed lambda function. The lambda function callsget()on theDeferredSupplier, waiting for the future to be executed. - Next, Thread A tried to acquire the lock on the
ConcurrentHashMap-internal node to update the map's element count and thus started waiting on Thread B. - Thus, Thread A never got around to run the future here:
So Thread B waits on Thread A to run the future inside DeferredSupplier and Thread A waits on Thread B to release the lock on the ConcurrentHashMap-internal node.
Context
- Used versions (Jupiter/Vintage/Platform): 6.0.2
- JDK 21.0.8
- Build Tool/IDE: IntelliJ and Gradle command line tools on the terminal