6

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

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

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

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

  1. 有没有办法在没有竞争条件的情况下编写这段代码？
  2. 有没有办法注释代码以使线程清理程序忽略它？我尝试过__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;
}

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

4

1 回答 1

0

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

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

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

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

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

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

于 2020-05-21T17:08:27.940 回答