无锁编程的 ABA 问题实战解法

这是无锁编程中最隐蔽、最难调试的陷阱——比内存分配器更"邪门"，因为它在单线程下完全不存在，只有在多线程高并发下才会随机触发，导致数据损坏或程序崩溃。

1. ABA 问题的本质（硬件视角回顾）

我们之前讲过 ABA 问题的硬件根源，现在从实战角度重新审视：

// 场景：无锁栈的 pop 操作（有 ABA 漏洞）
std::atomic<Node*> head{nullptr};

bool pop(Node*& result) {
    Node* old_head = head.load(std::memory_order_acquire);
    Node* new_head;
    do {
        if (!old_head) return false;
        new_head = old_head->next;  // ← 读取 old_head 的 next
    } while (!head.compare_exchange_weak(old_head, new_head,
              std::memory_order_release, std::memory_order_relaxed));
    
    result = old_head;  // ← 此时 old_head 可能已经被其他线程释放！
    return true;
}

ABA 攻击时序：

[时刻 T1] 线程A 读取 head = 节点X (地址 0x1000)
[时刻 T2] 线程B 弹出节点X → head = 节点Y
[时刻 T3] 线程B 释放节点X（delete / free）
[时刻 T4] 线程B 分配新节点Z，恰好复用地址 0x1000
[时刻 T5] 线程B push 节点Z → head = 0x1000
[时刻 T6] 线程A 执行 CAS：当前 head (0x1000) == 期望值 (0x1000) → ✅ 成功！
          new_head = old_head->next = 0x1000->next (此时是节点Z的next)
          head = new_head（可能是垃圾地址）

结果：head 指向了完全无关的地址，数据结构被破坏。

2. 工业级解法 1：带标签的指针（Tagged Pointer）

这是 最常用、最优雅 的解法。原理是：把版本号和指针打包成一个原子变量，CAS 时同时比较指针和版本号。

实现原理

在 64 位系统上，指针的有效位只有低 48 位（高 16 位为 0 或 FFF…）。我们可以利用高 16 位存储版本号。

// 打包：指针 + 版本号
struct TaggedPtr {
    uint64_t raw;  // 64位原子操作
    
    static constexpr uint64_t PTR_MASK = (1ULL << 48) - 1;
    static constexpr uint64_t TAG_SHIFT = 48;
    
    // 从原始值中提取指针
    void* ptr() const {
        return reinterpret_cast<void*>(raw & PTR_MASK);
    }
    
    // 提取版本号
    uint64_t tag() const {
        return raw >> TAG_SHIFT;
    }
    
    // 构造新的 TaggedPtr（指针不变，版本号+1）
    TaggedPtr next() const {
        return TaggedPtr{ptr(), tag() + 1};
    }
    
    // 直接从指针构造（版本号=0）
    TaggedPtr(void* p) : raw(reinterpret_cast<uint64_t>(p) & PTR_MASK) {}
    
    TaggedPtr(void* p, uint64_t t) 
        : raw((reinterpret_cast<uint64_t>(p) & PTR_MASK) | (t << TAG_SHIFT)) {}
};

// 使用 TaggedPtr 改造无锁栈
std::atomic<TaggedPtr> head{nullptr};

bool pop(Node*& result) {
    TaggedPtr old_head = head.load(std::memory_order_acquire);
    TaggedPtr new_head;
    do {
        if (!old_head.ptr()) return false;
        Node* old_node = static_cast<Node*>(old_head.ptr());
        new_head = TaggedPtr(old_node->next, old_head.tag() + 1);
    } while (!head.compare_exchange_weak(old_head, new_head,
              std::memory_order_release, std::memory_order_relaxed));
    
    result = static_cast<Node*>(old_head.ptr());
    return true;
}

void push(Node* node) {
    TaggedPtr old_head = head.load(std::memory_order_acquire);
    TaggedPtr new_head;
    do {
        node->next = static_cast<Node*>(old_head.ptr());
        // 版本号+1：即使地址相同，版本号变了，CAS 会失败
        new_head = TaggedPtr(node, old_head.tag() + 1);
    } while (!head.compare_exchange_weak(old_head, new_head,
              std::memory_order_release, std::memory_order_relaxed));
}

为什么这能解决 ABA？

[时刻 T1] 线程A 读取 head = {ptr: 0x1000, tag: 5}
[时刻 T2] 线程B 弹出节点X → head = {ptr: 0x2000, tag: 6}
[时刻 T3] 线程B push 节点Z (地址 0x1000) → head = {ptr: 0x1000, tag: 7}
                                    ← 注意 tag 从 5 变成了 7！
[时刻 T6] 线程A 执行 CAS：期望 {ptr: 0x1000, tag: 5}
          当前 head = {ptr: 0x1000, tag: 7}
          → 比较失败！ABA 被成功检测到！

3. 工业级解法 2：使用 128 位 CAS（`cmpxchg16b`）

如果 16 位版本号不够用（高并发下可能溢出），可以使用 128 位原子操作：

// 使用 64 位指针 + 64 位版本号（共 128 位）
struct AlignedTaggedPtr {
    void* ptr;      // 8 字节
    uint64_t tag;   // 8 字节，永不溢出
};

// x86-64 上使用 cmpxchg16b 实现 128 位原子 CAS
// 编译器支持：__int128 或 std::atomic<AlignedTaggedPtr>（需对齐到16字节）

std::atomic<AlignedTaggedPtr> head;

// 注意：需要结构体对齐到 16 字节
struct alignas(16) TaggedPtr128 {
    void* ptr;
    uint64_t tag;
};
static_assert(sizeof(TaggedPtr128) == 16);
static_assert(alignof(TaggedPtr128) == 16);

硬件代价：

cmpxchg16b 比普通 64 位 CAS 慢约 2~3 倍。
在 ARM 上，128 位原子操作由 LL/SC 循环实现，代价更高。

4. 工业级解法 3：不使用 `delete`，用 Hazard Pointer / RCU 延迟释放

如果根本不允许内存被复用，ABA 自然无法触发。

Hazard Pointer 的额外防护：

即使内存地址被复用，Hazard Pointer 会保护旧节点，直到所有引用都释放。
内存复用时，旧节点还在保护中 → 不会被复用 → 地址不会变回原值。

// Hazard Pointer 版本的 pop（无需 Tagged Pointer）
bool pop_with_hp(Node*& result) {
    int slot = 0;
    Node* old_head;
    Node* new_head;
    
    while (true) {
        old_head = static_cast<Node*>(hazard_pointer.protect(slot, head));
        if (!old_head) return false;
        
        new_head = old_head->next;  // 此时 old_head 被保护，不会被释放
        
        if (head.compare_exchange_weak(old_head, new_head,
                                       std::memory_order_acquire,
                                       std::memory_order_relaxed)) {
            result = old_head;
            hazard_pointer.retire(old_head);  // 延迟删除
            hazard_pointer.clear(slot);
            return true;
        }
        hazard_pointer.clear(slot);
    }
}

注意：Hazard Pointer 本身不解决 ABA（地址可能变回原值），但它保证旧节点不会被复用，所以即使地址变回原值，节点内容依然是原来的内容（未被修改）。

5. 三种方案的对比与选型

方案	实现复杂度	性能开销	保护范围	适用场景
Tagged Pointer (16位)	低	极低 (一次 CAS)	版本号有限（65536 次复用）	绝大多数场景
128 位 CAS (64位Tag)	中	中等 (2~3x CAS)	几乎无限	高并发、tag 可能溢出的场景
Hazard Pointer	高	中等 (需额外清理)	完全防止内存复用	已有 HP 实现的系统
RCU	高	读操作零开销	完全防止内存复用	读多写少场景

6. 笔记存档：ABA 问题核心概念速查

概念	解释
ABA 问题	CAS 只比较值是否相等，无法区分"从未改变"和"改变后又变回来"的场景。
常见触发场景	无锁栈/队列 + 内存复用（`new`/`delete` 或 `malloc`/`free` 返回相同地址）。
Tagged Pointer	利用 64 位地址的高 16 位存储版本号，CAS 同时比较指针和版本号。
128 位 CAS	使用 `cmpxchg16b` 或 `std::atomic<16字节结构体>` 存储 64 位指针 + 64 位 tag。
Hazard Pointer / RCU	延迟释放内存，从根本上阻止内存复用。
适用场景	任何使用 CAS 的无锁数据结构（栈、队列、链表、哈希表）。

本节关键词：ABA、Tagged Pointer、版本号、128位CAS、Hazard Pointer、内存复用。 与前期知识的关联：

CAS 指令（cmpxchg / LL/SC）是 ABA 的触发基础。

内存分配器（jemalloc/tcmalloc）复用内存地址的频率更高 → ABA 更易触发。

Hazard Pointer / RCU（之前笔记）是 ABA 的根治方案。

1. ABA 问题的本质（硬件视角回顾）#

2. 工业级解法 1：带标签的指针（Tagged Pointer）#

实现原理#

3. 工业级解法 2：使用 128 位 CAS（cmpxchg16b）#

4. 工业级解法 3：不使用 delete，用 Hazard Pointer / RCU 延迟释放#

5. 三种方案的对比与选型#

6. 笔记存档：ABA 问题核心概念速查#