Start developing paging

5 files changed, 229 insertions, 80 deletions

diff --git a/arch/x86_64/include/arch/memory/frame_allocator.hpp b/arch/x86_64/include/arch/memory/frame_allocator.hpp
index 1fd1f08..ab93231 100644
--- a/arch/x86_64/include/arch/memory/frame_allocator.hpp
+++ b/arch/x86_64/include/arch/memory/frame_allocator.hpp
@@ -8,47 +8,46 @@
 
 namespace teachos::arch::memory
 {
-  namespace
-  {
-    constexpr std::size_t PAGE_FRAME_SIZE = 4096U;  ///< Default page size of x86_84 is always 4KiB
-  }
+  constexpr std::size_t PAGE_FRAME_SIZE = 4096U;  ///< Default page size of x86_84 is always 4KiB.
 
   /**
-   * @brief Specific frame containing helper functions to determine if a specific address is in that frame or not
+   * @brief Specific physical_frame containing helper functions to determine if a specific address is in that
+   * physical_frame or not.
    */
-  struct frame
+  struct physical_frame
   {
     /**
      * @brief Constructor
      *
-     * @param frame_number Index number that should be assigned to this frame
+     * @param frame_number Index number that should be assigned to this physical_frame.
      */
-    frame(std::size_t frame_number);
+    explicit physical_frame(std::size_t frame_number);
 
     /**
-     * @brief Returns the frame the given address is contained in
+     * @brief Returns the physical_frame the given address is contained in.
      *
-     * @param address Address we want to get the corresponding frame for
-     * @return Frame the given address is contained in
+     * @param address Address we want to get the corresponding physical_frame for.
+     * @return Frame the given address is contained in.
      */
-    static auto containing_address(std::size_t address) -> frame;
+    static auto containing_address(std::size_t address) -> physical_frame;
 
     /**
-     * @brief Defaulted equals operator
+     * @brief Defaulted equals operator.
      */
-    constexpr auto operator==(const frame & other) const -> bool = default;
+    constexpr auto operator==(const physical_frame & other) const -> bool = default;
 
     /**
-     * @brief Defaulted three-way comparsion operator
+     * @brief Defaulted three-way comparsion operator.
      */
-    constexpr auto operator<=>(const frame & other) const -> std::partial_ordering = default;
+    constexpr auto operator<=>(const physical_frame & other) const -> std::partial_ordering = default;
 
-    std::size_t frame_number;  ///< Index number of the current frame, used to distinguish it from other frames
+    std::size_t
+        frame_number;  ///< Index number of the current physical frame, used to distinguish it from other frames.
   };
 
   template<typename T>
   concept FrameAllocator = requires(T t) {
-    { t.allocate_frame() } -> std::same_as<std::optional<frame>>;
+    { t.allocate_frame() } -> std::same_as<std::optional<physical_frame>>;
     { t.deallocate_frame() } -> std::same_as<void>;
   };
 
@@ -58,121 +57,121 @@ namespace teachos::arch::memory
   struct memory_area_iterator
   {
     /**
-     * @brief Constructor
+     * @brief Constructor.
      *
-     * @param p Underlying address the iterator should point too, ensure to not pass an invalid pointer
+     * @param p Underlying address the iterator should point too, ensure to not pass an invalid pointer.
      */
     explicit memory_area_iterator(memory_area * p);
 
     /**
      * @brief Dereferences the initally given pointer to its value.
      *
-     * @return Reference to the value
+     * @return Reference to the value.
      */
     memory_area & operator*() const;
 
     /**
      * @brief Post increment operator. Returns a copy of the value
      *
-     * @return Copy of the incremented underlying address
+     * @return Copy of the incremented underlying address.
      */
     memory_area_iterator operator++(int);
 
     /**
-     * @brief Pre increment operator. Returns a reference to the changed value
+     * @brief Pre increment operator. Returns a reference to the changed value.
      *
-     * @return Reference to the incremented underlying address
+     * @return Reference to the incremented underlying address.
      */
     memory_area_iterator & operator++();
 
     /**
      * @brief Defaulted comparsion operator. Simply compares the memory address of both iterators.
      *
-     * @param other Other iterator to compare to
-     * @return Whether poith iterators point to the same underlying address in memory
+     * @param other Other iterator to compare to.
+     * @return Whether poith iterators point to the same underlying address in memory.
      */
     bool operator==(memory_area_iterator const & other) const = default;
 
   private:
-    memory_area * ptr;  ///< Underlying address the iterator is currently pointing too
+    memory_area * ptr;  ///< Underlying address the iterator is currently pointing too.
   };
 
   /**
-   * @brief Allocates memory using memory areas read from the multiboot2 information pointer
+   * @brief Allocates memory using memory areas read from the multiboot2 information pointer.
    */
   struct area_frame_allocator
   {
     /**
      * @brief Constructor
      *
-     * @param kernel_start Start address of the kernel code in memory
-     * @param kernel_end End address of the kernel code in memory
-     * @param multiboot_start Start address of the multiboot code in memory
-     * @param multiboot_end End address of the multiboot code in memory
-     * @param memory_areas Pointer to the first element of all memory areas
-     * @param area_count Amount of total entries in the memory_areas array
+     * @param kernel_start Start address of the kernel code in memory.
+     * @param kernel_end End address of the kernel code in memory.
+     * @param multiboot_start Start address of the multiboot code in memory.
+     * @param multiboot_end End address of the multiboot code in memory.
+     * @param memory_areas Pointer to the first element of all memory areas.
+     * @param area_count Amount of total entries in the memory_areas array.
      */
     area_frame_allocator(std::size_t kernel_start, std::size_t kernel_end, std::size_t multiboot_start,
                          std::size_t multiboot_end, memory_area * memory_areas, uint8_t area_count)
         : area_begin(memory_areas)
         , area_end(memory_areas + area_count)
-        , kernel_start(frame::containing_address(kernel_start))
-        , kernel_end(frame::containing_address(kernel_end))
-        , multiboot_start(frame::containing_address(multiboot_start))
-        , multiboot_end(frame::containing_address(multiboot_end))
+        , kernel_start(physical_frame::containing_address(kernel_start))
+        , kernel_end(physical_frame::containing_address(kernel_end))
+        , multiboot_start(physical_frame::containing_address(multiboot_start))
+        , multiboot_end(physical_frame::containing_address(multiboot_end))
     {
       choose_next_area();
     }
 
     /**
-     * @brief Allocate memory by finding and returning a free frame
+     * @brief Allocate memory by finding and returning a free physical_frame.
      *
-     * The frame allocation executes multiple checks before returning
-     * the frame that is available to allocate. It must at least
+     * The physical_frame allocation executes multiple checks before returning
+     * the physical_frame that is available to allocate. It must at least
      * do the following:
      * - check if the next_free_frame is within the current_area
      * - check if the next_free_frame is actually free
-     * - update the next_free_frame after finding a free frame
+     * - update the next_free_frame after finding a free physical_frame
      */
-    auto allocate_frame() -> std::optional<frame>;
+    auto allocate_frame() -> std::optional<physical_frame>;
 
     /**
-     * @brief Deallocates a previously allocated frame
+     * @brief Deallocates a previously allocated physical_frame.
      *
-     * @param frame Previously allocated frame that should be allocated
+     * @param physical_frame Previously allocated physical_frame that should be allocated.
      */
-    auto deallocate_frame(frame frame) -> void;
+    auto deallocate_frame(physical_frame physical_frame) -> void;
 
     /**
      * @brief Returns the iterator pointing to the first element of the memory area.
-     * Allows using this class in the for each loop, because it follows the InputIterator template scheme
+     * Allows using this class in the for each loop, because it follows the InputIterator template scheme.
      *
-     * @return Iterator pointing to first element of the memory area
+     * @return Iterator pointing to first element of the memory area.
      */
     auto begin() -> memory_area_iterator;
 
     /**
      * @brief Returns the iterator pointing to one past the last element of the memory area.
-     * Allows using this class in the for each loop, because it follows the InputIterator template scheme
+     * Allows using this class in the for each loop, because it follows the InputIterator template scheme.
      *
-     * @return Iterator pointing to one past the last element of the memory area
+     * @return Iterator pointing to one past the last element of the memory area.
      */
     auto end() -> memory_area_iterator;
 
   private:
     /**
-     * @brief Find the next memory area and write it into current_area
+     * @brief Find the next memory area and write it into current_area.
      */
     auto choose_next_area() -> void;
 
-    frame next_free_frame{0};                               ///< The frame after the last allocated one
-    std::optional<memory_area> current_area{std::nullopt};  ///< The current memory area
-    memory_area_iterator area_begin;                        ///< Pointer to the first element of all memory areas
-    memory_area_iterator area_end;                          ///< Pointer to one pas the last element of all memory areas
-    frame const kernel_start;                               ///< The start address of the kernel code in memory
-    frame const kernel_end;                                 ///< The end address of the kernel code in memory
-    frame const multiboot_start;                            ///< The start address of the multiboot code in memory
-    frame const multiboot_end;                              ///< The end address of the multiboot code in memory
+    physical_frame next_free_frame{0};                      ///< The physical_frame after the last allocated one.
+    std::optional<memory_area> current_area{std::nullopt};  ///< The current memory area.
+    memory_area_iterator area_begin;                        ///< Pointer to the first element of all memory areas.
+    memory_area_iterator area_end;         ///< Pointer to one pas the last element of all memory areas.
+    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
 
diff --git a/arch/x86_64/include/arch/memory/multiboot.hpp b/arch/x86_64/include/arch/memory/multiboot.hpp
index 35b483e..93d214c 100644
--- a/arch/x86_64/include/arch/memory/multiboot.hpp
+++ b/arch/x86_64/include/arch/memory/multiboot.hpp
@@ -152,7 +152,7 @@ namespace teachos::arch::memory
      *
      * @return Current section is writable.
      */
-    auto writeable() const -> bool;
+    auto writable() const -> bool;
 
     /**
      * @brief (SHF_ALLOC) Whether the current section occupies memory during execution or not. ALLOC flag is shown in
diff --git a/arch/x86_64/include/arch/memory/paging.hpp b/arch/x86_64/include/arch/memory/paging.hpp
new file mode 100644
index 0000000..a5408e1
--- /dev/null
+++ b/arch/x86_64/include/arch/memory/paging.hpp
@@ -0,0 +1,150 @@
+#ifndef TEACHOS_ARCH_X86_64_MEMORY_PAGING_HPP
+#define TEACHOS_ARCH_X86_64_MEMORY_PAGING_HPP
+
+#include "frame_allocator.hpp"
+
+namespace teachos::arch::memory
+{
+  constexpr std::size_t PAGE_TABLE_ENTRY_COUNT = 512U;  ///< Default entry count of a page table in x86_84 is 512.
+
+  /**
+   * @brief Virtual page entry contained in P1 page tables
+   */
+  struct virtual_page
+  {
+    std::size_t number;  ///< Index number of the current virtual page, used to distinguish it from other pages.
+
+    /**
+     * @brief Defaulted equals operator.
+     */
+    constexpr auto operator==(const virtual_page & other) const -> bool = default;
+
+    /**
+     * @brief Defaulted three-way comparsion operator.
+     */
+    constexpr auto operator<=>(const virtual_page & other) const -> std::partial_ordering = default;
+  };
+
+  /**
+   * @brief Marks a specific entry in an actual page table.
+   */
+  struct entry
+  {
+    /**
+     * @brief Whether the current page is unused, meaning the underlying std::bitset is 0.
+     *
+     * @return Current page is in memory.
+     */
+    auto is_unused() const -> bool;
+
+    /**
+     * @brief Marks the page as unused, meaning the underlying std::bitset is set to 0.
+     */
+    auto set_unused() -> void;
+
+    /**
+     * @brief Whether the current page is in memory and therefore present or not. Read from bit index 0.
+     *
+     * @return Current page is in memory.
+     */
+    auto present() const -> bool;
+
+    /**
+     * @brief Whether it is possible to write to the current page or not. Read from bit index 1.
+     *
+     * @return Current page can be written too.
+     */
+    auto writable() const -> bool;
+
+    /**
+     * @brief Whether the current page can be accessed in user mode, or only in kernel mode code. Read from bit index 2.
+     *
+     * @return Current page can be accessed in user mode.
+     */
+    auto user_accessible() const -> bool;
+
+    /**
+     * @brief Whether any write to the current page go directly to memory instead of the cache or not. Read from bit
+     * index 3.
+     *
+     * @return Writes to the current page go directly to memory.
+     */
+    auto write_through_caching() const -> bool;
+
+    /**
+     * @brief Whether the current page uses caching or not. Read from bit index 4.
+     *
+     * @return Current page does not use caching.
+     */
+    auto disabled_caching() const -> bool;
+
+    /**
+     * @brief Whether the current page is currently being used or not. Read from bit index 5.
+     *
+     * @return Current page is currently being used.
+     */
+    auto is_accessing() const -> bool;
+
+    /**
+     * @brief Whether the current page has been writen too or not. Read from bit index 6.
+     *
+     * @return Current page has been writen too.
+     */
+    auto is_diry() const -> bool;
+
+    /**
+     * @brief Whether the current page is huge or not (2 MiB page size in P2 page table and 1 GiB in P3 page table,
+     * instead of 4 KiB). Has to be false for P1 and P4 page tables. Read from bit index 7.
+     *
+     * @return Current page is huge
+     */
+    auto is_huge_page() const -> bool;
+
+    /**
+     * @brief Whether the current page is not flushed from caches on address space switches or not (PGE bit of CR4
+     * register has to be set). Read from bit index 8.
+     *
+     * @return Current page is not flushed from caches on address space switches.
+     */
+    auto is_global() const -> bool;
+
+    /**
+     * @brief Whether the current page is forbidden from executing code or not (NXE bit in the EFER register has to be
+     * set). Read from bit index 63.
+     *
+     * @return Current page is forbidden from executing code.
+     */
+    auto executing_code_forbidden() const -> bool;
+
+    /**
+     * @brief Calculates the physical frame this entry is pointing too, can be null if the page is not present in
+     * memory.
+     *
+     * @return Calculated physical frame entry is pointing too.
+     */
+    auto calculate_pointed_to_frame() const -> std::optional<physical_frame>;
+
+  private:
+    /**
+     * @brief Extracts the physical address from the underlying bitset read from bit index 12 - 51. Is a 52 bit page
+     * aligned physical address of the frame of the next page table or the pyhscial address of the frame for P1 page
+     * tables.
+     *
+     * @return Extracted physical address of the next page or of the frame for P1 page tables.
+     */
+    auto calculate_physical_address() const -> std::size_t;
+
+    /**
+     * @brief Checks the underlying std::bitset if the bit at the specific index is set, meaning a value of 1
+     *
+     * @param index Specific index we want to check at
+     * @return Bit value 1 is set and will return true
+     */
+    auto is_bit_set(uint8_t index) const -> bool;
+
+    std::bitset<64U> flags;  ///< Underlying bitset used to read the flags from. Bits 9 - 11 and 52 - 62 can be freely
+                             ///< used for additional flagsby the operating system.
+  };
+}  // namespace teachos::arch::memory
+
+#endif  // TEACHOS_ARCH_X86_64_MEMORY_PAGING_HPP
diff --git a/arch/x86_64/include/arch/video/vga/io.hpp b/arch/x86_64/include/arch/video/vga/io.hpp
index da9375d..3d2e90c 100644
--- a/arch/x86_64/include/arch/video/vga/io.hpp
+++ b/arch/x86_64/include/arch/video/vga/io.hpp
@@ -10,24 +10,24 @@ namespace teachos::arch::video::vga
   namespace crtc
   {
     /**
-     * @brief The address port of the CRT Controller
+     * @brief The address port of the CRT Controller.
      */
     using address_port = arch::io::port<0x3d4, 1>;
 
     /**
-     * @brief The data port of the CRT Controller
+     * @brief The data port of the CRT Controller.
      */
     using data_port = arch::io::port<0x3d5, 1>;
 
     namespace registers
     {
       /**
-       * @brief The address of the Cursor Start register of the CRTC
+       * @brief The address of the Cursor Start register of the CRTC.
        */
       [[maybe_unused]] auto constexpr cursor_start = std::byte{0x0a};
 
       /**
-       * @brief The address of the Cursor End register of the CRTC
+       * @brief The address of the Cursor End register of the CRTC.
        */
       [[maybe_unused]] auto constexpr curser_end = std::byte{0x0b};
     }  // namespace registers
diff --git a/arch/x86_64/include/arch/video/vga/text.hpp b/arch/x86_64/include/arch/video/vga/text.hpp
index 79ec7be..cfafce0 100644
--- a/arch/x86_64/include/arch/video/vga/text.hpp
+++ b/arch/x86_64/include/arch/video/vga/text.hpp
@@ -12,14 +12,14 @@ namespace teachos::arch::video::vga::text
    */
   enum struct color : std::uint8_t
   {
-    black,  /**< Equivalent to HTML color \#000000 */
-    blue,   /**< Equivalent to HTML color \#0000AA */
-    green,  /**< Equivalent to HTML color \#00AA00 */
-    cyan,   /**< Equivalent to HTML color \#00AAAA */
-    red,    /**< Equivalent to HTML color \#AA0000 */
-    purple, /**< Equivalent to HTML color \#AA00AA */
-    brown,  /**< Equivalent to HTML color \#AA5500 */
-    gray,   /**< Equivalent to HTML color \#AAAAAA */
+    black,   ///< Equivalent to HTML color \#000000
+    blue,    ///< Equivalent to HTML color \#0000AA
+    green,   ///< Equivalent to HTML color \#00AA00
+    cyan,    ///< Equivalent to HTML color \#00AAAA
+    red,     ///< Equivalent to HTML color \#AA0000
+    purple,  ///< Equivalent to HTML color \#AA00AA
+    brown,   ///< Equivalent to HTML color \#AA5500
+    gray,    ///< Equivalent to HTML color \#AAAAAA
   };
 
   /**
@@ -27,8 +27,8 @@ namespace teachos::arch::video::vga::text
    */
   enum struct foreground_flag : bool
   {
-    none,    /**< Apply no flag e.g., keep color as is. */
-    intense, /**< Make the color more intense (usually brighter). */
+    none,     ///< Apply no flag e.g., keep color as is.
+    intense,  ///< Make the color more intense (usually brighter).
   };
 
   /**
@@ -36,8 +36,8 @@ namespace teachos::arch::video::vga::text
    */
   enum struct background_flag : bool
   {
-    none,            /**< Apply no flag e.g., keep color as is. */
-    blink_or_bright, /**< Make the cell blink or more intense, dependent on the VGA configuration */
+    none,             ///< Apply no flag e.g., keep color as is.
+    blink_or_bright,  ///< Make the cell blink or more intense, dependent on the VGA configuration
   };
 
   /**
@@ -51,10 +51,10 @@ namespace teachos::arch::video::vga::text
    */
   struct attribute
   {
-    color foreground_color : 3;               /**< The foreground color of the cell, e.g. the color of the code point.*/
-    enum foreground_flag foreground_flag : 1; /**< The foreground color modification flag of the cell.*/
-    color bacground_color : 3;                /**< The background color of the cell.*/
-    enum background_flag background_flag : 1; /**< The background color modification flag of the cell.*/
+    color foreground_color : 3;                ///< The foreground color of the cell, e.g. the color of the code point
+    enum foreground_flag foreground_flag : 1;  ///< The foreground color modification flag of the cell.
+    color bacground_color : 3;                 ///< The background color of the cell.
+    enum background_flag background_flag : 1;  ///< The background color modification flag of the cell.
   };
 
   static_assert(sizeof(attribute) == 1, "The VGA text mode attribute must fit inside a single byte.");