Re: Shared memory not SMP safe to user-mode code.

Jamie Lokier (lkd@tantalophile.demon.co.uk)
Wed, 1 Dec 1999 21:59:10 +0100

Richard B. Johnson wrote:
> On Wed, 1 Dec 1999, Jamie Lokier wrote:
>
> > Richard B. Johnson wrote a spinlock:
> > > pars->spin += key;
> > > if(pars->spin != key)
> > > {
> > > pars->spin -= key;
> >
> > Wrong. This is not safe on UP /or/ SMP because "+=" and "-=" are not
> > atomic operations in C. `volatile' does not help either.
> >
> It is not necessary for the operations to be atomic! It is only essential
> that they can be undone. Both the child and the parent have private
> copies of their key value. The resulting arithmetic on the shared variable
> will be wrong if any of the read/modify/write operations are interrupted
> by another task, however, the resulting "mess" will be completely undone
> when both of the tasks subtract their key values (in any order).

Subtracting the private key values will not undo the mess. Back to the
diagram. += and -= are not atomic in C.

[ On SMP, even if the compiler happens to choose (unlocked)
read-modify-write instructions, the processor divides them into those
three phases using an internal register anyway. So reg below still
makes sense ].

So:

Process 0 Process 1
--------- ---------
reg = pars->spin
reg += KEY0
<task switch>
reg = pars->spin to
reg += KEY1
pars->spin = reg
<task switch>
pars->spin = reg

At this point, pars->spin == KEY0.

<task switch>
if (pars->spin != KEY1) {
pars->spin -= KEY1;

At this point, pars->spin == KEY0 - KEY1.

<task switch>
if (pars->spin != KEY0) {
pars->spin -= KEY0;

At this point, pars->spin == -KEY1 and both processes think they have
restored the spin state. Oh dear. No-one ever gets the lock after this
point.

> This is the important point of locking with a private key value,
> taught when I was a kid in CS-101.

Indeed, Ingo's lockless spinlock works using private keys way but not
using non-atomic += and -=.

> Now, another thing. If any task "thinks" only for an instant, that
> their copy of the key is exactly the same as the shared variable, then
> it is guaranteed that the other task will never, even for an instant
> "think" that the shared variable is the same. This is enforced by
> the CPU which guarantees that, regardless of what it "speculates",
> code will never be executed out-of-order.

This loses me. Can you rephrase?

> That said, the code executes perfectly, but only if you use the
> version that has the flush() macro. The flush() macro loads a segment
> register (cs) in the "far" return. This flushes the offending cache.

IMO, only by luck. far jumps are not defined to be serialising, and do not
flush anything except the prefetch queue (back when there was one). The
only reason it works here is because of timing.

-- Jamie

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/