#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:
- T1 calls
pop(), loadsold == A, executes line (1) sonext == B, and is preempted just before the CAS at (2). - T2 calls
pop(), which returns A's value and deletes A. - T2 calls
pop()again, which returns B's value and deletes B.headis nownullptr. - 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.) - T1 resumes and executes the CAS at (2).
Which statement correctly describes what happens at step 5, and the standard remedy?
Loading interactive editor…