hazard pointer · epoch · RCU

Treiber 栈与内存回收

Treiber 栈是无锁结构里最短的一个。共享状态只有一个 Top 指针，push 与 pop 各只有一次 CAS，Michael-Scott 队列那套「两个指针、帮助推进」的机器在此一概不需要。

正因为算法本身短到没有可讨论的余地，剩下的那个问题就无处躲藏：pop 读到节点地址之后、用它之前，这块内存还属于自己吗。

1 · 一个指针与一次 CAS

push(v)：n = alloc(v)；t = load(Top)；n.next = t；CAS(Top, t, n) 失败则重来<br> pop()：t = load(Top)；若为 NIL 返回空；nx = load(t.next)；CAS(Top, t, nx) 失败则重来

push 的前三步全在私有数据上：新节点尚未发布，谁也看不见，写它的 next 不需要任何同步。真正的发布是那一次 CAS，它同时完成「把节点接进链表」与「宣告栈顶换人」。

pop 就不同了。t = load(Top) 与 nx = load(t.next) 是两次独立的载入，第二次读的是别人也能改的内存。ABA 是这个缝隙的一种后果，CAS 与 ABA §3 已经量过；本页看的是另一种，更基础的一种。

2 · 危险窗口

设 T1 执行 pop，读到 t = n3 之后被抢占。T2 抢在前面完成了自己的 pop，把 n3 弹出并交还给分配器。T1 恢复，执行 nx = load(n3.next)——读的是一块已经不属于任何人的内存。

图 2-1 · Treiber 栈上「读已释放节点」的全部交错统计与单步复现。可切换是否立刻回收、调整 T2 连续 pop 的次数，也可一键复现最短的那条出错交错。

穷举 T1 一次 pop、T2 一次 pop 的全部 20 条交错，其中 6 条会读到已释放的节点，占三成。T2 改成连续两次 pop，408 条交错里有 237 条，占 58.1%。把回收关掉（弹出的节点一律不还给分配器）之后，同样这些交错一条错误都没有——安全买回来了，代价是每弹出一个元素就永久漏掉一块内存。

警示 · 带 GC 的语言看不见这一层。JavaScript、Java、Go 里写 Treiber 栈，写完 CAS 循环基本就完了：只要还有一个局部变量指着节点，回收器就不会碰它。这不是「问题不存在」，而是「已经被别人解决过一遍」——GC 干的正是延迟回收，只是它的判据是可达性、代价是停顿。C++ 与 Rust 没有这层地板，本页余下三节全部在补它。

3 · 引用计数

最直白的办法是给每个节点挂一个原子计数：读它之前加一，用完减一，归零才真回收。

这条路正确，但它把开销放到了最热的地方。每一次读都变成对共享内存的两次原子读改写，而读操作在多数结构里远多于写。更麻烦的是它有一个先有鸡还是先有蛋的问题：要给节点的计数加一，得先安全地读到这个节点的地址；而「安全地读到」正是待解决的那件事。破解它需要双宽 CAS 或者 split reference count 这类额外机制，复杂度不比后两条路低。

4 · hazard pointer

hazard pointer 把问题反过来：不去追踪「谁还在引用这个节点」，而是让每个线程主动声明「我正在读哪几个指针」。

每个线程占若干个全局可见的槽。读一个节点之前，先把它的地址写进自己的槽，再重读一遍来源确认没变；用完清掉槽。删除方不立刻 free，而是把节点挂进本线程的退休表；退休表攒到阈值 $R$ 就扫一次：把全部线程的槽收成一个集合，退休表里不在集合内的才真回收，在集合内的留到下一轮。

图 4-1 · hazard pointer 的一次扫描现场，以及扫描阈值 R 与两项代价的关系。可调线程数与 R，对照每回收一个节点的比对次数和峰值未回收节点数。

代价可以写成闭式。一次扫描要建一遍 hazard 集合（ $H$ 个槽）再逐个探查退休表（ $R$ 项），共 $H + R$ 次比对，摊到 $R$ 个节点上是 $H/R + 1$ 。实测与它逐位吻合：8 线程各一个槽时， $R = 1$ 每回收一个节点比对 9.00 次， $R = 32$ 时降到 1.25 次。

另一头是内存。 $R = 1$ 时峰值未回收为 0， $R = 32$ 时涨到 248。两端都有界，这是 hazard pointer 最值钱的性质：延迟回收的节点数上界只与线程数和阈值有关，与任何一个线程停多久无关。

5 · epoch-based reclamation

epoch-based reclamation 走另一条路：不追踪单个指针，而是划代。

全局有一个 epoch 计数。线程进入临界区时把当前 epoch 抄进自己的本地变量，退出时清掉。删除的节点按「退休时的 epoch」归袋。当所有在临界区里的线程本地 epoch 都等于全局 epoch 时，全局 epoch 加一；编号不大于「当前 epoch 减二」的袋子可以整袋回收。

隔两代而非一代，是因为一个线程可能在 epoch $e$ 进入临界区、抓着某个节点一直待到 $e+1$ 才放手。Linux 内核的 RCU 属于同族，只是把「epoch 推进」换成了「等一个 grace period」。

图 5-1 · epoch 推进、垃圾袋分代与未回收量随轮次的变化，并与 hazard pointer 同负载对照。可让某个线程从指定轮次起滞留在临界区，观察回收被卡死。

读路径上的开销降到了极低：进入临界区写一次本地 epoch，这一次写覆盖整段临界区里的任意多次读，而 hazard pointer 是每读一个节点写一次槽外加一道 fence。峰值内存在正常情况下也更小，8 线程 50 轮的实测是 8 对 24。

代价全部压在一个假设上：所有线程都会及时退出临界区。

注 · 本页原本的说法是「epoch 的峰值内存低于 hazard pointer」。实测只在没有滞留线程时成立。让一个线程从第 10 轮起不再退出临界区，epoch 的未回收量从 8 涨到 281，并且随轮数线性增长：50 轮 281、100 轮 631、200 轮 1331，差值恒等于每轮新增的垃圾量，说明一个都没回收成。同一负载下 hazard pointer 的峰值纹丝不动仍是 24。于是那句话改成了现在的写法——两者的峰值不可比较，一个有界一个无界，比的是不同的东西。

6 · 三条路的分工

引用计数：无延迟回收，每读一个节点两次原子读改写<br> hazard pointer：延迟回收有界，每读一个节点一次 store 加一道 fence<br> epoch-based reclamation：延迟回收无界，每段临界区一次 store

判据不是「哪个快」，而是「能不能容忍一个线程长时间不放手」。内核与数据库的读侧临界区短且可控，RCU 与 epoch 在那里近乎免费；而通用库要面对任意用户代码，一个被换出去的线程就能让 epoch 方案的内存无限涨，hazard pointer 的有界性在那里值钱。C++ 标准库在 std::hazard_pointer 上落地的是后者。

值得单独记一笔的是 tagged pointer 与本页三条路的关系。tag 治的是 CAS 认错，本页三条路治的是内存被提前交还，两者正交。ABA 那一节的 3945 条交错里，加了 tag 之后不可线性化的交错从 18 条降到 0，而读到已释放节点的交错仍是 2577 条，一个没少。

7 · 参考文献

Treiber, R. K. (1986). Systems programming: coping with parallelism (Technical Report RJ 5118). IBM Almaden Research Center.
Michael, M. M. (2004). Hazard pointers: safe memory reclamation for lock-free objects. IEEE Transactions on Parallel and Distributed Systems, 15(6), 491–504.
Fraser, K. (2004). Practical lock-freedom (Technical Report UCAM-CL-TR-579, Chapter 5). University of Cambridge Computer Laboratory.
McKenney, P. E., & Slingwine, J. D. (1998). Read-copy update: using execution history to solve concurrency problems. Parallel and Distributed Computing and Systems, 509–518.
Brown, T. A. (2015). Reclaiming memory for lock-free data structures: there has to be a better way. Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 261–270. 对比了当时全部主流方案的读路径开销与最坏内存。