iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 13
1
自我挑戰組

Linux Inside - Synchronization & Interrupt系列 第 15

RCU(Read, Copy, Update) - What is RCU

範例參考我原本想丟 perfbook 的範例就好,但覺得不是很好理解,不小心又發現 Linux 的文件有一堆 RCU 的介紹,所以我決定改看 Linux 的文件來介紹

文件中有表示存在 LWN.net 的文章可以閱讀,這真的是我非常喜歡的一個網站,寫的都非常詳細@@

  1. What is RCU, Fundamentally?
  2. What is RCU? Part 2: Usage
  3. RCU part 3: the RCU API
  4. The RCU API, 2010 Edition
    2010 Big API Table
  5. The RCU API, 2014 Edition
    2014 Big API Table

目前會先閱讀第一份文章,其他再議

Seqlock

我們之前只介紹過 RWLock,但在講 RCU 之前還需要對 Seqlock 有點認識,顧名思義是 sequential locks,應用在 resource 是極小又簡單的情況,且少有 Write 需求

演算法很簡單
Writer: 增加 counter 的數值,然後使用 Spinlock,成功執行後,釋放 spinlock 並再次增加 counter 的數值
Reader: 讀取 Counter 的數值,確認 Counter 數值是否一樣,一樣的話,就能進入 critical section

在我看來這只是一個 Spinlock 的特化應用,用來讓使多個 Reader 同時讀取

還可以發現一點,他與 RWlock 極其相似,他們到底是差在哪呢?差在 RWLock 中 Writer 必需要等待到 Reader 都消失才能做存取,但是 Seqlock 只要輪到 Writer ,就會直接上鎖@@

What is RCU

參考 Linux 核心設計: RCU 同步機制

參考 RCU 初步認識

什麼是 RCU ? 這跟 Lock 系列的機制不同,RCU 是一個允許多個 Reader 及單個 Writer 同時運作的機制,沒錯!這又是一個 Lock-Free 系列的東西,這也是他與與 Seqlock/RWlock 最大的差別,不用因為寫入而上鎖

那麼他是怎麼做到的呢??這是透過維護多個版本來實作,如下圖所示

如果是 RWlock 為了保證每個 Reader 看到的資料都是一樣的,一定要全部鎖起來;而 RCU 是同時有多個 Reader ,看到多個不同的版本,只能保證等下一次讀取資料時,會更新到目前的狀態,這就是所謂的維護多個版本,也可以說這就是訂閱機制啦

那麼有這麼多個 Reader 我們怎麼知道,這個 Reader 現在是讀取什麼版本呢???

RCU 把這個部份分為兩個狀態「Removal」「Reclamation」,以下以刪除指標為例

  • Removal
    移除某個指標,但因為我們允許多個 Reader 同時運行,所以這時有些 Reader 的資料是還沒有被刪除的

    注意:移除的動作必須是 Atomic

  • Reclamation
    確保沒有 Reader 會再次使用這筆資料,可以真正把他刪除

    但是事情有這麼簡單嘛???我們之前光是探討 Concurrent Linked List 就發現,那是一篇論文==

    所以我們必須遵守以下兩個規定,才能真正的執行成功

    1. 所有 Reader 讀取 Linked List 必須是單向的,不回頭
    2. 所有 reader-side critical section 內的動作不能 Block 或 Preempt

    符合以上兩個規定的話,我們可以把 synchronize_rcu 簡單表示如下

    void synchronize_rcu(void) {
       int cpu;
       for_each_cpu(cpu);
       run_on(cpu);
    }
    

    這邊我並不確定是否存在允許 Preempt 的 synchronize_rcu 的實作,但這會妨礙我們理解 RCU ,所以也暫不研究

  • Grace Period
    Removal -> Reclamation 這段時間,也就是 for_each_cpu(cpu) 的時間,等待所有 CPU 執行完畢

從圖中我們可以發現,只有在 Grace Period 中才會存在多個版本@@ 其他時候大家看到的都一樣

API 們

在上圖中,我們看到了很多 API 的調用,以下作一些解釋,下圖表示這些 API 之間的關係

	    rcu_assign_pointer()
	                            +--------+
	    +---------------------->| reader |---------+
	    |                       +--------+         |
	    |                           |              |
	    |                           |              | Protect:
	    |                           |              | rcu_read_lock()
	    |                           |              | rcu_read_unlock()
	    |        rcu_dereference()  |              |
	    +---------+                 |              |
	    | updater |<----------------+              |
	    +---------+                                V
	    |                                    +-----------+
	    +----------------------------------->| reclaimer |
	                                         +-----------+
	      Defer:
	      synchronize_rcu() & call_rcu()

可以發現在執行 RCU 的時候,會有三種角色

  1. Updater
  2. Reader
  3. Reclaimer
  • rcu_read_lock()
    通知 Reclaimer 有一個 Reader 進入 read-side critical section

    但如果有設置 CONFIG_PREEMPT_RCU 則會允許他被搶佔==,這非常可能表示存在 Preempt 版本的 synchronize_rcu

  • rcu_read_unlock()
    通知 Reclaimer 有一個 Reader 離開 read-side critical section

  • synchronize_rcu() / call_rcu()
    synchronize_rcu 代表同步,等待所有 CPU 執行完畢

    	         CPU 0                  CPU 1                 CPU 2
           ----------------- ------------------------- ---------------
       1.  rcu_read_lock()
       2.                    enters synchronize_rcu()
       3.                                               rcu_read_lock()
       4.  rcu_read_unlock()
       5.                     exits synchronize_rcu()
       6.                                              rcu_read_unlock()
    

    注意:我們只會等待在 synchronize_rcu 執行之前的 rcu_read_lock 執行結束,如範例所示,並不會等待 CPU 2

    就算真的等到所有 CPU 了,涵式也不一定會馬上回傳,為了各種效率考量,會跟 Schedule 去作配合

    call_rcusynchronize_rcu 的 callback function

    Updater 並不是直接監視所有 Reader ,而是透過 Reclaimer 來觀測 Reader 的狀態

  • rcu_dereference()
    rcu_dereference 我相信大家都是擅長寫 C 語言的朋友,dereference 不就是我們的指標嗎@@

    取得最新的資料,如果只是一般的取值是不夠的,我們需要保證他執行的順序,會使用到各種 Memory Barrier

    /* 1st read-side critical section */
    rcu_read_lock();
    p = rcu_dereference(head.next);
    rcu_read_unlock();
    
    /* outside read-side critical section */
    x = p->address;	/* BUG!!! */
    
    /* 2nd read-side critical section */
    rcu_read_lock();
    y = p->data;	/* BUG!!! */
    rcu_read_unlock();
    

    注意:在 read-side critical section 之外的地方,調用 rcu_deference 取得的指標是非法的,在另外一個 read-side critical section 調用也是非法的

  • rcu_assign_pointer()
    修改指標,與 rcu_derefence 相同,要使用各種 Memory Barrier

    rcu_deference rcu_assign_pointer 兩者之間的關係,如何實作與資料結構有非常大的關係,因為我還沒看這一部份,所以我並知道如何描述他們在對什麼東西進行操作

Others

因為要去比 2019 全國智慧製造大數據分析競賽(imbd)了,花了很多時間在研究如何調校模型會比較好,很可惜的是今天比賽也沒有好的成果,資料分析真的不是我的專業==

也花了非常非常多時間刷 Leetcode,Leetcode 刷破 50 題了@@

老實說很久沒寫競賽題目,以前打 ITSA 或是 NCPC 的時候還會加減刷,現在真的都忘記了,完全寫不快,Medium 就算知道怎麼寫,也需要花個 20-30 分鐘才能刷一題, Hard 就等靈感@@

BTW 如果想超過一個禮拜想不出答案,我就會去看答案了

一個禮拜刷了 10 幾題吧,其中有幾題我印象特別深刻

  1. 142. Linked List Cycle II
    這題只是一個龜兔賽跑問題的變形,因為我實在不了解,為什麼可以從相遇的點再出發,就可以找到入口

    但無所謂@@ 我直接把之前介紹的 Concurrent Linked List 實作中的技巧應用上去,我把每個經過的點都標記,就順利的找到入口了

    Answer

  2. 1192. Critical Connections in a Network
    這題我解不出來,是看答案的,但以前沒有想過如何在一個無向圖中尋找 Circle,解法似乎蠻有名的,「Tarjan 演算法」
    原理非常簡單,使用 DFS 暴力搜尋,但重點是額外紀錄兩個東西

    1. 現在是第幾個被找到
    2. 如果這是一個 Circle,Circle 中最早被找到的是誰

    當然在實作的時候,還需要注意 parent 是誰,又或者答案要存在哪,不過這是小事@@

More

至於更多 RCU 的介紹,就等明天我再來閱讀了


上一篇
RWLock: 只有資料結構以及原理 ......
下一篇
RCU API 原始碼閱讀
系列文
Linux Inside - Synchronization & Interrupt18

尚未有邦友留言

立即登入留言