Linux內核同步機制:spin lock

在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頭文件進行整理:


Linux內核同步機制: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相關,我們在下一節描述


Linux內核同步機制:spin lock

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:


Linux內核同步機制:spin lock

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的指令。


分享到:


相關文章: