From c34524767c9eac650f16dbe9059c24af2acd1397 Mon Sep 17 00:00:00 2001 From: hachem Date: Fri, 11 Sep 2026 02:38:27 +0200 Subject: feat: pmm + kernel heap --- boot/boot.zig | 37 +++++++++ boot/framebuffer.zig | 2 +- boot/heap.zig | 34 +++++++++ boot/limine.zig | 65 ++++++++++++++-- boot/pmm.zig | 210 +++++++++++++++++++++++++++++++++++++++++++++++++++ boot/serial.zig | 28 +++++++ 6 files changed, 367 insertions(+), 9 deletions(-) create mode 100644 boot/heap.zig create mode 100644 boot/pmm.zig (limited to 'boot') 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); +} -- cgit v1.3