From d1ff7bcc91886626dc9060ec5fb67ee102ab7c1d Mon Sep 17 00:00:00 2001 From: Jon Santmyer Date: Mon, 11 Mar 2024 21:30:31 -0400 Subject: usermode capable kernel with logging syscall --- mem/buddymap.c | 151 +++++++++++++++++++++++++++++++++++++++++++ mem/buddymap.d | 2 + mem/buddymap.h | 21 ++++++ mem/memory.h | 49 ++++++++++++++ mem/phys.c | 14 ++++ mem/phys.d | 1 + mem/slab.c | 201 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ mem/slab.d | 2 + mem/slab.h | 33 ++++++++++ 9 files changed, 474 insertions(+) create mode 100644 mem/buddymap.c create mode 100644 mem/buddymap.d create mode 100644 mem/buddymap.h create mode 100644 mem/memory.h create mode 100644 mem/phys.c create mode 100644 mem/phys.d create mode 100644 mem/slab.c create mode 100644 mem/slab.d create mode 100644 mem/slab.h (limited to 'mem') diff --git a/mem/buddymap.c b/mem/buddymap.c new file mode 100644 index 0000000..5165876 --- /dev/null +++ b/mem/buddymap.c @@ -0,0 +1,151 @@ +#include "buddymap.h" +#include "lib/string.h" +#include "boot/boot.h" +#include "io/log.h" +#include + +#define ENTRY_BITS (sizeof(uintmax_t) * 8) +#define ENTRY_SIZE (ENTRY_BITS * PAGESIZE) +#define ENTRY_COUNT (MEMMAP_BUDDY_LIMIT / ENTRY_SIZE) +#define BUDDY_LAYERS 4 + +uintmax_t s_buddy_l0[ENTRY_COUNT]; +uintmax_t s_buddy_l1[ENTRY_COUNT << 1]; +uintmax_t s_buddy_l2[ENTRY_COUNT << 2]; +uintmax_t s_buddy_l3[ENTRY_COUNT << 3]; +uintmax_t *s_buddies[BUDDY_LAYERS] = { + s_buddy_l0, + s_buddy_l1, + s_buddy_l2, + s_buddy_l3 +}; +size_t s_buddies_lastfree[BUDDY_LAYERS] = { 1, 1, 1, 1 }; + +static bool +s_buddy_test(size_t l, size_t i) +{ + return (s_buddies[l][i / (ENTRY_BITS)] & (1ULL << (i % (ENTRY_BITS)))) > 0; +} + +static void +s_buddy_set(size_t l, size_t i) +{ + size_t j = i << l; + size_t w = 1 << l; + for(int layer = 0; layer < BUDDY_LAYERS; layer++) + { + if(w == 0) w = 1; + for(size_t bit = 0; bit < w; bit++) { + size_t entry = (j + bit) / ENTRY_BITS; + s_buddies[layer][entry] |= (1ULL << (j + bit % ENTRY_BITS)); + } + j >>= 1; + w >>= 1; + } +} + +static void +s_buddy_unset(size_t l, size_t i) +{ + size_t j = i << l; + size_t w = 1 << l; + bool free_upper = false; + for(int layer = 0; layer < BUDDY_LAYERS; layer++) + { + if(w == 0) { + size_t lower = (j << 1) % ENTRY_BITS; + size_t other = (lower + 1); + size_t entry = (j << 1) / ENTRY_BITS; + if((s_buddies[layer-1][entry] & (1ULL << lower)) > 0 && + (s_buddies[layer-1][entry] & (1ULL << other)) > 0) + s_buddies[layer][entry >> 1] &= ~(1ULL << (j % ENTRY_BITS)); + } + + for(size_t bit = 0; bit < w; bit++) { + size_t entry = j / ENTRY_BITS; + s_buddies[layer][entry] |= (1ULL << bit); + } + j >>= 1; + w >>= 1; + } +} + +void +mem_buddy_set_range(uintptr_t base, size_t length) +{ + for(int l = 0; l < BUDDY_LAYERS; l++) { + size_t bits = (length / PAGESIZE) >> l; + size_t biti = (base / PAGESIZE) >> l; + + if(bits == 0) bits = 1; + for(size_t i = 0; i < bits; i++) { + size_t entry = (biti + i) / ENTRY_BITS; + s_buddies[l][entry] |= 1ULL << ((biti + i) % ENTRY_BITS); + } + } +} + +void +mem_buddy_free_range(uintptr_t base, size_t length) +{ + for(int l = 0; l < BUDDY_LAYERS; l++) { + size_t bits = (length / PAGESIZE) >> l; + size_t biti = (base / PAGESIZE) >> l; + size_t bitbase = (biti * PAGESIZE) << l; + + if(bits == 0) continue; + for(size_t i = 0; i < bits; i++, bitbase += (PAGESIZE << l)) { + if(bitbase < base) continue; + size_t entry = (biti + i) / ENTRY_BITS; + s_buddies[l][entry] &= ~(1ULL << ((biti+ i) % ENTRY_BITS)); + } + } +} + + +uintptr_t +mem_buddy_takefree(size_t l) +{ + uintmax_t *layer = s_buddies[l]; + size_t lastfree = s_buddies_lastfree[l]; + if(s_buddy_test(l, lastfree)) lastfree = 0; + size_t entries = ENTRY_COUNT >> l; + for(size_t i = lastfree / ENTRY_BITS; i < entries; i++) { + uintmax_t entry = layer[i]; + if(entry == (uintmax_t)-1LL) continue; + for(size_t j = 0; j < ENTRY_BITS; j++) { + if((entry & (1ULL << j)) == 0) { + size_t bit = (i * ENTRY_BITS) + j; + s_buddies_lastfree[l] = bit + 1; + s_buddy_set(l, bit); + return bit * (PAGESIZE << l); + } + } + } + return 0; +} + +void +mem_buddy_setup() +{ + memset(s_buddy_l0, 0xFF, sizeof(s_buddy_l0)); + memset(s_buddy_l1, 0xFF, sizeof(s_buddy_l1)); + memset(s_buddy_l2, 0xFF, sizeof(s_buddy_l2)); + memset(s_buddy_l3, 0xFF, sizeof(s_buddy_l3)); + + for(int i = 0; i < boot_memorymap.count; i++) { + struct MemoryMapEntry *entry = &boot_memorymap.entries[i]; + klogf("%2i\t%#016X -> %#016X (%i)\n", + i, entry->base, entry->base + entry->length, entry->usable); + if(entry->base > MEMMAP_BUDDY_LIMIT) continue; + size_t length = entry->length; + if(entry->base + length > MEMMAP_BUDDY_LIMIT) length = MEMMAP_BUDDY_LIMIT - (entry->base + length); + if(entry->usable) + mem_buddy_free_range(entry->base, entry->length); + } + + s_buddies[0][0] |= 1; + s_buddies[1][0] |= 1; + s_buddies[2][0] |= 1; + s_buddies[3][0] |= 1; +} diff --git a/mem/buddymap.d b/mem/buddymap.d new file mode 100644 index 0000000..7132cfe --- /dev/null +++ b/mem/buddymap.d @@ -0,0 +1,2 @@ +mem/buddymap.o: mem/buddymap.c mem/buddymap.h mem/memory.h mem/slab.h \ + lib/string.h boot/boot.h io/log.h diff --git a/mem/buddymap.h b/mem/buddymap.h new file mode 100644 index 0000000..2f4f5dc --- /dev/null +++ b/mem/buddymap.h @@ -0,0 +1,21 @@ +#ifndef JOVE_MEMORY_BUDDYMAP_H +#define JOVE_MEMORY_BUDDYMAP_H 1 + +#include "memory.h" +#include +#include + +#define MEMMAP_BUDDY_LIMIT (4 * GiB) + +void mem_buddy_set_range(uintptr_t base, size_t length); +void mem_buddy_free_range(uintptr_t base, size_t length); +uintptr_t mem_buddy_takefree(size_t layer); + +#define mem_buddy_takefree_4k() mem_buddy_takefree(0) +#define mem_buddy_takefree_8k() mem_buddy_takefree(1) +#define mem_buddy_takefree_16k() mem_buddy_takefree(2) +#define mem_buddy_takefree_32k() mem_buddy_takefree(3) + +void mem_buddy_setup(void); + +#endif diff --git a/mem/memory.h b/mem/memory.h new file mode 100644 index 0000000..eb30217 --- /dev/null +++ b/mem/memory.h @@ -0,0 +1,49 @@ +#ifndef JOVE_MEM_H +#define JOVE_MEM_H 1 + +#define PAGESIZE 4096ULL +#define KiB 1024ULL +#define MiB (KiB * KiB) +#define GiB (MiB * KiB) +#define TiB (GiB * KiB) + +#include +#include +#include +typedef uintptr_t physptr_t; + +#include "slab.h" + +/*Linear*/ +void mem_paging_setup(void); + +physptr_t mem_linear_tophys(uintptr_t virt); + +/**Check if pointer is within valid memory. + * @param ptr pointer to check. + * @return if the pointer is invalid.*/ +bool mem_check_ptr(const void *ptr); + +/**Make sure the range indicated is available in memory. + * If necessary, allocate new pages using the passed flags + * @param from start of the range. + * @param to end of the range. + * @param rw flag to mark page is writeable. + * @param user flag to mark page as user accessable*/ +void mem_ensure_range(uintptr_t from, uintptr_t to, bool rw, bool user); + +void mem_slab_setup(void); +void mem_slabcache_new(struct SlabCache *cache, char *name, size_t objsize); + +void* mem_slab_alloc(struct SlabCache *cache); +void mem_slab_free(struct SlabCache *cache, void *ptr); + +void* mem_alloc(size_t width); +void mem_free(void *ptr); + +/*Physical*/ + +physptr_t mem_phys_take4k(void); +void mem_phys_reserve(physptr_t start, size_t len); + +#endif diff --git a/mem/phys.c b/mem/phys.c new file mode 100644 index 0000000..e56a4d6 --- /dev/null +++ b/mem/phys.c @@ -0,0 +1,14 @@ +#include "memory.h" +#include "buddymap.h" + +physptr_t +mem_phys_take4k(void) +{ + return mem_buddy_takefree_4k(); +} + +void +mem_phys_reserve(physptr_t start, size_t len) +{ + mem_buddy_set_range(start, len); +} diff --git a/mem/phys.d b/mem/phys.d new file mode 100644 index 0000000..192b714 --- /dev/null +++ b/mem/phys.d @@ -0,0 +1 @@ +mem/phys.o: mem/phys.c mem/memory.h mem/slab.h mem/buddymap.h diff --git a/mem/slab.c b/mem/slab.c new file mode 100644 index 0000000..75b8302 --- /dev/null +++ b/mem/slab.c @@ -0,0 +1,201 @@ +#include "slab.h" +#include "memory.h" +#include "lib/format.h" +#include "lib/string.h" +#include "lib/jove.h" +#include "io/log.h" + +extern void *_kernel_end; + +static uintptr_t s_addr_next_free; + +#define GENERIC_CACHEC 8 +static struct SlabCache s_generic_caches[GENERIC_CACHEC]; + +static uintptr_t +s_next_free(size_t width) +{ + uintptr_t ret = s_addr_next_free; + s_addr_next_free += width; + mem_ensure_range(ret, s_addr_next_free, true, false); + return ret; +} + +static int +s_get_free_listw(size_t slabw, size_t objw) +{ + int freelistc = 1; + while(freelistc < 256) { + int maxobjc = (slabw - (freelistc * sizeof(uintptr_t))) / objw; + if(maxobjc <= freelistc) return maxobjc; + freelistc++; + } + return freelistc; +} + +static struct SlabDescriptor +*s_slab_new(struct SlabCache *cache, struct SlabDescriptor *last) +{ + size_t slab_width = (cache->slab_pages * PAGESIZE); + uintptr_t descr_base = s_next_free(slab_width); + struct SlabDescriptor *descr = (struct SlabDescriptor*)descr_base; + + size_t free_listc = s_get_free_listw( + slab_width - sizeof(struct SlabDescriptor), + cache->obj_size); + size_t descriptor_width = sizeof(struct SlabDescriptor) + + (free_listc * sizeof(uintptr_t)); + uintptr_t obj_base = descr_base + descriptor_width; + + if(free_listc < 8) { + free_listc = ((slab_width - sizeof(struct SlabDescriptor)) / cache->obj_size); + descr = mem_alloc(sizeof(struct SlabDescriptor) + (free_listc * sizeof(uintptr_t))); + obj_base = descr_base; + } + + *descr = (struct SlabDescriptor) { + .prev = last, + .next = (last == NULL ? NULL : last->next), + .slab_base = (void*)descr_base, + .obj_base = (void*)obj_base, + .free_count = free_listc, + .free_index = free_listc - 1 + }; + for(size_t i = 0; i < free_listc; i++) { + descr->free[i] = obj_base + (i * cache->obj_size); + } + + return descr; +} + +void +mem_slabcache_new(struct SlabCache *cache, char *name, size_t objsize) +{ + if(objsize % 8 > 0) objsize += (8 - (objsize % 8)); + size_t pages = objsize > 512 ? (objsize >> 9) : 1; + *cache = (struct SlabCache){ + .obj_size = objsize, + .slab_pages = pages, + .list_free = NULL, + .list_partial = NULL, + .list_full = NULL + }; + size_t namelen = strlen(name); + namelen = namelen > 32 ? 32 : namelen; + memcpy(cache->name, name, namelen); + + //Allocate the first slab + cache->list_free = s_slab_new(cache, NULL); +} + +void* +mem_slab_alloc(struct SlabCache *cache) +{ + // Get a free slab + struct SlabDescriptor *slab = NULL; + if(cache->list_partial != NULL) slab = cache->list_partial; + if(slab == NULL && cache->list_free != NULL) { + slab = cache->list_free; + cache->list_free = slab->next; + } + if(slab == NULL) slab = s_slab_new(cache, cache->list_free); + cache->list_partial = slab; + + // Take an object from the slab. + uintptr_t objaddr = slab->free[slab->free_index]; + slab->free_index -= 1; + + if(slab->free_index < 0) { + slab->next = cache->list_full; + cache->list_full = slab; + } + return (void*)objaddr; +} + +void +mem_slab_free(struct SlabCache *cache, void *ptr) +{ + uintptr_t addr = (uintptr_t)ptr; + //Look for the pointer in the bounds of every slab + for(struct SlabDescriptor *slab = cache->list_full; + slab != NULL; slab = slab->next) + { + uintptr_t base = (uintptr_t)slab->obj_base; + uintptr_t limit = ((uintptr_t)slab->slab_base) + + (cache->slab_pages * PAGESIZE); + if(addr > limit || addr < base) continue; + if((addr - base) % cache->obj_size != 0) { + klogf("Tried to free offset pointer %#016X in slab %s\n", + addr, cache->name); + return; + } + slab->free_index++; + slab->free[slab->free_index] = addr; + + cache->list_full = slab->next; + slab->next = cache->list_partial; + cache->list_partial = slab; + return; + } + for(struct SlabDescriptor *slab = cache->list_partial; + slab != NULL; slab = slab->next) + { + uintptr_t base = (uintptr_t)slab->obj_base; + uintptr_t limit = ((uintptr_t)slab->slab_base) + + (cache->slab_pages * PAGESIZE); + if(addr > limit || addr < base) continue; + if((addr - base) % cache->obj_size != 0) { + klogf("Tried to free offset pointer %#016X in slab %s\n", + addr, cache->name); + return; + } + slab->free_index++; + slab->free[slab->free_index] = addr; + + if(slab->free_index == (slab->free_count - 1)) { + cache->list_partial = slab->next; + slab->next = cache->list_free; + cache->list_free = slab; + } + return; + } +} + +void* +mem_alloc(size_t width) +{ + size_t width_log2 = (__builtin_clz(width) ^ 31) + 1; + if(width_log2 < 6) width_log2 = 6; + width_log2 -= 6; + if(width_log2 >= GENERIC_CACHEC) { + klogf("Allocation size %i too big for generic caches!\n", width); + return NULL; + } + + struct SlabCache *generic_cache = &s_generic_caches[width_log2]; + return mem_slab_alloc(generic_cache); +} + +void +mem_free(void *ptr) +{ + for(int i = 0; i < GENERIC_CACHEC; i++) { + mem_slab_free(&s_generic_caches[i], ptr); + } +} + +void +mem_slab_setup(void) +{ + s_addr_next_free = (uintptr_t)&_kernel_end; + s_addr_next_free = ((s_addr_next_free >> 12) + 1) << 12; + s_get_free_listw(PAGESIZE - sizeof(struct SlabDescriptor), 32); + + for(int i = 0; i < GENERIC_CACHEC; i++) + { + size_t objsize = 1 << (i + 6); + char slab_name[SLABCACHE_NAME_LIMIT]; + sfmt(slab_name, SLABCACHE_NAME_LIMIT, "generic_%i", 1 << (i + 6)); + mem_slabcache_new(&s_generic_caches[i], slab_name, objsize); + } +} diff --git a/mem/slab.d b/mem/slab.d new file mode 100644 index 0000000..5cffd4c --- /dev/null +++ b/mem/slab.d @@ -0,0 +1,2 @@ +mem/slab.o: mem/slab.c mem/slab.h mem/memory.h lib/format.h lib/string.h \ + lib/jove.h io/log.h diff --git a/mem/slab.h b/mem/slab.h new file mode 100644 index 0000000..074d278 --- /dev/null +++ b/mem/slab.h @@ -0,0 +1,33 @@ +#ifndef JOVE_MEMORY_SLAB_H +#define JOVE_MEMORY_SLAB_H 1 + +#include +#include +#include + +#define SLABCACHE_NAME_LIMIT 32 +struct SlabCache +{ + char name[SLABCACHE_NAME_LIMIT]; + + struct SlabDescriptor *list_free; + struct SlabDescriptor *list_partial; + struct SlabDescriptor *list_full; + + size_t obj_size; + size_t slab_pages; +}; + +struct SlabDescriptor +{ + struct SlabDescriptor *prev; + struct SlabDescriptor *next; + void *slab_base; + void *obj_base; + + size_t free_count; + int free_index; + uintptr_t free[]; +}; + +#endif -- cgit v1.2.1