Hard
Treiber stack pop with a tagged pointer and double-width CAS
Replaying the earlier Treiber-stack ABA scenario: Thread 1 reads head as {A, tag=5}, then is preempted before its CAS. While preempted, Thread 2 pops A (tag becomes 6), pops B (tag becomes 7), then pushes a freshly allocated node that happens to reuse A's old address as the new head (tag becomes 8, so head is now {A, tag=8}). Thread 1 resumes and executes compare_exchange_weak(expected={A,tag=5}, desired={B,tag=6}). What happens now?
main.cpp
struct TaggedPtr { Node* ptr; uint64_t tag; };
std::atomic<TaggedPtr> head; // assumes a lock-free double-width CAS is available
Node* pop() {
TaggedPtr oldHead = head.load();
TaggedPtr newHead;
do {
if (!oldHead.ptr) return nullptr;
newHead.ptr = oldHead.ptr->next;
newHead.tag = oldHead.tag + 1; // always advances, never reused
} while (!head.compare_exchange_weak(oldHead, newHead));
return oldHead.ptr;
}27 of 51 in Concurrency