Reading and writing¶

Several processes reading and writing the same memory at once is how data gets mixed up: a reader can catch a writer halfway, or a buggy process can scribble over the layout everyone relies on. This page explains the two habits that keep a box safe while other processes use the same segment: a process never trusts the shared copy of the layout, and it writes only under a sequence lock.

Never trust the shared copy of the layout¶

Any process that can open the block can also write to it, header included. So if the code read a field's offset from the header every time it copied data, another process could change that offset between the check and the copy, and make this process read or write outside the block. This mistake has a name, "time of check, time of use".¹

To rule it out, a process that opens an existing block copies line 0 of the header and the field table once, checks those copies against the size of the mapping as the operating system reports it (fstat on Linux, VirtualQuery on Windows), and from then on uses only its own copies. The header's own size field must match the mapping size, but the mapping size comes from the OS, not from the block. The same idea applies to values arriving from Python: the native write checks the size of every value before it takes the write lock, so a bad value in a multi-field update changes nothing.

The write lock: a sequence counter¶

The lock has two jobs: a reader must never hold up a writer, and neither should need a call into the operating system in the usual case. A single counter in the header does both. The technique is called a sequence lock:² the counter is even when no write is in progress and odd while one is running.

Step through a write that lands in the middle of a read, and point at a shape to read what it does:

Because the reader always checks the counter again after copying, it never returns a mix of old and new bytes,² and writes to several fields (update(a=..., b=...)) are seen all at once or not at all. The writer takes the counter from even to odd with one compare-and-swap, so two writers can't both win. Sequence lock gives the exact steps and orderings, including why the unlock is a compare-and-swap rather than a plain store.

The code needs memory_order arguments and fences because processors and compilers are allowed to reorder memory accesses when a single thread cannot tell the difference.³ Here another process can tell. The fences forbid the reorderings that would break the rule above: the writer's data copy may not move before it takes the lock or after it releases it, and the reader's check of the counter may not move before its copy. This placement of the fences, a release fence after the writer takes the counter and an acquire fence between the reader's copy and its second look at the counter, is the one Boehm shows to be correct for C++.⁴

sharedbox does not use an ordinary mutex, for three reasons:

• A reader never makes a writer wait. With a mutex, a slow reader delays every writer.
• A process that dies holding a mutex leaves it held in a way other processes cannot always detect. A dead writer here leaves an odd counter and its pid in writer_pid, so you can see who held the lock, and force_unlock releases it.
• Writers take turns. One lock per box is enough for records the size of a dataclass, and it is what lets update change several fields at once.

The counter must be usable from several processes at once. C++ only guarantees that for atomic operations the processor performs directly, without a hidden lock inside the program,⁵ so the header checks at compile time that the counter's operations are of that kind:

static_assert(std::atomic_ref<std::uint64_t>::is_always_lock_free);

writing holds this same lock for as long as its block runs, so a reader that starts in the meantime keeps retrying until the block ends. If that takes longer than the reader's lock timeout, the reader gives up with LockTimeoutError. That trade is worth it for a large array a producer can fill in place, because it saves a full copy, but only while the block stays shorter than the readers' lock timeout.

Waiting for the lock¶

A writer that waits too long for the lock, or a reader that keeps losing to writers, gives up after lock_timeout seconds with LockTimeoutError, whose message names the process stored in writer_pid as the lock's holder. That process may have died while holding the lock, and force_unlock releases it.

The wait for the lock spins, then yields, then sleeps for a doubling interval of at most 1 ms. On Windows a sleep ends on a timer tick, so a wait lasts at least one tick; the Notes of SharedBox give its length. In the stress tests on GitHub Actions runners (CI runs 36440952244 and 36443594984), a 1 ms lock_timeout ended after 15.7 and 15.8 ms on Windows (median of 200 waits), against 1.18 and 1.16 ms on Linux. A lock holder that is descheduled for one timer tick can also make a short timeout expire: with a 10 ms lock_timeout and two contending writers, the Windows runner timed out 1 of 4.3 million writes in the first run and none of 2.9 million in the second.

Sources¶