keyAfter() in SkipList.cpp copies the caller's key with an unguarded memcpy:
// SkipList.cpp:31
std::span<constuint8_t>keyAfter(Arena&arena,std::span<constuint8_t>key){autoresult=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>usingnamespaceweaselab;intmain(){ConflictSetcs(0);// point read of the empty key, then a point write of the empty key
ConflictSet::ReadRanger{{nullptr,0},{nullptr,0},0};ConflictSet::Resultresult;cs.check(&r,&result,1);printf("check -> %d\n",(int)result);ConflictSet::WriteRangew{{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:
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:
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 andrew2026-11-10 19:10:46 +00:00
Blocking a user prevents them from interacting with repositories, such as opening or commenting on pull requests or issues. Learn more about blocking a user.
Summary
keyAfter()inSkipList.cppcopies the caller's key with an unguardedmemcpy:For a zero-length key whose pointer is null this is
memcpy(dst, nullptr, 0), which isundefined behavior (the pointers must be valid even when the count is 0) and a hard error in
a UBSan build.
keyAfteris on the hot path for every point read (Impl::check) and everypoint write (
Impl::addWrites), so any empty-key point operation with a nullptrips it.Commit
2231c09(closing #64) fixed exactly this pattern inoperator<(const KeyInfo&),SkipList::lessandcopyToArena-- the commit message says "guard the memcmp/memcpy calls... against empty spans (where data() may be nullptr)".
keyAfterin the same file wasmissed.
Reproduction
repro.cpp:The identical program linked against the shipped implementation is clean:
So the two implementations of the same API disagree on the same input, which is exactly what
the test harness (
DebugConflictSetintest_conflict_set.py) bisimulates.Why this is valid input
p != nullptr;len == 0is a documented, meaningful length("
endhaving length 0 denotes that this range is the single key {begin}"), and the emptykey is a first-class key: the radix tree starts out holding it, and
test_conflict_set.py::test_update_zero_should_commitwritesb"".{nullptr, 0}is this repo's own idiom for a zero-length key:ShowMemoryTest.cpp:19and:26pass{nullptr, 0}for their zero-lengthendkey.SkipList.cppitself produces{nullptr, 0}spans for the empty key --copyToArena(line 39) returns
std::span<const uint8_t>()-- and feeds them back intoSkipList::find/SkipList::less. The representation is canonical internally.ConflictSet.cpp) handles{nullptr, 0}with no UB, verifiedabove.
Impact
point write.
CMakeLists.txtcompilesfuzz_driverwith-fsanitize=address,undefined,and
build_msan_toolchain.sh/ the CI matrix build sanitizer configurations; anyonepointing a sanitizer build at
SkipList.cpp(e.g. by enabling the opt-indriver_skip_listcorpus tests) gets an immediate trap instead of a test result.NULL/0.Suggested fix
Guard the copy the same way
copyToArenais guarded: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())), onlycalled from the unused
ReadConflictRange::operator<) andFinger::found()at line 374(
memcmp(n->value(), value.data(), value.size()), only ever given non-empty write-rangeends).