为什么需要内存回收

主线位置：回收主线的起点。还没有任何代码在跑，先把问题说清楚：一块被摘下来的内存，在什么条件下才能释放。

sequenceDiagram
  participant A as 线程 A（pop）
  participant S as 栈顶 head
  participant B as 线程 B（pop）
  A->>S: 读 head，得到节点 N
  B->>S: 读 head 得到 N，CAS(head, N, N.next) 成功
  B->>B: free(N)
  A->>A: 读 N.next（N 已释放：use-after-free）
  Note over A,B: 若 N 的地址又被分配给新节点并被压回栈顶，<br/>A 的 CAS(head, N, 旧 next) 会成功：ABA

问题：摘下来不等于没人在用

用最简单的无锁栈（Treiber 栈）说明。crossbeam-epoch 自己的 loom 测试里就有一个（tests/loom.rs 第 98 行），pop 的核心是：

let head = self.head.load(Acquire, &guard);
match unsafe { head.as_ref() } {
    Some(h) => {
        let next = h.next.load(Relaxed, &guard);
        if self
            .head
            .compare_exchange(head, next, Relaxed, Relaxed, &guard)
            .is_ok()
        {
            unsafe {
                guard.defer_destroy(head);
                return Some(ManuallyDrop::into_inner(ptr::read(&(*h).data)));
            }
        }
    }
    None => return None,
}

读 head、读 h.next、CAS，这三步之间没有锁。去掉最后那行 defer_destroy，换成直接释放，就会出两种错：

• use-after-free：线程 A 读到了 head == N，还没读 N.next；线程 B 抢先把 N 摘下来并释放。A 接着读 N.next，读的是已经还给分配器的内存。
• ABA：B 释放 N 以后，分配器把同一块地址发给了一个新节点，这个新节点又被压回栈顶。A 醒来做 CAS(head, N, 旧的 next)：比较的只是地址，地址对上了，CAS 成功，栈顶被改成一个早已被摘掉的节点。

两个错误的根子是同一个：B 不知道还有没有别的线程手里攥着 N 的指针。只要 N 在所有可能的读者离开之前不被释放，地址就不会被复用，ABA 也随之消失。内存回收方案要回答的就是「怎么知道读者都离开了」。

有垃圾回收器的语言把这件事交给运行时；crate 文档的第一段说的就是这一点（lib.rs 第 1–20 行）。Rust 里只能自己做。

三种做法

下面只比机制，不比性能。性能取决于读写比例、线程数、对象大小，没有通用的结论。

引用计数：每个节点带一个计数，读者在用之前加一、用完减一，减到零的那个人释放。难点在「读到指针」和「把计数加一」不是一个原子操作：读到指针以后、加一之前，节点可能已经被减到零释放了。常见的补法是双字 CAS（指针和计数打包一起改），或者把计数拆成「外部计数 + 内部计数」。不管哪种，每次读共享指针都是一次对共享缓存行的原子读改写。Arc 的克隆就是这一侧的例子，bytes 卷「clone 与提升」讲了它的内存序和 CAS 提升。

hazard pointer：每个线程有几个公开的「危险指针」槽。读者读到指针后，先把它写进自己的槽，再重新读一次共享位置确认它没变（中间要一道 store-load 屏障），然后才能解引用。回收者想释放一个节点时，扫描所有线程的槽，只要有人登记了它就先留着。好处是未回收的垃圾有上界（和「线程数 × 每线程槽数」成正比）；代价是每次读一个新指针都要发布 + 校验一次。

基于纪元的回收（EBR）：全局有一个纪元计数，每个线程有一个本地纪元。读者进入一段访问共享数据的代码前，把全局纪元抄到本地并标记「已钉住」（pin），离开时清掉标记。这段代码里读多少个指针都不再付额外开销。回收者把摘下的节点连同当时的纪元一起存起来；只有当全局纪元比它往前走了足够多步（crossbeam 里是 2 步），而全局纪元只有在「所有已钉住的线程都已经看到当前纪元」时才能前进，于是那时不可能再有读者攥着它。代价是：一个线程长期钉住，全局纪元就走不动，所有人的垃圾都放不掉，垃圾没有上界。

crossbeam 的选择

crossbeam-epoch 选的是 EBR。读侧几乎零开销对它的几个用户最重要：deque 的每次 steal、skiplist 的每次查找都要读共享指针；按 EBR，一次 steal 只需要 pin 一次，pin 里的那道 SeqCst fence 还被 deque 顺手拿来当自己需要的屏障用（Chase-Lev 双端队列）。

代价也写在 API 文档里。Guard::defer_destroy 的文档原话是：「There is no guarantee when exactly the destructor will be executed. The only guarantee is that it won't be executed until all currently pinned threads get unpinned. In theory, the destructor might never run」（guard.rs 第 207–210 行）。「一个线程长期 pin 住，垃圾一个都放不掉」在实验 E3 里量过：20 万个 1 KiB 的对象，析构 0 个，RSS 从 1920 KiB 涨到 211248 KiB（约 206 MiB），见 defer 与回收。

还有一点要先说清楚：EBR 只解决「什么时候释放」，不解决「能不能看到」。读者读到的指针在 pin 期间不会被释放，但它可能已经不在结构里了（被别人摘掉、正在等回收）。数据结构自己要处理「读到一个已删除节点」的情况，比如 skiplist 删除时先在指针低位打标记，下一章讲这些标签位。

小结

• 无锁结构里摘下的节点不能立即释放：别的线程可能刚读到它的指针。直接释放会造成 use-after-free，地址被复用还会造成 ABA。
• 引用计数让每次读都付一次原子读改写；hazard pointer 让每次读都付「发布 + 屏障 + 校验」，换来有界的垃圾；EBR 把开销挪到进出临界区（pin / unpin），临界区内读多少指针都不额外付钱。
• EBR 的代价是垃圾没有上界：一个线程长期 pin 住，全局纪元停住，所有垃圾都等着。
• crossbeam 选 EBR，deque 和 skiplist 都建在它上面。EBR 只管「何时释放」，数据结构仍要自己处理读到已摘除节点的情况。