implement first half of linked list dallocation

7 files changed, 61 insertions, 28 deletions

diff --git a/arch/x86_64/CMakeLists.txt b/arch/x86_64/CMakeLists.txt
index 4ba6590..4a02e15 100644
--- a/arch/x86_64/CMakeLists.txt
+++ b/arch/x86_64/CMakeLists.txt
@@ -57,7 +57,7 @@ target_sources("_memory" PRIVATE
   "src/memory/cpu/control_register.cpp"
   "src/memory/cpu/msr.cpp"
   "src/memory/heap/bump_allocator.cpp"
-  "src/memory/heap/memory_hole.cpp"
+  "src/memory/heap/memory_block.cpp"
   "src/memory/heap/linked_list_allocator.cpp"
 )
 
diff --git a/arch/x86_64/include/arch/memory/heap/bump_allocator.hpp b/arch/x86_64/include/arch/memory/heap/bump_allocator.hpp
index 595eeea..545b72f 100644
--- a/arch/x86_64/include/arch/memory/heap/bump_allocator.hpp
+++ b/arch/x86_64/include/arch/memory/heap/bump_allocator.hpp
@@ -42,7 +42,7 @@ namespace teachos::arch::memory::heap
      * @param pointer Pointer to the location which should be deallocated.
      * @param size Size of the underlying memory area we want to deallocate.
      */
-    auto deallocate(uint8_t * pointer, std::size_t size) -> void;
+    auto deallocate(void * pointer, std::size_t size) -> void;
 
   private:
     std::size_t heap_start;     ///< Start of the allocatable heap area
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 5f9a72b..99d0013 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
@@ -1,7 +1,7 @@
 #ifndef TEACHOS_ARCH_X86_64_MEMORY_HEAP_LINKED_LIST_ALLOCATOR_HPP
 #define TEACHOS_ARCH_X86_64_MEMORY_HEAP_LINKED_LIST_ALLOCATOR_HPP
 
-#include "arch/memory/heap/memory_hole.hpp"
+#include "arch/memory/heap/memory_block.hpp"
 
 #include <cstdint>
 
@@ -37,7 +37,7 @@ namespace teachos::arch::memory::heap
      * @param pointer Pointer to the location which should be deallocated.
      * @param size Size of the underlying memory area we want to deallocate.
      */
-    auto deallocate(uint8_t * pointer, std::size_t size) -> void;
+    auto deallocate(void * pointer, std::size_t size) -> void;
 
   private:
     /**
@@ -45,22 +45,22 @@ namespace teachos::arch::memory::heap
      *
      * @return Smallest allocatable block of heap memory.
      */
-    auto constexpr min_allocatable_size() -> std::size_t { return sizeof(memory_hole); }
+    auto constexpr min_allocatable_size() -> std::size_t { return sizeof(memory_block); }
 
     /**
      * @brief Splits the given hole into two, where the latter block keeps beeing free and the first part will be used
      * for the allocation.
      *
-     * @param current_hole Hole we want to split.
+     * @param current_block Hole we want to split.
      * @param size Size we want to allocate at the start of the hole.
      *
      * @return Address of the hole we just split.
      */
-    auto split_hole(memory_hole *& current_hole, std::size_t size) -> void *;
+    auto split_free_memory_block(memory_block *& current_block, std::size_t size) -> void *;
 
     std::size_t heap_start;  ///< Start of the allocatable heap area
     std::size_t heap_end;    ///< End of the allocatable heap area
-    memory_hole * first;     ///< First free entry in our memory
+    memory_block * first;    ///< First free entry in our memory
   };
 }  // namespace teachos::arch::memory::heap
 
diff --git a/arch/x86_64/include/arch/memory/heap/memory_hole.hpp b/arch/x86_64/include/arch/memory/heap/memory_block.hpp
index e017599..c48d0cd 100644
--- a/arch/x86_64/include/arch/memory/heap/memory_hole.hpp
+++ b/arch/x86_64/include/arch/memory/heap/memory_block.hpp
@@ -1,5 +1,5 @@
-#ifndef TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_HOLE_HPP
-#define TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_HOLE_HPP
+#ifndef TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_BLOCK_HPP
+#define TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_BLOCK_HPP
 
 #include <cstdint>
 
@@ -9,7 +9,7 @@ namespace teachos::arch::memory::heap
    * @brief Block containing free memory, pointing to the next free hole (nullptr) if there is none.
    * Forms a single linked list.
    */
-  struct memory_hole
+  struct memory_block
   {
     /**
      * @brief Constructor,
@@ -17,12 +17,12 @@ namespace teachos::arch::memory::heap
      * @param size Amount of free memory of this specific hole.
      * @param next Optional pointer to the next free memory.
      */
-    memory_hole(std::size_t size, memory_hole * next);
+    memory_block(std::size_t size, memory_block * next);
 
     std::size_t size;  ///< Amount of free memory this hole contains, has to always be atleast 16 bytes to hold the size
                        ///< variable and the pointer to the next hole.
-    memory_hole * next;  ///< Optional pointer to the next free memory, holds nullptr if there is none.
+    memory_block * next;  ///< Optional pointer to the next free memory, holds nullptr if there is none.
   };
 }  // namespace teachos::arch::memory::heap
 
-#endif  // TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_HOLE_HPP
+#endif  // TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_BLOCK_HPP
diff --git a/arch/x86_64/src/memory/heap/bump_allocator.cpp b/arch/x86_64/src/memory/heap/bump_allocator.cpp
index 8807645..bbf2021 100644
--- a/arch/x86_64/src/memory/heap/bump_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/bump_allocator.cpp
@@ -42,7 +42,7 @@ namespace teachos::arch::memory::heap
     }
   }
 
-  auto bump_allocator::deallocate(uint8_t * pointer, std::size_t size) -> void
+  auto bump_allocator::deallocate(void * pointer, std::size_t size) -> void
   {
     if (pointer || size)
     {
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 a2a8c79..9b27f70 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -17,20 +17,24 @@ namespace teachos::arch::memory::heap
         heap_size < min_allocatable_size(),
         "[Linked List Allocator] Total heap size can not be smaller than minimum of 16 bytes to hold "
         "atleast one memory hole entry");
-    first = new (reinterpret_cast<void *>(heap_start)) memory_hole(heap_size, nullptr);
+    first = new (reinterpret_cast<void *>(heap_start)) memory_block(heap_size, nullptr);
   }
 
   auto linked_list_allocator::allocate(std::size_t size) -> void *
   {
+    exception_handling::assert(size < min_allocatable_size(),
+                               "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes");
+
     auto & previous = first;
     auto & current = first;
+
     while (current != nullptr)
     {
-      if (current->size > size)
+      if (current->size >= size + min_allocatable_size())
       {
-        return split_hole(current, size);
+        return split_free_memory_block(current, size);
       }
-      else if (current->size == size)
+      else if (current->size >= size)
       {
         if (previous != current)
         {
@@ -40,30 +44,59 @@ namespace teachos::arch::memory::heap
         {
           current = current->next;
         }
+
         delete current;
         return static_cast<void *>(current);
       }
+
       previous = current;
       current = current->next;
     }
     exception_handling::panic("[Linked List Allocator] Out of memory");
   }
 
-  auto linked_list_allocator::deallocate(uint8_t * pointer, std::size_t size) -> void
+  auto linked_list_allocator::deallocate(void * pointer, std::size_t size) -> void
   {
-    auto const deallocate_size = std::max(size, min_allocatable_size());
-    if (pointer || deallocate_size)
+    exception_handling::assert(size < min_allocatable_size(),
+                               "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes");
+
+    auto & previous = first;
+    auto & current = first;
+
+    while (current != nullptr)
     {
+      // if pointer + size < current
+      // create memory block
+      auto const previous_address = reinterpret_cast<std::size_t>(pointer);
+      auto const new_address = previous_address + size;
+
+      if (new_address != reinterpret_cast<std::size_t>(current) &&
+          previous_address != (reinterpret_cast<std::size_t>(previous) + previous->size))
+      {
+        auto new_block = new (pointer) memory_block(size, current);
+        previous->next = new_block;
+        return;
+      }
+
+      // elseif pointer + size == current
+      // combine memory block with current
+      // combine(previous, pointer, current)
+
+      previous = current;
+      current = current->next;
     }
   }
 
-  auto split_hole(memory_hole *& current_hole, std::size_t size) -> void *
+  auto linked_list_allocator::split_free_memory_block(memory_block *& current_block, std::size_t size) -> void *
   {
-    auto const previous_address = reinterpret_cast<std::size_t>(current_hole);
+    auto const previous_address = reinterpret_cast<std::size_t>(current_block);
     auto const new_address = previous_address + size;
-    current_hole =
-        new (reinterpret_cast<void *>(new_address)) memory_hole(current_hole->size - size, current_hole->next);
+    current_block =
+        new (reinterpret_cast<void *>(new_address)) memory_block(current_block->size - size, current_block->next);
     return reinterpret_cast<void *>(previous_address);
   }
 
+  // auto linked_list_allocator::combine_free_memory_block(memory_block *& previous_block, memory_block *&
+  // current_block, std::size_t size) -> void *
+
 }  // namespace teachos::arch::memory::heap
diff --git a/arch/x86_64/src/memory/heap/memory_hole.cpp b/arch/x86_64/src/memory/heap/memory_block.cpp
index 7590610..b68dd6d 100644
--- a/arch/x86_64/src/memory/heap/memory_hole.cpp
+++ b/arch/x86_64/src/memory/heap/memory_block.cpp
@@ -1,8 +1,8 @@
-#include "arch/memory/heap/memory_hole.hpp"
+#include "arch/memory/heap/memory_block.hpp"
 
 namespace teachos::arch::memory::heap
 {
-  memory_hole::memory_hole(std::size_t size, memory_hole * next)
+  memory_block::memory_block(std::size_t size, memory_block * next)
       : size(size)
       , next(next)
   {