为何lock_free_stack的pop()不能直接释放compare_exchange_weak获取的节点

你正在阅读Anthony Williams所著的《C++ Concurrency in Action（第2版）》，学习到7.2.2节《解决恼人的泄漏问题：无锁数据结构的内存管理》。章节初始给出的存在节点泄漏的lock_free_stack实现如下：

template <typename T> class lock_free_stack {
private:
  struct node {
    std::shared_ptr<T> data;
    node *next;
    node(T const &data_) : data(std::make_shared<T>(data_)) {}
  };
  std::atomic<node *> head;

public:
  void push(T const &data) {
    node *const new_node = new node(data);
    new_node->next = head.load();
    while (!head.compare_exchange_weak(new_node->next, new_node));
  }
  std::shared_ptr<T> pop() {
    node *old_head = head.load();
    while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
    return old_head ? old_head->data : std::shared_ptr<T>();
  }
};

作者在该节提到：

初次查看pop()实现时，我们选择放任节点泄漏，是为了避免竞态条件：一个线程删除节点时，另一个线程仍持有该节点指针即将解引用。

自定义修改版本的问题 #

你提出疑问：如果两个线程并发调用pop()，每个线程会获取不同的头节点，各线程的old_head互不相同，理应可以安全删除old_head，因此给出了无内存泄漏的pop实现：

std::shared_ptr<T> pop() {
    node *old_head = head.load();
    while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
    std::shared_ptr<T> res = old_head ? old_head->data : std::shared_ptr<T>();
    delete old_head;
    return res;
  }

这个实现的核心漏洞是错误假设了不同线程持有的old_head一定互不相同，实际会触发典型的use-after-free未定义行为，具体触发流程为：

• 初始栈状态：head指向节点A，A->next指向节点B
• 线程1执行pop，通过head.load()拿到节点A的指针，还没来得及执行CAS操作就被操作系统切出调度
• 线程2同时执行pop，同样通过head.load()拿到节点A的指针，执行CAS成功将head更新为节点B，取出A存储的data指针后执行delete A，节点A对应的内存被回收
• 线程1恢复调度执行CAS：compare_exchange_weak执行时需要先读取old_head指向的next字段和原子变量head的当前值做比较，此时old_head指向的A已经被释放，对old_head->next的访问就是对已释放内存的非法访问，轻则读到随机垃圾值导致栈结构损坏，重则直接触发段错误导致程序崩溃。

这里要注意一个容易被忽略的细节：compare_exchange_weak除了原子的比较交换逻辑外，当比较发现原子变量当前值和传入的期望值不相等时，它会把原子变量的当前值写回你传入的期望值变量，整个过程中只要你传入的期望值指针（也就是old_head）指向的内存已经被其他线程释放，所有对该指针的解引用行为都是非法的。

你假设的“各线程old_head互不相同”只有在所有线程都成功完成CAS、拿到唯一的出栈节点所有权之后才成立，但在CAS循环的执行阶段，多个线程完全可能同时加载到同一个头节点指针，只要其中一个线程成功出栈后立刻删除节点，其他还在循环中持有该节点指针的线程，下一次CAS尝试时就会访问已释放内存，这就是作者提到初始版本放任节点泄漏的核心原因。

内容的提问来源于stack exchange，提问作者Aero