Linux RCU Q&A
Q1: Linux RCU是什么
A: Read-Copy-Update, 是Linux內(nèi)核里的一種"鎖"機制, 可以保證并發(fā)讀的時候基本無加鎖的等待, 不同于rwlock, RCU在寫入的時候也可以讀
Q2: RCU是如何執(zhí)行寫入操作的
A: RCU在寫入的時候, 采用以下步驟(需要修改的內(nèi)容在結(jié)構(gòu)體A內(nèi)):
- 新建一個結(jié)構(gòu)體, 將原結(jié)構(gòu)體A拷貝到新結(jié)構(gòu)體內(nèi)(Copy),
- 根據(jù)需要修改結(jié)構(gòu)體的內(nèi)容(Update),
- 然后將原來指向該結(jié)構(gòu)體的指針指向新的結(jié)構(gòu)體. 此時原結(jié)構(gòu)體A出現(xiàn)兩份
- 待所有讀操作完成后, 刪除原結(jié)構(gòu)體, 這樣結(jié)構(gòu)體A只有一份最新的
以鏈表為例:
- 初始狀態(tài): A--->B--->C
- copy: B' = malloc(sizeof(B)); B' <= B
- update: B'->x = value; 此時存在A, B, C和B', A--->B--->C, B'--->C, 這里借用了賦值操作的原子性
- 修改指針, 得到: A--->B'--->C, B--->C
- 待所有對于B的讀操作完成后, free(B), 此時變?yōu)锳--->B'--->C
由此可見寫操作的損耗是比較大的, 涉及到內(nèi)存分配, 內(nèi)存拷貝等操作
Q3: RCU是如何執(zhí)行讀操作的
A: 仍然以前面的鏈表為例:
- 在步驟4之前發(fā)生的讀操作, 獲取到的是B, 在讀操作期間, B不會被釋放, 讀操作可以正常完成
- 在步驟4之后發(fā)生的讀操作, 獲取到的是新的B', 同樣可以正常完成操作
- 只有在步驟4之前發(fā)生的讀操作完成后, B才會被釋放, 此時是安全的
由此可見讀操作完全可以并發(fā), 原則上是不需要加鎖的, RCU唯一要判斷的是"步驟4之前發(fā)生的讀操作完成"這一條件
Q4: 那么, 如何判斷讀操作已完成?
A: 內(nèi)核提供了兩個rcu api: rcu_read_lock和rcu_read_unlock, 兩者之間的內(nèi)容就是對于rcu保護對象的讀操作
前面鏈表例子的步驟5會釋放結(jié)構(gòu)體B, 如果此時對于B還有引用, 后續(xù)會導致異常, 因此這一步操作必須確認讀操作已經(jīng)調(diào)用rcu_read_unlock.
從代碼可以看出rcu_read_lock是關閉內(nèi)核搶占, 而rcu_read_unlock是打開內(nèi)核搶占, 因此RCU確保了讀操作期間內(nèi)核是禁用搶占的(對于當前這個CPU核), 那么寫操作在釋放原結(jié)構(gòu)體之前, 可以嘗試去搶占每個核, 如果每個核都能搶占到, 說明每個核的內(nèi)核搶占都打開著, 也說明所有的核都沒有正在讀的操作.
當然在輪詢每個核的時候, 已經(jīng)輪詢過的核, 有可能有新的讀操作又進來, 這是沒有關系的, 從前面鏈表操作可以看出, 步驟4已經(jīng)修改了鏈表, B'已經(jīng)占據(jù)了B的位置, 新的讀操作不會訪問到B
RCU提出的是一種機制, 輪詢只是一種實現(xiàn)方式, Linux內(nèi)核提供的相應接口為synchronize_rcu, 這個api會阻塞寫操作, 直到完成前面的檢測. 如果寫操作不允許阻塞, 如果不想阻塞, 可以調(diào)用call_rcu接口, 這種情況不會阻塞, 但是會注冊一個回調(diào)函數(shù), 當判斷讀操作全部完成時, 會調(diào)用回調(diào)函數(shù), 完成釋放指針之類的操作.
多核之間RCU讀寫流程如下:
| CPU 0 | CPU 1 | CPU 2 |
|---|---|---|
| rcu_read_lock() | ||
| enters synchronize_rcu() | ||
| rcu_read_lock() | ||
| rcu_read_unlock() | ||
| exits synchronize_rcu() | ||
| rcu_read_lock() |
Q5: 并發(fā)寫操作是否要加鎖?
A: 從內(nèi)核文檔看, 寫操作在修改原指針的時候是需要加鎖的, 用spinlock即可, 主要是為了防止多個CPU核在更新結(jié)構(gòu)體時造成的沖突, 同樣以鏈表為例, 如果不加鎖, 在A--->B修改為A--->B'之前, 多個寫操作可能都得到的是B對象, 同時可能導致修改不一致的沖突出現(xiàn). 所以內(nèi)核里推薦的讀寫操作如下:
struct el {
struct list_head list;
long key;
spinlock_t mutex;
int data;
/* Other data fields */
};
spinlock_t listmutex;
struct el head;
int search(long key, int *result)
{
struct list_head *lp;
struct el *p;
rcu_read_lock();
list_for_each_entry_rcu(p, head, lp) {
if (p->key == key) {
*result = p->data;
rcu_read_unlock();
return 1;
}
}
rcu_read_unlock();
return 0;
}
int delete(long key)
{
struct el *p;
spin_lock(&listmutex);
list_for_each_entry(p, head, lp) {
if (p->key == key) {
list_del_rcu(&p->list);
spin_unlock(&listmutex);
synchronize_rcu();
kfree(p);
return 1;
}
}
spin_unlock(&listmutex);
return 0;
}
Q5: 還有什么其他API?
A: RCU還提供另外兩個基本的API: rcu_assign_pointer和rcu_dereference.
rcu_assign_pointer完成的是鏈表操作4中修改指針的操作, 將A--->B--->C改為A--->B'--->C:
rcu_assign_pointer(A->next, typeof(B') B');
rcu_dereference在讀操作獲取指針地址時使用:
p = rcu_dereference(A->next);
return p->data;
對于一般的CPU如x86, arm, 這些操作實際上就是簡單的賦值
Q6: RCU有什么好處? 在哪用到?
A: 提供并發(fā)讀操作, 加鎖開銷可以忽略不計(實際上, 并沒有真正的讀加鎖過程), 但是寫操作開銷比較大, 因此特別適合讀多寫很少的場景. 最近在讀openvswitch的代碼, 流表操作大量用到RCU的功能.
Q7: 更詳細的文檔?
A: 內(nèi)核文檔/Documentation/RCU/whatisRCU.txt里就有詳細的說明, Is Parallel Programming Hard一書中同樣用大篇幅介紹了RCU
