Lockfree Stack with atomic


I need to build a lock-free stack implementation. I read this page and I understand the functionality of the listed lock-free push operation.

Now, I have to build a similar version of the pop operation. This is what I’ve done until now but I think, there are some concurrency problems:

node<T>* old_head = head.load(std::memory_order_relaxed);

if(old_head == nullptr) {
    return false;

// from here on we can assume that there is an element to pop
node<T>* new_head = old_head->next;

// if head still equals old_head this implies the same relation for new_head
while(!head.compare_exchange_weak(old_head, old_head->next, std::memory_order_release, std::memory_order_relaxed));

return true;

I think I also will get trouble if I delete old_head after the swap, right?


Yes, deletion is hard because other threads could still be reading it. RCU has the same problems, and and solves it by deferring deletion until all threads have passes a sync point. (IIRC, with a generation number or something, so you know which pool of old objects can be deleted now). Wikipedia has a diagram. en.wikipedia.org/wiki/Read-copy-update#Overview
You should put new_head = old_head->next; inside the CAS retry loop. Think about which variable compare_exchange_weak updates on failure.
Yes, you’re right! I’ll insert this into the loop. What if we ignore the deletes for a moment: Is it allowed to do old_head->next within compare_exchange_weak? Is this still atomic?
– lukasl1991
7 mins ago
What do you mean “within”? If you mean inside a do { new_head = old_head->next; } while(! CAS) loop, then yes, that’s what you should do. Any compare_exchange_weak that compiles is itself atomic, the only issue is whether the pointer you’re trying to replace head with is pointing to an object with the right contents. (And getting the rest of the logic right.) It’s possible to go wrong if your algorithm actually requires (for correctness) multiple updates (to different objects) to be an atomic transaction; i.e. if you designed it wrong. But that’s not the case here.
I thought about while(!head.compare_exchange_weak(old_head, old_head->next, std::memory_order_release, std::memory_order_relaxed)) { new_head = old_head->next; }
– lukasl1991
48 secs ago