alloc_fixed

Internal implementation documentation

Overview · API · Code relationships · Verification · Audit

Overview

Package overview

Allocation strategies in this implementation package at lib/alloc/fixed work over a buffer the caller provides or over an allocator upstream. A reader chooses among the six strategies by what each one allocates from and what that choice costs to reclaim. Tracked keeps the bump frontier offset and records that a raw allocation ran out of room, while used reports the current bump frontier offset.

Tracked frontier accounting

The struct Tracked keeps its numbers over a byte slice the caller provides.

1test "tutorial: tracked frontier accounting and reset" {2    const std = @import("std");3    const alloc_fixed = @import("alloc_fixed");45    var storage: [64]u8 align(16) = undefined;6    var tracked = alloc_fixed.Tracked.init(&storage);7    const allocator = tracked.allocator();89    // 1. Initial allocation advances the current frontier10    const first = try allocator.alloc(u8, 24);11    var status = tracked.status();12    try std.testing.expectEqual(@as(usize, 24), status.used_bytes);13    try std.testing.expectEqual(@as(usize, 24), status.peak_bytes);14    try std.testing.expectEqual(@as(usize, 24), status.high_water_bytes);15    try std.testing.expect(!status.exhausted);1617    // 2. Second allocation advances the frontier further18    const second = try allocator.alloc(u8, 24);19    status = tracked.status();20    try std.testing.expectEqual(@as(usize, 48), status.used_bytes);21    try std.testing.expectEqual(@as(usize, 48), status.peak_bytes);2223    // 3. Freeing the last allocation at the frontier reduces used_bytes24    allocator.free(second);25    status = tracked.status();26    try std.testing.expectEqual(@as(usize, 24), status.used_bytes);27    try std.testing.expectEqual(@as(usize, 48), status.peak_bytes);2829    // 4. Raw allocation failure sets the sticky exhausted flag30    try std.testing.expectError(error.OutOfMemory, allocator.alloc(u8, 48));31    status = tracked.status();32    try std.testing.expect(status.exhausted);3334    allocator.free(first);3536    // 5. Reset rewinds the frontier and clears peak and exhausted37    tracked.reset();38    status = tracked.status();39    try std.testing.expectEqual(@as(usize, 0), status.used_bytes);40    try std.testing.expectEqual(@as(usize, 0), status.peak_bytes);41    try std.testing.expectEqual(@as(usize, 48), status.high_water_bytes);42    try std.testing.expect(!status.exhausted);43}

Callers wrap Tracked to hold a phase to its limit and read the sticky record that a raw allocation came back empty for want of room through status().exhausted, the exhausted flag.

Allocation capabilities and owner stability

In the Zig standard library a std.mem.Allocator is a pointer to the struct that holds the storage and the bookkeeping behind an allocator handle, the owner, paired with a pointer to a table of allocation functions, forming the allocator handle:

• ptr: *anyopaque is the type-erased pointer to the owner that holds the state
• vtable: *const VTable points at the table of allocation functions

The allocator() method borrows that handle from one of six owners: Tracked, Chunks, Recycling, Monotonic, Fallback, or FixedBuffer.

The duty of the caller to keep the owner alive and at one address for as long as a handle points at it is owner stability. Copying the owner leaves handles that already exist pointing at the original address, so working with copies as independent allocators over the same storage drives their state apart. Reaching a handle after the owner moves or goes away is undefined behavior.

Physical capacity, bump frontier, and alignment

Four concepts govern the fixed-buffer and chunked strategies:

1. The whole byte slice an owner has to cut allocations from, which the caller provides or that comes from an upstream allocator, is the physical capacity.
2. The byte offset reached so far inside a buffer, which every allocation advances, is the bump frontier (used). In FixedBuffer and Tracked it moves back when the newest allocation is freed or made smaller, but it stays where it is when an allocation is freed while later ones are still live.
3. The bytes skipped to bring a pointer to the alignment a request asks for are the alignment padding. Padding carries the frontier past the requested length. Rewinding the frontier to zero with a reset makes that space available again, while freeing the most recent allocation first, a LIFO free, on its own leaves the alignment gaps behind.
4. When memory comes back and how is the reclamation policy. In the bump and chunk strategies, freeing one allocation returns no interior hole, so memory comes back in bulk, through reset, discard, or the teardown of the arena behind the owner.

Backing allocators and chunk retention

Several strategies take memory from an upstream allocator supplied by the caller, the backing allocator (backing: Allocator). A buffer obtained from the backing allocator to serve multiple allocations is a chunk. Chunks, Recycling, and Monotonic request chunks from this backing allocator. By contrast, Fallback first uses its caller-supplied byte slice and passes spill requests directly upstream.

To track chunks, Chunks and Recycling each maintain at most 64 chunk descriptors, where each descriptor records chunk storage and bookkeeping: the buffer, its alignment, its active flag, and a count of live allocations maintained only by Recycling. This fixed table bounds the number of simultaneously tracked chunks rather than the total count of allocation requests. That 64-descriptor bound applies only to Chunks and Recycling: Monotonic retains only its current chunk descriptor, while Fallback passes spill requests directly upstream.

In Recycling, inactive chunk descriptors are kept for reuse and still occupy slots in the table. In Chunks, calling retain() clears descriptor tracking without freeing backing memory, so those committed chunks no longer occupy its descriptor table.

The next fresh chunk has @max(scheduled_capacity, len) bytes, taking the larger of a planned size or the requested length. This planned capacity starts at initial_capacity, doubles after each successful fresh chunk, and stops growing at maximum_capacity, forming the growth schedule. Reused chunks do not advance the schedule. Oversized requests are allowed and do not change the doubling calculation to use their actual size. Thus maximum_capacity caps the schedule, not individual requests or total storage.

• Clearing the descriptor table without freeing the backing memory through retain() commits the chunks to the lifetime of the upstream owner
• lib/chic/src/language/value/own.zig uses that pattern to commit values it cloned into an outer arena
• Freeing every tracked chunk in reverse order back to the backing allocator and putting the growth schedule back where it started rolls the chunks back through discard()
• In Recycling, the number of allocations still outstanding in one chunk is tracked for each chunk as the live allocation count
• When frees bring the live count of the most recently activated chunk that every allocation tries first, the tail chunk, to zero, that chunk is deactivated by closing it and rewinding it, ready for the next allocation
• In Recycling, rawRemap returns null when it cannot grow the memory where it sits, and a caller going through std.mem.Allocator.realloc then gets the allocate, copy, and free path across chunks
• rawResize in Chunks, in Recycling, and in Monotonic answers true as soon as new_len <= memory.len, before it consults any chunk
• Shrinking therefore leaves the bump frontier where it was in those three, even for the most recent allocation
• Growing in place checks whether the memory belongs to the chunk currently open for allocation, the active chunk

Strategy overview

• FixedBuffer: the caller's slice, reclaimed by LIFO free or reset()
• Tracked: the caller's slice, with the frontier, the peak, the high-water mark, and the exhausted flag
• Chunks: a backing allocator, a doubling schedule, retain() to commit, and discard() to roll back
• Recycling: a backing allocator, tail chunk reuse, and the 64-descriptor limit
• Monotonic: a backing allocator, fixed chunks, the oversized bypass, and reclamation by arena teardown
• Fallback: the caller's slice with spillover to a backing allocator, and operations routed by provenance

Primary literature and historical context

• David R. Hanson (1990): Fast Allocation and Deallocation of Memory Based on Object Lifetimes, Software: Practice and Experience 20(1), pages 5–12, DOI: 10.1002/spe.4380200104. Author Scan.

Hanson grouped allocations by intended lifetime, allocated sequentially from a linked list of buffers, and deallocated each lifetime group together by resetting state to make backing buffers available for reuse instead of returning every block to the operating system. Chunks similarly groups allocations for a shared lifetime: retain() forgets tracked descriptors without freeing chunks and leaves committed storage to the upstream lifetime owner, while discard() issues backing frees for uncommitted chunks in reverse order. Actual physical reuse of the freed memory depends on the free policy of the backing allocator.

• Mads Tofte and Jean-Pierre Talpin (POPL 1994): Implementation of the Typed Call-by-Value lambda-Calculus using a Stack of Regions, pages 188–201, DOI: 10.1145/174675.177855. Paper.

Tofte and Talpin gave a proof that their translation, which annotates a program with regions, agrees with a store semantics built on regions, and their inference of regions and effects settles at compile time where memory is taken and given back. This package infers no region lifetimes and proves none: a caller manages memory through the borrowed handles instead.

• David Gay and Alex Aiken (PLDI 1998): Memory Management with Explicit Regions, pages 313–323, DOI: 10.1145/277650.277748. Author Site.

Gay and Aiken designed safe regions by counting external region references through tracked region pointers, where deleteregion does nothing while the relevant reference count is nonzero. This mechanism tracks region pointers, so deleteregion does not account for region pointers cast to ordinary pointers. Recycling differs in purpose: its counts track outstanding allocations inside each chunk solely to find empty tails to deactivate and reuse. It tracks no references held outside and provides no dangling-pointer protection.

Executable examples

Transactional chunks commit and rollback (Chunks)

The example rolls back after an injected failure from std.testing.FailingAllocator, retries, commits with retain(), and shows a request larger than maximum_capacity succeeding.

1test "tutorial: transactional chunks rollback on injected failure and commit" {2    const std = @import("std");3    const alloc_fixed = @import("alloc_fixed");45    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);6    defer arena.deinit();78    // 1. Transaction failure scenario with injected allocation failure9    {10        var failing = std.testing.FailingAllocator.init(11            arena.allocator(),12            .{ .fail_index = 1 }, // Second backing allocation fails13        );14        var transaction = alloc_fixed.Chunks.init(failing.allocator(), 64, 128);15        errdefer transaction.discard();1617        // First chunk allocation (64 bytes) succeeds18        _ = try transaction.allocator().alloc(u8, 48);19        try std.testing.expectEqual(@as(usize, 1), failing.allocations);20        try std.testing.expectEqual(@as(usize, 64), failing.allocated_bytes);2122        // Second allocation (96 bytes) requires a new chunk; backing alloc returns null23        const failed_alloc = transaction.allocator().alloc(u8, 96);24        try std.testing.expectError(error.OutOfMemory, failed_alloc);2526        // Rollback frees the first chunk back to the backing allocator27        transaction.discard();28        try std.testing.expectEqual(@as(usize, 64), failing.freed_bytes);29        try std.testing.expectEqual(failing.allocated_bytes, failing.freed_bytes);30    }3132    // 2. Transaction success scenario committing memory via retain()33    {34        var transaction = alloc_fixed.Chunks.init(arena.allocator(), 64, 128);35        const alloc = transaction.allocator();3637        const data1 = try alloc.alloc(u8, 48);38        const data2 = try alloc.alloc(u8, 96);39        // Requests exceeding maximum_capacity allocate max(scheduled, len)40        const oversized = try alloc.alloc(u8, 200);4142        @memset(data1, 0xAA);43        @memset(data2, 0xBB);44        @memset(oversized, 0xCC);4546        // Commit chunks to backing arena; transaction metadata is forgotten47        transaction.retain();4849        for (data1) |b| try std.testing.expectEqual(@as(u8, 0xAA), b);50        for (data2) |b| try std.testing.expectEqual(@as(u8, 0xBB), b);51        for (oversized) |b| try std.testing.expectEqual(@as(u8, 0xCC), b);52    }53}

Tail-chunk recycling and metadata exhaustion (Recycling)

The example follows the live allocation count, the tail chunk deactivating so its memory is reused, and the 64-descriptor limit being reached while the backing storage still has room.

1test "tutorial: recycling tail deactivation and metadata exhaustion" {2    const std = @import("std");3    const alloc_fixed = @import("alloc_fixed");45    var backing_bytes: [2048]u8 align(16) = undefined;6    var backing_tracked = alloc_fixed.Tracked.init(&backing_bytes);78    var recycling = alloc_fixed.Recycling.init(9        backing_tracked.allocator(),10        64,11        128,12    );13    defer recycling.discard();14    const allocator = recycling.allocator();1516    const chunk1_slice = try allocator.alloc(u8, 48);17    const chunk2_slice = try allocator.alloc(u8, 80);18    try std.testing.expect(backing_tracked.status().used_bytes >= 144);1920    allocator.free(chunk2_slice);21    allocator.free(chunk1_slice);2223    const high_water_before = backing_tracked.status().high_water_bytes;24    const reused_slice = try allocator.alloc(u8, 48);25    defer allocator.free(reused_slice);26    try std.testing.expectEqual(high_water_before, backing_tracked.status().high_water_bytes);2728    var slot_tester = alloc_fixed.Recycling.init(29        backing_tracked.allocator(),30        16,31        16,32    );33    defer slot_tester.discard();3435    for (0..alloc_fixed.Recycling.maximum_chunk_count) |_| {36        _ = try slot_tester.allocator().alloc(u8, 16);37    }3839    try std.testing.expectError(error.OutOfMemory, slot_tester.allocator().alloc(u8, 16));40    try std.testing.expect(slot_tester.metadataExhausted());41    try std.testing.expect(!backing_tracked.status().exhausted);42}

Fixed buffer with backing spillover (Fallback)

The example serves the first allocations from the fixed buffer, spills the next to the caller's backing allocator, and checks which tier owns each slice along with the count of backing allocations.

1test "tutorial: fallback buffer with backing spillover" {2    const std = @import("std");3    const alloc_fixed = @import("alloc_fixed");45    var storage: [64]u8 align(16) = undefined;6    var counting = std.testing.FailingAllocator.init(std.testing.allocator, .{});7    var fallback = alloc_fixed.Fallback.init(&storage, counting.allocator());8    const allocator = fallback.allocator();9    const fixed_buf = try allocator.alloc(u8, 48);10    defer allocator.free(fixed_buf);11    @memset(fixed_buf, 0x11);12    try std.testing.expect(fallback.fixed.ownsSlice(fixed_buf));13    try std.testing.expectEqual(@as(usize, 0), counting.alloc_index);14    const backing_buf = try allocator.alloc(u8, 32);15    defer allocator.free(backing_buf);16    @memset(backing_buf, 0x22);17    try std.testing.expect(!fallback.fixed.ownsSlice(backing_buf));18    try std.testing.expectEqual(@as(usize, 1), counting.alloc_index);19}

Stream allocation with oversized bypass (Monotonic)

The example fills fixed-capacity chunks while an oversized allocation goes straight to the backing allocator, leaving the active tail chunk in place.

1test "tutorial: monotonic stream allocation and preserved tail" {2    const std = @import("std");3    const alloc_fixed = @import("alloc_fixed");4    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);5    defer arena.deinit();6    var mono = alloc_fixed.Monotonic.init(arena.allocator(), 64);7    const allocator = mono.allocator();8    const first = try allocator.alloc(u8, 20);9    const second = try allocator.alloc(u8, 20);10    const oversized = try allocator.alloc(u8, 128);11    const tail = try allocator.alloc(u8, 16);12    @memset(first, 0x01);13    @memset(second, 0x02);14    @memset(oversized, 0x03);15    @memset(tail, 0x04);16    try std.testing.expectEqual(@intFromPtr(second.ptr) + second.len, @intFromPtr(tail.ptr));17    try std.testing.expect(@intFromPtr(oversized.ptr) != @intFromPtr(second.ptr) + second.len);18    try std.testing.expect(mono.isBackedBy(arena.allocator()));19}

Definitions

Actions

Public operations.

• used: used reports in bytes how far the bump frontier of a FixedBuffer has moved.

Types and contracts

Public types and contracts.

• Chunks: Chunks builds a result across several allocations, committing backing chunks to an outer owner through retain() or invoking upstream frees for rollback through discard().
• Fallback: When small work can run on the stack while larger requests spill to the heap, Fallback tries a fixed storage buffer first and falls back to a backing allocator.
• FixedBuffer: FixedBuffer is a fixed-capacity bump allocator that cuts allocations from a caller-owned byte slice with no allocator behind it.
• Monotonic: To stream allocations inside an arena that will free everything at once, Monotonic refills fixed-capacity chunks from a backing allocator.
• Recycling: Recycling reuses memory chunks across repeated workloads by tracking outstanding allocations across up to 64 chunk descriptors, including inactive chunks kept for reuse.
• Tracked: Tracked provides fixed-capacity bump allocation over a caller-supplied slice while measuring exact memory consumption.

Code relationships

Direct static dependencies extracted from parsed source by semantic graph analysis.

Uses: tiny.bumpalo
Used by: tiny.accy, tiny.choir

Verification

No verification records are cataloged for this module in this build.

Audit