Linux x86 spinlock实现之分析

1. TAS lock (test-and-set)
这是最简单的spinlock，CPU会在硬件上提供一些指令来帮助OS实现spinlock，
比如x86就有xchg, LOCK指令前缀等指令。。。
test_and_set()可以利用这些指令对某个memory地址，来原子地完成：
写入true到这个地址，同时返回这个地址储存的旧的值。

void spin_lock(lock)
{
    while (test_and_set(lock, true));
}

void spin_unlock(lock)
{
    atomic_set(lock, false);
}

在SMP(shared bus)的环境里，TAS lock的性能非常差。
首先test_and_set一般都需要serialization，即在执行这条指令前,
CPU必须要完成前面所有对memory的访问指令(read and write)。
这是非常heavy的操作，使得CPU无法对指令进行reorder，从而优化执行。

其次，因为每一次test_and_set都必须读-写lock这个变量。这就要涉及到
多个CPU之间cache coherence的问题。

当CPU1读lock的时候，如果这个lock没有在CPU1的cache中，就需要从memory中读入，
因为CPU又需要写这个变量，所以在把这个变量读入cache的时候，如果其他CPU已经
cache了这个变量，就需要invalidate它们。这样在CPU1把lock读入自己的cache中时，
这块cacheline所cache的lock就是CPU1所独占的，CPU1就可以更改它的值了。

如果多个CPU在竞争这个spinlock的话，每一次test_and_set都需要完成以上的操作，
在系统总线上会产生大量的traffic，开销是非常大的，而且unlock的CPU还必须同其它正在
竞争spinlock的CPU去竞争cacheline ownership. 随着CPU数目的增多，性能会成衰减的非常快。

2. TTAS (test-and-test-and-set)

void spin_lock(lock)
{
    while (test_and_set(lock, true))
        while (lock != false);
}

TTAS lock的改进是，当有CPU(CPU0)已经抓住了这把锁的话，CPU1就只会以只读的方式
cache这个lock。这样做的好处好处就是，CPU1在等待这把锁的时候，不会在总线上
产生traffic，和其它CPU一起竞争cacheline的ownership。

第一次的test_and_set还是和TAS lock一样，需要invalidate CPU0的cacheline,
这样的话CPU1独占的拥有了cache lock变量的cacheline。当它发现锁已经被别人锁住了，
CPU1就开始进入第二层循环。

如果CPU2这时也想抢这把锁，它执行test_and_set时，会invalidate CPU1的cacheline。
它也发现锁已经被锁住了，进入第二层循环。

这时CPU1想读lock这个变量的时候，会cache miss，会把read的请求发到系统总线上，
从memory中读入lock的值，同时CPU2的cache controller会发现总线上的这次交易，它
会把自己cache了lock的cacheline的状态转为shared。
这样CPU1和CPU2的cache里都cache了lock，第二层循环就都只在CPU内部执行，不会产生
总线交易。

当CPU0释放锁的时候，会invalidate CPU1和CPU2的cacheline，CPU1/CPU2会cache miss，
重新读入lock，发现锁已经被释放了，就会进行一个test_and_set()，谁先完成就抢到了
锁，另一个就必须重新循环等待锁的释放。

TTAS lock在自己的local cache copy上spinning被称为local spinning。是设计高效
的spinlock非常重要的一个原理。


3. TTAS with random backoff
TTAS lock有一个问题是在释放锁的时候，会产生大量的总线交易，因为所有在竞争的
CPU都会去作一个test_and_set().

在local spinning的时候，如果引入一定的延时(就像以太网的collision avoidance机制)，
这样就会有效的降低在锁释放时系统总线的竞争。

在2.6.25之前，Linux kernel x86的spinlock的实现就是这一类型的。

static inline void __raw_spin_lock(raw_spinlock_t *lock)
{
    asm volatile("\n1:\t"
             LOCK_PREFIX " ; 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"
             : "+m" (lock->slock) : : "memory");
}

首先是做一个test_and_set （LOCK; decb lock)，如果发现已经被锁住了，就
random backoff (rep; nop)，然后作local test (cmpb)。


static inline void __raw_spin_unlock(raw_spinlock_t *lock)
{
    asm volatile("movb $1,%0" : "+m" (lock->slock) :: "memory");
}


4. FIFO ticket spinlock (solved the fairness problem)
TTAS with random backoff还有一个公平性的问题，当锁释放时，谁能抢到锁是随机的。并不是等待
最久的那个竞争者会得到锁。这样就可能造成一个thread会busy looping很长的时间而得不到锁。

Linux kernel x86的ticket spinlock是有Nick Piggin实现的，在2.6.25中被接受。
(git commit id is: 314cdbefd1fd0a7acf3780e9628465b77ea6a836)

LWN上有一篇文章介绍了ticket spinlock的原理()。


一个spinlock被分成了两个部分，owner是现在拥有锁的lock owner的ticket id，Next是下一个能拿到锁的ticket id，初始化的时候Owner = Next = 0。当current lock owner释放锁的时候，会把Owner域加1，这样当拿着Next的锁竞争者发现Owner已经变成自己的ticket id的时候，就认为自己拿到了锁了。

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

1. 初始化 -> slock: owner = next = 0
2. CPU0第一个拿到了锁 -> slock: owner = 0, next = 1
3. 当CPU1也想竞争这把锁的时候，xaddw -> slock: owner = 0, next = 2 同时
   inc: owner = 0, next = 1
   它发现inc: owner != next (注意它是在测试inc这个变量），就等待(rep; nop)，然后把s
   lock的owner读入inc。如果CPU0释放了锁，它会把slock:owner加1。这样CPU1就会发现
   inc:next = 1,owner = 1，它就认为自己拿到了锁。
4. 如果在CPU0释放锁之前，CPU2也来竞争这把锁的话，CPU2: slock: owner = 0, next = 3
   inc: owner = 0, next = 2。当CPU0释放锁的时候，inc:owner = 1, next = 2，它仍然会
   继续循环，等待CPU1释放锁。

references:
1. For SMP cache coherence, please see chapter 4 of Computer Architecture-A
   Quantitative Approach.
2. Linux kernel source code.
3. For TAS, TTAS concept refer to chapter 7 of The Art of Multiprocessor 
   Programming.