3.3　自旋锁

自旋锁（spinlock）用于短竞态逻辑的并发重入控制，同时只允许一个逻辑进入，逻辑包括普通参与调度的逻辑和不参与调度的中断逻辑。默认的spin_lock自旋锁入口不关闭中断，中断逻辑和参与调度的普通逻辑同样参与自旋锁的竞争。如果用户空间的逻辑已经持有自旋锁了，中断在持有自旋锁的中间发生，然后去尝试获得自旋锁就会被卡，中断逻辑不再释放CPU给普通线程。而如果允许中断重入逻辑参与竞态，就需要使用spin_lock_irq、spin_lock_bh或spin_lock_irqsave在普通逻辑中获得锁时关闭中断或者软中断。参与竞态的逻辑有可能就位于中断上下文中，如果在中断上下文中使用spin_lock_irq，就可能导致严重的状态不一致问题。所以在用户上下文中使用spin_lock_irq来直接关闭中断，在中断上下文中使用spin_lock_irqsave来保存当前中断的上下文，再确保关闭中断是正确的。因此在硬中断中只可能出现spin_lock_irqsave，在普通逻辑的中断中则可能出现所有的形式。

自旋锁有禁止编译器重排和CPU乱序的内存栅语义，所以在自旋锁的前后，是不需要考虑乱序执行的问题的。

lockref中包含了一个自旋锁，cmpxchg64_relaxed并没有使用自旋锁API接口，而直接使用内部的数据格式定义，是一种侵入式的优化。自旋锁的定义如下。

从以上代码可知，自旋锁在本质上就是一个简单的4字节的整数。一般来说，4字节的长度正好对应我们在lockref中看到的自旋锁的内存空间占用。

计算系统分为UP（Uni-Processor，单处理器）和SMP（Symmetric Multi-Processors，对称多处理器），而UP的CPU只有一个核，所以不需要考虑并发问题，只需要考虑抢占问题。抢占是指在同一个CPU的另外一个任务抢占当前任务执行的行为；并发是指多个CPU核心完全并行地执行一段逻辑的行为。这里只讨论在SMP下spinlock的实现。

自旋锁的头文件是include/linux/spinlock.h，根据编译选项的不同决定是要包括SMP的实现还是UP的实现，当编译选项指定SMP或者调试自旋锁的时候，就会包含spinlock_api_smp.h头文件，通过宏控制包含不同的头文件来变换定义。include/linux/spinlock_types.h下定义了自旋锁的通用数据类型，同样，也会根据编译选项来选择具体的SMP版本或者UP版本的spinlock_types.h文件。lockdep是内核用于检测死锁的机制，可以检测spinlock、rwlock、mutex、rwsem等内核锁的死锁问题。在编译配置为SMP，并且不打开lockdep的（关闭CONFIG_DEBUG_LOCK_ALLOC宏）情况下，spinlock只是一个4字节的整数，对应的自旋锁操作就是最精简的。加锁的代码如下。

在最新的内核中可以认为CONFIG_GENERIC_LOCKBREAK开关已经不被打开，在spinlock的开头部分有一个宏分支，如果这个开关被打开，就会定义CAS的函数实现；如果这个开关不被打开，则会进入上述SMP的标准实现。在x86下，这个实现对应了qspinlock。

preempt_disable（）函数先关闭当前CPU的抢占，以上代码获得了自旋锁会关闭抢占的逻辑设计。这是因为在内核中认为所有的spinlock都是快速完成的，不会等待很久，因此不允许当前的线程被抢占，CPU必须忙等待当前的自旋任务。这个逻辑对于CPU来说极其重要，因为在整个内核中，任何一个自旋锁持有时间过长，都会导致非常严重的响应问题。自旋锁的使用越来越广泛，当内核处在极高负载的情况时，就比较容易触发某个模块。自旋锁的不恰当使用带来的性能瓶颈，已经成为当前影响Linux内核性能的重要原因。

spin_acquire是lockdep的入口，用来检查死锁的问题，因为这里假设spinlock没有包含lockdep，所以结构体中对应的域不存在。在lockdep的实现中，如果没有打开lockdep宏，则所有的函数都对应空操作。

LOCK_CONTENDED（lock，do_raw_spin_trylock，do_raw_spin_lock）是核心操作，实际上就是do_raw_spin_lock（lock）函数的调用，定义如下。

__acquires（lock）和__acquire（lock）是内核sparse静态代码检查工具的语法，没有逻辑意义。mmiowb_spin_lock（）用于在NUMA的情况下多个CPU之间的同步。arch_spin_lock是真正的加锁逻辑。在x86下，内核实现的自旋锁是qspinlock，对应的实现在kernel/locking/qspinlock.c中。最外层的spin_lock的API调用会转换为arch_spin_lock，最终将转换为queued_spin_lock函数的调用。这个映射发生在include/asm-generic/qspinlock.h中，定义如下。

qspinlock是自旋锁发展到一定阶段的成熟产品。最原始的自旋锁是CAS自旋锁，在获得锁的时候，简单地检查自旋锁的值是不是0，如果值为0就将值改为1，代表获得锁；如果值已经为1，则表示锁已经被其他人持有，这时就会自旋等待。

这种拿锁方式的最大问题是：当一个线程释放锁时，下一个线程能否拿到锁全看调度，并不是等待时间最久的线程能拿到锁。改进这个问题的方法是使用ticket spinlock，自旋锁的数据结构是两个整数，第一个整数owner代表当前持有锁的线程的序号，第二个整数next代表最后一个等待锁的线程的序号。

每一个线程在等待自旋锁的时候都会把next增加1，得到的值就是自己的ticket，已经得到锁的线程会把owner设置为自己的序号，当释放锁的时候，会把owner自增1，意思是该轮到下一个线程来获得锁了。这样持有与当前owner线程相等ticket的线程就会获得锁，其他的线程检查owner与自己的ticket的值是否一样，若不一样就不会获得锁。这个设计有效解决了等待队列顺序的公平性问题。但是这个方法也有一个很大的问题，就是cache不友好，因为当自旋锁的owner被改变的时候，也就是释放锁的时候，锁所在的cache line会被invalide，这个时候其他的线程（或者说其他的CPU核）去对比新的owner值就相当于重新从内存中加载这个自旋锁的值。

为了解决cache不友好的问题，又产生了MCS自旋锁。MCS自旋锁在内核中存在一个单独的定义文件（msc_spinlock.h），但是在内核代码中没有被直接使用，只是在qspinlock中被内核使用。MCS自旋锁的原理是将原来的一个整数锁变成了一个锁链表。每个自旋等待的线程都对应一个链表上的节点，每个线程的自旋逻辑都只检查自己的链表内容来确定自己是否可以获得锁。而当持有锁的线程释放锁的时候，只会改变链表的下一个节点的持锁信息，从而只有下一个节点对应的自旋线程能看到内容梗概。

由于只检查自己是否可以获得锁，并且释放锁的时候只改变一个线程的持锁信息，所以就没有cache被刷新的问题了。MCS自旋锁的实现是一个简单的链表，当前持有锁的永远是链表的第一个节点，下一个节点永远是下一个会获得锁的线程。当释放锁的时候，持有锁的线程就修改链表的下一个节点的内容，下一个节点对应的线程就能根据这个通知获得锁，其他的节点没有得到这个通知，所以既不刷新cache，也不会获得锁，新加入的等待节点就会直接进入链表的最后。MSC自旋锁的传递如图3-3所示。

自旋锁出现竞态的情况非常少，出现竞态的时候一般都只有一个自旋线程，所以qspinlock的设计是对下一个自旋线程进行优化。MCS spinlock大于4字节，因为除了锁本身还需要一个指向下一个节点的指针，所以即使没有竞态发生，MCS spinlock也大于4字节。qspinlock使用4字节的锁，但是在锁内部切分成三大部分：16位是tail部分；8位是pending部分；8位是锁部分。qspinlock的tail部分是MCS自旋锁的链表节点，pending部分是下一个要获得自旋锁的自旋线程，8位的锁部分有0和1两个取值，表示持有锁的状态。tail只有16位，不能充当链表中的指针，所以在等待的线程必然位于不同的CPU，可以同时等待的线程数一定小于CPU的个数（这里先不考虑中断，中断逻辑不属于线程），所以在tail中并不需要存储指针，只需要存储CPU的编号，就可以找到下一个自旋等待的线程了。后面的线程就与MCS完全一样，也就是说，qspinlock在本质上是在当前持有锁和下一个候选锁上做了优化，从第三个锁开始完全就是MCS spinlock的实现。qspinlock原理图如图3-4所示。

MCS spinlock的数据结构定义如下。

mcs_node是个每CPU变量，最多有四个。即使禁止了抢占，线程仍然可以被中断，softirq、hardirq和nmi三种中断都可以打断自旋锁的自旋，并且可以继续在同一个CPU上添加嵌套自旋锁。与自旋锁发生自旋的概率一样，在大部分情况下，同一个CPU都只有一个逻辑在自旋（包括线程逻辑和中断逻辑），但是当发生嵌套的时候一般只有一级嵌套，嵌套最多可以有四级。这里的中断和线程的嵌套自旋的等级在qspinlock中叫作idx。

qspinlock在x86下的定义如下。

32位的qspinlock结构体如图3-5所示。

其中，对应到位的定义如下。

在tail的16个位中定位一个mcs_node（即一个自旋等待的逻辑实体），需要分为CPU索引和idx两部分，CPU编号从1开始，idx最大值是3。tail的编码逻辑如下。

qspinlock的加锁逻辑非常复杂，因为涉及MCS节点队列、pending位和lock位三者的切换，并且要高性能地可重入实现，因此整个流程的导出都是竞态判断的。qspinlock的加锁逻辑如下。

queued_spin_lock是实际执行上锁的操作，_Q_LOCKED_VAL的值是1，第一步尝试用简单的原子操作进行上锁，因为大部分情况是没有竞态的，这一步如果成功，就可以直接获得锁，这时qspinlock相当于一个简单的CAS自旋锁操作。lockref中第一步的原子操作尝试获得锁，如果尝试成功，就相当于完成自旋锁加锁，如果不成功，就会调用正常的自旋锁路径。

atomic_try_cmpxchg_acquire会把val变量设置为原来的值，当第一次尝试获得锁失败，val中已经包含了当前lock->val的值。在qspinlock的情况下，lock->val的值并不一定为1，因为虽然这时候已经上锁，但qspinlock的锁只占了8位，其他的位仍然可能有内容。

如果尝试无法获得锁，就会进入慢速路径，在x86下kernel/locking/qspinlock.c中定义的queued_spin_lock_slowpath函数，添加注释后的代码如下（代码中去掉了不相关逻辑）：

加锁逻辑在本质上位于三个不同阶段的不同阻塞等待继续前进的逻辑，而释放锁的逻辑简单得多，因为在释放锁的时候只更改lock位即可，代码如下。

自旋锁的性能

自旋锁在Linux内核中被重度使用，尤其是在核心系统。自旋锁的逻辑看起来不那么友好，因为自旋锁在使用时不能一直自旋，甚至不能过多地自旋。在内核中为自旋锁专门开发了调试支持数据，可以看到自旋锁的运行情况，但是在并发高到一定的程度时，内核测试用例并不一定能发现特定场景高并发带来的自旋锁瓶颈。而这种瓶颈一旦发生，就会对整个系统的影响非常大，因为高并发自旋意味着所有的CPU都在忙等，系统失去响应。这种状态叫作自旋灾难。

在使用自旋锁的时候，使用者必须要有人为的锁判断，能判断出该锁不应该锁太久。实际上大部分使用者并没有这个判断能力，尤其难以判断逻辑并发到什么程度会造成自旋灾难。对于大部分内核逻辑，应该使用可睡眠的其他锁，一旦没有拿到锁，自己的CPU上下文就会让渡给其他的线程，这个让渡与内核的进程调度算法关联。内核的调度算法会判断其他的线程有没有更高的CPU需求，如果有，就让其他的线程先占用CPU去执行，而不会让加锁失败的线程完全霸占CPU在忙等。但是这样做的代价是，线程上下文的切换是一个相对高性能惩罚的操作，即要保存完整的寄存器上下文，要刷Cache，也要让CPU的流水线中充满了来自另外一个线程的内容。当这个加锁的线程恢复执行的时候，这一切又要重来一遍。

在内核内部，很多情况都需要阻塞地等待一个结果，但是预期阻塞的持续时间较短。自旋锁的逻辑是其就要自旋地在这里等待，不会让出CPU，更加不会触发内核的调度引擎。这个逻辑本身是十分危险的，例如在中断逻辑中一旦没有用好，就意味着该CPU的性能惩罚会达到完全不可接受的程度。

使用自旋需要使用者自我承诺：充分地了解自己的逻辑会给CPU带来的性能惩罚，并且不使用Linux内核的调度算法来决策线程的调度，还需要知道自己的逻辑在并发程度增强时会不会产生自旋灾难。

下面，我们看一个内核之外的DPDK的自旋锁的实现，具体代码如下。

以上DPDK的自旋锁使用GCC的ASM扩展来实现，但是并不影响我们分析对应的汇编逻辑。这是一个简单原始的CAS自旋锁，相比内核的实现功能简单很多。xchg这个指令的用途是交换内存中两个值的内容，但是比较特殊的是xchg自带锁总线的操作，所以该指令的执行有可能失败。在指令执行失败的情况下，尝试加锁就会失败，但不会阻塞，继续执行，不会产生retire效果。

代码中“2”这个分支标签就是用于对比该锁的值是不是0，如果该锁的值不是0而是1，则表示有人已经上锁，将锁的值进行交换，也就是加锁，并循环尝试加锁的过程。

在这个自旋锁的实现过程中有一个pause操作，该操作是一个宏指令，在经过CPU的解码之后会变成若干个低功耗的nop操作，就是解码之后的微指令，早期的CPU上的pause指令会被直接翻译成nop指令。pause指令是Intel专门针对自旋锁的功耗和性能的优化实现。

内核和DPDK都没有使用CSMA算法：内核有更好的MCS队列实现方法；DPDK追求通用编程领域的极限性能，因为DPDK程序的数据核基本上是满负载运行的，CSMA算法对于功率的降低带来的延迟惩罚对DPDK这种极限延迟要求的场景并不合适，并且DPDK一般很少使用锁。 bWYUU+DT5P2WzKPtNGZb3jY/vK/fAoZRH/QrkTZPqOp28BPVeJKWXd6ju7tgqLxm