无锁环形缓冲区设计¶

作者:: Steven Rostedt <srostedt@redhat.com>
许可证:: GNU 自由文档许可证，版本 1.2 (根据 GPL v2 双重授权)
审阅者:: Mathieu Desnoyers, Huang Ying, Hidetoshi Seto 和 Frederic Weisbecker。

编写版本：2.6.31

本文档中使用的术语¶

tail

环形缓冲区中发生新写入的地方。

head

环形缓冲区中发生新读取的地方。

生产者 (producer)

向环形缓冲区写入的任务（与 writer 相同）

写入者 (writer)

同生产者

consumer

从缓冲区读取的任务（与 reader 相同）

读取者 (reader)

同 consumer。

reader_page

环形缓冲区外部的一个页面，主要（在很大程度上）仅由读取者使用。

head_page

指向读取者下一个要使用的页面的指针

tail_page

指向下一个将被写入的页面的指针

commit_page

指向包含最后完成的非嵌套写入的页面的指针。

cmpxchg

执行以下操作的硬件辅助原子事务

A = B if previous A == C

R = cmpxchg(A, C, B) is saying that we replace A with B if and only
    if current A is equal to C, and we put the old (current)
    A into R

R gets the previous A regardless if A is updated with B or not.

要查看更新是否成功，可以使用 R == C 比较。

通用环形缓冲区¶

环形缓冲区既可以用于覆盖模式，也可以用于生产者/消费者模式。

在生产者/消费者模式下，如果生产者在消费者释放任何空间之前填满了缓冲区，生产者将停止向缓冲区写入。这将会丢失最近的事件。

在覆盖模式下，如果生产者在消费者释放任何空间之前填满了缓冲区，生产者将覆盖较旧的数据。这将会丢失最早的事件。

没有两个写入者可以同时写入（在同一个 per-cpu 缓冲区上），但是一个写入者可能会中断另一个写入者，不过它必须在先前的写入者继续之前完成写入。这对该算法非常重要。写入者表现得像一个“栈”。中断的工作方式强制实现了这种行为

writer1 start
   <preempted> writer2 start
       <preempted> writer3 start
                   writer3 finishes
               writer2 finishes
writer1 finishes

这非常类似于一个写入者被中断抢占，并且该中断也执行了写入。

读取操作随时可能发生。但没有两个读取者可以同时运行，读取者也不能抢占/中断另一个读取者。读取者不能抢占/中断写入者，但它可以在写入者写入的同时从缓冲区读取/消费，不过读取者必须在另一个处理器上才能这样做。读取者可以在其自己的处理器上读取，并且可以被写入者抢占。

写入者可以抢占读取者，但读取者不能抢占写入者。但是读取者可以与写入者同时（在另一个处理器上）读取缓冲区。

环形缓冲区由通过链表连接在一起的一组页面组成。

在初始化时，会为读取者分配一个不属于环形缓冲区的读取者页面。

head_page、tail_page 和 commit_page 都初始化为指向同一个页面。

读取者页面初始化为其 next 指针指向 head page，其 previous 指针指向 head page 之前的页面。

读取者有自己的页面可供使用。在启动时，该页面已分配但未附加到链表中。当读取者想要从缓冲区读取时，如果其页面为空（就像启动时一样），它将把自己的页面与 head_page 进行交换。旧的读取者页面将成为环形缓冲区的一部分，而 head_page 将被移除。插入页面（旧的 reader_page）之后的页面将成为新的 head page。

一旦新页面交给了读取者，读取者就可以对它进行任何操作，只要写入者已经离开该页面。

读取者页面如何交换的示例：请注意，这没有显示缓冲区中的 head page，它仅用于演示交换。

+------+
|reader|          RING BUFFER
|page  |
+------+
                +---+   +---+   +---+
                |   |-->|   |-->|   |
                |   |<--|   |<--|   |
                +---+   +---+   +---+
                 ^ |             ^ |
                 | +-------------+ |
                 +-----------------+


+------+
|reader|          RING BUFFER
|page  |-------------------+
+------+                   v
  |             +---+   +---+   +---+
  |             |   |-->|   |-->|   |
  |             |   |<--|   |<--|   |<-+
  |             +---+   +---+   +---+  |
  |              ^ |             ^ |   |
  |              | +-------------+ |   |
  |              +-----------------+   |
  +------------------------------------+

+------+
|reader|          RING BUFFER
|page  |-------------------+
+------+ <---------------+ v
  |  ^          +---+   +---+   +---+
  |  |          |   |-->|   |-->|   |
  |  |          |   |   |   |<--|   |<-+
  |  |          +---+   +---+   +---+  |
  |  |             |             ^ |   |
  |  |             +-------------+ |   |
  |  +-----------------------------+   |
  +------------------------------------+

+------+
|buffer|          RING BUFFER
|page  |-------------------+
+------+ <---------------+ v
  |  ^          +---+   +---+   +---+
  |  |          |   |   |   |-->|   |
  |  |  New     |   |   |   |<--|   |<-+
  |  | Reader   +---+   +---+   +---+  |
  |  |  page ----^                 |   |
  |  |                             |   |
  |  +-----------------------------+   |
  +------------------------------------+

如果环形缓冲区中的内容少于缓冲区页面所容纳的内容，则被交换的页面有可能是 commit page 和 tail page。

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

对于该算法，这种情况仍然有效。当写入者离开该页面时，它只是进入环形缓冲区，因为读取者页面仍然指向环形缓冲区中的下一个位置。

主要指针

reader page

仅由读取者使用且不属于环形缓冲区的页面（可能会被交换进来）

head page

环形缓冲区中下一个将与读取者页面进行交换的页面。

tail page

下一次写入将要发生的页面。

commit page

最后完成写入的页面。

commit page 仅由写入者栈中最外层的写入者更新。抢占另一个写入者的写入者不会移动 commit page。

当数据被写入环形缓冲区时，会在环形缓冲区中保留一个位置并将其传回给写入者。当写入者完成将数据写入该位置时，它会提交写入。

在此事务期间的任何时间都可能发生另一次写入（或读取）。如果发生了另一次写入，它必须在继续先前的写入之前完成。

写入保留 (Write reserve)

 Buffer page
+---------+
|written  |
+---------+  <--- given back to writer (current commit)
|reserved |
+---------+ <--- tail pointer
| empty   |
+---------+

写入提交 (Write commit)

 Buffer page
+---------+
|written  |
+---------+
|written  |
+---------+  <--- next position for write (current commit)
| empty   |
+---------+

如果在第一次保留之后发生写入

     Buffer page
    +---------+
    |written  |
    +---------+  <-- current commit
    |reserved |
    +---------+  <--- given back to second writer
    |reserved |
    +---------+ <--- tail pointer

After second writer commits::


     Buffer page
    +---------+
    |written  |
    +---------+  <--(last full commit)
    |reserved |
    +---------+
    |pending  |
    |commit   |
    +---------+ <--- tail pointer

When the first writer commits::

     Buffer page
    +---------+
    |written  |
    +---------+
    |written  |
    +---------+
    |written  |
    +---------+  <--(last full commit and tail pointer)

commit 指针指向在没有抢占另一个写入的情况下提交的最后一个写入位置。当一个抢占了另一个写入的写入被提交时，它仅成为一个挂起提交，并且在所有写入都提交之前不会成为完全提交。

commit page 指向具有最后一次完全提交的页面。tail page 指向带有最后一次写入（在提交之前）的页面。

tail page 总是等于或位于 commit page 之后。它可能超前好几个页面。如果 tail page 追上了 commit page，则不能再进行写入（无论环形缓冲区的模式如何：覆盖或生产/消费者）。

页面的顺序是

head page
commit page
tail page

可能的情景

                             tail page
  head page         commit page  |
      |                 |        |
      v                 v        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

有一种特殊情况，即 head page 位于 commit page 甚至 tail page 之后。这是当 commit（和 tail）page 已与读取者页面交换时。这是因为 head page 始终是环形缓冲区的一部分，但读取者页面不是。每当环形缓冲区内提交的内容不足一页，并且读取者交换出一个页面时，它交换出去的就是 commit page。

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

在这种情况下，当 tail 和 commit 移回环形缓冲区时，head page 不会移动。

如果 commit page 仍在某个页面上，则读取者不能将页面交换到环形缓冲区中。如果读取操作遇到了最后一次提交（真正的提交，而不是挂起或保留的提交），则没有更多内容可读了。在另一个完全提交完成之前，缓冲区被认为是空的。

当 tail 遇到 head page 时，如果缓冲区处于覆盖模式，head page 将向前推进一个。如果缓冲区处于生产者/消费者模式，则写入将失败。

覆盖模式 (Overwrite mode)

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+
                        ^
                        |
                    head page


            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+
                                 ^
                                 |
                             head page


                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+
                                 ^
                                 |
                             head page

注意，读取者页面将仍然指向先前的 head page。但当发生交换时，它将使用最新的 head page。

使环形缓冲区无锁化¶

无锁算法背后的主要思想是将 head_page 指针的移动与同读取者的页面交换结合起来。状态标志被放置在指向页面的指针内部。为此，每个页面在内存中必须按 4 字节对齐。这将允许地址的 2 个最低有效位用作标志，因为对于地址而言它们始终为零。要获取地址，只需将标志屏蔽掉即可

MASK = ~3

address & MASK

这两个位将保留两个标志

HEADER

被指向的页面是一个 head page

UPDATE

被指向的页面正在被写入者更新，并且曾经是或即将成为一个 head page。

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

上面的指针 “-H->” 将设置 HEADER 标志。也就是说，下一个页面是将被读取者交换出去的下一个页面。该指针意味着下一个页面是 head page。

当 tail page 遇到 head 指针时，它将使用 cmpxchg 将指针更改为 UPDATE 状态

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

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

“-U->” 表示处于 UPDATE 状态的指针。

对读取者的任何访问都需要获取某种锁来串行化读取者。但写入者绝不会为了写入环形缓冲区而获取锁。这意味着我们只需要担心单个读取者，并且写入仅以“栈”的形式进行抢占。

当读取者尝试与环形缓冲区交换页面时，它也会使用 cmpxchg。如果指向 head page 的指针中的标志位未设置 HEADER 标志，则比较将失败，读取者将需要寻找新的 head page 并重试。注意，标志 UPDATE 和 HEADER 绝不会同时设置。

读取者按如下方式交换 reader page

+------+
|reader|          RING BUFFER
|page  |
+------+
                +---+    +---+    +---+
                |   |--->|   |--->|   |
                |   |<---|   |<---|   |
                +---+    +---+    +---+
                 ^ |               ^ |
                 | +---------------+ |
                 +-----H-------------+

读取者将 reader page 的 next 指针设置为指向 head page 之后的页面的 HEADER

+------+
|reader|          RING BUFFER
|page  |-------H-----------+
+------+                   v
  |             +---+    +---+    +---+
  |             |   |--->|   |--->|   |
  |             |   |<---|   |<---|   |<-+
  |             +---+    +---+    +---+  |
  |              ^ |               ^ |   |
  |              | +---------------+ |   |
  |              +-----H-------------+   |
  +--------------------------------------+

它对指向先前 head page 的指针执行 cmpxchg，使其指向 reader page。请注意，新指针未设置 HEADER 标志。此操作会原子性地将 head page 向前移动

+------+
|reader|          RING BUFFER
|page  |-------H-----------+
+------+                   v
  |  ^          +---+   +---+   +---+
  |  |          |   |-->|   |-->|   |
  |  |          |   |<--|   |<--|   |<-+
  |  |          +---+   +---+   +---+  |
  |  |             |             ^ |   |
  |  |             +-------------+ |   |
  |  +-----------------------------+   |
  +------------------------------------+

设置好新的 head page 后，head page 的 previous 指针将更新为 reader page

+------+
|reader|          RING BUFFER
|page  |-------H-----------+
+------+ <---------------+ v
  |  ^          +---+   +---+   +---+
  |  |          |   |-->|   |-->|   |
  |  |          |   |   |   |<--|   |<-+
  |  |          +---+   +---+   +---+  |
  |  |             |             ^ |   |
  |  |             +-------------+ |   |
  |  +-----------------------------+   |
  +------------------------------------+

+------+
|buffer|          RING BUFFER
|page  |-------H-----------+  <--- New head page
+------+ <---------------+ v
  |  ^          +---+   +---+   +---+
  |  |          |   |   |   |-->|   |
  |  |  New     |   |   |   |<--|   |<-+
  |  | Reader   +---+   +---+   +---+  |
  |  |  page ----^                 |   |
  |  |                             |   |
  |  +-----------------------------+   |
  +------------------------------------+

另一个重要点：reader page 通过其 previous 指针反向指向的页面（即现在指向新 head page 的那个页面）永远不会反向指向 reader page。这是因为 reader page 不属于环形缓冲区。通过 next 指针遍历环形缓冲区将始终停留在环形缓冲区内。通过 prev 指针遍历环形缓冲区则不一定。

注意，确定 reader page 的方法很简单，只需检查页面的 previous 指针即可。如果前一个页面的 next 指针没有反向指向原页面，则原页面就是 reader page

 +--------+
 | reader |  next   +----+
 |  page  |-------->|    |<====== (buffer page)
 +--------+         +----+
     |                | ^
     |                v | next
prev |              +----+
     +------------->|    |
                    +----+

head page 向前移动的方式

当 tail page 遇到 head page 且缓冲区处于覆盖模式并发生更多写入时，必须先将 head page 向前移动，然后写入者才能移动 tail page。完成此操作的方式是，写入者执行 cmpxchg，将指向 head page 的指针从 HEADER 标志转换为设置 UPDATE 标志。一旦完成此操作，在写入者完成移动之前，读取者将无法从缓冲区交换 head page，也无法移动 head page。

这消除了读取者可能对写入者产生的任何竞态条件。读取者必须自旋，这就是为什么读取者不能抢占写入者的原因

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

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

以下页面将被做成新的 head page

           tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

设置好新的 head page 后，我们可以将旧的 head page 指针改回 NORMAL

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

head page 移动后，tail page 现在可以向前移动了

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

以上是简单的更新。现在来看更复杂的场景。

如前所述，如果有足够的写入抢占了第一次写入，tail page 可能会绕缓冲区一整圈并遇到 commit page。此时，我们必须开始丢弃写入（通常会向用户发出某种警告）。但是，如果 commit 仍在 reader page 上会发生什么？commit page 不属于环形缓冲区。tail page 必须考虑这一点

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

如果 tail page 只是简单地将 head page 向前推，那么当离开 reader page 时，commit 将不会指向正确的页面。

针对此问题的解决方案是，在推送 head page 之前测试 commit page 是否在 reader page 上。如果是，则可以假设 tail page 绕过了缓冲区，我们必须丢弃新的写入。

这不是竞态条件，因为 commit page 只能由最外层的写入者（被抢占的写入者）移动。这意味着当写入者移动 tail page 时，commit 不会移动。如果 reader page 同时被用作 commit page，读取者就无法将其交换出去。读取者可以简单地检查 commit 是否不在 reader page 上。一旦 commit page 离开 reader page，它就永远不会再回到上面，除非读取者与同时也是 commit page 的缓冲区页面进行另一次交换。

嵌套写入¶

在向前推送 tail page 时，如果 head page 是下一个页面，我们必须首先向前推送 head page。如果 head page 不是下一个页面，则只需通过 cmpxchg 更新 tail page。

只有写入者会移动 tail page。这必须以原子方式完成，以防范嵌套写入者

temp_page = tail_page
next_page = temp_page->next
cmpxchg(tail_page, temp_page, next_page)

如果 tail page 仍然指向预期的页面，上述操作将更新 tail page。如果失败，说明有嵌套写入将其向前推送了，当前写入不需要再推送它

           temp page
               |
               v
            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

嵌套写入介入并将 tail page 向前移动

                    tail page (moved by nested writer)
            temp page   |
               |        |
               v        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

上述操作会导致 cmpxchg 失败，但由于 tail page 已经被向前移动，写入者只需重试以在新的 tail page 上保留存储空间即可。

但 head page 的移动要稍微复杂一些

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

写入操作将 head page 指针转换为 UPDATE

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

但是，如果嵌套写入在此处抢占，它将看到下一个页面是 head page，但它也是嵌套的。它会检测到它是嵌套的并保存该信息。检测的依据是它看到了 UPDATE 标志而不是 HEADER 或 NORMAL 指针。

嵌套写入将设置新的 head page 指针

           tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

但它不会将 update 重置回 normal。只有将指针从 HEAD 转换为 UPDATE 的写入者才会将其转换回 NORMAL

                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

嵌套写入完成后，最外层的写入者会将 UPDATE 指针转换为 NORMAL

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

如果有多个嵌套写入介入并将 tail page 向前移动了好几个页面，情况可能会更复杂

(first writer)

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

写入操作将 head page 指针转换为 UPDATE

            tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

下一个写入者介入，看到该更新并设置新的 head page

(second writer)

           tail page
               |
               v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

嵌套写入将 tail page 向前移动。但由于它不是最外层的写入者，因此不会将旧的 update 页面设置为 NORMAL

                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

另一个写入者抢占并看到 tail page 之后的页面是一个 head page。它将其从 HEAD 更改为 UPDATE

(third writer)

                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-U->|   |--->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

该写入者将把 head page 向前移动

(third writer)

                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-U->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

但现在第三个写入者确实将 HEAD 标志更改为了 UPDATE，它将把它转换为 normal

(third writer)

                    tail page
                        |
                        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

然后它将移动 tail page，并返回给第二个写入者

(second writer)

                             tail page
                                 |
                                 v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

第二个写入者将无法移动 tail page，因为它已经被移动了，所以它将重试并将其数据添加到新的 tail page 中。它将返回给第一个写入者

(first writer)

                             tail page
                                 |
                                 v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

第一个写入者无法在更新 HEAD 页面的同时原子性地知道 tail page 是否已移动。然后它将把 head page 更新为它认为的新 head page

(first writer)

                             tail page
                                 |
                                 v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

由于 cmpxchg 返回指针的旧值，第一个写入者将看到它成功将指针从 NORMAL 更新为 HEAD。但正如我们所见，这还不够。它必须同时检查 tail page 是在它过去的位置上还是在下一个页面上

(first writer)

               A        B    tail page
               |        |        |
               v        v        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |-H->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

如果 tail page != A 且 tail page != B，则它必须将指针重置回 NORMAL。它只需要担心嵌套写入这一事实意味着它只需要在设置 HEAD 页面之后检查这一点

(first writer)

               A        B    tail page
               |        |        |
               v        v        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |-U->|   |--->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

现在写入者可以更新 head page 了。这也是为什么 head page 必须保持在 UPDATE 状态且只能由最外层的写入者重置的原因。这可以防止读取者看到不正确的 head page

(first writer)

               A        B    tail page
               |        |        |
               v        v        v
    +---+    +---+    +---+    +---+
<---|   |--->|   |--->|   |--->|   |-H->
--->|   |<---|   |<---|   |<---|   |<---
    +---+    +---+    +---+    +---+

Linux 内核

目录

本页

无锁环形缓冲区设计¶

本文档中使用的术语¶

通用环形缓冲区¶

使环形缓冲区无锁化¶

嵌套写入¶