Why using parallel streams in static initializer leads to not stable deadlock

Question

CAUTION: it is not a duplicate, please read topic сarefully https://stackoverflow.com/users/3448419/apangin quote:

The real question is why the code sometimes works when it should not. The issue reproduces even without lambdas. This makes me think there might be a JVM bug.

In the comments of https://mcmap.net/q/586287/-deadlock-happens-if-i-use-lambda-in-parallel-stream-but-it-doesn-39-t-happen-if-i-use-anonymous-class-instead-duplicate I tried to find out reasons why code behaves differently from one start to another and participants of that discussion made me piece of of advice to create a separated topic.

Let's consider following source code:

public class Test {
    static {
        System.out.println("static initializer: " + Thread.currentThread().getName());

        final long SUM = IntStream.range(0, 5)
                .parallel()
                .mapToObj(i -> {
                    System.out.println("map: " + Thread.currentThread().getName() + " " + i);
                    return i;
                })
                .sum();
    }

    public static void main(String[] args) {
        System.out.println("Finished");
    }
}

Sometimes(almost always) it leads to deadlock.

Example of output:

static initializer: main
map: main 2
map: ForkJoinPool.commonPool-worker-3 4
map: ForkJoinPool.commonPool-worker-3 3
map: ForkJoinPool.commonPool-worker-2 0

But sometimes it finishes successfully(very rare):

static initializer: main
map: main 2
map: main 3
map: ForkJoinPool.commonPool-worker-2 4
map: ForkJoinPool.commonPool-worker-1 1
map: ForkJoinPool.commonPool-worker-3 0
Finished

or

static initializer: main
map: main 2
map: ForkJoinPool.commonPool-worker-2 0
map: ForkJoinPool.commonPool-worker-1 1
map: ForkJoinPool.commonPool-worker-3 4
map: main 3

Could you explain that behaviour?

Umbrella

@Amongalen it is not a duplicate. I read that topic. – Umbrella

What exactly is not explained in the duplicated question? The answer boils down to: "writing such code can lead to deadlocks. so dont write such code". What else do you think could be added to that? – Nazi

@GhostCat, reason why behaviour is not stable!!! – Umbrella

@GhostCat, my question is more detailed! – Umbrella

GhostCat, I am curious to know about internals and we have guys who know it. At least @apangin – Umbrella

The nature of multi threading is a sensitive to timing. If it would fail all the time, or never, then "more than one thread" wouldn't be hard. – Nazi

@GhostCat, it is clear for me but we can try all possible combination of order and visibility and predict result – Umbrella

all possible combinations ... might work for your small example here, but given any real, realistic problem, you quickly loot at an exponentially growing amount of combinations. and the only thing you could possibly predict is like the chance for a deadlock? – Nazi

@GhostCat, You are correct - I am not able to predict deadlock for real complex code and will use your piece of advice to avoid parallel streams in static initializer. But I am curious to know how it works on simplest example just for my personal enrichment just because it will let me sleep quite) – Umbrella

This is not a duplicate. The real question is why the code sometimes works when it should not. The issue reproduces even without lambdas. This makes me think there might be a JVM bug. I'll check it a bit later. – Trabzon

Agreeing with @Trabzon When we move the System.out.println("Finished"); to the end of the static {} block, we can clearly show that the worker threads managed to execute the lambda body while the class initialization has not completed yet, i.e. that it is not an issue of the stream op returning too early. Note that the example is a bit unfortunate for newer Java versions as starting with Java 9, count() will skip the entire processing and return the predictable size. So .map(i -> { System.out.println("map: "+Thread.currentThread().getName()+" "+i); return 1; }).sum(); might be better. – Guglielma

Using Holger's version, this always deadlocks in oracle jdk1.8.0_121 for me, but never in openJdk jdk-11.0.1. Something definitely changed here. – Atropine

@Atropine you mean you tried with sum()? – Umbrella

for me: java version "1.8.0_111" - oracle jdk – Umbrella

@Umbrella yes, with sum(), because count() skips the processing (starting with java 9, as Holger mentioned). – Atropine

@Atropine Do you know where can I read about that feature? – Umbrella

@Umbrella the JavaDocs, for example: "An implementation may choose to not execute the stream pipeline (either sequentially or in parallel) if it is capable of computing the count directly from the stream source." – Atropine

@apangin, any news? – Umbrella

Yes, I'm convincied now this is a JVM bug apparently related to constant pool resolution. I also found a very old similar bug JDK-4493560 regarding static field access. Seems like the bug was fixed for getstatic/putstatic bytecodes, but not for invokestatic. – Trabzon

Didn't have time to find the root cause yet. I'll post the answer after deeper research that will probably result in a submission of a bug report. – Trabzon

Describe in your question (not in comments) why it is not a duplicate. – Izy

@Raedwald, added to the topic. – Umbrella

@apangin,very interesting research – Umbrella

Answer 1

TL;DR This is a HotSpot bug JDK-8215634

The problem can be reproduced with a simple test case that has no races at all:

public class StaticInit {

    static void staticTarget() {
        System.out.println("Called from " + Thread.currentThread().getName());
    }

    static {
        Runnable r = new Runnable() {
            public void run() {
                staticTarget();
            }
        };

        r.run();

        Thread thread2 = new Thread(r, "Thread-2");
        thread2.start();
        try { thread2.join(); } catch (Exception ignore) {}

        System.out.println("Initialization complete");
    }

    public static void main(String[] args) {
    }
}

This looks like a classic initialization deadlock, but HotSpot JVM does not hang. Instead it prints:

Called from main
Called from Thread-2
Initialization complete

Why this is a bug

JVMS §6.5 requires that upon execution of invokestatic bytecode

the class or interface that declared the resolved method is initialized if that class or interface has not already been initialized

When Thread-2 calls staticTarget, the main class StaticInit is obviously uninitialized (since its static initializer is still running). This means Thread-2 must launch class initialization procedure described in JVMS §5.5. According to this procedure,

2. If the Class object for C indicates that initialization is in progress for C by some other thread, then release LC and block the current thread until informed that the in-progress initialization has completed

However, Thread-2 is not blocked despite the class is in progress of initialization by thread main.

What about other JVMs

I tested OpenJ9 and JET, and they both expectedly deadlock on the above test.
It's interesting that HotSpot also hangs in -Xcomp mode, but not in -Xint or mixed modes.

How it happens

When interpreter first encounters invokestatic bytecode, it calls JVM runtime to resolve the method reference. As a part of this process JVM initializes the class if necessary. After successful resolution the resolved method is saved in the Constant Pool Cache entry. Constant Pool Cache is a HotSpot-specific structure that stores resolved constant pool values.

In the above test invokestatic bytecode that calls staticTarget is first resolved by the main thread. Interpreter runtime skips class initialization, because the class is already being initialized by the same thread. The resolved method is saved in the constant pool cache. The next time when Thread-2 executes the same invokestatic, the interpreter sees that the bytecode is already resolved and uses constant pool cache entry without calling to runtime and thus skips class initialization.

A similar bug for getstatic/putstatic was fixed long ago - JDK-4493560, but the fix did not touch invokestatic. I've submitted the new bug JDK-8215634 to address this issue.

As to the original example,

whether it hangs or not depends on which thread first resolves the static call. If it is main thread, the program completes without a deadlock. If the static call is resolved by one of ForkJoinPool threads, the program hangs.

Update

The bug is confirmed. It is fixed in the upcoming releases: JDK 8u201, JDK 11.0.2 and JDK 12.

Trabzon