從 CPU cache coherence 談 Linux spinlock 可擴展能力議題

資料整理: jserv

在〈藉由 spinlock 的調整，改善多核處理器建立 TCP 連線效能〉一文，spinlock 被拆解為 percpu 並予以分析，但未涵蓋 spinlock 本身的效能和可擴展能力 (scalability) 議題，本文繼續探討。

本文啟發自 dog250 的文章

術語和背景知識

開始探討主題前，先說明本文的術語:

1. core (核): 最基本的運算處理單元。為區隔作業系統「核心」(kernel) 一詞，本文一律將中央處理器的 core 翻譯為「核」，對應到 Linux 核心程式碼就是 cpu0 和 cpu1 一類的寫法;
2. processor (處理器): 將若干個核透過 CPU socket，讓每個核的接腳得以連通電子訊號，近年來每個核的接腳數量越多，針腳必須越做越細且密度越高，主流設計是將針腳改成彈性針腳位於 CPU 插座上，處理器上僅有接觸點;
3. system (系統): 由若干處理器藉由高速的網路連接 (interconnect) 構成整個運算系統。配合台灣資訊科技術語，本文把 Intel 或類似廠商出品的系統稱為「中央處理器」;

示意如下圖:

出處: Intel® Performance Counter Monitor - A Better Way to Measure CPU Utilization

假設在實驗環境中中央處理器擁有 16 核，其中每個處理器 (processor) 封裝著有 2 個實體核，也就是說，每個處理器具備兩個獨立 (private) cache 的核，佈局如下：

由於系統實作的可擴展能力考量，目前大多數中央處理器架構在 cache coherence 處理機制大致可分以下兩種:

• snooping 方式
  • "snoop" 在漢語中的涵義是「窺探、打探」，在此引申為 cache coherence 訊息通過匯流排廣播，於是就要監聽匯流排，以便於某時獲得控制權。這種方式往往限制可擴展能力，在中央處理器的核數目達到一定規模之際，匯流排的競爭狀況會很嚴重。
  • 參考乙太網路的 CSMA/CD 協定，會得出類似的結論，正如 CSMA/CD 之於匯流排的擴展能力受限、從而進化到 (Switched Ethernet)，中央處理器內部各核之間的 cache coherence 協定的點對點 unicast 實作方式最終替代 snooping (小規模本地 cache coherence 依然會採用 snooping 的方式)。總而言之，是匯流排頻寬限制 snooping 在大規模 SMP 的發展。
• 點對點 unicast 方式
  • 既然 snooping 需要嚴格的匯流排仲裁，採用點對點的方式進行 cache coherence 的訊息路由就成為可選的應對措施，但是對於多個目的地的訊息的發送方而言，有著明確順序的逐一 (in turn) 方式發送就成為唯一的選擇，正是這種處理方式釀造點對點 unicast 方式在擴展能力受限的根源。
  • 但這種不可擴展性是針對更上層而言，在 cache coherence 協定的實作中，它克服匯流排仲裁帶來的本層的擴展能力議題。業界很多的場景都遵循了類似的匯流排 $\to$ 點對點的發展軌跡，除了乙太網路之外，尚有 PCI 到 PCIe 的進化。無論哪種實作策略，發展過程都展現採用被動的 NAK 仲裁向主動的訊息路由方向的進化之路，似乎是條放之四海而皆準的康莊大道。

理解這些，特別是理解點對點 unicast 方式的 one by one 處理時延會隨著核數的增加而線性增加為後面的內容埋下了伏筆。

Linux 核心中存在多種 spinlock (自旋鎖) 被大規模使用，最初是 wild spinlock，再來採納 ticket spinlock。

wild spinlock

一如 "wild" 在漢語的意思「粗暴、未經馴化」，這種 spinlock 非常簡單，就由一個整數構成:

typedef struct {
    volatile unsigned int lock;
} spinlock_t;

其上鎖和解鎖操作如下:

void spin_lock(spinlock_t *lock) {
    while (lock->lock == 1)
        /* spin-wait */ ; 
}
void spin_unlock(spinlock_t *lock) {
    lock->lock = 0;
}

然而在這貌似簡單的程式背後，卻猶如野生環境中動物間頻繁廝殺的競爭，為何呢？

根據上面的中央處理器佈局圖，我們可知各處理器核之間的 processor affinity (趨向的程度) 不同，特定中央處理器核的 cache line 更新同步到不同核的 cache line 的時間亦不同，這就意味著等待 spinlock 的中央處理器中哪個核先察覺到 lock->lock 的變化，該核就能優先獲得鎖。

這將大幅損害等鎖者之間的公平性。這就好比一群人不排隊上火車，體格好的乘客總是優先登車一樣。

為了解決這個公平性問題，ticket spinlock 登場，後者相較於 wild spinlock 的設計，新增一個紀錄等鎖期間單調遞增的 ticket 欄位，確保先到者先獲得鎖，從而保證公平性。

Linux ticket spinlock 的實作和執行過程

以下是 Linux ticket spinlock 的簡化實作程式碼，為了行文便利，以下的程式碼中所有的遞增 (如 i++) 操作均為 atomic (有如原子般不可切割)，避免鎖中鎖。

• 定義 spinlock

struct spinlock_t {
    /* 上鎖者抽到的號碼 */
    int my_ticket;

    /* 目前的叫號數值 */
    int curr_ticket;
}

這段程式碼展現標準的佇列，類似銀行叫號系統，每個辦理業務的抽取一個號碼牌，然後按照號碼的先後，循序進行服務。

• spin_lock 上鎖

void spin_lock(spinlock_t *lock) { 
    int my_ticket; 
    /* 依序拿到自己的 ticket 號碼 */
    my_ticket = lock->my_ticket++; 
    while (my_ticket != lock->curr_ticket)
        /* spin-wait */ ; 
}

• spin_unlock 解鎖

void spin_unlock(spinlock_t *lock)
{
    /* 呼喚下一位 */
    lock->curr_ticket++;
}

若僅是閱讀程式碼，確實沒看到什麼可議之處，但只要深究就會發現潛藏的危機。以下是從 cache 的角度，分析上述 spinlock 的執行過程，搭配下列程式碼來進行實驗:

void demo()
{
    spin_lock(&g_lock);
    g_var1 ++;
    g_var2 --;
    g_var3 = g_var1 + g_var2;
    spin_unlock(&g_lock)
}

各步驟如下：

• 步驟 1: CPU₀ 申請鎖，持有本地 ticket 到申請者的 cache
  

• 步驟 2: 執行鎖定區域指令的同時，其它 CPU 核企圖獲取鎖而自旋
  

• 步驟 3：CPU₀ 釋放鎖
  

我們可發現，步驟 3 過於複雜。目前許多中央處理器實作偏好用點對點 unicast 的方式來更新 cache line (因為 broadcast 方式對匯流排頻寬有要求，隨著中央處理器核數的增加，實作複雜度會提高，也限制整體擴展能力)，因此步驟 3 裡頭更新每個 cache line 是個循序執行的過程，若是 write invalidate 方式，就需要更多的存取指令，這些對於理解 Linux ticket spinlock 的可擴展能力至關重要！

顯然隨著處理器核數的增加，步驟 3 對於 spinlock 請求增加的執行時間會線性增長，最終，當 spinlock 的請求量達到一定規模時，多核中央處理器非但無法提高效能，反而由於 cache line 更新的時間過久，反過來損害效能。

注意，wild spinlock 同樣存在這個問題，wild spinlock 背後的 cache coherence 過程和 ticket spinlock 完全一致，只是 ticket spinlock 嚴格規定誰將下一個獲得鎖，而 wild spinlock 並不能。

我們已定性地描述 Linux ticket spinlock 的實作會有什麼問題，為定量地衡量這種實作會帶來哪些具體的後果，需要簡述 Linux ticket spinlock (此後簡稱 Linux spinlock) 對應到經典的 Markov chain 模型。

Linux spinlock 的馬可夫鏈模型

為闡釋 Linux spinlock 的具體效能表現和帶來的衝擊，必然要建立一個模型，本模型結合排隊理論，可精確描述和預測 Linux spinlock 行為。

考慮以下圖示：

這是個 Markov chain，其中一共有 $0,1,2,...,n$ 即 $n+1$ 個狀態，每一個狀態 $k$，表示系統中有 $k$ 個中央處理器核正在自旋等待鎖，$A[k]$ 表示狀態 $k$ 轉換到狀態 $k+1$ 的頻率，也就是相當於請求鎖的頻率，而 $S[k]$ 則表示狀態 $k+1$ 轉換到狀態 $k$ 的頻率，也就是相當於釋放鎖的頻率。

簡化起見，我們忽略掉 spinlock 到達的細節，假設在中央處理器單一核上平均每隔 $T_{arrive}$ (應是指數分佈，Exponential distribution) 會請求一次 spinlock，因此單一核的請求 spinlock 的頻率 (rate) 即是${\displaystyle \frac{1}{T_{arrive}}}$ (應是 Poisson 分佈，法語的 pois 發音類似英語的 pwa，於是 Poisson 音似漢語「玻頌」，讀音可參考 Wiktionary 上的音訊)。進而推廣到多核中央處理器平台，於是請求 spinlock 的頻率和空閒核的數量成正比。假設現有 $n$ 核中央處理器系統上已有 k 個核在自旋等鎖，那麼 $n-k$ 個核上 spinlock 的到達頻率則是 ${\displaystyle \frac{n-k}{T_{arrive}}}$，因此，從上圖中的 $A[k]$ 得到：
$$A[k]={\displaystyle \frac{n-k}{T_{arrive}}}$$

註：以上敘述對照參考文獻 Non-scalable locks are dangerous 的 Section 3.2，原文是 rate，剛好是 ${\displaystyle \frac{\mathrm{次}\mathrm{數}}{\mathrm{時}\mathrm{間}}}$，翻成「頻率」較易懂。

現在考慮釋放鎖的過程導致的狀態轉換。

先理解狀態 $S[k]$ 的意義，$S[]$ 這裡指的是 Service，相應的對應 $A[]$ 則表示 Arrival，所謂的服務時間指的是從目前核獲得 spinlock 到該 spinlock 成功轉給下個核的時間區段！這時間區段包括兩個部分，一是執行 lock/unlock 之間程式碼的時間 E，另一是 unlock 操作中消耗的時間，我們把這部分時間設為 R，現在的問題就變成根據上述資訊，求出 R 的表達式。

討論中有個假設，即我們設想實驗的平台對 cache coherence 中 update 的管理方式是點對點、循序的 unicast 方式，而非 broadcast 的方式。假設處理一個核的 update 時間為 c，那麼在 k 個核同時自旋等鎖的條件下，所有的中央處理器核的 cache line 全部更新的時間就是 $k\times c$，由於 ticket spinlock 具備嚴格順序，而 cache line update 的到達先後卻不可控制，因此下個獲得鎖的核的 cache line 得到更新的時間平均值為 $k\times c/2$，即平均在這個時間後，下個核即可成功獲取鎖，從 spin_lock 自旋狀態返回。因此我們可知：
$$S[k]={\displaystyle \frac{1}{E+{\displaystyle \frac{k\times c}{2}}}}$$

以上關於 $A[k]$ 和 $S[k]$ 的表達式非常好理解，可見請求的到達頻率，是 spinlock 的頻率是和空閒核數量的關聯，即不在自旋狀態的核數量成正比，顯然空閒核越多，請求越容易到達，相反，spin_unlock 的頻率，即 $S[k]$，則是和目前自旋狀態的核數量成反比的，至少是負相關的，因為自旋狀態的核越多，更新這麼多核的 cache line 的時間開銷就越大，這意味著服務頻率 $S[k]$ 就會越低。

有了上面基本的結論，搭配下面一個穩態 Markov chain 狀態轉換率守恆的基本原則，即可導出模型本身：

假設 P₀, P₁, P₂, …, P_n 是系統處在這 $n$ 個狀態的機率，顯然 $\sum P_k=1$。當系統處在穩態時，下方式子成立：
$$P_k\times A[k]=P_{k+1}\times S[k]$$

這是一個遞推的開始，我們可求出 $P_k$ 關於 $k$ 的表達式，然後模型裡的參數就可以去用實際值填充。最終透過上面的三個式子推導出來的公式為：
$$P_k={\displaystyle \frac{\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}i{P}_i$$

模型最終在於解釋歷史紀錄和預測未來表現，在上面的基礎上，我們導出一個加速比的概念，即在 $x$ 個 CPU 的系統中爭搶特定的 spinlock，CPU 總量 $x$ 中有多少 CPU 未處在自旋等鎖的狀態。顯然，它的值為：
$$S=x-C$$

隨著 $x$ 的增加，S 也增加，這意味著增加中央處理器核數量確實緩解 spinlock 帶來的序列化 (serial) 問題，但是不幸的是，情況並非如此。該模型顯示出的 ${\displaystyle \frac{S}{x}}$ 曲線顯示出當總核數 $x$ 增加到一定程度，加速比會斷崖跌落 (CPU 一多，one by one 的 cache line 操作太重太耗時)，這意味著在達到某種條件的情況下，增加核數反而會損害系統效能。

除了影響擴展能力，cache line 的操作超出預料有著巨大影響！

關於馬可夫鏈 spinlock 模型的推論

再看 $S[k]$ 的表達式：
$$S[k]={\displaystyle \frac{1}{E+{\displaystyle \frac{k\times c}{2}}}}$$

這個式子是限制 spinlock 擴展能力的根源。注意這裡的 $E$，它對 spinlock 整體擴展能力受限的程度的影響至關重要！我們進一步可將式子抽象為：
$$f(x)={\displaystyle \frac{1}{\alpha +x}}$$

然後我們來看一下 $x/y$
曲線的走勢：

回到我們的模型，$E$ 越大，cache coherence 時間線性增長的影響就越不明顯，只有在 $E$ 比較小時，我們才會深受 spinlock 擴展能力受限之害。然而 spinlock 的應用場合不就是 critical section 範圍很小之際嗎？

假設我們的 critical section 範圍確實很小，那麼 $S[k]$
和 $k$ 之間就近似反比關係，如此事態就嚴重多。它的根源在於 cache coherence 的時間是 $O(n)$ 的而不是常數級 $O(1)$，因此我們也就有了解決問題的方向。下一節詳述。

MCS spinlock 如何解決問題

問題已經很明確，如何迴避顯然已至關重要。

既然問題出在共用變數上自旋導致的 cache coherence 開銷過大，那改成在私有變數上自旋即可，這顯然是一個 $O(1)$ 的操作，替掉之前擴展能力有限的 $O(n)$ 操作即可。

為了做到這一點，需要重新設計 spinlock 的資料結構。本節所描述的新的 spinlock 正是 MCS spinlock，可參照 MCS locks and qspinlocks 一文。

讓我們從程式碼的角度來看為何 MCS spinlock 可解決 cache coherence 導致擴展能力受限的問題。

mcs spinlock 在 Linux 的實作在 kernel/locking/mcs_spinlock.h 檔案，不過直到 4.14 版，Linux 並沒有哪個子系統採用這個新的 spinlock，不管怎樣，既然程式碼在手，我們便可自行運用。

和 ticket spinlock 的描述一致：

• 定義 MCS spinlock

struct mcs_spinlock {
    struct mcs_spinlock *next; // 類似 ticket，競爭持有鎖的佇列
    int locked; /* 1 if lock acquired */ // 本地的自旋變數，不再是全域
};

可見其特點在於在自旋變數納入佇列實體本身。在 mcs spinlock 中，一個 mcs_spinlock 結構體的實例 (instance) 就是個佇列實體，它擁有自己的自旋變數 locked，即它只需要不斷查驗自身的 locked 變數即可。

• MCS spinlock 上鎖

/* 自身的佇列節點 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; 
    // (atomic) 執行 *lock = node 並返回原来的 *lock 
    prev = xchg(lock, node); 
    if (likely(prev == NULL))
        return; 

    // (atomic) 執行 prev->next = node;
    // 這相當於一個排入佇列的操作。記為(*) 
    WRITE_ONCE(prev->next, node); 
    while (0 == &node->locked)
        /* spin-wait */ ; 
}

• MCS spinlock 解鎖

/* 自己要傳入一個排入到 lock 的佇列中自身的節點物件 node
 * 解鎖操作即是 node 移出佇列並且主動將佇列中下一個物件的 locked 設定為 1
 */ 
void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node) { 
    // (atomic) 持有 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(); 
    } 
    // (atomic) 執行 next->locked = 1; 
    arch_mcs_spin_unlock_contended(&next->locked); 
}

如你所見，mcs_spin_unlock 操作僅操作 next 的 locked 欄位，後者屬於在某個 CPU 上自旋等待的 mcs spinlock 物件，不會觸發全域的 cache coherence 刷新！

上述的 mcs spinlock 實作之所以可解決因 cache coherence 而導致的開銷隨著處理器核數的增加線性增加的問題，就是因為一個簡單的動作，即傳球代替搶球。 ticket spinlock 的問題在於，既然已知誰是下一個持有鎖的等待者，為什麼不直接將控制權交給它呢？為什麼還要有一個全域盲搶的動作呢？

從前述程式碼列表中，也許你已發現 Linux 的 MCS spinlock 的實作議題：它的 API 改變，這意味著你無法對核心既有 ticket spinlock 進行無縫轉換。我們期望形如下方的函式:

void mcs_spin_lock(struct mcs_spinlock *lock);
void mcs_spin_unlock(struct mcs_spinlock *lock);

由於同個中央處理器核同時僅能等待一個 spinlock，這件事簡單，可如下實作：

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();
    
    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 的討論。

Aliworkqueue

針對 spinlock 改進策略的另一種體現，由阿里巴巴集團提交: aliworkqueue: Adaptive lock integration on multi-core platform

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

設計思維如 Fast asymmetric thread synchronization

Aliworkqueue 除了考慮到 spinlock 本身加鎖解鎖對 cache coherence 的影響，還考慮 spinlock 保護的 critical section 操作的共享資料讀寫對 cache coherence 的影響，如此一來，本文上述的 Markov chain 模型就要進行修訂，因為 critical section 的操作時間不再視作常數 $E$，而它也要作為一個和中央處理器核數相關的量參與到模型的構建中。