Re: RFC: patch to allow lock-free traversal of lists with insertion

From: Paul McKenney (Paul.McKenney@us.ibm.com)
Date: Tue Oct 09 2001 - 20:19:49 EST


> The IPIs and related junk are I believe needed only on Alpha, which
has
> no single memory-barrier instruction that can do wmbdd()'s job. Given
> that Alpha seems to be on its way out, this did not seem to me to be
> too horrible.
>
> I somehow doubt that you need an IPI to implement the equivalent of
> "membar #StoreStore" on Alpha. Richard?

I received my copy of the SPARC Architecture Manual (Weaver and Germond)
today.

It turns out that there is -no- equivalent of "membar #StoreStore"
on Alpha, if I am correctly interpreting this manual.

>From section D.4.4, on page 260:

     A memory order is legal in RMO if and only if:

     (1) X <d Y & L(X) -> X <m Y

     [... two other irrelevant cases omitted ...]

     Rule (1) states that the RMO model will maintain dependence
     when the preceding transaction is a load. Preceding stores
     may be delayed in the implementation, so their order may
     not be preserved globally.

In the example dereferencing a pointer, we first load the
pointer, then load the value it points to. The second load is
dependent on the first, and the first is a load. Thus, rule (1)
holds, and there is no need for a read-side memory barrier
between the two loads.

This is consistent with the book's definition of
"completion" and the description of the membar
instruction.

In contrast, on Alpha, unless there is an explicit rmb(), data
dependence between a pair of loads in no way forces the two loads
to be ordered. http://lse.sourceforge.net/locking/wmbdd.html
shows how Alpha can get the new value of the pointer, but the
old value of the data it points to. Alpha thus needs the rmb()
between the two loads, even though there is a data dependency.

Am I misinterpreting the SPARC manual?

                              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/



This archive was generated by hypermail 2b29 : Mon Oct 15 2001 - 21:00:28 EST