tiny.bumpalo.BumpAllocator

1pub fn BumpAllocator(comptime min_alignment: usize) type {2    comptime {3        if (!std.math.isPowerOfTwo(min_alignment)) {4            @compileError("min_alignment must be a power of two");5        }6        if (min_alignment > chunk_alignment) {7            @compileError("min_alignment may not be larger than chunk_alignment");8        }9    }1011    return struct {12        const chunk_header_alignment = @max(chunk_alignment, @alignOf(Chunk));13        const minimum_alignment = min_alignment;14        const metadata_size = std.mem.alignForward(usize, @sizeOf(Chunk), chunk_alignment);15        const overhead = std.mem.alignForward(usize, malloc_overhead + metadata_size, chunk_alignment);16        pub const default_chunk_capacity = first_allocation_goal - overhead;1718        backing_allocator: Allocator,19        current: ?*Chunk = null,20        backing_data_capacity_limit: ?usize = null,21        chunk_growth_goal_bytes: ?usize = null,22        caller_root: CallerRootState = .none,23        observation_id: if (observe.enabled) u64 else void,24        observation_generation: if (observe.enabled) u64 else void =25            if (observe.enabled) 0 else {},2627        const Self = @This();28        pub const ChunkIterator: type = chunk_mod.Iterator;29        pub const ResetMode: type = ResetPolicy;3031        pub fn init(backing_allocator: Allocator) Self {32            return .{33                .backing_allocator = backing_allocator,34                .observation_id = if (comptime observe.enabled)35                    observe.producerId()36                else {},37            };38        }3940        pub inline fn observationId(arena: *const Self) u64 {41            if (comptime !observe.enabled) return 0;42            return arena.observation_id;43        }4445        pub inline fn observationIdentity(46            arena: *const Self,47        ) observe.Identity {48            if (comptime !observe.enabled) {49                return .{50                    .producer_id = 0,51                    .producer = .bump,52                    .generation = 0,53                    .owner_cookie = 0,54                };55            }56            return observe.Identity.movable(57                arena.observation_id,58                .bump,59                arena.observation_generation,60            );61        }6263        pub fn initCapacity(backing_allocator: Allocator, capacity: usize) Allocator.Error!Self {64            var arena = Self.init(backing_allocator);65            if (capacity != 0) {66                arena.current = try arena.newChunk(capacity, capacity, .@"1", null, null);67                assert(arena.queryCapacity() >= capacity);68            }69            return arena;70        }7172        pub fn deinit(arena: *Self) void {73            var span = observe.beginLifecycle(74                arena.observationIdentity(),75                .end,76                .deinit,77                @returnAddress(),78            );79            arena.assertCallerRootInvariant();80            chunk_mod.destroyList(arena.backing_allocator, arena.current);81            arena.current = null;82            arena.caller_root = .none;83            span.finish(.{ .succeeded = true });84        }8586        pub fn allocator(arena: *Self) Allocator {87            const Table = allocator_vtable.VTable(Self);88            return .{89                .ptr = arena,90                .vtable = &Table.vtable,91            };92        }9394        pub fn minAlign(_: *const Self) usize {95            return min_alignment;96        }9798        pub fn backingDataCapacityLimit(arena: *const Self) ?usize {99            return arena.backing_data_capacity_limit;100        }101102        pub fn setBackingDataCapacityLimit(arena: *Self, limit: ?usize) void {103            arena.backing_data_capacity_limit = limit;104        }105106        pub fn chunkGrowthGoal(arena: *const Self) ?usize {107            return arena.chunk_growth_goal_bytes;108        }109110        pub fn setChunkGrowthGoal(arena: *Self, goal: ?usize) void {111            if (goal) |bytes| assert(bytes >= default_chunk_capacity);112            arena.chunk_growth_goal_bytes = goal;113        }114115        pub fn reset(arena: *Self, mode: ResetMode) bool {116            var span = observe.beginLifecycle(117                arena.observationIdentity(),118                .invalidate,119                .reset,120                @returnAddress(),121            );122            const succeeded = switch (mode) {123                .free_all => blk: {124                    arena.freeAllChunks();125                    break :blk true;126                },127                .retain_current => blk: {128                    arena.retainCurrentChunk();129                    break :blk true;130                },131                .retain_capacity => arena.retainSingleChunk(132                    arena.queryCapacity(),133                    null,134                ),135                .retain_with_limit => |limit| arena.retainSingleChunk(136                    @min(arena.queryCapacity(), limit),137                    limit,138                ),139            };140            span.finish(.{ .succeeded = succeeded });141            arena.advanceObservationGeneration();142            return succeeded;143        }144145        pub fn queryCapacity(arena: *const Self) usize {146            const current = arena.current orelse return 0;147            return current.total_capacity;148        }149150        pub fn queryCallerDataCapacity(arena: *const Self) usize {151            return switch (arena.caller_root) {152                .linked => |root| root.capacity,153                .none, .detached => 0,154            };155        }156157        pub fn queryBackingDataCapacity(arena: *const Self) usize {158            const capacity = arena.queryCapacity();159            const caller_capacity = arena.queryCallerDataCapacity();160            assert(caller_capacity <= capacity);161            return capacity - caller_capacity;162        }163164        pub fn queryUsedCapacity(arena: *const Self) usize {165            var used: usize = 0;166            var chunk = arena.current;167            while (chunk) |c| : (chunk = c.previous) {168                used += c.usedSlice().len;169            }170            return used;171        }172173        pub fn queryCurrentChunkAvailable(arena: *const Self) usize {174            const current = arena.current orelse return 0;175            return current.remaining();176        }177178        pub fn queryCapacityIncludingMetadata(arena: *const Self) usize {179            var bytes: usize = 0;180            var chunk = arena.current;181            while (chunk) |c| : (chunk = c.previous) {182                bytes += chunk_mod.allocationFootprint(c);183            }184            return bytes;185        }186187        pub fn clearAndFree(arena: *Self) void {188            var span = observe.beginLifecycle(189                arena.observationIdentity(),190                .invalidate,191                .clear_and_free,192                @returnAddress(),193            );194            arena.freeAllChunks();195            span.finish(.{ .succeeded = true });196            arena.advanceObservationGeneration();197        }198199        pub fn clearRetainingCurrent(arena: *Self) void {200            var span = observe.beginLifecycle(201                arena.observationIdentity(),202                .invalidate,203                .clear_retaining_current,204                @returnAddress(),205            );206            arena.retainCurrentChunk();207            span.finish(.{ .succeeded = true });208            arena.advanceObservationGeneration();209        }210211        pub fn clearRetainingLargest(arena: *Self) void {212            var span = observe.beginLifecycle(213                arena.observationIdentity(),214                .invalidate,215                .clear_retaining_largest,216                @returnAddress(),217            );218            arena.retainLargestChunk();219            span.finish(.{ .succeeded = true });220            arena.advanceObservationGeneration();221        }222223        pub fn clearRetainingCapacity(arena: *Self) bool {224            var span = observe.beginLifecycle(225                arena.observationIdentity(),226                .invalidate,227                .clear_retaining_capacity,228                @returnAddress(),229            );230            const succeeded = arena.retainSingleChunk(231                arena.queryCapacity(),232                null,233            );234            span.finish(.{ .succeeded = succeeded });235            arena.advanceObservationGeneration();236            return succeeded;237        }238239        pub fn clearRetainingCapacityLimit(arena: *Self, limit: usize) bool {240            var span = observe.beginLifecycle(241                arena.observationIdentity(),242                .invalidate,243                .clear_retaining_capacity_limit,244                @returnAddress(),245            );246            const succeeded = arena.retainSingleChunk(247                @min(arena.queryCapacity(), limit),248                limit,249            );250            span.finish(.{ .succeeded = succeeded });251            arena.advanceObservationGeneration();252            return succeeded;253        }254255        fn advanceObservationGeneration(arena: *Self) void {256            if (comptime !observe.enabled) return;257            arena.observation_generation = std.math.add(258                u64,259                arena.observation_generation,260                1,261            ) catch @panic("allocator observation generation exhausted");262        }263264        fn freeAllChunks(arena: *Self) void {265            arena.assertCallerRootInvariant();266            chunk_mod.destroyList(arena.backing_allocator, arena.current);267            arena.current = null;268            arena.restoreCallerRoot();269            arena.assertCallerRootInvariant();270        }271272        fn retainCurrentChunk(arena: *Self) void {273            arena.assertCallerRootInvariant();274            const current = arena.current orelse return;275            chunk_mod.destroyList(arena.backing_allocator, current.previous);276            current.previous = null;277            current.setCursor(current.dataEnd());278            current.total_capacity = current.capacity;279            switch (arena.caller_root) {280                .linked => |root| {281                    if (current != root) arena.caller_root = .{ .detached = root };282                },283                .none, .detached => {},284            }285            assert(current.remaining() == current.capacity);286            assert(arena.queryCapacity() == arena.queryCurrentChunkAvailable());287            arena.assertCallerRootInvariant();288        }289290        fn retainLargestChunk(arena: *Self) void {291            switch (arena.caller_root) {292                .none => {},293                .linked, .detached => {294                    arena.freeAllChunks();295                    return;296                },297            }298            const current = arena.current orelse return;299            var retained = current;300            var candidate = current.previous;301            while (candidate) |chunk| : (candidate = chunk.previous) {302                if (chunk.capacity > retained.capacity) retained = chunk;303            }304            chunk_mod.destroyUntil(arena.backing_allocator, current, retained);305            chunk_mod.destroyList(arena.backing_allocator, retained.previous);306            retained.previous = null;307            retained.setCursor(retained.dataEnd());308            retained.total_capacity = retained.capacity;309            arena.current = retained;310            assert(retained.remaining() == retained.capacity);311            assert(arena.queryCapacity() == arena.queryCurrentChunkAvailable());312        }313314        fn retainSingleChunk(arena: *Self, requested_capacity: usize, max_capacity: ?usize) bool {315            arena.assertCallerRootInvariant();316            const bounded_capacity = if (max_capacity) |limit|317                @min(requested_capacity, limit)318            else319                requested_capacity;320            if (bounded_capacity == 0) {321                arena.clearLiveAndDetachCallerRoot();322                arena.assertCallerRootInvariant();323                return true;324            }325            if (max_capacity) |limit| {326                const aligned_limit = std.mem.alignBackward(327                    usize,328                    limit,329                    @max(chunk_header_alignment, min_alignment),330                );331                if (aligned_limit == 0) {332                    arena.clearLiveAndDetachCallerRoot();333                    arena.assertCallerRootInvariant();334                    return true;335                }336            }337338            assert(bounded_capacity > 0);339            if (arena.current) |current| {340                if (current.previous == null and current.capacity >= bounded_capacity) {341                    if (max_capacity == null or current.capacity <= max_capacity.?) {342                        current.setCursor(current.dataEnd());343                        current.total_capacity = current.capacity;344                        assert(current.remaining() == current.capacity);345                        arena.assertCallerRootInvariant();346                        return true;347                    }348                }349            }350351            arena.clearLiveAndDetachCallerRoot();352            const backing_capacity_remaining =353                arena.backingDataCapacityRemaining();354            if (backing_capacity_remaining) |remaining| {355                const aligned_remaining = std.mem.alignBackward(356                    usize,357                    remaining,358                    @max(chunk_header_alignment, min_alignment),359                );360                if (max_capacity != null and aligned_remaining == 0) {361                    arena.assertCallerRootInvariant();362                    return true;363                }364            }365            arena.current = arena.newChunkBounded(366                bounded_capacity,367                if (max_capacity == null) bounded_capacity else 0,368                .@"1",369                null,370                max_capacity,371                backing_capacity_remaining,372            ) catch {373                arena.restoreCallerRoot();374                arena.assertCallerRootInvariant();375                return false;376            };377            arena.assertCallerRootInvariant();378            return true;379        }380381        fn clearLiveAndDetachCallerRoot(arena: *Self) void {382            chunk_mod.destroyList(arena.backing_allocator, arena.current);383            arena.current = null;384            switch (arena.caller_root) {385                .linked => |root| arena.caller_root = .{ .detached = root },386                .none, .detached => {},387            }388        }389390        fn restoreCallerRoot(arena: *Self) void {391            switch (arena.caller_root) {392                .none => {},393                .linked, .detached => |root| {394                    root.previous = null;395                    root.setCursor(root.dataEnd());396                    root.total_capacity = root.capacity;397                    arena.current = root;398                    arena.caller_root = .{ .linked = root };399                },400            }401        }402403        fn assertCallerRootInvariant(arena: *const Self) void {404            switch (arena.caller_root) {405                .none => {},406                .linked => |root| {407                    assert(root.previous == null);408                    assert(arena.chunkReachable(root));409                },410                .detached => |root| {411                    assert(root.previous == null);412                    assert(!arena.chunkReachable(root));413                },414            }415        }416417        fn chunkReachable(arena: *const Self, target: *Chunk) bool {418            var chunk = arena.current;419            while (chunk) |current| : (chunk = current.previous) {420                if (current == target) return true;421            }422            return false;423        }424425        pub fn iterAllocatedChunks(arena: *Self) ChunkIterator {426            return .{ .next_chunk = arena.current };427        }428429        pub inline fn allocValue(arena: *Self, value: anytype) Allocator.Error!*@TypeOf(value) {430            const T = @TypeOf(value);431            const ptr = try arena.create(T);432            ptr.* = value;433            return ptr;434        }435436        pub inline fn create(arena: *Self, comptime T: type) Allocator.Error!*T {437            if (@sizeOf(T) == 0) {438                const address = comptime Alignment.of(T).backward(std.math.maxInt(usize));439                return @ptrFromInt(address);440            }441            const raw = try arena.allocBytes(@sizeOf(T), .of(T));442            return @ptrCast(@alignCast(raw));443        }444445        pub inline fn alloc(arena: *Self, comptime T: type, len: usize) Allocator.Error![]T {446            if (@sizeOf(T) == 0) {447                const address = comptime Alignment.of(T).backward(std.math.maxInt(usize));448                const ptr: [*]T = @ptrFromInt(address);449                return ptr[0..len];450            }451            const byte_len = if (comptime @sizeOf(T) == 1)452                len453            else454                std.math.mul(usize, @sizeOf(T), len) catch return error.OutOfMemory;455            const raw = try arena.allocBytes(byte_len, .of(T));456            const ptr: [*]T = @ptrCast(@alignCast(raw));457            return ptr[0..len];458        }459460        pub inline fn dupe(arena: *Self, comptime T: type, source: []const T) Allocator.Error![]T {461            const dest = try arena.alloc(T, source.len);462            @memcpy(dest, source);463            return dest;464        }465466        pub inline fn dupeSentinel(467            arena: *Self,468            comptime T: type,469            source: []const T,470            comptime sentinel: T,471        ) Allocator.Error![:sentinel]T {472            const dest = try arena.alloc(T, source.len + 1);473            @memcpy(dest[0..source.len], source);474            dest[source.len] = sentinel;475            return dest[0..source.len :sentinel];476        }477478        pub inline fn dupeZ(arena: *Self, comptime T: type, source: []const T) Allocator.Error![:0]T {479            return arena.dupeSentinel(T, source, 0);480        }481482        pub inline fn allocFill(arena: *Self, comptime T: type, len: usize, value: T) Allocator.Error![]T {483            const dest = try arena.alloc(T, len);484            @memset(dest, value);485            return dest;486        }487488        pub inline fn allocBytes(arena: *Self, len: usize, alignment: Alignment) Allocator.Error![*]u8 {489            return arena.tryAllocBytes(len, alignment) orelse error.OutOfMemory;490        }491492        inline fn tryAllocBytes(arena: *Self, len: usize, alignment: Alignment) ?[*]u8 {493            if (len == 0) {494                const effective_align = @max(alignment.toByteUnits(), min_alignment);495                const address = Alignment.fromByteUnits(effective_align).backward(std.math.maxInt(usize));496                return @ptrFromInt(address);497            }498499            if (arena.tryAllocBytesFast(len, alignment)) |ptr| return ptr;500            return arena.allocBytesSlow(len, alignment);501        }502503        inline fn tryAllocBytesFast(arena: *Self, len: usize, alignment: Alignment) ?[*]u8 {504            const current = arena.current orelse {505                @branchHint(.unlikely);506                return null;507            };508            return allocFast(current, len, alignment, min_alignment);509        }510511        inline fn allocFast(current: *Chunk, len: usize, alignment: Alignment, comptime min_align: usize) ?[*]u8 {512            return chunk_mod.allocFast(current, len, alignment, min_align);513        }514515        fn allocBytesSlow(arena: *Self, len: usize, alignment: Alignment) ?[*]u8 {516            assert(len != 0);517            const remaining_limit = arena.backingDataCapacityRemaining();518            const previous = arena.current;519            const min_new_capacity = @max(len, default_chunk_capacity);520            var base_capacity = min_new_capacity;521            if (previous) |chunk| {522                const effective_align = @max(alignment.toByteUnits(), min_alignment);523                if (std.mem.isAligned(@intFromPtr(chunk.cursor()), effective_align)) {524                    base_capacity = @max(chunk.capacity *| 2, min_new_capacity);525                }526            }527            if (arena.chunk_growth_goal_bytes) |goal| {528                base_capacity = @min(base_capacity, @max(goal, min_new_capacity));529            }530531            if (remaining_limit) |remaining| {532                if (remaining < len) return null;533                if (base_capacity > remaining) base_capacity = remaining;534            }535536            if (base_capacity < len) return null;537            const new_chunk = arena.newChunk(538                base_capacity,539                len,540                alignment,541                previous,542                remaining_limit,543            ) catch return null;544            arena.current = new_chunk;545            const ptr = allocFast(new_chunk, len, alignment, min_alignment).?;546            assert(std.mem.isAligned(@intFromPtr(ptr), @max(alignment.toByteUnits(), min_alignment)));547            return ptr;548        }549550        fn backingDataCapacityRemaining(arena: *const Self) ?usize {551            const limit = arena.backing_data_capacity_limit orelse return null;552            const allocated = arena.queryBackingDataCapacity();553            if (allocated >= limit) return 0;554            return limit - allocated;555        }556557        fn newChunk(558            arena: *Self,559            requested_capacity: usize,560            requested_len: usize,561            requested_alignment: Alignment,562            previous: ?*Chunk,563            backing_data_capacity_remaining: ?usize,564        ) Allocator.Error!*Chunk {565            return arena.newChunkBounded(566                requested_capacity,567                requested_len,568                requested_alignment,569                previous,570                null,571                backing_data_capacity_remaining,572            );573        }574575        fn newChunkBounded(576            arena: *Self,577            requested_capacity: usize,578            requested_len: usize,579            requested_alignment: Alignment,580            previous: ?*Chunk,581            max_capacity: ?usize,582            backing_data_capacity_remaining: ?usize,583        ) Allocator.Error!*Chunk {584            assert(requested_len <= requested_capacity);585            return chunk_mod.create(arena.backing_allocator, .{586                .requested_capacity = requested_capacity,587                .requested_len = requested_len,588                .requested_alignment = requested_alignment,589                .previous = previous,590                .max_capacity = max_capacity,591                .min_alignment = min_alignment,592                .chunk_header_alignment = chunk_header_alignment,593                .overhead = overhead,594                .typical_page_size = typical_page_size,595                .backing_data_capacity_remaining = backing_data_capacity_remaining,596            });597        }598599        pub fn initBuffer(backing_allocator: Allocator, buffer: []u8) Allocator.Error!Self {600            var arena = Self.init(backing_allocator);601            if (buffer.len != 0) {602                const initial = try Self.newChunkInBuffer(buffer, null);603                arena.current = initial;604                arena.caller_root = .{ .linked = initial };605                arena.assertCallerRootInvariant();606            }607            return arena;608        }609610        fn newChunkInBuffer(buffer: []u8, previous: ?*Chunk) Allocator.Error!*Chunk {611            return chunk_mod.createInBuffer(buffer, .{612                .previous = previous,613                .min_alignment = min_alignment,614                .chunk_header_alignment = chunk_header_alignment,615            }) orelse error.OutOfMemory;616        }617    };618}

1pub const BumpAllocator = bump_impl.BumpAllocator;