Merge branch 'develop-BA-FS26' into 'develop'HEADdevelop

Merge of BA-FS26 branch into develop

See merge request teachos/kernel!49

6 files changed, 531 insertions, 34 deletions

diff --git a/kernel/src/memory/bitmap_allocator.cpp b/kernel/src/memory/bitmap_allocator.cpp
index c010f77..240e2af 100644
--- a/kernel/src/memory/bitmap_allocator.cpp
+++ b/kernel/src/memory/bitmap_allocator.cpp
@@ -1,11 +1,12 @@
-#include "kernel/memory/bitmap_allocator.hpp"
+#include <kernel/memory/bitmap_allocator.hpp>
 
-#include "kapi/memory.hpp"
+#include <kapi/memory.hpp>
 
 #include <algorithm>
 #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..05d11a3
--- /dev/null
+++ b/kernel/src/memory/bitmap_allocator.tests.cpp
@@ -0,0 +1,288 @@
+#include <kernel/memory/bitmap_allocator.hpp>
+
+#include <kapi/memory.hpp>
+
+#include <catch2/catch_test_macros.hpp>
+#include <catch2/matchers/catch_matchers.hpp>
+#include <catch2/matchers/catch_matchers_range_equals.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.cpp b/kernel/src/memory/block_list_allocator.cpp
index 5d870d8..6e68ada 100644
--- a/kernel/src/memory/block_list_allocator.cpp
+++ b/kernel/src/memory/block_list_allocator.cpp
@@ -1,24 +1,26 @@
-#include "kernel/memory/block_list_allocator.hpp"
+#include <kernel/memory/block_list_allocator.hpp>
 
-#include "kapi/memory.hpp"
-#include "kapi/system.hpp"
+#include <kernel/memory/heap_allocator.hpp>
 
-#include "kernel/memory/heap_allocator.hpp"
+#include <kapi/memory.hpp>
+#include <kapi/system.hpp>
 
 #include <kstd/mutex>
+#include <kstd/units>
 
 #include <bit>
 #include <cstddef>
 #include <cstdint>
 #include <memory>
-#include <new>
+
+using namespace kstd::units_literals;
 
 namespace kernel::memory
 {
 
   namespace
   {
-    [[nodiscard]] constexpr auto align_up(std::byte * pointer, std::align_val_t alignment) noexcept -> std::byte *
+    [[nodiscard]] constexpr auto align_up(std::byte * pointer, kstd::units::bytes alignment) noexcept -> std::byte *
     {
       auto const remainder = std::bit_cast<std::uintptr_t>(pointer) % static_cast<std::size_t>(alignment);
       return remainder == 0 ? pointer : pointer + static_cast<std::size_t>(alignment) - remainder;
@@ -33,7 +35,7 @@ namespace kernel::memory
       , m_lock{}
   {}
 
-  auto block_list_allocator::allocate(std::size_t size, std::align_val_t alignment) noexcept -> void *
+  auto block_list_allocator::allocate(kstd::units::bytes size, kstd::units::bytes alignment) noexcept -> void *
   {
     kstd::lock_guard guard{m_lock};
 
@@ -47,13 +49,13 @@ namespace kernel::memory
           auto const raw_block = reinterpret_cast<std::byte *>(current);
           auto const unaligned_payload = raw_block + allocated_metadata_size;
           auto const aligned_payload = align_up(unaligned_payload, alignment);
-          auto const required_padding = static_cast<std::size_t>(aligned_payload - unaligned_payload);
+          auto const required_padding = static_cast<kstd::units::bytes>(aligned_payload - unaligned_payload);
           auto const total_required_size = required_padding + allocated_metadata_size + size;
 
           if (current->usable_size >= total_required_size)
           {
             auto const payload_header = aligned_payload - sizeof(block_header *) - sizeof(block_header);
-            auto const front_padding = static_cast<std::size_t>(payload_header - raw_block);
+            auto const front_padding = static_cast<kstd::units::bytes>(payload_header - raw_block);
 
             auto payload_block = current;
 
@@ -72,9 +74,10 @@ namespace kernel::memory
               payload_block->prev = current;
             }
 
-            auto const payload_size =
-                aligned_payload - reinterpret_cast<std::byte *>(payload_block) - allocated_metadata_size + size;
-            split(payload_block, payload_size, 0uz);
+            auto const header_size =
+                static_cast<kstd::units::bytes>(aligned_payload - reinterpret_cast<std::byte *>(payload_block));
+            auto const payload_size = header_size - allocated_metadata_size + size;
+            split(payload_block, payload_size, 0_B);
 
             payload_block->free = false;
 
@@ -87,7 +90,7 @@ namespace kernel::memory
         current = current->next;
       }
 
-      auto const search_size = size + static_cast<std::size_t>(alignment);
+      auto const search_size = size + alignment;
       if (attempt == 0uz && !expand(search_size))
       {
         return nullptr;
@@ -114,10 +117,10 @@ namespace kernel::memory
     coalesce(block);
   }
 
-  auto block_list_allocator::expand(std::size_t size) noexcept -> bool
+  auto block_list_allocator::expand(kstd::units::bytes size) noexcept -> bool
   {
     auto const total_required_size = size + allocated_metadata_size;
-    auto const frames_needed = (total_required_size + kapi::memory::frame::size - 1) / kapi::memory::frame::size;
+    auto const frames_needed = (total_required_size + kapi::memory::frame::size - 1_B) / kapi::memory::frame::size;
 
     auto const flags = kapi::memory::page_mapper::flags::writable | kapi::memory::page_mapper::flags::supervisor_only |
                        kapi::memory::page_mapper::flags::global;
@@ -187,7 +190,8 @@ namespace kernel::memory
     }
   }
 
-  auto block_list_allocator::split(block_header * block, std::size_t size, std::size_t padding) noexcept -> void
+  auto block_list_allocator::split(block_header * block, kstd::units::bytes size, kstd::units::bytes padding) noexcept
+      -> void
   {
     auto const new_block_size = size + padding;
 
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..c5f84c5
--- /dev/null
+++ b/kernel/src/memory/block_list_allocator.tests.cpp
@@ -0,0 +1,85 @@
+#include <kernel/memory/block_list_allocator.hpp>
+
+#include <kernel/test_support/memory.hpp>
+
+#include <kapi/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")
+  {
+    kernel::tests::memory::deinit();
+    kapi::memory::init();
+
+    auto sandbox_base = kernel::tests::memory::virtual_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/memory/mmio_allocator.cpp b/kernel/src/memory/mmio_allocator.cpp
new file mode 100644
index 0000000..ba23dbd
--- /dev/null
+++ b/kernel/src/memory/mmio_allocator.cpp
@@ -0,0 +1,111 @@
+#include <kernel/memory/mmio_allocator.hpp>
+
+#include <kapi/memory.hpp>
+#include <kapi/system.hpp>
+
+#include <kstd/allocator>
+
+#include <cstddef>
+#include <memory>
+#include <utility>
+
+namespace kernel::memory
+{
+
+  mmio_allocator::mmio_allocator(kapi::memory::linear_address base, std::size_t pages)
+      : m_head{make_node(base, pages, nullptr, nullptr, true)}
+  {}
+
+  auto mmio_allocator::allocate(std::size_t count) -> kapi::memory::linear_address
+  {
+    if (count == 0 || !m_head)
+    {
+      return {};
+    }
+
+    auto current = m_head;
+    while (current)
+    {
+      if (current->is_free && current->page_count >= count)
+      {
+        if (current->page_count > count)
+        {
+          auto new_base = current->base + (count * kapi::memory::page::size);
+          auto split_node = make_node(new_base, current->page_count - count, std::move(current->next), current, true);
+
+          if (current->next)
+          {
+            current->next->previous = split_node;
+          }
+          current->next = split_node;
+          current->page_count = count;
+        }
+
+        current->is_free = false;
+        return current->base;
+      }
+      current = current->next;
+    }
+
+    kapi::system::panic("[OS:MEM] MMIO alloctor out of memory!");
+    return {};
+  }
+
+  auto mmio_allocator::release(kapi::memory::linear_address base) -> void
+  {
+    auto current = m_head;
+
+    while (current)
+    {
+      if (current->base == base && !current->is_free)
+      {
+        current->is_free = true;
+
+        if (current->next && current->next->is_free)
+        {
+          auto removed = current->next;
+          current->page_count += removed->page_count;
+          current->next = removed->next;
+          if (current->next)
+          {
+            current->next->previous = current;
+          }
+          destroy_node(removed);
+        }
+
+        if (current->previous && current->previous->is_free)
+        {
+          auto removed = current;
+          removed->previous->page_count += removed->page_count;
+          removed->previous->next = removed->next;
+          if (removed->next)
+          {
+            removed->next->previous = removed->previous;
+          }
+          destroy_node(removed);
+        }
+        return;
+      }
+      current = current->next;
+    }
+  }
+
+  auto mmio_allocator::make_node(kapi::memory::linear_address base, std::size_t page_count, node * next,
+                                 node * previous, bool is_free) -> node *
+  {
+    using traits = std::allocator_traits<kstd::allocator<node>>;
+
+    auto new_node = traits::allocate(m_allocator, 1);
+    traits::construct(m_allocator, new_node, base, page_count, next, previous, is_free);
+    return new_node;
+  }
+
+  auto mmio_allocator::destroy_node(node * instance) -> void
+  {
+    using traits = std::allocator_traits<kstd::allocator<node>>;
+
+    traits::destroy(m_allocator, instance);
+    traits::deallocate(m_allocator, instance, 1);
+  }
+
+}  // namespace kernel::memory
diff --git a/kernel/src/memory/operators.cpp b/kernel/src/memory/operators.cpp
index 57e31e6..5673d68 100644
--- a/kernel/src/memory/operators.cpp
+++ b/kernel/src/memory/operators.cpp
@@ -1,6 +1,8 @@
-#include "kapi/system.hpp"
+#include <kernel/memory.hpp>
 
-#include "kernel/memory.hpp"
+#include <kapi/system.hpp>
+
+#include <kstd/units>
 
 #include <cstddef>
 #include <new>
@@ -8,7 +10,8 @@
 [[nodiscard]] auto operator new(std::size_t size, std::align_val_t alignment, std::nothrow_t const &) noexcept -> void *
 {
   auto & allocator = kernel::memory::get_heap_allocator();
-  return allocator.allocate(size, alignment);
+  return allocator.allocate(static_cast<kstd::units::bytes>(size),
+                            static_cast<kstd::units::bytes>(static_cast<std::size_t>(alignment)));
 }
 
 [[nodiscard]] auto operator new(std::size_t size, std::align_val_t alignment) -> void *
@@ -73,9 +76,9 @@ auto operator delete(void * pointer, std::align_val_t) noexcept -> void
   ::operator delete(pointer);
 }
 
-auto operator delete(void * pointer, std::size_t, std::align_val_t) noexcept -> void
+auto operator delete(void * pointer, std::size_t size, std::align_val_t) noexcept -> void
 {
-  ::operator delete(pointer);
+  ::operator delete(pointer, size);
 }
 
 auto operator delete[](void * pointer) noexcept -> void
@@ -83,9 +86,9 @@ auto operator delete[](void * pointer) noexcept -> void
   ::operator delete(pointer);
 }
 
-auto operator delete[](void * pointer, std::size_t) noexcept -> void
+auto operator delete[](void * pointer, std::size_t size) noexcept -> void
 {
-  ::operator delete(pointer);
+  ::operator delete(pointer, size);
 }
 
 auto operator delete[](void * pointer, std::align_val_t) noexcept -> void
@@ -93,7 +96,7 @@ auto operator delete[](void * pointer, std::align_val_t) noexcept -> void
   ::operator delete(pointer);
 }
 
-auto operator delete[](void * pointer, std::size_t, std::align_val_t) noexcept -> void
+auto operator delete[](void * pointer, std::size_t size, std::align_val_t) noexcept -> void
 {
-  ::operator delete(pointer);
+  ::operator delete(pointer, size);
 }