SEQC(9)

🦋 SEQC(9) — lockless read algorithm 🦋

okay bestie, welcome to the SEQC(9) page from the Kernel Developer’s Manual — we’re doing lockless reads today and it’s honestly iconic. no cap.

🌸 NAME 🌸

These absolute main characters — seqc_consistent, seqc_read, seqc_write_begin, and seqc_write_end — are the lockless read algorithm. periodt.

🎀 SYNOPSIS 🎀

#include <sys/seqc.h>

void
seqc_write_begin(seqc_t *seqcp);

void
seqc_write_end(seqc_t *seqcp);

seqc_t
seqc_read(seqc_t *seqcp);

seqc_t
seqc_consistent(const seqc_t *seqcp, seqc_t oldseqc);

💅 DESCRIPTION 💅

okay so the seqc lets zero or more readers and zero or one writer concurrently access an object, and it gives readers a consistent snapshot of that object. the way that works is lowkey elegant: no mutual exclusion between readers and writers is required, but bestie, readers may be starved indefinitely by writers. yes, that’s the tradeoff. 🙈

Here’s the function vibe check:

• seqc_write_begin() and seqc_write_end() — these are for the writer. they’re used to create a transaction for the writer and notify the readers that the object will be modified.
• seqc_read() — returns the current sequence number. if a writer has started a transaction, this function will spin until the transaction has ended.
• seqc_consistent() — compares the sequence number with a previously fetched value. the oldseqc variable should contain a sequence number from the beginning of the read transaction.

At the end of a transaction, the reader checks if the sequence number has changed. if the sequence number didn’t change, the object wasn’t modified, and the fetched variables are valid. if the sequence number changed, the object was modified and the fetch should be repeated. and in the case when the sequence number is odd, the object change is in progress and the reader will wait until the write will the sequence number will become even. fr fr, that’s the whole dance. 💃

✨ EXAMPLES ✨

The following example for a writer changes the var1 and var2 variables in the obj structure:

lock_exclusive(&obj->lock);
seqc_write_begin(&obj->seqc);
obj->var1 = 1;
obj->var2 = 2;
seqc_write_end(&obj->seqc);
unlock_exclusive(&obj->lock);

The following example for a reader reads the var1 and var2 variables from the obj structure. In the case where the sequence number was changed, it restarts the whole process:

int var1, var2;
seqc_t seqc;

for (;;) {
        seqc = seqc_read(&obj->seqc);
        var1 = obj->var1;
        var2 = obj->var2;
        if (seqc_consistent(&obj->seqc, seqc))
                break;
}

👑 AUTHORS 👑

The seqc functions was implemented by Mateusz Guzik <mjg@FreeBSD.org>. This manual page was written by Mariusz Zaborski <oshogbo@FreeBSD.org>. we love a credited icon. 🫶

💀 CAVEATS 💀

⚠️ No progress guarantee for readers. There is no guarantee of progress for readers. In case when there are a lot of writers the reader can be starved. This concern may be solved by returning error after a few attempts. not me warning you about starvation in a cute font, but here we are. 😭

💀 The theoretical overflow jumpscare: Theoretically if reading takes a very long time, and when there are many writers the counter may overflow and wrap around to the same value. In that case the reader will not notice that the object was changed. Given that this needs 4 billion transactional writes across a single contended reader, it is unlikely to ever happen. This could be avoided by extending the interface to allow 64-bit counters. like, 4 billion? bestie, that’s not a vibe check, that’s a whole apocalypse. 🌈

---

Debian · July 29, 2019 · SEQC(9) — bye bestie, slay your lockless reads 💅🫶