JCarder — Manual

JCarder manual

1. Introduction
2. Requirements
3. Execution
4. Analysis
5. Performance
6. Limitations
7. Reference
- 7.1. The JCarder Java agent
- 7.2. The JCarder analyzer

1. Introduction

Threads are difficult. It is hard to write a correct multi-threaded program, at least when the threads have shared state. If the program does not have proper synchronization (locking) when accessing the shared state, it will have problems with data race, which makes the program execution indeterministic and erroneous. And if the program is synchronized so that data race is avoided, it may still suffer from problems with deadlock, which makes two (or several) threads wait for the other to release a lock, making them wait forever.

JCarder is a tool that can find potential deadlocks in a Java program. It can analyze a program and tell whether a deadlock might have occurred if the threads would have been scheduled differently. That is, deadlock problems can be found without triggering actual deadlocks while running the program.

Here is a simplified overview of what happens when analyzing a program with JCarder:

First, JCarder instruments the program's byte code so that all lock operations are logged to disk.
Next, the program continues execution as usual while logging information about its use of locks.
Finally, when the program has finished execution, JCarder analyzes the logged information to find deadlock problems.

Note that JCarder does not perform any static code analysis. It is not necessary to have access to the program's source code, only the .class files.

We hope that you will find JCarder useful. Oh, and we would love to get feedback. Does JCarder find any errors, and if so, what kind of errors? Does it fail to find errors that should have been found? Please contact us at the JCarder forum.

JCarder's primary authors are Ulrik Svensson and Joel Rosdahl, Enea.

JCarder source code and documentation is released to the open source community by Enea under the GNU GPL v2 license.

2. Requirements

JCarder is written in Java and runs on any JVM that is compliant with Java 5.0 or higher. The only requirement on a program to be analyzed by JCarder is that it can be run on the same JVM as JCarder, for example Sun's ordinary JRE. Thus, there is no need to use a special JVM or build procedure and there is also no need for special code annotations or other changes to the program's source code.

It is, however, a big advantage to have automated integration test cases that cover all possible execution paths of the program, using the same thread model that the program uses when run normally. If such test cases exist, it is easy to just let JCarder analyze the test execution to find potential deadlocks. Otherwise, the program must be run in a more ad hoc fashion each time an analysis is to be made. It is, of course, perfectly okay to use JCarder while running the program manually if no automated integration test cases exist.

The analysis step currently produces a GraphViz DOT file, so an installation of GraphViz is needed to visualize the result.

3. Execution

3.1. Running the agent

It is very straightforward to prepare a program for analysis by JCarder. The only necessary thing to do is to make sure that the JVM is started with jcarder.jar as a Java agent. Upon execution, the agent will intercept classes loaded by the class loader and instrument the classes with some extra byte code. The task of the inserted byte code is to log each lock acquisition event to disk, along with the thread ID and some other information.

The agent is normally activated by passing a -javaagent:path/to/jcarder.jar option to the JVM:

java -javaagent:path/to/jcarder.jar -jar yourprogram.jar ...

Here is an example of how to run JCarder on the modelview example program in examples.jar distributed with JCarder:

% java -javaagent:path/to/jcarder.jar -classpath path/to/examples.jar modelview/Main
Starting JCarder (1.0) agent
Opening for writing: ./jcarder_events.db
Opening for writing: ./jcarder_contexts.db
JCarder agent initialized

Registering view in data model
Registering view in data model
Updating the model
Freezing view
Thawing view
Main thread finished
Notifying listeners

By the way, can you find any potential deadlock in the example program? The source code is included in examples.jar and is also available here: modelview/Main.java, modelview/Model.java, modelview/View.java.

The first five rows are printed by the JCarder agent to standard output and the rest are output from the example program. jcarder_events.db and jcarder_contexts.db are the files to which JCarder logs information about locks. A log file called jcarder.log is also created.

By default, JCarder writes to files in the current working directory. This can be changed by setting the jcarder.outputdir Java system property to another directory. Example:

java -javaagent:path/to/jcarder.jar -Djcarder.outputdir=path -jar yourprogram.jar ...

Alternatively, you may specify jcarder options using javaagent parameters. Example:

java -javaagent:path/to/jcarder.jar=outputdir=path,foo=bar -jar yourprogram.jar ...

See the JCarder agent reference section for more information and options.

3.2. How to get good results

Since JCarder analyzes code dynamically, it cannot find potential deadlocks in code that is not executed. To get good results, it is therefore important that as many code paths as possible are executed. Try to make the program start all threads it can start and make the threads run all code they can run. Note, however, that the scheduling of threads does not matter, so it is not necessary to run tasks repeatedly with different timings. If the program is a GUI, make sure to exercise all scenarios that spawn threads, and so on. Focus on integration tests (which may be automated or manual) rather than unit tests, since deadlocks in most cases manifest themselves in the interaction between classes.

3.3. Instrumentation of the standard library

With one exception, JCarder does not instrument classes in the standard library. This is because of several reasons:

The standard library is used by JCarder itself. If JCarder were to instrument the standard library while using it, nasty problems would occur.
It would affect performance considerably, since a typical Java program uses the standard library frequently.
We do not know of any class in the standard library that calls non-standard library code while holding a lock. It should therefore be unnecessary to keep track of when those locks are held.

The exception is the AWT and Swing libraries. Since classes in those packages actually may call user code while holding a lock (for instance, javax.swing.JTable calls javax.swing.table.TableModel.getValueAt while holding an AWTTreeLock) and since the JCarder agent does not use them, they are instrumented, provided that the agent is on the bootstrap class path. See the JCarder Java agent reference for more information.

It should be noted that most Swing object methods are not thread safe. Methods not explicitly marked "thread safe" in the documentation must be invoked from the event dispatch thread only! Read more about this in Sun's Concurrency in Swing tutorial.

Another thing to note is that some Java library licenses (for instance, Sun's binary code license agreement, which is used for Sun's prebuilt JRE/JDK packages) say that you are not allowed to modify or change the behaviour of standard library classes. JCarder will never instrument the standard library unless you add jcarder.jar to the bootstrap class path. Use your own judgement.

4. Analysis

4.1. Running the analyzer

When the program has been run together with the JCarder Java agent, it is time to run JCarder in analysis mode. This is done by running jcarder.jar as a JAR file. For instance:

java -jar path/to/jcarder.jar

Pass the -help option to print some usage information. See the JCarder analyzer reference for more information.

The JCarder analyzer reads information from jcarder_events.db and jcarder_contexts.db and constructs a lock acquisition order graph. It then tries to find cycles in that graph. Each found cycle identifies a potential deadlock situation.

For example, here is the JCarder analyzer run on the information produced by the agent for the modelview example program mentioned earlier:

% java -jar path/to/jcarder.jar
Opening for reading: ./jcarder_contexts.db
Opening for reading: ./jcarder_events.db

Loaded from database files:
   Nodes: 3
   Edges: 4 (excluding 0 duplicated)

Cycle analysis result:
   Cycles:          2
   Edges in cycles: 3
   Nodes in cycles: 2
   Max cycle depth: 2
   Max graph depth: 2

Ignoring 0 almost identical cycle(s).

Writing Graphviz file: ./jcarder_result_0.dot

If any potential deadlocks are found, JCarder creates Graphviz DOT files (named jcarder_result_x.dot) that describe the cycles. Unrelated parts of the graph are put into different DOT files to avoid unnecessary complexity when reviewing the result.

A PNG image file (here named example.png) can be generated from a DOT file like this:

dot -T png -o example.png jcarder_result_0.dot

This is the resulting image for the modelview example program:

It is also possible to run the dotty program to view the result directly on screen (with a somewhat cruder rendering):

dotty jcarder_result_0.dot

4.2. Interpreting the result

Consider this program:

class MyClass {
    Object myLock = new Object();

    void fum() {
        synchronized (myLock) {
        }
    }

    void fie() {
        fum();
    }

    synchronized void foo() {
        fie();
    }

    public static void main(String args[]) {
        new MyClass().foo();
    }
}

The JCarder analyzer run with -outputmode all produces this graph:

Nodes in the graph represent locks and edges represent lock acquisitions. Locks may have different colors:

Red: the lock is part of a multi-thread cycle
Yellow: the lock is part of single-thread cycle
White: the lock is not part of any cycle

More about single-thread and multi-thread cycles later.

The content of a lock node is a string representing the lock instance. In the example above, the monitor lock of a MyClass instance (unique ID 1C691F36) was acquired while acquiring the other lock.

An edge in the graph represents a lock acquisition made by a single thread that already holds another lock. The direction of the edge tells the order in which the locks were acquired. The label next to the edge includes information about the thread in question ("Thread:"), the acquired locks ("holding:" and "taking:") and the methods that acquired the locks ("in:").

4.3. Single-thread cycles

By default, the JCarder analyzer includes single-thread cycles (cycles that are created by just one thread) in the result. Since locks in Java are recursive, such cycles will not create any deadlock. But:

If the program makes use of a thread pool but only uses the same single thread except for concurrent incoming requests or under high load, all found cycles will be reported as single-thread cycles unless the test scenario consists of such concurrent requests or high load. During production use of the program, the cycles could come out as multi-thread cycles, resulting in potential deadlocks.
Module test cases used while performing a test with JCarder may sometimes be very simplified and perform all actions within a single thread, while the real program might execute the same methods by several different threads. If only a single thread is used by the module test case, all cycles found will be reported as single-thread cycles, but they could still be potential deadlocks in your real program.

One could also argue that a single-thread cycle is a sign of bad design — if there is only one thread in the cycle, why are locks acquired?

However, in many cases, it is either hard (or simply unwanted) to avoid single-thread cycles. JCarder can be told to ignore single-thread cycles by passing -outputmode mtcycles to the analyzer. By passing -outputmode all, nothing is pruned from the output; even non-cycles are included.

4.4. Gated cycles

In a large multi-threaded program, it is often the case that there are some top level coarse locks that are always taken before some more granular locks. For example, consider the following code:

class MyClass {
    Object gateLock = new Object();
    Object lockA = new Object();
    Object lockB = new Object();

    public class ThreadA extends Thread {
        public void run() {
            synchronized (gateLock) {
                synchronized (lockA) {
                    synchronized (lockB) {
                    }
                }
            }
        }
    }

    public class ThreadB extends Thread {
        public void run() {
            synchronized (gateLock) {
                synchronized (lockB) {
                    synchronized (lockA) {
                    }
                }
            }
        }
    }

    public static void main(String args[]) {
        new ThreadA().start();
        new ThreadB().start();
    }
}

Although the order of lockA and lockB has been inverted, the inversions can never occur at the same time, since the lock acquisitions are both covered by gateLock.

JCarder will by default recognize these situations and remove such gated cycles from its output. In order to disable this functionality, you may use the -include-gated-cycles option when running the analysis.

5. Performance

Since JCarder makes the analyzed program write to a file for each lock that is acquired, the performance penalty depends on how often locks are used in the program. The file writes are buffered, but performance will still be affected. A lock-intensive program may slow down by, say, 5–10 times, while other programs may be almost unaffected.

The memory penalty imposed by JCarder should be relatively small for most programs. JCarder keeps an internal cache to improve performance, but since the cache uses java.lang.ref.SoftReference for its entries, the cache size will be decreased automatically if the maximum heap size is reached.

6. Limitations

JCarder currently cannot find potential deadlock problems where lock cycles are due to:

usage of locks in native code (implemented via JNI or similar)
usage of locks from the java.util.concurrent package
internal synchronization in the standard library

7. Reference

7.1. JCarder Java agent

Usage

Add the jcarder.jar file as a Java agent. This is normally done by passing a -javaagent:path/to/jcarder.jar option to the JVM.

If instrumentation of AWT and Swing classes is wanted, jcarder.jar must be on the bootstrap class path. This can be accomplished by passing -Xbootclasspath/a:path/to/jcarder.jar to the JVM.

Example

java -Xbootclasspath/a:path/to/jcarder.jar -javaagent:path/to/jcarder.jar \
     -Djcarder.outputdir=path/to/outputdir -jar yourprogram.jar

Configuration

The JCarder Java agent can be configured by the following Java system properties:

jcarder.dump

Set to true to turn on dumping of instrumented and original class files to disk (for debugging purposes); default: false

jcarder.loglevel

Level of log messages to print to the log file (one of severe, warning, info, config, fine, finer, finest); default: fine

jcarder.outputdir

Directory to which the agent should write information.

You may specify the special text @TIME@ in this path, and the current unixtime will be substituted in its place when the agent starts.

default: current directory

Any of the above options may also be specified as java agent options where the jcarder. prefix is dropped. For example:

java -javaagent:path/tojcarder.jar=outputdir=output,dump=false ...

7.2. JCarder analyzer

Usage

Run jcarder.jar as a JAR file to analyze the output from the JCarder Java agent. The analyzer does not take any positional arguments.

Example

java -jar path/to/jcarder.jar -d path/to/outputdir -outputmode mtcycles

Options

The JCarder analyzer accepts the the following options:

-d <directory>: Read results to analyze from <directory> (default: current directory)
-help: Print this help text
-includepackages: Include packages (not only class names) in graph
-include-gated-cycles: Include also cycles, where all the lock acquisitions forming a cycle, are guarded by a gated lock.
-outputmode <mode>: Set output mode to <mode> (one of all, cycles, mtcycles); all: include everything; cycles: only include cycles (this is the default); mtcycles: only include multi-thread cycles
-printdetails: Print some more information to standard output
-version: Print program version

JCarder manual

Contents

1. Introduction

2. Requirements

3. Execution

3.1. Running the agent

3.2. How to get good results

3.3. Instrumentation of the standard library

4. Analysis

4.1. Running the analyzer

4.2. Interpreting the result

4.3. Single-thread cycles

4.4. Gated cycles

5. Performance

6. Limitations

7. Reference

7.1. JCarder Java agent

Usage

Example

Configuration

7.2. JCarder analyzer

Usage

Example

Options