Testing multithreading Java seams impossible. Bugs depend on the specific timing and sometimes even on a specific processor type or JVM. But Java has a specification that enables us to test multithreaded software: The Java memory model.

The Java memory model enables us to execute all thread interleavings of a multithreaded program as long as the program is data race free. And it defines rules to automatically check if a program contains a data race. So we can use a two-step approach for testing: In the first step, we execute all thread interleavings. In the second step, we check if the test contained data races. I have implemented those two steps in a tool called vmlens.

What is the Java memory model?

The Java memory model is a specification to define what happens when multiple threads read and write the same memory location As Hans Boehm, one of the authors of the Java memory model writes:

We have been repeatedly surprised at how difficult it is to formalize the seemingly simple and fundamental property of “what value a read should return in a multithreaded program.”

The Java memory model answers this question in the following way:

If a program has no data races, then all executions of the program will appear to be sequentially consistent.

Sequential consistency means that a run of a multi-threaded program is one specific interleaving of the source code statements of the different threads. So to execute a sequential consistent program we can use the following algorithm: Select one thread and execute the current statement of this thread. Repeat this till all threads are terminated.

But Java programs are only sequential consistent when they are data race free. A program contains a data race when it contains a read and a write or two writes to the same memory location which are not ordered by the so-called happens-before order. Synchronization actions like the read and write from a volatile field generate an order between multiple threads, the happens-before order. For example the write to a volatile variable happens-before all subsequent volatile reads from this variable. And if all memory accesses can be ordered through this happens-before relation our program is data race free.

In the following example, the read and write to the field i are ordered through a happens-before relation. In this interleaving the write to the volatile variable v in thread A comes before the read from this variable in thread B. So the write to the normal field i in the thread A can be ordered with the reading from this field in thread B. And so the following interleaving is data race free:

Compare this to the following interleaving of the same program. Here the read from the field i in thread B can not be ordered with the write to this field in thread A. And so the following interleaving contains a data race.

The weaker form of sequential consistency of the Java memory model has the advantage that it allows the JVM to apply optimizations of the generated machine code. And it makes caching in the processor possible.

This blog post from Martin Thompson shows how the caching in the CPU works and how caching is related to the Java memory model. And this post from Aleksey Shipilev gives a comprehensive overview of the Java memory model.

And this weaker form of sequential consistency means that we only need to consider synchronization actions when we want to test all thread interleavings.

How does the Java memory model enable the testing of multithreaded Java?

When testing we only need to consider thread interleavings which lead to a different happen-before order. So we calculate all orders the synchronization actions of the test run can create. And for each order, we execute one thread interleaving which leads to this order.

After we executed all those thread interleavings we need to check that the test is data race free. Therefore we check for each multi-threaded memory access if this access can be ordered according to the happens-before order.

Testing multi-threaded software by executing all thread interleavings is not new. The tool Concuerror implements this approach for the language Erlang, a programming language without shared memory. Finding data races at runtime is also not new. A prominent example is ThreadSanitizer which detects data races in C++ programs and golang and probably at sometime Java.

New is the combination of those two techniques in one tool to systematically test multithreaded Java programs.

A multithreaded unit test

The following JUnit test implements the examples from above in a real test. One thread reads the variable i and the volatile variable v. The other thread writes to those two variables. To test all thread interleavings we put the complete test in a while loop iterating over all thread interleavings using the class com.vmlens.api.AllInterleavings.

You can download the source code of the example from Github here.

import org.junit.Test;
import com.vmlens.api.AllInterleavings;
public class TestReadWrite {
 volatile int v = 0;
 int i = 0;
 @Test
 public void testUpdate() throws InterruptedException {
   try (AllInterleavings allInterleavings =
     new AllInterleavings(TestReadWrite.class.getName());) {
	 while (allInterleavings.hasNext()) {
	   Thread first = new Thread(() -> {
		 i = 5;
		 v = 7;
	   });
	   Thread second = new Thread(() -> {
		 int x = v;
		 int y = i;
	   });
	   first.start();
	   second.start();

	   first.join();
	   second.join();
	   }
    }
 }
}

vmlens traces all multi-threaded memory accesses and synchronization actions as java agent using byte code transformation. Using this trace vmlens calculates all potential thread interleavings and checks for data races. Running the above test, vmlens reports the following data race.

Performance of the multithreaded unit tests

Using this two-step approach it is possible to test even complicated data structures like java.util.concurrent.ConcurrentHashMap. For example, testing put using two threads takes 353 iterations and less than 3 seconds on my Intel i5 3,40 GHz 4 core CPU, see the test com.vmlens.examples.javaMemoryModel.TestConcurrentHashMapWithoutAtomicTwoPuts. Since we always run one thread at a time the performance depends on the CPU clock speed and not on the available cores.

But typically we do not write new concurrent data structures. We use existing data structures. Here we can use the fact that most of the methods of concurrent data structures are atomic. And for two atomic methods a and b we only need to test two combinations. The combination a before b and the combination b before a. So we can drastically reduce the iteration count when testing the usage of atomic methods.

Summary

The Java memory model guarantees that all data race free programs are sequentially consistent. This allows us to test multithreaded programs in a two-step approach. In the first step, we execute all thread interleavings and in the second step, we check for data races. This allows us to test multithreaded Java in a systematic, reproducible way.