一、Linux為何會(huì)引入讀寫鎖？

除了mutex，在linux內(nèi)核中，還有一個(gè)經(jīng)常用到的睡眠鎖就是rw semaphore（后文簡稱為rwsem），它到底和mutex有什么不同呢？為何會(huì)有rw semaphore？無他，僅僅是為了增加內(nèi)核的并發(fā)，從而增加性能而已。Mutex嚴(yán)格的限制只有一個(gè)thread可以進(jìn)入臨界區(qū)，但是實(shí)際應(yīng)用中，有些場(chǎng)景對(duì)共享資源的訪問可以嚴(yán)格區(qū)分讀和寫的，并且是讀多寫少，這時(shí)候，其實(shí)多個(gè)讀的thread同時(shí)進(jìn)入臨界區(qū)是OK的，使用mutex則限制一個(gè)線程進(jìn)入臨界區(qū)，從而導(dǎo)致性能的下降。

本文會(huì)描述linux5.15.81中讀寫鎖的數(shù)據(jù)結(jié)構(gòu)和邏輯過程。

二、如何抽象讀寫鎖的數(shù)據(jù)結(jié)構(gòu)？

下圖可以抽象rwsem相關(guān)的數(shù)據(jù)結(jié)構(gòu)：

一個(gè)rwsem對(duì)象需要記錄兩種數(shù)據(jù)：

1、讀寫鎖的狀態(tài)信息

2、和該讀寫鎖相關(guān)的任務(wù)信息

我們先看看讀寫鎖的狀態(tài)。讀寫鎖狀態(tài)字需要分別記錄讀鎖和寫鎖的狀態(tài)：由于多個(gè)reader可以同時(shí)處于臨界區(qū)，所以對(duì)于reader-owned的場(chǎng)景，讀鎖狀態(tài)變成了一個(gè)counter，來記錄臨界區(qū)內(nèi)reader的數(shù)量，counter等于0表示讀鎖為空鎖狀態(tài)。對(duì)于writer，其行為和互斥鎖一致，因此其寫鎖狀態(tài)和mutex一樣，仍然使用一個(gè)bit表示。

和讀寫相關(guān)的任務(wù)有兩類，一類是已經(jīng)持鎖的線程（即在臨界區(qū)的線程），另外一類是無法持鎖而需要等待的任務(wù)。對(duì)于writer持鎖情況，由于排他性，我們很清楚的知道是哪個(gè)task持鎖，那么一個(gè)task struct指針就足夠了記錄owner了。然而對(duì)于讀側(cè)可以多個(gè)reader進(jìn)入臨界區(qū)，那么owner們需要組成一個(gè)隊(duì)列才可以記錄每一個(gè)臨界區(qū)的reader。

不過在實(shí)際的rwsem實(shí)現(xiàn)中，由于跟蹤owner們開銷比較大，因此也是用一個(gè)task struct指針指向其一。具體linux代碼是這樣處理的：reader進(jìn)入的時(shí)候會(huì)設(shè)置owner task，但是離開讀臨界區(qū)并不會(huì)清除task指針。這樣，實(shí)際上對(duì)于讀，owner task應(yīng)該表示該任務(wù)曾經(jīng)擁有該鎖，并不表示是目前持鎖的owner task，也有可能已經(jīng)離開臨界區(qū)，甚至該任務(wù)已經(jīng)銷毀。

如果持鎖失敗，無法進(jìn)入臨界區(qū)，我們有兩種選擇：

1、樂觀自旋

2、掛入等待隊(duì)列

兩種選擇各有優(yōu)點(diǎn)和缺點(diǎn)，總結(jié)如下：

在5.15的內(nèi)核中，只有在write持鎖路徑上有樂觀自旋的操作，reader路徑?jīng)]有，只有偷鎖的操作。當(dāng)樂觀自旋失敗后就會(huì)掛入等待隊(duì)列，阻塞當(dāng)前線程。（樂觀自旋功能有一個(gè)很有意思的發(fā)展過程，從開始支持writer的樂觀自旋，到支持全場(chǎng)景的樂觀自旋，然后又回到最初，有興趣可以查閱內(nèi)核的patch了解詳情）

在了解了rwsem的基本概念之后，我們一起來看看struct rw_semaphore數(shù)據(jù)結(jié)構(gòu)，其成員描述如下：

由于是sleep lock，我們需要把等待的任務(wù)掛入隊(duì)列。在內(nèi)核中，struct rwsem_waiter用來抽象等待rwsem的任務(wù)，其成員描述如下：

三、Rwsem外部接口API為何？

Rwsem模塊的外部接口API如下：

四、嘗試獲取讀鎖

和down_read不一樣，down_read_trylock只是嘗試獲取讀鎖，如果成功，那么自然是好的，直接返回1，如果失敗，也不會(huì)阻塞，只是返回0就可以了。代碼主邏輯在__down_read_trylock函數(shù)中，如下：

A、tmp的初始值設(shè)定為RWSEM_UNLOCKED_VALUE（0值），因此第一次循環(huán)是為當(dāng)前是空鎖而做的優(yōu)化：如果當(dāng)前的sem->count等于0，那么給sem->count賦值RWSEM_READER_BIAS，標(biāo)記持鎖成功，然后設(shè)定owner返回1即可。

B、如果快速獲取空鎖不成功，這時(shí)候tmp已經(jīng)賦值（等于sem->count），不再是0值了。通過對(duì)當(dāng)前sem->count的值可以判斷是否是可以進(jìn)入臨界區(qū)。持讀鎖失敗的情況包括：

如果判斷可以進(jìn)入讀臨界區(qū)（臨界區(qū)僅有reader并且沒有writer等待的場(chǎng)景），那么重新進(jìn)入循環(huán)，如果sem->count保持不變，那么可以持鎖成功，給進(jìn)入臨界區(qū)的reader數(shù)目加一，并設(shè)置owner task和reader持鎖標(biāo)記（non-spinnable比特保持不變）。如果這期間有其他線程插入修改了count值，那么需要再次判斷是否能持讀鎖，重復(fù)上面的循環(huán)。如果判斷不可以進(jìn)入臨界區(qū)，退出循環(huán)，持鎖失敗。

五、獲取讀鎖

Reader獲取讀鎖的代碼主要在__down_read_common函數(shù)中，如下：

1、快速路徑

rwsem_read_trylock是快速路徑，代碼如下：

A、reader直接會(huì)給sem->count加RWSEM_READER_BIAS來增加讀臨界區(qū)的線程個(gè)數(shù)，當(dāng)然這有可能失敗，那么就進(jìn)入慢速路徑（需要回退錯(cuò)誤增加讀臨界區(qū)線程數(shù)量）。如果恰好能夠進(jìn)入臨界區(qū)，那么就直接設(shè)定owner返回即可。注意：這里*cntp保存了atomic add之后的新值。rwsem_down_read_slowpath會(huì)使用這個(gè)新值作為參數(shù)。

B、當(dāng)reader的數(shù)量過多（以至于都溢出了）的時(shí)候，需要禁止樂觀自旋。

C、這里是持鎖成功的路徑。RWSEM_READ_FAILED_MASK上一節(jié)已經(jīng)解釋，這里不再贅述。這里需要注意的是rwsem_set_reader_owned函數(shù)中flag的設(shè)定，由于reader進(jìn)入臨界區(qū)，因此RWSEM_READER_OWNED也需要設(shè)定。RWSEM_RD_NONSPINNABLE標(biāo)記保持不變。

在快速路徑中，有兩種常見的情況會(huì)持鎖成功：一種是空鎖，另外一種是沒有任何waiter等待的純r(jià)eader并發(fā)。

2、慢速路徑

如果快速路徑持鎖失敗，那么進(jìn)入慢速路徑。慢速路徑代碼比較長，我們分段解析。首先是防止等待隊(duì)列中waiter任務(wù)餓死的代碼：

如果當(dāng)前的鎖被reader持有（至少有一個(gè)reader在臨界區(qū)），那么不再樂觀偷鎖而是直接進(jìn)行掛等待隊(duì)列的操作。為何怎么做呢？因?yàn)樾枰陴I死waiter和reader吞吐量上進(jìn)行平衡。一方面，連續(xù)的reader持續(xù)偷鎖的話會(huì)餓死等待隊(duì)列上的任務(wù)。另外，在喚醒路徑上，被喚醒的top reader會(huì)順便將隊(duì)列中的若干（不大于256個(gè)）reader也同時(shí)喚醒，以便增加rwsem的吞吐量。所以這里的reader直接掛入隊(duì)列，累計(jì)多個(gè)reader以便可以批量喚醒。

Reader偷鎖的場(chǎng)景主要發(fā)生在喚醒top waiter的過程中，這時(shí)候臨界區(qū)沒有線程，被喚醒的reader或者writer也沒有持鎖（writer需要被調(diào)度到CPU上執(zhí)行之后才會(huì)試圖持鎖，高負(fù)載的場(chǎng)景下，鎖被偷的概率比較大，reader是喚醒后立刻持鎖，被偷的幾率小一點(diǎn)）。具體樂觀偷鎖（optimistic lock stealing）的代碼如下：

A、所謂偷鎖就是不樂觀自旋（要有排隊(duì)），不管先來后到，直接獲取鎖。允許偷鎖的場(chǎng)景是這樣的：臨界區(qū)沒有writer持鎖，也沒有設(shè)置handoff，正在喚醒top waiter的過程中，并且有任務(wù)在等待隊(duì)列的情況。這時(shí)候進(jìn)入慢速路徑的reader可以先于top waiter喚醒之前把鎖偷走。需要特別說明的是：這時(shí)候reader counter已經(jīng)加一，還是盡量讓reader偷鎖成功，否則還需要回退。

B、當(dāng)前線程獲得了讀鎖，需要設(shè)置owner，畢竟它是臨界區(qū)的新客

C、如果偷鎖成功并且它是臨界區(qū)第一個(gè)reader，那么它還會(huì)把等待隊(duì)列中的reader都喚醒（前提是top waiter不是writer），帶領(lǐng)大家一起往前沖（這里會(huì)打破FIFO的順序，懲罰了隊(duì)列中的writer）。具體是通過rwsem_mark_wake來標(biāo)記喚醒的reader，然后通過wake_up_q將reader喚醒并進(jìn)入讀臨界區(qū)。為了減低對(duì)等待中的writer線程的影響，這時(shí)候?qū)eader的并發(fā)是受限的，最多可以喚醒MAX_READERS_WAKEUP個(gè)reader。

如果偷鎖不成功，當(dāng)前的reader還是需要進(jìn)入阻塞狀態(tài)：

A、準(zhǔn)備好掛入等待隊(duì)列的rwsem waiter數(shù)據(jù)，需要特別說明的是這里的timeout時(shí)間：目前手機(jī)平臺(tái)的HZ設(shè)置的是250，也就是說在觸發(fā)handoff機(jī)制之前waiter需要至少在隊(duì)列中等待一個(gè)tick（4ms）的時(shí)間。這里的timeout是指handoff timeout，為了防止偷鎖或者自旋導(dǎo)致等待隊(duì)列中的top waiter有一個(gè)長時(shí)間的持鎖延遲。在timeout時(shí)間內(nèi)，樂觀偷鎖或者自旋可以順利進(jìn)行，但是一旦超時(shí)就會(huì)設(shè)定handoff標(biāo)記，樂觀偷鎖或者自旋被禁止，鎖的所有權(quán)需要遞交給等待隊(duì)列中的top waiter。

B、如果目前等待隊(duì)列為空，那么要做一些額外的處理。例如入隊(duì)之前肯定給安排上RWSEM_FLAG_WAITERS這個(gè)標(biāo)記。

C、當(dāng)然，在入隊(duì)之前還要垂死掙扎一下（等待隊(duì)列為空的時(shí)候邏輯簡單一些，不需要喚醒隊(duì)列上的wait），看看是不是當(dāng)前有機(jī)可乘，如果是這樣，那么就順勢(shì)而為，直接持鎖成功，而且counter都已經(jīng)準(zhǔn)備好了，前面已經(jīng)加一了。

D、等待隊(duì)列非空的時(shí)候，邏輯稍微負(fù)載一點(diǎn)。調(diào)用rwsem_add_waiter函數(shù)即可以把當(dāng)前任務(wù)掛入等待隊(duì)列尾部。這時(shí)候也需要把之前武斷增加的counter給修正回來了（adjustment初始化為-RWSEM_READER_BIAS）。如果是第一個(gè)waiter，也順便設(shè)置了RWSEM_FLAG_WAITERS標(biāo)記。

在當(dāng)前線程進(jìn)入阻塞之前，我們需要進(jìn)行試圖持鎖的動(dòng)作（上面是空隊(duì)列場(chǎng)景檢查，這里的邏輯稍微復(fù)雜一點(diǎn)，由于已經(jīng)入隊(duì)，這里需要調(diào)用rwsem_mark_wake函數(shù)來完成阻塞后喚醒的動(dòng)作），畢竟這時(shí)候可能恰好owner離開臨界區(qū)，變成空鎖。

A、如果這時(shí)候發(fā)現(xiàn)鎖的owner恰好都離開了臨界區(qū)，那么我們是需要執(zhí)行喚醒top waiter操作的，喚醒之前需要清除禁止樂觀自旋的標(biāo)記，畢竟目前臨界區(qū)沒有任何線程。

B、除了上面說的場(chǎng)景需要喚醒，在reader持鎖并且我們是隊(duì)列中的第一個(gè)waiter的時(shí)候，也需要喚醒的動(dòng)作（喚醒自己）。

阻塞部分的代碼邏輯如下：

A、在rwsem_mark_wake函數(shù)中我們會(huì)喚醒reader并將其等待對(duì)象的task成員（waiter.task）設(shè)置為NULL。因此，這里如果發(fā)現(xiàn)waiter.task等于NULL，那么說明是該線程被正常喚醒，那么從阻塞狀態(tài)返回，持鎖成功。

B、如果在該線程阻塞的時(shí)候，有其他任務(wù)發(fā)送信號(hào)給該線程，那么就持鎖失敗退出。如果已經(jīng)被喚醒，同時(shí)又收到信號(hào)，這時(shí)候需要首先完成喚醒，持鎖成功，然后在其他的合適點(diǎn)再處理該信號(hào)。當(dāng)然，大部分的rwsem都是D狀態(tài)，也就不需要處理信號(hào)了。

C、進(jìn)入阻塞狀態(tài)，讓調(diào)度器選擇next task

六、釋放讀鎖

釋放讀鎖的代碼邏輯主要在__up_read函數(shù)中，如下：

需要強(qiáng)調(diào)的是：這里僅僅是減去了讀臨界區(qū)的counter計(jì)數(shù)，并沒有清除owner中的task pointer。此外，當(dāng)?shù)却?duì)列有waiter并且沒有writer或者reader在臨界區(qū)的時(shí)候，我們會(huì)調(diào)用rwsem_wake來喚醒等待隊(duì)列的線程。因?yàn)榕R界區(qū)已經(jīng)沒有線程，所以需要清除nonspinable標(biāo)記。喚醒的動(dòng)作主要是通過rwsem_mark_wake和wake_up_q來完成的，wake_up_q比較簡單，我們就不贅述了，主要看看rwsem_mark_wake的邏輯。

我們首先給出wake type的解釋：

在RWSEM_WAKE_READERS場(chǎng)景中，多個(gè)reader被喚醒，并且當(dāng)前很可能是空鎖狀態(tài)，為了防止writer搶鎖，因此會(huì)先讓top waiter持有讀鎖，然后慢慢處理后續(xù)。RWSEM_WAKE_READ_OWNED則沒有這個(gè)顧慮，因?yàn)閱拘颜咭呀?jīng)持有讀鎖。

在釋放讀鎖的場(chǎng)景中，rwsem_mark_wake使用的是RWSEM_WAKE_ANY參數(shù)，具體的代碼如下：

這段代碼是處理top waiter是writer的邏輯。這時(shí)候，如果wake type是RWSEM_WAKE_ANY，即不關(guān)心喚醒的是reader還是writer，只要喚醒等待隊(duì)列頭部的waiter就好。如果top waiter是writer，我們只需要將這個(gè)writer喚醒即可，不需要修改鎖的狀態(tài)，出隊(duì)等操作，這些都是在喚醒之后完成。如果wake type是其他兩種類型（都是喚醒reader的），那么就直接返回。也就是說在rwsem_mark_wake想要喚醒reader的場(chǎng)景中，如果top waiter是writer，那么將不會(huì)喚醒任何reader線程。如果top waiter是reader的話，那么基本上是需要喚醒一組reader了。

A、執(zhí)行到這里，我們需要喚醒等待隊(duì)列頭部的若干reader線程去持鎖。由于writer有可能會(huì)在這個(gè)階段偷鎖，因此，這里我們會(huì)先讓top waiter（reader）持鎖，然后再慢慢去計(jì)算到底需要喚醒多少個(gè)reader并將其喚醒。如果當(dāng)前線程已經(jīng)持有了讀鎖（wake type的類型是RWSEM_WAKE_READ_OWNED），則不需要提前持鎖，直接越過這部分的邏輯即可。

B、如果的確發(fā)生了writer通過樂觀自旋偷鎖，那么我們需要檢查設(shè)置handoff的條件。如果reader被writer阻塞太久，那么我們?cè)O(shè)定handoff標(biāo)記，要求rwsem的writer停止通過樂觀自旋偷鎖，將鎖的所有權(quán)轉(zhuǎn)交給top waiter（reader）

C、上面已經(jīng)向rwsem的count增加reader計(jì)數(shù)，這里把owner也設(shè)定上（flag也同步安排，這里non-spinnable bit保持不變）。隨后top waiter的reader會(huì)喚醒若干隊(duì)列中的non top reader，但是它們都不配擁有名字。

讀鎖已經(jīng)安排的妥妥的了，下面就是慢慢喚醒等待隊(duì)列的reader了。我們通過兩步來完成喚醒：

1、將等待隊(duì)列中的reader摘下放入到一個(gè)單獨(dú)的列表中（wlist），同時(shí)對(duì)reader進(jìn)行計(jì)數(shù)。后續(xù)這個(gè)計(jì)數(shù)會(huì)寫入rwsem 的reader counte域。

2、對(duì)于wlist中的每一個(gè)waiter對(duì)象（reader任務(wù)），清除waiter->task并將它們放入wake_q以便稍后被喚醒。

我們先看第一輪計(jì)算喚醒reader個(gè)數(shù)的計(jì)數(shù)：

A、對(duì)于rwsem，其公平性是區(qū)分讀寫的。對(duì)于讀，如果top waiter是reader，那么所有的reader都可以進(jìn)入臨界區(qū)，不管reader在隊(duì)列中的順序。對(duì)于writer，我們要確保其公平性，我們要按照writer在隊(duì)列中的順序依次持鎖。根據(jù)上面的原則，我們會(huì)略過隊(duì)列中的writer，將盡量多的reader喚醒并進(jìn)入臨界區(qū)

B、喚醒數(shù)量不能大于256，否則會(huì)餓死writer

C、根據(jù)喚醒的reader數(shù)量計(jì)算count調(diào)整值