From f0248ad1724f9fbdd372db4da8ee8f956ae6aacd Mon Sep 17 00:00:00 2001 From: Jon Santmyer Date: Sun, 24 Aug 2025 16:05:30 -0400 Subject: libc heap impl --- apps/init/arch/x86_64/link.ld | 1 + apps/init/arch/x86_64/paging.c | 2 - apps/init/main.c | 5 +- config.mk | 5 +- initrd/files/bin/init | Bin 16656 -> 20784 bytes lib/libc-jove/Makefile | 15 ++++ lib/libc-jove/stdlib/heap.c | 139 ++++++++++++++++++++++++++++++++ lib/libc-jove/stdlib/heap.h | 19 +++++ lib/libjove/arch/x86_64/pager/ensure.c | 28 ++++++- lib/libjove/include/arch/x86_64/pager.h | 3 + lib/libjove/include/memory.h | 15 ++++ lib/libjove/memory.c | 23 ++++++ sysroot/boot/initrd.tar | Bin 20480 -> 30720 bytes 13 files changed, 246 insertions(+), 9 deletions(-) create mode 100644 lib/libc-jove/Makefile create mode 100644 lib/libc-jove/stdlib/heap.c create mode 100644 lib/libc-jove/stdlib/heap.h create mode 100644 lib/libjove/include/memory.h create mode 100644 lib/libjove/memory.c diff --git a/apps/init/arch/x86_64/link.ld b/apps/init/arch/x86_64/link.ld index 45b08f5..79da5cb 100644 --- a/apps/init/arch/x86_64/link.ld +++ b/apps/init/arch/x86_64/link.ld @@ -7,4 +7,5 @@ SECTIONS . = 0x1000; .text BLOCK(PAGESIZE) : ALIGN(PAGESIZE) { *(.text.start) *(.text) *(.rodata) } .data BLOCK(PAGESIZE) : ALIGN(PAGESIZE) { *(.data) *(.bss) } + __program_end = .; } diff --git a/apps/init/arch/x86_64/paging.c b/apps/init/arch/x86_64/paging.c index 641fc8a..36fe950 100644 --- a/apps/init/arch/x86_64/paging.c +++ b/apps/init/arch/x86_64/paging.c @@ -13,6 +13,4 @@ pager_setup(void) size_t lastfree = jove_objdir_lastmemb(&__rootdir) + 1; __jove_work_obj.membi = lastfree; __jove_work_obj.parent = &__rootdir; - - jove_pager_ensure(0x00000000F0000000); } diff --git a/apps/init/main.c b/apps/init/main.c index 9ed2579..6deb12c 100644 --- a/apps/init/main.c +++ b/apps/init/main.c @@ -1,5 +1,3 @@ -#include -#include #include #include #include @@ -16,6 +14,8 @@ spin_fail(void) for(;;); } +extern void __libc_heap_init(uintptr_t); + void main(void *message_ptr) { @@ -25,6 +25,7 @@ main(void *message_ptr) jove_kprintf("Hello, Userland!\n"); pager_setup(); + __libc_heap_init((uintptr_t)message_ptr + KO_MESSAGE_BYTES); for(;;); } diff --git a/config.mk b/config.mk index 1659c3a..f01a853 100644 --- a/config.mk +++ b/config.mk @@ -17,8 +17,9 @@ TARGET_BOOTLOADER = limine APPS := $(INITRDDIR)/files/bin/init -STATICLIBS := $(SYSROOTDIR)/lib/libjove.a \ - $(SYSROOTDIR)/lib/libc-headless.a +STATICLIBS := $(SYSROOTDIR)/lib/libc-jove.a \ + $(SYSROOTDIR)/lib/libjove.a \ + $(SYSROOTDIR)/lib/libc-headless.a \ CC := $(TOOLSDIR)/bin/$(TARGET_TRIPLET)-gcc LD := $(TOOLSDIR)/bin/$(TARGET_TRIPLET)-ld diff --git a/initrd/files/bin/init b/initrd/files/bin/init index e76918a..575c604 100755 Binary files a/initrd/files/bin/init and b/initrd/files/bin/init differ diff --git a/lib/libc-jove/Makefile b/lib/libc-jove/Makefile new file mode 100644 index 0000000..a084ca6 --- /dev/null +++ b/lib/libc-jove/Makefile @@ -0,0 +1,15 @@ +include $(CONFIG) + +CDIRS := stdio ctype string stdlib + +CFILES += $(foreach dir,$(CDIRS),$(wildcard $(dir)/*.c)) + +OFILES := $(patsubst %.c,%.o,$(CFILES)) + +CFLAGS := -ffreestanding -nostdlib + +all: ${OFILES} + ar rcs $(OUT)/libc-jove.a $(OFILES) + +%.o:%.c + $(CC) $(CFLAGS) -c $< -o $@ diff --git a/lib/libc-jove/stdlib/heap.c b/lib/libc-jove/stdlib/heap.c new file mode 100644 index 0000000..034278c --- /dev/null +++ b/lib/libc-jove/stdlib/heap.c @@ -0,0 +1,139 @@ +#include "heap.h" +#include +#include +#include +#include + +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 +__libc_heap_init(uintptr_t program_end) +{ + __heap_start = __heap_end = program_end; + freelist_tail = heap_newbin(__heap_start, LIBC_HEAP_INIT_SIZE, NULL); +} diff --git a/lib/libc-jove/stdlib/heap.h b/lib/libc-jove/stdlib/heap.h new file mode 100644 index 0000000..9628444 --- /dev/null +++ b/lib/libc-jove/stdlib/heap.h @@ -0,0 +1,19 @@ +#ifndef _LIBC_JOVE_HEAP_H +#define _LIBC_JOVE_HEAP_H 1 + +#include +#include + +#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 __libc_heap_init(uintptr_t program_end); + +#endif diff --git a/lib/libjove/arch/x86_64/pager/ensure.c b/lib/libjove/arch/x86_64/pager/ensure.c index bfe68ff..874db35 100644 --- a/lib/libjove/arch/x86_64/pager/ensure.c +++ b/lib/libjove/arch/x86_64/pager/ensure.c @@ -18,7 +18,7 @@ pager_write_path(uintptr_t vptr, uint8_t depth) if(depth >= 4) return -1; uint16_t *path = (uint16_t*)&r; - for(uint8_t i = 0; i < depth; i++) path[i] = PMLI_DL(vptr, i); + for(uint8_t i = 0; i < depth + 1; i++) path[i] = PMLI_DL(vptr, i); return r; } @@ -70,10 +70,10 @@ pager_ensure_at_depth(KernelObjectPageMap *map, uint8_t depth, uint16_t *path) JoveError jove_pager_ensure_for(KernelObjectPageMap *map, uintptr_t vptr) { + vptr &= ~0xFFFULL; + uint64_t path = pager_write_path(vptr, 3); if(path == -1) return EJOVE_BADARG; - - vptr &= ~0xFFFULL; uint16_t *path_seg = (uint16_t*)&path; jove_kprintf("%p Alloc %p : %x:%x:%x:%x\n", map, vptr, path_seg[0], path_seg[1], path_seg[2], path_seg[3]); @@ -86,3 +86,25 @@ jove_pager_ensure_for(KernelObjectPageMap *map, uintptr_t vptr) } return EJOVE_OK; } + +#define PAGER_CACHE_EXISTS_DEPTH(map, path_seg, d) \ + if(path_seg[d] != d_cache[d]) { \ + if(!jove_pagemap_exists(map, d, path_seg)) return 0; \ + d_cache[d] = path_seg[d]; \ + } + + +int +jove_pager_exists_for(KernelObjectPageMap *map, uintptr_t vptr) +{ + vptr &= ~0xFFFULL; + + uint64_t path = pager_write_path(vptr, 3); + if(path == -1) return EJOVE_BADARG; + uint16_t *path_seg = (uint16_t*)&path; + + PAGER_CACHE_EXISTS_DEPTH(map, path_seg, 0); + PAGER_CACHE_EXISTS_DEPTH(map, path_seg, 1); + PAGER_CACHE_EXISTS_DEPTH(map, path_seg, 2); + return jove_pagemap_exists(map, 3, path_seg); +} diff --git a/lib/libjove/include/arch/x86_64/pager.h b/lib/libjove/include/arch/x86_64/pager.h index 7e47ed1..2a53a07 100644 --- a/lib/libjove/include/arch/x86_64/pager.h +++ b/lib/libjove/include/arch/x86_64/pager.h @@ -9,4 +9,7 @@ extern KernelObjectPageMap __jove_pagemap; JoveError jove_pager_ensure_for(KernelObjectPageMap *map, uintptr_t vptr); #define jove_pager_ensure(vptr) jove_pager_ensure_for(&__jove_pagemap, vptr) +int jove_pager_exists_for(KernelObjectPageMap *map, uintptr_t vptr); +#define jove_pager_exists(vptr) jove_pager_exists_for(&__jove_pagemap, vptr); + #endif diff --git a/lib/libjove/include/memory.h b/lib/libjove/include/memory.h new file mode 100644 index 0000000..9d4ce1d --- /dev/null +++ b/lib/libjove/include/memory.h @@ -0,0 +1,15 @@ +#ifndef _LIBJOVE_MEMORY_H +#define _LIBJOVE_MEMORY_H 1 + +#include + +#ifdef __x86_64__ +#include +#define jove_mem_ensure(vptr) jove_pager_ensure(vptr) +#define jove_mem_exists(vptr) jove_pager_exists(vptr) +#endif + +JoveError jove_mem_ensure_range(uintptr_t start, uintptr_t end); +JoveError jove_mem_ensure_w(uintptr_t start, size_t pages); + +#endif diff --git a/lib/libjove/memory.c b/lib/libjove/memory.c new file mode 100644 index 0000000..db76528 --- /dev/null +++ b/lib/libjove/memory.c @@ -0,0 +1,23 @@ +#include + +JoveError +jove_mem_ensure_w(uintptr_t start, size_t pages) +{ + start &= ~0xFFFULL; + for(size_t i = 0; i < pages; i++) { + uintptr_t at = start + (i << 12); + JoveError e = jove_mem_ensure(at); + if(e) return e; + } + return EJOVE_OK; +} + +JoveError +jove_mem_ensure_range(uintptr_t start, uintptr_t end) +{ + start &= ~0xFFFULL; + if(end & 0xFFF) + end += 0x1000 - (end & 0xFFF); + + return jove_mem_ensure_w(start, (end - start) >> 12); +} diff --git a/sysroot/boot/initrd.tar b/sysroot/boot/initrd.tar index 8b6baa4..20f2641 100644 Binary files a/sysroot/boot/initrd.tar and b/sysroot/boot/initrd.tar differ -- cgit v1.2.1