From 07b15b375ee7cc87f476200b2fd6205959ac0ba4 Mon Sep 17 00:00:00 2001 From: katchup Date: Sun, 12 Dec 2010 17:29:31 +0100 Subject: New heap, simple and bug-free, but inefficient. --- src/kernel/config.h | 15 +++ src/kernel/core/kmain.c | 15 ++- src/kernel/core/test.c | 50 +++++---- src/kernel/mem/heap.basic.c | 136 ++++++++++++++++++++++++ src/kernel/mem/heap.basic.h | 30 ++++++ src/kernel/mem/heap.c | 245 ++------------------------------------------ src/kernel/mem/heap.h | 32 ------ src/kernel/mem/heap.std.c | 241 +++++++++++++++++++++++++++++++++++++++++++ src/kernel/mem/heap.std.h | 34 ++++++ src/kernel/mem/mem.c | 17 ++- src/kernel/task/syscall.c | 3 + src/kernel/task/task.c | 3 +- 12 files changed, 523 insertions(+), 298 deletions(-) create mode 100644 src/kernel/config.h create mode 100644 src/kernel/mem/heap.basic.c create mode 100644 src/kernel/mem/heap.basic.h delete mode 100644 src/kernel/mem/heap.h create mode 100644 src/kernel/mem/heap.std.c create mode 100644 src/kernel/mem/heap.std.h diff --git a/src/kernel/config.h b/src/kernel/config.h new file mode 100644 index 0000000..ccad9cf --- /dev/null +++ b/src/kernel/config.h @@ -0,0 +1,15 @@ +#ifndef DEF_CONFIG_H +#define DEF_CONFIG_H + +#define K_OS_NAME "Grapes" +#define K_OS_VER "0.0.4" +#define K_OS_CODENAME "Cat in my heart" + +/* HEAP CODE TO USE : + Two kernel heap implementations are available : + - Basic implementation, slow but bug-free + - Standard implementation, efficient, buggy, based on the heap code from JamesM's OSDev tutorial + Comment the following define to use the second version */ +#define K_USE_BASIC_HEAP + +#endif diff --git a/src/kernel/core/kmain.c b/src/kernel/core/kmain.c index 6c9700e..8f14843 100644 --- a/src/kernel/core/kmain.c +++ b/src/kernel/core/kmain.c @@ -1,4 +1,6 @@ #include +#include + #include "multiboot.h" #include "monitor.h" #include "sys.h" @@ -24,7 +26,7 @@ void kmain(struct multiboot_info_t* mbd, int32_t magic) { size_t totalRam = 0; uint32_t i; - mem_placementAddr = (size_t)&end; + mem_placementAddr = ((size_t)&end & 0xFFFFF000) + 0x1000; mbd->cmdline += 0xE0000000; mbd->mods_addr += 0xE0000000; struct module_t *mods = (struct module_t*)mbd->mods_addr; for (i = 0; i < mbd->mods_count; i++) { @@ -35,7 +37,12 @@ void kmain(struct multiboot_info_t* mbd, int32_t magic) { mem_placementAddr = (mods[i].mod_end & 0xFFFFF000) + 0x1000; } - monitor_write("Grapes 0.0.4 'Cat in my heart' starting up :\n"); + monitor_write(K_OS_NAME); + monitor_write(" version "); + monitor_write(K_OS_VER); + monitor_write(" codename '"); + monitor_write(K_OS_CODENAME); + monitor_write("' starting up :\n"); idt_init(); @@ -47,6 +54,8 @@ void kmain(struct multiboot_info_t* mbd, int32_t magic) { kheap_init(); timer_init(30); tasking_init(); + + test_run(); monitor_write("\nLoading modules :\n"); for (i = 0; i < mbd->mods_count; i++) { @@ -64,8 +73,6 @@ void kmain(struct multiboot_info_t* mbd, int32_t magic) { } } - test_run(); - monitor_write("Modules now RULE THE WORLD !\n"); sti(); tasking_switch(); diff --git a/src/kernel/core/test.c b/src/kernel/core/test.c index fa26c7b..867a4b5 100644 --- a/src/kernel/core/test.c +++ b/src/kernel/core/test.c @@ -3,27 +3,35 @@ #include #include "sys.h" -#define TEST_KMALLOC(var, sz) void *var = kmalloc(sz); ASSERT(var > 0xE0000000); -#define TEST_KFREE(var) if (var != 0) { kfree(var); } +static void test_run_kmalloc() { + monitor_write("\tkmalloc:\n"); + int alloc_sizes[8] = { 10, 32, 16, 20, 64, 128, 32, 48 }; + int *ptrs[8] = { 0 }; + int t, i; + for (t = 0; t < 2; t++) { + for (i = 0; i < 8; i++) { + monitor_writeDec(i); monitor_write(" alloc "); monitor_writeDec(alloc_sizes[i]); + monitor_write(" : "); + ptrs[i] = kmalloc(alloc_sizes[i]); + ASSERT(ptrs[i] != 0); + *ptrs[i] = i; + monitor_writeHex((int)ptrs[i]); monitor_write("\n"); + } + monitor_write("free : "); + for (i = 0; i < 8; i++) { + monitor_writeDec(i); + ASSERT(*ptrs[i] == i); + kfree(ptrs[i]); + monitor_write("."); + } + monitor_write("\n"); + } +} +/* This function is called when the kernel starts up. + It runs some basic unit tests (for the moment, only tests kmalloc/kfree) */ void test_run() { - monitor_write("Unit tests:\n\tkmalloc:"); - int i; - for (i = 1; i <= 7; i++) { - monitor_write(" #"); monitor_writeDec(i); - TEST_KMALLOC(a, 32); - TEST_KMALLOC(b, 64); - TEST_KMALLOC(c, 256); - TEST_KMALLOC(d, 512); - TEST_KMALLOC(e, 1024); - TEST_KMALLOC(f, 4096); - TEST_KMALLOC(g, 16384); - TEST_KFREE(b); - TEST_KFREE(c); - TEST_KFREE(d); - TEST_KFREE(e); - TEST_KFREE(f); - TEST_KFREE(g); - } - monitor_write("\n >> Tests OK\n"); + monitor_write("Unit tests:\n"); + test_run_kmalloc(); + monitor_write(" >> Tests OK\n"); } 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 +#include + +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); +} diff --git a/src/kernel/mem/heap.basic.h b/src/kernel/mem/heap.basic.h new file mode 100644 index 0000000..c752750 --- /dev/null +++ b/src/kernel/mem/heap.basic.h @@ -0,0 +1,30 @@ +#ifndef DEF_HEAP_H +#define DEF_HEAP_H + +/* This heap implementation is extra-simple and extra-slow. */ + +#include "types.h" + +#define HH_FREE_MAGIC 0xFEE0FEE0 +#define HH_ALLOC_MAGIC 0xA110A110 + +#define HEAP_EXTEND_QUANTITY 0x00080000 // each time we extend the heap, extend it 512 k + +#define MIN_BLK_SIZE 0x20 // 32 bytes + +struct heap_header { + uint32_t magic; + struct heap_header *prev, *next; +}; + +struct heap { + struct heap_header *first, *first_free; // first_free is not necessarily free, it's just an indication + size_t start_addr, end_addr, max_end; + uint32_t mutex; +}; + +void heap_create(struct heap *heap, size_t start, size_t datasize, size_t maxdatasize); +void *heap_alloc(struct heap *heap, size_t sz); +void heap_free(struct heap *heap, void *ptr); + +#endif diff --git a/src/kernel/mem/heap.c b/src/kernel/mem/heap.c index 79ef81e..a590c28 100644 --- a/src/kernel/mem/heap.c +++ b/src/kernel/mem/heap.c @@ -1,241 +1,12 @@ -#include "heap.h" -#include "paging.h" -#include +// THIS EITHER INCLUDES heap.std.c OR heap.basic.c DEPENDING ON +// WHAT'S SPECIFIED IN config.h -#include +#include -#define HEAP_MAGIC 0xBAD0BEEF -#define HEAP_MIN_SIZE 0x4000 +#ifdef K_USE_BASIC_HEAP +#include "heap.basic.c" -/* ******************* HEADER ****************** */ +#else +#include "heap.std.c" -/* For internal use only. Inserts a hole in the heap's hole index at the correct position. */ -static void heapIdx_insert(struct heap *heap, struct heap_header *e) { - if ((heap->idxused + sizeof(struct heap_header*) + (size_t)heap->idx) >= heap->start_addr) return; - - uint32_t iterator = 0, pos; - while (iterator < heap->idxused && heap->idx[iterator]->size <= e->size) { - if (heap->idx[iterator] == e) return; - iterator++; - } - if (iterator == heap->idxused) { - heap->idx[heap->idxused++] = e; - } else { - pos = iterator; - iterator = heap->idxused; - while (iterator > pos) { - heap->idx[iterator] = heap->idx[iterator - 1]; - iterator--; - } - heap->idxused++; - heap->idx[pos] = e; - } -} - -/* For internal use only. Removes a hole from the heap's hole index. */ -static void heapIdx_remove(struct heap *heap, struct heap_header *e) { - uint32_t iterator; - for (iterator = 0; iterator < heap->idxused; iterator++) { - if (heap->idx[iterator] == e) break; - } - if (iterator == heap->idxused) return; - heap->idxused--; - while (iterator < heap->idxused) { - heap->idx[iterator] = heap->idx[iterator + 1]; - iterator++; - } -} - -/* ******************** CONTENTS ********************* */ - -/* Initializes the heap, creates the correct data structures. */ -void heap_create(struct heap *heap, size_t start, size_t idxsize, size_t datasize, size_t maxdatasize) { - uint32_t i; - - if (start & 0x0FFF) start = (start & 0xFFFFF000) + 0x1000; - - heap->start_addr = start + idxsize; - heap->end_addr = start + idxsize + datasize; - heap->max_end = start + idxsize + maxdatasize; - - for (i = start; i < heap->end_addr; i += 0x1000) { - page_map(pagedir_getPage(kernel_pagedir, i, 1), frame_alloc(), 0, 0); - } - - heap->idx = (struct heap_header**)start; - heap->idxused = 0; - - struct heap_header *hole = (struct heap_header*) heap->start_addr; - hole->size = (heap->end_addr - heap->start_addr); - hole->magic = HEAP_MAGIC; - hole->is_hole = 1; - - struct heap_footer *hole_footer = (struct heap_footer*)(heap->end_addr - sizeof(struct heap_footer)); - hole_footer->header = hole; - hole_footer->magic = HEAP_MAGIC; - - heapIdx_insert(heap, hole); -} - -/* For internal use only. Called by heap_alloc when necessary. Expands the heap to take more space. */ -static uint32_t heap_expand(struct heap *heap, size_t quantity) { - uint32_t i; - - if (quantity & 0x0FFF) { - quantity = (quantity & 0xFFFFF000) + 0x1000; - } - - if (heap->end_addr + quantity > heap->max_end) return 0; - - size_t newEnd = heap->end_addr + quantity; - - for (i = heap->end_addr; i < newEnd; i += 0x1000) { - page_map(pagedir_getPage(kernel_pagedir, i, 1), frame_alloc(), 0, 0); - } - - struct heap_footer *last_footer = (struct heap_footer*)(heap->end_addr - sizeof(struct heap_footer)); - struct heap_header *last_header = last_footer->header; - if (last_header->is_hole) { - heapIdx_remove(heap, last_header); - last_header->size += quantity; - - last_footer = (struct heap_footer*)(newEnd - sizeof(struct heap_footer)); - last_footer->magic = HEAP_MAGIC; - last_footer->header = last_header; - - heapIdx_insert(heap, last_header); - } else { - last_header = (struct heap_header*)heap->end_addr; - last_footer = (struct heap_footer*)(newEnd - sizeof(struct heap_footer)); - - last_header->is_hole = 1; - last_header->magic = HEAP_MAGIC; - last_header->size = quantity; - - last_footer->magic = HEAP_MAGIC; - last_footer->header = last_header; - - heapIdx_insert(heap, last_header); - } - - heap->end_addr = newEnd; - - return 1; -} - -/* For internal use only. Called by heap_free when necessary. Reduces the heap's size. */ -static void heap_contract(struct heap *heap) { - return; //TODO: this function bugs everything - - - struct heap_footer *last_footer = (struct heap_footer*)(heap->end_addr - sizeof(struct heap_footer)); - struct heap_header *last_header = last_footer->header; - - if (last_header->is_hole == 0) return; - if (last_header->size <= 0x1000) return; - - size_t quantity = ((heap->end_addr - heap->start_addr) & 0xFFFFF000) - 0x1000; - while ((heap->end_addr - heap->start_addr) - quantity < HEAP_MIN_SIZE || - last_header->size - 0x4000 < quantity) - quantity -= 0x1000; - if (quantity == 0) return; - - size_t newEnd = heap->end_addr - quantity; - - heapIdx_remove(heap, last_header); - last_header->size -= quantity; - last_footer = (struct heap_footer*)((size_t)last_footer - quantity); - last_footer->magic = HEAP_MAGIC; - last_footer->header = last_header; - heapIdx_insert(heap, last_header); - - for (heap->end_addr -= 0x1000; heap->end_addr >= newEnd; heap->end_addr -= 0x1000) { - page_unmapFree(pagedir_getPage(kernel_pagedir, heap->end_addr, 0)); - } -} - -/* Alocate some bytes on the heap. */ -void* heap_alloc(struct heap *heap, size_t sz) { - ASSERT(heap > 0xE0000000); - size_t newsize = sz + sizeof(struct heap_header) + sizeof(struct heap_footer); - uint32_t iterator = 0; - - while (iterator < heap->idxused) { - if (heap->idx[iterator]->size >= newsize) break; - iterator++; - } - - if (iterator == heap->idxused) { //No hole is big enough - if (heap_expand(heap, - MAX((heap->end_addr - heap->start_addr) & 0xFFFFF000, (newsize & 0xFFFFF000) + 0x1000) - ) == 0) return 0; //FAILED - return heap_alloc(heap, sz); - } - - struct heap_header *loc = heap->idx[iterator]; - heapIdx_remove(heap, loc); - struct heap_footer *footer = (struct heap_footer*)((size_t)loc + loc->size - sizeof(struct heap_footer)); - loc->is_hole = 0; - - //If we have enough space to create a USEFUL new hole next to the allocated block, do it. - //If we do not, we might return a block that is a few bytes bigger than needed. - if (loc->size > (newsize + sizeof(struct heap_header) + sizeof(struct heap_footer))) { - loc->size = newsize; - - //Write footer for block we return - struct heap_footer *newfooter = (struct heap_footer*)((size_t)loc + newsize - sizeof(struct heap_footer)); - newfooter->header = loc; - newfooter->magic = HEAP_MAGIC; - - //Write header for new hole we create - struct heap_header *nextloc = (struct heap_header*)((size_t)loc + newsize); - nextloc->is_hole = 1; - nextloc->magic = HEAP_MAGIC; - nextloc->size = ((size_t)footer - (size_t)nextloc + sizeof(struct heap_footer)); - footer->header = nextloc; //Update footer - footer->magic = HEAP_MAGIC; - - heapIdx_insert(heap, nextloc); - } - - return (void*)((size_t)loc + sizeof(struct heap_header)); -} - -/* Frees a block previously allocated on the heap. */ -void heap_free(struct heap *heap, void* ptr) { - if (ptr == 0) return; - if ((size_t)ptr < heap->start_addr || (size_t)ptr > heap->end_addr) return; - - struct heap_header *header = (struct heap_header*)((size_t)ptr - sizeof(struct heap_header)); - struct heap_footer *footer = (struct heap_footer*)((size_t)header + header->size - sizeof(struct heap_footer)); - if (header->magic != HEAP_MAGIC || footer->magic != HEAP_MAGIC) return; - - //Unify left - struct heap_footer *prev_footer = (struct heap_footer*)((size_t)header - sizeof(struct heap_footer)); - if (prev_footer->magic == HEAP_MAGIC && prev_footer->header->is_hole) { - header = prev_footer->header; - heapIdx_remove(heap, header); - - footer->header = header; - header->size = ((size_t)footer - (size_t)header + sizeof(struct heap_footer)); - } - - //Unify right - struct heap_header *next_header = (struct heap_header*)((size_t)footer + sizeof(struct heap_footer)); - if (next_header->magic == HEAP_MAGIC && next_header->is_hole) { - heapIdx_remove(heap, next_header); - footer = (struct heap_footer*)((size_t)footer + next_header->size); - - footer->header = header; - header->size = ((size_t)footer - (size_t)header + sizeof(struct heap_footer)); - } - - header->is_hole = 1; - - heapIdx_insert(heap, header); - - if ((size_t)footer == (heap->end_addr - sizeof(struct heap_footer)) && - header->size >= 0x2000 && (heap->end_addr - heap->start_addr > HEAP_MIN_SIZE)) { - heap_contract(heap); - } -} +#endif diff --git a/src/kernel/mem/heap.h b/src/kernel/mem/heap.h deleted file mode 100644 index 8f8cdcf..0000000 --- a/src/kernel/mem/heap.h +++ /dev/null @@ -1,32 +0,0 @@ -#ifndef DEF_HEAP_H -#define DEF_HEAP_H - -/* The heap is the data structure that permits allocating and freeing memory easily. - The functions in this file are only used by mem.c, which provides kmalloc and kfree. - The heap algorithm used is the one described here : - http://www.jamesmolloy.co.uk/tutorial_html/7.-The%20Heap.html */ - -#include "types.h" - -struct heap_header { - uint32_t magic; - uint32_t is_hole; - size_t size; -}; - -struct heap_footer { - uint32_t magic; - struct heap_header *header; -}; - -struct heap { - struct heap_header **idx; - uint32_t idxused; - size_t start_addr, end_addr, max_end; -}; - -void heap_create(struct heap *heap, size_t start, size_t idxsize, size_t datasize, size_t maxdatasize); -void* heap_alloc(struct heap *heap, size_t sz); -void heap_free(struct heap *heap, void* ptr); - -#endif diff --git a/src/kernel/mem/heap.std.c b/src/kernel/mem/heap.std.c new file mode 100644 index 0000000..5b2d025 --- /dev/null +++ b/src/kernel/mem/heap.std.c @@ -0,0 +1,241 @@ +#include "heap.std.h" +#include "paging.h" +#include + +#include + +#define HEAP_MAGIC 0xBAD0BEEF +#define HEAP_MIN_SIZE 0x4000 + +/* ******************* HEADER ****************** */ + +/* For internal use only. Inserts a hole in the heap's hole index at the correct position. */ +static void heapIdx_insert(struct heap *heap, struct heap_header *e) { + if ((heap->idxused + sizeof(struct heap_header*) + (size_t)heap->idx) >= heap->start_addr) return; + + uint32_t iterator = 0, pos; + while (iterator < heap->idxused && heap->idx[iterator]->size <= e->size) { + if (heap->idx[iterator] == e) return; + iterator++; + } + if (iterator == heap->idxused) { + heap->idx[heap->idxused++] = e; + } else { + pos = iterator; + iterator = heap->idxused; + while (iterator > pos) { + heap->idx[iterator] = heap->idx[iterator - 1]; + iterator--; + } + heap->idxused++; + heap->idx[pos] = e; + } +} + +/* For internal use only. Removes a hole from the heap's hole index. */ +static void heapIdx_remove(struct heap *heap, struct heap_header *e) { + uint32_t iterator; + for (iterator = 0; iterator < heap->idxused; iterator++) { + if (heap->idx[iterator] == e) break; + } + if (iterator == heap->idxused) return; + heap->idxused--; + while (iterator < heap->idxused) { + heap->idx[iterator] = heap->idx[iterator + 1]; + iterator++; + } +} + +/* ******************** CONTENTS ********************* */ + +/* Initializes the heap, creates the correct data structures. */ +void heap_create(struct heap *heap, size_t start, size_t idxsize, size_t datasize, size_t maxdatasize) { + uint32_t i; + + if (start & 0x0FFF) start = (start & 0xFFFFF000) + 0x1000; + + heap->start_addr = start + idxsize; + heap->end_addr = start + idxsize + datasize; + heap->max_end = start + idxsize + maxdatasize; + + for (i = start; i < heap->end_addr; i += 0x1000) { + page_map(pagedir_getPage(kernel_pagedir, i, 1), frame_alloc(), 0, 0); + } + + heap->idx = (struct heap_header**)start; + heap->idxused = 0; + + struct heap_header *hole = (struct heap_header*) heap->start_addr; + hole->size = (heap->end_addr - heap->start_addr); + hole->magic = HEAP_MAGIC; + hole->is_hole = 1; + + struct heap_footer *hole_footer = (struct heap_footer*)(heap->end_addr - sizeof(struct heap_footer)); + hole_footer->header = hole; + hole_footer->magic = HEAP_MAGIC; + + heapIdx_insert(heap, hole); +} + +/* For internal use only. Called by heap_alloc when necessary. Expands the heap to take more space. */ +static uint32_t heap_expand(struct heap *heap, size_t quantity) { + uint32_t i; + + if (quantity & 0x0FFF) { + quantity = (quantity & 0xFFFFF000) + 0x1000; + } + + if (heap->end_addr + quantity > heap->max_end) return 0; + + size_t newEnd = heap->end_addr + quantity; + + for (i = heap->end_addr; i < newEnd; i += 0x1000) { + page_map(pagedir_getPage(kernel_pagedir, i, 1), frame_alloc(), 0, 0); + } + + struct heap_footer *last_footer = (struct heap_footer*)(heap->end_addr - sizeof(struct heap_footer)); + struct heap_header *last_header = last_footer->header; + if (last_header->is_hole) { + heapIdx_remove(heap, last_header); + last_header->size += quantity; + + last_footer = (struct heap_footer*)(newEnd - sizeof(struct heap_footer)); + last_footer->magic = HEAP_MAGIC; + last_footer->header = last_header; + + heapIdx_insert(heap, last_header); + } else { + last_header = (struct heap_header*)heap->end_addr; + last_footer = (struct heap_footer*)(newEnd - sizeof(struct heap_footer)); + + last_header->is_hole = 1; + last_header->magic = HEAP_MAGIC; + last_header->size = quantity; + + last_footer->magic = HEAP_MAGIC; + last_footer->header = last_header; + + heapIdx_insert(heap, last_header); + } + + heap->end_addr = newEnd; + + return 1; +} + +/* For internal use only. Called by heap_free when necessary. Reduces the heap's size. */ +static void heap_contract(struct heap *heap) { + return; //TODO: this function bugs everything + + + struct heap_footer *last_footer = (struct heap_footer*)(heap->end_addr - sizeof(struct heap_footer)); + struct heap_header *last_header = last_footer->header; + + if (last_header->is_hole == 0) return; + if (last_header->size <= 0x1000) return; + + size_t quantity = ((heap->end_addr - heap->start_addr) & 0xFFFFF000) - 0x1000; + while ((heap->end_addr - heap->start_addr) - quantity < HEAP_MIN_SIZE || + last_header->size - 0x4000 < quantity) + quantity -= 0x1000; + if (quantity == 0) return; + + size_t newEnd = heap->end_addr - quantity; + + heapIdx_remove(heap, last_header); + last_header->size -= quantity; + last_footer = (struct heap_footer*)((size_t)last_footer - quantity); + last_footer->magic = HEAP_MAGIC; + last_footer->header = last_header; + heapIdx_insert(heap, last_header); + + for (heap->end_addr -= 0x1000; heap->end_addr >= newEnd; heap->end_addr -= 0x1000) { + page_unmapFree(pagedir_getPage(kernel_pagedir, heap->end_addr, 0)); + } +} + +/* Alocate some bytes on the heap. */ +void* heap_alloc(struct heap *heap, size_t sz) { + ASSERT(heap > 0xE0000000); + size_t newsize = sz + sizeof(struct heap_header) + sizeof(struct heap_footer); + uint32_t iterator = 0; + + while (iterator < heap->idxused) { + if (heap->idx[iterator]->size >= newsize) break; + iterator++; + } + + if (iterator == heap->idxused) { //No hole is big enough + if (heap_expand(heap, + MAX((heap->end_addr - heap->start_addr) & 0xFFFFF000, (newsize & 0xFFFFF000) + 0x1000) + ) == 0) return 0; //FAILED + return heap_alloc(heap, sz); + } + + struct heap_header *loc = heap->idx[iterator]; + heapIdx_remove(heap, loc); + struct heap_footer *footer = (struct heap_footer*)((size_t)loc + loc->size - sizeof(struct heap_footer)); + loc->is_hole = 0; + + //If we have enough space to create a USEFUL new hole next to the allocated block, do it. + //If we do not, we might return a block that is a few bytes bigger than needed. + if (loc->size > (newsize + sizeof(struct heap_header) + sizeof(struct heap_footer))) { + loc->size = newsize; + + //Write footer for block we return + struct heap_footer *newfooter = (struct heap_footer*)((size_t)loc + newsize - sizeof(struct heap_footer)); + newfooter->header = loc; + newfooter->magic = HEAP_MAGIC; + + //Write header for new hole we create + struct heap_header *nextloc = (struct heap_header*)((size_t)loc + newsize); + nextloc->is_hole = 1; + nextloc->magic = HEAP_MAGIC; + nextloc->size = ((size_t)footer - (size_t)nextloc + sizeof(struct heap_footer)); + footer->header = nextloc; //Update footer + footer->magic = HEAP_MAGIC; + + heapIdx_insert(heap, nextloc); + } + + return (void*)((size_t)loc + sizeof(struct heap_header)); +} + +/* Frees a block previously allocated on the heap. */ +void heap_free(struct heap *heap, void* ptr) { + if (ptr == 0) return; + if ((size_t)ptr < heap->start_addr || (size_t)ptr > heap->end_addr) return; + + struct heap_header *header = (struct heap_header*)((size_t)ptr - sizeof(struct heap_header)); + struct heap_footer *footer = (struct heap_footer*)((size_t)header + header->size - sizeof(struct heap_footer)); + if (header->magic != HEAP_MAGIC || footer->magic != HEAP_MAGIC) return; + + //Unify left + struct heap_footer *prev_footer = (struct heap_footer*)((size_t)header - sizeof(struct heap_footer)); + if (prev_footer->magic == HEAP_MAGIC && prev_footer->header->is_hole) { + header = prev_footer->header; + heapIdx_remove(heap, header); + + footer->header = header; + header->size = ((size_t)footer - (size_t)header + sizeof(struct heap_footer)); + } + + //Unify right + struct heap_header *next_header = (struct heap_header*)((size_t)footer + sizeof(struct heap_footer)); + if (next_header->magic == HEAP_MAGIC && next_header->is_hole) { + heapIdx_remove(heap, next_header); + footer = (struct heap_footer*)((size_t)footer + next_header->size); + + footer->header = header; + header->size = ((size_t)footer - (size_t)header + sizeof(struct heap_footer)); + } + + header->is_hole = 1; + + heapIdx_insert(heap, header); + + if ((size_t)footer == (heap->end_addr - sizeof(struct heap_footer)) && + header->size >= 0x2000 && (heap->end_addr - heap->start_addr > HEAP_MIN_SIZE)) { + heap_contract(heap); + } +} diff --git a/src/kernel/mem/heap.std.h b/src/kernel/mem/heap.std.h new file mode 100644 index 0000000..a7ba173 --- /dev/null +++ b/src/kernel/mem/heap.std.h @@ -0,0 +1,34 @@ +#ifndef DEF_HEAP_H +#define DEF_HEAP_H + +#error "Using standard heap ! It's all buggy everywhere !" + +/* The heap is the data structure that permits allocating and freeing memory easily. + The functions in this file are only used by mem.c, which provides kmalloc and kfree. + The heap algorithm used is based on the one described here : + http://www.jamesmolloy.co.uk/tutorial_html/7.-The%20Heap.html */ + +#include "types.h" + +struct heap_header { + uint32_t magic; + uint32_t is_hole; + size_t size; +}; + +struct heap_footer { + uint32_t magic; + struct heap_header *header; +}; + +struct heap { + struct heap_header **idx; + uint32_t idxused; + size_t start_addr, end_addr, max_end; +}; + +void heap_create(struct heap *heap, size_t start, size_t idxsize, size_t datasize, size_t maxdatasize); +void* heap_alloc(struct heap *heap, size_t sz); +void heap_free(struct heap *heap, void* ptr); + +#endif diff --git a/src/kernel/mem/mem.c b/src/kernel/mem/mem.c index 2061aff..c6494b7 100644 --- a/src/kernel/mem/mem.c +++ b/src/kernel/mem/mem.c @@ -2,12 +2,19 @@ #include #include #include "paging.h" -#include "heap.h" + +#include + +#ifdef K_USE_BASIC_HEAP +#include "heap.basic.h" +#else +#include "heap.std.h" +#endif #define FREEPAGESTOKEEP 5 -#define KHEAP_IDXSIZE 0x1000 -#define KHEAP_INITSIZE 0x80000 +#define KHEAP_IDXSIZE 0x4000 // only used with heap.std.h +#define KHEAP_INITSIZE 0x00080000 #define KHEAP_MAXSIZE 0x08000000 size_t mem_placementAddr; @@ -76,7 +83,11 @@ static struct heap kheap; /* Called on kernel start. Creates the kernel heap. */ void kheap_init() { +#ifdef K_USE_BASIC_HEAP + heap_create(&kheap, (mem_placementAddr & 0xFFFFF000) + 0x1000, KHEAP_INITSIZE, KHEAP_MAXSIZE); +#else heap_create(&kheap, (mem_placementAddr & 0xFFFFF000) + 0x1000, KHEAP_IDXSIZE, KHEAP_INITSIZE, KHEAP_MAXSIZE); +#endif kheap_working = 1; monitor_write("[KHeap] "); } diff --git a/src/kernel/task/syscall.c b/src/kernel/task/syscall.c index 46ccff6..3ae546f 100644 --- a/src/kernel/task/syscall.c +++ b/src/kernel/task/syscall.c @@ -1,5 +1,6 @@ #include "syscall.h" #include "task.h" +#include #define CALL0(name, scname) static void scname(struct registers* r) { r->eax = name(); } #define CALL1(name, scname) static void scname(struct registers* r) { \ @@ -26,7 +27,9 @@ CALL2(shm_create, shm_create_sc); CALL1(shm_delete, shm_delete_sc); static void thread_new_sc(struct registers* r) { + cli(); thread_new(current_thread->process, (thread_entry)r->ebx, (void*)r->ecx, (void*)r->edx); + sti(); } int_callback syscalls[NUMBER_OF_SYSCALLS] = { diff --git a/src/kernel/task/task.c b/src/kernel/task/task.c index f074c77..3d322c1 100644 --- a/src/kernel/task/task.c +++ b/src/kernel/task/task.c @@ -35,9 +35,9 @@ void tasking_init() { kernel_process->parent = kernel_process; kernel_process->pagedir = kernel_pagedir; kernel_process->next = 0; + kernel_process->threads = 0; current_thread = 0; idle_thread = thread_new(kernel_process, task_idle, 0, 0); - kernel_process->threads = idle_thread; sti(); monitor_write("[Tasking] "); } @@ -278,6 +278,7 @@ struct process *process_new(struct process* parent, uint32_t uid, uint32_t privi p->pid = (nextpid++); p->uid = uid; p->thread_count = 0; + p->threads = 0; p->privilege = privilege; p->parent = parent; p->pagedir = pagedir_new(); -- cgit v1.2.3