Semaphore Part 1 (__ticket_spin_lock explained)

We know from the previous article that semaphore uses the spin_lock_irq, which in turn, calls _raw_spin_lock, then calls, __ticket_spin_lock:

static __always_inline void __ticket_spin_lock(raw_spinlock_t *lock)
{
short inc = 0x0100;

asm volatile (
LOCK_PREFIX "xaddw %w0, %1\n"
"1:\t"
"cmpb %h0, %b0\n\t"
"je 2f\n\t"
"rep ; nop\n\t"
"movb %1, %b0\n\t"
"jmp 1b\n"
"2:"
: "+Q" (inc), "+m" (lock->slock)
:
: "memory", "cc");
}

This can be defined in C code as:

void __ticket_spin_lock_C(raw_lock_t * lock)
{

short inc = *(short *)&lock->slock;

//
// xaddw
//
lock->slock += 0x0100;

while ( *(char *)&inc != *( (char *)&inc + 1) ) )
*(char *)&inc = *(char *)&lock->slock;

}

Before, knowing what we're doing here, we must also look at __ticket_spin_unlock:

static __always_inline void __ticket_spin_unlock(raw_spinlock_t *lock)
{
asm volatile(UNLOCK_LOCK_PREFIX "incw %0"
: "+m" (lock->slock)
:
: "memory", "cc");
}

This can be implemented in C as:

void __ticket_spin_unlock_C(raw_spinlock_t * lock)
{
++lock->slock; /* must-be-atomic action */
}

Therefore, while the low byte is not equal to the high byte in the summation of increment and slock, keep looping and update the low byte of slock and comparing it with the high byte of inc. Once they are equal, then we have attained the lock.

The only way this will happen is when __ticket_spin_unlock gets called. It increments the slock, and returns. Basically, the ordering is preserved through this process, inc will denote the current thread. So, when slock is incremented, it will be the first thread that has access to the lock. Therefore, no starvation will occur, and this is truly first-come-first-serve.