On Wed, 9 Dec 2009, Alan Stern wrote: > > That could be attributed to reordering on CPU2, so let's take CPU2's > peculiarities out of the picture (initially everything is set to 0): > > CPU1 CPU2 > ---- ---- > if (x == 1) z = y; > y = 5; mb(); > x = 1; > > This gets at the heart of the question: Can a write move up past a > control dependency? > [ .. ] > Can z end up equal to 5 in any of these examples? In any _practical_ microarchitecture I know of, the above will never result in 'z' being 5, even though CPU1 doesn't really have a memory barrier. But if I read the alpha memory ordering guarantees rigth, then at least in theory you really can end up with z=5. Let me write that as five events (with the things in brackets being what the alpha memory ordering manual calls them): - A is "read of x returns 1" on CPU1 [ P1:R(x,1) ] - B is "write of value 5 to y" on CPU1 [ P1:W(y,5) ] - C is "read of y returns 5" on CPU2 [ P2:R(y,5) ] - D is "write of value 1 to x" on CPU2 [ P2:W(x,1) ] - 'MB' is the mb() on CPU2 [ P2:MB ] (The write of 'z' is irrelevant, we can think of it as a register, the end result is the same). And yes, if I read the alpha memory ordering rules correctly, you really can end up with z=5, although I don't think you will ever find an alpha _implementation_ that does it. Why? The alpha memory ordering literally defines ordering in two ways: - "location access order". But that is _only_ defined per actual location, so while 'x' can have a location access order specified by seeing certain values, there is no "location access order" for two different memory locations (x and y). The alpha architecture manual uses "A << B" to say "event A" is before "event B" when there is a defined ordering. So in the example above, there is a location access ordering between P2:W(x,1) << P1:R(x, 1) and P2:R(y,5) << P1:W(y,5) ie you have D << A and B << C. Good so far, but that doesn't define anything else: there's only ordering between the pairs (D,A) and (B,C), nothing between them. - "Processor issue order" for two instruction is _only_ defined by either (a) memory barriers or (b) accesses to the _same_ locations. The alpha architecture manual uses "A < B" to say that "event A" is before "event B" in processor issue order. So there is a "Processor issue order" on CPU2 due to the memory barrier: P2:R(y,5) < P2:MB < P2:W(x,1), or put another way C < MB < D: C < D. Now, the question is, can we actually get the behaviour of reading 5 on CPU2 (ie P2:R(y,5)), and that is only possible if we can find an ordering that satisfies all the constraints. We have D << A B << C C < D and it seems to be that it is a possible situation: "B C D A" really does satisfy all the constraints afaik. So yes, according to the actual alpha architecture memory ordering rules, you can see '5' from that first read of 'y'. DESPITE having a mb() on CPU2. In order to not see 5, you need to also specify "A < B", and the _only_ way to do that processor issue order specification is with a memory barrier (or if the locations are the same, which they aren't). "Causality" simply is nowhere in the officially defined alpha memory ordering. The fact that we test 'x == 1' and conditionally do the write simply doesn't enter the picture. I suspect you'd have a really hard time not having causality in practice, but there _are_ things that can break causality (value prediction etc), so it's not like you'd have to actually violate physics of reality to do it. IOW, you could at least in theory implement a CPU that does every instruction speculatively in parallel, and then validates the end result afterwards according to the architecture rules. And that CPU would require the memory barrier on alpha. (On x86, 'causality' is defined to be part of the memory ordering rules, so on x86, you _do_ have a 'A < B' relationship. But not on alpha). Linus -- To unsubscribe from this list: send the line "unsubscribe linux-acpi" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
