4

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)?

Benji Mizrahi
  • 2,154
  • 2
  • 23
  • 38

2 Answers2

8

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.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
  • Sorry, it is still not clear for me. Yes, thread 1 will follow not existent pointer and read value in "next" which probably already allocated for another variable. So, 2nd argument for compare_exchange_weak() will be invalid. But it will be never used, because when compare_exchange_weak() will be executed it will detect that "head_ != old_head". So, yes, we will read invalid argument for compare_exchange_weak() but it will be never used. What is the problem? Could you please clarify? – Alex Mar 29 '17 at 05:07
  • @alex why would you assume they are not equal? You followed a dangling pointer, the value can be *anything*. And where does it check `head_!=old_head_`? Did I miss it? – Yakk - Adam Nevraumont Mar 29 '17 at 11:31
  • Most probably I'm missing something, but I still can't understand what exactly. Check "head_!=old_head_" is inside compare_exchange_weak(). If those values are not equal, 2nd argument of compare_exchange_weak() will not be used. In my understanding compare_exchange_weak() atomically reads current value of head from memory. In discussed scenario after 1st thread wakes up, value of head in register will not be equal to current value of head in memory. So, compare_exchange_weak() will see it and will not use 2nd argument (garbage, that we read following invalid value of head in register). – Alex Mar 30 '17 at 03:48
  • @alex you mean `old_head` not `old_head_`? – Yakk - Adam Nevraumont Mar 30 '17 at 11:18
0

I had the same confusions reading that and tried to google the answer...I couldn't find an answer and finally went to check compare_exchange_weak reference. The part we were missing is the time you pass in second desired parameter, you're already dereferencing the dangling pointer... You can't really get away with that since the function needs to know what you're passing in, thus dereferencing it.

user11082152
  • 1