背景
Read the fucking source code!--By 魯迅A picture is worth a thousand words.--By 高爾基
說明：
- Kernel版本：4.14
- ARM64處理器，Contex-A53，雙核
- 使用工具：Source Insight 3.5， Visio
1. 概述
RCU, Read-Copy-Update，是Linux內核中的一種同步機制，
RCU常被描述為讀寫鎖的替代品，它的特點是讀者并不需要直接與寫者進行同步，讀者與寫者也能并發的執行，RCU的目標就是最大程度來減少讀者側的開銷，因此也常用于對讀者性能要求高的場景，
-
優點：
- 讀者側開銷很少、不需要獲取任何鎖，不需要執行原子指令或者記憶體屏障；
- 沒有死鎖問題；
- 沒有優先級反轉的問題；
- 沒有記憶體泄露的危險問題；
- 很好的實時延遲；
-
缺點：
- 寫者的同步開銷比較大，寫者之間需要互斥處理；
- 使用上比其他同步機制復雜；
來一張圖片來描述下大體的操作吧：
- 多個讀者可以并發訪問臨界資源，同時使用
rcu_read_lock/rcu_read_unlock來標定臨界區； - 寫者(
updater)在更新臨界資源的時候，拷貝一份副本作為基礎進行修改，當所有讀者離開臨界區后，把指向舊臨界資源的指標指向更新后的副本，并對舊資源進行回收處理； - 圖中只顯示一個寫者，當存在多個寫者的時候，需要在寫者之間進行互斥處理；
上述的描述比較簡單，RCU的實作很復雜，本文先對RCU來一個初印象，并結合介面進行實體分析，后續文章再逐層深入到背后的實作原理，開始吧！
2. RCU基礎
2.1 RCU基本要素
RCU的基本思想是將更新Update操作分為兩個部分：1）Removal移除；2）Reclamation回收，
直白點來理解就是，臨界資源被多個讀者讀取，寫者在拷貝副本修改后進行更新時，第一步需要先把舊的臨界資源資料移除（修改指標指向），第二步需要把舊的資料進行回收（比如kfree），
因此，從功能上分為以下三個基本的要素：Reader/Updater/Reclaimer，三者之間的互動如下圖：
-
Reader
- 使用
rcu_read_lock和rcu_read_unlock來界定讀者的臨界區，訪問受RCU保護的資料時，需要始終在該臨界區域內訪問； - 在訪問受保護的資料之前，需要使用
rcu_dereference來獲取RCU-protected指標； - 當使用不可搶占的
RCU時，rcu_read_lock/rcu_read_unlock之間不能使用可以睡眠的代碼；
- 使用
-
Updater
- 多個Updater更新資料時，需要使用互斥機制進行保護；
- Updater使用
rcu_assign_pointer來移除舊的指標指向，指向更新后的臨界資源； - Updater使用
synchronize_rcu或call_rcu來啟動Reclaimer，對舊的臨界資源進行回收，其中synchronize_rcu表示同步等待回收，call_rcu表示異步回收；
-
Reclaimer
- Reclaimer回收的是舊的臨界資源；
- 為了確保沒有讀者正在訪問要回收的臨界資源，Reclaimer需要等待所有的讀者退出臨界區，這個等待的時間叫做寬限期（
Grace Period）；
2.2 RCU三個基本機制
用來提供上述描述的功能，RCU基于三種機制來實作，
2.2.1 Publish-Subscribe Mechanism
訂閱機制是個什么概念，來張圖：
Updater與Reader類似于Publisher和Subsriber的關系；Updater更新內容后呼叫介面進行發布，Reader呼叫介面讀取發布內容；
那么這種訂閱機制，需要做點什么來保證呢？來看一段偽代碼：
/* Definiton of global structure */
1 struct foo {
2 int a;
3 int b;
4 int c;
5 };
6 struct foo *gp = NULL;
7
8 /* . . . */
9 /* =========Updater======== */
10 p = kmalloc(sizeof(*p), GFP_KERNEL);
11 p->a = 1;
12 p->b = 2;
13 p->c = 3;
14 gp = p;
15
16 /* =========Reader======== */
17 p = gp;
18 if (p != NULL) {
19 do_something_with(p->a, p->b, p->c);
20 }
乍一看似乎問題不大，Updater進行賦值更新，Reader進行讀取和其他處理，然而，由于存在編譯亂序和執行亂序的問題，上述代碼的執行順序不見得就是代碼的順序，比如在某些架構（DEC Alpha）中，讀者的操作部分，可能在p賦值之前就操作了do_something_with()，
為了解決這個問題，Linux提供了rcu_assign_pointer/rcu_dereference宏來確保執行順序，Linux內核也基于rcu_assign_pointer/rcu_dereference宏進行了更高層的封裝，比如list, hlist，因此，在內核中有三種被RCU保護的場景：1）指標；2）list鏈表；3）hlist哈希鏈表，
針對這三種場景，Publish-Subscribe介面如下表：
2.2.2 Wait For Pre-Existing RCU Readers to Complete
Reclaimer需要對舊的臨界資源進行回收，那么問題來了，什么時候進行呢？因此RCU需要提供一種機制來確保之前的RCU讀者全部都已經完成，也就是退出了rcu_read_lock/rcu_read_unlock標定的臨界區后，才能進行回收處理，
- 圖中Readers和Updater并發執行；
- 當Updater執行
Removal操作后，呼叫synchronize_rcu，標志著更新結束并開始進入回收階段； - 在
synchronize_rcu呼叫后，此時可能還有新的讀者來讀取臨界資源(更新后的內容)，但是，Grace Period只等待Pre-Existing的讀者，也就是在圖中的Reader-4, Reader-5，只要這些之前就存在的RCU讀者退出臨界區后，意味著寬限期的結束，因此就進行回收處理作業了； synchronize_rcu并不是在最后一個Pre-ExistingRCU讀者離開臨界區后立馬就回傳，它可能存在一個調度延遲；
2.2.3 Maintain Multiple Versions of Recently Updated Objects
從2.2.2節可以看出，在Updater進行更新后，在Reclaimer進行回收之前，是會存在新舊兩個版本的臨界資源的，只有在synchronize_rcu回傳后，Reclaimer對舊的臨界資源進行回收，最后剩下一個版本，顯然，在有多個Updater時，臨界資源的版本會更多，
還是來張圖吧，分別以指標和鏈表為例：
- 呼叫
synchronize_rcu開始為臨界點，分別維護不同版本的臨界資源； - 等到Reclaimer回收舊版本資源后，最終歸一統；
3. RCU示例分析
是時候來一波fucking sample code了，
- 整體的代碼邏輯：
- 構造四個內核執行緒，兩個內核執行緒測驗指標的RCU保護操作，兩個內核執行緒用于測驗鏈表的RCU保護操作；
- 在回收的時候，分別用了
synchronize_rcu同步回收和call_rcu異步回收兩種機制； - 為了簡化代碼，基本的容錯判斷都已經省略了；
- 沒有考慮多個Updater的機制，因此，也省略掉了Updater之間的互斥操作；
#include <linux/module.h>
#include <linux/init.h>
#include <linux/slab.h>
#include <linux/kthread.h>
#include <linux/rcupdate.h>
#include <linux/delay.h>
struct foo {
int a;
int b;
int c;
struct rcu_head rcu;
struct list_head list;
};
static struct foo *g_pfoo = NULL;
LIST_HEAD(g_rcu_list);
struct task_struct *rcu_reader_t;
struct task_struct *rcu_updater_t;
struct task_struct *rcu_reader_list_t;
struct task_struct *rcu_updater_list_t;
/* 指標的Reader操作 */
static int rcu_reader(void *data)
{
struct foo *p = NULL;
int cnt = 100;
while (cnt--) {
msleep(100);
rcu_read_lock();
p = rcu_dereference(g_pfoo);
pr_info("%s: a = %d, b = %d, c = %d\n",
__func__, p->a, p->b, p->c);
rcu_read_unlock();
}
return 0;
}
/* 回收處理操作 */
static void rcu_reclaimer(struct rcu_head *rh)
{
struct foo *p = container_of(rh, struct foo, rcu);
pr_info("%s: a = %d, b = %d, c = %d\n",
__func__, p->a, p->b, p->c);
kfree(p);
}
/* 指標的Updater操作 */
static int rcu_updater(void *data)
{
int value = https://www.cnblogs.com/LoyenWang/p/1;
int cnt = 100;
while (cnt--) {
struct foo *old;
struct foo *new = (struct foo *)kzalloc(sizeof(struct foo), GFP_KERNEL);
msleep(200);
old = g_pfoo;
*new = *g_pfoo;
new->a = value;
new->b = value + 1;
new->c = value + 2;
rcu_assign_pointer(g_pfoo, new);
pr_info("%s: a = %d, b = %d, c = %d\n",
__func__, new->a, new->b, new->c);
call_rcu(&old->rcu, rcu_reclaimer);
value++;
}
return 0;
}
/* 鏈表的Reader操作 */
static int rcu_reader_list(void *data)
{
struct foo *p = NULL;
int cnt = 100;
while (cnt--) {
msleep(100);
rcu_read_lock();
list_for_each_entry_rcu(p, &g_rcu_list, list) {
pr_info("%s: a = %d, b = %d, c = %d\n",
__func__, p->a, p->b, p->c);
}
rcu_read_unlock();
}
return 0;
}
/* 鏈表的Updater操作 */
static int rcu_updater_list(void *data)
{
int cnt = 100;
int value = https://www.cnblogs.com/LoyenWang/p/1000;
while (cnt--) {
msleep(100);
struct foo *p = list_first_or_null_rcu(&g_rcu_list, struct foo, list);
struct foo *q = (struct foo *)kzalloc(sizeof(struct foo), GFP_KERNEL);
*q = *p;
q->a = value;
q->b = value + 1;
q->c = value + 2;
list_replace_rcu(&p->list, &q->list);
pr_info("%s: a = %d, b = %d, c = %d\n",
__func__, q->a, q->b, q->c);
synchronize_rcu();
kfree(p);
value++;
}
return 0;
}
/* module初始化 */
static int rcu_test_init(void)
{
struct foo *p;
rcu_reader_t = kthread_run(rcu_reader, NULL, "rcu_reader");
rcu_updater_t = kthread_run(rcu_updater, NULL, "rcu_updater");
rcu_reader_list_t = kthread_run(rcu_reader_list, NULL, "rcu_reader_list");
rcu_updater_list_t = kthread_run(rcu_updater_list, NULL, "rcu_updater_list");
g_pfoo = (struct foo *)kzalloc(sizeof(struct foo), GFP_KERNEL);
p = (struct foo *)kzalloc(sizeof(struct foo), GFP_KERNEL);
list_add_rcu(&p->list, &g_rcu_list);
return 0;
}
/* module清理作業 */
static void rcu_test_exit(void)
{
kfree(g_pfoo);
kfree(list_first_or_null_rcu(&g_rcu_list, struct foo, list));
kthread_stop(rcu_reader_t);
kthread_stop(rcu_updater_t);
kthread_stop(rcu_reader_list_t);
kthread_stop(rcu_updater_list_t);
}
module_init(rcu_test_init);
module_exit(rcu_test_exit);
MODULE_AUTHOR("Loyen");
MODULE_LICENSE("GPL");
為了證明沒有騙人，貼出在開發板上運行的輸出log，如下圖：
4. API介紹
4.1 核心API
下邊的這些介面，不能更核心了，
a. rcu_read_lock() //標記讀者臨界區的開始
b. rcu_read_unlock() //標記讀者臨界區的結束
c. synchronize_rcu() / call_rcu() //等待Grace period結束后進行資源回收
d. rcu_assign_pointer() //Updater使用這個宏對受RCU保護的指標進行賦值
e. rcu_dereference() //Reader使用這個宏來獲取受RCU保護的指標
4.2 其他相關API
基于核心的API，擴展了其他相關的API，如下，不再詳述：
RCU list traversal::
list_entry_rcu
list_entry_lockless
list_first_entry_rcu
list_next_rcu
list_for_each_entry_rcu
list_for_each_entry_continue_rcu
list_for_each_entry_from_rcu
list_first_or_null_rcu
list_next_or_null_rcu
hlist_first_rcu
hlist_next_rcu
hlist_pprev_rcu
hlist_for_each_entry_rcu
hlist_for_each_entry_rcu_bh
hlist_for_each_entry_from_rcu
hlist_for_each_entry_continue_rcu
hlist_for_each_entry_continue_rcu_bh
hlist_nulls_first_rcu
hlist_nulls_for_each_entry_rcu
hlist_bl_first_rcu
hlist_bl_for_each_entry_rcu
RCU pointer/list update::
rcu_assign_pointer
list_add_rcu
list_add_tail_rcu
list_del_rcu
list_replace_rcu
hlist_add_behind_rcu
hlist_add_before_rcu
hlist_add_head_rcu
hlist_add_tail_rcu
hlist_del_rcu
hlist_del_init_rcu
hlist_replace_rcu
list_splice_init_rcu
list_splice_tail_init_rcu
hlist_nulls_del_init_rcu
hlist_nulls_del_rcu
hlist_nulls_add_head_rcu
hlist_bl_add_head_rcu
hlist_bl_del_init_rcu
hlist_bl_del_rcu
hlist_bl_set_first_rcu
RCU::
Critical sections Grace period Barrier
rcu_read_lock synchronize_net rcu_barrier
rcu_read_unlock synchronize_rcu
rcu_dereference synchronize_rcu_expedited
rcu_read_lock_held call_rcu
rcu_dereference_check kfree_rcu
rcu_dereference_protected
bh::
Critical sections Grace period Barrier
rcu_read_lock_bh call_rcu rcu_barrier
rcu_read_unlock_bh synchronize_rcu
[local_bh_disable] synchronize_rcu_expedited
[and friends]
rcu_dereference_bh
rcu_dereference_bh_check
rcu_dereference_bh_protected
rcu_read_lock_bh_held
sched::
Critical sections Grace period Barrier
rcu_read_lock_sched call_rcu rcu_barrier
rcu_read_unlock_sched synchronize_rcu
[preempt_disable] synchronize_rcu_expedited
[and friends]
rcu_read_lock_sched_notrace
rcu_read_unlock_sched_notrace
rcu_dereference_sched
rcu_dereference_sched_check
rcu_dereference_sched_protected
rcu_read_lock_sched_held
SRCU::
Critical sections Grace period Barrier
srcu_read_lock call_srcu srcu_barrier
srcu_read_unlock synchronize_srcu
srcu_dereference synchronize_srcu_expedited
srcu_dereference_check
srcu_read_lock_held
SRCU: Initialization/cleanup::
DEFINE_SRCU
DEFINE_STATIC_SRCU
init_srcu_struct
cleanup_srcu_struct
All: lockdep-checked RCU-protected pointer access::
rcu_access_pointer
rcu_dereference_raw
RCU_LOCKDEP_WARN
rcu_sleep_check
RCU_NONIDLE
好吧，羅列這些API有點然并卵，
RCU這個神秘的面紗算是初步揭開了，再往里邊扒衣服的話，就會顯得有些難了，畢竟RCU背后的實作機制確實挺困難的，那么，問題來了，要不要做一個扒衣見君者呢，敬請關注吧，
參考
Documentation/RCU
What is RCU, Fundamentally?
What is RCU? Part 2: Usage
RCU part 3: the RCU API
Introduction to RCU
歡迎關注公眾號，持續以圖文形式分享內核機制文章
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/108876.html
標籤：Linux