# Linux 核心設計: RCU 同步機制 研讀筆記
contributed by < `Jordymalone` >

探究本題材之前，請先研讀 Linux 核心設計: 淺談同步機制

RCU (Read-Copy Update)
> 參閱 [What is RCU, Fundamentally?](https://lwn.net/Articles/262464/)

strong consistency ?

> RCU ensures that reads are coherent by maintaining multiple versions of objects and ensuring that they are not freed up until all pre-existing read-side critical sections complete.

透過保留資料的多個版本，並在新版本出現前的讀取操作結束之前不會釋放舊版本，來保證一致性，那這個資料要儲存在哪裡？萬一一直寫的話不就一堆版本要維護？

用 RCU 的前提就是 讀多寫少，這樣記憶體開銷才在可接受範圍。

什麼是 **寬限期 (grace period)**?
> 指義務期限過後緊接的一段時期，只要在寬限期內履行義務，就可免除因未能按時完成任務而應採取的滯納金或進一步行動。寬限期可從幾分鐘到幾天甚至更長的時間不等。最常見的情況為借貸，其他情況如支付帳單、滿足政府或法律要求也適用。RCU 借用 grace period 這概念，描述共用資料的處理期間，寫入端執行緒發布共用資料的更新作為寬限期的起點，直到諸多讀取端執行緒得以達成取得更新資料的操作為止。

`synchronize_rcu()`:
* 等待 所有自本函式執行前 已經進入 RCU 讀取區段的讀者呼叫 rcu_read_unlock()。
* 它保證：當 synchronize_rcu() 返回後，不會再有任何讀者持有舊節點的指標，你就可以安全地 kfree() 或回收這個 handler 的記憶體

:::info
會不會遇到某個讀者讀太久，導致一直無法返回 synchronize_rcu() 並作 kfree()？這樣會有什麼影響嗎？
:::


Publish-Subscribe 機制？

* updater 更新內容後，透過呼叫指定界面進行發佈，reader 呼叫特定介面來讀取已發布的內容

:::info
類似廣播的機制嗎?
:::

### Memory ordering Effect

[memory barrier](https://www.kernel.org/doc/Documentation/memory-barriers.txt) ?

RCU 機制對 memory barrier 進行包裝，提供了專用 API 來解決該問題。

#define rcu_assign_pointer(p, v)					      \
do {									      \
    uintptr_t _r_a_p__v = (uintptr_t)(v);				      \
    rcu_check_sparse(p, __rcu);					      \
    								      \
    if (__builtin_constant_p(v) && (_r_a_p__v) == (uintptr_t)NULL)	      \
        WRITE_ONCE((p), (typeof(p))(_r_a_p__v));		      \
    else								      \
        smp_store_release(&p, RCU_INITIALIZER((typeof(p))_r_a_p__v)); \
} while (0)

`rcu_assign_pointer()` 是一個專門用來「更新 RCU 保護指標」的工具。它不只是在程式中做 p = v 這種簡單指派，它還保證了記憶體的寫入順序，確保在你「把指標發佈出去之前」，你已經把那份資料初始化完成了。

> RCU 保護指標 - 我們希望在不加鎖的情況下讓讀者讀資料時使用的那個指標，為了安全，我們會在寫入它的時候用 `rcu_assign_pointer`，在讀的時候用 `rcu_dereference`，這樣才能保證記憶體一致性和正確性。

:::info
`WRITE_ONCE(x, val)` 是什麼？似乎很常看到
強制讓對變數 x 的寫入動作，不可被編譯器優化掉、不可被重排，也不可被拆分，保證寫入動作如實、一次性地發生。
但注意，它：
* 不是 memory barrier
* 不是原子操作（atomic）
* 只是針對編譯器與 store-order 的語意防護 (by gpt)
:::

可見其實作只是在數值指派之前，加了 `WRITE_ONCE` 這樣的 memory barrier 來確保程式碼的執行順序。另外，上方程式碼列表出現的 `__rcu`，只是作為編譯過程的檢查條件用途，主要搭配 Sparse。

> [Sparse](https://www.kernel.org/doc/html/latest/dev-tools/sparse.html) is a semantic checker for C programs; it can be used to find a number of potential problems with kernel code
:::info
所以 sparse 是啥？
:::

為了避免在存取資料時，新舊資料的不同步，Linux 提供了以下的巨集
`linux/include/linux/rcupdate.h`:

#define rcu_dereference_check(p, c) \
    __rcu_dereference_check((p), (c) || rcu_read_lock_held(), __rcu)

#define __rcu_dereference_check(p, c, space) \
({ \
    /* Dependency order vs. p above. */ \
    typeof(*p) *________p1 = (typeof(*p) *__force)READ_ONCE(p); \
    RCU_LOCKDEP_WARN(!(c), "suspicious rcu_dereference_check() usage"); \
    rcu_check_sparse(p, space); \
    ((typeof(*p) __force __kernel *)(________p1)); \
})

#define rcu_dereference(p) rcu_dereference_check(p, 0)

> 待整理

### 資料讀取的完整性

在 Linux 核心中，RCU 用來保護以下場景:
* 指標
* linked list
* hlist (hash list)

我們理解到藉由 RCU，可達到 lock-free 的操作。

q = malloc(sizeof(*p));
*q = *p; 
q->b = 2;
q->c = 3; 
list_replace_rcu(&p->list , &q->list);
synchronize_rcu();
free(p);

第 2 行將舊節點內容複製給新節點:

我原本以為第 2 行是等同於把 q pointer 也指向 p pointer 指著的地方，實際上不是，我說的情況是 `q = p;` 才對。注意細節啊！

第 5 行具體是怎麼做 replace？

摘錄自 [v6.15-rc1](https://elixir.bootlin.com/linux/v6.15-rc1/source/include/linux/rculist.h#L233) `/include/linux/rculist.h`:

/**
 * list_replace_rcu - replace old entry by new one
 * @old : the element to be replaced
 * @new : the new element to insert
 *
 * The @old entry will be replaced with the @new entry atomically from
 * the perspective of concurrent readers.  It is the caller's responsibility
 * to synchronize with concurrent updaters, if any.
 *
 * Note: @old should not be empty.
 */
static inline void list_replace_rcu(struct list_head *old,
				struct list_head *new)
{
	new->next = old->next;
	new->prev = old->prev;
	rcu_assign_pointer(list_next_rcu(new->prev), new);
	new->next->prev = new;
	old->prev = LIST_POISON2;
}

第 6 行 synchronize_rcu 執行後，會經歷寬限期，之後所有的在 list_replace_rcu 之前進入 CS 的讀取端執行緒都已完成讀取操作，並離開 CS，也不會有新的讀取端執行緒讀取 (5, 6, 7)，後者的節點也變為黑色方框，表示沒有任何資料參照。這時 list 回歸到唯一版本。

以上所有操作都不需要持有 lock，但衍生新的問題: 何時可釋放 p 指向的節點？因為無法確認是否仍有其他執行緒在讀取該記憶體區塊。
> 待測試 [rcu-list](https://github.com/sysprog21/concurrent-programs/tree/master/rcu-list)

- [ ] QBSR 演算法

### RCU 模型


### 待整理

* [Using RCU for linked lists — a case study](https://lwn.net/Articles/610972/)
* [rculist](https://github.com/torvalds/linux/blob/master/include/linux/rculist.h)