From 31f671f2137bc09e62de09142bea232c1975c76b Mon Sep 17 00:00:00 2001 From: Marvin Borner Date: Sun, 26 Apr 2020 20:12:05 +0200 Subject: Complete rewrite of paging and allocation libs -> This was REALLY needed. --- src/kernel/memory/alloc.c | 552 +++++++++++----------------------------------- 1 file changed, 131 insertions(+), 421 deletions(-) (limited to 'src/kernel/memory/alloc.c') diff --git a/src/kernel/memory/alloc.c b/src/kernel/memory/alloc.c index 174f298..fbf97d8 100644 --- a/src/kernel/memory/alloc.c +++ b/src/kernel/memory/alloc.c @@ -2,478 +2,188 @@ #include #include #include +#include +#include -int liballoc_lock() -{ - // cli(); - return 0; -} +uint32_t placement_address; -int liballoc_unlock() -{ - // sti(); - return 0; -} - -void *liballoc_alloc(size_t p) -{ - uint32_t ptr = paging_alloc_pages((uint32_t)p); - return (void *)ptr; -} +struct heap_header *kheap = NULL; +struct heap_header *uheap = NULL; -int liballoc_free(void *ptr, size_t p) +void kheap_init() { - paging_set_free((uint32_t)ptr, (uint32_t)p); - return 0; + placement_address = &ASM_KERNEL_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, (uint32_t)&uheap, (uint32_t)&uheap); } -#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) { \ - uintptr_t diff; \ - ptr = (void *)((uintptr_t)ptr + ALIGN_INFO); \ - diff = (uintptr_t)ptr & (ALIGNMENT - 1); \ - if (diff != 0) { \ - diff = ALIGNMENT - diff; \ - ptr = (void *)((uintptr_t)ptr + diff); \ - } \ - *((ALIGN_TYPE *)((uintptr_t)ptr - ALIGN_INFO)) = diff + ALIGN_INFO; \ - } - -#define UNALIGN(ptr) \ - if (ALIGNMENT > 1) { \ - uintptr_t diff = *((ALIGN_TYPE *)((uintptr_t)ptr - ALIGN_INFO)); \ - if (diff < (ALIGNMENT + ALIGN_INFO)) { \ - ptr = (void *)((uintptr_t)ptr - diff); \ - } \ - } - -#define LIBALLOC_MAGIC 0x900df00d -#define LIBALLOC_DEAD 0xbaadf00d - -struct liballoc_major { - struct liballoc_major *prev; - struct liballoc_major *next; - unsigned int pages; - unsigned int size; - unsigned int usage; - struct liballoc_minor *first; -}; - -struct liballoc_minor { - struct liballoc_minor *prev; - struct liballoc_minor *next; - struct liballoc_major *block; - unsigned int magic; - unsigned int size; - unsigned int req_size; -}; - -static struct liballoc_major *l_memRoot = NULL; -static struct liballoc_major *l_bestBet = NULL; - -static unsigned int l_pageSize = 4096; -static unsigned int l_pageCount = 16; -static unsigned long long l_allocated = 0; -static unsigned long long l_inuse = 0; - -static long long l_warningCount = 0; -static long long l_errorCount = 0; -static long long l_possibleOverruns = 0; - -static void *liballoc_memset(void *s, int c, size_t n) +void *fmalloc(uint32_t size) { - unsigned int i; - for (i = 0; i < n; i++) - ((char *)s)[i] = c; - - return s; + //assert(placement_address + size < MEM_END); + uint32_t hold = placement_address; + memset((void *)hold, 0, size); + placement_address += size; + return (void *)hold; } -static void *liballoc_memcpy(void *s1, const void *s2, size_t n) +void *kmalloc_a(uint32_t size) { - char *cdest; - char *csrc; - unsigned int *ldest = (unsigned int *)s1; - unsigned int *lsrc = (unsigned int *)s2; - - while (n >= sizeof(unsigned int)) { - *ldest++ = *lsrc++; - n -= sizeof(unsigned int); - } + //assert(((placement_address & 0xFFFFF000) + 0x1000) + size < MEM_END); + placement_address &= 0xFFFFF000; + placement_address += 0x1000; - cdest = (char *)ldest; - csrc = (char *)lsrc; + uint32_t hold = placement_address; + placement_address += size; - while (n > 0) { - *cdest++ = *csrc++; - n -= 1; - } - return s1; + return (void *)hold; } -static struct liballoc_major *allocate_new_page(unsigned int size) +struct heap_header *find_sized_heap(struct heap_header *heap, size_t size) { - unsigned int st; - struct liballoc_major *maj; + 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 *)((uint32_t)heap + HEAP_S + heap->size); + assert(foot->magic == KHEAP_MAGIC); + assert(foot->magic2 == KHEAP_MAGIC2); - st = size + sizeof(struct liballoc_major); - st += sizeof(struct liballoc_minor); + if (foot->size == KHEAP_END) + panic("Out of heap space"); - if ((st % l_pageSize) == 0) - st = st / (l_pageSize); - else - st = st / (l_pageSize) + 1; + if (foot->size != heap->size) + panic("Heap footer/header mismatch"); - if (st < l_pageCount) - st = l_pageCount; - - maj = (struct liballoc_major *)liballoc_alloc(st); - - if (maj == NULL) { - l_warningCount += 1; - return NULL; + heap = (struct heap_header *)((uint32_t)foot + sizeof(struct heap_footer)); } - maj->prev = NULL; - maj->next = NULL; - maj->pages = st; - maj->size = st * l_pageSize; - maj->usage = sizeof(struct liballoc_major); - maj->first = NULL; - - l_allocated += maj->size; - - return maj; + return heap; } -void *PREFIX(malloc)(size_t req_size) +void split_heap(struct heap_header *heap, size_t size) { - int startedBet = 0; - unsigned long long bestSize = 0; - void *p = NULL; - uintptr_t diff; - struct liballoc_major *maj; - struct liballoc_minor *min; - struct liballoc_minor *new_min; - unsigned long size = req_size; - - if (ALIGNMENT > 1) { - size += ALIGNMENT + ALIGN_INFO; - } - - liballoc_lock(); - - if (size == 0) { - l_warningCount += 1; - liballoc_unlock(); - return PREFIX(malloc)(1); - } - - if (l_memRoot == NULL) { - l_memRoot = allocate_new_page(size); - if (l_memRoot == NULL) { - liballoc_unlock(); - return NULL; - } - } + struct heap_footer *foot = (struct heap_footer *)((uint32_t)heap + HEAP_S + size); + foot->magic = KHEAP_MAGIC; + foot->magic2 = KHEAP_MAGIC2; + foot->size = size; - maj = l_memRoot; - startedBet = 0; + size_t new_size = heap->size - HEAP_TOTAL - size; + heap->size = size; - if (l_bestBet != NULL) { - bestSize = l_bestBet->size - l_bestBet->usage; + heap = (struct heap_header *)((uint32_t)foot + sizeof(struct heap_footer)); + heap->size = new_size; + heap->free = true; + heap->magic = KHEAP_MAGIC; + heap->magic2 = KHEAP_MAGIC2; - if (bestSize > (size + sizeof(struct liballoc_minor))) { - maj = l_bestBet; - startedBet = 1; - } + foot = (struct heap_footer *)((uint32_t)heap + HEAP_S + heap->size); + if ((foot->magic != KHEAP_MAGIC) || (foot->magic2 != KHEAP_MAGIC2)) { + warn("Invalid footer in split"); } - while (maj != NULL) { - diff = maj->size - maj->usage; - if (bestSize < diff) { - l_bestBet = maj; - bestSize = diff; - } - -#ifdef USE_CASE1 - if (diff < (size + sizeof(struct liballoc_minor))) { - if (maj->next != NULL) { - maj = maj->next; - continue; - } - - if (startedBet == 1) { - maj = l_memRoot; - 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 *)((uintptr_t)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 *)((uintptr_t)(maj->first) + sizeof(struct liballoc_minor)); - ALIGN(p); - liballoc_unlock(); - return p; - } -#endif - -#ifdef USE_CASE3 - diff = (uintptr_t)(maj->first); - diff -= (uintptr_t)maj; - diff -= sizeof(struct liballoc_major); - - if (diff >= (size + sizeof(struct liballoc_minor))) { - maj->first->prev = (struct liballoc_minor *)((uintptr_t)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 *)((uintptr_t)(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 = (uintptr_t)(maj) + maj->size; - diff -= (uintptr_t)min; - diff -= sizeof(struct liballoc_minor); - diff -= min->size; - if (diff >= (size + sizeof(struct liballoc_minor))) { - min->next = (struct liballoc_minor - *)((uintptr_t)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 *)((uintptr_t)min + - sizeof(struct liballoc_minor)); - ALIGN(p); - liballoc_unlock(); - return p; - } - } - - if (min->next != NULL) { - diff = (uintptr_t)(min->next); - diff -= (uintptr_t)min; - diff -= sizeof(struct liballoc_minor); - diff -= min->size; - - if (diff >= (size + sizeof(struct liballoc_minor))) { - new_min = (struct liballoc_minor - *)((uintptr_t)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 *)((uintptr_t)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_memRoot; - startedBet = 0; - continue; - } - maj->next = allocate_new_page(size); - if (maj->next == NULL) - break; - maj->next->prev = maj; - } -#endif - maj = maj->next; - } - - liballoc_unlock(); - - return NULL; + if (foot->size != KHEAP_END) + foot->size = new_size; } -void PREFIX(free)(void *ptr) +void free_internal(struct heap_header *heap, void *address) { - struct liballoc_minor *min; - struct liballoc_major *maj; - - if (ptr == NULL) { - l_warningCount += 1; + struct heap_header *head = (struct heap_header *)((uint32_t)address - HEAP_S); + if (head == heap) { + warn("Can't collapse top of heap"); + head->free = true; return; } - UNALIGN(ptr); - liballoc_lock(); + if ((head->magic != KHEAP_MAGIC) || (head->magic2 != KHEAP_MAGIC2)) { + //warn("Invalid header in heap"); + return; + } - min = (struct liballoc_minor *)((uintptr_t)ptr - sizeof(struct liballoc_minor)); + struct heap_footer *foot = (struct heap_footer *)((uint32_t)head + HEAP_S + head->size); + if ((foot->magic != KHEAP_MAGIC) || (foot->magic2 != KHEAP_MAGIC2)) + panic("Bad heap call"); - if (min->magic != LIBALLOC_MAGIC) { - l_errorCount += 1; + foot = (struct heap_footer *)((uint32_t)head - sizeof(struct heap_footer)); + if ((foot->magic != KHEAP_MAGIC) || (foot->magic2 != KHEAP_MAGIC2)) { + //warn("Invalid footer in heap"); + return; + } - if (((min->magic & 0xFFFFFF) == (LIBALLOC_MAGIC & 0xFFFFFF)) || - ((min->magic & 0xFFFF) == (LIBALLOC_MAGIC & 0xFFFF)) || - ((min->magic & 0xFF) == (LIBALLOC_MAGIC & 0xFF))) { - l_possibleOverruns += 1; - } + if (foot->size == KHEAP_END) + panic("Impossible condition for heap"); - liballoc_unlock(); + heap = (struct heap_header *)((uint32_t)foot - foot->size - HEAP_S); + if ((heap->magic != KHEAP_MAGIC) || (heap->magic2 != KHEAP_MAGIC2)) { + warn("Invalid parent in heap"); return; } - 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_memRoot == maj) - l_memRoot = maj->next; - if (l_bestBet == maj) - l_bestBet = 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_bestBet != NULL) { - int bestSize = l_bestBet->size - l_bestBet->usage; - int majSize = maj->size - maj->usage; - if (majSize > bestSize) - l_bestBet = maj; - } + foot = (struct heap_footer *)((uint32_t)heap + (heap->size + head->size + HEAP_TOTAL) + + HEAP_S); + if ((foot->magic != KHEAP_MAGIC) || (foot->magic2 != KHEAP_MAGIC2)) { + /*vga_puts("Footer with size of "); + vga_puts_hex(foot->size); + vga_puts(" / head size of "); + vga_puts_hex(heap->size); + vga_puts("\n"); + dump_struct(foot, sizeof(struct heap_footer)); + warn("fatal arithmetic error in free() call"); + */ + return; } - liballoc_unlock(); + + heap->size += head->size + HEAP_TOTAL; + foot->size = heap->size; } -void *PREFIX(calloc)(size_t nobj, size_t size) +void *malloc_internal(struct heap_header *heap, size_t size) { - int real_size; - void *p; - - real_size = nobj * size; - - p = PREFIX(malloc)(real_size); - - liballoc_memset(p, 0, real_size); - - return p; + heap = find_sized_heap(heap, size + 8); + heap->free = false; + split_heap(heap, size); + return (void *)((uint32_t)heap + HEAP_S); } -void *PREFIX(realloc)(void *p, size_t size) +void init_heap(struct heap_header *heap, size_t size) { - void *ptr; - struct liballoc_minor *min; - unsigned int real_size; - - if (size == 0) { - PREFIX(free)(p); - return NULL; - } - - if (p == NULL) - return PREFIX(malloc)(size); - - ptr = p; - UNALIGN(ptr); - liballoc_lock(); - min = (struct liballoc_minor *)((uintptr_t)ptr - sizeof(struct liballoc_minor)); - - if (min->magic != LIBALLOC_MAGIC) { - l_errorCount += 1; - if (((min->magic & 0xFFFFFF) == (LIBALLOC_MAGIC & 0xFFFFFF)) || - ((min->magic & 0xFFFF) == (LIBALLOC_MAGIC & 0xFFFF)) || - ((min->magic & 0xFF) == (LIBALLOC_MAGIC & 0xFF))) { - l_possibleOverruns += 1; - } + heap->magic = KHEAP_MAGIC; + heap->magic2 = KHEAP_MAGIC2; + heap->free = true; + heap->size = size - HEAP_TOTAL; + + struct heap_footer *foot = (struct heap_footer *)((uint32_t)heap + HEAP_S + heap->size); + foot->magic = KHEAP_MAGIC; + foot->magic2 = KHEAP_MAGIC2; + foot->size = KHEAP_END; +} - liballoc_unlock(); - return NULL; - } +void *kmalloc(uint32_t size) +{ + if (kheap == NULL) + return fmalloc(size); - real_size = min->req_size; + return malloc_internal(kheap, size); +} - if (real_size >= size) { - min->req_size = size; - liballoc_unlock(); - return p; - } +void kfree(void *address) +{ + if (kheap == NULL) + return; - liballoc_unlock(); + free_internal(kheap, address); +} - ptr = PREFIX(malloc)(size); - liballoc_memcpy(ptr, p, real_size); - PREFIX(free)(p); +void *umalloc(size_t size) +{ + return malloc_internal(uheap, size); +} - return ptr; -} \ No newline at end of file +void ufree(void *address) +{ + free_internal(uheap, address); +} -- cgit v1.2.3