【译】一种无锁环形缓冲区-LWN

November 11, 2022

Translate from: [A lockless ring-buffer LWN.net]

去年的Linux峰会和Linux前线会议就有(计划创造一种底层的ring-buffer实现)[http://lwn.net/Articles/300992/]，用于解决各种Linux内核和用户层之间数据跟踪的场景。虽然在2.6.28版本的内核中已经可以找到一种通用的ring-buffer，但是过度依赖锁的实现，性能上不尽如人意。最近，Steven Rostedt提出了一种无锁算法，在写入时完全不使用锁，非常适合跟踪的场景。

因为跟踪信息都由内核收集，就要求能够快速保存，所以对于事件耗时的观测以及总的系统性能影响应该非常小。而读取数据则是在用户空间，所以对于性能的要求可以适当放宽。目前的ring-buffer是基于环形双向链接的页表，包含一个头指针和一个尾指针，从尾端写入头端读取。

如果一个ring-buffer满了，或者将要满，写入者就会覆盖头端页表的数据，但是也会破坏正在读取的数据。新的算法实现中，被读取的页面和环形链表相分离，所以就不用担心被写入者的破坏。但是使用分离的读取页面在当前页表读取完成，然后重新放回链表并取出下一个的时候有一些额外的动作。读取页表必须要正确放回尾页表之后，然后取出当前头页表作为新的读取页表，头页表也更新指向下一个。这里必须使用锁。

从如下来自Rostedt的这篇ring-buffer-design.txt中的示图，可以大概理解新ring-buffer的结构。善于观察的读者应该注意到了H代表的指针表示带有HEADER标记的指针。

              reader page
                  |
                  v
                 +---+
                 |   |------+
                 +---+      |
                            |
                            v
        +---+    +---+    +---+    +---+
    <---|   |--->|   |-H->|   |--->|   |--->
    --->|   |<---|   |<---|   |<---|   |<---
        +---+    +---+    +---+    +---+

写入操作可能被后面的其他写入中断，并且要等到中断进程写入完成，被中断的写入才能继续。暂停的操作被记录到中断栈，以保证整个ring-buffer结构的完整性。一个写入操作开始后，尾部之后的一个页表必须独占直到写入完成。但是开始写入时尾指针就会更新，所以需要另一个提交指针(commit pointer)来跟踪尾部已经完成的写入操作。

在一个空的ring-buffer中，读端页表也可能是尾端页表或者提交页表。但是当读端页表从ring-buffer中分离后，next指针依然指向下一个ring-buffer单元。每一次的写入操作完成，提交指针和尾端指针只会简单的顺着next指向下一个页表。

为了移除目前用于同步头端、尾端和提交指针更新的写锁，Rostedt提到了目前许多处理器都已经支持的cmpxchg()原子操作。他是这样工作的：

   R = cmpxchg(A, C, B) 
        - 如果 A == C 执行赋值操作 A = B
        - 然后无条件返回 A

如果再次检查发现R等于C，那么赋值成功。

算法还要求页表必须是4字节对齐的，这样底部的2比特就可以作为标志位。2个标志位的作用：

HEADER - 当前指针指向头端页表
UPDATE - 当前指针指向一个正在被写入的页表，或者说即将成为头端的页表

只要使用exchange()操作这2个标志，就可以实现无锁的写缓冲

上一个读端页表操作完成时，当前头端指针成为新的读端页表并且需要从链表中剥离。读取者会先检查指向头端页表的next指针中的HEADER标志位，所以无锁写入也不会干涉到读取操作。把读端页表放回链表的时候，读取者通过cmpxchg()尝试遍历链表next中的HEADER标志，并把操作完成的读取页表放回当前位置。当然，写入者也可以设置的UPDATE标志让读取者停止往后遍历。当读取者的cmpxchg()操作失败时（没有执行赋值A=B），表示在读取操作期间写入者改变了链表的状态（覆盖了原先的头端），读取者重新执行放回操作过程。

写入者在改变一个新的尾端页表就能填满缓冲区的时候，它会先检查新页表的next指针是否有HEADER标志，如果是，更新为UPDATE。标记这个（next指向的）页表是活动的，写入者正在使用它，导致读取者的cmpxchg()操作失败，这样它就不能剥离为读端页表。同时也表示链表马上就要填满了，只剩一个页表（新的尾页表）可以用。

算法的基本功能相对好理解，但是考虑到一些复杂的情形还是有点费脑。一种可能就是连续的写入导致缓冲区很快填满，尾端页表也碰到了提交页表，这里做出的选择是放弃当前的写入操作。但是有可能碰到一种情形，提交指针正好指向读端页表（如下所示）。这时候再推着头端页表向前移动，跳过了读端页表，提交页表指针可能就再也没法从读端页表回到ring-buffer。所以写入者必须在检查到这种状态时放弃写入。

              reader page    commit page
                  |              |
                  v              |
                 +---+           |
                 |   |<----------+
                 |   |
                 |   |------+
                 +---+      |
                            |
                            v
        +---+    +---+    +---+    +---+
    <---|   |--->|   |-H->|   |--->|   |--->
    --->|   |<---|   |<---|   |<---|   |<---
        +---+    +---+    +---+    +---+
                   ^
                   |
               tail page

还有一些其他复杂的情形，感兴趣的读者可以移步Rostedt的设计文档获取更多信息。文档相当详细而且用了遍布篇幅的ASCII字符画展示了ring-buffer的操作。算法本身属于Rostedt为红帽申请的专利。遵守红帽的专利政策前提下，经授权后可以应用到自己的免费软件中。

下一代Linux跟踪工具集（LTTng）开发者之一的Mathieu Desnoyers，也一直关注ring-buffer相关的进展。LTTng作为一种跟踪实现，很多人也期待能用上通用ring-buffer。新提出的算法的复杂度堪比RCU的实现，他说，但是整体上又不像RCU（或者说LTTng 无锁缓冲算法），算法的形式证明也还没有给出。但他认为把无锁ring-buffer用在跟踪上是可取并且能实现的。但是Rostedt的算法未经正式验证可能导致查找bug更加费时。然而，这种复杂性并非全然无用，Desnoyers在评论中提到：”这样就没有人说LTTng的无锁缓冲算法与此相比是复杂的:)“

另外他提到的两点有关性能和用户空间追踪。Rostedt的算法依赖于关闭内核抢占，然而这对用户空间来说是不可能的。Desnoyers还说，LTTng有着更紧凑的事件表示，所以LTTng的版本能在每秒处理更多的事件。但是目前没人做过两者实际性能的对比。很有可能Desoyers会基于现在的LTTng的代码，在不久将来提出一种另一种的无锁ring-buffer，但是在那之前他先要解决博士论文上的琐碎事务。

Rostedt目标是在2.6.32内核中合入他的无锁ring-buffer算法，其他人是否有反对意见有待观察，或许还要同其他候选算法一较高下。但是，内核迟早要为跟踪事件合入一种无锁ring-buffer算法。