tiny.machine.checkpoint.roots.maintenance

1/// The collection bounds derived from the limits. The `metadata_bytes` field2/// covers the seed roots and the mark arrays. The `work` field caps two things:3/// walking the manifest chains and the sweep that ends the collection.4pub const CollectionCapacity = struct {5    limits: CollectionLimits,6    seeds: u32,7    metadata_bytes: u64,8    work: u64,910    pub const DeriveError: type = CollectionCapacityError;1112    /// Derives the metadata byte count and the work bound from the limits.13    /// Overflow in any product or sum returns `CollectionCapacityOverflow`.14    /// Fewer object slots than root slots returns15    /// `CollectionObjectCapacityTooSmall`.16    pub fn derive(limits: CollectionLimits) DeriveError!CollectionCapacity {17        if (limits.roots > limits.objects) {18            return error.CollectionObjectCapacityTooSmall;19        }20        const seeds = limits.seeds.total();21        const seed_bytes = std.math.mul(22            u64,23            seeds,24            @sizeOf(ManifestRoot),25        ) catch return error.CollectionCapacityOverflow;26        const object_bytes = std.math.mul(27            u64,28            limits.objects,29            @sizeOf(bool),30        ) catch return error.CollectionCapacityOverflow;31        const root_bytes = std.math.mul(32            u64,33            limits.roots,34            @sizeOf(bool),35        ) catch return error.CollectionCapacityOverflow;36        const block_bytes = std.math.mul(37            u64,38            limits.blocks,39            @sizeOf(bool),40        ) catch return error.CollectionCapacityOverflow;41        const metadata_partial = std.math.add(42            u64,43            seed_bytes,44            object_bytes,45        ) catch return error.CollectionCapacityOverflow;46        const metadata_roots = std.math.add(47            u64,48            metadata_partial,49            root_bytes,50        ) catch return error.CollectionCapacityOverflow;51        const metadata_bytes = std.math.add(52            u64,53            metadata_roots,54            block_bytes,55        ) catch return error.CollectionCapacityOverflow;56        const tree_work = std.math.mul(57            u64,58            publication_capacity.objects,59            4,60        ) catch return error.CollectionCapacityOverflow;61        const per_chain_entry = std.math.add(62            u64,63            tree_work,64            6,65        ) catch return error.CollectionCapacityOverflow;66        const per_seed = std.math.mul(67            u64,68            chain_limit,69            per_chain_entry,70        ) catch return error.CollectionCapacityOverflow;71        const trace_work = std.math.mul(72            u64,73            seeds,74            per_seed,75        ) catch return error.CollectionCapacityOverflow;76        const physical_work = @as(u64, limits.objects) + limits.roots +77            limits.blocks;78        return .{79            .limits = limits,80            .seeds = seeds,81            .metadata_bytes = metadata_bytes,82            .work = std.math.add(83                u64,84                trace_work,85                physical_work,86            ) catch return error.CollectionCapacityOverflow,87        };88    }89};

1/// A ceiling on seeds, manifest roots, objects, and blocks for one collection.2pub const CollectionLimits = struct {3    seeds: SeedCounts,4    roots: u16,5    objects: u32,6    blocks: u16,7};

1/// The physical roots, objects, and blocks one collection retained or removed.2pub const CollectionReport = struct {3    retained_roots: u16,4    collected_roots: u16,5    retained_objects: u32,6    collected_objects: u32,7    retained_blocks: u16,8    collected_blocks: u16,9};

1/// The provider's snapshot of its seeds and physical storage, taken before2/// marking begins.3pub const CollectionSnapshot = struct {4    seeds: SeedCounts,5    roots: u16,6    objects: u32,7    blocks: u16,8};

1/// An owner class the provider snapshots, whose manifest roots seed a2/// collection.3pub const ReachabilityClass = enum(u8) {4    chic_world,5    live_staged_instance,6    retained_receipt,7    concurrent_reader,8};

1/// What a collection learns when it retains one stored identity. A `fresh`2/// result means this collection marked the identity first, and an `existing`3/// result means it had marked it already. The caller uses the result to stop a4/// trace from walking the same subtree twice.5pub const Retention = enum(u8) {6    fresh,7    existing,8};

1/// The number of collection seeds in each owner class.2pub const SeedCounts = struct {3    chic_worlds: u16,4    live_staged_instances: u16,5    retained_receipts: u16,6    concurrent_readers: u16,78    /// Gives how many seeds one owner class holds.9    pub fn count(self: SeedCounts, class: ReachabilityClass) u16 {10        return switch (class) {11            .chic_world => self.chic_worlds,12            .live_staged_instance => self.live_staged_instances,13            .retained_receipt => self.retained_receipts,14            .concurrent_reader => self.concurrent_readers,15        };16    }1718    /// Returns the sum of all seed classes as a `u32`. The caller uses the19    /// total to size the work a trace will do.20    pub fn total(self: SeedCounts) u32 {21        return @as(u32, self.chic_worlds) + self.live_staged_instances +22            self.retained_receipts + self.concurrent_readers;23    }24};

1pub const compaction_capacity = Capacity.derive(compaction_limits) catch2    unreachable;

1pub const compaction_limits: Limits = .{2    .pages = 0,3    .nodes = 0,4    .manifests = 1,5};

1const manifest = @import("manifest.zig");2const owner = @import("owner.zig");3const std = @import("std");4const tree = @import("tree.zig");5const types = @import("types.zig");67pub const CollectionCapacity = types.CollectionCapacity;8pub const CollectionLimits = types.CollectionLimits;9pub const CollectionReport = types.CollectionReport;10pub const CollectionSnapshot = types.CollectionSnapshot;11pub const ReachabilityClass = types.ReachabilityClass;12pub const Retention = types.Retention;13pub const SeedCounts = types.SeedCounts;14pub const compaction_capacity = types.compaction_capacity;15pub const compaction_limits = types.compaction_limits;1617/// The call opens a manifest chain again, authenticates it, and walks the18/// newest page tree in full before publishing a single manifest with no parent19/// that carries the newest state. A parentless input returns its existing root20/// without publishing anything. Any publication failure aborts the compaction21/// transaction. A caller turns a long chain into a single record, so later22/// reopens walk one manifest.23pub fn compact(24    storage: types.Storage,25    expected: types.ManifestRoot,26) types.Error!types.Binding {27    const value = try owner.reopen(storage, expected);28    try tree.verify(storage, value.pages);29    if (value.parent == null) {30        return .{ .root = expected, .manifest = value };31    }32    var compacted = value;33    compacted.parent = null;34    compacted.dirty_pages = @intCast(types.page_count);35    try storage.begin(types.compaction_capacity);36    var transaction_open = true;37    defer if (transaction_open) storage.abort();38    const root = try manifest.stage(storage, compacted);39    try storage.commit(root);40    transaction_open = false;41    return .{ .root = root, .manifest = compacted };42}4344/// The call traces every owner class the provider snapshotted, then commits one45/// atomic physical sweep. The call validates the snapshot against the supplied46/// capacity before marking begins, returning `RootCollectionCapacityExceeded`47/// when the snapshot exceeds it. A failure during tracing ends the collection48/// with no object removed. A caller runs collection to get space back from49/// captures nobody holds.50pub fn collect(51    storage: types.Storage,52    capacity: types.CollectionCapacity,53) types.Error!types.CollectionReport {54    const snapshot = try storage.beginCollection(capacity);55    var collection_open = true;56    defer if (collection_open) storage.abortCollection();57    try validateSnapshot(capacity, snapshot);58    inline for (types.reachability_classes) |class| {59        var index: u16 = 0;60        while (index < snapshot.seeds.count(class)) : (index += 1) {61            const root = try storage.readSeed(class, index);62            try retainRoot(storage, root);63        }64    }65    const report = try storage.commitCollection();66    collection_open = false;67    validateReport(snapshot, report);68    return report;69}7071fn retainRoot(72    storage: types.Storage,73    root: types.ManifestRoot,74) types.Error!void {75    const retention = try storage.retainObject(.manifest, root.digest);76    if (retention == .existing) return;77    _ = try owner.openShared(storage, root);78    var current = root;79    var depth: usize = 0;80    while (depth < types.chain_limit) : (depth += 1) {81        const value = try manifest.read(storage, current);82        try tree.retain(storage, value.pages);83        _ = try storage.retainBlock(value.block);84        if (value.parent) |parent| {85            const parent_retention = try storage.retainObject(86                .manifest,87                parent.digest,88            );89            if (parent_retention == .existing) return;90            current = parent;91        } else {92            return;93        }94    }95    return error.DeltaChainCapacityExceeded;96}9798fn validateSnapshot(99    capacity: types.CollectionCapacity,100    snapshot: types.CollectionSnapshot,101) types.StorageError!void {102    const limits = capacity.limits;103    inline for (types.reachability_classes) |class| {104        if (snapshot.seeds.count(class) > limits.seeds.count(class)) {105            return error.RootCollectionCapacityExceeded;106        }107    }108    if (snapshot.roots > limits.roots or109        snapshot.objects > limits.objects or110        snapshot.blocks > limits.blocks)111    {112        return error.RootCollectionCapacityExceeded;113    }114}115116fn validateReport(117    snapshot: types.CollectionSnapshot,118    report: types.CollectionReport,119) void {120    std.debug.assert(121        @as(u32, report.retained_roots) + report.collected_roots ==122            snapshot.roots,123    );124    std.debug.assert(125        report.retained_objects + report.collected_objects == snapshot.objects,126    );127    std.debug.assert(128        @as(u32, report.retained_blocks) + report.collected_blocks ==129            snapshot.blocks,130    );131}

1pub const maintenance = @import("maintenance.zig");