c++ - 如何避免或抑制此无锁堆栈中的竞争？

Question

我正在使用无锁堆栈(通过标记指针)来管理一个小块内存池。当 block 插入池中和从池中删除时，列表节点就地创建和销毁。

这是一个非常简化的测试程序，它只从堆栈中弹出。因此，没有 ABA 问题，也没有标记指针。足以证明我正在参加的比赛:

#include <atomic>
#include <list>
#include <thread>
#include <type_traits>

struct Node {
  Node() = default;
  Node(Node *n) { next.store(n); }
  std::atomic<Node *> next;
};

using Memory = std::aligned_storage_t<sizeof(Node)>;

struct Stack {
  bool pop_and_use() {
    for (Node *current_head = head.load(); current_head;) {
      Node *next = current_head->next.load(); // READ RACE
      if (head.compare_exchange_weak(current_head, next, std::memory_order_seq_cst)) {
        current_head->~Node();
        Memory *mem = reinterpret_cast<Memory *>(current_head);
        new (mem) int{0}; // use memory with non-atomic write (WRITE RACE)
        return true;
      }
    }
    return false;
  }
  void populate(Memory *mem, int count) {
    for (int i = 0; i < count; ++i) {
      head = new (mem + i) Node(head.load());
    }
  }
  std::atomic<Node *> head{};
};

int main() {
  Memory storage[10000];
  Stack test_list;
  test_list.populate(storage, 10000);
  std::thread worker([&test_list]() {
    while (test_list.pop_and_use()) {
    };
  });
  while (test_list.pop_and_use()) {};
  worker.join();
  return 0;
}

Thread sanitizer 报告以下错误:

clang++-10 -fsanitize=thread tsan_test_2.cpp -o tsan_test_2 -O2 -g2 -Wall -Wextra && ./tsan_test_2
LLVMSymbolizer: error reading file: No such file or directory
==================
WARNING: ThreadSanitizer: data race (pid=35998)
  Atomic read of size 8 at 0x7fff48bd57b0 by thread T1:
    #0 __tsan_atomic64_load <null> (tsan_test_2+0x46d88e)
    #1 std::__atomic_base<Node*>::load(std::memory_order) const /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/atomic_base.h:713:9 (tsan_test_2+0x4b3e6c)
    #2 std::atomic<Node*>::load(std::memory_order) const /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/atomic:452:21 (tsan_test_2+0x4b3e6c)
    #3 Stack::pop_and_use() /home/BOSDYN/akhripin/tmp/tsan_test_2.cpp:17:39 (tsan_test_2+0x4b3e6c)
    #4 main::$_0::operator()() const /home/BOSDYN/akhripin/tmp/tsan_test_2.cpp:40:22 (tsan_test_2+0x4b3e6c)
    #5 void std::__invoke_impl<void, main::$_0>(std::__invoke_other, main::$_0&&) /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/invoke.h:60:14 (tsan_test_2+0x4b3e6c)
    #6 std::__invoke_result<main::$_0>::type std::__invoke<main::$_0>(main::$_0&&) /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/invoke.h:95:14 (tsan_test_2+0x4b3e6c)
    #7 decltype(std::__invoke(_S_declval<0ul>())) std::thread::_Invoker<std::tuple<main::$_0> >::_M_invoke<0ul>(std::_Index_tuple<0ul>) /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/thread:244:13 (tsan_test_2+0x4b3e6c)
    #8 std::thread::_Invoker<std::tuple<main::$_0> >::operator()() /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/thread:253:11 (tsan_test_2+0x4b3e6c)
    #9 std::thread::_State_impl<std::thread::_Invoker<std::tuple<main::$_0> > >::_M_run() /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/thread:196:13 (tsan_test_2+0x4b3e6c)
    #10 <null> <null> (libstdc++.so.6+0xbd6de)

  Previous write of size 4 at 0x7fff48bd57b0 by main thread:
    #0 Stack::pop_and_use() /home/BOSDYN/akhripin/tmp/tsan_test_2.cpp:21:9 (tsan_test_2+0x4b3d5d)
    #1 main /home/BOSDYN/akhripin/tmp/tsan_test_2.cpp:43:20 (tsan_test_2+0x4b3d5d)

  Location is stack of main thread.

  Location is global '??' at 0x7fff48bad000 ([stack]+0x0000000287b0)

  Thread T1 (tid=36000, running) created by main thread at:
    #0 pthread_create <null> (tsan_test_2+0x4246bb)
    #1 std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State> >, void (*)()) <null> (libstdc++.so.6+0xbd994)
    #2 __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:310 (libc.so.6+0x21b96)

SUMMARY: ThreadSanitizer: data race (/home/BOSDYN/akhripin/tmp/tsan_test_2+0x46d88e) in __tsan_atomic64_load
==================
ThreadSanitizer: reported 1 warnings

当两个线程读取 current_head 的相同值时，就会出现问题。 , 但其中一个在另一个有机会读取 current_head->next 之前完成了弹出并覆盖了节点.

这类似于这里讨论的问题: Why would 'deleting' nodes in this lock-free stack class would cause race condition?除了内存实际上没有被释放。

我知道从机器的角度来看，这种竞争是良性的——如果发生读取竞争，比较和交换将不会成功——但我认为这仍然进入了 C++ 中未定义的行为领域。

有没有办法在没有竞争条件的情况下编写这段代码？

有没有办法注释代码以使线程清理程序忽略它？我尝试了__tsan_acquire和 __tsan_release但找不到始终有效的东西。

更新 我非常确信在标准 C++ 中无法安全地执行原子读取——该对象不再存在。但是——我可以从依赖未定义的行为转向依赖实现定义的行为吗？考虑到典型的架构和工具链(x86/ARM、gcc/clang)，我能做的最好的事情是什么？

更新 2 一种似乎可行的特定于实现的方法是用内联汇编替换负载:

inline Node *load_next_wrapper(Node *h) {
  Node *ret;
  asm volatile("movq (%1), %0" : "=r"(ret) : "r"(&h->next));
  return ret;
}

这既是体系结构又是编译器特定的——但我认为这确实用“实现定义的”行为取代了“未定义”的行为。

Answer 1

如果您只是想重用数据结构中的相同节点，则标记指针很好，即您不破坏它，而只需将其放在空闲列表中，以便在下一个需要新节点时可以重用它推操作。在这种情况下，标记指针足以防止 ABA 问题，但它们无法解决您在这里面临的_内存回收问题_。

Another object of some type will be constructed in the same location. Eventually, it will be destroyed and the memory would return to the pool.

这是真正的问题 - 您正在破坏对象并将内存重新用于其他用途。正如许多其他人已经在评论中解释的那样，这会导致未定义的行为。我不确定“返回池”是什么意思-返回内存管理器？暂时忽略 UB - 你说得对，这场比赛通常是良性的(从硬件的角度来看)，但如果你确实在某个时候释放了内存，你实际上可能会遇到段错误(例如，如果内存管理器决定将内存返回给操作系统)。

在这种情况下如何避免未定义的行为

如果您想将内存重用于其他用途，则必须使用内存回收方案，如无锁引用计数、危险指针、基于时期的回收或 DEBRA。这些可以确保一个对象只有在保证所有对它的引用都已被删除时才被销毁，因此任何线程都不能再访问它。

我的 xenium library提供了可以在这种情况下使用的各种回收方案(包括前面提到的所有方案)的 C++ 实现。