Good SMP spinlock (was -> Re: RFC: Resource Management)

erich@uruk.org
Sun, 03 Mar 1996 21:56:52 -0800


I had promised to send this to Alan Cox, but others might be interested.

I've looked at a few spinlock papers (we have a spinlock expert on site
here :-), and the best one I've heard of (modulo slight modifications)
is what I'm including here. I'm grabbing the algorithm from a technical
report by John M. Mellor-Crummey and Michael L. Scott from the University
of Rochester dept. of Computer Science, report #342, April 1990. There is
a paper by our MP expert, Shreekant Ticky Thakkar, which is details
basically the same algorithm, but I don't remember the exact reference
offhand.

The basic idea is that you have a tail pointer to a linked list.
The list grows at the tail from new CPUs, and the head of CPUs at
the front of the FIFO know how to drain themselves out of it. Details
follow.

The properties this has are very good:

-- Guarantees FIFO ordering (guaranteed service).
-- Each CPU spins memory very local to it (presumably an Exclusive-ly
owned cache-line via the MESI cache protocol). This keeps main
memory bus traffic low.
-- Requires a small (1 pointer-sized word per CPU + 1 for a tail pointer),
constant amount of space per lock. Each pointer should really be
in a separate cache-line, or it might generate extra bus traffic
as the CPUs fight over ownership of the cache-lines when one of
them is released. In the algorithm given, the fact that the
local variables are on the stack is probably good enough.

The requirements are:

(1) Atomic swap operation.
(2) Atomic compare and swap operation (it can be done with only the
first, but you loose FIFO ordering, add complexity, and slow it
down... also, all the machines I care about right now have it).

The data-structure for the pointer (presumably aligned on the appropriate
size-boundary):

"spinlock_t":

All but LSB: top n-1 bits of the pointer (the pointer would be at least
32-bits in modern architectures, and aligned such
that the bottom few bits are zero anyway).
LSB: boolean flag, only used in the CPU-local lock variables.

----------------------(start FIFO spinlock for x86)--------------------------

/* if there's interest, I'll look up the first three things here and
repost them when I have the right code... but then again, most
might not care and simply recode this in assembly. Maybe I should
just say it's left as an exercise to the reader :-) */

/* vital to be aligned on 4-byte boundary !!! I forget the
GCC macro offhand... */
typedef volatile unsigned long spinlock_t;

/* puts "val" in location "dest" and returns original value in
one atomic operation */
#define XCHG(dest, val) .....

/* compares val2 with data in location "dest", if equal, performs
an exchange like in "XCHG", else returns the value "val", all
in one atomic operation */
#define CMPXCHG(dest, val, val2) .....

#define GET_SPIN_FLAG(x) (x & 1)
#define SET_SPIN_FLAG(x, y) (x = ((x & ~1) | (y & 1)))
#define GET_SPIN_PTR(x) ((spinlock_t *)(x & ~1))
#define SET_SPIN_PTR(x, y) (x = ((x & 1) | (y & ~1)))

void
spinlock_around_my_func(spinlock_t *my_lock, func *my_func)
{
spinlock_t my_local_lock = 1; /* initialize flag to TRUE */
unsigned long tmp_lock_val;

/*
* Enter spinlock.
*/

/*
* Swaps contents of global tail pointer "my_lock" with address of
* our local lock "my_local_lock".
*/
tmp_lock_val = XCHG(&my_lock, &my_local_lock);

/*
* If queue is non-empty, set up to wait. (The global pointer never
* used the LSB, so we can safely ignore it)
*/
if (tmp_lock_val) {
/*
* Set predecessor's next pointer to point to ours.
*/
SET_SPIN_PTR(*GET_SPIN_PTR(tmp_lock_val), &my_local_lock);

/*
* Spin until our already initialized flag changes goes to FALSE.
*/
while (GET_SPIN_FLAG(my_local_lock));
}

/*
* Spinlock is now ours!
*
* Call our function here.
*/

(*myfunc)();

/*
* Leave spinlock.
*/

/*
* If our successor is NULL, try to reset the tail pointer to NULL.
*/
if (GET_SPIN_PTR(my_local_lock) == NULL) {
/*
* If it's only us in the tail pointer, we're done.
*/
if (CMPXCHG(&my_lock, NULL, &my_local_lock))
return;

/*
* If not, spin until next CPU is ready to be unlocked
*/
while (GET_SPIN_PTR(my_local_lock) == NULL);
}

/*
* Release the next CPU.
*/
SET_SPIN_FLAG(*GET_SPIN_PTR(my_local_lock), FALSE);
}

----------------------(end FIFO spinlock for x86)--------------------------

--
Erich Stefan Boleyn                   \_ E-mail (preferred):  <erich@uruk.org>
Mad Genius wanna-be, CyberMuffin        \__     home #:  +1 (503) 226-0741
Home page:  http://www.uruk.org/~erich/    \_  USnail: 924 S.W. 16th Ave, #202
Motto: "I'll live forever or die trying"     \        Portland, OR, USA  97205