Testing Race Conditions in Java with Weaver

This tutorial walks through a series of concurrency problems to demonstrate Weaver, a framework for writing multi-threaded unit tests in Java. Weaver allows you to create mutliple threads inside a unit test, and to control how these threads are stopped and started. By doing this, you can replicate potential race conditions, and verify that your code performs correctly.

Note that Weaver will not necessarily help you detect unknown race conditions. Like any testing framwework, it requires you to anticipate potential problems, and write tests to cover them. In addition, it does not detect thread starvation issues, and it will not detect deadlocks (although your test will timeout if a deadlock occurs.) However, it does provide a repeatable and consistent way to verify that certain aspects of your code are threadsafe.

The source code for this tutorial is available in the examples subdirectory of the Weaver distribution, along with an Ant build file that will compile and run the tests.

Note that the example source code contains various multi-threading bugs, and hence the tests are expected to fail when run. As part of the tutorial we will fix these errors.

A Simple Class

Suppose we have the following Java class: 
 
public class UniqueList<E> extends ArrayList<E> {
 
  /**
   * Adds an element iff it is not already present in this list. Returns true
   * if the element was added, and false if it was already found.
   */
  public boolean putIfAbsent(E elem) {
    boolean absent = ! super.contains(elem);
    if (absent) {
      super.add(elem);
    }
    return absent;
  }
}
This class contains a potential race condition. If we start with an empty list, and two separate threads invoke putIfAbsent with the same element, then depending on the exact ordering of the two threads it is possible that the same element could be added twice, thus violating the class' contract. (Note that in this case and the cases that follow, we are assuming that the example classes are intended to be called from multiple threads. If the contract of UniqueList stated that it was only intended to be called from a single thread, then the above code would be correct.)

We can detect this race condition by inspecting the code, but it is difficult to write a unit test that demonstrates the problem. If we create two separate threads in our test, and start them independently, it would be difficult to synchronize them so that the potential bug is revealed. We could create a soak test that tries to recreate the problem by running the same operations over and over again, hoping that at some point the threads will be scheduled in such a way as to trigger the bug, but this is neither reliable or repeatable.

Weaver provides a framework that allows us to control the exact ordering of threads, and thus create repeatable tests.

A first Weaver Test

The class UniqueListTest in the examples directory provides a test that demonstrates the problem with UniqueList. From the examples directory, you can run it with: 
 
  ant unique-list-test
This should generate a failure.

Let's take a look at the test code in more detail. The test is defined by a set of special annotations. The @ThreadedBefore annotation defines a setup method that is invoked at the start of the test. The @ThreadedMain and @ThreadedSecondary methods are then invoked in two separate threads. When the main and secondary methods have both run, the @ThreadedAfter method is invoked to verify the results of the test. 

  @ThreadedBefore
  public void before() {
    // Set up a new UniqueList instance for the test
    uniqueList = new UniqueList<String>();
    System.out.printf("Created new list\n");    
  }
 
  @ThreadedMain
  public void main() {
    // Add a new element to the list in the main test thread
    uniqueList.putIfAbsent(HELLO);
  }
 
  @ThreadedSecondary
  public void secondary() {
    // Add a new element to the list in the secondary test thread
    uniqueList.putIfAbsent(HELLO);
  }
 
  @ThreadedAfter
  public void after() {
    // If UniqueList is behaving correctly, it should only contain
    // a single copy of HELLO
    assertEquals(1, uniqueList.size());
    assertTrue(uniqueList.contains(HELLO));
  }

Running the test as-is will result in a failure. In the output you should see something like this: 

 
    [junit] Testcase: testPutIfAbsent took 0.524 sec
    [junit] 	Caused an ERROR
    ...
    [junit] Caused by: junit.framework.AssertionFailedError: expected:<1> but was:<2>
    [junit] 	at UniqueListTest.after(UniqueListTest.java:70)
As you cans see, we have managed to add two instances of the string HELLO to the list. To fix the problem, try editing UniqueList as follows: 
 
public class UniqueList<E> extends ArrayList<E> {
 
  public synchronized boolean putIfAbsent(E elem) {
    ...
Run the test again, and it should pass.

Iterating through the Test Case

Take a look at the standard output for the test. It should look something like this: 

 
In testPutIfAbsent
Created new list
Created new list
Created new list
Created new list
It looks as though we're running the test four times. What's going on?

In fact, Weaver is running four different variants of the same test. If we go back and look at the original method, there are four executable lines. 

 
  public boolean putIfAbsent(E elem) {
1:    boolean absent = ! super.contains(elem);
2:   if (absent) {
3:      super.add(elem);
    }
4:   return absent;
  }
Weaver runs the test four times. On the first pass, it runs the @ThreadedMain method until it reaches line 1. Then it pauses the main thread, and runs the @ThreadedSecondary method. On the second pass it runs the @ThreadedMain method up until line 2, and then runs the @ThreadedSecondary, and so on.

(Internally, Weaver achieves this by instrumenting the bytecode of the classes under test. By adding callbacks into the test framework, we can pause one thread and run another. This will be covered in more detail below.)

To verify Weaver's behaviour, remove the synchronized keyword again, and re-run the test. It will fail, and if you look at the test output we should see: 

 
In testPutIfAbsent
Created new list
Created new list
...
The first time the test is run, Weaver stops just before line 1, and then allows the second thread to run. This configuration is in fact safe: the variable absent has not yet been evaluated. However, on the second run, we stop at line 2, and this triggers the bug.

For more debugging, try adding the following to the test: 

 
  public void testThreadedTests() {
    runner.setDebug(true); // Add this line
    runner.runTests(getClass(), Player.class);
  }

A More Complex Class

For simple methods, allowing Weaver to break once at every line is sufficient, but for more complex methods there may be problems. Certain lines may be executed several times, due to loops, but Weaver will only stop on the first execution of that line. Long methods may be slow to test, and many of the test cases may be unnecessary.

More seriously, stopping at certain lines may not represent a valid state. For example, consider the class in Player.java. This maintains a mapping between a Controller that issues commands to play audio media assets, and the underlying AudioService that controls the sound card. (This is a simplified version of a real class, and a real bug.) After the Player has started playing an asset, it adds a mapping from the asset back to the controller. 

 
  public int playAsset(String assetName, Controller controller) {
    validateAsset(assetName);
 
    // Start playing the asset, and get the token that identifies the audio stream.
    int token = service.cue(assetName, this);
 
    // Add a mapping from token back to the controller that owns it.
    controllerMap.put(token, controller);
    return token;
  }
When the audio finishes, the mapping is used to inform the controller. This happens when the AudioService invokes the onAudioPlayed method in a separate thread. 
 
  public void onAudioPlayed(int audioToken) {
    Controller controller = controllerMap.get(audioToken);
    controller.onFinished();
  }
Once again, we have a potential race condition. If the media asset has a problem, or is of zero length, it is possible that it will terminate immediately, and invoke the onAudioPlayed method before we have had a chance to add the token into the controllerMap. If this happens, then we will get an error when we try to retrieve the controller from the map.

We would like to test this scenario. We could run the playAsset method in one thread, and the onAudioPlayed method in a separate thread. However, we need to ensure that we do not call onAudioPlayed in the second thread until after we have called service.cue in the main thread. (Because there is no way that an asset can finish playing before it has started.) In order to make this work, we need finer-grained control over where the main thread stops. We can do this using CodePositions.

CodePositions

A CodePosition represents a point of execution within the class under test. Once we have defined a position, we can then cause Weaver to break execution at that position.

Currently, CodePositions are defined with respect to methods. A position can be specified at the start or end of a method, or at the point before or after a method calls another method.

In the Player example, we want to stop at the point just after the call to service.cue. 

 
    int token = service.cue(assetName, this);
                                                <<== Stop here
    controllerMap.put(token, controller);
    return token;
  }
The CodePosition that we want can be defined using a MethodRecorder. A MethodRecorder contains a dummy instance of the object under test, which can be used in much the same way as an EasyMock mock object.

In EasyMock we can say: 

 
  service = createMock(AudioService.class);
  expect(service.cue(ASSET, player)).andReturn(TOKEN);
and this will tell the mock object to expect a call to the cue method, and return the given token.

Similarly, we can create a CodePosition with the following syntax: 

 
  CodePosition cp = recorder.atStartOf(player.playAsset(null, ASSET);
This produces a position at the start of the method playAsset. Note that player is a dummy instance of the Player class, just like an EasyMock mock.

A more complete example can be found in PlayerTest.java, where we have the following: 

 
    // Create a MethodRecorder for the Player
    MethodRecorder<Player> recorder = new MethodRecorder<Player>(Player.class);
 
    // Get hold of a dummy Player instance so that we can record method calls.
    Player player = recorder.getControl();
 
    // Get hold of a dummy AudioService instance so that we can record method calls.
    AudioService service = recorder.createTarget(AudioService.class);
 
    // Specify a position in "playAsset" after calling "service.play"
    CodePosition cp = recorder.
        in(player.playAsset(null, ASSET)).
        afterCalling(service.cue(ASSET, null)).
        position();
The code position created here represents the point just after the call to cue, within the method playAsset. Once we have defined this position, we can then create a test thread that will break here.

Using CodePositions

To create the test, we define two runnable tasks. The main task will call Player.play(), and will break at the given code position. The second task will call Player.onAudioPlayed(), and will run when the main thread is broken. 
 
  private class PlayerMain extends MainRunnableImpl<Player> {
    ...
    @Override
    public void run() {
      player.playAsset(ASSET, controller);
    }
  }
 
  private class PlayerSecond extends 
      SecondaryRunnableImpl<Player, PlayerMain> {
    ...
    @Override
    public void run() {
      player.onAudioPlayed(TOKEN);
    }
  }
These two tasks are then declared to run in parallel, breaking at the position that we have defined: 
 
    CodePosition cp = getCodePosition();
    RunResult result = InterleavedRunner.interleave(new PlayerMain(), new PlayerSecond(), 
        Lists.newArrayList(cp));
The InterleavedRunner is a part of the Weaver framework. It allows two runnable tasks to be interleaved in a variety of ways.

To run the test, type: 

 
ant player-test
The test should fail. Fix it by adding the appropriate synchronization to Player.java, and verify that the test now passes.

Please see the PlayerTest class for full details of how the test works, including alternative methods for creating CodePositions.

Using Scripts for Greater Flexibility

Using the InterleavedRunner allows us to start one task, pause it at a certain point (or points) and let another task run. For more complex scenarios, Weaver offers Scripts. A Script is a series of operations that runs in a single thread. A Script can yield control to another Script at any point in its execution. When a Script yields, it will block until another Script yields control back to it again.

The sample below shows a simple script case. We create two scripts, main and secondary and add a task to each script. The main task yields control to the second script after invoking the AudioService.cue method. 

 
    final Script<Player> main = new Script<Player>(player);
    final Script<Player> second = new Script<Player>(main);
 
    // Create control and target objects to allow us to specify a release point.
    final Player control = main.object();
    final AudioService target = main.createTarget(AudioService.class);
 
    main.addTask(new ScriptedTask<Player>() {
      @Override
      public void execute() {
        // Tell the main script to release to the second script after we've called
        // AudioService.play() from within Plyer.playAsset()
        main.in(control.playAsset(ASSET, controller))
            .afterCalling(target.cue(ASSET, player))
            .releaseTo(second);
        player.playAsset(ASSET, controller);
      }
    });
 
    second.addTask(new ScriptedTask<Player>() {
      @Override
      public void execute() {
        player.onAudioPlayed(TOKEN);
      }
    });
 
    new Scripter<Player>(main, second).execute();
The above example comes from class PlayerTestUsingScript in the javatests directory. This shows the PlayerTest class rewritten to use scripts. A more complex example can be found in the UserCacheTest class, which analyses the read/write locks used in the UserCache class. Run it using: 
 
ant user-cache-test
The test code demonstrates two separate scripts, but you can create as many simultaneous Scripts as are necessary for your test scenario, and a Script can yield control to any other script. When debugging complex scripting scenarios, it may be helpful to insert logging statements in the various script cases.

Instrumentation, and how to Avoid It

As previously mentioned, Weaver creates breakpoints by modifying the classes under test. During the test, Weaver reloads these classes using a custom classloader, which instruments the bytecode as it is loaded. At every execution point, and at the start and end of every method call, the modified classes make a logging call into the test framework. Threads can be blocked when these logging calls are made.

This is why the test cases create an instance of ThreadedTestRunner in order to run the multi-threaded tests. The runner is responsible for loading the necessary test classes, performing the instrumentation, and then invoking the annotated test methods. Attempting to run the multithreaded test methods directly will typically generate an error, because breakpoints can only be created in classes that have been instrumented.

However, there are certain categories of test case where the added complexity of instrumentation is not necessary. Consider the class UserManager in the examples directory. This manages users that are stored in an underlying database, and displays a similar bug to the one that we first looked at: 

 
  Database db;
 
  public boolean addUser(String username) {
    boolean exists = db.userExists(username);
    if (!exists) {
      db.addUser(username);
    }
    return !exists;
  }
If two threads invoke this method at the same time, with the same username, then the underlying db.addUser method may be invoked twice with the same user.

To write a test for this, we need to block the first thread after the call to userExists. Because Database is an interface that we have defined, we can create our own fake implementation, and block the calling thread in there. Weaver provides a utility class that makes this straightforward. Firstly we need to create a fake Database instance. 

 
  private class FakeDatabase implements Database {
    @Override
    public void addUser(String username) {
      if (userExists(username)) {
        throw new IllegalArgumentException("User exists");
      }
      users.add(username);
    }
  }
  ...
  Database fakeDb = new FakeDatabase();
Then create a BlockingProxy. This is a dynamic proxy that forwards all calls to an underlying implementation, but will also act as a BreakPoint, blocking the calling thread at a specified location. 
 
  // Create a proxy that blocks after the call to 'useExists; 
  BlockingProxy<Database> dbProxy = 
      BlockingProxy.create(Database.class, fakeDb, "userExists", false);  Database db;
The BlockingProxy can then be used to control the interleaving of two threads. A full example is provided. To run it: 
 
ant user-manager-test
The test will fail. Fix the UserManager implementation by making the method synchronized, and the test should pass.

Exercise

The source directory contains another file with a concurrency problem. See NameManager.java. Write a test that demonstrates the problem.

Related Materials

  • JavaDoc -- Index

    • Document History

    Alasdair Mackintosh - initial revision, May 2009

    Copyright 2009 Weaver authors
    Licensed under the Apache License, Version 2.0 (the "License");