lib/closure/src/limits.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const schema = @import("schema/root.zig");
2 const project = @import("project/root.zig");
3 const std = @import("std");
4
5 pub const nodes_max: usize = 64;
6 pub const edges_max: usize = 128;
7 pub const artifacts_max: usize = 32;
8 pub const ranges_max: usize = 128;
9 pub const digests_max: usize = 128;
10 pub const provenance_parents_max: usize = 128;
11 pub const source_records_max: usize = 64;
12 pub const build_records_max: usize = 64;
13 pub const authorities_max: usize = 64;
14 pub const lineage_references_max: usize = 64;
15 pub const service_descriptors_max: usize = 16;
16 pub const residual_roots_max: usize = 64;
17 pub const claims_max: usize = 8;
18 pub const claim_nodes_max: usize = 128;
19 pub const receipt_bytes_max: usize = 512 * 1_024;
20 pub const storage_alignment: usize = 16;
21 pub const header_bytes: usize = 512;
22 pub const slot_header_bytes: usize = 256;
23
24 pub const Limits = struct {
25 nodes: usize = nodes_max,
26 edges: usize = edges_max,
27 artifacts: usize = artifacts_max,
28 ranges: usize = ranges_max,
29 digests: usize = digests_max,
30 provenance_parents: usize = provenance_parents_max,
31 source_records: usize = source_records_max,
32 build_records: usize = build_records_max,
33 authorities: usize = authorities_max,
34 lineage_references: usize = lineage_references_max,
35 service_descriptors: usize = service_descriptors_max,
36 residual_roots: usize = residual_roots_max,
37 claims: usize = claims_max,
38 claim_nodes: usize = claim_nodes_max,
39 receipt_bytes: usize = receipt_bytes_max,
40 };
41
42 pub const SlotLayout = struct {
43 base: usize,
44 header: usize,
45 nodes: usize,
46 edges: usize,
47 artifacts: usize,
48 ranges: usize,
49 digests: usize,
50 provenance_parents: usize,
51 source_records: usize,
52 build_records: usize,
53 authorities: usize,
54 lineage_references: usize,
55 service_descriptors: usize,
56 residual_roots: usize,
57 claims: usize,
58 claim_nodes: usize,
59 end: usize,
60 };
61
62 pub const Layout = struct {
63 header: usize,
64 slots: [2]SlotLayout,
65 visited: usize,
66 queue: usize,
67 receipt: usize,
68 storage_bytes: usize,
69 };
70
71 pub const CapacityError = error{
72 EmptyLimit,
73 NodeCapacityExceeded,
74 EdgeCapacityExceeded,
75 ArtifactCapacityExceeded,
76 RangeCapacityExceeded,
77 DigestCapacityExceeded,
78 ProvenanceParentCapacityExceeded,
79 SourceRecordCapacityExceeded,
80 BuildRecordCapacityExceeded,
81 AuthorityCapacityExceeded,
82 LineageReferenceCapacityExceeded,
83 ServiceDescriptorCapacityExceeded,
84 ResidualRootCapacityExceeded,
85 ClaimCapacityExceeded,
86 ClaimNodeCapacityExceeded,
87 ReceiptCapacityExceeded,
88 CapacityArithmeticOverflow,
89 };
90
91 pub const Capacity = struct {
92 nodes: usize,
93 edges: usize,
94 artifacts: usize,
95 ranges: usize,
96 digests: usize,
97 provenance_parents: usize,
98 source_records: usize,
99 build_records: usize,
100 authorities: usize,
101 lineage_references: usize,
102 service_descriptors: usize,
103 residual_roots: usize,
104 claims: usize,
105 claim_nodes: usize,
106 receipt_bytes: usize,
107 projection_steps_max: usize,
108 receipt_rows_max: usize,
109 layout: Layout,
110 storage_bytes: usize,
111
112 pub const DeriveError: type = CapacityError;
113
114 pub fn derive(requested: Limits) DeriveError!Capacity {
115 try validate(requested);
116 const layout = try deriveLayout(requested);
117 const projection_steps = project.maximumWork(.{
118 .nodes = requested.nodes,
119 .edges = requested.edges,
120 .artifacts = requested.artifacts,
121 .ranges = requested.ranges,
122 .digests = requested.digests,
123 .provenance_parents = requested.provenance_parents,
124 .source_records = requested.source_records,
125 .build_records = requested.build_records,
126 .authorities = requested.authorities,
127 .lineage_references = requested.lineage_references,
128 .service_descriptors = requested.service_descriptors,
129 .residual_roots = requested.residual_roots,
130 .claims = requested.claims,
131 .claim_nodes = requested.claim_nodes,
132 }) catch return error.CapacityArithmeticOverflow;
133 return .{
134 .nodes = requested.nodes,
135 .edges = requested.edges,
136 .artifacts = requested.artifacts,
137 .ranges = requested.ranges,
138 .digests = requested.digests,
139 .provenance_parents = requested.provenance_parents,
140 .source_records = requested.source_records,
141 .build_records = requested.build_records,
142 .authorities = requested.authorities,
143 .lineage_references = requested.lineage_references,
144 .service_descriptors = requested.service_descriptors,
145 .residual_roots = requested.residual_roots,
146 .claims = requested.claims,
147 .claim_nodes = requested.claim_nodes,
148 .receipt_bytes = requested.receipt_bytes,
149 .projection_steps_max = projection_steps,
150 .receipt_rows_max = try receiptRows(requested),
151 .layout = layout,
152 .storage_bytes = layout.storage_bytes,
153 };
154 }
155 };
156
157 fn deriveLayout(requested: Limits) CapacityError!Layout {
158 var cursor = try aligned(header_bytes, storage_alignment);
159 const first = try slotLayout(cursor, requested);
160 cursor = try aligned(first.end, storage_alignment);
161 const second = try slotLayout(cursor, requested);
162 cursor = try aligned(second.end, storage_alignment);
163 const visited = cursor;
164 cursor = try added(cursor, requested.nodes);
165 cursor = try aligned(cursor, @alignOf(u32));
166 const queue = cursor;
167 cursor = try segment(cursor, requested.nodes, @sizeOf(u32));
168 cursor = try aligned(cursor, storage_alignment);
169 const receipt = cursor;
170 cursor = try added(cursor, requested.receipt_bytes);
171 cursor = try aligned(cursor, storage_alignment);
172 return .{
173 .header = 0,
174 .slots = .{ first, second },
175 .visited = visited,
176 .queue = queue,
177 .receipt = receipt,
178 .storage_bytes = cursor,
179 };
180 }
181
182 fn receiptRows(requested: Limits) CapacityError!usize {
183 return total(&.{
184 requested.nodes,
185 requested.edges,
186 requested.artifacts,
187 requested.ranges,
188 requested.digests,
189 requested.provenance_parents,
190 requested.source_records,
191 requested.build_records,
192 requested.authorities,
193 requested.lineage_references,
194 requested.service_descriptors,
195 requested.residual_roots,
196 requested.claims,
197 requested.claim_nodes,
198 1,
199 });
200 }
201
202 fn validate(requested: Limits) Capacity.DeriveError!void {
203 if (requested.nodes == 0 or
204 requested.edges == 0 or
205 requested.artifacts == 0 or
206 requested.ranges == 0 or
207 requested.digests == 0 or
208 requested.provenance_parents == 0 or
209 requested.source_records == 0 or
210 requested.build_records == 0 or
211 requested.authorities == 0 or
212 requested.lineage_references == 0 or
213 requested.service_descriptors == 0 or
214 requested.residual_roots == 0 or
215 requested.claims == 0 or
216 requested.claim_nodes == 0 or
217 requested.receipt_bytes == 0)
218 {
219 return error.EmptyLimit;
220 }
221 if (requested.nodes > nodes_max) return error.NodeCapacityExceeded;
222 if (requested.edges > edges_max) return error.EdgeCapacityExceeded;
223 if (requested.artifacts > artifacts_max) {
224 return error.ArtifactCapacityExceeded;
225 }
226 if (requested.ranges > ranges_max) return error.RangeCapacityExceeded;
227 if (requested.digests > digests_max) return error.DigestCapacityExceeded;
228 if (requested.provenance_parents > provenance_parents_max) {
229 return error.ProvenanceParentCapacityExceeded;
230 }
231 if (requested.source_records > source_records_max) {
232 return error.SourceRecordCapacityExceeded;
233 }
234 if (requested.build_records > build_records_max) {
235 return error.BuildRecordCapacityExceeded;
236 }
237 if (requested.authorities > authorities_max) {
238 return error.AuthorityCapacityExceeded;
239 }
240 if (requested.lineage_references > lineage_references_max) {
241 return error.LineageReferenceCapacityExceeded;
242 }
243 if (requested.service_descriptors > service_descriptors_max) {
244 return error.ServiceDescriptorCapacityExceeded;
245 }
246 if (requested.residual_roots > residual_roots_max) {
247 return error.ResidualRootCapacityExceeded;
248 }
249 if (requested.claims > claims_max) return error.ClaimCapacityExceeded;
250 if (requested.claim_nodes > claim_nodes_max) {
251 return error.ClaimNodeCapacityExceeded;
252 }
253 if (requested.receipt_bytes > receipt_bytes_max) {
254 return error.ReceiptCapacityExceeded;
255 }
256 }
257
258 fn slotLayout(
259 base: usize,
260 requested: Limits,
261 ) Capacity.DeriveError!SlotLayout {
262 var cursor = base;
263 const header = cursor;
264 cursor = try added(cursor, slot_header_bytes);
265 const nodes = try start(&cursor, requested.nodes, schema.Node);
266 const edges = try start(&cursor, requested.edges, schema.Edge);
267 const artifacts = try start(&cursor, requested.artifacts, schema.Artifact);
268 const ranges = try start(&cursor, requested.ranges, schema.ByteRange);
269 const digests = try start(&cursor, requested.digests, schema.DigestRecord);
270 const provenance_parents = try start(
271 &cursor,
272 requested.provenance_parents,
273 schema.ProvenanceParent,
274 );
275 const source_records = try start(&cursor, requested.source_records, schema.SourceRecord);
276 const build_records = try start(&cursor, requested.build_records, schema.BuildRecord);
277 const authorities = try start(&cursor, requested.authorities, schema.Authority);
278 const lineage_references = try start(
279 &cursor,
280 requested.lineage_references,
281 schema.LineageReference,
282 );
283 const service_descriptors = try start(
284 &cursor,
285 requested.service_descriptors,
286 schema.ServiceDescriptor,
287 );
288 const residual_roots = try start(&cursor, requested.residual_roots, schema.ResidualRoot);
289 const claims = try start(&cursor, requested.claims, schema.Claim);
290 const claim_nodes = try start(&cursor, requested.claim_nodes, schema.ClaimNode);
291 return .{
292 .base = base,
293 .header = header,
294 .nodes = nodes,
295 .edges = edges,
296 .artifacts = artifacts,
297 .ranges = ranges,
298 .digests = digests,
299 .provenance_parents = provenance_parents,
300 .source_records = source_records,
301 .build_records = build_records,
302 .authorities = authorities,
303 .lineage_references = lineage_references,
304 .service_descriptors = service_descriptors,
305 .residual_roots = residual_roots,
306 .claims = claims,
307 .claim_nodes = claim_nodes,
308 .end = try aligned(cursor, storage_alignment),
309 };
310 }
311
312 fn start(
313 cursor: *usize,
314 count: usize,
315 comptime T: type,
316 ) Capacity.DeriveError!usize {
317 cursor.* = try aligned(cursor.*, @alignOf(T));
318 const offset = cursor.*;
319 cursor.* = try segment(cursor.*, count, @sizeOf(T));
320 return offset;
321 }
322
323 fn segment(
324 offset: usize,
325 count: usize,
326 size: usize,
327 ) Capacity.DeriveError!usize {
328 return added(offset, try multiplied(count, size));
329 }
330
331 fn aligned(
332 value: usize,
333 alignment: usize,
334 ) Capacity.DeriveError!usize {
335 const extra = alignment - 1;
336 const sum = try added(value, extra);
337 return sum & ~extra;
338 }
339
340 fn multiplied(
341 left: usize,
342 right: usize,
343 ) Capacity.DeriveError!usize {
344 return std.math.mul(usize, left, right) catch
345 error.CapacityArithmeticOverflow;
346 }
347
348 fn added(
349 left: usize,
350 right: usize,
351 ) Capacity.DeriveError!usize {
352 return std.math.add(usize, left, right) catch
353 error.CapacityArithmeticOverflow;
354 }
355
356 fn total(values: []const usize) CapacityError!usize {
357 var result: usize = 0;
358 for (values) |value| result = try added(result, value);
359 return result;
360 }
361
362 test "maximum closure capacity derives two disjoint slots and scratch" {
363 const capacity = try Capacity.derive(.{});
364 try std.testing.expectEqual(
365 @as(usize, 1_008_874),
366 capacity.projection_steps_max,
367 );
368 try std.testing.expect(
369 capacity.layout.slots[0].end <=
370 capacity.layout.slots[1].base,
371 );
372 try std.testing.expect(
373 capacity.layout.slots[1].end <= capacity.layout.visited,
374 );
375 try std.testing.expect(
376 capacity.layout.receipt + capacity.receipt_bytes <=
377 capacity.storage_bytes,
378 );
379 try std.testing.expectEqual(capacity.storage_bytes, capacity.layout.storage_bytes);
380 }
381
382 test "independent closure capacities reject maximum plus one" {
383 var requested = Limits{};
384 inline for (.{
385 .{ "nodes", error.NodeCapacityExceeded },
386 .{ "edges", error.EdgeCapacityExceeded },
387 .{ "artifacts", error.ArtifactCapacityExceeded },
388 .{ "ranges", error.RangeCapacityExceeded },
389 .{ "digests", error.DigestCapacityExceeded },
390 .{
391 "provenance_parents",
392 error.ProvenanceParentCapacityExceeded,
393 },
394 .{ "source_records", error.SourceRecordCapacityExceeded },
395 .{ "build_records", error.BuildRecordCapacityExceeded },
396 .{ "authorities", error.AuthorityCapacityExceeded },
397 .{
398 "lineage_references",
399 error.LineageReferenceCapacityExceeded,
400 },
401 .{
402 "service_descriptors",
403 error.ServiceDescriptorCapacityExceeded,
404 },
405 .{ "residual_roots", error.ResidualRootCapacityExceeded },
406 .{ "claims", error.ClaimCapacityExceeded },
407 .{ "claim_nodes", error.ClaimNodeCapacityExceeded },
408 .{ "receipt_bytes", error.ReceiptCapacityExceeded },
409 }) |case| {
410 requested = .{};
411 @field(requested, case[0]) += 1;
412 try std.testing.expectError(case[1], Capacity.derive(requested));
413 }
414 }