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 co