lib/alloc/arena/src/sequential.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! A sequential scope is an allocation owner that groups temporary allocations
2 //! made during a single operation and releases them together when the operation
3 //! completes. The scope requires sequential execution and relies on the caller
4 //! to prevent concurrent access.
5 //!
6 //! When serving an allocation request, the scope inspects its existing head
7 //! node first. If the request fits within the remaining space of that node, the
8 //! scope advances the head node frontier. If the request exceeds remaining
9 //! space, the scope attempts to expand the head node in place through
10 //! `rawResize`, requesting an expanded preferred size before falling back to
11 //! the exact required size. In-place expansion never relocates previously
12 //! published allocations.
13 //!
14 //! If the head node cannot expand in place, the scope allocates a fresh node
15 //! from the backing allocator using exact-first growth. Exact-first allocation
16 //! applies only to fresh nodes, satisfying the tight backing request before
17 //! requesting spare capacity. The scope requests the exact bytes needed for the
18 //! node header, requested payload, and alignment slack. If that initial backing
19 //! allocation succeeds, the scope optionally attempts to stretch the buffer to
20 //! a larger preferred size through `rawRemap`. Because no pointer has been
21 //! published from the fresh block yet, `rawRemap` may relocate the buffer to
22 //! find contiguous capacity. If the backing allocator refuses the remap, the
23 //! scope retains the successful exact allocation rather than failing the
24 //! request. A fresh node is not guaranteed to be larger than its predecessor,
25 //! and physical reclamation of released buffers depends on the child allocator.
26
27 const std = @import("std");
28 const observe = @import("alloc_observe");
29
30 const Allocator = std.mem.Allocator;
31 const Alignment = std.mem.Alignment;
32
33 /// A compile-time alias selecting between ObservedSequentialScope when
34 /// allocation observation is enabled and UnobservedSequentialScope when
35 /// disabled. Both implementations provide identical public methods for init,
36 /// allocator, deinit, and queryCapacity. The type does not expose a reset
37 /// method, bounding all allocations to a single sequential lifetime ended by
38 /// calling deinit, which releases every backing node. The implementation is not
39 /// thread-safe and requires single-threaded access.
40 pub const SequentialScope = if (observe.enabled)
41 ObservedSequentialScope
42 else
43 UnobservedSequentialScope;
44
45 /// This allocator manages an intrusive linked list of backing memory buffers
46 /// supplied by a child allocator, dedicating the head node to the active
47 /// allocation frontier. The owner serves temporary allocations during a
48 /// caller-managed sequential lifetime and frees all nodes in reverse order of
49 /// allocation, newest first, when `deinit` is called. Fresh buffers follow an
50 /// exact-first growth policy, requesting the exact bytes needed first and
51 /// optionally attempting to remap to an expanded preferred size before
52 /// returning a pointer.
53 ///
54 /// The scope enforces no intrinsic byte or node capacity limit beyond what the
55 /// backing allocator and address space supply. Each linked node begins with an
56 /// internal header spanning three `usize` words, enforced by a compile-time
57 /// assertion, but the struct offers no public guarantee of private field ABI
58 /// layout.
59 ///
60 /// For allocation requests, if preferredNodeSize arithmetic overflows, the
61 /// scope skips that optional expansion attempt, allowing a valid exact
62 /// allocation to still succeed. A raw allocation request returns null if the
63 /// required size or alignment cannot be calculated, or if the backing allocator
64 /// cannot supply the required fresh block after the existing head path is
65 /// insufficient. High-level allocation then reports error.OutOfMemory. This
66 /// behavior applies specifically to allocation requests, as resizing or
67 /// remapping issued slices follows a separate contract.
68 ///
69 /// An `Allocator` handle borrowed from the scope stores a pointer to this
70 /// owner, requiring the owner to remain at a stable memory address while that
71 /// handle is used. Individual `free` and shrink operations reclaim storage only
72 /// when the target allocation terminates exactly at the head node frontier.
73 /// Shrinking an earlier allocation succeeds without reclaiming storage,
74 /// non-tail growth requests return `false`, and alignment gaps remain
75 /// uncollected until teardown. The raw remap interface mirrors in-place
76 /// resizing and will not relocate published allocations, whereas higher-level
77 /// `Allocator.realloc` calls may allocate a new buffer, copy live data, and
78 /// free the prior allocation. Physical reclamation of freed storage depends on
79 /// the backing child allocator.
80 const UnobservedSequentialScope = struct {
81 /// The backing `Allocator` handle is stored by value and used to acquire
82 /// node blocks, perform in-place resizing, remap fresh allocations, and
83 /// release storage. The caller must keep the underlying state owner of the
84 /// backing allocator valid through all node operations and teardown through
85 /// `deinit`. The caller does not need to maintain the temporary handle
86 /// value itself at a stable memory address.
87 child: Allocator,
88 /// Pointer to the newest node in the linked list, or null when the scope
89 /// has allocated no storage. This chain is maintained exclusively by the
90 /// scope owner and cannot be copied or shared independently.
91 first: ?*Node = null,
92
93 const Self = @This();
94
95 /// Initializes an empty sequential scope over the provided child allocator
96 /// without allocating any backing memory blocks up front.
97 pub fn init(child: Allocator) Self {
98 return .{ .child = child };
99 }
100
101 /// Returns a borrowed std.mem.Allocator handle holding a pointer to this
102 /// owner. The caller must ensure the scope instance remains alive and
103 /// pinned at a stable memory address while the handle is in use.
104 pub fn allocator(self: *Self) Allocator {
105 return .{ .ptr = self, .vtable = &vtable };
106 }
107
108 /// Traverses the node list from newest to oldest, recording each node's
109 /// successor pointer before calling rawFree on the entire backing
110 /// allocation slice including the node header, and sets the head pointer to
111 /// null. Calling this method invalidates all memory slices previously
112 /// issued by the scope without running individual object destructors.
113 /// Physical reclamation of freed blocks depends on the child allocator, and
114 /// the teardown process must be performed sequentially.
115 pub fn deinit(self: *Self) void {
116 var current = self.first;
117 while (current) |node| {
118 current = node.next;
119 self.child.rawFree(
120 node.allocatedSlice(),
121 .of(Node),
122 @returnAddress(),
123 );
124 }
125 self.first = null;
126 }
127
128 /// The queryCapacity function sums each held node's payload capacity across
129 /// the scope, excluding headers and including unused room and padding. It
130 /// does not report live user bytes or represent a memory budget. Addition
131 /// overflow saturates to std.math.maxInt(usize), the maximum value
132 /// representable by usize. Because this query reads unsynchronized state,
133 /// the caller must exclude all concurrent mutation, including allocation,
134 /// free, and deinit operations.
135 pub fn queryCapacity(self: *const Self) usize {
136 var capacity: usize = 0;
137 var current = self.first;
138 while (current) |node| : (current = node.next) {
139 capacity = std.math.add(
140 usize,
141 capacity,
142 node.buffer().len,
143 ) catch return std.math.maxInt(usize);
144 }
145 return capacity;
146 }
147
148 fn rawAlloc(
149 context: *anyopaque,
150 len: usize,
151 alignment: Alignment,
152 return_address: usize,
153 ) ?[*]u8 {
154 const self: *Self = @ptrCast(@alignCast(context));
155 std.debug.assert(len > 0);
156 var previous_buffer_len: usize = 0;
157 if (self.first) |node| {
158 previous_buffer_len = node.buffer().len;
159 if (self.allocateFromNode(
160 node,
161 len,
162 alignment,
163 return_address,
164 )) |result| return result;
165 }
166 return self.allocateNode(
167 len,
168 alignment,
169 return_address,
170 previous_buffer_len,
171 );
172 }
173
174 /// Attempts to satisfy an allocation request from the existing head node.
175 /// It computes the forward-aligned offset of the node's current frontier
176 /// and returns a pointer immediately if the requested length fits within
177 /// remaining capacity. When the node already has sufficient capacity,
178 /// success advances the frontier offset only. When the node lacks
179 /// sufficient capacity, it attempts to expand the backing block in place
180 /// using `rawResize`, requesting an expanded preferred size first and
181 /// falling back to the exact required size on refusal. An existing head
182 /// node is never relocated through `rawRemap`. If a backing resize
183 /// succeeds, the method updates the node size as well as the frontier. If
184 /// both resize attempts are refused, allocation falls back to creating a
185 /// fresh node.
186 fn allocateFromNode(
187 self: *Self,
188 node: *Node,
189 len: usize,
190 alignment: Alignment,
191 return_address: usize,
192 ) ?[*]u8 {
193 const buffer = node.buffer();
194 const index = alignedIndex(
195 buffer.ptr,
196 node.end_index,
197 alignment,
198 ) orelse return null;
199 const end = std.math.add(usize, index, len) catch return null;
200 if (end <= buffer.len) {
201 node.end_index = end;
202 return buffer[index..end].ptr;
203 }
204 const size = std.math.add(usize, @sizeOf(Node), end) catch
205 return null;
206 const allocated = node.allocatedSlice();
207 if (preferredNodeSize(buffer.len, len, alignment)) |preferred_size| {
208 std.debug.assert(preferred_size >= size);
209 if (preferred_size != size and self.child.rawResize(
210 allocated,
211 .of(Node),
212 preferred_size,
213 return_address,
214 )) {
215 node.size = preferred_size;
216 node.end_index = end;
217 return node.buffer()[index..end].ptr;
218 }
219 }
220 if (!self.child.rawResize(
221 allocated,
222 .of(Node),
223 size,
224 return_address,
225 )) return null;
226 node.size = size;
227 node.end_index = end;
228 return node.buffer()[index..end].ptr;
229 }
230
231 /// Allocates a fresh node to fulfill a request that cannot fit in the
232 /// existing head node. It first computes the exact size needed for the node
233 /// header, requested payload length, and conservative alignment slack,
234 /// returning null if arithmetic overflows or if the backing allocator's
235 /// rawAlloc call fails. Once the exact block is secured, it optionally
236 /// invokes rawRemap to expand the block to a preferred size. Unlike
237 /// existing nodes whose published pointers prevent memory relocation, a
238 /// fresh node has not yet issued any pointers to callers, allowing rawRemap
239 /// to relocate the block in search of contiguous storage without breaking
240 /// caller references. If remap is refused, the scope retains the original
241 /// exact block. The node header is initialized only after the remap attempt
242 /// finishes. If subsequent alignment checks or end index additions fail,
243 /// the method frees the fresh block and returns null without linking it
244 /// into the owner's chain. On complete success, the new node is linked as
245 /// the list head and the memory pointer is published to the caller.
246 fn allocateNode(
247 self: *Self,
248 len: usize,
249 alignment: Alignment,
250 return_address: usize,
251 previous_buffer_len: usize,
252 ) ?[*]u8 {
253 const alignment_bytes = alignment.toByteUnits();
254 const slack = if (alignment_bytes <= @alignOf(Node))
255 0
256 else
257 alignment_bytes - 1;
258 const payload = std.math.add(usize, len, slack) catch return null;
259 const exact_size = std.math.add(usize, @sizeOf(Node), payload) catch
260 return null;
261 var raw = self.child.rawAlloc(
262 exact_size,
263 .of(Node),
264 return_address,
265 ) orelse return null;
266 var size = exact_size;
267 if (preferredNodeSize(
268 previous_buffer_len,
269 len,
270 alignment,
271 )) |preferred_size| {
272 std.debug.assert(preferred_size >= exact_size);
273 if (preferred_size != exact_size) {
274 if (self.child.rawRemap(
275 raw[0..exact_size],
276 .of(Node),
277 preferred_size,
278 return_address,
279 )) |preferred| {
280 raw = preferred;
281 size = preferred_size;
282 }
283 }
284 }
285 const node: *Node = @ptrCast(@alignCast(raw));
286 node.* = .{
287 .size = size,
288 .end_index = 0,
289 .next = self.first,
290 };
291 const buffer = node.buffer();
292 const index = alignedIndex(buffer.ptr, 0, alignment) orelse {
293 self.child.rawFree(
294 node.allocatedSlice(),
295 .of(Node),
296 return_address,
297 );
298 return null;
299 };
300 const end = std.math.add(usize, index, len) catch {
301 self.child.rawFree(
302 node.allocatedSlice(),
303 .of(Node),
304 return_address,
305 );
306 return null;
307 };
308 std.debug.assert(end <= buffer.len);
309 node.end_index = end;
310 self.first = node;
311 return buffer[index..end].ptr;
312 }
313
314 fn rawResize(
315 context: *anyopaque,
316 memory: []u8,
317 alignment: Alignment,
318 new_len: usize,
319 return_address: usize,
320 ) bool {
321 const self: *Self = @ptrCast(@alignCast(context));
322 _ = alignment;
323 _ = return_address;
324 std.debug.assert(memory.len > 0);
325 std.debug.assert(new_len > 0);
326 const node = self.first orelse return false;
327 const buffer = node.buffer();
328 if (buffer.ptr + node.end_index != memory.ptr + memory.len) {
329 return new_len <= memory.len;
330 }
331 if (new_len <= memory.len) {
332 node.end_index -= memory.len - new_len;
333 return true;
334 }
335 const extra = new_len - memory.len;
336 if (extra > buffer.len - node.end_index) return false;
337 node.end_index += extra;
338 return true;
339 }
340
341 fn rawRemap(
342 context: *anyopaque,
343 memory: []u8,
344 alignment: Alignment,
345 new_len: usize,
346 return_address: usize,
347 ) ?[*]u8 {
348 return if (rawResize(
349 context,
350 memory,
351 alignment,
352 new_len,
353 return_address,
354 )) memory.ptr else null;
355 }
356
357 fn rawFree(
358 context: *anyopaque,
359 memory: []u8,
360 alignment: Alignment,
361 return_address: usize,
362 ) void {
363 const self: *Self = @ptrCast(@alignCast(context));
364 _ = alignment;
365 _ = return_address;
366 std.debug.assert(memory.len > 0);
367 const node = self.first orelse return;
368 const buffer = node.buffer();
369 if (buffer.ptr + node.end_index != memory.ptr + memory.len) return;
370 node.end_index -= memory.len;
371 }
372
373 const vtable: Allocator.VTable = .{
374 .alloc = rawAlloc,
375 .resize = rawResize,
376 .remap = rawRemap,
377 .free = rawFree,
378 };
379 };
380
381 /// Calculates a preferred target node byte size to amortize future backing
382 /// allocator requests when growing or allocating a buffer. Let H equal
383 /// @sizeOf(Node), A represent the requested alignment in bytes, P be the
384 /// previous head node payload capacity, and L be the requested allocation
385 /// length. The calculation first computes a baseline biased size X = P + H +
386 /// A + L + 16 using checked addition. It then computes an expanded size Y = X +
387 /// floor(X / 2) and rounds Y up to an even byte boundary using Y + (Y & 1),
388 /// checking each step for integer overflow. If any intermediate addition
389 /// overflows, the function returns null. Returning null causes the caller to
390 /// skip the optional expansion attempt and proceed with the valid exact size
391 /// request rather than aborting the allocation. The actual capacity of the next
392 /// node is not guaranteed to be 1.5 times the previous node because requests
393 /// vary in length and backing allocators may refuse optional remap expansions.
394 fn preferredNodeSize(
395 previous_buffer_len: usize,
396 len: usize,
397 alignment: Alignment,
398 ) ?usize {
399 const minimum_with_alignment = std.math.add(
400 usize,
401 @sizeOf(Node),
402 alignment.toByteUnits(),
403 ) catch return null;
404 const minimum_size = std.math.add(
405 usize,
406 minimum_with_alignment,
407 len,
408 ) catch return null;
409 const accumulated_size = std.math.add(
410 usize,
411 previous_buffer_len,
412 minimum_size,
413 ) catch return null;
414 const biased_size = std.math.add(
415 usize,
416 accumulated_size,
417 16,
418 ) catch return null;
419 const grown_size = std.math.add(
420 usize,
421 biased_size,
422 biased_size / 2,
423 ) catch return null;
424 return std.math.add(
425 usize,
426 grown_size,
427 grown_size & 1,
428 ) catch null;
429 }
430
431 /// Represents an individual node in the scope's intrusive list, owning one
432 /// backing allocation composed of this header followed immediately by usable
433 /// payload bytes. Nodes are linked in reverse chronological order from newest
434 /// to oldest. The header occupies three usize words in the current verified
435 /// implementation layout, which is asserted at compile time but does not
436 /// constitute a portable public ABI guarantee. The scope owner maintains this
437 /// internal state directly, and the structure cannot be cloned or copied
438 /// independently.
439 const Node = struct {
440 /// The total size in bytes of the backing memory allocation, including both
441 /// the node header and its payload space. The scope uses this value when
442 /// issuing rawResize and rawFree calls to the child allocator.
443 size: usize,
444 /// The byte offset within the node payload buffer where the current
445 /// allocation frontier stands. This index includes alignment padding
446 /// inserted between allocations, and does not represent a sum of surviving
447 /// live payload bytes.
448 end_index: usize,
449 /// Pointer to the next older node in the scope's allocation chain, or null
450 /// if this node is the oldest buffer. The scope saves this pointer prior to
451 /// freeing the current node during teardown.
452 next: ?*Node,
453
454 fn allocatedSlice(self: *Node) []u8 {
455 return @as([*]u8, @ptrCast(self))[0..self.size];
456 }
457
458 fn buffer(self: *Node) []u8 {
459 return self.allocatedSlice()[@sizeOf(Node)..];
460 }
461
462 comptime {
463 std.debug.assert(@sizeOf(Node) == 3 * @sizeOf(usize));
464 }
465 };
466
467 fn alignedIndex(
468 buffer: [*]u8,
469 end_index: usize,
470 alignment: Alignment,
471 ) ?usize {
472 const base = @intFromPtr(buffer);
473 const address = std.math.add(usize, base, end_index) catch return null;
474 const aligned = alignment.forward(address);
475 if (aligned < address) return null;
476 return aligned - base;
477 }
478
479 /// This wrapper embeds an `UnobservedSequentialScope` and reports logical
480 /// allocation operations and lifecycle `deinit` events to the `alloc_observe`
481 /// framework. The wrapper assigns an observation identity derived from a
482 /// process producer identifier rather than a pointer address. This derivation
483 /// keeps the identity consistent when the wrapper moves in memory, though
484 /// moving the wrapper does not repair existing `Allocator` handles that hold
485 /// the old address. The wrapper stores no generation counter, and `identity()`
486 /// supplies a literal 0 so all emitted events use generation 0. It requires the
487 /// caller to avoid concurrent mutation, matching the thread-safety requirements
488 /// of the underlying scope.
489 const ObservedSequentialScope = struct {
490 /// The underlying unobserved sequential scope that owns node storage and
491 /// linked list bookkeeping. Mutating this instance directly bypasses event
492 /// emission and lifecycle tracking.
493 inner: UnobservedSequentialScope,
494 /// The numeric producer identifier assigned at initialization to tag
495 /// observed allocation events. This identifier remains stable when the
496 /// scope struct is moved in memory, though existing allocator handles are
497 /// not retargeted and continue to reference the old address.
498 producer_id: u64,
499
500 const Self = @This();
501
502 /// Initializes an empty sequential scope over the provided child allocator
503 /// without allocating any backing memory blocks up front.
504 pub fn init(child: Allocator) Self {
505 return .{
506 .inner = .init(child),
507 .producer_id = observe.producerId(),
508 };
509 }
510
511 /// Returns a borrowed std.mem.Allocator handle holding a pointer to this
512 /// owner. The caller must ensure the scope instance remains alive and
513 /// pinned at a stable memory address while the handle is in use.
514 pub fn allocator(self: *Self) Allocator {
515 return .{ .ptr = self, .vtable = &vtable };
516 }
517
518 /// Emits a lifecycle deinit event through the observation framework while
519 /// delegating storage reclamation to the inner scope's deinit method. All
520 /// allocated blocks are released newest first under the standard sequential
521 /// scope teardown policy, invalidating previously issued slices. Because
522 /// the scope does not support resets, the event concludes the scope's
523 /// single lifetime at generation zero.
524 pub fn deinit(self: *Self) void {
525 var span = observe.beginLifecycle(
526 self.identity(),
527 .end,
528 .deinit,
529 @returnAddress(),
530 );
531 self.inner.deinit();
532 span.finish(.{ .succeeded = true });
533 }
534
535 /// The queryCapacity function sums each held node's payload capacity across
536 /// the scope, excluding headers and including unused room and padding. It
537 /// does not report live user bytes or represent a memory budget. Addition
538 /// overflow saturates to std.math.maxInt(usize), the maximum value
539 /// representable by usize. Because this query reads unsynchronized state,
540 /// the caller must exclude all concurrent mutation, including allocation,
541 /// free, and deinit operations.
542 pub fn queryCapacity(self: *const Self) usize {
543 return self.inner.queryCapacity();
544 }
545
546 fn rawAlloc(
547 context: *anyopaque,
548 len: usize,
549 alignment: Alignment,
550 return_address: usize,
551 ) ?[*]u8 {
552 const self: *Self = @ptrCast(@alignCast(context));
553 var span = observe.beginOwned(
554 self.identity(),
555 .alloc,
556 0,
557 0,
558 len,
559 alignment.toByteUnits(),
560 return_address,
561 );
562 const result = self.inner.allocator().rawAlloc(
563 len,
564 alignment,
565 return_address,
566 );
567 span.finish(.{
568 .address = if (result) |pointer| @intFromPtr(pointer) else 0,
569 .succeeded = result != null,
570 });
571 return result;
572 }
573
574 fn rawResize(
575 context: *anyopaque,
576 memory: []u8,
577 alignment: Alignment,
578 new_len: usize,
579 return_address: usize,
580 ) bool {
581 const self: *Self = @ptrCast(@alignCast(context));
582 var span = observe.beginOwned(
583 self.identity(),
584 .resize,
585 @intFromPtr(memory.ptr),
586 memory.len,
587 new_len,
588 alignment.toByteUnits(),
589 return_address,
590 );
591 const succeeded = self.inner.allocator().rawResize(
592 memory,
593 alignment,
594 new_len,
595 return_address,
596 );
597 span.finish(.{
598 .address = if (succeeded) @intFromPtr(memory.ptr) else 0,
599 .succeeded = succeeded,
600 });
601 return succeeded;
602 }
603
604 fn rawRemap(
605 context: *anyopaque,
606 memory: []u8,
607 alignment: Alignment,
608 new_len: usize,
609 return_address: usize,
610 ) ?[*]u8 {
611 const self: *Self = @ptrCast(@alignCast(context));
612 var span = observe.beginOwned(
613 self.identity(),
614 .remap,
615 @intFromPtr(memory.ptr),
616 memory.len,
617 new_len,
618 alignment.toByteUnits(),
619 return_address,
620 );
621 const result = self.inner.allocator().rawRemap(
622 memory,
623 alignment,
624 new_len,
625 return_address,
626 );
627 span.finish(.{
628 .address = if (result) |pointer| @intFromPtr(pointer) else 0,
629 .succeeded = result != null,
630 });
631 return result;
632 }
633
634 fn rawFree(
635 context: *anyopaque,
636 memory: []u8,
637 alignment: Alignment,
638 return_address: usize,
639 ) void {
640 const self: *Self = @ptrCast(@alignCast(context));
641 var span = observe.beginOwned(
642 self.identity(),
643 .free,
644 @intFromPtr(memory.ptr),
645 memory.len,
646 0,
647 alignment.toByteUnits(),
648 return_address,
649 );
650 self.inner.allocator().rawFree(
651 memory,
652 alignment,
653 return_address,
654 );
655 span.finish(.{
656 .address = @intFromPtr(memory.ptr),
657 .succeeded = true,
658 });
659 }
660
661 const vtable: Allocator.VTable = .{
662 .alloc = rawAlloc,
663 .resize = rawResize,
664 .remap = rawRemap,
665 .free = rawFree,
666 };
667
668 fn identity(self: *const Self) observe.Identity {
669 return observe.Identity.movable(
670 self.producer_id,
671 .arena,
672 0,
673 );
674 }
675 };