Recursive ConcurrentHashMap.computeIfAbsent() call never terminates. Bug or "feature"?

Some time ago, I've blogged about a Java 8 functional way of calculating fibonacci numbers recursively, with a ConcurrentHashMap cache and the new, useful computeIfAbsent() method:

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class Test {
    static Map<Integer, Integer> cache = new ConcurrentHashMap<>();

    public static void main(String[] args) {
        System.out.println(
            "f(" + 8 + ") = " + fibonacci(8));
    }

    static int fibonacci(int i) {
        if (i == 0)
            return i;

        if (i == 1)
            return 1;

        return cache.computeIfAbsent(i, (key) -> {
            System.out.println(
                "Slow calculation of " + key);

            return fibonacci(i - 2) + fibonacci(i - 1);
        });
    }
}

I chose ConcurrentHashMap because I was thinking of making this example even more sophisticated by introducing parallelism (which I didn't in the end).

Now, let's increase the number from 8 to 25 and observe what happens:

        System.out.println(
            "f(" + 25 + ") = " + fibonacci(25));

The program never halts. Inside the method, there's a loop that just runs forever:

for (Node<K,V>[] tab = table;;) {
    // ...
}

I'm using:

C:\Users\Lukas>java -version
java version "1.8.0_40-ea"
Java(TM) SE Runtime Environment (build 1.8.0_40-ea-b23)
Java HotSpot(TM) 64-Bit Server VM (build 25.40-b25, mixed mode)

Matthias, a reader of that blog post also confirmed the issue (he actually found it).

This is weird. I would have expected any of the following two:

It works
It throws a ConcurrentModificationException

But just never halting? That seems dangerous. Is it a bug? Or did I misunderstand some contract?

Solution

This is fixed in JDK-8062841.

In the 2011 proposal, I identified this issue during the code review. The JavaDoc was updated and a temporary fix was added. It was removed in a further rewrite due to performance issues.

In the 2014 discussion, we explored ways to better detect and fail. Note that some of the discussion was taken offline to private email for considering the low-level changes. While not every case can be covered, the common cases will not livelock. These fixes are in Doug's repository but have not made it into a JDK release.