From bd034d586a7c8571fd910f37fd12cced5ff8b623 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 6 Oct 2026 20:09:14 +0530 Subject: [PATCH] feat: Minigraf::verify and rebuild_indexes (#373) Page checksums catch torn and rotted pages, but not pages that are valid and say the wrong thing. verify() walks every committed page and reports one structured error per finding: an index whose facts differ from EAVT (compared by an order-independent digest, no per-fact memory), keys out of order or a page reached twice, DICT maps that disagree or ids with no entry, and leaked or doubly used pages. rebuild_indexes() rebuilds EAVT, AEVT, AVET and VAET from an intact index that agrees with another one (or the only intact one), derives the free list again, and commits like a checkpoint, including pending facts. It writes only pages the active meta does not reference, so a crash at any point keeps the previous checkpoint. With no usable source or a damaged DICT it fails with STG-041 and writes nothing. New codes STG-038..STG-041. Design: docs/superpowers/specs/2026-10-06-verify-rebuild-indexes-design.md Refs #373, #383 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- CHANGELOG.md | 4 + CLAUDE.md | 5 +- README.md | 2 +- ROADMAP.md | 2 +- docs/ERROR_REFERENCE.md | 63 +- docs/TEST_COVERAGE.md | 4 +- ...026-10-06-verify-rebuild-indexes-design.md | 156 +++++ src/db.rs | 145 +++- src/error.rs | 36 + src/lib.rs | 2 +- src/storage/mod.rs | 1 + src/storage/persistent_facts.rs | 574 +++++++++++++++- src/storage/verify.rs | 620 ++++++++++++++++++ tests/integrity_test.rs | 128 ++++ 14 files changed, 1718 insertions(+), 24 deletions(-) create mode 100644 docs/superpowers/specs/2026-10-06-verify-rebuild-indexes-design.md create mode 100644 src/storage/verify.rs create mode 100644 tests/integrity_test.rs diff --git a/CHANGELOG.md b/CHANGELOG.md index d236784da9..66e6e47958 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -17,6 +17,10 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **Size limits for file-backed databases:** a string value may be up to 4,068 bytes, whatever the rest of the fact, and an attribute name or keyword value up to 1,024 bytes. Both are checked when the transaction is written and fail with `WAL-003`, whose message now names the value. This replaces the 4,080-byte limit on a whole serialised fact (4,052 in earlier v3.0.0 development builds). In-memory databases have no limit. - **Formats v1–v6 are no longer readable.** Opening one fails with the new `STG-028`; open it once with Minigraf v2.x to upgrade it to v7 first. `STG-003` and `STG-004` are deprecated (no longer emitted, still registered, never reused). `STG-005` and `STG-006` message text changed. +### Added + +- **`Minigraf::verify()` and `Minigraf::rebuild_indexes()`** (#373). Page checksums turn a torn or rotted page into an error, but they cannot see a page that is valid and says the wrong thing. `verify()` walks every committed page and returns an `IntegrityReport` with one structured error per finding: an index that holds different facts than EAVT or a different count than the meta page (new `STG-038`), keys out of order or a page reached twice (new `STG-039`), dictionary maps that disagree (new `STG-040`), ids with no dictionary entry (`STG-036`), and leaked, doubly used or wrongly free pages (`STG-035`). It keeps no per-fact state: indexes are compared by an order-independent digest. `rebuild_indexes()` rebuilds EAVT, AEVT, AVET and VAET from an intact index that agrees with another one (or the only intact one), derives the free list again, and commits like a checkpoint, including uncheckpointed writes; a crash at any point leaves the previous checkpoint. If no index can serve as the source, or the dictionary is damaged, it fails with new `STG-041` and writes nothing. Both are Rust API only for now; the bindings follow. + ### Fixed - Two values of the same attribute written in one transaction are both returned by every query path. Previously only one came back, and entity-bound and attribute-bound queries could return different ones (#371, #287). diff --git a/CLAUDE.md b/CLAUDE.md index bed4d7914e..cc004da5d6 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -115,6 +115,7 @@ cargo run < demos/demo_negation.txt - `dict.rs`: `DictReader` (id ↔ UUID/ident, tx timestamps, long values) and `Encoder` (checkpoint-time id assignment and key building) - `value_pages.rs`: append-only value pages for strings over 64 bytes - `reader.rs`: `OnDiskReader` — covering reads of committed facts (`CommittedReader`) + - `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 - `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) @@ -137,7 +138,7 @@ cargo run < demos/demo_negation.txt 5. **`src/repl.rs`** — Interactive REPL; TTY-aware (suppresses prompts/banner for piped input) -6. **`src/db.rs`** — Public API: `Minigraf::open/execute/prepare/begin_write/checkpoint/save`, `WriteTransaction`, `OpenOptions::page_cache_size` +6. **`src/db.rs`** — Public API: `Minigraf::open/execute/prepare/begin_write/checkpoint/save/verify/rebuild_indexes`, `WriteTransaction`, `IntegrityReport`, `OpenOptions::page_cache_size` 7. **`src/wal.rs`** — Fact-level sidecar WAL, CRC32-protected entries, crash recovery @@ -193,7 +194,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1238 tests** (1229 passing, 9 ignored; unit + integration + doc). +**1248 tests** (1239 passing, 9 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/README.md b/README.md index fef7e6c2d4..a073eb4347 100644 --- a/README.md +++ b/README.md @@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1238 tests +cargo test # run 1248 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/ROADMAP.md b/ROADMAP.md index df8880166a..fd147f04a7 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -60,7 +60,7 @@ Scope — format and storage integrity: - covering byte-comparable keys with a dictionary and deduplicated long values, at about 142 bytes per fact (#433). The format is frozen for the golden-file corpus (#391). -- Index `verify` and public `rebuild_indexes()` (#373) +- Index `verify` and public `rebuild_indexes()` (#373; done on `v3`) - Net-assert on v8 keys before resolving facts, for O(live) point queries (#379) - `btree_page` fuzz target that reaches node decoding (#375) diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index f43a0464c6..55f0d8a8eb 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -146,6 +146,10 @@ with no `CodedError` anywhere in its chain. | STG-035 | Free-list inconsistency | Storage | | STG-036 | Dictionary entry missing | Storage | | STG-037 | Transaction with two timestamps | Storage | +| STG-038 | Index disagrees with the committed facts | Storage | +| STG-039 | Malformed tree | Storage | +| STG-040 | Dictionary inconsistency | Storage | +| STG-041 | Cannot rebuild indexes | Storage | | WAL-001 | Invalid WAL magic number | WAL | | WAL-002 | Unsupported WAL version | WAL | | WAL-003 | Value size exceeds maximum | WAL | @@ -2083,10 +2087,11 @@ See the [file format section in README](../README.md#file-format) for version hi **Error text**: `Free list is inconsistent: {}` -**Cause**: The chain of free-list pages loops, or holds a page id that is reserved or past the end of the file. +**Cause**: The chain of free-list pages loops, or holds a page id that is reserved or past the end of the file. `Minigraf::verify()` also reports here a free-list count that disagrees with the meta page, a page listed twice, a free page that is still in use, a page used twice, and pages that are neither free nor in use (leaked). **Resolution**: -- Restore from backup. +- Run `Minigraf::rebuild_indexes()`: it derives a new free list from the pages the rebuilt file uses. +- Restore from backup if the rebuild fails. **Scenario**: A corrupted free-list page whose `next` pointer points back at itself. @@ -2118,6 +2123,60 @@ See the [file format section in README](../README.md#file-format) for version hi --- +### STG-038 Index disagrees with the committed facts + +**Error text**: `Index {} disagrees with the committed facts: {}` + +**Cause**: `Minigraf::verify()` found an index whose pages are intact (every checksum passes) but whose contents are wrong: it holds a different number of entries or different facts than EAVT, EAVT's entry count differs from the meta page's fact count, an entry belongs to a transaction newer than the last checkpoint, or a key's long value does not match the stored value. Queries that use that index can return wrong or missing results. + +**Resolution**: +- Run `Minigraf::rebuild_indexes()`, which rebuilds all four indexes from an index that agrees with another one. +- Restore from backup if the rebuild fails with STG-041. + +**Scenario**: A bug or a lost write leaves AVET without some entries that EAVT and AEVT hold. + +--- + +### STG-039 Malformed tree + +**Error text**: `Tree {} is malformed: {}` + +**Cause**: `Minigraf::verify()` found a B+tree whose pages pass their checksums but whose structure is wrong: keys out of order, a key outside its parent's separator range, a page reached twice (from the same tree or from two trees), a tree deeper than any real tree can be, a node or an index key that does not decode. + +**Resolution**: +- If the tree is EAVT, AEVT, AVET or VAET, run `Minigraf::rebuild_indexes()`. +- If the tree is DICT, restore from backup: the dictionary holds the only copy of entity UUIDs and attribute names. + +**Scenario**: A misdirected write leaves an older, valid leaf where a newer one belonged, so two leaves of the tree overlap. + +--- + +### STG-040 Dictionary inconsistency + +**Error text**: `Dictionary is inconsistent: {}` + +**Cause**: `Minigraf::verify()` found DICT entries that disagree with each other or with the meta page: the UUID → entity-id and entity-id → UUID maps (or the ident maps) are not inverse, an id is not below the meta page's next id, an entry has the wrong shape or an unknown tag, or a long value does not match its hash. + +**Resolution**: +- Restore from backup. The dictionary cannot be rebuilt from the indexes. + +**Scenario**: A DICT leaf is replaced by an older valid copy, so an entity id maps to a UUID that maps to another id. + +--- + +### STG-041 Cannot rebuild indexes + +**Error text**: `Cannot rebuild indexes: {}` + +**Cause**: `Minigraf::rebuild_indexes()` found no index to rebuild from. A source must be an intact index (EAVT, AEVT or AVET) that agrees with another intact index, or the only intact one. This error also means the dictionary is damaged. The file is not modified. + +**Resolution**: +- Restore from backup. + +**Scenario**: EAVT, AEVT and AVET are all intact but each holds a different set of facts. + +--- + ## WAL — Write-Ahead Log Errors WAL errors relate to the sidecar `.wal` file written alongside the `.graph` file. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 76a0116e90..887fab5d27 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-10-06 with `cargo test --quiet` -**Result**: 1,229 passing tests and 9 ignored tests (1,238 total) +**Result**: 1,239 passing tests and 9 ignored tests (1,248 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. +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. 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). ### Covered Areas diff --git a/docs/superpowers/specs/2026-10-06-verify-rebuild-indexes-design.md b/docs/superpowers/specs/2026-10-06-verify-rebuild-indexes-design.md new file mode 100644 index 0000000000..e0d1ab4b70 --- /dev/null +++ b/docs/superpowers/specs/2026-10-06-verify-rebuild-indexes-design.md @@ -0,0 +1,156 @@ +# Integrity check and index rebuild — Design + +**Issue:** #373 (split out of #370), tracker #383 +**Milestone:** v3.0.0, branch `v3`, file format v8 (no format change) +**Builds on:** `2026-10-05-v8-storage-format-design.md` §4.2, §5.2, §7, §8, §11 + +## 1. Problem + +#373 was written against v7: fact pages were the source of truth and four reference +indexes pointed into them. An index that disagreed with the fact pages was silent. +Entity-bound queries returned `[]` and the file checksum still passed (#370). + +v8 removes fact pages. Every index entry holds the whole fact (D4), and EAVT, AEVT and +AVET each hold the complete fact set. Every page carries a CRC, its own id and its +generation, and every read checks them (G3). A torn or rotted page is therefore an error +on the read that hits it, never a wrong answer. + +Two gaps remain: + +1. **Logical damage is still silent.** A bug like #370's, or a lost write that leaves an + older valid page in place, gives pages that pass their CRC but say the wrong thing: + an index missing entries, two indexes that disagree, a leaked or doubly referenced + page, a key whose ids have no DICT entry. Only a full cross-check finds these. +2. **There is no repair.** The spec promises `rebuild_indexes` from EAVT or AEVT + (§5.2, §7). A checkpoint cannot repair: it inserts copy-on-write into the existing + trees and fails on a damaged leaf. + +## 2. API + +```rust +impl Minigraf { + /// Check the committed file. O(file). + pub fn verify(&self) -> Result; + /// Rebuild EAVT, AEVT, AVET and VAET from an intact index, then checkpoint. + pub fn rebuild_indexes(&self) -> Result<(), MinigrafError>; +} + +#[non_exhaustive] +pub struct IntegrityReport { + pub facts: u64, // EAVT entries + pub pages: u64, // pages checked + pub problems: Vec, +} +impl IntegrityReport { pub fn is_ok(&self) -> bool; } +``` + +- `verify` returns `Err` only when it cannot run (lock poisoned, I/O error reading the + meta). Damage goes into `problems`, one structured error per finding, so a caller can + match on codes. It keeps going after a finding where it can. +- It checks the committed file only. Pending facts live in memory and in the WAL, whose + entries carry their own CRC. +- In-memory databases have no committed pages: the report is empty and `is_ok()`. +- Both take the write lock, so the active meta and its pages cannot change underneath + them. Readers keep running. +- No Datalog or REPL syntax. Datalog stays the query language; SQLite's equivalent is a + pragma, not SQL. Bindings expose the two methods later (Python is Tier 1). +- No on-open sampling. v8 open is O(1) by design (G4), and per-page checks already turn + physical damage into errors. Sampling a few entries cannot find a missing one. + +## 3. Checks (`verify`) + +All against the active meta `M`. + +| # | check | code | +|---|---|---| +| C1 | Every node of the five trees verifies (CRC, id, generation, type), decodes, and is reached once across all trees | STG-029/030/031/013, STG-039 | +| C2 | Keys strictly increase across each tree (cursor walk) | STG-039 | +| C3 | Every index key decodes; VAET values are refs | STG-039 | +| C4 | EAVT count = `M.fact_count` | STG-038 | +| C5 | AEVT and AVET hold the same facts as EAVT; VAET holds exactly EAVT's ref facts | STG-038 | +| C6 | Every `tx_count` ≤ `M.last_checkpointed_tx_count` | STG-038 | +| C7 | Every eid (entity or ref) has 0x02, every iid (attribute or keyword) 0x04, every `tx_count` 0x05, every long value ref a 0x06 entry | STG-036 | +| C8 | 0x01 ↔ 0x02 and 0x03 ↔ 0x04 are inverse; ids below `next_eid` / `next_iid` | STG-040 | +| C9 | Each long value reads, and its hash and prefix match the key | STG-038 | +| C10 | Free list reads; ids distinct; count = `M.freelist_count`; free ∩ reachable = ∅; free ∪ reachable = `2..M.page_count` | STG-035 | + +**C5 without O(N) memory.** Each entry is mapped to its canonical EAVT key bytes and +hashed. Per index the check keeps `(count, Σ h₁, ⊕ h₂)` with two independent 64-bit +hashes. Equal digests mean equal multisets except with probability ≈ 2⁻⁶⁴ per pair. This +is a corruption check, not an adversarial one. The digest also tells which index is the +odd one out (§4). + +Memory: the reachable page set (8 B per page) and the DICT id sets (one entry per entity, +ident and transaction). No per-fact state. + +## 4. Rebuild (`rebuild_indexes`) + +**Choosing the source.** Walk EAVT, AEVT and AVET (C1–C3 and the C5 digest). An index +is *clean* if its walk finished without error. + +1. If two clean indexes have the same digest, the first of them (EAVT, AEVT, AVET order) + is the source. +2. Otherwise, if exactly one is clean, it is the source: it is the only copy left. +3. Otherwise fail with STG-041 and change nothing. + +DICT is not rebuilt: UUIDs and ident names exist only there. A damaged DICT is not +repairable by this operation (STG-036 / STG-041); restore from backup. + +**Writing.** Like `save()` (§8.3), with bulk builds instead of copy-on-write inserts: + +1. Encode pending facts on top of `M`'s dictionary (new ids, new long values), as `save()`. +2. Stream the source, re-encode each entry as a `KeyFact`, and produce keys for all four + indexes. Merge the pending index entries. Sort each list and `build_btree` it. +3. `cow_insert` the new DICT entries into `M`'s DICT. +4. New free list: `2..next_append` minus everything the new meta reaches (the four new + trees, DICT nodes, value pages through DICT 0x06). This re-derives the list from + scratch, so a leaked or wrong free list is repaired too. Chain pages are appended. +5. Sync, write meta `g+1` to the inactive slot, sync. Delete the WAL as a checkpoint does. + +**Crash safety (§8.1 invariant).** Pages for steps 1–3 come from `M`'s free list only if +it reads cleanly and is disjoint from every page that the DICT tree, the value pages and +the source tree use; otherwise every page is appended. Either way nothing the old meta +needs to reopen is overwritten before the commit. A crash reopens at `g` plus the WAL. + +**Cost.** O(N) time. Memory O(N) for the four key lists, as the v7 migration already +does. An external sort is not worth the code for a repair operation. The file can grow by +one copy of the indexes; those pages return to the free list at commit and are reused. + +## 5. Errors + +New codes, never recycled; `docs/ERROR_REFERENCE.md` updated: + +- **STG-038** `Index {} disagrees with the committed facts: {}` +- **STG-039** `Tree {} is malformed: {}` +- **STG-040** `Dictionary is inconsistent: {}` +- **STG-041** `Cannot rebuild indexes: {}` + +STG-035 (free list) and STG-036 (dictionary entry missing) gain the verify scenarios. + +## 6. Testing + +- Clean files of mixed facts (strings, long strings, refs, keywords, retractions, + several checkpoints) verify with no problems; `facts` and `pages` are exact. +- Each check fires on a targeted damage, built with page-level helpers: a leaf whose + entries are removed and resealed (C4/C5 for that index only), a dropped VAET entry, + swapped keys (C2), a node linked from two trees (C1), a leaked page and a free id that + is still referenced (C10), a deleted DICT entry (C7), a flipped bit (C1 / STG-029). +- Rebuild: after each damage above that leaves a source, `rebuild_indexes` succeeds, + `verify` is clean, and queries return the model's facts. Pending facts and WAL entries + made before the rebuild survive it and the WAL is gone. +- Source choice: EAVT damaged → AEVT; EAVT and AEVT disagree with AVET agreeing with one; + all three disagree → STG-041 with the file unchanged. +- Crash at every write and sync of a rebuild (FaultInjectingBackend): reopen gives + either the old or the rebuilt state, never a loss. +- Space accounting (`assert_space_accounted`) holds after every rebuild. + +## 7. Philosophy + +Aligned: reliability over features, single file, no format change, no dependency, no +configuration. Two methods, like SQLite's `integrity_check` and `REINDEX`. + +## 8. Out of scope + +- Recovering at generation `g` after STG-033 (§4.1.1): an open option, separate issue. +- Rebuilding DICT, vacuum, salvage of individual pages. +- Browser (`BrowserDb`) and binding exposure: follow-ups. diff --git a/src/db.rs b/src/db.rs index 841b9a51fc..cd2edb2ed6 100644 --- a/src/db.rs +++ b/src/db.rs @@ -282,6 +282,27 @@ enum WriteContext { }, } +// ─── IntegrityReport ────────────────────────────────────────────────────────── + +/// The result of [`Minigraf::verify`]. +#[derive(Debug, Default)] +#[non_exhaustive] +pub struct IntegrityReport { + /// Facts in the committed file (EAVT entries). + pub facts: u64, + /// Pages checked. + pub pages: u64, + /// One structured error per finding; empty when the file is intact. + pub problems: Vec, +} + +impl IntegrityReport { + /// True if no problem was found. + pub fn is_ok(&self) -> bool { + self.problems.is_empty() + } +} + // ─── Inner ──────────────────────────────────────────────────────────────────── struct Inner { @@ -731,6 +752,98 @@ impl Minigraf { Self::do_checkpoint(&self.inner.fact_storage, &mut ctx) } + // ── Integrity ──────────────────────────────────────────────────────────── + + /// Check the committed database file for damage that page checksums cannot + /// see. + /// + /// Every page read already checks its checksum, id and generation, so a + /// torn or rotted page is an error on the read that hits it. `verify` looks + /// for logical damage: an index holding different facts than EAVT, keys + /// out of order, an id with no dictionary entry, a page that is leaked, + /// listed free while in use, or used twice. Each finding is one structured + /// error in [`IntegrityReport::problems`] (codes STG-035, STG-036, STG-038, + /// STG-039, STG-040, or a page read error). + /// + /// Reads every page: O(file). Uncheckpointed writes are not checked here; + /// they live in memory and in the WAL, whose entries carry their own CRC. + /// Holds the write lock, so writes and checkpoints wait; queries keep + /// running. In-memory databases have no committed pages and always pass. + /// + /// # Errors + /// + /// Returns an error only if the check cannot run (for example, the write + /// lock is poisoned). Damage is reported in the returned report. + pub fn verify(&self) -> Result { + self.verify_inner().map_err(MinigrafError::from) + } + + fn verify_inner(&self) -> Result { + let ctx = self + .inner + .write_lock + .lock() + .map_err(|_| err_coded!(ErrorCode::Api001))?; + match &*ctx { + WriteContext::Memory => Ok(IntegrityReport::default()), + #[cfg(not(target_arch = "wasm32"))] + WriteContext::File { pfs, .. } => { + let f = pfs.verify()?; + Ok(IntegrityReport { + facts: f.facts, + pages: f.pages, + problems: f.problems.into_iter().map(MinigrafError::from).collect(), + }) + } + } + } + + /// Rebuild the four indexes (EAVT, AEVT, AVET, VAET) from an intact one, + /// and checkpoint. + /// + /// Use this when [`verify`](Self::verify) reports index damage (STG-038, + /// STG-039 on an index tree, a page read error inside an index, or a + /// free-list problem, STG-035). EAVT, AEVT and AVET each hold every fact. + /// The source is the first of them (in that order) that is intact and + /// agrees with another intact one, or else the only intact one. The free + /// list is derived again from the pages the rebuilt file uses. + /// + /// The rebuild commits like a checkpoint: uncheckpointed writes are + /// included, the WAL is deleted afterwards, and a crash at any point leaves + /// the previous checkpoint intact. It takes O(facts) time and memory, and + /// the file may grow by one copy of the indexes; the old pages are reused + /// by later checkpoints. No-op for in-memory databases. + /// + /// # Errors + /// + /// - STG-041 if no index can serve as the source, or the dictionary is + /// damaged. The file is not modified; restore from backup. + /// - An I/O error from the rebuild or the WAL delete. + pub fn rebuild_indexes(&self) -> Result<(), MinigrafError> { + self.rebuild_indexes_inner().map_err(MinigrafError::from) + } + + fn rebuild_indexes_inner(&self) -> Result<()> { + let mut ctx = self + .inner + .write_lock + .lock() + .map_err(|_| err_coded!(ErrorCode::Api001))?; + match &mut *ctx { + WriteContext::Memory => Ok(()), + #[cfg(not(target_arch = "wasm32"))] + WriteContext::File { + pfs, + wal, + db_path, + wal_entry_count, + } => { + pfs.rebuild_indexes()?; + Self::delete_wal(wal, db_path, wal_entry_count) + } + } + } + /// Returns the current monotonic transaction counter. /// /// This is the value that `:as-of N` compares against. After a successful @@ -775,24 +888,30 @@ impl Minigraf { // the replayed facts would never reach the main file. pfs.force_dirty(); pfs.save()?; - - // Derive WAL path and delete the sidecar. - let wal_path = Self::wal_path_for(db_path); - - // Close the WAL writer (drop it) before deleting the file. - *wal = None; - - if wal_path.exists() { - WalWriter::delete_file(&wal_path)?; - } - - // WAL writer will be recreated lazily on the next write. - *wal_entry_count = 0; + Self::delete_wal(wal, db_path, wal_entry_count)?; } } Ok(()) } + /// Delete the WAL sidecar after a commit made its entries durable in the + /// main file. The writer is recreated lazily on the next write. + #[cfg(not(target_arch = "wasm32"))] + fn delete_wal( + wal: &mut Option, + db_path: &Path, + wal_entry_count: &mut usize, + ) -> Result<()> { + let wal_path = Self::wal_path_for(db_path); + // Close the WAL writer (drop it) before deleting the file. + *wal = None; + if wal_path.exists() { + WalWriter::delete_file(&wal_path)?; + } + *wal_entry_count = 0; + Ok(()) + } + /// Parse and plan a query once; bind slots (`$name`) are left unresolved. /// /// Returns a [`crate::query::datalog::prepared::PreparedQuery`] that can be executed diff --git a/src/error.rs b/src/error.rs index 0e4c392908..18567c53cc 100644 --- a/src/error.rs +++ b/src/error.rs @@ -178,6 +178,10 @@ pub(crate) enum ErrorCode { Stg035, Stg036, Stg037, + Stg038, + Stg039, + Stg040, + Stg041, Wal001, Wal002, Wal003, @@ -1012,6 +1016,30 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "Transaction {} has two timestamps: {} and {}", ErrorCategory::Storage, ), + ( + ErrorCode::Stg038, + "STG-038", + "Index {} disagrees with the committed facts: {}", + ErrorCategory::Storage, + ), + ( + ErrorCode::Stg039, + "STG-039", + "Tree {} is malformed: {}", + ErrorCategory::Storage, + ), + ( + ErrorCode::Stg040, + "STG-040", + "Dictionary is inconsistent: {}", + ErrorCategory::Storage, + ), + ( + ErrorCode::Stg041, + "STG-041", + "Cannot rebuild indexes: {}", + ErrorCategory::Storage, + ), ( ErrorCode::Wal001, "WAL-001", @@ -1836,6 +1864,10 @@ mod tests { | ErrorCode::Stg035 | ErrorCode::Stg036 | ErrorCode::Stg037 + | ErrorCode::Stg038 + | ErrorCode::Stg039 + | ErrorCode::Stg040 + | ErrorCode::Stg041 | ErrorCode::Wal001 | ErrorCode::Wal002 | ErrorCode::Wal003 @@ -2037,6 +2069,10 @@ mod tests { ErrorCode::Stg035, ErrorCode::Stg036, ErrorCode::Stg037, + ErrorCode::Stg038, + ErrorCode::Stg039, + ErrorCode::Stg040, + ErrorCode::Stg041, ErrorCode::Wal001, ErrorCode::Wal002, ErrorCode::Wal003, diff --git a/src/lib.rs b/src/lib.rs index 80ce28b87d..2d733257f5 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -90,7 +90,7 @@ pub mod browser; #[cfg(not(target_arch = "wasm32"))] pub use db::OpenOptionsWithPath; -pub use db::{Minigraf, OpenOptions, SyncMode, WriteTransaction}; +pub use db::{IntegrityReport, Minigraf, OpenOptions, SyncMode, WriteTransaction}; pub use error::{ErrorCategory, MinigrafError}; pub use repl::Repl; diff --git a/src/storage/mod.rs b/src/storage/mod.rs index bd1ee14bdf..07bc1918d2 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -20,6 +20,7 @@ pub(crate) mod page; pub mod persistent_facts; pub(crate) mod reader; pub(crate) mod value_pages; +pub(crate) mod verify; use crate::error::{ErrorCode, bail_coded, err_coded}; use anyhow::Result; diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index 28c0e85bc7..dc67c19ce5 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -9,13 +9,13 @@ use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::graph::FactStorage; use crate::graph::types::Fact; -use crate::storage::btree::{build_btree, cow_insert}; +use crate::storage::btree::{MutexStorageBackend, build_btree, cow_insert}; use crate::storage::cache::PageCache; use crate::storage::dict::{DictReader, Encoded, Encoder}; use crate::storage::meta::{MetaPage, SlotState, slot_page}; use crate::storage::page::PageAllocator; use crate::storage::reader::OnDiskReader; -use crate::storage::{LegacyHeaderV7, PAGE_SIZE, StorageBackend, freelist, page}; +use crate::storage::{LegacyHeaderV7, PAGE_SIZE, StorageBackend, freelist, page, verify}; use anyhow::Result; use std::sync::{Arc, Mutex}; @@ -33,6 +33,10 @@ pub struct PersistentFactStorage { meta: MetaPage, } +/// Page cache size for the integrity walk: enough to keep a value page hot +/// while its values are checked, without displacing the readers' cache. +const VERIFY_CACHE_PAGES: usize = 64; + /// What open found in the meta slots. enum Opened { Meta(MetaPage), @@ -363,6 +367,184 @@ impl PersistentFactStorage { Ok(()) } + /// Check the committed file (#373). Never modifies it, and holds the + /// backend lock only for each page read, so queries keep running. + pub(crate) fn verify(&self) -> Result { + let backend = MutexStorageBackend(self.backend.clone()); + let cache = PageCache::new(VERIFY_CACHE_PAGES); + cache.set_generation_bound(self.meta.generation); + Ok(verify::verify(&backend, &cache, self.meta)) + } + + /// Rebuild EAVT, AEVT, AVET and VAET from an intact index and commit them, + /// with the pending facts, as the next generation (#373). + /// + /// The source is chosen by [`verify::choose_source`]; with none, or with a + /// damaged DICT, this fails with STG-041 and writes nothing. Like + /// [`save`](Self::save), it writes only pages the active meta does not + /// 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. + pub(crate) fn rebuild_indexes(&mut self) -> Result<()> { + use crate::storage::btree::LeafCursor; + use crate::storage::keys::{Index, KeyFact}; + use std::collections::BTreeSet; + + let m = self.meta; + let next_gen = m.next_generation()?; + let pending_facts = self.storage.get_pending_facts(); + let mut backend = self.lock()?; + 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) = { + let mut w = verify::Walker::new(&*backend, &cache, m); + let scans: Vec = [Index::Eavt, Index::Aevt, Index::Avet] + .into_iter() + .map(|i| w.scan_index(i)) + .collect(); + let vaet = w.scan_index(Index::Vaet); + let dict = w.scan_dict(); + if !dict.clean { + bail_coded!(ErrorCode::Stg041, "the dictionary (DICT) is damaged"); + } + let source = verify::choose_source(&scans).ok_or_else(|| { + err_coded!( + ErrorCode::Stg041, + "no intact index agrees with another and more than one is intact, or none is" + ) + })?; + let mut keep: BTreeSet = dict.value_pages.clone(); + for s in scans.iter().chain([&vaet]) { + keep.extend(s.nodes.iter().copied()); + } + keep.extend(dict.nodes.iter().copied()); + let pool: BTreeSet = w + .read_free_list() + .map(|(ids, _)| ids.into_iter().filter(|id| !keep.contains(id)).collect()) + .unwrap_or_default(); + (source, pool) + }; + + let mut alloc = PageAllocator::new(pool.into_iter().collect(), m.page_count, next_gen); + let encoded = encode( + &pending_facts, + &m, + &mut alloc, + &mut *backend, + &self.page_cache, + )?; + let (next_eid, next_iid) = (encoded.next_eid, encoded.next_iid); + let Encoded { + index: mut lists, + dict, + .. + } = encoded; + + let source_root = match source { + Index::Eavt => m.eavt_root, + Index::Aevt => m.aevt_root, + Index::Avet => m.avet_root, + Index::Vaet => m.vaet_root, + }; + if source_root != 0 { + let mut cursor = LeafCursor::new(source_root, None, &*backend, &cache)?; + while let Some((k, _)) = cursor.next_ref()? { + let kf = KeyFact::decode(source, k)?; + for (list, idx) in lists.iter_mut().zip(Index::ALL) { + if let Some(key) = kf.key(idx) { + list.push((key, Vec::new())); + } + } + } + } + for list in &mut lists { + list.sort_unstable(); + list.dedup(); + } + let fact_count = + u64::try_from(lists[0].len()).map_err(|_| err_coded!(ErrorCode::Stg024))?; + + let mut roots = [0u64; 5]; + for (root, entries) in roots.iter_mut().zip(lists) { + *root = build_btree(entries, &mut *backend, &self.page_cache, &mut alloc)?; + } + let mut replaced = Vec::new(); + roots[4] = cow_insert( + m.dict_root, + dict, + &mut *backend, + &self.page_cache, + &mut alloc, + &mut replaced, + )?; + let [eavt_root, aevt_root, avet_root, vaet_root, dict_root] = roots; + let mut new_meta = MetaPage { + generation: next_gen, + page_count: alloc.next_append(), + fact_count, + last_checkpointed_tx_count: self.storage.current_tx_count(), + eavt_root, + aevt_root, + avet_root, + vaet_root, + dict_root, + next_eid, + next_iid, + freelist_head: 0, + freelist_count: 0, + ..m + }; + + // Every page from 2 up that the new meta does not reach is free. The + // walk also checks what was just written. + let reached = { + let check = PageCache::new(VERIFY_CACHE_PAGES); + check.set_generation_bound(next_gen); + let mut w = verify::Walker::new(&*backend, &check, new_meta); + let mut reached: BTreeSet = BTreeSet::new(); + for idx in Index::ALL { + let s = w.scan_index(idx); + if !s.clean { + bail_coded!(ErrorCode::Int049, "rebuilt index fails its own check"); + } + reached.extend(s.nodes); + } + let d = w.scan_dict(); + if !d.clean { + bail_coded!( + ErrorCode::Int049, + "dictionary fails its check after rebuild" + ); + } + reached.extend(d.nodes); + reached.extend(d.value_pages); + reached + }; + let free: Vec = (2..alloc.next_append()) + .filter(|p| !reached.contains(p)) + .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)?; + new_meta.freelist_head = freelist_head; + new_meta.freelist_count = u64::try_from(free.len()) + .map_err(|_| err_coded!(ErrorCode::Int048, "free-list length"))?; + new_meta.page_count = chain_alloc.next_append(); + + backend.sync()?; + backend.write_page(slot_page(next_gen), &new_meta.encode())?; + backend.sync()?; + drop(backend); + + self.dirty = false; + self.activate(new_meta); + self.storage.post_checkpoint_clear(); + Ok(()) + } + /// Get a reference to the underlying fact storage pub fn storage(&self) -> &FactStorage { &self.storage @@ -1749,6 +1931,394 @@ mod tests { assert!(as_set(reopened.storage().get_all_facts().unwrap()) == all); } + // ── verify and rebuild_indexes (#373) ─────────────────────────────────── + + /// Rewrite leaf `id` in place with `f` applied to its entries, resealed so + /// that its CRC passes: logical damage that page checks cannot see. + fn rewrite_leaf( + mem: &MemoryBackend, + id: u64, + f: impl FnOnce(&mut Vec), + ) { + let mut mem = mem.clone(); // shares the pages + let old = mem.read_page(id).unwrap(); + let generation = page::page_generation(&old).unwrap(); + let mut entries = crate::storage::node::decode_leaf(&old).unwrap(); + f(&mut entries); + let mut p = crate::storage::node::encode_leaf(&entries).unwrap(); + page::seal(&mut p, id, generation).unwrap(); + mem.write_page(id, &p).unwrap(); + } + + /// Rewrite free-list chain page `id` with `f` applied to its ids. + fn rewrite_free_page(mem: &mut MemoryBackend, id: u64, f: impl FnOnce(&mut Vec)) { + let old = mem.read_page(id).unwrap(); + let generation = page::page_generation(&old).unwrap(); + let next = u64::from_le_bytes(old[24..32].try_into().unwrap()); + let count = usize::from(page::page_count_field(&old).unwrap()); + let mut ids: Vec = (0..count) + .map(|j| u64::from_le_bytes(old[32 + 8 * j..40 + 8 * j].try_into().unwrap())) + .collect(); + f(&mut ids); + let mut p = page::new_page(page::PAGE_TYPE_FREELIST, ids.len() as u16); + p[24..32].copy_from_slice(&next.to_le_bytes()); + for (j, id) in ids.iter().enumerate() { + p[32 + 8 * j..40 + 8 * j].copy_from_slice(&id.to_le_bytes()); + } + page::seal(&mut p, id, generation).unwrap(); + mem.write_page(id, &p).unwrap(); + } + + fn verify_codes(mem: &MemoryBackend) -> Vec<&'static str> { + let pfs = open_mem(mem, None).unwrap(); + pfs.verify() + .unwrap() + .problems + .into_iter() + .map(code) + .collect() + } + + /// Ids in the free list of `m` (all chain pages). + fn free_ids(m: &MetaPage, mem: &MemoryBackend) -> Vec { + freelist::read_chain(m.freelist_head, mem, &PageCache::new(0), m.page_count) + .unwrap() + .0 + } + + #[test] + fn intact_files_verify_clean() { + let mem = MemoryBackend::new(); + let pfs = PersistentFactStorage::new(mem.clone(), 16).unwrap(); + let f = pfs.verify().unwrap(); + assert!(f.problems.is_empty(), "an empty file is intact"); + assert_eq!(f.facts, 0); + drop(pfs); + + let mem = corruptible(); + let pfs = open_mem(&mem, None).unwrap(); + let m = pfs.meta(); + let f = pfs.verify().unwrap(); + assert!(f.problems.is_empty(), "an intact file has no problems"); + assert_eq!(f.facts, m.fact_count); + let in_use = (2..m.page_count).count() - free_ids(&m, &mem).len(); + assert_eq!(f.pages as usize, in_use, "every page in use is checked"); + } + + /// Each kind of damage is found with its code, and `rebuild_indexes` + /// repairs it: verify is clean, every fact reads back, the indexes agree + /// and every page is accounted for. + #[test] + fn each_index_damage_is_found_and_repaired() { + type Damage = fn(&mut MemoryBackend, &MetaPage); + let cases: [(&str, Damage, &str); 9] = [ + ( + "a page in two trees", + |mem, m| { + let shared = leaves_of(m.aevt_root, mem)[0]; + let meta = MetaPage { + vaet_root: shared, + ..*m + }; + mem.write_page(slot_page(m.generation), &meta.encode()) + .unwrap(); + }, + "STG-039", + ), + ( + "AVET leaf missing an entry", + |mem, m| { + rewrite_leaf(mem, leaves_of(m.avet_root, mem)[0], |e| { + e.remove(0); + }) + }, + "STG-038", + ), + ( + "EAVT leaf missing an entry", + |mem, m| { + rewrite_leaf(mem, leaves_of(m.eavt_root, mem)[1], |e| { + e.remove(3); + }) + }, + "STG-038", + ), + ( + "AEVT leaf missing an entry", + |mem, m| { + rewrite_leaf(mem, leaves_of(m.aevt_root, mem)[0], |e| { + e.pop(); + }) + }, + "STG-038", + ), + ( + "VAET leaf missing an entry", + |mem, m| { + rewrite_leaf(mem, leaves_of(m.vaet_root, mem)[0], |e| { + e.remove(0); + }) + }, + "STG-038", + ), + ( + "AVET keys out of order", + |mem, m| rewrite_leaf(mem, leaves_of(m.avet_root, mem)[0], |e| e.swap(0, 1)), + "STG-039", + ), + ( + "AEVT leaf rotted", + |mem, m| flip(mem, leaves_of(m.aevt_root, mem)[0]), + "STG-029", + ), + ( + "free page still in use", + |mem, m| { + let node = leaves_of(m.dict_root, mem)[0]; + rewrite_free_page(mem, m.freelist_head, |ids| ids[0] = node); + }, + "STG-035", + ), + ( + "leaked page", + |mem, m| { + rewrite_free_page(mem, m.freelist_head, |ids| { + ids.pop(); + }) + }, + "STG-035", + ), + ]; + let mem = corruptible(); + let (all, m) = { + let pfs = open_mem(&mem, None).unwrap(); + (as_set(pfs.storage().get_all_facts().unwrap()), pfs.meta()) + }; + for (what, damage, expected) in cases { + let mut damaged = deep_copy(&mem); + damage(&mut damaged, &m); + let found = verify_codes(&damaged); + assert!( + found.contains(&expected), + "{what}: expected {expected}, got {found:?}" + ); + + let mut pfs = open_mem(&damaged, None).unwrap(); + pfs.rebuild_indexes() + .unwrap_or_else(|e| panic!("{what}: rebuild failed: {e}")); + assert_eq!(pfs.generation(), m.generation + 1, "{what}"); + drop(pfs); + assert!( + verify_codes(&damaged).is_empty(), + "{what}: clean after rebuild" + ); + let pfs = open_mem(&damaged, None).unwrap(); + assert!( + as_set(pfs.storage().get_all_facts().unwrap()) == all, + "{what}: every fact reads back" + ); + assert_space_accounted(&pfs.meta(), &damaged); + assert_indexes_exact(&pfs.meta(), &damaged); + } + } + + /// The source is an intact index that agrees with another one. + #[test] + fn rebuild_source_is_an_index_that_agrees_with_another() { + let mem = corruptible(); + let pfs = open_mem(&mem, None).unwrap(); + let m = pfs.meta(); + let all = as_set(pfs.storage().get_all_facts().unwrap()); + drop(pfs); + // EAVT and AEVT lose different entries; AVET agrees with neither, so + // there is no majority and two indexes are intact: refused. + let damaged = deep_copy(&mem); + rewrite_leaf(&damaged, leaves_of(m.eavt_root, &damaged)[0], |e| { + e.remove(0); + }); + rewrite_leaf(&damaged, leaves_of(m.aevt_root, &damaged)[0], |e| { + e.remove(1); + }); + rewrite_leaf(&damaged, leaves_of(m.avet_root, &damaged)[0], |e| { + e.remove(2); + }); + let before = snapshot(&damaged); + let mut pfs = open_mem(&damaged, None).unwrap(); + let err = pfs.rebuild_indexes().unwrap_err(); + assert_eq!(code(err), "STG-041"); + drop(pfs); + assert!( + snapshot(&damaged) == before, + "a refused rebuild writes nothing" + ); + + // EAVT and AEVT unreadable: AVET is the only intact index. + let mut damaged = deep_copy(&mem); + let id = leaves_of(m.eavt_root, &damaged)[0]; + flip(&mut damaged, id); + let id = leaves_of(m.aevt_root, &damaged)[0]; + flip(&mut damaged, id); + let mut pfs = open_mem(&damaged, None).unwrap(); + pfs.rebuild_indexes().unwrap(); + assert!(as_set(pfs.storage().get_all_facts().unwrap()) == all); + drop(pfs); + assert!(verify_codes(&damaged).is_empty()); + } + + /// DICT holds the only copy of UUIDs and idents: a damaged DICT is + /// reported and a rebuild refuses without writing. + #[test] + fn dictionary_damage_is_reported_and_not_rebuilt() { + let mem = corruptible(); + let m = open_mem(&mem, None).unwrap().meta(); + let tx_leaf = leaves_of(m.dict_root, &mem) + .into_iter() + .find(|&id| { + crate::storage::node::decode_leaf(&mem.read_page(id).unwrap()) + .unwrap() + .iter() + .any(|(k, _)| k[0] == crate::storage::keys::DICT_TX) + }) + .unwrap(); + let damaged = deep_copy(&mem); + rewrite_leaf(&damaged, tx_leaf, |e| { + let i = e + .iter() + .position(|(k, _)| k[0] == crate::storage::keys::DICT_TX) + .unwrap(); + e.remove(i); + }); + assert!(verify_codes(&damaged).contains(&"STG-036")); + + // An entity id whose UUID maps back to another id. + let eid_leaf = leaves_of(m.dict_root, &mem) + .into_iter() + .find(|&id| { + crate::storage::node::decode_leaf(&mem.read_page(id).unwrap()) + .unwrap() + .iter() + .any(|(k, _)| k[0] == crate::storage::keys::DICT_EID_TO_UUID) + }) + .unwrap(); + let damaged = deep_copy(&mem); + rewrite_leaf(&damaged, eid_leaf, |e| { + let i = e + .iter() + .position(|(k, _)| k[0] == crate::storage::keys::DICT_EID_TO_UUID) + .unwrap(); + e[i].1 = Uuid::from_u128(0xdead).as_bytes().to_vec(); + }); + assert!(verify_codes(&damaged).contains(&"STG-040")); + + let mut damaged = deep_copy(&mem); + flip(&mut damaged, tx_leaf); + assert!(verify_codes(&damaged).contains(&"STG-029")); + let before = snapshot(&damaged); + let mut pfs = open_mem(&damaged, None).unwrap(); + assert_eq!(code(pfs.rebuild_indexes().unwrap_err()), "STG-041"); + drop(pfs); + assert!( + snapshot(&damaged) == before, + "a refused rebuild writes nothing" + ); + } + + /// Pending facts are committed by the rebuild, with new ids and long values. + #[test] + fn rebuild_commits_pending_facts() { + let mem = corruptible(); + let m = open_mem(&mem, None).unwrap().meta(); + rewrite_leaf(&mem, leaves_of(m.avet_root, &mem)[0], |e| { + e.remove(0); + }); + let mut pfs = open_mem(&mem, None).unwrap(); + let (asserts, retracts) = mixed_batch(7, 120); + let new_long = ( + entity(9_000), + ":attr/new".to_string(), + Value::String("brand new long value ".repeat(5)), + ); + pfs.storage() + .transact(asserts.into_iter().chain([new_long]).collect(), None) + .unwrap(); + pfs.storage().retract(retracts).unwrap(); + pfs.mark_dirty(); + let expected = as_set(pfs.storage().get_all_facts().unwrap()); + pfs.rebuild_indexes().unwrap(); + assert!(!pfs.is_dirty()); + assert!(pfs.storage().get_pending_facts().is_empty()); + assert!(as_set(pfs.storage().get_all_facts().unwrap()) == expected); + assert_eq!( + pfs.last_checkpointed_tx_count(), + pfs.storage().current_tx_count() + ); + drop(pfs); + let pfs = open_mem(&mem, None).unwrap(); + assert!(as_set(pfs.storage().get_all_facts().unwrap()) == expected); + assert!(pfs.verify().unwrap().problems.is_empty()); + assert_space_accounted(&pfs.meta(), &mem); + assert_indexes_exact(&pfs.meta(), &mem); + } + + /// A crash at any write or sync of a rebuild reopens at the old generation + /// (unchanged) or the new one (repaired), and never loses a fact. + #[test] + fn crash_at_every_point_of_rebuild_keeps_every_fact() { + let base = corruptible(); + let (all, m) = { + let pfs = open_mem(&base, None).unwrap(); + (as_set(pfs.storage().get_all_facts().unwrap()), pfs.meta()) + }; + let mut points = 0; + for (write_kind, sync_kind, torn) in [ + (true, false, None), + (true, false, Some(512usize)), + (false, true, None), + ] { + for k in 0u64.. { + let mem = deep_copy(&base); + let leaf = leaves_of(m.avet_root, &mem)[0]; + rewrite_leaf(&mem, leaf, |e| { + e.remove(0); + }); + let (backend, config) = FaultInjectingBackend::with_config(mem.clone()); + let mut pfs = PersistentFactStorage::new(backend, 16).unwrap(); + { + let mut cfg = config.lock().unwrap(); + cfg.fail_write_after = write_kind.then_some(k); + cfg.fail_sync_after = sync_kind.then_some(k); + cfg.torn_write_bytes = torn; + } + let rebuilt = pfs.rebuild_indexes().is_ok(); + pfs.dirty = false; + drop(pfs); + + let pfs = open_mem(&mem, None).expect("reopen after crash"); + assert!( + as_set(pfs.storage().get_all_facts().unwrap()) == all, + "no fact lost" + ); + let problems = pfs.verify().unwrap().problems; + if pfs.generation() == m.generation + 1 { + assert!(problems.is_empty(), "the rebuilt generation is intact"); + } else { + assert_eq!(pfs.generation(), m.generation); + assert!(!rebuilt, "a reported success must be durable"); + let codes: Vec<_> = problems.into_iter().map(code).collect(); + assert!( + codes == ["STG-038"], + "the old generation keeps exactly its old damage" + ); + } + if rebuilt { + break; + } + points += 1; + } + } + assert!(points > 20, "expected many crash points"); + } + // ── size (spec §10.1, §11, #433) ──────────────────────────────────────── /// File bytes per fact for `entities` entities in #433's acceptance shape: diff --git a/src/storage/verify.rs b/src/storage/verify.rs new file mode 100644 index 0000000000..b225e277e0 --- /dev/null +++ b/src/storage/verify.rs @@ -0,0 +1,620 @@ +//! Integrity check of a committed v8 file (#373). +//! +//! Every page read already checks its CRC, id and generation (spec §4.2), so +//! physical damage is an error on the read that hits it. This module finds the +//! logical damage those checks cannot see: an index missing entries, indexes +//! that disagree, keys out of order, ids without dictionary entries, pages that +//! are leaked or referenced twice. It also picks the source index for +//! `rebuild_indexes`. +//! +//! The walk keeps no per-fact state. Indexes are compared by an order-independent +//! digest of their entries in canonical (EAVT) key form, so memory is bounded by +//! the page count and the dictionary sizes. + +use crate::error::{ErrorCode, err_coded}; +use crate::storage::cache::PageCache; +use crate::storage::keys::{self, Index, KeyFact, KeyValue, Reader, SHORT_STRING_MAX, ValueRef}; +use crate::storage::meta::MetaPage; +use crate::storage::node::{Internal, decode_leaf}; +use crate::storage::page::{PAGE_TYPE_INTERNAL, PAGE_TYPE_LEAF}; +use crate::storage::value_pages::read_value; +use crate::storage::{StorageBackend, freelist}; +use anyhow::Result; +use std::collections::{BTreeSet, HashMap, HashSet}; + +/// Deepest tree the walk descends (as `btree::MAX_TREE_DEPTH`). +const MAX_DEPTH: usize = 32; + +/// Order-independent digest of a set of index entries: count and two wrapping +/// sums of independent 64-bit hashes of each entry's canonical key. Equal sets +/// give equal digests; different ones collide with probability about 2^-64. +#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)] +pub(crate) struct Digest { + pub count: u64, + sum1: u64, + sum2: u64, +} + +impl Digest { + fn add(&mut self, canonical: &[u8]) { + self.count = self.count.wrapping_add(1); + self.sum1 = self.sum1.wrapping_add(keys::hash64(canonical)); + self.sum2 = self.sum2.wrapping_add(mix64(canonical)); + } +} + +/// A second hash, independent of FNV-1a: a multiply-rotate over each byte, +/// finished with the splitmix64 mixer. +fn mix64(bytes: &[u8]) -> u64 { + let mut h: u64 = 0x9E37_79B9_7F4A_7C15 ^ u64::try_from(bytes.len()).unwrap_or(u64::MAX); + for &b in bytes { + h = (h ^ u64::from(b)) + .wrapping_mul(0xBF58_476D_1CE4_E5B9) + .rotate_left(27); + } + h ^= h >> 31; + h = h.wrapping_mul(0x94D0_49BB_1331_11EB); + h ^ (h >> 29) +} + +/// What a walk of one index tree found. +pub(crate) struct IndexScan { + pub index: Index, + /// The walk finished: every page verified and decoded, keys in order. + pub clean: bool, + pub digest: Digest, + /// Digest of the ref facts only (used to check VAET against EAVT). + pub ref_digest: Digest, + /// Node pages reached. + pub nodes: Vec, +} + +/// What a walk of the DICT tree found. +pub(crate) struct DictScan { + pub clean: bool, + pub nodes: Vec, + /// Pages holding long values (through 0x06 entries). + pub value_pages: BTreeSet, + eids: HashSet, + iids: HashSet, + txs: HashSet, + long_values: HashMap)>, +} + +/// Ids, transactions and long values used by index keys. +#[derive(Default)] +struct IdUse { + eids: HashSet, + iids: HashSet, + txs: HashSet, + long: HashMap)>, +} + +/// The outcome of [`verify`]. +pub(crate) struct Findings { + pub facts: u64, + pub pages: u64, + pub problems: Vec, +} + +fn tree_name(index: Index) -> &'static str { + match index { + Index::Eavt => "EAVT", + Index::Aevt => "AEVT", + Index::Avet => "AVET", + Index::Vaet => "VAET", + } +} + +fn root_of(meta: &MetaPage, index: Index) -> u64 { + match index { + Index::Eavt => meta.eavt_root, + Index::Aevt => meta.aevt_root, + Index::Avet => meta.avet_root, + Index::Vaet => meta.vaet_root, + } +} + +/// A node to visit: page id, depth, and the key range its parent gives it +/// (lower bound inclusive, upper bound exclusive). +type Visit = (u64, usize, Option>, Option>); + +/// A walk over the committed file at one meta. +pub(crate) struct Walker<'a> { + backend: &'a dyn StorageBackend, + cache: &'a PageCache, + meta: MetaPage, + /// Every tree node reached so far, across all trees. + seen: HashSet, + pub problems: Vec, +} + +impl<'a> Walker<'a> { + pub fn new(backend: &'a dyn StorageBackend, cache: &'a PageCache, meta: MetaPage) -> Self { + Walker { + backend, + cache, + meta, + seen: HashSet::new(), + problems: Vec::new(), + } + } + + /// Walk the tree at `root` in key order, calling `on_entry` for each entry. + /// + /// Checks every node once: it verifies (through the cache), decodes, is not + /// reached twice (across all trees walked by this walker), and its keys lie + /// within the bounds its parent's separators give and increase strictly. + /// Returns the nodes reached and whether the walk finished; the first + /// problem stops it and is recorded. + fn walk_tree( + &mut self, + root: u64, + name: &str, + mut on_entry: impl FnMut(&[u8], &[u8]) -> Result<()>, + ) -> (Vec, bool) { + let mut nodes = Vec::new(); + if root == 0 { + return (nodes, true); + } + let malformed = |msg: String| err_coded!(ErrorCode::Stg039, name.to_string(), msg); + let mut prev: Option> = None; + let mut stack: Vec = vec![(root, 0, None, None)]; + let result: Result<()> = (|| { + while let Some((id, depth, lo, hi)) = stack.pop() { + if depth > MAX_DEPTH { + return Err(malformed(format!("deeper than {MAX_DEPTH} at page {id}"))); + } + if !self.seen.insert(id) { + return Err(malformed(format!("page {id} is reached twice"))); + } + nodes.push(id); + let page = self.cache.get_or_load(id, self.backend)?; + match page.first().copied() { + Some(PAGE_TYPE_LEAF) => { + let entries = decode_leaf(&page[..]) + .map_err(|e| malformed(format!("leaf {id} does not decode: {e}")))?; + for (k, v) in entries { + if lo.as_deref().is_some_and(|l| k.as_slice() < l) + || hi.as_deref().is_some_and(|h| k.as_slice() >= h) + { + return Err(malformed(format!( + "a key in leaf {id} is outside its parent's range" + ))); + } + if prev.as_deref().is_some_and(|p| k.as_slice() <= p) { + return Err(malformed(format!("keys out of order in leaf {id}"))); + } + on_entry(&k, &v)?; + prev = Some(k); + } + } + Some(PAGE_TYPE_INTERNAL) => { + let bad_node = + |e: anyhow::Error| malformed(format!("node {id} does not decode: {e}")); + let node = Internal::new(&page[..]).map_err(bad_node)?; + let n = node.count(); + let mut children = Vec::with_capacity(n.saturating_add(1)); + for i in 0..=n { + let c_lo = match i.checked_sub(1) { + Some(j) => Some(node.sep(j).map_err(bad_node)?.to_vec()), + None => lo.clone(), + }; + let c_hi = if i < n { + Some(node.sep(i).map_err(bad_node)?.to_vec()) + } else { + hi.clone() + }; + if let (Some(l), Some(h)) = (&c_lo, &c_hi) + && l >= h + { + return Err(malformed(format!( + "separators out of order in node {id}" + ))); + } + let child = node.child(i).map_err(bad_node)?; + children.push((child, depth.saturating_add(1), c_lo, c_hi)); + } + stack.extend(children.into_iter().rev()); + } + _ => return Err(err_coded!(ErrorCode::Stg013, id)), + } + } + Ok(()) + })(); + match result { + Ok(()) => (nodes, true), + Err(e) => { + self.problems.push(e); + (nodes, false) + } + } + } + + /// Walk one index tree: decode every key, digest it, and record the ids it + /// uses in `ids` (when given). + fn scan_index_with(&mut self, index: Index, mut ids: Option<&mut IdUse>) -> IndexScan { + let name = tree_name(index); + let last_tx = self.meta.last_checkpointed_tx_count; + let mut digest = Digest::default(); + let mut ref_digest = Digest::default(); + let root = root_of(&self.meta, index); + let (nodes, clean) = self.walk_tree(root, name, |k, v| { + if !v.is_empty() { + return Err(err_coded!( + ErrorCode::Stg039, + name.to_string(), + "an index entry carries a value" + )); + } + let kf = KeyFact::decode(index, k).map_err(|e| { + err_coded!(ErrorCode::Stg039, name.to_string(), format!("bad key: {e}")) + })?; + if kf.tx_count > last_tx { + return Err(err_coded!( + ErrorCode::Stg038, + name.to_string(), + format!( + "transaction {} is newer than the last checkpoint ({last_tx})", + kf.tx_count + ) + )); + } + let canonical = kf + .key(Index::Eavt) + .ok_or_else(|| err_coded!(ErrorCode::Int049, "EAVT key missing"))?; + digest.add(&canonical); + if matches!(kf.v, KeyValue::Ref(_)) { + ref_digest.add(&canonical); + } + if let Some(ids) = ids.as_deref_mut() { + ids.eids.insert(kf.e); + ids.iids.insert(kf.a); + ids.txs.insert(kf.tx_count); + match kf.v { + KeyValue::Ref(t) => { + ids.eids.insert(t); + } + KeyValue::Keyword(i) => { + ids.iids.insert(i); + } + KeyValue::LongStr { prefix, hash, vref } => { + ids.long.insert(vref, (hash, prefix)); + } + _ => {} + } + } + Ok(()) + }); + IndexScan { + index, + clean, + digest, + ref_digest, + nodes, + } + } + + pub fn scan_index(&mut self, index: Index) -> IndexScan { + self.scan_index_with(index, None) + } + + /// Walk the DICT tree, checking each entry's shape, the two inverse maps, + /// the id counters and every long value. + pub fn scan_dict(&mut self) -> DictScan { + let next_eid = self.meta.next_eid; + let next_iid = self.meta.next_iid; + let backend = self.backend; + let cache = self.cache; + let mut uuid_to_eid: HashMap, u64> = HashMap::new(); + let mut eid_to_uuid: HashMap> = HashMap::new(); + let mut ident_to_iid: HashMap, u32> = HashMap::new(); + let mut iid_to_ident: HashMap> = HashMap::new(); + let mut txs = HashSet::new(); + let mut long_values = HashMap::new(); + let mut value_pages = BTreeSet::new(); + let bad = |msg: String| err_coded!(ErrorCode::Stg040, msg); + let iid_from = + |n: u64| u32::try_from(n).map_err(|_| bad(format!("ident id {n} too large"))); + let root = self.meta.dict_root; + let (nodes, clean) = self.walk_tree(root, "DICT", |k, v| { + let (&tag, rest) = k + .split_first() + .ok_or_else(|| bad("empty key".to_string()))?; + let uint_key = |rest: &[u8]| -> Result { + let mut r = Reader::new(rest); + let n = r.uint()?; + if !r.is_empty() { + return Err(bad("trailing bytes after an id".to_string())); + } + Ok(n) + }; + match tag { + keys::DICT_UUID_TO_EID => { + if rest.len() != 16 { + return Err(bad("UUID key is not 16 bytes".to_string())); + } + uuid_to_eid.insert(rest.to_vec(), keys::read_uint_bytes(v)?); + } + keys::DICT_EID_TO_UUID => { + let e = uint_key(rest)?; + if v.len() != 16 { + return Err(bad(format!("entity id {e} maps to {} bytes", v.len()))); + } + if e == 0 || e >= next_eid.max(1) { + return Err(bad(format!("entity id {e} not below next_eid {next_eid}"))); + } + eid_to_uuid.insert(e, v.to_vec()); + } + keys::DICT_IDENT_TO_IID => { + ident_to_iid.insert(rest.to_vec(), iid_from(keys::read_uint_bytes(v)?)?); + } + keys::DICT_IID_TO_IDENT => { + let i = iid_from(uint_key(rest)?)?; + if i == 0 || i >= next_iid.max(1) { + return Err(bad(format!("ident id {i} not below next_iid {next_iid}"))); + } + if std::str::from_utf8(v).is_err() { + return Err(bad(format!("ident id {i} is not UTF-8"))); + } + iid_to_ident.insert(i, v.to_vec()); + } + keys::DICT_TX => { + txs.insert(uint_key(rest)?); + keys::read_uint_bytes(v)?; + } + keys::DICT_LONG_VALUE => { + let vref = keys::dict_long_value_ref(k)?; + let hash = rest + .get(..8) + .and_then(|b| <[u8; 8]>::try_from(b).ok()) + .map(u64::from_be_bytes) + .ok_or_else(|| bad("long-value key too short".to_string()))?; + let bytes = read_value(vref, backend, cache)?; + if bytes.len() <= SHORT_STRING_MAX + || keys::hash64(&bytes) != hash + || std::str::from_utf8(&bytes).is_err() + { + return Err(bad(format!( + "long value {}:{} does not match its entry", + vref.page, vref.slot + ))); + } + let prefix = + keys::long_str(std::str::from_utf8(&bytes).unwrap_or_default(), vref); + let KeyValue::LongStr { prefix, .. } = prefix else { + return Err(err_coded!(ErrorCode::Int049, "long_str shape")); + }; + value_pages.insert(vref.page); + long_values.insert(vref, (hash, prefix)); + } + other => return Err(bad(format!("unknown tag {other:#04x}"))), + } + Ok(()) + }); + let mut ok = clean; + if clean { + let pairs_match = uuid_to_eid.len() == eid_to_uuid.len() + && uuid_to_eid + .iter() + .all(|(u, e)| eid_to_uuid.get(e) == Some(u)); + if !pairs_match { + self.problems + .push(bad("UUID and entity-id maps are not inverse".to_string())); + ok = false; + } + let idents_match = ident_to_iid.len() == iid_to_ident.len() + && ident_to_iid + .iter() + .all(|(n, i)| iid_to_ident.get(i) == Some(n)); + if !idents_match { + self.problems + .push(bad("ident and ident-id maps are not inverse".to_string())); + ok = false; + } + } + DictScan { + clean: ok, + nodes, + value_pages, + eids: eid_to_uuid.into_keys().collect(), + iids: iid_to_ident.into_keys().collect(), + txs, + long_values, + } + } + + /// Read the free list: `(free ids, chain pages)`, recording a problem if it + /// cannot be read or its count disagrees with the meta. + pub fn read_free_list(&mut self) -> Option<(Vec, Vec)> { + if self.meta.freelist_head == 0 { + if self.meta.freelist_count != 0 { + self.problems.push(err_coded!( + ErrorCode::Stg035, + format!( + "empty chain but freelist_count {}", + self.meta.freelist_count + ) + )); + return None; + } + return Some((Vec::new(), Vec::new())); + } + match freelist::read_chain( + self.meta.freelist_head, + self.backend, + self.cache, + self.meta.page_count, + ) { + Ok((ids, chain)) => { + let n = u64::try_from(ids.len()).unwrap_or(u64::MAX); + if n != self.meta.freelist_count { + self.problems.push(err_coded!( + ErrorCode::Stg035, + format!( + "chain holds {n} ids, meta says {}", + self.meta.freelist_count + ) + )); + return None; + } + Some((ids, chain)) + } + Err(e) => { + self.problems.push(e); + None + } + } + } +} + +/// Check the committed file at `meta` (spec 2026-10-06 §3). +pub(crate) fn verify(backend: &dyn StorageBackend, cache: &PageCache, meta: MetaPage) -> Findings { + let mut w = Walker::new(backend, cache, meta); + let mut ids = IdUse::default(); + let scans: Vec = Index::ALL + .iter() + .map(|&i| w.scan_index_with(i, Some(&mut ids))) + .collect(); + let dict = w.scan_dict(); + let facts = scans.first().map_or(0, |s| s.digest.count); + + // C4, C5: cardinality and content against EAVT. + if let Some(eavt) = scans.iter().find(|s| s.index == Index::Eavt && s.clean) { + if eavt.digest.count != meta.fact_count { + w.problems.push(err_coded!( + ErrorCode::Stg038, + "EAVT", + format!( + "{} entries, meta records {}", + eavt.digest.count, meta.fact_count + ) + )); + } + for s in scans.iter().filter(|s| s.index != Index::Eavt && s.clean) { + let expected = if s.index == Index::Vaet { + eavt.ref_digest + } else { + eavt.digest + }; + if s.digest != expected { + w.problems.push(err_coded!( + ErrorCode::Stg038, + tree_name(s.index), + format!( + "{} entries differ from EAVT's {}", + s.digest.count, expected.count + ) + )); + } + } + } + + // C7, C9: every id and long value an index uses has its DICT entry. + if dict.clean { + let missing = |what: String| err_coded!(ErrorCode::Stg036, what); + if let Some(e) = ids.eids.iter().find(|e| !dict.eids.contains(e)) { + w.problems.push(missing(format!("entity id {e}"))); + } + if let Some(i) = ids.iids.iter().find(|i| !dict.iids.contains(i)) { + w.problems.push(missing(format!("ident id {i}"))); + } + if let Some(t) = ids.txs.iter().find(|t| !dict.txs.contains(t)) { + w.problems.push(missing(format!("transaction {t}"))); + } + for (vref, (hash, prefix)) in &ids.long { + match dict.long_values.get(vref) { + None => { + w.problems + .push(missing(format!("long value {}:{}", vref.page, vref.slot))); + break; + } + Some((h, p)) if h != hash || p != prefix => { + w.problems.push(err_coded!( + ErrorCode::Stg038, + "index", + format!( + "a key's long value {}:{} does not match the stored value", + vref.page, vref.slot + ) + )); + break; + } + Some(_) => {} + } + } + } + + // C10: every page from 2 up is reached once or free, never both. + let all_clean = scans.iter().all(|s| s.clean) && dict.clean; + let free = w.read_free_list(); + let mut pages = u64::try_from(w.seen.len()).unwrap_or(u64::MAX); + if let Some((free_ids, chain)) = free { + let mut reached: BTreeSet = w.seen.iter().copied().collect(); + for &p in dict.value_pages.iter().chain(chain.iter()) { + if !reached.insert(p) { + w.problems.push(err_coded!( + ErrorCode::Stg035, + format!("page {p} is used twice") + )); + } + } + pages = u64::try_from(reached.len()).unwrap_or(u64::MAX); + let mut free_set = BTreeSet::new(); + for &id in &free_ids { + if !free_set.insert(id) { + w.problems.push(err_coded!( + ErrorCode::Stg035, + format!("page {id} is listed twice") + )); + } else if reached.contains(&id) { + w.problems.push(err_coded!( + ErrorCode::Stg035, + format!("free page {id} is still in use") + )); + } + } + if all_clean { + let leaked = (2..meta.page_count) + .filter(|p| !reached.contains(p) && !free_set.contains(p)) + .count(); + if leaked > 0 { + w.problems.push(err_coded!( + ErrorCode::Stg035, + format!("{leaked} page(s) neither free nor in use") + )); + } + if let Some(p) = reached.iter().find(|&&p| p < 2 || p >= meta.page_count) { + w.problems.push(err_coded!( + ErrorCode::Stg035, + format!("page {p} in use outside 2..{}", meta.page_count) + )); + } + } + } + + Findings { + facts, + pages, + problems: w.problems, + } +} + +/// The index to rebuild from (spec 2026-10-06 §4): the first of two clean +/// indexes that agree, else the only clean one. `None` if neither applies. +pub(crate) fn choose_source(scans: &[IndexScan]) -> Option { + let clean: Vec<&IndexScan> = scans.iter().filter(|s| s.clean).collect(); + for (i, a) in clean.iter().enumerate() { + if clean + .iter() + .skip(i.saturating_add(1)) + .any(|b| b.digest == a.digest) + { + return Some(a.index); + } + } + match clean.as_slice() { + [only] => Some(only.index), + _ => None, + } +} diff --git a/tests/integrity_test.rs b/tests/integrity_test.rs new file mode 100644 index 0000000000..b2a375da0b --- /dev/null +++ b/tests/integrity_test.rs @@ -0,0 +1,128 @@ +//! `Minigraf::verify` and `Minigraf::rebuild_indexes` through the public API (#373). +#![cfg(not(target_arch = "wasm32"))] + +use minigraf::QueryResult; +use minigraf::db::Minigraf; + +const PAGE_SIZE: u64 = 4096; +const PAGE_TYPE_LEAF: u8 = 0x61; + +fn count(db: &Minigraf, query: &str) -> usize { + match db.execute(query).unwrap() { + QueryResult::QueryResults { results, .. } => results.len(), + _ => panic!("expected query results"), + } +} + +fn people(db: &Minigraf) -> usize { + count(db, "(query [:find ?e ?n :where [?e :person/name ?n]])") +} + +fn fill(db: &Minigraf, from: usize, to: usize) { + for i in from..to { + db.execute(&format!( + r#"(transact [[:p{i} :person/name "Person {i}"] [:p{i} :person/friend :p{}]])"#, + i / 2 + )) + .unwrap(); + } +} + +#[test] +fn in_memory_database_always_verifies() { + let db = Minigraf::in_memory().unwrap(); + fill(&db, 0, 10); + let report = db.verify().unwrap(); + assert!(report.is_ok()); + assert_eq!(report.facts, 0, "nothing is committed to pages"); + db.rebuild_indexes().unwrap(); + assert_eq!(people(&db), 10); +} + +#[test] +fn checkpointed_file_verifies_clean() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("clean.graph"); + let db = Minigraf::open(&path).unwrap(); + fill(&db, 0, 200); + db.checkpoint().unwrap(); + let report = db.verify().unwrap(); + assert!(report.is_ok(), "an intact file has no problems"); + assert_eq!(report.facts, 400); + assert!(report.pages > 0); +} + +#[test] +fn rebuild_commits_wal_entries_and_deletes_the_wal() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("rebuild.graph"); + let wal = dir.path().join("rebuild.graph.wal"); + { + let db = Minigraf::open(&path).unwrap(); + fill(&db, 0, 100); + db.checkpoint().unwrap(); + fill(&db, 100, 150); + db.execute("(retract [[:p3 :person/name \"Person 3\"]])") + .unwrap(); + assert!(wal.exists(), "uncheckpointed writes are in the WAL"); + db.rebuild_indexes().unwrap(); + assert!(!wal.exists(), "the rebuild commits like a checkpoint"); + assert_eq!(people(&db), 149); + let report = db.verify().unwrap(); + assert!(report.is_ok()); + assert_eq!(report.facts, 301); + } + let db = Minigraf::open(&path).unwrap(); + assert_eq!(people(&db), 149); + assert!(db.verify().unwrap().is_ok()); +} + +/// Flip a byte in each leaf page in turn. `verify` reports the damage as +/// STG-029; `rebuild_indexes` either repairs it (an index leaf) or refuses +/// with STG-041 (a DICT leaf), never returning success on a damaged file. +#[test] +fn damaged_leaves_are_reported_and_index_damage_is_repaired() { + let dir = tempfile::tempdir().unwrap(); + let clean = dir.path().join("clean.graph"); + { + let db = Minigraf::open(&clean).unwrap(); + fill(&db, 0, 300); + db.checkpoint().unwrap(); + } + let bytes = std::fs::read(&clean).unwrap(); + let leaves: Vec = (2..bytes.len() as u64 / PAGE_SIZE) + .filter(|&p| bytes[(p * PAGE_SIZE) as usize] == PAGE_TYPE_LEAF) + .collect(); + assert!(leaves.len() > 4, "fixture spans several leaves"); + + let (mut repaired, mut refused) = (0, 0); + for (i, &leaf) in leaves.iter().enumerate() { + let path = dir.path().join(format!("damaged{i}.graph")); + let mut damaged = bytes.clone(); + damaged[(leaf * PAGE_SIZE + 2000) as usize] ^= 0x5A; + std::fs::write(&path, &damaged).unwrap(); + + let db = Minigraf::open(&path).unwrap(); + let report = db.verify().unwrap(); + assert!(!report.is_ok(), "a flipped leaf is reported"); + assert!(report.problems.iter().any(|e| e.code() == "STG-029")); + match db.rebuild_indexes() { + Ok(()) => { + repaired += 1; + assert!(db.verify().unwrap().is_ok(), "clean after rebuild"); + assert_eq!(people(&db), 300); + } + Err(e) => { + refused += 1; + assert_eq!(e.code(), "STG-041"); + drop(db); + assert!( + std::fs::read(&path).unwrap() == damaged, + "a refused rebuild writes nothing" + ); + } + } + } + assert!(repaired > 0, "index leaves are repaired"); + assert!(refused > 0, "DICT leaves are refused"); +}