Messages in this thread | | | From | erich@uruk ... | Subject | Good SMP spinlock (was -> Re: RFC: Resource Management) | Date | 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
| |