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

From: Paul McKenney (
Date: Tue Oct 09 2001 - 10:24:17 EST

> From: "Paul McKenney" <>
> 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
> 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;
     d = q->b;

More thoughts?

                         Thanx, Paul

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

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