From 3012fa5dfe5dfed5e83baf9b40934ed8e8317627 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 3 Jul 2026 09:32:30 +0200 Subject: kernel: rearrange sources according to p1204 --- kernel/src/memory/bitmap_allocator.cpp | 106 --------- kernel/src/memory/bitmap_allocator.tests.cpp | 288 ----------------------- kernel/src/memory/block_list_allocator.cpp | 215 ----------------- kernel/src/memory/block_list_allocator.tests.cpp | 85 ------- kernel/src/memory/mmio_allocator.cpp | 111 --------- kernel/src/memory/operators.cpp | 102 -------- 6 files changed, 907 deletions(-) delete mode 100644 kernel/src/memory/bitmap_allocator.cpp delete mode 100644 kernel/src/memory/bitmap_allocator.tests.cpp delete mode 100644 kernel/src/memory/block_list_allocator.cpp delete mode 100644 kernel/src/memory/block_list_allocator.tests.cpp delete mode 100644 kernel/src/memory/mmio_allocator.cpp delete mode 100644 kernel/src/memory/operators.cpp (limited to 'kernel/src/memory') diff --git a/kernel/src/memory/bitmap_allocator.cpp b/kernel/src/memory/bitmap_allocator.cpp deleted file mode 100644 index 240e2afe..00000000 --- a/kernel/src/memory/bitmap_allocator.cpp +++ /dev/null @@ -1,106 +0,0 @@ -#include - -#include - -#include -#include -#include -#include -#include -#include -#include - -namespace kernel::memory -{ - - bitmap_frame_allocator::bitmap_frame_allocator(std::span storage, std::size_t frame_count) noexcept - : m_bitmap{storage} - , m_frame_count{frame_count} - , m_last_index{} - { - 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 - -> std::optional> - { - if (count == 0) - { - return std::nullopt; - } - - auto free_count = 0uz; - auto first_free = 0uz; - - for (auto i = 0uz; i < m_frame_count; ++i) - { - auto const current = (m_last_index + i) % m_frame_count; - if (!test(current)) - { - if (free_count == 0) - { - first_free = current; - } - - ++free_count; - - if (free_count == count) - { - for (auto j = 0uz; j < count; ++j) - { - set(first_free + j); - } - m_last_index = first_free + count; - return std::make_pair(kapi::memory::frame{first_free}, count); - } - } - else - { - free_count = 0; - } - } - - return std::nullopt; - } - - auto bitmap_frame_allocator::release_many(std::pair frame_set) -> void - { - auto const [start, count] = frame_set; - for (auto i = 0uz; i < count; ++i) - { - clear(start.number() + i); - } - } - - auto bitmap_frame_allocator::mark_used(kapi::memory::frame frame) -> void - { - set(frame.number()); - } - - auto bitmap_frame_allocator::test(std::size_t index) const noexcept -> bool - { - 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 - { - 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 - { - 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); - } - -} // namespace kernel::memory \ No newline at end of file diff --git a/kernel/src/memory/bitmap_allocator.tests.cpp b/kernel/src/memory/bitmap_allocator.tests.cpp deleted file mode 100644 index 05d11a33..00000000 --- a/kernel/src/memory/bitmap_allocator.tests.cpp +++ /dev/null @@ -1,288 +0,0 @@ -#include - -#include - -#include -#include -#include - -#include -#include -#include -#include -#include - -constexpr auto all_bits_set = std::numeric_limits::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 deleted file mode 100644 index 6e68ada7..00000000 --- a/kernel/src/memory/block_list_allocator.cpp +++ /dev/null @@ -1,215 +0,0 @@ -#include - -#include - -#include -#include - -#include -#include - -#include -#include -#include -#include - -using namespace kstd::units_literals; - -namespace kernel::memory -{ - - namespace - { - [[nodiscard]] constexpr auto align_up(std::byte * pointer, kstd::units::bytes alignment) noexcept -> std::byte * - { - auto const remainder = std::bit_cast(pointer) % static_cast(alignment); - return remainder == 0 ? pointer : pointer + static_cast(alignment) - remainder; - } - } // namespace - - block_list_allocator::block_list_allocator(kapi::memory::linear_address base) noexcept - : heap_allocator{} - , m_base{base} - , m_frontier{base} - , m_block_list{} - , m_lock{} - {} - - auto block_list_allocator::allocate(kstd::units::bytes size, kstd::units::bytes alignment) noexcept -> void * - { - kstd::lock_guard guard{m_lock}; - - for (auto attempt = 0uz; attempt < 2uz; ++attempt) - { - auto current = m_block_list; - while (current != nullptr) - { - if (current->free) - { - auto const raw_block = reinterpret_cast(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(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(payload_header - raw_block); - - auto payload_block = current; - - if (front_padding >= allocated_metadata_size + minimum_allocation_size) - { - payload_block = reinterpret_cast(payload_header); - std::construct_at(payload_block, current->usable_size - front_padding, true, current->next); - - if (payload_block->next) - { - payload_block->next->prev = payload_block; - } - - current->usable_size = front_padding - allocated_metadata_size; - current->next = payload_block; - payload_block->prev = current; - } - - auto const header_size = - static_cast(aligned_payload - reinterpret_cast(payload_block)); - auto const payload_size = header_size - allocated_metadata_size + size; - split(payload_block, payload_size, 0_B); - - payload_block->free = false; - - auto back_pointer = reinterpret_cast(aligned_payload - sizeof(block_header *)); - *back_pointer = payload_block; - - return reinterpret_cast(aligned_payload); - } - } - current = current->next; - } - - auto const search_size = size + alignment; - if (attempt == 0uz && !expand(search_size)) - { - return nullptr; - } - } - - return nullptr; - } - - auto block_list_allocator::deallocate(void * ptr) noexcept -> void - { - if (!ptr) - { - return; - } - - kstd::lock_guard guard{m_lock}; - - auto const aligned_payload = reinterpret_cast(ptr); - auto back_pointer = reinterpret_cast(aligned_payload - sizeof(block_header *)); - auto block = *back_pointer; - - block->free = true; - coalesce(block); - } - - 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_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; - - for (auto i = 0uz; i < frames_needed; ++i) - { - auto frame = kapi::memory::allocate_frame(); - if (!frame) - { - kapi::system::panic("[OS:Heap] OOM when expanding heap."); - return false; - } - - auto page = kapi::memory::page::containing(m_frontier + i * kapi::memory::page::size); - kapi::memory::map(page, *frame, flags); - } - - auto block = static_cast(m_frontier); - std::construct_at(block, frames_needed * kapi::memory::frame::size - allocated_metadata_size, true, nullptr, - nullptr); - - m_frontier += frames_needed * kapi::memory::frame::size; - - if (!m_block_list) - { - m_block_list = block; - } - else - { - auto current = m_block_list; - while (current->next) - { - current = current->next; - } - current->next = block; - block->prev = current; - } - - coalesce(block); - return true; - } - - auto block_list_allocator::coalesce(block_header * block) noexcept -> void - { - if (block->next && block->next->free) - { - auto follower = block->next; - block->usable_size += follower->usable_size + allocated_metadata_size; - block->next = follower->next; - if (block->next) - { - block->next->prev = block; - } - std::destroy_at(follower); - } - - if (block->prev && block->prev->free) - { - auto leader = block->prev; - leader->usable_size += block->usable_size + allocated_metadata_size; - leader->next = block->next; - if (block->next) - { - block->next->prev = leader; - } - std::destroy_at(block); - } - } - - 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; - - if (block->usable_size > new_block_size + allocated_metadata_size + minimum_allocation_size) - { - auto raw_block = reinterpret_cast(block); - auto new_block = reinterpret_cast(raw_block + allocated_metadata_size + new_block_size); - std::construct_at(new_block, block->usable_size - new_block_size - allocated_metadata_size, true, block->next, - block); - - if (new_block->next) - { - new_block->next->prev = new_block; - } - - block->usable_size = new_block_size; - block->next = new_block; - } - } - -} // namespace kernel::memory \ 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 deleted file mode 100644 index c5f84c52..00000000 --- a/kernel/src/memory/block_list_allocator.tests.cpp +++ /dev/null @@ -1,85 +0,0 @@ -#include - -#include - -#include - -#include - -#include - -#include - -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(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 deleted file mode 100644 index ba23dbde..00000000 --- a/kernel/src/memory/mmio_allocator.cpp +++ /dev/null @@ -1,111 +0,0 @@ -#include - -#include -#include - -#include - -#include -#include -#include - -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>; - - 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>; - - 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 deleted file mode 100644 index 5673d680..00000000 --- a/kernel/src/memory/operators.cpp +++ /dev/null @@ -1,102 +0,0 @@ -#include - -#include - -#include - -#include -#include - -[[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(static_cast(size), - static_cast(static_cast(alignment))); -} - -[[nodiscard]] auto operator new(std::size_t size, std::align_val_t alignment) -> void * -{ - auto pointer = operator new(size, alignment, std::nothrow); - - if (pointer == nullptr) - { - kapi::system::panic("[OS:Heap] Out of memory!"); - } - - return pointer; -} - -[[nodiscard]] auto operator new(std::size_t size, std::nothrow_t const &) noexcept -> void * -{ - return operator new(size, std::align_val_t{__STDCPP_DEFAULT_NEW_ALIGNMENT__}, std::nothrow); -} - -[[nodiscard]] auto operator new(std::size_t size) -> void * -{ - return operator new(size, std::align_val_t{__STDCPP_DEFAULT_NEW_ALIGNMENT__}); -} - -[[nodiscard]] auto operator new[](std::size_t size, std::align_val_t alignment, std::nothrow_t const &) noexcept - -> void * -{ - return operator new(size, alignment, std::nothrow); -} - -[[nodiscard]] auto operator new[](std::size_t size, std::align_val_t alignment) -> void * -{ - return operator new(size, alignment); -} - -[[nodiscard]] auto operator new[](std::size_t size, std::nothrow_t const &) noexcept -> void * -{ - return ::operator new(size); -} - -[[nodiscard]] auto operator new[](std::size_t size) -> void * -{ - return ::operator new(size); -} - -auto operator delete(void * pointer) noexcept -> void -{ - if (pointer != nullptr) - { - auto & allocator = kernel::memory::get_heap_allocator(); - allocator.deallocate(pointer); - } -} - -auto operator delete(void * pointer, std::size_t) noexcept -> void -{ - ::operator delete(pointer); -} - -auto operator delete(void * pointer, std::align_val_t) noexcept -> void -{ - ::operator delete(pointer); -} - -auto operator delete(void * pointer, std::size_t size, std::align_val_t) noexcept -> void -{ - ::operator delete(pointer, size); -} - -auto operator delete[](void * pointer) noexcept -> void -{ - ::operator delete(pointer); -} - -auto operator delete[](void * pointer, std::size_t size) noexcept -> void -{ - ::operator delete(pointer, size); -} - -auto operator delete[](void * pointer, std::align_val_t) noexcept -> void -{ - ::operator delete(pointer); -} - -auto operator delete[](void * pointer, std::size_t size, std::align_val_t) noexcept -> void -{ - ::operator delete(pointer, size); -} -- cgit v1.2.3