kernel/tests: add basic heap allocator tests

4 files changed, 118 insertions, 18 deletions

diff --git a/kernel/CMakeLists.txt b/kernel/CMakeLists.txt
index 4264441..1b71a5f 100644
--- a/kernel/CMakeLists.txt
+++ b/kernel/CMakeLists.txt
@@ -115,6 +115,7 @@ else()
         
         # Memory Subsystem Tests
         "src/memory/bitmap_allocator.tests.cpp"
+        "src/memory/block_list_allocator.tests.cpp"
 
         # Storage Subsystem Tests
         "src/devices/storage/ram_disk/device.tests.cpp"
diff --git a/kernel/include/kernel/test_support/memory.hpp b/kernel/include/kernel/test_support/memory.hpp
new file mode 100644
index 0000000..c6b7449
--- /dev/null
+++ b/kernel/include/kernel/test_support/memory.hpp
@@ -0,0 +1,11 @@
+#ifndef TEACHOS_KERNEL_TEST_SUPPORT_MEMORY_HPP
+#define TEACHOS_KERNEL_TEST_SUPPORT_MEMORY_HPP
+
+#include "kapi/memory.hpp"
+
+namespace kernel::tests::memory
+{
+  auto heap_base() -> kapi::memory::linear_address;
+}
+
+#endif
\ 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..5f6f382
--- /dev/null
+++ b/kernel/src/memory/block_list_allocator.tests.cpp
@@ -0,0 +1,80 @@
+#include "kernel/memory/block_list_allocator.hpp"
+
+#include "kernel/test_support/memory.hpp"
+
+#include <kstd/units>
+
+#include <catch2/catch_test_macros.hpp>
+
+#include <cstddef>
+
+using namespace kstd::units_literals;
+
+SCENARIO("Block List Allocator Operations", "[memory][allocator]")
+{
+  GIVEN("A newly initialized block list allocator mapped via the test sandbox")
+  {
+    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);
+      }
+    }
+  }
+}
diff --git a/kernel/src/test_support/kapi/memory.cpp b/kernel/src/test_support/kapi/memory.cpp
index 3a2c2ba..f244b7f 100644
--- a/kernel/src/test_support/kapi/memory.cpp
+++ b/kernel/src/test_support/kapi/memory.cpp
@@ -9,29 +9,29 @@
 
 #include <optional>
 
-namespace kapi::memory
+namespace
 {
+  //! The size of the simulated RAM.
+  constexpr auto memory_size = kstd::units::MiB(32);
+  constexpr auto number_of_frames = memory_size / kapi::memory::frame::size;
 
-  namespace
-  {
-    //! The size of the simulated RAM.
-    constexpr auto memory_size = kstd::units::MiB(32);
-    constexpr auto number_of_frames = memory_size / frame::size;
+  auto constinit bump_allocator = std::optional<kernel::tests::bump_frame_allocator>{};
+  auto constinit test_mapper = std::optional<kernel::tests::page_mapper>{};
 
-    auto constinit bump_allocator = std::optional<kernel::tests::bump_frame_allocator>{};
-    auto constinit test_mapper = std::optional<kernel::tests::page_mapper>{};
+  auto constinit old_allocator = std::optional<kapi::memory::frame_allocator *>{};
+  auto constinit old_mapper = std::optional<kapi::memory::page_mapper *>{};
 
-    auto constinit old_allocator = std::optional<frame_allocator *>{};
-    auto constinit old_mapper = std::optional<page_mapper *>{};
+  auto handoff_to_kernel_pmm(kapi::memory::frame_allocator & new_allocator) -> void
+  {
+    auto first_free_frame = bump_allocator->next_free_frame;
+    auto number_of_free_frames = number_of_frames - first_free_frame;
+    new_allocator.release_many({kapi::memory::frame{first_free_frame}, number_of_free_frames});
+  }
 
-    auto handoff_to_kernel_pmm(frame_allocator & new_allocator) -> void
-    {
-      auto first_free_frame = bump_allocator->next_free_frame;
-      auto number_of_free_frames = number_of_frames - first_free_frame;
-      new_allocator.release_many({frame{first_free_frame}, number_of_free_frames});
-    }
+}  // namespace
 
-  }  // namespace
+namespace kapi::memory
+{
 
   auto init() -> void
   {
@@ -60,4 +60,12 @@ namespace kapi::memory
     test_mapper.reset();
   }
 
-}  // namespace kapi::memory
\ No newline at end of file
+}  // namespace kapi::memory
+
+namespace kernel::tests::memory
+{
+  auto heap_base() -> kapi::memory::linear_address
+  {
+    return test_mapper->memory.heap_base();
+  }
+}  // namespace kernel::tests::memory
\ No newline at end of file