读写信号量
一、前言
最近参加了很多D状态导致卡顿问题的分析，都是在等待内核中的某一把mutex或者rwsem锁。mutex比较简单一些，只会有一个线程持锁，其它线程睡眠等待。而rwsem就稍显复杂，会存在多个线程同时持锁，导致等待的线程睡眠很长时间的情况。并且，我们对rwsem锁传递的优化，只能是writer持锁才能传递，reader持锁时传递不了。为了弄明白其中的原理，决定认真看一下代码。
二、锁的作用
Linux作为典型的多用户、多任务、抢占式内核调度的操作系统，在内核层面涉及到各种软硬件中断、多线程、抢占式内核调度、多处理器SMP架构等，内核在完成自己工作的时候需要处理各种条件下资源抢占的冲突问题。因此linux内核提供了semaphore、spinlock、mutex等锁机制，以及rcu、atomic等同步机制来解决这些问题。然而每种机制都有不同的实现原理以及适用场景，在性能方面也是会存在一定差异，因此对于不同场景下的问题我们能选择最适用的机制才是最好的。
1. mutex锁，也叫互斥锁。特点是：
a 某个时刻，只能有一个线程持锁进入临界区
2. spinlock，也叫自旋锁。特点是：
a 某个时刻，只能有一个线程持锁进入临界区
b 线程在持锁失败后，不进入睡眠状态而是原地自旋，等待持锁成功
因为线程睡眠、唤醒时都需要进行调度，这部分线程上、下文的切换也是性能开销。而spinlock则在持锁失败后，不会进行睡眠，少了这一部分的开销。但是，spinlock不适合保护很大的临界区，因为在持锁后会关闭抢占或中断，如果持锁时间过长，持锁线程以及持锁未成功进行自旋线程所在cpu会出现调度不及时带来的性能问题。
另外，在软硬中断上下文，是不允许睡眠的，所以mutex不能在这里使用，需要使用spinlock。
3. 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，那么就会进入阻塞状态并插入等待队列的尾部。
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有两个地方
1. 在rwsem_optimistic_spin 方法中，如果自旋的是writer并且持锁的是reader，等待的时间超过自旋的timeout，则会设置 nonspinnable
2. 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成功后的一种状态
读者在等待队列种的状态
（3）乐观自旋
① rwsem_can_spin_on_owner
rwsem_can_spin_on_owner用于判断当前任务是否可以进行乐观自旋
② rwsem_spin_on_owner
rwsem_spin_on_owner 是rwsem自旋实现的地方，从字面就可以看出，它会不停的去查询owner的状态，实现自旋
与乐观自旋owner state相关的状态
乐观自旋失败总结：
1.writer持锁
a.reader/writer乐观自旋失败原因：need_resched() || writer不在cpu上 || nonspinable
2.reader持锁
a.reader乐观自旋失败原因：nonspinable || (handoff标记 && （need_resched() || rt_task ))
b.writer乐观自旋失败原因：nonspinable || need_reshced() || timeout || rt_task
Writer乐观自旋尝试持锁
Reader乐观自旋尝试持锁
乐观自旋成功后：
3. read持锁慢速路径
4. read持锁总结
1.reader持锁前，没有其它人持锁，快速路径中持锁成功
2.reader持锁前，有reader持锁，但是没有writer等待，没有设置handoff标记，reader持锁数量没有溢出，快速路径中持锁成功
3.reader持锁前，有reader持锁，但是有writer等待
a.乐观自旋中，拿到了osq锁，进入乐观自旋，没有设置handoff标记，则持锁成功
b.乐观自旋失败，走慢速路径，睡眠等待被唤醒
4.reader持锁前，有writer持锁，乐观自旋失败后，走慢速路径，睡眠等待被唤醒
5. read释放锁
六、rwsem write
同read一样，write持锁也有3种状态
快速路径
中速路径
慢速路径
1. write持锁快速路径
write持锁快速路径比较简单，直接调用
atomic_long_try_cmpxchg_acquire(&sem->count, &tmp, RWSEM_WRITER_LOCKED)
只有当锁没有人持有时，才能成功
2. write持锁中速路径
与reader持锁的实现是一模一样的
3. write持锁慢速路径
（1）handoff
设置RWSEM_FLAG_HANDOFF 的作用：防止处于wait list第一个等待者饿死
因为加入了osq乐观自旋，存在一种情况，任务持锁失败，被挂入wait list中的第一个，同时也存在处于rwsem乐观自旋状态的任务，owner释放了锁，那么该锁大概率会被乐观自旋的任务抢走，如果持续的有乐观自旋状态任务来抢锁，那么wait list中的任务可能会被饿死。
1.rwsem_try_read_lock_unqueued/rwsem_try_write_lock_unqueued时会直接返回
2.reader持锁情况下，另外的reader再来持锁时，也不会成功
3.rwsem_down_read_slowpath 时，如果wait list空的，且是writer持锁或者设置了handoff则不能获得锁(正常是可以的，因为是读者持锁)
4.rwsem_try_write_lock 时，可以直接返回
设置RWSEM_FLAG_HANDOFF的地方
1.在rwsem_down_write_slowpath 慢速路径被唤醒后，如果满足这个条件(wstate == WRITER_FIRST) && (rt_task(current) || time_after(jiffies, waiter.timeout)，会将wstate 设置成WRITER_HANDOFF，然后调用rwsem_try_write_lock去拿锁，若锁还有人持有，则将RWSEM_FLAG_HANDOFF 标志置上，这样在其它任务正常的路径上拿锁就不会成功了。
2.在rwsem_mark_wake 流程中，如果是writer持锁，wait list第一个等待者是reader且超过timeout的时间没有拿到锁，也会把RWSEM_FLAG_HANDOFF 标志置上。
1.如果已经设置了handoff 且 wstate == WRITER_NOT_FIRST，则直接返回，在rwsem_mark_wake 里，如果reader等的时间太长，会设置handoff bit，不能让reader饿死。
2. 锁被持有的情况，如果设置了handeroff 或者不是WRITER_HANDOFF，则直接return false。否则把handoff标置设上，然后也会return false，第二次进来的时候，如果没有人持锁，这个线程就能持锁成功，这是为了避免在这个线程被唤醒后，被spiner把锁给偷了2次。
（2）慢速路径过程
1. 如果设置了WRITER_HANDOFF，则直接调用rwsem_spin_on_owner，如果返回的是无人持锁，则直接去拿锁，就不需要睡眠了。
2. 如果WRITER_HANDOFF 已经设置了，就不走后面的流程了，因为后面的流程也是为了设置handoff标记。
3. 是第一个waiter 且 是rt task 或者 超时了，会设置writer_handoff标记，这个标记可以让这个线程不会被spiner把锁再次偷走为什么要判断这个，设想一个场景，假设该writer从睡眠被唤醒，说明锁被释放后把它唤醒了，它本来可以去拿到锁，但是失败了，说明被spiner偷走了为了防止这个现象再次发生，就要设置handoff 标记，让其它人偷不了锁。
4. write释放锁
七、总结
文中所讲的有很大一部分都是源码，很细节的东西。如果大家看的云里雾里的，不要怀疑自己。尽管文档是我一字一句写出来的，并且反复回味了非常多遍，但是我在碰到很细节的问题时，仍然要回头再去看文档的描述才能弄清楚原因。对于读写信号量，我的建议如下：
1.只想了解个大概。可以看下rwsem的结构，osq的概念，搞懂reader/writer持锁后，又有reader/writer进来持锁以及有乐观自旋任务的情况下，会有哪些可能即可。
2.想深入弄懂原理。对着代码好好研究一番。rwsem还是会复杂一些，弄清除了这个，再看其它锁的实现时，应该会更得心应手了。
参考文献：
1.https://zhuanlan.zhihu.com/p/511643725
2.kernel 5.10源码