Home of The JavaSpecialists' Newsletter

184Deadlocks through Cyclic Dependencies

Posted: 2010-06-04Category: ConcurrencyJava Version: 1.2+Dr. Heinz M. Kabutz
 

Abstract: A common approach to ensuring serialization consistency in thread safe classes such as Vector, Hashtable or Throwable is to include a synchronized writeObject() method. This can result in a deadlock when the object graph contain a cyclic dependency and we serialize from two threads. Whilst unlikely, it has happened in production.

 

Welcome to the 184th edition of The Java(tm) Specialists' Newsletter, sent to you from Chorafakia, where the birds are singing outside and the blue sea smiles at me in the distance (not too much of a distance though :-)). On Wednesday my wife and I visited the police station, where I was asked to hand over my driver's license for two months. The Law of Cretan Driving caught up with me, as I knew it would. I will tell you the whole story later this evening when we cover that law in our Master Course day 1.

NEW: Refactoring to Java 8 Lambdas and Streams Workshop Are you currently using Java 6 or 7 and would like to see how Java 8 can improve your code base? Are you tired of courses that teach you a whole bunch of techniques that you cannot apply in your world? Check out our one day intensive Refactoring to Java 8 Lambdas and Streams Workshop.

Deadlocks through Cyclic Dependencies

In my last newsletter, I asked readers why Vector had a writeObject() method that just did the default, without a readObject() method. The answer is to simply make the writeObject() method synchronized. The quiz was easy, I admit.

One of my readers pointed out that in another JVM implementation, Vector had been coded specifically to avoid a deadlock situation that was found in production. Instead of making the entire method synchronized, they first cloned the Vector with the underlying Object[], but not the elements inside, and then wrote those out in a synchronized block.

This led me to the question - could I generate a deadlock by writing out two Vectors with a cyclic dependency from two threads? Turns out it was easy as pie:

import java.io.*;
import java.util.*;
import java.util.concurrent.*;

public class VectorSerializationDeadlock {
  public static void main(String[] args) {
    ExecutorService pool = Executors.newFixedThreadPool(2);

    final Vector[] vecs = {
        new Vector(),
        new Vector(),
    };
    vecs[0].add(vecs[1]);
    vecs[1].add(vecs[0]);

    for (int i = 0; i < 2; i++) {
      final int threadNumber = i;
      pool.submit(new Callable() {
        public Object call() throws Exception {
          for (int i = 0; i < 1000 * 1000; i++) {
            ObjectOutputStream out = new ObjectOutputStream(
                new NullOutputStream()
            );
            out.writeObject(vecs[threadNumber]);
            out.close();
          }
          System.out.println("done");
          return null;
        }
      });
    }
  }
}

public class NullOutputStream extends OutputStream {
  public void write(int b) throws IOException {
  }
}
  

After a very short time, this causes a deadlock on the Sun's Java Virtual Machine (JVM). On other JVMs, this might not cause a deadlock, as they specifically coded around it.

Update: Java 7 was modified to avoid this deadlock. However, it can still happen if you wrap a LinkedList with a SynchronizedList, such as you can see in my SynchronizedListSerializationDeadlock example.

When I mentioned this in the Java Specialist Club, Olivier Croisier pointed out that there are lots of cases in the JDK with a synchronized writeObject() method:

    - java.beans.beancontext.BeanContextServicesSupport
    - java.beans.beancontext.BeanContextSupport
    - java.io.File
    - java.lang.StringBuffer
    - java.lang.Throwable
    - java.net.Inet6Address
    - java.net.SocketPermission
    - java.net.URL
    - java.util.Hashtable
    - java.util.PropertyPermission
    - java.util.Vector
    - javax.security.auth.kerberos.DelegationPermission
  

He even managed to cause a deadlocks with Throwable, although I would argue that a cyclic dependency in Throwables would be a bug. If you try to print the stack space you will get a StackOverflowError. All he did was replace my Vectors with Throwables:

Throwable t1 = new Throwable("t1");
Throwable t2 = new Throwable("t2", t1);
t1.initCause(t2);

final Throwable[] vecs = {t1,t2};

My Vector example is contrived, meaning that it is extremely unlikely that with a simple object graph you would have two vectors that contain one another. However, with a complicated data structure, it is entirely possible that this could happen. In fact, it has happened to someone in production, which is why the "other" JVM had to code around it specifically.

Synchronized List

Another interesting point is that the List returned by the Collections.synchronizedList() method does not protect itself against concurrent updates in the writeObject() method. Collections.synchronizedCollection returns a class that does also use the synchronized writeObject() approach. In the case of the Synchronized Collection, we might quite easily also cause deadlocks on the write, I imagine, though I have not tried that out.

Here is an example of how we can cause a ConcurrentModificationException with a Synchronized List. This does not happen with the Synchronized Collection.

import java.io.*;
import java.util.*;

public class MangledSynchronizedList {
  public static void main(String[] args) {
    final List<String> synchList = Collections.synchronizedList(
        new ArrayList<String>());
    Collections.addAll(synchList, "hello", "world");
    Thread tester = new Thread() {
      { setDaemon(true); }
      public void run() {
        while (true) {
          synchList.add("hey there");
          synchList.remove(2);
        }

      }
    };
    tester.start();

    while (true) {
      try {
        ObjectOutputStream out = new ObjectOutputStream(
            new NullOutputStream()
        );
        for (int i = 0; i < 100 * 1000; i++) {
          out.writeObject(synchList);
        }
        out.close();
      } catch (IOException e) {
        e.printStackTrace();
        break;
      }
    }
  }
}

After a short while, we see ConcurrentModificationException.

Kind regards

Heinz

 

Related Articles

Browse the Newsletter Archive

About the Author

demo

Java Champion, author of the Javaspecialists Newsletter, conference speaking regular... About Heinz

Java Training

We deliver relevant courses, by top Java developers to produce more resourceful and efficient programmers within their organisations.

Java Consulting

Nobody ever wants to call a Java performance consultant, but with first-hand experience repairing and improving commercial Java applications - JavaSpecialists are a good place to start...

Threading Emergency?

If your system is down, we will review it for 15 minutes and give you our findings for just 1 € without any obligation.