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

3 files changed, 40 insertions, 25 deletions

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