SkipList::Impl::setOldestVersion (SkipList.cpp:821-826) assumes its argument is monotonically non-decreasing:
voidsetOldestVersion(int64_toldestVersion){// This isn't 100% accurate. It overcounts if you hit the end
gc_iterations_total.add(keyUpdates);assert(oldestVersion>=this->oldestVersion);// SkipList.cpp:825
this->oldestVersion=oldestVersion;// SkipList.cpp:826
That is not the documented contract. include/ConflictSet.h:93-97 (and the C declaration at include/ConflictSet.h:241-245):
/** Reads where readVersion < `oldestVersion` will result in `TooOld`.
* @pre `oldestVersion >= 0` and `oldestVersion <= newestVersion`.
* @post `oldestVersion` becomes the maximum of its previous value and the
* argument; `newestVersion` is unchanged. */
void setOldestVersion(int64_t oldestVersion);
So passing a version older than the current oldestVersion is valid input, and oldestVersion must be left unchanged. The other two implementations in the tree do exactly that (ConflictSet.cpp:5257-5263 and HashTable.cpp:50-53), and the main implementation explicitly documents that addWrites can legitimately auto-advance oldestVersion past a value an application later passes. SkipList.cpp instead asserts in Debug builds and, with -DNDEBUG, lowersoldestVersion, so later checks return Conflict/Commit where the API requires TooOld.
Reproducer
repro.c (plain C, C API — same three calls for every implementation):
The repository's own bisimulation harness aborts the same way, because test_conflict_set.py's DebugConflictSet uses skip_list as the oracle compared against radix_tree:
withDebugConflictSet()ascs:cs.addWrites(5,write(b"k"))cs.setOldestVersion(5)cs.setOldestVersion(2)# valid per the documented postconditioncs.check(read(3,b"k"))# -> Assertion `oldestVersion >= this->oldestVersion' failed (SkipList.cpp:825)
Impact
Debug/asserted builds: an abort (process crash) on valid input.
Release builds: silently wrong results. After the lowering, every read with oldestVersion_new <= readVersion < oldestVersion_old is evaluated instead of reporting TooOld. Because entries at or below the old oldestVersion may already have been garbage-collected, such reads can be reported as Commit/Conflict from a window the caller was told to consider expired — precisely the failure mode TooOld exists to prevent.
skip_list is not only benchmark code: test_conflict_set.py (DebugConflictSet) uses it as the reference oracle for the radix tree, so this divergence can also make the scripted test suite abort or report spurious mismatches as soon as any test uses the documented behaviour.
Why it went unnoticed
driver_skip_list's corpus tests are disabled in CMakeLists.txt (if(0) at line 228), so SkipList.cpp is never run against ReferenceImpl, and every existing scripted test happens to increase oldestVersion monotonically.
Suggested fix
Clamp instead of assert, mirroring HashTable.cpp:50-53:
and consider enabling the driver_skip_list tests so the two implementations are actually cross-checked.
## Summary
`SkipList::Impl::setOldestVersion` (`SkipList.cpp:821-826`) assumes its argument is monotonically non-decreasing:
```cpp
void setOldestVersion(int64_t oldestVersion) {
// This isn't 100% accurate. It overcounts if you hit the end
gc_iterations_total.add(keyUpdates);
assert(oldestVersion >= this->oldestVersion); // SkipList.cpp:825
this->oldestVersion = oldestVersion; // SkipList.cpp:826
```
That is not the documented contract. `include/ConflictSet.h:93-97` (and the C declaration at `include/ConflictSet.h:241-245`):
```
/** Reads where readVersion < `oldestVersion` will result in `TooOld`.
* @pre `oldestVersion >= 0` and `oldestVersion <= newestVersion`.
* @post `oldestVersion` becomes the maximum of its previous value and the
* argument; `newestVersion` is unchanged. */
void setOldestVersion(int64_t oldestVersion);
```
So passing a version *older* than the current `oldestVersion` is valid input, and `oldestVersion` must be left unchanged. The other two implementations in the tree do exactly that (`ConflictSet.cpp:5257-5263` and `HashTable.cpp:50-53`), and the main implementation explicitly documents that `addWrites` can legitimately auto-advance `oldestVersion` past a value an application later passes. `SkipList.cpp` instead asserts in Debug builds and, with `-DNDEBUG`, *lowers* `oldestVersion`, so later checks return `Conflict`/`Commit` where the API requires `TooOld`.
## Reproducer
`repro.c` (plain C, C API — same three calls for every implementation):
```c
#include "ConflictSet.h"
#include <stdio.h>
int main(void) {
ConflictSet *cs = ConflictSet_create(0);
ConflictSet_WriteRange w;
ConflictSet_ReadRange r;
ConflictSet_Result res = ConflictSet_Commit;
w.begin.p = (const uint8_t *)"k"; w.begin.len = 1;
w.end.p = NULL; w.end.len = 0;
ConflictSet_addWrites(cs, &w, 1, 5); /* newestVersion = 5 */
ConflictSet_setOldestVersion(cs, 5); /* oldestVersion = 5 */
/* Valid: pre(2 >= 0, 2 <= 5); post: oldestVersion = max(5, 2) = 5. */
ConflictSet_setOldestVersion(cs, 2);
r.begin.p = (const uint8_t *)"k"; r.begin.len = 1;
r.end.p = NULL; r.end.len = 0;
r.readVersion = 3; /* 3 < 5 => must be TooOld */
ConflictSet_check(cs, &r, &res, 1);
printf("result=%d (Commit=0 Conflict=1 TooOld=2)\n", (int)res);
ConflictSet_destroy(cs);
return 0;
}
```
Observed (commit `ba781b8`, aarch64, gcc 16.1.1):
```
$ gcc -std=c90 -Iinclude repro.c -o repro -Lbuild-rel/<impl> -lconflict-set
$ LD_LIBRARY_PATH=build-rel/<impl> ./repro
radix_tree : result=2 (TooOld) <- correct
hash_table : result=2 (TooOld) <- correct
skip_list : result=1 (Conflict) <- wrong, oldestVersion was lowered to 2
```
Same program against the `Debug` build of skip_list (asserts enabled):
```
$ LD_LIBRARY_PATH=build/skip_list ./repro
repro: .../SkipList.cpp:825: void weaselab::ConflictSet::Impl::setOldestVersion(int64_t):
Assertion `oldestVersion >= this->oldestVersion' failed.
Aborted (core dumped) (exit 134)
```
The repository's own bisimulation harness aborts the same way, because `test_conflict_set.py`'s `DebugConflictSet` uses skip_list as the oracle compared against radix_tree:
```python
with DebugConflictSet() as cs:
cs.addWrites(5, write(b"k"))
cs.setOldestVersion(5)
cs.setOldestVersion(2) # valid per the documented postcondition
cs.check(read(3, b"k"))
# -> Assertion `oldestVersion >= this->oldestVersion' failed (SkipList.cpp:825)
```
## Impact
* Debug/asserted builds: an abort (process crash) on valid input.
* Release builds: silently wrong results. After the lowering, every read with `oldestVersion_new <= readVersion < oldestVersion_old` is evaluated instead of reporting `TooOld`. Because entries at or below the old `oldestVersion` may already have been garbage-collected, such reads can be reported as `Commit`/`Conflict` from a window the caller was told to consider expired — precisely the failure mode `TooOld` exists to prevent.
* skip_list is not only benchmark code: `test_conflict_set.py` (`DebugConflictSet`) uses it as the reference oracle for the radix tree, so this divergence can also make the scripted test suite abort or report spurious mismatches as soon as any test uses the documented behaviour.
## Why it went unnoticed
`driver_skip_list`'s corpus tests are disabled in `CMakeLists.txt` (`if(0)` at line 228), so `SkipList.cpp` is never run against `ReferenceImpl`, and every existing scripted test happens to increase `oldestVersion` monotonically.
## Suggested fix
Clamp instead of assert, mirroring `HashTable.cpp:50-53`:
```cpp
void setOldestVersion(int64_t oldestVersion) {
if (oldestVersion <= this->oldestVersion) {
return; // post: oldestVersion = max(previous value, argument)
}
gc_iterations_total.add(keyUpdates);
this->oldestVersion = oldestVersion;
... unchanged ...
}
```
and consider enabling the `driver_skip_list` tests so the two implementations are actually cross-checked.
weaselbot
was assigned by andrew2026-10-26 21:35:06 +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
SkipList::Impl::setOldestVersion(SkipList.cpp:821-826) assumes its argument is monotonically non-decreasing:That is not the documented contract.
include/ConflictSet.h:93-97(and the C declaration atinclude/ConflictSet.h:241-245):So passing a version older than the current
oldestVersionis valid input, andoldestVersionmust be left unchanged. The other two implementations in the tree do exactly that (ConflictSet.cpp:5257-5263andHashTable.cpp:50-53), and the main implementation explicitly documents thataddWritescan legitimately auto-advanceoldestVersionpast a value an application later passes.SkipList.cppinstead asserts in Debug builds and, with-DNDEBUG, lowersoldestVersion, so later checks returnConflict/Commitwhere the API requiresTooOld.Reproducer
repro.c(plain C, C API — same three calls for every implementation):Observed (commit
ba781b8, aarch64, gcc 16.1.1):Same program against the
Debugbuild of skip_list (asserts enabled):The repository's own bisimulation harness aborts the same way, because
test_conflict_set.py'sDebugConflictSetuses skip_list as the oracle compared against radix_tree:Impact
oldestVersion_new <= readVersion < oldestVersion_oldis evaluated instead of reportingTooOld. Because entries at or below the oldoldestVersionmay already have been garbage-collected, such reads can be reported asCommit/Conflictfrom a window the caller was told to consider expired — precisely the failure modeTooOldexists to prevent.test_conflict_set.py(DebugConflictSet) uses it as the reference oracle for the radix tree, so this divergence can also make the scripted test suite abort or report spurious mismatches as soon as any test uses the documented behaviour.Why it went unnoticed
driver_skip_list's corpus tests are disabled inCMakeLists.txt(if(0)at line 228), soSkipList.cppis never run againstReferenceImpl, and every existing scripted test happens to increaseoldestVersionmonotonically.Suggested fix
Clamp instead of assert, mirroring
HashTable.cpp:50-53:and consider enabling the
driver_skip_listtests so the two implementations are actually cross-checked.