lib/machine/src/checkpoint/roots/tree.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const canon = @import("../canon/root.zig");
2 const os = @import("os");
3 const std = @import("std");
4 const types = @import("types.zig");
5
6 const magic = [8]u8{ 'M', 'C', 'H', 'P', 'G', 'N', '1', 0 };
7 const version: u8 = 1;
8
9 const NodeKind = enum(u8) {
10 leaf = 1,
11 branch = 2,
12 };
13
14 const Expected = union(enum) {
15 leaf: u16,
16 branch: u8,
17 };
18
19 const Node = struct {
20 kind: NodeKind,
21 level: u8,
22 index: u16,
23 first: os.abi.Digest,
24 second: os.abi.Digest,
25 };
26
27 const Frame = struct {
28 digest: os.abi.Digest,
29 expected: Expected,
30 first_page: u16,
31 };
32
33 const DeltaState = enum(u8) {
34 enter,
35 left,
36 right,
37 };
38
39 const DeltaFrame = struct {
40 parent_digest: os.abi.Digest,
41 expected: Expected,
42 first_page: u16,
43 dirty_start: u16,
44 dirty_end: u16,
45 dirty_split: u16 = 0,
46 state: DeltaState = .enter,
47 parent_node: Node = undefined,
48 left: os.abi.Digest = undefined,
49 };
50
51 const DeltaPair = struct {
52 parent_digest: os.abi.Digest,
53 child_digest: os.abi.Digest,
54 expected: Expected,
55 first_page: u16,
56 };
57
58 /// Stages every page and every tree node for one complete memory image. The
59 /// call reads each staged object back and authenticates it before it returns
60 /// the page root. A memory image other than 67,108,864 bytes returns
61 /// `RamBytesMismatch`. The open publication transaction belongs to the caller,
62 /// and the caller chooses what an abort does.
63 pub fn stage(
64 storage: types.Storage,
65 ram: []align(types.page_bytes) const u8,
66 ) types.Error!types.PageRoot {
67 if (ram.len != canon.page_count * canon.page_bytes) {
68 return error.RamBytesMismatch;
69 }
70 var frontier: [canon.tree_levels + 1]os.abi.Digest = undefined;
71 for (0..canon.page_count) |index| {
72 const page_digest = try stagePage(storage, pageAt(ram, index));
73 var node_digest = canon.leaf(index, page_digest);
74 var node_bytes: [types.node_bytes]u8 = undefined;
75 encodeLeaf(@intCast(index), page_digest, &node_bytes);
76 try stageNode(storage, node_digest, .{ .leaf = @intCast(index) }, &node_bytes);
77 var position = index;
78 var level: usize = 0;
79 while (position & 1 == 1 and level < canon.tree_levels) : (level += 1) {
80 encodeBranch(@intCast(level), frontier[level], node_digest, &node_bytes);
81 node_digest = canon.node(
82 @intCast(level),
83 frontier[level],
84 node_digest,
85 );
86 try stageNode(storage, node_digest, .{ .branch = @intCast(level) }, &node_bytes);
87 position >>= 1;
88 }
89 std.debug.assert(level <= canon.tree_levels);
90 frontier[level] = node_digest;
91 }
92 return .{ .digest = frontier[canon.tree_levels] };
93 }
94
95 /// Computes the exact capacity one changed-page publication needs, given
96 /// indices that ascend with each page named once. The calculation counts one
97 /// page object per index and, at each of the 14 levels, one node per distinct
98 /// group of indices. A malformed index set returns a delta error with no
99 /// provider call made. A caller uses this capacity to reserve exactly what a
100 /// changed-page publication will write.
101 pub fn deltaCapacity(indices: []const u16) types.Error!types.Capacity {
102 try validateDeltaIndices(indices);
103 var nodes: u32 = @intCast(indices.len);
104 var shift: usize = 1;
105 while (shift <= canon.tree_levels) : (shift += 1) {
106 var groups: u32 = 0;
107 var previous: ?u16 = null;
108 for (indices) |index| {
109 const group = index >> @intCast(shift);
110 if (previous == null or group != previous.?) groups += 1;
111 previous = group;
112 }
113 nodes = std.math.add(u32, nodes, groups) catch
114 return error.RootCapacityOverflow;
115 }
116 return types.Capacity.derive(.{
117 .pages = @intCast(indices.len),
118 .nodes = nodes,
119 .manifests = 1,
120 });
121 }
122
123 /// Stages the changed pages and the tree paths above them against `parent`.
124 /// Indices arrive in strictly ascending order with each page named once, and
125 /// every index has one aligned page record beside it. Subtrees holding no
126 /// changed page keep the parent's digest and stage nothing. An empty set of
127 /// indices returns the parent page root.
128 pub fn stageDelta(
129 storage: types.Storage,
130 parent: types.PageRoot,
131 indices: []const u16,
132 pages: []align(types.page_bytes) const u8,
133 ) types.Error!types.PageRoot {
134 try validateDeltaStorage(indices, pages);
135 if (indices.len == 0) return parent;
136 var stack: [canon.tree_levels + 1]DeltaFrame = undefined;
137 var count: usize = 1;
138 stack[0] = deltaFrame(
139 parent.digest,
140 .{ .branch = canon.tree_levels - 1 },
141 0,
142 0,
143 @intCast(indices.len),
144 );
145 var result: os.abi.Digest = undefined;
146 var returned = false;
147 while (count > 0) {
148 const frame = &stack[count - 1];
149 if (returned) {
150 returned = try resumeDelta(
151 storage,
152 &stack,
153 &count,
154 frame,
155 &result,
156 );
157 continue;
158 }
159 returned = try enterDelta(
160 storage,
161 indices,
162 pages,
163 &stack,
164 &count,
165 frame,
166 &result,
167 );
168 }
169 std.debug.assert(returned);
170 return .{ .digest = result };
171 }
172
173 /// Authenticates every changed path between a parent page root and a child page
174 /// root. The traversal descends only where the two digests differ, so a subtree
175 /// the parent already authenticated is skipped. The walk counts the distinct
176 /// changed leaves and requires that count to be `expected_dirty`, returning
177 /// `DeltaPageCountMismatch` for any other count.
178 pub fn verifyDelta(
179 storage: types.Storage,
180 parent: types.PageRoot,
181 child: types.PageRoot,
182 expected_dirty: u16,
183 ) types.Error!void {
184 if (expected_dirty > types.page_count) return error.DeltaPageCountMismatch;
185 try validateDigest(parent.digest);
186 try validateDigest(child.digest);
187 var stack: [canon.tree_levels + 1]DeltaPair = undefined;
188 var count: usize = 1;
189 stack[0] = .{
190 .parent_digest = parent.digest,
191 .child_digest = child.digest,
192 .expected = .{ .branch = canon.tree_levels - 1 },
193 .first_page = 0,
194 };
195 var dirty: u16 = 0;
196 while (count > 0) {
197 count -= 1;
198 const pair = stack[count];
199 if (sameDigest(pair.parent_digest, pair.child_digest)) continue;
200 const parent_node = try readNode(storage, pair.parent_digest, pair.expected);
201 const child_node = try readNode(storage, pair.child_digest, pair.expected);
202 switch (pair.expected) {
203 .leaf => |index| {
204 if (sameDigest(parent_node.first, child_node.first)) {
205 return error.DeltaPageCountMismatch;
206 }
207 try readPage(storage, parent_node.first, index, null);
208 try readPage(storage, child_node.first, index, null);
209 dirty += 1;
210 if (dirty > expected_dirty) return error.DeltaPageCountMismatch;
211 },
212 .branch => |level| pushDeltaPairs(
213 &stack,
214 &count,
215 pair.first_page,
216 level,
217 parent_node,
218 child_node,
219 ),
220 }
221 }
222 if (dirty != expected_dirty) return error.DeltaPageCountMismatch;
223 }
224
225 /// Authenticates every node and every page reachable from one page root. A
226 /// traversal reaching other than 32,767 nodes and 16,384 pages returns
227 /// `RootObjectCorrupt`.
228 pub fn verify(
229 storage: types.Storage,
230 root: types.PageRoot,
231 ) types.Error!void {
232 return walk(storage, root, null);
233 }
234
235 /// Marks each node and page reachable from the root while a provider collection
236 /// runs. A newly marked object is authenticated before the traversal continues
237 /// past it. An object this collection has already marked ends that branch of
238 /// the traversal.
239 pub fn retain(
240 storage: types.Storage,
241 root: types.PageRoot,
242 ) types.Error!void {
243 try validateDigest(root.digest);
244 var stack: [canon.tree_levels + 1]Frame = undefined;
245 var stack_count: usize = 1;
246 stack[0] = .{
247 .digest = root.digest,
248 .expected = .{ .branch = canon.tree_levels - 1 },
249 .first_page = 0,
250 };
251 var work: u32 = 0;
252 while (work < types.node_count and stack_count > 0) : (work += 1) {
253 stack_count -= 1;
254 const frame = stack[stack_count];
255 const retention = try storage.retainObject(.node, frame.digest);
256 if (retention == .existing) continue;
257 const node = try readNode(storage, frame.digest, frame.expected);
258 switch (frame.expected) {
259 .leaf => |index| try retainPage(storage, node.first, index),
260 .branch => |level| pushChildren(
261 &stack,
262 &stack_count,
263 frame.first_page,
264 level,
265 node,
266 ),
267 }
268 }
269 if (stack_count != 0) return error.RootObjectCorrupt;
270 }
271
272 /// Authenticates a complete page tree while writing its pages into an aligned
273 /// caller-owned destination. A destination other than 67,108,864 bytes returns
274 /// `RamBytesMismatch`.
275 pub fn materialize(
276 storage: types.Storage,
277 root: types.PageRoot,
278 destination: []align(types.page_bytes) u8,
279 ) types.Error!void {
280 if (destination.len != canon.page_count * canon.page_bytes) {
281 return error.RamBytesMismatch;
282 }
283 return walk(storage, root, destination);
284 }
285
286 /// Validates the encoding of a page-root digest.
287 pub fn validateRoot(root: types.PageRoot) types.Error!void {
288 return validateDigest(root.digest);
289 }
290
291 /// Checks the page bytes at one zero-based index against every node on the path
292 /// down to them. The traversal walks one node per level from the root down to
293 /// the leaf, with 14 reads in all. The call copies the page into aligned
294 /// caller-owned output and returns its digest. An index of 16,384 or more
295 /// returns `RootObjectCorrupt`.
296 pub fn readPageAt(
297 storage: types.Storage,
298 root: types.PageRoot,
299 page_index: u16,
300 output: *align(types.page_bytes) [types.page_bytes]u8,
301 ) types.Error!os.abi.Digest {
302 if (page_index >= types.page_count) return error.RootObjectCorrupt;
303 try validateRoot(root);
304 var digest = root.digest;
305 var first_page: u16 = 0;
306 var level: usize = canon.tree_levels;
307 while (level > 0) {
308 level -= 1;
309 const node = try readNode(
310 storage,
311 digest,
312 .{ .branch = @intCast(level) },
313 );
314 const child_pages = childPageCount(@intCast(level));
315 if (page_index < first_page + child_pages) {
316 digest = node.first;
317 } else {
318 first_page += child_pages;
319 digest = node.second;
320 }
321 }
322 const leaf = try readNode(storage, digest, .{ .leaf = page_index });
323 try readPageInto(storage, leaf.first, output);
324 return leaf.first;
325 }
326
327 /// Reads page bytes under a digest an earlier tree-path read authenticated. The
328 /// provider keeps a committed digest bound to the same bytes, so that binding
329 /// makes the single read safe.
330 pub fn readAuthenticatedPage(
331 storage: types.Storage,
332 digest: os.abi.Digest,
333 output: *align(types.page_bytes) [types.page_bytes]u8,
334 ) types.Error!void {
335 try validateDigest(digest);
336 return storage.read(.page, digest, output);
337 }
338
339 fn enterDelta(
340 storage: types.Storage,
341 indices: []const u16,
342 pages: []align(types.page_bytes) const u8,
343 stack: *[canon.tree_levels + 1]DeltaFrame,
344 count: *usize,
345 frame: *DeltaFrame,
346 result: *os.abi.Digest,
347 ) types.Error!bool {
348 switch (frame.expected) {
349 .leaf => |index| {
350 if (frame.dirty_end != frame.dirty_start + 1 or
351 indices[frame.dirty_start] != index)
352 {
353 return error.DeltaIndicesInvalid;
354 }
355 const parent_node = try readNode(
356 storage,
357 frame.parent_digest,
358 frame.expected,
359 );
360 const page_digest = try stagePage(
361 storage,
362 pageAt(pages, frame.dirty_start),
363 );
364 if (sameDigest(parent_node.first, page_digest)) {
365 return error.DeltaIndicesInvalid;
366 }
367 var bytes: [types.node_bytes]u8 = undefined;
368 encodeLeaf(index, page_digest, &bytes);
369 result.* = canon.leaf(index, page_digest);
370 try stageNode(storage, result.*, frame.expected, &bytes);
371 count.* -= 1;
372 return true;
373 },
374 .branch => |level| {
375 frame.parent_node = try readNode(
376 storage,
377 frame.parent_digest,
378 frame.expected,
379 );
380 const split_page = frame.first_page + childPageCount(level);
381 frame.dirty_split = lowerBoundDirty(
382 indices,
383 frame.dirty_start,
384 frame.dirty_end,
385 split_page,
386 );
387 frame.state = .left;
388 if (frame.dirty_start == frame.dirty_split) {
389 result.* = frame.parent_node.first;
390 return true;
391 }
392 pushDeltaChild(
393 stack,
394 count,
395 frame,
396 false,
397 frame.dirty_start,
398 frame.dirty_split,
399 );
400 return false;
401 },
402 }
403 }
404
405 fn resumeDelta(
406 storage: types.Storage,
407 stack: *[canon.tree_levels + 1]DeltaFrame,
408 count: *usize,
409 frame: *DeltaFrame,
410 result: *os.abi.Digest,
411 ) types.Error!bool {
412 switch (frame.state) {
413 .enter => unreachable,
414 .left => {
415 frame.left = result.*;
416 frame.state = .right;
417 if (frame.dirty_split == frame.dirty_end) {
418 result.* = frame.parent_node.second;
419 return true;
420 }
421 pushDeltaChild(
422 stack,
423 count,
424 frame,
425 true,
426 frame.dirty_split,
427 frame.dirty_end,
428 );
429 return false;
430 },
431 .right => {
432 const level = switch (frame.expected) {
433 .branch => |value| value,
434 .leaf => unreachable,
435 };
436 var bytes: [types.node_bytes]u8 = undefined;
437 encodeBranch(level, frame.left, result.*, &bytes);
438 result.* = canon.node(level, frame.left, result.*);
439 try stageNode(storage, result.*, frame.expected, &bytes);
440 count.* -= 1;
441 return true;
442 },
443 }
444 }
445
446 fn pushDeltaChild(
447 stack: *[canon.tree_levels + 1]DeltaFrame,
448 count: *usize,
449 parent: *const DeltaFrame,
450 right: bool,
451 dirty_start: u16,
452 dirty_end: u16,
453 ) void {
454 const level = switch (parent.expected) {
455 .branch => |value| value,
456 .leaf => unreachable,
457 };
458 const pages = childPageCount(level);
459 const first_page = parent.first_page + if (right) pages else 0;
460 const expected: Expected = if (level == 0)
461 .{ .leaf = first_page }
462 else
463 .{ .branch = level - 1 };
464 const digest = if (right)
465 parent.parent_node.second
466 else
467 parent.parent_node.first;
468 std.debug.assert(count.* < stack.len);
469 stack[count.*] = deltaFrame(
470 digest,
471 expected,
472 first_page,
473 dirty_start,
474 dirty_end,
475 );
476 count.* += 1;
477 }
478
479 fn deltaFrame(
480 parent_digest: os.abi.Digest,
481 expected: Expected,
482 first_page: u16,
483 dirty_start: u16,
484 dirty_end: u16,
485 ) DeltaFrame {
486 std.debug.assert(dirty_start < dirty_end);
487 return .{
488 .parent_digest = parent_digest,
489 .expected = expected,
490 .first_page = first_page,
491 .dirty_start = dirty_start,
492 .dirty_end = dirty_end,
493 };
494 }
495
496 fn lowerBoundDirty(
497 indices: []const u16,
498 start: u16,
499 end: u16,
500 page: u16,
501 ) u16 {
502 for (start..end) |index| {
503 if (indices[index] >= page) return @intCast(index);
504 }
505 return end;
506 }
507
508 fn childPageCount(level: u8) u16 {
509 const shift: std.math.Log2Int(u16) = @intCast(level);
510 return @as(u16, 1) << shift;
511 }
512
513 fn walk(
514 storage: types.Storage,
515 root: types.PageRoot,
516 destination: ?[]align(types.page_bytes) u8,
517 ) types.Error!void {
518 try validateDigest(root.digest);
519 var stack: [canon.tree_levels + 1]Frame = undefined;
520 var stack_count: usize = 1;
521 stack[0] = .{
522 .digest = root.digest,
523 .expected = .{ .branch = canon.tree_levels - 1 },
524 .first_page = 0,
525 };
526 var nodes: u32 = 0;
527 var pages: u32 = 0;
528 while (nodes < types.node_count and stack_count > 0) : (nodes += 1) {
529 stack_count -= 1;
530 const frame = stack[stack_count];
531 const node = try readNode(storage, frame.digest, frame.expected);
532 switch (frame.expected) {
533 .leaf => |index| {
534 try readPage(storage, node.first, index, destination);
535 pages += 1;
536 },
537 .branch => |level| pushChildren(
538 &stack,
539 &stack_count,
540 frame.first_page,
541 level,
542 node,
543 ),
544 }
545 }
546 if (stack_count != 0 or nodes != types.node_count or pages != types.page_count) {
547 return error.RootObjectCorrupt;
548 }
549 }
550
551 fn stagePage(
552 storage: types.Storage,
553 page: *const [types.page_bytes]u8,
554 ) types.Error!os.abi.Digest {
555 const snapshot = page.*;
556 const digest = canon.page(&snapshot);
557 try storage.put(.page, digest, &snapshot);
558 var reopened: [types.page_bytes]u8 = undefined;
559 try storage.readStaged(.page, digest, &reopened);
560 if (!std.mem.eql(u8, &snapshot, &reopened)) {
561 return error.RootObjectCorrupt;
562 }
563 return digest;
564 }
565
566 fn stageNode(
567 storage: types.Storage,
568 digest: os.abi.Digest,
569 expected: Expected,
570 bytes: *const [types.node_bytes]u8,
571 ) types.Error!void {
572 try storage.put(.node, digest, bytes);
573 var reopened: [types.node_bytes]u8 = undefined;
574 try storage.readStaged(.node, digest, &reopened);
575 _ = try decodeNode(&reopened, digest, expected);
576 }
577
578 fn readNode(
579 storage: types.Storage,
580 digest: os.abi.Digest,
581 expected: Expected,
582 ) types.Error!Node {
583 var bytes: [types.node_bytes]u8 = undefined;
584 try storage.read(.node, digest, &bytes);
585 return decodeNode(&bytes, digest, expected);
586 }
587
588 fn readPage(
589 storage: types.Storage,
590 digest: os.abi.Digest,
591 index: u16,
592 destination: ?[]align(types.page_bytes) u8,
593 ) types.Error!void {
594 var page: [types.page_bytes]u8 align(types.page_bytes) = undefined;
595 try readPageInto(storage, digest, &page);
596 if (destination) |output| {
597 const start = @as(usize, index) * types.page_bytes;
598 @memcpy(output[start..][0..types.page_bytes], &page);
599 }
600 }
601
602 fn retainPage(
603 storage: types.Storage,
604 digest: os.abi.Digest,
605 index: u16,
606 ) types.Error!void {
607 const retention = try storage.retainObject(.page, digest);
608 if (retention == .existing) return;
609 try readPage(storage, digest, index, null);
610 }
611
612 fn readPageInto(
613 storage: types.Storage,
614 digest: os.abi.Digest,
615 output: *align(types.page_bytes) [types.page_bytes]u8,
616 ) types.Error!void {
617 try storage.read(.page, digest, output);
618 if (!sameDigest(digest, canon.page(output))) {
619 return error.RootObjectCorrupt;
620 }
621 }
622
623 fn pushChildren(
624 stack: *[canon.tree_levels + 1]Frame,
625 count: *usize,
626 first_page: u16,
627 level: u8,
628 node: Node,
629 ) void {
630 std.debug.assert(count.* + 2 <= stack.len);
631 const shift: std.math.Log2Int(usize) = @intCast(level);
632 const child_pages: u16 = @intCast(@as(usize, 1) << shift);
633 const expected: Expected = if (level == 0)
634 .{ .leaf = first_page }
635 else
636 .{ .branch = level - 1 };
637 const right_expected: Expected = if (level == 0)
638 .{ .leaf = first_page + 1 }
639 else
640 .{ .branch = level - 1 };
641 stack[count.*] = .{
642 .digest = node.second,
643 .expected = right_expected,
644 .first_page = first_page + child_pages,
645 };
646 count.* += 1;
647 stack[count.*] = .{
648 .digest = node.first,
649 .expected = expected,
650 .first_page = first_page,
651 };
652 count.* += 1;
653 }
654
655 fn pushDeltaPairs(
656 stack: *[canon.tree_levels + 1]DeltaPair,
657 count: *usize,
658 first_page: u16,
659 level: u8,
660 parent: Node,
661 child: Node,
662 ) void {
663 std.debug.assert(count.* + 2 <= stack.len);
664 const child_pages = childPageCount(level);
665 const left_expected: Expected = if (level == 0)
666 .{ .leaf = first_page }
667 else
668 .{ .branch = level - 1 };
669 const right_expected: Expected = if (level == 0)
670 .{ .leaf = first_page + 1 }
671 else
672 .{ .branch = level - 1 };
673 stack[count.*] = .{
674 .parent_digest = parent.second,
675 .child_digest = child.second,
676 .expected = right_expected,
677 .first_page = first_page + child_pages,
678 };
679 count.* += 1;
680 stack[count.*] = .{
681 .parent_digest = parent.first,
682 .child_digest = child.first,
683 .expected = left_expected,
684 .first_page = first_page,
685 };
686 count.* += 1;
687 }
688
689 fn encodeLeaf(
690 index: u16,
691 page_digest: os.abi.Digest,
692 output: *[types.node_bytes]u8,
693 ) void {
694 var bytes: [types.node_bytes]u8 = @splat(0);
695 @memcpy(bytes[0..magic.len], &magic);
696 bytes[8] = version;
697 bytes[9] = @backingInt(NodeKind.leaf);
698 std.mem.writeInt(u32, bytes[12..16], index, .little);
699 @memcpy(bytes[16..48], &page_digest);
700 output.* = bytes;
701 }
702
703 fn encodeBranch(
704 level: u8,
705 left: os.abi.Digest,
706 right: os.abi.Digest,
707 output: *[types.node_bytes]u8,
708 ) void {
709 var bytes: [types.node_bytes]u8 = @splat(0);
710 @memcpy(bytes[0..magic.len], &magic);
711 bytes[8] = version;
712 bytes[9] = @backingInt(NodeKind.branch);
713 bytes[10] = level;
714 @memcpy(bytes[16..48], &left);
715 @memcpy(bytes[48..80], &right);
716 output.* = bytes;
717 }
718
719 fn decodeNode(
720 input: *const [types.node_bytes]u8,
721 expected_digest: os.abi.Digest,
722 expected: Expected,
723 ) types.Error!Node {
724 if (!std.mem.eql(u8, input[0..magic.len], &magic) or
725 input[8] != version or input[11] != 0)
726 {
727 return error.RootObjectCorrupt;
728 }
729 const kind: NodeKind = switch (input[9]) {
730 @backingInt(NodeKind.leaf) => .leaf,
731 @backingInt(NodeKind.branch) => .branch,
732 else => return error.RootObjectCorrupt,
733 };
734 const encoded_index = std.mem.readInt(u32, input[12..16], .little);
735 if (encoded_index >= canon.page_count) return error.RootObjectCorrupt;
736 const value: Node = .{
737 .kind = kind,
738 .level = input[10],
739 .index = @intCast(encoded_index),
740 .first = input[16..48].*,
741 .second = input[48..80].*,
742 };
743 try validateNode(value, expected_digest, expected);
744 return value;
745 }
746
747 fn validateNode(
748 value: Node,
749 expected_digest: os.abi.Digest,
750 expected: Expected,
751 ) types.Error!void {
752 try validateDigest(value.first);
753 const actual = switch (value.kind) {
754 .leaf => leaf: {
755 if (value.level != 0 or !allZero(value.second)) {
756 return error.RootObjectCorrupt;
757 }
758 break :leaf canon.leaf(value.index, value.first);
759 },
760 .branch => branch: {
761 if (value.index != 0 or value.level >= canon.tree_levels) {
762 return error.RootObjectCorrupt;
763 }
764 try validateDigest(value.second);
765 break :branch canon.node(value.level, value.first, value.second);
766 },
767 };
768 if (!sameDigest(actual, expected_digest)) return error.RootObjectCorrupt;
769 switch (expected) {
770 .leaf => |index| if (value.kind != .leaf or value.index != index) {
771 return error.RootObjectCorrupt;
772 },
773 .branch => |level| if (value.kind != .branch or value.level != level) {
774 return error.RootObjectCorrupt;
775 },
776 }
777 }
778
779 fn pageAt(
780 bytes: []align(types.page_bytes) const u8,
781 index: usize,
782 ) *const [types.page_bytes]u8 {
783 const start = index * types.page_bytes;
784 std.debug.assert(start + types.page_bytes <= bytes.len);
785 return @ptrCast(bytes[start..][0..types.page_bytes]);
786 }
787
788 fn validateDeltaStorage(
789 indices: []const u16,
790 pages: []const u8,
791 ) types.Error!void {
792 try validateDeltaIndices(indices);
793 const expected = std.math.mul(
794 usize,
795 indices.len,
796 types.page_bytes,
797 ) catch return error.DeltaStorageMismatch;
798 if (pages.len != expected) return error.DeltaStorageMismatch;
799 }
800
801 fn validateDeltaIndices(indices: []const u16) types.Error!void {
802 if (indices.len > types.page_count) return error.DeltaCapacityExceeded;
803 var previous: ?u16 = null;
804 for (indices) |index| {
805 if (index >= types.page_count) return error.DeltaIndicesInvalid;
806 if (previous) |value| {
807 if (index <= value) return error.DeltaIndicesInvalid;
808 }
809 previous = index;
810 }
811 }
812
813 fn validateDigest(value: os.abi.Digest) types.Error!void {
814 os.abi.wire.validateDigest(value) catch return error.RootObjectCorrupt;
815 }
816
817 fn sameDigest(left: os.abi.Digest, right: os.abi.Digest) bool {
818 return std.mem.eql(u8, &left, &right);
819 }
820
821 fn allZero(value: os.abi.Digest) bool {
822 return os.abi.wire.allZero(&value);
823 }
824
825 comptime {
826 std.debug.assert(types.node_bytes == 80);
827 std.debug.assert(canon.tree_levels <= std.math.maxInt(u8));
828 std.debug.assert(canon.page_count <= std.math.maxInt(u16) + 1);
829 }