首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何避免或抑制此无锁堆栈中的竞争?

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

Stack Overflow用户
提问于 2020-05-20 17:53:06
回答 1查看 322关注 0票数 6

我使用一个释放锁的堆栈(通过标记的指针)来管理一个小内存块池。当将块插入池并从池中移除时,列表节点将就地创建和销毁。

这是一个非常简化的测试程序,它只从堆栈中弹出。所以,没有ABA问题,也没有标记的指针。只要演示一下我所遇到的比赛就足够了:

代码语言:javascript
复制
#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;
}

线程清除器报告以下错误:

代码语言:javascript
复制
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之前完成pop并覆盖节点。

这类似于这里讨论的问题:除了内存实际上没有被释放之外,为什么“删除”这个无锁堆栈类中的节点会导致争用状态?

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

  1. 有没有任何方法可以在没有竞争条件的情况下编写这段代码?
  2. 是否有任何方法对代码进行注释,使线程清除器忽略它?我用__tsan_acquire__tsan_release做了实验,但找不到持续有效的东西。

Update我非常确信,没有办法在标准C++中安全地执行原子读取--对象只是不再存在了。但是--我能从依赖未定义的行为转向依赖于实现定义的行为吗?考虑到典型的体系结构和工具链(x86/ARM,gcc/clang),我能做的最好的是什么?

Update 2一种似乎有效的特定于实现的方法是用内联程序集替换加载:

代码语言:javascript
复制
inline Node *load_next_wrapper(Node *h) {
  Node *ret;
  asm volatile("movq (%1), %0" : "=r"(ret) : "r"(&h->next));
  return ret;
}

这既是体系结构,也是编译器特有的--但我认为这确实将“未定义”行为替换为“实现定义”行为。

EN

回答 1

Stack Overflow用户

发布于 2020-05-21 17:08:27

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

另一个类型的对象将在同一位置构造。最终,它将被摧毁,记忆将回到池中。

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

如何避免本场景中未定义的行为

如果您想要将内存重用到其他方面,您必须使用内存回收方案,如无锁引用计数、危险指针、基于时代的回收或黛布拉。这可以确保只有在保证删除了对对象的所有引用之后才销毁对象,因此任何线程都不能访问对象。

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

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/61919666

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档