Java Specialists' Java Training Europehome of the java specialists' newsletter

The Java Specialists' Newsletter
Issue 1842010-06-04 Category: Concurrency Java version: 1.2, 1.3, 1.4, 1.5, 6+

GitHub Subscribe Free RSS Feed

Deadlocks through Cyclic Dependencies

by 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.

In about 6.5 hours from now, we are running the first day of the Java Specialist Master Course as a welcome gift for members of our Java Specialist Club. If you have not signed up yet, please do. I would not want you to miss out on this opportunity. And yes, it is completely free for club members. The course runs from 13:00-21:00 GMT today on June 4th. Once you have signed up to the club, please find the registration link by visiting our club forum. Please note that the webinar requires either Mac OS X or Windows. Linux is currently not supported.

NEW: Please see our new "Extreme Java" course, combining concurrency, a little bit of performance and Java 8. Extreme Java - Concurrency & Performance for Java 8.

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

Concurrency Articles Related Java Course

Extreme Java - Concurrency and Performance for Java 8
Extreme Java - Advanced Topics for Java 8
Design Patterns
In-House Courses

© 2010-2016 Heinz Kabutz - All Rights Reserved Sitemap
Oracle and Java are registered trademarks of Oracle and/or its affiliates. Other names may be trademarks of their respective owners. JavaSpecialists.eu is not connected to Oracle, Inc. and is not sponsored by Oracle, Inc.