Create base of linked list allocator

2 files changed, 65 insertions, 0 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
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