Adjust linked list allocator to allow for deallocation without passing size parameter and with arbitrary size

8 files changed, 56 insertions, 59 deletions

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 d5f4561..74734af 100644
--- a/arch/x86_64/include/arch/memory/heap/bump_allocator.hpp
+++ b/arch/x86_64/include/arch/memory/heap/bump_allocator.hpp
@@ -28,23 +28,14 @@ namespace teachos::arch::memory::heap
       // Nothing to do
     }
 
-    /**
-     * @brief Allocates the specified amount of memory in the heap.
-     *
-     * @param size Amount of memory to allocate.
-     * @return Address of the first byte to the allocated area
-     */
     auto allocate(std::size_t size) -> void * override;
 
     /**
-     * @brief Deallocates heap memory at the specified location.
-     *
-     * @note Simply does nothing, because this allocator leaks all memory.
+     * @copybrief heap_allocator::deallocate
      *
-     * @param pointer Pointer to the location which should be deallocated.
-     * @param size Size of the underlying memory area we want to deallocate.
+     * @note Simply does nothing, because this allocator leaks all memory
      */
-    auto deallocate(void * pointer, std::size_t size) -> void override;
+    auto deallocate(void * pointer) -> void override;
 
   private:
     std::size_t heap_start;     ///< Start of the allocatable heap area
diff --git a/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp b/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp
index 6719bec..a1621b5 100644
--- a/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp
+++ b/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp
@@ -48,13 +48,12 @@ namespace teachos::arch::memory::heap
     static auto allocate(std::size_t size) -> void *;
 
     /**
-     * @brief Deallocated the given amount of memory starting from the given pointer address.
+     * @brief Deallocated all memory associated with the memory area starting from the given pointer address.
      * Simply forwards the call to the deallocate method of the registered heap_allocation implementation
      *
      * @param pointer Previously allocated memory area, that should now be freed
-     * @param size Size of the memory area we want to free
      */
-    static auto deallocate(void * pointer, std::size_t size) -> void;
+    static auto deallocate(void * pointer) -> void;
 
   private:
     static heap_allocator * allocator_instance;  ///< Instance used to actually allocate and deallocate
diff --git a/arch/x86_64/include/arch/memory/heap/heap_allocator.hpp b/arch/x86_64/include/arch/memory/heap/heap_allocator.hpp
index 1519155..01657f2 100644
--- a/arch/x86_64/include/arch/memory/heap/heap_allocator.hpp
+++ b/arch/x86_64/include/arch/memory/heap/heap_allocator.hpp
@@ -31,12 +31,12 @@ namespace teachos::arch::memory::heap
     virtual auto allocate(std::size_t size) -> void * = 0;
 
     /**
-     * @brief Deallocated the given amount of memory starting from the given pointer address
+     * @brief Deallocates all memory associated with the given pointer address.
+     * Simply deallocates the amount of memory created with the corresponding call to allocate
      *
      * @param pointer Previously allocated memory area, that should now be freed
-     * @param size Size of the memory area we want to free
      */
-    virtual auto deallocate(void * pointer, std::size_t size) -> void = 0;
+    virtual auto deallocate(void * pointer) -> void = 0;
   };
 }  // namespace teachos::arch::memory::heap
 
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 966e28e..d53756d 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
@@ -22,7 +22,7 @@ namespace teachos::arch::memory::heap
     linked_list_allocator(std::size_t heap_start, std::size_t heap_end);
 
     /**
-     * @brief Allocates the specified amount of memory in the heap.
+     * @copybrief heap_allocator::allocate
      *
      * @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
@@ -32,21 +32,10 @@ namespace teachos::arch::memory::heap
      * 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
      */
-    auto allocate(std::size_t size) -> void *;
+    auto allocate(std::size_t size) -> void * override;
 
-    /**
-     * @brief Deallocates heap memory at the specified location.
-     *
-     * @note Simply does nothing, because this allocator leaks all memory.
-     *
-     * @param pointer Pointer to the location which should be deallocated.
-     * @param size Size of the underlying memory area we want to deallocate.
-     */
-    auto deallocate(void * pointer, std::size_t size) -> void;
+    auto deallocate(void * pointer) -> void override;
 
   private:
     /**
@@ -79,8 +68,8 @@ namespace teachos::arch::memory::heap
      *
      * @return Previous start address of the memory block we just split, because it can now be used for the allocation.
      */
-    auto split_free_memory_block(memory_block * previous_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 Removes a free memory block from the free list and returns its address so the caller can allocate into it.
diff --git a/arch/x86_64/src/kernel/main.cpp b/arch/x86_64/src/kernel/main.cpp
index f3518a8..472aed5 100644
--- a/arch/x86_64/src/kernel/main.cpp
+++ b/arch/x86_64/src/kernel/main.cpp
@@ -39,6 +39,9 @@ namespace teachos::arch::kernel
     test2->multiboot_start = 2000;
     delete test2;
     delete test3;
+
+    auto test9 = new int(50);
+    delete test9;
   }
 
   auto main() -> void
diff --git a/arch/x86_64/src/memory/heap/bump_allocator.cpp b/arch/x86_64/src/memory/heap/bump_allocator.cpp
index bbf2021..a9fb121 100644
--- a/arch/x86_64/src/memory/heap/bump_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/bump_allocator.cpp
@@ -42,9 +42,9 @@ namespace teachos::arch::memory::heap
     }
   }
 
-  auto bump_allocator::deallocate(void * pointer, std::size_t size) -> void
+  auto bump_allocator::deallocate(void * pointer) -> void
   {
-    if (pointer || size)
+    if (pointer)
     {
     }
   }
diff --git a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp
index 71fe775..09db9ba 100644
--- a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp
@@ -10,11 +10,11 @@ namespace teachos::arch::memory::heap
 
   auto global_heap_allocator::allocate(std::size_t size) -> void * { return get().allocate(size); }
 
-  auto global_heap_allocator::deallocate(void * pointer, std::size_t size) -> void { get().deallocate(pointer, size); }
+  auto global_heap_allocator::deallocate(void * pointer) -> void { get().deallocate(pointer); }
 
   auto global_heap_allocator::register_heap_allocator(heap_allocator_type new_type) -> void
   {
-    exception_handling::assert(allocator_instance != nullptr,
+    exception_handling::assert(allocator_instance == nullptr,
                                "Calling register_heap_allocator_type can only be done once.");
 
     switch (new_type)
@@ -52,13 +52,15 @@ auto operator new(std::size_t size) -> void *
 
 auto operator delete(void * pointer) noexcept -> void
 {
-  teachos::arch::exception_handling::assert(false && pointer == nullptr,
-                                            "Called delete operator without passing required size attribute");
+  teachos::arch::memory::heap::global_heap_allocator::deallocate(pointer);
 }
 
 auto operator delete(void * pointer, std::size_t size) noexcept -> void
 {
-  teachos::arch::memory::heap::global_heap_allocator::deallocate(pointer, size);
+  if (size)
+  {
+  }
+  teachos::arch::memory::heap::global_heap_allocator::deallocate(pointer);
 }
 
 auto operator new[](std::size_t size) -> void *
@@ -68,11 +70,13 @@ auto operator new[](std::size_t size) -> void *
 
 auto operator delete[](void * pointer) noexcept -> void
 {
-  teachos::arch::exception_handling::assert(false && pointer == nullptr,
-                                            "Called delete[] operator without passing required size attribute");
+  teachos::arch::memory::heap::global_heap_allocator::deallocate(pointer);
 }
 
 auto operator delete[](void * pointer, std::size_t size) noexcept -> void
 {
-  teachos::arch::memory::heap::global_heap_allocator::deallocate(pointer, size);
+  if (size)
+  {
+  }
+  teachos::arch::memory::heap::global_heap_allocator::deallocate(pointer);
 }
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 e5bae21..9beb466 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -3,6 +3,8 @@
 #include "arch/exception_handling/assert.hpp"
 #include "arch/exception_handling/panic.hpp"
 
+#include <algorithm>
+
 namespace teachos::arch::memory::heap
 {
   linked_list_allocator::linked_list_allocator(std::size_t heap_start, std::size_t heap_end)
@@ -21,8 +23,9 @@ namespace teachos::arch::memory::heap
 
   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");
+    // Add size of size_t to the total allocated size, because we add a header that includes the size of the allocated
+    // block, to allow for deallocation without the need to call with the corresponding size
+    auto const total_size = size + sizeof(std::size_t);
     mutex.lock();
 
     memory_block * previous = nullptr;
@@ -30,17 +33,23 @@ namespace teachos::arch::memory::heap
 
     while (current != nullptr)
     {
-      if (current->size == size)
+      if (current->size == total_size)
       {
         auto const memory_address = remove_free_memory_block(previous, current);
+        new (memory_address) std::size_t(total_size);
         mutex.unlock();
-        return memory_address;
+        return reinterpret_cast<void *>(reinterpret_cast<std::size_t>(memory_address) + sizeof(std::size_t));
       }
-      else if (current->size >= size + min_allocatable_size())
+      else if (current->size >= total_size + min_allocatable_size())
       {
-        auto const memory_address = split_free_memory_block(previous, current, size);
+        // Ensure that the allocated size block is atleast 16 bytes (required because if we free the hole afterwards
+        // there needs to be enough space for a memory block). Therefore we allocate more than is actually required if
+        // the total size was less and simply deallocate it as well
+        auto const max_size = std::max(total_size, min_allocatable_size());
+        auto const memory_address = split_free_memory_block(previous, current, max_size);
+        new (memory_address) std::size_t(max_size);
         mutex.unlock();
-        return memory_address;
+        return reinterpret_cast<void *>(reinterpret_cast<std::size_t>(memory_address) + sizeof(std::size_t));
       }
 
       previous = current;
@@ -50,14 +59,16 @@ namespace teachos::arch::memory::heap
     exception_handling::panic("[Linked List Allocator] Out of memory");
   }
 
-  auto linked_list_allocator::deallocate(void * pointer, std::size_t size) -> void
+  auto linked_list_allocator::deallocate(void * pointer) -> void
   {
-    exception_handling::assert(size > min_allocatable_size(),
-                               "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes");
     mutex.lock();
 
-    auto const start_address = reinterpret_cast<std::size_t>(pointer);
-    auto const end_address = start_address + size;
+    // Read configured header size of the complete allocated block
+    auto const header_pointer = reinterpret_cast<void *>(reinterpret_cast<std::size_t>(pointer) - sizeof(std::size_t));
+    auto const total_size = *reinterpret_cast<std::size_t *>(header_pointer);
+
+    auto const start_address = reinterpret_cast<std::size_t>(header_pointer);
+    auto const end_address = start_address + total_size;
 
     memory_block * previous = nullptr;
     auto current = first;
@@ -75,12 +86,12 @@ namespace teachos::arch::memory::heap
       current = current->next;
     }
 
-    coalesce_free_memory_block(previous, current, pointer, size);
+    coalesce_free_memory_block(previous, current, header_pointer, total_size);
     mutex.unlock();
   }
 
-  auto linked_list_allocator::remove_free_memory_block(memory_block * previous_block,
-                                                       memory_block * current_block) -> void *
+  auto linked_list_allocator::remove_free_memory_block(memory_block * previous_block, memory_block * current_block)
+      -> void *
   {
     return replace_free_memory_block(previous_block, current_block, current_block->next);
   }