在我看来，RCU[1]不是具体的某个算法，接口或者是实现。RCU更像是一种思想，于2002年被引入linux内核。Paul E. McKenney是RCU的开发者和补道者，其一生都在大力推广RCU在Linux内核中的使用。据McKenney在2018年发表的回顾论文RCU Usage In the Linux Kernel: One Decade Later [2] 中提到的，直到2016年，使用RCU api的代码数量已经超过10000行，而且在linux内核代码中，有多个针对不同场景的RCU版本被实现。毋庸置疑，RCU已经是linux内核中保证高性能的重要基石了，尤其在当前cpu朝着多核化发展的趋势下。从某种程度上说，2002被引入linux内核的RCU可能更加适合现在的cpu架构，McKenney成功地预言了这一切～
    官方定义上来说，RCU是一种 synchronization mechanism，而且其目标是可拓展，和高性能。从基础的思想上，RCU把更新阶段拆分为removal 和 reclamation ，在removal阶段，会原子的将修改指向某块数据的指针或引用，相当于把数据给remove掉。这个动作必需是原子的，因为要确保读取该指针或者引用的请求只能看到remove前或者后的结果。(动作是原子的不代表动作使用了原子操作，仅仅只是对于外部观察者来说，不能看到更新前后两种状态外的第三态)。在reclamation阶段，则是会释放掉removal阶段remove掉的数据。对于这两个阶段，习惯了java python这类自带gc的语言的朋友可能不太好理解，为啥不在remove数据掉之后直接释放数据呢？原因有两个：1)从安全性考虑，remove后的数据，很有可能正在被另外的执行上下文访问，因此不能直接释放。对于带gc的语言来说，reclamation是后台垃圾回收线程做的。2)从性能考虑，频繁的内存释放会引入不必要的开销，可以延迟批量释放。

    如果不使用RCU，要想保证安全性，reclamation阶段也必需要和并发读取互斥，常规的实现就是使用读写锁，在removal阶段开始前，持有写锁，在reclamation阶段结束后，释放写锁。读取操作需要持有读锁。更新操作和读取操作之间是完成串行化的。如下面例子所示：

    1. // update task
    2. void update()
    3. {
    4.   write_lock();
    5.   removal();
    6.   reclamation();
    7.   write_unlock();
    8. }
    9. // read task
    10. void read()
    11. {
    12.   read_lock();
    13.   read_data();
    14.   read_unlock();
    15. }
    16. /**
    17. read()操作和update()操作之间是串行化的：
    18. CPU A     |       CPU B
    19. read()
    20. read()
    21.                   update()
    22. read()
    23.                   update()
    24. read()
    26. **/

    RCU的优化思路本质上就是将reclamation阶段从和并发读取冲突的临界区中拆开，减小这部分的临界区大小，从而提升整体的并发度。RCU中更新和读取并发的示意图如下：

    1. /**
    2. read()操作和removal()操作之间是串行化的，因为update = removal + reclamation，
    3. 所以和上图相比，RCU的并发度更好。
    4. CPU A     |       CPU B
    5. read()
    6. read()
    7.                   removal()
    8. read()
    9.                   removal()
    10. read()
    11. read()            reclamation()
    12. **/

    RCU策略中有一个最关键的地方是，要找到一个时间点（姑且叫做reclamation point），满足两个特征：1）这个时间点在removal之后，2）确保当前所有的执行上下文都不再持有旧数据的引用。在这个时间点之后的任意时刻都可以对旧数据执行reclamation。

    在linux内核代码中，核心的接口有5个：

    1. // 标记进入RCU读取临界区，在这个临界区中能够获取到的数据引用均是未被reclamation的
    2. rcu_read_lock();
    3. // 标记离开RCU读取临界区
    4. rcu_read_unlock()
    5. // call_rcu是synchronize_rcu的异步接口，它们两算作一个接口
    6. // synchronize_rcu调用会阻塞，直到reclamation point
    7. synchronize_rcu() / call_rcu()
    8. // 下面两个用于操作和读取rcu保护的指针，本质上是为了保证removal的可见性和原子性
    9. // 只能在RCU读取临界区内被调用
    10. rcu_assign_pointer()
    11. rcu_dereference()

    并不打算一开始就讲解linux中的实现，而是先从最简单的实现入手。
    rcu_dereference 和 rcu_assign_pointer操作，是为了保证读取和修改rcu数据引用的原子性和可见性，并不受具体rcu实现细节的影响，其实现和具体的处理器架构有关，简单来说就是通过阻止编译器和cpu的reorder来实现。由于并不是本文的重点，因此后续并不会再做详细介绍。

    前文提到，synchronize_rcu返回成功的前提是要保证当前所有的执行上下文都不再持有旧数据的引用。而执行上下文只有在rcu_read_lock/rcu_read_unlock的临界区内才能持有数据的引用，因此通过读写锁来保证rcu_read_lock和synchronize_rcu的互斥即可实现最简单的RCU:

    1. void rcu_read_lock()
    2. {
    3.   read_lock();
    4. }
    5. void rcu_read_unlock()
    6. {
    7.   read_unlock();
    8. }
    9. void synchronize_rcu()
    10. {
    11.   write_lock();
    12.   write_unlock();
    13. }

    但是由于读写锁本身实现的原因，会给rcu_read_lock/rcu_read_unlock的调用引入开销，因为上读锁本身就是一个原子操作，而原子操作在多核场景下对cache line并不友好。实现为percpu或者perthread的读写锁可以减轻这类开销，但是会导致空间浪费。其实在linux内部，通过控制任务调度的方式，其实是有更好的降低开销的方式的。

    为了降低rcu_read_lock/rcu_read_unlock调用的开销，可以通过暂时阻止任务抢占的方式，来实现RCU，如下所示：

    1. void rcu_read_lock()
    2. {
    3.   preempt_disable();//阻止任务抢占
    4. }
    5. void rcu_read_unlock()
    6. {
    7.   preempt_enable();
    8. }
    9. void synchronize_rcu()
    10. {
    11.   // 调度该任务在每个cpu上轮流执行
    12.   for_each_cpu(cpu)
    13.       run_on(cpu);
    14. }

    在rcu_read_lock/rcu_readunlock执行的临界区内，由于无法抢占，因此cpu不能执行其他任务，当run_on任务在该cpu执行后，说明该cpu已经退出临界区了，后续再次进入临界区也无法看到旧数据的引用了。因此synchronize_rcu在每个cpu都调度执行run_on后，即可保证旧数据不会再被访问。相比于实现一，能够降低rcu_read_lock/rcu_readunlock的调用开销。不过由于rcu_read_lock/rcu_readunlock暂停了任务抢占，因此不能在临界区内执行阻塞调用或者sleep等，否则会导致cpu资源的浪费。

    看过上述两类实现后，linux内核内的实现也不再神秘，如下所示，仍然是非抢占式的：

    1. static inline void __rcu_read_lock(void)
    2. {
    3.     preempt_disable();
    4. }
    5. static inline void __rcu_read_unlock(void)
    6. {
    7.     preempt_enable();
    8. }

    synchronize_rcu() / call_rcu()实现的代码比较复杂，具体流程就是上下文切换触发软中断，调用rcu_sched_clock_irq()

    1. void rcu_sched_clock_irq(int user)
    2. {
    3.     ...
    4.     if (rcu_pending(user))
    5.         invoke_rcu_core();  // 通过软中断，或者直接唤醒rcu任务处理线程
    6.     ...
    7. }
    8. // rcu任务处理函数
    9. static void rcu_core(void)
    10. {
    11.         ...
    12.         // 标记当前cpu的rcu状态
    13.     rcu_check_quiescent_state(rdp);
    14.         ...
    15. }

    synchronize_rcu会通过call_rcu注册等待任务，当每个cpu上rcu任务被处理后，就会等待成功，这个时候synchronize_rcu调用返回，可以安全的回收旧数据了。

    [1] http://www2.rdrop.com/users/paulmck/RCU/
    [2] https://pdos.csail.mit.edu/6.828/2018/readings/rcu-decade-later.pdf