Overview

The change to ConcurrentReferenceHashMap in 12dd75815867def5c6d29be results in the mapping function now being computed whilst the lock is held. If the mapping function involves access to the same map, that one thread can acquire locks to multiple map segments. If two threads try and acquire locks already held by one another, a deadlock occurs. Below is a test case which illustrates the issue (passes on 6.2.12, fails on 6.2.13). For simplicity, I've used the same two keys in the example below, but in reality, they only need to be keys that hash to the same segment.

This deadlock doesn't present itself as long as the mapping function doesn't involve access to the same map. However, there is such a call in the Spring code during context initialization in: org.springframework.core.annotation.AnnotationTypeMappings$Cache.get(AnnotationTypeMappings.java:273). Thus, complex Spring contexts may occasionally fail to initialise if map access timings and key hashes are unfavorable. Please also see sample thread_dump.txt.

@Test
void deadlock() throws Exception {
    var map = new org.springframework.util.ConcurrentReferenceHashMap<String, String>();
    var deadLockSync = new CountDownLatch(2);
    ExecutorService executor = Executors.newFixedThreadPool(2);

    // Thread 1: key1 -> key2
    executor.submit(() -> {
        try {
            map.computeIfAbsent("key1", k -> {
                deadLockSync.countDown();
                return map.computeIfAbsent("key2", k2 -> "value2");
            });
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    });

    // Thread 2: key2 -> key1
    executor.submit(() -> {
        try {
            map.computeIfAbsent("key2", k -> {
                deadLockSync.countDown();
                return map.computeIfAbsent("key1", k2 -> "value1");
            });
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    });

    executor.shutdown();
    boolean completed = executor.awaitTermination(5, TimeUnit.SECONDS);
    if (!completed) fail("AB-BA Deadlock detected");
}

Related Issues

• 35794

Comment From: jhoeller

The general recommendation for such a mapping function is that it should not call back into the same map indeed; that's what the introduction of those methods in ConcurrentHashMap came with in JDK 8. And that's what ConcurrentReferenceHashMap is effectively expecting as well now - but yeah, we're violating that usage rule in our own AnnotationTypeMappings, unfortunately. We'll see what we can do about our own use of computeIfAbsent across the codebase there.

A practical way out is to use Map.get for fast-path access where possible, and to combine it with putIfAbsent where uniqueness of the mapped values is not absolutely required.