Linux 自旋鎖Spinlock，教你如何把Ubuntu弄死鎖
背景
由于在多處理器環境中某些資源的有限性，有時需要互斥訪問(mutual exclusion)，這時候就需要引入鎖的概念，只有獲取了鎖的任務才能夠對資源進行訪問，由于多線程的核心是CPU的時間分片，所以同一時刻只能有一個任務獲取到鎖。
內核當發生訪問資源沖突的時候，通常有兩種處理方式：
- 一個是原地等待
- 一個是掛起當前進程，調度其他進程執行(睡眠)
自旋鎖
Spinlock 是內核中提供的一種比較常見的鎖機制，自旋鎖是“原地等待”的方式解決資源沖突的。即，一個線程獲取了一個自旋鎖后，另外一個線程期望獲取該自旋鎖，獲取不到，只能夠原地“打轉”(忙等待)。
由于自旋鎖的這個忙等待的特性，注定了它使用場景上的限制 —— 自旋鎖不應該被長時間的持有(消耗 CPU 資源)。
自旋鎖的優點
自旋鎖不會使線程狀態發生切換，一直處于用戶態，即線程一直都是active的;不會使線程進入阻塞狀態，減少了不必要的上下文切換，執行速度快。
非自旋鎖在獲取不到鎖的時候會進入阻塞狀態，從而進入內核態，當獲取到鎖的時候需要從內核態恢復，需要線程上下文切換。(線程被阻塞后便進入內核(Linux)調度狀態，這個會導致系統在用戶態與內核態之間來回切換，嚴重影響鎖的性能)。
自旋鎖的使用
在linux kernel的實現中，經常會遇到這樣的場景：共享數據被中斷上下文和進程上下文訪問，該如何保護呢?
如果只有進程上下文的訪問，那么可以考慮使用semaphore或者mutex的鎖機制，但是現在中斷上下文也摻和進來，那些可以導致睡眠的lock就不能使用了，這時候，可以考慮使用spin lock。
在中斷上下文，是不允許睡眠的，所以，這里需要的是一個不會導致睡眠的鎖——spinlock。
換言之，中斷上下文要用鎖，首選 spinlock。
使用自旋鎖，有兩種方式定義一個鎖：
動態的：
- spinlock_t lock;
- spin_lock_init (&lock);
靜態的：
- DEFINE_SPINLOCK(lock);
使用步驟
spinlock的使用很簡單:
- 我們要訪問臨界資源需要首先申請自旋鎖;
- 獲取不到鎖就自旋，如果能獲得鎖就進入臨界區;
- 當自旋鎖釋放后，自旋在這個鎖的任務即可獲得鎖并進入臨界區，退出臨界區的任務必須釋放自旋鎖。
使用實例
- static spinlock_t lock;
- static int flage = 1;
- spin_lock_init(&lock);
- static int hello_open (struct inode *inode, struct file *filep)
- {
- spin_lock(&lock);
- if(flage !=1)
- {
- spin_unlock(&lock);
- return -EBUSY;
- }
- flage =0;
- spin_unlock(&lock);
- return 0;
- }
- static int hello_release (struct inode *inode, struct file *filep)
- {
- flage = 1;
- return 0;
- }
補充
中斷上下文不能睡眠的原因是：
1.中斷處理的時候,不應該發生進程切換，因為在中斷context中，唯一能打斷當前中斷handler的只有更高優先級的中斷，它不會被進程打斷，如果在 中斷context中休眠，則沒有辦法喚醒它，因為所有的wake_up_xxx都是針對某個進程而言的，而在中斷context中，沒有進程的概念，沒 有一個task_struct(這點對于softirq和tasklet一樣)，因此真的休眠了，比如調用了會導致block的例程，內核幾乎肯定會死。
2.schedule()在切換進程時，保存當前的進程上下文(CPU寄存器的值、進程的狀態以及堆棧中的內容)，以便以后恢復此進程運行。中斷發生后，內核會先保存當前被中斷的進程上下文(在調用中斷處理程序后恢復);
但在中斷處理程序里，CPU寄存器的值肯定已經變化了吧(最重要的程序計數器PC、堆棧SP等)，如果此時因為睡眠或阻塞操作調用了schedule()，則保存的進程上下文就不是當前的進程context了.所以不可以在中斷處理程序中調用schedule()。
3.內核中schedule()函數本身在進來的時候判斷是否處于中斷上下文:
- if(unlikely(in_interrupt()))
- BUG();
因此，強行調用schedule()的結果就是內核BUG。
4.中斷handler會使用被中斷的進程內核堆棧，但不會對它有任何影響，因為handler使用完后會完全清除它使用的那部分堆棧，恢復被中斷前的原貌。
5.處于中斷context時候，內核是不可搶占的。因此，如果休眠，則內核一定掛起。
自旋鎖的死鎖
自旋鎖不可遞歸，自己等待自己已經獲取的鎖，會導致死鎖。
自旋鎖可以在中斷上下文中使用，但是試想一個場景：一個線程獲取了一個鎖，但是被中斷處理程序打斷，中斷處理程序也獲取了這個鎖(但是之前已經被鎖住了，無法獲取到，只能自旋)，中斷無法退出，導致線程中后面釋放鎖的代碼無法被執行，導致死鎖。(如果確認中斷中不會訪問和線程中同一個鎖，其實無所謂)。
一、考慮下面的場景(內核搶占場景)：
(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狀態。
二、再考慮下面的場景(中斷上下文場景)：
運行在CPU0上的進程A在某個系統調用過程中訪問了共享資源 R
運行在CPU1上的進程B在某個系統調用過程中也訪問了共享資源 R
外設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就可以了。
四、中斷上下文之間的競爭
同一種中斷handler之間在uni core和multi core上都不會并行執行，這是linux kernel的特性。如果不同中斷handler需要使用spin lock保護共享資源，對于新的內核(不區分fast handler和slow handler)，所有handler都是關閉中斷的，因此使用spin lock不需要關閉中斷的配合。bottom half又分成softirq和tasklet，同一種softirq會在不同的CPU上并發執行，因此如果某個驅動中的softirq的handler中會訪問某個全局變量，對該全局變量是需要使用spin lock保護的，不用配合disable CPU中斷或者bottom half。tasklet更簡單，因為同一種tasklet不會多個CPU上并發。
自旋鎖的實現原理
數據結構
首先定義一個 spinlock_t 的數據類型，其本質上是一個整數值(對該數值的操作需要保證原子性)，該數值表示spin lock是否可用。初始化的時候被設定為1。當thread想要持有鎖的時候調用spin_lock函數，該函數將spin lock那個整數值減去1，然后進行判斷，如果等于0，表示可以獲取spin lock，如果是負數，則說明其他thread的持有該鎖，本thread需要spin。
內核中的spinlock_t的數據類型定義如下：
- typedef struct spinlock {
- struct raw_spinlock rlock;
- } spinlock_t;
- typedef struct raw_spinlock {
- arch_spinlock_t raw_lock;
- } raw_spinlock_t;
通用(適用于各種arch)的spin lock使用spinlock_t這樣的type name，各種arch定義自己的struct raw_spinlock。聽起來不錯的主意和命名方式，直到linux realtime tree(PREEMPT_RT)提出對spinlock的挑戰。
spin lock的命名規范定義如下：
- spinlock，在rt linux(配置了PREEMPT_RT)的時候可能會被搶占(實際底層可能是使用支持PI(優先級翻轉)的mutext)。
- raw_spinlock，即便是配置了PREEMPT_RT也要頑強的spin
- arch_spinlock，spin lock是和architecture相關的，
ARM 結構體系 arch_spin_lock 接口實現
加鎖
同樣的，這里也只是選擇一個典型的API來分析，其他的大家可以自行學習。我們選擇的是 arch_spin_lock，其ARM32的代碼如下：
- static inline void arch_spin_lock(arch_spinlock_t *lock)
- {
- unsigned long tmp;
- u32 newval;
- arch_spinlock_t lockval;
- prefetchw(&lock->slock);－－－－－－－－－（0）
- __asm__ __volatile__(
- "1: ldrex %0, [%3]\n"－－－－－－－－－（1）
- " add %1, %0, %4\n" －－－－－－－－－－（2）
- " 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）
- }
- （0）和preloading cache相關的操作，主要是為了性能考慮
- （1）lockval = lock->slock (如果lock->slock沒有被其他處理器獨占，則標記當前執行處理器對lock->slock地址的獨占訪問；否則不影響)
- （2）newval = lockval + (1 << TICKET_SHIFT)
- （3）strex tmp, newval, [&lock->slock] (如果當前執行處理器沒有獨占lock->slock地址的訪問，不進行存儲，返回1給temp；如果當前處理器已經獨占lock->slock內存訪問，則對內存進行寫，返回0給temp，清除獨占標記) lock->tickets.next = lock->tickets.next + 1
- （4）檢查是否寫入成功 lockval.tickets.next
- （5）初始化時lock->tickets.owner、lock->tickets.next都為0，假設第一次執行arch_spin_lock，lockval = *lock，lock->tickets.next++，lockval.tickets.next 等于 lockval.tickets.owner，獲取到自旋鎖；自旋鎖未釋放，第二次執行的時候，lock->tickets.owner = 0, lock->tickets.next = 1，拷貝到lockval后，lockval.tickets.next != lockval.tickets.owner，會執行wfe等待被自旋鎖釋放被喚醒，自旋鎖釋放時會執行 lock->tickets.owner++，lockval.tickets.owner重新賦值
- （6）暫時中斷掛起執行。如果當前spin lock的狀態是locked，那么調用wfe進入等待狀態。更具體的細節請參考ARM WFI和WFE指令中的描述。
- （7）其他的CPU喚醒了本cpu的執行，說明owner發生了變化，該新的own賦給lockval，然后繼續判斷spin lock的狀態，也就是回到step 5。
- （8）memory barrier的操作，具體可以參考memory barrier中的描述。
釋放鎖
- static inline void arch_spin_unlock(arch_spinlock_t *lock)
- {
- smp_mb();
- lock->tickets.owner++; ---------------------- (0)
- dsb_sev(); ---------------------------------- (1)
- }
(0)lock->tickets.owner增加1，下一個被喚醒的處理器會檢查該值是否與自己的lockval.tickets.next相等，lock->tickets.owner代表可以獲取的自旋鎖的處理器，lock->tickets.next你一個可以獲取的自旋鎖的owner;處理器獲取自旋鎖時，會先讀取lock->tickets.next用于與lock->tickets.owner比較并且對lock->tickets.next加1，下一個處理器獲取到的lock->tickets.next就與當前處理器不一致了，兩個處理器都與lock->tickets.owner比較，肯定只有一個處理器會相等，自旋鎖釋放時時對lock->tickets.owner加1計算，因此，先申請自旋鎖多處理器lock->tickets.next值更新，自然先獲取到自旋鎖
(1)執行sev指令，喚醒wfe等待的處理器
自旋鎖導致死鎖實例
死鎖的2種情況
1)擁有自旋鎖的進程A在內核態阻塞了，內核調度B進程，碰巧B進程也要獲得自旋鎖，此時B只能自旋轉。而此時搶占已經關閉，不會調度A進程了，B永遠自旋，產生死鎖。
2)進程A擁有自旋鎖，中斷到來，CPU執行中斷函數，中斷處理函數，中斷處理函數需要獲得自旋鎖，訪問共享資源，此時無法獲得鎖，只能自旋，產生死鎖。
如何避免死鎖
- 如果中斷處理函數中也要獲得自旋鎖，那么驅動程序需要在擁有自旋鎖時禁止中斷;
- 自旋鎖必須在可能的最短時間內擁有;
- 避免某個獲得鎖的函數調用其他同樣試圖獲取這個鎖的函數，否則代碼就會死鎖;不論是信號量還是自旋鎖，都不允許鎖擁有者第二次獲得這個鎖，如果試圖這么做，系統將掛起;
- 鎖的順序規則 按同樣的順序獲得鎖; 如果必須獲得一個局部鎖和一個屬于內核更中心位置的鎖，則應該首先獲取自己的局部鎖 ; 如果我們擁有信號量和自旋鎖的組合，則必須首先獲得信號量;在擁有自旋鎖時調用down(可導致休眠)是個嚴重的錯誤的。
死鎖舉例
因為自旋鎖持有時間非常短，沒有直觀的現象，下面舉一個會導致死鎖的實例。
運行條件
- 虛擬機：vmware
- OS ：Ubuntu 14
- 配置 ：將虛擬機的處理個數設置為1，否則不會死鎖
原理
針對單CPU，擁有自旋鎖的任務不應該調度會引起休眠的函數，否則會導致死鎖。
步驟：
- 進程A在open()字符設備后，對應的內核函數會申請自旋鎖，此時自旋鎖空閑，申請到自旋鎖，進程A隨即進入執行sleep()函數進入休眠;
- 在進程A 處于sleep期間，自旋鎖一直屬于進程A所有;
- 運行進程B，進程B執行open函數，對應的內核函數也會申請自旋鎖，此時自旋鎖歸進程A所有，所以進程B進入自旋狀態;
- 因為此時搶占已經關閉，系統死鎖。
驅動代碼如下：
- #include <linux/init.h>
- #include <linux/module.h>
- #include <linux/kdev_t.h>
- #include <linux/fs.h>
- #include <linux/cdev.h>
- #include <linux/device.h>
- #include <linux/spinlock.h>
- static int major = 250;
- static int minor = 0;
- static dev_t devno;
- static struct cdev cdev;
- static struct class *cls;
- static struct device *test_device;
- static spinlock_t lock;
- static int flage = 1;
- #define DEAD 1
- static int hello_open (struct inode *inode, struct file *filep)
- {
- spin_lock(&lock);
- if(flage !=1)
- {
- spin_unlock(&lock);
- return -EBUSY;
- }
- flage =0;
- #if DEAD
- #elif
- spin_unlock(&lock);
- #endif
- return 0;
- }
- static int hello_release (struct inode *inode, struct file *filep)
- {
- flage = 1;
- #if DEAD
- spin_unlock(&lock);
- #endif
- return 0;
- }
- static struct file_operations hello_ops =
- {
- .open = hello_open,
- .release = hello_release,
- };
- static int hello_init(void)
- {
- int result;
- int error;
- printk("hello_init \n");
- result = register_chrdev( major, "hello", &hello_ops);
- if(result < 0)
- {
- printk("register_chrdev fail \n");
- return result;
- }
- devno = MKDEV(major,minor);
- cls = class_create(THIS_MODULE,"helloclass");
- if(IS_ERR(cls))
- {
- unregister_chrdev(major,"hello");
- return result;
- }
- test_device = device_create(cls,NULL,devno,NULL,"test");
- if(IS_ERR(test_device ))
- {
- class_destroy(cls);
- unregister_chrdev(major,"hello");
- return result;
- }
- spin_lock_init(&lock);
- return 0;
- }
- static void hello_exit(void)
- {
- printk("hello_exit \n");
- device_destroy(cls,devno);
- class_destroy(cls);
- unregister_chrdev(major,"hello");
- return;
- }
- module_init(hello_init);
- module_exit(hello_exit);
- MODULE_LICENSE("GPL");
測試程序如下：
- #include <stdio.h>
- #include <sys/types.h>
- #include <sys/stat.h>
- #include <fcntl.h>
- main()
- {
- int fd;
- fd = open("/dev/test",O_RDWR);
- if(fd<0)
- {
- perror("open fail \n");
- return;
- }
- sleep(20);
- close(fd);
- printf("open ok \n ");
- }
測試步驟：
編譯加載內核
- make
- insmod hello.ko
運行進程A
- gcc test.c -o a
- ./a
打開一個新的終端，運行進程B
- gcc test.c -o b
- ./b
注意，一定要在進程A沒有退出的時候運行進程B。
本文轉載自微信公眾號「一口Linux」，可以通過以下二維碼關注。轉載本文請聯系一口Linux公眾號。
