无锁环形缓冲区设计¶
版权所有 2009 Red Hat Inc.
- 作者:
Steven Rostedt <srostedt@redhat.com>
- 许可:
GNU 自由文档许可证，版本 1.2 (在 GPL v2 下双重许可)
- 审核人:
Mathieu Desnoyers, Huang Ying, Hidetoshi Seto, and 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的比较。
通用环形缓冲区¶
环形缓冲区可以在覆盖模式或生产者/消费者模式下使用。
生产者/消费者模式是指，如果生产者在消费者释放任何内容之前填满了缓冲区，则生产者将停止写入缓冲区。这将丢失最近的事件。
覆盖模式是指，如果生产者在消费者释放任何内容之前填满了缓冲区，则生产者将覆盖较旧的数据。这将丢失最旧的事件。
没有两个写入者可以同时写入 (在同一个 per-cpu 缓冲区上)，但是一个写入者可以中断另一个写入者，但是它必须在先前的写入者可以继续之前完成写入。这对算法非常重要。写入者的行为就像一个“堆栈”。中断的工作方式强制执行这种行为
writer1 start
<preempted> writer2 start
<preempted> writer3 start
writer3 finishes
writer2 finishes
writer1 finishes
这非常类似于一个写入者被中断抢占，并且中断也执行写入。
读取者可以在任何时候发生。但是没有两个读取者可以同时运行，也不能一个读取者抢占/中断另一个读取者。读取者不能抢占/中断写入者，但是它可以与写入者同时读取/使用缓冲区，但是读取者必须在另一个处理器上才能这样做。读取者可以在自己的处理器上读取，并且可以被写入者抢占。
写入者可以抢占读取者，但是读取者不能抢占写入者。但是读取者可以与写入者同时 (在另一个处理器上) 读取缓冲区。
环形缓冲区由一个链表链接在一起的页面列表组成。
在初始化时，为不属于环形缓冲区的读取者分配一个读取者页面。
head_page，tail_page 和 commit_page 都被初始化为指向同一个页面。
读取者页面被初始化为使其 next 指针指向 head 页面，并且其 previous 指针指向 head 页面之前的页面。
读取者有自己的页面可以使用。在启动时，会分配此页面，但不附加到列表。当读取者想要从缓冲区读取时，如果它的页面为空 (就像在启动时一样)，它将把它的页面与 head_page 交换。旧的读取者页面将成为环形缓冲区的一部分，并且 head_page 将被删除。插入的页面 (旧的 reader_page) 之后的页面将成为新的 head 页面。
一旦将新页面提供给读取者，只要写入者离开了该页面，读取者就可以对它做任何想做的事情。
读取者页面如何交换的示例：注意，这不显示缓冲区中的 head 页面，它仅用于演示交换。
+------+
|reader| RING BUFFER
|page |
+------+
+---+ +---+ +---+
| |-->| |-->| |
| |<--| |<--| |
+---+ +---+ +---+
^ | ^ |
| +-------------+ |
+-----------------+
+------+
|reader| RING BUFFER
|page |-------------------+
+------+ v
| +---+ +---+ +---+
| | |-->| |-->| |
| | |<--| |<--| |<-+
| +---+ +---+ +---+ |
| ^ | ^ | |
| | +-------------+ | |
| +-----------------+ |
+------------------------------------+
+------+
|reader| RING BUFFER
|page |-------------------+
+------+ <---------------+ v
| ^ +---+ +---+ +---+
| | | |-->| |-->| |
| | | | | |<--| |<-+
| | +---+ +---+ +---+ |
| | | ^ | |
| | +-------------+ | |
| +-----------------------------+ |
+------------------------------------+
+------+
|buffer| RING BUFFER
|page |-------------------+
+------+ <---------------+ v
| ^ +---+ +---+ +---+
| | | | | |-->| |
| | New | | | |<--| |<-+
| | Reader +---+ +---+ +---+ |
| | page ----^ | |
| | | |
| +-----------------------------+ |
+------------------------------------+
如果环形缓冲区中的内容小于缓冲区页面中保存的内容，则交换的页面可能是 commit 页面和 tail 页面。
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)
commit 指针指向上次在没有抢占另一个写入的情况下提交的写入位置。当提交抢占另一个写入的写入时，它仅成为挂起的提交，并且在所有写入都已提交之前不会成为完全提交。
commit 页面指向具有上次完全提交的页面。tail 页面指向具有上次写入的页面 (在提交之前)。
tail 页面始终等于或晚于 commit 页面。它可能会提前几个页面。如果 tail 页面赶上 commit 页面，则无论环形缓冲区的模式如何 (覆盖和生产者/消费者)，都不能再进行写入。
页面的顺序是
head page
commit page
tail page
可能的场景
tail page
head page commit page |
| | |
v v v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
有一种特殊情况，即头部页面在 commit 页面之后，并且可能在尾部页面之后。这是当 commit (和 tail) 页面已与读取者页面交换时。这是因为头部页面始终是环形缓冲区的一部分，但读取者页面不是。只要在环形缓冲区内提交的页面少于一个完整页面，并且读取者交换出一个页面，它将交换出 commit 页面。
reader page commit page tail page
| | |
v | |
+---+ | |
| |<----------+ |
| |<------------------------+
| |------+
+---+ |
|
v
+---+ +---+ +---+ +---+
<---| |--->| |--->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
^
|
head page
在这种情况下，当 tail 和 commit 移回环形缓冲区时，头部页面不会移动。
如果 commit 页面仍在页面上，则读取者无法将页面交换到环形缓冲区中。如果读取与上次提交 (真实提交，而不是挂起或保留) 相遇，则没有更多要读取的内容。缓冲区被认为是空的，直到另一个完全提交完成。
当 tail 与头部页面相遇时，如果缓冲区处于覆盖模式，则头部页面将向前推一个。如果缓冲区处于生产者/消费者模式，则写入将失败。
覆盖模式
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->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
上面的指针“-H->”将设置 HEADER 标志。也就是说，下一个页面是要被读取者交换出的下一个页面。此指针表示下一个页面是头部页面。
当尾部页面与头部指针相遇时，它将使用 cmpxchg 将指针更改为 UPDATE 状态
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-H->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
tail page
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-U->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
“-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 ----^ | |
| | | |
| +-----------------------------+ |
+------------------------------------+
另一个重点：读取者页面通过其先前指针指向的页面 (现在指向新的头部页面的页面) 永远不会指向读取者页面。那是因为读取者页面不属于环形缓冲区。通过 next 指针遍历环形缓冲区将始终停留在环形缓冲区中。通过 prev 指针遍历环形缓冲区可能不会。
请注意，确定读取者页面的方法很简单，只需检查页面的先前指针即可。如果先前页面的 next 指针没有指向原始页面，则原始页面是一个读取者页面
+--------+
| 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->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
以上是简单的更新。现在来看更复杂的场景。
如前所述，如果足够的写入抢占了第一个写入，则尾部页面可能会一直绕缓冲区转，并与 commit 页面相遇。此时，我们必须开始丢弃写入 (通常会向用户发出某种警告)。但是，如果 commit 仍然在读取者页面上会发生什么？commit 页面不属于环形缓冲区。尾部页面必须考虑到这一点
reader page commit page
| |
v |
+---+ |
| |<----------+
| |
| |------+
+---+ |
|
v
+---+ +---+ +---+ +---+
<---| |--->| |-H->| |--->| |--->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
^
|
tail page
如果尾部页面只是简单地将头部页面向前推，则离开读取者页面时的 commit 将不会指向正确的页面。
对此的解决方案是在推动头部页面之前测试 commit 页面是否在读取者页面上。如果是，则可以假定尾部页面已包装缓冲区，并且我们必须丢弃新的写入。
这不是竞争条件，因为 commit 页面只能由最外层的写入者 (被抢占的写入者) 移动。这意味着当写入者移动尾部页面时，commit 不会移动。如果读取者页面也用作 commit 页面，则读取者无法交换读取者页面。读取者可以简单地检查 commit 是否已离开读取者页面。一旦 commit 页面离开读取者页面，除非读取者与也作为 commit 页面的缓冲区页面再次进行交换，否则它将永远不会回到它上面。
嵌套写入¶
在向前推动尾部页面时，如果头部页面是下一个页面，我们必须首先向前推动头部页面。如果头部页面不是下一个页面，则只需使用 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->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+
如果 tail 页面 != A 并且 tail 页面 != 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->
--->| |<---| |<---| |<---| |<---
+---+ +---+ +---+ +---+