8000 feat(storage): v8 page format — meta pages, verified page headers, atomic save (v8 PR 2, refs #374 #388) by adityamukho · Pull Request #444 · project-minigraf/minigraf · GitHub
[go: up one dir, main page]
Skip to content

feat(storage): v8 page format — meta pages, verified page headers, atomic save (v8 PR 2, refs #374 #388) - #444

Merged
adityamukho merged 3 commits into
v3from
feat/v8-pr2-page-format
Oct 6, 2026
Merged

feat(storage): v8 page format — meta pages, verified page headers, atomic save (v8 PR 2, refs #374 #388)#444
adityamukho merged 3 commits into
v3from
feat/v8-pr2-page-format

Conversation

@adityamukho
@adityamukho adityamukho commented Oct 5, 2026 •
edited
Loading
Copy link
Copy Markdown
Collaborator

PR 2 of 5 for the v8 storage format (spec: docs/superpowers/specs/2026-10-05-v8-storage-format-design.md; plan: docs/superpowers/plans/2026-10-05-v8-storage-format.md, PR 2 section).

What changes

  • Common 24-byte page header on every non-meta page: type, count, CRC32, page id, generation. The page cache verifies it on every load. A failure returns STG-029 (CRC), STG-030 (page id) or STG-031 (generation ahead of meta), and the page is never cached. Legacy or unknown page types fail with STG-013 before the CRC is computed.
  • Two alternating meta pages (odd generations in page 0, even in page 1) replace the 84-byte header and are the only commit point. save() writes only pages the active meta does not reference (its free list first, then appended), syncs, writes the other meta page and syncs again. The whole-file index checksum, fact_prefix_crc and the rebuild-on-open path are removed.
  • Meta selection on open follows spec §4.1.1. It uses the new WAL v2 base_generation, and searches for pages of the next generation on the free list and past page_count. If a later commit existed, open fails with STG-033 instead of rolling back silently. Unknown feature bits fail with STG-034. A file with no valid meta fails with STG-032; one with no magic still gets STG-002.
  • Free list (0x81 page chain). In this PR it is rewritten in full on every save; PR 4 makes push and pop O(change). The on-disk format is already final.
  • v7 migration moved here from PR 3, because page 0 changes in this PR. It follows §9: everything is appended past the v7 pages, the old pages go on the free list, a backup meta is written as the last page, and the commit goes through page 0. A torn page-0 write is repaired from the backup on the next open.
  • FileBackend is format-agnostic. The page count comes from the file length, and it no longer parses or rewrites page 0 on every append. is_new is removed from StorageBackend.
  • Fact pages stay until PR 3, under the interim type 0x41 with the new header. They are append-only, so stream_all keeps insertion order.

Bug found and fixed

An index key can be nearly as large as its fact (key ≤ fact − 1), and an internal node needs room for one separator beside the header and child pointers. With the larger header, a maximum-size value overflowed an internal node silently: max_size_value_at_exact_boundary_checkpoint_and_read_back returned 1 of 2 facts. Fixes:

  • MAX_FACT_BYTES is now 4052 (was 4080).
  • The leaf and internal encoders reject overflow instead of writing an overlapping page.
  • Two regression tests cover this.

v2.x is not affected. Its index keys have no value bytes, and the parser caps attribute keywords at 1,024 bytes, so its keys stay far below the internal-node limit. I checked this end-to-end on main. The overflow became possible only when the v3 branch added value bytes to keys (#287) and was never released.

Tests

1,225 passing, 8 ignored.

  • Page header, meta pages, free-list chain and WAL v2: unit tests for each.
  • Meta selection: one test per row of the §4.1.1 table, including the free-list and past-page_count evidence cases. Each failed open is checked to leave the file unmodified.
  • Crash atomicity:
    • Saves: a crash at every page write (clean, and torn at 0/512/4095 bytes, including the meta write) and at every sync. Each reopen sees exactly the old or the new checkpoint, and the reachable pages plus the free list cover the file exactly.
    • v7 migration: a crash at every write, clean and torn.
  • Write guard: 25 consecutive saves never write a page the previous meta references.

Performance

  • Point lookups and attribute scans: unchanged.
  • checkpoint/after_1_fact: 10k from about 3.7 ms to about 11.5 ms; 100k from about 33 ms to about 63 ms. Every save now frees all old tree pages and rewrites the whole free-list chain. This interim cost goes away in PR 4 (copy-on-write insert, O(change) free list).

Not covered

  • The browser flush already writes every dirty page, including the meta page, in one IndexedDB transaction. There is no wasm test for it yet.
  • .wiki/Architecture.md and the size and cost benchmarks are in PR 5.

Refs #374 #388 #434

🤖 Generated with Claude Code

https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn

adityamukho and others added 3 commits October 5, 2026 23:24
@adityamukho @claude
docs(v8): detailed PR 2 plan; spec fixes for meta slot mapping and in…
c64a6a0 
…terim fact pages

The meta slot formula is (generation - 1) % 2 so generation 1 lands in
page 0, matching the migration section. New files get an empty
generation-1 meta. v7 migration moves into PR 2 because PR 2 replaces
page 0.

Refs #374 #388 #434

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho @claude
feat(storage): v8 page format with meta pages, verified page headers …
e0f6a89 
…and atomic save

Every non-meta page now carries a 24-byte header (type, count, CRC32,
page id, generation) that the page cache verifies on every load.
Two alternating meta pages are the only commit point: save() writes
only pages the active meta does not reference (its free list first,
then appended), syncs, then writes the other meta slot and syncs.
A crash or torn write at any point leaves the previous checkpoint
intact, so the index checksum and the rebuild-on-open path are gone.

- Meta selection on open per spec 4.1.1, using the new WAL v2
  base_generation and a search for pages of the next generation.
- Free list (0x81 pages), rewritten in full each save for now.
- v7 migration appends the new layout and commits through page 0
  with a backup meta in the last page.
- FileBackend no longer parses page 0; page count is the file length.
- MAX_FACT_BYTES is 4052 so every index key fits in an internal node;
  page encoders now reject overflow instead of corrupting the page.
- New codes STG-029..STG-035.

Refs #374 #388 #434

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho @claude
docs(v8): changelog, test coverage and file-format notes for PR 2
4cca5b0 
Also refine the spec's meta-selection table: a WAL whose base generation
is at or below the valid meta's means open there and replay, and a
v2.x (version 1) WAL reads as base generation 1. INT-053 stays in use
for a damaged v7 header.

Refs #374 #388 #434

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@codecov
codecov Bot commented Oct 5, 2026
Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 96.19565% with 14 lines in your changes missing coverage. Please review.

Files with missing lines Patch % Lines
src/storage/mod.rs 77.77% 6 Missing ⚠️
src/storage/btree_v6.rs 93.18% 3 Missing ⚠️
src/storage/freelist.rs 95.83% 2 Missing ⚠️
src/storage/backend/file.rs 87.50% 1 Missing ⚠️
src/storage/meta.rs 98.90% 1 Missing ⚠️
src/storage/page.rs 98.87% 1 Missing ⚠️

📢 Thoughts on this report? Let us know!

@adityamukho
adityamukho merged commit 75bd970 into v3 Oct 6, 2026
26 of 32 checks passed
@adityamukho
adityamukho deleted the feat/v8-pr2-page-format branch October 6, 2026 02:10
This was referenced Oct 6, 2026
Closed
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

1 participant

@adityamukho
0