Fix algorithm issues with linked list allocator

1 files changed, 31 insertions, 33 deletions

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<void *>(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<std::size_t>(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<std::size_t>(current_block);
     auto const end_address = start_address + size;
-    current_block =
+    auto const new_block =
         new (reinterpret_cast<void *>(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<void *>(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<std::size_t>(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<std::size_t>(previous_block) + previous_block->size))
+    if (previous_block != nullptr &&
+        start_address == (reinterpret_cast<std::size_t>(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;
   }