What happens if `compare_exchange_weak` is called on a dangling pointer? How is the code in my textbook safe?

Question

I feel like there could about the a dangling pointer in this example implementation of a lock-free stack in C++: Concurrency in Action. The author, Anthony Williams, provides a beginning for the lock-free stack class as:

class LockFreeStack {
  private:
    struct Node {
        T data;
        Node* next;

        Node(T const& data_) : data(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));
    }
};

Williams then discusses how to implement pop. He says, "push() doesn’t touch the node once it’s been added to the stack, so the thread that called pop() must be the only thread that can touch the node, and it can safely delete it." Nodes to delete are initially added on to a std::atomic<Node*> pending_deletion_head, and a variable std::atomic<unsigned> threads_in_pop stores the count of threads that are accessing pop. The entire chain extending from pending_deletion_head is finally deleted when threads_in_pop is zero.

This makes sense to me in general, but I'm confused about how push is safe. Specifically, couldn't new_node->next in the line while(!head.compare_exchange_weak(new_node->next, new_node)); be a dangling pointer with the given implementation of pop?

Answer 1

The implementation of push is safe because you only access new_node->next. new_node is always locally created with new Node, so it cannot be a dangling pointer. The statement:

while (!head.compare_exchange_weak(new_node->next, new_node)) {}

... is effectively doing:

while(true) {
    // syntax from transactional memory TS
    atomic_noexcept {
        // using -> is safe here because up to this point,
        // new_node is always a not-null pointer
        if (head == new_node->next) {
            // new_node->next may be dangling after this, but we don't care
            // and return from the function
            head = new_node;
            break;
        }
        else {
            new_node->next = head;
            continue;
        }
    }
}

Accessing new_node->next is always safe because new_node is the new node you've created earlier. new_node->next might be replaced with head during the loop, which makes it an invalid pointer, but new_node itself is never dangling, which makes this okay.