七七八八 RCU

RCU与普通锁

通常对临界区的保护会使用锁，而锁的实现通常会用到共享内存，用到共享内存那么就会存在对共享资源的访问竞争，核与核之前还会有数据一致性的问题，由于这两点的存在，系统会在性能上付出一定的代价，在大型系统上性能的regression会表现的更加明显，所以锁的可扩展性通常不会太好。这也是为什么内核中经常会有一些提交通过拆锁来降低锁粒度的优化。

RCU机制属于无锁编程的一种，在访问读端临界区时不需要加锁，故不存在上面提到的锁的问题，所以拥有极好的扩展性，且可以多个读者同时存在。那为什么不用RCU锁取代其他锁呢？前面说到读端不用加锁，但是写端是需要加锁的，用来保证写者之间的同步，这一特点限制RCU的适用场景一定是读多写少的，否则相对其他锁优势就没那么明显了。且由于读端无锁写端才需要加锁，RCU又是可以读者写者共存的，即多个读者一个写者同时存在。

RCU的思想

关于RCU，我对它的理解是它将对数据块的保护转化成了对指向数据块的指针的保护，极大的简化了对被保护资源的保护的难易程度，而对指针的保护则通过封装原子操作和各种屏障就可以确保，这样就用不到锁了。（所以RCU通常用来保护链表资源。）

当然，将对数据块的保护转化成对指向数据块的指针的保护是要付出额外的代价的，毕竟用户真正要操作的还是数据块中的数据。所以写者在update动作前，需要先copy一份数据块的副本，在副本中修改完成后，再将新的副本再重新assign到链表中替代旧的数据块。

那旧的数据块怎么办呢？当然是要回收了，那么什么时候回收呢？当然是要在没人访问它时再回收了，那怎么如何确定没人访问它了呢？当然是在宽限期(grace period)结束之后就可以确定了，那宽限期什么时候会结束呢？当然是在所有的CPU都经过一次静止态(Quiescent state)时就结束了。

RCU的分类

RCU主要的种类可分为不可抢占RCU、可抢占RCU、SRCU和RCU-tasks。其中是否可抢占是指RCU的读临界区是否可以被抢占，SRCU则是指RCU读临界区允许睡眠，前面三种RCU都是基于CPU来检测静止态，而RCU-tasks则是基于task来检测静止态的(这种rcu的出现是为了满足trampoline机制的需求，目前也只在bpf、ftrace等中被使用)。

概念澄清

宽限期(Grace period)：

普通宽限期：用户调用call_rcu()或synchronize_rcu()所开启的宽限期。

加速宽限期：用户调用synchronize_rcu_expedited()会触发一个加速宽限期或是将进行中的普通宽限期标记为一个加速宽限期。所谓加速宽限期主要的执行流程跟普通宽限期是一样的，只是会比普通宽限期多出一些QS的上报点，用来减少宽限期中不必要的延时。此接口会为系统带来一些额外的overhead，作者Paul建议少用。

静止态(Quiescent state)：

普通的QS: CPU发生进程切换，或是运行在用户态都标志着它进入了QS

Deferred QS：调用rcu_read_unlock退出最外层RCU读临界区时若抢占是关的、或软中断是关的、或中断是关的三种情况之一都会导致读端临界区被延长，致使当前CPU的QS推迟上报。被推迟的QS会在读临界区以外的中断、软中断、进程切换中被上报。举例：若unlock时抢占是关的，在抢占开之前再次进入另一个临界区，那QS的上报将在退出第二个读临界区以后开抢占之后。deferred QS的提出是为了解决scheduler中的一个死锁问题。

Tick中断：

Tick中断即我们熟悉的周期性调度器。它的中断处理程序不仅包含任务调度、定时器、时间管理等相关操作，也包含了RCU的部分任务，由于位于中断处理程序中，而中断处理程序通常被要求耗时短，所以这里只是主要的工作是检查是否存在待处理的事情(例如：需要上报QS、Callback过载)，有的话则唤醒RCU软中断进行实质性的工作。

我们熟知的CPU stall的检查也是在tick中断中进行的，检测中若发现宽限期在规定的时间内(默认是21秒)未结束，则会打出cpu stall的警告，以各个cpu的QS情况。

RCU软中断：

Linux系统专门为RCU留了一个名为RCU_SOFTIRQ的软中断，并在系统启动阶段通过rcu_init()为它注册对应的回调函数rcu_core_si()。RCU软中断主要有两个大的作用：

1. 处理本CPU上已经进入DONE状态的callback

2. 检测并更新本CPU的gp编号；检测并上报本CPU的静止态；若有需要则唤醒gp线程。

小知识点：1. RCU_SOFTIRQ软中断是所有软中断中优先级最低的。2. 在RT-Linux中并未使用软中断，而是为每个CPU都注册了一个rcu_cpu_kthread线程作为替代。

GP内核线程：

这里所谓的gp线程即rcu_gp_kthread()，主要功能是处理宽限期相关的事务，包括：开启新的宽限期、处理forcing QS、清理已结束的宽限期。

此线程的名字保存在rcu_state->name中，可抢占RCU命名是rcu_preempt；不可抢占RCU的命名是rcu_sched。我们可以通过ps -aux看到。

GP原理

读侧临界部分RCS(Read-Side Critical Section): 保护禁止其他CPU修改的代码区域，但允许多个CPU同时读；

三个主要的角色

读者reader：

安全访问临界区资源；负责标识进出临界区；

写者updater：

复制一份数据，然后更新数据；用新数据覆盖旧数据，然后进入grace period；

回收者reclaimer：

等待在grace period之前的读者退出临界区；在宽限期结束后，负责回收旧资源；

三个重要机制

发布/订阅机制

主要用于更新数据，即使在数据被同时修改时线程也能安全浏览数据。RCU通过发布-订阅机制（Publish-Subscribe Mechanism）实现这种并发的插入操作能力；

延迟回收机制：

实现检查旧数据上所有RCU读者完成，用于安全删除旧数据；

多版本机制：

维护最近更新对象的多个版本，用于允许读者容忍并发的插入和删除新对象的多个版本；

RCU锁的核心思想：

• 读者无锁访问数据，标记进出临界区；
• 写者读取，复制，更新；
• 旧数据延迟回收；

RCU write

synchronize_rcu(）

写者可以使用下面4个函数。

（1）使用函数synchronize_rcu()等待宽限期结束，即所有读者退出读端临界区，然后写者执行下一步操作。这个函数可能睡眠。

（2）使用函数synchronize_rcu_expedited()等待宽限期结束。和函数synchronize_rcu()的区别是：该函数会向其他处理器发送处理器间中断（Inter-Processor Interrupt，IPI）请求，强制宽限期快速结束。我们把强制快速结束的宽限期称为加速宽限期（expedited grace period），把没有强制快速结束的宽限期称为正常宽限期（normal grace period）。

（3）使用函数call_rcu()注册延后执行的回调函数，把回调函数添加到RCU回调函数链表中，立即返回，不会阻塞。函数原型如下：

void call_rcu(struct rcu_head *head, rcu_callback_t func);

struct callback_head {

struct callback_head *next;

void (*func)(struct callback_head *head);

} __attribute__((aligned(sizeof(void *))));

#define rcu_head callback_head

typedef void (*rcu_callback_t)(struct rcu_head *head);

（4）使用函数rcu_barrier()等待使用call_rcu注册的所有回调函数执行完。这个函数可能睡眠。

一次完整的rcu同步需要cpu发起一次gp, 等待所有cpu经历一次gp后再完成本次gp的清理工作. 具体到rcu线程, 首先rcu_gp_kthread()会一直睡眠直到被rsp->gp_flags置位RCU_GP_FLAG_INIT才被唤醒, 该标志位被认为是发起一次gp的标记.被唤醒后调用rcu_gp_init()执行gp的初始化, 若初始化失败则请求调度. 如成功发起一次gp则开始睡眠等待本次gp完成. 该睡眠仅在三种情况下唤醒, 所有cpu都经历一次完整的gp(rnp->qsmask为0), cpu请求fqs(rsp->gp_flags & RCU_GP_FLAG_FQS)或超时. 第一种情况执行完成gp后的清理工作, 第二种情况执行fqs, 最后一种情况修改到期时间后继续睡眠等待

State Machine

The common-case path through this state machine on a busy system goes through the two uppermost loops, initializing at the beginning of each grace period (GP), waiting for quiescent states (QS), and noting when each CPU passes through its first quiescent state for a given grace period. On such a system, quiescent states will occur on each context switch, or, for CPUs that are either idle or executing user-mode code, each scheduling-clock interrupt. CPU-hotplug events will take the state machine through the “CPU Offline” box, while the presence of “holdout” CPUs that fail to pass through quiescent states quickly enough will exercise the path through the “Send resched IPIs to Holdout CPUs” box. RCU implementations that avoid unnecessarily awakening dyntick-idle CPUs will mark those CPUs as being in an extended quiescent state, taking the “Y” branch out of the “CPUs in dyntick-idle Mode?” decision diamond (but note that CPUs in dyntick-idle mode will notbe sent resched IPIs). Finally, if CONFIG_RCU_CPU_STALL_DETECTOR is enabled, truly excessive delays in reaching quiescent states will exercise the “Complain About Holdout CPUs” path.

The events in the above state schematic interact with different data structures, as shown below:

However, the state schematic does not directly translate into C code for any of the RCU implementations. Instead, these implementations are coded as an event-driven system within the kernel. Therefore, the following section describes some “use cases”, or ways in which the RCU algorithm traverses the above state schematic as well as the relevant data structures.

RCUC Thread

Per CPU 一个线程。用来处理本CPU上的CPU RCU 相关。包括 GS 上报，开始结束/callback

/sys/module/rcutree/parameters/blimit 10

/sys/module/rcutree/parameters/rcu_divisor 7

·Rcuc call flow

rcu_preempt

整个系统一个线程。可运行在所有的CPU 上。完成一个gp生命周期的管理包括 init/boost rcu thread/FQS/GP end 上报jiffies_till_first_fqs=1 jiffies_till_next_fqs=1 jiffies_till_sched_qs=max （/sys/module/rcutree/parameters）

· rcu_state

· rcu_gp_kthread flow

· Rcu ftrace

rcub 一个rcu_node 一个可以运行在所有的CPU 上

该线程是临时boost 需要该rcu_node上的exp_tasks 或boost_tasks，主要是通过rt_mutex_lock 能进行优先级继承来完成（rcu_boost_kthread->rcu_boost(rnp))

RCU stall check