Merge branch 'fmorgner/develop-SA-FS26/kernel-bht' into 'develop-BA-FS26'

Add experimental support for kernel tests

See merge request teachos/kernel!20

3 files changed, 395 insertions, 7 deletions

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/memory/block_list_allocator.tests.cpp b/kernel/src/memory/block_list_allocator.tests.cpp
new file mode 100644
index 0000000..8ca426d
--- /dev/null
+++ b/kernel/src/memory/block_list_allocator.tests.cpp
@@ -0,0 +1,93 @@
+#include "kernel/memory/block_list_allocator.hpp"
+
+#include "kapi/memory.hpp"
+
+#include "kernel/test_support/memory.hpp"
+
+#include <kstd/units>
+
+#include <catch2/catch_test_macros.hpp>
+
+#include <cstddef>
+
+using namespace kstd::units_literals;
+
+namespace kapi
+{
+  namespace memory
+  {
+    auto reset() -> void;
+  }
+}  // namespace kapi
+
+SCENARIO("Block List Allocator Operations", "[memory][allocator]")
+{
+  GIVEN("A newly initialized block list allocator mapped via the test sandbox")
+  {
+    kapi::memory::reset();
+    kapi::memory::init();
+
+    auto sandbox_base = kernel::tests::memory::heap_base();
+    kernel::memory::block_list_allocator allocator{sandbox_base};
+
+    WHEN("a basic allocation request is made")
+    {
+      void * ptr = allocator.allocate(128_B, 8_B);
+
+      THEN("a valid, non-null pointer is returned")
+      {
+        REQUIRE(ptr != nullptr);
+      }
+
+      AND_THEN("the returned memory is writeable without causing segmentation faults")
+      {
+        auto byte_ptr = static_cast<std::byte *>(ptr);
+        byte_ptr[0] = std::byte{0xDE};
+        byte_ptr[127] = std::byte{0xAD};
+        REQUIRE(byte_ptr[0] == std::byte{0xDE});
+        REQUIRE(byte_ptr[127] == std::byte{0xAD});
+      }
+
+      allocator.deallocate(ptr);
+    }
+
+    WHEN("multiple allocations are made sequentially")
+    {
+      void * ptr1 = allocator.allocate(64_B, 8_B);
+      void * ptr2 = allocator.allocate(64_B, 8_B);
+      void * ptr3 = allocator.allocate(1_KiB, 16_B);
+
+      THEN("they return distinct, non-overlapping memory blocks")
+      {
+        REQUIRE(ptr1 != nullptr);
+        REQUIRE(ptr2 != nullptr);
+        REQUIRE(ptr3 != nullptr);
+        REQUIRE(ptr1 != ptr2);
+        REQUIRE(ptr2 != ptr3);
+        REQUIRE(ptr1 != ptr3);
+      }
+
+      allocator.deallocate(ptr1);
+      allocator.deallocate(ptr2);
+      allocator.deallocate(ptr3);
+    }
+
+    WHEN("a block is allocated and then completely freed")
+    {
+      void * original_ptr = allocator.allocate(512_B, 16_B);
+      allocator.deallocate(original_ptr);
+
+      AND_WHEN("a new allocation of equal or smaller size is requested")
+      {
+        void * new_ptr = allocator.allocate(128_B, 16_B);
+
+        THEN("the allocator actively reuses the coalesced space")
+        {
+          REQUIRE(new_ptr == original_ptr);
+        }
+
+        allocator.deallocate(new_ptr);
+      }
+    }
+  }
+}