由于ABA问题，此危害指示器示例是否存在缺陷？ [英] Is this hazard pointer example flawed because of ABA issue?

问题描述

在 C ++并发操作中，作者举了一个使用危险指针实现无锁堆栈数据结构的示例。部分代码如下：

  std :: shared_ptr< T> pop（）
 {
 std :: atomic< void *>& hp = get_hazard_pointer_for_current_thread（）; 
节点* old_head = head.load（）; 
 node * temp; 
 do 
 {
 temp = old_head; 
 hp.store（old_head）; 
 old_head = head.load（）; 
} while（old_head！= temp）; 
 // ... 
} 
  

说明如下

您必须在 while 循环中执行此操作，以确保 head 指针与危险指针的
设置之间，尚未删除> node 。在此窗口中，没有其他线程
知道您正在访问该特定节点。幸运的是，如果要删除旧的
head 节点，则必须更改 head 本身， b $ b，这样您就可以检查并保持循环，直到您知道 head
指针仍然具有与危险指针相同的值。

我认为代码有缺陷，因为 head 节点受 ABA问题。即使 head 的值保持不变，它最初指向的节点也可能已被删除。分配了一个新的 head 节点，该节点恰好具有与上一个相同的地址值。

方案

默认 memory_order load（）操作的c $ c> 是 std :: memory_order_seq_cst ，可确保所有操作（总全局排序）：

每个 memory_order_seq_cst 操作<$ c $从原子变量
M 加载的c> B 观察到以下情况之一：

• 最后一次修改 M 的操作 A 的结果如果存在这样的 A B 之前


• OR $ c>， B 可能会观察到对 M 的某些修改结果，而不是 memory_order_seq_cst 而不是
  发生在 A


• OR之前，如果没有这样的 A ， B 可能会观察到对 M 的一些不相关的修改而不是的结果memory_order_seq_cst 。

因此，如果节点被修改（删除）并且在总的全局顺序中第二次读取之前发生这种情况，因此可以确保您看到更改，因此循环将继续执行。如果此命令是在以后订购的，则不会造成危害，因为已经设置了危险指针。

您具有此保证，因为存储到危险指针也使用 std :: memory_order_seq_cst 。此内存顺序为您提供了用于加载的 acquire 操作和用于存储的 release 操作，从而防止了在同一线程内重新排序。因此，成功读取（ old_head == temp ）保证保存了正确的数据。

处理这两个数据作为同步点加载-由于它们执行 acquire 操作，因此它们与修改这些值的相应 release 操作同步，从而使所有写入变为可见。

---

您所描述的问题不会以任何方式破坏示例。 pop（）函数用于删除top元素，并且它将完成此操作。同时，如果添加/删除了元素，则无论元素的地址是什么，它都会弹出它（它甚至可以与先前获取的地址相同）。这是一个完全不同的问题。考虑：

  concurrent_stack< int> ; 
 if（！p.empty（）&&（p.top（）== 5））
 {
 auto t = p.pop（）; 
 assert（t）; //可能失败
 assert（* t == 5）; //可能会失败
} 
  

这两个断言都可能失败，并且如果有很多线程使用堆栈非常密集地，很可能会经常失败。但这不是由于 pop（）的错误实现，而是事实，您需要更严格的访问限制以确保确实从堆栈中删除了最后一个检查的元素。 / p>

In the book C++ Concurrency in Action, the author gave an example of using hazard pointer to implement a lock-free stack data structure. Part of the code is as follows:

std::shared_ptr<T> pop()
{
    std::atomic<void*>& hp=get_hazard_pointer_for_current_thread();
    node* old_head=head.load();
    node* temp;
    do
    {
        temp=old_head;
        hp.store(old_head);
        old_head=head.load();
    } while(old_head!=temp);
    // ...
}

The description says that

You have to do this in a while loop to ensure that the node hasn’t been deleted between the reading of the old head pointer and the setting of the hazard pointer. During this window no other thread knows you’re accessing this particular node. Fortunately, if the old head node is going to be deleted, head itself must have changed, so you can check this and keep looping until you know that the head pointer still has the same value you set your hazard pointer to.

I think the code is flawed because the head node is subject to the ABA problem. Even if the value of head remains the same, the node it originally points to may have been deleted. A new head node is allocated, which happens to have the same address value as the previous one.

解决方案

The default memory_order for load() operations is std::memory_order_seq_cst, which ensures sequential consistency of all operations (total global ordering):

Each memory_order_seq_cst operation B that loads from atomic variable M, observes one of the following:

• the result of the last operation A that modified M, which appears before B in the single total order
• OR, if there was such an A, B may observe the result of some modification on M that is not memory_order_seq_cst and does not happen-before A
• OR, if there wasn't such an A, B may observe the result of some unrelated modification of M that is not memory_order_seq_cst.

So, if the node is modified (deleted) and this happens before second read in the total global order, you are guaranteed to see that change and thus loop will continue to execute. If this modification is ordered after, there is no harm since hazard pointer has been already set.

You have this guarantee, because store to hazard pointer is also done with std::memory_order_seq_cst. This memory order gives you an acquire operation for loads and release operation for stores, preventing from reordering within the same thread. Thus, "successful" read (old_head==temp) guarantees that proper data was saved.

Treat these two loads as sync points - since they perform an acquire operation, they are synchronized-with respective release operations that modify those values, causing all writes to become visible.

---

The issue you described does not flaw the example in any way. pop() function is meant to remove top element and it will do it. If, in the meantime, element is added/removed, it will pop it, no matter what its address is (it may even be the same the one previously fetched). This is a totally different problem. Consider:

concurrent_stack<int> p;
if (!p.empty() && (p.top() == 5))
{
  auto t = p.pop();
  assert( t ); // May fail
  assert( *t == 5 ); // May fail
}

Both assertions may fail and in case many threads use the stack very intensively, most likely will fail quite often. But this is not due to incorrect implementation of pop(), but the fact, that you need stronger access restriction to ensure that last checked element is indeed removed from the stack.

这篇关于由于ABA问题，此危害指示器示例是否存在缺陷？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！