1122 Commits

This Branch

This Branch

All Branches

Author	SHA1	Message	Date
andrew	e23018c952	Merge pull request 'Improve perf/codegen' (#94) from perf into main ... Reviewed-on: #94	2026-10-27 20:45:52 +00:00
andrew	b1c1f8f2ee	Merge pull request 'Replace test_fixup_256 with a regression test for the Node256 fixupMaxVersion false-Commit bug' (#90) from weaselbot/conflict-set:weaselbot/issue-89 into main ... Reviewed-on: #90	2026-10-27 19:33:17 +00:00
andrew	4bec2cf4eb	Merge pull request 'Make SHOW_MEMORY builds work: fix deferred node capacity assert and eraseTree use-after-free' (#91) from weaselbot/conflict-set:weaselbot/issue-88 into main ... Reviewed-on: #91	2026-10-27 19:32:43 +00:00
andrew	fa1701479c	Merge pull request 'SkipList: don't lower oldestVersion in setOldestVersion' (#92) from weaselbot/conflict-set:weaselbot/issue-87 into main ... Reviewed-on: #92	2026-10-27 19:30:11 +00:00
andrew	20e2e332e4	Merge pull request 'Skip DEBUG_VERBOSE end print for point writes (uninitialized Result::endRemaining)' (#93) from weaselbot/conflict-set:weaselbot/issue-86 into main ... Reviewed-on: #93	2026-10-27 19:29:26 +00:00
andrew	23d092ab69	Avoid IFUNC for short prefixes in LCP	2026-10-27 15:09:58 -04:00
andrew	84bf5707f9	Skip IFUNC call for Node3 in fixupMaxVersion	2026-10-27 14:21:58 -04:00
weaselbot	c94e9aaee6	Remove test_fixup_256, which cannot detect the bug ... Every child of the Node256 in test_fixup_256 is written at the same version, so max(childMaxVersion[0..15]) and max(maxOfMax) agree and the buggy code passes. test_fixup_256_heterogeneous_versions covers the same Node256-under-a-range-end shape with distinct versions, so keep only that.	2026-10-27 14:10:36 -04:00
andrew	d71d963d9a	Improve codegen for checkMaxBetweenExclusiveImpl(Node3 ... $ ninja -C build && nm -C -S build/CMakeFiles/conflict-set-object.dir/ConflictSet.cpp.o | grep 'checkMaxBetweenExclusive(Node3' ... 0000000000000000 0000000000000529 T checkMaxBetweenExclusive(Node3*, int, int, InternalVersionT, ReadContext*) $ git stash pop ... $ ninja -C build && nm -C -S build/CMakeFiles/conflict-set-object.dir/ConflictSet.cpp.o | grep 'checkMaxBetweenExclusive(Node3' ... 0000000000000000 0000000000000106 T checkMaxBetweenExclusive(Node3*, int, int, InternalVersionT, ReadContext*)	2026-10-27 14:06:58 -04:00
andrew	dabddbcb56	Use individual comparison operators instead of operator<=> ... This gives better codegen	2026-10-27 13:55:44 -04:00
andrew	3b4271dac1	Update readme	2026-10-27 13:44:11 -04:00
weaselbot	a792352387	Skip DEBUG_VERBOSE end print for point writes ... Point writes are recorded with the 2-argument interleaved_insert::Result constructor, which leaves endRemaining indeterminate, so the Phase 2 debug print in interleavedWrites read an indeterminate span and, with stack garbage left over from an earlier call, dereferenced a freed pointer. Confirmed with valgrind on a point write following a range write: "Conditional jump or move depends on uninitialised value(s)" and "Invalid read of size 1" at ConflictSet.cpp:4984, and ASan heap-use-after-free in the same place. Only print the end search path and spans for range writes, mirroring the `if (e != nullptr)` check that already guards the endInsertionPoint forwarding-chain fixup a few lines above. Production code already treats endRemaining as range-write only, so nothing else changes.	2026-10-27 13:07:00 -04:00
weaselbot	56e0673fc7	Make the skip list corpus tests opt-in, not default ... Review feedback: running the skip list tests on every default ctest run is a waste of time. Gate them behind a TEST_SKIP_LIST CMake option, off by default, so they remain easy to run when cross-checking SkipList.cpp against ReferenceImpl. Verified with -DTEST_SKIP_LIST=ON: all 2845 skip_list corpus tests pass; the default test list is unchanged.	2026-10-27 13:02:45 -04:00
weaselbot	80f084cc43	Compile eraseTree's search path length bookkeeping out of non-SHOW_MEMORY builds ... `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.	2026-10-27 12:56:55 -04:00
weaselbot	c0bd10effa	Drop redundant coverage exclusion markers in the excluded tail region ... `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.	2026-10-26 21:47:41 -04:00
weaselbot	df986810ff	Give the SHOW_MEMORY instrumentation a single definition per function ... 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.	2026-10-26 20:34:45 -04:00
weaselbot	8b6389236a	Enable the skip list corpus tests by default ... driver_skip_list checks SkipList.cpp against ReferenceImpl, but its tests were disabled, so the implementation diverged from the documented API without anything noticing. The corpus tests pass in Debug and Release builds, so run them like the other implementations' tests.	2026-10-26 18:46:02 -04:00
weaselbot	b22d5f4816	SkipList: don't lower oldestVersion in setOldestVersion ... setOldestVersion is documented to set oldestVersion to the maximum of its previous value and its argument, so passing a version older than the current oldestVersion is valid input. SkipList.cpp instead asserted that the argument was monotonically non-decreasing, aborting Debug builds, and with NDEBUG it lowered oldestVersion. That resurrected a window of versions that callers had been told result in TooOld: reads in that window were evaluated against entries that may already have been garbage collected, so they could report Commit or Conflict instead. Leave oldestVersion alone when the argument isn't newer, mirroring HashTable.cpp. Falling through on equality keeps garbage collection making progress without advancing the oldest version. Add a scripted regression test, which bisimulates against the radix tree.	2026-10-26 18:46:00 -04:00
weaselbot	bba328f79f	Fix SHOW_MEMORY crashes on valid input ... `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.	2026-10-26 18:32:03 -04:00
weaselbot	3d3184ef5f	Add regression test for Node256 fixupMaxVersion	2026-10-26 18:20:37 -04:00
andrew	ba781b8875	Spec that addWrites advances oldestVersion minimally ... The old wording only gave the lower bound oldestVersion >= newestVersion - two billion, which an implementation could satisfy by discarding more readable versions than necessary. State that oldestVersion becomes the larger of its previous value and newestVersion - two billion.	2026-10-10 14:04:17 -04:00
andrew	8621662d3c	Don't poison Node48 reverseIndex ... Follows the reasoning of "Remove redundant version update": a write can never lower the logical max version of a key range, so there's no read that didn't pass before that should pass after a write. The check stays exact reading the physical childMaxVersion and reverseIndex of unused slots, so scan16's whole-page reads of them are well-defined and intended. The client requests only produced valgrind false positives. Keep the initialization, drop the poisoning.	2026-10-10 13:58:58 -04:00
andrew	9c721bcdca	Stop printing metrics from TestDriver ... The per-corpus-file Prometheus dump was debug-only output that nothing consumes. It also floods stdout well past ctest's failed-output cap, so the real failure (e.g. a valgrind report) never made it into the CI summary.	2026-10-10 13:55:02 -04:00
andrew	4ef10b106a	Fix wrong-result bug. Previously it could incorrectly report Commit ... Blog post forthcoming	2026-10-09 16:34:33 -04:00
andrew	9b6dd51b85	Add a spec for fixupMaxVersion	2026-10-09 16:28:36 -04:00
andrew	647ba5beb1	Remove redundant version update ... A write can never lower the logical max version of a key range. There's no read that didn't pass before that should pass after a write.	2026-10-09 16:19:20 -04:00
andrew	2f9f49c692	Use doxygen pre/post tags and make public api more precise	2026-10-09 15:09:58 -04:00
andrew	6a6e36909f	Fix assert memcmp size	2026-10-09 15:05:39 -04:00
andrew	46d1f05333	Avoid signed overflow ... This only happens at implausibly high version numbers, but the fix is straightforward so we'll just do it anyway. Closes #84	2026-09-23 11:36:12 -04:00
andrew	8a16f9a6d6	Merge pull request 'Fix broken endInsertionPoint forwarding chain resolution in DEBUG_VERBOSE print' (#83) from weaselbot/conflict-set:weaselbot/issue-82 into main ... Reviewed-on: #83	2026-08-31 01:14:10 +00:00
weaselbot	9a2c64d31c	Fix broken endInsertionPoint forwarding chain resolution in DEBUG_VERBOSE print ... In the Phase 2 debug block of ConflictSet::Impl::interleavedWrites, the loop resolving the end insertion point's releaseDeferred/forwardTo chain followed the begin node's chain instead (e = b->forwardTo). Once b is resolved, b->forwardTo aliases the Entry union member, so e was assigned garbage derived from version bytes and the loop dereferenced it, causing a SEGV or hang whenever DEBUG_VERBOSE builds traced writes. Use the end node's own forwarding chain (e = e->forwardTo), matching the production code in the same loop body and in Phase 3.	2026-08-30 20:17:22 -04:00
andrew	ec1b476977	Merge pull request 'Fix NEON type mismatch in conflictMask16 for gcc/aarch64 + USE_64_BIT=1' (#81) from weaselbot/conflict-set:weaselbot/issue-80 into main ... Reviewed-on: http://git.weaselab.dev/weaselab/conflict-set/pulls/81	2026-08-18 17:39:48 +00:00
weaselbot	8c55e835c4	Fix NEON type mismatch in conflictMask16 for gcc/aarch64 + USE_64_BIT=1 ... vcgtq_s64 returns uint64x2_t but vmovn_s64 requires int64x2_t. clang accepts the implicit conversion via lax vector conversions, but gcc does not. Add an explicit vreinterpretq_s64_u64 so the code compiles with gcc on aarch64 when USE_64_BIT=1. This path is otherwise untested in CI (aarch64 matrices use USE_64_BIT=0; the 64-bit-versions matrix uses amd64 AVX compare16). Closes #80	2026-08-16 21:16:23 -04:00
andrew	af76c4d623	Merge pull request 'Fix hash_table setOldestVersion infinite loop on empty map' (#79) from weaselbot/conflict-set:weaselbot/issue-78 into main ... Reviewed-on: http://git.weaselab.dev/weaselab/conflict-set/pulls/79	2026-08-17 00:25:27 +00:00
weaselbot	6db080a34c	Fix hash_table setOldestVersion infinite loop on empty map ... setOldestVersion's GC pass charges keyUpdates at 2x the entry count, so when every entry has version <= oldestVersion and is erased, keyUpdates remains > 0 while the map is empty. The outer while(keyUpdates > 0) loop then reset iter to map.begin() (== end() for an empty map) and the inner for loop never executed, spinning forever. Break out of the while loop when the map is exhausted, so the call returns normally. Closes #78	2026-08-16 13:02:50 -04:00
andrew	cdbad1c013	Merge pull request 'Replace SIMD assembly with initialized Node16::index + valgrind client request' (#77) from client-request-instead-of-asm into main ... Reviewed-on: #77	2026-08-04 00:07:19 +00:00
andrew	6d9810fe7f	Poison Node48 reverseIndex slot on erase ... When a Node48 loses a child, the vacated reverseIndex slot would otherwise remain defined, letting valgrind miss reads that rely on the stale value. Mark it undefined, mirroring the existing poisoning of the vacated children slot.	2026-08-03 17:38:21 -04:00
andrew	bae2b22e95	Replace SIMD assembly with initialized Node16::index + valgrind client request ... Commit 6fed133 moved SIMD operations on Node16::index into file-level assembly (later extended to aarch64) to avoid reading indeterminate bytes (UB in C++). Revert that in favor of a simpler, architecture-independent fix: - Restore the original HAS_AVX / HAS_ARM_NEON intrinsics at the affected call sites, keeping the newer conflictMask16 helper and scalar fallback. - memset Node16::index in both copy constructors (from Node3 and Node48) so the [numChildren, 16) tail is always initialized, making the full 16-byte SIMD loads well-defined. This also fixes the same latent UB in the NEON path and the Node16->Node16 full-array memcpy. - Issue a VALGRIND_MAKE_MEM_UNDEFINED client request on the tail so valgrind still flags any read that relies on the unused slots rather than numChildren. - Drop simd.h, simd_x86_64.S, simd_aarch64.S, and the CMake ASM wiring.	2026-08-03 17:32:41 -04:00
andrew	b11e92ee0b	Merge pull request 'Move aarch64 Node16 SIMD index loads into assembly' (#76) from weaselbot/conflict-set:weaselbot/issue-68 into main ... Reviewed-on: #76	2026-08-03 13:42:45 +00:00
weaselbot	e02dd41f74	Address review: drop unused bti c landing pads, fix rationale comment	2026-08-03 09:17:28 -04:00
andrew	b0e326aacc	Merge pull request 'ci: run MSan on arm64' (#74) from weaselbot/conflict-set:weaselbot/issue-73 into main ... Reviewed-on: #74	2026-08-03 12:27:49 +00:00
andrew	1179c1f56e	Merge pull request 'Fix ARM NEON scan helpers truncating 64-bit versions' (#75) from weaselbot/conflict-set:weaselbot/issue-69 into main ... Reviewed-on: #75	2026-08-03 12:26:03 +00:00
andrew	bdbac1556d	Merge pull request 'Correct rationale in simd_x86_64.S comment' (#72) from weaselbot/conflict-set:weaselbot/issue-71 into main ... Reviewed-on: #72	2026-08-03 04:59:26 +00:00
andrew	0103837488	Merge pull request 'Run valgrind in arm64 release in CI' (#70) from valgrind-in-arm into main ... Reviewed-on: #70	2026-08-03 04:34:34 +00:00
weaselbot	d040ed63a4	Move aarch64 Node16 SIMD index loads into assembly ... The aarch64 NEON paths in getNodeIndex/getNodeIndexExists, getChildGeq(Node16*), scan16, and checkMaxBetweenExclusiveImpl<Node16> loaded the full 16-element Node16::index array (and the Node48 reverseIndex array via scan16) with NEON intrinsics, then masked the result down to [0, numChildren). Only the in-use slots are initialized; the unused bytes are indeterminate, so the wide loads were undefined behavior in C++ (per [basic.indet]) even though the trailing lanes were discarded. MSan reports this on x86-64; on aarch64 it is the same UB but MSan's imprecise modeling doesn't flag it at -O0, so there is no red->green test. Mirror the existing x86-64 fix (commit 6fed133): implement the index operations in file-level assembly, where loading and operating on indeterminate values is well-defined. Add simd_aarch64.S with find_eq_16, find_ge_16, and mask_in_range_16. AArch64 lacks pmovmskb, so (like the prior NEON code) these return a 64-bit nibble mask rather than a 16-bit bitmask; the C++ call sites keep their existing nibble-mask arithmetic and only swap the inline NEON load/compare for the assembly call. The childMaxVersion compares stay in C++ NEON intrinsics, matching x86-64's compare16: those slots are always initialized to zero by the allocator, so the wide loads are defined. The assembly functions carry `bti c` landing pads and the same aeabi_feature_and_bits attributes the compiler emits for -mbranch-protection=standard, so the object stays BTI/PAC/GCS-compatible (and warning-free under -z force-bti). CMakeLists.txt builds simd_aarch64.S into the object library and the SIMD test/bench/fuzz targets on aarch64. Closes #68	2026-08-02 23:48:28 -04:00
weaselbot	6b1f597d77	Fix ARM NEON scan helpers truncating 64-bit versions ... When USE_64_BIT=1, InternalVersionT stores an int64_t, but the aarch64 NEON fast paths in scan16 (both the indexed Node48 variant and the Node256 variant) and checkMaxBetweenExclusiveImpl(Node16) only copied the low 32 bits of each version into uint32x4_t lanes and compared against a truncated 32-bit readVersion. This produced wrong conflict/commit decisions once any version exceeded 2^32 - 1. Extract the per-version "greater than readVersion" computation into a shared conflictMask16 helper. For 64-bit versions it uses vcgtq_s64 on the full int64 values and narrows the resulting 16-byte mask into the same nibble-packed layout the callers already consume. The 32-bit path is preserved unchanged. Closes #69	2026-08-02 23:35:32 -04:00
weaselbot	70630649d9	ci: run MSan on arm64 ... Add a debug-arm64 matrix entry to the test job that runs the MSan fuzz tests on an arm64 runner. The arm instrumented libc++ toolchain (22.1.8) is built against LLVM 22, so this entry installs clang-22 from apt.llvm.org while the existing amd64 entries keep clang-21. Generalize the test job matrix with runner/arch/llvm_version/msan_url fields so the runner, apt cache key, LLVM toolchain version, and MSan toolchain download URL are selected per matrix entry. Closes #73	2026-08-02 23:28:40 -04:00
weaselbot	0b12a037c4	Correct rationale in simd_x86_64.S comment ... The SIMD operations are written in assembly because loading and operating on indeterminate values is UB in C++ but well-defined in assembly. msan not tracking the loads is a side effect, not the reason. Closes #71	2026-08-03 02:37:18 +00:00
andrew	79113ecb88	Run valgrind in arm64 release in CI	2026-08-03 02:36:45 +00:00
andrew	5c16b8ee90	Add .note.gnu.property section for CET/CFI to simd_x86_64.S ... The assembly file was missing the GNU property note that records control-flow integrity (CET) support, causing hardening-check to report 'Control flow integrity: no, not found!'. Add the note matching what clang emits with -fcf-protection.	2026-08-02 22:31:56 -04:00