diff options
Diffstat (limited to 'user')
| -rw-r--r-- | user/membrk.c | 93 | ||||
| -rw-r--r-- | user/user.h | 159 |
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; |