summaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/libc-jove/Makefile15
-rw-r--r--lib/libc-jove/stdlib/heap.c139
-rw-r--r--lib/libc-jove/stdlib/heap.h19
-rw-r--r--lib/libjove/arch/x86_64/pager/ensure.c28
-rw-r--r--lib/libjove/include/arch/x86_64/pager.h3
-rw-r--r--lib/libjove/include/memory.h15
-rw-r--r--lib/libjove/memory.c23
7 files changed, 239 insertions, 3 deletions
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 <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
+__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 <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 __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 <jove/error.h>
+
+#ifdef __x86_64__
+#include <jove/arch/x86_64/pager.h>
+#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 <jove/memory.h>
+
+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);
+}
generated by cgit v1.2.1 (git 2.18.0) at 2025-08-29 18:24:24 +0000