The skip_list implementation invokes memcmp (and memcpy) with nullptr arguments on valid input. This is undefined behavior per the C/C++ standard (the pointers must be valid even when the count is 0), and is flagged by UBSan / -fsanitize=undefined. It is triggered by the most basic operation — a single point write on a freshly created ConflictSet — so it fires on essentially every use of the skip_list implementation.
Root cause
ConflictSet::Impl::addWrites in SkipList.cpp constructs the points vector with a sizing constructor and then appends to it with emplace_back:
std::vector<KeyInfo>(count * 2) value-initializes count * 2 default KeyInfo objects. KeyInfo's key member is a default-constructed std::span (StringRef), whose data() is nullptr and size() is 0. The subsequent emplace_back calls append the real points instead of overwriting those slots, so the vector contains count * 2 junk entries (null/empty keys) followed by the count * 2 real entries.
std::is_sorted (and sortPoints) then compare every element, including the junk ones, via operator<(const KeyInfo&, const KeyInfo&):
When a junk entry is compared, lhs.key.data() and/or rhs.key.data() is nullptr, so memcmp is called with a null pointer. The sizing constructor was almost certainly intended to be points.reserve(count * 2).
Reproduction
Build with UBSan (aarch64, GCC 16.1.1 here; the bug is not arch-specific):
Then, via the C API (e.g. through ctypes against build-skip_list/libconflict-set.so):
ConflictSet*cs=ConflictSet_create(0);ConflictSet_WriteRangew={{"key",3},{NULL,0}};// a single point write
ConflictSet_addWrites(cs,&w,1,1);// valid: writeVersion 1 >= 0
ConflictSet_destroy(cs);
Observed (UBSan):
SkipList.cpp:100:17: runtime error: null pointer passed as argument 1, which is declared to never be null
SkipList.cpp:100:17: runtime error: null pointer passed as argument 2, which is declared to never be null
A second, related manifestation occurs in setOldestVersion. The first valid setOldestVersion call resolves an empty removal key (finger.getValue() returns an empty StringRef with data()==nullptr), and both SkipList::less (SkipList.cpp:290, memcmp) and copyToArena (SkipList.cpp:42, memcpy) are called with that null pointer:
SkipList.cpp:290:19: runtime error: null pointer passed as argument 2, which is declared to never be null
SkipList.cpp:42:9: runtime error: null pointer passed as argument 2, which is declared to never be null
The existing test_conflict_set.py::test_conflict_set (which uses DebugConflictSet, i.e. both implementations) triggers all four of the above UBSan reports when run against a UBSan build.
Expected vs actual
Expected: addWrites/setOldestVersion with valid arguments produce no undefined behavior.
Actual: they pass nullptr to memcmp/memcpy, which is undefined behavior.
Impact
The skip_list is a shipped, selectable implementation (skip_list/libconflict-set.so, used by conflict_set.py and the DebugConflictSet test harness). The UB is reachable with valid input on essentially every addWrites and the first setOldestVersion. While glibc's memcmp/memcpy happen not to dereference the pointers when the count is 0, the behavior is undefined per the standard and may be exploited by optimizers; it also blocks running the skip_list under UBSan/type-sanitizer (issue #37). Additionally, the sizing-constructor bug doubles the vector size with junk entries, wasting memory and sort work.
Suggested fix
In SkipList.cpp:757, replace the sizing constructor with reserve:
and guard the memcmp/memcpy calls in operator< (line 100), less (line 290), and copyToArena (line 42) against null/empty spans (or ensure empty spans never reach them).
## Summary
The `skip_list` implementation invokes `memcmp` (and `memcpy`) with `nullptr` arguments on valid input. This is undefined behavior per the C/C++ standard (the pointers must be valid even when the count is `0`), and is flagged by UBSan / `-fsanitize=undefined`. It is triggered by the most basic operation — a single point write on a freshly created `ConflictSet` — so it fires on essentially every use of the skip_list implementation.
## Root cause
`ConflictSet::Impl::addWrites` in `SkipList.cpp` constructs the `points` vector with a *sizing* constructor and then appends to it with `emplace_back`:
```cpp
// SkipList.cpp:757
auto points = std::vector<KeyInfo>(count * 2); // count*2 value-init'd KeyInfo
Arena arena;
for (int r = 0; r < count; r++) {
points.emplace_back(StringRef(writes[r].begin.p, writes[r].begin.len), true, true);
points.emplace_back(... , false, true);
}
if (!std::is_sorted(points.begin(), points.end())) { // SkipList.cpp:771
sortPoints(points);
}
```
`std::vector<KeyInfo>(count * 2)` value-initializes `count * 2` default `KeyInfo` objects. `KeyInfo`'s `key` member is a default-constructed `std::span` (`StringRef`), whose `data()` is `nullptr` and `size()` is `0`. The subsequent `emplace_back` calls *append* the real points instead of overwriting those slots, so the vector contains `count * 2` junk entries (null/empty keys) followed by the `count * 2` real entries.
`std::is_sorted` (and `sortPoints`) then compare every element, including the junk ones, via `operator<(const KeyInfo&, const KeyInfo&)`:
```cpp
// SkipList.cpp:99-100
bool operator<(const KeyInfo &lhs, const KeyInfo &rhs) {
int i = std::min(lhs.key.size(), rhs.key.size());
int c = memcmp(lhs.key.data(), rhs.key.data(), i); // <-- null pointer(s)
```
When a junk entry is compared, `lhs.key.data()` and/or `rhs.key.data()` is `nullptr`, so `memcmp` is called with a null pointer. The sizing constructor was almost certainly intended to be `points.reserve(count * 2)`.
## Reproduction
Build with UBSan (aarch64, GCC 16.1.1 here; the bug is not arch-specific):
```
cmake -B build-san -DCMAKE_BUILD_TYPE=Debug \
-DCMAKE_CXX_FLAGS=-fsanitize=undefined,address -fno-omit-frame-pointer \
-DCMAKE_C_FLAGS=-fsanitize=undefined,address -fno-omit-frame-pointer \
-DCMAKE_EXE_LINKER_FLAGS=-fsanitize=undefined,address \
-DCMAKE_SHARED_LINKER_FLAGS=-fsanitize=undefined,address
cmake --build build-san -- skip_list
```
Then, via the C API (e.g. through ctypes against `build-skip_list/libconflict-set.so`):
```c
ConflictSet *cs = ConflictSet_create(0);
ConflictSet_WriteRange w = { { "key", 3 }, { NULL, 0 } }; // a single point write
ConflictSet_addWrites(cs, &w, 1, 1); // valid: writeVersion 1 >= 0
ConflictSet_destroy(cs);
```
Observed (UBSan):
```
SkipList.cpp:100:17: runtime error: null pointer passed as argument 1, which is declared to never be null
SkipList.cpp:100:17: runtime error: null pointer passed as argument 2, which is declared to never be null
```
A second, related manifestation occurs in `setOldestVersion`. The first valid `setOldestVersion` call resolves an empty removal key (`finger.getValue()` returns an empty `StringRef` with `data()==nullptr`), and both `SkipList::less` (`SkipList.cpp:290`, `memcmp`) and `copyToArena` (`SkipList.cpp:42`, `memcpy`) are called with that null pointer:
```c
ConflictSet *cs = ConflictSet_create(0);
ConflictSet_setOldestVersion(cs, 0); // valid: 0 >= prev oldest (0), 0 <= latest addWrites (0)
ConflictSet_destroy(cs);
```
```
SkipList.cpp:290:19: runtime error: null pointer passed as argument 2, which is declared to never be null
SkipList.cpp:42:9: runtime error: null pointer passed as argument 2, which is declared to never be null
```
The existing `test_conflict_set.py::test_conflict_set` (which uses `DebugConflictSet`, i.e. both implementations) triggers all four of the above UBSan reports when run against a UBSan build.
## Expected vs actual
- Expected: `addWrites`/`setOldestVersion` with valid arguments produce no undefined behavior.
- Actual: they pass `nullptr` to `memcmp`/`memcpy`, which is undefined behavior.
## Impact
The skip_list is a shipped, selectable implementation (`skip_list/libconflict-set.so`, used by `conflict_set.py` and the `DebugConflictSet` test harness). The UB is reachable with valid input on essentially every `addWrites` and the first `setOldestVersion`. While glibc's `memcmp`/`memcpy` happen not to dereference the pointers when the count is `0`, the behavior is undefined per the standard and may be exploited by optimizers; it also blocks running the skip_list under UBSan/type-sanitizer (issue #37). Additionally, the sizing-constructor bug doubles the vector size with junk entries, wasting memory and sort work.
## Suggested fix
In `SkipList.cpp:757`, replace the sizing constructor with `reserve`:
```cpp
auto points = std::vector<KeyInfo>();
points.reserve(count * 2);
```
and guard the `memcmp`/`memcpy` calls in `operator<` (line 100), `less` (line 290), and `copyToArena` (line 42) against null/empty spans (or ensure empty spans never reach them).
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
The
skip_listimplementation invokesmemcmp(andmemcpy) withnullptrarguments on valid input. This is undefined behavior per the C/C++ standard (the pointers must be valid even when the count is0), and is flagged by UBSan /-fsanitize=undefined. It is triggered by the most basic operation — a single point write on a freshly createdConflictSet— so it fires on essentially every use of the skip_list implementation.Root cause
ConflictSet::Impl::addWritesinSkipList.cppconstructs thepointsvector with a sizing constructor and then appends to it withemplace_back:std::vector<KeyInfo>(count * 2)value-initializescount * 2defaultKeyInfoobjects.KeyInfo'skeymember is a default-constructedstd::span(StringRef), whosedata()isnullptrandsize()is0. The subsequentemplace_backcalls append the real points instead of overwriting those slots, so the vector containscount * 2junk entries (null/empty keys) followed by thecount * 2real entries.std::is_sorted(andsortPoints) then compare every element, including the junk ones, viaoperator<(const KeyInfo&, const KeyInfo&):When a junk entry is compared,
lhs.key.data()and/orrhs.key.data()isnullptr, somemcmpis called with a null pointer. The sizing constructor was almost certainly intended to bepoints.reserve(count * 2).Reproduction
Build with UBSan (aarch64, GCC 16.1.1 here; the bug is not arch-specific):
Then, via the C API (e.g. through ctypes against
build-skip_list/libconflict-set.so):Observed (UBSan):
A second, related manifestation occurs in
setOldestVersion. The first validsetOldestVersioncall resolves an empty removal key (finger.getValue()returns an emptyStringRefwithdata()==nullptr), and bothSkipList::less(SkipList.cpp:290,memcmp) andcopyToArena(SkipList.cpp:42,memcpy) are called with that null pointer:The existing
test_conflict_set.py::test_conflict_set(which usesDebugConflictSet, i.e. both implementations) triggers all four of the above UBSan reports when run against a UBSan build.Expected vs actual
addWrites/setOldestVersionwith valid arguments produce no undefined behavior.nullptrtomemcmp/memcpy, which is undefined behavior.Impact
The skip_list is a shipped, selectable implementation (
skip_list/libconflict-set.so, used byconflict_set.pyand theDebugConflictSettest harness). The UB is reachable with valid input on essentially everyaddWritesand the firstsetOldestVersion. While glibc'smemcmp/memcpyhappen not to dereference the pointers when the count is0, the behavior is undefined per the standard and may be exploited by optimizers; it also blocks running the skip_list under UBSan/type-sanitizer (issue #37). Additionally, the sizing-constructor bug doubles the vector size with junk entries, wasting memory and sort work.Suggested fix
In
SkipList.cpp:757, replace the sizing constructor withreserve:and guard the
memcmp/memcpycalls inoperator<(line 100),less(line 290), andcopyToArena(line 42) against null/empty spans (or ensure empty spans never reach them).The skip_list is not shipped. It's test only. Let's fix it anyway though