Linux核心中的鎖

1. 為什麼要保證原子性

處理器分兩種：cisc（複雜指令集，可以直接在記憶體上進行操作，如x86，一條彙編指令可以原子的完整讀記憶體、計算、寫記憶體）和rics（精簡指令集，所有操作都必須是在CPU内部進行。是以你想給記憶體某個變量做加法，你要先用load指令把記憶體load到CPU的寄存器、再執行add，再執行store把結果放到記憶體中）。

是以a++這句話在rics上并不是原子的，必須翻譯成一個rmw序列（讀、修改、寫）。那麼就有可能在中途被打斷，執行結果就可能不符合預期了。又例如，CPU去修改某個寄存器，也是這樣的rmw過程，是以如果多個線程像修改這個寄存器也會有潛在問題。

是以一些晶片把寄存器分類成了set和clear兩個寄存器。那麼在修改寄存器的時候，想把某個寄存器的某個bit寫1，就去寫它的set寄存器，想把某位清0，就去寫它的clear寄存器，這樣就隻有寫操作。然後硬體會保證修改寄存器内容及其原子性，你就不用做了。例如，你想把寄存器的bit9寫1，則就把1>>9寫到set寄存器就好了，無需知道寄存器原來的值是什麼。

有的晶片使用bitband技術：一個寄存器有32位，就有32個影子寄存器，對應寄存器的每一位。同上，你想改某一位就寫這個bit的影子寄存器，硬體會給把寄存器修改成正确的值。這樣，你寫的代碼就無需考慮原子性，提高了代碼的performance。

硬體上保證原子性的一些手段：

排他性（或獨占性）的load和store，對于ARM，讀的時候調用ldrex，寫的時候調用strex：當兩個線程同時做load或store（使用ex），就會把并行的序列變成串行，隻有第一個store的人會成功，第二個失敗（指令會有傳回值），第二個store的代碼要寫成死循環，判斷傳回值，失敗後就重新從load開始再次執行序列。注意，編譯器無法産生idrex/strex指令，是以要用它們的話必須手寫内嵌彙編。

atomic_add/atomic_sub/atomic_inc/atomic_dec/atomic_set/atomic_read等都是通過上述排他性的wmx序列來完成，是以給一個整數變量加減可以使用這幾個api。并且定義變量要使用atomic_t，雖然隻是int的typeof，但還是寫規範點。

atomic_xxx隻能用來對整型變量保證原子性。對于其他類型或語義通常是通過加鎖或禁用中斷來保證原子性的。

2. Linux核心鎖

臨界區：就是可能存在多個線程同時通路臨界資源的代碼片段，而臨界資源在一個時間點隻能被一個線程通路。這種情況下，我們通過加鎖的方式對臨界區加以保護（在使用者态還可以通過同步信号量或條件變量等方式，但核心中一般隻用鎖）。

拿到一把鎖，要把相關的語義事物全部做完，再解鎖。具體哪些部分是一個語義整體，就得你根據實際場景自己分析了，看哪些語義是互相關聯的，就一起加鎖。另外，要做到語義最小，不能說為了安全，不管三七二十一對整段代碼加鎖。

另外一點要注意的就是，語義關聯的東西必須要共同加鎖。這句話的意思是，加鎖的對象一定要是一個語義，不能是其中的一部分，例如，一個結構體執行個體，裡面有性别和姓名兩個成員，多個線程會修改它，那麼這時的語義就是整個結構體，你就要給整個結構體加鎖。如果你給姓名和性别單獨加鎖的話，就可能出現在某個時刻小明的性别變成了女性。

一般那些某個地方代碼的錯誤導緻了其他代碼的bug都是兩個原因：1.記憶體越界，指針亂踏。2.鎖沒加對，導緻偶然性的bug，可能好幾天才會挂。

2.1 spinlock

自旋鎖是用在多處理器環境中的鎖：如果核心控制路徑發現自旋鎖開着，就擷取鎖并繼續執行，相反，如果核心控制路徑發現鎖由運作在另一個CPU上的核心控制路徑鎖着，就在周圍“旋轉”，直到鎖被釋放。這個“旋轉”就是在忙等，這期間正在等待的核心控制路徑除了浪費時間，無事可做。

spin_lock()的實作邏輯是，他執行的是一個 核内鎖排程，核間自旋 的過程。多核處理器裡面，任何一個核拿到了spinlock，這個核内的排程器就被鎖住了，也就是這個核上的其他線程就不可能被排程執行了，核内是通過直接把排程器鎖住來實作的。而核間才是真正自旋，是以spinlock中的”spin”在多核上才有意義。在單核情況下，spin_lock()就隻是簡單的去鎖住排程器（preempt_disable，即禁掉核心搶占）。

spinlock适合鎖住那些時間特别短且不睡眠的區間。這包括了兩方面：

1. 核1鎖住臨界區，核2上某線程在等待進入臨界區，那麼核2線程可以選擇睡眠讓其他線程運作，等核1線程退出臨界區喚醒自己後再繼續運作，也可以原地自旋忙等。如果一個臨界區的時間很短，核1的線程很快執行完臨界區了，這種情況下，核2線程與其睡眠進行兩次上下文切換，還不如原地死等（while循環去檢查一個變量的值），因為可能前者的開銷更大。
2. spinlock的區間不能睡眠（不能調用可睡眠函數），這個好了解，因為不能排程了，而睡眠會引發排程。

在定義一個spinlock的時候要将鎖初始化為“未鎖住”的狀态，確定第一次可以獲得鎖，定義一個自旋鎖用DEFINE_SPINLOCK(x)宏即可，x是鎖的名字。

雖然spinlock之後這個核不能進行排程了，但這個核上的中斷還可能來，spin_lock擋不住中斷，如果中斷處理程式也要通路臨界資源，則spinlock就起不到作用了。這時要用spinlock的修改版本spin_lock_irqsave，即既拿spinlock，也把這個核上的中斷關掉。并且，這時線程中必須使用spin_lock_irqsave，要不然線程在spin_lock的時候被中斷，中斷進行中又調用spin_lock就死鎖了。

多核的競态有哪些情況呢？一個最嚴重的并發網：CPU0（有t1，t2兩個線程和中斷irq1）和CPU1（有t3，t4兩個線程和中斷irq2），這6個例程互相之間都可能産生競态（通路相同的資源）。

解決競态的簡單做法：線上程裡面統一調用spin_lock_irqsave，在中斷裡面統一調用spinlock。這樣就避免了核内和核間的所有競态，（核間的競态是通過spin解決的，核内通過禁搶占和中斷解決）。如果你知道隻有線程才通路臨界區，那線程裡隻用spinlock即可。

注：Linux 2.6.32以後就不支援中斷嵌套了，是以中斷裡spinlock就好了，而老版核心版本，中斷裡面也要調用spin_lock_irqsave。

中斷的幾個API：

local_irq_save或local_irq_disable，關閉本CPU的中斷。local_irq_save在關中斷的同時會儲存目前開關中斷的狀态，可以在restore的時候恢複。local_irq_disable/save是直接去改cprs寄存器，讓CPU不響應中斷。spin_lock_irqsave，是spinlock加local_irq_save的合體。

irq_disable(iqr_desc)，屏蔽某号中斷，它該的是描述符，讓這個中斷不發給CPU了。

我們說spin_lock核内鎖排程，核間自旋。而local_irq_save是鎖住了本核的中斷，但在核間是沒有任何作用的（Linux沒有任何API能關其他核的中斷或排程器）。由于我們平時寫的驅動都是跨核的，不要假設自己代碼肯定是單核上運作，local_irq_save起不到鎖住多核的作用，如果另一個核要通路你這個核上線程的資源就産生競态了，是以寫代碼的時候不要用local_irq_save，你自己寫的代碼基本不會存在隻需要使用local_irq_save的情況，建議都改用spin_lock_irqsave來鎖中斷。當然local_irq_disable就更不要用了。

是以，spin_lock和spin_lock_irqsave是常用的。

注意kmalloc可能睡眠，如果在spinlock申請記憶體，可以加GFP_ATOMIC的flag，也可以直接用alloc_page系列函數。

還有其他的變種例如local_bh_disable()是鎖下半部（鎖搶占）的，相應的spin_lock_bh()是多核中鎖下半部的。

2.2 mutex和信号量

mutex原理很簡單，一個線程拿到了mutex，另一個線程運作時得不到mutex就睡覺，排程出去。mutex适合時間比較長或需要睡眠的臨界區間。這裡再多說一句，如果你的臨界區裡面需要調用睡眠函數就不要用spin_lock，因為代碼如何運作不可預料，kernel裡面有個選項CONFIG_DEBUG_ATOMIC_SLEEP，打開這個選項，在spinlock裡睡就會有oops。

以前核心裡還有信号量，現在基本被淘汰了，因為太複雜，實作成本太高，已經不建議用了。

加鎖的原則：同一把鎖，語義整體，粒度最小。是以包括三方面：1.鎖一個資源用同一把鎖，2.保證語義完整，3.但語義範圍盡量小，使加鎖粒度最小。

其中1很好了解，一個資源如果用不同的鎖是鎖不住的。2直接影響到功能的正确性了，而3則會影響程式的并行性能。

如果發現一個語義太大，可能是你的設計或資料結構定義有問題，本來沒有互斥的語義給放到一個大的語義裡了，就要嘗試做語義分解。

補充一下同步鎖和互斥鎖：

互斥鎖: 用來保護臨界區，確定兩個線程不能同時通路同一個資源。但是不在乎這兩個線程通路這個資源的先後順序。例如mutex，核心中的spinlock。

同步鎖: 用來保證兩個線程有序地通路某個資源，也有互斥在裡面。例如信号量、使用者态的條件變量。好像直接提及“同步鎖”這個名字的時候不多。

3. 調試Linux死鎖

Linux被hang住通常是由于spinlock和鎖中斷導緻的，因為他倆都把CPU堵住了。一個調試hang死的工具是Linux自帶的lockup detector。

soft lockup: 鎖住排程器。

hard lockup: 鎖住了中斷。

kernel/watchdog.c就是用來實作lockup detector的（開啟核心選項CONFIG_LOCKUP_DETECTOR），它使能了一個高優先級的rt線程，周期性的跑，給某個計數器+1，有個定時器中斷定期檢查這個計數器。如果定時器發現一定時間内都沒+1，則說明排程器鎖死了，定時器中斷處理程式就列印backtrace（中斷服務程式是運作在目前線程的棧，是以列印backtrace就能看到最新被排程的線程的棧）。

hard lockup：需要CPU支援NMI（不可屏蔽中斷，通常是通過CPU裡的PMU單元實作的），如果PMU發現長時間（這個cycle是借助NMI來計算的，因為定時器可能不工作了）一個中斷都不來，就知道發生了hard lockup，這時（觸發NMI中斷，中斷處理函數中）分析棧就知道在哪裡鎖住中斷的。需要把CONFIG_HARDLOCKUP_DETECTOR打開。

由于ARM裡面沒有NMI，是以核心不支援ARM的hard lockup detector。但有一些核心patch可以用，比如用FIQ模拟MNI（如果FIQ用于其他地方了，這裡就用不了了），或者用CPU1去檢測CPU0是否被hard lockup(但CPU1沒辦法獲得線程的棧，隻能知道lockup了)，但這兩個patch都沒在主線上。FIQ在Linux中基本不用的（一般隻做特殊的debugger，正常代碼不用）。

注意别跟drivers/watchdog/弄混了，這是看門狗，不是一回事。