一、前言
最近参加了很多D状态导致卡顿问题的分析，都是在等待内核中的某一把mutex或者rwsem锁。mutex比较简单一些，只会有一个线程持锁，其它线程睡眠等待。而rwsem就稍显复杂，会存在多个线程同时持锁，导致等待的线程睡眠很长时间的情况。并且，我们对rwsem锁传递的优化，只能是writer持锁才能传递，reader持锁时传递不了。为了弄明白其中的原理，决定认真看一下代码。
二、锁的作用
Linux作为典型的多用户、多任务、抢占式内核调度的操作系统，在内核层面涉及到各种软硬件中断、多线程、抢占式内核调度、多处理器SMP架构等，内核在完成自己工作的时候需要处理各种条件下资源抢占的冲突问题。因此linux内核提供了semaphore、spinlock、mutex等锁机制，以及rcu、atomic等同步机制来解决这些问题。然而每种机制都有不同的实现原理以及适用场景，在性能方面也是会存在一定差异，因此对于不同场景下的问题我们能选择最适用的机制才是最好的。
mutex锁，也叫互斥锁。特点是：
a 某个时刻，只能有一个线程持锁进入临界区
b 线程在持锁失败后，进入睡眠状态
spinlock，也叫自旋锁。特点是：
a 某个时刻，只能有一个线程持锁进入临界区
b 线程在持锁失败后，不进入睡眠状态而是原地自旋，等待持锁成功
因为线程睡眠、唤醒时都需要进行调度，这部分线程上、下文的切换也是性能开销。而spinlock则在持锁失败后，不会进行睡眠，少了这一部分的开销。但是，spinlock不适合保护很大的临界区，因为在持锁后会关闭抢占或中断，如果持锁时间过长，持锁线程以及持锁未成功进行自旋线程所在cpu会出现调度不及时带来的性能问题。
另外，在软硬中断上下文，是不允许睡眠的，所以mutex不能在这里使用，需要使用spinlock。
rwsem，读写信号量，和mutex很像。保护临界区的原因是其同时有被修改和读的可能，如果这个资源只是被读永远不会修改，那也不需要保护。有这样一个场景，被保护的临界区大部分情况下都是读取操作，少数情况会被修改。如果使用mutex，假设此刻一个读者进入临界区，另外一个线程也是读取操作，那它因为没有拿到锁而去休眠，但实际上它只是想去读，并不会做修改，按理是可以进去的。这个时候rwsem的作用就体现出来了，所以它的特点是：
a 同一时刻允许多个读者（reader）获得锁进入临界区
b 同一时刻只允许一个写者（writer）获得锁进入临界区，也就是写者与写者互斥
c 同一时刻不存在写着和读者同时获取锁进入临界区，也就是读者与写者互斥
d 持锁失败后，进入睡眠状态
三、rwsem
1. rwsem简介
以下是一个简单的rwsem工作示意图：
传统的rwsem只需要一个count计数和一个等待队列就可以了，等待队列中是一个个阻塞的线程，thread owner(s)当前持有rwsem，当它(们)离开临界区释放锁的时候，如果没有持锁的线程了，会唤醒等待队列中第一个线程（top waiter）或者一组reader，这时候top waiter会去竞争持锁，如果成功，那么从等待队列中摘下，成为owner。如果失败，继续保持阻塞状态，等待owner释放锁的时候唤醒它。在owner task持锁过程中，如果有新的任务来竞争rwsem，那么就会进入阻塞状态并插入等待队列的尾部。
资料直通车：Linux内核源码技术学习路线+视频教程内核源码
2. rwsem数据结构
以下代码都是基于kenerl 5.10版本
（1）count
count用于描述rwsem的一些状态，在64位的系统中，各个bit定义如下：
与count值相关的宏
这里要注意RWSEM_READ_FAILED_MASK，用于reader是否可以持锁的判断，其中有一位是RWSEM_FLAG_WAITERS。有一个场景，假设当前持锁的是reader，来了一个writer，持锁失败进入等待队列，那么RWSEM_FLAG_WAITERS为1。此时又有一个reader来持锁，在快速路径中根据这个判断，持锁也会失败，进入慢速路径，再根据一些条件进行判断是否可以持锁。所以，reader已经持锁的情况下，其它的reader也不是无条件可以马上持锁的，后续会讲。
（2）owner
owner成员有两个作用：
1.记录rwsem被哪个Task持有。只有writer持锁时，这个owner才能正确表示持有者，而可能同时存在很多个reader，所以reader持锁时，owner不能正确表示持锁者，这也是锁传递不能对reader进行传递的原因。
2.因为task_struct地址是L1_CACHE_BYTES(cache line大小典型值为32byte)对齐的，所以其最低的3位是恒等于0的，这3位就可以用于描述一些状态信息，具体有：
与owner 状态相关的宏
（3）osq
struct optimistic_spin_queue osq，在配置了CONFIG_RWSEM_SPIN_ON_OWNER时，rwsem就支持乐观自旋机制，osq成员就是乐观自旋需要持有的MCS锁队列。数据结构optimistic_spin_queue只有一个成员tail，如果等于0，那就是一个空队列，说明没有乐观自旋的任务。否则，tail指向一个节点是optimistic_spin_node对象队列的尾部(tail并不是一个指针，它是一个cpu number，optimistic_spin_node对象是per cpu的，有了cpu number就可以定位到其optimistic_spin_node对象)。osq乐观自旋原理后面会讲。
（4）wait_list、wait_lock
rwsem是睡眠锁，当取锁失败并且不在乐观自旋状态时需要挂入wait_list等待队列，等待owner释放锁。
wait_lock是一个spin_lock锁，用于保护wait_list
四、osq
1. osq简介
和osq相关的两个结构体
osq对象结构体，从其内部变量next、prev可以看出，osq是一个双向链表locked 表示这个节点是否获得mcs锁，为1表示持有。
cpu 可以获得具体的节点，因为optimistic_spin_node 是percpu的，每个cpu上一个节点。
osq工作示意图
字如其名，Optimistic spin queue就是乐观自旋队列的意思，也就是形成一组处于自旋状态的任务队列。和等待队列不一样，这个队列中的任务都是当前正在执行的务。Osq并没有直接将这些任务的task struct形成队列结构，而是把per-CPU的mcs lock对象串联形成队列。Mcs lock中有cpu number，通过这些cpu number可以定位到指定cpu上的current thread，也就定位到了自旋的任务。
虽然都是自旋，但是自旋方式并不一样。Osq队列中的头部节点是持有osq锁的，只有该任务处于对rwsem的owner进行乐观自旋的状态（我们称之rwsem乐观自旋）。Osq队列中的其他节点都是自旋在自己的mcs lock上（我们称之mcs乐观自旋）。当头部的mcs lock释放掉后（结束rwsem乐观自旋），它会将mcs lock传递给下一个节点，从而让spinner队列上的任务一个个的按顺序进入rwsem的乐观自旋，从而避免了cache-line bouncing带来的性能开销。
cache-line bouncing的理解：为了以较低的成本大幅提升性能，现代CPU都有cache。cpu cache已经发展到了三级缓存结构。其中L1和L2cache为每一个核独有，L3则全部核共享。为了保证全部的核看到正确的内存数据，一个核在写入本身的L1 cache后，CPU会执行Cache一致性算法把对应的cacheline同步到其余核，这个过程并不很快。当多个cpu上频繁修改某个字段时，这个字段所在的cacheline被不停地同步到其它的核上，就像在核间弹来弹去，这个现象就叫作cache bouncing。
2. osq相关函数
（1）osq_wait_next
（2）osq_unlock
（3）smp_cond_load_relaxed
osq通过msc锁自旋是在smp_cond_load_relaxed实现的调用方式为：
smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
vcpu_is_preempted(node_cpu(node->prev)))
函数实现：
其中
cond_exprt = VAL || need_resched() || vcpu_is_preempted(node_cpu(node->prev))
VAL = &node->locked
cond_exprt 是结束自旋的条件，也就是说 &node->locked，need_resched()，vcpu_is_preempted(node_cpu(node->prev)任意一个值为True，就结束自旋，而函数的返回值是VAL，即&node->locked
（4）osq_lock
五、rwsem read
因为有osq的支持，可以把read分为3种状态
快速路径
中速路径
慢速路径
1. read持锁快速路径
2. read持锁中速路径
（1）nonspinable
两个nonspinable宏
RWSEM_RD_NONSPINNABLE - Readers cannot spin on this lock.
RWSEM_WR_NONSPINNABLE - Writers cannot spin on this lock.
RWSEM_NONSPINNABLE (RWSEM_RD_NONSPINNABLE | RWSEM_WR_NONSPINNABLE)
设置RWSEM_NONSPINNABLE的函数
调用rwsem_set_nonspinnable有两个地方
在rwsem_optimistic_spin 方法中，如果自旋的是writer并且持锁的是reader，等待的时间超过自旋的timeout，则会设置 nonspinnable
rwsem_read_trylock 时，如果reader过多溢出了，也会调用 rwsem_set_nonspinnable，设置nonspinnable
清除RWSEM_WR_NONSPINNABLE的函数
调用clear_wr_nonspinnable,清除 RWSEM_WR_NONSPINNABLE有两个地方
1.在down_read慢速路径中，如果没有持锁者了，可以把这个标记清除，因为之前writer spin出现超时后，设置过nonspinnable
2.在__up_read 释放锁之后，如果没有持锁者且有waiter，可以把这个标记清除
因为nonspinnable 标记是设置在owner 地址的后3位，那么在write持锁设置owner时，就会把这个标记清除掉了。也就是说，如果之前设置了RWSEM_NONSPINNABLE，只要writer没有持锁成功过，RWSEM_RD_NONSPINNABLE都不应该被清除。
NONSPINNABLE 影响：
1.在读/写的乐观自旋流程中，如果判断到owner设置了 对应的NONSPINNABLE 标记，就不会进入乐观自旋了，乐观自旋有很大概率会把锁偷走
2.在进入乐观自旋之前没有设置NONSPINNABLE，进入后被设置了，也会结束乐观自旋
（2）rwsem_mark_wake
rwsem_mark_wake 用于唤醒Wait_list中的一组任务
wait_list排序：读/读/写/写/读/读
因为rw锁的特点，在wait_list中会存在一组顺序杂乱的读/写者，如果可以唤醒读者，或许可以唤醒队列中所有的读者，尽管这些读者的顺序不一定连续。所以，rwsem专门实现了一个函数用于唤醒队列中任务的操作。
与rwsem_mark_wake相关的宏
wait_list中，每个wait的状态，读者/写者
wake type，表示调用rwsem_mark_wake时，期望唤醒哪些任务
RWSEM_WAKE_READ_OWNED 表示reader spin成功后的一种状态
读者在等待队列种的状态
文章篇幅过长，下文继续讲解
