The skip list implementation passed nullptr to memcmp/memcpy on valid input, which is undefined behavior even when the count is 0, and is flagged by UBSan. Two root causes:
addWrites sizing-constructor bug:std::vector<KeyInfo>(count * 2) value-initialized count*2 default KeyInfos (whose key span has data() == nullptr, size() == 0), then emplace_backappended the real points after them. std::is_sorted/sortPoints then compared the junk entries via operator<, calling memcmp with null pointers. The sizing constructor was meant to be reserve.
Empty spans reaching memcmp/memcpy:setOldestVersion resolves an empty removal key (data() == nullptr, size() == 0), passing it to SkipList::less (memcmp) and copyToArena (memcpy).
Changes
addWrites: replace the sizing constructor with reserve(count * 2) so no junk entries are created (also avoids the wasted memory/sort work).
copyToArena: return early for an empty key instead of memcpy-ing with a null pointer.
SkipList::less: skip memcmp when there are no bytes to compare (n > 0 ? memcmp(...) : 0).
operator<: guard the memcmp with i > 0 ? ... : 0. When one key is empty and the other is not, c defaults to 0 and the existing downstream length comparison (lhs.key.size() < rhs.key.size()) places the empty key first, so ordering is unchanged.
Verification
Built with -fsanitize=undefined (and address) on aarch64/GCC 16.1.1:
The issue's two repros (a point write on "key"; setOldestVersion on a fresh conflict set) produce no UBSan reports.
The full test_conflict_set.py suite (bisimulating the skip list against the radix tree via DebugConflictSet) is clean under UBSan.
The same repros and suite against an unpatched build trigger the UBSan reports from the issue, confirming the fix targets the reported behavior.
Closes #64.
The skip list implementation passed `nullptr` to `memcmp`/`memcpy` on valid input, which is undefined behavior even when the count is `0`, and is flagged by UBSan. Two root causes:
1. **`addWrites` sizing-constructor bug:** `std::vector<KeyInfo>(count * 2)` value-initialized `count*2` default `KeyInfo`s (whose `key` span has `data() == nullptr`, `size() == 0`), then `emplace_back` *appended* the real points after them. `std::is_sorted`/`sortPoints` then compared the junk entries via `operator<`, calling `memcmp` with null pointers. The sizing constructor was meant to be `reserve`.
2. **Empty spans reaching `memcmp`/`memcpy`:** `setOldestVersion` resolves an empty removal key (`data() == nullptr`, `size() == 0`), passing it to `SkipList::less` (`memcmp`) and `copyToArena` (`memcpy`).
### Changes
- `addWrites`: replace the sizing constructor with `reserve(count * 2)` so no junk entries are created (also avoids the wasted memory/sort work).
- `copyToArena`: return early for an empty key instead of `memcpy`-ing with a null pointer.
- `SkipList::less`: skip `memcmp` when there are no bytes to compare (`n > 0 ? memcmp(...) : 0`).
- `operator<`: guard the `memcmp` with `i > 0 ? ... : 0`. When one key is empty and the other is not, `c` defaults to `0` and the existing downstream length comparison (`lhs.key.size() < rhs.key.size()`) places the empty key first, so ordering is unchanged.
### Verification
Built with `-fsanitize=undefined` (and address) on aarch64/GCC 16.1.1:
- The issue's two repros (a point write on `"key"`; `setOldestVersion` on a fresh conflict set) produce no UBSan reports.
- The full `test_conflict_set.py` suite (bisimulating the skip list against the radix tree via `DebugConflictSet`) is clean under UBSan.
- The same repros and suite against an unpatched build trigger the UBSan reports from the issue, confirming the fix targets the reported behavior.
In addWrites, the sizing constructor std::vector<KeyInfo>(count * 2)
was used instead of reserve(count * 2), leaving count*2 default-
constructed (null/empty key) entries that were then compared via
operator<, passing nullptr to memcmp. Switch to reserve so only real
entries exist.
Additionally guard the memcmp/memcpy calls in operator<, SkipList::less,
and copyToArena against empty spans (where data() may be nullptr), which
is reachable on the first setOldestVersion with an empty removal key.
Closes#64
andrew
requested changes 2026-07-13 19:51:47 +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.
andrew
Closes #64.
The skip list implementation passed
nullptrtomemcmp/memcpyon valid input, which is undefined behavior even when the count is0, and is flagged by UBSan. Two root causes:addWritessizing-constructor bug:std::vector<KeyInfo>(count * 2)value-initializedcount*2defaultKeyInfos (whosekeyspan hasdata() == nullptr,size() == 0), thenemplace_backappended the real points after them.std::is_sorted/sortPointsthen compared the junk entries viaoperator<, callingmemcmpwith null pointers. The sizing constructor was meant to bereserve.Empty spans reaching
memcmp/memcpy:setOldestVersionresolves an empty removal key (data() == nullptr,size() == 0), passing it toSkipList::less(memcmp) andcopyToArena(memcpy).Changes
addWrites: replace the sizing constructor withreserve(count * 2)so no junk entries are created (also avoids the wasted memory/sort work).copyToArena: return early for an empty key instead ofmemcpy-ing with a null pointer.SkipList::less: skipmemcmpwhen there are no bytes to compare (n > 0 ? memcmp(...) : 0).operator<: guard thememcmpwithi > 0 ? ... : 0. When one key is empty and the other is not,cdefaults to0and the existing downstream length comparison (lhs.key.size() < rhs.key.size()) places the empty key first, so ordering is unchanged.Verification
Built with
-fsanitize=undefined(and address) on aarch64/GCC 16.1.1:"key";setOldestVersionon a fresh conflict set) produce no UBSan reports.test_conflict_set.pysuite (bisimulating the skip list against the radix tree viaDebugConflictSet) is clean under UBSan.@@ -98,3 +101,3 @@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);int c = i > 0 ? memcmp(lhs.key.data(), rhs.key.data(), i) : 0;If one of them is non-empty, this could compare them incorrectly
I missed that there was a downstream length comparison. First commit was fine. Please remove the last commit
494e836aaeto2231c093df