Vavr: Deadlock on Static Class Initialization of Iterator

[eremeev]

javaslang.collection.Iterator has public final static field EMPTY which is initialized by an instance of anonymous class (extends AbstractIterator). If AbsctractorIterator is loaded in another thread, it may lead to deadlock.

See: https://bugs.openjdk.java.net/browse/JDK-8037567
and the snippet for more information.

In the snippet:

• Thread 1: loads Iterator -> AbstractorIterator
• Thread 2: loads A -> AbstractIterator -> Iterator

The snippet almost always hangs.

package slang;

import javaslang.collection.AbstractIterator;
import javaslang.collection.Iterator;

/**
 * Created by aeremeev on 25.12.16.
 */
public class DeadlockTest {

    public static void main(String[] args) {
        new Thread(Iterator::empty).start();
        new A();
        System.out.println("Success");
    }

    private static class A extends AbstractIterator<Void> {
        @Override
        protected Void getNext() {
            return null;
        }

        @Override
        public boolean hasNext() {
            return false;
        }
    }
}

[igoonich]

Here is one more test, which can be used to reproduce this issue:

public class JavaslangClassInitializationDeadlockTest {

    @Test(timeout = 5_000)
    public void testConcurrentClassInitialization() throws InterruptedException {
        ExecutorService executorService = Executors.newFixedThreadPool(2);
        executorService.execute(new ClassInitializer("javaslang.collection.Iterator"));
        executorService.execute(new ClassInitializer("javaslang.collection.AbstractIterator"));
        executorService.shutdown();
        // try to access javaslang iterator and it will hang
        Iterator.empty().iterator();
    }

    public static class ClassInitializer implements Runnable {
        private String type;

        public ClassInitializer(String type) {
            this.type = type;
        }

        public void run() {
            try {
                Class.forName(type);
            } catch (ClassNotFoundException e) {
                throw new RuntimeException(e);
            }
        }
    }
}

[igoonich]

Just in case, here is a thread dump from our environment, taken at the point of time when we got such a deadlock last time:

"health-checker" #192 daemon prio=5 os_prio=0 tid=0x00007ffba8101000 nid=0x5375 in Object.wait() [0x00007ffba1391000]
   java.lang.Thread.State: RUNNABLE
        at javaslang.collection.Iterator.<clinit>(Iterator.java:51)
    ...
        at java.util.TimerThread.mainLoop(Timer.java:555)
        at java.util.TimerThread.run(Timer.java:505)

"Thread-4-fail-fast" #31 prio=5 os_prio=0 tid=0x00000000016fa800 nid=0x52d7 in Object.wait() [0x00007ffbaf4f5000]
   java.lang.Thread.State: RUNNABLE
        at javaslang.collection.Traversable.iterator(Traversable.java:553)
        at javaslang.Value.forEach(Value.java:246)
        ...
        at java.lang.Thread.run(Thread.java:745)

[igoonich]

Similar issue in guava was fixed recently in 19.0.0 - https://github.com/google/guava/issues/1977.

[eremeev]

Find the suggested fix. Anyway, the fix does not save from deadlock if the anonymous class is loaded via reflection. In my opinion EMPTY should be deprecated and moved to another class in some future release.

diff --git a/javaslang/src/main/java/javaslang/collection/Iterator.java b/javaslang/src/main/java/javaslang/collection/Iterator.java
index 9225b84..3d140b2 100644
--- a/javaslang/src/main/java/javaslang/collection/Iterator.java
+++ b/javaslang/src/main/java/javaslang/collection/Iterator.java
@@ -54,16 +54,20 @@ public interface Iterator<T> extends java.util.Iterator<T>, Traversable<T> {
     /**
      * The empty Iterator.
      */
-    Iterator<Object> EMPTY = new AbstractIterator<Object>() {
-
+    Iterator<Object> EMPTY = new Iterator<Object>() {
         @Override
         public boolean hasNext() {
             return false;
         }

         @Override
-        public Object getNext() {
-            return null;
+        public Object next() {
+            throw new NoSuchElementException("next() on empty iterator");
+        }
+
+        @Override
+        public String toString() {
+            return stringPrefix() + "()";
         }
     };

diff --git a/javaslang/src/test/java/javaslang/collection/IteratorTest.java b/javaslang/src/test/java/javaslang/collection/IteratorTest.java
index 20bc239..aacb207 100644
--- a/javaslang/src/test/java/javaslang/collection/IteratorTest.java
+++ b/javaslang/src/test/java/javaslang/collection/IteratorTest.java
@@ -8,16 +8,17 @@ package javaslang.collection;
 import javaslang.Tuple;
 import javaslang.Tuple2;
 import javaslang.Tuple3;
-import javaslang.Value;
 import javaslang.control.Option;
 import org.assertj.core.api.Assertions;
 import org.assertj.core.api.IterableAssert;
 import org.assertj.core.api.ObjectAssert;
+import org.junit.Assert;
 import org.junit.Test;

 import java.math.BigDecimal;
 import java.util.ArrayList;
 import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicBoolean;
 import java.util.function.Function;
 import java.util.function.Supplier;
 import java.util.stream.Collector;
@@ -515,4 +516,22 @@ public class IteratorTest extends AbstractTraversableTest {
         // Iterator equality undefined
     }

+    @Test(timeout = 5_000)
+    public void testDeadlock() throws InterruptedException {
+        AtomicBoolean failed = new AtomicBoolean();
+        Thread thread = new Thread(() -> {
+            try {
+                Class.forName("javaslang.collection.AbstractIterator");
+            } catch (Exception e) {
+                e.printStackTrace();
+                failed.set(true);
+            }
+        });
+        thread.start();
+
+        Iterator.empty();
+
+        thread.join();
+        Assert.assertFalse(failed.get());
+    }
 }

[danieldietrich]

Hi @eremeev,
many thanks for reporting the bug and providing us with such detailed information. This is really an interesting one!
You're right, the EMPTY instance should 1) not be public and 2) be moved to some other place.
We will deprecate it.
However, in the past I was not 100% satisfied with making AbstractIterator public available. Maybe we should use it only internally.

[danieldietrich]

@eremeev on my local machine all tests pass when we move Iterator.EMPTY to ItertatorModule (also located in Iterator.java):

interface Iterator ... {
    ...
}

interface IteratorModule {

    /**
     * The empty Iterator.
     */
    Iterator<Object> EMPTY = new AbstractIterator<Object>() {

        @Override
        public boolean hasNext() {
            return false;
        }

        @Override
        public Object getNext() {
            return null;
        }
    };

    ...
}

Do you see any drawbacks regarding that solution? (Of course Iterator.EMPTY should be implemented as you suggested and be deprecated)

[eremeev]

Looks good, but I would prefer package-private final class instead of interface, and Iterator#empty should return IteratorModule.EMPTY.
Also, I like how EmptyIterator is done in JDK (See java.util.Collections#emptyIterator).