test_fixup_256 passes on the buggy fixupMaxVersion Node256 code: no test in the repo catches 4ef10b1's false-Commit bug #89

New Issue

2026-10-25T22:47:27Z

weaselbot commented

2026-10-25 22:47:27 +00:00

fixupMaxVersion for Node256 (ConflictSet.cpp:2900-2931) used to read self256->childMaxVersion, which horizontalMax16 only scans 16 entries of, instead of the 16 pages of self256->maxOfMax. 4ef10b1 fixed that (line 2928) after the bug was evidently found by hand: the fuzz corpus does not catch it (#85). But neither does the scripted test that was written for exactly this code -- test_conflict_set.py::test_fixup_256 (added by 1d9e8ab, "Add missing test coverage for fixupMaxVersion for Node256", test_conflict_set.py:225-231) -- so at the moment no test in the tree detects a false Commit in fixupMaxVersion for Node256; the fix is unverified by CI.

Minimal reproducer (valid API usage, no invalid input)

// repro.cpp
#include "ConflictSet.h"
#include <cstdio>
#include <vector>
using namespace weaselab;

int main() {
  ConflictSet cs{0};
  std::vector<std::vector<uint8_t>> keys;
  std::vector<ConflictSet::WriteRange> w1;
  for (int b = 0; b < 256; ++b) {          // makes a Node256 under "\x10"
    keys.push_back({0x10, (uint8_t)b});
    w1.push_back({{keys.back().data(), 2}, {nullptr, 0}});
  }
  cs.addWrites(w1.data(), (int)w1.size(), 1);              // all 256 children at v1
  std::vector<uint8_t> k = {0x10, 0x50};                   // child index 0x50 >= 16
  ConflictSet::WriteRange w2{{k.data(), 2}, {nullptr, 0}};
  cs.addWrites(&w2, 1, 10);                                // high version, high child index
  std::vector<uint8_t> b0 = {0x05}, b1 = {0x10};
  ConflictSet::WriteRange w3{{b0.data(), 1}, {b1.data(), 1}};  // range [0x05, 0x10) ends at the Node256
  cs.addWrites(&w3, 1, 11);

  // write at v10 > 5 intersects {0x10,0x50} => postcondition requires Conflict
  ConflictSet::ReadRange r{{k.data(), 2}, {nullptr, 0}, 5};
  ConflictSet::Result res = ConflictSet::TooOld;
  cs.check(&r, &res, 1);
  printf("result=%d (0=Commit 1=Conflict 2=TooOld) expected 1\n", (int)res);
  return res == ConflictSet::Conflict ? 0 : 1;
}

$ clang++ -std=c++20 -O1 -I include repro.cpp ConflictSet.cpp -isystem third_party/valgrind -o repro
$ ./repro
result=1 (0=Commit 1=Conflict 2=TooOld) expected 1        # HEAD (ba781b8): correct

Now revert only the fix in ConflictSet.cpp:2928:

-    max = std::max(max, horizontalMax16(self256->maxOfMax, writeContext->zero));
+    max = std::max(max, horizontalMax16(self256->childMaxVersion, writeContext->zero));

$ ./repro
result=0 (0=Commit 1=Conflict 2=TooOld) expected 1        # WRONG: reports Commit

The project's own invariant checker also sees it. Appending checkCorrectness(cs.rootParent->children[0], cs.oldestVersion, &cs) and running it after the third addWrites in a whitebox build prints, with the fix reverted:

 x10 has max version 1 . Expected 10

i.e. the Node256 for "\x10" gets its max version clobbered from 10 down to 1 by eraseInRange -> fixupMaxVersion (ConflictSet.cpp:2999), because only children 0..15 were considered, and the high-version child is 0x50. A later read is then short-circuited by the too-low maxVersion and returns Commit instead of Conflict.

Why `test_fixup_256` misses it

def test_fixup_256():                          # test_conflict_set.py:225
    with DebugConflictSet() as cs:
        cs.addWrites(0, write(bytes([1])))
        for i in range(256):
            cs.addWrites(1, write(bytes([1, i])))
        cs.addWrites(2, write(bytes([0]), bytes([1])))
        cs.check(read(0, bytes([1]), bytes([2])))

It does build the right shape (a Node256 whose key is the end of a range write), but every one of the 256 children is written at the same version (1). max(childMaxVersion[0..15]) then equals max(maxOfMax), so the buggy line and the fixed line compute the same value and the test cannot distinguish them. The bug only shows up when the highest-version child has an index >= 16 (the value horizontalMax16 never looks at).

Verified: with the one-line revert above,

python3 test_conflict_set.py test fixup_256 --build-dir <reverted build> -> passes (exit 0),
the whole corpus passes as well -- fuzz_driver (with checkCorrectness) and the blackbox driver over all 2845 files in corpus/: 0 failures.

Suggested test (verified to fail on the buggy code, pass on HEAD)

def test_fixup_256_heterogeneous_versions():
    with DebugConflictSet() as cs:
        for i in range(256):
            cs.addWrites(1, write(bytes([0x10, i])))
        cs.addWrites(10, write(bytes([0x10, 0x50])))          # high version, child index >= 16
        cs.addWrites(11, write(bytes([0x05]), bytes([0x10])))  # range ends at the Node256
        assert cs.check(read(5, bytes([0x10, 0x50]))) == [Result.CONFLICT]

Against the reverted (buggy) library this fails in DebugConflictSet.check (test_conflict_set.py:28, AssertionError: radix tree says Commit, skip list says Conflict); against HEAD it passes.

Relation to #85

#85 ("Enhance fuzz tests to cover Node256 better / We should be able to catch 0814822 in the fuzz tests") is about the corpus. This report is about the scripted test that was added specifically "for fixupMaxVersion for Node256" (1d9e8ab), which silently does not exercise the bug, and it offers the minimal input that does (usable both as a corpus seed and as a test_conflict_set.py case). Since 0814822 introduced the bug after test_fixup_256 was written, the test never had a chance to fail; it should be strengthened rather than trusted as coverage of this code.

Impact

A wrong Commit for a conflicting read is the worst kind of bug this library can have (it lets a transaction commit despite a conflicting write). Right now that behavior is only prevented by a one-line fix that no test in the repository would catch if it were accidentally reverted or refactored (the Node256 case of fixupMaxVersion is otherwise only guarded by #85-less fuzz coverage)."

`fixupMaxVersion` for `Node256` (`ConflictSet.cpp:2900-2931`) used to read `self256->childMaxVersion`, which `horizontalMax16` only scans 16 entries of, instead of the 16 pages of `self256->maxOfMax`. `4ef10b1` fixed that (line 2928) after the bug was evidently found by hand: the fuzz corpus does not catch it (#85). But neither does the scripted test that was written for exactly this code -- `test_conflict_set.py::test_fixup_256` (added by `1d9e8ab`, *"Add missing test coverage for fixupMaxVersion for Node256"*, `test_conflict_set.py:225-231`) -- so at the moment **no test in the tree detects a false `Commit` in `fixupMaxVersion` for `Node256`**; the fix is unverified by CI. ## Minimal reproducer (valid API usage, no invalid input) ```c++ // repro.cpp #include "ConflictSet.h" #include <cstdio> #include <vector> using namespace weaselab; int main() { ConflictSet cs{0}; std::vector<std::vector<uint8_t>> keys; std::vector<ConflictSet::WriteRange> w1; for (int b = 0; b < 256; ++b) { // makes a Node256 under "\x10" keys.push_back({0x10, (uint8_t)b}); w1.push_back({{keys.back().data(), 2}, {nullptr, 0}}); } cs.addWrites(w1.data(), (int)w1.size(), 1); // all 256 children at v1 std::vector<uint8_t> k = {0x10, 0x50}; // child index 0x50 >= 16 ConflictSet::WriteRange w2{{k.data(), 2}, {nullptr, 0}}; cs.addWrites(&w2, 1, 10); // high version, high child index std::vector<uint8_t> b0 = {0x05}, b1 = {0x10}; ConflictSet::WriteRange w3{{b0.data(), 1}, {b1.data(), 1}}; // range [0x05, 0x10) ends at the Node256 cs.addWrites(&w3, 1, 11); // write at v10 > 5 intersects {0x10,0x50} => postcondition requires Conflict ConflictSet::ReadRange r{{k.data(), 2}, {nullptr, 0}, 5}; ConflictSet::Result res = ConflictSet::TooOld; cs.check(&r, &res, 1); printf("result=%d (0=Commit 1=Conflict 2=TooOld) expected 1\n", (int)res); return res == ConflictSet::Conflict ? 0 : 1; } ``` ``` $ clang++ -std=c++20 -O1 -I include repro.cpp ConflictSet.cpp -isystem third_party/valgrind -o repro $ ./repro result=1 (0=Commit 1=Conflict 2=TooOld) expected 1 # HEAD (ba781b8): correct ``` Now revert only the fix in `ConflictSet.cpp:2928`: ```diff - max = std::max(max, horizontalMax16(self256->maxOfMax, writeContext->zero)); + max = std::max(max, horizontalMax16(self256->childMaxVersion, writeContext->zero)); ``` ``` $ ./repro result=0 (0=Commit 1=Conflict 2=TooOld) expected 1 # WRONG: reports Commit ``` The project's own invariant checker also sees it. Appending `checkCorrectness(cs.rootParent->children[0], cs.oldestVersion, &cs)` and running it after the third `addWrites` in a whitebox build prints, with the fix reverted: ``` x10 has max version 1 . Expected 10 ``` i.e. the `Node256` for `"\x10"` gets its max version clobbered from 10 down to 1 by `eraseInRange` -> `fixupMaxVersion` (`ConflictSet.cpp:2999`), because only children 0..15 were considered, and the high-version child is `0x50`. A later read is then short-circuited by the too-low `maxVersion` and returns `Commit` instead of `Conflict`. ## Why `test_fixup_256` misses it ```python def test_fixup_256(): # test_conflict_set.py:225 with DebugConflictSet() as cs: cs.addWrites(0, write(bytes([1]))) for i in range(256): cs.addWrites(1, write(bytes([1, i]))) cs.addWrites(2, write(bytes([0]), bytes([1]))) cs.check(read(0, bytes([1]), bytes([2]))) ``` It does build the right shape (a `Node256` whose key is the *end* of a range write), but every one of the 256 children is written at the *same* version (1). `max(childMaxVersion[0..15])` then equals `max(maxOfMax)`, so the buggy line and the fixed line compute the same value and the test cannot distinguish them. The bug only shows up when the highest-version child has an index >= 16 (the value `horizontalMax16` never looks at). Verified: with the one-line revert above, * `python3 test_conflict_set.py test fixup_256 --build-dir <reverted build>` -> passes (exit 0), * the whole corpus passes as well -- `fuzz_driver` (with `checkCorrectness`) and the blackbox `driver` over all 2845 files in `corpus/`: 0 failures. ## Suggested test (verified to fail on the buggy code, pass on HEAD) ```python def test_fixup_256_heterogeneous_versions(): with DebugConflictSet() as cs: for i in range(256): cs.addWrites(1, write(bytes([0x10, i]))) cs.addWrites(10, write(bytes([0x10, 0x50]))) # high version, child index >= 16 cs.addWrites(11, write(bytes([0x05]), bytes([0x10]))) # range ends at the Node256 assert cs.check(read(5, bytes([0x10, 0x50]))) == [Result.CONFLICT] ``` Against the reverted (buggy) library this fails in `DebugConflictSet.check` (`test_conflict_set.py:28`, `AssertionError`: radix tree says `Commit`, skip list says `Conflict`); against HEAD it passes. ## Relation to #85 #85 ("Enhance fuzz tests to cover Node256 better / We should be able to catch 0814822 in the fuzz tests") is about the corpus. This report is about the *scripted* test that was added specifically "for fixupMaxVersion for Node256" (`1d9e8ab`), which silently does not exercise the bug, and it offers the minimal input that does (usable both as a corpus seed and as a `test_conflict_set.py` case). Since `0814822` introduced the bug *after* `test_fixup_256` was written, the test never had a chance to fail; it should be strengthened rather than trusted as coverage of this code. ## Impact A wrong `Commit` for a conflicting read is the worst kind of bug this library can have (it lets a transaction commit despite a conflicting write). Right now that behavior is only prevented by a one-line fix that no test in the repository would catch if it were accidentally reverted or refactored (the `Node256` case of `fixupMaxVersion` is otherwise only guarded by `#85`-less fuzz coverage)."

weaselbot was assigned by andrew

2026-10-26 21:33:57 +00:00

weaselbot referenced a pull request that will close this issue

2026-10-26 22:20:51 +00:00

Replace test_fixup_256 with a regression test for the Node256 fixupMaxVersion false-Commit bug #90

andrew closed this issue

2026-10-27 19:33:21 +00:00

Sign in to join this conversation.