Saturday, February 9, 2013

Spring context initialization fails after AspectJ upgrade

I was upgrading project's version of AspectJ to 1.7.1 to get Java 7 support. Nobrainer. But after the upgrade the application was not able to start up because of org.springframework.beans.factory.BeanCreationException: Error creating bean with name ... No matching factory method found: factory method 'aspectOf()' failure during Spring context initialization. Trying different versions showed the problem appeared in 1.6.11 version. Problem was in change aop.xml config file semantic.

Originally this kind of aop.xml was OK:

<aspectj>
    <weaver>
        <include within="cz.kara.foo..*"/>
    </weaver>
    <aspects>
        <aspect name="cz.kara.aspects.FooAspect"/>
    </aspects>
</aspectj>

But with a newer version the aop.xml has to be changed like this:

<aspectj>
    <weaver>
        <include within="cz.kara.foo..*"/>
        <include within="cz.kara.aspects..*"/>
    </weaver>
    <aspects>
        <aspect name="cz.kara.aspects.FooAspect"/>
    </aspects>
</aspectj>

While pre-1.6.11 the aspects did not need to be specified in weaver include section, they have to be specified there in later versions.

Saturday, June 25, 2011

Screenshots in JBehave reports

JBehave with Selenium is able to create screenshots when scenario fails. It is very useful feature when you want to see what was happening on the screen when the test failed. Unfortunately JBehave Web documentation is not very helpful at this point.

The trader-runner-webdriver project from the examples in JBehave Web source code contains example of the solution. The screenshot feature is implemented through WebDriverScreenshotOnFailure class. This class just needs to be added to the step candidate list.

JBehave also supports linking these screenshots into the HTML report. Example is available in the tutorial project. This behaviour can be added to above trader-runner-webdriver example project very easily. There is a class WebDriverHtmlOutput in the JBehave/Selenium module which extends HtmlOutput. All you need to do is to replace HTML format in you format configuration with WebDriverHtmlOutput.WEB_DRIVER_HTML format. Modify TraderWebStories.configuration() - change:

    .withFormats(CONSOLE, TXT, HTML, XML));

to

    .withFormats(CONSOLE, TXT, WebDriverHtmlOutput.WEB_DRIVER_HTML, XML));

This solution is not perfect though. WebDriverScreenshotOnFailure class does not play well with stories executed with "doIgnoreFailureInStories(true)" flag (this setting is useful when you want to have report generated even when scenarios fail). There is a bug in JBehave (3.4.5). In case multiple scenarios in story fail, all screenshots are saved to the same file, i.e. rewriting each other. If you then try to open these screenshots from the HTML report first link opens but it will show a screenshot for the last failure, rest of the links won't work at all.

Trader-runner-webdriver project can be simply modified to show this bug:

  1. Add this method to TraderWebStories class:
        @Before
        public void init(){
            configuredEmbedder().embedderControls()
            .doGenerateViewAfterStories(true)
            .doIgnoreFailureInStories(true)
            .doIgnoreFailureInView(false);
        }
  2. Introduce failures to existing stories - add exception throwing to TraderWebSteps.stepsFound(List stepsOrMethods).

Run test and check report for the screenshot problems. You will see the the second link does not work at all and only single screenshot file exists.

There is a workaround for this problem:

  1. As WebDriverScreenshotOnFailure class does not provide required screenshots it is removed. Modify method TraderWebStories.stepsFactory() - remove WebDriverScreenshotOnFailure class from the list of step candidates.
  2. Create a new class ScreenshootingHtmlOutput which extends class WebDriverHtmlOutput. This class will extend failure handling with screenshot generation by calling WebDriverScreenshotOnFailure:
    public class ScreenshootingHtmlOutput extends WebDriverHtmlOutput {
    
        private WebDriverScreenshotOnFailure screenshotMaker;
    
        public ScreenshootingHtmlOutput(PrintStream output,
                StoryReporterBuilder reporterBuilder,
                WebDriverProvider webDriverProvider) {
            super(output, reporterBuilder.keywords());
            screenshotMaker = new WebDriverScreenshotOnFailure(
                webDriverProvider);
        }
    
        @Override
        public void failed(String step, Throwable storyFailure) {
            super.failed(step, storyFailure);
            try {
                UUIDExceptionWrapper uuidWrappedFailure =
                    (UUIDExceptionWrapper) storyFailure;
                screenshotMaker.afterScenarioFailure(uuidWrappedFailure);
            } catch (Exception e) {
                System.out.println("Screenshot failed");
            }
        }
    }
  3. Then a new format class is needed:
    public class ScreenshootingHtmlFormat extends Format{
        private WebDriverProvider webDriverProvider;
    
        public ScreenshootingHtmlFormat(WebDriverProvider webDriverProvider) {
            super("HTML");
            this.webDriverProvider = webDriverProvider;
        }
    
        @Override
        public StoryReporter createStoryReporter(
                FilePrintStreamFactory factory,
                StoryReporterBuilder builder) {
            factory.useConfiguration(
                    builder.fileConfiguration("html"));
            return new ScreenshootingHtmlOutput(factory.createPrintStream(),
                        builder, webDriverProvider)
                    .doReportFailureTrace(builder.reportFailureTrace())
                    .doCompressFailureTrace(builder.compressFailureTrace());
        }
    }
  4. And finally you need to modify the TraderWebStories class. Add field:
        private Format screenshootingFormat =
                new ScreenshootingHtmlFormat(driverProvider);
    
    and replace WebDriverHtmlOutput.WEB_DRIVER_HTML with screenshootingFormat so you get:
                        .withFormats(CONSOLE, TXT, screenshootingFormat, XML));
    

It is not very nice solution but it works. Hopefully the JBehave bug is going to be fixed soon and this nasty workaround won't be needed any more.

Thursday, April 28, 2011

Flat-Combining NUMA Locks paper

There is a new interesting paper Flat-Combining NUMA Locks at David Dice's blog. The new algorithm improves performance in case of high contention by better exploitation of data locality. Lock handover is not done randomly but preferably between threads with the same locality (but avoiding starvation and fairness issues). Great reading.

Trivia - One of the co-authors is Nir Shavit. He is also co-author of the brilliant The Art of Multiprocessor Programming. If I had not read the book I would have strugled with the above paper much more...

Monday, March 14, 2011

Java static initialization - part 2

This is a follow-up of Java static initialization - part 1. Part 1 went through §12.4.1 When Initialization Occurs of Java language specification.

This post will go throught the rest of 12.4 chapter starting with the section "12.4.2 Detailed Initialization Procedure". As name suggests this section provides detailed description of how a class or interface is initialized. It starts with rationale.

12.4.2 Detailed Initialization Procedure

Because the Java programming language is multithreaded, initialization of a class or interface requires careful synchronization, since some other thread may be trying to initialize the same class or interface at the same time. There is also the possibility that initialization of a class or interface may be requested recursively as part of the initialization of that class or interface; for example, a variable initializer in class A might invoke a method of an unrelated class B, which might in turn invoke a method of class A.

After explanation why this level of detail is needed it describes the procedure itself. This procedure can be rewritten in this Java pseudo-code (comments refer to procedure points):

void initializeClass(Clazz clazz) {
    boolean repeat = false;
    while (repeat) {
        repeat = false;
        synchronized (clazz) { // 1.
            InitializationStatus status = clazz.getInitializationStatus();
            switch (status) {
            case PREPARED: //6.
                clazz.setInitStatus(InitializationStatus.INITIALIZING);
                clazz.setInitThread(Thread.currentThread());
                break;
            case INITIALIZING:
                if (clazz.getInitThread() == Thread.currentThread()) { // 3.
                    return;
                } else {    // 2.
                    try {
                        clazz.wait();
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                        throw new NoClassDefFoundError();
                    }
                    repeat = true;
                }
                break;
            case INITIALIZED: // 4.
                return;
            case ERRONEOUS:  // 5.
                throw new NoClassDefFoundError();
            }
        }
    }
    try {
        Clazz superClass = clazz.getSuperclass();  // 7.
        if (superClass != null) {
            initializeClass(superClass);
        }
    } catch(Throwable t) {
        synchronized (clazz){
            clazz.setInitStatus(InitializationStatus.ERRONEOUS);
            clazz.notifyAll();
        }
        throw t;
    }
    try {
        clazz.getClassLoader().desiredAssertionStatus(clazz.getName()); // 8.
        clazz.<clinit>();  // 9.
        synchronized (clazz){  // 10.
            clazz.setInitStatus(InitializationStatus.INITIALIZED);
            clazz.notifyAll();
        }
    } catch(Throwable t) {
        if (!(t instanceof Error)){ // 11.
            try{
                t = new ExceptionInInitializerError(t);
            } catch (OutOfMemoryError oome){
                t = oome;
            }
        }
        synchronized (clazz){ // 12.
            clazz.setInitStatus(InitializationStatus.ERRONEOUS);
            clazz.notifyAll();
        }
        throw t;
    }
}

The implementation of the Java virtual machine is responsible for taking care of synchronization and recursive initialization by using the following procedure. It assumes that the Class object has already been verified and prepared, and that the Class object contains state that indicates one of four situations:

  • This Class object is verified and prepared but not initialized.
  • This Class object is being initialized by some particular thread T.
  • This Class object is fully initialized and ready for use.
  • This Class object is in an erroneous state, perhaps because initialization was attempted and failed.

The procedure for initializing a class or interface is then as follows:

  1. Synchronize (§14.19) on the Class object that represents the class or interface to be initialized. This involves waiting until the current thread can obtain the lock for that object (§17.1).
  2. If initialization is in progress for the class or interface by some other thread, then wait on this Class object (which temporarily releases the lock). When the current thread awakens from the wait, repeat this step.
  3. If initialization is in progress for the class or interface by the current thread, then this must be a recursive request for initialization. Release the lock on the Class object and complete normally.
  4. If the class or interface has already been initialized, then no further action is required. Release the lock on the Class object and complete normally.
  5. If the Class object is in an erroneous state, then initialization is not possible. Release the lock on the Class object and throw a NoClassDefFoundError.
  6. 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.
  7. Next, if the Class object represents a class rather than an interface, and the superclass of this class has not yet been initialized, then 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.
  8. Next, determine whether assertions are enabled (§14.10) for this class by querying its defining class loader.
  9. Next, execute either the class variable initializers and static initializers of the class, or the field initializers of the interface, in textual order, as though they were a single block, except that final class variables and fields of interfaces whose values are compile-time constants are initialized first (§8.3.2.1, §9.3.1, §13.4.9).
  10. If the execution of the initializers completes normally, then lock this Class object, label it fully initialized, notify all waiting threads, release the lock, and complete this procedure normally.
  11. Otherwise, the initializers must have completed abruptly by throwing some exception E. If the class of E is not Error or one of its subclasses, then create a new instance of the class ExceptionInInitializerError, with E as the argument, and use this object in place of E in the following step. But if a new instance of ExceptionInInitializerError cannot be created because an OutOfMemoryError occurs, then instead use an OutOfMemoryError object in place of E in the following step.
  12. Lock the Class object, label it erroneous, notify all waiting threads, release the lock, and complete this procedure abruptly with reason E or its replacement as determined in the previous step.

(Due to a flaw in some early implementations, a exception during class initialization was ignored, rather than causing an ExceptionInInitializerError as described here.)

As mentioned above this detail description allows us to reason about static initialization scenarios including circular dependencies.

Let's have 2 classes A and B:

class A {
    static int Y = B.Y;
    static int X = 10;
}

class B {
    static int X = A.X;
    static int Y = 25;
}

It seems quite straightforward what values these static fields are going to have - A.X and B.X will be initialized to 10 and A.Y and B.Y will be initialized to 25. But it is not so (obviously - otherwise it would not be worth mentioning). When running this program:

public class TestCircularInitialization {
    public static void main(String[] args) {
        int x = A.X;
        System.out.println("X = " + B.X);
        System.out.println("Y = " + A.Y);
    }
}

the output is:

X = 0
Y = 25

So what happens. int x = A.X will start A initialization. Initialization will try to execute line 2 in the class A. That will start B initialization and executing line 7. And that will cause another try to initialize A. But A is in the INITIALIZING state and the initializing thread is the same as the current one (point 3. of the procedure). Thread returns to line 7. and sets B.X with current value of A.X - the default value 0. Then it executes line 8 and ends B initialization where B.X = 0 and B.Y = 25. A initialization continues and A.Y is set to 25. And then A.X is set to 10 at last.

Interesting thing happens when TestCircularInitialization is modified a bit - int x = B.X:

public class TestCircularInitialization {
    public static void main(String[] args) {
        int x = B.X;
        System.out.println("X = " + B.X);
        System.out.println("Y = " + A.Y);
    }
}

the output is then:

X = 10
Y = 0

The explanation is equivalent to the previous example.

The example demonstrated why circular dependency is dangerous. The real behaviour is not obvious and depends on the execution path. The fix in this case would be reordering of static fields:

class A {
    static int X = 10;
    static int Y = B.Y;
}

class B {
    static int Y = 25;
    static int X = A.X;
}

In this form the real behaviour matches the expected behaviour. The best solution would be to avoid circular dependency altogether though.

The specification declares Class object is used for synchronization of class initialization state but it is not necessary so in reality. (Note: Following examples are JVM specific. Sun JDK 1.6.0_24 is used in the examples below.)

Let's run the following program:

class Foo {
    static {
        System.out.println("Foo initialized");
    }
}

public class TestStaticInitLockingBasic {
    public static void main(String[] args) throws InterruptedException {
        synchronized (Foo.class) {
            System.out.println("Foo locked");
            new Thread(new Runnable() {
                public void run() {
                    new Foo();
                }
            }).start();
            Thread.sleep(2000);
            System.out.println("Unlocking Foo");
        }
    }
}

This program locks on Foo.class object at first then it fires second thread. 1st thread then sleeps for 2s. 2nd thread cause Foo static initialization. At that moment 2nd thread should wait for 1st thread to unlock Foo.class and then continue with initialization. So at the end the console should contain:

Foo locked
Unlocking Foo
Foo initialized

But program prints:

Foo locked
Foo initialized
Unlocking Foo

It proves JVM does not use Class object as prescribed in specification. Now let's modify program a bit:

class Foo {
    static {
        synchronized (Foo.class) {
            System.out.println("Foo initialized");
        }
    }
}

public class TestStaticInitLocking {
    public static void main(String[] args) throws InterruptedException {
        synchronized (Foo.class) {
            System.out.println("Foo locked");
            new Thread(new Runnable() {
                public void run() {
                    new Foo();
                }
            }).start();
            Thread.sleep(2000);
            System.out.println("Main thread woke up - creating Foo instance");
            new Foo();
            System.out.println("Unlocking Foo");
        }
    }
}

There are 2 differences from previous code - Foo's static initialization has additional synchronization on Foo.class and main thread is creating the new Foo instance. Program will print:

Foo locked
Main thread woke up - creating Foo instance

and then program hangs. The program is using only a single lock and JVM is expected to use a synchronization for static initialization. It means JVM is using some lock other than Foo.class and program hangs because the threads are locking Foo.class and JVM's lock in different ordering. Another interesting thing is that thread dump does not detect any deadlock. This means this internal JVM's lock is not using standard JVM's lock mechanisms.

Existing JVM implementation apparently breaks JLS specification but this situation should be officially fixed soon. Surprisingly it won't happen by JVM implementation change but by JVM specification change. A new draft version of JVM specification (JSR‑000924 Java Virtual Machine Specification Java SE 7 Maintenance Review Draft 3) includes updated version of initialization procedure. This version already don't insist on using Class object for synchronization. The Draft changelog comments on this change:

The initialization procedure for a class or interface relaxes the requirement to lock on the user-visible Class object of the class or interface being initialized. Few JVM implementations actually lock on this object. Most use an internal lock invisible to user code, and this practice is now permitted by the initialization procedure.

There is the quote from the draft - the discussed part is highlighted.

Because the Java virtual machine is multithreaded, initialization of a class or interface requires careful synchronization, since some other thread may be trying to initialize the same class or interface at the same time. There is also the possibility that initialization of a class or interface may be requested recursively as part of the initialization of that class or interface. The implementation of the Java virtual machine is responsible for taking care of synchronization and recursive initialization by using the following procedure. It assumes that the Class object has already been verified and prepared, and that the Class object contains state that indicates one of four situations:

  • This Class object is verified and prepared but not initialized.
  • This Class object is being initialized by some particular thread.
  • This Class object is fully initialized and ready for use.
  • This Class object is in an erroneous state, perhaps because initialization was attempted and failed.

For each class or interface C, there is a unique initialization lock LC. The mapping from C to LC is left to the discretion of the Java virtual machine implementation. The procedure for initializing C is then as follows:

  1. Synchronize on the initialization lock, LC, for C. This involves waiting until the current thread can acquire LC.
  2. If the Class object for C indicates that initialization is in progress for C by some other thread, then release LC and block the current thread until informed that the in-progress initialization has completed, at which time repeat this procedure.
  3. If the Class object for C indicates that initialization is in progress for C by the current thread, then this must be a recursive request for initialization. Release LC and complete normally.
  4. If the Class object for C indicates that C has already been initialized, then no further action is required. Release LC and complete normally.
  5. If the Class object for C is in an erroneous state, then initialization is not possible. Release LC and throw a NoClassDefFoundError.
  6. Otherwise, record the fact that initialization of the Class object for C is in progress by the current thread, and release LC. Then, initialize each final static field of C with the constant value in its ConstantValue attribute (§4.7.2), in the order the fields appear in the ClassFile.
  7. Next, if C is a class rather than an interface, and its superclass SC has not yet been initialized, then recursively perform this entire procedure for SC. If necessary, verify and prepare SC first. If the initialization of SC completes abruptly because of a thrown exception, then acquire LC, label the Class object for C as erroneous, notify all waiting threads, release LC, and complete abruptly, throwing the same exception that resulted from initializing SC.
  8. Next, determine whether assertions are enabled for C by querying its defining class loader.
  9. Next, execute the class or interface initialization method of C.
  10. If the execution of the class or interface initialization method completes normally, then acquire LC, label the Class object for C as fully initialized, notify all waiting threads, release LC, and complete this procedure normally.
  11. Otherwise, the class or interface initialization method must have completed abruptly by throwing some exception E . If the class of E is not Error or one of its subclasses, then create a new instance of the class ExceptionInInitializerError with E as the argument, and use this object in place of E in the following step. If a new instance of ExceptionInInitializerError cannot be created because an OutOfMemoryError occurs, then use an OutOfMemoryError object in place of E in the following step.
  12. Acquire LC, label the Class object for C as erroneous, notify all waiting threads, release LC, and complete this procedure abruptly with reason E or its replacement as determined in the previous step.

An implementation may optimize this procedure by eliding the lock acquisition in step 1 (and release in step 4/5) when it can determine that the initialization of the class has already completed, provided that, in terms of the memory model, all happens-before orderings (JLS3 §17.4.5) that would exist if the lock were acquired, still exist when the optimization is performed.

Now back to static initialization specification. It continues with the last section 12.4.3.

12.4.3 Initialization: Implications for Code Generation

Code generators need to preserve the points of possible initialization of a class or interface, inserting an invocation of the initialization procedure just described. If this initialization procedure completes normally and the Class object is fully initialized and ready for use, then the invocation of the initialization procedure is no longer necessary and it may be eliminated from the code-for example, by patching it out or otherwise regenerating the code.

Compile-time analysis may, in some cases, be able to eliminate many of the checks that a type has been initialized from the generated code, if an initialization order for a group of related types can be determined. Such analysis must, however, fully account for concurrency and for the fact that initialization code is unrestricted.

This section allows JVM to eliminate synchronization on initialized classes. Please note the quote from JavaSE7 Draft provides the means for the same optimization at the end.

Overall the static initialization has some tricky areas but these can be usually avoided. It is just another area where "keep it simple, ..." simply works.

Wednesday, March 2, 2011

Deadlock despite consistent lock acquisition ordering

Consistent lock acquisition ordering (further as lock ordering) is one of the techniques of deadlock prevention. Deadlock is caused by circular dependency of threads trying to acquire locks. The consistent ordering prevents such dependency.

There is a common example of code which is vulnerable to deadlock:

public void someMethod() {
    synchronized (lock1) {
        synchronized (lock2) {
            // do something here
        }
    }
}

public void someOtherMethod() {
    synchronized (lock2) {
        synchronized (lock1) {
            // do something here
        }
    }
}

If 2 threads concurrently execute these methods they can end up in deadlock where thread1 holds lock1 while waiting for lock2 and thread2 holds lock2 while waiting for lock1. More detailed explanation of deadlock can be found for example here.

This article will use even simpler model code:

public void someMethod() {
    synchronized (lock1) {
        synchronized (lock2) {
            // do something here
        }
    }
}

This code can be executed concurrently by more threads without the risk of deadlock as threads acquire the locks in the same order. It is not 100% deadlock proof though because the lock ordering can be broken by wait(). This program:

public class BrokenOrderingBasic implements Runnable {
    private Object lock1 = new Object();
    private Object lock2 = new Object();

    public static void main(String[] args) throws InterruptedException {
        BrokenOrderingBasic runnable = new BrokenOrderingBasic();
        Thread thread1 = new Thread(runnable, "thread1");
        Thread thread2 = new Thread(runnable, "thread2");
        thread1.start();
        Thread.sleep(500);
        thread2.start();
    }

    @Override
    public void run() {
        try {
            String threadName = Thread.currentThread().getName();
            synchronized (lock1) {
                System.out.println(threadName + " has lock1");
                synchronized (lock2) {
                    System.out.println(threadName + " has lock2");
                    lock1.wait(1000);
                }
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

prints:

thread1 has lock1
thread1 has lock2
thread2 has lock1

and hangs. Thread dump confirms a deadlock:

Found one Java-level deadlock:
=============================
"thread2":
  waiting to lock monitor 0x092807b0 (object 0x9f182210, a java.lang.Object),
  which is held by "thread1"
"thread1":
  waiting to lock monitor 0x09281fe8 (object 0x9f182208, a java.lang.Object),
  which is held by "thread2"

The reason is wait() will break the lock ordering. The program's lock ordering is lock1 -> lock2. thread1 acquires lock1 and lock2 at first. But then it releases lock1 by lock1.wait() while still holding lock2. When thread1 later timeouts from wait() it will try to acquire lock1 again and that way it practically establishes lock ordering lock2 -> lock1. As lock1 was acquired by thread2 in the meantime we have standard deadlock scenario here.

The above example is not quite realistic scenario as calling wait() on outer lock does not make much sense. If it appeared in real code, it would be very likely a bug.

Let us look on variation of the first scenario. This program:

public class BrokenOrderingReentredLock implements Runnable {
    private Object lock1 = new Object();
    private Object lock2 = new Object();

    public static void main(String[] args) throws InterruptedException {
        BrokenOrderingReentredLock runnable = new BrokenOrderingReentredLock();
        Thread thread1 = new Thread(runnable, "thread1");
        Thread thread2 = new Thread(runnable, "thread2");
        thread1.start();
        Thread.sleep(500);
        thread2.start();
    }

    @Override
    public void run() {
        try {
            String threadName = Thread.currentThread().getName();
            synchronized (lock1) {
                System.out.println(threadName + " has lock1");
                synchronized (lock2) {
                    System.out.println(threadName + " has lock2");
                    synchronized (lock1) {
                        System.out.println(threadName + " reenters lock1");
                        lock1.wait(1000);
                    }
                }
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

prints:

thread1 has lock1
thread1 has lock2
thread1 reenters lock1
thread2 has lock1

and it hangs too:

Found one Java-level deadlock:
=============================
"thread2":
  waiting to lock monitor 0x02b7fdcc (object 0x229bf910, a java.lang.Object),
  which is held by "thread1"
"thread1":
  waiting to lock monitor 0x02b816fc (object 0x229bf908, a java.lang.Object),
  which is held by "thread2"

The reasoning is the same as for the previous scenario. The program's lock ordering is lock1 -> lock2. thread1 acquires lock1 and lock2 and reenters lock1. It releases lock1 by lock1.wait() while still holding lock2. When it later timeouts from wait() it will try to acquire lock1 again and that way it practically establishes lock ordering lock2 -> lock1. lock1 was acquired by thread2 in the meantime.

This scenario does not seem to be realistic either but the lock acquisitions can spread over multiple methods. In case of the complex code base + 3rd party libraries/frameworks is such situation more likely. On the other hand it also strongly suggests some redesign is needed.

The deadlock "property" of wait() is not limited to Java built-in synchronization and monitors. It is inherent with any wait-like feature (suspend the current thread and release the associated lock). The following program is equivalent to the previous one but using the java.util.concurrent.locks package:

import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

public class BrokenOrderingReentrantLock implements Runnable {
    private ReentrantLock lock1 = new ReentrantLock();
    private ReentrantLock lock2 = new ReentrantLock();
    private Condition condition = lock1.newCondition();

    public static void main(String[] args) throws InterruptedException {
        BrokenOrderingReentrantLock runnable = new BrokenOrderingReentrantLock();
        Thread thread1 = new Thread(runnable, "thread1");
        Thread thread2 = new Thread(runnable, "thread2");
        thread1.start();
        Thread.sleep(500);
        thread2.start();
    }

    @Override
    public void run() {
        try {
            String threadName = Thread.currentThread().getName();
            lock1.lock();
            try{
                System.out.println(threadName + " has lock1");
                lock2.lock();
                try{
                    System.out.println(threadName + " has lock2");
                    lock1.lock();
                    try{
                        System.out.println(threadName + " reenters lock1");
                        condition.await(1, TimeUnit.SECONDS);
                    } finally {
                        lock1.unlock();
                    }
                } finally {
                    lock2.unlock();
                }
            } finally {
                lock1.unlock();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}
When executed it behaves the same way. It prints:
thread1 has lock1
thread1 has lock2
thread1 reenters lock1
thread2 has lock1

and it hangs too:

Found one Java-level deadlock:
=============================
"thread2":
  waiting for ownable synchronizer 0x9f142860,
  (a java.util.concurrent.locks.ReentrantLock$NonfairSync),
  which is held by "thread1"
"thread1":
  waiting for ownable synchronizer 0x9f142838,
  (a java.util.concurrent.locks.ReentrantLock$NonfairSync),
  which is held by "thread2"

To summarize - the consistent lock acquisition ordering helps to prevent deadlock but one has to be aware that wait() can mess up with seemingly obvious correct ordering. But if such situation happens it is probably a bug or a superficial code design.

Saturday, February 12, 2011

Java static initialization - part 1

Details of java static initialization (i.e. initialization of classes and interfaces) are defined in Java Language Specification (JLS) - §12.4. This post goes through the specification and provides additional comments and code examples. Please note that any quotations are taken from JLS if not said otherwise.

12.4 Initialization of Classes and Interfaces

Initialization of a class consists of executing its static initializers and the initializers for static fields (class variables) declared in the class. Initialization of an interface consists of executing the initializers for fields (constants) declared there.
Detail specification of static initializer is available in JLS - 8.7 Static Initializers and specification of initializer for static fields is in JLS - 8.3.2 Initialization of Fields. This little class should be a sufficient remainder for above:
public class A {
    static {
        System.out.println("This is a static initializer");
    }
    static public String staticField = "This is initializer for static field";
}
Interface does not have static initializers and its fields are always static, public and final.
Before a class is initialized, its superclass must be initialized, but interfaces implemented by the class are not initialized. Similarly, the superinterfaces of an interface are not initialized before the interface is initialized.
It means the following program:
interface I{
    String X = TestClassHierarchy.out("I ");
}
 
class Super implements I{
    static String x = TestClassHierarchy.out("Super ");
}
 
class Sub extends Super{
    static String x = TestClassHierarchy.out("Sub ");
}
 
public class TestClassHierarchy {
    static public void main(String[]arg){
        new Sub();
    }
    static String out(String text){ System.out.print(text); return text; }
}

prints:

Super Sub

There is another example program regarding this section later in the JLS too.

12.4.1 When Initialization Occurs

Initialization of a class consists of executing its static initializers and the initializers for static fields declared in the class. Initialization of an interface consists of executing the initializers for fields declared in the interface.

Before a class is initialized, its direct superclass must be initialized, but interfaces implemented by the class need not be initialized. Similarly, the superinterfaces of an interface need not be initialized before the interface is initialized.

This section just repeats first two paragraphs without an apparent reason...
A class or interface type T will be initialized immediately before the first occurrence of any one of the following:
This is the interesting part. JLS is quite often benevolent to give enough freedom to JVM implementators for various optimizations. But it is strict in this case. Initialization is done on these events below. It can't be done sooner - or later for that matter. (Note: This is why Initialization On Demand Holder idiom works.)
  • T is a class and an instance of T is created.
T instance can be created using:
  1. a new keyword - new T()
  2. reflection - e.g. T.class.newInstance()
  3. deserialization
  4. cloning
Obviously only 1) - 3) are relevant here and can cause a static initialization.
  • T is a class and a static method declared by T is invoked.
So this program:
class A {
    static {
        System.out.print("class A initialized, ");
    }
 
    static public void staticMethod(){
        System.out.print("static method called, ");
    }
}

public class TestStaticMethodInit {
    public static void main(String[] args) {
        A.staticMethod();
    }
}

prints:

class A initialized, static method called,
  • A static field declared by T is assigned.
And this program:
class A {
    static { System.out.print("class A initialized, "); }
    static public int X;
}

public class TestStaticFieldAssigned {
    public static void main(String[] args) {
        A.X = 3;
    }
}

prints:

class A initialized,
  • A static field declared by T is used and the field is not a constant variable (§4.12.4).

A constant variable exception makes this item a bit more complicated. Section 4.12.4 says that the "constant variable" is "a variable, of primitive type or type String, that is final and initialized with a compile-time constant expression (§15.28)". The exact definition of compile-time constant expression is in §15.28 but in short - a compile-time constant expression, as name suggests, is an expression which can be evaluated by compiler. It can be composed of primitive and string literals, operators and other compile-time constant expressions but usually it is just simple literal. Some of the §15.28's more complicated constant expression examples are (short)(1*2*3*4*5*6) and "The integer " + Long.MAX_VALUE + " is mighty big.".

Note: Be aware that despite their constant-like look and feel the Boolean.TRUE/Boolean.FALSE are not constant expressions.

Example time. This program:

class A {
    static { System.out.print("class A initialized, "); }
    static public final String X = "string";
}

public class TestStaticFieldUsed {
    public static void main(String[] args) {
        System.out.println(A.X);
    }
}

prints only:

string

But if you change X initialization to new String("string") or "string".intern() then program prints:

class A initialized, string

because these are not constant expressions.

Please note the "string" and "string".intern() will initialize X to the identical object though.

  • T is a top-level class, and an assert statement (§14.10) lexically nested within T is executed.
If it is not clear what scenario is described here then the §14.10 gives a clue (highlight added):

Note that an assertion that is enclosed by a top-level interface does not cause initialization.

Usually, the top level class enclosing an assertion will already be initialized. However, if the assertion is located within a static nested class, it may be that the initialization has not taken place.

So this program (with assertions enabled):
public class TestInitializationAssert {
    public static void main(String[] args) {
        new A.AInner();
    }
}
----------------
public class A{
    static {
        System.out.print("init A, ");
    }
    static public class AInner{
        static {
            assert Boolean.TRUE;
            System.out.print("init AInner, ");
        }
    }
}

should print:

init AInner, init A,

But it actually does not. It prints only:

init AInner,

The reason why it does not work as expected is Bug ID: 6394986 JLS3 14.10 An assert statement must cause the enclosing top level class... The problem exists on both Sun and IBM JDK's.

Invocation of certain reflective methods in class Class and in package java.lang.reflect also causes class or interface initialization.
The above list of static initialization triggers works in the case of the reflection too. The point is it does not matter how exactly these triggers are activated but when it happens static initializations should happen.
A class or interface will not be initialized under any other circumstance.
As mentioned above JLS is strict in this case.
The intent here is that a class or interface type has a set of initializers that put it in a consistent state, and that this state is the first state that is observed by other classes. The static initializers and class variable initializers are executed in textual order, and may not refer to class variables declared in the class whose declarations appear textually after the use, even though these class variables are in scope (§8.3.2.3). This restriction is designed to detect, at compile time, most circular or otherwise malformed initializations.
This section introduces the crucial rule for static initialization of the class/interface - execution happens in textual order. It means this program:
public class TestStaticInitializtionOrdering {
    static { out("initialized first, ");}

    public static void main(String[] args) {
        out("class is initialized");
    }

    static public String X = out("initialized second, ");
 
    private static String out(String text) {
        System.out.print(text);
        return text;
    }
 
    static { out("initialized third, ");}
}

prints:

initialized first, initialized second, initialized third, class is initialized

Above section also mentions §8.3.2.3. Other sections of §8.3.2 - Initialization of Fields discuss static initialization too but §8.3.2.3 is the most relevant of them in this context and it is quoted fully below:

8.3.2.3 Restrictions on the use of Fields during Initialization

The declaration of a member needs to appear textually before it is used only if the member is an instance (respectively static) field of a class or interface C and all of the following conditions hold:
  • The usage occurs in an instance (respectively static) variable initializer of C or in an instance (respectively static) initializer of C.
  • The usage is not on the left hand side of an assignment.
  • The usage is via a simple name.
  • C is the innermost class or interface enclosing the usage.
A compile-time error occurs if any of the four requirements above are not met. This means that a compile-time error results from the test program:
class Test {
    int i = j; // compile-time error: incorrect forward reference
    int j = 1;
}
whereas the following example compiles without error:

class Test {
    Test() { k = 2; }
    int j = 1;
    int i = j;
    int k;
}
even though the constructor (§8.8) for Test refers to the field k that is declared three lines later. These restrictions are designed to catch, at compile time, circular or otherwise malformed initializations. Thus, both:
class Z {
    static int i = j + 2; 
    static int j = 4;
}
and:
class Z {
    static { i = j + 2; }
    static int i, j;
    static { j = 4; }
}
result in compile-time errors. Accesses by methods are not checked in this way, so:
class Z {
    static int peek() { return j; }
    static int i = peek();
    static int j = 1;
}
class Test {
    public static void main(String[] args) {
        System.out.println(Z.i);
    }
}
produces the output: 0 because the variable initializer for i uses the class method peek to access the value of the variable j before j has been initialized by its variable initializer, at which point it still has its default value (§4.12.5).

A more elaborate example is:

class UseBeforeDeclaration {
    static {
        x = 100; // ok - assignment
        int y = x + 1; // error - read before declaration
        int v = x = 3; // ok - x at left hand side of assignment
        int z = UseBeforeDeclaration.x * 2; 
        // ok - not accessed via simple name
        Object o = new Object(){ 
            void foo(){x++;} // ok - occurs in a different class
            {x++;} // ok - occurs in a different class
        };
    }
    {
        j = 200; // ok - assignment
        j = j + 1; // error - right hand side reads before declaration
        int k = j = j + 1; 
        int n = j = 300; // ok - j at left hand side of assignment
        int h = j++; // error - read before declaration
        int l = this.j * 3; // ok - not accessed via simple name
        Object o = new Object(){ 
            void foo(){j++;} // ok - occurs in a different class
            { j = j + 1;} // ok - occurs in a different class
        };
    }
    int w = x = 3; // ok - x at left hand side of assignment
    int p = x; // ok - instance initializers may access static fields
    static int u = (new Object(){int bar(){return x;}}).bar();
    // ok - occurs in a different class
    static int x;
    int m = j = 4; // ok - j at left hand side of assignment
    int o = (new Object(){int bar(){return j;}}).bar(); 
    // ok - occurs in a different class
    int j;
}
The examples at the end of the quote is descriptive and very helpful in understanding of the next section.
As shown in an example in §8.3.2.3, the fact that initialization code is unrestricted allows examples to be constructed where the value of a class variable can be observed when it still has its initial default value, before its initializing expression is evaluated, but such examples are rare in practice. (Such examples can be also constructed for instance variable initialization; see the example at the end of §12.5). The full power of the language is available in these initializers; programmers must exercise some care. This power places an extra burden on code generators, but this burden would arise in any case because the language is concurrent (§12.4.3).

Some of the static initialization scenarios are really tricky so the safest thing to do is to stick to the proper action ordering - declare, initialize, use. Otherwise one might be really surprised what is going on especially if non-standard static initialization order is combined with other Java features.

This program is inspired by one of the Java puzzlers:

public class TestStaticInitOrderWithAutoboxing {

    static{System.out.println(getYesOrNo() ? "yes" : "no");}
 
    static final public Boolean YES_OR_NO = Boolean.TRUE;
 
    static boolean getYesOrNo(){ return YES_OR_NO;};
 
    public static void main(String[] args) {}
}

The program above does print neither yes nor no but it throws NullPointerException instead. The class name gives a subtle hint - it is caused by adding autoboxing to the mix. The reason is getYesOrNo() method called in line 3 is supposed to return a value of YES_OR_NO which has not been initialized yet. Because YES_OR_NO is of Boolean class type so it has null value when uninitialized. As getYesOrNo() method returns boolean primitive, it tries to unbox null which cause the exception. The fix is straightforward - move line 5 ahead of line 3 so the "declare, initialize, use" rule is satisfied.

As a little exercise: what will program do when YES_OR_NO's type is changed from Boolean to boolean?

The section 12.4.1 ends with 3 commented examples.

Before a class is initialized, its superclasses are initialized, if they have not previously been initialized.

Thus, the test program:

class Super {
    static { System.out.print("Super "); }
}
class One {
    static { System.out.print("One "); }
}
class Two extends Super {
    static { System.out.print("Two "); }
}
class Test {
    public static void main(String[] args) {
        One o = null;
        Two t = new Two();
        System.out.println((Object)o == (Object)t);
    }
}

prints:

Super Two false

The class One is never initialized, because it not used actively and therefore is never linked to. The class Two is initialized only after its superclass Super has been initialized.

A reference to a class field causes initialization of only the class or interface that actually declares it, even though it might be referred to through the name of a subclass, a subinterface, or a class that implements an interface.

The test program:

class Super { static int taxi = 1729; }
class Sub extends Super {
    static { System.out.print("Sub "); }
}
class Test {
    public static void main(String[] args) {
        System.out.println(Sub.taxi);
    }
}

prints only:

1729
because the class Sub is never initialized; the reference to Sub.taxi is a reference to a field actually declared in class Super and does not trigger initialization of the class Sub.

Initialization of an interface does not, of itself, cause initialization of any of its superinterfaces.

Thus, the test program:

interface I {
    int i = 1, ii = Test.out("ii", 2);
}
interface J extends I {
    int j = Test.out("j", 3), jj = Test.out("jj", 4);
}
interface K extends J {
    int k = Test.out("k", 5);
}
class Test {
    public static void main(String[] args) {
        System.out.println(J.i);
        System.out.println(K.j);
    }
    static int out(String s, int i) {
        System.out.println(s + "=" + i);
        return i;
    }
}

produces the output:

1
j=3
jj=4
3

The reference to J.i is to a field that is a compile-time constant; therefore, it does not cause I to be initialized. The reference to K.j is a reference to a field actually declared in interface J that is not a compile-time constant; this causes initialization of the fields of interface J, but not those of its superinterface I, nor those of interface K. Despite the fact that the name K is used to refer to field j of interface J, interface K is not initialized.

To sum the post:

  • Static fields and static blocks of a class are initialized in the textual order
  • Interface fields are initialized in the textual order
  • Static initialization is triggered solely by these events - instance creation, static method call, assignment to static field, usage of static non-constant variable field and execution of an nested assert statement
  • Before static initialization of the class starts, a static initialization of the super class is done in case it has not been initialized yet
  • Usage of static field before initialization should be avoided

Part 2 is available here.