无锁环形缓冲区设计¶
版权所有 2009 Red Hat Inc.
- 作者:
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）
与生产者相同
- 消费者（consumer）
从缓冲区读取的任务（与读取器相同）
- 读取器（reader）
与消费者相同。
- 读取器页（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。
通用环形缓冲区¶
环形缓冲区可以用于覆盖模式或生产者/消费者模式。
生产者/消费者模式是指如果生产者在消费者释放任何内容之前填满缓冲区，生产者将停止写入缓冲区。这将丢失最近的事件。
覆盖模式是指如果生产者在消费者释放任何内容之前填满缓冲区，生产者将覆盖较旧的数据。这将丢失最旧的事件。
没有两个写入器可以同时写入（在同一个每个 CPU 的缓冲区上），但是一个写入器可能会中断另一个写入器，但它必须在之前的写入器可以继续之前完成写入。这对于算法非常重要。写入器的行为类似于“堆栈”。中断的工作方式强制执行此行为
writer1 start
<preempted> writer2 start
<preempted> writer3 start
writer3 finishes
writer2 finishes
writer1 finishes
这非常类似于一个写入器被中断抢占，并且中断也进行写入。
读取器可以随时发生。但是没有两个读取器可以同时运行，读取器也不能抢占/中断另一个读取器。读取器不能抢占/中断写入器，但是它可以在写入器正在写入的同时从缓冲区读取/消费，但是读取器必须在另一个处理器上才能这样做。读取器可以在其自己的处理器上读取，并且可以被写入器抢占。
写入器可以抢占读取器，但是读取器不能抢占写入器。但是读取器可以与写入器同时（在另一个处理器上）读取缓冲区。
环形缓冲区由一个链表连接的页面列表组成。
在初始化时，会为读取器分配一个不属于环形缓冲区的读取器页面。
head_page、tail_page 和 commit_page 都被初始化为指向同一页面。
读取器页面被初始化为其下一个指针指向头页，其上一个指针指向头页之前的页面。
读取器有自己的页面可以使用。在启动时，会分配此页面，但不会将其附加到列表中。当读取器想要从缓冲区读取时，如果其页面为空（就像在启动时一样），它会将其页面与 head_page 交换。旧的读取器页面将成为环形缓冲区的一部分，并且 head_page 将被删除。插入页面（旧的 reader_page）之后的页面将成为新的头页。
一旦将新页面提供给读取器，读取器就可以对它执行任何操作，只要写入器已离开该页面。
读取器页面如何交换的示例：请注意，这不显示缓冲区中的头页，它仅用于演示交换。
+------+
|reader| RING BUFFER
|page |
+------+
+---+ +---+ +---+
| |-->| |-->| |
| |<--| |<--| |
+---+ +---+ +---+
^ | ^ |
| +-------------+ |
+-----------------+
+------+
|reader| RING BUFFER
|page |-------------------+
+------+ v
| +---+ +---+ +---+
| | |-->| |-->| |
| | |<--| |<--| |<-+
| +---+ +---+ +---+ |
| ^ | ^ | |
| | +-------------+ | |
| +-----------------+ |
+------------------------------------+
+------+
|reader| RING BUFFER
|page |-------------------+
+------+ <---------------+ v
| ^ +---+ +---+ +---+
| | | |-->| |-->| |
| | | | | |<--| |<-+
| | +---+ +---+ +---+ |
| | | ^ | |
| | +-------------+ | |
| +-----------------------------+ |
+------------------------------------+
+------+
|buffer| RING BUFFER
|page |-------------------+
+------+ <---------------+ v
| ^ +---+ +---+ +---+
| | | | | |-->| |
| | New | | | |<--| |<-+
| | Reader +---+ +---+ +---+ |
| | page ----^ | |
| | | |
| +-----------------------------+ |
+------------------------------------+
如果环形缓冲区中的内容少于缓冲区页面中保存的内容，则交换的页面可能是提交页面和尾页。
reader page commit page tail page
| | |
v | |
+---+ | |
| |<----------+ |
| |<------------------------+
| |------+
+---+ |
|
v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
这种情况对于此算法仍然有效。当写入器离开页面时，它只是进入环形缓冲区，因为读取器页面仍然指向环形缓冲区中的下一个位置。
主要指针
- 读取器页面
仅由读取器使用的页面，不属于环形缓冲区（可以交换进来）
- 头页
环形缓冲区中下一个将与读取器页面交换的页面。
- 尾页
下一个写入将发生的页面。
- 提交页
最后一个完成写入的页面。
提交页面仅由写入器堆栈中最外层的写入器更新。抢占另一个写入器的写入器不会移动提交页面。
当数据写入环形缓冲区时，会在环形缓冲区中保留一个位置并传递回写入器。当写入器完成将数据写入该位置时，它会提交写入。
在此事务期间，可能会在任何时间发生另一次写入（或读取）。如果发生另一次写入，则必须在继续之前的写入之前完成。
写入保留
Buffer page +---------+ |written | +---------+ <--- given back to writer (current commit) |reserved | +---------+ <--- tail pointer | empty | +---------+写入提交
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)
提交指针指向上次提交的写入位置，而没有抢占另一个写入。当提交抢占另一个写入的写入时，它只会成为挂起的提交，并且在所有写入都已提交之前不会是完全提交。
提交页面指向具有最后一个完全提交的页面。尾页指向具有最后一个写入的页面（在提交之前）。
尾页始终等于或在提交页面之后。它可能会提前几个页面。如果尾页赶上提交页面，则不再允许进行写入（无论环形缓冲区的模式如何：覆盖和生产者/消费者）。
页面的顺序是
head page
commit page
tail page
可能的情况
tail page
head page commit page |
| | |
v v v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
有一种特殊情况，即头页在提交页之后，也可能在尾页之后。那是当提交（和尾部）页面已与读取器页面交换时。这是因为头页始终是环形缓冲区的一部分，但是读取器页面不是。每当环形缓冲区内提交的页面少于完整页面时，并且读取器交换出一个页面时，它将交换出提交页面。
reader page commit page tail page
| | |
v | |
+---+ | |
| |<----------+ |
| |<------------------------+
| |------+
+---+ |
|
v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
^
|
head page
在这种情况下，当尾部和提交移回环形缓冲区时，头页不会移动。
如果提交页面仍然在该页面上，则读取器无法将页面交换到环形缓冲区中。如果读取满足最后的提交（真正的提交而不是挂起或保留），则没有更多内容可读。在另一个完全提交完成之前，该缓冲区被视为空。
当尾部与头页相遇时，如果缓冲区处于覆盖模式，则头页将向前推一个。如果缓冲区处于生产者/消费者模式，则写入将失败。
覆盖模式
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
^
|
head page
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
^
|
head page
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
^
|
head page
请注意，读取器页面仍然指向之前的头页。但是，当发生交换时，它将使用最近的头页。
使环形缓冲区无锁：¶
无锁算法背后的主要思想是将 head_page 指针的移动与读取器的页面交换相结合。状态标志放置在指向页面的指针内。为此，每个页面在内存中必须按 4 个字节对齐。这将允许地址的 2 个最低有效位用作标志，因为对于地址，它们将始终为零。要获取地址，只需屏蔽掉标志
MASK = ~3
address & MASK
这两个位将保留两个标志
- HEADER
指向的页面是头页
- UPDATE
指向的页面正在由写入器更新，并且曾经是或即将成为头页。
reader page
|
v
+---+
| |------+
+---+ |
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-H->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
上面的指针“->”将设置 HEADER 标志。也就是说，下一个页面是读取器要交换出的下一个页面。此指针表示下一个页面是头页。
当尾页与头指针相遇时，它将使用 cmpxchg 将指针更改为 UPDATE 状态
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-H->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
“->”表示处于 UPDATE 状态的指针。
对读取器的任何访问都需要采取某种形式的锁来序列化读取器。但是，写入器永远不会使用锁来写入环形缓冲区。这意味着我们只需要担心单个读取器，并且写入仅以“堆栈”形式抢占。
当读取器尝试与环形缓冲区交换页面时，它也将使用 cmpxchg。如果指向头页的指针中的标志位未设置 HEADER 标志，则比较将失败，并且读取器将需要查找新的头页并重试。请注意，标志 UPDATE 和 HEADER 永远不会同时设置。
读取器按如下方式交换读取器页面
+------+
|reader| RING BUFFER
|page |
+------+
+---+ +---+ +---+
| |--->| |--->| |
| |<---| |<---| |
+---+ +---+ +---+
^ | ^ |
| +---------------+ |
+-----H-------------+
读取器将读取器页面的下一个指针设置为 HEADER，指向头页之后的页面
+------+
|reader| RING BUFFER
|page |-------H-----------+
+------+ v
| +---+ +---+ +---+
| | |--->| |--->| |
| | |<---| |<---| |<-+
| +---+ +---+ +---+ |
| ^ | ^ | |
| | +---------------+ | |
| +-----H-------------+ |
+--------------------------------------+
它对指向前一个头页的指针执行 cmpxchg，使其指向读取器页面。请注意，新指针没有设置 HEADER 标志。此操作会原子地将头页向前移动
+------+
|reader| RING BUFFER
|page |-------H-----------+
+------+ v
| ^ +---+ +---+ +---+
| | | |-->| |-->| |
| | | |<--| |<--| |<-+
| | +---+ +---+ +---+ |
| | | ^ | |
| | +-------------+ | |
| +-----------------------------+ |
+------------------------------------+
设置新头页后，头页的前一个指针将更新为读取器页面
+------+
|reader| RING BUFFER
|page |-------H-----------+
+------+ <---------------+ v
| ^ +---+ +---+ +---+
| | | |-->| |-->| |
| | | | | |<--| |<-+
| | +---+ +---+ +---+ |
| | | ^ | |
| | +-------------+ | |
| +-----------------------------+ |
+------------------------------------+
+------+
|buffer| RING BUFFER
|page |-------H-----------+ <--- New head page
+------+ <---------------+ v
| ^ +---+ +---+ +---+
| | | | | |-->| |
| | New | | | |<--| |<-+
| | Reader +---+ +---+ +---+ |
| | page ----^ | |
| | | |
| +-----------------------------+ |
+------------------------------------+
另一个重点：读取器页面通过其前一个指针（现在指向新的头页面）指回的页面永远不会指回读取器页面。这是因为读取器页面不属于环形缓冲区。通过下一个指针遍历环形缓冲区将始终留在环形缓冲区内。通过前一个指针遍历环形缓冲区可能不会。
注意，确定读取器页面的方法很简单，就是检查页面的前一个指针。如果前一个页面的下一个指针没有指回原始页面，则原始页面是读取器页面。
+--------+
| reader | next +----+
| page |-------->| |<====== (buffer page)
+--------+ +----+
| | ^
| v | next
prev | +----+
+------------->| |
+----+
头页面向前移动的方式
当尾页面与头页面相遇，并且缓冲区处于覆盖模式，并且发生更多写入时，必须先将头页面向前移动，然后写入器才能移动尾页面。实现此目的的方法是，写入器执行 cmpxchg 操作，将指向头页面的指针从 HEADER 标志转换为设置 UPDATE 标志。完成此操作后，读取器将无法从缓冲区交换头页面，也无法移动头页面，直到写入器完成移动。
这消除了读取器可能对写入器产生的任何竞争。读取器必须自旋等待，这就是读取器不能抢占写入器的原因。
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-H->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
以下页面将成为新的头页面
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |-H->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
设置新的头页面后，我们可以将旧的头页面指针设置回 NORMAL
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |-H->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
移动头页面后，尾页面现在可以向前移动
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |-H->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
以上是简单的更新。现在来看更复杂的场景。
如前所述，如果足够的写入抢占了第一次写入，则尾页面可能会一直绕着缓冲区移动，并与提交页面相遇。此时，我们必须开始丢弃写入（通常会向用户发出某种警告）。但是，如果提交仍然在读取器页面上会发生什么？提交页面不属于环形缓冲区。尾页面必须考虑到这一点。
reader page commit page
| |
v |
+---+ |
| |<----------+
| |
| |------+
+---+ |
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-H->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
^
|
tail page
如果尾页面只是将头页面向前推，则离开读取器页面时的提交将不会指向正确的页面。
解决此问题的方法是在推送头页面之前测试提交页面是否在读取器页面上。如果是，则可以假定尾页面环绕了缓冲区，我们必须丢弃新的写入。
这不是竞争条件，因为提交页面只能由最外层的写入器（被抢占的写入器）移动。这意味着当写入器移动尾页面时，提交不会移动。如果读取器页面也被用作提交页面，则读取器无法交换读取器页面。读取器可以简单地检查提交是否不在读取器页面上。一旦提交页面离开读取器页面，除非读取器与也是提交页面的缓冲页面再次进行交换，否则它将永远不会回到该页面上。
嵌套写入¶
在向前推送尾页面时，如果头页面是下一个页面，我们必须首先向前推送头页面。如果头页面不是下一个页面，则仅使用 cmpxchg 更新尾页面。
只有写入器才能移动尾页面。这必须以原子方式完成，以防止嵌套写入器。
temp_page = tail_page
next_page = temp_page->next
cmpxchg(tail_page, temp_page, next_page)
如果尾页面仍指向预期的页面，则上述操作将更新尾页面。如果此操作失败，则嵌套写入将其向前推送，则当前写入不需要推送它。
temp page
|
v
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
嵌套写入进入并向前移动尾页面
tail page (moved by nested writer)
temp page |
| |
v v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
上述操作将使 cmpxchg 失败，但是由于尾页面已经向前移动，因此写入器将只是尝试在新尾页面上再次保留存储空间。
但是移动头页面有点复杂
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-H->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
写入操作将头页面指针转换为 UPDATE
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
但是，如果嵌套的写入器在此处抢占，它将看到下一个页面是头页面，但它也是嵌套的。它会检测到它是嵌套的，并将保存该信息。检测的方法是它看到 UPDATE 标志而不是 HEADER 或 NORMAL 指针。
嵌套的写入器将设置新的头页面指针
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |-H->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
但是它不会将更新重置回 normal。只有将指针从 HEAD 转换为 UPDATE 的写入器才会将其转换回 NORMAL
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |-H->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
嵌套的写入器完成后，最外层的写入器会将 UPDATE 指针转换为 NORMAL
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |-H->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
如果有多个嵌套的写入进入并将尾页面向前移动多个页面，情况会更加复杂
(first writer)
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-H->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
写入操作将头页面指针转换为 UPDATE
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
下一个写入器进入，看到更新并设置新的头页面
(second writer)
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |-H->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
嵌套的写入器将尾页面向前移动。但不会将旧的更新页面设置为 NORMAL，因为它不是最外层的写入器
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |-H->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
另一个写入器抢占并看到尾页面之后的页面是头页面。它将其从 HEAD 更改为 UPDATE
(third writer)
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |-U->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
写入器将向前移动头页面
(third writer)
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |-U->| |-H->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
但是，由于第三个写入器确实将 HEAD 标志更改为 UPDATE，因此它会将其转换为 normal
(third writer)
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |--->| |-H->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
然后它将移动尾页面，并返回到第二个写入器
(second writer)
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |--->| |-H->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
第二个写入器将无法移动尾页面，因为它已经被移动，因此它将再次尝试，并将其数据添加到新的尾页面。它将返回到第一个写入器
(first writer)
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |--->| |-H->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
第一个写入器无法以原子方式知道在它更新 HEAD 页面时尾页面是否已移动。然后，它会将头页面更新为它认为的新头页面
(first writer)
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |-H->| |-H->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
由于 cmpxchg 返回指针的旧值，因此第一个写入器将看到它成功地将指针从 NORMAL 更新为 HEAD。但是，正如我们所看到的，这还不够好。它还必须检查尾页面是否在它过去的位置或在下一个页面上
(first writer)
A B tail page
| | |
v v v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |-H->| |-H->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
如果尾页面 != A 且尾页面 != B，则必须将指针重置回 NORMAL。它只需要担心嵌套的写入器这一事实意味着它只需要在设置 HEAD 页面后检查这一点
(first writer)
A B tail page
| | |
v v v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |--->| |-H->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
现在，写入器可以更新头页面。这也是为什么头页面必须保持 UPDATE 状态，并且只能由最外层的写入器重置的原因。这可以防止读取器看到错误的头页面
(first writer)
A B tail page
| | |
v v v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |--->| |-H->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+