什么是RCU

作者：

Paul E. McKenney, IBM Linux Technology Center ，

Jonathan Walpole, Portland State University Department of Computer Science

RCU ： read-copy-update (RCU) is a synchronization mechanism based on mutual exclusion.

对于RCU机制保护下的数据，读数据不需要获得任何锁或者很小代价的开销就可以访问，对于写者需要先拷贝一份副本，然后修改，最后使用一个回调（callback）机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。这个时机就是所有引用该数据的CPU都退出对共享数据的操作。

本文主要介绍RCU同步机制的三个部分：

针对插入操作的发布订阅机制；
针对删除操作的等待预先启动读者完成机制；
维护最新更新对象多个版本；

文章中以链表为例介绍了RCU处理过程：

删除情况下保持多版本：

  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   list_del_rcu(&p->list);
 14   synchronize_rcu();
 15   kfree(p);
 16 }

找到要删除的节点

Initial list
state.

调用list_del_rcu，但是此时还为真正删除节点

After
deletion.

通过synchronize_rcu等待所有reader 走完grace period.

After deletion.

通过kfree删除节点

After deletion.

更新情况下保持多版本：

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);

申请一个要替换的元素

List state after
allocation.