11-读-拷贝-更新
7.4.4 读-拷贝-更新
RCU（Read-Copy Update，读-拷贝-更新），它是基于其原理命名的。RCU并不是新的锁机制，它只是对Linux内核而言是新的。早在20世纪80年代就有了这种机制，而在Linux中是在开发内核2.5.43中引入该技术的并正式包含在2.6内核中。
对于被RCU保护的共享数据结构，读执行单元不需要获得任何锁就可以访问它，不使用原子指令，而且在除alpha的所有架构上也不需要内存屏障（Memory Barrier），因此不会导致锁竞争、内存延迟以及流水线停滞。不需要锁也使得使用更容易，因为死锁问题就不需要考虑了。使用RCU的写执行单元在访问它前需首先拷贝一个副本，然后对副本进行修改，最后使用一个回调机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据，这个时机就是所有引用该数据的CPU都退出对共享数据的操作的时候。读执行单元没有任何同步开销，而写执行单元的同步开销则取决于使用的写执行单元间同步机制。
RCU可以看作读写锁的高性能版本，相比读写锁，RCU的优点在于既允许多个读执行单元同时访问被保护的数据，又允许多个读执行单元和多个写执行单元同时访问被保护的数据。但是，RCU不能替代读写锁，因为如果写比较多时，对读执行单元的性能提高不能弥补写执行单元导致的损失。因为使用RCU时，写执行单元之间的同步开销会比较大，它需要延迟数据结构的释放，复制被修改的数据结构，它也必须使用某种锁机制同步并行的其他写执行单元的修改操作。
Linux中提供的RCU操作包括如下4种。
1．读锁定
rcu_read_lock()
rcu_read_lock_bh()
2．读解锁
rcu_read_unlock()
rcu_read_unlock_bh()
使用RCU进行读的模式如下：
rcu_read_lock()
.../ 读临界区/
rcu_read_unlock()
其中rcu_read_lock()和rcu_read_unlock()实质只是禁止和使能内核的抢占调度：
define rcu_read_lock() preempt_disable()
define rcu_read_unlock() preempt_enable()
其变种rcu_read_lock_bh()、rcu_read_unlock_bh()则定义为：
define rcu_read_lock_bh() local_bh_disable()
define rcu_read_unlock_bh() local_bh_enable()
3．同步RCU
synchronize_rcu()
该函数由RCU写执行单元调用，它将阻塞写执行单元，直到所有的读执行单元已经完成读执行单元临界区，写执行单元才可以继续下一步操作。如果有多个RCU写执行单元调用该函数，它们将在一个grace period（即所有的读执行单元已经完成对临界区的访问）之后全部被唤醒。synchronize_rcu()保证所有CPU都处理完正在运行的读执行单元临界区。
synchronize_kernel()
内核代码使用该函数来等待所有CPU处于可抢占状态，目前功能等同于synchronize_rcu()，但现在已经不建议使用，而是使用synchronize_sched()，该函数用于等待所有CPU都处在可抢占状态，它能保证正在运行的中断处理函数处理完毕，但不能保证正在运行的软中断处理完毕。
● 挂接回调
void call_rcu(struct rcu_head *head,
void (func)(struct rcu_head rcu));
函数call_rcu()也由RCU写执行单元调用，它不会使写执行单元阻塞，因而可以在中断上下文或软中断使用。该函数将把函数func挂接到RCU回调函数链上，然后立即返回。函数synchronize_rcu()的实现实际上使用了call_rcu()函数。
void call_rcu_bh(struct rcu_head *head,
void (func)(struct rcu_head rcu));
call_rcu_bh()函数的功能几乎与call_rcu()完全相同，惟一差别就是它把软中断的完成也当作经历一个quiescent state（静默状态），因此如果写执行单元使用了该函数，在进程上下文的读执行单元必须使用rcu_read_lock_bh()。
每个CPU维护两个数据结构rcu_data和rcu_bh_data，它们用于保存回调函数，函数call_rcu()把回调函数注册到rcu_data，而call_rcu_bh()则把回调函数注册到rcu_bh_data，在每一个数据结构上，回调函数被组成一个链表，先注册的排在前头，后注册的排在末尾。
使用RCU时，读执行单元必须提供一个信号给写执行单元以便写执行单元能够确定数据可以被安全地释放或修改的时机。有一个专门的垃圾收集器来探测读执行单元的信号，一旦所有的读执行单元都已经发送信号告知它们都不在使用被RCU保护的数据结构，垃圾收集器就调用回调函数完成最后的数据释放或修改操作。
RCU还增加了链表操作函数的RCU版本：
static inline void list_add_rcu(struct list_head new, struct list_head head);
该函数把链表元素new插入RCU保护的链表head的开头，内存栅保证了在引用这个新插入的链表元素之前，新链表元素的链接指针的修改对所有读执行单元是可见的。
static inline void list_add_tail_rcu(struct list_head *new,
struct list_head *head);
该函数类似于list_add_rcu()，它将把新的链表元素new添加到被RCU保护的链表的末尾。
static inline void list_del_rcu(struct list_head *entry);
该函数从RCU保护的链表中删除指定的链表元素entry。
static inline void list_replace_rcu(struct list_head old, struct list_head new);
该函数是RCU新添加的函数，并不存在非RCU版本。它使用新的链表元素new取代旧的链表元素old，内存栅保证在引用新的链表元素之前，它对链接指针的修正对所有读执行单元是可见的。
list_for_each_rcu(pos, head)
该宏用于遍历由RCU保护的链表head，只要在读执行单元临界区使用该函数，它就可以安全地和其他_rcu链表操作函数，如list_add_rcu()并发运行。
list_for_each_safe_rcu(pos, n, head)
该宏类似于list_for_each_rcu，但不同之处在于它允许安全地删除当前链表元素pos。
list_for_each_entry_rcu(pos, head, member)
该宏类似于list_for_each_rcu，不同之处在于它用于遍历指定类型的数据结构链表，当前链表元素pos为一包含struct list_head结构的特定的数据结构。
static inline void hlist_del_rcu(struct hlist_node *n)
它从由RCU保护的哈希链表中移走链表元素n。
static inline void hlist_add_head_rcu(struct hlist_node *n,
struct hlist_head *h);
该函数用于把链表元素n插入被RCU保护的哈希链表的开头，但同时允许读执行单元对该哈希链表的遍历。内存栅确保在引用新链表元素之前，它对指针的修改对所有读执行单元可见。
hlist_for_each_rcu(pos, head)
该宏用于遍历由RCU保护的哈希链表head，只要在读端临界区使用该函数，它就可以安全地和其他_rcu哈希链表操作函数（如hlist_add_rcu）并发运行。
hlist_for_each_entry_rcu(tpos, pos, head, member)
类似于hlist_for_each_rcu()，不同之处在于它用于遍历指定类型的数据结构哈希链表，当前链表元素pos为一包含struct list_head结构的特定的数据结构。
目前，RCU的使用在内核中已经非常普遍，内核中大量原先使用读写锁的代码被RCU替换，下面的表单左右两列平行地分别给出使用读写锁和RCU实现链表元素读、删除、添加和修改的代码：
/*
原先的audit_filter_task函数，读链表前获得
读写锁 */
static enum audit_state
audit_filter_task(struct task_struct
*tsk)
{
struct audit_entry *e;
enum audit_state state;
read_lock(&auditsc_lock);
/ 遍历链表 /
list_for_each_entry(e, &audit_tsklist,
list) {
if (audit_filter_rules(tsk, &e
->rule, NULL, &state)) {
read_unlock(&auditsc_lock);
return state;
/*
修改后的audit_filter_task函数，采用RCU
*/
static enum audit_state
audit_filter_task(struct task_struct
*tsk)
{
struct audit_entry *e;
enum audit_state state;
rcu_read_lock();
/ 遍历链表 /
list_for_each_entry_rcu(e,
&audit_tsklist, list) {
if (audit_filter_rules(tsk, &e
->rule, NULL, &state)) {
rcu_read_unlock();
return state;
}
}
read_unlock(&auditsc_lock);
return AUDIT_BUILD_CONTEXT;
}
}
}
rcu_read_unlock();
return AUDIT_BUILD_CONTEXT;
}
/* 原先的audit_del_rule，删除链表元素前获得
读写锁 */
static inline int audit_del_rule(struct
audit_rule *rule, struct
list_head*list)
{
struct audit_entry *e;
write_lock(&auditsc_lock);
/ 遍历链表 /
list_for_each_entry(e, list, list) {
if (!audit_compare_rule(rule, &e
->rule)) {
list_del(&e->list); /* 删除链表元素
write_unlock(&auditsc_lock);
return 0;
}
}
write_unlock(&auditsc_lock);
return - EFAULT;
}
/* 修改后的audit_del_rule，使用list_del_rcu
删除链表元素，并调用call_rcu注册回调函数 */
static inline int audit_del_rule(struct
audit_rule *rule, struct
list_head*list)
{
struct audit_entry *e;
/ 遍历链表 /
list_for_each_entry(e, list, list) {
if (!audit_compare_rule(rule, &e
->rule)) {
list_del_rcu(&e->list);
call_rcu(&e->rcu,audit_free_rule);
return 0;
}
}
return - EFAULT;
}
/* 原先的audit_add_rule，添加链表元素前获得
读写锁 */
static inline int audit_add_rule(struct
audit_entry *entry, struct
list_head*list)
{
write_lock(&auditsc_lock);
if (entry->rule.flags &AUDIT_PREPEND) {
entry->rule.flags &= ~AUDIT_PREPEND;
list_add(&entry->list, list);
} else {
list_add_tail(&entry->list, list);
}
write_unlock(&auditsc_lock);
return 0;
}
/* 修改后的audit_add_rule，在添加链表元素时
使用list_add_xxx函数 */
static inline int audit_add_rule(struct
audit_entry *entry, struct
list_head*list)
{
if (entry->rule.flags &AUDIT_PREPEND) {
entry->rule.flags &= ~AUDIT_PREPEND;
list_add_rcu(&entry->list, list);
} else {
list_add_tail_rcu(&entry->list,
list);
}
return 0;
}
/*原先的audit_upd_rule函数，在修改链表元素前
获得读写锁 */
static inline int audit_upd_rule(struct
audit_rule *rule, struct list_head
*list, u32 newaction, u32
newfield_count)
{
struct audit_entry *e;
struct audit_newentry *ne;
write_lock(&auditsc_lock);
/ 遍历链表 /
/* 修改后的audit_upd_rule，使用listreplace
rcu修改链表元素，并用call_rcu注册回调函数 */
static inline int audit_upd_rule(struct
audit_rule *rule, struct list_head
*list, u32 newaction, u32
newfield_count)
{
struct audit_entry *e;
struct audit_newentry *ne;
list_for_each_entry(e, list, list) {
if (!audit_compare_rule(rule, &e
->rule)) {
e->rule.action = newaction;
e->rule.file_count =
newfield_count;
write_unlock(&auditsc_lock);
return 0;
}
}
write_unlock(&auditsc_lock);
return - EFAULT;
}
/ 遍历链表 /
list_for_each_entry(e, list, list) {
if (!audit_compare_rule(rule, &e
->rule)) {
ne = kmalloc(sizeof(*entry),
GFP_ATOMIC);/ 分配新元素内存 /
if (ne == NULL)
return - ENOMEM;
audit_copy_rule(&ne->rule, &e
->rule);/ 写前拷贝/
ne->rule.action = newaction;
ne->rule.file_count =
newfield_count;
list_replace_rcu(e, ne);
call_rcu(&e->rcu,audit_free_rule);
return 0;
}
}
return - EFAULT;
}