Spinlock的用法

在這篇文章中，我將會介紹 Kernel 提供用來使用 spinlock 的 function。除此之外，我還會告訴各位，為何在 SMP 的環境裡，使用 spinlock 會比將所有 CPU 的中斷 disable 這個方法來的有效率，我也會告訴各位如何針對不同的使用需求，使 spinlock 的 cost 再降低，進而使系統的效能更好...

前言

在 Linux Kernel 裡有著許多重要的資料結構，這些資料在作業系統的運作中扮演著舉足輕重的角色。然而，Linux 是個多任務的作業系統，也就是在同一時間裡可以同時有許多的行程在執行，所以，很有可能某個行程在依序讀取 inode list，同時卻又有另一個在 inode list 裡加入新的 inode，這會造成什?情形呢？這會造成 inode list 的不穩定。所以，在 Kernel 裡，我們需要一個機制，可以使得當我們在修改某個重要的資料結構時，不能被中斷，即使被中斷了，這個資料結構由於還沒修改完，別的行程也都不能去讀取和修改它。Linux Kernel提供了 spinlock 這個機制可以使我們做到這樣的功能。

有的人會想到當我們在修改某個重要的資料結構時，將中斷都 disable 掉就好了，等修改完了再將中斷 enable 不就得了，何必還要再提供一個 spinlock 來做同樣的事。在 uni-processor 的環境底下，的確是如此。所謂 uni-processor 就是指只有一個 CPU 的電腦，但是在SMP的環境下就不是這麼一回事了。

我們知道現在 Linux 已經有支持 SMP，也就是可以使用多顆 CPU 來加快系統的速度，如果當我們在修改重要的資料結構時，將執行修改工作的 CPU 中斷 disable 掉的話，只有目前的這個 CPU 的執行不會被中斷，在 SMP 環境下，還有別的 CPU 正同時運作，如果別的 CPU 也去修改這個資料結構的話，就會造成同時有兩個 CPU 在修改它，不穩定性就會產生。解決方法是將全部的 CPU 中斷都 disable 掉，等修改完之後，再全部都 enable 起來。但是這樣的做法其 cost 會很大，整個系統的效能會 down 下來。因此，Linux Kernel 才會提供 spinlock 這樣的機制，它不會將全部 CPU 的中斷 disable 掉，所以效率比上述的方法好，但同時卻又能確保資料的穩定性，不會有某個行程在修改它，另外又有一個行程在讀取或修改它的情形發生。

在這篇文章中，我將會介紹 Kernel 提供用來使用 spinlock 的 function。除此之外，我還會告訴各位，為何在 SMP 的環境裡，使用 spinlock 會比將所有 CPU 的中斷 disable 這個方法來的有效率，我也會告訴各位如何針對不同的使用需求，使 spinlock 的 cost 再降低，進而使系統的效能更好。

spinlock的資料結構

spinlock 的資料結構在 Linux底下是以 spinlock_t 來表示的，在 SMP 和 UP(uni-processor)環境底下兩者的欄位有一些差異，其實在 UP 底下 spinlock_t 可以說是一個空的結構，空就是空的，為何要說"可以說是空的"呢？這是因為 gcc 版本的問題，gcc 在 2.8 版以前結構的內容必須不能是空的，而在 2.8 版之後就可以，所以在 UP 環境底下，會根據 gcc 的版本而設定不同的 spinlock_t 結構欄位，但基本上，在 UP 環境底下，是根本不會用到 spinlock_t 結構裡的欄位的，詳情請見以下諸節即可瞭解。

由於 spinlock 主要是用在SMP的環境底下，所以，以下我們就只針對在SMP環境底下的 spinlock_t 結構來討論，它的結構內容是這樣子的：
typedef struct {
volatile unsigned int lock;
} spinlock t;

說穿了，不過就是一個 unsigned int 型別的變數而已，但可不要小看這小小的變數，螺絲釘雖小，功能卻是不可忽視的。

使用 spinlock
spinlock t xxx lock = SPIN_LOCK_UNLOCKED;
unsigned long flags;

spin lock irqsave (&xxx lock, flags)
...critical section...
spin unlock irqrestore (&xxx lock, flags)


這一組的函式在使用上是最保險的，用的頻率也算是最多的。首先在使用前，必須先宣告一個 spinlock_t 型別的變數，並把初始值設為 SPIN_LOCK_UNLOCKED。除此之外，還必須有一個unsigned long型別的變數，這個變數是用來將 CPU 的 flag（旗標）儲存起來的，等 critical section 執行完了，再把 flag 的值設回到系統裡。使用上是很簡單明白的。這兩個 function 除了可以在 SMP 的環境下使用外，在UP的環境裡也是同樣可行的，接下來，我們來看看它們程序碼是怎?寫的。

在 這個檔案裡定義了 spin_lock_irqsave() 及 spin_lock_irqrestore() 這兩個 function。
#define spin_lock_irqsave(lock，flags)
do { local_irq_save(flags); spin_lock(lock); } while (0)

#define spin_unlock_irqrestore(lock，flags)
do { spin_unlock(lock); local_irq_restore(flags); } while (0)

local_irq_save(flags) 做的事就是將 CPU 的 flag 值先儲存到 flags 變數里，然後將 CPU 的中斷 diable 掉。這裡將 CPU 的中斷 disable 是指將執行這段 code 的 CPU，並不是指全部的 CPU。 也就是說它只會 disable local CPU 的中斷。我們可以在裡看到這樣的程序碼：

#define local_irq_save(x) __asm__ __volatile__("pushfl ; popl %0 ;
cli":"=g" (x): /* no input */ :"memory")
#define local_irq_restore(x) __asm__ __volatile__("pushl %0 ; popfl"
/* no output */ :"g" (x):"memory")

至於 local_irq_restore(flags) 從字面上可以很清楚的看出來，只是將 flags 裡的值再設回 CPU 的 flag 裡而已。至於 spin_lock(lock) 和 spin_unlock(lock) 這兩個函式，在 SMP 和在 UP 的環境底下則會擴展成不同的樣子。首先先看到這個檔案的下半部。
#ifdef __SMP__
#include <asm/spinlock.h>

#else /* !SMP */
.......
#endif

在 SMP 的環境底下，SMP 這個constant被會 set。而在 UP 底下則不會，所以，如果要看 UP 底下 spin_lock(lock) 會變成怎?樣子，就必須來看看 #else /* !SMP */ 和 #endif 之間的程序碼。

UP 環境下的 Implementation

我們先來看看在 UP 的環境下， spin_lock(lock) 會變成什?樣子。

#define spin_lock(x) (void)lock
#define spin_unlock(x) do {} while(0)

簡單吧，根本什麼事都沒有做，所以，在 UP 的環境底下，我們如果將上面那段 spinlock 的使用擴展開來的話，會變成下面這個樣子。

spinlock_t xxx_lock = SPIN_LOCK_UNLOCKED;
unsigned long flags;

local_save_flags(flags); cli();
... critical section ...
local_restore_flags(flags);

而這也正是在 UP 環境下，用來保護重要資料結構的寫法。這也就是為什?在介紹spinlock_t 的結構內容時，我們說在UP環境底下這個結構就算是空的也不會影響到 spinlock 的功效，因為根本沒用到裡面的欄位，但是在 SMP 底下，這就很重要了。

SMP 環境下的 Implementation

在 SMP 的環境底下， spin_lock() 和 spin_unlock() 這兩個函式的原始碼是放在。

extern inline void spin_lock(spinlock_t *plock)
{
__asm__ __volatile__(
spin_lock_string
:"=m" (__dummy_lock(plock)));
}


其實，這段程序碼是經過我削減後的，至於削減掉的程序碼是用來做 debug 的，所以，就不列出來，有興趣的朋友不彷自行去看看。在上圖中，spin_lock_string 是一個 macro，加上 __asm 語法，我將它展開成下面這個樣子：

extern inline void spin_lock(spinlock_t *plock)
{
1:
lock ; btsl $0,plock;
jc 2f;
.section .text.lock,"ax"
2:
testb $1,plock;
rep;nop;
jne 2b;
jmp 1b;
.previous
}


讓我們來看看 spin_lock() 這段組合語言是什?意思。在 Linux 底下，組合語言是用 AT&T 的語法，跟平常我們在 PC 底下使用的 Microsoft 語法不相同，主要的差別是 source 與 destination 的位置相反。基本上，spinlock 有兩種狀態，第一種被鎖住的狀態（lock），第二種則是沒被鎖住的狀態（unlock）；當 spinlock 被鎖住時，spinlock_t.lock 會被設為 1，當沒被鎖時，則會設回 0，各位可以去看我們之前所列出來的使用方法，它會將 spinlock_t 結構的初始值設為 SPIN_LOCK_UNLOCK，現在再來看看這個 constant 的值，可以發現它其實就是將 spinlock_t.lock 設為 0 而已。

#define SPIN_LOCK_UNLOCKED (spinlock_t) { 0 }

所以，檢查其狀態就變成了 spin_lock() 的首要工作，如果已被鎖住，則 CPU 就不能去使用它所保護的資料結構，而如果沒上鎖，則可以從 spin_lock() 傳回，接下去使用它所保護的資料。所以，檢查其狀態我們可以檢查 spinlock_t.lock 的第 0 個 bit。btsl $0, plock 會將 plock 的第 0 個 bit 值傳到 flag 旗標的 carry 並把 plock 的第 0 個 bit 設為 1，其中 $0 是在 AT&T 語法中是指數字，也就是 immediate value。所以，再來只要檢查 carry 的值就可以了。當 carry 的值是 1 時，表示 spinlock 是上鎖狀態的，就跳到 label 2 的地方去執行，在程序碼裡，我們可以看到 jump 指令後面接著 2b，2f 及 1b 這些字眼，這些都是指 1: 或 2: 這些 label，如果某個 label 定在 jump 的前面，則指定label 時，要加上 b（backward），如果在後面，則加上 f（forward）。在 label 2 這段程序碼裡，它不停的做迴圈，執行 nop 指令，每次的迴圈都會去檢查一次 spinlock_t.lock 的值，當 spinlock 不是鎖住的狀態時，就會跳離迴圈，離開 spin_lock() 函式。
看完了 spin_lock()，再來看 spin_unlock() 就會發覺簡單多了。
#define spin_unlock(lock)
__asm__ __volatile__( spin_unlock_string
:"=m" (__dummy_lock(lock)))

其中，spin_unlock_string 一樣是個 macro，展開後變成下面這個樣子:
spin_unlock(plock)
｛
lock; btrl $0, plock;
}

btrl $0, plock 這一行會將 plock 的第 0 個 bit 設為 0，可以很清楚的看出來，spin_unlock() 只是將 plock 的第 0 個 bit 再設回 0 而已。在 spin_lock() 和 spin_unlock() 裡我們都可以看到 lock 這個指令在 btrl 或 btsl 的前頭，這個指令的用途是當 btrl 或 btsl 在修改 plock 的值時，其它別的行程都不能來修改 plock 的值，如果有別的行程企圖修改 plock 的值就會造成 exception 的發生。

看到這裡，各位應該可以瞭解 spinlock 的運作方式及其基本的使用方法了，接下來，我要跟各位介紹 spinlock 的另一種小小的變型，叫 read-write spinlock。

第二種的使用方式

有些資料結構是這樣子的，我們希望有人在修改它的內容時，別人都不能讀取或修改它，但是當沒有人在修改它時，可以同時有很多人去讀取它的內容。我們稱這樣的 spinlock 為 read-write spinlock。 Kernel 為它定義了 rwlock_t，放在 裡。使用方式是這樣子的。

rwlock_t xxx_lock = RW_LOCK_UNLOCKED;

unsigned long flags;

read_lock_irqsave(&xxx_lock， flags);
... critical section that only reads the info ...
read_unlock_irqrestore(&xxx_lock， flags);

write_lock_irqsave(&xxx_lock， flags);
... read and write exclusive access to the info ...
write_unlock_irqrestore(&xxx_lock， flags);

其實我們可以看到，它們的使用方式都是差不多的。在使用之前，先要宣告一個 rwlock_t 的變數，並將初始值設為 RW_LOCK_UNLOCKED， flags 還是一樣是用來存放 CPU flag 的值。如果你要去讀取資料結構的值，可以呼叫 read_lock_irqsave()，用完時則呼叫read_unlock_irqrestore()。至於當你要修改資料結構時，則呼叫 write_lock_irqsave()，修改完呼叫 write_unlock_irqrestore() 即可。

我們來看看read這組函式的原始碼是怎?樣子的：

#define read_lock_irqsave(lock， flags) do { local_irq_save(flags);　
read_lock(lock); } while (0)

#define read_unlock_irqrestore(lock， flags) do { read_unlock(lock);　　
local_irq_restore(flags); } while (0)

這二個函式和 spin_lock_irqsave() 與 read_unlock_irqrestore() 的 差別只在於一個是呼叫 spin_lock() 與 spin_unlock()，另一個則是呼叫 read_lock() 與 read_unlock()。
我們再來看看 read_lock() 與 read_unlock() 這兩個函式，在 UP 環境底下是這個樣子的：


#define read_lock(lock) (void)(lock) /* Not "unused variable". */
#define read_unlock(lock) do { } while(0)

啊哈，跟 UP 底下的 spin_lock() 與 spin_unlock() 完全是一模一樣的，所以，事實上在 UP 的環境下，使用 rwlock 和 spinlock 是沒有差別的。其實，各位可以自己去看 write_lock_irqsave() 與 write_unlock_irqsave() 的程序，擴展開來跟上面兩組函式都是一樣的。原因其實很簡單，在 UP 的環境下，雖然 Linux 號稱多任務的系統，但由於只有一顆 CPU，在同一時間只有一個行程在執行，其它的行程都會被 suspend，唯一會中斷 Kernel 執行的只有 interrupt 了。所以，事實上，要做好 critical section 的保護只要暫時將中斷 disable 掉就行了。 Kernel 之所以要提 供上面這些函式其實是要給 SMP 的系統使用的，除此之外，它另一個用途就是增加 portability。 程序只要用 spinlock 來寫的話，那不管是在 SMP 或 UP 環境下都可以直接 compile 並執行，不用再重新修改程序碼。

至於 SMP 底下 rwlock 的實作方式我就不再贅述，基本上它們的實作方式都是差不多的，只有一點要特別說的是，由於 rwlock 可以容許多個 reader，但卻只能有一個 writer，所以，它不會只用到 rwlock_t.lock 的第 0 個 bit 而已。事實上，rwlock_t.lock 是個 32bit 的 unsigned int 型別的變數，因此，它用第 0 到 30 個 bit 當作 reader 的 counter，而第 31 個 bit 則是用來給 writer 使用的。當第 31 個 bit 為 1 時，表示目前 rwlock 被 writer 鎖住，此時前 30 個 bit 都應該是 0，表示此時沒有任何的 reader。因此，可以推斷 rwlock 同一時間最多可以有 2 的 30 次方個 reader。

第三種使用 spinlock 的方式

我們可以看到以上兩種的使用機制都是以 disable 中斷的方式來做的，雖然 disable 中斷很簡單，只要一個指令就行了，但事實上，這個指令的 cost 對 CPU 來講是蠻大的。所以， Kernel 還提供另一組的函式，它不 disable 中斷，所以，它的執行速度會比上面兩種來得有效率一些。 但是，上帝是公平的，它讓你速度快，相對的它也提供的某些限制。這個限制就是就如果你確定 interrupt handler 不會用到這個受保護的資料結構時，那你就可以考慮用這一組的函式， 以加快程序的執行。其實，這一組函式我們已經在上面見過了。

spin_lock(&lock);
...
spin_unlock(&lock);

就是 spin_lock() 和 spin_unlock() 這兩個函式。在上面我們已經見過這兩個函式展開的情形了， 在 UP 的環境裡，這兩個函式跟空的沒什?兩樣。但為何在UP底下，它們可以做到保護 critical section的作用呢？原因其實也講過了，因為在UP底下只有一個 CPU，所以，在同一時間只有一個行程在執行，除非行程自己放棄執行，不然只有 interrupt 會中斷其執行。剛才我們說過，使用這組函式的前提是在 interrupt handler 中不能使用到放在 critical section 中的資料結構。既然在 interrupt handler 中不會使用到，就算在 critical section 使用這個資料結構使用到一半，中斷突然發生，處理完中斷，CPU 還是會直接回來執行 critical section 的程序碼。所以，不會造成受保護的資料結構的不穩定。我們現在來看看，如果我們使用這組函式， 而且在 interrupt handler 中使用受保護的資料結構時會發生什?事。

spin_lock(&lock);
....
<------ interrupt
spin_lock(&lock);
...
spin_unlock(&lock)


在 UP 的的環境下，由於 spin_lock() 是空的，則當中斷發生時，很有可能行程使用資料結構到一半，中斷跑進來，也在使用它，造成這個資料結構的不穩定。如果是在SMP的環境下，由於 spin_lock() 是真的有在做事，所以當中斷發生時，如果這個中斷是發生在別的 CPU 上， 那就沒事，因為 spin_lock() 只會讓中斷發生的 CPU suspend 住而已。等原先的 CPU 執行完 spin_unlock() 它就可以恢復了，但是如果這時的中斷還是發生在原先的 CPU 上時，那在 interrupt handler 中，CPU 會一直被 suspend 住，直到 lock 被釋放為止。這就造成了一個 dead lock。因為這顆 CPU 現在已經被 lock 住，如何離開 interrupt handler 去呼叫 spin_unlock() 呢。

混合使用
針對 rwlock_t 這組函式除了上面提到的用法外，事實上，還是可以混合 spin_lock() 及 spin_unlock() 來使用的。由於 rwlock_t 可以允許多個 reader，所以如果在 interrupt handler 中只會讀取受保護的資料結構，而不會去修改它的話，那我們可以使用 spin_lock() 這組函式，但是當行程要修改資料結構時，還是得呼叫 write_spin_lock() 及 write_spin_unlock() 這組的函式。這樣既可以增加執行的效率，又可以確保重要資料結構的穩定性了。

結論
雖然在 UP 的環境中，保護重要的資料結構只要呼叫 cli() 和 sti() 就好，但是隨著 SMP 技術的成熟，相信 SMP 系統會逐漸的增加，為了讓自己寫的程序具有可移植性，善用 spinlock 這項機制相信會為未來省下相當修改程序碼的功夫。