Lock-free stack with reference counting

Question

From answers to my previous question: Pointers in c++ after delete

it's become clear, that using the values of pointers, that point to "deleted" memory (in particular, copying them) lead to undef behaviour in c++11, and implementation-defined behaviour in c++14.

Antomy Williams in his book "C++ concurrency in action" suggests the next lock-free stack with reference counting:

#include <atomic>
#include <memory>

template<typename T>
class lock_free_stack
{
private:
    struct node;
    struct counted_node_ptr
    {
        int external_count;
        node* ptr;
    };
    struct node
    {
        std::shared_ptr<T> data;
        std::atomic<int> internal_count;
        counted_node_ptr next;
        node(T const& data_):
            data(std::make_shared<T>(data_)),
            internal_count(0)
        {}
    };
    std::atomic<counted_node_ptr> head;
    void increase_head_count(counted_node_ptr& old_counter)
    {
        counted_node_ptr new_counter;
        do
        {
            new_counter=old_counter;
            ++new_counter.external_count;
        }
        while(!head.compare_exchange_strong(
                  old_counter,new_counter,
                  std::memory_order_acquire,
                  std::memory_order_relaxed));
        old_counter.external_count=new_counter.external_count;
    }
public:
    ~lock_free_stack()
    {
        while(pop());
    }
    void push(T const& data)
    {
        counted_node_ptr new_node;
        new_node.ptr=new node(data);
        new_node.external_count=1;
        new_node.ptr->next=head.load(std::memory_order_relaxed)
            while(!head.compare_exchange_weak(
                      new_node.ptr->next,new_node,
                      std::memory_order_release,
                      std::memory_order_relaxed));
    }
    std::shared_ptr<T> pop()
    {
        counted_node_ptr old_head=
            head.load(std::memory_order_relaxed);
        for(;;)
        {
            increase_head_count(old_head);
            node* const ptr=old_head.ptr;
            if(!ptr)
            {
                return std::shared_ptr<T>();
            }
            if(head.compare_exchange_strong(
                   old_head,ptr->next,std::memory_order_relaxed))
            {
                std::shared_ptr<T> res;
                res.swap(ptr->data);
                int const count_increase=old_head.external_count-2;
                if(ptr->internal_count.fetch_add(
                       count_increase,std::memory_order_release)==-count_increase)
                {
                    delete ptr;
                }
                return res;
            }
            else if(ptr->internal_count.fetch_add(
                        -1,std::memory_order_relaxed)==1)
            {
                ptr->internal_count.load(std::memory_order_acquire);
                delete ptr;
            }
        }
    }
};

I'm worried about function

void increase_head_count(counted_node_ptr& old_counter)
{
    counted_node_ptr new_counter;
    do
    {
        new_counter=old_counter;
        ++new_counter.external_count;
    }
    while(!head.compare_exchange_strong(
              old_counter,new_counter,
              std::memory_order_acquire,
              std::memory_order_relaxed));
    old_counter.external_count=new_counter.external_count;
}

It seems, that new_counter=old_counter; can be executed, when old_counter.ptr has been deleted by another thread.

So, could somebody confirm or refuse, that this stack implementation is strictly incorrect in c++11?

Neither `std::atomic` or `std::shared_ptr` need be lock free (implementation and type defined) so how is the whole class "lock free"? — Richard Critten, May 25 '17 at 17:49
@RichardCritten: The class also uses `new` and `delete`, which are almost certainly not lock-free. — Ben Voigt, May 25 '17 at 18:08
@RichardCritten Both can be; and often are, and I believe you can even ask the compiler if atomic is always lock free (uncertain about shared pointer). Writing code that is lock free if std atomic is lock free is a reasonable thing to do and describe as a "lock free data structure". — Yakk - Adam Nevraumont, May 25 '17 at 18:34

Cyril Gao · Answer 1 · 2019-06-20T23:21:56.570

I think that the implementation has other problem: Let us suppose that two threads are working on a non-empty lock free stack:

thread A calls push() to add a new node, after the line of code new_node.ptr->next=head.load(std::memory_order_relaxed); has been executed, thread A goes to sleep;
thread B calls pop() to remove an old node, after the line of code increase_head_count(old_head); has been executed, thread B goes into sleep;
thread A continues to run, and finds that the external reference count of the head node is not 1, but the information will be ignored, and the new node will be added to the stack as the new head;
thread B continues to run, and head.compare_exchange_strong() will be failed, and ptr->internal_count.fetch_add(-1, std::memory_order_relaxed) will be executed, it causes that the external reference count of the old head pointer is still 2, but the internal reference count is -1.
so the lock free stack is broken!

Who can help to check whether it is a real problem?

One trick for testing problems like this is to attach a debugger and single-step one thread while others run free, or while you also single-step another thread. You can manually create any order of execution that the C source allows that way. (At least for `memory_order_seq_cst` where you aren't depending on runtime reordering of a single thread's own stores/loads.) — Peter Cordes, Jun 21 '19 at 05:25
could you tell me how that 3. can be "... is not 1, but the information will be ignored" ? I think compare_exchange_weak will never update head if compare does not match — philsumuru, Aug 30 '19 at 02:47

score 0 · Answer 2 · answered May 25 '17 at 18:05

0

It is possible, but not problematic, because the compare_exchange call will detect it and discard new_counter.

answered May 25 '17 at 18:05

Ben Voigt

277,958
43
419
720

Lock-free stack with reference counting

2 Answers2