feat: finish ghostty pane backend integration

1 files changed, 1021 insertions, 0 deletions

diff --git a/vendor/libghostty-vt/src/terminal/bitmap_allocator.zig b/vendor/libghostty-vt/src/terminal/bitmap_allocator.zig
new file mode 100644
index 00000000..deeecf55
--- /dev/null
+++ b/vendor/libghostty-vt/src/terminal/bitmap_allocator.zig
@@ -0,0 +1,1021 @@
+const std = @import("std");
+const assert = @import("../quirks.zig").inlineAssert;
+const Allocator = std.mem.Allocator;
+const size = @import("size.zig");
+const getOffset = size.getOffset;
+const Offset = size.Offset;
+const OffsetBuf = size.OffsetBuf;
+const alignForward = std.mem.alignForward;
+
+/// A relatively naive bitmap allocator that uses memory offsets against
+/// a fixed backing buffer so that the backing buffer can be easily moved
+/// without having to update pointers.
+///
+/// The chunk size determines the size of each chunk in bytes. This is the
+/// minimum distributed unit of memory. For example, if you request a
+/// 1-byte allocation, you'll use a chunk of chunk_size bytes. Likewise,
+/// if your chunk size is 4, and you request a 5-byte allocation, you'll
+/// use 2 chunks.
+///
+/// The allocator is susceptible to fragmentation. If you allocate and free
+/// memory in a way that leaves small holes in the memory, you may not be
+/// able to allocate large chunks of memory even if there is enough free
+/// memory in aggregate. To avoid fragmentation, use a chunk size that is
+/// large enough to cover most of your allocations.
+///
+// Notes for contributors: this is highly contributor friendly part of
+// the code. If you can improve this, add tests, show benchmarks, then
+// please do so!
+pub fn BitmapAllocator(comptime chunk_size: comptime_int) type {
+    return struct {
+        const Self = @This();
+
+        comptime {
+            assert(std.math.isPowerOfTwo(chunk_size));
+        }
+
+        pub const base_align: std.mem.Alignment = .fromByteUnits(@alignOf(u64));
+        pub const bitmap_bit_size = @bitSizeOf(u64);
+
+        /// The bitmap of available chunks. Each bit represents a chunk. A
+        /// 1 means the chunk is free and a 0 means it's used. We use 1
+        /// for free since it makes it very slightly faster to find free
+        /// chunks.
+        bitmap: Offset(u64),
+        bitmap_count: usize,
+
+        /// The contiguous buffer of chunks.
+        chunks: Offset(u8),
+
+        /// Initialize the allocator map with a given buf and memory layout.
+        pub fn init(buf: OffsetBuf, l: Layout) Self {
+            assert(base_align.check(@intFromPtr(buf.start())));
+
+            // Initialize our bitmaps to all 1s to note that all chunks are free.
+            const bitmap = buf.member(u64, l.bitmap_start);
+            const bitmap_ptr = bitmap.ptr(buf);
+            @memset(bitmap_ptr[0..l.bitmap_count], std.math.maxInt(u64));
+
+            return .{
+                .bitmap = bitmap,
+                .bitmap_count = l.bitmap_count,
+                .chunks = buf.member(u8, l.chunks_start),
+            };
+        }
+
+        /// Returns the number of bytes required to allocate n elements of
+        /// type T. This accounts for the chunk size alignment used by the
+        /// bitmap allocator.
+        pub fn bytesRequired(comptime T: type, n: usize) usize {
+            const byte_count = @sizeOf(T) * n;
+            return alignForward(usize, byte_count, chunk_size);
+        }
+
+        /// Allocate n elements of type T. This will return error.OutOfMemory
+        /// if there isn't enough space in the backing buffer.
+        ///
+        /// Use (size.zig).getOffset to get the base offset from the backing
+        /// memory for portable storage.
+        pub fn alloc(
+            self: *Self,
+            comptime T: type,
+            base: anytype,
+            n: usize,
+        ) Allocator.Error![]T {
+            // note: we don't handle alignment yet, we just require that all
+            // types are properly aligned. This is a limitation that should be
+            // fixed but we haven't needed it. Contributor friendly: add tests
+            // and fix this.
+            assert(chunk_size % @alignOf(T) == 0);
+            assert(n > 0);
+
+            const byte_count = std.math.mul(usize, @sizeOf(T), n) catch
+                return error.OutOfMemory;
+            const chunk_count = std.math.divCeil(usize, byte_count, chunk_size) catch
+                return error.OutOfMemory;
+
+            // Find the index of the free chunk. This also marks it as used.
+            const bitmaps = self.bitmap.ptr(base);
+            const idx = findFreeChunks(bitmaps[0..self.bitmap_count], chunk_count) orelse
+                return error.OutOfMemory;
+
+            const chunks = self.chunks.ptr(base);
+            const ptr: [*]T = @ptrCast(@alignCast(&chunks[idx * chunk_size]));
+            return ptr[0..n];
+        }
+
+        pub fn free(self: *Self, base: anytype, slice: anytype) void {
+            // Convert the slice of whatever type to a slice of bytes. We
+            // can then use the byte len and chunk size to determine the
+            // number of chunks that were allocated.
+            const bytes = std.mem.sliceAsBytes(slice);
+            const aligned_len = std.mem.alignForward(usize, bytes.len, chunk_size);
+            const chunk_count = @divExact(aligned_len, chunk_size);
+
+            // From the pointer, we can calculate the exact index.
+            const chunks = self.chunks.ptr(base);
+            const chunk_idx = @divExact(@intFromPtr(slice.ptr) - @intFromPtr(chunks), chunk_size);
+
+            const bitmaps = self.bitmap.ptr(base);
+
+            // Current bitmap index.
+            var i: usize = @divFloor(chunk_idx, 64);
+            // Number of chunks we still have to mark as free.
+            var rem: usize = chunk_count;
+
+            // Mark any bits in the starting bitmap that need to be marked.
+            {
+                // Bit index.
+                const bit = chunk_idx % 64;
+                // Number of bits we need to mark in this bitmap.
+                const bits = @min(rem, 64 - bit);
+
+                bitmaps[i] |= ~@as(u64, 0) >> @intCast(64 - bits) << @intCast(bit);
+                rem -= bits;
+            }
+
+            // Mark any full bitmaps worth of bits that need to be marked.
+            i += 1;
+            while (rem > 64) : (i += 1) {
+                bitmaps[i] = std.math.maxInt(u64);
+                rem -= 64;
+            }
+
+            // Mark any bits at the start of this last bitmap if it needs it.
+            if (rem > 0) {
+                bitmaps[i] |= ~@as(u64, 0) >> @intCast(64 - rem);
+            }
+        }
+
+        /// Returns the total capacity in bytes.
+        pub fn capacityBytes(self: Self) usize {
+            return self.bitmap_count * bitmap_bit_size * chunk_size;
+        }
+
+        /// Returns the number of bytes currently in use.
+        pub fn usedBytes(self: Self, base: anytype) usize {
+            const bitmaps = self.bitmap.ptr(base);
+            var free_chunks: usize = 0;
+            for (bitmaps[0..self.bitmap_count]) |bitmap| free_chunks += @popCount(bitmap);
+            const total_chunks = self.bitmap_count * bitmap_bit_size;
+            return (total_chunks - free_chunks) * chunk_size;
+        }
+
+        /// For testing only.
+        fn isAllocated(self: *Self, base: anytype, slice: anytype) bool {
+            comptime assert(@import("builtin").is_test);
+
+            const bytes = std.mem.sliceAsBytes(slice);
+            const aligned_len = std.mem.alignForward(usize, bytes.len, chunk_size);
+            const chunk_count = @divExact(aligned_len, chunk_size);
+
+            const chunks = self.chunks.ptr(base);
+            const chunk_idx = @divExact(@intFromPtr(slice.ptr) - @intFromPtr(chunks), chunk_size);
+
+            const bitmaps = self.bitmap.ptr(base);
+
+            for (chunk_idx..chunk_idx + chunk_count) |i| {
+                const bitmap = @divFloor(i, bitmap_bit_size);
+                const bit = i % bitmap_bit_size;
+                if (bitmaps[bitmap] & (@as(u64, 1) << @intCast(bit)) != 0) {
+                    return false;
+                }
+            }
+
+            return true;
+        }
+
+        /// For debugging
+        fn dumpBitmaps(self: *Self, base: anytype) void {
+            const bitmaps = self.bitmap.ptr(base);
+            for (bitmaps[0..self.bitmap_count], 0..) |bitmap, idx| {
+                std.log.warn("bm={b} idx={}", .{ bitmap, idx });
+            }
+        }
+
+        pub const Layout = struct {
+            total_size: usize,
+            bitmap_count: usize,
+            bitmap_start: usize,
+            chunks_start: usize,
+        };
+
+        /// Get the layout for the given capacity. The capacity is in
+        /// number of bytes, not chunks. The capacity will likely be
+        /// rounded up to the nearest chunk size and bitmap size so
+        /// everything is perfectly divisible.
+        pub fn layout(cap: usize) Layout {
+            // Align the cap forward to our chunk size so we always have
+            // a full chunk at the end.
+            const aligned_cap = alignForward(usize, cap, chunk_size);
+
+            // Calculate the number of bitmaps. We need 1 bitmap per 64 chunks.
+            // We align the chunk count forward so our bitmaps are full so we
+            // don't have to handle the case where we have a partial bitmap.
+            const chunk_count = @divExact(aligned_cap, chunk_size);
+            const aligned_chunk_count = alignForward(usize, chunk_count, 64);
+            const bitmap_count = @divExact(aligned_chunk_count, 64);
+
+            const bitmap_start = 0;
+            const bitmap_end = @sizeOf(u64) * bitmap_count;
+            const chunks_start = alignForward(usize, bitmap_end, @alignOf(u8));
+            const chunks_end = chunks_start + (aligned_cap * chunk_size);
+            const total_size = chunks_end;
+
+            return Layout{
+                .total_size = total_size,
+                .bitmap_count = bitmap_count,
+                .bitmap_start = bitmap_start,
+                .chunks_start = chunks_start,
+            };
+        }
+    };
+}
+
+/// Find `n` sequential free chunks in the given bitmaps and return the index
+/// of the first chunk. If no chunks are found, return `null`. This also updates
+/// the bitmap to mark the chunks as used.
+fn findFreeChunks(bitmaps: []u64, n: usize) ?usize {
+    // NOTE: This is a naive implementation that just iterates through the
+    // bitmaps. There is very likely a more efficient way to do this but
+    // I'm not a bit twiddling expert. Perhaps even SIMD could be used here
+    // but unsure. Contributor friendly: let's benchmark and improve this!
+
+    // Large chunks require special handling.
+    if (n > @bitSizeOf(u64)) {
+        var i: usize = 0;
+        search: while (i < bitmaps.len) {
+            // Number of chunks available at the end of this bitmap.
+            const prefix = @clz(~bitmaps[i]);
+
+            // If there are no chunks available at the end of this bitmap
+            // then we can't start in it, so we'll try the next one.
+            if (prefix == 0) {
+                i += 1;
+                continue;
+            }
+
+            // Starting position if we manage to find the span we need here.
+            const start_bitmap = i;
+            const start_bit = 64 - prefix;
+
+            // The remaining number of sequential free chunks we need to find.
+            var rem: usize = n - prefix;
+
+            i += 1;
+            while (rem > 64) : (i += 1) {
+                // We ran out of bitmaps, there's no sufficiently large gap.
+                if (i >= bitmaps.len) return null;
+
+                // There's more than 64 remaining chunks and this bitmap has
+                // content in it, so we try starting again with this bitmap.
+                if (bitmaps[i] != std.math.maxInt(u64)) continue :search;
+
+                // This bitmap is completely free, we can subtract 64 from
+                // our remaining number.
+                rem -= 64;
+            }
+
+            // If the number of available chunks at the start of this bitmap
+            // is less than the remaining required, we have to try again.
+            if (@ctz(~bitmaps[i]) < rem) continue;
+
+            const suffix = (n - prefix) % 64;
+
+            // Found! Mark everything between our start and end as full.
+            bitmaps[start_bitmap] ^= ~@as(u64, 0) >> @intCast(start_bit) << @intCast(start_bit);
+            const full_bitmaps = @divFloor(n - prefix - suffix, 64);
+            for (bitmaps[start_bitmap + 1 ..][0..full_bitmaps]) |*bitmap| {
+                bitmap.* = 0;
+            }
+            if (suffix > 0) bitmaps[i] ^= ~@as(u64, 0) >> @intCast(64 - suffix);
+
+            return start_bitmap * 64 + start_bit;
+        }
+
+        return null;
+    }
+
+    assert(n <= @bitSizeOf(u64));
+    for (bitmaps, 0..) |*bitmap, idx| {
+        // Shift the bitmap to find `n` sequential free chunks.
+        // EXAMPLE:
+        // n = 4
+        // shifted = 001111001011110010
+        //         & 000111100101111001
+        //         & 000011110010111100
+        //         & 000001111001011110
+        //         = 000001000000010000
+        //                ^       ^
+        // In this example there are 2 places with at least 4 sequential 1s.
+        var shifted: u64 = bitmap.*;
+        for (1..n) |i| shifted &= bitmap.* >> @intCast(i);
+
+        // If we have zero then we have no matches
+        if (shifted == 0) continue;
+
+        // Trailing zeroes gets us the index of the first bit index with at
+        // least `n` sequential 1s. In the example above, that would be `4`.
+        const bit = @ctz(shifted);
+
+        // Calculate the mask so we can mark it as used
+        const mask = (@as(u64, std.math.maxInt(u64)) >> @intCast(64 - n)) << @intCast(bit);
+        bitmap.* ^= mask;
+
+        return (idx * 64) + bit;
+    }
+
+    return null;
+}
+
+test "findFreeChunks single found" {
+    const testing = std.testing;
+
+    var bitmaps = [_]u64{
+        0b10000000_00000000_00000000_00000000_00000000_00000000_00001110_00000000,
+    };
+    const idx = findFreeChunks(&bitmaps, 2).?;
+    try testing.expectEqual(@as(usize, 9), idx);
+    try testing.expectEqual(
+        0b10000000_00000000_00000000_00000000_00000000_00000000_00001000_00000000,
+        bitmaps[0],
+    );
+}
+
+test "findFreeChunks single not found" {
+    const testing = std.testing;
+
+    var bitmaps = [_]u64{0b10000111_00000000_00000000_00000000_00000000_00000000_00000000_00000000};
+    const idx = findFreeChunks(&bitmaps, 4);
+    try testing.expect(idx == null);
+}
+
+test "findFreeChunks multiple found" {
+    const testing = std.testing;
+
+    var bitmaps = [_]u64{
+        0b10000111_00000000_00000000_00000000_00000000_00000000_00000000_01110000,
+        0b10000000_00111110_00000000_00000000_00000000_00000000_00111110_00000000,
+    };
+    const idx = findFreeChunks(&bitmaps, 4).?;
+    try testing.expectEqual(@as(usize, 73), idx);
+    try testing.expectEqual(
+        0b10000000_00111110_00000000_00000000_00000000_00000000_00100000_00000000,
+        bitmaps[1],
+    );
+}
+
+test "findFreeChunks exactly 64 chunks" {
+    const testing = std.testing;
+
+    var bitmaps = [_]u64{
+        0b11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111111,
+    };
+    const idx = findFreeChunks(&bitmaps, 64).?;
+    try testing.expectEqual(
+        0b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000000,
+        bitmaps[0],
+    );
+    try testing.expectEqual(@as(usize, 0), idx);
+}
+
+test "findFreeChunks larger than 64 chunks" {
+    const testing = std.testing;
+
+    var bitmaps = [_]u64{
+        0b11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111111,
+        0b11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111111,
+    };
+    const idx = findFreeChunks(&bitmaps, 65).?;
+    try testing.expectEqual(
+        0b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000000,
+        bitmaps[0],
+    );
+    try testing.expectEqual(
+        0b11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111110,
+        bitmaps[1],
+    );
+    try testing.expectEqual(@as(usize, 0), idx);
+}
+
+test "findFreeChunks larger than 64 chunks not at beginning" {
+    const testing = std.testing;
+
+    var bitmaps = [_]u64{
+        0b11111111_00000000_00000000_00000000_00000000_00000000_00000000_00000000,
+        0b11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111111,
+        0b11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111111,
+    };
+    const idx = findFreeChunks(&bitmaps, 65).?;
+    try testing.expectEqual(
+        0b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000000,
+        bitmaps[0],
+    );
+    try testing.expectEqual(
+        0b11111110_00000000_00000000_00000000_00000000_00000000_00000000_00000000,
+        bitmaps[1],
+    );
+    try testing.expectEqual(
+        0b11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111111,
+        bitmaps[2],
+    );
+    try testing.expectEqual(@as(usize, 56), idx);
+}
+
+test "findFreeChunks larger than 64 chunks exact" {
+    const testing = std.testing;
+
+    var bitmaps = [_]u64{
+        0b11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111111,
+        0b11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111111,
+    };
+    const idx = findFreeChunks(&bitmaps, 128).?;
+    try testing.expectEqual(
+        0b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000000,
+        bitmaps[0],
+    );
+    try testing.expectEqual(
+        0b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000000,
+        bitmaps[1],
+    );
+    try testing.expectEqual(@as(usize, 0), idx);
+}
+
+test "BitmapAllocator layout" {
+    const Alloc = BitmapAllocator(4);
+    const cap = 64 * 4;
+
+    const testing = std.testing;
+    const layout = Alloc.layout(cap);
+
+    // We expect to use one bitmap since the cap is bytes.
+    try testing.expectEqual(@as(usize, 1), layout.bitmap_count);
+}
+
+test "BitmapAllocator alloc sequentially" {
+    const Alloc = BitmapAllocator(4);
+    const cap = 64;
+
+    const testing = std.testing;
+    const alloc = testing.allocator;
+    const layout = Alloc.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, Alloc.base_align, layout.total_size);
+    defer alloc.free(buf);
+
+    var bm = Alloc.init(.init(buf), layout);
+    const ptr = try bm.alloc(u8, buf, 1);
+    ptr[0] = 'A';
+
+    const ptr2 = try bm.alloc(u8, buf, 1);
+    try testing.expect(@intFromPtr(ptr.ptr) != @intFromPtr(ptr2.ptr));
+
+    // Should grab the next chunk
+    try testing.expectEqual(@intFromPtr(ptr.ptr) + 4, @intFromPtr(ptr2.ptr));
+
+    // Free ptr and next allocation should be back
+    bm.free(buf, ptr);
+    const ptr3 = try bm.alloc(u8, buf, 1);
+    try testing.expectEqual(@intFromPtr(ptr.ptr), @intFromPtr(ptr3.ptr));
+}
+
+test "BitmapAllocator alloc non-byte" {
+    const Alloc = BitmapAllocator(4);
+    const cap = 128;
+
+    const testing = std.testing;
+    const alloc = testing.allocator;
+    const layout = Alloc.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, Alloc.base_align, layout.total_size);
+    defer alloc.free(buf);
+
+    var bm = Alloc.init(.init(buf), layout);
+    const ptr = try bm.alloc(u21, buf, 1);
+    ptr[0] = 'A';
+
+    const ptr2 = try bm.alloc(u21, buf, 1);
+    try testing.expect(@intFromPtr(ptr.ptr) != @intFromPtr(ptr2.ptr));
+    try testing.expectEqual(@intFromPtr(ptr.ptr) + 4, @intFromPtr(ptr2.ptr));
+
+    // Free ptr and next allocation should be back
+    bm.free(buf, ptr);
+    const ptr3 = try bm.alloc(u21, buf, 1);
+    try testing.expectEqual(@intFromPtr(ptr.ptr), @intFromPtr(ptr3.ptr));
+}
+
+test "BitmapAllocator alloc non-byte multi-chunk" {
+    const Alloc = BitmapAllocator(4 * @sizeOf(u21));
+    const cap = 128;
+
+    const testing = std.testing;
+    const alloc = testing.allocator;
+    const layout = Alloc.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, Alloc.base_align, layout.total_size);
+    defer alloc.free(buf);
+
+    var bm = Alloc.init(.init(buf), layout);
+    const ptr = try bm.alloc(u21, buf, 6);
+    try testing.expectEqual(@as(usize, 6), ptr.len);
+    for (ptr) |*v| v.* = 'A';
+
+    const ptr2 = try bm.alloc(u21, buf, 1);
+    try testing.expect(@intFromPtr(ptr.ptr) != @intFromPtr(ptr2.ptr));
+    try testing.expectEqual(@intFromPtr(ptr.ptr) + (@sizeOf(u21) * 4 * 2), @intFromPtr(ptr2.ptr));
+
+    // Free ptr and next allocation should be back
+    bm.free(buf, ptr);
+    const ptr3 = try bm.alloc(u21, buf, 1);
+    try testing.expectEqual(@intFromPtr(ptr.ptr), @intFromPtr(ptr3.ptr));
+}
+
+test "BitmapAllocator alloc large" {
+    const Alloc = BitmapAllocator(2);
+    const cap = 256;
+
+    const testing = std.testing;
+    const alloc = testing.allocator;
+    const layout = Alloc.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, Alloc.base_align, layout.total_size);
+    defer alloc.free(buf);
+
+    var bm = Alloc.init(.init(buf), layout);
+    const ptr = try bm.alloc(u8, buf, 129);
+    ptr[0] = 'A';
+    bm.free(buf, ptr);
+}
+
+test "BitmapAllocator alloc and free one bitmap" {
+    const Alloc = BitmapAllocator(1);
+    // Capacity such that we'll have 3 bitmaps.
+    const cap = Alloc.bitmap_bit_size * 3;
+
+    const testing = std.testing;
+    const alloc = testing.allocator;
+    const layout = Alloc.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, Alloc.base_align, layout.total_size);
+    defer alloc.free(buf);
+
+    var bm = Alloc.init(.init(buf), layout);
+
+    // Allocate exactly one bitmap worth of bytes.
+    const slice = try bm.alloc(u8, buf, Alloc.bitmap_bit_size);
+    try testing.expectEqual(Alloc.bitmap_bit_size, slice.len);
+
+    @memset(slice, 0x11);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([Alloc.bitmap_bit_size]u8, @splat(0x11)),
+        slice,
+    );
+
+    // Free it
+    try testing.expect(bm.isAllocated(buf, slice));
+    bm.free(buf, slice);
+    try testing.expect(!bm.isAllocated(buf, slice));
+
+    // All of our bitmaps should be free.
+    try testing.expectEqualSlices(
+        u64,
+        &@as([3]u64, @splat(~@as(u64, 0))),
+        bm.bitmap.ptr(buf)[0..3],
+    );
+}
+
+test "BitmapAllocator alloc and free half bitmap" {
+    const Alloc = BitmapAllocator(1);
+    // Capacity such that we'll have 3 bitmaps.
+    const cap = Alloc.bitmap_bit_size * 3;
+
+    const testing = std.testing;
+    const alloc = testing.allocator;
+    const layout = Alloc.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, Alloc.base_align, layout.total_size);
+    defer alloc.free(buf);
+
+    var bm = Alloc.init(.init(buf), layout);
+
+    // Allocate exactly half a bitmap worth of bytes.
+    const slice = try bm.alloc(u8, buf, Alloc.bitmap_bit_size / 2);
+    try testing.expectEqual(Alloc.bitmap_bit_size / 2, slice.len);
+
+    @memset(slice, 0x11);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([Alloc.bitmap_bit_size / 2]u8, @splat(0x11)),
+        slice,
+    );
+
+    // Free it
+    try testing.expect(bm.isAllocated(buf, slice));
+    bm.free(buf, slice);
+    try testing.expect(!bm.isAllocated(buf, slice));
+
+    // All of our bitmaps should be free.
+    try testing.expectEqualSlices(
+        u64,
+        &@as([3]u64, @splat(~@as(u64, 0))),
+        bm.bitmap.ptr(buf)[0..3],
+    );
+}
+
+test "BitmapAllocator alloc and free two half bitmaps" {
+    const Alloc = BitmapAllocator(1);
+    // Capacity such that we'll have 3 bitmaps.
+    const cap = Alloc.bitmap_bit_size * 3;
+
+    const testing = std.testing;
+    const alloc = testing.allocator;
+    const layout = Alloc.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, Alloc.base_align, layout.total_size);
+    defer alloc.free(buf);
+
+    var bm = Alloc.init(.init(buf), layout);
+
+    // Allocate exactly one bitmap worth of bytes across two allocations.
+    const slice = try bm.alloc(u8, buf, Alloc.bitmap_bit_size / 2);
+    try testing.expectEqual(Alloc.bitmap_bit_size / 2, slice.len);
+
+    @memset(slice, 0x11);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([Alloc.bitmap_bit_size / 2]u8, @splat(0x11)),
+        slice,
+    );
+
+    const slice2 = try bm.alloc(u8, buf, Alloc.bitmap_bit_size / 2);
+    try testing.expectEqual(Alloc.bitmap_bit_size / 2, slice2.len);
+
+    @memset(slice2, 0x22);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([Alloc.bitmap_bit_size / 2]u8, @splat(0x22)),
+        slice2,
+    );
+    try testing.expectEqualSlices(
+        u8,
+        &@as([Alloc.bitmap_bit_size / 2]u8, @splat(0x11)),
+        slice,
+    );
+
+    // Free them
+    try testing.expect(bm.isAllocated(buf, slice2));
+    bm.free(buf, slice2);
+    try testing.expect(!bm.isAllocated(buf, slice2));
+    try testing.expect(bm.isAllocated(buf, slice));
+    bm.free(buf, slice);
+    try testing.expect(!bm.isAllocated(buf, slice));
+
+    // All of our bitmaps should be free.
+    try testing.expectEqualSlices(
+        u64,
+        &@as([3]u64, @splat(~@as(u64, 0))),
+        bm.bitmap.ptr(buf)[0..3],
+    );
+}
+
+test "BitmapAllocator alloc and free 1.5 bitmaps" {
+    const Alloc = BitmapAllocator(1);
+    // Capacity such that we'll have 3 bitmaps.
+    const cap = Alloc.bitmap_bit_size * 3;
+
+    const testing = std.testing;
+    const alloc = testing.allocator;
+    const layout = Alloc.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, Alloc.base_align, layout.total_size);
+    defer alloc.free(buf);
+
+    var bm = Alloc.init(.init(buf), layout);
+
+    // Allocate exactly 1.5 bitmaps worth of bytes.
+    const slice = try bm.alloc(u8, buf, 3 * Alloc.bitmap_bit_size / 2);
+    try testing.expectEqual(3 * Alloc.bitmap_bit_size / 2, slice.len);
+
+    @memset(slice, 0x11);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 2]u8, @splat(0x11)),
+        slice,
+    );
+
+    // Free them
+    try testing.expect(bm.isAllocated(buf, slice));
+    bm.free(buf, slice);
+    try testing.expect(!bm.isAllocated(buf, slice));
+
+    // All of our bitmaps should be free.
+    try testing.expectEqualSlices(
+        u64,
+        &@as([3]u64, @splat(~@as(u64, 0))),
+        bm.bitmap.ptr(buf)[0..3],
+    );
+}
+
+test "BitmapAllocator alloc and free two 1.5 bitmaps" {
+    const Alloc = BitmapAllocator(1);
+    // Capacity such that we'll have 3 bitmaps.
+    const cap = Alloc.bitmap_bit_size * 3;
+
+    const testing = std.testing;
+    const alloc = testing.allocator;
+    const layout = Alloc.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, Alloc.base_align, layout.total_size);
+    defer alloc.free(buf);
+
+    var bm = Alloc.init(.init(buf), layout);
+
+    // Allocate exactly 3 bitmaps worth of bytes across two allocations.
+    const slice = try bm.alloc(u8, buf, 3 * Alloc.bitmap_bit_size / 2);
+    try testing.expectEqual(3 * Alloc.bitmap_bit_size / 2, slice.len);
+
+    @memset(slice, 0x11);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 2]u8, @splat(0x11)),
+        slice,
+    );
+
+    const slice2 = try bm.alloc(u8, buf, 3 * Alloc.bitmap_bit_size / 2);
+    try testing.expectEqual(3 * Alloc.bitmap_bit_size / 2, slice2.len);
+
+    @memset(slice2, 0x22);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 2]u8, @splat(0x22)),
+        slice2,
+    );
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 2]u8, @splat(0x11)),
+        slice,
+    );
+
+    // Free them
+    try testing.expect(bm.isAllocated(buf, slice2));
+    bm.free(buf, slice2);
+    try testing.expect(!bm.isAllocated(buf, slice2));
+    try testing.expect(bm.isAllocated(buf, slice));
+    bm.free(buf, slice);
+    try testing.expect(!bm.isAllocated(buf, slice));
+
+    // All of our bitmaps should be free.
+    try testing.expectEqualSlices(
+        u64,
+        &@as([3]u64, @splat(~@as(u64, 0))),
+        bm.bitmap.ptr(buf)[0..3],
+    );
+}
+
+test "BitmapAllocator alloc and free 1.5 bitmaps offset by 0.75" {
+    const Alloc = BitmapAllocator(1);
+    // Capacity such that we'll have 3 bitmaps.
+    const cap = Alloc.bitmap_bit_size * 3;
+
+    const testing = std.testing;
+    const alloc = testing.allocator;
+    const layout = Alloc.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, Alloc.base_align, layout.total_size);
+    defer alloc.free(buf);
+
+    var bm = Alloc.init(.init(buf), layout);
+
+    // Allocate three quarters of a bitmap first.
+    const slice = try bm.alloc(u8, buf, 3 * Alloc.bitmap_bit_size / 4);
+    try testing.expectEqual(3 * Alloc.bitmap_bit_size / 4, slice.len);
+
+    @memset(slice, 0x11);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 4]u8, @splat(0x11)),
+        slice,
+    );
+
+    // Then a 1.5 bitmap sized allocation, so that it spans
+    // from 0.75 to 2.25, occupying bits in 3 different bitmaps.
+    const slice2 = try bm.alloc(u8, buf, 3 * Alloc.bitmap_bit_size / 2);
+    try testing.expectEqual(3 * Alloc.bitmap_bit_size / 2, slice2.len);
+
+    @memset(slice2, 0x22);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 2]u8, @splat(0x22)),
+        slice2,
+    );
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 4]u8, @splat(0x11)),
+        slice,
+    );
+
+    // Free them
+    try testing.expect(bm.isAllocated(buf, slice2));
+    bm.free(buf, slice2);
+    try testing.expect(!bm.isAllocated(buf, slice2));
+    try testing.expect(bm.isAllocated(buf, slice));
+    bm.free(buf, slice);
+    try testing.expect(!bm.isAllocated(buf, slice));
+
+    // All of our bitmaps should be free.
+    try testing.expectEqualSlices(
+        u64,
+        &@as([3]u64, @splat(~@as(u64, 0))),
+        bm.bitmap.ptr(buf)[0..3],
+    );
+}
+
+test "BitmapAllocator alloc and free three 0.75 bitmaps" {
+    const Alloc = BitmapAllocator(1);
+    // Capacity such that we'll have 3 bitmaps.
+    const cap = Alloc.bitmap_bit_size * 3;
+
+    const testing = std.testing;
+    const alloc = testing.allocator;
+    const layout = Alloc.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, Alloc.base_align, layout.total_size);
+    defer alloc.free(buf);
+
+    var bm = Alloc.init(.init(buf), layout);
+
+    // Allocate three quarters of a bitmap three times.
+    const slice = try bm.alloc(u8, buf, 3 * Alloc.bitmap_bit_size / 4);
+    try testing.expectEqual(3 * Alloc.bitmap_bit_size / 4, slice.len);
+
+    @memset(slice, 0x11);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 4]u8, @splat(0x11)),
+        slice,
+    );
+
+    const slice2 = try bm.alloc(u8, buf, 3 * Alloc.bitmap_bit_size / 4);
+    try testing.expectEqual(3 * Alloc.bitmap_bit_size / 4, slice2.len);
+
+    @memset(slice2, 0x22);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 4]u8, @splat(0x22)),
+        slice2,
+    );
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 4]u8, @splat(0x11)),
+        slice,
+    );
+
+    const slice3 = try bm.alloc(u8, buf, 3 * Alloc.bitmap_bit_size / 4);
+    try testing.expectEqual(3 * Alloc.bitmap_bit_size / 4, slice3.len);
+
+    @memset(slice3, 0x33);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 4]u8, @splat(0x33)),
+        slice3,
+    );
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 4]u8, @splat(0x22)),
+        slice2,
+    );
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 4]u8, @splat(0x11)),
+        slice,
+    );
+
+    // Free them
+    try testing.expect(bm.isAllocated(buf, slice2));
+    bm.free(buf, slice2);
+    try testing.expect(!bm.isAllocated(buf, slice2));
+    try testing.expect(bm.isAllocated(buf, slice));
+    bm.free(buf, slice);
+    try testing.expect(!bm.isAllocated(buf, slice));
+    try testing.expect(bm.isAllocated(buf, slice3));
+    bm.free(buf, slice3);
+    try testing.expect(!bm.isAllocated(buf, slice3));
+
+    // All of our bitmaps should be free.
+    try testing.expectEqualSlices(
+        u64,
+        &@as([3]u64, @splat(~@as(u64, 0))),
+        bm.bitmap.ptr(buf)[0..3],
+    );
+}
+
+test "BitmapAllocator alloc and free two 1.5 bitmaps offset 0.75" {
+    const Alloc = BitmapAllocator(1);
+    // Capacity such that we'll have 4 bitmaps.
+    const cap = Alloc.bitmap_bit_size * 4;
+
+    const testing = std.testing;
+    const alloc = testing.allocator;
+    const layout = Alloc.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, Alloc.base_align, layout.total_size);
+    defer alloc.free(buf);
+
+    var bm = Alloc.init(.init(buf), layout);
+
+    // First allocate a 0.75 bitmap
+    const slice = try bm.alloc(u8, buf, 3 * Alloc.bitmap_bit_size / 4);
+    try testing.expectEqual(3 * Alloc.bitmap_bit_size / 4, slice.len);
+
+    @memset(slice, 0x11);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 4]u8, @splat(0x11)),
+        slice,
+    );
+
+    // Then two 1.5 bitmaps
+    const slice2 = try bm.alloc(u8, buf, 3 * Alloc.bitmap_bit_size / 2);
+    try testing.expectEqual(3 * Alloc.bitmap_bit_size / 2, slice2.len);
+
+    @memset(slice2, 0x22);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 2]u8, @splat(0x22)),
+        slice2,
+    );
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 4]u8, @splat(0x11)),
+        slice,
+    );
+
+    const slice3 = try bm.alloc(u8, buf, 3 * Alloc.bitmap_bit_size / 2);
+    try testing.expectEqual(3 * Alloc.bitmap_bit_size / 2, slice3.len);
+
+    @memset(slice3, 0x33);
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 2]u8, @splat(0x33)),
+        slice3,
+    );
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 2]u8, @splat(0x22)),
+        slice2,
+    );
+    try testing.expectEqualSlices(
+        u8,
+        &@as([3 * Alloc.bitmap_bit_size / 4]u8, @splat(0x11)),
+        slice,
+    );
+
+    // Free them
+    try testing.expect(bm.isAllocated(buf, slice2));
+    bm.free(buf, slice2);
+    try testing.expect(!bm.isAllocated(buf, slice2));
+    try testing.expect(bm.isAllocated(buf, slice));
+    bm.free(buf, slice);
+    try testing.expect(!bm.isAllocated(buf, slice));
+    try testing.expect(bm.isAllocated(buf, slice3));
+    bm.free(buf, slice3);
+    try testing.expect(!bm.isAllocated(buf, slice3));
+
+    // All of our bitmaps should be free.
+    try testing.expectEqualSlices(
+        u64,
+        &@as([4]u64, @splat(~@as(u64, 0))),
+        bm.bitmap.ptr(buf)[0..4],
+    );
+}
+
+test "BitmapAllocator bytesRequired" {
+    const testing = std.testing;
+
+    // Chunk size of 16 bytes (like grapheme_chunk in page.zig)
+    {
+        const Alloc = BitmapAllocator(16);
+
+        // Single byte rounds up to chunk size
+        try testing.expectEqual(16, Alloc.bytesRequired(u8, 1));
+        try testing.expectEqual(16, Alloc.bytesRequired(u8, 16));
+        try testing.expectEqual(32, Alloc.bytesRequired(u8, 17));
+
+        // u21 (4 bytes each)
+        try testing.expectEqual(16, Alloc.bytesRequired(u21, 1)); // 4 bytes -> 16
+        try testing.expectEqual(16, Alloc.bytesRequired(u21, 4)); // 16 bytes -> 16
+        try testing.expectEqual(32, Alloc.bytesRequired(u21, 5)); // 20 bytes -> 32
+        try testing.expectEqual(32, Alloc.bytesRequired(u21, 6)); // 24 bytes -> 32
+    }
+
+    // Chunk size of 4 bytes
+    {
+        const Alloc = BitmapAllocator(4);
+
+        try testing.expectEqual(4, Alloc.bytesRequired(u8, 1));
+        try testing.expectEqual(4, Alloc.bytesRequired(u8, 4));
+        try testing.expectEqual(8, Alloc.bytesRequired(u8, 5));
+
+        // u32 (4 bytes each) - exactly one chunk per element
+        try testing.expectEqual(4, Alloc.bytesRequired(u32, 1));
+        try testing.expectEqual(8, Alloc.bytesRequired(u32, 2));
+    }
+
+    // Chunk size of 32 bytes (like string_chunk in page.zig)
+    {
+        const Alloc = BitmapAllocator(32);
+
+        try testing.expectEqual(32, Alloc.bytesRequired(u8, 1));
+        try testing.expectEqual(32, Alloc.bytesRequired(u8, 32));
+        try testing.expectEqual(64, Alloc.bytesRequired(u8, 33));
+    }
+}