細節是魔鬼——基于計數器的鎖機制的實作準則

有點标題黨了，本意是想把對核心鎖機制的一些實作細節記錄下來，但多少反映了鎖機制實作時的一些準則。本文讨論的鎖機制主要指基于計數器的鎖機制例如 spinlock、mutex，不包括 RCU 這類鎖機制。

parallesim

在讨論各種鎖機制之前，有必要讨論系統的并行度，即有哪些潛在的競争場景

1. 中斷上下文與程序上下文對共享資源的通路，由于中斷是異步進行的，因而中斷與程序是并發執行的，當中斷上下文與程序上下文同時對共享資源進行通路時，就有可能形成競争
2. 在 UP 與 SMP 系統中，當處理器是可搶占的時，由于可搶占的特性，同一個處理器内程序與程序間是并發執行的
3. 在 SMP 系統中，多處理器間的程序是嚴格意義上的并發執行的

parallesim from preemption

在單處理器上，程序之間的搶占是并行度的一大來源，為了排除程序搶占帶來的并行度，在鎖機制的實作過程中必須關閉搶占

parallesim from SMP

在 SMP 系統中，多處理器之間是嚴格并發執行的

目前核心中大部分鎖機制使用 counter based locking 來排除多處理器之間的并行度，其原理是維護一個整型資料類型的 counter 計數器，計數器的值就表示可用資源的份數，在申請占用資源的時候計數器就加 1，在申請釋放資源的時候計數器就減 1

counter based 的鎖機制在實作時都需要考慮 atomic 與 barrier 兩個次元

atomic

首先，counter based 的鎖機制的核心都是整型資料類型的 counter 計數器，需要保證對計數的操作是 atomic 的

現代處理器架構一般都保證對整型資料類型的 load 或 store 操作原生是 atomic 的，但是鎖機制中大量涉及的是 add/sub 即 RMW (Read-Modify-Write) 操作，但是處理器架構一般不能保證 RMW (Read-Modify-Write) 操作原生是 atomic 的

• x86 架構下使用 LOCK 指令來實作 atomic RMW (read-modify-write)
• ARM 架構下提供 LDREX/STREX 指令來實作 atomic RMW (read-modify-write)

acquire/release barrier

隻有 atomic RMW (read-modify-write) 還不夠，因為 memory reordering 可能會将 lock 操作之後的記憶體通路指令重排到 lock 操作之前執行

update counter
---------------------
LOCK
---------------------
critical area           

也有可能将 unlock 操作之前的記憶體通路指令重排到 unlock 操作之後執行

critical area
---------------------
UNLOCK
---------------------
update counter           

因而 counter based 的鎖機制還需要實作 acquire/release 語義，進而確定 lock 操作之後的記憶體通路指令不會重排到 lock 操作之前執行

update counter
---------------------
read acquire (LOCK)
---------------------
critical area stay below the line           

unlock 操作之前的記憶體通路指令不會重排到 unlock 操作之後執行

critical area stay above the line
---------------------
write release (UNLOCK)
---------------------
update counter           

這就需要在 lock 操作的最後調用 acquire barrier，在 unlock 操作的最開始調用 release barrier，進而確定 lock/unlock 之間的記憶體通路指令一定位于 lock/unlock 之間

x86 架構下由于隻存在 StoreLoad reorder，因而天生滿足 acquire/release 語義，因而 x86 架構下以上這兩個 barrier 的定義都為空

aarch64 架構下則使用 dmb 指令實作 acquire/release 語義

parallesim from IRQ

以上 atomic、barrier、preemption 三個次元實作的鎖機制，不是中斷安全的，即并不能排除中斷帶來的并行度

如果鎖機制需要保護的共享資源不會被中斷處理程式通路，即隻是在 process context 之間共享，那麼以上三個次元 atomic、barrier、preemption 實作的鎖機制就完全夠用了

而如果共享資源還會被中斷處理程式通路，也就是共享資源實際上是在 process context 和 interrupt context 之間共享，那麼由 process context 這一方發起的上鎖的過程中，還必須關閉全局中斷，例如 spinlock 就提供了 spin_lock_irq()/spin_unlock_irq() 這類的接口