diff options
| -rw-r--r-- | arch/x86_64/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp | 2 | ||||
| -rw-r--r-- | arch/x86_64/include/arch/memory/allocator/stack_frame_allocator.hpp | 67 | ||||
| -rw-r--r-- | arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp | 2 | ||||
| -rw-r--r-- | arch/x86_64/include/arch/stl/stack.hpp | 179 | ||||
| -rw-r--r-- | arch/x86_64/include/arch/stl/vector.hpp | 82 | ||||
| -rw-r--r-- | arch/x86_64/src/context_switching/main.cpp | 4 | ||||
| -rw-r--r-- | arch/x86_64/src/memory/allocator/area_frame_allocator.cpp | 2 | ||||
| -rw-r--r-- | arch/x86_64/src/memory/allocator/stack_frame_allocator.cpp | 105 | ||||
| -rw-r--r-- | arch/x86_64/src/memory/main.cpp | 20 |
10 files changed, 433 insertions, 31 deletions
diff --git a/arch/x86_64/CMakeLists.txt b/arch/x86_64/CMakeLists.txt index 8f5b9bd..71b1946 100644 --- a/arch/x86_64/CMakeLists.txt +++ b/arch/x86_64/CMakeLists.txt @@ -54,6 +54,7 @@ target_sources("_memory" PRIVATE "src/memory/multiboot/elf_symbols_section.cpp" "src/memory/multiboot/reader.cpp" "src/memory/allocator/area_frame_allocator.cpp" + "src/memory/allocator/stack_frame_allocator.cpp" "src/memory/allocator/tiny_frame_allocator.cpp" "src/memory/allocator/physical_frame.cpp" "src/memory/paging/page_entry.cpp" diff --git a/arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp b/arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp index b8370db..2244613 100644 --- a/arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp +++ b/arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp @@ -55,7 +55,7 @@ namespace teachos::arch::memory::allocator physical_frame next_free_frame; ///< The physical_frame after the last allocated one. std::optional<multiboot::memory_area> current_area; ///< The current memory area. multiboot::memory_area_container const - memory_areas; ///< All memory areas in custom container allows to use std::ranges + memory_areas; ///< All memory areas in custom container allows to use std::ranges. physical_frame const kernel_start; ///< The start address of the kernel code in memory. physical_frame const kernel_end; ///< The end address of the kernel code in memory. physical_frame const multiboot_start; ///< The start address of the multiboot code in memory. diff --git a/arch/x86_64/include/arch/memory/allocator/stack_frame_allocator.hpp b/arch/x86_64/include/arch/memory/allocator/stack_frame_allocator.hpp new file mode 100644 index 0000000..a8e7233 --- /dev/null +++ b/arch/x86_64/include/arch/memory/allocator/stack_frame_allocator.hpp @@ -0,0 +1,67 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_STACK_FRAME_ALLOCATOR_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_STACK_FRAME_ALLOCATOR_HPP + +#include "arch/memory/allocator/physical_frame.hpp" +#include "arch/memory/multiboot/reader.hpp" +#include "arch/stl/stack.hpp" + +#include <optional> + +namespace teachos::arch::memory::allocator +{ + /** + * @brief Uses an internal stack-like dynamic structure to keep track of the address of all avaialable physical frames + * that are available using the memory areas read from the multiboot2 information pointer and simply pushes + * deallocated frames back onto the stack. Allows for constant speed O(1) allocation and deallocation + */ + struct stack_frame_allocator + { + /** + * @brief Constructor + * + * @param mem_info Structure containg all relevant information to map and allocate memory + */ + stack_frame_allocator(multiboot::memory_information const & mem_info); + + /** + * @brief Allocate memory by finding and returning a free physical frame. + * + * @return next free physical frame or nullopt if none was found. + */ + auto allocate_frame() -> std::optional<physical_frame>; + + /** + * @brief Deallocates a previously allocated physical frame. + * + * @param physical_frame Previously allocated physical_frame that should be deallocated. + */ + auto deallocate_frame(physical_frame const & physical_frame) -> void; + + private: + /** + * @brief Load all initally free physical frames from the current memory area into the underlying stack data + * structure so they can simply be accessed once required. Recallling the method will load all free physical frames + * from the next free memory area until there are no memory areas left. + */ + auto load_free_physical_frames() -> void; + + /** + * @brief Find the next memory area and write it into current_area. + */ + auto choose_next_area() -> void; + + stl::stack<physical_frame> free_frames; ///< All currently free physical frames in a LIFO (last-in, first-out) + ///< data structure. + physical_frame next_free_frame; ///< The physical_frame after the last allocated one. + std::optional<multiboot::memory_area> current_area; ///< The current memory area. + multiboot::memory_area_container const + memory_areas; ///< All memory areas in custom container allows to use std::ranges. + physical_frame const kernel_start; ///< The start address of the kernel code in memory. + physical_frame const kernel_end; ///< The end address of the kernel code in memory. + physical_frame const multiboot_start; ///< The start address of the multiboot code in memory. + physical_frame const multiboot_end; ///< The end address of the multiboot code in memory. + }; + +} // namespace teachos::arch::memory::allocator + +#endif // TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_STACK_FRAME_ALLOCATOR_HPP diff --git a/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp b/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp index dff837e..772f171 100644 --- a/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp +++ b/arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp @@ -16,7 +16,7 @@ namespace teachos::arch::memory::heap BUMP, ///< Use the bump allocator as the heap allocation implementation, be aware that using this allocator leaks ///< memory, because there is no delete implementation LINKED_LIST ///< Use the linked list allocator as the heap implementation, recommended because it does not leak - ///< memory and + ///< memory }; /** diff --git a/arch/x86_64/include/arch/stl/stack.hpp b/arch/x86_64/include/arch/stl/stack.hpp new file mode 100644 index 0000000..c78a25e --- /dev/null +++ b/arch/x86_64/include/arch/stl/stack.hpp @@ -0,0 +1,179 @@ +#ifndef TEACHOS_ARCH_X86_64_STL_STACK_HPP +#define TEACHOS_ARCH_X86_64_STL_STACK_HPP + +#include "arch/exception_handling/panic.hpp" +#include "arch/stl/vector.hpp" + +#include <algorithm> +#include <concepts> + +namespace teachos::arch::stl +{ + /** + * @brief Custom stack implementation mirroring the std::stack to allow for the usage of STL functionality with our + * custom memory management. + * + * @tparam T Element the stack instance should contain. + */ + template<typename T, typename Container = stl::vector<T>> + struct stack + { + /** + * @brief Default Constructor. + */ + stack() = default; + + /** + * @brief Constructs data with the given amount of elements containg the given value or alterantively the default + * constructed value. + * + * @param capacity Amount of elements we want to create and set the given value for. + * @param initial Inital value of all elements in the underlying data array. + */ + explicit stack(std::size_t capacity, T initial = T{}) + : _container(capacity, initial) + { + // Nothing to do. + } + + /** + * @brief Constructs data by copying all element from the given exclusive range. + * + * @tparam InputIterator Template that should have atleast input iterator characteristics. + * @param first Input iterator to the first element in the range we want to copy from. + * @param last Input iterator to one past the last element in the range we want to copy from. + */ + template<typename InputIterator> + explicit stack(InputIterator first, InputIterator last) + : _container(first, last) + { + // Nothing to do. + } + + /** + * @brief Construct data by copying all elements from the initializer list. + * + * @param initalizer_list List we want to copy all elements from. + */ + explicit stack(std::initializer_list<T> initalizer_list) + : _container(initalizer_list) + { + // Nothing to do. + } + + /** + * @brief Copy constructor. + * + * @note Allocates underlying data container with the same capacity as vector we are copying from and copies all + * elements from it. + * + * @param other Other instance of vector we want to copy the data from. + */ + stack(stack<T> const & other) + : _container(other) + { + // Nothing to do. + } + + /** + * @brief Copy assignment operator. + * + * @note Allocates underlying data container with the same capacity as vector we are copying from and copies all + * elements from it. + * + * @param other Other instance of vector we want to copy the data from. + * @return Newly created copy. + */ + stack<T> & operator=(stack<T> const & other) { _container = other; } + + /** + * @brief Destructor. + */ + ~stack() = default; + + /** + * @brief Amount of elements currently contained in this vector, will fill up until we have reached the capacity. If + * that is the case the capacity is increased automatically. + * + * @return Current amount of elements. + */ + std::size_t size() const { return _container.size(); } + + /** + * @brief Returns a reference to the last element in the container. Calling back on an empty container causes + * undefined behavior. + * + * @return Reference to the last element. + */ + T & top() { return _container.back(); } + + /** + * @brief Returns a reference to the last element in the container. Calling back on an empty container causes + * undefined behavior. + * + * @return Reference to the last element. + */ + T const & top() const { return _container.back(); } + + /** + * @brief Appends the given element value to the end of the container. The new element is initalized as a copy of + * value. + * + * @note If after the operation the new size() is greater than old capacity() a reallocation takes place, + * in which case all iterators (including the end() iterator) and all references to the elements are invalidated. + * Otherwise only the end() iterator is invalidated. + * + * @param value The value of the element to append. + */ + void push(T const & value) { _container.push_back(value); } + + /** + * @brief Appends the given element value to the end of the container. Value is moved into the new element. + * + * @note If after the operation the new size() is greater than old capacity() a reallocation takes place, + * in which case all iterators (including the end() iterator) and all references to the elements are invalidated. + * Otherwise only the end() iterator is invalidated. + * + * @param value The value of the element to append. + */ + void push(T && value) { _container.push_back(std::move(value)); } + + /** + * @brief Appends a new element to the end of the container. The element is constructed through a constructor of the + * template type. The arguments args... are forwarded to the constructor as std::forward<Args>(args).... + * + * If after the operation the new size() is greater than old capacity() a reallocation takes place, in which case + * all iterators (including the end() iterator) and all references to the elements are invalidated. Otherwise only + * the end() iterator is invalidated. + * + * @tparam Args + * @param args Arguments to forward to the constructor of the element + * @return T& + */ + template<class... Args> + auto emplace(Args &&... args) -> T & + { + _container.emplace_back(std::forward<Args>(args)...); + } + + /** + * @brief Removes the last element of the container. Calling pop_back on an empty container results in halting the + * further execution. Iterators and references to the last element are invalidated. The end() + * iterator is also invalidated. + */ + void pop() { _container.pop_back(); } + + /** + * @brief Wheter there are currently any items this container or not. + * + * @return True if there are no elements, false if there are. + */ + auto empty() const -> bool { return _container.empty(); } + + private: + Container _container = {}; ///< Underlying container used by the stack to actually save the data. + }; + +} // namespace teachos::arch::stl + +#endif // TEACHOS_ARCH_X86_64_STL_STACK_HPP diff --git a/arch/x86_64/include/arch/stl/vector.hpp b/arch/x86_64/include/arch/stl/vector.hpp index f3d41fd..e14f2c9 100644 --- a/arch/x86_64/include/arch/stl/vector.hpp +++ b/arch/x86_64/include/arch/stl/vector.hpp @@ -162,13 +162,9 @@ namespace teachos::arch::stl */ void push_back(T const & value) { - if (_size == _capacity) - { - reserve(_capacity * 2); - } - + increase_capacity_if_full(); _data[_size] = value; - _size++; + (void)_size++; } /** @@ -182,11 +178,7 @@ namespace teachos::arch::stl */ void push_back(T && value) { - if (_size == _capacity) - { - reserve(_capacity * 2); - } - + increase_capacity_if_full(); _data[_size] = std::move(value); _size++; } @@ -206,11 +198,7 @@ namespace teachos::arch::stl template<class... Args> auto emplace_back(Args &&... args) -> T & { - if (_size == _capacity) - { - reserve(_capacity * 2); - } - + increase_capacity_if_full(); _data[_size] = T{std::forward<Args>(args)...}; auto const index = _size++; return _data[index]; @@ -223,11 +211,8 @@ namespace teachos::arch::stl */ void pop_back() { - if (_size <= 0) - { - exception_handling::panic("[Vector] Attempted to pop back last element of already empty vector"); - } - _size--; + throw_if_empty(); + (void)_size--; } /** @@ -355,7 +340,11 @@ namespace teachos::arch::stl * * @return Reference to the first element. */ - T & front() { return *begin(); } + T & front() + { + throw_if_empty(); + return *begin(); + } /** * @brief Returns a reference to the first element in the container. Calling front on an empty container causes @@ -363,7 +352,11 @@ namespace teachos::arch::stl * * @return Reference to the first element. */ - T const & front() const { return *begin(); } + T const & front() const + { + throw_if_empty(); + return *begin(); + } /** * @brief Returns a reference to the last element in the container. Calling back on an empty container causes @@ -371,7 +364,11 @@ namespace teachos::arch::stl * * @return Reference to the last element. */ - T & back() { return *rbegin(); } + T & back() + { + throw_if_empty(); + return *rbegin(); + } /** * @brief Returns a reference to the last element in the container. Calling back on an empty container causes @@ -379,7 +376,11 @@ namespace teachos::arch::stl * * @return Reference to the last element. */ - T const & back() const { return *rbegin(); } + T const & back() const + { + throw_if_empty(); + return *rbegin(); + } /** * @brief Increase the capacity of the vector (the total number of elements that the vector can hold without @@ -442,7 +443,38 @@ namespace teachos::arch::stl _data = temp; } + /** + * @brief Wheter there are currently any items this container or not. + * + * @return True if there are no elements, false if there are. + */ + auto empty() const -> bool { return _size <= 0; } + private: + /** + * @brief Halts the execution of the application if the data container is currently empty. + */ + auto throw_if_empty() const -> void + { + if (empty()) + { + exception_handling::panic("[Vector] Attempted to access element of currently empty vector"); + } + } + + /** + * @brief Increases the internal capacity to 1 if it was previously 0 and to * 2 after that, meaning exponential + * growth. This is done to decrease the amount of single allocations done and because a power of 2 in memory size is + * normally perferable for the cache. + */ + auto increase_capacity_if_full() -> void + { + if (_size == _capacity) + { + reserve(_capacity == 0U ? 1U : _capacity * 2U); + } + } + std::size_t _size = {}; ///< Amount of elements in the underlying data container std::size_t _capacity = {}; ///< Amount of space for elements in the underlying data container T * _data = {}; ///< Pointer to the first element in the underlying data container diff --git a/arch/x86_64/src/context_switching/main.cpp b/arch/x86_64/src/context_switching/main.cpp index 952a3b2..486a09f 100644 --- a/arch/x86_64/src/context_switching/main.cpp +++ b/arch/x86_64/src/context_switching/main.cpp @@ -21,6 +21,8 @@ namespace teachos::arch::context_switching constexpr context_switching::interrupt_descriptor_table::segment_selector USER_DATA_SEGMENT_SELECTOR{ 4U, context_switching::interrupt_descriptor_table::segment_selector::REQUEST_LEVEL_USER}; + auto reload_global_descriptor_table_register() -> void { kernel::cpu::call(KERNEL_CODE_POINTER); } + } // namespace auto initialize_descriptor_tables() -> descriptor_tables @@ -34,7 +36,7 @@ namespace teachos::arch::context_switching segment_descriptor_table::update_global_descriptor_table_register(); interrupt_descriptor_table::update_interrupt_descriptor_table_register(); - kernel::cpu::call(KERNEL_CODE_POINTER); + reload_global_descriptor_table_register(); segment_descriptor_table::update_task_state_segment_register(); kernel::cpu::set_interrupt_flag(); diff --git a/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp b/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp index cb4fefa..a5a1b49 100644 --- a/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp +++ b/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp @@ -9,7 +9,7 @@ namespace teachos::arch::memory::allocator { area_frame_allocator::area_frame_allocator(multiboot::memory_information const & mem_info) - : next_free_frame(0U) + : next_free_frame() , current_area(std::nullopt) , memory_areas(mem_info.areas) , kernel_start(physical_frame::containing_address(mem_info.kernel_start)) diff --git a/arch/x86_64/src/memory/allocator/stack_frame_allocator.cpp b/arch/x86_64/src/memory/allocator/stack_frame_allocator.cpp new file mode 100644 index 0000000..0fa277a --- /dev/null +++ b/arch/x86_64/src/memory/allocator/stack_frame_allocator.cpp @@ -0,0 +1,105 @@ +#include "arch/memory/allocator/stack_frame_allocator.hpp" + +#include "arch/exception_handling/assert.hpp" + +#include <algorithm> +#include <array> +#include <ranges> + +namespace teachos::arch::memory::allocator +{ + stack_frame_allocator::stack_frame_allocator(multiboot::memory_information const & mem_info) + : free_frames() + , 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)) + { + load_free_physical_frames(); + } + + auto stack_frame_allocator::load_free_physical_frames() -> void + { + choose_next_area(); + if (!current_area.has_value()) + { + return; + } + + auto const address = current_area.value().base_address + current_area.value().area_length - 1; + physical_frame const current_area_last_frame = physical_frame::containing_address(address); + + // Only try to allocate memory if current_area is not null, because + // the current_area is null if there is no more available memory. + while (next_free_frame <= current_area_last_frame) + { + 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; + // TODO: Fix using heap like structure to initalize paging allocator used by heap does not work + // free_frames.push(next_free_frame); + static uint32_t count = 0U; + count++; + } + } + } + + auto stack_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 stack_frame_allocator::allocate_frame() -> std::optional<physical_frame> + { + // If the underlying stack is empty that are no free frames left to allocate. + if (free_frames.empty()) + { + load_free_physical_frames(); + if (free_frames.empty()) + { + return std::nullopt; + } + } + + decltype(auto) top = free_frames.top(); + free_frames.pop(); + return top; + } + + auto stack_frame_allocator::deallocate_frame(physical_frame const & physical_frame) -> void + { + free_frames.push(physical_frame); + } +} // namespace teachos::arch::memory::allocator diff --git a/arch/x86_64/src/memory/main.cpp b/arch/x86_64/src/memory/main.cpp index a920a20..3041a75 100644 --- a/arch/x86_64/src/memory/main.cpp +++ b/arch/x86_64/src/memory/main.cpp @@ -4,6 +4,8 @@ #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/allocator/stack_frame_allocator.hpp" #include "arch/memory/heap/heap_allocator.hpp" #include "arch/memory/paging/active_page_table.hpp" #include "arch/memory/paging/kernel_mapper.hpp" @@ -12,7 +14,21 @@ namespace teachos::arch::memory { namespace { - auto remap_heap(allocator::area_frame_allocator allocator, paging::active_page_table & active_table) -> void + template<allocator::FrameAllocator T> + auto create_frame_allocator(multiboot::memory_information const & memory_information) -> T + { + return allocator::area_frame_allocator{memory_information}; + } + + template<> + auto create_frame_allocator(multiboot::memory_information const & memory_information) + -> allocator::stack_frame_allocator + { + return allocator::stack_frame_allocator{memory_information}; + } + + template<allocator::FrameAllocator T> + auto remap_heap(T & allocator, paging::active_page_table & active_table) -> void { auto const start_page = paging::virtual_page::containing_address(memory::heap::HEAP_START); auto const end_page = @@ -36,7 +52,7 @@ namespace teachos::arch::memory has_been_called = true; auto const memory_information = multiboot::read_multiboot2(); - allocator::area_frame_allocator allocator(memory_information); + auto allocator = create_frame_allocator<allocator::stack_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); |