一、前言

該文章中的自旋鎖描述是基于比較老的內(nèi)核版本，那時(shí)候的自旋鎖還是ticket base鎖，而目前最新內(nèi)核中的自旋鎖已經(jīng)進(jìn)化成queued spinlock，因此需要一篇新的自旋鎖文檔來(lái)跟上時(shí)代。此外，本文將不再描述基本的API和應(yīng)用場(chǎng)景，主要的篇幅將集中在具體的自旋鎖實(shí)現(xiàn)上。順便說(shuō)一句，同時(shí)準(zhǔn)備一份linux5.10源碼是打開(kāi)本文的正確方式。如果不想下載源代碼，這個(gè)網(wǎng)址https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/tree/?h=v5.10.123可以瀏覽自旋鎖的源代碼。

由于自旋鎖可以在各種上下文中使用，因此本文中的thread是執(zhí)行線(xiàn)索的意思，表示進(jìn)程上下文、hardirq上下文、softirq上下文等多種執(zhí)行線(xiàn)索，而不是調(diào)度器中線(xiàn)程的意思。

二、簡(jiǎn)介

Spinlock是linux內(nèi)核中常用的一種互斥鎖機(jī)制，和mutex不同，當(dāng)無(wú)法持鎖進(jìn)入臨界區(qū)的時(shí)候，當(dāng)前執(zhí)行線(xiàn)索不會(huì)阻塞，而是不斷的自旋等待該鎖釋放。正因?yàn)槿绱?，自旋鎖也是可以用在中斷上下文的。也正是因?yàn)樽孕?，臨界區(qū)的代碼要求盡量的精簡(jiǎn)，否則在高競(jìng)爭(zhēng)場(chǎng)景下會(huì)浪費(fèi)寶貴的CPU資源。

1、代碼結(jié)構(gòu)

我們整理spinlock的代碼結(jié)構(gòu)如下：

最上層是通用自旋鎖代碼（體系結(jié)構(gòu)無(wú)關(guān)，平臺(tái)無(wú)關(guān)），這一層的代碼提供了兩種接口：spinlock接口和raw spinlock接口。在沒(méi)有配置PREEMPT_RT情況下，spinlock接口和raw spinlock接口是一毛一樣的，但是如果配置了PREEMPT_RT，spinlock接口走rt spinlock，底層是基于rtmutex的。也就是說(shuō)這時(shí)候的spinlock不再禁止搶占，不再自旋等待，而是使用了支持PI的睡眠鎖來(lái)實(shí)現(xiàn)，因此有了更好的實(shí)時(shí)性。而raw spinlock接口即便在配置了PREEMPT_RT下仍然保持傳統(tǒng)自旋鎖特性。

中間一層是區(qū)分SMP和UP的，在SMP和UP上，自旋鎖的實(shí)現(xiàn)是不一樣的。對(duì)于UP，自旋沒(méi)有意義，因此spinlock的上鎖和放鎖操作退化為preempt disable和enable。SMP平臺(tái)上，除了搶占操作之外還有正常自旋鎖的邏輯，具體如何實(shí)現(xiàn)自旋鎖邏輯是和底層的CPU architecture相關(guān)的，后面我們會(huì)詳細(xì)描述。

最底層的代碼是體系結(jié)構(gòu)相關(guān)的代碼，ARM64上，目前采用是qspinlock。和體系結(jié)構(gòu)無(wú)關(guān)的Qspinlock代碼抽象在qspinlock.c文件中，也就是本文重點(diǎn)要描述的內(nèi)容。

2、接口API

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

具體的接口API簡(jiǎn)單而直觀，這里就不再羅列了。

3、自旋鎖的演進(jìn)

自旋鎖的演進(jìn)過(guò)程如下：

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

如果thread4當(dāng)前持鎖，同一個(gè)cluster中的cpu7上的thread7和另外一個(gè)cluster中的thread0都在自旋等待鎖的釋放。當(dāng)thread4釋放鎖的時(shí)候，由于cpu7和cpu4的拓?fù)渚嚯x更近，thread7會(huì)有更高概率可以搶到自旋鎖，從而產(chǎn)生了不公平現(xiàn)象。

為了解決這個(gè)問(wèn)題，內(nèi)核工程師又開(kāi)發(fā)了ticket base的自旋鎖，但是這種自旋鎖在持鎖失敗的時(shí)候會(huì)對(duì)自旋鎖狀態(tài)數(shù)據(jù)next成員進(jìn)行++操作，當(dāng)CPU數(shù)據(jù)巨大并且競(jìng)爭(zhēng)激烈的時(shí)候，自旋鎖狀態(tài)數(shù)據(jù)對(duì)應(yīng)的cacheline會(huì)在不同cpu上跳來(lái)跳去，從而對(duì)性能產(chǎn)生影響，為了解決這個(gè)問(wèn)題，qspinlock產(chǎn)生了，下面的文章會(huì)集中在qspinlock的原理和實(shí)現(xiàn)上。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個(gè)人覺(jué)得比較好的學(xué)習(xí)書(shū)籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書(shū)、實(shí)戰(zhàn)項(xiàng)目及代碼)??

三、Qspinlock的數(shù)據(jù)結(jié)構(gòu)

1、Qspinlock

struct qspinlock定義如下（little endian）：

Qspinlock的數(shù)據(jù)結(jié)構(gòu)一共4個(gè)byte，不同的場(chǎng)景下，為了操作方便，我們可以從不同的視角來(lái)看這四個(gè)字節(jié)，示意圖如下：

Tail成員占2B，包括tail index（1617）和tail cpu（1831）兩個(gè)域。補(bǔ)充說(shuō)明一下，上圖是系統(tǒng)CPU的個(gè)數(shù)小于16k的時(shí)候的布局，如果CPU數(shù)據(jù)太大，tail需要擴(kuò)展，壓縮pending域的空間。這時(shí)候pending域占一個(gè)bit，其他的7個(gè)bit用于tail。之所以定義的如此復(fù)雜主要是為了操作方便，有時(shí)候我們需要對(duì)整個(gè)4B的spinlock val進(jìn)行操作（例如判斷空鎖需要直接判斷val是否為0值），有時(shí)候需要對(duì)pending+locked這兩個(gè)byte進(jìn)行操作（例如mcs node queue head需要自旋在pending+locked上），而有的時(shí)候又需要單獨(dú)對(duì)pending或者locked進(jìn)行設(shè)置，大家可以結(jié)合代碼體會(huì)owner的良苦用心。

拋開(kāi)這些復(fù)雜的union數(shù)據(jù)成員，實(shí)際上spinlock的4B由下面三個(gè)域組成：

2、MCS lock

MCS lock定義如下：

為了解決多個(gè)thread對(duì)spinlock的讀寫(xiě)造成的cache bouncing問(wèn)題，我們引入了per cpu的mcs lock，讓thread自旋在各自CPU的mcs lock，從而減少了緩存顛簸問(wèn)題，提升了性能。由于自旋鎖可能是嵌套的，因此mcs lock節(jié)點(diǎn)在每個(gè)CPU上是多個(gè)，具體如下圖所示：

在某個(gè)線(xiàn)程上下文，由于持A鎖失敗而進(jìn)入自旋，我們需要把該CPU上的mcs鎖節(jié)點(diǎn)掛入A spinlock的隊(duì)列。在這個(gè)自旋過(guò)程中，該CPU有可能發(fā)生軟中斷，在軟中斷處理函數(shù)中，我們?cè)噲D持B鎖，如果失敗，那么該cpu上的mcs鎖節(jié)點(diǎn)需要掛入B spinlock的隊(duì)列。在這樣的場(chǎng)景中，我們必須區(qū)分線(xiàn)程上下文和軟中斷上下文的mcs node。這樣復(fù)雜的嵌套最多有四層：線(xiàn)程上下文、軟中斷上下文、硬中斷上下文和NMI上下文。因此我們每個(gè)CPU實(shí)際上定義了多個(gè)mcs node節(jié)點(diǎn)（目前是四個(gè)），用來(lái)解決自旋鎖的嵌套問(wèn)題。

了解了上面的內(nèi)容之后，我們可以回頭看看tail成員。這個(gè)成員分成兩個(gè)部分，一個(gè)是cpu id加一（0表示隊(duì)列無(wú)節(jié)點(diǎn)），一個(gè)就是context index。這兩部分合起來(lái)可以確定一個(gè)mcs node對(duì)象。

四、Qspinlock的原理

1、Qspinlock狀態(tài)說(shuō)明

通過(guò)上面對(duì)qspinlock數(shù)據(jù)結(jié)構(gòu)的說(shuō)明我們可以知道，spinlock的狀態(tài)由locked、pending和tail三元組來(lái)表示。下面就是幾種狀態(tài)示例：

需要說(shuō)明的是tail block中的“n”和“*”表示了mcs node隊(duì)列的情況。n表示qspinlock只有一個(gè)mcs node，*表示qspinlock有若干個(gè)mcs node形成隊(duì)列，同時(shí)在競(jìng)爭(zhēng)spinlock。

2、Qspinlock中的狀態(tài)遷移

一個(gè)完整的qspinlock狀態(tài)遷移過(guò)程如下：

我們可以對(duì)照下一節(jié)的代碼來(lái)驗(yàn)證上面的這張狀態(tài)遷移圖。

五、Qspinlock的實(shí)現(xiàn)

1、獲取qspinlock

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

如果spinlock的值（指完整的4B數(shù)據(jù)，即spinlock的val成員）等于0，那么說(shuō)明是空鎖，那么調(diào)用線(xiàn)程可以持鎖進(jìn)入臨界區(qū)。這時(shí)候，spinlock的值被設(shè)置為1，即鎖處于locked狀態(tài)。如果快速路徑失敗，那么進(jìn)入慢速路徑。慢速路徑比較長(zhǎng)，我們分段解讀：

A、如果當(dāng)前spinlock的值只有pending比特被設(shè)定，那么說(shuō)明該spinlock正處于owner把鎖轉(zhuǎn)交給自旋鎖spinner的過(guò)程中。在這種情況下，我們需要重讀spinlock的值。當(dāng)然，如果持續(xù)重讀的結(jié)果仍然是僅pending比特被設(shè)定，那么在_Q_PENDING_LOOPS次循環(huán)讀之后放棄。

B、如果有其他的線(xiàn)程已經(jīng)自旋等待該spinlock（pending域被設(shè)置為1）或者自旋等待per cpu的MCS鎖上（pending域被設(shè)置為1并且設(shè)置了tail域也被設(shè)置），那么該線(xiàn)程需要掛入自旋等待隊(duì)列。否則說(shuō)明該線(xiàn)程是第一個(gè)等待持鎖的，那么不需要排隊(duì)，只要pending在自旋鎖上就OK了。我們先看看怎么pending自旋等待qspinlock代碼：

A、執(zhí)行至此tail+pending都是0，看起來(lái)我們應(yīng)該是第一個(gè)pending線(xiàn)程，通過(guò)queued_fetch_set_pending_acquire函數(shù)讀取了spinlock的舊值，同時(shí)設(shè)置pending比特標(biāo)記狀態(tài)。

B、在設(shè)置pending標(biāo)記位之后，我們需要再次檢查一下我們這里設(shè)置pending比特的時(shí)候，其他的競(jìng)爭(zhēng)者是否也修改了pending或者tail域。如果其他線(xiàn)程已經(jīng)搶先修改，那么本線(xiàn)程不能再pending在自旋鎖上了，而是需要回退pending設(shè)置（如果需要的話(huà)），并且掛入自旋等待隊(duì)列。如果沒(méi)有其他線(xiàn)程插入，那么當(dāng)前線(xiàn)程可以開(kāi)始自旋在qspinlock狀態(tài)，等待owner釋放鎖了：

A、至此，我們已經(jīng)成為合法的spinlock自旋者，通過(guò)atomic_cond_read_acquire函數(shù)自旋在spinlock的locked域，直到owner釋放spinlock。這里自旋并不是輪詢(xún)，而是通過(guò)WFE指令讓CPU停下來(lái)，降低功耗。當(dāng)owner釋放spinlock的時(shí)候會(huì)發(fā)送事件喚醒該CPU。

B、發(fā)現(xiàn)owner已經(jīng)釋放了鎖，那么清除pending標(biāo)記，同時(shí)設(shè)定locked標(biāo)記，持鎖成功，進(jìn)入臨界區(qū)。以上的代碼就是pending線(xiàn)程自旋等待進(jìn)入臨界區(qū)的代碼，下面我們?cè)僖黄鹂纯醋孕贛CS lock的情況：

當(dāng)不能pending在spinlock的時(shí)候，當(dāng)前執(zhí)行線(xiàn)索需要掛入自旋隊(duì)列，自旋在自己的mcs lock上。首先要進(jìn)行入隊(duì)前的準(zhǔn)備工作：一是要找到對(duì)應(yīng)的mcs node，其次要準(zhǔn)備好tail域要設(shè)置的值。

A、獲取mcs node的基地址

B、由于spin_lock可能會(huì)嵌套（在不同的自旋鎖上嵌套，如果同一個(gè)那么就是死鎖了）因此我們構(gòu)建了多個(gè)mcs node，每次遞進(jìn)一層。順便一提的是：當(dāng)index大于閥值的時(shí)候，我們會(huì)取消qspinlock機(jī)制，恢復(fù)原始自旋機(jī)制。

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

D、根據(jù)mcs node基地址和index找到對(duì)應(yīng)的mcs node

找到mcs node之后，我們需要掛入隊(duì)列，代碼如下：

A、初始化MCS lock為未持鎖狀態(tài)

B、試圖獲取鎖，很可能在上面的過(guò)程中，pending thread和owner thread都已經(jīng)離開(kāi)了臨界區(qū)，這時(shí)候如果持鎖成功，那么就可以長(zhǎng)驅(qū)直入，進(jìn)入臨界區(qū)。

C、修改qspinlock的tail域，old保存了舊值。如果這是隊(duì)列中的第一個(gè)節(jié)點(diǎn)，那么至此就結(jié)束了，如果之前tial域就有值，那么說(shuō)明有隊(duì)列中有其他waiter

A、如果等待隊(duì)列中已經(jīng)有了waiter，那么需要串聯(lián)起來(lái)，等待機(jī)會(huì)去自旋在spinlock上去。

B、建立新node和舊的等待隊(duì)列的關(guān)系

C、自旋在mcs lock上，等待locked狀態(tài)變成1。至此，我們已經(jīng)是處于mcs queue中的頭部

執(zhí)行至此，我們已經(jīng)獲得了MCS lock。在我們自旋等待的時(shí)候，可能其他的競(jìng)爭(zhēng)者也加入到鏈表了，next不再是null了（即我們不再是隊(duì)尾了）。因此這里需要更新next變量。由于本線(xiàn)程已經(jīng)獲取了自旋在spinlock的機(jī)會(huì)，那么需要

A、在獲取了MCS lock之后（排到了mcs node queue的頭部），我們獲準(zhǔn)了在spinlock上自旋。這里等待pending和owner離開(kāi)臨界區(qū)。

B、至此，我們獲取了spinlock，在進(jìn)入臨界區(qū)之前，我們需要解放自旋在mcs鎖的頭部節(jié)點(diǎn)。如果本mcs node是隊(duì)列中的最后一個(gè)節(jié)點(diǎn)，我們不需要處理mcs lock傳遞，直接試圖持鎖，如果成功，完成持鎖，進(jìn)入臨界區(qū)。如果mcs node隊(duì)列中仍然有節(jié)點(diǎn)，那么邏輯要更復(fù)雜一些，代碼如下：

A、如果本mcs node不是隊(duì)列尾部，那么不需要考慮競(jìng)爭(zhēng)，直接持spinlock

B、在進(jìn)入臨界區(qū)之前需要釋放下一個(gè)節(jié)點(diǎn)，讓其自旋在spinlock上。

把mcs lock傳遞給下一個(gè)節(jié)點(diǎn)

2、釋放qspinlock

釋放spinlock的代碼是queued_spin_unlock函數(shù)，非常的簡(jiǎn)單，就是把qspinlock的locked域設(shè)置為0。

六、小結(jié)

本文簡(jiǎn)單的介紹了linux內(nèi)核中的自旋鎖同步機(jī)制，在移動(dòng)環(huán)境的激烈競(jìng)爭(zhēng)場(chǎng)景中，自旋鎖的性能表現(xiàn)不盡如人意，無(wú)論是吞吐量還是延遲。產(chǎn)生這個(gè)問(wèn)題的主要原因有兩個(gè)：一是內(nèi)核中自旋鎖的設(shè)計(jì)基本上是僅考慮SMP硬件平臺(tái)，在目前異構(gòu)的手機(jī)平臺(tái)上表現(xiàn)不佳。二是由于內(nèi)核自旋鎖是基于公平的原則來(lái)設(shè)計(jì)，而手機(jī)場(chǎng)景中從來(lái)不是追求公平的，它看中的是響應(yīng)延遲。目前OPPO內(nèi)核團(tuán)隊(duì)正在進(jìn)行內(nèi)核自旋鎖的優(yōu)化課題，我們也歡迎對(duì)此有興趣的小伙伴加入我們，一起感受這份優(yōu)化內(nèi)核帶來(lái)的快樂(lè)。

原文作者：內(nèi)核工匠