危害指标的内存排序 [英] Memory ordering for hazard-pointers

问题描述

下面的代码段是它们大大简化了危害指示器算法之后得到的代码(在

The following piece of code is what one can get after they significantly simplify the hazard-pointer algorithm (introduced in this paper). Because of the gross amount of simplification, it cannot be used in place of the algorithm (and one does not need to know anything about the algorithm to answer this question). However, I believe it still perfectly represents the memory-ordering challenge in the original algorithm.

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

So the question is what is the best memory-ordering so that if ptr->a = 1; gets executed, the result won't be undefined (values of 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的效果.即使我们到处都只使用顺序的内存排序，我也无法弄清楚为什么代码会起作用.

We know for ptr->a=1; to get executed, a.exchange must happen after the 2nd a.load (even relaxed-memory ordering guarantees this). However, the problem is how to ensure h.load will see the effect of h.store. I cannot figure out why the code works even if we only use sequential memory-ordering everywhere.

推荐答案

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

For simplicity, these paper usually assume a sequential consistent memory model - that is also the case for the paper you referenced. Your example is highly simplified, but it still contains the gist of hazard pointer algorithm. You have to ensure that either Thread 2 "sees" the hazard pointer stored by Thread 1 (i.e., Thread 1 has acquired a safe reference), or Thread 1 sees the updated value of a.

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

In my argument I will use the following notation - a -sb-> b means "a is sequenced before b" - a -sco-> b means "a precedes b in the single total order S of all sequential consistent operations" - a -rf-> b means "b reads the value written by a" (reads-from)

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

Let's assume that all atomic operations are sequentially consistent. That would give the following situation:

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

• Thread 1: a.load() -sb-> h.store() -sb-> a.load() -sb-> ptr->a=1
• Thread 2: a.exchange() -sb-> h.load() -> delete ptr

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

Since sequential consistent operations are totally ordered, we have to consider two cases:

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

• h.store() -sco-> h.load()
  This implies h.store() -rf-> h.load(), i.e., Thread 2 is guaranteed to "see" the hazard pointer written be Thread 1, so it does not delete the ptr (and Thread 1 can therefore safely update 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).

h.load() -sco-> h.store()
Because we also have a.exchange() -sb-> h.load() (Thread 2) and h.store() -sb-> a.load() (Thread 1), this implies that a.exchange() -sco-> a.load() and therefore a.exchange() -rf-> a.load(), i.e., Thread 1 is guaranteed to "see" the updated value of a (and therefore does not attempt to update ptr->a).

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

So if all operations are sequentially consistent, the algorithm works as intended. But what if we cannot (or don't want to) assume that all operations are sequentially consistent? Can we relax some operations? The problem is that we have to ensure visibility between two different variables (a and h) in two different thread, and this requires stronger guarantees then acquire/release can provide. However, it is possible to relax the operations if you introduce sequentially consistent fences:

// 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

• Thread 1: a.load() -sb-> h.store() -sb-> fence() -sb-> a.load() -sb-> ptr->a=1
• Thread 2: a.exchange() -sb-> fence() -sb-> h.load() -> delete ptr

标准规定:

对于原子对象 M 上的原子操作 A 和 B ，其中 A 修改 M 和 B 取其值，如果存在memory_order_seq_cst栅栏 X 和 Y 使得 A 为在 X 之前排序， Y 在 B 之前排序，并且 X 在 Y 之前 S ，然后 B 观察 A 的效果或后来对 M 的修改顺序.

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 的一部分，因此我们再次考虑两种情况:

The fences are also part of the single total order S so we again have two cases to consider:

• 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的更新值.

• Thread1 fence -sco-> Thread 2 fence
  Since h.store() -sb-> fence() (Thread 1) and fence() -sb-> h.load() (Thread 2) it is guaranteed that Thread 2 "sees" the hazard pointer written by Thread 1.
• Thread 2 fence -sco-> Thread 1 fence
  Since a.exchange() -sb-> fence() (Thread 2) and fence() -sb-> a.load() (Thread 1) it is guaranteed that Thread 1 "sees" the updated value of a.

以后的版本正是我在 xenium 库中实现危险指针的方式.

The later version is exactly how I have implemented hazard pointers in my xenium library.

这篇关于危害指标的内存排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！