qspinlock分析

发表于 | 更新于: | 分类于 | 阅读次数:
字数统计: 1.1k | 阅读时长 ≈ 4

qspinlock

Qspinlock 代码分析

MCS锁没有被广泛应用的原因之一是，每个锁都需要在每个cpu上使用一个副本，从而带来了大量的空间浪费。
Qspinlock的出发点是，在申请自旋锁之前要关闭进程抢占，因此每个CPU上全部需要的MCS锁副本是有限的。实际分析下来，一个CPU上最多同时等待4个自旋锁。分析如下：

  1. 申请自旋锁的函数禁止内核抢占，所以进程在等待自旋锁的过程中不会被其他进程抢占。
  2. 进程在等待自旋锁的过程中可能被软中断抢占，然后软中断等待另一个自旋锁。
  3. 软中断在等待自旋锁的过程中可能被硬中断抢占，然后硬中断等待另一个自旋锁。
  4. 硬中断在等待自旋锁的过程中可能被不可屏蔽中断抢占，然后不可屏蔽中断等待另一个自旋锁。
    因此通过使用qspinlock可以解决mcs锁使用大量存储空间的问题，可用性得到了提升。

qspinlock的代码主要集中在qspinlock.c,qspinlock.h,qspinlock_types.h中。

数据结构

qspinlock的数据结构定义在qspinlock_types.h中。如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 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
...
#endif
	};
} arch_spinlock_t;

其结构如下。整体长度为32位，可以表现为一个整形值val，也可以拆分成三个域。

  • locked字段置1说明锁被占用。
  • pending字段一般只用第8位。置1说明有进程在等待占用锁。
  • tail是类似mcs锁数据结构中next的左右，标识等待队列的尾部节点。它分为两部分。
    • cpu字段。在少于16k个处理器时该字段使用18-31位，指出相应的cpu号（加1）
    • idx字段。在少于16k个处理器时该字段使用16-17位，指出使用了4个mcs锁的哪一个。

对于mcs锁的结构也做了一个改动。增加了count位，每个CPU上第一个mcs实例上的count记录了总共使用了几个mcs结构。

1
2
3
4
5
6
//mcs_spinlock.h
struct mcs_spinlock {
	struct mcs_spinlock *next;
	int locked; /* 1 if lock acquired */
	int count;  /* nesting count, see qspinlock.c */
};

内核做了几个优化：

  1. 第1个等待自旋锁的处理器直接在锁自身上面自旋等待，不是在自己的mcs_spinlock结构体上自旋等待。这个优化带来的好处是：当锁被释放的时候，不需要访问mcs_spinlock结构体的缓存行，相当于减少了一次缓存没命中。后续的处理器在自己的mcs_spinlock结构体上面自旋等待，直到它们移动到队列的首部为止。
  2. pending位进一步扩展这个优化策略。第1个等待自旋锁的处理器简单地设置pending位，不需要使用自己的mcs_spinlock结构体。第2个处理器看到pending被设置，开始创建等待队列，在自己的mcs_spinlock结构体的locked字段上自旋等待。这种做法消除了两个等待者之间的缓存同步，而且第1个等待者没使用自己的mcs_spinlock结构体，减少了一次缓存行没命中。

封装及初始化

1
2
3
4
5
6
7
8
9
// qspinlock_types.h
#define	__ARCH_SPIN_LOCK_UNLOCKED	{ { .val = ATOMIC_INIT(0) } }
// qspinlock.h
#define arch_spin_is_locked(l)		queued_spin_is_locked(l)
#define arch_spin_is_contended(l)	queued_spin_is_contended(l)
#define arch_spin_value_unlocked(l)	queued_spin_value_unlocked(l)
#define arch_spin_lock(l)		queued_spin_lock(l)
#define arch_spin_trylock(l)		queued_spin_trylock(l)
#define arch_spin_unlock(l)		queued_spin_unlock(l)

这一部分比较简单。例如unlock就是将locked位置0。lock操作如果没有竞争者也比较简单。复杂点是如果有竞争者的时候，即queued_spin_lock_slowpath()函数的处理。

lock_slowpath

该函数是qspinlock.c的主要内容。其具体处理流程见流程图。我们跳过虚拟化的部分。
该函数分几个部分。
第一部分尝试直接获取锁，如果确定有竞争者，则进入下一部分创建mcs结构。如果只有我们在等待的话，直接在qspinlock结构上等待，不创建mcs锁。
第二部分是确定有竞争者，因此需要初始化一个mcs结构，等待我们成为等待队列的队头，再等待上一个用户unlock完毕。
第三部分是获取锁及清理mcs结构。