lib/machine/src/checkpoint/root.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 //! A program running under a virtual machine has to be halted and turned into a
  2 //! value that carries a name, and a run has to be started again from that value
  3 //! later. The deterministic virtual machine this package runs, with a fixed
  4 //! memory size and a restricted kernel, is a *machine*.
  5 //!
  6 //! Callers want three things from such a value: restart a machine where it
  7 //! stopped, decide whether two runs reached the same state, and accept a
  8 //! capture from a party they have no reason to trust.
  9 //!
 10 //! The machine's fixed 67,108,864 bytes, addressed from zero, holding 16,384
 11 //! pages, is its *memory*. A region of 4096 contiguous bytes of a machine's
 12 //! memory, named by its zero-based index, is a *page*. The four memory regions
 13 //! carrying per-run transport and activation state are the *boot frame*,
 14 //! *request ring*, *event ring*, and *kernel stack*. A machine's memory holds
 15 //! per-run state in its page tables, boot frame, request ring, event ring, and
 16 //! kernel stack, so two runs that reached the same logical state hold different
 17 //! bytes there, and hashing memory as it stands would give one state two names.
 18 //! Memory alone leaves out where execution resumes, so a name over memory alone
 19 //! would let two different restart states share one name. A memory image is
 20 //! 67,108,864 bytes, so copying and hashing one per capture costs a full pass,
 21 //! and a machine captured repeatedly changes a small part of it between two
 22 //! captures. A capture can be interrupted part way, and a reader arriving
 23 //! afterwards has to tell a finished capture from an abandoned one.
 24 //!
 25 //! A hash tree yields one root digest over a large value and lets a changed
 26 //! region be rehashed along a single path (Merkle, 1979). A content-addressed
 27 //! object store keys each object by the digest of its bytes and shares the
 28 //! subtrees two versions have in common, as Git does for its trees.
 29 //!
 30 //! The complete binary tree over the 16,384 page digests, 14 levels deep, with
 31 //! each node binding its level to its two ordered child digests, is the *page
 32 //! tree*. From the first source, the code builds that page tree and runs a
 33 //! changed-page rebuild that walks one path per changed page. From the second
 34 //! source, the immutable root store keys pages, tree nodes, and manifests by
 35 //! digest, writes new objects only along the paths a capture changed, and
 36 //! reuses the parent's digests everywhere else.
 37 //!
 38 //! The in-place operation that rewrites page tables to their canonical form and
 39 //! zeroes the boot frame, request ring, event ring, and kernel stack is
 40 //! *normalization*. The memory image that normalization produces is *normalized
 41 //! memory*. Under the first departure, memory is normalized before it is
 42 //! hashed, which gives one logical state one name.
 43 //!
 44 //! Under the second departure, the name is layered. The SHA-256 identity of a
 45 //! normalized memory image, binding the page tree's root to the fixed memory
 46 //! geometry, is the *memory digest*, which names normalized memory. The record
 47 //! of a stopped machine boundary with activation authority removed, so one
 48 //! guest state keeps one identity across runs, is a *settled receipt*. The ten
 49 //! register values a restarted machine begins with, each fixed by the kernel
 50 //! manifest for one entry offset, form the *CPU restart frame*. The kernel
 51 //! image's digest, the initial CPU state it admits, its entry offset, and up to
 52 //! four load ranges placing image bytes in memory make up the *immutable image
 53 //! descriptor*. The SHA-256 identity of one restart state, committing the
 54 //! settled receipt, the CPU restart frame, the immutable image digest, and the
 55 //! memory digest, is the *state digest*. The machine configuration an execution
 56 //! ran under, identified by a profile fingerprint that is a SHA-256 digest, is
 57 //! an *execution profile*. The digest binding that profile fingerprint to the
 58 //! state digest is the *checkpoint root*.
 59 //!
 60 //! The borrowed value naming a published checkpoint's storage, memory, and root
 61 //! digest is the *handle*. Claiming empty storage, copying memory into the
 62 //! caller's second region, normalizing it, computing and writing the identity,
 63 //! and finishing with one atomic store that makes the handle visible is
 64 //! *publication*. Under the third departure, publication ensures that a crash
 65 //! leaves the storage either empty or holding a complete capture.
 66 //!
 67 //! Recomputing the memory, state, and root digests from the stored bytes and
 68 //! comparing them with the stored ones is *verification*. Under the fourth
 69 //! departure, verification occurs on every open, so a digest found in storage
 70 //! is checked before it is used.
 71 //!
 72 //! Captured machine execution state carrying an identity that any holder of the
 73 //! bytes can recompute is a *checkpoint*. A capture takes four forms over the
 74 //! same name. A checkpoint holding a complete normalized memory image, keeping
 75 //! its metadata and its page-aligned memory in two caller-owned regions, is a
 76 //! *durable checkpoint*. A checkpoint holding ordered changed pages against a
 77 //! durable parent is a *hot snapshot*, recorded by the `hot` namespace. The
 78 //! fixed 67,112,960-byte encoding of one durable checkpoint, consisting of a
 79 //! 4096-byte header followed by all normalized memory, is a *checkpoint
 80 //! stream*, encoded by the `stream` namespace. A caller-supplied
 81 //! content-addressed store that owns every stored byte and answers reads and
 82 //! writes by digest is a *provider*. The `roots` namespace stores pages and
 83 //! manifests as objects through such a provider.
 84 
 85 const owner = @import("owner/root.zig");
 86 const profile = @import("../profile/root.zig");
 87 const source = @import("source.zig");
 88 
 89 pub const stream = @import("stream/root.zig");
 90 pub const hot = @import("hot/root.zig");
 91 pub const roots = @import("roots/root.zig");
 92 
 93 pub const Checkpoint = owner.Checkpoint;
 94 pub const Contents = owner.Contents;
 95 pub const CpuState = owner.CpuState;
 96 pub const DurableError = owner.Error;
 97 pub const Error = DurableError || hot.Error;
 98 pub const Identity = owner.Identity;
 99 pub const Material = owner.Material;
100 pub const Materialization = owner.Materialization;
101 pub const MemoryDigest = owner.MemoryDigest;
102 pub const Recovery = owner.Recovery;
103 pub const Root = owner.Root;
104 pub const Source = source.Source;
105 pub const PreparedSource = source.Prepared;
106 pub const StateDigest = owner.StateDigest;
107 pub const Storage = owner.Storage;
108 pub const ram_alignment = owner.ram_alignment;
109 pub const ram_bytes = owner.ram_bytes;
110 pub const page_count = owner.page_count;
111 pub const storage_alignment = owner.storage_alignment;
112 pub const storage_bytes = owner.storage_bytes;
113 pub const validateStorageBytes = owner.validateStorageBytes;
114 pub const validateParent = owner.validateParent;
115 pub const open = owner.open;
116 pub const recoverAfterCrash = owner.recoverAfterCrash;
117 pub const captureDelta = owner.captureDelta;
118 pub const deltaDigest = owner.deltaDigest;
119 pub const identify = owner.identify;
120 pub const inspect = owner.inspect;
121 pub const materializeForRestore = owner.materializeForRestore;
122 pub const beginMaterialization = owner.beginMaterialization;
123 pub const ensureAvailable = owner.ensureAvailable;
124 pub const publish = owner.publish;
125 pub const publishMaterialized = owner.publishMaterialized;
126 pub const validateDeltaImage = owner.validateDeltaImage;
127 pub const validatedMemoryDigest = owner.validatedMemoryDigest;
128 
129 pub const determinism_sources = [_]profile.DeterminismSource{
130     .checkpoint_memory,
131     .checkpoint_source,
132 };