diff options
| -rw-r--r-- | arch/x86_64/include/x86_64/memory/buffered_allocator.hpp | 97 | ||||
| -rw-r--r-- | arch/x86_64/include/x86_64/memory/region_allocator.hpp | 9 | ||||
| -rw-r--r-- | arch/x86_64/src/memory/region_allocator.cpp | 33 | ||||
| -rw-r--r-- | kapi/include/kapi/memory.hpp | 9 | ||||
| -rw-r--r-- | kapi/include/kapi/memory/frame_allocator.hpp | 24 | ||||
| -rw-r--r-- | kernel/src/kapi/memory.cpp | 13 |
6 files changed, 153 insertions, 32 deletions
diff --git a/arch/x86_64/include/x86_64/memory/buffered_allocator.hpp b/arch/x86_64/include/x86_64/memory/buffered_allocator.hpp index 90ac878..fa3b5cb 100644 --- a/arch/x86_64/include/x86_64/memory/buffered_allocator.hpp +++ b/arch/x86_64/include/x86_64/memory/buffered_allocator.hpp @@ -2,11 +2,13 @@ #define TEACHOS_X86_64_BUFFERED_ALLOCATOR_HPP #include "kapi/memory.hpp" +#include "kapi/system.hpp" #include <algorithm> #include <array> #include <cstddef> #include <optional> +#include <utility> namespace teachos::memory::x86_64 { @@ -16,8 +18,15 @@ namespace teachos::memory::x86_64 { explicit buffered_allocator(frame_allocator * underlying) : m_underlying{underlying} + , m_free{BufferSize} { - std::ranges::generate(m_pool, [this] { return m_underlying->allocate(); }); + auto from_underlying = m_underlying->allocate_many(BufferSize); + if (!from_underlying) + { + system::panic("[x86_64:MEM] Not enough frames available from underlying allocator."); + } + auto [first_frame, count] = *from_underlying; + std::ranges::generate_n(m_pool.begin(), count, [first_frame]() mutable { return first_frame++; }); } buffered_allocator(buffered_allocator const &) = delete; @@ -28,7 +37,7 @@ namespace teachos::memory::x86_64 std::ranges::for_each(m_pool, [this](auto const & maybe_frame) { if (maybe_frame) { - m_underlying->release(*maybe_frame); + m_underlying->release_many({*maybe_frame, 1}); } }); } @@ -36,30 +45,90 @@ namespace teachos::memory::x86_64 auto operator=(buffered_allocator const &) = delete; auto operator=(buffered_allocator &&) = delete; - auto allocate() noexcept -> std::optional<frame> override + auto allocate_many(std::size_t count = 1) noexcept -> std::optional<std::pair<frame, std::size_t>> override { - auto found = std::ranges::find_if(m_pool, [](auto const & candidate) { return candidate.has_value(); }); - if (found == std::end(m_pool)) + if (count > m_free) + { + return m_underlying->allocate_many(count); + } + + auto start_of_set = std::ranges::find_if(m_pool, [](auto const & candidate) { return candidate.has_value(); }); + if (start_of_set == m_pool.end()) + { + return m_underlying->allocate_many(count); + } + + if (std::distance(start_of_set, m_pool.end()) < static_cast<std::ptrdiff_t>(count)) + { + return m_underlying->allocate_many(count); + } + + auto number_of_consecutive_frames = 1uz; + for (auto current = std::next(start_of_set); current != m_pool.end() && number_of_consecutive_frames < count; + ++current) + { + if (*current && *start_of_set && **current == (**start_of_set) + 1) + { + ++number_of_consecutive_frames; + continue; + } + number_of_consecutive_frames = 0; + start_of_set = current; + } + + if (std::distance(start_of_set, m_pool.end()) >= static_cast<std::ptrdiff_t>(count)) { - return m_underlying->allocate(); + auto result = std::make_pair(**start_of_set, count); + m_free -= count; + std::ranges::for_each(start_of_set, start_of_set + count, [](auto & frame) { frame.reset(); }); + sort_pool(); + return result; } - auto frame = found->value(); - found->reset(); - return frame; + return m_underlying->allocate_many(count); } - auto release(frame frame) -> void override + auto release_many(std::pair<frame, std::size_t> frame_set) -> void override { - auto found = std::ranges::find_if(m_pool, [](auto const & candidate) { return !candidate; }); - if (found == std::end(m_pool)) + if (m_free == BufferSize) { - return m_underlying->release(frame); + return m_underlying->release_many(frame_set); + } + + auto [first_frame, count] = frame_set; + auto start_of_set = std::ranges::find_if(m_pool, [](auto const & candidate) { return !candidate.has_value(); }); + + for (auto current = start_of_set; current != m_pool.end() && count; ++current) + { + *current = first_frame++; + ++m_free; + --count; + } + sort_pool(); + + if (count) + { + m_underlying->release_many({first_frame, count}); } - (*found) = frame; } private: + auto sort_pool() -> void + { + std::ranges::sort(m_pool, [](auto lhs, auto rhs) -> bool { + if (lhs && rhs) + { + return *lhs < *rhs; + } + if (!lhs) + { + return false; + } + return true; + }); + } + frame_allocator * m_underlying; + std::size_t m_free; std::array<std::optional<frame>, BufferSize> m_pool{}; }; diff --git a/arch/x86_64/include/x86_64/memory/region_allocator.hpp b/arch/x86_64/include/x86_64/memory/region_allocator.hpp index bf657a0..4063bcc 100644 --- a/arch/x86_64/include/x86_64/memory/region_allocator.hpp +++ b/arch/x86_64/include/x86_64/memory/region_allocator.hpp @@ -7,6 +7,7 @@ #include <multiboot2/information.hpp> +#include <cstddef> #include <optional> #include <utility> @@ -50,16 +51,16 @@ namespace teachos::memory::x86_64 //! @param information The description of the detected memory regions as well as regions that are already occupied. explicit region_allocator(memory_information const & information); - //! @copydoc frame_allocator::allocate + //! @copydoc frame_allocator::allocate_many //! //! @note As long as free frames are available, successive calls to this implementation are guaranteed to yield //! frames in ascending order. - auto allocate() noexcept -> std::optional<frame> override; + auto allocate_many(std::size_t count = 1) noexcept -> std::optional<std::pair<frame, std::size_t>> override; - //! @copydoc frame_allocator::release + //! @copydoc frame_allocator::release_many //! //! @note This implementation will never actually release any frames. - auto release(frame frame) -> void override; + auto release_many(std::pair<frame, std::size_t> frame_set) -> void override; auto next_free_frame() noexcept -> std::optional<frame>; diff --git a/arch/x86_64/src/memory/region_allocator.cpp b/arch/x86_64/src/memory/region_allocator.cpp index efa1f4a..7a8fb8b 100644 --- a/arch/x86_64/src/memory/region_allocator.cpp +++ b/arch/x86_64/src/memory/region_allocator.cpp @@ -6,6 +6,7 @@ #include <multiboot2/information.hpp> #include <algorithm> +#include <cstddef> #include <optional> #include <ranges> #include <utility> @@ -56,7 +57,7 @@ namespace teachos::memory::x86_64 m_current_region = *lowest_region; if (auto start_of_region = frame::containing(physical_address{m_current_region->base}); - start_of_region < m_next_frame) + start_of_region > m_next_frame) { m_next_frame = start_of_region; } @@ -96,16 +97,32 @@ namespace teachos::memory::x86_64 return m_current_region.transform([this](auto) -> auto { return m_next_frame; }); } - auto region_allocator::allocate() noexcept -> std::optional<frame> + auto region_allocator::allocate_many(std::size_t count) noexcept -> std::optional<std::pair<frame, std::size_t>> { - return find_next_frame().transform([this](auto frame) -> auto { - auto result = frame; - ++m_next_frame; - return result; - }); + while (m_current_region) + { + auto result = find_next_frame(); + + if (result) + { + auto region_end = last_frame(*m_current_region); + if ((region_end.number() - result->number()) >= count) + { + m_next_frame = m_next_frame + count; + return std::make_pair(*result, count); + } + else + { + m_next_frame = region_end + 1; + choose_next_region(); + } + } + } + + return std::nullopt; } - auto region_allocator::release(frame) -> void {} + auto region_allocator::release_many(std::pair<frame, std::size_t>) -> void {} auto region_allocator::next_free_frame() noexcept -> std::optional<frame> { diff --git a/kapi/include/kapi/memory.hpp b/kapi/include/kapi/memory.hpp index da666da..c2e9df8 100644 --- a/kapi/include/kapi/memory.hpp +++ b/kapi/include/kapi/memory.hpp @@ -10,6 +10,7 @@ #include <cstddef> #include <optional> +#include <utility> namespace teachos::memory { @@ -46,6 +47,14 @@ namespace teachos::memory auto allocate_frame() -> std::optional<frame>; //! @qualifier kernel-defined + //! Allocate multiple new frames of physical memory + //! + //! @warning This function will panic if no frame allocator has been registered. + //! + //! @return An engaged std::optional iff. @p count frames could be allocated, std::nullopt otherwise. + auto allocate_many_frames(std::size_t count) -> std::optional<std::pair<frame, std::size_t>>; + + //! @qualifier kernel-defined //! Map a page onto a frame. //! //! @warning This function will panic if no page mapper has been registered, or the page has already been mapped. diff --git a/kapi/include/kapi/memory/frame_allocator.hpp b/kapi/include/kapi/memory/frame_allocator.hpp index fb6bc0d..8532a45 100644 --- a/kapi/include/kapi/memory/frame_allocator.hpp +++ b/kapi/include/kapi/memory/frame_allocator.hpp @@ -5,7 +5,9 @@ #include "kapi/memory/frame.hpp" +#include <cstddef> #include <optional> +#include <utility> namespace teachos::memory { @@ -27,12 +29,30 @@ namespace teachos::memory //! Allocate a frame of physical memory. //! //! @return An engaged std::optional iff. a new frame could be allocated, std::nullopt otherwise. - virtual auto allocate() noexcept -> std::optional<frame> = 0; + virtual auto allocate() noexcept -> std::optional<frame> + { + return allocate_many(1).transform([](auto result) { return result.first; }); + } + + //! Allocate multiple consecutive frames of physical memory. + //! + //! @param count The number of frames to allocate + //! @return an engaged optional iff. a block of consecutive frames could be allocated, std::nullopt otherwise. + virtual auto allocate_many(std::size_t count) noexcept -> std::optional<std::pair<frame, std::size_t>> = 0; //! Release a frame of physical memory. //! //! @param frame A frame of physical memory, previously acquired by a call to the #allocate function. - virtual auto release(frame frame) -> void = 0; + virtual auto release(frame frame) -> void + { + return release_many({frame, 1}); + } + + //! Release a frame of physical memory. + //! + //! @param frame_set A set of frames of physical memory, previously acquired by a call to the #allocate_many + //! function. + virtual auto release_many(std::pair<frame, std::size_t> frame_set) -> void = 0; protected: frame_allocator() = default; diff --git a/kernel/src/kapi/memory.cpp b/kernel/src/kapi/memory.cpp index 2f707ec..ebd4c15 100644 --- a/kernel/src/kapi/memory.cpp +++ b/kernel/src/kapi/memory.cpp @@ -15,14 +15,14 @@ namespace teachos::memory { bad_frame_allocator static instance; - auto allocate() noexcept -> std::optional<frame> override + auto allocate_many(std::size_t) noexcept -> std::optional<std::pair<frame, std::size_t>> override { - system::panic("Tried to allocate a frame without an active allocator."); + system::panic("Tried to allocate frames without an active allocator."); } - auto release(frame) -> void override + auto release_many(std::pair<frame, std::size_t>) -> void override { - system::panic("Tried to release a frame without an active allocator."); + system::panic("Tried to release frames without an active allocator."); } }; @@ -76,6 +76,11 @@ namespace teachos::memory return active_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); + } + auto map(page page, frame frame) -> std::byte * { return active_page_mapper->map(page, frame, page_mapper::flags::empty); |