Michael S (already5chosen@yahoo.com) on 3/20/08 wrote:
>
>I did read Intel memory ordering whitepaper before posting
>the original post. It clearly states that locked operations
>from different agents are ordered in absolute machine-wide
>order (i.e. seen in the same order by all observers) rather
>than in "processor order" like the rest of the WB stores.

Ahh, I think that is just a natural outcome of the all the
other rules - ie loads are not re-ordered wrt each other,
and stores also are guaranteed to be seen in the same order.

Couple that with the fact that locked instructions also
disable some of the reordering that is allowed (ie
the local store-to-load forwarding and loads passing
stores), and you end up with total ordering for the locked
ops.

>I'm too stupid to figure out whether semantics like these
>constrain possible implementations of big hierarchical
>directory based NUMA machines.

Hey, being too stupid to understand all the implications of
memory ordering means that pretty exactly 100% of humanity
is too stupid. Those things are really really subtle, but I
do think that the 2.7 rule is not actually fundamental, but
springs directly from the previous rules together with
the fact that atomic ops hold on to the cacheline.

And no, none of it needs non-local information. Basically,
here's the rule:

- in order for a CPU to do a locked op, it has to have
that cacheline exclusively and continuously for the read
and write (that "continuously" part is different: a
non-locked access can split the read and write and the
read could be satisfied earlier and then the cacheline
lost and regained).

- in order for another CPU to see the result, it obviously
will have to have that cacheline too.

- now, if you track the cacheline ownership for that 2.7
case, the disallowed case simply cannot happen.

Why? Because processors 2 and 3 can only reorder their
reads to _x and _y if they keep them in their cache across
the execution of both instructions (otherwise, the load
reordering would be architecturally visible, which is
against 2.1).

Think of _x and _y as being cachelines, and the locked
ops as being "guaranteed sequence point for that cacheline",
simply because it's owned exclusively by that CPU for
that one whole instruction.

So in order for the illegal case in 2.7 to happen (r3=1,
r4=0, r5=1, r6=0), we know that the movement for cacheline
_x must have been: P3x -> P0x -> P2x. And similarly for _y
it must have been P2y -> P1y ->P3y. Agreed?

That's all possible, because we're talking about two
different cachelines, and they can obviously move around
their ownership independently of each other.

But now, look at P2: because of the load order requirement,
we know that P2 must have held _x before it held _y,
because otherwise the load ordering (rule 2.1) is no longer
valid. So we know that P2x -> P2y. Similarly, for the same
reasons, we know that P3y -> P3x.

And this is where x86 is different from your regular weakly
ordered read-rule CPU. If you allow reads to be visibly
reordered wrt other reads, those P2x -> P2y and P3y -> P3x
guarantees do not exist, and the 2.7 guarantee doesn't hold.

But on x86 you do know that either P2 held both cachelines
over both instructions or it did the P2y fill later than P2x
(and the same for P3), because anything else would violate
the local load ordering constraints of 2.1 and the CPU could
be architecturally seen to re-order loads.

(Note the importance of "architecturally". P2 can
do load re-ordering internally, but only if it holds on to
the cachelines in question across the whole sequence, which
makes the reordering architecturally invisible since
clearly no other CPU could have modified those values
and shown an ordering violation!)

So now you have an impossible sequence. There's no way
we can satisfy all of

P3x -> P0x -> P2x (cacheline _x movement order)
P2x -> P2y (CPU2 cacheline load order)
P2y -> P1y -> P3y (cacheline _y movement order)
P3y -> P3x (CPU3 cacheline load order)

because that would be a circular dependency (P3x -> .. ->
P3x).

And notice how all these things are "local" decisions. All
of those ordering points are decisions about a single
cacheline state change at a single CPU, there's no "global
ordering" required for the above argument, every point is
just a local decision.

But yeah, memory ordering is really easy to get wrong, so
maybe I have a thinko there somewhere. But basically I
claim that it falls out of just the cache coherency rules
and the new stricter load ordering that Intel guarantees.

Linus