RCU 初步認識

從 Paul McKenney 的[網站] 有 [RCU 的基本介紹] 一文，趁著爬文後還有印象，趕快整理一下重點與常見問題：
1. RCU 的需求：
  RCU (Read Copy Update) 是一種 synchronization 機制，允許多個 reads to occur concurrently with updates，它本身不使用 lock 機制，在 kernel 內，適合用在 reader 多但 writer 少的資料保護。因為現在的系統多半都有多個 CPUs，RCU 機制允許多個 readers 的 scability 特性(無限個 readers，而且進入 reader-side critical section 是非常的 low cost)，使得它在這些情形下，比用 lock 有更好的 performance。

2. RCU 的工作方式及術語：(資料來源 : [RCU Wiki] )
  RCU 把 update 分成兩個 phase: "removal" and "reclamation".
  Removal phase 移除某個 data 指標，此時允許多個 readers 繼續進行，readers 可能看到兩種版本的資料(移除該 data 前跟移除後) 因為是更改指標，所以只要確保更改指標的動作是 atomic operation ，就不會破壞到資料。
  Reclamation phase 時，只要確保沒有 reader 會再參考該 data 之後，就可以安全的移除該資料---這涉及兩個條件：一、 所有 reader 讀取資料的動作是 link list 的單一方向的拜訪，不回頭。二、 所有的 reader 執行 "reader-side critical section" 內的動作時不能 block 或 preempt，這樣我們的 reclamation phase 可以簡單的設計成：

void synchronize_rcu(void) {
   int cpu;
   for_each_cpu(cpu);
   run_on(cpu);
}


只要令每個 CPU 都輪流完，就可確保下列情形：所有在 synchronize_rcu() 的執行時間之前，所有參考到舊版本(未移除時)的 readers 都保證結束，在這個時間點後，所有的 readers 都將只看到新版本(已移除該 data) 的資料串列了！這段等待所有 CPU 跑完的時間稱作 "Grace Period"，在歷經 grace period 後，我們就可以確定該 data 已經沒有任何的 reader 參考了，可以放心的 free 掉。(即 reclamation).

剛才所討論的是 delete 的 RCU 動作， add/replace 的 RCU 動作原理也是依此類推。
 
3 一些 RCU 的 API :

假設我們有一片段程式，updater 動作如下:
例一：
  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;

 這裡不能保證 11-14 行不會被 compiler reorder，所以我們改為：

  1 p->a = 1;
  2 p->b = 2;
  3 p->c = 3;
  4 rcu_assign_pointer(gp, p); 裡面加了 memory barrier 保證 pointer assign 發生於 line 1-3 之後.

同樣的，在 reader 一方，reader 也需要 memory barrier:
例二：
  1 p = gp;
  2 if (p != NULL) {
  3   do_something_with(p->a, p->b, p->c);
  4 }
在大部分的 arch 下是正確的，但是在 DEC Alpha 還是會有可能 p->a, p->b, p->c 發生得比 fetch p 來得早，
所以應該改成：
例三：
  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();


這裡 rcu_dereference()裡面有memory barrier，保證 p->a,p->b,p->c僅發生在 p 被 fetch 之後。
另外 rcu_read_lock() rcu_read_unlock() 也是必要的，它們標明了 reader-side critical section，在 preempt kernel 中，
他們的動作就是暫時 disable preempt(前面的條件二)，在 non-preempt kernel 中，就沒事做，展開成空的 macro.

先跳來看一下 rcu_dereference()
#define rcu_dereference(p)     ({ \
                typeof(p) _________p1 = ACCESS_ONCE(p); \
                smp_read_barrier_depends(); \
                (_________p1); \
                })
其中 ACCESS_ONCE 確保 p 不被最佳化動作影響，可以確實讀取，smp_read_barrier_depends() 意思為 "flush all pending reads that subsequents reads depend on"（使 barrier 之後的 reads 動作不受 barrier 之前的 reads 所影響).

ok 言歸正傳，既然 pointer 有包裝了 memory barrier。因為 rcu 常用於 list operation，所以 list 動作中，也有 rcu 版本的 API:

list_add_rcu()
list_del_rcu()
list_replace_rcu()

這些 macro 中也包裝了 memory barrier。

把各種 API 做個表格來看就清楚了：
===============================================================================================================
Category          Publish                    Retract                                Subscribe

Pointers          rcu_assign_pointer()       rcu_assign_pointer(...,NULL)            rcu_dereference()

Lists              list_add_rcu()             list_del_rcu()                         list_for_each_entry_rcu()
                   list_add_tail_rcu()
                   list_replace_rcu()
===============================================================================================================
接下來看看 list 的 example，這是 updater 的程式片段:
例四：
 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);
其中第 16 行就是 read-copy，第 17-19 行就是 update 動作。

list_replace_rcu() 如下：

static inline void list_replace_rcu(struct list_head *old,
                struct list_head *new)
{
    new->next = old->next;
    new->prev = old->prev;
    smp_wmb();
    new->next->prev = new;
    new->prev->next = new;
    old->prev = LIST_POISON2;
}
看得出來，是 list 代換加上內嵌一個 memory barrier.


好的，來看看 reader 的動作：

例五：
list_for_each_rcu(p, list_head) {
  rcu_read_lock();
  if (need_to_reference(p)) {
    reference_without_blocking(p);
    rcu_read_unlock();
    break;
  }
  rcu_read_unlock();
}

rcu_read_lock()/rcu_read_unlock() pair 是標明 reader critical section(CS)。在 CS 裡面，如果要參考某個 link data，有個條件剛剛提過---就是 reader 不能 blocking !!

總結： RCU algorithm 的動作大抵有三個部份：
1. publish-subscribe 機制，用來給 reader 參考的，如例三與例五。
2. 於 updater 端則是：waiting for pre-existing RCU readers to finish，如例四的 synchronize_rcu()，and
3. maintain multiple versions to permit change w/o harming concurrent RCU readers 就是前面說的兩個條件！


問題 1： seqlock 也是 synchronize 機制，與 RCU 比較有何不同？
Ans: seqlock 當遇到 updater update 資料時，會強迫 readers retry reading，但是 RCU 則不會。

問題 2： 當 reader 執行 list_for_each_entry_rcu() 的同時，若是(假設另一個 CPU上) updater 也正在執行 list_add_rcu()
( 或是 list_del_rcu(), list_replace_rcu() 等) 更改資料，這樣不會有問題嗎？
Ans: 因為在 Linux 系統上，load/store pointer 是 atomic operation，所以 list_for_each_entry_rcu() 參考到的資料，
可能會是原始版本的資料，或是新版本的資料，這兩種其中之一；而不會是資料 inconsistent 的情形。並且，
list_for_each_entry_rcu() 是一路前進的參考，不會回頭，所以看到的可能是新資料 or 舊資料。
之後 updater 會讓所有參考到舊資料的 readers 保證可以結束 read critical section，然後才把該筆舊資料移除 或置換掉，其餘的 reader 都將讀到新資料，所以不會有問題。

這裡有個跟以前觀念上不同之處，我們以前的 CS 是保證唯一占用被保護的資源。
但是 RCU  Reader 進入 CS 之後，並不保證他是讀到新或舊資料。讀到新舊資料的分野，是在於 updater 執行 synchronize_rcu() 的時間點，對所有的 readers，在該時間之前，所有的讀取都讀到舊資料！在該時間之後，所有的讀取都將讀到新資料！

Technorati 標籤: RCU, kernel code, synchronization