Merge branch 'feat_memory_manager' into 'develop_sa'

Finish inital draft of Memory Manager

See merge request teachos/kernel!3

63 files changed, 3747 insertions, 120 deletions

diff --git a/arch/x86_64/CMakeLists.txt b/arch/x86_64/CMakeLists.txt
index 6ff1332..c5624d8 100644
--- a/arch/x86_64/CMakeLists.txt
+++ b/arch/x86_64/CMakeLists.txt
@@ -37,6 +37,43 @@ target_sources("_video" PRIVATE
 )
 
 #[============================================================================[
+# The Memory Library
+#]============================================================================]
+
+target_sources("_memory" PRIVATE
+  "src/memory/main.cpp"
+  "src/memory/multiboot/elf_symbols_section.cpp"
+  "src/memory/multiboot/reader.cpp"
+  "src/memory/allocator/area_frame_allocator.cpp"
+  "src/memory/allocator/tiny_frame_allocator.cpp"
+  "src/memory/allocator/physical_frame.cpp"
+  "src/memory/paging/page_entry.cpp"
+  "src/memory/paging/page_table.cpp"
+  "src/memory/paging/temporary_page.cpp"
+  "src/memory/paging/virtual_page.cpp"
+  "src/memory/paging/active_page_table.cpp"
+  "src/memory/paging/inactive_page_table.cpp"
+  "src/memory/cpu/tlb.cpp"
+  "src/memory/cpu/control_register.cpp"
+  "src/memory/cpu/msr.cpp"
+  "src/memory/heap/bump_allocator.cpp"
+  "src/memory/heap/memory_block.cpp"
+  "src/memory/heap/linked_list_allocator.cpp"
+  "src/shared/mutex.cpp"
+)
+
+#[============================================================================[
+# The Exception handling Library
+#]============================================================================]
+
+target_sources("_exception" PRIVATE
+  "src/exception_handling/assert.cpp"
+  "src/exception_handling/abort.cpp"
+  "src/exception_handling/panic.cpp"
+  "src/exception_handling/pure_virtual.cpp"
+)
+
+#[============================================================================[
 # The Bootable ISO Image
 #]============================================================================]
 
diff --git a/arch/x86_64/include/arch/boot/pointers.hpp b/arch/x86_64/include/arch/boot/pointers.hpp
index dcd14fe..fe9c657 100644
--- a/arch/x86_64/include/arch/boot/pointers.hpp
+++ b/arch/x86_64/include/arch/boot/pointers.hpp
@@ -5,7 +5,11 @@
 
 namespace teachos::arch::boot
 {
-  extern "C" std::byte const multiboot_information_pointer;
+  /**
+   * @brief Address pointing to the start of the multiboot information structure.
+   */
+  extern "C" size_t const multiboot_information_pointer;
+
 }  // namespace teachos::arch::boot
 
-#endif
\ No newline at end of file
+#endif  // TEACHOS_ARCH_X86_64_BOOT_POINTERS_HPP
diff --git a/arch/x86_64/include/arch/exception_handling/assert.hpp b/arch/x86_64/include/arch/exception_handling/assert.hpp
new file mode 100644
index 0000000..1286768
--- /dev/null
+++ b/arch/x86_64/include/arch/exception_handling/assert.hpp
@@ -0,0 +1,17 @@
+#ifndef TEACHOS_ARCH_X86_64_EXCEPTION_HANDLING_ASSERT_HPP
+#define TEACHOS_ARCH_X86_64_EXCEPTION_HANDLING_ASSERT_HPP
+
+namespace teachos::arch::exception_handling
+{
+  /**
+   * @brief Assert a condition to be true, if not do not continue
+   * execution of the code and print the given message to screen.
+   *
+   * @param condition Condition we want to be true or else halt execution.
+   * @param message Message that should be printed before halting the execution if the condition is not met.
+   */
+  auto assert(bool condition, char const * message) -> void;
+
+}  // namespace teachos::arch::exception_handling
+
+#endif  // TEACHOS_ARCH_X86_64_EXCEPTION_HANDLING_ASSERT_HPP
diff --git a/arch/x86_64/include/arch/exception_handling/panic.hpp b/arch/x86_64/include/arch/exception_handling/panic.hpp
new file mode 100644
index 0000000..6a2404c
--- /dev/null
+++ b/arch/x86_64/include/arch/exception_handling/panic.hpp
@@ -0,0 +1,23 @@
+#ifndef TEACHOS_ARCH_X86_64_EXCEPTION_HANDLING_PANIC_HPP
+#define TEACHOS_ARCH_X86_64_EXCEPTION_HANDLING_PANIC_HPP
+
+namespace teachos::arch::exception_handling
+{
+  /**
+   * @brief Print the given kernel panic message and then halt the system.
+   *
+   * @param reason Reason to print before halting the system.
+   */
+  [[noreturn]] auto panic(char const * reason) -> void;
+
+  /**
+   * @brief Print the given kernel panic message started by a given prefix and then halt the system.
+   *
+   * @param prefix Prefix to print before printing the reason.
+   * @param reason Reason to print before halting the system.
+   */
+  [[noreturn]] auto panic(char const * prefix, char const * reason) -> void;
+
+}  // namespace teachos::arch::exception_handling
+
+#endif  // TEACHOS_ARCH_X86_64_EXCEPTION_HANDLING_PANIC_HPP
diff --git a/arch/x86_64/include/arch/io/port_io.hpp b/arch/x86_64/include/arch/io/port_io.hpp
index 5b61f90..ba41660 100644
--- a/arch/x86_64/include/arch/io/port_io.hpp
+++ b/arch/x86_64/include/arch/io/port_io.hpp
@@ -8,7 +8,6 @@
 
 namespace teachos::arch::io
 {
-
   /**
    * @brief An I/O port of a given size at a given address.
    *
@@ -131,4 +130,4 @@ namespace teachos::arch::io
 
 }  // namespace teachos::arch::io
 
-#endif
\ No newline at end of file
+#endif  // TEACHOS_ARCH_X86_64_IO_PORT_IO_HPP
diff --git a/arch/x86_64/include/arch/kernel/halt.hpp b/arch/x86_64/include/arch/kernel/halt.hpp
new file mode 100644
index 0000000..377acc0
--- /dev/null
+++ b/arch/x86_64/include/arch/kernel/halt.hpp
@@ -0,0 +1,13 @@
+#ifndef TEACHOS_ARCH_X86_64_KERNEL_HALT_HPP
+#define TEACHOS_ARCH_X86_64_KERNEL_HALT_HPP
+
+namespace teachos::arch::kernel
+{
+  /**
+   * @brief Halts the kernel execution, meaning any code after a call to this will not run anymore.
+   */
+  extern "C" [[noreturn]] auto halt() -> void;
+
+}  // namespace teachos::arch::kernel
+
+#endif  // TEACHOS_ARCH_X86_64_KERNEL_HALT_HPP
diff --git a/arch/x86_64/include/arch/kernel/main.hpp b/arch/x86_64/include/arch/kernel/main.hpp
index 6961594..a13e5f4 100644
--- a/arch/x86_64/include/arch/kernel/main.hpp
+++ b/arch/x86_64/include/arch/kernel/main.hpp
@@ -1,11 +1,13 @@
 #ifndef TEACHOS_ARCH_X86_64_KERNEL_MAIN_HPP
 #define TEACHOS_ARCH_X86_64_KERNEL_MAIN_HPP
 
-#include <cstddef>
-
 namespace teachos::arch::kernel
 {
+  /**
+   * @brief Initalizes the kernel system.
+   */
   auto main() -> void;
-}
 
-#endif
\ No newline at end of file
+}  // namespace teachos::arch::kernel
+
+#endif  // TEACHOS_ARCH_X86_64_KERNEL_MAIN_HPP
diff --git a/arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp b/arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp
new file mode 100644
index 0000000..b8370db
--- /dev/null
+++ b/arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp
@@ -0,0 +1,67 @@
+#ifndef TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_AREA_FRAME_ALLOCATOR_HPP
+#define TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_AREA_FRAME_ALLOCATOR_HPP
+
+#include "arch/memory/allocator/physical_frame.hpp"
+#include "arch/memory/multiboot/reader.hpp"
+
+#include <optional>
+
+namespace teachos::arch::memory::allocator
+{
+  /**
+   * @brief Allocates memory linearly using memory areas read from the multiboot2 information pointer and leaks any
+   * deallocated frames.
+   */
+  struct area_frame_allocator
+  {
+    /**
+     * @brief Constructor
+     *
+     * @param mem_info Structure containg all relevant information to map and allocate memory
+     */
+    area_frame_allocator(multiboot::memory_information const & mem_info);
+
+    /**
+     * @brief Allocate memory by finding and returning a free physical frame.
+     *
+     * @note The physical_frame allocation executes multiple checks before returning
+     * the physical_frame that is available to allocate. It must at least
+     * do the following:
+     * - check if the next_free_frame is within the current_area
+     * - check if the next_free_frame is actually free
+     * - update the next_free_frame after finding a free physical_frame
+     *
+     * @return next free physical frame or nullopt if none was found.
+     */
+    auto allocate_frame() -> std::optional<physical_frame>;
+
+    /**
+     * @brief Deallocates a previously allocated physical frame.
+     *
+     * @note Simply does nothing, because the simply area frame
+     * allocator implementation does not keep track of free or used frames and can therefore not deallocate, because it
+     * does not know which frames have been alocated in the first place.
+     *
+     * @param physical_frame Previously allocated physical_frame that should be deallocated.
+     */
+    auto deallocate_frame(physical_frame const & physical_frame) -> void;
+
+  private:
+    /**
+     * @brief Find the next memory area and write it into current_area.
+     */
+    auto choose_next_area() -> void;
+
+    physical_frame next_free_frame;                      ///< The physical_frame after the last allocated one.
+    std::optional<multiboot::memory_area> current_area;  ///< The current memory area.
+    multiboot::memory_area_container const
+        memory_areas;                      ///< All memory areas in custom container allows to use std::ranges
+    physical_frame const kernel_start;     ///< The start address of the kernel code in memory.
+    physical_frame const kernel_end;       ///< The end address of the kernel code in memory.
+    physical_frame const multiboot_start;  ///< The start address of the multiboot code in memory.
+    physical_frame const multiboot_end;    ///< The end address of the multiboot code in memory.
+  };
+
+}  // namespace teachos::arch::memory::allocator
+
+#endif  // TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_AREA_FRAME_ALLOCATOR_HPP
diff --git a/arch/x86_64/include/arch/memory/allocator/concept.hpp b/arch/x86_64/include/arch/memory/allocator/concept.hpp
new file mode 100644
index 0000000..2d3f4ae
--- /dev/null
+++ b/arch/x86_64/include/arch/memory/allocator/concept.hpp
@@ -0,0 +1,21 @@
+#ifndef TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_CONCEPT_HPP
+#define TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_CONCEPT_HPP
+
+#include "arch/memory/allocator/physical_frame.hpp"
+
+#include <optional>
+
+namespace teachos::arch::memory::allocator
+{
+  /**
+   * @brief Frame allocator concept required for allocating and deallocating physical frames in memory.
+   */
+  template<typename T>
+  concept FrameAllocator = requires(T t, physical_frame const & a) {
+    { t.allocate_frame() } -> std::same_as<std::optional<physical_frame>>;
+    { t.deallocate_frame(a) } -> std::same_as<void>;
+  };
+
+}  // namespace teachos::arch::memory::allocator
+
+#endif  // TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_CONCEPT_HPP
diff --git a/arch/x86_64/include/arch/memory/allocator/physical_frame.hpp b/arch/x86_64/include/arch/memory/allocator/physical_frame.hpp
new file mode 100644
index 0000000..7f04042
--- /dev/null
+++ b/arch/x86_64/include/arch/memory/allocator/physical_frame.hpp
@@ -0,0 +1,86 @@
+#ifndef TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_PHYSICAL_FRAME_HPP
+#define TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_PHYSICAL_FRAME_HPP
+
+#include "arch/shared/container.hpp"
+#include "arch/shared/forward_value_iterator.hpp"
+
+#include <compare>
+#include <cstdint>
+#include <iterator>
+
+namespace teachos::arch::memory::allocator
+{
+  typedef std::size_t physical_address;
+
+  std::size_t constexpr PAGE_FRAME_SIZE = 4096U;  ///< Default page size of x86_84 is always 4KiB.
+
+  /**
+   * @brief Specific physical frame containing helper functions to determine if a specific address is in that
+   * physical frame or not.
+   */
+  struct physical_frame
+  {
+    /**
+     * @brief Defaulted constructor.
+     */
+    constexpr physical_frame() = default;
+
+    /**
+     * @brief Constructor.
+     *
+     * @param frame_number Index number that should be assigned to this physical frame.
+     */
+    explicit constexpr physical_frame(std::size_t frame_number)
+        : frame_number(frame_number)
+    {
+      // Nothing to do
+    }
+
+    /**
+     * @brief Returns the physical frame the given address is contained in.
+     *
+     * @param address Physical address we want to get the corresponding physical frame for.
+     * @return Frame the given address is contained in.
+     */
+    auto static containing_address(physical_address address) -> physical_frame;
+
+    /**
+     * @brief Get the start address of this physical frame.
+     *
+     * @return Start address of the physical frame.
+     */
+    auto start_address() const -> physical_address;
+
+    /**
+     * @brief Post increment operator. Returns a copy of the value.
+     *
+     * @return Copy of the incremented underlying frame number.
+     */
+    auto operator++(int) -> physical_frame;
+
+    /**
+     * @brief Pre increment operator. Returns a reference to the changed value.
+     *
+     * @return Reference to the incremented underlying frame number.
+     */
+    auto operator++() -> physical_frame &;
+
+    /**
+     * @brief Defaulted equals operator.
+     */
+    auto operator==(physical_frame const & other) const -> bool = default;
+
+    /**
+     * @brief Defaulted three-way comparsion operator.
+     */
+    auto operator<=>(physical_frame const & other) const -> std::partial_ordering = default;
+
+    std::size_t frame_number =
+        {};  ///< Index number of the current physical frame, used to distinguish it from other frames.
+  };
+
+  typedef shared::container<shared::forward_value_iterator<physical_frame>> frame_container;
+
+}  // namespace teachos::arch::memory::allocator
+
+#endif  // TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_PHYSICAL_FRAME_HPP
diff --git a/arch/x86_64/include/arch/memory/allocator/tiny_frame_allocator.hpp b/arch/x86_64/include/arch/memory/allocator/tiny_frame_allocator.hpp
new file mode 100644
index 0000000..1ceb74d
--- /dev/null
+++ b/arch/x86_64/include/arch/memory/allocator/tiny_frame_allocator.hpp
@@ -0,0 +1,74 @@
+#ifndef TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_TINY_FRAME_ALLOCATOR_HPP
+#define TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_TINY_FRAME_ALLOCATOR_HPP
+
+#include "arch/memory/allocator/concept.hpp"
+#include "arch/memory/allocator/physical_frame.hpp"
+
+#include <array>
+
+namespace teachos::arch::memory::allocator
+{
+  namespace
+  {
+    uint8_t constexpr TINY_ALLOCATOR_FRAMES_COUNT = 3U;
+  }
+
+  /**
+   * @brief Allocates memory using memory areas read from the multiboot2 information pointer. Does not allocate its own
+   * frames, but uses the necessary three frames provided by another allocator to map one virtual level 1 page entry and
+   * the necessary upper layers.
+   */
+  struct tiny_frame_allocator
+  {
+    /**
+     * @brief Constructor.
+     *
+     * @tparam T Contract the allocator that should be used to actually allocate and deallocate, the underlying three
+     * frames has to follow.
+     *
+     * @param allocator Reference to an allocator following the FrameAllocator concept, which is used to allocate
+     * entries when the underlying frames are created.
+     */
+    template<allocator::FrameAllocator T>
+    tiny_frame_allocator(T & allocator)
+        : frames{}
+    {
+      // Has to be done this way, because constructing the constructor with the data from allocator.allocate_frames(),
+      // does not work because it would set the value correctly but because we pass it as an std::optional it would not
+      // set the engaged flag. Meaning the has_value() method would still return false.
+      for (auto & frame : frames)
+      {
+        auto allocated = allocator.allocate_frame();
+        if (allocated.has_value())
+        {
+          frame.emplace(allocated.value());
+        }
+      }
+    }
+
+    /**
+     * @brief Allocate memory by finding and returning one of the three free physical frames.
+     *
+     * @return First free physical frames of the three frames held by this allocator or nullopt if we used up all three
+     * frames already.
+     */
+    auto allocate_frame() -> std::optional<physical_frame>;
+
+    /**
+     * @brief Deallocates one of the three previously allocated physical frames.
+     *
+     * @note If more than the three frames are deallocated the method will halt execution, because it can only hold 3
+     * frames.
+     *
+     * @param physical_frame Previously allocated physical_frame that should be deallocated.
+     */
+    auto deallocate_frame(physical_frame const & physical_frame) -> void;
+
+  private:
+    std::array<std::optional<physical_frame>, TINY_ALLOCATOR_FRAMES_COUNT> frames =
+        {};  ///< Container that holds the frames allocated by another allocator.
+  };
+
+}  // namespace teachos::arch::memory::allocator
+
+#endif  // TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_TINY_FRAME_ALLOCATOR_HPP
diff --git a/arch/x86_64/include/arch/memory/cpu/control_register.hpp b/arch/x86_64/include/arch/memory/cpu/control_register.hpp
new file mode 100644
index 0000000..e11813d
--- /dev/null
+++ b/arch/x86_64/include/arch/memory/cpu/control_register.hpp
@@ -0,0 +1,71 @@
+#ifndef TEACHOS_ARCH_X86_64_MEMORY_CPU_CR3_HPP
+#define TEACHOS_ARCH_X86_64_MEMORY_CPU_CR3_HPP
+
+#include <cstdint>
+
+namespace teachos::arch::memory::cpu
+{
+  /**
+   * @brief Control registers that can be read and written