diff options
| -rw-r--r-- | README.md | 2 | ||||
| -rw-r--r-- | boot/elf.zig | 1 | ||||
| -rw-r--r-- | boot/sched.zig | 49 | ||||
| -rw-r--r-- | boot/user.zig | 6 | ||||
| -rw-r--r-- | build.zig | 2 | ||||
| -rw-r--r-- | user/membrk.c | 93 | ||||
| -rw-r--r-- | user/user.h | 159 |
7 files changed, 311 insertions, 1 deletions
@@ -74,6 +74,8 @@ the syscall table | 7 | `open` | path | flags | | | fd or -1 | | 8 | `close` | fd | | | | 0 or -1 | | 9 | `lseek` | fd | offset | whence | | new offset | +| 10 | `brk` | addr | | | | new break or -1 | +| 11 | `sbrk` | inc | | | | old break or -1 | the three preopened fds diff --git a/boot/elf.zig b/boot/elf.zig index a6e621c..32acbfe 100644 --- a/boot/elf.zig +++ b/boot/elf.zig @@ -5,4 +5,5 @@ pub const programs = [_]Program{ .{ .name = "primes", .bytes = @embedFile("user_primes") }, .{ .name = "save", .bytes = @embedFile("user_save") }, .{ .name = "chat", .bytes = @embedFile("user_chat") }, + .{ .name = "membrk", .bytes = @embedFile("user_membrk") }, }; diff --git a/boot/sched.zig b/boot/sched.zig index 30d5698..4367fc0 100644 --- a/boot/sched.zig +++ b/boot/sched.zig @@ -3,6 +3,7 @@ const std = @import("std"); const Frame = @import("regs.zig").Frame; const vmm = @import("vmm.zig"); +const pmm = @import("pmm.zig"); const gdt = @import("gdt.zig"); const bridge = @import("bridge"); @@ -11,6 +12,9 @@ const KSTACK_SIZE = 16 * 1024; const MAX_FDS = 8; const MAX_PATH = 128; +// user heap lives here in the gap between the program and the arg/stack +const HEAP_BASE: u64 = 0x1000_0000; + const State = enum { free, ready, dead, blocked }; // file descriptor not "foid decimator" @@ -27,6 +31,8 @@ const Task = struct { cr3: u64 = 0, kstack_top: u64 = 0, // tss rsp0 for this task, 0 for the ring 0 kernel task state: State = .free, + brk_cur: u64 = 0, // the program break, top of the user heap + brk_top: u64 = 0, // first page above the break thats actually mapped }; var tasks: [MAX_TASKS]Task = @splat(.{}); @@ -75,12 +81,55 @@ pub fn spawn(cr3: u64, entry: u64, ustack: u64, arg: u64, arglen: u64) void { .cr3 = cr3, .kstack_top = @intFromPtr(&kstacks[i]) + KSTACK_SIZE, .state = .ready, + .brk_cur = HEAP_BASE, + .brk_top = HEAP_BASE, }; initFds(i); return; } } +const USER_PAGE: u64 = vmm.WRITE | vmm.USER; + +// map heap pages until everything below target is present +// false on oom +fn growHeap(t: *Task, target: u64) bool { + while (t.brk_top < target) { + const phys = pmm.alloc() orelse return false; + // zero it so we never hand ring 3 whatever the fuck was in that frame before + const page: [*]u8 = @ptrFromInt(pmm.physToVirt(phys)); + @memset(page[0..pmm.PAGE_SIZE], 0); + if (!vmm.map(t.cr3, t.brk_top, phys, USER_PAGE)) { + pmm.free(phys); + return false; + } + t.brk_top += pmm.PAGE_SIZE; + } + return true; +} + +// move the break to addr +pub fn brk(addr: u64) i64 { + if (current == 0 or addr < HEAP_BASE) return -1; + const t = &tasks[current]; + if (addr > t.brk_cur and !growHeap(t, addr)) return -1; + t.brk_cur = addr; + return @intCast(addr); +} + +// move the break by increment +pub fn sbrk(increment: i64) i64 { + if (current == 0) return -1; + const t = &tasks[current]; + const old = t.brk_cur; + const want: i64 = @as(i64, @intCast(old)) + increment; + if (want < @as(i64, @intCast(HEAP_BASE))) return -1; + const new_brk: u64 = @intCast(want); + if (new_brk > old and !growHeap(t, new_brk)) return -1; + t.brk_cur = new_brk; + return @intCast(old); +} + // stdin at keyboard fn initFds(i: usize) void { for (&fdtabs[i]) |*f| f.* = .{}; diff --git a/boot/user.zig b/boot/user.zig index 78d20ff..0cda97d 100644 --- a/boot/user.zig +++ b/boot/user.zig @@ -214,6 +214,12 @@ export fn syscallHandler(frame: *SyscallFrame) callconv(.c) void { const src: [*]const u8 = @ptrFromInt(frame.rsi); frame.rax = if (bridge.fsStore(name, src[0..len])) 1 else 0; }, + 10 => { // brk(addr) + frame.rax = @bitCast(sched.brk(frame.rdi)); + }, + 11 => { // sbrk(increment) + frame.rax = @bitCast(sched.sbrk(@bitCast(frame.rdi))); + }, else => serial.write("[syscall] unknown\r\n"), } } @@ -103,7 +103,7 @@ pub fn build(b: *std.Build) void { kernel.root_module.addAnonymousImport(e[0], .{ .root_source_file = b.path(e[1]) }); } - inline for (.{ "hexview", "calc", "primes", "save", "chat" }) |prog| { + inline for (.{ "hexview", "calc", "primes", "save", "chat", "membrk" }) |prog| { const cc = b.addSystemCommand(&.{ "zig", "cc", "-target", "x86_64-freestanding", diff --git a/user/membrk.c b/user/membrk.c new file mode 100644 index 0000000..f1949cc --- /dev/null +++ b/user/membrk.c @@ -0,0 +1,93 @@ +#include "user.h" + +static void check(const char* name, int ok) +{ + put(ok ? "ok " : "FAIL "); + put(name); + put("\n"); +} + +void _start(const char* arg, unsigned long arglen) +{ + (void)arg; + (void)arglen; + + long start = (long)sys_sbrk(0); + put("heap base: "); + put_int(start); + put("\n"); + + // obese alloc test + char* run[80]; + for (int i = 0; i < 80; i++) + run[i] = (char*)malloc(4000); + long run_after = (long)sys_sbrk(0); + for (int i = 0; i < 80; i++) + free(run[i]); + char* merged = (char*)malloc(80 * 4000 - 8000); + long merge_after = (long)sys_sbrk(0); + check("freed neighbours coalesce", merged != 0 && merge_after <= run_after); + free(merged); + + // a pile of small tagged allocations + char* blocks[16]; + for (int i = 0; i < 16; i++) + { + blocks[i] = (char*)malloc(64); + for (int j = 0; j < 64; j++) + blocks[i][j] = (char)(i * 7 + j); + } + int small_ok = 1; + for (int i = 0; i < 16; i++) + for (int j = 0; j < 64; j++) + if (blocks[i][j] != (char)(i * 7 + j)) + small_ok = 0; + check("small allocs keep their data", small_ok); + + // a big block spanning several pages written edge to edge + unsigned long big = 20000; + unsigned char* buffer = (unsigned char*)malloc(big); + for (unsigned long k = 0; k < big; k++) + buffer[k] = (unsigned char)(k & 0xff); + int big_ok = 1; + for (unsigned long k = 0; k < big; k++) + if (buffer[k] != (unsigned char)(k & 0xff)) + big_ok = 0; + check("big multi page alloc", big_ok); + + // testing that the the heap must doesnt grow across the loop + long churn_before = (long)sys_sbrk(0); + for (int i = 0; i < 2000; i++) + { + void* pointer = malloc(500); + free(pointer); + } + long churn_after = (long)sys_sbrk(0); + check("alloc/free churn reclaims (no growth)", churn_before == churn_after); + + // calloc dirty test + unsigned char* zeroed = (unsigned char*)calloc(200, 1); + int zero_ok = 1; + for (int i = 0; i < 200; i++) + if (zeroed[i] != 0) + zero_ok = 0; + check("calloc is zeroed", zero_ok); + + // realloc test + char* grown = (char*)malloc(32); + for (int i = 0; i < 32; i++) + grown[i] = (char)(i + 1); + grown = (char*)realloc(grown, 500); + int grow_ok = 1; + for (int i = 0; i < 32; i++) + if (grown[i] != (char)(i + 1)) + grow_ok = 0; + check("realloc grows and preserves data", grow_ok); + + long end = (long)sys_sbrk(0); + put("heap high water: "); + put_int(end - start); + put(" bytes\n"); + + sys_exit(0); +} diff --git a/user/user.h b/user/user.h index 34710ac..86c2f91 100644 --- a/user/user.h +++ b/user/user.h @@ -75,6 +75,165 @@ static long sys_fs_write(const char* name, const char* buffer, unsigned long len return result; } +static long sys_brk(void* addr) +{ + long result; + __asm__ volatile("int $0x80" : "=a"(result) : "a"(10L), "D"(addr) : "memory"); + return result; +} + +static void* sys_sbrk(long increment) +{ + long result; + __asm__ volatile("int $0x80" : "=a"(result) : "a"(11L), "D"(increment) : "memory"); + return (void*)result; +} + +// shitty heap implementation +// temporary af this will be in its own libc +#define HEAP_HDR 16UL +#define HEAP_ALIGN 16UL +#define HEAP_MIN 32UL +#define HEAP_CHUNK (64UL * 1024UL) + +static unsigned long heap_start = 0; +static unsigned long heap_end = 0; +static unsigned long heap_rover = 0; + +static unsigned long heap_blk_size(unsigned long b) +{ + return *(unsigned long*)b & ~15UL; +} + +static int heap_blk_used(unsigned long b) +{ + return (int)(*(unsigned long*)b & 1UL); +} + +static void heap_set(unsigned long b, unsigned long size, int used) +{ + *(unsigned long*)b = size | (used ? 1UL : 0UL); +} + +static unsigned long heap_align(unsigned long x) +{ + return (x + HEAP_ALIGN - 1UL) & ~(HEAP_ALIGN - 1UL); +} + +// pull another hunk off sbrk and drop a free block over it +static int heap_grow(unsigned long need) +{ + unsigned long want = heap_align(need); + if (want < HEAP_CHUNK) + want = HEAP_CHUNK; + unsigned long got = (unsigned long)sys_sbrk((long)want); + if ((long)got < 0) + return 0; + if (heap_start == 0) + { + heap_start = got; + heap_end = got; + heap_rover = got; + } + heap_set(heap_end, want, 0); + heap_end += want; + return 1; +} + +// yummy O(n) malloc implementation +static void* malloc(unsigned long len) +{ + if (len == 0) + return 0; + unsigned long need = heap_align(HEAP_HDR + len); + if (need < HEAP_MIN) + need = HEAP_MIN; + + for (;;) + { + if (heap_rover < heap_start || heap_rover >= heap_end) + heap_rover = heap_start; + unsigned long b = heap_rover; + unsigned long limit = heap_end; + for (int pass = 0; pass < 2; pass++) + { + while (b < limit) + { + if (!heap_blk_used(b)) + { + unsigned long size = heap_blk_size(b); + while (b + size < heap_end && !heap_blk_used(b + size)) + size += heap_blk_size(b + size); + heap_set(b, size, 0); + if (size >= need) + { + if (size >= need + HEAP_MIN) + { + heap_set(b, need, 1); + heap_set(b + need, size - need, 0); + heap_rover = b + need; + } + else + { + heap_set(b, size, 1); + heap_rover = b + size; + } + if (heap_rover >= heap_end) + heap_rover = heap_start; + return (void*)(b + HEAP_HDR); + } + } + b += heap_blk_size(b); + } + b = heap_start; + limit = heap_rover; + } + if (!heap_grow(need)) + return 0; + } +} + +static void free(void* ptr) +{ + if (ptr == 0) + return; + unsigned long b = (unsigned long)ptr - HEAP_HDR; + heap_set(b, heap_blk_size(b), 0); +} + +static void* calloc(unsigned long count, unsigned long size) +{ + unsigned long total = count * size; + unsigned char* p = (unsigned char*)malloc(total); + if (p) + for (unsigned long i = 0; i < total; i++) + p[i] = 0; + return p; +} + +static void* realloc(void* ptr, unsigned long len) +{ + if (ptr == 0) + return malloc(len); + if (len == 0) + { + free(ptr); + return 0; + } + unsigned long b = (unsigned long)ptr - HEAP_HDR; + unsigned long have = heap_blk_size(b) - HEAP_HDR; + if (len <= have) + return ptr; + unsigned char* np = (unsigned char*)malloc(len); + if (!np) + return 0; + unsigned char* src = (unsigned char*)ptr; + for (unsigned long i = 0; i < have; i++) + np[i] = src[i]; + free(ptr); + return np; +} + static void put(const char* string) { unsigned long length = 0; |