X-Git-Url: https://scm.lunaixsky.com/lunaix-os.git/blobdiff_plain/728194869c3dc89b0e1c625480d486ada309ae40..8ee36f112e021d03e4bbbd95c4d561ee112f3887:/lunaix-os/kernel/mm/kalloc.c diff --git a/lunaix-os/kernel/mm/kalloc.c b/lunaix-os/kernel/mm/kalloc.c index ba00b09..0ce97e9 100644 --- a/lunaix-os/kernel/mm/kalloc.c +++ b/lunaix-os/kernel/mm/kalloc.c @@ -1,3 +1,6 @@ + +/**** DO NOT USE ****/ + /** * @file kalloc.c * @author Lunaixsky @@ -11,270 +14,271 @@ * @copyright Copyright (c) 2022 * */ -#include -#include -#include - -#include -#include +// #include +// #include +// #include -#include +// #include +// #include -#include +// #include -extern uint8_t __kernel_heap_start; - -void* -lx_malloc_internal(heap_context_t* heap, size_t size); - -void -place_chunk(uint8_t* ptr, size_t size); +// #include -void -lx_free_internal(void* ptr); +// extern uint8_t __kernel_heap_start; + +// void* +// lx_malloc_internal(heap_context_t* heap, size_t size); + +// void +// place_chunk(uint8_t* ptr, size_t size); -void* -coalesce(uint8_t* chunk_ptr); +// void +// lx_free_internal(void* ptr); -void* -lx_grow_heap(heap_context_t* heap, size_t sz); +// 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 +// /* +// At the beginning, we allocate an empty page and put our initial marker - | 4/1 | 0/1 | - ^ ^ brk - start +// | 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. +// 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 +// | 4/1 | 4096/0 | ....... | 4096/0 | 0/1 | +// ^ ^ brk_old ^ +// start brk - Note: the brk always point to the beginning of epilogue. -*/ +// Note: the brk always point to the beginning of epilogue. +// */ -// FIXME: This should be per-process but not global! -static heap_context_t kheap; +// static heap_context_t kheap; -int -kalloc_init() -{ - kheap.start = KHEAP_START; - kheap.brk = NULL; - kheap.max_addr = - (void*)PROC_START; // 在新的布局中，堆结束的地方即为进程表开始的地方 - - 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* -lxmalloc(size_t size) -{ - mutex_lock(&kheap.lock); - void* r = lx_malloc_internal(&kheap, size); - mutex_unlock(&kheap.lock); - - return r; -} - -void* -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, 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 -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 +// int +// kalloc_init() +// { +// kheap.start = KHEAP_START; +// kheap.brk = NULL; +// kheap.max_addr = +// (void*)PROC_START; // 在新的布局中，堆结束的地方即为进程表开始的地方 + +// 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* +// lxmalloc(size_t size) +// { +// mutex_lock(&kheap.lock); +// void* r = lx_malloc_internal(&kheap, size); +// mutex_unlock(&kheap.lock); + +// return r; +// } + +// void* +// 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, pd); +// } + +// void +// lxfree(void* ptr) +// { +// if (!ptr) { +// return; +// } +// mutex_lock(&kheap.lock); + +// uint8_t* chunk_ptr = (uint8_t*)ptr - WSIZE; +// u32_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) { +// u32_t header = *((u32_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 +// place_chunk(uint8_t* ptr, size_t size) +// { +// u32_t header = *((u32_t*)ptr); +// size_t chunk_size = CHUNK_S(header); +// *((u32_t*)ptr) = PACK(size, CHUNK_PF(header) | M_ALLOCATED); +// uint8_t* n_hdrptr = (uint8_t*)(ptr + size); +// u32_t diff = chunk_size - size; + +// if (!diff) { +// // if the current free block is fully occupied +// u32_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 +// u32_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) +// { +// u32_t hdr = LW(chunk_ptr); +// u32_t pf = CHUNK_PF(hdr); +// u32_t sz = CHUNK_S(hdr); + +// u32_t n_hdr = LW(chunk_ptr + sz); + +// if (CHUNK_A(n_hdr) && pf) { +// // case 1: prev is free +// u32_t prev_ftr = LW(chunk_ptr - WSIZE); +// size_t prev_chunk_sz = CHUNK_S(prev_ftr); +// u32_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); +// u32_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 +// u32_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); +// u32_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; + +// u32_t old_marker = *((u32_t*)start); +// u32_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