29 Commits

This Branch

This Branch

All Branches

Author	SHA1	Message	Date
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
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
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
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
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
weaselbot	e02dd41f74	Address review: drop unused bti c landing pads, fix rationale comment	2026-08-03 09:17:28 -04: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
weaselbot	2231c093df	Fix null pointers passed to memcmp/memcpy in skip_list ... 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	2026-07-13 12:04:22 -04:00
weaselbot	dee3a8f640	Return 0 instead of -1 from hash_table getBytes() ... The hash_table implementation cannot accurately track memory usage and was returning -1 from ConflictSet::getBytes() and ConflictSet_getBytes(). That violates the API contract that getBytes() returns a non-negative byte count. Change both entry points to return 0 and document in ConflictSet.h that implementations which do not track memory usage may return 0. Add a regression test in test_conflict_set.py that loads the hash_table implementation and verifies getBytes() is non-negative. Closes #62	2026-07-07 11:00:52 -04:00
weaselbot	4fcdc5d7e9	Fix RealDataBench subspan and version API contract violations ... - Use subspan count `line.size() - 2` instead of `line.size()` to avoid reading past the line bounds, and guard lines shorter than the two-byte prefix. - Clamp `readVersion` and `setOldestVersion` arguments to `0` so the conflict set never receives negative, non-monotonic versions during the warmup phase. Fixes #58.	2026-06-29 14:01:23 -04:00
weaselbot	63f9a139da	Fix undefined behavior on empty input in strinc() and prefixRange() ... strinc() in ConflictSet.cpp used std::string_view::size() (size_t) and subtracted 1 without first checking for an empty string. For the root node, getSearchPath() returns the empty string, so every debug correctness check underflowed size_t and relied on implementation-defined conversion to signed int. prefixRange() in Bench.cpp had the same loop shape. Although TrivialSpan::size() returns int, on an empty (or all-0xff) key the function then asserted and continued executing, allocating a zero-length buffer and writing before its start. Changes: - In strinc(), initialize index as signed int(str.size()) - 1 so the loop is skipped for empty input, and return ok=false cleanly. - In prefixRange(), initialize index the same way and call std::abort() after the assert so invalid input cannot fall through to an out-of-bounds write. - Replace C-style uint8_t casts with explicit static_casts. Closes #59	2026-06-29 13:52:02 -04:00
weaselbot	971deb477c	Keep Python key buffers alive in WriteRange/ReadRange ... `write()` and `read()` created _Key objects from ephemeral ctypes arrays backed by local bytearray objects. Once the helpers returned, those local variables were freed, leaving the C library with dangling pointers when addWrites()/check() later read the keys. Store the backing bytearray on the returned WriteRange/ReadRange objects as private `_begin_buf` / `_end_buf` attributes. Python keeps them alive for the lifetime of the range object, so the C pointer is always valid. Closes #42	2026-06-22 14:09:18 -04:00
weaselbot	ff0722728a	Include <sys/syscall.h> in ServerBench.cpp for SYS_perf_event_open ... `ServerBench.cpp` calls `syscall(SYS_perf_event_open, ...)` but did not include `<sys/syscall.h>`, relying on `<unistd.h>` to transitively provide the `SYS_*` constants. On toolchains where that does not happen, the build fails with `SYS_perf_event_open` not declared. Add the missing include so `server_bench` compiles on any platform that provides `perf_event_open`. Resolves weaselab/conflict-set#41.	2026-06-22 14:09:14 -04:00
weaselbot	60881419b8	Assert return values in test_update_zero_should_commit / conflict ... Add the missing [Result.COMMIT] / [Result.CONFLICT] assertions so that the two regression tests actually verify the expected conflict-set outcome, not just that the calls do not crash.	2026-06-22 14:09:10 -04:00
weaselbot	4515af3662	CMake: add target-level dependencies for conflict-set-object ... The custom command that links conflict-set.o depends on $<TARGET_OBJECTS:conflict-set-object>, but that generator expression does not create a target-level dependency. With the Unix Makefiles generator, parallel builds can start building the consuming libraries before the object library's build rule is available, producing: gmake[3]: *** No rule to make target 'CMakeFiles/conflict-set-object.dir/ConflictSet.cpp.o', needed by 'conflict-set.o'. Stop. Add add_dependencies() so that conflict-set and conflict-set-static cannot build until conflict-set-object has produced its object files. Closes #47	2026-06-22 14:09:04 -04:00
weaselbot	4dc5f7f75c	Fix self-move-assignment and leak in ConflictSet move-assignment ... The user-declared move-assignment operator overwrote `impl` without first destroying the existing implementation object, leaking all memory and resources owned by the left-hand side. Self-move-assignment also set `impl` to nullptr, leaving the object invalid and leaking the old state. Fix all three implementations (ConflictSet.cpp, SkipList.cpp, HashTable.cpp) to guard against self-assignment and to destroy/free the old `impl` before taking ownership of `other.impl`.	2026-06-22 14:08:59 -04:00
weaselbot	7eaac2a184	Make ConflictSet non-copyable in C++98/C++03 ... `ConflictSet(const ConflictSet&)` and `operator=(const ConflictSet&)` were only deleted for C++11 and later. In C++98/C++03 the compiler implicitly generated public copy operations, so copying a ConflictSet shared the opaque `Impl*` and caused a double-free on destruction. Declare both operations private and leave them undefined when `__cplusplus <= 199711L`, matching the standard pre-C++11 idiom for move-only types. Guard the declarations with `defined(__cplusplus)` so they are not exposed to C90 compilation units. Closes #48	2026-06-22 13:43:04 -04:00
weaselbot	742d920aa1	Set restype=None for void-returning C functions in conflict_set.py ... ConflictSet_check, ConflictSet_addWrites, ConflictSet_setOldestVersion, and ConflictSet_destroy return void in C, but the Python wrapper left their ctypes restype at the default c_int. Set restype = None for each to match the C API contract and avoid undefined behavior from reading the return register of void functions.	2026-06-21 19:25:27 -04:00