深入講解讀寫信號量（上）
一、前言
最近參加了很多D狀態(tài)導(dǎo)致卡頓問題的分析，都是在等待內(nèi)核中的某一把mutex或者rwsem鎖。mutex比較簡單一些，只會有一個線程持鎖，其它線程睡眠等待。而rwsem就稍顯復(fù)雜，會存在多個線程同時持鎖，導(dǎo)致等待的線程睡眠很長時間的情況。并且，我們對rwsem鎖傳遞的優(yōu)化，只能是writer持鎖才能傳遞，reader持鎖時傳遞不了。為了弄明白其中的原理，決定認(rèn)真看一下代碼。
二、鎖的作用
Linux作為典型的多用戶、多任務(wù)、搶占式內(nèi)核調(diào)度的操作系統(tǒng)，在內(nèi)核層面涉及到各種軟硬件中斷、多線程、搶占式內(nèi)核調(diào)度、多處理器SMP架構(gòu)等，內(nèi)核在完成自己工作的時候需要處理各種條件下資源搶占的沖突問題。因此linux內(nèi)核提供了semaphore、spinlock、mutex等鎖機制，以及rcu、atomic等同步機制來解決這些問題。然而每種機制都有不同的實現(xiàn)原理以及適用場景，在性能方面也是會存在一定差異，因此對于不同場景下的問題我們能選擇最適用的機制才是最好的。
mutex鎖，也叫互斥鎖。特點是：
a 某個時刻，只能有一個線程持鎖進入臨界區(qū)
b 線程在持鎖失敗后，進入睡眠狀態(tài)
spinlock，也叫自旋鎖。特點是：
a 某個時刻，只能有一個線程持鎖進入臨界區(qū)
b 線程在持鎖失敗后，不進入睡眠狀態(tài)而是原地自旋，等待持鎖成功
因為線程睡眠、喚醒時都需要進行調(diào)度，這部分線程上、下文的切換也是性能開銷。而spinlock則在持鎖失敗后，不會進行睡眠，少了這一部分的開銷。但是，spinlock不適合保護很大的臨界區(qū)，因為在持鎖后會關(guān)閉搶占或中斷，如果持鎖時間過長，持鎖線程以及持鎖未成功進行自旋線程所在cpu會出現(xiàn)調(diào)度不及時帶來的性能問題。
另外，在軟硬中斷上下文，是不允許睡眠的，所以mutex不能在這里使用，需要使用spinlock。
rwsem，讀寫信號量，和mutex很像。保護臨界區(qū)的原因是其同時有被修改和讀的可能，如果這個資源只是被讀永遠(yuǎn)不會修改，那也不需要保護。有這樣一個場景，被保護的臨界區(qū)大部分情況下都是讀取操作，少數(shù)情況會被修改。如果使用mutex，假設(shè)此刻一個讀者進入臨界區(qū)，另外一個線程也是讀取操作，那它因為沒有拿到鎖而去休眠，但實際上它只是想去讀，并不會做修改，按理是可以進去的。這個時候rwsem的作用就體現(xiàn)出來了，所以它的特點是：
a 同一時刻允許多個讀者（reader）獲得鎖進入臨界區(qū)
b 同一時刻只允許一個寫者（writer）獲得鎖進入臨界區(qū)，也就是寫者與寫者互斥
c 同一時刻不存在寫著和讀者同時獲取鎖進入臨界區(qū)，也就是讀者與寫者互斥
d 持鎖失敗后，進入睡眠狀態(tài)
三、rwsem
1. rwsem簡介
以下是一個簡單的rwsem工作示意圖：
傳統(tǒng)的rwsem只需要一個count計數(shù)和一個等待隊列就可以了，等待隊列中是一個個阻塞的線程，thread owner(s)當(dāng)前持有rwsem，當(dāng)它(們)離開臨界區(qū)釋放鎖的時候，如果沒有持鎖的線程了，會喚醒等待隊列中第一個線程（top waiter）或者一組reader，這時候top waiter會去競爭持鎖，如果成功，那么從等待隊列中摘下，成為owner。如果失敗，繼續(xù)保持阻塞狀態(tài)，等待owner釋放鎖的時候喚醒它。在owner task持鎖過程中，如果有新的任務(wù)來競爭rwsem，那么就會進入阻塞狀態(tài)并插入等待隊列的尾部。
2. rwsem數(shù)據(jù)結(jié)構(gòu)
以下代碼都是基于kenerl 5.10版本
（1）count
count用于描述rwsem的一些狀態(tài)，在64位的系統(tǒng)中，各個bit定義如下：
與count值相關(guān)的宏
這里要注意RWSEM_READ_FAILED_MASK，用于reader是否可以持鎖的判斷，其中有一位是RWSEM_FLAG_WAITERS。有一個場景，假設(shè)當(dāng)前持鎖的是reader，來了一個writer，持鎖失敗進入等待隊列，那么RWSEM_FLAG_WAITERS為1。此時又有一個reader來持鎖，在快速路徑中根據(jù)這個判斷，持鎖也會失敗，進入慢速路徑，再根據(jù)一些條件進行判斷是否可以持鎖。所以，reader已經(jīng)持鎖的情況下，其它的reader也不是無條件可以馬上持鎖的，后續(xù)會講。
（2）owner
owner成員有兩個作用：
1.記錄rwsem被哪個Task持有。只有writer持鎖時，這個owner才能正確表示持有者，而可能同時存在很多個reader，所以reader持鎖時，owner不能正確表示持鎖者，這也是鎖傳遞不能對reader進行傳遞的原因。
2.因為task_struct地址是L1_CACHE_BYTES(cache line大小典型值為32byte)對齊的，所以其最低的3位是恒等于0的，這3位就可以用于描述一些狀態(tài)信息，具體有：
與owner 狀態(tài)相關(guān)的宏
（3）osq
struct optimistic_spin_queue osq，在配置了CONFIG_RWSEM_SPIN_ON_OWNER時，rwsem就支持樂觀自旋機制，osq成員就是樂觀自旋需要持有的MCS鎖隊列。數(shù)據(jù)結(jié)構(gòu)optimistic_spin_queue只有一個成員tail，如果等于0，那就是一個空隊列，說明沒有樂觀自旋的任務(wù)。否則，tail指向一個節(jié)點是optimistic_spin_node對象隊列的尾部(tail并不是一個指針，它是一個cpu number，optimistic_spin_node對象是per cpu的，有了cpu number就可以定位到其optimistic_spin_node對象)。osq樂觀自旋原理后面會講。
（4）wait_list、wait_lock
rwsem是睡眠鎖，當(dāng)取鎖失敗并且不在樂觀自旋狀態(tài)時需要掛入wait_list等待隊列，等待owner釋放鎖。
wait_lock是一個spin_lock鎖，用于保護wait_list
四、osq
1. osq簡介
和osq相關(guān)的兩個結(jié)構(gòu)體
osq對象結(jié)構(gòu)體，從其內(nèi)部變量next、prev可以看出，osq是一個雙向鏈表locked 表示這個節(jié)點是否獲得mcs鎖，為1表示持有。
cpu 可以獲得具體的節(jié)點，因為optimistic_spin_node 是percpu的，每個cpu上一個節(jié)點。
osq工作示意圖
字如其名，Optimistic spin queue就是樂觀自旋隊列的意思，也就是形成一組處于自旋狀態(tài)的任務(wù)隊列。和等待隊列不一樣，這個隊列中的任務(wù)都是當(dāng)前正在執(zhí)行的務(wù)。Osq并沒有直接將這些任務(wù)的task struct形成隊列結(jié)構(gòu)，而是把per-CPU的mcs lock對象串聯(lián)形成隊列。Mcs lock中有cpu number，通過這些cpu number可以定位到指定cpu上的current thread，也就定位到了自旋的任務(wù)。
雖然都是自旋，但是自旋方式并不一樣。Osq隊列中的頭部節(jié)點是持有osq鎖的，只有該任務(wù)處于對rwsem的owner進行樂觀自旋的狀態(tài)（我們稱之rwsem樂觀自旋）。Osq隊列中的其他節(jié)點都是自旋在自己的mcs lock上（我們稱之mcs樂觀自旋）。當(dāng)頭部的mcs lock釋放掉后（結(jié)束rwsem樂觀自旋），它會將mcs lock傳遞給下一個節(jié)點，從而讓spinner隊列上的任務(wù)一個個的按順序進入rwsem的樂觀自旋，從而避免了cache-line bouncing帶來的性能開銷。
cache-line bouncing的理解：為了以較低的成本大幅提升性能，現(xiàn)代CPU都有cache。cpu cache已經(jīng)發(fā)展到了三級緩存結(jié)構(gòu)。其中L1和L2cache為每一個核獨有，L3則全部核共享。為了保證全部的核看到正確的內(nèi)存數(shù)據(jù)，一個核在寫入本身的L1 cache后，CPU會執(zhí)行Cache一致性算法把對應(yīng)的cacheline同步到其余核，這個過程并不很快。當(dāng)多個cpu上頻繁修改某個字段時，這個字段所在的cacheline被不停地同步到其它的核上，就像在核間彈來彈去，這個現(xiàn)象就叫作cache bouncing。
2. osq相關(guān)函數(shù)
（1）osq_wait_next
（2）osq_unlock
（3）smp_cond_load_relaxed
osq通過msc鎖自旋是在smp_cond_load_relaxed實現(xiàn)的調(diào)用方式為：
smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
vcpu_is_preempted(node_cpu(node->prev)))
函數(shù)實現(xiàn)：
其中
cond_exprt = VAL || need_resched() || vcpu_is_preempted(node_cpu(node->prev))
VAL = &node->locked
cond_exprt 是結(jié)束自旋的條件，也就是說 &node->locked，need_resched()，vcpu_is_preempted(node_cpu(node->prev)任意一個值為True，就結(jié)束自旋，而函數(shù)的返回值是VAL，即&node->locked
（4）osq_lock
五、rwsem read
因為有osq的支持，可以把read分為3種狀態(tài)
快速路徑
中速路徑
慢速路徑
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)
設(shè)置RWSEM_NONSPINNABLE的函數(shù)
調(diào)用rwsem_set_nonspinnable有兩個地方
在rwsem_optimistic_spin 方法中，如果自旋的是writer并且持鎖的是reader，等待的時間超過自旋的timeout，則會設(shè)置 nonspinnable
rwsem_read_trylock 時，如果reader過多溢出了，也會調(diào)用 rwsem_set_nonspinnable，設(shè)置nonspinnable
清除RWSEM_WR_NONSPINNABLE的函數(shù)
調(diào)用clear_wr_nonspinnable,清除 RWSEM_WR_NONSPINNABLE有兩個地方
1.在down_read慢速路徑中，如果沒有持鎖者了，可以把這個標(biāo)記清除，因為之前writer spin出現(xiàn)超時后，設(shè)置過nonspinnable
2.在__up_read 釋放鎖之后，如果沒有持鎖者且有waiter，可以把這個標(biāo)記清除
因為nonspinnable 標(biāo)記是設(shè)置在owner 地址的后3位，那么在write持鎖設(shè)置owner時，就會把這個標(biāo)記清除掉了。也就是說，如果之前設(shè)置了RWSEM_NONSPINNABLE，只要writer沒有持鎖成功過，RWSEM_RD_NONSPINNABLE都不應(yīng)該被清除。
NONSPINNABLE 影響：
1.在讀/寫的樂觀自旋流程中，如果判斷到owner設(shè)置了 對應(yīng)的NONSPINNABLE 標(biāo)記，就不會進入樂觀自旋了，樂觀自旋有很大概率會把鎖偷走
2.在進入樂觀自旋之前沒有設(shè)置NONSPINNABLE，進入后被設(shè)置了，也會結(jié)束樂觀自旋
（2）rwsem_mark_wake
rwsem_mark_wake 用于喚醒Wait_list中的一組任務(wù)
wait_list排序：讀/讀/寫/寫/讀/讀
因為rw鎖的特點，在wait_list中會存在一組順序雜亂的讀/寫者，如果可以喚醒讀者，或許可以喚醒隊列中所有的讀者，盡管這些讀者的順序不一定連續(xù)。所以，rwsem專門實現(xiàn)了一個函數(shù)用于喚醒隊列中任務(wù)的操作。
與rwsem_mark_wake相關(guān)的宏
wait_list中，每個wait的狀態(tài)，讀者/寫者
wake type，表示調(diào)用rwsem_mark_wake時，期望喚醒哪些任務(wù)
RWSEM_WAKE_READ_OWNED 表示reader spin成功后的一種狀態(tài)
讀者在等待隊列種的狀態(tài)
文章篇幅過長，下文繼續(xù)講解
原文作者：內(nèi)核工匠
