Merge branch 'feat_memory_manager' into 'develop_sa'

Finish inital draft of Memory Manager

See merge request teachos/kernel!3

3 files changed, 143 insertions, 0 deletions

diff --git a/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp b/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp
new file mode 100644
index 0000000..cb4fefa
--- /dev/null
+++ b/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp
@@ -0,0 +1,85 @@
+#include "arch/memory/allocator/area_frame_allocator.hpp"
+
+#include "arch/exception_handling/assert.hpp"
+
+#include <algorithm>
+#include <array>
+#include <ranges>
+
+namespace teachos::arch::memory::allocator
+{
+  area_frame_allocator::area_frame_allocator(multiboot::memory_information const & mem_info)
+      : next_free_frame(0U)
+      , current_area(std::nullopt)
+      , memory_areas(mem_info.areas)
+      , kernel_start(physical_frame::containing_address(mem_info.kernel_start))
+      , kernel_end(physical_frame::containing_address(mem_info.kernel_end))
+      , multiboot_start(physical_frame::containing_address(mem_info.multiboot_start))
+      , multiboot_end(physical_frame::containing_address(mem_info.multiboot_end))
+  {
+    choose_next_area();
+  }
+
+  auto area_frame_allocator::choose_next_area() -> void
+  {
+    current_area = std::nullopt;
+    auto next_area_with_free_frames = memory_areas | std::views::filter([this](auto const & area) {
+                                        auto address = area.base_address + area.area_length - 1;
+                                        return physical_frame::containing_address(address) >= next_free_frame;
+                                      });
+
+    auto const lowest_area_with_free_frames = std::ranges::min_element(
+        next_area_with_free_frames, [](auto const & a, auto const & b) { return a.base_address < b.base_address; });
+
+    if (lowest_area_with_free_frames != next_area_with_free_frames.end())
+    {
+      current_area = *lowest_area_with_free_frames;
+      // Update the `next_free_frame` according to the new memory area
+      auto const start_frame = physical_frame::containing_address(current_area.value().base_address);
+      if (next_free_frame < start_frame)
+      {
+        next_free_frame = start_frame;
+      }
+    }
+  }
+
+  auto area_frame_allocator::allocate_frame() -> std::optional<physical_frame>
+  {
+    // Only try to allocate memory if current_area is not null, because
+    // the current_area is null if there is no more available memory.
+    if (!current_area.has_value())
+    {
+      return std::nullopt;
+    }
+
+    auto const address = current_area.value().base_address + current_area.value().area_length - 1;
+    physical_frame current_area_last_frame = physical_frame::containing_address(address);
+
+    if (next_free_frame > current_area_last_frame)
+    {
+      // All frames of current area are used, switch to next area.
+      choose_next_area();
+    }
+    else if (next_free_frame >= kernel_start && next_free_frame <= kernel_end)
+    {
+      // `physical_frame` is used by the kernel or multiboot information structure.
+      next_free_frame = allocator::physical_frame{kernel_end.frame_number + 1};
+    }
+    else if (next_free_frame >= multiboot_start && next_free_frame <= multiboot_end)
+    {
+      // `physical_frame` is used by the kernel or multiboot information structure.
+      next_free_frame = allocator::physical_frame{multiboot_end.frame_number + 1};
+    }
+    else
+    {
+      // Frame is unused, increment `next_free_frame` and return it.
+      next_free_frame.frame_number += 1;
+      return next_free_frame;
+    }
+
+    // `physical_frame` was not valid, try it again with the updated `next_free_frame`.
+    return allocate_frame();
+  }
+
+  auto area_frame_allocator::deallocate_frame(physical_frame const & physical_frame) -> void { (void)physical_frame; }
+}  // namespace teachos::arch::memory::allocator
diff --git a/arch/x86_64/src/memory/allocator/physical_frame.cpp b/arch/x86_64/src/memory/allocator/physical_frame.cpp
new file mode 100644
index 0000000..ec387a1
--- /dev/null
+++ b/arch/x86_64/src/memory/allocator/physical_frame.cpp
@@ -0,0 +1,24 @@
+#include "arch/memory/allocator/physical_frame.hpp"
+
+namespace teachos::arch::memory::allocator
+{
+  auto physical_frame::containing_address(physical_address address) -> physical_frame
+  {
+    return physical_frame{address / PAGE_FRAME_SIZE};
+  }
+
+  auto physical_frame::start_address() const -> physical_address { return frame_number * PAGE_FRAME_SIZE; }
+
+  auto physical_frame::operator++(int) -> physical_frame
+  {
+    physical_frame const old_value = *this;
+    ++frame_number;
+    return old_value;
+  }
+
+  auto physical_frame::operator++() -> physical_frame &
+  {
+    ++frame_number;
+    return *this;
+  }
+}  // namespace teachos::arch::memory::allocator
diff --git a/arch/x86_64/src/memory/allocator/tiny_frame_allocator.cpp b/arch/x86_64/src/memory/allocator/tiny_frame_allocator.cpp
new file mode 100644
index 0000000..3cdf9c7
--- /dev/null
+++ b/arch/x86_64/src/memory/allocator/tiny_frame_allocator.cpp
@@ -0,0 +1,34 @@
+#include "arch/memory/allocator/tiny_frame_allocator.hpp"
+
+#include "arch/exception_handling/panic.hpp"
+
+namespace teachos::arch::memory::allocator
+{
+  auto tiny_frame_allocator::allocate_frame() -> std::optional<physical_frame>
+  {
+    for (auto & frame_option : frames)
+    {
+      if (frame_option.has_value())
+      {
+        auto value = frame_option;
+        frame_option.reset();
+        return value;
+      }
+    }
+    return std::nullopt;
+  }
+
+  auto tiny_frame_allocator::deallocate_frame(physical_frame const & physical_frame) -> void
+  {
+    for (auto & frame_option : frames)
+    {
+      if (!frame_option.has_value())
+      {
+        frame_option.emplace(physical_frame);
+        return;
+      }
+    }
+    exception_handling::panic(
+        "[Tiny Frame Allocator] Attempted to deallocate more than the 3 frames, that can be held");
+  }
+}  // namespace teachos::arch::memory::allocator