RCU is a library that allows kernel subsystems to synchronize access to shared data in an efficient manner.

QEMU 也有自己的 RCU 实现。QEMU RCU implementation

Optimized for read-mostly situations. RCU supports concurrency between a single updater and multiple readers. 如果要用多个 updater，需要额外安排锁来进行同步（spinlock, etc.）。

参考了数据库中 MVCC (Multi-version concurrency control) 的设计思路，给 object 设定多个版本。其实相当于是一个对于读写锁（rwlock）的优化，至于为什么读锁和写锁需要互斥，之前的文章有介绍（为什么读锁和写锁要互斥？^）。

RCU 的本质是，把之前非原子性更新的问题，改成了进行原子性操作的问题。（而写者要更新一个新版本，它首先创建新的版本，然后保存旧版本的指针，然后让指针指向新版本，这个切换（指针赋值）是一个原子操作）。

我们可以把对于数据的写看作是一个很长的旅途，假设一个 object 有 100 个 porperties，需要对每一个 property 进行更新，所以耗时比较长。在过程中会有人来读，如果任凭随意读，那么读出来就是中间状态。如果上 rwlock，那么在写的过程中没有人能读，对性能不好。因此，我们设计另一个指针指向更新前的 object，在更新过程中让大家都读在这个 object 上，然后更新完直接对指针切换即可，因为指针切换（rcu_assign_pointer()）会是一个原子操作（not by nature，而是我们加了内存屏障 smp_mb()来保证其原子性，因为指针并不是一个 byte，可以原子性更新），所以不用担心。

RCU 的极其强大之处在于，它可以等待几千个不同的事情完成，而不需要显式的追踪它们。和自旋锁等不同，RCU 不用定义一个类似 spinlock_t 的变量来显式的追踪每一个 RCU 保护区。RCU 是全局的，这是由 RCU 的设计决定的，这也是 RCU 不同于其它同步机制的一个显著特点。

RCU 有以下三个基本要素：Reader/Updater/Reclaimer。

  • Reader:
    • 使用 rcu_read_lock() 和 rcu_read_unlock() 来界定读者的临界区，访问受 RCU 保护的数据时，需要始终在该临界区域内访问；
    • 在访问受保护的数据之前，需要使用 rcu_dereference() 来获取 RCU-protected 指针；
    • 当使用不可抢占的 RCU 时，rcu_read_lock/rcu_read_unlock 之间不能使用可以睡眠的代码；
    • Reader 不管读旧指针还是新指针，读就好了，为什么需要临界区？ 这是为了告诉 reclaimer 现在有 reader 在读，先延缓一下 reclaim，不然可能处理到一半发现数据被 reclaim 掉了？所以需要所有 reader 都退出之后，reclaimer 才能进行 reclaim。
  • Updater:
    • RCU 机制是面向 single updater 的，当有多个 Updater 更新数据时，需要额外的互斥机制进行保护（比如 spinlock）；
    • Updater 使用 rcu_assign_pointer() 来移除旧的指针指向，指向更新后的临界资源；
    • Updater 使用 synchronize_rcu() 或 call_rcu 来启动 Reclaimer，对旧的临界资源进行回收，其中 synchronize_rcu 表示同步等待回收，call_rcu 表示异步回收；因此，在调用 synchronize_rcu() 时，Updater 和 Reclaimer 是同一个线程；在调用 call_rcu() 时，两者仍然是同一个线程。
  • Reclaimer:
    • Reclaimer 回收旧的临界资源；
    • 为了确保没有读者正在访问要回收的临界资源，Reclaimer 需要等待所有的读者退出临界区，这个等待的时间叫做宽限期（Grace Period）；
    • 需要澄清的是 Reclaimer 需要等的是所有在其之前进入临界区（rcu_read_lock()）的 reader 要离开临界区，在 Reclaimer 等的过程中，如果有新的 Reader 进入了临界区，那么不需要等它退出，因为这个 reader 读到的已经是最新的数据了，和我们要 reclaim 的老数据并不冲突。

【原创】Linux RCU原理剖析（一）-初窥门径 - LoyenWang - 博客园

这篇文章讲的比较详细：内核RCU原理和用法 - ILD

What is RCU? -- "Read, Copy, Update" — The Linux Kernel documentation

What is RCU, Fundamentally? [LWN.net]

一个写的不错的 RCU 例子：

深入理解 Linux 的 RCU 机制 - 知乎

RCU Reclaimer

Grace period

从 Updater 调用 synchronize_rcu() 开始，到 Reclaimer 等待所有的读者退出临界区（rcu_read_unlock()）的时间叫做宽限期（Grace Period）。那是不是在 synchronize_rcu() 开始后，就不能有新的 reader 来了？新的 reader 会 block 在 rcu_read_lock()？

SRCU (Sleepable RCU)

Permits arbitrary sleeping (or blocking) within RCU read-side critical sections.

Sleepable RCU [LWN.net]

CONFIG_PROVE_RCU

This config is not configurable.

RCU Core APIs

rcu_assign_pointer(p, v)

  • @p: pointer to assign to
  • @v: value to assign (publish)

This function can be used to replace gp = p; with rcu_assign_pointer(gp, p);.

Writer 使用这个接口来更新指针，从而更新一个版本。

rcu_dereference()

rcu_assign_pointer()'s counterpart.

Reader 用这个来获取一个版本。注意，要在临界区内使用这个函数，也就是说这个函数要放在 lock 和 unlock 中间：

rcu_read_lock();
rcu_dereference();
rcu_read_unlock();

rcu_read_lock() / rcu_read_unlock() / RCU read-side critical section

It is illegal to block while in an RCU read-side critical section, though kernels built with CONFIG_PREEMPT_RCU can preempt RCU read-side critical sections.

Basically do nothing. rcu_read_lock() prevents timer interrupts from forcing a pre-emptive context switch on the current CPU, and rcu_read_unlock() enables pre-emptive context switches. This enable/disable is very cheap.

RCU 的读者虽然拥有无限的优先级，但是读者在读时仍然需要有一个关键区：RCU read-side critical sections。关键区以 rcu_read_lock() 开始，以 rcu_read_unlock() 结束。RCU 需要创建关键去是因为 RCU 需要防止关键区被抢占等（依赖于 RCU 的类型），rcu_read_lock() 的作用是关闭抢占、软中断等。RCU 的关键区可以嵌套，可以包含非常多的代码，只要代码不显式的阻塞或者睡眠。内核要根据“是否发生过切换”来判断读者是否已结束读操作。但是也有一种特殊的 RCU 叫做 SRCU，允许在 SRCU 的关键区睡眠。

总之，在进入这个关键区时（rcu_read_lock()），并不会因为别人目前拿着锁而阻塞，这个关键区的作用可能仅仅就是避免被抢占而已。

为什么在读的时候需要关闭抢占？

Any RCU-protected data structure accessed during an RCU read-side critical section is guaranteed to remain unreclaimed for the full duration of that critical section. 确保在关键区内，要读的数据没有被 reclaim 掉。因为如果被抢占从而调度出去了被 reclaim 掉了，那么回来再访问数据就没有了。只有在所有读者离开了它们的 RCU read-side critical section 之后，数据才会被 reclaim。

这么做也可能是为了支持下面这个机制：当 Updater 更新数据之后，所有的 CPU 核都发生了一次上下文切换之后（那么肯定都已经 rcu_read_unlock() 过了，不然是没法被抢占的），那么所有对旧版本的数据的访问都已结束，此时可以安全的释放旧版本的数据。但是不知道这个机制是因还是果：

  • 是为了支持这个机制，所以才让设计一个不能抢占的关键区；
  • 还是说因为关键区不能 block，推导出了这个机制，可以用来作为释放旧版本的依据。

synchronize_rcu()

Synchronize_rcu() doesn't return until all cores have gone through at least one context switch.

call_rcu()

call_rcu(f,x) returns immediately, after adding <f,x> to a list of callbacks. The callback is called after all cores have gone through at least one context switch.

Will asynchronously invokes a specified callback after all CPUs have passed through at least one context switch.