CODEWITHSUNDEEP
c++multithreadingc++11c++14
Oleksii Hamov
Oleksii Hamov

Reputation: 166

Non-blocking thread-safe stack

Recently I've being reading Anthony Williams - C++ Concurrency in action and I get to the chapter where the author suggest non-blocking thread-safe stack implementation. In the first implementation of pop() it is said that the method is not thread-safe. The question is why it is not thread-safe? In another words - could anybody point me out where data race is?

#include <memory>
#include <thread>
#include <iostream>
#include <atomic>

using namespace std;

template <class T>
class lock_free_stack
{
  private:
    struct Node
    {
        std::shared_ptr<T> data_;
        Node *next;


        Node(const T& data): data_(std::make_shared<T>(data)) 
        {
        }

    };
    std::atomic<Node *> head;


    public:
    lock_free_stack() { head.store(nullptr); }

    void push(T const& data)  
    {
        Node* const newNode = new Node(data);
        newNode->next = head.load();
        while(!head.compare_exchange_weak(newNode->next, newNode));
    }

    // The following function is not thread-safe
    std::shared_ptr<T> pop()
    {
        Node* old_head = head.load();

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

        unique_ptr<Node> deleter;
        if(old_head)
            deleter.reset(old_head);

        return old_head ? old_head->data_ : std::shared_ptr<T>();
    }

};

Upvotes: 1

Views: 183

Answers (1)

MikeMB
MikeMB

Reputation: 21166

The race condition is that one thread could evaluate old_head->next, just when (or after) your unique_ptr's destructor is called that deletes the node old_head points to.

Upvotes: 3

Related Questions