lib/alloc/fixed/src/root.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! ## Package overview
2 //!
3 //! Allocation strategies in this implementation package at `lib/alloc/fixed`
4 //! work over a buffer the caller provides or over an allocator upstream. A
5 //! reader chooses among the six strategies by what each one allocates from and
6 //! what that choice costs to reclaim. `Tracked` keeps the bump frontier offset
7 //! and records that a raw allocation ran out of room, while `used` reports the
8 //! current bump frontier offset.
9 //!
10 //! ### Tracked frontier accounting
11 //!
12 //! The struct `Tracked` keeps its numbers over a byte slice the caller
13 //! provides.
14 //!
15 //! ```zig
16 //! test "tutorial: tracked frontier accounting and reset" {
17 //! const std = @import("std");
18 //! const alloc_fixed = @import("alloc_fixed");
19 //!
20 //! var storage: [64]u8 align(16) = undefined;
21 //! var tracked = alloc_fixed.Tracked.init(&storage);
22 //! const allocator = tracked.allocator();
23 //!
24 //! // 1. Initial allocation advances the current frontier
25 //! const first = try allocator.alloc(u8, 24);
26 //! var status = tracked.status();
27 //! try std.testing.expectEqual(@as(usize, 24), status.used_bytes);
28 //! try std.testing.expectEqual(@as(usize, 24), status.peak_bytes);
29 //! try std.testing.expectEqual(@as(usize, 24), status.high_water_bytes);
30 //! try std.testing.expect(!status.exhausted);
31 //!
32 //! // 2. Second allocation advances the frontier further
33 //! const second = try allocator.alloc(u8, 24);
34 //! status = tracked.status();
35 //! try std.testing.expectEqual(@as(usize, 48), status.used_bytes);
36 //! try std.testing.expectEqual(@as(usize, 48), status.peak_bytes);
37 //!
38 //! // 3. Freeing the last allocation at the frontier reduces used_bytes
39 //! allocator.free(second);
40 //! status = tracked.status();
41 //! try std.testing.expectEqual(@as(usize, 24), status.used_bytes);
42 //! try std.testing.expectEqual(@as(usize, 48), status.peak_bytes);
43 //!
44 //! // 4. Raw allocation failure sets the sticky exhausted flag
45 //! try std.testing.expectError(error.OutOfMemory, allocator.alloc(u8, 48));
46 //! status = tracked.status();
47 //! try std.testing.expect(status.exhausted);
48 //!
49 //! allocator.free(first);
50 //!
51 //! // 5. Reset rewinds the frontier and clears peak and exhausted
52 //! tracked.reset();
53 //! status = tracked.status();
54 //! try std.testing.expectEqual(@as(usize, 0), status.used_bytes);
55 //! try std.testing.expectEqual(@as(usize, 0), status.peak_bytes);
56 //! try std.testing.expectEqual(@as(usize, 48), status.high_water_bytes);
57 //! try std.testing.expect(!status.exhausted);
58 //! }
59 //! ```
60 //!
61 //! Callers wrap `Tracked` to hold a phase to its limit and read the sticky
62 //! record that a raw allocation came back empty for want of room through
63 //! `status().exhausted`, the *exhausted flag*.
64 //!
65 //! ### Allocation capabilities and owner stability
66 //!
67 //! In the Zig standard library a `std.mem.Allocator` is a pointer to the struct
68 //! that holds the storage and the bookkeeping behind an allocator handle, the
69 //! *owner*, paired with a pointer to a table of allocation functions, forming
70 //! the *allocator handle*:
71 //! - `ptr: *anyopaque` is the type-erased pointer to the owner that holds the
72 //! state
73 //! - `vtable: *const VTable` points at the table of allocation functions
74 //!
75 //! The `allocator()` method borrows that handle from one of six owners:
76 //! `Tracked`, `Chunks`, `Recycling`, `Monotonic`, `Fallback`, or `FixedBuffer`.
77 //!
78 //! The duty of the caller to keep the owner alive and at one address for as
79 //! long as a handle points at it is *owner stability*. Copying the owner leaves
80 //! handles that already exist pointing at the original address, so working with
81 //! copies as independent allocators over the same storage drives their state
82 //! apart. Reaching a handle after the owner moves or goes away is undefined
83 //! behavior.
84 //!
85 //! ### Physical capacity, bump frontier, and alignment
86 //!
87 //! Four concepts govern the fixed-buffer and chunked strategies:
88 //!
89 //! 1. The whole byte slice an owner has to cut allocations from, which the
90 //! caller provides or that comes from an upstream allocator, is the
91 //! *physical capacity*.
92 //! 2. The byte offset reached so far inside a buffer, which every allocation
93 //! advances, is the *bump frontier* (`used`). In `FixedBuffer` and `Tracked`
94 //! it moves back when the newest allocation is freed or made smaller, but it
95 //! stays where it is when an allocation is freed while later ones are still
96 //! live.
97 //! 3. The bytes skipped to bring a pointer to the alignment a request asks for
98 //! are the *alignment padding*. Padding carries the frontier past the
99 //! requested length. Rewinding the frontier to zero with a *reset* makes
100 //! that space available again, while freeing the most recent allocation
101 //! first, a *LIFO free*, on its own leaves the alignment gaps behind.
102 //! 4. When memory comes back and how is the *reclamation policy*. In the bump
103 //! and chunk strategies, freeing one allocation returns no interior hole, so
104 //! memory comes back in bulk, through `reset`, `discard`, or the teardown of
105 //! the arena behind the owner.
106 //!
107 //! ### Backing allocators and chunk retention
108 //!
109 //! Several strategies take memory from an upstream allocator supplied by the
110 //! caller, the *backing allocator* (`backing: Allocator`). A buffer obtained
111 //! from the backing allocator to serve multiple allocations is a *chunk*.
112 //! `Chunks`, `Recycling`, and `Monotonic` request chunks from this backing
113 //! allocator. By contrast, `Fallback` first uses its caller-supplied byte
114 //! slice and passes spill requests directly upstream.
115 //!
116 //! To track chunks, `Chunks` and `Recycling` each maintain at most 64 *chunk
117 //! descriptors*, where each descriptor records chunk storage and bookkeeping:
118 //! the buffer, its alignment, its active flag, and a count of live
119 //! allocations maintained only by `Recycling`. This fixed table bounds the
120 //! number of simultaneously tracked chunks rather than the total count of
121 //! allocation requests. That 64-descriptor bound applies only to `Chunks` and
122 //! `Recycling`: `Monotonic` retains only its current chunk descriptor, while
123 //! `Fallback` passes spill requests directly upstream.
124 //!
125 //! In `Recycling`, inactive chunk descriptors are kept for reuse and still
126 //! occupy slots in the table. In `Chunks`, calling `retain()` clears
127 //! descriptor tracking without freeing backing memory, so those committed
128 //! chunks no longer occupy its descriptor table.
129 //!
130 //! The next fresh chunk has `@max(scheduled_capacity, len)` bytes, taking the
131 //! larger of a planned size or the requested length. This planned capacity
132 //! starts at `initial_capacity`, doubles after each successful fresh chunk,
133 //! and stops growing at `maximum_capacity`, forming the *growth schedule*.
134 //! Reused chunks do not advance the schedule. Oversized requests are allowed
135 //! and do not change the doubling calculation to use their actual size. Thus
136 //! `maximum_capacity` caps the schedule, not individual requests or total
137 //! storage.
138 //!
139 //! - Clearing the descriptor table without freeing the backing memory through
140 //! `retain()` commits the chunks to the lifetime of the upstream owner
141 //! - `lib/chic/src/language/value/own.zig` uses that pattern to commit values
142 //! it cloned into an outer arena
143 //! - Freeing every tracked chunk in reverse order back to the backing allocator
144 //! and putting the growth schedule back where it started rolls the chunks
145 //! back through `discard()`
146 //! - In `Recycling`, the number of allocations still outstanding in one chunk
147 //! is tracked for each chunk as the *live allocation count*
148 //! - When frees bring the live count of the most recently activated chunk that
149 //! every allocation tries first, the *tail chunk*, to zero, that chunk is
150 //! deactivated by closing it and rewinding it, ready for the next allocation
151 //! - In `Recycling`, `rawRemap` returns `null` when it cannot grow the memory
152 //! where it sits, and a caller going through `std.mem.Allocator.realloc` then
153 //! gets the allocate, copy, and free path across chunks
154 //! - `rawResize` in `Chunks`, in `Recycling`, and in `Monotonic` answers `true`
155 //! as soon as `new_len <= memory.len`, before it consults any chunk
156 //! - Shrinking therefore leaves the bump frontier where it was in those three,
157 //! even for the most recent allocation
158 //! - Growing in place checks whether the memory belongs to the chunk currently
159 //! open for allocation, the *active chunk*
160 //!
161 //! ### Strategy overview
162 //!
163 //! - `FixedBuffer`: the caller's slice, reclaimed by LIFO free or `reset()`
164 //! - `Tracked`: the caller's slice, with the frontier, the peak, the high-water
165 //! mark, and the exhausted flag
166 //! - `Chunks`: a backing allocator, a doubling schedule, `retain()` to commit,
167 //! and `discard()` to roll back
168 //! - `Recycling`: a backing allocator, tail chunk reuse, and the 64-descriptor
169 //! limit
170 //! - `Monotonic`: a backing allocator, fixed chunks, the oversized bypass, and
171 //! reclamation by arena teardown
172 //! - `Fallback`: the caller's slice with spillover to a backing allocator, and
173 //! operations routed by provenance
174 //!
175 //! ### Primary literature and historical context
176 //!
177 //! - **David R. Hanson (1990):** *Fast Allocation and Deallocation of Memory
178 //! Based on Object
179 //! Lifetimes*, Software: Practice and Experience 20(1), pages 5–12, DOI:
180 //! 10.1002/spe.4380200104.
181 //! [Author Scan](https://drhanson.s3.amazonaws.com/storage/documents/fastalloc.pdf).
182 //!
183 //! Hanson grouped allocations by intended lifetime, allocated sequentially
184 //! from a linked list of buffers, and deallocated each lifetime group
185 //! together by resetting state to make backing buffers available for reuse
186 //! instead of returning every block to the operating system. `Chunks`
187 //! similarly groups allocations for a shared lifetime: `retain()` forgets
188 //! tracked descriptors without freeing chunks and leaves committed storage
189 //! to the upstream lifetime owner, while `discard()` issues backing frees
190 //! for uncommitted chunks in reverse order. Actual physical reuse of the
191 //! freed memory depends on the free policy of the backing allocator.
192 //!
193 //! - **Mads Tofte and Jean-Pierre Talpin (POPL 1994):** *Implementation of the
194 //! Typed Call-by-Value
195 //! lambda-Calculus using a Stack of Regions*, pages 188–201, DOI:
196 //! 10.1145/174675.177855.
197 //! [Paper](https://www.cs.cmu.edu/afs/cs/academic/class/15745-s06/web/handouts/tofte-popl94.pdf).
198 //!
199 //! Tofte and Talpin gave a proof that their translation, which annotates a
200 //! program with regions, agrees with a store semantics built on regions, and
201 //! their inference of regions and effects settles at compile time where
202 //! memory is taken and given back. This package infers no region lifetimes
203 //! and proves none: a caller manages memory through the borrowed handles
204 //! instead.
205 //!
206 //! - **David Gay and Alex Aiken (PLDI 1998):** *Memory Management with Explicit
207 //! Regions*,
208 //! pages 313–323, DOI: 10.1145/277650.277748.
209 //! [Author Site](https://theory.stanford.edu/~aiken/publications/papers/pldi98a.pdf).
210 //!
211 //! Gay and Aiken designed safe regions by counting external region
212 //! references through tracked region pointers, where `deleteregion` does
213 //! nothing while the relevant reference count is nonzero. This mechanism
214 //! tracks region pointers, so `deleteregion` does not account for region
215 //! pointers cast to ordinary pointers. `Recycling` differs in purpose: its
216 //! counts track outstanding allocations inside each chunk solely to find
217 //! empty tails to deactivate and reuse. It tracks no references held
218 //! outside and provides no dangling-pointer protection.
219 //!
220 //! ### Executable examples
221 //!
222 //! #### Transactional chunks commit and rollback (`Chunks`)
223 //!
224 //! The example rolls back after an injected failure from
225 //! `std.testing.FailingAllocator`, retries, commits with `retain()`, and shows
226 //! a request larger than `maximum_capacity` succeeding.
227 //!
228 //! ```zig
229 //! test "tutorial: transactional chunks rollback on injected failure and commit" {
230 //! const std = @import("std");
231 //! const alloc_fixed = @import("alloc_fixed");
232 //!
233 //! var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
234 //! defer arena.deinit();
235 //!
236 //! // 1. Transaction failure scenario with injected allocation failure
237 //! {
238 //! var failing = std.testing.FailingAllocator.init(
239 //! arena.allocator(),
240 //! .{ .fail_index = 1 }, // Second backing allocation fails
241 //! );
242 //! var transaction = alloc_fixed.Chunks.init(failing.allocator(), 64, 128);
243 //! errdefer transaction.discard();
244 //!
245 //! // First chunk allocation (64 bytes) succeeds
246 //! _ = try transaction.allocator().alloc(u8, 48);
247 //! try std.testing.expectEqual(@as(usize, 1), failing.allocations);
248 //! try std.testing.expectEqual(@as(usize, 64), failing.allocated_bytes);
249 //!
250 //! // Second allocation (96 bytes) requires a new chunk; backing alloc returns null
251 //! const failed_alloc = transaction.allocator().alloc(u8, 96);
252 //! try std.testing.expectError(error.OutOfMemory, failed_alloc);
253 //!
254 //! // Rollback frees the first chunk back to the backing allocator
255 //! transaction.discard();
256 //! try std.testing.expectEqual(@as(usize, 64), failing.freed_bytes);
257 //! try std.testing.expectEqual(failing.allocated_bytes, failing.freed_bytes);
258 //! }
259 //!
260 //! // 2. Transaction success scenario committing memory via retain()
261 //! {
262 //! var transaction = alloc_fixed.Chunks.init(arena.allocator(), 64, 128);
263 //! const alloc = transaction.allocator();
264 //!
265 //! const data1 = try alloc.alloc(u8, 48);
266 //! const data2 = try alloc.alloc(u8, 96);
267 //! // Requests exceeding maximum_capacity allocate max(scheduled, len)
268 //! const oversized = try alloc.alloc(u8, 200);
269 //!
270 //! @memset(data1, 0xAA);
271 //! @memset(data2, 0xBB);
272 //! @memset(oversized, 0xCC);
273 //!
274 //! // Commit chunks to backing arena; transaction metadata is forgotten
275 //! transaction.retain();
276 //!
277 //! for (data1) |b| try std.testing.expectEqual(@as(u8, 0xAA), b);
278 //! for (data2) |b| try std.testing.expectEqual(@as(u8, 0xBB), b);
279 //! for (oversized) |b| try std.testing.expectEqual(@as(u8, 0xCC), b);
280 //! }
281 //! }
282 //! ```
283 //!
284 //! #### Tail-chunk recycling and metadata exhaustion (`Recycling`)
285 //!
286 //! The example follows the live allocation count, the tail chunk deactivating
287 //! so its memory is reused, and the 64-descriptor limit being reached while the
288 //! backing storage still has room.
289 //!
290 //! ```zig
291 //! test "tutorial: recycling tail deactivation and metadata exhaustion" {
292 //! const std = @import("std");
293 //! const alloc_fixed = @import("alloc_fixed");
294 //!
295 //! var backing_bytes: [2048]u8 align(16) = undefined;
296 //! var backing_tracked = alloc_fixed.Tracked.init(&backing_bytes);
297 //!
298 //! var recycling = alloc_fixed.Recycling.init(
299 //! backing_tracked.allocator(),
300 //! 64,
301 //! 128,
302 //! );
303 //! defer recycling.discard();
304 //! const allocator = recycling.allocator();
305 //!
306 //! const chunk1_slice = try allocator.alloc(u8, 48);
307 //! const chunk2_slice = try allocator.alloc(u8, 80);
308 //! try std.testing.expect(backing_tracked.status().used_bytes >= 144);
309 //!
310 //! allocator.free(chunk2_slice);
311 //! allocator.free(chunk1_slice);
312 //!
313 //! const high_water_before = backing_tracked.status().high_water_bytes;
314 //! const reused_slice = try allocator.alloc(u8, 48);
315 //! defer allocator.free(reused_slice);
316 //! try std.testing.expectEqual(high_water_before, backing_tracked.status().high_water_bytes);
317 //!
318 //! var slot_tester = alloc_fixed.Recycling.init(
319 //! backing_tracked.allocator(),
320 //! 16,
321 //! 16,
322 //! );
323 //! defer slot_tester.discard();
324 //!
325 //! for (0..alloc_fixed.Recycling.maximum_chunk_count) |_| {
326 //! _ = try slot_tester.allocator().alloc(u8, 16);
327 //! }
328 //!
329 //! try std.testing.expectError(error.OutOfMemory, slot_tester.allocator().alloc(u8, 16));
330 //! try std.testing.expect(slot_tester.metadataExhausted());
331 //! try std.testing.expect(!backing_tracked.status().exhausted);
332 //! }
333 //! ```
334 //!
335 //! #### Fixed buffer with backing spillover (`Fallback`)
336 //!
337 //! The example serves the first allocations from the fixed buffer, spills the
338 //! next to the caller's backing allocator, and checks which tier owns each
339 //! slice along with the count of backing allocations.
340 //!
341 //! ```zig
342 //! test "tutorial: fallback buffer with backing spillover" {
343 //! const std = @import("std");
344 //! const alloc_fixed = @import("alloc_fixed");
345 //!
346 //! var storage: [64]u8 align(16) = undefined;
347 //! var counting = std.testing.FailingAllocator.init(std.testing.allocator, .{});
348 //! var fallback = alloc_fixed.Fallback.init(&storage, counting.allocator());
349 //! const allocator = fallback.allocator();
350 //! const fixed_buf = try allocator.alloc(u8, 48);
351 //! defer allocator.free(fixed_buf);
352 //! @memset(fixed_buf, 0x11);
353 //! try std.testing.expect(fallback.fixed.ownsSlice(fixed_buf));
354 //! try std.testing.expectEqual(@as(usize, 0), counting.alloc_index);
355 //! const backing_buf = try allocator.alloc(u8, 32);
356 //! defer allocator.free(backing_buf);
357 //! @memset(backing_buf, 0x22);
358 //! try std.testing.expect(!fallback.fixed.ownsSlice(backing_buf));
359 //! try std.testing.expectEqual(@as(usize, 1), counting.alloc_index);
360 //! }
361 //! ```
362 //!
363 //! #### Stream allocation with oversized bypass (`Monotonic`)
364 //!
365 //! The example fills fixed-capacity chunks while an oversized allocation goes
366 //! straight to the backing allocator, leaving the active tail chunk in place.
367 //!
368 //! ```zig
369 //! test "tutorial: monotonic stream allocation and preserved tail" {
370 //! const std = @import("std");
371 //! const alloc_fixed = @import("alloc_fixed");
372 //! var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
373 //! defer arena.deinit();
374 //! var mono = alloc_fixed.Monotonic.init(arena.allocator(), 64);
375 //! const allocator = mono.allocator();
376 //! const first = try allocator.alloc(u8, 20);
377 //! const second = try allocator.alloc(u8, 20);
378 //! const oversized = try allocator.alloc(u8, 128);
379 //! const tail = try allocator.alloc(u8, 16);
380 //! @memset(first, 0x01);
381 //! @memset(second, 0x02);
382 //! @memset(oversized, 0x03);
383 //! @memset(tail, 0x04);
384 //! try std.testing.expectEqual(@intFromPtr(second.ptr) + second.len, @intFromPtr(tail.ptr));
385 //! try std.testing.expect(@intFromPtr(oversized.ptr) != @intFromPtr(second.ptr) + second.len);
386 //! try std.testing.expect(mono.isBackedBy(arena.allocator()));
387 //! }
388 //! ```
389
390 const fixed = @import("fixed.zig");
391
392 /// `Chunks` builds a result across several allocations, committing backing
393 /// chunks to an outer owner through `retain()` or invoking upstream frees for
394 /// rollback through `discard()`.
395 ///
396 /// Fresh chunks requested from the backing allocator follow a growth schedule
397 /// that starts at `initial_capacity`, doubles after each successful fresh
398 /// chunk, and stops growing at `maximum_capacity`, with each fresh chunk
399 /// sized to `@max(scheduled_capacity, len)`. Requests larger than the
400 /// scheduled size are permitted without altering the doubling calculation,
401 /// but can fail from exhausted descriptor slots or backing allocation
402 /// failure.
403 ///
404 /// The owner tracks at most 64 chunk descriptors simultaneously. Calling
405 /// `retain()` clears the descriptor table without freeing backing memory,
406 /// leaving committed storage for the upstream lifetime owner to reclaim.
407 pub const Chunks = fixed.Chunks;
408
409 /// When small work can run on the stack while larger requests spill to the
410 /// heap, `Fallback` tries a fixed storage buffer first and falls back to a
411 /// backing allocator. It adds no memory bound of its own, so the bound is
412 /// whatever the backing allocator imposes. Provenance routing sends every later
413 /// `free`, `resize`, or `remap` to the tier that owns the slice.
414 pub const Fallback = fixed.Fallback;
415
416 /// `FixedBuffer` is a fixed-capacity bump allocator that cuts allocations from
417 /// a caller-owned byte slice with no allocator behind it. With allocation
418 /// observation compiled in (`-Dobserve-allocations=true`) it resolves to
419 /// `ObservedFixedBuffer`, and with observation off it is
420 /// `std.heap.FixedBufferAllocator`.
421 pub const FixedBuffer = fixed.FixedBuffer;
422
423 /// To stream allocations inside an arena that will free everything at once,
424 /// `Monotonic` refills fixed-capacity chunks from a backing allocator. An
425 /// oversized allocation bypasses the chunk chain straight to backing storage,
426 /// leaving the active tail chunk in place. Built for growth inside an enclosing
427 /// arena lifetime, the owner has no `reset` and no `discard`, so the arena
428 /// behind it reclaims the memory.
429 pub const Monotonic = fixed.Monotonic;
430
431 /// `Recycling` reuses memory chunks across repeated workloads by tracking
432 /// outstanding allocations across up to 64 chunk descriptors, including
433 /// inactive chunks kept for reuse. When deallocations bring the live count of
434 /// the active tail chunk to zero, that chunk is deactivated and reset for
435 /// subsequent reuse. Because reusing an inactive chunk requires that its
436 /// capacity and alignment satisfy the new request, subsequent workloads may
437 /// still require new backing allocations if existing chunks lack sufficient
438 /// size or alignment.
439 pub const Recycling = fixed.Recycling;
440
441 /// `Tracked` provides fixed-capacity bump allocation over a caller-supplied
442 /// slice while measuring exact memory consumption. Bookkeeping records the
443 /// current bump frontier offset, the peak offset reached since the last reset,
444 /// the high-water mark over the owner's whole life, and the exhausted flag that
445 /// latches any raw allocation that ran out of room.
446 pub const Tracked = fixed.Tracked;
447
448 /// `used` reports in bytes how far the bump frontier of a `FixedBuffer` has
449 /// moved. That figure counts both payload bytes and alignment padding. The
450 /// figure stands above the bytes that are live once an allocation has been
451 /// freed ahead of a later one, and once alignment gaps remain behind.
452 pub const used = fixed.used;