歡迎光臨
每天分享高質量文章

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)

已同步到看一看
赞(0)

分享創造快樂