feat: pmm + kernel heap

1 files changed, 210 insertions, 0 deletions

diff --git a/boot/pmm.zig b/boot/pmm.zig
new file mode 100644
index 0000000..71d132e
--- /dev/null
+++ b/boot/pmm.zig
@@ -0,0 +1,210 @@
+// Physical memory manager: a bitmap of 4 KiB frames over Limine's memory map.
+// this manages a bitmap of 4 KiB frames over limine's memory map.
+// one bit per frame, 1 = used, 0 = free.
+// this is just barely good enough to bootstrap a real heap later
+// TODO: make this better lmao
+//
+// we never touch physical memory directly, everything goes through the HHDM
+// offset (phys + offset = a virtual address limine already mapped for us)
+//
+// see: https://wiki.osdev.org/Physical_Memory_Allocation
+
+const limine = @import("limine.zig");
+const serial = @import("serial.zig");
+
+pub const PAGE_SIZE: usize = 4096;
+
+var hhdm_offset: u64 = 0;
+
+// the bitmap itself lives inside a usable region (found at init time) and is
+// reached through the HHDM, so it's just a normal slice we write through.
+var bitmap: []u8 = &[_]u8{};
+
+var total_frames: usize = 0;  // frames the bitmap can index (up to highest usable end)
+var usable_frames: usize = 0; // frames that started free
+var free_frames: usize = 0;   // frames currently free
+var next_hint: usize = 0;     // where to start the next alloc scan
+
+pub fn physToVirt(phys: u64) u64 {
+    return phys + hhdm_offset;
+}
+
+fn frameUsed(i: usize) bool {
+    return (bitmap[i >> 3] & (@as(u8, 1) << @intCast(i & 7))) != 0;
+}
+
+fn markUsed(i: usize) void {
+    bitmap[i >> 3] |= (@as(u8, 1) << @intCast(i & 7));
+}
+
+fn markFree(i: usize) void {
+    bitmap[i >> 3] &= ~(@as(u8, 1) << @intCast(i & 7));
+}
+
+// walk a region's frames and apply f to each index. base is rounded up and
+// end rounded down so we only ever touch whole frames fully inside the region.
+fn forEachFrame(base: u64, length: u64, comptime f: fn (usize) void) void {
+    const start = (base + PAGE_SIZE - 1) / PAGE_SIZE;
+    const end = (base + length) / PAGE_SIZE;
+    var i = start;
+    while (i < end) : (i += 1) {
+        if (i < total_frames) f(i);
+    }
+}
+
+pub fn init(hhdm: *const limine.HhdmResponse, memmap: *const limine.MemoryMapResponse) void {
+    hhdm_offset = hhdm.offset;
+    const entries = memmap.entries.?[0..memmap.entry_count];
+
+    // highest end of any usable region bounds the bitmap. we only ever
+    //  alloc/free usable frames, so there's no point indexing past that
+    var highest: u64 = 0;
+    for (entries) |e| {
+        if (e.type == .usable) {
+            const top = e.base + e.length;
+            if (top > highest) highest = top;
+        }
+    }
+    total_frames = highest / PAGE_SIZE;
+    const bitmap_bytes = (total_frames + 7) / 8;
+
+    // park the bitmap in the first usable region big enough to hold it
+    var storage_base: u64 = 0;
+    for (entries) |e| {
+        if (e.type == .usable and e.length >= bitmap_bytes) {
+            storage_base = e.base;
+            break;
+        }
+    }
+    if (storage_base == 0 and bitmap_bytes > 0) @panic("pmm: no room for the frame bitmap");
+    const ptr: [*]u8 = @ptrFromInt(physToVirt(storage_base));
+    bitmap = ptr[0..bitmap_bytes];
+
+    // start with everything used, then punch out the usable regions
+    @memset(bitmap, 0xFF);
+    for (entries) |e| {
+        if (e.type == .usable) {
+            forEachFrame(e.base, e.length, markFree);
+            usable_frames += e.length / PAGE_SIZE;
+        }
+    }
+    free_frames = usable_frames;
+
+    // reclaim nothing that we're actually using, so the bitmap's own frames,
+    // and frame 0.
+    //
+    // WARNING: never hand out a physical-null address
+    //
+    // unlike marking a region free, here we round the END UP so a partial 
+    // last frame the bitmap spills into still gets reserved
+    {
+        const start = storage_base / PAGE_SIZE;
+        const end = (storage_base + bitmap_bytes + PAGE_SIZE - 1) / PAGE_SIZE;
+        var i = start;
+        while (i < end) : (i += 1) {
+            if (i < total_frames) reserve(i);
+        }
+    }
+    if (total_frames > 0) reserve(0);
+}
+
+// reserve = mark used
+fn reserve(i: usize) void {
+    if (!frameUsed(i)) {
+        markUsed(i);
+        free_frames -= 1;
+    }
+}
+
+// hand out one physical frame, or null if we're out
+// NOTE: returns a physical address
+pub fn alloc() ?u64 {
+    var i = next_hint;
+    var scanned: usize = 0;
+    while (scanned < total_frames) : (scanned += 1) {
+        if (i >= total_frames) i = 0;
+        if (!frameUsed(i)) {
+            markUsed(i);
+            free_frames -= 1;
+            next_hint = i + 1;
+            return @as(u64, i) * PAGE_SIZE;
+        }
+        i += 1;
+    }
+    return null;
+}
+
+// hand out n contiguous physical frames cause the heap needs one flat buffer, and a
+// single usable region is contiguous in physical space, so this just finds a
+// run of n free bits. 
+// NOTE: returns the base physical address of the run
+pub fn allocContig(n: usize) ?u64 {
+    if (n == 0) return null;
+    var i: usize = 0;
+    while (i + n <= total_frames) {
+        var run: usize = 0;
+        while (run < n and !frameUsed(i + run)) : (run += 1) {}
+        if (run == n) {
+            var j: usize = 0;
+            while (j < n) : (j += 1) {
+                markUsed(i + j);
+                free_frames -= 1;
+            }
+            return @as(u64, i) * PAGE_SIZE;
+        }
+        // skip past the used frame that broke the run
+        i += run + 1;
+    }
+    return null;
+}
+
+pub fn free(phys: u64) void {
+    const i = phys / PAGE_SIZE;
+    if (i < total_frames and frameUsed(i)) {
+        markFree(i);
+        free_frames += 1;
+        if (i < next_hint) next_hint = i;
+    }
+}
+
+pub fn freeBytes() u64 {
+    return @as(u64, free_frames) * PAGE_SIZE;
+}
+
+pub fn usableBytes() u64 {
+    return @as(u64, usable_frames) * PAGE_SIZE;
+}
+
+// dump the map + totals to serial so we can eyeball what limine gave us.
+pub fn dump(memmap: *const limine.MemoryMapResponse) void {
+    const entries = memmap.entries.?[0..memmap.entry_count];
+    serial.write("memory map:\r\n");
+    for (entries) |e| {
+        serial.write("  ");
+        serial.writeHex(e.base);
+        serial.write(" len=");
+        serial.writeHex(e.length);
+        serial.write(" type=");
+        serial.write(typeName(e.type));
+        serial.write("\r\n");
+    }
+    serial.write("usable: ");
+    serial.writeDec(usableBytes() / (1024 * 1024));
+    serial.write(" MiB, free: ");
+    serial.writeDec(freeBytes() / (1024 * 1024));
+    serial.write(" MiB\r\n");
+}
+
+fn typeName(t: limine.MemoryType) []const u8 {
+    return switch (t) {
+        .usable => "usable",
+        .reserved => "reserved",
+        .acpi_reclaimable => "acpi-reclaimable",
+        .acpi_nvs => "acpi-nvs",
+        .bad => "bad",
+        .bootloader_reclaimable => "bootloader-reclaimable",
+        .kernel_and_modules => "kernel+modules",
+        .framebuffer => "framebuffer",
+        _ => "unknown",
+    };
+}