基本原理

RCU - Read-Copy Update,適用于讀多寫(xiě)少(最好只有一個(gè)線程寫(xiě))。其背后思想非常簡(jiǎn)單

1. Read時(shí)直接Read, 唯一約束時(shí)暫時(shí)當(dāng)前線程不允許被搶占preempt，其overhead基本可以忽略不計(jì)。
2. Copy Update指的是update前先把要改的內(nèi)存copy一份到其他內(nèi)存上，然后對(duì)這段內(nèi)存進(jìn)行update
3. 在update結(jié)束后，將原來(lái)的指針指向新的指針(原子更新)
4. 最后記得回收掉以前不用的內(nèi)存

約束

1. RCU機(jī)制并不保護(hù)并發(fā)寫(xiě)，如果有并發(fā)寫(xiě)，還需要用其他鎖進(jìn)一步進(jìn)行保護(hù)。
2. 讀線程的操作被包在rcu_read_lock和rcu_read_unlock宏之間。在這之間不允許切換線程。schedule(),kmalloc(),copy_from_user()等操作都會(huì)引起切換線程，因此這段期間不允許用。

grace period

1. rcu_read_lock宏等同于preempt_disable()?？梢酝茢?code>rcu_read_lock和rcu_read_unlock組成的critical section中，線程不會(huì)被切換。反之，如果線程被切換，則說(shuō)明critical section已經(jīng)結(jié)束。
2. grace period開(kāi)始與寫(xiě)線程更新指針。
3. grace period結(jié)束于一個(gè)同步點(diǎn)。synchronize_rcu()等待所有舊的數(shù)據(jù)的寫(xiě)線程都退出了critical section。
4. grace period結(jié)束后，就可以回收對(duì)應(yīng)的內(nèi)存，因?yàn)橐呀?jīng)沒(méi)有人再用它了。
5. 除了synchronize_rcu(),call_rcu也能代表grace period的結(jié)束

圖例

image.png

1. 上圖中每個(gè)藍(lán)色的reader方塊代表了一個(gè)read side的critical section的長(zhǎng)度。
2. 黃色方塊代表updater的grace period。黃色左端邊緣表示grace period的開(kāi)始。所有和左邊緣有overlap的reader，都有可能還再用舊的內(nèi)存。
3. 因此grace period的右端結(jié)束時(shí)間，取決于上述的那些有overlap的writer的最后一個(gè)結(jié)束點(diǎn)。同步點(diǎn)也就是等最后一個(gè)有overlap的結(jié)束。

例子1

寫(xiě)操作1

11~14行運(yùn)行的時(shí)候可能會(huì)和代碼順序不一致。需要用barrier改寫(xiě)下。

  1 struct foo {
  2   int a;
  3   int b;
  4   int c;
  5 };
  6 struct foo *gp = NULL;
  7 
  8 /* . . . */
  9 
 10 p = kmalloc(sizeof(*p), GFP_KERNEL);
 11 p->a = 1;
 12 p->b = 2;
 13 p->c = 3;
 14 gp = p;

寫(xiě)操作2

將上述代碼改寫(xiě)下，rcu_assign_pointer內(nèi)部調(diào)用了barrier，保證了順序。rcu_assign_pointer語(yǔ)義等同一個(gè)publish,將舊指針換成了新指針。

  1 p->a = 1;
  2 p->b = 2;
  3 p->c = 3;
  4 rcu_assign_pointer(gp, p);

讀操作1

對(duì)于有些CPU，p->a的預(yù)讀會(huì)發(fā)生在第2行之前，也會(huì)亂序。

  1 p = gp;
  2 if (p != NULL) {
  3   do_something_with(p->a, p->b, p->c);
  4 }

讀操作2

將上述代碼做如下改寫(xiě)，rcu_dereference()起到了subscribe的語(yǔ)義。

  1 rcu_read_lock();
  2 p = rcu_dereference(gp);
  3 if (p != NULL) {
  4   do_something_with(p->a, p->b, p->c);
  5 }
  6 rcu_read_unlock();

例子2

寫(xiě)操作

  1 struct foo {
  2   struct list_head list;
  3   int a;
  4   int b;
  5   int c;
  6 };
  7 LIST_HEAD(head);
  8 
  9 /* . . . */
 10 
 11 p = search(head, key);
 12 if (p == NULL) {
 13   /* Take appropriate action, unlock, and return. */
 14 }
 15 q = kmalloc(sizeof(*p), GFP_KERNEL);
 16 *q = *p;
 17 q->b = 2;
 18 q->c = 3;
 19 list_replace_rcu(&p->list, &q->list);
 20 synchronize_rcu();
 21 kfree(p);

讀操作

  1 rcu_read_lock();
  2 list_for_each_entry_rcu(p, head, list) {
  3   do_something_with(p->a, p->b, p->c);
  4 }
  5 rcu_read_unlock();