Re: [PATCH RFC tip/core/rcu 06/11] smp: Document transitivity for memory barriers.

["Paul E. McKenney" <paulmck@linux.vnet.ibm.com>]

On Wed, Feb 23, 2011 at 02:21:17PM +0800, Lai Jiangshan wrote:
> On 02/23/2011 11:29 AM, Steven Rostedt wrote:
> > On Tue, 2011-02-22 at 17:39 -0800, Paul E. McKenney wrote:
> >> Transitivity is guaranteed only for full memory barriers (smp_mb()).
> >>
> >> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> >> ---
> >>  Documentation/memory-barriers.txt |   58 +++++++++++++++++++++++++++++++++++++
> >>  1 files changed, 58 insertions(+), 0 deletions(-)
> >>
> >> diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
> >> index 631ad2f..f0d3a80 100644
> >> --- a/Documentation/memory-barriers.txt
> >> +++ b/Documentation/memory-barriers.txt
> >> @@ -21,6 +21,7 @@ Contents:
> >>       - SMP barrier pairing.
> >>       - Examples of memory barrier sequences.
> >>       - Read memory barriers vs load speculation.
> >> +     - Transitivity
> >>  
> >>   (*) Explicit kernel barriers.
> >>  
> >> @@ -959,6 +960,63 @@ the speculation will be cancelled and the value reloaded:
> >>  	retrieved                               :       :       +-------+
> >>  
> >>
> >> +TRANSITIVITY
> >> +------------
> >> +
> >> +Transitivity is a deeply intuitive notion about ordering that is not
> >> +always provided by real computer systems.  The following example
> >> +demonstrates transitivity (also called "cumulativity"):
> >> +
> >> +	CPU 1			CPU 2			CPU 3
> >> +	=======================	=======================	=======================
> >> +		{ X = 0, Y = 0 }
> >> +	STORE X=1		LOAD X			STORE Y=1
> >> +				<general barrier>	<general barrier>
> >> +				LOAD Y			LOAD X
> >> +
> >> +Suppose that CPU 2's load from X returns 1 and its load from Y returns 0.
> >> +This indicates that CPU 2's load from X in some sense follows CPU 1's
> >> +store to X and that CPU 2's load from Y in some sense preceded CPU 3's
> >> +store to Y.  The question is then "Can CPU 3's load from X return 0?"
> >> +
> >> +Because CPU 2's load from X in some sense came after CPU 1's store, it
> >> +is natural to expect that CPU 3's load from X must therefore return 1.
> >> +This expectation is an example of transitivity: if a load executing on
> >> +CPU A follows a load from the same variable executing on CPU B, then
> >> +CPU A's load must either return the same value that CPU B's load did,
> >> +or must return some later value.
> >> +
> >> +In the Linux kernel, use of general memory barriers guarantees
> >> +transitivity.  Therefore, in the above example, if CPU 2's load from X
> >> +returns 1 and its load from Y returns 0, then CPU 3's load from X must
> >> +also return 1.
> >> +
> >> +However, transitivity is -not- guaranteed for read or write barriers.
> >> +For example, suppose that CPU 2's general barrier in the above example
> >> +is changed to a read barrier as shown below:
> >> +
> >> +	CPU 1			CPU 2			CPU 3
> >> +	=======================	=======================	=======================
> >> +		{ X = 0, Y = 0 }
> >> +	STORE X=1		LOAD X			STORE Y=1
> >> +				<read barrier>		<general barrier>
> >> +				LOAD Y			LOAD X
> >> +
> >> +This substitution destroys transitivity: in this example, it is perfectly
> >> +legal for CPU 2's load from X to return 1, its load from Y to return 0,
> >> +and CPU 3's load from X to return 0.
> >> +
> >> +The key point is that although CPU 2's read barrier orders its pair
> >> +of loads, it does not guarantee to order CPU 1's store.  Therefore, if
> >> +this example runs on a system where CPUs 1 and 2 share a store buffer
> >> +or a level of cache, CPU 2 might have early access to CPU 1's writes.
> >> +General barriers are therefore required to ensure that all CPUs agree
> >> +on the combined order of CPU 1's and CPU 2's accesses.
> > 
> > Sounds like someone had a fun time debugging their code.
> > 
> >> +
> >> +To reiterate, if your code requires transitivity, use general barriers
> >> +throughout.
> > 
> > I expect that your code is the only code in the kernel that actually
> > requires transitivity ;-)
> 
> Maybe, but my RCURING also requires transitivity, I had asked Paul for advice
> one years ago when I was writing the patch. Good document for it!

Glad you like it!

By the way, what finally got me to get my act together and document
this was a group of patches that implicitly assumed that smp_rmb()
and smp_wmb() provide transitivity...

So, no, it is not just Lai and myself.  ;-)

							Thanx, Paul