Preempted in the middle of a pop
pop() and push() implement a lock-free stack using CAS on a raw Node* head. Consider this interleaving: Thread 1 calls pop(), reads old_head = A (with A->next == B), then is preempted right before its compare_exchange_weak runs. Meanwhile Thread 2 fully executes: pop() twice (removing A, then B, so head becomes nullptr), frees node A, allocates a brand-new node that the allocator happens to place at A's old address (call it A again), and pushes it, followed by pushing some other node C, then pushing the original A address again so that head == A once more (but now A->next == C, not B). Thread 1 now resumes and executes its compare_exchange_weak(old_head, old_head->next, ...) where old_head is still the address A and old_head->next is still the stale value B. What happens, and what is this failure mode called?
#include <atomic>
struct Node { int value; Node* next; };
std::atomic<Node*> head{nullptr};
Node* pop() {
Node* old_head = head.load(std::memory_order_acquire);
while (old_head &&
!head.compare_exchange_weak(
old_head, old_head->next,
std::memory_order_acq_rel,
std::memory_order_acquire)) {
// old_head reloaded with the current head on failure; retry
}
return old_head;
}
void push(Node* n) {
n->next = head.load(std::memory_order_relaxed);
while (!head.compare_exchange_weak(
n->next, n,
std::memory_order_release,
std::memory_order_relaxed)) {}
}