spin lock在kernel 2.4与2.6中的实现与改进

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);
}

实际代码(kernel 2.3)：

注意这里lock初始值为0 ，也就是当该值为0时为未锁，为1时为上锁 。 该定义在2.4之后被翻转。 

extern inline void spin_lock(spinlock_t *plock) 
{ 
1: 
lock ; btsl $0,plock;  （btsl 指令：根据位偏移0值从位串plock中取出一位放入CF中，然后将位串中的该位置成1）
jc 2f; 

注意，下一条指令的物理位置其实不是testb,而是跳出该函数。因为下面定义了一个 专门的区(.text.lock)来存放一段代码。它们和前边的”js 2f”并不在一个区（section）里,原因是在大多数情况下，spin lock是能获取成功的，从.section 到.previous的这一段代码并不经常被调用，如果把它跟别的常用指令混在一起，会浪费指令 缓存的空间。
.section .text.lock,”ax” 

2: 
testb $1,plock; 
rep;nop; 

注意这里rep其实不一定根据ecx寄存器的值来做循环，编译器其实会把rep；nor翻译成pause 指令，告诉处理器所执行的代码序列是一个 spin-wait loop。处理器会根据这个提示而避开内存序列冲突(memory order violation)，也就是说对 spin-wait loop 不做缓存，不做指令重新排序等动作。这样就可以大大的提高了处理器的性能。正是基于此，才建议在 spin-wait loops 中使用 paSUSE 指令。PAUSE指令的另外一个功能是让 Pentium4 处理器在执行 spin-wait loop 时可以减少电源的消耗。
在等待资源而执行自旋锁等待时，Pentium4 处理器以极快的速度执行自旋等待时，将会消耗很多电能，但使用 pause 指令则可以极大的减少处理器的电能消耗。

jne 2b; 
jmp 1b; 
.previous 
} 

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(“\n

1:\t”
LOCK_PREFIX ” ; decb %0\n\t”

decb将lock->lock减1，它前边的lock指令表示在执行decb的时候，要锁住 
内存总线（memory bus），另外的CPU不能访问内存，以保证decb指令的原子性。 
注意，decb并不是原子操作（atomic operation），它需要将变量从内存读出来， 
放入寄存器（register），减1，再写入内存。如果在这时候另外的CPU也进行同样的操作的 
时候，那么decb的执行结果就会不确定，也就是说，操作的原子性遭到了破坏。另外这里不必担心decb到底执行多少次（负多少），因为在unlock时 ，lock->lock 会直接被写值为1。

“jns 3f\n”

如果decb的结果小于0，表示无法取得spin lock，则执行下一条指令（rep）。
如果decb的结果大于或等于0，表示已经获得spin lock，则跳到标签为3的指令，实际就是跳出整段代码，函数返回。

“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”);

memory强制gcc编译器假设RAM所有内存单元均被汇编指令修改，这样cpu中的registers和cache中已缓存的内存单元中的数据将作废。cpu将不得不在需要的时候重新读取内存中的数据。这就阻止了cpu又将registers，cache中的数据用于去优化指令，而避免去访问内存。这种技术叫做内存屏障(memory barrier)
}

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

【注意这里rep其实不一定根据ecx寄存器的值来做循环，编译器其实会把rep；nor翻译成pause 指令，告诉处理器所执行的代码序列是一个 spin-wait loop。处理器会根据这个提示而避开内存序列冲突(memory order violation)，也就是说对 spin-wait loop 不做缓存，不做指令重新排序等动作。这样就可以大大的提高了处理器的性能。正是基于此，才建议在 spin-wait loops 中使用 pasuse 指令。PAUSE指令的另外一个功能是让 Pentium4 处理器在执行 spin-wait loop 时可以减少电源的消耗。
在等待资源而执行自旋锁等待时，Pentium4 处理器以极快的速度执行自旋等待时，将会消耗很多电能，但使用 pause 指令则可以极大的减少处理器的电能消耗。】

【

PAUSE指令虽然是在Intel P4处理器开始出现的，但是它可以向后与所有的IA32处理器兼容。在早期的IA32 CPU中，PAUSE就像NOP指令。Intel P4和Intel Xeon处理器将PAUSE实现成一个预定义的延迟(pre-defined delay)。这种延迟是有限的，而且一些处理器可以为0。PAUSE指令不改变处理器的架构状态（也就是说，它实际上只是执行了一个延迟——并不做任何其他事情——的操作）。

所以这里说的TTAS with random backoff中的延迟应该就是指这里的pause指令。pause指令的引入一方面使cpu内部的内存序列冲突减少（具体我也不清楚，可能是指令预取和乱序执行之类的），一方面减少电源消耗（省事了能不省电吗），一方面还做了预定义延迟。如果没有这个延迟，测试总共两条指令，多个cpu同时循环时一同发现解锁情况而竞争总线的概率很大，有了延迟，同时发现的概率大大减少，也许有的cpu根本无法发现中间锁的归属已经发生变化了。这大概就是文中所说的第三代使用硬件来减少竞争的spin_lock。至于为什么第二代的TTAS中也会出现pause指令，大概是笔误吧，只能如此理解了

】

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的原理(http://lwn.net/Articles/267968/)。

一个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 = 0×0100;

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.

关于intel cpu 中的总线lock ：

从 P6 处理器开始，如果指令访问的内存区域已经存在于处理器的内部缓存中，则“lock” 前缀并不将引线 LOCK 的电位拉低，而是锁住本处理器的内部缓存，然后依靠缓存一致性协议保证操作的原子性。

4.2) IA32 CPU调用有lock前缀的指令，或者如xchg这样的指令，会导致其它的CPU也触发一定的动作来同步自己的Cache。
CPU的#lock引脚链接到北桥芯片(North Bridge)的#lock引脚，当带lock前缀的执行执行时，北桥芯片会拉起#lock
电平，从而锁住总线，直到该指令执行完毕再放开。 而总线加锁会自动invalidate所有CPU对 _该指令涉及的内存_
的Cache，因此barrier就能保证所有CPU的Cache一致性。

4.3) 接着解释。
lock前缀(或cpuid、xchg等指令)使得本CPU的Cache写入了内存，该写入动作也会引起别的CPU invalidate其Cache。
IA32在每个CPU内部实现了Snoopying(BUS-Watching)技术，监视着总线上是否发生了写内存操作(由某个CPU或DMA控
制器发出的)，只要发生了，就invalidate相关的Cache line。 因此，只要lock前缀导致本CPU写内存，就必将导致
所有CPU去invalidate其相关的Cache line。