skip_list: newestVersion - 2e9 is computed in double precision, so the TooOld window boundary is wrong for versions >= 2^53 (Commit instead of TooOld); the test oracle in Internal.h has the same bug #99

New Issue

Open

opened 2026-11-08 13:45:41 +00:00 by weaselbot · 0 comments

weaselbot commented 2026-11-08 13:45:41 +00:00

Member

Copy link

Copy source

Summary

SkipList.cpp:744 decides TooOld for reads that fell out of the two-billion-version window with

if (reads[i].readVersion < oldestVersion ||
    reads[i].readVersion < newestVersion - 2e9) {   // SkipList.cpp:743-744
  results[i] = TooOld;
}

2e9 is a double literal, so newestVersion - 2e9 is evaluated in double (the int64_t operand is converted, and readVersion is converted for the comparison). A double has a 53-bit mantissa, so for any newestVersion >= 2^53 the boundary is off by up to ~512 versions, in both directions. The result is that check() returns Commit for reads that the API says must be TooOld, and TooOld for reads that are exactly at the boundary and must not be.

The radix tree gets this right because it keeps the window as an integer (ConflictSet.cpp:99, constexpr int64_t kNominalVersionWindow = 2e9;, used at ConflictSet.cpp:5178-5192), so the two shipped implementations disagree on the same valid input.

Internal.h:516 (ReferenceImpl::check, the test oracle used by TestDriver/the corpus driver) contains the identical expression, so the differential tests share the defect and cannot catch it (and would flag the correct radix tree if the corpus ever produced such versions).

Reproduction

Same 3-operation program, linked against each shipped implementation:

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

int main() {
  const int64_t newest = (int64_t(1) << 53) + 1;        // >= 0, so valid input
  const int64_t readVersion = newest - 2000000000 - 1;  // 1 below the window
  const char *name[] = {"Commit", "Conflict", "TooOld"};

  ConflictSet cs{0};
  cs.addWrites(nullptr, 0, newest);  // count == 0: no write, newestVersion advances
  ConflictSet::ReadRange r{{(const uint8_t *)"k", 1}, {nullptr, 0}, readVersion};
  ConflictSet::Result result = ConflictSet::Conflict;
  cs.check(&r, &result, 1);

  printf("newest=%lld readVersion=%lld newest-2e9=%lld -> %s (expected TooOld)\n",
         (long long)newest, (long long)readVersion,
         (long long)(newest - 2000000000), name[int(result)]);
  return result == ConflictSet::TooOld ? 0 : 1;
}

$ cmake -S . -B build -G Ninja -DCMAKE_BUILD_TYPE=Debug -DCMAKE_CXX_COMPILER=clang++ && ninja -C build
$ for impl in radix_tree skip_list; do
    g++ -std=c++20 -O1 -Iinclude -I. -isystem third_party/valgrind -o repro_$impl repro.cpp \
        -L$PWD/build/$impl -lconflict-set -Wl,-rpath,$PWD/build/$impl
    ./repro_$impl ; echo "  exit=$?"
  done

Observed:

radix_tree  newest=9007199254740993 readVersion=9007197254740992 newest-2e9=9007197254740993 -> TooOld (expected TooOld)
  exit=0
skip_list   newest=9007199254740993 readVersion=9007197254740992 newest-2e9=9007197254740993 -> Commit (expected TooOld)
  exit=1

The repo's own bisimulation harness (DebugConflictSet in test_conflict_set.py, which asserts that the skip list and the radix tree agree) fails on the same input:

$ PYTHONPATH=. python3 - <<'EOF'
from conflict_set import read
from test_conflict_set import DebugConflictSet
with DebugConflictSet() as cs:
    cs.addWrites((1 << 53) + 1)
    print(cs.check(read((1 << 53) + 1 - 2 * 10**9 - 1, b"k")))
EOF
Traceback (most recent call last):
  ...
  File "test_conflict_set.py", line 28, in check
    assert expected == actual
AssertionError

It is wrong in both directions

Measured with the same program (skip_list only; the radix tree is correct in every case):

newestVersion	readVersion	exact rule (readVersion < newest - 2e9)	skip_list
2^53+1 = 9007199254740993	9007197254740992 (newest-2e9-1)	TooOld	Commit
2^53+5 = 9007199254740997	9007197254740996 (newest-2e9-1)	TooOld	Commit
INT64_MAX	9223372034854775806 (newest-2e9-1)	TooOld	Commit
2^53+3 = 9007199254740995	9007197254740995 (newest-2e9)	not TooOld	TooOld
2^53+7 = 9007199254740999	9007197254740999 (newest-2e9)	not TooOld	TooOld

For newestVersion = INT64_MAX, every readVersion in [newest-2e9-510, newest-2e9-1] is misreported as not-TooOld (510 consecutive versions), because double(INT64_MAX) rounds up to 2^63. In general the error is bounded by half an ULP of newestVersion, i.e. up to 512 versions near 2^63 and 256 near 2^62.

Expected vs actual

include/ConflictSet.h states (both the C++ and the C text):

 * All versions are >= 0. `oldestVersion` is the smallest version a subsequent
 * `check` can read and `newestVersion` is the largest version passed to
 * `addWrites` or the constructor. `oldestVersion <= newestVersion`, and
 * `oldestVersion >= newestVersion - two billion`.
...
 * @post For every i < count, `results[i]` is `TooOld` if
 * `reads[i].readVersion < oldestVersion`; ...

• Expected: TooOld for readVersion < newestVersion - 2·10^9 (exact, all int64_t).
• Actual (skip_list): the comparison is done in double, so the answer flips whenever readVersion is within ~ULP(newestVersion)/2 of the boundary.

Why this is valid input

• The header only requires versions to be >= 0; int64_t versions near INT64_MAX are explicitly treated as valid by this repo -- conflict_set_cxx_api_test.cpp exercises INT64_MAX - 1e9 with the comment "Versions are only required to be >= 0, so this is valid input" (the regression test for #84).
• Versions above 2^53 are reachable in practice with any numbering derived from a wide counter or a clock: e.g. nanosecond wall-clock timestamps are ~1.8e18 today, far above 2^53 = 9.007e15.
• count == 0 in addWrites ("newestVersion (and possibly oldestVersion) still advance") is a documented postcondition, so advancing newestVersion without adding a write is valid usage.

Impact

• The 2e9 window exists so that reads whose versions may have been garbage collected are told TooOld instead of being given an answer (see the reasoning quoted in #98 and commit a68ad5d). skip_list silently returns Commit for such reads, which is exactly the case the window is meant to prevent: a transaction reading a version whose writes were reclaimed is allowed to commit. Conflict is equally possible if stale entries remain.
• The opposite error spuriously aborts transactions that read exactly at the boundary.
• Because Internal.h:516 has the same 2e9 expression, the ENABLE_FUZZ corpus/TestDriver oracle agrees with the buggy skip list, so this class of bug is invisible to the differential tests (and the oracle would blame the radix tree if the corpus ever generated versions >= 2^53).
• The counters commits_total / too_olds_total are also wrong for those reads.

Not a duplicate

• #98: hash_table never implements the window at all (no newestVersion member). Different file, different cause; here the rule is implemented but evaluated with the wrong precision.
• #84 (closed): signed integer overflow in the radix tree's addWrites near INT64_MAX. Different file and expression; ConflictSet.cpp already uses the integer constant kNominalVersionWindow.
• #87 (closed): SkipList.cpp::setOldestVersion monotonicity. Different function.

Suggested fix

Use integer arithmetic in both places:

--- a/SkipList.cpp
+++ b/SkipList.cpp
-          reads[i].readVersion < newestVersion - 2e9) {
+          reads[i].readVersion < newestVersion - int64_t(2000000000)) {
--- a/Internal.h
+++ b/Internal.h
-          reads[i].readVersion < newestVersion - 2e9) {
+          reads[i].readVersion < newestVersion - int64_t(2000000000)) {

and add a regression case to test_conflict_set.py (the DebugConflictSet bisimulation makes it fail without the fix):

def test_too_old_window_precision():
    # Regression test: the TooOld window boundary must be computed exactly.
    with DebugConflictSet() as cs:
        newest = (1 << 53) + 1
        cs.addWrites(newest)                        # count == 0
        assert cs.check(read(newest - 2 * 10**9 - 1, b"k")) == [Result.TOO_OLD]
        assert cs.check(read(newest - 2 * 10**9, b"k")) == [Result.COMMIT]

## Summary `SkipList.cpp:744` decides `TooOld` for reads that fell out of the two-billion-version window with ```c++ if (reads[i].readVersion < oldestVersion || reads[i].readVersion < newestVersion - 2e9) { // SkipList.cpp:743-744 results[i] = TooOld; } ``` `2e9` is a **`double` literal**, so `newestVersion - 2e9` is evaluated in `double` (the `int64_t` operand is converted, and `readVersion` is converted for the comparison). A `double` has a 53-bit mantissa, so for any `newestVersion >= 2^53` the boundary is off by up to ~512 versions, in both directions. The result is that `check()` returns `Commit` for reads that the API says must be `TooOld`, and `TooOld` for reads that are exactly at the boundary and must not be. The radix tree gets this right because it keeps the window as an integer (`ConflictSet.cpp:99`, `constexpr int64_t kNominalVersionWindow = 2e9;`, used at `ConflictSet.cpp:5178-5192`), so the two shipped implementations disagree on the same valid input. `Internal.h:516` (`ReferenceImpl::check`, the test oracle used by `TestDriver`/the corpus driver) contains the identical expression, so the differential tests share the defect and cannot catch it (and would flag the correct radix tree if the corpus ever produced such versions). ## Reproduction Same 3-operation program, linked against each shipped implementation: ```c++ // repro.cpp #include "ConflictSet.h" #include <cstdint> #include <cstdio> using namespace weaselab; int main() { const int64_t newest = (int64_t(1) << 53) + 1; // >= 0, so valid input const int64_t readVersion = newest - 2000000000 - 1; // 1 below the window const char *name[] = {"Commit", "Conflict", "TooOld"}; ConflictSet cs{0}; cs.addWrites(nullptr, 0, newest); // count == 0: no write, newestVersion advances ConflictSet::ReadRange r{{(const uint8_t *)"k", 1}, {nullptr, 0}, readVersion}; ConflictSet::Result result = ConflictSet::Conflict; cs.check(&r, &result, 1); printf("newest=%lld readVersion=%lld newest-2e9=%lld -> %s (expected TooOld)\n", (long long)newest, (long long)readVersion, (long long)(newest - 2000000000), name[int(result)]); return result == ConflictSet::TooOld ? 0 : 1; } ``` ```sh $ cmake -S . -B build -G Ninja -DCMAKE_BUILD_TYPE=Debug -DCMAKE_CXX_COMPILER=clang++ && ninja -C build $ for impl in radix_tree skip_list; do g++ -std=c++20 -O1 -Iinclude -I. -isystem third_party/valgrind -o repro_$impl repro.cpp \ -L$PWD/build/$impl -lconflict-set -Wl,-rpath,$PWD/build/$impl ./repro_$impl ; echo " exit=$?" done ``` Observed: ``` radix_tree newest=9007199254740993 readVersion=9007197254740992 newest-2e9=9007197254740993 -> TooOld (expected TooOld) exit=0 skip_list newest=9007199254740993 readVersion=9007197254740992 newest-2e9=9007197254740993 -> Commit (expected TooOld) exit=1 ``` The repo's own bisimulation harness (`DebugConflictSet` in `test_conflict_set.py`, which asserts that the skip list and the radix tree agree) fails on the same input: ```sh $ PYTHONPATH=. python3 - <<'EOF' from conflict_set import read from test_conflict_set import DebugConflictSet with DebugConflictSet() as cs: cs.addWrites((1 << 53) + 1) print(cs.check(read((1 << 53) + 1 - 2 * 10**9 - 1, b"k"))) EOF Traceback (most recent call last): ... File "test_conflict_set.py", line 28, in check assert expected == actual AssertionError ``` ### It is wrong in both directions Measured with the same program (`skip_list` only; the radix tree is correct in every case): | `newestVersion` | `readVersion` | exact rule (`readVersion < newest - 2e9`) | skip_list | |---|---|---|---| | 2^53+1 = 9007199254740993 | 9007197254740992 (`newest-2e9-1`) | TooOld | **Commit** | | 2^53+5 = 9007199254740997 | 9007197254740996 (`newest-2e9-1`) | TooOld | **Commit** | | INT64_MAX | 9223372034854775806 (`newest-2e9-1`) | TooOld | **Commit** | | 2^53+3 = 9007199254740995 | 9007197254740995 (`newest-2e9`) | not TooOld | **TooOld** | | 2^53+7 = 9007199254740999 | 9007197254740999 (`newest-2e9`) | not TooOld | **TooOld** | For `newestVersion = INT64_MAX`, every `readVersion` in `[newest-2e9-510, newest-2e9-1]` is misreported as not-`TooOld` (510 consecutive versions), because `double(INT64_MAX)` rounds up to `2^63`. In general the error is bounded by half an ULP of `newestVersion`, i.e. up to 512 versions near 2^63 and 256 near 2^62. ## Expected vs actual `include/ConflictSet.h` states (both the C++ and the C text): ``` * All versions are >= 0. `oldestVersion` is the smallest version a subsequent * `check` can read and `newestVersion` is the largest version passed to * `addWrites` or the constructor. `oldestVersion <= newestVersion`, and * `oldestVersion >= newestVersion - two billion`. ... * @post For every i < count, `results[i]` is `TooOld` if * `reads[i].readVersion < oldestVersion`; ... ``` * Expected: `TooOld` for `readVersion < newestVersion - 2·10^9` (exact, all `int64_t`). * Actual (`skip_list`): the comparison is done in `double`, so the answer flips whenever `readVersion` is within ~`ULP(newestVersion)/2` of the boundary. ## Why this is valid input * The header only requires versions to be `>= 0`; `int64_t` versions near `INT64_MAX` are explicitly treated as valid by this repo -- `conflict_set_cxx_api_test.cpp` exercises `INT64_MAX - 1e9` with the comment *"Versions are only required to be >= 0, so this is valid input"* (the regression test for #84). * Versions above 2^53 are reachable in practice with any numbering derived from a wide counter or a clock: e.g. nanosecond wall-clock timestamps are ~1.8e18 today, far above 2^53 = 9.007e15. * `count == 0` in `addWrites` ("`newestVersion` (and possibly `oldestVersion`) still advance") is a documented postcondition, so advancing `newestVersion` without adding a write is valid usage. ## Impact * The `2e9` window exists so that reads whose versions may have been garbage collected are told `TooOld` instead of being given an answer (see the reasoning quoted in #98 and commit `a68ad5d`). `skip_list` silently returns `Commit` for such reads, which is exactly the case the window is meant to prevent: a transaction reading a version whose writes were reclaimed is allowed to commit. `Conflict` is equally possible if stale entries remain. * The opposite error spuriously aborts transactions that read exactly at the boundary. * Because `Internal.h:516` has the same `2e9` expression, the `ENABLE_FUZZ` corpus/`TestDriver` oracle agrees with the buggy skip list, so this class of bug is invisible to the differential tests (and the oracle would blame the radix tree if the corpus ever generated versions >= 2^53). * The counters `commits_total` / `too_olds_total` are also wrong for those reads. ## Not a duplicate * #98: `hash_table` never implements the window at all (no `newestVersion` member). Different file, different cause; here the rule is implemented but evaluated with the wrong precision. * #84 (closed): signed integer overflow in the radix tree's `addWrites` near `INT64_MAX`. Different file and expression; `ConflictSet.cpp` already uses the integer constant `kNominalVersionWindow`. * #87 (closed): `SkipList.cpp::setOldestVersion` monotonicity. Different function. ## Suggested fix Use integer arithmetic in both places: ```diff --- a/SkipList.cpp +++ b/SkipList.cpp - reads[i].readVersion < newestVersion - 2e9) { + reads[i].readVersion < newestVersion - int64_t(2000000000)) { --- a/Internal.h +++ b/Internal.h - reads[i].readVersion < newestVersion - 2e9) { + reads[i].readVersion < newestVersion - int64_t(2000000000)) { ``` and add a regression case to `test_conflict_set.py` (the `DebugConflictSet` bisimulation makes it fail without the fix): ```python def test_too_old_window_precision(): # Regression test: the TooOld window boundary must be computed exactly. with DebugConflictSet() as cs: newest = (1 << 53) + 1 cs.addWrites(newest) # count == 0 assert cs.check(read(newest - 2 * 10**9 - 1, b"k")) == [Result.TOO_OLD] assert cs.check(read(newest - 2 * 10**9, b"k")) == [Result.COMMIT] ```

weaselbot was assigned by andrew 2026-11-10 19:06:47 +00:00

weaselbot referenced a pull request that will close this issue 2026-11-10 20:20:53 +00:00

Compute the TooOld window in integer arithmetic (#99) #102

Sign in to join this conversation.

No Branch/Tag Specified

Branches Tags

main

release-0.0

v0.0.13

v0.0.12

v0.0.11

v0.0.10

v0.0.9

v0.0.8

v0.0.7

v0.0.6

v0.0.5

v0.0.4

v0.0.3

v0.0.2

v0.0.1

Labels

Clear labels

bug

Something is not working

enhancement

New feature

investigation

wontfix

This won't be fixed

missing-test-coverage

Issues having to do with missing test coverage

No labels

Milestone

No items

No Milestone

Assignees

Clear assignees

andrew weaselbot

No Assignees weaselbot

1 Participants

Notifications

Subscribe

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: weaselab/conflict-set#99