tiny.machine.checkpoint.roots.branch

1const os = @import("os");2const std = @import("std");3const owner = @import("owner.zig");4const tree = @import("tree.zig");5const types = @import("types.zig");67const authentication_word_bits: usize = @bitSizeOf(u64);8pub const authentication_word_count: usize =9    (types.page_count + authentication_word_bits - 1) /10    authentication_word_bits;1112const BranchError = error{13    BranchAddressOverflow,14    BranchOutOfBounds,15    BranchPageCapacityExceeded,16    BranchStorageMismatch,17};1819/// Combines stored-capture failures together with branch range, capacity, and20/// storage failures.21pub const Error = types.Error || BranchError;2223/// Sizes the storage a branch needs for its private pages exactly. The byte24/// counts cover one two-byte page index and one aligned 4096-byte page for25/// every slot.26pub const Capacity = struct {27    pages: u16,28    index_storage_bytes: u32,29    page_storage_bytes: u32,3031    /// Derives the storage counts for `pages` slots. A count above 16,38432    /// returns `BranchPageCapacityExceeded`.33    pub fn derive(pages: usize) error{BranchPageCapacityExceeded}!Capacity {34        if (pages > types.page_count) return error.BranchPageCapacityExceeded;35        const index_bytes = std.math.mul(36            usize,37            pages,38            @sizeOf(u16),39        ) catch return error.BranchPageCapacityExceeded;40        const page_storage_bytes = std.math.mul(41            usize,42            pages,43            types.page_bytes,44        ) catch return error.BranchPageCapacityExceeded;45        return .{46            .pages = @intCast(pages),47            .index_storage_bytes = @intCast(index_bytes),48            .page_storage_bytes = @intCast(page_storage_bytes),49        };50    }51};5253pub const maximum_capacity = Capacity.derive(types.page_count) catch unreachable;5455/// Holds the caller-owned memory a branch uses. The page pool holds private56/// writes. A bitmap of fixed size and a digest array remember which shared57/// pages have been authenticated.58pub const Storage = struct {59    capacity: Capacity,60    indices: []u16,61    pages: []align(types.page_bytes) u8,62    authenticated: *[authentication_word_count]u64,63    digests: *[types.page_count]os.abi.Digest,6465    /// Pairs each aligned private page with the index slot that names it. The66    /// authentication bitmap holds 256 words of 64 bits and the digest array67    /// holds one digest per page, both covering all 16,384 pages. More than68    /// 16,384 indices returns `BranchPageCapacityExceeded`. Any other69    /// page-storage length returns `BranchStorageMismatch`.70    pub fn init(71        indices: []u16,72        pages: []align(types.page_bytes) u8,73        authenticated: *[authentication_word_count]u64,74        digests: *[types.page_count]os.abi.Digest,75    ) Error!Storage {76        const capacity = try Capacity.derive(indices.len);77        if (pages.len != capacity.page_storage_bytes) {78            return error.BranchStorageMismatch;79        }80        return .{81            .capacity = capacity,82            .indices = indices,83            .pages = pages,84            .authenticated = authenticated,85            .digests = digests,86        };87    }88};8990/// Provides a mutable memory view over one stored manifest root. A read91/// authenticates a shared page the first time that page is touched. A page is92/// copied into private storage the caller supplied when a write first touches93/// it. Ownership of the provider and of every storage region stays with the94/// caller.95pub const Branch = struct {96    root_storage: types.Storage,97    root: types.ManifestRoot,98    manifest: types.Manifest,99    storage: Storage,100    private_count: u16 = 0,101    authenticated_count: u16 = 0,102103    /// Fills a caller's output buffer from a byte range that lies inside104    /// memory. A shared page is checked against its digest and the tree path105    /// above it the first time the branch touches it. A read consumes no pool106    /// slot. A range reaching past 67,108,864 bytes returns107    /// `BranchOutOfBounds`, and an address whose sum overflows returns108    /// `BranchAddressOverflow`.109    pub fn read(110        self: *@This(),111        address: usize,112        output: []u8,113    ) Error!void {114        const range = try checkedRange(address, output.len);115        var cursor = range.start;116        var output_offset: usize = 0;117        while (cursor < range.end) {118            const page_index: u16 = @intCast(cursor / types.page_bytes);119            const page_offset = cursor % types.page_bytes;120            const count = @min(types.page_bytes - page_offset, range.end - cursor);121            var page: [types.page_bytes]u8 align(types.page_bytes) = undefined;122            try self.readPage(page_index, &page);123            @memcpy(output[output_offset..][0..count], page[page_offset..][0..count]);124            cursor += count;125            output_offset += count;126        }127        std.debug.assert(output_offset == output.len);128    }129130    /// Sends a caller's bytes into private pages over a range that lies inside131    /// memory. Too little pool capacity is refused before any input byte is132    /// written.133    pub fn write(134        self: *@This(),135        address: usize,136        input: []const u8,137    ) Error!void {138        const range = try checkedRange(address, input.len);139        try self.preflightPrivate(range);140        try self.materializeRange(range);141        var cursor = range.start;142        var input_offset: usize = 0;143        while (cursor < range.end) {144            const page_index: u16 = @intCast(cursor / types.page_bytes);145            const page_offset = cursor % types.page_bytes;146            const count = @min(types.page_bytes - page_offset, range.end - cursor);147            const page = self.privatePage(page_index) orelse unreachable;148            @memcpy(page[page_offset..][0..count], input[input_offset..][0..count]);149            cursor += count;150            input_offset += count;151        }152        std.debug.assert(input_offset == input.len);153    }154155    /// Sets every byte of a range inside memory to one value, working through156    /// private pages. Too little pool capacity is refused before any157    /// destination byte is changed.158    pub fn fill(159        self: *@This(),160        address: usize,161        byte_count: usize,162        value: u8,163    ) Error!void {164        const range = try checkedRange(address, byte_count);165        try self.preflightPrivate(range);166        try self.materializeRange(range);167        var cursor = range.start;168        while (cursor < range.end) {169            const page_index: u16 = @intCast(cursor / types.page_bytes);170            const page_offset = cursor % types.page_bytes;171            const count = @min(types.page_bytes - page_offset, range.end - cursor);172            const page = self.privatePage(page_index) orelse unreachable;173            @memset(page[page_offset..][0..count], value);174            cursor += count;175        }176    }177178    /// Delivers a whole page, named by its zero-based index, into an aligned179    /// buffer the caller owns. A private page is copied from the pool, and any180    /// other page is read and authenticated through the provider. An index of181    /// 16,384 or more returns `BranchOutOfBounds`.182    pub fn readPage(183        self: *@This(),184        page_index: u16,185        output: *align(types.page_bytes) [types.page_bytes]u8,186    ) Error!void {187        if (page_index >= types.page_count) return error.BranchOutOfBounds;188        if (self.privatePage(page_index)) |page| {189            @memcpy(output, page);190            return;191        }192        return self.readSharedPage(page_index, output);193    }194195    /// Hands back a page the caller can write into directly, named by its196    /// zero-based index. The first access authenticates the shared page, copies197    /// it into the pool, and consumes one pool slot. A full pool returns198    /// `BranchPageCapacityExceeded`.199    pub fn writablePage(200        self: *@This(),201        page_index: u16,202    ) Error!*align(types.page_bytes) [types.page_bytes]u8 {203        if (page_index >= types.page_count) return error.BranchOutOfBounds;204        if (self.privatePage(page_index)) |page| return page;205        if (self.private_count == self.storage.capacity.pages) {206            return error.BranchPageCapacityExceeded;207        }208        var page: [types.page_bytes]u8 align(types.page_bytes) = undefined;209        try self.readSharedPage(page_index, &page);210        const slot = self.private_count;211        const destination = pageAt(self.storage.pages, slot);212        @memcpy(destination, &page);213        self.storage.indices[slot] = page_index;214        self.private_count += 1;215        return destination;216    }217218    /// Makes every distinct page index in the list private. The whole list is219    /// sized against the pool before a single slot is taken, and an index that220    /// appears twice costs one slot. A caller reserves pages up front so a221    /// later write cannot run out of pool.222    pub fn preparePages(self: *@This(), pages: []const u16) Error!void {223        var missing: usize = 0;224        for (pages, 0..) |page_index, index| {225            if (page_index >= types.page_count) return error.BranchOutOfBounds;226            if (self.privatePage(page_index) != null) continue;227            var duplicate = false;228            for (pages[0..index]) |previous| {229                duplicate = duplicate or previous == page_index;230            }231            if (!duplicate) missing += 1;232        }233        const available = self.storage.capacity.pages - self.private_count;234        if (missing > available) return error.BranchPageCapacityExceeded;235        for (pages) |page_index| _ = try self.writablePage(page_index);236    }237238    /// Gives the branch a private copy of every page a byte range touches. The239    /// range is sized against the pool before a single slot is taken.240    pub fn prepareWrite(241        self: *@This(),242        address: usize,243        byte_count: usize,244    ) Error!void {245        const range = try checkedRange(address, byte_count);246        try self.preflightPrivate(range);247        try self.materializeRange(range);248    }249250    /// Reports how many pool slots the branch has spent on private pages.251    pub fn privatePageCount(self: *const @This()) u16 {252        return self.private_count;253    }254255    /// Returns the branch metadata together with the authenticated-digest and256    /// private-page bytes. The total counts the branch value, the whole257    /// authentication bitmap, one digest for each authenticated page, and 4098258    /// bytes for each private page.259    pub fn residentBytes(self: *const @This()) u64 {260        const authenticated_bytes = @as(u64, self.authenticated_count) *261            @sizeOf(os.abi.Digest);262        const private_bytes = @as(u64, self.private_count) *263            (types.page_bytes + @sizeOf(u16));264        return @sizeOf(Branch) + @sizeOf(@TypeOf(self.storage.authenticated.*)) +265            authenticated_bytes + private_bytes;266    }267268    /// Answers whether a byte range touches the branch value itself or any of269    /// the four caller-owned regions: the index slots, the page pool, the270    /// authentication bitmap, and the digest cache. A caller checks this to271    /// keep a buffer clear of everything the branch borrows.272    pub fn aliases(self: *const @This(), bytes: []const u8) bool {273        return buffersOverlap(bytes, std.mem.asBytes(self)) or274            buffersOverlap(bytes, std.mem.sliceAsBytes(self.storage.indices)) or275            buffersOverlap(bytes, self.storage.pages) or276            buffersOverlap(bytes, std.mem.asBytes(self.storage.authenticated)) or277            buffersOverlap(bytes, std.mem.asBytes(self.storage.digests));278    }279280    fn readSharedPage(281        self: *@This(),282        page_index: u16,283        output: *align(types.page_bytes) [types.page_bytes]u8,284    ) Error!void {285        if (self.authenticated(page_index)) {286            return tree.readAuthenticatedPage(287                self.root_storage,288                self.storage.digests[page_index],289                output,290            );291        }292        const digest = try tree.readPageAt(293            self.root_storage,294            self.manifest.pages,295            page_index,296            output,297        );298        self.storage.digests[page_index] = digest;299        self.markAuthenticated(page_index);300    }301302    fn privatePage(303        self: *const @This(),304        page_index: u16,305    ) ?*align(types.page_bytes) [types.page_bytes]u8 {306        for (self.storage.indices[0..self.private_count], 0..) |index, slot| {307            if (index == page_index) return pageAt(self.storage.pages, slot);308        }309        return null;310    }311312    fn preflightPrivate(self: *const @This(), range: Range) Error!void {313        if (range.start == range.end) return;314        const first = range.start / types.page_bytes;315        const last = (range.end - 1) / types.page_bytes;316        var missing: usize = 0;317        for (first..last + 1) |page_index| {318            if (self.privatePage(@intCast(page_index)) == null) missing += 1;319        }320        const available = self.storage.capacity.pages - self.private_count;321        if (missing > available) return error.BranchPageCapacityExceeded;322    }323324    fn materializeRange(self: *@This(), range: Range) Error!void {325        if (range.start == range.end) return;326        const first = range.start / types.page_bytes;327        const last = (range.end - 1) / types.page_bytes;328        for (first..last + 1) |page_index| {329            _ = try self.writablePage(@intCast(page_index));330        }331    }332333    fn authenticated(self: *const @This(), page_index: u16) bool {334        const word = page_index / authentication_word_bits;335        const bit: u6 = @intCast(page_index % authentication_word_bits);336        return self.storage.authenticated[word] & (@as(u64, 1) << bit) != 0;337    }338339    fn markAuthenticated(self: *@This(), page_index: u16) void {340        const word = page_index / authentication_word_bits;341        const bit: u6 = @intCast(page_index % authentication_word_bits);342        std.debug.assert(!self.authenticated(page_index));343        self.storage.authenticated[word] |= @as(u64, 1) << bit;344        self.authenticated_count += 1;345    }346};347348const Range = struct {349    start: usize,350    end: usize,351};352353/// Opens one stored manifest root for shared-page access. The function354/// authenticates the manifest chain and its delta relationships, leaving each355/// page for the read that first touches it. The call validates the private pool356/// and clears the authentication bitmap, so no page starts out trusted. The357/// returned branch borrows every supplied resource.358pub fn restore(359    root_storage: types.Storage,360    root: types.ManifestRoot,361    storage: Storage,362) Error!Branch {363    try validateStorage(storage);364    const value = try owner.openShared(root_storage, root);365    @memset(storage.authenticated, 0);366    return .{367        .root_storage = root_storage,368        .root = root,369        .manifest = value,370        .storage = storage,371    };372}373374fn validateStorage(storage: Storage) Error!void {375    const actual = try Capacity.derive(storage.indices.len);376    if (!std.meta.eql(actual, storage.capacity) or377        storage.pages.len != storage.capacity.page_storage_bytes)378    {379        return error.BranchStorageMismatch;380    }381}382383fn checkedRange(address: usize, byte_count: usize) Error!Range {384    const end = std.math.add(usize, address, byte_count) catch385        return error.BranchAddressOverflow;386    const ram_bytes = types.page_count * types.page_bytes;387    if (address > ram_bytes or end > ram_bytes) return error.BranchOutOfBounds;388    return .{ .start = address, .end = end };389}390391fn pageAt(392    pages: []align(types.page_bytes) u8,393    slot: usize,394) *align(types.page_bytes) [types.page_bytes]u8 {395    const start = slot * types.page_bytes;396    std.debug.assert(start + types.page_bytes <= pages.len);397    return @ptrCast(@alignCast(pages[start..][0..types.page_bytes]));398}399400fn buffersOverlap(left: []const u8, right: []const u8) bool {401    if (left.len == 0 or right.len == 0) return false;402    const left_start = @intFromPtr(left.ptr);403    const right_start = @intFromPtr(right.ptr);404    const left_end = std.math.add(usize, left_start, left.len) catch return true;405    const right_end = std.math.add(usize, right_start, right.len) catch return true;406    return left_start < right_end and right_start < left_end;407}408409test "branch capacity rejects max plus one" {410    try std.testing.expectEqual(411        @as(u16, types.page_count),412        maximum_capacity.pages,413    );414    try std.testing.expectError(415        error.BranchPageCapacityExceeded,416        Capacity.derive(types.page_count + 1),417    );418}419420comptime {421    std.debug.assert(types.page_count % authentication_word_bits == 0);422    std.debug.assert(types.page_count <= std.math.maxInt(u16));423    std.debug.assert(authentication_word_count == 256);424}

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