Benji Mizrahi Benji Mizrahi - 2 months ago 15
C++ Question

Why would 'deleting' nodes in this lock-free stack class would cause race condition?

In the book titled "C++ Concurrency in Action" by Anthony Williams, in Section 7.2.1, a lock-free stack implementation is listed:

template <typename T>
class lock_free_stack {
struct node {
shared_ptr<T> data_;
node* next_;
node(const T& data) : data_(make_shared(data)) {}
};
atomic<node*> head_;
public:
void push(const T& data)
{
node* new_node = new node(data);
new_node->next_ = head_.load();
while(!head.compare_exchange_weak(new_node->next_, new_node));
}
shared_ptr<T> pop()
{
node* old_head = head_.load();
while (old_head &&
!head_.compare_exchange_weak(old_head, head_->next_));
return old_head ? old_head->data_ : shared_ptr<T>();
}
};


Then in Section 7.2.2, the author says "... at pop(), we opted to leak nodes in order to avoid the race condition where one thread deletes a node while another thread still holds a pointer to it that it's just about to dereference."

1) I don't understand why such a scenario might happen and why the following pop() function would cause race condition:

shared_ptr<T> pop()
{
node* old_head = head_.load(); // (1)
while (old_head &&
!head_.compare_exchange_weak(old_head, head_->next_)); // (2)
shared_ptr<T> res; // (3)
if (old_head) {
res.swap(old_head->data);
delete old_head;
return res;
} else {
return {};
}
}


2) How comes that for multiple threads that call pop() at the same time, 'old_head' variable can point to the same node object after line (3)?

Answer

Thread 1 proceeds to (2). It starts to evaluate head_->next. It loads head_ into a register, then gives up priority.

Thread 2 proceeds from the start to the end of the function. It removes head_ from existence by deleting it and returns the contents of head_.

Thread 1 wakes up. It follows head_ in a register getting the ->next field. But thread 2 has already deleted the data pointed to by head_, and we just followed a dangling pointer.