From 52dab7fc85d877e80e3032f0afabae906adebad8 Mon Sep 17 00:00:00 2001 From: hachem Date: Sun, 4 Oct 2026 16:03:42 +0200 Subject: feat: fs tree and free list alloc --- boot/boot.zig | 38 +++++++++++++++++++--- boot/elf.zig | 1 + boot/heap.zig | 100 ++++++++++++++++++++++++++++++++++++++++++++++----------- boot/sched.zig | 41 ++++++++++++----------- boot/user.zig | 18 +++++++---- 5 files changed, 150 insertions(+), 48 deletions(-) (limited to 'boot') diff --git a/boot/boot.zig b/boot/boot.zig index 5a3c429..fff8a6b 100644 --- a/boot/boot.zig +++ b/boot/boot.zig @@ -39,7 +39,7 @@ pub const panic = std.debug.FullPanic(struct { // console and shit pub const std_options_debug_io: std.Io = bridge.debug_io; -// check `linker.ld` +// note: check `linker.ld` export var base_revision: limine.BaseRevision linksection(".limine_requests") = limine.BaseRevision.init(3); export var requests_start: limine.RequestsStartMarker linksection(".limine_requests_start") = .{}; export var requests_end: limine.RequestsEndMarker linksection(".limine_requests_end") = .{}; @@ -70,33 +70,42 @@ fn kSerialNext() i64 { // read only kernel state exposed to revo so it can present it (mem/uptime/ps and // the memory map dump live in revo now) var g_memmap: ?*const limine.MemoryMapResponse = null; + fn kMemmapCount() u64 { const mm = g_memmap orelse return 0; return mm.entry_count; } + fn memmapEntry(i: u64) ?*const limine.MemoryMapEntry { const mm = g_memmap orelse return null; if (i >= mm.entry_count) return null; return mm.entries.?[i]; } + fn kMemmapBase(i: u64) u64 { return if (memmapEntry(i)) |e| e.base else 0; } + fn kMemmapLen(i: u64) u64 { return if (memmapEntry(i)) |e| e.length else 0; } + fn kMemmapKind(i: u64) u64 { return if (memmapEntry(i)) |e| @intFromEnum(e.type) else 0; } + fn kMemFree() u64 { return pmm.freeBytes(); } + fn kMemTotal() u64 { return pmm.usableBytes(); } + fn kUptime() u64 { return timer.now(); } + fn kProcCount() u64 { return sched.procCount(); } @@ -104,16 +113,18 @@ fn kProcCount() u64 { fn kDiskSectors() u64 { return ata.sectorCount(); } + fn kDiskRead(lba: u64, phys: u64) u64 { const buf: *[ata.SECTOR]u8 = @ptrFromInt(pmm.physToVirt(phys)); return if (ata.read(@truncate(lba), buf)) 1 else 0; } + fn kDiskWrite(lba: u64, phys: u64) u64 { const buf: *const [ata.SECTOR]u8 = @ptrFromInt(pmm.physToVirt(phys)); return if (ata.write(@truncate(lba), buf)) 1 else 0; } -// the embedded programs, copied to frames at boot so revo can load them by name +// the embedded programs const Prog = struct { name: []const u8, phys: u64, size: u64 }; var g_progs: [elf.programs.len]Prog = undefined; @@ -129,13 +140,27 @@ fn loadPrograms() void { fn kProgCount() u64 { return g_progs.len; } + fn kProgPhys(i: u64) u64 { return g_progs[i].phys; } + fn kProgName(i: u64) []const u8 { return g_progs[i].name; } +fn kProgSize(i: u64) u64 { + return g_progs[i].size; +} + +fn kTaskMax() u64 { + return sched.taskMax(); +} + +fn kTaskState(i: u64) u64 { + return sched.taskState(i); +} + // entry(_start) export fn _start() callconv(.c) noreturn { serial.init(); @@ -186,6 +211,9 @@ export fn _start() callconv(.c) noreturn { .prog_count = &kProgCount, .prog_phys = &kProgPhys, .prog_name = &kProgName, + .prog_size = &kProgSize, + .task_max = &kTaskMax, + .task_state = &kTaskState, .disk_sectors = &kDiskSectors, .disk_read = &kDiskRead, .disk_write = &kDiskWrite, @@ -252,9 +280,9 @@ fn vmmSelfTest() void { serial.write("vmm test: switched back OK\r\n"); } -// sleep until an interrupt, then drain the keyboard / tick and repeat. this is -// scheduler task 0. the cli/pop/sti hlt dance closes the lost wakeup race (a key -// arriving between "queue empty" and hlt would otherwise sit until the next one) +// 1- sleep until an interrupt +// 2- then drain the keyboard / tick +// 3- repeat fn eventLoop() noreturn { var last_ticks: u64 = 0; while (true) { diff --git a/boot/elf.zig b/boot/elf.zig index 51dc107..2070db6 100644 --- a/boot/elf.zig +++ b/boot/elf.zig @@ -3,4 +3,5 @@ pub const programs = [_]Program{ .{ .name = "hexview", .bytes = @embedFile("user_hexview") }, .{ .name = "calc", .bytes = @embedFile("user_calc") }, .{ .name = "primes", .bytes = @embedFile("user_primes") }, + .{ .name = "save", .bytes = @embedFile("user_save") }, }; diff --git a/boot/heap.zig b/boot/heap.zig index a845f60..badf506 100644 --- a/boot/heap.zig +++ b/boot/heap.zig @@ -1,34 +1,98 @@ -// 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 -// well 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 +// freelist allocator type shit const std = @import("std"); const pmm = @import("pmm.zig"); const serial = @import("serial.zig"); -// 32 mib -// note: bump if the vm needs more -const HEAP_PAGES: usize = 8192; +const HEAP_PAGES: usize = 16384; // 64 mib +const HEADER: usize = 16; // keeps payloads 16 aligned +const ALIGN: usize = 16; +const MIN_BLOCK: usize = 32; // header + a usable scrap, dont split below this -var fba: std.heap.FixedBufferAllocator = undefined; +var heap_start: usize = 0; +var heap_end: usize = 0; + +inline fn word(b: usize) *usize { + return @ptrFromInt(b); +} +inline fn blkSize(b: usize) usize { + return word(b).* & ~@as(usize, 0xf); +} +inline fn blkUsed(b: usize) bool { + return (word(b).* & 1) != 0; +} +inline fn setBlk(b: usize, size: usize, used: bool) void { + word(b).* = size | @as(usize, if (used) 1 else 0); +} +inline fn alignUp(x: usize, a: usize) usize { + return (x + a - 1) & ~(a - 1); +} 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]); + heap_start = pmm.physToVirt(phys); + const total = HEAP_PAGES * pmm.PAGE_SIZE; + heap_end = heap_start + total; + setBlk(heap_start, total, false); // start as one big free block serial.write("heap: "); - serial.writeDec((HEAP_PAGES * pmm.PAGE_SIZE) / (1024 * 1024)); - serial.write(" MiB at "); - serial.writeHex(virt); + serial.writeDec(total / (1024 * 1024)); + serial.write(" MiB free-list at "); + serial.writeHex(heap_start); serial.write("\r\n"); } +fn allocImpl(_: *anyopaque, len: usize, alignment: std.mem.Alignment, _: usize) ?[*]u8 { + // we only guarantee 16 byte payload alignment + // anything else can like actually go fuck itself + if (alignment.toByteUnits() > ALIGN) return null; + const need = alignUp(HEADER + len, ALIGN); + + var b = heap_start; + while (b < heap_end) { + if (!blkUsed(b)) { + // lazy coalesce + var size = blkSize(b); + while (b + size < heap_end and !blkUsed(b + size)) size += blkSize(b + size); + setBlk(b, size, false); + + if (size >= need) { + if (size >= need + MIN_BLOCK) { + setBlk(b, need, true); + setBlk(b + need, size - need, false); // the leftover tail + } else { + setBlk(b, size, true); + } + return @ptrFromInt(b + HEADER); + } + } + b += blkSize(b); + } + return null; +} + +fn freeImpl(_: *anyopaque, buf: []u8, _: std.mem.Alignment, _: usize) void { + const b = @intFromPtr(buf.ptr) - HEADER; + setBlk(b, blkSize(b), false); +} + +fn resizeImpl(_: *anyopaque, buf: []u8, _: std.mem.Alignment, new_len: usize, _: usize) bool { + const b = @intFromPtr(buf.ptr) - HEADER; + return new_len <= blkSize(b) - HEADER; +} + +fn remapImpl(ctx: *anyopaque, buf: []u8, alignment: std.mem.Alignment, new_len: usize, ra: usize) ?[*]u8 { + if (resizeImpl(ctx, buf, alignment, new_len, ra)) return buf.ptr; + return null; +} + +const vtable = std.mem.Allocator.VTable{ + .alloc = allocImpl, + .resize = resizeImpl, + .remap = remapImpl, + .free = freeImpl, +}; + pub fn allocator() std.mem.Allocator { - return fba.allocator(); + return .{ .ptr = undefined, .vtable = &vtable }; } diff --git a/boot/sched.zig b/boot/sched.zig index 0857abe..1842309 100644 --- a/boot/sched.zig +++ b/boot/sched.zig @@ -1,8 +1,4 @@ -// tiny preemptive round robin scheduler. a task is a saved frame + cr3 + kernel -// stack, task 0 is the kernel event loop. the pit tick swaps the interrupted -// frame for the next ready tasks and iretqs in, which covers ring 0 and ring 3 -// alike. each task has its own kernel stack so preempting one mid syscall (e.g. a -// read() parked on sti/hlt) doesnt clobber anothers rsp0 +// tiny preemptive shitty round robin scheduler const std = @import("std"); const Frame = @import("regs.zig").Frame; @@ -25,7 +21,6 @@ const Task = struct { var tasks: [MAX_TASKS]Task = @splat(.{}); var kstacks: [MAX_TASKS][KSTACK_SIZE]u8 align(16) = undefined; var current: usize = 0; -var spawn_count: u64 = 0; var blocked_reader: ?usize = null; var foreground: ?usize = null; @@ -45,13 +40,13 @@ fn stdinPop() ?u8 { return byte; } -// task 0 = the kernel/event loop, running in whatever cr3 boot set up +// task 0 = the kernel/event loop running in whatever cr3 boot set up pub fn init(kernel_cr3: u64) void { tasks[0] = .{ .cr3 = kernel_cr3, .state = .ready, .kstack_top = 0 }; current = 0; } -pub fn spawn(cr3: u64, entry: u64, ustack: u64) void { +pub fn spawn(cr3: u64, entry: u64, ustack: u64, arg: u64, arglen: u64) void { var i: usize = 1; while (i < MAX_TASKS) : (i += 1) { if (tasks[i].state != .free) continue; @@ -61,8 +56,8 @@ pub fn spawn(cr3: u64, entry: u64, ustack: u64) void { f.rflags = 0x202; // reserved bit + if=1, so its preemptible f.rsp = ustack; f.ss = 0x23; // user data (0x20) | rpl 3 - f.rdi = spawn_count; - spawn_count += 1; + f.rdi = arg; // _start(arg_ptr, arg_len), the sysv first two args + f.rsi = arglen; tasks[i] = .{ .frame = f, .cr3 = cr3, @@ -82,14 +77,24 @@ pub fn procCount() u64 { return count; } +// task table size + per slot state +// state is 0 free, 1 ready, 2 dead, 3 blocked +pub fn taskMax() u64 { + return MAX_TASKS; +} +pub fn taskState(i: u64) u64 { + if (i >= MAX_TASKS) return 0; + return @intFromEnum(tasks[i].state); +} + var proc_exited_flag: bool = false; -// mark the running process dead. it then sti+hlts +// mark the running process dead then sti+hlts pub fn exitCurrent() void { if (current != 0) { tasks[current].state = .dead; - proc_exited_flag = true; // the kernel task reprints the prompt on seeing this - if (foreground == current) { // hand keyboard back to the shell + proc_exited_flag = true; + if (foreground == current) { foreground = null; stdin_head = 0; stdin_tail = 0; @@ -117,7 +122,7 @@ pub fn blockCurrentOnRead(resume_frame: Frame) void { pub fn deliverInput(byte: u8) bool { if (blocked_reader) |task| { - tasks[task].frame.rax = byte; // read()s return value + tasks[task].frame.rax = byte; tasks[task].state = .ready; blocked_reader = null; return true; @@ -133,11 +138,11 @@ pub fn tick(frame: *Frame) void { if (bridge.vmBusy()) return; if (tasks[current].state == .dead) { - tasks[current].state = .free; // reclaim, dont bother saving its context + tasks[current].state = .free; } else if (tasks[current].state == .blocked) { - // keep the resume frame saved by blockcurrentonread, dont clobber it you bitch + // dont clobber it you bitch } else { - tasks[current].frame = frame.*; // freeze the current task + tasks[current].frame = frame.*; } var next = current; @@ -150,7 +155,7 @@ pub fn tick(frame: *Frame) void { break; } } - + if (tasks[current].state != .ready and next == current) next = 0; if (next == current) return; diff --git a/boot/user.zig b/boot/user.zig index 5ba6604..9bce9e9 100644 --- a/boot/user.zig +++ b/boot/user.zig @@ -8,8 +8,7 @@ const regs = @import("regs.zig"); const bridge = @import("bridge"); const Frame = regs.Frame; -// scratch for a filename copied out of the caller. one static buffer is fine, -// syscalls run one at a time (if=0) +// scratch for a filename copied out of the caller legit one static buffer is fine var name_buf: [64]u8 = undefined; fn userName(ptr: u64) []const u8 { const p: [*]const u8 = @ptrFromInt(ptr); @@ -18,9 +17,6 @@ fn userName(ptr: u64) []const u8 { return name_buf[0..i]; } -// what the syscall stub leaves on the stack: the gp regs it pushed, then the -// frame the cpu pushed on int 0x80. rax holds the syscall number in, and the -// handler writes the return value back into it (restored by the stubs pop) pub const SyscallFrame = extern struct { r15: u64, r14: u64, @@ -49,8 +45,10 @@ pub fn installSyscall() void { idt.setGate(0x80, @intFromPtr(&syscallStub), 3, 1); // ist1: big stack for vm calls } -// save gp regs, hand the frame to the zig handler, restore, iretq. the handler -// returns via syscallframe.rax (restored by the pop below), exit() never returns +// 1- save gp regs +// 2- hand the frame to the zig handler +// 3- restore +// 4- iretq export fn syscallStub() callconv(.naked) void { asm volatile (regs.PUSH_GPRS ++ \\ @@ -120,6 +118,12 @@ export fn syscallHandler(frame: *SyscallFrame) callconv(.c) void { const dst: [*]u8 = @ptrFromInt(frame.rdx); frame.rax = bridge.fsReadInto(name, frame.rsi, dst[0..len]); }, + 6 => { // fs_write(name_ptr, buf_ptr, len): returns 1 ok / 0 fail + const len = @min(frame.rdx, 64 * 1024); + const name = userName(frame.rdi); + const src: [*]const u8 = @ptrFromInt(frame.rsi); + frame.rax = if (bridge.fsStore(name, src[0..len])) 1 else 0; + }, else => serial.write("[syscall] unknown\r\n"), } } -- cgit v1.3