Search code examples
javaconcurrencyconcurrenthashmap

ConcurrentHashMap throws IllegalStateException: Recursive update

First of all, I am aware of several similar (53998845, 71087512, 71269113) and related (28840047, 44224952) questions, but I believe that none of them exactly captures the same situation that I am encountering.

I am using a ConcurrentHashMap as a cache for some runtime-generated Java classes. Specifically, I use computeIfAbsent to either return a previously generated class, or generate the class on the fly. In some circumstances, this call throws an IllegalStateException: Recursive update. An example stack trace looks like this:

java.lang.IllegalStateException: Recursive update
at java.base/java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1742)
at pro.projo.internal.rcg.RuntimeCodeGenerationHandler.getImplementationOf(RuntimeCodeGenerationHandler.java:151)
at pro.projo.Projo.getImplementationClass(Projo.java:451)
at pro.projo.Projo.getImplementationClass(Projo.java:438)
at fxxx.natives.bootstrap.Bootstrap$1.lambda$configure$2(Bootstrap.java:63)
at java.base/java.util.ArrayList.forEach(ArrayList.java:1510)
at fxxx.natives.bootstrap.Bootstrap$1.configure(Bootstrap.java:76)
at com.google.inject.AbstractModule.configure(AbstractModule.java:66)
at com.google.inject.spi.Elements$RecordingBinder.install(Elements.java:409)
at com.google.inject.spi.Elements.getElements(Elements.java:108)
at com.google.inject.internal.InjectorShell$Builder.build(InjectorShell.java:160)
at com.google.inject.internal.InternalInjectorCreator.build(InternalInjectorCreator.java:107)
at com.google.inject.Guice.createInjector(Guice.java:87)
at com.google.inject.Guice.createInjector(Guice.java:69)
at com.google.inject.Guice.createInjector(Guice.java:59)
at fxxx.natives.bootstrap.Bootstrap.<init>(Bootstrap.java:89)
at java.base/jdk.internal.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
at java.base/jdk.internal.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:62)
at java.base/jdk.internal.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:45)
at java.base/java.lang.reflect.Constructor.newInstanceWithCaller(Constructor.java:500)
at java.base/java.lang.reflect.Constructor.newInstance(Constructor.java:481)
at java.base/java.util.ServiceLoader$ProviderImpl.newInstance(ServiceLoader.java:782)
at java.base/java.util.ServiceLoader$ProviderImpl.get(ServiceLoader.java:724)
at java.base/java.util.ServiceLoader$3.next(ServiceLoader.java:1396)
at java.base/java.util.ServiceLoader.findFirst(ServiceLoader.java:1811)
at fxxx.bootstrap.Bootstrap.load(Bootstrap.java:34)
at fxxx.test.junit.FxxxTestClassTestDescriptor.instantiateTestClass(FxxxTestClassTestDescriptor.java:27)

As far as I am aware, I am not violating ConcurrentHashMap.computeIfAbsent's requirement that "The mapping function must not modify this map during computation", as that function is a pure function without side effects. For the other requirement, that "the computation should be short and simple", my code's compliance is not as clear cut, since generating the classes on the fly is definitely an involved and expensive process (hence the caching).

I do, however, believe that the exception's claimed "Recursive update" is an incorrect assessment of what is actually going on here. If that were indeed the case, I would expect to see multiple occurrences of my code's call to CHM.computeIfAbsent in the stack trace, but this is not what I see (not in the example stack trace, or any other stack trace that I've seen with this problem).

The code in CHM is as follows:

1738            Node<K,V> pred = e;
1739            if ((e = e.next) == null) {
1740                if ((val = mappingFunction.apply(key)) != null) {
1741                    if (pred.next != null)
1742                        throw new IllegalStateException("Recursive update");
1743                    added = true;
1744                    pred.next = new Node<K,V>(h, key, val);
1745                }
1746                break;
1747            }

From the stack trace, I already know that this is not a recursive call to computeIfAbsent from within another computeIfAbsent invocation. The code saves a reference to the previous node as pred (line 1738) and then updates e to the next node (line 1739). Since we made it past the if check, we know that the original e's next value was null, therefore pred.next should at this point also be null. However, a subsequent check (line 1741) reveals that pred next is no longer null (which triggers the exception). As a recursive update is not corroborated by the stack trace, I am assuming that this must actually be a concurrent update instead. It appears that the original e object, now known as pred, has its next pointer changed by another thread (java.util.concurrent.ConcurrentHashMap.Node produces mutable objects, unfortunately).

I am using CHM for the one reason that this caching mechanism must be thread-safe and have low overhead (i.e., no blanket locking). I would expect concurrent update of the cache to work. However, in this particular scenario, concurrent access does not work, and seems to be incorrectly classified as a recursive update instead.

For further context, my own code that invokes computeIfAbsent looks like this:

public Class<? extends _Artifact_> getImplementationOf(Class<_Artifact_> type, boolean defaultPackage)
{
    return implementationClassCache.computeIfAbsent(type, it -> generateImplementation(it, defaultPackage));
}

This code is from a utility library that needs to work on Java 8, but I've only ever seen the exception happen when the code is used from another project that's running on Java 11.

Is this another bug in ConcurrentHashMap or am I overlooking something regarding the proper use of this class?

Solution

  • Alright, mea culpa, false alarm, after some further debugging it turns out that ConcurrentHashMap works as designed. There was a rarely executed code branch, where the runtime code generator made use of itself to create certain classes (I should have foreseen that this would cause trouble at some point). The problem only surfaced when the particular class was not in the cache yet, i.e. there was a recursive call but no update, which made it look like a race condition (which it technically was).

    My fallacy when analyzing the stack traces was that the offending update (of course!) had already popped of the stack since it already had already been completed. The first update (which caused the problem) succeeded just fine, but it was the second update that threw the exception, and, by then, the offending earlier update was no longer on the stack.

    The way I tracked it down in the end was by using an instrumented anonymous subclass of CHM. Instead of just initializing the map with new ConcurrentHashMap<Class<_Artifact_>, Class<? extends _Artifact_>>();, I used:

    new ConcurrentHashMap<Class<_Artifact_>, Class<? extends _Artifact_>>()
{
    @Override
    public Class<? extends _Artifact_> computeIfAbsent(Class<_Artifact_> key, Function<? super Class<_Artifact_>, ? extends Class<? extends _Artifact_>> mappingFunction)
    {
        Stream<StackTraceElement> stack = Stream.of(new Throwable().getStackTrace());
        if (stack.filter(element -> element.getMethodName().equals("computeIfAbsent")).count() > 2)
        {
            throw new RuntimeException("recursive update happening!");
        }
        return super.computeIfAbsent(key, mappingFunction);
    }   
};

    Normally, there should only be two occurrences of computeIfAbsent in the stack (one for the modified implementation in the subclass, and one for the original implementation called via super). If there were more than two, this means there was a recursive update (unless there happened to be multiple different maps involved). This pinpointed the source of the problem pretty quickly, and I thought it might be worth sharing (alternatively, some debuggers may have a feature that can be used to the same effect).