From e284d574ed9237a215d994861cc502452fec11ce Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Fri, 13 Mar 2026 22:28:50 +0100 Subject: kernel/memory: implement basic bitmap allocator --- kernel/CMakeLists.txt | 1 + kernel/include/kernel/memory/bitmap_allocator.hpp | 56 ++++++++++++ kernel/kapi/memory.cpp | 56 +++++++++++- kernel/src/memory/bitmap_allocator.cpp | 100 ++++++++++++++++++++++ 4 files changed, 210 insertions(+), 3 deletions(-) create mode 100644 kernel/include/kernel/memory/bitmap_allocator.hpp create mode 100644 kernel/src/memory/bitmap_allocator.cpp (limited to 'kernel') diff --git a/kernel/CMakeLists.txt b/kernel/CMakeLists.txt index 97a0267..ae2325a 100644 --- a/kernel/CMakeLists.txt +++ b/kernel/CMakeLists.txt @@ -10,6 +10,7 @@ add_executable("kernel" # Kernel Implementation "src/main.cpp" + "src/memory/bitmap_allocator.cpp" ) target_include_directories("kernel" PRIVATE diff --git a/kernel/include/kernel/memory/bitmap_allocator.hpp b/kernel/include/kernel/memory/bitmap_allocator.hpp new file mode 100644 index 0000000..fb5bf55 --- /dev/null +++ b/kernel/include/kernel/memory/bitmap_allocator.hpp @@ -0,0 +1,56 @@ +#ifndef TEACHOS_KERNEL_MEMORY_BITMAP_ALLOCATOR_HPP +#define TEACHOS_KERNEL_MEMORY_BITMAP_ALLOCATOR_HPP + +#include "kapi/memory.hpp" + +#include +#include +#include +#include +#include + +namespace kernel::memory +{ + + //! A generic, bitmap base frame allocator. + //! + //! This frame allocator manages the allocation state of each frame present in the system using a single bit per + //! frame. All state information is stored in a contiguous region of memory. + struct bitmap_frame_allocator final : kapi::memory::frame_allocator + { + //! Construct a new, empty bitmap allocator. + //! + //! @param storage A contiguous region of virtual memory for state storage. + //! @param total_frame The total number of frames in the system. + bitmap_frame_allocator(std::span storage, std::size_t frame_count) noexcept; + + bitmap_frame_allocator(bitmap_frame_allocator const &) = delete; + bitmap_frame_allocator(bitmap_frame_allocator &&) = delete; + auto operator=(bitmap_frame_allocator const &) -> bitmap_frame_allocator & = delete; + auto operator=(bitmap_frame_allocator &&) -> bitmap_frame_allocator & = delete; + + //! @copydoc kapi::memory::frame_allocator::allocate_many + [[nodiscard]] auto allocate_many(std::size_t count = 1) noexcept + -> std::optional> override; + + //! @copydoc kapi::memory::frame_allocator::release_many + auto release_many(std::pair frame_set) -> void override; + + //! Mark a given frame as being used. + //! + //! This function is used during bootstrap to hand the platform allocator state over to this allocator. + auto mark_used(kapi::memory::frame frame) -> void override; + + private: + [[nodiscard]] auto test(std::size_t index) const noexcept -> bool; + auto set(std::size_t index) noexcept -> void; + auto clear(std::size_t index) noexcept -> void; + + std::span m_bitmap; + std::uint64_t m_frame_count; + std::uint64_t m_last_index; + }; + +} // namespace kernel::memory + +#endif diff --git a/kernel/kapi/memory.cpp b/kernel/kapi/memory.cpp index 7c9b1da..1699cd3 100644 --- a/kernel/kapi/memory.cpp +++ b/kernel/kapi/memory.cpp @@ -2,8 +2,17 @@ #include "kapi/system.hpp" +#include "kernel/memory/bitmap_allocator.hpp" + +#include + +#include +#include #include +#include #include +#include +#include #include namespace kapi::memory @@ -20,6 +29,11 @@ namespace kapi::memory system::panic("Tried to allocate frames without an active allocator."); } + auto mark_used(frame) -> void override + { + system::panic("Tried to mark frame as used without an active allocator."); + } + auto release_many(std::pair) -> void override { system::panic("Tried to release frames without an active allocator."); @@ -48,11 +62,17 @@ namespace kapi::memory constinit bad_frame_allocator bad_frame_allocator::instance{}; constinit bad_page_mapper bad_page_mapper::instance{}; + auto constinit allocator = std::optional{}; } // namespace constinit auto static active_frame_allocator = static_cast(&bad_frame_allocator::instance); constinit auto static active_page_mapper = static_cast(&bad_page_mapper::instance); + auto get_frame_allocator() -> frame_allocator & + { + return *active_frame_allocator; + } + auto set_frame_allocator(frame_allocator & allocator) -> std::optional { if (&allocator == active_frame_allocator) @@ -73,12 +93,12 @@ namespace kapi::memory auto allocate_frame() -> std::optional { - return active_frame_allocator->allocate(); + return get_frame_allocator().allocate(); } auto allocate_many_frames(std::size_t count) -> std::optional> { - return active_frame_allocator->allocate_many(count); + return get_frame_allocator().allocate_many(count); } auto map(page page, frame frame) -> std::byte * @@ -91,4 +111,34 @@ namespace kapi::memory return active_page_mapper->unmap(page); } -} // namespace kapi::memory \ No newline at end of file + auto init_pmm(std::size_t frame_count, void (&handoff_handler)(frame_allocator &)) -> void + { + auto const bitmap_bytes = (frame_count + 7uz) / 8uz; + auto const bitmap_pages = (bitmap_bytes + page::size - 1uz) / page::size; + + auto const bitmap_frames = allocate_many_frames(bitmap_pages); + if (!bitmap_frames) + { + system::panic("[OS:MEM] Not enough memory for bitmap allocator!"); + } + + auto const base_address = 0xffff'c000'0000'0000uz; + auto const flags = page_mapper::flags::writable | page_mapper::flags::supervisor_only; + + std::ranges::for_each(std::views::iota(0uz, bitmap_pages), [&](auto index) { + auto page = page::containing(linear_address{base_address + index * page::size}); + auto frame = memory::frame(bitmap_frames->first.number() + index); + active_page_mapper->map(page, frame, flags); + }); + + auto bitmap_ptr = std::bit_cast(base_address); + auto bitmap = std::span{bitmap_ptr, (bitmap_bytes + sizeof(std::uint64_t) - 1uz) / sizeof(std::uint64_t)}; + + allocator.emplace(bitmap, frame_count); + + handoff_handler(allocator.value()); + set_frame_allocator(allocator.value()); + kstd::println("[OS:MEM] Physical memory manager initialized."); + } + +} // namespace kapi::memory diff --git a/kernel/src/memory/bitmap_allocator.cpp b/kernel/src/memory/bitmap_allocator.cpp new file mode 100644 index 0000000..c010f77 --- /dev/null +++ b/kernel/src/memory/bitmap_allocator.cpp @@ -0,0 +1,100 @@ +#include "kernel/memory/bitmap_allocator.hpp" + +#include "kapi/memory.hpp" + +#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{} + { + std::ranges::fill(m_bitmap, ~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 + { + auto entry_entry = index / 64; + auto entry_offset = index % 64; + 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; + 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; + m_bitmap[entry_entry] &= ~(1uz << entry_offset); + } + +} // namespace kernel::memory \ No newline at end of file -- cgit v1.2.3