Linux讀寫鎖邏輯解析—Linux為何會引入讀寫鎖？

一、Linux為何會引入讀寫鎖？

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

本文會描述linux5.15.81中讀寫鎖的數據結構和邏輯過程。

二、如何抽象讀寫鎖的數據結構？

下圖可以抽象rwsem相關的數據結構：

一個rwsem對象需要記錄兩種數據：

1、讀寫鎖的狀態信息

2、和該讀寫鎖相關的任務信息

我們先看看讀寫鎖的狀態。讀寫鎖狀態字需要分別記錄讀鎖和寫鎖的狀態：由于多個reader可以同時處于臨界區，所以對于reader-owned的場景，讀鎖狀態變成了一個counter，來記錄臨界區內reader的數量，counter等于0表示讀鎖為空鎖狀態。對于writer，其行為和互斥鎖一致，因此其寫鎖狀態和mutex一樣，仍然使用一個bit表示。

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

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

如果持鎖失敗，無法進入臨界區，我們有兩種選擇：

1、樂觀自旋

2、掛入等待隊列

兩種選擇各有優點和缺點，總結如下：

在5.15的內核中，只有在write持鎖路徑上有樂觀自旋的操作，reader路徑沒有，只有偷鎖的操作。當樂觀自旋失敗后就會掛入等待隊列，阻塞當前線程。（樂觀自旋功能有一個很有意思的發展過程，從開始支持writer的樂觀自旋，到支持全場景的樂觀自旋，然后又回到最初，有興趣可以查閱內核的patch了解詳情）

在了解了rwsem的基本概念之后，我們一起來看看struct rw_semaphore數據結構，其成員描述如下：

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

三、Rwsem外部接口API為何？

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

四、嘗試獲取讀鎖

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

A、tmp的初始值設定為RWSEM_UNLOCKED_VALUE（0值），因此第一次循環是為當前是空鎖而做的優化：如果當前的sem->count等于0，那么給sem->count賦值RWSEM_READER_BIAS，標記持鎖成功，然后設定owner返回1即可。

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

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

五、獲取讀鎖

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

1、快速路徑

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

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

B、當reader的數量過多（以至于都溢出了）的時候，需要禁止樂觀自旋。

C、這里是持鎖成功的路徑。RWSEM_READ_FAILED_MASK上一節已經解釋，這里不再贅述。這里需要注意的是rwsem_set_reader_owned函數中flag的設定，由于reader進入臨界區，因此RWSEM_READER_OWNED也需要設定。RWSEM_RD_NONSPINNABLE標記保持不變。

在快速路徑中，有兩種常見的情況會持鎖成功：一種是空鎖，另外一種是沒有任何waiter等待的純reader并發。

2、慢速路徑

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

如果當前的鎖被reader持有（至少有一個reader在臨界區），那么不再樂觀偷鎖而是直接進行掛等待隊列的操作。為何怎么做呢？因為需要在餓死waiter和reader吞吐量上進行平衡。一方面，連續的reader持續偷鎖的話會餓死等待隊列上的任務。另外，在喚醒路徑上，被喚醒的top reader會順便將隊列中的若干（不大于256個）reader也同時喚醒，以便增加rwsem的吞吐量。所以這里的reader直接掛入隊列，累計多個reader以便可以批量喚醒。

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

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

B、當前線程獲得了讀鎖，需要設置owner，畢竟它是臨界區的新客

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

如果偷鎖不成功，當前的reader還是需要進入阻塞狀態：

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

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

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

D、等待隊列非空的時候，邏輯稍微負載一點。調用rwsem_add_waiter函數即可以把當前任務掛入等待隊列尾部。這時候也需要把之前武斷增加的counter給修正回來了（adjustment初始化為-RWSEM_READER_BIAS）。如果是第一個waiter，也順便設置了RWSEM_FLAG_WAITERS標記。

在當前線程進入阻塞之前，我們需要進行試圖持鎖的動作（上面是空隊列場景檢查，這里的邏輯稍微復雜一點，由于已經入隊，這里需要調用rwsem_mark_wake函數來完成阻塞后喚醒的動作），畢竟這時候可能恰好owner離開臨界區，變成空鎖。

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

B、除了上面說的場景需要喚醒，在reader持鎖并且我們是隊列中的第一個waiter的時候，也需要喚醒的動作（喚醒自己）。

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

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

B、如果在該線程阻塞的時候，有其他任務發送信號給該線程，那么就持鎖失敗退出。如果已經被喚醒，同時又收到信號，這時候需要首先完成喚醒，持鎖成功，然后在其他的合適點再處理該信號。當然，大部分的rwsem都是D狀態，也就不需要處理信號了。

C、進入阻塞狀態，讓調度器選擇next task

六、釋放讀鎖

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

需要強調的是：這里僅僅是減去了讀臨界區的counter計數，并沒有清除owner中的task pointer。此外，當等待隊列有waiter并且沒有writer或者reader在臨界區的時候，我們會調用rwsem_wake來喚醒等待隊列的線程。因為臨界區已經沒有線程，所以需要清除nonspinable標記。喚醒的動作主要是通過rwsem_mark_wake和wake_up_q來完成的，wake_up_q比較簡單，我們就不贅述了，主要看看rwsem_mark_wake的邏輯。

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

在RWSEM_WAKE_READERS場景中，多個reader被喚醒，并且當前很可能是空鎖狀態，為了防止writer搶鎖，因此會先讓top waiter持有讀鎖，然后慢慢處理后續。RWSEM_WAKE_READ_OWNED則沒有這個顧慮，因為喚醒者已經持有讀鎖。

在釋放讀鎖的場景中，rwsem_mark_wake使用的是RWSEM_WAKE_ANY參數，具體的代碼如下：

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

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

B、如果的確發生了writer通過樂觀自旋偷鎖，那么我們需要檢查設置handoff的條件。如果reader被writer阻塞太久，那么我們設定handoff標記，要求rwsem的writer停止通過樂觀自旋偷鎖，將鎖的所有權轉交給top waiter（reader）

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

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

1、將等待隊列中的reader摘下放入到一個單獨的列表中（wlist），同時對reader進行計數。后續這個計數會寫入rwsem 的reader counte域。

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

我們先看第一輪計算喚醒reader個數的計數：

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

B、喚醒數量不能大于256，否則會餓死writer

C、根據喚醒的reader數量計算count調整值