checkMaxVersion looks every node's successor up from the root's search path, so its maxVersion "borrowed range version" check never runs (and enabling it SEGVs in firstGeqLogical)
#95
checkMaxVersion() (ConflictSet.cpp:5914-5948) is the invariant checker that the fuzz/corpus suite runs after everyTestDriver::next() (LLVMFuzzerTestOneInput, ConflictSet.cpp:6280-6296). It is the only automated check of the maxVersion invariant documented at ConflictSet.cpp:2975-2978.
It is given the tree root (root) and the node being verified (node), and derives the key it searches for from the root's search path:
instead of getSearchPath(node). getSearchPath() of the tree root is always the empty string (ConflictSet.cpp:2665-2682 pops the implicit rootParent byte and stops), and strinc("", ok) sets ok = false (ConflictSet.cpp:5779-5790: "the empty string has no successor"). So the if (ok) block at ConflictSet.cpp:5934-5939 — the part that accounts for the range version of the first key after the node's subtree — never executes, for any node, on any input. It is dead code, and has been since it was introduced in 9363d78 ("Specify maxVersion meaning"), where the diff makes the intent clear (checkMaxVersion(Node *root, Node *node, ...) plus the new getSearchPath(root)/strinc/firstGeq block; root was meant to be the search base, node the key source).
The same block is also the only caller of firstGeqLogical() (ConflictSet.cpp:5596-5650), which is therefore also dead — and broken (see below).
strinc("") returning ok=false is easy to confirm in isolation:
strinc("") -> ok=0
strinc("ab") -> ok=1 r=ac
checkCorrectness() is only ever called with the tree root (ConflictSet.cpp:6021 calls checkMaxVersion(node, node, ...)), and the recursion at ConflictSet.cpp:5926 threads root through unchanged, so getSearchPath(root) == "" in every recursive call.
2. Enabling the check SEGVs inside firstGeqLogical()
Change only the lookup key:
sed -i 's/getSearchPath(root)/getSearchPath(node)/' ConflictSet.cpp
then run the fuzz driver on any corpus input (here corpus/003fdafe6e5f359e1043927b266e6ed6193562bc):
ConflictSet.cpp:5648:14: runtime error: member access within null pointer of type 'Node'
AddressSanitizer: SEGV on unknown address 0x000000000016
#0 firstGeqLogical(Node*, TrivialSpan) ConflictSet.cpp:5648:14
#1 firstGeq(Node*, std::string_view) ConflictSet.cpp:5862:10
#2 checkMaxVersion(...) ConflictSet.cpp:5935:21
firstGeqLogical() requires the key to have a successor; when the search key sorts after every key in the tree it returns nullptr from the branch at ConflictSet.cpp:5614-5618, but the equivalent branch for a diverging partial key does not:
// ConflictSet.cpp:5628-5636
if(i<commonLen){autoc=n->partialKey()[i]<=>remaining[i];if(c>0){gotodownLeftSpine;}else{n=nextSibling(n);// can be nullptr
gotodownLeftSpine;// -> `for (; !n->entryPresent; ...)` dereferences null
}}
(Minimal shape: keys "" and "abX" in the tree, search key "abZ" — the node for "abX" has a partial key that compares less, and it is the last node.)
With both defects fixed (use getSearchPath(node), plus the missing nullptr check), all 2845corpus/ inputs pass, so the invariant does hold and the check is safe to enable — it just has never been enabled.
Reproduction
cmake -S . -B build -G Ninja -DCMAKE_BUILD_TYPE=Debug -DCMAKE_CXX_COMPILER=clang++
ninja -C build fuzz_driver
# current code: passes (and silently skips the borrowed-rangeVersion check)
./build/fuzz_driver corpus/003fdafe6e5f359e1043927b266e6ed6193562bc ;echo$?# 0# fix the lookup key only: now the check actually runs, and crashes
sed -i 's/getSearchPath(root)/getSearchPath(node)/' ConflictSet.cpp
ninja -C build fuzz_driver
./build/fuzz_driver corpus/003fdafe6e5f359e1043927b266e6ed6193562bc # SEGV
Impact
The corpus/fuzz suite (conflict_set_fuzz_*, plus the libFuzzer target) has, for every node of every test input since Feb 2024, verified only maxVersion(node) == max(oldestVersion, pointVersion/rangeVersion of the subtree). The term that the code was written to validate — the range version contributed by the first key after the node's subtree — is never checked. That is exactly the quantity fixupMaxVersion() must restore after eraseInRange() has erased a subtree ("Inserting end trashed the last node's maxVersion. Fix that.", ConflictSet.cpp:3080-3082), and getting it wrong produces a false Commit, i.e. a silently missed conflict (the bug class of #89).
firstGeqLogical() is broken (null dereference on valid input) and has never been executed, so it has bit-rotted unnoticed. Anyone who fixes the search path gets a crash instead of a check.
Because the whole tail of the file is // GCOVR_EXCL_START (ConflictSet.cpp:5594), the 100%-line-coverage requirement in CI cannot flag the dead code.
(Not a duplicate of #89: that one is about fixupMaxVersion's own recomputation and now has a scripted regression test; this is the checker itself never running.)
## Summary
`checkMaxVersion()` (ConflictSet.cpp:5914-5948) is the invariant checker that the fuzz/corpus suite runs after **every** `TestDriver::next()` (`LLVMFuzzerTestOneInput`, ConflictSet.cpp:6280-6296). It is the only automated check of the `maxVersion` invariant documented at ConflictSet.cpp:2975-2978.
It is given the tree root (`root`) and the node being verified (`node`), and derives the key it searches for from the **root's** search path:
```c++
// ConflictSet.cpp:5931
auto key = getSearchPath(root);
```
instead of `getSearchPath(node)`. `getSearchPath()` of the tree root is always the empty string (ConflictSet.cpp:2665-2682 pops the implicit rootParent byte and stops), and `strinc("", ok)` sets `ok = false` (ConflictSet.cpp:5779-5790: *"the empty string has no successor"*). So the `if (ok)` block at ConflictSet.cpp:5934-5939 — the part that accounts for the range version of the first key *after* the node's subtree — **never executes, for any node, on any input**. It is dead code, and has been since it was introduced in 9363d78 ("Specify maxVersion meaning"), where the diff makes the intent clear (`checkMaxVersion(Node *root, Node *node, ...)` plus the new `getSearchPath(root)`/`strinc`/`firstGeq` block; `root` was meant to be the search base, `node` the key source).
The same block is also the only caller of `firstGeqLogical()` (ConflictSet.cpp:5596-5650), which is therefore also dead — and broken (see below).
## Evidence
### 1. The lookup key is always `""`
Instrumenting the unmodified `checkMaxVersion` with
```c++
fprintf(stderr, "checkMaxVersion: root path=%s node path=%s\n",
printable(getSearchPath(root)).c_str(), printable(getSearchPath(node)).c_str());
```
and running the fuzz driver on a corpus input prints, e.g.:
```
checkMaxVersion: root path=<empty> node path=x7ax7ax7a...x00x08
checkMaxVersion: root path=<empty> node path=x7ax7ax7a...x00
strinc failed: borrowed check skipped
```
`strinc("")` returning `ok=false` is easy to confirm in isolation:
```
strinc("") -> ok=0
strinc("ab") -> ok=1 r=ac
```
`checkCorrectness()` is only ever called with the tree root (ConflictSet.cpp:6021 calls `checkMaxVersion(node, node, ...)`), and the recursion at ConflictSet.cpp:5926 threads `root` through unchanged, so `getSearchPath(root) == ""` in every recursive call.
### 2. Enabling the check SEGVs inside `firstGeqLogical()`
Change only the lookup key:
```sh
sed -i 's/getSearchPath(root)/getSearchPath(node)/' ConflictSet.cpp
```
then run the fuzz driver on any corpus input (here `corpus/003fdafe6e5f359e1043927b266e6ed6193562bc`):
```
ConflictSet.cpp:5648:14: runtime error: member access within null pointer of type 'Node'
AddressSanitizer: SEGV on unknown address 0x000000000016
#0 firstGeqLogical(Node*, TrivialSpan) ConflictSet.cpp:5648:14
#1 firstGeq(Node*, std::string_view) ConflictSet.cpp:5862:10
#2 checkMaxVersion(...) ConflictSet.cpp:5935:21
```
`firstGeqLogical()` requires the key to have a successor; when the search key sorts after every key in the tree it returns `nullptr` from the branch at ConflictSet.cpp:5614-5618, but the equivalent branch for a diverging partial key does not:
```c++
// ConflictSet.cpp:5628-5636
if (i < commonLen) {
auto c = n->partialKey()[i] <=> remaining[i];
if (c > 0) {
goto downLeftSpine;
} else {
n = nextSibling(n); // can be nullptr
goto downLeftSpine; // -> `for (; !n->entryPresent; ...)` dereferences null
}
}
```
(Minimal shape: keys `""` and `"abX"` in the tree, search key `"abZ"` — the node for `"abX"` has a partial key that compares less, and it is the last node.)
With both defects fixed (use `getSearchPath(node)`, plus the missing `nullptr` check), **all 2845** `corpus/` inputs pass, so the invariant does hold and the check is safe to enable — it just has never been enabled.
## Reproduction
```sh
cmake -S . -B build -G Ninja -DCMAKE_BUILD_TYPE=Debug -DCMAKE_CXX_COMPILER=clang++
ninja -C build fuzz_driver
# current code: passes (and silently skips the borrowed-rangeVersion check)
./build/fuzz_driver corpus/003fdafe6e5f359e1043927b266e6ed6193562bc ; echo $? # 0
# fix the lookup key only: now the check actually runs, and crashes
sed -i 's/getSearchPath(root)/getSearchPath(node)/' ConflictSet.cpp
ninja -C build fuzz_driver
./build/fuzz_driver corpus/003fdafe6e5f359e1043927b266e6ed6193562bc # SEGV
```
## Impact
* The corpus/fuzz suite (`conflict_set_fuzz_*`, plus the libFuzzer target) has, for every node of every test input since Feb 2024, verified only `maxVersion(node) == max(oldestVersion, pointVersion/rangeVersion of the subtree)`. The term that the code was written to validate — the range version contributed by the first key after the node's subtree — is never checked. That is exactly the quantity `fixupMaxVersion()` must restore after `eraseInRange()` has erased a subtree ("Inserting end trashed the last node's maxVersion. Fix that.", ConflictSet.cpp:3080-3082), and getting it wrong produces a **false `Commit`**, i.e. a silently missed conflict (the bug class of #89).
* `firstGeqLogical()` is broken (null dereference on valid input) and has never been executed, so it has bit-rotted unnoticed. Anyone who fixes the search path gets a crash instead of a check.
* Because the whole tail of the file is `// GCOVR_EXCL_START` (ConflictSet.cpp:5594), the 100%-line-coverage requirement in CI cannot flag the dead code.
## Suggested fix
```c++
- auto key = getSearchPath(root);
+ auto key = getSearchPath(node);
```
and, in `firstGeqLogical()` (ConflictSet.cpp:5628-5636):
```c++
} else {
n = nextSibling(n);
+ if (n == nullptr) {
+ return nullptr;
+ }
goto downLeftSpine;
}
```
(Not a duplicate of #89: that one is about `fixupMaxVersion`'s own recomputation and now has a scripted regression test; this is the checker itself never running.)
weaselbot
was assigned by andrew2026-11-10 19:15:30 +00:00
Blocking a user prevents them from interacting with repositories, such as opening or commenting on pull requests or issues. Learn more about blocking a user.
Summary
checkMaxVersion()(ConflictSet.cpp:5914-5948) is the invariant checker that the fuzz/corpus suite runs after everyTestDriver::next()(LLVMFuzzerTestOneInput, ConflictSet.cpp:6280-6296). It is the only automated check of themaxVersioninvariant documented at ConflictSet.cpp:2975-2978.It is given the tree root (
root) and the node being verified (node), and derives the key it searches for from the root's search path:instead of
getSearchPath(node).getSearchPath()of the tree root is always the empty string (ConflictSet.cpp:2665-2682 pops the implicit rootParent byte and stops), andstrinc("", ok)setsok = false(ConflictSet.cpp:5779-5790: "the empty string has no successor"). So theif (ok)block at ConflictSet.cpp:5934-5939 — the part that accounts for the range version of the first key after the node's subtree — never executes, for any node, on any input. It is dead code, and has been since it was introduced in9363d78("Specify maxVersion meaning"), where the diff makes the intent clear (checkMaxVersion(Node *root, Node *node, ...)plus the newgetSearchPath(root)/strinc/firstGeqblock;rootwas meant to be the search base,nodethe key source).The same block is also the only caller of
firstGeqLogical()(ConflictSet.cpp:5596-5650), which is therefore also dead — and broken (see below).Evidence
1. The lookup key is always
""Instrumenting the unmodified
checkMaxVersionwithand running the fuzz driver on a corpus input prints, e.g.:
strinc("")returningok=falseis easy to confirm in isolation:checkCorrectness()is only ever called with the tree root (ConflictSet.cpp:6021 callscheckMaxVersion(node, node, ...)), and the recursion at ConflictSet.cpp:5926 threadsrootthrough unchanged, sogetSearchPath(root) == ""in every recursive call.2. Enabling the check SEGVs inside
firstGeqLogical()Change only the lookup key:
then run the fuzz driver on any corpus input (here
corpus/003fdafe6e5f359e1043927b266e6ed6193562bc):firstGeqLogical()requires the key to have a successor; when the search key sorts after every key in the tree it returnsnullptrfrom the branch at ConflictSet.cpp:5614-5618, but the equivalent branch for a diverging partial key does not:(Minimal shape: keys
""and"abX"in the tree, search key"abZ"— the node for"abX"has a partial key that compares less, and it is the last node.)With both defects fixed (use
getSearchPath(node), plus the missingnullptrcheck), all 2845corpus/inputs pass, so the invariant does hold and the check is safe to enable — it just has never been enabled.Reproduction
Impact
conflict_set_fuzz_*, plus the libFuzzer target) has, for every node of every test input since Feb 2024, verified onlymaxVersion(node) == max(oldestVersion, pointVersion/rangeVersion of the subtree). The term that the code was written to validate — the range version contributed by the first key after the node's subtree — is never checked. That is exactly the quantityfixupMaxVersion()must restore aftereraseInRange()has erased a subtree ("Inserting end trashed the last node's maxVersion. Fix that.", ConflictSet.cpp:3080-3082), and getting it wrong produces a falseCommit, i.e. a silently missed conflict (the bug class of #89).firstGeqLogical()is broken (null dereference on valid input) and has never been executed, so it has bit-rotted unnoticed. Anyone who fixes the search path gets a crash instead of a check.// GCOVR_EXCL_START(ConflictSet.cpp:5594), the 100%-line-coverage requirement in CI cannot flag the dead code.Suggested fix
and, in
firstGeqLogical()(ConflictSet.cpp:5628-5636):(Not a duplicate of #89: that one is about
fixupMaxVersion's own recomputation and now has a scripted regression test; this is the checker itself never running.)