kapi/memory: implement multi-frame allocation

3 files changed, 113 insertions, 26 deletions

diff --git a/arch/x86_64/include/x86_64/memory/buffered_allocator.hpp b/arch/x86_64/include/x86_64/memory/buffered_allocator.hpp
index 90ac878..fa3b5cb 100644
--- a/arch/x86_64/include/x86_64/memory/buffered_allocator.hpp
+++ b/arch/x86_64/include/x86_64/memory/buffered_allocator.hpp
@@ -2,11 +2,13 @@
 #define TEACHOS_X86_64_BUFFERED_ALLOCATOR_HPP
 
 #include "kapi/memory.hpp"
+#include "kapi/system.hpp"
 
 #include <algorithm>
 #include <array>
 #include <cstddef>
 #include <optional>
+#include <utility>
 
 namespace teachos::memory::x86_64
 {
@@ -16,8 +18,15 @@ namespace teachos::memory::x86_64
   {
     explicit buffered_allocator(frame_allocator * underlying)
         : m_underlying{underlying}
+        , m_free{BufferSize}
     {
-      std::ranges::generate(m_pool, [this] { return m_underlying->allocate(); });
+      auto from_underlying = m_underlying->allocate_many(BufferSize);
+      if (!from_underlying)
+      {
+        system::panic("[x86_64:MEM] Not enough frames available from underlying allocator.");
+      }
+      auto [first_frame, count] = *from_underlying;
+      std::ranges::generate_n(m_pool.begin(), count, [first_frame]() mutable { return first_frame++; });
     }
 
     buffered_allocator(buffered_allocator const &) = delete;
@@ -28,7 +37,7 @@ namespace teachos::memory::x86_64
       std::ranges::for_each(m_pool, [this](auto const & maybe_frame) {
         if (maybe_frame)
         {
-          m_underlying->release(*maybe_frame);
+          m_underlying->release_many({*maybe_frame, 1});
         }
       });
     }
@@ -36,30 +45,90 @@ namespace teachos::memory::x86_64
     auto operator=(buffered_allocator const &) = delete;
     auto operator=(buffered_allocator &&) = delete;
 
-    auto allocate() noexcept -> std::optional<frame> override
+    auto allocate_many(std::size_t count = 1) noexcept -> std::optional<std::pair<frame, std::size_t>> override
     {
-      auto found = std::ranges::find_if(m_pool, [](auto const & candidate) { return candidate.has_value(); });
-      if (found == std::end(m_pool))
+      if (count > m_free)
+      {
+        return m_underlying->allocate_many(count);
+      }
+
+      auto start_of_set = std::ranges::find_if(m_pool, [](auto const & candidate) { return candidate.has_value(); });
+      if (start_of_set == m_pool.end())
+      {
+        return m_underlying->allocate_many(count);
+      }
+
+      if (std::distance(start_of_set, m_pool.end()) < static_cast<std::ptrdiff_t>(count))
+      {
+        return m_underlying->allocate_many(count);
+      }
+
+      auto number_of_consecutive_frames = 1uz;
+      for (auto current = std::next(start_of_set); current != m_pool.end() && number_of_consecutive_frames < count;
+           ++current)
+      {
+        if (*current && *start_of_set && **current == (**start_of_set) + 1)
+        {
+          ++number_of_consecutive_frames;
+          continue;
+        }
+        number_of_consecutive_frames = 0;
+        start_of_set = current;
+      }
+
+      if (std::distance(start_of_set, m_pool.end()) >= static_cast<std::ptrdiff_t>(count))
       {
-        return m_underlying->allocate();
+        auto result = std::make_pair(**start_of_set, count);
+        m_free -= count;
+        std::ranges::for_each(start_of_set, start_of_set + count, [](auto & frame) { frame.reset(); });
+        sort_pool();
+        return result;
       }
-      auto frame = found->value();
-      found->reset();
-      return frame;
+      return m_underlying->allocate_many(count);
     }
 
-    auto release(frame frame) -> void override
+    auto release_many(std::pair<frame, std::size_t> frame_set) -> void override
     {
-      auto found = std::ranges::find_if(m_pool, [](auto const & candidate) { return !candidate; });
-      if (found == std::end(m_pool))
+      if (m_free == BufferSize)
       {
-        return m_underlying->release(frame);
+        return m_underlying->release_many(frame_set);
+      }
+
+      auto [first_frame, count] = frame_set;
+      auto start_of_set = std::ranges::find_if(m_pool, [](auto const & candidate) { return !candidate.has_value(); });
+
+      for (auto current = start_of_set; current != m_pool.end() && count; ++current)
+      {
+        *current = first_frame++;
+        ++m_free;
+        --count;
+      }
+      sort_pool();
+
+      if (count)
+      {
+        m_underlying->release_many({first_frame, count});
       }
-      (*found) = frame;
     }
 
   private:
+    auto sort_pool() -> void
+    {
+      std::ranges::sort(m_pool, [](auto lhs, auto rhs) -> bool {
+        if (lhs && rhs)
+        {
+          return *lhs < *rhs;
+        }
+        if (!lhs)
+        {
+          return false;
+        }
+        return true;
+      });
+    }
+
     frame_allocator * m_underlying;
+    std::size_t m_free;
     std::array<std::optional<frame>, BufferSize> m_pool{};
   };
 
diff --git a/arch/x86_64/include/x86_64/memory/region_allocator.hpp b/arch/x86_64/include/x86_64/memory/region_allocator.hpp
index bf657a0..4063bcc 100644
--- a/arch/x86_64/include/x86_64/memory/region_allocator.hpp
+++ b/arch/x86_64/include/x86_64/memory/region_allocator.hpp
@@ -7,6 +7,7 @@
 
 #include <multiboot2/information.hpp>
 
+#include <cstddef>
 #include <optional>
 #include <utility>
 
@@ -50,16 +51,16 @@ namespace teachos::memory::x86_64
     //! @param information The description of the detected memory regions as well as regions that are already occupied.
     explicit region_allocator(memory_information const & information);
 
-    //! @copydoc frame_allocator::allocate
+    //! @copydoc frame_allocator::allocate_many
     //!
     //! @note As long as free frames are available, successive calls to this implementation are guaranteed to yield
     //! frames in ascending order.
-    auto allocate() noexcept -> std::optional<frame> override;
+    auto allocate_many(std::size_t count = 1) noexcept -> std::optional<std::pair<frame, std::size_t>> override;
 
-    //! @copydoc frame_allocator::release
+    //! @copydoc frame_allocator::release_many
     //!
     //! @note This implementation will never actually release any frames.
-    auto release(frame frame) -> void override;
+    auto release_many(std::pair<frame, std::size_t> frame_set) -> void override;
 
     auto next_free_frame() noexcept -> std::optional<frame>;
 
diff --git a/arch/x86_64/src/memory/region_allocator.cpp b/arch/x86_64/src/memory/region_allocator.cpp
index efa1f4a..7a8fb8b 100644
--- a/arch/x86_64/src/memory/region_allocator.cpp
+++ b/arch/x86_64/src/memory/region_allocator.cpp
@@ -6,6 +6,7 @@
 #include <multiboot2/information.hpp>
 
 #include <algorithm>
+#include <cstddef>
 #include <optional>
 #include <ranges>
 #include <utility>
@@ -56,7 +57,7 @@ namespace teachos::memory::x86_64
 
     m_current_region = *lowest_region;
     if (auto start_of_region = frame::containing(physical_address{m_current_region->base});
-        start_of_region < m_next_frame)
+        start_of_region > m_next_frame)
     {
       m_next_frame = start_of_region;
     }
@@ -96,16 +97,32 @@ namespace teachos::memory::x86_64
     return m_current_region.transform([this](auto) -> auto { return m_next_frame; });
   }
 
-  auto region_allocator::allocate() noexcept -> std::optional<frame>
+  auto region_allocator::allocate_many(std::size_t count) noexcept -> std::optional<std::pair<frame, std::size_t>>
   {
-    return find_next_frame().transform([this](auto frame) -> auto {
-      auto result = frame;
-      ++m_next_frame;
-      return result;
-    });
+    while (m_current_region)
+    {
+      auto result = find_next_frame();
+
+      if (result)
+      {
+        auto region_end = last_frame(*m_current_region);
+        if ((region_end.number() - result->number()) >= count)
+        {
+          m_next_frame = m_next_frame + count;
+          return std::make_pair(*result, count);
+        }
+        else
+        {
+          m_next_frame = region_end + 1;
+          choose_next_region();
+        }
+      }
+    }
+
+    return std::nullopt;
   }
 
-  auto region_allocator::release(frame) -> void {}
+  auto region_allocator::release_many(std::pair<frame, std::size_t>) -> void {}
 
   auto region_allocator::next_free_frame() noexcept -> std::optional<frame>
   {