From a6481249cad8a95bd54d46d683b210edb782702f Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 7 Oct 2026 14:54:42 +0530 Subject: [PATCH] fix(browser): store migrated pages on open; keep only live pages (#411, #440) BrowserDb.open() now flushes the pages an open writes, so a v7 IndexedDB store is upgraded to v8 once instead of in memory on every open (#411). Free pages no longer hold bytes in the buffer or keys in IndexedDB (#440). Open drops the whole free list (after a v7 upgrade, the old v7 region); each commit drops the ids it newly put on the free list, which PageAllocator::finish_free_list now returns, so the cost stays O(change). The deletes go in the same IndexedDB transaction as the commit's pages and meta page. importGraph() also deletes the replaced database's keys. exportGraph() pads free pages with zeros up to the meta's page_count. Spec: docs/superpowers/specs/2026-10-07-browser-page-reuse-design.md Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- CHANGELOG.md | 1 + CLAUDE.md | 2 +- README.md | 2 +- docs/TEST_COVERAGE.md | 4 +- .../2026-10-07-browser-page-reuse-design.md | 90 +++++ src/browser/buffer.rs | 87 ++++- src/browser/indexeddb.rs | 28 +- src/browser/mod.rs | 325 ++++++++++++++++-- src/storage/freelist.rs | 15 +- src/storage/page.rs | 8 +- src/storage/persistent_facts.rs | 58 +++- .../persistent_facts/browser_access.rs | 31 +- 12 files changed, 603 insertions(+), 48 deletions(-) create mode 100644 docs/superpowers/specs/2026-10-07-browser-page-reuse-design.md diff --git a/CHANGELOG.md b/CHANGELOG.md index 321f49d21..fb71b2f32 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -30,6 +30,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Fixed - **The wasm32 builds are tested again, and the browser layer no longer panics or drops pages.** The repo split (#231) moved the browser and WASI CI jobs to minigraf-wasm, which only builds the package, so core's own wasm tests stopped running and the wasm32 test build broke unnoticed. A new `wasm.yml` workflow runs the `wasm-bindgen` tests in headless Firefox and Chrome, runs the unit and integration tests on `wasm32-wasip1` under Wasmtime, and lints both targets with `clippy -D warnings`. Fixes found on the way: `BrowserDb` skipped any dirty page it could not read when flushing to IndexedDB and still reported success, and now returns the error. The IndexedDB upgrade callback, the IndexedDB backend handle and the page-buffer lock no longer `unwrap()` (on wasm32 a panic aborts the whole instance). IndexedDB keys that are not whole page numbers are rejected instead of truncated. The nine `BrowserBufferBackend` tests used `#[test]`, which the wasm test runner never runs, and now run. File-only modules (`wal`, `storage::verify`, `storage::dir_sync`) are no longer compiled for wasm32, so the wasm32 builds have no warnings. +- **`BrowserDb` stores upgraded pages and keeps only live pages** (#411, #440). `BrowserDb.open()` now writes the pages an open produced to IndexedDB, so a v7 store is upgraded to v8 once instead of in memory on every open. Pages on the free list no longer keep their bytes in memory or their keys in IndexedDB: open drops them (after a v7 upgrade, the whole old v7 region), and each `transact`, `retract`, `checkpoint()` and `importGraph()` drops the pages its commit freed, in the same IndexedDB transaction as the commit's pages and meta page. Memory and IndexedDB size now follow the live data rather than the write history, and opening no longer reads dead pages back. `importGraph()` also deletes the keys of the replaced database's pages, which a reopen used to load next to the imported ones. `exportGraph()` writes free pages as zeros and is as long as the file's meta page says; the blob opens natively as before. - Two values of the same attribute written in one transaction are both returned by every query path. Previously only one came back, and entity-bound and attribute-bound queries could return different ones (#371, #287). - A retract that removes several values of one attribute in one call now hides all of them (#371). - Queries no longer lose or duplicate facts when more than 65,535 facts are waiting for a checkpoint (#445; also fixed in v2.0.3). diff --git a/CLAUDE.md b/CLAUDE.md index ab18c0226..5cb7d8bea 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -197,7 +197,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1346 tests** (1337 passing, 9 ignored; unit + integration + doc). +**1347 tests** (1338 passing, 9 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/README.md b/README.md index 33509c5e8..15fc187b7 100644 --- a/README.md +++ b/README.md @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1346 tests +cargo test # run 1347 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 4f5f7d7bf..1c3858600 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-10-07 with `cargo test --quiet` -**Result**: 1,337 passing tests and 9 ignored tests (1,346 total) +**Result**: 1,338 passing tests and 9 ignored tests (1,347 total) -This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, and `API-011` from `transact` and from `WriteTransaction::commit`. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 25 `wasm_bindgen_test` tests: fourteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), nine for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 935 passing; nine that spawn threads or a child process are ignored on WASI. These are not counted above. +This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, and `API-011` from `transact` and from `WriteTransaction::commit`. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 935 passing; nine that spawn threads or a child process are ignored on WASI. These are not counted above. ### Covered Areas diff --git a/docs/superpowers/specs/2026-10-07-browser-page-reuse-design.md b/docs/superpowers/specs/2026-10-07-browser-page-reuse-design.md new file mode 100644 index 000000000..31f9f569f --- /dev/null +++ b/docs/superpowers/specs/2026-10-07-browser-page-reuse-design.md @@ -0,0 +1,90 @@ +# BrowserDb: write back migrated pages, keep only live pages — Design + +Issues: #411 (migrated pages are not written back to IndexedDB), #440 (bound page +growth via v8 free-list reuse; avoid v7→v8 migration bloat). Milestone v3.0.0, branch +`v3`. + +## 1. Problem + +- `BrowserDb::open()` runs `PersistentFactStorage::new` on the pages loaded from + IndexedDB. A v7 store is migrated to v8 in the buffer, but nothing is flushed, so the + stored copy stays v7 and every open migrates again (#411). +- v8 checkpoints reuse freed pages (spec 2026-10-05 §8), so the *live* page set is + bounded. But a free page keeps its old bytes in `BrowserBufferBackend` and its key in + IndexedDB. After a v7→v8 migration the whole v7 region is free: one extra copy of the + database in the WASM heap and in IndexedDB, for good (#440 §2). + +## 2. Decisions + +D1. **Free pages hold no bytes in the browser.** After open and after each commit, +`BrowserDb` drops the bytes of every page on the active free list from the buffer and +deletes its IndexedDB key. Chosen over "migrate into a fresh object store" because it +also covers ordinary churn, needs no IndexedDB schema version bump, and has one code +path. Safe because: + - A free page is never read before it is written: the allocator hands out ids and the + writer fills them; only free-list *chain* pages are read, and those are referenced + by the meta, so never dropped. + - The single-valid-slot probe (§4.1.1) already skips an unreadable page. + - A read of an absent page is still `INT-052`, free or not. + +D2. **One IndexedDB transaction per flush.** `IndexedDbBackend::write_pages` takes the +puts *and* the deletes. The meta page is in the dirty set of the same commit, so data +pages, meta and deletes commit or abort together (v8 spec §12, verified). + +D3. **O(change) per commit.** `PersistentFactStorage::save` records the ids it lists in +the new free-list head pages (freed pages, chain pages read, ids read but not handed +out). The untouched tail was already released by an earlier commit or by open. +`take_released()` hands that list to the caller. Open releases the whole free list once +(`free_page_ids()`). + +D4. **Open flushes (#411).** After `PersistentFactStorage::new`, `open()` releases the +free list and flushes dirty pages and deletes, like `import_graph()`. A normal open of a +v8 store with nothing to release does no IndexedDB write. + +D5. **Export pads free pages with zeros.** `exportGraph()` writes +`max(meta.page_count, buffer high-water)` pages. A page the buffer released is written +as zeros; any other absent page is an error. Natively a zero page on the free list is +never read (allocator writes first; probe and verify do not decode free pages), so the +blob opens and verifies with `Minigraf::open()`. + +D6. **Buffer bookkeeping.** `BrowserBufferBackend` gains `release(ids) -> Vec` +(drops bytes, clears dirty, returns ids that had bytes, i.e. the IndexedDB keys to +delete) and a `released` id set used only by export. A later `write_page` to a released +id removes it from the set. + +## 3. Failure model + +IndexedDB transactions are atomic, so a crash leaves the store at either the previous +or the new commit. A save that reaches the buffer but never the store (tab closed +before the flush) reopens at the previous commit, whose pages were never deleted (the +deletes are in the unflushed transaction). + +Out of scope (pre-existing): if a flush *fails*, the drained dirty set is not restored, +so a later flush can miss pages. Tracked separately. + +## 4. Tests + +wasm (`wasm-pack test --headless --firefox --features browser`): +1. v7 fixture pages written straight into IndexedDB → `open()` + query only → page 0 + in IndexedDB is a v8 meta; IndexedDB key count equals live pages; no v7 bytes left + (#411, #440 §2). +2. N transacts on an IndexedDB store → buffer page count and IndexedDB key count equal + `meta.page_count − freelist_count` and stay below a bound independent of N. +3. A save applied to the buffer but not flushed, then reopen → previous commit, free + list consistent, a further transact succeeds. +4. Export after churn → page 0 meta valid, length `meta.page_count` pages, imports back. +5. Buffer unit tests for `release`. + +Native: +6. `PersistentFactStorage`: zeroing every free page after save, then reopen, verify and + more saves → no findings, facts intact (what an exported blob looks like). +7. `take_released()` after save lists exactly the ids newly put on the free list. + +## 5. Docs + +CHANGELOG (v3.0.0, browser), TEST_COVERAGE, CLAUDE.md test count. No new error codes. + +## 6. Philosophy + +Aligned: reliability (no lost migrations), self-contained (no new deps), single store, +no format change. diff --git a/src/browser/buffer.rs b/src/browser/buffer.rs index 86376a390..910ee95e5 100644 --- a/src/browser/buffer.rs +++ b/src/browser/buffer.rs @@ -8,9 +8,16 @@ use std::collections::{HashMap, HashSet}; /// Implements `StorageBackend` so it can be used with `PersistentFactStorage`. /// After `PersistentFactStorage::save()` writes updated pages here, call /// `take_dirty()` to retrieve the page IDs that must be flushed to IndexedDB. +/// +/// A page on the free list holds no bytes (#440): [`release`](Self::release) +/// drops them. Reading a released page is an error like any absent page; the +/// allocator always writes a free page before anything reads it. pub struct BrowserBufferBackend { pages: HashMap>, dirty: HashSet, + /// Free pages whose bytes were dropped. Only export reads this, to write + /// them as zeros. + released: HashSet, } impl BrowserBufferBackend { @@ -19,6 +26,7 @@ impl BrowserBufferBackend { Self { pages: HashMap::new(), dirty: HashSet::new(), + released: HashSet::new(), } } @@ -28,6 +36,7 @@ impl BrowserBufferBackend { Self { pages, dirty: HashSet::new(), + released: HashSet::new(), } } @@ -35,7 +44,11 @@ impl BrowserBufferBackend { /// Used during `BrowserDb::import_graph()` so all pages are flushed to IDB. pub fn load_pages_all_dirty(pages: HashMap>) -> Self { let dirty: HashSet = pages.keys().copied().collect(); - Self { pages, dirty } + Self { + pages, + dirty, + released: HashSet::new(), + } } /// Drain and return the set of page IDs written since the last call. @@ -44,6 +57,40 @@ impl BrowserBufferBackend { std::mem::take(&mut self.dirty) } + /// Drop the bytes of the free pages `ids` and forget any unflushed write to + /// them. Returns the ids that held bytes: the IndexedDB keys to delete in + /// the same transaction as the commit's meta page. + pub fn release(&mut self, ids: impl IntoIterator) -> Vec { + let mut dropped = Vec::new(); + for id in ids { + self.dirty.remove(&id); + if self.pages.remove(&id).is_some() { + dropped.push(id); + } + self.released.insert(id); + } + dropped + } + + /// Page `page_id` for export: a released page is all zeros, any other + /// absent page is an error. + pub fn export_page(&self, page_id: u64) -> Result> { + if !self.pages.contains_key(&page_id) && self.released.contains(&page_id) { + return Ok(vec![0u8; PAGE_SIZE]); + } + self.read_page(page_id) + } + + /// The ids of the pages holding bytes. + pub fn page_ids(&self) -> impl Iterator + '_ { + self.pages.keys().copied() + } + + /// The number of pages holding bytes. + pub fn stored_page_count(&self) -> usize { + self.pages.len() + } + /// Mark `page_id` dirty without writing it, for tests of the flush path. #[cfg(test)] pub(crate) fn mark_dirty_for_test(&mut self, page_id: u64) { @@ -76,6 +123,7 @@ impl StorageBackend for BrowserBufferBackend { } self.pages.insert(page_id, data.to_vec()); self.dirty.insert(page_id); + self.released.remove(&page_id); Ok(()) } @@ -178,6 +226,43 @@ mod tests { assert!(buf.write_page(0, &[0u8; 100]).is_err()); } + #[wasm_bindgen_test] + fn release_drops_bytes_and_dirty_and_reports_stored_ids() { + let mut buf = BrowserBufferBackend::load_pages(HashMap::from([(2u64, page(2))])); + buf.write_page(3, &page(3)).unwrap(); + let mut dropped = buf.release([2, 3, 4]); + dropped.sort_unstable(); + assert_eq!(dropped, vec![2, 3], "page 4 held no bytes"); + assert!( + buf.take_dirty().is_empty(), + "a released write is not flushed" + ); + assert!(buf.read_page(2).is_err(), "a released page reads as absent"); + assert_eq!(buf.stored_page_count(), 0); + assert!( + buf.release([2]).is_empty(), + "releasing twice deletes nothing" + ); + } + + #[wasm_bindgen_test] + fn export_page_zeroes_released_pages_only() { + let mut buf = BrowserBufferBackend::new(); + buf.write_page(2, &page(9)).unwrap(); + let _ = buf.release([2]); + assert_eq!(buf.export_page(2).unwrap(), page(0)); + assert!( + buf.export_page(5).is_err(), + "an absent page that is not free" + ); + buf.write_page(2, &page(7)).unwrap(); + assert_eq!( + buf.export_page(2).unwrap(), + page(7), + "rewritten after reuse" + ); + } + #[wasm_bindgen_test] fn read_missing_page_errors() { let buf = BrowserBufferBackend::new(); diff --git a/src/browser/indexeddb.rs b/src/browser/indexeddb.rs index 428b27440..e134462a1 100644 --- a/src/browser/indexeddb.rs +++ b/src/browser/indexeddb.rs @@ -142,15 +142,22 @@ impl IndexedDbBackend { } } - /// Write a batch of pages to IndexedDB in a single `readwrite` transaction. + /// Write a batch of pages and delete a batch of page keys in a single + /// `readwrite` transaction. /// - /// All `put` operations are queued synchronously on the store, then we wait - /// for the transaction's `oncomplete` event. If any put fails, the transaction - /// is aborted and an error is returned. + /// All requests are queued synchronously on the store, then we wait for the + /// transaction's `oncomplete` event. If any request fails, the transaction + /// is aborted and an error is returned, so the pages of a commit, its meta + /// page and the keys of the pages it freed land together or not at all. /// - /// `pages` is a list of `(page_id, page_bytes)` pairs. Empty input is a no-op. - pub async fn write_pages(&self, pages: Vec<(u64, Vec)>) -> Result<(), JsValue> { - if pages.is_empty() { + /// `pages` is a list of `(page_id, page_bytes)` pairs; `deletes` is a list + /// of page ids. Both empty is a no-op. + pub async fn write_pages( + &self, + pages: Vec<(u64, Vec)>, + deletes: Vec, + ) -> Result<(), JsValue> { + if pages.is_empty() && deletes.is_empty() { return Ok(()); } let tx = self @@ -158,6 +165,9 @@ impl IndexedDbBackend { .transaction_with_str_and_mode(&self.store_name, IdbTransactionMode::Readwrite)?; let store = tx.object_store(&self.store_name)?; + for page_id in &deletes { + store.delete(&JsValue::from_f64(*page_id as f64))?; + } for (page_id, data) in &pages { let key = JsValue::from_f64(*page_id as f64); let arr = Uint8Array::from(data.as_slice()); @@ -165,8 +175,8 @@ impl IndexedDbBackend { } // Wait for the transaction to commit. The IDB transaction commits - // automatically once all put requests have been processed and no - // new requests are made. We wait here to ensure durability before + // automatically once all requests have been processed and no new + // requests are made. We wait here to ensure durability before // returning to the caller. JsFuture::from(transaction_to_promise(&tx)).await?; Ok(()) diff --git a/src/browser/mod.rs b/src/browser/mod.rs index 8462facc8..216bbd3ff 100644 --- a/src/browser/mod.rs +++ b/src/browser/mod.rs @@ -80,10 +80,18 @@ impl BrowserDb { let buffer = BrowserBufferBackend::load_pages(existing); // Page cache capacity 0 — see comment in `open_in_memory` above. - let pfs = + let mut pfs = PersistentFactStorage::new(buffer, 0).map_err(|e| JsValue::from_str(&e.to_string()))?; let fact_storage = pfs.storage().clone(); + // Opening may have written pages: a v7 store is migrated to v8 (#411). + // Store them, and drop the free pages (after a migration, the whole v7 + // region) from memory and from IndexedDB (#440). A v8 store with no + // free page bytes left writes nothing. + let free = pfs.free_page_ids().map_err(to_js_error)?; + let flush = take_flush(&mut pfs, free)?; + idb.write_pages(flush.puts, flush.deletes).await?; + Ok(BrowserDb { inner: Rc::new(RefCell::new(BrowserDbInner { fact_storage, @@ -161,23 +169,21 @@ impl BrowserDb { /// so `checkpoint()` is only needed after `import_graph()` or explicit bulk ops. /// No-op for in-memory databases. pub async fn checkpoint(&self) -> Result<(), JsValue> { - let (dirty_pages, idb) = { + let (flush, idb) = { let mut inner = self.inner.borrow_mut(); inner .pfs .save() .map_err(|e| JsValue::from_str(&e.to_string()))?; - let pages = take_dirty_pages(&mut inner.pfs)?; + let released = inner.pfs.take_released(); ( - pages, + take_flush(&mut inner.pfs, released)?, inner.idb.as_ref().map(IndexedDbBackend::clone_handle), ) }; - if let Some(idb) = idb - && !dirty_pages.is_empty() - { - idb.write_pages(dirty_pages).await?; + if let Some(idb) = idb { + idb.write_pages(flush.puts, flush.deletes).await?; } Ok(()) } @@ -185,17 +191,21 @@ impl BrowserDb { /// Serialise the current database to a portable `.graph` blob. /// /// The blob is byte-for-bit compatible with native `.graph` files opened by - /// `Minigraf::open()`. Pages are always in ascending `page_id` order. + /// `Minigraf::open()`. Pages are always in ascending `page_id` order. Free + /// pages are written as zeros. /// /// Call `checkpoint()` on native before importing a file here to ensure /// no WAL entries are missing from the main file. #[wasm_bindgen(js_name = exportGraph)] pub fn export_graph(&self) -> Result { let inner = self.inner.borrow(); + // Free pages hold no bytes (#440), so the trailing ones may be absent: + // the file is as long as the meta says. let page_count = inner .pfs .with_backend(|b| b.page_count_raw()) - .map_err(|e| JsValue::from_str(&e.to_string()))?; + .map_err(|e| JsValue::from_str(&e.to_string()))? + .max(inner.pfs.committed_page_count()); let capacity = usize::try_from(page_count) .ok() .and_then(|n| n.checked_mul(crate::storage::PAGE_SIZE)) @@ -205,7 +215,7 @@ impl BrowserDb { for id in 0..page_count { let page = inner .pfs - .with_backend(|b| b.read_page_raw(id)) + .with_backend(|b| b.export_page(id)) .map_err(|e| JsValue::from_str(&e.to_string()))?; blob.extend_from_slice(&page); } @@ -232,7 +242,7 @@ impl BrowserDb { } // ── Sync section ────────────────────────────────────────────────────────── - let (dirty_pages, idb) = { + let (flush, idb) = { let mut inner = self.inner.borrow_mut(); let buffer = BrowserBufferBackend::load_pages_all_dirty(pages); // Page cache capacity 0 — see comment in `open_in_memory` above. @@ -240,23 +250,33 @@ impl BrowserDb { .map_err(|e| JsValue::from_str(&e.to_string()))?; let new_fact_storage = new_pfs.storage().clone(); - // Drain dirty set and collect owned page bytes before swapping inner. - let dirty_pages = take_dirty_pages(&mut new_pfs)?; + // Drain dirty set and collect owned page bytes before swapping + // inner, leaving out the free pages (#440). + let free = new_pfs.free_page_ids().map_err(to_js_error)?; + let mut flush = take_flush(&mut new_pfs, free)?; + // Every page of the old database the new one does not hold must go + // too, or a reopen would load it next to the imported pages. + let new_ids: std::collections::HashSet = + new_pfs.with_backend(|b| b.page_ids().collect()); + let stale: Vec = inner + .pfs + .with_backend(|b| b.page_ids().filter(|id| !new_ids.contains(id)).collect()); + flush.deletes.extend(stale); + flush.deletes.sort_unstable(); + flush.deletes.dedup(); inner.pfs = new_pfs; inner.fact_storage = new_fact_storage; ( - dirty_pages, + flush, inner.idb.as_ref().map(IndexedDbBackend::clone_handle), ) }; // ── Borrow dropped ──────────────────────────────────────────────────────── - if let Some(idb) = idb - && !dirty_pages.is_empty() - { - idb.write_pages(dirty_pages).await?; + if let Some(idb) = idb { + idb.write_pages(flush.puts, flush.deletes).await?; } Ok(()) } @@ -299,7 +319,7 @@ impl BrowserDb { use crate::graph::types::tx_id_now; // ── Sync section: hold borrow, do ALL sync work, collect owned data ── - let (dirty_pages, result_json) = { + let (flush, result_json) = { let mut inner = self.inner.borrow_mut(); // Before allocating: a rejected transaction takes no tx_count (#435). @@ -333,8 +353,10 @@ impl BrowserDb { .save() .map_err(|e| JsValue::from_str(&e.to_string()))?; - // Collect dirty pages as owned Vec<(u64, Vec)> — no borrows escape - let dirty_pages = take_dirty_pages(&mut inner.pfs)?; + // Collect dirty pages as owned Vec<(u64, Vec)> — no borrows + // escape — and drop the pages this commit freed (#440). + let released = inner.pfs.take_released(); + let flush = take_flush(&mut inner.pfs, released)?; let json = if is_retract { format!(r#"{{"retracted":{}}}"#, tx_id) @@ -342,7 +364,7 @@ impl BrowserDb { format!(r#"{{"transacted":{}}}"#, tx_id) }; - (dirty_pages, json) + (flush, json) }; // ── Borrow dropped here ─────────────────────────────────────────────── @@ -353,10 +375,8 @@ impl BrowserDb { .idb .as_ref() .map(IndexedDbBackend::clone_handle); - if let Some(idb) = idb - && !dirty_pages.is_empty() - { - idb.write_pages(dirty_pages).await?; + if let Some(idb) = idb { + idb.write_pages(flush.puts, flush.deletes).await?; } Ok(result_json) @@ -428,6 +448,25 @@ fn take_dirty_pages( .map_err(to_js_error) } +/// What one commit sends to IndexedDB, in one transaction: the pages it wrote +/// (its meta page among them) and the keys of the free pages it dropped. +struct Flush { + puts: Vec<(u64, Vec)>, + deletes: Vec, +} + +/// Drop the bytes of the free pages `free` (#440), then take the dirty pages. +/// A free page is never read before it is written again, so its bytes are +/// never needed. +fn take_flush( + pfs: &mut PersistentFactStorage, + free: Vec, +) -> Result { + let deletes = pfs.with_backend_mut(|b| b.release(free)); + let puts = take_dirty_pages(pfs)?; + Ok(Flush { puts, deletes }) +} + fn to_js_error(e: anyhow::Error) -> JsValue { JsValue::from_str(&crate::MinigrafError::from(e).to_string()) } @@ -746,4 +785,236 @@ mod tests { assert_eq!(results.len(), 1); assert_eq!(results[0][0], serde_json::Value::String("eng".into())); } + // ── #411 / #440: migrated pages are stored, free pages hold no bytes ── + + /// Open `name` with its object store emptied, so earlier runs leave nothing. + async fn empty_store(name: &str) -> IndexedDbBackend { + let idb = IndexedDbBackend::open(name).await.expect("idb open"); + let keys: Vec = idb + .load_all_pages() + .await + .expect("load") + .into_keys() + .collect(); + idb.write_pages(Vec::new(), keys).await.expect("clear"); + idb + } + + /// Pages the active meta does not list as free: the only ones that should + /// hold bytes. + fn live_pages(db: &BrowserDb) -> usize { + let m = db.inner.borrow().pfs.meta(); + usize::try_from(m.page_count - m.freelist_count).unwrap() + } + + fn stored_pages(db: &BrowserDb) -> usize { + db.inner + .borrow() + .pfs + .with_backend(BrowserBufferBackend::stored_page_count) + } + + async fn idb_keys(name: &str) -> std::collections::HashMap> { + IndexedDbBackend::open(name) + .await + .expect("idb open") + .load_all_pages() + .await + .expect("load") + } + + async fn count(db: &BrowserDb, q: &str) -> usize { + let r = db.execute(q.to_string()).await.expect("query"); + let v: serde_json::Value = serde_json::from_str(&r).unwrap(); + v["results"].as_array().unwrap().len() + } + + #[wasm_bindgen_test] + async fn open_stores_migrated_v7_pages_and_drops_the_v7_region() { + let name = "minigraf-test-411-migrate"; + let fixture: &[u8] = include_bytes!("../../tests/fixtures/compat.graph"); + let v7_pages: Vec<(u64, Vec)> = fixture + .chunks(crate::storage::PAGE_SIZE) + .enumerate() + .map(|(i, c)| (i as u64, c.to_vec())) + .collect(); + let idb = empty_store(name).await; + idb.write_pages(v7_pages, Vec::new()) + .await + .expect("seed v7"); + + let db = BrowserDb::open(name).await.expect("open v7 store"); + assert_eq!( + count(&db, "(query [:find ?n :where [?e :name ?n]])").await, + 1, + "fixture fact readable" + ); + + let stored = idb_keys(name).await; + let page0 = stored.get(&0).expect("page 0 stored"); + assert_eq!(&page0[0..4], b"MGRF"); + assert_eq!(u32::from_le_bytes(page0[4..8].try_into().unwrap()), 8); + assert_eq!(&page0[8..12], b"META", "page 0 is a v8 meta in IndexedDB"); + let m = db.inner.borrow().pfs.meta(); + assert!(m.freelist_count > 0, "the v7 region is free"); + assert_eq!( + stored.len(), + live_pages(&db), + "IndexedDB holds live pages only" + ); + assert_eq!( + stored_pages(&db), + live_pages(&db), + "memory holds live pages only" + ); + drop(db); + + // The store is v8 now: reopening migrates nothing and writes nothing. + let db = BrowserDb::open(name).await.expect("reopen"); + assert_eq!(db.inner.borrow().pfs.meta().generation, m.generation); + assert_eq!(idb_keys(name).await.len(), stored.len()); + assert_eq!( + count(&db, "(query [:find ?a :where [?e :age ?a]])").await, + 1, + "fixture fact readable after reopen" + ); + } + + #[wasm_bindgen_test] + async fn transacts_keep_only_live_pages() { + let name = "minigraf-test-440-churn"; + let _ = empty_store(name).await; + let db = BrowserDb::open(name).await.expect("open"); + let mut high_water = Vec::new(); + for i in 0..60 { + db.execute(format!(r#"(transact [[:e{i} :n {i}] [:e{i} :s "v{i}"]])"#)) + .await + .expect("transact"); + assert_eq!(stored_pages(&db), live_pages(&db), "memory after tx {i}"); + high_water.push(db.inner.borrow().pfs.meta().page_count); + } + assert_eq!(idb_keys(name).await.len(), live_pages(&db), "IndexedDB"); + // Without reuse each commit abandons a path in all five trees, so the + // file would grow by several pages per transact. With reuse the last + // 30 transacts grow it by far less than one page each. + let grown = high_water[59] - high_water[29]; + assert!(grown < 30, "page_count grew by {grown} over 30 transacts"); + + drop(db); + let db = BrowserDb::open(name).await.expect("reopen"); + assert_eq!(count(&db, "(query [:find ?n :where [?e :n ?n]])").await, 60); + assert_eq!(stored_pages(&db), live_pages(&db), "memory after reopen"); + } + + #[wasm_bindgen_test] + async fn unflushed_commit_reopens_at_the_previous_one() { + let name = "minigraf-test-440-unflushed"; + let _ = empty_store(name).await; + let db = BrowserDb::open(name).await.expect("open"); + for i in 0..5 { + db.execute(format!("(transact [[:a{i} :n {i}]])")) + .await + .expect("transact"); + } + // A commit that reaches the buffer but never IndexedDB, as when the tab + // closes before the flush: its writes and its deletes are both lost. + { + let mut inner = db.inner.borrow_mut(); + let cmd = parse_datalog_command("(transact [[:lost :n 99]])").unwrap(); + let DatalogCommand::Transact(tx) = cmd else { + panic!("transact") + }; + let tx_count = inner.fact_storage.allocate_tx_count(); + for mut f in crate::db::Minigraf::materialize_transaction(&tx).unwrap() { + f.tx_count = tx_count; + f.tx_id = crate::graph::types::tx_id_now(); + f.valid_from = f.tx_id.cast_signed(); + inner.fact_storage.load_fact(f).unwrap(); + } + inner.pfs.mark_dirty(); + inner.pfs.save().unwrap(); + let released = inner.pfs.take_released(); + let flush = take_flush(&mut inner.pfs, released).unwrap(); + assert!(!flush.puts.is_empty(), "the commit wrote pages"); + } + drop(db); + + let db = BrowserDb::open(name).await.expect("reopen"); + assert_eq!(count(&db, "(query [:find ?n :where [?e :n ?n]])").await, 5); + assert_eq!(stored_pages(&db), live_pages(&db)); + db.execute("(transact [[:b :n 7]])".to_string()) + .await + .expect("transact after reopen"); + assert_eq!(count(&db, "(query [:find ?n :where [?e :n ?n]])").await, 6); + assert_eq!(idb_keys(name).await.len(), live_pages(&db)); + } + + #[wasm_bindgen_test] + async fn export_after_churn_pads_free_pages_and_imports_back() { + let db = BrowserDb::open_in_memory().expect("open"); + for i in 0..30 { + db.execute(format!("(transact [[:e{i} :n {i}]])")) + .await + .expect("transact"); + } + let m = db.inner.borrow().pfs.meta(); + assert!(m.freelist_count > 0, "churn left free pages"); + assert_eq!(stored_pages(&db), live_pages(&db)); + let bytes = db.export_graph().expect("export").to_vec(); + assert_eq!( + bytes.len(), + usize::try_from(m.page_count).unwrap() * crate::storage::PAGE_SIZE + ); + + let db2 = BrowserDb::open_in_memory().expect("open2"); + db2.import_graph(js_sys::Uint8Array::from(bytes.as_slice())) + .await + .expect("import"); + assert_eq!( + count(&db2, "(query [:find ?n :where [?e :n ?n]])").await, + 30 + ); + assert_eq!( + stored_pages(&db2), + live_pages(&db2), + "import drops free pages" + ); + db2.execute("(transact [[:x :n 100]])".to_string()) + .await + .expect("transact after import"); + assert_eq!( + count(&db2, "(query [:find ?n :where [?e :n ?n]])").await, + 31 + ); + } + + #[wasm_bindgen_test] + async fn import_deletes_the_old_databases_pages() { + let name = "minigraf-test-440-import"; + let _ = empty_store(name).await; + let small = BrowserDb::open_in_memory().expect("small"); + small + .execute(r#"(transact [[:only :n 1]])"#.to_string()) + .await + .expect("transact"); + let blob = small.export_graph().expect("export"); + + let db = BrowserDb::open(name).await.expect("open"); + for i in 0..40 { + let long = "x".repeat(200 + i); + db.execute(format!(r#"(transact [[:e{i} :s "{long}"]])"#)) + .await + .expect("transact"); + } + let before = idb_keys(name).await.len(); + db.import_graph(blob).await.expect("import"); + let after = idb_keys(name).await; + assert!(after.len() < before, "the old pages are gone"); + assert_eq!(after.len(), stored_pages(&db), "IndexedDB matches memory"); + drop(db); + + let db = BrowserDb::open(name).await.expect("reopen"); + assert_eq!(count(&db, "(query [:find ?n :where [?e :n ?n]])").await, 1); + assert_eq!(count(&db, "(query [:find ?s :where [?e :s ?s]])").await, 0); + } } diff --git a/src/storage/freelist.rs b/src/storage/freelist.rs index 94a5cd1cb..2578dd467 100644 --- a/src/storage/freelist.rs +++ b/src/storage/freelist.rs @@ -208,7 +208,7 @@ mod tests { let handed: Vec = (0..take) .map(|_| alloc.alloc(&backend, &cache).unwrap()) .collect(); - let (new_head, count) = alloc + let (new_head, count, listed) = alloc .finish_free_list(freed.clone(), &mut backend, &cache) .unwrap(); let (new_ids, new_chain) = @@ -233,6 +233,16 @@ mod tests { let after: BTreeSet = h.union(&ni).chain(nc.iter()).copied().collect(); let expected: BTreeSet = before.union(&appended).copied().collect(); assert!(after == expected, "every page is accounted for"); + // `listed` is the new head: every freed page, and nothing but ids that + // were already free besides (the unread tail is the rest). + let l = set(&listed); + assert_eq!(l.len(), listed.len(), "no duplicate listed id"); + assert!(l.is_subset(&ni), "listed ids are on the new free list"); + assert!(set(&freed).is_subset(&l), "every freed page is listed"); + assert!( + ni.difference(&l).all(|id| old_ids.contains(id)), + "only the unread tail is left out" + ); // Chain pages never read are shared unchanged (same ids, generation 1). let read_pages = take.div_ceil(IDS_PER_PAGE).max(usize::from(take > 0)); for &id in old_chain.iter().skip(read_pages + 1) { @@ -269,10 +279,11 @@ mod tests { let (head, chain) = write_chain(&ids, &mut a1, &mut backend, &cache).unwrap(); // No allocation and nothing freed: the list is unchanged. let mut alloc = PageAllocator::from_chain(head, 3000, a1.next_append(), 2); - let (h, count) = alloc + let (h, count, listed) = alloc .finish_free_list(Vec::new(), &mut backend, &cache) .unwrap(); assert_eq!((h, count), (head, 3000)); + assert!(listed.is_empty(), "nothing newly listed"); assert_eq!(alloc.next_append(), a1.next_append(), "nothing written"); assert_eq!(chain.len(), 6); } diff --git a/src/storage/page.rs b/src/storage/page.rs index c60b3d2ae..9b3ef9512 100644 --- a/src/storage/page.rs +++ b/src/storage/page.rs @@ -272,7 +272,9 @@ impl PageAllocator { v } - /// Write the new free list and return `(head, count)`. + /// Write the new free list and return `(head, count, listed)`, where + /// `listed` holds the ids in the new head pages (everything but the unread + /// tail). /// /// The list is `freed` (pages the new meta no longer references), every /// chain page read and the ids read but not handed out, as new head pages in @@ -284,7 +286,7 @@ impl PageAllocator { freed: Vec, backend: &mut dyn crate::storage::StorageBackend, cache: &crate::storage::cache::PageCache, - ) -> Result<(u64, u64)> { + ) -> Result<(u64, u64, Vec)> { use crate::storage::freelist::IDS_PER_PAGE; let mut pages: Vec = Vec::new(); let ids = loop { @@ -312,7 +314,7 @@ impl PageAllocator { .checked_add(u64::try_from(ids.len()).unwrap_or(u64::MAX)) .ok_or_else(|| err_coded!(ErrorCode::Int048, "free-list count overflow"))?; crate::storage::freelist::write_pages(&ids, &pages, tail, self, backend, cache)?; - Ok((pages.first().copied().unwrap_or(tail), count)) + Ok((pages.first().copied().unwrap_or(tail), count, ids)) } /// Seal `page` as `page_id` in this generation, write it, and put it in the diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index d8fe958cc..95f4a9ad1 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -40,6 +40,10 @@ pub struct PersistentFactStorage { dirty: bool, /// The active (last committed) meta page. meta: MetaPage, + /// Ids the last `save()` put on the free list, for the browser layer to + /// drop (#440). The rest of the list was released by an earlier commit. + #[cfg(all(target_arch = "wasm32", feature = "browser"))] + released: Vec, } /// Page cache size for the integrity walk: enough to keep a value page hot @@ -127,6 +131,8 @@ impl PersistentFactStorage { storage: FactStorage::new(), dirty: false, meta: MetaPage::empty(1), + #[cfg(all(target_arch = "wasm32", feature = "browser"))] + released: Vec::new(), } } @@ -408,7 +414,7 @@ impl PersistentFactStorage { )?; } let [eavt_root, aevt_root, avet_root, vaet_root, dict_root] = roots; - let (freelist_head, freelist_count) = + let (freelist_head, freelist_count, listed) = alloc.finish_free_list(freed, &mut *backend, &self.page_cache)?; backend.sync()?; @@ -438,6 +444,12 @@ impl PersistentFactStorage { self.dirty = false; self.activate(new_meta); + #[cfg(all(target_arch = "wasm32", feature = "browser"))] + { + self.released = listed; + } + #[cfg(not(all(target_arch = "wasm32", feature = "browser")))] + drop(listed); // Clear pending — all data now on disk self.storage.post_checkpoint_clear(); Ok(()) @@ -1413,6 +1425,50 @@ mod tests { ); } + /// Overwrite every page on `m`'s free list with zeros. + fn zero_free_pages(m: &MetaPage, mem: &mut MemoryBackend) { + if m.freelist_head == 0 { + return; + } + let (free, _) = + freelist::read_chain(m.freelist_head, &*mem, &PageCache::new(0), m.page_count).unwrap(); + for id in free { + mem.write_page(id, &[0u8; PAGE_SIZE]).unwrap(); + } + } + + /// The browser drops the bytes of free pages and exports them as zeros + /// (#440). That is only sound if nothing reads a free page before writing + /// it: a file whose free pages are zeros must open, verify clean and keep + /// committing. Covers the migrated generation-1 file (one valid meta slot, + /// so open probes the free pages) and a file after many saves. + #[test] + fn zeroed_free_pages_are_never_read() { + let mut mem = v7_file(&sample_facts(300), 300); + let pfs = open_mem(&mem, None).unwrap(); + let migrated = pfs.meta(); + drop(pfs); + zero_free_pages(&migrated, &mut mem); + let mut pfs = open_mem(&mem, None).unwrap(); + assert_eq!(pfs.meta().generation, 1, "reopens at the migration commit"); + assert_eq!(count_n(&pfs), 300); + assert!(pfs.verify().unwrap().problems.is_empty(), "migrated file"); + + let mut next_entity = 1000; + for round in 0..20u64 { + transact_mixed(&mut pfs, &mut next_entity, 10, round); + pfs.save().unwrap(); + zero_free_pages(&pfs.meta(), &mut mem); + } + let expected = pfs.storage().get_all_facts().unwrap().len(); + drop(pfs); + let pfs = open_mem(&mem, None).unwrap(); + assert_eq!(pfs.storage().get_all_facts().unwrap().len(), expected); + assert!(pfs.verify().unwrap().problems.is_empty(), "after saves"); + assert_space_accounted(&pfs.meta(), &mem); + assert_indexes_exact(&pfs.meta(), &mem); + } + #[test] fn crash_at_every_point_of_migration_keeps_every_fact() { let facts = sample_facts(120); diff --git a/src/storage/persistent_facts/browser_access.rs b/src/storage/persistent_facts/browser_access.rs index 18ed1a86a..a5b3242d2 100644 --- a/src/storage/persistent_facts/browser_access.rs +++ b/src/storage/persistent_facts/browser_access.rs @@ -3,7 +3,8 @@ //! `browser` feature. use super::PersistentFactStorage; -use crate::storage::StorageBackend; +use crate::storage::{StorageBackend, freelist}; +use anyhow::Result; impl PersistentFactStorage { /// Run a closure with read access to the underlying storage backend. @@ -35,4 +36,32 @@ impl PersistentFactStorage { .unwrap_or_else(std::sync::PoisonError::into_inner); f(&mut *guard) } + + /// The ids the last `save()` put on the free list, clearing the record. + /// Pages already free before that commit are not repeated (#440). + pub(crate) fn take_released(&mut self) -> Vec { + std::mem::take(&mut self.released) + } + + /// Every id on the active meta's free list, read from its chain. Used once + /// at open; after that, [`take_released`](Self::take_released) gives the + /// change per commit. + pub(crate) fn free_page_ids(&self) -> Result> { + if self.meta.freelist_head == 0 { + return Ok(Vec::new()); + } + let backend = self.lock()?; + let (ids, _) = freelist::read_chain( + self.meta.freelist_head, + &*backend, + &self.page_cache, + self.meta.page_count, + )?; + Ok(ids) + } + + /// The active meta's `page_count`: the length of the file it describes. + pub(crate) fn committed_page_count(&self) -> u64 { + self.meta.page_count + } }