# 從 CPU cache coherence 談 Linux spinlock 可擴展能力議題 本文衍生自 [dog250 的文章](https://blog.csdn.net/dog250/article/details/80589442),斟酌採繁體中文和台灣慣用語,並且補充相關資訊 -- [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) 在 [改善多核心處理器上新建 TCP 連線效能:透過 spinlock 的調整](https://hackmd.io/s/BJv5HGD3m) 一文,spinlock 被拆解為 per cpu 並予以分析,但未涵蓋 spinlock 本身的效能和可擴展能力 ([scalability](https://en.wikipedia.org/wiki/Scalability)) 議題,本文繼續探討。 ## 一點說明 正文開始之前,先給出本文討論的各個場景基於的 CPU 佈局圖,本文中我們將描述很多的場景實驗,因為是分析原理,我將其定義為思想實驗,假設我們思想實驗的系統擁有 16 核 CPU,其中每一個 CPU 封裝有 2 個物理核,每一個物理核有兩個有獨立 cache 的核心,其佈局如下: ![](https://i.imgur.com/mBMdv82.png) 由於實現的可擴展性的原因,當前的大多數平台在實現 CPU cache coherence 處理機制有以下兩種: * snoopy 方式 這意味著 cache coherence 消息通過匯流排廣播,於是就要偵聽總線以在某個時機獲得控制權。這種方式極其不易擴展,在 CPU 數目達到一定量時,總線的爭搶會很嚴重。 參考以太網的 CSMA/CD 協議,會得出一樣的結論,正如 CSMA/CD 的基於總線的以太網由於其不可擴展性進化到了交換式以太網一樣,CPU 間的 cache 一致性協議的點對點 unicast 實現方式最終替代了 snoopy (小規模本地 cache 一致性依然會採用 snoopy 的方式)。總而言之,是總線帶寬限制了 snoopy 想大規模 SMP 發展。 * 點對點 unicast 方式 既然 snoopy 需要嚴格的總線仲裁,採用點對點的方式進行 cache 一致性的消息路由就成了一個可選的應對措施,但是對於多個目的地的消息的發送方而言,one by one 的按序 in turn 方式發送就成了唯一的選擇,正是這種處理方式成了**點對點 unicast 方式的另一個不可擴展性根源**。 但這種不可擴展性是針對更上層而言,在 cache 一致性協議的實現上,它克服了總線仲裁帶來的本層的不可擴展性。業界很多的場景都遵循了類似的**總線–>點對點**的發展軌跡,除了以太網之外,還有 PCI 到 PCIe 的進化。無論哪種實現方式,其過程都體現了**採用被動的 NAK 仲裁向主動的消息路由方向的進化之路似乎是一條放之四海而皆準的康莊大道**。 理解這些,特別是理解**點對點 unicast 方式的 one by one 處理時延會隨著 CPU 核數的增加而線性增加**為後面的內容埋下了伏筆。 在 Linux 內核中,先後有過新舊兩種版本的自旋鎖被大規模使用,一個是 wild spinlock,另一個則是當前內核默認使用的 ticket spinlock,下面的章節會簡而述之。 ## wild spinlock 這種自旋鎖非常簡單,簡而言之就是一個整數: ```clike typedef struct { volatile unsigned int lock; } spinlock_t; ``` 然後其加鎖和解鎖過程為: ```clike void spin_lock(spinlock_t *lock) { while (lock->lock == 1) ; // 自旋等待 } void spin_unlock(spinlock_t *lock) { lock->lock = 0; } ``` 然而在這種簡單的背後卻掩蓋著一個血雨腥風的戰場,我們看一下 why。 根據上面的 CPU 佈局圖,我們可以了解到 CPU 之間的親密關係是不同的,特定 CPU 的 cache line 更新同步到不同 CPU 的 cache line 的時間也不同,這就意味著等待自旋鎖的 CPU 中哪個 CPU 先感知到 lock->lock 的變化,哪個就能優先獲得鎖。 這將大大有損等鎖者之間的公平性。這就好比一群人不排隊上火車,體格好的總是優先登車一樣。 為了解決這個公平性問題,ticket spinlock 登場了。 ## ticket spinlock 登場 ticket spinlock 在設計上增加了一個等鎖期間單調遞增的 ticket 字段(當然,在實現上如何體現這個 ticket 就是 trick 了),確保了先到者先獲得鎖,從而保證了公平性。 ## Linux ticket spinlock 的實現和執行過程 我先給出 Linux ticket spinlock 的偽代碼實現,為了討論簡單,以下的代碼中所有的自加 (i++) 操作均為原子操作,避免鎖中鎖。 * 定義 spinlock ```clike struct spinlock_t { // 上鎖者自己的排隊號 int my_ticket; // 當前叫號 int curr_ticket; } ``` 非常簡單,一個標準的排隊裝置,類似銀行叫號系統,每個辦理業務的取一個號,然後按照號碼的大小依次串行被服務。 * spin_lock 上鎖 ```clike void spin_lock(spinlock_t *lock) { int my_ticket; // 順位拿到自己的 ticket 號碼; my_ticket = lock->my_ticket++; while (my_ticket != lock->curr_ticket) ; // 自旋等待! } ``` * spin_unlock 解鎖 ```clike void spin_unlock(spinlock_t *lock) { // 呼叫下一位! lock->curr_ticket++; } ``` 以上基本就是 Linux ticket spinlock 實現的全部了,沒什麼複雜的,沒什麼大不了的。如果說僅僅是為了讀懂程式碼,確實沒有什麼大不了的,然而深究起來卻可以發現它的不妙。 以下我就從 cache 的角度來分析一下這個自旋鎖的執行過程,以下面的程式碼片段為例: ```clike void demo() { spin_lock(&g_lock); g_var1 ++; g_var2 --; g_var3 = g_var1 + g_var2; spin_unlock(&g_lock) } ``` 步驟如下: * step 1:CPU0 申請鎖,獲取本地 ticket 到申請者的 CPU cache ![](https://i.imgur.com/v9tIf8D.png) * step 2:執行鎖定區域指令的同時,其它 CPU 企圖獲取鎖而自旋 ![](https://i.imgur.com/NOYWNAH.png) * step 3:CPU0 釋放鎖 ![](https://i.imgur.com/BBgkzfu.png) 我們發現,上述的 step 3 中的步驟有點太複雜了。當前的大多數平台傾向於用點對點 unicast 的方式來更新 cache line (因為 broadcast 方式對總線帶寬有要求,隨著 CPU 核數的增加,實現複雜度會增加,這是另一種不可伸縮!),因此 step 3 中更新每一個 CPU cache line 是一個 one by one 的過程,如果是 write invalidate 方式,就更會多出超級多的訪存指令,這些對於理解 Linux ticket spinlock 的不可伸縮性至關重要! 很顯然,隨著 CPU 核數的增加,隨著 spinlock 申請者的增加,step 3 中動作的執行時間會線性增加,最終,當 spinlock 的申請者達到一定數量時,多核 CPU 非但沒有提高效能,反而由於 cache line 更新的時間過久,反過來損害效能。 注意,wild spinlock 同樣存在這個問題,wild spinlock 背後的 cache 一致性過程和 ticket spinlock 完全一致,只是 ticket spinlock 嚴格限定了誰將下一個獲得鎖而 wild spinlock 並不能。 我們已經定性地描述了 Linux ticket spinlock 的當前實現會有什麼問題,為了定量地衡量這種實現會帶來哪些具體的後果,我需要簡單說一下 Linux ticket spinlock (此後簡稱 Linux spinlock)經典的 Markov chain 模型,請看下節。 ## Linux spinlock 的馬可夫鏈模型 為了闡釋 Linux spinlock 的具體性能表現和帶來的結果,必然需要建立一個模型,本節我就說一下 Linux spinlock 的 Markov chain 模型,該模型結合排隊論可以精確描述和預測 Linux spinlock 的行為。 先看一下圖示: ![](https://i.imgur.com/qbCWfEt.png) 解釋一下: :::info 這是一個 Markov chain,其中一共有 $0,1,…n$ 一共 $n + 1$ 個狀態,每一個狀態 $k$,表示系統中有 $k$ 個 CPU 正在自旋等待鎖,$A[k]$ 表示狀態 $k$ 轉換到狀態 $k + 1$ 的速率,也就是相當於請求鎖的速率,而 $S[k]$ 則表示狀態 $k + 1$ 轉換到狀態 $k$ 的速率,也就是相當於釋放鎖的速率。 ::: 簡化起見,我們忽略掉 spinlock 到達的細節,即設在單一 CPU 核心上 spinlock 的請求到達平均間隔為 $T_{arrive}$ (事實上應該是指數分佈),那麼單一 CPU 核心的 spinlock 請求到達的速率就是$\dfrac{1}{T_{arrive}}$ (事實上應該是柏松分佈),由於我們的思想實驗基於多核 CPU 平台,因此總體上的 spinlock 請求到達的速率和空閒 CPU 個數成正比。假設當前的 $n$ 核 CPU 系統上已經有k個 CPU 在自旋等鎖了,那麼 $n−k$ 個 CPU 上 spinlock 的到達速率為 $\dfrac{n−k}{T_{arrive}}$,因此,上圖中的 $A[k]$ 便求了出來: :::info $A[k]=\dfrac{n−k}{T_{arrive}}$ ::: > 註:以上敘述同參考文獻[Non-scalable locks are dangerous](https://people.csail.mit.edu/nickolai/papers/boyd-wickizer-locks.pdf)的Section 3.2。「速率」以台灣慣用語的語感來說似乎有些不對。原文是rate。翻譯成台灣用語會比較像是:單顆CPU平均每隔$T_{arrive}$會請求一次spinlock,所以單顆CPU請求spinlock的頻率(rate)是$1/T_{arrive}$。對上述多核系統同一個spinlock來說,它被請求的頻率是$A[k]=1/T_{arrive}*(\text{還沒請求鎖的CPU})=\dfrac{n-k}{T_{arrive}}$ > 因為這裡的rate剛好是$\dfrac{次數}{時間}$,翻成頻率或許比較易懂。 現在考慮釋放鎖的過程導致的狀態轉換。 先理解狀態 $S[k]$ 的意義,$S[]$ 這裡指的是 Service,相應的對應 $A[]$ 則表示 Arrival,所謂的服務時間指的是從當前 CPU 獲得 spinlock 到該 spinlock 成功轉給下一個 CPU 之間的時間!這部分時間包括兩個部分,一個部分是執行 lock/unlock 之間代碼的時間E,另一部分時間指的是 unlock 操作中消耗的時間,我們把這部分時間設為 R,現在的問題轉化為根據以上的信息,求出 R 的表達式。 我們在討論中有個假設,即我們思想實驗的平台對 cache 一致性中 update 的管理方式是點對點 one by one 的 unicast 方式,而不是 broadcast 的方式,設處理一個 CPU 的 update 時間為 c,那麼在 k 個 CPU 同時自旋等鎖的條件下,所有的 CPU 的 cache line 全部更新的時間就是 $k\times c$,由於 ticket spinlock 是嚴序的,而 cache line update 的到達先後卻不可控制,因此下一個獲得鎖的 CPU 的 cache line 得到更新的時間平均值為 $k\times c/2$,即平均在這個時間後,下一個 CPU 即可以成功獲取鎖,從 spin_lock 自旋狀態返回。於是,我們有: :::info $S[k]=\dfrac{1}{E+\dfrac{k×c}{2}}$ ::: 以上關於 $A[k]$ 和 $S[k]$ 的表達式非常好理解,我們可以看到,請求的到達速率,即 spinlock 的速率是和空閒 CPU 數量,即不在自旋狀態的 CPU 數量成正比的,顯然地,空閒 CPU 越多,請求越容易到達,相反,spin_unlock 的速率,即 $S[k]$,則是和當前自旋狀態的 CPU 數量成反比的,至少是負相關的,因為自旋狀態的 CPU 越多,更新這麼多 CPU 的 cache line 的時間開銷就越大,這意味著服務速率 $S[k]$ 就會越小。 有了上面基本的結論,加上下面一個穩態下 Markov chain 狀態轉換率守恆的基本原則,就可以導出模型本身了: >設,P0,P1,...Pn 是系統處在這n個狀態的概率,顯然 $\sum P+k=1$。當系統處在穩態時,下面的式子成立: >$P_k×A[k]=P_{k+1}\times S[k]$ 這是一個遞推的開始,我們可以求出 $P_k$ 關於 $k$ 的表達式,然後模型裡的參數就可以去用實際值填充了。具體過程不在這里羅列,最終通過上面的三個式子推導出來的公式為: $P_k = \dfrac{\frac{1}{T_{arrive}^k(n-k)!}\prod_{i=0}^k (E+ic)}{\sum_{i=0}^{n}\frac{1}{T_{arrive}^i(n-i)!}\prod_{j=0}^i (E+jc)}$ 有了這個式子,我們便可以求出任意時刻系統中處在自旋等鎖狀態的 CPU 總量: $C=\sum_{i=0}^{n}iP_i$ 模型最終在於解釋歷史數據和預測未來數據,在上面的基礎上,我們導出一個加速比的概念,即在 $x$ 個 CPU 的系統中爭搶特定的 spinlock,CPU 總量 $x$ 中有多少 CPU 未處在自旋等鎖的狀態。顯然,它的值為: $S=x−C$ 如果隨著 $x$ 的增加,S 也增加,這意味著增加了 CPU 核心數量確實緩解了 spinlock 帶來的串行化問題,但是不幸的是,情況並非如此。該模型顯示出的 $\dfrac{S}{x}$ 曲線顯示出當總 CPU 數量 $x$ 增加到一定程度,加速比會斷崖跌落(CPU 太多了,one by one 的 cache line 操作太重太耗時了!),這意味著在達到某種條件的情況下,增加 CPU 核心數量反而會損害系統性能! 不可伸縮也就罷了,cache line 的操作沒想到影響如此之大! ## 關於 Markov chain spinlock 模型的推論 我們再看 $S[k]$ 的表達式: $S[k]=\dfrac{1}{E+\dfrac{k\times c}{2}}$ 這個式子是 spinlock 不可伸縮的根源。注意這裡的 $E$,它對 spinlock 整體不可伸縮性的程度的影響至關重要!我們進一步可以將式子抽象為: $f(x)=\dfrac{1}{\alpha+x}$ 然後我們來看一下 $x/y$ 曲線的走勢: ![](https://i.imgur.com/I4vmo1C.png) 回到我們的模型,$E$ 越大,cache 一致性時間線性增長的影響就越不明顯,只有在 $E$ 比較小的時候,我們才深受 spinlock 不可伸縮之害。然而 spinlock 的應用場合不就是 critical section 很小的時候嗎? 假設我們的 critical section 確實很小,那麼 $S[k]$ 和 $k$ 之間就近似反比關係了,這樣事情就嚴重多了。它的根源在於 cache 一致性的時間是 $O(n)$ 的而不是常數級 $O(1)$ 的,因此我們也就有了解決問題的方向。下一節詳述。 <參考文獻:[Non-scalable locks are dangerous](https://people.csail.mit.edu/nickolai/papers/boyd-wickizer-locks.pdf)> ## MCS spinlock 如何解決問題 問題已經很明確,如何破解顯然已經不是重要的事了。 既然問題出在共享變量上自旋導致的 cache 一致性時間開銷太大,那麼改成在私有變量上自旋即可,這顯然是一個 $O(1)$ 的操作,替掉之前不可伸縮的 $O(n)$ 操作即可。 為了做到這一點,需要重新設計 spinlock 的數據結構。本節所描述的新的 spinlock 正是業內有名的 MCS spinlock,一些簡單的介紹請參考下面的文章: MCS locks and qspinlocks:https://lwn.net/Articles/590243/ 讓我們從代碼的角度來看一下為什麼 MCS spinlock 可以解決 cache 一致性導致的 non-scalable 問題。 mcs spinlock 在 Linux 的實現在 `kernel/locking/mcs_spinlock.h` 檔案,不過直到 4.14 版本內核,Linux 並沒有哪個子系統採用這個新的 spinlock,不管怎樣,既然代碼在手,我們便可以自己用。 和 ticket spinlock 的描述一致: * 定義 MCS spinlock ```c= struct mcs_spinlock { struct mcs_spinlock *next; // 類似 ticket 的概念,所有争鎖排隊 int locked; /* 1 if lock acquired */ // 本地的自旋變量,不再是全局 }; ``` 可見其創舉在於在自旋變量納入了排隊實體本身。在 mcs spinlock 中,一個 struct mcs_spinlock 實例就是一個排隊實體,它擁有自己的自旋變量 locked,即它只需要不斷 check 自己的 locked 變量即可。這體現了 OO 的思想。 * MCS spinlock 上鎖 ```clike // 自己的排隊節點 node 需要自己在外部初始化,它将被排隊到 lock 指示的等鎖隊列中。 void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node) { struct mcs_spinlock *prev; /* Init node */ node->locked = 0; node->next = NULL; // 原子執行 *lock = node並返回原来的 *lock prev = xchg(lock, node); if (likely(prev == NULL)) { return; } // 原子執行 prev->next = node; // 這相當於一個排入隊的操作。記為(*) WRITE_ONCE(prev->next, node); while (0 == &node->locked) ; // 在自己的 locked 變量上自旋等待! } ``` * MCS spinlock 解鎖 ```clike // 自己要傳入一個排入到 lock 的隊列中的自己的 node 對象 node,解鎖操作就是 node 出隊並且主動將隊列中下一個對象的 locked 幫忙設置成 1. void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node) { // 原子獲取 node 的下一個節點。 struct mcs_spinlock *next = READ_ONCE(node->next); if (likely(!next)) { // 二次確認真的是NULL,則返回,說明自己是最後一個,什麼都不需要做。 if (likely(cmpxchg_release(lock, node, NULL) == node)) return; // 否則說明在 if 判斷 next 為 NULL 和 cmpxchg 原子操作之間有 node 插入,随即等待它的 mcs_spin_lock 調用完成,即上面 mcs_spin_lock 中的(*)注釋那句完成以後 while (!(next = READ_ONCE(node->next))) cpu_relax_lowlatency(); } // 原子執行 next->locked = 1; arch_mcs_spin_unlock_contended(&next->locked); } ``` 你已經看到了,unlock 操作僅僅操作了 next 的 locked 字段,該字段屬於在某個 CPU 上自旋等待的 mcs spinlock 對象,不會觸發全局的 cache 一致性刷新! 上述的 mcs spinlock 實現,之所以解決了保證 cache 一致性而導致的開銷隨著 CPU 核數的增加線性增加的問題,就是因為一個簡單的動作,即傳球代替了搶球。 ticket spinlock 的問題在於,既然你已經知道誰是下一個獲得鎖的等待者,為什麼不直接將控制權交給它呢?為什麼還要有一個全局盲搶的動作呢? 也許你已經看到了當前 Linux 的 MCS spinlock 的實現問題,它的 API 變了,這意味著你無法對內核中已經使用的 ticket spinlock 進行無縫替換。我們需要下面的 API: ```clike void mcs_spin_lock(struct mcs_spinlock *lock); void mcs_spin_unlock(struct mcs_spinlock *lock); ``` 由於同一個 CPU 同時只能等待一個 spinlock,這件事就很簡單了。來吧,讓我們實現它: ```clike struct mcs_spinlock_node { struct mcs_spinlock_node *next; int locked; /* 1 if lock acquired */ }; struct mcs_spinlock { struct mcs_spinlock_node nodes[NR_CPUS]; struct mcs_spinlock_node *tail; }; void mcs_spin_lock(struct mcs_spinlock *lock) { struct mcs_spinlock_node *local; struct mcs_spinlock_node *prev; int cpu = smp_processor_id(); local = &(lock->nodes[cpu]); local->locked = 0; local->next = NULL; prev = xchg(&lock->tail, local); if (prev == NULL) return; WRITE_ONCE(prev->next, local); while (!local->locked); } void mcs_spin_unlock(struct mcs_spinlock *lock) { struct mcs_spinlock_node *local; struct mcs_spinlock_node *next; int cpu = smp_processor_id(); cpu = smp_processor_id(); local = &(lock->nodes[cpu]); next = READ_ONCE(local->next); if (likely(!next)) { if (cmpxchg_release(lock->tail, local, NULL) == local) { return; } while (!(next = READ_ONCE(local->next))); } local->next->locked = 1; } ``` 是不是好看了很多呢? 好了,關於 spinlock 的話題差不多該結束了。 延伸閱讀: * [新的排隊 spin_lock – 有序和無序](https://blog.csdn.net/dog250/article/details/5303249?locationNum=10&fps=1) * [本地自旋鎖與信號量/多服務台自旋隊列 - spin wait 風格的信號量](https://blog.csdn.net/dog250/article/details/47098055) * [一個 Linux 內核的自旋鎖設計-接力嵌套堆棧式自旋鎖](https://blog.csdn.net/dog250/article/details/46921989) ## Aliworkqueue 這是同樣優化策略的另一種體現,我還沒有測試,但是看其實現感覺略微重量的些。不多說,直接看 patch 吧: aliworkqueue: Adaptive lock integration on multi-core platform:https://patchwork.kernel.org/patch/8844841/ >Wire-latency(RC delay) dominate modern computer performance, conventional serialized works cause cache line ping-pong seriously, the process spend lots of time and power to complete.specially on multi-core platform. However if the serialized works are sent to one core and executed ONLY when contention happens, that can save much time and power, because all shared data are located in private cache of one core. We call the mechanism as Adaptive Lock Integration. (ali workqueue) 參照解說: [介绍 aliworkqueue](https://www.douban.com/note/596489332/) * 設計思維如 [Fast asymmetric thread synchronization](https://dl.acm.org/citation.cfm?id=2400686) Aliworkqueue 除了考慮到了 spinlock 本身加鎖解鎖對 cache 一致性的影響,還考慮到了 spinlock 保護的 critical section 操作的共享數據讀寫對 cache 一致性的影響,如此一來,本文上述的 Markov chain 模型就要進行修訂了,因為 critical section 的操作時間不能再被當是常量 $E$ 了,而它也要作為一個和 CPU 核數相關的量參與到模型的構建中了。