skip_list: keyAfter() passes a null pointer to memcpy for empty keys (UB); the #64 guard missed it #96

Closed
opened 2026-11-07 14:22:54 +00:00 by weaselbot · 0 comments
Member

Summary

keyAfter() in SkipList.cpp copies the caller's key with an unguarded memcpy:

// SkipList.cpp:31
std::span<const uint8_t> keyAfter(Arena &arena, std::span<const uint8_t> key) {
  auto result =
      std::span<uint8_t>(new (arena) uint8_t[key.size() + 1], key.size() + 1);
  memcpy(result.data(), key.data(), key.size());   // line 34
  ...

For a zero-length key whose pointer is null this is memcpy(dst, nullptr, 0), which is
undefined behavior (the pointers must be valid even when the count is 0) and a hard error in
a UBSan build. keyAfter is on the hot path for every point read (Impl::check) and every
point write (Impl::addWrites), so any empty-key point operation with a null p trips it.

Commit 2231c09 (closing #64) fixed exactly this pattern in operator<(const KeyInfo&),
SkipList::less and copyToArena -- the commit message says "guard the memcmp/memcpy calls
... against empty spans (where data() may be nullptr)". keyAfter in the same file was
missed.

Reproduction

repro.cpp:

#include "ConflictSet.h"
#include <cstdio>
using namespace weaselab;
int main() {
  ConflictSet cs(0);
  // point read of the empty key, then a point write of the empty key
  ConflictSet::ReadRange r{{nullptr, 0}, {nullptr, 0}, 0};
  ConflictSet::Result result;
  cs.check(&r, &result, 1);
  printf("check -> %d\n", (int)result);
  ConflictSet::WriteRange w{{nullptr, 0}, {nullptr, 0}};
  cs.addWrites(&w, 1, 1);
  printf("write ok\n");
}
$ g++ -std=c++20 -O1 -g -fsanitize=undefined -fno-sanitize-recover=all \
      -Iinclude -I. -Ithird_party/valgrind -o repro repro.cpp SkipList.cpp
$ ./repro ; echo "exit=$?"
SkipList.cpp:34:9: runtime error: null pointer passed as argument 2, which is declared to never be null
exit=1                      # aborted before producing any result

The identical program linked against the shipped implementation is clean:

$ g++ -std=c++20 -O1 -g -fsanitize=undefined -fno-sanitize-recover=all \
      -Iinclude -I. -Ithird_party/valgrind -o repro_rt repro.cpp ConflictSet.cpp
$ ./repro_rt ; echo "exit=$?"
check -> 0
write ok
exit=0

So the two implementations of the same API disagree on the same input, which is exactly what
the test harness (DebugConflictSet in test_conflict_set.py) bisimulates.

Why this is valid input

  • The header never requires p != nullptr; len == 0 is a documented, meaningful length
    ("end having length 0 denotes that this range is the single key {begin}"), and the empty
    key is a first-class key: the radix tree starts out holding it, and
    test_conflict_set.py::test_update_zero_should_commit writes b"".
  • {nullptr, 0} is this repo's own idiom for a zero-length key: ShowMemoryTest.cpp:19 and
    :26 pass {nullptr, 0} for their zero-length end key.
  • SkipList.cpp itself produces {nullptr, 0} spans for the empty key -- copyToArena
    (line 39) returns std::span<const uint8_t>() -- and feeds them back into
    SkipList::find / SkipList::less. The representation is canonical internally.
  • The other implementation (ConflictSet.cpp) handles {nullptr, 0} with no UB, verified
    above.

Impact

  • A UBSan build of the skip_list implementation aborts on a valid empty-key point read or
    point write. CMakeLists.txt compiles fuzz_driver with -fsanitize=address,undefined,
    and build_msan_toolchain.sh / the CI matrix build sanitizer configurations; anyone
    pointing a sanitizer build at SkipList.cpp (e.g. by enabling the opt-in
    driver_skip_list corpus tests) gets an immediate trap instead of a test result.
  • Latent trap for any binding or embedding that spells the empty key as NULL/0.

Suggested fix

Guard the copy the same way copyToArena is guarded:

if (key.size() > 0) {
  memcpy(result.data(), key.data(), key.size());
}

Related latent instances of the same unguarded pattern in the same file (not reachable
through the public API today, but they should get the same guard so the fix is complete):
compare() at line 183 (memcmp(a.data(), b.data(), std::min(a.size(), b.size())), only
called from the unused ReadConflictRange::operator<) and Finger::found() at line 374
(memcmp(n->value(), value.data(), value.size()), only ever given non-empty write-range
ends).

## Summary `keyAfter()` in `SkipList.cpp` copies the caller's key with an unguarded `memcpy`: ```c++ // SkipList.cpp:31 std::span<const uint8_t> keyAfter(Arena &arena, std::span<const uint8_t> key) { auto result = std::span<uint8_t>(new (arena) uint8_t[key.size() + 1], key.size() + 1); memcpy(result.data(), key.data(), key.size()); // line 34 ... ``` For a zero-length key whose pointer is null this is `memcpy(dst, nullptr, 0)`, which is undefined behavior (the pointers must be valid even when the count is 0) and a hard error in a UBSan build. `keyAfter` is on the hot path for every point read (`Impl::check`) and every point write (`Impl::addWrites`), so any empty-key point operation with a null `p` trips it. Commit 2231c09 (closing #64) fixed exactly this pattern in `operator<(const KeyInfo&)`, `SkipList::less` and `copyToArena` -- the commit message says "guard the memcmp/memcpy calls ... against empty spans (where data() may be nullptr)". `keyAfter` in the same file was missed. ## Reproduction `repro.cpp`: ```c++ #include "ConflictSet.h" #include <cstdio> using namespace weaselab; int main() { ConflictSet cs(0); // point read of the empty key, then a point write of the empty key ConflictSet::ReadRange r{{nullptr, 0}, {nullptr, 0}, 0}; ConflictSet::Result result; cs.check(&r, &result, 1); printf("check -> %d\n", (int)result); ConflictSet::WriteRange w{{nullptr, 0}, {nullptr, 0}}; cs.addWrites(&w, 1, 1); printf("write ok\n"); } ``` ``` $ g++ -std=c++20 -O1 -g -fsanitize=undefined -fno-sanitize-recover=all \ -Iinclude -I. -Ithird_party/valgrind -o repro repro.cpp SkipList.cpp $ ./repro ; echo "exit=$?" SkipList.cpp:34:9: runtime error: null pointer passed as argument 2, which is declared to never be null exit=1 # aborted before producing any result ``` The identical program linked against the shipped implementation is clean: ``` $ g++ -std=c++20 -O1 -g -fsanitize=undefined -fno-sanitize-recover=all \ -Iinclude -I. -Ithird_party/valgrind -o repro_rt repro.cpp ConflictSet.cpp $ ./repro_rt ; echo "exit=$?" check -> 0 write ok exit=0 ``` So the two implementations of the same API disagree on the same input, which is exactly what the test harness (`DebugConflictSet` in `test_conflict_set.py`) bisimulates. ## Why this is valid input * The header never requires `p != nullptr`; `len == 0` is a documented, meaningful length ("`end` having length 0 denotes that this range is the single key {begin}"), and the empty key is a first-class key: the radix tree starts out holding it, and `test_conflict_set.py::test_update_zero_should_commit` writes `b""`. * `{nullptr, 0}` is this repo's own idiom for a zero-length key: `ShowMemoryTest.cpp:19` and `:26` pass `{nullptr, 0}` for their zero-length `end` key. * `SkipList.cpp` itself produces `{nullptr, 0}` spans for the empty key -- `copyToArena` (line 39) returns `std::span<const uint8_t>()` -- and feeds them back into `SkipList::find` / `SkipList::less`. The representation is canonical internally. * The other implementation (`ConflictSet.cpp`) handles `{nullptr, 0}` with no UB, verified above. ## Impact * A UBSan build of the skip_list implementation aborts on a valid empty-key point read or point write. `CMakeLists.txt` compiles `fuzz_driver` with `-fsanitize=address,undefined`, and `build_msan_toolchain.sh` / the CI matrix build sanitizer configurations; anyone pointing a sanitizer build at `SkipList.cpp` (e.g. by enabling the opt-in `driver_skip_list` corpus tests) gets an immediate trap instead of a test result. * Latent trap for any binding or embedding that spells the empty key as `NULL`/0. ## Suggested fix Guard the copy the same way `copyToArena` is guarded: ```c++ if (key.size() > 0) { memcpy(result.data(), key.data(), key.size()); } ``` Related latent instances of the same unguarded pattern in the same file (not reachable through the public API today, but they should get the same guard so the fix is complete): `compare()` at line 183 (`memcmp(a.data(), b.data(), std::min(a.size(), b.size()))`, only called from the unused `ReadConflictRange::operator<`) and `Finger::found()` at line 374 (`memcmp(n->value(), value.data(), value.size())`, only ever given non-empty write-range ends).
weaselbot was assigned by andrew 2026-11-10 19:10:46 +00:00
Sign in to join this conversation.
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: weaselab/conflict-set#96