Welche dieser Implementierungen von seqlock sind richtig?

Ich studiere die Implementierung von Seqlock. Alle Quellen, die ich gefunden habe, implementieren sie jedoch unterschiedlich.

Linux Kernel

Der Linux-Kernel implementiert es so:

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;
}

Grundsätzlich verwendet es einen flüchtigen Lesevorgang plus eine Lesebarriere mit Erwerbssemantik auf der Leserseite.

Bei Verwendung sind nachfolgende Lesevorgänge ungeschützt:

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;
}

Das Laden von Daten wird immer noch ohne eine atomare Operation oder Schutz durchgeführt. Allerdings, ein atomic_signal_fence mit Acquiring-Release-Semantik wird im Gegensatz zu dem vor dem Lesen hinzugefügt rmb mit Acquir-Semantik im Kernel.

Amaneu/seqlock (Rost)

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;
        }
    }
}

Keine Speicherbarriere zwischen dem Laden seq und dataaber stattdessen wird hier ein flüchtiger Lesevorgang verwendet.

Können Seqlocks mit Programmiersprachen-Speichermodellen auskommen? (Variante 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;
}

Ähnlich der Rust-Implementierung, aber atomare Operationen statt volatile_read werden auf Daten verwendet.

Argumente ein P1478R1: Byteweise atomare Memcpy

Dieses Papier behauptet, dass:

Im allgemeinen Fall gibt es gute semantische Gründe zu fordern, dass alle Datenzugriffe innerhalb eines solchen seqlock “kritischen Abschnitts” atomar sein müssen. Wenn wir einen Zeiger p als Teil des Lesens der Daten lesen und dann auch *p lesen, liest der Code im kritischen Abschnitt möglicherweise von einer fehlerhaften Adresse, wenn beim Lesen von p zufällig ein halb aktualisierter Zeigerwert angezeigt wird. In solchen Fällen führt wohl kein Weg daran vorbei, den Zeiger mit einer konventionellen Atomlast auszulesen, und genau das ist auch erwünscht.

In vielen Fällen, insbesondere im Fall mehrerer Prozesse, bestehen Seqlock-Daten jedoch aus einem einzigen trivial kopierbaren Objekt, und der “kritische Abschnitt” von Seqlock besteht aus einer einfachen Kopieroperation. Unter normalen Umständen hätte dies mit memcpy geschrieben werden können. Das ist hier aber nicht akzeptabel, da memcpy keine atomaren Zugriffe generiert und (jedenfalls nach unserer Spezifikation) anfällig für Data Races ist.

Um solchen Code korrekt zu schreiben, müssen wir solche Daten derzeit im Grunde in viele kleine lock-freie atomare Unterobjekte zerlegen und sie Stück für Stück kopieren. Das Behandeln der Daten als ein einziges großes atomares Objekt würde den Zweck der seqlock zunichte machen, da die atomare Kopieroperation eine herkömmliche Sperre erwerben würde. Unser Vorschlag fügt im Wesentlichen eine bequeme Bibliothekseinrichtung hinzu, um diese Zerlegung in kleine Objekte zu automatisieren.

Meine Frage

1. Welche der obigen Implementierungen sind richtig? Welche sind richtig, aber ineffizient?
2. Kann das volatile_read vor dem Erfassen-Lesen von Seqlock nachbestellt werden?

Ihre Zitate von Linux scheinen falsch zu sein.

Entsprechend https://www.kernel.org/doc/html/latest/locking/seqlock.html Der Lesevorgang ist:

Read path:

do {
        seq = read_seqcount_begin(&foo_seqcount);

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

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

Wenn Sie sich den in der Frage geposteten Github-Link ansehen, finden Sie einen Kommentar, der fast denselben Prozess enthält.

Es scheint, dass Sie nur einen Teil des Lesevorgangs untersuchen. Die verknüpfte Datei implementiert, was Sie zum Implementieren von Readern und Writern benötigen, aber nicht den Reader/Writer selbst.

Beachten Sie auch diesen Kommentar am Anfang der Datei:

* 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.