分级RCU的基础知识
1、准备工作
本文基于linux 2.6.32-rc7版本的源码， 因此请准备一份linux2.6.32-rc7代码。建议用如下两种方法获取源代码：
1、直接在linux.org上面下载源码包。
2、使用git从linux-next拉取最新代码，然后使用git checkout -b linux-2.6.32-rc7 v2.6.32-rc7检出2.6.32-rc7版本的源码。
2、概述
虽然linux更早版本中的经典rcu，其读端原语拥有出色的性能和扩展性，但是写端原语则需要判断预先存在的读端临界区在什么时候完成，它仅仅被设计用于数十个cpu的系统。经典rcu的实现，要求在每个优雅周期内，每个cpu必须获取一个全局锁，这使得它们的扩展性受到了限制。虽然在实际生产系统中，经典rcu可以运行在几百个cpu的系统中，甚至能够比较困难的使用到上千个 cpu的系统中，但是大型多核系统仍然需要更好的扩展性。
另外，经典rcu有一个不是最优的dynticks 接口，导致经典rcu在每一个优雅周期都要唤醒每一个cpu，即使这些cpu处于idle状态。我们考虑一个16核的系统，它只有四个cpu比较忙，其他cpu的负载都很轻。理想情况下，余下12个cpu可以一直处于深度睡眠模式以节约能源。然而不幸的是，如果四个忙的cpu频繁的执行rcu更新，这12个空闲cpu会被周期性的唤醒，浪费了重要的能源。因此，对于经典rcu的任何优化，都应当让这些睡眠状态的cpu继续处于睡眠状态。
经典rcu和分级rcu实现都有和经典rcu相同的语义和api。但是，原有的实现被称为“经典rcu”，新实现被称为“分级rcu”。
2.1. rcu基础回顾
从最基本的方面来说，rcu 是一种等待事务完成的方法。当然，要等待事务完成，还存在很多其他方法，包括引用计数、读写锁、事件等等。rcu的一个大的优势是可以同时等待20，000个不同的事件，而不必具体的跟踪其中每一个事件，并且不用担心性能被降低，以及扩展性被限制，也不用担心复杂的死锁情况和内存泄漏的危险。
在rcu中，被等待的事件被称为“rcu 读端临界区”。rcu读端临界区以rcu_read_lock()原语开始，以相应的rcu_read_unlock() 原语结束。rcu读端临界区可以嵌套，也可以包含相当多的代码，只要这些代码不阻塞或者睡眠(当然，这是针对经典rcu来说的。有一种特殊的名为srcu的可睡眠rcu，它允许在srcu读端临界区中进行短期睡眠)。如果您遵从这些约束，您可以使用rcu来等待任何代码片段完成。
rcu通过间接的确定其他事务何时完成来实现这一点。但是，请注意：在特定的优雅周期之后开始的rcu 读端临界区能够、也必然会延长优雅周期的结束点。
2.2. 经典rcu实现概要
经典rcu实现的关键原理是：经典rcu 读端临界区限制其中的内核代码不允许阻塞。这意味着在任意时刻，一个特定的cpu只要看起来处于阻塞状态、idle循环、或者离开了内核后，我们就知道所有rcu读端临界区已经完成。这些状态被称为“静止状态”，当每一个cpu已经经历过至少一次静止状态时，rcu优雅周期结束。
经典rcu最重要的数据结构是rcu_ctrlblk，它包含了->cpumask字段，每一个cpu在该字段中包含一位，如上图所示。当每一个优雅周期开始时，每一个 cpu相应的位被设置为1，每一个cpu经过一次静止状态时，必须清除相应的位。由于多个cpu可能希望同时清除它们的位，这将破坏->cpumask 字段，因此使用了一个->lock自旋锁来保护->cpumask。不幸的是，当超过几千个cpu时，这个自旋锁会遇到严重的竞争状态。更糟糕的是，事实上所有cpu必须清除它们的位，意味着在一个优雅周期内，cpu不允许一直睡眠。这削弱了linux节能的能力。
2.3. rcu 迫切要解决的问题
实时rcu迫切要解决的问题列表如下：
1. 延迟销毁。这样，直到所有已经预先存在的rcu读端临界区已经完成，一个rcu优雅周期才能结束。
2. 可靠性，这样rcu支持24x7运行。
3. 可以在irq处理函数中调用。
4. 包含内存标记，这样，如果有很多回调过程，这种机制将加快结束优雅周期。
5. 独立的内存块，这样rcu能够基于可信的内存分配器进行工作。
6. synchronization-free的读端，这样允许通常的非原子指令操作于cpu（或者任务）的本地内存。
7. 无条件的read-to-write提升，在linux内核中，有几个地方需要这样使用。
8. 兼容的api。
9. 抢占rcu读端临界区的要求可以被去掉。
10. 极低的rcu内部锁的竞争，从而带来极大的扩展性。rcu必须支持至少1，024个cpu，最好是至少4，096个cpu。
11. 节能：rcu必须能够避免唤醒低电压状态的dynticks-idle cpu，但是仍然能够判断当前的优雅周期何时结束。这已经在实时rcu中实现，但是需要大大的简化。
12. rcu读端临界区必须允许在nmi处理函数中使用，就如在中断处理函数中一样。
13. rcu必须很好的管理不停的cpu热插拨操作。
14. 必须能够等待所有事先注册的rcu回调完成，虽然这已经以rcu_barrier()的形式提供。
15. 检测失去响应的cpu是值得的，以帮助诊断rcu和死循环bug及硬件错误，这能够防止rcu优雅周期不能结束的情况。
16. 加快rcu优雅周期是值得的，这样rcu优雅周期能够强制在数百微秒内完成。但是，这样的操作预期会带来严重的cpu负载。
最急迫的首要需求是：可扩展性。因此需要减少rcu的内部锁。
2.4. 迈向可扩展rcu实现
减少锁竞争的一个有效方法是创建一个分级结构，如上图所示。在此，四个rcu_node 结构中的每一个都有各自的锁，这样只有 cpu 0 和 1 会获取最左边的 rcu_node的锁， cpu 2 和 3 会获取中间的rcu_node的锁，cpu 4和5会获取右边的rcu_node的锁。在任一个优雅周期期间，仅仅某一个cpu节点会访问rcu_node 结构的上一层的rcu_node。也就是说，在上图中，每一对cpu(它们处于同一个cpu节点)中，最后一个记录静止状态的cpu才会访问上一层的rcu_node。
这样做的最终结果，是减少了锁的竞争。在经典rcu中，6个cpu在每一个优雅周期内竞争同一个全局锁，在上图中，仅仅是三个节点竞争最上层的rcu_node锁 (降低了50%)。
rcu_node结构树被嵌入到rcu_state 结构的一个线性数组，树根是结点0，如上图。它是一个8-cpu的、三层分级结构的系统。每一个箭头将一个rcu_node 结构链接到它的父结点，这对应着rcu_node结构的->parent 字段。每一个rcu_node都标示了它所覆盖的cpu范围，这样根结点覆盖了所有cpu，每一个二级结点覆盖了一半的cpu，每一个叶子结点覆盖了两个 cpu。这个数组在编译时基于nr_cpus的值静态分配。
上图显示了如何检测优雅周期。在第一个图中，没有cpu经过静止状态，并用红块标示。假设所有6个cpu试图同时告诉rcu，它们已经经过一个静止状态。那么，在每一对cpu中，仅仅其中某一个cpu能够获得底层rcu_node结构的锁。第二个图中，假设cpu0、3、5比较幸运的获得了底层rcu_node结构的锁，在图中标识为绿色块。一旦这些幸运的cpu结束了，那么其他cpu将获得锁，如图3所示。这三个cpu中，每一个cpu将会发现它们是组内最后一个cpu，因此所有三个cpu尝试移到上层rcu_node。此时，仅仅其中一个能获得上层rcu_node 锁。我们假设cpu1、2、4依次获得了锁，则第4、5、6图显示了相应的状态。最后，第6图显示了所有cpu已经经过一次静止状态，因此优雅周期结束。
在上面的顺序中，没有超过3个cpu为同一个锁产生竞争，与经典rcu进行对比，我们会高兴的发现，经典rcu中，所有6个cpu都可能冲突。但是，对更多的cpu来说，可以再显著的减少锁之间的冲突。考虑有64个底层结构及64*64=4,096 cpu的分组结构，如图上图。
在此，每一个底层rcu_node 结构的锁被64个cpu申请，将从经典rcu的4096个cpu竞争一个单一的锁降为64个cpu竞争一个锁。在一个特定的优雅周期期间，仅仅一个底层rcu_node 中的某一个cpu会申请上级rcu_node 的锁。这样，与经典rcu相比，减少了64倍的锁竞争。
2.5. 迈向不成熟的rcu实现
正如较早前提示的一样，这些努力的一个重要目的是使一个处于睡眠状态的cpu保持它的睡眠状态，以节约能源。与之相对的是，经典rcu至少会在一个优雅周期内唤醒每一个处于睡眠状态的cpu。当其他大多数cpu都处于空闲状态时，这些个别的cpu进行rcu写操作，会使得这种处理方法不是最优的。这种情形将在周期性的高负载系统中发生，我们需要更好的处理这种情况。
这是通过要求所有cpu操作位于一个每cpu rcu_dynticks 结构中的计数器来实现的。不是那么准确的说，当相应的cpu处于dynticks idle模式时，计数器的值为偶数，否则是奇数。这样，rcu仅仅需要等待rcu_dynticks 计数值为奇数的cpu经过静止状态，而不必唤醒正在睡眠的cpu。如上图，每一个每cpu rcu_dynticks结构被“rcu”和“rcu_bh”实现所共享。
2.6. 状态机
从十分高层的视角来看，linux内核rcu 实现可以被认为是一个高级状态机，如上图。在一个很繁忙的系统上，通常的路径是最上面的两个循环。在每一个优雅周期(gp)开始时进行初始化，等待静止状态 (qs)。在一个特定的优雅周期中，当每一个cpu都经历过静止状态时，它其实什么都不用做。在这样一个系统中，经历如下事件表明产生一个静止状态：
1、每一次进程切换
2、在cpu进入idle状态
3、或者执行用户态代码时
cpu热插拨事件将使状态机进入“cpu offline”流程。而“holdout”cpu（那些由于软件或者硬件原因导致迟迟不能经过一次静止状态的cpu）的出现，使得不能快速经历一次静止状态，这将使状态机进入“send reschedipis to holdout cpus”（发送重新调度ipi给holdout cpus）流程。为了避免不必要的唤醒处于dyntick-idle 状态的cpu，rcu 实现将标记这些cpu处于扩展的静止状态，通过“y”分支离开“cpus in dyntick-idle mode?”（但是请注意，这些处于dyntick-idle模式的cpu将不会被发送重新调度ipi）。最后，如果config_rcu_cpu_stall_detector打开了，过迟的到达静止状态将使状态机进入“complain about holdout cpus”流程。
上面的状态图中，事件会与不同的数据结构交互。但是，状态图不会被任何rcu实现直接翻译为c代码。相反的，这些实现在内核中被编码为事件驱动的系统。我们通过一些用例来表示这些事件。
2.7.用例
这些事件驱动的用例包括：
1.开始一个新的优雅周期
2.经历一个静止状态
3.向rcu通告一个静止状态
4.进入、退出dynticks idle 模式
5.从dynticks idle 模式进入中断
6.从 dynticks idle 模式进入nmi
7.标记一个cpu处于dynticks idle 模式
8.cpu离线
9.cpu上线
10.检测一个太长的优雅周期
2.7.1.开始一个新的优雅周期
rcu_start_gp()函数开始一个新的优雅周期。当一个cpu存在回调，而该回调需要等待优雅周期时，就需要调用此函数。
rcu_start_gp()函数更新rcu_state和rcu_data结构中的状态，以标识开始一个新的优雅周期，获取->onoff 锁 (并关中断) 以防止任何并发的cpu热插拨操作，在所有的rcu_node结构中设置位，以标识所有cpu (包括当前cpu) 必须经历一次静止状态，最后释放->onoff 锁。
设置位操作分两个阶段进行。首先，在没有持有任何锁的情况下，非叶子节点rcu_node 的位被设置，然后，在持有->lock的情况下，每一个叶子节点的rcu_node 结构的位被设置。
2.7.2.经历一次静止状态
rcu和rcu_bh有各自的静止状态集合。
rcu的静止状态是进程切换、idle (不管是dynticks 还是idle循环)、以及执行用户态程序。
rcu-bh的静止状态是在开中断状态下，退出软中断。
需要注意的是，rcu的静止状态也是rcu_bh的静止状态。rcu的静止状态通过调用rcu_qsctr_inc()来记录。而rcu_bh的静止状态通过调用rcu_bh_qsctr_inc()来记录。这两个函数将它们的状态记录到当前cpu的rcu_data 结构中。请注意：在2.6.32版本中，rcu_qsctr_inc和rcu_bh_qsctr_inc函数已经被更名。如何通过git查找它们被更名为什么名称，这个任务就留给作者当做练习了。
这些函数在调度器、__do_softirq()和rcu_check_callbacks()中被调用。后面这个函数在调度时钟中断中调用，并分析状态以确定中断是否发生在一个静止状态中，以确定是调用rcu_qsctr_inc()或者 rcu_bh_qsctr_inc()。它也触发rcu_softirq软中断，并导致当前cpu在随后的软中断上下文中调用rcu_process_callbacks()，rcu_process_callbacks函数处理rcu在每个cpu上的回调函数以释放资源。
2.7.3.向rcu宣告一次静止状态
前述的rcu_process_callbacks() 函数要完成几个事情：
1.确定何时结束一个太长的优雅周期(通过force_quiescent_state())。
2.当cpu检测到优雅周期结束时，采用适当的动作。(通过 rcu_process_gp_end())。“适当的动作”包括加快本cpu的回调，以及记录新的优雅周期。同一个函数也更新状态以响应其他cpu。
3.向rcu核心机制报告当前cpu的静止状态。(通过 rcu_check_quiescent_state()，它会调用 cpu_quiet())。当然，这个过程也会标记当前的优雅周期结束。
4.如果没有处理优雅周期，并且这个cpu有rcu回调等待优雅周期，则开始一个新的优雅周期(通过 cpu_needs_another_gp()和rcu_start_gp())。
5.当优雅周期结束时，调用这个cpu的回调 (通过 rcu_do_batch())。
这些接口都经过精心实现，以避免bug，如：错误的从上一个优雅周期向当前优雅周期报告静止状态这样的bug。
2.7.4.进入和退出 dynticks idle模式
调度器调用rcu_enter_nohz()进入dynticks-idle 模式，并调用 rcu_exit_nohz()离开此模式。rcu_enter_nohz() 函数递增每cpu dynticks_nesting变量，也递增每cpu dynticks计数器，然后，后者必然拥有一个偶数值。rcu_exit_nohz() 函数递减每cpu dynticks_nesting 变量，并且再一次递增每cpu dynticks计数器，后者将拥有一个奇数值。
dynticks 计数器可以被其他 cpu采样。如果其值是偶数，那么该cpu处于扩展静止状态。类似的，如果计数器在一个特定的优雅周期内发生了改变，那么cpu必然在优雅周期期间的某个时间点上处于扩展静止状态。但是，还需要采样另外一个dynticks_nmi每cpu变量，随后我们将讨论这个变量。
2.7.5.从dynticks idle 模式进入中断
从dynticks idle 模式进入中断由rcu_irq_enter() 和 rcu_irq_exit()处理。rcu_irq_enter() 函数递增每cpu dynticks_nesting 变量，如果此变量为0，也递增dynticks每cpu变量 (它将拥有一个奇数值)。
rcu_irq_exit()函数递减每cpu dynticks_nesting变量。并且，如果新值是0，也递增dynticks每cpu变量 (它将拥有一个偶数值)。
注意：进入中断会处理退出dynticks idle模式，反之也一样。进入、退出之间不一致可能导致一些混乱，不用警告你也应该想得到这一点。
2.7.6.从dynticks idle 模式进入nmi
从dynticks idle模式进入nmi由rcu_nmi_enter()和rcu_nmi_exit()处理。这些函数同时递增dynticks_nmi计数器，但仅仅是在前述dynticks 计数是偶数时才进行递增。换句话说，如果nmi发生时，处于非dynticks-idle模式或者处于中断状态，那么 nmi将不操作dynticks_nmi计数器。
这两个函数之间唯一的差异在于错误检查，rcu_nmi_enter()必然使dynticks_nmi计数器为奇数值，rcu_nmi_exit()必然使这个计数器为偶数值。
2.7.7.标记cpu处于dynticks idle模式
force_quiescent_state()函数实现一个三阶段的状态机。第一个阶段 (rcu_initializing)等待rcu_start_gp()完成对优雅周期的初始化。这个状态不是从force_quiescent_state()退出，就是从rcu_start_gp()退出。
在第二阶段(rcu_save_dyntick)，dyntick_save_progress_counter()函数扫描还没有报告静止状态的cpu，记录它们的每cpu dynticks 和dynticks_nmi 计数器。如果这些计数器都是偶数值，那么相应的cpu处于dynticks-idle 状态，因此标记它们为扩展静止状态(通过cpu_quiet_msk()报告)。
在第三阶段(rcu_force_qs)，rcu_implicit_dynticks_qs()函数再一次扫描仍然没有报告静止状态的cpu (既没有明确标示，也没有在rcu_save_dyntick阶段隐含的标示)，再一次检查每cpu dynticks 和 dynticks_nmi计数器。如果每一个值都变化，或者目前为偶数，那么相应的相应的cpu已经经过一次静止状态或者目前处于dynticks idle模式，也就是前述扩展静止状态。
如果rcu_implicit_dynticks_qs()发现特定cpu既没有处于dynticks idle模式，也没有报告一个静止状态，它调用rcu_implicit_offline_qs()，这个函数检查cpu是否处于离线状态，如果是，那么也报告一个扩展静止状态。如果cpu在线，那么rcu_implicit_offline_qs()发送一个重新调度ipi，尝试提醒该cpu应当向rcu报告一个静止状态。
请注意：force_quiescent_state() 既不直接调用dyntick_save_progress_counter()，也不直接调用rcu_implicit_dynticks_qs()，而是将它们传递给rcu_process_dyntick() 函数。这个函数抽象出扫描cpu、报告扩展静止状态的通用代码。
2.7.8.cpu离线
cpu离线事件导致rcu_cpu_notify()调用rcu_offline_cpu()，在rcu和rcu_bh上依次调用__rcu_offline_cpu()。这个函数清除离线cpu的位，这样，后面的优雅周期将不再期望这个cpu宣告静止状态，随后调用cpu_quiet()，以宣告离线扩展静止状态。这是在持有全局->onofflock锁的情况下执行的，这是为了防止与优雅周期初始化相冲突。
2.7.9.cpu上线
cpu上线事件导致rcu_cpu_notify()调用rcu_online_cpu()，用于初始化cpu的dynticks状态，然后调用rcu_init_percpu_data()初始化cpu的rcu_data 数据结构，也设置这个 cpu的位(同样通过全局->onofflock进行保护)，这样后面的优雅周期将等待这个cpu的静止状态。最后，rcu_online_cpu()设置这个cpu的rcu 软中断向量。
2.7.10.检测太长的优雅周期
当配置了config_rcu_cpu_stall_detector内核参数时，record_gp_stall_check_time() 函数记录当前时间，以及3秒以后的时间戳。如果当前优雅周期到期后仍然没有结束，那么check_cpu_stall函数将检测罪魁祸首。并且如果当前cpu是造成延迟的cpu，则调用print_cpu_stall()，如果不是，则调用print_other_cpu_stall()。两个jiffies的时间差有助于确保其他cpu在可能的情况下报告它的状态，利用这个时间差，cpu能够做一些事情，例如跟踪它自己的堆栈。
2.8.测试
rcu是基本的同步代码，因此rcu的错误导致的后果是随机的、难于调试的内存错误。因此，高可靠的rcu是非常重要的。这些可靠性来自于小心的设计，但是最终还是需要依赖于高强度的压力测试。
幸运的是，虽然有一些关于覆盖性方面的争论，但是仍然可以对软件进行一些压力测试。实际上，进行这些测试是被强烈建议的，因为不对你的软件进行折磨性测试的话，它就会反过来折磨你，这种折磨来自于：它在不合时宜的时候崩溃掉。
因此，我们使用rcutorture模块来对rcu进行压力测试。
但是，根据通常情况下的rcu用法来对rcu进行测试，显得还不是很充分。也有必要针对不常用的情况进行压力测试。例如，cpu并发的上线或者离线，cpu并发的进入及退出dynticks idle模式。paul使用了一个脚本codesamples，并向模块rcutorture使用test_no_idle_hz 模块参数对dynticks idle模式进行压力测试。有时作者也比较疑神疑鬼，因此尽量在测试时运行一个kernbench负载测试程序。在128路的机器上运行10个小时的压力测试，看起来是足够测试出几乎所有bug了。
实际上这还不算完。alexey dobriyan和nick piggin早在2008年就证明过，以所有相关内核参数组合对rcu进行压力测试是必要的。相关的内核参数可以使用另外一个脚本codesamples进行标识。
1.config_classic_rcu：经典 rcu。
2.config_preempt_rcu：可抢占 (实时) rcu。
3.config_tree_rcu：用于大型smp系统的经典 rcu。
4.config_rcu_fanout：每一个rcu_node 的子结点数量。
5.config_rcu_fanout_exact：平衡rcu_node 树。
6.config_hotplug_cpu：允许 cpu上线、离线。
7.config_no_hz：打开dyntick-idle 模式。
8.config_smp：打开 multi-cpu选项。
9.config_rcu_cpu_stall_detector：当cpu进入扩展静止状态时进行rcu检测。
10.config_rcu_trace：在debugfs中生成 rcu跟踪文件。
我们忽略config_debug_lock_alloc 配置变量，因为我们假设分级rcu不能打断 lockdep。仍然有10个配置变量，如果它们是独立的布尔值，则导致1024种组合。幸运的是，首先，其中前三个是互斥的，这样可以将组合数量减少到384个，但是config_rcu_fanout可以取值2-64，将组合数量增加到12，096。这么大量的组合是不可能都实施的。
关键的一点是：如果config_classic_rcu或者config_preempt_rcu有效时，预期仅仅config_no_hz 和 config_preempt 可能会改变其行为。这几乎减少了三分之二的组合。
而且，并不是这些所有可能的config_rcu_fanout值都会产生显著有效的结果，实际上仅仅一部分情况需要分别测试：
1.单结点“tree”。
2.两级平衡树。
3.三级平衡树。
4.自动平衡树，当 config_rcu_fanout 指定一个不平衡树，但是没有配置config_rcu_fanout_exact 时，进行自动平衡。
5.非平衡树。
更进一步说，config_hotplug_cpu仅仅在指定config_smp 时才有用，config_rcu_cpu_stall_detector是独立的，因此仅仅需要测试一次(然而有些人比我还多疑，他们可能决定在有config_smp和没有config_smp 时，都测试它)。类似的，config_rcu_trace也仅仅需要测试一次。但是象我一样多疑的人，会选择在有config_no_hz 和没有config_no_hz 时，都测试一下它。
这允许我们在15种测试情形下，得到一个覆盖率较好的rcu测试。所有这些测试情形都指定如下配置参数以运行rcutorture，这样config_hotplug_cpu=n会产生实际的效果：
config_rcu_torture_test=m
config_module_unload=y
config_suspend=n
config_hibernation=n
15个测试用例如下：
1.强制单节点“树”，用于小型系统：
config_nr_cpus=8
config_rcu_fanout=8
config_rcu_fanout_exact=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
2.强制两级节点树用于大型系统：
config_nr_cpus=8
config_rcu_fanout=4
config_rcu_fanout_exact=n
config_rcu_trace=n
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
3.强制三级节点树，用于非常大型的系统:
config_nr_cpus=8
config_rcu_fanout=2
config_rcu_fanout_exact=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
4.测试自动平衡：
config_nr_cpus=8
config_rcu_fanout=6
config_rcu_fanout_exact=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
5.测试不平衡树：
config_nr_cpus=8
config_rcu_fanout=6
config_rcu_fanout_exact=y
config_rcu_cpu_stall_detector=y
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
6.禁止cpu延迟检测：
config_smp=y
config_no_hz=y
config_rcu_cpu_stall_detector=n
config_hotplug_cpu=y
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
7.禁止 cpu延迟检测及dyntick idle 模式：
config_smp=y
config_no_hz=n
config_rcu_cpu_stall_detector=n
config_hotplug_cpu=y
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
8.禁止 cpu延迟检测及cpu热插拨：
config_smp=y
config_no_hz=y
config_rcu_cpu_stall_detector=n
config_hotplug_cpu=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
9.禁止 cpu延迟检测，dyntick idle 模式，及cpu热插拨：
config_smp=y
config_no_hz=n
config_rcu_cpu_stall_detector=n
config_hotplug_cpu=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
10.禁止smp、cpu延迟检测、dyntick idle 模式、及cpu热插拨：
config_smp=n
config_no_hz=n
config_rcu_cpu_stall_detector=n
config_hotplug_cpu=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
这个组合有一些编译警告。
11.禁止smp、禁止cpu热插拨：
config_smp=n
config_no_hz=y
config_rcu_cpu_stall_detector=y
config_hotplug_cpu=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
12.有dynticks idle 但是没有抢占的情况下，测试经典rcu：
config_no_hz=y
config_preempt=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=y
config_tree_rcu=n
13.有抢占但是没有dynticks idle时，测试经典rcu：
config_no_hz=n
config_preempt=y
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=y
config_tree_rcu=n
14.在dynticks idle情况下，测试可抢占rcu：
config_no_hz=y
config_preempt=y
config_rcu_trace=y
config_preempt_rcu=y
config_classic_rcu=n
config_tree_rcu=n
15.在没有 dynticks idle时，测试可抢占rcu：
config_no_hz=n
config_preempt=y
config_rcu_trace=y
config_preempt_rcu=y
config_classic_rcu=n
config_tree_rcu=n
对于每一次大的影响rcu核心代码的变化，都应当以上面的组合运行rcutorture，并且在config_hotplug_cpu时，并发的进行cpu热插拨。对小的变化，在每一种情况下运行kernbench就行了。当然，如果变化仅仅限于配置参数的部分子集，就可以减少测试用例的数量。
作者强烈推荐压力测试软件：geneva convention！
2.9.结论
这个分级rcu实现减少了锁竞争，避免了不必要的唤醒dyntick-idle睡眠状态的cpu，因此有助于调试linux cpu热插拨代码。这个实现被设计用于处理数千个cpu的大型系统，并且在64位系统上，cpu数量限制是250，000，在今后一段时间内，这个限制是没有问题的。
这个rcu实现当然也有一些局限：
1.force_quiescent_state()可能在关中断下扫描整个cpu集。这在实时rcu实现中，是一个重大缺陷。因此，如果需要在可抢占rcu中加入分级，则需要其他方法。在4096个cpu的系统中，它可能会产生一些问题，但是需要在实际的系统中进行测试以证明真的有问题。
在繁忙的系统中，不能指望force_quiescent_state()扫描会发生，cpu将在开始一个静止状态后，在三个jiffies内经历一次静止状态。在半繁忙的系统中，仅仅处于dynticks-idle模式的cpu需要扫描。其他情况下，例如，在一个dynticks-idle cpu扫描过程中，处理一个中断时，后继的扫描是需要的。但是，这样的扫描是分别在相应的cpu上执行的，因此相应的调度延迟仅仅影响该扫描过程所在的cpu负载。
如果扫描被证明确实有问题，一个好的方法是进行递增扫描。这将稍微增加一点代码复杂性，也增加一点结束优雅周期的时间，但是这也确实算是一个好的方案。
2.rcu_node分级在编译时创建，因此其长度是最大的cpu数量nr_cpus。但是，即使在4，096 cpu的系统中，在64位系统上，rcu_node 分级也仅仅消耗65个缓存行。(即使在32位系统上包含4，096 cpus也是这样!)。当然，在一个16 cpu的系统中，配置nr_cpus=4096将使用一个二级树，实际上在这种情况下，单节点树也会运行得很好。虽然这个配置会增加锁的负载，但是实际上不会影响经常执行的读端代码，因此事实上不会有太大的问题。
3.这个补丁会稍微增加内核代码及数据尺寸：在nr_cpus=4的系统中，从经典rcu的1，757字节内核代码、456字节数据，共2213字节的内核尺寸，而分级rcu则增加到4，006字节的内核代码、624字节的内核数据，共计4，630字节尺寸。即使对大多数嵌入式系统来说，这也不是一个问题。这些系统通常有上百兆主内存。但是对特别小的系统来说，这可能就是一个问题了，需要提供两种类型的rcu实现以满足这样的嵌入式系统。不过有一个有趣的问题，在这样的系统中，也许仅仅包含一个cpu，这样的系统完全可以用一个特别简单的rcu实现。
即使有这些问题，相对于经典rcu来说，在数百个cpu的系统中，这个分级rcu实现仍然是一个巨大的进步。最后需要说明一下，经典rcu设计用于16-32个cpu的系统。
在某些地方，在可抢占rcu实现中使用分级是有必要的。
后续章节将继续分析分级rcu的代码，以及linux中其他一些rcu的实现。也许还会讨论实现rcu这类复杂并行软件的开发方法及其形式化验证。
基于OpenAMP框架的双核ARM通信案例
精彩预告 | OpenHarmony Meetup 2023 北京站抢先剧透
认识服务器风扇
现代汽车将获得对波士顿动力的最终控制权？
热电堆红外传感器的原理和结构
分级RCU的基础知识
联想Z6Pro 5G高清图集
中国铁塔/宁德时代入局 共享换电赛道机会与暗礁
三星note8什么时候上市？三星note8最新消息：三星Note 8曝光，视觉效果很有冲击力
Microchip 宣布业界首款基于RISC-V的片上系统（SoC）FPGA开始量产
华为智慧屏售价曝光 65寸7999元
电容触控传感技术将会让手机变得更加智能
2020年工业互联网行业趋势分析
高比能量动力电池将是未来研发和产业化的重点
创新突破：精准型农业与气候不确定性
短路保护原理及电路分析
直线导轨使用中常见的问题有哪些
石油公司进军区块链领域会带来什么
身材虽小，用途强大！aigo国民好物固态U盘U393体验
淘宝直播四面楚歌，小主播该如何摆脱困境
本文基于linux 2.6.32-rc7版本的源码， 因此请准备一份linux2.6.32-rc7代码。建议用如下两种方法获取源代码：
1、直接在linux.org上面下载源码包。
2、使用git从linux-next拉取最新代码，然后使用git checkout -b linux-2.6.32-rc7 v2.6.32-rc7检出2.6.32-rc7版本的源码。
2、概述
虽然linux更早版本中的经典rcu，其读端原语拥有出色的性能和扩展性，但是写端原语则需要判断预先存在的读端临界区在什么时候完成，它仅仅被设计用于数十个cpu的系统。经典rcu的实现，要求在每个优雅周期内，每个cpu必须获取一个全局锁，这使得它们的扩展性受到了限制。虽然在实际生产系统中，经典rcu可以运行在几百个cpu的系统中，甚至能够比较困难的使用到上千个 cpu的系统中，但是大型多核系统仍然需要更好的扩展性。
另外，经典rcu有一个不是最优的dynticks 接口，导致经典rcu在每一个优雅周期都要唤醒每一个cpu，即使这些cpu处于idle状态。我们考虑一个16核的系统，它只有四个cpu比较忙，其他cpu的负载都很轻。理想情况下，余下12个cpu可以一直处于深度睡眠模式以节约能源。然而不幸的是，如果四个忙的cpu频繁的执行rcu更新，这12个空闲cpu会被周期性的唤醒，浪费了重要的能源。因此，对于经典rcu的任何优化，都应当让这些睡眠状态的cpu继续处于睡眠状态。
经典rcu和分级rcu实现都有和经典rcu相同的语义和api。但是，原有的实现被称为“经典rcu”，新实现被称为“分级rcu”。
2.1. rcu基础回顾
从最基本的方面来说，rcu 是一种等待事务完成的方法。当然，要等待事务完成，还存在很多其他方法，包括引用计数、读写锁、事件等等。rcu的一个大的优势是可以同时等待20，000个不同的事件，而不必具体的跟踪其中每一个事件，并且不用担心性能被降低，以及扩展性被限制，也不用担心复杂的死锁情况和内存泄漏的危险。
在rcu中，被等待的事件被称为“rcu 读端临界区”。rcu读端临界区以rcu_read_lock()原语开始，以相应的rcu_read_unlock() 原语结束。rcu读端临界区可以嵌套，也可以包含相当多的代码，只要这些代码不阻塞或者睡眠(当然，这是针对经典rcu来说的。有一种特殊的名为srcu的可睡眠rcu，它允许在srcu读端临界区中进行短期睡眠)。如果您遵从这些约束，您可以使用rcu来等待任何代码片段完成。
rcu通过间接的确定其他事务何时完成来实现这一点。但是，请注意：在特定的优雅周期之后开始的rcu 读端临界区能够、也必然会延长优雅周期的结束点。
2.2. 经典rcu实现概要
经典rcu实现的关键原理是：经典rcu 读端临界区限制其中的内核代码不允许阻塞。这意味着在任意时刻，一个特定的cpu只要看起来处于阻塞状态、idle循环、或者离开了内核后，我们就知道所有rcu读端临界区已经完成。这些状态被称为“静止状态”，当每一个cpu已经经历过至少一次静止状态时，rcu优雅周期结束。
经典rcu最重要的数据结构是rcu_ctrlblk，它包含了->cpumask字段，每一个cpu在该字段中包含一位，如上图所示。当每一个优雅周期开始时，每一个 cpu相应的位被设置为1，每一个cpu经过一次静止状态时，必须清除相应的位。由于多个cpu可能希望同时清除它们的位，这将破坏->cpumask 字段，因此使用了一个->lock自旋锁来保护->cpumask。不幸的是，当超过几千个cpu时，这个自旋锁会遇到严重的竞争状态。更糟糕的是，事实上所有cpu必须清除它们的位，意味着在一个优雅周期内，cpu不允许一直睡眠。这削弱了linux节能的能力。
2.3. rcu 迫切要解决的问题
实时rcu迫切要解决的问题列表如下：
1. 延迟销毁。这样，直到所有已经预先存在的rcu读端临界区已经完成，一个rcu优雅周期才能结束。
2. 可靠性，这样rcu支持24x7运行。
3. 可以在irq处理函数中调用。
4. 包含内存标记，这样，如果有很多回调过程，这种机制将加快结束优雅周期。
5. 独立的内存块，这样rcu能够基于可信的内存分配器进行工作。
6. synchronization-free的读端，这样允许通常的非原子指令操作于cpu（或者任务）的本地内存。
7. 无条件的read-to-write提升，在linux内核中，有几个地方需要这样使用。
8. 兼容的api。
9. 抢占rcu读端临界区的要求可以被去掉。
10. 极低的rcu内部锁的竞争，从而带来极大的扩展性。rcu必须支持至少1，024个cpu，最好是至少4，096个cpu。
11. 节能：rcu必须能够避免唤醒低电压状态的dynticks-idle cpu，但是仍然能够判断当前的优雅周期何时结束。这已经在实时rcu中实现，但是需要大大的简化。
12. rcu读端临界区必须允许在nmi处理函数中使用，就如在中断处理函数中一样。
13. rcu必须很好的管理不停的cpu热插拨操作。
14. 必须能够等待所有事先注册的rcu回调完成，虽然这已经以rcu_barrier()的形式提供。
15. 检测失去响应的cpu是值得的，以帮助诊断rcu和死循环bug及硬件错误，这能够防止rcu优雅周期不能结束的情况。
16. 加快rcu优雅周期是值得的，这样rcu优雅周期能够强制在数百微秒内完成。但是，这样的操作预期会带来严重的cpu负载。
最急迫的首要需求是：可扩展性。因此需要减少rcu的内部锁。
2.4. 迈向可扩展rcu实现
减少锁竞争的一个有效方法是创建一个分级结构，如上图所示。在此，四个rcu_node 结构中的每一个都有各自的锁，这样只有 cpu 0 和 1 会获取最左边的 rcu_node的锁， cpu 2 和 3 会获取中间的rcu_node的锁，cpu 4和5会获取右边的rcu_node的锁。在任一个优雅周期期间，仅仅某一个cpu节点会访问rcu_node 结构的上一层的rcu_node。也就是说，在上图中，每一对cpu(它们处于同一个cpu节点)中，最后一个记录静止状态的cpu才会访问上一层的rcu_node。
这样做的最终结果，是减少了锁的竞争。在经典rcu中，6个cpu在每一个优雅周期内竞争同一个全局锁，在上图中，仅仅是三个节点竞争最上层的rcu_node锁 (降低了50%)。
rcu_node结构树被嵌入到rcu_state 结构的一个线性数组，树根是结点0，如上图。它是一个8-cpu的、三层分级结构的系统。每一个箭头将一个rcu_node 结构链接到它的父结点，这对应着rcu_node结构的->parent 字段。每一个rcu_node都标示了它所覆盖的cpu范围，这样根结点覆盖了所有cpu，每一个二级结点覆盖了一半的cpu，每一个叶子结点覆盖了两个 cpu。这个数组在编译时基于nr_cpus的值静态分配。
上图显示了如何检测优雅周期。在第一个图中，没有cpu经过静止状态，并用红块标示。假设所有6个cpu试图同时告诉rcu，它们已经经过一个静止状态。那么，在每一对cpu中，仅仅其中某一个cpu能够获得底层rcu_node结构的锁。第二个图中，假设cpu0、3、5比较幸运的获得了底层rcu_node结构的锁，在图中标识为绿色块。一旦这些幸运的cpu结束了，那么其他cpu将获得锁，如图3所示。这三个cpu中，每一个cpu将会发现它们是组内最后一个cpu，因此所有三个cpu尝试移到上层rcu_node。此时，仅仅其中一个能获得上层rcu_node 锁。我们假设cpu1、2、4依次获得了锁，则第4、5、6图显示了相应的状态。最后，第6图显示了所有cpu已经经过一次静止状态，因此优雅周期结束。
在上面的顺序中，没有超过3个cpu为同一个锁产生竞争，与经典rcu进行对比，我们会高兴的发现，经典rcu中，所有6个cpu都可能冲突。但是，对更多的cpu来说，可以再显著的减少锁之间的冲突。考虑有64个底层结构及64*64=4,096 cpu的分组结构，如图上图。
在此，每一个底层rcu_node 结构的锁被64个cpu申请，将从经典rcu的4096个cpu竞争一个单一的锁降为64个cpu竞争一个锁。在一个特定的优雅周期期间，仅仅一个底层rcu_node 中的某一个cpu会申请上级rcu_node 的锁。这样，与经典rcu相比，减少了64倍的锁竞争。
2.5. 迈向不成熟的rcu实现
正如较早前提示的一样，这些努力的一个重要目的是使一个处于睡眠状态的cpu保持它的睡眠状态，以节约能源。与之相对的是，经典rcu至少会在一个优雅周期内唤醒每一个处于睡眠状态的cpu。当其他大多数cpu都处于空闲状态时，这些个别的cpu进行rcu写操作，会使得这种处理方法不是最优的。这种情形将在周期性的高负载系统中发生，我们需要更好的处理这种情况。
这是通过要求所有cpu操作位于一个每cpu rcu_dynticks 结构中的计数器来实现的。不是那么准确的说，当相应的cpu处于dynticks idle模式时，计数器的值为偶数，否则是奇数。这样，rcu仅仅需要等待rcu_dynticks 计数值为奇数的cpu经过静止状态，而不必唤醒正在睡眠的cpu。如上图，每一个每cpu rcu_dynticks结构被“rcu”和“rcu_bh”实现所共享。
2.6. 状态机
从十分高层的视角来看，linux内核rcu 实现可以被认为是一个高级状态机，如上图。在一个很繁忙的系统上，通常的路径是最上面的两个循环。在每一个优雅周期(gp)开始时进行初始化，等待静止状态 (qs)。在一个特定的优雅周期中，当每一个cpu都经历过静止状态时，它其实什么都不用做。在这样一个系统中，经历如下事件表明产生一个静止状态：
1、每一次进程切换
2、在cpu进入idle状态
3、或者执行用户态代码时
cpu热插拨事件将使状态机进入“cpu offline”流程。而“holdout”cpu（那些由于软件或者硬件原因导致迟迟不能经过一次静止状态的cpu）的出现，使得不能快速经历一次静止状态，这将使状态机进入“send reschedipis to holdout cpus”（发送重新调度ipi给holdout cpus）流程。为了避免不必要的唤醒处于dyntick-idle 状态的cpu，rcu 实现将标记这些cpu处于扩展的静止状态，通过“y”分支离开“cpus in dyntick-idle mode?”（但是请注意，这些处于dyntick-idle模式的cpu将不会被发送重新调度ipi）。最后，如果config_rcu_cpu_stall_detector打开了，过迟的到达静止状态将使状态机进入“complain about holdout cpus”流程。
上面的状态图中，事件会与不同的数据结构交互。但是，状态图不会被任何rcu实现直接翻译为c代码。相反的，这些实现在内核中被编码为事件驱动的系统。我们通过一些用例来表示这些事件。
2.7.用例
这些事件驱动的用例包括：
1.开始一个新的优雅周期
2.经历一个静止状态
3.向rcu通告一个静止状态
4.进入、退出dynticks idle 模式
5.从dynticks idle 模式进入中断
6.从 dynticks idle 模式进入nmi
7.标记一个cpu处于dynticks idle 模式
8.cpu离线
9.cpu上线
10.检测一个太长的优雅周期
2.7.1.开始一个新的优雅周期
rcu_start_gp()函数开始一个新的优雅周期。当一个cpu存在回调，而该回调需要等待优雅周期时，就需要调用此函数。
rcu_start_gp()函数更新rcu_state和rcu_data结构中的状态，以标识开始一个新的优雅周期，获取->onoff 锁 (并关中断) 以防止任何并发的cpu热插拨操作，在所有的rcu_node结构中设置位，以标识所有cpu (包括当前cpu) 必须经历一次静止状态，最后释放->onoff 锁。
设置位操作分两个阶段进行。首先，在没有持有任何锁的情况下，非叶子节点rcu_node 的位被设置，然后，在持有->lock的情况下，每一个叶子节点的rcu_node 结构的位被设置。
2.7.2.经历一次静止状态
rcu和rcu_bh有各自的静止状态集合。
rcu的静止状态是进程切换、idle (不管是dynticks 还是idle循环)、以及执行用户态程序。
rcu-bh的静止状态是在开中断状态下，退出软中断。
需要注意的是，rcu的静止状态也是rcu_bh的静止状态。rcu的静止状态通过调用rcu_qsctr_inc()来记录。而rcu_bh的静止状态通过调用rcu_bh_qsctr_inc()来记录。这两个函数将它们的状态记录到当前cpu的rcu_data 结构中。请注意：在2.6.32版本中，rcu_qsctr_inc和rcu_bh_qsctr_inc函数已经被更名。如何通过git查找它们被更名为什么名称，这个任务就留给作者当做练习了。
这些函数在调度器、__do_softirq()和rcu_check_callbacks()中被调用。后面这个函数在调度时钟中断中调用，并分析状态以确定中断是否发生在一个静止状态中，以确定是调用rcu_qsctr_inc()或者 rcu_bh_qsctr_inc()。它也触发rcu_softirq软中断，并导致当前cpu在随后的软中断上下文中调用rcu_process_callbacks()，rcu_process_callbacks函数处理rcu在每个cpu上的回调函数以释放资源。
2.7.3.向rcu宣告一次静止状态
前述的rcu_process_callbacks() 函数要完成几个事情：
1.确定何时结束一个太长的优雅周期(通过force_quiescent_state())。
2.当cpu检测到优雅周期结束时，采用适当的动作。(通过 rcu_process_gp_end())。“适当的动作”包括加快本cpu的回调，以及记录新的优雅周期。同一个函数也更新状态以响应其他cpu。
3.向rcu核心机制报告当前cpu的静止状态。(通过 rcu_check_quiescent_state()，它会调用 cpu_quiet())。当然，这个过程也会标记当前的优雅周期结束。
4.如果没有处理优雅周期，并且这个cpu有rcu回调等待优雅周期，则开始一个新的优雅周期(通过 cpu_needs_another_gp()和rcu_start_gp())。
5.当优雅周期结束时，调用这个cpu的回调 (通过 rcu_do_batch())。
这些接口都经过精心实现，以避免bug，如：错误的从上一个优雅周期向当前优雅周期报告静止状态这样的bug。
2.7.4.进入和退出 dynticks idle模式
调度器调用rcu_enter_nohz()进入dynticks-idle 模式，并调用 rcu_exit_nohz()离开此模式。rcu_enter_nohz() 函数递增每cpu dynticks_nesting变量，也递增每cpu dynticks计数器，然后，后者必然拥有一个偶数值。rcu_exit_nohz() 函数递减每cpu dynticks_nesting 变量，并且再一次递增每cpu dynticks计数器，后者将拥有一个奇数值。
dynticks 计数器可以被其他 cpu采样。如果其值是偶数，那么该cpu处于扩展静止状态。类似的，如果计数器在一个特定的优雅周期内发生了改变，那么cpu必然在优雅周期期间的某个时间点上处于扩展静止状态。但是，还需要采样另外一个dynticks_nmi每cpu变量，随后我们将讨论这个变量。
2.7.5.从dynticks idle 模式进入中断
从dynticks idle 模式进入中断由rcu_irq_enter() 和 rcu_irq_exit()处理。rcu_irq_enter() 函数递增每cpu dynticks_nesting 变量，如果此变量为0，也递增dynticks每cpu变量 (它将拥有一个奇数值)。
rcu_irq_exit()函数递减每cpu dynticks_nesting变量。并且，如果新值是0，也递增dynticks每cpu变量 (它将拥有一个偶数值)。
注意：进入中断会处理退出dynticks idle模式，反之也一样。进入、退出之间不一致可能导致一些混乱，不用警告你也应该想得到这一点。
2.7.6.从dynticks idle 模式进入nmi
从dynticks idle模式进入nmi由rcu_nmi_enter()和rcu_nmi_exit()处理。这些函数同时递增dynticks_nmi计数器，但仅仅是在前述dynticks 计数是偶数时才进行递增。换句话说，如果nmi发生时，处于非dynticks-idle模式或者处于中断状态，那么 nmi将不操作dynticks_nmi计数器。
这两个函数之间唯一的差异在于错误检查，rcu_nmi_enter()必然使dynticks_nmi计数器为奇数值，rcu_nmi_exit()必然使这个计数器为偶数值。
2.7.7.标记cpu处于dynticks idle模式
force_quiescent_state()函数实现一个三阶段的状态机。第一个阶段 (rcu_initializing)等待rcu_start_gp()完成对优雅周期的初始化。这个状态不是从force_quiescent_state()退出，就是从rcu_start_gp()退出。
在第二阶段(rcu_save_dyntick)，dyntick_save_progress_counter()函数扫描还没有报告静止状态的cpu，记录它们的每cpu dynticks 和dynticks_nmi 计数器。如果这些计数器都是偶数值，那么相应的cpu处于dynticks-idle 状态，因此标记它们为扩展静止状态(通过cpu_quiet_msk()报告)。
在第三阶段(rcu_force_qs)，rcu_implicit_dynticks_qs()函数再一次扫描仍然没有报告静止状态的cpu (既没有明确标示，也没有在rcu_save_dyntick阶段隐含的标示)，再一次检查每cpu dynticks 和 dynticks_nmi计数器。如果每一个值都变化，或者目前为偶数，那么相应的相应的cpu已经经过一次静止状态或者目前处于dynticks idle模式，也就是前述扩展静止状态。
如果rcu_implicit_dynticks_qs()发现特定cpu既没有处于dynticks idle模式，也没有报告一个静止状态，它调用rcu_implicit_offline_qs()，这个函数检查cpu是否处于离线状态，如果是，那么也报告一个扩展静止状态。如果cpu在线，那么rcu_implicit_offline_qs()发送一个重新调度ipi，尝试提醒该cpu应当向rcu报告一个静止状态。
请注意：force_quiescent_state() 既不直接调用dyntick_save_progress_counter()，也不直接调用rcu_implicit_dynticks_qs()，而是将它们传递给rcu_process_dyntick() 函数。这个函数抽象出扫描cpu、报告扩展静止状态的通用代码。
2.7.8.cpu离线
cpu离线事件导致rcu_cpu_notify()调用rcu_offline_cpu()，在rcu和rcu_bh上依次调用__rcu_offline_cpu()。这个函数清除离线cpu的位，这样，后面的优雅周期将不再期望这个cpu宣告静止状态，随后调用cpu_quiet()，以宣告离线扩展静止状态。这是在持有全局->onofflock锁的情况下执行的，这是为了防止与优雅周期初始化相冲突。
2.7.9.cpu上线
cpu上线事件导致rcu_cpu_notify()调用rcu_online_cpu()，用于初始化cpu的dynticks状态，然后调用rcu_init_percpu_data()初始化cpu的rcu_data 数据结构，也设置这个 cpu的位(同样通过全局->onofflock进行保护)，这样后面的优雅周期将等待这个cpu的静止状态。最后，rcu_online_cpu()设置这个cpu的rcu 软中断向量。
2.7.10.检测太长的优雅周期
当配置了config_rcu_cpu_stall_detector内核参数时，record_gp_stall_check_time() 函数记录当前时间，以及3秒以后的时间戳。如果当前优雅周期到期后仍然没有结束，那么check_cpu_stall函数将检测罪魁祸首。并且如果当前cpu是造成延迟的cpu，则调用print_cpu_stall()，如果不是，则调用print_other_cpu_stall()。两个jiffies的时间差有助于确保其他cpu在可能的情况下报告它的状态，利用这个时间差，cpu能够做一些事情，例如跟踪它自己的堆栈。
2.8.测试
rcu是基本的同步代码，因此rcu的错误导致的后果是随机的、难于调试的内存错误。因此，高可靠的rcu是非常重要的。这些可靠性来自于小心的设计，但是最终还是需要依赖于高强度的压力测试。
幸运的是，虽然有一些关于覆盖性方面的争论，但是仍然可以对软件进行一些压力测试。实际上，进行这些测试是被强烈建议的，因为不对你的软件进行折磨性测试的话，它就会反过来折磨你，这种折磨来自于：它在不合时宜的时候崩溃掉。
因此，我们使用rcutorture模块来对rcu进行压力测试。
但是，根据通常情况下的rcu用法来对rcu进行测试，显得还不是很充分。也有必要针对不常用的情况进行压力测试。例如，cpu并发的上线或者离线，cpu并发的进入及退出dynticks idle模式。paul使用了一个脚本codesamples，并向模块rcutorture使用test_no_idle_hz 模块参数对dynticks idle模式进行压力测试。有时作者也比较疑神疑鬼，因此尽量在测试时运行一个kernbench负载测试程序。在128路的机器上运行10个小时的压力测试，看起来是足够测试出几乎所有bug了。
实际上这还不算完。alexey dobriyan和nick piggin早在2008年就证明过，以所有相关内核参数组合对rcu进行压力测试是必要的。相关的内核参数可以使用另外一个脚本codesamples进行标识。
1.config_classic_rcu：经典 rcu。
2.config_preempt_rcu：可抢占 (实时) rcu。
3.config_tree_rcu：用于大型smp系统的经典 rcu。
4.config_rcu_fanout：每一个rcu_node 的子结点数量。
5.config_rcu_fanout_exact：平衡rcu_node 树。
6.config_hotplug_cpu：允许 cpu上线、离线。
7.config_no_hz：打开dyntick-idle 模式。
8.config_smp：打开 multi-cpu选项。
9.config_rcu_cpu_stall_detector：当cpu进入扩展静止状态时进行rcu检测。
10.config_rcu_trace：在debugfs中生成 rcu跟踪文件。
我们忽略config_debug_lock_alloc 配置变量，因为我们假设分级rcu不能打断 lockdep。仍然有10个配置变量，如果它们是独立的布尔值，则导致1024种组合。幸运的是，首先，其中前三个是互斥的，这样可以将组合数量减少到384个，但是config_rcu_fanout可以取值2-64，将组合数量增加到12，096。这么大量的组合是不可能都实施的。
关键的一点是：如果config_classic_rcu或者config_preempt_rcu有效时，预期仅仅config_no_hz 和 config_preempt 可能会改变其行为。这几乎减少了三分之二的组合。
而且，并不是这些所有可能的config_rcu_fanout值都会产生显著有效的结果，实际上仅仅一部分情况需要分别测试：
1.单结点“tree”。
2.两级平衡树。
3.三级平衡树。
4.自动平衡树，当 config_rcu_fanout 指定一个不平衡树，但是没有配置config_rcu_fanout_exact 时，进行自动平衡。
5.非平衡树。
更进一步说，config_hotplug_cpu仅仅在指定config_smp 时才有用，config_rcu_cpu_stall_detector是独立的，因此仅仅需要测试一次(然而有些人比我还多疑，他们可能决定在有config_smp和没有config_smp 时，都测试它)。类似的，config_rcu_trace也仅仅需要测试一次。但是象我一样多疑的人，会选择在有config_no_hz 和没有config_no_hz 时，都测试一下它。
这允许我们在15种测试情形下，得到一个覆盖率较好的rcu测试。所有这些测试情形都指定如下配置参数以运行rcutorture，这样config_hotplug_cpu=n会产生实际的效果：
config_rcu_torture_test=m
config_module_unload=y
config_suspend=n
config_hibernation=n
15个测试用例如下：
1.强制单节点“树”，用于小型系统：
config_nr_cpus=8
config_rcu_fanout=8
config_rcu_fanout_exact=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
2.强制两级节点树用于大型系统：
config_nr_cpus=8
config_rcu_fanout=4
config_rcu_fanout_exact=n
config_rcu_trace=n
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
3.强制三级节点树，用于非常大型的系统:
config_nr_cpus=8
config_rcu_fanout=2
config_rcu_fanout_exact=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
4.测试自动平衡：
config_nr_cpus=8
config_rcu_fanout=6
config_rcu_fanout_exact=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
5.测试不平衡树：
config_nr_cpus=8
config_rcu_fanout=6
config_rcu_fanout_exact=y
config_rcu_cpu_stall_detector=y
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
6.禁止cpu延迟检测：
config_smp=y
config_no_hz=y
config_rcu_cpu_stall_detector=n
config_hotplug_cpu=y
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
7.禁止 cpu延迟检测及dyntick idle 模式：
config_smp=y
config_no_hz=n
config_rcu_cpu_stall_detector=n
config_hotplug_cpu=y
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
8.禁止 cpu延迟检测及cpu热插拨：
config_smp=y
config_no_hz=y
config_rcu_cpu_stall_detector=n
config_hotplug_cpu=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
9.禁止 cpu延迟检测，dyntick idle 模式，及cpu热插拨：
config_smp=y
config_no_hz=n
config_rcu_cpu_stall_detector=n
config_hotplug_cpu=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
10.禁止smp、cpu延迟检测、dyntick idle 模式、及cpu热插拨：
config_smp=n
config_no_hz=n
config_rcu_cpu_stall_detector=n
config_hotplug_cpu=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
这个组合有一些编译警告。
11.禁止smp、禁止cpu热插拨：
config_smp=n
config_no_hz=y
config_rcu_cpu_stall_detector=y
config_hotplug_cpu=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=n
config_tree_rcu=y
12.有dynticks idle 但是没有抢占的情况下，测试经典rcu：
config_no_hz=y
config_preempt=n
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=y
config_tree_rcu=n
13.有抢占但是没有dynticks idle时，测试经典rcu：
config_no_hz=n
config_preempt=y
config_rcu_trace=y
config_preempt_rcu=n
config_classic_rcu=y
config_tree_rcu=n
14.在dynticks idle情况下，测试可抢占rcu：
config_no_hz=y
config_preempt=y
config_rcu_trace=y
config_preempt_rcu=y
config_classic_rcu=n
config_tree_rcu=n
15.在没有 dynticks idle时，测试可抢占rcu：
config_no_hz=n
config_preempt=y
config_rcu_trace=y
config_preempt_rcu=y
config_classic_rcu=n
config_tree_rcu=n
对于每一次大的影响rcu核心代码的变化，都应当以上面的组合运行rcutorture，并且在config_hotplug_cpu时，并发的进行cpu热插拨。对小的变化，在每一种情况下运行kernbench就行了。当然，如果变化仅仅限于配置参数的部分子集，就可以减少测试用例的数量。
作者强烈推荐压力测试软件：geneva convention！
2.9.结论
这个分级rcu实现减少了锁竞争，避免了不必要的唤醒dyntick-idle睡眠状态的cpu，因此有助于调试linux cpu热插拨代码。这个实现被设计用于处理数千个cpu的大型系统，并且在64位系统上，cpu数量限制是250，000，在今后一段时间内，这个限制是没有问题的。
这个rcu实现当然也有一些局限：
1.force_quiescent_state()可能在关中断下扫描整个cpu集。这在实时rcu实现中，是一个重大缺陷。因此，如果需要在可抢占rcu中加入分级，则需要其他方法。在4096个cpu的系统中，它可能会产生一些问题，但是需要在实际的系统中进行测试以证明真的有问题。
在繁忙的系统中，不能指望force_quiescent_state()扫描会发生，cpu将在开始一个静止状态后，在三个jiffies内经历一次静止状态。在半繁忙的系统中，仅仅处于dynticks-idle模式的cpu需要扫描。其他情况下，例如，在一个dynticks-idle cpu扫描过程中，处理一个中断时，后继的扫描是需要的。但是，这样的扫描是分别在相应的cpu上执行的，因此相应的调度延迟仅仅影响该扫描过程所在的cpu负载。
如果扫描被证明确实有问题，一个好的方法是进行递增扫描。这将稍微增加一点代码复杂性，也增加一点结束优雅周期的时间，但是这也确实算是一个好的方案。
2.rcu_node分级在编译时创建，因此其长度是最大的cpu数量nr_cpus。但是，即使在4，096 cpu的系统中，在64位系统上，rcu_node 分级也仅仅消耗65个缓存行。(即使在32位系统上包含4，096 cpus也是这样!)。当然，在一个16 cpu的系统中，配置nr_cpus=4096将使用一个二级树，实际上在这种情况下，单节点树也会运行得很好。虽然这个配置会增加锁的负载，但是实际上不会影响经常执行的读端代码，因此事实上不会有太大的问题。
3.这个补丁会稍微增加内核代码及数据尺寸：在nr_cpus=4的系统中，从经典rcu的1，757字节内核代码、456字节数据，共2213字节的内核尺寸，而分级rcu则增加到4，006字节的内核代码、624字节的内核数据，共计4，630字节尺寸。即使对大多数嵌入式系统来说，这也不是一个问题。这些系统通常有上百兆主内存。但是对特别小的系统来说，这可能就是一个问题了，需要提供两种类型的rcu实现以满足这样的嵌入式系统。不过有一个有趣的问题，在这样的系统中，也许仅仅包含一个cpu，这样的系统完全可以用一个特别简单的rcu实现。
即使有这些问题，相对于经典rcu来说，在数百个cpu的系统中，这个分级rcu实现仍然是一个巨大的进步。最后需要说明一下，经典rcu设计用于16-32个cpu的系统。
在某些地方，在可抢占rcu实现中使用分级是有必要的。
后续章节将继续分析分级rcu的代码，以及linux中其他一些rcu的实现。也许还会讨论实现rcu这类复杂并行软件的开发方法及其形式化验证。
基于OpenAMP框架的双核ARM通信案例
精彩预告 | OpenHarmony Meetup 2023 北京站抢先剧透
认识服务器风扇
现代汽车将获得对波士顿动力的最终控制权？
热电堆红外传感器的原理和结构
分级RCU的基础知识
联想Z6Pro 5G高清图集
中国铁塔/宁德时代入局 共享换电赛道机会与暗礁
三星note8什么时候上市？三星note8最新消息：三星Note 8曝光，视觉效果很有冲击力
Microchip 宣布业界首款基于RISC-V的片上系统（SoC）FPGA开始量产
华为智慧屏售价曝光 65寸7999元
电容触控传感技术将会让手机变得更加智能
2020年工业互联网行业趋势分析
高比能量动力电池将是未来研发和产业化的重点
创新突破：精准型农业与气候不确定性
短路保护原理及电路分析
直线导轨使用中常见的问题有哪些
石油公司进军区块链领域会带来什么
身材虽小，用途强大！aigo国民好物固态U盘U393体验
淘宝直播四面楚歌，小主播该如何摆脱困境