From 55f32173e97fdcf4a45006b66cc4b20329a5c7af Mon Sep 17 00:00:00 2001
From: Fabian Imhof <fabian.imhof@ost.ch>
Date: Sun, 24 Nov 2024 13:10:21 +0000
Subject: implement basic heap and remap it

---
 arch/x86_64/src/memory/heap/allocator.cpp | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)
 create mode 100644 arch/x86_64/src/memory/heap/allocator.cpp

(limited to 'arch/x86_64/src/memory/heap')

diff --git a/arch/x86_64/src/memory/heap/allocator.cpp b/arch/x86_64/src/memory/heap/allocator.cpp
new file mode 100644
index 0000000..c9ddd78
--- /dev/null
+++ b/arch/x86_64/src/memory/heap/allocator.cpp
@@ -0,0 +1,27 @@
+#include "arch/memory/heap/allocator.hpp"
+
+#include "arch/exception_handling/assert.hpp"
+
+namespace teachos::arch::memory::heap
+{
+  auto bump_allocator::allocate(std::size_t size) -> void *
+  {
+    // Uses some sort of alignment orignally:
+    // https://github.com/phil-opp/blog_os/blob/7f6576c9dc34e360b81236c54c25c7827fd6a2df/src/memory/heap_allocator.rs#L24
+    auto alloc_start = next;
+    auto alloc_end = next + size;
+
+    arch::exception_handling::assert(alloc_end <= heap_end, "[Heap Allocator] Out of memory!");
+
+    next = alloc_end;
+    return reinterpret_cast<void *>(alloc_start);
+  }
+
+  auto bump_allocator::deallocate(uint8_t * pointer, std::size_t size) -> void
+  {
+    // Memory leak
+    if (pointer || size)
+    {
+    }
+  }
+}  // namespace teachos::arch::memory::heap
\ No newline at end of file
-- 
cgit v1.2.3


From 24805678884bcfcc3f14e88757955ab574d647cb Mon Sep 17 00:00:00 2001
From: Fabian Imhof <fabian.imhof@ost.ch>
Date: Sun, 24 Nov 2024 13:18:31 +0000
Subject: add doxygen comments to remapping

---
 arch/x86_64/src/memory/heap/allocator.cpp | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

(limited to 'arch/x86_64/src/memory/heap')

diff --git a/arch/x86_64/src/memory/heap/allocator.cpp b/arch/x86_64/src/memory/heap/allocator.cpp
index c9ddd78..bb61be4 100644
--- a/arch/x86_64/src/memory/heap/allocator.cpp
+++ b/arch/x86_64/src/memory/heap/allocator.cpp
@@ -17,10 +17,10 @@ namespace teachos::arch::memory::heap
     return reinterpret_cast<void *>(alloc_start);
   }
 
-  auto bump_allocator::deallocate(uint8_t * pointer, std::size_t size) -> void
+  auto bump_allocator::deallocate(uint8_t * pointer) -> void
   {
-    // Memory leak
-    if (pointer || size)
+    // Not implemented; leaking memory
+    if (pointer)
     {
     }
   }
-- 
cgit v1.2.3


From c291e1ed629489c418049f6c4116433636717636 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Sun, 24 Nov 2024 13:51:12 +0000
Subject: Add comments and rename file

---
 arch/x86_64/src/memory/heap/allocator.cpp      | 27 --------------------------
 arch/x86_64/src/memory/heap/bump_allocator.cpp | 26 +++++++++++++++++++++++++
 2 files changed, 26 insertions(+), 27 deletions(-)
 delete mode 100644 arch/x86_64/src/memory/heap/allocator.cpp
 create mode 100644 arch/x86_64/src/memory/heap/bump_allocator.cpp

(limited to 'arch/x86_64/src/memory/heap')

diff --git a/arch/x86_64/src/memory/heap/allocator.cpp b/arch/x86_64/src/memory/heap/allocator.cpp
deleted file mode 100644
index bb61be4..0000000
--- a/arch/x86_64/src/memory/heap/allocator.cpp
+++ /dev/null
@@ -1,27 +0,0 @@
-#include "arch/memory/heap/allocator.hpp"
-
-#include "arch/exception_handling/assert.hpp"
-
-namespace teachos::arch::memory::heap
-{
-  auto bump_allocator::allocate(std::size_t size) -> void *
-  {
-    // Uses some sort of alignment orignally:
-    // https://github.com/phil-opp/blog_os/blob/7f6576c9dc34e360b81236c54c25c7827fd6a2df/src/memory/heap_allocator.rs#L24
-    auto alloc_start = next;
-    auto alloc_end = next + size;
-
-    arch::exception_handling::assert(alloc_end <= heap_end, "[Heap Allocator] Out of memory!");
-
-    next = alloc_end;
-    return reinterpret_cast<void *>(alloc_start);
-  }
-
-  auto bump_allocator::deallocate(uint8_t * pointer) -> void
-  {
-    // Not implemented; leaking memory
-    if (pointer)
-    {
-    }
-  }
-}  // namespace teachos::arch::memory::heap
\ No newline at end of file
diff --git a/arch/x86_64/src/memory/heap/bump_allocator.cpp b/arch/x86_64/src/memory/heap/bump_allocator.cpp
new file mode 100644
index 0000000..486ece8
--- /dev/null
+++ b/arch/x86_64/src/memory/heap/bump_allocator.cpp
@@ -0,0 +1,26 @@
+#include "arch/memory/heap/bump_allocator.hpp"
+
+#include "arch/exception_handling/assert.hpp"
+
+namespace teachos::arch::memory::heap
+{
+  auto bump_allocator::allocate(std::size_t size) -> void *
+  {
+    // Uses some sort of alignment orignally:
+    // https://github.com/phil-opp/blog_os/blob/7f6576c9dc34e360b81236c54c25c7827fd6a2df/src/memory/heap_allocator.rs#L24
+    auto alloc_start = next;
+    auto alloc_end = next + size;
+
+    arch::exception_handling::assert(alloc_end <= heap_end, "[Heap Allocator] Out of memory!");
+
+    next = alloc_end;
+    return reinterpret_cast<void *>(alloc_start);
+  }
+
+  auto bump_allocator::deallocate(uint8_t * pointer, std::size_t size) -> void
+  {
+    if (pointer || size)
+    {
+    }
+  }
+}  // namespace teachos::arch::memory::heap
\ No newline at end of file
-- 
cgit v1.2.3


From eada7bbb150fd81e6fbf71b1df28c8dc19393cfa Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Sun, 24 Nov 2024 15:19:29 +0000
Subject: Adjust bump allocator comment

---
 arch/x86_64/src/memory/heap/bump_allocator.cpp | 2 --
 1 file changed, 2 deletions(-)

(limited to 'arch/x86_64/src/memory/heap')

diff --git a/arch/x86_64/src/memory/heap/bump_allocator.cpp b/arch/x86_64/src/memory/heap/bump_allocator.cpp
index 486ece8..1ab8ea9 100644
--- a/arch/x86_64/src/memory/heap/bump_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/bump_allocator.cpp
@@ -6,8 +6,6 @@ namespace teachos::arch::memory::heap
 {
   auto bump_allocator::allocate(std::size_t size) -> void *
   {
-    // Uses some sort of alignment orignally:
-    // https://github.com/phil-opp/blog_os/blob/7f6576c9dc34e360b81236c54c25c7827fd6a2df/src/memory/heap_allocator.rs#L24
     auto alloc_start = next;
     auto alloc_end = next + size;
 
-- 
cgit v1.2.3


From d2aa4fbf948a56df5328e0f1b8ec3dfd52b16e13 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Tue, 26 Nov 2024 09:49:06 +0000
Subject: Make bump allocator atomic and therefore thread safe

---
 arch/x86_64/src/memory/heap/bump_allocator.cpp | 43 +++++++++++++++++++++-----
 1 file changed, 35 insertions(+), 8 deletions(-)

(limited to 'arch/x86_64/src/memory/heap')

diff --git a/arch/x86_64/src/memory/heap/bump_allocator.cpp b/arch/x86_64/src/memory/heap/bump_allocator.cpp
index 1ab8ea9..19ced47 100644
--- a/arch/x86_64/src/memory/heap/bump_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/bump_allocator.cpp
@@ -2,17 +2,43 @@
 
 #include "arch/exception_handling/assert.hpp"
 
+#include <limits>
+#include <type_traits>
+
 namespace teachos::arch::memory::heap
 {
-  auto bump_allocator::allocate(std::size_t size) -> void *
+  namespace
   {
-    auto alloc_start = next;
-    auto alloc_end = next + size;
-
-    arch::exception_handling::assert(alloc_end <= heap_end, "[Heap Allocator] Out of memory!");
+    template<typename T>
+    auto saturating_add(T x, T y) -> T
+      requires std::is_unsigned_v<T>
+    {
+      if (x > std::numeric_limits<T>::max() - y)
+      {
+        return std::numeric_limits<T>::max();
+      }
+      T result = x + y;
+      return result;
+    }
+  }  // namespace
 
-    next = alloc_end;
-    return reinterpret_cast<void *>(alloc_start);
+  auto bump_allocator::allocate(std::size_t size) -> void *
+  {
+    // Repeat allocation until it succeeds, has to be done, because another allocator could overtake it at any time
+    // causing the value to differ and the calculation to have to be redone.
+    for (;;)
+    {
+      auto alloc_start = next.load(std::memory_order::relaxed);
+      auto const alloc_end = saturating_add(alloc_start, size);
+      arch::exception_handling::assert(alloc_end <= heap_end, "[Heap Allocator] Out of memory");
+      // Check if the atomic value is still the one initally loaded, if it isn't we have been overtaken by another
+      // thread and need to redo the calculation.
+      auto const updated = next.compare_exchange_strong(alloc_start, alloc_end, std::memory_order::relaxed);
+      if (updated)
+      {
+        return reinterpret_cast<void *>(alloc_start);
+      }
+    }
   }
 
   auto bump_allocator::deallocate(uint8_t * pointer, std::size_t size) -> void
@@ -21,4 +47,5 @@ namespace teachos::arch::memory::heap
     {
     }
   }
-}  // namespace teachos::arch::memory::heap
\ No newline at end of file
+
+}  // namespace teachos::arch::memory::heap
-- 
cgit v1.2.3


From a4268440d5c77f39032bb9f003aafd7fef2ca997 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Tue, 26 Nov 2024 11:09:59 +0000
Subject: Replace strong with weak compare_exchange

---
 arch/x86_64/src/memory/heap/bump_allocator.cpp | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

(limited to 'arch/x86_64/src/memory/heap')

diff --git a/arch/x86_64/src/memory/heap/bump_allocator.cpp b/arch/x86_64/src/memory/heap/bump_allocator.cpp
index 19ced47..8807645 100644
--- a/arch/x86_64/src/memory/heap/bump_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/bump_allocator.cpp
@@ -32,8 +32,9 @@ namespace teachos::arch::memory::heap
       auto const alloc_end = saturating_add(alloc_start, size);
       arch::exception_handling::assert(alloc_end <= heap_end, "[Heap Allocator] Out of memory");
       // Check if the atomic value is still the one initally loaded, if it isn't we have been overtaken by another
-      // thread and need to redo the calculation.
-      auto const updated = next.compare_exchange_strong(alloc_start, alloc_end, std::memory_order::relaxed);
+      // thread and need to redo the calculation. Spurious failure by weak can be ignored, because the whole allocation
+      // is wrapped in an infinite for loop so a failure that wasn't actually one will simply be retried until it works.
+      auto const updated = next.compare_exchange_weak(alloc_start, alloc_end, std::memory_order::relaxed);
       if (updated)
       {
         return reinterpret_cast<void *>(alloc_start);
-- 
cgit v1.2.3


From 31796138b1c85e7b3236055b6d93d568e1fe8a81 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Thu, 28 Nov 2024 12:40:04 +0000
Subject: Create base of linked list allocator

---
 arch/x86_64/src/memory/heap/linked_list_allocator.cpp | 16 ++++++++++++++++
 arch/x86_64/src/memory/heap/memory_hole.cpp           | 11 +++++++++++
 2 files changed, 27 insertions(+)
 create mode 100644 arch/x86_64/src/memory/heap/linked_list_allocator.cpp
 create mode 100644 arch/x86_64/src/memory/heap/memory_hole.cpp

(limited to 'arch/x86_64/src/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
new file mode 100644
index 0000000..b0f011b
--- /dev/null
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -0,0 +1,16 @@
+#include "arch/memory/heap/linked_list_allocator.hpp"
+
+#include "arch/exception_handling/assert.hpp"
+
+namespace teachos::arch::memory::heap
+{
+  linked_list_allocator::linked_list_allocator(std::size_t heap_start, std::size_t heap_end)
+      : heap_start(heap_start)
+      , heap_end(heap_end)
+      , first(heap_end - heap_start, nullptr)
+  {
+    exception_handling::assert(heap_end - heap_start < min_allocatable_size(),
+                               "[Memory Hole List] Total heap size can not be smaller than minimum of 16 bytes to hold "
+                               "atleast one memory hole entry");
+  }
+}  // 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_hole.cpp
new file mode 100644
index 0000000..7590610
--- /dev/null
+++ b/arch/x86_64/src/memory/heap/memory_hole.cpp
@@ -0,0 +1,11 @@
+#include "arch/memory/heap/memory_hole.hpp"
+
+namespace teachos::arch::memory::heap
+{
+  memory_hole::memory_hole(std::size_t size, memory_hole * next)
+      : size(size)
+      , next(next)
+  {
+    // Nothing to do
+  }
+}  // namespace teachos::arch::memory::heap
-- 
cgit v1.2.3


From d3e4df4dd4ee117e247f78a86746bf178787bc8f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Thu, 28 Nov 2024 13:53:01 +0000
Subject: Start with linked list alloc and dealloc

---
 .../src/memory/heap/linked_list_allocator.cpp      | 27 ++++++++++++++++++++++
 1 file changed, 27 insertions(+)

(limited to 'arch/x86_64/src/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 b0f011b..006d9c7 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -2,6 +2,8 @@
 
 #include "arch/exception_handling/assert.hpp"
 
+#include <algorithm>
+
 namespace teachos::arch::memory::heap
 {
   linked_list_allocator::linked_list_allocator(std::size_t heap_start, std::size_t heap_end)
@@ -13,4 +15,29 @@ namespace teachos::arch::memory::heap
                                "[Memory Hole List] Total heap size can not be smaller than minimum of 16 bytes to hold "
                                "atleast one memory hole entry");
   }
+
+  auto linked_list_allocator::allocate(std::size_t size) -> void *
+  {
+    if (first.next == nullptr || size)
+    {
+    }
+    return nullptr;
+  }
+
+  auto linked_list_allocator::deallocate(uint8_t * pointer, std::size_t size) -> void
+  {
+    auto const deallocate_size = std::max(size, min_allocatable_size());
+    if (pointer || deallocate_size)
+    {
+    }
+  }
+
+  auto split_hole(memory_hole & current_hole, memory_hole *& new_hole) -> void *
+  {
+    if (new_hole)
+    {
+    }
+    return static_cast<void *>(&current_hole);
+  }
+
 }  // namespace teachos::arch::memory::heap
-- 
cgit v1.2.3


From 9af867de0050eef28772f7dee799666ae343950e Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Thu, 28 Nov 2024 14:33:42 +0000
Subject: Start imlementation on actual algorithm

---
 .../src/memory/heap/linked_list_allocator.cpp      | 44 ++++++++++++++++------
 1 file changed, 33 insertions(+), 11 deletions(-)

(limited to 'arch/x86_64/src/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 006d9c7..f4ba5e2 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -1,6 +1,7 @@
 #include "arch/memory/heap/linked_list_allocator.hpp"
 
 #include "arch/exception_handling/assert.hpp"
+#include "arch/exception_handling/panic.hpp"
 
 #include <algorithm>
 
@@ -9,19 +10,39 @@ namespace teachos::arch::memory::heap
   linked_list_allocator::linked_list_allocator(std::size_t heap_start, std::size_t heap_end)
       : heap_start(heap_start)
       , heap_end(heap_end)
-      , first(heap_end - heap_start, nullptr)
+      , first(nullptr)
   {
-    exception_handling::assert(heap_end - heap_start < min_allocatable_size(),
-                               "[Memory Hole List] Total heap size can not be smaller than minimum of 16 bytes to hold "
-                               "atleast one memory hole entry");
+    auto const heap_size = heap_end - heap_start;
+    exception_handling::assert(
+        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);
   }
 
   auto linked_list_allocator::allocate(std::size_t size) -> void *
   {
-    if (first.next == nullptr || size)
+    memory_hole * previous = nullptr;
+    auto current = first;
+    while (current != nullptr)
     {
+      if (current->size > size)
+      {
+        return split_hole(current, size);
+      }
+      else if (current->size == size)
+      {
+        if (previous != nullptr)
+        {
+          previous->next = current->next;
+        }
+        delete current;
+        return static_cast<void *>(current);
+      }
+      previous = current;
+      current = current->next;
     }
-    return nullptr;
+    exception_handling::panic("[Linked List Allocator] Out of memory");
   }
 
   auto linked_list_allocator::deallocate(uint8_t * pointer, std::size_t size) -> void
@@ -32,12 +53,13 @@ namespace teachos::arch::memory::heap
     }
   }
 
-  auto split_hole(memory_hole & current_hole, memory_hole *& new_hole) -> void *
+  auto split_hole(memory_hole *& current_hole, std::size_t size) -> void *
   {
-    if (new_hole)
-    {
-    }
-    return static_cast<void *>(&current_hole);
+    auto const previous_address = reinterpret_cast<std::size_t>(current_hole);
+    auto const new_address = previous_address + size;
+    current_hole =
+        new (reinterpret_cast<void *>(new_address)) memory_hole(current_hole->size - size, current_hole->next);
+    return reinterpret_cast<void *>(previous_address);
   }
 
 }  // namespace teachos::arch::memory::heap
-- 
cgit v1.2.3


From 318fbff1717b291c81db8f9c4d5a84019fe2b4b9 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Sun, 1 Dec 2024 10:21:17 +0000
Subject: Adjust allocate

---
 arch/x86_64/src/memory/heap/linked_list_allocator.cpp | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

(limited to 'arch/x86_64/src/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 f4ba5e2..a2a8c79 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -22,8 +22,8 @@ namespace teachos::arch::memory::heap
 
   auto linked_list_allocator::allocate(std::size_t size) -> void *
   {
-    memory_hole * previous = nullptr;
-    auto current = first;
+    auto & previous = first;
+    auto & current = first;
     while (current != nullptr)
     {
       if (current->size > size)
@@ -32,10 +32,14 @@ namespace teachos::arch::memory::heap
       }
       else if (current->size == size)
       {
-        if (previous != nullptr)
+        if (previous != current)
         {
           previous->next = current->next;
         }
+        else
+        {
+          current = current->next;
+        }
         delete current;
         return static_cast<void *>(current);
       }
-- 
cgit v1.2.3


From eba6c94eed15b90ea8a09e4bc16ae1c0f1645dea Mon Sep 17 00:00:00 2001
From: Fabian Imhof <fabian.imhof@ost.ch>
Date: Sun, 1 Dec 2024 11:08:00 +0000
Subject: implement first half of linked list dallocation

---
 arch/x86_64/src/memory/heap/bump_allocator.cpp     |  2 +-
 .../src/memory/heap/linked_list_allocator.cpp      | 55 +++++++++++++++++-----
 arch/x86_64/src/memory/heap/memory_block.cpp       | 11 +++++
 arch/x86_64/src/memory/heap/memory_hole.cpp        | 11 -----
 4 files changed, 56 insertions(+), 23 deletions(-)
 create mode 100644 arch/x86_64/src/memory/heap/memory_block.cpp
 delete mode 100644 arch/x86_64/src/memory/heap/memory_hole.cpp

(limited to 'arch/x86_64/src/memory/heap')

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_block.cpp b/arch/x86_64/src/memory/heap/memory_block.cpp
new file mode 100644
index 0000000..b68dd6d
--- /dev/null
+++ b/arch/x86_64/src/memory/heap/memory_block.cpp
@@ -0,0 +1,11 @@
+#include "arch/memory/heap/memory_block.hpp"
+
+namespace teachos::arch::memory::heap
+{
+  memory_block::memory_block(std::size_t size, memory_block * next)
+      : size(size)
+      , next(next)
+  {
+    // Nothing to do
+  }
+}  // 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_hole.cpp
deleted file mode 100644
index 7590610..0000000
--- a/arch/x86_64/src/memory/heap/memory_hole.cpp
+++ /dev/null
@@ -1,11 +0,0 @@
-#include "arch/memory/heap/memory_hole.hpp"
-
-namespace teachos::arch::memory::heap
-{
-  memory_hole::memory_hole(std::size_t size, memory_hole * next)
-      : size(size)
-      , next(next)
-  {
-    // Nothing to do
-  }
-}  // namespace teachos::arch::memory::heap
-- 
cgit v1.2.3


From b8fd52b6b3a7f002cff58ff8da0313a684cb3ab4 Mon Sep 17 00:00:00 2001
From: Fabian Imhof <fabian.imhof@ost.ch>
Date: Sun, 1 Dec 2024 11:44:30 +0000
Subject: implement heap linked_list deallocate

---
 .../src/memory/heap/linked_list_allocator.cpp      | 64 +++++++++++++++-------
 1 file changed, 43 insertions(+), 21 deletions(-)

(limited to 'arch/x86_64/src/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 9b27f70..3330399 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -60,43 +60,65 @@ namespace teachos::arch::memory::heap
     exception_handling::assert(size < min_allocatable_size(),
                                "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes");
 
+    auto const start_address = reinterpret_cast<std::size_t>(pointer);
+    auto const end_address = start_address + size;
+
     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))
+      if (reinterpret_cast<std::size_t>(current) >= end_address)
       {
-        auto new_block = new (pointer) memory_block(size, current);
-        previous->next = new_block;
-        return;
+        break;
       }
 
-      // elseif pointer + size == current
-      // combine memory block with current
-      // combine(previous, pointer, current)
-
-      previous = current;
+      previous->next = 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 const previous_address = reinterpret_cast<std::size_t>(current_block);
-    auto const new_address = previous_address + size;
+    auto const start_address = reinterpret_cast<std::size_t>(current_block);
+    auto const end_address = start_address + size;
     current_block =
-        new (reinterpret_cast<void *>(new_address)) memory_block(current_block->size - size, current_block->next);
-    return reinterpret_cast<void *>(previous_address);
+        new (reinterpret_cast<void *>(end_address)) memory_block(current_block->size - size, current_block->next);
+    return reinterpret_cast<void *>(start_address);
   }
 
-  // auto linked_list_allocator::combine_free_memory_block(memory_block *& previous_block, memory_block *&
-  // current_block, std::size_t size) -> void *
+  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);
+    auto const end_address = start_address + size;
+
+    auto block_size = size;
+    auto new_block_address = pointer;
+    auto next_block = current_block;
+
+    // If free memory block after block to deallocate is adjacent
+    if (end_address == reinterpret_cast<std::size_t>(current_block))
+    {
+      block_size += current_block->size;
+      next_block = current_block->next;
+
+      delete current_block;
+    }
+
+    // If free memory block before block to deallocate is adjacent
+    if (start_address == (reinterpret_cast<std::size_t>(previous_block) + previous_block->size))
+    {
+      block_size += previous_block->size;
+
+      previous_block->size = block_size;
+      previous_block->next = next_block;
+      return;
+    }
+
+    new (reinterpret_cast<void *>(new_block_address)) memory_block(block_size, next_block);
+  }
 
 }  // namespace teachos::arch::memory::heap
-- 
cgit v1.2.3


From 2671b9522db44418536559524a22c95d3575569e Mon Sep 17 00:00:00 2001
From: Fabian Imhof <fabian.imhof@ost.ch>
Date: Sun, 1 Dec 2024 12:07:42 +0000
Subject: enable heap test

---
 arch/x86_64/src/memory/heap/linked_list_allocator.cpp | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

(limited to 'arch/x86_64/src/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 3330399..98a936c 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -90,13 +90,12 @@ namespace teachos::arch::memory::heap
   }
 
   auto linked_list_allocator::coalesce_free_memory_block(memory_block *& previous_block, memory_block *& current_block,
-                                                         void * pointer, std::size_t size) -> void *
+                                                         void * pointer, std::size_t size) -> void
   {
     auto const start_address = reinterpret_cast<std::size_t>(pointer);
     auto const end_address = start_address + size;
 
     auto block_size = size;
-    auto new_block_address = pointer;
     auto next_block = current_block;
 
     // If free memory block after block to deallocate is adjacent
@@ -118,7 +117,7 @@ namespace teachos::arch::memory::heap
       return;
     }
 
-    new (reinterpret_cast<void *>(new_block_address)) memory_block(block_size, next_block);
+    new (reinterpret_cast<void *>(pointer)) memory_block(block_size, next_block);
   }
 
 }  // namespace teachos::arch::memory::heap
-- 
cgit v1.2.3


From 0cf972394e99dfa69fbaf2ec9f4c718fd36bbc3e Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Sun, 1 Dec 2024 12:38:38 +0000
Subject: Add comments and fix edge case

---
 .../src/memory/heap/linked_list_allocator.cpp      | 23 +++++++++++++++++++---
 1 file changed, 20 insertions(+), 3 deletions(-)

(limited to 'arch/x86_64/src/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 98a936c..63a762e 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -68,6 +68,8 @@ namespace teachos::arch::memory::heap
 
     while (current != nullptr)
     {
+      // Current address of the free memory block now points to an address that is after our block to deallocate in heap
+      // memory space.
       if (reinterpret_cast<std::size_t>(current) >= end_address)
       {
         break;
@@ -95,10 +97,22 @@ namespace teachos::arch::memory::heap
     auto const start_address = reinterpret_cast<std::size_t>(pointer);
     auto const end_address = start_address + size;
 
+    // Inital values if there are no adjacent blocks either before or after, meaning we have to simply create a free
+    // memory block that is placed in between the previous and next block.
     auto block_size = size;
     auto next_block = current_block;
 
-    // If free memory block after block to deallocate is adjacent
+    // 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.
     if (end_address == reinterpret_cast<std::size_t>(current_block))
     {
       block_size += current_block->size;
@@ -107,7 +121,9 @@ namespace teachos::arch::memory::heap
       delete current_block;
     }
 
-    // If free memory block before block to deallocate is adjacent
+    // 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))
     {
       block_size += previous_block->size;
@@ -117,7 +133,8 @@ namespace teachos::arch::memory::heap
       return;
     }
 
-    new (reinterpret_cast<void *>(pointer)) memory_block(block_size, next_block);
+    auto const new_block = new (pointer) memory_block(block_size, next_block);
+    previous_block->next = new_block;
   }
 
 }  // namespace teachos::arch::memory::heap
-- 
cgit v1.2.3


From 9072c2a277c0da298b977cf4fb3dbebb5481abd0 Mon Sep 17 00:00:00 2001
From: Fabian Imhof <fabian.imhof@ost.ch>
Date: Sun, 1 Dec 2024 13:34:46 +0000
Subject: implement clear_memory_block_header

---
 .../src/memory/heap/linked_list_allocator.cpp      | 22 +++++++++++++++-------
 1 file changed, 15 insertions(+), 7 deletions(-)

(limited to 'arch/x86_64/src/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 63a762e..07d7e5e 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 <string.h>
+
 #include <algorithm>
 
 namespace teachos::arch::memory::heap
@@ -14,7 +16,7 @@ namespace teachos::arch::memory::heap
   {
     auto const heap_size = heap_end - heap_start;
     exception_handling::assert(
-        heap_size < min_allocatable_size(),
+        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_block(heap_size, nullptr);
@@ -22,7 +24,7 @@ namespace teachos::arch::memory::heap
 
   auto linked_list_allocator::allocate(std::size_t size) -> void *
   {
-    exception_handling::assert(size < min_allocatable_size(),
+    exception_handling::assert(size > min_allocatable_size(),
                                "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes");
 
     auto & previous = first;
@@ -34,7 +36,8 @@ namespace teachos::arch::memory::heap
       {
         return split_free_memory_block(current, size);
       }
-      else if (current->size >= size)
+
+      if (current->size >= size)
       {
         if (previous != current)
         {
@@ -42,10 +45,10 @@ namespace teachos::arch::memory::heap
         }
         else
         {
-          current = current->next;
+          first = current->next;
         }
 
-        delete current;
+        clear_memory_block_header(current);
         return static_cast<void *>(current);
       }
 
@@ -57,7 +60,7 @@ namespace teachos::arch::memory::heap
 
   auto linked_list_allocator::deallocate(void * pointer, std::size_t size) -> void
   {
-    exception_handling::assert(size < min_allocatable_size(),
+    exception_handling::assert(size > min_allocatable_size(),
                                "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes");
 
     auto const start_address = reinterpret_cast<std::size_t>(pointer);
@@ -118,7 +121,7 @@ namespace teachos::arch::memory::heap
       block_size += current_block->size;
       next_block = current_block->next;
 
-      delete current_block;
+      clear_memory_block_header(current_block);
     }
 
     // If the block we want to deallocate is behind another free block and we can therefore combine both into one.
@@ -137,4 +140,9 @@ namespace teachos::arch::memory::heap
     previous_block->next = new_block;
   }
 
+  auto linked_list_allocator::clear_memory_block_header(void * pointer) -> void
+  {
+    memset(pointer, 0, min_allocatable_size());
+  }
+
 }  // namespace teachos::arch::memory::heap
-- 
cgit v1.2.3


From a5e5eabd32872f81a7190589aa648dc0e1963888 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Mon, 2 Dec 2024 10:17:36 +0000
Subject: Fix algorithm issues with linked list allocator

---
 .../src/memory/heap/linked_list_allocator.cpp      | 64 +++++++++++-----------
 1 file changed, 31 insertions(+), 33 deletions(-)

(limited to 'arch/x86_64/src/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 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;
   }
 
-- 
cgit v1.2.3


From aa4de534ec7bf0b609aff032c4649484aa49823c Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Mon, 2 Dec 2024 11:14:43 +0000
Subject: Add check to detect double free in linked list allocator

---
 arch/x86_64/src/memory/heap/linked_list_allocator.cpp | 7 +++++++
 1 file changed, 7 insertions(+)

(limited to 'arch/x86_64/src/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 706f43e..f596f27 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -126,6 +126,13 @@ namespace teachos::arch::memory::heap
       return;
     }
 
+    // Check if the block we want to deallocate is contained in the previous block, because if it is it can only mean
+    // that the block has already been deallocated and we therefore attempted a double free.
+    exception_handling::assert(previous_block == nullptr ||
+                                   start_address >=
+                                       (reinterpret_cast<std::size_t>(previous_block) + previous_block->size),
+                               "[Linked List Allocator] Attempted double free detected");
+
     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
-- 
cgit v1.2.3


From dcd83b71c833e86c7e00e2b8f75ab6208b5d360d Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Mon, 2 Dec 2024 13:51:58 +0000
Subject: WIP thread safe linked list

---
 arch/x86_64/src/memory/heap/linked_list_allocator.cpp | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

(limited to 'arch/x86_64/src/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 f596f27..22b5757 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -28,7 +28,7 @@ namespace teachos::arch::memory::heap
                                "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes");
 
     memory_block * previous = nullptr;
-    auto current = first;
+    auto current = first.load(std::memory_order::relaxed);
 
     while (current != nullptr)
     {
@@ -52,7 +52,7 @@ namespace teachos::arch::memory::heap
     auto const end_address = start_address + size;
 
     memory_block * previous = nullptr;
-    auto current = first;
+    auto current = first.load(std::memory_order::relaxed);
 
     while (current != nullptr)
     {
@@ -81,11 +81,11 @@ namespace teachos::arch::memory::heap
     // free block (nullptr). Therefore we have to overwrite the first block instead of overwriting its next value.
     if (previous_block == nullptr)
     {
-      first = new_block;
+      first.compare_exchange_weak(previous_block, new_block, std::memory_order::relaxed);
     }
     else
     {
-      previous_block->next = new_block;
+      previous_block->next.compare_exchange_weak(current_block, new_block, std::memory_order::relaxed);
     }
     clear_memory_block_header(current_block);
     return reinterpret_cast<void *>(start_address);
-- 
cgit v1.2.3


From b4962c8c7b94fce2e67a00671de87fa96fdbb659 Mon Sep 17 00:00:00 2001
From: Fabian Imhof <fabian.imhof@ost.ch>
Date: Tue, 3 Dec 2024 08:00:26 +0000
Subject: add mutex to linked_list_allocator

---
 arch/x86_64/src/memory/heap/linked_list_allocator.cpp | 14 ++++++++++----
 1 file changed, 10 insertions(+), 4 deletions(-)

(limited to 'arch/x86_64/src/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 22b5757..01838f9 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -13,6 +13,7 @@ namespace teachos::arch::memory::heap
       : heap_start(heap_start)
       , heap_end(heap_end)
       , first(nullptr)
+      , mutex{shared::mutex{}}
   {
     auto const heap_size = heap_end - heap_start;
     exception_handling::assert(
@@ -26,9 +27,10 @@ namespace teachos::arch::memory::heap
   {
     exception_handling::assert(size > min_allocatable_size(),
                                "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes");
+    mutex.lock();
 
     memory_block * previous = nullptr;
-    auto current = first.load(std::memory_order::relaxed);
+    auto current = first;
 
     while (current != nullptr)
     {
@@ -40,6 +42,8 @@ namespace teachos::arch::memory::heap
       previous = current;
       current = current->next;
     }
+
+    mutex.unlock();
     exception_handling::panic("[Linked List Allocator] Out of memory");
   }
 
@@ -47,12 +51,13 @@ namespace teachos::arch::memory::heap
   {
     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;
 
     memory_block * previous = nullptr;
-    auto current = first.load(std::memory_order::relaxed);
+    auto current = first;
 
     while (current != nullptr)
     {
@@ -68,6 +73,7 @@ namespace teachos::arch::memory::heap
     }
 
     coalesce_free_memory_block(previous, current, pointer, size);
+    mutex.unlock();
   }
 
   auto linked_list_allocator::split_free_memory_block(memory_block * previous_block, memory_block * current_block,
@@ -81,11 +87,11 @@ namespace teachos::arch::memory::heap
     // free block (nullptr). Therefore we have to overwrite the first block instead of overwriting its next value.
     if (previous_block == nullptr)
     {
-      first.compare_exchange_weak(previous_block, new_block, std::memory_order::relaxed);
+      first = new_block;
     }
     else
     {
-      previous_block->next.compare_exchange_weak(current_block, new_block, std::memory_order::relaxed);
+      previous_block = new_block;
     }
     clear_memory_block_header(current_block);
     return reinterpret_cast<void *>(start_address);
-- 
cgit v1.2.3


From 45e36abbd404ba0c4137d0b989f3774af9ac9e3c Mon Sep 17 00:00:00 2001
From: Fabian Imhof <fabian.imhof@ost.ch>
Date: Tue, 3 Dec 2024 08:10:33 +0000
Subject: fix linked_list_allocator mutex usage

---
 arch/x86_64/src/memory/heap/linked_list_allocator.cpp | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

(limited to 'arch/x86_64/src/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 01838f9..1c5c443 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -36,14 +36,15 @@ namespace teachos::arch::memory::heap
     {
       if (current->size >= size + min_allocatable_size())
       {
-        return split_free_memory_block(previous, current, size);
+        auto memory_address = split_free_memory_block(previous, current, size);
+        mutex.unlock();
+        return memory_address;
       }
 
       previous = current;
       current = current->next;
     }
 
-    mutex.unlock();
     exception_handling::panic("[Linked List Allocator] Out of memory");
   }
 
-- 
cgit v1.2.3


From e6da0a1b12a3e777bd54e4b22b6a873a4c5fe195 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Tue, 3 Dec 2024 08:19:24 +0000
Subject: Add allocate case where size fits exactly

---
 .../src/memory/heap/linked_list_allocator.cpp      | 26 ++++++++++++++++++++--
 1 file changed, 24 insertions(+), 2 deletions(-)

(limited to 'arch/x86_64/src/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);
-- 
cgit v1.2.3


From 23526b8d10cf41ad5598928bf2bf3264539d497f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Tue, 3 Dec 2024 08:41:59 +0000
Subject: Add missing comments

---
 .../src/memory/heap/linked_list_allocator.cpp      | 30 +++++++++-------------
 1 file changed, 12 insertions(+), 18 deletions(-)

(limited to 'arch/x86_64/src/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 d922dc8..6600c6e 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -36,7 +36,7 @@ namespace teachos::arch::memory::heap
     {
       if (current->size == size)
       {
-        return remove_free_memory_block(previous, current, size);
+        return remove_free_memory_block(previous, current);
       }
       else if (current->size >= size + min_allocatable_size())
       {
@@ -81,31 +81,25 @@ 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 linked_list_allocator::remove_free_memory_block(memory_block * previous_block,
+                                                       memory_block * current_block) -> 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);
+    return replace_free_memory_block(previous_block, current_block, current_block->next);
   }
 
   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;
+    auto const end_address = reinterpret_cast<std::size_t>(current_block) + size;
     auto const new_block =
         new (reinterpret_cast<void *>(end_address)) memory_block(current_block->size - size, current_block->next);
+    return replace_free_memory_block(previous_block, current_block, new_block);
+  }
+
+  auto linked_list_allocator::replace_free_memory_block(memory_block * previous_block, memory_block * current_block,
+                                                        memory_block * new_block) -> 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)
-- 
cgit v1.2.3


From 0a531eaa43cdd6ab15e60da2f4b203505265f5c6 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Tue, 3 Dec 2024 08:47:13 +0000
Subject: Fix missing mutex unlock

---
 arch/x86_64/src/memory/heap/linked_list_allocator.cpp | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

(limited to 'arch/x86_64/src/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 6600c6e..d0bf8e6 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -36,11 +36,13 @@ namespace teachos::arch::memory::heap
     {
       if (current->size == size)
       {
-        return remove_free_memory_block(previous, current);
+        auto const memory_address = remove_free_memory_block(previous, current);
+        mutex.unlock();
+        return memory_address;
       }
       else if (current->size >= size + min_allocatable_size())
       {
-        auto memory_address = split_free_memory_block(previous, current, size);
+        auto const memory_address = split_free_memory_block(previous, current, size);
         mutex.unlock();
         return memory_address;
       }
-- 
cgit v1.2.3


From 05fe50cefb12a7333a320a3d101dccdd13b8034a Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= <matteo.gmuer1@ost.ch>
Date: Tue, 3 Dec 2024 09:13:53 +0000
Subject: Clear old memory in contructor

---
 arch/x86_64/src/memory/heap/linked_list_allocator.cpp | 14 ++------------
 arch/x86_64/src/memory/heap/memory_block.cpp          | 10 +++++++---
 2 files changed, 9 insertions(+), 15 deletions(-)

(limited to 'arch/x86_64/src/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 d0bf8e6..e5bae21 100644
--- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
+++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp
@@ -3,10 +3,6 @@
 #include "arch/exception_handling/assert.hpp"
 #include "arch/exception_handling/panic.hpp"
 
-#include <string.h>
-
-#include <algorithm>
-
 namespace teachos::arch::memory::heap
 {
   linked_list_allocator::linked_list_allocator(std::size_t heap_start, std::size_t heap_end)
@@ -112,7 +108,7 @@ namespace teachos::arch::memory::heap
     {
       previous_block->next = new_block;
     }
-    clear_memory_block_header(current_block);
+    current_block->~memory_block();
     return reinterpret_cast<void *>(start_address);
   }
 
@@ -134,8 +130,7 @@ namespace teachos::arch::memory::heap
     {
       block_size += current_block->size;
       next_block = current_block->next;
-
-      clear_memory_block_header(current_block);
+      current_block->~memory_block();
     }
 
     // If the block we want to deallocate is behind another free block and we can therefore combine both into one.
@@ -170,9 +165,4 @@ namespace teachos::arch::memory::heap
     previous_block->next = new_block;
   }
 
-  auto linked_list_allocator::clear_memory_block_header(void * pointer) -> void
-  {
-    memset(pointer, 0, min_allocatable_size());
-  }
-
 }  // namespace teachos::arch::memory::heap
diff --git a/arch/x86_64/src/memory/heap/memory_block.cpp b/arch/x86_64/src/memory/heap/memory_block.cpp
index b68dd6d..446cd96 100644
--- a/arch/x86_64/src/memory/heap/memory_block.cpp
+++ b/arch/x86_64/src/memory/heap/memory_block.cpp
@@ -1,11 +1,15 @@
 #include "arch/memory/heap/memory_block.hpp"
 
+#include <string.h>
+
 namespace teachos::arch::memory::heap
 {
   memory_block::memory_block(std::size_t size, memory_block * next)
-      : size(size)
-      , next(next)
   {
-    // Nothing to do
+    memset(static_cast<void *>(this), 0, size);
+    this->size = size;
+    this->next = next;
   }
+
+  memory_block::~memory_block() { memset(static_cast<void *>(this), 0, sizeof(memory_block)); }
 }  // namespace teachos::arch::memory::heap
-- 
cgit v1.2.3