SkipList: guard memcpy/memcmp against null pointers in keyAfter and friends #105

Merged
andrew merged 1 commits from weaselbot/conflict-set:weaselbot/issue-96 into main 2026-11-19 20:04:26 +00:00
Member

Closes #96

keyAfter() copied the caller's key with an unguarded memcpy, so a zero-length key spelled with a null pointer (which ConflictSet.h allows -- it only constrains Key::len) became memcpy(dst, nullptr, 0). That is undefined behavior even though the count is 0, and keyAfter() runs for every point read and point write, so any empty-key point operation trapped in a UBSan build.

Commit 2231c09 fixed this pattern in operator<(const KeyInfo&), SkipList::less and copyToArena, but missed keyAfter().

Changes

  • keyAfter(): guard the memcpy with if (key.size() > 0), matching copyToArena.
  • compare(), Finger::found() and the point-read fast path in CheckMax::advance(): guard the remaining unguarded memcmp calls through a small equalBytes() helper (the CheckMax::advance() site compares against start.value, a read range's begin, which may also be a null-pointer empty key).
  • test_empty_key_null_pointer: bisimulates both implementations on an empty key spelled with {NULL, 0} for both a point write and a point read, and checks that the same operations spelled with a non-null empty key agree.

Testing

  • The reproduction from the issue, built against SkipList.cpp with -fsanitize=undefined -fno-sanitize-recover=all, aborts on SkipList.cpp:34 before this change and prints check -> 0 / write ok after (also clean under -fsanitize=address,undefined).
  • The new test fails with the same UBSan trap against the pre-patch SkipList.cpp and passes after.
  • Full suite: ninja -C build && ctest -j 8 -> 8603/8603 passed (Debug build, with valgrind and scripted tests).
  • Opt-in driver_skip_list corpus cross-check: built with -DTEST_SKIP_LIST=ON and UBSan over the whole corpus (2845 files), no traps.
  • All scripted tests re-run against a skip_list library built with UBSan: no failures.
  • clang-format and black are clean.
Closes #96 `keyAfter()` copied the caller's key with an unguarded `memcpy`, so a zero-length key spelled with a null pointer (which `ConflictSet.h` allows -- it only constrains `Key::len`) became `memcpy(dst, nullptr, 0)`. That is undefined behavior even though the count is 0, and `keyAfter()` runs for every point read and point write, so any empty-key point operation trapped in a UBSan build. Commit 2231c09 fixed this pattern in `operator<(const KeyInfo&)`, `SkipList::less` and `copyToArena`, but missed `keyAfter()`. ## Changes * `keyAfter()`: guard the `memcpy` with `if (key.size() > 0)`, matching `copyToArena`. * `compare()`, `Finger::found()` and the point-read fast path in `CheckMax::advance()`: guard the remaining unguarded `memcmp` calls through a small `equalBytes()` helper (the `CheckMax::advance()` site compares against `start.value`, a read range's `begin`, which may also be a null-pointer empty key). * `test_empty_key_null_pointer`: bisimulates both implementations on an empty key spelled with `{NULL, 0}` for both a point write and a point read, and checks that the same operations spelled with a non-null empty key agree. ## Testing * The reproduction from the issue, built against `SkipList.cpp` with `-fsanitize=undefined -fno-sanitize-recover=all`, aborts on `SkipList.cpp:34` before this change and prints `check -> 0` / `write ok` after (also clean under `-fsanitize=address,undefined`). * The new test fails with the same UBSan trap against the pre-patch `SkipList.cpp` and passes after. * Full suite: `ninja -C build && ctest -j 8` -> 8603/8603 passed (Debug build, with valgrind and scripted tests). * Opt-in `driver_skip_list` corpus cross-check: built with `-DTEST_SKIP_LIST=ON` and UBSan over the whole corpus (2845 files), no traps. * All scripted tests re-run against a skip_list library built with UBSan: no failures. * `clang-format` and `black` are clean.
weaselbot added 1 commit 2026-11-10 20:44:15 +00:00
Guard memcpy/memcmp calls in SkipList.cpp against null pointers
CI / test (arm64, -DCMAKE_BUILD_TYPE=Debug -DMSAN_TOOLCHAIN_PATH=/opt/msan, 22, https://minio.weaselab.dev/public/aarch64/msan-toolchain-22.1.8.tar.zst, debug-arm64, ubuntu-latest-arm64) (pull_request) Successful in 5m27s
CI / release (arm64, , ubuntu-latest-arm64) (pull_request) Successful in 3m31s
CI / pre-commit (pull_request) Successful in 2m13s
CI / test (amd64, -DCMAKE_BUILD_TYPE=Debug -DMSAN_TOOLCHAIN_PATH=/opt/msan, 21, https://minio.weaselab.dev/public/x86_64/msan-toolchain-21.1.8.tar.zst, debug, ubuntu-latest-amd64) (pull_request) Successful in 4m1s
CI / test (amd64, -DCMAKE_CXX_FLAGS=-DUSE_64_BIT=1, 21, , 64-bit-versions, ubuntu-latest-amd64) (pull_request) Successful in 3m32s
CI / test (amd64, -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++, 21, , gcc, ubuntu-latest-amd64) (pull_request) Successful in 3m29s
CI / test (amd64, -DUSE_SIMD_FALLBACK=ON, 21, , simd-fallback, ubuntu-latest-amd64) (pull_request) Successful in 3m30s
CI / release (amd64, -DMSAN_TOOLCHAIN_PATH=/opt/msan, ubuntu-latest-amd64) (pull_request) Successful in 5m53s
CI / coverage (pull_request) Successful in 4m4s
0ca1d3c546
keyAfter() copied the caller's key with an unguarded memcpy, so a zero-length
key spelled with a null pointer (which the header allows -- it only constrains
Key::len) became memcpy(dst, nullptr, 0). That is undefined behavior even
though the count is 0, and keyAfter() runs for every point read and point
write, so any empty-key point operation tripped UBSan builds.

Commit 2231c09 fixed this pattern in operator<(const KeyInfo&),
SkipList::less and copyToArena, but missed keyAfter(). Apply the same guard
here, and guard the remaining unguarded memcmp calls in the same file
(compare(), Finger::found() and the point-read fast path in
CheckMax::advance()) via a small equalBytes() helper.

Add test_empty_key_null_pointer, which bisimulates both implementations on an
empty key spelled with a null pointer. It fails with a UBSan trap on
SkipList.cpp:34 before this change and passes after.
andrew merged commit aeafce1bc8 into main 2026-11-19 20:04:26 +00:00
andrew deleted branch weaselbot/issue-96 2026-11-19 20:04:34 +00:00
Sign in to join this conversation.
No Reviewers
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: weaselab/conflict-set#105