RCU (Read-Copy Update)
Table of Contents
1. RCU 简介
RCU (Read-Copy Update) 是一种数据同步的方式，可以作为“读写锁”的替代方案。RCU 顾名思义就是“读-拷贝修改”：对于被 RCU 保护的共享数据结构，读者不需要获得锁就可以访问它，但写者在访问它时首先拷贝一个副本，然后 对副本进行修改（即所谓的“Copy Update”）， 最后在适当的时机把指向原来数据的指针重新指向新的被修改的数据。
RCU 的读性能比“读写锁”要好，它适应满足两个条件（1、读多写少；2、对数据没有强一致性要求）的场景。 在 Linux 内核中 RCU 使用广泛。
RCU 主要针对的数据对象是链表，下面讨论都以 RCU 保护链表为例。
2. 宽限期
RCU 中有一个“宽限期（Grace Period）”的概念，它的意义是， 在一个删除动作发生后，它必须等待所有在宽限期开始前已经开始的读线程结束，才可以进行真正的销毁操作。 这样做的原因是这些线程有可能读到了要删除的元素。
Figure 1: RCU 宽限期
图 1（摘自：https://lwn.net/Articles/262464/ ）中，必须等待在宽限期开始前已经开始的读线程（即图中的读者 1/2/3）结束后，宽限期才结束，才可以回收已经删除的节点。
2.1. 插入、删除实例
图 2（摘自： https://lwn.net/Articles/610972/ ）展示了在链表中加入节点的过程。加入一个新节点 New 到 A 之前，所要做的第一步是将 New 的指针指向首个数据节点，第二步才是将 Head 的指针指向 New。这样做的目的是当插入操作完成第一步的时候，对于链表的读取并不产生影响，而执行完第二步的时候，读线程如果读到 New 节点，也可以继续遍历链表。如果把这个过程反过来，第一步 Head 指向 New，而这时一个线程读到 New，由于 New 的指针指向的是 NULL，这样将导致读线程无法读取到后续节点了。从以上过程中，可以看出 RCU 并不保证读线程一定可以读取到 New 节点。
Figure 2: RCU 增加链表节点
图 3（摘自： https://lwn.net/Articles/610972/ ）展示了在链表中删除节点的过程。和插入节点类似，链表指针操作也有严格的顺序。宽限期过后，删除 Old 节点并不对系统造成影响。
Figure 3: RCU 删除链表节点
删除场景，使用者也有可能看到旧状态，也就是 RCU 不保证“强一致性”。RCU 保证的是，旧状态的数据结构（内存）在合适的时候被释放，也不会导致使用者访问无效内存。
3. 取代读写锁
RCU 常常用于取代读写锁，下面展示了读取锁和 RCU 的使用区别：
/* reader-writer locking */ /* RCU */
1 struct el { 1 struct el {
2 struct list_head lp; 2 struct list_head lp;
3 long key; 3 long key;
4 spinlock_t mutex; 4 spinlock_t mutex;
5 int data; 5 int data;
6 /* Other data fields */ 6 /* Other data fields */
7 }; 7 };
*8 DEFINE_RWLOCK(listmutex); 8 DEFINE_SPINLOCK(listmutex);
9 LIST_HEAD(head); 9 LIST_HEAD(head);
1 int search(long key, int *result) 1 int search(long key, int *result)
2 { 2 {
3 struct el *p; 3 struct el *p;
4 4
*5 read_lock(&listmutex); 5 rcu_read_lock();
*6 list_for_each_entry(p, &head, lp) { 6 list_for_each_entry_rcu(p, &head, lp) {
7 if (p->key == key) { 7 if (p->key == key) {
8 *result = p->data; 8 *result = p->data;
*9 read_unlock(&listmutex); 9 rcu_read_unlock();
10 return 1; 10 return 1;
11 } 11 }
12 } 12 }
*13 read_unlock(&listmutex); 13 rcu_read_unlock();
14 return 0; 14 return 0;
15 } 15 }
1 int delete(long key) 1 int delete(long key)
2 { 2 {
3 struct el *p; 3 struct el *p;
4 4
*5 write_lock(&listmutex); 5 spin_lock(&listmutex);
6 list_for_each_entry(p, &head, lp) { 6 list_for_each_entry(p, &head, lp) {
7 if (p->key == key) { 7 if (p->key == key) {
*8 list_del(&p->lp); 8 list_del_rcu(&p->lp);
*9 write_unlock(&listmutex); 9 spin_unlock(&listmutex);
* 10 synchronize_rcu();
10 kfree(p); 11 kfree(p);
11 return 1; 12 return 1;
12 } 13 }
13 } 14 }
*14 write_unlock(&listmutex); 15 spin_unlock(&listmutex);
15 return 0; 16 return 0;
16 } 17 }
上面代码摘自：https://en.wikipedia.org/wiki/Read-copy-update#Analogy_with_reader%E2%80%93writer_locking
4. 参考
What is RCU, Fundamentally? https://lwn.net/Articles/262464/
Using RCU for linked lists — a case study: https://lwn.net/Articles/610972/
Introduction to RCU: http://www2.rdrop.com/users/paulmck/RCU/