Add stack frame allocator. Fix stl vector bug and create stl stack implementation

3 files changed, 124 insertions, 3 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
index cb4fefa..a5a1b49 100644
--- a/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp
+++ b/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp
@@ -9,7 +9,7 @@
 namespace teachos::arch::memory::allocator
 {
   area_frame_allocator::area_frame_allocator(multiboot::memory_information const & mem_info)
-      : next_free_frame(0U)
+      : next_free_frame()
       , current_area(std::nullopt)
       , memory_areas(mem_info.areas)
       , kernel_start(physical_frame::containing_address(mem_info.kernel_start))
diff --git a/arch/x86_64/src/memory/allocator/stack_frame_allocator.cpp b/arch/x86_64/src/memory/allocator/stack_frame_allocator.cpp
new file mode 100644
index 0000000..0fa277a
--- /dev/null
+++ b/arch/x86_64/src/memory/allocator/stack_frame_allocator.cpp
@@ -0,0 +1,105 @@
+#include "arch/memory/allocator/stack_frame_allocator.hpp"
+
+#include "arch/exception_handling/assert.hpp"
+
+#include <algorithm>
+#include <array>
+#include <ranges>
+
+namespace teachos::arch::memory::allocator
+{
+  stack_frame_allocator::stack_frame_allocator(multiboot::memory_information const & mem_info)
+      : free_frames()
+      , next_free_frame()
+      , 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))
+  {
+    load_free_physical_frames();
+  }
+
+  auto stack_frame_allocator::load_free_physical_frames() -> void
+  {
+    choose_next_area();
+    if (!current_area.has_value())
+    {
+      return;
+    }
+
+    auto const address = current_area.value().base_address + current_area.value().area_length - 1;
+    physical_frame const current_area_last_frame = physical_frame::containing_address(address);
+
+    // Only try to allocate memory if current_area is not null, because
+    // the current_area is null if there is no more available memory.
+    while (next_free_frame <= current_area_last_frame)
+    {
+      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;
+        // TODO: Fix using heap like structure to initalize paging allocator used by heap does not work
+        // free_frames.push(next_free_frame);
+        static uint32_t count = 0U;
+        count++;
+      }
+    }
+  }
+
+  auto stack_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 stack_frame_allocator::allocate_frame() -> std::optional<physical_frame>
+  {
+    // If the underlying stack is empty that are no free frames left to allocate.
+    if (free_frames.empty())
+    {
+      load_free_physical_frames();
+      if (free_frames.empty())
+      {
+        return std::nullopt;
+      }
+    }
+
+    decltype(auto) top = free_frames.top();
+    free_frames.pop();
+    return top;
+  }
+
+  auto stack_frame_allocator::deallocate_frame(physical_frame const & physical_frame) -> void
+  {
+    free_frames.push(physical_frame);
+  }
+}  // namespace teachos::arch::memory::allocator
diff --git a/arch/x86_64/src/memory/main.cpp b/arch/x86_64/src/memory/main.cpp
index a920a20..3041a75 100644
--- a/arch/x86_64/src/memory/main.cpp
+++ b/arch/x86_64/src/memory/main.cpp
@@ -4,6 +4,8 @@
 #include "arch/kernel/cpu/control_register.hpp"
 #include "arch/kernel/cpu/msr.hpp"
 #include "arch/memory/allocator/area_frame_allocator.hpp"
+#include "arch/memory/allocator/concept.hpp"
+#include "arch/memory/allocator/stack_frame_allocator.hpp"
 #include "arch/memory/heap/heap_allocator.hpp"
 #include "arch/memory/paging/active_page_table.hpp"
 #include "arch/memory/paging/kernel_mapper.hpp"
@@ -12,7 +14,21 @@ namespace teachos::arch::memory
 {
   namespace
   {
-    auto remap_heap(allocator::area_frame_allocator allocator, paging::active_page_table & active_table) -> void
+    template<allocator::FrameAllocator T>
+    auto create_frame_allocator(multiboot::memory_information const & memory_information) -> T
+    {
+      return allocator::area_frame_allocator{memory_information};
+    }
+
+    template<>
+    auto create_frame_allocator(multiboot::memory_information const & memory_information)
+        -> allocator::stack_frame_allocator
+    {
+      return allocator::stack_frame_allocator{memory_information};
+    }
+
+    template<allocator::FrameAllocator T>
+    auto remap_heap(T & allocator, paging::active_page_table & active_table) -> void
     {
       auto const start_page = paging::virtual_page::containing_address(memory::heap::HEAP_START);
       auto const end_page =
@@ -36,7 +52,7 @@ namespace teachos::arch::memory
     has_been_called = true;
 
     auto const memory_information = multiboot::read_multiboot2();
-    allocator::area_frame_allocator allocator(memory_information);
+    auto allocator = create_frame_allocator<allocator::stack_frame_allocator>(memory_information);
 
     kernel::cpu::set_cr0_bit(kernel::cpu::cr0_flags::WRITE_PROTECT);
     kernel::cpu::set_efer_bit(kernel::cpu::efer_flags::NXE);