diff options
| -rw-r--r-- | arch/x86_64/include/arch/memory/region_allocator.hpp | 3 | ||||
| -rw-r--r-- | arch/x86_64/kapi/memory.cpp | 54 | ||||
| -rw-r--r-- | arch/x86_64/src/memory/region_allocator.cpp | 9 | ||||
| -rw-r--r-- | kapi/include/kapi/memory.hpp | 15 | ||||
| -rw-r--r-- | kapi/include/kapi/memory/buffered_allocator.hpp | 5 | ||||
| -rw-r--r-- | kapi/include/kapi/memory/chunk.hpp | 37 | ||||
| -rw-r--r-- | kapi/include/kapi/memory/frame.hpp | 12 | ||||
| -rw-r--r-- | kapi/include/kapi/memory/frame_allocator.hpp | 3 | ||||
| -rw-r--r-- | kapi/include/kapi/memory/page.hpp | 10 | ||||
| -rw-r--r-- | kernel/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | kernel/include/kernel/memory/bitmap_allocator.hpp | 56 | ||||
| -rw-r--r-- | kernel/kapi/memory.cpp | 56 | ||||
| -rw-r--r-- | kernel/src/memory/bitmap_allocator.cpp | 100 |
13 files changed, 334 insertions, 27 deletions
diff --git a/arch/x86_64/include/arch/memory/region_allocator.hpp b/arch/x86_64/include/arch/memory/region_allocator.hpp index f391293..1c5885e 100644 --- a/arch/x86_64/include/arch/memory/region_allocator.hpp +++ b/arch/x86_64/include/arch/memory/region_allocator.hpp @@ -58,6 +58,9 @@ namespace arch::memory auto allocate_many(std::size_t count = 1) noexcept -> std::optional<std::pair<kapi::memory::frame, std::size_t>> override; + //! @copydoc kapi::memory::frame_allocator::mark_used + auto mark_used(kapi::memory::frame frame) -> void override; + //! @copydoc kapi::memory::frame_allocator::release_many //! //! @note This implementation will never actually release any frames. diff --git a/arch/x86_64/kapi/memory.cpp b/arch/x86_64/kapi/memory.cpp index b71fa17..48aab9f 100644 --- a/arch/x86_64/kapi/memory.cpp +++ b/arch/x86_64/kapi/memory.cpp @@ -18,14 +18,17 @@ #include <kstd/print> +#include <multiboot2/constants.hpp> #include <multiboot2/information.hpp> +#include <algorithm> #include <atomic> #include <bit> #include <cstddef> #include <cstdint> #include <memory> #include <optional> +#include <ranges> #include <span> #include <utility> @@ -37,6 +40,10 @@ namespace kapi::memory constexpr auto static unused_page_address = linear_address{0x0000'7fff'cafe'faceuz}; constexpr auto static recursive_page_map_index = arch::memory::page_table::entry_count - 2; + auto constinit region_based_allocator = std::optional<arch::memory::region_allocator>{}; + auto constinit allocation_buffer = std::optional<buffered_allocator<4>>{}; + auto constinit recursive_page_mapper = std::optional<arch::memory::recursive_page_mapper>{}; + //! Instantiate a basic, memory region based, early frame allocator for remapping. auto collect_memory_information() { @@ -150,9 +157,42 @@ namespace kapi::memory } } - auto constinit region_based_allocator = std::optional<arch::memory::region_allocator>{}; - auto constinit allocation_buffer = std::optional<buffered_allocator<4>>{}; - auto constinit recursive_page_mapper = std::optional<arch::memory::recursive_page_mapper>{}; + auto handoff_to_kernel_pmm(frame_allocator & new_allocator) -> void + { + auto memory_map = boot::bootstrap_information.mbi->memory_map(); + + for (auto const & region : memory_map.regions() | std::views::filter([](auto const & region) { + return region.type == multiboot2::memory_type::available; + })) + { + auto start = frame::containing(physical_address{region.base}); + auto count = region.size_in_B / page::size; + new_allocator.release_many({start, count}); + } + + auto next_free_frame = region_based_allocator->next_free_frame(); + if (!next_free_frame) + { + system::panic("[x86_64:MEM] No more free memory!"); + } + + std::ranges::for_each(std::views::iota(kapi::memory::frame{}, *next_free_frame), + [&](auto frame) { new_allocator.mark_used(frame); }); + + auto image_start = frame::containing(physical_address{&arch::boot::_start_physical}); + auto image_end = frame::containing(physical_address{&arch::boot::_end_physical}) + 1; + + std::ranges::for_each(std::views::iota(image_start, image_end), + [&](auto frame) { new_allocator.mark_used(frame); }); + + auto mbi_base = std::bit_cast<std::uintptr_t>(boot::bootstrap_information.mbi); + auto mbi_size = boot::bootstrap_information.mbi->size_bytes(); + auto mbi_address = physical_address{mbi_base & ~std::bit_cast<std::uintptr_t>(&arch::boot::TEACHOS_VMA)}; + auto mbi_start = frame::containing(mbi_address); + auto mbi_end = frame::containing(physical_address{mbi_address.raw() + mbi_size}) + 1; + + std::ranges::for_each(std::views::iota(mbi_start, mbi_end), [&](auto frame) { new_allocator.mark_used(frame); }); + } } // namespace @@ -189,6 +229,14 @@ namespace kapi::memory set_frame_allocator(*allocation_buffer); set_page_mapper(*recursive_page_mapper); + + auto memory_map = boot::bootstrap_information.mbi->memory_map(); + auto highest_byte = std::ranges::max(std::views::transform( + std::views::filter(memory_map.regions(), + [](auto const & region) { return region.type == multiboot2::memory_type::available; }), + [](auto const & region) { return region.base + region.size_in_B; })); + + init_pmm(frame::containing(physical_address{highest_byte}).number() + 1, handoff_to_kernel_pmm); } } // namespace kapi::memory diff --git a/arch/x86_64/src/memory/region_allocator.cpp b/arch/x86_64/src/memory/region_allocator.cpp index a2dfd48..36902ad 100644 --- a/arch/x86_64/src/memory/region_allocator.cpp +++ b/arch/x86_64/src/memory/region_allocator.cpp @@ -124,6 +124,15 @@ namespace arch::memory return std::nullopt; } + auto region_allocator::mark_used(kapi::memory::frame frame) -> void + { + if (frame < m_next_frame) + { + m_next_frame = frame; + find_next_frame(); + } + } + auto region_allocator::release_many(std::pair<kapi::memory::frame, std::size_t>) -> void {} auto region_allocator::next_free_frame() noexcept -> std::optional<kapi::memory::frame> diff --git a/kapi/include/kapi/memory.hpp b/kapi/include/kapi/memory.hpp index 87268ff..3a8f42d 100644 --- a/kapi/include/kapi/memory.hpp +++ b/kapi/include/kapi/memory.hpp @@ -25,6 +25,21 @@ namespace kapi::memory auto init() -> void; //! @qualifier kernel-defined + //! Initialize the physical memory manager. + //! + //! This function initializes the kernel-wide physical memory manager. The function will invoke the handoff handler to + //! transfer the platform-specific frame allocation state to the physical memory manager. + //! + //! @param frame_count The number of frames present in the system. + //! @param handoff_handler A function to be invoked to transfer the platform-specific frame allocation state. The + //! allocator to hand off to is passed to the handler. + auto init_pmm(std::size_t frame_count, void (&handoff_handler)(frame_allocator &)) -> void; + + //! @qualifier kernel-defined + //! Get the currently active frame allocator. + auto get_frame_allocator() -> frame_allocator &; + + //! @qualifier kernel-defined //! Set the currently active frame allocator. //! //! @param allocator A new frame allocator. diff --git a/kapi/include/kapi/memory/buffered_allocator.hpp b/kapi/include/kapi/memory/buffered_allocator.hpp index 49137c6..286c841 100644 --- a/kapi/include/kapi/memory/buffered_allocator.hpp +++ b/kapi/include/kapi/memory/buffered_allocator.hpp @@ -88,6 +88,11 @@ namespace kapi::memory return m_underlying->allocate_many(count); } + auto mark_used(kapi::memory::frame) -> void override + { + system::panic("[x86_64:MEM] Not implemented"); + } + auto release_many(std::pair<kapi::memory::frame, std::size_t> frame_set) -> void override { if (m_free == BufferSize) diff --git a/kapi/include/kapi/memory/chunk.hpp b/kapi/include/kapi/memory/chunk.hpp index dd97a58..3d90326 100644 --- a/kapi/include/kapi/memory/chunk.hpp +++ b/kapi/include/kapi/memory/chunk.hpp @@ -12,9 +12,10 @@ namespace kapi::memory //! @qualifier kernel-defined //! A fixed-size unit of memory, indexed by a number. //! + //! @tparam ChunkType The CRTP type of the deriving class //! @tparam AddressType The type of addresses used to index this chunk //! @tparam Size The size of this chunk. - template<typename AddressType, std::size_t Size> + template<typename ChunkType, typename AddressType, std::size_t Size> struct chunk { //! The type of addresses used to index this chunk @@ -23,21 +24,13 @@ namespace kapi::memory //! The size of this chunk constexpr auto static size = Size; - //! Construct a handle referencing the first chunk of the respective address space. - constexpr chunk() noexcept = default; - - //! Construct a handle referencing the chunk of memory with the given number. - explicit constexpr chunk(std::size_t number) noexcept - : m_number{number} - {} - //! Construct a new chunk handle for the chunk containing the given address. //! //! @param address An address contained by the desired chunk. //! @return A handle to a chunk containing the given address. - constexpr auto static containing(address_type address) noexcept -> chunk + constexpr auto static containing(address_type address) noexcept -> ChunkType { - return chunk{address.raw() / size}; + return ChunkType{address.raw() / size}; } //! Get the start address of the chunk referenced by this handle. @@ -60,17 +53,17 @@ namespace kapi::memory //! //! @param n The positive offset to this chunk. //! @return A handle referencing the chunk n chunks after the one referenced by this handle. - constexpr auto operator+(std::size_t n) const noexcept -> chunk + constexpr auto operator+(std::size_t n) const noexcept -> ChunkType { - return chunk{m_number + n}; + return ChunkType{m_number + n}; } //! Let this handle reference the next chunk after the currently reference one. //! //! @return A handle referencing the same chunk as this handle did before the operation. - constexpr auto operator++(int) noexcept -> chunk + constexpr auto operator++(int) noexcept -> ChunkType { - auto copy = *this; + auto copy = static_cast<ChunkType>(*this); ++*this; return copy; } @@ -78,10 +71,10 @@ namespace kapi::memory //! Let this handle reference the next chunk after the currently reference one. //! //! @return A reference to this handle. - constexpr auto operator++() noexcept -> chunk & + constexpr auto operator++() noexcept -> ChunkType & { ++m_number; - return *this; + return static_cast<ChunkType &>(*this); } //! Check if this chunk handle reference the same chunk as another one. @@ -95,6 +88,16 @@ namespace kapi::memory constexpr auto operator<=>(chunk const & other) const noexcept -> std::strong_ordering = default; private: + friend ChunkType; + + //! Construct a handle referencing the first chunk of the respective address space. + constexpr chunk() noexcept = default; + + //! Construct a handle referencing the chunk of memory with the given number. + explicit constexpr chunk(std::size_t number) noexcept + : m_number{number} + {} + //! The number of the currently referenced chunk. std::size_t m_number{}; }; diff --git a/kapi/include/kapi/memory/frame.hpp b/kapi/include/kapi/memory/frame.hpp index e7b0832..deab300 100644 --- a/kapi/include/kapi/memory/frame.hpp +++ b/kapi/include/kapi/memory/frame.hpp @@ -6,6 +6,8 @@ #include "kapi/memory/address.hpp" #include "kapi/memory/chunk.hpp" +#include <cstddef> + namespace kapi::memory { @@ -13,9 +15,15 @@ namespace kapi::memory //! A handle to a frame of physical memory. //! //! @note Contrary to the address types, this type is modeled using inheritance to support future extensions. - struct frame : chunk<physical_address, PLATFORM_FRAME_SIZE> + struct frame : chunk<frame, physical_address, PLATFORM_FRAME_SIZE> { - using chunk::chunk; + frame() = default; + + frame(std::size_t number) + : chunk{number} + {} + + using difference_type = std::ptrdiff_t; //! @copydoc chunk::containing //! diff --git a/kapi/include/kapi/memory/frame_allocator.hpp b/kapi/include/kapi/memory/frame_allocator.hpp index 6ed114c..cfa8a1c 100644 --- a/kapi/include/kapi/memory/frame_allocator.hpp +++ b/kapi/include/kapi/memory/frame_allocator.hpp @@ -34,6 +34,9 @@ namespace kapi::memory return allocate_many(1).transform([](auto result) { return result.first; }); } + //! Mark the given frame as used + virtual auto mark_used(frame frame) -> void = 0; + //! Allocate multiple consecutive frames of physical memory. //! //! @param count The number of frames to allocate diff --git a/kapi/include/kapi/memory/page.hpp b/kapi/include/kapi/memory/page.hpp index 55d6e75..f209278 100644 --- a/kapi/include/kapi/memory/page.hpp +++ b/kapi/include/kapi/memory/page.hpp @@ -6,6 +6,8 @@ #include "kapi/memory/address.hpp" #include "kapi/memory/chunk.hpp" +#include <cstddef> + namespace kapi::memory { @@ -13,9 +15,13 @@ namespace kapi::memory //! A handle to a page of virtual memory. //! //! @note Contrary to the address types, this type is modeled using inheritance to support future extensions. - struct page : chunk<linear_address, PLATFORM_PAGE_SIZE> + struct page : chunk<page, linear_address, PLATFORM_PAGE_SIZE> { - using chunk::chunk; + page() = default; + + page(std::size_t number) + : chunk{number} + {} //! @copydoc chunk::containing //! 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 <cstddef> +#include <cstdint> +#include <optional> +#include <span> +#include <utility> + +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<std::uint64_t> 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<std::pair<kapi::memory::frame, std::size_t>> override; + + //! @copydoc kapi::memory::frame_allocator::release_many + auto release_many(std::pair<kapi::memory::frame, std::size_t> 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<std::uint64_t> 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 <kstd/print> + +#include <algorithm> +#include <bit> #include <cstddef> +#include <cstdint> #include <optional> +#include <ranges> +#include <span> #include <utility> 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<frame, std::size_t>) -> 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<kernel::memory::bitmap_frame_allocator>{}; } // namespace constinit auto static active_frame_allocator = static_cast<frame_allocator *>(&bad_frame_allocator::instance); constinit auto static active_page_mapper = static_cast<page_mapper *>(&bad_page_mapper::instance); + auto get_frame_allocator() -> frame_allocator & + { + return *active_frame_allocator; + } + auto set_frame_allocator(frame_allocator & allocator) -> std::optional<frame_allocator *> { if (&allocator == active_frame_allocator) @@ -73,12 +93,12 @@ namespace kapi::memory auto allocate_frame() -> std::optional<frame> { - return active_frame_allocator->allocate(); + return get_frame_allocator().allocate(); } auto allocate_many_frames(std::size_t count) -> std::optional<std::pair<frame, std::size_t>> { - 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<std::uint64_t *>(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 <algorithm> +#include <cstddef> +#include <cstdint> +#include <optional> +#include <span> +#include <utility> + +namespace kernel::memory +{ + + bitmap_frame_allocator::bitmap_frame_allocator(std::span<std::uint64_t> 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<std::pair<kapi::memory::frame, std::size_t>> + { + 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<kapi::memory::frame, std::size_t> 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 |