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

[Paul McKenney]

>    From: "Paul McKenney" <[e-mail]>
>    Date: Mon, 8 Oct 2001 22:27:44 -0700
>
>    All other CPUs must observe the preceding stores before the following
>    stores.
>  ...
>    Does this do the trick?
>
>               membar #StoreStore
>
> Yes.

Cool!  Thank you!!!

>    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?

If "membar #StoreStore" is sufficient, then there is no equivalent of
it on Alpha.  Neither the "mb" nor the "wmb" instructions wait for
outstanding invalidations to complete, and therefore do -not- guarantee
that reading CPUs will see writes occuring in the order that the writes
occurred on the writing CPU, even if data dependencies force the order
of the reads (as the pointer-dereference example I gave does).

On Alpha, there -must- be an "mb" on the reading CPU if the reading CPU
is to observe the stores in order.  The IPIs are just a way of causing
those "mb"s to happen without having code like this:

     d = p->a->b;

from having to be written as follows:

     q = p->a;
     rmb();
     d = q->b;

More thoughts?

                         Thanx, Paul