Friday, December 31, 2010

Optimizing concurrency with Freescale’s Deadlock Preventer

The overall concurrency of a program, given it already uses an optimal number of threads, will depend on how much lock contention is occurring.

To avoid both deadlocks and lock contention, synchronization primitives should be the most granular possible given a fixed number of primitives.

For example, in the following snippet:

public synchronized void setProperty(Object newValue) {
    value = newValue;
    notifyPropertyChange();
}

private void notifyPropertyChange() {
    synchronized(listeners) {
        for (IListener listener : listeners)
            listener.changed();
    }
}

The setProperty() method is synchronized in order to protect the “value” data from concurrent data access.  Inadvertently, the synchronized block will cause all the code path executed by the listener.changed() invocation to needlessly have the synchronized(this) lock as a precedent.

This will not only cause the code to have a sub-optimal concurrent execution, but also introduce a lock order dependency between ‘this’, ‘listeners’, and whatever lock is acquired by the listener’s changed() implementation, possibly eventually causing a deadlock (in the Deadlock' Preventer’s terminology, the ‘listeners’ lock is then a ‘follower’ of the ‘this’ lock, and the ‘this’ lock a precedent of the ‘listeners’ lock).

The code could be re-written as follows:

public void setProperty(Object newValue) {
    synchronized(this) {
        value = newValue;
    }
    notifyPropertyChange();
}

By simply reducing the granularity of the ‘this’ lock acquisition, we improve possible concurrent execution, eliminate the lock dependency, and avoid lock ordering acquisition problems between ‘this’ and ‘listeners’, and ‘this’ and all listener’s changed() implementations, without any negative effect whatsoever.

We could also re-write the notifyPropertyChange() implementation as follows:

private void notifyPropertyChange() {
    IListener[] tmp;
    synchronized(listeners) {
        tmp = listeners.clone();
    }
    for (IListener listener : tmp)
        listener.changed();
}

At the cost of the clone() statement (something probably insignificant compared to the code executed in the listeners), the lock dependency is completely removed between ‘this’, ‘listeners’, and all lock acquisitions in the listener’s changed() implementations.

In a java program, the locks with the most number of followers are not only the most likely to cause deadlocks, but also the locks that are likely to reduce overall system concurrency.

It is unfortunately very easy to induce unnecessary dependencies between synchronization primitives, and hard to discover which locks have effectively a large number of followers.

Without a tool such as the Deadlock Preventer, which helps identifying which locks have the most followers, developers would be reduced to half hazardly trying to improve lock granularity without knowing where to start.

This is very similar to performance optimization without using a profiler:  without knowing what takes the most time, developer’s time is easily wasted, and so is concurrency optimization.

Help with the Deadlock Preventer

With the latest release of the Deadlock Preventer, it is now possible to use the Deadlock Preventer view to download lock statistics for a java program.

image

By right-clicking on the process name in the “Conflicts” tab, and selecting the “Statistics…” menu, the following dialog appears:

image

The table lists all locks in the program, the number of followers and precedents, and their acquisition locations.  More information can be obtained for each lock by selecting its row and doing copy, which puts the following information in the clipboard (for the first lock in the table above):

lock: java.lang.Object (id=2), precedents(1) followers(1)
  zzz.Main.test(Main.java:14)
  zzz.Main.main(Main.java:6)
  precedents:
    java.lang.Object (id=1), thread id(1 (main))
     zzz.Main.test(Main.java:13)
     zzz.Main.main(Main.java:6)
  followers:
    java.lang.Object (id=1), thread id(13 (Thread-2))
     zzz.Main$1.run(Main.java:22)
     java.lang.Thread.run(Thread.java:619)

The text contains detailed information about each precedents and followers, along with the stack trace in which their relationship to the lock were recorded.

The information for all locks can also be exported to a single text file by using the “Export…” button.

One very useful way to use the statistics generated by the Deadlock Preventer is to sort all the locks by their follower count.

To give an example of what large programs lock statistics look like, the following table shows what the Eclipse IDE synchronization primitives statistics just after opening the workbench window:

image

Listing the top followers’ count locks out of a total of 21 830 locks.

Running Freescale’s Deadlock Preventer from the command line

One of the best ways to detect potential deadlocks is to integrate the Deadlock Preventer in a release engineering process, so it can run with the java program executing the automated tests, and have an excellent code coverage to analyze the system’s synchronization primitives.

To integrate the Deadlock Preventer in a release engineering process, although, means being able to configure the test scripts to run the Deadlock Preventer.

Adding the Deadlock preventer is as simple as adding the following two arguments to the “java” executable:

-javaagent:path-to\com.freescale.deadlockPreventer.wrapper_1.0.0\com.freescale.deadlockpreventer.jar

-Xbootclasspath/a:path-to\com.freescale.deadlockPreventer.wrapper_1.0.0\com.freescale.deadlockpreventer.jar;path-to\javassist.wrapper_1.0.0\javassist.jar

Where the two plugins “com.freescale.deadlockPreventer.wrapper” and “javassist.wrapper” can be obtained from the following link(in the build/eclipse/plugins sub-folder):

https://github.com/sbeauchamp/Deadlock-Preventer/zipball/master

The following java property can be specified to write the Deadlock Preventer output to a file:

-Dcom.freescale.deadlockpreventer.logToFile=path-to\deadlock_preventer_output.log

Alternatively, the output can be re-directed to the standard output with the following property:

-Dcom.freescale.deadlockpreventer.logToStream=out

or

-Dcom.freescale.deadlockpreventer.logToStream=err

Memory Requirements

An important factor to keep in mind, is that running a java program with the Deadlock Preventer will cause all locks ever acquired to be referenced in memory by the analysis engine, so they will not be garbage collected for the life time of the program.

This can cause some significant memory consumption increase, and may require the –Xmx flag to be passed to java to be increased.

For example, running an eclipse.exe instance with the the Deadlock Preventer can increase its memory usage by several hundred MBs.

Running the Deadlock Preventer interactively

Another alternative to either running the Deadlock Preventer in the Eclipse workbench with the UI or running it in an automated build, is to use the built-in command line server/client.

To start the server, the following command can be used:

java –cp path-to\com.freescale.deadlockPreventer.wrapper_1.0.0\com.freescale.deadlockpreventer.jar com.freescale.deadlockpreventer.ConsoleNetworkServer 43537

The last argument is the port number of the server, which can be omitted, in which case the default port will be used, 43537.

The following output will then appear to the command line:

Server started on port: 43537
services:
  report: report.2
  query: query.1
Type 'help' for a list of commands.

This information can then be used to pass the following two properties to the java instance that is running the Deadlock Preventer (the one that is getting the –javagent flag):

-Dcom.freescale.deadlockpreventer.reportService=localhost:43537:report.2

-Dcom.freescale.deadlockpreventer.queryService=localhost:43537:query.1

Note that if the server is started on a different machine, the “localhost” string must be replaced by the IP address of the server.

When the Deadlock Preventer is connected to the server, any inconsistent locking detected will be displayed on the server’s console interactively, so that the user can decide to continue, or abort the program.  The server console can also be used to query lock statistics with the following commands:

getLockCount

      Returns the number of locks in the program.
getDetails index end

      Return detailed information on the lock(s) from index to end (being numbers between 0 and the number of locks in the program)
getAll

      Return all lock information as output on the standard out stream
writeAll file-path

      Download all lock information and write the complete output in a file

Note that downloading lock statistics can require quite a lot of memory and bandwidth (several hundred MBs for an eclipse workbench, for example).

Monday, December 6, 2010

Freescale's Deadlock Preventer is now released!

To try it out:
  1. Be sure to have an Eclipse 3.6.1 SDK layout, and using JDK 1.6 as your default JRE (jdk 1.7 doesn't work yet)
  2. Install Git
  3. Set your user and email in Git
  4. Type in the shell (cygwin on windows):
git clone git@github.com:sbeauchamp/Deadlock-Preventer.git
This will create a directory on your file system containing all the deadlock preventer plugins.
If you simply want to run the deadlock preventer tool, get the 4 plugins under
./Deadlock-Preventer/build/eclipse/plugins/
And copy them in the eclipse/dropins of your eclipse directory:
You will see that a new view is available from "Other/Deadlock Preventer".

alt
The easiest way to try is out is to create a new java project, with the following sample code in Main.java:
public class Main {
public static void main(String[] args) {
new Main().test();
}
Object lock = new Object();
Object lock2 = new Object();
private void test() {
synchronized(lock) {
synchronized(lock2) {
code();
}
}
Thread thread = new Thread(new Runnable() {
public void run() {
synchronized(lock2) {
synchronized(lock) {
code();
}
}
}
});
thread.start();
try {
thread.join();
} catch (InterruptedException e1) {
}
}
private void code() {
System.out.println("test");
}
}
Then create a new launch configuration to run the program. The new configuration will automatically appear in the combo box under the tab "Eclipse JDT Debugging" of the "Deadlock Preventer" view.
Once you click "Debug" from that tab (using the "Run/Debug" menu does not have the same effect), the program runs with the deadlock preventer automatically instrumenting the byte code.
You will then see the following error being reported:

altAnd if double-clicked the full information is displayed:

alt
By setting a breakpoint on "RuntimeException"s and using the 'Interactive' or “throw exception" mode, you are able to break in the debugger at the exact point where the inconsistent locking order is detected.
This should be enough to get your started with using the deadlock preventer, and investigating potential deadlocks in your programs.
In a next post, I will post the different options and runtime settings of the deadlock preventer including those useful to integrate it in a release engineering process.
P.S. I submitted a talk to EclipseCon 2011 on the deadlock preventer and using it to prevent deadlocks in Eclipse plugins. Please drop a comment in the submission if you think it would be an interesting talk.