conflict-set: fixupMaxVersion misses Node256 children past the first 16

conflict-set

This one is a fault in a bookkeeping repair path: fixupMaxVersion recomputes a node's cached max version after a range write, and for one node type it recomputes it over only a fraction of the children. The result is a max version that is too low, which makes read checks short-circuit to Commit when they should report Conflict.

It was found by a downstream project using AI inspection against main. No user-reported symptoms, and no release contains it.

🔗 Summary

Affected versions: none released. The defect is not present in any tagged release (the latest, v0.0.13, predates it) nor on the release-0.0 branch. The fix is on main.

🔗 Timeline

🔗 2024-09-13

The bug is introduced in 0814822 ("avx512 implementations for fixupMaxVersion"), a performance refactor that replaces the scalar scan in fixupMaxVersion with AVX-512 horizontal max helpers.

🔗 2026-10-06

A downstream project reports the bug, found using AI inspection of main.

🔗 2026-10-09

Root cause confirmed and fixed in 4ef10b1.

🔗 Details

Before the refactor, the Node256 branch of fixupMaxVersion scanned the node's maxOfMax pages:

case Type_Node256: {
  auto *self256 = static_cast<Node256 *>(node);
  for (auto v : self256->maxOfMax) {
    max = std::max(v, max);
  }
} break;

Node256::maxOfMax has 16 pages, each summarizing 16 of the node's 256 children, so scanning all 16 pages covers all 256 children. The refactor replaced that with:

case Type_Node256: {
  auto *self256 = static_cast<Node256 *>(node);
  max = std::max(
      max, horizontalMax16(self256->childMaxVersion, writeContext->zero));
} break;

horizontalMax16 reduces over 16 consecutive elements, but Node256::childMaxVersion has 256 elements. So this reads only the children at byte values 0x00–0x0F. The intent was horizontalMax16(self256->maxOfMax, ...).

When the endNode of a range write is a Node256 whose highest-version child lives at byte >= 0x10, fixupMaxVersion computes a max that is too low, and setMaxVersion writes that too-low value onto the node's link in its parent. A later read that passes through that link short-circuits on the bogus max and returns Commit.

Minimal reproducer. A single-byte prefix with 49 children forces a Node256 (a Node48 holds at most 48). Write the prefix itself so it has a stored version, put a high-version child at a byte outside [0x00, 0x0F], then perform a range write whose end is the prefix, which runs fixupMaxVersion on it. Here's how to reproduce (in a python-like pseudocode):

# Give "b" 49 children, so it must be a Node256, and write "b" itself.
cs = ConflictSet(0)
cs.addWrites(1, write(b"b"), *(write(b"b" + bytes([b])) for b in range(0x31)))

# Put the newest version in the child at byte 0x20.
cs.addWrites(100, write(b"b\x20"))

# A range write whose end is "b". Inserting the range's end trashes "b"'s
# cached max version, so fixupMaxVersion runs to repair it.
cs.addWrites(200, write(b"a", b"b"))

# Read the high-version child. "b" is still cached at v1, so the check
# short-circuits and reports commit. It should report conflict (100 > 50).
cs.check(read(50, b"b\x20"))
# got=commit expected=conflict

🔗 Root Cause Analysis

The root cause was a refactor that changed the quantity being summarized. horizontalMax16 reduces 16 elements, which is a drop-in replacement for a Node16 (16 children) but not for a Node256 (256 children). Calling it on childMaxVersion incorrectly narrowed the scan from 256 children to the first 16.

🔗 Why not caught sooner?

Fuzzing did not cover this case. It executed the buggy line — we have 100% line coverage — but not with the circumstances that make the bug manifest. In particular, our fuzzing has worse coverage of Node256 than of the other node types, because reaching a Node256 consumes more entropy.

🔗 How was it discovered?

By AI inspection of main in a downstream project.

🔗 Prevention

This incident to me feels like we're hitting the fundamental limitations of testing. I think the way forward is carefully tracking preconditions, invariants, and postconditions in comments and striving to structure the program as an informal proof of its own correctness, interpreting helper functions as "lemmas". This is obviously a good style to use anyway but it always felt a little silly without anything mechanically checking the comments. I think with a little tooling and recent LLM capabilities those comments can basically be mechanically checked now, at least informally.

I also plan to augment the fuzz testing until it catches this bug on its own (issue #85).

🔗 What went well