Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

From: Andrea Arcangeli (
Date: Wed Oct 10 2001 - 11:58:48 EST

On Wed, Oct 10, 2001 at 08:24:11AM -0700, Paul McKenney wrote:
> which states:
> For instance, your producer must issue a "memory barrier" instruction
> after writing the data to shared memory and before inserting it on
> the queue; likewise, your consumer must issue a memory barrier
> instruction after removing an item from the queue and before reading
> from its memory. Otherwise, you risk seeing stale data, since,
> while the Alpha processor does provide coherent memory, it does
> not provide implicit ordering of reads and writes. (That is, the
> write of the producer's data might reach memory after the write of
> the queue, such that the consumer might read the new item from the
> queue but get the previous values from the item's memory.
> Note that they require a memory barrier (rmb()) between the time the
> item is removed from the queue and the time that the data in the item
> is referenced, despite the fact that there is a data dependency between
> the dequeueing and the dereferencing. So, again, data dependency does
> -not- substitute for an MB on Alpha.

This is very explicit indeed.

In short I guess what happens is that the reader may have old data in
its cache, and the rmb() makes sure the cache used after the rmb() is
not older than the cache used before the rmb().

However the more I think about it the more I suspect we'd better use
rmb() in all readers in the common code, rather than defining rmbdd with
IPI on alpha, maybe alpha after all isn't the only one that needs the
rmb() but it's the only one defining the behaviour in detail? I can very
well imagine other archs also not invalidating all caches of all other
cpus after a write followed by wmb, the synchronization can be delayed
safely if the other cpus are readers, and they didn't issued an explicit
rmb. So what alpha is doing can really be seen as a "feature" that
allows to delay synchronization of caches after writes and wmb, unless
an explicit order is requested by the reader via rmb (or better mb on alpha).

The fact is that if there's old data in cache, a data dependency isn't
different than non data dependency if the cpu caches aren't synchronized
or invalidated during wmb run by the producer.

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:33 EST