一、spin_lock概述
1. spin lock 是一种可休眠锁，可用于原子上下文。当获取不到锁的时候会spin等待，此时是running状态。
2. spin lock 的发展到现在经历了四个阶段
(1) CAS
锁只有一个原子变量，执行单个 compare-and-swap 指令来获取锁。问题是没有公平可言，无法让等待最长的那个任务优先拿到锁，
为了解决这个问题引入了ticket spinlock。
(2) ticket spinlock
类似排队叫号，只有任务手中事先领取的号和被叫到的号相等时才能持锁进入临界区。这解决了不公平的问题。但是出现叫号时，所有
等待的任务所在的cpu都要读取内存，刷新对应的cache line，而只有获取锁的那个任务所在的cpu对cache line 的刷新才是有意义的，
锁争抢的越激烈，无谓的开销也就越大。
(3) MCS Lock
在ticket spinlock的基础上做一定的修改，让多个CPU不再等待同一个spinlock变量，而是基于各自的per-CPU的变量进行等待，
那么每个CPU平时只需要查询自己对应的这个变量所在的本地cache line，仅在这个变量发生变化的时候，才需要读取内存和刷新这
条cache line，这样就可以解决上述问题。
要实现类似这样的spinlock的分身，其中的一种方法就是使用MCS lock。试图获取一个spinlock的每个CPU，都有一份自己的MCS lock。
(4) qspinlock
相比起Linux中只占4个字节的ticket spinlock，MCS lock多了一个指针，要多占4（或者8）个字节，消耗的存储空间是原来的2-3倍。
qspinlock的首要目标就是改进原生的MCS lock结构体，尽量将原生MCS lock要包含的内容塞进4字节的空间里。
如果只有1个或2个CPU试图获取锁，那么只需要一个4字节的qspinlock就可以了，其所占内存的大小和ticket spinlock一样。当有3个以
上的CPU试图获取锁，需要一个qspinlock加上(N-2)个MCS node。
qspinlock中加入”pending”位域，如果是两个CPU试图获取锁，那么第二个CPU只需要简单地设置”pending”为1，而不用另起炉灶创建一个
MCS node。
试图加锁的CPU数目超过3个是小概率事件，但一旦发生，使用ticket spinlock机制就会造成多个CPU的cache line无谓刷新的问题，而
qspinlock可以利用MCS node队列来解决这个问题。
可见，使用qspinlock机制来实现spinlock，具有很好的可扩展性，也就是无论当前锁的争抢程度如何，性能都可以得到保证。
二、相关数据结构
1. struct spinlock
除去使能deug才会有的相关成员，结构如下：
//include/linux/spinlock_types.h
typedef struct spinlock {
struct raw_spinlock rlock;
} spinlock_t;
//include/linux/spinlock_types.h
typedef struct raw_spinlock {
arch_spinlock_t raw_lock;
} raw_spinlock_t;
//include/asm-generic/qspinlock_types.h
typedef struct qspinlock {
union {
atomic_t val;
struct {
u16 tail;
u16 locked_pending;
};
struct {
u8 reserved[2];
u8 pending;
u8 locked;
};
};
} arch_spinlock_t;
spinlock 结构中只有一个类型为 raw_spinlock 的 rlock 成员。而 raw_spinlock 结构中只有一个类型为 qspinlock 的 raw_lock
成员。qspinlock 结构中维护的是一个联合体。
val：为0表示没有人持锁，然后对其赋值为 _Q_LOCKED_VAL(1)表示持有了该锁。
三、相关函数
//定义并初始化为unlock状态的，名为x的spin_lock变量。
DEFINE_SPINLOCK(x);
四、上锁代码分析
1. spin_lock()
static __always_inline void spin_lock(spinlock_t *lock) //include/linux/spinlock.h
{
raw_spin_lock(&lock->rlock);
}
#define raw_spin_lock(lock) _raw_spin_lock(lock) //include/linux/spinlock.h
void __lockfunc _raw_spin_lock(raw_spinlock_t *lock) //kernel/locking/spinlock.c
{
__raw_spin_lock(lock);
}
static inline void __raw_spin_lock(raw_spinlock_t *lock) //include/linux/spinlock_api_smp.h
{
/* 关抢占 */
preempt_disable();
/* 默认不使能 CONFIG_LOCKDEP，是个空函数 */
spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
/* 默认不使能 CONFIG_LOCK_STAT, 等效于 do_raw_spin_lock(lock) */
LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
}
static inline void do_raw_spin_lock(raw_spinlock_t *lock) __acquires(lock) //include/linux/spinlock.h
{
/* 静态代码检查相关，忽略之 */
__acquire(lock);
arch_spin_lock(&lock->raw_lock);
mmiowb_spin_lock();
}
#define arch_spin_lock(l) queued_spin_lock(l) //include/asm-generic/qspinlock.h
/**
* queued_spin_lock - acquire a queued spinlock
* @lock: Pointer to queued spinlock structure, that is arch_spinlock_t.
*/
static __always_inline void queued_spin_lock(struct qspinlock *lock) //include/asm-generic/qspinlock.h
{
u32 val = 0;
/*
* 参数(*v, *old, new):
* if (*v == *old) {*v = new; return true;}
* if (*v != *old) {*old = *v; return false;}
*
* 如果 lock->val == 0, lock->val = _Q_LOCKED_VAL; return true;
* 也就是说 lock->val 为0表示没有人持锁，此时赋值为1表示持有了该锁
*/
if (likely(atomic_try_cmpxchg_acquire(&lock->val, &val, _Q_LOCKED_VAL)))
return;
/* 若是上面持锁失败，进入持锁慢速路径，上面进行了赋值，传参 val=lock->val */
queued_spin_lock_slowpath(lock, val);
}
(1)
#define preempt_count_inc() preempt_count_add(1) //include/linux/preempt.h
#define preempt_count_add(val) __preempt_count_add(val) //include/linux/preempt.h
static inline void __preempt_count_add(int val) //arch/arm64/include/asm/preempt.h
{
/* 使用的是 current->thread_info.preempt.count */
u32 pc = READ_ONCE(current_thread_info()->preempt.count);
pc += val;
WRITE_ONCE(current_thread_info()->preempt.count, pc);
}
五、解锁代码分析
六、总结
参考：
浅谈spinlock的实现：http://liujunming.top/2020/01/20/%E6%B5%85%E8%B0%88spinlock/
Linux中的spinlock机制[二] - MCS Lock：https://zhuanlan.zhihu.com/p/89058726
Linux中的spinlock机制[三] - qspinlock：https://zhuanlan.zhihu.com/p/100546935
Linux中的spinlock机制[四] - API的使用：https://zhuanlan.zhihu.com/p/90634198
MCS locks and qspinlocks：https://lwn.net/Articles/590243/
TODO: 看来也要分为3讲了
一、spin_lock概述
1. spin lock 是一种可休眠锁，可用于原子上下文。当获取不到锁的时候会spin等待，此时是running状态。
2. spin lock 的发展到现在经历了四个阶段
(1) CAS
锁只有一个原子变量，执行单个 compare-and-swap 指令来获取锁。问题是没有公平可言，无法让等待最长的那个任务优先拿到锁，为了解决这个问题引入了ticket spinlock。
(2) ticket spinlock
类似排队叫号，只有任务手中事先领取的号和被叫到的号相等时才能持锁进入临界区。这解决了不公平的问题。但是出现叫号时，所有等待的任务所在的cpu都要读取内存，刷新对应的cache line，而只有获取锁的那个任务所在的cpu对cache line 的刷新才是有意义的，锁争抢的越激烈，无谓的开销也就越大。
(3) MCS Lock
在ticket spinlock的基础上做一定的修改，让多个CPU不再等待同一个spinlock变量，而是基于各自的per-CPU的变量进行等待，那么每个CPU平时只需要查询自己对应的这个变量所在的本地cache line，仅在这个变量发生变化的时候，才需要读取内存和刷新这条cache line，这样就可以解决上述问题。要实现类似这样的spinlock的分身，其中的一种方法就是使用MCS lock。试图获取一个spinlock的每个CPU，都有一份自己的MCS lock。
(4) qspinlock
相比起Linux中只占4个字节的ticket spinlock，MCS lock多了一个指针，要多占4（或者8）个字节，消耗的存储空间是原来的2-3倍。qspinlock的首要目标就是改进原生的MCS lock结构体，尽量将原生MCS lock要包含的内容塞进4字节的空间里。
如果只有1个或2个CPU试图获取锁，那么只需要一个4字节的qspinlock就可以了，其所占内存的大小和ticket spinlock一样。当有3个以上的CPU试图获取锁，需要一个qspinlock加上(N-2)个MCS node。
qspinlock中加入”pending”位域，如果是两个CPU试图获取锁，那么第二个CPU只需要简单地设置”pending”为1，而不用另起炉灶创建一个MCS node。
试图加锁的CPU数目超过3个是小概率事件，但一旦发生，使用ticket spinlock机制就会造成多个CPU的cache line无谓刷新的问题，而qspinlock可以利用MCS node队列来解决这个问题。
可见，使用qspinlock机制来实现spinlock，具有很好的可扩展性，也就是无论当前锁的争抢程度如何，性能都可以得到保证。
二、相关数据结构
1. struct spinlock
除去使能deug才会有的相关成员，结构如下：//include/linux/spinlock_types.htypedef struct spinlock {struct raw_spinlock rlock;} spinlock_t;
//include/linux/spinlock_types.htypedef struct raw_spinlock {arch_spinlock_t raw_lock;} raw_spinlock_t;
//include/asm-generic/qspinlock_types.htypedef struct qspinlock {union {atomic_t val;
struct {u16tail;u16locked_pending;};struct {u8reserved[2];u8pending;u8locked;};};} arch_spinlock_t;
spinlock 结构中只有一个类型为 raw_spinlock 的 rlock 成员。而 raw_spinlock 结构中只有一个类型为 qspinlock 的 raw_lock成员。qspinlock 结构中维护的是一个联合体。
val：为0表示没有人持锁，然后对其赋值为 _Q_LOCKED_VAL(1)表示持有了该锁。
三、相关函数
//定义并初始化为unlock状态的，名为x的spin_lock变量。DEFINE_SPINLOCK(x);
四、上锁代码分析
1. spin_lock()static __always_inline void spin_lock(spinlock_t *lock) //include/linux/spinlock.h{raw_spin_lock(&lock->rlock);}
#define raw_spin_lock(lock)_raw_spin_lock(lock) //include/linux/spinlock.h
void __lockfunc _raw_spin_lock(raw_spinlock_t *lock) //kernel/locking/spinlock.c{__raw_spin_lock(lock);}
static inline void __raw_spin_lock(raw_spinlock_t *lock) //include/linux/spinlock_api_smp.h{/* 关抢占 */preempt_disable();/* 默认不使能 CONFIG_LOCKDEP，是个空函数 */spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);/* 默认不使能 CONFIG_LOCK_STAT, 等效于 do_raw_spin_lock(lock) */LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);}
static inline void do_raw_spin_lock(raw_spinlock_t *lock) __acquires(lock) //include/linux/spinlock.h{/* 静态代码检查相关，忽略之 */__acquire(lock);arch_spin_lock(&lock->raw_lock);mmiowb_spin_lock();}
#define arch_spin_lock(l)queued_spin_lock(l) //include/asm-generic/qspinlock.h
/** * queued_spin_lock – acquire a queued spinlock * @lock: Pointer to queued spinlock structure, that is arch_spinlock_t. */static __always_inline void queued_spin_lock(struct qspinlock *lock) //include/asm-generic/qspinlock.h{u32 val = 0;
/* * 参数(*v, *old, new): *if (*v == *old) {*v = new; return true;} *if (*v != *old) {*old = *v; return false;} * * 如果 lock->val == 0, lock->val = _Q_LOCKED_VAL; return true; * 也就是说 lock->val 为0表示没有人持锁，此时赋值为1表示持有了该锁 */if (likely(atomic_try_cmpxchg_acquire(&lock->val, &val, _Q_LOCKED_VAL)))return;
/* 若是上面持锁失败，进入持锁慢速路径，上面进行了赋值，传参 val=lock->val */queued_spin_lock_slowpath(lock, val);}
(1)
#define preempt_count_inc() preempt_count_add(1) //include/linux/preempt.h
#define preempt_count_add(val)__preempt_count_add(val) //include/linux/preempt.h
static inline void __preempt_count_add(int val) //arch/arm64/include/asm/preempt.h{/* 使用的是 current->thread_info.preempt.count */u32 pc = READ_ONCE(current_thread_info()->preempt.count);pc += val;WRITE_ONCE(current_thread_info()->preempt.count, pc);}
五、解锁代码分析
六、总结
参考：浅谈spinlock的实现：http://liujunming.top/2020/01/20/%E6%B5%85%E8%B0%88spinlock/Linux中的spinlock机制[二] – MCS Lock：https://zhuanlan.zhihu.com/p/89058726Linux中的spinlock机制[三] – qspinlock：https://zhuanlan.zhihu.com/p/100546935Linux中的spinlock机制[四] – API的使用：https://zhuanlan.zhihu.com/p/90634198MCS locks and qspinlocks：https://lwn.net/Articles/590243/
TODO: 看来也要分为3讲了
原创文章，作者：kirin，如若转载，请注明出处：https://blog.ytso.com/267712.html