Replaced alloc.h with liballoc

And many more adaptions to the lib

1 files changed, 418 insertions, 132 deletions

diff --git a/src/kernel/memory/alloc.c b/src/kernel/memory/alloc.c
index bd4ecb3..d94e482 100644
--- a/src/kernel/memory/alloc.c
+++ b/src/kernel/memory/alloc.c
@@ -1,3 +1,4 @@
+#include <io/io.h>
 #include <lib/lib.h>
 #include <memory/alloc.h>
 #include <memory/paging.h>
@@ -5,192 +6,477 @@
 #include <stdint.h>
 #include <system.h>
 
-extern u32 end;
-u32 placement_address;
+static int locked = 0;
 
-struct heap_header *kheap = NULL;
-struct heap_header *uheap = NULL;
+int liballoc_lock()
+{
+	spinlock(locked);
+	return 0;
+}
 
-void kheap_init()
+int liballoc_unlock()
 {
-	end = &end;
-	placement_address = end;
-	kheap = (struct heap_header *)fmalloc(KHEAP_SIZE);
-	init_heap(kheap, KHEAP_SIZE);
-
-	// Make user heap
-	uheap = (struct heap_header *)kmalloc_a(UHEAP_SIZE);
-	init_heap(uheap, UHEAP_SIZE);
-	paging_map_user(paging_root_directory, (u32)&uheap, (u32)&uheap);
+	locked = 0;
+	return 0;
 }
 
-void *fmalloc(u32 size)
+void *liballoc_alloc(u32 p)
 {
-	assert(placement_address + size < MEM_END);
-	u32 hold = placement_address;
-	memset((void *)hold, 0, size);
-	placement_address += size;
-	return (void *)hold;
+	u32 ptr = paging_alloc_pages((u32)p);
+	return (void *)ptr;
 }
 
-void *kmalloc_a(u32 size)
+int liballoc_free(void *ptr, u32 p)
 {
-	assert(((placement_address & 0xFFFFF000) + 0x1000) + size < MEM_END);
-	placement_address &= 0xFFFFF000;
-	placement_address += 0x1000;
+	paging_set_free((u32)ptr, (u32)p);
+	return 0;
+}
 
-	u32 hold = placement_address;
-	placement_address += size;
+#define ALIGNMENT 16ul
+#define ALIGN_TYPE char
+#define ALIGN_INFO sizeof(ALIGN_TYPE) * 16
+#define USE_CASE1
+#define USE_CASE2
+#define USE_CASE3
+#define USE_CASE4
+#define USE_CASE5
+
+#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;                      \
+	}
 
-	return (void *)hold;
-}
+#define UNALIGN(ptr)                                                                               \
+	if (ALIGNMENT > 1) {                                                                       \
+		u32 diff = *((ALIGN_TYPE *)((u32)ptr - ALIGN_INFO));                               \
+		if (diff < (ALIGNMENT + ALIGN_INFO)) {                                             \
+			ptr = (void *)((u32)ptr - diff);                                           \
+		}                                                                                  \
+	}
 
-struct heap_header *find_sized_heap(struct heap_header *heap, u32 size)
+#define LIBALLOC_MAGIC 0x900df00d
+#define LIBALLOC_DEAD 0xbaadf00d
+
+struct liballoc_major {
+	struct liballoc_major *prev;
+	struct liballoc_major *next;
+	u32 pages;
+	u32 size;
+	u32 usage;
+	struct liballoc_minor *first;
+};
+
+struct liballoc_minor {
+	struct liballoc_minor *prev;
+	struct liballoc_minor *next;
+	struct liballoc_major *block;
+	u32 magic;
+	u32 size;
+	u32 req_size;
+};
+
+static struct liballoc_major *l_mem_root = NULL;
+static struct liballoc_major *l_best_bet = NULL;
+
+static u32 l_page_size = 4096;
+static u32 l_page_count = 16;
+static u64 l_allocated = 0;
+static u64 l_inuse = 0;
+
+static long long l_warning_count = 0;
+static long long l_error_count = 0;
+static long long l_possible_overruns = 0;
+
+static void *liballoc_memset(void *s, int c, u32 n)
 {
-	while ((heap->size < HEAP_FIND_SIZE + size) || (heap->free != true)) {
-		assert(heap->magic == KHEAP_MAGIC);
-		assert(heap->magic2 == KHEAP_MAGIC2);
-		struct heap_footer *foot = (struct heap_footer *)((u32)heap + HEAP_S + heap->size);
-		assert(foot->magic == KHEAP_MAGIC);
-		assert(foot->magic2 == KHEAP_MAGIC2);
+	u32 i;
+	for (i = 0; i < n; i++)
+		((char *)s)[i] = c;
 
-		if (foot->size == KHEAP_END)
-			panic("Out of heap space");
-
-		if (foot->size != heap->size)
-			panic("Heap footer/header mismatch");
+	return s;
+}
 
-		heap = (struct heap_header *)((u32)foot + sizeof(struct heap_footer));
+static void *liballoc_memcpy(void *s1, const void *s2, u32 n)
+{
+	char *cdest;
+	char *csrc;
+	u32 *ldest = (u32 *)s1;
+	u32 *lsrc = (u32 *)s2;
+
+	while (n >= sizeof(u32)) {
+		*ldest++ = *lsrc++;
+		n -= sizeof(u32);
 	}
 
-	return heap;
+	cdest = (char *)ldest;
+	csrc = (char *)lsrc;
+
+	while (n > 0) {
+		*cdest++ = *csrc++;
+		n -= 1;
+	}
+	return s1;
 }
 
-void split_heap(struct heap_header *heap, u32 size)
+static struct liballoc_major *allocate_new_page(u32 size)
 {
-	struct heap_footer *foot = (struct heap_footer *)((u32)heap + HEAP_S + size);
-	foot->magic = KHEAP_MAGIC;
-	foot->magic2 = KHEAP_MAGIC2;
-	foot->size = size;
+	u32 st;
+	struct liballoc_major *maj;
+
+	st = size + sizeof(struct liballoc_major);
+	st += sizeof(struct liballoc_minor);
 
-	u32 new_size = heap->size - HEAP_TOTAL - size;
-	heap->size = size;
+	if ((st % l_page_size) == 0)
+		st = st / (l_page_size);
+	else
+		st = st / (l_page_size) + 1;
 
-	heap = (struct heap_header *)((u32)foot + sizeof(struct heap_footer));
-	heap->size = new_size;
-	heap->free = true;
-	heap->magic = KHEAP_MAGIC;
-	heap->magic2 = KHEAP_MAGIC2;
+	if (st < l_page_count)
+		st = l_page_count;
 
-	foot = (struct heap_footer *)((u32)heap + HEAP_S + heap->size);
-	if ((foot->magic != KHEAP_MAGIC) || (foot->magic2 != KHEAP_MAGIC2)) {
-		warn("Invalid footer in split");
+	maj = (struct liballoc_major *)liballoc_alloc(st);
+
+	if (maj == NULL) {
+		l_warning_count += 1;
+		return NULL;
 	}
 
-	if (foot->size != KHEAP_END)
-		foot->size = new_size;
+	maj->prev = NULL;
+	maj->next = NULL;
+	maj->pages = st;
+	maj->size = st * l_page_size;
+	maj->usage = sizeof(struct liballoc_major);
+	maj->first = NULL;
+
+	l_allocated += maj->size;
+
+	return maj;
 }
 
-void free_internal(struct heap_header *heap, void *address)
+void *malloc(u32 req_size)
 {
-	struct heap_header *head = (struct heap_header *)((u32)address - HEAP_S);
-	if (head == heap) {
-		//warn("Can't collapse top of heap"); // TODO: Fix "can't collapse top of heap" at start
-		head->free = true;
-		return;
+	int startedBet = 0;
+	u64 best_size = 0;
+	void *p = NULL;
+	u32 diff;
+	struct liballoc_major *maj;
+	struct liballoc_minor *min;
+	struct liballoc_minor *new_min;
+	u32 size = req_size;
+
+	if (ALIGNMENT > 1) {
+		size += ALIGNMENT + ALIGN_INFO;
 	}
 
-	if ((head->magic != KHEAP_MAGIC) || (head->magic2 != KHEAP_MAGIC2)) {
-		warn("Invalid header in heap");
-		return;
-	}
+	liballoc_lock();
 
-	struct heap_footer *foot = (struct heap_footer *)((u32)head + HEAP_S + head->size);
-	if ((foot->magic != KHEAP_MAGIC) || (foot->magic2 != KHEAP_MAGIC2))
-		panic("Bad heap call");
+	if (size == 0) {
+		l_warning_count += 1;
+		liballoc_unlock();
+		return malloc(1);
+	}
 
-	foot = (struct heap_footer *)((u32)head - sizeof(struct heap_footer));
-	if ((foot->magic != KHEAP_MAGIC) || (foot->magic2 != KHEAP_MAGIC2)) {
-		warn("Invalid footer in heap");
-		return;
+	if (l_mem_root == NULL) {
+		l_mem_root = allocate_new_page(size);
+		if (l_mem_root == NULL) {
+			liballoc_unlock();
+			return NULL;
+		}
 	}
 
-	if (foot->size == KHEAP_END)
-		panic("Impossible condition for heap");
+	maj = l_mem_root;
+	startedBet = 0;
 
-	heap = (struct heap_header *)((u32)foot - foot->size - HEAP_S);
-	if ((heap->magic != KHEAP_MAGIC) || (heap->magic2 != KHEAP_MAGIC2)) {
-		warn("Invalid parent in heap");
-		return;
+	if (l_best_bet != NULL) {
+		best_size = l_best_bet->size - l_best_bet->usage;
+
+		if (best_size > (size + sizeof(struct liballoc_minor))) {
+			maj = l_best_bet;
+			startedBet = 1;
+		}
 	}
 
-	foot = (struct heap_footer *)((u32)heap + (heap->size + head->size + HEAP_TOTAL) + HEAP_S);
-	if ((foot->magic != KHEAP_MAGIC) || (foot->magic2 != KHEAP_MAGIC2)) {
-		panic("Fatal arithmetic error in free() call");
-		return;
+	while (maj != NULL) {
+		diff = maj->size - maj->usage;
+		if (best_size < diff) {
+			l_best_bet = maj;
+			best_size = diff;
+		}
+
+#ifdef USE_CASE1
+		if (diff < (size + sizeof(struct liballoc_minor))) {
+			if (maj->next != NULL) {
+				maj = maj->next;
+				continue;
+			}
+
+			if (startedBet == 1) {
+				maj = l_mem_root;
+				startedBet = 0;
+				continue;
+			}
+
+			maj->next = allocate_new_page(size);
+			if (maj->next == NULL)
+				break;
+			maj->next->prev = maj;
+			maj = maj->next;
+		}
+#endif
+
+#ifdef USE_CASE2
+		if (maj->first == NULL) {
+			maj->first =
+				(struct liballoc_minor *)((u32)maj + sizeof(struct liballoc_major));
+
+			maj->first->magic = LIBALLOC_MAGIC;
+			maj->first->prev = NULL;
+			maj->first->next = NULL;
+			maj->first->block = maj;
+			maj->first->size = size;
+			maj->first->req_size = req_size;
+			maj->usage += size + sizeof(struct liballoc_minor);
+			l_inuse += size;
+			p = (void *)((u32)(maj->first) + sizeof(struct liballoc_minor));
+			ALIGN(p);
+			liballoc_unlock();
+			return p;
+		}
+#endif
+
+#ifdef USE_CASE3
+		diff = (u32)(maj->first);
+		diff -= (u32)maj;
+		diff -= sizeof(struct liballoc_major);
+
+		if (diff >= (size + sizeof(struct liballoc_minor))) {
+			maj->first->prev =
+				(struct liballoc_minor *)((u32)maj + sizeof(struct liballoc_major));
+			maj->first->prev->next = maj->first;
+			maj->first = maj->first->prev;
+			maj->first->magic = LIBALLOC_MAGIC;
+			maj->first->prev = NULL;
+			maj->first->block = maj;
+			maj->first->size = size;
+			maj->first->req_size = req_size;
+			maj->usage += size + sizeof(struct liballoc_minor);
+			l_inuse += size;
+			p = (void *)((u32)(maj->first) + sizeof(struct liballoc_minor));
+			ALIGN(p);
+			liballoc_unlock();
+			return p;
+		}
+#endif
+
+#ifdef USE_CASE4
+		min = maj->first;
+
+		while (min != NULL) {
+			if (min->next == NULL) {
+				diff = (u32)(maj) + maj->size;
+				diff -= (u32)min;
+				diff -= sizeof(struct liballoc_minor);
+				diff -= min->size;
+				if (diff >= (size + sizeof(struct liballoc_minor))) {
+					min->next = (struct liballoc_minor
+							     *)((u32)min +
+								sizeof(struct liballoc_minor) +
+								min->size);
+					min->next->prev = min;
+					min = min->next;
+					min->next = NULL;
+					min->magic = LIBALLOC_MAGIC;
+					min->block = maj;
+					min->size = size;
+					min->req_size = req_size;
+					maj->usage += size + sizeof(struct liballoc_minor);
+					l_inuse += size;
+					p = (void *)((u32)min + sizeof(struct liballoc_minor));
+					ALIGN(p);
+					liballoc_unlock();
+					return p;
+				}
+			}
+
+			if (min->next != NULL) {
+				diff = (u32)(min->next);
+				diff -= (u32)min;
+				diff -= sizeof(struct liballoc_minor);
+				diff -= min->size;
+
+				if (diff >= (size + sizeof(struct liballoc_minor))) {
+					new_min = (struct liballoc_minor
+							   *)((u32)min +
+							      sizeof(struct liballoc_minor) +
+							      min->size);
+					new_min->magic = LIBALLOC_MAGIC;
+					new_min->next = min->next;
+					new_min->prev = min;
+					new_min->size = size;
+					new_min->req_size = req_size;
+					new_min->block = maj;
+					min->next->prev = new_min;
+					min->next = new_min;
+					maj->usage += size + sizeof(struct liballoc_minor);
+					l_inuse += size;
+					p = (void *)((u32)new_min + sizeof(struct liballoc_minor));
+					ALIGN(p);
+					liballoc_unlock();
+					return p;
+				}
+			}
+
+			min = min->next;
+		}
+#endif
+
+#ifdef USE_CASE5
+		if (maj->next == NULL) {
+			if (startedBet == 1) {
+				maj = l_mem_root;
+				startedBet = 0;
+				continue;
+			}
+			maj->next = allocate_new_page(size);
+			if (maj->next == NULL)
+				break;
+			maj->next->prev = maj;
+		}
+#endif
+		maj = maj->next;
 	}
 
-	heap->size += head->size + HEAP_TOTAL;
-	foot->size = heap->size;
-}
+	liballoc_unlock();
 
-void *malloc_internal(struct heap_header *heap, u32 size)
-{
-	heap = find_sized_heap(heap, size + 8);
-	heap->free = false;
-	split_heap(heap, size);
-	return (void *)((u32)heap + HEAP_S);
+	return NULL;
 }
 
-void init_heap(struct heap_header *heap, u32 size)
+void free(void *ptr)
 {
-	heap->magic = KHEAP_MAGIC;
-	heap->magic2 = KHEAP_MAGIC2;
-	heap->free = true;
-	heap->size = size - HEAP_TOTAL;
-
-	struct heap_footer *foot = (struct heap_footer *)((u32)heap + HEAP_S + heap->size);
-	foot->magic = KHEAP_MAGIC;
-	foot->magic2 = KHEAP_MAGIC2;
-	foot->size = KHEAP_END;
-}
+	struct liballoc_minor *min;
+	struct liballoc_major *maj;
 
-void *kmalloc(u32 size)
-{
-	if (kheap == NULL)
-		return fmalloc(size);
+	if (ptr == NULL) {
+		l_warning_count += 1;
+		return;
+	}
 
-	return malloc_internal(kheap, size);
-}
+	UNALIGN(ptr);
+	liballoc_lock();
 
-void *kcalloc(u32 num, u32 size)
-{
-	void *ptr = kmalloc(num * size);
-	memset(ptr, 0, num * size);
-	return ptr;
-}
+	min = (struct liballoc_minor *)((u32)ptr - sizeof(struct liballoc_minor));
 
-void kfree(void *address)
-{
-	if (kheap == NULL)
+	if (min->magic != LIBALLOC_MAGIC) {
+		l_error_count += 1;
+
+		if (((min->magic & 0xFFFFFF) == (LIBALLOC_MAGIC & 0xFFFFFF)) ||
+		    ((min->magic & 0xFFFF) == (LIBALLOC_MAGIC & 0xFFFF)) ||
+		    ((min->magic & 0xFF) == (LIBALLOC_MAGIC & 0xFF))) {
+			l_possible_overruns += 1;
+		}
+
+		liballoc_unlock();
 		return;
+	}
 
-	free_internal(kheap, address);
+	maj = min->block;
+	l_inuse -= min->size;
+	maj->usage -= (min->size + sizeof(struct liballoc_minor));
+	min->magic = LIBALLOC_DEAD;
+
+	if (min->next != NULL)
+		min->next->prev = min->prev;
+	if (min->prev != NULL)
+		min->prev->next = min->next;
+	if (min->prev == NULL)
+		maj->first = min->next;
+	if (maj->first == NULL) {
+		if (l_mem_root == maj)
+			l_mem_root = maj->next;
+		if (l_best_bet == maj)
+			l_best_bet = NULL;
+		if (maj->prev != NULL)
+			maj->prev->next = maj->next;
+		if (maj->next != NULL)
+			maj->next->prev = maj->prev;
+		l_allocated -= maj->size;
+		liballoc_free(maj, maj->pages);
+	} else {
+		if (l_best_bet != NULL) {
+			int best_size = l_best_bet->size - l_best_bet->usage;
+			int maj_size = maj->size - maj->usage;
+			if (maj_size > best_size)
+				l_best_bet = maj;
+		}
+	}
+	liballoc_unlock();
 }
 
-void *umalloc(u32 size)
+void *calloc(u32 nobj, u32 size)
 {
-	return malloc_internal(uheap, size);
-}
+	int real_size;
+	void *p;
 
-void *ucalloc(u32 num, u32 size)
-{
-	void *ptr = umalloc(num * size);
-	memset(ptr, 0, num * size);
-	return ptr;
+	real_size = nobj * size;
+
+	p = malloc(real_size);
+
+	liballoc_memset(p, 0, real_size);
+
+	return p;
 }
 
-void ufree(void *address)
+void *realloc(void *p, u32 size)
 {
-	free_internal(uheap, address);
+	void *ptr;
+	struct liballoc_minor *min;
+	u32 real_size;
+
+	if (size == 0) {
+		free(p);
+		return NULL;
+	}
+
+	if (p == NULL)
+		return malloc(size);
+
+	ptr = p;
+	UNALIGN(ptr);
+	liballoc_lock();
+	min = (struct liballoc_minor *)((u32)ptr - sizeof(struct liballoc_minor));
+
+	if (min->magic != LIBALLOC_MAGIC) {
+		l_error_count += 1;
+		if (((min->magic & 0xFFFFFF) == (LIBALLOC_MAGIC & 0xFFFFFF)) ||
+		    ((min->magic & 0xFFFF) == (LIBALLOC_MAGIC & 0xFFFF)) ||
+		    ((min->magic & 0xFF) == (LIBALLOC_MAGIC & 0xFF))) {
+			l_possible_overruns += 1;
+		}
+
+		liballoc_unlock();
+		return NULL;
+	}
+
+	real_size = min->req_size;
+
+	if (real_size >= size) {
+		min->req_size = size;
+		liballoc_unlock();
+		return p;
+	}
+
+	liballoc_unlock();
+
+	ptr = malloc(size);
+	liballoc_memcpy(ptr, p, real_size);
+	free(p);
+
+	return ptr;
 }
\ No newline at end of file