解开 RCU 使用之谜（额外用例）¶
标题：Unraveling RCU-Usage Mysteries (Additional Use Cases)
日期：2022/02/24
作者：Paul McKenney
链接：https://www.youtube.com/watch?v=tBl3yh6Mc1c
注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。
所以我们今天要讨论的是… 所以今天我们要讨论的是用额外的用例来解开RCU使用之谜。这是对去年12月7日那次演讲的后续。这就是我们今天要做的内容。我们会非常快速地回顾上次的演讲内容。我们会查看用例，并深入探讨其中一些。快速回顾一下，页面底部的URL是上次演讲的链接，如果你想回去再看一遍的话。
但首先，从核心问题说起，这导致了RCU以及那里提到的风险指针（hazard pointers），核心问题是全局达成一致的成本高昂。让所有CPU、所有线程、所有东西就某事达成一致需要时间。这是由于光速的有限性。另一个事实是，虽然项目非常小，但它们的尺寸并非为零。正如我去年12月说的，如果50年前有人告诉我，我会说光速太慢，原子太大——不是为了太空旅行，而是为了计算——我不知道我当时会说什么，但我保证我不会相信你。但今天，我就站在这里这么说。
所以解决这个问题的方法是，我们同时使用空间同步和时间同步。读-写锁严格使用时间同步。我们要在此基础上加入空间同步。RCU是实现这一点的一种方式。同样，风险指针是另一种方式。所以这里我们快速过一下它是如何工作的。
那么，这里是核心RCU API，我们有时间的部分。是的。非常抱歉打断一下。我想可能Zoom菜单栏可能挡住了你幻灯片上的标题。哦，真的吗？是的。好的。其他人也看到了吗？这很有趣。我们试试点击这里让它消失。试试看。走开。嗯。不，刚才似乎没起作用。是的。看起来标题上方可能有一个黑框。所以我们现在看到的是“RCU核心…”，一堆乱码，然后是“空间”。是的。哦，太好了。我“爱”Zoom。是的。好的。让我看看能不能做点什么让它消失。或者也许你只需把标题念出来，我们确保在幻灯片里捕捉到这个情况。好的。停止共享然后重新开始，看看会不会导致什么问题。好的。好的。所以我停止了共享，然后在这里重新开始。然后我这样做，然后点击共享。现在，好点了吗？是的。是的，我们看到标题了。是的。好的。我们看到大部分了。可能被切掉了一点，但其余部分都在。是的。好的。好吧，我会把标题念出来，但现在大家能更好地看到它们了。所以谢谢你。那么我们就… 好的。谢谢你提醒我。就像我说的，我“爱”Zoom。是的。好的。不过你得承认，如果50年前有人告诉我，我会在自己的办公室里舒舒服服地向散布在世界各地的人做演讲，我也不会相信。所以是的，世事难料。我想就是这样吧。
好的。所以我们有RCU API：时间（temporal）与空间（spatial）。蓝色的东西是时间部分。我们用rcu_read_lock标记读者开始，用rcu_read_unlock标记读者结束，给出读者开始和结束的时间。synchronize_rcu 和 call_rcu 分别是同步和异步接口，用于等待所有先前存在的读者完成。然后这些… 所以这些是处理时间的内容。处理空间的部分。我们有 rcu_dereference 用于加载一个受RCU保护的指针。引用的保护在更新端。涉及块的引用。rcu_assign_pointer 用于更新一个指针。理论上这些可以只是赋值语句。但是CPU，尤其是编译器，在尝试编写并发代码时有时会有点“讨厌”。而这些函数可以防止CPU和编译器做傻事。这些只是API的七个元素。还有更多。底部有一个URL指向2019年1月的一篇LWN文章讨论这些。自那以后又增加了一些，但不多。
好的，继续看RCU语义的图形化表示。所以我们有那个核心API，现在我们只讨论其中的三个：rcu_read_lock 和 rcu_unlock，界定一个读者。我们从左上角开始。在左上角，我们有一个 synchronize_rcu 在一个读者之后启动。这意味着该读者可能看到被移除的数据。它可能持有对该数据的引用。这意味着 synchronize_rcu 必须克制不返回，直到那个读者完成，那时你才可以释放旧内存而不用担心搞乱那个读者。让我告诉你，释放后使用（use after free）是个坏主意。把RCU和释放后使用结合起来也无济于事。好的。所以这很重要。
然而，另一方面，如果 synchronize_rcu 先启动，嗯，那意味着我们现在在右上角。在右上角，synchronize_rcu 先启动。这意味着读者不可能看到被移除的数据。所以那个内存被释放不会给那个读者带来不便。因此，即使可能有后来的读者还在进行中，synchronize_rcu 返回也是可以的。因为那些后来的读者看不到被移除的东西。这就是关键的好处所在。
我们把更新分成两部分。我们有一个对读者可见的移除部分。然后我们有一个释放部分。我们在两者之间留出足够的时间，这样我们等待的是先前存在的读者，而不必等待后来的读者。然后我们可以两者兼得。我们可以既有皮带又有背带（双重保险）。这在左下角这里。如果我们有一个读者在移除之后才出现，所以它看不到正在被释放的数据，并且它在内存被释放之前就完成了，嗯，这是双重的好，因为它既没看到那个内存，而且无论如何在它完成之前内存也不会被释放。
坏的情况，你在RCU中有bug的情况，是在右下角。我们不能让一个读者在一个 synchronize_rcu 开始之前启动并在其结束之后才结束。因为你可以清楚地看到，它可能获得对那个旧数据的引用，并且当它被释放时它可能还在使用它。这又是个坏主意。所以这大致上图形化地展示了RCU对时间顺序施加的约束。
好的。下一张幻灯片又是关于RCU管理的，但看的是限制。RCU通过成为一个专用工具来获得其性能。好吧。它并不试图成为所有人的万能工具，这使得它在其设计应用的领域能很好地工作。因此，作为一个经验法则，你读得越多，更新得越少，RCU对你来说就越好用。另一个经验法则是，你的算法越能容忍陈旧和不一致的数据，RCU对你来说就越好用。这听起来可能很奇怪，但光速也适用于计算机外部的事物。这意味着如果我们在计算机内部发生了一个更改，等那个更改在计算机内部生效时，它已经是旧闻了。所以如果我们有一个跟踪外部状态的算法，而这个外部状态甚至不必是那么“外部”，即使像连接到CPU的设备从这个角度看也是“外部”的，那么我们本来就在处理陈旧和不一致的状态。所以多一点点时间上的不一致通常是可以接受的。
在左下角，那个红色的三角形，那是RCU对你来说不会很好用的地方。20年前我会说，别在那里用RCU。但与Linux内核社区合作的一个非常酷的事情是，他们能够提出我未曾考虑过的新东西并教会我新东西。他们教会了我两个你确实想在那里使用它的理由。我们会讨论第一个。我们将展示一个案例，即使你一直在更新，RCU也能为非阻塞同步提供一些保护来简化它。另一个情况是如果你读得不那么频繁，但当你读的时候，有严格的延迟约束。在那种情况下，你可能也想使用RCU。
另一个需要考虑的事情是，RCU经常用于链接数据结构。在12月，我们看到了一个案例，阶段状态改变（phase state change），那里根本看不到任何指针或链接。所以它也可以用在其他情况，但大多数用途，最常见的用途，涉及链接数据结构。好的。所以这就是限制。
这里我们只是展示一下全局达成一致的成本，标题在那里。这首先展示了读者-写者锁。那么会发生什么呢？我们有一堆读者。假设我们有一个读者一直在运行的情况。这意味着如果一个更新者出现，我们必须等待所有读者完成。然后我们必须等待读者完成的协议在整个机器中传播，这样就不会有新的读者启动。然后我们才能更新。一旦更新者完成，我们必须等待更新者完成的协议在整个机器中传播。那里那五个红色的大条，那是无法挽回的损失时间。当然，随着你增加CPU，那个红色区域会变大。它以两种方式变大。首先，显然，你有更多的条。其次，更大机器的协议延迟往往比小机器更大。这可能是个问题。我的意思是，显然，这对于激进的实时性来说，即使在延迟方面也是个问题。如果你希望你的读者出现并且你希望是亚毫秒级的，这可能是个问题。但即使对于更常规的工作负载，例如数据中心，你有基于Web的延迟，如果你的更新者需要任何特定的时间长度（它们经常如此），这在数据中心也可能是不可接受的。
所以我们想用RCU来做这个，在幻灯片的底部。所以这里我们到处都是读者。我们把更新者分成两部分，就像我们之前在上一张幻灯片上那样。我们有一个移除和一个释放。所以我们在那里有更新者1（移除）和更新者2（释放）。中间那个条，有点绿蓝色的。如果在你看来颜色不同，抱歉。我是红绿色盲。所以我给你颜色的大致名称。这里发生的是，我们只有非常少的开销。现在会有缓存未命中。更新者移除了一些东西。这将导致缓存未命中。所以当时正在运行的读者可能会因为缓存未命中而多花一点时间。但没有大的协议延迟，没有大的红色区域。所以我们可以获得好得多的延迟和好得多的效率。
好的。那么让我们回过头来看看12月7日那张特定的幻灯片。这是那张展示空间和时间同步的幻灯片。时间从上到下推进。因为我们没有那个大红色的东西，如果我们有那个大红色的东西，那么读者要么看到旧值，要么看到新值。它们会在不同的时间，一切都会非常、非常容易理解，非常有条理，非常有控制欲。但我们在中间会有那个大缺口。我们要为那个特权付出代价。
所以我们做的是将地址空间与时间结合使用来理清事情。在水平的蓝色虚线之上，大家都同意我们处理的是旧数据。只有旧数据。新数据还没出现。如果我们看第二条蓝色虚线之下，大家都同意有新数据，不再有旧数据了。在两条线之间，不同的读者可能得到不同的数据，要么是旧数据，要么是新数据，但任何一个给定的读者只会得到其中之一。它不会两者都得到。结果证明，现在有些情况下这还不够。我们将在本次演讲后面讨论一种解决这个问题的方法，一个特定的用例。准多版本一致性控制（Quasi multi-version consistency control）的幻灯片。我们会讨论那个。但就目前而言，如果我们不需要那种程度的一致性，我们只需要一个给定的读者看到相同的一致结果，这将通过一方面使用时间、另一方面使用地址空间来保证一致性。
好的。所以我们可以将其映射回上一张幻灯片，并展示保证看到旧值的读者（用蓝色表示）。保证看到新值的读者（用绿色表示）。中间那种蓝绿色的，是那些可能看到旧值也可能看到新值的。但是，一旦一个给定的CPU或线程开始看到新值，那个CPU或线程之后将永远看到新值。所以我们事先不知道顶部的线程上那两个读者（从左数第三和第四个），它们中的哪个会开始看到新值。它们中的一个或另一个会。或者它们可能都看到旧值。但是一旦它开始看到新值，它将永远看到新值。所以这大致上图形化地展示了在更新进行时读者会发生什么。
好的。这就是我们的回顾。再次，我们提供了上次演讲的URL，供那些想更深入回顾的人使用。但现在我们要看用例的图表。阶段状态改变我们去年12月讨论过，这次不再讨论。准读写锁（QuasiReadItWriterLock）我们上次花了很多时间讨论。这次我们只打算给它加几个“花样”，如果我们有时间的话。如果时间允许，我会讲所有这些。如果我们时间不够，我会跳过我认为不那么重要的一个。但墨菲定律说，那些将是你接下来需要的，对吧？是的，生活有时就是这样。
好的。让我们从仅追加列表开始。所以仅追加列表在左下角那里。它只连接到链接发布订阅，这是有意为之的。它非常基础。它几乎没有在原始RCU之上增加什么内容。好的。让我们用代码来说明。但首先我们从典型的增删列表开始，因为这对那些熟悉Linux内核的人来说会更熟悉。
所以我们有一个读者和一个更新者。它们将在不同的线程中运行。读者由 rcu_read_lock 开始，由 rcu_read_unlock 结束，正如你所期望的。list_for_each_entry_rcu 只是一个遍历列表的迭代器。它正在遍历的列表是这个 rl 东西。迭代变量是 p。好的。nxt 只是结构体中的一个字段，包含用于迭代的列表头指针。所以这将做的是，它会遍历列表，并对每个元素调用 do_something。并且可能在我们做这个的时候那个元素被移除了，但它不会被释放。所以 do_something 将有真实的内存可供操作。它下面的东西不会被猛地抽走。当然，这意味着更新者必须小心处理。那么让我们看看更新者。
有一个全局自旋锁 ml。它将要获取那个锁，然后在倒数第三行语句释放它。这避免了来自其他更新者的任何干扰。我们有多个更新者试图在锁的保护下运行一次。那个锁对读者没有任何影响。读者在我们做这些的时候仍然在蜂拥而入，正如我们在之前的图表中看到的。所以下一行用 list_first_entry 来获取列表的第一个元素，无论它是什么。然后下一行用 list_del_rcu 移除那个元素。带下划线的 _rcu 导致它保留 next 指针不变。这意味着一个读者碰巧在我们移除它时正在查看那个元素，它仍然能够从那个元素出去到列表中的下一个元素。好的。所以 list_del 本身会毒化（poison）前向和后向指针。list_del_rcu 只毒化前向指针，保留后向指针在那里，这样读者可以继续遍历列表。
然后我们有一些指针 queue，我们之前不知怎么地分配并初始化了它。别担心它是怎么发生的。我想塞在一张幻灯片里，这样就做到了。所以我们用 list_add_rcu 把它添加到列表的开头。所以我们拿到那个 queue 指针并把它添加到 rl 列表。我们释放锁。所以现在另一个更新者可以进来做事了。我们做 synchronize_rcu 来等待所有先前存在的读者。那些先前存在的读者是唯一可能持有对 p 的引用的读者，因为我们用了 list_del_rcu 来移除它。所以一旦我们完成等待所有读者，一旦那个 synchronize_rcu 返回，我们就可以安全地对 p 做 kfree 并摆脱那个东西。
所以这是一个增删列表，标准的东西，类似于你在Linux内核中看到的那种。通常你只做添加或删除，而不是像我们这里这样一次做两个，但再次强调，一张幻灯片。
那么让我们看看我们需要做些什么来让它变成仅追加列表。有一个例外，我们必须在 list_for_each_entry_rcu 里加一个 true 来让锁检测（lockdep）满意。true 不影响它的操作。它只是告诉锁检测，嘿，我明白我不在一个可重入临界区，这是可以的。别抱怨。因为我们从不删除任何东西，我们不需要标记 rcu_read_lock 或 rcu_done_lock。所以这些可以去掉。在更新者这边，我们不删除，只添加，所以我们显然可以去掉获取第一个元素并删除它的部分。list_first_entry 和 list_del_rcu，这些都去掉。我们没移除任何东西。所以我们不需要做 synchronize_rcu，也没有东西要释放。所以这些都去掉。所以红色划掉的线都要去掉。
下一张幻灯片将展示我们剩下什么。所以读者只是迭代列表并对每个元素做些事情。我们只添加，不移除。所以元素不会消失。我们不必担心它们消失。它们永远不会。然后更新者只是添加东西。在Linux内核中确实有采用这种方法的代码。它可能看起来有点傻。为什么你会制造内存泄漏，对吧？你只添加，从不删除。但有些情况下，你偶尔会有变化。你需要跟踪自这次启动以来的旧状态。所以列表只是增长。但出于各种原因，它不能增长得太远。也许你有插入的设备。它们不能被移除。或者可能有可以上线的设备。一旦它们上线，你就添加它们。如果它们被移除，你仍然跟踪同一个列表。当你再次添加它们时，你重用那个条目，例如。这样，列表只能增长到设备数量那么多。你永远不必担心删除任何东西，因为它可能被移除，但你仍然跟踪它曾经存在过的事实。所以这就是它的一个用途。
好的。这是它如何运作的。这次，我展示了我在示例中省略的分配初始化部分。所以我们有我们的列表 rl，顶部的红色框。时间从左向右推进。所以我们有这个列表。我们有箭头显示改变它的操作。我们给它上色。红色框是读者可以访问的东西。绿色框是读者无法访问的东西。我的意思是，除了直接去内存里挖掘，那无论如何都是个坏主意。
好的。所以我们分配了那个东西。它是未初始化的。我们最终得到第二个状态，rl 指针仍然是NULL，但有一块内存可以操作。我们初始化它。现在它不再是未定义的了。我们有了 a=1, b=2, c=3，等等。我们用 list_add_rcu。突然，读者可以访问它了，他们用 list_for_each_entry_rcu 来遍历它。生活很美好。这能工作的原因是 list_add_rcu 小心地让编译器一次性写入指针。它不是一次写一个字节之类的。而 list_for_each_entry_rcu 强制编译器一次性加载它。并且如果像DEC Alpha这样的架构需要在读端添加特殊指令来使排序生效，它就提供了。相当多的架构确实要求 list_add_rcu 在需要时添加适当的排序。所以它在需要时就这么做。所以这就是我们在运行更新时大致发生的事情。而读者一直在进行。所以我们有一种向列表添加东西的方法，而无需阻塞读者等待添加，并且仍然能让事情顺利进行。读者要么会看到空列表，要么会看到新元素，但它不会看到奇怪的东西。
好的。所以如果我们随着时间的推移在列表中添加了三个元素，它看起来像这样。我们有一个 prev 和 next 指针。那是我们之前看到的 nxt 字段。我们有我们的后向和前向指针。后面的指针环是红色的，因为我将在所有包含此列表的后续幻灯片中省略它们。好的。它们仍然存在。你可以在想象中把它们放回去。但我们需要装饰列表，并且我们必须为它腾出空间。所以那些指针就消失了。我们可能有一个锁。我们会有一些使用它的案例。我们还有其他数据。例如，在上一张幻灯片中，a、b 和 c 就在“其他数据”里。
所以RCU的工作方式是，我们将同步责任分散到不同的机制中。在这个案例中，我们只做添加。红色的虚线表示 ml 锁的同步责任。所以更新者做了 spin_lock(&ml)。它那样做是为了保护元素的 prev 和 next 指针。它正在插入一个新元素。它将不得不处理被插入元素相邻元素的 prev 和 next 指针。然后是蓝色的RCU发布订阅。这体现在 list_for_each_entry_rcu 中。它确保初始化对读者是可见的。他们不会得到一个指向某物的指针却看到初始化之前就在那里的东西。所以这就是我们如何拆分事务。
在某些情况下，“其他数据”可能是可变的。那样的话，锁就会起作用。那就是黄色的框。通常会发生的是，锁负责保护“其他数据”。在RCU里使用锁可能看起来很奇怪。为什么我们要扔一个锁进去？关键点是，ml 锁是一个全局锁。如果我们在那上面有任何争用，生活就会变得艰难。这些在数据结构本身中的锁，它们是每个数据结构（per-data-structure）的。它们是分开的。所以争用被分散到所有元素上。只要你的数据中没有某种热点，那意味着你的争用保持在合理低的水平，或者可以保持在合理低的水平。
好的。那么总结一下RCU在仅追加列表中的应用，我们使用了链接结构的发布订阅。那就是之前在“你在这里”图表左下角的白色方框。我们没有给它添加任何东西。这就是我们拥有的全部。所以这非常简单。非常基础，可以说是RCU的一种原始用法，这就是它排在第一位的原因。
好的。让我们推进到仅删除列表。如果我们有仅追加列表，我们也有仅删除列表。它可能听起来同样傻，但我们会讨论一个可能的用例。所以我们在这里。它基于存在保证（existence guarantee）。所以它比仅追加列表稍微不那么原始。如果我们从增删列表开始，我会再过一遍。这和几张幻灯片前的一模一样。我们将看看我们需要改变什么来从增删列表变成仅删除列表。
这里我们为仅删除列表移除代码。读者那边没发生太多变化。我的意思是，我们可以… 我是说，嵌入在 list_for_each_entry_rcu 中的是一个 rcu_dereference。它也可以换成 READ_ONCE。但这不会有多大区别，尤其是在最近的内核中。好的。但我们不添加任何东西。所以我们在更新者中去掉了添加的部分。所以当我说仅删除列表不如仅追加列表原始时，我是认真的。你可以看到从增删列表变化的复杂度要小得多。
那么为什么我们要有仅删除列表？也许你有某个东西在跟踪内存设备。也许如果它们显示出故障率，例如显示出ECC错误，你就必须停止使用它们。在那种情况下，你可能会有某个东西跟踪每个内存。但一旦它变得不可靠，你可能只是把它从列表中删除，再也不关注它了。而且你可能没有办法在这个系统中实际插入新内存。这在当今并不是那么常见的能力。所以在那种情况下，内存只能被移除。它不能回来，你就有了一个仅删除列表。我相信我在Linux内核中见过一两个这样的东西，但我无法告诉你它们在哪里或者是否还存在。
好的。所以如果我们只展示代码，你可以看到它基本是一样的。我们去掉了添加的部分，这里就是。
所以这是仅删除列表如何工作的。我们添加了另一种颜色，黄色。那表示读者无法访问它，但旧的读者可能仍然在那里。所以如果我们从一个列表开始，它上面有 cat 和 tux，全是红色的。可能有读者在任何地方。我们对 cat 做 list_del_rcu。好的。在这一点上，rl 现在指向 tux，新的读者没有办法访问 cat 了。所以可能仍然有读者碰巧在我们做 list_del_rcu 之前加载了 rl 的指针，并且它们可能在那里待相当长的时间。它们可能在用 cat 做天知道的事情，特别是名字还叫薛定谔。但无论如何，只有旧的读者。那意味着我们做 synchronize_rcu。那些旧的读者必须在 synchronize_rcu 返回之前完成。所以 cat 现在变成绿色了。安全了。没有读者能访问它了，我们可以安全地 kfree 它。
好的。所以这只是展示了仅删除列表如何工作以及它如何保护读者的安全。
我们有非常相似的同步责任图。我们从列表中删除，这由一个全局锁 ml 保护。我们在几张幻灯片前看到了那个东西的 spin_lock 和 spin_unlock。我们仍然需要防止编译器干扰读者。现在我们不必担心初始化，因为我们没有添加任何东西。然而，我们确实需要编译器以单条指令存储的方式存储更改后的指针，这样读者，它必须使用单条指令加载，才不会看到几个指针的某种混乱组合。这对你的内核的实际真实统计数据来说很糟糕，你可能已经体验过了。再次强调，就像之前一样，如果我们有可变数据，我们可以有一个每个元素的锁，我们只需扫描列表来找到我们想要的。我们以无锁方式做这个。当我们到达元素时，我们可能发现需要修改某些东西，我们可能需要在锁的保护下做那个。
所以对于仅删除列表我们也有那个选项。仅删除列表有趣的地方在于，我们利用了存在保证并从其中移除了某物。我们不再依赖发布订阅部分，但我们依赖构成存在保证的所有其他部分。
好的。那么我们来谈谈存在保证。这就在仅删除列表的正下方。看起来仅删除列表给它添加了东西，但那是个假动作。它实际上是为它移除了东西。所以存在保证实际上比仅删除列表更不原始。所以我们在代码中要做的是类似读者然后更新者（reader-then-updater）的事情。
好的。所以我们有一个读者，我们在那里用 rcu_read_lock 开始，读者在大概三分之二的位置用 rcu_read_unlock 结束。我们要寻找一个元素，我们要把那个元素的指针放在 q 里。所以我们一开始 q 是NULL。我们用 list_for_each_entry_rcu 遍历列表，就像我们在之前所有例子中那样。这将按顺序逐步遍历列表。如果我们有正确的键，我们设置 q = p 来记住我们找到了那个东西。然后我们获取自旋锁。
所以这里发生的是，RCU确保元素存在的时间足够长，让我们能获取一个自旋锁。如果我们没有那些 rcu_read_lock 和 rcu_done_lock，我们可能会遇到某人移除元素或释放它，就在我们获取自旋锁的时候，这对你的内核也不好。好的？但因为我们处于RCU读端临界区，我们在顶部有 rcu_read_lock 保护我们。我们可以做那个自旋锁，然后我们可以跳出循环。
如果我们找到了一个元素，q 将是非空的。我们检查它是否已被删除，我们将在下一张幻灯片看到那是如何工作的。但如果它已经被删除，我们不想做任何事。我们只希望在它没有被删除的情况下进行一些更新。在那种情况下，现在我们不再有RCU保护了，但我们确实持有锁，我们将在下一张幻灯片看到这阻止了更新者移除元素。然后我们释放锁，我们就完成了。
好的。在下一张幻灯片上，我们要获取锁。我们获取第一个条目。现在我们添加一个自旋锁。所以我们在获取元素本身的锁，只有现在我们才设置 deleted = true 并删除它。好的？所以一个读者可能进来，它可能在我们做之前获取锁，那样的话我们的自旋锁会等待，读者会继续，它会做它的事情，它会调用那个函数。好的？如果它刚好在那之后出现，它会看到 deleted == true，它就不会做任何事。好的？我们为添加做我们的 list_add_rcu。我们释放全局锁，然后我们做 synchronize_rcu 来等待读者，然后我们可以安全地释放它。好的？好的。
现在我们依赖锁，我们依赖锁覆盖的不仅是“其他数据”，像之前那样，而是整个元素。这是因为删除者必须持有每个元素的锁来执行移除。所以它也保护被移除元素的 next 和 prev 指针。好的？否则，我们有相同类型的事情。全局锁也保护删除。它也保护可能发生的任何添加。而且，list_for_each_entry_rcu 确保读者看到有效的指针，并且也看到添加元素的初始化。好的？
好的？所以再次，我们将不同的责任委托给不同的同步机制，使它们一起工作。
好的？所以再次，锁比之前做的更多。它保护“其他数据”，并且它也防止相应的节点被移除。如果你持有锁，它要么已经被移除了，要么不会被移除。两种情况之一。
好的？所以我们从RCU开始。存在保证的RCU转换，如果你愿意的话。我们从等待读者和发布订阅开始，两者都是之前在图表底部角落的白色方框。我们使用堆分配器，我们使用延迟回收。延迟回收可以是 synchronize_rcu 或 call_rcu 或 kfree_rcu 或一些更新的“发射后不管”（fire and forget）风格的原语。好的？存在保证相当强大。如果你在一个读者中，那个东西保证存在。但有时它可能很昂贵。所以对于那些时候，我们有类型安全内存。
所以类型安全内存类似于存在保证。它稍微弱一点。用起来稍微难一点。但在某些情况下，你能获得更高的效率。所以让我们看看这里。类型安全内存在内核中的实现方式是，你有一个slab分配器。好的？你做 kmem_cache_create。你传入 SLAB_TYPESAFE_BY_RCU 标志。好的？这实际上是对真正学术上的类型安全内存的一种近似。但它似乎对我们相当有效。有时近似比原始的东西更好。这样做的好处是你能获得更好的缓存局部性。如果你有一个带 SLAB_TYPESAFE_BY_RCU 的slab分配器，如果你释放了某物，它可以立即被重新分配。你不必等待一个宽限期来释放它。你直接现在就释放它。它可能立即被重新分配。那意味着被重新分配的内存仍然在缓存中是热的。另一方面，如果你等待一个宽限期，就像你在存在保证中做的那样，那个内存在缓存中可能更冷。当你重新分配它时，你可能会受到一些性能损失。但没有免费的午餐，特别是因为这是RCU。而同步一般来说也没有多少免费的午餐，你可能已经注意到了。所以那意味着读者需要一个验证步骤。因为你没有等待宽限期。所以你可能是读者去抓取某物，而它可能被释放并从你下面被重新分配走了。所以你必须确保你正在处理的是你认为的那个东西。
所以看看这个。我们将有一个TSM（类型安全内存）状态图。这是特定于Linux内核的。所以我们有带 SLAB_TYPESAFE_BY_RCU 的slab缓存，kmem_cache 东西。我们可以从中分配。kmem_cache_alloc 在那里。一旦我们做了那个，我们在最左边。它正在使用中。在某个时刻，我们可能决定释放它，那样它就回到slab。如果那个元素碰巧是那个slab中的最后一个东西，我们就有一个空的slab，我们释放它。但当我们把它释放回页分配器时，我们在那时等待一个RCU宽限期。好的？所以任何可能访问它的读者都知道在到达最右边的空闲页池之前已经完成并放弃了引用。
当然，如果 kmem_cache_alloc 说，嘿，我需要点东西，但什么也没有，那么slab缓存将获取一个新的slab，获取一些页，并从中创建一个新的slab。所以那将从顶部右边绕过来。所以我们这里有一个类似8字的图形，缓存已经运行过了。但有趣的部分是左边的8字，因为一块特定的内存可以非常非常快地绕着那个圆圈转啊转。这里没有宽限期。你直接释放它。它可以立即被重新分配。它可以使用一小会儿。它可以转得非常非常快。而大多数读者，也许不是全部，但我所知道的那些，他们需要阻止这种搅动。他们需要一种方法来停止那种搅动。那就是验证的目的。
好的。一种停止搅动的方法，我们将看一些被粗暴地砍掉的示例代码。完整的东西在dash RCU树的一个特定标签上，在幻灯片底部。我不打算把它推送到上游，但有一个标签为后代保存着它。
所以你可以做的是使用一个引用计数器。避免释放项的方法是使用一个叫做 atomic_add_unless 的东西。atomic_add_unless 执行一个原子加，除非你有一个指定的值。在这个案例中，我们将使用零。好的。所以会发生的是，我们将做一个 atomic_add_unless。所以会发生的是我们做一个原子增加，除非值已经是零，那样它就返回说，抱歉，我做不了。那样做允许我们拒绝当前正在被释放的项。当然，它可能已经被释放然后在我们搞清楚发生了什么之前被重新分配了。所以即使我们成功获得了一个引用，我们也必须重新检查键并确保它仍然是我们要的那个东西。所以我们必须有条件地获取一个引用。如果我们获得了引用，我们必须重新检查键。
所以让我们看看我们如何做那个。所以这只是展示一个我们将要使用的 struct foo。它有一个列表头，在RCU的示例代码中使用。我们不会关注它。我们将假设我们知道如何制作RCU保护的列表，因为我们在本次演讲中已经讲过好几次了。我们有一个原子引用计数在那里，ref。我们有一个键，是一个整数。
现在我们必须有自己的 kmem_cache。那就是我们中间的 foo_cache。我们创建它。就像你总是做的那样 kmem_cache_create。但你要传入那个红色的 SLAB_TYPESAFE_BY_RCU 标志，告诉它，嘿，在把整个slab交回页池之前，请等待一个宽限期。kmem_cache_destroy 就像你总是做的那样。这样做的一个好处是它会为你发现内存泄漏，我在调试代码时就有几个。好的。好的。
你必须专门分配初始化。我们在这页上有一个完整的 foo_alloc 为我们做这个。我们做 kmem_cache_alloc。如果我们什么也没得到，我们返回NULL报告这个悲伤的故事。否则，我们将键设置为所需的传入值。然后我们做 atomic_set_release。好的。所以我们有一个初始引用计数为一。那有点像数据结构的隐式引用。调用者有责任将它添加到那个数据结构中。我们一开始就给了引用。而 atomic_set_release 意味着如果有人做 atomic_add_unless，如果他们获得了一个引用，他们将看到键的新值。好的。那个排序很重要。
好的。有了这些，让我们看看如何获取键。所以读者在找到元素后，必须做 foo_get_key 来确保它获得了引用并且那个东西有相同的身份。所以它将在 rcu_read_lock 内部做这个。所以我们在顶部有 rcu_read_lock。我们在返回之前，在底部有 rcu_read_unlock。现在我们做 foo_lookup，我们这里没有展示，但它做了一次查找。我们给它键，它返回给我们一个指针。它可能返回一个空指针，那样的话我们就直接返回NULL。这就是那个 if 语句的空 then 子句。但如果我们确实得到了一个指针，我们将尝试 atomic_add_unless 它。所以如果它是零，那是最后一个参数，我们原子地加一。所以这可以认为是一个 atomic_inc_unless，但我们有一个 atomic_add_unless。如果它返回假，那意味着引用是零。所以意味着在我们查找它的时候或者在我们刚返回之后，有人释放了它。在那种情况下，我们没有得到引用。我们在 else if 的子句中设置 p = NULL。现在，如果我们到达最后一个 else if 那里，那意味着我们得到了一个引用。所以我们检查键是否匹配。如果不匹配，那么我们必须调用 foo_put 来撤销我们的引用计数。我没在那里放那个，事实上是我导致内存泄漏的bug之一。所以我们 foo_put 来撤销我们的引用，并设置 p = NULL。然后我们返回 p 的值。所以如果我们获得了引用并且键在获得引用后仍然匹配，我们就返回指向元素的 p。否则我们返回NULL。要么我们一开始在搜索结构中没找到那个东西。我们无法获得引用。或者我们获得了引用，但它的身份在期间改变了。好的。所以这是示例验证代码，我们用它来处理我们没有在释放元素之前等待宽限期的事实。我们直接释放它。它可能立即被重新分配。而这个加在读者身上的额外开销，是我们为在热释放/分配路径上不需要宽限期所付出的代价。
好的。那么关于那个有什么问题吗？这确实快速地讲了很多东西。所以我给大家一个提问的机会。一次。两次。好的。成交。我们去下一张幻灯片。如果你看过最新的内核，这看起来可能很熟悉。我们做 atomic_dec_and_test。它获取我们的引用计数并递减它。如果结果是零，它返回真，否则返回假。如果它返回真，那么我们现在有零引用。并且没有读者引用它了。如果读者试图引用它，它在上一张幻灯片上的 atomic_add_unless 会失败。所以我们可以直接 kmem_cache_free 它。好的。现在，那意味着我们可能有读者指向空闲列表，但这是一个特殊的空闲列表，因为我们有一个带 SLAB_TYPESAFE_BY_RCU 的slab。我们在空闲列表中。在回到页分配器之前，我们不会没有宽限期。所以它可以被另一个 kmem_cache_alloc 回收为相同类型，但我们不会真正被释放并用于别的东西。好的。所以那意味着结构体的布局保持不变，我们可以指望它不会变形成别的东西。它可能变形为相同类型的不同实例，但这就是为什么我们在 foo_get 代码中有引用获取和键的重新检查。
好的。你可能会有一个问题是，这很复杂。为什么不用锁呢？我是说，我们有这个东西。它一直存在。为什么不直接获取一个锁？
问题是 kmem_cache_alloc 可能返回未初始化的内存。我们将在另一张幻灯片看到那是怎么发生的。那意味着初始化… 我是说，在之前的状态下，我们只是把引用设置为零。如果这是这个特定元素的第一次轮回，它只是从垃圾设置为零。如果它是通过 kmem_cache_free 回来再通过 kmem_cache_alloc，atomic_dec_and_test 已经把它设为零，而我们又设为零。好的，所以我们设置为零并没有改变它的值。问题是自旋锁比那复杂一点。如果我们在那里做一个自旋锁初始化，而同时有人试图获取那个自旋锁，那不会是好事情。那会变得非常糟糕非常快。我们不能允许那样。另一件事是，我的意思是，如果你使用 kmem_cache_alloc 之前，那是我们有的问题。如果我们使用 kmem_cache_alloc，那会是另一个选项。问题是那样也会破坏锁（clobber the lock）。你可以想象一些锁，设置零就释放它，但问题是因为它被释放了，并不意味着没有读者在关注它。所以你可能会遇到一个读者试图获取锁，就在我们清零了那个东西的时候，那也会很糟糕。因为它会以某种方式自动释放所有那些读者的锁。
所以目前，发生这种情况的原因，以及你可能会尝试做的事情，对吧？你可能会做 kmem_cache_alloc。你可能会做一个条件初始化。那是那边的红色框。我们以前直接去“未使用”。问题是当我们获得一个新的slab时，它不是零填充的。所以那意味着如果我们做了一个 kmem_cache_alloc，而我们得到的内存是刚新分配的，还没有经过 kmem_cache_free，它刚从空闲页出来。它里面有任意的东西。所以我们没有办法决定如何初始化它。现在，很可能我们应该改变这点。可能Linux内核真的需要一种方式来说，嘿，这是一个 SLAB_TYPESAFE_BY_RCU 的东西，所以请把新页清零。那可能值得研究。因为如果你那样做，那么你就可以只用一个自旋锁。当你转回来时，自旋锁会保持为一个自旋锁。你会检查是否有一个标志被设为零。如果是，抱歉，你可以，如果标志是零，你知道这是一个刚进来的新slab。你会把它设为一，而标志为一会告诉你它已经初始化过了。你不需要初始化它。好的。但那是以后的事情了。
读者需要原子操作吗？结果是不需要。我原以为需要。John Carr不久前给我解释了。如果你想查邮件，下面有链接。技巧是，AXP4（一个架构）使用了这个，你可以有另一个你持有引用的对象，并且你可以知道类型安全项（type safe item）比那个稳定项（stabilized item）有更长的生命周期。在那种情况下，仅仅因为你持有那个另一个对象的引用，而类型安全项绑定到它，持有对它的引用，你就可以只做非原子地检查那个，就没问题了。好的。所以那有点巧妙。那对我来说是个惊喜。与Linux内核社区合作的另一个有趣之处。
要从RCU转到类型安全内存，有点像转到存在保证，只是对于堆分配器，你有了一个slab分配器。并且你不是总是有延迟回收，你只在slab上才有延迟回收。所以当你把页交回时，你在那时延迟回收，而不是在每次释放时。
所以让我们看看轻量级垃圾收集器。我要… 我要做的是，我们将快速过一遍这个。它在概念上有点简单，但细节可能有点难看。可能发生的一件事是，非阻塞算法会受到一种叫做ABA的问题的影响。发生的情况是，重新分配的内存可能导致失败。所以一个例子是FIFO栈，一个原子FIFO栈，你推送（push）和弹出（pop）单个元素。好的。如果你推送一个元素并弹出整个列表，那么生活很美好，但那并不总是你想要的。
所以我不打算详细讲解代码。但我会说，所以这是推送，这是弹出，但它有bug。为什么有bug？嗯，那是下一张幻灯片。
所以假设我们有一个栈顶，我们有像之前那样的列表，上面有 cat 和 tux。好的。现在我们尝试弹出顶部的元素，弹出操作被抢占（preempted）了。所以第一个弹出操作 list_pop_one 拥有旧的指针，指针 next，它现在要做的就是把这些交给比较交换（compare swap）。想法是，如果旧指针和 top 相同，那么就可以让 top 成为 next 指针。那将自动把 cat 从列表中拉出来，让列表顶部是 tux。除了这个被延迟了或被中断了之类的。它被延迟了。同时，有人做了一个列表弹出（list pop）。嗯，他们把栈顶从列表弹出了。现在列表只有 tux 了。被抢占的列表弹出仍然有 cat，但它在空闲列表上。所以它有点像是 cat 的幽灵（ghost）了。我们可以有第二个，第三个列表弹出。tux 现在也没了。所以我们的两个指针都指向了那些曾经是真实东西的空闲列表。然后其他人可能做一个列表推送 dog，并碰巧重新分配了 cat。所以现在 old_p 指向这个现在是 dog 但曾经是 cat 的东西。我们假装编译器能对此感到不安并向你吼叫，导致各种丑陋的事情发生。但我们假装我们有一个简单的编译器，或者我们小心地使用了原子操作之类的东西来让编译器不碍事。所以 old_p 指向 dog，但 old_p->next 仍然指向 tux。
现在假设原始的列表弹出恢复了。好的，所以它处于这个状态，它有一个指向 dog 的指针和一个指向 tux 的指针。所以它做了这个比较交换（compare and swap）。嘿，猜猜怎么着？old_p 等于 top，所以比较交换成功了。一旦我们做了那个，我们就有了一个指向空闲列表的列表，这真是个坏主意。好的，这就是臭名昭著的ABA问题。所以我们有一种情况，一块特定的内存改变了角色并给我们带来了问题。
我们可以通过阻止 cat 的重新分配来防止这种情况。我们可以做到的方法，我不会详细讲，但我们在原子操作周围放了一个RCU读端临界区。这就是我之前提到的情况，我们总是在做更新，但RCU仍然有用。
所以这里发生的是，如果有人从我们下面释放了 cat，它在我们完成比较交换之前不能被重新分配。事实上，在我们完全完成比较交换循环之前都不能被重新分配。所以那意味着要么比较交换成功，并且它还是原来那个元素，要么如果它是一个不同的元素，如果那个元素已经从栈中被移除，被弹出了，那么比较交换保证会失败。好的？所以我们使用RCU读者，显然我们还必须延迟释放节点。这是一个使用存在保证而不是类型安全内存来使其工作的案例。我们必须在每次释放前等待宽限期（grace period）。通过这样做，我们使得简单的非阻塞（NBS）代码不需要为了在没有延迟回收的情况下工作而添加一大堆其他“毛发”。所以这是那个我们之前在幻灯片中看到的左下角红色三角形的情况，我们几乎总是在做更新，但RCU仍然可以发挥作用。这再次让我感到惊讶，如果是20年前的话。活到老学到老。
所以我们在这里为类型安全内存添加的是非阻塞同步。有了这个，我们可以转到准读写锁（quasi reader, writer lock）。但我要跳过这个，因为我们已经讲过了，它只是在这里讲了几件事。
我们将做的是看看多版本一致性控制（multiversion consistency control）。好的？现在，它做的是，你可以把RCU看作是在给你版本。你只是发布一个新版本。你做 rcu_assign_pointer。你订阅它。他们可能发布一个新版本，其他一些读者可能得到那个其他版本。所以你可能有，正如我们看到的，多个读者同时拥有不同的版本。这就是空间同步（spatial synchronization）在帮助我们，所以我们不必强制性地、排他地使用严格且昂贵的时间同步（temporal synchronization）。这实际上是Linux内核中使用的。dentry缓存，入口缓存（entry cache）使用它，dcache。它有助于路径名查。它的工作方式是，给你一个路径名，你想找到相应的inode。它所做的就是遍历一个内存中的目录项缓存。它无锁地做这个。如果发生了一些不好的事情——对于相当多“不好的事情”的值——我们回退到一个更重度同步的遍历，或者我们可能只是重复无锁遍历，取决于发生了什么。
一件不好的事情是，你可能在做路径查找，你到达一个不在目录项缓存中的段（segment），因为它还没有从磁盘加载。现在，这个代码非常复杂。Neil Brown做了一个很棒的LWN系列，在下面的URL中有展示。我们要做的是，通过一个极其简化的版本来展示处理版本所涉及的工作。
好的。首先，从如果你没有多版本控制会发生什么开始。假设我们有一个文件系统有这两个路径名。这个路径名存在。有一个路径名，那个东西可能不存在作为另一个路径名。我们正在查找这个不存在的路径名，说实话，广告里也说了，它确实不存在。所以将要发生的是，我们无锁地沿着路径向下走。我们有RCU保护，所以我们不必担心东西从我们下面消失。所以“this”找到“this”。“path name”继续前进。“does”也找到“this”那个东西。然后有人做了一个移动 this/pathname 到 that。好的。所以我们要把左边第二个（从顶数）的路径名框（path name box）移动到右边顶部的“that”框下面。换句话说，像这样。好的，所以“砰”一下，它被移过去了。我会再做一次那个转换。我们从这里开始。我们做了那个移动命令，最后像那样。
现在，当你做那个操作时，dentry缓存中的dentry元素不会改变身份。所以我们持有的指针仍然有效。所以遍历仍然在查看下面的“does”框。但这还不够。让我们再做一次。假设我们做 mv that/might/not。所以“that”是右边从底数第二个框。把它移到“that/pathname/does”下面。所以中间那个“does”框。我们要做那个移动。我们要那样做。换句话说，我们把“not”框移到“does”下面。我会重复那个。我会倒回去再重复一次，好让你看到它。现在读者继续。嘿，现在有个“not”了。太好了。我们找到了它。猜猜怎么着？还有一个“exist”。所以发生的是我们匹配了这个路径名。我们找到了一个和“that”对应的“exist”东西。但那个路径名在整个过程中的任何时间点实际上从未存在过。好的？在整个过程中从未存在过 /this/pathname/does/not/exist。有些人争辩说这种行为完全没问题。但很多应用程序真的不喜欢那种事情。而Linux内核阻止了它。好的？所以Linux内核不会查找从未存在的路径名。或者至少如果它查了，那是个bug。
那么我们如何避免这种竞态条件？我们所做的是使用RCU，但我们也使用序列锁（sequence locking）。这些，再次强调，有不同的角色。RCU使无锁遍历安全。它防止东西在我们下面被释放。而序列锁检测重命名。所以我们可以确定我们是否可能遍历了一个从未真正存在的路径。我们快速看一下序列锁的核心API。read_seqbegin 启动一个读者。read_seqretry 检查是否有干扰操作发生。好的？write_seqlock 启动一个写者，write_sequnlock 结束一个写者。所以发生的是，每个重命名都被包裹在 write_seqlock 和 write_sequnlock 中。那意味着如果你做了 read_seqbegin，当你做了并做了 read_seqretry，如果与重命名有任何类型的重叠，read_seqretry 会说，嘿，你必须重试。发生了不好的事情。
所以那意味着我们可以做类似这样的事情。再次强调，这是被粗暴简化的。如果你想要更多介绍，那里有LWN文章。当然，源代码是最终权威。所以我们取一个变量 seq，赋值为 read_seqbegin，我们用的是这个重命名锁。重命名操作，再次强调，将在同一个东西上做 write_seqlock 和 write_sequnlock。我们做 rcu_read_lock，然后我们做一大堆复杂的事情来遍历目录项缓存，这可能涉及跨越挂载点。它可能涉及符号链接、目录、硬链接，整个流程，所有可能发生的事情。最终我们做 read_seqretry，我们再次给它重命名锁，并给它我们传入的 seq。如果它返回真，发生了不好的事情，我们做点什么来重试。我没有给重试打标签，但我们去到某处说，嘿，发生了不好的事情。我们必须处理它。如果 read_seqretry 返回假，那意味着没发生坏事。我们可以直接做 rcu_read_unlock，宣布成功并感到高兴，知道我们无锁走过的这个路径名在遍历期间确实存在过。
好的。所以如果我们回到我们的查找，这种情况仍然可能发生。我们仍然可能走到下面并得到那个“exist”，但我们在路径名查找期间发生了两次重命名。那意味着序列，seq 变量将不再有效。所以 read_seqretry 会在那时失败并说，嘿，你知道，是的，你查到了这个，但它是错的。离开池子做点别的，因为这个没成功。所以发生的是，我们使用RCU使遍历再次安全。序列锁拒绝不一致的遍历。它拒绝与重命名发生竞态的遍历。而这所做的只是识别一个版本。它只是验证整个读操作发生在单个版本的上下文中。本次演讲中我们不会讨论它们。有更复杂的方案可以允许不同版本的并发遍历，一致的并发遍历。我现在做得很好。让我再试一次。有更复杂的方案可以允许不同版本的并发遍历。这个代码是由… 最初由Sony在大约15年前尝试过。后来Nick Pagan做了升级。现在Vero（可能是笔误或昵称，指Viro？）把它变成了今天的样子。Christoph Helwig参与了很多审查和升级。当然，正如我们所知，Neil Brown也参与其中，可能还有其他贡献。所以这是一段非常令人印象深刻的代码。一段很酷的代码。向这些家伙致敬，他们让它工作并保持工作。它确实对路径名查找（path name lookup）做了重大的改进。
好的。如果我们拿RCU来做准多版本并发控制（quasi multi-version concurrency control），我们从存在保证开始。我们需要读者有某种快照操作。那就是 read_seqbegin 调用，它返回给我们序列号。并且必须对读者和写者有约束。你可以使用单个对象。我们在这个例子中使用了序列锁。有一大堆方案使用版本号。那些允许多个并发读者同时进行不同版本的操作。然后还有Issaquah挑战（Issaquah challenge），它有一个更弱的并发一致性标准。好的。
我们可以讲准引用计数（quasi-reference count）。它在右上角那里。RCU是一个有点奇怪的东西，因为它可以算是一种隐式引用计数（implicit reference count）。你可以把 rcu_dereference 看作获得对对象的一个引用，这个引用限于包围它的RCU读端临界区内。所以你做了 rcu_dereference。你得到一个对象，你就有了一种奇怪的隐式引用。那个引用一直存在直到你做 rcu_read_unlock。你也可以认为RCU提供批量引用计数。你可以认为 rcu_read_lock 获取了系统中每一个受RCU保护的对象的引用。好的。所有对象都以接近零的成本。但再次强调，你将被限制在包围它的RCU读端临界区。当你到达匹配的 rcu_read_unlock 时，那些引用就消失了。
现在，代码看起来是什么样的？嗯，其实你已经看过了。你可以把之前看过的任何数量的代码示例解释为准引用计数。我的意思是，你有 rcu_read_lock，你有 rcu_dereference。你可以争辩说那些是在获取引用，而不是你想要的任何其他方式。这可能看起来很奇怪。我的意思是，同样的代码怎么可能是锁和准读写锁和准引用计数？这里发生了什么？答案是，生活就是这样。好的。如果你有一个 atomic_inc，它在做什么？
嗯，那个 atomic_inc 可能在做很多事情，对吧？它可能是在获取一个引用计数。如果你知道你已经有对一个对象的引用，你可以做一个 atomic_inc 来再获得一个。所以你有两个对该对象的引用。也许你想传递一个给其他线程或什么的。好的。
它可能是在做一个统计。你可能在用 atomic_inc 计数一个统计。希望那是一个非常少被计数的统计，因为如果你用很多CPU频繁做 atomic_inc，它会变得相当昂贵。但那可能是它的用途。它可能是在推进一个并发状态机（concurrent state machine）。你可以用 atomic_inc 推进到下一个状态。好的。你可以用那个做很多事情。所以你在使用 atomic_inc 这一事实并不一定告诉你很多关于意图的东西。RCU也是如此。好的。RCU有你能够使用的原语。你可以使用 rcu_read_lock 和 rcu_dereference。你可以把它看作某种读写锁。你可以把它看作某种引用计数。或者某种多版本并发控制。对吧？很大程度上取决于情况。很多时候当你使用RCU时，你是在拿现有的代码应用RCU。它将控制的，真的，是旧代码在做什么。所以如果你的旧代码在使用读写锁，你很可能并且很可能应该认为你在使用RCU作为一种准读写锁。如果它一开始使用引用计数，或者你使用RCU来替换那些引用，那么你可能需要把它看作准引用计数。如果它有某种显式的版本控制，而你使用RCU作为一种更轻量级的版本控制，你可能想把它看作准多版本并发控制。所以这就是诀窍。如果你有一些原语，你可以以多种不同的方式使用它。atomic_inc 和 RCU 是同样的事情。
所以要从RCU转到准存在… 抱歉，准引用计数，我们从存在保证开始。我们有RCU读者作为单个或批量无条件引用获取。在某些情况下，你会想要桥接到一个每个对象的锁或引用。例如，你可能正在使用RCU作为引用，但需要做一些会休眠的事情，那样的话，如果你有时需要做那个，你可能想要在对象本身获取一个物理引用，然后退出RCU读端临界区。网络做类似的事情来处理往返延迟。
好的。所以我们在这里。我们在12月和现在讲完了所有这些。所以我们过完了整个列表。我想再次强调责任范围。当你处于陈旧和不一致数据是可以接受的，并且你主要是读操作（mostly reads）的情况时，RCU最容易使用且效果最好。这就是为什么它最初出现在网络中。网络是它的一个典型代表（poster boy）。你在网络中有路由表（routing table）。但出于各种原因，路由信息在互联网上传播得相当慢。如果你试图传播得太快，最终会产生各种奇怪的故障模式，路由来回翻转。这非常丑陋。你有数据包永远绕圈。所以他们人为地减慢路由更新以促进稳定性。所以那意味着在路由更新到达系统时，你已经把数据包发错方向相当长一段时间了。所以让它们继续发错方向一小会儿，等读者完成，并不是什么大问题。
在某些情况下，你需要一致的数据。读-修改-写通常需要一致的数据。我们看到了一个可能发生这种情况的例子。那就是我们在对象上加锁的情况。所以我们使用RCU以无锁方式遍历某种搜索结构。所以如果我们有一个树，例如，我们避免了在树的根部的全局锁瓶颈。我们只是用RCU遍历它而没有瓶颈。我们在树的叶子上加锁，这意味着我们可以把争用分散到树的所有叶子上，并保持相当低的争用。那样，我们在需要一致性的叶子层级获得一致性，并且在搜索结构本身没有巨大的争用。
另一种我们有读、写并且需要一致数据的情况，RCU可能没问题。dentry缓存可以被认为是这种情况的一个例子。有很多工作负载非常频繁地添加和删除文件和目录。但事实上我们避免了根inode上的巨大锁定瓶颈，意味着即使我们在改变树，事情也能相当好地工作。另外，我们是在改变树的某个部分，而有很多流量正通过树的其他部分，那些部分不受更改的影响。所以dentry缓存是黄线的一个例子。
我们在红色区域（red zone）看到了一个非阻塞数据结构的例子，带有单元素推送和弹出，它实际上也能工作。仍然，是的，我喜欢RCU。我是它的共同发明人之一，和Jack Slingwine一起。我从中获得了很多乐趣。但重要的是为工作选择合适的工具。我的意思是，有时RCU是合适的工具。那很棒。我喜欢那样。但如果RCU不是合适的工具，你应该用别的。所以你可以争辩说RCU是一个专业化的东西。它是专业化的。事实上，我会争辩它是专业化的。为了大致了解它有多专业化，一个有用的事情是把它和读写锁（reader-writer lock）比较。如果你看看读写锁在Linux内核中的使用情况，并与RCU比较，证据表明RCU的使用强度大约是读写锁的四到五倍。所以你可以争辩说读写锁比RCU专业四到五倍。另一方面，普通的排他锁的使用频率大约是RCU的十倍。所以你可以争辩说有一个谱系，也许读写锁是锤，RCU是螺丝刀，大约占锁使用量的十分之一，读写锁是… 我不知道，扳手之类的，大约占排他锁的四十分之一或五十分之一，或者RCU的四分之一或五分之一。这只是大致让你了解整体情况。
以及RCU的适用性。理论上，你可以在使用RCU的大多数地方使用读写锁，但我们看到读者-写者锁所隐含的全局达成一致，对于多处理器来说是一个真正的问题。
好的，让我们总结一下。正如我们之前看到的，RCU在空间和时间上同步，并且它们是交织在一起的。所以时间和空间紧密地协同工作，这使我们能够获得接近零成本的读同步。我们浏览了几个RCU用例的例子。我们在那里看到了它们。再次强调，和12月一样，RCU肮脏的小秘密是它极其简单。语义相当直接。我们看到一张有四个象限和蓝色框的幻灯片。但为了好好利用它，你必须改变思考问题的方式。我希望这两次演讲，12月的那次和今天的这次，能帮助你理解如何不同地思考你的问题，以便在合适的地方使用RCU。
再次希望这有助于理解RCU，但老话说得好，就像12月说的，我听，我会忘记；我看，我会记住；我做，我才会理解。能够看到并记住是一个有用的状态。如果你所做的只是看这个演讲，它可能有助于你审查代码或者理解代码在做什么。但如果你真的想彻底理解RCU，真正严肃地理解它——不是每个人都需要，但在我看来如果更多人理解会更好——你真的需要动手实践。它在Linux内核中当然可用。也有用户空间RCU库可用，如果你喜欢使用用户空间调试器的话。你实践它，看看它能做什么，对它做测量。但那是真正深入理解它的方法。
所以我们在这里。我们完成了。它们现在都是蓝色的了，因为我们都讲过了。我们有这张幻灯片，和12月的相同，除了它告诉你第一部分在哪里。那么，到此为止，开放提问。感谢你们迄今为止的时间和关注，以及对RCU的兴趣。
Paul，我有一个问题。我想知道，你刚才在几张幻灯片前提到，RCU，像任何其他工具一样，它需要被应用在它合适的地方，对某些情况好，对某些情况不好，对吧？所以你能讲讲内核中你认为RCU适用和不适用的例子吗？
好的。是的，这是个好问题。
所以这是你说的那张幻灯片，对吧？正确。好的，很好。那么我举几个例子。早期的成功案例之一是安全。在90年代，Linux只是一个转发邮件、打印、提供磁盘服务、用于一般用途的东西。安全并不是什么大事，原因有几个。一是Linux没有被用于真正重要的数据。第二是当时的互联网友好得多，好吧？但随着2000年代初企业兴趣的出现，安全变得更加重要。所以像安全策略这样的东西被添加了。我想是Kega Kohai，还有James Morris。他们决定添加后来成为SELinux的东西。那最初意味着在每个系统调用上获取一个全局锁。他们的问题是，它在4核上运行良好，但到了32核，你就卡在那个锁的争用上了。他们发现了RCU并应用了它，性能得到了巨大的提升。原因是，当然，你有一个安全策略，但它是在某个时间点由某个高管设定的。然后它向下渗透，人们才真正实施它。所以你可能在安全上做错事已经好几周了，可能。所以，再多几毫秒又怎样？这为他们带来了线性可扩展性。事实上，SELinux的性能损失是存在的。你能看到。但只是几个百分点，而不是数量级。所以这是一个效果非常好的案例。
在另一端，dentry缓存的效果比我预期的要好得多。我原以为我们得慢慢迁移。我们确实迁移得很慢。花了整整10年时间才达到今天的水平。但我引以为豪的故事是在2004年Linux Conf.au，我第一次参加。我们一群人在一个家伙家吃晚饭，他是个BSD黑客，现在退休了。很抱歉，我忘了他名字。我真的感觉很糟糕。总之，他在阿德莱德附近的家招待了我们所有人。他碰巧在他的办公室里并排放着一台BSD系统和一台配置相同的Linux系统。当然，我们很快就想出了一个基准测试，就是在Linux源码树上做一个 find。所以我们拿了一个tar球（tar ball），在两台机器上都放了一个Linux源码树，在BSD机器和Linux机器上都做了 find，同时可能还有其他东西在运行。我不记得确切的基准了。但它在Linux上10秒就完成了。而在BSD系统上，过了好几分钟还在运行。好的？碰巧Linus也在场，他看着我说，我为我们的dentry系统感到非常自豪。我无法告诉你那感觉有多好。听他这么说。我当时所做的只是提供RCU。dentry本身是Manish Soni的工作。当然，后来Nick和Al接手了它。好的。
那么RCU有什么不好的地方？给我一个它不起作用的例子。一个我们至今仍有问题并且正在努力解决的例子是MAPSEM（mmap_sem）。好的？那是一个读写信号量。有些工作正在进行以尝试推动事情进展。Peter Zijlstra在2010年启动了推测性页错误（SPF, Speculative Page Fault）。Laurent Dufour几年前接手了它，最近Michelle Lepinasse接手得更多。所以这已经进行了大约12年。还有一个MIT的研究项目也做了让它使用RCU的东西，但在某些工作负载上出现了性能下降，不幸的是是重要的工作负载。那是在2013年的ASPLOS。而推测性页错误路径尝试在不获取MAPSEM的情况下处理页错误，并使用各种技术来判断那样做是否有效。如果不行，就用困难的方式重新获取MAPSEM。另一部分是Matthew Wilcox和Liam Howlett的工作。他们一直在研究枫树（Maple Tree）变体，它允许部分搜索在RCU保护下进行。我相信它避免了回退路径。这两个补丁集正在朝着那个目标前进。SPF对Android来说非常有用。它在应用程序启动时间上有20%的速度提升，以至于许多Android厂商将SPF作为树外补丁（out of tree patch）应用。如果你在运行Android，你很可能运行着那个补丁，如果是较新的Android。所以，你知道，它已经在生产环境中使用了，尽管它很难进入主线。所以我们看看情况如何。
另一个是部分应用的例子。PowerPC在页表结构上有RCU保护。这样做将允许无锁的 /proc 条目。所以这些是RCU过去有困难的地方。它没有被使用。我们也许能部分覆盖MAPSEM，但目前我们没有野心完全消除它。也许我们将来能做到。所以带有MAPSEM的MM（内存管理）系统是RCU遇到一些困难的一个例子。可能还有其他一些。这是立刻想到的那个。这是个好问题。我其实有过一个问题。我在2012年做学术演讲。其中一个家伙说，好吧，那么RCU什么时候接管世界？我说，不，它不会。我的意思是，我们使用排他锁进行更新，例如。但我认为它是一个非常有用的工具。它得到了很多应用，我非常高兴。我很高兴它能得到更多应用，但我也很高兴了解其他同步原语以及它们如何让事情运转。所以好问题。还有其他问题吗？
谢谢你解释那个。太棒了。因为我知道我们谈论RCU很多。我们在内核中使用它很多。这让我对它在何时有用有了一个清晰的认识。另一种找到更多的方法是，只需查找 read_lock 和 write_lock，以及各种信号量和互斥锁的读端原语，看看那里有什么。对的。
好的，很好。那么，如果没有其他问题，我很高兴结束这次会议。非常感谢大家今天的时间。谢谢你，Paul，为我们讲解这个主题。也谢谢你，Shua，在这里为我们解答问题。我们希望在未来导师会议上见到大家。这个录像今天晚些时候会上传到我们的YouTube。再次感谢大家。祝大家有美好的一天。谢谢大家。