aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--arch/x86_64/CMakeLists.txt1
-rw-r--r--arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp2
-rw-r--r--arch/x86_64/include/arch/memory/allocator/stack_frame_allocator.hpp67
-rw-r--r--arch/x86_64/include/arch/memory/heap/global_heap_allocator.hpp2
-rw-r--r--arch/x86_64/include/arch/stl/deque.hpp524
-rw-r--r--arch/x86_64/include/arch/stl/stack.hpp182
-rw-r--r--arch/x86_64/include/arch/stl/vector.hpp244
-rw-r--r--arch/x86_64/src/context_switching/main.cpp4
-rw-r--r--arch/x86_64/src/memory/allocator/area_frame_allocator.cpp2
-rw-r--r--arch/x86_64/src/memory/allocator/stack_frame_allocator.cpp105
-rw-r--r--arch/x86_64/src/memory/main.cpp20
11 files changed, 1055 insertions, 98 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/deque.hpp b/arch/x86_64/include/arch/stl/deque.hpp
new file mode 100644
index 0000000..b4a3054
--- /dev/null
+++ b/arch/x86_64/include/arch/stl/deque.hpp
@@ -0,0 +1,524 @@
+#ifndef TEACHOS_ARCH_X86_64_STL_DEQUE_HPP
+#define TEACHOS_ARCH_X86_64_STL_DEQUE_HPP
+
+#include "arch/exception_handling/panic.hpp"
+
+#include <algorithm>
+#include <array>
+
+namespace teachos::arch::stl
+{
+ /**
+ * @brief Custom deque implementation mirroring the std::deque to allow for the usage of STL functionality with our
+ * custom memory management.
+ *
+ * @tparam T Element the deque instance should contain.
+ */
+ template<typename T>
+ struct deque
+ {
+ using value_type = T; ///< Type of the elements contained in the container.
+ using size_type = std::size_t; ///< Type of the size in the container.
+ using reference = value_type &; ///< Type of reference to the elements.
+ using const_reference = value_type const &; ///< Type of constant reference to the elements.
+ using pointer = value_type *; ///< Type of pointer to the elements.
+ using const_pointer = value_type const *; ///< Type of constant pointer to the elements.
+
+ /**
+ * @brief Deque block for the linked list, either added or removed if more or less space is required.
+ */
+ struct block
+ {
+ std::array<value_type, 8U> data; ///< Data this block in the deque contains
+ block * next; ///< Optional pointer to the next free memory, holds nullptr if there is none.
+ };
+
+ /**
+ * @brief Default Constructor.
+ */
+ deque() = default;
+
+ /**
+ * @brief Constructs data with the given amount of elements containg the given value or alterantively the default
+ * constructed value.
+ *
+ * @param n 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 deque(size_type n, value_type initial = value_type{})
+ : _size(n)
+ , _capacity(n)
+ , _linked_list_start()
+ {
+ std::array<value_type, 8U> data{};
+ std::ranges::fill_n(data, n, initial);
+ block block{data, nullptr};
+ _linked_list_start =
+ &block; // Taking reference to temporary, how would this be saved without causing issues later?
+ }
+
+ /**
+ * @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 deque(InputIterator first, InputIterator last)
+ : _size(std::distance(first, last))
+ , _capacity(std::distance(first, last))
+ , _linked_list_start()
+ {
+ std::array<value_type, 8U> data{};
+ stl::container<InputIterator> container{first, last};
+ std::ranges::copy(container, data.begin());
+ block block{data, nullptr};
+ _linked_list_start = &block;
+ }
+
+ /**
+ * @brief Construct data by copying all elements from the initializer list.
+ *
+ * @param initalizer_list List we want to copy all elements from.
+ */
+ explicit deque(std::initializer_list<value_type> initalizer_list)
+ : _size(initalizer_list.size())
+ , _capacity(initalizer_list.size())
+ , _data(new value_type[_capacity]{})
+ {
+ std::ranges::copy(initalizer_list, _data);
+ }
+
+ /**
+ * @brief Copy constructor.
+ *
+ * @note Allocates underlying data container with the same capacity as deque we are copying from and copies all
+ * elements from it.
+ *
+ * @param other Other instance of deque we want to copy the data from.
+ */
+ deque(deque<value_type> const & other)
+ : _size(other._size)
+ , _capacity(other._capacity)
+ {
+ delete[] _data;
+ _data = new value_type[_capacity]{};
+ std::ranges::copy(other, _data);
+ }
+
+ /**
+ * @brief Copy assignment operator.
+ *
+ * @note Allocates underlying data container with the same capacity as deque we are copying from and copies all
+ * elements from it.
+ *
+ * @param other Other instance of deque we want to copy the data from.
+ * @return Newly created copy.
+ */
+ deque<value_type> & operator=(deque<value_type> const & other)
+ {
+ delete[] _data;
+ _size = other._size;
+ _capacity = other._capacity;
+ _data = new value_type[_capacity]{};
+ std::ranges::copy(other, _data);
+ return *this;
+ }
+
+ /**
+ * @brief Destructor.
+ */
+ ~deque() { delete[] _data; }
+
+ /**
+ * @brief Amount of elements currently contained in this deque, will fill up until we have reached the capacity. If
+ * that is the case the capacity is increased automatically.
+ *
+ * @return Current amount of elements.
+ */
+ auto size() const -> size_type { return _size; }
+
+ /**
+ * @brief Amount of space the deque currently has, can be different than the size, because we allocate more than we
+ * exactly require to decrease the amount of allocations and deallocation to improve speed.
+ *
+ * @return Current amount of space the deque has for elements.
+ */
+ auto capacity() const -> size_type { return _capacity; }
+
+ /**
+ * @brief Array indexing operator. Allowing to access element at the given index.
+ *
+ * @note Does not do any bounds checks use at() for that.
+ *
+ * @param index Index we want to access elements at.
+ * @return Reference to the underlying element.
+ */
+ auto operator[](size_type index) -> reference { return _data[index]; }
+
+ /**
+ * @brief Array indexing operator. Allowing to access element at the given index.
+ *
+ * @note Does not do any bounds checks use at() for that.
+ *
+ * @param index Index we want to access elements at.
+ * @return Reference to the underlying element.
+ */
+ auto operator[](size_type index) const -> const_reference { return _data[index]; }
+
+ /**
+ * @brief Array indexing operator. Allowing to access element at the given index.
+ *
+ * @note Ensures we do not access element outside of the bounds of the array, if we do further execution is halted.
+ *
+ * @param index Index we want to access elements at.
+ * @return Reference to the underlying element.
+ */
+ auto at(size_type index) -> reference
+ {
+ throw_if_out_of_range(index);
+ return this->operator[](index);
+ }
+
+ /**
+ * @brief Array indexing operator. Allowing to access element at the given index.
+ *
+ * @note Ensures we do not access element outside of the bounds of the array, if we do further execution is halted.
+ *
+ * @param index Index we want to access elements at.
+ * @return Reference to the underlying element.
+ */
+ auto at(size_type index) const -> const_reference
+ {
+ throw_if_out_of_range(index);
+ return this->operator[](index);
+ }
+
+ /**
+ * @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.
+ */
+ template<class U>
+ auto push_back(U && value) -> void
+ {
+ increase_capacity_if_full();
+ _data[_size] = std::forward<U>(value);
+ (void)_size++;
+ }
+
+ /**
+ * @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 value_type&
+ */
+ template<class... Args>
+ auto emplace_back(Args &&... args) -> value_type &
+ {
+ increase_capacity_if_full();
+ _data[_size] = value_type{std::forward<Args>(args)...};
+ auto const index = _size++;
+ return _data[index];
+ }
+
+ /**
+ * @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.
+ */
+ auto pop_back() -> void
+ {
+ throw_if_empty();
+ (void)_size--;
+ }
+
+ /**
+ * @brief Returns an iterator to the first element of the deque.
+ * If the deque is empty, the returned iterator will be equal to end().
+ *
+ * @return Iterator to the first element.
+ */
+ auto begin() noexcept -> pointer { return _data; }
+
+ /**
+ * @brief Returns an iterator to the first element of the deque.
+ * If the deque is empty, the returned iterator will be equal to end().
+ *
+ * @return Iterator to the first element.
+ */
+ auto begin() const noexcept -> const_pointer { return _data; }
+
+ /**
+ * @brief Returns an iterator to the first element of the deque.
+ * If the deque is empty, the returned iterator will be equal to end().
+ *
+ * @return Iterator to the first element.
+ */
+ auto cbegin() const noexcept -> const_pointer { return begin(); }
+
+ /**
+ * @brief Returns a reverse iterator to the first element of the reversed deque. It corresponds to the last element
+ * of the non-reversed deque. If the deque is empty, the returned iterator will be equal to rend().
+ *
+ * @return Reverse iterator to the first element.
+ */
+ auto rbegin() noexcept -> pointer { return _data + _size - 1; }
+
+ /**
+ * @brief Returns a reverse iterator to the first element of the reversed deque. It corresponds to the last element
+ * of the non-reversed deque. If the deque is empty, the returned iterator will be equal to rend().
+ *
+ * @return Reverse iterator to the first element.
+ */
+ auto rbegin() const noexcept -> const_pointer { return _data + _size - 1; }
+
+ /**
+ * @brief Returns a reverse iterator to the first element of the reversed deque. It corresponds to the last element
+ * of the non-reversed deque. If the deque is empty, the returned iterator will be equal to rend().
+ *
+ * @return Reverse iterator to the first element.
+ */
+ auto crbegin() const noexcept -> const_pointer { return rbegin(); }
+
+ /**
+ * @brief Returns an iterator to the element following the last element of the deque. This element acts as a
+ * placeholder, attempting to access it results in undefined behavior.
+ *
+ * @return Iterator to the element following the last element.
+ */
+ auto end() noexcept -> pointer { return _data + _size; }
+
+ /**
+ * @brief Returns an iterator to the element following the last element of the deque. This element acts as a
+ * placeholder, attempting to access it results in undefined behavior.
+ *
+ * @return Iterator to the element following the last element.
+ */
+ auto end() const noexcept -> const_pointer { return _data + _size; }
+
+ /**
+ * @brief Returns an iterator to the element following the last element of the deque. This element acts as a
+ * placeholder, attempting to access it results in undefined behavior.
+ *
+ * @return Iterator to the element following the last element.
+ */
+ auto cend() const noexcept -> const_pointer { return end(); }
+
+ /**
+ * @brief Returns a reverse iterator to the element following the last element of the reversed deque. It
+ * corresponds to the element preceding the first element of the non-reversed deque. This element acts as a
+ * placeholder, attempting to access it results in undefined behavior.
+ *
+ * @return Reverse iterator to the element following the last element.
+ */
+ auto rend() noexcept -> pointer { return _data + size - 1; }
+
+ /**
+ * @brief Returns a reverse iterator to the element following the last element of the reversed deque. It
+ * corresponds to the element preceding the first element of the non-reversed deque. This element acts as a
+ * placeholder, attempting to access it results in undefined behavior.
+ *
+ * @return Reverse iterator to the element following the last element.
+ */
+ auto rend() const noexcept -> const_pointer { return _data + size - 1; }
+
+ /**
+ * @brief Returns a reverse iterator to the element following the last element of the reversed deque. It
+ * corresponds to the element preceding the first element of the non-reversed deque. This element acts as a
+ * placeholder, attempting to access it results in undefined behavior.
+ *
+ * @return Reverse iterator to the element following the last element.
+ */
+ auto crend() const noexcept -> const_pointer { return rbegin(); }
+
+ /**
+ * @brief Returns a pointer to the underlying array serving as element storage. The pointer is such that range
+ * [data(), data() + size()) is always a valid range, even if the container is empty (data() is not dereferenceable
+ * in that case).
+ *
+ * @return Pointer to the underlying element storage. For non-empty containers, the returned pointer compares equal
+ * to the address of the first element.
+ */
+ auto data() -> pointer { return _data; }
+
+ /**
+ * @brief Returns a pointer to the underlying array serving as element storage. The pointer is such that range
+ * [data(), data() + size()) is always a valid range, even if the container is empty (data() is not dereferenceable
+ * in that case).
+ *
+ * @return Pointer to the underlying element storage. For non-empty containers, the returned pointer compares equal
+ * to the address of the first element.
+ */
+ auto data() const -> const_pointer { return _data; }
+
+ /**
+ * @brief Returns a reference to the first element in the container. Calling front on an empty container causes
+ * undefined behavior.
+ *
+ * @return Reference to the first element.
+ */
+ auto front() -> reference
+ {
+ throw_if_empty();
+ return *begin();
+ }
+
+ /**
+ * @brief Returns a reference to the first element in the container. Calling front on an empty container causes
+ * undefined behavior.
+ *
+ * @return Reference to the first element.
+ */
+ auto front() const -> const_reference
+ {
+ throw_if_empty();
+ return *begin();
+ }
+
+ /**
+ * @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.
+ */
+ auto back() -> reference
+ {
+ throw_if_empty();
+ return *rbegin();
+ }
+
+ /**
+ * @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.
+ */
+ auto back() const -> const_reference
+ {
+ throw_if_empty();
+ return *rbegin();
+ }
+
+ /**
+ * @brief Increase the capacity of the deque (the total number of elements that the deque can hold without
+ * requiring reallocation) to a value that's greater or equal to new_cap. If new_cap is greater than the current
+ * capacity(), new storage is allocated, otherwise the function does nothing.
+ *
+ * reserve() does not change the size of the deque.
+ *
+ * If new_cap is greater than capacity(), all iterators (including the end() iterator) and all references to the
+ * elements are invalidated. Otherwise, no iterators or references are invalidated.
+ *
+ * After a call to reserve(), insertions will not trigger reallocation unless the insertion would make the size of
+ * the deque greater than the value of capacity().
+ *
+ * @note Correctly using reserve() can prevent unnecessary reallocations, but inappropriate uses of reserve() (for
+ * instance, calling it before every push_back() call) may actually increase the number of reallocations (by causing
+ * the capacity to grow linearly rather than exponentially) and result in increased computational complexity and
+ * decreased performance. For example, a function that receives an arbitrary deque by reference and appends
+ * elements to it should usually not call reserve() on the deque, since it does not know of the deque's usage
+ * characteristics.
+ *
+ * When inserting a range, the range version of insert() is generally preferable as it preserves the correct
+ * capacity growth behavior, unlike reserve() followed by a series of push_back()s.
+ *
+ * reserve() cannot be used to reduce the capacity of the container; to that end shrink_to_fit() is provided.
+ *
+ * @param new_capacity New capacity of the deque, in number of elements
+ */
+ auto reserve(size_type new_capacity) -> void
+ {
+ if (new_capacity <= _capacity)
+ {
+ return;
+ }
+
+ _capacity = new_capacity;
+ value_type * temp = new value_type[_capacity]{};
+ stl::container<value_type *> container{begin(), end()};
+ std::ranges::copy(container, temp);
+ delete[] _data;
+ _data = temp;
+ }
+
+ /**
+ * @brief Requests the removal of unused capacity. Meaning it requests to reduce capacity() to size().
+ *
+ * If reallocation occurs, all iterators (including the end() iterator) and all references to the elements are
+ * invalidated. If no reallocation occurs, no iterators or references are invalidated.
+ */
+ auto shrink_to_fit() -> void
+ {
+ if (_size == _capacity)
+ {
+ return;
+ }
+
+ _capacity = _size;
+ value_type * temp = new value_type[_capacity]{};
+ stl::container<value_type *> container{begin(), end()};
+ std::copy(container, temp);
+ delete[] _data;
+ _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("[Deque] Attempted to access element of currently empty deque");
+ }
+ }
+
+ auto throw_if_out_of_range(size_type index) const -> void
+ {
+ if (index >= _size)
+ {
+ exception_handling::panic("[Deque] Attempted to read element at invalid index");
+ }
+ }
+
+ /**
+ * @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);
+ }
+ }
+
+ size_type _size = {}; ///< Amount of elements in the underlying data container
+ size_type _capacity = {}; ///< Amount of space for elements in the underlying data container
+ block * _linked_list_start = {}; ///< Start pointer to the first element in the linked list
+ };
+
+} // namespace teachos::arch::stl
+
+#endif // TEACHOS_ARCH_X86_64_STL_DEQUE_HPP
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..316aacd
--- /dev/null
+++ b/arch/x86_64/include/arch/stl/stack.hpp
@@ -0,0 +1,182 @@
+#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/deque.hpp"
+
+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.
+ * @tparam Container Actual underlying container that should be wrapped to provide stack functionality. Requires
+ * access to pop_back(), push_back(), back(), size(), empty() and emplace_back()
+ */
+ template<typename T, typename Container = stl::deque<T>>
+ struct stack
+ {
+ using container_type = Container; ///< Type of the underlying container used to implement stack-like interface.
+ using value_type = Container::value_type; ///< Type of the elements contained in the underlying container.
+ using size_type = Container::size_type; ///< Type of the size in the underlying container.
+ using reference = Container::reference; ///< Type of reference to the elements.
+ using const_reference = Container::const_reference; ///< Type of constant reference to the elements.
+
+ /**
+ * @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 n 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(size_type n, value_type initial = value_type{})
+ : _container(n, 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 stack we are copying from and copies all
+ * elements from it.
+ *
+ * @param other Other instance of stack 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.
+ */
+ auto size() const -> size_type { 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.
+ */
+ auto top() -> reference { 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.
+ */
+ auto top() const -> const_reference { return _container.back(); }
+
+ /**
+ * @brief Appends the given element value to the end of the container. The element is assigned through the
+ * assignment operator of the template type. The value is forwarded to the constructor as
+ * std::forward<U>(value), meaning it is either moved (rvalue) or copied (lvalue).
+ *
+ * @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. Uses a forward reference for the actual value passed, which
+ * allows the template method to be used by both lvalue and rvalues and compile a different implementation.
+ *
+ * @param value The value of the element to append.
+ */
+ template<class U>
+ auto push(U && value) -> void
+ {
+ _container.push_back(std::forward<U>(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. Uses a forward reference for the actual value passed, which
+ * allows the template method to be used by both lvalue and rvalues and compile a different implementation.
+ *
+ * @tparam Args
+ * @param args Arguments to forward to the constructor of the element
+ * @return value_type&
+ */
+ template<class... Args>
+ auto emplace(Args &&... args) -> reference
+ {
+ _container.emplace_back(std::forward<Args>(args)...);
+ }
+
+ /**
+ * @brief Removes the last element of the container.
+ *
+ * @note 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.
+ */
+ auto pop() -> void { _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_type _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..c7d7853 100644
--- a/arch/x86_64/include/arch/stl/vector.hpp
+++ b/arch/x86_64/include/arch/stl/vector.hpp
@@ -2,9 +2,10 @@
#define TEACHOS_ARCH_X86_64_STL_VECTOR_HPP
#include "arch/exception_handling/panic.hpp"
+#include "arch/stl/container.hpp"
+#include "arch/stl/contiguous_pointer_iterator.hpp"
#include <algorithm>
-#include <concepts>
namespace teachos::arch::stl
{
@@ -17,6 +18,13 @@ namespace teachos::arch::stl
template<typename T>
struct vector
{
+ using value_type = T; ///< Type of the elements contained in the container.
+ using size_type = std::size_t; ///< Type of the size in the container.
+ using reference = value_type &; ///< Type of reference to the elements.
+ using const_reference = value_type const &; ///< Type of constant reference to the elements.
+ using pointer = value_type *; ///< Type of pointer to the elements.
+ using const_pointer = value_type const *; ///< Type of constant pointer to the elements.
+
/**
* @brief Default Constructor.
*/
@@ -26,15 +34,15 @@ namespace teachos::arch::stl
* @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 n 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 vector(std::size_t capacity, T initial = T{})
- : _size(capacity)
- , _capacity(capacity)
- , _data(new T[_capacity]{})
+ explicit vector(size_type n, value_type initial = value_type{})
+ : _size(n)
+ , _capacity(n)
+ , _data(new value_type[_capacity]{})
{
- std::ranges::fill(begin(), end(), initial);
+ std::ranges::fill(*this, initial);
}
/**
@@ -48,9 +56,10 @@ namespace teachos::arch::stl
explicit vector(InputIterator first, InputIterator last)
: _size(std::distance(first, last))
, _capacity(std::distance(first, last))
- , _data(new T[_capacity]{})
+ , _data(new value_type[_capacity]{})
{
- std::copy(first, last, _data);
+ stl::container<InputIterator> container{first, last};
+ std::ranges::copy(container, _data);
}
/**
@@ -58,12 +67,12 @@ namespace teachos::arch::stl
*
* @param initalizer_list List we want to copy all elements from.
*/
- explicit vector(std::initializer_list<T> initalizer_list)
+ explicit vector(std::initializer_list<value_type> initalizer_list)
: _size(initalizer_list.size())
, _capacity(initalizer_list.size())
- , _data(new T[_capacity]{})
+ , _data(new value_type[_capacity]{})
{
- std::copy(initalizer_list.begin(), initalizer_list.end(), _data);
+ std::ranges::copy(initalizer_list, _data);
}
/**
@@ -74,13 +83,13 @@ namespace teachos::arch::stl
*
* @param other Other instance of vector we want to copy the data from.
*/
- vector(vector<T> const & other)
+ vector(vector<value_type> const & other)
: _size(other._size)
, _capacity(other._capacity)
{
delete[] _data;
- _data = new T[_capacity]{};
- std::copy(other.begin(), other.end(), _data);
+ _data = new value_type[_capacity]{};
+ std::ranges::copy(other, _data);
}
/**
@@ -92,13 +101,13 @@ namespace teachos::arch::stl
* @param other Other instance of vector we want to copy the data from.
* @return Newly created copy.
*/
- vector<T> & operator=(vector<T> const & other)
+ vector<value_type> & operator=(vector<value_type> const & other)
{
delete[] _data;
_size = other._size;
_capacity = other._capacity;
- _data = new T[_capacity]{};
- std::copy(other.begin(), other.end(), _data);
+ _data = new value_type[_capacity]{};
+ std::ranges::copy(other, _data);
return *this;
}
@@ -113,7 +122,7 @@ namespace teachos::arch::stl
*
* @return Current amount of elements.
*/
- std::size_t size() const { return _size; }
+ auto size() const -> size_type { return _size; }
/**
* @brief Amount of space the vector currently has, can be different than the size, because we allocate more than we
@@ -121,7 +130,17 @@ namespace teachos::arch::stl
*
* @return Current amount of space the vector has for elements.
*/
- std::size_t capacity() const { return _capacity; }
+ auto capacity() const -> size_type { return _capacity; }
+
+ /**
+ * @brief Array indexing operator. Allowing to access element at the given index.
+ *
+ * @note Does not do any bounds checks use at() for that.
+ *
+ * @param index Index we want to access elements at.
+ * @return Reference to the underlying element.
+ */
+ auto operator[](size_type index) -> reference { return _data[index]; }
/**
* @brief Array indexing operator. Allowing to access element at the given index.
@@ -131,7 +150,7 @@ namespace teachos::arch::stl
* @param index Index we want to access elements at.
* @return Reference to the underlying element.
*/
- T & operator[](std::size_t index) { return _data[index]; }
+ auto operator[](size_type index) const -> const_reference { return _data[index]; }
/**
* @brief Array indexing operator. Allowing to access element at the given index.
@@ -141,54 +160,44 @@ namespace teachos::arch::stl
* @param index Index we want to access elements at.
* @return Reference to the underlying element.
*/
- T & at(std::size_t index)
+ auto at(size_type index) -> reference
{
- if (index >= _size)
- {
- exception_handling::panic("[Vector] Attempted to read element at invalid index");
- }
+ throw_if_out_of_range(index);
return this->operator[](index);
}
/**
- * @brief Appends the given element value to the end of the container. The new element is initalized as a copy of
- * value.
+ * @brief Array indexing operator. Allowing to access element at the given index.
*
- * @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.
+ * @note Ensures we do not access element outside of the bounds of the array, if we do further execution is halted.
*
- * @param value The value of the element to append.
+ * @param index Index we want to access elements at.
+ * @return Reference to the underlying element.
*/
- void push_back(T const & value)
+ auto at(size_type index) const -> const_reference
{
- if (_size == _capacity)
- {
- reserve(_capacity * 2);
- }
-
- _data[_size] = value;
- _size++;
+ throw_if_out_of_range(index);
+ return this->operator[](index);
}
/**
- * @brief Appends the given element value to the end of the container. Value is moved into the new element.
+ * @brief Appends the given element value to the end of the container. The element is assigned through the
+ * assignment operator of the template type. The value is forwarded to the constructor as
+ * std::forward<U>(value), meaning it is either moved (rvalue) or copied (lvalue).
*
* @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.
+ * Otherwise only the end() iterator is invalidated. Uses a forward reference for the actual value passed, which
+ * allows the template method to be used by both lvalue and rvalues and compile a different implementation.
*
* @param value The value of the element to append.
*/
- void push_back(T && value)
+ template<class U>
+ auto push_back(U && value) -> void
{
- if (_size == _capacity)
- {
- reserve(_capacity * 2);
- }
-
- _data[_size] = std::move(value);
- _size++;
+ increase_capacity_if_full();
+ _data[_size] = std::forward<U>(value);
+ (void)_size++;
}
/**
@@ -197,21 +206,18 @@ namespace teachos::arch::stl
*
* 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.
+ * the end() iterator is invalidated. Uses a forward reference for the actual value passed, which
+ * allows the template method to be used by both lvalue and rvalues and compile a different implementation.
*
* @tparam Args
* @param args Arguments to forward to the constructor of the element
- * @return T&
+ * @return value_type&
*/
template<class... Args>
- auto emplace_back(Args &&... args) -> T &
+ auto emplace_back(Args &&... args) -> value_type &
{
- if (_size == _capacity)
- {
- reserve(_capacity * 2);
- }
-
- _data[_size] = T{std::forward<Args>(args)...};
+ increase_capacity_if_full();
+ _data[_size] = value_type{std::forward<Args>(args)...};
auto const index = _size++;
return _data[index];
}
@@ -221,13 +227,10 @@ namespace teachos::arch::stl
* further execution. Iterators and references to the last element are invalidated. The end()
* iterator is also invalidated.
*/
- void pop_back()
+ auto pop_back() -> void
{
- if (_size <= 0)
- {
- exception_handling::panic("[Vector] Attempted to pop back last element of already empty vector");
- }
- _size--;
+ throw_if_empty();
+ (void)_size--;
}
/**
@@ -236,7 +239,7 @@ namespace teachos::arch::stl
*
* @return Iterator to the first element.
*/
- T * begin() noexcept { return _data; }
+ auto begin() noexcept -> pointer { return _data; }
/**
* @brief Returns an iterator to the first element of the vector.
@@ -244,7 +247,7 @@ namespace teachos::arch::stl
*
* @return Iterator to the first element.
*/
- T const * begin() const noexcept { return _data; }
+ auto begin() const noexcept -> const_pointer { return _data; }
/**
* @brief Returns an iterator to the first element of the vector.
@@ -252,7 +255,7 @@ namespace teachos::arch::stl
*
* @return Iterator to the first element.
*/
- T const * cbegin() const noexcept { return begin(); }
+ auto cbegin() const noexcept -> const_pointer { return begin(); }
/**
* @brief Returns a reverse iterator to the first element of the reversed vector. It corresponds to the last element
@@ -260,7 +263,7 @@ namespace teachos::arch::stl
*
* @return Reverse iterator to the first element.
*/
- T * rbegin() noexcept { return _data + _size - 1; }
+ auto rbegin() noexcept -> pointer { return _data + _size - 1; }
/**
* @brief Returns a reverse iterator to the first element of the reversed vector. It corresponds to the last element
@@ -268,7 +271,7 @@ namespace teachos::arch::stl
*
* @return Reverse iterator to the first element.
*/
- T const * rbegin() const noexcept { return _data + _size - 1; }
+ auto rbegin() const noexcept -> const_pointer { return _data + _size - 1; }
/**
* @brief Returns a reverse iterator to the first element of the reversed vector. It corresponds to the last element
@@ -276,7 +279,7 @@ namespace teachos::arch::stl
*
* @return Reverse iterator to the first element.
*/
- T const * crbegin() const noexcept { return rbegin(); }
+ auto crbegin() const noexcept -> const_pointer { return rbegin(); }
/**
* @brief Returns an iterator to the element following the last element of the vector. This element acts as a
@@ -284,7 +287,7 @@ namespace teachos::arch::stl
*
* @return Iterator to the element following the last element.
*/
- T * end() noexcept { return _data + _size; }
+ auto end() noexcept -> pointer { return _data + _size; }
/**
* @brief Returns an iterator to the element following the last element of the vector. This element acts as a
@@ -292,7 +295,7 @@ namespace teachos::arch::stl
*
* @return Iterator to the element following the last element.
*/
- T const * end() const noexcept { return _data + _size; }
+ auto end() const noexcept -> const_pointer { return _data + _size; }
/**
* @brief Returns an iterator to the element following the last element of the vector. This element acts as a
@@ -300,7 +303,7 @@ namespace teachos::arch::stl
*
* @return Iterator to the element following the last element.
*/
- T const * cend() const noexcept { return end(); }
+ auto cend() const noexcept -> const_pointer { return end(); }
/**
* @brief Returns a reverse iterator to the element following the last element of the reversed vector. It
@@ -309,7 +312,7 @@ namespace teachos::arch::stl
*
* @return Reverse iterator to the element following the last element.
*/
- T * rend() noexcept { return _data + size - 1; }
+ auto rend() noexcept -> pointer { return _data + size - 1; }
/**
* @brief Returns a reverse iterator to the element following the last element of the reversed vector. It
@@ -318,7 +321,7 @@ namespace teachos::arch::stl
*
* @return Reverse iterator to the element following the last element.
*/
- T const * rend() const noexcept { return _data + size - 1; }
+ auto rend() const noexcept -> const_pointer { return _data + size - 1; }
/**
* @brief Returns a reverse iterator to the element following the last element of the reversed vector. It
@@ -327,7 +330,7 @@ namespace teachos::arch::stl
*
* @return Reverse iterator to the element following the last element.
*/
- T const * crend() const noexcept { return rbegin(); }
+ auto crend() const noexcept -> const_pointer { return rbegin(); }
/**
* @brief Returns a pointer to the underlying array serving as element storage. The pointer is such that range
@@ -337,7 +340,7 @@ namespace teachos::arch::stl
* @return Pointer to the underlying element storage. For non-empty containers, the returned pointer compares equal
* to the address of the first element.
*/
- T * data() { return _data; }
+ auto data() -> pointer { return _data; }
/**
* @brief Returns a pointer to the underlying array serving as element storage. The pointer is such that range
@@ -347,7 +350,7 @@ namespace teachos::arch::stl
* @return Pointer to the underlying element storage. For non-empty containers, the returned pointer compares equal
* to the address of the first element.
*/
- T const * data() const { return _data; }
+ auto data() const -> const_pointer { return _data; }
/**
* @brief Returns a reference to the first element in the container. Calling front on an empty container causes
@@ -355,7 +358,11 @@ namespace teachos::arch::stl
*
* @return Reference to the first element.
*/
- T & front() { return *begin(); }
+ auto front() -> reference
+ {
+ 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 +370,11 @@ namespace teachos::arch::stl
*
* @return Reference to the first element.
*/
- T const & front() const { return *begin(); }
+ auto front() const -> const_reference
+ {
+ 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 +382,11 @@ namespace teachos::arch::stl
*
* @return Reference to the last element.
*/
- T & back() { return *rbegin(); }
+ auto back() -> reference
+ {
+ 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 +394,11 @@ namespace teachos::arch::stl
*
* @return Reference to the last element.
*/
- T const & back() const { return *rbegin(); }
+ auto back() const -> const_reference
+ {
+ throw_if_empty();
+ return *rbegin();
+ }
/**
* @brief Increase the capacity of the vector (the total number of elements that the vector can hold without
@@ -408,7 +427,7 @@ namespace teachos::arch::stl
*
* @param new_capacity New capacity of the vector, in number of elements
*/
- void reserve(std::size_t new_capacity)
+ auto reserve(size_type new_capacity) -> void
{
if (new_capacity <= _capacity)
{
@@ -416,8 +435,9 @@ namespace teachos::arch::stl
}
_capacity = new_capacity;
- T * temp = new T[_capacity]{};
- std::copy(begin(), end(), temp);
+ value_type * temp = new value_type[_capacity]{};
+ stl::container<value_type *> container{begin(), end()};
+ std::ranges::copy(container, temp);
delete[] _data;
_data = temp;
}
@@ -428,7 +448,7 @@ namespace teachos::arch::stl
* If reallocation occurs, all iterators (including the end() iterator) and all references to the elements are
* invalidated. If no reallocation occurs, no iterators or references are invalidated.
*/
- void shrink_to_fit()
+ auto shrink_to_fit() -> void
{
if (_size == _capacity)
{
@@ -436,16 +456,56 @@ namespace teachos::arch::stl
}
_capacity = _size;
- T * temp = new T[_capacity]{};
- std::copy(begin(), end(), temp);
+ value_type * temp = new value_type[_capacity]{};
+ stl::container<value_type *> container{begin(), end()};
+ std::copy(container, temp);
delete[] _data;
_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:
- 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
+ /**
+ * @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");
+ }
+ }
+
+ auto throw_if_out_of_range(size_type index) const -> void
+ {
+ if (index >= _size)
+ {
+ exception_handling::panic("[Vector] Attempted to read element at invalid index");
+ }
+ }
+
+ /**
+ * @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);
+ }
+ }
+
+ size_type _size = {}; ///< Amount of elements in the underlying data container
+ size_type _capacity = {}; ///< Amount of space for elements in the underlying data container
+ value_type * _data = {}; ///< Pointer to the first element in the underlying data container
};
} // namespace teachos::arch::stl
diff --git a/arch/x86_64/src/context_switching/main.cpp b/arch/x86_64/src/context_switching/main.cpp
index fc8790f..7be286a 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);
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-20 14:06:08 +0000