The Stale Next Pointer

A Treiber stack push:

struct Node { int value; Node* next; };
std::atomic<Node*> head{nullptr};

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

Single-threaded it is fine. With 8 threads pushing 100,000 values each, walking the finished stack finds far fewer than 800,000 nodes. Which change fixes it?

Make Node::next a std::atomic<Node*>.

Move n->next = old; inside the loop body so it is recomputed after every failed exchange.

Use compare_exchange_strong so the loop cannot fail spuriously.

Use std::memory_order_seq_cst for both the success and the failure ordering.