Why does std::atomic<T>::compare_exchange_* should not suffer from ABA issue?

Question

In some forums and books (i.e. C++ Concurrency in Action) there's a nice example of multi-producer/multi-consumer stack, and in pop implementations they usually do the following:

// head is an std::atomic<node*> variable
node *old_head = head.load();
while(old_head && !head.compare_exchange_weak(old_head, old_head->next));
...

Why would using a std::atomic<T>::compare_exchange_* prevent the ABA issue?
Let's say that:

• old_head->next gets resolved before the thread is pre-empted (just before compare_exchange_weak)
• then the BA scenario happens
• after the thread is resumed head == old_head is valid; in this case old_head->next wouldn't be resolved again, pointing to an invalid memory location
• the compare_exchange_weak would be executed, would pass, but the value old_head->next would still be the old one

ABA related issue would then happen.

I believe I'm missing something. What am I missing here?

Cheers

Answer 1

Yes, you would suffer from an ABA problem here.

Though, I think that wouldn't matter because the implementation you are referring to(listing 7.3 in CiA) is anyway invalid, it is leaking nodes.

If we have a look at the most simple reference-counted implementation, the one using a lock-free std::shared_ptr(listing 7.9 in CiA) we see that the problem wouldn't happen. When using shared pointers, the old_head would not be deleted as our thread still holds a reference to it, as such a newly created head couldn't be created in the memory address of the old head.

There is also a thread on the official Concurrency in Action Manning forums about ABA problems in the stack implementation.