英文:
What happens if `compare_exchange_weak` is called on a dangling pointer? How is the code in my textbook safe?
问题
我觉得在这个《C++并发实战》中关于无锁栈的示例实现中可能存在悬空指针的问题。作者Anthony Williams提供了无锁栈类的初始实现如下：
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讨论了如何实现pop方法。他说，“push()在将节点添加到栈后不再触及该节点，因此调用pop()的线程必须是唯一能够访问该节点的线程，并且可以安全地删除它。” 要删除的节点最初添加到std::atomic<Node*> pending_deletion_head上，变量std::atomic<unsigned> threads_in_pop存储了正在访问pop的线程计数。只有当threads_in_pop为零时，从pending_deletion_head扩展的整个链才会被删除。
这在一般情况下对我来说是有道理的，但是我对push方法如何安全的部分感到困惑。具体来说，在while(!head.compare_exchange_weak(new_node->next, new_node));这一行中，根据pop的实现方式，new_node->next是否可能成为悬空指针呢？
英文:
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?
答案1
得分: 3
push 的实现是安全的，因为你只访问 new_node->next。new_node 始终是通过 new Node 局部创建的，因此不会成为悬空指针。下面这个语句：
while (!head.compare_exchange_weak(new_node->next, new_node)) {}
实际上在执行以下操作：
while(true) {
// 事务内存 TS 中的语法
atomic_noexcept {
// 在这里使用 -> 是安全的，因为到此为止，
// new_node 一直是一个非空指针
if (head == new_node->next) {
// 在此之后，new_node->next 可能会变成悬空指针，但我们不关心
// 并从函数返回
head = new_node;
break;
}
else {
new_node->next = head;
continue;
}
}
}
访问 new_node->next 一直是安全的，因为 new_node 是之前创建的新节点。
在循环期间，new_node->next 可能会被替换为 head，从而使其成为无效指针，但 new_node 本身永远不会成为悬空指针，这是安全的。
英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论