Cache recursive compute may deadlock #5439
Description
ConcurrentHashMap used to livelock on a recursive computation in Java 8, and later added early detection to fail. Many years ago, Guava's loader used to deadlock and I added a check via Thread.holdsLock to error instead (see waitForLoadingValue). It appears that map computations may deadlock because it doesn't have this check and instead waits on the pending future.
public void testMerge_recurse() {
cache = CacheBuilder.newBuilder().build();
cache.put(key, "1");
// As we cannot provide immediate checking without an expensive solution, e.g. ThreadLocal,
// instead we assert that a stack overflow error will occur to inform the developer (vs
// a live-lock or deadlock alternative).
BiFunction<String, String, String> mappingFunction =
new BiFunction<String, String, String>() {
int recursed;
@Override public String apply(String oldValue, String value) {
if (++recursed == 2) {
throw new StackOverflowError();
}
return cache.asMap().merge(key, "1", this);
}
};
try {
cache.asMap().merge(key, "1", mappingFunction);
Assert.fail();
} catch (StackOverflowError e) {}
}