184Deadlocks Through Cyclic Dependencies

Author: Dr. Heinz M. KabutzDate: 2010-06-04Java Version: 1.2Category: Concurrency

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.

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

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 also uses 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

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive