Epoch-Based Reclamation：两个纪元的由来、Crossbeam 的实现与停顿的代价
内容提要
本文基于Fraser 2004年博士论文，分析纪元回收（EBR）机制：挂起节点需等待两个纪元才能释放，标签应使用全局纪元而非线程自身纪元，并解读crossbeam-epoch 0.9.18源码。实测表明，提前一纪元释放或使用本地纪元打标签会触发use-after-free；EBR在长遍历中开销极低，但在短操作上比hazard pointers慢约12%。
延伸解读
两个纪元的必要性：从证明到变异体
文章通过形式化证明和变异体测试，解释了EBR必须等待两个纪元的原因。证明显示，若只等一个纪元，读者可能在节点被摘下前进入临界区并持有引用，导致释放后使用。变异体EBR_GAP=1在竞争窗口下被ASan和TSan频繁捕获，而正确版本无报告。这强调了遵循算法细节的重要性，也展示了形式化验证与实证测试的结合。
标签纪元的选择：全局与局部的陷阱
使用线程本地纪元而非全局纪元为退休节点打标签，看似节省一次共享读，实则引入微妙错误。文章通过序列图说明，本地标签可能比实际退休时的全局纪元小，导致节点过早释放。变异体EBR_TAG_LOCAL=1在低竞争下难以触发，但高竞争时ASan和TSan均能捕获。正确做法是使用全局纪元，或本地标签但多等一个纪元。
性能权衡：EBR在长遍历与短操作中的表现
EBR将保护粒度从单个指针扩大到整个操作，在长遍历中优势明显：每次遍历只pin一次时，开销与无保护几乎相同。但在短操作如Treiber栈的push/pop上，EBR比HP慢12%-13%，因为每次操作仍需宣告和栅栏，且垃圾释放延迟导致缓存局部性差。性能取决于每次操作访问的节点数和垃圾停留时间，而非方案本身。
垃圾积累：由最慢的临界区决定
EBR的垃圾回收受限于最慢的临界区。单线程时峰值是推进间隔的两倍；多线程下，若一个线程在临界区中被抢占，其他线程的推进尝试会失败，导致垃圾积压。实测中，一个读者每次停100ms，峰值达170万节点；若一直停住，所有退休节点都无法释放。这揭示了EBR的非鲁棒性：内存无界，依赖所有线程及时离开临界区。
Q&A
EBR 中挂起的节点为什么要等两个纪元才能释放？等一个纪元为什么不够？
因为一个仍在临界区里的线程，它宣告的纪元最多比全局纪元 G 小 1。若只等一个纪元，当 G 从 g 推进到 g+1 时，一个在 x 被摘下之前、G=g 时进入临界区并读到 x 的读者可能还没离开，此时释放 x 会导致 use-after-free。等两个纪元（G ≥ g+2）能保证所有可能持有 x 的读者都已离开临界区。
EBR 中给挂起节点打标签应该用全局纪元还是线程自己的纪元？
应该用全局纪元。用线程自己的纪元（pin 时宣告的纪元 w）作标签，可能因为其他线程已把 G 推进到 w+1，而读者可以宣告 w+1 并在 x 被摘下前读到它，导致提前释放。用全局纪元作标签时，标签是摘下后读到的 G，需要等到 G ≥ 标签+2 才释放，这样才安全。
crossbeam-epoch 0.9.18 在 x86 上为什么用 lock cmpxchg 代替栅栏？这个选择今天还成立吗？
crossbeam 在 x86 上用一次对自己宣告字的 SeqCst CAS（编译为 lock cmpxchg）代替 SeqCst 栅栏，因为源码注释称基准测试显示这样 pin 更快。但实测表明，今天编译器已将 SeqCst 栅栏编译为 lock or（2.45 ns），而 lock cmpxchg 是 3.00 ns，并不更快；mfence 则贵得多（20 ns）。所以这个选择在速度上已不再有优势，且它可能不被 C++ 内存模型允许，只是 x86 硬件上安全。
EBR 在什么情况下比 hazard pointers 便宜，什么情况下反而更贵？
EBR 在长遍历中开销极低：每次遍历只 pin 一次时，1000 个节点分摊一次宣告，每节点开销与不保护几乎相同（1.45 ns vs 1.38 ns）。但在短操作上，如 Treiber 栈的 push/pop，EBR 比 HP 慢 12% 到 13%，因为每次操作都要付宣告代价，且垃圾释放延迟导致缓存不友好。
EBR 中一个读者停住时垃圾会涨到多少？没有人故意停住时呢？
一个读者每次在临界区里停 D 微秒时，峰值接近 retire 速率乘以 D：D=100 ms 时峰值约 170 万节点。若读者一直不出来，所有被 retire 的节点都无法释放，垃圾随操作数线性增长。没有人故意停住时，2 线程下采样中位数在 235 到 2067 节点之间，但峰值可达 6.5 万到 14.5 万，主要由调度抢占导致。
crossbeam-epoch 的回收速率上限是多少？为什么会有这个上限？
crossbeam 每 128 次 pin 最多析构 8 袋、每袋 64 个对象，平均每次 pin 最多析构 4 个对象。如果每个临界区平均 retire 超过 4 个对象，积压就会线性增长。实测单线程每次 pin retire 16 个对象时，结束时 75.1% 未析构，与 1-4/16 吻合。
