tiny.machine.checkpoint.roots

1/// The result of one root publication. The `root` field authenticates the2/// returned manifest.3pub const Binding = struct {4    root: ManifestRoot,5    manifest: Manifest,6};

1/// The exact publication requirement derived from `Limits`. The `objects` field2/// counts object slots and the `bytes` field counts their complete values.3pub const Capacity = struct {4    limits: Limits,5    objects: u32,6    bytes: u64,78    pub const DeriveError: type = CapacityDeriveError;910    /// Derives the exact object and byte counts from the limits. More pages11    /// than 16,384 returns `PageCapacityExceeded`, more nodes than 32,76712    /// returns `NodeCapacityExceeded`, and more than one manifest returns13    /// `ManifestCapacityExceeded`. Overflow in any product or sum returns14    /// `RootCapacityOverflow`.15    pub fn derive(limits: Limits) DeriveError!Capacity {16        if (limits.pages > page_count) return error.PageCapacityExceeded;17        if (limits.nodes > node_count) return error.NodeCapacityExceeded;18        if (limits.manifests > 1) return error.ManifestCapacityExceeded;19        const first = std.math.add(20            u32,21            limits.pages,22            limits.nodes,23        ) catch return error.RootCapacityOverflow;24        const objects = std.math.add(25            u32,26            first,27            limits.manifests,28        ) catch return error.RootCapacityOverflow;29        const page_storage = std.math.mul(30            u64,31            limits.pages,32            page_bytes,33        ) catch return error.RootCapacityOverflow;34        const node_storage = std.math.mul(35            u64,36            limits.nodes,37            node_bytes,38        ) catch return error.RootCapacityOverflow;39        const manifest_storage = std.math.mul(40            u64,41            limits.manifests,42            manifest_bytes,43        ) catch return error.RootCapacityOverflow;44        const partial = std.math.add(45            u64,46            page_storage,47            node_storage,48        ) catch return error.RootCapacityOverflow;49        return .{50            .limits = limits,51            .objects = objects,52            .bytes = std.math.add(53                u64,54                partial,55                manifest_storage,56            ) catch return error.RootCapacityOverflow,57        };58    }59};

1/// A ceiling on the pages, tree nodes, and manifests one publication writes.2pub const Limits = struct {3    pages: u32,4    nodes: u32,5    manifests: u16,6};

1/// The stored record links a checkpoint root, a page tree, the settled2/// receipt's block root, and the restore material. The `parent` field forms a3/// delta chain. The `dirty_pages` field counts the changed pages, and it is4/// every page for a parentless manifest.5pub const Manifest = struct {6    machine: owner.Root,7    memory: owner.MemoryDigest,8    pages: PageRoot,9    block: os.abi.BlockRoot,10    material: owner.Material,11    parent: ?ManifestRoot,12    dirty_pages: u16,13};

1/// The digest identity of one encoded checkpoint manifest.2pub const ManifestRoot = struct {3    digest: os.abi.Digest,4};

1/// The family of a stored object, used to select its exact byte length and2/// digest check. A page is 4096 bytes, a tree node is 80 bytes, and a manifest3/// is 4352 bytes.4pub const ObjectKind = enum(u8) {5    page = 1,6    node = 2,7    manifest = 3,8};

1/// The digest identity of a complete page tree.2pub const PageRoot = struct {3    digest: os.abi.Digest,4};

1/// The borrowed transaction, read, block, and collection capabilities of one2/// provider. Every stored byte and all context belong to the provider. A3/// committed binding from a digest to its bytes stays fixed. The caller keeps4/// the provider and the table of function pointers alive while the capability5/// is used.6pub const Storage = struct {7    context: *anyopaque,8    vtable: *const VTable,910    /// The table of function pointers a provider supplies. A provider reserves11    /// capacity first, and a failed reservation opens no transaction. The `put`12    /// call copies its input and rejects unequal bytes for a key that already13    /// exists. Commit makes every staged object and the new root visible in one14    /// step. A collection begins by snapshotting every seed class before15    /// marking. A collection commit removes only unmarked storage. An abort,16    /// and a crash before commit, expose no changes.17    pub const VTable: type = StorageVTable;1819    /// Reserves the whole capacity first, then opens one publication20    /// transaction.21    pub fn begin(self: Storage, capacity: Capacity) StorageError!void {22        const derived = Capacity.derive(capacity.limits) catch unreachable;23        std.debug.assert(std.meta.eql(derived, capacity));24        return self.vtable.begin(self.context, capacity);25    }2627    /// Copies one object into the open publication transaction. The byte count28    /// must equal the length its kind fixes, checked by an assertion.29    pub fn put(30        self: Storage,31        kind: ObjectKind,32        digest: os.abi.Digest,33        bytes: []const u8,34    ) StorageError!void {35        std.debug.assert(bytes.len == objectBytes(kind));36        return self.vtable.put(self.context, kind, digest, bytes);37    }3839    /// Copies one staged object out into caller-owned output, so the caller can40    /// check it. The output length must equal the length its kind fixes,41    /// checked by an assertion.42    pub fn readStaged(43        self: Storage,44        kind: ObjectKind,45        digest: os.abi.Digest,46        output: []u8,47    ) StorageError!void {48        std.debug.assert(output.len == objectBytes(kind));49        return self.vtable.read_staged(self.context, kind, digest, output);50    }5152    /// Publishes the staged objects under `root` in one atomic step.53    pub fn commit(self: Storage, root: ManifestRoot) StorageError!void {54        return self.vtable.commit(self.context, root);55    }5657    /// Drops the open publication transaction with no staged object made58    /// visible.59    pub fn abort(self: Storage) void {60        self.vtable.abort(self.context);61    }6263    /// Copies one committed object into caller-owned output. The output length64    /// must equal the length its kind fixes, checked by an assertion.65    pub fn read(66        self: Storage,67        kind: ObjectKind,68        digest: os.abi.Digest,69        output: []u8,70    ) StorageError!void {71        std.debug.assert(output.len == objectBytes(kind));72        return self.vtable.read(self.context, kind, digest, output);73    }7475    /// Opens every byte the provider holds under `block` again and76    /// authenticates it.77    pub fn verifyBlock(78        self: Storage,79        block: os.abi.BlockRoot,80    ) StorageError!void {81        return self.vtable.verify_block(self.context, block);82    }8384    /// Reserves the capacity, records the seeds of every class, and opens the85    /// collection.86    pub fn beginCollection(87        self: Storage,88        capacity: CollectionCapacity,89    ) StorageError!CollectionSnapshot {90        const derived = CollectionCapacity.derive(capacity.limits) catch91            unreachable;92        std.debug.assert(std.meta.eql(derived, capacity));93        return self.vtable.begin_collection(self.context, capacity);94    }9596    /// Returns one snapshotted manifest root by owner class and zero-based97    /// index.98    pub fn readSeed(99        self: Storage,100        class: ReachabilityClass,101        index: u16,102    ) StorageError!ManifestRoot {103        return self.vtable.read_seed(self.context, class, index);104    }105106    /// Marks one stored object, answering whether the mark is the first this107    /// collection set on it.108    pub fn retainObject(109        self: Storage,110        kind: ObjectKind,111        digest: os.abi.Digest,112    ) StorageError!Retention {113        return self.vtable.retain_object(self.context, kind, digest);114    }115116    /// Marks the data held under one block root, answering whether the mark is117    /// the first this collection set on that root.118    pub fn retainBlock(119        self: Storage,120        block: os.abi.BlockRoot,121    ) StorageError!Retention {122        return self.vtable.retain_block(self.context, block);123    }124125    /// Removes the unmarked storage in one atomic step and returns the126    /// retention and removal counts.127    pub fn commitCollection(self: Storage) StorageError!CollectionReport {128        return self.vtable.commit_collection(self.context);129    }130131    /// Aborts the collection and removes no storage.132    pub fn abortCollection(self: Storage) void {133        self.vtable.abort_collection(self.context);134    }135};

1/// Names every failure a provider reports, covering capacity, transactions,2/// collisions, reads, writes, and collection.3pub const StorageError = error{4    RootCapacityExceeded,5    RootCollision,6    RootCollectionCapacityExceeded,7    RootCollectionFailed,8    RootCollectionUnsupported,9    RootMissing,10    RootReadFailed,11    RootSeedMissing,12    RootTransactionInUse,13    RootWriteFailed,14};

1/// Writes a verified durable checkpoint into the store as a full page tree2/// under a manifest that has no parent. The provider reserves3/// `publication_capacity`, takes a copy of each object, verifies the settled4/// block closure, and commits in one step. A page root whose memory digest5/// differs from the checkpoint's returns `PageRootMismatch`. Any failure aborts6/// the publication transaction. The caller puts a complete capture into the7/// store to get a name for it.8pub fn bind(9    storage: types.Storage,10    checkpoint: *const owner.Checkpoint,11) types.Error!types.Binding {12    try storage.begin(types.publication_capacity);13    var transaction_open = true;14    defer if (transaction_open) storage.abort();1516    const contents = try owner.inspect(checkpoint);17    const pages = try tree.stage(storage, checkpoint.ram);18    const memory: owner.MemoryDigest = .{ .digest = canon.memory(pages.digest) };19    if (!std.meta.eql(memory, contents.memory)) {20        return error.PageRootMismatch;21    }22    const value: types.Manifest = .{23        .machine = contents.root,24        .memory = memory,25        .pages = pages,26        .block = contents.material.receipt.block_root,27        .material = contents.material,28        .parent = null,29        .dirty_pages = @intCast(types.page_count),30    };31    try storage.verifyBlock(value.block);32    const root = try manifest.stage(storage, value);33    try storage.commit(root);34    transaction_open = false;35    return .{ .root = root, .manifest = value };36}

1/// Stores a hot snapshot as a manifest whose parent is `parent_root`. The call2/// validates each material link along the parent manifest chain and verifies3/// the parent checkpoint and the child identity. A chain already 64 entries4/// deep returns `DeltaChainCapacityExceeded`. Each changed page becomes a new5/// page object, and the tree path above it is staged with it. A block closure6/// differing from the parent's is verified. Any failure after the transaction7/// opens aborts it.8pub fn bindDelta(9    storage: types.Storage,10    parent_root: types.ManifestRoot,11    snapshot: *const hot.Snapshot,12) types.Error!types.Binding {13    const parent = try inspectParentChain(storage, parent_root);14    _ = try admitNextDepth(parent.depth);15    const parent_contents = try owner.inspect(snapshot.parent);16    try validateSnapshotParent(parent.manifest, parent_contents);17    const snapshot_identity = try snapshot.identity();18    const capacity = try tree.deltaCapacity(snapshot.indices);19    try storage.begin(capacity);20    var transaction_open = true;21    defer if (transaction_open) storage.abort();2223    const pages = try tree.stageDelta(24        storage,25        parent.manifest.pages,26        snapshot.indices,27        snapshot.pages,28    );29    const memory: owner.MemoryDigest = .{ .digest = canon.memory(pages.digest) };30    if (!std.meta.eql(memory, snapshot.memory)) return error.PageRootMismatch;31    const identity = try owner.identify(snapshot.material, memory);32    if (!std.meta.eql(identity, snapshot_identity)) {33        return error.DeltaParentMismatch;34    }35    const block = snapshot.material.receipt.block_root;36    if (!std.meta.eql(block, parent.manifest.block)) {37        try storage.verifyBlock(block);38    }39    const value: types.Manifest = .{40        .machine = identity.root,41        .memory = memory,42        .pages = pages,43        .block = block,44        .material = snapshot.material,45        .parent = parent_root,46        .dirty_pages = snapshot.dirtyPageCount(),47    };48    const root = try manifest.stage(storage, value);49    try storage.commit(root);50    transaction_open = false;51    return .{ .root = root, .manifest = value };52}

1/// Opens the chain again, fills an aligned destination the caller owns with the2/// newest normalized memory, and checks that image against its memory digest. A3/// destination whose memory digest differs from the manifest's returns4/// `PageRootMismatch`.5pub fn materialize(6    storage: types.Storage,7    expected: types.ManifestRoot,8    destination: []align(types.page_bytes) u8,9) types.Error!types.Manifest {10    return open(storage, expected, destination);11}

1/// Opens a manifest chain again and authenticates it together with every2/// page-tree object beneath it and every block closure it names. The call walks3/// the parentless tree in full, then authenticates the changed paths between4/// each manifest and its child, which together covers every object the newest5/// root reaches. The call then returns the newest manifest.6pub fn reopen(7    storage: types.Storage,8    expected: types.ManifestRoot,9) types.Error!types.Manifest {10    return open(storage, expected, null);11}

1/// The failures of the provider joined with those of capacity, checkpoints,2/// manifests, page trees, and delta chains.3pub const Error = StorageError || Capacity.DeriveError || owner.Error || IntegrityError;

1pub const chain_limit: usize = 64;

1pub const manifest_bytes: usize = 256 + stream.header_bytes;

1pub const node_bytes: usize = 80;

1pub const node_count: u32 = 2 * page_count - 1;

1pub const publication_capacity = Capacity.derive(publication_limits) catch2    unreachable;

1pub const publication_limits: Limits = .{2    .pages = page_count,3    .nodes = node_count,4    .manifests = 1,5};

1pub const page_bytes: usize = core.layout.page_bytes;

1pub const roots = @import("roots/root.zig");

1//! Holding one capture is easy, and holding fifty is the problem the calls here2//! solve: the calls write captures into a store the caller supplies and read3//! them back.4//!5//! A caller keeping many captures pays a full memory image for each one unless6//! the captures share the pages they hold in common. The machine's fixed7//! 67,108,864 bytes, addressed from zero, holding 16,384 pages, are its8//! *memory*. The 4096 contiguous bytes of a machine's memory, named by their9//! zero-based index, are a *page*.10//!11//! A store outside the process can hand back the wrong bytes, so a reader has12//! to check each object it receives. A publication interrupted part way would13//! leave a root pointing at objects that were never written. Captures14//! accumulate, so something has to remove the objects nobody reaches without15//! removing the ones a reader still holds.16//!17//! A content-addressed object store keys each object by the digest of its bytes18//! and shares the subtrees two versions have in common, as Git does for its19//! trees. Mark and sweep reclaims storage by marking everything reachable from20//! 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, where23//! each node binds its level to its two ordered child digests, is a *page24//! tree*. The digest identifying a complete page tree held as stored objects is25//! the *page root*. Pages, tree nodes, and manifests are all written under26//! their digests, and a capture against a parent restages only the changed27//! pages and the tree paths above them. The caller-supplied content-addressed28//! store that owns every stored byte and answers reads and writes by digest is29//! the *provider*. One manifest root the provider reports as owned at the30//! moment collection opens is a *seed*. Marking every object reachable from the31//! provider's snapshotted seeds, then one atomic sweep that removes the32//! unmarked, is a *collection*.33//!34//! One page, one page-tree node, or one manifest, each written under its digest35//! at the exact byte length its kind fixes: 4096, 80, or 4352, is a *stored36//! object*. Every stored object fixes its byte length, so a read knows its37//! length before it asks.38//!39//! The digest binding one profile fingerprint to one state digest is the40//! *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 *memory42//! digest*. A generation and digest naming the stored data an execution read is43//! a *block root*. The fixed-size values needed to recompute an identity and44//! rebuild execution: profile fingerprint, settled receipt, CPU restart frame,45//! and immutable image descriptor, are the restore *material*. The stored46//! record joining a checkpoint root, a memory digest, a page root, a block47//! root, the restore material, an optional parent, and a changed-page count is48//! 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 verification54//! before commit, is a *staged object*. The window between reserving the exact55//! capacity and the commit that exposes every staged object and the new root at56//! once is a *publication transaction*, so an abort or a crash before the57//! commit exposes nothing.58//!59//! Every object read back is hashed and compared against the digest it was60//! asked for, so the store holds bytes without being trusted.61//!62//! The four kinds of collection seed the provider counts separately form each63//! *owner class*. Collection snapshots every owner class before marking and64//! derives a work bound from the snapshot, so a trace that reaches the bound is65//! refused.66//!67//! The store itself is a caller-supplied capability of function pointers, so68//! the bytes can live in a file tree, a database, or a test double. Reopening69//! walks the delta chain, authenticates the page trees, and verifies each70//! referenced block root, and it returns the newest manifest. A memory image71//! whose page tables have been rewritten to their canonical form and whose boot72//! frame, request ring, event ring, and kernel stack are zeroed is *normalized73//! memory*. Materializing does the same and also writes the newest normalized74//! memory into an aligned caller-owned destination. The digest of one encoded75//! 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 private77//! pool on first write, is a *branch*.7879const owner = @import("owner.zig");80const types = @import("types.zig");8182pub const branch = @import("branch.zig");83pub const maintenance = @import("maintenance.zig");8485pub const Binding = types.Binding;86pub const Capacity = types.Capacity;87pub const Error = types.Error;88pub const Limits = types.Limits;89pub const Manifest = types.Manifest;90pub const ManifestRoot = types.ManifestRoot;91pub const ObjectKind = types.ObjectKind;92pub const PageRoot = types.PageRoot;93pub const Storage = types.Storage;94pub const StorageError = types.StorageError;95pub const bind = owner.bind;96pub const bindDelta = owner.bindDelta;97pub const chain_limit = types.chain_limit;98pub const manifest_bytes = types.manifest_bytes;99pub const materialize = owner.materialize;100pub const node_bytes = types.node_bytes;101pub const node_count = types.node_count;102pub const page_bytes = types.page_bytes;103pub const page_count = types.page_count;104pub const publication_capacity = types.publication_capacity;105pub const publication_limits = types.publication_limits;106pub const reopen = owner.reopen;