SkipList::Impl::setOldestVersion asserted that its argument was monotonically
non-decreasing and otherwise lowered oldestVersion. The documented contract
(include/ConflictSet.h) is that oldestVersion becomes the maximum of its
previous value and the argument, so passing an older version is valid input and
must leave oldestVersion unchanged.
Effects: Debug builds abort on valid input, and with NDEBUG builds report Commit/Conflict for reads in a version window the caller was told is
expired (those entries may already have been garbage collected).
Fix
SkipList.cpp: return early when the argument isn't newer than the current oldestVersion, mirroring HashTable.cpp. The < (rather than <=) keeps
the previous behaviour of doing garbage collection work on an equal version,
which is safe: it only removes entries strictly older than oldestVersion, and
it does not advance oldestVersion.
Tests
test_conflict_set.py: new test_setOldestVersion_does_not_decrease
regression test, run through DebugConflictSet so it bisimulates skip_list
against the radix tree. It covers both the plain case and the case where the
write at the old oldestVersion has already been garbage collected. It fails
(abort in Debug, mismatch in Release) before the fix and passes after.
CMakeLists.txt: the driver_skip_list corpus tests were behind if(0),
i.e. never run. Per review feedback they are not enabled by default (they
would slow down every ctest run); instead they are gated behind a new TEST_SKIP_LIST CMake option, off by default. Run them with cmake -B build -DTEST_SKIP_LIST=ON to cross-check SkipList.cpp against ReferenceImpl.
Verification
Debug build (gcc 16.1.1, aarch64): full ctest suite passes (8600 tests, skip_list_* absent by default).
Release build with -DTEST_SKIP_LIST=ON: all 2845 skip_list_* corpus tests
pass (11447 tests total).
The issue's repro.c now reports TooOld (2) for skip_list in both Debug and
Release builds, matching radix_tree and hash_table.
Closes #87
## Problem
`SkipList::Impl::setOldestVersion` asserted that its argument was monotonically
non-decreasing and otherwise lowered `oldestVersion`. The documented contract
(`include/ConflictSet.h`) is that `oldestVersion` becomes the maximum of its
previous value and the argument, so passing an older version is valid input and
must leave `oldestVersion` unchanged.
Effects: Debug builds abort on valid input, and with `NDEBUG` builds report
`Commit`/`Conflict` for reads in a version window the caller was told is
expired (those entries may already have been garbage collected).
## Fix
`SkipList.cpp`: return early when the argument isn't newer than the current
`oldestVersion`, mirroring `HashTable.cpp`. The `<` (rather than `<=`) keeps
the previous behaviour of doing garbage collection work on an equal version,
which is safe: it only removes entries strictly older than `oldestVersion`, and
it does not advance `oldestVersion`.
## Tests
* `test_conflict_set.py`: new `test_setOldestVersion_does_not_decrease`
regression test, run through `DebugConflictSet` so it bisimulates skip_list
against the radix tree. It covers both the plain case and the case where the
write at the old `oldestVersion` has already been garbage collected. It fails
(abort in Debug, mismatch in Release) before the fix and passes after.
* `CMakeLists.txt`: the `driver_skip_list` corpus tests were behind `if(0)`,
i.e. never run. Per review feedback they are not enabled by default (they
would slow down every `ctest` run); instead they are gated behind a new
`TEST_SKIP_LIST` CMake option, off by default. Run them with
`cmake -B build -DTEST_SKIP_LIST=ON` to cross-check `SkipList.cpp` against
`ReferenceImpl`.
## Verification
* Debug build (gcc 16.1.1, aarch64): full `ctest` suite passes (8600 tests,
`skip_list_*` absent by default).
* Release build with `-DTEST_SKIP_LIST=ON`: all 2845 `skip_list_*` corpus tests
pass (11447 tests total).
* The issue's `repro.c` now reports `TooOld` (2) for skip_list in both Debug and
Release builds, matching radix_tree and hash_table.
setOldestVersion is documented to set oldestVersion to the maximum of its
previous value and its argument, so passing a version older than the
current oldestVersion is valid input. SkipList.cpp instead asserted that
the argument was monotonically non-decreasing, aborting Debug builds, and
with NDEBUG it lowered oldestVersion. That resurrected a window of
versions that callers had been told result in TooOld: reads in that
window were evaluated against entries that may already have been garbage
collected, so they could report Commit or Conflict instead.
Leave oldestVersion alone when the argument isn't newer, mirroring
HashTable.cpp. Falling through on equality keeps garbage collection
making progress without advancing the oldest version.
Add a scripted regression test, which bisimulates against the radix tree.
CI / test (arm64, -DCMAKE_BUILD_TYPE=Debug -DMSAN_TOOLCHAIN_PATH=/opt/msan, 22, https://minio.weaselab.dev/public/aarch64/msan-toolchain-22.1.8.tar.zst, debug-arm64, ubuntu-latest-arm64) (pull_request) Successful in 3m50s
CI / test (amd64, -DCMAKE_BUILD_TYPE=Debug -DMSAN_TOOLCHAIN_PATH=/opt/msan, 21, https://minio.weaselab.dev/public/x86_64/msan-toolchain-21.1.8.tar.zst, debug, ubuntu-latest-amd64) (pull_request) Successful in 4m12s
driver_skip_list checks SkipList.cpp against ReferenceImpl, but its tests
were disabled, so the implementation diverged from the documented API
without anything noticing. The corpus tests pass in Debug and Release
builds, so run them like the other implementations' tests.
CI / test (arm64, -DCMAKE_BUILD_TYPE=Debug -DMSAN_TOOLCHAIN_PATH=/opt/msan, 22, https://minio.weaselab.dev/public/aarch64/msan-toolchain-22.1.8.tar.zst, debug-arm64, ubuntu-latest-arm64) (pull_request) Successful in 3m50s
CI / test (amd64, -DCMAKE_BUILD_TYPE=Debug -DMSAN_TOOLCHAIN_PATH=/opt/msan, 21, https://minio.weaselab.dev/public/x86_64/msan-toolchain-21.1.8.tar.zst, debug, ubuntu-latest-amd64) (pull_request) Successful in 8m0s
Review feedback: running the skip list tests on every default ctest run is a
waste of time. Gate them behind a TEST_SKIP_LIST CMake option, off by default,
so they remain easy to run when cross-checking SkipList.cpp against
ReferenceImpl.
Verified with -DTEST_SKIP_LIST=ON: all 2845 skip_list corpus tests pass; the
default test list is unchanged.
andrew
merged commit fa1701479c into main2026-10-27 19:30:12 +00:00
andrew
deleted branch weaselbot/issue-872026-10-27 19:30:15 +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.
andrew
Closes #87
Problem
SkipList::Impl::setOldestVersionasserted that its argument was monotonicallynon-decreasing and otherwise lowered
oldestVersion. The documented contract(
include/ConflictSet.h) is thatoldestVersionbecomes the maximum of itsprevious value and the argument, so passing an older version is valid input and
must leave
oldestVersionunchanged.Effects: Debug builds abort on valid input, and with
NDEBUGbuilds reportCommit/Conflictfor reads in a version window the caller was told isexpired (those entries may already have been garbage collected).
Fix
SkipList.cpp: return early when the argument isn't newer than the currentoldestVersion, mirroringHashTable.cpp. The<(rather than<=) keepsthe previous behaviour of doing garbage collection work on an equal version,
which is safe: it only removes entries strictly older than
oldestVersion, andit does not advance
oldestVersion.Tests
test_conflict_set.py: newtest_setOldestVersion_does_not_decreaseregression test, run through
DebugConflictSetso it bisimulates skip_listagainst the radix tree. It covers both the plain case and the case where the
write at the old
oldestVersionhas already been garbage collected. It fails(abort in Debug, mismatch in Release) before the fix and passes after.
CMakeLists.txt: thedriver_skip_listcorpus tests were behindif(0),i.e. never run. Per review feedback they are not enabled by default (they
would slow down every
ctestrun); instead they are gated behind a newTEST_SKIP_LISTCMake option, off by default. Run them withcmake -B build -DTEST_SKIP_LIST=ONto cross-checkSkipList.cppagainstReferenceImpl.Verification
ctestsuite passes (8600 tests,skip_list_*absent by default).-DTEST_SKIP_LIST=ON: all 2845skip_list_*corpus testspass (11447 tests total).
repro.cnow reportsTooOld(2) for skip_list in both Debug andRelease builds, matching radix_tree and hash_table.
@@ -231,3 +227,1 @@add_test(NAME skip_list_${hash} COMMAND driver_skip_list ${TEST})endforeach()endif()# skip list tests, which cross-check SkipList.cpp against ReferenceImplWe don't want to run the skip list tests every time by default. That's a waste of time