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

[Paul McKenney]

>    I am particularly interested in comments from people who understand
>    the detailed operation of the SPARC membar instruction and the PARISC
>    SYNC instruction.  My belief is that the membar("#SYNC") and SYNC
>    instructions are sufficient,
>
> SYNC is sufficient but way too strict.  You don't explicitly say what
> you need to happen.  If you need all previous stores to finish
> before all subsequent memory operations then:
>
>          membar #StoreStore | #StoreLoad
>
> is sufficient.  If you need all previous memory operations to finish
> before all subsequent stores then:
>
>          membar #StoreStore | #LoadStore
>
> is what you want.

I need to segregate the stores executed by the CPU doing the membar.
All other CPUs must observe the preceding stores before the following
stores.  Of course, this means that the loads on the observing CPUs
must be ordered somehow.  I need data dependencies between the loads
to be sufficient to order the loads.

For example, if a CPU executes the following:

     a = new_value;
     wmbdd();
     p = &a;

then i need any other CPU executing:

     d = *p;

to see either the value that "p" pointed to before the "p = &a" assignment,
or "new_value", -never- the old value of "a".

Does this do the trick?

           membar #StoreStore

>    Thoughts?
>
> I think if you need to perform IPIs and junk like that to make the
> memory barrier happen correctly, just throw your code away and use a
> spinlock instead.

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.

                                   Thanx, Paul