tiny.machine.checkpoint

1/// An exclusive publication claim for caller-filled memory. The caller aborts2/// an active claim when the fill stops part way. Publication consumes the3/// active claim.4pub const Materialization = struct {5    storage: *Storage,6    ram: []align(layout.page_bytes) u8,7    active: bool = true,8};

1/// The result of crash recovery. A published result carries a handle borrowing2/// the supplied storage and memory. By contrast, an empty result means the3/// storage holds nothing and can take a publication.4pub const Recovery = union(enum) {5    empty,6    published: Checkpoint,7};

1/// The authenticated metadata that checkpoint inspection returns. The value2/// carries the checkpoint root, the memory digest, and the material.3pub const Contents = struct {4    root: Root,5    memory: MemoryDigest,6    material: Material,7};

1/// A checkpoint root together with the digest of its settled receipt. The2/// `root` field authenticates the checkpoint state. The `semantic` field3/// identifies the settled execution receipt. Restore and world boundaries carry4/// this pair.5pub const Identity = struct {6    root: Root,7    semantic: os.abi.Digest,8};

1/// Holds what a restore needs to recompute a checkpoint identity and start2/// execution again: the profile fingerprint, the settled receipt, the CPU3/// restart frame, and the immutable image descriptor. The value has a fixed4/// size and owns no external storage.5pub const Material = struct {6    profile: profile.ProfileFingerprint,7    receipt: instance_receipt.SemanticReceipt,8    cpu: CpuState,9    immutable_image: core.provenance.ImmutableImage,10};

1/// Verified identity and material prepared for building a machine from a2/// capture.3pub const Prepared = struct {4    identity: checkpoint.Identity,5    material: checkpoint.Material,6};

1/// Borrowed capture used as the source of a restore. A durable source2/// references a complete normalized memory image. By contrast, a hot source3/// references ordered changed pages against a durable parent. The caller keeps4/// the selected checkpoint or snapshot alive for as long as the source can be5/// used.6pub const Source = union(enum) {7    durable: *const checkpoint.Checkpoint,8    hot: *const hot.Snapshot,910    /// Checks the selected source and hands back the identity it would restore.11    pub fn identity(self: @This()) checkpoint.Error!checkpoint.Identity {12        return switch (self) {13            .durable => |value| value.identity(),14            .hot => |value| value.identity(),15        };16    }1718    /// Verifies the source and the expected checkpoint root before a machine is19    /// constructed. A stored root other than the expected one returns20    /// `CheckpointRootMismatch`. The destination must have `ram_alignment` and21    /// `ram_bytes`. A hot source further requires the destination to hold22    /// parent memory that has been authenticated.23    pub fn prepareForRestore(24        self: @This(),25        expected: checkpoint.Root,26        destination: []align(checkpoint.ram_alignment) const u8,27    ) checkpoint.Error!Prepared {28        return switch (self) {29            .durable => |value| durable: {30                const contents = try checkpoint.inspect(value);31                if (!std.meta.eql(contents.root, expected)) {32                    return error.CheckpointRootMismatch;33                }34                if (destination.len != checkpoint.ram_bytes) {35                    return error.RamBytesMismatch;36                }37                break :durable .{38                    .identity = try checkpoint.identify(39                        contents.material,40                        contents.memory,41                    ),42                    .material = contents.material,43                };44            },45            .hot => |value| .{46                .identity = try value.prepareForRestore(expected, destination),47                .material = value.material,48            },49        };50    }5152    /// Fills a caller-owned memory region that lies outside the source and53    /// returns the restore material. A durable source copies the whole memory54    /// image. By contrast, a hot source overlays its ordered changed pages on55    /// authenticated parent memory. A failure after the copying starts can56    /// leave the destination bytes changed.57    pub fn materializeForRestore(58        self: @This(),59        expected: checkpoint.Root,60        destination: []align(checkpoint.ram_alignment) u8,61    ) checkpoint.Error!checkpoint.Material {62        return switch (self) {63            .durable => |value| checkpoint.materializeForRestore(64                value,65                expected,66                destination,67            ),68            .hot => |value| (try value.materializeForRestore(69                expected,70                destination,71            )).material,72        };73    }7475    /// Returns the complete memory image used as the source's evidence. A hot76    /// source returns its durable parent's normalized memory.77    pub fn evidenceRam(78        self: @This(),79    ) []align(checkpoint.ram_alignment) const u8 {80        return switch (self) {81            .durable => |value| value.ram,82            .hot => |value| value.evidenceRam(),83        };84    }8586    /// Reports whether bytes overlap any handle, metadata, memory, index, or87    /// page storage the source borrows.88    pub fn aliases(self: @This(), bytes: []const u8) bool {89        return switch (self) {90            .durable => |value| buffersOverlap(bytes, std.mem.asBytes(value)) or91                buffersOverlap(bytes, &value.storage.bytes) or92                buffersOverlap(bytes, value.ram),93            .hot => |value| value.aliases(bytes),94        };95    }96};

1/// Requires a child and its parent to share the profile fingerprint, the2/// immutable image descriptor, and the execution fingerprint. The call returns3/// the error naming the field that differs: `ParentProfileMismatch`,4/// `ParentImageMismatch`, or `ParentExecutionMismatch`.5pub fn validateParent(child: types.Material, parent: types.Material) Error!void {6    if (!std.meta.eql(child.profile, parent.profile)) {7        return error.ParentProfileMismatch;8    }9    if (!std.meta.eql(child.immutable_image, parent.immutable_image)) {10        return error.ParentImageMismatch;11    }12    if (!std.meta.eql(13        child.receipt.execution_fingerprint,14        parent.receipt.execution_fingerprint,15    )) {16        return error.ParentExecutionMismatch;17    }18}

1/// Captures the pages of live memory that differ from a normalized parent2/// image. The call writes strictly ascending page indices into the caller's3/// index array and one matching 4096-byte page record into the caller's page4/// array. Page tables, the boot frame, the transport rings, and the stack keep5/// their parent bytes, and no captured index names one of those pages. The two6/// output slices must be disjoint from each other and from both memory images,7/// and each index slot has exactly one aligned page waiting for it in the page8/// array. Every failure, including too few index slots, happens before any9/// output byte is written. The call returns the child memory digest and the10/// number of changed pages.11pub fn captureDelta(12    parent: []align(layout.page_bytes) const u8,13    current: []align(layout.page_bytes) const u8,14    image: provenance.ImmutableImage,15    indices: []u16,16    pages: []align(layout.page_bytes) u8,17) Error!Delta {18    try validateDeltaStorage(indices, pages);19    try validateCaptureAliases(parent, current, indices, pages);20    try validateLive(current, image);21    try validateNormalizedMemory(parent, image);22    var dirty = DirtyPageSet.empty;23    const facts = deltaFacts(parent, current, &dirty);24    if (facts.page_count > indices.len) return error.DeltaCapacityExceeded;25    fillDelta(current, indices, pages, &dirty);26    return facts;27}

1/// Computes the memory digest that one ordered set of changed pages produces2/// over a parent memory image. Indices must be strictly ascending, so each page3/// appears once, and each supplied page must differ from the parent page at its4/// index. An index naming a page table, the boot frame, a transport ring, or5/// the stack is rejected. The page array measures 4096 bytes for each index6/// supplied. A rejected index returns `DeltaIndicesInvalid`, and a wrong7/// page-array length returns `DeltaStorageMismatch`.8pub fn deltaDigest(9    parent: []align(layout.page_bytes) const u8,10    indices: []const u16,11    pages: []align(layout.page_bytes) const u8,12) Error!types.MemoryDigest {13    try layout.validateRamBytes(parent.len);14    try validateDeltaStorage(indices, pages);15    try validateDelta(parent, indices, pages);16    return overlayDigest(parent, indices, pages);17}

1/// Rejects any changed page overlapping a load range of the immutable image.2/// The call validates the image descriptor before reading its load ranges, and3/// an overlapping page returns `DeltaIndicesInvalid`. A caller uses this4/// validation to keep a changed page from rewriting the kernel image a capture5/// claims to have run.6pub fn validateDeltaImage(7    indices: []const u16,8    image: provenance.ImmutableImage,9) Error!void {10    try provenance.validate(image);11    for (indices) |page_index| {12        const page_start = @as(u64, page_index) * layout.page_bytes;13        const page_end = page_start + layout.page_bytes;14        for (image.loads[0..image.load_count]) |load| {15            const load_start = std.math.add(16                u64,17                os.boot.kernel.physical_base,18                load.physical_offset,19            ) catch return error.ImmutableLoadOutOfBounds;20            const load_end = std.math.add(21                u64,22                load_start,23                load.memory_bytes,24            ) catch return error.ImmutableLoadOutOfBounds;25            if (page_start < load_end and load_start < page_end) {26                return error.DeltaIndicesInvalid;27            }28        }29    }30}

1/// Checks that a memory image has the right length and normalized shape before2/// hashing it into a memory digest. A length other than 67,108,864 bytes3/// returns `RamBytesMismatch`, and page tables outside their canonical form, or4/// a nonzero byte in the boot frame, either transport ring, or the kernel5/// stack, returns `MemoryNotNormalized`.6pub fn validatedDigest(7    ram: []align(layout.page_bytes) const u8,8    image: provenance.ImmutableImage,9) Error!types.MemoryDigest {10    try validateNormalizedMemory(ram, image);11    return digest(ram);12}

1/// The failures of durable publication, ownership, corruption, identity, and2/// memory.3pub const Error = error{4    CheckpointClosed,5    CheckpointCorrupt,6    CheckpointRootMismatch,7    CheckpointStorageInUse,8    MemoryAliasesStorage,9    SourceAliasesDestination,10    StorageAliasesInstance,11    StorageAliasesOwner,12    StorageAliasesRam,13    RamBytesMismatch,14} || identity.Error || instance_receipt.Error || memory.Error || provenance.Error;

1/// Claims empty storage for memory that another source will fill. The storage2/// and the memory lie apart from each other and carry the sizes the call3/// requires. An existing claim or publication returns `CheckpointStorageInUse`.4pub fn beginMaterialization(5    storage: *Storage,6    ram: []align(layout.page_bytes) u8,7) Error!Materialization {8    try validateStoredInputs(storage, ram);9    const owner = ownerState(storage);10    if (owner.status.cmpxchgStrong(11        @backingInt(Status.empty),12        @backingInt(Status.capturing),13        .acq_rel,14        .acquire,15    ) != null) return error.CheckpointStorageInUse;16    return .{ .storage = storage, .ram = ram };17}

1/// Requires initialized storage to be empty. Storage already in use returns2/// `CheckpointStorageInUse`, and a malformed status byte returns3/// `CheckpointCorrupt`. The caller checks storage before starting work that4/// would waste it.5pub fn ensureAvailable(storage: *const Storage) Error!void {6    if (try checkedStatus(ownerStateConst(storage)) != .empty) {7        return error.CheckpointStorageInUse;8    }9}

1/// Validates the CPU restart frame and the settled receipt, then computes the2/// restore identity from the material and a memory digest.3pub fn identify(4    material: types.Material,5    memory_digest: types.MemoryDigest,6) Error!types.Identity {7    const state_digest = try identity.state(8        material.receipt,9        material.cpu,10        material.immutable_image,11        memory_digest,12    );13    return .{14        .root = identity.root(material.profile, state_digest),15        .semantic = try instance_receipt.semanticReceiptDigest(material.receipt),16    };17}

1/// Rebuilds each identity a checkpoint carries, then returns the metadata it2/// has authenticated.3pub fn inspect(checkpoint: *const Checkpoint) Error!types.Contents {4    const storage = checkpoint.storage;5    const source = checkpoint.ram;6    try validateStoredInputs(storage, source);7    const owner = ownerStateConst(storage);8    if (try checkedStatus(owner) != .published) {9        return error.CheckpointClosed;10    }11    if (!owns(checkpoint, owner)) return error.CheckpointClosed;12    const material = storedMaterial(owner);13    const memory_digest = owner.memory_digest;14    const root_value = owner.root;15    try verifyMaterial(material, memory_digest, root_value, source);16    return .{17        .root = root_value,18        .memory = memory_digest,19        .material = material,20    };21}

1/// Checks a durable checkpoint against `expected`, writes its normalized memory2/// into an aligned destination that lies outside the checkpoint's own regions,3/// and returns the restore material. Bytes already written stay in the4/// destination when the closing check fails.5pub fn materializeForRestore(6    checkpoint: *const Checkpoint,7    expected: types.Root,8    destination: []align(layout.page_bytes) u8,9) Error!types.Material {10    const storage = checkpoint.storage;11    const source = checkpoint.ram;12    try validateStoredInputs(storage, destination);13    if (buffersOverlap(source, destination)) {14        return error.SourceAliasesDestination;15    }16    const material = try inspectForRestore(checkpoint, expected);17    const owner = ownerStateConst(storage);18    const memory_digest = owner.memory_digest;19    const root_value = owner.root;20    @memcpy(destination, source);21    try verifyMaterial(material, memory_digest, root_value, destination);22    return material;23}

1/// Opens a published checkpoint whose root is `expected`, checking the stored2/// material and the memory image behind it. A stored root other than `expected`3/// returns `CheckpointRootMismatch`. Ownership of the two regions stays with4/// the caller, and the returned handle points at them.5pub fn open(6    storage: *const Storage,7    ram: []align(layout.page_bytes) const u8,8    expected: types.Root,9) Error!Checkpoint {10    try validateStoredInputs(storage, ram);11    const owner = ownerStateConst(storage);12    if (try checkedStatus(owner) != .published) {13        return error.CheckpointClosed;14    }15    if (!std.meta.eql(owner.root, expected)) {16        return error.CheckpointRootMismatch;17    }18    const checkpoint: Checkpoint = .{19        .storage = storage,20        .ram = ram,21        .root_digest = expected.digest,22    };23    try checkpoint.verify();24    return checkpoint;25}

1/// Copies live memory into a separate caller-owned memory region, normalizes2/// it, authenticates the material, and publishes one handle with a single3/// atomic store. Both memory slices must have `ram_alignment` and `ram_bytes`.4/// The two slices must be disjoint from the storage and from each other. A5/// failure after the storage is claimed returns that storage to empty. Copied6/// or normalized bytes can sit in the destination after a failure.7pub fn publish(8    material: types.Material,9    storage: *Storage,10    source: []align(layout.page_bytes) const u8,11    destination: []align(layout.page_bytes) u8,12) Error!Checkpoint {13    return switch (try publishUntil(14        material,15        storage,16        source,17        destination,18        null,19    )) {20        .interrupted => unreachable,21        .published => |checkpoint| checkpoint,22    };23}

1/// Authenticates caller-filled memory against the expected memory digest and2/// the expected checkpoint root, then publishes it with a single atomic store.3/// An authentication failure after the claim is confirmed aborts the claim. On4/// success, the returned handle points at the candidate's storage and memory.5pub fn publishMaterialized(6    candidate: *Materialization,7    material: types.Material,8    expected_root: types.Root,9    expected_memory: types.MemoryDigest,10) Error!Checkpoint {11    if (!candidate.active) return error.CheckpointStorageInUse;12    const owner = ownerState(candidate.storage);13    if (try checkedStatus(owner) != .capturing) {14        return error.CheckpointStorageInUse;15    }16    errdefer abortMaterialization(candidate);17    try provenance.validateRam(material.immutable_image, candidate.ram);18    const memory_digest = try memory.validatedDigest(19        candidate.ram,20        material.immutable_image,21    );22    if (!std.meta.eql(memory_digest, expected_memory)) {23        return error.MemoryDigestMismatch;24    }25    const state_digest = try identity.state(26        material.receipt,27        material.cpu,28        material.immutable_image,29        memory_digest,30    );31    const root_value = identity.root(material.profile, state_digest);32    if (!std.meta.eql(root_value, expected_root)) {33        return error.CheckpointRootMismatch;34    }35    return switch (publishAuthenticated(36        material,37        owner,38        candidate.storage,39        candidate.ram,40        memory_digest,41        root_value,42        null,43    )) {44        .interrupted => unreachable,45        .published => |checkpoint| result: {46            candidate.active = false;47            break :result checkpoint;48        },49    };50}

1/// Recovers caller-owned storage after a crash. An interrupted capture is reset2/// to empty. Storage found published needs an expected root from the caller,3/// and the call returns a handle it has verified. An invalid status, root,4/// storage, or memory returns the matching error.5pub fn recoverAfterCrash(6    storage: *Storage,7    ram: []align(layout.page_bytes) const u8,8    expected: ?types.Root,9) Error!Recovery {10    try validateStoredInputs(storage, ram);11    const owner = ownerState(storage);12    return switch (try checkedStatus(owner)) {13        .empty => .empty,14        .capturing => result: {15            reset(owner);16            break :result .empty;17        },18        .published => .{ .published = try open(19            storage,20            ram,21            expected orelse return error.CheckpointRootMismatch,22        ) },23    };24}

1pub const storage_alignment: usize = @alignOf(OwnerState);

1pub const storage_bytes: usize = @sizeOf(OwnerState);

1/// Confirms that an allocation made elsewhere for the metadata measures2/// `storage_bytes` and nothing else.3pub fn validateStorageBytes(bytes: usize) error{StorageBytesMismatch}!void {4    if (bytes != storage_bytes) return error.StorageBytesMismatch;5}

1//! A program running under a virtual machine has to be halted and turned into a2//! value that carries a name, and a run has to be started again from that value3//! later. The deterministic virtual machine this package runs, with a fixed4//! memory size and a restricted kernel, is a *machine*.5//!6//! Callers want three things from such a value: restart a machine where it7//! stopped, decide whether two runs reached the same state, and accept a8//! 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,38411//! pages, is its *memory*. A region of 4096 contiguous bytes of a machine's12//! memory, named by its zero-based index, is a *page*. The four memory regions13//! carrying per-run transport and activation state are the *boot frame*,14//! *request ring*, *event ring*, and *kernel stack*. A machine's memory holds15//! per-run state in its page tables, boot frame, request ring, event ring, and16//! kernel stack, so two runs that reached the same logical state hold different17//! 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 alone19//! would let two different restart states share one name. A memory image is20//! 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 two22//! captures. A capture can be interrupted part way, and a reader arriving23//! 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 changed26//! region be rehashed along a single path (Merkle, 1979). A content-addressed27//! object store keys each object by the digest of its bytes and shares the28//! 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, with31//! each node binding its level to its two ordered child digests, is the *page32//! tree*. From the first source, the code builds that page tree and runs a33//! changed-page rebuild that walks one path per changed page. From the second34//! source, the immutable root store keys pages, tree nodes, and manifests by35//! digest, writes new objects only along the paths a capture changed, and36//! reuses the parent's digests everywhere else.37//!38//! The in-place operation that rewrites page tables to their canonical form and39//! zeroes the boot frame, request ring, event ring, and kernel stack is40//! *normalization*. The memory image that normalization produces is *normalized41//! memory*. Under the first departure, memory is normalized before it is42//! hashed, which gives one logical state one name.43//!44//! Under the second departure, the name is layered. The SHA-256 identity of a45//! normalized memory image, binding the page tree's root to the fixed memory46//! geometry, is the *memory digest*, which names normalized memory. The record47//! of a stopped machine boundary with activation authority removed, so one48//! guest state keeps one identity across runs, is a *settled receipt*. The ten49//! register values a restarted machine begins with, each fixed by the kernel50//! manifest for one entry offset, form the *CPU restart frame*. The kernel51//! image's digest, the initial CPU state it admits, its entry offset, and up to52//! four load ranges placing image bytes in memory make up the *immutable image53//! descriptor*. The SHA-256 identity of one restart state, committing the54//! settled receipt, the CPU restart frame, the immutable image digest, and the55//! memory digest, is the *state digest*. The machine configuration an execution56//! ran under, identified by a profile fingerprint that is a SHA-256 digest, is57//! an *execution profile*. The digest binding that profile fingerprint to the58//! state digest is the *checkpoint root*.59//!60//! The borrowed value naming a published checkpoint's storage, memory, and root61//! digest is the *handle*. Claiming empty storage, copying memory into the62//! caller's second region, normalizing it, computing and writing the identity,63//! and finishing with one atomic store that makes the handle visible is64//! *publication*. Under the third departure, publication ensures that a crash65//! leaves the storage either empty or holding a complete capture.66//!67//! Recomputing the memory, state, and root digests from the stored bytes and68//! comparing them with the stored ones is *verification*. Under the fourth69//! departure, verification occurs on every open, so a digest found in storage70//! is checked before it is used.71//!72//! Captured machine execution state carrying an identity that any holder of the73//! bytes can recompute is a *checkpoint*. A capture takes four forms over the74//! same name. A checkpoint holding a complete normalized memory image, keeping75//! its metadata and its page-aligned memory in two caller-owned regions, is a76//! *durable checkpoint*. A checkpoint holding ordered changed pages against a77//! durable parent is a *hot snapshot*, recorded by the `hot` namespace. The78//! fixed 67,112,960-byte encoding of one durable checkpoint, consisting of a79//! 4096-byte header followed by all normalized memory, is a *checkpoint80//! stream*, encoded by the `stream` namespace. A caller-supplied81//! content-addressed store that owns every stored byte and answers reads and82//! writes by digest is a *provider*. The `roots` namespace stores pages and83//! manifests as objects through such a provider.8485const owner = @import("owner/root.zig");86const profile = @import("../profile/root.zig");87const source = @import("source.zig");8889pub const stream = @import("stream/root.zig");90pub const hot = @import("hot/root.zig");91pub const roots = @import("roots/root.zig");9293pub const Checkpoint = owner.Checkpoint;94pub const Contents = owner.Contents;95pub const CpuState = owner.CpuState;96pub const DurableError = owner.Error;97pub const Error = DurableError || hot.Error;98pub const Identity = owner.Identity;99pub const Material = owner.Material;100pub const Materialization = owner.Materialization;101pub const MemoryDigest = owner.MemoryDigest;102pub const Recovery = owner.Recovery;103pub const Root = owner.Root;104pub const Source = source.Source;105pub const PreparedSource = source.Prepared;106pub const StateDigest = owner.StateDigest;107pub const Storage = owner.Storage;108pub const ram_alignment = owner.ram_alignment;109pub const ram_bytes = owner.ram_bytes;110pub const page_count = owner.page_count;111pub const storage_alignment = owner.storage_alignment;112pub const storage_bytes = owner.storage_bytes;113pub const validateStorageBytes = owner.validateStorageBytes;114pub const validateParent = owner.validateParent;115pub const open = owner.open;116pub const recoverAfterCrash = owner.recoverAfterCrash;117pub const captureDelta = owner.captureDelta;118pub const deltaDigest = owner.deltaDigest;119pub const identify = owner.identify;120pub const inspect = owner.inspect;121pub const materializeForRestore = owner.materializeForRestore;122pub const beginMaterialization = owner.beginMaterialization;123pub const ensureAvailable = owner.ensureAvailable;124pub const publish = owner.publish;125pub const publishMaterialized = owner.publishMaterialized;126pub const validateDeltaImage = owner.validateDeltaImage;127pub const validatedMemoryDigest = owner.validatedMemoryDigest;128129pub const determinism_sources = [_]profile.DeterminismSource{130    .checkpoint_memory,131    .checkpoint_source,132};

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