引言你的 lock-free queue 通过了所有单元测试在 4 线程环境下稳定跑了整整一周性能数据漂亮直到你把压测线程数拉到 64跑了 17 分钟后收到 SIGSEGV打开 coredump 一看崩溃地址指向的那块内存已经被 free 掉又被另一次 enqueue 重新 allocate 成了一个全新的节点而 dequeue 线程还在拿着这个地址做 CAS 比较比较成功了——因为新节点的 next 指针恰好和旧节点的 next 指针值相同——然后整个队列的链表结构被撕裂后续所有操作都在一个已经断裂的链上狂奔直到某个线程解引用了一个彻底非法的地址。这不是一个低级 bug。每一步 CAS 操作都正确地返回了 true每一个原子操作都满足了 memory ordering 的要求TSan 在低并发下也报不出任何 data race。问题出在一个更深层的地方你的无锁队列没有解决什么时候可以安全地释放一个已经被逻辑删除的节点这个问题。这就是无锁编程中最隐蔽、最致命、也最经常被先跑起来再说的程序员忽略的问题——内存回收的生死时序。这篇文章要做的事情是从那个 coredump 出发沿着 ABA 问题的精确时序一步步追踪崩溃的根因然后从 1983 年 IBM 的第一个 ABA 相关专利讲到 2004 年 Maged Michael 提出 Hazard Pointer再到 2024 年即将进入 C26 标准的std::hazard_pointer让你建立起对 lock-free 内存回收的完整认知——不只是知道有这个东西而是能够精确判断在我的场景下该用 Hazard Pointer 还是 Epoch-Based Reclamation以及为什么。无锁队列的内存回收困境CAS 成功不代表操作安全在讲 ABA 问题之前我们需要先理解一个很多人没有想清楚的前提在无锁数据结构中逻辑删除和物理释放是两个完全不同的动作而这两个动作之间的时间差正是所有麻烦的根源。用 Michael-Scott lock-free queue1996 年 PODC 论文至今仍是教科书级的 lock-free queue 参考实现来说明这个问题。dequeue 操作的核心逻辑是这样的// Michael-Scott Queue dequeue (简化版) // 参考Michael Scott, PODC 1996 Node* dequeue() { while (true) { Node* head Head.load(std::memory_order_acquire); Node* tail Tail.load(std::memory_order_acquire); Node* next head-next.load(std::memory_order_acquire); if (head Head.load(std::memory_order_acquire)) { if (head tail) { if (next nullptr) return nullptr; Tail.compare_exchange_weak(tail, next); } else { T value next-data; if (Head.compare_exchange_weak(head, next)) { // CAS成功head节点已被逻辑删除 // 问题这里能直接 delete head 吗 return value; } } } } }看到那行注释了吗——这里能直接 delete head 吗 答案是绝对不能。原因很简单但后果极其严重当线程 A 执行 CAS 成功、把 Head 从head推进到next的那一瞬间可能有另外 10 个线程正卡在第 5 行——它们已经把head这个地址读到了本地变量里正准备用它做后续的操作读取head-next、或者把它作为 CAS 的期望值。如果线程 A 此时delete head那些线程接下来对head-next的读取就是 use-after-free在最好的情况下读到垃圾数据导致 CAS 失败然后重试在最坏的情况下这块内存已经被 allocator 分配给了别的对象读到的next指针指向一个完全不相关的地址然后你的程序就以一种极其诡异的方式崩溃了。这个困境的数学表述非常精确设线程 i 在时刻 t1 读取了共享指针 P 的值 p然后在时刻 t2 使用 p解引用或作为 CAS 参数那么在整个区间 [t1, t2] 内p 指向的内存必须保持有效。但在无锁环境下没有任何机制保证这一点——另一个线程可能在 t1 和 t2 之间把 p 指向的节点从数据结构中移除并释放。这就是无锁内存回收的核心矛盾你需要释放已删除的节点来避免内存泄漏但你不知道有多少其他线程还持有指向这个节点的指针。带锁的数据结构不存在这个问题因为锁保证了在你持有锁的期间没有其他线程能修改或释放任何东西GC 语言也不存在这个问题因为垃圾收集器会自动追踪所有引用。但在 C 的无锁世界里你必须自己解决这个问题。最天真的解决方案是永远不释放——节点从队列中删除后放进一个 free list将来 enqueue 需要新节点时从 free list 中取而不是 malloc。这消除了 use-after-free因为内存永远有效但引入了另一个问题。ABA 问题的时序解剖每一步都正确组合起来却是灾难ABA 的精确定义ABA 问题不是一个模糊的可能出错——它有精确的触发条件和确定的后果。让我用一个完整的时序表来展示它是如何在一个看起来完全正确的 Michael-Scott queue 中被触发的。场景设定队列当前状态为Head → A → B → CHead 是哨兵节点A 是队头的实际数据节点。线程 T1 执行 dequeue线程 T2 也执行 dequeue线程 T3 执行 enqueue。假设被删除的节点通过 free list 回收再利用这是很多naive实现的做法。时刻T1 (dequeue)T2 (dequeue)T3 (enqueue)队列状态t0读取 headA, nextB--Head→A→B→Ct1被调度出去--Head→A→B→Ct2-读取 headA, nextB-Head→A→B→Ct3-CAS(Head, A, B) 成功-Head→B→C, A 进入 free listt4--从 free list 取出 A写入新数据Head→B→Ct5-读取 headB, nextC-Head→B→Ct6-CAS(Head, B, C) 成功-Head→C, B 进入 free listt7--A-next C, CAS(Tail...)Head→C→A(新数据)t8被调度回来--Head→C→A(新数据)t9CAS(Head, A, B) ???--???关键时刻来了。T1 在 t0 读取了headA, nextB然后被调度出去。等它在 t8 回来时试图执行CAS(Head, A, B)——把 Head 从 A 改为 B。但此时队列的真实状态已经是Head→C→A(新数据)Head 并不指向 A。等等那 CAS 不是应该失败吗不一定。这取决于实现细节。在上面的时序中如果 T3 的 enqueue 恰好把节点 A物理上同一块内存但逻辑上是一个全新的节点又放回了队列的某个位置并且在某些更复杂的队列变种中 Head 恰好又指向了 A 的地址——CAS 比较的是地址值不是语义身份它看到Head 的值还是 A 的地址就认为没人动过然后把 Head 改成了 B。但 B 此时已经不在队列里了——它在 t6 就被 T2 删除并放进了 free list。于是 Head 指向了一个已经不属于队列的节点整个链表结构断裂。让我把这个过程中 CAS 的欺骗讲得更精确一些。CAS 操作的语义是CAS(addr, expected, desired): atomically { if (*addr expected) { *addr desired; return true; } else { return false; } }这里的比较的是位模式bit pattern不是语义等价性。当 T1 用地址 A 作为 expected 去做 CAS 时CAS 只检查 Head 里存的是不是 A 这个地址值——它无法区分Head 指向 A 且 A 仍然是原来那个队头节点和Head 指向 A 但 A 已经是一个被回收再利用的全新节点。这就是 ABA 的本质指针值相同但指针指向的语义对象已经不是同一个了。为什么低并发下测不出来你可能会问既然 ABA 这么致命为什么我的 4 线程测试跑一周都没事答案在于概率。ABA 的触发需要一个极其精确的时序窗口——线程 T1 必须在读取了 head和执行 CAS之间被挂起足够长的时间在这个时间窗口内其他线程必须完成删除原节点→回收→再分配→恰好放回相同位置的完整循环。在 4 线程下这个窗口被命中的概率极低每次 dequeue 操作从读取 head 到执行 CAS 可能只有几十纳秒而节点从删除到被重新分配需要另一个线程恰好在这个窗口内完成多步操作。但当线程数增加到 64 时情况完全不同。更多线程意味着更频繁的调度切换OS 调度器在 64 线程争抢 CPU 时会频繁抢占每次抢占都可能让某个线程停在读取 head和执行 CAS之间。同时更多线程意味着更高的 free list 周转率——节点被删除后几乎立刻就会被另一个 enqueue 线程从 free list 中取走重用。这两个因素叠加让 ABA 的触发概率从几乎不可能变成了17 分钟内必然发生。我做过一个粗略的概率估算假设单次 dequeue 在读取 head和执行 CAS之间停留的平均时间为 τ取决于线程数和调度频率free list 中节点从被放入到被取出的平均时间为 λ那么单次操作触发 ABA 的概率大约正比于 (N-1)/N × τ/λ其中 N 是线程数。当 N4, τ≈50ns, λ≈10μs 时这个概率在 10^-5 量级当 N64, τ≈5μs因为频繁抢占, λ≈100ns因为高周转率时概率飙升到 10^-1 量级。这就是为什么 4 线程跑一周没事64 线程 17 分钟就崩。ABA 的三种后果根据队列的具体状态和触发时刻ABA 可能导致三种不同的后果严重程度递增后果一丢失节点。最轻微的情况——几个节点从队列中消失了它们的 dequeue 永远不会返回给消费者但程序不会崩溃。在消息队列场景下这意味着消息丢失在任务队列场景下意味着任务被静默丢弃。后果二链表循环。中等严重——ABA 导致链表中出现环路某个 dequeue 操作陷入无限循环不断沿着 next 指针走但永远走不到 nullCPU 占用率飙升到 100% 但没有崩溃。这种 bug 在生产环境中表现为服务突然变慢然后 hang 住。后果三use-after-free → SIGSEGV。最严重的情况——dequeue 线程解引用了一个已经被释放并重新分配给其他用途的地址直接触发段错误。这就是文章开头那个 coredump 的场景。如果这块内存恰好没有被重新分配还在 allocator 的 free pool 中你甚至可能读到看起来合理的数据——程序不崩溃但默默返回错误结果这比 SIGSEGV 更可怕因为你可能几天后才从下游系统发现数据不一致。我的判断是任何在生产环境中使用 free list 做节点回收的 lock-free queue如果没有配套的内存回收方案Hazard Pointer / EBR / RCU在高并发压测下必然会触发 ABA。这不是可能是一定——只是时间早晚的问题。如果你的 lock-free queue 在跑得好好的唯一的解释是你的并发度不够高、或者你的测试时间不够长。Tagged Pointer一个流行但有上限的缓解方案面对 ABA 问题最直觉的解决思路是既然 CAS 无法区分地址相同、语义不同的两个状态那我给每个指针加一个版本号不就行了每次修改指针的同时递增版本号CAS 同时比较地址和版本号——即使地址回到了原来的值版本号也已经变了CAS 就会失败。这就是 tagged pointer也叫 stamped pointer 或 counted pointer方案// Tagged pointer: 将 counter 和指针打包到一个 atomic 变量中 struct TaggedPtr { Node* ptr; uint64_t tag; }; // 在64位系统上用128位CAS (cmpxchg16b on x86-64) std::atomicTaggedPtr Head; // dequeue 时 TaggedPtr old_head Head.load(); // ... 读取 next ... TaggedPtr new_head{next, old_head.tag 1}; Head.compare_exchange_weak(old_head, new_head); // 即使 ptr 回到了原来的值tag 已经不同CAS 不会被欺骗这个方案在 x86-64 上需要cmpxchg16b指令128 位 CAS在 ARM64 上需要LDXP/STXPload-exclusive pair / store-exclusive pair。大多数现代处理器都支持但有两个根本性的问题问题一tag 溢出。tag 是有限位数的整数通常 32 位或 64 位理论上会溢出回到 0。在 64 位 tag 的情况下需要 2^64 次修改才会溢出——以每秒 10 亿次操作计算需要跑 584 年。所以 64 位 tag 在工程实践中可以认为不会溢出。但如果你为了在 64 位系统上避免使用 128 位 CAS性能损耗约 2-3x而把 tag 压缩到了高 16 位利用 x86-64 的 canonical address 特性用户空间指针的高 16 位总是 0那 16 位 tag 只能撑 65536 次修改——在 64 线程每秒 200 万次操作的场景下大约 30 毫秒就溢出一轮。虽然 ABA 还需要在溢出的精确时刻命中概率很低但很低在压测面前毫无意义——给足够长的时间必然触发。问题二tagged pointer 不解决内存回收问题。这一点至关重要。tagged pointer 只是让 CAS 不会被地址复用欺骗——它保证了 CAS 操作本身的逻辑正确性。但如果你在 CAS 成功后delete head其他线程仍然可能在head-next这一步 use-after-free。tagged pointer 保护的是CAS 决策点不是节点的生命周期。说得更直白一些tagged pointer 解决的是CAS 被骗ABA但没有解决节点被提前释放use-after-free。如果你用了 tagged pointer 但仍然在 CAS 成功后立刻delete你的程序在 64 线程压测下照样会崩——只不过崩溃的原因从CAS 被骗导致链表断裂变成了其他线程解引用已释放内存。很多 lock-free queue 的实现选择了一个妥协tagged pointer 永不释放或者 tagged pointer free list 永不归还 OS。这确实能避免崩溃——tagged pointer 保证 CAS 不被骗永不释放保证不会 use-after-free。代价是内存只增不减在长时间运行的服务中最终会 OOM。所以真正的问题不是怎么让 CAS 不被骗——tagged pointer 已经解决了这个——而是怎么在不加锁的前提下判断一个节点是否可以安全释放。这正是 Hazard Pointer 要解决的问题。Hazard Pointer 的设计哲学用声明式保护取代引用计数历史脉络从 lock-free 的内存管理绝望到 Maged Michael 的突破lock-free 数据结构的内存回收问题从 1990 年代就开始折磨研究者了。在 Maged Michael 2004 年发表那篇开创性论文之前这个领域尝试过三条路径但每条路都走进了死胡同第一条死路引用计数。最自然的想法——给每个节点维护一个引用计数线程访问节点时 1离开时 -1计数归零时释放。问题在于引用计数的增减本身需要原子操作而在 lock-free 场景下你面临一个鸡生蛋蛋生鸡的困境你想递增节点 A 的引用计数但递增之前你需要先读取 A 的地址而在你读取地址和递增引用计数之间A 可能已经被其他线程释放了。你需要一个原子的读取指针并递增引用计数操作但这需要多字 CAS 或 LL/SC 对在大多数架构上不可用或效率极低。第二条死路延迟释放 全局屏障。类似 RCU 的思路——删除节点时不立即释放等所有线程都经过了一个安全点后再批量释放。这在内核态Linux RCU工作得很好因为内核知道每个 CPU 何时发生了上下文切换这是一个天然的安全点。但在用户态没有一个高效的机制让你知道所有线程是否都已经完成了它们当前的 lock-free 操作——你总不能让每个线程在每次操作前后都递增一个全局计数器吧那和加锁有什么区别第三条死路type-preserving allocator。不把内存归还 OS也不改变内存的类型——确保一个 Node 地址永远只存放 Node 类型的数据。这解决了 use-after-free 导致的类型混乱不会把 Node 的 next 指针当成另一个对象的数据字段来读但不解决语义混乱同一地址的新 Node 和旧 Node 是不同的逻辑实体tagged pointer 已经解决了这个问题。更大的问题是内存永远不会被释放长时间运行的服务最终会 OOM。2004 年IBM 研究院的 Maged Michael 发表了 Hazard Pointers: Safe Memory Reclamation for Lock-Free ObjectsIEEE TPDS, Vol. 15, No. 6提出了一个优雅得令人赞叹的方案让每个线程显式声明我正在使用哪些指针一个节点只有在没有任何线程声明正在使用它时才能被安全释放。这个方案的天才之处在于它把一个全局问题有没有任何线程还在用这个节点转化成了一个可高效检查的本地问题遍历一遍所有线程的声明列表看看有没有人声明了这个地址。Hazard Pointer 的核心机制三步协议Hazard Pointer 的工作原理可以压缩成三个操作Protect保护、Retire退役、Scan扫描回收。Protect保护—— 线程声明我正在使用这个指针// 每个线程有固定数量的 hazard pointer slot // 对于 Michael-Scott queue每个线程需要2个 thread_local std::arraystd::atomicvoid*, K my_hazard_ptrs; void protect(int slot, void* ptr) { my_hazard_ptrs[slot].store(ptr, std::memory_order_release); } void unprotect(int slot) { my_hazard_ptrs[slot].store(nullptr, std::memory_order_release); }Retire退役—— 线程声明我已经把这个节点从数据结构中移除了但先别急着 freethread_local std::vectorvoid* retired_list; void retire(void* ptr) { retired_list.push_back(ptr); if (retired_list.size() R) { // R 是阈值通常设为 2*N*K scan(); } }Scan扫描回收—— 检查退役列表中的每个节点如果没有线程在保护它就释放void scan() { // 第一步收集所有线程的 hazard pointer 值 std::unordered_setvoid* protected_ptrs; for (int t 0; t num_threads; t) { for (int k 0; k K; k) { void* hp all_hazard_ptrs[t][k].load( std::memory_order_acquire); if (hp ! nullptr) { protected_ptrs.insert(hp); } } } // 第二步遍历退役列表释放不在保护集中的节点 auto it retired_list.begin(); while (it ! retired_list.end()) { if (protected_ptrs.find(*it) protected_ptrs.end()) { delete static_castNode*(*it); it retired_list.erase(it); } else { it; } } }为什么 Protect 必须在验证之前一个致命的顺序错误这里有一个极其容易写错的顺序问题错了就会导致 use-after-free而且 TSan 在低并发下几乎不可能报出来。错误写法先验证再保护// ❌ 错误先检查指针有效性再设置 hazard pointer Node* head Head.load(std::memory_order_acquire); if (head nullptr) return nullptr; Node* next head-next.load(); // 危险head 可能已经被释放 my_hazard_ptrs[0].store(head); // 太晚了保护在使用之后正确写法先保护再验证// ✅ 正确先设置 hazard pointer再验证指针仍然有效 Node* head Head.load(std::memory_order_acquire); my_hazard_ptrs[0].store(head, std::memory_order_release); // 关键必须重新验证 head 仍然是当前的 Head // 因为在 load 和 store 之间head 可能已经被删除并回收 if (head ! Head.load(std::memory_order_acquire)) { // head 已经变了重新开始整个操作 continue; } // 现在可以安全使用 head 了 Node* next head-next.load(std::memory_order_acquire); // 安全这个先保护再验证的模式protect-then-validate是 Hazard Pointer 正确使用的核心——它的逻辑是这样的在你设置 hazard pointer 的那一瞬间之后任何执行 scan 的线程都能看到你的保护声明因此不会释放这个节点。但在你设置 hazard pointer 之前这个节点可能已经被 retire 并且被 scan 释放了。所以你需要在设置保护之后重新验证这个指针还是你想保护的那个——如果验证失败说明它可能已经被释放了你需要从头来过。这个顺序写反是我见过的 Hazard Pointer 实现中最常见的 bug。很多人的直觉是先确认指针有效再保护但正确的做法是反过来——先无条件保护再确认是否值得保护。如果不值得验证失败你浪费的只是一次 atomic store如果你按直觉来浪费的可能是一条命use-after-free。将 Hazard Pointer 接入 Michael-Scott Queue有了 Hazard Pointer 的三步协议我们可以把它接入 Michael-Scott queue 的 dequeue 操作。对于 M-S queue每个线程需要 2 个 hazard pointer slot一个保护 head当前队头一个保护 next队头的下一个节点。// Michael-Scott Queue Hazard Pointer 的 dequeue // 参考实现基于 Maged Michael 2004 论文 Section 5.2 T dequeue() { while (true) { Node* head Head.load(std::memory_order_acquire); hp_protect(0, head); if (head ! Head.load(std::memory_order_acquire)) { continue; } Node* tail Tail.load(std::memory_order_acquire); Node* next head-next.load(std::memory_order_acquire); hp_protect(1, next); if (head ! Head.load(std::memory_order_acquire)) { continue; } if (head tail) { if (next nullptr) { hp_clear(0); hp_clear(1); return EMPTY; } Tail.compare_exchange_weak(tail, next); } else { T value next-data; if (Head.compare_exchange_weak(head, next)) { hp_clear(0); hp_clear(1); hp_retire(head); return value; } } hp_clear(0); hp_clear(1); } }这段代码中有几个关键的设计决策值得展开为什么需要两次验证 head第一次验证在hp_protect(0, head)之后确保我们保护的确实是当前的 head。第二次验证在hp_protect(1, next)之后确保在我们读取head-next的过程中 head 没有被其他线程 dequeue 并 retire——如果被 retire 了我们读到的 next 可能是垃圾值虽然我们的 hazard pointer 保护了 head 不被 free但如果 head 已经不是 Head 了next 的值可能已经被其他操作修改了。为什么 CAS 成功后先 hp_clear 再 hp_retire因为 CAS 成功意味着 Head 已经从 head 推进到了 next此时其他线程不会再通过 Head 访问到 old head 了——新的线程看到的 Head 是 next不是 head。但已经进入循环并读取了 old head 地址的线程可能还在用它它们的 hazard pointer 会保护它所以我们不能直接 delete而是 retire 它让 scan 来判断。hp_retire 后什么时候真正被释放取决于其他线程何时清除对 head 的保护。如果所有线程都已经推进到了新的 headnext那下一次 scan 就能释放它。如果有某个线程卡在 retry loop 里还保护着 head那它会继续存活在退役列表中直到那个线程进入下一次迭代并更新了它的 hazard pointer。Hazard Pointer 的内存上界为什么它是确定性安全的Hazard Pointer 最强大的理论保证是它对未回收内存有一个严格的上界。在任意时刻系统中未被回收的退役节点数最多为上界 N × (R K×N)其中 N 线程数K 每个线程的 hazard pointer 数量对 M-S queue 是 2R 触发 scan 的阈值retired_list 达到 R 个节点时执行 scan。这个上界的含义是每个线程最多持有 R 个未被 scan 的退役节点加上最多有 K×N 个节点被其他线程的 hazard pointer 保护着无法释放。通常 R 被设置为 2×K×N所以上界约为 N × 3KN 3KN²。对于 64 线程、K2 的 M-S queue 场景上界是 3×2×64² 24576 个节点。如果每个节点 64 字节这是约 1.5 MB 的延迟释放开销——在绝大多数场景下完全可以接受。这个上界是确定性的——不存在运气不好就无限增长的情况。这和 Epoch-Based Reclamation 形成鲜明对比后者在某个线程长时间不进入安全点比如被长时间调度出去时退役列表可以无限增长。我的判断是如果你的系统对内存使用有严格的上界要求嵌入式、实时系统、或者内存受限的容器化部署Hazard Pointer 是唯一能给你确定性内存上界保证的 lock-free 回收方案。EBR 在理论上没有上界保证虽然实践中通常表现很好RCU 在用户态实现中也面临类似的无界问题。生死时序用一张完整的时序表证明 Hazard Pointer 为什么是安全的到目前为止我讲了 Hazard Pointer 的机制——Protect/Retire/Scan 三步协议。但知道怎么用和理解为什么安全是两个完全不同层次的认知。很多人用了 Hazard Pointer 之后仍然心里不踏实凭什么 Protect 和 Scan 之间没有 race condition凭什么我 Protect 之后、Scan 读取我的 hazard pointer 之前的那个窗口里节点不会被释放最危险的交错场景场景设定队列状态Head → A → B → C线程 T1 执行 dequeue目标是摘掉 A线程 T2 也执行 dequeue 并且还会触发 scan。最危险的交错是T1 正在保护 A 的过程中T2 已经把 A retire 了并且开始 scan。时刻T1 (dequeuer)T2 (dequeuer scanner)A 的状态t0head Head.load()→ 得到 A-在队列中t1hp[0].store(A)-在队列中被T1保护t2-head Head.load()→ 得到 A在队列中被T1保护t3-hp[0].store(A)被T1和T2保护t4-验证 head Head → 通过同上t5-next A-next→ 得到 B同上t6-CAS(Head, A, B)→ 成功逻辑删除仍被T1和T2保护t7-hp[0].clear(); hp[1].clear()逻辑删除仅被T1保护t8-retire(A)→ A进入retired_list退役仅被T1保护t9-scan()开始收集所有 hazard pointer退役仅被T1保护t10-scan 读取 T1.hp[0] →发现值为 A退役scan知道被保护t11-A 在 protected_set 中跳过不释放退役安全保留t12验证 head Head →失败-退役仅被T1保护t13hp[0].clear()→ 重新开始-退役无人保护t14-下次 scan 发现 A 无保护退役无人保护t15-delete A→安全释放已释放关键观察点t9-t10 是整个协议的安全关键。在 t9T2 的 scan 开始收集所有线程的 hazard pointer。它读取 T1 的hp[0]发现值为 A。这个读取使用memory_order_acquire配合 T1 在 t1 时hp[0].store(A)使用的memory_order_release构成了一个 acquire-release 同步——T2 在 t10 看到的 A一定是 T1 在 t1 或之后存入的值不会看到更早的 nullptr。如果 T1 在 t1 和 t12 之间被完全调度出去呢没关系。只要 T1 的hp[0]中存着 A 的地址任何线程的 scan 都不会释放 A。T1 可以被调度出去几秒钟、几分钟A 都不会被释放。代价是 A 的内存在这段时间内不能被回收——这就是 Hazard Pointer 的延迟释放开销但它是有上界的。如果 T2 的 scan 在 T1 的 store 之前执行呢t9 发生在 t1 之前这意味着 T1 还没有保护 Ascan 也不会看到 A 在 T1 的 hazard pointer 中。但此时 A 还没有被 retireretire 发生在 t8而 t8 t6 t1所以 scan 根本不会去检查 A——A 不在 T2 的 retired_list 中。安全。Safety Invariant 的形式化描述用一个更精确的不变量来描述 Hazard Pointer 的安全性Safety Invariant: 节点 P 被释放当且仅当(1) P 在某个线程的 retired_list 中且 (2) 执行 scan 时P 不在任何线程的 hazard pointer 中。条件 (1) 要求 P 已经被从数据结构中逻辑删除否则不会被 retire。条件 (2) 要求没有线程声明正在使用 P。这两个条件一起保证了如果一个线程正在使用 P它的 hazard pointer 中有 PP 就不会被释放。这个不变量的证明核心在于 protect-then-validate 协议如果一个线程 T 通过hp.store(P)验证 P 仍在数据结构中这两步都成功了那么在 T 清除它的 hazard pointer 之前P 一定不会被释放——因为任何执行 scan 的线程在收集 hazard pointer 时一定会看到 T 的声明acquire-release 语义保证了可见性。一个反面案例protect 和 retire 的顺序写错了来看一个真实会出错的实现。假设某个程序员认为先 retire 再 scan 就够了protect 的时机不重要// ❌ 错误实现dequeue 时在读取 next 之后才设置 hazard pointer T broken_dequeue() { while (true) { Node* head Head.load(std::memory_order_acquire); Node* next head-next.load(std::memory_order_acquire); // head 可能在上面两行之间已经被 retire scan free hp_protect(0, head); // 太晚了 if (head ! Head.load(std::memory_order_acquire)) { continue; } // ... 后续 CAS ... } }这段代码的问题在哪在Head.load()和head-next.load()之间存在一个未保护的窗口。在这个窗口内另一个线程可能执行了完整的dequeue(A) → retire(A) → scan() → free(A)序列。当 T1 执行head-next.load()时head 指向的内存可能已经被释放并归还给了 OS或被 allocator 分配给了其他对象——这就是 use-after-free。有人可能会说但是后面有head ! Head.load()的验证如果 head 已经被 dequeue 了Head 已经不等于 head 了验证会失败然后重试。 问题是验证发生在 use-after-free 之后。你先head-next.load()了这一步已经是 use-after-free然后才检查是否应该这么做。这就像先开枪再问我是不是该开枪——为时已晚。在低并发下4 线程从Head.load()到head-next.load()只有几纳秒其他线程几乎不可能在这个窗口内完成 dequeueretirescanfree 的完整链路。但在 64 线程下如果 T1 恰好在这两行之间被 OS 调度出去了几十微秒其他线程有充足的时间完成整个回收链路use-after-free 就会发生。这是一个只在高并发压测中才会暴露的 bug也是为什么你的无锁队列4 线程跑一周没事、64 线程 17 分钟崩溃的根本原因之一。Epoch-Based Reclamation一条不同的路以及为什么它不总是更好Hazard Pointer 的确定性安全保证非常强但它有一个工程上的代价每次读取共享指针时都需要一次 atomic store设置 hazard pointer 一次 atomic load验证。在读多写少的场景下这些额外的原子操作会显著增加读路径的开销。Epoch-Based ReclamationEBR提供了一条不同的思路不保护具体的指针而是保护时间段。// 3-Epoch Based Reclamation 核心逻辑 std::atomicuint64_t global_epoch{0}; thread_local uint64_t local_epoch; thread_local bool in_critical_section false; void enter() { local_epoch global_epoch.load(std::memory_order_acquire); in_critical_section true; std::atomic_thread_fence(std::memory_order_seq_cst); } void leave() { in_critical_section false; } void try_advance() { uint64_t current global_epoch.load(); for (int t 0; t num_threads; t) { if (thread_in_cs[t] thread_epoch[t] current) { return; // 有线程还卡在旧 epoch } } if (global_epoch.compare_exchange_strong(current, current 1)) { free_all(retired_lists[(current - 2) % 3]); } }EBR 的核心思想是一个节点在 epoch E 被 retire只有当所有线程都至少经历了 E2即两个完整的 grace period 过去了之后才能被安全释放。这保证了在节点被 retire 时还持有它引用的所有线程都已经完成了当前操作并离开了临界区。EBR vs Hazard Pointer工程选型EBR 的优势在于读路径的开销极低——进入和离开临界区各只需要一次写操作不需要像 Hazard Pointer 那样对每个读取的共享指针都做一次 atomic store 验证。在读多写少的场景中EBR 的性能通常比 Hazard Pointer 好 20-40%。但 EBR 有一个致命的弱点如果某个线程长时间不离开临界区比如被调度出去了整个系统的内存回收都会停滞。因为 epoch 无法推进——只要有一个线程还卡在旧 epoch所有在新 epoch 中 retire 的节点都不能被释放。来看一个具体场景64 个线程操作一个 lock-free queue每秒 retire 200 万个节点。某个线程在enter()之后被 OS 调度出去了 100ms在高负载下完全可能发生——Linux CFS 在 64 线程争抢时一个线程被抢占后可能等 100ms 才被重新调度。在这 100ms 内其他 63 个线程 retire 了 20 万个节点但一个都不能释放——因为 epoch 无法推进。如果每个节点 64 字节这是 12.5 MB 的内存突增。维度Hazard PointerEpoch-Based Reclamation读路径开销每个指针 1 store 1 load整个操作只需 enter/leave内存上界确定性有界O(N²K)无界受最慢线程影响实现复杂度中等protect-then-validate 易错低enter/leave/retire适合场景实时系统、内存受限、线程可能被长时间抢占读多写少、线程调度及时C 标准C26std::hazard_pointer无标准支持2025 年的新进展C26 std::hazard_pointerHazard Pointer 从 2004 年被提出到 2024 年被纳入 C26 标准P2530R3Maged Michael 本人参与走了整整 20 年。标准化的接口封装了最容易出错的部分// C26 std::hazard_pointer 使用示例 #include hazard_pointer struct Node : std::hazard_pointer_obj_baseNode { std::atomicNode* next; int data; }; void dequeue(std::atomicNode* Head) { std::hazard_pointer hp std::make_hazard_pointer(); while (true) { Node* head hp.protect(Head); // 原子地 load protect validate if (!head) return; Node* next head-next.load(); if (Head.compare_exchange_weak(head, next)) { hp.reset_protection(); head-retire(); return; } } }hp.protect(atomic_ref)把load store hazard pointer validate三步封装成了一个操作消除了顺序写错的风险——你不可能把 protect 和 validate 拆开再搞错顺序了。这一个 API 设计决策就能预防 80% 的 Hazard Pointer 使用错误。2025 年还有一个值得关注的新方向Cyclic Memory Protection (CMP)由 DISC 2024 论文提出核心思想是完全不需要线程间协调——每个线程独立维护一个本地的保护周期初步性能数据显示在高争用场景下比 Hazard Pointer 快 1.72-4 倍。但这个方案还太新没有经过大规模生产验证目前不建议在生产环境中使用——等它有了 2-3 年的工业实践数据再考虑。工程选型决策树三条规则回到文章开头那个 coredump。现在你知道了崩溃的完整因果链1.无锁队列使用 free list 做节点回收没有配套内存回收方案2.高并发下 ABA 概率急剧上升节点被 free list 回收后立即被其他线程重用3.CAS 比较地址值相同就认为没人动过但语义已经变了4.更严重的是即使用了 tagged pointer 解决 CAS 层面的 ABAhead-next.load()仍然是 use-after-free——你读取了一个已经不属于当前队列的节点的 next 字段规则一lock-free 数据结构不允许在没有内存回收方案的情况下释放节点。永远不要delete一个刚从 lock-free 数据结构中逻辑删除的节点。要么永不释放适合短生命周期的程序或节点数有上界的场景要么用 Hazard Pointer / EBR / RCU。没有中间选项。规则二默认用 Hazard Pointer除非你有明确的理由用 EBR。Hazard Pointer 的确定性内存上界是一个极其重要的工程保障——在凌晨三点 OOM 的场景下你会感激当初选了一个有上界保证的方案。EBR 性能更好但只在所有线程都能及时推进 epoch的假设下成立——一旦某个线程被长时间调度出去这个假设就不成立了。规则三protect-then-validate 的顺序绝对不能写反。先hp.store(ptr)设置保护再load()验证 ptr 仍然有效。不是先验证再保护不是先使用再保护。如果你用的是 C26 的std::hazard_pointerhp.protect(atomic_ref)已经把这个顺序封装好了——但如果你在用自己实现的 Hazard Pointer 或者第三方库每次 protect 后必须跟一个 validate否则你的代码在 64 线程压测下一定会崩。回到那个 coredump。dequeue线程在head-next.load()处读取了一个已被释放的节点的 next 字段这个字段恰好存储着一个看起来像合法地址的值因为那块内存已经被另一次enqueue重新分配成了新节点新节点的 next 字段指向另一个有效节点。然后 CAS 用这个看起来合法的 next 值作为 desired 去修改 Head——成功了。从此刻起队列的链表结构指向了一个不属于当前队列的节点链后续操作沿着这条断裂的链走到了一个真正的非法地址SIGSEGV。如果当初用了 Hazard PointerT1 在读取 head 之前就设置了保护即使其他线程 retire 了 headscan 也会看到 T1 的 hazard pointer 而跳过释放。T1 的head-next.load()永远指向一块有效的内存——即使这个节点已经从队列中被逻辑删除了它的物理内存仍然有效T1 最终会在 validate 阶段发现 head 已经变了然后安全地重试。不会崩溃不会 use-after-free不会有凌晨三点的告警。Lock-free 编程从来不是把锁去掉换成 CAS那么简单。CAS 解决的是互斥tagged pointer 解决的是 ABA 的识别但内存回收——什么时候一个节点真正死了、可以被安全地归还给 allocator——这个问题需要 Hazard Pointer 或 EBR 这样的专门机制来回答。无锁的自由是有代价的这个代价就是你必须自己管理每个节点的生死时序。