diff options
Diffstat (limited to 'lib/libjove')
| -rw-r--r-- | lib/libjove/Makefile | 4 | ||||
| -rw-r--r-- | lib/libjove/arch/x86_64/libjove.c | 14 | ||||
| -rw-r--r-- | lib/libjove/heap/heap.c | 142 | ||||
| -rw-r--r-- | lib/libjove/heap/heap.h | 19 | ||||
| -rw-r--r-- | lib/libjove/include/arch/x86_64/jove.h | 6 | ||||
| -rw-r--r-- | lib/libjove/libjove.c | 34 |
6 files changed, 217 insertions, 2 deletions
diff --git a/lib/libjove/Makefile b/lib/libjove/Makefile index b82de22..9633c85 100644 --- a/lib/libjove/Makefile +++ b/lib/libjove/Makefile @@ -1,6 +1,6 @@ include $(CONFIG) -CDIRS := syscall object pager +CDIRS := syscall object pager heap CFILES := $(wildcard *.c) CFILES += $(foreach dir,$(CDIRS),$(wildcard $(dir)/*.c)) @@ -9,7 +9,7 @@ CFILES += $(foreach dir,$(CDIRS),$(wildcard arch/$(TARGET_MACHINE)/$(dir)/*.c)) OFILES := $(patsubst %.c,%.o,$(CFILES)) -CFLAGS := -ffreestanding -nostdlib -Iinclude -g +CFLAGS := -Iinclude -Wall -Wextra all: ${OFILES} ar rcs $(OUT)/libjove.a $(OFILES) diff --git a/lib/libjove/arch/x86_64/libjove.c b/lib/libjove/arch/x86_64/libjove.c new file mode 100644 index 0000000..0abc6b6 --- /dev/null +++ b/lib/libjove/arch/x86_64/libjove.c @@ -0,0 +1,14 @@ +#include "jove.h" +#include "arch/x86_64/pager.h" + +void +__libjove_arch_init(void) +{ + +} + +void +__libjove_pager_init(uint8_t pml_obji) +{ + _jove_alloc_pagemap_inplace(&__jove_pagemap, &__rootdir, pml_obji); +} diff --git a/lib/libjove/heap/heap.c b/lib/libjove/heap/heap.c new file mode 100644 index 0000000..ab313ae --- /dev/null +++ b/lib/libjove/heap/heap.c @@ -0,0 +1,142 @@ +#include "heap.h" +#include <jove/memory.h> +#include <jove/jove.h> +#include <stdlib.h> +#include <string.h> + +static heap_bin_t *freelist_tail; + +uintptr_t __heap_start; +uintptr_t __heap_end; + +#define HEAP_BIN_SIZE(bin) (bin->size_taken & (~1ULL)) +#define HEAP_BIN_TAKEN(bin) (bin->size_taken & 1) + +#define HEAP_BIN_AFTER(bin) ((heap_bin_t*)((uintptr_t)bin->data + HEAP_BIN_SIZE(bin) + sizeof(uintptr_t))) +#define HEAP_BIN_BEFORE(bin) ((heap_bin_t*)*((uintptr_t*)bin - 1)) + +static void +heap_grow(uintptr_t to) +{ + jove_mem_ensure_range(__heap_end, to); + __heap_end = to; +} + +static heap_bin_t* +heap_newbin(uintptr_t at, size_t size, heap_bin_t *next) +{ + uintptr_t headat = (at + sizeof(heap_bin_t) + size); + uintptr_t endat = headat + sizeof(uintptr_t); + + if(endat > __heap_end) heap_grow(endat); + + heap_bin_t *newbin = (heap_bin_t*)at; + newbin->size_taken = size; + newbin->next = next; + + *((uintptr_t*)headat) = at; + return newbin; +} + +static heap_bin_t* +heap_find_bestfit(size_t rsize) +{ + heap_bin_t *best = freelist_tail; + if(best == NULL) return NULL; + size_t bestsize = best->size_taken; + + for(heap_bin_t *bin = best->next; bin; bin = bin->next) + { + if(bin->size_taken < rsize) continue; + if(bin->size_taken < bestsize) { + best = bin; + bestsize = bin->size_taken; + } + } + return best; +} + +static void +heap_split(heap_bin_t *bin, size_t splitsize) +{ + size_t size_diff = bin->size_taken - splitsize; + if(size_diff < LIBC_HEAP_MINSPLIT) return; + + size_t newsize = size_diff - sizeof(heap_bin_t) - sizeof(uintptr_t); + uintptr_t newat = ((uintptr_t)bin->data) + splitsize + sizeof(uintptr_t); + jove_kprintf("Split %p to %p [%x]\n", bin, newat, newsize); + + bin->size_taken = splitsize; + freelist_tail = heap_newbin(newat, newsize, freelist_tail); +} + +static void* +heap_alloc(size_t size) +{ + if(size & 1) size++; + if(size < LIBC_HEAP_MINALLOC) size = LIBC_HEAP_MINALLOC; + + heap_bin_t *bestfit = heap_find_bestfit(size); + if(bestfit == NULL) { + bestfit = heap_newbin(__heap_end, size, NULL); + }else{ + if(bestfit == freelist_tail) { + freelist_tail = bestfit->next; + } + size_t bestsize = bestfit->size_taken; + + if(bestsize < size) { + jove_kprintf("Growing bin %p [%x] to %x\n", bestfit, bestsize, size); + heap_newbin((uintptr_t)bestfit, size, NULL); + }else if(bestsize > size) { + heap_split(bestfit, size); + } + } + bestfit->size_taken |= 1; + return bestfit->data; +} + +static void +heap_free(void *ptr) +{ + uintptr_t binptr = (uintptr_t)ptr - sizeof(heap_bin_t); + if(binptr > __heap_end || binptr < __heap_start) return; + + heap_bin_t *bin = (heap_bin_t*)binptr; + bin->size_taken &= ~1ULL; + bin->next = freelist_tail; + freelist_tail = bin; + +start_merge_loop: { + heap_bin_t *prevbin = HEAP_BIN_BEFORE(bin); + heap_bin_t *nextbin = HEAP_BIN_AFTER(bin); + + if((uintptr_t)prevbin >= __heap_start) { + if(!HEAP_BIN_TAKEN(prevbin)) { + jove_kprintf("Merge back bin %p into %p\n", bin, prevbin); + freelist_tail = prevbin; + prevbin->size_taken += bin->size_taken + sizeof(heap_bin_t) + sizeof(uintptr_t); + bin = prevbin; + goto start_merge_loop; + } + } + if((uintptr_t)nextbin < __heap_end) { + if(!HEAP_BIN_TAKEN(nextbin)) { + jove_kprintf("Merge forward bin %p into %p\n", bin, nextbin); + if(bin->next == nextbin) bin->next = nextbin->next; + bin->size_taken += nextbin->size_taken + sizeof(heap_bin_t) + sizeof(uintptr_t); + goto start_merge_loop; + } + } + } +} + +void +__libjove_heap_init(uintptr_t program_end) +{ + __heap_start = __heap_end = program_end; + freelist_tail = heap_newbin(__heap_start, LIBC_HEAP_INIT_SIZE, NULL); + + __libc_malloc = heap_alloc; + __libc_free = heap_free; +} diff --git a/lib/libjove/heap/heap.h b/lib/libjove/heap/heap.h new file mode 100644 index 0000000..8a02655 --- /dev/null +++ b/lib/libjove/heap/heap.h @@ -0,0 +1,19 @@ +#ifndef _LIBC_JOVE_HEAP_H +#define _LIBC_JOVE_HEAP_H 1 + +#include <stdint.h> +#include <stddef.h> + +#define LIBC_HEAP_INIT_SIZE (0x1000) +#define LIBC_HEAP_MINALLOC (0x10) +#define LIBC_HEAP_MINSPLIT (sizeof(heap_bin_t) + sizeof(uintptr_t) + LIBC_HEAP_MINALLOC) + +typedef struct heap_bin { + struct heap_bin *next; + size_t size_taken; + char data[]; +} heap_bin_t; + +void __libjove_heap_init(uintptr_t program_end); + +#endif diff --git a/lib/libjove/include/arch/x86_64/jove.h b/lib/libjove/include/arch/x86_64/jove.h new file mode 100644 index 0000000..36303f4 --- /dev/null +++ b/lib/libjove/include/arch/x86_64/jove.h @@ -0,0 +1,6 @@ +#ifndef _JOVE_x86_64_JOVE_H +#define _JOVE_x86_64_JOVE_H 1 + + + +#endif diff --git a/lib/libjove/libjove.c b/lib/libjove/libjove.c index 6b40a54..ef5d7e6 100644 --- a/lib/libjove/libjove.c +++ b/lib/libjove/libjove.c @@ -1,6 +1,7 @@ #include "include/jove.h" #include "include/object-untyped.h" #include "error.h" +#include "heap/heap.h" uintmax_t __jove_syscall_obj = 0; void *__jove_syscall_ptr = 0; @@ -15,3 +16,36 @@ uintptr_t __program_end; void *(*_jove_alloc)(size_t) = NULL; void (*_jove_free)(void*) = NULL; void *(*_jove_realloc)(void*, size_t) = NULL; + +extern void __libjove_arch_init(void); + +void +__libjove_init(uint8_t syscall_obj, void *syscall_ptr) +{ + __rootdir = (KernelObjectDirectory) { + .typed = { + .type = KO_OBJECT_DIRECTORY, + .membi = 0, + .parent = NULL + }, + .firstfree = -1, + .lastmemb = -1 + }; + + __jove_syscall_obj = syscall_obj; + __jove_syscall_ptr = syscall_ptr; + + __jove_work_obj = (KernelObjectTyped) { + .membi = jove_objdir_lastmemb(&__rootdir), + .parent = &__rootdir, + .type = KO_NONE + }; + + __libjove_arch_init(); +} + +void +__libjove_init_untypeddir(uint8_t diri) +{ + _jove_alloc_objdir_inplace(&__jove_untyped_directory, &__rootdir, diri); +} |