⚠ 转载请注明出处：作者：ZobinHuang，更新日期：Nov.23 2021
本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。
目录
有特定需要的内容直接跳转到相关章节查看即可。
Section 1. RCU 基本介绍：介绍了 RCU 同步机制的 Motivation;
Section 2. RCU 工作流程：介绍了 RCU 中 Updater 和 Reader 的工作流程;
Section 3. RCU 原语: 列举了常见的 RCU 原语以及对它们的相应功能进行了阐述;
Section 4. RCU 原语使用实例: 分析了内核源码中常见的 RCU 原语的使用实例;
注明：
- 本文的分析基于内核版本 v5.14.18 展开;
1. RCU 基本介绍
Read-copy update (RCU) 是 Linux Kernel 的一种同步机制，与传统的读写锁和互斥锁不同，RCU 允许一个 Updater 和多个 Reader 的存在 (注意，多个 Updater 之间仍然是互斥的)。RCU 允许 Reader 在执行 Read-side Critical Section 的指令 (i.e. 临界区，访问了可能产生竞争的共享数据结构的代码段) 的时候不加锁就可以访问，这样一来就大大加速了 Reader 的代码执行流程，因为申请一个互斥/读写/自旋锁的 overhead 是很大的。由于对 读多写少 场景的优化，RCU 大量的应用在 Linux Network 源码中，如对路由表的访问等场景。
2. RCU 工作流程
我们现在简单分析一下 RCU 机制是如何保障在 Reader 不加锁的情况下对数据的安全并发访问的。首先，我们要先明确以下两点：
- RCU 只保护 被动态分配并通过指针引用的 数据结构;
- 在对被 RCU 保护的 Critical Section 进行操作时，任何 Reader 都不能被休眠;
首先我们先分析 Reader 的工作流程：我们假设指针 `p` 指向的数据区域是受 RCU 保护的，也即是 Read-side Critical Section。当 Reader 在读取被 RCU 保护的共享数据结构时，也即上图 ①，它会首先调用 rcu_read_lock()，这个 RCU 原语实际上是在执行 preempt_disable()，即暂时关闭内核调度器抢占，然后 Reader 引用指针 `p` 所对应的内存单元，并且开始读取共享数据结构。正如我们上面所述，在 Reader 完成对共享数据结构的读取之前，它是不能睡眠的。完成读取后，Reader 又会调用 rcu_read_unlock()，这个 RCU 原语实际上是在执行 preempt_enable()，即重新使能内核任务调度器的抢占。
对于 Updater 来说，当 Updater 要更新这个被 RCU 保护的共享数据结构时，它肯定不会直接基于指针 `p` 对原数据结构进行修改，因为如果有并行的同样是在操作原数据结构的 Reader 存在的话，Updater 的更新将导致 Reader 有不可预测的读取结果。因此，Updater 会首先生成一份原数据结构的副本，然后 Updater 开始更新这个副本，也即上图 ②。Updater 修改完毕后，会改变指针变量 `p` 的值，以使它指向由 Updater 更新过的数据结构副本，也即上图 ③ (p.s. 这个指针修改操作是一个原子操作，这保证了这个指针值不会出现数据错乱的情况发生，更改了指针值时一定能成功的)。
基于上述理解，我们以上图为例子来更加详细地分析 RCU Updater 和 Reader 的工作过程。我们把 RCU 更新过程分为两个阶段: Removal (移除阶段) 和 Reclamation (回收阶段)。下面我们分别进行讨论。
在上图中，`t_1 \to t_2` 时间段内是 Removal 阶段，Updater 首先对共享数据结构的副本进行修改操作。在修改完成后，通过调用原语 rcu_assign_pointer() 来修改指针以指向新的副本区域，现代 CPU 的指针操作都是原子的，rcu_assign_pointer() 原语在大多数系统上编译为一个简单的指针赋值操作。我们把这个时刻定义为 `t_1'`。在 `t_1'` 时刻后，由于指针已被更新，所以新的读取操作都将读取到更新后的共享数据结构。注意到在 `t_1 \to t_2` 时间段内，当 Updater 在修改数据的时候，并行的四个 Reader 并不受影响，尽管它们读取的是旧的共享数据结构。
在 `t_2` 时刻，Updater 调用了原语 synchronize_rcu() 来进入 Grace Period (宽限期)，其本质是 Updater 在修改完指针之后必须释放掉旧的共享数据结构，而旧的共享数据结构由于还有 Reader 在进行读取操作 (i.e. 在 `t_1'` 之前发起读取访问的 Reader 使用的都是旧共享数据结构)，因此不能被立即释放 (i.e. 我们把这些读取操作称为 "pre-existed read")，所以 Updater 就会进入阻塞的 Grace Period 以等待所有的 "pre-existed read" 结束。在上图所示的 `t_3` 时刻，最后一个 "pre-existed reader" 调用了 rcu_read_unlock() 离开了它的 Read-side Critical Section，此时旧的共享数据结构已经没有任何 "pre-existed reader" 产生的引用，所以 Updater 下一步就可以安全地将其给释放掉，此时 Grace Period 就结束了。
`t_3` 时刻 Grace Period 结束后，我们就进入了 Reclamation 阶段，此时 Updater 会将已 "无人问津" 的旧的共享数据结构释放掉。
3. RCU 原语
本小节对我们上面用到过的 RCU 原语进行总结。
3.1 rcu_read_lock()
void rcu_read_lock(void) 在 Reader 读取受 RCU 保护的共享数据结构之前被调用，以说明 Reader 进入了 Read-side Critical Section。在 Read-side Critical Section 访问的任何受 RCU 保护的共享数据结构都会保证在临界区期间保持未回收状态。另外，值得注意的是在 Read-side Critical Section 中阻塞是非法的。Linue Kernel 的 void rcu_read_lock(void) 的实现非常简单，事实上就是调用了 preempt_disable() 关闭了内核调度器的抢占机制。
3.2 rcu_read_unlock()
void rcu_read_lock(void) 在 Reader 离开 Read-side Critical Section 时被调用，已说明 Reader 对受 RCU 保护的共享数据结构的访问已经结束。同样地，与 void rcu_read_lock(void) 相反，void rcu_read_lock(void) 的实质是通过调用 preempt_enable() 重新使能了内核调度器的抢占机制。
3.3 synchronize_rcu()
void synchronize_rcu(void) 在 Updater 修改完指向受 RCU 保护的共享数据结构的指针之后被调用，它是一个阻塞型函数：在旧的数据结构区域仍有 "pre-existed reader" 在进行访问时 (i.e. 这些 "pre-existed reader" 尚未调用 void rcu_read_lock(void) 离开它们的 Read-side Critical Section) 发生阻塞，一直等到所有 "pre-existed reader" 结束对旧数据结构区域的访问。阻塞结束后，这个函数会释放旧结构体。synchronize_rcu 的调用点标志着 "更新者代码的结束" 和 "回收者代码的开始"。
3.4 rcu_assign_pointer()
void rcu_assign_pointer(p, typeof(p) v) 通过宏实现，其作用是给受 RCU 保护的共享数据结构对应的指针赋新值，由 Updater 来调用。
3.5 rcu_dereference()
typeof(p) rcu_dereference(p) 同样通过宏来进行实现，Reader 可以通过 rcu_dereference() 获取受保护的 RCU 指针。
4. RCU 原语使用实例
TODO，可以参考 [6] 来进行补充。
附录：参考源
- Quara, What is the read-copy-update mechanism in Linux Kernel?
- LWN.net, What is RCU? Part 2: Usage
- StackOverflow, what does __rcu stands for in linux?
- 知乎, rcu 机制简介
- Paul E. McKenney, Read-Copy Update (RCU) Papers
- 梁康, 深入理解 Linux 的 RCU 机制