lib/alloc/fixed/src/fixed.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const observe = @import("alloc_observe");
3
4 const Allocator = std.mem.Allocator;
5 const Alignment = std.mem.Alignment;
6
7 /// This owner allocates from a byte slice the caller already owns, with no
8 /// allocator behind it, providing a fixed-capacity buffer allocator over that
9 /// slice. With observation left off (`-Dobserve-allocations=false`), it is
10 /// `std.heap.FixedBufferAllocator` itself. With observation compiled in
11 /// (`-Dobserve-allocations=true`), it is `ObservedFixedBuffer`, a wrapper
12 /// holding a `std.heap.FixedBufferAllocator` and a producer identity.
13 ///
14 /// ### Owner stability and address requirements
15 /// The owner struct stays alive and at one memory address while a borrowed
16 /// allocator handle is in use. One owner serves one buffer, and the caller
17 /// takes no copy of it to act as a second allocator over that same storage.
18 ///
19 /// ### Memory operations and reclamation
20 /// Memory is cut in order from the start of the buffer up to the byte offset
21 /// the allocations have reached inside the buffer, the *bump frontier*. Freeing
22 /// or shrinking the most recent allocation lowers the frontier. Freeing an
23 /// earlier allocation leaves its space taken until `reset()` rewinds the
24 /// frontier. Calling `reset()` rewinds the frontier to zero and leaves every
25 /// active allocation invalid, so the space can be used again.
26 ///
27 /// ### Concurrency and thread safety
28 /// The ordinary `allocator()` handle needs the caller to serialize access. The
29 /// `threadSafeAllocator()` handle advances the frontier with lock-free
30 /// compare-and-swap inside the standard library allocator. With observation on,
31 /// the instrumented callbacks and the observation bookkeeping carry no such
32 /// guarantee and handle their own concurrency. Calling `used()` or reading the
33 /// owner's fields while thread-safe operations run leaves a data race. A caller
34 /// keeps concurrent calls to `allocator()` and to `threadSafeAllocator()`
35 /// apart, and leaves `reset()` alone while thread-safe operations may be
36 /// running. Calling `Tracked.status()` needs the caller's own serialization.
37 pub const FixedBuffer = if (observe.enabled)
38 ObservedFixedBuffer
39 else
40 std.heap.FixedBufferAllocator;
41
42 /// Reports in bytes how far the bump frontier of a `FixedBuffer` has moved. The
43 /// figure is the end index reached in the backing buffer, counting the payload
44 /// bytes and the alignment padding. Freeing or shrinking the most recent
45 /// allocation lowers it. The figure stands above the bytes that are live once
46 /// an allocation has been freed ahead of a later one, and once alignment gaps
47 /// remain behind.
48 pub fn used(owner: *const FixedBuffer) usize {
49 return if (comptime observe.enabled)
50 owner.inner.end_index
51 else
52 owner.end_index;
53 }
54
55 /// When a caller allocates from its own slice and needs to find out afterwards
56 /// how much memory the work took, this fixed-capacity buffer allocator records
57 /// usage figures alongside a sticky record of any raw allocation that ran out
58 /// of room. It wraps a `FixedBuffer` and records the current bump frontier
59 /// offset, the peak since the last reset, the high-water mark over its life,
60 /// and the allocation failure.
61 ///
62 /// ### Owner stability
63 /// The instance stays alive at one memory address for as long as any handle
64 /// from `allocator()` is in use. One instance owns one set of numbers, and the
65 /// caller takes no copy of it to act as a second allocator over that same
66 /// state.
67 pub const Tracked = struct {
68 /// The fixed-buffer storage owner whose frontier every other field counts,
69 /// maintained by `Tracked`.
70 fixed: FixedBuffer,
71 /// Furthest the bump frontier has reached in the current interval, which
72 /// starts when the instance starts and again at every `reset()`.
73 peak_bytes: usize = 0,
74 /// Furthest the bump frontier has reached at any point in the life of the
75 /// struct, the figure for sizing the buffer. A `reset()` leaves it
76 /// standing.
77 high_water_bytes: usize = 0,
78 /// Set to `true` exactly when `rawAlloc` returns `null` for want of room in
79 /// the buffer, separating a buffer too small from work that fits. A failed
80 /// `rawResize` or `rawRemap` leaves it alone. Calling `reset()` clears it
81 /// to `false`.
82 exhausted: bool = false,
83
84 const Self = @This();
85
86 /// A point-in-time snapshot of the numbers a `Tracked` allocator records,
87 /// used to read every figure at once as it stood when taken.
88 pub const Status = struct {
89 /// Current bump frontier offset in bytes, counting the payload and the
90 /// alignment padding.
91 used_bytes: usize,
92 /// Furthest the bump frontier reached in the interval that ends here,
93 /// which began at the last reset, or at initialization when there was
94 /// none.
95 peak_bytes: usize,
96 /// Furthest the bump frontier reached at any point, with every reset
97 /// behind it counted.
98 high_water_bytes: usize,
99 /// Indicates whether a raw allocation failure happened since
100 /// initialization or the last reset. A failed in-place resize or remap
101 /// leaves it unchanged.
102 exhausted: bool,
103 };
104
105 /// Starts a `Tracked` instance over a byte slice the caller supplies. The
106 /// caller keeps ownership of `bytes`. It performs no backing allocation.
107 pub fn init(bytes: []u8) Self {
108 return .{ .fixed = FixedBuffer.init(bytes) };
109 }
110
111 /// Hands the whole buffer back to the next round of work by resetting the
112 /// bump frontier, the peak offset, and the exhausted flag. It rewinds the
113 /// frontier to zero, sets `peak_bytes` to 0, and sets `exhausted` to
114 /// `false`. It leaves `high_water_bytes` standing across resets. Every
115 /// active allocation becomes invalid, and the space is available again.
116 pub fn reset(self: *Self) void {
117 self.fixed.reset();
118 self.peak_bytes = 0;
119 self.exhausted = false;
120 }
121
122 /// Returns a borrowed `std.mem.Allocator` handle pointing at `self` to pass
123 /// to code that allocates. The `self` instance stays alive at one memory
124 /// address while the handle is in use.
125 pub fn allocator(self: *Self) Allocator {
126 return .{ .ptr = self, .vtable = &vtable };
127 }
128
129 /// Returns a snapshot of the current usage numbers by value so a caller can
130 /// inspect them. The caller serializes access, because the read is unsafe
131 /// while another thread mutates the allocator.
132 pub fn status(self: *const Self) Status {
133 return .{
134 .used_bytes = used(&self.fixed),
135 .peak_bytes = self.peak_bytes,
136 .high_water_bytes = self.high_water_bytes,
137 .exhausted = self.exhausted,
138 };
139 }
140
141 fn observeUsage(self: *Self) void {
142 const used_bytes = used(&self.fixed);
143 self.peak_bytes = @max(self.peak_bytes, used_bytes);
144 self.high_water_bytes = @max(self.high_water_bytes, used_bytes);
145 }
146
147 fn rawAlloc(
148 context: *anyopaque,
149 len: usize,
150 alignment: Alignment,
151 return_address: usize,
152 ) ?[*]u8 {
153 const self: *Self = @ptrCast(@alignCast(context));
154 const result = self.fixed.allocator().rawAlloc(
155 len,
156 alignment,
157 return_address,
158 ) orelse {
159 self.exhausted = true;
160 return null;
161 };
162 self.observeUsage();
163 return result;
164 }
165
166 fn rawResize(
167 context: *anyopaque,
168 memory: []u8,
169 alignment: Alignment,
170 new_len: usize,
171 return_address: usize,
172 ) bool {
173 const self: *Self = @ptrCast(@alignCast(context));
174 const resized = self.fixed.allocator().rawResize(
175 memory,
176 alignment,
177 new_len,
178 return_address,
179 );
180 if (resized) self.observeUsage();
181 return resized;
182 }
183
184 fn rawRemap(
185 context: *anyopaque,
186 memory: []u8,
187 alignment: Alignment,
188 new_len: usize,
189 return_address: usize,
190 ) ?[*]u8 {
191 const self: *Self = @ptrCast(@alignCast(context));
192 const result = self.fixed.allocator().rawRemap(
193 memory,
194 alignment,
195 new_len,
196 return_address,
197 );
198 if (result != null) self.observeUsage();
199 return result;
200 }
201
202 fn rawFree(
203 context: *anyopaque,
204 memory: []u8,
205 alignment: Alignment,
206 return_address: usize,
207 ) void {
208 const self: *Self = @ptrCast(@alignCast(context));
209 self.fixed.allocator().rawFree(
210 memory,
211 alignment,
212 return_address,
213 );
214 }
215
216 const vtable: Allocator.VTable = .{
217 .alloc = rawAlloc,
218 .resize = rawResize,
219 .remap = rawRemap,
220 .free = rawFree,
221 };
222 };
223
224 fn storage(owner: *const FixedBuffer) []u8 {
225 return if (comptime observe.enabled)
226 owner.inner.buffer
227 else
228 owner.buffer;
229 }
230
231 fn fits(owner: *const FixedBuffer, len: usize, alignment: Alignment) bool {
232 const bytes = storage(owner);
233 const unaligned = std.math.add(
234 usize,
235 @intFromPtr(bytes.ptr),
236 used(owner),
237 ) catch return false;
238 const start = alignment.forward(unaligned) - @intFromPtr(bytes.ptr);
239 const end = std.math.add(usize, start, len) catch return false;
240 return end <= bytes.len;
241 }
242
243 /// A chunked allocator that builds a result across several allocations and
244 /// then either commits backing chunks to an outer owner through `retain()` or
245 /// invokes upstream frees for rollback through `discard()`. It requests
246 /// chunks from an upstream backing allocator as needed, tracking at most 64
247 /// chunk descriptors simultaneously in an array fixed at compile time.
248 /// Initializing an instance performs no initial backing allocation, acquiring
249 /// chunks only as requests demand them.
250 ///
251 /// ### Growth schedule and capacity bounds
252 /// Fresh chunks follow a growth schedule that starts at `initial_capacity`,
253 /// doubles after each successful fresh chunk, and stops growing at
254 /// `maximum_capacity`. Each fresh chunk has `@max(scheduled_capacity, len)`
255 /// bytes, so requests larger than `maximum_capacity` are allowed but need
256 /// both a free descriptor and a successful backing allocation. Because
257 /// doubling calculations use the scheduled capacity rather than the actual
258 /// requested length, oversized requests do not advance the growth progression
259 /// faster. The `maximum_capacity` parameter caps the growth schedule itself
260 /// rather than limiting individual request sizes or total storage.
261 ///
262 /// Calling `retain()` clears this descriptor table without freeing backing
263 /// memory, so committed chunks no longer occupy slots in the table and more
264 /// than 64 total chunks can be allocated across successive retain cycles. The
265 /// upstream lifetime owner must reclaim that committed memory. When an
266 /// allocation fails, the failure stems either from the backing allocator
267 /// returning `null` or from exhausting the 64 descriptor slots. Both
268 /// conditions return an allocation failure to the caller.
269 ///
270 /// ### Transaction discipline
271 /// - Calling `retain()` commits every chunk it holds to the backing lifetime
272 /// owner, such as an enclosing `std.heap.ArenaAllocator`.
273 /// - Calling `retain()` clears the descriptor tracking without freeing the
274 /// backing memory.
275 /// - A chunk that was retained can no longer be freed through
276 /// `Chunks.discard()`.
277 /// - Calling `discard()` frees every tracked chunk in reverse order back to the
278 /// upstream allocator and puts the growth schedule back at
279 /// `initial_capacity`.
280 ///
281 /// ### Resize behavior
282 /// In `rawResize`, shrinking returns `true` at once without consulting the
283 /// active chunk buffer, leaving the bump frontier where it was. Growing in
284 /// place looks at the active tail chunk alone, `self.current()`. A slice
285 /// allocated in an earlier chunk cannot grow in place.
286 pub const Chunks = struct {
287 /// Internal chunk storage holding the buffer descriptors and the growth
288 /// state that the methods work through. The owner maintains it, so a caller
289 /// accesses storage through `retain` and `discard` and takes no copy of it
290 /// and makes no direct changes.
291 inner: ChunkStorage,
292
293 const Self = @This();
294 /// Number of chunk descriptors tracked at one time, fixed at 64 to cap how
295 /// many chunks one instance holds at a time.
296 pub const maximum_chunk_count = ChunkStorage.maximum_chunk_count;
297
298 /// Starts a `Chunks` instance to open an allocation transaction over an
299 /// allocator the caller already has. It asserts that `initial_capacity > 0`
300 /// and that `maximum_capacity >= initial_capacity`. It allocates nothing
301 /// here: chunks are requested from the backing allocator as they are
302 /// needed.
303 pub fn init(
304 backing: Allocator,
305 initial_capacity: usize,
306 maximum_capacity: usize,
307 ) Self {
308 return .{ .inner = .init(
309 backing,
310 initial_capacity,
311 maximum_capacity,
312 ) };
313 }
314
315 /// Returns a borrowed `std.mem.Allocator` handle pointing at `self` to pass
316 /// to code that allocates. The `self` instance stays alive at one memory
317 /// address while the handle is in use.
318 pub fn allocator(self: *Self) Allocator {
319 return .{ .ptr = self, .vtable = &vtable };
320 }
321
322 /// Reports whether a given handle came from a `Chunks` instance, allowing a
323 /// caller to allocate straight into an open transaction when handed one. It
324 /// compares the candidate's vtable pointer against the `Chunks` vtable.
325 pub fn isAllocator(candidate: Allocator) bool {
326 return candidate.vtable == &vtable;
327 }
328
329 /// Commits every tracked chunk to the upstream backing owner and clears
330 /// tracking metadata when work succeeds. It sets the chunk descriptor count
331 /// to zero without freeing any backing memory. It leaves the current growth
332 /// schedule, `next_capacity`, as it is. Once retained, the backing memory
333 /// can no longer be freed through `Chunks.discard()`, and reclaiming it
334 /// belongs to the upstream backing owner.
335 pub fn retain(self: *Self) void {
336 self.inner.retain();
337 }
338
339 /// Rolls back an uncommitted transaction after failure by freeing all
340 /// tracked chunks to the backing allocator in reverse order. This
341 /// invalidates any allocations residing in those chunks and resets
342 /// `next_capacity` to `initial_capacity`. Chunks committed by an earlier
343 /// call to `retain()` are untouched and remain allocated. Actual physical
344 /// reuse of the freed memory depends on the free policy of the backing
345 /// allocator.
346 pub fn discard(self: *Self) void {
347 self.inner.discard();
348 }
349
350 fn rawAlloc(
351 context: *anyopaque,
352 len: usize,
353 alignment: Alignment,
354 return_address: usize,
355 ) ?[*]u8 {
356 const self: *Self = @ptrCast(@alignCast(context));
357 return self.inner.allocate(.retained, len, alignment, return_address);
358 }
359
360 fn rawResize(
361 context: *anyopaque,
362 memory: []u8,
363 alignment: Alignment,
364 new_len: usize,
365 return_address: usize,
366 ) bool {
367 const self: *Self = @ptrCast(@alignCast(context));
368 return self.inner.resize(memory, alignment, new_len, return_address);
369 }
370
371 fn rawRemap(
372 context: *anyopaque,
373 memory: []u8,
374 alignment: Alignment,
375 new_len: usize,
376 return_address: usize,
377 ) ?[*]u8 {
378 const self: *Self = @ptrCast(@alignCast(context));
379 return self.inner.remap(
380 .retained,
381 memory,
382 alignment,
383 new_len,
384 return_address,
385 );
386 }
387
388 fn rawFree(
389 context: *anyopaque,
390 memory: []u8,
391 alignment: Alignment,
392 return_address: usize,
393 ) void {
394 const self: *Self = @ptrCast(@alignCast(context));
395 self.inner.free(.retained, memory, alignment, return_address);
396 }
397
398 const vtable: Allocator.VTable = .{
399 .alloc = rawAlloc,
400 .resize = rawResize,
401 .remap = rawRemap,
402 .free = rawFree,
403 };
404 };
405
406 /// `Recycling` reuses memory chunks across repeated workloads to reduce
407 /// allocation calls to an upstream backing allocator. It tracks the count of
408 /// outstanding live allocations within each chunk. When deallocations bring
409 /// the live count of the active tail chunk to zero, that chunk is deactivated
410 /// and reset for subsequent reuse. Because reusing an inactive chunk requires
411 /// that its capacity and alignment satisfy the new request, subsequent
412 /// workloads may still require new backing allocations if existing chunks
413 /// lack sufficient size or alignment.
414 ///
415 /// ### Chunk deactivation and reuse constraints
416 /// - It compacts no holes, so a chunk that sits before the tail and has emptied
417 /// waits for every chunk behind it to empty too.
418 /// - Reusing an inactive chunk needs the alignment it was allocated at to meet
419 /// or exceed the requested alignment, and needs room for the request.
420 /// - In `rawRemap`, growth that cannot happen in place returns `null`, and a
421 /// caller going through `std.mem.Allocator.realloc` gets the allocate, copy,
422 /// and free path, which is how a reallocation crosses chunks.
423 /// - In `rawResize`, shrinking returns `true` at once and leaves the frontier
424 /// where it was, and growing in place looks at the active tail chunk alone.
425 pub const Recycling = struct {
426 /// Internal chunk storage holding the buffer descriptors and the live
427 /// allocation counts that the methods work through. The owner maintains it,
428 /// so a caller accesses storage through `reset` and `discard` and takes no
429 /// copy of it and makes no direct changes.
430 inner: ChunkStorage,
431
432 const Self = @This();
433 /// Ceiling on how many chunks one instance holds at a time, fixed at 64
434 /// chunk descriptors and counting the inactive chunks kept for reuse.
435 pub const maximum_chunk_count = ChunkStorage.maximum_chunk_count;
436
437 /// Starts a `Recycling` instance over an allocator the caller already has.
438 /// It asserts that `initial_capacity > 0` and that
439 /// `maximum_capacity >= initial_capacity`. It allocates nothing here: the
440 /// first request that needs backing memory takes it.
441 pub fn init(
442 backing: Allocator,
443 initial_capacity: usize,
444 maximum_capacity: usize,
445 ) Self {
446 return .{ .inner = .init(
447 backing,
448 initial_capacity,
449 maximum_capacity,
450 ) };
451 }
452
453 /// Returns a borrowed `std.mem.Allocator` handle pointing at `self` to pass
454 /// to code that allocates. The `self` instance stays alive at one memory
455 /// address while the handle is in use.
456 pub fn allocator(self: *Self) Allocator {
457 return .{ .ptr = self, .vtable = &vtable };
458 }
459
460 /// Resets every tracked chunk and deactivates them for reuse so the next
461 /// round of work can start with the chunks it already has. It rewinds the
462 /// bump frontier of every tracked chunk and sets its live allocation count
463 /// to zero. The backing memory stays where it is, so later allocations
464 /// reuse the existing chunks when the size and the alignment fit. It leaves
465 /// `next_capacity` as it is and clears the descriptor exhaustion flag.
466 /// Every allocation returned before becomes invalid.
467 pub fn reset(self: *Self) void {
468 self.inner.reset();
469 }
470
471 /// Returns every tracked chunk back to the allocator it came from and
472 /// starts the growth schedule over. It frees in reverse order, puts
473 /// `next_capacity` back at `initial_capacity`, and clears the descriptor
474 /// exhaustion flag.
475 pub fn discard(self: *Self) void {
476 self.inner.discard();
477 }
478
479 /// Reports whether an allocation failed because all 64 chunk descriptors
480 /// were taken, helping a caller separate a full descriptor table from an
481 /// exhausted backing allocator because the two need different fixes. It
482 /// stays set until `reset()` or `discard()`.
483 pub fn metadataExhausted(self: *const Self) bool {
484 return self.inner.metadata_exhausted;
485 }
486
487 fn rawAlloc(
488 context: *anyopaque,
489 len: usize,
490 alignment: Alignment,
491 return_address: usize,
492 ) ?[*]u8 {
493 const self: *Self = @ptrCast(@alignCast(context));
494 return self.inner.allocate(.recycling, len, alignment, return_address);
495 }
496
497 fn rawResize(
498 context: *anyopaque,
499 memory: []u8,
500 alignment: Alignment,
501 new_len: usize,
502 return_address: usize,
503 ) bool {
504 const self: *Self = @ptrCast(@alignCast(context));
505 return self.inner.resize(memory, alignment, new_len, return_address);
506 }
507
508 fn rawRemap(
509 context: *anyopaque,
510 memory: []u8,
511 alignment: Alignment,
512 new_len: usize,
513 return_address: usize,
514 ) ?[*]u8 {
515 const self: *Self = @ptrCast(@alignCast(context));
516 return self.inner.remap(
517 .recycling,
518 memory,
519 alignment,
520 new_len,
521 return_address,
522 );
523 }
524
525 fn rawFree(
526 context: *anyopaque,
527 memory: []u8,
528 alignment: Alignment,
529 return_address: usize,
530 ) void {
531 const self: *Self = @ptrCast(@alignCast(context));
532 self.inner.free(.recycling, memory, alignment, return_address);
533 }
534
535 const vtable: Allocator.VTable = .{
536 .alloc = rawAlloc,
537 .resize = rawResize,
538 .remap = rawRemap,
539 .free = rawFree,
540 };
541 };
542
543 const ChunkMode = enum {
544 retained,
545 recycling,
546 };
547
548 const ChunkStorage = struct {
549 backing: Allocator,
550 initial_capacity: usize,
551 maximum_capacity: usize,
552 next_capacity: usize,
553 chunks: [maximum_chunk_count]Chunk = undefined,
554 chunk_count: usize = 0,
555 active_indices: [maximum_chunk_count]u8 = undefined,
556 active_chunk_count: usize = 0,
557 metadata_exhausted: bool = false,
558
559 const Self = @This();
560 const maximum_chunk_count = 64;
561
562 const Chunk = struct {
563 fixed: FixedBuffer,
564 alignment: Alignment,
565 live_allocations: usize,
566 active: bool,
567 };
568
569 fn init(
570 backing: Allocator,
571 initial_capacity: usize,
572 maximum_capacity: usize,
573 ) Self {
574 std.debug.assert(initial_capacity > 0);
575 std.debug.assert(maximum_capacity >= initial_capacity);
576 return .{
577 .backing = backing,
578 .initial_capacity = initial_capacity,
579 .maximum_capacity = maximum_capacity,
580 .next_capacity = initial_capacity,
581 };
582 }
583
584 fn reset(self: *Self) void {
585 for (self.chunks[0..self.chunk_count]) |*chunk| {
586 chunk.fixed.reset();
587 chunk.live_allocations = 0;
588 chunk.active = false;
589 }
590 self.active_chunk_count = 0;
591 self.metadata_exhausted = false;
592 }
593
594 fn retain(self: *Self) void {
595 self.chunk_count = 0;
596 self.active_chunk_count = 0;
597 self.metadata_exhausted = false;
598 }
599
600 fn discard(self: *Self) void {
601 while (self.chunk_count != 0) {
602 self.chunk_count -= 1;
603 const chunk = &self.chunks[self.chunk_count];
604 self.backing.rawFree(
605 storage(&chunk.fixed),
606 chunk.alignment,
607 @returnAddress(),
608 );
609 }
610 self.active_chunk_count = 0;
611 self.next_capacity = self.initial_capacity;
612 self.metadata_exhausted = false;
613 }
614
615 fn allocate(
616 self: *Self,
617 mode: ChunkMode,
618 len: usize,
619 alignment: Alignment,
620 return_address: usize,
621 ) ?[*]u8 {
622 if (self.current()) |active| {
623 if (fits(&active.fixed, len, alignment)) {
624 return allocateFrom(
625 mode,
626 active,
627 len,
628 alignment,
629 return_address,
630 ) orelse unreachable;
631 }
632 }
633 if (!self.refill(mode, len, alignment)) return null;
634 return allocateFrom(
635 mode,
636 self.current().?,
637 len,
638 alignment,
639 return_address,
640 ) orelse unreachable;
641 }
642
643 fn resize(
644 self: *Self,
645 memory: []u8,
646 alignment: Alignment,
647 new_len: usize,
648 return_address: usize,
649 ) bool {
650 if (new_len <= memory.len) return true;
651 if (self.current()) |active| {
652 if (active.fixed.ownsSlice(memory)) {
653 return active.fixed.allocator().rawResize(
654 memory,
655 alignment,
656 new_len,
657 return_address,
658 );
659 }
660 }
661 return false;
662 }
663
664 fn remap(
665 self: *Self,
666 mode: ChunkMode,
667 memory: []u8,
668 alignment: Alignment,
669 new_len: usize,
670 return_address: usize,
671 ) ?[*]u8 {
672 if (new_len <= memory.len) return memory.ptr;
673 if (self.current()) |active| {
674 if (active.fixed.ownsSlice(memory)) {
675 if (active.fixed.allocator().rawRemap(
676 memory,
677 alignment,
678 new_len,
679 return_address,
680 )) |result| return result;
681 }
682 }
683 if (mode == .recycling) return null;
684 const result = self.allocate(
685 mode,
686 new_len,
687 alignment,
688 return_address,
689 ) orelse return null;
690 @memcpy(result[0..memory.len], memory);
691 return result;
692 }
693
694 fn free(
695 self: *Self,
696 mode: ChunkMode,
697 memory: []u8,
698 alignment: Alignment,
699 return_address: usize,
700 ) void {
701 if (mode == .retained) {
702 if (self.current()) |active| {
703 if (!active.fixed.ownsSlice(memory)) return;
704 active.fixed.allocator().rawFree(
705 memory,
706 alignment,
707 return_address,
708 );
709 }
710 return;
711 }
712
713 var active_position = self.active_chunk_count;
714 while (active_position != 0) {
715 active_position -= 1;
716 const active_index = self.active_indices[active_position];
717 const active = &self.chunks[active_index];
718 if (!active.fixed.ownsSlice(memory)) continue;
719 std.debug.assert(active.live_allocations > 0);
720 active.fixed.allocator().rawFree(
721 memory,
722 alignment,
723 return_address,
724 );
725 active.live_allocations -= 1;
726 self.deactivateEmptyTail();
727 return;
728 }
729 }
730
731 fn current(self: *Self) ?*Chunk {
732 if (self.active_chunk_count == 0) return null;
733 const active_index = self.active_indices[self.active_chunk_count - 1];
734 return &self.chunks[active_index];
735 }
736
737 noinline fn refill(
738 self: *Self,
739 mode: ChunkMode,
740 len: usize,
741 alignment: Alignment,
742 ) bool {
743 var retained_index: usize = 0;
744 while (retained_index < self.chunk_count) : (retained_index += 1) {
745 const retained = &self.chunks[retained_index];
746 if (retained.active) continue;
747 retained.fixed.reset();
748 if (mode == .recycling and
749 retained.alignment.toByteUnits() < alignment.toByteUnits())
750 {
751 continue;
752 }
753 if (!fits(&retained.fixed, len, alignment)) continue;
754 self.activate(retained_index);
755 return true;
756 }
757 if (self.chunk_count == self.chunks.len) {
758 if (mode == .recycling) self.metadata_exhausted = true;
759 return false;
760 }
761 const scheduled_capacity = self.next_capacity;
762 const capacity = @max(scheduled_capacity, len);
763 const chunk_alignment = Alignment.max(alignment, .@"16");
764 const pointer = self.backing.rawAlloc(
765 capacity,
766 chunk_alignment,
767 @returnAddress(),
768 ) orelse return false;
769 const bytes = pointer[0..capacity];
770 self.chunks[self.chunk_count] = .{
771 .fixed = FixedBuffer.init(bytes),
772 .alignment = chunk_alignment,
773 .live_allocations = 0,
774 .active = false,
775 };
776 self.chunk_count += 1;
777 self.activate(self.chunk_count - 1);
778 const doubled = std.math.mul(usize, scheduled_capacity, 2) catch
779 std.math.maxInt(usize);
780 self.next_capacity = @min(doubled, self.maximum_capacity);
781 return true;
782 }
783
784 fn activate(self: *Self, chunk_index: usize) void {
785 std.debug.assert(chunk_index < self.chunk_count);
786 std.debug.assert(!self.chunks[chunk_index].active);
787 std.debug.assert(self.chunks[chunk_index].live_allocations == 0);
788 std.debug.assert(self.active_chunk_count < self.active_indices.len);
789 self.chunks[chunk_index].active = true;
790 self.active_indices[self.active_chunk_count] = @intCast(chunk_index);
791 self.active_chunk_count += 1;
792 }
793
794 fn deactivateEmptyTail(self: *Self) void {
795 while (self.current()) |active| {
796 if (active.live_allocations != 0) return;
797 active.fixed.reset();
798 active.active = false;
799 self.active_chunk_count -= 1;
800 }
801 }
802
803 fn allocateFrom(
804 mode: ChunkMode,
805 chunk: *Chunk,
806 len: usize,
807 alignment: Alignment,
808 return_address: usize,
809 ) ?[*]u8 {
810 const result = chunk.fixed.allocator().rawAlloc(
811 len,
812 alignment,
813 return_address,
814 ) orelse return null;
815 if (mode == .recycling) {
816 std.debug.assert(
817 chunk.live_allocations < std.math.maxInt(usize),
818 );
819 chunk.live_allocations += 1;
820 }
821 return result;
822 }
823 };
824
825 /// A stream allocator with a bypass for oversized allocations, used inside an
826 /// arena that frees everything at once and keeps a large allocation from
827 /// throwing away the chunk in use. It refills fixed-capacity chunks of
828 /// `chunk_capacity` bytes from an upstream allocator for ordinary allocations.
829 /// A request longer than `chunk_capacity` goes straight to the backing
830 /// allocator, and the active tail chunk stays where it is.
831 ///
832 /// ### Reclamation and lifetime
833 /// It keeps metadata for the chunk in `current` alone. It has no `reset`,
834 /// `deinit`, or `discard` method. The backing allocator, typically an enclosing
835 /// `std.heap.ArenaAllocator`, reclaims the chunk memory when the owner around
836 /// it is torn down.
837 ///
838 /// ### Resize behavior
839 /// Shrinking returns `true` at once, leaving the frontier where it was. Growing
840 /// in place looks at `current` alone. Growth returns `false` for memory that
841 /// sits in an earlier chunk or came from the oversized bypass.
842 pub const Monotonic = struct {
843 /// Upstream allocator that provides the memory for chunks and for oversized
844 /// allocations.
845 backing: Allocator,
846 /// Fixed byte capacity of an ordinary chunk, which sets the length above
847 /// which a request bypasses the chunk.
848 chunk_capacity: usize,
849 /// The fixed buffer chunk in use that ordinary allocations are cut from,
850 /// which is `null` before the first allocation.
851 current: ?FixedBuffer = null,
852
853 const Self = @This();
854
855 /// Starts a `Monotonic` instance with a fixed chunk size to open a stream
856 /// allocator over an arena the caller already has. It asserts that
857 /// `chunk_capacity > 0`. It allocates nothing here.
858 pub fn init(backing: Allocator, chunk_capacity: usize) Self {
859 std.debug.assert(chunk_capacity > 0);
860 return .{
861 .backing = backing,
862 .chunk_capacity = chunk_capacity,
863 };
864 }
865
866 /// Returns a borrowed `std.mem.Allocator` handle pointing at `self` to pass
867 /// to code that allocates. The `self` instance stays alive at one memory
868 /// address while the handle is in use.
869 pub fn allocator(self: *Self) Allocator {
870 return .{ .ptr = self, .vtable = &vtable };
871 }
872
873 /// Confirms whether a given handle is this instance's backing allocator so
874 /// a caller knows the allocator hands memory to the arena expected to free
875 /// it. It checks the type-erased state pointer and the vtable pointer,
876 /// both.
877 pub fn isBackedBy(self: *const Self, candidate: Allocator) bool {
878 return self.backing.ptr == candidate.ptr and
879 self.backing.vtable == candidate.vtable;
880 }
881
882 fn rawAlloc(
883 context: *anyopaque,
884 len: usize,
885 alignment: Alignment,
886 return_address: usize,
887 ) ?[*]u8 {
888 const self: *Self = @ptrCast(@alignCast(context));
889 if (self.current) |*current| {
890 if (fits(current, len, alignment)) {
891 return current.allocator().rawAlloc(
892 len,
893 alignment,
894 return_address,
895 ) orelse unreachable;
896 }
897 }
898 if (len > self.chunk_capacity) {
899 return self.backing.rawAlloc(
900 len,
901 alignment,
902 @returnAddress(),
903 );
904 }
905 const chunk_alignment = Alignment.max(alignment, .@"16");
906 const pointer = self.backing.rawAlloc(
907 self.chunk_capacity,
908 chunk_alignment,
909 @returnAddress(),
910 ) orelse return null;
911 self.current = FixedBuffer.init(pointer[0..self.chunk_capacity]);
912 return self.current.?.allocator().rawAlloc(
913 len,
914 alignment,
915 return_address,
916 ) orelse unreachable;
917 }
918
919 fn rawResize(
920 context: *anyopaque,
921 memory: []u8,
922 alignment: Alignment,
923 new_len: usize,
924 return_address: usize,
925 ) bool {
926 if (new_len <= memory.len) return true;
927 const self: *Self = @ptrCast(@alignCast(context));
928 if (self.current) |*current| {
929 if (current.ownsSlice(memory)) {
930 return current.allocator().rawResize(
931 memory,
932 alignment,
933 new_len,
934 return_address,
935 );
936 }
937 }
938 return false;
939 }
940
941 fn rawRemap(
942 context: *anyopaque,
943 memory: []u8,
944 alignment: Alignment,
945 new_len: usize,
946 return_address: usize,
947 ) ?[*]u8 {
948 if (new_len <= memory.len) return memory.ptr;
949 const self: *Self = @ptrCast(@alignCast(context));
950 if (self.current) |*current| {
951 if (current.ownsSlice(memory)) {
952 if (current.allocator().rawRemap(
953 memory,
954 alignment,
955 new_len,
956 return_address,
957 )) |result| return result;
958 }
959 }
960 const result = rawAlloc(
961 self,
962 new_len,
963 alignment,
964 return_address,
965 ) orelse return null;
966 @memcpy(result[0..memory.len], memory);
967 return result;
968 }
969
970 fn rawFree(
971 context: *anyopaque,
972 memory: []u8,
973 alignment: Alignment,
974 return_address: usize,
975 ) void {
976 const self: *Self = @ptrCast(@alignCast(context));
977 if (self.current) |*current| {
978 if (current.ownsSlice(memory)) {
979 current.allocator().rawFree(
980 memory,
981 alignment,
982 return_address,
983 );
984 }
985 }
986 }
987
988 const vtable: Allocator.VTable = .{
989 .alloc = rawAlloc,
990 .resize = rawResize,
991 .remap = rawRemap,
992 .free = rawFree,
993 };
994 };
995
996 /// A two-tier allocator that serves small work from bytes the caller already
997 /// has and lets larger work reach the allocator behind it without the caller
998 /// choosing between them. It serves a request from `fixed` while the room and
999 /// the alignment fit, and hands the request to `backing` otherwise.
1000 ///
1001 /// ### Bounds and provenance routing
1002 /// - The `backing` allocator is any allocator the caller chooses, and
1003 /// `Fallback` adds no memory bound of its own, so a bounded backing allocator
1004 /// bounds the pair.
1005 /// - The `free` operation asks `fixed.ownsSlice(memory)`, and calls
1006 /// `fixed.allocator().rawFree()` for memory the fixed buffer owns and
1007 /// `backing.rawFree()` for the rest.
1008 /// - The `resize` operation tries to grow or shrink in place in the tier that
1009 /// owns the memory.
1010 /// - The `remap` operation on memory that started in `fixed` and cannot be
1011 /// resized in place allocates elsewhere, which may spill to `backing`, copies
1012 /// the bytes over, and frees the old memory from `fixed`, while memory that
1013 /// started in `backing` has its remap handed straight to `backing`.
1014 pub const Fallback = struct {
1015 /// Primary fixed-buffer storage owner that serves allocation requests
1016 /// first.
1017 fixed: FixedBuffer,
1018 /// Secondary backing allocator that takes requests once the primary fixed
1019 /// storage cannot fit them.
1020 backing: Allocator,
1021
1022 const Self = @This();
1023
1024 /// Starts a `Fallback` instance over a fixed storage buffer the caller
1025 /// supplies and a backing allocator.
1026 pub fn init(storage_bytes: []u8, backing: Allocator) Self {
1027 return .{
1028 .fixed = FixedBuffer.init(storage_bytes),
1029 .backing = backing,
1030 };
1031 }
1032
1033 /// Returns a borrowed `std.mem.Allocator` handle pointing at `self` to pass
1034 /// to code that allocates. The `self` instance stays alive at one memory
1035 /// address while the handle is in use.
1036 pub fn allocator(self: *Self) Allocator {
1037 return .{ .ptr = self, .vtable = &vtable };
1038 }
1039
1040 fn rawAlloc(
1041 context: *anyopaque,
1042 len: usize,
1043 alignment: Alignment,
1044 return_address: usize,
1045 ) ?[*]u8 {
1046 const self: *Self = @ptrCast(@alignCast(context));
1047 if (fits(&self.fixed, len, alignment)) {
1048 return self.fixed.allocator().rawAlloc(
1049 len,
1050 alignment,
1051 return_address,
1052 ) orelse unreachable;
1053 }
1054 return self.backing.rawAlloc(
1055 len,
1056 alignment,
1057 return_address,
1058 );
1059 }
1060
1061 fn rawResize(
1062 context: *anyopaque,
1063 memory: []u8,
1064 alignment: Alignment,
1065 new_len: usize,
1066 return_address: usize,
1067 ) bool {
1068 const self: *Self = @ptrCast(@alignCast(context));
1069 if (self.fixed.ownsSlice(memory)) {
1070 return self.fixed.allocator().rawResize(
1071 memory,
1072 alignment,
1073 new_len,
1074 return_address,
1075 );
1076 }
1077 return self.backing.rawResize(
1078 memory,
1079 alignment,
1080 new_len,
1081 return_address,
1082 );
1083 }
1084
1085 fn rawRemap(
1086 context: *anyopaque,
1087 memory: []u8,
1088 alignment: Alignment,
1089 new_len: usize,
1090 return_address: usize,
1091 ) ?[*]u8 {
1092 const self: *Self = @ptrCast(@alignCast(context));
1093 if (!self.fixed.ownsSlice(memory)) {
1094 return self.backing.rawRemap(
1095 memory,
1096 alignment,
1097 new_len,
1098 return_address,
1099 );
1100 }
1101 if (self.fixed.allocator().rawRemap(
1102 memory,
1103 alignment,
1104 new_len,
1105 return_address,
1106 )) |result| return result;
1107 const result = rawAlloc(
1108 self,
1109 new_len,
1110 alignment,
1111 return_address,
1112 ) orelse return null;
1113 @memcpy(result[0..@min(memory.len, new_len)], memory[0..@min(memory.len, new_len)]);
1114 self.fixed.allocator().rawFree(
1115 memory,
1116 alignment,
1117 return_address,
1118 );
1119 return result;
1120 }
1121
1122 fn rawFree(
1123 context: *anyopaque,
1124 memory: []u8,
1125 alignment: Alignment,
1126 return_address: usize,
1127 ) void {
1128 const self: *Self = @ptrCast(@alignCast(context));
1129 if (self.fixed.ownsSlice(memory)) {
1130 self.fixed.allocator().rawFree(
1131 memory,
1132 alignment,
1133 return_address,
1134 );
1135 return;
1136 }
1137 self.backing.rawFree(
1138 memory,
1139 alignment,
1140 return_address,
1141 );
1142 }
1143
1144 const vtable: Allocator.VTable = .{
1145 .alloc = rawAlloc,
1146 .resize = rawResize,
1147 .remap = rawRemap,
1148 .free = rawFree,
1149 };
1150 };
1151
1152 /// Stand-in for `FixedBuffer` when the build turns allocation observation on,
1153 /// wrapping `std.heap.FixedBufferAllocator` and publishing an event for every
1154 /// operation to `alloc_observe`.
1155 const ObservedFixedBuffer = struct {
1156 /// Wrapped standard library fixed buffer allocator performing the work
1157 /// behind the instrumentation. The owner maintains it, and changing its
1158 /// fields directly is unsupported.
1159 inner: std.heap.FixedBufferAllocator,
1160 /// Producer identity assigned by `alloc_observe.producerId()` to attribute
1161 /// the events of one session.
1162 producer_id: u64,
1163
1164 const Self = @This();
1165
1166 /// Puts an instrumented allocator over `buffer` and gives it the identity
1167 /// its events carry for the session.
1168 pub fn init(buffer: []u8) Self {
1169 return .{
1170 .inner = std.heap.FixedBufferAllocator.init(buffer),
1171 .producer_id = observe.producerId(),
1172 };
1173 }
1174
1175 /// Returns a single-threaded `std.mem.Allocator` handle instrumented with
1176 /// allocation events.
1177 pub fn allocator(self: *Self) Allocator {
1178 return .{
1179 .ptr = self,
1180 .vtable = &VTable(false).vtable,
1181 };
1182 }
1183
1184 /// Returns a thread-safe `std.mem.Allocator` handle instrumented with
1185 /// allocation events so concurrent threads can allocate from one buffer.
1186 /// The `FixedBufferAllocator` underneath advances the bump frontier with
1187 /// lock-free compare-and-swap. The instrumented events reach the
1188 /// observation sink callbacks the build configured, and those callbacks
1189 /// answer for their own concurrency and locking. A caller keeps concurrent
1190 /// use apart from `allocator()` and leaves `reset()` alone while
1191 /// thread-safe operations may be running.
1192 pub fn threadSafeAllocator(self: *Self) Allocator {
1193 return .{
1194 .ptr = self,
1195 .vtable = &VTable(true).vtable,
1196 };
1197 }
1198
1199 /// Returns `true` when the pointer sits inside the backing buffer, telling
1200 /// memory from this buffer apart from memory that came from elsewhere.
1201 pub fn ownsPtr(self: *Self, ptr: [*]u8) bool {
1202 return self.inner.ownsPtr(ptr);
1203 }
1204
1205 /// Returns `true` when the whole slice sits inside the backing buffer,
1206 /// allowing a caller to route a free or a resize to the tier that owns the
1207 /// memory.
1208 pub fn ownsSlice(self: *Self, slice: []u8) bool {
1209 return self.inner.ownsSlice(slice);
1210 }
1211
1212 /// Returns `true` for the allocation that ends exactly at the frontier, the
1213 /// one made most recently, which is the test for whether an allocation can
1214 /// grow in place or be freed back. It forwards the standard library's
1215 /// endpoint check, `buf.ptr + buf.len == buffer.ptr + end_index`. A fresh
1216 /// allocation always matches `end_index`. It answers `false` for an
1217 /// allocation that is the most recent live one, once a later aligned
1218 /// allocation has been freed: that free lowers `end_index` by the payload
1219 /// length alone and leaves the alignment padding behind, so the earlier
1220 /// allocation's endpoint ends below `end_index`.
1221 pub fn isLastAllocation(self: *Self, buffer: []u8) bool {
1222 return self.inner.isLastAllocation(buffer);
1223 }
1224
1225 /// Rewinds the bump frontier to zero to hand the whole buffer back to the
1226 /// next round of work.
1227 pub fn reset(self: *Self) void {
1228 self.inner.reset();
1229 }
1230
1231 fn VTable(comptime thread_safe: bool) type {
1232 return struct {
1233 const vtable: Allocator.VTable = .{
1234 .alloc = rawAlloc,
1235 .resize = rawResize,
1236 .remap = rawRemap,
1237 .free = rawFree,
1238 };
1239
1240 fn innerAllocator(self: *Self) Allocator {
1241 return if (thread_safe)
1242 self.inner.threadSafeAllocator()
1243 else
1244 self.inner.allocator();
1245 }
1246
1247 fn rawAlloc(
1248 context: *anyopaque,
1249 len: usize,
1250 alignment: Alignment,
1251 return_address: usize,
1252 ) ?[*]u8 {
1253 const self: *Self = @ptrCast(@alignCast(context));
1254 var span = observe.begin(
1255 self.producer_id,
1256 .fixed_buffer,
1257 .alloc,
1258 0,
1259 0,
1260 len,
1261 alignment.toByteUnits(),
1262 return_address,
1263 );
1264 const result = innerAllocator(self).rawAlloc(
1265 len,
1266 alignment,
1267 return_address,
1268 );
1269 span.finish(.{
1270 .address = if (result) |ptr| @intFromPtr(ptr) else 0,
1271 .succeeded = result != null,
1272 });
1273 return result;
1274 }
1275
1276 fn rawResize(
1277 context: *anyopaque,
1278 memory: []u8,
1279 alignment: Alignment,
1280 new_len: usize,
1281 return_address: usize,
1282 ) bool {
1283 const self: *Self = @ptrCast(@alignCast(context));
1284 var span = observe.begin(
1285 self.producer_id,
1286 .fixed_buffer,
1287 .resize,
1288 @intFromPtr(memory.ptr),
1289 memory.len,
1290 new_len,
1291 alignment.toByteUnits(),
1292 return_address,
1293 );
1294 const succeeded = innerAllocator(self).rawResize(
1295 memory,
1296 alignment,
1297 new_len,
1298 return_address,
1299 );
1300 span.finish(.{
1301 .address = if (succeeded) @intFromPtr(memory.ptr) else 0,
1302 .succeeded = succeeded,
1303 });
1304 return succeeded;
1305 }
1306
1307 fn rawRemap(
1308 context: *anyopaque,
1309 memory: []u8,
1310 alignment: Alignment,
1311 new_len: usize,
1312 return_address: usize,
1313 ) ?[*]u8 {
1314 const self: *Self = @ptrCast(@alignCast(context));
1315 var span = observe.begin(
1316 self.producer_id,
1317 .fixed_buffer,
1318 .remap,
1319 @intFromPtr(memory.ptr),
1320 memory.len,
1321 new_len,
1322 alignment.toByteUnits(),
1323 return_address,
1324 );
1325 const result = innerAllocator(self).rawRemap(
1326 memory,
1327 alignment,
1328 new_len,
1329 return_address,
1330 );
1331 span.finish(.{
1332 .address = if (result) |ptr| @intFromPtr(ptr) else 0,
1333 .succeeded = result != null,
1334 });
1335 return result;
1336 }
1337
1338 fn rawFree(
1339 context: *anyopaque,
1340 memory: []u8,
1341 alignment: Alignment,
1342 return_address: usize,
1343 ) void {
1344 const self: *Self = @ptrCast(@alignCast(context));
1345 var span = observe.begin(
1346 self.producer_id,
1347 .fixed_buffer,
1348 .free,
1349 @intFromPtr(memory.ptr),
1350 memory.len,
1351 0,
1352 alignment.toByteUnits(),
1353 return_address,
1354 );
1355 innerAllocator(self).rawFree(
1356 memory,
1357 alignment,
1358 return_address,
1359 );
1360 span.finish(.{
1361 .address = @intFromPtr(memory.ptr),
1362 .succeeded = true,
1363 });
1364 }
1365 };
1366 }
1367 };