Lock-free stack pop implementation in C++

Question

In C++ Concurrency in Action, 2e, The author describes a lock-free thread safe linked list implementation. Right now, he is describing the pop() method and how to safely delete the nodes in a sort of "garbage-collector" like method to make sure that no other threads called pop on the same instance. Here is some of that code for pop:

#include <atomic>
#include <memory>

template<typename T>
class lock_free_stack
{
private:
    std::atomic<unsigned> threads_in_pop;
    void try_reclaim(node* old_head);
public:
    std::shared_ptr<T> pop()
    {
        ++threads_in_pop;
        node* old_head=head.load();
        while(old_head &&
              !head.compare_exchange_weak(old_head,old_head->next));
        std::shared_ptr<T> res;
        if(old_head)
        {
            res.swap(old_head->data);
        }
        try_reclaim(old_head);
        return res;
    }
};

The important thing is that a counter is incremented atomically every time pop() is called. Then, the try_reclaim function will decrement said counter. Here is try_reclaim's implementation:

void try_reclaim(node* old_head)
{
    if(threads_in_pop==1) //#1
    {
        node* nodes_to_delete=to_be_deleted.exchange(nullptr);
        if(!--threads_in_pop) //#2
        {
            delete_nodes(nodes_to_delete);
        }
        else if(nodes_to_delete)
        {
            chain_pending_nodes(nodes_to_delete);//#3
        }
        delete old_head; //#4 THIS IS THE PART I AM CONFUSED ABOUT
    }
    else
    {
        chain_pending_node(old_head);
        --threads_in_pop;
    }
}

The implementations of the other functions called here are irrelevant (they just add nodes to a chain of nodes to be deleted), so I have omitted them. The part I am confused about in the code is #4 (marked). Here, the author calls delete on the old_head that was passed in. However, why doesn't he check to see if threads_in_pop is still zero at this point before deleting old_head? He double checks in lines #2 and #1 to make sure another thread isn't currently in pop(), so why doesn't he check again before proceeding to delete old_head? Couldn't another thread have possibly called pop() right after #3, thus incrementing the counter, and by the time the first thread reaches #4, then threads_in_pop would no longer be zero?

That is to say, couldn't it be possible that threads_in_pop is, for example, 2, by the time the code reaches #4? How could he safely delete old_head in that case? Could someone explain please?

Answer 1

The thread that calls try_reclaim has just removed old_head from the stack.

The class ensures that any other uses of old_head must be inside pop calls from other threads, so if the thread discovers that there are no other concurrent calls, then it knows that it is the exclusive holder of the old_head pointer. Then, as long as it doesn't publish that pointer so that it might be picked up from another thread, it can delete it whenever it gets around to it.

So the implementation is safe. The question you asked: "Why doesn't he check [again]" indicates that you are thinking about it incorrectly. Checking again wouldn't prove anything, because if it were possible for another thread to get into pop and use old_head, then it could always happen after you check!