diff options
| -rw-r--r-- | README.md | 4 | ||||
| -rw-r--r-- | apps/init.c | 3 | ||||
| -rw-r--r-- | kernel/features/mm.c | 6 | ||||
| -rw-r--r-- | kernel/features/proc.c | 1 | ||||
| -rw-r--r-- | kernel/features/syscall.c | 8 | ||||
| -rw-r--r-- | libc/alloc.c | 573 | ||||
| -rw-r--r-- | libc/inc/mem.h | 3 | ||||
| -rw-r--r-- | libc/inc/sys.h | 2 |
8 files changed, 327 insertions, 273 deletions
@@ -84,14 +84,14 @@ This project is somewhat of a coding playground for me. It doesn't have any usef Melvix is released under the MIT License and uses parts of the following 3rd party projects: -Inspiration/usage: +Inspiration/usage (documented in the respective files): - [OSDev wiki](https://wiki.osdev.org) - Very helpful! - [James Molloy's tutorials](http://jamesmolloy.co.uk/tutorial_html/) - [virtix - tasking inspiration](https://github.com/16Bitt/virtix/) - [MIT License](https://github.com/16Bitt/virtix/blob/85a3c58f3d3b8932354e85a996a79c377139c201/LICENSE) - [studix - FS inspiration](https://github.com/orodley/studix) - [MIT License](https://github.com/orodley/studix/blob/d1b1d006010120551df58ff3faaf97484dfa9806/LICENSE) +- [skiftOS - Memory management inspiration](https://github.com/skiftOS/skift) - [MIT License](https://github.com/skiftOS/skift/blob/ea0e1cf0d7b07302370fc1519be2e072a4cad70c/license.md) - [ToAruOS - PCI and network driver inspiration](https://github.com/klange/toaruos) - [NCSA License](https://github.com/klange/toaruos/blob/351d5d38f22b570459931475d36468bf4e37f45a/LICENSE) -- [SHMALL - Heap allocator inspiration](https://github.com/CCareaga/heap_allocator) - [MIT License](https://github.com/CCareaga/heap_allocator/blob/fc423c6113df598ac8d10bc1f2954d51248e6443/LICENSE) Resources: diff --git a/apps/init.c b/apps/init.c index 6503022..705f178 100644 --- a/apps/init.c +++ b/apps/init.c @@ -8,7 +8,8 @@ int main(int argc, char **argv) { - log("%s loaded\n", argv[0]); + UNUSED(argc); + UNUSED(argv); while (1) { }; diff --git a/kernel/features/mm.c b/kernel/features/mm.c index 5fe70fd..b5fd33c 100644 --- a/kernel/features/mm.c +++ b/kernel/features/mm.c @@ -448,8 +448,6 @@ static struct memory_range kernel_memory_range(void) void memory_install(struct mem_info *mem_info) { - heap_init(HEAP_START); - for (struct mmap_boot *p = mem_info->start; (u32)(p - mem_info->start) < mem_info->size; p++) { if (p->hbase || !p->acpi || !p->type) @@ -486,10 +484,6 @@ void memory_install(struct mem_info *mem_info) memory_map_identity(&kernel_dir, memory_range_around(STACK_START - STACK_SIZE, STACK_SIZE), MEMORY_NONE); - // Map kernel heap - memory_map_identity(&kernel_dir, memory_range_around(HEAP_START, HEAP_INIT_SIZE), - MEMORY_NONE); - // TODO: Triple fault prevention? Probably bootloader stuff or something memory_map_identity(&kernel_dir, memory_range_around(0x7000, 0x1000), MEMORY_NONE); diff --git a/kernel/features/proc.c b/kernel/features/proc.c index e4b5105..e7ddf4b 100644 --- a/kernel/features/proc.c +++ b/kernel/features/proc.c @@ -487,6 +487,7 @@ void proc_init(void) struct node *new = list_add(proc_list, proc_make(PROC_PRIV_ROOT)); bin_load("/bin/init", new->data); current = new; + proc_stack_push(new->data, 0); _eip = ((struct proc *)new->data)->regs.eip; _esp = ((struct proc *)new->data)->regs.useresp; diff --git a/kernel/features/syscall.c b/kernel/features/syscall.c index bac1738..486da6c 100644 --- a/kernel/features/syscall.c +++ b/kernel/features/syscall.c @@ -5,6 +5,7 @@ #include <interrupts.h> #include <load.h> #include <mem.h> +#include <mm.h> #include <net.h> #include <print.h> #include <proc.h> @@ -25,12 +26,13 @@ static void syscall_handler(struct regs *r) loop(); break; } - case SYS_MALLOC: { - r->eax = (u32)malloc(r->ebx); + case SYS_ALLOC: { + r->eax = (u32)memory_alloc(proc_current()->page_dir, r->ebx, + MEMORY_CLEAR | MEMORY_USER); break; } case SYS_FREE: { - free((void *)r->ebx); + memory_free(proc_current()->page_dir, memory_range(r->ebx, r->ecx)); break; } case SYS_STAT: { diff --git a/libc/alloc.c b/libc/alloc.c index f621c4e..083f2c0 100644 --- a/libc/alloc.c +++ b/libc/alloc.c @@ -1,297 +1,383 @@ // MIT License, Copyright (c) 2021 Marvin Borner +// Mostly by Durand Miller, released into public domain #include <assert.h> -#include <def.h> +#include <cpu.h> #include <mem.h> -#include <print.h> -#include <sys.h> - -/** - * Kernel heap allocator - * Inspired by SHMALL (MIT License) - * Copyright (c) 2017 Chris Careaga - * Copyright (c) 2021 Marvin Borner - */ #ifdef kernel -#define HEAP_MAGIC 0x424242 -#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 magic; - u32 hole; - u32 size; - struct h_node *next; - struct h_node *prev; -}; - -struct h_footer { - struct h_node *header; -}; +#include <mm.h> -struct h_bin { - struct h_node *head; -}; - -struct heap { - u32 start; - u32 end; - struct h_bin bins[BIN_COUNT]; -}; - -static void node_add(struct h_bin *bin, struct h_node *node) +static void *liballoc_alloc(u32 p) { - node->magic = HEAP_MAGIC; - 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; - } + return memory_alloc(virtual_kernel_dir(), p, MEMORY_CLEAR); } -static void node_remove(struct h_bin *bin, struct h_node *node) +static int liballoc_free(void *ptr, u32 p) { - if (!bin->head) - return; - if (bin->head == node) { - bin->head = bin->head->next; - return; - } - - 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; - } + memory_free(virtual_kernel_dir(), memory_range((u32)ptr, (u32)p)); + return 0; } -static struct h_node *node_best_fit(struct h_bin *bin, u32 size) -{ - if (!bin->head) - return NULL; +#else - struct h_node *temp = bin->head; - while (temp) { - if (temp->size >= size) - return temp; - temp = temp->next; - } - return NULL; -} +#include <sys.h> -/* static struct h_node *node_last(struct h_bin *bin) */ -/* { */ -/* struct h_node *temp = bin->head; */ -/* while (temp->next) */ -/* temp = temp->next; */ -/* return temp; */ -/* } */ +#define sys_alloc(size) (void *)sys1(SYS_ALLOC, size) +#define sys_free(ptr, size) (u32) sys2(SYS_FREE, ptr, size) -static struct h_footer *node_foot(struct h_node *node) +static void *liballoc_alloc(u32 p) { - return (struct h_footer *)((char *)node + sizeof(*node) + node->size); + return sys_alloc((u32)p); } -static void node_create_foot(struct h_node *head) +static int liballoc_free(void *ptr, u32 p) { - struct h_footer *foot = node_foot(head); - foot->header = head; + sys_free((u32)ptr, (u32)p); + return 0; } -static u32 bin_index(u32 sz) +#endif + +static int locked = 0; + +static int liballoc_lock(void) { - 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; + spinlock(&locked); + return 0; } -/* 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; */ -/* } */ - -/* static u32 expand(struct heap *heap, u32 sz) */ -/* { */ -/* (void)heap; */ -/* (void)sz; */ -/* return 0; */ -/* } */ - -/* static u32 contract(struct heap *heap, u32 sz) */ -/* { */ -/* (void)heap; */ -/* (void)sz; */ -/* return 0; */ -/* } */ - -static struct heap heap = { 0 }; -void heap_init(u32 start) +static int liballoc_unlock(void) { - 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 = (u32)start; - heap.end = (u32)start + HEAP_INIT_SIZE; + locked = 0; + return 0; } -#define ALIGN sizeof(long) -static void *_malloc(u32 size) -{ - size = ((size + ALIGN - 1) / ALIGN) * ALIGN; // Alignment - 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 ALIGNMENT 16 +#define ALIGN_UP(__addr, __align) (((__addr) + (__align)-1) & ~((__align)-1)) +#define ALIGN_DOWN(__addr, __align) ((__addr) & ~((__align)-1)) + +#define USE_CASE1 +#define USE_CASE2 +#define USE_CASE3 +#define USE_CASE4 +#define USE_CASE5 +#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; +}; - while (!found) { - assert(index + 1 < BIN_COUNT); +struct liballoc_minor { + struct liballoc_minor *prev; + struct liballoc_minor *next; + struct liballoc_major *block; + u32 magic; + u32 size; + u32 req_size; +}; - temp = &heap.bins[++index]; - found = node_best_fit(temp, size); - } +#define MAJOR_SIZE (ALIGN_UP(sizeof(struct liballoc_major), 16)) +#define MINOR_SIZE (ALIGN_UP(sizeof(struct liballoc_minor), 16)) +#define MIN(__x, __y) ((__x) < (__y) ? (__x) : (__y)) +#define MAX(__x, __y) ((__x) > (__y) ? (__x) : (__y)) - assert(found->magic == HEAP_MAGIC); +static struct liballoc_major *l_mem_root = NULL; +static struct liballoc_major *l_best_bet = NULL; - if ((found->size - size) > (OVERHEAD + MIN_ALLOC_SZ)) { - struct h_node *split = (struct h_node *)(((char *)found + OVERHEAD) + size); - split->magic = HEAP_MAGIC; - split->size = found->size - size - OVERHEAD; - split->hole = 1; +static u32 l_page_size = 4096; +static u32 l_page_count = 16; - node_create_foot(split); +static struct liballoc_major *allocate_new_page(u32 size) +{ + u32 st = size + MAJOR_SIZE + MINOR_SIZE; - u32 new_idx = bin_index(split->size); + if ((st % l_page_size) == 0) + st = st / (l_page_size); + else + st = st / (l_page_size) + 1; - node_add(&heap.bins[new_idx], split); + st = MAX(st, l_page_count); - found->size = size; - node_create_foot(found); - } + struct liballoc_major *maj = (struct liballoc_major *)liballoc_alloc(st * l_page_size); - found->hole = 0; - node_remove(&heap.bins[index], found); + if (maj == NULL) + return NULL; - // 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)); */ - /* } */ + maj->prev = NULL; + maj->next = NULL; + maj->pages = st; + maj->size = st * l_page_size; + maj->usage = MAJOR_SIZE; + maj->first = NULL; - found->prev = NULL; - found->next = NULL; - return &found->next; + return maj; } -static void _free(void *p) +static void *_malloc(u32 req_size) { - if (!p) - return; + req_size = ALIGN_UP(req_size, 16); - struct h_bin *list; - struct h_footer *new_foot, *old_foot; + u32 best_size = 0; + u32 size = req_size; - struct h_node *head = (struct h_node *)((char *)p - 12); - assert(head->magic == HEAP_MAGIC && head->hole == 0); - if (head == (struct h_node *)(u32 *)heap.start) { - head->hole = 1; - node_add(&heap.bins[bin_index(head->size)], head); - return; + liballoc_lock(); + + if (size == 0) { + liballoc_unlock(); + return malloc(1); } - 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 (l_mem_root == NULL) { + l_mem_root = allocate_new_page(size); + if (l_mem_root == NULL) { + liballoc_unlock(); + return NULL; + } + } - if (prev->hole) { - list = &heap.bins[bin_index(prev->size)]; - node_remove(list, prev); + struct liballoc_major *maj = l_mem_root; + u8 started_bet = 0; - prev->size += OVERHEAD + head->size; - new_foot = node_foot(head); - new_foot->header = prev; + if (l_best_bet != NULL) { + best_size = l_best_bet->size - l_best_bet->usage; - head = prev; + if (best_size > (size + MINOR_SIZE)) { + maj = l_best_bet; + started_bet = 1; + } } - if (next->hole) { - list = &heap.bins[bin_index(next->size)]; - node_remove(list, next); + while (maj != NULL) { + u32 diff = maj->size - maj->usage; + if (best_size < diff) { + l_best_bet = maj; + best_size = diff; + } - head->size += OVERHEAD + next->size; +#ifdef USE_CASE1 + if (diff < (size + MINOR_SIZE)) { + if (maj->next != NULL) { + maj = maj->next; + continue; + } - old_foot = node_foot(next); - old_foot->header = 0; - next->size = 0; - next->hole = 0; + if (started_bet == 1) { + maj = l_mem_root; + started_bet = 0; + continue; + } - new_foot = node_foot(head); - new_foot->header = head; - } + maj->next = allocate_new_page(size); + if (maj->next == NULL) + break; + maj->next->prev = maj; + maj = maj->next; + } +#endif - head->hole = 1; - node_add(&heap.bins[bin_index(head->size)], head); -} +#ifdef USE_CASE2 + if (maj->first == NULL) { + maj->first = (struct liballoc_minor *)((u32)maj + MAJOR_SIZE); + + 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 + MINOR_SIZE; + void *p = (void *)((u32)(maj->first) + MINOR_SIZE); + liballoc_unlock(); + return p; + } +#endif + +#ifdef USE_CASE3 + diff = (u32)(maj->first); + diff -= (u32)maj; + diff -= MAJOR_SIZE; + + if (diff >= (size + MINOR_SIZE)) { + maj->first->prev = (struct liballoc_minor *)((u32)maj + MAJOR_SIZE); + 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 + MINOR_SIZE; + void *p = (void *)((u32)(maj->first) + MINOR_SIZE); + liballoc_unlock(); + return p; + } +#endif -#elif defined(userspace) +#ifdef USE_CASE4 + struct liballoc_minor *min = maj->first; + + while (min != NULL) { + if (min->next == NULL) { + diff = (u32)(maj) + maj->size; + diff -= (u32)min; + diff -= MINOR_SIZE; + diff -= min->size; + if (diff >= (size + MINOR_SIZE)) { + min->next = + (struct liballoc_minor *)((u32)min + MINOR_SIZE + + 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 + MINOR_SIZE; + void *p = (void *)((u32)min + MINOR_SIZE); + liballoc_unlock(); + return p; + } + } -#define kmalloc(n) (void *)sys1(SYS_MALLOC, n) -#define kfree(ptr) (void)(sys1(SYS_FREE, (int)ptr)) + if (min->next != NULL) { + diff = (u32)(min->next); + diff -= (u32)min; + diff -= MINOR_SIZE; + diff -= min->size; + + if (diff >= (size + MINOR_SIZE)) { + struct liballoc_minor *new_min = + (struct liballoc_minor *)((u32)min + MINOR_SIZE + + 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 + MINOR_SIZE; + void *p = (void *)((u32)new_min + MINOR_SIZE); + liballoc_unlock(); + return p; + } + } -static void *_malloc(u32 size) -{ - return kmalloc(size); + min = min->next; + } +#endif + +#ifdef USE_CASE5 + if (maj->next == NULL) { + if (started_bet == 1) { + maj = l_mem_root; + started_bet = 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; } static void _free(void *ptr) { - kfree(ptr); + if (ptr == NULL) { + return; + } + + liballoc_lock(); + + struct liballoc_minor *min = (struct liballoc_minor *)((u32)ptr - MINOR_SIZE); + + if (min->magic != LIBALLOC_MAGIC) { + liballoc_unlock(); + return; + } + + struct liballoc_major *maj = min->block; + maj->usage -= (min->size + MINOR_SIZE); + 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; + liballoc_free(maj, maj->pages * l_page_size); + } 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(); } -#endif +static void *_realloc(void *ptr, u32 size) +{ + size = ALIGN_UP(size, 16); + + if (size == 0) { + free(ptr); + return NULL; + } + + if (ptr == NULL) + return malloc(size); + + liballoc_lock(); + struct liballoc_minor *min = (struct liballoc_minor *)((u32)ptr - MINOR_SIZE); + + if (min->magic != LIBALLOC_MAGIC) { + liballoc_unlock(); + return NULL; + } + + if (min->size >= size) { + min->req_size = size; + liballoc_unlock(); + return ptr; + } + + liballoc_unlock(); + + void *new_ptr = malloc(size); + memcpy(new_ptr, ptr, min->req_size); + free(ptr); + + return new_ptr; +} #ifdef kernel #define PREFIX "K" @@ -303,42 +389,18 @@ static void _free(void *ptr) void *zalloc(u32 size) { -#ifdef userspace - panic("AAH!\n"); -#endif void *ret = malloc(size); memset(ret, 0, size); return ret; } -// Naive realloc implementation - TODO! void *realloc(void *ptr, u32 size) { -#ifdef userspace - panic("AAH!\n"); -#endif - if (!ptr) - return malloc(size); - - FUNC("Realloc not implemented!\n"); - return NULL; - /* // This could work; untested - struct h_node *node = (struct h_node *)((char *)ptr - 12); - u32 old_size = node->size; - - void *new = malloc(size); - memcpy(new, ptr, old_size); - - free(ptr); - return new; - */ + return _realloc(ptr, size); } void *malloc_debug(u32 size, const char *file, int line, const char *func, const char *inp) { -#ifdef userspace - panic("AAH!\n"); -#endif assert(size < (100 << 20)); // Don't brag with memory pls void *ret = _malloc(size); @@ -352,9 +414,6 @@ void *malloc_debug(u32 size, const char *file, int line, const char *func, const void free_debug(void *ptr, const char *file, int line, const char *func, const char *inp) { -#ifdef userspace - panic("AAH!\n"); -#endif if (ptr) _free(ptr); diff --git a/libc/inc/mem.h b/libc/inc/mem.h index e93f4d2..ec00628 100644 --- a/libc/inc/mem.h +++ b/libc/inc/mem.h @@ -15,9 +15,6 @@ void *zalloc(u32 size); #ifdef kernel #define STACK_START 0x00500000 // Defined it bootloader #define STACK_SIZE 0x1000 // idk -#define HEAP_START 0x00f00000 -#define HEAP_INIT_SIZE 0x0f00000 -void heap_init(u32 start); #elif defined(userspace) #else #error "No lib target specified. Please use -Dkernel or -Duserspace" diff --git a/libc/inc/sys.h b/libc/inc/sys.h index c20eabc..c100e6a 100644 --- a/libc/inc/sys.h +++ b/libc/inc/sys.h @@ -11,7 +11,7 @@ enum sys { SYS_LOOP, // To infinity and beyond (debug)! - SYS_MALLOC, // Allocate memory + SYS_ALLOC, // Allocate memory SYS_FREE, // Free memory SYS_STAT, // Get file information SYS_READ, // Read file |