c++ - 危害指标的内存排序

Question

以下代码是在大大简化了危害指示器算法(在this论文中引入)之后可以得到的代码。由于总的简化，因此不能代替算法使用(并且不需要知道任何有关算法的知识即可回答此问题)。但是，我相信它仍然完美地代表了原始算法中的内存排序挑战。

所以问题是什么是最好的内存排序，以便如果执行ptr->a = 1;，结果将不会是不确定的(order1 ... order5的值)？

struct T { int a = 0; };
static_assert(std::is_trivially_destructible_v<T>);
std::atomic<T*> a{new T()};
std::atomic<T*> h{nullptr};

// Thread 1
auto ptr = a.load(order1);
h.store(ptr,order2);
if(ptr == nullptr || ptr != a.load(order3))
  return;
ptr->a = 1;

// Thread 2
auto ptr = a.exchange(nullptr,order4);
if(ptr != h.load(order5))
  delete ptr;

我们知道要执行 ptr->a=1;， a.exchange必须在第二个 a.load之后发生(即使是宽松的内存顺序也可以保证这一点)。但是，问题在于如何确保 h.load可以看到 h.store的效果。即使我们在任何地方都只使用顺序的内存排序，我也无法弄清楚为什么代码会起作用。

Answer 1

为简单起见，这些论文通常采用顺序一致的内存模型-您引用的论文也是如此。您的示例已高度简化，但仍包含危险指针算法的要点。您必须确保线程2“看到”线程1存储的危险指针(即线程1已获取安全引用)，或者线程1看到了更新的a值。

在我的论点中，我将使用以下表示法
-a -sb-> b表示“a在b之前排序”
-a -sco-> b的意思是“在所有顺序一致操作的单个总顺序S中，a在b之前”
-a -rf-> b表示“b读取a写入的值”(读取自)

假设所有原子操作都是顺序一致的。这将导致以下情况:

线程1:a.load() -sb-> h.store() -sb-> a.load() -sb-> ptr->a=1

线程2:a.exchange() -sb-> h.load() -> delete ptr

由于顺序一致操作是完全有序的，因此我们必须考虑两种情况:

h.store() -sco-> h.load()
这意味着h.store() -rf-> h.load()，即，保证线程2“看到”由线程1编写的危险指针，因此它不会删除ptr(因此线程1可以安全地更新ptr->a)。

h.load() -sco-> h.store()
因为我们也有a.exchange() -sb-> h.load()(线程2)和h.store() -sb-> a.load()(线程1)，所以这意味着a.exchange() -sco-> a.load()和a.exchange() -rf-> a.load()(即线程1)保证“看到”了a的更新值(因此不尝试更新ptr->a)。

因此，如果所有操作顺序一致，则该算法将按预期工作。但是，如果我们不能(或不想)假设所有操作都顺序一致怎么办？我们可以放松一些操作吗？问题是我们必须确保两个不同线程中两个不同变量( a和 h)之间的可见性，这需要获得/释放才能提供的更强有力的保证。但是，如果引入顺序一致的栅栏，则可以放宽操作:

// Thread 1
auto ptr = a.load(std::memory_order_acquire);
h.store(ptr, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_seq_cst);
if(ptr == nullptr || ptr != a.load(std::memory_order_relaxed))
  return;
ptr->a = 1;

// Thread 2
auto ptr = a.exchange(nullptr, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_seq_cst);
if(ptr != h.load(std::memory_order_relaxed))
  delete ptr;

因此，我们有以下情况:

线程1:a.load() -sb-> h.store() -sb-> fence() -sb-> a.load() -sb-> ptr->a=1

线程2:a.exchange() -sb-> fence() -sb-> h.load() -> delete ptr

标准规定:

For atomic operations A and B on an atomic object M, where A modifies M and B takes its value, if there are memory_order_seq_cst fences X and Y such that A is sequenced before X, Y is sequenced before B, and X precedes Y in S, then B observes either the effects of A or a later modification of M in its modification order.

栅栏也是单个总订单S的一部分，因此我们再次考虑两种情况:

Thread1 fence -sco-> Thread 2 fence
由于h.store() -sb-> fence()(线程1)和fence() -sb-> h.load()(线程2)，因此可以确保线程2“看到”线程1编写的危险指针。

Thread 2 fence -sco-> Thread 1 fence
由于a.exchange() -sb-> fence()(线程2)和fence() -sb-> a.load()(线程1)，因此可以确保线程1“看到” a的更新值。

更高的版本正是我在 xenium库中实现危害指针的方式。