Earlier this month we posted Takipi’s 1st Java puzzle, as a tribute to “Java Puzzlers” by Joshua Bloch and Neal Gafter. We assumed this puzzle might get some attention, but even we were amazed with the sheer volume of responses and their quality.
We received hundreds of solutions, some more creative than others (not necessarily a good thing in this case). Some readers told us it took several sleepless nights to solve this puzzle, while others thought they had the correct answer without changing anything at all. Some developers even missed the deadline, but sent a solution anyway, just to share their take on it.
Eventually, out of 34 correct answers, one was randomly drawn as the winner, and will receive a $250 Amazon gift card. However, we had so much fun creating this puzzle and getting great responses from the Java community, we will definitely have more puzzles in the near future. You can follow us on twitter to know exactly when they’re posted.
Let’s cut to the chase.
What Caused the Bug?
(If you haven’t seen the puzzle itself yet, you can find it here)
The bug in the program stems from what is called unsafe publication.
Notice the method advanceScore, in conjunction with the constructor of BoxScore and the assignment of the result in MatchSimulator.advanceSimulation.
At first glance, the code seems rather harmless:
Performs some reads and arithmetic;
Passes the values into the constructor;
The constructor in turn sets the values of its object members;
The constructed object is returned;
The resulting object is then set into the appropriate member of match.
The problem in general is that the Java Memory Model (JMM) does not guarantee that reads and writes from and to shared variables are performed in the order in which they appear in the code, barring certain conditions and constraints.
The spec gives JVM and compiler implementations freedom to perform various optimizations, including reordering read/write instructions, as long as they adhere to the semantics specified in the JMM.
Specifically, what’s interesting in our case — the JMM does not require that all the assignments to object members which appear in the constructor be performed before the constructor returns.
This means that our verifier thread might see partially constructed BoxScore objects, if the JVM decides to assign the new instances to homeScore or visitorsScore before performing the field assignments in its constructor.
For example, the verifier thread might see a BoxScore instance with score = 12, but pt1Made = 0 and pt2Made = 0, causing its assertion to fail and an exception to be thrown!
What can we do about it?
The final approach
Remember when we said that the JMM allows this freedom with some constraints? One of the mechanisms which helps us help the JVM help us, is the final keyword.
Notice that BoxScore is effectively final. That is, the only assignments we perform to its members are in the constructor. This means we can safely add the final keyword to all three members like so:
[java]
public class BoxScore {
private final int score;
private final int pt1Made;
private final int pt2Made;
…
[/java]
This has some major advantages. The first is that it makes it obvious to readers of the code that the BoxScore objects are immutable. The second, is that it enforces immutability in the syntactic level, meaning that any future assignment attempts past the constructor will not compile.
The third advantage, and the one that’s relevant to the case at hand, is that final fields get special treatment in the JMM: Assignment to final fields must be made visible to readers by the time the constructor completes.
This means that adding the final keyword to our instance fields fixes the bug — the verifier can no longer see partially constructed objects. Unfortunately, this means adding 3 tokens to our code instead of just one.
Luckily for us, a single final field is enough to emit a memory barrier at the end of the constructor in the Oracle/HotSpot JVM implementation. See this snippet from the HotSpot source code:
[java]
if (wrote_final()) {
// This method (which must be a constructor by the rules of Java)
// wrote a final. The effects of all initializations must be
// committed to memory before any code after the constructor
// publishes the reference to the newly constructor object.
// Rather than wait for the publication, we simply block the
// writes here. Rather than put a barrier on only those writes
// which are required to complete, we force all writes to complete.
//
// “All bets are off” unless the first publication occurs after a
// normal return from the constructor. We do not attempt to detect
// such unusual early publications. But no barrier is needed on
// exceptional returns, since they cannot publish normally.
//
_exits.insert_mem_bar(Op_MemBarRelease, alloc_with_final());
[/java]
This means we can add one single final to one of the fields, and the bug is fixed!
The volatile approach
When the volatile keyword is added to a field, it tells the compiler that the field is modified and accessed frequently by multiple threads. The JVM must then ensure that all writes to the volatile field are visible to any reading thread for any subsequent reads of that field. This means fresh data is read from main memory instead of from thread-local caches.
Making the homeScore and the visitorsScore fields volatile will ensure that the verifier thread reads up-to-date and complete instances of BoxScore. Again this means 2 tokens added to our code. Argh!
Another option, is making the BasketballMatch.instance singleton field non-volatile. This allows the verifier thread to verify a cached copy of BasketballMatch. Non-volatility comes with a price, however, and the main problem with this solution is that the verifier thread might end up working on stale copies of the BasketballMatch object.
Finally, there are the members of BoxScore. Can volatility help us there?
According to the JMM, writing to a volatile field must follow all other reads/writes in the thread, even of non-volatile fields. In other words — you guessed it — a volatile write results in a memory barrier. See:
[java]
void Parse::do_put_xxx(Node* obj, ciField* field, bool is_field) {
bool is_vol = field->is_volatile();
// If reference is volatile, prevent following memory ops from
// floating down past the volatile write. Also prevents commoning
// another volatile read.
if (is_vol) insert_mem_bar(Op_MemBarRelease);
[/java]
Since we are limited to single-token changes only, we must carefully choose which field to make volatile. Unlike the case in the final approach, the decision here is not arbitrary; we must ensure that the memory barrier is emitted correctly. The only reasonable place to put the mem-bar would be after the last of the 3 writes. Since the last field that’s written in the constructor of BoxScore is pt2Made, pt2Made is the only field that can yield a reliable memory barrier. Hence, adding the volatile keyword to the pt2Made field fixes the bug.
The synchronized approach
Another possible solution to our data-race is adding the synchronized keyword to the advanceScore method.
Initially, it may seem weird. Why would this work? Synchronizing the writing thread alone, leaving the reading thread as-is shouldn’t make any difference, as the reading thread still isn’t concerned with the lock we introduced.
Indeed the mutex is not what makes the difference here, and access to the BoxScore instances is not mutually exclusive even after adding the synchronized keyword to advanceScore. What the synchronized block does, however, is introduce a memory barrier at the exit of the method advanceScore.
This memory barrier, in essence, causes all the assignments to the object fields to be flushed and visible to other threads, before the new instance is returned. Only then, the new BoxScore instance is propagated up the stack and assigned to the field which is eventually read by the verifier thread.
All Three approaches above were considered correct, and developers who suggested any of them entered the draw.
The creative approach
Some of the more creative suggestions we received include:
Commenting out the verifier thread altogether,
Removing the keyword throw from throw new IllegalStateException(…),
Replacing simulatorThread.start() with simulatorThread.run(),
Moving simulatorThread.join() above verifierThread.start(),
Running the program with the -Xint command line argument to avoid JIT,
Adding Thread.sleep(###) just before verifierThread.start().
These solutions, of course, were not considered as correct ones.
The winner
The winner of the 1st Java Puzzle is Sean Molloy, who took the synchronized approach.
Congrats to the winner, and thanks to all the developers who participated. Think you have a better solution? Use the comments.
Takipi detects all errors in production and shows the variable values as if you were there when it happened –
Deploy now and get a free Java T-shirt