//! A size-class free-list allocator over the process allocator.
const std = @import("std");
/// The allocator a zit process runs on. Over `std.heap.smp_allocator` -- the
/// process allocator of a build without libc, such as the static Linux
/// release -- it keeps a free list of its own per power-of-two size class
/// and gives blocks back only at `deinit`.
///
/// The SMP allocator keeps its free lists per CPU slot and moves a thread to
/// the next slot whenever one size class runs dry in the current one. A
/// single-threaded import does exactly that, constantly, so the blocks one
/// commit frees land in one slot while the next commit allocates fresh
/// slabs in another. On a four-core host that left a long import holding
/// several times its live memory resident, growing with the history. Here a
/// freed block is reused for the next request of its class wherever it was
/// freed, so resident memory follows each class's peak. A full derive's walk
/// churns the same way, and an import's warm-up reuses what the import freed
/// instead of growing past it.
///
/// Blocks are requested from the backing allocator at exactly their class
/// size and alignment, which is how the SMP allocator sizes them anyway, so
/// nothing is lost to the extra layer, and a block that escapes the heap
/// can still be freed straight to the backing allocator. Requests past the
/// SMP allocator's largest class are whole mappings there and pass through.
/// Over any other allocator the layer is a pass-through.
pub const ClassHeap = struct {
backing: std.mem.Allocator,
mutex: std.atomic.Mutex = .unlocked,
free_lists: [class_count]?*FreeBlock = @splat(null),
const FreeBlock = struct { next: ?*FreeBlock };
const min_shift = std.math.log2_int(usize, @sizeOf(FreeBlock));
/// The SMP allocator's largest small class: 32 KiB.
pub const max_shift = 15;
pub const class_count = max_shift - min_shift + 1;
pub fn allocator(self: *ClassHeap) std.mem.Allocator {
if (self.backing.vtable != std.heap.smp_allocator.vtable) return self.backing;
return self.caching();
}
pub fn caching(self: *ClassHeap) std.mem.Allocator {
return .{ .ptr = self, .vtable = &.{ .alloc = alloc, .resize = resize, .remap = remap, .free = free } };
}
pub fn deinit(self: *ClassHeap) void {
for (&self.free_lists, min_shift..) |*list, shift| {
while (list.*) |block| {
list.* = block.next;
const bytes: [*]u8 = @ptrCast(block);
self.backing.rawFree(bytes[0 .. @as(usize, 1) << @intCast(shift)], .fromByteUnits(@as(usize, 1) << @intCast(shift)), @returnAddress());
}
}
self.* = undefined;
}
/// The class `len` bytes at `alignment` fall in, or null past the largest.
fn shiftOf(len: usize, alignment: std.mem.Alignment) ?usize {
const shift = @max(std.math.log2_int_ceil(usize, @max(len, 1)), @as(usize, @backingInt(alignment)), min_shift);
return if (shift > max_shift) null else shift;
}
fn lock(self: *ClassHeap) void {
while (!self.mutex.tryLock()) std.atomic.spinLoopHint();
}
fn alloc(context: *anyopaque, len: usize, alignment: std.mem.Alignment, ra: usize) ?[*]u8 {
const self: *ClassHeap = @ptrCast(@alignCast(context));
const shift = shiftOf(len, alignment) orelse return self.backing.rawAlloc(len, alignment, ra);
self.lock();
defer self.mutex.unlock();
const list = &self.free_lists[shift - min_shift];
if (list.*) |block| {
list.* = block.next;
return @ptrCast(block);
}
return self.backing.rawAlloc(@as(usize, 1) << @intCast(shift), .fromByteUnits(@as(usize, 1) << @intCast(shift)), ra);
}
fn resize(context: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ra: usize) bool {
const self: *ClassHeap = @ptrCast(@alignCast(context));
const old_shift = shiftOf(memory.len, alignment);
const new_shift = shiftOf(new_len, alignment);
if (old_shift == null and new_shift == null) return self.backing.rawResize(memory, alignment, new_len, ra);
return old_shift != null and old_shift == new_shift;
}
fn remap(context: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ra: usize) ?[*]u8 {
const self: *ClassHeap = @ptrCast(@alignCast(context));
const old_shift = shiftOf(memory.len, alignment);
const new_shift = shiftOf(new_len, alignment);
if (old_shift == null and new_shift == null) return self.backing.rawRemap(memory, alignment, new_len, ra);
return if (old_shift != null and old_shift == new_shift) memory.ptr else null;
}
fn free(context: *anyopaque, memory: []u8, alignment: std.mem.Alignment, ra: usize) void {
const self: *ClassHeap = @ptrCast(@alignCast(context));
const shift = shiftOf(memory.len, alignment) orelse return self.backing.rawFree(memory, alignment, ra);
self.lock();
defer self.mutex.unlock();
const block: *FreeBlock = @ptrCast(@alignCast(memory.ptr));
const list = &self.free_lists[shift - min_shift];
block.next = list.*;
list.* = block;
}
};