在linux kernel的實現中，經常會遇到這樣的場景：共享數據被中斷上下文和進程上下文訪問，該如何保護呢？如果只有進程上下文的訪問，那麼可以考慮使用semaphore或者mutex的鎖機制，但是現在中斷上下文也參和進來，那些可以導致睡眠的lock就不能使用了，這時候，可以考慮使用spin lock。本文主要介紹了linux kernel中的spin lock的原理以及代碼實現。由於spin lock是architecture dependent代碼，因此，我們在第四章討論了ARM32和ARM64上的實現細節。
二、工作原理
1、spin lock的特點
我們可以總結spin lock的特點如下：
（1）spin lock是一種死等的鎖機制。當發生訪問資源衝突的時候，可以有兩個選擇：一個是死等，一個是掛起當前進程，調度其他進程執行。spin lock是一種死等的機制，當前的執行thread會不斷的重新嘗試直到獲取鎖進入臨界區。
（2）只允許一個thread進入。semaphore可以允許多個thread進入，spin lock不行，一次只能有一個thread獲取鎖並進入臨界區，其他的thread都是在門口不斷的嘗試。
（3）執行時間短。由於spin lock死等這種特性，因此它使用在那些代碼不是非常複雜的臨界區（當然也不能太簡單，否則使用原子操作或者其他適用簡單場景的同步機制就OK了），如果臨界區執行時間太長，那麼不斷在臨界區門口“死等”的那些thread是多麼的浪費CPU啊（當然，現代CPU的設計都會考慮同步原語的實現，例如ARM提供了WFE和SEV這樣的類似指令，避免CPU進入busy loop的悲慘境地）
（4）可以在中斷上下文執行。由於不睡眠，因此spin lock可以在中斷上下文中適用。
2、 場景分析
對於spin lock，其保護的資源可能來自多個CPU CORE上的進程上下文和中斷上下文的中的訪問，其中，進程上下文包括：用戶進程通過系統調用訪問，內核線程直接訪問，來自workqueue中work function的訪問（本質上也是內核線程）。中斷上下文包括：HW interrupt context（中斷handler）、軟中斷上下文（soft irq，當然由於各種原因，該softirq被推遲到softirqd的內核線程中執行的時候就不屬於這個場景了，屬於進程上下文那個分類了）、timer的callback函數（本質上也是softirq）、tasklet（本質上也是softirq）。
先看最簡單的單CPU上的進程上下文的訪問。如果一個全局的資源被多個進程上下文訪問，這時候，內核如何交錯執行呢？對於那些沒有打開preemptive選項的內核，所有的系統調用都是串行化執行的，因此不存在資源爭搶的問題。如果內核線程也訪問這個全局資源呢？本質上內核線程也是進程，類似普通進程，只不過普通進程時而在用戶態運行、時而通過系統調用陷入內核執行，而內核線程永遠都是在內核態運行，但是，結果是一樣的，對於non-preemptive的linux kernel，只要在內核態，就不會發生進程調度，因此，這種場景下，共享數據根本不需要保護（沒有併發，談何保護呢）。如果時間停留在這裡該多麼好，單純而美好，在繼續前進之前，讓我們先享受這一刻。
當打開premptive選項後，事情變得複雜了，我們考慮下面的場景：
（1）進程A在某個系統調用過程中訪問了共享資源R
（2）進程B在某個系統調用過程中也訪問了共享資源R
會不會造成衝突呢？假設在A訪問共享資源R的過程中發生了中斷，中斷喚醒了沉睡中的，優先級更高的B，在中斷返回現場的時候，發生進程切換，B啟動執行，並通過系統調用訪問了R，如果沒有鎖保護，則會出現兩個thread進入臨界區，導致程序執行不正確。OK，我們加上spin lock看看如何：A在進入臨界區之前獲取了spin lock，同樣的，在A訪問共享資源R的過程中發生了中斷，中斷喚醒了沉睡中的，優先級更高的B，B在訪問臨界區之前仍然會試圖獲取spin lock，這時候由於A進程持有spin lock而導致B進程進入了永久的spin……怎麼破？linux的kernel很簡單，在A進程獲取spin lock的時候，禁止本CPU上的搶佔（上面的永久spin的場合僅僅在本CPU的進程搶佔本CPU的當前進程這樣的場景中發生）。如果A和B運行在不同的CPU上，那麼情況會簡單一些：A進程雖然持有spin lock而導致B進程進入spin狀態，不過由於運行在不同的CPU上，A進程會持續執行並會很快釋放spin lock，解除B進程的spin狀態。
多CPU core的場景和單核CPU打開preemptive選項的效果是一樣的，這裡不再贅述。
我們繼續向前分析，現在要加入中斷上下文這個因素。訪問共享資源的thread包括：
（1）運行在CPU0上的進程A在某個系統調用過程中訪問了共享資源R
（2）運行在CPU1上的進程B在某個系統調用過程中也訪問了共享資源R
（3）外設P的中斷handler中也會訪問共享資源R
在這樣的場景下，使用spin lock可以保護訪問共享資源R的臨界區嗎？我們假設CPU0上的進程A持有spin lock進入臨界區，這時候，外設P發生了中斷事件，並且調度到了CPU1上執行，看起來沒有什麼問題，執行在CPU1上的handler會稍微等待一會CPU0上的進程A，等它立刻臨界區就會釋放spin lock的，但是，如果外設P的中斷事件被調度到了CPU0上執行會怎麼樣？CPU0上的進程A在持有spin lock的狀態下被中斷上下文搶佔，而搶佔它的CPU0上的handler在進入臨界區之前仍然會試圖獲取spin lock，悲劇發生了，CPU0上的P外設的中斷handler永遠的進入spin狀態，這時候，CPU1上的進程B也不可避免在試圖持有spin lock的時候失敗而導致進入spin狀態。為了解決這樣的問題，linux kernel採用了這樣的辦法：如果涉及到中斷上下文的訪問，spin lock需要和禁止本CPU上的中斷聯合使用。
linux kernel中提供了豐富的bottom half的機制，雖然同屬中斷上下文，不過還是稍有不同。我們可以把上面的場景簡單修改一下：外設P不是中斷handler中訪問共享資源R，而是在的bottom half中訪問。使用spin lock+禁止本地中斷當然是可以達到保護共享資源的效果，但是使用牛刀來殺雞似乎有點小題大做，這時候disable bottom half就OK了。
最後，我們討論一下中斷上下文之間的競爭。同一種中斷handler之間在uni core和multi core上都不會並行執行，這是linux kernel的特性。如果不同中斷handler需要使用spin lock保護共享資源，對於新的內核（不區分fast handler和slow handler），所有handler都是關閉中斷的，因此使用spin lock不需要關閉中斷的配合。bottom half又分成softirq和tasklet，同一種softirq會在不同的CPU上併發執行，因此如果某個驅動中的sofirq的handler中會訪問某個全局變量，對該全局變量是需要使用spin lock保護的，不用配合disable CPU中斷或者bottom half。tasklet更簡單，因為同一種tasklet不會多個CPU上併發，具體我就不分析了，大家自行思考吧。
三、通用代碼實現
1、文件整理
和體系結構無關的代碼如下：
（1）include/linux/spinlock_types.h。這個頭文件定義了通用spin lock的基本的數據結構（例如spinlock_t）和如何初始化的接口（DEFINE_SPINLOCK）。這裡的“通用”是指不論SMP還是UP都通用的那些定義。
（2）include/linux/spinlock_types_up.h。這個頭文件不應該直接include，在include/linux/spinlock_types.h文件會根據系統的配置（是否SMP）include相關的頭文件，如果UP則會include該頭文件。這個頭文定義UP系統中和spin lock的基本的數據結構和如何初始化的接口。當然，對於non-debug版本而言，大部分struct都是empty的。
（3）include/linux/spinlock.h。這個頭文件定義了通用spin lock的接口函數聲明，例如spin_lock、spin_unlock等，使用spin lock模塊接口API的驅動模塊或者其他內核模塊都需要include這個頭文件。
（4）include/linux/spinlock_up.h。這個頭文件不應該直接include，在include/linux/spinlock.h文件會根據系統的配置（是否SMP）include相關的頭文件。這個頭文件是debug版本的spin lock需要的。
（5）include/linux/spinlock_api_up.h。同上，只不過這個頭文件是non-debug版本的spin lock需要的
（6）linux/spinlock_api_smp.h。SMP上的spin lock模塊的接口聲明
（7）kernel/locking/spinlock.c。SMP上的spin lock實現。
頭文件有些凌亂，我們對UP和SMP上spin lock頭文件進行整理：
2、數據結構
根據第二章的分析，我們可以基本可以推斷出spin lock的實現。首先定義一個spinlock_t的數據類型，其本質上是一個整數值（對該數值的操作需要保證原子性），該數值表示spin lock是否可用。初始化的時候被設定為1。當thread想要持有鎖的時候調用spin_lock函數，該函數將spin lock那個整數值減去1，然後進行判斷，如果等於0，表示可以獲取spin lock，如果是負數，則說明其他thread的持有該鎖，本thread需要spin。
內核中的spinlock_t的數據類型定義如下：
<code>typedef struct spinlock {
struct raw_spinlock rlock;
} spinlock_t;
typedef struct raw_spinlock {
arch_spinlock_t raw_lock;
} raw_spinlock_t;/<code>由於各種原因（各種鎖的debug、鎖的validate機制，多平臺支持什麼的），spinlock_t的定義沒有那麼直觀，為了讓事情簡單一些，我們去掉那些繁瑣的成員。struct spinlock中定義了一個struct raw_spinlock的成員，為何會如此呢？好吧，我們又需要回到kernel歷史課本中去了。在舊的內核中（比如我熟悉的linux 2.6.23內核），spin lock的命令規則是這樣：
通用（適用於各種arch）的spin lock使用spinlock_t這樣的type name，各種arch定義自己的struct raw_spinlock。聽起來不錯的主意和命名方式，直到linux realtime tree（PREEMPT_RT）提出對spinlock的挑戰。real time linux是一個試圖將linux kernel增加硬實時性能的一個分支（你知道的，linux kernel mainline只是支持soft realtime），多年來，很多來自realtime branch的特性被merge到了mainline上，例如：高精度timer、中斷線程化等等。realtime tree希望可以對現存的spinlock進行分類：一種是在realtime kernel中可以睡眠的spinlock，另外一種就是在任何情況下都不可以睡眠的spinlock。分類很清楚但是如何起名字？起名字絕對是個技術活，起得好了事半功倍，可維護性好，什麼文檔啊、註釋啊都素那浮雲，閱讀代碼就是享受，如沐春風。起得不好，註定被後人唾棄，或者拖出來吊打（這讓我想起給我兒子起名字的那段不堪回首的歲月……）。最終，spin lock的命名規範定義如下：
（1）spinlock，在rt linux（配置了PREEMPT_RT）的時候可能會被搶佔（實際底層可能是使用支持PI（優先級翻轉）的mutext）。
（2）raw_spinlock，即便是配置了PREEMPT_RT也要頑強的spin
（3）arch_spinlock，spin lock是和architecture相關的，arch_spinlock是architecture相關的實現
對於UP平臺，所有的arch_spinlock_t都是一樣的，定義如下：
<code>typedef struct { } arch_spinlock_t;
/<code>什麼都沒有，一切都是空啊。當然，這也符合前面的分析，對於UP，即便是打開的preempt選項，所謂的spin lock也不過就是disable preempt而已，不需定義什麼spin lock的變量。
對於SMP平臺，這和arch相關，我們在下一節描述
spin_lock的代碼如下：
static inline void spin_lock(spinlock_t *lock)
{
raw_spin_lock(&lock->rlock);
}
當然，在linux mainline代碼中，spin_lock和raw_spin_lock是一樣的，在realtime linux patch中，spin_lock應該被換成可以sleep的版本，當然具體如何實現我沒有去看（也許直接使用了Mutex，畢竟它提供了優先級繼承特性來解決了優先級翻轉的問題），有興趣的讀者可以自行閱讀，我們這裡重點看看（本文也主要focus這個主題）真正的，不睡眠的spin lock，也就是是raw_spin_lock，代碼如下：
<code>#define raw_spin_lock(lock) _raw_spin_lock(lock)
UP中的實現：
#define _raw_spin_lock(lock) __LOCK(lock)
#define __LOCK(lock) \\
do { preempt_disable(); ___LOCK(lock); } while (0)
SMP的實現：
void __lockfunc _raw_spin_lock(raw_spinlock_t *lock)
{
__raw_spin_lock(lock);
}
static inline void __raw_spin_lock(raw_spinlock_t *lock)
{
preempt_disable();
spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
}/<code>
UP中很簡單，本質上就是一個preempt_disable而已，和我們在第二章中分析的一致。SMP中稍顯複雜，preempt_disable當然也是必須的，spin_acquire可以略過，這是和運行時檢查鎖的有效性有關的，如果沒有定義CONFIG_LOCKDEP其實就是空函數。如果沒有定義CONFIG_LOCK_STAT（和鎖的統計信息相關），LOCK_CONTENDED就是調用do_raw_spin_lock而已，如果沒有定義CONFIG_DEBUG_SPINLOCK，它的代碼如下：
<code>static inline void do_raw_spin_lock(raw_spinlock_t *lock) __acquires(lock)
{
__acquire(lock);
arch_spin_lock(&lock->raw_lock);
}/<code>
四、ARM平臺的細節
代碼位於arch/arm/include/asm/spinlock.h和spinlock_type.h，和通用代碼類似，spinlock_type.h定義ARM相關的spin lock定義以及初始化相關的宏；spinlock.h中包括了各種具體的實現。
1、回憶過去
在分析新的spin lock代碼之前，讓我們先回到2.6.23版本的內核中，看看ARM平臺如何實現spin lock的。和arm平臺相關spin lock數據結構的定義如下（那時候還是使用raw_spinlock_t而不是arch_spinlock_t）：
<code>typedef struct {
volatile unsigned int lock;
} raw_spinlock_t;/<code>一個整數就OK了，0表示unlocked，1表示locked。配套的API包括__raw_spin_lock和__raw_spin_unlock。__raw_spin_lock會持續判斷lock的值是否等於0，如果不等於0（locked）那麼其他thread已經持有該鎖，本thread就不斷的spin，判斷lock的數值，一直等到該值等於0為止，一旦探測到lock等於0，那麼就設定該值為1，表示本thread持有該鎖了，當然，這些操作要保證原子性，細節和exclusive版本的ldr和str（即ldrex和strexeq）相關，這裡略過。立刻臨界區後，持鎖thread會調用__raw_spin_unlock函數是否spin lock，其實就是把0這個數值賦給lock。
這個版本的spin lock的實現當然可以實現功能，而且在沒有衝突的時候表現出不錯的性能，不過存在一個問題：不公平。也就是所有的thread都是在無序的爭搶spin lock，誰先搶到誰先得，不管thread等了很久還是剛剛開始spin。在衝突比較少的情況下，不公平不會體現的特別明顯，然而，隨著硬件的發展，多核處理器的數目越來越多，多核之間的衝突越來越劇烈，無序競爭的spinlock帶來的performance issue終於浮現出來，根據Nick Piggin的描述：多麼的不公平，有些可憐的thread需要飢餓的等待1000000次。本質上無序競爭從概率論的角度看應該是均勻分佈的，不過由於硬件特性導致這麼嚴重的不公平，我們來看一看硬件block：
lock本質上是保存在main memory中的，由於cache的存在，當然不需要每次都有訪問main memory。在多核架構下，每個CPU都有自己的L1 cache，保存了lock的數據。假設CPU0獲取了spin lock，那麼執行完臨界區，在釋放鎖的時候會調用smp_mb invalide其他忙等待的CPU的L1 cache，這樣後果就是釋放spin lock的那個cpu可以更快的訪問L1cache，操作lock數據，從而大大增加的下一次獲取該spin lock的機會。
2、回到現在：arch_spinlock_t
ARM平臺中的arch_spinlock_t定義如下（little endian）：
typedef struct {
union {
u32 slock;
struct __raw_tickets {
u16 owner;
u16 next;
} tickets;
};
} arch_spinlock_t;
本來以為一個簡單的整數類型的變量就搞定的spin lock看起來沒有那麼簡單，要理解這個數據結構，需要了解一些ticket-based spin lock的概念。如果你有機會去九毛九去排隊吃飯（聲明：不是九毛九的飯託，僅僅是喜歡麵食而常去吃而已）就會理解ticket-based spin lock。大概是因為便宜，每次去九毛九總是無法長驅直入，門口的笑容可掬的靚女會給一個ticket，上面寫著15號，同時會告訴你，當前狀態是10號已經入席，11號在等待。
回到arch_spinlock_t，這裡的owner就是當前已經入席的那個號碼，next記錄的是下一個要分發的號碼。下面的描述使用普通的計算機語言和在九毛九就餐（假設九毛九隻有一張餐桌）的例子來進行描述，估計可以讓吃貨更有興趣閱讀下去。最開始的時候，slock被賦值為0，也就是說owner和next都是0，owner和next相等，表示unlocked。當第一個個thread調用spin_lock來申請lock（第一個人就餐）的時候，owner和next相等，表示unlocked，這時候該thread持有該spin lock（可以擁有九毛九的唯一的那個餐桌），並且執行next++，也就是將next設定為1（再來人就分配1這個號碼讓他等待就餐）。也許該thread執行很快（吃飯吃的快），沒有其他thread來競爭就調用spin_unlock了（無人等待就餐，生意慘淡啊），這時候執行owner++，也就是將owner設定為1（表示當前持有1這個號碼牌的人可以就餐）。姍姍來遲的1號獲得了直接就餐的機會，next++之後等於2。1號這個傢伙吃飯巨慢，這是不文明現象（thread不能持有spin lock太久），但是存在。又來一個人就餐，分配當前next值的號碼2，當然也會執行next++，以便下一個人或者3的號碼牌。持續來人就會分配3、4、5、6這些號碼牌，next值不斷的增加，但是owner巋然不動，直到欠扁的1號吃飯完畢（調用spin_unlock），釋放飯桌這個唯一資源，owner++之後等於2，表示持有2那個號碼牌的人可以進入就餐了。
3、接口實現
同樣的，這裡也只是選擇一個典型的API來分析，其他的大家可以自行學習。我們選擇的是arch_spin_lock，其ARM32的代碼如下：
<code>static inline void arch_spin_lock(arch_spinlock_t *lock)
{
unsigned long tmp;
u32 newval;
arch_spinlock_t lockval;
prefetchw(&lock->slock);－－－－－－－－－－－－－－－－－－－－－－－－（1）
__asm__ __volatile__(
"1: ldrex %0, [%3]\\n"－－－－－－－－－－－－－－－－－－－－－－－－－（2）
" add %1, %0, %4\\n"
" strex %2, %1, [%3]\\n"－－－－－－－－－－－－－－－－－－－－－－－－（3）
" teq %2, #0\\n"－－－－－－－－－－－－－－－－－－－－－－－－－－－－（4）
" bne 1b"
: "=&r" (lockval), "=&r" (newval), "=&r" (tmp)
: "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
: "cc");
while (lockval.tickets.next != lockval.tickets.owner) {－－－－－－－－－－－－（5）
wfe();－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－（6）
lockval.tickets.owner = ACCESS_ONCE(lock->tickets.owner);－－－－－－（7）
}
smp_mb();－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－（8）
}/<code>
（1）和preloading cache相關的操作，主要是為了性能考慮
（2）將slock的值保存在lockval這個臨時變量中
（3）將spin lock中的next加一
（4）判斷是否有其他的thread插入。更具體的細節參考Linux內核同步機制之（一）：原子操作中的描述
（5）判斷當前spin lock的狀態，如果是unlocked，那麼直接獲取到該鎖
（6）如果當前spin lock的狀態是locked，那麼調用wfe進入等待狀態。更具體的細節請參考ARM WFI和WFE指令中的描述。
（7）其他的CPU喚醒了本cpu的執行，說明owner發生了變化，該新的own賦給lockval，然後繼續判斷spin lock的狀態，也就是回到step 5。
（8）memory barrier的操作，具體可以參考memory barrier中的描述。
arch_spin_lock函數ARM64的代碼（來自4.1.10內核）如下：
<code>static inline void arch_spin_lock(arch_spinlock_t *lock)
{
unsigned int tmp;
arch_spinlock_t lockval, newval;
asm volatile(
/* Atomically increment the next ticket. */
" prfm pstl1strm, %3\\n"
"1: ldaxr %w0, %3\\n"－－－－－（A）－－－－－－－－－－－lockval = lock
" add %w1, %w0, %w5\\n"－－－－－－－－－－－－－newval ＝ lockval + (1 << 16)，相當於next++
" stxr %w2, %w1, %3\\n"－－－－－－－－－－－－－－lock ＝ newval
" cbnz %w2, 1b\\n"－－－－－－－－－－－－－－是否有其他PE的執行流插入？有的話，重來。
/* Did we get the lock? */
" eor %w1, %w0, %w0, ror #16\\n"－－lockval中的next域就是自己的號碼牌，判斷是否等於owner
" cbz %w1, 3f\\n"－－－－－－－－－－－－－－－－如果等於，持鎖進入臨界區
/*
* No: spin on the owner. Send a local event to avoid missing an
* unlock before the exclusive load.
*/
" sevl\\n"
"2: wfe\\n"－－－－－－－－－－－－－－－－－－－－否則進入spin
" ldaxrh %w2, %4\\n"－－－－（A）－－－－－－－－－其他cpu喚醒本cpu，獲取當前owner值
" eor %w1, %w2, %w0, lsr #16\\n"－－－－－－－－－自己的號碼牌是否等於owner？
" cbnz %w1, 2b\\n"－－－－－－－－－－如果等於，持鎖進入臨界區，否者回到2，即繼續spin
/* We got the lock. Critical section starts here. */
"3:"
: "=&r" (lockval), "=&r" (newval), "=&r" (tmp), "+Q" (*lock)
: "Q" (lock->owner), "I" (1 << TICKET_SHIFT)
: "memory");
}/<code>
基本的代碼邏輯的描述都已經嵌入代碼中，這裡需要特別說明的有兩個知識點：
（1）Load-Acquire/Store-Release指令的應用。Load-Acquire/Store-Release指令是ARMv8的特性，在執行load和store操作的時候順便執行了memory barrier相關的操作，在spinlock這個場景，使用Load-Acquire/Store-Release指令代替dmb指令可以節省一條指令。上面代碼中的（A）就標識了使用Load-Acquire指令的位置。Store-Release指令在哪裡呢？在arch_spin_unlock中，這裡就不貼代碼了。Load-Acquire/Store-Release指令的作用如下：
－Load-Acquire可以確保系統中所有的observer看到的都是該指令先執行，然後是該指令之後的指令（program order）再執行
－Store-Release指令可以確保系統中所有的observer看到的都是該指令之前的指令（program order）先執行，Store-Release指令隨後執行
（2）第二個知識點是關於在arch_spin_unlock代碼中為何沒有SEV指令？關於這個問題可以參考ARM ARM文檔中的Figure B2-5，這個圖是PE（n）的global monitor的狀態遷移圖。當PE（n）對x地址發起了exclusive操作的時候，PE（n）的global monitor從open access遷移到exclusive access狀態，來自其他PE上針對x（該地址已經被mark for PE（n））的store操作會導致PE（n）的global monitor從exclusive access遷移到open access狀態，這時候，PE（n）的Event register會被寫入event，就好象生成一個event，將該PE喚醒，從而可以省略一個SEV的指令。
閱讀更多 餘生做酒長醉不憂 的文章
