哪些seqlock实现正确？

Question

我正在研究Seqlock的实现。但是我发现的所有资料来源都以不同的方式实现它们。

Linux内核

Linux内核是这样实现的：

static inline unsigned __read_seqcount_begin(const seqcount_t *s)
{
    unsigned ret;

repeat:
    ret = READ_ONCE(s->sequence);
    if (unlikely(ret & 1)) {
        cpu_relax();
        goto repeat;
    }
    return ret;
}

static inline unsigned raw_read_seqcount_begin(const seqcount_t *s)
{
    unsigned ret = __read_seqcount_begin(s);
    smp_rmb();
    return ret;
}

基本上，它使用易失性读取以及在读取器端具有获取语义的读取屏障。

使用时，后续读取不受保护：

struct Data {
    u64 a, b;
};

// ...
read_seqcount_begin(&seq);
int v1 = d.a, v2 = d.b;
// ...

rigtorp / Seqlock

RIGTORP_SEQLOCK_NOINLINE T load() const noexcept {
  T copy;
  std::size_t seq0, seq1;
  do {
    seq0 = seq_.load(std::memory_order_acquire);
    std::atomic_signal_fence(std::memory_order_acq_rel);
    copy = value_;
    std::atomic_signal_fence(std::memory_order_acq_rel);
    seq1 = seq_.load(std::memory_order_acquire);
  } while (seq0 != seq1 || seq0 & 1);
  return copy;
}

数据加载仍在没有原子操作或保护的情况下执行。但是，atomic_signal_fence与rmb内核中的带有获取语义相反，在读取之前添加了带有获取释放语义。

Amanieu / seqlock（铁锈色）

pub fn read(&self) -> T {
    loop {
        // Load the first sequence number. The acquire ordering ensures that
        // this is done before reading the data.
        let seq1 = self.seq.load(Ordering::Acquire);

        // If the sequence number is odd then it means a writer is currently
        // modifying the value.
        if seq1 & 1 != 0 {
            // Yield to give the writer a chance to finish. Writing is
            // expected to be relatively rare anyways so this isn't too
            // performance critical.
            thread::yield_now();
            continue;
        }

        // We need to use a volatile read here because the data may be
        // concurrently modified by a writer.
        let result = unsafe { ptr::read_volatile(self.data.get()) };

        // Make sure the seq2 read occurs after reading the data. What we
        // ideally want is a load(Release), but the Release ordering is not
        // available on loads.
        fence(Ordering::Acquire);

        // If the sequence number is the same then the data wasn't modified
        // while we were reading it, and can be returned.
        let seq2 = self.seq.load(Ordering::Relaxed);
        if seq1 == seq2 {
            return result;
        }
    }
}

在加载seq和之间没有内存障碍data，而是在这里使用了易失性读取。

Seqlocks可以和编程语言记忆模型相处吗？（变体3）

T reader() {
  int r1, r2;
  unsigned seq0, seq1;
  do {
    seq0 = seq.load(m_o_acquire);
    r1 = data1.load(m_o_relaxed);
    r2 = data2.load(m_o_relaxed);
    atomic_thread_fence(m_o_acquire);
    seq1 = seq.load(m_o_relaxed);
  } while (seq0 != seq1 || seq0 & 1);
  // do something with r1 and r2;
}

与Rust实现类似，但是volatile_read对数据使用原子操作而不是原子操作。

P1478R1中的参数：按字节的原子memcpy

本文声称：

在一般情况下，出于充分的语义上的原因，要求这样的seqlock“关键部分”内部的所有数据访问必须是原子的。如果我们在读取数据的过程中先读取了指针p，然后又读取了* p，则如果读取p时碰巧看到指针值已更新一半，则临界区中的代码可能会从错误的地址读取。在这种情况下，可能无法避免以常规原子负载读取指针，而这正是所希望的。

但是，在许多情况下，尤其是在多进程情况下，seqlock数据由一个简单的可复制对象组成，而seqlock“关键部分”由简单的复制操作组成。在正常情况下，这可以使用memcpy编写。但这在这里是不可接受的，因为memcpy不会生成原子访问，并且（无论如何根据我们的规范）容易受到数据竞争的影响。

当前，要正确地编写此类代码，我们需要将此类数据基本分解为许多小的无锁原子子对象，然后一次复制它们。将数据视为单个大的原子对象会破坏seqlock的目的，因为原子复制操作将获得常规锁。我们的建议本质上增加了一种便利的库工具，可以自动将分解分解为小对象。

我的问题

1. 以上哪种实现是正确的？哪些是正确的但效率低下？
2. 可以在volatile_readseqlock的读取读取之前重新排序吗？

Answer 1

你的 Linux 的 qoutes 似乎是错误的。

根据https://www.kernel.org/doc/html/latest/locking/seqlock.html，读取过程是：

Read path:

do {
        seq = read_seqcount_begin(&foo_seqcount);

        /* ... [[read-side critical section]] ... */

} while (read_seqcount_retry(&foo_seqcount, seq));

如果您查看问题中发布的 github 链接，您会发现一条评论，其中包含几乎相同的过程。

看来您只研究了阅读过程的一部分。链接文件实现了实现读取器和写入器所需的功能，但不是读取器/写入器本身。

另请注意文件顶部的这条注释：

* The seqlock seqcount_t interface does not prescribe a precise sequence of
* read begin/retry/end. For readers, typically there is a call to
* read_seqcount_begin() and read_seqcount_retry(), however, there are more
* esoteric cases which do not follow this pattern.