我使用一个释放锁的堆栈(通过标记的指针)来管理一个小内存块池。当将块插入池并从池中移除时,列表节点将就地创建和销毁。
这是一个非常简化的测试程序,它只从堆栈中弹出。所以,没有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;
}线程清除器报告以下错误:
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++中未定义的行为领域。
__tsan_acquire和__tsan_release做了实验,但找不到持续有效的东西。Update我非常确信,没有办法在标准C++中安全地执行原子读取--对象只是不再存在了。但是--我能从依赖未定义的行为转向依赖于实现定义的行为吗?考虑到典型的体系结构和工具链(x86/ARM,gcc/clang),我能做的最好的是什么?
Update 2一种似乎有效的特定于实现的方法是用内联程序集替换加载:
inline Node *load_next_wrapper(Node *h) {
Node *ret;
asm volatile("movq (%1), %0" : "=r"(ret) : "r"(&h->next));
return ret;
}这既是体系结构,也是编译器特有的--但我认为这确实将“未定义”行为替换为“实现定义”行为。
发布于 2020-05-21 17:08:27
如果您只是想重用数据结构中相同的节点,即不销毁它,而只是将其放在一个自由列表上,以便在下一个推送操作中需要一个新节点时,则标记指针是可以重用的。在这种情况下,带标记的指针足以防止ABA问题,但它们不能解决您在这里面临的内存回收problem_。
另一个类型的对象将在同一位置构造。最终,它将被摧毁,记忆将回到池中。
这才是真正的问题--你正在破坏对象,并将内存重用到其他东西上。正如许多其他人已经在注释中解释的那样,这会导致未定义的行为。我不知道你所说的“返回池”是什么意思--返回到内存管理器?暂时忽略UB --您是对的,这种竞争通常是良性的(从硬件角度来看),但是如果您确实在某个时候释放了内存,您实际上可能会遇到分段错误(例如,如果内存管理器决定将内存返回给操作系统)。
如何避免本场景中未定义的行为
如果您想要将内存重用到其他方面,您必须使用内存回收方案,如无锁引用计数、危险指针、基于时代的回收或黛布拉。这可以确保只有在保证删除了对对象的所有引用之后才销毁对象,因此任何线程都不能访问对象。
我的xenium库提供了您可以在这种情况下使用的各种回收方案(包括前面提到的所有方案)的C++实现。
https://stackoverflow.com/questions/61919666
复制相似问题