Re: [PATCH] Document Linux's memory barriers

David Howells
2006-03-09T13:02:22Z

Alan Cox <alan@lxorguk.ukuu.org.uk> wrote:

> > Alan Cox <alan@lxorguk.ukuu.org.uk> wrote:
> > So, you're saying that the LOCK and UNLOCK primitives don't actually modify
> > memory, but rather simply pin the cacheline into the CPU's cache and refuse to
> > let anyone else touch it?
>
> Basically yes

What you said is incomplete: the cacheline is wangled into the Exclusive
state, and there it sits until modified (at which point it shifts to the
Modified state) or stolen (when it shifts to the Shared state). Whilst the x86
CPU might pin it there for the duration of the execution of the locked
instruction, it can't leave it there until it detects a spin_unlock() or
equivalent.

I guess LL/SC and LWARX/STWCX work by the reserved load wangling the cacheline
into the Exclusive state, and then the conditional store only doing the store
if the cacheline is still in that state. I don't know whether the conditional
store may modify a cacheline that's in the Modified state, but I'd guess you'd
need more state than that, because you have to pair it with a load reserved.

With inter-CPU memory barriers I think you have to consider the cache part of
the memory, not part of the CPU. The CPU _does_ make a memory modification;
it's just that it doesn't proceed any further than the cache, until the cache
coherency mechanisms transfer the change to another CPU, or until the cache
becomes full and the lock's line gets ejected.

> > No... it can't work like that. It *must* make a memory modification
>
> Then you'll have to argue with the chip designers because it doesn't.
>
> Its all built around the cache coherency. To make a write to a cache
> line I must be the sole owner of the line. Look up "MESI cache" in a
> good book on the subject.

http://en.wikipedia.org/wiki/MESI_protocol

And a picture of the state machine may be found here:

https://www.cs.tcd.ie/Jeremy.Jones/vivio/caches/MESIHelp.htm

David