zu2: both seqlock readers can return a torn read, because the validating load has nothing under it

[tamnd]

A seqlock reader takes the sequence, reads the data, and takes the sequence again. The second read is what makes the first one mean anything, and for that to work the data has to be read before it. Neither reader in zu2 makes that true.

Neighbourhood::read in crates/zu2/src/graph.rs:

let before = self.version.load(Ordering::Acquire);
if before & LOCK != 0 { std::hint::spin_loop(); continue; }
let answer = visit(unsafe { self.slice() });
if self.version.load(Ordering::Acquire) == before {
    return answer;
}

The neighbours are plain loads out of the inline array or the block. An acquire load orders only what comes after it, so nothing stops those plain loads from being taken after the validating load. The check then reads a version from before the writer started while the data comes back from the middle of what the writer did, the versions match, and the torn read is returned as the answer. That is the missing smp_rmb of the textbook seqlock, and Boehm's "Can seqlocks get along with programming language memory models?" (MSPC 2012) is the write-up of exactly this hole.

Record::read_value in crates/zu2/src/record.rs has the same shape, with an extend_from_slice where the graph has a walk, so a point read of a record being updated in place can come back half old and half new with a version that says it did not.

It is not theoretical and it is not rare. The new crates/zu2/tests/graphracy.rs has four threads writing edges into their own runs of node ids while a compaction runs under them and each thread also reads another thread's hub, where the model says nothing but sorted, no duplicates and every id inside the owner's run has to hold whatever the writer is doing. On an aarch64 laptop at 200000 operations a thread it fails 3 to 4 runs in 20:

thread 3 at op 87812: hub of 0 came back unsorted or with a duplicate:
[0, 1, 2, 3, 4, 5, 7, ..., 251, 252, 253, 253, 254]

Every failure is one adjacent duplicate, which is exactly the state insert_sorted leaves halfway through:

Err(at) => {
    slots.copy_within(at..len, at + 1);
    slots[at] = value;

so the reader is inside the writer's memmove and the version check is not catching it.

x86 does not reorder load with load, so this needs a weakly ordered machine to show, and it is a compiler reordering everywhere. The fix is an acquire fence between the data and the validating load, which is nothing on x86 and a dmb ishld on aarch64, on a path that already does two atomic loads.

What has to be true when this is closed:

• Neighbourhood::read fences between the data and the check
• Record::read_value fences between the copy and the check
• tests/graphracy.rs, which is the first test to write edges from more than one thread at all
• the same run green thirty times over with the fix, against three to four failures in twenty without it
• the fence measured on a hop, on a host rather than on the laptop, so the cost is a number rather than an argument

[tamnd]

Fixed at 0d197e9 on zu2-planes, and three of the five boxes are ticked.

Both readers now fence between the data and the check, and the validating load drops to relaxed because the fence is what orders it:

let answer = visit(unsafe { self.slice() });
std::sync::atomic::fence(Ordering::Acquire);
if self.version.load(Ordering::Relaxed) == before {
    return answer;
}

The evidence, all on the aarch64 laptop at 200000 operations a thread, tests/graphracy.rs:

	failures in 20 runs
without the fence	3
without the fence, earlier round	4
with the fence	0 in 30

Every failure without it is one adjacent duplicate at the sortedness assert, which is the state insert_sorted leaves halfway through its memmove, so the reader was inside the writer's copy and the version check agreed with it. The control was run by taking the fence back out of the same tree rather than by going back to the old commit, so nothing else moved between the two columns.

Suite is 32 binaries, 196 passed 0 failed, clippy clean, cargo fmt --check clean.

Left open is the cost, which is a number owed on a host rather than on the laptop. s3-782.sh is queued on server3 behind the sqlite E retake and the two mapping jobs: two runs of benches/traverse.rs at a million vertices and degree 16, one with the fence and one with it patched out of the same tree, plus twenty runs of the race there. server3 is x86, where a load is not reordered with a load and the fence is a compiler barrier and nothing else, so the expected answer is that the two runs are the same within noise. Worth writing down either way: the fix is free where the whole fleet runs, and the machine that catches the bug is the one nobody publishes from.