begin implementing frame allocator

2 files changed, 126 insertions, 16 deletions

diff --git a/arch/x86_64/include/arch/memory/frame_allocator.hpp b/arch/x86_64/include/arch/memory/frame_allocator.hpp
index 8dee848..35d7360 100644
--- a/arch/x86_64/include/arch/memory/frame_allocator.hpp
+++ b/arch/x86_64/include/arch/memory/frame_allocator.hpp
@@ -1,6 +1,7 @@
 #ifndef TEACHOS_ARCH_X86_64_MEMORY_FRAME_HPP
 #define TEACHOS_ARCH_X86_64_MEMORY_FRAME_HPP
 
+#include "multiboot.hpp"
 #include <cstddef>
 #include <optional>
 
@@ -8,20 +9,26 @@ namespace teachos::arch::memory
 {
   namespace
   {
-    const size_t PAGE_FRAME_SIZE = 4096U;
+    const std::size_t PAGE_FRAME_SIZE = 4096U;
   }
 
   struct frame
   {
-    size_t frame_number;
+    std::size_t frame_number;
 
-    frame(size_t frame_number)
+    frame(std::size_t frame_number)
         : frame_number(frame_number)
     {
       // Nothing to do
     }
 
-    auto containing_address(size_t address) -> frame { return frame{address / PAGE_FRAME_SIZE}; }
+    static auto containing_address(std::size_t address) -> frame { return frame{address / PAGE_FRAME_SIZE}; }
+
+    constexpr bool operator==(const frame & other) const noexcept { return frame_number == other.frame_number; }
+    constexpr bool operator>(const frame & other) const noexcept { return frame_number > other.frame_number; }
+    constexpr bool operator<(const frame & other) const noexcept { return frame_number < other.frame_number; }
+    constexpr bool operator>=(const frame & other) const noexcept { return frame_number >= other.frame_number; }
+    constexpr bool operator<=(const frame & other) const noexcept { return frame_number <= other.frame_number; }
   };
 
   struct frame_allocator
@@ -30,18 +37,53 @@ namespace teachos::arch::memory
     virtual auto deallocate_frame(frame frame) -> void = 0;
   };
 
-  struct area_frame_allocator : public frame_allocator
+  // TODO: FIX CONCEPT USAGE
+  // template<typename T>
+  // concept FrameAllocator = requires(T t) {
+  //   { t.allocate_frame() } -> std::optional<frame>;
+  //   { t.deallocate_frame() } -> void;
+  // };
+
+  // template<FrameAllocator T>
+  struct area_frame_allocator : frame_allocator
   {
-    frame next_free_frame;
-    // std::optional<memory_area> current_area;
-    // memory_area * areas;
-    frame kernel_start;
-    frame kernel_end;
-    frame multiboot_start;
-    frame multiboot_end;
-
-    auto allocate_frame() -> std::optional<frame> override;
-    auto deallocate_frame(frame frame) -> void override;
+    frame next_free_frame{0};                                             //!< The frame after the last allocated one
+    std::optional<arch::memory::memory_area> current_area{std::nullopt};  //!< The current memory area
+    arch::memory::memory_area * areas;                                    //!< A list of all memory areas
+    frame kernel_start;     //!< The start address of the kernel code in memory
+    frame kernel_end;       //!< The end address of the kernel code in memory
+    frame multiboot_start;  //!< The start address of the multiboot code in memory
+    frame multiboot_end;    //!< The end address of the multiboot code in memory
+
+    area_frame_allocator(std::size_t kernel_start, std::size_t kernel_end, std::size_t multiboot_start,
+                         std::size_t multiboot_end, arch::memory::memory_area * memory_areas)
+        : kernel_start(frame{kernel_start})
+        , kernel_end(frame{kernel_end})
+        , multiboot_start(frame{multiboot_start})
+        , multiboot_end(frame{multiboot_end})
+        , areas(memory_areas)
+    {
+      choose_next_area();
+    }
+
+    /**
+     * @brief Allocate memory be finding and returning a free frame
+     *
+     * The frame allocation executes multiple checks before returning
+     * the 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 frame
+     */
+    auto allocate_frame() -> std::optional<frame>;
+    auto deallocate_frame(frame frame) -> void;
+
+  private:
+    /**
+     * @brief Find the next memory area and write it into current_area
+     */
+    auto choose_next_area() -> void;
   };
 }  // namespace teachos::arch::memory
 
diff --git a/arch/x86_64/src/memory/frame_allocator.cpp b/arch/x86_64/src/memory/frame_allocator.cpp
index b9d26a5..b8f53be 100644
--- a/arch/x86_64/src/memory/frame_allocator.cpp
+++ b/arch/x86_64/src/memory/frame_allocator.cpp
@@ -2,8 +2,76 @@
 
 namespace teachos::arch::memory
 {
-  auto area_frame_allocator::allocate_frame() -> std::optional<frame> {}
+  auto area_frame_allocator::allocate_frame() -> std::optional<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)
+    {
+      frame frame{next_free_frame.frame_number};
+
+      struct frame current_area_last_frame = {
+          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 (frame >= multiboot_start && frame <= kernel_end)
+      {
+        // `frame` is used by the kernel or multiboot information structure
+        next_free_frame = arch::memory::frame{kernel_end.frame_number + 1};
+      }
+      else
+      {
+        // Frame is unused, increment `next_free_frame` and return it
+        next_free_frame.frame_number += 1;
+        return frame;
+      }
+
+      // `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(frame frame) -> void {}
 
+  namespace
+  {
+    auto area_frame_allocator::choose_next_area() -> void
+    {
+      current_area = std::nullopt;
+
+      // TODO: Fix this loop as soon as you've created an area iterator
+      for (const auto & area : areas)
+      {
+        std::size_t address = area.base_addr + area.length - 1;
+        if (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_addr < current_area->base_address)
+          {
+            current_area = area;
+          }
+        }
+      }
+
+      if (current_area)
+      {
+        // Update the `next_free_frame` according to the new memory area
+        frame start_frame = frame::containing_address(current_area->base_address);
+        if (next_free_frame < start_frame)
+        {
+          next_free_frame = start_frame;
+        }
+      }
+    }
+
+  }  // namespace
 }  // namespace teachos::arch::memory