Include <sys/syscall.h> in ServerBench.cpp for SYS_perf_event_open

`ServerBench.cpp` calls `syscall(SYS_perf_event_open, ...)` but did
not include `<sys/syscall.h>`, relying on `<unistd.h>` to transitively
provide the `SYS_*` constants. On toolchains where that does not happen,
the build fails with `SYS_perf_event_open` not declared.

Add the missing include so `server_bench` compiles on any platform that
provides `perf_event_open`.

Resolves weaselab/conflict-set#41.

.gitea/workflows/ci.yml

@@ -2,37 +2,62 @@ name: CI
 
 on: [push, pull_request]
 
-env:
-  CC: clang
-  CXX: clang++
-
 jobs:
-  pre-commit:
-    runs-on: ubuntu-latest-amd64
+  build-image:
+    strategy:
+      fail-fast: false
+      matrix:
+        include:
+          - runner: ubuntu-latest-amd64
+            arch: amd64
+          - runner: ubuntu-latest-arm64
+            arch: arm64
+    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') }}
-
-      - name: Install dependencies
+      - name: Log in to registry
+        env:
+          REGISTRY_USER: ${{ secrets.REGISTRY_USER }}
+          REGISTRY_TOKEN: ${{ secrets.REGISTRY_TOKEN }}
         run: |
-          sudo apt-get update -qq
-          sudo apt-get install -y git nodejs pre-commit
+          echo "$REGISTRY_TOKEN" \
+            | docker login -u "$REGISTRY_USER" --password-stdin git.weaselab.dev
 
-      - uses: actions/cache@v4
-        with:
-          path: ~/.cache/pre-commit
-          key: pre-commit-${{ hashFiles('.pre-commit-config.yaml') }}
+      - name: Build and push image if changed
+        run: |
+          image=git.weaselab.dev/weaselab/conflict-set-ci
+          hash="$(sha256sum Dockerfile .pre-commit-config.yaml | sha256sum | cut -c 1-16)"
+          latest="$image:latest-${{ matrix.arch }}"
+          current="$(docker buildx imagetools inspect "$latest" \
+            --format '{{index .Image.Config.Labels "dev.weaselab.ci-hash"}}' 2> /dev/null || true)"
+          if [ "$current" = "$hash" ]; then
+            echo "$latest is up to date"
+          else
+            docker build --push --label "dev.weaselab.ci-hash=$hash" -t "$latest" .
+          fi
+
+  pre-commit:
+    needs: build-image
+    runs-on: ubuntu-latest-amd64
+    container:
+      image: git.weaselab.dev/weaselab/conflict-set-ci:latest-amd64
+      credentials:
+        username: ${{ secrets.REGISTRY_USER }}
+        password: ${{ secrets.REGISTRY_TOKEN }}
+    steps:
+      - uses: actions/checkout@v4
 
       - name: Run pre-commit
+        env:
+          # use the hooks pre-installed in the image
+          HOME: /tmp
         run: |
           git config --global --add safe.directory "$PWD"
           pre-commit run --all-files --show-diff-on-failure
 
   test:
+    needs: build-image
     strategy:
       fail-fast: false
       matrix:
@@ -46,35 +71,20 @@ jobs:
           - name: gcc
             cmake_args: -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++
     runs-on: ubuntu-latest-amd64
+    container:
+      image: git.weaselab.dev/weaselab/conflict-set-ci:latest-amd64
+      credentials:
+        username: ${{ secrets.REGISTRY_USER }}
+        password: ${{ secrets.REGISTRY_TOKEN }}
     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 common dependencies
-        run: |
-          sudo apt-get update -qq
-          sudo apt-get install -y \
-            build-essential ccache cmake gcc g++ libc6-dbg \
-            ninja-build python3 valgrind 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
-
-      - name: Install LLVM toolchain
-        if: matrix.name != 'gcc'
-        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 \
-            clang-21 llvm-21 lld-21 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
-          done
+          path: .ccache
+          key: ccache-${{ matrix.name }}-${{ gitea.sha }}
+          restore-keys: |
+            ccache-${{ matrix.name }}-
 
       - name: Build
         run: |
@@ -110,6 +120,7 @@ jobs:
             | tee -a "$GITHUB_STEP_SUMMARY"
 
   release:
+    needs: build-image
     strategy:
       fail-fast: false
       matrix:
@@ -119,38 +130,14 @@ jobs:
           - runner: ubuntu-latest-arm64
             arch: arm64
     runs-on: ${{ matrix.runner }}
+    container:
+      image: git.weaselab.dev/weaselab/conflict-set-ci:latest-${{ matrix.arch }}
+      credentials:
+        username: ${{ secrets.REGISTRY_USER }}
+        password: ${{ secrets.REGISTRY_TOKEN }}
     steps:
       - uses: actions/checkout@v4
 
-      - uses: actions/cache@v4
-        with:
-          path: /var/cache/apt/archives
-          key: apt-${{ matrix.arch }}-${{ 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 devscripts \
-            libc6-dbg llvm-21 lld-21 mold ninja-build rpm \
-            valgrind 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: Install paper build dependencies
-        if: matrix.arch == 'amd64'
-        run: |
-          sudo apt-get install -y \
-            biber latexmk \
-            texlive-bibtex-extra texlive-fonts-recommended \
-            texlive-latex-extra texlive-pictures
-
       - uses: actions/cache@v4
         with:
           path: .ccache
@@ -201,6 +188,9 @@ jobs:
           dest="minio/jenkins/conflict-set/${{ gitea.run_number }}/release-${{ matrix.arch }}/"
           zstd build/Testing/*/Test.xml
           mc cp build/Testing/*/Test.xml.zst "$dest"
+          # This step runs even when a previous step failed, to upload test
+          # results. The packages may never have been built though, so skip
+          # them if they're missing.
           if compgen -G "build/*.deb" > /dev/null; then
             mc cp build/*.deb "$dest"
           fi
@@ -218,114 +208,17 @@ 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:
+    needs: build-image
     runs-on: ubuntu-latest-amd64
+    container:
+      image: git.weaselab.dev/weaselab/conflict-set-ci:latest-amd64
+      credentials:
+        username: ${{ secrets.REGISTRY_USER }}
+        password: ${{ secrets.REGISTRY_TOKEN }}
     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 gcovr \
-            libc6-dbg llvm-21 lld-21 mold ninja-build python3 valgrind 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
-
       - uses: actions/cache@v4
         with:
           path: .ccache

Bench.cpp

@@ -37,16 +37,15 @@ ConflictSet::ReadRange singleton(Arena &arena, TrivialSpan key) {
 }
 
 ConflictSet::ReadRange prefixRange(Arena &arena, TrivialSpan key) {
-  int index = key.size() - 1;
-  for (; index >= 0; index--)
-    if (key[index] != 255)
+  int index;
+  for (index = key.size() - 1; index >= 0; index--)
+    if ((key[index]) != 255)
       break;
 
   // Must not be called with a string that consists only of zero or more '\xff'
-  // bytes, or with an empty string (which has no finite upper bound).
+  // bytes.
   if (index < 0) {
     assert(false);
-    std::abort();
   }
 
   uint8_t *buf = new (arena) uint8_t[index + 1];

CMakeLists.txt

@@ -1,7 +1,7 @@
 cmake_minimum_required(VERSION 3.18)
 project(
   conflict-set
-  VERSION 0.1.0
+  VERSION 0.0.14
   DESCRIPTION
     "A data structure for optimistic concurrency control on ranges of bitwise-lexicographically-ordered keys."
   HOMEPAGE_URL "https://git.weaselab.dev/weaselab/conflict-set"
@@ -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,8 +103,6 @@ option(USE_SIMD_FALLBACK
 
 option(DISABLE_TSAN "Disable TSAN" OFF)
 
-option(USE_MSAN "Build with MemorySanitizer (disables ASan/UBSan)" OFF)
-
 # This is encouraged according to
 # https://valgrind.org/docs/manual/manual-core-adv.html#manual-core-adv.clientreq
 include_directories(SYSTEM ${CMAKE_CURRENT_SOURCE_DIR}/third_party/valgrind)
@@ -153,7 +139,6 @@ add_custom_command(
   COMMAND_EXPAND_LISTS)
 
 add_library(${PROJECT_NAME} SHARED ${CMAKE_BINARY_DIR}/${PROJECT_NAME}.o)
-add_dependencies(${PROJECT_NAME} ${PROJECT_NAME}-object)
 set_target_properties(
   ${PROJECT_NAME} PROPERTIES LIBRARY_OUTPUT_DIRECTORY
                              "${CMAKE_CURRENT_BINARY_DIR}/radix_tree")
@@ -170,7 +155,6 @@ if(HAS_VERSION_SCRIPT)
 endif()
 
 add_library(${PROJECT_NAME}-static STATIC ${CMAKE_BINARY_DIR}/${PROJECT_NAME}.o)
-add_dependencies(${PROJECT_NAME}-static ${PROJECT_NAME}-object)
 if(CMAKE_BUILD_TYPE STREQUAL Debug)
   set_target_properties(${PROJECT_NAME}-static PROPERTIES LINKER_LANGUAGE CXX)
 else()
@@ -246,10 +230,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()
@@ -273,13 +255,8 @@ if(CMAKE_SOURCE_DIR STREQUAL CMAKE_CURRENT_SOURCE_DIR AND BUILD_TESTING)
   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
@@ -290,9 +267,7 @@ if(CMAKE_SOURCE_DIR STREQUAL CMAKE_CURRENT_SOURCE_DIR AND BUILD_TESTING)
   endforeach()
 
   # 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)
@@ -408,25 +383,13 @@ if(CMAKE_SOURCE_DIR STREQUAL CMAKE_CURRENT_SOURCE_DIR AND BUILD_TESTING)
   if(NOT CMAKE_CROSSCOMPILING)
     find_program(HARDENING_CHECK hardening-check)
     if(HARDENING_CHECK)
-      # Not all versions of hardening-check support the same options, so query
-      # the help output before using architecture-specific skips.
-      execute_process(
-        COMMAND ${HARDENING_CHECK} --help
-        OUTPUT_VARIABLE hardening_check_help
-        ERROR_VARIABLE hardening_check_help
-        OUTPUT_STRIP_TRAILING_WHITESPACE ERROR_STRIP_TRAILING_WHITESPACE)
-      set(hardening_check_arch_flags "")
       # Control flow integrity (CET) is x86-only and branch protection (PAC/BTI)
       # is arm64-only, so ignore whichever doesn't apply.
       if(CMAKE_SYSTEM_PROCESSOR STREQUAL aarch64 OR CMAKE_SYSTEM_PROCESSOR
                                                     STREQUAL arm64)
-        if(hardening_check_help MATCHES "nocfprotection")
-          list(APPEND hardening_check_arch_flags --nocfprotection)
-        endif()
+        set(hardening_check_arch_flags --nocfprotection)
       else()
-        if(hardening_check_help MATCHES "nobranchprotection")
-          list(APPEND hardening_check_arch_flags --nobranchprotection)
-        endif()
+        set(hardening_check_arch_flags --nobranchprotection)
       endif()
       add_test(
         NAME hardening_check
@@ -514,11 +477,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})

ConflictSet.cpp

@@ -3864,10 +3864,11 @@ PRESERVE_NONE void right_side_iter(Job *job, Context *context) {
 void Job::init(const ConflictSet::ReadRange *read, ConflictSet::Result *result,
                Node *root, int64_t oldestVersionFullPrecision) {
   auto begin = TrivialSpan(read->begin.p, read->begin.len);
+  auto end = TrivialSpan(read->end.p, read->end.len);
   if (read->readVersion < oldestVersionFullPrecision) [[unlikely]] {
     *result = ConflictSet::TooOld;
     continuation = complete;
-  } else if (read->end.len == 0) {
+  } else if (end.size() == 0) {
     this->begin = begin;
     this->n = root;
     this->readVersion = InternalVersionT(read->readVersion);
@@ -3875,7 +3876,7 @@ void Job::init(const ConflictSet::ReadRange *read, ConflictSet::Result *result,
     continuation = check::point_read_state_machine::begin;
   } else {
     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;
@@ -5045,8 +5046,8 @@ struct __attribute__((visibility("hidden"))) ConflictSet::Impl {
       for (int i = 0; i < count; ++i) {
         const auto &w = writes[i];
         auto begin = TrivialSpan(w.begin.p, w.begin.len);
+        auto end = TrivialSpan(w.end.p, w.end.len);
         if (w.end.len > 0) {
-          auto end = TrivialSpan(w.end.p, w.end.len);
           addWriteRange(rootParent->children[0], begin, end,
                         InternalVersionT(writeVersion), &writeContext);
         } else {
@@ -5588,12 +5589,7 @@ ConflictSet::ConflictSet(ConflictSet &&other) noexcept
     : impl(std::exchange(other.impl, nullptr)) {}
 
 ConflictSet &ConflictSet::operator=(ConflictSet &&other) noexcept {
-  if (this != &other) {
-    if (impl) {
-      internal_destroy(impl);
-    }
-    impl = std::exchange(other.impl, nullptr);
-  }
+  impl = std::exchange(other.impl, nullptr);
   return *this;
 }
 
@@ -5678,13 +5674,13 @@ std::string getPartialKeyPrintable(Node *n) {
 }
 
 std::string strinc(std::string_view str, bool &ok) {
-  int index = static_cast<int>(str.size()) - 1;
-  for (; index >= 0; index--)
-    if (static_cast<uint8_t>(str[index]) != 255)
+  int index;
+  for (index = str.size() - 1; index >= 0; index--)
+    if ((uint8_t &)(str[index]) != 255)
       break;
 
   // Must not be called with a string that consists only of zero or more
-  // '\xff' bytes, and the empty string has no successor.
+  // '\xff' bytes.
   if (index < 0) {
     ok = false;
     return {};
@@ -5692,8 +5688,7 @@ std::string strinc(std::string_view str, bool &ok) {
   ok = true;
 
   auto r = std::string(str.substr(0, index + 1));
-  auto &last = r[r.size() - 1];
-  last = static_cast<char>(static_cast<uint8_t>(last) + 1);
+  ((uint8_t &)r[r.size() - 1])++;
   return r;
 }
 

Dockerfile

@@ -0,0 +1,46 @@
+FROM ubuntu:rolling
+
+WORKDIR /tmp
+ENV HOME=/tmp
+RUN chmod -R 777 /tmp
+
+# Install apt dependencies
+RUN apt-get update
+RUN apt-get upgrade -y
+RUN TZ=America/Los_Angeles DEBIAN_FRONTEND=noninteractive apt-get install -y \
+    biber \
+    build-essential \
+    ccache \
+    clang \
+    cmake \
+    curl \
+    devscripts \
+    gcovr \
+    git \
+    latexmk \
+    libc6-dbg \
+    llvm \
+    mold \
+    ninja-build \
+    nodejs \
+    pre-commit \
+    python3-requests \
+    rpm \
+    texlive-bibtex-extra \
+    texlive-fonts-recommended \
+    texlive-latex-extra \
+    texlive-pictures \
+    valgrind \
+    wget \
+    zstd
+
+# MinIO client, for uploading build artifacts
+RUN curl -Ls "https://dl.min.io/client/mc/release/linux-$(dpkg --print-architecture)/mc" \
+    -o /usr/local/bin/mc && chmod +x /usr/local/bin/mc
+
+ENV CC=clang
+ENV CXX=clang++
+
+# Try to have all the pre-commit hooks we'll need already initialized
+COPY .pre-commit-config.yaml /tmp/
+RUN git init && pre-commit install-hooks

HashTable.cpp

@@ -96,9 +96,7 @@ void ConflictSet::setOldestVersion(int64_t oldestVersion) {
   return impl->setOldestVersion(oldestVersion);
 }
 
-// The hash_table implementation does not track memory usage, so return 0 to
-// satisfy the API contract that getBytes() returns a non-negative value.
-int64_t ConflictSet::getBytes() const { return 0; }
+int64_t ConflictSet::getBytes() const { return -1; }
 
 void ConflictSet::getMetricsV1(MetricsV1 **metrics, int *count) const {
   *metrics = nullptr;
@@ -121,13 +119,7 @@ ConflictSet::ConflictSet(ConflictSet &&other) noexcept
     : impl(std::exchange(other.impl, nullptr)) {}
 
 ConflictSet &ConflictSet::operator=(ConflictSet &&other) noexcept {
-  if (this != &other) {
-    if (impl) {
-      impl->~Impl();
-      safe_free(impl, sizeof(Impl));
-    }
-    impl = std::exchange(other.impl, nullptr);
-  }
+  impl = std::exchange(other.impl, nullptr);
   return *this;
 }
 
@@ -163,10 +155,7 @@ __attribute__((__visibility__("default"))) void ConflictSet_destroy(void *cs) {
 }
 __attribute__((__visibility__("default"))) int64_t
 ConflictSet_getBytes(void *cs) {
-  (void)cs;
-  // The hash_table implementation does not track memory usage, so return 0 to
-  // satisfy the API contract that ConflictSet_getBytes returns a non-negative
-  // value.
-  return 0;
+  using Impl = ConflictSet::Impl;
+  return -1;
 }
 }

RealDataBench.cpp

@@ -1,6 +1,5 @@
 #include <ConflictSet.h>
 
-#include <algorithm>
 #include <cerrno>
 #include <chrono>
 #include <cstdio>
@@ -78,10 +77,10 @@ int main(int argc, const char **argv) {
       begin = end + 1;
       end = (uint8_t *)memchr(begin, '\n', size);
 
-      if (line.size() >= 2 && line[0] == 'P') {
-        write = line.subspan(2, line.size() - 2);
-      } else if (line.size() >= 2 && line[0] == 'L') {
-        reads.push_back(line.subspan(2, line.size() - 2));
+      if (line.size() > 0 && line[0] == 'P') {
+        write = line.subspan(2, line.size());
+      } else if (line.size() > 0 && line[0] == 'L') {
+        reads.push_back(line.subspan(2, line.size()));
       } else if (line.empty()) {
         {
           readRanges.resize(reads.size());
@@ -91,7 +90,7 @@ int main(int argc, const char **argv) {
             iter->begin.len = read.size();
             checkBytes += read.size();
             iter->end.len = 0;
-            iter->readVersion = std::max<int64_t>(0, version - 100);
+            iter->readVersion = version - 100;
             ++iter;
           }
         }
@@ -122,7 +121,7 @@ int main(int argc, const char **argv) {
         }
 
         timer = now();
-        cs.setOldestVersion(std::max<int64_t>(0, version - 10000));
+        cs.setOldestVersion(version - 10000);
         gcTime += now() - timer;
       }
     }

SkipList.cpp

@@ -38,9 +38,6 @@ std::span<const uint8_t> keyAfter(Arena &arena, std::span<const uint8_t> key) {
 
 std::span<const uint8_t> copyToArena(Arena &arena,
                                      std::span<const uint8_t> key) {
-  if (key.size() == 0) {
-    return std::span<const uint8_t>();
-  }
   auto result = std::span<uint8_t>(new (arena) uint8_t[key.size()], key.size());
   memcpy(result.data(), key.data(), key.size());
   return result;
@@ -100,7 +97,7 @@ force_inline bool getCharacter(const KeyInfo &ki, int character,
 
 bool operator<(const KeyInfo &lhs, const KeyInfo &rhs) {
   int i = std::min(lhs.key.size(), rhs.key.size());
-  int c = i > 0 ? memcmp(lhs.key.data(), rhs.key.data(), i) : 0;
+  int c = memcmp(lhs.key.data(), rhs.key.data(), i);
   if (c != 0)
     return c < 0;
 
@@ -290,8 +287,7 @@ private:
 
   static force_inline bool less(const uint8_t *a, int aLen, const uint8_t *b,
                                 int bLen) {
-    int n = std::min(aLen, bLen);
-    int c = n > 0 ? memcmp(a, b, n) : 0;
+    int c = memcmp(a, b, std::min(aLen, bLen));
     if (c < 0)
       return true;
     if (c > 0)
@@ -758,8 +754,7 @@ struct __attribute__((visibility("hidden"))) ConflictSet::Impl {
 
   void addWrites(const ConflictSet::WriteRange *writes, int count,
                  int64_t writeVersion) {
-    auto points = std::vector<KeyInfo>();
-    points.reserve(count * 2);
+    auto points = std::vector<KeyInfo>(count * 2);
     Arena arena;
 
     for (int r = 0; r < count; r++) {
@@ -986,12 +981,7 @@ ConflictSet::ConflictSet(ConflictSet &&other) noexcept
     : impl(std::exchange(other.impl, nullptr)) {}
 
 ConflictSet &ConflictSet::operator=(ConflictSet &&other) noexcept {
-  if (this != &other) {
-    if (impl) {
-      internal_destroy(impl);
-    }
-    impl = std::exchange(other.impl, nullptr);
-  }
+  impl = std::exchange(other.impl, nullptr);
   return *this;
 }
 

build_msan_toolchain.sh

@@ -1,43 +0,0 @@
-#!/bin/bash
-
-set -euxo pipefail
-
-LLVM_VERSION="${LLVM_VERSION:-21}"
-MSAN_PREFIX="${MSAN_PREFIX:-$PWD/msan}"
-JOBS="${JOBS:-$(nproc)}"
-
-cd /tmp
-rm -rf libcxx-msan
-mkdir libcxx-msan
-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 \
-  -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_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
-
-cmake --build build -j"${JOBS}"
-cmake --install build
-
-VERSION="$(clang-"${LLVM_VERSION}" --version | head -n1 | sed -E 's/.*clang version ([0-9.]+).*/\1/')"
-TARBALL="msan-toolchain-${VERSION}.tar.zst"
-
-tar --zstd -cf "${TARBALL}" -C "${MSAN_PREFIX}" .
-
-TARBALL_PATH="$(pwd)/${TARBALL}"
-echo "Created: ${TARBALL_PATH}"

conflict_set.py

@@ -27,37 +27,23 @@ class Result(enum.Enum):
     TOO_OLD = 2
 
 
-def _make_key(buf: bytes) -> tuple[_Key, bytearray]:
-    """Create a _Key and a backing bytearray that must be kept alive."""
-    backing = bytearray(buf)
-    array = (ctypes.c_ubyte * len(backing)).from_buffer(backing)
-    return _Key(array, len(array)), backing
-
-
 def write(begin: bytes, end: Optional[bytes] = None) -> WriteRange:
-    begin_key, begin_buf = _make_key(begin)
+    b = (ctypes.c_ubyte * len(begin)).from_buffer(bytearray(begin))
+
     if end is None:
-        end_key = _Key((ctypes.c_ubyte * 0)(), 0)
-        end_buf = None
+        e = (ctypes.c_ubyte * 0)()
     else:
-        end_key, end_buf = _make_key(end)
-    result = WriteRange(begin_key, end_key)
-    result._begin_buf = begin_buf
-    result._end_buf = end_buf
-    return result
+        e = (ctypes.c_ubyte * len(end)).from_buffer(bytearray(end))
+    return WriteRange(_Key(b, len(b)), _Key(e, len(e)))
 
 
 def read(version: int, begin: bytes, end: Optional[bytes] = None) -> ReadRange:
-    begin_key, begin_buf = _make_key(begin)
+    b = (ctypes.c_ubyte * len(begin)).from_buffer(bytearray(begin))
     if end is None:
-        end_key = _Key((ctypes.c_ubyte * 0)(), 0)
-        end_buf = None
+        e = (ctypes.c_ubyte * 0)()
     else:
-        end_key, end_buf = _make_key(end)
-    result = ReadRange(begin_key, end_key, version)
-    result._begin_buf = begin_buf
-    result._end_buf = end_buf
-    return result
+        e = (ctypes.c_ubyte * len(end)).from_buffer(bytearray(end))
+    return ReadRange(_Key(b, len(b)), _Key(e, len(e)), version)
 
 
 class ConflictSet:
@@ -102,7 +88,6 @@ class ConflictSet:
             ctypes.POINTER(ctypes.c_int),
             ctypes.c_int,
         )
-        self._lib.ConflictSet_check.restype = None
 
         self._lib.ConflictSet_addWrites.argtypes = (
             ctypes.c_void_p,
@@ -110,16 +95,13 @@ class ConflictSet:
             ctypes.c_int,
             ctypes.c_int64,
         )
-        self._lib.ConflictSet_addWrites.restype = None
 
         self._lib.ConflictSet_setOldestVersion.argtypes = (
             ctypes.c_void_p,
             ctypes.c_int64,
         )
-        self._lib.ConflictSet_setOldestVersion.restype = None
 
         self._lib.ConflictSet_destroy.argtypes = (ctypes.c_void_p,)
-        self._lib.ConflictSet_destroy.restype = None
 
         self._lib.ConflictSet_getBytes.argtypes = (ctypes.c_void_p,)
         self._lib.ConflictSet_getBytes.restype = ctypes.c_int64

include/ConflictSet.h

@@ -88,8 +88,7 @@ struct __attribute__((__visibility__("default"))) ConflictSet {
 
   ~ConflictSet();
 
-  /** Returns the total bytes in use by this ConflictSet. Implementations that
-   * do not track memory usage return 0. */
+  /** Returns the total bytes in use by this ConflictSet */
   int64_t getBytes() const;
 
   /** Experimental! */
@@ -133,13 +132,6 @@ struct __attribute__((__visibility__("default"))) ConflictSet {
 
 private:
   Impl *impl;
-#if __cplusplus <= 199711L
-  /* Declared private and left undefined to prevent copying in C++98/C++03.
-     The compiler would otherwise implicitly generate public copy operations,
-     which share the opaque Impl* and cause a double-free. */
-  ConflictSet(const ConflictSet &);
-  ConflictSet &operator=(const ConflictSet &);
-#endif
 };
 } /* namespace weaselab */
 
@@ -219,8 +211,7 @@ ConflictSet *ConflictSet_create(int64_t oldestVersion);
 
 void ConflictSet_destroy(ConflictSet *cs);
 
-/** Returns the total bytes in use by this ConflictSet. Implementations that
- * do not track memory usage return 0. */
+/** Returns the total bytes in use by this ConflictSet */
 int64_t ConflictSet_getBytes(const ConflictSet *cs);
 
 #endif

test_conflict_set.py

@@ -57,53 +57,6 @@ def test_conflict_set():
         assert cs.check(read(0, key), read(1, key)) == [Result.TOO_OLD, Result.COMMIT]
 
 
-def test_hash_table_getBytes():
-    # Regression test for issue #62: the hash_table implementation is
-    # point-query only and does not track memory usage, but getBytes() must
-    # still return a non-negative value rather than -1.
-    with ConflictSet(0, build_dir=build_dir, implementation="hash_table") as cs:
-        assert cs.getBytes() == 0
-        cs.addWrites(1, write(b"key"))
-        assert cs.getBytes() >= 0
-        assert cs.check(read(0, b"key")) == [Result.CONFLICT]
-
-
-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
-    # stored in _Key while addWrites/check run.
-    with DebugConflictSet() as cs:
-        # The bytes literal is not referenced after this expression.
-        cs.addWrites(1, write(b"key"))
-        assert cs.check(read(0, b"key")) == [Result.CONFLICT]
-
-        cs.addWrites(2, write(b"a", b"z"))
-        assert cs.check(read(1, b"a", b"z")) == [Result.CONFLICT]
-        assert cs.check(read(1, b"b")) == [Result.CONFLICT]
-        assert cs.check(read(1, b"0")) == [Result.COMMIT]
-
-
-def test_range_keeps_key_buffers_alive():
-    # Verify the fix for issue #42: returned range objects must retain a
-    # reference to the backing bytearray so the C pointer stays valid after
-    # the helper returns.
-    w = write(b"key")
-    assert w._begin_buf == bytearray(b"key")
-    assert w._end_buf is None
-
-    w2 = write(b"a", b"z")
-    assert w2._begin_buf == bytearray(b"a")
-    assert w2._end_buf == bytearray(b"z")
-
-    r = read(0, b"key")
-    assert r._begin_buf == bytearray(b"key")
-    assert r._end_buf is None
-
-    r2 = read(1, b"a", b"z")
-    assert r2._begin_buf == bytearray(b"a")
-    assert r2._end_buf == bytearray(b"z")
-
-
 def test_update_zero_should_commit():
     with DebugConflictSet() as cs1:
         with DebugConflictSet() as cs2:
@@ -115,7 +68,7 @@ def test_update_zero_should_commit():
             for i in range(256 - 17, 256):
                 cs2.addWrites(int(1), write(bytes([i])))
             # Scan until first point write
-            assert cs2.check(read(0, b"\x00", bytes([256 - 17]))) == [Result.COMMIT]
+            cs2.check(read(0, b"\x00", bytes([256 - 17])))
 
 
 def test_update_zero_should_conflict():
@@ -128,7 +81,7 @@ def test_update_zero_should_conflict():
             # "zero" is now 2**31 + 100
             cs1.addWrites(2**32 + 101, write(b"", b"\x02"), write(b"\x01"))
             # rangeVersion of \x01 is now 2**31 + 100 ("max" of (2**31 + 100, 2**32 + 101))
-            assert cs1.check(read(2**32 + 1, b"\x00")) == [Result.CONFLICT]
+            cs1.check(read(2**32 + 1, b"\x00"))
             # but 2**32 + 1 ">" 2**31 + 100 , and it incorrectly commits