什么是 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()）。
上面的步骤 (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 half、抢占或中断的任何操作也会进入 RCU 读取端临界区。获取自旋锁也会进入 RCU 读取端临界区，即使对于不禁用抢占的自旋锁也是如此，就像使用 CONFIG_PREEMPT_RT=y 构建的内核中的情况一样。睡眠锁不会进入 RCU 读取端临界区。
rcu_read_unlock()¶
void rcu_read_unlock(void);
此时间原语由读取器用来通知回收器读取器正在退出 RCU 读取端临界区。启用 bottom half、抢占或中断的任何操作也会退出 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 保护的指针分配一个新值，以便安全地将值的更改从更新程序传递给读取程序。这是一个空间宏（而不是时间宏）。它不会计算为右值，但它会为给定的编译或 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 读取端临界区是非法的，就像从一个基于锁的临界区持有引用到另一个临界区一样！同样，在获取引用的临界区之外使用引用是非法的，就像使用正常锁定这样做一样。
与
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 保护读取较多的链表 和 使用 RCU 保护动态 NMI 处理程序 中找到。
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 保护读取较多的链表 和 使用 RCU 保护动态 NMI 处理程序 中找到。
4. 如果我的更新线程无法阻塞怎么办？¶
在上面的示例中，foo_update_a() 会阻塞，直到宽限期过去。这非常简单，但在某些情况下，人们无法承受如此长的等待时间 -- 可能有其他高优先级的工作要做。
在这种情况下，应使用 call_rcu() 而不是 synchronize_rcu()。call_rcu() API 如下：
void call_rcu(struct rcu_head *head, rcu_callback_t func);
此函数在宽限期过后调用 func(head)。此调用可能来自 softirq 或进程上下文，因此不允许该函数阻塞。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 中，普通自旋锁可能会阻塞时，您到底该怎么做？？？
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 时，请正确使用引用计数器。（那些愿意在 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-任务
Critical sections Grace period Barrier
N/A call_rcu_tasks rcu_barrier_tasks
synchronize_rcu_tasks
RCU-任务-粗略
Critical sections Grace period Barrier
N/A N/A
synchronize_rcu_tasks_rude
RCU-任务-跟踪
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
全部：锁依赖检查的 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 开始，您可以使用普通的 RCU 更新原语。
您是否需要 RCU 宽限期即使在软中断独占一个或多个 CPU 的情况下也能完成？例如，您的代码是否容易受到基于网络的拒绝服务攻击？如果是，则应禁用读取器上的软中断，例如，通过使用
rcu_read_lock_bh()。从 v4.20 开始，您可以使用普通的 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() 禁用 irq。
CPU 1 进入
synchronize_rcu()，写获取 rcu_gp_mutex。CPU 0 进入
rcu_read_lock()，但必须等待，因为 CPU 1 持有 rcu_gp_mutex。CPU 1 被中断，irq 处理程序尝试获取 problematic_lock。
系统现在死锁了。
避免此死锁的一种方法是使用类似于 CONFIG_PREEMPT_RT 的方法，其中所有普通的自旋锁都变为阻塞锁，并且所有 irq 处理程序都在特殊任务的上下文中执行。在这种情况下，在上面的步骤 4 中，irq 处理程序会阻塞，从而允许 CPU 1 释放 rcu_gp_mutex，从而避免死锁。
即使在没有死锁的情况下，此 RCU 实现也允许延迟通过
synchronize_rcu()从读取器 “传递” 到其他读取器。要了解这一点，请考虑处于 RCU 读取端临界区中的任务 A（因此读取持有 rcu_gp_mutex），试图写入获取 rcu_gp_mutex 而阻塞的任务 B，以及在rcu_read_lock()中阻塞并尝试读取获取 rcu_gp_mutex 的任务 C。任务 A 的 RCU 读取端延迟正在间接地通过任务 B 阻止任务 C。因此，实时 RCU 实现使用基于计数器的方法，其中 RCU 读取端临界区中的任务不会被执行
synchronize_rcu()的任务阻塞。
- 快速测验 #2
给出一个经典 RCU 读取侧开销为负的示例。
- 答案
假设一个具有非 CONFIG_PREEMPTION 内核的单 CPU 系统，其中路由表被进程上下文代码使用，但可以被 irq 上下文代码（例如，通过 “ICMP REDIRECT” 数据包）更新。处理这种情况的通常方法是让进程上下文代码在搜索路由表时禁用中断。使用 RCU 可以免除此类中断禁用。因此，在没有 RCU 的情况下，您需要付出禁用中断的代价，而使用 RCU 则不需要。
可以认为，在这种情况下，RCU 的开销相对于单 CPU 中断禁用方法是负的。其他人可能会认为 RCU 的开销仅仅是零，并且用零开销的 RCU 方案替换中断禁用方案的正开销并不构成负开销。
当然，在现实生活中，事情更加复杂。但是，同步原语的负开销的理论可能性也有些出乎意料。;-)
- 快速测验 #3
如果在 RCU 读取侧临界区中阻塞是非法的，那么在 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。