关注了就能看到更多这么棒的文章哦～

Lockless algorithms for mere mortals

By Jonathan Corbet
July 28, 2020
https://lwn.net/Articles/827180/
DeepL assisted translation

正如人们所说，自然界要想确保所有事情别一下子同时发生，就是靠 time（时间）。在今天这些高度并发的计算机中，time 本身并不足以让事件按期望地进行。这个任务更多是在依靠一组丰富的 locking primitives （加锁操作）上，而在这些操作之下，则是被称为 Linux kernel memory model 的格式内存模型。不过，想要真正理解 memory model 需要一种特殊的思维方式，缺乏这种“超能力”的内核开发者在 memory model 起作用的领域进行开发工作时很可能会犯错误。但是呢，要想提高系统性能，就非常有必要在这个层面上来进行开发工作。最近的一次对话，就指出了内核可以让普通内核开发者更容易完成这种工作的方法。

当多个线程同时访问相同的数据时，就会产生并发（concurrency）问题。哪怕在非常简单的世界里，在这样的情况下要想让一切都保持一致性（coherent），也是很有挑战性的。内核通过使用 spinlocks、mutexes 和其他可以控制并发性的加锁操作来防止并发中出现错误的顺序。这些锁可以被认为是类似于城市中的交通灯：只要大家都遵守，就能防止事故的发生，但代价是会让驾驶中经常不得不停下来。等待锁的时间影响很大，甚至在 memory 和 cache 之间交换 lock 数据的这些时间也会伤害软件的可扩展性，所以开发人员经常需要寻找方法来避免使用 lock。

Lockless list linking

我们来考虑一个高度简化过的例子：在一个单向列表（singly-linked list）中插入一个 element 的过程。一种解决方案是使用一个 mutex 来保护整个 list；任何要遍历 list 的线程都必须首先获得这个 mutex。如果插入 element 的线程获得了这个锁，它就知道没有其他线程会在此时此刻遍历这个列表，所以这时做的改动都是可靠的。但是如果这个 list 到处都在使用，那么这种锁机制会很快让性能下降。

所以可以考虑采用 lockess（无锁）的替代方案。如果这个列表最初的样子是这样的：

这样我们可以先将新 element 中的后向指针指向指向我们要插入的位置之后的那个 element。

此时，对于任何其他正在遍历这个 list 的线程来说，它看到的 list 并没有什么改变。接下来为了完成插入操作，需要把列表中的前一个 element 的后向指针重定向到插入的这个 element。

现在，每个人都能看到新的 list，这里不需要加锁，list 对于它的使用者来说，看起来总是一致并正确的。或者说，人们希望如此。

问题是，现代硬件为了提高性能，让事情变得更加复杂了。这时，按顺序进行的一系列操作的执行顺序，在其他线程看来可能并不是这个顺序。举例来说，系统中的其他线程很可能看到上面两个指针的修改顺序是相反的，结果，从它们的角度来看，有一个时间窗口之中这个 list 是这样的：

新 element 中的后向指针的内容还不正确，可能是随机值，这回导致 list 的遍历动作到此为止了。世界上很少有 100%确定的事情，但我们有理由相信出现这种 list 错误时不会有什么好结果。

A more complex view of memory

另一种理解方式可以是这样的：locking 提供了一种牛顿物理学的世界观，在给定的情况下，人们总是知道会发生什么。在更底层的实现上来说，这里的规则却开始类似于量子物理，很可能会发生一些令人惊讶的事情，很少有人能让别人信服他真的能了解这一切。在这个世界上，不了解量子物理学的人通常可以很好地生活，但有些情况下有专家在身边是件好事。

Linux 内核就有一些这样的专家；他们多年来在创建内核的 memory model 方面做了大量的工作，它描述了内核如何看待内存，以及如何安全地执行那些可能涉及并发的操作。其结果就是著名的 memory-barriers.txt 文档和大量的参考资料。从这个文档中，我们可以学到一些对上面给出的 list-insertion 例子有用的内容。

• 遍历列表的代码应该用 "acquire"操作来读取后向指针，这是一种特殊的 barrier。它保证在 barrier 之后发生的任何操作对于系统中任何观察者来说，都是在 barrier 之后才会发生的。这样它就可以保证，在 list 遍历过程中读到任意一个 element 的指针时，它 element 的 "next "指针的赋值已经完成。

• 修改指针的代码则应该用 "release "操作来进行，这样可以确保在 release 操作之前所做的任何其他操作都在看到 release 操作之前确保已经完成。这就保证了新 element 的 "next"指针在 element 本身的指针之前生效，对于任意一个观察者来说都是如此。

这个例子足够复杂，但这是我们要讨论的话题中最最简单的一个例子，大多数情况实际上更加复杂。更糟糕的是，人们在优化编译器时，为了追求更高的性能，也会制造不少意外现象。内核的 memory model 也在努力解决这个威胁。

The problem with the memory model

最近，Eric Biggers 发布了一个 patch，修复了 direct I/O 代码中发现的一个问题，即并发数据访问的情况下没有使用合适的 barrier。有一些讨论，大家在争论这里是否真的存在 bug。根据 Biggers 的说法，问题在于这种并发访问被认为是 "undefined behavior（未定义的行为）"，这意味着编译器有权采用任何它有兴趣的实现方式。不过，这里真正的争议是关于这个 fix。

Dave Chinner 被公认为是一个技术很不错的内核开发者，他抱怨说，改动后的代码并不容易让人理解。

I'm talking from self interest here: I need to be able to understand and debug this code, and if I struggle to understand what the memory ordering relationship is and have to work it out from first principles every time I have to look at the code, then that is bad code.
译：我是出于自身利益的考虑 我需要能够理解和调试这段代码，如果我需要先努力理解这里的 memory ordering，而且每次都要从最基本的规则出发来研究它，那么 这就是糟糕的代码 。

有人指点他看 memory-model 文档，但没有改变他的看法：

The majority of the good programmers I know run away screaming from this stuff. As was said many, many years ago - understanding memory-barriers.txt is an -extremely high bar- to set as a basic requirement for being a kernel developer.
译文：我认识的大多数非常棒的程序员见到这些东西都会尖叫着逃跑。就像很多年前说过的那样--理解 memory-barriers.txt 对于一个内核开发者来说，属于一个极高的门槛了。

他说，这个文档是针对那些花时间思考 memory-ordering 问题的人。其他所有人要想读懂，都得从使用的基本术语开始很费力地研究。即使是那些想方设法终于理解了这个文档的人，一旦回到他们要解决的实际问题上，也很可能会很快就忘记这些内容。Chinner 认为，内核开发者最好能有一套简单的规则，来告诉他们如何能写出安全的 lockless 代码。

Biggers 的回应是发布了一个 "initialize once" pattern 的文档 patch，这个 pattern 就是 direct I/O 子系统中问题的根源。当一个数据结构的初始化被推迟到该结构被实际使用时（也许是因为可能永远不会使用），就会发生这种 pattern。初始化应该确保只完成一次，两个竞争线程不应该同时尝试进行初始化动作。该文档提供了几个复杂度逐步提高的方案，供各种不同性能要求的场景下使用。

虽然大家很欢迎他的态度（试图提供有用的方案），但很明显，一些人认为这种努力有些错失了问题的焦点。例如，Darrick Wong 指出下面这样的语言对于多数开发者来说，很难一下子理解：

Specifically, if all initialized memory is transitively reachable from the pointer itself, then there is no control dependency so the data dependency barrier provided by READ_ONCE() is sufficient.
译文：具体来说，如果所有初始化的内存都可以从指针本身中转到达，那么就不存在控制依赖，所以 READ_ONCE()提供的数据依赖内存屏障就足够了。

Alan Stern 试图对此进一步解释：

Specifically, if the only way to reach the initialized memory involves dereferencing the pointer itself then READ_ONCE() is sufficient. This is because there will be an address dependency between reading the pointer and accessing the memory, which will ensure proper ordering. But if some of the initialized memory is reachable some other way (for example, if it is global or static data) then there need not be an address dependency, merely a control dependency (checking whether the pointer is non-NULL). Control dependencies do not always ensure ordering -- certainly not for reads, and depending on the compiler, possibly not for some writes -- and therefore a load-acquire is necessary.
译文：具体来说，如果到达这个初始化过的内存的唯一方法是去引用指针本身，那么 READ_ONCE()就足够了。这是因为读取指针和访问内存之间会有一个地址依赖性，这样可以保证正确的排序。但是如果初始化后的某些内存是可以通过其他方式到达的（例如，如果是全局数据或静态数据），那么就不是地址依赖关系，而是一个纯粹的控制依赖（检查指针是否为非 NULL）。控制依赖并不总是确保先后顺序——对于读操作来说不会保证，并且根据编译器的不同，对于某些写操作来说也不确保顺序——因此这里需要添加一个 load-acquire。

这一下子就把整个讨论又推回了起点：大多数开发者并不这样看待内存，而且真的不希望这么做。他们根本不会用这种方式来思考。如果 lockless 的算法必须要完全理解这种逻辑，那么人们就不会愿意使用 lockless 的算法，并且相关的具体实现很可能会有一些微妙的错误。

正如 Matthew Wilcox 所建议的，另一种方法是为这种 on-the-fly initialization 定义一个 API，并隐藏其底层实现细节。了解 memory model 并喜欢思考 memory model 的开发者可以关注于优化这个 API 的底层实现，而其他内核开发者则可以简单地使用它就好，只要知道这个 API 可以让系统正常工作就好。随后，又有了许多讨论都是关于这个 API 应该是个什么样子的，有几种不同的想法，但是没有哪个看起来可以广泛应用的。

这个讨论已经渐渐冷却下来了，但根本问题仍然存在。多层软件开发的成功取决于是否控制住了复杂性，但这在 memory model 这个 level 还没有真正达到。迟早会有人点亮正确的技能树，既能理解 Linux 内核 memory model，又能把它隐藏在一套 API 里让其他开发者无需理解该模型就能安全使用。在那之前，编写 lockless 的代码对于许多开发者——以及必须 review 他们的代码的人来说，仍然是一项非常有挑战性的任务。