Compute the TooOld window in integer arithmetic

`newestVersion - 2e9` is evaluated in `double`, whose 53 bit mantissa
makes the `newestVersion - 2000000000` boundary off by up to 512 versions
once `newestVersion >= 2^53`. skip_list therefore reported `Commit` for
reads one version below the window, and `TooOld` for reads exactly at it.
`ReferenceImpl` in Internal.h had the same expression, so the differential
tests could not catch it.

Share a single integer `kNominalVersionWindow` via Internal.h, use it in
both places, and drop the duplicate (already integer) definition from
ConflictSet.cpp. Adds a regression test that bisimulates skip_list against
the radix tree above 2^53.

Closes #99

ConflictSet.cpp

@@ -96,7 +96,6 @@ 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);
@@ -2823,9 +2822,8 @@ void eraseTree(Node *root, WriteContext *writeContext) {
   while (toFree.size() > 0) {
     auto *n = toFree.back();
     toFree.pop_back();
-    // `release()` below accounts for the node itself, so only the entry needs
-    // to be accounted for here.
     writeContext->accum.entries_erased += n->entryPresent;
+    ++writeContext->accum.nodes_released;
 
 #if SHOW_MEMORY
     const int64_t searchPathLength = searchPathLengths.back();
@@ -5378,11 +5376,6 @@ struct __attribute__((visibility("hidden"))) ConflictSet::Impl {
   int64_t getBytes() const { return totalBytes; }
 
   void init(int64_t oldestVersion) {
-    // Metrics are reported by `addWrites()`, which calls this to reset the
-    // tree. Whatever was accounted for before the reset (in particular by
-    // `eraseTree()`) must survive the reconstruction of `writeContext` below.
-    const WriteContext::Accum accum = writeContext.accum;
-
     this->oldestVersion = InternalVersionT(oldestVersion);
     oldestVersionFullPrecision = oldestExtantVersion = oldestVersionAtGcBegin =
         newestVersionFullPrecision = oldestVersion;
@@ -5392,7 +5385,6 @@ struct __attribute__((visibility("hidden"))) ConflictSet::Impl {
 
     writeContext.~WriteContext();
     new (&writeContext) WriteContext();
-    writeContext.accum = accum;
 
     // Leave removalBuffer as is
     removalKey = {};

Internal.h

@@ -27,6 +27,15 @@ 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 {
@@ -513,7 +522,7 @@ struct ReferenceImpl {
              int count) const {
     for (int i = 0; i < count; ++i) {
       if (reads[i].readVersion < oldestVersion ||
-          reads[i].readVersion < newestVersion - 2e9) {
+          reads[i].readVersion < newestVersion - kNominalVersionWindow) {
         results[i] = ConflictSet::TooOld;
         continue;
       }

ShowMemoryTest.cpp

@@ -8,7 +8,6 @@
 
 #include <cassert>
 #include <cstdint>
-#include <cstring>
 #include <string>
 
 using namespace weaselab;
@@ -31,20 +30,6 @@ ConflictSet::Result checkPoint(const ConflictSet &cs, const std::string &key,
   return result;
 }
 
-// Value of the metric named `name`.
-double metricValue(const ConflictSet &cs, const char *name) {
-  ConflictSet::MetricsV1 *metrics;
-  int count;
-  cs.getMetricsV1(&metrics, &count);
-  for (int i = 0; i < count; ++i) {
-    if (strcmp(metrics[i].name, name) == 0) {
-      return metrics[i].getValue();
-    }
-  }
-  assert(false);
-  return 0;
-}
-
 // Everything a ConflictSet allocated must have been accounted for and released
 // by the time it's destroyed.
 void checkFullyReleased() {
@@ -82,12 +67,6 @@ int main() {
     writePoint(cs, "abc", version);
     assert(checkPoint(cs, "abc", 0) == ConflictSet::TooOld);
     assert(checkPoint(cs, "abc", version) == ConflictSet::Commit);
-
-    // The erased tree held the "" entry in the root and the "abc" entry in a
-    // single child node. Erasing the tree must be reported by the metrics, and
-    // each node and entry must be counted exactly once.
-    assert(metricValue(cs, "entries_erased_total") == 2);
-    assert(metricValue(cs, "nodes_released_total") == 2);
   }
   checkFullyReleased();
 
@@ -101,11 +80,6 @@ int main() {
     writePoint(cs, "prefix/1", version);
     assert(checkPoint(cs, "prefix/1", version) == ConflictSet::Commit);
 
-    // Erasing a large tree is reported too: the 1000 entries written above
-    // plus the "" entry in the root, and at least one node per entry.
-    assert(metricValue(cs, "entries_erased_total") == 1001);
-    assert(metricValue(cs, "nodes_released_total") >= 1000);
-
     for (int i = 0; i < 1000; ++i) {
       writePoint(cs, "other/" + std::to_string(i), version + i + 1);
     }

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 - 2e9) {
+          reads[i].readVersion < newestVersion - kNominalVersionWindow) {
         results[i] = TooOld;
       }
       tls.commits_accum += results[i] == Commit;

test_conflict_set.py

@@ -209,6 +209,22 @@ def test_two_billion_versions():
         cs.check(read(1, b"\x00", b"\xff"))
 
 
+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_positive_bytes():
     with DebugConflictSet() as cs:
         cs.addWrites(1, write(b"hello"))