From a5e5eabd32872f81a7190589aa648dc0e1963888 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= Date: Mon, 2 Dec 2024 10:17:36 +0000 Subject: Fix algorithm issues with linked list allocator --- .../arch/memory/heap/linked_list_allocator.hpp | 10 +++- arch/x86_64/src/kernel/main.cpp | 11 +++- .../src/memory/heap/linked_list_allocator.cpp | 64 +++++++++++----------- 3 files changed, 48 insertions(+), 37 deletions(-) (limited to 'arch') diff --git a/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp b/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp index 71e495a..e8ecc30 100644 --- a/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp +++ b/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp @@ -49,12 +49,16 @@ namespace teachos::arch::memory::heap * @brief Splits the given free memory block into two, where the latter block keeps being free and the first part * will be used for the allocation. * - * @param current_block Free memory block we want to split. + * @param previous_block Free memory block before the block to allocate in our heap memory. Was to small to allocate + * the required size into. + * @param current_block Free memory block we want to split into a size part for the allocation and the rest for + * future allocations. * @param size Size we want to allocate at the start of the free memory block. * * @return Previous start address of the memory block we just split. */ - auto split_free_memory_block(memory_block *& current_block, std::size_t size) -> void *; + auto split_free_memory_block(memory_block * previous_block, memory_block * current_block, + std::size_t size) -> void *; /** * @brief Combines multiple free memory blocks into one if they are adjacent. @@ -76,7 +80,7 @@ namespace teachos::arch::memory::heap * @param pointer Block to deallocate. * @param size Size of the block we want to deallocate. */ - auto coalesce_free_memory_block(memory_block *& previous_block, memory_block *& current_block, void * pointer, + auto coalesce_free_memory_block(memory_block * previous_block, memory_block * current_block, void * pointer, std::size_t size) -> void; /** diff --git a/arch/x86_64/src/kernel/main.cpp b/arch/x86_64/src/kernel/main.cpp index a4f138c..7992b34 100644 --- a/arch/x86_64/src/kernel/main.cpp +++ b/arch/x86_64/src/kernel/main.cpp @@ -41,6 +41,15 @@ namespace teachos::arch::kernel } heap_allocator.deallocate(test, 1024); + + heap_allocator.allocate(1024); // test 9 + auto test10 = heap_allocator.allocate(1024); + auto test11 = heap_allocator.allocate(1024); + auto test12 = heap_allocator.allocate(1024); + heap_allocator.allocate(1024); // test 13 + heap_allocator.deallocate(test11, 1024); + heap_allocator.deallocate(test10, 1024); + heap_allocator.deallocate(test12, 1024); } auto main() -> void @@ -52,6 +61,6 @@ namespace teachos::arch::kernel memory::initialize_memory_management(); // stack_overflow_test(0); - // heap_test(); + heap_test(); } } // namespace teachos::arch::kernel diff --git a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp index 07d7e5e..706f43e 100644 --- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp +++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp @@ -27,29 +27,14 @@ namespace teachos::arch::memory::heap exception_handling::assert(size > min_allocatable_size(), "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes"); - auto & previous = first; - auto & current = first; + memory_block * previous = nullptr; + auto current = first; while (current != nullptr) { if (current->size >= size + min_allocatable_size()) { - return split_free_memory_block(current, size); - } - - if (current->size >= size) - { - if (previous != current) - { - previous->next = current->next; - } - else - { - first = current->next; - } - - clear_memory_block_header(current); - return static_cast(current); + return split_free_memory_block(previous, current, size); } previous = current; @@ -66,8 +51,8 @@ namespace teachos::arch::memory::heap auto const start_address = reinterpret_cast(pointer); auto const end_address = start_address + size; - auto & previous = first; - auto & current = first; + memory_block * previous = nullptr; + auto current = first; while (current != nullptr) { @@ -78,23 +63,35 @@ namespace teachos::arch::memory::heap break; } - previous->next = current; + previous = current; current = current->next; } coalesce_free_memory_block(previous, current, pointer, size); } - auto linked_list_allocator::split_free_memory_block(memory_block *& current_block, std::size_t size) -> void * + auto linked_list_allocator::split_free_memory_block(memory_block * previous_block, memory_block * current_block, + std::size_t size) -> void * { auto const start_address = reinterpret_cast(current_block); auto const end_address = start_address + size; - current_block = + auto const new_block = new (reinterpret_cast(end_address)) memory_block(current_block->size - size, current_block->next); + // If we want to allocate into the first block that is before any other free block, then there exists no previous + // free block (nullptr). Therefore we have to overwrite the first block instead of overwriting its next value. + if (previous_block == nullptr) + { + first = new_block; + } + else + { + previous_block->next = new_block; + } + clear_memory_block_header(current_block); return reinterpret_cast(start_address); } - auto linked_list_allocator::coalesce_free_memory_block(memory_block *& previous_block, memory_block *& current_block, + auto linked_list_allocator::coalesce_free_memory_block(memory_block * previous_block, memory_block * current_block, void * pointer, std::size_t size) -> void { auto const start_address = reinterpret_cast(pointer); @@ -105,14 +102,6 @@ namespace teachos::arch::memory::heap auto block_size = size; auto next_block = current_block; - // Heap memory has been completly used up and therefore the inital free pointer is null and this deallocation will - // result in the first inital pointer in our linked list of free memory blocks. - if (previous_block == nullptr) - { - previous_block = new (pointer) memory_block(block_size, next_block); - return; - } - // If the block we want to deallocate is before another free block and we can therefore combine both into one. // This is done by deleting the current free block and creating a new block at the start address of the block to // deallocate with both the size of the block to deallcoate and the free block next to it. @@ -127,7 +116,8 @@ namespace teachos::arch::memory::heap // If the block we want to deallocate is behind another free block and we can therefore combine both into one. // This is done by simply changin the size of the previous block to include the size of the block to deallocate. // This is done, because the previous block might still be referencered by the next field of other memory blocks. - if (start_address == (reinterpret_cast(previous_block) + previous_block->size)) + if (previous_block != nullptr && + start_address == (reinterpret_cast(previous_block) + previous_block->size)) { block_size += previous_block->size; @@ -137,6 +127,14 @@ namespace teachos::arch::memory::heap } auto const new_block = new (pointer) memory_block(block_size, next_block); + // If we want to deallocate the first block that is before any other free block, then there exists no previous free + // block (nullptr). Therefore we have to overwrite the first block instead of overwriting its + // next value. + if (previous_block == nullptr) + { + first = new_block; + return; + } previous_block->next = new_block; } -- cgit v1.2.3