diff options
Diffstat (limited to 'arch/x86_64/include')
5 files changed, 305 insertions, 27 deletions
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 |