Re-ordering of assignments and adding a fence

Question

The following Java code looks a little strange because I have simplified it down to the bare essentials. I think the code has an ordering problem. I am looking at the first table in the JSR-133 Cookbook and it seems the normal store can be reordered with the volatile store in change().

Can the assignment to m_normal in change() move ahead of the assignment of m_volatile? In other words, can get() return null?

What is the best way to solve this?

private          Object m_normal   = new Object();
private volatile Object m_volatile;

public void change() {
    Object normal;

    normal = m_normal;      // Must capture value to avoid double-read

    if (normal == null) {
        return;
    }

    m_volatile = normal;
    m_normal   = null;
}

public Object get() {
    Object normal;

    normal = m_normal;      // Must capture value to avoid double-read

    if (normal != null) {
        return normal;
    }

    return m_volatile;
}

Note: I do not have control over the code where m_normal is declared.

Note: I am running on Java 8.

Grapevine

Answer 1

TL;DR: Friends do not let friends waste time with figuring out if racy accesses work up to Extreme Concurrency Optimist desires. Use volatile, and sleep happily.

I am looking at the first table in the JSR-133 Cookbook

Please note the full title is "JMM Cookbook For Compiler Writers". Which begs the question: are we compiler writers here, or just the users trying to figure out our code? I think the latter, so we should really close the JMM Cookbook, and open the JLS itself. See "Myth: JSR 133 Cookbook Is JMM Synopsis" and the section after that.

In other words, can get() return null?

Yes, trivially by get() observing the default values for the fields, without observing anything that change() did. :)

But I guess the question is, would it be allowed to see the old value in m_volatile after change() completed (Caveat: for some notion of "completed", because that implies time, and logical time is specified by JMM itself).

The question is basically, is there a valid execution that includes read(m_normal):null --po/hb--> read(m_volatile):null, with the read of m_normal observing the write of null to m_normal? Yes, here it is: write(m_volatile, X) --po/hb--> write(m_normal, null) ... read(m_normal):null --po/hb--> read(m_volatile):null.

The reads and writes to m_normal are not ordered, and so there is no structural constraints that prohibit the execution that reads both nulls. But "volatile", you would say! Yes, it comes with some constraints, but it is in wrong order w.r.t. the non-volatile operations, see "Pitfall: Acquiring and Releasing in Wrong Order" (look at that example closely, it is remarkably similar to what you are asking).

It is true that the operations on m_volatile itself are providing some memory semantics: the write to m_volatile is "release" that "publishes" everything happened before it, and the read from m_volatile is the "acquire" that "gets" everything published. If you do the derivation like in this post accurately, the pattern appears: you can trivially move the operations over the "release" program-upwards (those were racy anyway!), and you can trivially move the operations over the "acquire" program-downwards (those were racy anyway too!).

This interpretation is frequently called "roach motel semantics", and gives the intuitive answer to: "Can these two statements reorder?"

m_volatile = value; // release
m_normal   = null;  // some other store

The answer under roach motel semantics is "yes".

What is the best way to solve this?

The best way to solve is to avoid racy operations to begin with, and thus avoid the whole mess. Just make m_normal volatile, and you are all set: the operations over both m_normal and m_volatile would be sequentially consistent.

Would adding value = m_volatile; after m_volatile = value; prevent the assignment of m_normal happening before the assignment of m_volatile?

So the question is, would this help:

m_volatile = value; // "release"
value = m_volatile; // poison "acquire" read 
m_normal   = null;  // some other store

In naive world of only roach motel semantics, it could help: it would seem as if poison acquire breaks the code movement. But, since the value of that read is unobserved, it is equivalent to the execution without any poison read, and good optimizers would exploit that. See "Wishful Thinking: Unobserved Volatiles Have Memory Effects". It is important to understand that volatiles do not always mean barriers, even if the conservative implementation outlined in JMM Cookbook for Compiler Writers has them.

Aside: there is an alternative, VarHandle.fullFence() that can be used in the example like this, but it is restricted to very powerful users, because reasoning with barriers gets borderline insane. See "Myth: Barriers Are The Sane Mental Model" and "Myth: Reorderings And Commit to Memory".

Just make m_normal volatile, and everyone would sleep better.

Swizzle

I do not have control over the code where m_normal is declared. Also, I am running on Java 8. VarHandle is not available. Can you suggest some more solutions? – Grapevine

Would adding value.equals(null) or something like that after the poison acquire read be a solution? – Grapevine

That must mean that the alien code does the operations over m_normal, including racy publishing? If so, there is no reliable way to recover from this, as there is no way to launder the race that already happens. You can hope something breaks the code movement and is opaque to compiler and HW, but that is a bandaid. I would probably do the non-inlined method that can access both m_volatile and m_normal fields, and call it in-between stores to m_volatile and m_normal, and hope it provides enough dependencies. – Swizzle

@AlekseyShipilev I've read your blog posts, watched probably all of your videos I could find, seen you on conferences, and this intro is just here to show how scared I am to write this comment. :) Still there are mainly three things here 1) Can this m_volatile = normal; m_normal = null; be re-ordered, the plain answer is yes 2) would reading the volatile help? no, you have to observer the value that was written 3) would making it volatile help? yes, volatiles can not be re-ordered between them. Is my understanding correct? – Lead

My final solution was to discard m_normal and use m_volatile exclusively. This resolved the JIT reordering, of course. – Grapevine

@Eugene: 1) True; 2) Somewhat true, because we would have to analyze separately if this helps. My suspicion is that you would need to make the control dependency on that volatile read; 3) True. – Swizzle

Answer 2

// Must capture value to avoid double-read

Blasphemy. The compiler is free to do what it likes with normal accesses, repeating them when there is no Java code doing it, eliminating them when there is Java code doing it - whatever does not break the Java semantics.

Inserting a volatile read between these two:

m_volatile = normal;
tmp = m_volatile; // "poison read"
m_normal   = null;

is incorrect for a different reason than what Aleksey Shipilev stated in his answer: JMM has zero statements about modifying orders of operations like that; elimination of the unobserved "poison read" never modifies the ordering (never eliminates the barriers) of any operations. The actual problem with "poison read" is in the get().

Suppose, m_normal read in get() observes null. Which m_volatile write is m_volatile read in get() not allowed to not synchronize-with? The problem here is that it is allowed to appear in the total order of synchronization actions before m_volatile write in change() (gets reordered with m_normal read in get()), therefore observe the initial null in m_volatile, and not synchronize-with the write to m_volatile in change(). You would need a "full barrier" before the m_volatile read in get() - a volatile store. Which you don't want.

Also, using VarHandle.fullFence() in change() alone won't solve the problem for the same reason: the race in the get() is not eliminated by that.

---

PS. The explanation Aleksey gave on https://shipilev.net/blog/2016/close-encounters-of-jmm-kind/#wishful-unobserved-volatiles slide is not correct. There are no disappearing barriers there, only allowed partial orders where accesses to GREAT_BARRIER_REEF appear as the first and the last synchronization actions respectively.

---

You should start with the assumption that get() is allowed to return null. Then prove constructively that it is not allowed. Until you have such a proof, you should assume it may still happen.

Example where you can prove constructively that null is not allowed:

volatile boolean m_v;
volatile Object m_volatile;
Object m_normal = new Object();

public void change() {
  Object normal;

  normal = m_normal;

  if (normal == null) {
    return;
  }

  m_volatile = normal; // W2
  boolean v = m_v;     // R2
  m_normal   = null;
}

public Object get() {
  Object normal;

  normal = m_normal;

  if (normal != null) {
    return normal;
  }

  m_v = true;        // W1
  return m_volatile; // R1
}

Now, start with the assumption that get() may return null. For this to happen, get() must observe null in m_normal and m_volatile. It can observe null in m_volatile only when R1 appears before W2 in the total order of synchronization actions. But this means that R2 is necessarily after W1 in that order, therefore synchronizes-with it. This establishes a happens-before between m_normal read in get() and m_normal write in change(), so the m_normal read is not allowed to observe that write of null (cannot observe writes that happen after the read) - a contradiction. So the original assumption that both m_normal and m_volatile reads observe null is wrong: at least one of them will observe non-null value, and the method will return that.

If you don't have W1 in get(), there is nothing in change() that could force a happens-before edge between m_normal read and m_normal write - therefore, observing that write in get() does not contradict JMM.

Underthecounter