Re: sinval synchronization considered harmful

On Thu, Jul 21, 2011 at 02:31:15PM -0400, Robert Haas wrote:
> 1. Machines with strong memory ordering. On this category of machines
> (which include x86), the CPU basically does not perform loads or
> stores out of order. On some of these machines, it is apparently
> possible for there to be some ordering of stores relative to loads,
> but if the program stores two values or loads two values, those
> operations will performed in the same order they appear in the
> program.

This is all correct, but...

> The main thing you need to make your code work reliably on
> these machines is a primitive that keeps the compiler from reordering
> your code during optimization.

If you're suggesting that hardware memory barriers aren't going to be
needed to implement lock-free code on x86, that isn't true. Because a
read can be reordered with respect to a write to a different memory
location, you can still have problems. So you do still need memory
barriers, just fewer of them.

Dekker's algorithm is the classic example: two threads each set a flag
and then check whether the other thread's flag is set. In any
sequential execution, at least one should see the other's flag set, but
on the x86 that doesn't always happen. One thread's read might be
reordered before its write.

> 2. Machines with weak memory ordering. On this category of machines
> (which includes PowerPC, Dec Alpha, and maybe some others), the CPU
> reorders memory accesses arbitrarily unless you explicitly issue
> instructions that enforce synchronization. You still need to keep the
> compiler from moving things around, too. Alpha is particularly
> pernicious, because something like a->b can fetch the pointed-to value
> before loading the pointer itself. This is otherwise known as "we
> have basically no cache coherency circuits on this chip at all". On
> these machines, you need to issue an explicit memory barrier
> instruction at each sequence point, or just acquire and release a
> spinlock.

The Alpha is pretty much unique (thankfully!) in allowing dependent
reads to be reordered. That makes it even weaker than the typical
weak-ordering machine. Since reading a pointer and then dereferencing
it is a pretty reasonable thing to do regularly in RCU code, you
probably don't want to emit barriers in between on architectures where
it's not actually necessary. That argues for another operation that's
defined to be a barrier (mb) on the Alpha but a no-op elsewhere.
Certainly the Linux kernel found it useful to do so
(read_barrier_depends)

Alternatively, one might question how important it is to support the
Alpha these days...

Dan

--
Dan R. K. Ports MIT CSAIL http://drkp.net/