3. 无锁单链表（Lock-Free Singly Linked List）：插入、删除、查找的ABA问题与解决方案

无锁单链表是并发编程中基础且关键的数据结构。在DPDK等高性能网络场景中，多个核（lcore）同时操作同一个链表是常态。本章深入剖析无锁单链表的插入、删除、查找操作，重点攻克并发环境下最棘手的ABA问题，并给出工程级的解决方案。

3.1 无锁单链表的核心操作与CAS原语

无锁编程的核心依赖是比较并交换（Compare-And-Swap, CAS）原子操作。在x86架构上对应 CMPXCHG 指令，在DPDK中通常通过 rte_atomic32_cmpset() 或C11的 __atomic_compare_exchange_n 实现。

无锁单链表的基本节点结构如下：

struct lf_node {
    void *data;               // 用户数据指针
    struct lf_node *next;     // 下一个节点指针（原子操作）
};

3.1.1 插入操作（Insert）

在无锁链表中插入节点，通常采用头插法或指定位置插入。以头插法为例，其核心逻辑是：

1. 新节点 new_node 的 next 指向当前头节点 head。
2. 使用CAS将 head 原子地更新为 new_node。
3. 如果CAS失败（说明其他线程修改了 head），则重试步骤1。

void lf_list_push(struct lf_node **head, struct lf_node *new_node) {
    struct lf_node *old_head;
    do {
        old_head = *head;
        new_node->next = old_head;  // 步骤1
    } while (!rte_atomic32_cmpset((uint32_t *)head,
                                   (uint32_t)old_head,
                                   (uint32_t)new_node)); // 步骤2
}

3.1.2 删除操作（Delete）

删除操作更为复杂。假设我们要删除节点 A，其前驱节点为 prev。直观的做法是：

1. 读取 prev->next，确认其指向 A。
2. 读取 A->next，得到 B。
3. 使用CAS将 prev->next 从 A 更新为 B。

然而，这个看似简单的流程隐藏着巨大的风险——ABA问题。

3.2 ABA问题的本质与危害

ABA问题是无锁数据结构中最经典、最隐蔽的并发陷阱。

在单链表的删除场景中，ABA问题的具体表现如下：

在t5时刻，T1的CAS认为 prev->next 仍然是 A（实际上地址相同，但内容已变），于是将其更新为 B，导致节点C和D从链表中丢失，造成内存泄漏或野指针。

3.3 ABA问题的解决方案

解决ABA问题的主流方案有三种：标记指针（Tagged Pointer）、双宽CAS（DCAS）和危险指针（Hazard Pointer）。在DPDK环境中，最常用的是标记指针方案。

3.3.1 方案一：标记指针（Tagged Pointer）

核心思想：在指针的高位或低位附加一个版本号/标记，每次修改指针时同时递增标记。即使地址被复用，标记不同也能被CAS检测到。

// 将指针和标记打包在一个uint64_t中（x86-64用户空间地址高16位空闲）
union tagged_ptr {
    struct {
        uint64_t ptr  : 48;  // 指针（48位虚拟地址）
        uint64_t tag  : 16;  // 标记（16位版本号）
    } fields;
    uint64_t raw;            // 用于CAS操作的完整64位值
};

struct lf_node_tagged {
    void *data;
    union tagged_ptr next;   // 原子操作next.raw
};

插入操作使用标记指针：

void lf_list_push_tagged(union tagged_ptr *head, struct lf_node_tagged *new_node) {
    union tagged_ptr old_head;
    do {
        old_head.raw = head->raw;  // 原子读取
        new_node->next.raw = old_head.raw;
        // 新节点的next标记继承旧头节点的标记（或置0）
    } while (!rte_atomic64_cmpset(&head->raw,
                                   old_head.raw,
                                   (uint64_t)(uintptr_t)new_node | (old_head.fields.tag + 1)));
    // 头节点标记+1，即使地址相同，标记不同也会导致CAS失败
}

3.3.2 方案二：双宽CAS（Double-Word CAS, DCAS）

某些架构（如x86的 CMPXCHG16B）支持对16字节（128位）进行原子CAS操作。可以将指针和标记作为两个独立的64位字段，一起进行CAS。

struct lf_node_dcas {
    void *data;
    struct lf_node_dcas *next;  // 8字节指针
    uint64_t tag;               // 8字节标记
} __attribute__((aligned(16))); // 16字节对齐

// 使用CMPXCHG16B原子更新 (next, tag) 对
// 伪代码：DCAS(&node->next, &node->tag, old_next, old_tag, new_next, new_tag)

3.3.3 方案三：危险指针（Hazard Pointer, HP）

危险指针是一种延迟回收机制，确保一个节点在被任何线程引用时不会被释放。每个线程维护一个危险指针列表，指向其当前正在访问的节点。在释放节点前，检查所有线程的危险指针列表。

3.4 查找操作与无锁遍历

无锁单链表的查找（Search）相对简单，因为查找是只读操作，不涉及CAS。但需要注意内存一致性问题：

struct lf_node *lf_list_search(struct lf_node *head, void *key,
                               int (*cmp)(void *, void *)) {
    struct lf_node *curr = head;
    while (curr != NULL) {
        // 使用原子加载确保读取到最新的next指针
        if (cmp(curr->data, key) == 0) {
            return curr;
        }
        // 使用rte_smp_rmb()或atomic_load确保可见性
        curr = (struct lf_node *)rte_atomic32_read((uint32_t *)&curr->next);
    }
    return NULL;
}

3.5 工程选型对比

在DPDK项目中，选择哪种ABA解决方案取决于具体场景：

3.6 实践建议与避坑指南

• 优先使用标记指针： 在DPDK中，标记指针方案在性能和实现复杂度之间取得了最佳平衡。DPDK的 rte_ring 和 rte_hash 内部也采用了类似思想。
• 注意内存序（Memory Order）： 无锁操作必须配合适当的内存屏障。在DPDK中，rte_atomic32_cmpset 默认提供完整的内存屏障（相当于 memory_order_seq_cst），在性能敏感路径上可考虑使用 rte_atomic32_cmpset_relaxed 配合显式屏障。
• 避免在删除后立即释放内存： 即使使用标记指针，也建议将删除的节点放入一个待回收列表，延迟一个宽限期（Grace Period）后再释放。DPDK的 rte_rcu_qsbr 库提供了现成的RCU机制。
• 测试覆盖ABA场景： 编写单元测试时，构造多线程交替插入/删除同一地址的场景，使用压力测试工具（如 rte_test）验证ABA防护的有效性。