commit de8d6aa793a3b2a46ace986b7b1bb8cb0b9afa55
parent 84a5e94bfe9302b155316ede1df7a617a9b2513f
Author: Connor Thomson <connor@gnufault.org>
Date:   Sat, 31 Oct 2026 08:49:25 -0700

Add memory allocator

Diffstat:
M
sdk/include/stdlib.h
 | 
1
+
M
sdk/linker.ld
 | 
9
+++++++++
M
sdk/src/stdlib.c
 | 
259
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

3 files changed, 269 insertions(+), 0 deletions(-)
diff --git a/sdk/include/stdlib.h b/sdk/include/stdlib.h
@@ -7,6 +7,7 @@
 #include <stddef.h>
 
 void *malloc(size_t size);
+void *calloc(size_t count, size_t size);
 void *realloc(void *ptr, size_t size);
 void free(void *ptr);
 
diff --git a/sdk/linker.ld b/sdk/linker.ld
@@ -1,6 +1,10 @@
 OUTPUT_ARCH(riscv)
 ENTRY(_start)
 
+PROVIDE(__ram_size = 0x10000);
+PROVIDE(__stack_size = 0x2000);
+__heap_end = __ram_size - __stack_size;
+
 SECTIONS {
 	. = 0;
 
@@ -27,8 +31,13 @@ SECTIONS {
 	.bss : {
 		*(.bss .bss.* .sbss .sbss.* COMMON)
 	}
+
+	. = ALIGN(8);
+	__heap_start = .;
 	
 	/DISCARD/ : {
 		*
 	}
+
+	ASSERT(__heap_start + 64 <= __heap_end, "no room left for heap")
 }
diff --git a/sdk/src/stdlib.c b/sdk/src/stdlib.c
@@ -0,0 +1,259 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+#include <stddef.h>
+
+#define HEAP_ALIGNMENT  8u
+#define HEADER_SIZE     8u
+#define MIN_BLOCK       16u
+#define MAX_REQUEST     0x7FFFFFF0u
+#define USED_MAGIC      0xA110C8EDu
+
+typedef struct free_block free_block;
+
+struct free_block {
+	uint32_t size;
+	uint32_t used;
+	free_block *next;
+};
+
+extern uint8_t __heap_start[];
+extern uint8_t __heap_end[];
+
+static free_block *free_list;
+static uint8_t *heap_low;
+static uint8_t *heap_high;
+static uint32_t heap_ready;
+
+static size_t align_up(size_t value) {
+	return (value + (HEAP_ALIGNMENT - 1)) & ~(size_t)(HEAP_ALIGNMENT - 1);
+}
+
+static uint32_t request_to_block(size_t size) {
+	uint32_t block = (uint32_t)align_up(size) + HEADER_SIZE;
+
+	return block < MIN_BLOCK ? MIN_BLOCK : block;
+}
+
+static void heap_init(void) {
+	size_t start = align_up((size_t)__heap_start);
+	size_t end = (size_t)__heap_end & ~(size_t)(HEAP_ALIGNMENT - 1);
+
+	heap_ready = 1;
+	free_list = NULL;
+	heap_low = (uint8_t *)start;
+	heap_high = (uint8_t *)end;
+
+	if (end < start + MIN_BLOCK) {
+		return;
+	}
+
+	free_block *block = (free_block *)start;
+
+	block->size = (uint32_t)(end - start);
+	block->used = 0;
+	block->next = NULL;
+	free_list = block;
+}
+
+static void release(free_block *block) {
+	free_block *previous = NULL;
+	free_block *current = free_list;
+
+	block->used = 0;
+
+	while (current != NULL && current < block) {
+		previous = current;
+		current = current->next;
+	}
+
+	block->next = current;
+
+	if (previous != NULL) {
+		previous->next = block;
+	} else {
+		free_list = block;
+	}
+
+	if (current != NULL && (uint8_t *)block + block->size == (uint8_t *)current) {
+		block->size += current->size;
+		block->next = current->next;
+	}
+
+	if (previous != NULL && (uint8_t *)previous + previous->size == (uint8_t *)block) {
+		previous->size += block->size;
+		previous->next = block->next;
+	}
+}
+
+static void unlink_block(free_block *target) {
+	free_block **link = &free_list;
+
+	while (*link != NULL) {
+		if (*link == target) {
+			*link = target->next;
+
+			return;
+		}
+
+		link = &(*link)->next;
+	}
+}
+
+static void trim(free_block *block, uint32_t need) {
+	if (block->size - need < MIN_BLOCK) {
+		return;
+	}
+
+	free_block *tail = (free_block *)((uint8_t *)block + need);
+
+	tail->size = block->size - need;
+	block->size = need;
+
+	release(tail);
+}
+
+static free_block *block_from_pointer(void *pointer) {
+	if (!heap_ready) {
+		return NULL;
+	}
+
+	uint8_t *address = (uint8_t *)pointer;
+
+	if (address < heap_low + HEADER_SIZE || address >= heap_high) {
+		return NULL;
+	}
+
+	if (((size_t)address & (HEAP_ALIGNMENT - 1)) != 0) {
+		return NULL;
+	}
+
+	free_block *block = (free_block *)(address - HEADER_SIZE);
+
+	if (block->used != USED_MAGIC) {
+		return NULL;
+	}
+
+	return block;
+}
+
+void *malloc(size_t size) {
+	if (!heap_ready) {
+		heap_init();
+	}
+
+	if (size == 0 || size > MAX_REQUEST) {
+		return NULL;
+	}
+
+	uint32_t need = request_to_block(size);
+	free_block *best = NULL;
+
+	for (free_block *current = free_list; current != NULL; current = current->next) {
+		if (current->size < need) {
+			continue;
+		}
+
+		if (best == NULL || current->size < best->size) {
+			best = current;
+
+			if (current->size == need) {
+				break;
+			}
+		}
+	}
+
+	if (best == NULL) {
+		return NULL;
+	}
+
+	unlink_block(best);
+	trim(best, need);
+	best->used = USED_MAGIC;
+
+	return (uint8_t *)best + HEADER_SIZE;
+}
+
+void free(void *pointer) {
+	if (pointer == NULL) {
+		return;
+	}
+
+	free_block *block = block_from_pointer(pointer);
+
+	if (block == NULL) {
+		return;
+	}
+
+	release(block);
+}
+
+void *calloc(size_t count, size_t size) {
+	if (size != 0 && count > MAX_REQUEST / size) {
+		return NULL;
+	}
+
+	size_t total = count * size;
+	void *pointer = malloc(total);
+
+	if (pointer != NULL) {
+		memset(pointer, 0, total);
+	}
+
+	return pointer;
+}
+
+void *realloc(void *pointer, size_t size) {
+	if (pointer == NULL) {
+		return malloc(size);
+	}
+
+	free_block *block = block_from_pointer(pointer);
+
+	if (block == NULL) {
+		return NULL;
+	}
+
+	if (size == 0) {
+		free(pointer);
+
+		return NULL;
+	}
+
+	if (size > MAX_REQUEST) {
+		return NULL;
+	}
+
+	uint32_t need = request_to_block(size);
+
+	if (need <= block->size) {
+		trim(block, need);
+
+		return pointer;
+	}
+
+	free_block *neighbor = free_list;
+
+	while (neighbor != NULL && (uint8_t *)neighbor < (uint8_t *)block + block->size) {
+		neighbor = neighbor->next;
+	}
+
+	if (neighbor != NULL && (uint8_t *)neighbor == (uint8_t *)block + block->size && block->size + neighbor->size >= need) {
+		unlink_block(neighbor);
+		block->size += neighbor->size;
+		trim(block, need);
+
+		return pointer;
+	}
+
+	void *grown = malloc(size);
+
+	if (grown == NULL) {
+		return NULL;
+	}
+
+	memcpy(grown, pointer, block->size - HEADER_SIZE);
+	free(pointer);
+
+	return grown;
+}