什么是 RCU？ -- “读取、复制、更新”¶
请注意，“什么是 RCU？” LWN 系列是开始学习 RCU 的绝佳起点
对于那些喜欢视频的人
什么是 RCU？
RCU 是一种同步机制，在 2.5 开发工作中添加到 Linux 内核中，专门为读取较多的情况进行了优化。 虽然 RCU 实际上非常简单，但有效使用它需要您以不同的方式思考您的代码。 问题的另一部分是错误地假设描述和使用 RCU 存在“一种真正的方法”。 相反，经验表明，不同的人必须采取不同的路径才能理解 RCU，这取决于他们的经验和用例。 本文档提供了几种不同的路径，如下所示
喜欢从概念概述开始的人应该关注第 1 节，尽管大多数读者在某个时候阅读本节都会有所收获。 喜欢从可以实验的 API 开始的人应该关注第 2 节。 喜欢从示例用法开始的人应该关注第 3 节和第 4 节。 需要了解 RCU 实现的人应该关注第 5 节，然后深入研究内核源代码。 擅长类比推理的人应该关注第 6 节和第 7 节。第 8 节充当 docbook API 文档的索引，第 9 节是传统的答案密钥。
因此，从对您和您喜欢的学习方法最有意义的部分开始。 如果您需要了解一切，请随意阅读全文——但如果您真的是那种人，您就已经仔细阅读了源代码，因此无论如何都不需要本文档。 ;-)
1. RCU 概述¶
RCU 背后的基本思想是将更新分为“删除”和“回收”阶段。 删除阶段删除数据结构中对数据项的引用（可能通过将它们替换为对这些数据项的新版本的引用），并且可以与读取器同时运行。 与读取器同时运行删除阶段是安全的，原因是现代 CPU 的语义保证读取器将看到数据结构的旧版本或新版本，而不是部分更新的引用。 回收阶段完成回收（例如，释放）在删除阶段从数据结构中删除的数据项的工作。 因为回收数据项可能会中断同时引用这些数据项的任何读取器，所以回收阶段必须在读取器不再持有对这些数据项的引用之后才能开始。
将更新分为删除和回收阶段允许更新器立即执行删除阶段，并将回收阶段推迟到在删除阶段处于活动状态的所有读取器完成之后，可以通过阻塞直到它们完成或通过注册在它们完成后调用的回调来完成。 只需要考虑在删除阶段处于活动状态的读取器，因为在删除阶段之后启动的任何读取器都无法获得对已删除数据项的引用，因此不会被回收阶段中断。
因此，典型的 RCU 更新序列如下
删除指向数据结构的指针，以便后续读取器无法获得对其的引用。
等待所有先前的读取器完成其 RCU 读取端临界区。
此时，不能有任何读取器持有对数据结构的引用，因此现在可以安全地回收它（例如，
kfree()d）。
上面的步骤 (b) 是 RCU 延迟销毁的基础关键思想。 等待直到所有读取器完成的能力允许 RCU 读取器使用更轻量级的同步，在某些情况下，根本不需要同步。 相比之下，在更传统的基于锁的方案中，读取器必须使用重量级同步，以防止更新器在它们不知情的情况下删除数据结构。 这是因为基于锁的更新器通常就地更新数据项，因此必须排除读取器。 相比之下，基于 RCU 的更新器通常会利用以下事实：对单个对齐指针的写入在现代 CPU 上是原子的，允许原子插入、删除和替换链接结构中的数据项，而不会中断读取器。 并发的 RCU 读取器可以继续访问旧版本，并且可以避免原子操作、内存屏障和通信缓存未命中，即使在没有锁竞争的情况下，这些操作在当今的 SMP 计算机系统中也非常昂贵。
在上面显示的三步过程中，更新器正在执行删除和回收步骤，但是通常由一个完全不同的线程来执行回收，就像 Linux 内核的目录条目缓存 (dcache) 中的情况一样。 即使同一个线程执行更新步骤（上面的步骤 (a)）和回收步骤（上面的步骤 (c)），将它们分开考虑通常也很有帮助。 例如，RCU 读取器和更新器不需要进行任何通信，但 RCU 在读取器和回收器之间提供隐式的低开销通信，即在上面的步骤 (b) 中。
那么，鉴于读取器没有执行任何类型的同步操作，回收器到底如何判断读取器何时完成呢？ 继续阅读以了解 RCU 的 API 如何使这变得容易。
2. RCU 的核心 API 是什么？¶
核心 RCU API 非常小
RCU API 还有许多其他成员，但其余成员可以用这五个来表示，尽管大多数实现而是用 call_rcu() 回调 API 来表示 synchronize_rcu()。
下面描述了五个核心 RCU API，其余 18 个将在后面枚举。 有关更多信息，请参阅内核 docbook 文档，或直接查看函数头注释。
rcu_read_lock()¶
void rcu_read_lock(void);
读取器使用此时间原语来通知回收器该读取器正在进入 RCU 读取端临界区。 在 RCU 读取端临界区中阻塞是非法的，尽管使用 CONFIG_PREEMPT_RCU 构建的内核可以抢占 RCU 读取端临界区。 在 RCU 读取端临界区期间访问的任何受 RCU 保护的数据结构都保证在该临界区的整个持续时间内保持未回收。 引用计数可以与 RCU 结合使用，以维护对数据结构的长期引用。
请注意，任何禁用 bottom halves、抢占或中断的操作也会进入 RCU 读取端临界区。 获取自旋锁也会进入 RCU 读取端临界区，即使对于不禁用抢占的自旋锁也是如此，如使用 CONFIG_PREEMPT_RT=y 构建的内核中的情况。 Sleeplocks *不*进入 RCU 读取端临界区。
rcu_read_unlock()¶
void rcu_read_unlock(void);
读取器使用此时间原语来通知回收器该读取器正在退出 RCU 读取端临界区。 任何启用 bottom halves、抢占或中断的操作也会退出 RCU 读取端临界区。 释放自旋锁也会退出 RCU 读取端临界区。
请注意，RCU 读取端临界区可以嵌套和/或重叠。
synchronize_rcu()¶
void synchronize_rcu(void);
此时间原语标记更新器代码的结尾和回收器代码的开始。 它通过阻塞直到所有 CPU 上所有先前存在的 RCU 读取端临界区都已完成来实现此目的。 请注意，
synchronize_rcu()*不*一定等待任何后续的 RCU 读取端临界区完成。 例如，考虑以下事件序列CPU 0 CPU 1 CPU 2 ----------------- ------------------------- --------------- 1. rcu_read_lock() 2. enters synchronize_rcu() 3. rcu_read_lock() 4. rcu_read_unlock() 5. exits synchronize_rcu() 6. rcu_read_unlock()重申一下，
synchronize_rcu()仅等待正在进行的 RCU 读取端临界区完成，不一定等待在调用synchronize_rcu()之后开始的任何临界区。当然，
synchronize_rcu()不一定在最后一个先前存在的 RCU 读取端临界区完成后*立即*返回。 一方面，可能会有调度延迟。 另一方面，许多 RCU 实现会批量处理请求以提高效率，这可能会进一步延迟synchronize_rcu()。由于
synchronize_rcu()是必须确定读取器何时完成的 API，因此其实现是 RCU 的关键。 为了使 RCU 在除了读取密集型情况之外的所有情况中都有用，synchronize_rcu()的开销也必须非常小。
call_rcu()API 是synchronize_rcu()的异步回调形式，并在后面的章节中更详细地描述。 它不是阻塞，而是注册一个函数和参数，在所有正在进行的 RCU 读取端临界区完成后调用。 这种回调变体在无法阻塞或更新端性能至关重要的情况下特别有用。但是，不应轻易使用
call_rcu()API，因为使用synchronize_rcu()API 通常会导致更简单的代码。 此外，synchronize_rcu()API 具有自动限制更新速率的良好特性，以防宽限期延迟。 面对拒绝服务攻击，此属性会产生系统弹性。 使用call_rcu()的代码应限制更新速率，以便获得相同类型的弹性。 请参阅 RCU 补丁的审核清单，了解限制更新速率的一些方法。
rcu_assign_pointer()¶
void rcu_assign_pointer(p, typeof(p) v);
是的，
rcu_assign_pointer()*是*作为宏实现的，尽管能够以这种方式声明函数会很酷。 （并且已经有一些关于向 C 语言添加重载函数的讨论，所以谁知道呢？）更新器使用此空间宏为受 RCU 保护的指针分配一个新值，以便安全地将值的更改从更新器传达给读取器。 这是一个空间（而不是时间）宏。 它不会评估为 rvalue，但它确实提供了给定编译或 CPU 架构所需的任何编译器指令和内存屏障指令。 它的排序属性是存储-释放操作，也就是说，初始化结构所需的任何先前的加载和存储操作都在存储操作之前排序，该存储操作发布指向该结构的指针。
也许同样重要的是，
rcu_assign_pointer()用于记录 (1) 哪些指针受 RCU 保护，以及 (2) 给定结构变得可供其他 CPU 访问的点。 也就是说，rcu_assign_pointer()最常间接使用，通过 _rcu 列表操作原语，例如list_add_rcu()。
rcu_dereference()¶
typeof(p) rcu_dereference(p);
与
rcu_assign_pointer()一样，rcu_dereference()必须作为宏实现。读取器使用空间
rcu_dereference()宏来获取受 RCU 保护的指针，该指针返回一个可以安全地取消引用的值。 请注意，rcu_dereference()实际上并不取消引用指针，而是保护指针以供以后取消引用。 它还执行给定 CPU 架构所需的任何内存屏障指令。 目前，只有 Alpha 需要在rcu_dereference()中使用内存屏障——在其他 CPU 上，它会编译为易失性加载。 但是，没有主流的 C 编译器尊重地址依赖性，因此rcu_dereference()使用易失性转换，结合 正确处理来自 rcu_dereference() 的返回值 中列出的编码指南，可以防止当前的编译器破坏这些依赖性。常见的编码实践使用
rcu_dereference()将受 RCU 保护的指针复制到局部变量，然后取消引用此局部变量，例如，如下所示p = rcu_dereference(head.next); return p->data;但是，在这种情况下，人们可以很容易地将这些组合成一个语句
return rcu_dereference(head.next)->data;如果要从受 RCU 保护的结构中获取多个字段，则当然首选使用局部变量。 重复的
rcu_dereference()调用看起来很丑陋，不能保证如果在临界区中发生更新会返回相同的指针，并且会在 Alpha CPU 上产生不必要的开销。请注意，
rcu_dereference()返回的值仅在封闭的 RCU 读取端临界区中有效 [1]。 例如，以下代码 *不是*合法的rcu_read_lock(); p = rcu_dereference(head.next); rcu_read_unlock(); x = p->address; /* BUG!!! */ rcu_read_lock(); y = p->data; /* BUG!!! */ rcu_read_unlock();将一个 RCU 读取端临界区的引用保持到另一个临界区是非法的，就像将一个基于锁的临界区的引用保持到另一个临界区一样！ 同样，在获取引用的临界区之外使用引用也是非法的，就像使用普通锁一样。
与
rcu_assign_pointer()一样，rcu_dereference()的一个重要功能是记录哪些指针受 RCU 保护，特别是标记一个随时可能更改的指针，包括在rcu_dereference()之后立即更改。 并且，与rcu_assign_pointer()再次一样，rcu_dereference()通常是间接使用，通过 _rcu 列表操作原语，例如list_for_each_entry_rcu()[2]。
下图显示了每个 API 在读取器、更新器和回收器之间的通信方式。
rcu_assign_pointer()
+--------+
+---------------------->| reader |---------+
| +--------+ |
| | |
| | | Protect:
| | | rcu_read_lock()
| | | rcu_read_unlock()
| rcu_dereference() | |
+---------+ | |
| updater |<----------------+ |
+---------+ V
| +-----------+
+----------------------------------->| reclaimer |
+-----------+
Defer:
synchronize_rcu() & call_rcu()
RCU 基础设施观察 rcu_read_lock()、 rcu_read_unlock()、 synchronize_rcu() 和 call_rcu() 调用的时间顺序，以确定何时 (1) synchronize_rcu() 调用可以返回给调用者，以及 (2) 何时可以调用 call_rcu() 回调。 RCU 基础设施的高效实现大量使用批处理，以便分摊其在相应 API 的多次使用中的开销。 rcu_assign_pointer() 和 rcu_dereference() 调用通过对 RCU 保护指针的存储和加载来传达空间变化。
在 Linux 内核中至少有三种 RCU 用法。 上图显示了最常见的用法。 在更新端，rcu_assign_pointer()、synchronize_rcu() 和 call_rcu() 原语对于所有三种用法都是相同的。 然而，对于保护（在读取端），所使用的原语因用法而异。
rcu_read_lock_bh()/rcu_read_unlock_bh()local_bh_disable() / local_bh_enable()rcu_dereference_bh()rcu_read_lock_sched()/rcu_read_unlock_sched()preempt_disable() / preempt_enable() local_irq_save() / local_irq_restore() hardirq enter / hardirq exit NMI enter / NMI exitrcu_dereference_sched()
这三种用法的使用方式如下：
RCU 应用于正常数据结构。
RCU 应用于可能受到远程拒绝服务攻击的网络数据结构。
RCU 应用于调度器和中断/NMI 处理程序任务。
同样，大多数使用情况将是 (a)。 (b) 和 (c) 的情况对于专门用途非常重要，但相对不常见。 SRCU、RCU-Tasks、RCU-Tasks-Rude 和 RCU-Tasks-Trace 在其各种原语之间具有类似的关系。
3. 核心 RCU API 的一些示例用法是什么？¶
本节展示了核心 RCU API 的一个简单用法，以保护指向动态分配结构的全局指针。 可以在 使用 RCU 保护读多写少链表 和 使用 RCU 保护动态 NMI 处理程序 中找到更典型的 RCU 用法。
struct foo {
int a;
char b;
long c;
};
DEFINE_SPINLOCK(foo_mutex);
struct foo __rcu *gbl_foo;
/*
* Create a new struct foo that is the same as the one currently
* pointed to by gbl_foo, except that field "a" is replaced
* with "new_a". Points gbl_foo to the new structure, and
* frees up the old structure after a grace period.
*
* Uses rcu_assign_pointer() to ensure that concurrent readers
* see the initialized version of the new structure.
*
* Uses synchronize_rcu() to ensure that any readers that might
* have references to the old structure complete before freeing
* the old structure.
*/
void foo_update_a(int new_a)
{
struct foo *new_fp;
struct foo *old_fp;
new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
spin_lock(&foo_mutex);
old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
*new_fp = *old_fp;
new_fp->a = new_a;
rcu_assign_pointer(gbl_foo, new_fp);
spin_unlock(&foo_mutex);
synchronize_rcu();
kfree(old_fp);
}
/*
* Return the value of field "a" of the current gbl_foo
* structure. Use rcu_read_lock() and rcu_read_unlock()
* to ensure that the structure does not get deleted out
* from under us, and use rcu_dereference() to ensure that
* we see the initialized version of the structure (important
* for DEC Alpha and for people reading the code).
*/
int foo_get_a(void)
{
int retval;
rcu_read_lock();
retval = rcu_dereference(gbl_foo)->a;
rcu_read_unlock();
return retval;
}
所以，总结一下：
使用
rcu_read_lock()和rcu_read_unlock()来保护 RCU 读取端临界区。在 RCU 读取端临界区内，使用
rcu_dereference()来解引用受 RCU 保护的指针。使用一些可靠的设计（例如锁或信号量）来防止并发更新相互干扰。
使用
rcu_assign_pointer()来更新受 RCU 保护的指针。 此原语保护并发读取器免受更新器的影响，**而不是**并发更新免受彼此的影响！ 因此，您仍然需要使用锁（或类似的东西）来防止并发的rcu_assign_pointer()原语相互干扰。在从受 RCU 保护的数据结构中删除数据元素**之后**，但在回收/释放数据元素**之前**，使用
synchronize_rcu()，以便等待可能引用该数据项的所有 RCU 读取端临界区完成。
有关使用 RCU 时要遵循的其他规则，请参见 RCU 补丁的审核清单。 再次，可以在 使用 RCU 保护读多写少链表 和 使用 RCU 保护动态 NMI 处理程序 中找到更典型的 RCU 用法。
4. 如果我的更新线程无法阻塞怎么办？¶
在上面的示例中，foo_update_a() 阻塞直到宽限期过去。 这很简单，但在某些情况下，您无法承受等待这么长时间 -- 可能还有其他高优先级的工作要做。
在这种情况下，您使用 call_rcu() 而不是 synchronize_rcu()。call_rcu() API 如下：
void call_rcu(struct rcu_head *head, rcu_callback_t func);
此函数在宽限期过去后调用 func(head)。 此调用可能来自软中断或进程上下文，因此不允许该函数阻塞。 foo 结构需要添加一个 rcu_head 结构，可能如下所示：
struct foo {
int a;
char b;
long c;
struct rcu_head rcu;
};
然后可以将 foo_update_a() 函数编写如下：
/*
* Create a new struct foo that is the same as the one currently
* pointed to by gbl_foo, except that field "a" is replaced
* with "new_a". Points gbl_foo to the new structure, and
* frees up the old structure after a grace period.
*
* Uses rcu_assign_pointer() to ensure that concurrent readers
* see the initialized version of the new structure.
*
* Uses call_rcu() to ensure that any readers that might have
* references to the old structure complete before freeing the
* old structure.
*/
void foo_update_a(int new_a)
{
struct foo *new_fp;
struct foo *old_fp;
new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
spin_lock(&foo_mutex);
old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
*new_fp = *old_fp;
new_fp->a = new_a;
rcu_assign_pointer(gbl_foo, new_fp);
spin_unlock(&foo_mutex);
call_rcu(&old_fp->rcu, foo_reclaim);
}
foo_reclaim() 函数可能如下所示：
void foo_reclaim(struct rcu_head *rp)
{
struct foo *fp = container_of(rp, struct foo, rcu);
foo_cleanup(fp->a);
kfree(fp);
}
container_of() 原语是一个宏，给定一个指向结构体的指针、结构体的类型以及结构体中指向的字段，返回一个指向结构体开头的指针。
使用 call_rcu() 允许 foo_update_a() 的调用者立即重新获得控制权，而无需进一步担心新更新元素的旧版本。 它还清楚地显示了 RCU 在更新器（即 foo_update_a()）和回收器（即 foo_reclaim()）之间的区别。
建议的摘要与上一节相同，只是我们现在使用 call_rcu() 而不是 synchronize_rcu()。
在从受 RCU 保护的数据结构中删除数据元素**之后**，使用
call_rcu()来注册一个回调函数，该函数将在可能引用该数据项的所有 RCU 读取端临界区完成后调用。
如果 call_rcu() 的回调除了在结构体上调用 kfree() 之外什么都不做，则可以使用 kfree_rcu() 而不是 call_rcu()，以避免必须编写您自己的回调。
kfree_rcu(old_fp, rcu);
如果允许偶尔睡眠，则可以使用单参数形式，从 foo 结构体中省略 rcu_head 结构体。
kfree_rcu_mightsleep(old_fp);
此变体几乎从不阻塞，但可能会通过调用 synchronize_rcu() 来响应内存分配失败。
再次，有关管理 RCU 使用的其他规则，请参见 RCU 补丁的审核清单。
5. RCU 的一些简单实现是什么？¶
关于 RCU 的一件好事是，它具有非常简单的“玩具”实现，这是理解 Linux 内核中生产质量实现的第一步。 本节介绍了 RCU 的两个此类“玩具”实现，一个是用熟悉的锁定原语实现的，另一个更类似于“经典” RCU。 两者都过于简单，无法在现实世界中使用，既缺乏功能又缺乏性能。 但是，它们有助于了解 RCU 的工作原理。 有关生产质量的实现，请参见 kernel/rcu/update.c，并参见
有关描述 Linux 内核 RCU 实现的论文。 OLS'01 和 OLS'02 论文是一个很好的介绍，而论文提供了有关截至 2004 年初的当前实现的更多详细信息。
5A. “玩具”实现 #1：锁定¶
本节介绍了一个基于熟悉的锁定原语的“玩具” RCU 实现。 它的开销使其无法用于实际用途，它的可伸缩性也是如此。 它也不适合实时使用，因为它允许调度延迟从一个读取端临界区“泄漏”到另一个读取端临界区。 它还假设递归读者-写者锁：如果您尝试使用非递归锁，并且允许嵌套的 rcu_read_lock() 调用，则可能会发生死锁。
但是，它可能是最容易理解的实现，因此是一个很好的起点。
它非常简单
static DEFINE_RWLOCK(rcu_gp_mutex);
void rcu_read_lock(void)
{
read_lock(&rcu_gp_mutex);
}
void rcu_read_unlock(void)
{
read_unlock(&rcu_gp_mutex);
}
void synchronize_rcu(void)
{
write_lock(&rcu_gp_mutex);
smp_mb__after_spinlock();
write_unlock(&rcu_gp_mutex);
}
[您可以忽略 rcu_assign_pointer() 和 rcu_dereference() 而不会错过太多。 但无论如何，这里有一些简化的版本。 无论您做什么，在提交使用 RCU 的补丁时都不要忘记它们！]
#define rcu_assign_pointer(p, v) \
({ \
smp_store_release(&(p), (v)); \
})
#define rcu_dereference(p) \
({ \
typeof(p) _________p1 = READ_ONCE(p); \
(_________p1); \
})
rcu_read_lock() 和 rcu_read_unlock() 原语读取获取和释放全局读者-写者锁。synchronize_rcu() 原语写入获取此相同的锁，然后释放它。 这意味着一旦 synchronize_rcu() 退出，保证在调用 synchronize_rcu() 之前正在进行的所有 RCU 读取端临界区都已完成 -- synchronize_rcu() 无法以其他方式写入获取锁。 smp_mb__after_spinlock() 按照“内存屏障保证”中的列出的，将 synchronize_rcu() 提升为完整的内存屏障。
可以嵌套 rcu_read_lock()，因为读者-写者锁可以递归获取。 还要注意，rcu_read_lock() 不受死锁影响（RCU 的一个重要属性）。 原因是唯一可以阻塞 rcu_read_lock() 的是 synchronize_rcu()。 但是 synchronize_rcu() 在保持 rcu_gp_mutex 时不获取任何锁，因此不会有死锁循环。
- 快速测验 #1
为什么这个论点很天真？ 在现实世界的 Linux 内核中使用此算法时，如何发生死锁？ 如何避免这种死锁？
5B. “玩具”示例 #2：经典 RCU¶
本节介绍了一个基于“经典 RCU”的“玩具” RCU 实现。 它也缺乏性能（但仅对于更新）以及诸如热插拔 CPU 和在 CONFIG_PREEMPTION 内核中运行的能力等功能。rcu_dereference() 和 rcu_assign_pointer() 的定义与上一节中显示的定义相同，因此省略了它们。
void rcu_read_lock(void) { }
void rcu_read_unlock(void) { }
void synchronize_rcu(void)
{
int cpu;
for_each_possible_cpu(cpu)
run_on(cpu);
}
请注意，rcu_read_lock() 和 rcu_read_unlock() 绝对不执行任何操作。 这是非抢占内核中经典 RCU 的巨大优势：读取端开销恰好为零，至少在非 Alpha CPU 上是这样。 并且 rcu_read_lock() 绝对不可能参与死锁循环！
synchronize_rcu() 的实现只是依次在每个 CPU 上调度自身。 run_on() 原语可以使用 sched_setaffinity() 原语直接实现。 当然，一个稍微不那么“玩具”的实现会在完成后恢复亲和性，而不仅仅是将所有任务留在最后一个 CPU 上运行，但是当我说“玩具”时，我的意思是 **玩具**！
那么这到底应该如何工作？？？
请记住，在 RCU 读取端临界区中阻塞是非法的。 因此，如果给定的 CPU 执行上下文切换，我们知道它必须已完成所有先前的 RCU 读取端临界区。 一旦 **所有** CPU 都执行了上下文切换，那么 **所有** 先前的 RCU 读取端临界区都将完成。
因此，假设我们从其结构中删除一个数据项，然后调用 synchronize_rcu()。 一旦 synchronize_rcu() 返回，我们保证没有 RCU 读取端临界区持有对该数据项的引用，因此我们可以安全地回收它。
- 快速测验 #2
给出一个经典 RCU 的读取端开销为 **负数** 的示例。
- 快速测验 #3
如果在 RCU 读取端临界区中阻塞是非法的，那么在 CONFIG_PREEMPT_RT 中该怎么做呢？在 CONFIG_PREEMPT_RT 中，正常的自旋锁可能会阻塞！！！
6. 与读者-写者锁的类比¶
虽然 RCU 可以以许多不同的方式使用，但 RCU 的一个非常常见的用法类似于读者-写者锁。 以下统一差异显示了 RCU 和读者-写者锁之间的密切关系。
@@ -5,5 +5,5 @@ struct el {
int data;
/* Other data fields */
};
-rwlock_t listmutex;
+spinlock_t listmutex;
struct el head;
@@ -13,15 +14,15 @@
struct list_head *lp;
struct el *p;
- read_lock(&listmutex);
- list_for_each_entry(p, head, lp) {
+ rcu_read_lock();
+ list_for_each_entry_rcu(p, head, lp) {
if (p->key == key) {
*result = p->data;
- read_unlock(&listmutex);
+ rcu_read_unlock();
return 1;
}
}
- read_unlock(&listmutex);
+ rcu_read_unlock();
return 0;
}
@@ -29,15 +30,16 @@
{
struct el *p;
- write_lock(&listmutex);
+ spin_lock(&listmutex);
list_for_each_entry(p, head, lp) {
if (p->key == key) {
- list_del(&p->list);
- write_unlock(&listmutex);
+ list_del_rcu(&p->list);
+ spin_unlock(&listmutex);
+ synchronize_rcu();
kfree(p);
return 1;
}
}
- write_unlock(&listmutex);
+ spin_unlock(&listmutex);
return 0;
}
或者，对于那些喜欢并排列表的人：
1 struct el { 1 struct el {
2 struct list_head list; 2 struct list_head list;
3 long key; 3 long key;
4 spinlock_t mutex; 4 spinlock_t mutex;
5 int data; 5 int data;
6 /* Other data fields */ 6 /* Other data fields */
7 }; 7 };
8 rwlock_t listmutex; 8 spinlock_t listmutex;
9 struct el head; 9 struct el head;
1 int search(long key, int *result) 1 int search(long key, int *result)
2 { 2 {
3 struct list_head *lp; 3 struct list_head *lp;
4 struct el *p; 4 struct el *p;
5 5
6 read_lock(&listmutex); 6 rcu_read_lock();
7 list_for_each_entry(p, head, lp) { 7 list_for_each_entry_rcu(p, head, lp) {
8 if (p->key == key) { 8 if (p->key == key) {
9 *result = p->data; 9 *result = p->data;
10 read_unlock(&listmutex); 10 rcu_read_unlock();
11 return 1; 11 return 1;
12 } 12 }
13 } 13 }
14 read_unlock(&listmutex); 14 rcu_read_unlock();
15 return 0; 15 return 0;
16 } 16 }
1 int delete(long key) 1 int delete(long key)
2 { 2 {
3 struct el *p; 3 struct el *p;
4 4
5 write_lock(&listmutex); 5 spin_lock(&listmutex);
6 list_for_each_entry(p, head, lp) { 6 list_for_each_entry(p, head, lp) {
7 if (p->key == key) { 7 if (p->key == key) {
8 list_del(&p->list); 8 list_del_rcu(&p->list);
9 write_unlock(&listmutex); 9 spin_unlock(&listmutex);
10 synchronize_rcu();
10 kfree(p); 11 kfree(p);
11 return 1; 12 return 1;
12 } 13 }
13 } 14 }
14 write_unlock(&listmutex); 15 spin_unlock(&listmutex);
15 return 0; 16 return 0;
16 } 17 }
无论哪种方式，差异都很小。 读取端锁定移动到 rcu_read_lock() 和 rcu_read_unlock，更新端锁定从读者-写者锁移动到简单的自旋锁，并且 synchronize_rcu() 先于 kfree()。
但是，有一个潜在的问题：读取端和更新端临界区现在可以并发运行。 在许多情况下，这不会成为问题，但无论如何都需要仔细检查。 例如，如果必须将多个独立的列表更新视为单个原子更新，则转换为 RCU 将需要特别小心。
此外，synchronize_rcu() 的存在意味着 delete() 的 RCU 版本现在可以阻塞。 如果这是一个问题，则有一种基于回调的机制永远不会阻塞，即 call_rcu() 或 kfree_rcu()，可以用来代替 synchronize_rcu()。
7. 与引用计数的类比¶
读者-写者类比（如上一节所示）并非总是考虑使用 RCU 的最佳方式。 另一个有用的类比是将 RCU 视为对受 RCU 保护的所有内容进行有效引用计数。
引用计数通常不会阻止被引用对象的值发生变化，但会阻止类型发生变化 -- 特别是当该对象的内存被释放并为其他目的重新分配时发生的类型上的重大变化。 一旦获得了对对象的类型安全引用，就需要一些其他机制来确保对对象中数据的一致访问。 这可能涉及获取自旋锁，但使用 RCU，典型的方法是使用感知 SMP 的操作（例如 smp_load_acquire()）执行读取，使用原子读取-修改-写入操作执行更新，并提供必要的排序。 RCU 提供了许多支持函数，这些函数嵌入了所需的操作和排序，例如上一节中使用的 list_for_each_entry_rcu() 宏。
更聚焦于引用计数行为的观点是，在 rcu_read_lock() 和 rcu_read_unlock() 之间，通过 rcu_dereference() 获取的对标记为 __rcu 的指针的任何引用，都可以被视为该对象的引用计数已暂时增加。 这可以防止对象更改类型。 这到底意味着什么将取决于该类型对象的正常预期，但通常包括自旋锁仍然可以安全地锁定，正常引用计数器可以安全地操作，并且 __rcu 指针可以安全地解引用。
对持有 RCU 引用的对象，一些预期会执行的操作包括：
复制出保证由对象类型保证稳定的数据。
使用
kref_get_unless_zero()或类似方法获取更长期的引用。当然，这可能会失败。获取对象中的自旋锁，并检查该对象是否仍然是预期的对象，如果是，则可以自由地操作它。
理解 RCU 提供的引用仅阻止类型更改这一点，在使用标记为 SLAB_TYPESAFE_BY_RCU 的 slab 缓存分配的对象时尤其明显。 RCU 操作可能会产生对来自此类缓存的对象的引用，该对象已被并发释放，并且内存已重新分配给一个完全不同的对象，尽管类型相同。 在这种情况下，RCU 甚至不能保护对象身份不发生改变，只能保护其类型。 因此，找到的对象可能不是预期的对象，但它是一个可以安全地获取引用（然后可能获取自旋锁）的对象，从而允许后续代码检查身份是否符合预期。 很容易在不先获取引用的情况下直接获取自旋锁，但不幸的是，SLAB_TYPESAFE_BY_RCU 对象中的任何自旋锁都必须在每次调用 kmem_cache_alloc() 之后初始化，这使得无引用的自旋锁获取完全不安全。 因此，当使用 SLAB_TYPESAFE_BY_RCU 时，请正确使用引用计数器。如果使用 refcount_t，则应使用专门的 refcount_{add|inc}_not_zero_acquire() 和 refcount_set_release() API，以确保在验证对象身份和初始化新分配的对象时的正确操作顺序。 refcount_{add|inc}_not_zero_acquire() 中的 Acquire fence 确保身份检查在获取引用计数*之后*发生。 refcount_set_release() 应该在新分配的对象完全初始化后调用，并且 release fence 确保新值在其他用户成功获取引用计数*之前*可见。 一旦 refcount_set_release() 被调用，该对象应被认为对其他任务可见。（那些愿意在 kmem_cache 构造函数中初始化其锁的人也可以使用锁，包括缓存友好的序列锁。）
对于传统的引用计数（例如 Linux 中 kref 库实现的引用计数），通常存在当对象的最后一个引用被删除时运行的代码。 对于 kref，这是传递给 kref_put() 的函数。 当使用 RCU 时，只有在所有引用该对象的 __rcu 指针都已更新，并且经过一段宽限期后，才能运行此类终结代码。 必须将每个剩余的全局可见的对象指针视为潜在的计数引用，并且通常仅在所有这些指针都已更改后，才使用 call_rcu() 运行终结代码。
为了了解如何在这两个类比之间进行选择（将 RCU 视为读者-写者锁，将 RCU 视为引用计数系统），反思受保护事物的规模非常有用。 读者-写者锁的类比着眼于更大的多部分对象，例如链表，并展示了当元素被添加到链表和从链表中删除时，RCU 如何促进并发。 引用计数的类比着眼于单个对象，并着眼于如何在它们所属的整体中安全地访问它们。
8. RCU API 的完整列表¶
RCU API 在 Linux 内核源代码中以 docbook 格式的头注释记录，但拥有完整的 API 列表会有所帮助，因为似乎没有办法在 docbook 中对它们进行分类。 这是按类别划分的列表。
RCU 列表遍历
list_entry_rcu
list_entry_lockless
list_first_entry_rcu
list_next_rcu
list_for_each_entry_rcu
list_for_each_entry_continue_rcu
list_for_each_entry_from_rcu
list_first_or_null_rcu
list_next_or_null_rcu
hlist_first_rcu
hlist_next_rcu
hlist_pprev_rcu
hlist_for_each_entry_rcu
hlist_for_each_entry_rcu_bh
hlist_for_each_entry_from_rcu
hlist_for_each_entry_continue_rcu
hlist_for_each_entry_continue_rcu_bh
hlist_nulls_first_rcu
hlist_nulls_for_each_entry_rcu
hlist_bl_first_rcu
hlist_bl_for_each_entry_rcu
RCU 指针/列表更新
rcu_assign_pointer
list_add_rcu
list_add_tail_rcu
list_del_rcu
list_replace_rcu
hlist_add_behind_rcu
hlist_add_before_rcu
hlist_add_head_rcu
hlist_add_tail_rcu
hlist_del_rcu
hlist_del_init_rcu
hlist_replace_rcu
list_splice_init_rcu
list_splice_tail_init_rcu
hlist_nulls_del_init_rcu
hlist_nulls_del_rcu
hlist_nulls_add_head_rcu
hlist_bl_add_head_rcu
hlist_bl_del_init_rcu
hlist_bl_del_rcu
hlist_bl_set_first_rcu
RCU
Critical sections Grace period Barrier
rcu_read_lock synchronize_net rcu_barrier
rcu_read_unlock synchronize_rcu
rcu_dereference synchronize_rcu_expedited
rcu_read_lock_held call_rcu
rcu_dereference_check kfree_rcu
rcu_dereference_protected
bh
Critical sections Grace period Barrier
rcu_read_lock_bh call_rcu rcu_barrier
rcu_read_unlock_bh synchronize_rcu
[local_bh_disable] synchronize_rcu_expedited
[and friends]
rcu_dereference_bh
rcu_dereference_bh_check
rcu_dereference_bh_protected
rcu_read_lock_bh_held
sched
Critical sections Grace period Barrier
rcu_read_lock_sched call_rcu rcu_barrier
rcu_read_unlock_sched synchronize_rcu
[preempt_disable] synchronize_rcu_expedited
[and friends]
rcu_read_lock_sched_notrace
rcu_read_unlock_sched_notrace
rcu_dereference_sched
rcu_dereference_sched_check
rcu_dereference_sched_protected
rcu_read_lock_sched_held
RCU-Tasks
Critical sections Grace period Barrier
N/A call_rcu_tasks rcu_barrier_tasks
synchronize_rcu_tasks
RCU-Tasks-Rude
Critical sections Grace period Barrier
N/A N/A
synchronize_rcu_tasks_rude
RCU-Tasks-Trace
Critical sections Grace period Barrier
rcu_read_lock_trace call_rcu_tasks_trace rcu_barrier_tasks_trace
rcu_read_unlock_trace synchronize_rcu_tasks_trace
SRCU
Critical sections Grace period Barrier
srcu_read_lock call_srcu srcu_barrier
srcu_read_unlock synchronize_srcu
srcu_dereference synchronize_srcu_expedited
srcu_dereference_check
srcu_read_lock_held
SRCU：初始化/清理
DEFINE_SRCU
DEFINE_STATIC_SRCU
init_srcu_struct
cleanup_srcu_struct
全部：lockdep 检查的 RCU 实用程序 API
RCU_LOCKDEP_WARN
rcu_sleep_check
全部：未检查的 RCU 保护的指针访问
rcu_dereference_raw
全部：禁止解引用的未检查的 RCU 保护的指针访问
rcu_access_pointer
有关更多信息，请参见源代码中的注释头（或从中生成的 docbook）。
但是，鉴于 Linux 内核中至少有四个系列的 RCU API，您如何选择使用哪一个？ 以下列表可能会有所帮助
读者是否需要阻塞？ 如果是，则需要 SRCU。
读者是否需要阻塞，并且您是否在进行跟踪，例如 ftrace 或 BPF？ 如果是，则需要 RCU-tasks、RCU-tasks-rude 和/或 RCU-tasks-trace。
那么 -rt 补丁集呢？ 如果读者需要在非 rt 内核中阻塞，则需要 SRCU。 如果读者在 -rt 内核中获取自旋锁时会阻塞，但在非 rt 内核中不会阻塞，则不需要 SRCU。（-rt 补丁集将自旋锁转换为睡眠锁，因此存在这种区别。）
您是否需要将 NMI 处理程序、硬中断处理程序以及禁用抢占的代码段（无论是通过 preempt_disable()、local_irq_save()、local_bh_disable() 还是其他机制）视为显式 RCU 读者？ 如果是这样，RCU-sched 读者将是唯一可行的选择，但自从大约 v4.20 以来，您可以使用 vanilla RCU 更新原语。
即使在软中断垄断一个或多个 CPU 的情况下，您是否需要 RCU 宽限期才能完成？ 例如，您的代码是否容易受到基于网络的拒绝服务攻击？ 如果是这样，您应该禁用读者中的软中断，例如，通过使用
rcu_read_lock_bh()。自从大约 v4.20 以来，您可以使用 vanilla RCU 更新原语。您的工作负载对于正常使用 RCU 来说是否更新过于密集，但不适合其他同步机制？ 如果是这样，请考虑 SLAB_TYPESAFE_BY_RCU（最初命名为 SLAB_DESTROY_BY_RCU）。 但请务必小心！
您是否需要在即使在 CPU 处于空闲循环深处、进入或退出用户模式执行期间或在脱机 CPU 上也能受到尊重的读端临界区？ 如果是这样，SRCU 和 RCU Tasks Trace 是唯一可行的选择，但在几乎所有情况下都强烈建议使用 SRCU。
否则，请使用 RCU。
当然，这都假设您已经确定 RCU 实际上是您工作的正确工具。
9. 快速测验的答案¶
- 快速测验 #1
为什么这个论点是幼稚的？ 在真实的 Linux 内核中使用此算法时，如何发生死锁？ [参考基于锁的“玩具” RCU 算法。]
- 答案
考虑以下事件序列
CPU 0 获取一些不相关的锁，称之为“problematic_lock”，通过 spin_lock_irqsave() 禁用中断。
CPU 1 进入
synchronize_rcu()，写获取 rcu_gp_mutex。CPU 0 进入
rcu_read_lock()，但必须等待，因为 CPU 1 持有 rcu_gp_mutex。CPU 1 被中断，中断处理程序尝试获取 problematic_lock。
系统现在死锁。
避免此死锁的一种方法是使用类似于 CONFIG_PREEMPT_RT 的方法，其中所有普通自旋锁都变为阻塞锁，并且所有中断处理程序都在特殊任务的上下文中执行。 在这种情况下，在上面的步骤 4 中，中断处理程序将阻塞，允许 CPU 1 释放 rcu_gp_mutex，从而避免死锁。
即使在没有死锁的情况下，此 RCU 实现也允许延迟通过
synchronize_rcu()从读者“传递”到其他读者。 为了看到这一点，请考虑 RCU 读端临界区中的任务 A（因此读持有 rcu_gp_mutex），尝试写获取 rcu_gp_mutex 而阻塞的任务 B，以及尝试读获取 rcu_gp_mutex 而在rcu_read_lock()中阻塞的任务 C。任务 A 的 RCU 读端延迟正在阻止任务 C，尽管是间接通过任务 B。因此，实时 RCU 实现使用一种基于计数器的方法，其中 RCU 读端临界区中的任务不会被执行
synchronize_rcu()的任务阻塞。
- 快速测验 #2
给出一个经典 RCU 的读取端开销为 **负数** 的示例。
- 答案
想象一个单 CPU 系统，该系统具有一个非 CONFIG_PREEMPTION 内核，其中路由表由进程上下文代码使用，但可以由中断上下文代码（例如，通过“ICMP REDIRECT”数据包）更新。 处理这种情况的通常方法是让进程上下文代码在搜索路由表时禁用中断。 使用 RCU 可以省去这种中断禁用。 因此，在没有 RCU 的情况下，您需要支付禁用中断的成本，而使用 RCU 则不需要。
有人可能会争辩说，在这种情况下，RCU 的开销相对于单 CPU 中断禁用方法而言是负的。 其他人可能会争辩说，RCU 的开销仅仅为零，并且用零开销的 RCU 方案替换中断禁用方案的正开销并不构成负开销。
当然，在现实生活中，事情要复杂得多。 但是，同步原语的负开销的理论可能性也是有点出乎意料的。 ;-)
- 快速测验 #3
如果在 RCU 读取端临界区中阻塞是非法的，那么在 CONFIG_PREEMPT_RT 中该怎么做呢？在 CONFIG_PREEMPT_RT 中，正常的自旋锁可能会阻塞！！！
- 答案
正如 CONFIG_PREEMPT_RT 允许抢占自旋锁临界区一样，它也允许抢占 RCU 读端临界区。 它还允许自旋锁在 RCU 读端临界区中阻塞。
为什么会出现明显的不一致？ 因为如果需要（例如，如果内存不足），可以使用优先级提升来缩短 RCU 宽限期。 相比之下，如果阻塞等待（例如）网络接收，则无法知道应该提升什么。 尤其是考虑到我们需要提升的进程很可能是一个出去吃披萨或什么的普通人。 尽管计算机操作的电击棒可能会引起极大的兴趣，但也可能会引起严重的反对。 此外，计算机如何知道这个人去了哪家披萨店？？？
致谢
感谢帮助使本文更易于理解的人们，包括 Jon Walpole、Josh Triplett、Serge Hallyn、Suzanne Wood 和 Alan Stern。
有关更多信息，请参见 http://www.rdrop.com/users/paulmck/RCU。