Started new heap implementation (not working yet)

5 files changed, 238 insertions, 83 deletions

diff --git a/kernel/features/proc.c b/kernel/features/proc.c
index d76312c..c0216bc 100644
--- a/kernel/features/proc.c
+++ b/kernel/features/proc.c
@@ -142,6 +142,8 @@ void proc_exit(struct proc *proc, int status)
 		printf("Process %s exited with status %d\n", proc->name, status);
 
 	quantum = 0; // TODO: Add quantum to each process struct?
+	sti();
+	hlt();
 }
 
 void proc_yield(struct regs *r)
diff --git a/kernel/main.c b/kernel/main.c
index 563cae7..665d474 100644
--- a/kernel/main.c
+++ b/kernel/main.c
@@ -11,6 +11,7 @@
 #include <mouse.h>
 #include <net.h>
 #include <pci.h>
+#include <print.h>
 #include <serial.h>
 #include <syscall.h>
 #include <timer.h>
diff --git a/libc/inc/assert.h b/libc/inc/assert.h
index 3e45f44..e42fc5a 100644
--- a/libc/inc/assert.h
+++ b/libc/inc/assert.h
@@ -9,7 +9,8 @@
 #include <proc.h>
 #define assert(exp)                                                                                \
 	if (!(exp)) {                                                                              \
-		printf("%s:%d: %s: Assertion '%s' failed\n", __FILE__, __LINE__, __func__, #exp);  \
+		printf("%s:%d: %s: Kernel assertion '%s' failed\n", __FILE__, __LINE__, __func__,  \
+		       #exp);                                                                      \
 		struct proc *assert_proc = proc_current();                                         \
 		if (assert_proc)                                                                   \
 			proc_exit(assert_proc, 1);                                                 \
diff --git a/libc/inc/mem.h b/libc/inc/mem.h
index 15505fd..9075736 100644
--- a/libc/inc/mem.h
+++ b/libc/inc/mem.h
@@ -7,12 +7,11 @@
 
 // Huh
 #ifdef kernel
-#define HEAP_SIZE 0x10000
-#define HEAP_MAGIC 0x42
 void heap_init(u32 start);
 void *malloc(u32 size);
 void free(void *ptr);
 #elif defined(userspace)
+#include <print.h>
 void *malloc(u32 size);
 void free(void *ptr);
 #else
diff --git a/libc/mem.c b/libc/mem.c
index dc4e0e6..8c81ad4 100644
--- a/libc/mem.c
+++ b/libc/mem.c
@@ -1,5 +1,6 @@
 // MIT License, Copyright (c) 2020 Marvin Borner
 
+#include <assert.h>
 #include <def.h>
 #include <mem.h>
 #include <sys.h>
@@ -68,126 +69,277 @@ int memcmp(const void *s1, const void *s2, u32 n)
 	return 0;
 }
 
-#define ALIGNMENT 16ul
-#define ALIGN_TYPE char
-#define ALIGN_INFO sizeof(ALIGN_TYPE) * 16
+/**
+ * Heap allocator
+ */
 
-#define ALIGN(ptr)                                                                                 \
-	if (ALIGNMENT > 1) {                                                                       \
-		u32 diff;                                                                          \
-		ptr = (void *)((u32)ptr + ALIGN_INFO);                                             \
-		diff = (u32)ptr & (ALIGNMENT - 1);                                                 \
-		if (diff != 0) {                                                                   \
-			diff = ALIGNMENT - diff;                                                   \
-			ptr = (void *)((u32)ptr + diff);                                           \
-		}                                                                                  \
-		*((ALIGN_TYPE *)((u32)ptr - ALIGN_INFO)) = diff + ALIGN_INFO;                      \
-	}
+#ifdef kernel
 
-#define UNALIGN(ptr)                                                                               \
-	if (ALIGNMENT > 1) {                                                                       \
-		u32 diff = *((ALIGN_TYPE *)((u32)ptr - ALIGN_INFO));                               \
-		if (diff < (ALIGNMENT + ALIGN_INFO)) {                                             \
-			ptr = (void *)((u32)ptr - diff);                                           \
-		}                                                                                  \
+#define HEAP_INIT_SIZE 0xff000000
+#define HEAP_MIN_SIZE HEAP_INIT_SIZE
+#define MIN_ALLOC_SZ 4
+#define BIN_COUNT 9
+#define BIN_MAX_IDX (BIN_COUNT - 1)
+#define OVERHEAD (sizeof(struct h_footer) + sizeof(struct h_node))
+/* #define MIN_WILDERNESS 0x2000 */
+/* #define MAX_WILDERNESS 0x1000000 */
+
+struct h_node {
+	u32 hole;
+	u32 size;
+	struct h_node *next;
+	struct h_node *prev;
+};
+
+struct h_footer {
+	struct h_node *header;
+};
+
+struct h_bin {
+	struct h_node *head;
+};
+
+struct heap {
+	u32 start;
+	u32 end;
+	struct h_bin bins[BIN_COUNT];
+};
+
+void node_add(struct h_bin *bin, struct h_node *node)
+{
+	node->next = NULL;
+	node->prev = NULL;
+	if (!bin->head) {
+		bin->head = node;
+		return;
+	}
+	struct h_node *curr = bin->head;
+	struct h_node *prev = NULL;
+	while (curr && curr->size <= node->size) {
+		prev = curr;
+		curr = curr->next;
 	}
+	if (!curr) {
+		prev->next = node;
+		node->prev = prev;
+	} else if (prev) {
+		node->next = curr;
+		prev->next = node;
+		node->prev = prev;
+		curr->prev = node;
+	} else {
+		node->next = bin->head;
+		bin->head->prev = node;
+		bin->head = node;
+	}
+}
 
-#ifdef kernel
+void node_remove(struct h_bin *bin, struct h_node *node)
+{
+	if (!bin->head)
+		return;
+	if (bin->head == node) {
+		bin->head = bin->head->next;
+		return;
+	}
 
-static u32 *heap;
-static u32 index;
+	struct h_node *temp = bin->head->next;
+	while (temp) {
+		if (temp == node) {
+			if (!temp->next) {
+				temp->prev->next = NULL;
+			} else {
+				temp->prev->next = temp->next;
+				temp->next->prev = temp->prev;
+			}
+			return;
+		}
+		temp = temp->next;
+	}
+}
 
-void heap_init(u32 start)
+struct h_node *node_best_fit(struct h_bin *bin, u32 size)
 {
-	heap = (u32 *)start;
-	for (int i = 0; i < HEAP_SIZE; i++)
-		heap[i] = 0;
-	heap[0] = HEAP_MAGIC;
-	index = 1;
+	if (!bin->head)
+		return NULL;
+
+	struct h_node *temp = bin->head;
+	while (temp) {
+		if (temp->size >= size)
+			return temp;
+		temp = temp->next;
+	}
+	return NULL;
 }
 
-int count()
+struct h_node *node_last(struct h_bin *bin)
 {
-	int i = 0;
-	u32 *iterator = heap + 1;
-	do {
-		iterator += iterator[0] + 1;
-		i++;
-	} while (iterator[0] != 0);
-	return i;
+	struct h_node *temp = bin->head;
+	while (temp->next)
+		temp = temp->next;
+	return temp;
 }
 
-// TODO: Identify by pid (for freeing)
-void *malloc(u32 size)
+struct h_footer *node_foot(struct h_node *node)
 {
-	if (size < 1)
-		return NULL;
+	return (struct h_footer *)((char *)node + sizeof(*node) + node->size);
+}
 
-	size = size + ALIGNMENT + ALIGN_INFO;
+void node_create_foot(struct h_node *head)
+{
+	struct h_footer *foot = node_foot(head);
+	foot->header = head;
+}
 
-	heap[index] = size;
-	index += size + 1;
+u32 bin_index(u32 sz)
+{
+	u32 index = 0;
+	sz = sz < 4 ? 4 : sz;
+	while (sz >>= 1)
+		index++;
+	index -= 2;
+	if (index > BIN_MAX_IDX)
+		index = BIN_MAX_IDX;
+	return index;
+}
 
-	void *p = (void *)(heap + index - size);
-	ALIGN(p);
+/* struct h_node *wilderness_get(struct heap *heap) */
+/* { */
+/* 	struct h_footer *wild_foot = (struct h_footer *)((char *)heap->end - sizeof(*wild_foot)); */
+/* 	return wild_foot->header; */
+/* } */
 
-	return p;
+u32 expand(struct heap *heap, u32 sz)
+{
+	(void)heap;
+	(void)sz;
+	return 0;
 }
 
-// TODO: Implement free, realloc and find_smallest_hole
-void free(void *ptr)
+u32 contract(struct heap *heap, u32 sz)
 {
-	(void)ptr;
-	/* UNALIGN(ptr); */
+	(void)heap;
+	(void)sz;
+	return 0;
 }
 
-void *realloc(void *ptr, u32 size)
+static struct heap heap = { 0 };
+void heap_init(u32 start)
 {
-	(void)size;
-	return ptr;
+	struct h_node *init_region = (struct h_node *)start;
+	init_region->hole = 1;
+	init_region->size = HEAP_INIT_SIZE - OVERHEAD;
+	node_create_foot(init_region);
+	node_add(&heap.bins[bin_index(init_region->size)], init_region);
+	heap.start = start;
+	heap.end = start + HEAP_INIT_SIZE;
 }
 
-#elif defined(userspace)
+void *malloc(u32 size)
+{
+	u32 index = bin_index(size);
+	struct h_bin *temp = (struct h_bin *)&heap.bins[index];
+	struct h_node *found = node_best_fit(temp, size);
 
-#define HEAP_SIZE 100000
+	while (!found) {
+		assert(index + 1 < BIN_COUNT);
 
-#define kmalloc(n) (void *)sys1(SYS_MALLOC, n)
-#define kfree(ptr) (void)(sys1(SYS_FREE, (int)ptr))
+		temp = &heap.bins[++index];
+		found = node_best_fit(temp, size);
+	}
 
-/* static u32 *heap = NULL; */
-/* static u32 index = 0; */
-/* static u32 malloced = 0; */
+	if ((found->size - size) > (OVERHEAD + MIN_ALLOC_SZ)) {
+		struct h_node *split = (struct h_node *)(((char *)found + OVERHEAD) + size);
+		split->size = found->size - size - OVERHEAD;
+		split->hole = 1;
 
-// TODO: Fix userspace malloc (for size > HEAP_SIZE)!
-void *malloc(u32 size)
-{
-	return kmalloc(size);
+		node_create_foot(split);
+
+		u32 new_idx = bin_index(split->size);
 
-	/* if (size < 1) */
-	/* 	return NULL; */
+		node_add(&heap.bins[new_idx], split);
+
+		found->size = size;
+		node_create_foot(found);
+	}
 
-	/* size = size + ALIGNMENT + ALIGN_INFO; */
+	found->hole = 0;
+	node_remove(&heap.bins[index], found);
 
-	/* if (!malloced || size > malloced) { */
-	/* 	heap = kmalloc(HEAP_SIZE); */
-	/* 	malloced = HEAP_SIZE; */
+	// TODO: Implement expand/contract
+	/* struct h_node *wild = wilderness_get(&heap); */
+	/* if (wild->size < MIN_WILDERNESS) { */
+	/* 	assert(expand(&heap, 0x1000)); */
+	/* } else if (wild->size > MAX_WILDERNESS) { */
+	/* 	assert(contract(&heap, 0x1000)); */
 	/* } */
-	/* malloced -= size; */
 
-	/* heap[index] = size; */
-	/* index += size + 1; */
+	found->prev = NULL;
+	found->next = NULL;
+	return &found->next;
+}
+
+void free(void *p)
+{
+	struct h_bin *list;
+	struct h_footer *new_foot, *old_foot;
+
+	struct h_node *head = (struct h_node *)((char *)p - 8);
+	if (head == (struct h_node *)(u32 *)heap.start) {
+		head->hole = 1;
+		node_add(&heap.bins[bin_index(head->size)], head);
+		return;
+	}
 
-	/* void *p = (void *)(heap + index - size); */
-	/* ALIGN(p); */
+	struct h_node *next = (struct h_node *)((char *)node_foot(head) + sizeof(struct h_footer));
+	struct h_footer *f = (struct h_footer *)((char *)head - sizeof(struct h_footer));
+	struct h_node *prev = f->header;
+
+	if (prev->hole) {
+		list = &heap.bins[bin_index(prev->size)];
+		node_remove(list, prev);
+
+		prev->size += OVERHEAD + head->size;
+		new_foot = node_foot(head);
+		new_foot->header = prev;
+
+		head = prev;
+	}
 
-	/* return p; */
+	if (next->hole) {
+		list = &heap.bins[bin_index(next->size)];
+		node_remove(list, next);
+
+		head->size += OVERHEAD + next->size;
+
+		old_foot = node_foot(next);
+		old_foot->header = 0;
+		next->size = 0;
+		next->hole = 0;
+
+		new_foot = node_foot(head);
+		new_foot->header = head;
+	}
+
+	head->hole = 1;
+	node_add(&heap.bins[bin_index(head->size)], head);
+}
+
+#elif defined(userspace)
+
+#define kmalloc(n) (void *)sys1(SYS_MALLOC, n)
+#define kfree(ptr) (void)(sys1(SYS_FREE, (int)ptr))
+
+static u32 total = 0;
+void *malloc(u32 size)
+{
+	total += size;
+	return kmalloc(size);
 }
 
-// TODO: Implement free, realloc and find_smallest_hole
 void free(void *ptr)
 {
-	(void)ptr;
-	/* UNALIGN(ptr); */
+	kfree(ptr);
 }
 
 #endif