1. Linux中的RCU机制[二] - GP的处理
Linux中的RCU机制[一] - 原理与使用方法
说明：由于现代 RCU 的实现已非常复杂，本文将基于 Linux 2.5.43 版本来解释 RCU 的基本概念与使用方法，同时也会涉及一些现代 RCU 的特性。
GP 的生命周期
RCU 的 Grace Period（GP）从产生到结束的生命周期如下：GP 由 writer 的 CPU 发起，发生在 writer 调用 synchronize_rcu()/call_rcu() 的时刻，表示准备释放一个 object 的时候。释放的具体操作（callback）被填入 object 的 "rcu_head" 中，然后加入到待执行的链表中。"rcu_head" 主要用于携带 callback 信息，类似于 "list_head"。
何时开始与何时结束
GP 开始于 writer 发起释放 object 的操作，结束条件取决于 CPU 的状态。在默认的 non-preemptible 的 RCU 中，reader 所在的 CPU 上的调度在进入临界区时关闭，直到退出后重新打开。除非涉及 SRCU 的情况，临界区内的代码不能睡眠或阻塞，因此不会发生线程切换。
判断退出临界区
当 CPU 开始执行其他任务，说明发生了线程切换，意味着该 CPU 已退出临界区。在 tick 中断时，如果 CPU 在 userspace 执行代码，同样可以判断临界区已退出。处于 idle loop 中的 CPU 也可作为判断依据，虽然代码做了裁剪，未加入 interrupt context 的判断。
判断退出的机制
在 tasklet 的执行函数中，通过比较 "qsctr" 的变化来判断是否退出了临界区。"qsctr" 是 QS 的计数，从 reader 退出临界区开始，到可以判定离开临界区的这段时间，被称为 "Quiescent State"（QS）。
QS 与 GP
QS 是 CPU 私有的，而 GP 是全局的，类似于“一票否决制”。当所有 CPU 都进入 QS，GP 才能结束。分配 bitmap 用于标记每个 CPU 的状态，GP 开始后将所有 bit 置 1，一个 CPU 进入 QS 后，将其对应的 bit 清零。所有 bits 都被置 0 后，就可以判断 GP 的结束。
存在的问题与解决方案
多个 CPU 同时操作 bitmap 的问题需要使用 spinlock 来保护。对于 CPU 数量较多的情况，采用层级管理结构，每个 CPU 向 "rcu_node" 的 leader 汇报 QS 标记状态，增强了系统的扩展性。
为什么 writer 侧的 callback 需要 per-cpu 的链表？
同一个 writer 可能发起多个 object 的 GP，因此采用链表排队，并且链表是 per-cpu 的。即使在 GP 之间，一个 writer 可能同时处理多个 callback，直到所有 GP 的 CPU 都进入 QS，这些 GP 的 callback 才能一起执行。
RCU 的优势与问题
RCU 的基本流程介绍完毕，下文将探讨 RCU 的优势、问题以及衍生品种 SRCU。
注-1：Tree RCU 的实现没有采用 rbtree 或者 radix tree，而是通过数组与指针连接形成逻辑上的树形关系，同时实现广度优先遍历。
注-2：郭大侠的讲解深入浅出，让一些难以理解的 Linux 内核细节变得清晰，实属难得。