Skip to content
QuantReadySign In
#1795hardC++ & Systems

A Lock-Free Stack Under Preemption

Consider this Treiber lock-free stack (assume C++17, x86-64, and a general-purpose heap allocator):

#include <atomic>

struct Node {
    int   value;
    Node* next;
};

std::atomic<Node*> head{nullptr};

void push(int v) {
    Node* n = new Node{v, head.load(std::memory_order_relaxed)};
    while (!head.compare_exchange_weak(n->next, n,
                                       std::memory_order_release,
                                       std::memory_order_relaxed)) {
    }
}

bool pop(int& out) {
    Node* old = head.load(std::memory_order_acquire);
    while (old != nullptr) {
        Node* next = old->next;                              // (1)
        if (head.compare_exchange_weak(old, next,
                                       std::memory_order_acquire,
                                       std::memory_order_acquire)) {   // (2)
            out = old->value;
            delete old;                                      // (3)
            return true;
        }
    }
    return false;
}

The stack initially contains two nodes: head points to node A, A->next points to node B, and B->next is nullptr. Two threads then interleave as follows:

  1. T1 calls pop(), loads old == A, executes line (1) so next == B, and is preempted just before the CAS at (2).
  2. T2 calls pop(), which returns A's value and deletes A.
  3. T2 calls pop() again, which returns B's value and deletes B. head is now nullptr.
  4. T2 calls push(42). The allocator happens to return the block that A occupied, so the new node is constructed at the exact address A had. (Same-size blocks are recycled quickly by general-purpose allocators, so such reuse is common.)
  5. T1 resumes and executes the CAS at (2).

Which statement correctly describes what happens at step 5, and the standard remedy?

Loading interactive editor…