Re: [PATCH] Document Linux's memory barriers [try #6]

[Alan Stern <stern@rowland.harvard.edu>]

David:

I've got some comments inspired by the data-dependency sections of your
memory-barrier document.

Consider this part (under WHAT ARE MEMORY BARRIERS?):

+Memory barriers ...
...  request that the sequence of memory events generated appears to other
+parts of the system as if the barrier is effective on that CPU.

Also take this paragraph (under VARIETIES OF MEMORY BARRIER):

+     A write memory barrier gives a guarantee that all the STORE operations
+     specified before the barrier will appear to happen before all the STORE
+     operations specified after the barrier with respect to the other
+     components of the system.

Now compare those two to this part (under DATA DEPENDENCY BARRIERS):

+	CPU 1		CPU 2
+	===============	===============
+	{ A == 1, B == 2, C = 3, P == &A, Q == &C }
+	B = 4;
+	<write barrier>
+	P = &B
+			Q = P;
+			D = *Q;
+
+There's a clear data dependency here, and it would seem that by the end of the
+sequence, Q must be either &A or &B, and that:
+
+	(Q == &A) implies (D == 1)
+	(Q == &B) implies (D == 4)
+
+But! CPU 2's perception of P may be updated _before_ its perception of B, thus
+leading to the following situation:
+
+	(Q == &B) and (D == 2) ????

This contradicts the earlier text.  If the write barrier functions as
advertised, then it _must_ appear to CPU 2 that B was updated before P
was.  If not then the guarantee has been violated.

It may be that the earlier parts of the text are oversimplified.  For
instance, perhaps the write barrier on CPU 1 insures that the writes
are perceived in the correct order by CPU 2's cache (or caches) but
not necessarily by CPU 2 itself.  In other words, the ordering
perception guarantees made by memory barriers _don't_ apply with
respect to all the other components of the system, but only with
respect to some of them.

In fact, wouldn't it be better to say that the ordering provided by a
write barrier applies only to other CPUs that use an appropriate read
barrier?  Certainly it doesn't apply to the actual data on the bus,
and it's not clear whether it applies to other bus masters (devices).

Or to put it another way, the only guarantee made by memory barriers
is that when the following sequence occurs:

	CPU 1			CPU 2
	===============		===============
	store X			load Y
	<write barrier>		<read barrier>
	store Y			load X

then CPU 2 won't obtain the old value of X and the new value of Y.  Is
there really any more functionality to memory barriers than just this?

(Hmmm...  What about when this occurs:

	CPU 1			CPU 2
	===============		===============
	store A in X		store B in Y
	<write barrier>		<write barrier>
	store C in Y		store D in X

What can be said in this case?  Is there any guarantee that the final
values in memory won't end up being X == A and Y == B?)

You might also want to clarify the notion of a control dependency
versus a data dependency.  I gather that the basic idea goes something
like this: Some CPUs aren't good at tracking all possible
dependencies.  For instance, while they might realize that "mov X to
Y" means Y is dependent on X, they might not realize that "mov X to Y
if Z is 0" means Y is also dependent on Z.  It's best to assume that
anything other than a straight-line value-type dependency is too
subtle for all processors to recognize.

Alan Stern

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/