Is the Happens-Before mechanism only hb(w, r)?

Question

I'm trying to understand the Happens Before mechanism and i can't find any source in the internet talking about happens-before relationship between a READ and subsequent WRITE. I can only read about the opposite: hb(w,r).

Anyhow reading the JLS i found that:

We say that a read r of a variable v is allowed to observe a write w to v if, in the happens-before partial order of the execution trace:

r is not ordered before w (i.e., it is not the case that hb(r, w))

It also says:

A set of actions A is happens-before consistent if for all reads r in A, where W(r) is the write action seen by r, it is not the case that either hb(r, W(r))

I don't understand this hb(r,w) relationship, what is that and how does it work? What is trying to say the JLS?

Thanks!

Answer 1

hb(r, w) describes the opposite of hb(w, r). Let's start with the easier to follow hb(w, r) that you already seem to understand. Let me write it in my own words, so that when I explain hb(r, w), you can see where it's almost exactly the same explanation:

• We have some java statement (actually, bytecode, the JMM is part of the JVMS and hence about bytecode, but, let's for argument's sake blur the lines between statements and bytecode for now). We shall call this statement 'BAR'.
• We have a second statement elsewhere, we call it 'FOO'. For one of the reasons explicitly enumerated in the JMM, for example, BAR is the first line in the run() method of a thread, and FOO is t.start(), FOO/BAR have a happens-before relationship in the JMM sense.

This means that it must never be the case that BAR gets to observe any state as it was before FOO modified it. In other words, if some field x is 5, and FOO is x=10;, then if BAR observes x being 5, then that JVM is broken.

The texts tend to talk about 'observability' because that's more accurate than the far more obvious but subtly wrong: "If hb(FOO, BAR), then BAR is guaranteed to run after FOO" - because if BAR doesn't observe anything FOO does, then the JVM can completely ignore the hb relationship there and reorder at will. This seems irrelevant (if it is not possible to observe which way a thing was ordered, then who cares?), but it is relevant: "observe" is also a very specific term and it doesn't mean what the english dicionary says it means. For example, "observing" that things are happening by way of how long the CPU needs to process it is in the human/dictionary definition certainly "observing", but not in the JMM's definition of "observing".

For example, I don't think System.currentTimeMillis() is specced to be an HB/HA point (I think on most impls it ends up being one - it's a lot slower than you think, but that's an implementation detail), so if FOO and BAR both log their acts, in theory one can notice that BAR occurs before FOO even though hb(FOO, BAR) - as long as BAR doesn't 'observe' any fields that FOO modified, that's allowed. You'll have a hard time finding a code+JVMimpl+OS+architecture combo to actually see that happening, but you managed to find such a combo, nothing is broken - bugs you file with that as example would be closed as 'working as intended'. The JVM reserves the right to do that; it's on you to write code that is aware it can happen; if you don't - your code is broken. Probably in a way that will never actually result in a problem on your current JVM stack, but broken nonetheless.

One could argue that it is possible to witness that BAR occurred before FOO via those timestamps, i.e. that it can be 'observed', but that's not the meaning of the word "observe" that the JVM implies in this section.

And now to flip it around

What hb(r, w) is about is the reverse. Given that the JVM is allowed to reorder FOO and BAR even if hb(FOO, BAR) is established, because the only actual guarantee the JVM makes is that BAR cannot observe state as it was before FOO modified any of it (i.e. BAR cannot read anything that predates FOO's writes), we get into this funky scenario:

Well, then, if we flip it around and it is in fact FOO (the 'before' bytecode) that writes x = 10; and it's the BAR (the 'after') code that attempts to observe (read) x, given that the JVM explicitly does not define happens-before as actually requiring that FOO runs physically before BAR, is reordering then allowed and thus a JVM may wel lreorder things so that BAR gets to observe the state of x as it is after FOO writes to it, i.e., if BAR reads the value of x as 10, then that's fine, the JVM isn't broken?

That section about hb(r, w) says: No. Given that x is 5 originally and some statement modifies it to 10, the JMM makes BOTH guarantees:

• If x = 10; is JMM-defined as 'happening before' a read x, the read code cannot observe the 5.
• If x = 10; is JMM-defined as 'happening after' a read x, the read code cannot observe the 10.
• If x = 10; is JMM-defined as having no HB/HA relationship to code that reads x, then the read code can observe either 5 or 10 - a JVM is allowed to do either one, depending on whatever it wants including the phase of the moon. There is no guarantee of consistency either. It is allowed to flip a coin every run if the JVM wants to. However, a JVM is not allowed to let the read code observe anything else. pre- state is fine, post-state is fine, but nothing else¹.

---

[1] As per the spec this guarantee does not exist for long/double (you can see 'sheared' updates - the top 32 bits having been set to the new value with the bottom 32 bits still on the old, or vice versa, as per the JVM spec). However, and this is a personal injection: As far as I know, no 64-bit JVM implementation exists where you would be able to observe sheared long/double updates. 32-bit hardware still exists of course. Raspberry π's are a thing, for one.

Answer 2

I'm trying to understand the Happens Before mechanism and i can't find any source in the internet talking about happens-before relationship between a READ and subsequent WRITE. I can only read about the opposite: hb(w,r).

The JLS has this text:

Two actions can be ordered by a happens-before relationship. If one action happens-before another, then the first is visible to and ordered before the second.

If we have two actions x and y, we write hb(x, y) to indicate that x happens-before y.

• If x and y are actions of the same thread and x comes before y in program order, then hb(x, y).
• There is a happens-before edge from the end of a constructor of an object to the start of a finalizer (§12.6) for that object.
• If an action x synchronizes-with a following action y, then we also have hb(x, y).
• If hb(x, y) and hb(y, z), then hb(x, z).

So, for example, if in the same thread READ is followed by WRITE, then hb(READ, WRITE).

---

I don't understand this hb(r,w) relationship, what is that and how does it work? What is trying to say the JLS?

In short: JMM is rules for multi-threading programs for what a read can return.

In single-threaded code a read always returns the value written by the latest write to that variable.
In multi-threaded code things get hairy: JMM allows a read to return any value written to that variable by any write from other threads. More than that, JMM allows a read to return a value written by a write from another thread, even if that write happens later in real time than the read.
Happens-before limits the writes that a read can return: for every HB chain only that last write can be returned.

Why JMM is so relaxed:

1. it reflects the behavior of current CPUs: ARM and Power are themselves pretty relaxed
2. it allows for the compiler optimizations (compilers for single threaded programs often achieve high performance by various instruction reordering)

If the JMM were strict (e.g. like SC), then there would a huge performance loss: both in multi-threaded and single-threaded code (because many compiler optimizations for single-threaded coded would be illegal).