Linux內核同步機制之（五）：Read Write spin lock【轉】

一、為何會有rw spin lock？

在有了強大的spin lock之後，為何還會有rw spin lock呢？無他，僅僅是為了增加內核的併發，從而增加性能而已。spin lock嚴格的限制只有一個thread可以進入臨界區，但是實際中，有些對共用資源的訪問可以嚴格區分讀和寫的，這時候，其實多個讀的thread進入臨界區是OK的，使用spin lock則限制一個讀thread進入，從而導致性能的下降。

本文主要描述RW spin lock的工作原理及其實現。需要說明的是Linux內核同步機制之（四）：spin lock是本文的基礎，請先閱讀該文檔以便保證閱讀的暢順。

二、工作原理

1、應用舉例

我們來看一個rw spinlock在文件系統中的例子：

static struct file_system_type *file_systems; 
static DEFINE_RWLOCK(file_systems_lock);

linux內核支持多種文件系統類型，例如EXT4，YAFFS2等，每種文件系統都用struct file_system_type來表示。內核中所有支持的文件系統用一個鏈表來管理，file_systems指向這個鏈表的第一個node。訪問這個鏈表的時候，需要用file_systems_lock來保護，場景包括：

（1）register_filesystem和unregister_filesystem分別用來向系統註冊和註銷一個文件系統。

（2）fs_index或者fs_name等函數會遍歷該鏈表，找到對應的struct file_system_type的名字或者index。

2、基本的策略

使用普通的spin lock可以完成上一節中描述的臨界區的保護，但是，由於spin lock的特定就是只允許一個thread進入，因此這時候就禁止了多個讀thread進入臨界區，而實際上多個read thread可以同時進入的，但現在也只能是不停的spin，cpu強大的運算能力無法發揮出來，如果使用不斷retry檢查spin lock的狀態的話（而不是使用類似ARM上的WFE這樣的指令），對系統的功耗也是影響很大的。因此，必須有新的策略來應對：

我們首先看看加鎖的邏輯：

（1）假設臨界區內沒有任何的thread，這時候任何read thread或者write thread可以進入，但是只能是其一。

（2）假設臨界區內有一個read thread，這時候新來的read thread可以任意進入，但是write thread不可以進入

（3）假設臨界區內有一個write thread，這時候任何的read thread或者write thread都不可以進入

（4）假設臨界區內有一個或者多個read thread，write thread當然不可以進入臨界區，但是該write thread也無法阻止後續read thread的進入，他要一直等到臨界區一個read thread也沒有的時候，才可以進入，多麼可憐的write thread。

unlock的邏輯如下：

（1）在write thread離開臨界區的時候，由於write thread是排他的，因此臨界區有且只有一個write thread，這時候，如果write thread執行unlock操作，釋放掉鎖，那些處於spin的各個thread（read或者write）可以競爭上崗。

（2）在read thread離開臨界區的時候，需要根據情況來決定是否讓其他處於spin的write thread們參與競爭。如果臨界區仍然有read thread，那麼write thread還是需要spin（註意：這時候read thread可以進入臨界區，聽起來也是不公平的）直到所有的read thread釋放鎖（離開臨界區），這時候write thread們可以參與到臨界區的競爭中，如果獲取到鎖，那麼該write thread可以進入。

三、實現

1、通用代碼文件的整理

rw spin lock的頭文件的結構和spin lock是一樣的。include/linux/rwlock_types.h文件中定義了通用rw spin lock的基本的數據結構（例如rwlock_t）和如何初始化的介面（DEFINE_RWLOCK）。include/linux/rwlock.h。這個頭文件定義了通用rw spin lock的介面函數聲明，例如read_lock、write_lock、read_unlock、write_unlock等。include/linux/rwlock_api_smp.h文件定義了SMP上的rw spin lock模塊的介面聲明。

需要特別說明的是：用戶不需要include上面的頭文件，基本上普通spinlock和rw spinlock使用統一的頭文件介面，用戶只需要include一個include/linux/spinlock.h文件就OK了。

2、數據結構

rwlock_t數據結構定義如下：

typedef struct { 
    arch_rwlock_t raw_lock; 
} rwlock_t;

rwlock_t依賴arch對rw spinlock相關的定義。

3、API

我們整理RW spinlock的介面API如下表：

在具體的實現面，如何將archtecture independent的代碼轉到具體平臺的代碼的思路是和spin lock一樣的，這裡不再贅述。

2、ARM上的實現

對於arm平臺，rw spin lock的代碼位於arch/arm/include/asm/spinlock.h和spinlock_type.h（其實普通spin lock的代碼也是在這兩個文件中），和通用代碼類似，spinlock_type.h定義ARM相關的rw spin lock定義以及初始化相關的巨集；spinlock.h中包括了各種具體的實現。我們先看arch_rwlock_t的定義：

typedef struct { 
    u32 lock; 
} arch_rwlock_t

毫無壓力，就是一個32-bit的整數。從定義就可以看出rw spinlock不是ticket-based spin lock。我們再看看arch_write_lock的實現：

static inline void arch_write_lock(arch_rwlock_t *rw) 
{ 
    unsigned long tmp;

    prefetchw(&rw->lock); －－－－－－－知道後面需要訪問這個記憶體，先通知hw進行preloading cache 
    __asm__ __volatile__( 
"1:    ldrex    %0, [%1]\n" －－－－－獲取lock的值並保存在tmp中 
"    teq    %0, #0\n" －－－－－－－－判斷是否等於0 
    WFE("ne") －－－－－－－－－－如果tmp不等於0，那麼說明有read 或者write的thread持有鎖，那麼還是靜靜的等待吧。其他thread會在unlock的時候Send Event來喚醒該CPU的 
"    strexeq    %0, %2, [%1]\n" －－－－如果tmp等於0，將0x80000000這個值賦給lock 
"    teq    %0, #0\n" －－－－－－－－是否str成功，如果有其他thread在上面的過程插入進來就會失敗 
"    bne    1b" －－－－－－－－－如果不成功，那麼需要重新來過，否則持有鎖，進入臨界區 
    : "=&r" (tmp) －－－－％0 
    : "r" (&rw->lock), "r" (0x80000000)－－－－－－－％1和％2 
    : "cc");

    smp_mb(); －－－－－－－memory barrier的操作 
}

對於write lock，只要臨界區有一個thread進行讀或者寫的操作（具體判斷是針對32bit的lock進行，覆蓋了writer和reader thread），該thread都會進入spin狀態。如果臨界區沒有任何的讀寫thread，那麼writer進入臨界區，並設定lock＝0x80000000。我們再來看看write unlock的操作：

static inline void arch_write_unlock(arch_rwlock_t *rw) 
{ 
    smp_mb(); －－－－－－－memory barrier的操作

    __asm__ __volatile__( 
    "str    %1, [%0]\n"－－－－－－－－－－－恢復0值 
    : 
    : "r" (&rw->lock), "r" (0) －－－－－－－－％0和％1 
    : "cc");

    dsb_sev();－－－－－－－memory barrier的操作加上send event，wakeup其他 thread（那些cpu處於WFE狀態）
}

write unlock看起來很簡單，就是一個lock＝0x0的操作。瞭解了write相關的操作後，我們再來看看read的操作：

static inline void arch_read_lock(arch_rwlock_t *rw) 
{ 
    unsigned long tmp, tmp2;

    prefetchw(&rw->lock); 
    __asm__ __volatile__( 
"1:    ldrex    %0, [%2]\n"－－－－－－－－獲取lock的值並保存在tmp中 
"    adds    %0, %0, #1\n"－－－－－－－－tmp = tmp + 1 
"    strexpl    %1, %0, [%2]\n"－－－－如果tmp結果非負值，那麼就執行該指令，將tmp值存入lock 
    WFE("mi")－－－－－－－－－如果tmp是負值，說明有write thread，那麼就進入wait for event狀態 
"    rsbpls    %0, %1, #0\n"－－－－－判斷strexpl指令是否成功執行 
"    bmi    1b"－－－－－－－－－－如果不成功，那麼需要重新來過，否則持有鎖，進入臨界區 
    : "=&r" (tmp), "=&r" (tmp2)－－－－－－－－－－％0和％1 
    : "r" (&rw->lock)－－－－－－－－－－－－－－－％2 
    : "cc");

    smp_mb(); 
}

上面的代碼比較簡單，需要說明的是adds指令更新了狀態寄存器（指令中s那個字元就是這個意思），strexpl會根據adds指令的執行結果來判斷是否執行。pl的意思就是positive or zero，也就是說，如果結果是正數或者0（沒有thread在臨界區或者臨界區內有若幹read thread），該指令都會執行，如果是負數（有write thread在臨界區），那麼就不執行。OK，最後我們來看read unlock的函數：

static inline void arch_read_unlock(arch_rwlock_t *rw) 
{ 
    unsigned long tmp, tmp2;

    smp_mb();

    prefetchw(&rw->lock); 
    __asm__ __volatile__( 
"1:    ldrex    %0, [%2]\n"－－－－－－－－獲取lock的值並保存在tmp中 
"    sub    %0, %0, #1\n"－－－－－－－－tmp = tmp - 1 
"    strex    %1, %0, [%2]\n"－－－－－－將tmp值存入lock中 
"    teq    %1, #0\n"－－－－－－是否str成功，如果有其他thread在上面的過程插入進來就會失敗 
"    bne    1b"－－－－－－－如果不成功，那麼需要重新來過，否則離開臨界區 
    : "=&r" (tmp), "=&r" (tmp2)－－－－－－－－－－－－％0和％1 
    : "r" (&rw->lock)－－－－－－－－－－－－－－－－－％2 
    : "cc");

    if (tmp == 0) 
        dsb_sev();－－－－－如果read thread已經等於0，說明是最後一個離開臨界區的reader，那麼調用sev去喚醒WFE的cpu core 
}

最後，總結一下：

32個bit的lock，0～30的bit用來記錄進入臨界區的read thread的數目，第31個bit用來記錄write thread的數目，由於只允許一個write thread進入臨界區，因此1個bit就OK了。在這樣的設計下，read thread的數目最大就是2的30次冪減去1的數值，超過這個數值就溢出了，當然這個數值在目前的系統中已經足夠的大了，姑且認為它是安全的吧。

四、後記

read/write spinlock對於read thread和write thread採用相同的優先順序，read thread必須等待write thread完成離開臨界區才可以進入，而write thread需要等到所有的read thread完成操作離開臨界區才能進入。正如我們前面所說，這看起來對write thread有些不公平，但這就是read/write spinlock的特點。此外，在內核中，已經不鼓勵對read/write spinlock的使用了，RCU是更好的選擇。如何解決read/write spinlock優先順序問題？RCU又是什麼呢？我們下回分解。