c_allocator_impl

const c_allocator_impl = struct {
    comptime {
        if (!builtin.link_libc) {
            @compileError("C allocator is only available when linking against libc");
        }
    }

    const vtable: Allocator.VTable = .{
        .alloc = alloc,
        .resize = resize,
        .remap = remap,
        .free = free,
    };

    const have_posix_memalign = switch (builtin.os.tag) {
        .dragonfly,
        .netbsd,
        .freebsd,
        .illumos,
        .openbsd,
        .linux,
        .driverkit,
        .ios,
        .maccatalyst,
        .macos,
        .tvos,
        .visionos,
        .watchos,
        .serenity,
        => true,
        else => false,
    };

    fn allocStrat(need_align: Alignment) union(enum) {
        raw,
        posix_memalign: if (have_posix_memalign) void else noreturn,
        manual_align: if (have_posix_memalign) noreturn else void,
    } {
        // If `malloc` guarantees `need_align`, always prefer a raw allocation.
        if (Alignment.compare(need_align, .lte, .of(c.max_align_t))) {
            return .raw;
        }
        // Use `posix_memalign` if available. Otherwise, we must manually align the allocation.
        return if (have_posix_memalign) .posix_memalign else .manual_align;
    }

    /// If `allocStrat(a) == .manual_align`, an allocation looks like this:
    ///
    /// unaligned_ptr   hdr_ptr  aligned_ptr
    /// v               v        v
    /// +---------------+--------+--------------+
    /// |    padding    | header | usable bytes |
    /// +---------------+--------+--------------+
    ///
    /// * `unaligned_ptr` is the raw return value of `malloc`.
    /// * `aligned_ptr` is computed by aligning `unaligned_ptr` forward; it is what `alloc` returns.
    /// * `hdr_ptr` points to a pointer-sized header directly before the usable space. This header
    ///   contains the value `unaligned_ptr`, so that we can pass it to `free` later. This is
    ///   necessary because the width of the padding is unknown.
    ///
    /// This function accepts `aligned_ptr` and offsets it backwards to return `hdr_ptr`.
    fn manualAlignHeader(aligned_ptr: [*]u8) *[*]u8 {
        return @ptrCast(@alignCast(aligned_ptr - @sizeOf(usize)));
    }

    fn alloc(
        _: *anyopaque,
        len: usize,
        alignment: Alignment,
        return_address: usize,
    ) ?[*]u8 {
        _ = return_address;
        assert(len > 0);
        switch (allocStrat(alignment)) {
            .raw => {
                // `std.c.max_align_t` isn't the whole story, because if `len` is smaller than
                // every C type with alignment `max_align_t`, the allocation can be less-aligned.
                // The implementation need only guarantee that any type of length `len` would be
                // suitably aligned.
                //
                // For instance, if `len == 8` and `alignment == .@"16"`, then `malloc` may not
                // fulfil this request, because there is necessarily no C type with 8-byte size
                // but 16-byte alignment.
                //
                // In theory, the resulting rule here would be target-specific, but in practice,
                // the smallest type with an alignment of `max_align_t` has the same size (it's
                // usually `c_longdouble`), so we can just extend the allocation size up to the
                // alignment of `max_align_t` if necessary.
                const actual_len = @max(len, @alignOf(std.c.max_align_t));
                const ptr = c.malloc(actual_len) orelse return null;
                assert(alignment.check(@intFromPtr(ptr)));
                return @ptrCast(ptr);
            },
            .posix_memalign => {
                // The posix_memalign only accepts alignment values that are a
                // multiple of the pointer size
                const effective_alignment = @max(alignment.toByteUnits(), @sizeOf(usize));
                var aligned_ptr: ?*anyopaque = undefined;
                if (c.posix_memalign(&aligned_ptr, effective_alignment, len) != 0) {
                    return null;
                }
                assert(alignment.check(@intFromPtr(aligned_ptr)));
                return @ptrCast(aligned_ptr);
            },
            .manual_align => {
                // Overallocate to account for alignment padding and store the original pointer
                // returned by `malloc` before the aligned address.
                const padded_len = len + @sizeOf(usize) + alignment.toByteUnits() - 1;
                const unaligned_ptr: [*]u8 = @ptrCast(c.malloc(padded_len) orelse return null);
                const unaligned_addr = @intFromPtr(unaligned_ptr);
                const aligned_addr = alignment.forward(unaligned_addr + @sizeOf(usize));
                const aligned_ptr = unaligned_ptr + (aligned_addr - unaligned_addr);
                manualAlignHeader(aligned_ptr).* = unaligned_ptr;
                return aligned_ptr;
            },
        }
    }

    fn resize(
        _: *anyopaque,
        memory: []u8,
        alignment: Alignment,
        new_len: usize,
        return_address: usize,
    ) bool {
        _ = return_address;
        assert(new_len > 0);
        if (new_len <= memory.len) {
            return true; // in-place shrink always works
        }
        const mallocSize = func: {
            if (@TypeOf(c.malloc_size) != void) break :func c.malloc_size;
            if (@TypeOf(c.malloc_usable_size) != void) break :func c.malloc_usable_size;
            if (@TypeOf(c._msize) != void) break :func c._msize;
            return false; // we don't know how much space is actually available
        };
        const usable_len: usize = switch (allocStrat(alignment)) {
            .raw, .posix_memalign => mallocSize(memory.ptr),
            .manual_align => usable_len: {
                const unaligned_ptr = manualAlignHeader(memory.ptr).*;
                const full_len = mallocSize(unaligned_ptr);
                const padding = @intFromPtr(memory.ptr) - @intFromPtr(unaligned_ptr);
                break :usable_len full_len - padding;
            },
        };
        return new_len <= usable_len;
    }

    fn remap(
        ctx: *anyopaque,
        memory: []u8,
        alignment: Alignment,
        new_len: usize,
        return_address: usize,
    ) ?[*]u8 {
        assert(new_len > 0);
        // Prefer resizing in-place if possible, since `realloc` could be expensive even if legal.
        if (resize(ctx, memory, alignment, new_len, return_address)) {
            return memory.ptr;
        }
        switch (allocStrat(alignment)) {
            .raw => {
                // `malloc` and friends guarantee the required alignment, so we can try `realloc`.
                // C only needs to respect `max_align_t` up to the allocation size due to object
                // alignment rules. If necessary, extend the allocation size.
                const actual_len = @max(new_len, @alignOf(std.c.max_align_t));
                const new_ptr = c.realloc(memory.ptr, actual_len) orelse return null;
                assert(alignment.check(@intFromPtr(new_ptr)));
                return @ptrCast(new_ptr);
            },
            .posix_memalign, .manual_align => {
                // `realloc` would potentially return a new allocation which does not respect
                // the original alignment, so we can't do anything more.
                return null;
            },
        }
    }

    fn free(
        _: *anyopaque,
        memory: []u8,
        alignment: Alignment,
        return_address: usize,
    ) void {
        _ = return_address;
        switch (allocStrat(alignment)) {
            .raw, .posix_memalign => c.free(memory.ptr),
            .manual_align => c.free(manualAlignHeader(memory.ptr).*),
        }
    }
}