Linux内核学习系列---排队自旋锁

      传统的自旋锁实际上就是一个整数，值为1时表示没有被占用，值为0或负数时表示锁已经被占用，此时spin_lock循环等待，直到spin_unlock将自旋锁的值置为1，在这个过程中没有保存线程申请自旋锁的顺序信息，后进入等待的线程有可能先获得自旋锁。
      排队自旋锁(FIFO Ticket Spinlock)是 Linux 内核 2.6.25 版本引入的一种新型自旋锁，它通过保存执行线程申请锁的顺序信息解决了这种问题，让先申请自旋锁的线程先得到锁。
1. Ticket spinlock的实现原理
        排队自旋锁还是使用一个整形slock，并将其分为两个部分：
                    
        Next和Owner的长度与CPU的个数相关, 当CPU的个数 < 256时，Next和Owner为8位。当CPU的个数 > 256时，Next和Owner为16位。

#if (NR_CPUS < 256)

#define TICKET_SHIFT 8

...
#else
#define TICKET_SHIFT 16

        slock初始化时被置为0，Next和Owner都被置为0，当内核线程申请自旋锁时，比较原始的Next和Owner并将Next加1，如果原始的Next域和Owner域相等则表示锁处理未使用状态，否则改线程轮询等待直到Next域和Owner域相等。当释放锁时将Owner域加1.

2. Ticket spinlock的实现代码
下面查看__ticket_spin_lock和__ticket_spin_unlock两个函数(NR_CPUS < 256)：
加锁：

static __always_inline void __ticket_spin_lock(arch_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"
    /* don't need lfence here, because loads are in-order */
    "jmp 1b\n"
    "2:"
    : "+Q" (inc), "+m" (lock->slock)
    :
    : "memory", "cc");
}

a. xaddw %w0, %1： 将inc和lock->slock的低16位置交换，并将相加后的值存贷lock->slock中. 
        例：slock = 0x00 00 11 10，操作之后slock = 0x00 00 12 10, inc = 0x00 00 11 10.
b. cmpb %h0, %b0： 比较inc的低8位（Owner）和高8位（Next），相等则获得锁返回，不相等则继续执行；
c. 不断轮询lock->slock, 等待直到Next和Owner相等。

解锁

static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
{
  asm volatile(UNLOCK_LOCK_PREFIX "incb %0" // 将owner加1
         : "+m" (lock->slock)
         :
         : "memory", "cc");
}

a. 解锁只执行一个操作就是讲slock的Owner字段加1；

通过这种方式，线程调用__ticket_spin_lock的顺序存放在Next字段中，Next字段小的线程会先得到锁。