1. RCU概述
看HotRing时，其涉及到RCU，借此稍微补补课。
Read-Copy Update是一种并发控制机制，其意思非常简单：
- 读：直接访问，无需获取锁
- 写：先拷贝出新副本并执行写入，等待读取结束后，覆盖旧副本
易得知：
- 当有多个读和一个写时，不需上任何锁
- 当有多个写时，需要额外的同步机制
所以RCU的并发控制适用于“读多写少”的情景。
RCU的一个典型应用场景是链表，Linux有专门的RCU链表实现，于头文件rculist.h中定义。
2. rculist: Insert
Linux的rculist的插入代码如下：
#define list_next_rcu(list) (*((struct list_head __rcu **)(&(list)->next)))
static inline void __list_add_rcu(struct list_head *new,
struct list_head *prev, struct list_head *next)
{
// 本节点连接前后节点
new->next = next;
new->prev = prev;
// 前后节点连接本节点
rcu_assign_pointer(list_next_rcu(prev), new);
next->prev = new;
}
注意函数rcu_assign_pointer，它涉及一个宏，代码如下：
#define __rcu_assign_pointer(p, v, space) \
({ \
smp_wmb(); \
(p) = (typeof(*v) __force space *)(v); \
})
注意smp_wmb，该宏添加了一个写内存屏障，保证前一条写指令不会先于后一条写指令执行。在本节的场景中，该屏障可以保证“本节点连接前后节点”先于“前后节点连接本节点”，从而保证“新节点的初始化（包含新节点的前后指针）”一定在“连接前后节点”之前完成。
而当有多个读进程时，当prev->next没设置时，读到的是旧链表；当prev->next设置后，读到的就是新链表。不论怎样，读进程不会访问到非法地址。
3. rculist: Read
读取基本的模式如下所示，基本就是：
- 上RCU读锁
- 获取RCU保护的指针，进行读取
- 解RCU读锁
rcu_read_lock(); // read lock
// ... READ SECTION BEGIN ...
void *list = rcu_dereference(*p); // dereference the item ptr
// ... READ SECTION END ...
rcu_read_unlock(); // read unlock
这里注意rcu_dereference宏，代码如下所示，其效果就是把一个指针赋给另一个指针：
#define rcu_dereference(p) rcu_dereference_check(p, 0)
#define rcu_dereference_check(p, c) \
__rcu_dereference_check((p), rcu_read_lock_held() || (c), __rcu)
#define __rcu_dereference_check(p, c, space) \
({ \
typeof(*p) *_________p1 = (typeof(*p)*__force )ACCESS_ONCE(p); \
rcu_lockdep_assert(c, "suspicious rcu_dereference_check()" \
" usage"); \
rcu_dereference_sparse(p, space); \
smp_read_barrier_depends(); \
((typeof(*p) __force __kernel *)(_________p1)); \
})
其中关键的就是smp_read_barrier_depends，也是一个内存屏障（读屏障），保证p1一定先从p读取，之后再返回给外部赋值（也是读取）。这个内存屏障在很多架构里是空实现（如x86, ARM）。
从上面看到，读需要上读锁，这是为了保证写操作的安全——因为执行RCU写时，新副本替换旧副本后，需要保证没有进程读旧副本后，才能释放旧副本的内存。这就涉及到：Grace period和synchronize_rcu API。
4. Grace Period与synchronize_rcu
当有多个读和一个写时，写进程设置好新副本后，何时释放旧副本内存？答案是：所有读进程退出旧副本的访问。
Linux内核使用synchronize_rcu开启Grace Period，它会等待所有旧副本访问结束后返回，返回后Grace Period结束。
如上图所示，易知：
t2~t3是Grace period：t2调用synchronize_rcu，t3从synchronize_rcu返回t2前读到的是旧副本，t2后读到的是新副本- Grace period/
synchronize_rcu结束条件：所有横跨t2的读进程结束
5. rculist：Delete
有了第4节的铺垫，链表删除的逻辑就很简单了，大致如下：
void delete() {
p = seach_the_entry_to_delete();
list_del_rcu(p->list); // 移除链表项
synchronize_rcu(); // 开始Grace period, 等待读退出
kfree(p); // Grace period结束,安全,释放内存
}
/* list.h */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
/* rculist.h */
static inline void list_del_rcu(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->prev = LIST_POISON2;
}
这里第4行代码保证了所有的旧表项的读结束后，旧表项才会被释放。
6. rculist：Update
更新操作如RCU所述，需要拷贝一个新副本，更改完成后替换旧副本，然后释放旧副本内存。
根据第4节，其代码也是很简单的：
void update() {
p = search_the_entry_to_update();
q = kmalloc(sizeof(*p), GFP_KERNEL); // 拷贝
*q = *p;
q->field = new_value; // 更改字段
list_replace_rcu(&p->list, &q->list); // 替换旧副本
synchronize_rcu(); // 开始Grace period, 等待读退出
kfree(p); // Grace period结束,安全,释放内存
}
static inline void list_replace_rcu(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->prev = old->prev;
rcu_assign_pointer(list_next_rcu(new->prev), new); // 内存屏障，保证更改在连接之前完成
new->next->prev = new;
old->prev = LIST_POISON2;
}
这里，第16行代码的写内存屏障保证了“新链表项的更改（包含前后指针）”在“连接前后节点之前”完成；而第7行保证了所有的旧表项的读结束后，旧表项才会被释放。
