I am trying to understand how more than one thread hold head pointer in pop(), If two threads hold head pointer at "node *old_head = head.load();" then the first thread will complete the loop by updating the head and at the end let's say we delete the old_head and Thread1 completes it's work, now Thread2 is still holding deleted old_head and it will enter the while loop and old_head and current head are not same, so it will go to else if condition and set "old_head = head;" and loop again and update the head and come out of loop and delete the old_head.

In the above process Thread2 never dereference the deleted node because it will come to else if condition if head and old_head are not same.

But as per the Author from C ConcurrencyInAction Book do we really need to check for other Threads holding the old_head ?

From C ConcurrencyInAction Book: The basic problem is that you want to free a node, but you can’t do so until you’re sure there are no other threads that still hold pointers to it.

#include <memory>
#include <atomic>
using namespace std;

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)); 
        // background steps of compare_exchange_weak
        /*      if ((old_head != nullptr) && (head == old_head))
                {
                    try 
                    {
                        head = old_head->next;
                        return true; // loop ends
                    }
                    catch(exception &e)
                    {
                        return false; // loop forever, at the end if we are deleting old_head then we are deleting head, it makes Stack without head
                    }
                }
                else if ((old_head != nullptr) && (head != old_head))
                {
                    old_head = head;
                    return false;
                }
                else
                {
                    return false; // loop forever
                } */          
        return old_head ? old_head->data : std::shared_ptr<T>();
    } 
};

int main()
{
    return 0;
}

CodePudding user response：

In the above process Thread2 never dereference the deleted node because it will come to else if condition if head and old_head are not same.

This is not true. Consider this line:

head.compare_exchange_weak(old_head, old_head->next)

This will access the value of old_head->next before the compare_exchange_weak even runs. Which means if old_head is a dangling pointer you get Undefined Behavoir.

(Note that head will not equal old_head in this case and so the value of old_head->next will not be used but just accessing it before we know we'll not use it already causes the issue).

Additionally in your pseudocode for cew it seems you think that accessing old_head->next will throw an exception? This isn't true in c . Accesssing a bad pointer will immediately cause Undefined Behavoir which means all bets are off.