自旋鎖探祕

一、前言

本公衆號之前已經有了一篇關於 spinlock 的文檔（Linux kerenl 同步機制（上篇）），在之前的文章中有對自旋鎖進行簡單的介紹，同時給出了 API 彙整和應用場景。不過該文章中的自旋鎖描述是基於比較老的內核版本，那時候的自旋鎖還是 ticket base 鎖，而目前最新內核中的自旋鎖已經進化成 queued spinlock，因此需要一篇新的自旋鎖文檔來跟上時代。此外，本文將不再描述基本的 API 和應用場景，主要的篇幅將集中在具體的自旋鎖實現上。順便說一句，同時準備一份 linux5.10 源碼是打開本文的正確方式。如果不想下載源代碼，這個網址 https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/tree/?h=v5.10.123 可以瀏覽自旋鎖的源代碼。

由於自旋鎖可以在各種上下文中使用，因此本文中的 thread 是執行線索的意思，表示進程上下文、hardirq 上下文、softirq 上下文等多種執行線索，而不是調度器中線程的意思。

二、簡介

Spinlock 是 linux 內核中常用的一種互斥鎖機制，和 mutex 不同，當無法持鎖進入臨界區的時候，當前執行線索不會阻塞，而是不斷的自旋等待該鎖釋放。正因爲如此，自旋鎖也是可以用在中斷上下文的。也正是因爲自旋，臨界區的代碼要求儘量的精簡，否則在高競爭場景下會浪費寶貴的 CPU 資源。

1、代碼結構

我們整理 spinlock 的代碼結構如下：

最上層是通用自旋鎖代碼（體系結構無關，平臺無關），這一層的代碼提供了兩種接口：spinlock 接口和 raw spinlock 接口。在沒有配置 PREEMPT_RT 情況下，spinlock 接口和 raw spinlock 接口是一毛一樣的，但是如果配置了 PREEMPT_RT，spinlock 接口走 rt spinlock，底層是基於 rtmutex 的。也就是說這時候的 spinlock 不再禁止搶佔，不再自旋等待，而是使用了支持 PI 的睡眠鎖來實現，因此有了更好的實時性。而 raw spinlock 接口即便在配置了 PREEMPT_RT 下仍然保持傳統自旋鎖特性。

中間一層是區分 SMP 和 UP 的，在 SMP 和 UP 上，自旋鎖的實現是不一樣的。對於 UP，自旋沒有意義，因此 spinlock 的上鎖和放鎖操作退化爲 preempt disable 和 enable。SMP 平臺上，除了搶佔操作之外還有正常自旋鎖的邏輯，具體如何實現自旋鎖邏輯是和底層的 CPU architecture 相關的，後面我們會詳細描述。

最底層的代碼是體系結構相關的代碼，ARM64 上，目前採用是 qspinlock。和體系結構無關的 Qspinlock 代碼抽象在 qspinlock.c 文件中，也就是本文重點要描述的內容。

2、接口 API

一個示例性的接口 API 流程如下（左邊是 UP，右邊是 SMP）：

具體的接口 API 簡單而直觀，這裏就不再羅列了。

3、自旋鎖的演進

自旋鎖的演進過程如下：

最早的自旋鎖是 TAS（test and set）自旋鎖，即通過原子指令來修改自旋鎖的狀態（locked、unlocked）。這種鎖存在不公平的現象，具體原因如下圖所示：

如果 thread4 當前持鎖，同一個 cluster 中的 cpu7 上的 thread7 和另外一個 cluster 中的 thread0 都在自旋等待鎖的釋放。當 thread4 釋放鎖的時候，由於 cpu7 和 cpu4 的拓撲距離更近，thread7 會有更高概率可以搶到自旋鎖，從而產生了不公平現象。

爲了解決這個問題，內核工程師又開發了 ticket base 的自旋鎖，但是這種自旋鎖在持鎖失敗的時候會對自旋鎖狀態數據 next 成員進行 ++ 操作，當 CPU 數據巨大並且競爭激烈的時候，自旋鎖狀態數據對應的 cacheline 會在不同 cpu 上跳來跳去，從而對性能產生影響，爲了解決這個問題，qspinlock 產生了，下面的文章會集中在 qspinlock 的原理和實現上。

三、Qspinlock 的數據結構

1、Qspinlock

struct qspinlock 定義如下（little endian）：

Qspinlock 的數據結構一共 4 個 byte，不同的場景下，爲了操作方便，我們可以從不同的視角來看這四個字節，示意圖如下：

Tail 成員佔 2B，包括 tail index（16~17）和 tail cpu（18~31）兩個域。補充說明一下，上圖是系統 CPU 的個數小於 16k 的時候的佈局，如果 CPU 數據太大，tail 需要擴展，壓縮 pending 域的空間。這時候 pending 域佔一個 bit，其他的 7 個 bit 用於 tail。之所以定義的如此複雜主要是爲了操作方便，有時候我們需要對整個 4B 的 spinlock val 進行操作（例如判斷空鎖需要直接判斷 val 是否爲 0 值），有時候需要對 pending+locked 這兩個 byte 進行操作（例如 mcs node queue head 需要自旋在 pending+locked 上），而有的時候又需要單獨對 pending 或者 locked 進行設置，大家可以結合代碼體會 owner 的良苦用心。

拋開這些複雜的 union 數據成員，實際上 spinlock 的 4B 由下面三個域組成：

2、MCS lock

MCS lock 定義如下：

爲了解決多個 thread 對 spinlock 的讀寫造成的 cache bouncing 問題，我們引入了 per cpu 的 mcs lock，讓 thread 自旋在各自 CPU 的 mcs lock，從而減少了緩存顛簸問題，提升了性能。由於自旋鎖可能是嵌套的，因此 mcs lock 節點在每個 CPU 上是多個，具體如下圖所示：

在某個線程上下文，由於持 A 鎖失敗而進入自旋，我們需要把該 CPU 上的 mcs 鎖節點掛入 A spinlock 的隊列。在這個自旋過程中，該 CPU 有可能發生軟中斷，在軟中斷處理函數中，我們試圖持 B 鎖，如果失敗，那麼該 cpu 上的 mcs 鎖節點需要掛入 B spinlock 的隊列。在這樣的場景中，我們必須區分線程上下文和軟中斷上下文的 mcs node。這樣複雜的嵌套最多有四層：線程上下文、軟中斷上下文、硬中斷上下文和 NMI 上下文。因此我們每個 CPU 實際上定義了多個 mcs node 節點（目前是四個），用來解決自旋鎖的嵌套問題。

瞭解了上面的內容之後，我們可以回頭看看 tail 成員。這個成員分成兩個部分，一個是 cpu id 加一（0 表示隊列無節點），一個就是 context index。這兩部分合起來可以確定一個 mcs node 對象。

四、Qspinlock 的原理

1、Qspinlock 狀態說明

通過上面對 qspinlock 數據結構的說明我們可以知道，spinlock 的狀態由 locked、pending 和 tail 三元組來表示。下面就是幾種狀態示例：

需要說明的是 tail block 中的 “n” 和“”表示了 mcs node 隊列的情況。n 表示 qspinlock 只有一個 mcs node， 表示 qspinlock 有若干個 mcs node 形成隊列，同時在競爭 spinlock。

2、Qspinlock 中的狀態遷移

一個完整的 qspinlock 狀態遷移過程如下：

我們可以對照下一節的代碼來驗證上面的這張狀態遷移圖。

五、Qspinlock 的實現

1、獲取 qspinlock

本小節我們主要描述獲取和釋放 qspinlock 的代碼邏輯（省略了調試、內存屏障等的代碼）。我們先看獲取去 qspinlock 的代碼如下：

如果 spinlock 的值（指完整的 4B 數據，即 spinlock 的 val 成員）等於 0，那麼說明是空鎖，那麼調用線程可以持鎖進入臨界區。這時候，spinlock 的值被設置爲 1，即鎖處於 locked 狀態。如果快速路徑失敗，那麼進入慢速路徑。慢速路徑比較長，我們分段解讀：

A、如果當前 spinlock 的值只有 pending 比特被設定，那麼說明該 spinlock 正處於 owner 把鎖轉交給自旋鎖 spinner 的過程中。在這種情況下，我們需要重讀 spinlock 的值。當然，如果持續重讀的結果仍然是僅 pending 比特被設定，那麼在_Q_PENDING_LOOPS 次循環讀之後放棄。

B、如果有其他的線程已經自旋等待該 spinlock（pending 域被設置爲 1）或者自旋等待 per cpu 的 MCS 鎖上（pending 域被設置爲 1 並且設置了 tail 域也被設置），那麼該線程需要掛入自旋等待隊列。否則說明該線程是第一個等待持鎖的，那麼不需要排隊，只要 pending 在自旋鎖上就 OK 了。我們先看看怎麼 pending 自旋等待 qspinlock 代碼：

A、執行至此 tail+pending 都是 0，看起來我們應該是第一個 pending 線程，通過 queued_fetch_set_pending_acquire 函數讀取了 spinlock 的舊值，同時設置 pending 比特標記狀態。

B、在設置 pending 標記位之後，我們需要再次檢查一下我們這裏設置 pending 比特的時候，其他的競爭者是否也修改了 pending 或者 tail 域。如果其他線程已經搶先修改，那麼本線程不能再 pending 在自旋鎖上了，而是需要回退 pending 設置（如果需要的話），並且掛入自旋等待隊列。如果沒有其他線程插入，那麼當前線程可以開始自旋在 qspinlock 狀態，等待 owner 釋放鎖了：

A、至此，我們已經成爲合法的 spinlock 自旋者，通過 atomic_cond_read_acquire 函數自旋在 spinlock 的 locked 域，直到 owner 釋放 spinlock。這裏自旋並不是輪詢，而是通過 WFE 指令讓 CPU 停下來，降低功耗。當 owner 釋放 spinlock 的時候會發送事件喚醒該 CPU。

B、發現 owner 已經釋放了鎖，那麼清除 pending 標記，同時設定 locked 標記，持鎖成功，進入臨界區。以上的代碼就是 pending 線程自旋等待進入臨界區的代碼，下面我們再一起看看自旋在 MCS lock 的情況：

當不能 pending 在 spinlock 的時候，當前執行線索需要掛入自旋隊列，自旋在自己的 mcs lock 上。首先要進行入隊前的準備工作：一是要找到對應的 mcs node，其次要準備好 tail 域要設置的值。

A、獲取 mcs node 的基地址

B、由於 spin_lock 可能會嵌套（在不同的自旋鎖上嵌套，如果同一個那麼就是死鎖了）因此我們構建了多個 mcs node，每次遞進一層。順便一提的是：當 index 大於閥值的時候，我們會取消 qspinlock 機制，恢復原始自旋機制。

C、將 context index 和 cpu id 組合成 tail

D、根據 mcs node 基地址和 index 找到對應的 mcs node

找到 mcs node 之後，我們需要掛入隊列，代碼如下：

A、初始化 MCS lock 爲未持鎖狀態

B、試圖獲取鎖，很可能在上面的過程中，pending thread 和 owner thread 都已經離開了臨界區，這時候如果持鎖成功，那麼就可以長驅直入，進入臨界區。

C、修改 qspinlock 的 tail 域，old 保存了舊值。如果這是隊列中的第一個節點，那麼至此就結束了，如果之前 tial 域就有值，那麼說明有隊列中有其他 waiter

A、如果等待隊列中已經有了 waiter，那麼需要串聯起來，等待機會去自旋在 spinlock 上去。

B、建立新 node 和舊的等待隊列的關係

C、自旋在 mcs lock 上，等待 locked 狀態變成 1。至此，我們已經是處於 mcs queue 中的頭部

執行至此，我們已經獲得了 MCS lock。在我們自旋等待的時候，可能其他的競爭者也加入到鏈表了，next 不再是 null 了（即我們不再是隊尾了）。因此這裏需要更新 next 變量。由於本線程已經獲取了自旋在 spinlock 的機會，那麼需要

A、在獲取了 MCS lock 之後（排到了 mcs node queue 的頭部），我們獲准了在 spinlock 上自旋。這裏等待 pending 和 owner 離開臨界區。

B、至此，我們獲取了 spinlock，在進入臨界區之前，我們需要解放自旋在 mcs 鎖的頭部節點。如果本 mcs node 是隊列中的最後一個節點，我們不需要處理 mcs lock 傳遞，直接試圖持鎖，如果成功，完成持鎖，進入臨界區。如果 mcs node 隊列中仍然有節點，那麼邏輯要更復雜一些，代碼如下：

A、如果本 mcs node 不是隊列尾部，那麼不需要考慮競爭，直接持 spinlock

B、在進入臨界區之前需要釋放下一個節點，讓其自旋在 spinlock 上。

把 mcs lock 傳遞給下一個節點

2、釋放 qspinlock

釋放 spinlock 的代碼是 queued_spin_unlock 函數，非常的簡單，就是把 qspinlock 的 locked 域設置爲 0。

六、小結

本文簡單的介紹了 linux 內核中的自旋鎖同步機制，在移動環境的激烈競爭場景中，自旋鎖的性能表現不盡如人意，無論是吞吐量還是延遲。產生這個問題的主要原因有兩個：一是內核中自旋鎖的設計基本上是僅考慮 SMP 硬件平臺，在目前異構的手機平臺上表現不佳。二是由於內核自旋鎖是基於公平的原則來設計，而手機場景中從來不是追求公平的，它看中的是響應延遲。目前 OPPO 內核團隊正在進行內核自旋鎖的優化課題，我們也歡迎對此有興趣的小夥伴加入我們，一起感受這份優化內核帶來的快樂。

參考文獻：

1、內核源代碼

https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/tree/?h=v5.10.123

2、linux-5.10.61\Documentation\scheduler*

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/viUgMAnVgC_bHyVifkHqsQ