lib/choir/src/core/operation/storage.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_observe = @import("alloc_observe");
3 const alloc_phase = @import("alloc_phase");
4
5 const Allocator = std.mem.Allocator;
6 const pool_items_per_chunk: usize = 32;
7
8 pub const Handle = struct {
9 bytes: [*]u8,
10 len: usize,
11 alignment: std.mem.Alignment,
12
13 pub fn deinit(self: *Handle, allocator: Allocator) void {
14 allocator.rawFree(self.bytes[0..self.len], self.alignment, @returnAddress());
15 self.* = undefined;
16 }
17 };
18
19 const segment_count: usize = 8;
20
21 pub const Storage = struct {
22 pub const claim: alloc_phase.capacity.Declaration = .{
23 .source = .{
24 .id = "choir.operation_fixed_storage",
25 .kind = .phase_static,
26 .limit_source = .caller,
27 .storage = .{
28 .covered = &.{
29 .{
30 .id = "one_exact_operation_header_with_context_tracking_li_8dbfeaab8a9b",
31 .lifetime = .steady,
32 .detail = "one exact Operation header with context tracking links and initial structural region",
33 },
34 .{
35 .id = "initial_operand_values_result_types_use_records_val_dfde1e9abc4c",
36 .lifetime = .steady,
37 .detail = "initial operand values, result types, use records, values, regions, and successors",
38 },
39 .{
40 .id = "exact_registered_property_bytes_embedded_in_the_str_4e71d9c026ef",
41 .lifetime = .steady,
42 .detail = "exact registered property bytes embedded in the structural region",
43 },
44 },
45 .excluded = &.{
46 "attributes, nested property allocations, blocks, and region contents",
47 "later operand and successor replacement spill storage",
48 "profiling instrumentation and allocator implementation state",
49 },
50 },
51 .capacity = .{
52 .inputs = &.{},
53 .type_selectors = &.{},
54 .nodes = &.{
55 .{ .constant = 0 },
56 },
57 .assertions = &.{.{
58 .scope = .closure_total,
59 .measure = .retained,
60 .relation = .exact,
61 .expression = 0,
62 }},
63 },
64 .overload = .{
65 .kind = .reject_before_seal,
66 .detail = "capacity arithmetic or allocation failure returns before the Operation header is initialized or storage is sealed",
67 },
68 .risks = .{
69 .transitive = .{
70 .status = .open,
71 .detail = "the parent mutable Operation retains allocator authority for explicitly excluded attributes, nested owners, and later spills",
72 },
73 .foreign = .{
74 .status = .open,
75 .detail = "dialect property hooks may traverse state outside the embedded property byte region",
76 },
77 },
78 .obligations = &.{
79 .{ .key = "choir_operation_storage_capacity", .role = .capacity_model },
80 .{ .key = "choir_operation_storage_acquisition", .role = .custom },
81 .{ .key = "choir_operation_storage_boundary", .role = .overload },
82 .{ .key = "choir_operation_storage_oom", .role = .overload },
83 .{ .key = "choir_operation_storage_integration", .role = .custom },
84 .{ .key = "choir_operation_tracking_static", .role = .custom },
85 .{ .key = "choir_operation_storage_spill", .role = .custom },
86 },
87 },
88 .bindings = .{
89 .owner = @This(),
90 .seal = .{
91 .family = alloc_phase.capacity.selector(@This().activate),
92 .premise = .{
93 .class = .checked_semantic_fact,
94 .authority = .checker,
95 },
96 },
97 .teardown = .{
98 .family = alloc_phase.capacity.selector(@This().deinit),
99 .premise = .{
100 .class = .checked_semantic_fact,
101 .authority = .checker,
102 },
103 },
104 },
105 };
106
107 pub const Segment = struct {
108 count: usize,
109 element_bytes: usize,
110 alignment: std.mem.Alignment,
111 };
112
113 pub const Limits = struct {
114 segments: [segment_count]Segment,
115 };
116
117 pub const Capacity = struct {
118 total_bytes: usize,
119 allocation_alignment: std.mem.Alignment,
120
121 pub fn derive(limits: Limits) error{CapacityOverflow}!Capacity {
122 var cursor: usize = 0;
123 var alignment: usize = 1;
124 for (limits.segments) |segment| {
125 const bytes = std.math.mul(
126 usize,
127 segment.count,
128 segment.element_bytes,
129 ) catch return error.CapacityOverflow;
130 _ = try placeBytes(
131 bytes,
132 segment.alignment.toByteUnits(),
133 &cursor,
134 &alignment,
135 );
136 }
137 return .{
138 .total_bytes = cursor,
139 .allocation_alignment = .fromByteUnits(alignment),
140 };
141 }
142 };
143
144 phase: alloc_phase.capacity.Phase,
145 capacity: Capacity,
146 bytes: [*]u8,
147
148 pub fn init(allocator: Allocator, limits: Limits) !Storage {
149 const capacity = try Capacity.derive(limits);
150 const bytes = allocator.rawAlloc(
151 capacity.total_bytes,
152 capacity.allocation_alignment,
153 @returnAddress(),
154 ) orelse return error.OutOfMemory;
155 return .{
156 .phase = .initialization,
157 .capacity = capacity,
158 .bytes = bytes,
159 };
160 }
161
162 pub fn activate(self: *Storage) void {
163 std.debug.assert(self.phase == .initialization);
164 self.phase = .steady;
165 }
166
167 pub fn status(self: *const Storage) alloc_phase.capacity.Phase {
168 return self.phase;
169 }
170
171 pub fn deinit(self: *Storage, allocator: Allocator) void {
172 std.debug.assert(self.phase != .teardown);
173 self.phase = .teardown;
174 var handle = self.storageHandle();
175 handle.deinit(allocator);
176 self.* = undefined;
177 }
178
179 fn storageHandle(self: *const Storage) Handle {
180 return .{
181 .bytes = self.bytes,
182 .len = self.capacity.total_bytes,
183 .alignment = self.capacity.allocation_alignment,
184 };
185 }
186 };
187
188 comptime {
189 alloc_phase.capacity.requireAllocatorExactOwnerShape(Storage);
190 }
191
192 pub fn PoolAllocator(
193 comptime first_capacity: Storage.Capacity,
194 comptime second_capacity: Storage.Capacity,
195 comptime third_capacity: Storage.Capacity,
196 comptime fourth_capacity: Storage.Capacity,
197 ) type {
198 comptime {
199 std.debug.assert(first_capacity.total_bytes != second_capacity.total_bytes);
200 std.debug.assert(first_capacity.total_bytes != third_capacity.total_bytes);
201 std.debug.assert(first_capacity.total_bytes != fourth_capacity.total_bytes);
202 std.debug.assert(second_capacity.total_bytes != third_capacity.total_bytes);
203 std.debug.assert(second_capacity.total_bytes != fourth_capacity.total_bytes);
204 std.debug.assert(third_capacity.total_bytes != fourth_capacity.total_bytes);
205 }
206
207 const FirstPool = FixedPool(first_capacity);
208 const SecondPool = FixedPool(second_capacity);
209 const ThirdPool = FixedPool(third_capacity);
210 const FourthPool = FixedPool(fourth_capacity);
211 return struct {
212 backing: Allocator,
213 first: FirstPool = .{},
214 second: SecondPool = .{},
215 third: ThirdPool = .{},
216 fourth: FourthPool = .{},
217 observation_id: if (alloc_observe.enabled) u64 else void,
218
219 const Self = @This();
220 const Class = enum { first, second, third, fourth };
221 pub const items_per_chunk: usize = pool_items_per_chunk;
222 pub const first_chunk_bytes: usize = FirstPool.chunk_bytes;
223 pub const second_chunk_bytes: usize = SecondPool.chunk_bytes;
224 pub const third_chunk_bytes: usize = ThirdPool.chunk_bytes;
225 pub const fourth_chunk_bytes: usize = FourthPool.chunk_bytes;
226
227 pub fn init(backing: Allocator) Self {
228 return .{
229 .backing = backing,
230 .observation_id = if (comptime alloc_observe.enabled)
231 alloc_observe.producerId()
232 else {},
233 };
234 }
235
236 pub fn deinit(self: *Self) void {
237 self.first.deinit(self.backing);
238 self.second.deinit(self.backing);
239 self.third.deinit(self.backing);
240 self.fourth.deinit(self.backing);
241 self.* = undefined;
242 }
243
244 pub fn allocator(self: *Self) Allocator {
245 return .{
246 .ptr = self,
247 .vtable = &.{
248 .alloc = alloc,
249 .resize = resize,
250 .remap = remap,
251 .free = free,
252 },
253 };
254 }
255
256 fn alloc(
257 context: *anyopaque,
258 len: usize,
259 alignment: std.mem.Alignment,
260 ret_addr: usize,
261 ) ?[*]u8 {
262 const self: *Self = @ptrCast(@alignCast(context));
263 var span = self.begin(.alloc, 0, 0, len, alignment, ret_addr);
264 const result = if (classify(len, alignment)) |class| switch (class) {
265 .first => self.first.create(self.backing) catch null,
266 .second => self.second.create(self.backing) catch null,
267 .third => self.third.create(self.backing) catch null,
268 .fourth => self.fourth.create(self.backing) catch null,
269 } else self.backing.rawAlloc(len, alignment, ret_addr);
270 span.finish(.{
271 .address = if (result) |ptr| @intFromPtr(ptr) else 0,
272 .succeeded = result != null,
273 });
274 return result;
275 }
276
277 fn begin(
278 self: *const Self,
279 operation: alloc_observe.Operation,
280 old_address: usize,
281 old_len: usize,
282 len: usize,
283 alignment: std.mem.Alignment,
284 ret_addr: usize,
285 ) alloc_observe.Span {
286 return alloc_observe.begin(
287 if (comptime alloc_observe.enabled) self.observation_id else 0,
288 .pool,
289 operation,
290 old_address,
291 old_len,
292 len,
293 alignment.toByteUnits(),
294 ret_addr,
295 );
296 }
297
298 fn resize(
299 context: *anyopaque,
300 memory: []u8,
301 alignment: std.mem.Alignment,
302 new_len: usize,
303 ret_addr: usize,
304 ) bool {
305 const self: *Self = @ptrCast(@alignCast(context));
306 var span = self.begin(
307 .resize,
308 @intFromPtr(memory.ptr),
309 memory.len,
310 new_len,
311 alignment,
312 ret_addr,
313 );
314 const succeeded = if (memory.len == new_len)
315 true
316 else if (isClassLength(memory.len) or isClassLength(new_len))
317 false
318 else
319 self.backing.rawResize(memory, alignment, new_len, ret_addr);
320 span.finish(.{
321 .address = if (succeeded) @intFromPtr(memory.ptr) else 0,
322 .succeeded = succeeded,
323 });
324 return succeeded;
325 }
326
327 fn remap(
328 context: *anyopaque,
329 memory: []u8,
330 alignment: std.mem.Alignment,
331 new_len: usize,
332 ret_addr: usize,
333 ) ?[*]u8 {
334 const self: *Self = @ptrCast(@alignCast(context));
335 var span = self.begin(
336 .remap,
337 @intFromPtr(memory.ptr),
338 memory.len,
339 new_len,
340 alignment,
341 ret_addr,
342 );
343 const result = if (memory.len == new_len)
344 memory.ptr
345 else if (isClassLength(memory.len) or isClassLength(new_len))
346 null
347 else
348 self.backing.rawRemap(memory, alignment, new_len, ret_addr);
349 span.finish(.{
350 .address = if (result) |ptr| @intFromPtr(ptr) else 0,
351 .succeeded = result != null,
352 });
353 return result;
354 }
355
356 fn free(
357 context: *anyopaque,
358 memory: []u8,
359 alignment: std.mem.Alignment,
360 ret_addr: usize,
361 ) void {
362 const self: *Self = @ptrCast(@alignCast(context));
363 var span = self.begin(
364 .free,
365 @intFromPtr(memory.ptr),
366 memory.len,
367 0,
368 alignment,
369 ret_addr,
370 );
371 if (classify(memory.len, alignment)) |class| {
372 switch (class) {
373 .first => self.first.destroy(memory.ptr),
374 .second => self.second.destroy(memory.ptr),
375 .third => self.third.destroy(memory.ptr),
376 .fourth => self.fourth.destroy(memory.ptr),
377 }
378 } else {
379 self.backing.rawFree(memory, alignment, ret_addr);
380 }
381 span.finish(.{
382 .address = @intFromPtr(memory.ptr),
383 .succeeded = true,
384 });
385 }
386
387 fn classify(len: usize, alignment: std.mem.Alignment) ?Class {
388 if (len == first_capacity.total_bytes and
389 alignment.compare(.lte, first_capacity.allocation_alignment)) return .first;
390 if (len == second_capacity.total_bytes and
391 alignment.compare(.lte, second_capacity.allocation_alignment)) return .second;
392 if (len == third_capacity.total_bytes and
393 alignment.compare(.lte, third_capacity.allocation_alignment)) return .third;
394 if (len == fourth_capacity.total_bytes and
395 alignment.compare(.lte, fourth_capacity.allocation_alignment)) return .fourth;
396 return null;
397 }
398
399 fn isClassLength(len: usize) bool {
400 return len == first_capacity.total_bytes or
401 len == second_capacity.total_bytes or
402 len == third_capacity.total_bytes or
403 len == fourth_capacity.total_bytes;
404 }
405 };
406 }
407
408 fn FixedPool(comptime capacity: Storage.Capacity) type {
409 const alignment = capacity.allocation_alignment.toByteUnits();
410 comptime {
411 std.debug.assert(capacity.total_bytes >= @sizeOf(?*anyopaque));
412 std.debug.assert(alignment >= @alignOf(?*anyopaque));
413 }
414
415 return struct {
416 chunks: ?*Chunk = null,
417 free_list: ?*FreeNode = null,
418
419 const Self = @This();
420 const Slot = struct {
421 bytes: [capacity.total_bytes]u8 align(alignment),
422 };
423 const Chunk = struct {
424 next: ?*Chunk,
425 used: usize,
426 slots: [pool_items_per_chunk]Slot,
427 };
428 const FreeNode = struct {
429 next: ?*FreeNode,
430 };
431 const chunk_bytes: usize = @sizeOf(Chunk);
432
433 comptime {
434 std.debug.assert(@sizeOf(Slot) == std.mem.alignForward(usize, capacity.total_bytes, alignment));
435 std.debug.assert(@sizeOf(Slot) >= capacity.total_bytes);
436 std.debug.assert(@alignOf(Slot) == alignment);
437 }
438
439 fn create(self: *Self, allocator: Allocator) Allocator.Error![*]u8 {
440 if (self.free_list) |node| {
441 self.free_list = node.next;
442 const slot: *Slot = @ptrCast(@alignCast(node));
443 slot.* = undefined;
444 return @ptrCast(slot);
445 }
446
447 const chunk = self.chunks orelse return try self.addChunk(allocator);
448 if (chunk.used == pool_items_per_chunk) return try self.addChunk(allocator);
449 const slot = &chunk.slots[chunk.used];
450 chunk.used += 1;
451 slot.* = undefined;
452 return @ptrCast(slot);
453 }
454
455 fn destroy(self: *Self, bytes: [*]u8) void {
456 const slot: *Slot = @ptrCast(@alignCast(bytes));
457 slot.* = undefined;
458 const node: *FreeNode = @ptrCast(slot);
459 node.* = .{ .next = self.free_list };
460 self.free_list = node;
461 }
462
463 fn deinit(self: *Self, allocator: Allocator) void {
464 var chunk = self.chunks;
465 while (chunk) |current| {
466 chunk = current.next;
467 allocator.destroy(current);
468 }
469 self.* = undefined;
470 }
471
472 fn addChunk(self: *Self, allocator: Allocator) Allocator.Error![*]u8 {
473 const chunk = try allocator.create(Chunk);
474 chunk.* = .{
475 .next = self.chunks,
476 .used = 1,
477 .slots = undefined,
478 };
479 self.chunks = chunk;
480 const slot = &chunk.slots[0];
481 slot.* = undefined;
482 return @ptrCast(slot);
483 }
484 };
485 }
486
487 pub fn List(comptime T: type) type {
488 return struct {
489 items: []T = &.{},
490 capacity: usize = 0,
491
492 const Self = @This();
493
494 pub fn init(storage: []T) Self {
495 if (storage.len == 0) return .{};
496 return .{ .items = storage[0..0], .capacity = storage.len };
497 }
498
499 pub fn appendAssumeCapacity(self: *Self, item: T) void {
500 std.debug.assert(self.items.len < self.capacity);
501 const index = self.items.len;
502 const next_len = std.math.add(usize, index, 1) catch unreachable;
503 self.items = self.items.ptr[0..next_len];
504 self.items[index] = item;
505 }
506
507 pub fn appendSliceAssumeCapacity(self: *Self, items: []const T) void {
508 const remaining = std.math.sub(usize, self.capacity, self.items.len) catch unreachable;
509 std.debug.assert(items.len <= remaining);
510 const previous_len = self.items.len;
511 const next_len = std.math.add(usize, previous_len, items.len) catch unreachable;
512 self.items = self.items.ptr[0..next_len];
513 @memcpy(self.items[previous_len..], items);
514 }
515
516 pub fn clearRetainingCapacity(self: *Self) void {
517 self.items = self.items.ptr[0..0];
518 }
519 };
520 }
521
522 pub fn Plan(
523 comptime Header: type,
524 comptime OperandValue: type,
525 comptime ResultType: type,
526 comptime Operand: type,
527 comptime Result: type,
528 comptime Region: type,
529 comptime Successor: type,
530 ) type {
531 return struct {
532 pub const Limits = struct {
533 operands: usize,
534 results: usize,
535 regions: usize,
536 successors: usize,
537 properties: usize,
538 properties_alignment: std.mem.Alignment,
539 };
540
541 pub const Capacity = struct {
542 pub fn derive(limits: Limits) error{CapacityOverflow}!Storage.Capacity {
543 return try Storage.Capacity.derive(storageLimits(limits));
544 }
545 };
546
547 const Layout = struct {
548 operands: usize,
549 results: usize,
550 regions: usize,
551 successors: usize,
552 properties: usize,
553 header_offset: usize,
554 operand_values_offset: usize,
555 result_types_offset: usize,
556 operands_offset: usize,
557 results_offset: usize,
558 regions_offset: usize,
559 successors_offset: usize,
560 properties_offset: usize,
561 total_bytes: usize,
562 allocation_alignment: std.mem.Alignment,
563
564 fn derive(limits: Limits) error{CapacityOverflow}!Layout {
565 var cursor: usize = 0;
566 var alignment: usize = 1;
567 const header_offset = try place(Header, 1, &cursor, &alignment);
568 const operand_values_offset = try place(OperandValue, limits.operands, &cursor, &alignment);
569 const result_types_offset = try place(ResultType, limits.results, &cursor, &alignment);
570 const operands_offset = try place(Operand, limits.operands, &cursor, &alignment);
571 const results_offset = try place(Result, limits.results, &cursor, &alignment);
572 const regions_offset = try place(Region, limits.regions, &cursor, &alignment);
573 const successors_offset = try place(Successor, limits.successors, &cursor, &alignment);
574 const properties_offset = try placeBytes(
575 limits.properties,
576 limits.properties_alignment.toByteUnits(),
577 &cursor,
578 &alignment,
579 );
580 return .{
581 .operands = limits.operands,
582 .results = limits.results,
583 .regions = limits.regions,
584 .successors = limits.successors,
585 .properties = limits.properties,
586 .header_offset = header_offset,
587 .operand_values_offset = operand_values_offset,
588 .result_types_offset = result_types_offset,
589 .operands_offset = operands_offset,
590 .results_offset = results_offset,
591 .regions_offset = regions_offset,
592 .successors_offset = successors_offset,
593 .properties_offset = properties_offset,
594 .total_bytes = cursor,
595 .allocation_alignment = .fromByteUnits(alignment),
596 };
597 }
598 };
599
600 pub const Regions = struct {
601 header: *Header,
602 operand_values: []OperandValue,
603 result_types: []ResultType,
604 operands: []Operand,
605 results: []Result,
606 regions: []Region,
607 successors: []Successor,
608 properties: []u8,
609 };
610
611 pub const Allocation = struct {
612 storage: Storage,
613 regions: Regions,
614 };
615
616 pub fn init(allocator: Allocator, limits: Limits) !Allocation {
617 var storage = try Storage.init(allocator, storageLimits(limits));
618 errdefer storage.deinit(allocator);
619 return .{
620 .storage = storage,
621 .regions = try acquire(&storage, limits),
622 };
623 }
624
625 fn storageLimits(limits: Limits) Storage.Limits {
626 return .{ .segments = .{
627 .{ .count = 1, .element_bytes = @sizeOf(Header), .alignment = .fromByteUnits(@alignOf(Header)) },
628 .{ .count = limits.operands, .element_bytes = @sizeOf(OperandValue), .alignment = .fromByteUnits(@alignOf(OperandValue)) },
629 .{ .count = limits.results, .element_bytes = @sizeOf(ResultType), .alignment = .fromByteUnits(@alignOf(ResultType)) },
630 .{ .count = limits.operands, .element_bytes = @sizeOf(Operand), .alignment = .fromByteUnits(@alignOf(Operand)) },
631 .{ .count = limits.results, .element_bytes = @sizeOf(Result), .alignment = .fromByteUnits(@alignOf(Result)) },
632 .{ .count = limits.regions, .element_bytes = @sizeOf(Region), .alignment = .fromByteUnits(@alignOf(Region)) },
633 .{ .count = limits.successors, .element_bytes = @sizeOf(Successor), .alignment = .fromByteUnits(@alignOf(Successor)) },
634 .{ .count = limits.properties, .element_bytes = 1, .alignment = limits.properties_alignment },
635 } };
636 }
637
638 fn acquire(storage: *Storage, limits: Limits) error{CapacityOverflow}!Regions {
639 std.debug.assert(storage.phase == .initialization);
640 const layout = try Layout.derive(limits);
641 std.debug.assert(layout.total_bytes == storage.capacity.total_bytes);
642 std.debug.assert(layout.allocation_alignment == storage.capacity.allocation_alignment);
643 const handle = storage.storageHandle();
644 return .{
645 .header = pointer(Header, handle, layout.header_offset),
646 .operand_values = slice(OperandValue, handle, layout.operand_values_offset, layout.operands),
647 .result_types = slice(ResultType, handle, layout.result_types_offset, layout.results),
648 .operands = slice(Operand, handle, layout.operands_offset, layout.operands),
649 .results = slice(Result, handle, layout.results_offset, layout.results),
650 .regions = slice(Region, handle, layout.regions_offset, layout.regions),
651 .successors = slice(Successor, handle, layout.successors_offset, layout.successors),
652 .properties = byteSlice(handle, layout.properties_offset, layout.properties),
653 };
654 }
655
656 fn pointer(comptime T: type, handle: Handle, offset: usize) *T {
657 const raw: [*]u8 = @ptrFromInt(addressAt(handle, offset));
658 return @ptrCast(@alignCast(raw));
659 }
660
661 fn slice(comptime T: type, handle: Handle, offset: usize, count: usize) []T {
662 const byte_count = std.math.mul(usize, count, @sizeOf(T)) catch unreachable;
663 assertRegion(handle, offset, byte_count);
664 const raw: [*]u8 = @ptrFromInt(addressAt(handle, offset));
665 const items: [*]T = @ptrCast(@alignCast(raw));
666 return items[0..count];
667 }
668 };
669 }
670
671 pub fn Pair(comptime First: type, comptime Second: type) type {
672 return struct {
673 pub const Capacity = struct {
674 count: usize,
675 first_offset: usize,
676 second_offset: usize,
677 total_bytes: usize,
678 allocation_alignment: std.mem.Alignment,
679
680 pub fn derive(count: usize) error{CapacityOverflow}!Capacity {
681 var cursor: usize = 0;
682 var alignment: usize = 1;
683 const first_offset = try place(First, count, &cursor, &alignment);
684 const second_offset = try place(Second, count, &cursor, &alignment);
685 return .{
686 .count = count,
687 .first_offset = first_offset,
688 .second_offset = second_offset,
689 .total_bytes = cursor,
690 .allocation_alignment = .fromByteUnits(alignment),
691 };
692 }
693 };
694
695 pub const Allocation = struct {
696 handle: Handle,
697 first: []First,
698 second: []Second,
699 };
700
701 pub fn init(allocator: Allocator, count: usize) !Allocation {
702 std.debug.assert(count > 0);
703 const capacity = try Capacity.derive(count);
704 const bytes = allocator.rawAlloc(
705 capacity.total_bytes,
706 capacity.allocation_alignment,
707 @returnAddress(),
708 ) orelse return error.OutOfMemory;
709 const handle = Handle{
710 .bytes = bytes,
711 .len = capacity.total_bytes,
712 .alignment = capacity.allocation_alignment,
713 };
714 return .{
715 .handle = handle,
716 .first = slice(First, handle, capacity.first_offset, capacity.count),
717 .second = slice(Second, handle, capacity.second_offset, capacity.count),
718 };
719 }
720
721 fn slice(comptime T: type, handle: Handle, offset: usize, count: usize) []T {
722 const byte_count = std.math.mul(usize, count, @sizeOf(T)) catch unreachable;
723 assertRegion(handle, offset, byte_count);
724 const raw: [*]u8 = @ptrFromInt(addressAt(handle, offset));
725 const items: [*]T = @ptrCast(@alignCast(raw));
726 return items[0..count];
727 }
728 };
729 }
730
731 fn place(
732 comptime T: type,
733 count: usize,
734 cursor: *usize,
735 allocation_alignment: *usize,
736 ) error{CapacityOverflow}!usize {
737 const bytes = std.math.mul(usize, count, @sizeOf(T)) catch return error.CapacityOverflow;
738 return try placeBytes(bytes, @alignOf(T), cursor, allocation_alignment);
739 }
740
741 fn placeBytes(
742 bytes: usize,
743 alignment: usize,
744 cursor: *usize,
745 allocation_alignment: *usize,
746 ) error{CapacityOverflow}!usize {
747 std.debug.assert(std.math.isPowerOfTwo(alignment));
748 const mask = std.math.sub(usize, alignment, 1) catch unreachable;
749 const padded = std.math.add(usize, cursor.*, mask) catch return error.CapacityOverflow;
750 const offset = padded & ~mask;
751 cursor.* = std.math.add(usize, offset, bytes) catch return error.CapacityOverflow;
752 allocation_alignment.* = @max(allocation_alignment.*, alignment);
753 return offset;
754 }
755
756 fn byteSlice(handle: Handle, offset: usize, len: usize) []u8 {
757 assertRegion(handle, offset, len);
758 const pointer: [*]u8 = @ptrFromInt(addressAt(handle, offset));
759 return pointer[0..len];
760 }
761
762 fn addressAt(handle: Handle, offset: usize) usize {
763 std.debug.assert(offset <= handle.len);
764 return std.math.add(usize, @intFromPtr(handle.bytes), offset) catch unreachable;
765 }
766
767 fn assertRegion(handle: Handle, offset: usize, len: usize) void {
768 const remaining = std.math.sub(usize, handle.len, offset) catch unreachable;
769 std.debug.assert(len <= remaining);
770 }
771
772 test "operation storage capacity matches an independent aligned byte model" {
773 comptime {
774 @stardustClaim(
775 @import("alloc_phase").capacity.witness(Storage, "choir_operation_storage_capacity"),
776 null,
777 null,
778 null,
779 null,
780 null,
781 null,
782 );
783 }
784
785 const Header = extern struct { word: u64 };
786 const Operand = extern struct { words: [3]u64 };
787 const Result = struct { byte: u8 };
788 const TypedPlan = Plan(Header, *u8, u32, Operand, Result, u128, *u16);
789 const limits = TypedPlan.Limits{
790 .operands = 3,
791 .results = 2,
792 .regions = 1,
793 .successors = 4,
794 .properties = 7,
795 .properties_alignment = .@"32",
796 };
797 const capacity = try TypedPlan.Capacity.derive(limits);
798
799 const Model = struct {
800 fn placeType(comptime T: type, count: usize, cursor: *usize) !void {
801 cursor.* = std.mem.alignForward(usize, cursor.*, @alignOf(T));
802 const bytes = try std.math.mul(usize, count, @sizeOf(T));
803 cursor.* = try std.math.add(usize, cursor.*, bytes);
804 }
805
806 fn placeBytes(bytes: usize, alignment: usize, cursor: *usize) !void {
807 cursor.* = std.mem.alignForward(usize, cursor.*, alignment);
808 cursor.* = try std.math.add(usize, cursor.*, bytes);
809 }
810 };
811 var expected_bytes: usize = 0;
812 try Model.placeType(Header, 1, &expected_bytes);
813 try Model.placeType(*u8, limits.operands, &expected_bytes);
814 try Model.placeType(u32, limits.results, &expected_bytes);
815 try Model.placeType(Operand, limits.operands, &expected_bytes);
816 try Model.placeType(Result, limits.results, &expected_bytes);
817 try Model.placeType(u128, limits.regions, &expected_bytes);
818 try Model.placeType(*u16, limits.successors, &expected_bytes);
819 try Model.placeBytes(limits.properties, limits.properties_alignment.toByteUnits(), &expected_bytes);
820
821 try std.testing.expectEqual(expected_bytes, capacity.total_bytes);
822 try std.testing.expectEqual(@as(usize, 32), capacity.allocation_alignment.toByteUnits());
823 }
824
825 test "operation storage acquires one exact aligned region" {
826 comptime {
827 @stardustClaim(
828 @import("alloc_phase").capacity.witness(Storage, "choir_operation_storage_acquisition"),
829 null,
830 null,
831 null,
832 null,
833 null,
834 null,
835 );
836 }
837
838 const Header = extern struct { word: u64 };
839 const Operand = extern struct { words: [3]u64 };
840 const Result = struct { byte: u8 };
841 const TypedPlan = Plan(Header, *u8, u32, Operand, Result, u128, *u16);
842 const limits = TypedPlan.Limits{
843 .operands = 3,
844 .results = 2,
845 .regions = 1,
846 .successors = 4,
847 .properties = 7,
848 .properties_alignment = .@"32",
849 };
850 const capacity = try TypedPlan.Capacity.derive(limits);
851 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
852 var allocation = try TypedPlan.init(failing.allocator(), limits);
853 defer allocation.storage.deinit(failing.allocator());
854 const regions = allocation.regions;
855
856 try std.testing.expectEqual(@as(usize, 1), failing.alloc_index);
857 try std.testing.expectEqual(capacity.total_bytes, failing.allocated_bytes);
858 try std.testing.expect(@intFromPtr(allocation.storage.bytes) % capacity.allocation_alignment.toByteUnits() == 0);
859 try std.testing.expectEqual(limits.operands, regions.operands.len);
860 try std.testing.expectEqual(limits.results, regions.results.len);
861 try std.testing.expectEqual(limits.properties, regions.properties.len);
862 try std.testing.expect(!alloc_phase.capacity.typeHasAllocatorCapability(Storage));
863 try std.testing.expectEqual(alloc_phase.capacity.Phase.initialization, allocation.storage.status());
864 allocation.storage.activate();
865 try std.testing.expectEqual(alloc_phase.capacity.Phase.steady, allocation.storage.status());
866 }
867
868 test "operation storage capacity rejects max plus one arithmetic" {
869 comptime {
870 @stardustClaim(
871 @import("alloc_phase").capacity.witness(Storage, "choir_operation_storage_boundary"),
872 null,
873 null,
874 null,
875 null,
876 null,
877 null,
878 );
879 }
880
881 const TypedPlan = Plan(u8, usize, usize, usize, usize, usize, usize);
882 try std.testing.expectError(error.CapacityOverflow, TypedPlan.Capacity.derive(.{
883 .operands = std.math.maxInt(usize),
884 .results = 0,
885 .regions = 0,
886 .successors = 0,
887 .properties = 0,
888 .properties_alignment = .@"1",
889 }));
890 try std.testing.expectError(error.CapacityOverflow, Pair(usize, usize).Capacity.derive(std.math.maxInt(usize)));
891 }
892
893 test "operation storage retries after allocation failure" {
894 comptime {
895 @stardustClaim(
896 @import("alloc_phase").capacity.witness(Storage, "choir_operation_storage_oom"),
897 null,
898 null,
899 null,
900 null,
901 null,
902 null,
903 );
904 }
905
906 const TypedPlan = Plan(u8, usize, usize, usize, usize, usize, usize);
907 const limits = TypedPlan.Limits{
908 .operands = 1,
909 .results = 1,
910 .regions = 1,
911 .successors = 1,
912 .properties = 1,
913 .properties_alignment = .@"1",
914 };
915 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{ .fail_index = 0 });
916 try std.testing.expectError(error.OutOfMemory, TypedPlan.init(failing.allocator(), limits));
917
918 failing.fail_index = std.math.maxInt(usize);
919 var allocation = try TypedPlan.init(failing.allocator(), limits);
920 allocation.storage.deinit(failing.allocator());
921 }
922
923 test "operation storage pool preserves fallback allocation provenance" {
924 const TestAllocator = PoolAllocator(
925 .{ .total_bytes = 64, .allocation_alignment = .@"8" },
926 .{ .total_bytes = 96, .allocation_alignment = .@"8" },
927 .{ .total_bytes = 128, .allocation_alignment = .@"8" },
928 .{ .total_bytes = 160, .allocation_alignment = .@"8" },
929 );
930 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
931 var pool = TestAllocator.init(failing.allocator());
932 defer pool.deinit();
933 const allocator = pool.allocator();
934
935 const fallback_before = failing.alloc_index;
936 const fallback = allocator.rawAlloc(
937 63,
938 .@"8",
939 @returnAddress(),
940 ) orelse return error.OutOfMemory;
941 try std.testing.expectEqual(
942 std.math.add(usize, fallback_before, 1) catch unreachable,
943 failing.alloc_index,
944 );
945 const resize_before = failing.resize_index;
946 try std.testing.expect(!allocator.rawResize(fallback[0..63], .@"8", 64, @returnAddress()));
947 try std.testing.expectEqual(resize_before, failing.resize_index);
948 try std.testing.expectEqual(
949 @as(?[*]u8, null),
950 allocator.rawRemap(fallback[0..63], .@"8", 96, @returnAddress()),
951 );
952 try std.testing.expectEqual(resize_before, failing.resize_index);
953 allocator.rawFree(fallback[0..63], .@"8", @returnAddress());
954
955 const aligned_before = failing.alloc_index;
956 const aligned = allocator.rawAlloc(
957 64,
958 .@"16",
959 @returnAddress(),
960 ) orelse return error.OutOfMemory;
961 try std.testing.expectEqual(
962 std.math.add(usize, aligned_before, 1) catch unreachable,
963 failing.alloc_index,
964 );
965 allocator.rawFree(aligned[0..64], .@"16", @returnAddress());
966 }
967
968 test "operation storage pool pads slot strides without widening allocations" {
969 const TestAllocator = PoolAllocator(
970 .{ .total_bytes = 17, .allocation_alignment = .@"8" },
971 .{ .total_bytes = 25, .allocation_alignment = .@"8" },
972 .{ .total_bytes = 33, .allocation_alignment = .@"8" },
973 .{ .total_bytes = 41, .allocation_alignment = .@"8" },
974 );
975 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
976 var pool = TestAllocator.init(failing.allocator());
977 defer pool.deinit();
978 const allocator = pool.allocator();
979
980 const first = allocator.rawAlloc(17, .@"8", @returnAddress()) orelse
981 return error.OutOfMemory;
982 try std.testing.expect(@intFromPtr(first) % 8 == 0);
983 const allocation_count = failing.alloc_index;
984 allocator.rawFree(first[0..17], .@"8", @returnAddress());
985
986 const reused = allocator.rawAlloc(17, .@"8", @returnAddress()) orelse
987 return error.OutOfMemory;
988 try std.testing.expectEqual(allocation_count, failing.alloc_index);
989 try std.testing.expectEqual(@intFromPtr(first), @intFromPtr(reused));
990 allocator.rawFree(reused[0..17], .@"8", @returnAddress());
991 }
992
993 test "operation storage pool attributes requests satisfied without backing dispatch" {
994 if (comptime !alloc_observe.enabled) return error.SkipZigTest;
995 const Capture = struct {
996 events: [4]alloc_observe.Event = undefined,
997 count: usize = 0,
998
999 fn record(context: *anyopaque, event: alloc_observe.Event) void {
1000 const self: *@This() = @ptrCast(@alignCast(context));
1001 std.debug.assert(self.count < self.events.len);
1002 self.events[self.count] = event;
1003 self.count += 1;
1004 }
1005 };
1006 const TestAllocator = PoolAllocator(
1007 .{ .total_bytes = 17, .allocation_alignment = .@"8" },
1008 .{ .total_bytes = 25, .allocation_alignment = .@"8" },
1009 .{ .total_bytes = 33, .allocation_alignment = .@"8" },
1010 .{ .total_bytes = 41, .allocation_alignment = .@"8" },
1011 );
1012 var capture = Capture{};
1013 const sink = alloc_observe.Sink{
1014 .context = &capture,
1015 .record = Capture.record,
1016 };
1017 var observation = try alloc_observe.install(&sink);
1018 defer observation.deinit();
1019 var pool = TestAllocator.init(std.testing.allocator);
1020 defer pool.deinit();
1021 const allocator = pool.allocator();
1022 const first = allocator.rawAlloc(17, .@"8", @returnAddress()) orelse
1023 return error.OutOfMemory;
1024 allocator.rawFree(first[0..17], .@"8", @returnAddress());
1025 const reused = allocator.rawAlloc(17, .@"8", @returnAddress()) orelse
1026 return error.OutOfMemory;
1027 allocator.rawFree(reused[0..17], .@"8", @returnAddress());
1028
1029 try std.testing.expectEqual(@as(usize, 4), capture.count);
1030 try std.testing.expectEqual(alloc_observe.Producer.pool, capture.events[0].producer);
1031 try std.testing.expectEqual(alloc_observe.Operation.alloc, capture.events[0].operation);
1032 try std.testing.expect(capture.events[0].succeeded);
1033 try std.testing.expectEqual(alloc_observe.Operation.alloc, capture.events[2].operation);
1034 try std.testing.expectEqual(@intFromPtr(first), capture.events[2].address);
1035 try std.testing.expectEqual(capture.events[0].producer_id, capture.events[2].producer_id);
1036 }
1037
1038 test "operation storage list exposes fixed capacity without allocation authority" {
1039 var backing: [3]u32 = undefined;
1040 var list = List(u32).init(&backing);
1041 list.appendAssumeCapacity(1);
1042 list.appendSliceAssumeCapacity(&.{ 2, 3 });
1043 try std.testing.expectEqualSlices(u32, &.{ 1, 2, 3 }, list.items);
1044 list.clearRetainingCapacity();
1045 try std.testing.expectEqual(@as(usize, 0), list.items.len);
1046 try std.testing.expectEqual(@as(usize, 3), list.capacity);
1047 }