Test the two-billion-version window in every implementation

test_two_billion_versions asserted nothing about the results, and hash_table
was never exercised across a version jump larger than two billion. Assert the
expected results and add test_two_billion_version_window, which checks the
window boundary (and the count == 0 case) for radix_tree, skip_list and
hash_table.

ConflictSet.cpp

@@ -96,6 +96,7 @@ int64_t getSearchPathLength(struct Node *);
 
 // ==================== BEGIN IMPLEMENTATION ====================
 
+constexpr int64_t kNominalVersionWindow = 2e9;
 constexpr int64_t kMaxCorrectVersionWindow =
     std::numeric_limits<int32_t>::max();
 static_assert(kNominalVersionWindow <= kMaxCorrectVersionWindow);

HashTable.cpp

@@ -18,15 +18,21 @@ struct string_hash {
   }
 };
 
+// Reads more than this many versions behind `newestVersion` are `TooOld`, so
+// that a caller whose read version fell out of the version window is told to
+// retry. See the `addWrites` postcondition in ConflictSet.h.
+constexpr int64_t kVersionWindow = 2'000'000'000;
+
 struct __attribute__((visibility("hidden"))) ConflictSet::Impl {
-  Impl(int64_t oldestVersion) : oldestVersion(oldestVersion) {}
+  Impl(int64_t oldestVersion)
+      : oldestVersion(oldestVersion), newestVersion(oldestVersion) {}
   void check(const ConflictSet::ReadRange *reads, ConflictSet::Result *results,
              int count) const {
     for (int i = 0; i < count; ++i) {
       auto key =
           std::string_view((const char *)reads[i].begin.p, reads[i].begin.len);
       auto version = reads[i].readVersion;
-      if (version < oldestVersion) {
+      if (version < oldestVersion || version < newestVersion - kVersionWindow) {
         results[i] = TooOld;
         continue;
       }
@@ -38,6 +44,10 @@ struct __attribute__((visibility("hidden"))) ConflictSet::Impl {
 
   void addWrites(const ConflictSet::WriteRange *writes, int count,
                  int64_t writeVersion) {
+    // Advance newestVersion before the loop, so that it also advances when
+    // count == 0, as documented in ConflictSet.h.
+    assert(writeVersion >= newestVersion);
+    newestVersion = writeVersion;
     for (int i = 0; i < count; ++i) {
       auto &max = map[std::string((const char *)writes[i].begin.p,
                                   writes[i].begin.len)];
@@ -84,6 +94,7 @@ struct __attribute__((visibility("hidden"))) ConflictSet::Impl {
 private:
   int64_t keyUpdates = 0;
   int64_t oldestVersion;
+  int64_t newestVersion;
   std::unordered_map<std::string, int64_t, string_hash, std::equal_to<>> map;
   std::string removalKey;
 };

Internal.h

@@ -27,15 +27,6 @@ using namespace weaselab;
 #define SHOW_MEMORY 0
 #endif
 
-// The window of versions, ending at `newestVersion`, that a subsequent `check`
-// is guaranteed to answer correctly. Reads older than
-// `newestVersion - kNominalVersionWindow` are reported as `TooOld`.
-//
-// This must be an integer constant: `newestVersion - 2e9` is computed in
-// `double`, whose 53 bit mantissa makes the boundary off by up to 512 versions
-// once `newestVersion >= 2^53`.
-constexpr int64_t kNominalVersionWindow = 2000000000;
-
 // std::span is not trivially constructible. We want a span that leaves its
 // members uninitialized for performance reasons.
 struct TrivialSpan {
@@ -522,7 +513,7 @@ struct ReferenceImpl {
              int count) const {
     for (int i = 0; i < count; ++i) {
       if (reads[i].readVersion < oldestVersion ||
-          reads[i].readVersion < newestVersion - kNominalVersionWindow) {
+          reads[i].readVersion < newestVersion - 2e9) {
         results[i] = ConflictSet::TooOld;
         continue;
       }

SkipList.cpp

@@ -741,7 +741,7 @@ struct __attribute__((visibility("hidden"))) ConflictSet::Impl {
     int iters = skipList.detectConflicts(ranges, count, results);
     for (int i = 0; i < count; ++i) {
       if (reads[i].readVersion < oldestVersion ||
-          reads[i].readVersion < newestVersion - kNominalVersionWindow) {
+          reads[i].readVersion < newestVersion - 2e9) {
         results[i] = TooOld;
       }
       tls.commits_accum += results[i] == Commit;

test_conflict_set.py

@@ -205,24 +205,32 @@ def test_internal_version_zero():
 def test_two_billion_versions():
     with DebugConflictSet() as cs:
         cs.addWrites(int(2e9) + 1)
-        cs.check(read(0, b"\x00", b"\xff"))
-        cs.check(read(1, b"\x00", b"\xff"))
+        assert cs.check(read(0, b"\x00", b"\xff")) == [Result.TOO_OLD]
+        assert cs.check(read(1, b"\x00", b"\xff")) == [Result.COMMIT]
 
 
-def test_too_old_window_precision():
-    # Regression test for issue #99: the TooOld window boundary
-    # (`newestVersion - 2e9`) must be computed with integer arithmetic. It used
-    # to be computed in `double`, whose 53 bit mantissa makes the boundary off
-    # by up to ~512 versions once newestVersion >= 2^53.
-    for newest in (1 << 53, (1 << 53) + 1, (1 << 53) + 7, 2**63 - 1):
-        with DebugConflictSet() as cs:
-            cs.addWrites(newest)  # No writes; advances newestVersion
-            boundary = newest - 2 * 10**9
-            # One below the window is TooOld, even though `double` rounding
-            # used to put it inside the window.
-            assert cs.check(read(boundary - 1, b"k")) == [Result.TOO_OLD]
-            # Exactly at the boundary is not TooOld.
-            assert cs.check(read(boundary, b"k")) == [Result.COMMIT]
+def test_two_billion_version_window():
+    # Regression test for issue #98: `addWrites` advances `newestVersion`, so a
+    # read whose readVersion fell more than two billion versions behind it is
+    # TooOld. `hash_table` used to discard writeVersion entirely, so it reported
+    # Conflict/Commit for reads far outside the version window.
+    window = 2 * 10**9
+    newest = 2**32
+
+    def probe(implementation, read_version, *writes):
+        with ConflictSet(0, build_dir=build_dir, implementation=implementation) as cs:
+            cs.addWrites(newest, *writes)
+            return cs.check(read(read_version, b"k"))[0]
+
+    for implementation in ("radix_tree", "skip_list", "hash_table"):
+        # The window advances even when addWrites added no writes at all.
+        assert probe(implementation, 0, write(b"k")) == Result.TOO_OLD
+        assert probe(implementation, 0) == Result.TOO_OLD
+        assert probe(implementation, newest - window - 1, write(b"k")) == Result.TOO_OLD
+        assert probe(implementation, newest - window - 1) == Result.TOO_OLD
+        # Exactly `window` versions behind newestVersion is still evaluable.
+        assert probe(implementation, newest - window, write(b"k")) == Result.CONFLICT
+        assert probe(implementation, newest - window) == Result.COMMIT
 
 
 def test_positive_bytes():