lib/machine/src/checkpoint/roots/root.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 //! Holding one capture is easy, and holding fifty is the problem the calls here
  2 //! solve: the calls write captures into a store the caller supplies and read
  3 //! them back.
  4 //!
  5 //! A caller keeping many captures pays a full memory image for each one unless
  6 //! the captures share the pages they hold in common. The machine's fixed
  7 //! 67,108,864 bytes, addressed from zero, holding 16,384 pages, are its
  8 //! *memory*. The 4096 contiguous bytes of a machine's memory, named by their
  9 //! zero-based index, are a *page*.
 10 //!
 11 //! A store outside the process can hand back the wrong bytes, so a reader has
 12 //! to check each object it receives. A publication interrupted part way would
 13 //! leave a root pointing at objects that were never written. Captures
 14 //! accumulate, so something has to remove the objects nobody reaches without
 15 //! removing the ones a reader still holds.
 16 //!
 17 //! A content-addressed object store keys each object by the digest of its bytes
 18 //! and shares the subtrees two versions have in common, as Git does for its
 19 //! trees. Mark and sweep reclaims storage by marking everything reachable from
 20 //! a set of roots and then removing the rest (McCarthy, 1960).
 21 //!
 22 //! The complete binary tree over the 16,384 page digests, 14 levels deep, where
 23 //! each node binds its level to its two ordered child digests, is a *page
 24 //! tree*. The digest identifying a complete page tree held as stored objects is
 25 //! the *page root*. Pages, tree nodes, and manifests are all written under
 26 //! their digests, and a capture against a parent restages only the changed
 27 //! pages and the tree paths above them. The caller-supplied content-addressed
 28 //! store that owns every stored byte and answers reads and writes by digest is
 29 //! the *provider*. One manifest root the provider reports as owned at the
 30 //! moment collection opens is a *seed*. Marking every object reachable from the
 31 //! provider's snapshotted seeds, then one atomic sweep that removes the
 32 //! unmarked, is a *collection*.
 33 //!
 34 //! One page, one page-tree node, or one manifest, each written under its digest
 35 //! at the exact byte length its kind fixes: 4096, 80, or 4352, is a *stored
 36 //! object*. Every stored object fixes its byte length, so a read knows its
 37 //! length before it asks.
 38 //!
 39 //! The digest binding one profile fingerprint to one state digest is the
 40 //! *checkpoint root*. The SHA-256 identity of a normalized memory image,
 41 //! binding the page tree's root to the fixed memory geometry, is the *memory
 42 //! digest*. A generation and digest naming the stored data an execution read is
 43 //! a *block root*. The fixed-size values needed to recompute an identity and
 44 //! rebuild execution: profile fingerprint, settled receipt, CPU restart frame,
 45 //! and immutable image descriptor, are the restore *material*. The stored
 46 //! record joining a checkpoint root, a memory digest, a page root, a block
 47 //! root, the restore material, an optional parent, and a changed-page count is
 48 //! a *manifest*, so one object carries everything a restore needs.
 49 //!
 50 //! A manifest and its parents, at most 64 entries long, form a *delta chain*.
 51 //! The delta chain bounds the work any reopen can do.
 52 //!
 53 //! An object copied into an open transaction, readable back for verification
 54 //! before commit, is a *staged object*. The window between reserving the exact
 55 //! capacity and the commit that exposes every staged object and the new root at
 56 //! once is a *publication transaction*, so an abort or a crash before the
 57 //! commit exposes nothing.
 58 //!
 59 //! Every object read back is hashed and compared against the digest it was
 60 //! asked for, so the store holds bytes without being trusted.
 61 //!
 62 //! The four kinds of collection seed the provider counts separately form each
 63 //! *owner class*. Collection snapshots every owner class before marking and
 64 //! derives a work bound from the snapshot, so a trace that reaches the bound is
 65 //! refused.
 66 //!
 67 //! The store itself is a caller-supplied capability of function pointers, so
 68 //! the bytes can live in a file tree, a database, or a test double. Reopening
 69 //! walks the delta chain, authenticates the page trees, and verifies each
 70 //! referenced block root, and it returns the newest manifest. A memory image
 71 //! whose page tables have been rewritten to their canonical form and whose boot
 72 //! frame, request ring, event ring, and kernel stack are zeroed is *normalized
 73 //! memory*. Materializing does the same and also writes the newest normalized
 74 //! memory into an aligned caller-owned destination. The digest of one encoded
 75 //! manifest is a *manifest root*. A mutable memory view over one manifest root,
 76 //! authenticating a shared page on first read and copying it into a private
 77 //! pool on first write, is a *branch*.
 78 
 79 const owner = @import("owner.zig");
 80 const types = @import("types.zig");
 81 
 82 pub const branch = @import("branch.zig");
 83 pub const maintenance = @import("maintenance.zig");
 84 
 85 pub const Binding = types.Binding;
 86 pub const Capacity = types.Capacity;
 87 pub const Error = types.Error;
 88 pub const Limits = types.Limits;
 89 pub const Manifest = types.Manifest;
 90 pub const ManifestRoot = types.ManifestRoot;
 91 pub const ObjectKind = types.ObjectKind;
 92 pub const PageRoot = types.PageRoot;
 93 pub const Storage = types.Storage;
 94 pub const StorageError = types.StorageError;
 95 pub const bind = owner.bind;
 96 pub const bindDelta = owner.bindDelta;
 97 pub const chain_limit = types.chain_limit;
 98 pub const manifest_bytes = types.manifest_bytes;
 99 pub const materialize = owner.materialize;
100 pub const node_bytes = types.node_bytes;
101 pub const node_count = types.node_count;
102 pub const page_bytes = types.page_bytes;
103 pub const page_count = types.page_count;
104 pub const publication_capacity = types.publication_capacity;
105 pub const publication_limits = types.publication_limits;
106 pub const reopen = owner.reopen;