Why does deleting nodes in this stacked stack class cause a race condition?

Anthony Williams, Section 7.2.1, lists the stack lock implementation in a book called "C ++ Concurrency in Action":

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 chose a node leak to avoid a race condition where one thread deletes a node while the other thread still contains a pointer to it, something like dereferencing. "

1) I do not understand why such a scenario can occur and why the following pop () function will cause a 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 is it that for several threads that call pop () at the same time, the variable "old_head" can point to the same node object after line (3)?

+4
1

1 (2). head_->next. head_ , .

2 . head_ , head_.

1 . , ->next, head_. 2 , head_, .

+8

Source: https://habr.com/ru/post/1654847/


All Articles