feat: brk/sbrk syscalls + shitty heap

2 files changed, 252 insertions, 0 deletions

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;