diff options
Diffstat (limited to 'arch/x86_64/src/memory')
24 files changed, 513 insertions, 1316 deletions
diff --git a/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp b/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp deleted file mode 100644 index a5a1b49..0000000 --- a/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp +++ /dev/null @@ -1,85 +0,0 @@ -#include "arch/memory/allocator/area_frame_allocator.hpp" - -#include "arch/exception_handling/assert.hpp" - -#include <algorithm> -#include <array> -#include <ranges> - -namespace teachos::arch::memory::allocator -{ - area_frame_allocator::area_frame_allocator(multiboot::memory_information const & mem_info) - : next_free_frame() - , current_area(std::nullopt) - , memory_areas(mem_info.areas) - , kernel_start(physical_frame::containing_address(mem_info.kernel_start)) - , kernel_end(physical_frame::containing_address(mem_info.kernel_end)) - , multiboot_start(physical_frame::containing_address(mem_info.multiboot_start)) - , multiboot_end(physical_frame::containing_address(mem_info.multiboot_end)) - { - choose_next_area(); - } - - auto area_frame_allocator::choose_next_area() -> void - { - current_area = std::nullopt; - auto next_area_with_free_frames = memory_areas | std::views::filter([this](auto const & area) { - auto address = area.base_address + area.area_length - 1; - return physical_frame::containing_address(address) >= next_free_frame; - }); - - auto const lowest_area_with_free_frames = std::ranges::min_element( - next_area_with_free_frames, [](auto const & a, auto const & b) { return a.base_address < b.base_address; }); - - if (lowest_area_with_free_frames != next_area_with_free_frames.end()) - { - current_area = *lowest_area_with_free_frames; - // Update the `next_free_frame` according to the new memory area - auto const start_frame = physical_frame::containing_address(current_area.value().base_address); - if (next_free_frame < start_frame) - { - next_free_frame = start_frame; - } - } - } - - auto area_frame_allocator::allocate_frame() -> std::optional<physical_frame> - { - // 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.has_value()) - { - return std::nullopt; - } - - auto const address = current_area.value().base_address + current_area.value().area_length - 1; - physical_frame current_area_last_frame = physical_frame::containing_address(address); - - if (next_free_frame > current_area_last_frame) - { - // All frames of current area are used, switch to next area. - choose_next_area(); - } - else if (next_free_frame >= kernel_start && next_free_frame <= kernel_end) - { - // `physical_frame` is used by the kernel or multiboot information structure. - next_free_frame = allocator::physical_frame{kernel_end.frame_number + 1}; - } - else if (next_free_frame >= multiboot_start && next_free_frame <= multiboot_end) - { - // `physical_frame` is used by the kernel or multiboot information structure. - next_free_frame = allocator::physical_frame{multiboot_end.frame_number + 1}; - } - else - { - // Frame is unused, increment `next_free_frame` and return it. - next_free_frame.frame_number += 1; - return next_free_frame; - } - - // `physical_frame` was not valid, try it again with the updated `next_free_frame`. - return allocate_frame(); - } - - auto area_frame_allocator::deallocate_frame(physical_frame const & physical_frame) -> void { (void)physical_frame; } -} // namespace teachos::arch::memory::allocator diff --git a/arch/x86_64/src/memory/allocator/physical_frame.cpp b/arch/x86_64/src/memory/allocator/physical_frame.cpp deleted file mode 100644 index ec387a1..0000000 --- a/arch/x86_64/src/memory/allocator/physical_frame.cpp +++ /dev/null @@ -1,24 +0,0 @@ -#include "arch/memory/allocator/physical_frame.hpp" - -namespace teachos::arch::memory::allocator -{ - auto physical_frame::containing_address(physical_address address) -> physical_frame - { - return physical_frame{address / PAGE_FRAME_SIZE}; - } - - auto physical_frame::start_address() const -> physical_address { return frame_number * PAGE_FRAME_SIZE; } - - auto physical_frame::operator++(int) -> physical_frame - { - physical_frame const old_value = *this; - ++frame_number; - return old_value; - } - - auto physical_frame::operator++() -> physical_frame & - { - ++frame_number; - return *this; - } -} // namespace teachos::arch::memory::allocator diff --git a/arch/x86_64/src/memory/allocator/tiny_frame_allocator.cpp b/arch/x86_64/src/memory/allocator/tiny_frame_allocator.cpp deleted file mode 100644 index 3cdf9c7..0000000 --- a/arch/x86_64/src/memory/allocator/tiny_frame_allocator.cpp +++ /dev/null @@ -1,34 +0,0 @@ -#include "arch/memory/allocator/tiny_frame_allocator.hpp" - -#include "arch/exception_handling/panic.hpp" - -namespace teachos::arch::memory::allocator -{ - auto tiny_frame_allocator::allocate_frame() -> std::optional<physical_frame> - { - for (auto & frame_option : frames) - { - if (frame_option.has_value()) - { - auto value = frame_option; - frame_option.reset(); - return value; - } - } - return std::nullopt; - } - - auto tiny_frame_allocator::deallocate_frame(physical_frame const & physical_frame) -> void - { - for (auto & frame_option : frames) - { - if (!frame_option.has_value()) - { - frame_option.emplace(physical_frame); - return; - } - } - exception_handling::panic( - "[Tiny Frame Allocator] Attempted to deallocate more than the 3 frames, that can be held"); - } -} // namespace teachos::arch::memory::allocator diff --git a/arch/x86_64/src/memory/heap/bump_allocator.cpp b/arch/x86_64/src/memory/heap/bump_allocator.cpp deleted file mode 100644 index 525f45c..0000000 --- a/arch/x86_64/src/memory/heap/bump_allocator.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include "arch/memory/heap/bump_allocator.hpp" - -#include "arch/exception_handling/assert.hpp" - -#include <limits> -#include <type_traits> - -namespace teachos::arch::memory::heap -{ - namespace - { - template<typename T> - auto saturating_add(T x, T y) -> T - requires std::is_unsigned_v<T> - { - if (x > std::numeric_limits<T>::max() - y) - { - return std::numeric_limits<T>::max(); - } - T result = x + y; - return result; - } - } // namespace - - auto bump_allocator::allocate(std::size_t size) -> void * - { - // Reading the value only has to be done once, because compare_exchange_weak updates the value as well if the - // exchange failed, becuase the value was not the expected one. - auto alloc_start = next.load(std::memory_order::relaxed); - // Repeat allocation until it succeeds, has to be done, because another allocator could overtake it at any time - // causing the value to differ and the calculation to have to be redone. - for (;;) - { - auto const alloc_end = saturating_add(alloc_start, size); - arch::exception_handling::assert(alloc_end <= heap_end, "[Heap Allocator] Out of memory"); - // Check if the atomic value is still the one initally loaded, if it isn't we have been overtaken by another - // thread and need to redo the calculation. Spurious failure by weak can be ignored, because the whole allocation - // is wrapped in an infinite for loop so a failure that wasn't actually one will simply be retried until it works. - auto const updated = next.compare_exchange_weak(alloc_start, alloc_end, std::memory_order::relaxed); - if (updated) - { - return reinterpret_cast<void *>(alloc_start); - } - } - } - - auto bump_allocator::deallocate(void * pointer) noexcept -> void - { - if (pointer) - { - } - } - -} // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp deleted file mode 100644 index 35cd623..0000000 --- a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp +++ /dev/null @@ -1,135 +0,0 @@ -#include "arch/memory/heap/global_heap_allocator.hpp" - -#include "arch/context_switching/syscall/main.hpp" -#include "arch/exception_handling/assert.hpp" -#include "arch/kernel/cpu/segment_register.hpp" -#include "arch/memory/heap/bump_allocator.hpp" -#include "arch/memory/heap/linked_list_allocator.hpp" -#include "arch/memory/heap/user_heap_allocator.hpp" - -namespace teachos::arch::memory::heap -{ - namespace - { - constexpr char NOT_REGISTRED_ERROR_MESSAGE[] = - "Attempted to allocate or deallocate using the global_heap_allocator before " - "register_heap_allocation_type was called."; - constexpr uint16_t KERNEL_CODE_INDEX = 1U; - - [[gnu::section(".user_text")]] - auto os_in_kernel_mode() -> bool - { - auto const cs = teachos::arch::kernel::cpu::read_code_segment_register(); - return cs.get_index() == KERNEL_CODE_INDEX; - } - } // namespace - - heap_allocator * global_heap_allocator::kernel_allocator_instance = nullptr; - user_heap_allocator * global_heap_allocator::user_allocator_instance = nullptr; - - auto global_heap_allocator::kmalloc(std::size_t size) -> void * { return kernel().allocate(size); } - - auto global_heap_allocator::kfree(void * pointer) noexcept -> void { kernel().deallocate(pointer); } - - auto global_heap_allocator::malloc(std::size_t size) -> void * { return user().allocate(size); } - - auto global_heap_allocator::free(void * pointer) noexcept -> void { user().deallocate(pointer); } - - auto global_heap_allocator::register_heap_allocator(heap_allocator_type new_type) -> void - { - exception_handling::assert(kernel_allocator_instance == nullptr, - "Calling register_heap_allocator_type can only be done once."); - - switch (new_type) - { - case heap_allocator_type::NONE: - // Nothing to do - break; - case heap_allocator_type::BUMP: { - static bump_allocator kernel_allocator{KERNEL_HEAP_START, KERNEL_HEAP_START + KERNEL_HEAP_SIZE}; - kernel_allocator_instance = &kernel_allocator; - break; - } - case heap_allocator_type::LINKED_LIST: { - static linked_list_allocator kernel_allocator{KERNEL_HEAP_START, KERNEL_HEAP_START + KERNEL_HEAP_SIZE}; - kernel_allocator_instance = &kernel_allocator; - break; - } - } - - [[gnu::section(".user_data")]] - static user_heap_allocator user_allocator{}; - user_allocator_instance = &user_allocator; - } - - auto global_heap_allocator::kernel() -> heap_allocator & - { - exception_handling::assert(kernel_allocator_instance != nullptr, NOT_REGISTRED_ERROR_MESSAGE); - - return *kernel_allocator_instance; - } - - auto global_heap_allocator::user() -> user_heap_allocator & - { - context_switching::syscall::syscall( - context_switching::syscall::type::ASSERT, - {user_allocator_instance != nullptr, reinterpret_cast<uint64_t>(&NOT_REGISTRED_ERROR_MESSAGE)}); - return *user_allocator_instance; - } -} // namespace teachos::arch::memory::heap - -auto operator new(std::size_t size) -> void * -{ - if (teachos::arch::memory::heap::os_in_kernel_mode()) - { - return teachos::arch::memory::heap::global_heap_allocator::kmalloc(size); - } - return teachos::arch::memory::heap::global_heap_allocator::malloc(size); -} - -auto operator delete(void * pointer) noexcept -> void -{ - if (teachos::arch::memory::heap::os_in_kernel_mode()) - { - teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); - } - teachos::arch::memory::heap::global_heap_allocator::free(pointer); -} - -auto operator delete(void * pointer, std::size_t size) noexcept -> void -{ - (void)size; - if (teachos::arch::memory::heap::os_in_kernel_mode()) - { - teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); - } - teachos::arch::memory::heap::global_heap_allocator::free(pointer); -} - -auto operator new[](std::size_t size) -> void * -{ - if (teachos::arch::memory::heap::os_in_kernel_mode()) - { - return teachos::arch::memory::heap::global_heap_allocator::kmalloc(size); - } - return teachos::arch::memory::heap::global_heap_allocator::malloc(size); -} - -auto operator delete[](void * pointer) noexcept -> void -{ - if (teachos::arch::memory::heap::os_in_kernel_mode()) - { - teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); - } - teachos::arch::memory::heap::global_heap_allocator::free(pointer); -} - -auto operator delete[](void * pointer, std::size_t size) noexcept -> void -{ - (void)size; - if (teachos::arch::memory::heap::os_in_kernel_mode()) - { - teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); - } - teachos::arch::memory::heap::global_heap_allocator::free(pointer); -} diff --git a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp deleted file mode 100644 index 63a6111..0000000 --- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp +++ /dev/null @@ -1,177 +0,0 @@ -#include "arch/memory/heap/linked_list_allocator.hpp" - -#include "arch/exception_handling/assert.hpp" -#include "arch/exception_handling/panic.hpp" - -#include <algorithm> - -namespace teachos::arch::memory::heap -{ - linked_list_allocator::linked_list_allocator(std::size_t heap_start, std::size_t heap_end) - : first(nullptr) - , mutex{stl::mutex{}} - { - auto const heap_size = heap_end - heap_start; - exception_handling::assert( - heap_size > min_allocatable_size(), - "[Linked List Allocator] Total heap size can not be smaller than minimum of 16 bytes to hold " - "atleast one memory hole entry"); - first = new (reinterpret_cast<void *>(heap_start)) memory_block(heap_size, nullptr); - } - - auto linked_list_allocator::allocate(std::size_t size) -> void * - { - // Add size of size_t to the total allocated size, because we add a header that includes the size of the allocated - // block, to allow for deallocation without the need to call with the corresponding size - auto const total_size = size + sizeof(std::size_t); - mutex.lock(); - - memory_block * previous = nullptr; - auto current = first; - - while (current != nullptr) - { - if (current->size == total_size) - { - auto const memory_address = remove_free_memory_block(previous, current); - new (memory_address) std::size_t(total_size); - mutex.unlock(); - return reinterpret_cast<void *>(reinterpret_cast<std::size_t>(memory_address) + sizeof(std::size_t)); - } - else if (current->size >= total_size + min_allocatable_size()) - { - // Ensure that the allocated size block is atleast 16 bytes (required because if we free the hole afterwards - // there needs to be enough space for a memory block). Therefore we allocate more than is actually required if - // the total size was less and simply deallocate it as well - auto const max_size = std::max(total_size, min_allocatable_size()); - auto const memory_address = split_free_memory_block(previous, current, max_size); - new (memory_address) std::size_t(max_size); - mutex.unlock(); - return reinterpret_cast<void *>(reinterpret_cast<std::size_t>(memory_address) + sizeof(std::size_t)); - } - - previous = current; - current = current->next; - } - - exception_handling::panic("[Linked List Allocator] Out of memory"); - } - - auto linked_list_allocator::deallocate(void * pointer) noexcept -> void - { - mutex.lock(); - - // Read configured header size of the complete allocated block - auto const header_pointer = reinterpret_cast<void *>(reinterpret_cast<std::size_t>(pointer) - sizeof(std::size_t)); - auto const total_size = *reinterpret_cast<std::size_t *>(header_pointer); - - auto const start_address = reinterpret_cast<std::size_t>(header_pointer); - auto const end_address = start_address + total_size; - - memory_block * previous = nullptr; - auto current = first; - - while (current != nullptr) - { - // Current address of the free memory block now points to an address that is after our block to deallocate in heap - // memory space. - if (reinterpret_cast<std::size_t>(current) >= end_address) - { - break; - } - - previous = current; - current = current->next; - } - - coalesce_free_memory_block(previous, current, header_pointer, total_size); - mutex.unlock(); - } - - auto linked_list_allocator::remove_free_memory_block(memory_block * previous_block, memory_block * current_block) - -> void * - { - return replace_free_memory_block(previous_block, current_block, current_block->next); - } - - auto linked_list_allocator::split_free_memory_block(memory_block * previous_block, memory_block * current_block, - std::size_t size) -> void * - { - auto const end_address = reinterpret_cast<std::size_t>(current_block) + size; - auto const new_block = - new (reinterpret_cast<void *>(end_address)) memory_block(current_block->size - size, current_block->next); - return replace_free_memory_block(previous_block, current_block, new_block); - } - - auto linked_list_allocator::replace_free_memory_block(memory_block * previous_block, memory_block * current_block, - memory_block * new_block) -> void * - { - auto const start_address = reinterpret_cast<std::size_t>(current_block); - // If we want to allocate into the first block that is before any other free block, then there exists no previous - // free block (nullptr). Therefore we have to overwrite the first block instead of overwriting its next value. - if (previous_block == nullptr) - { - first = new_block; - } - else - { - previous_block->next = new_block; - } - current_block->~memory_block(); - return reinterpret_cast<void *>(start_address); - } - - auto linked_list_allocator::coalesce_free_memory_block(memory_block * previous_block, memory_block * current_block, - void * pointer, std::size_t size) -> void - { - auto const start_address = reinterpret_cast<std::size_t>(pointer); - auto const end_address = start_address + size; - - // Inital values if there are no adjacent blocks either before or after, meaning we have to simply create a free - // memory block that is placed in between the previous and next block. - auto block_size = size; - auto next_block = current_block; - - // If the block we want to deallocate is before another free block and we can therefore combine both into one. - // This is done by deleting the current free block and creating a new block at the start address of the block to - // deallocate with both the size of the block to deallcoate and the free block next to it. - if (end_address == reinterpret_cast<std::size_t>(current_block)) - { - block_size += current_block->size; - next_block = current_block->next; - current_block->~memory_block(); - } - - // If the block we want to deallocate is behind another free block and we can therefore combine both into one. - // This is done by simply changin the size of the previous block to include the size of the block to deallocate. - // This is done, because the previous block might still be referencered by the next field of other memory blocks. - if (previous_block != nullptr && - start_address == (reinterpret_cast<std::size_t>(previous_block) + previous_block->size)) - { - block_size += previous_block->size; - - previous_block->size = block_size; - previous_block->next = next_block; - return; - } - - // Check if the block we want to deallocate is contained in the previous block, because if it is it can only mean - // that the block has already been deallocated and we therefore attempted a double free. - exception_handling::assert(previous_block == nullptr || - start_address >= - (reinterpret_cast<std::size_t>(previous_block) + previous_block->size), - "[Linked List Allocator] Attempted double free detected"); - - auto const new_block = new (pointer) memory_block(block_size, next_block); - // If we want to deallocate the first block that is before any other free block, then there exists no previous free - // block (nullptr). Therefore we have to overwrite the first block instead of overwriting its - // next value. - if (previous_block == nullptr) - { - first = new_block; - return; - } - previous_block->next = new_block; - } - -} // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/src/memory/heap/memory_block.cpp b/arch/x86_64/src/memory/heap/memory_block.cpp deleted file mode 100644 index bc97bd6..0000000 --- a/arch/x86_64/src/memory/heap/memory_block.cpp +++ /dev/null @@ -1,15 +0,0 @@ -#include "arch/memory/heap/memory_block.hpp" - -#include <string.h> - -namespace teachos::arch::memory::heap -{ - memory_block::memory_block(std::size_t size, memory_block * next) - { - memset(static_cast<void *>(this), 0U, size); - this->size = size; - this->next = next; - } - - memory_block::~memory_block() { memset(static_cast<void *>(this), 0U, sizeof(memory_block)); } -} // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp deleted file mode 100644 index 427a68a..0000000 --- a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp +++ /dev/null @@ -1,200 +0,0 @@ -#include "arch/memory/heap/user_heap_allocator.hpp" - -#include "arch/context_switching/syscall/main.hpp" - -#include <algorithm> - -namespace teachos::arch::memory::heap -{ - auto user_heap_allocator::allocate(std::size_t size) -> void * - { - // Add size of size_t to the total allocated size, because we add a header that includes the size of the allocated - // block, to allow for deallocation without the need to call with the corresponding size - auto const total_size = size + sizeof(std::size_t); - mutex.lock(); - - memory_block * previous = nullptr; - auto current = first; - - while (current != nullptr) - { - auto memory = allocate_into_memory_block_if_big_enough(current, previous, total_size); - if (memory.has_value()) - { - return memory.value(); - } - - previous = current; - current = current->next; - } - - current = expand_heap_if_full(); - - if (current != nullptr) - { - auto memory = allocate_into_memory_block_if_big_enough(current, previous, total_size); - if (memory.has_value()) - { - return memory.value(); - } - } - - char constexpr OUT_OF_MEMORY_ERROR_MESSAGE[] = "[Linked List Allocator] Out of memory"; - context_switching::syscall::syscall(context_switching::syscall::type::ASSERT, - {false, reinterpret_cast<uint64_t>(&OUT_OF_MEMORY_ERROR_MESSAGE)}); - return nullptr; - } - - auto user_heap_allocator::deallocate(void * pointer) noexcept -> void - { - mutex.lock(); - - // Read configured header size of the complete allocated block - auto const header_pointer = reinterpret_cast<void *>(reinterpret_cast<std::size_t>(pointer) - sizeof(std::size_t)); - auto const total_size = *reinterpret_cast<std::size_t *>(header_pointer); - - auto const start_address = reinterpret_cast<std::size_t>(header_pointer); - auto const end_address = start_address + total_size; - - memory_block * previous = nullptr; - auto current = first; - - while (current != nullptr) - { - // Current address of the free memory block now points to an address that is after our block to deallocate in heap - // memory space. - if (reinterpret_cast<std::size_t>(current) >= end_address) - { - break; - } - - previous = current; - current = current->next; - } - - coalesce_free_memory_block(previous, current, header_pointer, total_size); - mutex.unlock(); - } - - auto user_heap_allocator::allocate_into_memory_block_if_big_enough(memory_block * current, memory_block * previous, - std::size_t total_size) -> std::optional<void *> - { - if (current->size == total_size) - { - auto const memory_address = remove_free_memory_block(previous, current); - new (memory_address) std::size_t(total_size); - mutex.unlock(); - return reinterpret_cast<void *>(reinterpret_cast<std::size_t>(memory_address) + sizeof(std::size_t)); - } - else if (current->size >= total_size + min_allocatable_size()) - { - // Ensure that the allocated size block is atleast 16 bytes (required because if we free the hole afterwards - // there needs to be enough space for a memory block). Therefore we allocate more than is actually required if - // the total size was less and simply deallocate it as well - auto const max_size = std::max(total_size, min_allocatable_size()); - auto const memory_address = split_free_memory_block(previous, current, max_size); - new (memory_address) std::size_t(max_size); - mutex.unlock(); - return reinterpret_cast<void *>(reinterpret_cast<std::size_t>(memory_address) + sizeof(std::size_t)); - } - return std::nullopt; - } - - auto user_heap_allocator::expand_heap_if_full() -> memory_block * - { - auto const result = context_switching::syscall::syscall(context_switching::syscall::type::EXPAND_HEAP); - - uint64_t const heap_start = result.values.arg_0; - uint64_t const heap_size = result.values.arg_1; - return !result.error_code ? new (reinterpret_cast<void *>(heap_start)) memory_block(heap_size, nullptr) : nullptr; - } - - auto user_heap_allocator::remove_free_memory_block(memory_block * previous_block, memory_block * current_block) - -> void * - { - return replace_free_memory_block(previous_block, current_block, current_block->next); - } - - auto user_heap_allocator::split_free_memory_block(memory_block * previous_block, memory_block * current_block, - std::size_t size) -> void * - { - auto const end_address = reinterpret_cast<std::size_t>(current_block) + size; - auto const new_block = - new (reinterpret_cast<void *>(end_address)) memory_block(current_block->size - size, current_block->next); - return replace_free_memory_block(previous_block, current_block, new_block); - } - - auto user_heap_allocator::replace_free_memory_block(memory_block * previous_block, memory_block * current_block, - memory_block * new_block) -> void * - { - auto const start_address = reinterpret_cast<std::size_t>(current_block); - // If we want to allocate into the first block that is before any other free block, then there exists no previous - // free block (nullptr). Therefore we have to overwrite the first block instead of overwriting its next value. - if (previous_block == nullptr) - { - first = new_block; - } - else - { - previous_block->next = new_block; - } - current_block->~memory_block(); - return reinterpret_cast<void *>(start_address); - } - - auto user_heap_allocator::coalesce_free_memory_block(memory_block * previous_block, memory_block * current_block, - void * pointer, std::size_t size) -> void - { - auto const start_address = reinterpret_cast<std::size_t>(pointer); - auto const end_address = start_address + size; - - // Inital values if there are no adjacent blocks either before or after, meaning we have to simply create a free - // memory block that is placed in between the previous and next block. - auto block_size = size; - auto next_block = current_block; - - // If the block we want to deallocate is before another free block and we can therefore combine both into one. - // This is done by deleting the current free block and creating a new block at the start address of the block to - // deallocate with both the size of the block to deallcoate and the free block next to it. - if (end_address == reinterpret_cast<std::size_t>(current_block)) - { - block_size += current_block->size; - next_block = current_block->next; - current_block->~memory_block(); - } - - // If the block we want to deallocate is behind another free block and we can therefore combine both into one. - // This is done by simply changin the size of the previous block to include the size of the block to deallocate. - // This is done, because the previous block might still be referencered by the next field of other memory blocks. - if (previous_block != nullptr && - start_address == (reinterpret_cast<std::size_t>(previous_block) + previous_block->size)) - { - block_size += previous_block->size; - - previous_block->size = block_size; - previous_block->next = next_block; - return; - } - - // Check if the block we want to deallocate is contained in the previous block, because if it is it can only mean - // that the block has already been deallocated and we therefore attempted a double free. - char constexpr DOUBLE_FREE_ERROR_MESSAGE[] = "[Linked List Allocator] Attempted double free detected"; - context_switching::syscall::syscall( - context_switching::syscall::type::ASSERT, - {previous_block == nullptr || - start_address >= (reinterpret_cast<std::size_t>(previous_block) + previous_block->size), - reinterpret_cast<uint64_t>(&DOUBLE_FREE_ERROR_MESSAGE)}); - - auto const new_block = new (pointer) memory_block(block_size, next_block); - // If we want to deallocate the first block that is before any other free block, then there exists no previous free - // block (nullptr). Therefore we have to overwrite the first block instead of overwriting its - // next value. - if (previous_block == nullptr) - { - first = new_block; - return; - } - previous_block->next = new_block; - } - -} // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/src/memory/kernel_mapper.cpp b/arch/x86_64/src/memory/kernel_mapper.cpp new file mode 100644 index 0000000..4781d64 --- /dev/null +++ b/arch/x86_64/src/memory/kernel_mapper.cpp @@ -0,0 +1,111 @@ +#include "x86_64/memory/kernel_mapper.hpp" + +#include "kapi/cio.hpp" +#include "kapi/memory.hpp" +#include "kapi/system.hpp" + +#include "x86_64/boot/ld.hpp" + +#include <elf/format.hpp> +#include <elf/section_header.hpp> +#include <multiboot2/information.hpp> + +#include <algorithm> +#include <array> +#include <bit> +#include <cstdint> +#include <ranges> +#include <string_view> +#include <utility> + +namespace teachos::memory::x86_64 +{ + + namespace + { + using namespace std::string_view_literals; + + constexpr auto static ignored_section_prefixes = std::array{ + ".boot_"sv, + }; + + constexpr auto static user_accessible_prefixes = std::array{ + ".user"sv, + ".stl"sv, + }; + + } // namespace + + kernel_mapper::kernel_mapper(multiboot2::information_view const * mbi) + : m_mbi{std::move(mbi)} + , m_kernel_load_base{std::bit_cast<std::uintptr_t>(&boot::x86_64::TEACHOS_VMA)} + {} + + auto kernel_mapper::remap_kernel(page_mapper & mapper) -> void + { + auto elf_information = m_mbi->maybe_elf_symbols<elf::format::elf64>(); + if (!elf_information) + { + system::panic("[x86_64:MEM] ELF section information is not available."); + } + + auto sections = *elf_information; + auto allocated_sections = + std::views::all(sections) | std::views::filter(&elf::section_header<elf::format::elf64>::allocated) | + std::views::filter([&](auto const & section) -> auto { + auto name = sections.name(section); + return !std::ranges::any_of(ignored_section_prefixes, + [&](auto const & prefix) -> auto { return name.starts_with(prefix); }); + }); + + if (allocated_sections.empty()) + { + system::panic("[x86_64:MEM] No allocated ELF sections were found."); + } + + std::ranges::for_each(allocated_sections, + [&](auto const & section) -> auto { map_section(section, sections.name(section), mapper); }); + } + + auto kernel_mapper::map_section(section_header_type const & section, std::string_view name, page_mapper & mapper) + -> void + { + cio::print("[x86_64:MEM] mapping "); + cio::println(name); + + auto number_of_pages = (section.size + (PLATFORM_PAGE_SIZE - 1)) / PLATFORM_PAGE_SIZE; + + auto linear_start_address = linear_address{section.virtual_load_address}; + auto physical_start_address = physical_address{section.virtual_load_address & ~m_kernel_load_base}; + + auto first_page = page::containing(linear_start_address); + auto first_frame = frame::containing(physical_start_address); + + auto page_flags = page_mapper::flags::empty; + + if (section.writable()) + { + page_flags |= page_mapper::flags::writable; + } + + if (section.executable()) + { + page_flags |= page_mapper::flags::executable; + } + + auto is_prefix_of_name = [=](auto prefix) -> bool { + return name.starts_with(prefix); + }; + + if (!std::ranges::any_of(user_accessible_prefixes, is_prefix_of_name)) + { + page_flags |= page_mapper::flags::supervisor_only; + } + + for (auto i = 0uz; i < number_of_pages; ++i) + { + mapper.map(first_page + i, first_frame + i, page_flags); + } + } + +} // namespace teachos::memory::x86_64
\ No newline at end of file diff --git a/arch/x86_64/src/memory/main.cpp b/arch/x86_64/src/memory/main.cpp deleted file mode 100644 index 2746a71..0000000 --- a/arch/x86_64/src/memory/main.cpp +++ /dev/null @@ -1,77 +0,0 @@ -#include "arch/memory/main.hpp" - -#include "arch/exception_handling/assert.hpp" -#include "arch/kernel/cpu/control_register.hpp" -#include "arch/kernel/cpu/msr.hpp" -#include "arch/memory/allocator/area_frame_allocator.hpp" -#include "arch/memory/allocator/concept.hpp" -#include "arch/memory/heap/global_heap_allocator.hpp" -#include "arch/memory/paging/active_page_table.hpp" -#include "arch/memory/paging/kernel_mapper.hpp" - -#include <optional> - -namespace teachos::arch::memory -{ - namespace - { - static std::optional<allocator::area_frame_allocator> frame_allocator; - - auto create_frame_allocator(multiboot::memory_information const & memory_information) - -> allocator::area_frame_allocator & - { - frame_allocator.emplace(memory_information); - return frame_allocator.value(); - } - - auto get_frame_allocator() -> allocator::area_frame_allocator & - { - exception_handling::assert(frame_allocator.has_value(), - "[Initialization] Frame allocator has not been created yet"); - return frame_allocator.value(); - } - } // namespace - - auto remap_heap(std::size_t heap_start, std::size_t heap_size, paging::entry::bitset additional_flags = {}) -> void - { - decltype(auto) allocator = get_frame_allocator(); - decltype(auto) active_table = paging::active_page_table::create_or_get(); - auto const start_page = paging::virtual_page::containing_address(heap_start); - auto const end_page = ++(paging::virtual_page::containing_address(heap_start + heap_size - 1)); - - paging::page_container::iterator const begin{start_page}; - paging::page_container::iterator const end{end_page}; - paging::page_container const pages{begin, end}; - - constexpr auto base_flags = paging::entry::WRITABLE; - auto const flags = base_flags | additional_flags; - - for (auto const & page : pages) - { - active_table.map_page_to_next_free_frame(allocator, page, flags); - } - } - - auto initialize_memory_management() -> void - { - static bool has_been_called = false; - arch::exception_handling::assert(!has_been_called, - "[Initialization] Memory management has already been initialized"); - has_been_called = true; - - auto const memory_information = multiboot::read_multiboot2(); - decltype(auto) allocator = create_frame_allocator(memory_information); - - kernel::cpu::set_cr0_bit(kernel::cpu::cr0_flags::WRITE_PROTECT); - kernel::cpu::set_efer_bit(kernel::cpu::efer_flags::NXE); - - paging::kernel_mapper kernel(allocator, memory_information); - kernel.remap_kernel(); - video::vga::text::write("Kernel remapping successful", video::vga::text::common_attributes::green_on_black); - video::vga::text::newline(); - - remap_heap(heap::KERNEL_HEAP_START, heap::KERNEL_HEAP_SIZE); - video::vga::text::write("Heap remapping successful", video::vga::text::common_attributes::green_on_black); - video::vga::text::newline(); - } -} // namespace teachos::arch::memory diff --git a/arch/x86_64/src/memory/mmu.cpp b/arch/x86_64/src/memory/mmu.cpp new file mode 100644 index 0000000..e15d94e --- /dev/null +++ b/arch/x86_64/src/memory/mmu.cpp @@ -0,0 +1,21 @@ +#include "x86_64/memory/mmu.hpp" + +#include "kapi/memory.hpp" + +#include "x86_64/cpu/registers.hpp" + +namespace teachos::memory::x86_64 +{ + namespace cpu = cpu::x86_64; + + auto tlb_flush(linear_address address) -> void + { + asm volatile("invlpg (%[input])" : /* no output from call */ : [input] "r"(address) : "memory"); + } + + auto tlb_flush_all() -> void + { + auto paging_root = cpu::cr3::read(); + cpu::cr3::write(paging_root); + } +} // namespace teachos::memory::x86_64 diff --git a/arch/x86_64/src/memory/multiboot/elf_symbols_section.cpp b/arch/x86_64/src/memory/multiboot/elf_symbols_section.cpp deleted file mode 100644 index f5d126b..0000000 --- a/arch/x86_64/src/memory/multiboot/elf_symbols_section.cpp +++ /dev/null @@ -1,13 +0,0 @@ -#include "arch/memory/multiboot/elf_symbols_section.hpp" - -namespace teachos::arch::memory::multiboot -{ - auto elf_section_flags::contains_flags(std::bitset<64U> other) const -> bool { return (flags & other) == other; } - - auto elf_section_header::is_null() const -> bool - { - return name_table_index == 0U && type == elf_section_type::INACTIVE && flags == elf_section_flags(0U) && - physical_address == 0U && file_offset == 0U && additional_information == 0U && address_alignment == 0U && - fixed_table_entry_size == 0U; - } -} // namespace teachos::arch::memory::multiboot diff --git a/arch/x86_64/src/memory/multiboot/reader.cpp b/arch/x86_64/src/memory/multiboot/reader.cpp deleted file mode 100644 index 2bf5b25..0000000 --- a/arch/x86_64/src/memory/multiboot/reader.cpp +++ /dev/null @@ -1,131 +0,0 @@ -#include "arch/memory/multiboot/reader.hpp" - -#include "arch/boot/pointers.hpp" -#include "arch/exception_handling/assert.hpp" -#include "arch/memory/multiboot/elf_symbols_section.hpp" -#include "arch/memory/multiboot/info.hpp" - -#include <algorithm> -#include <ranges> - -namespace teachos::arch::memory::multiboot -{ - namespace - { - template<typename T> - requires std::is_pointer<T>::value - auto align_to_8_byte_boundary(T ptr, uint32_t size) -> T - { - return reinterpret_cast<T>(reinterpret_cast<uint8_t *>(ptr) + ((size + 7) & ~7)); - } - - auto process_memory_map(memory_map_header * mminfo) -> memory_area_container - { - auto const expected_entry_size = mminfo->entry_size; - auto constexpr actual_entry_size = sizeof(memory_area); - exception_handling::assert(expected_entry_size == actual_entry_size, - "[Multiboot Reader] Unexpected memory area entry size"); - - auto const total_size = mminfo->info.size; - auto const total_entries_size = total_size - sizeof(memory_map_header) + actual_entry_size; - auto const number_of_entries = total_entries_size / actual_entry_size; - - auto const begin = memory_area_container::iterator{&mminfo->entries}; - auto const end = begin + number_of_entries; - return memory_area_container{begin, end}; - } - - auto process_elf_sections(elf_symbols_section_header * symbol, std::size_t & kernel_start, - std::size_t & kernel_end) -> elf_section_header_container - { - auto const expected_entry_size = symbol->entry_size; - auto constexpr actual_entry_size = sizeof(elf_section_header); - exception_handling::assert(expected_entry_size == actual_entry_size, - "[Multiboot Reader] Unexpected elf section header entry size"); - - auto const expected_total_size = symbol->info.size; - auto const actual_total_entry_size = actual_entry_size * symbol->number_of_sections; - auto constexpr actual_total_section_size = sizeof(elf_symbols_section_header) - sizeof(uint32_t); - auto const actual_total_size = actual_total_entry_size + actual_total_section_size; - exception_handling::assert(expected_total_size == actual_total_size, - "[Multiboot Reader] Unexpected elf symbols section header total size"); - - auto const begin = elf_section_header_container::iterator{reinterpret_cast<elf_section_header *>(&symbol->end)}; - auto const end = begin + symbol->number_of_sections; - exception_handling::assert(begin->is_null(), - "[Multiboot Reader] Elf symbols section not starting with SHT_NULL section"); - - elf_section_header_container sections{begin, end}; - - auto allocated_sections = sections | std::views::filter([](auto const & section) { - return section.flags.contains_flags(elf_section_flags::OCCUPIES_MEMORY); - }); - - auto const elf_section_with_lowest_physical_address = std::ranges::min_element( - allocated_sections, [](auto const & a, auto const & b) { return a.physical_address < b.physical_address; }); - - auto const elf_section_with_highest_physical_address = - std::ranges::max_element(allocated_sections, [](auto const & a, auto const & b) { - auto a_physical_address_end = a.physical_address + a.section_size; - auto b_physical_address_end = b.physical_address + b.section_size; - return a_physical_address_end < b_physical_address_end; - }); - - auto const symbol_table_section_count = std::ranges::count_if(sections, [](auto const & section) { - return section.type == elf_section_type::DYNAMIC_SYMBOL_TABLE || section.type == elf_section_type::SYMBOL_TABLE; - }); - auto const dynamic_section_count = std::ranges::count_if( - sections, [](auto const & section) { return section.type == elf_section_type::DYNAMIC; }); - - exception_handling::assert( - symbol_table_section_count == 1U, - "[Multiboot Reader] ELF Specifications allows only (1) symbol table section, but got more"); - exception_handling::assert( - dynamic_section_count <= 1U, - "[Multiboot Reader] ELF Specifications allows only (1) or less dynamic sections, but got more"); - - auto const lowest_elf_section = *elf_section_with_lowest_physical_address; - kernel_start = lowest_elf_section.physical_address; - - auto const highest_elf_section = *elf_section_with_highest_physical_address; - kernel_end = highest_elf_section.physical_address + highest_elf_section.section_size; - - return sections; - } - } // namespace - - auto read_multiboot2() -> memory_information - { - memory_information mem_info{UINT64_MAX, - 0U, - elf_section_header_container{}, - boot::multiboot_information_pointer, - 0U, - memory_area_container{}}; - - auto const multiboot_information_pointer = reinterpret_cast<info_header *>(boot::multiboot_information_pointer); - auto const multiboot_tag = &multiboot_information_pointer->tags; - mem_info.multiboot_end = mem_info.multiboot_start + multiboot_information_pointer->total_size; - - for (auto tag = multiboot_tag; tag->type != tag_type::END; tag = align_to_8_byte_boundary(tag, tag->size)) - { - switch (tag->type) - { - case tag_type::ELF_SECTIONS: { - auto const symbol = reinterpret_cast<elf_symbols_section_header *>(tag); - mem_info.sections = process_elf_sections(symbol, mem_info.kernel_start, mem_info.kernel_end); - break; - } - case tag_type::MEMORY_MAP: { - auto const mminfo = reinterpret_cast<memory_map_header *>(tag); - mem_info.areas = process_memory_map(mminfo); - break; - } - default: - // All other cases are not important and can be ignored. - break; - } - } - return mem_info; - } -} // namespace teachos::arch::memory::multiboot diff --git a/arch/x86_64/src/memory/page_table.cpp b/arch/x86_64/src/memory/page_table.cpp new file mode 100644 index 0000000..2de099d --- /dev/null +++ b/arch/x86_64/src/memory/page_table.cpp @@ -0,0 +1,82 @@ +#include "x86_64/memory/page_table.hpp" + +#include "kapi/memory.hpp" + +#include <algorithm> +#include <bit> +#include <cstddef> +#include <cstdint> +#include <optional> +#include <utility> + +namespace teachos::memory::x86_64 +{ + + auto page_table::entry::clear() noexcept -> void + { + m_raw = 0; + } + + auto page_table::entry::present() const noexcept -> bool + { + return (all_flags() & flags::present) != flags::empty; + } + + auto page_table::entry::huge() const noexcept -> bool + { + return (all_flags() & flags::huge_page) != flags::empty; + } + + auto page_table::entry::all_flags() const noexcept -> flags + { + return std::bit_cast<flags>(m_raw & ~frame_number_mask); + } + + auto page_table::entry::all_flags(flags flags) noexcept -> void + { + m_raw = (m_raw & ~frame_number_mask) | std::to_underlying(flags); + } + + auto page_table::entry::operator|=(flags rhs) noexcept -> page_table::entry & + { + auto raw_flags = std::to_underlying(rhs) & ~frame_number_mask; + m_raw |= raw_flags; + return *this; + } + + auto page_table::entry::frame() const noexcept -> std::optional<struct frame> + { + if (present()) + { + return frame::containing(physical_address{m_raw & frame_number_mask}); + } + return std::nullopt; + } + + auto page_table::entry::frame(struct frame frame, flags flags) noexcept -> void + { + m_raw = (frame.start_address().raw() | static_cast<std::uint64_t>(flags)); + }; + + auto page_table::operator[](std::size_t index) -> entry & + { + return m_entries.at(index); + } + + auto page_table::operator[](std::size_t index) const -> entry const & + { + return m_entries.at(index); + } + + auto page_table::clear() noexcept -> void + { + std::ranges::for_each(m_entries, &page_table::entry::clear); + } + + auto page_table::empty() const noexcept -> bool + { + return std::ranges::all_of(m_entries, + [](auto const & entry) -> auto { return entry.all_flags() == entry::flags::empty; }); + } + +} // namespace teachos::memory::x86_64 diff --git a/arch/x86_64/src/memory/paging/active_page_table.cpp b/arch/x86_64/src/memory/paging/active_page_table.cpp deleted file mode 100644 index 0113869..0000000 --- a/arch/x86_64/src/memory/paging/active_page_table.cpp +++ /dev/null @@ -1,98 +0,0 @@ -#include "arch/memory/paging/active_page_table.hpp" - -namespace teachos::arch::memory::paging -{ - namespace - { - paging::virtual_address constexpr PAGE_TABLE_LEVEL_4_ADDRESS = 0xffffffff'fffff000; - } - - auto active_page_table::create_or_get() -> active_page_table & - { - static page_table_handle active_handle{reinterpret_cast<page_table *>(PAGE_TABLE_LEVEL_4_ADDRESS), - page_table_handle::LEVEL4}; - static active_page_table active_page{active_handle}; - return active_page; - } - - auto active_page_table::operator[](std::size_t index) -> entry & { return active_handle[index]; } - - auto active_page_table::translate_address(virtual_address address) -> std::optional<allocator::physical_address> - { - auto const offset = address % allocator::PAGE_FRAME_SIZE; - auto const page = virtual_page::containing_address(address); - auto const frame = translate_page(page); - - if (frame.has_value()) - { - return frame.value().frame_number * allocator::PAGE_FRAME_SIZE + offset; - } - - return std::nullopt; - } - - auto active_page_table::translate_page(virtual_page page) -> std::optional<allocator::physical_frame> - { - auto current_handle = active_handle; - - for (auto level = page_table_handle::LEVEL4; level != page_table_handle::LEVEL1; --level) - { - auto const next_handle = current_handle.next_table(page.get_level_index(level)); - // If the next table method failed then it is highly likely that it was a huge page and we therefore have to - // parse the table differently. Therefore, we attempt to parse it using the method required by huge pages. - if (!next_handle.has_value()) - { - return translate_huge_page(page); - } - current_handle = next_handle.value(); - } - - auto const level1_index = page.get_level_index(page_table_handle::LEVEL1); - auto const level1_entry = current_handle[level1_index]; - return level1_entry.calculate_pointed_to_frame(); - } - - auto active_page_table::translate_huge_page(virtual_page page) -> std::optional<allocator::physical_frame> - { - auto current_handle = active_handle; - auto level3_handle = current_handle.next_table(page.get_level_index(page_table_handle::LEVEL4)); - - if (!level3_handle.has_value()) - { - return std::nullopt; - } - - auto const level3_entry = level3_handle.value()[page.get_level_index(page_table_handle::LEVEL3)]; - auto const level3_frame = level3_entry.calculate_pointed_to_frame(); - if (level3_frame.has_value() && level3_entry.contains_flags(entry::HUGE_PAGE)) - { - exception_handling::assert( - level3_frame.value().frame_number % (PAGE_TABLE_ENTRY_COUNT * PAGE_TABLE_ENTRY_COUNT) == 0U, - "[Page Mapper] Physical address must be 1 GiB aligned"); - return allocator::physical_frame{level3_frame.value().frame_number + - page.get_level_index(page_table_handle::LEVEL2) * PAGE_TABLE_ENTRY_COUNT + - page.get_level_index(page_table_handle::LEVEL1)}; - } - - auto level2_handle = level3_handle.value().next_table(page.get_level_index(page_table_handle::LEVEL3)); - if (level2_handle.has_value()) - { - auto const level2_entry = level2_handle.value()[page.get_level_index(page_table_handle::LEVEL2)]; - auto const level2_frame = level2_entry.calculate_pointed_to_frame(); - if (level2_frame.has_value() && level2_entry.contains_flags(entry::HUGE_PAGE)) - { - exception_handling::assert(level2_frame.value().frame_number % PAGE_TABLE_ENTRY_COUNT == 0U, - "[Page Mapper] Physical address must be 2 MiB aligned"); - return allocator::physical_frame{level2_frame.value().frame_number + - page.get_level_index(page_table_handle::LEVEL1)}; - } - } - return std::nullopt; - } - - active_page_table::active_page_table(page_table_handle active_handle) - : active_handle(active_handle) - { - // Nothing to do - } -} // namespace teachos::arch::memory::paging diff --git a/arch/x86_64/src/memory/paging/inactive_page_table.cpp b/arch/x86_64/src/memory/paging/inactive_page_table.cpp deleted file mode 100644 index 4e0610e..0000000 --- a/arch/x86_64/src/memory/paging/inactive_page_table.cpp +++ /dev/null @@ -1,20 +0,0 @@ -#include "arch/memory/paging/inactive_page_table.hpp" - -namespace teachos::arch::memory::paging -{ - inactive_page_table::inactive_page_table(allocator::physical_frame frame) - : page_table_level_4_frame{frame} - { - // Nothing to do - } - - inactive_page_table::inactive_page_table(allocator::physical_frame frame, active_page_table & active_page_table, - temporary_page & temporary_page) - : page_table_level_4_frame{frame} - { - auto table = temporary_page.map_table_frame(page_table_level_4_frame, active_page_table); - table.zero_entries(); - table[511].set_entry(page_table_level_4_frame, entry::PRESENT | entry::WRITABLE); - temporary_page.unmap_page(active_page_table); - } -} // namespace teachos::arch::memory::paging diff --git a/arch/x86_64/src/memory/paging/page_entry.cpp b/arch/x86_64/src/memory/paging/page_entry.cpp deleted file mode 100644 index 57045ca..0000000 --- a/arch/x86_64/src/memory/paging/page_entry.cpp +++ /dev/null @@ -1,63 +0,0 @@ -#include "arch/memory/paging/page_entry.hpp" - -#include "arch/exception_handling/assert.hpp" - -namespace teachos::arch::memory::paging -{ - namespace - { - std::size_t constexpr PHYSICAL_ADDRESS_MASK = 0x000fffff'fffff000; - } // namespace - - entry::entry(uint64_t flags) - : flags(flags) - { - // Nothing to do. - } - - entry::entry(multiboot::elf_section_flags elf_flags) - { - if (elf_flags.contains_flags(multiboot::elf_section_flags::OCCUPIES_MEMORY)) - { - flags |= entry::PRESENT; - } - - if (elf_flags.contains_flags(multiboot::elf_section_flags::WRITABLE)) - { - flags |= entry::WRITABLE; - } - - if (!elf_flags.contains_flags(multiboot::elf_section_flags::EXECUTABLE_CODE)) - { - flags |= entry::EXECUTING_CODE_FORBIDDEN; - } - } - - auto entry::is_unused() const -> bool { return flags == 0U; } - - auto entry::set_unused() -> void { flags = 0U; } - - auto entry::set_user_accessible() -> void { flags |= entry::USER_ACCESSIBLE; } - - auto entry::calculate_pointed_to_frame() const -> std::optional<allocator::physical_frame> - { - if (contains_flags(PRESENT)) - { - auto const address = flags.to_ulong() & PHYSICAL_ADDRESS_MASK; - return allocator::physical_frame::containing_address(address); - } - return std::nullopt; - } - - auto entry::contains_flags(std::bitset<64U> other) const -> bool { return (flags & other) == other; } - - auto entry::set_entry(allocator::physical_frame frame, std::bitset<64U> additional_flags) -> void - { - exception_handling::assert((frame.start_address() & ~PHYSICAL_ADDRESS_MASK) == 0, - "[Paging Entry] Start address is not aligned with page"); - - flags = frame.start_address() | additional_flags.to_ulong(); - } - - auto entry::get_flags() const -> std::bitset<64U> { return flags.to_ulong() & ~PHYSICAL_ADDRESS_MASK; } -} // namespace teachos::arch::memory::paging diff --git a/arch/x86_64/src/memory/paging/page_table.cpp b/arch/x86_64/src/memory/paging/page_table.cpp deleted file mode 100644 index eb11810..0000000 --- a/arch/x86_64/src/memory/paging/page_table.cpp +++ /dev/null @@ -1,128 +0,0 @@ -#include "arch/memory/paging/page_table.hpp" - -#include <algorithm> -#include <array> -#include <memory> - -/* - * This is a linker variable reference. This referenc cannot reside inside a namespace, because in - * that case the compiler would try to find arch::memory::paging::_end_of_image inside the ELF file. - */ -extern char _end_of_image; - -namespace teachos::arch::memory::paging -{ - /** - * @brief A Page table containing 512 entries. - */ - struct page_table - { - auto zero_entries() -> void; - - auto is_empty() const -> bool; - - auto next_table(std::size_t table_index) const -> std::optional<page_table *>; - - auto operator[](std::size_t index) -> entry &; - - auto operator[](std::size_t index) const -> entry const &; - - private: - /** - * @brief Calculates the address of the next page table level for the given table index. - * - * @note The next page table address is only valid if the corresponding entry is present and not a huge page. - * Meaning we use an index into a Level 4 page table to get the according Level 3 page table address. - * - * @param table_index Index of this page table in the page table one level higher. - * @return An optional of the address of the next page table or null. - */ - auto next_table_address(std::size_t table_index) const -> std::optional<std::size_t>; - - std::array<entry, PAGE_TABLE_ENTRY_COUNT> entries = - {}; ///< Entries containing addresses to page tables of a level below or - ///< actual virtual addresses for the level 1 page table. - }; - - auto page_table::zero_entries() -> void - { - std::ranges::for_each(entries, [](auto & entry) { entry.set_unused(); }); - } - - auto page_table::is_empty() const -> bool - { - return std::all_of(entries.begin(), entries.end(), [](entry const & entry) { return entry.is_unused(); }); - } - - auto page_table::next_table(std::size_t table_index) const -> std::optional<page_table *> - { - auto const address = next_table_address(table_index); - if (address.has_value()) - { - return reinterpret_cast<page_table *>(address.value()); - } - return std::nullopt; - } - - auto page_table::operator[](std::size_t index) -> entry & - { - exception_handling::assert(index < PAGE_TABLE_ENTRY_COUNT, "[Page Table] Index out of bounds"); - return entries[index]; - } - - auto page_table::operator[](std::size_t index) const -> entry const & - { - exception_handling::assert(index < PAGE_TABLE_ENTRY_COUNT, "[Page Table] Index out of bounds"); - return entries[index]; - } - - auto page_table::next_table_address(std::size_t table_index) const -> std::optional<std::size_t> - { - auto const entry = this->operator[](table_index); - - if (entry.contains_flags(entry::PRESENT) && !entry.contains_flags(entry::HUGE_PAGE)) - { - auto const table_address = reinterpret_cast<std::size_t>(this); - return ((table_address << 9) | (table_index << 12)); - } - return std::nullopt; - } - - page_table_handle::page_table_handle(page_table * table, page_table_handle::level table_level) - : table(table) - , table_level(table_level) - { - exception_handling::assert(table != nullptr, - "[Page Table] Attempted to pass nullptr as table to page table table method"); - } - - auto page_table_handle::zero_entries() -> void { table->zero_entries(); } - - auto page_table_handle::is_empty() const -> bool { return table->is_empty(); } - - auto page_table_handle::next_table(std::size_t table_index) const -> std::optional<page_table_handle> - { - exception_handling::assert(table_level != page_table_handle::LEVEL1, - "[Page Table] Attempted to call next_table on level 1 page table"); - auto const next_table = table->next_table(table_index); - if (next_table.has_value()) - { - auto const new_level = static_cast<page_table_handle::level>(table_level - 1); - return page_table_handle{next_table.value(), new_level}; - } - return std::nullopt; - } - - auto page_table_handle::get_level() const -> page_table_handle::level { return table_level; } - - auto page_table_handle::operator[](std::size_t index) -> entry & { return table->operator[](index); } - - auto operator--(page_table_handle::level & value) -> page_table_handle::level & - { - exception_handling::assert(value != page_table_handle::LEVEL1, - "[Page table] Attempted to decrement enum to value outside of range"); - auto new_value = static_cast<std::underlying_type<page_table_handle::level>::type>(value); - value = static_cast<page_table_handle::level>(--new_value); - return value; - } -} // namespace teachos::arch::memory::paging diff --git a/arch/x86_64/src/memory/paging/temporary_page.cpp b/arch/x86_64/src/memory/paging/temporary_page.cpp deleted file mode 100644 index 8e73523..0000000 --- a/arch/x86_64/src/memory/paging/temporary_page.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include "arch/memory/paging/temporary_page.hpp" - -#include "arch/memory/paging/page_entry.hpp" - -namespace teachos::arch::memory::paging -{ - auto temporary_page::map_table_frame(allocator::physical_frame frame, active_page_table & active_table) - -> page_table_handle - { - page_table_handle handle{reinterpret_cast<page_table *>(map_to_frame(frame, active_table)), - page_table_handle::LEVEL1}; - return handle; - } - - auto temporary_page::map_to_frame(allocator::physical_frame frame, active_page_table & active_table) - -> virtual_address - { - exception_handling::assert(!active_table.translate_page(page).has_value(), - "[Temporary page] Page is already mapped"); - - active_table.map_page_to_frame(allocator, page, frame, entry::WRITABLE); - return page.start_address(); - } - - auto temporary_page::unmap_page(active_page_table & active_table) -> void - { - active_table.unmap_page(allocator, page); - } -} // namespace teachos::arch::memory::paging diff --git a/arch/x86_64/src/memory/paging/virtual_page.cpp b/arch/x86_64/src/memory/paging/virtual_page.cpp deleted file mode 100644 index d374156..0000000 --- a/arch/x86_64/src/memory/paging/virtual_page.cpp +++ /dev/null @@ -1,33 +0,0 @@ -#include "arch/memory/paging/virtual_page.hpp" - -#include "arch/exception_handling/assert.hpp" - -namespace teachos::arch::memory::paging -{ - auto virtual_page::containing_address(virtual_address address) -> virtual_page - { - exception_handling::assert(address < 0x00008000'00000000 || address >= 0xffff8000'00000000, - "[Virtual Page] Attempted to create virtual page from invalid address"); - return virtual_page{address / allocator::PAGE_FRAME_SIZE}; - } - - auto virtual_page::start_address() const -> virtual_address { return page_number * allocator::PAGE_FRAME_SIZE; } - - auto virtual_page::get_level_index(page_table_handle::level level) const -> size_t - { - return (page_number >> (level * 9U)) & 0x1FF; - } - - auto virtual_page::operator++(int) -> virtual_page - { - virtual_page const old_value = *this; - ++page_number; - return old_value; - } - - auto virtual_page::operator++() -> virtual_page & - { - ++page_number; - return *this; - } -} // namespace teachos::arch::memory::paging diff --git a/arch/x86_64/src/memory/paging_root.cpp b/arch/x86_64/src/memory/paging_root.cpp new file mode 100644 index 0000000..d849a82 --- /dev/null +++ b/arch/x86_64/src/memory/paging_root.cpp @@ -0,0 +1,19 @@ +#include "x86_64/memory/paging_root.hpp" + +#include <bit> +#include <cstdint> + +namespace teachos::memory::x86_64 +{ + + namespace + { + constexpr auto recursive_base = std::uintptr_t{0177777'776'776'776'776'0000uz}; + } // namespace + + auto paging_root::get() -> paging_root * + { + return std::bit_cast<paging_root *>(recursive_base); + } + +} // namespace teachos::memory::x86_64
\ No newline at end of file diff --git a/arch/x86_64/src/memory/recursive_page_mapper.cpp b/arch/x86_64/src/memory/recursive_page_mapper.cpp new file mode 100644 index 0000000..c5aabcb --- /dev/null +++ b/arch/x86_64/src/memory/recursive_page_mapper.cpp @@ -0,0 +1,119 @@ +#include "x86_64/memory/recursive_page_mapper.hpp" + +#include "kapi/memory.hpp" +#include "kapi/system.hpp" + +#include "x86_64/memory/page_table.hpp" +#include "x86_64/memory/page_utilities.hpp" +#include "x86_64/memory/paging_root.hpp" + +#include <cstddef> +#include <optional> + +namespace teachos::memory::x86_64 +{ + namespace + { + //! Perform the actual mapping of the page, via the recursive page map. + //! + //! On any level above PML1, the entries need to not be no_execute, because the image is densely packed. The entries + //! also need to be writable, since the mapping is being performed through the recursive page map hierarchy. When + //! setting the final entry in the PML1, the actually desired flags are set as is, with the present bit + //! added, thus still enforcing non-writability and non-execution of the affected page. + template<std::size_t Level> + requires(Level > 1uz && Level <= PLATFORM_PAGING_LEVELS) + auto do_map(recursive_page_table<Level> * pml, page page, frame_allocator & allocator, page_mapper::flags flags) + { + auto index = pml_index<Level>(page); + auto entry_flags = to_table_flags(flags); + + entry_flags = entry_flags & ~page_table::entry::flags::no_execute; + entry_flags = entry_flags | page_table::entry::flags::writable; + if (!(*pml)[index].present()) + { + auto new_table_frame = allocator.allocate(); + (*pml)[index].frame(new_table_frame.value(), page_table::entry::flags::present | entry_flags); + auto new_table = std::optional{std::construct_at(*pml->next(index))}; + return new_table; + } + (*pml)[index] |= entry_flags; + return pml->next(index); + } + + //! Perform the actual PML1 update. + auto do_map(page_table * pml, page page, frame frame, page_mapper::flags flags) -> std::optional<std::byte *> + { + auto index = pml_index<1>(page); + if ((*pml)[index].present()) + { + system::panic("[x86_64:MEM] Tried to map a page that is already mapped"); + } + (*pml)[index].frame(frame, page_table::entry::flags::present | to_table_flags(flags)); + return std::optional{static_cast<std::byte *>(page.start_address())}; + } + + } // namespace + + recursive_page_mapper::recursive_page_mapper(frame_allocator & allocator) + : m_allocator{&allocator} + {} + + auto recursive_page_mapper::map(page page, frame frame, flags flags) -> std::byte * + { + auto pml4 = static_cast<recursive_page_table<4> *>((paging_root::get())); + + return std::optional{pml4} + .and_then([&](auto pml) -> auto { return do_map(pml, page, *m_allocator, flags); }) + .and_then([&](auto pml) -> auto { return do_map(pml, page, *m_allocator, flags); }) + .and_then([&](auto pml) -> auto { return do_map(pml, page, *m_allocator, flags); }) + .and_then([&](auto pml) -> auto { return do_map(pml, page, frame, flags); }) + .value_or(nullptr); + } + + auto recursive_page_mapper::unmap(page page) -> void + { + if (!try_unmap(page)) + { + system::panic("[x86_64:MEM] Tried to unmap a page that was not mapped."); + } + } + + auto recursive_page_mapper::try_unmap(page page) noexcept -> bool + { + if (!paging_root::get()->translate(page)) + { + return false; + } + + auto pml4 = paging_root::get(); + auto pml3 = pml4->next(pml_index<4>(page)).value(); + auto pml2 = pml3->next(pml_index<3>(page)).value(); + auto pml1 = pml2->next(pml_index<2>(page)).value(); + + (*pml1)[pml_index<1>(page)].clear(); + + if (pml1->empty()) + { + auto pml1_frame = (*pml2)[pml_index<2>(page)].frame().value(); + m_allocator->release(pml1_frame); + (*pml2)[pml_index<2>(page)].clear(); + } + + if (pml2->empty()) + { + auto pml2_frame = (*pml3)[pml_index<3>(page)].frame().value(); + m_allocator->release(pml2_frame); + (*pml3)[pml_index<3>(page)].clear(); + } + + if (pml3->empty()) + { + auto pml3_frame = (*pml4)[pml_index<4>(page)].frame().value(); + m_allocator->release(pml3_frame); + (*pml4)[pml_index<4>(page)].clear(); + } + + return true; + } + +} // namespace teachos::memory::x86_64
\ No newline at end of file diff --git a/arch/x86_64/src/memory/region_allocator.cpp b/arch/x86_64/src/memory/region_allocator.cpp new file mode 100644 index 0000000..0f65b3a --- /dev/null +++ b/arch/x86_64/src/memory/region_allocator.cpp @@ -0,0 +1,92 @@ +#include "x86_64/memory/region_allocator.hpp" + +#include "kapi/memory/address.hpp" +#include "kapi/memory/frame.hpp" + +#include <multiboot2/information.hpp> + +#include <algorithm> +#include <optional> +#include <ranges> +#include <utility> + +namespace teachos::memory::x86_64 +{ + namespace + { + constexpr auto last_frame(multiboot2::memory_map::region const & region) + { + return frame::containing(physical_address{region.base + region.size_in_B - 1}); + } + + constexpr auto falls_within(frame const & candidate, frame const & start, frame const & end) + { + return candidate >= start && candidate <= end; + } + } // namespace + + region_allocator::region_allocator(memory_information const & mem_info) + : m_next_frame{} + , m_current_region{} + , m_memory_map{mem_info.memory_map} + , m_kernel_start(frame::containing(mem_info.image_range.first)) + , m_kernel_end(frame::containing(mem_info.image_range.second)) + , m_multiboot_start(frame::containing(mem_info.mbi_range.first)) + , m_multiboot_end(frame::containing(mem_info.mbi_range.second)) + { + choose_next_area(); + } + + auto region_allocator::choose_next_area() -> void + { + m_current_region.reset(); + auto next_area_with_free_frames = + m_memory_map | std::views::filter(&multiboot2::memory_map::region::available) | + std::views::filter([next = m_next_frame](auto const & region) -> bool { return last_frame(region) >= next; }); + + auto lowest_region_with_free_frames = std::ranges::min_element( + next_area_with_free_frames, [](auto lhs, auto rhs) -> bool { return lhs.base < rhs.base; }); + + if (lowest_region_with_free_frames != next_area_with_free_frames.end()) + { + m_current_region = *lowest_region_with_free_frames; + auto start_frame = frame::containing(physical_address{m_current_region->base}); + if (m_next_frame < start_frame) + { + m_next_frame = start_frame; + } + } + } + + auto region_allocator::allocate() noexcept -> std::optional<frame> + { + if (!m_current_region) + { + return {}; + } + + auto const end_address = physical_address{m_current_region->base + m_current_region->size_in_B - 1}; + auto end_frame = frame::containing(end_address); + + if (m_next_frame > end_frame) + { + choose_next_area(); + } + else if (falls_within(m_next_frame, m_kernel_start, m_kernel_end)) + { + m_next_frame = m_kernel_end + 1; + } + else if (falls_within(m_next_frame, m_multiboot_start, m_multiboot_end)) + { + m_next_frame = m_multiboot_end + 1; + } + else + { + return m_next_frame++; + } + + return allocate(); + } + + auto region_allocator::release(frame) -> void {} +} // namespace teachos::memory::x86_64 diff --git a/arch/x86_64/src/memory/scoped_mapping.cpp b/arch/x86_64/src/memory/scoped_mapping.cpp new file mode 100644 index 0000000..a86aaed --- /dev/null +++ b/arch/x86_64/src/memory/scoped_mapping.cpp @@ -0,0 +1,69 @@ +#include "x86_64/memory/scoped_mapping.hpp" + +#include "kapi/memory.hpp" +#include "kapi/system.hpp" + +#include "x86_64/memory/mmu.hpp" +#include "x86_64/memory/page_table.hpp" +#include "x86_64/memory/paging_root.hpp" + +#include <cstddef> +#include <utility> + +namespace teachos::memory::x86_64 +{ + + scoped_mapping::scoped_mapping(scoped_mapping && other) noexcept + : m_page{std::exchange(other.m_page, page{})} + , m_mapper{std::exchange(other.m_mapper, nullptr)} + , m_mapped{std::exchange(other.m_mapped, false)} + {} + + scoped_mapping::scoped_mapping(page page, page_mapper & mapper) + : m_page{page} + , m_mapper{&mapper} + , m_mapped{false} + { + if (paging_root::get()->translate(page)) + { + system::panic("[MEM] Tried to map a page that is already mapped!"); + } + } + + scoped_mapping::~scoped_mapping() + { + if (m_mapped) + { + unmap(); + x86_64::tlb_flush(m_page.start_address()); + } + } + + auto scoped_mapping::operator=(scoped_mapping && other) noexcept -> scoped_mapping & + { + swap(*this, other); + return *this; + } + + auto scoped_mapping::map(frame frame, page_table::entry::flags flags) -> std::byte * + { + auto result = m_mapper->map(m_page, frame, to_mapper_flags(flags)); + m_mapped = true; + return result; + } + + auto scoped_mapping::unmap() -> void + { + m_mapper->unmap(m_page); + m_mapped = false; + } + + auto swap(scoped_mapping & lhs, scoped_mapping & rhs) -> void + { + using std::swap; + swap(lhs.m_page, rhs.m_page); + swap(lhs.m_mapper, rhs.m_mapper); + swap(lhs.m_mapped, rhs.m_mapped); + } + +} // namespace teachos::memory::x86_64
\ No newline at end of file |