Seperate allocation and paging code into multiple files as well

2 files changed, 119 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..9c344d8
--- /dev/null
+++ b/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp
@@ -0,0 +1,97 @@
+#include "arch/memory/allocator/area_frame_allocator.hpp"
+
+#include "arch/exception_handling/assert.hpp"
+
+namespace teachos::arch::memory::allocator
+{
+  area_frame_allocator::area_frame_allocator(multiboot::memory_information mem_info)
+      : next_free_frame(0)
+      , current_area(std::nullopt)
+      , area_begin(mem_info.memory_areas)
+      , area_end(mem_info.memory_areas + mem_info.area_count)
+      , 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;
+
+    for (multiboot::memory_area_iterator it = begin(); it != end(); ++it)
+    {
+      multiboot::memory_area & area = *it;
+
+      std::size_t address = area.base_address + area.area_length - 1;
+      if (physical_frame::containing_address(address) >= next_free_frame)
+      {
+        // The `next_free_frame` address is smaller than the last address of the current area
+        if (!current_area || area.base_address < current_area->base_address)
+        {
+          current_area = area;
+        }
+      }
+    }
+
+    if (current_area)
+    {
+      // Update the `next_free_frame` according to the new memory area
+      physical_frame start_frame = physical_frame::containing_address(current_area->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)
+    {
+      physical_frame physical_frame{next_free_frame.frame_number};
+
+      struct physical_frame current_area_last_frame = {
+          physical_frame::containing_address(current_area->base_address + current_area->area_length - 1)};
+
+      if (next_free_frame > current_area_last_frame)
+      {
+        // All frames of current area are used, switch to next area
+        choose_next_area();
+      }
+      else if (physical_frame >= multiboot_start && physical_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
+      {
+        // Frame is unused, increment `next_free_frame` and return it
+        next_free_frame.frame_number += 1;
+        return physical_frame;
+      }
+
+      // `physical_frame` was not valid, try it again with the updated `next_free_frame`
+      return allocate_frame();
+    }
+
+    // no free frames left
+    return std::nullopt;
+  }
+
+  auto area_frame_allocator::deallocate_frame(physical_frame physical_frame) -> void
+  {
+    arch::exception_handling::assert(false && physical_frame.frame_number == 0,
+                                     "[deallocate_frame] Not implemented Exception");
+  }
+
+  auto area_frame_allocator::begin() -> multiboot::memory_area_iterator { return area_begin; }
+
+  auto area_frame_allocator::end() -> multiboot::memory_area_iterator { return area_end; }
+}  // 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..03ec193
--- /dev/null
+++ b/arch/x86_64/src/memory/allocator/physical_frame.cpp
@@ -0,0 +1,22 @@
+#include "arch/memory/allocator/physical_frame.hpp"
+
+namespace teachos::arch::memory::allocator
+{
+  namespace
+  {
+    constexpr std::size_t PAGE_FRAME_SIZE = 4096U;  ///< Default page size of x86_84 is always 4KiB.
+  }
+
+  physical_frame::physical_frame(std::size_t frame_number)
+      : frame_number(frame_number)
+  {
+    // Nothing to do
+  }
+
+  auto physical_frame::containing_address(std::size_t address) -> physical_frame
+  {
+    return physical_frame{address / PAGE_FRAME_SIZE};
+  }
+
+  auto physical_frame::start_address() const -> uint64_t { return frame_number * PAGE_FRAME_SIZE; }
+}  // namespace teachos::arch::memory::allocator