title: Which of these implementations of seqlock are correct?
body: <p>I am studying the implementation of <a href="https://en.wikipedia.org/wiki/Seqlock" rel="noreferrer">Seqlock</a>. However all sources I found implement them differently.</p>
  
  <h2>Linux Kernel</h2>
  
  <p><a href="https://github.com/torvalds/linux/blob/master/include/linux/seqlock.h" rel="noreferrer">Linux kernel implements it like this</a>:</p>
  
  <pre class="lang-c prettyprint-override"><code>static inline unsigned __read_seqcount_begin(const seqcount_t *s)
  {
      unsigned ret;
  
  repeat:
      ret = READ_ONCE(s-&gt;sequence);
      if (unlikely(ret &amp; 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;
  }
  </code></pre>
  
  <p>Basically, it uses a volatile read plus a read barrier with acquire semantics on the reader side.</p>
  
  <p>When used, subsequent reads are unprotected:</p>
  
  <pre class="lang-c prettyprint-override"><code>struct Data {
      u64 a, b;
  };
  
  // ...
  read_seqcount_begin(&amp;seq);
  int v1 = d.a, v2 = d.b;
  // ...
  </code></pre>
  
  <h2><a href="https://github.com/rigtorp/Seqlock/blob/master/include/rigtorp/Seqlock.h" rel="noreferrer">rigtorp/Seqlock</a></h2>
  
  <pre class="lang-cpp prettyprint-override"><code>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 &amp; 1);
    return copy;
  }
  </code></pre>
  
  <p>The load of data is still performed without an atomic operation or protection. However, an <code>atomic_signal_fence</code> with acquire-release semantics is added prior to the read, in contrast to the <code>rmb</code> with acquire semantics in Kernel.</p>
  
  <h2><a href="https://github.com/Amanieu/seqlock/blob/master/src/lib.rs#L147" rel="noreferrer">Amanieu/seqlock</a> (Rust)</h2>
  
  <pre class="lang-rust prettyprint-override"><code>pub fn read(&amp;self) -&gt; 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 &amp; 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;
          }
      }
  }
  </code></pre>
  
  <p>No memory barrier between loading <code>seq</code> and <code>data</code>, but instead a volatile read is used here.</p>
  
  <h2><a href="http://safari.ece.cmu.edu/MSPC2012/slides_posters/boehm-poster.pdf" rel="noreferrer">Can Seqlocks Get Along with Programming Language Memory Models? (Variant 3)</a></h2>
  
  <pre class="lang-cpp prettyprint-override"><code>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 &amp; 1);
    // do something with r1 and r2;
  }
  </code></pre>
  
  <p>Similar to the Rust implementation, but atomic operations instead of <code>volatile_read</code> are used on data. </p>
  
  <h2>Arguments in <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1478r1.html" rel="noreferrer">P1478R1: Byte-wise atomic memcpy</a></h2>
  
  <p>This paper claims that:</p>
  
  <blockquote>
    <p>In the general case, there are good semantic reasons to require that all data accesses inside such a seqlock "critical section" must be atomic. If we read a pointer p as part of reading the data, and then read *p as well, the code inside the critical section may read from a bad address if the read of p happened to see a half-updated pointer value. In such cases, there is probably no way to avoid reading the pointer with a conventional atomic load, and that's exactly what's desired.</p>
    
    <p>However, in many cases, particularly in the multiple process case, seqlock data consists of a single trivially copyable object, and the seqlock "critical section" consists of a simple copy operation. Under normal circumstances, this could have been written using memcpy. But that's unacceptable here, since memcpy does not generate atomic accesses, and is (according to our specification anyway) susceptable to data races.</p>
    
    <p>Currently to write such code correctly, we need to basically decompose such data into many small lock-free atomic subobjects, and copy them a piece at a time. Treating the data as a single large atomic object would defeat the purpose of the seqlock, since the atomic copy operation would acquire a conventional lock. Our proposal essentially adds a convenient library facility to automate this decomposition into small objects.</p>
  </blockquote>
  
  <h2>My question</h2>
  
  <ol>
  <li>Which of the above implementations are correct? Which are correct but inefficient?</li>
  <li>Can the <code>volatile_read</code> be reordered before the acquire-read of seqlock?</li>
  </ol>