## 研讀 [Linux 核心設計: RCU 同步機制](https://hackmd.io/@sysprog/linux-rcu#%E9%BB%9E%E9%A1%8C)

### 大綱
**RCU** 全名是 Read-Copy-Update 用途是創造一個不用鎖的讀取機制，但同時也不保證說所有讀取者讀取到的資料是相同的，可能會有些情況下會有差不多時間讀取的讀取者，獲取到不同資料，但在大多數情況下是相同的。

因此他的適用情境主要分為兩大點
1. 對 consistency 沒嚴格要求
2. 讀取較多，寫入較少

[Linux 核心設計: RCU 同步機制](https://hackmd.io/@sysprog/linux-rcu#%E9%BB%9E%E9%A1%8C) 內文讀取有說到 DNS 就很符合這個情況，只有在沒讀取到資訊時或 TTL 到期時會更新表格，而 DNS 本身就是層層的快取機制，當第一層沒獲取到資料則向更高階的 DNS 去發出查詢要求。

### RCU list 函式與顧及 memory ordering 的影響
跟撰寫核心空間其他程式碼一樣，需要確保順序的正確性，為了防止編譯器最佳化後順序不同，用到 `READ_ONCE`、 `WRITE_ONCE` 等函式，而 Linux 核心原始程式碼有好心的提供對應的 API

對於賦予值提供了 `rcu_assign_pointer`

#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)

可以看到這個巨集確實是透過 `WRITE_ONCE` 去確保寫入的正確性，但這可以發現它是在 NULL 時才呼叫 `WRITE_ONCE` ，把 p 直接設為 NULL 後，任何 `rcu_dereference(p)` 的讀者都會得到 NULL，並不會進一步讀取 p->next 或其它成員，因此不需要保證先寫入資料得順序性。反之則是呼叫 `smp_store_release`
而這裡的觀念就是除了編譯器最佳化外，硬體本身在多核心也有順序不同的問題，因此也需要對應的 `swp` 等函式去做處理，這裡的 `smp_store_release` 原始程式碼有很多種架構，這裡提出其中一種 [linux/include/asm-generic/barrier.h](https://elixir.bootlin.com/linux/v6.12.6/source/include/asm-generic/barrier.h#L194)

#define smp_store_release(p, v)						\
do {									\
	barrier();							\
	WRITE_ONCE(*p, v);						\
} while (0)

也就是 `barrier` 與 `WRITE_ONCE` 為基礎，保證「在此 store（釋放點）之前的所有 memory 操作（loads/stores）已完成且對其他 CPU 可見」，但也不阻止後續 loads/stores 與前面 loads 的 reorder

同理針對讀取值提供了 `rcu_dereference`

#define rcu_dereference(p) \
({ \
    typeof(p) _________p1 = p; \
    smp_read_barrier_depends(); \
    (_________p1); \
})

以上是簡化版，而可以看到其實就是多做了 CPU barrier ，確保硬體的順序性

### 寬限期
寬限期（grace period）是要確保所有在寬限期開始前進入的讀取臨界區都必須離開，才能安全回收舊版本資料。
而 `synchronize_rcu()` 會在一個完整的寬限期結束之後才回到呼叫者，也就是說，在所有當前正在執行的 RCU 讀取側臨界區都結束之後才會返回。
在 [https://linuxtv.org/](https://linuxtv.org/downloads/v4l-dvb-internals/device-drivers/API-synchronize-rcu.html?utm_source=chatgpt.com) 中寫到:
> Control will return to the caller some time after a full grace period has elapsed, in other words after all currently executing RCU read-side critical sections have completed. Note, however, that upon return from synchronize_rcu, the caller might well be executing concurrently with new RCU read-side critical sections that began while synchronize_rcu was waiting. RCU read-side critical sections are delimited by rcu_read_lock and rcu_read_unlock, and may be nested.

### linked list 實際應用
>我們希望刪除 B 節點，就將節點 A 的指標指向 C 節點，保持 B 節點的指標，然後刪除程式將進入寬限期檢查。由於 B 節點的內容沒有變更，讀到 B 的執行緒仍可繼續讀取 B 的後續節點。B 不能立即銷毀，它必須等待寬限期結束後，才能進行相應銷毀操作。由於 A 節點已指向 C 節點，當寬限期開始後，所有的後續讀取操作藉由 A 節點找到的是 C 節點，而 B 節點已隱藏，後續的讀取端執行緒都不會讀到它。這樣就確保寬限期過後，刪除 B 節點不對系統造成衝擊。