diff options
Diffstat (limited to 'src/kernel/mem/heap.basic.c')
| -rw-r--r-- | src/kernel/mem/heap.basic.c | 136 |
1 files changed, 136 insertions, 0 deletions
diff --git a/src/kernel/mem/heap.basic.c b/src/kernel/mem/heap.basic.c new file mode 100644 index 0000000..d746deb --- /dev/null +++ b/src/kernel/mem/heap.basic.c @@ -0,0 +1,136 @@ +#include "heap.basic.h" + +#include "paging.h" + +#include <lib/mutex.h> +#include <core/sys.h> + +void heap_create(struct heap *heap, size_t start, size_t datasize, size_t maxdatasize) { + uint32_t i; + if (start & 0x0FFF) start = (start & 0xFFFFF000) + 0x1000; + + // Allocate frames + for (i = start; i < start + datasize; i += 0x1000) { + page_map(pagedir_getPage(kernel_pagedir, i, 1), frame_alloc(), 0, 0); + } + + heap->start_addr = start; + heap->end_addr = start + datasize; + heap->max_end = start + maxdatasize; + + struct heap_header *first = (struct heap_header*)start; + first->magic = HH_FREE_MAGIC; + first->prev = first->next = first; + + heap->first = first; + heap->first_free = first; + + heap->mutex = 0; +} + +// ***** UTILITY FUNCTIONS ***** + +#define BLK_SIZE(blk) (blk->next == blk ? ((size_t)heap->end_addr - (size_t)blk) : ((size_t)blk->next - (size_t)blk)) +#define BLK_FREE(blk) (blk->magic == HH_FREE_MAGIC) + +void blk_split(struct heap *heap, struct heap_header *hdr, size_t size) { + ASSERT (size >= MIN_BLK_SIZE); + ASSERT (BLK_SIZE(hdr) > size); + ASSERT (BLK_SIZE(hdr) - size >= MIN_BLK_SIZE); + ASSERT (BLK_FREE(hdr)); + + struct heap_header *hdr_nxt = (struct heap_header*)((size_t)hdr + size); + hdr_nxt->magic = HH_FREE_MAGIC; + hdr_nxt->prev = hdr; + if (hdr->next == hdr) { + hdr_nxt->next = hdr_nxt; + } else { + hdr_nxt->next = hdr->next; + hdr->next->prev = hdr_nxt; + } + hdr->next = hdr_nxt; +} + +void blk_combine_next(struct heap *heap, struct heap_header *hdr) { + ASSERT (hdr != hdr->next); // make sure we are not the last block + ASSERT (hdr->magic == HH_FREE_MAGIC); + ASSERT (hdr->next->magic == HH_FREE_MAGIC); + + struct heap_header *hdr_nxt = hdr->next; + if (hdr_nxt->next == hdr_nxt) { + hdr->next = hdr; + } else { + hdr->next = hdr_nxt->next; + hdr_nxt->next->prev = hdr; + } +} + +// ***** Allocation/Freeing functions ***** + +void *heap_alloc(struct heap *heap, size_t sz) { + /* Algorithm : + 1 Use heap->first_free to find first effectively free block, update heap->first_free + 2 Find first free AND BIG ENOUGH block + - If no block can be found, return 0 (no heap expand yet) + 3 If that block is too big, split it in two + 4 Mark that block as used and return it's address + sizeof(heap_header) */ + mutex_lock(&heap->mutex); + + sz += sizeof(struct heap_header); + if (sz < MIN_BLK_SIZE) sz = MIN_BLK_SIZE; + if (sz % 4 != 0) sz = sz + 4 - (sz % 4); + + // 1 + struct heap_header *it = heap->first_free; + while (!BLK_FREE(it) && it != it->next) it = it->next; + if (!BLK_FREE(it) && it == it->next) { + mutex_unlock(&heap->mutex); + return 0; + } + heap->first_free = it; + + // 2 + while (BLK_SIZE(it) < sz && it != it->next) it = it->next; + if (BLK_SIZE(it) < sz) { // no block could be found + mutex_unlock(&heap->mutex); + return 0; + } + + // 3 + if (BLK_SIZE(it) >= sz + MIN_BLK_SIZE) blk_split(heap, it, sz); + + // 4 + void *ret = (void*)((size_t)it + sizeof(struct heap_header)); + it->magic = HH_ALLOC_MAGIC; + + mutex_unlock(&heap->mutex); + return ret; +} + +void heap_free(struct heap *heap, void *ptr) { + /* Algorithm : + 1 Get block pointer to the block we are freeing + 2 Mark that block as free + 3 If block->next is free, combine_next(block) + 4 If block->prev is free, block = block->prev; combine_next(block) + 5 If block < heap->first_free; heap->first_free = block + */ + mutex_lock(&heap->mutex); + + // 1 + struct heap_header *hdr = (struct heap_header*)((size_t)ptr - sizeof(struct heap_header)); + if (hdr->magic != HH_ALLOC_MAGIC) return; + // 2 + hdr->magic = HH_FREE_MAGIC; + // 3 + if (hdr->next != hdr && hdr->next->magic == HH_FREE_MAGIC) blk_combine_next(heap, hdr); + // 4 + if (hdr->prev != hdr && hdr->prev->magic == HH_FREE_MAGIC) { + hdr = hdr->prev; + blk_combine_next(heap, hdr); + } + // 5 + if (hdr < heap->first_free) heap->first_free = hdr; + + mutex_unlock(&heap->mutex); +} |