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

Question

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

Ale*_*x K 6 c++ multithreading thread-sanitizer

我正在使用无锁堆栈（通过标记指针）来管理小内存块池。当块被插入到池中和从池中移除时，列表节点就地创建和销毁。

这是一个非常简化的测试程序，它只从堆栈中弹出。因此，没有 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;
}

Run Code Online (Sandbox Code Playgroud)

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

Run Code Online (Sandbox Code Playgroud)

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

这类似于这里讨论的问题：为什么在这个无锁堆栈类中“删除”节点会导致竞争条件？除了内存实际上没有被释放。

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

有没有办法在不出现竞争条件的情况下编写此代码？
有什么方法可以注释代码以使线程清理器忽略它吗？我尝试过__tsan_acquire，__tsan_release但找不到始终有效的东西。

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

更新 2一种似乎有效的特定于实现的方法是用内联程序集替换负载：

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

Run Code Online (Sandbox Code Playgroud)

这是特定于架构和编译器的——但我认为这确实用“实现定义”行为替换了“未定义”行为。

Answer 1

mpo*_*ter 0

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

某种类型的另一个对象将在同一位置构造。最终，它将被销毁，内存将返回到池中。

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

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

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

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

归档时间：	6 年，3 月前
查看次数：	180 次
最近记录：	6 年，3 月前