Create base of linked list allocator

5 files changed, 94 insertions, 0 deletions

diff --git a/arch/x86_64/CMakeLists.txt b/arch/x86_64/CMakeLists.txt
index b758bf0..4ba6590 100644
--- a/arch/x86_64/CMakeLists.txt
+++ b/arch/x86_64/CMakeLists.txt
@@ -57,6 +57,8 @@ 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/linked_list_allocator.cpp"
 )
 
 #[============================================================================[
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
new file mode 100644
index 0000000..a742018
--- /dev/null
+++ b/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp
@@ -0,0 +1,37 @@
+#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 <cstdint>
+
+namespace teachos::arch::memory::heap
+{
+  /**
+   * @brief Sorted by address list of memory holes (free memory). Uses free holes itself to save the information,
+   * containing the size and pointer to the next hole. Resulting in a single linked list.
+   */
+  struct linked_list_allocator
+  {
+    /**
+     * @brief Constructor.
+     *
+     * @param heap_start Start of the allocatable heap area
+     * @param heap_end End of the allocatable heap area (Start + Size)
+     */
+    linked_list_allocator(std::size_t heap_start, std::size_t heap_end);
+
+    /**
+     * @brief Returns the smallest allocatable block of heap memory.
+     *
+     * @return Smallest allocatable block of heap memory.
+     */
+    auto constexpr min_allocatable_size() -> std::size_t { return sizeof(memory_hole); }
+
+    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
+  };
+}  // namespace teachos::arch::memory::heap
+
+#endif  // TEACHOS_ARCH_X86_64_MEMORY_HEAP_LINKED_LIST_ALLOCATOR_HPP
diff --git a/arch/x86_64/include/arch/memory/heap/memory_hole.hpp b/arch/x86_64/include/arch/memory/heap/memory_hole.hpp
new file mode 100644
index 0000000..e017599
--- /dev/null
+++ b/arch/x86_64/include/arch/memory/heap/memory_hole.hpp
@@ -0,0 +1,28 @@
+#ifndef TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_HOLE_HPP
+#define TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_HOLE_HPP
+
+#include <cstdint>
+
+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
+  {
+    /**
+     * @brief Constructor,
+     *
+     * @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);
+
+    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.
+  };
+}  // namespace teachos::arch::memory::heap
+
+#endif  // TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_HOLE_HPP
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