Spec that addWrites advances oldestVersion minimally

The old wording only gave the lower bound oldestVersion >= newestVersion - two billion, which an implementation could satisfy by discarding more readable versions than necessary. State that oldestVersion becomes the larger of its previous value and newestVersion - two billion.
Don't poison Node48 reverseIndex
2026-10-10 14:04:17 -04:00 · 2026-10-10 13:58:58 -04:00 · 2026-10-10 13:55:02 -04:00 · 2026-10-09 16:34:33 -04:00 · 2026-10-09 16:28:36 -04:00 · 2026-10-09 16:19:20 -04:00
11 changed files with 2162 additions and 326 deletions
@@ -38,21 +38,43 @@ jobs:
      matrix:
        include:
          - name: 64-bit-versions
+            runner: ubuntu-latest-amd64
+            arch: amd64
+            llvm_version: "21"
+            msan_url: ""
            cmake_args: -DCMAKE_CXX_FLAGS=-DUSE_64_BIT=1
          - name: debug
-            cmake_args: -DCMAKE_BUILD_TYPE=Debug
+            runner: ubuntu-latest-amd64
+            arch: amd64
+            llvm_version: "21"
+            msan_url: https://minio.weaselab.dev/public/x86_64/msan-toolchain-21.1.8.tar.zst
+            cmake_args: -DCMAKE_BUILD_TYPE=Debug -DMSAN_TOOLCHAIN_PATH=/opt/msan
          - name: simd-fallback
+            runner: ubuntu-latest-amd64
+            arch: amd64
+            llvm_version: "21"
+            msan_url: ""
            cmake_args: -DUSE_SIMD_FALLBACK=ON
          - name: gcc
+            runner: ubuntu-latest-amd64
+            arch: amd64
+            llvm_version: "21"
+            msan_url: ""
            cmake_args: -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++
-    runs-on: ubuntu-latest-amd64
+          - name: debug-arm64
+            runner: ubuntu-latest-arm64
+            arch: arm64
+            llvm_version: "22"
+            msan_url: https://minio.weaselab.dev/public/aarch64/msan-toolchain-22.1.8.tar.zst
+            cmake_args: -DCMAKE_BUILD_TYPE=Debug -DMSAN_TOOLCHAIN_PATH=/opt/msan
+    runs-on: ${{ matrix.runner }}
    steps:
      - uses: actions/checkout@v4

      - uses: actions/cache@v4
        with:
          path: /var/cache/apt/archives
-          key: apt-amd64-${{ hashFiles('.gitea/workflows/ci.yml') }}
+          key: apt-${{ matrix.arch }}-${{ hashFiles('.gitea/workflows/ci.yml') }}

      - name: Install common dependencies
        run: |
@@ -68,14 +90,21 @@ jobs:
        run: |
          . /etc/os-release
          wget -qO- https://apt.llvm.org/llvm-snapshot.gpg.key | sudo tee /etc/apt/trusted.gpg.d/apt.llvm.org.asc
-          echo "deb http://apt.llvm.org/${VERSION_CODENAME}/ llvm-toolchain-${VERSION_CODENAME}-21 main" | sudo tee /etc/apt/sources.list.d/llvm.list
+          echo "deb http://apt.llvm.org/${VERSION_CODENAME}/ llvm-toolchain-${VERSION_CODENAME}-${{ matrix.llvm_version }} main" | sudo tee /etc/apt/sources.list.d/llvm.list
          sudo apt-get update -qq
          sudo apt-get install -y \
-            clang-21 llvm-21 lld-21 mold
+            clang-${{ matrix.llvm_version }} llvm-${{ matrix.llvm_version }} lld-${{ matrix.llvm_version }} mold
          for tool in clang clang++ llvm-ar llvm-nm llvm-ranlib llvm-objcopy llvm-cov llvm-symbolizer lld ld.lld; do
-            sudo update-alternatives --install /usr/bin/${tool} ${tool} /usr/bin/${tool}-21 100
+            sudo update-alternatives --install /usr/bin/${tool} ${tool} /usr/bin/${tool}-${{ matrix.llvm_version }} 100
          done

+      - name: Download MSan toolchain
+        if: matrix.msan_url != ''
+        run: |
+          curl -Ls "${{ matrix.msan_url }}" -o /tmp/msan-toolchain.tar.zst
+          sudo mkdir -p /opt/msan
+          sudo tar --zstd -xf /tmp/msan-toolchain.tar.zst -C /opt/msan
+
      - name: Build
        run: |
          export CCACHE_DIR="$GITHUB_WORKSPACE/.ccache"
@@ -116,8 +145,10 @@ jobs:
        include:
          - runner: ubuntu-latest-amd64
            arch: amd64
+            cmake_args: -DMSAN_TOOLCHAIN_PATH=/opt/msan
          - runner: ubuntu-latest-arm64
            arch: arm64
+            cmake_args: ""
    runs-on: ${{ matrix.runner }}
    steps:
      - uses: actions/checkout@v4
@@ -158,23 +189,25 @@ jobs:
          restore-keys: |
            ccache-release-${{ matrix.arch }}-

+      - name: Download MSan toolchain
+        if: matrix.arch == 'amd64'
+        run: |
+          curl -Ls "https://minio.weaselab.dev/public/x86_64/msan-toolchain-21.1.8.tar.zst" -o /tmp/msan-toolchain.tar.zst
+          sudo mkdir -p /opt/msan
+          sudo tar --zstd -xf /tmp/msan-toolchain.tar.zst -C /opt/msan
+
      - name: Build
        run: |
          export CCACHE_DIR="$GITHUB_WORKSPACE/.ccache"
          rm -rf build
-          cmake -S . -B build -G Ninja -DCMAKE_CXX_COMPILER_LAUNCHER=ccache -DCMAKE_CXX_FLAGS=-DNVALGRIND
+          cmake -S . -B build -G Ninja -DCMAKE_CXX_COMPILER_LAUNCHER=ccache -DCMAKE_CXX_FLAGS=-DNVALGRIND ${{ matrix.cmake_args }}
          ninja -C build
          ccache -s

      - name: Test
        run: |
          cd build
-          # On arm64, valgrind needs the MAKE_MEM_DEFINED client requests for
-          # https://git.weaselab.dev/weaselab/conflict-set/issues/39, but this
-          # build has -DNVALGRIND, which compiles them out. Skip valgrind
-          # tests here; they run annotated in the test job.
-          ctest --no-compress-output --test-output-size-passed 100000 --test-output-size-failed 100000 ${{ matrix.arch == 'arm64' && '-E valgrind' || '' }} -T Test -j "$(nproc)" --timeout 90 > /dev/null
-
+          ctest --no-compress-output --test-output-size-passed 100000 --test-output-size-failed 100000 -T Test -j "$(nproc)" --timeout 90 > /dev/null
      - name: Package
        run: |
          cd build
@@ -218,89 +251,6 @@ jobs:
            --link "https://minio.weaselab.dev/jenkins/conflict-set/${{ gitea.run_number }}/release-${{ matrix.arch }}/Test.xml.zst" \
            | tee -a "$GITHUB_STEP_SUMMARY"

-  msan:
-    runs-on: ubuntu-latest-amd64
-    env:
-      MSAN_VERSION: "21.1.8"
-      MSAN_URL: "https://minio.weaselab.dev/public/x86_64/msan-toolchain-21.1.8.tar.zst"
-    steps:
-      - uses: actions/checkout@v4
-
-      - uses: actions/cache@v4
-        with:
-          path: /var/cache/apt/archives
-          key: apt-amd64-${{ hashFiles('.gitea/workflows/ci.yml') }}
-
-      - name: Install dependencies
-        run: |
-          . /etc/os-release
-          wget -qO- https://apt.llvm.org/llvm-snapshot.gpg.key | sudo tee /etc/apt/trusted.gpg.d/apt.llvm.org.asc
-          echo "deb http://apt.llvm.org/${VERSION_CODENAME}/ llvm-toolchain-${VERSION_CODENAME}-21 main" | sudo tee /etc/apt/sources.list.d/llvm.list
-          sudo apt-get update -qq
-          sudo apt-get install -y \
-            build-essential ccache clang-21 cmake libc6-dbg \
-            llvm-21 lld-21 mold ninja-build python3 zstd
-          sudo curl -Ls "https://minio.weaselab.dev/public/$(uname -m)/mc.RELEASE.2025-08-13T08-35-41Z" \
-            -o /usr/local/bin/mc && sudo chmod +x /usr/local/bin/mc
-          for tool in clang clang++ llvm-ar llvm-nm llvm-ranlib llvm-objcopy llvm-cov llvm-symbolizer lld ld.lld; do
-            sudo update-alternatives --install /usr/bin/${tool} ${tool} /usr/bin/${tool}-21 100
-          done
-
-      - name: Download MSan toolchain
-        run: |
-          curl -Ls "${MSAN_URL}" -o /tmp/msan-toolchain.tar.zst
-          sudo mkdir -p /opt/msan
-          sudo tar --zstd -xf /tmp/msan-toolchain.tar.zst -C /opt/msan
-
-      - uses: actions/cache@v4
-        with:
-          path: .ccache
-          key: ccache-msan-${{ gitea.sha }}
-          restore-keys: |
-            ccache-msan-
-
-      - name: Build
-        run: |
-          export CCACHE_DIR="$GITHUB_WORKSPACE/.ccache"
-          rm -rf build
-          cmake -S . -B build -G Ninja \
-            -DCMAKE_C_COMPILER=clang \
-            -DCMAKE_CXX_COMPILER=clang++ \
-            -DCMAKE_CXX_COMPILER_LAUNCHER=ccache \
-            -DCMAKE_BUILD_TYPE=Debug \
-            -DDISABLE_TSAN=ON \
-            -DUSE_MSAN=ON \
-            -DCMAKE_CXX_FLAGS="-fsanitize=memory -stdlib=libc++ -I/opt/msan/include/c++/v1 -L/opt/msan/lib -UNDEBUG" \
-            -DCMAKE_EXE_LINKER_FLAGS="-stdlib=libc++ -Wl,-rpath,/opt/msan/lib" \
-            -DCMAKE_SHARED_LINKER_FLAGS="-stdlib=libc++ -Wl,-rpath,/opt/msan/lib"
-          ninja -C build
-          ccache -s
-
-      - name: Test
-        run: |
-          cd build
-          ctest --no-compress-output --test-output-size-passed 100000 --test-output-size-failed 100000 -T Test -j "$(nproc)" --timeout 300 > /dev/null
-
-      - name: Upload test results to MinIO
-        if: always()
-        env:
-          MINIO_ACCESS_KEY: ${{ secrets.MINIO_ACCESS_KEY }}
-          MC_HOST_minio: https://${{ secrets.MINIO_ACCESS_KEY }}:${{ secrets.MINIO_SECRET_KEY }}@minio.weaselab.dev
-        run: |
-          if [ -z "$MINIO_ACCESS_KEY" ]; then
-            echo "MinIO credentials not configured; skipping upload"
-            exit 0
-          fi
-          zstd build/Testing/*/Test.xml
-          mc cp build/Testing/*/Test.xml.zst "minio/jenkins/conflict-set/${{ gitea.run_number }}/msan/"
-
-      - name: Test summary
-        if: always()
-        run: |
-          python3 ctest_summary.py build/Testing/*/Test.xml \
-            --link "https://minio.weaselab.dev/jenkins/conflict-set/${{ gitea.run_number }}/msan/Test.xml.zst" \
-            | tee -a "$GITHUB_STEP_SUMMARY"
-
  coverage:
    runs-on: ubuntu-latest-amd64
    steps:
@@ -49,18 +49,6 @@ if(CMAKE_CXX_COMPILER_ID STREQUAL "Clang")
        ${LLVM_OBJCOPY}
        CACHE FILEPATH "path to objcopy binary" FORCE)
  endif()
-  if(USE_MSAN)
-    find_program(LLD_LINKER lld)
-    if(LLD_LINKER)
-      set(CMAKE_LINKER_TYPE
-          "LLD"
-          CACHE STRING "Use LLD linker" FORCE)
-      set(CMAKE_LINKER
-          ${LLD_LINKER}
-          CACHE FILEPATH "path to linker binary" FORCE)
-      add_link_options("-fuse-ld=lld")
-    endif()
-  endif()
 endif()

 if(CMAKE_CXX_COMPILER_ID STREQUAL "GNU")
@@ -115,7 +103,12 @@ option(USE_SIMD_FALLBACK

 option(DISABLE_TSAN "Disable TSAN" OFF)

-option(USE_MSAN "Build with MemorySanitizer (disables ASan/UBSan)" OFF)
+set(MSAN_TOOLCHAIN_PATH
+    ""
+    CACHE
+      PATH
+      "Path to an MSan-instrumented libc++ toolchain. When set, an MSan fuzz_driver target is added. Must contain include/c++/v1 and lib. See build_msan_toolchain.sh to produce one."
+)

 # This is encouraged according to
 # https://valgrind.org/docs/manual/manual-core-adv.html#manual-core-adv.clientreq
@@ -246,10 +239,8 @@ if(CMAKE_SOURCE_DIR STREQUAL CMAKE_CURRENT_SOURCE_DIR AND BUILD_TESTING)
  target_compile_definitions(conflict_set_main PRIVATE ENABLE_MAIN)
  target_link_libraries(conflict_set_main PRIVATE nanobench)

-  if(NOT APPLE AND NOT USE_MSAN)
-    # libfuzzer target, to generate/manage corpus. MSan requires an instrumented
-    # libfuzzer runtime, which is not shipped with the compiler, so skip this
-    # target when building with MSan.
+  if(NOT APPLE)
+    # libfuzzer target, to generate/manage corpus
    set(FUZZ_FLAGS "-fsanitize=fuzzer-no-link,address,undefined")
    include(CheckCXXCompilerFlag)
    cmake_push_check_state()
@@ -269,17 +260,12 @@ if(CMAKE_SOURCE_DIR STREQUAL CMAKE_CURRENT_SOURCE_DIR AND BUILD_TESTING)
    endif()
  endif()

-  # whitebox tests
+  # whitebox tests asan+ubsan
  add_executable(fuzz_driver ConflictSet.cpp FuzzTestDriver.cpp)
  target_compile_options(fuzz_driver PRIVATE ${TEST_FLAGS})
  if(NOT CMAKE_CROSSCOMPILING)
-    if(USE_MSAN)
-      target_compile_options(fuzz_driver PRIVATE -fsanitize=memory)
-      target_link_options(fuzz_driver PRIVATE -fsanitize=memory)
-    else()
-      target_compile_options(fuzz_driver PRIVATE -fsanitize=address,undefined)
-      target_link_options(fuzz_driver PRIVATE -fsanitize=address,undefined)
-    endif()
+    target_compile_options(fuzz_driver PRIVATE -fsanitize=address,undefined)
+    target_link_options(fuzz_driver PRIVATE -fsanitize=address,undefined)
  endif()
  target_compile_definitions(fuzz_driver PRIVATE ENABLE_FUZZ)
  target_include_directories(fuzz_driver
@@ -289,10 +275,36 @@ if(CMAKE_SOURCE_DIR STREQUAL CMAKE_CURRENT_SOURCE_DIR AND BUILD_TESTING)
    add_test(NAME conflict_set_fuzz_${hash} COMMAND fuzz_driver ${TEST})
  endforeach()

+  # whitebox tests msan
+  if(MSAN_TOOLCHAIN_PATH)
+    add_executable(fuzz_driver_msan ConflictSet.cpp FuzzTestDriver.cpp)
+    target_compile_options(fuzz_driver_msan PRIVATE ${TEST_FLAGS})
+    if(NOT CMAKE_CROSSCOMPILING)
+      target_compile_options(
+        fuzz_driver_msan
+        PRIVATE -fsanitize=memory -fsanitize-memory-track-origins=2
+                $<$<COMPILE_LANGUAGE:CXX>:-stdlib=libc++>
+                -I${MSAN_TOOLCHAIN_PATH}/include/c++/v1)
+      target_link_options(
+        fuzz_driver_msan
+        PRIVATE
+        -fsanitize=memory
+        -fsanitize-memory-track-origins=2
+        -stdlib=libc++
+        -L${MSAN_TOOLCHAIN_PATH}/lib
+        LINKER:-rpath,${MSAN_TOOLCHAIN_PATH}/lib)
+    endif()
+    target_compile_definitions(fuzz_driver_msan PRIVATE ENABLE_FUZZ)
+    target_include_directories(fuzz_driver_msan
+                               PRIVATE ${CMAKE_CURRENT_SOURCE_DIR}/include)
+    foreach(TEST ${CORPUS_TESTS})
+      get_filename_component(hash ${TEST} NAME)
+      add_test(NAME conflict_set_msan_${hash} COMMAND fuzz_driver_msan ${TEST})
+    endforeach()
+  endif()
+
  # tsan tests
-  if(NOT CMAKE_CROSSCOMPILING
-     AND NOT DISABLE_TSAN
-     AND NOT USE_MSAN)
+  if(NOT CMAKE_CROSSCOMPILING AND NOT DISABLE_TSAN)
    add_executable(tsan_driver ConflictSet.cpp FuzzTestDriver.cpp)
    target_compile_options(tsan_driver PRIVATE ${TEST_FLAGS} -fsanitize=thread)
    target_link_options(tsan_driver PRIVATE -fsanitize=thread)
@@ -514,11 +526,6 @@ target_include_directories(
  PUBLIC $<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}/include>
         $<INSTALL_INTERFACE:${CMAKE_INSTALL_INCLUDEDIR}/${PROJECT_NAME}>)

-if(USE_MSAN)
-  target_compile_options(${PROJECT_NAME} PUBLIC -fsanitize=memory)
-  target_link_options(${PROJECT_NAME} PUBLIC -fsanitize=memory)
-endif()
-
 set_target_properties(
  ${PROJECT_NAME} PROPERTIES VERSION ${PROJECT_VERSION}
                             SOVERSION ${PROJECT_VERSION_MAJOR})
@@ -488,6 +488,7 @@ inline void Node3::copyChildrenAndKeyFrom(const Node16 &other) {

 inline void Node16::copyChildrenAndKeyFrom(const Node3 &other) {
  copyCommon(*this, other);
+  memset(index, 0, sizeof(index));
  memcpy(index, other.index, Node3::kMaxNodes);
  memcpy(children, other.children,
         Node3::kMaxNodes * sizeof(children[0])); // NOLINT
@@ -499,6 +500,12 @@ inline void Node16::copyChildrenAndKeyFrom(const Node3 &other) {
    assert(children[i]->parent == &other);
    children[i]->parent = this;
  }
+  // The index bytes beyond numChildren are initialized so that the SIMD loads
+  // of the full 16 bytes are well-defined (reading indeterminate bytes is UB
+  // in C++). valgrind then treats them as undefined so that it can still flag
+  // any read that relies on them.
+  VALGRIND_MAKE_MEM_UNDEFINED(index + numChildren,
+                              sizeof(index) - numChildren * sizeof(index[0]));
 }

 inline void Node16::copyChildrenAndKeyFrom(const Node16 &other) {
@@ -515,6 +522,7 @@ inline void Node16::copyChildrenAndKeyFrom(const Node16 &other) {

 inline void Node16::copyChildrenAndKeyFrom(const Node48 &other) {
  copyCommon(*this, other);
+  memset(index, 0, sizeof(index));
  int i = 0;
  other.bitSet.forEachSet([&](int c) {
    // Suppress a false positive -Waggressive-loop-optimizations warning
@@ -528,6 +536,12 @@ inline void Node16::copyChildrenAndKeyFrom(const Node48 &other) {
    ++i;
  });
  memcpy(partialKey(), &other + 1, partialKeyLen);
+  // The index bytes beyond numChildren are initialized so that the SIMD loads
+  // of the full 16 bytes are well-defined (reading indeterminate bytes is UB
+  // in C++). valgrind then treats them as undefined so that it can still flag
+  // any read that relies on them.
+  VALGRIND_MAKE_MEM_UNDEFINED(index + numChildren,
+                              sizeof(index) - numChildren * sizeof(index[0]));
 }

 inline void Node48::copyChildrenAndKeyFrom(const Node16 &other) {
@@ -535,6 +549,7 @@ inline void Node48::copyChildrenAndKeyFrom(const Node16 &other) {
  assert(numChildren == Node16::kMaxNodes);
  memset(index, -1, sizeof(index));
  memset(children, 0, sizeof(children));
+  memset(reverseIndex, 0, sizeof(reverseIndex));
  const auto z = InternalVersionT::zero;
  for (auto &v : childMaxVersion) {
    v = z;
@@ -554,6 +569,9 @@ inline void Node48::copyChildrenAndKeyFrom(const Node16 &other) {
        std::max(maxOfMax[i >> Node48::kMaxOfMaxShift], childMaxVersion[i]);
    ++i;
  }
+  // The reverseIndex bytes beyond numChildren are initialized so that the
+  // SIMD loads of a full 16-byte page in scan16 are well-defined (reading
+  // indeterminate bytes is UB in C++).
 }

 inline void Node48::copyChildrenAndKeyFrom(const Node48 &other) {
@@ -580,6 +598,7 @@ inline void Node48::copyChildrenAndKeyFrom(const Node256 &other) {
  copyCommon(*this, other);
  memset(index, -1, sizeof(index));
  memset(children, 0, sizeof(children));
+  memset(reverseIndex, 0, sizeof(reverseIndex));
  const auto z = InternalVersionT::zero;
  for (auto &v : childMaxVersion) {
    v = z;
@@ -601,6 +620,9 @@ inline void Node48::copyChildrenAndKeyFrom(const Node256 &other) {
    ++i;
  });
  memcpy(partialKey(), &other + 1, partialKeyLen);
+  // The reverseIndex bytes beyond numChildren are initialized so that the
+  // SIMD loads of a full 16-byte page in scan16 are well-defined (reading
+  // indeterminate bytes is UB in C++).
 }

 inline void Node256::copyChildrenAndKeyFrom(const Node48 &other) {
@@ -1332,8 +1354,8 @@ TaggedNodePointer getChildGeq(Node *self, int child) {

 TaggedNodePointer getFirstChild(Node0 *) { return nullptr; }
 TaggedNodePointer getFirstChild(Node3 *self) {
-  // Improves scan performance
-  self->children[1].prefetch();
+  // Don't prefetch since self->children[1] might be uninitialized and msan
+  // doesn't like that
  return self->children[0];
 }
 TaggedNodePointer getFirstChild(Node16 *self) {
@@ -1992,7 +2014,6 @@ Node *erase(Node *self, WriteContext *writeContext, bool logical) {
      parent48->index[parentIndex] = toRemoveChildrenIndex;
      parent48->reverseIndex[toRemoveChildrenIndex] = parentIndex;
    }
-    parent48->childMaxVersion[lastChildrenIndex] = writeContext->zero;
    VALGRIND_MAKE_MEM_UNDEFINED(parent48->children + lastChildrenIndex,
                                sizeof(parent48->children[0]));

@@ -2087,6 +2108,53 @@ compare16_avx512(const InternalVersionT *vs, InternalVersionT rv) {
 }
 #endif

+#ifdef HAS_ARM_NEON
+// Returns a uint8x16_t whose byte i is 0xff if vs[i] > readVersion and 0
+// otherwise. When USE_64_BIT is set the comparison uses the full 64-bit value
+// (via vcgtq_s64); otherwise it falls back to the 32-bit subtract-and-compare
+// used by the original NEON fast path. The caller narrows this 16-byte vector
+// into the nibble-packed (4 bits per version) mask expected by scan16 and
+// checkMaxBetweenExclusiveImpl.
+inline uint8x16_t conflictMask16(const InternalVersionT *vs,
+                                 InternalVersionT readVersion) {
+#if USE_64_BIT
+  int64_t rv;
+  memcpy(&rv, &readVersion, sizeof(rv));
+  const auto rvVec = vdupq_n_s64(rv);
+  int32x2_t r32[8];
+  const auto *vsp = reinterpret_cast<const int64_t *>(vs);
+  for (int j = 0; j < 8; ++j) {
+    r32[j] = vmovn_s64(
+        vreinterpretq_s64_u64(vcgtq_s64(vld1q_s64(vsp + 2 * j), rvVec)));
+  }
+  uint32x4_t w4[4];
+  for (int k = 0; k < 4; ++k) {
+    w4[k] = vreinterpretq_u32_s32(vcombine_s32(r32[2 * k], r32[2 * k + 1]));
+  }
+  return vcombine_u8(
+      vmovn_u16(vcombine_u16(vmovn_u32(w4[0]), vmovn_u32(w4[1]))),
+      vmovn_u16(vcombine_u16(vmovn_u32(w4[2]), vmovn_u32(w4[3]))));
+#else
+  uint32x4_t w4[4];
+  memcpy(w4, vs, sizeof(w4));
+  uint32_t rv;
+  memcpy(&rv, &readVersion, sizeof(rv));
+  const auto rvVec = vdupq_n_u32(rv);
+
+  int32x4_t z;
+  memset(&z, 0, sizeof(z));
+
+  uint16x4_t conflicting[4];
+  for (int i = 0; i < 4; ++i) {
+    conflicting[i] =
+        vmovn_u32(vcgtq_s32(vreinterpretq_s32_u32(vsubq_u32(w4[i], rvVec)), z));
+  }
+  return vcombine_u8(vmovn_u16(vcombine_u16(conflicting[0], conflicting[1])),
+                     vmovn_u16(vcombine_u16(conflicting[2], conflicting[3])));
+#endif
+}
+#endif
+
 // Returns true if v[i] <= readVersion for all i such that begin <= is[i] < end
 // Preconditions: begin <= end, end - begin < 256
 template <bool kAVX512>
@@ -2107,26 +2175,10 @@ bool scan16(const InternalVersionT *vs, const uint8_t *is, int begin, int end,
  uint64_t mask = vget_lane_u64(
      vreinterpret_u64_u8(vshrn_n_u16(vreinterpretq_u16_u8(results), 4)), 0);

-  uint32x4_t w4[4];
-  memcpy(w4, vs, sizeof(w4));
-  uint32_t rv;
-  memcpy(&rv, &readVersion, sizeof(rv));
-  const auto rvVec = vdupq_n_u32(rv);
-
-  int32x4_t z;
-  memset(&z, 0, sizeof(z));
-
-  uint16x4_t conflicting[4];
-  for (int i = 0; i < 4; ++i) {
-    conflicting[i] =
-        vmovn_u32(vcgtq_s32(vreinterpretq_s32_u32(vsubq_u32(w4[i], rvVec)), z));
-  }
-  auto combined =
-      vcombine_u8(vmovn_u16(vcombine_u16(conflicting[0], conflicting[1])),
-                  vmovn_u16(vcombine_u16(conflicting[2], conflicting[3])));
-
  uint64_t compared = vget_lane_u64(
-      vreinterpret_u64_u8(vshrn_n_u16(vreinterpretq_u16_u8(combined), 4)), 0);
+      vreinterpret_u64_u8(vshrn_n_u16(
+          vreinterpretq_u16_u8(conflictMask16(vs, readVersion)), 4)),
+      0);

  return !(compared & mask);

@@ -2153,12 +2205,14 @@ bool scan16(const InternalVersionT *vs, const uint8_t *is, int begin, int end,
  auto inBounds = [&](unsigned c) { return c - shiftAmount < shiftUpperBound; };

  uint32_t compared = 0;
-  for (int i = 0; i < 16; ++i) {
-    compared |= (vs[i] > readVersion) << i;
-  }
  uint32_t mask = 0;
  for (int i = 0; i < 16; ++i) {
-    mask |= inBounds(is[i]) << i;
+    if (vs[i] > readVersion) {
+      compared |= 1u << i;
+      if (inBounds(is[i])) {
+        mask |= 1u << i;
+      }
+    }
  }
  return !(compared & mask);

@@ -2174,26 +2228,10 @@ bool scan16(const InternalVersionT *vs, int begin, int end,
  assert(begin <= end);

 #if defined(HAS_ARM_NEON)
-  uint32x4_t w4[4];
-  memcpy(w4, vs, sizeof(w4));
-  uint32_t rv;
-  memcpy(&rv, &readVersion, sizeof(rv));
-  const auto rvVec = vdupq_n_u32(rv);
-
-  int32x4_t z;
-  memset(&z, 0, sizeof(z));
-
-  uint16x4_t conflicting[4];
-  for (int i = 0; i < 4; ++i) {
-    conflicting[i] =
-        vmovn_u32(vcgtq_s32(vreinterpretq_s32_u32(vsubq_u32(w4[i], rvVec)), z));
-  }
-  auto combined =
-      vcombine_u8(vmovn_u16(vcombine_u16(conflicting[0], conflicting[1])),
-                  vmovn_u16(vcombine_u16(conflicting[2], conflicting[3])));
-
  uint64_t conflict = vget_lane_u64(
-      vreinterpret_u64_u8(vshrn_n_u16(vreinterpretq_u16_u8(combined), 4)), 0);
+      vreinterpret_u64_u8(vshrn_n_u16(
+          vreinterpretq_u16_u8(conflictMask16(vs, readVersion)), 4)),
+      0);

  conflict &= end == 16 ? -1 : (uint64_t(1) << (end << 2)) - 1;
  conflict >>= begin << 2;
@@ -2250,17 +2288,9 @@ bool checkMaxBetweenExclusiveImpl(Node3 *n, int begin, int end,
  auto inBounds = [&](unsigned c) { return c - shiftAmount < shiftUpperBound; };

  uint32_t mask = 0;
-  for (int i = 0; i < Node3::kMaxNodes; ++i) {
+  for (int i = 0; i < self->numChildren; ++i) {
    mask |= inBounds(self->index[i]) << i;
  }
-  mask &= (1 << self->numChildren) - 1;
-#ifdef __aarch64__
-  // The bits surviving the mask above don't derive from uninitialized slots,
-  // but clang 21+ on aarch64 lowers inBounds through flags+csel, which
-  // memcheck models imprecisely, tainting bits the mask provably clears.
-  // https://git.weaselab.dev/weaselab/conflict-set/issues/39
-  VALGRIND_MAKE_MEM_DEFINED(&mask, sizeof(mask));
-#endif
  if (!mask) {
    return true;
  }
@@ -2268,17 +2298,11 @@ bool checkMaxBetweenExclusiveImpl(Node3 *n, int begin, int end,
  const bool firstRangeOk =
      !child->entryPresent || child->entry.rangeVersion <= readVersion;
  uint32_t compared = 0;
-  for (int i = 0; i < Node3::kMaxNodes; ++i) {
+  for (int i = 0; i < self->numChildren; ++i) {
    compared |= (self->childMaxVersion[i] > readVersion) << i;
  }

-  uint32_t compared_masked = compared & mask;
-#ifdef __aarch64__
-  // Same imprecise csel modeling as above.
-  // https://git.weaselab.dev/weaselab/conflict-set/issues/39
-  VALGRIND_MAKE_MEM_DEFINED(&compared_masked, sizeof(compared_masked));
-#endif
-  return !compared_masked && firstRangeOk;
+  return !(compared & mask) && firstRangeOk;
 }

 template <bool kAVX512>
@@ -2321,26 +2345,11 @@ bool checkMaxBetweenExclusiveImpl(Node16 *n, int begin, int end,
  const bool firstRangeOk =
      !child->entryPresent || child->entry.rangeVersion <= readVersion;

-  uint32x4_t w4[4];
-  memcpy(w4, self->childMaxVersion, sizeof(w4));
-  uint32_t rv;
-  memcpy(&rv, &readVersion, sizeof(rv));
-  const auto rvVec = vdupq_n_u32(rv);
-
-  int32x4_t z;
-  memset(&z, 0, sizeof(z));
-
-  uint16x4_t conflicting[4];
-  for (int i = 0; i < 4; ++i) {
-    conflicting[i] =
-        vmovn_u32(vcgtq_s32(vreinterpretq_s32_u32(vsubq_u32(w4[i], rvVec)), z));
-  }
-  auto combined =
-      vcombine_u8(vmovn_u16(vcombine_u16(conflicting[0], conflicting[1])),
-                  vmovn_u16(vcombine_u16(conflicting[2], conflicting[3])));
-
  uint64_t compared = vget_lane_u64(
-      vreinterpret_u64_u8(vshrn_n_u16(vreinterpretq_u16_u8(combined), 4)), 0);
+      vreinterpret_u64_u8(vshrn_n_u16(vreinterpretq_u16_u8(conflictMask16(
+                                          self->childMaxVersion, readVersion)),
+                                      4)),
+      0);

  return !(compared & mask) && firstRangeOk;

@@ -2375,10 +2384,9 @@ bool checkMaxBetweenExclusiveImpl(Node16 *n, int begin, int end,
  auto inBounds = [&](unsigned c) { return c - shiftAmount < shiftUpperBound; };

  uint32_t mask = 0;
-  for (int i = 0; i < 16; ++i) {
+  for (int i = 0; i < self->numChildren; ++i) {
    mask |= inBounds(self->index[i]) << i;
  }
-  mask &= (1 << self->numChildren) - 1;
  if (!mask) {
    return true;
  }
@@ -2386,7 +2394,7 @@ bool checkMaxBetweenExclusiveImpl(Node16 *n, int begin, int end,
  const bool firstRangeOk =
      !child->entryPresent || child->entry.rangeVersion <= readVersion;
  uint32_t compared = 0;
-  for (int i = 0; i < 16; ++i) {
+  for (int i = 0; i < self->numChildren; ++i) {
    compared |= (self->childMaxVersion[i] > readVersion) << i;
  }
  return !(compared & mask) && firstRangeOk;
@@ -2884,7 +2892,11 @@ horizontalMax16(InternalVersionT *vs, InternalVersionT) {
  return max;
 }

-// Precondition: `node->entryPresent`, and node is not the root
+/** @pre `node` is not the root, `node->entryPresent`, and `writeContext !=
+ * nullptr`.
+ * @post `maxVersion(node)` is the max of `writeContext->zero` and the max
+ * version of all logical keys starting with the search path of `node`.
+ */
 void fixupMaxVersion(Node *node, WriteContext *writeContext) {
  assert(node->parent);
  InternalVersionT max;
@@ -2913,8 +2925,7 @@ void fixupMaxVersion(Node *node, WriteContext *writeContext) {
  } break;
  case Type_Node256: {
    auto *self256 = static_cast<Node256 *>(node);
-    max = std::max(
-        max, horizontalMax16(self256->childMaxVersion, writeContext->zero));
+    max = std::max(max, horizontalMax16(self256->maxOfMax, writeContext->zero));
  } break;
  default:                   // GCOVR_EXCL_LINE
    __builtin_unreachable(); // GCOVR_EXCL_LINE
@@ -3874,8 +3885,9 @@ void Job::init(const ConflictSet::ReadRange *read, ConflictSet::Result *result,
    this->result = result;
    continuation = check::point_read_state_machine::begin;
  } else {
+    auto end = TrivialSpan(read->end.p, read->end.len);
    this->begin = begin;
-    this->end = TrivialSpan(read->end.p, read->end.len);
+    this->end = end;
    this->n = root;
    this->readVersion = InternalVersionT(read->readVersion);
    this->result = result;
@@ -4860,7 +4872,7 @@ struct __attribute__((visibility("hidden"))) ConflictSet::Impl {
        auto *results2 = new (arena) Result[count];
        check::Context context2;
        useSequential(reads, results2, count, context2);
-        assert(memcmp(result, results2, count) == 0);
+        assert(memcmp(result, results2, count * sizeof(Result)) == 0);
        assert(context.readContext == context2.readContext);
 #endif
      }
@@ -4961,7 +4973,7 @@ struct __attribute__((visibility("hidden"))) ConflictSet::Impl {
        }
        if (e != nullptr) {
          while (e->releaseDeferred) {
-            e = b->forwardTo;
+            e = e->forwardTo;
          }
        }
        fprintf(stderr, "search path: %s, begin: %s\n",
@@ -5071,7 +5083,7 @@ struct __attribute__((visibility("hidden"))) ConflictSet::Impl {

    if (oldestExtantVersion < writeVersion - kMaxCorrectVersionWindow)
        [[unlikely]] {
-      if (writeVersion > newestVersionFullPrecision + kNominalVersionWindow) {
+      if (writeVersion - kNominalVersionWindow > newestVersionFullPrecision) {
        eraseTree(rootParent->children[0], &writeContext);
        init(writeVersion - kNominalVersionWindow);
      }
@@ -59,6 +59,12 @@ struct __attribute__((visibility("hidden"))) ConflictSet::Impl {
    while (keyUpdates > 0) {
      if (iter == map.end()) {
        iter = map.begin();
+        // The map is empty, so there are no more entries to garbage-collect.
+        // Break rather than spinning forever (keyUpdates is charged at 2x
+        // the entry count, so it may still be > 0 after emptying the map).
+        if (iter == map.end()) {
+          break;
+        }
      }
      for (; iter != map.end(); --keyUpdates) {
        if (iter->second <= oldestVersion) {
@@ -7,10 +7,10 @@ Hardware for all benchmarks is an AMD Ryzen 9 7900 with (2x32GB) 5600MT/s CL28-3
 ```
 $ clang++ --version

-Ubuntu clang version 20.0.0 (++20241120082228+86734c857724-1~exp1~20241120202359.554)
+Ubuntu clang version 21.1.8 (6ubuntu1)
 Target: x86_64-pc-linux-gnu
 Thread model: posix
-InstalledDir: /usr/lib/llvm-20/bin
+InstalledDir: /usr/lib/llvm-21/bin
 ```

 # Microbenchmark
@@ -19,30 +19,30 @@ InstalledDir: /usr/lib/llvm-20/bin

 |               ns/op |                op/s |    err% |          ins/op |          cyc/op |    IPC |         bra/op |   miss% |     total | benchmark
 |--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
-|              161.29 |        6,200,056.17 |    0.1% |        3,014.03 |          831.04 |  3.627 |         504.59 |    0.0% |      1.93 | `point reads`
-|              158.32 |        6,316,160.64 |    0.1% |        2,954.16 |          815.80 |  3.621 |         490.17 |    0.0% |      1.89 | `prefix reads`
-|              237.39 |        4,212,409.50 |    0.2% |        3,592.41 |        1,233.96 |  2.911 |         629.31 |    0.0% |      2.84 | `range reads`
-|              442.11 |        2,261,878.94 |    0.0% |        4,450.57 |        2,314.25 |  1.923 |         707.92 |    2.1% |      5.28 | `point writes`
-|              439.89 |        2,273,308.53 |    0.1% |        4,410.22 |        2,302.29 |  1.916 |         694.74 |    2.1% |      5.25 | `prefix writes`
-|              290.96 |        3,436,936.78 |    0.0% |        2,315.38 |        1,528.68 |  1.515 |         396.69 |    3.3% |      3.49 | `range writes`
-|              476.93 |        2,096,762.02 |    0.6% |        6,999.33 |        2,484.94 |  2.817 |       1,251.73 |    1.3% |      0.06 | `monotonic increasing point writes`
-|          131,736.57 |            7,590.91 |    1.1% |      807,444.50 |      704,941.71 |  1.145 |     144,584.60 |    0.9% |      0.01 | `worst case for radix tree`
-|               45.50 |       21,978,369.95 |    1.1% |          902.00 |          232.36 |  3.882 |         132.00 |    0.0% |      0.01 | `create and destroy`
+|              164.29 |        6,086,873.38 |    0.0% |        3,107.03 |          604.19 |  5.142 |         558.59 |    0.0% |      1.96 | `point reads`
+|              161.05 |        6,209,395.38 |    0.1% |        3,036.76 |          592.21 |  5.128 |         539.35 |    0.0% |      1.93 | `prefix reads`
+|              239.55 |        4,174,539.38 |    0.1% |        3,722.71 |          880.68 |  4.227 |         692.00 |    0.0% |      2.86 | `range reads`
+|              354.75 |        2,818,919.14 |    0.7% |        4,523.64 |        1,304.75 |  3.467 |         720.22 |    2.0% |      4.23 | `point writes`
+|              345.32 |        2,895,878.47 |    0.1% |        4,484.57 |        1,270.31 |  3.530 |         705.00 |    1.8% |      4.12 | `prefix writes`
+|              193.48 |        5,168,547.42 |    0.1% |        2,224.10 |          711.72 |  3.125 |         377.17 |    3.3% |      2.32 | `range writes`
+|              404.89 |        2,469,777.50 |    2.4% |        6,855.96 |        1,489.70 |  4.602 |       1,227.82 |    1.3% |      0.05 | `monotonic increasing point writes`
+|          134,231.80 |            7,449.80 |    1.9% |      812,045.25 |      495,770.40 |  1.638 |     151,246.50 |    0.9% |      0.01 | `worst case for radix tree`
+|               37.80 |       26,454,311.17 |    0.4% |          701.00 |          139.14 |  5.038 |         102.00 |    0.0% |      0.01 | `create and destroy`

 ## Radix tree (this implementation)


 |               ns/op |                op/s |    err% |          ins/op |          cyc/op |    IPC |         bra/op |   miss% |     total | benchmark
 |--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
-|               12.36 |       80,885,626.43 |    0.2% |          243.56 |           63.62 |  3.828 |          31.07 |    0.6% |      0.15 | `point reads`
-|               14.18 |       70,502,196.81 |    0.1% |          297.72 |           73.13 |  4.071 |          40.31 |    0.5% |      0.17 | `prefix reads`
-|               33.44 |       29,901,623.04 |    0.1% |          767.90 |          172.42 |  4.454 |         101.32 |    0.2% |      0.40 | `range reads`
-|               19.48 |       51,342,564.70 |    0.3% |          374.45 |          100.43 |  3.728 |          48.92 |    0.5% |      0.23 | `point writes`
-|               37.46 |       26,694,471.44 |    0.1% |          672.00 |          193.14 |  3.479 |         101.28 |    0.3% |      0.45 | `prefix writes`
-|               38.78 |       25,784,784.34 |    0.0% |          738.26 |          199.93 |  3.693 |         111.59 |    0.1% |      0.47 | `range writes`
-|               76.05 |       13,148,995.74 |    0.7% |        1,450.77 |          397.16 |  3.653 |         275.72 |    0.0% |      0.01 | `monotonic increasing point writes`
-|          286,920.33 |            3,485.29 |    0.4% |    4,117,948.00 |    1,521,352.00 |  2.707 |     714,833.00 |    0.1% |      0.01 | `worst case for radix tree`
-|               95.66 |       10,453,798.72 |    0.5% |        1,986.00 |          495.04 |  4.012 |         315.00 |    0.0% |      0.01 | `create and destroy`
+|               12.89 |       77,565,115.56 |    0.1% |          244.55 |           47.43 |  5.155 |          34.21 |    0.6% |      0.15 | `point reads`
+|               15.11 |       66,162,047.76 |    0.1% |          297.79 |           55.60 |  5.356 |          43.23 |    0.4% |      0.18 | `prefix reads`
+|               36.29 |       27,559,358.29 |    0.1% |          783.16 |          133.44 |  5.869 |         109.52 |    0.2% |      0.43 | `range reads`
+|               20.53 |       48,719,405.55 |    0.1% |          381.81 |           75.51 |  5.057 |          51.04 |    0.5% |      0.25 | `point writes`
+|               39.37 |       25,402,042.40 |    0.1% |          685.00 |          144.83 |  4.730 |         106.72 |    0.3% |      0.47 | `prefix writes`
+|               43.78 |       22,843,841.63 |    0.1% |          800.40 |          161.06 |  4.970 |         127.36 |    0.1% |      0.53 | `range writes`
+|               78.37 |       12,760,008.75 |    1.0% |        1,452.61 |          288.24 |  5.040 |         278.69 |    0.1% |      0.01 | `monotonic increasing point writes`
+|          322,885.50 |            3,097.07 |    1.5% |    4,362,382.00 |    1,183,852.00 |  3.685 |     765,301.00 |    0.1% |      0.01 | `worst case for radix tree`
+|               99.99 |       10,000,718.79 |    0.4% |        1,775.00 |          367.93 |  4.824 |         288.00 |    0.0% |      0.01 | `create and destroy`

 # "Real data" test

@@ -51,13 +51,13 @@ Point queries only. Gc ratio is the ratio of time spent doing garbage collection
 ## skip list

 ```
-Check: 4.53508 seconds, 371.81 MB/s, Add: 3.81222 seconds, 150.919 MB/s, Gc ratio: 33.66%, Peak idle memory: 5.61007e+06
+Check: 4.62967 seconds, 352.195 MB/s, Add: 3.34177 seconds, 167.771 MB/s, Gc ratio: 37.9399%, Peak idle memory: 5.51852e+06
 ```

 ## radix tree

 ```
-Check: 0.957735 seconds, 1760.6 MB/s, Add: 1.19942 seconds, 479.678 MB/s, Gc ratio: 38.6069%, Peak idle memory: 2.05667e+06
+Check: 1.00477 seconds, 1622.8 MB/s, Add: 1.21142 seconds, 462.808 MB/s, Gc ratio: 39.4716%, Peak idle memory: 2.0226e+06
 ```

 ## hash table
@@ -65,6 +65,6 @@ Check: 0.957735 seconds, 1760.6 MB/s, Add: 1.19942 seconds, 479.678 MB/s, Gc rat
 (The hash table implementation doesn't work on range queries, and its purpose is to provide an idea of how fast point queries can be)

 ```
-Check: 0.804598 seconds, 2095.69 MB/s, Add: 0.671221 seconds, 857.147 MB/s, Gc ratio: 35.0034%, Peak idle memory: 0
+Check: 0.854254 seconds, 1908.74 MB/s, Add: 0.632626 seconds, 886.232 MB/s, Gc ratio: 41.0827%, Peak idle memory: 0
 ```

@@ -35,36 +35,5 @@ int main(int argc, char **argv) {
        break;
      }
    }
-
-    {
-      ConflictSet::MetricsV1 *metrics;
-      int metricsCount;
-      driver1.cs.getMetricsV1(&metrics, &metricsCount);
-      printf("#################### METRICS for ConflictSet 1 for %s "
-             "####################\n",
-             argv[i]);
-      for (int i = 0; i < metricsCount; ++i) {
-        printf("# HELP %s %s\n", metrics[i].name, metrics[i].help);
-        printf("# TYPE %s %s\n", metrics[i].name,
-               metrics[i].type == metrics[i].Counter ? "counter" : "gauge");
-        printf("%s %g\n", metrics[i].name, metrics[i].getValue());
-      }
-      puts("");
-    }
-    {
-      ConflictSet::MetricsV1 *metrics;
-      int metricsCount;
-      driver2.cs.getMetricsV1(&metrics, &metricsCount);
-      printf("#################### METRICS for ConflictSet 2 for %s "
-             "####################\n",
-             argv[i]);
-      for (int i = 0; i < metricsCount; ++i) {
-        printf("# HELP %s %s\n", metrics[i].name, metrics[i].help);
-        printf("# TYPE %s %s\n", metrics[i].name,
-               metrics[i].type == metrics[i].Counter ? "counter" : "gauge");
-        printf("%s %g\n", metrics[i].name, metrics[i].getValue());
-      }
-      puts("");
-    }
  }
 }
@@ -13,26 +13,26 @@ cd libcxx-msan

 git clone --depth=1 "https://github.com/llvm/llvm-project.git" -b "release/${LLVM_VERSION}.x"

-cmake -S llvm-project/runtimes -B build \
+cmake -S llvm-project/runtimes -B build_msan \
  -DCMAKE_BUILD_TYPE=Release \
-  -DCMAKE_C_COMPILER="clang-${LLVM_VERSION}" \
  -DCMAKE_CXX_COMPILER="clang++-${LLVM_VERSION}" \
-  -DLLVM_USE_SANITIZER=MemoryWithOrigins \
-  -DLLVM_ENABLE_RUNTIMES="libcxx;libcxxabi;libunwind" \
-  -DLLVM_TARGETS_TO_BUILD=Native \
+  -DCMAKE_C_COMPILER="clang-${LLVM_VERSION}" \
  -DCMAKE_INSTALL_PREFIX="${MSAN_PREFIX}" \
-  -DLIBCXXABI_USE_LLVM_UNWINDER=ON \
-  -DLIBCXXABI_ENABLE_STATIC_UNWINDER=ON \
-  -DLIBCXX_USE_COMPILER_RT=ON \
-  -DLIBCXXABI_USE_COMPILER_RT=ON \
-  -DLIBUNWIND_USE_COMPILER_RT=ON \
-  -DLIBCXX_INCLUDE_TESTS=OFF \
-  -DLIBCXXABI_INCLUDE_TESTS=OFF \
-  -DLIBUNWIND_INCLUDE_TESTS=OFF \
-  -DLIBCXX_ENABLE_CLANG_TIDY=OFF
+  -DLLVM_ENABLE_RUNTIMES="libcxx;libcxxabi;libunwind" \
+  -DLLVM_USE_SANITIZER=MemoryWithOrigins

-cmake --build build -j"${JOBS}"
-cmake --install build
+cmake --build build_msan -j"${JOBS}"
+cmake --install build_msan
+
+cmake -S llvm-project/runtimes -B build_nomsan \
+  -DCMAKE_BUILD_TYPE=Release \
+  -DCMAKE_CXX_COMPILER="clang++-${LLVM_VERSION}" \
+  -DCMAKE_C_COMPILER="clang-${LLVM_VERSION}" \
+  -DCMAKE_INSTALL_PREFIX="${MSAN_PREFIX}" \
+  -DLLVM_ENABLE_RUNTIMES="libunwind"
+
+cmake --build build_nomsan -j"${JOBS}"
+cmake --install build_nomsan

 VERSION="$(clang-"${LLVM_VERSION}" --version | head -n1 | sed -E 's/.*clang version ([0-9.]+).*/\1/')"
 TARBALL="msan-toolchain-${VERSION}.tar.zst"
@@ -2,6 +2,7 @@

 #include <cassert>
 #include <cstdio>
+#include <limits>

 using namespace weaselab;

@@ -23,6 +24,28 @@ int main(void) {
  int64_t bytes = cs.getBytes();
  assert(bytes > 0);

+  // Regression: a write just below INT64_MAX must not overflow the nominal
+  // version window comparison and erase entries that reads still observe.
+  // Versions are only required to be >= 0, so this is valid input.
+  {
+    const int64_t imax = std::numeric_limits<int64_t>::max();
+    const int64_t v0 = imax - int64_t(1000000000);
+    ConflictSet nearMax(0);
+    ConflictSet::WriteRange w2;
+    w2.begin.p = (const uint8_t *)"key";
+    w2.begin.len = 3;
+    w2.end.len = 0;
+    nearMax.addWrites(&w2, 1, v0);
+    nearMax.addWrites(&w2, 0, imax);
+    ConflictSet::ReadRange r2;
+    r2.begin.p = (const uint8_t *)"key";
+    r2.begin.len = 3;
+    r2.end.len = 0;
+    r2.readVersion = v0 - 1;
+    nearMax.check(&r2, &result, 1);
+    assert(result == ConflictSet::Conflict);
+  }
+
  ConflictSet::MetricsV1 *metrics;
  int metricsCount;
  cs.getMetricsV1(&metrics, &metricsCount);
@@ -21,7 +21,12 @@ limitations under the License.
 #ifdef __cplusplus
 namespace weaselab {
 /** A data structure for optimistic concurrency control on ranges of
- * bitwise-lexicographically-ordered keys. All versions must be >= 0.
+ * bitwise-lexicographically-ordered keys.
+ *
+ * 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`.
 *
 * Thread safety:
 *   - It's safe to operate on two different ConflictSets in two different
@@ -36,8 +41,7 @@ struct __attribute__((__visibility__("default"))) ConflictSet {
    /** The result of a check which intersects a write at a version >
       readVersion */
    Conflict,
-    /** The result of a check with a readVersion older than the highest call to
-       `setOldestVersion` */
+    /** The result of a check with a readVersion older than `oldestVersion` */
    TooOld
  };

@@ -54,9 +58,6 @@ struct __attribute__((__visibility__("default"))) ConflictSet {
    /** `end` having length 0 denotes that this range is the single key {begin}.
     * Otherwise this denotes the range [begin, end), and begin must be < end */
    Key end;
-    /** `readVersion` older than the oldestVersion or the version of the
-     * latest call to `addWrites` minus two billion will result in `TooOld`.
-     * Must be <= the version of the latest call to `addWrites` */
    int64_t readVersion;
  };

@@ -68,23 +69,38 @@ struct __attribute__((__visibility__("default"))) ConflictSet {
    Key end;
  };

-  /** The result of checking reads[i] is written in results[i] */
+  /** The result of checking reads[i] is written in results[i].
+   * @pre `reads` and `results` each hold at least `count` elements; each
+   * `reads[i]` is a valid `ReadRange` (see its field documentation); each
+   * `reads[i].readVersion <= newestVersion`.
+   * @post For every i < count, `results[i]` is `TooOld` if
+   * `reads[i].readVersion < oldestVersion`; `Conflict` if any write at a
+   * version greater than `reads[i].readVersion` intersects the range
+   * `reads[i]`; and `Commit` otherwise. */
  void check(const ReadRange *reads, Result *results, int count) const;

-  /** Reads intersecting writes where readVersion < `writeVersion` will result
-   * in `Conflict` (or `TooOld`, eventually).  `writeVersion` must be greater
-   * than or equal to all previous write versions. Call `addWrites` with `count`
-   * zero to only advance the version. */
+  /** Records writes at `writeVersion`, making them visible to `check`.
+   * @pre `writes` holds at least `count` elements; every `writes[i]` is a valid
+   * `WriteRange` (see its field documentation); `count >= 0`; `writeVersion >=
+   * newestVersion`.
+   * @post Writes (writes[i], writeVersion) are recorded for every i < count,
+   * and `newestVersion` becomes `writeVersion`. `oldestVersion` advances only
+   * as far as necessary: it becomes the larger of its previous value and
+   * `newestVersion - two billion`. Calling with `count == 0` adds no write;
+   * `newestVersion` (and possibly `oldestVersion`) still advance. */
  void addWrites(const WriteRange *writes, int count, int64_t writeVersion);

-  /** Reads where readVersion < `oldestVersion` will result in `TooOld`. Must be
-   * greater than or equal to all previous oldest versions. Must be <= the
-   * version of the latest call to `addWrites` */
+  /** 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);

-  /** Reads where readVersion < oldestVersion will result in `TooOld`. There are
-   * no writes initially */
-  explicit ConflictSet(int64_t oldestVersion);
+  /** Reads where readVersion < `oldestVersion` will result in `TooOld`.
+   * @pre `version >= 0`.
+   * @post No writes are recorded, and `oldestVersion == newestVersion ==
+   * version`. */
+  explicit ConflictSet(int64_t version);

  ~ConflictSet();

@@ -146,7 +162,12 @@ private:
 #else

 /** A data structure for optimistic concurrency control on ranges of
- * bitwise-lexicographically-ordered keys. All versions must be >= 0.
+ * bitwise-lexicographically-ordered keys.
+ *
+ * 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`.
 *
 * Thread safety:
 *   - It's safe to operate on two different ConflictSets in two different
@@ -160,11 +181,10 @@ typedef struct ConflictSet ConflictSet;
 typedef enum {
  /** The result of a check which does not intersect any conflicting writes */
  ConflictSet_Commit,
-  /** The result of a check which intersects a write at a version > readVersion
-   */
+  /** The result of a check which intersects a write at a version >
+     readVersion */
  ConflictSet_Conflict,
-  /** The result of a check with a readVersion older than the highest call to
-     `setOldestVersion` */
+  /** The result of a check with a readVersion older than `oldestVersion` */
  ConflictSet_TooOld
 } ConflictSet_Result;

@@ -181,9 +201,6 @@ typedef struct {
  /** `end` having length 0 denotes that this range is the single key {begin}.
   * Otherwise this denotes the range [begin, end), and begin must be < end */
  ConflictSet_Key end;
-  /** `readVersion` older than the oldestVersion or the version of the
-   * latest call to `addWrites` minus two billion will result in `TooOld`.
-   * Must be <= the version of the latest call to `addWrites` */
  int64_t readVersion;
 } ConflictSet_ReadRange;

@@ -195,27 +212,43 @@ typedef struct {
  ConflictSet_Key end;
 } ConflictSet_WriteRange;

-/** The result of checking reads[i] is written in results[i] */
+/** The result of checking reads[i] is written in results[i].
+ * @pre `reads` and `results` each hold at least `count` elements; each
+ * `reads[i]` is a valid `ConflictSet_ReadRange` (see its field documentation);
+ * each `reads[i].readVersion <= newestVersion`.
+ * @post For every i < count, `results[i]` is `ConflictSet_TooOld` if
+ * `reads[i].readVersion < oldestVersion`; `ConflictSet_Conflict` if any write
+ * at a version greater than `reads[i].readVersion` intersects the range
+ * `reads[i]`; and `ConflictSet_Commit` otherwise. */
 void ConflictSet_check(const ConflictSet *cs,
                       const ConflictSet_ReadRange *reads,
                       ConflictSet_Result *results, int count);

-/** Reads intersecting writes where readVersion < `writeVersion` will result
- * in `Conflict` (or `TooOld`, eventually).  `writeVersion` must be greater
- * than or equal to all previous write versions. Call `addWrites` with `count`
- * zero to only advance the version. */
+/** Records writes at `writeVersion`, making them visible to
+ * `ConflictSet_check`.
+ * @pre `writes` holds at least `count` elements; every `writes[i]` is a valid
+ * `ConflictSet_WriteRange` (see its field documentation); `count >= 0`;
+ * `writeVersion >= newestVersion`.
+ * @post Writes (writes[i], writeVersion) are recorded for every i < count,
+ * and `newestVersion` becomes `writeVersion`. `oldestVersion` advances only
+ * as far as necessary: it becomes the larger of its previous value and
+ * `newestVersion - two billion`. Calling with `count == 0` adds no write;
+ * `newestVersion` (and possibly `oldestVersion`) still advance. */
 void ConflictSet_addWrites(ConflictSet *cs,
                           const ConflictSet_WriteRange *writes, int count,
                           int64_t writeVersion);

-/** Reads where readVersion < `oldestVersion` will result in `TooOld`. Must be
- * greater than or equal to all previous oldest versions. Must be <= the
- * version of the latest call to `addWrites` */
+/** 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 ConflictSet_setOldestVersion(ConflictSet *cs, int64_t oldestVersion);

-/** Reads where readVersion < oldestVersion will result in `TooOld`. There are
- * no writes initially */
-ConflictSet *ConflictSet_create(int64_t oldestVersion);
+/** Reads where readVersion < `oldestVersion` will result in `TooOld`.
+ * @pre `version >= 0`.
+ * @post No writes are recorded, and `oldestVersion == newestVersion ==
+ * version`. */
+ConflictSet *ConflictSet_create(int64_t version);

 void ConflictSet_destroy(ConflictSet *cs);

@@ -68,6 +68,25 @@ def test_hash_table_getBytes():
        assert cs.check(read(0, b"key")) == [Result.CONFLICT]


+def test_hash_table_setOldestVersion_empties_map():
+    # Regression test for issue #78: setOldestVersion must terminate when
+    # its garbage-collection pass erases every entry in the map. Each write
+    # charges keyUpdates += 2, so with 50 writes keyUpdates = 100 and GC is
+    # enabled; erasing all entries leaves keyUpdates > 0 while the map is
+    # empty, which previously caused the GC loop to spin forever.
+    with ConflictSet(0, build_dir=build_dir, implementation="hash_table") as cs:
+        for i in range(50):
+            cs.addWrites(1, write(("k%06d" % i).encode()))
+        # All entries have version 1 <= oldestVersion 1 -> all erased.
+        cs.setOldestVersion(1)
+        # If we reach this point, setOldestVersion returned instead of hanging.
+        # The keys were erased, so reads at a valid version commit.
+        assert cs.check(read(1, b"k000000")) == [Result.COMMIT]
+        assert cs.check(read(2, b"k000000")) == [Result.COMMIT]
+        # A read older than oldestVersion is TooOld.
+        assert cs.check(read(0, b"k000000")) == [Result.TOO_OLD]
+
+
 def test_write_read_without_outer_reference():
    # Regression test for issue #42: WriteRange/ReadRange must keep their
    # backing key buffers alive, because the C library reads the pointer
Author	SHA1	Message	Date
andrew	ba781b8875	Spec that addWrites advances oldestVersion minimally The old wording only gave the lower bound oldestVersion >= newestVersion - two billion, which an implementation could satisfy by discarding more readable versions than necessary. State that oldestVersion becomes the larger of its previous value and newestVersion - two billion.	2026-10-10 14:04:17 -04:00
andrew	8621662d3c	Don't poison Node48 reverseIndex Follows the reasoning of "Remove redundant version update": a write can never lower the logical max version of a key range, so there's no read that didn't pass before that should pass after a write. The check stays exact reading the physical childMaxVersion and reverseIndex of unused slots, so scan16's whole-page reads of them are well-defined and intended. The client requests only produced valgrind false positives. Keep the initialization, drop the poisoning.	2026-10-10 13:58:58 -04:00
andrew	9c721bcdca	Stop printing metrics from TestDriver The per-corpus-file Prometheus dump was debug-only output that nothing consumes. It also floods stdout well past ctest's failed-output cap, so the real failure (e.g. a valgrind report) never made it into the CI summary.	2026-10-10 13:55:02 -04:00
andrew	4ef10b106a	Fix wrong-result bug. Previously it could incorrectly report Commit Blog post forthcoming	2026-10-09 16:34:33 -04:00
andrew	9b6dd51b85	Add a spec for fixupMaxVersion	2026-10-09 16:28:36 -04:00
andrew	647ba5beb1	Remove redundant version update A write can never lower the logical max version of a key range. There's no read that didn't pass before that should pass after a write.	2026-10-09 16:19:20 -04:00
andrew	2f9f49c692	Use doxygen pre/post tags and make public api more precise	2026-10-09 15:09:58 -04:00
andrew	6a6e36909f	Fix assert memcmp size	2026-10-09 15:05:39 -04:00
andrew	46d1f05333	Avoid signed overflow This only happens at implausibly high version numbers, but the fix is straightforward so we'll just do it anyway. Closes #84	2026-09-23 11:36:12 -04:00
andrew	8a16f9a6d6	Merge pull request 'Fix broken endInsertionPoint forwarding chain resolution in DEBUG_VERBOSE print' (#83 ) from weaselbot/conflict-set:weaselbot/issue-82 into main Reviewed-on: weaselab/conflict-set#83	2026-08-31 01:14:10 +00:00
weaselbot	9a2c64d31c	Fix broken endInsertionPoint forwarding chain resolution in DEBUG_VERBOSE print In the Phase 2 debug block of ConflictSet::Impl::interleavedWrites, the loop resolving the end insertion point's releaseDeferred/forwardTo chain followed the begin node's chain instead (e = b->forwardTo). Once b is resolved, b->forwardTo aliases the Entry union member, so e was assigned garbage derived from version bytes and the loop dereferenced it, causing a SEGV or hang whenever DEBUG_VERBOSE builds traced writes. Use the end node's own forwarding chain (e = e->forwardTo), matching the production code in the same loop body and in Phase 3.	2026-08-30 20:17:22 -04:00
andrew	ec1b476977	Merge pull request 'Fix NEON type mismatch in conflictMask16 for gcc/aarch64 + USE_64_BIT=1' (#81 ) from weaselbot/conflict-set:weaselbot/issue-80 into main Reviewed-on: http://git.weaselab.dev/weaselab/conflict-set/pulls/81	2026-08-18 17:39:48 +00:00
weaselbot	8c55e835c4	Fix NEON type mismatch in conflictMask16 for gcc/aarch64 + USE_64_BIT=1 vcgtq_s64 returns uint64x2_t but vmovn_s64 requires int64x2_t. clang accepts the implicit conversion via lax vector conversions, but gcc does not. Add an explicit vreinterpretq_s64_u64 so the code compiles with gcc on aarch64 when USE_64_BIT=1. This path is otherwise untested in CI (aarch64 matrices use USE_64_BIT=0; the 64-bit-versions matrix uses amd64 AVX compare16). Closes #80	2026-08-16 21:16:23 -04:00
andrew	af76c4d623	Merge pull request 'Fix hash_table setOldestVersion infinite loop on empty map' (#79 ) from weaselbot/conflict-set:weaselbot/issue-78 into main Reviewed-on: http://git.weaselab.dev/weaselab/conflict-set/pulls/79	2026-08-17 00:25:27 +00:00
weaselbot	6db080a34c	Fix hash_table setOldestVersion infinite loop on empty map setOldestVersion's GC pass charges keyUpdates at 2x the entry count, so when every entry has version <= oldestVersion and is erased, keyUpdates remains > 0 while the map is empty. The outer while(keyUpdates > 0) loop then reset iter to map.begin() (== end() for an empty map) and the inner for loop never executed, spinning forever. Break out of the while loop when the map is exhausted, so the call returns normally. Closes #78	2026-08-16 13:02:50 -04:00
andrew	cdbad1c013	Merge pull request 'Replace SIMD assembly with initialized Node16::index + valgrind client request' (#77 ) from client-request-instead-of-asm into main Reviewed-on: weaselab/conflict-set#77	2026-08-04 00:07:19 +00:00
andrew	6d9810fe7f	Poison Node48 reverseIndex slot on erase When a Node48 loses a child, the vacated reverseIndex slot would otherwise remain defined, letting valgrind miss reads that rely on the stale value. Mark it undefined, mirroring the existing poisoning of the vacated children slot.	2026-08-03 17:38:21 -04:00
andrew	bae2b22e95	Replace SIMD assembly with initialized Node16::index + valgrind client request Commit `6fed133` moved SIMD operations on Node16::index into file-level assembly (later extended to aarch64) to avoid reading indeterminate bytes (UB in C++). Revert that in favor of a simpler, architecture-independent fix: - Restore the original HAS_AVX / HAS_ARM_NEON intrinsics at the affected call sites, keeping the newer conflictMask16 helper and scalar fallback. - memset Node16::index in both copy constructors (from Node3 and Node48) so the [numChildren, 16) tail is always initialized, making the full 16-byte SIMD loads well-defined. This also fixes the same latent UB in the NEON path and the Node16->Node16 full-array memcpy. - Issue a VALGRIND_MAKE_MEM_UNDEFINED client request on the tail so valgrind still flags any read that relies on the unused slots rather than numChildren. - Drop simd.h, simd_x86_64.S, simd_aarch64.S, and the CMake ASM wiring.	2026-08-03 17:32:41 -04:00
andrew	b11e92ee0b	Merge pull request 'Move aarch64 Node16 SIMD index loads into assembly' (#76 ) from weaselbot/conflict-set:weaselbot/issue-68 into main Reviewed-on: weaselab/conflict-set#76	2026-08-03 13:42:45 +00:00
weaselbot	e02dd41f74	Address review: drop unused bti c landing pads, fix rationale comment	2026-08-03 09:17:28 -04:00
andrew	b0e326aacc	Merge pull request 'ci: run MSan on arm64' (#74 ) from weaselbot/conflict-set:weaselbot/issue-73 into main Reviewed-on: weaselab/conflict-set#74	2026-08-03 12:27:49 +00:00
andrew	1179c1f56e	Merge pull request 'Fix ARM NEON scan helpers truncating 64-bit versions' (#75 ) from weaselbot/conflict-set:weaselbot/issue-69 into main Reviewed-on: weaselab/conflict-set#75	2026-08-03 12:26:03 +00:00
andrew	bdbac1556d	Merge pull request 'Correct rationale in simd_x86_64.S comment' (#72 ) from weaselbot/conflict-set:weaselbot/issue-71 into main Reviewed-on: weaselab/conflict-set#72	2026-08-03 04:59:26 +00:00
andrew	0103837488	Merge pull request 'Run valgrind in arm64 release in CI' (#70 ) from valgrind-in-arm into main Reviewed-on: weaselab/conflict-set#70	2026-08-03 04:34:34 +00:00
weaselbot	d040ed63a4	Move aarch64 Node16 SIMD index loads into assembly The aarch64 NEON paths in getNodeIndex/getNodeIndexExists, getChildGeq(Node16*), scan16, and checkMaxBetweenExclusiveImpl<Node16> loaded the full 16-element Node16::index array (and the Node48 reverseIndex array via scan16) with NEON intrinsics, then masked the result down to [0, numChildren). Only the in-use slots are initialized; the unused bytes are indeterminate, so the wide loads were undefined behavior in C++ (per [basic.indet]) even though the trailing lanes were discarded. MSan reports this on x86-64; on aarch64 it is the same UB but MSan's imprecise modeling doesn't flag it at -O0, so there is no red->green test. Mirror the existing x86-64 fix (commit `6fed133`): implement the index operations in file-level assembly, where loading and operating on indeterminate values is well-defined. Add simd_aarch64.S with find_eq_16, find_ge_16, and mask_in_range_16. AArch64 lacks pmovmskb, so (like the prior NEON code) these return a 64-bit nibble mask rather than a 16-bit bitmask; the C++ call sites keep their existing nibble-mask arithmetic and only swap the inline NEON load/compare for the assembly call. The childMaxVersion compares stay in C++ NEON intrinsics, matching x86-64's compare16: those slots are always initialized to zero by the allocator, so the wide loads are defined. The assembly functions carry `bti c` landing pads and the same aeabi_feature_and_bits attributes the compiler emits for -mbranch-protection=standard, so the object stays BTI/PAC/GCS-compatible (and warning-free under -z force-bti). CMakeLists.txt builds simd_aarch64.S into the object library and the SIMD test/bench/fuzz targets on aarch64. Closes #68	2026-08-02 23:48:28 -04:00
weaselbot	6b1f597d77	Fix ARM NEON scan helpers truncating 64-bit versions When USE_64_BIT=1, InternalVersionT stores an int64_t, but the aarch64 NEON fast paths in scan16 (both the indexed Node48 variant and the Node256 variant) and checkMaxBetweenExclusiveImpl(Node16) only copied the low 32 bits of each version into uint32x4_t lanes and compared against a truncated 32-bit readVersion. This produced wrong conflict/commit decisions once any version exceeded 2^32 - 1. Extract the per-version "greater than readVersion" computation into a shared conflictMask16 helper. For 64-bit versions it uses vcgtq_s64 on the full int64 values and narrows the resulting 16-byte mask into the same nibble-packed layout the callers already consume. The 32-bit path is preserved unchanged. Closes #69	2026-08-02 23:35:32 -04:00
weaselbot	70630649d9	ci: run MSan on arm64 Add a debug-arm64 matrix entry to the test job that runs the MSan fuzz tests on an arm64 runner. The arm instrumented libc++ toolchain (22.1.8) is built against LLVM 22, so this entry installs clang-22 from apt.llvm.org while the existing amd64 entries keep clang-21. Generalize the test job matrix with runner/arch/llvm_version/msan_url fields so the runner, apt cache key, LLVM toolchain version, and MSan toolchain download URL are selected per matrix entry. Closes #73	2026-08-02 23:28:40 -04:00
weaselbot	0b12a037c4	Correct rationale in simd_x86_64.S comment The SIMD operations are written in assembly because loading and operating on indeterminate values is UB in C++ but well-defined in assembly. msan not tracking the loads is a side effect, not the reason. Closes #71	2026-08-03 02:37:18 +00:00
andrew	79113ecb88	Run valgrind in arm64 release in CI	2026-08-03 02:36:45 +00:00
andrew	5c16b8ee90	Add .note.gnu.property section for CET/CFI to simd_x86_64.S The assembly file was missing the GNU property note that records control-flow integrity (CET) support, causing hardening-check to report 'Control flow integrity: no, not found!'. Add the note matching what clang emits with -fcf-protection.	2026-08-02 22:31:56 -04:00
andrew	b19981ee3c	Only pass -stdlib=libc++ for c++	2026-08-02 21:34:22 -04:00
andrew	12650e2132	Update README.md	2026-08-02 21:16:27 -04:00
andrew	6fed133212	Remove UB from indeterminate value handling Move SIMD operations on potentially-indeterminate Node16::index bytes into file-level assembly, where loading and operating on indeterminate values is well-defined (unlike C++). Restructure scalar fallback loops to iterate [0, numChildren) instead of [0, kMaxNodes). Fix TrivialSpan construction from indeterminate pointers in check::Job::init and insertPointWritesOrSorted to only construct when end.len > 0. Add MSan toolchain to the debug CI build to catch these issues going forward.	2026-08-02 21:06:53 -04:00
andrew	9d15af772e	Run msan in CI. Closes #66	2026-07-23 15:16:58 -04:00
andrew	22159c38c5	Add Grafana dashboard for server bench metrics	2026-07-23 13:38:56 -04:00