Imagine a bacon-wrapped Ferrari. Still not better than our free technical reports.
See all our reports

Concurrency torture: testing your code within the Java Memory Model

java concurrency sad polar bear

Not sure about you, but one the most frustrating kind of bugs for me is dealing with concurrency issues. That is unless you manage to destroy your tools with your other tools. However, that is a story for another time, and given that we’re talking mostly about Java here, destroying tools is not that straightforward.

It often takes a lot skill to understand concurrency issues, plus some measure of agility to debug and wisdom to fix them. In fact, one of the most valuable assets in fixing those is a full understanding of what’s is going on under the hood of your Java program. In this post, I will show an example of a simple-yet-non-trivial concurrent program and prove that even in this simplistic case, there are outcomes which are hard to predict. Luckily, in the JVM ecosystem there are tools for almost everything and with the help of a concurrency test framework called JCStress, we can predict the behavior of concurrent Java program and verify our intuition of what’s happening there.

Diving into the problem

Recently, I stumbled upon an extremely insightful article about how the Java Memory Model, JMM for short, works. For the uninitiated, JMM, see 17.4 of the Java Language Specification, is the specification that formalizes how a JVM implementation should treat memory accesses and, basically, answers to a crucial question:

What values can a given read instruction in a program observe at a given time?

If you’re lucky enough to understand spoken Russian, I can recommend an excellent session “Pragmatics of Java Memory Model” by Aleksei Shipilev. It should shed some light on what the JMM is, why it is important and why concurrent programming is so complicated. Others, no doubt, can enjoy other resources and presentations on the subject, for example:

However, currently, I don’t want to dive into the theory of JMM and instead want to offer a quick example that shows its peculiarities and importance.

Guess the output

Originally, I found out about this example from Anton Arhipov, product manager for JRebel, who’s a dedicated fan of all puzzling questions about programming languages in general, and Java and JVM in particular.

So here it is:

import java.util.BitSet;
import java.util.concurrent.CountDownLatch;

public class AnExample {

   public static void main(String[] args) throws Exception {
       BitSet bs = new BitSet();
       CountDownLatch latch = new CountDownLatch(1);
       Thread t1 = new Thread(new Runnable() {
           public void run() {
               try {
                   latch.await();
                   Thread.sleep(1000);
               } catch (Exception ex) {
               }
               bs.set(1);
           }
       });
       Thread t2 = new Thread(new Runnable() {
           public void run() {
               try {
                   latch.await();
                   Thread.sleep(1000);
               } catch (Exception e) {
               }
               bs.set(2);
           }
       });

       t1.start();
       t2.start();
       latch.countDown();
       t1.join();
       t2.join();
      // crucial part here:
       System.out.println(bs.get(1));
       System.out.println(bs.get(2));
   }
}

The question is, what values will it print? What values can it print in general, as in what is it allowed to print without being accused in running on a corrupted JVM?

Let’s see what this program does:

  • We initiate a Bitset;
  • Two Threads run concurrently and set the first and second bits respectively;
  • We are trying hard to run schedule those threads to run at the same time;
  • We read values and print them.

If you can answer the questions above from the top of your head, congrats, you’re awesome. Tweet me the answer at @shelajev to show that awesomeness.

For the rest of us, we need to construct some form of a test to check the behavior.
Obviously, one can just run this example and observe the output, answering the first part of the question, however, answering the second about all allowed outputs is trickier.

Practice makes perfect

Luckily, there’s an app for that there are tools that can help us. JCStress is a test harness that is created specifically to fiddle with these kinds of questions.

We can easily embed our test case into the form recognized by JCStress. In fact, it is kind enough to provide us with interfaces for multiple possible scenarios. We need a test where 2 threads will run concurrently, with our result represented by two boolean values.

What we use here is an Actor2_Arbiter1_Test<BitSet, BooleanResult2> interface, which will humbly provide us with method stubs for our two threads and a method to convert a result in a form of BitSet state into a pair of booleans. We’ll need a Java 8 JVM at hand to run this, but it is not a problem nowadays.

Check out the test implementation below. Isn’t it amazingly concise?

public class AnExampleTest implements 
           Actor2_Arbiter1_Test<BitSet, BooleanResult2> {

  @Override
  public void actor1(BitSet s, BooleanResult2 r) {
    s.set(1);
  }

  @Override
  public void actor2(BitSet s, BooleanResult2 r) {
    s.set(2);
  }

  @Override
  public void arbiter1(BitSet s, BooleanResult2 r) {
    r.r1 = s.get(1);
    r.r2 = s.get(2);
  }

  @Override
  public BitSet newState() {
    return new BitSet();
  }

  @Override
  public BooleanResult2 newResult() {
    return new BooleanResult2();
  }
}

Now when running this test, the harness will attempt all kinds of tricks to obtain all possible combinations of factors to run these actors: concurrently and not, with and without load, and many-many times in a row, so all possible results are recorded.

When you want to see how your concurrent code behaves, it is definitely a superior approach than trying to come up with all subtle details yourself.

Furthermore, to enjoy the comprehensiveness of the JCStress harness we need to provide it with an interpretation of the possible results. We do that using a simple XML file below.

  <test name="org.openjdk.jcstress.tests.custom.AnExampleTest">
    <contributed-by>Oleg Shelajev</contributed-by>
    <description>
      Tests if BitSet works well without synchronization.
    </description>
    <case>
      <match>[true, true]</match>
      <expect>ACCEPTABLE</expect>
      <description>
        Seeing all updates intact.
      </description>
    </case>
    <case>
      <match>[true, false]</match>
      <expect>ACCEPTABLE_INTERESTING</expect>
      <description>
        T2 overwrites T1 result.
      </description>
    </case>
    <case>
      <match>[false, true]</match>
      <expect>ACCEPTABLE_INTERESTING</expect>
      <description>
        T1 overwrites T2 result.
      </description>
    </case>
    <unmatched>
      <expect>FORBIDDEN</expect>
      <description>
        All other cases are unexpected.
      </description>
    </unmatched>
  </test>

Now we’re ready to get this beast running. Start the tests by using a command line below.

java -XX:+UnlockDiagnosticVMOptions -XX:+WhiteBoxAPI -XX:-RestrictContended -jar tests-custom/target/jcstress.jar -t=".*AnExampleTest"

What we get as a result is a very handsome report.

JCStress result report page

Now it is clear that not only can we get the expected result, where both threads have set their bits, but also encounter a race condition, where one thread overwrites result of the other.

Even if you saw it coming, having proof is pleasant, isn’t it?

By the way, if you’re pondering about how to fix the code, the answer is to read the Javadoc for the BitSet class carefully, and realize that it is not thread safe and requires external synchronisation. This can easily be accomplished by adding synchronized blocks around setting the values.

synchronized (bs) {
  bs.set(1);
}

Conclusion

Concurrency is a very complicated topic and reasoning about concurrent programs requires lots of experience and skill. Luckily, Java ecosystem is extremely developed and there are tools that can help you on this road.

By the way, if you have a custom approach to solving concurrency issues, please share that in the comments below or reach out to me on Twitter: I’d love to hear about it.

In this post we’ve looked at a simple puzzle involving non synchronized access to BitSet, but the approach shown above is applicable to all kinds of concurrency puzzles in Java. Lots of corner cases you can stumble upon are described in the documentation, but who reads those, right?

So read Javadocs carefully and stay safe! Or, if you truly like to live dangerously, check out this Serkan Özal’s post about Object Layouts, Alignments and Unsafe in Java.

  • David Leppik

    A Java concurrency fuzzing tester. Sweet. Reminds me of a friend who, years ago, wanted to write a C compiler that would randomly emit any behavior allowed by the the C specification. Especially, if I remember correctly, when it came to the contents of uninitialized memory. This was extremely impractical: no predictable optimizations, and the number of unspecified behaviors was astronomical.

  • Jonathan Fisher

    This _is_ sweet

  • croz

    Unless this is Java 1.8, the CountDownLatch won’t be visible to the anonymous inner classes unless it’s made final.

    The answer to the first puzzler is “there’s no way to tell”. When you start the threads, either one could execute first.

  • a

    So, why are you sharing a BitSet between two threads? Sharing stuff between threads is a bad practice.

  • Check out thread weaver for testing concurrency in Java. It runs much faster and is a way more reliable approach for unit testing in my opinion. You won’t catch all specifics of the JMM when using invalid caches but race conditions and dead locks are covered pretty well. https://code.google.com/p/thread-weaver/

  • jeremyheiler

    It illustrates the point he wanted to make.

  • Tarun Ramakrishna

    I don’t get this. BitSet has been explicitly documented as not thread-safe. So, why bother with the test ? “A BitSet is not safe for multithreaded use without external synchronization.”.

  • arhan

    Who reads documentation anyway? ;)
    Here, BitSet is just used as an example, nothing special.