lkml.org 
[lkml]   [2006]   [Sep]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Uses for memory barriers
On Fri, Sep 08, 2006 at 11:55:46AM -0400, Alan Stern wrote:
> On Thu, 7 Sep 2006, Paul E. McKenney wrote:
>
> > On Thu, Sep 07, 2006 at 05:25:51PM -0400, Alan Stern wrote:
> > > Paul:
> > >
> > > Here's something I had been thinking about back in July but never got
> > > around to discussing: Under what circumstances would one ever want to use
> > > "mb()" rather than "rmb()" or "wmb()"?
> >
> > If there were reads needing to be separated from writes, for example
> > in spinlocks. The spinlock-acquisition primitive could not use either
> > wmb() or rmb(), since reads in the critical section must remain ordered
> > with respect to the write to the spinlock itself.
>
> Yes, okay, that's a general situation where mb() would be useful. But the
> actual application amounts to one of the two patterns below, as you will
> see...

Hey, you asked!!! ;-)

> Let's call the following pattern "write-mb-read", since that's what each
> CPU does (write a, mb, read b on CPU 0 and write b, mb, read a on CPU 1).
>
> > > The obvious extension of the canonical example is to have CPU 0 write
> > > one location and read another, while CPU 1 reads and writes the same
> > > locations. Example:
> > >
> > > CPU 0 CPU 1
> > > ----- -----
> > > while (y==0) relax(); y = -1;
> > > a = 1; b = 1;
> > > mb(); mb();
> > > y = b; x = a;
> > > while (y < 0) relax();
> > > assert(x==1 || y==1); //???
>
> > In the above code, there is nothing stopping CPU 1 from executing through
> > the "x=a" before CPU 0 starts, so that x==0.
>
> Agreed.
>
> > In addition, CPU 1 imposes
> > no ordering between the assignment to y and b,
>
> Agreed.
>
> > so there is nothing stopping
> > CPU 0 from seeing the new value of y, but failing to see the new value of
> > b,
>
> Disagree: CPU 0 executes mb() between reading y and b. You have assumed
> that CPU 1 executed its write to b and its mb() before CPU 0 got started,
> so why wouldn't CPU 0's mb() guarantee that it sees the new value of b?
> That's really the key point.

If we are talking about some specific CPUs, you might have a point.
But Linux must tolerate least-common-demoninator semantics...

And those least-common-denominator semantics are "if a CPU sees an
assignment from another CPU that followed a memory barrier on that
other CPU, then the first CPU is guaranteed to see any stores from
the other CPU -preceding- that memory barrier.

In your example, CPU 0 does not access x, so never sees any stores
from CPU 1 following the mb(), and thus is never guaranteed to see
the assignments preceding CPU 1's mb().

> To rephrase it in terms of partial orderings of events: CPU 1's mb()
> orders the commit for the write to b before the read from a. The fact
> that a was read as 0 means that the read occurred before CPU 0's write to
> a was committed. The mb() on CPU 0 orders the commit for the write to a
> before the read from b. By transitivity, the read from b must have
> occurred after the write to b was committed, so the value read must have
> been 1.

After CPU 1 sees the new value of y, then, yes, any operation ordered
after the read of y would see the new value of a. But (1) the "x=a"
precedes the check for y and (2) there is no mb() following the check of y
to force any ordering whatsoever.

Assume that initially, a==0 in a cache line owned by CPU 1. Assume that
b==0 and y==0 in separate cache lines owned by CPU 0.

CPU 0 CPU 1
----- -----
y = -1; [this goes out quickly.]
while (y==0) relax(); [picks up the value from CPU 1]
a = 1; [the cacheline is on CPU 1, so this one sits in
CPU 0's store queue. CPU 0 transmits an invalidation
request, which will take time to reach CPU 1.]
b = 1; [the cacheline is on CPU 0, so
this one sits in CPU 1's store
queue, and CPU 1 transmits an
invalidation request, which again
will take time to rech CPU 0.]
mb(); [CPU 0 waits for acknowledgement of reception of all previously
transmitted invalidation requests, and also processes any
invalidation requests that it has previously received (none!)
before processing any subsequent loads. Yes, CPU 1 already
sent the invalidation request for b, but there is no
guarantee that it has worked its way to CPU 0 yet!]
mb(); [Ditto.]

At this point, CPU 0 has received the invalidation request for b
from CPU 1, and CPU 1 has received the invalidation request for
a from CPU 0, but there is no guarantee that either of these
invalidation requests have been processed.

x = a; [Could therefore still be using
the old cached version of a, so
that x==0.]
y = b; [Could also be still using the old cached version of b,
so that y==0.]
while (y < 0) relax(); [This will spin until
the cache coherence protocol delivers
the new value y==0. At this point,
CPU 1 is guaranteed to see the new
value of a due to CPU 0's mb(), but
it is too late... And CPU 1 would
need a memory barrier following the
while loop in any case -- otherwise,
CPU 1 would be within its rights
on some CPUs to execute the code
out of order.]
assert(x==1 || y==1); //???
[This assertion can therefore fail.]

By the way, this sort of scenario is why maintainers have my full
sympathies when they automatically reject any patches containing explicit
memory barriers...

> > so that y==0 (assuming the initial value of b is zero).
> >
> > Something like the following might illustrate your point:
> >
> > CPU 0 CPU 1
> > ----- -----
> > b = 1;
> > wmb();
> > while (y==0) relax(); y = -1;
> > a = 1;
> > wmb();
> > y = b; while (y < 0) relax();
> > rmb();
> > x = a;
> > assert(x==1 || y==1); //???
> >
> > Except that the memory barriers have all turned into rmb()s or wmb()s...
>
> This seems like a non-sequitur. My point was about mb(); how could this
> example illustrate it? In particular, CPU 0's wmb() doesn't imply any
> ordering between its read of y and its read of b.

Excellent point, thus CPU 0's wmb() needs to instead be an mb().

> Furthermore, in this example the stronger assertion x==1 would always
> hold (it's a corollary of assert(y==-1 || x==1) combined with the
> knowledge that the while loop has terminated). Did you in fact intend CPU
> 0's wmb() to be rmb()?

I was just confused, confusion being a common symptom of working with
explicit memory barriers. :-/

If CPU 0 did mb(), then I believe assert(x==1&&y==1) would hold.

> Let's call the following pattern "read-mb-write".
>
> > > The opposite approach would use reads followed by writes:
> > >
> > > CPU 0 CPU 1
> > > ----- -----
> > > while (x==0) relax(); x = -1;
> > > x = a; y = b;
> > > mb(); mb();
> > > b = 1; a = 1;
> > > while (x < 0) relax();
> > > assert(x==0 || y==0); //???
> > >
> > > Similar reasoning can be applied here. However IIRC, you decided that
> > > neither of these assertions is actually guaranteed to hold. If that's the
> > > case, then it looks like mb() is useless for coordinating two CPUs.
> >
> > Yep, similar problems as with the earlier example.
> >
> > > Am I correct? Or are there some easily-explained situations where mb()
> > > really should be used for inter-CPU synchronization?
> >
> > Consider the following (lame) definitions for spinlock primitives,
> > but in an alternate universe where atomic_xchg() did not imply a
> > memory barrier, and on a weak-memory CPU:
> >
> > typedef spinlock_t atomic_t;
> >
> > void spin_lock(spinlock_t *l)
> > {
> > for (;;) {
> > if (atomic_xchg(l, 1) == 0) {
> > smp_mb();
> > return;
> > }
> > while (atomic_read(l) != 0) barrier();
> > }
> >
> > }
> >
> > void spin_unlock(spinlock_t *l)
> > {
> > smp_mb();
> > atomic_set(l, 0);
> > }
> >
> > The spin_lock() primitive needs smp_mb() to ensure that all loads and
> > stores in the following critical section happen only -after- the lock
> > is acquired. Similarly for the spin_unlock() primitive.
>
> Really? Let's take a closer look. Let b be a pointer to a spinlock_t and
> let a get accessed only within the critical sections:
>
> CPU 0 CPU 1
> ----- -----
> spin_lock(b);
> ...
> x = a;
> spin_unlock(b); spin_lock(b);
> a = 1;
> ...
> assert(x==0); //???
>
> Expanding out the code gives us a version of the read-mb-write pattern.

Eh? There is nothing guaranteeing that CPU 0 gets the lock before
CPU 1, so what is to assert?

> For the sake of argument, let's suppose that CPU 1's spin_lock succeeds
> immediately with no looping:
>
> CPU 0 CPU 1
> ----- -----
> ...
> x = a;
> // spin_unlock(b):
> mb();
> atomic_set(b,0); if (atomic_xchg(b,1) == 0) // Succeeds
> mb();
> a = 1;
> ...
> assert(x==0); //???
>
> As you can see, this fits the pattern exactly. CPU 0 does read a, mb,
> write b, and CPU 1 does read b, mb, write a.

Again, you don't have anything that guarantees that CPU 0 will get the
lock first, so the assertion is bogus. Also, the "if" shouldn't be
there -- since we are assuming CPU 1 got the lock immediately, it
would be unconditionally executing the mb(), right?

> We are supposing the read of b obtains the new value (no looping); can we
> then assert that the read of a obtained the old value? If we can -- and
> we had better if spinlocks are to work correctly -- then doesn't this mean
> that the read-mb-write pattern will always succeed?

Since CPU 1 saw CPU 0's assignment to b (which follows CPU 0's mb()),
and since CPU 1 immediately executed a memory barrier, CPU 1's critical
section is guaranteed to follow that of CPU 0. -Both- CPU 0's and CPU 1's
memory barriers are needed to make this work. This does not rely on
anything fancy, simply the standard pair-wise memory-barrier guarantee.

(Which is: if CPU 1 sees an assignment by CPU 0 following CPU 0 executing
a memory barrier, then any code on CPU 1 following a later CPU 1 memory
barrier is guaranteed to see the effects of all references by CPU 0
that preceded CPU 0's memory barrier.)

David Howells's Documentation/memory-barriers.txt goes through this
sort of thing, IIRC.

Thanx, Paul
-
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/

\
 
 \ /
  Last update: 2006-09-08 20:59    [W:0.062 / U:1.600 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site