4 qspinlock

MCS Lock并没有完全替代Ticket spinlock，其中一个原因是MCS Lock的数据结构大于32bit，内核中很多重要的结构体中都内嵌了spinlock，其中一些（典型的如struct page）的体积是不允许变大的。后来Waiman Long提出了qspinlock，并由Peter Zijlstra进行了改进，形成了现在的qspinlock。qspinlock是在kernel 4.16成为默认spinlock的。

qspinlock基于MCS Lock进行优化，既解决了MCS Lock的数据结构大于32bit的问题，又避免了cache颠簸的问题。后续对qspinlock的分析都是基于openEuler kernel 4.19。

qspinlock结合使用32bit的qspinlock结构体和的per-CPU mcs_spinlock，设计有几个要点：

1. 数据结构压缩：qspinlock结构体的大小是32bit，使用位来表示锁状态（8bit）和队尾的CPU。

2. 避免cache颠簸：qspinlock的设计使用了MCS spinlock队列对等待的CPU进行排队，每个排队中的CPU都在自己的per-CPU MCS spinlock上自旋，因此可以避免cache颠簸。

4.1 qspinlock对数据结构的压缩

qspinlock的数据结构大小为32bit，其定义见（include/asm-generic/qspinlock_types.h）：

typedef struct qspinlock {
        union {
                atomic_t val;

                /*
                 * By using the whole 2nd least significant byte for the
                 * pending bit, we can allow better optimization of the lock
                 * acquisition for the pending bit holder.
                 */
#ifdef __LITTLE_ENDIAN
                struct {
                        u8      locked;
                        u8      pending;
                };
                struct {
                        u16     locked_pending;
                        u16     tail;
                };
#else
                struct {
                        u16     tail;
                        u16     locked_pending;
                };
                struct {
                        u8      reserved[2];
                        u8      pending;
                        u8      locked;
                };
#endif
        };
} arch_spinlock_t;

qspinlock结构体由一个union组成，可以看到一个32bit的qspinlock被分成了4部分，如下图所示：

其中各部分说明如下：

1. locked：用于指示qspinlock是否加锁，0表示未加锁，其余值表示已加锁（通常情况下_Q_LOCKED_VAL == 1表示加锁，在PV场景下可能会使用_Q_SLOW_VAL == 3）。

2. pending：第一个等待锁的CPU需要先设置pending位，后续等待锁的CPU则全部进入MCS spinlock队列自旋等待。最初Waiman Long的patch并未包含该位，引入该pending位后，第一个等待者可以避免与访问自己的MCS spinlock数组相关的缓存未命中惩罚。

3. tail index：2个bit位，每个CPU在同一时刻可能存在4种不同的上下文：Normal, Software interrupt, Hardware interrupt, Non-maskable interrupt，因此每个CPU的per-CPU MCS spinlock需要包含一组共4个MCS spinlock，每个MCS spinlock对应一个上下文场景。

4. tail cpu：队尾的CPU编号（+1），将编号+1是为了和没有CPU排队的情况区分开来。

4.2 qspinlock对MCS spinlock的使用

前面提到，qspinlock的设计使用了MCS spinlock队列对等待的CPU进行排队，每个排队中的CPU都在自己的per-CPU MCS spinlock上自旋，per-cpu MCS spinlock定义如下：

static DEFINE_PER_CPU_ALIGNED(struct qnode, qnodes[MAX_NODES]);

MAX_NODES的值为4，可以看到每个CPU有4个struct qnode结构类型的per-cpu变量，struct qnode定义如下：

struct qnode {
        struct mcs_spinlock mcs;
#if defined(CONFIG_PARAVIRT_SPINLOCKS) || defined(CONFIG_NUMA_AWARE_SPINLOCKS)
        long reserved[2];
#endif
};

stuct qnode包含了struct mcs_spinlock，多CPU竞争qspinlock时的示意图如下：

1. 第一个锁等待者在设置好pending位之后，就在qspinlock结构的locked上自旋，直到锁持有者释放锁（将qspinlock结构的locked值设置为0）。

2. 第二个锁等待者需要将自己放入mcs_spinlock队列尾部，因为其是mcs_spinlock队列的头，其在qspinlock结构的pending | locked上自旋，直到qspinlock结构的pending和locked均变为0。

3. 第三个及以后的锁等待者将自己放入mcs_spinlock队列尾部，并在自己的per-cpu MCS spinlock上自旋，直到到达队列头部，然后在qspinlock结构的pending | locked上自旋，直到qspinlock结构的pending和locked均变为0。