linux内核--自旋锁的理解

自旋锁：如果内核配置为SMP系统，自旋锁就按SMP系统上的要求来实现真正的自旋等待，但是对于UP系统，自旋锁仅做抢占和中断操作，没有实现真正的“自旋”。如果配置了CONFIG_DEBUG_SPINLOCK，那么自旋锁按照SMP系统来编译。

但是为什么在UP系统中不需要真正的“带有自旋的”自旋锁呢？其实在理解了自旋锁的概念和由来，这个问题就迎刃而解了。所以我重新查找了关于自旋锁的资料，认真研究了自旋锁的实现和相关内容。

一、自旋锁spinlock的由来

众所周知，自旋锁最初就是为了SMP系统设计的，实现在多处理器情况下保护临界区。所以在SMP系统中，自旋锁的实现是完整的本来面目。但是对于UP系统，自旋锁可以说是SMP版本的阉割版。因为只有在SMP系统中的自旋锁才需要真正“自旋”。

二、自旋锁的目的

自旋锁的实现是为了保护一段短小的临界区操作代码，保证这个临界区的操作是原子的，从而避免并发的竞争冒险。在Linux内核中，自旋锁通常用于包含内核数据结构的操作，你可以看到在许多内核数据结构中都嵌入有spinlock，这些大部分就是用于保证它自身被操作的原子性，在操作这样的结构体时都经历这样的过程：上锁-操作-解锁。

如果内核控制路径发现自旋锁“开着”（可以获取），就获取锁并继续自己的执行。相反，如果内核控制路径发现锁由运行在另一个CPU上的内核控制路径“锁着”，就在原地“旋转”，反复执行一条紧凑的循环检测指令，直到锁被释放。自旋锁是循环检测“忙等”，即等待时内核无事可做（除了浪费时间），进程在CPU上保持运行，所以它保护的临界区必须小，且操作过程必须短。不过，自旋锁通常非常方便，因为很多内核资源只锁1毫秒的时间片段，所以等待自旋锁的释放不会消耗太多CPU的时间。

三、自旋锁需要做的工作

从保证临界区访问原子性的目的来考虑，自旋锁应该阻止在代码运行过程中出现的任何并发干扰。这些“干扰”包括：

1、中断，包括硬件中断和软件中断（仅在中断代码可能访问临界区时需要）

这种干扰存在于任何系统中，一个中断的到来导致了中断例程的执行，如果在中断例程中访问了临界区，原子性就被打破了。所以如果在某种中断例程中存在访问某个临界区的代码，那么就必须用spinlock保护。对于不同的中断类型（硬件中断和软件中断）对应于不同版本的自旋锁实现，其中包含了中断禁用和开启的代码。但是如果你保证没有中断代码会访问临界区，那么使用不带中断禁用的自旋锁API即可。

2、内核抢占（仅存在于可抢占内核中）

在2.6以后的内核中，支持内核抢占，并且是可配置的。这使UP系统和SMP类似，会出现内核态下的并发。这种情况下进入临界区就需要避免因抢占造成的并发，所以解决的方法就是在加锁时禁用抢占（preempt_disable(); ），在开锁时开启抢占（preempt_enable();注意此时会执行一次抢占调度）。

3、其他处理器对同一临界区的访问（仅SMP系统）

在SMP系统中，多个物理处理器同时工作，导致可能有多个进程物理上的并发。这样就需要在内存加一个标志，每个需要进入临界区的代码都必须检查这个标志，看是否有进程已经在这个临界区中。这种情况下检查标志的代码也必须保证原子和快速，这就要求必须精细地实现，正常情况下每个构架都有自己的汇编实现方案，保证检查的原子性。

有些人会以为自旋锁的自旋检测可以用for实现，这种想法“Too young, too simple, sometimes naive”！你可以在理论上用C去解释，但是如果用for，起码会有如下两个问题：

（1）你如何保证在SMP下其他处理器不会同时访问同一个的标志呢？（也就是标志的独占访问）

（2）必须保证每个处理器都不会去读取高速缓存而是真正的内存中的标志（可以实现，编程上可以用volitale）

要根本解决这个问题，需要在芯片底层实现物理上的内存地址独占访问，并且在实现上使用特殊的汇编指令访问。请看参考资料中对于自旋锁的实现分析。以arm为例，从存在SMP的ARM构架指令集开始（V6、V7），采用LDREX和STREX指令实现真正的自旋等待。

四、自旋锁操作组成

根据上的介绍，我们很容易知道自旋锁的组成：

中断控制是按代码访问临界区的不同而在编程时选用不同的变体，有些API中有，有些没有。

而抢占控制和自旋锁标志控制依据内核配置（是否支持内核抢占）和硬件平台（是否为SMP）的不同而在编译时确定。如果不需要，相应的控制代码就编译为空函数。对于非抢占式内核，由自旋锁所保护的每个临界区都有禁止内核抢占的API，但是为空操作。由于UP系统不存在物理上的并行，所以可以阉割掉自旋的部分，剩下抢占和中断操作部分即可。

到这里其实就可以解释为什么我开始的实验现象和预想的完全不同了：
由于UP系统（在不配置CONFIG_DEBUG_SPINLOCK的情况下），根本就没有自旋锁控制的部分，多次获得自旋锁是可能的（这种编程本来就是错误的，只是我想看错误的现象而已）。

对于其中的一点疑惑：
1、在有禁用中断的版本中，既然已经禁用了中断，在本处理器上就不会被打断，禁用抢占是否多余？
（1）禁用了中断可以避免因为中断引起的抢占调度，但是如果在自旋锁保护的临界区中存在 preempt_disable();和 preempt_enable();对。这样在preempt_enable();就会引发抢占调度。
（2）避免SMP系统中别的处理器执行调度程序使得本处理器的进程会被调度出去。？？？？？
对于这个问题我不是很确定，还有深入研究调度系统后才会有准确的答案。

五、自旋锁变体的使用规则

不论是抢占式UP、非抢占式UP还是SMP系统，只要在某类中断代码可能访问临界区，就需要控制中断，保证操作的原子性。所以这个和模块代码中临界区的访问还有关系，是否可能在中断中操作临界区，只有程序员才知道。所以自旋锁API中有针对不同中断类型的自旋锁变体：

不会在任何中断例程中操作临界区：
static inline void spin_lock(spinlock_t*lock)
static inline void spin_unlock(spinlock_t*lock)
如果在软件中断中操作临界区：
static inline void spin_lock_bh(spinlock_t*lock)
static inline void spin_unlock_bh(spinlock_t*lock)
bh代表bottom half，也就是中断中的底半部，因内核中断的底半部一般通过软件中断（tasklet等）来处理而得名。
如果在硬件中断中操作临界区：
static inline void spin_lock_irq(spinlock_t*lock)
static inline void spin_unlock_irq(spinlock_t*lock)
如果在控制硬件中断的时候需要同时保存中断状态：
spin_lock_irqsave(lock, flags)
static inline void spin_unlock_irqrestore(spinlock_t*lock, unsigned long flags)

这些情况描诉似乎有点简单，我在网上找到了一篇使用规则（（转）自旋锁（spinlock ）解释得经典，透彻），非常详细。我稍作修改，转载如下：

　 获得自旋锁和释放自旋锁有好几个版本，因此让读者知道在什么样的情况下使用什么版本的获得和释放锁的宏是非常必要的。
　　如果被保护的共享资源只在进程上下文访问和软中断（包括tasklet、timer）上下文访问，那么当在进程上下文访问共享资源时，可能被软中断打断，从而可能进入软中断上下文来对被保护的共享资源访问，因此对于这种情况，对共享资源的访问必须使用spin_lock_bh和spin_unlock_bh来保护。当然使用spin_lock_irq和spin_unlock_irq以及spin_lock_irqsave和spin_unlock_irqrestore也可以，它们失效了本地硬中断，失效硬中断隐式地也失效了软中断。但是使用spin_lock_bh和spin_unlock_bh是最恰当的，它比其他两个快。

　　如果被保护的共享资源只在两个或多个tasklet或timer上下文访问，那么对共享资源的访问仅需要用spin_lock和spin_unlock来保护，不必使用_bh版本，因为当tasklet或timer运行时，不可能有其他tasklet或timer在当前CPU上运行。
    如果被保护的共享资源只在一个tasklet或timer上下文访问，那么不需要任何自旋锁保护，因为同一个tasklet或timer只能在一个CPU上运行，即使是在SMP环境下也是如此。实际上tasklet在调用tasklet_schedule标记其需要被调度时已经把该tasklet绑定到当前CPU，因此同一个tasklet决不可能同时在其他CPU上运行。timer也是在其被使用add_timer添加到timer队列中时已经被帮定到当前CPU，所以同一个timer绝不可能运行在其他CPU上。当然同一个tasklet有两个实例同时运行在同一个CPU就更不可能了。
    如果被保护的共享资源只在一个软中断（tasklet和timer除外）上下文访问，那么这个共享资源需要用spin_lock和spin_unlock来保护，因为同样的软中断可以同时在不同的CPU上运行。
    如果被保护的共享资源在两个或多个软中断上下文访问，那么这个共享资源当然更需要用spin_lock和spin_unlock来保护，不同的软中断能够同时在不同的CPU上运行。

如果被保护的共享资源在软中断（包括tasklet和timer）或进程上下文和硬中断上下文访问，那么在软中断或进程上下文访问期间，可能被硬中断打断，从而进入硬中断上下文对共享资源进行访问，因此，在进程或软中断上下文需要使用spin_lock_irq和spin_unlock_irq来保护对共享资源的访问。

而在中断处理句柄中使用什么版本，需依情况而定，如果只有一个中断处理句柄访问该共享资源，那么在中断处理句柄中仅需要spin_lock和spin_unlock来保护对共享资源的访问就可以了。因为在执行中断处理句柄期间，不可能被同一CPU上的软中断或进程打断。
    但是如果有不同的中断处理句柄访问该共享资源，那么需要在中断处理句柄中使用spin_lock_irq和spin_unlock_irq来保护对共享资源的访问。

在使用spin_lock_irq和spin_unlock_irq的情况下，完全可以用spin_lock_irqsave和spin_unlock_irqrestore取代，那具体应该使用哪一个也需要依情况而定，如果可以确信在对共享资源访问前中断是使能的，那么使用spin_lock_irq更好一些。因为它比spin_lock_irqsave要快一些，但是如果你不能确定是否中断使能，那么使用spin_lock_irqsave和spin_unlock_irqrestore更好，因为它将恢复访问共享资源前的中断标志而不是直接使能中断。
　　当然，有些情况下需要在访问共享资源时必须中断失效，而访问完后必须中断使能，这样的情形使用spin_lock_irq和spin_unlock_irq最好。
    spin_lock用于阻止在不同CPU上的执行单元对共享资源的同时访问以及不同进程上下文互相抢占导致的对共享资源的非同步访问，而中断失效和软中断失效却是为了阻止在同一CPU上软中断或中断对共享资源的非同步访问。
    以上是我对自旋锁的理解和使用上的总结，对与自旋锁的实现，其实网上已经有之类文章了，我不废话。由于自旋锁涉及到内核抢占，所有最好还是学习以下抢占的相关知识。参考资料如下：

分析Linux中Spinlock在ARM及X86平台上的实现

ARM的SWP和LDREX
STREX指令

4.2.12. LDREX 和 STREX

spinlock与linux内核调度的关系

深入理解linux内核自旋锁

最近在内核频繁使用了自旋锁，自旋锁如果使用不当，极易引起死锁，在此总结一下。

自旋锁是一个互斥设备，它只有两个值：“锁定”和“解锁”。它通常实现为某个整数值中的某个位。希望获得某个特定锁得代码测试相关的位。如果锁可用，则“锁定”被设置，而代码继续进入临界区；相反，如果锁被其他人获得，则代码进入忙循环（而不是休眠，这也是自旋锁和一般锁的区别）并重复检查这个锁，直到该锁可用为止，这就是自旋的过程。“测试并设置位”的操作必须是原子的，这样，即使多个线程在给定时间自旋，也只有一个线程可获得该锁。

自旋锁最初是为了在多处理器系统（SMP）使用而设计的，但是只要考虑到并发问题，单处理器在运行可抢占内核时其行为就类似于SMP。因此，自旋锁对于SMP和单处理器可抢占内核都适用。可以想象，当一个处理器处于自旋状态时，它做不了任何有用的工作，因此自旋锁对于单处理器不可抢占内核没有意义，实际上，非抢占式的单处理器系统上自旋锁被实现为空操作，不做任何事情。

自旋锁有几个重要的特性：1、被自旋锁保护的临界区代码执行时不能进入休眠。2、被自旋锁保护的临界区代码执行时是不能被被其他中断中断。3、被自旋锁保护的临界区代码执行时，内核不能被抢占。从这几个特性可以归纳出一个共性：被自旋锁保护的临界区代码执行时，它不能因为任何原因放弃处理器。

考虑上面第一种情况，想象你的内核代码请求到一个自旋锁并且在它的临界区里做它的事情，在中间某处，你的代码失去了处理器。或许它已调用了一个函数（copy_from_user，假设）使进程进入睡眠。也或许，内核抢占发威，一个更高优先级的进程将你的代码推到了一边。此时，正好某个别的线程想获取同一个锁，如果这个线程运行在和你的内核代码不同的处理器上（幸运的情况），那么它可能要自旋等待一段时间（可能很长），当你的代码从休眠中唤醒或者重新得到处理器并释放锁，它就能得到锁。而最坏的情况是，那个想获取锁得线程刚好和你的代码运行在同一个处理器上，这时它将一直持有CPU进行自旋操作，而你的代码是永远不可能有任何机会来获得CPU释放这个锁了，这就是悲催的死锁。

考虑上面第二种情况，和上面第一种情况类似。假设我们的驱动程序正在运行，并且已经获取了一个自旋锁，这个锁控制着对设备的访问。在拥有这个锁得时候，设备产生了一个中断，它导致中断处理例程被调用，而中断处理例程在访问设备之前，也要获得这个锁。当中断处理例程和我们的驱动程序代码在同一个处理器上运行时，由于中断处理例程持有CPU不断自旋，我们的代码将得不到机会释放锁，这也将导致死锁。

因此，如果我们有一个自旋锁，它可以被运行在（硬件或软件）中断上下文中的代码获得，则必须使用某个禁用中断的spin_lock形式的锁来禁用本地中断（注意，只是禁用本地CPU的中断，不能禁用别的处理器的中断），使用其他的锁定函数迟早会导致系统死锁（导致死锁的时间可能不定，但是发生上述死锁情况的概率肯定是有的，看处理器怎么调度了）。如果我们不会在硬中断处理例程中访问自旋锁，但可能在软中断（例如，以tasklet的形式运行的代码）中访问，则应该使用spin_lock_bh，以便在安全避免死锁的同时还能服务硬件中断。

补充：

锁定一个自旋锁的函数有四个：

void spin_lock(spinlock_t *lock);

最基本得自旋锁函数，它不失效本地中断。

void spin_lock_irqsave(spinlock_t *lock, unsigned long flags);

在获得自旋锁之前禁用硬中断（只在本地处理器上），而先前的中断状态保存在flags中

void spin_lockirq(spinlock_t *lock);

在获得自旋锁之前禁用硬中断（只在本地处理器上），不保存中断状态

void spin_lock_bh(spinlock_t *lock);

在获得锁前禁用软中断，保持硬中断打开状态

Linux内核的同步机制(1)自旋锁（spinlock）

自旋锁与互斥锁有点类似，只是自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁，"自旋"一词就是因此而得名。

　　由于自旋锁使用者一般保持锁时间非常短，因此选择自旋而不是睡眠是非常必要的，自旋锁的效率远高于互斥锁。

　　信号量和读写信号量适合于保持时间较长的情况，它们会导致调用者睡眠，因此只能在进程上下文使用（_trylock的变种能够在中断上下文使用），而自旋锁适合于保持时间非常短的情况，它可以在任何上下文使用。

　　如果被保护的共享资源只在进程上下文访问，使用信号量保护该共享资源非常合适，如果对共巷资源的访问时间非常短，自旋锁也可以。但是如果被保护的共享资源需要在中断上下文访问（包括底半部即中断处理句柄和顶半部即软中断），就必须使用自旋锁。

　　自旋锁保持期间是抢占失效的，而信号量和读写信号量保持期间是可以被抢占的。自旋锁只有在内核可抢占或SMP的情况下才真正需要，在单CPU且不可抢占的内核下，自旋锁的所有操作都是空操作。

　　跟互斥锁一样，一个执行单元要想访问被自旋锁保护的共享资源，必须先得到锁，在访问完共享资源后，必须释放锁。如果在获取自旋锁时，没有任何执行单元保持该锁，那么将立即得到锁；如果在获取自旋锁时锁已经有保持者，那么获取锁操作将自旋在那里，直到该自旋锁的保持者释放了锁。

　　无论是互斥锁，还是自旋锁，在任何时刻，最多只能有一个保持者，也就说，在任何时刻最多只能有一个执行单元获得锁。

自旋锁的API有：

spin_lock_init(x)
该宏用于初始化自旋锁x。自旋锁在真正使用前必须先初始化。该宏用于动态初始化。

DEFINE_SPINLOCK(x)
该宏声明一个自旋锁x并初始化它。该宏在2.6.11中第一次被定义，在先前的内核中并没有该宏。

SPIN_LOCK_UNLOCKED
该宏用于静态初始化一个自旋锁。

DEFINE_SPINLOCK(x)等同于spinlock_t x = SPIN_LOCK_UNLOCKED

spin_is_locked(x)
该宏用于判断自旋锁x是否已经被某执行单元保持（即被锁），如果是，返回真，否则返回假。

spin_unlock_wait(x)
该宏用于等待自旋锁x变得没有被任何执行单元保持，如果没有任何执行单元保持该自旋锁，该宏立即返回，否则将循环在那里，直到该自旋锁被保持者释放。

spin_trylock(lock)
该宏尽力获得自旋锁lock，如果能立即获得锁，它获得锁并返回真，否则不能立即获得锁，立即返回假。它不会自旋等待lock被释放。

spin_lock(lock)
该宏用于获得自旋锁lock，如果能够立即获得锁，它就马上返回，否则，它将自旋在那里，直到该自旋锁的保持者释放，这时，它获得锁并返回。总之，只有它获得锁才返回。

spin_lock_irqsave(lock, flags)
该宏获得自旋锁的同时把标志寄存器的值保存到变量flags中并失效本地中断。

spin_lock_irq(lock)
该宏类似于spin_lock_irqsave，只是该宏不保存标志寄存器的值。

spin_lock_bh(lock)
该宏在得到自旋锁的同时失效本地软中断。

spin_unlock(lock)
该宏释放自旋锁lock，它与spin_trylock或spin_lock配对使用。如果spin_trylock返回假，表明没有获得自旋锁，因此不必使用spin_unlock释放。

spin_unlock_irqrestore(lock, flags)
该宏释放自旋锁lock的同时，也恢复标志寄存器的值为变量flags保存的值。它与spin_lock_irqsave配对使用。

spin_unlock_irq(lock)
该宏释放自旋锁lock的同时，也使能本地中断。它与spin_lock_irq配对应用。

spin_unlock_bh(lock)
该宏释放自旋锁lock的同时，也使能本地的软中断。它与spin_lock_bh配对使用。

spin_trylock_irqsave(lock, flags)
该宏如果获得自旋锁lock，它也将保存标志寄存器的值到变量flags中，并且失效本地中断，如果没有获得锁，它什么也不做。
　　因此如果能够立即获得锁，它等同于spin_lock_irqsave，如果不能获得锁，它等同于spin_trylock。如果该宏获得自旋锁lock，那需要使用spin_unlock_irqrestore来释放。

spin_trylock_irq(lock)
该宏类似于spin_trylock_irqsave，只是该宏不保存标志寄存器。如果该宏获得自旋锁lock，需要使用spin_unlock_irq来释放。

spin_trylock_bh(lock)
该宏如果获得了自旋锁，它也将失效本地软中断。如果得不到锁，它什么也不做。因此，如果得到了锁，它等同于spin_lock_bh，如果得不到锁，它等同于spin_trylock。如果该宏得到了自旋锁，需要使用spin_unlock_bh来释放。

spin_can_lock(lock)
该宏用于判断自旋锁lock是否能够被锁，它实际是spin_is_locked取反。如果lock没有被锁，它返回真，否则，返回假。该宏在2.6.11中第一次被定义，在先前的内核中并没有该宏。

　　获得自旋锁和释放自旋锁有好几个版本，因此让读者知道在什么样的情况下使用什么版本的获得和释放锁的宏是非常必要的。

　　如果被保护的共享资源只在进程上下文访问和软中断上下文访问，那么当在进程上下文访问共享资源时，可能被软中断打断，从而可能进入软中断上下文来对被保护的共享资源访问，因此对于这种情况，对共享资源的访问必须使用spin_lock_bh和spin_unlock_bh来保护。

　　当然使用spin_lock_irq和spin_unlock_irq以及spin_lock_irqsave和spin_unlock_irqrestore也可以，它们失效了本地硬中断，失效硬中断隐式地也失效了软中断。但是使用spin_lock_bh和spin_unlock_bh是最恰当的，它比其他两个快。

　　如果被保护的共享资源只在进程上下文和tasklet或timer上下文访问，那么应该使用与上面情况相同的获得和释放锁的宏，因为tasklet和timer是用软中断实现的。

　　如果被保护的共享资源只在一个tasklet或timer上下文访问，那么不需要任何自旋锁保护，因为同一个tasklet或timer只能在一个CPU上运行，即使是在SMP环境下也是如此。实际上tasklet在调用tasklet_schedule标记其需要被调度时已经把该tasklet绑定到当前CPU，因此同一个tasklet决不可能同时在其他CPU上运行。

　　timer也是在其被使用add_timer添加到timer队列中时已经被帮定到当前CPU，所以同一个timer绝不可能运行在其他CPU上。当然同一个tasklet有两个实例同时运行在同一个CPU就更不可能了。

　　如果被保护的共享资源只在两个或多个tasklet或timer上下文访问，那么对共享资源的访问仅需要用spin_lock和spin_unlock来保护，不必使用_bh版本，因为当tasklet或timer运行时，不可能有其他tasklet或timer在当前CPU上运行。

　　如果被保护的共享资源只在一个软中断（tasklet和timer除外）上下文访问，那么这个共享资源需要用spin_lock和spin_unlock来保护，因为同样的软中断可以同时在不同的CPU上运行。

　　如果被保护的共享资源在两个或多个软中断上下文访问，那么这个共享资源当然更需要用spin_lock和spin_unlock来保护，不同的软中断能够同时在不同的CPU上运行。

　　如果被保护的共享资源在软中断（包括tasklet和timer）或进程上下文和硬中断上下文访问，那么在软中断或进程上下文访问期间，可能被硬中断打断，从而进入硬中断上下文对共享资源进行访问，因此，在进程或软中断上下文需要使用spin_lock_irq和spin_unlock_irq来保护对共享资源的访问。

　　而在中断处理句柄中使用什么版本，需依情况而定，如果只有一个中断处理句柄访问该共享资源，那么在中断处理句柄中仅需要spin_lock和spin_unlock来保护对共享资源的访问就可以了。

　　因为在执行中断处理句柄期间，不可能被同一CPU上的软中断或进程打断。但是如果有不同的中断处理句柄访问该共享资源，那么需要在中断处理句柄中使用spin_lock_irq和spin_unlock_irq来保护对共享资源的访问。

　　在使用spin_lock_irq和spin_unlock_irq的情况下，完全可以用spin_lock_irqsave和spin_unlock_irqrestore取代，那具体应该使用哪一个也需要依情况而定，如果可以确信在对共享资源访问前中断是使能的，那么使用spin_lock_irq更好一些。

　　因为它比spin_lock_irqsave要快一些，但是如果你不能确定是否中断使能，那么使用spin_lock_irqsave和spin_unlock_irqrestore更好，因为它将恢复访问共享资源前的中断标志而不是直接使能中断。

　　当然，有些情况下需要在访问共享资源时必须中断失效，而访问完后必须中断使能，这样的情形使用spin_lock_irq和spin_unlock_irq最好。

　　需要特别提醒读者，spin_lock用于阻止在不同CPU上的执行单元对共享资源的同时访问以及不同进程上下文互相抢占导致的对共享资源的非同步访问，而中断失效和软中断失效却是为了阻止在同一CPU上软中断或中断对共享资源的非同步访问。
　　

#include <linux/spinlock.h>

头文件:
#include<linux/spinlock_types.h>

#ifndef __LINUX_SPINLOCK_TYPES_H
#define __LINUX_SPINLOCK_TYPES_H

/*
* include/linux/spinlock_types.h - generic spinlock type definitions
* and initializers
*
* portions Copyright 2005, Red Hat, Inc., Ingo Molnar
* Released under the General Public License (GPL).
*/

//对称多处理器
#if defined(CONFIG_SMP)
#include <asm/spinlock_types.h>
#else
#include <linux/spinlock_types_up.h>
#endif

#include <linux/lockdep.h>

typedef struct {
raw_spinlock_t raw_lock;
#ifdef CONFIG_GENERIC_LOCKBREAK
unsigned int break_lock;
#endif
} spinlock_t;

#define SPINLOCK_MAGIC 0xdead4ead

typedef struct {
raw_rwlock_t raw_lock;
#ifdef CONFIG_GENERIC_LOCKBREAK
unsigned int break_lock;
#endif
} rwlock_t;

#define RWLOCK_MAGIC 0xdeaf1eed

#define SPINLOCK_OWNER_INIT ((void *)-1L)

# define __SPIN_LOCK_UNLOCKED(lockname) \
    (spinlock_t)    {    .raw_lock = __RAW_SPIN_LOCK_UNLOCKED,    \
                SPIN_DEP_MAP_INIT(lockname) }
#define __RW_LOCK_UNLOCKED(lockname) \
    (rwlock_t)    {    .raw_lock = __RAW_RW_LOCK_UNLOCKED,    \
                RW_DEP_MAP_INIT(lockname) }

/*
* SPIN_LOCK_UNLOCKED and RW_LOCK_UNLOCKED defeat lockdep state tracking and
* are hence deprecated.
* Please use DEFINE_SPINLOCK()/DEFINE_RWLOCK() or
* __SPIN_LOCK_UNLOCKED()/__RW_LOCK_UNLOCKED() as appropriate.
*/
#define SPIN_LOCK_UNLOCKED __SPIN_LOCK_UNLOCKED(old_style_spin_init)
#define RW_LOCK_UNLOCKED __RW_LOCK_UNLOCKED(old_style_rw_init)

#define DEFINE_SPINLOCK(x) spinlock_t x = __SPIN_LOCK_UNLOCKED(x)
#define DEFINE_RWLOCK(x) rwlock_t x = __RW_LOCK_UNLOCKED(x)

#endif /* __LINUX_SPINLOCK_TYPES_H */

Linux 内核的排队自旋锁(FIFO Ticket Spinlock)

引言

自旋锁(Spinlock)是一种 Linux 内核中广泛运用的底层同步机制。自旋锁是一种工作于多处理器环境的特殊的锁，在单处理环境中自旋锁的操作被替换为空操作。当某个处理器上的内核执行线程申请自旋锁时，如果锁可用，则获得锁，然后执行临界区操作，最后释放锁；如果锁已被占用，线程并不会转入睡眠状态，而是忙等待该锁，一旦锁被释放，则第一个感知此信息的线程将获得锁。

长期以来，人们总是关注于自旋锁的安全和高效，而忽视了自旋锁的“公平”性。传统的自旋锁本质上用一个整数来表示，值为1代表锁未被占用。这种无序竞争的本质特点导致执行线程无法保证何时能取到锁，某些线程可能需要等待很长时间。随着计算机处理器个数的不断增长，这种“不公平”问题将会日益严重。

排队自旋锁(FIFO Ticket Spinlock)是 Linux 内核 2.6.25 版本引入的一种新型自旋锁，它通过保存执行线程申请锁的顺序信息解决了传统自旋锁的“不公平”问题。排队自旋锁的代码由 Linux 内核开发者 Nick Piggin 实现，目前只针对 x86 体系结构(包括 IA32 和 x86_64)，相信很快就会被移植到其它平台。

传统自旋锁的实现与不足

Linux 内核自旋锁的底层数据结构 raw_spinlock_t 定义如下：

清单 1. raw_spinlock_t 数据结构

typedef struct {

unsigned int slock;

} raw_spinlock_t;

slock 虽然被定义为无符号整数，但是实际上被当作有符号整数使用。slock 值为 1 代表锁未被占用，值为 0 或负数代表锁被占用。初始化时 slock 被置为 1。

线程通过宏 spin_lock 申请自旋锁。如果不考虑内核抢占，则 spin_lock 调用 __raw_spin_lock 函数，代码如下所示：

清单 2. __raw_spin_lock 函数

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

}

LOCK_PREFIX 的定义如下：
清单 3. LOCK_PREFIX宏
#ifdef CONFIG_SMP
#define LOCK_PREFIX \
        ".section .smp_locks,\"a\"\n"   \
        _ASM_ALIGN "\n"         \
        _ASM_PTR "661f\n" /* address */ \
        ".previous\n"           \
        "661:\n\tlock; "

#else /* ! CONFIG_SMP */
#define LOCK_PREFIX ""
#endif
在多处理器环境中 LOCK_PREFIX 实际被定义为 “lock”前缀。
x86 处理器使用“lock”前缀的方式提供了在指令执行期间对总线加锁的手段。芯片上有一条引线 LOCK，如果在一条汇编指令(ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, XCHG)前加上“lock” 前缀，经过汇编后的机器代码就使得处理器执行该指令时把引线 LOCK 的电位拉低，从而把总线锁住，这样其它处理器或使用DMA的外设暂时无法通过同一总线访问内存。
从 P6 处理器开始，如果指令访问的内存区域已经存在于处理器的内部缓存中，则“lock” 前缀并不将引线 LOCK 的电位拉低，而是锁住本处理器的内部缓存，然后依靠缓存一致性协议保证操作的原子性。
decb 汇编指令将 slock 的值减 1。由于“减 1”是“读-改-写”操作，不是原子操作，可能会被同时申请锁的其它处理器上的线程干扰，所以必须加上“lock”前缀。
jns 汇编指令检查 EFLAGS 寄存器的 SF(符号)位，如果为 0，说明 slock 原来的值为 1，则线程获得锁，然后跳到标签 3 的位置结束本次函数调用。如果 SF 位为 1，说明 slock 原来的值为 0 或负数，锁已被占用。那么线程转到标签 2 处不断测试 slock 与 0 的大小关系，假如 slock 小于或等于 0，跳转到标签 2 的位置继续忙等待；假如 slock 大于 0，说明锁已被释放，则跳转到标签 1 的位置重新申请锁。

线程通过宏 spin_unlock 释放自旋锁，该宏调用 __raw_spin_unlock 函数：

清单 4. __raw_spin_unlock函数

static inline void __raw_spin_unlock(raw_spinlock_t *lock)

{

asm volatile("movb $1,%0" : "+m" (lock->slock) :: "memory");

}

可见 __raw_spin_unlock 函数仅仅执行一条汇编指令：将 slock 置为 1。

尽管拥有使用简单方便、性能好的优点，自旋锁也存在自身的不足：

由于传统自旋锁无序竞争的本质特点，内核执行线程无法保证何时可以取到锁，某些执行线程可能需要等待很长时间，导致“不公平”问题的产生。这有两方面的原因：
1. 随着处理器个数的不断增加，自旋锁的竞争也在加剧，自然导致更长的等待时间。
2. 释放自旋锁时的重置操作将无效化所有其它正在忙等待的处理器的缓存，那么在处理器拓扑结构中临近自旋锁拥有者的处理器可能会更快地刷新缓存，因而增大获得自旋锁的机率。
由于每个申请自旋锁的处理器均在全局变量 slock 上忙等待，系统总线将因为处理器间的缓存同步而导致繁重的流量，从而降低了系统整体的性能。

排队自旋锁的设计原理

传统自旋锁的“不公平”问题在锁竞争激烈的服务器系统中尤为严重，因此 Linux 内核开发者 Nick Piggin 在 Linux 内核 2.6.25 版本中引入了排队自旋锁：通过保存执行线程申请锁的顺序信息来解决“不公平”问题。

排队自旋锁仍然使用原有的 raw_spinlock_t 数据结构，但是赋予 slock 域新的含义。为了保存顺序信息，slock 域被分成两部分，分别保存锁持有者和未来锁申请者的票据序号(Ticket Number)，如下图所示：

图 1. Next 和 Owner 域

Linux内核同步：自旋锁-LMLPHP

如果处理器个数不超过 256，则 Owner 域为 slock 的 0-7 位，Next 域为 slock 的 8-15 位，slock 的高 16 位不使用；如果处理器个数超过 256，则 Owner 和 Next 域均为 16 位，其中 Owner 域为 slock 的低 16 位。可见排队自旋锁最多支持 216=65536 个处理器。

只有 Next 域与 Owner 域相等时，才表明锁处于未使用状态（此时也无人申请该锁）。排队自旋锁初始化时 slock 被置为 0，即 Owner 和 Next 置为 0。内核执行线程申请自旋锁时，原子地将 Next 域加 1，并将原值返回作为自己的票据序号。如果返回的票据序号等于申请时的 Owner 值，说明自旋锁处于未使用状态，则直接获得锁；否则，该线程忙等待检查 Owner 域是否等于自己持有的票据序号，一旦相等，则表明锁轮到自己获取。线程释放锁时，原子地将 Owner 域加 1 即可，下一个线程将会发现这一变化，从忙等待状态中退出。线程将严格地按照申请顺序依次获取排队自旋锁，从而完全解决了“不公平”问题。

排队自旋锁的实现

排队自旋锁没有改变原有自旋锁的调用接口，该 API 是以 C 语言宏的形式提供给开发人员。下表列出 6 个主要的 API 和相对应的底层实现函数：

表 1. 排队自旋锁 API

spin_lock_init	无	将锁置为初始未使用状态(值为 0)
spin_lock	__raw_spin_lock	忙等待直到 Owner 域等于本地票据序号
spin_unlock	__raw_spin_unlock	Owner 域加 1，将锁传给后续等待线程
spin_unlock_wait	__raw_spin_unlock_wait	不申请锁，忙等待直到锁处于未使用状态
spin_is_locked	__raw_spin_is_locked	测试锁是否处于使用状态
spin_trylock	__raw_spin_trylock	如果锁处于未使用状态，获得锁；否则直接返回

下面介绍其中 3 个底层函数的实现细节，假定处理器个数不超过 256。

__raw_spin_is_locked
清单 5. __raw_spin_is_locked 函数
static inline int __raw_spin_is_locked(raw_spinlock_t *lock)
{
int tmp = *(volatile signed int *)(&(lock)->slock);
return (((tmp >> 8) & 0xff) != (tmp & 0xff));
}
1. 此函数判断 Next 和 Owner 域是否相等，如果相等，说明自旋锁处于未使用状态，返回 0；否则返回1。
2. tmp 这种复杂的赋值操作是为了直接从内存中取值，避免处理器缓存的影响。
__raw_spin_lock
清单 6. __raw_spin_lock 函数
static inline void __raw_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. LOCK_PREFIX 宏在前文中已经介绍过，就是“lock”前缀。
2. xaddw 汇编指令将 slock 和 inc 的值交换，然后把这两个值相加后的和存到 slock 中。也就是说，该指令执行完毕后，inc 存有原来的 slock 值作为票据序号，而 slock 的 Next 域被加 1。
3. comb 比较 inc 变量的高位和低位字节是否相等，如果相等，表明锁处于未使用状态，直接跳转到标签 2 的位置退出函数。
4. 如果锁处于使用状态，则不停地将当前的 slock 的 Owner 域复制到 inc 的低字节处(movb 指令)，然后重复 c 步骤。不过此时 inc 变量的高位和低位字节相等表明轮到自己获取了自旋锁。
__raw_spin_unlock
清单 7. __raw_spin_unlock 函数
static inline void __raw_spin_unlock(raw_spinlock_t *lock)
{
    __asm__ __volatile__(
        UNLOCK_LOCK_PREFIX "incb %0"
        :"+m" (lock->slock)
        :
        :"memory", "cc");
}
1. 在 IA32 体系结构下，如果使用 PPro SMP 系统或者启用了 X86_OOSTORE，则 UNLOCK_LOCK_PREFIX 被定义为“lock”前缀；否则被定义为空。
2. incb 指令将 slock 最低位字节也就是 Owner 域加 1。

Windows 操作系统的排队自旋锁(Queued Spinlock)介绍

排队自旋锁并不是一个新想法，某些操作系统早已采用了类似概念，只是实现方式有所差别。例如在 Windows 操作系统中排队自旋锁被称为 Queued Spinlock。

Queued Spinlock 的工作方式如下：每个处理器上的执行线程都有一个本地的标志，通过该标志，所有使用该锁的处理器（锁拥有者和等待者）被组织成一个单向队列。当一个处理器想要获得一个已被其它处理器持有的 Queued Spinlock 时，它把自己的标志放在该 Queued Spinlock 的单向队列的末尾。如果当前锁持有者释放了自旋锁，则它将该锁移交到队列中位于自己之后的第一个处理器。同时，如果一个处理器正在忙等待 Queued Spinlock，它并不是检查该锁自身的状态，而是检查针对自己的标志；在队列中位于该处理器之前的处理器释放自旋锁时会设置这一标志，以表明轮到这个正在等待的处理器了。

与 Linux 的排队自旋锁相比，Queued Spinlock 的设计更为复杂，但是 Queued Spinlock 拥有自己的优势：

忙等待 Queued Spinlock 的每个处理器在针对该处理器的标志上旋转，而不是在全局的自旋锁上测试旋转，因此处理器之间的同步比 Linux 的排队自旋锁少得多。
Queued Spinlock 拥有真实的队列结构，因此便于扩充更高级的功能。

扩展排队自旋锁的一点想法

排队自旋锁设计简单、实现容易且性能优秀，因此肯定会受到开发人员的欢迎。本节讨论一下排队自旋锁未来可能有用的一些扩展功能：

超时(Timeout)
尽管排队自旋锁保证了内核执行线程严格按照申请顺序获取锁，但是由于锁的竞争剧烈（例如处理器个数达到64或更多），线程仍然可能会等待过长的时间。当该线程获得锁时，环境也许已发生变化而导致无法完成任务。因此申请线程可以预先指定一个等待阈值，一旦超过该阈值且尚未获得锁，则自动从等待队伍中退出，并返回代表超时的错误值。
优先级(Priority)
当前的实现中，所有的线程一律平等，严格按照申请顺序等待。某些执行关键操作的线程也许需要特殊对待，即赋予更高的优先级。一旦它们申请自旋锁，就把他们插入到等待队列的前部优先执行。

自旋

Linux内核同步：自旋锁