From d829bdadfce2c29b8d83931569193dbd0eae4f70 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 13 Oct 2026 20:55:54 +0530 Subject: [PATCH 1/2] feat(storage): generation pins and page quarantine; fact logs no longer defer checkpoints (#543) PR 2 of 3 for #543 (plan steps 2, 3, 4, 6, 7). - src/storage/pins.rs: Pins (generation -> open pins, generation -> ids its checkpoint freed) and the RAII GenerationPin. An entry stays in force while a lower generation is pinned; it is dropped at publish or on release. - PageAllocator::with_quarantine: ids in force are never handed out and are listed again by finish_free_list. - save() and rebuild_indexes() allocate around pages_in_force() and record their freed pages in publish (under FactData's write lock). - FactStorage::snapshot() takes the committed reader, its pin and the pending store with its length under one FactData lock. FactLog reads from it; fact_log() no longer takes the write lock. LogPin, pin_log, log_pins and log_snapshot are gone, and so is the API-013 refusal in save/rebuild and the auto-checkpoint deferral in execute and WriteTransaction::commit. - API-013 deprecated: still registered, no longer emitted. Tests: pins unit tests, allocator quarantine tests, PFS tests that check by page id that saves and rebuilds never write a pinned generation's pages and reuse them after the pin is dropped; fact log tests for checkpoints, rebuilds, auto-checkpoints and concurrent writers with a log open. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- CHANGELOG.md | 2 +- CLAUDE.md | 7 +- ROADMAP.md | 2 +- docs/DURABILITY.md | 4 +- docs/ERROR_REFERENCE.md | 6 +- docs/TEST_COVERAGE.md | 4 +- ...2026-10-11-543-snapshots-and-quarantine.md | 3 + src/db.rs | 32 ++- src/error.rs | 4 + src/fact_log.rs | 51 ++--- src/graph/storage.rs | 112 ++++++----- src/storage/mod.rs | 1 + src/storage/page.rs | 85 +++++++- src/storage/persistent_facts.rs | 155 +++++++++++++-- src/storage/pins.rs | 184 ++++++++++++++++++ tests/fact_log_test.rs | 170 +++++++++++++--- 16 files changed, 667 insertions(+), 155 deletions(-) create mode 100644 src/storage/pins.rs diff --git a/CHANGELOG.md b/CHANGELOG.md index 0add303937..59ff1626a4 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -26,7 +26,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Added - **Binding support for cursors, open options, the fact log and the log writer** (#462, #465, #467). Two new codes let language bindings report what Rust's types rule out: `API-017` (an argument the binding cannot convert, such as an entity id that is not a UUID string), from `MinigrafError::invalid_argument`, and `API-018` (a log writer used after `finish` or `close`), from `MinigrafError::closed`. `BrowserDb.query(datalog)` returns a `BrowserCursor` with `vars()`, `nextBatch(maxRows)` (rows as JSON, as in `execute()`, or `undefined` at the end) and `close()`. The shared binding shape is in `docs/superpowers/specs/2026-10-07-binding-etl-surface-design.md`. The wasm32 test build compiles again (a duplicate `page_cache_capacity` and `tempfile` tests on wasm32). -- **Fact log: `Minigraf::fact_log()`** (#430). Streams every fact version in the database as `FactRecord`s (entity, attribute, value, `tx_count`, `tx_id`, valid-time bounds, and whether it is an assertion or a retraction), without Datalog. `FactFilter` selects attributes (exact or by prefix), entities and a `tx_count` range, checked on index keys so excluded records are never decoded. `FactOrder::Tx` (the default) returns records in ascending `tx_count`; format v8 has no index in transaction order, so it holds at most `FactFilter::window` records (default 262,144) and scans the selected keys once per window. `FactOrder::Storage` reads in one pass. The log reads the database as it was when it opened; while one is open, checkpoints are deferred (writes stay in the WAL, automatic checkpoints wait, and `checkpoint()` or `rebuild_indexes()` with work to do fail with the new `API-013`). Close, drop or finish the log to release it. Like `Cursor`, a `FactLog` is owned and `Send`. Rust API only for now; the bindings follow. +- **Fact log: `Minigraf::fact_log()`** (#430). Streams every fact version in the database as `FactRecord`s (entity, attribute, value, `tx_count`, `tx_id`, valid-time bounds, and whether it is an assertion or a retraction), without Datalog. `FactFilter` selects attributes (exact or by prefix), entities and a `tx_count` range, checked on index keys so excluded records are never decoded. `FactOrder::Tx` (the default) returns records in ascending `tx_count`; format v8 has no index in transaction order, so it holds at most `FactFilter::window` records (default 262,144) and scans the selected keys once per window. `FactOrder::Storage` reads in one pass. The log reads the database as it was when it opened. Writes, checkpoints and `rebuild_indexes()` go on while it is open (#543): the log pins the committed generation it opened on, and no checkpoint reuses a page that generation references, so the file grows by the pages checkpoints replace until the log is closed, dropped or read to the end; later checkpoints reuse them. `API-013` (checkpoint while a fact log is open), added with the fact log in earlier v3.0.0 development builds, is deprecated: no longer emitted, still registered, never reused. Like `Cursor`, a `FactLog` is owned and `Send`. Rust API only for now; the bindings follow. - **Raw log writer: `LogWriter`** (#431). Builds a new database from explicit `FactRecord`s, the load step of an offline migration after `fact_log()` on a read-only source. Each record keeps its `tx_count`, `tx_id`, valid-time window and assertion flag. Records come in transaction order, gaps allowed: leaving a transaction out leaves a hole, and `:as-of` on it shows the state before. `advance_tx_count` keeps the source's counter after trailing purged transactions. The checks are structural only: order (new `API-015`), one `tx_id` per transaction (new `API-016`) and size (`WAL-003`); a rejected record changes nothing. Every file it builds keeps the rules of a normal write (#436, #477): a valid-time window that ends at or before it starts is `API-019`, a second window of one fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction the new `API-020`. An unfiltered copy of a source that keeps these rules is identical to it. A source written before them (v2.x, or earlier v3 builds) can break them, and copying it fails at the first such record, so a middleware step must repair those records first; `docs/ERROR_REFERENCE.md` describes each repair. There is no WAL: records are committed in batches with the normal copy-on-write checkpoint, never splitting a transaction. The file is built at `.partial` and renamed into place by `finish`, so a crash or an abandoned build never leaves part of a log at `path`; an existing target or WAL is the new `STG-043`. The page-range copy the issue proposed is not provided, since v8 pages share one dictionary and are not self-contained. The bindings follow. - **Read-only open: `OpenOptions::read_only`** (#429). Opens a database so that nothing done through the handle writes to the `.graph` file or its WAL. The file is locked in shared mode: any number of read-only handles, in this process or others, can hold it at once, and they exclude a read-write open (and it excludes them) with the existing STG-025/STG-026. The handle shows the same data as a read-write open: a WAL left by an earlier session is applied in memory but not checkpointed or deleted, and a format v7 file is read into memory instead of migrated. A missing file is the new `STG-042` (nothing is created). `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` fail with the new `API-014`; queries, cursors, `fact_log`, `verify` and rule registration work, and dropping the handle does not checkpoint. `page_cache_size` applies as usual, so a tool can keep the whole file resident. Rust API only for now; the bindings follow. - **Cursor API: `Minigraf::query()` and `PreparedQuery::query()`** (#432). Both return a `Cursor` that hands a query's rows back in batches: `vars()`, `next_batch(max_rows) -> Result, _>`, `close()`, and an iterator over rows. The answer is fixed when the cursor opens, so writes that commit while it is open do not change it. A cursor borrows nothing from the database handle: it can outlive it and move to another thread. For now the answer is still computed when the cursor opens, under the same limits as `execute()`; the API is shaped so the engine can later produce rows as they are pulled without breaking callers. `query()` rejects `transact`, `retract` and `rule` with the new `API-012`, and a query with bind slots with `API-010`. `execute()` is unchanged. Rust API only for now; the bindings follow. diff --git a/CLAUDE.md b/CLAUDE.md index ab39b68b01..8c0d7c8f35 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -120,7 +120,8 @@ cargo run < demos/demo_negation.txt - `value_pages.rs`: append-only value pages for strings over 64 bytes - `reader.rs`: `OnDiskReader` — covering reads of committed facts (`CommittedReader`); `live_facts` decides net-assert on index keys (#379) - `verify.rs`: integrity walk for `Minigraf::verify` (tree order, index digests, DICT, page accounting) and the source choice for `rebuild_indexes` (#373) - - `meta.rs` / `page.rs` / `freelist.rs`: meta pages A/B, the common page header and allocator, free-list chain + - `meta.rs` / `page.rs` / `freelist.rs`: meta pages A/B, the common page header and allocator (skips quarantined ids), free-list chain + - `pins.rs`: `Pins` / `GenerationPin` — generations held by open snapshots and the quarantine of pages checkpoints freed after them (#543) - `cache.rs`: LRU page cache (`PageCache`, default 256 pages) - `dir_sync.rs`: `sync_parent_dir` — fsyncs the parent directory after creating the `.graph`/WAL or deleting the WAL (no-op off Unix) - `packed_pages.rs`: v7 fact pages, read only for migration @@ -144,7 +145,7 @@ cargo run < demos/demo_negation.txt 6. **`src/db.rs`** — Public API: `Minigraf::open/execute/query/fact_log/prepare/begin_write/checkpoint/save/verify/rebuild_indexes`, `WriteTransaction`, `IntegrityReport`, `OpenOptions::page_cache_size`, `OpenOptions::read_only` (#429: shared lock, nothing written, writes are `API-014`) - `src/cursor.rs`: `Cursor` / `Batch` — owned, `Send` cursor returned by `Minigraf::query` and `PreparedQuery::query` (#432); answer computed at open today, shaped for streaming operators - - `src/fact_log.rs`: `FactLog` / `FactFilter` / `FactRecord` / `FactOrder` — every fact version streamed by `Minigraf::fact_log` (#430): tx order (multi-pass, bounded window) or storage order, key-level filters; an open log pins the committed generation, deferring checkpoints (`API-013`) + - `src/fact_log.rs`: `FactLog` / `FactFilter` / `FactRecord` / `FactOrder` — every fact version streamed by `Minigraf::fact_log` (#430): tx order (multi-pass, bounded window) or storage order, key-level filters; an open log pins the committed generation (`storage::pins`), so checkpoints run but do not reuse its pages (`API-013` deprecated, #543) - `src/log_writer.rs`: `LogWriter` — builds a new file from `FactRecord`s with their tx and valid-time kept (#431): tx-ordered appends with holes (`API-015`/`API-016`), batched copy-on-write checkpoints at tx boundaries, no WAL, built at `.partial` and renamed by `finish` (`STG-043` if the target exists) 7. **`src/wal.rs`** — Fact-level sidecar WAL, CRC32-protected entries, crash recovery. Like `storage::verify` and `storage::dir_sync`, not compiled for wasm32 (no file backend there) @@ -201,7 +202,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1446 tests** (1436 passing, 10 ignored; unit + integration + doc). +**1457 tests** (1447 passing, 10 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/ROADMAP.md b/ROADMAP.md index 6c4385a9a5..24ef71e3c0 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -94,7 +94,7 @@ Scope — format and storage integrity: Scope — query API: - Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`, with the current evaluator computing the answer at open). The binding cursor objects follow. Streaming operators replace the evaluator behind the cursor in 3.x without further API changes; how operators bound their memory (spill, scratch pages in the `.graph` file, or a clear error) is still open. -- Fact-log iterator: `Minigraf::fact_log(&FactFilter)` streams every fact version (assertions and retractions, with `tx_count`, `tx_id` and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on `v3`). An open log defers checkpoints (`API-013` for an explicit one). A raw log writer (#431) completes the extract-transform-load path; the binding objects follow with #462. +- Fact-log iterator: `Minigraf::fact_log(&FactFilter)` streams every fact version (assertions and retractions, with `tx_count`, `tx_id` and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on `v3`). An open log pins its generation: checkpoints run but do not reuse its pages (#543; `API-013` deprecated). A raw log writer (#431) completes the extract-transform-load path; the binding objects follow with #462. - Read-only open: `OpenOptions::read_only` takes a shared lock, so several readers can hold a file at once, writes nothing to the file or its WAL (a WAL is applied in memory, a v7 file is read without migrating), and refuses writes with `API-014` (#429; Rust API done on `v3`). The bindings' `open_with_options` follows. - Raw log writer: `LogWriter` builds a new database from `FactRecord`s with their `tx_count`, `tx_id`, valid-time windows and assertion flags kept, gaps allowed (a purged transaction stays a hole for `:as-of`), at `.partial` renamed into place by `finish` (#431; Rust API done on `v3`). Completes extract (#429, #430), transform, load. The binding objects follow. diff --git a/docs/DURABILITY.md b/docs/DURABILITY.md index 704d969f10..97ff566396 100644 --- a/docs/DURABILITY.md +++ b/docs/DURABILITY.md @@ -122,7 +122,7 @@ out.advance_tx_count(tx_count)?; out.finish()?; ``` -- The log reads the database as it was when it opened, uncheckpointed transactions included. Writes go on meanwhile; they stay in the WAL, and checkpoints wait until the log is dropped (`checkpoint()` with work to do fails with `API-013`). +- The log reads the database as it was when it opened, uncheckpointed transactions included. Writes and checkpoints go on meanwhile. The log pins the committed generation it opened on, so checkpoints do not reuse the pages it reads: on a database taking many writes, the file grows by the pages checkpoints replace until the log is dropped, and later checkpoints reuse them. - Read the transaction count after opening the log, so it covers every logged transaction. The copy keeps every fact version with its `tx_count`, `tx_id` and valid-time window, so `:as-of` and `:valid-at` answer the same; internal ids and page layout are new. - The copy is built at `backup/app.graph.partial` and renamed into place by `finish()`, so an interrupted backup never leaves a partial file under the final name. @@ -185,7 +185,7 @@ Every error has a code (`MinigrafError::code()`); the [error reference](https:// | What to do | Codes | |---|---| -| **Retry later.** Nothing is wrong with the file | `STG-026` (another process holds the database: wait for it to exit), `API-013` (a fact log is open: drop it, then checkpoint) | +| **Retry later.** Nothing is wrong with the file | `STG-026` (another process holds the database: wait for it to exit) | | **Fix the setup.** The file is fine | `STG-025` (this process already has the file open: reuse that handle), `STG-027` (the filesystem cannot lock), `STG-042` (no file at the path, read-only open), `STG-043` (the log writer's target exists), `WAL-006` (the WAL could not be deleted after a checkpoint, usually directory permissions; nothing is lost) | | **Reopen.** The handle refuses writes; every committed transaction is in the WAL | `STG-046`, `WAL-007`, an I/O error from a write or checkpoint (fix the cause first), `API-001` (a thread panicked while holding the write lock) | | **Use another library version.** The file is not modified | `STG-006` (format newer than this library), `STG-034` (feature bits from a newer v3.x), `STG-028` (format older than v7: open with v2.x first), `WAL-002` (WAL from another version: open with that version and `checkpoint()`) | diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index 976e331360..e44d9c1122 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -178,7 +178,7 @@ with no `CodedError` anywhere in its chain. | API-010 | Query with bind slots passed to execute() | Database API | | API-011 | Two valid-time windows for one fact in one transact | Database API | | API-012 | Non-query command passed to query() | Database API | -| API-013 | Checkpoint while a fact log is open | Database API | +| API-013 | Checkpoint while a fact log is open (deprecated) | Database API | | API-014 | Write on a read-only handle | Database API | | API-015 | Log writer record out of transaction order | Database API | | API-016 | Log writer record with a second tx_id for one transaction | Database API | @@ -244,7 +244,7 @@ with no `CodedError` anywhere in its chain. | INT-055 | Rule predicate disappeared during rollback | Internal | | INT-056 | Write to a read-only storage backend | Internal | -Deprecated codes: STG-003 and STG-004 (pre-v7 header sizes) are deprecated as of v3.0.0 and are no longer emitted, because formats v1–v6 are rejected with STG-028 before any header-size check. They stay registered and documented, and error codes are never removed or reused. +Deprecated codes: STG-003 and STG-004 (pre-v7 header sizes) are deprecated as of v3.0.0 and are no longer emitted, because formats v1–v6 are rejected with STG-028 before any header-size check. API-013 (checkpoint while a fact log is open) is deprecated as of v3.0.0 and is no longer emitted, because checkpoints run while fact logs are open. They stay registered and documented, and error codes are never removed or reused. --- @@ -2651,6 +2651,8 @@ while let Some(batch) = cursor.next_batch(1000)? { ### API-013 Checkpoint while a fact log is open +> **Deprecated in v3.0.0.** No longer emitted: a fact log pins the committed generation it opened on, and checkpoints run while it is open without reusing the pages it reads. Kept for reference; this code will not be reused. + **Error text**: `checkpoint deferred while {} fact log(s) are open; close them and checkpoint again` **Cause**: `db.fact_log()` returns a `FactLog` that reads the committed pages as they were when it opened. A checkpoint frees pages that a later checkpoint reuses, so while any fact log is open, checkpoints are deferred. Writes still succeed and stay in the WAL, and automatic checkpoints wait. `checkpoint()` or `rebuild_indexes()` with uncheckpointed writes, or `rebuild_indexes()` on a file database, returns this error. The `{}` is the number of open logs. Nothing is written. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 166744d800..d9d99706a0 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-13 with `cargo test --quiet` -**Result**: 1,436 passing tests and 10 ignored tests (1,446 total) +**Result**: 1,447 passing tests and 10 ignored tests (1,457 total) This covers 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. It otherwise still covers 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). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (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 at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). `tests/property_test.rs` writes random histories (batched transacts, retracts, write transactions, checkpoints) in memory and to a file, and compares random queries (one to three joined patterns, `not` or `not-join`, a comparison predicate, `:as-of`, `:valid-at` or `:any-valid-time`) with a reference evaluator, on the open file and after a reopen; a query error fails the test (#386). `tests/crash_kill_test.rs` kills a child process running a seeded workload (multi-valued batches, batched retracts, five checkpoint modes) at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries and `verify`, again after a second reopen and after a checkpoint plus reopen (#384). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Page-count tests (#497) check that a CRC-valid meta whose `page_count` is past the end of the file (one page past, 2^50, `u64::MAX`; with the other slot valid or damaged; with or without a WAL) and a file cut short by one page, three pages or down to three pages are `STG-044` at open, with the file unchanged and not grown, while a `page_count` exactly at the end opens; that a checkpoint whose pages did not all reach the backend fails with `INT-049` before writing its meta, and the file reopens at the previous generation; and that `verify` at a meta counting pages past the end reports `STG-044` without scanning to that count. Through `Minigraf` (`tests/integrity_test.rs`), a file truncated by one or three pages and a file whose meta was rewritten with `page_count` 2^50 and a valid CRC are `STG-044` read-write and read-only, with no WAL created and the file length unchanged. The `file_header` fuzz input from #497 is a corpus seed. A sub-page test (#506, `tests/integrity_test.rs`) checks that a file of 1 to 4,095 bytes is `STG-045` read-write and read-only, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes writes when it is a prefix of the first meta page or all zeros; a file-backend unit test checks that `partial_page` returns the bytes past the last whole page. The `corrupt_file` fuzzer no longer skips files under one page: they must fail to open or open empty, and the #506 input is a corpus seed. Damaged v7 fact page tests (#496) check that a page in the counted fact range whose type byte is anything but the fact-page type (zero, `0x01`, the v2.x B+tree types, `0xFF`, a zeroed page; first and last page) is `STG-014` rather than skipped, while a range derived from the first index root skips only v2.x B+tree pages; that opening such a v7 file read-write or read-only fails with `STG-014` and writes nothing; and, in `tests/migration_matrix_test.rs`, that the golden `v7_basic.graph` with page 1's type byte changed or page 1 overwritten with noise fails both opens with the file unchanged and no WAL created. Both inputs are `fact_page` corpus seeds. Merged from the v2.x line: `tests/edge_cases_test.rs` checks the same refusal and acceptance through `Minigraf::open` on a database checkpointed twice (#506). Torn-WAL-tail tests (#513) check that opening a WAL writer cuts off a partial last entry (cut in the checksum, the header or the payload) or an entry with a bad checksum and everything after it, then appends where replay reaches, and leaves an intact WAL byte for byte; that an append that fails part-way makes every later append `WAL-007` while a rejected oversize fact (`WAL-003`, nothing written) does not; through `Minigraf`, that the failed transaction is not applied, later `transact` and `commit` are `WAL-007`, and a `checkpoint()` makes writes work again; and, in `tests/wal_test.rs`, that a commit made after reopening a crash-left WAL with each kind of torn tail survives a second crash. The fault matrix (#390, `src/fault_matrix.rs`) drives a test-only fault plan through the real file backend, WAL and directory fsync: an EIO, a short or torn write (1, 40 and 4,095 bytes), a full disk that keeps failing every later write, a failed fsync, and a failed fsync that also loses the writes since the last good one ("fsyncgate"), each at every write or sync call of a transact, a transact that creates the WAL, an automatic checkpoint, `checkpoint()`, the close-time checkpoint and `rebuild_indexes()`, on a database committed over two checkpoints with multi-valued, retracted and long values and entries pending in the WAL. After each fault, the handle holds the old facts or those plus the whole transaction, never part of one; after a failed checkpoint another is `STG-046`; a later write succeeds or is `WAL-007`/`STG-046`; a kill and reopen gives exactly the handle's facts, plus the failed transaction whole or not at all, and `verify` finds nothing; and a commit after recovery survives another kill. Two more tests fill the disk halfway through a checkpoint (`STG-046`, reads unchanged, reopen intact), and fail the fsync after a checkpoint's meta write and then retry the checkpoint, crashing at each of its writes: the retry is refused and every reopen is intact (without the refusal, a reopen hits `STG-029`). Unit tests check the fault plan's counting, and that a `rebuild_indexes` refused with `STG-041` leaves the handle usable. Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `API-011` from `transact` and from `WriteTransaction::execute`, and a later statement's window committed when two statements of a `WriteTransaction` give one fact different windows. Window-validation tests (#436) check that `check_valid_windows` rejects an empty window, an inverted one, and a `:valid-to` at or before the transaction time when `:valid-from` is left out, but not retractions; that `execute` rejects each such `transact` (both bounds, equal bounds, `:valid-to` only, a per-fact bound inverting the transaction's window) with `API-019` without writing or taking a `tx_count`, in memory, checkpointed and after reopen; that `tx.execute()` rejects them and the transaction still commits its other statements; that `commit()` rejects a default `valid_from` that has passed the `:valid-to` by commit time; and that `FactStorage::transact_batch` takes no `tx_count` on rejection. Statement-order tests (#477, `tests/statement_order_test.rs`) run every mix of two statements on one fact inside a `WriteTransaction` (retract then assert, assert then retract, two retracts, two windows, after a committed assertion and on an empty database) and check that reads inside the transaction and the committed rows agree, in memory, checkpointed and after reopen; that other facts of an overridden statement survive; that the commit is one transaction without the overridden records; and that two windows in one statement are `API-011` from `tx.execute()` while the rest commits. A unit test checks the commit collapse keeps each fact's newest statement in order. A log-writer test checks that an inverted window is `API-019`, a second window of a fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction `API-020` in either order, each leaving the writer usable and the output exact, while duplicate retractions, identical repeats and the same fact in the next transaction are accepted. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011`, a retraction of an asserted fact in one transaction `API-020`, an empty window `API-019` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Query-validation tests (#406, #414) check that a plain `:find` variable or a window function's argument, `:partition-by` or `:order-by` variable that no `:where` clause binds (including `?_` wildcards) is `PRS-080` from both `execute()` and `prepare()`, naming the variable, while variables bound by a pattern, an attribute position, a rule call, an expression binding, an `or-join`, every branch of an `or`, a pseudo-attribute or a window spec are accepted, and bind slots are not mistaken for `:find` variables; and that an unknown aggregate is `QRY-010` and an unknown window function `QRY-011` on an empty database, when no row matches, when rows match, through a rule query and through a prepared query, while a registered UDF in either position returns an empty result on an empty database. Coverage-gate tests (#396) check that replay stops at a WAL entry whose first fact is longer than 10 MB or that claims more than 1M facts, that a WAL writer cannot be opened in a missing directory, and that a failed cut of a torn WAL tail fails the open and leaves the file as it was; that a short v7 page and a slot past the record count are `INT-024`; that a migration backup meta of another generation or file length is not used (`STG-032`, file unchanged), and a torn first meta with data in page 1 is `STG-032`, not a new file; that `save` with nothing pending writes nothing, `into_backend` saves pending facts, and `rebuild_indexes` with nothing checkpointed commits the pending facts; and that unsorted or repeated B+tree input and a stored key inserted with another value are `INT-049`, a tree pointer to a free-list page is `STG-013` from `get`, a leaf walk and a copy-on-write insert, and the read-only `MutexStorageBackend` refuses writes, syncs and close. A page-cache test holds two threads in the backend read so both miss the same page, and checks that both get the one cached copy; before it, that path ran only when the scheduler happened to race the threads, and the gate flapped. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 956 passing; ten that spawn threads or a child process are ignored on WASI. These are not counted above. A WAL test checks that a checkpoint with no facts to flush still removes a WAL whose entries are all already in the file, and the golden-corpus test now requires the WAL to be gone after a checkpoint for the `stale_wal` fixtures too (#457). A WAL test checks that closing a handle opened with `wal_checkpoint_threshold(usize::MAX)`, in both sync modes, leaves the `.graph` file byte for byte as it was and keeps the WAL, whose entries replay on the next open, and a unit test closes an in-memory handle under the same setting (#476). A recursive-rule test checks that a rule query on a database with more live facts than `max_results` returns its answer, with a bound and with a free first argument, and that a query deriving more facts than its `:max-results` is still `INT-020` (#528). A log-writer test runs the online backup from `docs/DURABILITY.md`: it copies a read-write handle with an uncheckpointed transaction through `fact_log` and `LogWriter` while another thread writes past the automatic checkpoint threshold, and checks that the copy verifies clean, holds exactly the records the log returned and the counter read after the log opened, and that every concurrent write reaches the source's file once the log is dropped (#398). @@ -13,7 +13,7 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value - **Core database behavior**: in-memory and file-backed operation, transactions, checkpoints, retractions, bi-temporal queries, recursive rules, prepared statements, aggregation, expressions, disjunction, window functions, UDFs, and magic-sets evaluation. - **Multi-value and index-key correctness** (`tests/multi_value_test.rs`, 10 tests): same-transaction multi-valued facts surviving query-time dedup, retracting several values of one attribute in one call, valid-time stints (facts differing only in valid time), maximum-value-size boundaries, and format v8 index keys (value bytes + assert/retract flag) (#287, #371). - **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration (including v7→v8 index rebuild and v1–v6 rejection via `STG-028`), WAL replay, checksums, corruption handling, and fault injection. -- **Reliability and concurrency**: concurrent reads and writes, rollback behavior, same-process handle exclusion, cross-process locking, PID namespaces, NFS and container lock behavior, SIGKILL recovery, and queries seeing each concurrent transaction whole and reading one state for all their patterns, including while a checkpoint runs (`tests/snapshot_atomicity_test.rs`, #554, #555, #558). +- **Reliability and concurrency**: concurrent reads and writes, rollback behavior, same-process handle exclusion, cross-process locking, PID namespaces, NFS and container lock behavior, SIGKILL recovery, and queries seeing each concurrent transaction whole and reading one state for all their patterns, including while a checkpoint runs (`tests/snapshot_atomicity_test.rs`, #554, #555, #558). Generation pins (#543): a pinned generation's pages are never written by later saves or index rebuilds and are reused once the pin is dropped (by page id, `storage::persistent_facts`, `storage::pins`, `storage::page`); fact logs stay correct while checkpoints, rebuilds and concurrent writers run, and see whole transactions only (`tests/fact_log_test.rs`). - **Public diagnostics**: structured parser, query, storage, WAL, API, and internal error codes; the error-code registry is checked against [`ERROR_REFERENCE.md`](ERROR_REFERENCE.md). - **Compatibility and quality**: golden-file corpus of released file formats, cross-platform format compatibility, property-based tests, long-haul smoke coverage, a weekly soak at 10M facts with a 5-hour churn (#392), XTDB/Datomic semantic compatibility, grammar conformance, and rustdoc examples. diff --git a/docs/superpowers/plans/2026-10-11-543-snapshots-and-quarantine.md b/docs/superpowers/plans/2026-10-11-543-snapshots-and-quarantine.md index 45d24aff27..c123c7abcc 100644 --- a/docs/superpowers/plans/2026-10-11-543-snapshots-and-quarantine.md +++ b/docs/superpowers/plans/2026-10-11-543-snapshots-and-quarantine.md @@ -110,6 +110,9 @@ the rest of the docs. the pin holds pages (no reuse) until the cursor is dropped. ### 6. Fact log +- PR 2 adds `Snapshot` with only what the log needs (`committed`, the pin, the + pending store and its length, `pending_range`) and `FactStorage::snapshot()`; + step 5 adds `now`, the read methods and `Clone` (pin in an `Arc`). - `FactLog` holds a `Snapshot` instead of `LogPin` + `FactStorage` + `pending_end`; pending reads go to `snapshot.pending_range`. `Minigraf::fact_log` no longer takes `write_lock`. Remove `LogPin`, `pin_log`, `log_pins`, `log_snapshot`. diff --git a/src/db.rs b/src/db.rs index e595fd0b4b..3a0fa22e2d 100644 --- a/src/db.rs +++ b/src/db.rs @@ -759,9 +759,8 @@ impl Minigraf { let _ = self.inner.fact_storage.load_facts(stamped)?; // Trigger auto-checkpoint AFTER facts are in FactStorage so the - // checkpoint captures the newly written facts. An open fact log - // defers it; the first write after the log closes runs it (#430). - if should_checkpoint && self.inner.fact_storage.log_pins() == 0 { + // checkpoint captures the newly written facts. + if should_checkpoint { Minigraf::do_checkpoint(&self.inner.fact_storage, &mut ctx)?; } @@ -836,12 +835,13 @@ impl Minigraf { /// [`FactFilter::window`](crate::FactFilter::window) records, /// [`FactOrder::Storage`](crate::FactOrder::Storage) one batch. /// - /// While a log is open, checkpoints are deferred: writes still succeed and - /// stay in the WAL, automatic checkpoints wait, and [`checkpoint`] and - /// [`rebuild_indexes`] fail with `API-013` if they have work to do. Close - /// or drop the log (or read it to the end) to release the database. The - /// log owns what it reads, so it can outlive this handle and move to - /// another thread; the database file stays open until it is dropped. + /// Writes, [`checkpoint`] and [`rebuild_indexes`] go on while a log is + /// open. The log pins the committed generation it opened on: no checkpoint + /// reuses a page it may read, so the file grows by the pages checkpoints + /// replace until the log is closed or dropped (or read to the end). Keep + /// logs short-lived on a database that takes many writes. The log owns + /// what it reads, so it can outlive this handle and move to another + /// thread; the database file stays open until it is dropped. /// /// # Errors /// @@ -858,13 +858,8 @@ impl Minigraf { if is_write_tx_active() { bail_coded!(ErrorCode::Int001); } - // Held while the log opens: no transaction is half applied and no - // checkpoint runs until the log's pin is registered. - let _ctx = self - .inner - .write_lock - .lock() - .map_err(|_| err_coded!(ErrorCode::Api001))?; + // No write lock: the snapshot holds whole transactions, and its pin + // keeps checkpoints from reusing the pages it reads (#473 spec §4). crate::FactLog::open(&self.inner.fact_storage, filter) } @@ -1593,9 +1588,8 @@ impl<'a> WriteTransaction<'a> { let _ = self.inner.fact_storage.load_facts(stamped)?; // Trigger auto-checkpoint AFTER facts are in FactStorage so the - // checkpoint captures the newly written facts. An open fact log - // defers it; the first write after the log closes runs it (#430). - if should_checkpoint && self.inner.fact_storage.log_pins() == 0 { + // checkpoint captures the newly written facts. + if should_checkpoint { Minigraf::do_checkpoint(&self.inner.fact_storage, &mut self.guard)?; } } diff --git a/src/error.rs b/src/error.rs index 09062d28a2..22c725198c 100644 --- a/src/error.rs +++ b/src/error.rs @@ -210,6 +210,10 @@ pub(crate) enum ErrorCode { Api010, Api011, Api012, + // API-013 is deprecated since v3.0.0: fact logs no longer defer + // checkpoints; they pin their generation instead (#543). Kept so the code + // is never reused. + #[allow(dead_code)] Api013, Api014, Api015, diff --git a/src/fact_log.rs b/src/fact_log.rs index c397f92260..f2071afcdb 100644 --- a/src/fact_log.rs +++ b/src/fact_log.rs @@ -5,13 +5,13 @@ //! bounds), filtered by a [`FactFilter`]. It reads the index trees directly, //! without Datalog, and its memory does not grow with the database. //! -//! The log reads the database as it was when it opened. While any log is open, -//! checkpoints are deferred: writes still succeed and stay in the WAL, and -//! [`crate::Minigraf::checkpoint`] fails with `API-013`. Close the log, or drop -//! it, to release the database. +//! The log reads the database as it was when it opened. Writes and checkpoints +//! go on meanwhile: the log pins the committed generation it opened on, so no +//! checkpoint reuses the pages it reads, and those pages stay allocated in the +//! file until the log is closed or dropped (#473 spec §4.2). use crate::error::{ErrorCode, MinigrafError, err_coded}; -use crate::graph::storage::{FactStorage, LogPin}; +use crate::graph::storage::{FactStorage, Snapshot}; use crate::graph::types::{EntityId, Fact, Value}; use crate::storage::keys::{self, Index}; use crate::storage::{CommittedReader, LogSource}; @@ -197,8 +197,9 @@ impl FactFilter { /// A forward-only stream of fact records, from [`crate::Minigraf::fact_log`]. /// /// Pull records with [`FactLog::next_batch`] or iterate over them. The log -/// holds the database as it was when it opened and defers checkpoints until -/// it is closed or dropped, or has returned its last record. +/// holds the database as it was when it opened. Checkpoints still run, but +/// the pages they replace stay allocated until the log is closed or dropped, +/// or has returned its last record. /// /// ``` /// # use minigraf::{FactFilter, Minigraf}; @@ -216,12 +217,11 @@ impl FactFilter { pub struct FactLog { filter: FactFilter, committed: Option, - storage: FactStorage, - /// Next pending fact to read, and the end of the snapshot. + /// The state the log reads; None once it is finished. + snapshot: Option, + /// Next pending fact of the snapshot to read. pending_pos: usize, - pending_end: usize, done: bool, - pin: Option, } impl std::fmt::Debug for FactLog { @@ -234,23 +234,20 @@ impl std::fmt::Debug for FactLog { } impl FactLog { - /// Open a log over the current state of `storage`. The caller holds the - /// write lock, so no transaction is half applied and no checkpoint runs. + /// Open a log over a snapshot of `storage`: whole transactions only, and + /// a committed generation no checkpoint can take away. pub(crate) fn open(storage: &FactStorage, filter: &FactFilter) -> anyhow::Result { - let pin = storage.pin_log(); - let (reader, pending_end) = storage.log_snapshot()?; - let committed = match reader { - Some(reader) => Committed::new(reader, filter)?, + let snapshot = storage.snapshot()?; + let committed = match &snapshot.committed { + Some(reader) => Committed::new(Arc::clone(reader), filter)?, None => None, }; Ok(FactLog { filter: filter.clone(), committed, - storage: storage.clone(), + snapshot: Some(snapshot), pending_pos: 0, - pending_end, done: false, - pin: Some(pin), }) } @@ -284,7 +281,7 @@ impl FactLog { fn finish(&mut self) { self.done = true; self.committed = None; - self.pin = None; + self.snapshot = None; } fn fill(&mut self, n: usize) -> anyhow::Result> { @@ -295,15 +292,19 @@ impl FactLog { self.committed = None; } } - while out.len() < n && self.pending_pos < self.pending_end { + let Some(snapshot) = &self.snapshot else { + return Ok(out); + }; + let pending_end = snapshot.pending_len(); + while out.len() < n && self.pending_pos < pending_end { let end = self .pending_pos .saturating_add(n - out.len()) - .min(self.pending_end); - let facts = self.storage.pending_range(self.pending_pos, end)?; + .min(pending_end); + let facts = snapshot.pending_range(self.pending_pos, end)?; if facts.is_empty() { // The snapshot ends here; nothing past it can appear. - self.pending_pos = self.pending_end; + self.pending_pos = pending_end; break; } self.pending_pos = self.pending_pos.saturating_add(facts.len()); diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 250ec5f589..1174c6d402 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -4,9 +4,10 @@ use crate::graph::types::{ }; use crate::query::datalog::types::AsOf; 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, AtomicUsize, Ordering}; +use std::sync::atomic::{AtomicU64, Ordering}; use std::sync::{Arc, RwLock}; /// Compact key for O(1) duplicate detection in `PendingStore::keys`. @@ -136,17 +137,39 @@ pub(crate) struct FactStorage { data: Arc>, /// Monotonically incrementing batch counter — increments once per transact/retract call. tx_counter: Arc, - /// Open fact logs (#430). While above zero, no checkpoint may publish a - /// new committed generation: a log reads pages of the one it opened on. - log_pins: Arc, + /// Generations held by open snapshots, and the pages checkpoints freed + /// that they may still read (#473 spec §4.2). + pins: Arc, } -/// Keeps checkpoints from running while a fact log is open; released on drop. -pub(crate) struct LogPin(Arc); +/// The database as one read sees it: a committed generation, pinned so no +/// checkpoint reuses its pages, and the first `pending_len` facts of the +/// pending store that followed it. Taken under one `FactData` lock, so it +/// never holds part of a transaction or of a checkpoint. +pub(crate) struct Snapshot { + pub(crate) committed: Option>, + /// None for in-memory databases: there are no pages to hold. + _pin: Option, + pending: Arc>, + pending_len: usize, +} -impl Drop for LogPin { - fn drop(&mut self) { - self.0.fetch_sub(1, Ordering::SeqCst); +impl Snapshot { + /// The number of pending facts in the snapshot. + pub(crate) fn pending_len(&self) -> usize { + self.pending_len + } + + /// Clones of the snapshot's pending facts at positions `from..to` + /// (clamped). The store is append-only and never cleared, so these are + /// the facts that were there when the snapshot was taken. + pub(crate) fn pending_range(&self, from: usize, to: usize) -> Result> { + let p = self + .pending + .read() + .map_err(|_| err_coded!(ErrorCode::Int050, "pending"))?; + let to = to.min(self.pending_len).min(p.facts.len()); + Ok(p.facts.get(from.min(to)..to).unwrap_or(&[]).to_vec()) } } @@ -166,7 +189,7 @@ impl FactStorage { pending: PendingStore::new(), })), tx_counter: Arc::new(AtomicU64::new(0)), - log_pins: Arc::new(AtomicUsize::new(0)), + pins: Pins::new(), } } @@ -426,47 +449,31 @@ impl FactStorage { p.facts.clone() } - /// The committed reader and the number of pending facts, read together. - /// - /// The pending list is append-only between checkpoints, so with a - /// [`LogPin`] held its first `len` entries stay where they are. - pub(crate) fn log_snapshot( - &self, - ) -> Result<(Option>, usize)> { - let d = self - .data - .read() - .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - let p = d - .pending - .read() - .map_err(|_| err_coded!(ErrorCode::Int050, "pending"))?; - Ok((d.committed.clone(), p.facts.len())) - } - - /// Clones of the pending facts at positions `from..to` (clamped). - pub(crate) fn pending_range(&self, from: usize, to: usize) -> Result> { + /// Take a [`Snapshot`] of the current state: the committed reader, pinned, + /// and the pending store with its length, all under `FactData`'s lock. + pub(crate) fn snapshot(&self) -> Result { let d = self .data .read() .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - let p = d + let pending_len = d .pending .read() - .map_err(|_| err_coded!(ErrorCode::Int050, "pending"))?; - let to = to.min(p.facts.len()); - Ok(p.facts.get(from.min(to)..to).unwrap_or(&[]).to_vec()) - } - - /// Register an open fact log; checkpoints are refused until it is dropped. - pub(crate) fn pin_log(&self) -> LogPin { - self.log_pins.fetch_add(1, Ordering::SeqCst); - LogPin(self.log_pins.clone()) + .map_err(|_| err_coded!(ErrorCode::Int050, "pending"))? + .facts + .len(); + Ok(Snapshot { + committed: d.committed.clone(), + _pin: d.committed.as_ref().map(|_| self.pins.pin(d.generation)), + pending: Arc::clone(&d.pending), + pending_len, + }) } - /// The number of open fact logs. - pub(crate) fn log_pins(&self) -> usize { - self.log_pins.load(Ordering::SeqCst) + /// Ids freed by checkpoints that an open snapshot may still read. A + /// checkpoint must not hand any of them out. + pub(crate) fn pages_in_force(&self) -> HashSet { + self.pins.in_force() } /// Set the tx_counter to `max` (used on load to restore from persisted state). @@ -491,7 +498,8 @@ impl FactStorage { /// first `checkpointed` pending facts, and a new pending store replaces the /// old one, all under one write lock, so no read sees a checkpointed fact /// twice (#473 spec §4.1). The old store is left intact for readers that - /// hold it. + /// hold it. `freed` (pages the previous generation referenced and this one + /// does not) stays in quarantine while an older generation is pinned. /// /// Facts appended after the checkpoint read the pending store (positions /// `checkpointed..`) move to the new store, so none is lost. The database's @@ -501,8 +509,10 @@ impl FactStorage { reader: Arc, generation: u64, checkpointed: usize, + freed: Vec, ) { let mut d = self.data.write().unwrap_or_else(|e| e.into_inner()); + self.pins.record(generation, freed); let pending = PendingStore::new(); { let old = d.pending.read().unwrap_or_else(|e| e.into_inner()); @@ -1701,7 +1711,12 @@ mod tests { let checkpointed = storage.get_pending_facts(); let n = checkpointed.len(); - storage.publish(std::sync::Arc::new(MockReader(checkpointed)), 2, n); + storage.publish( + std::sync::Arc::new(MockReader(checkpointed)), + 2, + n, + Vec::new(), + ); assert_eq!(storage.generation(), 2); assert_eq!( storage.pending_index_counts(), @@ -1734,7 +1749,12 @@ mod tests { .unwrap(); let n = checkpointed.len(); - storage.publish(std::sync::Arc::new(MockReader(checkpointed)), 2, n); + storage.publish( + std::sync::Arc::new(MockReader(checkpointed)), + 2, + n, + Vec::new(), + ); let pending = storage.get_pending_facts(); assert_eq!(pending.len(), 1, "late fact carried over"); assert_eq!(pending[0].value, Value::Integer(2)); diff --git a/src/storage/mod.rs b/src/storage/mod.rs index cc3149a156..46254bd893 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -21,6 +21,7 @@ pub(crate) mod node; pub mod packed_pages; pub(crate) mod page; pub mod persistent_facts; +pub(crate) mod pins; pub(crate) mod reader; pub(crate) mod value_pages; // `Minigraf::verify` / `rebuild_indexes` walk a file; not built for wasm32. diff --git a/src/storage/page.rs b/src/storage/page.rs index 9b3ef95128..994c1c1b52 100644 --- a/src/storage/page.rs +++ b/src/storage/page.rs @@ -167,9 +167,17 @@ pub fn new_page(page_type: u8, count: u16) -> Vec { /// that has been read is replaced: [`PageAllocator::finish_free_list`] pushes it, /// its unused ids and every freed page as new head pages in front of the unread /// tail, which is shared unchanged. +/// +/// Ids in the quarantine ([`PageAllocator::with_quarantine`]) are free but may +/// still be read by a pinned generation (#473 spec §4.2): they are never +/// handed out, and the new free list keeps them. pub struct PageAllocator { /// Free ids ready to hand out, in reverse order (`pop` yields the next). free: Vec, + /// Ids that must not be handed out in this generation. + quarantine: std::collections::HashSet, + /// Free ids passed over because they are in the quarantine. + skipped: Vec, /// First chain page not read yet (0: none). chain_next: u64, /// Ids in the chain pages not read yet. @@ -189,6 +197,8 @@ impl PageAllocator { free.sort_unstable_by(|a, b| b.cmp(a)); PageAllocator { free, + quarantine: std::collections::HashSet::new(), + skipped: Vec::new(), chain_next: 0, chain_tail_count: 0, chain_read: Vec::new(), @@ -203,6 +213,8 @@ impl PageAllocator { pub fn from_chain(head: u64, count: u64, next_append: u64, generation: u64) -> Self { PageAllocator { free: Vec::new(), + quarantine: std::collections::HashSet::new(), + skipped: Vec::new(), chain_next: head, chain_tail_count: count, chain_read: Vec::new(), @@ -212,6 +224,16 @@ impl PageAllocator { } } + /// Never hand out an id in `ids`; any such free id is listed again by + /// [`finish_free_list`](Self::finish_free_list). + pub fn with_quarantine(mut self, ids: std::collections::HashSet) -> Self { + let (skipped, free) = self.free.into_iter().partition(|id| ids.contains(id)); + self.free = free; + self.skipped = skipped; + self.quarantine = ids; + self + } + /// The generation every page written through this allocator is stamped with. #[cfg(test)] pub fn generation(&self) -> u64 { @@ -232,6 +254,10 @@ impl PageAllocator { ) -> Result { loop { if let Some(id) = self.free.pop() { + if self.quarantine.contains(&id) { + self.skipped.push(id); + continue; + } return Ok(id); } if self.chain_next == 0 { @@ -263,8 +289,8 @@ impl PageAllocator { Ok(id) } - /// Free ids not handed out, in hand-out order. Chain pages not read yet are - /// not included. + /// Free ids not handed out, in hand-out order. Chain pages not read yet and + /// quarantined ids are not included. #[cfg(test)] pub fn take_unused_free(&mut self) -> Vec { let mut v = std::mem::take(&mut self.free); @@ -277,7 +303,8 @@ impl PageAllocator { /// tail). /// /// The list is `freed` (pages the new meta no longer references), every - /// chain page read and the ids read but not handed out, as new head pages in + /// chain page read, the quarantined ids passed over and the ids read but not + /// handed out, as new head pages in /// front of the unread tail. The head pages themselves are allocated here, /// which may read more of the chain, so this repeats until the page count /// covers the ids. Nothing listed here is handed out in this generation. @@ -292,6 +319,7 @@ impl PageAllocator { let ids = loop { let mut ids = freed.clone(); ids.extend(self.chain_read.iter().copied()); + ids.extend(self.skipped.iter().copied()); ids.extend(self.free.iter().rev().copied()); // Use the first `k` allocated pages for the chain and list the rest // as free: the smallest `k` whose pages hold every listed id. @@ -413,4 +441,55 @@ mod tests { assert_eq!(a.next_append(), 22); assert_eq!(a.generation(), 2); } + + #[test] + fn quarantined_ids_are_never_handed_out_and_stay_listed() { + let b = crate::storage::backend::MemoryBackend::new(); + let c = crate::storage::cache::PageCache::new(0); + let mut a = PageAllocator::new(vec![9, 4, 7, 5], 20, 2).with_quarantine([4, 9, 30].into()); + assert_eq!(a.alloc(&b, &c).unwrap(), 5); + assert_eq!(a.alloc(&b, &c).unwrap(), 7); + assert_eq!(a.alloc(&b, &c).unwrap(), 20, "4 and 9 are skipped"); + assert_eq!(a.take_unused_free(), Vec::::new()); + } + + #[test] + fn quarantined_chain_ids_are_listed_by_finish_free_list() { + use crate::storage::backend::MemoryBackend; + use crate::storage::freelist; + let mut b = MemoryBackend::new(); + let c = crate::storage::cache::PageCache::new(0); + // A chain at generation 1 listing ids 3..=8, written from page 10 up. + let free: Vec = (3..=8).collect(); + let mut chain = PageAllocator::new(Vec::new(), 10, 1); + let (head, _) = freelist::write_chain(&free, &mut chain, &mut b, &c).unwrap(); + let end = chain.next_append(); + + let mut a = PageAllocator::from_chain(head, 6, end, 2).with_quarantine([3, 5, 8].into()); + let mut handed = Vec::new(); + for _ in 0..4 { + handed.push(a.alloc(&b, &c).unwrap()); + } + assert_eq!( + handed, + vec![4, 6, 7, end], + "only ids out of quarantine, then append" + ); + let (new_head, count, listed) = a.finish_free_list(vec![], &mut b, &c).unwrap(); + for id in [3, 5, 8] { + assert!(listed.contains(&id), "quarantined id listed again"); + assert!(!handed.contains(&id), "quarantined id never handed out"); + } + let (read, _) = freelist::read_chain(new_head, &b, &c, a.next_append()).unwrap(); + assert_eq!( + u64::try_from(read.len()).unwrap(), + count, + "count matches the list" + ); + let mut read = read; + read.sort_unstable(); + let mut want = listed.clone(); + want.sort_unstable(); + assert_eq!(read, want); + } } diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index 2e137d8e80..d7cb6a55a2 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -413,6 +413,9 @@ impl PersistentFactStorage { /// point. A failure at any step leaves the active meta and all it references /// untouched. The pages written depend on the change, not on the graph size. /// + /// Pages an open snapshot may still read (freed by an earlier checkpoint + /// after the generation it pins) are not reused; they stay on the free list. + /// /// After a failure that may have written (anything past the checks /// below), this and every later commit fail with STG-046. pub fn save(&mut self) -> Result<()> { @@ -420,7 +423,6 @@ impl PersistentFactStorage { if !self.dirty { return Ok(()); } - self.refuse_while_logs_open()?; let pending_facts = self.storage.get_pending_facts(); let m = self.meta; let next_gen = m.next_generation()?; @@ -429,7 +431,8 @@ impl PersistentFactStorage { let mut backend = self.lock()?; let mut alloc = - PageAllocator::from_chain(m.freelist_head, m.freelist_count, m.page_count, next_gen); + PageAllocator::from_chain(m.freelist_head, m.freelist_count, m.page_count, next_gen) + .with_quarantine(self.storage.pages_in_force()); let encoded = encode( &pending_facts, &m, @@ -454,6 +457,7 @@ impl PersistentFactStorage { )?; } let [eavt_root, aevt_root, avet_root, vaet_root, dict_root] = roots; + let quarantine = freed.clone(); let (freelist_head, freelist_count, listed) = alloc.finish_free_list(freed, &mut *backend, &self.page_cache)?; @@ -494,7 +498,7 @@ impl PersistentFactStorage { drop(listed); // All pending facts are now in `reader`. self.storage - .publish(reader, new_meta.generation, pending_facts.len()); + .publish(reader, new_meta.generation, pending_facts.len(), quarantine); Ok(()) } @@ -518,14 +522,14 @@ impl PersistentFactStorage { /// reference: ids from its free list that no walked page uses, then new /// pages at the end. The free list is derived again from the pages the new /// meta reaches, so a leaked or wrong free list is repaired too. Memory is - /// O(facts): every index key is held for the bulk build. + /// O(facts): every index key is held for the bulk build. As in `save`, pages + /// an open snapshot may still read are not reused. pub(crate) fn rebuild_indexes(&mut self) -> Result<()> { use crate::storage::btree::LeafCursor; use crate::storage::keys::{Index, KeyFact}; use std::collections::BTreeSet; self.refuse_if_failed()?; - self.refuse_while_logs_open()?; let m = self.meta; let next_gen = m.next_generation()?; @@ -539,8 +543,10 @@ impl PersistentFactStorage { let cache = PageCache::new(VERIFY_CACHE_PAGES); cache.set_generation_bound(m.generation); - // Choose the source and the ids that are safe to overwrite. - let (source, pool) = { + // Choose the source and the ids that are safe to overwrite: free, not + // walked, and not readable through an open snapshot. + let in_force = self.storage.pages_in_force(); + let (source, pool, keep) = { let mut w = verify::Walker::new(&*backend, &cache, m); let scans: Vec = [Index::Eavt, Index::Aevt, Index::Avet] .into_iter() @@ -564,9 +570,13 @@ impl PersistentFactStorage { keep.extend(dict.nodes.iter().copied()); let pool: BTreeSet = w .read_free_list() - .map(|(ids, _)| ids.into_iter().filter(|id| !keep.contains(id)).collect()) + .map(|(ids, _)| { + ids.into_iter() + .filter(|id| !keep.contains(id) && !in_force.contains(id)) + .collect() + }) .unwrap_or_default(); - (source, pool) + (source, pool, keep) }; // Nothing is written before this point (STG-041 leaves the file and @@ -670,6 +680,9 @@ impl PersistentFactStorage { let free: Vec = (2..alloc.next_append()) .filter(|p| !reached.contains(p)) .collect(); + // Pages the active generation used that the new one does not: a + // snapshot on it may still read them. + let quarantine: Vec = keep.difference(&reached).copied().collect(); let mut chain_alloc = PageAllocator::new(Vec::new(), alloc.next_append(), next_gen); let (freelist_head, _) = freelist::write_chain(&free, &mut chain_alloc, &mut *backend, &self.page_cache)?; @@ -688,12 +701,10 @@ impl PersistentFactStorage { self.failed = false; let reader = self.activate(new_meta); self.storage - .publish(reader, new_meta.generation, pending_facts.len()); + .publish(reader, new_meta.generation, pending_facts.len(), quarantine); Ok(()) } - /// API-013 while a fact log is open: it reads pages of the active - /// generation, and a commit frees pages that the next one reuses (#430). fn refuse_if_failed(&self) -> Result<()> { if self.failed { bail_coded!(ErrorCode::Stg046); @@ -707,13 +718,6 @@ impl PersistentFactStorage { self.failed } - fn refuse_while_logs_open(&self) -> Result<()> { - match self.storage.log_pins() { - 0 => Ok(()), - n => Err(err_coded!(ErrorCode::Api013, n)), - } - } - /// Get a reference to the underlying fact storage pub fn storage(&self) -> &FactStorage { &self.storage @@ -1152,6 +1156,119 @@ mod tests { assert!(m.freelist_count > 0, "old tree pages are on the free list"); } + // ── pins and quarantine (#543) ────────────────────────────────────────── + + /// Pages a reader of `meta` reads: `reachable` without the free-list chain. + fn read_pages(meta: &MetaPage, backend: &dyn StorageBackend) -> BTreeSet { + let mut set = reachable(meta, backend); + if meta.freelist_head != 0 { + let (_, chain) = freelist::read_chain( + meta.freelist_head, + backend, + &PageCache::new(0), + meta.page_count, + ) + .unwrap(); + for id in chain { + set.remove(&id); + } + } + set + } + + fn committed_set(snap: &crate::graph::storage::Snapshot) -> Vec { + as_set( + snap.committed + .as_ref() + .expect("a committed reader") + .all_facts() + .unwrap(), + ) + } + + /// Pin a generation, then run `commit` (a save or a rebuild) repeatedly: + /// no commit writes a page the pinned generation reads, the pinned reader + /// still returns its facts, and space stays accounted for. Once the pin is + /// dropped, the next commits reuse the pages it held. + fn check_pin_holds_pages(commit: impl Fn(&mut PersistentFactStorage)) { + let rec = RecordingBackend { + inner: MemoryBackend::new(), + written: Arc::new(Mutex::new(Vec::new())), + }; + let log = rec.written.clone(); + let mem = rec.inner.clone(); + let mut pfs = PersistentFactStorage::new(rec, 64).unwrap(); + let mut next_entity = 0; + for round in 0..4u64 { + transact_mixed(&mut pfs, &mut next_entity, 40, round); + pfs.save().unwrap(); + } + let snap = pfs.storage().snapshot().unwrap(); + let pinned = read_pages(&pfs.meta(), &mem); + let expect = committed_set(&snap); + let mut released: BTreeSet = BTreeSet::new(); + for round in 4..14u64 { + log.lock().unwrap().clear(); + transact_mixed(&mut pfs, &mut next_entity, 30, round); + commit(&mut pfs); + for id in log.lock().unwrap().iter() { + assert!(!pinned.contains(id), "a commit wrote a page the pin reads"); + } + assert!(committed_set(&snap) == expect, "pinned reader changed"); + let m = pfs.meta(); + assert_space_accounted(&m, &mem); + assert!(pfs.verify().unwrap().problems.is_empty(), "verify clean"); + released.extend(pinned.difference(&read_pages(&m, &mem))); + } + assert!(!released.is_empty(), "commits freed pinned pages"); + + drop(snap); + assert!( + pfs.storage().pages_in_force().is_empty(), + "quarantine dropped" + ); + // Every id the pin held is free and may be handed out again: commit + // until the file grows, which takes the ids before any append. + log.lock().unwrap().clear(); + let mut round = 14u64; + let start = pfs.meta().page_count; + while pfs.meta().page_count == start { + transact_mixed(&mut pfs, &mut next_entity, 30, round); + commit(&mut pfs); + assert_space_accounted(&pfs.meta(), &mem); + round += 1; + } + let written: BTreeSet = log.lock().unwrap().iter().copied().collect(); + assert!( + !written.is_disjoint(&released), + "pages held by the pin are reused once it is dropped" + ); + assert!(pfs.verify().unwrap().problems.is_empty()); + } + + #[test] + fn pinned_generation_pages_survive_saves() { + check_pin_holds_pages(|pfs| pfs.save().unwrap()); + } + + #[test] + fn pinned_generation_pages_survive_rebuilds() { + check_pin_holds_pages(|pfs| pfs.rebuild_indexes().unwrap()); + } + + #[test] + fn pinned_generation_pages_survive_saves_and_rebuilds() { + let flip = std::cell::Cell::new(false); + check_pin_holds_pages(|pfs| { + flip.set(!flip.get()); + if flip.get() { + pfs.save().unwrap() + } else { + pfs.rebuild_indexes().unwrap() + } + }); + } + #[test] fn generations_alternate_between_the_two_meta_pages() { let mem = MemoryBackend::new(); diff --git a/src/storage/pins.rs b/src/storage/pins.rs new file mode 100644 index 0000000000..bbf4c8a3d4 --- /dev/null +++ b/src/storage/pins.rs @@ -0,0 +1,184 @@ +//! Generation pins and the page quarantine (#473 spec §4.2). +//! +//! A reader that holds a committed generation `p` reads pages that generation +//! references. A checkpoint that publishes generation `g > p` frees some of +//! them, and a later checkpoint would hand them out again. So each checkpoint +//! records the ids it freed as a quarantine entry for `g`, and the allocator +//! skips every id of an entry that is in force: one whose generation is above +//! some pinned generation. Skipped ids stay on the free list, so a crash or a +//! reopen (which has no pins) loses nothing and reuses them at once. +//! +//! An entry is dropped as soon as no pinned generation is below it: at publish +//! when nothing older is pinned, otherwise when the last such pin is released. +//! +//! Lock order: `FactData`, then this. Pins are taken and entries recorded +//! 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. + +use std::collections::{BTreeMap, HashSet}; +use std::sync::{Arc, Mutex, MutexGuard}; + +#[derive(Default)] +struct State { + /// Generation → open pins on it. + pinned: BTreeMap, + /// Generation `g` → ids the checkpoint publishing `g` freed. + quarantine: BTreeMap>, +} + +impl State { + /// Drop the entries no pin needs: those at or below the lowest pinned + /// generation, or all of them when nothing is pinned. + fn prune(&mut self) { + match self.pinned.keys().next().copied() { + Some(lowest) => self.quarantine.retain(|&g, _| g > lowest), + None => self.quarantine.clear(), + } + } +} + +/// The open pins of one database and the quarantine entries they keep. +#[derive(Default)] +pub(crate) struct Pins { + state: Mutex, +} + +impl Pins { + pub(crate) fn new() -> Arc { + Arc::new(Pins::default()) + } + + /// A poisoned lock still holds consistent maps: every update below is + /// one map operation followed by `prune`, and neither panics. + fn lock(&self) -> MutexGuard<'_, State> { + self.state.lock().unwrap_or_else(|e| e.into_inner()) + } + + /// Pin `generation` until the returned guard is dropped. The caller holds + /// `FactData`'s lock and `generation` is the active one. + pub(crate) fn pin(self: &Arc, generation: u64) -> GenerationPin { + let mut s = self.lock(); + let n = s.pinned.entry(generation).or_insert(0); + *n = n.saturating_add(1); + GenerationPin { + pins: Arc::clone(self), + generation, + } + } + + /// Record the ids freed by the checkpoint that publishes `generation`. + /// Kept only while a lower generation is pinned. The caller holds + /// `FactData`'s write lock. + pub(crate) fn record(&self, generation: u64, freed: Vec) { + let mut s = self.lock(); + if freed.is_empty() || !s.pinned.keys().any(|&p| p < generation) { + return; + } + s.quarantine.entry(generation).or_default().extend(freed); + } + + /// Every id of an entry in force: the allocator must not hand these out. + pub(crate) fn in_force(&self) -> HashSet { + self.lock().quarantine.values().flatten().copied().collect() + } + + fn release(&self, generation: u64) { + let mut s = self.lock(); + if let Some(n) = s.pinned.get_mut(&generation) { + *n = n.saturating_sub(1); + if *n == 0 { + s.pinned.remove(&generation); + } + } + s.prune(); + } + + /// The number of open pins (tests). + #[cfg(test)] + pub(crate) fn count(&self) -> usize { + self.lock().pinned.values().sum() + } +} + +/// Keeps the pages of one committed generation from being reused; released +/// on drop. +pub(crate) struct GenerationPin { + pins: Arc, + generation: u64, +} + +impl Drop for GenerationPin { + fn drop(&mut self) { + self.pins.release(self.generation); + } +} + +#[cfg(test)] +mod tests { + use super::*; + + fn ids(pins: &Pins) -> Vec { + let mut v: Vec = pins.in_force().into_iter().collect(); + v.sort_unstable(); + v + } + + #[test] + fn entry_is_in_force_while_a_lower_generation_is_pinned() { + let pins = Pins::new(); + let pin = pins.pin(3); + pins.record(4, vec![10, 11]); + pins.record(5, vec![12]); + assert_eq!(ids(&pins), vec![10, 11, 12]); + drop(pin); + assert!(ids(&pins).is_empty(), "released with the last pin"); + assert_eq!(pins.count(), 0); + } + + #[test] + fn entry_with_no_older_pin_is_dropped_at_once() { + let pins = Pins::new(); + pins.record(2, vec![7]); + assert!(ids(&pins).is_empty(), "nothing pinned"); + let _pin = pins.pin(2); + pins.record(2, vec![8]); + assert!( + ids(&pins).is_empty(), + "a pin on the same generation needs none" + ); + } + + #[test] + fn two_pins_release_in_either_order() { + for older_first in [true, false] { + let pins = Pins::new(); + let old = pins.pin(3); + pins.record(4, vec![20]); + let new = pins.pin(4); + pins.record(5, vec![21]); + assert_eq!(ids(&pins), vec![20, 21]); + if older_first { + drop(old); + assert_eq!(ids(&pins), vec![21], "entry 4 is needed by no pin"); + drop(new); + } else { + drop(new); + assert_eq!(ids(&pins), vec![20, 21], "pin 3 still needs both"); + drop(old); + } + assert!(ids(&pins).is_empty()); + } + } + + #[test] + fn two_pins_on_one_generation_both_hold_it() { + let pins = Pins::new(); + let a = pins.pin(1); + let b = pins.pin(1); + pins.record(2, vec![5]); + drop(a); + assert_eq!(ids(&pins), vec![5]); + drop(b); + assert!(ids(&pins).is_empty()); + } +} diff --git a/tests/fact_log_test.rs b/tests/fact_log_test.rs index 16025cda30..22237bf246 100644 --- a/tests/fact_log_test.rs +++ b/tests/fact_log_test.rs @@ -452,30 +452,47 @@ fn wal_exists(path: &Path) -> bool { Path::new(&p).exists() } +/// Checkpoints that rewrite the leaves of entity e1 and free the old ones. +fn churn(db: &Minigraf, rounds: usize) { + for i in 0..rounds { + let facts: String = (0..50) + .map(|j| format!("[#uuid \"{}\" :churn/n {}]", uuid(0), i * 100 + j)) + .collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + db.checkpoint().unwrap(); + } +} + #[test] -fn checkpoint_and_rebuild_are_api_013_while_a_log_is_open() { +fn checkpoint_and_rebuild_run_while_a_log_is_open() { let dir = tempfile::tempdir().unwrap(); let path = dir.path().join("pin.graph"); let db = file_db(&path); let model = write(&db, Some(3)); - let log = db.fact_log(&FactFilter::new()).unwrap(); + // Window 2: tx order reads the committed index again for every window, + // after each checkpoint below. + let mut log = db.fact_log(&FactFilter::new().window(2)).unwrap(); + let mut records = log.next_batch(1).unwrap().expect("a record"); - let err = db.checkpoint().expect_err("checkpoint must be refused"); - assert_eq!(err.code(), "API-013"); - let err = db.rebuild_indexes().expect_err("rebuild must be refused"); - assert_eq!(err.code(), "API-013"); - assert!(db.verify().unwrap().is_ok(), "verify still runs"); - assert!(wal_exists(&path), "nothing was checkpointed"); - - // The refused calls left the log intact. - let records: Vec = log.map(Result::unwrap).collect(); - assert_eq!(records.len(), model.len()); - - // Reading to the end released the database. db.checkpoint().unwrap(); - assert!(!wal_exists(&path)); - let rows: Vec = read(&db, &FactFilter::new(), 100).iter().map(row).collect(); + assert!(!wal_exists(&path), "checkpoint ran"); + churn(&db, 6); + db.rebuild_indexes().unwrap(); + churn(&db, 3); + assert!( + db.verify().unwrap().is_ok(), + "verify clean with the log open" + ); + + // The log still returns the database as it was when it opened. + while let Some(batch) = log.next_batch(3).unwrap() { + records.extend(batch); + churn(&db, 1); + } + assert_tx_ordered(&records); + let rows: Vec = records.iter().map(row).collect(); assert_eq!(sorted(rows), sorted(model)); + assert!(db.verify().unwrap().is_ok()); } #[test] @@ -487,42 +504,54 @@ fn checkpoint_with_nothing_to_write_is_allowed_while_a_log_is_open() { db.checkpoint().unwrap(); } +fn file_len(path: &Path) -> u64 { + std::fs::metadata(path).unwrap().len() +} + #[test] -fn close_releases_the_database() { +fn pages_held_by_a_log_are_reused_after_close() { let dir = tempfile::tempdir().unwrap(); let path = dir.path().join("close.graph"); let db = file_db(&path); - write(&db, None); + write(&db, Some(steps().len())); + churn(&db, 4); + // Growth over the same rounds of writes: with no log, with a log open, + // and after it closes. + let grow = |db: &Minigraf| { + let before = file_len(&path); + churn(db, 4); + file_len(&path) - before + }; + let free = grow(&db); let mut log = db.fact_log(&FactFilter::new()).unwrap(); assert!(log.next_batch(1).unwrap().is_some()); + let held = grow(&db); log.close(); - db.checkpoint().unwrap(); - assert!(!wal_exists(&path)); + let after = grow(&db); + eprintln!("growth: free {free}, held {held}, after {after}"); + assert!(held > free, "pages the log may read are not reused"); + assert!(after < held, "after close they are reused"); + assert!(db.verify().unwrap().is_ok()); } #[test] -fn auto_checkpoint_waits_for_the_log() { +fn auto_checkpoint_runs_while_a_log_is_open() { let dir = tempfile::tempdir().unwrap(); let path = dir.path().join("auto.graph"); let opts = OpenOptions::default().wal_checkpoint_threshold(2); let db = OpenOptions::path(opts, &path).open().unwrap(); db.execute(r#"(transact [[:a :n 1]])"#).unwrap(); let log = db.fact_log(&FactFilter::new()).unwrap(); - for i in 2..6 { + for i in 2..=6 { db.execute(&format!("(transact [[:a :n {i}]])")).unwrap(); } - assert!(wal_exists(&path), "auto-checkpoint must wait"); - drop(log); - db.execute(r#"(transact [[:a :n 6]])"#).unwrap(); - assert!( - !wal_exists(&path), - "the first write after close checkpoints" - ); + assert!(!wal_exists(&path), "auto-checkpoint ran"); + assert_eq!(log.count(), 1, "the log keeps its snapshot"); assert_eq!(read(&db, &FactFilter::new(), 100).len(), 6); } #[test] -fn write_transaction_commit_defers_auto_checkpoint() { +fn write_transaction_commit_checkpoints_while_a_log_is_open() { let dir = tempfile::tempdir().unwrap(); let path = dir.path().join("wtx.graph"); let opts = OpenOptions::default().wal_checkpoint_threshold(1); @@ -531,11 +560,88 @@ fn write_transaction_commit_defers_auto_checkpoint() { let mut tx = db.begin_write().unwrap(); tx.execute(r#"(transact [[:a :n 1]])"#).unwrap(); tx.commit().unwrap(); - assert!(wal_exists(&path), "commit's auto-checkpoint must wait"); - drop(log); + assert!(!wal_exists(&path), "commit's auto-checkpoint ran"); + assert_eq!(log.count(), 0, "the log keeps its snapshot"); assert_eq!(read(&db, &FactFilter::new(), 100).len(), 1); } +/// Logs opened while one thread writes transactions of `PER_TX` facts and +/// checkpoints see whole transactions, and every one up to the last they see. +#[test] +fn log_opened_during_writes_and_checkpoints_sees_whole_transactions() { + const PER_TX: usize = 7; + const TXS: usize = 60; + let dir = tempfile::tempdir().unwrap(); + let db = file_db(&dir.path().join("race.graph")); + let writer = { + let db = db.clone(); + std::thread::spawn(move || { + for t in 0..TXS { + let facts: String = (0..PER_TX) + .map(|j| format!("[:w :n {}]", t * 100 + j)) + .collect(); + if t % 3 == 0 { + let mut tx = db.begin_write().unwrap(); + tx.execute(&format!("(transact [{facts}])")).unwrap(); + tx.commit().unwrap(); + } else { + db.execute(&format!("(transact [{facts}])")).unwrap(); + } + if t % 4 == 3 { + db.checkpoint().unwrap(); + } + } + }) + }; + let mut opened = 0; + loop { + let done = writer.is_finished(); + let records: Vec = read(&db, &FactFilter::new().window(5), 4); + let mut per_tx = std::collections::BTreeMap::::new(); + for r in &records { + *per_tx.entry(r.tx_count).or_default() += 1; + } + assert!( + per_tx.values().all(|&n| n == PER_TX), + "a partial transaction" + ); + let max = per_tx.keys().next_back().copied().unwrap_or(0); + assert_eq!(per_tx.len() as u64, max, "a transaction is missing"); + opened += 1; + if done { + assert_eq!(max, TXS as u64); + break; + } + } + writer.join().unwrap(); + assert!(opened > 1); +} + +#[test] +fn in_memory_log_opens_while_another_thread_writes() { + let db = Minigraf::in_memory().unwrap(); + db.execute(r#"(transact [[:a :n 1]])"#).unwrap(); + let (held_tx, held_rx) = std::sync::mpsc::channel(); + let (go_tx, go_rx) = std::sync::mpsc::channel::<()>(); + let writer = { + let db = db.clone(); + std::thread::spawn(move || { + let mut tx = db.begin_write().unwrap(); + tx.execute(r#"(transact [[:a :n 2]])"#).unwrap(); + held_tx.send(()).unwrap(); + go_rx.recv().unwrap(); + tx.commit().unwrap(); + }) + }; + held_rx.recv().unwrap(); + // The write lock is held on the other thread; the log opens anyway. + let log = db.fact_log(&FactFilter::new()).unwrap(); + go_tx.send(()).unwrap(); + writer.join().unwrap(); + assert_eq!(log.count(), 1, "the uncommitted write is not in the log"); + assert_eq!(read(&db, &FactFilter::new(), 10).len(), 2); +} + #[test] fn fact_log_on_a_write_transaction_thread_is_int_001() { let db = Minigraf::in_memory().unwrap(); From eb0aab974dabb59a9fb28865959f29eb6d2cc93a Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 13 Oct 2026 20:57:07 +0530 Subject: [PATCH 2/2] test(fact_log): close-time checkpoint runs while a log outlives its handle (#543) Also notes at the browser release point that quarantined ids must be withheld once browser reads pin (plan step 8, Codex review). Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- CLAUDE.md | 2 +- docs/TEST_COVERAGE.md | 2 +- src/storage/persistent_facts.rs | 3 +++ tests/fact_log_test.rs | 20 ++++++++++++++++++++ 4 files changed, 25 insertions(+), 2 deletions(-) diff --git a/CLAUDE.md b/CLAUDE.md index 8c0d7c8f35..65243e5a75 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -202,7 +202,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1457 tests** (1447 passing, 10 ignored; unit + integration + doc). +**1458 tests** (1448 passing, 10 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index d9d99706a0..f5debf68ce 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-13 with `cargo test --quiet` -**Result**: 1,447 passing tests and 10 ignored tests (1,457 total) +**Result**: 1,448 passing tests and 10 ignored tests (1,458 total) This covers 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. It otherwise still covers 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). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (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 at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). `tests/property_test.rs` writes random histories (batched transacts, retracts, write transactions, checkpoints) in memory and to a file, and compares random queries (one to three joined patterns, `not` or `not-join`, a comparison predicate, `:as-of`, `:valid-at` or `:any-valid-time`) with a reference evaluator, on the open file and after a reopen; a query error fails the test (#386). `tests/crash_kill_test.rs` kills a child process running a seeded workload (multi-valued batches, batched retracts, five checkpoint modes) at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries and `verify`, again after a second reopen and after a checkpoint plus reopen (#384). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Page-count tests (#497) check that a CRC-valid meta whose `page_count` is past the end of the file (one page past, 2^50, `u64::MAX`; with the other slot valid or damaged; with or without a WAL) and a file cut short by one page, three pages or down to three pages are `STG-044` at open, with the file unchanged and not grown, while a `page_count` exactly at the end opens; that a checkpoint whose pages did not all reach the backend fails with `INT-049` before writing its meta, and the file reopens at the previous generation; and that `verify` at a meta counting pages past the end reports `STG-044` without scanning to that count. Through `Minigraf` (`tests/integrity_test.rs`), a file truncated by one or three pages and a file whose meta was rewritten with `page_count` 2^50 and a valid CRC are `STG-044` read-write and read-only, with no WAL created and the file length unchanged. The `file_header` fuzz input from #497 is a corpus seed. A sub-page test (#506, `tests/integrity_test.rs`) checks that a file of 1 to 4,095 bytes is `STG-045` read-write and read-only, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes writes when it is a prefix of the first meta page or all zeros; a file-backend unit test checks that `partial_page` returns the bytes past the last whole page. The `corrupt_file` fuzzer no longer skips files under one page: they must fail to open or open empty, and the #506 input is a corpus seed. Damaged v7 fact page tests (#496) check that a page in the counted fact range whose type byte is anything but the fact-page type (zero, `0x01`, the v2.x B+tree types, `0xFF`, a zeroed page; first and last page) is `STG-014` rather than skipped, while a range derived from the first index root skips only v2.x B+tree pages; that opening such a v7 file read-write or read-only fails with `STG-014` and writes nothing; and, in `tests/migration_matrix_test.rs`, that the golden `v7_basic.graph` with page 1's type byte changed or page 1 overwritten with noise fails both opens with the file unchanged and no WAL created. Both inputs are `fact_page` corpus seeds. Merged from the v2.x line: `tests/edge_cases_test.rs` checks the same refusal and acceptance through `Minigraf::open` on a database checkpointed twice (#506). Torn-WAL-tail tests (#513) check that opening a WAL writer cuts off a partial last entry (cut in the checksum, the header or the payload) or an entry with a bad checksum and everything after it, then appends where replay reaches, and leaves an intact WAL byte for byte; that an append that fails part-way makes every later append `WAL-007` while a rejected oversize fact (`WAL-003`, nothing written) does not; through `Minigraf`, that the failed transaction is not applied, later `transact` and `commit` are `WAL-007`, and a `checkpoint()` makes writes work again; and, in `tests/wal_test.rs`, that a commit made after reopening a crash-left WAL with each kind of torn tail survives a second crash. The fault matrix (#390, `src/fault_matrix.rs`) drives a test-only fault plan through the real file backend, WAL and directory fsync: an EIO, a short or torn write (1, 40 and 4,095 bytes), a full disk that keeps failing every later write, a failed fsync, and a failed fsync that also loses the writes since the last good one ("fsyncgate"), each at every write or sync call of a transact, a transact that creates the WAL, an automatic checkpoint, `checkpoint()`, the close-time checkpoint and `rebuild_indexes()`, on a database committed over two checkpoints with multi-valued, retracted and long values and entries pending in the WAL. After each fault, the handle holds the old facts or those plus the whole transaction, never part of one; after a failed checkpoint another is `STG-046`; a later write succeeds or is `WAL-007`/`STG-046`; a kill and reopen gives exactly the handle's facts, plus the failed transaction whole or not at all, and `verify` finds nothing; and a commit after recovery survives another kill. Two more tests fill the disk halfway through a checkpoint (`STG-046`, reads unchanged, reopen intact), and fail the fsync after a checkpoint's meta write and then retry the checkpoint, crashing at each of its writes: the retry is refused and every reopen is intact (without the refusal, a reopen hits `STG-029`). Unit tests check the fault plan's counting, and that a `rebuild_indexes` refused with `STG-041` leaves the handle usable. Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `API-011` from `transact` and from `WriteTransaction::execute`, and a later statement's window committed when two statements of a `WriteTransaction` give one fact different windows. Window-validation tests (#436) check that `check_valid_windows` rejects an empty window, an inverted one, and a `:valid-to` at or before the transaction time when `:valid-from` is left out, but not retractions; that `execute` rejects each such `transact` (both bounds, equal bounds, `:valid-to` only, a per-fact bound inverting the transaction's window) with `API-019` without writing or taking a `tx_count`, in memory, checkpointed and after reopen; that `tx.execute()` rejects them and the transaction still commits its other statements; that `commit()` rejects a default `valid_from` that has passed the `:valid-to` by commit time; and that `FactStorage::transact_batch` takes no `tx_count` on rejection. Statement-order tests (#477, `tests/statement_order_test.rs`) run every mix of two statements on one fact inside a `WriteTransaction` (retract then assert, assert then retract, two retracts, two windows, after a committed assertion and on an empty database) and check that reads inside the transaction and the committed rows agree, in memory, checkpointed and after reopen; that other facts of an overridden statement survive; that the commit is one transaction without the overridden records; and that two windows in one statement are `API-011` from `tx.execute()` while the rest commits. A unit test checks the commit collapse keeps each fact's newest statement in order. A log-writer test checks that an inverted window is `API-019`, a second window of a fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction `API-020` in either order, each leaving the writer usable and the output exact, while duplicate retractions, identical repeats and the same fact in the next transaction are accepted. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011`, a retraction of an asserted fact in one transaction `API-020`, an empty window `API-019` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Query-validation tests (#406, #414) check that a plain `:find` variable or a window function's argument, `:partition-by` or `:order-by` variable that no `:where` clause binds (including `?_` wildcards) is `PRS-080` from both `execute()` and `prepare()`, naming the variable, while variables bound by a pattern, an attribute position, a rule call, an expression binding, an `or-join`, every branch of an `or`, a pseudo-attribute or a window spec are accepted, and bind slots are not mistaken for `:find` variables; and that an unknown aggregate is `QRY-010` and an unknown window function `QRY-011` on an empty database, when no row matches, when rows match, through a rule query and through a prepared query, while a registered UDF in either position returns an empty result on an empty database. Coverage-gate tests (#396) check that replay stops at a WAL entry whose first fact is longer than 10 MB or that claims more than 1M facts, that a WAL writer cannot be opened in a missing directory, and that a failed cut of a torn WAL tail fails the open and leaves the file as it was; that a short v7 page and a slot past the record count are `INT-024`; that a migration backup meta of another generation or file length is not used (`STG-032`, file unchanged), and a torn first meta with data in page 1 is `STG-032`, not a new file; that `save` with nothing pending writes nothing, `into_backend` saves pending facts, and `rebuild_indexes` with nothing checkpointed commits the pending facts; and that unsorted or repeated B+tree input and a stored key inserted with another value are `INT-049`, a tree pointer to a free-list page is `STG-013` from `get`, a leaf walk and a copy-on-write insert, and the read-only `MutexStorageBackend` refuses writes, syncs and close. A page-cache test holds two threads in the backend read so both miss the same page, and checks that both get the one cached copy; before it, that path ran only when the scheduler happened to race the threads, and the gate flapped. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 956 passing; ten that spawn threads or a child process are ignored on WASI. These are not counted above. A WAL test checks that a checkpoint with no facts to flush still removes a WAL whose entries are all already in the file, and the golden-corpus test now requires the WAL to be gone after a checkpoint for the `stale_wal` fixtures too (#457). A WAL test checks that closing a handle opened with `wal_checkpoint_threshold(usize::MAX)`, in both sync modes, leaves the `.graph` file byte for byte as it was and keeps the WAL, whose entries replay on the next open, and a unit test closes an in-memory handle under the same setting (#476). A recursive-rule test checks that a rule query on a database with more live facts than `max_results` returns its answer, with a bound and with a free first argument, and that a query deriving more facts than its `:max-results` is still `INT-020` (#528). A log-writer test runs the online backup from `docs/DURABILITY.md`: it copies a read-write handle with an uncheckpointed transaction through `fact_log` and `LogWriter` while another thread writes past the automatic checkpoint threshold, and checks that the copy verifies clean, holds exactly the records the log returned and the counter read after the log opened, and that every concurrent write reaches the source's file once the log is dropped (#398). diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index d7cb6a55a2..d547c56617 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -490,6 +490,9 @@ impl PersistentFactStorage { self.dirty = false; self.failed = false; let reader = self.activate(new_meta); + // `listed` includes quarantined ids. Nothing pins a generation on + // the browser yet (it has no fact log); before its cursors pin, ids in + // force must be withheld here (#543 plan step 8). #[cfg(all(target_arch = "wasm32", feature = "browser"))] { self.released = listed; diff --git a/tests/fact_log_test.rs b/tests/fact_log_test.rs index 22237bf246..7fdffed5ba 100644 --- a/tests/fact_log_test.rs +++ b/tests/fact_log_test.rs @@ -673,3 +673,23 @@ fn log_is_send_and_outlives_the_database_handle() { let rows: Vec = read(&db, &FactFilter::new(), 100).iter().map(row).collect(); assert_eq!(sorted(rows), sorted(model)); } + +#[test] +fn close_time_checkpoint_runs_while_a_log_outlives_the_handle() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("close_cp.graph"); + let model = { + let db = Minigraf::open(&path).unwrap(); + let model = write(&db, Some(4)); + let log = db.fact_log(&FactFilter::new().window(2)).unwrap(); + drop(db); // checkpoints the pending writes + assert!(!wal_exists(&path), "close-time checkpoint ran"); + let rows: Vec = log.map(|r| row(&r.unwrap())).collect(); + assert_eq!(sorted(rows), sorted(model.clone())); + model + }; + let db = Minigraf::open(&path).unwrap(); + let rows: Vec = read(&db, &FactFilter::new(), 100).iter().map(row).collect(); + assert_eq!(sorted(rows), sorted(model)); + assert!(db.verify().unwrap().is_ok()); +}