diff --git a/CHANGELOG.md b/CHANGELOG.md index a57554b51f..803b70140f 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -10,6 +10,8 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Breaking changes - **File format v8** (#287, #371). Index keys now include the encoded value and the assert/retract flag. A v7 file (written by v2.x) is re-indexed and upgraded to v8 the first time it is opened; the upgrade is one-way and v2.x cannot open a v8 file (`STG-006`). Bindings users get this upgrade silently on open. +- **Crash-atomic checkpoints with verified pages** (v8 storage format, PR 2 of 5; #374, #388). Two alternating meta pages replace the 84-byte file header and are the only commit point: a checkpoint writes only pages the last commit does not use, syncs, then writes the other meta page and syncs. A crash or torn write at any point leaves the previous checkpoint intact, so opening never rebuilds an index, and the whole-file index checksum is gone. Every other page carries a 24-byte header (type, CRC32, its own page id, the checkpoint generation that wrote it), checked on every read: a torn, corrupted, misplaced or stale page now fails with `STG-029`, `STG-030` or `STG-031` instead of being read. If the newest meta page is damaged after its WAL was already deleted, open fails with `STG-033` rather than silently going back to the previous checkpoint. New codes `STG-029`–`STG-035`. The WAL header gains a base generation (WAL version 2); a v2.x WAL beside a migrated file is still replayed. Pages freed by a checkpoint are reused by later ones; checkpoints still rewrite all four indexes until copy-on-write insert lands (PR 4). Files written by a v3.0.0 development build before this change fail with `STG-032`. +- **The maximum fact size for file-backed databases is 4,052 bytes** (was 4,080), so that every index key derived from a fact fits in an index page. Index pages now reject an entry that does not fit instead of writing an overlapping page. - **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. ### Fixed diff --git a/CLAUDE.md b/CLAUDE.md index 00ece71896..aaea41cec2 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -162,18 +162,24 @@ enum Value { String(String), Integer(i64), Float(f64), Boolean(bool), ### File Format (v8) ``` -Page 0: Header (84 bytes) — magic "MGRF", version, page/fact counts, - B+tree root pages (eavt/aevt/avet/vaet), header_checksum, index_checksum, fact_page_count -Page 1+: Packed fact pages (postcard-encoded, ~25 facts/4KB page) -After: On-disk B+tree index pages (one node per 4KB page) -Sidecar: .wal — CRC32-protected WAL entries; replayed on open; deleted on checkpoint +Page 0, 1: Meta pages A/B (alternating commits: odd generations in page 0, even in 1). + Magic "MGRF"/"META", generation, page_count, index roots, free-list head, + required_features; CRC over the whole page. The only commit point. +Page 2+: Any mix of fact pages (0x41, interim until covering indexes), B+tree + leaf/internal pages (0x61/0x62) and free-list pages (0x81). Every one has + a 24-byte header (type, count, CRC32, page id, generation), verified on load. +Sidecar: .wal — v2 header records the base generation; CRC32-protected entries; + replayed on open; deleted on checkpoint ``` -Auto-migrates v7 → v8 on open (index rebuild). v1–v6 are rejected (STG-028). +A checkpoint writes only pages the active meta does not reference, syncs, then writes +the other meta page and syncs, so a crash at any point keeps the previous checkpoint. +Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are rejected +(STG-028). Design: `docs/superpowers/specs/2026-10-05-v8-storage-format-design.md`. ## Test Coverage -**1225 tests passing** (1217 passing, 8 ignored; unit + integration + doc). +**1233 tests** (1225 passing, 8 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/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index 0bcadac2cd..0ac766c588 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -137,6 +137,13 @@ with no `CodedError` anywhere in its chain. | STG-026 | Database locked by another process | Storage | | STG-027 | Filesystem does not support file locking | Storage | | STG-028 | Format version no longer supported | Storage | +| STG-029 | Page checksum mismatch | Storage | +| STG-030 | Page id mismatch | Storage | +| STG-031 | Page generation ahead of meta | Storage | +| STG-032 | No valid meta page | Storage | +| STG-033 | Meta page damaged after commit | Storage | +| STG-034 | Unsupported file feature | Storage | +| STG-035 | Free-list inconsistency | Storage | | WAL-001 | Invalid WAL magic number | WAL | | WAL-002 | Unsupported WAL version | WAL | | WAL-003 | Fact serialised size exceeds maximum | WAL | @@ -2003,6 +2010,84 @@ See the [file format section in README](../README.md#file-format) for version hi **Scenario**: A `.graph` file created with Minigraf v1.x and never opened with v2.x. +### STG-029 Page checksum mismatch + +**Error text**: `Page {} checksum mismatch: the page is torn or corrupted` + +**Cause**: A page's stored CRC32 does not match its contents. The page was partly written (a torn write) or its bytes changed on disk after it was written. + +**Resolution**: +- Restore from backup. If the damaged page belongs only to an unfinished checkpoint, the file opens at the previous checkpoint and the WAL replays the rest; this error means a page reachable from the committed meta page is damaged. + +**Scenario**: A disk sector holding a B+tree leaf is corrupted by the storage device. + +### STG-030 Page id mismatch + +**Error text**: `Page id mismatch: requested page {} but the page records id {}` + +**Cause**: A page's header records a different page id from the one that was read. The storage layer wrote the page to the wrong offset (a misdirected write), or the file was edited. + +**Resolution**: +- Restore from backup. Check the storage device and filesystem for faults. + +**Scenario**: A faulty controller writes page 812's contents at the offset of page 640. + +### STG-031 Page generation ahead of meta + +**Error text**: `Page {} has generation {}, newer than the committed generation {}` + +**Cause**: A page reachable from the committed meta page records a checkpoint generation newer than the meta page itself. Pages are only written by the checkpoint that commits them, so this means a stale meta page, or a page from a later checkpoint written where an older page should be. + +**Resolution**: +- Restore from backup. + +**Scenario**: A meta page restored from an old copy of the file, next to data pages from a newer one. + +### STG-032 No valid meta page + +**Error text**: `No valid meta page: the file is not a Minigraf v7 or v8 database, or both meta pages are damaged` + +**Cause**: Neither meta page (page 0 or page 1) passes its checksum, page 0 is not a valid format v7 header, and no migration backup meta page can be used. Pre-release v8 files written during v3.0.0 development are also rejected this way. + +**Resolution**: +- Check that the path points to a Minigraf database. +- Restore from backup. The file is not modified by the failed open. + +**Scenario**: Opening a file whose first two pages were overwritten, or a file from a v3.0.0 development build. + +### STG-033 Meta page damaged after commit + +**Error text**: `Meta page damaged after commit: generation {} is valid but a later commit existed ({}). Opening would silently drop that checkpoint` + +**Cause**: One meta page is valid and the other is damaged, and there is evidence that the damaged one held a newer, completed checkpoint: the WAL records a newer base generation, or there is no WAL and data pages from the newer generation exist. Opening at the older generation would lose the facts of the newest checkpoint, whose WAL is already deleted. + +**Resolution**: +- Restore from backup. The file is not modified by the failed open. + +**Scenario**: A storage fault corrupts the most recent meta page after a successful checkpoint. + +### STG-034 Unsupported file feature + +**Error text**: `Unsupported file feature bits {}: the file was written by a newer Minigraf version` + +**Cause**: The meta page's `required_features` bitmask has bits this version does not know. A newer Minigraf v3.x release wrote structures this version cannot read. + +**Resolution**: +- Open the file with the Minigraf version that wrote it, or a newer one. The file is not modified by the failed open. + +**Scenario**: A file written by a later v3.x release that enabled an optional on-disk structure, opened with v3.0.0. + +### STG-035 Free-list inconsistency + +**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. + +**Resolution**: +- Restore from backup. + +**Scenario**: A corrupted free-list page whose `next` pointer points back at itself. + --- ## WAL — Write-Ahead Log Errors diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 9d330da729..8f94bda5f7 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-10-05 with `cargo test --quiet` -**Result**: 1,217 passing tests and 8 ignored tests (1,225 total) +**Result**: 1,225 passing tests and 8 ignored tests (1,233 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). A fault-injection test crashes `save()` at each of its 47 page writes and syncs and checks that every reopen finds exactly the old or the new checkpointed facts (#374). +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. A maximum-size fact's index keys fit in an internal node, and an oversized leaf entry or separator is rejected instead of overlapping the slot directory. ### Covered Areas diff --git a/docs/superpowers/plans/2026-10-05-v8-storage-format.md b/docs/superpowers/plans/2026-10-05-v8-storage-format.md index 1f36fd4529..cd05aa37c9 100644 --- a/docs/superpowers/plans/2026-10-05-v8-storage-format.md +++ b/docs/superpowers/plans/2026-10-05-v8-storage-format.md @@ -8,7 +8,7 @@ **Tech Stack:** Rust (MSRV 1.89), postcard (until PR 3), crc32fast, criterion. No new dependencies. -**Delivery:** five PRs into `v3` (spec §14). This plan details PR 1 task by task. PRs 2–5 are listed at task level. Each gets its own detailed plan section, written when the previous PR has merged, because each builds on the code shape the previous one leaves. +**Delivery:** five PRs into `v3` (spec §14). PR 1 and PR 2 are detailed task by task. PRs 3–5 are listed at task level. Each gets its own detailed plan section, written when the previous PR has merged, because each builds on the code shape the previous one leaves. ## Global Constraints @@ -149,17 +149,222 @@ --- -# PR 2 — v8 page format (outline) +# PR 2 — v8 page format + +Spec §4.1, §4.2, §4.4 (full-rewrite form), §9, §12. Branch `feat/v8-pr2-page-format`. + +**Outcome:** every page carries a verified header, two alternating meta pages are the +only commit point, and a crash at any write, sync or torn write loses no checkpointed +fact and needs no index rebuild on open. `save()` still rewrites all four trees, so it +stays O(N). PR 4 makes it O(change). + +**Shape decisions (from reading the v3 code):** + +- **Fact pages stay until PR 3** with the interim type 0x41 and the 24-byte header. + They always append at `page_count` and are never freed, as value pages will be + (§8.2). Page id order is then insertion order, which keeps `stream_all` ordering. +- **`stream_all`** collects the distinct fact page ids referenced by EAVT, sorts them, + and reads each page. No fact-page directory and no contiguity assumption. +- **Trees** are rebuilt each save with the existing `rebuild_btree_incremental`. It now + takes a page allocator instead of a start id, and it restamps copied leaves with the + new id, generation and CRC. Tree and free-list pages come from `M`'s free list first, + then append. +- **Free list:** each save frees every page of `M`'s four trees and `M`'s free-list + pages, and writes the whole new list as a fresh 0x81 chain. PR 4 replaces this with + O(delta) push/pop. The on-disk format is already final. +- **FileBackend becomes format-agnostic.** Today it parses page 0 as a v7 header and + rewrites it on every append, which is the #308 hazard. Its page count comes from the + file length, rounded down so that a torn trailing append is invisible. Page 0 is just + a page. +- **New file:** `PersistentFactStorage` writes an empty generation-1 meta to page 0 and + syncs, before anything else. +- **v7 migration lands here**, because page 0 changes here. It follows §9 with + postcard keys and 0x41 fact pages. PR 3 retargets it to covering keys. +- **Page cache** verifies on every miss against a generation bound held in an + `AtomicU64`. Meta pages, legacy v7 pages and the evidence search read the backend + directly and never go through the cache. Every page write updates the cache + (`put_dirty`), so a reused page id never serves stale bytes. +- **Error codes (new):** STG-029 page checksum mismatch, STG-030 page id mismatch, + STG-031 page generation ahead of meta, STG-032 no valid meta page, STG-033 meta damaged + after commit, STG-034 unsupported file feature, STG-035 free-list inconsistency. An + unknown page type is the existing STG-013. INT-053 (header CRC) stays in use for a + damaged v7 header, and a file with no magic in page 0 is still STG-002. Check the + next free numbers in `src/error.rs` before assigning. -Spec §4.1, §4.2, §12. Atomic but still O(N) `save()`. +## Review Focus -- Common 24-byte page header (type, count, CRC, page id, generation): encode and verify helpers. Verification runs in `PageCache::get_or_load`, with new STG codes. -- Renumber page types (0x51, 0x61, 0x62, 0x81). Update constants and the type-check tests. -- Meta pages A/B: `MetaPage` struct, encode/decode, selection by §4.1.1. WAL v2 `base_generation` (`wal.rs` header). Search for evidence of an interrupted commit. -- `required_features` check and error code. -- `save()`: write everything into fresh pages (append), sync, write the inactive meta, sync. Delete `index_checksum`, `fact_prefix_crc` and the rebuild-on-open branch. -- `FaultInjectingBackend` torn-write mode. Extend the crash-at-every-point test, including a torn meta write. -- Browser flush check: the meta page goes in the same IDB transaction. +- Every page write in `save()` and migration targets a page `M` does not reference. + Task 9 asserts this in tests. +- Meta selection, row by row against the §4.1.1 table. +- No path silently opens an older generation when the WAL is gone. + +### Task 1: `src/storage/page.rs` — common header + +- [ ] Constants: `PAGE_HEADER_SIZE = 24`, `PAGE_TYPE_FACT_INTERIM = 0x41`, + `PAGE_TYPE_VALUE = 0x51`, `PAGE_TYPE_VALUE_OVERFLOW = 0x52`, `PAGE_TYPE_LEAF = 0x61`, + `PAGE_TYPE_INTERNAL = 0x62`, `PAGE_TYPE_FREELIST = 0x81`, plus a `RETIRED_PAGE_TYPES` + doc table (0x02, 0x03, 0x11, 0x21, 0x22). +- [ ] `fn seal(page: &mut [u8], page_id: u64, generation: u64)` writes the id and + generation, zeroes the CRC field, computes CRC32 over the page and stores it. +- [ ] `fn verify(page: &[u8], expected_id: u64, max_generation: u64) -> Result` runs + checks 1–4 from §4.2 in order and returns the page type. +- [ ] Register the STG codes in `src/error.rs` and `docs/ERROR_REFERENCE.md`. +- [ ] Tests: seal/verify round trip; flipped body bit → STG-029; wrong id → STG-030; + future generation → STG-031; legacy type byte 0x21 → STG-013 before the CRC check + (a page with a wrong CRC and type 0x21 still gives STG-013). + +### Task 2: Page cache verifies on load + +- [ ] `PageCache` gains `generation_bound: AtomicU64` (default `u64::MAX`) and + `set_generation_bound`. +- [ ] `get_or_load` calls `page::verify` on every backend read, including the + capacity-0 path, before inserting. A failed page is not cached. +- [ ] Remove `invalidate_from` (its only caller is the old `save`). +- [ ] Tests: a corrupt page returns STG-029 and `cached_page_count()` is unchanged; a + page with `generation > bound` is rejected and accepted after the bound is raised. + +### Task 3: Pages on the new header + +- [ ] B+tree: types 0x61/0x62, header 24 bytes, `next_leaf` removed from the encoding + and from `build_btree`'s patch pass and `HeldPage`. `count` lives at bytes 2..4. + Internal: `rightmost_child` moves to body offset 24. +- [ ] `PageAllocator { free: Vec, next_append: u64, generation: u64 }` with + `alloc()` (free list first, then append) and `alloc_append()`. Writers take + `&mut PageAllocator` and seal every page with its generation. + `rebuild_btree_incremental` restamps copied leaves. +- [ ] Fact pages: `packed_pages` writes 0x41 with the 24-byte header and + `MAX_FACT_BYTES = PAGE_SIZE − 24 − 4`. Move the 12-byte 0x02 reader to + `packed_pages::legacy_v7`, used only by migration. +- [ ] Update the type-check and layout tests and every `PAGE_TYPE_*` assertion. + `range_scan_ignores_next_leaf` is deleted, since the field no longer exists. + +### Task 4: Meta pages — `src/storage/meta.rs` + +- [ ] `MetaPage` with the §4.1 fields, `encode() -> [u8; PAGE_SIZE]` and + `decode(&[u8]) -> SlotState { Empty, Valid(MetaPage), Damaged }`. + `fn slot_page(generation) = (generation − 1) % 2`. +- [ ] `KNOWN_FEATURES: u64 = 0`. A valid meta with unknown bits fails open with + STG-034, naming the bits. +- [ ] Tests: round trip; each field offset matches the table; reserved bytes non-zero → + Damaged; CRC flip → Damaged; no magic → Empty; v7 header bytes → Empty (it has no + "META"). + +### Task 5: Free-list pages + +- [ ] `freelist::write_chain(ids, alloc, backend, cache)`: up to 508 ids per page, + `next u64` at body offset 24, chain pages allocated from `alloc`. The chain's own + pages are not in the list. +- [ ] `freelist::read_chain(head, backend, cache, page_count) -> Vec`: verifies each + page and bounds the walk by `page_count`. A cycle, an id < 2 or an id ≥ `page_count` + gives STG-035. +- [ ] Tests: round trip at 0, 1, 508, 509 and 5 000 ids; a cycle → STG-035. + +### Task 6: FileBackend format-agnostic + +- [ ] Drop the `header` field and `read_header`/`write_header`. `page_count = len / + PAGE_SIZE`, tracked in memory and bumped on append. `read_page` past it → INT-049. +- [ ] New file: create, `sync_parent_dir`, no page written. `is_new = page_count == 0`. +- [ ] `MemoryBackend::is_new` returns `page_count == 0`. +- [ ] Update `file.rs` tests. Header-validation tests move to Task 8. + +### Task 7: WAL v2 + +- [ ] `WAL_VERSION = 2`. `base_generation u64` at header bytes 8..16. + `WalWriter::open_or_create(path, sync, base_generation)` writes it on create. An + existing file keeps its header. +- [ ] `WalReader::base_generation() -> u64`. A v1 header reads as 1: a v1 WAL can only + sit next to a migrated file whose generation-2 commit has not finished. + Other versions → WAL-002. +- [ ] `db.rs`: read the WAL header (if the file exists) before + `PersistentFactStorage::open`, and pass `Option`. A lazily created WAL takes + `pfs.generation()`. +- [ ] Tests: v2 round trip; v1 file → 1; version 3 → WAL-002. + +### Task 8: Open and meta selection + +- [ ] `PersistentFactStorage::open(backend, cache_cap, wal_base: Option)` + replaces the load branch of `new`: + 1. `page_count == 0`, or neither slot valid with `page_count ≤ 2` and no v7 + header: write an empty generation-1 meta to page 0, sync. + 2. Both valid: the higher generation wins. + 3. One valid at `g`: apply the §4.1.1 table. The evidence search reads `M_g`'s free + list and pages `M_g.page_count..page_count` raw, and looks for a page that passes + `verify` with generation `g + 1`. + 4. Neither valid: a v7 header → Task 10 migration. Otherwise, a valid generation-1 + meta in the last page whose `page_count` equals the file's → copy it to page 0, + sync, continue. Otherwise STG-032. +- [ ] Wire the readers from the chosen meta and set the cache generation bound. Delete + `index_checksum`, `fact_prefix_crc`, `compute_*_checksum`, `hash_pages` and the + rebuild-on-open branch. `FileHeader` becomes `LegacyHeaderV7` (read-only, migration + only). +- [ ] Tests, one per row: both valid; torn newer slot with WAL base `g` (open at `g`, + replay); WAL base `> g` → STG-033; no WAL with a `g+1` page on the free list → STG-033; + no WAL with a `g+1` page past `page_count` → STG-033; no WAL and no evidence → open at + `g`; `g == 1` with slot B empty; unknown feature bit → STG-034 and the file bytes are + unchanged; pre-release v8 single header → STG-032; an error path never modifies the + file. + +### Task 9: `save()` — full rewrite, atomic + +- [ ] Steps: + 1. Set `g' = g + 1` and build the allocator from `read_chain(M.freelist_head)` and + `M.page_count`. + 2. Append fact pages for the pending facts. + 3. Rebuild the four trees through the allocator. + 4. `freed` = every page of `M`'s trees plus `M`'s chain pages. The new list is the + unused part of `M`'s free list plus `freed`. `write_chain` allocates its pages from + that unused part, or by appending. + 5. Sync. Write meta `g'` to `slot_page(g')`. Sync. + 6. Swap the readers, set `M = M'`, raise the cache bound, and clear pending. +- [ ] Concurrent queries hold `M`'s roots. They never read a page that `save` writes, + which follows from §8.1. +- [ ] Test guard: `WriteLog` (a test backend recording written ids) asserts that no + written id is reachable from `M`. Run it in the existing save tests. +- [ ] Invariant helper (`#[cfg(test)]`): the pages reachable from the trees plus the + fact pages plus the chain pages, together with the free ids, are disjoint and cover + `2..page_count`. Check it after each save in the multi-save tests. +- [ ] `stream_all` via EAVT page ids (see Shape decisions). + +### Task 10: v7 migration + +- [ ] Detection: a page 0 whose `LegacyHeaderV7` parses with version 7 and a valid + header CRC. +- [ ] Steps (§9 with interim pages): + 1. Read the facts through `legacy_v7`. + 2. Append 0x41 fact pages and four trees from `old_page_count`. + 3. Set the free list to `2..old_page_count`, plus the backup page id. + 4. Append the backup meta. + 5. Sync, write page 0, sync. +- [ ] A WAL next to the v7 file is replayed after migration. Its v1 header reads as + base 1. +- [ ] Tests: the existing `v7_header_forces_rebuild_and_upgrades_to_v8` and + `v7_migration_does_not_rewind_tx_counter…`; a crash at every write/sync of migration + leaves either the v7 file or a v8 file with every fact; a torn page-0 write recovers + from the backup. + +### Task 11: Torn writes and crash tests + +- [ ] `FaultConfig::torn_write_at: Option<(u64, usize)>`: at write number `n`, write + the first `k` bytes of the new page over the old one, then fail. +- [ ] Extend `crash_at_every_point_in_save_loses_no_checkpointed_fact`: for each write + index, a failure and torn writes at `k ∈ {0, 512, 4095}`, including the meta write. + After each: reopen with no rebuild, check the facts against the model, replay the + WAL, and run the invariant helper. +- [ ] Browser: confirm that `BrowserDb`'s flush writes page 0/1 in the same + `write_pages` call as the data pages. A test asserts that the dirty set after + `save()` holds the meta page. + +### Task 12: Docs and CI + +- [ ] `CHANGELOG.md` Unreleased (format v8 header, meta pages, WAL v2, `MAX_FACT_BYTES` + is 12 bytes smaller), `docs/ERROR_REFERENCE.md`, `docs/TEST_COVERAGE.md`, the + `CLAUDE.md` test count, and the `CLAUDE.md` File Format section, which describes the + interim layout. +- [ ] `cargo fmt`, `cargo clippy --all-targets -- -D warnings`, `cargo test`, and + `cargo bench --bench minigraf_bench -- checkpoint` against v3 (a regression is expected + until PR 4; record it). +- [ ] Open the PR into `v3` with `Refs #374 #388 #434`. Own CI until it is green. Ask the + user before merging. # PR 3 — Covering keys and dictionaries (outline) @@ -170,7 +375,7 @@ Spec §4.3, §5, §6, §9. The format freezes after this PR. - DICT tree with tags 0x01–0x06. Id assignment at transact time in WAL order (`FactStorage` pending index keyed by encoded keys). `next_eid`/`next_iid` in the meta page. - Value pages with dedup. `MAX_VALUE_BYTES` replaces `MAX_FACT_BYTES`. - Covering reads: `CommittedIndexReader` returns facts, translating ids through cached DICT lookups. Delete `FactRef`, fact pages, `CommittedFactReader`. -- v7 migration with a backup meta page, and crash tests. +- Retarget PR 2's v7 migration to covering keys, DICT and value pages; keep its crash tests. - Audit of result-order assumptions in tests and bindings. # PR 4 — Copy-on-write insert, allocator, free list (outline) diff --git a/docs/superpowers/specs/2026-10-05-v8-storage-format-design.md b/docs/superpowers/specs/2026-10-05-v8-storage-format-design.md index e8af4e5128..7f4a60c69d 100644 --- a/docs/superpowers/specs/2026-10-05-v8-storage-format-design.md +++ b/docs/superpowers/specs/2026-10-05-v8-storage-format-design.md @@ -127,9 +127,15 @@ Sidecar .wal — header gains base_generation (§4.1.1); entries unchang ### 4.1 Meta pages -Each checkpoint writes the inactive slot, `slot = generation % 2`. On open, both slots +Each checkpoint writes the inactive slot: odd generations go to page 0 (slot A) and even +generations to page 1 (slot B), so `slot = (generation − 1) % 2`. On open, both slots are read and one is chosen by §4.1.1. +A new file is created with an empty generation-1 meta in slot A, synced before anything +else is written, so every file that can hold committed data has a valid meta. If +neither slot is valid and the file has at most two pages, no commit can have written +data (every commit with data writes a page ≥ 2), and open initialises the file again. + | offset | field | notes | |---|---|---| | 0..4 | magic `"MGRF"` | | @@ -175,7 +181,11 @@ with two extra facts: 1. **WAL `base_generation`.** The WAL header records the generation of the meta that was active when the WAL file was created; it is reserved bytes today, so this is WAL version 2. A WAL is deleted only after a commit is durable, so an interrupted - commit of `g+1` always leaves a WAL with `base_generation == g`. + commit of `g+1` always leaves a WAL with `base_generation ≤ g`. The base can be + below `g` when a crash came between a commit and the WAL delete: the reopened + session keeps appending to that WAL, which still holds every fact not in `g`. + A version 1 WAL (v2.x) can only sit next to a migrated file whose generation-2 + commit has not finished, so it reads as base generation 1. 2. **Evidence of `g+1` in the data pages.** Generation `g+1` can only have written to pages on `M_g`'s free list or at or above `M_g.page_count` (§8.1). A valid page in one of those places stamped `generation == g+1` means `g+1` wrote its data. A @@ -185,7 +195,7 @@ with two extra facts: | WAL | page stamped `g+1` where `g+1` could write | meaning | action | |---|---|---|---| -| `base_generation == g` | any | torn commit of `g+1`, or the older slot was damaged | open at `g`, replay the WAL | +| `base_generation ≤ g` | any | torn commit of `g+1`, or the older slot was damaged | open at `g`, replay the WAL | | `base_generation > g` | any | a later commit existed and its meta is lost | error: meta damaged after commit | | none | found | `g+1` committed (its WAL was deleted), then its meta rotted | error: meta damaged after commit | | none | not found | the older slot was damaged, or `g == 1` with B empty | open at `g` | @@ -255,6 +265,10 @@ fails the type check before the CRC is computed. #373's verify and salvage can c any page from its first byte, and v7 migration never confuses an old page with a new one. Retired values stay reserved and are never reassigned. +During development, between delivery PRs 2 and 3 (§14), fact pages still exist and use +the interim type 0x41 with this header. Files carrying it are pre-release and are +rejected like any other pre-release v8 file. 0x41 is retired with them. + ### 4.3 B+tree nodes Leaves have no sibling pointer. With copy-on-write, a `next_leaf` pointer means changing @@ -444,7 +458,7 @@ several pages can come later behind a feature bit. ## 8. Checkpoint Let `M` be the active meta, with generation `g`. The new checkpoint commits generation -`g' = g + 1` into slot `g' % 2`. +`g' = g + 1` into slot `(g' − 1) % 2`. ### 8.1 Invariant @@ -488,7 +502,7 @@ never freed. A test pins this down (§11). 5. **Data sync.** All pages above have been written, each stamped with `g'` and its CRC. Call `backend.sync()`. 6. **Commit.** Write meta `g'` (with the new roots, `next_eid` and `next_iid`) to slot - `g' % 2`, then call `backend.sync()`. This is the only commit point. + `(g' − 1) % 2`, then call `backend.sync()`. This is the only commit point. 7. **Publish.** Swap the in-memory readers to the new roots and clear the pending facts. Then delete the WAL in `do_checkpoint`, as today. @@ -640,9 +654,10 @@ TDD per component. No new dependencies. Test assert messages follow the CodeQL r - New STG codes: page checksum mismatch, page id mismatch, page generation ahead of meta, no valid meta page, meta damaged after commit (§4.1.1), unsupported file - feature (§4.1.2), free-list/allocator inconsistency. The codes for the removed paths - (header CRC mismatch `INT-053`, index rebuild) stay registered and are marked - deprecated, never recycled. Update `docs/ERROR_REFERENCE.md`. + feature (§4.1.2), free-list/allocator inconsistency. A page that does not start with + the magic in either meta slot is still `STG-002`. `INT-053` (header CRC mismatch) + stays in use for a v7 header whose own CRC fails, so it is not deprecated. Codes are + never recycled. Update `docs/ERROR_REFERENCE.md`. - WAL format version 2: the header gains `base_generation u64` at bytes 8..16, taken from the reserved bytes. A v1 WAL is accepted only next to a v7 file being migrated. - Public API: `MAX_FACT_BYTES` → `MAX_VALUE_BYTES` (§6.3). Committed scan order changes @@ -689,10 +704,12 @@ TDD per component. No new dependencies. Test assert messages follow the CodeQL r 1. **Cursor scans:** add `LeafCursor` with `seek` and move every scan onto it, still on the current format. Behaviour does not change. 2. **v8 page format:** common page header with CRC/id/generation, verify on read, meta - pages A/B with meta selection, feature bits, WAL v2. `save()` still does a full - rebuild into fresh pages, which is atomic but O(N). (#388, #374 atomicity) + pages A/B with meta selection, feature bits, WAL v2, a full-rewrite free list, and + v7 migration with the backup meta (page 0 changes here, so migration must too). + `save()` rebuilds the trees into pages the active meta does not reference, which + is atomic but O(N). (#388, #374 atomicity) 3. **Covering keys (#433):** byte-comparable key encoding, prefix-compressed nodes, DICT, - value pages, eid/iid assignment, covering reads, v7 migration. + value pages, eid/iid assignment, covering reads; migration moves to the new keys. 4. **Copy-on-write insert, allocator, free list:** O(change) checkpoints. (#434) 5. **Cost and crash test hardening, benchmarks, docs.** diff --git a/src/browser/buffer.rs b/src/browser/buffer.rs index d170390a2c..a7f71f2acb 100644 --- a/src/browser/buffer.rs +++ b/src/browser/buffer.rs @@ -84,8 +84,10 @@ impl StorageBackend for BrowserBufferBackend { Ok(()) // no-op: durability handled by IndexedDbBackend } + /// One past the highest page id held (0 when empty), like a file's length + /// in pages. fn page_count(&self) -> Result { - Ok(self.pages.len() as u64) + Ok(self.pages.keys().max().map_or(0, |m| m.saturating_add(1))) } fn close(&mut self) -> Result<()> { @@ -95,10 +97,6 @@ impl StorageBackend for BrowserBufferBackend { fn backend_name(&self) -> &'static str { "browser-buffer" } - - fn is_new(&self) -> bool { - self.pages.is_empty() - } } #[cfg(test)] @@ -134,12 +132,14 @@ mod tests { } #[test] - fn page_count_reflects_distinct_ids() { + fn page_count_is_high_water_mark() { let mut buf = BrowserBufferBackend::new(); buf.write_page(0, &page(0)).unwrap(); buf.write_page(1, &page(1)).unwrap(); buf.write_page(0, &page(2)).unwrap(); // overwrite assert_eq!(buf.page_count().unwrap(), 2); + buf.write_page(5, &page(3)).unwrap(); // sparse + assert_eq!(buf.page_count().unwrap(), 6); } #[test] @@ -159,15 +159,8 @@ mod tests { } #[test] - fn is_new_true_when_empty() { - assert!(BrowserBufferBackend::new().is_new()); - } - - #[test] - fn is_new_false_after_write() { - let mut buf = BrowserBufferBackend::new(); - buf.write_page(0, &page(0)).unwrap(); - assert!(!buf.is_new()); + fn empty_buffer_has_no_pages() { + assert_eq!(BrowserBufferBackend::new().page_count().unwrap(), 0); } #[test] diff --git a/src/db.rs b/src/db.rs index 95d34500a2..ad6ce92f04 100644 --- a/src/db.rs +++ b/src/db.rs @@ -401,23 +401,33 @@ impl Minigraf { fn open_with_options_inner(path: impl AsRef, opts: OpenOptions) -> Result { let db_path = path.as_ref().to_path_buf(); - // Open the main .graph file + // Derive WAL path: ".wal" + let wal_path = Self::wal_path_for(&db_path); + + // Open the main .graph file. The WAL's base generation (if a WAL exists) + // decides which meta page to trust when only one is valid. let backend = FileBackend::open_with(&db_path, opts.allow_unlocked)?; - let pfs = PersistentFactStorage::new(backend, opts.page_cache_size)?; + let wal_base = if wal_path.exists() { + crate::wal::WalReader::open(&wal_path)?.base_generation() + } else { + None + }; + let pfs = PersistentFactStorage::open(backend, opts.page_cache_size, wal_base)?; // Share the fact storage let fact_storage = pfs.storage().clone(); - // Derive WAL path: ".wal" - let wal_path = Self::wal_path_for(&db_path); - // Replay any existing WAL entries before opening the writer let wal_entry_count = Self::replay_wal(&wal_path, &fact_storage, &pfs)?; // Open the WAL writer only if the WAL file already exists from a previous session. // Otherwise, create it lazily on the first write. let wal = if wal_path.exists() { - Some(WalWriter::open_or_create(&wal_path, opts.synchronous)?) + Some(WalWriter::open_or_create_at( + &wal_path, + opts.synchronous, + pfs.generation(), + )?) } else { None }; @@ -1266,7 +1276,11 @@ impl<'a> WriteTransaction<'a> { // Lazily open the WAL writer if not already open. if wal.is_none() { let wal_path = Minigraf::wal_path_for(db_path); - *wal = Some(WalWriter::open_or_create(&wal_path, opts.synchronous)?); + *wal = Some(WalWriter::open_or_create_at( + &wal_path, + opts.synchronous, + pfs.generation(), + )?); } let wal_writer = wal.as_mut().ok_or_else(|| err_coded!(ErrorCode::Api009))?; diff --git a/src/error.rs b/src/error.rs index 17c19aa485..1531264236 100644 --- a/src/error.rs +++ b/src/error.rs @@ -169,6 +169,13 @@ pub(crate) enum ErrorCode { Stg026, Stg027, Stg028, + Stg029, + Stg030, + Stg031, + Stg032, + Stg033, + Stg034, + Stg035, Wal001, Wal002, Wal003, @@ -949,6 +956,48 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "Format version {} is no longer supported (oldest supported: {}). Open the file once with Minigraf v2.x to upgrade it to format v7, then open it with this version.", ErrorCategory::Storage, ), + ( + ErrorCode::Stg029, + "STG-029", + "Page {} checksum mismatch: the page is torn or corrupted", + ErrorCategory::Storage, + ), + ( + ErrorCode::Stg030, + "STG-030", + "Page id mismatch: requested page {} but the page records id {}", + ErrorCategory::Storage, + ), + ( + ErrorCode::Stg031, + "STG-031", + "Page {} has generation {}, newer than the committed generation {}", + ErrorCategory::Storage, + ), + ( + ErrorCode::Stg032, + "STG-032", + "No valid meta page: the file is not a Minigraf v7 or v8 database, or both meta pages are damaged", + ErrorCategory::Storage, + ), + ( + ErrorCode::Stg033, + "STG-033", + "Meta page damaged after commit: generation {} is valid but a later commit existed ({}). Opening would silently drop that checkpoint", + ErrorCategory::Storage, + ), + ( + ErrorCode::Stg034, + "STG-034", + "Unsupported file feature bits {}: the file was written by a newer Minigraf version", + ErrorCategory::Storage, + ), + ( + ErrorCode::Stg035, + "STG-035", + "Free list is inconsistent: {}", + ErrorCategory::Storage, + ), ( ErrorCode::Wal001, "WAL-001", @@ -1764,6 +1813,13 @@ mod tests { | ErrorCode::Stg026 | ErrorCode::Stg027 | ErrorCode::Stg028 + | ErrorCode::Stg029 + | ErrorCode::Stg030 + | ErrorCode::Stg031 + | ErrorCode::Stg032 + | ErrorCode::Stg033 + | ErrorCode::Stg034 + | ErrorCode::Stg035 | ErrorCode::Wal001 | ErrorCode::Wal002 | ErrorCode::Wal003 @@ -1956,6 +2012,13 @@ mod tests { ErrorCode::Stg026, ErrorCode::Stg027, ErrorCode::Stg028, + ErrorCode::Stg029, + ErrorCode::Stg030, + ErrorCode::Stg031, + ErrorCode::Stg032, + ErrorCode::Stg033, + ErrorCode::Stg034, + ErrorCode::Stg035, ErrorCode::Wal001, ErrorCode::Wal002, ErrorCode::Wal003, diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 97fd70877f..fe1939d09b 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -384,26 +384,8 @@ impl FactStorage { Ok(all.into_iter().filter(|f| f.is_asserted()).collect()) } - /// Clear all facts (for testing) - pub(crate) fn clear(&self) -> Result<()> { - let mut d = self - .data - .write() - .map_err(|_| err_coded!(ErrorCode::Int050, "data"))?; - d.facts.clear(); - d.pending_keys.clear(); - d.pending_indexes = Indexes::new(); - d.committed = None; - d.committed_index_reader = None; - self.tx_counter.store(0, Ordering::SeqCst); - Ok(()) - } - - /// Replace the pending in-memory indexes with a freshly rebuilt set. - /// - /// Used by `PersistentFactStorage` after detecting an index checksum - /// mismatch (e.g. after crash recovery). - #[allow(dead_code)] + /// Replace the pending in-memory indexes (tests install hand-built ones). + #[cfg(test)] pub(crate) fn replace_pending_indexes(&self, indexes: Indexes) { let mut d = self.data.write().unwrap_or_else(|e| e.into_inner()); d.pending_indexes = indexes; @@ -1488,9 +1470,6 @@ mod tests { fn stream_all(&self) -> anyhow::Result> { Ok(self.facts.clone()) } - fn committed_page_count(&self) -> u64 { - 1 - } } let storage = FactStorage::new(); @@ -1585,9 +1564,6 @@ mod tests { fn stream_all(&self) -> anyhow::Result> { Ok(self.facts.clone()) } - fn committed_page_count(&self) -> u64 { - 1 - } } let storage = FactStorage::new(); @@ -2169,9 +2145,6 @@ mod tests { fn stream_all(&self) -> anyhow::Result> { Ok(self.facts.clone()) } - fn committed_page_count(&self) -> u64 { - 1 - } } let storage = FactStorage::new(); diff --git a/src/storage/backend/fault_inject.rs b/src/storage/backend/fault_inject.rs index 7a19a6b321..00397fa60a 100644 --- a/src/storage/backend/fault_inject.rs +++ b/src/storage/backend/fault_inject.rs @@ -21,6 +21,10 @@ pub struct FaultConfig { pub fail_sync_after: Option, /// Fail `close` after this many successful calls. pub fail_close_after: Option, + /// When the write that `fail_write_after` fails is reached, first write the + /// leading `n` bytes of the new page over the old contents (a torn write), + /// then fail. `None` leaves the old page untouched. + pub torn_write_bytes: Option, write_count: u64, sync_count: u64, close_count: u64, @@ -60,8 +64,21 @@ impl StorageBackend for FaultInjectingBackend { fn write_page(&mut self, page_id: u64, data: &[u8]) -> Result<()> { let mut cfg = self.config.lock().unwrap(); let limit = cfg.fail_write_after; - FaultConfig::check_and_increment(&mut cfg.write_count, limit)?; + let torn = cfg.torn_write_bytes; + let result = FaultConfig::check_and_increment(&mut cfg.write_count, limit); drop(cfg); + if let Err(e) = result { + if let Some(n) = torn { + let mut page = self + .inner + .read_page(page_id) + .unwrap_or_else(|_| vec![0u8; data.len()]); + let n = n.min(data.len()).min(page.len()); + page[..n].copy_from_slice(&data[..n]); + self.inner.write_page(page_id, &page)?; + } + return Err(e); + } self.inner.write_page(page_id, data) } @@ -92,10 +109,6 @@ impl StorageBackend for FaultInjectingBackend { fn backend_name(&self) -> &'static str { "fault-injecting" } - - fn is_new(&self) -> bool { - self.inner.is_new() - } } #[cfg(test)] @@ -163,4 +176,19 @@ mod tests { "write should succeed after removing fault" ); } + + #[test] + fn torn_write_keeps_a_prefix_of_the_new_page() { + let (mut backend, config) = FaultInjectingBackend::with_config(MemoryBackend::new()); + backend.write_page(0, &vec![0x11; PAGE_SIZE]).unwrap(); + { + let mut cfg = config.lock().unwrap(); + cfg.fail_write_after = Some(1); + cfg.torn_write_bytes = Some(100); + } + assert!(backend.write_page(0, &vec![0x22; PAGE_SIZE]).is_err()); + let page = backend.read_page(0).unwrap(); + assert!(page[..100].iter().all(|&b| b == 0x22), "new prefix"); + assert!(page[100..].iter().all(|&b| b == 0x11), "old suffix"); + } } diff --git a/src/storage/backend/file.rs b/src/storage/backend/file.rs index f521ee292f..2674c2fe2b 100644 --- a/src/storage/backend/file.rs +++ b/src/storage/backend/file.rs @@ -1,7 +1,7 @@ /// File-based storage backend for native platforms. use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::storage::dir_sync::sync_parent_dir; -use crate::storage::{FileHeader, PAGE_SIZE, StorageBackend}; +use crate::storage::{PAGE_SIZE, StorageBackend}; use anyhow::Result; use std::fs::{File, OpenOptions}; use std::io::{Read, Seek, SeekFrom, Write}; @@ -140,8 +140,8 @@ const LOCK_RETRY_MAX_DELAY: std::time::Duration = std::time::Duration::from_mill /// File-based storage backend for native platforms. /// /// Stores graph data in a single `.graph` file with a page-based structure: -/// - Page 0: File header (metadata) -/// - Page 1+: Data pages (nodes, edges, indexes) +/// - Pages 0 and 1: meta pages (interpreted by the storage layer, not here) +/// - Page 2+: data pages (B+tree nodes, fact pages, free-list pages) /// /// Supports: /// - Linux, macOS, Windows (native desktop) @@ -160,15 +160,15 @@ pub struct FileBackend { // declared before `file`. _path_guard: PathGuard, file: File, - header: FileHeader, - is_new: bool, + /// Whole pages in the file. + page_count: u64, } impl FileBackend { /// Open or create a .graph file at the given path. /// - /// If the file doesn't exist, creates it with an initial header. - /// If it exists, validates and loads the header. + /// If the file doesn't exist, creates it empty. Interpreting page 0 is + /// left to the storage layer. /// /// Takes a kernel file lock on the `.graph` file itself, which prevents /// both multi-process corruption and a second handle within this process. @@ -195,7 +195,7 @@ impl FileBackend { pub fn open_with>(path: P, allow_unlocked: bool) -> Result { let path = path.as_ref().to_path_buf(); - let mut file = OpenOptions::new() + let file = OpenOptions::new() .read(true) .write(true) .create(true) @@ -260,82 +260,27 @@ impl FileBackend { } }; - // Check file size using the open file handle's metadata. - // This is more reliable than checking path metadata separately, - // as it uses the same file descriptor we'll be reading from. + // The page count is the file length in whole pages. A torn append can + // leave a partial last page; it is ignored, and the next append to that + // id rewrites it. Page 0 carries no meaning here: the meta pages are the + // storage layer's business. let file_len = file.metadata()?.len(); - - // Determine if this is an existing file with data or a new/empty one. - let is_new = file_len < PAGE_SIZE as u64; - let header = if file_len >= PAGE_SIZE as u64 { - // File has at least one page - try to read the header - match Self::read_header(&mut file) { - Ok(header) => header, - Err(e) => { - // File has content but header is invalid - this is a real error. - // If `e` already carries a more specific code (e.g. STG-002 for a - // bad magic number, raised inside `FileHeader::from_bytes`/ - // `validate`), propagate it as-is rather than burying it under - // the generic STG-010 label — `read_header` never wraps with - // `.context()`, so a coded error from deeper down comes back - // here unmodified and downcasts directly. - if e.downcast_ref::().is_some() { - return Err(e); - } - bail_coded!(ErrorCode::Stg010, e); - } - } - } else { - // New file or empty file: write initial header, then make the - // file's directory entry durable. Without the directory sync a - // power loss can lose the whole file despite the header fsync - // (#389). An empty file left by a crash before this point takes - // this branch again on the next open, so the sync is repeated. - let header = FileHeader::new(); - Self::write_header(&mut file, &header)?; + let page_count = file_len / PAGE_SIZE as u64; + if page_count == 0 { + // Make the new file's directory entry durable. Without the directory + // sync a power loss can lose the whole file despite later fsyncs + // (#389). An empty file left by a crash takes this branch again. sync_parent_dir(&path)?; - header - }; + } Ok(FileBackend { path, file, - header, - is_new, + page_count, _path_guard: path_guard, }) } - /// Read the file header from page 0. - fn read_header(file: &mut File) -> Result { - file.seek(SeekFrom::Start(0))?; - - let mut header_bytes = vec![0u8; PAGE_SIZE]; - file.read_exact(&mut header_bytes)?; - - let header = FileHeader::from_bytes(&header_bytes)?; - header.validate()?; - - Ok(header) - } - - /// Write the file header to page 0. - fn write_header(file: &mut File, header: &FileHeader) -> Result<()> { - file.seek(SeekFrom::Start(0))?; - - let header_bytes = header.to_bytes(); - let mut page = vec![0u8; PAGE_SIZE]; - let hlen = header_bytes.len(); - page.get_mut(..hlen) - .ok_or_else(|| err_coded!(ErrorCode::Int049, "header bytes exceed page size"))? - .copy_from_slice(&header_bytes); - - file.write_all(&page)?; - file.sync_all()?; - - Ok(()) - } - /// Get the file path. #[allow(dead_code)] pub fn path(&self) -> &Path { @@ -358,43 +303,25 @@ impl StorageBackend for FileBackend { self.file.seek(SeekFrom::Start(offset))?; self.file.write_all(data)?; - // If writing page 0 (header), update our in-memory header - if page_id == 0 { - // Page 0 is the header itself, parse it to update our cached copy - self.header = FileHeader::from_bytes(data)?; - } else if page_id >= self.header.page_count { - // Bump and persist the page count so a plain reopen (no - // deliberate commit in between) still sees pages written this - // session -- callers like `test_file_backend_persistence` - // depend on that. #308: the bug here was writing the bumped - // page_count with a *stale* header_checksum left over from the - // last real commit, so a crash before that commit finished left - // a permanently checksum-invalid header with no recovery path. - // The fix is to recompute the checksum over the whole header - // every time, so the on-disk header is self-consistent at - // every single-page write, not just at the deliberate commits - // in `PersistentFactStorage::save`. - self.header.page_count = page_id.checked_add(1).ok_or_else(|| { + if page_id >= self.page_count { + self.page_count = page_id.checked_add(1).ok_or_else(|| { err_coded!( ErrorCode::Int048, format!("page_count overflow for page_id {page_id}") ) })?; - self.header.header_checksum = - crate::storage::persistent_facts::compute_header_checksum(&self.header); - Self::write_header(&mut self.file, &self.header)?; } Ok(()) } fn read_page(&self, page_id: u64) -> Result> { - if page_id >= self.header.page_count { + if page_id >= self.page_count { bail_coded!( ErrorCode::Int049, format!( "Page {page_id} out of bounds (total pages: {})", - self.header.page_count + self.page_count ) ); } @@ -420,7 +347,7 @@ impl StorageBackend for FileBackend { } fn page_count(&self) -> Result { - Ok(self.header.page_count) + Ok(self.page_count) } fn close(&mut self) -> Result<()> { @@ -430,10 +357,6 @@ impl StorageBackend for FileBackend { fn backend_name(&self) -> &'static str { "file" } - - fn is_new(&self) -> bool { - self.is_new - } } #[cfg(all(test, not(target_arch = "wasm32")))] @@ -466,41 +389,36 @@ mod tests { FileBackend::open(&temp_path).unwrap(); } - /// #308: whenever `write_page` bumps `page_count` for a newly appended - /// page (exactly what `save()`/`checkpoint()` do for every fact and - /// index page, ahead of the deliberate final header commit), the header - /// it persists to disk must have a `header_checksum` matching its own - /// content. Before this fix, the page_count byte moved but the checksum - /// was left stale from the last real commit -- a `SIGKILL` landing in - /// that window (which fires on nearly every appended page) left a - /// permanently checksum-invalid header with no recovery path. + /// The page count is the file length in whole pages: appends bump it, it + /// survives a reopen, and a torn partial page at the end is not counted. + /// Page 0 is never parsed or rewritten by the backend (#308 cannot recur). #[test] - fn test_write_page_keeps_disk_header_checksum_consistent_on_page_count_bump() { + fn test_page_count_follows_file_length() { let dir = tempfile::tempdir().unwrap(); - let path = dir.path().join("test_header_atomicity.graph"); + let path = dir.path().join("test_page_count.graph"); + { + let mut backend = FileBackend::open(&path).unwrap(); + assert_eq!(backend.page_count().unwrap(), 0); + backend.write_page(5, &vec![0xABu8; PAGE_SIZE]).unwrap(); + assert_eq!(backend.page_count().unwrap(), 6); + assert!(backend.read_page(6).is_err(), "past the end must fail"); + // Page 0 is a hole the backend never fills in. + assert!(backend.read_page(0).unwrap().iter().all(|&b| b == 0)); + } + { + // Simulate a torn append: half a page past the end. + let mut f = std::fs::OpenOptions::new() + .append(true) + .open(&path) + .unwrap(); + std::io::Write::write_all(&mut f, &[0xCDu8; PAGE_SIZE / 2]).unwrap(); + } let mut backend = FileBackend::open(&path).unwrap(); - - // Append a page well beyond the current page_count (1) -- exactly - // the pattern save()/checkpoint() use when writing fact and index - // pages ahead of the final atomic header commit. - let page_data = vec![0xABu8; PAGE_SIZE]; - backend.write_page(5, &page_data).unwrap(); - - // Read back through the same handle rather than opening the path - // independently: `backend` still holds the file lock, and Windows - // (unlike Unix) refuses a second, unrelated open of a locked file - // even from the same process. - let raw = backend.read_page(0).unwrap(); - let on_disk = FileHeader::from_bytes(&raw).unwrap(); - let computed = crate::storage::persistent_facts::compute_header_checksum(&on_disk); - assert_eq!( - on_disk.header_checksum, computed, - "on-disk header checksum must match its own content after a page-count bump" - ); - assert_eq!(on_disk.page_count, 6); - - // In-memory bookkeeping must agree with what's now on disk. - assert_eq!(backend.page_count().unwrap(), 6); + assert!(backend.page_count().unwrap() > 0); + assert_eq!(backend.page_count().unwrap(), 6, "partial page not counted"); + backend.write_page(6, &vec![0x11u8; PAGE_SIZE]).unwrap(); + assert_eq!(backend.read_page(6).unwrap()[PAGE_SIZE - 1], 0x11); + assert_eq!(backend.page_count().unwrap(), 7); } /// The child half of [`test_cross_process_lock_retries_then_fails_within_budget`]: @@ -713,8 +631,12 @@ mod tests { let backend = FileBackend::open(&temp_path).unwrap(); assert_eq!(backend.backend_name(), "file"); - assert_eq!(backend.page_count().unwrap(), 1); // Header page - assert!(backend.is_new(), "newly created file should be new"); + assert_eq!(backend.page_count().unwrap(), 0); // nothing written yet + assert_eq!( + backend.page_count().unwrap(), + 0, + "newly created file is empty" + ); } #[test] @@ -723,21 +645,19 @@ mod tests { let temp_path = dir.path().join("test_minigraf_existing.graph"); { - let backend = FileBackend::open(&temp_path).unwrap(); - assert!(backend.is_new(), "first open should be new"); + let mut backend = FileBackend::open(&temp_path).unwrap(); + assert_eq!(backend.page_count().unwrap(), 0, "first open is empty"); + backend.write_page(0, &vec![1u8; PAGE_SIZE]).unwrap(); } { let backend = FileBackend::open(&temp_path).unwrap(); - assert!( - !backend.is_new(), - "reopening existing file should not be new" - ); + assert_eq!(backend.page_count().unwrap(), 1, "reopen sees the page"); } { let backend = FileBackend::open(&temp_path).unwrap(); - assert!(!backend.is_new(), "third open should still not be new"); + assert_eq!(backend.page_count().unwrap(), 1, "third open too"); } } @@ -749,7 +669,7 @@ mod tests { let mut backend = FileBackend::open(&temp_path).unwrap(); let data = vec![42u8; PAGE_SIZE]; - backend.write_page(1, &data).unwrap(); // Page 0 is header + backend.write_page(1, &data).unwrap(); let read_data = backend.read_page(1).unwrap(); assert_eq!(data, read_data); @@ -782,7 +702,7 @@ mod tests { let temp_path = dir.path().join("test_minigraf_page_count.graph"); let mut backend = FileBackend::open(&temp_path).unwrap(); - assert_eq!(backend.page_count().unwrap(), 1); + assert_eq!(backend.page_count().unwrap(), 0); backend.write_page(1, &vec![0u8; PAGE_SIZE]).unwrap(); assert_eq!(backend.page_count().unwrap(), 2); @@ -865,7 +785,7 @@ mod tests { // ── #389: parent-directory fsync ──────────────────────────────────────── #[test] - fn test_create_syncs_parent_dir_after_header_write() { + fn test_create_syncs_parent_dir() { use crate::storage::dir_sync::take_sync_log; let dir = tempfile::tempdir().unwrap(); let path = dir.path().join("new.graph"); @@ -896,7 +816,10 @@ mod tests { use crate::storage::dir_sync::take_sync_log; let dir = tempfile::tempdir().unwrap(); let path = dir.path().join("existing.graph"); - drop(FileBackend::open(&path).unwrap()); + FileBackend::open(&path) + .unwrap() + .write_page(0, &vec![1u8; PAGE_SIZE]) + .unwrap(); take_sync_log(); let backend = FileBackend::open(&path).unwrap(); diff --git a/src/storage/backend/memory.rs b/src/storage/backend/memory.rs index e1bf399824..5d7144d84c 100644 --- a/src/storage/backend/memory.rs +++ b/src/storage/backend/memory.rs @@ -26,9 +26,15 @@ impl MemoryBackend { } } - /// Get the number of pages stored. + /// One past the highest page id written (0 when empty), like a file's length + /// in pages. fn page_count_internal(&self) -> u64 { - self.pages.read().unwrap_or_else(|e| e.into_inner()).len() as u64 + self.pages + .read() + .unwrap_or_else(|e| e.into_inner()) + .keys() + .max() + .map_or(0, |m| m.saturating_add(1)) } } @@ -80,10 +86,6 @@ impl StorageBackend for MemoryBackend { fn backend_name(&self) -> &'static str { "memory" } - - fn is_new(&self) -> bool { - true - } } #[cfg(test)] diff --git a/src/storage/backend/mod.rs b/src/storage/backend/mod.rs index f24e835c18..fd8bf92ab4 100644 --- a/src/storage/backend/mod.rs +++ b/src/storage/backend/mod.rs @@ -7,7 +7,7 @@ pub mod file; #[cfg(test)] pub mod fault_inject; #[cfg(test)] -pub use fault_inject::{FaultConfig, FaultInjectingBackend}; +pub use fault_inject::FaultInjectingBackend; // Future: WASM backend // #[cfg(target_arch = "wasm32")] diff --git a/src/storage/btree_v6.rs b/src/storage/btree_v6.rs index 47f523b44d..bbeb22795e 100644 --- a/src/storage/btree_v6.rs +++ b/src/storage/btree_v6.rs @@ -15,17 +15,17 @@ use std::sync::Mutex; // ─── Page type constants ─────────────────────────────────────────────────────── -/// Leaf node page type (v6). -pub const PAGE_TYPE_LEAF: u8 = 0x21; -/// Internal node page type (v6). -pub const PAGE_TYPE_INTERNAL: u8 = 0x22; +use crate::storage::page::{PAGE_HEADER_SIZE, PageAllocator}; +pub use crate::storage::page::{PAGE_TYPE_INTERNAL, PAGE_TYPE_LEAF}; // ─── Fixed sizes ────────────────────────────────────────────────────────────── -/// Leaf page fixed header: type(1) + reserved(1) + entry_count(2) + next_leaf(8) = 12 bytes. -const LEAF_HEADER_SIZE: usize = 12; -/// Internal page fixed header: type(1) + reserved(1) + key_count(2) + rightmost_child(8) = 12 bytes. -const INTERNAL_HEADER_SIZE: usize = 12; +/// Leaf page fixed header: the common page header (entry count in `count`). +const LEAF_HEADER_SIZE: usize = PAGE_HEADER_SIZE; +/// Offset of an internal node's `rightmost_child` (u64), right after the common header. +const RIGHTMOST_CHILD_OFFSET: usize = PAGE_HEADER_SIZE; +/// Internal page fixed header: common header (key count in `count`) + rightmost_child(8). +const INTERNAL_HEADER_SIZE: usize = PAGE_HEADER_SIZE + 8; /// Slot directory entry: offset(u16) + length(u16) = 4 bytes. const SLOT_SIZE: usize = 4; /// Fill-factor threshold: stop packing once total used bytes exceed this (~75% of PAGE_SIZE). @@ -66,22 +66,24 @@ fn read_u64_at(page: &[u8], offset: usize) -> Result { /// `entries`: each element is the postcard-serialised `(K, FactRef)` bytes for /// one index entry, in sort order. #[allow(clippy::arithmetic_side_effects, clippy::indexing_slicing)] -fn encode_leaf_page(entries: &[Vec], next_leaf: u64) -> Result> { +fn encode_leaf_page(entries: &[Vec]) -> Result> { let entry_count = u16::try_from(entries.len()).map_err(|_| { err_coded!( ErrorCode::Int049, format!("too many entries: {}", entries.len()) ) })?; - let mut page = vec![0u8; PAGE_SIZE]; - - // Fixed header - page[0] = PAGE_TYPE_LEAF; - page[1] = 0; // reserved - page[2..4].copy_from_slice(&entry_count.to_le_bytes()); - page[4..12].copy_from_slice(&next_leaf.to_le_bytes()); + let used = + LEAF_HEADER_SIZE + entries.len() * SLOT_SIZE + entries.iter().map(Vec::len).sum::(); + if used > PAGE_SIZE { + bail_coded!( + ErrorCode::Int049, + format!("leaf entries need {used} bytes, more than a page") + ); + } + let mut page = crate::storage::page::new_page(PAGE_TYPE_LEAF, entry_count); - // Slot directory starts at byte 12; data written end-to-start + // Slot directory follows the header; data written end-to-start let mut write_pos = PAGE_SIZE; for (i, entry) in entries.iter().enumerate() { write_pos -= entry.len(); @@ -105,21 +107,20 @@ fn encode_leaf_page(entries: &[Vec], next_leaf: u64) -> Result> { Ok(page) } -/// Write a single leaf page and insert it into the cache. +/// Write a single leaf page at a newly allocated id and insert it into the cache. fn write_leaf_page( backend: &mut dyn StorageBackend, cache: &PageCache, - page_id: u64, + alloc: &mut PageAllocator, entries: &[Vec], - next_leaf: u64, -) -> Result<()> { - let page = encode_leaf_page(entries, next_leaf)?; - backend.write_page(page_id, &page)?; - cache.put_dirty(page_id, page); - Ok(()) +) -> Result { + let page = encode_leaf_page(entries)?; + let page_id = alloc.alloc()?; + alloc.write(backend, cache, page_id, page)?; + Ok(page_id) } -/// Write a single internal node page and insert it into the cache. +/// Write a single internal node page at a newly allocated id and insert it into the cache. /// /// `child_ids`: all child page IDs in order; the last one is `rightmost_child`. /// `sep_bytes`: postcard-serialised Key bytes for each separator key. @@ -129,10 +130,10 @@ fn write_leaf_page( fn write_internal_page( backend: &mut dyn StorageBackend, cache: &PageCache, - page_id: u64, + alloc: &mut PageAllocator, child_ids: &[u64], sep_bytes: &[Vec], -) -> Result<()> { +) -> Result { debug_assert_eq!(child_ids.len(), sep_bytes.len() + 1); // Defensive check: empty child_ids would cause panic on .last() if child_ids.is_empty() { @@ -148,15 +149,20 @@ fn write_internal_page( .last() .ok_or_else(|| err_coded!(ErrorCode::Int049, "child_ids is empty".to_string()))?; - let mut page = vec![0u8; PAGE_SIZE]; - - // Fixed header - page[0] = PAGE_TYPE_INTERNAL; - page[1] = 0; // reserved - page[2..4].copy_from_slice(&key_count.to_le_bytes()); - page[4..12].copy_from_slice(&rightmost_child.to_le_bytes()); + let used = INTERNAL_HEADER_SIZE + + sep_bytes.len() * (8 + SLOT_SIZE) + + sep_bytes.iter().map(Vec::len).sum::(); + if used > PAGE_SIZE { + bail_coded!( + ErrorCode::Int049, + format!("internal node needs {used} bytes, more than a page") + ); + } + let mut page = crate::storage::page::new_page(PAGE_TYPE_INTERNAL, key_count); + page[RIGHTMOST_CHILD_OFFSET..RIGHTMOST_CHILD_OFFSET + 8] + .copy_from_slice(&rightmost_child.to_le_bytes()); - // Child array: key_count entries starting at byte 12 + // Child array: key_count entries after the fixed header let child_arr_start = INTERNAL_HEADER_SIZE; for (i, &cid) in child_ids[..child_ids.len() - 1].iter().enumerate() { let off = child_arr_start + i * 8; @@ -188,9 +194,9 @@ fn write_internal_page( page[slot_off + 2..slot_off + 4].copy_from_slice(&sep_len_u16.to_le_bytes()); } - backend.write_page(page_id, &page)?; - cache.put_dirty(page_id, page); - Ok(()) + let page_id = alloc.alloc()?; + alloc.write(backend, cache, page_id, page)?; + Ok(page_id) } /// True when adding an entry of `entry_len` bytes to a leaf that already holds @@ -227,8 +233,8 @@ pub fn btree_entries( /// Each item in `sorted_entries` is `(entry_bytes, key_bytes)` as produced by /// [`btree_entries`]. Entries **must already be sorted** by key. /// -/// Returns `(root_page_id, next_free_page_id)`. Chain multiple calls: -/// pass the returned `next_free_page_id` as `start_page_id` for the next index. +/// Pages are taken from `alloc` and stamped with its generation. Returns the +/// root page id. /// /// All written pages are inserted into `cache` via `put_dirty`. #[allow(clippy::arithmetic_side_effects, clippy::indexing_slicing)] @@ -236,29 +242,27 @@ pub fn build_btree( sorted_entries: impl Iterator, Vec)>, backend: &mut dyn StorageBackend, cache: &PageCache, - start_page_id: u64, -) -> Result<(u64, u64)> { + alloc: &mut PageAllocator, +) -> Result { // ── Phase 1: pack entries into leaf pages ───────────────────────────────── let mut leaf_infos: Vec<(u64, Vec)> = Vec::new(); let mut cur_entries: Vec> = Vec::new(); let mut cur_data_bytes: usize = 0; let mut cur_first_key: Option> = None; - let mut next_page = start_page_id; for (entry_bytes, key_bytes) in sorted_entries { if !cur_entries.is_empty() && leaf_overflows(cur_entries.len(), cur_data_bytes, entry_bytes.len()) { - write_leaf_page(backend, cache, next_page, &cur_entries, 0)?; + let page_id = write_leaf_page(backend, cache, alloc, &cur_entries)?; let first_key = cur_first_key.take().ok_or_else(|| { err_coded!( ErrorCode::Int049, "BUG: cur_first_key empty when writing leaf page".to_string() ) })?; - leaf_infos.push((next_page, first_key)); - next_page += 1; + leaf_infos.push((page_id, first_key)); cur_entries.clear(); cur_data_bytes = 0; cur_first_key = None; @@ -274,88 +278,52 @@ pub fn build_btree( // Flush the last (or only) batch if cur_entries.is_empty() && leaf_infos.is_empty() { // Empty tree: single empty leaf - write_leaf_page(backend, cache, next_page, &[], 0)?; - return Ok((next_page, next_page + 1)); + return write_leaf_page(backend, cache, alloc, &[]); } if !cur_entries.is_empty() { - write_leaf_page(backend, cache, next_page, &cur_entries, 0)?; + let page_id = write_leaf_page(backend, cache, alloc, &cur_entries)?; let first_key = cur_first_key.take().ok_or_else(|| { err_coded!( ErrorCode::Int049, "BUG: cur_first_key empty when flushing last leaf page".to_string() ) })?; - leaf_infos.push((next_page, first_key)); - next_page += 1; - } - - // Patch next_leaf pointers: leaf[i].next_leaf = leaf[i+1].page_id - for i in 0..leaf_infos.len() - 1 { - let (pid, _) = leaf_infos - .get(i) - .ok_or_else(|| err_coded!(ErrorCode::Int049, format!("leaf_infos[{i}] out of bounds")))? - .clone(); - let (next_lid, _) = leaf_infos - .get(i + 1) - .ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - format!("leaf_infos[{}] out of bounds", i + 1) - ) - })? - .clone(); - let cached = cache.get_or_load(pid, backend)?; - let mut page = (*cached).clone(); - // Safety: page is PAGE_SIZE bytes; offset 4..12 is always valid - page.get_mut(4..12) - .ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - "page too small to write next_leaf".to_string() - ) - })? - .copy_from_slice(&next_lid.to_le_bytes()); - backend.write_page(pid, &page)?; - cache.put_dirty(pid, page); + leaf_infos.push((page_id, first_key)); } - build_internal_levels(leaf_infos, backend, cache, next_page) + build_internal_levels(leaf_infos, backend, cache, alloc) } /// Build internal levels bottom-up over `leaf_infos` (`(page_id, first_key_bytes)` -/// per leaf, in key order), writing nodes from `next_page` onward. +/// per leaf, in key order), writing nodes at ids taken from `alloc`. /// -/// Returns `(root_page_id, next_free_page_id)`. A single leaf is its own root. +/// Returns the root page id. A single leaf is its own root. #[allow(clippy::arithmetic_side_effects, clippy::indexing_slicing)] fn build_internal_levels( leaf_infos: Vec<(u64, Vec)>, backend: &mut dyn StorageBackend, cache: &PageCache, - next_page: u64, -) -> Result<(u64, u64)> { + alloc: &mut PageAllocator, +) -> Result { if leaf_infos.is_empty() { bail_coded!( ErrorCode::Int049, "build_internal_levels: no leaves".to_string() ); } - let mut next_page = next_page; let mut current_level = leaf_infos; loop { if current_level.len() == 1 { - return Ok(( - current_level - .first() - .ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - "current_level unexpectedly empty".to_string() - ) - })? - .0, - next_page, - )); + return Ok(current_level + .first() + .ok_or_else(|| { + err_coded!( + ErrorCode::Int049, + "current_level unexpectedly empty".to_string() + ) + })? + .0); } let mut next_level: Vec<(u64, Vec)> = Vec::new(); @@ -408,9 +376,7 @@ fn build_internal_levels( i += 1; } - let node_page_id = next_page; - write_internal_page(backend, cache, node_page_id, &child_ids, &sep_bytes)?; - next_page += 1; + let node_page_id = write_internal_page(backend, cache, alloc, &child_ids, &sep_bytes)?; let first_key = current_level .get(i_start) @@ -454,14 +420,14 @@ pub fn merge_sorted_vecs(a: Vec, b: Vec) -> impl Iterator>, ) -> Result>>> { // A tree cannot have more nodes than the file has pages; more visits // means a cycle in the child pointers. @@ -480,6 +446,9 @@ pub fn collect_leaf_pages( ); } let page = cache.get_or_load(page_id, backend)?; + if let Some(nodes) = nodes_out.as_deref_mut() { + nodes.push(page_id); + } match page.first().copied() { Some(PAGE_TYPE_LEAF) => { validate_leaf_slots(&page[..], page_id)?; @@ -502,8 +471,9 @@ pub fn collect_leaf_pages( /// Check a leaf's slot directory stays inside the page without decoding entries. /// -/// Untouched leaves are copied verbatim and sealed under a fresh file checksum, -/// so damage must be caught here instead of being carried forward. +/// Untouched leaves are copied verbatim and resealed under a new page id and +/// generation, so damage the page CRC cannot see must be caught here instead of +/// being carried forward. #[allow(clippy::arithmetic_side_effects)] fn validate_leaf_slots(page: &[u8], page_id: u64) -> Result<()> { let count = read_u16_at(page, 2)? as usize; @@ -551,51 +521,25 @@ where Ok(Some(key)) } -/// Writes leaf pages at consecutive page ids, linking each to the next. -/// -/// One page is held back so its `next_leaf` can be set to the following page -/// id, or to 0 once it is known to be the last leaf. +/// Writes leaf pages at ids taken from an allocator, recording each leaf's id and +/// first key for [`build_internal_levels`]. struct LeafEmitter<'a> { backend: &'a mut dyn StorageBackend, cache: &'a PageCache, - next_page: u64, - held: Option<(u64, Vec)>, + alloc: &'a mut PageAllocator, infos: Vec<(u64, Vec)>, } impl LeafEmitter<'_> { - #[allow(clippy::arithmetic_side_effects)] + /// Write `page` (header type/count and body set; id, generation and CRC are + /// stamped here) at a new id. fn push(&mut self, page: Vec, first_key_bytes: Vec) -> Result<()> { - let page_id = self.next_page; - self.next_page += 1; - self.release_held(page_id)?; - self.held = Some((page_id, page)); + let page_id = self.alloc.alloc()?; + self.alloc + .write(&mut *self.backend, self.cache, page_id, page)?; self.infos.push((page_id, first_key_bytes)); Ok(()) } - - fn release_held(&mut self, next_leaf: u64) -> Result<()> { - if let Some((page_id, mut page)) = self.held.take() { - page.get_mut(4..12) - .ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - "page too small to write next_leaf".to_string() - ) - })? - .copy_from_slice(&next_leaf.to_le_bytes()); - self.backend.write_page(page_id, &page)?; - self.cache.put_dirty(page_id, page); - } - Ok(()) - } - - /// Write the last held leaf and return `(leaf_infos, next_free_page_id)`. - #[allow(clippy::type_complexity)] - fn finish(mut self) -> Result<(Vec<(u64, Vec)>, u64)> { - self.release_held(0)?; - Ok((self.infos, self.next_page)) - } } /// Serialise sorted entries and emit them as leaves. @@ -637,7 +581,7 @@ fn emit_packed( let first = cur_first.take().ok_or_else(|| { err_coded!(ErrorCode::Int049, "BUG: leaf without first key".to_string()) })?; - emitter.push(encode_leaf_page(&cur, 0)?, first)?; + emitter.push(encode_leaf_page(&cur)?, first)?; cur.clear(); cur_size = 0; } @@ -648,28 +592,29 @@ fn emit_packed( cur.push(entry); } if let Some(first) = cur_first { - emitter.push(encode_leaf_page(&cur, 0)?, first)?; + emitter.push(encode_leaf_page(&cur)?, first)?; } Ok(()) } /// Rebuild a B+tree from its old leaves plus sorted `pending` entries. /// -/// Leaves that receive no pending entry are copied verbatim (only `next_leaf` -/// is patched); only leaves that do are decoded, merged and repacked. Internal +/// Leaves that receive no pending entry are copied verbatim (only the page id, +/// generation and CRC are restamped); only leaves that do are decoded, merged +/// and repacked. Internal /// levels are rebuilt from scratch. Pending keys route to leaf `i` when /// `first_key[i] <= key < first_key[i + 1]`; keys below the first leaf's first /// key go to leaf 0. With no non-empty old leaves this is a plain bulk build. /// -/// `old_leaves` must be snapshotted (see [`collect_leaf_pages`]) before any -/// page in `start_page_id..` is written. Returns `(root_page_id, next_free_page_id)`. +/// Every page is written at an id from `alloc`, which never hands out a page +/// the old tree uses. Returns the root page id. pub fn rebuild_btree_incremental( old_leaves: Vec>>, pending: Vec<(K, FactRef)>, backend: &mut dyn StorageBackend, cache: &PageCache, - start_page_id: u64, -) -> Result<(u64, u64)> + alloc: &mut PageAllocator, +) -> Result where K: Serialize + for<'de> Deserialize<'de> + Ord, { @@ -684,15 +629,14 @@ where btree_entries(pending.into_iter())?.into_iter(), backend, cache, - start_page_id, + alloc, ); } let mut emitter = LeafEmitter { backend: &mut *backend, cache, - next_page: start_page_id, - held: None, + alloc: &mut *alloc, infos: Vec::new(), }; let mut pending = pending.into_iter().peekable(); @@ -714,46 +658,12 @@ where emit_packed(&mut emitter, merge_sorted_vecs(old, batch))?; } } - let (leaf_infos, next_page) = emitter.finish()?; - build_internal_levels(leaf_infos, backend, cache, next_page) + let leaf_infos = emitter.infos; + build_internal_levels(leaf_infos, backend, cache, alloc) } // ─── Leaf traversal helpers ─────────────────────────────────────────────────── -/// Traverse internal nodes from `root` to find the leftmost (first) leaf page. -#[cfg(test)] -#[allow(clippy::arithmetic_side_effects)] -fn find_leftmost_leaf(root: u64, backend: &dyn StorageBackend, cache: &PageCache) -> Result { - let mut page_id = root; - loop { - let page = cache.get_or_load(page_id, backend)?; - let page_type = page.first().copied().ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - format!("empty page at page_id={page_id}") - ) - })?; - match page_type { - PAGE_TYPE_LEAF => return Ok(page_id), - PAGE_TYPE_INTERNAL => { - let key_count = read_u16_at(&page[..], 2)? as usize; - if key_count == 0 { - page_id = read_u64_at(&page[..], 4)?; - } else { - page_id = read_u64_at(&page[..], INTERNAL_HEADER_SIZE)?; - } - } - t => bail_coded!( - ErrorCode::Int049, - format!( - "find_leftmost_leaf: unexpected page type 0x{:02x} at page_id={}", - t, page_id - ) - ), - } - } -} - /// Read all `(K, FactRef)` entries from a leaf page's slot directory. #[allow(clippy::arithmetic_side_effects)] fn read_leaf_entries(page: &[u8]) -> Result> @@ -798,7 +708,7 @@ fn internal_children(page: &[u8]) -> Result> { for i in 0..key_count { children.push(read_u64_at(page, INTERNAL_HEADER_SIZE + i * 8)?); } - children.push(read_u64_at(page, 4)?); + children.push(read_u64_at(page, RIGHTMOST_CHILD_OFFSET)?); Ok(children) } @@ -828,7 +738,7 @@ impl Frame { #[allow(clippy::arithmetic_side_effects)] fn child(&self, i: usize) -> Result { if i == self.key_count { - read_u64_at(&self.page[..], 4) + read_u64_at(&self.page[..], RIGHTMOST_CHILD_OFFSET) } else { read_u64_at(&self.page[..], INTERNAL_HEADER_SIZE + i * 8) } @@ -1129,10 +1039,6 @@ impl StorageBackend for MutexStorageBackend { fn backend_name(&self) -> &'static str { unimplemented!("MutexStorageBackend is read-only; backend_name must not be called") } - - fn is_new(&self) -> bool { - self.0.lock().map(|g| g.is_new()).unwrap_or(false) - } } // ─── OnDiskIndexReader ──────────────────────────────────────────────────────── @@ -1223,6 +1129,36 @@ impl crate::storage::CommittedIndexReader for OnDis #[cfg(test)] mod tests { use super::*; + + /// `build_btree` appending from `start` in generation 1; returns + /// `(root, next_free_page_id)`. + fn build_btree_at( + entries: impl Iterator, Vec)>, + backend: &mut dyn StorageBackend, + cache: &PageCache, + start: u64, + ) -> Result<(u64, u64)> { + let mut alloc = PageAllocator::new(Vec::new(), start, 1); + let root = build_btree(entries, backend, cache, &mut alloc)?; + Ok((root, alloc.next_append())) + } + + /// `rebuild_btree_incremental` appending from `start` in generation 1; + /// returns `(root, next_free_page_id)`. + fn rebuild_btree_incremental_at( + old_leaves: Vec>>, + pending: Vec<(K, FactRef)>, + backend: &mut dyn StorageBackend, + cache: &PageCache, + start: u64, + ) -> Result<(u64, u64)> + where + K: Serialize + for<'de> Deserialize<'de> + Ord, + { + let mut alloc = PageAllocator::new(Vec::new(), start, 1); + let root = rebuild_btree_incremental(old_leaves, pending, backend, cache, &mut alloc)?; + Ok((root, alloc.next_append())) + } use crate::storage::backend::MemoryBackend; use crate::storage::index::{EavtKey, FactRef}; use uuid::Uuid; @@ -1286,10 +1222,10 @@ mod tests { let mut backend = MemoryBackend::new(); let cache = PageCache::new(4096); let ser = btree_entries(committed.iter().cloned()).unwrap(); - let (old_root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); - let leaves = collect_leaf_pages(old_root, &backend, &cache).unwrap(); + let (old_root, _) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let leaves = collect_leaf_pages(old_root, &backend, &cache, None).unwrap(); let (root, next_free) = - rebuild_btree_incremental(leaves, pending.to_vec(), &mut backend, &cache, start) + rebuild_btree_incremental_at(leaves, pending.to_vec(), &mut backend, &cache, start) .unwrap(); (backend, cache, root, next_free) } @@ -1307,7 +1243,7 @@ mod tests { assert_eq!(got.len(), expected.len(), "entry count differs"); assert!(got == expected, "streamed entries differ from expected"); - let leaves = collect_leaf_pages(root, backend, cache).unwrap(); + let leaves = collect_leaf_pages(root, backend, cache, None).unwrap(); if expected.is_empty() { assert_eq!(leaves.len(), 1, "empty tree is one empty leaf"); } else { @@ -1337,16 +1273,8 @@ mod tests { let cache = PageCache::new(4096); let entries: Vec<_> = (0u128..500).map(|n| make_eavt(n, ":a", n as u64)).collect(); let ser = btree_entries(entries.into_iter()).unwrap(); - let (root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); - let mut ids = vec![find_leftmost_leaf(root, &backend, &cache).unwrap()]; - loop { - let page = cache.get_or_load(*ids.last().unwrap(), &backend).unwrap(); - let next = read_u64_at(&page[..], 4).unwrap(); - if next == 0 { - break; - } - ids.push(next); - } + let (root, _) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let ids = leaf_ids(root, &backend, &cache); assert!(ids.len() >= 3, "fixture needs several leaves"); (backend, cache, root, ids) } @@ -1366,7 +1294,7 @@ mod tests { page[INTERNAL_HEADER_SIZE..INTERNAL_HEADER_SIZE + 8].copy_from_slice(&root.to_le_bytes()); overwrite_page(&mut backend, &cache, root, page); assert!( - collect_leaf_pages(root, &backend, &cache).is_err(), + collect_leaf_pages(root, &backend, &cache, None).is_err(), "cycle must be rejected by collect_leaf_pages" ); assert!( @@ -1375,34 +1303,6 @@ mod tests { ); } - #[test] - fn range_scan_ignores_next_leaf() { - // Zeroing every next_leaf pointer must not change any read: the cursor - // walks the tree, which a copy-on-write layout (#374) requires. - let (mut backend, cache, root, ids) = multi_leaf_tree(); - let expected: Vec<(EavtKey, FactRef)> = - (0u128..500).map(|n| make_eavt(n, ":a", n as u64)).collect(); - for &id in &ids { - let mut page = cache.get_or_load(id, &backend).unwrap().to_vec(); - page[4..12].copy_from_slice(&0u64.to_le_bytes()); - overwrite_page(&mut backend, &cache, id, page); - } - let got: Vec<(EavtKey, FactRef)> = stream_all_entries(root, &backend, &cache).unwrap(); - assert!(got == expected, "stream must cover every leaf"); - let refs = range_scan(root, &expected[0].0, None, &backend, &cache).unwrap(); - assert_eq!( - refs.len(), - expected.len(), - "range_scan must cover every leaf" - ); - let leaves = collect_leaf_pages(root, &backend, &cache).unwrap(); - assert_eq!( - leaves.len(), - ids.len(), - "collect_leaf_pages must find every leaf" - ); - } - #[test] fn test_collect_leaf_pages_rejects_corrupt_slot_directory() { // Untouched leaves are copied without decoding, so a damaged slot must be @@ -1413,7 +1313,7 @@ mod tests { page[LEAF_HEADER_SIZE..LEAF_HEADER_SIZE + 2].copy_from_slice(&bad_offset.to_le_bytes()); overwrite_page(&mut backend, &cache, ids[1], page); assert!( - collect_leaf_pages(root, &backend, &cache).is_err(), + collect_leaf_pages(root, &backend, &cache, None).is_err(), "slot pointing past the page end must be rejected" ); @@ -1422,7 +1322,7 @@ mod tests { page[2..4].copy_from_slice(&u16::MAX.to_le_bytes()); overwrite_page(&mut backend, &cache, ids[2], page); assert!( - collect_leaf_pages(root, &backend, &cache).is_err(), + collect_leaf_pages(root, &backend, &cache, None).is_err(), "entry count overflowing the page must be rejected" ); } @@ -1435,9 +1335,10 @@ mod tests { let mut backend = MemoryBackend::new(); let cache = PageCache::new(4096); let ser = btree_entries(committed.iter().cloned()).unwrap(); - let (old_root, old_next) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); - let old_leaves = collect_leaf_pages(old_root, &backend, &cache).unwrap(); - let (root, _) = rebuild_btree_incremental( + let (old_root, old_next) = + build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let old_leaves = collect_leaf_pages(old_root, &backend, &cache, None).unwrap(); + let (root, _) = rebuild_btree_incremental_at( old_leaves.clone(), Vec::<(EavtKey, FactRef)>::new(), &mut backend, @@ -1445,11 +1346,14 @@ mod tests { old_next, ) .unwrap(); - let new_leaves = collect_leaf_pages(root, &backend, &cache).unwrap(); + let new_leaves = collect_leaf_pages(root, &backend, &cache, None).unwrap(); assert_eq!(new_leaves.len(), old_leaves.len(), "leaf count changed"); for (o, n) in old_leaves.iter().zip(new_leaves.iter()) { - assert!(o[..4] == n[..4], "leaf header prefix changed"); - assert!(o[12..] == n[12..], "leaf body changed"); + assert!(o[..4] == n[..4], "leaf type/count changed"); + assert!( + o[LEAF_HEADER_SIZE..] == n[LEAF_HEADER_SIZE..], + "leaf body changed" + ); } assert_tree_exact(root, &backend, &cache, &committed, &mut rng); } @@ -1539,19 +1443,23 @@ mod tests { let cache = PageCache::new(4096); let mut expected = random_eavt(&mut rng, 3000, &mut ctr); let ser = btree_entries(expected.iter().cloned()).unwrap(); - let (mut root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); - let bulk_leaves = collect_leaf_pages(root, &backend, &cache).unwrap().len(); + let (mut root, _) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let bulk_leaves = collect_leaf_pages(root, &backend, &cache, None) + .unwrap() + .len(); for _ in 0..600 { let pending = random_eavt(&mut rng, 1, &mut ctr); - let leaves = collect_leaf_pages(root, &backend, &cache).unwrap(); - root = rebuild_btree_incremental(leaves, pending.clone(), &mut backend, &cache, 1) + let leaves = collect_leaf_pages(root, &backend, &cache, None).unwrap(); + root = rebuild_btree_incremental_at(leaves, pending.clone(), &mut backend, &cache, 1) .unwrap() .0; expected = sorted_union(&expected, &pending); } assert_tree_exact(root, &backend, &cache, &expected, &mut rng); // 20% more entries; at >= ~37% fill that is at most ~2.5x the bulk leaf count. - let leaves = collect_leaf_pages(root, &backend, &cache).unwrap().len(); + let leaves = collect_leaf_pages(root, &backend, &cache, None) + .unwrap() + .len(); assert!( leaves <= bulk_leaves * 5 / 2, "leaf count grew from {bulk_leaves} to {leaves}" @@ -1568,14 +1476,14 @@ mod tests { let cache = PageCache::new(4096); let mut expected = random_eavt(&mut rng, 1500, &mut ctr); let ser = btree_entries(expected.iter().cloned()).unwrap(); - let (mut root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let (mut root, _) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); for round in 0..30u64 { let n_pending = 1 + (rng.next() % 150) as usize; let pending = random_eavt(&mut rng, n_pending, &mut ctr); - let leaves = collect_leaf_pages(root, &backend, &cache).unwrap(); + let leaves = collect_leaf_pages(root, &backend, &cache, None).unwrap(); let start = 1 + round % 3; let (r, _) = - rebuild_btree_incremental(leaves, pending.clone(), &mut backend, &cache, start) + rebuild_btree_incremental_at(leaves, pending.clone(), &mut backend, &cache, start) .unwrap(); root = r; expected = sorted_union(&expected, &pending); @@ -1603,7 +1511,7 @@ mod tests { let cache = PageCache::new(64); let entries: Vec<(EavtKey, FactRef)> = vec![]; let ser = btree_entries(entries.into_iter()).unwrap(); - let (root, next_free) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let (root, next_free) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); assert_eq!(root, 1, "root must be at start_page_id"); assert_eq!(next_free, 2, "single empty leaf = 1 page"); // Verify it is a leaf page @@ -1619,7 +1527,7 @@ mod tests { let cache = PageCache::new(64); let entries = vec![make_eavt(1, ":name", 1)]; let ser = btree_entries(entries.into_iter()).unwrap(); - let (root, next_free) = build_btree(ser.into_iter(), &mut backend, &cache, 5).unwrap(); + let (root, next_free) = build_btree_at(ser.into_iter(), &mut backend, &cache, 5).unwrap(); assert_eq!(root, 5); assert_eq!(next_free, 6); let page = cache.get_or_load(5, &backend).unwrap(); @@ -1633,12 +1541,12 @@ mod tests { let mut backend = MemoryBackend::new(); let cache = PageCache::new(128); let entries1 = btree_entries((0u128..5).map(|n| make_eavt(n, ":a", n as u64 + 1))).unwrap(); - let (_, next1) = build_btree(entries1.into_iter(), &mut backend, &cache, 1).unwrap(); + let (_, next1) = build_btree_at(entries1.into_iter(), &mut backend, &cache, 1).unwrap(); let entries2 = btree_entries((5u128..10).map(|n| make_eavt(n, ":b", n as u64 + 1))).unwrap(); let (root2, next2) = - build_btree(entries2.into_iter(), &mut backend, &cache, next1).unwrap(); + build_btree_at(entries2.into_iter(), &mut backend, &cache, next1).unwrap(); assert!(root2 >= next1, "second tree must not overlap with first"); assert!(next2 > root2); @@ -1651,7 +1559,8 @@ mod tests { let cache = PageCache::new(256); let entries = btree_entries((0u128..100).map(|n| make_eavt(n, ":x", n as u64 + 1))).unwrap(); - let (root, next_free) = build_btree(entries.into_iter(), &mut backend, &cache, 1).unwrap(); + let (root, next_free) = + build_btree_at(entries.into_iter(), &mut backend, &cache, 1).unwrap(); let empty_backend = MemoryBackend::new(); for page_id in root..next_free { @@ -1669,7 +1578,8 @@ mod tests { (0u128..200).map(|n| make_eavt(n, ":verylongattributename", n as u64 + 1)), ) .unwrap(); - let (root, next_free) = build_btree(entries.into_iter(), &mut backend, &cache, 1).unwrap(); + let (root, next_free) = + build_btree_at(entries.into_iter(), &mut backend, &cache, 1).unwrap(); for page_id in root..next_free { let page = cache.get_or_load(page_id, &backend).unwrap(); @@ -1688,7 +1598,7 @@ mod tests { // ~300 entries should force at least 2 leaf pages and 1 internal node let entries = (0u128..300).map(|n| make_eavt(n, ":attr", n as u64 + 1)); let ser = btree_entries(entries).unwrap(); - let (root, next_free) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let (root, next_free) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); let root_page = cache.get_or_load(root, &backend).unwrap(); let pages_written = next_free - 1; @@ -1721,54 +1631,20 @@ mod tests { } #[test] - fn test_build_btree_leaf_next_pointers_form_chain() { - // Build a tree with enough entries to require multiple leaf pages, - // then verify leaf[i].next_leaf == leaf[i+1].page_id + fn test_build_btree_spans_leaves_and_seals_every_page() { + // ~100 entries with long keys span several leaves. Every page written is + // sealed for generation 1 at its own id, and below next_free. let mut backend = MemoryBackend::new(); let cache = PageCache::new(256); - // ~100 entries with long keys should span 4-6 leaf pages let entries = (0u128..100).map(|n| make_eavt(n, ":verylongattributename", n as u64 + 1)); let ser = btree_entries(entries).unwrap(); - let (root, next_free) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); - - // Collect leaf page IDs by following the chain from the leftmost leaf - // The root may be an internal node; find the leftmost leaf first - let root_page = cache.get_or_load(root, &backend).unwrap(); - let mut leaf_pid = if root_page[0] == PAGE_TYPE_LEAF { - root - } else { - // leftmost leaf: follow first child of each internal node down - let mut pid = root; - loop { - let p = cache.get_or_load(pid, &backend).unwrap(); - if p[0] == PAGE_TYPE_LEAF { - break pid; - } - // first child is at child_array[0] = bytes 12..20 - pid = read_u64_at(&p[..], 12).unwrap(); - } - }; - - // Walk the chain and verify it's contiguous and terminates - let mut chain: Vec = vec![leaf_pid]; - loop { - let p = cache.get_or_load(leaf_pid, &backend).unwrap(); - assert_eq!(p[0], PAGE_TYPE_LEAF, "page {} should be leaf", leaf_pid); - let next = read_u64_at(&p[..], 4).unwrap(); - if next == 0 { - break; - } - chain.push(next); - leaf_pid = next; - } - + let (root, next_free) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let leaves = leaf_ids(root, &backend, &cache); assert!( - chain.len() >= 2, - "100 long-key entries should span multiple leaves; got {} leaves", - chain.len() + leaves.len() >= 2, + "100 long-key entries should span multiple leaves" ); - // Total entries across all leaves must equal 100 - let total_entries: u64 = chain + let total_entries: u64 = leaves .iter() .map(|&pid| { let p = cache.get_or_load(pid, &backend).unwrap(); @@ -1776,14 +1652,9 @@ mod tests { }) .sum(); assert_eq!(total_entries, 100); - // next_free must be > all leaf page IDs - for &pid in &chain { - assert!( - pid < next_free, - "leaf {} must be < next_free {}", - pid, - next_free - ); + for pid in 1..next_free { + let raw = backend.read_page(pid).unwrap(); + crate::storage::page::verify(&raw, pid, 1).expect("sealed page"); } } @@ -1803,7 +1674,7 @@ mod tests { .map(|n| make_eavt(n, ":name", n as u64 + 1)) .collect(); let ser = btree_entries(input.iter().cloned()).unwrap(); - let (root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let (root, _) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); let output: Vec<(EavtKey, FactRef)> = stream_all_entries(root, &backend, &cache).unwrap(); @@ -1822,7 +1693,7 @@ mod tests { let cache = PageCache::new(16); let entries: Vec<(EavtKey, FactRef)> = vec![]; let ser = btree_entries(entries.into_iter()).unwrap(); - let (root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let (root, _) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); let out: Vec<(EavtKey, FactRef)> = stream_all_entries(root, &backend, &cache).unwrap(); assert_eq!(out.len(), 0); } @@ -1835,7 +1706,7 @@ mod tests { .map(|n| make_eavt(n, ":v", n as u64 + 1)) .collect(); let ser = btree_entries(input.iter().cloned()).unwrap(); - let (root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let (root, _) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); let target_entity = Uuid::from_u128(42); let start = EavtKey { @@ -1878,7 +1749,7 @@ mod tests { .map(|n| make_eavt(n, ":v", n as u64 + 1)) .collect(); let ser = btree_entries(input.iter().cloned()).unwrap(); - let (root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let (root, _) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); let start = EavtKey { entity: Uuid::from_u128(999), @@ -1901,7 +1772,7 @@ mod tests { .map(|n| make_eavt(n, ":v", n as u64 + 1)) .collect(); let ser = btree_entries(input.iter().cloned()).unwrap(); - let (root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let (root, _) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); let start = EavtKey { entity: Uuid::from_u128(5), @@ -1924,7 +1795,7 @@ mod tests { .map(|n| make_eavt(n, ":a", n as u64 + 1)) .collect(); let ser = btree_entries(input.iter().cloned()).unwrap(); - let (root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let (root, _) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); let start = EavtKey { entity: Uuid::from_u128(100), @@ -1975,8 +1846,6 @@ mod tests { let mut page = cache.get_or_load(root, &backend).unwrap().to_vec(); assert_eq!(page[0], PAGE_TYPE_INTERNAL, "fixture root must be internal"); // A page that is neither leaf nor internal (as a fact page would be). - // Well past every page build_btree wrote (MemoryBackend's page_count - // counts written pages, so it can equal the root's id). let bogus_id = root + 1_000; let mut bogus = vec![0u8; PAGE_SIZE]; bogus[0] = crate::storage::packed_pages::PAGE_TYPE_PACKED; @@ -2004,7 +1873,7 @@ mod tests { .map(|n| make_eavt(n, ":x", n as u64 + 1)) .collect(); let ser = btree_entries(input.iter().cloned()).unwrap(); - let (eavt_root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let (eavt_root, _) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); let reader = OnDiskIndexReader::new(Arc::new(Mutex::new(backend)), cache, eavt_root, 0, 0, 0); @@ -2048,7 +1917,7 @@ mod tests { .map(|n| make_eavt(n, ":x", n as u64 + 1)) .collect(); let ser = btree_entries(input.iter().cloned()).unwrap(); - let (eavt_root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let (eavt_root, _) = build_btree_at(ser.into_iter(), &mut backend, &cache, 1).unwrap(); // Wrap in Arc after build_btree is done — OnDiskIndexReader requires Arc let reader = Arc::new(OnDiskIndexReader::new( @@ -2147,9 +2016,6 @@ mod tests { fn backend_name(&self) -> &'static str { "counting" } - fn is_new(&self) -> bool { - self.inner.is_new() - } } /// Entities `0, 2, 4, ...` so every odd entity is a key that is not in the tree. @@ -2169,7 +2035,9 @@ mod tests { entries: &[(EavtKey, FactRef)], ) -> u64 { let ser = btree_entries(entries.iter().cloned()).unwrap(); - build_btree(ser.into_iter(), backend, cache, 1).unwrap().0 + build_btree_at(ser.into_iter(), backend, cache, 1) + .unwrap() + .0 } fn drain(cursor: &mut LeafCursor<'_, EavtKey>) -> Vec<(EavtKey, FactRef)> { @@ -2426,4 +2294,73 @@ mod tests { "seek lands on the sibling's first entry" ); } + + /// An entry or separator too large for its page is an error, never a page + /// whose data region silently overlaps its slot directory. + #[test] + fn oversized_entry_or_separator_is_rejected() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(0); + let mut alloc = PageAllocator::new(Vec::new(), 2, 1); + let big = vec![7u8; PAGE_SIZE - LEAF_HEADER_SIZE - SLOT_SIZE + 1]; + assert!(encode_leaf_page(&[big]).is_err(), "leaf overflow"); + let fits = vec![7u8; PAGE_SIZE - LEAF_HEADER_SIZE - SLOT_SIZE]; + assert!(encode_leaf_page(&[fits]).is_ok(), "exact fit"); + + let sep = vec![7u8; PAGE_SIZE - INTERNAL_HEADER_SIZE - 8 - SLOT_SIZE + 1]; + let err = write_internal_page(&mut backend, &cache, &mut alloc, &[2, 3], &[sep]); + assert!(err.is_err(), "internal overflow"); + let sep = vec![7u8; PAGE_SIZE - INTERNAL_HEADER_SIZE - 8 - SLOT_SIZE]; + write_internal_page(&mut backend, &cache, &mut alloc, &[2, 3], &[sep]).unwrap(); + } + + /// The largest key a maximum-size fact can produce fits in an internal node. + #[test] + fn max_size_fact_key_fits_an_internal_node() { + use crate::graph::types::{Fact, VALID_TIME_FOREVER, Value}; + // tx_id 0 encodes in one byte: the smallest fact for a given key. + let attr = ":a".to_string(); + let overhead = |n: usize| { + let f = Fact::with_valid_time( + uuid::Uuid::from_u128(u128::MAX), + attr.clone(), + Value::String("x".repeat(n)), + 0, + u64::MAX, + i64::MIN, + VALID_TIME_FOREVER, + ); + postcard::to_allocvec(&f).unwrap().len() + }; + let mut n = crate::storage::packed_pages::MAX_FACT_BYTES; + while overhead(n) > crate::storage::packed_pages::MAX_FACT_BYTES { + n -= 1; + } + let f = Fact::with_valid_time( + uuid::Uuid::from_u128(u128::MAX), + attr, + Value::String("x".repeat(n)), + 0, + u64::MAX, + i64::MIN, + VALID_TIME_FOREVER, + ); + let keys = [ + postcard::to_allocvec(&EavtKey::from_fact(&f)) + .unwrap() + .len(), + postcard::to_allocvec(&crate::storage::index::AevtKey::from_fact(&f)) + .unwrap() + .len(), + postcard::to_allocvec(&crate::storage::index::AvetKey::from_fact(&f)) + .unwrap() + .len(), + ]; + for k in keys { + assert!( + INTERNAL_HEADER_SIZE + 8 + SLOT_SIZE + k <= PAGE_SIZE, + "a max-size key must fit beside one child pointer" + ); + } + } } diff --git a/src/storage/cache.rs b/src/storage/cache.rs index b7fcebd127..63a36f8c0e 100644 --- a/src/storage/cache.rs +++ b/src/storage/cache.rs @@ -17,8 +17,10 @@ use crate::error::{ErrorCode, err_coded}; use crate::storage::StorageBackend; +use crate::storage::page; use anyhow::Result; use std::collections::{HashMap, VecDeque}; +use std::sync::atomic::{AtomicU64, Ordering}; use std::sync::{Arc, RwLock}; struct CacheEntry { @@ -57,6 +59,9 @@ impl CacheInner { /// All methods take `&self` (interior mutability via `RwLock`). pub struct PageCache { inner: RwLock, + /// Highest page generation a load accepts: the active meta's generation + /// (spec §4.2 check 4). `u64::MAX` until storage sets it. + generation_bound: AtomicU64, } impl PageCache { @@ -76,10 +81,27 @@ impl PageCache { order: VecDeque::new(), capacity, }), + generation_bound: AtomicU64::new(u64::MAX), } } + /// Set the highest page generation that `get_or_load` accepts. + pub fn set_generation_bound(&self, generation: u64) { + self.generation_bound.store(generation, Ordering::SeqCst); + } + + /// Read a page from the backend and run the spec §4.2 header checks. + fn load_verified(&self, page_id: u64, backend: &dyn StorageBackend) -> Result> { + let data = backend.read_page(page_id)?; + page::verify(&data, page_id, self.generation_bound.load(Ordering::SeqCst))?; + Ok(data) + } + /// Get a page from the cache, loading from `backend` on a miss. + /// + /// Every page read from the backend is verified (type, CRC, page id, + /// generation) before it is returned or cached; a page that fails is + /// never cached. pub fn get_or_load(&self, page_id: u64, backend: &dyn StorageBackend) -> Result>> { // Fast path: read lock for cache hits (concurrent readers don't block each other) // Approximate LRU: return without promoting to MRU to avoid a write lock @@ -91,14 +113,14 @@ impl PageCache { .map_err(|_| err_coded!(ErrorCode::Int050, "cache"))?; // Capacity 0 disables the cache: always read through, no bookkeeping. if inner.capacity == 0 { - return Ok(Arc::new(backend.read_page(page_id)?)); + return Ok(Arc::new(self.load_verified(page_id, backend)?)); } if let Some(entry) = inner.entries.get(&page_id) { return Ok(entry.data.clone()); } } // Miss: load from backend (without holding any lock) - let data = Arc::new(backend.read_page(page_id)?); + let data = Arc::new(self.load_verified(page_id, backend)?); let mut inner = self .inner .write() @@ -181,16 +203,6 @@ impl PageCache { inner.order.retain(|&id| id != page_id); } - /// Invalidate all cached pages with `page_id >= from_page`. - /// - /// Used during save to discard stale B+tree index pages before - /// overwriting them with new fact and index pages. - pub fn invalidate_from(&self, from_page: u64) { - let mut inner = self.inner.write().unwrap_or_else(|e| e.into_inner()); - inner.entries.retain(|&id, _| id < from_page); - inner.order.retain(|&id| id < from_page); - } - /// Number of pages currently cached (for testing). #[allow(dead_code)] pub fn cached_page_count(&self) -> usize { @@ -215,37 +227,43 @@ impl PageCache { #[cfg(test)] mod tests { use super::*; - use crate::storage::PAGE_SIZE; use crate::storage::backend::MemoryBackend; - fn make_page(byte: u8) -> Vec { - vec![byte; PAGE_SIZE] + /// Byte offset of the marker each test page carries in its body. + const MARK: usize = 100; + + /// A valid sealed leaf page for `page_id` (generation 1) with `byte` at `MARK`. + fn make_page(page_id: u64, byte: u8) -> Vec { + let mut p = page::new_page(page::PAGE_TYPE_LEAF, 0); + p[MARK] = byte; + page::seal(&mut p, page_id, 1).unwrap(); + p } #[test] fn test_cache_miss_loads_from_backend() { let mut backend = MemoryBackend::new(); - backend.write_page(1, &make_page(0xAB)).unwrap(); + backend.write_page(1, &make_page(1, 0xAB)).unwrap(); let cache = PageCache::new(4); let page = cache.get_or_load(1, &backend).unwrap(); - assert_eq!(page[0], 0xAB); + assert_eq!(page[MARK], 0xAB); } #[test] fn test_cache_hit_returns_same_bytes() { let mut backend = MemoryBackend::new(); - backend.write_page(1, &make_page(0x11)).unwrap(); + backend.write_page(1, &make_page(1, 0x11)).unwrap(); let cache = PageCache::new(4); let p1 = cache.get_or_load(1, &backend).unwrap(); let p2 = cache.get_or_load(1, &backend).unwrap(); - assert_eq!(p1[0], p2[0]); + assert_eq!(p1[MARK], p2[MARK]); } #[test] fn test_lru_eviction_respects_capacity() { let mut backend = MemoryBackend::new(); for i in 1u64..=5 { - backend.write_page(i, &make_page(i as u8)).unwrap(); + backend.write_page(i, &make_page(i, i as u8)).unwrap(); } let cache = PageCache::new(3); // capacity 3 cache.get_or_load(1, &backend).unwrap(); @@ -260,12 +278,12 @@ mod tests { #[test] fn test_dirty_page_written_back_on_flush() { let mut backend = MemoryBackend::new(); - backend.write_page(1, &make_page(0x00)).unwrap(); + backend.write_page(1, &make_page(1, 0x00)).unwrap(); let cache = PageCache::new(4); - cache.put_dirty(1, make_page(0xFF)); + cache.put_dirty(1, make_page(1, 0xFF)); cache.flush(&mut backend).unwrap(); let page = backend.read_page(1).unwrap(); - assert_eq!(page[0], 0xFF); + assert_eq!(page[MARK], 0xFF); } #[test] @@ -274,7 +292,7 @@ mod tests { use std::sync::Arc; use std::thread; let mut backend = MemoryBackend::new(); - backend.write_page(1, &make_page(0x42)).unwrap(); + backend.write_page(1, &make_page(1, 0x42)).unwrap(); let cache = Arc::new(PageCache::new(8)); let handles: Vec<_> = (0..4) .map(|_| { @@ -282,7 +300,7 @@ mod tests { let b = backend.clone(); thread::spawn(move || { let page = c.get_or_load(1, &b).unwrap(); - assert_eq!(page[0], 0x42); + assert_eq!(page[MARK], 0x42); }) }) .collect(); @@ -295,7 +313,7 @@ mod tests { fn test_lru_eviction_evicts_correct_page() { let mut backend = MemoryBackend::new(); for i in 1u64..=4 { - backend.write_page(i, &make_page(i as u8)).unwrap(); + backend.write_page(i, &make_page(i, i as u8)).unwrap(); } let cache = PageCache::new(3); // Load 1, 2, 3 in order @@ -315,13 +333,13 @@ mod tests { fn test_zero_capacity_disables_caching() { let mut backend = MemoryBackend::new(); for i in 1u64..=10 { - backend.write_page(i, &make_page(i as u8)).unwrap(); + backend.write_page(i, &make_page(i, i as u8)).unwrap(); } let cache = PageCache::new(0); assert_eq!(cache.capacity(), 0); for i in 1u64..=10 { let page = cache.get_or_load(i, &backend).unwrap(); - assert_eq!(page[0], i as u8); + assert_eq!(page[MARK], i as u8); } // Nothing should have been retained: capacity 0 means "no cache", not // "unbounded cache" — every load must read straight through and leave @@ -332,7 +350,7 @@ mod tests { #[test] fn test_zero_capacity_put_dirty_is_noop() { let cache = PageCache::new(0); - cache.put_dirty(1, make_page(0xAA)); + cache.put_dirty(1, make_page(1, 0xAA)); assert_eq!(cache.cached_page_count(), 0); } @@ -344,7 +362,7 @@ mod tests { fn test_put_dirty_after_eviction_does_not_panic() { let mut backend = MemoryBackend::new(); for i in 1u64..=3 { - backend.write_page(i, &make_page(i as u8)).unwrap(); + backend.write_page(i, &make_page(i, i as u8)).unwrap(); } let cache = PageCache::new(2); // Fill cache: pages 1 and 2 (order: [1, 2]) @@ -357,7 +375,37 @@ mod tests { // became out of bounds after eviction made it a 2-element deque with // indices 0..1 but the stored position was 1 — which after pop_front // pointed past the end. - cache.put_dirty(2, make_page(0xBB)); // must not panic + cache.put_dirty(2, make_page(2, 0xBB)); // must not panic assert_eq!(cache.cached_page_count(), 2); } + + #[test] + fn corrupt_page_is_rejected_and_not_cached() { + let mut backend = MemoryBackend::new(); + let mut p = make_page(1, 0x11); + p[MARK] ^= 1; // body changed after sealing + backend.write_page(1, &p).unwrap(); + for cap in [0, 4] { + let cache = PageCache::new(cap); + let err = cache.get_or_load(1, &backend).unwrap_err(); + assert_eq!(crate::error::MinigrafError::from(err).code(), "STG-029"); + assert_eq!(cache.cached_page_count(), 0); + } + } + + #[test] + fn page_newer_than_bound_is_rejected_until_bound_rises() { + let mut backend = MemoryBackend::new(); + let mut p = page::new_page(page::PAGE_TYPE_LEAF, 0); + page::seal(&mut p, 1, 5).unwrap(); + backend.write_page(1, &p).unwrap(); + let cache = PageCache::new(4); + cache.set_generation_bound(4); + let err = cache.get_or_load(1, &backend).unwrap_err(); + assert_eq!(crate::error::MinigrafError::from(err).code(), "STG-031"); + assert_eq!(cache.cached_page_count(), 0); + cache.set_generation_bound(5); + cache.get_or_load(1, &backend).unwrap(); + assert_eq!(cache.cached_page_count(), 1); + } } diff --git a/src/storage/freelist.rs b/src/storage/freelist.rs new file mode 100644 index 0000000000..7c1a84ac1a --- /dev/null +++ b/src/storage/freelist.rs @@ -0,0 +1,155 @@ +//! Free-list pages (spec §4.4). +//! +//! A singly linked chain of 0x81 pages holding ids of pages the active meta does +//! not reference. Body after the common header: `next u64`, then `count` page +//! ids (u64 each). This version writes the whole chain afresh on every +//! checkpoint; the format is the same one copy-on-write push/pop will use. + +use crate::error::{ErrorCode, bail_coded, err_coded}; +use crate::storage::PAGE_SIZE; +use crate::storage::StorageBackend; +use crate::storage::cache::PageCache; +use crate::storage::page::{PAGE_HEADER_SIZE, PAGE_TYPE_FREELIST, PageAllocator, new_page}; +use anyhow::Result; + +const NEXT_OFFSET: usize = PAGE_HEADER_SIZE; +const IDS_OFFSET: usize = PAGE_HEADER_SIZE + 8; +/// Page ids per free-list page: (4096 − 24 − 8) / 8. +pub const IDS_PER_PAGE: usize = (PAGE_SIZE - IDS_OFFSET) / 8; + +/// Write `ids` as a new chain and return `(head, chain_page_ids)`. +/// +/// Chain pages come from `alloc`, so the chain never lists its own pages. +/// An empty list writes nothing and returns head 0. +pub fn write_chain( + ids: &[u64], + alloc: &mut PageAllocator, + backend: &mut dyn StorageBackend, + cache: &PageCache, +) -> Result<(u64, Vec)> { + let chunks: Vec<&[u64]> = ids.chunks(IDS_PER_PAGE).collect(); + let mut page_ids = Vec::with_capacity(chunks.len()); + for _ in &chunks { + page_ids.push(alloc.alloc()?); + } + for (i, chunk) in chunks.iter().enumerate() { + let count = u16::try_from(chunk.len()) + .map_err(|_| err_coded!(ErrorCode::Int048, "free-list page count exceeds u16"))?; + let mut page = new_page(PAGE_TYPE_FREELIST, count); + let next = page_ids.get(i.saturating_add(1)).copied().unwrap_or(0); + if let Some(dst) = page.get_mut(NEXT_OFFSET..IDS_OFFSET) { + dst.copy_from_slice(&next.to_le_bytes()); + } + for (j, id) in chunk.iter().enumerate() { + let off = IDS_OFFSET.saturating_add(j.saturating_mul(8)); + if let Some(dst) = page.get_mut(off..off.saturating_add(8)) { + dst.copy_from_slice(&id.to_le_bytes()); + } + } + let page_id = *page_ids + .get(i) + .ok_or_else(|| err_coded!(ErrorCode::Int049, "free-list page id missing"))?; + alloc.write(backend, cache, page_id, page)?; + } + Ok((page_ids.first().copied().unwrap_or(0), page_ids)) +} + +/// Read the chain at `head` and return `(free_ids, chain_page_ids)`. +/// +/// Every page is verified through `cache`. A cycle, or an id below 2 or at or +/// past `page_count`, is STG-035. +pub fn read_chain( + head: u64, + backend: &dyn StorageBackend, + cache: &PageCache, + page_count: u64, +) -> Result<(Vec, Vec)> { + let mut ids = Vec::new(); + let mut chain = Vec::new(); + let mut next = head; + while next != 0 { + if next < 2 || next >= page_count { + bail_coded!(ErrorCode::Stg035, format!("chain page {next} out of range")); + } + // A chain longer than the file has pages must loop. + if u64::try_from(chain.len()).unwrap_or(u64::MAX) >= page_count { + bail_coded!(ErrorCode::Stg035, "chain loops"); + } + let page = cache.get_or_load(next, backend)?; + if page.first().copied() != Some(PAGE_TYPE_FREELIST) { + bail_coded!(ErrorCode::Stg013, next); + } + chain.push(next); + let count = usize::from(crate::storage::page::page_count_field(&page)?); + if count > IDS_PER_PAGE { + bail_coded!(ErrorCode::Stg035, format!("page {next} count {count}")); + } + for j in 0..count { + let off = IDS_OFFSET.saturating_add(j.saturating_mul(8)); + let id = read_u64(&page, off)?; + if id < 2 || id >= page_count { + bail_coded!(ErrorCode::Stg035, format!("free id {id} out of range")); + } + ids.push(id); + } + next = read_u64(&page, NEXT_OFFSET)?; + } + Ok((ids, chain)) +} + +fn read_u64(page: &[u8], off: usize) -> Result { + page.get(off..off.saturating_add(8)) + .and_then(|b| <[u8; 8]>::try_from(b).ok()) + .map(u64::from_le_bytes) + .ok_or_else(|| err_coded!(ErrorCode::Int049, "free-list page too short")) +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::storage::backend::MemoryBackend; + + fn round_trip(n: u64) { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(16); + // Free ids 2..2+n; chain pages are appended after them. + let ids: Vec = (2..2 + n).collect(); + let mut alloc = PageAllocator::new(Vec::new(), 2 + n, 1); + let (head, chain) = write_chain(&ids, &mut alloc, &mut backend, &cache).unwrap(); + assert_eq!(chain.len(), (n as usize).div_ceil(IDS_PER_PAGE)); + let (read, read_chain_ids) = + read_chain(head, &backend, &PageCache::new(0), alloc.next_append()).unwrap(); + assert_eq!(read, ids, "ids round trip"); + assert_eq!(read_chain_ids, chain); + } + + #[test] + fn chain_round_trips_at_page_boundaries() { + for n in [0, 1, 508, 509, 5_000] { + round_trip(n); + } + assert_eq!(IDS_PER_PAGE, 508); + } + + #[test] + fn looping_chain_is_stg_035() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(0); + let alloc = PageAllocator::new(Vec::new(), 3, 1); + let mut page = new_page(PAGE_TYPE_FREELIST, 0); + page[NEXT_OFFSET..IDS_OFFSET].copy_from_slice(&2u64.to_le_bytes()); // points at itself + alloc.write(&mut backend, &cache, 2, page).unwrap(); + let err = read_chain(2, &backend, &cache, 3).unwrap_err(); + assert_eq!(crate::error::MinigrafError::from(err).code(), "STG-035"); + } + + #[test] + fn out_of_range_id_is_stg_035() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(0); + let mut alloc = PageAllocator::new(Vec::new(), 2, 1); + let (head, _) = write_chain(&[1], &mut alloc, &mut backend, &cache).unwrap(); + let err = read_chain(head, &backend, &cache, alloc.next_append()).unwrap_err(); + assert_eq!(crate::error::MinigrafError::from(err).code(), "STG-035"); + } +} diff --git a/src/storage/meta.rs b/src/storage/meta.rs new file mode 100644 index 0000000000..c97086857a --- /dev/null +++ b/src/storage/meta.rs @@ -0,0 +1,313 @@ +//! Format v8 meta pages (spec §4.1). +//! +//! Two alternating meta pages are the only commit point. Odd generations live in +//! page 0 (slot A), even generations in page 1 (slot B). Each covers the whole +//! page with its CRC, so the reserved tail must be zero. + +use crate::error::{ErrorCode, bail_coded, err_coded}; +use crate::storage::{FORMAT_VERSION, MAGIC_NUMBER, PAGE_SIZE}; +use anyhow::Result; + +/// Distinguishes a v8 meta page from a legacy header. +const META_MAGIC: [u8; 4] = *b"META"; + +/// File feature bits this version understands (spec §4.1.2). v3.0.0 defines none. +/// Bits are never reused; register new ones here with their meaning. +pub const KNOWN_FEATURES: u64 = 0; + +const CRC_RANGE: std::ops::Range = 12..16; +/// Bytes 124.. are reserved and must be zero. +const FIELDS_END: usize = 124; + +/// The contents of one meta page. +#[derive(Clone, Copy, PartialEq, Eq, Default)] +pub struct MetaPage { + pub generation: u64, + pub page_count: u64, + pub fact_count: u64, + pub last_checkpointed_tx_count: u64, + pub eavt_root: u64, + pub aevt_root: u64, + pub avet_root: u64, + pub vaet_root: u64, + pub dict_root: u64, + pub freelist_head: u64, + pub freelist_count: u64, + pub next_eid: u64, + pub required_features: u64, + pub next_iid: u32, +} + +/// How one meta slot reads. +pub enum SlotState { + /// No `"MGRF"`/`"META"` magic: never written as a meta page. + Empty, + /// Magic, version and CRC check out. + Valid(MetaPage), + /// Magic present, but the CRC or a field fails. + Damaged, +} + +impl SlotState { + /// True if this slot holds a valid meta of `generation`. + #[cfg(test)] + pub fn is_valid_generation(&self, generation: u64) -> bool { + matches!(self, SlotState::Valid(m) if m.generation == generation) + } +} + +/// The page that holds generation `generation`'s meta: 0 for odd, 1 for even. +pub fn slot_page(generation: u64) -> u64 { + generation.wrapping_sub(1) % 2 +} + +fn crc_of(page: &[u8]) -> u32 { + let mut h = crc32fast::Hasher::new(); + h.update(page.get(..CRC_RANGE.start).unwrap_or(&[])); + h.update(&[0u8; 4]); + h.update(page.get(CRC_RANGE.end..).unwrap_or(&[])); + h.finalize() +} + +fn u64_at(page: &[u8], off: usize) -> u64 { + page.get(off..off.saturating_add(8)) + .and_then(|b| <[u8; 8]>::try_from(b).ok()) + .map(u64::from_le_bytes) + .unwrap_or(0) +} + +fn u32_at(page: &[u8], off: usize) -> u32 { + page.get(off..off.saturating_add(4)) + .and_then(|b| <[u8; 4]>::try_from(b).ok()) + .map(u32::from_le_bytes) + .unwrap_or(0) +} + +impl MetaPage { + /// The u64 fields in on-disk order, starting at byte 16. + fn u64_fields(&self) -> [u64; 13] { + [ + self.generation, + self.page_count, + self.fact_count, + self.last_checkpointed_tx_count, + self.eavt_root, + self.aevt_root, + self.avet_root, + self.vaet_root, + self.dict_root, + self.freelist_head, + self.freelist_count, + self.next_eid, + self.required_features, + ] + } + + /// Encode as a full page with its CRC. + pub fn encode(&self) -> Vec { + let mut page = vec![0u8; PAGE_SIZE]; + let mut put = |off: usize, bytes: &[u8]| { + if let Some(dst) = page.get_mut(off..off.saturating_add(bytes.len())) { + dst.copy_from_slice(bytes); + } + }; + put(0, &MAGIC_NUMBER); + put(4, &FORMAT_VERSION.to_le_bytes()); + put(8, &META_MAGIC); + for (i, v) in self.u64_fields().iter().enumerate() { + put( + 16usize.saturating_add(i.saturating_mul(8)), + &v.to_le_bytes(), + ); + } + put(120, &self.next_iid.to_le_bytes()); + let crc = crc_of(&page); + if let Some(dst) = page.get_mut(CRC_RANGE) { + dst.copy_from_slice(&crc.to_le_bytes()); + } + page + } + + /// Classify a page read from a meta slot. + pub fn decode(page: &[u8]) -> SlotState { + if page.len() != PAGE_SIZE + || page.get(0..4) != Some(&MAGIC_NUMBER[..]) + || page.get(8..12) != Some(&META_MAGIC[..]) + { + return SlotState::Empty; + } + if u32_at(page, 4) != FORMAT_VERSION + || u32_at(page, CRC_RANGE.start) != crc_of(page) + || page + .get(FIELDS_END..) + .is_some_and(|r| r.iter().any(|&b| b != 0)) + { + return SlotState::Damaged; + } + let f = |i: usize| u64_at(page, 16usize.saturating_add(i.saturating_mul(8))); + let meta = MetaPage { + generation: f(0), + page_count: f(1), + fact_count: f(2), + last_checkpointed_tx_count: f(3), + eavt_root: f(4), + aevt_root: f(5), + avet_root: f(6), + vaet_root: f(7), + dict_root: f(8), + freelist_head: f(9), + freelist_count: f(10), + next_eid: f(11), + required_features: f(12), + next_iid: u32_at(page, 120), + }; + // Generation 0 is never committed, and pages 0 and 1 always exist. + if meta.generation == 0 || meta.page_count < 2 { + return SlotState::Damaged; + } + SlotState::Valid(meta) + } + + /// Fail with STG-034 if the file needs a feature this version lacks. + pub fn check_features(&self) -> Result<()> { + let unknown = self.required_features & !KNOWN_FEATURES; + if unknown != 0 { + bail_coded!(ErrorCode::Stg034, format!("{unknown:#x}")); + } + Ok(()) + } + + /// The four index roots, in EAVT, AEVT, AVET, VAET order. + pub fn index_roots(&self) -> [u64; 4] { + [ + self.eavt_root, + self.aevt_root, + self.avet_root, + self.vaet_root, + ] + } + + /// An empty database: no trees, no free pages, pages 0 and 1 allocated. + pub fn empty(generation: u64) -> Self { + MetaPage { + generation, + page_count: 2, + ..MetaPage::default() + } + } + + /// The next generation, or an error on overflow. + pub fn next_generation(&self) -> Result { + self.generation + .checked_add(1) + .ok_or_else(|| err_coded!(ErrorCode::Int048, "generation overflow")) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + fn sample() -> MetaPage { + MetaPage { + generation: 7, + page_count: 900, + fact_count: 1234, + last_checkpointed_tx_count: 55, + eavt_root: 10, + aevt_root: 11, + avet_root: 12, + vaet_root: 13, + dict_root: 14, + freelist_head: 15, + freelist_count: 16, + next_eid: 17, + required_features: 0, + next_iid: 18, + } + } + + #[test] + fn round_trip() { + let m = sample(); + match MetaPage::decode(&m.encode()) { + SlotState::Valid(d) => assert!(d == m, "decoded meta differs"), + _ => panic!("expected a valid meta"), + } + } + + #[test] + fn field_offsets_match_the_spec_table() { + let p = sample().encode(); + let at = |o: usize| u64::from_le_bytes(p[o..o + 8].try_into().unwrap()); + assert_eq!(&p[0..4], b"MGRF"); + assert_eq!(u32::from_le_bytes(p[4..8].try_into().unwrap()), 8); + assert_eq!(&p[8..12], b"META"); + assert_eq!(at(16), 7); + assert_eq!(at(24), 900); + assert_eq!(at(32), 1234); + assert_eq!(at(40), 55); + assert_eq!(at(48), 10); + assert_eq!(at(56), 11); + assert_eq!(at(64), 12); + assert_eq!(at(72), 13); + assert_eq!(at(80), 14); + assert_eq!(at(88), 15); + assert_eq!(at(96), 16); + assert_eq!(at(104), 17); + assert_eq!(at(112), 0); + assert_eq!(u32::from_le_bytes(p[120..124].try_into().unwrap()), 18); + assert!(p[124..].iter().all(|&b| b == 0)); + } + + #[test] + fn damaged_and_empty_are_told_apart() { + let good = sample().encode(); + + let mut flipped = good.clone(); + flipped[30] ^= 1; + assert!(matches!(MetaPage::decode(&flipped), SlotState::Damaged)); + + // A non-zero reserved byte is damage even with a matching CRC. + let mut reserved = sample(); + reserved.generation = 7; + let mut p = reserved.encode(); + p[2000] = 1; + let crc = crc_of(&p); + p[12..16].copy_from_slice(&crc.to_le_bytes()); + assert!(matches!(MetaPage::decode(&p), SlotState::Damaged)); + + assert!(matches!( + MetaPage::decode(&vec![0u8; PAGE_SIZE]), + SlotState::Empty + )); + + // A v7 header has "MGRF" but no "META". + let mut v7 = vec![0u8; PAGE_SIZE]; + v7[0..4].copy_from_slice(b"MGRF"); + v7[4..8].copy_from_slice(&7u32.to_le_bytes()); + assert!(matches!(MetaPage::decode(&v7), SlotState::Empty)); + + // A torn write that kept the magic but lost the tail. + let mut torn = good.clone(); + torn[16..].fill(0); + assert!(matches!(MetaPage::decode(&torn), SlotState::Damaged)); + } + + #[test] + fn unknown_feature_bit_is_stg_034() { + let mut m = sample(); + m.required_features = 1 << 5; + let err = m.check_features().unwrap_err(); + assert_eq!(crate::error::MinigrafError::from(err).code(), "STG-034"); + assert!(sample().check_features().is_ok()); + } + + #[test] + fn odd_generations_go_to_page_0() { + assert_eq!(slot_page(1), 0); + assert_eq!(slot_page(2), 1); + assert_eq!(slot_page(3), 0); + assert_eq!(slot_page(u64::MAX), 0); + } +} diff --git a/src/storage/mod.rs b/src/storage/mod.rs index 6853699d38..528a2377f5 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -9,8 +9,11 @@ pub mod backend; pub mod btree_v6; pub mod cache; pub(crate) mod dir_sync; +pub(crate) mod freelist; pub mod index; +pub(crate) mod meta; pub mod packed_pages; +pub(crate) mod page; pub mod persistent_facts; use crate::error::{ErrorCode, bail_coded, err_coded}; @@ -51,7 +54,8 @@ pub const FORMAT_VERSION: u32 = 8; /// opened with Minigraf v2.x, which upgrades them to v7 (see STG-028). pub const MIN_FORMAT_VERSION: u32 = 7; -/// fact_page_format: packed pages (v5+). +/// fact_page_format: packed pages (v5+), in the v7 header. +#[cfg(test)] pub const FACT_PAGE_FORMAT_PACKED: u8 = 0x02; /// Storage backend trait. @@ -89,15 +93,10 @@ pub trait StorageBackend: Send + Sync { /// Get a human-readable name for this backend (for debugging). #[allow(dead_code)] fn backend_name(&self) -> &'static str; - - /// Returns true if this is a newly created empty storage. - /// - /// This is used to determine whether a header read failure should - /// create a fresh header (new storage) or return an error (corrupted existing storage). - fn is_new(&self) -> bool; } -/// File header for .graph files — 84 bytes (v7 and v8 share the layout). +/// The format v7 file header (84 bytes in page 0), read only to migrate a v7 +/// file to v8. Format v8 replaces it with two meta pages ([`meta`]). /// /// Layout (all fields little-endian): /// 0..4 magic ("MGRF") @@ -114,8 +113,11 @@ pub trait StorageBackend: Send + Sync { /// 69..72 _padding ([u8; 3]) /// 72..80 fact_page_count (u64) — new in v6 /// 80..84 header_checksum (u32) — new in v7 +// Every v7 field is parsed so the layout stays documented in one place; the +// migration reads only some of them. +#[allow(dead_code)] #[derive(Debug, Clone, Copy)] -pub struct FileHeader { +pub struct LegacyHeaderV7 { pub magic: [u8; 4], pub version: u32, pub page_count: u64, @@ -137,12 +139,13 @@ pub struct FileHeader { pub header_checksum: u32, } -impl FileHeader { - /// Create a new file header with default values. +impl LegacyHeaderV7 { + /// An empty v7 header, for building v7 fixtures in tests. + #[cfg(test)] pub fn new() -> Self { - FileHeader { + LegacyHeaderV7 { magic: MAGIC_NUMBER, - version: FORMAT_VERSION, + version: 7, page_count: 1, // Just the header page initially node_count: 0, last_checkpointed_tx_count: 0, @@ -158,7 +161,8 @@ impl FileHeader { } } - /// Serialize the header to bytes. + /// Serialize the header to bytes (builds v7 fixtures in tests). + #[cfg(test)] pub fn to_bytes(self) -> Vec { let mut b = Vec::with_capacity(84); b.extend_from_slice(&self.magic); @@ -210,7 +214,7 @@ impl FileHeader { let fact_page_count = read_u64_le(bytes, 72)?; let header_checksum = read_u32_le(bytes, 80)?; - Ok(FileHeader { + Ok(LegacyHeaderV7 { magic, version, page_count, @@ -240,6 +244,60 @@ impl FileHeader { }) } + /// Recognise page 0 of a v7 file. + /// + /// `None` when page 0 does not start with the magic or carries version 8 + /// (a damaged or pre-release v8 file). Versions older than 7 fail with + /// STG-028 and newer than 8 with STG-006. A v7 header whose own CRC fails is + /// INT-053. + pub fn detect(page0: &[u8]) -> Result> { + if page0.get(0..4) != Some(&MAGIC_NUMBER[..]) { + return Ok(None); + } + let version = read_u32_le(page0, 4)?; + if version == FORMAT_VERSION { + return Ok(None); + } + let header = Self::from_bytes(page0)?; + header.validate()?; + if header.header_checksum != Self::checksum_of_bytes(page0) { + bail_coded!(ErrorCode::Int053); + } + Ok(Some(header)) + } + + /// CRC32 over header bytes 0..80 (the checksum field at 80..84 excluded). + #[cfg(test)] + pub fn checksum(&self) -> u32 { + Self::checksum_of_bytes(&self.to_bytes()) + } + + fn checksum_of_bytes(bytes: &[u8]) -> u32 { + let mut hasher = crc32fast::Hasher::new(); + hasher.update(bytes.get(..80).unwrap_or(bytes)); + hasher.finalize() + } + + /// Number of v7 fact pages from page 1: the header field, or (for files + /// that predate it) everything below the first index root. + pub fn fact_page_count_or_derived(&self) -> u64 { + if self.fact_page_count > 0 { + return self.fact_page_count; + } + [ + self.eavt_root_page, + self.aevt_root_page, + self.avet_root_page, + self.vaet_root_page, + ] + .iter() + .filter(|&&p| p > 0) + .copied() + .min() + .unwrap_or(self.page_count) + .saturating_sub(1) + } + /// Validate the header. pub fn validate(&self) -> Result<()> { if self.magic != MAGIC_NUMBER { @@ -248,7 +306,7 @@ impl FileHeader { if self.version < MIN_FORMAT_VERSION { bail_coded!(ErrorCode::Stg028, self.version, MIN_FORMAT_VERSION); } - if self.version > FORMAT_VERSION { + if self.version >= FORMAT_VERSION { bail_coded!(ErrorCode::Stg006, self.version, FORMAT_VERSION); } // Validate logical relationships @@ -265,7 +323,8 @@ impl FileHeader { } } -impl Default for FileHeader { +#[cfg(test)] +impl Default for LegacyHeaderV7 { fn default() -> Self { Self::new() } @@ -283,11 +342,8 @@ pub trait CommittedFactReader: Send + Sync { &self, fact_ref: crate::storage::index::FactRef, ) -> Result; - /// Stream all committed facts (for full scans, checksum verification, migration). + /// Stream all committed facts (for full scans). fn stream_all(&self) -> Result>; - /// Number of committed fact pages (used for checksum + iteration bounds). - #[allow(dead_code)] - fn committed_page_count(&self) -> u64; } /// Provides bounded range scans over the four committed (on-disk) covering indexes. @@ -335,7 +391,7 @@ mod tests { #[test] fn test_file_header_validation() { - let header = FileHeader::new(); + let header = LegacyHeaderV7::new(); assert!(header.validate().is_ok()); let mut invalid = header; @@ -350,21 +406,22 @@ mod tests { #[test] fn test_validate_accepts_version_7() { - let mut h = FileHeader::new(); + let mut h = LegacyHeaderV7::new(); h.version = 7; assert!(h.validate().is_ok()); } #[test] - fn test_validate_accepts_version_8() { - let mut h = FileHeader::new(); + fn test_validate_rejects_version_8_legacy_header() { + // A v8 file has meta pages, not this header. + let mut h = LegacyHeaderV7::new(); h.version = 8; - assert!(h.validate().is_ok()); + assert!(h.validate().is_err()); } #[test] fn test_validate_page_count_must_be_positive() { - let mut h = FileHeader::new(); + let mut h = LegacyHeaderV7::new(); h.page_count = 0; let result = h.validate(); assert!(result.is_err()); @@ -373,7 +430,7 @@ mod tests { #[test] fn test_validate_eavt_root_page_bounds() { - let mut h = FileHeader::new(); + let mut h = LegacyHeaderV7::new(); h.page_count = 10; h.eavt_root_page = 10; // equal to page_count, should fail let result = h.validate(); @@ -391,7 +448,7 @@ mod tests { #[test] fn test_validate_fact_page_count_bounds() { - let mut h = FileHeader::new(); + let mut h = LegacyHeaderV7::new(); h.page_count = 10; h.fact_page_count = 11; // exceeds page_count let result = h.validate(); @@ -404,31 +461,54 @@ mod tests { } #[test] - fn test_new_header_has_version_8() { - let header = FileHeader::new(); - assert_eq!(header.version, FORMAT_VERSION); - assert_eq!(header.version, 8); + fn test_new_legacy_header_has_version_7() { + assert_eq!(LegacyHeaderV7::new().version, 7); + } + + #[test] + fn detect_recognises_only_a_checksummed_v7_header() { + let mut page = vec![0u8; PAGE_SIZE]; + assert!(LegacyHeaderV7::detect(&page).unwrap().is_none(), "zeros"); + + let mut h = LegacyHeaderV7::new(); + h.page_count = 3; + h.header_checksum = h.checksum(); + page[..84].copy_from_slice(&h.to_bytes()); + assert!(LegacyHeaderV7::detect(&page).unwrap().is_some()); + + // A pre-release v8 single header is not a v7 header. + page[4..8].copy_from_slice(&8u32.to_le_bytes()); + assert!(LegacyHeaderV7::detect(&page).unwrap().is_none()); + + page[4..8].copy_from_slice(&7u32.to_le_bytes()); + page[20] ^= 1; // body changed after checksumming + let err = LegacyHeaderV7::detect(&page).unwrap_err(); + assert_eq!(crate::error::MinigrafError::from(err).code(), "INT-053"); + + page[4..8].copy_from_slice(&5u32.to_le_bytes()); + let err = LegacyHeaderV7::detect(&page).unwrap_err(); + assert_eq!(crate::error::MinigrafError::from(err).code(), "STG-028"); } #[test] fn test_file_header_serialization_v7() { - let header = FileHeader::new(); + let header = LegacyHeaderV7::new(); let bytes = header.to_bytes(); assert_eq!(bytes.len(), 84); } #[test] fn test_file_header_roundtrip_v7() { - let mut header = FileHeader::new(); + let mut header = LegacyHeaderV7::new(); header.header_checksum = 0xDEAD_BEEF; let bytes = header.to_bytes(); - let parsed = FileHeader::from_bytes(&bytes).unwrap(); + let parsed = LegacyHeaderV7::from_bytes(&bytes).unwrap(); assert_eq!(parsed.header_checksum, 0xDEAD_BEEF); } #[test] fn test_file_header_v7_byte_layout_all_fields() { - let mut h = FileHeader::new(); + let mut h = LegacyHeaderV7::new(); h.page_count = 0x0102_0304_0506_0708_u64; h.node_count = 0x1112_1314_1516_1718_u64; h.last_checkpointed_tx_count = 0x2122_2324_2526_2728_u64; @@ -446,7 +526,7 @@ mod tests { assert_eq!(b.len(), 84, "v7 header must be exactly 84 bytes"); assert_eq!(&b[0..4], b"MGRF"); - assert_eq!(&b[4..8], &FORMAT_VERSION.to_le_bytes()); + assert_eq!(&b[4..8], &7u32.to_le_bytes()); assert_eq!(&b[8..16], &0x0102_0304_0506_0708_u64.to_le_bytes()); assert_eq!(&b[16..24], &0x1112_1314_1516_1718_u64.to_le_bytes()); assert_eq!(&b[24..32], &0x2122_2324_2526_2728_u64.to_le_bytes()); @@ -466,16 +546,16 @@ mod tests { let mut bytes = vec![0u8; 80]; bytes[0..4].copy_from_slice(b"MGRF"); bytes[4..8].copy_from_slice(&7u32.to_le_bytes()); - assert!(FileHeader::from_bytes(&bytes).is_err()); + assert!(LegacyHeaderV7::from_bytes(&bytes).is_err()); } #[test] fn test_file_header_v7_header_checksum_roundtrip() { - let mut h = FileHeader::new(); + let mut h = LegacyHeaderV7::new(); h.header_checksum = 42; let bytes = h.to_bytes(); assert_eq!(bytes.len(), 84); - let parsed = FileHeader::from_bytes(&bytes).unwrap(); + let parsed = LegacyHeaderV7::from_bytes(&bytes).unwrap(); assert_eq!(parsed.header_checksum, 42); } @@ -483,9 +563,9 @@ mod tests { // // STG-001/005 guard byte lengths (<64/<84) that the production // `FileBackend` path never actually produces -- it always hands - // `FileHeader::from_bytes` a full `PAGE_SIZE` (4096-byte) buffer, + // `LegacyHeaderV7::from_bytes` a full `PAGE_SIZE` (4096-byte) buffer, // whatever the real file's length beyond the minimum one page. These - // codes are only reachable by calling `FileHeader::from_bytes` directly + // codes are only reachable by calling `LegacyHeaderV7::from_bytes` directly // with a short slice, which `storage` being crate-private makes // possible only from inside the crate -- hence unit tests here rather // than an integration test against the public `Minigraf` API. @@ -493,7 +573,7 @@ mod tests { #[test] fn from_bytes_too_short_returns_stg_001() { let bytes = vec![0u8; 10]; // < 64 bytes - let err = FileHeader::from_bytes(&bytes).expect_err("10 bytes is too short"); + let err = LegacyHeaderV7::from_bytes(&bytes).expect_err("10 bytes is too short"); let coded: crate::error::MinigrafError = err.into(); assert_eq!(coded.code(), "STG-001"); } @@ -503,7 +583,7 @@ mod tests { let mut bytes = vec![0u8; 82]; // >= 80, < 84 bytes[0..4].copy_from_slice(b"MGRF"); bytes[4..8].copy_from_slice(&7u32.to_le_bytes()); // version = 7 - let err = FileHeader::from_bytes(&bytes).expect_err("82 bytes is too short for v7"); + let err = LegacyHeaderV7::from_bytes(&bytes).expect_err("82 bytes is too short for v7"); let coded: crate::error::MinigrafError = err.into(); assert_eq!(coded.code(), "STG-005"); } @@ -511,9 +591,10 @@ mod tests { #[test] fn from_bytes_pre_v7_returns_stg_028() { for version in 1u32..=6 { - let mut bytes = FileHeader::new().to_bytes(); + let mut bytes = LegacyHeaderV7::new().to_bytes(); bytes[4..8].copy_from_slice(&version.to_le_bytes()); - let err = FileHeader::from_bytes(&bytes).expect_err("pre-v7 header must be rejected"); + let err = + LegacyHeaderV7::from_bytes(&bytes).expect_err("pre-v7 header must be rejected"); let coded: crate::error::MinigrafError = err.into(); assert_eq!(coded.code(), "STG-028"); } @@ -521,7 +602,7 @@ mod tests { #[test] fn validate_pre_v7_returns_stg_028() { - let mut h = FileHeader::new(); + let mut h = LegacyHeaderV7::new(); h.version = 6; let err = h.validate().expect_err("v6 must be rejected"); let coded: crate::error::MinigrafError = err.into(); diff --git a/src/storage/packed_pages.rs b/src/storage/packed_pages.rs index 4bb874aa3e..e55d2e62bd 100644 --- a/src/storage/packed_pages.rs +++ b/src/storage/packed_pages.rs @@ -1,13 +1,13 @@ -//! Packed fact page format (page_type = 0x02). +//! Packed fact pages. //! -//! Layout of a packed page: -//! ```text -//! [12-byte header] -//! byte 0: page_type (0x02 = packed fact data) -//! byte 1: _reserved (0x00) -//! bytes 2-3: record_count (u16 LE) -//! bytes 4-11: next_page (u64 LE, 0 = no overflow) +//! Format v8 (interim, page_type = 0x41, until fact pages are replaced by covering +//! indexes) uses the common 24-byte page header ([`crate::storage::page`]), with +//! `record_count` in its `count` field. Format v7 (page_type = 0x02) used a 12-byte +//! header with a `next_page` field that was always 0; it is read only to migrate a +//! v7 file. //! +//! Layout after the header: +//! ```text //! [record directory: record_count × 4 bytes each] //! per entry: offset u16 LE | length u16 LE //! (offset measured from page start) @@ -25,19 +25,32 @@ use crate::storage::index::FactRef; use crate::storage::{PAGE_SIZE, StorageBackend}; use anyhow::Result; -/// Page type byte for packed fact pages. -pub const PAGE_TYPE_PACKED: u8 = 0x02; -/// Page type byte for overflow pages (reserved, not yet used). -#[allow(dead_code)] -pub const PAGE_TYPE_OVERFLOW: u8 = 0x03; - -/// Packed page header size in bytes. -pub const PACKED_HEADER_SIZE: usize = 12; +/// Page type byte for format v8 (interim) packed fact pages. +pub const PAGE_TYPE_PACKED: u8 = crate::storage::page::PAGE_TYPE_FACT_INTERIM; +/// Page type byte for format v7 packed fact pages (read only, for migration). +pub const PAGE_TYPE_PACKED_V7: u8 = 0x02; + +/// Packed page header size in bytes (the common v8 page header). +pub const PACKED_HEADER_SIZE: usize = crate::storage::page::PAGE_HEADER_SIZE; +/// Format v7 packed page header size in bytes. +const PACKED_HEADER_SIZE_V7: usize = 12; + +/// Header size of a packed page of either format, by its type byte. +fn header_size_of(page_type: u8) -> Option { + match page_type { + PAGE_TYPE_PACKED => Some(PACKED_HEADER_SIZE), + PAGE_TYPE_PACKED_V7 => Some(PACKED_HEADER_SIZE_V7), + _ => None, + } +} /// Maximum serialised size (postcard bytes) for a single fact in a packed page. /// -/// Derived from the page layout: `PAGE_SIZE (4096) - PACKED_HEADER_SIZE (12) - 4` -/// (4 bytes for one record-directory entry). +/// Every index key derived from a fact is at least one byte smaller than the +/// fact's own encoding (it drops `tx_id`), and one key must fit in a B+tree +/// internal node beside its header, `rightmost_child`, one child pointer and +/// one slot: `PAGE_SIZE (4096) - 24 - 8 - 8 - 4 = 4052`. That is tighter than +/// the packed page's own bound (`4096 - 24 - 4`), so it is the limit. /// /// In practice the usable space for a `Value::String` is roughly 3 900–4 000 bytes /// after accounting for the fixed overhead of the other `Fact` fields (two UUIDs, @@ -45,7 +58,7 @@ pub const PACKED_HEADER_SIZE: usize = 12; /// /// File-backed databases reject facts that exceed this limit at insertion time. /// In-memory databases (`Minigraf::in_memory()`) have no size constraint. -pub const MAX_FACT_BYTES: usize = PAGE_SIZE - PACKED_HEADER_SIZE - 4; +pub const MAX_FACT_BYTES: usize = PAGE_SIZE - PACKED_HEADER_SIZE - 8 - 8 - 4; /// Pack a slice of facts into packed pages. /// @@ -184,9 +197,9 @@ pub fn read_slot(page: &[u8], slot: u16) -> Result { let page_type = *page .first() .ok_or_else(|| err_coded!(ErrorCode::Int024, "packed page empty"))?; - if page_type != PAGE_TYPE_PACKED { + let Some(header_size) = header_size_of(page_type) else { bail_coded!(ErrorCode::Stg014, format!("{:02x}", page_type)); - } + }; let b2 = *page .get(2) .ok_or_else(|| err_coded!(ErrorCode::Int024, "too short for record_count byte 2"))?; @@ -203,7 +216,7 @@ pub fn read_slot(page: &[u8], slot: u16) -> Result { // dir_base = PACKED_HEADER_SIZE + slot * 4; slot < record_count <= u16::MAX, // so slot as usize * 4 <= (65534 * 4) which fits in usize. let slot_usize = usize::from(slot); - let dir_base = PACKED_HEADER_SIZE.saturating_add(slot_usize.saturating_mul(4)); + let dir_base = header_size.saturating_add(slot_usize.saturating_mul(4)); let db0 = *page .get(dir_base) .ok_or_else(|| err_coded!(ErrorCode::Int024, format!("dir entry {slot} out of bounds")))?; @@ -246,26 +259,20 @@ pub fn read_slot(page: &[u8], slot: u16) -> Result { Ok(fact) } -/// Read all facts from a contiguous range of packed fact pages. -/// -/// `first_page_id` is the backend page ID of the first packed fact page. -/// `num_pages` is the number of pages to read. -/// Non-packed pages (e.g., index pages) are silently skipped. -pub fn read_all_from_pages( - backend: &dyn StorageBackend, - first_page_id: u64, - num_pages: u64, -) -> Result> { - Ok(read_all_with_refs(backend, first_page_id, num_pages)?.0) +/// Read every fact on one packed page, in slot order. +pub fn read_page_facts(page: &[u8]) -> Result> { + let b2 = page.get(2).copied().unwrap_or(0); + let b3 = page.get(3).copied().unwrap_or(0); + (0..u16::from_le_bytes([b2, b3])) + .map(|slot| read_slot(page, slot)) + .collect() } -/// Read every fact from `num_pages` packed pages, together with the `FactRef` that -/// addresses each fact at its actual on-disk location. +/// Read every fact from the `num_pages` format v7 fact pages starting at +/// `first_page_id`, together with the `FactRef` of its on-disk location. /// -/// Unlike re-packing the facts with [`pack_facts`], the returned refs reflect the real -/// page layout, which is not contiguous when the file was written by several `save()` -/// calls (each starts a fresh page). -pub fn read_all_with_refs( +/// Used only to migrate a v7 file; pages that are not v7 fact pages are skipped. +pub fn read_all_with_refs_v7( backend: &dyn StorageBackend, first_page_id: u64, num_pages: u64, @@ -276,7 +283,7 @@ pub fn read_all_with_refs( let page_id = first_page_id.saturating_add(i); let page = backend.read_page(page_id)?; let page_type = page.first().copied().unwrap_or(0); - if page.len() < PAGE_SIZE || page_type != PAGE_TYPE_PACKED { + if page.len() < PAGE_SIZE || page_type != PAGE_TYPE_PACKED_V7 { continue; } let b2 = page.get(2).copied().unwrap_or(0); @@ -303,7 +310,7 @@ fn new_packed_page() -> Vec { } // byte 1: reserved = 0x00 (already zero from vec initialisation) // bytes 2-3: record_count = 0 (written later via write_record_count) - // bytes 4-11: next_page = 0 (already zero) + // bytes 4-23: crc, page id, generation (set by `page::seal` when written) page } @@ -369,15 +376,15 @@ mod tests { } #[test] - fn test_page_type_byte_is_0x02() { + fn test_page_type_byte_is_0x41() { let facts = vec![make_fact(1)]; let (pages, _) = pack_facts(&facts, 1).unwrap(); assert_eq!(pages[0][0], PAGE_TYPE_PACKED); } - /// Pin every field in the 12-byte page header to its canonical byte offset. + /// Pin the packed-page fields of the common 24-byte header to their byte offsets. /// - /// Like the FileHeader layout test, a roundtrip would not catch accidental + /// Like the v7 header layout test, a roundtrip would not catch accidental /// field swaps or `to_ne_bytes()` use on big-endian platforms. We assert /// the raw bytes directly against the spec in the module doc comment. #[test] @@ -386,8 +393,8 @@ mod tests { let (pages, _) = pack_facts(&facts, 1).unwrap(); let page = &pages[0]; - // byte 0: page_type = 0x02 - assert_eq!(page[0], 0x02, "byte 0 must be PAGE_TYPE_PACKED (0x02)"); + // byte 0: page_type = 0x41 + assert_eq!(page[0], 0x41, "byte 0 must be PAGE_TYPE_PACKED (0x41)"); // byte 1: _reserved = 0x00 assert_eq!(page[1], 0x00, "byte 1 must be reserved zero"); @@ -399,27 +406,25 @@ mod tests { assert_eq!(page[2], 3, "record_count low byte at offset 2"); assert_eq!(page[3], 0, "record_count high byte at offset 3"); - // bytes 4..12: next_page (u64 LE) = 0 (no overflow in Phase 6.2) - let next_page = u64::from_le_bytes(page[4..12].try_into().unwrap()); - assert_eq!(next_page, 0, "next_page at bytes 4-11 must be 0"); - assert_eq!(&page[4..12], &0u64.to_le_bytes(), "next_page raw LE bytes"); + // bytes 4..24: crc, page id, generation — zero until sealed on write + assert!(page[4..24].iter().all(|&b| b == 0), "unsealed header tail"); } /// Verify the record directory entry layout: each entry is 4 bytes, - /// (offset: u16 LE, length: u16 LE), starting at byte 12. + /// (offset: u16 LE, length: u16 LE), starting at byte 24. #[test] fn test_packed_page_record_directory_layout() { let facts = vec![make_fact(1)]; let (pages, _) = pack_facts(&facts, 1).unwrap(); let page = &pages[0]; - // With 1 fact, record_count = 1; directory entry at bytes 12..16. + // With 1 fact, record_count = 1; directory entry at bytes 24..28. let record_count = u16::from_le_bytes([page[2], page[3]]); assert_eq!(record_count, 1); - // Directory entry 0: offset (u16 LE) at bytes 12-13, length (u16 LE) at 14-15. - let offset = u16::from_le_bytes([page[12], page[13]]) as usize; - let length = u16::from_le_bytes([page[14], page[15]]) as usize; + // Directory entry 0: offset (u16 LE) at bytes 24-25, length (u16 LE) at 26-27. + let offset = u16::from_le_bytes([page[24], page[25]]) as usize; + let length = u16::from_le_bytes([page[26], page[27]]) as usize; // Offset must be within the page and after the header + directory. assert!( @@ -434,27 +439,25 @@ mod tests { // Verify the bytes at the directory offset are the LE encoding of those values. assert_eq!( - &page[12..14], + &page[24..26], &(offset as u16).to_le_bytes(), "directory offset LE" ); assert_eq!( - &page[14..16], + &page[26..28], &(length as u16).to_le_bytes(), "directory length LE" ); } #[test] - fn test_read_all_from_pages_roundtrip() { - use crate::storage::backend::MemoryBackend; + fn test_read_page_facts_roundtrip() { let facts: Vec = (0..60).map(make_fact).collect(); let (pages, _refs) = pack_facts(&facts, 1).unwrap(); - let mut backend = MemoryBackend::new(); - for (i, page) in pages.iter().enumerate() { - backend.write_page((i + 1) as u64, page).unwrap(); - } - let recovered = read_all_from_pages(&backend, 1, pages.len() as u64).unwrap(); + let recovered: Vec = pages + .iter() + .flat_map(|p| read_page_facts(p).unwrap()) + .collect(); assert_eq!(recovered.len(), 60); for (orig, rec) in facts.iter().zip(recovered.iter()) { assert_eq!(orig.entity, rec.entity); @@ -463,7 +466,7 @@ mod tests { #[test] fn test_oversized_fact_returns_error() { - // Create a fact with a very large string value (>4080 bytes) + // Create a fact with a very large string value (> MAX_FACT_BYTES) let big_string = "x".repeat(5000); let fact = Fact::with_valid_time( Uuid::from_u128(999), @@ -486,7 +489,7 @@ mod tests { fn read_slot_wrong_page_type_returns_stg_014() { let facts = vec![make_fact(1)]; let (mut pages, _) = pack_facts(&facts, 1).unwrap(); - pages[0][0] = 0x01; // corrupt: not PAGE_TYPE_PACKED (0x02) + pages[0][0] = 0x01; // corrupt: not a packed page type let err = read_slot(&pages[0], 0).expect_err("wrong page type must fail to read"); let coded: crate::error::MinigrafError = err.into(); assert_eq!(coded.code(), "STG-014"); @@ -499,13 +502,34 @@ mod tests { fn read_slot_record_beyond_page_boundary_returns_stg_015() { let facts = vec![make_fact(1)]; let (mut pages, _) = pack_facts(&facts, 1).unwrap(); - // Directory entry 0 is at bytes 12..16 (offset u16 LE, length u16 LE). + // Directory entry 0 is at bytes 24..28 (offset u16 LE, length u16 LE). // Corrupt the length field so offset + length > PAGE_SIZE. - pages[0][14] = 0xFF; - pages[0][15] = 0xFF; + pages[0][26] = 0xFF; + pages[0][27] = 0xFF; let err = read_slot(&pages[0], 0) .expect_err("a record extending past the page boundary must fail to read"); let coded: crate::error::MinigrafError = err.into(); assert_eq!(coded.code(), "STG-015"); } + + /// A v7 page (type 0x02, 12-byte header) still reads, for migration. + #[test] + fn v7_page_reads_through_legacy_layout() { + use crate::storage::backend::MemoryBackend; + let facts: Vec = (0..3).map(make_fact).collect(); + let (pages, _) = pack_facts(&facts, 1).unwrap(); + // Re-lay the v8 page as v7: same records, directory moved 12 bytes earlier. + let v8 = &pages[0]; + let mut v7 = vec![0u8; PAGE_SIZE]; + v7[0] = PAGE_TYPE_PACKED_V7; + v7[2..4].copy_from_slice(&v8[2..4]); + v7[12..12 + 3 * 4].copy_from_slice(&v8[24..24 + 3 * 4]); + v7[100..].copy_from_slice(&v8[100..]); + let mut backend = MemoryBackend::new(); + backend.write_page(1, &v7).unwrap(); + let (read, refs) = read_all_with_refs_v7(&backend, 1, 1).unwrap(); + assert_eq!(read.len(), 3); + assert_eq!(refs[2].slot_index, 2); + assert_eq!(read[1].entity, facts[1].entity); + } } diff --git a/src/storage/page.rs b/src/storage/page.rs new file mode 100644 index 0000000000..9c3f12ef2f --- /dev/null +++ b/src/storage/page.rs @@ -0,0 +1,314 @@ +//! Common header of every non-meta page in a format v8 file (spec §4.2). +//! +//! ```text +//! 0 page_type u8 +//! 1 reserved u8 (0) +//! 2..4 count u16 (entries, keys, records or ids, by type) +//! 4..8 crc32 u32 over the full page with this field zeroed +//! 8..16 page_id u64, the page's own id +//! 16..24 generation u64, the checkpoint generation that wrote it +//! ``` +//! +//! Type values: the high nibble is the page family, the low nibble the variant. +//! Values used by earlier formats are retired and never reassigned: 0x02/0x03 +//! (v5–v7 fact pages), 0x11 (v5 index pages), 0x21/0x22 (v6/v7 B+tree). + +use crate::error::{ErrorCode, bail_coded, err_coded}; +use crate::storage::PAGE_SIZE; +use anyhow::Result; + +/// Size of the common page header. +pub const PAGE_HEADER_SIZE: usize = 24; + +/// Packed fact page. Interim: exists only until fact pages are removed by the +/// covering-index change; files carrying it are pre-release and the value is +/// then retired. +pub const PAGE_TYPE_FACT_INTERIM: u8 = 0x41; +/// Long-value page (spec §6.3). Not written yet. +#[allow(dead_code)] +pub const PAGE_TYPE_VALUE: u8 = 0x51; +/// Value overflow page. Reserved, never written. +#[allow(dead_code)] +pub const PAGE_TYPE_VALUE_OVERFLOW: u8 = 0x52; +/// B+tree leaf node. +pub const PAGE_TYPE_LEAF: u8 = 0x61; +/// B+tree internal node. +pub const PAGE_TYPE_INTERNAL: u8 = 0x62; +/// Free-list page. +pub const PAGE_TYPE_FREELIST: u8 = 0x81; + +const CRC_RANGE: std::ops::Range = 4..8; +const ID_RANGE: std::ops::Range = 8..16; +const GEN_RANGE: std::ops::Range = 16..24; + +fn is_known_type(t: u8) -> bool { + matches!( + t, + PAGE_TYPE_FACT_INTERIM + | PAGE_TYPE_VALUE + | PAGE_TYPE_VALUE_OVERFLOW + | PAGE_TYPE_LEAF + | PAGE_TYPE_INTERNAL + | PAGE_TYPE_FREELIST + ) +} + +fn field_u64(page: &[u8], range: std::ops::Range) -> Result { + let bytes = page + .get(range) + .ok_or_else(|| err_coded!(ErrorCode::Int049, "page shorter than its header"))?; + Ok(u64::from_le_bytes(bytes.try_into().map_err(|_| { + err_coded!(ErrorCode::Int049, "page header field is not 8 bytes") + })?)) +} + +/// CRC32 of `page` with the CRC field treated as zero. +fn page_crc(page: &[u8]) -> Result { + let (head, rest) = (page.get(..CRC_RANGE.start), page.get(CRC_RANGE.end..)); + let (head, rest) = head + .zip(rest) + .ok_or_else(|| err_coded!(ErrorCode::Int049, "page shorter than its header"))?; + let mut h = crc32fast::Hasher::new(); + h.update(head); + h.update(&[0u8; 4]); + h.update(rest); + Ok(h.finalize()) +} + +/// The type byte of a page. +pub fn page_type(page: &[u8]) -> Option { + page.first().copied() +} + +/// The `count` field of a page. +pub fn page_count_field(page: &[u8]) -> Result { + let bytes = page + .get(2..4) + .ok_or_else(|| err_coded!(ErrorCode::Int049, "page shorter than its header"))?; + Ok(u16::from_le_bytes([ + *bytes.first().unwrap_or(&0), + *bytes.get(1).unwrap_or(&0), + ])) +} + +/// The generation recorded in a page header. +pub fn page_generation(page: &[u8]) -> Result { + field_u64(page, GEN_RANGE) +} + +/// Write `page_id` and `generation` into the header, then the CRC over the page. +/// +/// The caller has already written the type and count bytes and the body. +pub fn seal(page: &mut [u8], page_id: u64, generation: u64) -> Result<()> { + if page.len() != PAGE_SIZE { + bail_coded!(ErrorCode::Int051, page.len(), PAGE_SIZE); + } + let too_short = || err_coded!(ErrorCode::Int049, "page shorter than its header"); + page.get_mut(ID_RANGE) + .ok_or_else(too_short)? + .copy_from_slice(&page_id.to_le_bytes()); + page.get_mut(GEN_RANGE) + .ok_or_else(too_short)? + .copy_from_slice(&generation.to_le_bytes()); + let crc = page_crc(page)?; + page.get_mut(CRC_RANGE) + .ok_or_else(too_short)? + .copy_from_slice(&crc.to_le_bytes()); + Ok(()) +} + +/// Run the read checks of spec §4.2 (1–4) and return the page type. +/// +/// The type check runs first, so a legacy or foreign page fails with STG-013 +/// before any CRC is computed. Checking the specific expected type (check 5) +/// is left to the caller. +pub fn verify(page: &[u8], expected_id: u64, max_generation: u64) -> Result { + let t = match page_type(page) { + Some(t) if is_known_type(t) && page.len() == PAGE_SIZE => t, + _ => bail_coded!(ErrorCode::Stg013, expected_id), + }; + let stored = page + .get(CRC_RANGE) + .and_then(|b| <[u8; 4]>::try_from(b).ok()) + .map(u32::from_le_bytes) + .ok_or_else(|| err_coded!(ErrorCode::Int049, "page shorter than its header"))?; + if stored != page_crc(page)? { + bail_coded!(ErrorCode::Stg029, expected_id); + } + let id = field_u64(page, ID_RANGE)?; + if id != expected_id { + bail_coded!(ErrorCode::Stg030, expected_id, id); + } + let generation = field_u64(page, GEN_RANGE)?; + if generation > max_generation { + bail_coded!(ErrorCode::Stg031, expected_id, generation, max_generation); + } + Ok(t) +} + +/// A zeroed page with the type and count bytes set. +pub fn new_page(page_type: u8, count: u16) -> Vec { + let mut page = vec![0u8; PAGE_SIZE]; + if let Some(b) = page.first_mut() { + *b = page_type; + } + if let Some(c) = page.get_mut(2..4) { + c.copy_from_slice(&count.to_le_bytes()); + } + page +} + +/// Hands out page ids for one checkpoint generation and writes sealed pages. +/// +/// `alloc` takes the lowest id from the active meta's free list first, then +/// appends at the high-water mark; `alloc_append` always appends. Every id it +/// hands out is unreferenced by the active meta (spec §8.1), so writing it can +/// never damage the committed state. +pub struct PageAllocator { + /// Free ids, highest first, so `pop` yields the lowest. + free: Vec, + next_append: u64, + generation: u64, +} + +impl PageAllocator { + /// An allocator over `free` (any order) that appends from `next_append`. + pub fn new(mut free: Vec, next_append: u64, generation: u64) -> Self { + free.sort_unstable_by(|a, b| b.cmp(a)); + PageAllocator { + free, + next_append, + generation, + } + } + + /// The generation every page written through this allocator is stamped with. + #[cfg(test)] + pub fn generation(&self) -> u64 { + self.generation + } + + /// The high-water mark: one past the highest id handed out or inherited. + pub fn next_append(&self) -> u64 { + self.next_append + } + + /// A free id if any is left, otherwise a new one at the end. + pub fn alloc(&mut self) -> Result { + match self.free.pop() { + Some(id) => Ok(id), + None => self.alloc_append(), + } + } + + /// A new id at the end of the file. + pub fn alloc_append(&mut self) -> Result { + let id = self.next_append; + self.next_append = id + .checked_add(1) + .ok_or_else(|| err_coded!(ErrorCode::Int048, "page id overflow"))?; + Ok(id) + } + + /// Free ids not handed out, lowest first. + pub fn take_unused_free(&mut self) -> Vec { + let mut v = std::mem::take(&mut self.free); + v.reverse(); + v + } + + /// Seal `page` as `page_id` in this generation, write it, and put it in the + /// cache so that a reused id never serves stale bytes. + pub fn write( + &self, + backend: &mut dyn crate::storage::StorageBackend, + cache: &crate::storage::cache::PageCache, + page_id: u64, + mut page: Vec, + ) -> Result<()> { + seal(&mut page, page_id, self.generation)?; + backend.write_page(page_id, &page)?; + cache.put_dirty(page_id, page); + Ok(()) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + fn code_of(e: anyhow::Error) -> &'static str { + crate::error::MinigrafError::from(e).code() + } + + fn sealed(id: u64, generation: u64) -> Vec { + let mut p = new_page(PAGE_TYPE_LEAF, 3); + if let Some(b) = p.get_mut(100) { + *b = 0xAB; + } + seal(&mut p, id, generation).unwrap(); + p + } + + #[test] + fn seal_then_verify_round_trips() { + let p = sealed(7, 3); + assert_eq!(verify(&p, 7, 3).unwrap(), PAGE_TYPE_LEAF); + assert_eq!(page_count_field(&p).unwrap(), 3); + assert_eq!(page_generation(&p).unwrap(), 3); + } + + #[test] + fn flipped_body_bit_is_stg_029() { + let mut p = sealed(7, 3); + if let Some(b) = p.get_mut(4000) { + *b ^= 1; + } + assert_eq!(code_of(verify(&p, 7, 3).unwrap_err()), "STG-029"); + } + + #[test] + fn wrong_page_id_is_stg_030() { + let p = sealed(7, 3); + assert_eq!(code_of(verify(&p, 8, 3).unwrap_err()), "STG-030"); + } + + #[test] + fn future_generation_is_stg_031() { + let p = sealed(7, 4); + assert_eq!(code_of(verify(&p, 7, 3).unwrap_err()), "STG-031"); + } + + #[test] + fn legacy_type_fails_before_crc() { + // A v7 B+tree leaf (0x21) with garbage where the CRC would be. + let mut p = vec![0u8; PAGE_SIZE]; + p[0] = 0x21; + p[5] = 0x99; + assert_eq!(code_of(verify(&p, 7, 3).unwrap_err()), "STG-013"); + for retired in [0x02u8, 0x03, 0x11, 0x22, 0x00] { + p[0] = retired; + assert_eq!(code_of(verify(&p, 7, 3).unwrap_err()), "STG-013"); + } + } + + #[test] + fn short_page_is_rejected() { + let p = vec![PAGE_TYPE_LEAF; 10]; + assert!(verify(&p, 0, 0).is_err()); + let mut q = vec![0u8; 10]; + assert!(seal(&mut q, 0, 0).is_err()); + } + + #[test] + fn allocator_takes_lowest_free_then_appends() { + let mut a = PageAllocator::new(vec![9, 4, 7], 20, 2); + assert_eq!(a.alloc().unwrap(), 4); + assert_eq!(a.alloc_append().unwrap(), 20); + assert_eq!(a.alloc().unwrap(), 7); + assert_eq!(a.take_unused_free(), vec![9]); + assert_eq!(a.alloc().unwrap(), 21); + assert_eq!(a.next_append(), 22); + assert_eq!(a.generation(), 2); + } +} diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index ef1eed9ff7..d947a42cd2 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -1,67 +1,39 @@ +//! Persistent fact storage: bridges [`FactStorage`] and a page-based +//! [`StorageBackend`] in format v8. +//! +//! Layout (spec §4): pages 0 and 1 are alternating meta pages, the only commit +//! point. Every other page carries the common header (type, CRC, page id, +//! generation) and is verified on every read. A checkpoint writes only pages the +//! active meta does not reference, syncs, then writes the other meta slot and +//! syncs again, so a crash at any point leaves the previous checkpoint intact. use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::graph::FactStorage; -/// Persistent fact storage that integrates StorageBackend with Datalog facts. -/// -/// This module bridges the gap between high-level fact operations and -/// low-level page-based storage backends. use crate::graph::types::Fact; -use crate::storage::FACT_PAGE_FORMAT_PACKED; use crate::storage::btree_v6::{ - MutexStorageBackend, OnDiskIndexReader, btree_entries, build_btree, collect_leaf_pages, - rebuild_btree_incremental, + LeafCursor, MutexStorageBackend, OnDiskIndexReader, btree_entries, build_btree, + collect_leaf_pages, rebuild_btree_incremental, }; use crate::storage::cache::PageCache; use crate::storage::index::{AevtKey, AvetKey, EavtKey, FactRef, VaetKey}; -use crate::storage::packed_pages::pack_facts; -use crate::storage::{FORMAT_VERSION, FileHeader, PAGE_SIZE, StorageBackend}; +use crate::storage::meta::{MetaPage, SlotState, slot_page}; +use crate::storage::packed_pages::{PAGE_TYPE_PACKED, pack_facts}; +use crate::storage::page::PageAllocator; +use crate::storage::{LegacyHeaderV7, PAGE_SIZE, StorageBackend, freelist, page}; use anyhow::Result; -use crc32fast::Hasher; -use std::sync::atomic::{AtomicU64, Ordering}; use std::sync::{Arc, Mutex}; -/// Compute the CRC32 sync checksum over all facts (used in tests only). -/// -/// Sorts facts by `(tx_count, entity_bytes, attribute)` before hashing to -/// produce a stable total order independent of Vec insertion order. -#[cfg(all(test, not(target_arch = "wasm32")))] -fn compute_index_checksum(facts: &[Fact]) -> u32 { - let mut sorted: Vec<&Fact> = facts.iter().collect(); - sorted.sort_by(|a, b| { - a.tx_count - .cmp(&b.tx_count) - .then_with(|| a.entity.as_bytes().cmp(b.entity.as_bytes())) - .then_with(|| a.attribute.as_str().cmp(b.attribute.as_str())) - }); - let mut hasher = Hasher::new(); - for fact in sorted { - let bytes = postcard::to_allocvec(fact) - .expect("BUG: failed to serialize Fact for index checksum; this should never happen"); - hasher.update(&bytes); - } - hasher.finalize() -} - /// CommittedFactReader backed by a PageCache + shared backend. /// -/// Resolves FactRefs to Fact objects by reading packed pages from the backend -/// through the page cache. Used after loading (or migrating) a v5/v6 file so that indexes can -/// resolve committed facts without keeping the entire fact list in memory. -// Fields are read inside CommittedFactReader trait methods that are accessed via -// dyn dispatch — Rust's dead-code lint does not track trait-impl field reads -// when the impl is behind dyn dispatch. +/// Resolves FactRefs to Fact objects by reading packed pages through the page +/// cache, so indexes can resolve committed facts without keeping the entire +/// fact list in memory. struct CommittedFactLoaderImpl { - #[allow(dead_code)] - backend: Arc>, - #[allow(dead_code)] page_cache: Arc, - /// Pre-built adapter reused on every `resolve()` call. - /// Avoids an `Arc::clone` per call: the adapter is constructed once and - /// holds the `Arc>` for the lifetime of this reader. - /// Backend mutex is still only acquired on cache misses (see `MutexStorageBackend`). + /// Pre-built adapter reused on every `resolve()` call; the backend mutex is + /// only acquired on cache misses (see `MutexStorageBackend`). backend_adapter: MutexStorageBackend, - committed_fact_pages: Arc, - #[allow(dead_code)] - first_fact_page: u64, // always 1 in current layout + /// EAVT root of the committed meta; `stream_all` finds the fact pages here. + eavt_root: u64, } impl crate::storage::CommittedFactReader @@ -71,123 +43,103 @@ impl crate::storage::CommittedFactReader &self, fact_ref: crate::storage::index::FactRef, ) -> anyhow::Result { - // backend_adapter is pre-built at construction time — no Arc::clone per call. - // Backend mutex is only acquired inside adapter.read_page() on a cache miss. let page = self .page_cache .get_or_load(fact_ref.page_id, &self.backend_adapter)?; crate::storage::packed_pages::read_slot(&page, fact_ref.slot_index) } + /// Every committed fact, in insertion order. + /// + /// Fact pages are only ever appended, so ascending page id is insertion + /// order. The pages are found through EAVT, which references every fact. fn stream_all(&self) -> anyhow::Result> { - let n = self.committed_fact_pages.load(Ordering::SeqCst); - let backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - crate::storage::packed_pages::read_all_from_pages(&*backend, 1, n) - } - - fn committed_page_count(&self) -> u64 { - self.committed_fact_pages.load(Ordering::SeqCst) + if self.eavt_root == 0 { + return Ok(Vec::new()); + } + let mut page_ids = std::collections::BTreeSet::new(); + let mut cursor = LeafCursor::::new( + self.eavt_root, + None, + &self.backend_adapter, + &self.page_cache, + )?; + while let Some((_, fr)) = cursor.next_ref()? { + page_ids.insert(fr.page_id); + } + let mut facts = Vec::new(); + for id in page_ids { + let page = self.page_cache.get_or_load(id, &self.backend_adapter)?; + let page_type = page.first().copied().unwrap_or(0); + if page_type != PAGE_TYPE_PACKED { + bail_coded!(ErrorCode::Stg014, format!("{page_type:02x}")); + } + facts.extend(crate::storage::packed_pages::read_page_facts(&page)?); + } + Ok(facts) } } -/// Persistent fact storage with serialization support. -/// -/// Architecture: -/// - Page 0: File header (metadata) -/// - Page 1+: Serialized facts (one fact per page, for simplicity) -/// -/// # Storage Strategy (Phase 3-5) -/// -/// Current implementation uses a simple "load all, save all" approach: -/// - On open: Deserialize all facts into memory (FactStorage) -/// - All operations: Work on in-memory `Vec` -/// - On save: Serialize all facts back to disk -/// -/// **Trade-offs:** -/// - ✅ Simple, correct, easy to reason about -/// - ✅ Fast queries (no disk I/O) -/// - ✅ Good for embedded use cases with small-medium datasets -/// - ❌ Memory usage = entire database size -/// - ❌ Not scalable to very large datasets -/// -/// **Scalability:** -/// - Works well for <100K facts (typical use case) -/// - Memory footprint: ~100-200 bytes per fact -/// - Example: 100K facts ≈ 10-20MB memory (acceptable for embedded) +/// Persistent fact storage with page-based persistence. /// -/// # Future: Phase 6 (Performance) -/// -/// Phase 6 will introduce page-based access with indexes: -/// - EAVT, AEVT, AVET, VAET indexes (in-memory B-trees) -/// - On-demand fact loading from disk -/// - LRU cache for hot pages -/// - Memory-mapped file access (optional) -/// - Target: Scale to millions of facts with bounded memory -/// -/// The page-based backend (StorageBackend) is designed to support this -/// future architecture without breaking changes. +/// Committed facts live on disk and are read on demand through the on-disk +/// indexes and the page cache; facts written since the last checkpoint live in +/// memory (and in the WAL) until `save()` commits them. pub struct PersistentFactStorage { backend: Arc>, page_cache: Arc, storage: FactStorage, dirty: bool, - last_checkpointed_tx_count: u64, - committed_fact_pages: Arc, - /// CRC32 state after hashing fact pages `1..=n` (`n` is the first element). - /// Fact pages are never rewritten, so `save()` extends this instead of - /// re-reading them; `None` (or a stale `n`) falls back to a full pass (#315). - fact_prefix_crc: Option<(u64, Hasher)>, + /// The active (last committed) meta page. + meta: MetaPage, +} + +/// What open found in the meta slots. +enum Opened { + Meta(MetaPage), + LegacyV7(LegacyHeaderV7), + Fresh, } impl PersistentFactStorage { - /// Create a new persistent storage with the given backend. + /// Open storage on `backend` with no WAL beside it (in-memory and browser + /// databases). See [`PersistentFactStorage::open`]. + pub fn new(backend: B, page_cache_capacity: usize) -> Result { + Self::open(backend, page_cache_capacity, None) + } + + /// Open storage on `backend`, creating an empty database if it has no pages. /// - /// If the backend already contains data, loads it. - /// Otherwise, initializes a new empty fact storage. + /// `wal_base_generation` is the base generation recorded in the WAL beside + /// the file, or `None` if there is no WAL. It decides meta selection when + /// only one meta slot is valid (spec §4.1.1). /// /// `page_cache_capacity` controls the LRU page cache size (in pages). /// A value of 256 means at most 256 x 4KB = 1MB of cached pages. - pub fn new(backend: B, page_cache_capacity: usize) -> Result { - let backend = Arc::new(Mutex::new(backend)); - let page_cache = Arc::new(PageCache::new(page_cache_capacity)); - let committed_fact_pages = Arc::new(AtomicU64::new(0)); - let mut persistent = PersistentFactStorage { - backend, - page_cache, + pub fn open( + backend: B, + page_cache_capacity: usize, + wal_base_generation: Option, + ) -> Result { + let mut pfs = PersistentFactStorage { + backend: Arc::new(Mutex::new(backend)), + page_cache: Arc::new(PageCache::new(page_cache_capacity)), storage: FactStorage::new(), dirty: false, - last_checkpointed_tx_count: 0, - committed_fact_pages, - fact_prefix_crc: None, + meta: MetaPage::empty(1), }; - - // Try to load existing data. - // - // The load condition combines two checks: - // - `!is_new`: FileBackend reports false when the file existed on disk - // (even with only a header page, page_count == 1). This ensures - // `load()` runs (and its version check rejects pre-v7 files) even - // for a file that has no fact pages. - // - `page_count > 1`: catches MemoryBackend, which always reports - // is_new == true; page count > 1 means facts were previously saved. - let (is_new_backend, page_count) = { - let b = persistent - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - (b.is_new(), b.page_count()?) + let meta = match pfs.select_meta(wal_base_generation)? { + Opened::Fresh => pfs.init_empty()?, + Opened::Meta(m) => { + m.check_features()?; + m + } + Opened::LegacyV7(h) => pfs.migrate_v7(&h)?, }; - if !is_new_backend || page_count > 1 { - persistent.load()?; - } else { - // New database: FileBackend already wrote the initial header; - // MemoryBackend starts empty. Nothing to save yet. - } - - Ok(persistent) + pfs.activate(meta); + pfs.storage + .restore_tx_counter_from(meta.last_checkpointed_tx_count); + Ok(pfs) } /// The LRU page cache capacity this storage was constructed with (for testing). @@ -196,247 +148,169 @@ impl PersistentFactStorage { self.page_cache.capacity() } - /// Load all facts from the backend into memory. - fn load(&mut self) -> Result<()> { - let (header, raw_header_bytes) = { - let backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - let header_page = backend.read_page(0)?; - let h = FileHeader::from_bytes(&header_page)?; - h.validate()?; - (h, header_page) - }; + fn lock(&self) -> Result> { + self.backend + .lock() + .map_err(|_| err_coded!(ErrorCode::Stg016)) + } - // For v7+ files, validate header checksum using raw bytes from disk - if header.header_checksum != 0 { - let computed = compute_header_checksum_from_bytes(&raw_header_bytes); - if header.header_checksum != computed { - bail_coded!(ErrorCode::Int053); - } + /// Choose the meta page to open at (spec §4.1.1). Never modifies the file, + /// except to restore page 0 from the migration backup meta (§9 step 5). + fn select_meta(&self, wal_base: Option) -> Result { + let mut backend = self.lock()?; + let page_count = backend.page_count()?; + if page_count == 0 { + return Ok(Opened::Fresh); } - - // Store last_checkpointed_tx_count from header (0 for v2 files) - self.last_checkpointed_tx_count = header.last_checkpointed_tx_count; - - // Clear existing storage - self.storage.clear()?; - - // v6 packed format - let num_fact_pages = if header.fact_page_count > 0 { - header.fact_page_count + let page0 = backend.read_page(0)?; + let slot_a = MetaPage::decode(&page0); + let slot_b = if page_count > 1 { + MetaPage::decode(&backend.read_page(1)?) } else { - let first_index_page = [ - header.eavt_root_page, - header.aevt_root_page, - header.avet_root_page, - header.vaet_root_page, - ] - .iter() - .filter(|&&p| p > 0) - .copied() - .min() - .unwrap_or(header.page_count); - first_index_page.saturating_sub(1) + SlotState::Empty }; - self.committed_fact_pages - .store(num_fact_pages, Ordering::SeqCst); - - // v7 files carry index keys without value bytes / asserted flags; they - // cannot be decoded as v8 keys, so rebuild every index from the fact - // pages (#371, #287). The header is written last, so a crash mid-rebuild - // leaves a v7 header and the next open rebuilds again. - let needs_rebuild = if header.version < FORMAT_VERSION { - true - } else if num_fact_pages == 0 || header.eavt_root_page == 0 { - num_fact_pages > 0 // rebuild if facts exist but no index root - } else { - let backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - let total_data_pages = header.page_count.saturating_sub(1); - // Hash fact pages, keep that state for save() (#315), then the index pages. - let (full_checksum, fact_prefix) = if total_data_pages >= num_fact_pages { - let mut hasher = Hasher::new(); - hash_pages(&*backend, &mut hasher, 1, num_fact_pages)?; - let prefix = hasher.clone(); - let index_start = num_fact_pages - .checked_add(1) - .ok_or_else(|| err_coded!(ErrorCode::Stg021))?; - hash_pages( - &*backend, - &mut hasher, - index_start, - total_data_pages.saturating_sub(num_fact_pages), - )?; - (hasher.finalize(), Some(prefix)) - } else { - (compute_page_checksum(&*backend, 1, total_data_pages)?, None) - }; - if full_checksum == header.index_checksum { - self.fact_prefix_crc = fact_prefix.map(|p| (num_fact_pages, p)); - false - } else { - true + match (slot_a, slot_b) { + (SlotState::Valid(a), SlotState::Valid(b)) => { + Ok(Opened::Meta(if a.generation >= b.generation { + a + } else { + b + })) } - }; + (SlotState::Valid(m), _) | (_, SlotState::Valid(m)) => { + // Refuse an unreadable file before probing its pages. + m.check_features()?; + check_single_valid(&*backend, m, wal_base)?; + Ok(Opened::Meta(m)) + } + _ => { + if let Some(h) = LegacyHeaderV7::detect(&page0)? { + return Ok(Opened::LegacyV7(h)); + } + // A torn page-0 write while committing a migration: the backup + // meta in the last page carries generation 1 (spec §9 step 5). + let last = backend.read_page(page_count.saturating_sub(1))?; + if let SlotState::Valid(m) = MetaPage::decode(&last) + && m.generation == 1 + && m.page_count == page_count + { + m.check_features()?; + backend.write_page(0, &m.encode())?; + backend.sync()?; + return Ok(Opened::Meta(m)); + } + if page_count <= 2 && is_torn_initial_meta(&*backend, &page0)? { + return Ok(Opened::Fresh); + } + if page0.get(0..4) != Some(&crate::storage::MAGIC_NUMBER[..]) { + // Not a Minigraf file at all (or page 0 overwritten). + bail_coded!(ErrorCode::Stg002) + } + bail_coded!(ErrorCode::Stg032) + } + } + } - // Register CommittedFactReader on FactStorage (before WAL replay) - let loader: std::sync::Arc = - std::sync::Arc::new(CommittedFactLoaderImpl { - backend: self.backend.clone(), - backend_adapter: MutexStorageBackend(self.backend.clone()), + /// Write an empty generation-1 meta to page 0 and a blank page 1, and sync. + fn init_empty(&self) -> Result { + let meta = MetaPage::empty(1); + let mut backend = self.lock()?; + backend.write_page(0, &meta.encode())?; + backend.write_page(1, &vec![0u8; PAGE_SIZE])?; + backend.sync()?; + Ok(meta) + } + + /// Make `meta` the active state: cache bound and committed readers. + fn activate(&mut self, meta: MetaPage) { + self.meta = meta; + self.page_cache.set_generation_bound(meta.generation); + let loader: Arc = + Arc::new(CommittedFactLoaderImpl { page_cache: self.page_cache.clone(), - committed_fact_pages: self.committed_fact_pages.clone(), - first_fact_page: 1, + backend_adapter: MutexStorageBackend(self.backend.clone()), + eavt_root: meta.eavt_root, }); self.storage.set_committed_reader(loader); - - // Restore tx_counter from header - self.storage - .restore_tx_counter_from(header.last_checkpointed_tx_count); - - if needs_rebuild { - // Checksum mismatch: rebuild indexes by re-reading all packed facts - // FactRefs must come from the actual on-disk layout: each save() starts a - // fresh page, so re-packing all facts contiguously would yield refs that - // point at the wrong page/slot (#370). - let (all_facts, real_refs) = { - let backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - crate::storage::packed_pages::read_all_with_refs(&*backend, 1, num_fact_pages)? - }; - - // Build sorted index entries - let (eavt_entries, aevt_entries, avet_entries, vaet_entries) = - build_sorted_index_entries(&all_facts, &real_refs); - - // Fix up tx_counter from actual facts. Empty transactions - // (`(transact [])`, `(retract [])`) still allocate a tx_count - // without producing any facts, so the highest fact tx_count can - // undercount the counter the file was actually at; floor it at - // the old header's last_checkpointed_tx_count so migration never - // rewinds the counter and lets new transactions reuse tx_counts - // that `:as-of N` already served facts for (#371, #287). - let max_fact_tx = all_facts.iter().map(|f| f.tx_count).max().unwrap_or(0); - let max_tx = max_fact_tx.max(header.last_checkpointed_tx_count); - self.storage.restore_tx_counter_from(max_tx); - - // Build v6 B+tree indexes directly - let index_start = 1u64 - .checked_add(num_fact_pages) - .ok_or_else(|| err_coded!(ErrorCode::Stg017))?; - let mut backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - let (eavt_root, next1) = build_btree( - btree_entries(eavt_entries.into_iter())?.into_iter(), - &mut *backend, - &self.page_cache, - index_start, - )?; - let (aevt_root, next2) = build_btree( - btree_entries(aevt_entries.into_iter())?.into_iter(), - &mut *backend, - &self.page_cache, - next1, - )?; - let (avet_root, next3) = build_btree( - btree_entries(avet_entries.into_iter())?.into_iter(), - &mut *backend, - &self.page_cache, - next2, - )?; - let (vaet_root, next4) = build_btree( - btree_entries(vaet_entries.into_iter())?.into_iter(), - &mut *backend, - &self.page_cache, - next3, - )?; - - // Sync index pages to disk before writing the header. - // The header update is the atomic commit point: once it's durable, - // recovery uses the new root pages. All data those roots reference - // must already be on stable storage. - backend.sync()?; - - // Write header with full-coverage checksum (facts + indexes) - let total_data_pages = next4.saturating_sub(1); - let full_checksum = compute_page_checksum(&*backend, 1, total_data_pages)?; - - let mut new_header = FileHeader::new(); - new_header.page_count = next4; - new_header.node_count = all_facts.len() as u64; - new_header.last_checkpointed_tx_count = max_tx; - new_header.eavt_root_page = eavt_root; - new_header.aevt_root_page = aevt_root; - new_header.avet_root_page = avet_root; - new_header.vaet_root_page = vaet_root; - new_header.index_checksum = full_checksum; - new_header.fact_page_format = FACT_PAGE_FORMAT_PACKED; - new_header.fact_page_count = num_fact_pages; - - let write_checksum = compute_header_checksum(&new_header); - new_header.header_checksum = write_checksum; - - let mut header_page = new_header.to_bytes(); - header_page.resize(PAGE_SIZE, 0); - backend.write_page(0, &header_page)?; - backend.sync()?; - drop(backend); - - self.last_checkpointed_tx_count = max_tx; - - // Wire OnDiskIndexReader - let index_reader: std::sync::Arc = - std::sync::Arc::new(OnDiskIndexReader::new( + if meta.eavt_root != 0 { + let index_reader: Arc = + Arc::new(OnDiskIndexReader::new( self.backend.clone(), self.page_cache.clone(), - eavt_root, - aevt_root, - avet_root, - vaet_root, + meta.eavt_root, + meta.aevt_root, + meta.avet_root, + meta.vaet_root, )); self.storage.set_committed_index_reader(index_reader); - } else { - // No rebuild needed - validate header checksum for v7+ files - // Re-read header from disk to get any updates from rebuild path - if header.header_checksum != 0 { - let backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - let current_header_bytes = backend.read_page(0)?; - let current_header = FileHeader::from_bytes(¤t_header_bytes)?; - let computed = compute_header_checksum_from_bytes(¤t_header_bytes); - if current_header.header_checksum != computed { - bail_coded!(ErrorCode::Int053); - } - } + } + } - if header.eavt_root_page != 0 { - // Fast path: v6 — wire OnDiskIndexReader from header roots, no RAM index load - let index_reader: std::sync::Arc = - std::sync::Arc::new(OnDiskIndexReader::new( - self.backend.clone(), - self.page_cache.clone(), - header.eavt_root_page, - header.aevt_root_page, - header.avet_root_page, - header.vaet_root_page, - )); - self.storage.set_committed_index_reader(index_reader); - } + /// Migrate a format v7 file to v8 (spec §9). + /// + /// Everything is appended past the v7 `page_count`; the v7 pages from 2 up + /// become the new free list. A backup of the generation-1 meta is the last + /// page, so a torn page-0 commit write can be repaired on the next open. A + /// crash before the page-0 write leaves the v7 header intact, and the next + /// open migrates again. + fn migrate_v7(&mut self, header: &LegacyHeaderV7) -> Result { + let mut backend = self.lock()?; + let num_fact_pages = header.fact_page_count_or_derived(); + let (facts, _) = + crate::storage::packed_pages::read_all_with_refs_v7(&*backend, 1, num_fact_pages)?; + + // Empty transactions allocate a tx_count without producing facts, so the + // highest fact tx_count can undercount; never rewind past the header's + // counter (#371, #287). + let max_fact_tx = facts.iter().map(|f| f.tx_count).max().unwrap_or(0); + let max_tx = max_fact_tx.max(header.last_checkpointed_tx_count); + + let old_page_count = header.page_count.max(2); + let mut alloc = PageAllocator::new(Vec::new(), old_page_count, 1); + let refs = append_fact_pages(&facts, &mut alloc, &mut *backend, &self.page_cache)?; + let [eavt_root, aevt_root, avet_root, vaet_root] = + build_all_trees(&facts, &refs, &mut alloc, &mut *backend, &self.page_cache)?; + + // Free list: old pages 2.. (page 1 is meta slot B) plus the backup page, + // which is appended right after the chain's own pages. + let mut free: Vec = (2..old_page_count).collect(); + let chain_len = u64::try_from( + free.len() + .saturating_add(1) + .div_ceil(freelist::IDS_PER_PAGE), + ) + .map_err(|_| err_coded!(ErrorCode::Int048, "free-list length"))?; + let backup_id = alloc + .next_append() + .checked_add(chain_len) + .ok_or_else(|| err_coded!(ErrorCode::Int048, "page id overflow"))?; + free.push(backup_id); + let (freelist_head, _) = + freelist::write_chain(&free, &mut alloc, &mut *backend, &self.page_cache)?; + if alloc.alloc_append()? != backup_id { + bail_coded!(ErrorCode::Int049, "migration backup page id mismatch"); } - // else: empty DB — indexes are empty by default, nothing to do. - self.dirty = false; - Ok(()) + let meta = MetaPage { + generation: 1, + page_count: alloc.next_append(), + fact_count: u64::try_from(facts.len()).map_err(|_| err_coded!(ErrorCode::Stg024))?, + last_checkpointed_tx_count: max_tx, + eavt_root, + aevt_root, + avet_root, + vaet_root, + freelist_head, + freelist_count: u64::try_from(free.len()) + .map_err(|_| err_coded!(ErrorCode::Int048, "free-list length"))?, + ..MetaPage::default() + }; + let encoded = meta.encode(); + backend.write_page(backup_id, &encoded)?; + backend.sync()?; + backend.write_page(0, &encoded)?; + backend.sync()?; + Ok(meta) } /// Consume this storage and return the underlying backend. @@ -463,193 +337,113 @@ impl PersistentFactStorage { } } - /// Save all facts from memory to the backend using packed pages and v6 on-disk B+tree indexes. + /// Commit pending facts as the next generation (spec §8.3, full-rewrite form). + /// + /// Fact pages are appended. The four trees are rebuilt into pages the active + /// meta does not reference (its free list first, then appended). Every page of + /// the old trees and the old free-list chain joins the new free list. After a + /// sync, the new meta goes to the other slot and is synced: the only commit + /// point. A failure at any step leaves the active meta and all it references + /// untouched. pub fn save(&mut self) -> Result<()> { if !self.dirty { return Ok(()); } - - // ── Step A: read current header + stream old B+tree entries BEFORE overwriting ── let pending_facts = self.storage.get_pending_facts(); - let mut backend = self - .backend - .lock() - .map_err(|_| err_coded!(ErrorCode::Stg016))?; - - let old_fact_page_count = self.committed_fact_pages.load(Ordering::SeqCst); - let new_fact_start = 1u64 - .checked_add(old_fact_page_count) - .ok_or_else(|| err_coded!(ErrorCode::Stg019))?; - - let curr_header = match backend.read_page(0) { - Ok(bytes) => FileHeader::from_bytes(&bytes)?, - Err(_) if backend.is_new() => FileHeader::new(), - Err(e) => bail_coded!(ErrorCode::Stg010, e), - }; - - // Snapshot old B+tree leaves BEFORE writing new pages that may overlap them. - let old_leaves = |root: u64| -> Result>>> { - if root == 0 { - Ok(Vec::new()) + let m = self.meta; + let next_gen = m.next_generation()?; + + let mut backend = self.lock()?; + + // Snapshot the old trees (their leaves, and every node for freeing) and + // the old free list. Nothing here is written. + let mut freed: Vec = Vec::new(); + let mut old_leaves = Vec::with_capacity(4); + for root in m.index_roots() { + old_leaves.push(if root == 0 { + Vec::new() } else { - collect_leaf_pages(root, &*backend, &self.page_cache) - } - }; - let old_eavt = old_leaves(curr_header.eavt_root_page)?; - let old_aevt = old_leaves(curr_header.aevt_root_page)?; - let old_avet = old_leaves(curr_header.avet_root_page)?; - let old_vaet = old_leaves(curr_header.vaet_root_page)?; - - // Invalidate cached pages that will be overwritten (old index pages) - self.page_cache.invalidate_from(new_fact_start); - - // ── Step B: pack pending facts as new appended pages ──────────────────── - let (new_pages, new_fact_refs) = pack_facts(&pending_facts, new_fact_start)?; - for (i, page_data) in new_pages.iter().enumerate() { - let page_offset = u64::try_from(i).map_err(|_| err_coded!(ErrorCode::Stg023, i))?; - let page_id = new_fact_start - .checked_add(page_offset) - .ok_or_else(|| err_coded!(ErrorCode::Stg022))?; - backend.write_page(page_id, page_data)?; + collect_leaf_pages(root, &*backend, &self.page_cache, Some(&mut freed))? + }); } - let new_pages_len = u64::try_from(new_pages.len()) - .map_err(|_| err_coded!(ErrorCode::Int048, "new page count exceeds u64::MAX"))?; - let new_total_fact_pages = old_fact_page_count - .checked_add(new_pages_len) - .ok_or_else(|| err_coded!(ErrorCode::Int048, "fact page count overflow"))?; - - // Sync fact pages to disk before building indexes on top of them. - // Without this, a crash during index build could leave partially-flushed - // fact pages that the old header's index roots would try to traverse. - backend.sync()?; + let (old_free, old_chain) = if m.freelist_head != 0 { + freelist::read_chain(m.freelist_head, &*backend, &self.page_cache, m.page_count)? + } else { + (Vec::new(), Vec::new()) + }; + freed.extend(old_chain); - // ── Step C: build sorted index entries for pending facts ──────────────── + let mut alloc = PageAllocator::new(old_free, m.page_count, next_gen); + let refs = append_fact_pages(&pending_facts, &mut alloc, &mut *backend, &self.page_cache)?; let (pending_eavt, pending_aevt, pending_avet, pending_vaet) = - build_sorted_index_entries(&pending_facts, &new_fact_refs); - - // ── Step D: merge committed + pending entries, build new B+trees ───────── - let index_start = 1u64 - .checked_add(new_total_fact_pages) - .ok_or_else(|| err_coded!(ErrorCode::Stg017))?; + build_sorted_index_entries(&pending_facts, &refs); - // Copy untouched leaves, repack only leaves that receive pending entries (#315). - let (eavt_root, next1) = rebuild_btree_incremental( - old_eavt, + let mut old_leaves = old_leaves.into_iter(); + let eavt_root = rebuild_btree_incremental( + old_leaves.next().unwrap_or_default(), pending_eavt, &mut *backend, &self.page_cache, - index_start, + &mut alloc, )?; - let (aevt_root, next2) = rebuild_btree_incremental( - old_aevt, + let aevt_root = rebuild_btree_incremental( + old_leaves.next().unwrap_or_default(), pending_aevt, &mut *backend, &self.page_cache, - next1, + &mut alloc, )?; - let (avet_root, next3) = rebuild_btree_incremental( - old_avet, + let avet_root = rebuild_btree_incremental( + old_leaves.next().unwrap_or_default(), pending_avet, &mut *backend, &self.page_cache, - next2, + &mut alloc, )?; - let (vaet_root, next4) = rebuild_btree_incremental( - old_vaet, + let vaet_root = rebuild_btree_incremental( + old_leaves.next().unwrap_or_default(), pending_vaet, &mut *backend, &self.page_cache, - next3, + &mut alloc, )?; - // Sync index pages to disk before writing the header. - // The header update is the atomic commit point: once it's durable, - // recovery uses the new root pages. All data those roots reference - // must already be on stable storage. - backend.sync()?; + // New free list: what is left of the old one, plus everything the old + // meta referenced that the new one does not. + let mut new_free = alloc.take_unused_free(); + new_free.extend(freed); + let (freelist_head, _) = + freelist::write_chain(&new_free, &mut alloc, &mut *backend, &self.page_cache)?; - // CRC32 over ALL data pages (facts + indexes), excluding page 0 (header). - // This detects corruption in both fact pages and B+tree index pages. - // Fact pages 1..=old count are unchanged since the last save/load, so extend - // the cached CRC state instead of re-reading them (#315). Taking the cache - // means a failed save leaves None and the next save does a full pass. - let mut hasher = match self.fact_prefix_crc.take() { - Some((n, prefix)) if n == old_fact_page_count => { - let mut h = prefix; - hash_pages(&*backend, &mut h, new_fact_start, new_pages_len)?; - h - } - _ => { - let mut h = Hasher::new(); - hash_pages(&*backend, &mut h, 1, new_total_fact_pages)?; - h - } - }; - let new_prefix = hasher.clone(); - hash_pages( - &*backend, - &mut hasher, - index_start, - next4.saturating_sub(index_start), - )?; - let checksum = hasher.finalize(); + backend.sync()?; - // ── Step E: write header (last write = crash-safe boundary) ───────────── - let mut header = FileHeader::new(); // version=FORMAT_VERSION - header.page_count = next4; let pending_len = u64::try_from(pending_facts.len()).map_err(|_| err_coded!(ErrorCode::Stg024))?; - header.node_count = curr_header - .node_count - .checked_add(pending_len) - .ok_or_else(|| err_coded!(ErrorCode::Int048, "node_count overflow"))?; - header.last_checkpointed_tx_count = self.storage.current_tx_count(); - header.eavt_root_page = eavt_root; - header.aevt_root_page = aevt_root; - header.avet_root_page = avet_root; - header.vaet_root_page = vaet_root; - header.index_checksum = checksum; - header.fact_page_format = FACT_PAGE_FORMAT_PACKED; - header.fact_page_count = new_total_fact_pages; - header.header_checksum = compute_header_checksum(&header); - - let mut header_page = header.to_bytes(); - header_page.resize(PAGE_SIZE, 0); - backend.write_page(0, &header_page)?; + let new_meta = MetaPage { + generation: next_gen, + page_count: alloc.next_append(), + fact_count: m + .fact_count + .checked_add(pending_len) + .ok_or_else(|| err_coded!(ErrorCode::Int048, "fact_count overflow"))?, + last_checkpointed_tx_count: self.storage.current_tx_count(), + eavt_root, + aevt_root, + avet_root, + vaet_root, + freelist_head, + freelist_count: u64::try_from(new_free.len()) + .map_err(|_| err_coded!(ErrorCode::Int048, "free-list length"))?, + ..m + }; + backend.write_page(slot_page(next_gen), &new_meta.encode())?; backend.sync()?; drop(backend); - self.committed_fact_pages - .store(new_total_fact_pages, Ordering::SeqCst); - self.fact_prefix_crc = Some((new_total_fact_pages, new_prefix)); - self.last_checkpointed_tx_count = self.storage.current_tx_count(); self.dirty = false; - - // ── Step F: wire CommittedFactReader and CommittedIndexReader ──────────── - let loader: Arc = - Arc::new(CommittedFactLoaderImpl { - backend: self.backend.clone(), - backend_adapter: MutexStorageBackend(self.backend.clone()), - page_cache: self.page_cache.clone(), - committed_fact_pages: self.committed_fact_pages.clone(), - first_fact_page: 1, - }); - self.storage.set_committed_reader(loader); - - let index_reader: Arc = - Arc::new(OnDiskIndexReader::new( - self.backend.clone(), - self.page_cache.clone(), - eavt_root, - aevt_root, - avet_root, - vaet_root, - )); - self.storage.set_committed_index_reader(index_reader); - + self.activate(new_meta); // Clear pending — all data now on disk self.storage.post_checkpoint_clear(); - Ok(()) } @@ -658,11 +452,23 @@ impl PersistentFactStorage { &self.storage } - /// The `last_checkpointed_tx_count` recorded in the on-disk header. + /// The `last_checkpointed_tx_count` recorded in the active meta page. /// /// Used by WAL replay to skip entries already present in the main file. pub fn last_checkpointed_tx_count(&self) -> u64 { - self.last_checkpointed_tx_count + self.meta.last_checkpointed_tx_count + } + + /// The active meta page's generation. A WAL created now records it as its + /// base generation. + pub fn generation(&self) -> u64 { + self.meta.generation + } + + /// The active meta page (for tests). + #[cfg(test)] + pub(crate) fn meta(&self) -> MetaPage { + self.meta } /// Mark storage as dirty (needs saving) @@ -729,81 +535,130 @@ impl Drop for PersistentFactStorage { } } -/// Compute CRC32 checksum over a range of pages on the backend. -fn compute_page_checksum( +/// Exactly one meta slot is valid, at generation `g`. Fail with STG-033 if a +/// later commit `g + 1` completed and its meta was lost (spec §4.1.1 table). +fn check_single_valid( backend: &dyn StorageBackend, - first_page: u64, - num_pages: u64, -) -> Result { - let mut hasher = Hasher::new(); - hash_pages(backend, &mut hasher, first_page, num_pages)?; - Ok(hasher.finalize()) -} - -/// Feed pages `first_page..first_page + num_pages` into `hasher`. -fn hash_pages( - backend: &dyn StorageBackend, - hasher: &mut Hasher, - first_page: u64, - num_pages: u64, + m: MetaPage, + wal_base: Option, ) -> Result<()> { - for i in 0..num_pages { - let page_id = first_page - .checked_add(i) - .ok_or_else(|| err_coded!(ErrorCode::Stg021))?; - hasher.update(&backend.read_page(page_id)?); + let g = m.generation; + match wal_base { + // The WAL has existed since generation `b <= g` and is deleted only after + // a durable commit, so it holds every fact that is not in `g`. + Some(b) if b <= g => Ok(()), + Some(b) => bail_coded!(ErrorCode::Stg033, g, format!("WAL base generation {b}")), + None => { + // Without a WAL, look where `g + 1` could have written: `M_g`'s free + // list and the pages past `M_g.page_count`. + let next = m.next_generation()?; + let probe = PageCache::new(0); + probe.set_generation_bound(g); + let (free, _) = if m.freelist_head != 0 { + freelist::read_chain(m.freelist_head, backend, &probe, m.page_count)? + } else { + (Vec::new(), Vec::new()) + }; + let end = backend.page_count()?; + for id in free.into_iter().chain(m.page_count..end) { + let Ok(p) = backend.read_page(id) else { + continue; + }; + if page::verify(&p, id, u64::MAX).is_ok() && page::page_generation(&p)? == next { + bail_coded!( + ErrorCode::Stg033, + g, + format!("page {id} was written by generation {next}") + ); + } + } + Ok(()) + } } - Ok(()) } -/// Compute CRC32 checksum over header bytes 0-79 (header_checksum field zeroed). -pub fn compute_header_checksum(header: &FileHeader) -> u32 { - let mut bytes = header.to_bytes(); - // Zero out bytes 80–83 (the header_checksum field) before hashing. - // The header is exactly 84 bytes (guaranteed by FileHeader::to_bytes). - if let Some(b) = bytes.get_mut(80) { - *b = 0; - } - if let Some(b) = bytes.get_mut(81) { - *b = 0; - } - if let Some(b) = bytes.get_mut(82) { - *b = 0; - } - if let Some(b) = bytes.get_mut(83) { - *b = 0; +/// True if `page0` is a torn write of the empty generation-1 meta onto a new +/// file: a prefix of its bytes, then zeros, with page 1 (if present) all zero. +/// Such a file never committed anything, so it is safe to initialise again. +fn is_torn_initial_meta(backend: &dyn StorageBackend, page0: &[u8]) -> Result { + let expected = MetaPage::empty(1).encode(); + let written = page0 + .iter() + .rposition(|&b| b != 0) + .map_or(0, |i| i.saturating_add(1)); + if page0.get(..written) != expected.get(..written) { + return Ok(false); } - let mut hasher = Hasher::new(); - if let Some(slice) = bytes.get(..80) { - hasher.update(slice); + if backend.page_count()? > 1 && backend.read_page(1)?.iter().any(|&b| b != 0) { + return Ok(false); } - hasher.finalize() + Ok(true) } -/// Compute CRC32 checksum over raw header bytes 0-79 (bytes 80-83 zeroed). -fn compute_header_checksum_from_bytes(bytes: &[u8]) -> u32 { - let mut data = bytes.to_vec(); - if data.len() < 84 { - data.resize(84, 0); - } - // Zero out bytes 80–83 (the header_checksum field) before hashing. - if let Some(b) = data.get_mut(80) { - *b = 0; - } - if let Some(b) = data.get_mut(81) { - *b = 0; - } - if let Some(b) = data.get_mut(82) { - *b = 0; - } - if let Some(b) = data.get_mut(83) { - *b = 0; - } - let mut hasher = Hasher::new(); - if let Some(slice) = data.get(..80) { - hasher.update(slice); +/// Append packed pages for `facts` and return each fact's `FactRef`. +/// +/// Fact pages always append, so ascending page id stays insertion order. +fn append_fact_pages( + facts: &[Fact], + alloc: &mut PageAllocator, + backend: &mut dyn StorageBackend, + cache: &PageCache, +) -> Result> { + if facts.is_empty() { + return Ok(Vec::new()); + } + let start = alloc.next_append(); + let (pages, refs) = pack_facts(facts, start)?; + for (i, page) in pages.into_iter().enumerate() { + let id = alloc.alloc_append()?; + let expected = u64::try_from(i) + .ok() + .and_then(|i| start.checked_add(i)) + .ok_or_else(|| err_coded!(ErrorCode::Stg022))?; + if id != expected { + bail_coded!(ErrorCode::Int049, "fact pages must be contiguous appends"); + } + alloc.write(backend, cache, id, page)?; } - hasher.finalize() + Ok(refs) +} + +/// Bulk-build all four trees from `facts` and return their roots +/// (EAVT, AEVT, AVET, VAET). +fn build_all_trees( + facts: &[Fact], + refs: &[FactRef], + alloc: &mut PageAllocator, + backend: &mut dyn StorageBackend, + cache: &PageCache, +) -> Result<[u64; 4]> { + let (eavt, aevt, avet, vaet) = build_sorted_index_entries(facts, refs); + Ok([ + build_btree( + btree_entries(eavt.into_iter())?.into_iter(), + backend, + cache, + alloc, + )?, + build_btree( + btree_entries(aevt.into_iter())?.into_iter(), + backend, + cache, + alloc, + )?, + build_btree( + btree_entries(avet.into_iter())?.into_iter(), + backend, + cache, + alloc, + )?, + build_btree( + btree_entries(vaet.into_iter())?.into_iter(), + backend, + cache, + alloc, + )?, + ]) } /// Build sorted index entry vecs for a slice of facts and their corresponding FactRefs. @@ -855,93 +710,128 @@ fn build_sorted_index_entries( mod tests { use super::*; use crate::graph::types::Value; + use crate::storage::backend::FaultInjectingBackend; use crate::storage::backend::MemoryBackend; use crate::storage::btree_v6::stream_all_entries; - use std::io::Write; + use std::collections::BTreeSet; use uuid::Uuid; - /// All four on-disk indexes equal a from-scratch derivation from the fact pages, - /// and the stored checksum equals a full pass over pages 1..page_count. - fn assert_indexes_and_checksum_exact( - pfs: &PersistentFactStorage, - ) { - let backend = pfs.backend.lock().unwrap(); - let header = FileHeader::from_bytes(&backend.read_page(0).unwrap()).unwrap(); - let full = compute_page_checksum(&*backend, 1, header.page_count - 1).unwrap(); - assert_eq!(header.index_checksum, full, "stored checksum != full pass"); + fn entity(i: u128) -> Uuid { + Uuid::from_u128(i + 1) + } - let (facts, refs) = - crate::storage::packed_pages::read_all_with_refs(&*backend, 1, header.fact_page_count) - .unwrap(); - let (eavt, aevt, avet, vaet) = build_sorted_index_entries(&facts, &refs); - let cache = &pfs.page_cache; - let got_eavt: Vec<(EavtKey, FactRef)> = - stream_all_entries(header.eavt_root_page, &*backend, cache).unwrap(); - let got_aevt: Vec<(AevtKey, FactRef)> = - stream_all_entries(header.aevt_root_page, &*backend, cache).unwrap(); - let got_avet: Vec<(AvetKey, FactRef)> = - stream_all_entries(header.avet_root_page, &*backend, cache).unwrap(); - let got_vaet: Vec<(VaetKey, FactRef)> = - stream_all_entries(header.vaet_root_page, &*backend, cache).unwrap(); - assert!( - got_eavt.is_sorted_by(|a, b| a.0 <= b.0), - "EAVT not in key order" - ); - assert!( - got_aevt.is_sorted_by(|a, b| a.0 <= b.0), - "AEVT not in key order" - ); - assert!( - got_avet.is_sorted_by(|a, b| a.0 <= b.0), - "AVET not in key order" - ); + fn code(e: anyhow::Error) -> &'static str { + crate::error::MinigrafError::from(e).code() + } + + /// Page ids the meta references: tree nodes, fact pages, free-list chain pages. + fn reachable(meta: &MetaPage, backend: &dyn StorageBackend) -> BTreeSet { + let cache = PageCache::new(0); + let mut nodes = Vec::new(); + for root in meta.index_roots() { + if root != 0 { + collect_leaf_pages(root, backend, &cache, Some(&mut nodes)).unwrap(); + } + } + let mut set: BTreeSet = nodes.into_iter().collect(); + if meta.eavt_root != 0 { + let entries: Vec<(EavtKey, FactRef)> = + stream_all_entries(meta.eavt_root, backend, &cache).unwrap(); + set.extend(entries.iter().map(|(_, fr)| fr.page_id)); + } + if meta.freelist_head != 0 { + let (_, chain) = + freelist::read_chain(meta.freelist_head, backend, &cache, meta.page_count).unwrap(); + set.extend(chain); + } + set + } + + /// Spec §11 invariant: reachable pages and free ids are disjoint and together + /// cover `2..page_count` exactly; every reachable page verifies. + fn assert_space_accounted(meta: &MetaPage, backend: &dyn StorageBackend) { + let reach = reachable(meta, backend); + let free: Vec = if meta.freelist_head == 0 { + Vec::new() + } else { + freelist::read_chain( + meta.freelist_head, + backend, + &PageCache::new(0), + meta.page_count, + ) + .unwrap() + .0 + }; + assert_eq!(free.len() as u64, meta.freelist_count, "freelist_count"); + let free_set: BTreeSet = free.iter().copied().collect(); + assert_eq!(free_set.len(), free.len(), "duplicate free id"); assert!( - got_vaet.is_sorted_by(|a, b| a.0 <= b.0), - "VAET not in key order" + reach.is_disjoint(&free_set), + "a free page is still referenced" ); - // One transaction can write the same (entity, attribute) twice, giving equal - // v7 keys (#371); their relative order is unspecified, so compare as sets. - fn by_key_then_ref(mut v: Vec<(K, FactRef)>) -> Vec<(K, FactRef)> { - v.sort(); - v + let all: BTreeSet = (2..meta.page_count).collect(); + let union: BTreeSet = reach.union(&free_set).copied().collect(); + assert!(union == all, "pages leaked or out of range"); + for &id in &reach { + page::verify(&backend.read_page(id).unwrap(), id, meta.generation) + .expect("reachable page verifies"); } - let (eavt, aevt, avet, vaet) = ( - by_key_then_ref(eavt), - by_key_then_ref(aevt), - by_key_then_ref(avet), - by_key_then_ref(vaet), - ); - let (got_eavt, got_aevt, got_avet, got_vaet) = ( - by_key_then_ref(got_eavt), - by_key_then_ref(got_aevt), - by_key_then_ref(got_avet), - by_key_then_ref(got_vaet), - ); - assert!(got_eavt == eavt, "EAVT differs from full derivation"); - assert!(got_aevt == aevt, "AEVT differs from full derivation"); - assert!(got_avet == avet, "AVET differs from full derivation"); - assert!(got_vaet == vaet, "VAET differs from full derivation"); } - /// One transact of `n` facts: new and reused entities, strings and refs (VAET). + /// The four indexes equal a derivation from the facts EAVT references. + fn assert_indexes_exact(meta: &MetaPage, backend: &dyn StorageBackend) { + let cache = PageCache::new(0); + let eavt: Vec<(EavtKey, FactRef)> = + stream_all_entries(meta.eavt_root, backend, &cache).unwrap(); + let refs: Vec = eavt.iter().map(|(_, fr)| *fr).collect(); + let facts: Vec = refs + .iter() + .map(|fr| { + let p = cache.get_or_load(fr.page_id, backend).unwrap(); + crate::storage::packed_pages::read_slot(&p, fr.slot_index).unwrap() + }) + .collect(); + let (e, a, av, v) = build_sorted_index_entries(&facts, &refs); + fn sorted(mut v: Vec<(K, FactRef)>) -> Vec<(K, FactRef)> { + v.sort(); + v + } + let got_e: Vec<(EavtKey, FactRef)> = + stream_all_entries(meta.eavt_root, backend, &cache).unwrap(); + let got_a: Vec<(AevtKey, FactRef)> = + stream_all_entries(meta.aevt_root, backend, &cache).unwrap(); + let got_av: Vec<(AvetKey, FactRef)> = + stream_all_entries(meta.avet_root, backend, &cache).unwrap(); + let got_v: Vec<(VaetKey, FactRef)> = + stream_all_entries(meta.vaet_root, backend, &cache).unwrap(); + assert!(got_a.is_sorted_by(|x, y| x.0 <= y.0), "AEVT order"); + assert!(got_av.is_sorted_by(|x, y| x.0 <= y.0), "AVET order"); + assert!(got_v.is_sorted_by(|x, y| x.0 <= y.0), "VAET order"); + assert!(sorted(got_e) == sorted(e), "EAVT differs from derivation"); + assert!(sorted(got_a) == sorted(a), "AEVT differs from derivation"); + assert!(sorted(got_av) == sorted(av), "AVET differs from derivation"); + assert!(sorted(got_v) == sorted(v), "VAET differs from derivation"); + } + + /// One transact of `n` facts: new and reused entities, strings and refs. fn transact_mixed( pfs: &mut PersistentFactStorage, - entities: &mut Vec, + next_entity: &mut u128, n: usize, seed: u64, ) { let mut batch = Vec::new(); for i in 0..n { let k = seed.wrapping_mul(31).wrapping_add(i as u64); - let e = if entities.is_empty() || k % 3 == 0 { - let e = Uuid::new_v4(); - entities.push(e); - e + let e = if *next_entity == 0 || k % 3 == 0 { + *next_entity += 1; + entity(*next_entity) } else { - entities[(k as usize) % entities.len()] + entity(u128::from(k) % *next_entity + 1) }; let value = if k % 4 == 0 { - Value::Ref(entities[(k as usize / 4) % entities.len()]) + Value::Ref(entity(u128::from(k / 4) % *next_entity + 1)) } else { Value::String(format!("v{k}")) }; @@ -951,110 +841,181 @@ mod tests { pfs.mark_dirty(); } + fn put_batch( + pfs: &mut PersistentFactStorage, + ids: std::ops::Range, + ) { + let batch = ids + .map(|i| (entity(i), ":test/n".to_string(), Value::Integer(i as i64))) + .collect(); + pfs.storage().transact(batch, None).unwrap(); + pfs.mark_dirty(); + } + + fn count_n(pfs: &PersistentFactStorage) -> usize { + pfs.storage() + .get_facts_by_attribute(&":test/n".to_string()) + .unwrap() + .len() + } + + /// Records the id of every page written. + #[derive(Clone)] + struct RecordingBackend { + inner: MemoryBackend, + written: Arc>>, + } + + impl StorageBackend for RecordingBackend { + fn write_page(&mut self, page_id: u64, data: &[u8]) -> Result<()> { + self.written.lock().unwrap().push(page_id); + self.inner.write_page(page_id, data) + } + fn read_page(&self, page_id: u64) -> Result> { + self.inner.read_page(page_id) + } + fn sync(&mut self) -> Result<()> { + Ok(()) + } + fn page_count(&self) -> Result { + self.inner.page_count() + } + fn close(&mut self) -> Result<()> { + Ok(()) + } + fn backend_name(&self) -> &'static str { + "recording" + } + } + + // ── save ──────────────────────────────────────────────────────────────── + + /// Many saves: indexes stay exact, space is fully accounted for, and no + /// save writes a page the previous meta references (spec §8.1). #[test] - fn test_incremental_saves_keep_indexes_and_checksum_exact() { - let mut pfs = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); - let mut entities = Vec::new(); + fn saves_never_write_committed_pages_and_account_for_all_space() { + 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..25u64 { + let before = pfs.meta(); + let committed = reachable(&before, &mem); + log.lock().unwrap().clear(); let n = 1 + ((round * 37) % 60) as usize; - transact_mixed(&mut pfs, &mut entities, n, round); + transact_mixed(&mut pfs, &mut next_entity, n, round); pfs.save().unwrap(); - assert!(pfs.fact_prefix_crc.is_some(), "prefix cached after save"); - assert_indexes_and_checksum_exact(&pfs); + let after = pfs.meta(); + assert_eq!(after.generation, before.generation + 1); + for &id in log.lock().unwrap().iter() { + assert!(!committed.contains(&id), "save overwrote a committed page"); + assert_ne!(id, slot_page(before.generation), "active meta overwritten"); + } + assert_space_accounted(&after, &mem); + assert_indexes_exact(&after, &mem); } + // Freed tree pages are reused: the file does not grow by a full copy + // of the trees per save. + let m = pfs.meta(); + assert!(m.freelist_count > 0, "old tree pages are on the free list"); } #[test] - fn test_reopen_after_incremental_saves_takes_no_rebuild() { - use crate::storage::backend::FileBackend; - use tempfile::NamedTempFile; - let tmp = NamedTempFile::new().unwrap(); - let path = tmp.path().to_str().unwrap().to_string(); - let mut entities = Vec::new(); - { - let mut pfs = - PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - for round in 0..10u64 { - transact_mixed(&mut pfs, &mut entities, 40, round); - pfs.save().unwrap(); + fn generations_alternate_between_the_two_meta_pages() { + let mem = MemoryBackend::new(); + let mut pfs = PersistentFactStorage::new(mem.clone(), 16).unwrap(); + assert_eq!(pfs.generation(), 1); + for g in 2..6u64 { + put_batch(&mut pfs, u128::from(g) * 10..u128::from(g) * 10 + 3); + pfs.save().unwrap(); + let page = mem.read_page(slot_page(g)).unwrap(); + match MetaPage::decode(&page) { + SlotState::Valid(m) => assert_eq!(m.generation, g), + _ => panic!("slot for the new generation must be valid"), + } + let other = mem.read_page(slot_page(g - 1)).unwrap(); + match MetaPage::decode(&other) { + SlotState::Valid(m) => assert_eq!(m.generation, g - 1), + _ => panic!("the previous generation stays valid"), } } - let mut pfs = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - // Set only when the full checksum matched on load, i.e. no rebuild. - assert!( - pfs.fact_prefix_crc.is_some(), - "full checksum must match on reopen" - ); - transact_mixed(&mut pfs, &mut entities, 40, 99); - pfs.save().unwrap(); - assert_indexes_and_checksum_exact(&pfs); } #[test] - fn test_prefix_cache_page_count_mismatch_falls_back() { - let mut pfs = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); - let mut entities = Vec::new(); - transact_mixed(&mut pfs, &mut entities, 50, 1); - pfs.save().unwrap(); - pfs.fact_prefix_crc = Some((999, Hasher::new())); - transact_mixed(&mut pfs, &mut entities, 50, 2); - pfs.save().unwrap(); - assert_indexes_and_checksum_exact(&pfs); + fn new_file_gets_an_empty_generation_1_meta() { + let mem = MemoryBackend::new(); + let pfs = PersistentFactStorage::new(mem.clone(), 16).unwrap(); + assert_eq!(pfs.storage().fact_count(), 0); + assert_eq!(pfs.last_checkpointed_tx_count(), 0); + drop(pfs); + assert_eq!(mem.page_count().unwrap(), 2); + match MetaPage::decode(&mem.read_page(0).unwrap()) { + SlotState::Valid(m) => assert!(m == MetaPage::empty(1), "empty gen-1 meta"), + _ => panic!("page 0 must hold the initial meta"), + } + assert!(matches!( + MetaPage::decode(&mem.read_page(1).unwrap()), + SlotState::Empty + )); + // Reopening an untouched new file is fine (g == 1, slot B empty, no WAL). + let pfs = PersistentFactStorage::new(mem, 16).unwrap(); + assert_eq!(pfs.generation(), 1); + } + + #[test] + fn torn_initial_meta_is_initialised_again() { + for n in [1usize, 16, 40, 2000] { + let mut mem = MemoryBackend::new(); + let mut page = vec![0u8; PAGE_SIZE]; + page[..n].copy_from_slice(&MetaPage::empty(1).encode()[..n]); + mem.write_page(0, &page).unwrap(); + let pfs = PersistentFactStorage::new(mem, 16).expect("re-init"); + assert_eq!(pfs.generation(), 1); + } + // Foreign bytes are never overwritten. + let mut mem = MemoryBackend::new(); + mem.write_page(0, &vec![0xAA; PAGE_SIZE]).unwrap(); + assert_eq!( + code(PersistentFactStorage::new(mem.clone(), 16).err().unwrap()), + "STG-002" + ); + assert!(mem.read_page(0).unwrap().iter().all(|&b| b == 0xAA)); } #[test] - fn test_prefix_cache_absent_after_rebuild_on_open() { + fn file_backed_reopen_sees_every_save() { use crate::storage::backend::FileBackend; - use tempfile::NamedTempFile; - let tmp = NamedTempFile::new().unwrap(); - let path = tmp.path().to_str().unwrap().to_string(); - let mut entities = Vec::new(); - { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("db.graph"); + let mut next_entity = 0; + let last = { let mut pfs = - PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - for round in 0..3u64 { - transact_mixed(&mut pfs, &mut entities, 30, round); + PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 16).unwrap(); + for round in 0..5 { + transact_mixed(&mut pfs, &mut next_entity, 40, round); pfs.save().unwrap(); } - } - // Corrupt index_checksum (re-sealing the header) to force the rebuild path. - { - let mut backend = FileBackend::open(&path).unwrap(); - let mut page = backend.read_page(0).unwrap(); - page[64] ^= 0xFF; - let cs = compute_header_checksum_from_bytes(&page); - page[80..84].copy_from_slice(&cs.to_le_bytes()); - backend.write_page(0, &page).unwrap(); - backend.sync().unwrap(); - } - let mut pfs = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - assert!( - pfs.fact_prefix_crc.is_none(), - "no prefix after rebuild-on-open" - ); - transact_mixed(&mut pfs, &mut entities, 30, 7); - pfs.save().unwrap(); - assert_indexes_and_checksum_exact(&pfs); + pfs.meta() + }; + let pfs = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 16).unwrap(); + assert!(pfs.meta() == last, "reopen picks the last committed meta"); + assert_eq!(pfs.storage().fact_count(), 200); + let backend = pfs.lock().unwrap(); + assert_space_accounted(&last, &*backend); } #[test] fn test_page_cache_capacity_reflects_constructed_value() { let zero_cap = PersistentFactStorage::new(MemoryBackend::new(), 0).unwrap(); assert_eq!(zero_cap.page_cache_capacity(), 0); - let nonzero_cap = PersistentFactStorage::new(MemoryBackend::new(), 64).unwrap(); assert_eq!(nonzero_cap.page_cache_capacity(), 64); } - #[test] - fn test_persistent_fact_storage_new() { - let backend = MemoryBackend::new(); - let storage = PersistentFactStorage::new(backend, 256).unwrap(); - - // Should be able to create new storage - assert_eq!(storage.storage().fact_count(), 0); - } - #[test] fn same_tx_multi_value_visible_through_entity_and_attribute_lookups_before_save() { let pfs = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); @@ -1079,1077 +1040,379 @@ mod tests { } #[test] - fn test_persistent_fact_storage_save_load() { - // Create separate scopes to test persistence - let alice = Uuid::new_v4(); + fn save_and_reopen_preserve_facts_tx_id_and_tx_count() { + let mut pfs = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); + let alice = entity(1); + let bob = entity(2); + pfs.storage() + .transact( + vec![ + ( + alice, + ":name".to_string(), + Value::String("Alice".to_string()), + ), + (alice, ":friend".to_string(), Value::Ref(bob)), + ], + None, + ) + .unwrap(); + pfs.storage().transact(vec![], None).unwrap(); // empty tx still counts + let tx_id = pfs.storage().get_all_facts().unwrap()[0].tx_id; + pfs.mark_dirty(); + pfs.save().unwrap(); + assert_eq!(pfs.last_checkpointed_tx_count(), 2); - // First session: create and save facts - { - let backend = MemoryBackend::new(); - let mut storage = PersistentFactStorage::new(backend, 256).unwrap(); - - storage - .storage() - .transact( - vec![ - ( - alice, - ":person/name".to_string(), - Value::String("Alice".to_string()), - ), - (alice, ":person/age".to_string(), Value::Integer(30)), - ], - None, - ) - .unwrap(); - - storage.mark_dirty(); - storage.save().unwrap(); - - // Verify facts are persisted - assert_eq!(storage.storage().fact_count(), 2); - } - - // Note: In a real scenario, we'd reopen the same file. - // MemoryBackend doesn't persist across instances, so this test - // mainly validates the save/load mechanism. - } - - #[test] - fn test_persistent_fact_storage_auto_save() { - let backend = MemoryBackend::new(); - - let alice = Uuid::new_v4(); - - // Create storage in a scope so it drops - { - let mut storage = PersistentFactStorage::new(backend, 256).unwrap(); - storage - .storage() - .transact( - vec![( - alice, - ":person/name".to_string(), - Value::String("Alice".to_string()), - )], - None, - ) - .unwrap(); - storage.mark_dirty(); - // Drop happens here, should auto-save - } - - // Load into new storage - backend is consumed, need to create a new test - // This test verifies the pattern, actual persistence is tested above - } - - #[test] - fn test_load_preserves_original_tx_id() { - let mut pfs = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); - - let alice = Uuid::new_v4(); - pfs.storage() - .transact( - vec![( - alice, - ":person/name".to_string(), - Value::String("Alice".to_string()), - )], - None, - ) - .unwrap(); - - let original_tx_id = pfs.storage().get_all_facts().unwrap()[0].tx_id; - - pfs.mark_dirty(); - pfs.save().unwrap(); - - // Reload from the same backend - let backend = pfs.into_backend().unwrap(); - let pfs2 = PersistentFactStorage::new(backend, 256).unwrap(); - let loaded_tx_id = pfs2.storage().get_all_facts().unwrap()[0].tx_id; - - assert_eq!( - original_tx_id, loaded_tx_id, - "tx_id must survive save/load round-trip" - ); - } - - #[test] - fn test_save_writes_v4_header() { - use crate::storage::FORMAT_VERSION; - - let backend = MemoryBackend::new(); - let mut pfs = PersistentFactStorage::new(backend, 256).unwrap(); - let alice = Uuid::new_v4(); - pfs.storage() - .transact( - vec![( - alice, - ":name".to_string(), - crate::graph::types::Value::String("Alice".to_string()), - )], - None, - ) - .unwrap(); - pfs.mark_dirty(); - pfs.save().unwrap(); - - // Read back the header and verify version and last_checkpointed_tx_count - let backend = pfs.into_backend().unwrap(); - let header_page = backend.read_page(0).unwrap(); - let header = crate::storage::FileHeader::from_bytes(&header_page).unwrap(); - assert_eq!(header.version, FORMAT_VERSION); - assert_eq!(header.last_checkpointed_tx_count, 1); // one transact call - } - - #[test] - fn test_last_checkpointed_tx_count_getter() { - let backend = MemoryBackend::new(); - let pfs = PersistentFactStorage::new(backend, 256).unwrap(); - // Fresh database: no checkpoint yet - assert_eq!(pfs.last_checkpointed_tx_count(), 0); - } + let pfs2 = PersistentFactStorage::new(pfs.into_backend().unwrap(), 256).unwrap(); + assert_eq!(pfs2.last_checkpointed_tx_count(), 2); + assert_eq!(pfs2.storage().get_all_facts().unwrap()[0].tx_id, tx_id); + let facts = pfs2.storage().get_facts_by_entity(&alice).unwrap(); + assert_eq!(facts.len(), 2, "EAVT resolves both facts after reopen"); + assert!(facts.iter().any(|f| matches!(f.value, Value::Ref(_)))); + } #[test] - fn test_indexes_survive_save_load_roundtrip() { - use crate::graph::types::Value; - use crate::storage::backend::FileBackend; - use tempfile::NamedTempFile; - use uuid::Uuid; - - let tmp = NamedTempFile::new().unwrap(); - let path = tmp.path().to_str().unwrap().to_string(); - let alice = Uuid::new_v4(); - let bob = Uuid::new_v4(); - - // Save phase - { - let mut pfs = - PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - pfs.storage() - .transact( - vec![ - ( - alice, - ":name".to_string(), - Value::String("Alice".to_string()), - ), - (alice, ":friend".to_string(), Value::Ref(bob)), - ], - None, - ) - .unwrap(); - pfs.dirty = true; + fn stream_all_returns_committed_facts_in_insertion_order() { + let mut pfs = PersistentFactStorage::new(MemoryBackend::new(), 16).unwrap(); + for b in 0..4u128 { + put_batch(&mut pfs, b * 50..(b + 1) * 50); pfs.save().unwrap(); } - - // Load phase — indexes must be accessible via on-disk B+tree - { - let pfs = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - // v6: indexes live on disk via CommittedIndexReader, not in pending RAM - let alice_facts = pfs.storage().get_facts_by_entity(&alice).unwrap(); - assert_eq!( - alice_facts.len(), - 2, - "EAVT must resolve 2 entries after reload" - ); - // Check that Ref-valued fact is accessible - let ref_facts: Vec<_> = alice_facts - .iter() - .filter(|f| matches!(&f.value, crate::graph::types::Value::Ref(_))) - .collect(); - assert_eq!( - ref_facts.len(), - 1, - "Ref fact must be accessible after reload" - ); - } + let all = pfs.storage().get_all_facts().unwrap(); + let ns: Vec = all + .iter() + .map(|f| match f.value { + Value::Integer(n) => n, + _ => -1, + }) + .collect(); + assert_eq!(ns, (0..200).collect::>()); } #[test] - fn test_sync_check_detects_mismatch_and_rebuilds() { - use crate::graph::types::Value; - use crate::storage::StorageBackend; - use crate::storage::backend::FileBackend; - use tempfile::NamedTempFile; - use uuid::Uuid; - - let tmp = NamedTempFile::new().unwrap(); - let path = tmp.path().to_str().unwrap().to_string(); - let alice = Uuid::new_v4(); - - // Write a database with 1 fact - { - let mut pfs = - PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - pfs.storage() - .transact( - vec![( - alice, - ":name".to_string(), - Value::String("Alice".to_string()), - )], - None, - ) - .unwrap(); - pfs.dirty = true; - pfs.save().unwrap(); - } - - // Corrupt the index_checksum (bytes 64..68 of page 0), then recompute header_checksum - { - let mut backend = FileBackend::open(&path).unwrap(); - let mut page = backend.read_page(0).unwrap(); - page[64] ^= 0xFF; - let new_header_checksum = compute_header_checksum_from_bytes(&page); - page[80] = (new_header_checksum & 0xFF) as u8; - page[81] = ((new_header_checksum >> 8) & 0xFF) as u8; - page[82] = ((new_header_checksum >> 16) & 0xFF) as u8; - page[83] = ((new_header_checksum >> 24) & 0xFF) as u8; - backend.write_page(0, &page).unwrap(); - backend.sync().unwrap(); - } - - // Re-open — new() should detect mismatch, rebuild, and succeed - { - let pfs = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - // v6: after rebuild, indexes are on disk; verify fact accessibility - let alice_facts = pfs.storage().get_facts_by_entity(&alice).unwrap(); - assert_eq!( - alice_facts.len(), - 1, - "After rebuild, fact must be accessible via index" - ); - } + fn save_with_poisoned_backend_mutex_returns_stg_016() { + let mut pfs = PersistentFactStorage::new(MemoryBackend::new(), 16).unwrap(); + put_batch(&mut pfs, 0..1); + let backend = pfs.backend.clone(); + let handle = std::thread::spawn(move || { + let _guard = backend.lock().unwrap(); + panic!("deliberate poison for STG-016 regression test"); + }); + let _ = handle.join(); + let err = pfs.save().expect_err("poisoned mutex must fail"); + assert_eq!(code(err), "STG-016"); + pfs.dirty = false; } - /// Regression test for #370: the rebuild-on-load path must derive `FactRef`s from the - /// on-disk fact-page layout, not by re-packing all facts as a single batch. Each - /// `save()` starts a fresh page, so a file written by several checkpoints has partially - /// filled pages that a contiguous re-pack would not reproduce. - #[test] - fn test_rebuild_after_multiple_checkpoints_keeps_entity_lookups() { - use crate::graph::types::Value; - use crate::storage::StorageBackend; - use crate::storage::backend::FileBackend; - use tempfile::NamedTempFile; - use uuid::Uuid; - - let tmp = NamedTempFile::new().unwrap(); - let path = tmp.path().to_str().unwrap().to_string(); - let entities: Vec = (0..5).map(|_| Uuid::new_v4()).collect(); - - // One checkpoint per entity: five fact batches, each on its own partial page. - { - let mut pfs = - PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - for (i, e) in entities.iter().enumerate() { - pfs.storage() - .transact( - vec![(*e, ":name".to_string(), Value::String(format!("n{i}")))], - None, - ) - .unwrap(); - pfs.dirty = true; - pfs.save().unwrap(); - } - } - - // Corrupt index_checksum (and re-seal the header) to force the rebuild path. - { - let mut backend = FileBackend::open(&path).unwrap(); - let mut page = backend.read_page(0).unwrap(); - page[64] ^= 0xFF; - let cs = compute_header_checksum_from_bytes(&page); - page[80..84].copy_from_slice(&cs.to_le_bytes()); - backend.write_page(0, &page).unwrap(); - backend.sync().unwrap(); - } + // ── meta selection (spec §4.1.1) ──────────────────────────────────────── - let pfs = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - for e in &entities { - let facts = pfs.storage().get_facts_by_entity(e).unwrap(); - assert_eq!( - facts.len(), - 1, - "entity lookup must survive index rebuild after multiple checkpoints" - ); - assert_eq!(facts[0].entity, *e, "lookup returned a different entity"); - } + /// A store with generations 1..=3 committed (gen 3 in page 0, gen 2 in page 1). + fn three_generations() -> MemoryBackend { + let mem = MemoryBackend::new(); + let mut pfs = PersistentFactStorage::new(mem.clone(), 16).unwrap(); + put_batch(&mut pfs, 0..20); + pfs.save().unwrap(); + put_batch(&mut pfs, 20..40); + pfs.save().unwrap(); + assert_eq!(pfs.generation(), 3); + mem } - #[test] - fn test_compute_index_checksum_stable() { - use crate::graph::types::{Fact, VALID_TIME_FOREVER, Value}; - use uuid::Uuid; - - let e = Uuid::new_v4(); - let facts = vec![ - Fact::with_valid_time( - e, - ":a".to_string(), - Value::Integer(1), - 100, - 2, - 0, - VALID_TIME_FOREVER, - ), - Fact::with_valid_time( - e, - ":b".to_string(), - Value::Integer(2), - 200, - 1, - 0, - VALID_TIME_FOREVER, - ), - ]; - let c1 = compute_index_checksum(&facts); - // Reversed order — same checksum (deterministic sort applied inside) - let facts_reversed = vec![facts[1].clone(), facts[0].clone()]; - let c2 = compute_index_checksum(&facts_reversed); - assert_eq!(c1, c2, "Checksum must be order-independent"); + fn damage(mem: &mut MemoryBackend, page_id: u64) { + let mut p = mem.read_page(page_id).unwrap(); + p[30] ^= 0xFF; + mem.write_page(page_id, &p).unwrap(); } - #[test] - fn test_save_writes_packed_pages() { - use crate::storage::backend::FileBackend; - use tempfile::NamedTempFile; - - let tmp = NamedTempFile::new().unwrap(); - let path = tmp.path().to_str().unwrap().to_string(); - let alice = Uuid::new_v4(); - let bob = Uuid::new_v4(); - - { - let mut pfs = - PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - let mut tuples = Vec::new(); - for i in 0u64..50 { - tuples.push((alice, format!(":attr{}", i), Value::Integer(i as i64))); - } - tuples.push((alice, ":friend".to_string(), Value::Ref(bob))); - pfs.storage().transact(tuples, None).unwrap(); - pfs.mark_dirty(); - pfs.save().unwrap(); - } - - // Verify: header says current version, fact_page_format = PACKED - { - let backend = FileBackend::open(&path).unwrap(); - let header_bytes = backend.read_page(0).unwrap(); - let header = crate::storage::FileHeader::from_bytes(&header_bytes).unwrap(); - assert_eq!(header.version, FORMAT_VERSION); - assert_eq!( - header.fact_page_format, - crate::storage::FACT_PAGE_FORMAT_PACKED - ); - // 51 facts @ ~25/page = ~3 pages (far fewer than 51) - let fact_page_count = header.eavt_root_page.saturating_sub(1); - assert!( - fact_page_count <= 5, - "got {} fact pages (expected <=5)", - fact_page_count - ); - } + fn open_mem( + mem: &MemoryBackend, + wal: Option, + ) -> Result> { + PersistentFactStorage::open(mem.clone(), 16, wal) } - #[test] - fn test_save_v5_checksum_stored() { - use crate::storage::backend::FileBackend; - use tempfile::NamedTempFile; - - let tmp = NamedTempFile::new().unwrap(); - let path = tmp.path().to_str().unwrap().to_string(); - let alice = Uuid::new_v4(); - - { - let mut pfs = - PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - pfs.storage() - .transact( - vec![( - alice, - ":name".to_string(), - Value::String("Alice".to_string()), - )], - None, - ) - .unwrap(); - pfs.mark_dirty(); - pfs.save().unwrap(); - } - - { - let backend = FileBackend::open(&path).unwrap(); - let header_bytes = backend.read_page(0).unwrap(); - let header = crate::storage::FileHeader::from_bytes(&header_bytes).unwrap(); - // Checksum should be non-zero for a non-empty DB - assert_ne!(header.index_checksum, 0, "checksum must be set"); - } + fn snapshot(mem: &MemoryBackend) -> Vec> { + (0..mem.page_count().unwrap()) + .map(|i| mem.read_page(i).unwrap_or_default()) + .collect() } #[test] - fn test_v5_load_fast_path_indexes_loaded() { - use crate::storage::backend::FileBackend; - use tempfile::NamedTempFile; - - let tmp = NamedTempFile::new().unwrap(); - let path = tmp.path().to_str().unwrap().to_string(); - let alice = Uuid::new_v4(); - - // Save in v5 format - { - let mut pfs = - PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - pfs.storage() - .transact( - vec![( - alice, - ":name".to_string(), - Value::String("Alice".to_string()), - )], - None, - ) - .unwrap(); - pfs.mark_dirty(); - pfs.save().unwrap(); - } - - // Reload — CommittedFactReader should be wired, fact accessible - { - let pfs = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - assert_eq!(pfs.storage().fact_count(), 1); - // Query by entity should work via index - let facts = pfs.storage().get_facts_by_entity(&alice).unwrap(); - assert_eq!(facts.len(), 1); - assert_eq!(facts[0].entity, alice); - } + fn both_valid_opens_the_higher_generation() { + let mem = three_generations(); + let pfs = open_mem(&mem, None).unwrap(); + assert_eq!(pfs.generation(), 3); + assert_eq!(count_n(&pfs), 40); } - // ── v6 on-disk B+tree tests ───────────────────────────────────────────── - #[test] - fn test_save_writes_v6_header() { - let backend = MemoryBackend::new(); - let mut storage = PersistentFactStorage::new(backend, 256).unwrap(); - storage - .storage() - .transact( - vec![( - Uuid::new_v4(), - ":name".to_string(), - Value::String("x".to_string()), - )], - None, - ) - .unwrap(); - storage.mark_dirty(); - storage.save().unwrap(); - - let backend = storage.into_backend().unwrap(); - let header_page = backend.read_page(0).unwrap(); - let header = crate::storage::FileHeader::from_bytes(&header_page).unwrap(); - assert_eq!( - header.version, FORMAT_VERSION, - "save() must write current-version header" - ); - assert_eq!(header.to_bytes().len(), 84, "header must be 84 bytes"); - assert!(header.fact_page_count > 0, "fact_page_count must be set"); - assert!( - header.eavt_root_page > 0, - "eavt_root must be set after save" - ); + fn torn_newest_with_wal_base_g_opens_at_g() { + let mut mem = three_generations(); + damage(&mut mem, slot_page(3)); + let pfs = open_mem(&mem, Some(2)).unwrap(); + assert_eq!(pfs.generation(), 2); + assert_eq!(count_n(&pfs), 20, "gen 2 holds the first batch only"); + // A WAL older than g holds every later fact too. + assert_eq!(open_mem(&mem, Some(1)).unwrap().generation(), 2); } #[test] - fn v7_header_forces_rebuild_and_upgrades_to_v8() { - use crate::storage::FileHeader; - let e = Uuid::from_u128(7); - let mut backend = { - let mut s = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); - s.storage() - .transact(vec![(e, ":n".to_string(), Value::Integer(1))], None) - .unwrap(); - s.mark_dirty(); - s.save().unwrap(); - s.into_backend().unwrap() - }; - // Downgrade the header to v7 (keys on disk are now v8-shaped, which is - // fine: the rebuild never reads them). - let mut h = FileHeader::from_bytes(&backend.read_page(0).unwrap()).unwrap(); - h.version = 7; - h.header_checksum = compute_header_checksum(&h); - let mut page = h.to_bytes(); - page.resize(PAGE_SIZE, 0); - backend.write_page(0, &page).unwrap(); - - let s = PersistentFactStorage::new(backend, 256).unwrap(); - assert_eq!(s.storage().get_facts_by_entity(&e).unwrap().len(), 1); - let b = s.into_backend().unwrap(); - let h2 = FileHeader::from_bytes(&b.read_page(0).unwrap()).unwrap(); - assert_eq!(h2.version, 8, "v7 file must be upgraded to v8 on open"); - } - - /// #371/#287 review finding: empty transactions (`(transact [])`, - /// `(retract [])`) still allocate a tx_count without producing any facts - /// (see `FactStorage::transact` — `fetch_add` happens unconditionally). - /// The v7->v8 rebuild path must not compute the restored tx_counter as - /// `max(fact.tx_count)` alone, or trailing empty transactions before the - /// last checkpoint would be forgotten, rewinding the counter and letting - /// new transactions reuse tx_counts that `:as-of N` already served facts - /// for. - #[test] - fn v7_migration_does_not_rewind_tx_counter_past_empty_transactions() { - use crate::storage::FileHeader; - let e = Uuid::from_u128(70); - let mut backend = { - let mut s = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); - s.storage() - .transact(vec![(e, ":n".to_string(), Value::Integer(1))], None) - .unwrap(); - // Empty transactions still allocate tx_count without producing facts. - s.storage().transact(vec![], None).unwrap(); - s.storage().transact(vec![], None).unwrap(); - s.mark_dirty(); - s.save().unwrap(); - s.into_backend().unwrap() - }; - let pre_migration_last_checkpointed = { - let h = FileHeader::from_bytes(&backend.read_page(0).unwrap()).unwrap(); - h.last_checkpointed_tx_count - }; - assert_eq!( - pre_migration_last_checkpointed, 3, - "one fact-bearing transact plus two empty transacts" - ); - - // Downgrade the header to v7 (keys on disk are now v8-shaped, which is - // fine: the rebuild never reads them). - let mut h = FileHeader::from_bytes(&backend.read_page(0).unwrap()).unwrap(); - h.version = 7; - h.header_checksum = compute_header_checksum(&h); - let mut page = h.to_bytes(); - page.resize(PAGE_SIZE, 0); - backend.write_page(0, &page).unwrap(); - - let s = PersistentFactStorage::new(backend, 256).unwrap(); + fn wal_newer_than_the_valid_meta_is_stg_033() { + let mut mem = three_generations(); + damage(&mut mem, slot_page(3)); + let before = snapshot(&mem); + assert_eq!(code(open_mem(&mem, Some(3)).err().unwrap()), "STG-033"); assert!( - s.storage().current_tx_count() >= pre_migration_last_checkpointed, - "tx_counter must not rewind below the pre-migration last_checkpointed_tx_count" - ); - - let b = s.into_backend().unwrap(); - let h2 = FileHeader::from_bytes(&b.read_page(0).unwrap()).unwrap(); - assert!( - h2.last_checkpointed_tx_count >= pre_migration_last_checkpointed, - "v8 header's last_checkpointed_tx_count must not decrease across migration" + snapshot(&mem) == before, + "a failed open must not modify the file" ); } #[test] - fn test_load_v6_wires_committed_index_reader() { - let alice = Uuid::new_v4(); - let backend = { - let backend = MemoryBackend::new(); - let mut s = PersistentFactStorage::new(backend, 256).unwrap(); - s.storage() - .transact( - vec![( - alice, - ":name".to_string(), - Value::String("Alice".to_string()), - )], - None, - ) - .unwrap(); - s.mark_dirty(); - s.save().unwrap(); - s.into_backend().unwrap() + fn no_wal_with_next_generation_pages_is_stg_033() { + // Pages of gen 3 exist past gen 2's page_count. + let mut mem = three_generations(); + damage(&mut mem, slot_page(3)); + assert_eq!(code(open_mem(&mem, None).err().unwrap()), "STG-033"); + + // A gen-4 page on gen 3's free list, and nothing past its page_count: + // keep only gen 3's extent of the file and drop gen 4's meta. + let mem = three_generations(); + let m3 = match MetaPage::decode(&mem.read_page(slot_page(3)).unwrap()) { + SlotState::Valid(m) => m, + _ => panic!("gen 3 valid"), }; - - let s2 = PersistentFactStorage::new(backend, 256).unwrap(); - let facts = s2.storage().get_facts_by_entity(&alice).unwrap(); - assert_eq!( - facts.len(), - 1, - "committed fact must be visible after reopen" - ); - } - - #[test] - fn test_save_twice_merges_committed_and_pending() { - let backend = MemoryBackend::new(); - let mut storage = PersistentFactStorage::new(backend, 256).unwrap(); - let e1 = Uuid::new_v4(); - let e2 = Uuid::new_v4(); - - // First checkpoint (e1 committed) - storage - .storage() - .transact( - vec![(e1, ":name".to_string(), Value::String("Alice".to_string()))], - None, - ) - .unwrap(); - storage.mark_dirty(); - storage.save().unwrap(); - - // Second checkpoint (e2 pending → committed) - storage - .storage() - .transact( - vec![(e2, ":name".to_string(), Value::String("Bob".to_string()))], - None, + let cache = PageCache::new(0); + let (free, _) = + freelist::read_chain(m3.freelist_head, &mem, &cache, m3.page_count).unwrap(); + let target = *free.first().expect("gen 3 has free pages"); + let mut trimmed = MemoryBackend::new(); + for id in 0..m3.page_count { + trimmed.write_page(id, &mem.read_page(id).unwrap()).unwrap(); + } + // Slot of gen 4 (page 1) is damaged: it held gen 2, now rotted. + damage(&mut trimmed, slot_page(4)); + // No evidence yet: opens at gen 3. + assert_eq!(open_mem(&trimmed, None).unwrap().generation(), 3); + let alloc = PageAllocator::new(Vec::new(), 0, 4); + alloc + .write( + &mut trimmed, + &cache, + target, + page::new_page(page::PAGE_TYPE_LEAF, 0), ) .unwrap(); - storage.mark_dirty(); - storage.save().unwrap(); - - let backend = storage.into_backend().unwrap(); - let s2 = PersistentFactStorage::new(backend, 256).unwrap(); - let e1_facts = s2.storage().get_facts_by_entity(&e1).unwrap(); - let e2_facts = s2.storage().get_facts_by_entity(&e2).unwrap(); - assert_eq!( - e1_facts.len(), - 1, - "e1 from first checkpoint must survive second checkpoint" - ); - assert_eq!( - e2_facts.len(), - 1, - "e2 from second checkpoint must be visible" - ); + assert_eq!(code(open_mem(&trimmed, None).err().unwrap()), "STG-033"); } - /// Regression test for fuzz-discovered timeout (artifact: - /// `timeout-23b2b7e0aa43d92c12c49f123a48d6f4ace6ce33`). - /// - /// A crafted v5 header with page_count=3_604_123_350 and vaet_root_page=61 - /// caused migrate_v5_to_v6 to use page_count as the B-tree start page. - /// build_btree then wrote a leaf at offset ~14 TB in a sparse file, and - /// compute_page_checksum looped over 3.6 billion zero-filled sparse pages - /// (each read_exact returns zeros, no error), hanging the process. - /// - /// Since v3.0.0 a v5 header is rejected before any page is touched. #[test] - fn test_v5_migration_large_page_count_does_not_hang() { - use crate::storage::backend::FileBackend; - use tempfile::NamedTempFile; - - let tmp = NamedTempFile::new().unwrap(); - let path = tmp.path().to_path_buf(); - - // Write the exact fuzz-artifact header bytes (75 bytes + zero padding to 4096) - let mut page = vec![0u8; PAGE_SIZE]; - page[0..4].copy_from_slice(b"MGRF"); - page[4..8].copy_from_slice(&5u32.to_le_bytes()); // version = 5 - page[8..16].copy_from_slice(&3_604_123_350u64.to_le_bytes()); // page_count (huge) - page[56..64].copy_from_slice(&61u64.to_le_bytes()); // vaet_root_page = 61 - page[68] = 0x20; // fact_page_format - std::fs::write(&path, &page).unwrap(); - - // `FileBackend::open` itself reads and validates the header, so the - // pre-v7 rejection surfaces there rather than in - // `PersistentFactStorage::new`. - let err = match FileBackend::open(&path) { - Ok(_) => panic!("v5 header must be rejected"), - Err(e) => e, - }; - assert!( - err.to_string().contains("no longer supported"), - "must fail with STG-028" - ); + fn no_wal_and_no_evidence_opens_at_g() { + // The older slot rots; the newest is intact and is the only valid one. + let mut mem = three_generations(); + damage(&mut mem, slot_page(2)); + let pfs = open_mem(&mem, None).unwrap(); + assert_eq!(pfs.generation(), 3); + assert_eq!(count_n(&pfs), 40); } #[test] - fn test_header_checksum_computation() { - use crate::storage::FileHeader; - - let mut header = FileHeader::new(); - header.page_count = 10; - header.node_count = 5; - - let checksum = compute_header_checksum(&header); - assert_ne!(checksum, 0, "checksum must be non-zero"); - - let mut header2 = FileHeader::new(); - header2.page_count = 10; - header2.node_count = 5; - assert_eq!(compute_header_checksum(&header2), checksum); - - let mut header3 = FileHeader::new(); - header3.page_count = 11; - assert_ne!(compute_header_checksum(&header3), checksum); + fn unknown_feature_bit_is_refused_without_modifying_the_file() { + let mut mem = three_generations(); + let mut m = match MetaPage::decode(&mem.read_page(slot_page(3)).unwrap()) { + SlotState::Valid(m) => m, + _ => panic!("gen 3 valid"), + }; + m.required_features = 1 << 9; + mem.write_page(slot_page(3), &m.encode()).unwrap(); + let before = snapshot(&mem); + assert_eq!(code(open_mem(&mem, None).err().unwrap()), "STG-034"); + assert!(snapshot(&mem) == before, "file unchanged"); } #[test] - fn test_header_checksum_corruption_detection() { - use crate::storage::{FORMAT_VERSION, FileHeader}; - - let mut header = FileHeader::new(); - header.version = FORMAT_VERSION; - let valid_checksum = compute_header_checksum(&header); - header.header_checksum = valid_checksum; - - header.page_count = 999; - - let computed = compute_header_checksum(&header); - assert_ne!(computed, header.header_checksum); + fn pre_release_v8_single_header_is_stg_032() { + let mut mem = MemoryBackend::new(); + let mut h = LegacyHeaderV7::new(); + h.version = 8; + h.page_count = 3; + let mut page = h.to_bytes(); + page.resize(PAGE_SIZE, 0); + mem.write_page(0, &page).unwrap(); + mem.write_page(1, &vec![0u8; PAGE_SIZE]).unwrap(); + mem.write_page(2, &vec![0u8; PAGE_SIZE]).unwrap(); + assert_eq!(code(open_mem(&mem, None).err().unwrap()), "STG-032"); + } + + // ── v7 migration (spec §9) ────────────────────────────────────────────── + + /// A v7 file: header in page 0 and v7 (0x02, 12-byte header) fact pages from 1. + fn v7_file(facts: &[Fact], last_tx: u64) -> MemoryBackend { + let mut mem = MemoryBackend::new(); + let (pages, _) = pack_facts(facts, 1).unwrap(); + for (i, v8) in pages.iter().enumerate() { + let count = usize::from(u16::from_le_bytes([v8[2], v8[3]])); + let mut v7 = vec![0u8; PAGE_SIZE]; + v7[0] = crate::storage::packed_pages::PAGE_TYPE_PACKED_V7; + v7[2..4].copy_from_slice(&v8[2..4]); + v7[12..12 + 4 * count].copy_from_slice(&v8[24..24 + 4 * count]); + let data_start = 24 + 4 * count; + v7[data_start..].copy_from_slice(&v8[data_start..]); + mem.write_page(i as u64 + 1, &v7).unwrap(); + } + let mut h = LegacyHeaderV7::new(); + h.page_count = pages.len() as u64 + 1; + h.fact_page_count = pages.len() as u64; + h.node_count = facts.len() as u64; + h.last_checkpointed_tx_count = last_tx; + h.header_checksum = h.checksum(); + let mut page = h.to_bytes(); + page.resize(PAGE_SIZE, 0); + mem.write_page(0, &page).unwrap(); + mem } - #[test] - fn test_save_with_valid_header_read() { - use crate::storage::backend::FileBackend; - use tempfile::NamedTempFile; - use uuid::Uuid; - - let tmp = NamedTempFile::new().unwrap(); - let path = tmp.path().to_str().unwrap().to_string(); - let alice = Uuid::new_v4(); - - { - let mut pfs = - PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); + fn sample_facts(n: u128) -> Vec { + let pfs = PersistentFactStorage::new(MemoryBackend::new(), 0).unwrap(); + for i in 0..n { pfs.storage() .transact( - vec![( - alice, - ":name".to_string(), - Value::String("Alice".to_string()), - )], + vec![(entity(i), ":test/n".to_string(), Value::Integer(i as i64))], None, ) .unwrap(); - pfs.dirty = true; - pfs.save().unwrap(); - } - - { - let pfs = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); - let facts = pfs.storage().get_facts_by_entity(&alice).unwrap(); - assert_eq!(facts.len(), 1, "should load facts from existing file"); } + pfs.storage().get_all_facts().unwrap() } #[test] - fn test_save_fails_on_corrupted_header() { - use crate::storage::backend::FileBackend; - use tempfile::NamedTempFile; - - let tmp = NamedTempFile::new().unwrap(); - let path = tmp.path().to_str().expect("valid path").to_string(); - drop(tmp); - - { - let mut file = std::fs::OpenOptions::new() - .write(true) - .create(true) - .truncate(true) - .open(&path) - .unwrap(); - file.write_all(&vec![0u8; PAGE_SIZE]).unwrap(); - file.write_all(&vec![0u8; PAGE_SIZE]).unwrap(); - } - - let result = FileBackend::open(&path); - assert!( - result.is_err(), - "should fail on corrupted header in existing file" + fn v7_file_migrates_to_generation_1_with_backup_meta() { + let facts = sample_facts(300); + // Two trailing empty transactions: the counter must not rewind (#371). + let mem = v7_file(&facts, 302); + let old_pages = mem.page_count().unwrap(); + let pfs = open_mem(&mem, None).unwrap(); + let m = pfs.meta(); + assert_eq!(m.generation, 1); + assert_eq!(count_n(&pfs), 300); + assert_eq!(pfs.last_checkpointed_tx_count(), 302); + assert!(pfs.storage().current_tx_count() >= 302); + assert_space_accounted(&m, &mem); + assert_indexes_exact(&m, &mem); + // Old pages 2.. and the backup page are free; the backup is the last page + // and holds the same meta. + let backup_id = m.page_count - 1; + assert!(MetaPage::decode(&mem.read_page(backup_id).unwrap()).is_valid_generation(1)); + let (free, _) = + freelist::read_chain(m.freelist_head, &mem, &PageCache::new(0), m.page_count).unwrap(); + assert!(free.contains(&backup_id)); + assert!((2..old_pages).all(|id| free.contains(&id))); + drop(pfs); + // Reopening does not migrate again. + assert_eq!( + open_mem(&mem, None).unwrap().meta().page_count, + m.page_count ); } #[test] - fn test_is_new_returns_correct_value() { - use crate::storage::backend::FileBackend; - use tempfile::NamedTempFile; - - let tmp = NamedTempFile::new().unwrap(); - let path = tmp.path().to_str().expect("valid path").to_string(); - drop(tmp); - - let backend = FileBackend::open(&path).unwrap(); - assert!(backend.is_new(), "newly created file should be new"); - drop(backend); - - let backend = FileBackend::open(&path).unwrap(); - assert!(!backend.is_new(), "reopened file should not be new"); - drop(backend); - } - - // ══ #359: STG-0xx regression tests ═══════════════════════════════════ - - /// A poisoned backend mutex (a previous operation panicked while - /// holding the lock) must surface as the coded STG-016, not a generic - /// error. - #[test] - fn save_with_poisoned_backend_mutex_returns_stg_016() { - let mut pfs = PersistentFactStorage::new(MemoryBackend::new(), 16).unwrap(); - let alice = Uuid::new_v4(); - pfs.storage() - .transact( - vec![( - alice, - ":name".to_string(), - Value::String("Alice".to_string()), - )], - None, - ) - .unwrap(); - pfs.mark_dirty(); - - // Poison the backend mutex by panicking while holding it. - let backend = pfs.backend.clone(); - let handle = std::thread::spawn(move || { - let _guard = backend.lock().unwrap(); - panic!("deliberate poison for STG-016 regression test"); - }); - let _ = handle.join(); - - let err = pfs - .save() - .expect_err("save on a poisoned backend mutex must fail"); - let coded: crate::error::MinigrafError = err.into(); - assert_eq!(coded.code(), "STG-016"); - assert_eq!(coded.category(), crate::error::ErrorCategory::Storage); - } - - /// A backend that reports an existing (non-new) file but then fails to - /// re-read the header at `save()` time (e.g. a transient disk I/O - /// error) must surface as the coded STG-010, not a generic error. - /// `read_page(0)` is allowed to succeed exactly once, so `load()` (run - /// from `PersistentFactStorage::new()`, since `is_new()` is false) - /// completes normally; the failure is injected only for the *second* - /// `read_page(0)` call, which `save()` makes. - struct FlakyHeaderBackend { - inner: MemoryBackend, - read_page_0_calls: std::sync::atomic::AtomicU32, - } - - impl StorageBackend for FlakyHeaderBackend { - fn write_page(&mut self, page_id: u64, data: &[u8]) -> Result<()> { - self.inner.write_page(page_id, data) - } - fn read_page(&self, page_id: u64) -> Result> { - if page_id == 0 { - let calls = self - .read_page_0_calls - .fetch_add(1, std::sync::atomic::Ordering::SeqCst); - if calls >= 1 { - anyhow::bail!("simulated disk read failure"); + fn crash_at_every_point_of_migration_keeps_every_fact() { + let facts = sample_facts(120); + let mut points = 0; + for torn in [None, Some(0usize), Some(20), Some(2048)] { + for k in 0u64.. { + let mem = v7_file(&facts, 120); + let (backend, config) = FaultInjectingBackend::with_config(mem.clone()); + { + let mut cfg = config.lock().unwrap(); + cfg.fail_write_after = Some(k); + cfg.torn_write_bytes = torn; + } + let done = PersistentFactStorage::open(backend, 16, None).is_ok(); + let pfs = open_mem(&mem, None).expect("reopen after an interrupted migration"); + assert_eq!(count_n(&pfs), 120, "every v7 fact survives"); + assert_eq!(pfs.generation(), 1); + assert_space_accounted(&pfs.meta(), &mem); + if done { + break; } + points += 1; } - self.inner.read_page(page_id) - } - fn sync(&mut self) -> Result<()> { - self.inner.sync() - } - fn page_count(&self) -> Result { - self.inner.page_count() - } - fn close(&mut self) -> Result<()> { - self.inner.close() - } - fn backend_name(&self) -> &'static str { - "flaky-header-test" - } - fn is_new(&self) -> bool { - false } + assert!(points > 20, "expected many crash points"); } + // ── crash atomicity (spec §11) ────────────────────────────────────────── + + /// Kill `save()` at every page write (cleanly or with a torn page) and every + /// sync, on a file already written by several checkpoints. Reopen with the + /// WAL's base generation: the old generation (old facts, WAL replays the + /// rest) or the new one (all facts), never anything else, and the space + /// invariant holds either way. #[test] - fn save_with_unreadable_existing_header_returns_stg_010() { - let mut inner = MemoryBackend::new(); - // A valid, empty v7 header so `load()` (triggered by `is_new() == - // false`) succeeds cleanly on the first `read_page(0)` call. - let mut header_page = FileHeader::new().to_bytes(); - header_page.resize(PAGE_SIZE, 0); - inner.write_page(0, &header_page).unwrap(); - - let backend = FlakyHeaderBackend { - inner, - read_page_0_calls: std::sync::atomic::AtomicU32::new(0), + fn crash_at_every_point_in_save_loses_no_checkpointed_fact() { + const PER_BATCH: u128 = 150; + const OLD_BATCHES: u128 = 3; + let build = || { + let mem = MemoryBackend::new(); + let mut pfs = PersistentFactStorage::new(mem.clone(), 16).unwrap(); + for b in 0..OLD_BATCHES { + put_batch(&mut pfs, b * PER_BATCH..(b + 1) * PER_BATCH); + pfs.save().unwrap(); + } + let g = pfs.generation(); + (mem, g) }; - let mut pfs = PersistentFactStorage::new(backend, 16).unwrap(); - pfs.mark_dirty(); - - let err = pfs - .save() - .expect_err("save must fail when the header becomes unreadable"); - let coded: crate::error::MinigrafError = err.into(); - assert_eq!(coded.code(), "STG-010"); - assert_eq!(coded.category(), crate::error::ErrorCategory::Storage); - } - - // ══ #214 fault-injection unit tests ══════════════════════════════════ - - mod fault_injection_tests { - use super::*; - use crate::storage::backend::MemoryBackend; - use crate::storage::backend::fault_inject::{FaultConfig, FaultInjectingBackend}; - - fn make_pfs_with_config() -> ( - PersistentFactStorage>, - std::sync::Arc>, - ) { - let (backend, config) = FaultInjectingBackend::with_config(MemoryBackend::new()); - let pfs = PersistentFactStorage::new(backend, 16).unwrap(); - (pfs, config) - } - - fn stage_fact(pfs: &mut PersistentFactStorage>) { - let entity = Uuid::new_v4(); - pfs.storage() - .transact( - vec![(entity, ":test/attr".to_string(), Value::Boolean(true))], - None, - ) - .unwrap(); - pfs.mark_dirty(); - } - - #[test] - fn save_returns_error_when_write_fails() { - let (mut pfs, config) = make_pfs_with_config(); - stage_fact(&mut pfs); - config.lock().unwrap().fail_write_after = Some(0); - let result = pfs.save(); - assert!( - result.is_err(), - "save must return Err when write_page fails" - ); - } - - #[test] - fn save_returns_error_when_sync_fails() { - let (mut pfs, config) = make_pfs_with_config(); - stage_fact(&mut pfs); - config.lock().unwrap().fail_sync_after = Some(0); - let result = pfs.save(); - assert!(result.is_err(), "save must return Err when sync fails"); - } + let old_total = (OLD_BATCHES * PER_BATCH) as usize; + let new_total = old_total + PER_BATCH as usize; - #[test] - fn save_error_message_is_non_empty() { - let (mut pfs, config) = make_pfs_with_config(); - stage_fact(&mut pfs); - config.lock().unwrap().fail_sync_after = Some(0); - let err = pfs.save().unwrap_err(); - assert!( - !err.to_string().is_empty(), - "error message must not be empty" - ); + let mut points = 0; + let mut kinds: Vec<(Option, Option, Option)> = Vec::new(); + for torn in [None, Some(0usize), Some(512), Some(4095)] { + kinds.push((Some(0), None, torn)); } - - /// #374: `save()` is not crash-atomic, but a crash at any point inside it must - /// lose no checkpointed fact. Kills `save()` at every page write and every sync - /// of a checkpoint on a file already written by several checkpoints, then reopens - /// the bytes that reached storage. Either the old header survives (old facts only, - /// old `last_checkpointed_tx_count`, so WAL replay re-applies the in-flight - /// transaction) or the new one does (all facts). Never anything in between. - #[test] - fn crash_at_every_point_in_save_loses_no_checkpointed_fact() { - const PER_BATCH: u128 = 150; - const OLD_BATCHES: u128 = 3; - let entity = |i: u128| Uuid::from_u128(i + 1); - - // A file written by several checkpoints, then one more batch pending. - let build = || { - let mem = MemoryBackend::new(); - let mut pfs = PersistentFactStorage::new(mem.clone(), 16).unwrap(); - for b in 0..OLD_BATCHES { - let batch = (b * PER_BATCH..(b + 1) * PER_BATCH) - .map(|i| (entity(i), ":test/n".to_string(), Value::Integer(i as i64))) - .collect(); - pfs.storage().transact(batch, None).unwrap(); - pfs.mark_dirty(); - pfs.save().unwrap(); - } - let old_tx = pfs.last_checkpointed_tx_count(); - drop(pfs); - (mem, old_tx) - }; - let old_total = (OLD_BATCHES * PER_BATCH) as usize; - let new_total = old_total + PER_BATCH as usize; - - // Returns (fact count, last_checkpointed_tx_count, rebuilt on open). - let crash_and_reopen = |fail_write: Option, fail_sync: Option| { - let (mem, old_tx) = build(); + kinds.push((None, Some(0), None)); + for (write_kind, sync_kind, torn) in kinds { + for k in 0u64.. { + let (mem, g) = build(); let (backend, config) = FaultInjectingBackend::with_config(mem.clone()); let mut pfs = PersistentFactStorage::new(backend, 16).unwrap(); - let batch = (OLD_BATCHES * PER_BATCH..(OLD_BATCHES + 1) * PER_BATCH) - .map(|i| (entity(i), ":test/n".to_string(), Value::Integer(i as i64))) - .collect(); - pfs.storage().transact(batch, None).unwrap(); - pfs.mark_dirty(); + put_batch( + &mut pfs, + OLD_BATCHES * PER_BATCH..(OLD_BATCHES + 1) * PER_BATCH, + ); { let mut cfg = config.lock().unwrap(); - cfg.fail_write_after = fail_write; - cfg.fail_sync_after = fail_sync; + cfg.fail_write_after = write_kind.map(|_| k); + cfg.fail_sync_after = sync_kind.map(|_| k); + cfg.torn_write_bytes = torn; } let saved = pfs.save().is_ok(); - // Simulated kill: no retry, no auto-save on drop. - pfs.dirty = false; + pfs.dirty = false; // simulated kill: no auto-save on drop drop(pfs); - let pfs = PersistentFactStorage::new(mem, 16).expect("reopen after crash"); - let by_attr = pfs - .storage() - .get_facts_by_attribute(&":test/n".to_string()) - .unwrap() - .len(); - let limit = if by_attr == new_total { - new_total + // The WAL holding the in-flight batch was created at base g. + let pfs = open_mem(&mem, Some(g)).expect("reopen after crash"); + let count = count_n(&pfs); + if pfs.generation() == g + 1 { + assert_eq!(count, new_total, "new generation sees all facts"); } else { - old_total - }; - for i in 0..limit as u128 { + assert_eq!(pfs.generation(), g, "otherwise the old generation"); + assert_eq!(count, old_total, "old generation sees the old facts"); + assert!(!saved, "a reported success must be durable"); + } + for i in 0..count as u128 { let facts = pfs.storage().get_facts_by_entity(&entity(i)).unwrap(); assert_eq!(facts.len(), 1, "entity lookup lost a checkpointed fact"); } - let rebuilt = pfs.fact_prefix_crc.is_none(); - ( - saved, - by_attr, - pfs.last_checkpointed_tx_count(), - old_tx, - rebuilt, - ) - }; - - let mut rebuilds = 0; - let mut points = 0; - for fault in ["write", "sync"] { - for k in 0u64.. { - let (saved, count, tx, old_tx, rebuilt) = if fault == "write" { - crash_and_reopen(Some(k), None) - } else { - crash_and_reopen(None, Some(k)) - }; - if saved { - assert_eq!(count, new_total, "completed save must keep all facts"); - break; - } - points += 1; - rebuilds += usize::from(rebuilt); - if tx == old_tx { - assert_eq!( - count, old_total, - "old header must see exactly the old facts" - ); - } else { - assert_eq!(count, new_total, "new header must see all facts"); - } + assert_space_accounted(&pfs.meta(), &mem); + if saved { + assert_eq!(count, new_total, "completed save keeps all facts"); + break; } + points += 1; } - assert!(points > 20, "expected many crash points"); - assert!( - rebuilds > 0, - "expected some crash points to force an index rebuild" - ); - eprintln!("#374 crash test: {points} crash points, {rebuilds} rebuilt on open"); } + assert!(points > 50, "expected many crash points"); } } diff --git a/src/wal.rs b/src/wal.rs index 3c611c940a..a70faa9c2a 100644 --- a/src/wal.rs +++ b/src/wal.rs @@ -8,9 +8,15 @@ //! //! ```text //! WAL header (32 bytes): -//! magic: [u8; 4] = b"MWAL" -//! version: u32 LE = 1 -//! reserved: [u8; 24] +//! magic: [u8; 4] = b"MWAL" +//! version: u32 LE = 2 +//! base_generation: u64 LE generation of the meta page that was active when +//! this WAL was created (v2; spec §4.1.1) +//! reserved: [u8; 16] +//! +//! A version 1 header (v2.x) has no base_generation. It can only sit next to a +//! file migrated from format v7 whose next checkpoint has not completed, so it +//! reads as base generation 1. //! //! WAL entries (variable length, sequential): //! checksum: u32 LE CRC32 of everything after this field in this entry @@ -30,23 +36,27 @@ use std::io::{self, Read, Seek, SeekFrom, Write}; use std::path::Path; const WAL_MAGIC: [u8; 4] = *b"MWAL"; -const WAL_VERSION: u32 = 1; +const WAL_VERSION: u32 = 2; +/// Format v7 (Minigraf v2.x) WAL version, read as base generation 1. +const WAL_VERSION_V1: u32 = 1; const WAL_HEADER_SIZE: usize = 32; // ─── WAL Header ───────────────────────────────────────────────────────────── -fn write_wal_header(file: &mut File) -> Result<()> { +fn write_wal_header(file: &mut File, base_generation: u64) -> Result<()> { let mut buf = [0u8; WAL_HEADER_SIZE]; buf[0..4].copy_from_slice(&WAL_MAGIC); buf[4..8].copy_from_slice(&WAL_VERSION.to_le_bytes()); - // bytes 8..32 are reserved zeros + buf[8..16].copy_from_slice(&base_generation.to_le_bytes()); + // bytes 16..32 are reserved zeros file.seek(SeekFrom::Start(0))?; file.write_all(&buf)?; file.sync_all()?; Ok(()) } -fn validate_wal_header(file: &mut File) -> Result<()> { +/// Check magic and version and return the header's base generation. +fn validate_wal_header(file: &mut File) -> Result { let mut buf = [0u8; WAL_HEADER_SIZE]; file.seek(SeekFrom::Start(0))?; file.read_exact(&mut buf)?; @@ -55,10 +65,15 @@ fn validate_wal_header(file: &mut File) -> Result<()> { bail_coded!(ErrorCode::Wal001); } let version = u32::from_le_bytes([buf[4], buf[5], buf[6], buf[7]]); - if version != WAL_VERSION { - bail_coded!(ErrorCode::Wal002, version, WAL_VERSION); + match version { + WAL_VERSION => { + let mut base = [0u8; 8]; + base.copy_from_slice(&buf[8..16]); + Ok(u64::from_le_bytes(base)) + } + WAL_VERSION_V1 => Ok(1), + _ => bail_coded!(ErrorCode::Wal002, version, WAL_VERSION), } - Ok(()) } /// Whether an existing WAL file's header is intact, or too short to @@ -135,11 +150,22 @@ pub struct WalWriter { } impl WalWriter { + /// [`WalWriter::open_or_create_at`] with base generation 1, for tests. + #[cfg(test)] + pub fn open_or_create(path: &Path, sync_mode: SyncMode) -> Result { + Self::open_or_create_at(path, sync_mode, 1) + } + /// Open an existing WAL or create a new one. /// - /// If creating, writes the WAL header. - /// If opening, validates the header and seeks to the end for appending. - pub fn open_or_create(path: &Path, sync_mode: SyncMode) -> Result { + /// If creating, writes the WAL header with `base_generation`, the generation + /// of the meta page active now. If opening, validates the header (keeping its + /// base generation) and seeks to the end for appending. + pub fn open_or_create_at( + path: &Path, + sync_mode: SyncMode, + base_generation: u64, + ) -> Result { // Try atomic create-new first (no TOCTOU window) match OpenOptions::new() .read(true) @@ -148,7 +174,7 @@ impl WalWriter { .open(path) { Ok(mut file) => { - write_wal_header(&mut file)?; + write_wal_header(&mut file, base_generation)?; // The header is durable; make the WAL's directory entry // durable too, or a power loss can lose the whole file (#389). sync_parent_dir(path)?; @@ -162,14 +188,16 @@ impl WalWriter { // File exists — validate its header and seek to end for appending let mut file = OpenOptions::new().read(true).write(true).open(path)?; match check_wal_header_length(&mut file)? { - WalHeaderState::Present => validate_wal_header(&mut file)?, + WalHeaderState::Present => { + validate_wal_header(&mut file)?; + } // A previous crash landed between this file's creation and its // header write completing; no entry could have been appended // yet, so re-initialize it as a fresh, empty WAL. // The crash may also have preceded the directory sync that // follows creation, so repeat it (#389). WalHeaderState::Absent => { - write_wal_header(&mut file)?; + write_wal_header(&mut file, base_generation)?; sync_parent_dir(path)?; } } @@ -239,23 +267,34 @@ impl WalWriter { /// Reads and validates WAL entries for crash recovery. pub struct WalReader { file: File, + base_generation: Option, } impl WalReader { /// Open the WAL at `path` for reading. pub fn open(path: &Path) -> Result { let mut file = File::open(path)?; - match check_wal_header_length(&mut file)? { - WalHeaderState::Present => validate_wal_header(&mut file)?, + let base_generation = match check_wal_header_length(&mut file)? { + WalHeaderState::Present => Some(validate_wal_header(&mut file)?), // Too short to contain a header, which can only mean a crash // landed before any entry was ever appended (see // `WalHeaderState::Absent`). `read_entries` already treats // hitting EOF while reading an entry as "no more entries", so // leaving the file as-is and letting that seek-past-end happen // naturally is correct -- there is nothing here to replay. - WalHeaderState::Absent => {} - } - Ok(WalReader { file }) + WalHeaderState::Absent => None, + }; + Ok(WalReader { + file, + base_generation, + }) + } + + /// The generation of the meta page active when this WAL was created, or + /// `None` for a header-less WAL (a crash before its header was written, so + /// it holds no entries and counts as no WAL). + pub fn base_generation(&self) -> Option { + self.base_generation } /// Read all valid entries from the WAL. @@ -867,4 +906,40 @@ mod tests { std::fs::remove_dir(&path).unwrap(); } + + #[test] + fn test_wal_v2_header_records_base_generation() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("base.wal"); + drop(WalWriter::open_or_create_at(&path, SyncMode::Full, 42).unwrap()); + assert_eq!(WalReader::open(&path).unwrap().base_generation(), Some(42)); + // Reopening for append keeps the original base generation. + drop(WalWriter::open_or_create_at(&path, SyncMode::Full, 99).unwrap()); + assert_eq!(WalReader::open(&path).unwrap().base_generation(), Some(42)); + } + + #[test] + fn test_wal_v1_header_reads_as_base_generation_1() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("v1.wal"); + let mut header = [0u8; WAL_HEADER_SIZE]; + header[0..4].copy_from_slice(&WAL_MAGIC); + header[4..8].copy_from_slice(&1u32.to_le_bytes()); + std::fs::write(&path, header).unwrap(); + assert_eq!(WalReader::open(&path).unwrap().base_generation(), Some(1)); + // A v2.x WAL can still be appended to. + let mut w = WalWriter::open_or_create_at(&path, SyncMode::Full, 5).unwrap(); + w.append_entry(1, &[]).unwrap(); + drop(w); + let mut r = WalReader::open(&path).unwrap(); + assert_eq!(r.read_entries().unwrap().len(), 1); + } + + #[test] + fn test_wal_headerless_has_no_base_generation() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("short.wal"); + std::fs::write(&path, [0u8; 5]).unwrap(); + assert_eq!(WalReader::open(&path).unwrap().base_generation(), None); + } } diff --git a/tests/btree_v6_test.rs b/tests/btree_v6_test.rs index d3cd770504..1ada2b5a22 100644 --- a/tests/btree_v6_test.rs +++ b/tests/btree_v6_test.rs @@ -207,57 +207,49 @@ fn test_v6_dead_pages_queries_correct_after_two_checkpoints() { assert!(s0.contains('0'), "original e0 should still be visible"); } +/// Damaging the newest meta page after a completed checkpoint (its WAL already +/// deleted) must refuse to open with STG-033, never silently fall back to the +/// older meta and lose that checkpoint's facts. #[test] -fn test_v6_checksum_mismatch_triggers_rebuild() { +fn newest_meta_damaged_after_commit_is_refused() { use std::io::{Read, Seek, SeekFrom, Write}; let (_tmp, path) = tmp_path(); populate_and_checkpoint(30, &path); - // Corrupt a field in the header - header_checksum now covers all header fields - // so this will trigger header_checksum mismatch (correct per spec) - { - let mut f = std::fs::OpenOptions::new() - .read(true) - .write(true) - .open(&path) - .unwrap(); - - // Read full page (4096 bytes) - let mut page = vec![0u8; 4096]; - f.read_exact(&mut page).unwrap(); - - // Corrupt index_checksum at bytes 64..68 - page[64] = 0xFF; - page[65] = 0xFF; - page[66] = 0xFF; - page[67] = 0xFF; - - // Compute header_checksum over bytes 0..79 (with bytes 80..83 zeroed) - let mut checksum_data = page[..80].to_vec(); - checksum_data.extend_from_slice(&[0u8; 4]); // bytes 80-83 zeroed for checksum - let checksum = crc32fast::hash(&checksum_data); - page[80] = (checksum & 0xFF) as u8; - page[81] = ((checksum >> 8) & 0xFF) as u8; - page[82] = ((checksum >> 16) & 0xFF) as u8; - page[83] = ((checksum >> 24) & 0xFF) as u8; - - // Write back the corrupted page with valid header_checksum - f.seek(SeekFrom::Start(0)).unwrap(); - f.write_all(&page).unwrap(); + let mut f = std::fs::OpenOptions::new() + .read(true) + .write(true) + .open(&path) + .unwrap(); + let mut pages = [vec![0u8; 4096], vec![0u8; 4096]]; + for p in pages.iter_mut() { + f.read_exact(p).unwrap(); } + let generation = |p: &[u8]| { + if &p[8..12] == b"META" { + u64::from_le_bytes(p[16..24].try_into().unwrap()) + } else { + 0 + } + }; + let newest = if generation(&pages[0]) > generation(&pages[1]) { + 0 + } else { + 1 + }; + assert!( + generation(&pages[newest]) >= 2, + "a checkpoint was committed" + ); + pages[newest][30] ^= 0xFF; + f.seek(SeekFrom::Start(newest as u64 * 4096)).unwrap(); + f.write_all(&pages[newest]).unwrap(); + drop(f); - // Re-open: header_checksum mismatch must be detected (correct per spec) match OpenOptions::new().path(&path).open() { - Ok(_) => panic!("opening corrupted file should fail"), - Err(e) => { - let err = e.to_string(); - assert!( - err.contains("Header checksum mismatch"), - "error should mention header checksum mismatch, got: {}", - err - ); - } + Ok(_) => panic!("opening with the newest meta damaged must fail"), + Err(e) => assert_eq!(e.code(), "STG-033"), } } diff --git a/tests/edge_cases_test.rs b/tests/edge_cases_test.rs index 1c4ee58f52..94180260ee 100644 --- a/tests/edge_cases_test.rs +++ b/tests/edge_cases_test.rs @@ -19,7 +19,7 @@ fn test_oversized_fact_rejected_at_insertion_file_backed() { .open() .unwrap(); - let large_value = "x".repeat(8192); // well above MAX_FACT_BYTES = 4080 + let large_value = "x".repeat(8192); // well above MAX_FACT_BYTES = 4052 let cmd = format!("(transact [[:e :attr \"{}\"]])", large_value); let result = db.execute(&cmd); @@ -29,8 +29,8 @@ fn test_oversized_fact_rejected_at_insertion_file_backed() { ); let msg = format!("{}", result.unwrap_err()); assert!( - msg.contains("4080"), - "error message must cite the 4080-byte limit; got: {}", + msg.contains("4052"), + "error message must cite the 4052-byte limit; got: {}", msg ); } @@ -59,8 +59,8 @@ fn test_oversized_fact_rejected_via_write_transaction() { ); let msg = format!("{}", result.unwrap_err()); assert!( - msg.contains("4080"), - "error message must cite the 4080-byte limit; got: {}", + msg.contains("4052"), + "error message must cite the 4052-byte limit; got: {}", msg ); } diff --git a/tests/error_codes_wal_test.rs b/tests/error_codes_wal_test.rs index f42f95848b..71eae1376c 100644 --- a/tests/error_codes_wal_test.rs +++ b/tests/error_codes_wal_test.rs @@ -108,7 +108,7 @@ fn wal_size_limit_oversized_fact_returns_wal_003() { let db = Minigraf::open(&db_path).unwrap(); - // Comfortably over MAX_FACT_BYTES (~4080 bytes) but well under the + // Comfortably over MAX_FACT_BYTES (4052 bytes) but well under the // parser's own 1 MB string cap, so the parser accepts it and the WAL // layer is what rejects it. let huge_value = "a".repeat(20_000); diff --git a/tests/multi_value_test.rs b/tests/multi_value_test.rs index eb41859b88..07e0f94ff4 100644 --- a/tests/multi_value_test.rs +++ b/tests/multi_value_test.rs @@ -481,7 +481,7 @@ fn max_size_value_at_exact_boundary_checkpoint_and_read_back() { // with `big_a`. Same attribute name (`:blob`) as the real facts below: // the attribute string is part of the encoded fact size, so a // differently-sized attribute name would find a different boundary. - // `hi` starts comfortably above MAX_FACT_BYTES (4080), so it is + // `hi` starts comfortably above MAX_FACT_BYTES (4052), so it is // guaranteed to fail. let mut lo = 0usize; let mut hi = 4096usize;