前言
在 Linux Kernel 里有著許多重要的資料結(jié)構(gòu)，這些資料在操作系統(tǒng)的運作中扮演著舉足輕重的角色。然而，Linux 是個多工的操作系統(tǒng)，也就是在同一時間里可以同時有許多的行程在執(zhí)行，所以，很有可能某個行程在依序讀取 inode list，同時卻又有另一個在 inode list 里加入新的 inode，這會造成什么情形呢？這會造成 inode list 的不穩(wěn)定。所以，在 Kernel 里，我們需要一個機(jī)制，可以使得當(dāng)我們在修改某個重要的資料結(jié)構(gòu)時，不能被中斷，即使被中斷了，這個資料結(jié)構(gòu)由于還沒修改完，別的行程也都不能去讀取和修改它。Linux Kernel提供了 spinlock 這個機(jī)制可以使我們做到這樣的功能。
有的人會想到當(dāng)我們在修改某個重要的資料結(jié)構(gòu)時，將中斷都 disable 掉就好了，等修改完了再將中斷 enable 不就得了，何必還要再提供一個 spinlock 來做同樣的事。在 uni-processor 的環(huán)境底下，的確是如此。所謂 uni-processor 就是指只有一個 CPU 的電腦，但是在SMP的環(huán)境下就不是這么一回事了。
我們知道現(xiàn)在 Linux 已經(jīng)有支援 SMP，也就是可以使用多顆 CPU 來加快系統(tǒng)的速度，如果當(dāng)我們在修改重要的資料結(jié)構(gòu)時，將執(zhí)行修改工作的 CPU 中斷 disable 掉的話，只有目前的這個 CPU 的執(zhí)行不會被中斷，在 SMP 環(huán)境下，還有別的 CPU 正同時運作，如果別的 CPU 也去修改這個資料結(jié)構(gòu)的話，就會造成同時有兩個 CPU 在修改它，不穩(wěn)定性就會產(chǎn)生。解決方法是將全部的 CPU 中斷都 disable 掉，等修改完之后，再全部都 enable 起來。但是這樣的做法其 cost 會很大，整個系統(tǒng)的效能會 down 下來。因此，Linux Kernel 才會提供 spinlock 這樣的機(jī)制，它不會將全部 CPU 的中斷 disable 掉，所以效率比上述的方法好，但同時卻又能確保資料的穩(wěn)定性，不會有某個行程在修改它，另外又有一個行程在讀取或修改它的情形發(fā)生。
在這篇文章中，我將會介紹 Kernel 提供用來使用 spinlock 的 function。除此之外，我還會告訴各位，為何在 SMP 的環(huán)境里，使用 spinlock 會比將所有 CPU 的中斷 disable 這個方法來的有效率，我也會告訴各位如何針對不同的使用需求，使 spinlock 的 cost 再降低，進(jìn)而使系統(tǒng)的效能更好。
spinlock的資料結(jié)構(gòu)
spinlock 的資料結(jié)構(gòu)在 Linux底下是以 spinlock_t 來表示的，在 SMP 和 UP 環(huán)境底下兩者的欄位有一些差異，其實在 UP 底下 spinlock_t 可以說是一個空的結(jié)構(gòu)，空就是空的，為何要說“可以說是空的”呢？這是因為 gcc 版本的問題，gcc 在 2.8 版以前結(jié)構(gòu)的內(nèi)容必須不能是空的，而在 2.8 版之后就可以，所以在 UP 環(huán)境底下，會根據(jù) gcc 的版本而設(shè)定不同的 spinlock_t 結(jié)構(gòu)欄位，但基本上，在 UP 環(huán)境底下，是根本不會用到 spinlock_t 結(jié)構(gòu)里的欄位的，詳情請見以下諸節(jié)即可了解。
由于 spinlock 主要是用在SMP的環(huán)境底下，所以，以下我們就只針對在SMP環(huán)境底下的 spinlock_t 結(jié)構(gòu)來討論，它的結(jié)構(gòu)內(nèi)容是這樣子的：
typedef struct {
volatile unsigned int lock;
} spinlock t;
說穿了，不過就是一個 unsigned int 型別的變數(shù)而已，但可不要小看這小小的變數(shù)，螺絲釘雖小，功能卻是不可忽視的。
使用 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 型別的變數(shù)，并把初始值設(shè)為 SPIN_LOCK_UNLOCKED。除此之外，還必須有一個unsigned long型別的變數(shù)，這個變數(shù)是用來將 CPU 的 flag（旗標(biāo)）儲存起來的，等 critical section 執(zhí)行完了，再把 flag 的值設(shè)回到系統(tǒng)里。使用上是很簡單明白的。這兩個 function 除了可以在 SMP 的環(huán)境下使用外，在UP的環(huán)境里也是同樣可行的，接下來，我們來看看它們程序碼是怎么寫的。
在 這個檔案里定義了 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 變數(shù)里，然后將 CPU 的中斷 diable 掉。這里將 CPU 的中斷 disable 是指將執(zhí)行這段 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 里的值再設(shè)回 CPU 的 flag 里而已。至于 spin_lock(lock) 和 spin_unlock(lock) 這兩個函式，在 SMP 和在 UP 的環(huán)境底下則會擴(kuò)展成不同的樣子。首先先看到這個檔案的下半部。
#ifdef __SMP__
#include
#else /* !SMP */
.......
#endif
在 SMP 的環(huán)境底下，SMP 這個constant被會 set。而在 UP 底下則不會，所以，如果要看 UP 底下 spin_lock(lock) 會變成怎么樣子，就必須來看看 #else /* !SMP */ 和 #endif 之間的程序碼。
UP 環(huán)境下的 Implementation
我們先來看看在 UP 的環(huán)境下， spin_lock(lock) 會變成什么樣子。
#define spin_lock(x) (void)lock
#define spin_unlock(x) do {} while(0)
簡單吧，根本什么事都沒有做，所以，在 UP 的環(huán)境底下，我們?nèi)绻麑⑸厦婺嵌?spinlock 的使用擴(kuò)展開來的話，會變成下面這個樣子。
spinlock_t xxx_lock = SPIN_LOCK_UNLOCKED;
unsigned long flags;
local_save_flags(flags); cli();
... critical section ...
local_restore_flags(flags);
而這也正是在 UP 環(huán)境下，用來保護(hù)重要資料結(jié)構(gòu)的寫法。這也就是為什么在介紹spinlock_t 的結(jié)構(gòu)內(nèi)容時，我們說在UP環(huán)境底下這個結(jié)構(gòu)就算是空的也不會影響到 spinlock 的功效，因為根本沒用到里面的欄位，但是在 SMP 底下，這就很重要了。
SMP 環(huán)境下的 Implementation
在 SMP 的環(huán)境底下， spin_lock() 和 spin_unlock() 這兩個函式的源代碼是放在 中。
extern inline void spin_lock(spinlock_t *plock)
{
__asm__ __volatile__(
spin_lock_string
:\"=m\" (__dummy_lock(plock)));
}
其實，這段程序碼是經(jīng)過我削減后的，至于削減掉的程序碼是用來做 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 有兩種狀態(tài)，第一種被鎖住的狀態(tài)（lock），第二種則是沒被鎖住的狀態(tài)（unlock）；當(dāng) spinlock 被鎖住時，spinlock_t.lock 會被設(shè)為 1，當(dāng)沒被鎖時，則會設(shè)回 0，各位可以去看我們之前所列出來的使用方法，它會將 spinlock_t 結(jié)構(gòu)的初始值設(shè)為 SPIN_LOCK_UNLOCK，現(xiàn)在再來看看這個 constant 的值，可以發(fā)現(xiàn)它其實就是將 spinlock_t.lock 設(shè)為 0 而已。
#define SPIN_LOCK_UNLOCKED (spinlock_t) { 0 }
所以，檢查其狀態(tài)就變成了 spin_lock() 的首要工作，如果已被鎖住，則 CPU 就不能去使用它所保護(hù)的資料結(jié)構(gòu)，而如果沒上鎖，則可以從 spin_lock() 傳回，接下去使用它所保護(hù)的資料。所以，檢查其狀態(tài)我們可以檢查 spinlock_t.lock 的第 0 個 bit。btsl $0, plock 會將 plock 的第 0 個 bit 值傳到 flag 旗標(biāo)的 carry 并把 plock 的第 0 個 bit 設(shè)為 1，其中 $0 是在 AT&T 語法中是指數(shù)字，也就是 immediate value。所以，再來只要檢查 carry 的值就可以了。當(dāng) carry 的值是 1 時，表示 spinlock 是上鎖狀態(tài)的，就跳到 label 2 的地方去執(zhí)行，在程序碼里，我們可以看到 jump 指令后面接著 2b，2f 及 1b 這些字眼，這些都是指 1: 或 2: 這些 label，如果某個 label 定在 jump 的前面，則指定label 時，要加上 b（backward），如果在后面，則加上 f（forward）。在 label 2 這段程序碼里，它不停的做回圈，執(zhí)行 nop 指令，每次的回圈都會去檢查一次 spinlock_t.lock 的值，當(dāng) spinlock 不是鎖住的狀態(tài)時，就會跳離回圈，離開 spin_lock() 函式。
看完了 spin_lock()，再來看 spin_unlock() 就會發(fā)覺簡單多了。
#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 設(shè)為 0，可以很清楚的看出來，spin_unlock() 只是將 plock 的第 0 個 bit 再設(shè)回 0 而已。在 spin_lock() 和 spin_unlock() 里我們都可以看到 lock 這個指令在 btrl 或 btsl 的前頭，這個指令的用途是當(dāng) btrl 或 btsl 在修改 plock 的值時，其它別的行程都不能來修改 plock 的值，如果有別的行程企圖修改 plock 的值就會造成 exception 的發(fā)生。
看到這里，各位應(yīng)該可以了解 spinlock 的運作方式及其基本的使用方法了，接下來，我要跟各位介紹 spinlock 的另一種小小的變型，叫 read-write spinlock。
第二種的使用方式
有些資料結(jié)構(gòu)是這樣子的，我們希望有人在修改它的內(nèi)容時，別人都不能讀取或修改它，但是當(dāng)沒有人在修改它時，可以同時有很多人去讀取它的內(nèi)容。我們稱這樣的 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 的變數(shù)，并將初始值設(shè)為 RW_LOCK_UNLOCKED， flags 還是一樣是用來存放 CPU flag 的值。如果你要去讀取資料結(jié)構(gòu)的值，可以呼叫 read_lock_irqsave()，用完時則呼叫read_unlock_irqrestore()。至于當(dāng)你要修改資料結(jié)構(gòu)時，則呼叫 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 環(huán)境底下是這個樣子的：
#define read_lock(lock) (void)(lock) /* Not \"unused variable\". */
#define read_unlock(lock) do { } while(0)
啊哈，跟 UP 底下的 spin_lock() 與 spin_unlock() 完全是一模一樣的，所以，事實上在 UP 的環(huán)境下，使用 rwlock 和 spinlock 是沒有差別的。其實，各位可以自己去看 write_lock_irqsave() 與 write_unlock_irqsave() 的程序，擴(kuò)展開來跟上面兩組函式都是一樣的。原因其實很簡單，在 UP 的環(huán)境下，雖然 Linux 號稱多工的系統(tǒng)，但由于只有一顆 CPU，在同一時間只有一個行程在執(zhí)行，其它的行程都會被 suspend，唯一會中斷 Kernel 執(zhí)行的只有 interrupt 了。所以，事實上，要做好 critical section 的保護(hù)只要暫時將中斷 disable 掉就行了。 Kernel 之所以要提 供上面這些函式其實是要給 SMP 的系統(tǒng)使用的，除此之外，它另一個用途就是增加 portability。 程序只要用 spinlock 來寫的話，那不管是在 SMP 或 UP 環(huán)境下都可以直接 compile 并執(zhí)行，不用再重新修改程序碼。
至于 SMP 底下 rwlock 的實作方式我就不再贅述，基本上它們的實作方式都是差不多的，只有一點要特別說的是，由于 rwlock 可以容許多個 reader，但卻只能有一個 writer，所以，它不會只用到 rwlock_t.lock 的第 0 個 bit 而已。事實上，rwlock_t.lock 是個 32bit 的 unsigned int 型別的變數(shù)，因此，它用第 0 到 30 個 bit 當(dāng)作 reader 的 counter，而第 31 個 bit 則是用來給 writer 使用的。當(dāng)?shù)?31 個 bit 為 1 時，表示目前 rwlock 被 writer 鎖住，此時前 30 個 bit 都應(yīng)該是 0，表示此時沒有任何的 reader。因此，可以推斷 rwlock 同一時間最多可以有 2 的 30 次方個 reader。
第三種使用 spinlock 的方式
我們可以看到以上兩種的使用機(jī)制都是以 disable 中斷的方式來做的，雖然 disable 中斷很簡單，只要一個指令就行了，但事實上，這個指令的 cost 對 CPU 來講是蠻大的。所以， Kernel 還提供另一組的函式，它不 disable 中斷，所以，它的執(zhí)行速度會比上面兩種來得有效率一些。 但是，上帝是公平的，它讓你速度快，相對的它也提供的某些限制。這個限制就是就如果你確定 interrupt handler 不會用到這個受保護(hù)的資料結(jié)構(gòu)時，那你就可以考慮用這一組的函式， 以加快程序的執(zhí)行。其實，這一組函式我們已經(jīng)在上面見過了。
spin_lock(&lock);
...
spin_unlock(&lock);
就是 spin_lock() 和 spin_unlock() 這兩個函式。在上面我們已經(jīng)見過這兩個函式展開的情形了， 在 UP 的環(huán)境里，這兩個函式跟空的沒什么兩樣。但為何在UP底下，它們可以做到保護(hù) critical section的作用呢？原因其實也講過了，因為在UP底下只有一個 CPU，所以，在同一時間只有一個行程在執(zhí)行，除非行程自己放棄執(zhí)行，不然只有 interrupt 會中斷其執(zhí)行。剛才我們說過，使用這組函式的前提是在 interrupt handler 中不能使用到放在 critical section 中的資料結(jié)構(gòu)。既然在 interrupt handler 中不會使用到，就算在 critical section 使用這個資料結(jié)構(gòu)使用到一半，中斷突然發(fā)生，處理完中斷，CPU 還是會直接回來執(zhí)行 critical section 的程序碼。所以，不會造成受保護(hù)的資料結(jié)構(gòu)的不穩(wěn)定。我們現(xiàn)在來看看，如果我們使用這組函式， 而且在 interrupt handler 中使用受保護(hù)的資料結(jié)構(gòu)時會發(fā)生什么事。
spin_lock(&lock);
....
<------ interrupt
spin_lock(&lock);
...
spin_unlock(&lock)
在 UP 的的環(huán)境下，由于 spin_lock() 是空的，則當(dāng)中斷發(fā)生時，很有可能行程使用資料結(jié)構(gòu)到一半，中斷跑進(jìn)來，也在使用它，造成這個資料結(jié)構(gòu)的不穩(wěn)定。如果是在SMP的環(huán)境下，由于 spin_lock() 是真的有在做事，所以當(dāng)中斷發(fā)生時，如果這個中斷是發(fā)生在別的 CPU 上， 那就沒事，因為 spin_lock() 只會讓中斷發(fā)生的 CPU suspend 住而已。等原先的 CPU 執(zhí)行完 spin_unlock() 它就可以恢復(fù)了，但是如果這時的中斷還是發(fā)生在原先的 CPU 上時，那在 interrupt handler 中，CPU 會一直被 suspend 住，直到 lock 被釋放為止。這就造成了一個 dead lock。因為這顆 CPU 現(xiàn)在已經(jīng)被 lock 住，如何離開 interrupt handler 去呼叫 spin_unlock() 呢。
混合使用
針對 rwlock_t 這組函式除了上面提到的用法外，事實上，還是可以混合 spin_lock() 及 spin_unlock() 來使用的。由于 rwlock_t 可以允許多個 reader，所以如果在 interrupt handler 中只會讀取受保護(hù)的資料結(jié)構(gòu)，而不會去修改它的話，那我們可以使用 spin_lock() 這組函式，但是當(dāng)行程要修改資料結(jié)構(gòu)時，還是得呼叫 write_spin_lock() 及 write_spin_unlock() 這組的函式。這樣既可以增加執(zhí)行的效率，又可以確保重要資料結(jié)構(gòu)的穩(wěn)定性了。
結(jié)論
雖然在 UP 的環(huán)境中，保護(hù)重要的資料結(jié)構(gòu)只要呼叫 cli() 和 sti() 就好，但是隨著 SMP 技術(shù)的成熟，相信 SMP 系統(tǒng)?%B