diff --git a/.vscode/settings.json b/.vscode/settings.json index f178ceb..dd72655 100644 --- a/.vscode/settings.json +++ b/.vscode/settings.json @@ -1,8 +1,5 @@ { "files.associations": { - "cursor.h": "c", - "alloc.h": "c", - "stdio.h": "c", - "tree-os.h": "c" + "*.h": "c" } } \ No newline at end of file diff --git a/.vscode/settings.json b/.vscode/settings.json index f178ceb..dd72655 100644 --- a/.vscode/settings.json +++ b/.vscode/settings.json @@ -1,8 +1,5 @@ { "files.associations": { - "cursor.h": "c", - "alloc.h": "c", - "stdio.h": "c", - "tree-os.h": "c" + "*.h": "c" } } \ No newline at end of file diff --git a/src/kernel/kernel.c b/src/kernel/kernel.c index 7d5d31e..44453e8 100644 --- a/src/kernel/kernel.c +++ b/src/kernel/kernel.c @@ -8,12 +8,28 @@ extern uint32_t _kernel_end; +void memoryTest() { + void* one = malloc(0x100); + printf("alloc one: %x\n", one); + void* two = malloc(0x100); + printf("alloc two: %x\n", two); + mfree(one); + printf("free one\n"); + void* three = malloc(1); + printf("alloc three: %x\n", three); + mfree(two); + printf("free two\n"); + printMemoryStack(); + void* four = malloc(0x180); + printf("alloc four: %x\n", four); + printMemoryStack(); +} + void kernelMain() { drawLogo(); initMemoryAllocation(0x100000); // initializing stacks after the kernel seems to not work :( otherwise, _kernel_end should be passed here + memoryTest(); initOSTasks(); - printf("malloc 0x100: %x\n", malloc(0x100)); - printf("malloc 0x100: %x\n", malloc(0x100)); printf("Switching to otherTask... \n"); yields(); printf("Returned to mainTask!\n"); diff --git a/.vscode/settings.json b/.vscode/settings.json index f178ceb..dd72655 100644 --- a/.vscode/settings.json +++ b/.vscode/settings.json @@ -1,8 +1,5 @@ { "files.associations": { - "cursor.h": "c", - "alloc.h": "c", - "stdio.h": "c", - "tree-os.h": "c" + "*.h": "c" } } \ No newline at end of file diff --git a/src/kernel/kernel.c b/src/kernel/kernel.c index 7d5d31e..44453e8 100644 --- a/src/kernel/kernel.c +++ b/src/kernel/kernel.c @@ -8,12 +8,28 @@ extern uint32_t _kernel_end; +void memoryTest() { + void* one = malloc(0x100); + printf("alloc one: %x\n", one); + void* two = malloc(0x100); + printf("alloc two: %x\n", two); + mfree(one); + printf("free one\n"); + void* three = malloc(1); + printf("alloc three: %x\n", three); + mfree(two); + printf("free two\n"); + printMemoryStack(); + void* four = malloc(0x180); + printf("alloc four: %x\n", four); + printMemoryStack(); +} + void kernelMain() { drawLogo(); initMemoryAllocation(0x100000); // initializing stacks after the kernel seems to not work :( otherwise, _kernel_end should be passed here + memoryTest(); initOSTasks(); - printf("malloc 0x100: %x\n", malloc(0x100)); - printf("malloc 0x100: %x\n", malloc(0x100)); printf("Switching to otherTask... \n"); yields(); printf("Returned to mainTask!\n"); diff --git a/src/kernel/lib/memory/alloc.c b/src/kernel/lib/memory/alloc.c index c4de5da..0dd6081 100644 --- a/src/kernel/lib/memory/alloc.c +++ b/src/kernel/lib/memory/alloc.c @@ -14,16 +14,62 @@ void* malloc(uint32_t size) { MemoryBlock* current = firstBlock; - while (current->next != 0x00) { + while (! (current->next == 0x00 || current->state == FREE && current->size >= size)) { current = current->next; } - MemoryBlock* next = (MemoryBlock*) ((void*) (current + 1) + size); - next->last = current; - next->state = FREE; - next->next = 0x00; - next->size = -1; - current->next = next; - current->size = size; + MemoryBlock* next; + if (current->next == 0x00) { + // this is currently the last block -> initialize the new last block + next = (MemoryBlock*) ((void*) (current + 1) + size); + next->last = current; + next->state = FREE; + next->next = 0x00; + next->size = -1; + } else { + // there is a next block + next = current->next; + } + if (current->size > size + sizeof(MemoryBlock) * 2 && current->next != 0x00) { + // segment the current block if it is big enough + current->next = (MemoryBlock*) (((void*) (current + 1)) + size); + current->next->size = current->size - sizeof(MemoryBlock) - size; + current->size = size; + current->next->state = FREE; + current->next->next = next; + next->last = current->next; + } else { + current->next = next; + if (current->next->next == 0x00) { + current->size = size; + } + } current->state = IN_USE; - return (void*) current; + return (void*) (current + 1); +} + +void mergeNextIfPossible(MemoryBlock* current) { + if (current->next != 0x00 && current->next->state == FREE) { + current->size = current->size + sizeof(MemoryBlock) + current->next->size; + current->next = current->next->next; + current->next->next->last = current; + } +} + +void mfree(void* location) { + MemoryBlock* current = ((MemoryBlock*) location) - 1; + current->state = FREE; + if (current->last != 0x00 && current->last->state == FREE) { + current = current->last; + } + mergeNextIfPossible(current); // call this function 2 times in case a used block between 2 free blocks is freed + mergeNextIfPossible(current); +} + +void printMemoryStack() { + MemoryBlock* current = firstBlock; + while (current->next != 0x00) { + printf("AT: %x size: %x next: %x last: %x, state: %x\n", current, current->size, current->next, current->last, current->state); + current = current->next; + } + printf("AT: %x size: %x next: %x last: %x, state: %x\n", current, current->size, current->next, current->last, current->state); } \ No newline at end of file diff --git a/.vscode/settings.json b/.vscode/settings.json index f178ceb..dd72655 100644 --- a/.vscode/settings.json +++ b/.vscode/settings.json @@ -1,8 +1,5 @@ { "files.associations": { - "cursor.h": "c", - "alloc.h": "c", - "stdio.h": "c", - "tree-os.h": "c" + "*.h": "c" } } \ No newline at end of file diff --git a/src/kernel/kernel.c b/src/kernel/kernel.c index 7d5d31e..44453e8 100644 --- a/src/kernel/kernel.c +++ b/src/kernel/kernel.c @@ -8,12 +8,28 @@ extern uint32_t _kernel_end; +void memoryTest() { + void* one = malloc(0x100); + printf("alloc one: %x\n", one); + void* two = malloc(0x100); + printf("alloc two: %x\n", two); + mfree(one); + printf("free one\n"); + void* three = malloc(1); + printf("alloc three: %x\n", three); + mfree(two); + printf("free two\n"); + printMemoryStack(); + void* four = malloc(0x180); + printf("alloc four: %x\n", four); + printMemoryStack(); +} + void kernelMain() { drawLogo(); initMemoryAllocation(0x100000); // initializing stacks after the kernel seems to not work :( otherwise, _kernel_end should be passed here + memoryTest(); initOSTasks(); - printf("malloc 0x100: %x\n", malloc(0x100)); - printf("malloc 0x100: %x\n", malloc(0x100)); printf("Switching to otherTask... \n"); yields(); printf("Returned to mainTask!\n"); diff --git a/src/kernel/lib/memory/alloc.c b/src/kernel/lib/memory/alloc.c index c4de5da..0dd6081 100644 --- a/src/kernel/lib/memory/alloc.c +++ b/src/kernel/lib/memory/alloc.c @@ -14,16 +14,62 @@ void* malloc(uint32_t size) { MemoryBlock* current = firstBlock; - while (current->next != 0x00) { + while (! (current->next == 0x00 || current->state == FREE && current->size >= size)) { current = current->next; } - MemoryBlock* next = (MemoryBlock*) ((void*) (current + 1) + size); - next->last = current; - next->state = FREE; - next->next = 0x00; - next->size = -1; - current->next = next; - current->size = size; + MemoryBlock* next; + if (current->next == 0x00) { + // this is currently the last block -> initialize the new last block + next = (MemoryBlock*) ((void*) (current + 1) + size); + next->last = current; + next->state = FREE; + next->next = 0x00; + next->size = -1; + } else { + // there is a next block + next = current->next; + } + if (current->size > size + sizeof(MemoryBlock) * 2 && current->next != 0x00) { + // segment the current block if it is big enough + current->next = (MemoryBlock*) (((void*) (current + 1)) + size); + current->next->size = current->size - sizeof(MemoryBlock) - size; + current->size = size; + current->next->state = FREE; + current->next->next = next; + next->last = current->next; + } else { + current->next = next; + if (current->next->next == 0x00) { + current->size = size; + } + } current->state = IN_USE; - return (void*) current; + return (void*) (current + 1); +} + +void mergeNextIfPossible(MemoryBlock* current) { + if (current->next != 0x00 && current->next->state == FREE) { + current->size = current->size + sizeof(MemoryBlock) + current->next->size; + current->next = current->next->next; + current->next->next->last = current; + } +} + +void mfree(void* location) { + MemoryBlock* current = ((MemoryBlock*) location) - 1; + current->state = FREE; + if (current->last != 0x00 && current->last->state == FREE) { + current = current->last; + } + mergeNextIfPossible(current); // call this function 2 times in case a used block between 2 free blocks is freed + mergeNextIfPossible(current); +} + +void printMemoryStack() { + MemoryBlock* current = firstBlock; + while (current->next != 0x00) { + printf("AT: %x size: %x next: %x last: %x, state: %x\n", current, current->size, current->next, current->last, current->state); + current = current->next; + } + printf("AT: %x size: %x next: %x last: %x, state: %x\n", current, current->size, current->next, current->last, current->state); } \ No newline at end of file diff --git a/src/kernel/lib/memory/alloc.h b/src/kernel/lib/memory/alloc.h index 3eba3b0..aac7846 100644 --- a/src/kernel/lib/memory/alloc.h +++ b/src/kernel/lib/memory/alloc.h @@ -17,5 +17,7 @@ extern void initMemoryAllocation(uint32_t kernelEnd); extern void* malloc(uint32_t size); +extern void mfree(void* location); +extern void printMemoryStack(); #endif \ No newline at end of file