2 files changed, 55 insertions, 11 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 49217d5..4ccc6a9 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
@@ -23,6 +23,15 @@ namespace teachos::arch::memory::heap
     /**
      * @brief Allocates the specified amount of memory in the heap.
      *
+     * @note The specified size is used to find a free memory block with the exact same size, meaning we can remove that
+     * free memory block from the free list and simply return its address. Or it has to be big enough to hold the size
+     * and alteast enough memory for another free memory block entry (16 bytes). If the amount of memory of that free
+     * memory block is in between we cannot use it for our allocation, because we could only return it to the user, but
+     * the additional bytes, could not be used to create a free memory block. Additionaly the user couldn't know
+     * they received more memory than wanted. Therefore the memory would simply be unused and because it is neither
+     * allocated nor deallocated would never be indexed by the free memory list. We would therefore permanently loose
+     * that memory, to prevent that allocation into free memory blocks like that are impossible.
+     *
      * @param size Amount of memory to allocate.
      * @return Address of the first byte to the allocated area
      */
@@ -47,11 +56,24 @@ namespace teachos::arch::memory::heap
     auto constexpr min_allocatable_size() -> std::size_t { return sizeof(memory_block); }
 
     /**
-     * @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.
+     * @brief Removes a free memory block from the free list and returns its address so the caller can allocate into it.
+     *
+     * @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 remove from the free list and return for the allocation.
+     * @param size Size we want to allocate that is exactly the same as the size of the curernt block
+     *
+     * @return Previous start address of the memory block we removed, because it has the exact required size.
+     */
+    auto remove_free_memory_block(memory_block * previous_block, memory_block * current_block,
+                                  std::size_t size) -> void *;
+
+    /**
+     * @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 previous_block Free memory block before the block to allocate in our heap memory. Was to small to allocate
-     * the required size into.
+     * @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.
@@ -93,14 +115,14 @@ namespace teachos::arch::memory::heap
      * @note Done so the given pointer can be reused to construct other classes into, without having the old values.
      * Required because we cannot call delete, because it causes "undefined reference to `sbrk`".
      *
-     * @param pointer Address we want to clear the memory block header at (16 bytes)
+     * @param pointer Address we want to clear the memory block header at (16 bytes).
      */
     auto clear_memory_block_header(void * pointer) -> void;
 
-    std::size_t heap_start;  ///< Start of the allocatable heap area
-    std::size_t heap_end;    ///< End of the allocatable heap area
-    memory_block * first;    ///< First free entry in our memory
-    shared::mutex mutex;
+    std::size_t heap_start;  ///< Start of the allocatable heap area.
+    std::size_t heap_end;    ///< End of the allocatable heap area.
+    memory_block * first;    ///< First free entry in our memory.
+    shared::mutex mutex;     ///< Mutex to ensure only one thread calls allocate or deallocate at once.
   };
 }  // namespace teachos::arch::memory::heap
 
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 1c5c443..d922dc8 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -34,7 +34,11 @@ namespace teachos::arch::memory::heap
 
     while (current != nullptr)
     {
-      if (current->size >= size + min_allocatable_size())
+      if (current->size == size)
+      {
+        return remove_free_memory_block(previous, current, size);
+      }
+      else if (current->size >= size + min_allocatable_size())
       {
         auto memory_address = split_free_memory_block(previous, current, size);
         mutex.unlock();
@@ -77,6 +81,24 @@ namespace teachos::arch::memory::heap
     mutex.unlock();
   }
 
+  auto linked_list_allocator::remove_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);
+    // 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 = nullptr;
+    }
+    else
+    {
+      previous_block->next = current_block->next;
+    }
+    clear_memory_block_header(current_block);
+    return reinterpret_cast<void *>(start_address);
+  }
+
   auto linked_list_allocator::split_free_memory_block(memory_block * previous_block, memory_block * current_block,
                                                       std::size_t size) -> void *
   {
@@ -92,7 +114,7 @@ namespace teachos::arch::memory::heap
     }
     else
     {
-      previous_block = new_block;
+      previous_block->next = new_block;
     }
     clear_memory_block_header(current_block);
     return reinterpret_cast<void *>(start_address);