kernel: add bitmap_allocator tests

4 files changed, 309 insertions, 11 deletions

diff --git a/kernel/CMakeLists.txt b/kernel/CMakeLists.txt
index 9db2ab7..926a682 100644
--- a/kernel/CMakeLists.txt
+++ b/kernel/CMakeLists.txt
@@ -111,6 +111,9 @@ else()
         # KSTD Shim Tests
         "kstd/print.tests.cpp"
         
+        # Memory Subsystem Tests
+        "src/memory/bitmap_allocator.tests.cpp"
+
         # Test Executable Main
         "src/main.tests.cpp"
     )
diff --git a/kernel/src/memory/bitmap_allocator.cpp b/kernel/src/memory/bitmap_allocator.cpp
index c010f77..caaf5a4 100644
--- a/kernel/src/memory/bitmap_allocator.cpp
+++ b/kernel/src/memory/bitmap_allocator.cpp
@@ -6,6 +6,7 @@
 #include <cstddef>
 #include <cstdint>
 #include <optional>
+#include <ranges>
 #include <span>
 #include <utility>
 
@@ -17,7 +18,9 @@ namespace kernel::memory
       , m_frame_count{frame_count}
       , m_last_index{}
   {
-    std::ranges::fill(m_bitmap, ~0uz);
+    constexpr auto bits_per_word = 64uz;
+    auto to_fill = (frame_count + bits_per_word - 1) / bits_per_word;
+    std::ranges::fill(std::views::take(m_bitmap, to_fill), ~0uz);
   }
 
   auto bitmap_frame_allocator::allocate_many(std::size_t count) noexcept
@@ -78,22 +81,25 @@ namespace kernel::memory
 
   auto bitmap_frame_allocator::test(std::size_t index) const noexcept -> bool
   {
-    auto entry_entry = index / 64;
-    auto entry_offset = index % 64;
+    constexpr auto bits_per_word = 64uz;
+    auto entry_entry = index / bits_per_word;
+    auto entry_offset = index % bits_per_word;
     return (m_bitmap[entry_entry] & (1uz << entry_offset));
   }
 
   auto bitmap_frame_allocator::set(std::size_t index) noexcept -> void
   {
-    auto entry_entry = index / 64;
-    auto entry_offset = index % 64;
+    constexpr auto bits_per_word = 64uz;
+    auto entry_entry = index / bits_per_word;
+    auto entry_offset = index % bits_per_word;
     m_bitmap[entry_entry] |= (1uz << entry_offset);
   }
 
   auto bitmap_frame_allocator::clear(std::size_t index) noexcept -> void
   {
-    auto entry_entry = index / 64;
-    auto entry_offset = index % 64;
+    constexpr auto bits_per_word = 64uz;
+    auto entry_entry = index / bits_per_word;
+    auto entry_offset = index % bits_per_word;
     m_bitmap[entry_entry] &= ~(1uz << entry_offset);
   }
 
diff --git a/kernel/src/memory/bitmap_allocator.tests.cpp b/kernel/src/memory/bitmap_allocator.tests.cpp
new file mode 100644
index 0000000..56ec0a4
--- /dev/null
+++ b/kernel/src/memory/bitmap_allocator.tests.cpp
@@ -0,0 +1,289 @@
+#include "kernel/memory/bitmap_allocator.hpp"
+
+#include "kapi/memory.hpp"
+
+#include "catch2/matchers/catch_matchers.hpp"
+#include "catch2/matchers/catch_matchers_range_equals.hpp"
+
+#include <catch2/catch_test_macros.hpp>
+
+#include <cstdint>
+#include <limits>
+#include <ranges>
+#include <span>
+#include <vector>
+
+constexpr auto all_bits_set = std::numeric_limits<std::uint64_t>::max();
+constexpr auto available_frames = 1024uz;
+
+SCENARIO("Bitmap allocator construction and initialization", "[memory][bitmap_allocator]")
+{
+  GIVEN("A storage region")
+  {
+    auto storage = std::vector(available_frames / 64, 0uz);
+
+    WHEN("constructing the allocator with 0 frames")
+    {
+      auto allocator = kernel::memory::bitmap_frame_allocator{std::span(storage), 0};
+
+      THEN("the storage region is not modified")
+      {
+        REQUIRE_THAT(storage, Catch::Matchers::RangeEquals(std::vector(16, 0uz)));
+      }
+    }
+
+    WHEN("constructing with 1 frame")
+    {
+      auto allocator = kernel::memory::bitmap_frame_allocator{std::span(storage), 1};
+
+      THEN("the first word of the storage region is set to all ones")
+      {
+        REQUIRE_THAT(std::views::take(storage, 1), Catch::Matchers::RangeEquals(std::vector(1, all_bits_set)));
+      }
+
+      THEN("the rest of the storage region is not modified")
+      {
+        REQUIRE_THAT(std::views::drop(storage, 1), Catch::Matchers::RangeEquals(std::vector(15, 0uz)));
+      }
+    }
+
+    WHEN("constructing with 64 frames")
+    {
+      auto allocator = kernel::memory::bitmap_frame_allocator{std::span(storage), 64};
+
+      THEN("the first word of the storage region is set to all ones")
+      {
+        REQUIRE_THAT(std::views::take(storage, 1), Catch::Matchers::RangeEquals(std::vector(1, all_bits_set)));
+      }
+
+      THEN("the rest of the storage region is not modified")
+      {
+        REQUIRE_THAT(std::views::drop(storage, 1), Catch::Matchers::RangeEquals(std::vector(15, 0uz)));
+      }
+    }
+
+    WHEN("constructing with all available frames")
+    {
+      auto allocator = kernel::memory::bitmap_frame_allocator{std::span(storage), available_frames};
+
+      THEN("the storage region is filled with all ones")
+      {
+        REQUIRE_THAT(storage, Catch::Matchers::RangeEquals(std::vector(16, all_bits_set)));
+      }
+    }
+
+    WHEN("constructing with half the available frames")
+    {
+      auto allocator = kernel::memory::bitmap_frame_allocator{std::span(storage), available_frames / 2};
+
+      THEN("the first half of the storage region is filled with all ones")
+      {
+        REQUIRE_THAT(std::views::take(storage, (available_frames / 2) / 64),
+                     Catch::Matchers::RangeEquals(std::vector((available_frames / 2) / 64, all_bits_set)));
+      }
+
+      THEN("the second half of the storage region is filled with all zeros")
+      {
+        REQUIRE_THAT(std::views::drop(storage, (available_frames / 2) / 64),
+                     Catch::Matchers::RangeEquals(std::vector((available_frames / 2) / 64, 0uz)));
+      }
+    }
+  }
+}
+
+SCENARIO("Bitmap allocator frame allocation", "[memory][bitmap_allocator]")
+{
+  GIVEN("A storage region")
+  {
+    auto storage = std::vector(available_frames / 64, 0uz);
+
+    AND_GIVEN("an allocator constructed with all available frames but no free ones")
+    {
+      auto allocator = kernel::memory::bitmap_frame_allocator{std::span(storage), available_frames};
+
+      WHEN("allocating 1 frame")
+      {
+        auto result = allocator.allocate_many(1);
+
+        THEN("the result is empty")
+        {
+          REQUIRE_FALSE(result.has_value());
+        }
+      }
+    }
+
+    AND_GIVEN("an allocator constructed with all available frames but only one free one")
+    {
+      auto allocator = kernel::memory::bitmap_frame_allocator{std::span(storage), available_frames};
+      allocator.release_many({kapi::memory::frame{0}, 1});
+
+      WHEN("allocating 1 frame")
+      {
+        auto result = allocator.allocate_many(1);
+
+        THEN("the result is not empty")
+        {
+          REQUIRE(result.has_value());
+        }
+
+        THEN("the result contains 1 frame")
+        {
+          REQUIRE(result->second == 1);
+        }
+      }
+
+      WHEN("allocating more frames than are free")
+      {
+        auto result = allocator.allocate_many(2);
+
+        THEN("the result is empty")
+        {
+          REQUIRE_FALSE(result.has_value());
+        }
+
+        AND_WHEN("allocating a single frame")
+        {
+          auto result = allocator.allocate_many(1);
+
+          THEN("the result is not empty")
+          {
+            REQUIRE(result.has_value());
+          }
+        }
+
+        WHEN("allocating 0 frames")
+        {
+          auto result = allocator.allocate_many(0);
+
+          THEN("the result is empty")
+          {
+            REQUIRE_FALSE(result.has_value());
+          }
+        }
+      }
+    }
+
+    AND_GIVEN("an allocator with many single frame holes")
+    {
+      auto allocator = kernel::memory::bitmap_frame_allocator{std::span(storage), available_frames};
+      for (auto i = 0uz; i < available_frames; i += 2)
+      {
+        allocator.release_many({kapi::memory::frame{i}, 1});
+      }
+
+      WHEN("allocating 1 frame")
+      {
+        auto result = allocator.allocate_many(1);
+
+        THEN("the result is not empty")
+        {
+          REQUIRE(result.has_value());
+        }
+
+        THEN("the result contains 1 frame")
+        {
+          REQUIRE(result->second == 1);
+        }
+      }
+
+      WHEN("allocating 2 frames")
+      {
+        auto result = allocator.allocate_many(2);
+
+        THEN("the result is empty")
+        {
+          REQUIRE_FALSE(result.has_value());
+        }
+      }
+    }
+
+    AND_GIVEN("and allocator with all frames marked as free")
+    {
+      auto allocator = kernel::memory::bitmap_frame_allocator{std::span(storage), available_frames};
+      allocator.release_many({kapi::memory::frame{0}, available_frames});
+
+      WHEN("allocating 1 frame")
+      {
+        auto result = allocator.allocate_many(1);
+
+        THEN("the result is not empty")
+        {
+          REQUIRE(result.has_value());
+        }
+
+        THEN("the result contains 1 frame")
+        {
+          REQUIRE(result->second == 1);
+        }
+      }
+
+      WHEN("allocating multiple frames")
+      {
+        auto result = allocator.allocate_many(20);
+
+        THEN("the result is not empty")
+        {
+          REQUIRE(result.has_value());
+        }
+
+        THEN("the result contains 20 frames")
+        {
+          REQUIRE(result->second == 20);
+        }
+      }
+
+      WHEN("marking all frames as used")
+      {
+        for (auto i = 0uz; i < available_frames; i++)
+        {
+          allocator.mark_used(kapi::memory::frame{i});
+        }
+
+        THEN("the allocator has no free frames")
+        {
+          REQUIRE_FALSE(allocator.allocate_many(1).has_value());
+        }
+      }
+    }
+
+    AND_GIVEN("an allocator with a contiguous block of free frames")
+    {
+      auto allocator = kernel::memory::bitmap_frame_allocator{std::span(storage), available_frames};
+      allocator.release_many({kapi::memory::frame{0}, available_frames});
+      for (auto i = 0uz; i < available_frames / 2; i++)
+      {
+        allocator.mark_used(kapi::memory::frame{i});
+      }
+
+      WHEN("allocating a single frame")
+      {
+        auto result = allocator.allocate_many(1);
+
+        THEN("the result is not empty")
+        {
+          REQUIRE(result.has_value());
+        }
+
+        THEN("the result contains 1 frame")
+        {
+          REQUIRE(result->second == 1);
+        }
+      }
+
+      WHEN("allocating multiple frames")
+      {
+        auto result = allocator.allocate_many(20);
+
+        THEN("the result is not empty")
+        {
+          REQUIRE(result.has_value());
+        }
+
+        THEN("the result contains 20 frames")
+        {
+          REQUIRE(result->second == 20);
+        }
+      }
+    }
+  }
+}
\ No newline at end of file
diff --git a/kernel/src/test_support/kapi/memory.cpp b/kernel/src/test_support/kapi/memory.cpp
index 6de2f60..556962c 100644
--- a/kernel/src/test_support/kapi/memory.cpp
+++ b/kernel/src/test_support/kapi/memory.cpp
@@ -19,6 +19,7 @@ namespace kapi::memory
   {
     //! The size of the simulated RAM.
     constexpr auto simulate_memory_size = kstd::units::MiB(32);
+    constexpr auto number_of_simulated_frames = simulate_memory_size / frame::size;
 
     struct test_boostrap_frame_allocator : frame_allocator
     {
@@ -66,10 +67,9 @@ namespace kapi::memory
 
     auto handoff_to_kernel_pmm(frame_allocator & new_allocator) -> void
     {
-      for (auto i = 0uz; i < boostrap_allocator.next_free_frame; ++i)
-      {
-        new_allocator.mark_used(frame{i});
-      }
+      auto first_free_frame = boostrap_allocator.next_free_frame;
+      auto number_of_free_frames = number_of_simulated_frames - first_free_frame;
+      new_allocator.release_many({frame{first_free_frame}, number_of_free_frames});
     }
 
   }  // namespace