Fix algorithm issues with linked list allocator

3 files changed, 48 insertions, 37 deletions

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<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;
   }