What are valid reordering for Java synchronized?

Question

Many people asked similar questions like this, but none of their answers satisfied me. The only two reordering rules that I am very sure of are as follows:

1. Operations inside the synchronized block(or just call it critical section) are allowed to be reordered, as long as it confirms to the as-if-serial semantics.
2. Operations(including both reads and writes) are disallowed to be moved(reordered) out of the critical section.

However, for those operations that are before or after the synchronized block, can they be moved into the critical section? For this problem, I found some contrary. For example, the cookbook said that the compiler will insert some barriers after the MonitorEnter and before the MonitorExit:

MonitorEnter
 (any other needed instructions go here )
[LoadLoad] <===MB1:Inserted memory barrier
[LoadStore] <===MB2:Inserted memory barrier
(Begin of critical section)

....
(end of critical section)
[LoadStore] <===MB3:Inserted memory barrier
[StoreStore] <===MB4:Inserted memory barrier
 (any other needed instructions go here )
MonitorExit

According to be above placement made by the compiler and given below pseudo code:

  Load a;
  Load b;
  Store 1;
  Store 2;
  MonitorEnter
     (any other needed instructions go here )
    [LoadLoad] <===MB1
    [LoadStore] <===MB2
    (Begin of critical section)

    ....
    (end of critical section)
    [LoadStore]  <===MB3
    [StoreStore]  <===MB4
     (any other needed instructions go here )
    MonitorExit
  Store 3;
  Store 4;
  Load c;
  Load d;

According to the cookbook and reordering prevention rules enforced by such XY(X is Load or Store,Y is Load or Store) memory barriers, it seems to me that valid/invalid reordering are as below:

Understanding 1: Any stores(Store 3 and Store 4 here) after the MonitorExit can NOT be moved up before MB3 and MB4, because of the existence of a LoadStore(MB3) followed by a StoreStore(MB4). That's to say stores after the MonitorExit cannot be moved into critical section. However, it can be moved up after MB4,namely the bracket area.

Understanding 2:Any loads(Load a and Load b here) before the MonitorEnter can NOT be moved down after MB2 and MB1, because of the existence of a LoadLoad(MB1) followed by a LoadLoad(MB2).That's to say loads before the MonitorEnter cannot be moved into critical sention. However, it can be moved down after MB2,namely the bracket area.

Understanding 3:Any loads(Load c and Load d here) after the MonitorExit can be moved up before the MonitorExit, including the critical section and the bracket area, but it cannot exceed the MonitorEnter.

Understanding 4: Any stores(Store 1 and Store 2 here) before the MonitorEnter can be moved down after the MonitorEnter, including the critical section and the bracket area, but it cannot exceed the MonitorExit.

However, all the above understanding or claim see to be contrary to what Jeremy Manson said in his blog, where he claimed that give below code:

x = 1;//Store
synchronized(o) {
z = z + 1;
}
y = 1//Store

Reordering that produce below code is allowed:

synchronized(o){
y = 1;//I added this comment:Store moved inside the critical section
z = z + 1;
x = 1;//I added this comment:Store moved inside the critical section
}

According to Understanding 1, "y=1" cannot be moved up inside the critical section, So I just was confused, which one is correct and complete?

Answer 1

Reordering do not care about memory barriers. Even if the compiler always inserts the strongest memory barrier between any two instructions, these reordering are still permitted regardless.

Now, given a sequence of instructions, possibly after being reordered from the the original sequence, the compiler needs to insert proper memory barriers between some instructions.

For example, given an original sequence of instructions

volatile store x
normal   store y

It does not need memory barrier between the two instructions.

However, the compiler may choose to reorder it to

normal   store y
volatile store x

then a StoreStore barrier is needed between the two instructions. The CPU only has a "store" instruction, no concept of normal/volatile store. And the CPU may have out-of-order stores. It is the Java semantics that requires that another CPU must not observe the effect of store x before the effect of volatile store y; so a StoreStore is used to tell the CPU to store them in order.

(If the compiler is smart enough, it'll remember that the original program does not require the ordering of y->x, therefore this barrier is not actually needed. But let's say the compiler isn't that smart.)

---

Roach Motel model --

The point of JMM is to establish some (partial) orders among instructions on different threads, so that effects of reads/writes can be defined. In the following example,

thread 1             thread 2

  a1                   a2
  |
 }b1       ----->      b2{
                       |
  c1                   c2

a synchronization order b1->b2 is established, which could be volatile store -> volatile load, or monitor exit -> monitor enter. This connects a1->b1->b2->c2 in happens-before order.

Since we need to guarantee the ordering of a1->c2, a1 must not be reordered with b1, and c2 must not be reordered with b2; that is, a roach cannot "check out".

On the other hand, JMM wants to be as weak as possible; it says nothing about the effects between c1 and a2,b2,c2; therefore, c1 can be freely reordered with b1. Similarly, a2 can be reordered with b2. That is, a roach can "check in".