Close Encounters of The Java Memory Model Kind

The jcstress API is really simple, and best demonstrated by this trivial example:

The jcstress harness will concurrently execute, on instances of VolatileIncrementAtomicityTest, the methods actor1 and actor2. Given an instance of VolatileIncrementAtomicityTest one thread will be responsible for executing method actor1 exactly once, and another thread will be responsible for executing actor2 exactly once. Thus an instance will visited, eventually, by both threads, sometimes at the same time. Therefore, over the aggregation of many instances of VolatileIncrementAtomicityTest and executions producing results or samples, returned in instances of IntResult2, the test case above explores the atomicity of volatile increment.

If you run this test on just about any hardware, this would be the result:

Notice how often the 1, 1 case is present — this is when both threads have met on the same volatile field, and non-atomically incremented it.

Since concurrency testing is probabilistic, we have three distinct setup problems to deal with:

Before we go in, let us take a quick recap of Java Memory Model. The more detailed explanation can be found in "JMM Pragmatics", so if reading this you have a nagging feeling of misunderstanding, stop reading this post, re-read JMM Pragmatics transcript, and then get back here.

The Big Picture: Java Memory Model (JMM) describes the allowed program outcomes by describing what executions are conforming. It does so by introducing actions, and orders over actions, and consistency rules that govern what actions+orders+constraints constitute a valid execution. If a program result can be explained by some valid execution, then this result is allowed under JMM.

There are several basic bits in the formalism:

The first order of business is the confusion between the language specification, and what hits the real hardware. It is easy, nay comfortable, to read the language rules and think that it is exactly what the machine will do.

However, it is a very misleading way of thinking about the issue. Language specification describes the behavior of the abstract machine executing the program. It is the runtime’s job to emulate the behavior of the abstract machine. The point of contention here is that a compatible runtime is not obliged to compile the program exactly as it is written in the source code.

The actual requirement is much weaker: the runtime is obliged to produce results as if there is a compatible abstract machine execution that backs the results. What the runtime does to do the actual computation is up to the runtime. It’s all smoke and mirrors.

For example, if you write:

…​it would be remarkably odd to require that the language runtime actually does allocate storage for all three local variables, store values there, load them back, add them, etc. This whole method should be optimizable to something like this:

In fact, it is optimizable in most languages, and it is allowed to happen because the observed result of the execution is one of the results of abstract machine execution. As long as programs cannot call runtime’s bluff (= detect something that language specification disallows) the runtime is free to do stuff under cover.

Similarly, when JMM says (for example) that there are program actions tied into the synchronization order, it does not mean the actual physical implementation should be emitting those loads and stores to the machine code!

For example, if we have a program:

…​this program is actually optimizable into:

Even though the spec says about actions (x = 1), (x = 2), and (r1 = x) as synchronization actions tied into the synchronization order, blah blah blah, it does not mean the actual runtime has to do all the program operations. Most runtimes would though, because this analysis — whether someone should be able to observe (x = 1) — is generally rather complicated.^[2]

Quite a few folks who get themselves burned by the abstract JMM rules, rest their gaze at JSR 133 Cookbook for the Compiler Writers. All those sweet, easy to understand barriers are much easier to grasp than the arcanery of the formal model. So, many are boldly suggesting Cookbook is a brief description (or even a short equivalent) of Java Memory Model.

But haven’t you read the Preface there?

JSR 133 Cookbook is one of the possible, yet conservative, sets of rules to implement JMM. One of the possible means that a conforming implementation does not have to follow the Cookbook, as long as it satisfies the JMM requirements. Conservative means it does not go into the intricacies of the model, and instead provides a very simple, yet coarse, implementation. It might be unnecessarily strong for practical use. We can go even deeper in our conservatism, and still arrive at JMM-conforming implementation: make sure JVM runs on a single core, or have a Global Interpreter Lock, and then concurrency is trivial.

The Cookbook was written to aid the actual compiler writers to quickly come up with a conforming implementation. Are you a compiler writer looking for implementation guidance? No? Thought so. Move along then. The bad thing that happens after you digest the JSR 133 Cookbook is that you start to believe in…​

…​while in fact, they are not: they are merely an implementation detail. The easiest example why barriers are not reliable as a mental model, is the following simple test case with two back-to-back synchronized statements:

Naively, you may think the 1, 0 case is prohibited, because synchronized sections should execute in an order consistent with a program order.

Let’s see what barriers tell us about code semantics. In pseudo-code, this will do:

Yup, seems fine. x = 1 cannot go past y = 1, because it will meet barriers long before that.

However, the JMM itself allows observing 1, 0, because the reads of x and y are not tied in any ordering constraints, and therefore there exists a plausible execution that justifies observing 1, 0. More formally, whatever conforming execution you can imagine, the reads of x and y are not synchronization actions, and therefore SO rules do not apply to the induced actions. The reads are not tied into HB, and therefore no HB rules are preventing from reading the racy values. There are no causality loops in observing 1, 0 too.

Allowing this behavior in the model is intentional for two reasons. First of all, the hardware should be able to perform independent operations in whatever order it wants to maximize performance. Secondly, this enables interesting and important optimizations.

For instance, in the example above, we can coalesce back-to-back locks:

…​which improves performance (because lock acquisition is costly), and allows further optimizations within the synchronized block. Notably, since the writes of x and y are independent, we may allow hardware to execute them in an arbitrary order, or allow optimizers to shift them around.

If you run the example above on an actual JVM and hardware, this is what happens on x86 with JDK 9 "fastdebug" build (needed to gain access to instruction scheduling fuzzing):

Notice the interesting case, that is our 1, 0. Surprise!

Disabling lock optimizations with -XX:-EliminateLocks trims down the number of occurrences of this interesting case to zero:

On POWER, the interesting case is present even without messing with instruction scheduling, because hardware guarantees are weaker:

There are other kinds of plausible optimizations around barriers that runtimes are making, or will choose to do in the future. Even JSR 133 Cookbook has the "Removing Barriers" section that gives a short outline of what elision techniques are readily available.

Given that, how can you trust barriers, if they are routinely removable?

The second part of the confusion is the notion of committing to memory. The pre-Java 5 memory model had the notion of "thread local caches" and "main memory". "Flushing to main memory" had some meaning there. In the new post-Java 5 model this is not the case. However, while most people moved on, they still implicitly rely on "main memory" abstraction as the basis for their mental models. That naive mental model says: when operations finally commit to the memory, memory will serialize it.

This intuition is broken on two accounts. First, memory is already asynchronous and so serialization is not guaranteed. Second, most of the interesting things are happening on the micro-scale of cache coherency, not the "actual" main memory.

Here comes the "Independent Reads of Independent Writes" (IRIW) test. It is really simple:

But this example is profound for the way you understand concurrency. First of all, consider whether the outcome (r1, r2, r3, r4) = (1, 0, 1, 0) is plausible. One may come up with the "reordering" explanation: reorder r3 = y and r4 = x, and the result is trivially achievable.

Okay then, since we know where the troubles lie, let’s add fences to inhibit those pesky reorderings:

And then run it on POWER:

Dang it! But how is that possible? We use those magic fences that inhibit reorderings!

The trouble comes from the fact that some machines, notably POWER do not guarantee multi-copy atomicity: "Either all processors see the write, or no processor does (yet)".^[4] The absence of this property precludes the existence of total store order, even if you put fences all around the stores.

If we put volatile into IRIW example, then the JVM would take additional steps to preserve sequential consistency.^[5] Notably, putting hwsyncs before the volatile reads. Therefore, this example works like a charm:

"But hey, Aleksey, see the part of the specification that actually calls out commits!":

The sad part is that reading that chapter for the first time, you can get tunnel vision, meet the familiar "commit" word, assign your own meaning to it, and disregard the rest of the chapter. That "commit" in JLS 17.4.8 is not about committing to memory, it is a part of formal validation scheme that tries to verify that there are no self-justifying action loops in the execution. This validation scheme does not generally preclude races, does not preclude observing different writes, or observing them in a non-intuitive order. It only precludes some selected bad cycles.

Now, for something completely different. When I talk with people about memory model, I am frequently surprised that many miss the beautiful symmetry between synchronized and volatile. Both induce synchronization actions. Unlock and volatile write are similar in their "release" action. Lock and volatile read are similar in their "acquire" action. This symmetry allows showing the examples on volatile-s, and almost immediately arrive at a similar synchronized one.

For example, memory effect-wise, these chunks of code are equivalent:

This symmetry allows constructing locks:

The second block is a plausible implementation of a synchronized section (all right, without wait/notify semantics): it wastes resources spinlooping on lock acquisition, but it is otherwise correct.

Let’s take the volatile increment atomicity example and slightly modify it:

Intuitively, by looking at non-looped example from Java Concurrency Stress Tests, you can imagine that a conflict that involves two threads may miss the update. The second intuitive stretch is that you can only lose updates, but you never step back. Notably, if you ask people what the possible outcomes for the test above are, most will answer "Somewhere between 10 and 20, inclusive".

But if you run the test, then:

What the Hell? Broken JVM! Broken hardware! Why don’t my unsynchronized counters work?

But, consider this timeline of events:

Here, first thread got stuck on the very first update, and after getting unstuck destroyed the result of all nine updates of second thread. But, it would then normally catch up, right? Not if the second thread reads "1" on its last iteration, and gets stuck too, in the end reciprocally destroying the first thread’s updates. This leaves us with "2" as the end result.

Of course, the probability of this interference gets lower as you require longer interference windows: this is why our empirical test results cut off at "6". If we acquire more samples, we will eventually see lower values too.

The most frequent and impactful misunderstanding of the model is really heart-breaking. Surprisingly, it comes even after studying the memory model in some detail. Consider this example again:

Way too many folks would nod through your JMM explanation, and then say this code is properly synchronized. Their reasoning goes like this: reference store is atomic, and therefore there is no need to care about anything else. What that reasoning misses is that the issue here is not about the access atomicity (e.g. whether you can see the non-complete version of the reference itself), but the ordering constraints. The actual failure comes from the fact that reading a reference to an object and reading the object’s fields are distinct under the memory model.

Therefore, you really need to ask yourself, given this test:

…​is the outcome 0 plausible? JMM says yes, because there are conformant executions that read a Box reference from RacyBoxy, and then read 0 from its field.

That said, running the example on x86 would almost always lead to this:

Hooray? Take that, Memory Model! But let’s run it on POWER:

Oops, there is our acceptable outcome. Note that it plays against the broken mental model that says "synchronized emits a memory barrier at the end, and thus non-synchronized reads are fine". Memory consistency requires cooperation from both parties.

The example above is fixable if we add some volatile-s. But the important thing is to know where to add them exactly. For instance, you may see the examples like this:

This, however, is incorrect: the model only guarantees happens-before between the actual volatile store and actual volatile load that observes that store. Making the container itself volatile would not help, because there is no volatile write to match the read to. So SynchronizedPublish_VolatileMeh fails in the same way SynchronizedPublish does. It will only help to put volatile over RacyBoxy.box field, so that a volatile store in RacyBoxy.set would match with a volatile load in RacyBoxy.get.

For the same reason, this example has surprising outcomes:

Even though the array itself is volatile, the reads and writes to the array elements do not have the volatile semantics. Therefore, the outcome 1, 0 is plausible.

It can be clearly demonstrated on POWER:

It is amazing to see how many folks glance over the synthetic examples, and do not map them to their day-to-day code. Take this example:

Here, the outcome 1, 0 can be observed empirically, which seems to look like a happens-before violation. What gives: didn’t we observe the volatile read g = 1, why don’t we observe x = 1? The answer is that the release order is wrong: we have to do "some-writes" → volatile write → volatile read → "some-reads", in order to guarantee that "some-reads" see the "some-writes". In this example, g = 1 and x = 1 come in the wrong order. The outcome in question can even be explained by a sequentially consistent execution!

Many would laugh this example away, and then proceed doing something like this:

Here, the volatile write of list is coming first, then the updates. If you think that guarantees that callers of getMyList see the entire list contents, rewind to a motivating example above, and think again!

This failure is easy to demonstrate on x86:

…​yields:

Oops.

The symmetric case is when you observe in a different order:

In this case, the outcome 0, 1 is completely plausible, and can also be explained by a sequentially consistent execution: r.r1 = x (reads 0), x = 1, g = 1, r.r2 = g (reads 1). Again, it is easy to laugh this example off, but then discover an actual bug hiding in a little more complicated production code. Be vigilant!

Combining two previous pitfalls into one major pitfall, by doing both acquire and release wrong:

…​yields an interesting case too. Here, the outcome (1, 0) can not be explained by any sequentially-consistent execution! But of course, it is a naked data race, and here is our "bad" result:

The most important thing that you would even learn from the Java Memory Model is the notion of safe publication. For volatiles, it goes like this:

Note the caveats: deviating just a little bit from them obliterates the guarantees, as examples in this section show.^{[7] [8]} This is the golden example:

…​and it indeed does not show the "bad" outcome on all platforms. This is POWER, weak hardware model as it is, there is no match for the language guarantees:

Using the symmetry with synchronized, we can construct similar cases with Java locks.

First, a little caveat about the phraseology. You can frequently see people handwave with "happens-before" like there is no tomorrow. Notably, faced with this code:

…​they say that g = 1 happens-before int lg = g. This train-wrecks the reasoning further by logically arriving at conclusion int lx = x would always see x = 1 (since x = 1 hb g = 1, and int lg = g hb int lx = x too). This is a very easy mistake to make, and you have to keep in mind that happens-before (and other orders in JMM formalism) is applied to actions, not the statements.

Having the little different designations for actions help to distinguish actions from statements. I like to use this nomenclature: write(x, V) writes value V to variable x; and read(x):V reads value V from variable x. In that nomenclature, you can say write(g, 1) happens-before read(g):1, because now you describe the actual action, not just some abstract program statement.

For completeness, these are the valid executions under JMM:

This execution has broken HB consistency, read(x) should be observing the latest write to x, but it does not: write(x, 1) →_hb write(g, 1) →_hb read(g):1 →_hb read(x):0

Note that a good API spec is careful to speak about actions, and their connection with the actual observable events. E.g. the java.util.concurrent package spec says:

Now, the notion of orders somehow wrecks people minds in assuming that "order" from the set theory used in JMM spec somehow relates to the physical execution order. Notably, people claim that if two actions are in program order, that’s the order they are executing in (which precludes any optimization!); or if they are tied in happens-before, then they also execute in that happens-before order (which precludes any optimization too, given HB is an extension of PO).

It goes into ridiculous examples, like this:

The actual test is more complicated due to the need to dodge compiler optimizations, but this example would also do. Just imagine that compiler does not coalesce the common reads of a.

Is the 1, 0 result plausible? E.g. if we read 1 already, can we read 0 next time? JMM says we can, because the execution producing this outcome does not violate the memory model requirements. Informally, we can say that a decision on what a particular read can observe is made for each read in isolation. Since both reads are racy, both may return either 0 or 1.

This can be demonstrated even on otherwise strong hardware, like x86:

This goes against intuition, and indeed, many would argue that you cannot see 1 and then see 0 in two back-to-back reads from the same location. That argument hinges on a definition of "then", and for most people it includes the intuitive/naive model of time, that gets contaminated with the program order. But in the Java Memory Model, "then" is defined by a partial happens-before order (for some paired write-read actions) and its consistency rules, and not by the program order itself. Therefore, it is useless to think about two independent reads to happen in any particular order here.^[9]

Next up, a more metaphysical question. Synchronization Order (SO) is specified to be a total order over actions. Getting back to the IRIW-like example:

We know that the (1, 0, 1, 0) outcome is precluded by SO rules. But if we take two "CPU demons" and let them observe the machine state of CPUs running readers, would it be possible for these CPU demons to have the inconsistent worldviews?

The answer is: yes, of course, we can see that both CPUs have mixed understanding which event took place first: x = 1 or y = 1. Therefore, even though specification requires that actions are in total order, the actual physical execution order may differ, depending on your observation point.^[10]

Having said that, the question we should be asking ourselves is not "What does the machine see?", but "What does the machine allow programs to see?". Some machines hide these details (and arguably pay with performance), some do not. In that case, runtime cooperation is required to avoid observing unwanted state. In the end, runtime would only allow to see the result that is consistent with some total order of events, even though it was physically chaos.

If you haven’t internalized that already, Java Memory Model only guarantees ordering across matching releases and acquires. This means that unobserved releases/acquires have no meaning under memory model, and are not required to produce memory effects. But quite often, you will see code like this:

We already know that barriers are implementation details, and may be omitted by the runtime. In fact, it is easy to demonstrate this with the following test:

Is the 1, 0 outcome plausible? Naively, with synchronized-as-barrier model it is forbidden. But it is easy for the runtime to exploit the simple fact that synchronizing on new Object() has no effect, and purge them out. The resulting optimized code would not have any barriers. And so even on x86 this would happen:

A similar example concerns volatile-s. It is tempting to read the JSR 133 Cookbook again, and imagine that since volatile implementations mean barriers, we can use volatiles to get barrier semantics! This should totally work, right?

If you run it on modern HotSpot, then you will see that -server (C2) compiler still leaves barriers behind. But that seems to be an implementation inefficiency: while it purges both Holder instances and volatile ops, it loses the association between the actual store and the relevant barrier shortly after parsing.

My duct-taped Graal runs show that Graal seems to eliminate both instances and associated barriers on x86: disassembly shows no barriers, and performance is 10x faster in actor methods — but, alas, we cannot run it on POWER yet. But we certainly would not like to throw compilers under the bus and say this is forbidden.

From the example above it can also be understood that releasing on one variable, and acquiring on another is not guaranteed to bring memory effects:

The outcome 1, 0 is allowed here. BARRIER is not really a barrier! Some VM implementations would still emit the same-looking barriers on both accesses, and thus accidentally provide the desired semantics, but this is not a language guarantee.

Let’s put a final nail into the volatile-as-barrier coffin. Imagine you have a class with a volatile field initialized in constructor. Suppose you publish the instance of this class via a race. Are you guaranteed to see the set value? E.g.:

…​is outcome 0 plausible here? "But volatile-s are so strong!" — one could say. "But barriers there are so strong!" — somebody else could say. "Who cares about barriers, when causality prevents this!" — others would say.

The fact of the matter is that JMM allows seeing 0 in this example! Only final would preclude 0, and we cannot have the field both final and volatile. This is one of the peculiar properties of the model, which can be solved by forcing all initializations perform as final ones, probably without a prohibitive performance cost.^[11][12]

Even when optimizers are not in the picture, the minute details in code generation may affect outcomes. The wishful thinking of many is that machines with Total Store Order (TSO) are saving us from bad things. This almost always hinges on the belief that if you cannot imagine why the compiler would mess up your code, then it wouldn’t. This gives rise to the urban legend that "safe initialization" is not required for x86, because it will preserve the order of field initializations and publication.

Let’s construct a simple case where an object with four fields is initialized and published via a race:

Even on x86 it will yield interesting behaviors, as if we don’t see all the stores from the constructor:

These kinds of failures are not theoretical! In practice, either safe publication or safe initialization (e.g. making all fields final) will prohibit these the intermediate outcomes. See more at "Safe Construction and Safe Initialization".

Another horrifying wishful thinking comes in a deceptively simple form: you may mistakenly believe it is easy to sanitize the racy result. Taking the example from this section, no matter what you do in consume(), it would not save you from the unfolding race. If your publisher does not cooperate with the consumer, all bets are off.

There are special forms of benign races (oxymoron, if you ask me). Their benignity comes from the safe initialization rules. They usually take this form:

This only works if class is safely initialized (i.e. has only final fields), and instance field is read only once. Both conditions are critical for the race to be benign in that example. If either condition is relaxed, then race is suddenly and abruptly stops being benign.

For example, relaxing the safe initialization rule opens up the failure described in Pitfall: Semi-Synchronized Is Fine:

Relaxing the single read rule also breaks benignity, by setting up the failure described in Wishful Thinking: Happens-Before Is The Actual Ordering:

This may appear counter-intuitive: if we read null from instance, we take a corrective action with storing new instance, and that’s it. Indeed, if we have the intervening store to instance, we cannot see the default value, and we can only see that store (since it happens-before us in all conforming executions where first read returned null), or the store from the other thread (which is not null, just a different object). But the interesting behavior unfolds when we don’t read null from the instance on the first read. No intervening store takes place. The second read tries to read again, and being racy as it is, may read null. Ouch.

This is actually exploitable by Evil Optimizers:

Introduce temporary variables (e.g. do SSA transform, and then some):

There are no ordering constraints on independent reads without intervening writes, so mess around with read ordering. First, observe that once control goes into if branch, we never reach T t2 = a, so the intervening write to a is invisible to T t2 = a, move the read before the branch. Second, shuffle around the independent reads T t1 and T t2 — can do that, independent reads:

This trivially gets you null at return t2.

In Java, every object is potentially a lock. This includes wrappers for primitives, which makes it possible to synchronize on primitives (their boxed wrappers, actually). Alas, as we have seen before, synchronizing on new Object() does not work, and we need to make sure that primitive values map to the same wrapper objects. Luckily, the Java specification gives another concession to us, and advertises that some small values are autoboxed to the same wrapper objects. These two (arguably overlooked) part of the specification give rise to this contraption:

It does indeed allows no more than $limit number of threads to execute in guardedExecute at any given time. It is even faster than java.util.concurrent.Semaphore, but it comes with some serious caveats:

Why have:

…​when you can have:

Of course, it comes with the caveat that the String instance you get from the String literal is shared within the execution. But, this is a blessing in disguise — it is shared between class loaders, too! Which means you can synchronize the code without figuring out how to pass static final-s between class loaders! Woo-hoo!

Also, nobody prevents us from carefully namespacing the locks:

…​which also lends itself for programmatic access:

What a magical language that gives me these powers!