Two bugs made the SHOW_MEMORY instrumentation in Internal.h unusable: every build aborted (asserts on) or corrupted memory (asserts off) on ordinary valid API calls.
Defect 1: assert(!releaseDeferred) in Node::getCapacity()
NodeAllocator<T>::releaseDeferred() only ever calls release() on nodes that still have releaseDeferred == true, and release() calls removeNode(), which reads n->getCapacity() under SHOW_MEMORY. partialKeyCapacity is not repurposed by deferRelease (only the entry/forwardTo union member and parent are), so the assertion had no basis. It's dropped, with a comment explaining why deferred nodes are fine.
Defect 2: eraseTree reads freed parent pointers via removeKey
eraseTree pushes a node's children onto the worklist and then immediately releases the node, so by the time a child is visited its parent pointer is dangling and removeKey -> getSearchPathLength walks freed memory (and deferRelease repurposes parent as the deferred-list link anyway). The worklist now carries each node's search path length, computed while its parent is still alive, and the accounting goes through a new removeKey(Node *, int64_t searchPathLength) overload. Key bytes are now exact rather than garbage, so keyBytes returns to 0 when the tree is erased.
Test
New conflict_set_show_memory_test target compiles ConflictSet.cpp with -DSHOW_MEMORY=1 (and, like fuzz_driver, ASan+UBSan) and runs a ShowMemoryTest.cpp covering the issue's repros: a node split with a pending deferred release, a mid-workload eraseTree from exceeding the version window, and destruction of a large tree. It asserts the accounting is fully unwound (nodeBytes, partialCapacityBytes, totalKeys, keyBytes and mallocBytes all 0) after each ConflictSet is destroyed, and the instrumentation's own totalBytes == mallocBytes checks abort on any inconsistency. SHOW_MEMORY is now overridable from the command line (#ifndef guard) so the target can enable it; the pre-commit guard against checking in #define SHOW_MEMORY 1 still applies.
Verification
Both repros from the issue (g++ -O1 -g -std=c++20 min1.cpp ConflictSet.cpp -DSHOW_MEMORY=1, with and without NDEBUG, plus valgrind -q and ASan): clean, exit 0, all accounting back to 0 at exit.
Reintroducing either defect locally makes the new test fail (the getCapacity() assertion aborts; ASan reports heap-use-after-free ... in getSearchPathLength, removeKey, eraseTree), so it's a real regression test.
Full ctest suite (Debug, asserts enabled): 8599/8599 passed, including the new test, all corpus fuzz/blackbox/valgrind tests and script tests. Release and clang builds also build and pass.
Sample report from the test's 1000-key case: Peak node bytes: 53008, Expected worst case node bytes: 112224, and no totalBytes != mallocBytes abort.
Follow-up (review): eraseTree's search path length bookkeeping is SHOW_MEMORY-only
eraseTree only needs the search path lengths it carries on the worklist so that the SHOW_MEMORY key accounting avoids walking parent pointers of nodes that were already released. Those lengths now live on a parallel stack that only exists when SHOW_MEMORY is enabled; other builds keep upstream's worklist of bare Node * and compute nothing extra (eraseTree is byte-for-byte the same size, and the whole -O2 object has the same .text size as upstream).
Two bugs made the `SHOW_MEMORY` instrumentation in `Internal.h` unusable: every build aborted (asserts on) or corrupted memory (asserts off) on ordinary valid API calls.
**Defect 1: `assert(!releaseDeferred)` in `Node::getCapacity()`**
`NodeAllocator<T>::releaseDeferred()` only ever calls `release()` on nodes that still have `releaseDeferred == true`, and `release()` calls `removeNode()`, which reads `n->getCapacity()` under `SHOW_MEMORY`. `partialKeyCapacity` is not repurposed by `deferRelease` (only the `entry`/`forwardTo` union member and `parent` are), so the assertion had no basis. It's dropped, with a comment explaining why deferred nodes are fine.
**Defect 2: `eraseTree` reads freed `parent` pointers via `removeKey`**
`eraseTree` pushes a node's children onto the worklist and then immediately releases the node, so by the time a child is visited its `parent` pointer is dangling and `removeKey` -> `getSearchPathLength` walks freed memory (and `deferRelease` repurposes `parent` as the deferred-list link anyway). The worklist now carries each node's search path length, computed while its parent is still alive, and the accounting goes through a new `removeKey(Node *, int64_t searchPathLength)` overload. Key bytes are now exact rather than garbage, so `keyBytes` returns to 0 when the tree is erased.
**Test**
New `conflict_set_show_memory_test` target compiles `ConflictSet.cpp` with `-DSHOW_MEMORY=1` (and, like `fuzz_driver`, ASan+UBSan) and runs a `ShowMemoryTest.cpp` covering the issue's repros: a node split with a pending deferred release, a mid-workload `eraseTree` from exceeding the version window, and destruction of a large tree. It asserts the accounting is fully unwound (`nodeBytes`, `partialCapacityBytes`, `totalKeys`, `keyBytes` and `mallocBytes` all 0) after each `ConflictSet` is destroyed, and the instrumentation's own `totalBytes == mallocBytes` checks abort on any inconsistency. `SHOW_MEMORY` is now overridable from the command line (`#ifndef` guard) so the target can enable it; the pre-commit guard against checking in `#define SHOW_MEMORY 1` still applies.
**Verification**
- Both repros from the issue (`g++ -O1 -g -std=c++20 min1.cpp ConflictSet.cpp -DSHOW_MEMORY=1`, with and without `NDEBUG`, plus `valgrind -q` and ASan): clean, exit 0, all accounting back to 0 at exit.
- Reintroducing either defect locally makes the new test fail (the `getCapacity()` assertion aborts; ASan reports `heap-use-after-free ... in getSearchPathLength, removeKey, eraseTree`), so it's a real regression test.
- Full `ctest` suite (Debug, asserts enabled): 8599/8599 passed, including the new test, all corpus fuzz/blackbox/valgrind tests and script tests. Release and clang builds also build and pass.
- Sample report from the test's 1000-key case: `Peak node bytes: 53008`, `Expected worst case node bytes: 112224`, and no `totalBytes != mallocBytes` abort.
Closes #88
**Follow-up (review): eraseTree's search path length bookkeeping is SHOW_MEMORY-only**
`eraseTree` only needs the search path lengths it carries on the worklist so that the `SHOW_MEMORY` key accounting avoids walking `parent` pointers of nodes that were already released. Those lengths now live on a parallel stack that only exists when `SHOW_MEMORY` is enabled; other builds keep upstream's worklist of bare `Node *` and compute nothing extra (`eraseTree` is byte-for-byte the same size, and the whole `-O2` object has the same `.text` size as upstream).
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 4m8s
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 3m56s
`Node::getCapacity()` asserted `!releaseDeferred`, but releasing a deferred
node requires its capacity, so any node replacement aborted an assertion-
enabled `SHOW_MEMORY` build. `partialKeyCapacity` is not repurposed by
`deferRelease`, so there is no reason to reject deferred nodes. Drop the
assertion.
`eraseTree` released a node before visiting its children, so the `parent`
pointers walked by `removeKey` pointed to freed memory (and `deferRelease`
repurposes `parent` as a list link). Carry the search path length of each node
in the worklist, computed while its parent is still alive, and account for it
with the new `removeKey` overload.
Add a test covering the SHOW_MEMORY instrumentation, which the rest of the
test suite doesn't compile with.
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 3m49s
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 3m54s
The coverage job compiles ConflictSet.cpp twice: once without SHOW_MEMORY,
like the rest of the build, and once with it for the SHOW_MEMORY test. Each
config previously saw a *different* definition of the accounting helpers:
no-op `constexpr` stubs near the top of the file when SHOW_MEMORY was off,
and the real definitions at the bottom when it was on.
gcovr reads the .gcda files for a source file and merges them, and its
default (strict) function merge mode asserts that a function name always
maps to one line. Since `addNode`, `removeNode`, `addKey`, both `removeKey`
overloads and `getSearchPathLength` were reported on two different lines,
report generation aborted with
AssertionError: Got function getSearchPathLength(Node*) on multiple
lines: 99, 6002.
Define those functions in exactly one place instead, and compile the
accounting out from within the bodies. Then every configuration reports each
function on the same line and the coverage data can be merged. The empty
calls are inlined away: the Release shared library contains no calls to
them.
With the merge fixed, the accounting lines that only exist in the SHOW_MEMORY
build show up in the report, so the coverage job's 100% line requirement
covers them. Extend the SHOW_MEMORY test to grow a node through every node
type (so `getNodeSize` covers every case) and to erase entries one at a time
via `setOldestVersion` (so `removeKey` and the `internal_setOldestVersion`
cross-check are covered). The remaining `abort()`s in the accounting are
defensive checks that can never be taken on a passing run; mark them
GCOVR_EXCL_LINE like the rest of the unreachable code in this file.
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 3m48s
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 3m54s
`getNodeSize`'s unreachable `default:` sits inside ConflictSet.cpp's
`GCOVR_EXCL_START`/`GCOVR_EXCL_STOP` block, so the `GCOVR_EXCL_LINE` markers on
those two lines are redundant: they cannot change the report, but they make
gcovr print
(WARNING) GCOVR_EXCL_LINE found on line 6002 in excluded region started on
line 5535
once per line for each of the four reports the coverage job writes. Drop them,
matching the rest of the excluded tail, which carries no exclusion markers.
Context: the previous coverage job for this branch did not fail in any of its
steps. Build, Test (5754/5754 passed), Coverage report (`gcovr
--fail-under-line 100` reported 100% for ConflictSet.cpp, LongestCommonPrefix.h
and Metrics.h), the upload and the test summary all reported success; the job
was marked failed while tearing the job container down. The post-actions
(actions/cache, actions/checkout) could no longer `docker exec` into the
container and the runner's rootless podman socket was gone ("Cannot connect to
the Docker daemon at unix:///run/user/992/podman/podman.sock", "Error while stop
job container"); the actions/cache service on 192.168.0.110:41379 had been
refusing connections for the whole run.
Verified locally on this commit: Debug, gcc and `--coverage` builds of the
coverage job's configuration; 5754/5754 tests pass; merged line coverage (union
over the library, SHOW_MEMORY and fuzz-driver objects, honouring the
GCOVR_EXCL_START/STOP regions) is 100% for all three measured files, and no
GCOVR_EXCL_LINE markers remain inside an excluded region.
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 5m8s
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 4m55s
`eraseTree` only carries the search path lengths of queued nodes around so
that the SHOW_MEMORY key accounting doesn't have to walk `parent` pointers of
nodes that have already been released. Put the lengths on a parallel stack
that only exists when SHOW_MEMORY is enabled, so that other builds keep the
upstream worklist of bare `Node *` and don't compute anything extra.
Addressed in 80f084c (ConflictSet.cpp line 2767 is gone): the search path lengths are now only tracked when SHOW_MEMORY is enabled.
eraseTree keeps the upstream worklist of bare Node *; the lengths live on a parallel stack that only exists under #if SHOW_MEMORY, and the per-child length is computed in a queueChild lambda whose SHOW_MEMORY branch is the only thing that reads child->partialKeyLen. In non-SHOW_MEMORY builds queueChild is just toFree.push_back(child), and removeKey(n, /*searchPathLength=*/0) is the same empty stub it is everywhere else, so nothing is computed or carried.
Verified that this is actually free in the normal build:
eraseTree in an -O2 non-SHOW_MEMORY object is the same code as upstream: whole-object .text is byte-identical in size (161331), and the disassembly of eraseTree differs from upstream only in jump offsets and a few removed nops (it comes out 20 bytes smaller).
-Wall -Wextra -Wunused is clean in both SHOW_MEMORY=0 and SHOW_MEMORY=1 builds.
Full ctest suite (Debug, asserts on): 8599/8599 passed, including conflict_set_show_memory_test.
The new lines are covered in at least one configuration, as the coverage merge needs: the SHOW_MEMORY object covers childSearchPathLength, the parallel stack pushes/pops and both Node256 bulk-append lines; the library object covers the #else branch and the shared queueChild/switch lines (including Node48, which the SHOW_MEMORY test itself never erases).
Both issue repros still run clean under valgrind (-DNDEBUG) and with assertions on, and the 20000-write workload still reports sensible numbers (Peak node bytes: 1056180, Expected worst case node bytes: 2240110, no totalBytes != mallocBytes abort).
Addressed in 80f084c (`ConflictSet.cpp` line 2767 is gone): the search path lengths are now only tracked when `SHOW_MEMORY` is enabled.
`eraseTree` keeps the upstream worklist of bare `Node *`; the lengths live on a parallel stack that only exists under `#if SHOW_MEMORY`, and the per-child length is computed in a `queueChild` lambda whose `SHOW_MEMORY` branch is the only thing that reads `child->partialKeyLen`. In non-`SHOW_MEMORY` builds `queueChild` is just `toFree.push_back(child)`, and `removeKey(n, /*searchPathLength=*/0)` is the same empty stub it is everywhere else, so nothing is computed or carried.
Verified that this is actually free in the normal build:
- `eraseTree` in an `-O2` non-`SHOW_MEMORY` object is the same code as upstream: whole-object `.text` is byte-identical in size (161331), and the disassembly of `eraseTree` differs from upstream only in jump offsets and a few removed `nop`s (it comes out 20 bytes smaller).
- `-Wall -Wextra -Wunused` is clean in both `SHOW_MEMORY=0` and `SHOW_MEMORY=1` builds.
- Full `ctest` suite (Debug, asserts on): 8599/8599 passed, including `conflict_set_show_memory_test`.
- The new lines are covered in at least one configuration, as the coverage merge needs: the `SHOW_MEMORY` object covers `childSearchPathLength`, the parallel stack pushes/pops and both `Node256` bulk-append lines; the library object covers the `#else` branch and the shared `queueChild`/`switch` lines (including `Node48`, which the `SHOW_MEMORY` test itself never erases).
- Both issue repros still run clean under valgrind (`-DNDEBUG`) and with assertions on, and the 20000-write workload still reports sensible numbers (`Peak node bytes: 1056180`, `Expected worst case node bytes: 2240110`, no `totalBytes != mallocBytes` abort).
andrew
merged commit 4bec2cf4eb into main2026-10-27 19:32:44 +00:00
andrew
deleted branch weaselbot/issue-882026-10-27 19:32:45 +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
Two bugs made the
SHOW_MEMORYinstrumentation inInternal.hunusable: every build aborted (asserts on) or corrupted memory (asserts off) on ordinary valid API calls.Defect 1:
assert(!releaseDeferred)inNode::getCapacity()NodeAllocator<T>::releaseDeferred()only ever callsrelease()on nodes that still havereleaseDeferred == true, andrelease()callsremoveNode(), which readsn->getCapacity()underSHOW_MEMORY.partialKeyCapacityis not repurposed bydeferRelease(only theentry/forwardTounion member andparentare), so the assertion had no basis. It's dropped, with a comment explaining why deferred nodes are fine.Defect 2:
eraseTreereads freedparentpointers viaremoveKeyeraseTreepushes a node's children onto the worklist and then immediately releases the node, so by the time a child is visited itsparentpointer is dangling andremoveKey->getSearchPathLengthwalks freed memory (anddeferReleaserepurposesparentas the deferred-list link anyway). The worklist now carries each node's search path length, computed while its parent is still alive, and the accounting goes through a newremoveKey(Node *, int64_t searchPathLength)overload. Key bytes are now exact rather than garbage, sokeyBytesreturns to 0 when the tree is erased.Test
New
conflict_set_show_memory_testtarget compilesConflictSet.cppwith-DSHOW_MEMORY=1(and, likefuzz_driver, ASan+UBSan) and runs aShowMemoryTest.cppcovering the issue's repros: a node split with a pending deferred release, a mid-workloaderaseTreefrom exceeding the version window, and destruction of a large tree. It asserts the accounting is fully unwound (nodeBytes,partialCapacityBytes,totalKeys,keyBytesandmallocBytesall 0) after eachConflictSetis destroyed, and the instrumentation's owntotalBytes == mallocByteschecks abort on any inconsistency.SHOW_MEMORYis now overridable from the command line (#ifndefguard) so the target can enable it; the pre-commit guard against checking in#define SHOW_MEMORY 1still applies.Verification
g++ -O1 -g -std=c++20 min1.cpp ConflictSet.cpp -DSHOW_MEMORY=1, with and withoutNDEBUG, plusvalgrind -qand ASan): clean, exit 0, all accounting back to 0 at exit.getCapacity()assertion aborts; ASan reportsheap-use-after-free ... in getSearchPathLength, removeKey, eraseTree), so it's a real regression test.ctestsuite (Debug, asserts enabled): 8599/8599 passed, including the new test, all corpus fuzz/blackbox/valgrind tests and script tests. Release and clang builds also build and pass.Peak node bytes: 53008,Expected worst case node bytes: 112224, and nototalBytes != mallocBytesabort.Closes #88
Follow-up (review): eraseTree's search path length bookkeeping is SHOW_MEMORY-only
eraseTreeonly needs the search path lengths it carries on the worklist so that theSHOW_MEMORYkey accounting avoids walkingparentpointers of nodes that were already released. Those lengths now live on a parallel stack that only exists whenSHOW_MEMORYis enabled; other builds keep upstream's worklist of bareNode *and compute nothing extra (eraseTreeis byte-for-byte the same size, and the whole-O2object has the same.textsize as upstream).The coverage job compiles ConflictSet.cpp twice: once without SHOW_MEMORY, like the rest of the build, and once with it for the SHOW_MEMORY test. Each config previously saw a *different* definition of the accounting helpers: no-op `constexpr` stubs near the top of the file when SHOW_MEMORY was off, and the real definitions at the bottom when it was on. gcovr reads the .gcda files for a source file and merges them, and its default (strict) function merge mode asserts that a function name always maps to one line. Since `addNode`, `removeNode`, `addKey`, both `removeKey` overloads and `getSearchPathLength` were reported on two different lines, report generation aborted with AssertionError: Got function getSearchPathLength(Node*) on multiple lines: 99, 6002. Define those functions in exactly one place instead, and compile the accounting out from within the bodies. Then every configuration reports each function on the same line and the coverage data can be merged. The empty calls are inlined away: the Release shared library contains no calls to them. With the merge fixed, the accounting lines that only exist in the SHOW_MEMORY build show up in the report, so the coverage job's 100% line requirement covers them. Extend the SHOW_MEMORY test to grow a node through every node type (so `getNodeSize` covers every case) and to erase entries one at a time via `setOldestVersion` (so `removeKey` and the `internal_setOldestVersion` cross-check are covered). The remaining `abort()`s in the accounting are defensive checks that can never be taken on a passing run; mark them GCOVR_EXCL_LINE like the rest of the unreachable code in this file.`getNodeSize`'s unreachable `default:` sits inside ConflictSet.cpp's `GCOVR_EXCL_START`/`GCOVR_EXCL_STOP` block, so the `GCOVR_EXCL_LINE` markers on those two lines are redundant: they cannot change the report, but they make gcovr print (WARNING) GCOVR_EXCL_LINE found on line 6002 in excluded region started on line 5535 once per line for each of the four reports the coverage job writes. Drop them, matching the rest of the excluded tail, which carries no exclusion markers. Context: the previous coverage job for this branch did not fail in any of its steps. Build, Test (5754/5754 passed), Coverage report (`gcovr --fail-under-line 100` reported 100% for ConflictSet.cpp, LongestCommonPrefix.h and Metrics.h), the upload and the test summary all reported success; the job was marked failed while tearing the job container down. The post-actions (actions/cache, actions/checkout) could no longer `docker exec` into the container and the runner's rootless podman socket was gone ("Cannot connect to the Docker daemon at unix:///run/user/992/podman/podman.sock", "Error while stop job container"); the actions/cache service on 192.168.0.110:41379 had been refusing connections for the whole run. Verified locally on this commit: Debug, gcc and `--coverage` builds of the coverage job's configuration; 5754/5754 tests pass; merged line coverage (union over the library, SHOW_MEMORY and fuzz-driver objects, honouring the GCOVR_EXCL_START/STOP regions) is 100% for all three measured files, and no GCOVR_EXCL_LINE markers remain inside an excluded region.@@ -2757,0 +2764,4 @@struct ToFree {Node *n;// Length of the key leading to `n`. See `getSearchPathLength`.int64_t searchPathLength;Can we only include searchPathLength when SHOW_MEMORY=1 ?
Addressed in
80f084c(ConflictSet.cppline 2767 is gone): the search path lengths are now only tracked whenSHOW_MEMORYis enabled.eraseTreekeeps the upstream worklist of bareNode *; the lengths live on a parallel stack that only exists under#if SHOW_MEMORY, and the per-child length is computed in aqueueChildlambda whoseSHOW_MEMORYbranch is the only thing that readschild->partialKeyLen. In non-SHOW_MEMORYbuildsqueueChildis justtoFree.push_back(child), andremoveKey(n, /*searchPathLength=*/0)is the same empty stub it is everywhere else, so nothing is computed or carried.Verified that this is actually free in the normal build:
eraseTreein an-O2non-SHOW_MEMORYobject is the same code as upstream: whole-object.textis byte-identical in size (161331), and the disassembly oferaseTreediffers from upstream only in jump offsets and a few removednops (it comes out 20 bytes smaller).-Wall -Wextra -Wunusedis clean in bothSHOW_MEMORY=0andSHOW_MEMORY=1builds.ctestsuite (Debug, asserts on): 8599/8599 passed, includingconflict_set_show_memory_test.SHOW_MEMORYobject coverschildSearchPathLength, the parallel stack pushes/pops and bothNode256bulk-append lines; the library object covers the#elsebranch and the sharedqueueChild/switchlines (includingNode48, which theSHOW_MEMORYtest itself never erases).-DNDEBUG) and with assertions on, and the 20000-write workload still reports sensible numbers (Peak node bytes: 1056180,Expected worst case node bytes: 2240110, nototalBytes != mallocBytesabort).