Why you can't free the node retrieved from the atomic compare_exchange_weak in pop() in lock_free_stack?

user_6223420 0
Viewed 77

I'm reading the book <c++ concurrency in action 2nd. Ed> by Anthony Williams Section 7.2.2 Stopping those pesky leaks: managing memory in lock-free data strcutures.

before this section, we implemented a lock_free_stack

template <typename T> class lock_free_stack {
private:
  struct node {
    std::shared_ptr<T> data;
    node *next;
    node(T const &data_) : data(std::make_shared<T>(data_)) {}
  };
  std::atomic<node *> head;

public:
  void push(T const &data) {
    node *const new_node = new node(data);
    new_node->next = head.load();
    while (!head.compare_exchange_weak(new_node->next, new_node));
  }
  std::shared_ptr<T> pop() {
    node *old_head = head.load();
    while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
    return old_head ? old_head->data : std::shared_ptr<T>();
  }
};

in section 7.2.2, anthony said:

When you first looked at pop(), you 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 about to dereference.

I don't understand, if two threads calling pop() concurrently, each thread will get different head, so old_head of each thread differes from each other, and they are free to delete old_head.

In my opinion, the no-memory-leaks pop() would be:

  std::shared_ptr<T> pop() {
    node *old_head = head.load();
    while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
    std::shared_ptr<T> res = old_head ? old_head->data : std::shared_ptr<T>();
    delete old_head;
    return res;
  }

How to understand what anthony says ?

stdatomic c++17 concurrency multithreading c++
2 Answers

The race is here

  while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
                                                           ^^^^^^^^^^^^^^

One possible race is:

  1. Thread 1 calls head.load(), retrieving a node at address X
  2. Thread 2 calls head.load(), retrieving a node at address X
  3. Thread 2 does the exchange
  4. Thread 2 performs its own operations on old_head
  5. Thread 2 deletes node at address X
  6. Thread 1 attempts to read old_head->next, which has been deleted, just prior to its own call to compare_exchange_weak
user_8622310

Lets assume 2 threads enter pop at the same time but thread 2 gets interrupted for a bit like this:

Thread 1                                 Thread 2
node *old_head = head.load();            node *old_head = head.load();
while (old_head &&
   !head.compare_exchange_weak(old_head,
                       old_head->next));
std::shared_ptr<T> res =
     old_head ? old_head->data
              : std::shared_ptr<T>();
delete old_head;
                                         while (old_head &&
                                            !head.compare_exchange_weak(old_head,
                                                                old_head->next));

Both threads start with the same old_head = head.load();. Then thread 1 deletes the object and after that thread 2 accesses old_head->next. That's access after free.

user_42623440
Related