Linux核心同步機制之：Seqlock

一、前言

普通的spin lock對待reader和writer是一視同仁，RW spin lock給reader賦予了更高的優先順序，那麼有沒有讓writer優先的鎖的機制呢？答案就是seqlock。本文主要描述linux kernel 4.0中的seqlock的機制，首先是seqlock的工作原理，如果想淺嘗輒止，那麼瞭解了概念性的東東就OK了，也就是第二章了，當然，我還是推薦普通的驅動工程師瞭解seqlock的API，第三章給出了一個簡單的例子，瞭解了這些，在驅動中（或者在其他核心模組）使用seqlock就可以易如反掌了。細節是魔鬼，概念性的東西需要天才的思考，不是說就程式碼實現的細節就無足輕重，如果想進入seqlock的內心世界，推薦閱讀第四章seqlock的程式碼實現，這一章和cpu體系結構相關的內容我們選擇了ARM64（呵呵～～要跟上時代的步伐）。最後一章是參考資料，如果覺得本文描述不清楚，可以參考這些經典文獻，在無數不眠之夜，她們給我心靈的慰籍，也願能夠給讀者帶來快樂。

二、工作原理

1、overview

seqlock這種鎖機制是傾向writer thread，也就是說，除非有其他的writer thread進入了臨界區，否則它會長驅直入，無論有多少的reader thread都不能阻擋writer的腳步。writer thread這麼霸道，reader腫麼辦？對於seqlock，reader這一側需要進行資料訪問的過程中檢測是否有併發的writer thread操作，如果檢測到併發的writer，那麼重新read。透過不斷的retry，直到reader thread在臨界區的時候，沒有任何的writer thread插入即可。這樣的設計對reader而言不是很公平，特別是如果writer thread負荷比較重的時候，reader thread可能會retry多次，從而導致reader thread這一側效能的下降。

總結一下seqlock的特點：臨界區只允許一個writer thread進入，在沒有writer thread的情況下，reader thread可以隨意進入，也就是說reader不會阻擋reader。在臨界區只有有reader thread的情況下，writer thread可以立刻執行，不會等待。

2、writer thread的操作

對於writer thread，獲取seqlock操作如下：

（1）獲取鎖（例如spin lock），該鎖確保臨界區只有一個writer進入。

（2）sequence counter加一

釋放seqlock操作如下：

（1）釋放鎖，允許其他writer thread進入臨界區。

（2）sequence counter加一（註意：不是減一哦，sequence counter是一個不斷累加的counter）

由上面的操作可知，如果臨界區沒有任何的writer thread，那麼sequence counter是偶數（sequence counter初始化為0），如果臨界區有一個writer thread（當然，也只能有一個），那麼sequence counter是奇數。

3、reader thread的操作如下：

（1）獲取sequence counter的值，如果是偶數，可以進入臨界區，如果是奇數，那麼等待writer離開臨界區（sequence counter變成偶數）。進入臨界區時候的sequence counter的值我們稱之old sequence counter。

（2）進入臨界區，讀取資料

（3）獲取sequence counter的值，如果等於old sequence counter，說明一切OK，否則回到step（1）

4、適用場景。一般而言，seqlock適用於：

（1）read操作比較頻繁

（2）write操作較少，但是效能要求高，不希望被reader thread阻擋（之所以要求write操作較少主要是考慮read side的效能）

（3）資料型別比較簡單，但是資料的訪問又無法利用原子操作來保護。我們舉一個簡單的例子來描述：假設需要保護的資料是一個連結串列，essay-header—>A node—>B node—>C node—>null。reader thread遍歷連結串列的過程中，將B node的指標賦給了臨時變數x，這時候，中斷發生了，reader thread被preempt（註意，對於seqlock，reader並沒有禁止搶佔）。這樣在其他cpu上執行的writer thread有充足的時間釋放B node的memory（註意：reader thread中的臨時變數x還指向這段記憶體）。當read thread恢復執行，並透過x這個指標進行記憶體訪問（例如試圖透過next找到C node），悲劇發生了……

三、API示例

在kernel中，jiffies_64儲存了從系統啟動以來的tick數目，對該資料的訪問（以及其他jiffies相關資料）需要持有jiffies_lock這個seq lock。

1、reader side程式碼如下：

u64 get_jiffies_64(void) 
{

    do { 
        seq = read_seqbegin(&jiffies;_lock); 
        ret = jiffies_64; 
    } while (read_seqretry(&jiffies;_lock, seq)); 
}

2、writer side程式碼如下：

static void tick_do_update_jiffies64(ktime_t now) 
{ 
    write_seqlock(&jiffies;_lock);

臨界區會修改jiffies_64等相關變數，具體程式碼略 
    write_sequnlock(&jiffies;_lock); 
}

對照上面的程式碼，任何工程師都可以比著葫蘆畫瓢，使用seqlock來保護自己的臨界區。當然，seqlock的介面API非常豐富，有興趣的讀者可以自行閱讀seqlock.h檔案。

四、程式碼實現

1、seq lock的定義

typedef struct { 
    struct seqcount seqcount;－－－－－－－－－－sequence counter 
    spinlock_t lock; 
} seqlock_t;

seq lock實際上就是spin lock ＋ sequence counter。

2、write_seqlock/write_sequnlock

static inline void write_seqlock(seqlock_t *sl) 
{ 
    spin_lock(&sl-;>lock);

    sl->sequence++; 
    smp_wmb(); 
}

唯一需要說明的是smp_wmb這個用於SMP場合下的寫記憶體屏障，它確保了編譯器以及CPU都不會打亂sequence counter記憶體訪問以及臨界區記憶體訪問的順序（臨界區的保護是依賴sequence counter的值，因此不能打亂其順序）。write_sequnlock非常簡單，留給大家自己看吧。

3、read_seqbegin

static inline unsigned read_seqbegin(const seqlock_t *sl) 
{  
    unsigned ret;

repeat: 
    ret = ACCESS_ONCE(sl->sequence); －－－進入臨界區之前，先要獲取sequenc counter的快照 
    if (unlikely(ret & 1)) { －－－－－如果是奇數，說明有writer thread 
        cpu_relax(); 
        goto repeat; －－－－如果有writer，那麼先不要進入臨界區，不斷的polling sequenc counter 
    }

    smp_rmb(); －－－確保sequenc counter和臨界區的記憶體訪問順序 
    return ret; 
}

如果有writer thread，read_seqbegin函式中會有一個不斷polling sequenc counter，直到其變成偶數的過程，在這個過程中，如果不加以控制，那麼整體系統的效能會有損失（這裡的效能指的是功耗和速度）。因此，在polling過程中，有一個cpu_relax的呼叫，對於ARM64，其程式碼是：

static inline void cpu_relax(void) 
{ 
        asm volatile(“yield” ::: “memory”); 
}

yield指令用來告知硬體系統，本cpu上執行的指令是polling操作，沒有那麼急迫，如果有任何的資源衝突，本cpu可以讓出控制權。

4、read_seqretry

static inline unsigned read_seqretry(const seqlock_t *sl, unsigned start) 
{ 
    smp_rmb();－－－確保sequenc counter和臨界區的記憶體訪問順序 
    return unlikely(sl->sequence != start); 
}

start引數就是進入臨界區時候的sequenc counter的快照，比對當前退出臨界區的sequenc counter，如果相等，說明沒有writer進入打攪reader thread，那麼可以愉快的離開臨界區。

還有一個比較有意思的邏輯問題：read_seqbegin為何要進行奇偶判斷？把一切都推到read_seqretry中進行判斷不可以嗎？也就是說，為何read_seqbegin要等到沒有writer thread的情況下才進入臨界區？其實有writer thread也可以進入，反正在read_seqretry中可以進行奇偶以及相等判斷，從而保證邏輯的正確性。當然，這樣想也是對的，不過在performance上有欠缺，reader在檢測到有writer thread在臨界區後，仍然放reader thread進入，可能會導致writer thread的一些額外的開銷（cache miss），因此，最好的方法是在read_seqbegin中攔截。

五、參考文獻

1、Understanding the Linux Kernel 3rd Edition

2、Linux Kernel Development 3rd Edition

3、Perfbook (https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html)