feat: pmm + kernel heap

6 files changed, 367 insertions, 9 deletions

diff --git a/boot/boot.zig b/boot/boot.zig
index 6cc3d12..933065c 100644
--- a/boot/boot.zig
+++ b/boot/boot.zig
@@ -4,6 +4,8 @@ const serial = @import("serial.zig");
 const framebuffer = @import("framebuffer.zig");
 const gdt = @import("gdt.zig");
 const idt = @import("idt.zig");
+const pmm = @import("pmm.zig");
+const heap = @import("heap.zig");
 
 // We need a panic handler otherwise zig won't be happy,
 // std usually formats a message through std.Io.Writer which
@@ -24,6 +26,11 @@ export var base_revision: limine.BaseRevision linksection(".limine_requests") =
 export var requests_start: limine.RequestsStartMarker linksection(".limine_requests_start") = .{};
 export var requests_end: limine.RequestsEndMarker linksection(".limine_requests_end") = .{};
 
+// the loader fills these before we run so we read them through volatile pointers or
+// the optimizer assumes they're still the null we initialized them to
+export var hhdm_request: limine.HhdmRequest linksection(".limine_requests") = .{};
+export var memmap_request: limine.MemoryMapRequest linksection(".limine_requests") = .{};
+
 // ENTRY(_start)
 export fn _start() callconv(.c) noreturn {
     serial.init();
@@ -31,8 +38,38 @@ export fn _start() callconv(.c) noreturn {
 
     gdt.load();
     idt.init();
+
+    
     serial.write("gdt + idt loaded\r\n");
 
+    // HHDM + memory map -> physical frame allocator -> kernel heap
+    const hhdm_req: *volatile limine.HhdmRequest = &hhdm_request;
+    const memmap_req: *volatile limine.MemoryMapRequest = &memmap_request;
+    const hhdm = hhdm_req.response orelse @panic("limine gave us no HHDM");
+    const memmap = memmap_req.response orelse @panic("limine gave us no memory map");
+
+    pmm.init(hhdm, memmap);
+    pmm.dump(memmap);
+    heap.init();
+
+    // NOTE: this is a sanity check
+    // two allocations should be distinct and non-overlapping,
+    // and a freed frame should come straight back on the next alloc.
+    const a = pmm.alloc().?;
+    const b = pmm.alloc().?;
+    serial.write("pmm test: a=");
+    serial.writeHex(a);
+    serial.write(" b=");
+    serial.writeHex(b);
+    serial.write("\r\n");
+    pmm.free(a);
+    const c = pmm.alloc().?;
+    serial.write("pmm test: freed a, realloc=");
+    serial.writeHex(c);
+    serial.write(if (c == a) " (reused, good)\r\n" else " (mismatch!)\r\n");
+    pmm.free(b);
+    pmm.free(c);
+
     if (framebuffer.get()) |screen| {
         // XOR texture
         var y: usize = 0;
diff --git a/boot/framebuffer.zig b/boot/framebuffer.zig
index 6518b17..b82e5af 100644
--- a/boot/framebuffer.zig
+++ b/boot/framebuffer.zig
@@ -19,7 +19,7 @@ pub fn get() ?*Framebuffer {
 }
 
 // assumes the usual Limine RGB 32-bpp layout im sure i wont forget about this layout
-// later and i wont fuck me over
+// later and it wont fuck me over
 pub fn putpixel(fb: *Framebuffer, x: usize, y: usize, color: u32) void {
     const pixel: *align(1) u32 = @ptrCast(fb.address + y * fb.pitch + x * 4);
     pixel.* = color;
diff --git a/boot/heap.zig b/boot/heap.zig
new file mode 100644
index 0000000..2f4e74b
--- /dev/null
+++ b/boot/heap.zig
@@ -0,0 +1,34 @@
+// this just grabs a contiguous chunk of frams from the PMM and then
+// hands out a bump allocator, this just gives std.mem.Allocator which
+// we'll pass to the revo VM later. FixedBufferAllocator never reclaims
+// freed space unless you free in reverse order which is ehhhhh, fine ig
+// for bootstrapping.
+//
+// TODO: swap fixed buffer allocator for a free list allocator
+
+const std = @import("std");
+const pmm = @import("pmm.zig");
+const serial = @import("serial.zig");
+
+// 4 MiB. 
+// NOTE: bump if the VM needs more
+const HEAP_PAGES: usize = 1024;
+
+var fba: std.heap.FixedBufferAllocator = undefined;
+
+pub fn init() void {
+    const phys = pmm.allocContig(HEAP_PAGES) orelse @panic("heap: no contiguous frames for the heap");
+    const virt = pmm.physToVirt(phys);
+    const buf: [*]u8 = @ptrFromInt(virt);
+    fba = std.heap.FixedBufferAllocator.init(buf[0 .. HEAP_PAGES * pmm.PAGE_SIZE]);
+
+    serial.write("heap: ");
+    serial.writeDec((HEAP_PAGES * pmm.PAGE_SIZE) / (1024 * 1024));
+    serial.write(" MiB at ");
+    serial.writeHex(virt);
+    serial.write("\r\n");
+}
+
+pub fn allocator() std.mem.Allocator {
+    return fba.allocator();
+}
diff --git a/boot/limine.zig b/boot/limine.zig
index e993853..914aca8 100644
--- a/boot/limine.zig
+++ b/boot/limine.zig
@@ -1,6 +1,6 @@
-// Limine scans the loaded image for these magic numbers,
-// BaseRevision is a handshake, essentially we ask limine
-// for rev 3, and if it supports it, limine zeros it out
+// Limine scans the loaded image for these magic numbers, BaseRevision is 
+// a handshake, essentially we ask limine for rev 3, and if it supports it, 
+// limine zeros it out
 pub const BaseRevision = extern struct {
     magic0: u64 = 0xf9562b2d5c95a6c8,
     magic1: u64 = 0x6a7b384944536bdc,
@@ -11,9 +11,8 @@ pub const BaseRevision = extern struct {
     }
 };
 
-// Bracketing markers, they are pretty optional but when
-// we add proper limine requests, having these here comes
-// handy
+// bracketing markers, they are pretty optional but when we add proper 
+// limine requests, having these here comes handy
 pub const RequestsStartMarker = extern struct {
     m0: u64 = 0xf6b8f4b39de7d1ae,
     m1: u64 = 0xfab91a6940fcb9cf,
@@ -26,8 +25,8 @@ pub const RequestsEndMarker = extern struct {
     m1: u64 = 0x9572709f31764c62,
 };
 
-// Every request id starts with this common magic, then two request-specific
-// words. Limine scans .limine_requests for these and fills in `response`.
+// every request id starts with this common magic, then two request specific
+// words, bootloader scans .limine_requests for these and fills in `response`
 fn requestId(a: u64, b: u64) [4]u64 {
     return .{ 0xc7b1dd30df4c8b88, 0x0a82e883a194f07b, a, b };
 }
@@ -66,3 +65,53 @@ pub const FramebufferRequest = extern struct {
     revision: u64 = 0,
     response: ?*FramebufferResponse = null,
 };
+
+// HHDM = higher-half direct map, limine linearly maps ALL of physical memory
+// starting at `offset`, so any physical address p is reachable at p + offset
+// This is how we touch physical frames without setting up our own page tables
+// and this is how my hypothetical future girlfriend should touch my pointer
+pub const HhdmResponse = extern struct {
+    revision: u64,
+    offset: u64,
+};
+
+pub const HhdmRequest = extern struct {
+    id: [4]u64 = requestId(0x48dcf1cb8ad2b852, 0x63984e959a98244b),
+    revision: u64 = 0,
+    response: ?*HhdmResponse = null,
+};
+
+// what each region of physical memory is
+// only `usable` (0) is ours to hand out freely
+// the rest belongs to firmware and other stingy shits
+pub const MemoryType = enum(u64) {
+    usable = 0,
+    reserved = 1,
+    acpi_reclaimable = 2,
+    acpi_nvs = 3,
+    bad = 4,
+    bootloader_reclaimable = 5,
+    kernel_and_modules = 6,
+    framebuffer = 7,
+    _,
+};
+
+pub const MemoryMapEntry = extern struct {
+    base: u64,
+    length: u64,
+    type: MemoryType,
+};
+
+// NOTE: `entries` is an array of POINTERS to entries, not the entries inline
+// NOTE: i will forget this
+pub const MemoryMapResponse = extern struct {
+    revision: u64,
+    entry_count: u64,
+    entries: ?[*]*MemoryMapEntry,
+};
+
+pub const MemoryMapRequest = extern struct {
+    id: [4]u64 = requestId(0x67cf3d9d378a806f, 0xe304acdfc50c3c62),
+    revision: u64 = 0,
+    response: ?*MemoryMapResponse = null,
+};
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",
+    };
+}
diff --git a/boot/serial.zig b/boot/serial.zig
index 4863864..2e8c8d0 100644
--- a/boot/serial.zig
+++ b/boot/serial.zig
@@ -48,3 +48,31 @@ fn putc(c: u8) void {
 pub fn write(s: []const u8) void {
     for (s) |c| putc(c);
 }
+
+// dump a u64 as decimal. handy for "usable: N MiB" type logging.
+pub fn writeDec(value: u64) void {
+    if (value == 0) return putc('0');
+    var buf: [20]u8 = undefined;
+    var i: usize = buf.len;
+    var v = value;
+    while (v > 0) {
+        i -= 1;
+        buf[i] = '0' + @as(u8, @intCast(v % 10));
+        v /= 10;
+    }
+    write(buf[i..]);
+}
+
+// dump a u64 as 0x-prefixed 16-digit hex.
+pub fn writeHex(value: u64) void {
+    const digits = "0123456789abcdef";
+    var buf: [18]u8 = undefined;
+    buf[0] = '0';
+    buf[1] = 'x';
+    var i: usize = 0;
+    while (i < 16) : (i += 1) {
+        const shift: u6 = @intCast((15 - i) * 4);
+        buf[2 + i] = digits[(value >> shift) & 0xF];
+    }
+    write(&buf);
+}