Skip to content

Cache recursive compute may deadlock #5439

Open

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) {}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Assignees

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions