Avoid (one) spinlock deadlock [LWN.net]

Avoid (one) spinlock deadlock

Posted Dec 8, 2005 16:05 UTC (Thu) by gottlieb (subscriber, #2240)
Parent article: FOSS.IN: A report

Thanks for posting the slides, which I very much enjoyed. Yet another reason to be pleased with my membership. You give the following code for spinlocks

To lock a spinlock:
   Decrement it by one
   If resulting value is zero
      it's yours
   else
      increment value
      go try again (spin)

When many are contending for the lock, this code can livelock with the value always negative.

To avoid this livelock use a pretest

   while value of spinlock is negative
       go try again (i.e., this is empty while loop)
   Decrement it by one
   If resulting value is zero
      it's yours
   else
      increment value
      go try again (spin)

Both “go try again”s go to the beginning (the while)

To optimize for non-contending locks, start with the decrement part (i.e., imagine a jump to the decrement part at the begining; but when you try again you jump to the while)

allan gottlieb, new york university

(Log in to post comments)

Avoid (one) spinlock deadlock

Posted Dec 8, 2005 21:08 UTC (Thu) by mingo (subscriber, #31122) [Link]

Linux kernel spinlocks have a couple of other twists as well.
The relevant code from include/asm-i386/spinlock.h is:

#define __raw_spin_lock_string \
"\n1:\t" \
"lock ; decb %0\n\t" \
"jns 3f\n" \
"2:\t" \
"rep;nop\n\t" \
"cmpb $0,%0\n\t" \
"jle 2b\n\t" \
"jmp 1b\n" \
"3:\n\t"

or:

repeat:
decrease by 1
if we reached 0, we got the lock
else keep looping until value <= 0
if value is 1 again then repeat

first we decrement, then we test until the counter has been - if we didnt succeed we keep polling the value without decreasing the value. Note we do not inrease the value back, we just poll the value until the counter goes 1 again. The owner of the lock writes 1 to the lock indiscriminately, thus undoing multiple decrease-by-1 effects, and signalling all waiters to try again. Furthermore, the 'rep;nop' is a 'take it easy' instruction on newer CPUs (it's a NOP on older CPUs) - this saves power and reduces the likelyhood of livelocks too.

Avoid (one) spinlock deadlock

Posted Dec 8, 2005 23:45 UTC (Thu) by corbet (editor, #1) [Link]

Sometimes slides don't carry the entire substance of the talk. When I actually spoke, I noted that the pseudocode was a simplified version of what really goes on. The point was to make it clear what the "spin" in "spinlock" means, rather than get into the details of any architecture's implementation of them.