Deadlock in class initialization specification, JLS 2nd ed. 12.4.2

Name: gm110360 Date: 07/16/2003


FULL PRODUCT VERSION :
java version "1.4.1"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.1-b21)
Java HotSpot(TM) Client VM (build 1.4.1-b21, mixed mode)


FULL OPERATING SYSTEM VERSION :
Windows NT Version 4.0
service pack 6

A DESCRIPTION OF THE PROBLEM :
When a superclass contains a static reference to one of its
subclasses, a deadlock can occur during class
initialization. This happens when one thread initializes
the parent class and another thread initializes the child
class, near the same time.

This is actually a bug in the algorithm given for class
initialization in section 12.4.2 of the Java Language
Specification, second edition. That is, the JVM appears to
implement the spec as written; but the spec has this
inherent deadlock in its algorithm.

I propose the following change to the algorithm, which
eliminates the deadlock by always setting locks from
superclass to subclass. (It will not eliminate all possible
class-initialization deadlocks, because two arbitrary
classes can statically refer to each other. But it will
eliminate the superclass-subclass deadlock illustrated by
the accompanying code.) Replace steps 6 and 7 of the
algorithm with the following:

6. If the Class object represents a class rather than an
interface, and the superclass of this class has not yet been
initialized, then release the lock on this Class object and
recursively perform this entire procedure for the
superclass. If necessary, verify and prepare the superclass
first. If the initialization of the superclass completes
abruptly because of a thrown exception, then lock this Class
object, label it erroneous, notify all waiting threads,
release the lock, and complete abruptly, throwing the same
exception that resulted from initializing the superclass.
If the initialization of the superclass completes normally,
then return to step 1. Note that this step will not be
repeated the next time through.

[Also note that the check of whether the superclass has been
initialized already must be done without locking the
superclass. Since this is a boolean, no lock is required
for safety.]

7. Otherwise, record the fact that initialization of the
Class object is now in progress by the current thread and
release the lock on the Class object.


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
1. Compile and run the accompanying code
2. Note that it does not complete.
3. Interrupt to get a thread dump, and note where it is
deadlocked.

EXPECTED VERSUS ACTUAL BEHAVIOR :
I would expect this output from the sample code:

Initializing A from thread Thread-1
Initializing B from thread Thread-1
In A.method() from thread Thread-1
In B.method() from thread Thread-2


What I actually see is just the first line, followed by an
indefinite hang. Generating a thread dump I see:

Full thread dump Java HotSpot(TM) Client VM (1.4.1-b21 mixed
mode):

"DestroyJavaVM" prio=5 tid=0x00773C80 nid=0x156 waiting on
condition [0..6fad8]

"Thread-2" prio=5 tid=0x00773EA0 nid=0x1dd in Object.wait()
[ae3f000..ae3fd8c]
at ClinitDeadlock$2.run(ClinitDeadlock.java:10)

"Thread-1" prio=5 tid=0x00771070 nid=0x185 in Object.wait()
[adff000..adffd8c]
at A.<clinit>(A.java:18)
at ClinitDeadlock$1.run(ClinitDeadlock.java:7)

"Signal Dispatcher" daemon prio=10 tid=0x0076C6A0 nid=0x23d
waiting on condition [0..0]

"Finalizer" daemon prio=9 tid=0x007686A0 nid=0xd5 in
Object.wait() [acbf000..acbfd8c]
at java.lang.Object.wait(Native Method)
- waiting on <02B60498> (a java.lang.ref.ReferenceQueue$Lock)
at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:111)
- locked <02B60498> (a java.lang.ref.ReferenceQueue$Lock)
at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:127)
at
java.lang.ref.Finalizer$FinalizerThread.run(Finalizer.java:159)

"Reference Handler" daemon prio=10 tid=0x007677B0 nid=0x1d3
in Object.wait() [ac7f000..ac7fd8c]
at java.lang.Object.wait(Native Method)
- waiting on <02B60388> (a java.lang.ref.Reference$Lock)
at java.lang.Object.wait(Object.java:426)
at
java.lang.ref.Reference$ReferenceHandler.run(Reference.java:113)
- locked <02B60388> (a java.lang.ref.Reference$Lock)

"VM Thread" prio=5 tid=0x00766AA0 nid=0x24f runnable

"VM Periodic Task Thread" prio=10 tid=0x0076BBA0 nid=0x19c
waiting on condition
"Suspend Checker Thread" prio=10 tid=0x0076B160 nid=0x245
runnable


REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
I have three files, ClinitDeadlock.java, A.java, and B.java.

ClinitDeadlock.java:

public class ClinitDeadlock
{
    public static void main( String[] args ) {
        new Thread() {
            public void run() { A.method(); }
        }.start();
        new Thread() {
            public void run() { B.method(); }
        }.start();
    }
}


A.java:

public abstract class A
{
    public static void method() {
        System.out.println( "In A.method() from thread "
                            +Thread.currentThread().getName() );
    }

    static {
        System.out.println( "Initializing A from thread "
                            +Thread.currentThread().getName() );
        try {
            Thread.sleep( 1000 );
        }
        catch (InterruptedException e) {}
    }

    public static final A globalA = new B();
}


And B.java:

public class B extends A
{
    public static void method() {
        System.out.println( "In B.method() from thread "
                            +Thread.currentThread().getName() );
    }

    static {
        System.out.println( "Initializing B from thread "
                            +Thread.currentThread().getName() );
        try {
            Thread.sleep( 1000 );
        }
        catch (InterruptedException e) {}
    }
}

---------- END SOURCE ----------

CUSTOMER WORKAROUND :
The only reliable workaround is never to statically refer to
child classes from the parent. One could argue that it is
somehow inherently bad design to do so; however, there are
cases where this is the most elegant design possible. The
best example of this I know of is a family of classes
representing intervals. The root of the family is an
abstract class; in the original design the root class
included a couple of constants for the empty interval and
the "everything" interval, which were instances of a
concrete subclass. The root class is in fact the best place
for these constants, but this bug forced a workaround of
putting the constants in the concrete subclass.
(Incident Review ID: 166849)
======================================================================