From 8773024d1b4e756fe5d3494479247c64c7ad8491 Mon Sep 17 00:00:00 2001 From: Fabian Imhof Date: Tue, 8 Oct 2024 09:51:26 +0000 Subject: begin implementing frame allocator --- .../x86_64/include/arch/memory/frame_allocator.hpp | 72 +++++++++++++++++----- arch/x86_64/src/memory/frame_allocator.cpp | 70 ++++++++++++++++++++- 2 files changed, 126 insertions(+), 16 deletions(-) (limited to 'arch') diff --git a/arch/x86_64/include/arch/memory/frame_allocator.hpp b/arch/x86_64/include/arch/memory/frame_allocator.hpp index 8dee848..35d7360 100644 --- a/arch/x86_64/include/arch/memory/frame_allocator.hpp +++ b/arch/x86_64/include/arch/memory/frame_allocator.hpp @@ -1,6 +1,7 @@ #ifndef TEACHOS_ARCH_X86_64_MEMORY_FRAME_HPP #define TEACHOS_ARCH_X86_64_MEMORY_FRAME_HPP +#include "multiboot.hpp" #include #include @@ -8,20 +9,26 @@ namespace teachos::arch::memory { namespace { - const size_t PAGE_FRAME_SIZE = 4096U; + const std::size_t PAGE_FRAME_SIZE = 4096U; } struct frame { - size_t frame_number; + std::size_t frame_number; - frame(size_t frame_number) + frame(std::size_t frame_number) : frame_number(frame_number) { // Nothing to do } - auto containing_address(size_t address) -> frame { return frame{address / PAGE_FRAME_SIZE}; } + static auto containing_address(std::size_t address) -> frame { return frame{address / PAGE_FRAME_SIZE}; } + + constexpr bool operator==(const frame & other) const noexcept { return frame_number == other.frame_number; } + constexpr bool operator>(const frame & other) const noexcept { return frame_number > other.frame_number; } + constexpr bool operator<(const frame & other) const noexcept { return frame_number < other.frame_number; } + constexpr bool operator>=(const frame & other) const noexcept { return frame_number >= other.frame_number; } + constexpr bool operator<=(const frame & other) const noexcept { return frame_number <= other.frame_number; } }; struct frame_allocator @@ -30,18 +37,53 @@ namespace teachos::arch::memory virtual auto deallocate_frame(frame frame) -> void = 0; }; - struct area_frame_allocator : public frame_allocator + // TODO: FIX CONCEPT USAGE + // template + // concept FrameAllocator = requires(T t) { + // { t.allocate_frame() } -> std::optional; + // { t.deallocate_frame() } -> void; + // }; + + // template + struct area_frame_allocator : frame_allocator { - frame next_free_frame; - // std::optional current_area; - // memory_area * areas; - frame kernel_start; - frame kernel_end; - frame multiboot_start; - frame multiboot_end; - - auto allocate_frame() -> std::optional override; - auto deallocate_frame(frame frame) -> void override; + frame next_free_frame{0}; //!< The frame after the last allocated one + std::optional current_area{std::nullopt}; //!< The current memory area + arch::memory::memory_area * areas; //!< A list of all memory areas + frame kernel_start; //!< The start address of the kernel code in memory + frame kernel_end; //!< The end address of the kernel code in memory + frame multiboot_start; //!< The start address of the multiboot code in memory + frame multiboot_end; //!< The end address of the multiboot code in memory + + area_frame_allocator(std::size_t kernel_start, std::size_t kernel_end, std::size_t multiboot_start, + std::size_t multiboot_end, arch::memory::memory_area * memory_areas) + : kernel_start(frame{kernel_start}) + , kernel_end(frame{kernel_end}) + , multiboot_start(frame{multiboot_start}) + , multiboot_end(frame{multiboot_end}) + , areas(memory_areas) + { + choose_next_area(); + } + + /** + * @brief Allocate memory be finding and returning a free frame + * + * The frame allocation executes multiple checks before returning + * the frame that is available to allocate. It must at least + * do the following: + * - check if the next_free_frame is within the current_area + * - check if the next_free_frame is actually free + * - update the next_free_frame after finding a free frame + */ + auto allocate_frame() -> std::optional; + auto deallocate_frame(frame frame) -> void; + + private: + /** + * @brief Find the next memory area and write it into current_area + */ + auto choose_next_area() -> void; }; } // namespace teachos::arch::memory diff --git a/arch/x86_64/src/memory/frame_allocator.cpp b/arch/x86_64/src/memory/frame_allocator.cpp index b9d26a5..b8f53be 100644 --- a/arch/x86_64/src/memory/frame_allocator.cpp +++ b/arch/x86_64/src/memory/frame_allocator.cpp @@ -2,8 +2,76 @@ namespace teachos::arch::memory { - auto area_frame_allocator::allocate_frame() -> std::optional {} + auto area_frame_allocator::allocate_frame() -> std::optional + { + /* + * Only try to allocate memory if current_area is not null, because + * the current_area is null if there is no more available memory. + */ + if (current_area) + { + frame frame{next_free_frame.frame_number}; + + struct frame current_area_last_frame = { + frame::containing_address(current_area->base_address + current_area->area_length - 1)}; + + if (next_free_frame > current_area_last_frame) + { + // All frames of current area are used, switch to next area + choose_next_area(); + } + else if (frame >= multiboot_start && frame <= kernel_end) + { + // `frame` is used by the kernel or multiboot information structure + next_free_frame = arch::memory::frame{kernel_end.frame_number + 1}; + } + else + { + // Frame is unused, increment `next_free_frame` and return it + next_free_frame.frame_number += 1; + return frame; + } + + // `frame` was not valid, try it again with the updated `next_free_frame` + return allocate_frame(); + } + + // no free frames left + return std::nullopt; + } auto area_frame_allocator::deallocate_frame(frame frame) -> void {} + namespace + { + auto area_frame_allocator::choose_next_area() -> void + { + current_area = std::nullopt; + + // TODO: Fix this loop as soon as you've created an area iterator + for (const auto & area : areas) + { + std::size_t address = area.base_addr + area.length - 1; + if (frame::containing_address(address) >= next_free_frame) + { + // The `next_free_frame` address is smaller than the last address of the current area + if (!current_area || area.base_addr < current_area->base_address) + { + current_area = area; + } + } + } + + if (current_area) + { + // Update the `next_free_frame` according to the new memory area + frame start_frame = frame::containing_address(current_area->base_address); + if (next_free_frame < start_frame) + { + next_free_frame = start_frame; + } + } + } + + } // namespace } // namespace teachos::arch::memory -- cgit v1.2.3