X-Git-Url: https://scm.lunaixsky.com/lunaix-os.git/blobdiff_plain/d07db7c15d6cf9d6c0fd07ea29cca77a89b02a79..1f37d39e678168ffc089bcde6f9ea203c4763550:/lunaix-os/kernel/mm/kalloc.c diff --git a/lunaix-os/kernel/mm/kalloc.c b/lunaix-os/kernel/mm/kalloc.c index c932bb5..ba00b09 100644 --- a/lunaix-os/kernel/mm/kalloc.c +++ b/lunaix-os/kernel/mm/kalloc.c @@ -1,38 +1,280 @@ -#include +/** + * @file kalloc.c + * @author Lunaixsky + * @brief Implicit free list implementation of malloc family, for kernel use. + * + * This version of code is however the simplest and yet insecured, thread unsafe + * it just to demonstrate how the malloc/free works behind the curtain + * @version 0.1 + * @date 2022-03-05 + * + * @copyright Copyright (c) 2022 + * + */ #include +#include +#include + +#include +#include -#include +#include #include extern uint8_t __kernel_heap_start; -heap_context_t __kalloc_kheap; +void* +lx_malloc_internal(heap_context_t* heap, size_t size); + +void +place_chunk(uint8_t* ptr, size_t size); + +void +lx_free_internal(void* ptr); + +void* +coalesce(uint8_t* chunk_ptr); + +void* +lx_grow_heap(heap_context_t* heap, size_t sz); + +/* + At the beginning, we allocate an empty page and put our initial marker + + | 4/1 | 0/1 | + ^ ^ brk + start + + Then, expand the heap further, with HEAP_INIT_SIZE (evaluated to 4096, i.e., + 1 pg size) This will allocate as much pages and override old epilogue marker + with a free region hdr and put new epilogue marker. These are handled by + lx_grow_heap which is internally used by alloc to expand the heap at many + moment when needed. + + | 4/1 | 4096/0 | ....... | 4096/0 | 0/1 | + ^ ^ brk_old ^ + start brk + + Note: the brk always point to the beginning of epilogue. +*/ + +// FIXME: This should be per-process but not global! +static heap_context_t kheap; int -kalloc_init() { - __kalloc_kheap.start = &__kernel_heap_start; - __kalloc_kheap.brk = 0; +kalloc_init() +{ + kheap.start = KHEAP_START; + kheap.brk = NULL; + kheap.max_addr = + (void*)PROC_START; // 在新的布局中，堆结束的地方即为进程表开始的地方 - return dmm_init(&__kalloc_kheap); + for (size_t i = 0; i < KHEAP_SIZE_MB >> 2; i++) { + vmm_set_mapping(PD_REFERENCED, + (uintptr_t)kheap.start + (i << 22), + 0, + PG_PREM_RW, + VMAP_NOMAP); + } + + if (!dmm_init(&kheap)) { + return 0; + } + + SW(kheap.start, PACK(4, M_ALLOCATED)); + SW(kheap.start + WSIZE, PACK(0, M_ALLOCATED)); + kheap.brk += WSIZE; + + return lx_grow_heap(&kheap, HEAP_INIT_SIZE) != NULL; } void* -kmalloc(size_t size) { - return lx_malloc(&__kalloc_kheap, size); +lxmalloc(size_t size) +{ + mutex_lock(&kheap.lock); + void* r = lx_malloc_internal(&kheap, size); + mutex_unlock(&kheap.lock); + + return r; } void* -kcalloc(size_t size) { - void* ptr = kmalloc(size); +lxcalloc(size_t n, size_t elem) +{ + size_t pd = n * elem; + + // overflow detection + if (pd < elem || pd < n) { + return NULL; + } + + void* ptr = lxmalloc(pd); if (!ptr) { return NULL; } - return memset(ptr, 0, size); + return memset(ptr, 0, pd); +} + +void +lxfree(void* ptr) +{ + if (!ptr) { + return; + } + mutex_lock(&kheap.lock); + + uint8_t* chunk_ptr = (uint8_t*)ptr - WSIZE; + uint32_t hdr = LW(chunk_ptr); + size_t sz = CHUNK_S(hdr); + uint8_t* next_hdr = chunk_ptr + sz; + + // make sure the ptr we are 'bout to free makes sense + // the size trick is stolen from glibc's malloc/malloc.c:4437 ;P + + assert_msg(((uintptr_t)ptr < (uintptr_t)(-sz)) && !((uintptr_t)ptr & 0x3), + "free(): invalid pointer"); + + assert_msg(sz > WSIZE, "free(): invalid size"); + + SW(chunk_ptr, hdr & ~M_ALLOCATED); + SW(FPTR(chunk_ptr, sz), hdr & ~M_ALLOCATED); + SW(next_hdr, LW(next_hdr) | M_PREV_FREE); + + coalesce(chunk_ptr); + + mutex_unlock(&kheap.lock); +} + +void* +lx_malloc_internal(heap_context_t* heap, size_t size) +{ + // Simplest first fit approach. + + if (!size) { + return NULL; + } + + uint8_t* ptr = heap->start; + // round to largest 4B aligned value + // and space for header + size = ROUNDUP(size + WSIZE, BOUNDARY); + while (ptr < (uint8_t*)heap->brk) { + uint32_t header = *((uint32_t*)ptr); + size_t chunk_size = CHUNK_S(header); + if (!chunk_size && CHUNK_A(header)) { + break; + } + if (chunk_size >= size && !CHUNK_A(header)) { + // found! + place_chunk(ptr, size); + return BPTR(ptr); + } + ptr += chunk_size; + } + + // if heap is full (seems to be!), then allocate more space (if it's + // okay...) + if ((ptr = lx_grow_heap(heap, size))) { + place_chunk(ptr, size); + return BPTR(ptr); + } + + // Well, we are officially OOM! + return NULL; } void -kfree(void* ptr) { - lx_free(ptr); +place_chunk(uint8_t* ptr, size_t size) +{ + uint32_t header = *((uint32_t*)ptr); + size_t chunk_size = CHUNK_S(header); + *((uint32_t*)ptr) = PACK(size, CHUNK_PF(header) | M_ALLOCATED); + uint8_t* n_hdrptr = (uint8_t*)(ptr + size); + uint32_t diff = chunk_size - size; + + if (!diff) { + // if the current free block is fully occupied + uint32_t n_hdr = LW(n_hdrptr); + // notify the next block about our avaliability + SW(n_hdrptr, n_hdr & ~0x2); + } else { + // if there is remaining free space left + uint32_t remainder_hdr = PACK(diff, M_NOT_ALLOCATED | M_PREV_ALLOCATED); + SW(n_hdrptr, remainder_hdr); + SW(FPTR(n_hdrptr, diff), remainder_hdr); + + /* + | xxxx | | | + + | + v + + | xxxx | | + */ + coalesce(n_hdrptr); + } +} + +void* +coalesce(uint8_t* chunk_ptr) +{ + uint32_t hdr = LW(chunk_ptr); + uint32_t pf = CHUNK_PF(hdr); + uint32_t sz = CHUNK_S(hdr); + + uint32_t n_hdr = LW(chunk_ptr + sz); + + if (CHUNK_A(n_hdr) && pf) { + // case 1: prev is free + uint32_t prev_ftr = LW(chunk_ptr - WSIZE); + size_t prev_chunk_sz = CHUNK_S(prev_ftr); + uint32_t new_hdr = PACK(prev_chunk_sz + sz, CHUNK_PF(prev_ftr)); + SW(chunk_ptr - prev_chunk_sz, new_hdr); + SW(FPTR(chunk_ptr, sz), new_hdr); + chunk_ptr -= prev_chunk_sz; + } else if (!CHUNK_A(n_hdr) && !pf) { + // case 2: next is free + size_t next_chunk_sz = CHUNK_S(n_hdr); + uint32_t new_hdr = PACK(next_chunk_sz + sz, pf); + SW(chunk_ptr, new_hdr); + SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr); + } else if (!CHUNK_A(n_hdr) && pf) { + // case 3: both free + uint32_t prev_ftr = LW(chunk_ptr - WSIZE); + size_t next_chunk_sz = CHUNK_S(n_hdr); + size_t prev_chunk_sz = CHUNK_S(prev_ftr); + uint32_t new_hdr = + PACK(next_chunk_sz + prev_chunk_sz + sz, CHUNK_PF(prev_ftr)); + SW(chunk_ptr - prev_chunk_sz, new_hdr); + SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr); + chunk_ptr -= prev_chunk_sz; + } + + // (fall through) case 4: prev and next are not free + return chunk_ptr; +} + +void* +lx_grow_heap(heap_context_t* heap, size_t sz) +{ + void* start; + + // The "+ WSIZE" capture the overhead for epilogue marker + if (!(start = lxsbrk(heap, sz + WSIZE, 0))) { + return NULL; + } + sz = ROUNDUP(sz, BOUNDARY); + + // minus the overhead for epilogue, keep the invariant. + heap->brk -= WSIZE; + + uint32_t old_marker = *((uint32_t*)start); + uint32_t free_hdr = PACK(sz, CHUNK_PF(old_marker)); + SW(start, free_hdr); + SW(FPTR(start, sz), free_hdr); + SW(NEXT_CHK(start), PACK(0, M_ALLOCATED | M_PREV_FREE)); + + return coalesce(start); } \ No newline at end of file