weaselab/conflict-set
1
Fork 1
Code Issues 6 Pull Requests Actions 1 Packages Releases 13 Activity

SHOW_MEMORY builds crash on valid input: assert(!releaseDeferred) in getCapacity(), and heap-use-after-free in eraseTree/removeKey #88

New Issue
Closed
opened 2026-10-25 17:19:06 +00:00 by weaselbot · 1 comment
weaselbot commented 2026-10-25 17:19:06 +00:00
Member
Copy link
Copy source

Internal.h's SHOW_MEMORY instrumentation (Internal.h:26) cannot be used at all. With SHOW_MEMORY set to 1, a build with assertions enabled aborts on the second write, and an NDEBUG build performs a heap-use-after-free in eraseTree. Both are reachable from plain valid API calls (two addWrites on keys with a common prefix), so the peak-memory report and the internal totalBytes != mallocBytes checks can never be exercised.

Repro

// min1.cpp
#include "ConflictSet.h"
using namespace weaselab;
int main() {
  ConflictSet cs{0};
  ConflictSet::WriteRange w1{{(const uint8_t *)"a", 1}, {nullptr, 0}};
  cs.addWrites(&w1, 1, 1);
  ConflictSet::WriteRange w2{{(const uint8_t *)"ab", 2}, {nullptr, 0}};
  cs.addWrites(&w2, 1, 2);
}

$ sed -i 's/^#define SHOW_MEMORY 0/#define SHOW_MEMORY 1/' Internal.h
$ g++ -O1 -g -std=c++20 min1.cpp ConflictSet.cpp -Iinclude -isystem third_party/valgrind
$ ./a.out
a.out: ConflictSet.cpp:310: int32_t Node::getCapacity() const: Assertion `!releaseDeferred' failed.

Defect 1: assert(!releaseDeferred) in getCapacity() is guaranteed to fire on deferred release

Node::getCapacity() (ConflictSet.cpp:309-312) asserts !releaseDeferred, but NodeAllocator<T>::releaseDeferred() (ConflictSet.cpp:754-760) by construction only ever calls release() on nodes that still have releaseDeferred == true (they were put on the list by deferRelease, ConflictSet.cpp:747-752). release() calls removeNode() (ConflictSet.cpp:742-745), and under SHOW_MEMORY removeNode() calls n->getCapacity() (ConflictSet.cpp:5996-5999), which trips the assert.

Backtrace (from the repro above, gdb):

#5  Node::getCapacity (this=0x456e00) at ConflictSet.cpp:310
#6  removeNode (n=0x456e00) at ConflictSet.cpp:5998
#7  NodeAllocator<Node0>::release (p=0x456e00) at ConflictSet.cpp:742
#8  NodeAllocator<Node0>::releaseDeferred (this=0x456080) at ConflictSet.cpp:758
#9  WriteContext::releaseDeferred (this=0x456030) at ConflictSet.cpp:895
#10 ConflictSet::Impl::addWrites (...) at ConflictSet.cpp:5139

The second addWrites splits the Node0 for "a" into a Node3, which deferReleases the old node; the flush at ConflictSet.cpp:5139 then aborts. Any workload that replaces a node (upsize, capacity change, downsize) hits this, so SHOW_MEMORY + assertions cannot run anything.

Defect 2: eraseTree reads freed parent pointers via removeKey

With -DNDEBUG (asserts off) the same program runs, but destruction is a heap-use-after-free:

$ g++ -O1 -g -std=c++20 -DNDEBUG min1.cpp ConflictSet.cpp -Iinclude -isystem third_party/valgrind
$ valgrind -q ./a.out
==577687== Invalid read of size 4
==577687==    at 0x402968: getSearchPathLength(Node*) (ConflictSet.cpp:5975)
==577687==    by 0x40535B: removeKey(Node*) (ConflictSet.cpp:6017)
==577687==    by 0x406D13: eraseTree(Node*, WriteContext*) (ConflictSet.cpp:2767)
==577687==    by 0x407707: ~Impl (ConflictSet.cpp:5347)
==577687==    by 0x407707: internal_destroy(...) (ConflictSet.cpp:5490)
==577687==    by 0x4077E7: ConflictSet::~ConflictSet() (ConflictSet.cpp:5595)
==577687==  Address 0x4e6ef70 is 16 bytes inside a block of size 72 free'd
==577687==    at 0x488870C: free (vg_replace_malloc.c:950)
==577687==    by 0x406C37: safe_free (Internal.h:147)
==577687==    by 0x406C37: release (ConflictSet.cpp:744)
==577687==    by 0x406C37: release<Node3> (ConflictSet.cpp:866)
==577687==    by 0x406C37: eraseTree(Node*, WriteContext*) (ConflictSet.cpp:2779)

eraseTree (ConflictSet.cpp:2756-2806) pushes a node's children onto the worklist and then immediately frees the node (writeContext->release(...)), so by the time a child is processed its parent pointer refers to freed memory. removeKey (ConflictSet.cpp:6014) → getSearchPathLength (ConflictSet.cpp:5971-5983) walks n->parent until it is nullptr, dereferencing the freed node every step. The length is then garbage (so keyBytes/peakKeyBytes -- printed as "Peak key bytes" -- are garbage too) and, as seen above, the walk can also run off into unmapped memory (plain segfault, not just a valgrind complaint).

This is also reachable in the middle of a workload, not only at destruction: Impl::addWrites calls eraseTree at ConflictSet.cpp:5087 when the version window is exceeded, e.g.

ConflictSet cs{0};
ConflictSet::WriteRange w{{(const uint8_t *)"abc", 3}, {nullptr, 0}};
cs.addWrites(&w, 1, 1);
cs.addWrites(&w, 1, int64_t(1) << 40);  // > 2e9 jump -> eraseTree + init

segfaults (eraseTree -> removeKey -> getSearchPathLength, invalid read of a freed 72-byte Node3).

Note that deferRelease also repurposes Node::parent as the deferred-list link (ConflictSet.cpp:750), so any bookkeeping that walks parent pointers over a deferred node is meaningless as well.

Impact

SHOW_MEMORY is the only in-tree way to observe node bytes, partial-key capacity, key bytes and the "peak node bytes <= peak keys * kBytesPerKey" bound (ConflictSet.cpp:5985-6037, see also the comment block at ConflictSet.cpp:673-712), and the totalBytes != mallocBytes consistency checks for getBytes()/memory_bytes (ConflictSet.cpp:5463-5467 and 5475-5479). Since any workload aborts (assert build) or corrupts memory / crashes (NDEBUG build), those checks and reports cannot be run, so memory-usage regressions in the data structure would go unnoticed.

If both crashes are worked around locally (drop the getCapacity() assert and don't walk parent pointers in removeKey), the instrumentation runs fine and produces sensible output, e.g. for a 20000-write workload: Peak node bytes: 139864, Expected worst case node bytes: 195440, and the totalBytes == mallocBytes check does not fire. So these two lines are the only blockers.

Suggested fix

  • removeNode() should not go through getCapacity(): use n->partialKeyCapacity (or relax the assert in getCapacity() so deferred nodes are allowed).
  • eraseTree() should account for key length before freeing a node, or getSearchPathLength must not be called on a node whose ancestors have already been released (e.g. accumulate the search-path length of children while the parent is still alive and pass the decrement down the worklist).
`Internal.h`'s `SHOW_MEMORY` instrumentation (`Internal.h:26`) cannot be used at all. With `SHOW_MEMORY` set to 1, a build with assertions enabled aborts on the second write, and an `NDEBUG` build performs a heap-use-after-free in `eraseTree`. Both are reachable from plain valid API calls (two `addWrites` on keys with a common prefix), so the peak-memory report and the internal `totalBytes != mallocBytes` checks can never be exercised. ## Repro ```c++ // min1.cpp #include "ConflictSet.h" using namespace weaselab; int main() { ConflictSet cs{0}; ConflictSet::WriteRange w1{{(const uint8_t *)"a", 1}, {nullptr, 0}}; cs.addWrites(&w1, 1, 1); ConflictSet::WriteRange w2{{(const uint8_t *)"ab", 2}, {nullptr, 0}}; cs.addWrites(&w2, 1, 2); } ``` ```sh $ sed -i 's/^#define SHOW_MEMORY 0/#define SHOW_MEMORY 1/' Internal.h $ g++ -O1 -g -std=c++20 min1.cpp ConflictSet.cpp -Iinclude -isystem third_party/valgrind $ ./a.out a.out: ConflictSet.cpp:310: int32_t Node::getCapacity() const: Assertion `!releaseDeferred' failed. ``` ## Defect 1: `assert(!releaseDeferred)` in `getCapacity()` is guaranteed to fire on deferred release `Node::getCapacity()` (`ConflictSet.cpp:309-312`) asserts `!releaseDeferred`, but `NodeAllocator<T>::releaseDeferred()` (`ConflictSet.cpp:754-760`) by construction only ever calls `release()` on nodes that *still have* `releaseDeferred == true` (they were put on the list by `deferRelease`, `ConflictSet.cpp:747-752`). `release()` calls `removeNode()` (`ConflictSet.cpp:742-745`), and under `SHOW_MEMORY` `removeNode()` calls `n->getCapacity()` (`ConflictSet.cpp:5996-5999`), which trips the assert. Backtrace (from the repro above, gdb): ``` #5 Node::getCapacity (this=0x456e00) at ConflictSet.cpp:310 #6 removeNode (n=0x456e00) at ConflictSet.cpp:5998 #7 NodeAllocator<Node0>::release (p=0x456e00) at ConflictSet.cpp:742 #8 NodeAllocator<Node0>::releaseDeferred (this=0x456080) at ConflictSet.cpp:758 #9 WriteContext::releaseDeferred (this=0x456030) at ConflictSet.cpp:895 #10 ConflictSet::Impl::addWrites (...) at ConflictSet.cpp:5139 ``` The second `addWrites` splits the `Node0` for `"a"` into a `Node3`, which `deferRelease`s the old node; the flush at `ConflictSet.cpp:5139` then aborts. Any workload that replaces a node (upsize, capacity change, downsize) hits this, so `SHOW_MEMORY` + assertions cannot run anything. ## Defect 2: `eraseTree` reads freed `parent` pointers via `removeKey` With `-DNDEBUG` (asserts off) the same program runs, but destruction is a heap-use-after-free: ```sh $ g++ -O1 -g -std=c++20 -DNDEBUG min1.cpp ConflictSet.cpp -Iinclude -isystem third_party/valgrind $ valgrind -q ./a.out ==577687== Invalid read of size 4 ==577687== at 0x402968: getSearchPathLength(Node*) (ConflictSet.cpp:5975) ==577687== by 0x40535B: removeKey(Node*) (ConflictSet.cpp:6017) ==577687== by 0x406D13: eraseTree(Node*, WriteContext*) (ConflictSet.cpp:2767) ==577687== by 0x407707: ~Impl (ConflictSet.cpp:5347) ==577687== by 0x407707: internal_destroy(...) (ConflictSet.cpp:5490) ==577687== by 0x4077E7: ConflictSet::~ConflictSet() (ConflictSet.cpp:5595) ==577687== Address 0x4e6ef70 is 16 bytes inside a block of size 72 free'd ==577687== at 0x488870C: free (vg_replace_malloc.c:950) ==577687== by 0x406C37: safe_free (Internal.h:147) ==577687== by 0x406C37: release (ConflictSet.cpp:744) ==577687== by 0x406C37: release<Node3> (ConflictSet.cpp:866) ==577687== by 0x406C37: eraseTree(Node*, WriteContext*) (ConflictSet.cpp:2779) ``` `eraseTree` (`ConflictSet.cpp:2756-2806`) pushes a node's children onto the worklist and then *immediately* frees the node (`writeContext->release(...)`), so by the time a child is processed its `parent` pointer refers to freed memory. `removeKey` (`ConflictSet.cpp:6014`) → `getSearchPathLength` (`ConflictSet.cpp:5971-5983`) walks `n->parent` until it is `nullptr`, dereferencing the freed node every step. The length is then garbage (so `keyBytes`/`peakKeyBytes` -- printed as "Peak key bytes" -- are garbage too) and, as seen above, the walk can also run off into unmapped memory (plain segfault, not just a valgrind complaint). This is also reachable in the middle of a workload, not only at destruction: `Impl::addWrites` calls `eraseTree` at `ConflictSet.cpp:5087` when the version window is exceeded, e.g. ```c++ ConflictSet cs{0}; ConflictSet::WriteRange w{{(const uint8_t *)"abc", 3}, {nullptr, 0}}; cs.addWrites(&w, 1, 1); cs.addWrites(&w, 1, int64_t(1) << 40); // > 2e9 jump -> eraseTree + init ``` segfaults (`eraseTree` -> `removeKey` -> `getSearchPathLength`, invalid read of a freed 72-byte `Node3`). Note that `deferRelease` also repurposes `Node::parent` as the deferred-list link (`ConflictSet.cpp:750`), so any bookkeeping that walks parent pointers over a deferred node is meaningless as well. ## Impact `SHOW_MEMORY` is the only in-tree way to observe node bytes, partial-key capacity, key bytes and the "peak node bytes <= peak keys * kBytesPerKey" bound (`ConflictSet.cpp:5985-6037`, see also the comment block at `ConflictSet.cpp:673-712`), and the `totalBytes != mallocBytes` consistency checks for `getBytes()`/`memory_bytes` (`ConflictSet.cpp:5463-5467` and `5475-5479`). Since any workload aborts (assert build) or corrupts memory / crashes (NDEBUG build), those checks and reports cannot be run, so memory-usage regressions in the data structure would go unnoticed. If both crashes are worked around locally (drop the `getCapacity()` assert and don't walk parent pointers in `removeKey`), the instrumentation runs fine and produces sensible output, e.g. for a 20000-write workload: `Peak node bytes: 139864`, `Expected worst case node bytes: 195440`, and the `totalBytes == mallocBytes` check does not fire. So these two lines are the only blockers. ## Suggested fix * `removeNode()` should not go through `getCapacity()`: use `n->partialKeyCapacity` (or relax the assert in `getCapacity()` so deferred nodes are allowed). * `eraseTree()` should account for key length before freeing a node, or `getSearchPathLength` must not be called on a node whose ancestors have already been released (e.g. accumulate the search-path length of children while the parent is still alive and pass the decrement down the worklist).
weaselbot was assigned by andrew 2026-10-26 21:34:05 +00:00
weaselbot commented 2026-10-27 01:47:52 +00:00
Author
Member
Copy link
Copy source

Investigated the failing coverage job on PR #91 (run 1016, job 2640, head df98681). The job did not fail in any of its steps — Gitea's own job detail reports success for all nine of them:

step conclusion
Build (41 targets) success
Test success (ctest, no failed tests)
Coverage report success (gcovr --fail-under-line 100)
Upload results to MinIO success (skipped, no credentials)
Test summary success (✅ All 5754 tests passed)

The report itself is green:

ConflictSet.cpp                             3079    3079   100%
LongestCommonPrefix.h                         54      54   100%
Metrics.h                                     30      30   100%
TOTAL                                       3163    3163   100%

The job was marked failed only after the last step, while the runner was tearing the job container down:

Run Post actions/cache@v4
docker exec cmd=[node .../dist/save/index.js]
Failure - Post actions/cache@v4
##[error]Get "http://%2Frun%2Fuser%2F992%2Fpodman%2Fpodman.sock/.../archive?path=...": context canceled
docker daemon ping during version negotiation failed, continuing: ... Cannot connect to the Docker daemon at unix:///run/user/992/podman/podman.sock
Error while stop job container: Cannot connect to the Docker daemon ...
Job failed

So the job container (and the rootless podman daemon on the udon runner, /run/user/992/podman/podman.sock) disappeared a few seconds after the last step finished, the post-actions could no longer docker exec into it, and the job was marked failed. Nothing in the build, the test suite or the coverage check failed. The actions/cache service (192.168.0.110:41379) was also unreachable for this whole run (::warning::Failed to restore: getCacheEntry failed: connect ECONNREFUSED), so restores were misses and saves were no-ops in every job of the run; that alone is only warnings, as the other eight jobs show.

What I verified locally against df98681 (fresh clone):

  • The coverage job's build config (cmake -G Ninja -DCMAKE_C_FLAGS=--coverage -DCMAKE_CXX_FLAGS=--coverage -DCMAKE_BUILD_TYPE=Debug -DDISABLE_TSAN=ON) builds, and ctest -j8 gives 100% tests passed, 0 tests failed out of 5754 — the same 5754 tests the CI job ran, including the new conflict_set_show_memory_test. Same for the plain Debug config and for a gcc build.
  • Recomputed merged line coverage the way gcovr does (union of the three ConflictSet.cpp objects — library, SHOW_MEMORY test, fuzz driver — honouring the GCOVR_EXCL_START/STOP regions): 100% of measured lines for ConflictSet.cpp, LongestCommonPrefix.h and Metrics.h, zero uncovered. (This needs a local MUSTTAIL workaround: this sandbox is aarch64, where clang/gcc reject musttail under --coverage; the CI coverage job runs on x86_64, where the same source builds fine, as its Build step shows.)
  • The earlier, genuine coverage failure on bba328f (AssertionError: Got function ... on multiple lines) stays fixed: the accounting helpers are defined exactly once, so every configuration reports them on the same line.

The only thing in the log that is attributable to my change is cosmetic: gcovr's GCOVR_EXCL_LINE found on line 6002 in excluded region started on line 5535 warnings, from two markers my previous commit added to getNodeSize's default: even though that code is already inside the file's excluded tail region. I pushed c0bd10e to drop those redundant markers (no functional change; the lines stay excluded by the enclosing region, and merged line coverage is still 100%).

Since I have no permission to re-run the workflow through the API, that push re-triggers CI. If the coverage job fails the same way again — every step green, then Job failed after Error while stop job container — then it is the runner (udon: rootless podman at /run/user/992/podman) and/or the cache service on 192.168.0.110:41379 that needs attention, not this change.

Investigated the failing `coverage` job on PR #91 (run 1016, job 2640, head df98681). **The job did not fail in any of its steps** — Gitea's own job detail reports `success` for all nine of them: | step | conclusion | | --- | --- | | Build (41 targets) | success | | Test | success (`ctest`, no failed tests) | | Coverage report | success (`gcovr --fail-under-line 100`) | | Upload results to MinIO | success (skipped, no credentials) | | Test summary | success (`✅ All 5754 tests passed`) | The report itself is green: ``` ConflictSet.cpp 3079 3079 100% LongestCommonPrefix.h 54 54 100% Metrics.h 30 30 100% TOTAL 3163 3163 100% ``` The job was marked failed only *after* the last step, while the runner was tearing the job container down: ``` Run Post actions/cache@v4 docker exec cmd=[node .../dist/save/index.js] Failure - Post actions/cache@v4 ##[error]Get "http://%2Frun%2Fuser%2F992%2Fpodman%2Fpodman.sock/.../archive?path=...": context canceled docker daemon ping during version negotiation failed, continuing: ... Cannot connect to the Docker daemon at unix:///run/user/992/podman/podman.sock Error while stop job container: Cannot connect to the Docker daemon ... Job failed ``` So the job container (and the rootless podman daemon on the `udon` runner, `/run/user/992/podman/podman.sock`) disappeared a few seconds after the last step finished, the post-actions could no longer `docker exec` into it, and the job was marked failed. Nothing in the build, the test suite or the coverage check failed. The `actions/cache` service (`192.168.0.110:41379`) was also unreachable for this whole run (`::warning::Failed to restore: getCacheEntry failed: connect ECONNREFUSED`), so restores were misses and saves were no-ops in every job of the run; that alone is only warnings, as the other eight jobs show. What I verified locally against df98681 (fresh clone): * The coverage job's build config (`cmake -G Ninja -DCMAKE_C_FLAGS=--coverage -DCMAKE_CXX_FLAGS=--coverage -DCMAKE_BUILD_TYPE=Debug -DDISABLE_TSAN=ON`) builds, and `ctest -j8` gives `100% tests passed, 0 tests failed out of 5754` — the same 5754 tests the CI job ran, including the new `conflict_set_show_memory_test`. Same for the plain `Debug` config and for a `gcc` build. * Recomputed merged line coverage the way gcovr does (union of the three `ConflictSet.cpp` objects — library, SHOW_MEMORY test, fuzz driver — honouring the `GCOVR_EXCL_START/STOP` regions): 100% of measured lines for `ConflictSet.cpp`, `LongestCommonPrefix.h` and `Metrics.h`, zero uncovered. (This needs a local `MUSTTAIL` workaround: this sandbox is aarch64, where clang/gcc reject `musttail` under `--coverage`; the CI coverage job runs on x86_64, where the same source builds fine, as its Build step shows.) * The earlier, genuine coverage failure on bba328f (`AssertionError: Got function ... on multiple lines`) stays fixed: the accounting helpers are defined exactly once, so every configuration reports them on the same line. The only thing in the log that is attributable to my change is cosmetic: gcovr's `GCOVR_EXCL_LINE found on line 6002 in excluded region started on line 5535` warnings, from two markers my previous commit added to `getNodeSize`'s `default:` even though that code is already inside the file's excluded tail region. I pushed c0bd10e to drop those redundant markers (no functional change; the lines stay excluded by the enclosing region, and merged line coverage is still 100%). Since I have no permission to re-run the workflow through the API, that push re-triggers CI. If the `coverage` job fails the same way again — every step green, then `Job failed` after `Error while stop job container` — then it is the runner (`udon`: rootless podman at `/run/user/992/podman`) and/or the cache service on `192.168.0.110:41379` that needs attention, not this change.
Sign in to join this conversation.
No Branch/Tag Specified
Labels
Clear labels
bug
Something is not working
 enhancement
New feature
 investigation
wontfix
This won't be fixed
missing-test-coverage
Issues having to do with missing test coverage
No labels
Milestone
No items
No Milestone
Assignees
Clear assignees
andrew weaselbot
No Assignees weaselbot
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: weaselab/conflict-set#88