From d3e0001c14320b90af0704f812fa226d80941c68 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 29 Oct 2026 08:37:58 +0530 Subject: [PATCH] test: explore and replay bounded storage schedules (#760) --- .github/workflows/deterministic-schedules.yml | 137 ++++++++++++ CHANGELOG.md | 1 + CLAUDE.md | 2 + Cargo.toml | 6 +- README.md | 2 + ROADMAP.md | 1 + docs/TEST_COVERAGE.md | 2 + docs/testing/deterministic-schedules.md | 203 ++++++++++++++++++ docs/testing/dst-ci-validation.json | 8 + docs/testing/dst-results.json | 78 +++++++ src/graph/storage.rs | 20 +- src/graph/storage/deterministic.rs | 203 ++++++++++++++++++ src/storage/pins.rs | 6 +- tests/dst-mutations/check.py | 99 +++++++++ .../dst-mutations/live-snapshot-cutoff.patch | 7 + tests/dst-mutations/per-fact-commit.patch | 18 ++ tests/dst-mutations/split-publication.patch | 7 + 17 files changed, 795 insertions(+), 5 deletions(-) create mode 100644 .github/workflows/deterministic-schedules.yml create mode 100644 docs/testing/deterministic-schedules.md create mode 100644 docs/testing/dst-ci-validation.json create mode 100644 docs/testing/dst-results.json create mode 100644 src/graph/storage/deterministic.rs create mode 100644 tests/dst-mutations/check.py create mode 100644 tests/dst-mutations/live-snapshot-cutoff.patch create mode 100644 tests/dst-mutations/per-fact-commit.patch create mode 100644 tests/dst-mutations/split-publication.patch diff --git a/.github/workflows/deterministic-schedules.yml b/.github/workflows/deterministic-schedules.yml new file mode 100644 index 000000000..093d6ba18 --- /dev/null +++ b/.github/workflows/deterministic-schedules.yml @@ -0,0 +1,137 @@ +name: Deterministic storage schedules + +# #760: only the storage/snapshot/pin boundary is instrumented. Keep this +# file identical on main and v3: schedules run from the default branch but +# explicitly check out v3. Merge the main companion after the suite lands. +# At the v3 release cut, update the scheduled/dispatch default ref to main. +on: + pull_request: + branches: ["v3"] + paths: + - "src/graph/**" + - "src/storage/**" + - "src/db.rs" + - "src/lib.rs" + - "src/error.rs" + - "src/temporal.rs" + - "Cargo.toml" + - "tests/dst-mutations/**" + - ".github/workflows/deterministic-schedules.yml" + schedule: + - cron: "23 19 * * *" + workflow_dispatch: + inputs: + ref: + description: Branch or commit containing the storage schedule suite + required: true + default: v3 + +permissions: + contents: read + +concurrency: + group: dst-${{ github.event_name }}-${{ github.ref }} + cancel-in-progress: ${{ github.event_name == 'pull_request' }} + +jobs: + schedules: + name: Schedules (${{ matrix.os }}, Rust ${{ matrix.toolchain }}) + runs-on: ${{ matrix.os }} + timeout-minutes: 30 + strategy: + fail-fast: false + matrix: + include: + - os: ubuntu-latest + toolchain: stable + - os: macos-latest + toolchain: stable + - os: windows-latest + toolchain: stable + - os: ubuntu-latest + toolchain: "1.89.0" + defaults: + run: + shell: bash + env: + RUSTFLAGS: --cfg minigraf_shuttle + CARGO_TERM_COLOR: never + CARGO_RESOLVER_INCOMPATIBLE_RUST_VERSIONS: fallback + MINIGRAF_DST_ITERATIONS: ${{ github.event_name == 'pull_request' && '1000' || '10000' }} + DST_SEEDS: ${{ github.event_name == 'pull_request' && '760' || '760 761 762' }} + DST_TOOLCHAIN: ${{ matrix.toolchain }} + + steps: + - uses: actions/checkout@v4 + if: github.event_name == 'pull_request' + + - uses: actions/checkout@v4 + if: github.event_name != 'pull_request' + with: + ref: ${{ github.event_name == 'workflow_dispatch' && inputs.ref || 'v3' }} + + - uses: dtolnay/rust-toolchain@master + with: + toolchain: ${{ matrix.toolchain }} + + - name: Record replay environment + run: | + mkdir -p dst-artifacts + git rev-parse HEAD > dst-artifacts/revision.txt + git archive --format=tar.gz --output=dst-artifacts/source.tar.gz HEAD + rustc -Vv > dst-artifacts/environment.txt + cargo -V >> dst-artifacts/environment.txt + printf 'RUSTFLAGS=%s\nMINIGRAF_DST_ITERATIONS=%s\nDST_SEEDS=%s\n' \ + "$RUSTFLAGS" "$MINIGRAF_DST_ITERATIONS" "$DST_SEEDS" >> dst-artifacts/environment.txt + if [ "$DST_TOOLCHAIN" != stable ]; then + declared=$(sed -n 's/^rust-version = "\(.*\)"$/\1/p' Cargo.toml) + test "$DST_TOOLCHAIN" = "$declared.0" + fi + + - name: Resolve compatible dependencies + run: | + cargo generate-lockfile 2>&1 | tee dst-artifacts/resolve.log + cp Cargo.lock dst-artifacts/Cargo.lock + + - uses: Swatinem/rust-cache@v2 + with: + key: dst-${{ matrix.toolchain }} + + - name: Explore bounded schedules + run: | + # Fail if the cfg/filter ever silently selects zero or fewer tests. + cargo test --locked --lib graph::storage::deterministic:: -- --list \ + 2>&1 | tee dst-artifacts/tests.log + count=$(grep -c '^graph::storage::deterministic::.*: test$' dst-artifacts/tests.log) + test "$count" -eq 3 + for seed in $DST_SEEDS; do + export MINIGRAF_DST_SEED="$seed" + cargo test --locked --lib graph::storage::deterministic:: \ + -- --nocapture --test-threads=1 2>&1 | tee "dst-artifacts/seed-$seed.log" + completed=$(grep -cF "DST seed=$seed schedules=$MINIGRAF_DST_ITERATIONS" "dst-artifacts/seed-$seed.log") + test "$completed" -eq 3 + done + + - name: Summarize result + if: always() + env: + RESULT: ${{ job.status }} + run: | + { + echo "### Deterministic storage schedules" + echo "- Result: $RESULT" + echo "- Rust: $DST_TOOLCHAIN; seeds: $DST_SEEDS" + echo "- Executions per workload per seed: $MINIGRAF_DST_ITERATIONS" + echo "- Replay artifact: dst-${{ matrix.os }}-${{ matrix.toolchain }}-${{ github.run_attempt }}" + echo '- A test failure prints its schedule and test name in the seed log.' + echo '- Restore source.tar.gz and Cargo.lock; follow docs/testing/deterministic-schedules.md to replay.' + } >> "$GITHUB_STEP_SUMMARY" + + - name: Preserve replay inputs and logs + if: always() + uses: actions/upload-artifact@v4 + with: + name: dst-${{ matrix.os }}-${{ matrix.toolchain }}-${{ github.run_attempt }} + path: dst-artifacts/ + if-no-files-found: warn + retention-days: 14 diff --git a/CHANGELOG.md b/CHANGELOG.md index 2e9f3c143..9e2b38027 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -140,6 +140,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Tests +- **Deterministic storage schedule tests (#760).** Three separately enabled native tests explore transaction append, snapshot cutoffs and checkpoint publication with Shuttle, using the real storage methods and immutable committed-reader fixtures. Deliberate fault patches validate failure detection and schedule replay. Focused PR checks cover Linux, macOS, Windows and Linux MSRV; nightly/manual runs explore more schedules and retain replay inputs. [Findings and reproduction](docs/testing/deterministic-schedules.md) describe the limits; ordinary tests and production builds retain `std` synchronization. - **Format-v8 scalar key decoders are model checked (#693).** Pure inner decoders let Kani prove round trips for signed and unsigned integers, descending transaction counts, valid-to times, floats and six tagged scalar value kinds, plus no panic and bounded cursor consumption on short malformed inputs. The `Reader` still returns the same INT-049 messages and cursor positions; a test-only copy of its old code checks those against exhaustive 0–2 byte and seeded longer inputs. Strings, sets, packed pages and WAL retain fuzz and property coverage. No key bytes or file format change. - **Statement bases and large write transactions (#550).** A `WriteTransaction` whose statements repeat, change, retract and re-assert each other's facts across chunks gives every statement the same outcome, and stores the same records, at chunk sizes 1 to 4 as with one chunk; queries after each statement return what a commit of the statements so far would hold; failed and rolled-back statements and transactions leave the file passing `verify`. The fault matrix covers a large `WriteTransaction` at every write and sync, and with `test-hooks` the crash-kill test runs every third transaction of its large variant as one. - **Golden-file compatibility corpus (#391).** `tests/golden/` holds v7 files written by minigraf 2.0.3, each with a JSON manifest of its CRC32, `tx_count` and expected query results. They cover one checkpoint, several checkpoints, indexes rebuilt on open, a WAL left by a crash, a WAL whose entries were already checkpointed, and same-transaction multi-values (#371). `tests/golden_corpus_test.rs` opens a copy of each file and checks its manifest after open, after a checkpoint and reopen, and after one more write. Golden files are never regenerated, only added; a new `golden-corpus` job in `policy.yml` fails a pull request that changes one. The generator is a standalone crate pinned to `minigraf = "=2.0.3"` (`tests/golden/gen/v7/`). On `v3`, each v7 file must also carry a v8 meta page after its first open, and seven v8 files are frozen alongside them, written by the `v3` branch at `23aa57c` (`tests/golden/gen/v8/`): one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values (a 4,068-byte string stored twice, the 64/65-byte inline boundary, a 1,000-byte attribute and keyword). All #371 queries now pass. diff --git a/CLAUDE.md b/CLAUDE.md index 26962e645..614c69ec3 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -221,6 +221,8 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are **2000 tests** (1983 passing, 17 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. +The #760 deterministic storage suite adds three native unit tests in a separate `--cfg minigraf_shuttle` build, outside the default count. Run only `graph::storage::deterministic::` with that cfg; ordinary unit tests do not enter its scheduler. `deterministic-schedules.yml` runs relevant v3 PRs on Linux/macOS/Windows plus Linux MSRV, and larger nightly/manual searches with replay artifacts. The identical main workflow activates the v3 schedule after both PRs merge. See `docs/testing/deterministic-schedules.md` for scope, controls and findings. + **Testing conventions** — see the Testing Conventions section below before writing any tests. ## Current Maintainer Context diff --git a/Cargo.toml b/Cargo.toml index ca540a6f1..91f8cc639 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -63,6 +63,10 @@ pest = "2" pest_derive = "2" pest_meta = "2" +[target.'cfg(all(minigraf_shuttle, not(target_arch = "wasm32")))'.dev-dependencies] +# #760 bounded prototype; used only with --cfg minigraf_shuttle in unit tests. +shuttle = "=0.9.8" + [target.'cfg(not(target_arch = "wasm32"))'.dev-dependencies] tempfile = "3" criterion = { version = "0.8", features = ["html_reports"] } @@ -136,7 +140,7 @@ workspace = true [workspace.lints.rust] # Kani proof harnesses (#627): `cargo kani` sets cfg(kani). -unexpected_cfgs = { level = "warn", check-cfg = ['cfg(kani)'] } +unexpected_cfgs = { level = "warn", check-cfg = ['cfg(kani)', 'cfg(minigraf_shuttle)'] } [workspace.lints.clippy] # Panic prevention — use Result/? or debug_assert! instead diff --git a/README.md b/README.md index e568a494f..de9b0a3f4 100644 --- a/README.md +++ b/README.md @@ -289,6 +289,8 @@ This is a solo-maintained project with a long-term vision. Read [PHILOSOPHY.md]( See [CONTRIBUTING.md](CONTRIBUTING.md) for development setup, code standards, and the PR process. +The [deterministic storage schedule suite](docs/testing/deterministic-schedules.md) (#760) documents the native/MSRV CI checks, replay commands and coverage limits. + ## License Licensed under either of: diff --git a/ROADMAP.md b/ROADMAP.md index 4de8d89c5..b4ff5dc0b 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -114,6 +114,7 @@ Scope — features: Scope — release-gate testing and documentation: +- Deterministic storage schedules (#760; v3.0.0): [suite and findings](docs/testing/deterministic-schedules.md) cover batch visibility, snapshot cutoffs and checkpoint publication. Focused native/MSRV PR checks and larger nightly/manual searches retain replay artifacts; the workflow-only main companion enables the v3 nightly schedule. Whole-database simulation remains out of scope. - Golden-file compatibility corpus for every format version (#391; done on `v3`: six v7 files from 2.0.3 checked after migration, seven v8 files frozen at `23aa57c`) - SIGKILL crash test that checks committed data through EAVT, AEVT and full scan (#384; done on `v3`: `tests/crash_kill_test.rs`, 100 rounds per OS nightly) - Model-based test of transact/retract/checkpoint/reopen (#385; done on `v3`: `tests/model_based_test.rs`, 30,000 cases nightly) diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index f28c03761..1baeebc17 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -24,6 +24,8 @@ Not counted above: the browser tests and the WASI run (see [Browser and WASI](#browser-and-wasi)). +Also outside those counts: three native unit tests in the separate #760 `minigraf_shuttle` build. The [bounded suite and findings](testing/deterministic-schedules.md) record 90,000 passing schedule executions and three deliberately injected faults, each replayed 10/10 times. The suite checks real storage synchronization with immutable committed-reader fixtures; it does not simulate file durability. `deterministic-schedules.yml` runs relevant v3 PRs on three native OSes plus Linux MSRV, with larger nightly/manual searches and replay artifacts. Default-feature test counts are unchanged. + **Scope**: the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. Otherwise the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Tests merged from the v2.x line are marked *(v2.x)*. ## Covered Areas diff --git a/docs/testing/deterministic-schedules.md b/docs/testing/deterministic-schedules.md new file mode 100644 index 000000000..3bee890e1 --- /dev/null +++ b/docs/testing/deterministic-schedules.md @@ -0,0 +1,203 @@ +# Deterministic storage schedule tests (#760) + +Investigation on `v3`, based on `9117392e9` (2026-10-29), for the v3.0.0 +release gate in #383. The bounded prototype is adopted as a native CI suite. +It adds no database configuration and does not prove concurrency correct. + +## Boundary audit + +| Boundary | Current synchronization | What this prototype checks | +|---|---|---| +| Transaction append / snapshot | `FactStorage::load_facts` holds the pending write lock for the whole batch; `snapshot` reads its length under the same lock | A reader observes zero or two facts from a two-fact transaction, never one (#554) | +| Separate scans of one snapshot | `Snapshot` retains one pending store and cutoff | Reads of `:pair/x` and `:pair/y` agree even if another pair is appended between scans (#555-like failure) | +| Checkpoint publication / reader / append | `FactData` write lock publishes the committed reader, generation and replacement pending store together; appends hold its read lock | No mixed generation, duplicate or missing fact; a late append survives; an old reader and a concurrently captured reader stay stable | +| Snapshot lifetime / page reuse | `Pins` mutex maintains generation pins and quarantine; snapshot capture and publication hold `FactData` while taking/recording pins | A page remains quarantined while an old snapshot exists and is released after its last snapshot drops | +| Rule registration / query planning | `execute_rule` holds the registry write lock through registration and stratification; `open_rule_query` holds its read lock through rewriting/planning | Audited only; the registry is not instrumented by this prototype | + +The facade serializes writes with `Inner::write_lock`. The storage-level late +append scenario also checks the explicitly supported `publish` tail-copy +contract, even though the facade currently prevents that overlap. Reopen has +no shared in-process snapshot and remains covered by recovery tests. + +## Instrumented suite + +`src/graph/storage/deterministic.rs` runs three small workloads against the +**real** `FactStorage`, `Snapshot` and `Pins` implementations. Only their locks +and transaction-counter atomic are substituted. The checkpoint reader is an +immutable list of facts: disk pages, WAL and the allocator are outside this +experiment. A yield in the batch's input iterator exposes the per-fact gap in +the negative control; in the correct code the batch lock spans that yield. + +The substitutions require **all** of `cfg(test)`, `cfg(minigraf_shuttle)` and a +native target. Shuttle 0.9.8 is a conditional, native dev dependency. Ordinary +tests, production builds and WASM use `std`; no public API, file format or +production algorithm changes. `std::sync::Arc` remains the ownership primitive; +the instrumented locks schedule access to the shared contents. Other modules' +locks are not instrumented: do not extend these workloads to the full facade +without auditing them for blocking outside Shuttle. + +Facts use fixed ids and timestamps. Although `snapshot()` captures the wall +clock, these tests do not use it in their assertions or scheduling decisions. +Hash iteration does not select operations: comparisons use ordered results. +Each search has a fixed seed and iteration budget, plus a 10,000-step failure +bound per execution. Passing a randomized search does not establish complete +schedule coverage, weak-memory correctness, fairness or absence of starvation. + +## Reproduction + +Use the designated test machine for these commands. Use the debug test profile; +the project's release profile aborts on panic. + +```bash +RUSTFLAGS='--cfg minigraf_shuttle' cargo test --lib \ + graph::storage::deterministic:: -- --nocapture + +MINIGRAF_DST_ITERATIONS=10000 MINIGRAF_DST_SEED=761 \ + RUSTFLAGS='--cfg minigraf_shuttle' cargo test --locked --lib \ + graph::storage::deterministic:: -- --nocapture +``` + +Default: 1,000 executions **per workload**, seed 760. Do not run the ordinary +unit suite with this cfg: those tests are not wrapped in a Shuttle runtime. +Retain the generated `Cargo.lock`, exact source and compiler version with a +failure; the root lockfile is intentionally untracked in this repository. +Schedule encodings are tied to the instrumented program and dependency versions. + +Shuttle prints a `failing schedule`. Replay it with the exact test selected: + +```bash +MINIGRAF_DST_REPLAY='' RUSTFLAGS='--cfg minigraf_shuttle' \ + cargo test --locked --lib \ + graph::storage::deterministic::batch_append_is_atomic -- --exact --nocapture +``` + +`tests/dst-mutations/*.patch` are three **deliberate faults**, never changes to +ship. In a disposable checkout, after the first command generates a lockfile: + +```bash +python3 tests/dst-mutations/check.py > dst-controls.json +``` + +The script applies each patch separately, requires the expected assertion +failure, replays its saved schedule ten times, restores the original source +in `finally`, then rebuilds and runs all three correct workloads. Keep its +stderr if a check fails. This is a harness validation experiment, not part of +the normal test suite. Do not interrupt it with SIGKILL or edit its source file +concurrently; use a disposable checkout so a process kill cannot affect work. + +## Alternatives and compatibility + +| Technique | Fit and cost for Minigraf | +|---|---| +| Shuttle | The prototype instruments the two storage modules with a small import change. Randomized schedule search and saved-schedule replay suit these bounded lock-based invariants. It does not control unmodified `std` locks, external I/O or SIGKILL recovery. [Primary documentation](https://docs.rs/shuttle/0.9.8/shuttle/) | +| Loom | Requires synchronization substitutions too; offers memory-model exploration valuable for future lock-free/relaxed-atomic code. Full-engine models would add state-space and maintenance cost. Not prototyped or timed here. [Primary documentation](https://docs.rs/loom/0.7.2/loom/) | +| Explicit channels/barriers | Works with real OS threads, `std` locks and file I/O, without another dependency. Good for a specific known interleaving, but requires hooks placed at the dangerous internal boundaries and a deadlock-safe protocol. It does not automatically explore other schedules. No second implementation was built here. | +| ffs | Traces unmodified native threads, so it could cover more of the facade. Its documented Linux/x86-64, ptrace/perf-counter requirements and external-side-effect replay obligations make it a separate platform-specific experiment. Not run here. [Primary repository](https://github.com/aoli-al/ffs) | + +WASM is excluded from the instrumented suite; its production imports remain +unchanged. The initial prototype was measured on Linux x86-64. The CI matrix +also runs macOS and Windows; its PR checks provide the native-platform evidence. File-backed real-OS concurrency tests, fault injection, +model-based reopen tests and the SIGKILL suite must remain. The immutable reader +cannot establish filesystem ordering, torn-write handling, durable commit or +correct page reclamation by the actual allocator. #558's page-overwrite defect +was v2.x-only and is not claimed to exist on v3. + +## Measurements and recommendation + +On the designated bench machine (Linux x86-64, Rust 1.99.1), all three deliberate +faults were detected with seed 760 and a budget of 1,000 executions. Each saved +schedule reproduced the intended assertion failure **10/10 times**: + +| Deliberate mutation | Saved failing schedule | +|---|---| +| Per-fact locking in `load_facts` (#554-style) | `9101149fd8bda2a2a0cbf6e901a0288aa202` | +| Live pending length instead of the captured snapshot cutoff (#555-like) | `910115b9befafab08ae7c8f301000020282800` | +| Release/reacquire the publication lock between reader and pending replacement | `91022bf8050000000000001228499208112400400200` | + +These were mutations of current v3 source, not runs of the original historical +commits. The ordinary stress tests can also catch these classes of fault; this +experiment demonstrates saved-schedule replay and small-workload detection, +not a measured improvement in bug-finding rate over those tests. + +After restoration, 3,000 executions passed. Extended searches then passed +10,000 executions per workload for each of seeds 760, 761 and 762: +**90,000 executions, no failures**. These are execution counts, not counts of +distinct schedules or a completeness bound. No new Minigraf defect was found. + +Five idle-machine runs, pinned to one NUMA node, ran the three workloads +sequentially in the debug test executable. Each ran 1,000 schedules per workload: +**1.0531–1.0848 seconds**, median **1.0638 seconds**, excluding compilation. +The 30,000-execution runs took 10.1808, 10.2648 and 10.1196 seconds for seeds +760, 761 and 762 respectively. These are local test-cost estimates, not hosted-CI +timings or database performance measurements. An instrumented build has its +own Cargo artifacts and incurs compilation of Shuttle and its transitive dev +dependencies; the runtime numbers exclude that cost. + +Verification on the same source: 1,156 ordinary library unit tests passed +(five ignored), all eight real-thread snapshot tests passed, the repository's +`cargo clippy --all-features -- -D warnings` command passed, and library compile +checks passed for browser WASM (`--features browser`) and WASI. Formatting and +patch whitespace checks passed. The repository's dependency-policy command +(`cargo deny check advisories bans licenses sources`) passed. `cargo tree -e +normal` contains no Shuttle dependency. The complete integration/doc suite was +not rerun for this prototype. + +An additional `cargo clippy --lib --tests -- -D warnings` run with the +instrumentation cfg failed on existing test-code lints (including integration +test unwraps and existing unit-test sort/cast/style warnings). It produced no +diagnostic in `deterministic.rs`. That broader command is not the repository's +CI lint gate; its pre-existing findings were left unchanged. + +Replay environment: Shuttle 0.9.8, shuttle-engine 0.1.7, shuttle-std 0.1.5, +shuttle-schedulers 0.1.1. The retained local root lockfile has SHA-256 +`08a1495662974810709834e9a3530faa0f1f63656020f868767a75bc20fd625f`. +For a fresh resolution, the mutation script regenerates and validates schedules +instead of assuming that the strings above remain valid forever. + +## CI adoption + +`.github/workflows/deterministic-schedules.yml` runs the three workloads on +Linux, macOS and Windows with stable Rust, and on Linux with Rust 1.89.0. +Relevant PRs targeting `v3` run 1,000 executions per workload with seed 760. +Nightly (19:23 UTC) and manual runs check out `v3` by default and run 10,000 +executions per workload for seeds 760, 761 and 762. A manual run can select +another source ref. Each job is capped at 30 minutes, and the per-execution +step bound remains 10,000. The workflow fails if the filter selects anything +other than three tests or if any workload fails to finish its requested budget. + +The identical workflow needs to land on `main` as a separate companion PR +**after** the suite lands on `v3`: GitHub executes schedules only from the +default branch. The companion adds no test implementation to v2.x. At the +v3 release cut, change the workflow's PR target and scheduled/manual default +source ref to `main`. This job does not change branch-protection settings. + +Every job uploads a `dst---` artifact for 14 days, +even on test failure. It contains seed logs (including the failing test and +Shuttle schedule), the resolved `Cargo.lock`, compiler/Cargo versions, +configuration, source revision and a tracked-source archive. To replay: + +1. Extract `source.tar.gz` into an empty directory and copy the artifact's + `Cargo.lock` into that directory. +2. Select the recorded Rust version and native target; take the failing test + name and schedule from `seed-*.log`. +3. Use the `MINIGRAF_DST_REPLAY` command above with `--locked` and `--exact`. + +Do not substitute the current branch tip or resolve fresh dependencies when +replaying an archived failure. Archive the artifact elsewhere if it must be +kept beyond retention. No credentials or runner environment dump are collected. +The deliberate-fault script remains a manual harness-validation tool, not a +scheduled failing job. The seed log pipeline preserves Cargo's failure status. + +The actual workflow exploration block was validated on the bench under Rust +1.89.0, including PR/nightly budgets, rejection of a build selecting zero tests, +and propagation/logging of the injected partial-transaction failure. See the +PR's native matrix for hosted-runner results. Source and runtime behavior are +unchanged from the measured prototype; CI configuration and documentation are +the adoption changes. + +This costs two small synchronization import substitutions and three bounded +workloads. The maintenance cost is keeping those substitutions aligned with +the real lock graph and keeping fixtures representative. New shared-state +paths need an explicit audit before inclusion. Full-engine simulation, +filesystem simulation and a general-purpose hook layer remain deferred; the +present evidence does not justify making them v3 release dependencies. diff --git a/docs/testing/dst-ci-validation.json b/docs/testing/dst-ci-validation.json new file mode 100644 index 000000000..b3f358912 --- /dev/null +++ b/docs/testing/dst-ci-validation.json @@ -0,0 +1,8 @@ +{ + "toolchain": "Rust 1.89.0", + "platform": "Linux x86-64", + "pr_mode": "passed, 3 workloads x 1000 executions", + "zero_test_guard": "rejected a real non-instrumented build with zero selected tests", + "failure_propagation": "returned 101 through tee and retained schedule + test name in seed log", + "nightly_mode": "passed, 3 workloads x 10000 executions x 3 seeds" +} diff --git a/docs/testing/dst-results.json b/docs/testing/dst-results.json new file mode 100644 index 000000000..d917fbf1d --- /dev/null +++ b/docs/testing/dst-results.json @@ -0,0 +1,78 @@ +{ + "base_commit": "9117392e9d1779e935307c05957cc4472cc6389a", + "platform": "Linux x86-64", + "rustc": "1.99.1", + "shuttle": "0.9.8", + "lockfile_sha256": "08a1495662974810709834e9a3530faa0f1f63656020f868767a75bc20fd625f", + "negative_controls": [ + { + "mutation": "per-fact-commit", + "test": "batch_append_is_atomic", + "seed": 760, + "schedule": "9101149fd8bda2a2a0cbf6e901a0288aa202", + "reproduced": 10, + "attempts": 10 + }, + { + "mutation": "live-snapshot-cutoff", + "test": "one_snapshot_keeps_its_cutoff_across_scans", + "seed": 760, + "schedule": "910115b9befafab08ae7c8f301000020282800", + "reproduced": 10, + "attempts": 10 + }, + { + "mutation": "split-publication", + "test": "checkpoint_publication_preserves_readers_and_late_appends", + "seed": 760, + "schedule": "91022bf8050000000000001228499208112400400200", + "reproduced": 10, + "attempts": 10 + } + ], + "restored_schedules": 3000, + "warm_runs": [ + { + "seed": 760, + "schedules_per_workload": 1000, + "seconds": 1.0598 + }, + { + "seed": 760, + "schedules_per_workload": 1000, + "seconds": 1.0848 + }, + { + "seed": 760, + "schedules_per_workload": 1000, + "seconds": 1.0531 + }, + { + "seed": 760, + "schedules_per_workload": 1000, + "seconds": 1.0764 + }, + { + "seed": 760, + "schedules_per_workload": 1000, + "seconds": 1.0638 + } + ], + "extended_runs": [ + { + "seed": 760, + "schedules_per_workload": 10000, + "seconds": 10.1808 + }, + { + "seed": 761, + "schedules_per_workload": 10000, + "seconds": 10.2648 + }, + { + "seed": 762, + "schedules_per_workload": 10000, + "seconds": 10.1196 + } + ] +} diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 2ca3407cc..b4ee9e020 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -9,8 +9,22 @@ use crate::storage::index::{Indexes, encode_value}; use crate::storage::pins::{GenerationPin, Pins}; use anyhow::Result; use std::collections::HashSet; -use std::sync::atomic::{AtomicU64, Ordering}; -use std::sync::{Arc, RwLock}; +use std::sync::Arc; +// Only this bounded unit-test build uses a controlled scheduler (#760). +// Normal builds, integration tests and WASM retain std synchronization. +#[cfg(all(test, minigraf_shuttle, not(target_arch = "wasm32")))] +use shuttle::sync::{ + RwLock, RwLockReadGuard, + atomic::{AtomicU64, Ordering}, +}; +#[cfg(not(all(test, minigraf_shuttle, not(target_arch = "wasm32"))))] +use std::sync::{ + RwLock, RwLockReadGuard, + atomic::{AtomicU64, Ordering}, +}; + +#[cfg(all(test, minigraf_shuttle, not(target_arch = "wasm32")))] +mod deterministic; /// Compact key for O(1) duplicate detection in `PendingStore::keys`. /// @@ -429,7 +443,7 @@ impl Snapshot { self.now } - fn read_pending(&self) -> Result> { + fn read_pending(&self) -> Result> { self.pending .read() .map_err(|_| err_coded!(ErrorCode::Int050, "pending")) diff --git a/src/graph/storage/deterministic.rs b/src/graph/storage/deterministic.rs new file mode 100644 index 000000000..0d434de8d --- /dev/null +++ b/src/graph/storage/deterministic.rs @@ -0,0 +1,203 @@ +//! Bounded schedule exploration of the real storage methods (#760). +//! Compiled only in the native, instrumented unit-test build. See +//! docs/testing/deterministic-schedules.md for commands and limitations. + +use super::*; +use crate::storage::{CommittedReader, Scan}; +use shuttle::{Config, MaxSteps, Runner, scheduler::RandomScheduler, thread}; + +fn check(workload: fn()) { + if let Ok(schedule) = std::env::var("MINIGRAF_DST_REPLAY") { + shuttle::replay(workload, &schedule); + return; + } + let iterations = std::env::var("MINIGRAF_DST_ITERATIONS") + .map(|s| s.parse::().expect("positive iteration count")) + .unwrap_or(1_000); + assert!(iterations > 0, "must explore at least one schedule"); + let seed = std::env::var("MINIGRAF_DST_SEED") + .map(|s| s.parse::().expect("integer seed")) + .unwrap_or(760); + let mut config = Config::default(); + config.max_steps = MaxSteps::FailAfter(10_000); + let explored = + Runner::new(RandomScheduler::new_from_seed(seed, iterations), config).run(workload); + assert_eq!(explored, iterations, "all requested schedules ran"); + eprintln!("DST seed={seed} schedules={explored}"); +} + +// Fixed timestamps and ids: the wall clock captured by snapshot() is not +// consulted by these assertions. No UUID generation, file I/O or OS threads. +fn pair(n: u64) -> Vec { + [":pair/x", ":pair/y"] + .into_iter() + .map(|a| { + Fact::with_valid_time( + uuid::Uuid::from_u128(u128::from(n)), + a.into(), + Value::Integer(1), + n, + n, + 0, + VALID_TIME_FOREVER, + ) + }) + .collect() +} + +fn ids(facts: Vec) -> Vec<(u128, String)> { + let mut ids: Vec<_> = facts + .into_iter() + .map(|f| (f.entity.as_u128(), f.attribute)) + .collect(); + ids.sort(); + ids +} + +fn whole_pairs(facts: Vec, counts: &[usize]) { + assert!( + counts.contains(&facts.len()), + "partial or duplicated transaction" + ); + let xs: Vec<_> = facts + .iter() + .filter(|f| f.attribute == ":pair/x") + .map(|f| f.entity) + .collect(); + let ys: Vec<_> = facts + .iter() + .filter(|f| f.attribute == ":pair/y") + .map(|f| f.entity) + .collect(); + assert!(xs == ys, "attributes came from different transactions"); +} + +#[test] +fn batch_append_is_atomic() { + check(|| { + let storage = FactStorage::new(); + let writer = storage.clone(); + let writer = thread::spawn(move || { + // Yield between facts while load_facts holds its batch lock. + // Replacing it with per-fact locking must make this test fail. + writer + .load_facts(pair(1).into_iter().inspect(|_| thread::yield_now())) + .unwrap(); + }); + let snap = storage.snapshot().unwrap(); + whole_pairs(snap.all_facts().unwrap(), &[0, 2]); + writer.join().unwrap(); + whole_pairs(storage.snapshot().unwrap().all_facts().unwrap(), &[2]); + }); +} + +#[test] +fn one_snapshot_keeps_its_cutoff_across_scans() { + check(|| { + let storage = FactStorage::new(); + storage.load_facts(pair(1)).unwrap(); + let writer = storage.clone(); + let writer = thread::spawn(move || { + writer.load_facts(pair(2)).unwrap(); + }); + let snap = storage.snapshot().unwrap(); + let xs = snap + .live_facts_of_scans(&[Scan::Attribute(":pair/x")], None) + .unwrap(); + thread::yield_now(); + let ys = snap + .live_facts_of_scans(&[Scan::Attribute(":pair/y")], None) + .unwrap(); + let mut x_ids: Vec<_> = xs.iter().map(|f| f.entity).collect(); + let mut y_ids: Vec<_> = ys.iter().map(|f| f.entity).collect(); + x_ids.sort(); + y_ids.sort(); + assert!(x_ids == y_ids, "one snapshot saw two database states"); + writer.join().unwrap(); + assert_eq!( + snap.all_facts().unwrap().len(), + xs.len() * 2, + "snapshot grew after capture" + ); + }); +} + +// Immutable committed facts isolate publication from page I/O. This is not +// a model of checkpoint durability, B+tree traversal or the page allocator. +struct Reader(Vec); + +impl CommittedReader for Reader { + fn all_facts(&self) -> Result> { + Ok(self.0.clone()) + } + fn facts_for_entity(&self, e: &EntityId) -> Result> { + Ok(self.0.iter().filter(|f| f.entity == *e).cloned().collect()) + } + fn facts_for_entity_attribute(&self, e: &EntityId, a: &str) -> Result> { + Ok(self + .0 + .iter() + .filter(|f| f.entity == *e && f.attribute == a) + .cloned() + .collect()) + } + fn facts_for_attribute(&self, a: &str) -> Result> { + Ok(self + .0 + .iter() + .filter(|f| f.attribute == a) + .cloned() + .collect()) + } +} + +#[test] +fn checkpoint_publication_preserves_readers_and_late_appends() { + check(|| { + let storage = FactStorage::new(); + storage.set_committed(Arc::new(Reader(pair(1))), 1); + storage.load_facts(pair(2)).unwrap(); + let held = storage.snapshot().unwrap(); + let before = ids(held.all_facts().unwrap()); + let checkpoint = storage.clone(); + let checkpoint = thread::spawn(move || { + let committed = [pair(1), pair(2)].concat(); + checkpoint.publish(Arc::new(Reader(committed)), 2, 2, vec![7]); + }); + let writer = storage.clone(); + let writer = thread::spawn(move || { + writer.load_facts(pair(3)).unwrap(); + }); + let snap = storage.snapshot().unwrap(); + let observed = ids(snap.all_facts().unwrap()); + assert!( + observed == before || observed == ids([pair(1), pair(2), pair(3)].concat()), + "publication mixed committed and pending generations" + ); + checkpoint.join().unwrap(); + writer.join().unwrap(); + assert!( + ids(held.all_facts().unwrap()) == before, + "old reader changed" + ); + assert!( + ids(snap.all_facts().unwrap()) == observed, + "concurrent reader changed" + ); + assert!( + storage.pages_in_force().contains(&7), + "old reader lost its page pin" + ); + assert!( + ids(storage.snapshot().unwrap().all_facts().unwrap()) + == ids([pair(1), pair(2), pair(3)].concat()), + "publication lost or duplicated a late append" + ); + drop(held); + drop(snap); + assert!( + storage.pages_in_force().is_empty(), + "last reader did not release its pin" + ); + }); +} diff --git a/src/storage/pins.rs b/src/storage/pins.rs index 7eb69c87a..c0e730519 100644 --- a/src/storage/pins.rs +++ b/src/storage/pins.rs @@ -15,8 +15,12 @@ //! under `FactData`'s lock, so a pin is always on the active generation and an //! entry is never dropped before a pin that needs it exists. +#[cfg(all(test, minigraf_shuttle, not(target_arch = "wasm32")))] +use shuttle::sync::{Mutex, MutexGuard}; use std::collections::{BTreeMap, HashSet}; -use std::sync::{Arc, Mutex, MutexGuard}; +use std::sync::Arc; +#[cfg(not(all(test, minigraf_shuttle, not(target_arch = "wasm32"))))] +use std::sync::{Mutex, MutexGuard}; #[derive(Default)] struct State { diff --git a/tests/dst-mutations/check.py b/tests/dst-mutations/check.py new file mode 100644 index 000000000..7b5b1be90 --- /dev/null +++ b/tests/dst-mutations/check.py @@ -0,0 +1,99 @@ +#!/usr/bin/env python3 +"""Validate #760 negative controls in a disposable checkout; restore source. + +Run from anywhere with cargo on PATH. Builds and tests can be expensive. +Writes JSON evidence to stdout; compiler/test diagnostics go to stderr. +""" + +import json +import os +from pathlib import Path +import re +import subprocess +import sys + +ROOT = Path(__file__).resolve().parents[2] +SOURCE = ROOT / "src/graph/storage.rs" +PREFIX = "graph::storage::deterministic::" +CASES = [ + ("per-fact-commit", "batch_append_is_atomic", "partial or duplicated transaction"), + ("live-snapshot-cutoff", "one_snapshot_keeps_its_cutoff_across_scans", + "one snapshot saw two database states|snapshot grew after capture"), + ("split-publication", "checkpoint_publication_preserves_readers_and_late_appends", + "publication mixed committed and pending generations"), +] +ENV = dict(os.environ) +ENV["RUSTFLAGS"] = ENV.get("RUSTFLAGS", "") + " --cfg minigraf_shuttle" +ENV["MINIGRAF_DST_SEED"] = "760" +ENV["MINIGRAF_DST_ITERATIONS"] = "1000" +ENV.pop("MINIGRAF_DST_REPLAY", None) + + +def build(): + result = subprocess.run( + ["cargo", "test", "--locked", "--lib", "--no-run", "--message-format=json"], + cwd=ROOT, env=ENV, text=True, stdout=subprocess.PIPE, check=True, + ) + executables = [] + for line in result.stdout.splitlines(): + item = json.loads(line) + if item.get("reason") == "compiler-message": + print(item["message"].get("rendered", ""), file=sys.stderr) + if item.get("reason") == "compiler-artifact" and item.get("executable"): + if item["target"]["name"] == "minigraf" and "rlib" in item["target"]["kind"]: + executables.append(item["executable"]) + assert len(executables) == 1, "expected one library test executable" + return executables[0] + + +def run(binary, test, schedule=None): + env = dict(ENV) + if schedule is not None: + env["MINIGRAF_DST_REPLAY"] = schedule + return subprocess.run( + [binary, PREFIX + test, "--exact", "--nocapture"], + cwd=ROOT, env=env, text=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, + ) + + +def main(): + original = SOURCE.read_bytes() + evidence = [] + try: + for name, test, expected in CASES: + SOURCE.write_bytes(original) + subprocess.run( + ["patch", "--batch", "--forward", "-p1", "-i", + str(ROOT / "tests/dst-mutations" / (name + ".patch"))], + cwd=ROOT, stdout=sys.stderr, check=True, + ) + binary = build() + result = run(binary, test) + print(result.stdout, file=sys.stderr) + assert result.returncode == 101, "mutant must fail with a test assertion" + assert re.search(expected, result.stdout), "wrong failure reason" + match = re.search(r'failing schedule:\s*"\s*([0-9a-f]+)\s*"', result.stdout) + assert match, "missing replayable schedule" + schedule = match[1] + for _ in range(10): + replay = run(binary, test, schedule) + assert replay.returncode == 101, "replay did not fail" + assert re.search(expected, replay.stdout), "replay failed for another reason" + evidence.append({"mutation": name, "test": test, "seed": 760, + "schedule": schedule, "reproduced": 10, "attempts": 10}) + print(f"{name}: detected, replayed 10/10", file=sys.stderr) + finally: + SOURCE.write_bytes(original) + # Do not leave a mutant executable as the last build. This also checks + # that the unchanged implementation survives the same search budget. + binary = build() + for _, test, _ in CASES: + result = run(binary, test) + print(result.stdout, file=sys.stderr) + assert result.returncode == 0, "restored implementation failed" + assert "schedules=1000" in result.stdout, "search budget was not completed" + print(json.dumps({"negative_controls": evidence, "restored_schedules": 3000}, indent=2)) + + +if __name__ == "__main__": + main() diff --git a/tests/dst-mutations/live-snapshot-cutoff.patch b/tests/dst-mutations/live-snapshot-cutoff.patch new file mode 100644 index 000000000..8492b3fb9 --- /dev/null +++ b/tests/dst-mutations/live-snapshot-cutoff.patch @@ -0,0 +1,7 @@ +--- a/src/graph/storage.rs ++++ b/src/graph/storage.rs +@@ -373,3 +373,3 @@ + p, +- len: self.pending_len.min(p.facts.len()), ++ len: p.facts.len(), + staged: self.staged.as_deref(), diff --git a/tests/dst-mutations/per-fact-commit.patch b/tests/dst-mutations/per-fact-commit.patch new file mode 100644 index 000000000..ac7984b89 --- /dev/null +++ b/tests/dst-mutations/per-fact-commit.patch @@ -0,0 +1,18 @@ +--- a/src/graph/storage.rs ++++ b/src/graph/storage.rs +@@ -835,8 +835,9 @@ + pub(crate) fn load_facts(&self, facts: impl IntoIterator) -> Result { +- self.write_pending(|p| { +- facts.into_iter().fold( +- 0usize, +- |n, fact| if p.push(fact) { n.saturating_add(1) } else { n }, +- ) +- }) ++ let mut count = 0; ++ for fact in facts { ++ if self.load_fact(fact)? { ++ count += 1; ++ } ++ } ++ Ok(count) + } diff --git a/tests/dst-mutations/split-publication.patch b/tests/dst-mutations/split-publication.patch new file mode 100644 index 000000000..6b194e62b --- /dev/null +++ b/tests/dst-mutations/split-publication.patch @@ -0,0 +1,7 @@ +--- a/src/graph/storage.rs ++++ b/src/graph/storage.rs +@@ -1015,2 +1015,4 @@ + d.generation = generation; ++ drop(d); ++ let mut d = self.data.write().unwrap_or_else(|e| e.into_inner()); + d.pending = pending;