diff options
Diffstat (limited to 'arch')
63 files changed, 3747 insertions, 120 deletions
diff --git a/arch/x86_64/CMakeLists.txt b/arch/x86_64/CMakeLists.txt index 6ff1332..c5624d8 100644 --- a/arch/x86_64/CMakeLists.txt +++ b/arch/x86_64/CMakeLists.txt @@ -37,6 +37,43 @@ target_sources("_video" PRIVATE ) #[============================================================================[ +# The Memory Library +#]============================================================================] + +target_sources("_memory" PRIVATE + "src/memory/main.cpp" + "src/memory/multiboot/elf_symbols_section.cpp" + "src/memory/multiboot/reader.cpp" + "src/memory/allocator/area_frame_allocator.cpp" + "src/memory/allocator/tiny_frame_allocator.cpp" + "src/memory/allocator/physical_frame.cpp" + "src/memory/paging/page_entry.cpp" + "src/memory/paging/page_table.cpp" + "src/memory/paging/temporary_page.cpp" + "src/memory/paging/virtual_page.cpp" + "src/memory/paging/active_page_table.cpp" + "src/memory/paging/inactive_page_table.cpp" + "src/memory/cpu/tlb.cpp" + "src/memory/cpu/control_register.cpp" + "src/memory/cpu/msr.cpp" + "src/memory/heap/bump_allocator.cpp" + "src/memory/heap/memory_block.cpp" + "src/memory/heap/linked_list_allocator.cpp" + "src/shared/mutex.cpp" +) + +#[============================================================================[ +# The Exception handling Library +#]============================================================================] + +target_sources("_exception" PRIVATE + "src/exception_handling/assert.cpp" + "src/exception_handling/abort.cpp" + "src/exception_handling/panic.cpp" + "src/exception_handling/pure_virtual.cpp" +) + +#[============================================================================[ # The Bootable ISO Image #]============================================================================] diff --git a/arch/x86_64/include/arch/boot/pointers.hpp b/arch/x86_64/include/arch/boot/pointers.hpp index dcd14fe..fe9c657 100644 --- a/arch/x86_64/include/arch/boot/pointers.hpp +++ b/arch/x86_64/include/arch/boot/pointers.hpp @@ -5,7 +5,11 @@ namespace teachos::arch::boot { - extern "C" std::byte const multiboot_information_pointer; + /** + * @brief Address pointing to the start of the multiboot information structure. + */ + extern "C" size_t const multiboot_information_pointer; + } // namespace teachos::arch::boot -#endif
\ No newline at end of file +#endif // TEACHOS_ARCH_X86_64_BOOT_POINTERS_HPP diff --git a/arch/x86_64/include/arch/exception_handling/assert.hpp b/arch/x86_64/include/arch/exception_handling/assert.hpp new file mode 100644 index 0000000..1286768 --- /dev/null +++ b/arch/x86_64/include/arch/exception_handling/assert.hpp @@ -0,0 +1,17 @@ +#ifndef TEACHOS_ARCH_X86_64_EXCEPTION_HANDLING_ASSERT_HPP +#define TEACHOS_ARCH_X86_64_EXCEPTION_HANDLING_ASSERT_HPP + +namespace teachos::arch::exception_handling +{ + /** + * @brief Assert a condition to be true, if not do not continue + * execution of the code and print the given message to screen. + * + * @param condition Condition we want to be true or else halt execution. + * @param message Message that should be printed before halting the execution if the condition is not met. + */ + auto assert(bool condition, char const * message) -> void; + +} // namespace teachos::arch::exception_handling + +#endif // TEACHOS_ARCH_X86_64_EXCEPTION_HANDLING_ASSERT_HPP diff --git a/arch/x86_64/include/arch/exception_handling/panic.hpp b/arch/x86_64/include/arch/exception_handling/panic.hpp new file mode 100644 index 0000000..6a2404c --- /dev/null +++ b/arch/x86_64/include/arch/exception_handling/panic.hpp @@ -0,0 +1,23 @@ +#ifndef TEACHOS_ARCH_X86_64_EXCEPTION_HANDLING_PANIC_HPP +#define TEACHOS_ARCH_X86_64_EXCEPTION_HANDLING_PANIC_HPP + +namespace teachos::arch::exception_handling +{ + /** + * @brief Print the given kernel panic message and then halt the system. + * + * @param reason Reason to print before halting the system. + */ + [[noreturn]] auto panic(char const * reason) -> void; + + /** + * @brief Print the given kernel panic message started by a given prefix and then halt the system. + * + * @param prefix Prefix to print before printing the reason. + * @param reason Reason to print before halting the system. + */ + [[noreturn]] auto panic(char const * prefix, char const * reason) -> void; + +} // namespace teachos::arch::exception_handling + +#endif // TEACHOS_ARCH_X86_64_EXCEPTION_HANDLING_PANIC_HPP diff --git a/arch/x86_64/include/arch/io/port_io.hpp b/arch/x86_64/include/arch/io/port_io.hpp index 5b61f90..ba41660 100644 --- a/arch/x86_64/include/arch/io/port_io.hpp +++ b/arch/x86_64/include/arch/io/port_io.hpp @@ -8,7 +8,6 @@ namespace teachos::arch::io { - /** * @brief An I/O port of a given size at a given address. * @@ -131,4 +130,4 @@ namespace teachos::arch::io } // namespace teachos::arch::io -#endif
\ No newline at end of file +#endif // TEACHOS_ARCH_X86_64_IO_PORT_IO_HPP diff --git a/arch/x86_64/include/arch/kernel/halt.hpp b/arch/x86_64/include/arch/kernel/halt.hpp new file mode 100644 index 0000000..377acc0 --- /dev/null +++ b/arch/x86_64/include/arch/kernel/halt.hpp @@ -0,0 +1,13 @@ +#ifndef TEACHOS_ARCH_X86_64_KERNEL_HALT_HPP +#define TEACHOS_ARCH_X86_64_KERNEL_HALT_HPP + +namespace teachos::arch::kernel +{ + /** + * @brief Halts the kernel execution, meaning any code after a call to this will not run anymore. + */ + extern "C" [[noreturn]] auto halt() -> void; + +} // namespace teachos::arch::kernel + +#endif // TEACHOS_ARCH_X86_64_KERNEL_HALT_HPP diff --git a/arch/x86_64/include/arch/kernel/main.hpp b/arch/x86_64/include/arch/kernel/main.hpp index 6961594..a13e5f4 100644 --- a/arch/x86_64/include/arch/kernel/main.hpp +++ b/arch/x86_64/include/arch/kernel/main.hpp @@ -1,11 +1,13 @@ #ifndef TEACHOS_ARCH_X86_64_KERNEL_MAIN_HPP #define TEACHOS_ARCH_X86_64_KERNEL_MAIN_HPP -#include <cstddef> - namespace teachos::arch::kernel { + /** + * @brief Initalizes the kernel system. + */ auto main() -> void; -} -#endif
\ No newline at end of file +} // namespace teachos::arch::kernel + +#endif // TEACHOS_ARCH_X86_64_KERNEL_MAIN_HPP 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 new file mode 100644 index 0000000..b8370db --- /dev/null +++ b/arch/x86_64/include/arch/memory/allocator/area_frame_allocator.hpp @@ -0,0 +1,67 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_AREA_FRAME_ALLOCATOR_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_AREA_FRAME_ALLOCATOR_HPP + +#include "arch/memory/allocator/physical_frame.hpp" +#include "arch/memory/multiboot/reader.hpp" + +#include <optional> + +namespace teachos::arch::memory::allocator +{ + /** + * @brief Allocates memory linearly using memory areas read from the multiboot2 information pointer and leaks any + * deallocated frames. + */ + struct area_frame_allocator + { + /** + * @brief Constructor + * + * @param mem_info Structure containg all relevant information to map and allocate memory + */ + area_frame_allocator(multiboot::memory_information const & mem_info); + + /** + * @brief Allocate memory by finding and returning a free physical frame. + * + * @note 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 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. + * + * @note Simply does nothing, because the simply area frame + * allocator implementation does not keep track of free or used frames and can therefore not deallocate, because it + * does not know which frames have been alocated in the first place. + * + * @param physical_frame Previously allocated physical_frame that should be deallocated. + */ + auto deallocate_frame(physical_frame const & physical_frame) -> void; + + private: + /** + * @brief Find the next memory area and write it into current_area. + */ + auto choose_next_area() -> void; + + 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_AREA_FRAME_ALLOCATOR_HPP diff --git a/arch/x86_64/include/arch/memory/allocator/concept.hpp b/arch/x86_64/include/arch/memory/allocator/concept.hpp new file mode 100644 index 0000000..2d3f4ae --- /dev/null +++ b/arch/x86_64/include/arch/memory/allocator/concept.hpp @@ -0,0 +1,21 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_CONCEPT_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_CONCEPT_HPP + +#include "arch/memory/allocator/physical_frame.hpp" + +#include <optional> + +namespace teachos::arch::memory::allocator +{ + /** + * @brief Frame allocator concept required for allocating and deallocating physical frames in memory. + */ + template<typename T> + concept FrameAllocator = requires(T t, physical_frame const & a) { + { t.allocate_frame() } -> std::same_as<std::optional<physical_frame>>; + { t.deallocate_frame(a) } -> std::same_as<void>; + }; + +} // namespace teachos::arch::memory::allocator + +#endif // TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_CONCEPT_HPP diff --git a/arch/x86_64/include/arch/memory/allocator/physical_frame.hpp b/arch/x86_64/include/arch/memory/allocator/physical_frame.hpp new file mode 100644 index 0000000..7f04042 --- /dev/null +++ b/arch/x86_64/include/arch/memory/allocator/physical_frame.hpp @@ -0,0 +1,86 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_PHYSICAL_FRAME_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_PHYSICAL_FRAME_HPP + +#include "arch/shared/container.hpp" +#include "arch/shared/forward_value_iterator.hpp" + +#include <compare> +#include <cstdint> +#include <iterator> + +namespace teachos::arch::memory::allocator +{ + typedef std::size_t physical_address; + + std::size_t constexpr PAGE_FRAME_SIZE = 4096U; ///< Default page size of x86_84 is always 4KiB. + + /** + * @brief Specific physical frame containing helper functions to determine if a specific address is in that + * physical frame or not. + */ + struct physical_frame + { + /** + * @brief Defaulted constructor. + */ + constexpr physical_frame() = default; + + /** + * @brief Constructor. + * + * @param frame_number Index number that should be assigned to this physical frame. + */ + explicit constexpr physical_frame(std::size_t frame_number) + : frame_number(frame_number) + { + // Nothing to do + } + + /** + * @brief Returns the physical frame the given address is contained in. + * + * @param address Physical address we want to get the corresponding physical frame for. + * @return Frame the given address is contained in. + */ + auto static containing_address(physical_address address) -> physical_frame; + + /** + * @brief Get the start address of this physical frame. + * + * @return Start address of the physical frame. + */ + auto start_address() const -> physical_address; + + /** + * @brief Post increment operator. Returns a copy of the value. + * + * @return Copy of the incremented underlying frame number. + */ + auto operator++(int) -> physical_frame; + + /** + * @brief Pre increment operator. Returns a reference to the changed value. + * + * @return Reference to the incremented underlying frame number. + */ + auto operator++() -> physical_frame &; + + /** + * @brief Defaulted equals operator. + */ + auto operator==(physical_frame const & other) const -> bool = default; + + /** + * @brief Defaulted three-way comparsion operator. + */ + auto operator<=>(physical_frame const & other) const -> std::partial_ordering = default; + + std::size_t frame_number = + {}; ///< Index number of the current physical frame, used to distinguish it from other frames. + }; + + typedef shared::container<shared::forward_value_iterator<physical_frame>> frame_container; + +} // namespace teachos::arch::memory::allocator + +#endif // TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_PHYSICAL_FRAME_HPP diff --git a/arch/x86_64/include/arch/memory/allocator/tiny_frame_allocator.hpp b/arch/x86_64/include/arch/memory/allocator/tiny_frame_allocator.hpp new file mode 100644 index 0000000..1ceb74d --- /dev/null +++ b/arch/x86_64/include/arch/memory/allocator/tiny_frame_allocator.hpp @@ -0,0 +1,74 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_TINY_FRAME_ALLOCATOR_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_TINY_FRAME_ALLOCATOR_HPP + +#include "arch/memory/allocator/concept.hpp" +#include "arch/memory/allocator/physical_frame.hpp" + +#include <array> + +namespace teachos::arch::memory::allocator +{ + namespace + { + uint8_t constexpr TINY_ALLOCATOR_FRAMES_COUNT = 3U; + } + + /** + * @brief Allocates memory using memory areas read from the multiboot2 information pointer. Does not allocate its own + * frames, but uses the necessary three frames provided by another allocator to map one virtual level 1 page entry and + * the necessary upper layers. + */ + struct tiny_frame_allocator + { + /** + * @brief Constructor. + * + * @tparam T Contract the allocator that should be used to actually allocate and deallocate, the underlying three + * frames has to follow. + * + * @param allocator Reference to an allocator following the FrameAllocator concept, which is used to allocate + * entries when the underlying frames are created. + */ + template<allocator::FrameAllocator T> + tiny_frame_allocator(T & allocator) + : frames{} + { + // Has to be done this way, because constructing the constructor with the data from allocator.allocate_frames(), + // does not work because it would set the value correctly but because we pass it as an std::optional it would not + // set the engaged flag. Meaning the has_value() method would still return false. + for (auto & frame : frames) + { + auto allocated = allocator.allocate_frame(); + if (allocated.has_value()) + { + frame.emplace(allocated.value()); + } + } + } + + /** + * @brief Allocate memory by finding and returning one of the three free physical frames. + * + * @return First free physical frames of the three frames held by this allocator or nullopt if we used up all three + * frames already. + */ + auto allocate_frame() -> std::optional<physical_frame>; + + /** + * @brief Deallocates one of the three previously allocated physical frames. + * + * @note If more than the three frames are deallocated the method will halt execution, because it can only hold 3 + * frames. + * + * @param physical_frame Previously allocated physical_frame that should be deallocated. + */ + auto deallocate_frame(physical_frame const & physical_frame) -> void; + + private: + std::array<std::optional<physical_frame>, TINY_ALLOCATOR_FRAMES_COUNT> frames = + {}; ///< Container that holds the frames allocated by another allocator. + }; + +} // namespace teachos::arch::memory::allocator + +#endif // TEACHOS_ARCH_X86_64_MEMORY_ALLOCATOR_TINY_FRAME_ALLOCATOR_HPP diff --git a/arch/x86_64/include/arch/memory/cpu/control_register.hpp b/arch/x86_64/include/arch/memory/cpu/control_register.hpp new file mode 100644 index 0000000..e11813d --- /dev/null +++ b/arch/x86_64/include/arch/memory/cpu/control_register.hpp @@ -0,0 +1,71 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_CPU_CR3_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_CPU_CR3_HPP + +#include <cstdint> + +namespace teachos::arch::memory::cpu +{ + /** + * @brief Control registers that can be read and written to. + * + * @note CR1 and CR5 - 7 are reserved and will throw an exception if they are accessed, therefore they are not defined + * in the enum. See https://en.wikipedia.org/wiki/Control_register#Control_registers_in_Intel_x86_series for more + * information. + */ + enum struct control_register : uint8_t + { + CR0, ///< Contains various control flags that modify basic operation of the processor, Machine Status World (MSW) + ///< register. + CR2 = 2U, ///< Contains Page Fault Linear Address (PFLA), when page fault occurs address program attended to accces + ///< is stored here. + CR3, ///< Enables process to translate linear addresses into physical addresses using paging, CR0 bit 32 Paging + ///< (PG) needs to be enabled simply contains the register value that represents the physical address of the + ///< level 4 page table used for paging in the system. Therefore reading this value allows to access the level + ///< 4 page table directly. Instead of over the virtual address 0xffffffff'fffff000, which then has to be + ///< first translated into a physical address. + CR4 ///< Used in protected mode to control operations. + }; + + /** + * @brief Control register 0 flags that can be set. + * + * @note Modifies the basic operation of the processor. Only the most important extensions are listed below, the rest + * are excluded for brevity. See https://en.wikipedia.org/wiki/Control_register#CR0 for more information. + */ + enum struct cr0_flags : uint64_t + { + PROTECTED_MODE_ENABLED = 1U << 0U, ///< System is in protected or system is in real mode. + TASK_SWITCHED = 1U << 3U, ///< Allows saving x87 task context upon a task switch only after x87 instruction used. + WRITE_PROTECT = 1U << 16U, ///< When set, the CPU cannot write to read-only pages when privilege level is 0. + PAGING = 1U << 31U, // Enable paging using the CR3 register. + }; + + /** + * @brief Reads the value of the given control register. + * + * @param cr Control register that should be read. + * @return Value of the control register. + */ + auto read_control_register(control_register cr) -> uint64_t; + + /** + * @brief Sets a specific bit in the Extended Feature Enable Register (EFER) Model-Specific Register (MSR) register. + * + * @param cr Control register that should be written. + * @param new_value New value that should be written. + */ + auto write_control_register(control_register cr, uint64_t new_value) -> void; + + /** + * @brief Sets a specific bit in the CR0. + * + * @note This function reads the current value of the CR0 register, ORs the specified + * bit with the current value, and writes the updated value back to the CR0. + * + * @param flag he flag to set in the CR0. + */ + auto set_cr0_bit(cr0_flags flag) -> void; + +} // namespace teachos::arch::memory::cpu + +#endif // TEACHOS_ARCH_X86_64_MEMORY_CPU_CR3_HPP diff --git a/arch/x86_64/include/arch/memory/cpu/msr.hpp b/arch/x86_64/include/arch/memory/cpu/msr.hpp new file mode 100644 index 0000000..cda70e2 --- /dev/null +++ b/arch/x86_64/include/arch/memory/cpu/msr.hpp @@ -0,0 +1,64 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_CPU_NXE_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_CPU_NXE_HPP + +#include <bitset> +#include <cstdint> + +namespace teachos::arch::memory::cpu +{ + /** + * @brief Important flags that can be writen into the Extended Feature Enable Register (EFER). + * + * @note EFER is a model-specific register allowing to configure CPU extensions. Only the most important extensions + * are listed below, the rest are excluded for brevity. See https://en.wikipedia.org/wiki/Control_register#EFER for + * more information. + */ + enum class efer_flags : uint64_t + { + SCE = 1UL << 0UL, ///< System Call Extensions. + LME = 1UL << 8UL, ///< Long Mode Enabled. + LMA = 1UL << 10UL, ///< Long Mode Active. + NXE = 1UL << 11UL, ///< No-Execute Enable. + SVME = 1UL << 12UL, ///< Secure Virtual Machine Enable. + LMSLE = 1UL << 13UL, ///< Long Mode Segment Limit Enable. + FFXSR = 1UL << 14UL, ///< Fast FXSAVE/FXSTOR. + TCE = 1UL << 15UL, ///< Translation Cache Extension. + }; + + /** + * @brief Reads a 64-bit from the Model-Specific Register (MSR). + * + * @note This function reads the value of an MSR specified by the given address. It combines the lower and upper + * 32-bits of the MSR value read using the 'rdmsr' instruction and returns it as a 64-bit unsigned integer. + * + * @param msr The address of the MSR to read. + * @return The 64-bit value read from the MSR. + */ + auto read_msr(uint32_t msr) -> uint64_t; + + /** + * @brief Writes a 64-bit value to a Model-Specific Register (MSR). + * + * @note This function writes a 64-bit value to the MSR specified by the given address. + * It splits the 64-bit value into two 32-bit parts and writes them using the + * `wrmsr` instruction. + * + * @param msr The address of the MSR to write to. + * @param new_value The 64-bit value to write to the MSR. + */ + auto write_msr(uint32_t msr, uint64_t new_value) -> void; + + /** + * @brief Sets a specific bit in the Extended Feature Enable Register (EFER), which is a Model-Specific Register + * (MSR). + * + * @note This function reads the current value of the EFER register, ORs the specified + * bit with the current value, and writes the updated value back to the EFER register. + * + * @param flag The flag to set in the EFER register. + */ + auto set_efer_bit(efer_flags flag) -> void; + +} // namespace teachos::arch::memory::cpu + +#endif // TEACHOS_ARCH_X86_64_MEMORY_CPU_NXE_HPP
\ No newline at end of file diff --git a/arch/x86_64/include/arch/memory/cpu/tlb.hpp b/arch/x86_64/include/arch/memory/cpu/tlb.hpp new file mode 100644 index 0000000..075d7bb --- /dev/null +++ b/arch/x86_64/include/arch/memory/cpu/tlb.hpp @@ -0,0 +1,27 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_CPU_TLB_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_CPU_TLB_HPP + +#include "arch/memory/paging/virtual_page.hpp" + +namespace teachos::arch::memory::cpu +{ + /** + * @brief Invalidates any translation lookaside buffer (TLB) entry for the page table the given address is cotained + * in. See https://www.felixcloutier.com/x86/invlpg for more information on the used x86 instruction. + * + * @param address Memory address, which will be used to determine the contained page and flush the TLB entry for + * that page. + */ + auto tlb_flush(paging::virtual_address address) -> void; + + /** + * @brief Invalidates the translation lookaside buffer (TLB) entry for all page tables. + * + * @note Simply reassigns the CR3 register the value of the CR3 register, causing a flush of the TLB buffer, because + * the system has to assume that the location of the level 4 page table moved. + */ + auto tlb_flush_all() -> void; + +} // namespace teachos::arch::memory::cpu + +#endif // TEACHOS_ARCH_X86_64_MEMORY_CPU_TLB_HPP diff --git a/arch/x86_64/include/arch/memory/heap/bump_allocator.hpp b/arch/x86_64/include/arch/memory/heap/bump_allocator.hpp new file mode 100644 index 0000000..545b72f --- /dev/null +++ b/arch/x86_64/include/arch/memory/heap/bump_allocator.hpp @@ -0,0 +1,55 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_HEAP_BUMP_ALLOCATOR_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_HEAP_BUMP_ALLOCATOR_HPP + +#include <atomic> +#include <cstdint> + +namespace teachos::arch::memory::heap +{ + /** + * @brief Simple heap allocator, which allocates linearly and leaks all allocated memory, because it does not really + * deallocate anything. + */ + struct bump_allocator + { + /** + * @brief Constructor. + * + * @param heap_start Start of the allocatable heap area + * @param heap_end End of the allocatable heap area (Start + Size) + */ + bump_allocator(std::size_t heap_start, std::size_t heap_end) + : heap_start{heap_start} + , heap_end{heap_end} + , next{heap_start} + { + // Nothing to do + } + + /** + * @brief Allocates the specified amount of memory in the heap. + * + * @param size Amount of memory to allocate. + * @return Address of the first byte to the allocated area + */ + auto allocate(std::size_t size) -> void *; + + /** + * @brief Deallocates heap memory at the specified location. + * + * @note Simply does nothing, because this allocator leaks all memory. + * + * @param pointer Pointer to the location which should be deallocated. + * @param size Size of the underlying memory area we want to deallocate. + */ + auto deallocate(void * pointer, std::size_t size) -> void; + + private: + std::size_t heap_start; ///< Start of the allocatable heap area + std::size_t heap_end; ///< End of the allocatable heap area + std::atomic_uint64_t next; ///< Current address, which is the start of still unused allocatable heap area + }; + +} // namespace teachos::arch::memory::heap + +#endif // TEACHOS_ARCH_X86_64_MEMORY_HEAP_BUMP_ALLOCATOR_HPP diff --git a/arch/x86_64/include/arch/memory/heap/concept.hpp b/arch/x86_64/include/arch/memory/heap/concept.hpp new file mode 100644 index 0000000..e22e35f --- /dev/null +++ b/arch/x86_64/include/arch/memory/heap/concept.hpp @@ -0,0 +1,22 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_HEAP_CONCEPT_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_HEAP_CONCEPT_HPP + +#include <concepts> + +namespace teachos::arch::memory::heap +{ + std::size_t constexpr HEAP_START = 0x100000000; + std::size_t constexpr HEAP_SIZE = 100 * 1024; + + /** + * @brief Heap allocator concept required for allocating and managing free space on the heap. + */ + template<typename T> + concept HeapAllocator = requires(T t, uint8_t * pointer, std::size_t size) { + { t.allocate(size) } -> std::same_as<uint8_t *>; + { t.deallocate(pointer, size) } -> std::same_as<void>; + }; + +} // namespace teachos::arch::memory::heap + +#endif // TEACHOS_ARCH_X86_64_MEMORY_HEAP_CONCEPT_HPP diff --git a/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp b/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp new file mode 100644 index 0000000..06b21bb --- /dev/null +++ b/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp @@ -0,0 +1,132 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_HEAP_LINKED_LIST_ALLOCATOR_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_HEAP_LINKED_LIST_ALLOCATOR_HPP + +#include "arch/memory/heap/memory_block.hpp" +#include "arch/shared/mutex.hpp" + +namespace teachos::arch::memory::heap +{ + /** + * @brief Sorted by address list of memory holes (free memory). Uses free holes itself to save the information, + * containing the size and pointer to the next hole. Resulting in a singly linked list. + */ + struct linked_list_allocator + { + /** + * @brief Constructor. + * + * @param heap_start Start of the allocatable heap area + * @param heap_end End of the allocatable heap area (Start + Size) + */ + linked_list_allocator(std::size_t heap_start, std::size_t heap_end); + + /** + * @brief Allocates the specified amount of memory in the heap. + * + * @note The specified size is used to find a free memory block with the exact same size, meaning we can remove that + * free memory block from the free list and simply return its address. Or it has to be big enough to hold the size + * and alteast enough memory for another free memory block entry (16 bytes). If the amount of memory of that free + * memory block is in between we cannot use it for our allocation, because we could only return it to the user, but + * the additional bytes, could not be used to create a free memory block. Additionaly the user couldn't know + * they received more memory than wanted. Therefore the memory would simply be unused and because it is neither + * allocated nor deallocated would never be indexed by the free memory list. We would therefore permanently loose + * that memory, to prevent that allocation into free memory blocks like that are impossible. + * + * @param size Amount of memory to allocate. + * @return Address of the first byte to the allocated area + */ + auto allocate(std::size_t size) -> void *; + + /** + * @brief Deallocates heap memory at the specified location. + * + * @note Simply does nothing, because this allocator leaks all memory. + * + * @param pointer Pointer to the location which should be deallocated. + * @param size Size of the underlying memory area we want to deallocate. + */ + auto deallocate(void * pointer, std::size_t size) -> void; + + private: + /** + * @brief Returns the smallest allocatable block of heap memory. + * + * @return Smallest allocatable block of heap memory. + */ + auto constexpr min_allocatable_size() -> std::size_t { return sizeof(memory_block); } + + /** + * @brief Removes a free memory block from the free list and returns its address so the caller can allocate into it. + * + * @param previous_block Free memory block before the block to allocate in our heap memory. Was to small to + * allocate the required size into. + * @param current_block Free memory block we want to remove from the free list and return for the allocation. + * + * @return Previous start address of the memory block we removed, because it can now be used for the allocation. + */ + auto remove_free_memory_block(memory_block * previous_block, memory_block * current_block) -> void *; + + /** + * @brief Splits the given free memory block into two, where the latter block keeps being free and the first + * part will be used for the allocation. + * + * @param previous_block Free memory block before the block to allocate in our heap memory. Was to small to + * allocate the required size into. + * @param current_block Free memory block we want to split into a size part for the allocation and the rest for + * future allocations. + * @param size Size we want to allocate at the start of the free memory block. + * + * @return Previous start address of the memory block we just split, because it can now be used for the allocation. + */ + auto split_free_memory_block(memory_block * previous_block, memory_block * current_block, + std::size_t size) -> void *; + + /** + * @brief Removes a free memory block from the free list and returns its address so the caller can allocate into it. + * + * @param previous_block Free memory block before the block to allocate in our heap memory. Was to small to + * allocate the required size into. + * @param current_block Free memory block we want to remove from the free list and return for the allocation. + * @param new_block Replaces the current block with the given new block can be nullptr, meaning the free list will + * end here. + * + * @return Previous start address of the memory block we removed, because it can now be used for the allocation. + */ + auto replace_free_memory_block(memory_block * previous_block, memory_block * current_block, + memory_block * new_block) -> void *; + + /** + * @brief Combines multiple free memory blocks into one if they are adjacent. + * + * @note The internal algorithm for recombination functions like this: + * 1. Check if there is even any memory left, if not the first entry of our linked list should be a nullptr and + * we can therefore set the first entry to our newly created entry. This entry is created in the now deallocated + * memory area. + * 2. If there are more blocks but neither the previous nor the current block are adjacent, we simply create a + * new free memory block of the given size and set the previous next to our block and the next of our block to + * the current block. + * 3. If the current block is adjacent the start address of the newly created block stays the same, but the size + * increases by the amount in the current memory block header. After reading it we also clear the header. + * 4. If the previous block is adjacent the size of the previous block simply increases to include the given + * size as well. + * 5. If the previous block is directly in our start address, so they overlap then it has to mean some or all of + * the region we are trying to deallocate has been freed before. Which would result in a double free therefore + * we halt the execution of the program. + * + * @param previous_block Free memory block before the block to deallocate in our heap memory. + * @param current_block Free memory block after the block to deallocate in our heap memory. + * @param pointer Block to deallocate. + * @param size Size of the block we want to deallocate. + */ + auto coalesce_free_memory_block(memory_block * previous_block, memory_block * current_block, void * pointer, + std::size_t size) -> void; + + std::size_t heap_start; ///< Start of the allocatable heap area. + std::size_t heap_end; ///< End of the allocatable heap area. + memory_block * first; ///< First free entry in our memory. + shared::mutex mutex; ///< Mutex to ensure only one thread calls allocate or deallocate at once. + }; + +} // namespace teachos::arch::memory::heap + +#endif // TEACHOS_ARCH_X86_64_MEMORY_HEAP_LINKED_LIST_ALLOCATOR_HPP diff --git a/arch/x86_64/include/arch/memory/heap/memory_block.hpp b/arch/x86_64/include/arch/memory/heap/memory_block.hpp new file mode 100644 index 0000000..b9a2254 --- /dev/null +++ b/arch/x86_64/include/arch/memory/heap/memory_block.hpp @@ -0,0 +1,38 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_BLOCK_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_BLOCK_HPP + +#include <cstdint> + +namespace teachos::arch::memory::heap +{ + /** + * @brief Block containing free memory, pointing to the next free hole (nullptr) if there is none. + * Forms a singly linked list of free memory blocks that we can callocate memory into. + */ + struct memory_block + { + /** + * @brief Constructor. Clears all memory from the place it was allocated until the end (address + + * size). + * + * @param size Amount of free memory of this specific hole. + * @param next Optional pointer to the next free memory. + */ + memory_block(std::size_t size, memory_block * next); + + /** + * @brief Destructor. Clears all internal memory. + * + * @note Used so the memory can be reused to construct other classes into, without having the old values. + * Required because we cannot call delete, because it causes "undefined reference to `sbrk`". + */ + ~memory_block(); + + std::size_t size; ///< Amount of free memory this hole contains, has to always be atleast 16 bytes to hold the + ///< size variable and the pointer to the next hole. + memory_block * next; ///< Optional pointer to the next free memory, holds nullptr if there is none. + }; + +} // namespace teachos::arch::memory::heap + +#endif // TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_BLOCK_HPP diff --git a/arch/x86_64/include/arch/memory/main.hpp b/arch/x86_64/include/arch/memory/main.hpp new file mode 100644 index 0000000..164abbc --- /dev/null +++ b/arch/x86_64/include/arch/memory/main.hpp @@ -0,0 +1,16 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_MAIN_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_MAIN_HPP + +namespace teachos::arch::memory +{ + /** + * @brief Initializes memory management. + * + * @note Enables the necessary register flags and remaps the kernel, + * elf_sections, vga_text and the heap. + */ + auto initialize_memory_management() -> void; + +} // namespace teachos::arch::memory + +#endif // TEACHOS_ARCH_X86_64_MEMORY_MAIN_HPP diff --git a/arch/x86_64/include/arch/memory/multiboot/elf_symbols_section.hpp b/arch/x86_64/include/arch/memory/multiboot/elf_symbols_section.hpp new file mode 100644 index 0000000..e8f6b0a --- /dev/null +++ b/arch/x86_64/include/arch/memory/multiboot/elf_symbols_section.hpp @@ -0,0 +1,169 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_MULTIBOOT_ELF_SYBOLS_SECTION_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_MULTIBOOT_ELF_SYBOLS_SECTION_HPP + +#include "arch/memory/multiboot/info.hpp" +#include "arch/shared/container.hpp" +#include "arch/shared/contiguous_pointer_iterator.hpp" + +#include <bitset> +#include <cstdint> + +namespace teachos::arch::memory::multiboot +{ + /** + * @brief Defines all elf section types an elf section header can have. + * + * @note See https://docs.oracle.com/cd/E19683-01/816-1386/chapter6-94076/index.html for more information. + */ + enum struct elf_section_type : uint32_t + { + INACTIVE, ///< (SHT_NULL) Unused, meaning all values are zeroed out. + PROGRAMM, ///< (SHT_PROGBITS) Program data (DATA, CODE). + SYMBOL_TABLE, ///< (SHT_SYMBTAB) Contains actual entries pointed to in symbol hash table. + STRING_TABLE, ///< (SHT_STRTAB) Contains symbols, section and deubbging null-terminated strings. + RELOCATION_ENTRY_WITH_ADDENDS, ///< (SHT_RELA) Only used on 64 bit systems. + SYMBOL_HASH_TABLE, ///< (SHT_HASH) Hash table used by dynamic linker to locate symbols. + DYNAMIC, ///< (SHT_DYNAMIC) Contains dynamic linking information. + NOTE, ///< (SHT_NOTE) Stores information that marks files in some way. + EMPTY, ///< (SHT_NOBITS) Program data section, that occupies no space in the file (.bss). + RELOCATION_ENTRY_WITHOUT_ADDENDS, ///< (SHT_REL) Only used on 32 bit systems. + UNSPECIFIED, ///< (SHT_SHLIB) Reserved but has unspecified semantics. + DYNAMIC_SYMBOL_TABLE, ///< (SHT_DYNSYM) Holds minimal set of symbols adequate for dynamic linking. + INITALIZATION_FUNCTION_ARRAY = 14, ///< (SHT_INIT_ARRAY) Array of pointers to intialization functions () -> void. + TERMINATION_FUNCTION_ARRAY, ///< (SHT_FINI_ARRAY) Array of pointers to termination functions () -> void. + PRE_INITALIZATION_FUNCTION_ARRAY ///< (SHT_PRE_INIT_ARRAY) Array of pointers to functions invoked before other + ///< initalization functions () -> void. + }; + + /** + * @brief Defines helper function for all states that the elf section flags of an elf section header can + * have. + * + * @note See https://docs.oracle.com/cd/E19683-01/816-1386/chapter6-94076/index.html for more information. + */ + struct elf_section_flags + { + /** + * @brief Possible set bits in our underlying std::bitset and the meaning when they are set. + */ + enum bitset : uint32_t + { + WRITABLE = 1U << 0U, ///< (SHF_WRITE) Section is writable at runtime. If it isn't then the section + ///< is assumed to be READONLY and only that flag is shown in the objdump. + OCCUPIES_MEMORY = 1U << 1U, ///< (SHF_ALLOC) Section occupies memory during execution. + ///< ALLOC flag is shown in the objdump. + EXECUTABLE_CODE = 1U << 2U, ///< (SHF_EXECINSTR) Section is executable. CODE flag is shown in the object dump. + DUPLICATE_DATA = 1U << 4U, ///< (SHF_MERGE) Section might be merged with another section. + CONTAINS_STRING = 1U << 5U, ///< (SHF_STRINGS) Section contains null-terminated strings. + SECTION_HEADER_INFO_IS_SECTION_HEADER_TABLE_INDEX = + 1U << 6U, ///< (SHF_INFO_LINK) Section contains the section header table index in the (sh_info) + ///< additional_information variable. + PRESERVE_ORDERING_AFTER_COMBINATION = + 1U << 7U, ///< (SHF_LINK_ORDER) Section preserves order after combining with another section. + REQUIRES_SPECIAL_OS_PROCESSING = + 1U << 8U, ///< (SHF_OS_NONCONFORMING) Section requires non-standard OS specific handling of its code or + ///< data, which does not confirm to standard ELF specifications. + SECTION_GROUP_MEMBER = 1U << 9U, ///< (SHF_GROUP) Section is a member of a section group. + HOLDS_THREAD_LOCAL_DATA = 1U << 10U, ///< (SHF_TLS) Section holds thread-local data. + COMPRESSED = 1U << 11U, ///< (SHF_COMPRESSED) Section contains compressed data. + SPECIAL_ORDERING_REQUIREMENTS = + 1U << 30U, ///< (SHF_ORDERED) Section has special ordering requirements, meaning it + ///< should be ordered in relation to other sections of the same type. + EXCLUDED_UNLESS_REFERENCED_OR_ALLOCATED = 1U << 31U, ///< (SHF_EXCLUDE)Section is excluded unless referenced or + ///< allocated, used for LTO (Link-Time Optimizations). + }; + + /** + * @brief Constructor. + * + * @param flags Actual value read from the elf section header, which should be converted into a std::bitset, to + * allow reading the state of single bits more easily. + */ + explicit elf_section_flags(uint64_t flags) + : flags(flags) + { + // Nothing to do + } + + /** + * @brief Checks if the given std::bitset is a subset or equivalent to the underlying std::bitset. + * + * @note Meaning that all bits that are set in the given std::bitset also have to be set in the underlyng + * std::bitset. Any additional bits that are set are not relevant. + * + * @param other Flags that we want to compare against and check if the underlying std::bitset has the same bits set. + * @return Whether the given flags are a subset or equivalent with the underlying std::bitset. + */ + auto contains_flags(std::bitset<64U> other) const -> bool; + + /** + * @brief Allows to compare the underlying std::bitset of two instances. + * + * @param other Other instance that we want to compare with. + * @return Whether the underlying std::bitset of both types is the same. + */ + auto operator==(elf_section_flags const & other) const -> bool = default; + + private: + std::bitset<64U> flags; ///< Underlying bitset used to read the flags from. Bits 21 - 28 are reserved for operating + ///< system specific semantics and bits 29 - 32 are reserved for processor specific + ///< semantics. Bits 33 - 64 are unused for compatability with ELF32. + }; + + /** + * @brief Defines the data included in a section header, where each section has exactly one section header. + * + * @note See https://refspecs.linuxbase.org/elf/gabi4+/ch4.sheader.html for more information. + */ + struct elf_section_header + { + uint32_t name_table_index; ///< Index into the section header string table, specifies the name of the section. + elf_section_type type; ///< Categorizes the sections content and semantics. + elf_section_flags flags; ///< 1-bit flgas that describe section attributes. + uint64_t physical_address; ///< If section appears in memory image of a process, gives address at which the + ///< sections first byte should reside, otherwise 0. + uint64_t file_offset; ///< Offset from the beginning of the file to the first byte in the section. SHT_NOBITS + ///< contains the conceptual placement instead (because it occupies no space in the file). + uint64_t section_size; ///< Complete section size in bytes, SHT_NOBITS may have non-zero value but will always + ///< occupy no space in the file. + uint32_t other_section; ///< Section header table index link, behaviour varies on type + ///< https://refspecs.linuxbase.org/elf/gabi4+/ch4.sheader.html#sh_link. + uint32_t additional_information; ///< Extra information, behaviour varies on type + ///< https://refspecs.linuxbase.org/elf/gabi4+/ch4.sheader.html#sh_link. + uint64_t address_alignment; ///< Possible address alignment constraints. Value of virutal_address must be 0 % value + ///< of address_alignment. Value 0 or 1 mean no alignment constraints. + uint64_t fixed_table_entry_size; ///< If sections holds table with fixed-sized entries, this gives the size in + ///< bytes of each entry. + + /** + * @brief Detect whether a section header is inactive or not, should always be the case for the first entry in the + * sections table. + * + * @return Whether the current section header is actually null or not, requires all fields besides section_size and + * other_section to contain 0. + */ + auto is_null() const -> bool; + }; + + /** + * @brief Defines an entry in the multi_boot_tag array of the multi_boot_info struct, of type + * multi_boot_tag_type::ELF_SECTIONS. + * + * @note The first section in the sections array will always be INACTIVE, there can only ever be one DYNAMIC section + * and only either one DYNAMIC_SYMBOL_TABLE or SYMBOL_TABLE. + */ + struct elf_symbols_section_header + { + tag info; ///< Basic multi_boot_tag information. + uint32_t number_of_sections; ///< Number of sections in the sections array. + uint32_t entry_size; ///< Size of each entry in the sections array. + uint32_t section_index; ///< Index to the string table used for symbol names. + std::byte end; ///< Marks the end of the tag, used to mark the beginning of any additional data. + ///< contained in the section, to ensure byte alignment is actually 4 byte. + }; + + typedef shared::container<shared::contiguous_pointer_iterator<elf_section_header>> elf_section_header_container; + +} // namespace teachos::arch::memory::multiboot + +#endif // TEACHOS_ARCH_X86_64_MEMORY_MULTIBOOT_ELF_SYBOLS_SECTION_HPP diff --git a/arch/x86_64/include/arch/memory/multiboot/info.hpp b/arch/x86_64/include/arch/memory/multiboot/info.hpp new file mode 100644 index 0000000..a9abf12 --- /dev/null +++ b/arch/x86_64/include/arch/memory/multiboot/info.hpp @@ -0,0 +1,64 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_MULTIBOOT_INFO_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_MULTIBOOT_INFO_HPP + +#include <cstdint> + +namespace teachos::arch::memory::multiboot +{ + /** + * @brief Defines all possible types a multiboot2 tag structure can have. + * + * @note See + * https://github.com/rhboot/grub2/blob/fedora-39/include/multiboot2.h for more information on the structure of the + * tag headers and see https://github.com/rhboot/grub2/blob/fedora-39/include/multiboot.h for more information on the + * actual header contents and their following data. + */ + enum struct tag_type : uint32_t + { + END, ///< Signals final tag for the multiboot2 information structure. + CMDLINE, ///< Contains the command line string. + BOOT_LOADER_NAME, ///< Contains the name of the boot loader booting the kernel. + MODULE, ///< Indicates the boot module which was loaded along the kernel image. + BASIC_MEMORY_INFO, ///< Contains the amount of lower (0MB start address) and upper memory (1MB start address). + BOOTDEV, ///< Indicates which BIOS disk device the hoot loader has loaded the OS image from. + MEMORY_MAP, ///< Describes the memory layout of the system with individual areas and their flags. + VBE_INFO, ///< Includes information to access and utilize the device GPU. + FRAMEBUFFER, ///< VBE framebuffer information. + ELF_SECTIONS, ///< Includes list of all section headers from the loaded ELF kernel. + APM_INFO, ///< Advanced Power Management information. + EFI32, ///< EFI 32 bit system table pointer. + EFI64, ///< EFI 64 bit system table pointer. + SMBIOS, ///< Contains copy of all Sytem Management BIOS tables. + ACPI_OLD, ///< Contains copy of RSDP as defined per ACPI1.0 specification. + ACPI_NEW, ///< Contains copy of RSDP as defined per ACPI2.0 or later specification. + NETWORK, ///< Contains network information specified specified as DHCP. + EFI_MEMORY_MAP, ///< Contains EFI memory map. + EFI_BS_NOT_TERMINATED, ///< Indicated ExitBootServies wasn't called. + EFI32_IMAGE_HANDLE, ///< EFI 32 bit image handle pointer. + EFI64_IMAGE_HANDLE, ///< EFI 64 bit imae handle pointer. + LOAD_BASE_ADDRESS ///< Contains image load base physical address. + }; + + /** + * @brief Basic structure that every entry in the multi_boot_tag array of the multi_boot_info struct has to begin + * with. + */ + struct tag + { + tag_type type; ///< Specific type of this multi_boot_tag entry, used to differentiate handling. + uint32_t size; ///< Total size of this multi_boot_tag entry with all fields of the actual type. + }; + + /** + * @brief Basic structure the multiboot_information_pointer points too and which contains all information of + * multiboot2 in the tags array of different types. The start as well as the content has to be 8 byte aligned. + */ + struct info_header + { + uint32_t total_size; ///< Total size of all multiboot::tags and their data. + alignas(8) struct tag tags; ///< Specific tags. + }; + +} // namespace teachos::arch::memory::multiboot + +#endif // TEACHOS_ARCH_X86_64_MEMORY_MULTIBOOT_INFO_HPP diff --git a/arch/x86_64/include/arch/memory/multiboot/memory_map.hpp b/arch/x86_64/include/arch/memory/multiboot/memory_map.hpp new file mode 100644 index 0000000..c28c986 --- /dev/null +++ b/arch/x86_64/include/arch/memory/multiboot/memory_map.hpp @@ -0,0 +1,53 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_MULTIBOOT_MEMORY_MAP_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_MULTIBOOT_MEMORY_MAP_HPP + +#include "arch/memory/multiboot/info.hpp" +#include "arch/shared/container.hpp" +#include "arch/shared/contiguous_pointer_iterator.hpp" + +#include <cstdint> + +namespace teachos::arch::memory::multiboot +{ + /** + * @brief Defines all memory area types possible that the memory region can be in. + */ + enum struct memory_area_type : uint32_t + { + AVAILABLE = 1, ///< Region is available for use by the OS. + RESERVED, ///< Region is reserved by firmware or bootloader and should not be used by OS. + ACPI_AVAILABLE, ///< Region is reclaimable by OS after ACPI event. + RESERVED_HIBERNATION, ///< Region is used for Non-volatile Storage (NVS). + DEFECTIVE ///< Region is defective or unusable. + }; + + /** + * @brief Defines an entry in the entries array of the memory_map struct. + * + * @note Last value needs to be padded, because the size of the entry needs to be + * exactly 24 bytes and not one byte more. + */ + struct memory_area + { + uint64_t base_address; ///< Base address the memory region starts at. + uint64_t area_length; ///< Size of the memory region, added to base_address results in the final address. + alignas(8) memory_area_type type; ///< Specific type of memory the region can contain. + }; + + /** + * @brief Defines an entry in the multi_boot_tag array of the multi_boot_info struct, of type + * multi_boot_tag_type::MEMORY_MAP. + */ + struct memory_map_header + { + tag info; ///< Basic multi_boot_tag information. + uint32_t entry_size; ///< Size of each entry in the memory_area array. Guaranteed multiple of 8. + uint32_t entry_version; ///< Version of the entries, currently 0. + struct memory_area entries; ///< Specific memory regions. + }; + + typedef shared::container<shared::contiguous_pointer_iterator<memory_area>> memory_area_container; + +} // namespace teachos::arch::memory::multiboot + +#endif // TEACHOS_ARCH_X86_64_MEMORY_MULTIBOOT_MEMORY_MAP_HPP diff --git a/arch/x86_64/include/arch/memory/multiboot/reader.hpp b/arch/x86_64/include/arch/memory/multiboot/reader.hpp new file mode 100644 index 0000000..bda0c43 --- /dev/null +++ b/arch/x86_64/include/arch/memory/multiboot/reader.hpp @@ -0,0 +1,53 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_MULTIBOOT_READER_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_MULTIBOOT_READER_HPP + +#include "arch/memory/multiboot/elf_symbols_section.hpp" +#include "arch/memory/multiboot/memory_map.hpp" + +#include <cstdint> + +namespace teachos::arch::memory::multiboot +{ + /** + * @brief Contains all relevant information to map and allocate memory that is read from the multiboot2 information + * structure. + */ + struct memory_information + { + std::size_t kernel_start; ///< Start address of the kernel code in memory. + std::size_t kernel_end; ///< End address of the kernel code in memory. + elf_section_header_container sections; ///< Contains non-owning pointers to all kernel sections. + std::size_t multiboot_start; ///< Start address of the multiboot code in memory. + std::size_t multiboot_end; ///< End address of the multiboot code in memory. + memory_area_container areas; ///< Contains non-owning pointers to all memory areas. + }; + + /** + * @brief Reads the relevant multiboot2 information data from memory. + * + * @note This is done using the multiboot_information_pointer, which marks the start of the multiboot2 data. The + * indivdual headers we have to read are 8 byte aligned, whereas the data contained in those headers does not have to + * be. All sections that are read additionaly receive some sanity to ensure the read address is actually pointing to + * the expected structure, if they are not this method will assert. + * + * The memory_information variables are calcualted like this: + * - kernel_start: Calculated by getting the lowest address specified in the elf symbols headers. + * - kernel_end: Calculated by getting the highest address specified in the elf symbols headers and adding the length + * of that section. + * - multiboot_start: Calcualted by simply getting the value of the multiboot information pointer, because it already + * contains the address pointint to the start of the multiboot2 data. + * - multiboot_end: Calcualted by getting the value of the multiboot information pointer and adding the total size of + * the complete multiboot2 data + * - memory_areas: Calculated by simply accessing the address of the entries variable in the memory map header + * structure. + * - area_count: Calculated by subtracing the memory map header size from the total tag size, which results in the + * remaining size (size of the entries array), this size is then divided by the size of one entry in that array, which + * should be 24 bytes. + * + * @return Relevant data read from multiboot2. + */ + auto read_multiboot2() -> memory_information; + +} // namespace teachos::arch::memory::multiboot + +#endif // TEACHOS_ARCH_X86_64_MEMORY_MULTIBOOT_READER_HPP diff --git a/arch/x86_64/include/arch/memory/paging/active_page_table.hpp b/arch/x86_64/include/arch/memory/paging/active_page_table.hpp new file mode 100644 index 0000000..1b2aaed --- /dev/null +++ b/arch/x86_64/include/arch/memory/paging/active_page_table.hpp @@ -0,0 +1,206 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_PAGING_ACTIVE_PAGE_TABLE_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_PAGING_ACTIVE_PAGE_TABLE_HPP + +#include "arch/exception_handling/assert.hpp" +#include "arch/memory/allocator/concept.hpp" +#include "arch/memory/cpu/tlb.hpp" +#include "arch/memory/paging/virtual_page.hpp" + +#include <array> +#include <bitset> +#include <optional> + +namespace teachos::arch::memory::paging +{ + /** + * @brief Currently actively by the CPU used level 4 page table, is used to ensure there is only ever one valid + * instance and it cannot be copied or constructed again. + */ + struct active_page_table + { + /** + * @brief Creates a single instance of an active level 4 page table table and returns the created instance or + * alternatively returns the previously created instance instead. The instance is owned by this method and is + * static, meaning it lives on for the complete lifetime of the program. + * + * @return Active single unique instance of the level 4 page table. + */ + static auto create_or_get() -> active_page_table &; + + /** + * @brief Index operator overload to access specific mutable entry directy of the level 4 page table. + * + * @param index Index of the entry we want to access and only read. + * @return Entry at the given table index. + */ + auto operator[](std::size_t index) -> entry &; + + /** + * @brief Translates virtual address into corresponding physical address. Calls translate_page under the hood. + * + * @param address Virtual address we want to translate into physical one. + * @return Physical address corresponding to the provided virtual address. + */ + auto translate_address(virtual_address address) -> std::optional<allocator::physical_address>; + + /** + * @brief Translates page into physical frame, will first attempt to parse normally using default page size and if + * it failed attempt to parse using huge pages. + * + * @param page Page to translate into physical frame. + * @return Physical frame corresponding to the provided virtual page. + */ + auto translate_page(virtual_page page) -> std::optional<allocator::physical_frame>; + + /** + * @brief Translates huge page into actual physical frame. + * + * @param page Page to translate into physical frame. + * @return Physical frame corresponding to the provided virtual page. + */ + auto translate_huge_page(virtual_page page) -> std::optional<allocator::physical_frame>; + + /** + * @brief Maps a virtual page to a physical frame in the page table with the specified flags. + * + * @note Allocates and maps an entry in every page level if it does not exists yet down to level 1. If the level 1 + * page table already exists it halts execution instead. + * + * @tparam T Type constraint of the allocator, being that is follows the given concept and contains an allocate and + * deallocate method. + * @param allocator Reference to an allocator following the FrameAllocator concept, which is used to allocate + * entries when a new page table is required. + * @param page Virtual page that is being mapped. + * @param frame Physical frame that the virtual page will be mapped to. + * @param flags A bitset of flags that configure the page table entry for this mapping. + */ + template<allocator::FrameAllocator T> + auto map_page_to_frame(T & allocator, virtual_page page, allocator::physical_frame frame, + std::bitset<64U> flags) -> void + { + auto current_handle = active_handle; + + for (auto level = page_table_handle::LEVEL4; level != page_table_handle::LEVEL1; --level) + { + current_handle = current_handle.next_table_or_create(allocator, page.get_level_index(level)); + } + + auto & level1_entry = current_handle[page.get_level_index(page_table_handle::LEVEL1)]; + arch::exception_handling::assert(!level1_entry.contains_flags(entry::HUGE_PAGE), + "[Page Mapper] Unable to map huge pages"); + arch::exception_handling::assert(level1_entry.is_unused(), "[Page Mapper] Page table entry is already used"); + level1_entry.set_entry(frame, flags.to_ulong() | entry::PRESENT); + } + + /** + * @brief Allocates the next free frame and then uses that frame to call map_page_to_frame. + * + * @see map_page_to_frame + */ + template<allocator::FrameAllocator T> + auto map_page_to_next_free_frame(T & allocator, virtual_page page, std::bitset<64U> flags) -> void + { + auto const frame = allocator.allocate_frame(); + exception_handling::assert(frame.has_value(), "[Page mapper] Out of memory exception"); + map_page_to_frame(allocator, page, frame.value(), flags); + } + + /** + * @brief Gets the corresponding page the given frame has to be contained in and uses that to call + * map_page_to_frame. + * + * @see map_page_to_frame + */ + template<allocator::FrameAllocator T> + auto identity_map(T & allocator, allocator::physical_frame frame, std::bitset<64U> flags) -> void + { + auto const page = virtual_page::containing_address(frame.start_address()); + map_page_to_frame(allocator, page, frame, flags); + } + + /** + * @brief Unmaps the virtual page from the previously mapped to physical frame and resets the flags. + * + * @note For the unmap function to deallocates and unmaps correctly, the entry in every page level if this page was + * the last one up to level 4 should be unmapped and ensured to clear the Translation Lookaside Buffer, so that the + * unmapped value is removed from cache as well. This is currently not done and instead we only dallocate and unmap + * the level 1 page table entry, this is the case because it conflicts with our recursive mapping for the temporary + * page, which requires the other page table entries to walk to the actual level 4 page table. If we remove all page + * table entries beforehand, we therefore can not remap the kernel anymore. + * + * @tparam T Type constraint of the allocator, being that is follows the given concept and contains an allocate and + * deallocate method. + * @param allocator Reference to an allocator following the FrameAllocator concept, which is used to allocate + * entries when a new page table is required. + * @param page Virtual page that is being unmapped. + */ + template<allocator::FrameAllocator T> + auto unmap_page(T & allocator, virtual_page page) -> void + { + exception_handling::assert(translate_page(page).has_value(), + "[Page Mapper] Attempted to unmap page, which has not been mapped previously"); + + auto current_handle = active_handle; + + for (auto level = page_table_handle::LEVEL4; level != page_table_handle::LEVEL1; --level) + { + auto const level_index = page.get_level_index(level); + auto const next_handle = current_handle.next_table(level_index); + // The next table method failed even tough the page has to be mapped already, because translate_page did not + // fail. This can only mean that we attempted to unmap a huge page, which is not supported in the first place. + exception_handling::assert(next_handle.has_value(), "[Page Mapper] Unable to unmap huge pages"); + current_handle = next_handle.value(); + } + + unmap_page_table_entry(allocator, page, current_handle); + cpu::tlb_flush(page.start_address()); + } + + private: + /** + * @brief Private constructor should only be used by create or get method, which ensures to create only ever one + * instance. + * + * @param active_handle Handle to the underlying currently active level 4 page table. + */ + active_page_table(page_table_handle active_handle); + + /** + * @brief Deleted copy constructor. + */ + active_page_table(active_page_table const &) = delete; + + /** + * @brief Deleted copy assignment operator. + */ + active_page_table & operator=(active_page_table const &) = delete; + + /** + * @brief Unmaps specific page at the current internal handle level. + * + * @tparam T Type constraint of the allocator, being that is follows the given concept and contains an allocate and + * deallocate method. + * @param allocator Reference to an allocator following the FrameAllocator concept, which is used to allocate + * entries *when a new page table is required. + * @param page Virtual page that is being unmapped. + * @param handle Page Table handle we want to access the entry that should be cleared on. + */ + template<allocator::FrameAllocator T> + static auto unmap_page_table_entry(T & allocator, virtual_page page, page_table_handle & handle) -> void + { + auto level_index = page.get_level_index(handle.get_level()); + auto & entry = handle[level_index]; + auto const frame = entry.calculate_pointed_to_frame(); + exception_handling::assert(frame.has_value(), + "[Page Mapper] Attempted to unmap page, which has not been mapped previously"); + entry.set_unused(); + allocator.deallocate_frame(frame.value()); + } + + public: + page_table_handle active_handle; ///< Underlying active level 4 page table + }; + +} // namespace teachos::arch::memory::paging + +#endif // TEACHOS_ARCH_X86_64_MEMORY_PAGING_ACTIVE_PAGE_TABLE_HPP diff --git a/arch/x86_64/include/arch/memory/paging/inactive_page_table.hpp b/arch/x86_64/include/arch/memory/paging/inactive_page_table.hpp new file mode 100644 index 0000000..8d96740 --- /dev/null +++ b/arch/x86_64/include/arch/memory/paging/inactive_page_table.hpp @@ -0,0 +1,39 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_PAGING_INACTIVE_PAGE_TABLE_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_PAGING_INACTIVE_PAGE_TABLE_HPP + +#include "arch/memory/allocator/physical_frame.hpp" +#include "arch/memory/paging/active_page_table.hpp" +#include "arch/memory/paging/temporary_page.hpp" + +namespace teachos::arch::memory::paging +{ + /** + * @brief By the CPU used level 4 page table. + */ + struct inactive_page_table + { + /** + * @brief Constructor. + * + * @param frame Frame that should be mapped as the level 4 page table. + */ + inactive_page_table(allocator::physical_frame frame); + + /** + * @brief Constructor. + * + * @param frame Frame that should be mapped as the level 4 page table. + * @param active_page_table Actual active page table that should be unmapped so we can map a new level 4 + * page table. + * @param temporary_page Temporary page that should be used to map the given frame as the new level 4 page + * table. + */ + inactive_page_table(allocator::physical_frame frame, active_page_table & active_page_table, + temporary_page & temporary_page); + + allocator::physical_frame page_table_level_4_frame; ///< Temporary level 4 page table + }; + +} // namespace teachos::arch::memory::paging + +#endif // TEACHOS_ARCH_X86_64_MEMORY_PAGING_INACTIVE_PAGE_TABLE_HPP diff --git a/arch/x86_64/include/arch/memory/paging/kernel_mapper.hpp b/arch/x86_64/include/arch/memory/paging/kernel_mapper.hpp new file mode 100644 index 0000000..74f1c14 --- /dev/null +++ b/arch/x86_64/include/arch/memory/paging/kernel_mapper.hpp @@ -0,0 +1,159 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_PAGING_KERNEL_MAPPER_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_PAGING_KERNEL_MAPPER_HPP + +#include "arch/memory/cpu/control_register.hpp" +#include "arch/memory/paging/active_page_table.hpp" +#include "arch/memory/paging/inactive_page_table.hpp" +#include "arch/memory/paging/temporary_page.hpp" +#include "arch/video/vga/text.hpp" + +namespace teachos::arch::memory::paging +{ + /** + * @brief Kernel mapper that allows to remap the kernel elf sections in C++. + * + * @tparam T Contract the allocator that should be used to allocate frames for the remapping process has to fulfill. + */ + template<allocator::FrameAllocator T> + struct kernel_mapper + { + /** + * @brief Constructor. + * + * @param allocator Allocator that should be used to allocate frames for the remapping process. + * @param mem_info Information about elf kernel sections required for remapping process. + */ + kernel_mapper(T & allocator, multiboot::memory_information const & mem_info) + : allocator(allocator) + , mem_info(mem_info) + { + // Nothing to do + } + + /** + * @brief Remap the kernel, meaning we map the entire kernel and all of it's elf sections with the correct flags + * into memory and then replace the created mapping with the current one. + * + * @note We have to use a workaround with an + * inactive page table, that is not used by the CPU to ensure we are not changign memory that we are using. Because + * remapping active kernel memory in the kernel wouldn't work. + */ + auto remap_kernel() -> active_page_table & + { + temporary_page temporary_page{virtual_page{0xCAFEBABE}, allocator}; + auto & active_table = active_page_table::create_or_get(); + auto const frame = allocator.allocate_frame(); + exception_handling::assert(frame.has_value(), + "[Kernel Mapper] Frame could not be allocated and therefore kernel not mapped"); + inactive_page_table new_table{frame.value(), active_table, temporary_page}; + remap_elf_kernel_sections(new_table, temporary_page, active_table); + auto const old_table = switch_active_page_table(new_table); + // Turn old level 4 page table, mapped by assembler code into stack guard page. + // Only works if the identity mapped page tables by assembler are right above the stack. + auto const old_level_4_page = + virtual_page::containing_address(old_table.page_table_level_4_frame.start_address()); + active_table.unmap_page(allocator, old_level_4_page); + return active_table; + } + + private: + /** + * @brief Remaps the kernel elf sections. + * + * This is done with switching the current level 4 page table recursive + * mapping to any unmapped address in memory and then actually mapping the level 4 page table on that address. + * Once the remapping process is done we can restore the original recursive mapping with the complete remapped + * kernel. + * + * @note Because we change the entries we also have to ensure we flush the translation lookaside buffer, before we + * map the entries. + * + * @param inactive_table Level 4 page table we temporarily map the kernel into. + * @param temporary_page Temporary page that should be used for the mapping process and then + * unmapped once finished. + * @param active_table Active level 4 page table that has its recursive mapping overwritten temporarily and then + * restored once the process is finished. + */ + auto remap_elf_kernel_sections(inactive_page_table & inactive_table, temporary_page & temporary_page, + active_page_table & active_table) -> void + { + auto const backup = + allocator::physical_frame::containing_address(cpu::read_control_register(cpu::control_register::CR3)); + auto page_table_level4 = temporary_page.map_table_frame(backup, active_table); + + active_table[511].set_entry(inactive_table.page_table_level_4_frame, entry::PRESENT | entry::WRITABLE); + cpu::tlb_flush_all(); + map_elf_kernel_sections(active_table); + + page_table_level4[511].set_entry(backup, entry::PRESENT | entry::WRITABLE); + cpu::tlb_flush_all(); + temporary_page.unmap_page(active_table); + } + + /** + * @brief Switches the current active table pointed to by the CR3 register with another page table that is currently + * inactive. + * + * @param new_table Inactive page table that should now be made active and replace the current active one. + * @return The previous active page table. + */ + auto switch_active_page_table(inactive_page_table new_table) -> inactive_page_table + { + auto const backup = + allocator::physical_frame::containing_address(cpu::read_control_register(cpu::control_register::CR3)); + auto const old_table = inactive_page_table{backup}; + + auto const new_address = new_table.page_table_level_4_frame.start_address(); + cpu::write_control_register(cpu::control_register::CR3, new_address); + return old_table; + } + + /** + * @brief Maps the required entries according to every elf section and it's contained frames. Additionally each of + * thoose frames gets the correct entry flags according to elf section flags. + * + * @param active_table Active level 4 page table that should be used to map the required elf sections into entries. + * Has had its recursive mapping temporarily replaced and points to unmapped place in memory. + */ + auto map_elf_kernel_sections(active_page_table & active_table) -> void + { + exception_handling::assert(!mem_info.sections.empty(), "[Kernel Mapper] Kernel elf sections empty"); + for (auto const & section : mem_info.sections) + { + if (!section.flags.contains_flags(multiboot::elf_section_flags::OCCUPIES_MEMORY)) + { + continue; + } + exception_handling::assert(section.physical_address % allocator::PAGE_FRAME_SIZE == 0U, + "[Kernel Mapper] Section must be page aligned"); + auto const start_frame = allocator::physical_frame::containing_address(section.physical_address); + // End address is exclusive, so that it is not part of the section anymore (one past the last frame of this + // section). But end frame would now point to the actual last frame and not one past the last frame, therefore + // we increment by one to get one past the last frame of this section. + auto const end_frame = + ++(allocator::physical_frame::containing_address(section.physical_address + section.section_size - 1)); + + allocator::frame_container::iterator const begin{start_frame}; + allocator::frame_container::iterator const end{end_frame}; + allocator::frame_container const frames{begin, end}; + entry const entry{section.flags}; + + for (auto const & frame : frames) + { + active_table.identity_map(allocator, frame, entry.get_flags()); + } + } + + auto const vga_buffer_frame = + allocator::physical_frame::containing_address(video::vga::text::DEFAULT_VGA_TEXT_BUFFER_ADDRESS); + active_table.identity_map(allocator, vga_buffer_frame, entry::WRITABLE); + } + + T & allocator; + multiboot::memory_information const & + mem_info; ///< Information about elf kernel sections required for remapping process. + }; + +} // namespace teachos::arch::memory::paging + +#endif // TEACHOS_ARCH_X86_64_MEMORY_PAGING_KERNEL_MAPPER_HPP diff --git a/arch/x86_64/include/arch/memory/paging/page_entry.hpp b/arch/x86_64/include/arch/memory/paging/page_entry.hpp new file mode 100644 index 0000000..876ea3c --- /dev/null +++ b/arch/x86_64/include/arch/memory/paging/page_entry.hpp @@ -0,0 +1,116 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_PAGING_PAGE_ENTRY_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_PAGING_PAGE_ENTRY_HPP + +#include "arch/memory/allocator/physical_frame.hpp" +#include "arch/memory/multiboot/elf_symbols_section.hpp" + +#include <bitset> +#include <optional> + +namespace teachos::arch::memory::paging +{ + /** + * @brief Marks a specific entry in an actual page table. + */ + struct entry + { + /** + * @brief Possible set bits in our underlying std::bitset and the meaning when they are set. + */ + enum bitset : uint64_t + { + PRESENT = 1UL << 0UL, ///< Page is in memory and therefore present. + ///< is assumed to be READONLY and only that flag is shown in the objdump. + WRITABLE = 1UL << 1UL, ///< It is possible to write to the page. + USER_ACCESIBLE = 1UL << 2UL, ///< Page can be accessed in user mode instead of only in kernel mode code. + WRITE_THROUGH_CACHING = 1UL << 3UL, ///< Write to the page go directly to memory instead of the cache. + DISABLED_CACHING = 1UL << 4UL, ///< Page uses caching. + ACCESSED = 1UL << 5UL, ///< Page is currently in use. + DIRTY = 1UL << 6UL, ///< Page has been writen too. + HUGE_PAGE = 1UL << 7UL, ///< Page is huge (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. + GLOBAL = 1UL << 8UL, ///< Page is not flushed from caches on address space switches (PGE bit of CR4 register + ///< has to be set) + EXECUTING_CODE_FORBIDDEN = + 1UL << 63UL, ///< Page is forbidden from executing code (NXE bit in the EFER register has to be set) + }; + + /** + * @brief Defaulted constructor. + */ + entry() = default; + + /** + * @brief Creates a new entry object from a 64bit address. Should follow the scheme where bit index 12 - 51 are the + * actual address and the other bits are flags. + * + * @param flags Flags that will be passed to underlying std::bitset. + */ + explicit entry(uint64_t flags); + + /** + * @brief Converts the given elf section flags into the corresponding correct entry flags. + * + * @note Enables us to set the correct flags on a entry depending on which elf section it is contained in. For + * example entries of .text sections should be executable and read only or entries of .data sections should be + * writable but not executable. + * + * @param elf_flags Elf section flags we want to convert into entry flags. + * @return Entry that has the corresponding bit flags set. + */ + explicit entry(multiboot::elf_section_flags elf_flags); + + /** + * @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 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<allocator::physical_frame>; + + /** + * @brief Copies the address and flags from the given physical frame into the underlying std::bitset + * + * @param frame Physical frame that contains the address we want to copy into our underlying std::bitset. + * @param additional_flags Entry flags which will be copied into our underlying std::bitset. + */ + auto set_entry(allocator::physical_frame frame, std::bitset<64U> additional_flags) -> void; + + /** + * @brief Checks if the given std::bitset is a subset or equivalent to the underlying std::bitset. + * + * @note Meaning that all bits that are set in the given std::bitset also have to be set in the underlyng + * std::bitset. Any additional bits that are set are not relevant. + * + * @param other Flags that we want to compare against and check if the underlying std::bitset has the same bits set. + * @return Whether the given flags are a subset or equivalent with the underlying std::bitset. + */ + auto contains_flags(std::bitset<64U> other) const -> bool; + + /** + * @brief Extracts only the flags from the underlying entry and ignores all bits that contain the physical address. + * + * @return Extracted entry flags, without the physical address. + */ + auto get_flags() const -> std::bitset<64U>; + + private: + std::bitset<64U> flags; ///< Underlying bitset used to read the flags from. Bits 9 - 11 and 52 - 62 can be + ///< freely used for additional flags by the operating system. + }; + +} // namespace teachos::arch::memory::paging + +#endif // TEACHOS_ARCH_X86_64_MEMORY_PAGING_PAGE_ENTRY_HPP diff --git a/arch/x86_64/include/arch/memory/paging/page_table.hpp b/arch/x86_64/include/arch/memory/paging/page_table.hpp new file mode 100644 index 0000000..60a0a2f --- /dev/null +++ b/arch/x86_64/include/arch/memory/paging/page_table.hpp @@ -0,0 +1,148 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_PAGING_PAGE_TABLE_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_PAGING_PAGE_TABLE_HPP + +#include "arch/exception_handling/assert.hpp" +#include "arch/memory/allocator/concept.hpp" +#include "arch/memory/paging/page_entry.hpp" + +namespace teachos::arch::memory::paging +{ + std::size_t constexpr PAGE_TABLE_ENTRY_COUNT = 512U; ///< Default entry count of a page table in x86_84 is 512. + + /** + * @brief Forward delcaration of the page_table, because it should only be accessible over the handle. + * + * @note The actual methods or constructor are not defined meaning they are not callable from outside. Instead the + * struct is only fully defined in the implementation (.cpp) file of the page table, and therefore the memthods are + * only accesible in that file. + */ + struct page_table; + + /** + * @brief Handle that ensures accessing the page table is safe because it adds additional checks to the next_table + * method and ensures it can only be called if the table level is not LEVEL1. + */ + struct page_table_handle + { + /** + * @brief Level of the page table. + * + * Level 1 will not be able to call next_table anymore, because it would result in + * attempting to access memory that it should not. + */ + enum level : uint8_t + { + LEVEL1, + LEVEL2, + LEVEL3, + LEVEL4 + }; + + /** + * @brief Constructor. + * + * @param table Underlying page table the handle should point to. + * @param table_level Level the underlying page table is on, used to ensure safety. + */ + page_table_handle(page_table * table, level table_level); + + /** + * @brief Set every entry of the page to unused. + */ + auto zero_entries() -> void; + + /** + * @brief Checks if all entries of this page are unused. + */ + auto is_empty() const -> bool; + + /** + * @brief Get the current table level. + * + * @return Current table level. + */ + auto get_level() const -> level; + + /** + * @brief Returns the next page table level from the given page table index. Meaning we + * use an index into a Level 4 page table to get the according Level 3 page table. + * + * @note If this method is called with a Level 1 page table it will instead assert and halt execution, because there + * is no furthere page table and mangeling up and returning the physical address would cause hard to debug issues. + * + * @param table_index Index of this page table in the page table one level lower. + */ + auto next_table(std::size_t table_index) const -> std::optional<page_table_handle>; + + /** + * @brief Call next_table and then checks if the table already exists, if it does not it will use the given + * allocator to get the next free frame and set the entry to that instead. + * + * @param allocator Reference to an allocator following the FrameAllocator concept, which is used to allocate + * entries when a new page table is required. + * @param table_index Index of this page table in the page table one level lower. + */ + template<allocator::FrameAllocator T> + auto next_table_or_create(T & allocator, std::size_t table_index) -> page_table_handle + { + auto next_handle = next_table(table_index); + // If the next table method failed then it means that the page level of the frame we want allocate has not yet + // been created itself. So we have to do that before we are able to allocate the wanted frame. This has to be done + // for every level, meaning we potenitally create a level 4, level 3 and level 2 page entry, each pointing to a + // page table one level below. + if (!next_handle.has_value()) + { + auto const allocated_frame = allocator.allocate_frame(); + exception_handling::assert(allocated_frame.has_value(), "[Page mapper] Unable to allocate frame"); + this->operator[](table_index).set_entry(allocated_frame.value(), entry::PRESENT | entry::WRITABLE); + // There should now be an entry at the previously not existent index, therefore we can simply access it again. + next_handle = next_table(table_index); + exception_handling::assert(next_handle.has_value(), "[Page mapper] Unable to create new entry into page table"); + next_handle.value().zero_entries(); + } + return next_handle.value(); + } + + /** + * @brief Index operator overload to access specific mutable entry directy. + * + * @param index Index of the entry we want to access and only read. + * @return Entry at the given table index. + */ + auto operator[](std::size_t index) -> entry &; + + /** + * @brief Index operator overload to access specific immutable entry directy. + * + * @param index Index of the entry we want to access and read or write. + * @return Entry at the given table index. + */ + auto operator[](std::size_t index) const -> entry const &; + + /** + * @brief Pre decrement operator on the page table level enum, is defined so we can use it as a replacement + * for an int index in a range based for loop. + * + * @note Will halt execution if called with page_table_handle::LEVEL1, because there is no level below. Has to be + * defined as either a friend function or inline header method, because we define an operator of another type. In + * this instance friend function was choosen, because the struct itself also requires the operator, but declaring + * before the struct is not possible, because the enum is in the struct. This is inpossible because the struct + * requires the operator declared before itself to work, and the operator requires the struct declared before itself + * to work. Furthermore this allows the defintion of the method to be done in the cpp, avoiding includes in the + * header file. + * + * @param value Value we want to decrement on + * @return New level value decrement by one, meaning the level is also decrement by one Level4 --> Level3, ... + */ + friend auto operator--(level & value) -> level &; + + private: + page_table * table; ///< Handle to underlying page table, can never be null (invariant ensured by + ///< constructor) + level table_level; ///< Level page table is currently on, depends on how often next_level was + ///< called successfuly. + }; + +} // namespace teachos::arch::memory::paging + +#endif // TEACHOS_ARCH_X86_64_MEMORY_PAGING_PAGE_TABLE_HPP diff --git a/arch/x86_64/include/arch/memory/paging/temporary_page.hpp b/arch/x86_64/include/arch/memory/paging/temporary_page.hpp new file mode 100644 index 0000000..d0d7781 --- /dev/null +++ b/arch/x86_64/include/arch/memory/paging/temporary_page.hpp @@ -0,0 +1,64 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_PAGING_TEMPORARY_PAGE_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_PAGING_TEMPORARY_PAGE_HPP + +#include "arch/memory/allocator/physical_frame.hpp" +#include "arch/memory/allocator/tiny_frame_allocator.hpp" +#include "arch/memory/paging/active_page_table.hpp" +#include "arch/memory/paging/virtual_page.hpp" + +namespace teachos::arch::memory::paging +{ + /** + * @brief A temporary page used to remap the kernel. + */ + struct temporary_page + { + /** + * @brief Construct a new temporary page object. + * + * @tparam Type constraint of the allocator, being that is follows the given concept and contains an allocate and + * deallocate method. + * @param page Page to turn into temporary page. + * @param allocator Frame allocator used to fill page. + */ + template<allocator::FrameAllocator T> + temporary_page(virtual_page page, T & allocator) + : page{page} + , allocator{allocator} + { + // Nothing to do + } + + /** + * @brief Unmap the current page. + * + * @param active_table The current active page table. + */ + auto unmap_page(active_page_table & active_table) -> void; + + /** + * @brief Map the temporary page to a frame. + * + * @param frame The frame to which the page is mapped. + * @param active_table The current active page table. + * @return level1 page table handle containing the mapped page. + */ + auto map_table_frame(allocator::physical_frame frame, active_page_table & active_table) -> page_table_handle; + + private: + /** + * @brief Map the temporary page to a frame. + * + * @param frame The frame to which the page is mapped. + * @param active_table The current active page table. + * @return The virtual address of the page. + */ + auto map_to_frame(allocator::physical_frame frame, active_page_table & active_table) -> virtual_address; + + virtual_page page; ///< Underlying virtual page we want to temporarily map. + allocator::tiny_frame_allocator allocator; ///< Allocator that should be used to map the temporary page. + }; + +} // namespace teachos::arch::memory::paging + +#endif // TEACHOS_ARCH_X86_64_MEMORY_PAGING_TEMPORARY_PAGE_HPP
\ No newline at end of file diff --git a/arch/x86_64/include/arch/memory/paging/virtual_page.hpp b/arch/x86_64/include/arch/memory/paging/virtual_page.hpp new file mode 100644 index 0000000..d820e82 --- /dev/null +++ b/arch/x86_64/include/arch/memory/paging/virtual_page.hpp @@ -0,0 +1,91 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_PAGING_VIRTUAL_PAGE_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_PAGING_VIRTUAL_PAGE_HPP + +#include "arch/memory/allocator/physical_frame.hpp" +#include "arch/memory/paging/page_table.hpp" + +#include <compare> +#include <cstdint> +#include <optional> + +namespace teachos::arch::memory::paging +{ + typedef std::size_t virtual_address; + + /** + * @brief Virtual page entry contained in P1 page tables + */ + struct virtual_page + { + /** + * @brief Defaulted constructor. + */ + constexpr virtual_page() = default; + + /** + * @brief Constructor. + * + * @param page_number Index number of the current virtual page, used to distinguish it from other pages. + */ + explicit constexpr virtual_page(std::size_t page_number) + : page_number(page_number) + { + // Nothing to do + } + + /** + * @brief Returns the virtual page the given address is contained in. + * + * @param address Virtual address we want to get the corresponding virtual page for. + * @return Frame the given address is contained in. + */ + auto static containing_address(virtual_address address) -> virtual_page; + + /** + * @brief Evaluates the start address of the virtual page. + * + * @return Start address of the virtual page. + */ + auto start_address() const -> virtual_address; + + /** + * @brief Calculates the index into the page table with the given level, which leads to this virtual page. + * + * @param level Level of the page table we want to calculate the index for. + * @return Index into the page table with the given level. + */ + auto get_level_index(page_table_handle::level level) const -> size_t; + + /** + * @brief Post increment operator. Returns a copy of the value. + * + * @return Copy of the incremented underlying page number. + */ + auto operator++(int) -> virtual_page; + + /** + * @brief Pre increment operator. Returns a reference to the changed value. + * + * @return Reference to the incremented underlying page number. + */ + auto operator++() -> virtual_page &; + + /** + * @brief Defaulted equals operator. + */ + auto operator==(const virtual_page & other) const -> bool = default; + + /** + * @brief Defaulted three-way comparsion operator. + */ + auto operator<=>(const virtual_page & other) const -> std::partial_ordering = default; + + std::size_t page_number = + {}; ///< Index number of the current virtual page, used to distinguish it from other pages. + }; + + typedef shared::container<shared::forward_value_iterator<virtual_page>> page_container; + +} // namespace teachos::arch::memory::paging + +#endif // TEACHOS_ARCH_X86_64_MEMORY_PAGING_VIRTUAL_PAGE_HPP diff --git a/arch/x86_64/include/arch/shared/container.hpp b/arch/x86_64/include/arch/shared/container.hpp new file mode 100644 index 0000000..f2fd1dc --- /dev/null +++ b/arch/x86_64/include/arch/shared/container.hpp @@ -0,0 +1,83 @@ +#ifndef TEACHOS_ARCH_X86_64_SHARED_CONTAINER_HPP +#define TEACHOS_ARCH_X86_64_SHARED_CONTAINER_HPP + +#include <iterator> + +namespace teachos::arch::shared +{ + /** + * @brief Minimal iterator concept required for usage in container + */ + template<typename T> + concept Iterator = std::forward_iterator<T>; + + /** + * @brief Read-only container for given template type, that allow to easily use this container instance in C++20 + * ranges calls. + * + * @tparam T Iterator the container uses to signal the start and end of it's data, has to atleast be a simple forward + * iterator. + */ + template<Iterator T> + struct container + { + using iterator = T; ///< Iterators used by this container. + using size_type = std::size_t; ///< Maximum size of this container. + + /** + * @brief Defaulted constructor. + */ + container() = default; + + /** + * @brief Constructor. + * + * @param begin Iterator containing non-owning pointer to the first element of all memory areas. + * @param end Iterator pointing to one past the last element of all memory areas. + */ + container(iterator begin, iterator end) + : begin_itr(begin) + , end_itr(end) + { + // Nothing to do + } + + /** + * @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. + * + * @return Iterator pointing to first element of the memory area. + */ + auto begin() const -> iterator { return begin_itr; } + + /** + * @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. + * + * @return Iterator pointing to one past the last element of the memory area. + */ + auto end() const -> iterator { return end_itr; } + + /** + * @brief Calculates the size of this container, simply subtracts the iterator pointing to the first element by the + * last. + * + * @return Actual size of this container. + */ + auto size() const -> size_type { return std::distance(begin(), end()); } + + /** + * @brief Calcualtes the size and returns true if the size is 0 and the container therefore emtpy. + * + * @return Whether the container is empty, size being 0 or not + */ + auto empty() const -> bool { return size() == 0; } + + private: + iterator begin_itr = {}; ///< Pointer to the first element of the given template type. + iterator end_itr = {}; ///< Pointer to one pas the last element of the given template type. + }; + +} // namespace teachos::arch::shared + +#endif // TEACHOS_ARCH_X86_64_SHARED_CONTAINER_HPP diff --git a/arch/x86_64/include/arch/shared/contiguous_pointer_iterator.hpp b/arch/x86_64/include/arch/shared/contiguous_pointer_iterator.hpp new file mode 100644 index 0000000..e2520dc --- /dev/null +++ b/arch/x86_64/include/arch/shared/contiguous_pointer_iterator.hpp @@ -0,0 +1,190 @@ +#ifndef TEACHOS_ARCH_X86_64_SHARED_CONTIGUOUS_POINTER_ITERATOR_HPP +#define TEACHOS_ARCH_X86_64_SHARED_CONTIGUOUS_POINTER_ITERATOR_HPP + +#include <iterator> + +namespace teachos::arch::shared +{ + /** + * @brief Generic contiguous iterator for given template type. Allows to easily use this iterator instance in + * algorithm calls. + * + * @note Allows any value that is contained in an array in memory, which is a block of contiguous memory. This is the + * case because we assume we can simply increment or decrement the pointer address to get the next valid instance of + * the given value type. + * + * @tparam T Value the iterator points too. + */ + template<typename T> + struct contiguous_pointer_iterator + { + using iterator_category = std::contiguous_iterator_tag; ///< Iterator category of this type. + using difference_type = std::ptrdiff_t; ///< Type when diving one instance of this iterator by another. + using value_type = T; ///< Underlying value pointed to by this iterator. + using reference_type = value_type &; ///< Reference to value returned by dereference * operation. + using pointer_type = value_type *; ///< Pointer to value returned by arrow -> operation. + + /** + * @brief Defaulted constructor. + */ + contiguous_pointer_iterator() = default; + + /** + * @brief Constructor. + * + * @param p Underlying address the iterator should point too. + */ + explicit contiguous_pointer_iterator(value_type * p) + : ptr(p) + { + // Nothing to do + } + + /** + * @brief Dereferences the initally given pointer to its value. + * + * @return Reference to the value. + */ + auto operator*() const -> reference_type { return *ptr; } + + /** + * @brief Get underlying value, which is the intially passed pointer. + * + * @return Pointer to the underlying value passed intially. + */ + auto operator->() const -> pointer_type { return ptr; } + + /** + * @brief Pre decrement operator. Returns a reference to the changed address. + * + * @return Reference to the decremented underlying address. + */ + auto operator--() -> contiguous_pointer_iterator & + { + contiguous_pointer_iterator const old_value = *this; + ++ptr; + return old_value; + } + + /** + * @brief Pre increment operator. Returns a reference to the changed address. + * + * @return Reference to the incremented underlying address. + */ + auto operator++() -> contiguous_pointer_iterator & + { + ++ptr; + return *this; + } + + /** + * @brief Post decrement operator. Returns a copy of the address. + * + * @return Copy of the decremented underlying address. + */ + auto operator--(int) -> contiguous_pointer_iterator + { + auto const old_value = *this; + --ptr; + return old_value; + } + + /** + * @brief Post increment operator. Returns a copy of the address. + * + * @return Copy of the incremented underlying address. + */ + auto operator++(int) -> contiguous_pointer_iterator + { + auto const old_value = *this; + ++ptr; + return old_value; + } + + /** + * @brief Addition assignment operator. Returns a reference to the changed address. + * + * @param value Value we want to add to the underlying address. + * @return Reference to the changed underlying address. + */ + auto operator+=(difference_type value) -> contiguous_pointer_iterator & + { + ptr += value; + return *this; + } + + /** + * @brief Subtraction assignment operator. Returns a reference to the changed address. + * + * @param value Value we want to subtract from the underlying address. + * @return Reference to the changed underlying address. + */ + auto operator-=(difference_type value) -> contiguous_pointer_iterator & + { + ptr -= value; + return *this; + } + + /** + * @brief Addition operator. Returns the changed address. + * + * @param value Value we want to add to a copy of the underlying address. + * @return Copy of underlying address incremented by the given value. + */ + auto operator+(difference_type value) const -> contiguous_pointer_iterator + { + return contiguous_pointer_iterator{ptr + value}; + } + + /** + * @brief Subtraction operator. Returns the changed address. + * + * @param value Value we want to subtrcat from a copy of the underlying address. + * @return Copy of underlying address decremented by the given value. + */ + auto operator-(difference_type value) const -> contiguous_pointer_iterator + { + return contiguous_pointer_iterator{ptr - value}; + } + + /** + * @brief Subtraction operator. Returns the size difference between two iterators. + * + * @param other Other iterator we want to substract the underlying address with ours. + * @return Size difference between the underlying address of this instance and the given iterator. + */ + auto operator-(const contiguous_pointer_iterator & other) const -> difference_type { return ptr - other.ptr; } + + /** + * @brief Index operator overload. Returns a reference to the value at the given index. Simply returns the + * dereferenced underlying pointer incremented by the given index. + * + * @param index Index we want to access and get the value from. + * @return Reference to the value at the given index. + */ + auto operator[](difference_type index) const -> value_type & { return *(ptr + index); } + + /** + * @brief Defaulted comparsion operator. Simply compares the memory address of both iterators. + * + * @param other Other iterator to compare to. + * @return Whether both iterators point to the same underlying address in memory. + */ + auto operator==(contiguous_pointer_iterator const & other) const -> bool = default; + + /** + * @brief Defaulted threeway comparsion operator. Simply compares the memory address of both iterators. + * + * @param other Other iterator to compare to. + * @return Whether the given iterator is smaller or larger than this iterator. + */ + auto operator<=>(contiguous_pointer_iterator const & other) const -> std::strong_ordering = default; + + private: + pointer_type ptr = + {}; ///< Underlying value the iterator is currently pointing too and should increment or decrement. + }; + +} // namespace teachos::arch::shared + +#endif // TEACHOS_ARCH_X86_64_SHARED_CONTIGUOUS_POINTER_ITERATOR_HPP diff --git a/arch/x86_64/include/arch/shared/forward_value_iterator.hpp b/arch/x86_64/include/arch/shared/forward_value_iterator.hpp new file mode 100644 index 0000000..c5dfc06 --- /dev/null +++ b/arch/x86_64/include/arch/shared/forward_value_iterator.hpp @@ -0,0 +1,110 @@ +#ifndef TEACHOS_ARCH_X86_64_SHARED_FORWARD_VALUE_ITERATOR_HPP +#define TEACHOS_ARCH_X86_64_SHARED_FORWARD_VALUE_ITERATOR_HPP + +#include <iterator> + +namespace teachos::arch::shared +{ + /** + * @brief Concept for a type to have a post and prefix increment operator, that returns the correct type. + */ + template<typename T> + concept Incrementable = requires(T t) { + { ++t } -> std::same_as<T &>; + { t++ } -> std::same_as<T>; + }; + + /** + * @brief Iterable concept for the forward value iterator, meaning the type itself is incrementable and comparable. + */ + template<typename T> + concept Iterable = std::regular<T> && Incrementable<T>; + + /** + * @brief Generic forward iterator for given template type. Allows to easily use this iterator + * instance in algorithm calls. + * + * @note Allows any value that itself can be incremented until we have reached the end, does not interact with the + * address of the value in any way. + * + * @tparam T Value the iterator contains. + */ + template<Iterable T> + struct forward_value_iterator + { + using iterator_category = std::forward_iterator_tag; ///< Iterator category of this type. + using difference_type = std::ptrdiff_t; ///< Type when diving one instance of this iterator by another. + using value_type = T; ///< Underlying value contained by this iterator. + using const_reference_type = + value_type const &; ///< Constant reference to value returned by dereference * operation. + using const_pointer_type = value_type const *; ///< Constant pointer to value returned by arrow -> operation. + + /** + * @brief Defaulted constructor. + */ + forward_value_iterator() = default; + + /** + * @brief Constructor. + * + * @param value Underlying value the iterator contains. + */ + explicit forward_value_iterator(value_type value) + : value(value) + { + // Nothing to do + } + + /** + * @brief Returns the initally given value. + * + * @return Reference to the value. + */ + auto operator*() const -> const_reference_type { return value; } + + /** + * @brief Gets pointer to the underlying value passed intially. + * + * @return Pointer to the underlying value passed intially. + */ + auto operator->() const -> const_pointer_type { return &value; } + + /** + * @brief Pre increment operator. Returns a reference to the changed value. + * + * @return Reference to the incremented underlying value. + */ + auto operator++() -> forward_value_iterator & + { + ++value; + return *this; + } + + /** + * @brief Post increment operator. Returns a copy of the value. + * + * @return Copy of the incremented underlying value. + */ + auto operator++(int) -> forward_value_iterator + { + auto const old_value = *this; + ++value; + return old_value; + } + + /** + * @brief Defaulted comparsion operator. Simply compares the memory address of both iterators. + * + * @param other Other iterator to compare to. + * @return Whether both iterators point to the same underlying address in memory. + */ + auto operator==(forward_value_iterator const & other) const -> bool = default; + + private: + value_type value = + {}; ///< Underlying value the iterator is currently pointing too and should increment or decrement. + }; + +} // namespace teachos::arch::shared + +#endif // TEACHOS_ARCH_X86_64_SHARED_FORWARD_VALUE_ITERATOR_HPP diff --git a/arch/x86_64/include/arch/shared/mutex.hpp b/arch/x86_64/include/arch/shared/mutex.hpp new file mode 100644 index 0000000..b18a8b3 --- /dev/null +++ b/arch/x86_64/include/arch/shared/mutex.hpp @@ -0,0 +1,57 @@ +#ifndef TEACHOS_ARCH_X86_64_SHARED_MUTEX_HPP +#define TEACHOS_ARCH_X86_64_SHARED_MUTEX_HPP + +#include <atomic> + +namespace teachos::arch::shared +{ + /** + * @brief Custom mutex implementation, that simply wraps an atomic boolean to keep track if the mutex is already in + * use by another thread or not. + */ + struct mutex + { + /** + * @brief Defaulted constructor. + */ + mutex() = default; + + /** + * @brief Defaulted destructor. + */ + ~mutex() = default; + + /** + * @brief Deleted copy constructor. + */ + mutex(const mutex &) = delete; + + /** + * @brief Deleted assignment operator. + */ + mutex & operator=(const mutex &) = delete; + + /** + * @brief Lock the mutex (blocks for as long as it is not available). + */ + auto lock() -> void; + + /** + * @brief Try to lock the mutex (non-blocking). + * + * @return True if lock has been acquired and false otherwise. + */ + auto try_lock() -> bool; + + /** + * @brief Unlock the mutex. + */ + auto unlock() -> void; + + private: + std::atomic<bool> locked = {false}; // Atomic boolean to track if mutex is locked or not. + }; + +} // namespace teachos::arch::shared + +#endif // TEACHOS_ARCH_X86_64_SHARED_MUTEX_HPP diff --git a/arch/x86_64/include/arch/video/vga/io.hpp b/arch/x86_64/include/arch/video/vga/io.hpp index 9226c5c..c399fad 100644 --- a/arch/x86_64/include/arch/video/vga/io.hpp +++ b/arch/x86_64/include/arch/video/vga/io.hpp @@ -7,29 +7,27 @@ 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 @@ -38,4 +36,4 @@ namespace teachos::arch::video::vga } // namespace teachos::arch::video::vga -#endif
\ No newline at end of file +#endif // TEACHOS_ARCH_X86_64_VIDEO_VGA_IO_HPP diff --git a/arch/x86_64/include/arch/video/vga/text.hpp b/arch/x86_64/include/arch/video/vga/text.hpp index 1e584d6..cfbf98f 100644 --- a/arch/x86_64/include/arch/video/vga/text.hpp +++ b/arch/x86_64/include/arch/video/vga/text.hpp @@ -3,22 +3,25 @@ #include <cstdint> #include <string_view> +#include <type_traits> namespace teachos::arch::video::vga::text { + auto constexpr DEFAULT_VGA_TEXT_BUFFER_ADDRESS = 0xB8000; + /** * @brief The colors available in the standard VGA text mode. */ 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. }; /** @@ -26,8 +29,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). }; /** @@ -35,31 +38,31 @@ 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. }; /** * @brief The VGA text mode attribute. * - * In the text mode of VGA, every code point being presented is followed by an attribute description. This allows for - * the modification of how the relevant "cell" is presented. + * @note In the text mode of VGA, every code point being presented is followed by an attribute description. This + * allows for the modification of how the relevant "cell" is presented. * * @see vga::text::foreground_flag * @see vga::text::background_flag */ 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."); /** - * @brief Commonly used VGA text mode attributes + * @brief Commonly used VGA text mode attributes. */ namespace common_attributes { @@ -99,6 +102,11 @@ namespace teachos::arch::video::vga::text auto cursor(bool enabled) -> void; /** + * @brief Move the cursor to a new line, scrolling the buffer if necessary. + */ + auto newline() -> void; + + /** * @brief Write a string of code points to the VGA text buffer. * * @note This function also updates the text mode buffer pointer. @@ -108,6 +116,54 @@ namespace teachos::arch::video::vga::text * @see vga::text::attribute */ auto write(std::string_view code_points, attribute attribute) -> void; + + /** + * @brief Write a single character to the VGA text buffer. + * + * @note This function also updates the text mode buffer pointer. + * + * @param code_point A code point to write to the VGA text mode buffer. + * @param attribute The attribute to apply to the written sequence of code points. + * @see vga::text::attribute + */ + auto write_char(char code_point, attribute attribute) -> void; + + template<typename T> + concept Integral = std::is_integral_v<T>; + + /** + * @brief Write a integral value to the VGA text buffer. + * + * @note This function also updates the text mode buffer pointer. + * + * @param value A integral value to write to the VGA text mode buffer. + * @param attribute The attribute to apply to the written sequence of code points. + * @see vga::text::attribute + */ + template<Integral T> + auto write_number(T value, attribute attribute) -> void + { + T current_value = value; + T divisor = 1; + + while (current_value > 9) + { + divisor *= 10; + current_value = current_value / 10; + } + + current_value = value; + while (divisor > 0) + { + uint8_t quotient = current_value / divisor; + char ascii_digit = quotient + '0'; + + write_char(ascii_digit, attribute); + current_value %= divisor; + divisor /= 10; + } + } + } // namespace teachos::arch::video::vga::text -#endif
\ No newline at end of file +#endif // TEACHOS_ARCH_X86_64_VIDEO_VGA_TEXT_HPP
\ No newline at end of file diff --git a/arch/x86_64/scripts/kernel.ld b/arch/x86_64/scripts/kernel.ld index 943266c..cc07896 100644 --- a/arch/x86_64/scripts/kernel.ld +++ b/arch/x86_64/scripts/kernel.ld @@ -3,7 +3,6 @@ ENTRY(_start) /***************************************************************************** * Virtual and linear start addresses of the TeachOS kernel *****************************************************************************/ -TEACHOS_HIGH = -2048M; TEACHOS_LOW = 1M; PHDRS { @@ -31,44 +30,40 @@ SECTIONS * symbols at the beginning. ***************************************************************************/ _start_linear = .; - _start_virtual = . + TEACHOS_HIGH; + _start_virtual = .; /*************************************************************************** * The bootstrapping infratructure goes first. We first place the read-only * data, followed by our code, initialized mutable data, and finally our * uninitialized mutable data. ***************************************************************************/ - .boot_rodata : + .boot_rodata ALIGN(4K) : AT(ADDR (.boot_rodata)) { KEEP(*(.boot_mbh)) *(.boot_rodata) } :boot_rodata - .boot_text : + .boot_text ALIGN(4K) : AT(ADDR (.boot_text)) { *(.boot_text) } :boot_text - .boot_data : - { - *(.boot_data) - } :boot_data - - .boot_bss : + .boot_bss ALIGN(4K) : AT(ADDR (.boot_bss)) { *(.boot_bss) *(.boot_stack) } + .boot_data ALIGN(4K) : AT(ADDR (.boot_data)) + { + *(.boot_data) + } :boot_data + /*************************************************************************** - * Now it is time to load the 64-bit kernel code. We virtually load it into - * the upper 2GiB, while adjusting the linear load address appropriately. We - * also make sure to align the loaded data onto a page boundary. + * Now it is time to load the 64-bit kernel code. We + * make sure to align the loaded data onto a page boundary. ***************************************************************************/ - . = ALIGN(4K); - . += TEACHOS_HIGH; - - .init ALIGN(4K) : AT(ADDR (.init) - TEACHOS_HIGH) + .init ALIGN(4K) : AT(ADDR (.init)) { /* * Make sure that the crt code is wrapped around the compiler generated @@ -79,7 +74,7 @@ SECTIONS KEEP(*crtn.s.o*(.init)) } :text - .fini ALIGN(4K) : AT(ADDR (.fini) - TEACHOS_HIGH) + .fini ALIGN(4K) : AT(ADDR (.fini)) { /* * Make sure that the crt code is wrapped around the compiler generated @@ -90,18 +85,18 @@ SECTIONS KEEP(*crtn.s.o*(.fini)) } - .text ALIGN(4K) : AT(ADDR (.text) - TEACHOS_HIGH) + .text ALIGN(4K) : AT(ADDR (.text)) { *(.text*) } - .rodata ALIGN(4K) : AT (ADDR (.rodata) - TEACHOS_HIGH) + .rodata ALIGN(4K) : AT (ADDR (.rodata)) { *(.rodata) *(.rodata.*) } :rodata - .ctors ALIGN(4K) : AT (ADDR (.ctors) - TEACHOS_HIGH) + .ctors ALIGN(4K) : AT (ADDR (.ctors)) { KEEP(*crtbegin.o(.ctors)) KEEP(*(EXCLUDE_FILE (*crtend.o) .ctors)) @@ -109,7 +104,7 @@ SECTIONS KEEP(*crtend.o(.ctors)) } :data - .dtors ALIGN(4K) : AT (ADDR (.dtors) - TEACHOS_HIGH) + .dtors ALIGN(4K) : AT (ADDR (.dtors)) { KEEP(*crtbegin.o(.dtors)) KEEP(*(EXCLUDE_FILE (*crtend.o) .dtors)) @@ -117,15 +112,15 @@ SECTIONS KEEP(*crtend.o(.dtors)) } - .data ALIGN(4K) : AT (ADDR (.data) - TEACHOS_HIGH) + .bss ALIGN(4K) : AT (ADDR (.bss)) { - *(.data*) + *(COMMON) + *(.bss*) } - .bss ALIGN(4K) : AT (ADDR (.bss) - TEACHOS_HIGH) + .data ALIGN(4K) : AT (ADDR (.data)) { - *(COMMON) - *(.bss*) + *(.data*) } /*************************************************************************** @@ -133,7 +128,7 @@ SECTIONS * symbols to mark the end of our loaded image. ***************************************************************************/ _end_virtual = ADDR(.bss) + SIZEOF(.bss); - _end_linear = _end_virtual - TEACHOS_HIGH; + _end_linear = _end_virtual; /DISCARD/ : { *(.comment) } } diff --git a/arch/x86_64/src/boot/boot.s b/arch/x86_64/src/boot/boot.s index 7b4e193..8d27ea1 100644 --- a/arch/x86_64/src/boot/boot.s +++ b/arch/x86_64/src/boot/boot.s @@ -7,38 +7,38 @@ * Uninitialized data for the bootstrapping process. */ .section .boot_bss, "aw", @nobits + +/** + * Reserve some space for the Multiboot 2 information pointer. + */ +.global multiboot_information_pointer +multiboot_information_pointer: .skip 4 + +/** + * Align page maps to 4 KiB or the assembler code, will cause crashes when attempting to enable paging. + */ .align 4096 /** - * Reserve space for the page maps we are going to used during startup. + * Reserve space for the page maps we are going to use during startup. * * Note: We are going to use large pages to make the initial mapping code * simpler. * * We need: * - A single PML 4 (since we will only use 4-level paging) - * - 2 PML 3s (since we need to map high (-2GiB) and low (1+MiB) memory) - * - 2 PML 2s (since we need to map high (-2GiB) and low (1+MiB) memory) + * - 1 PML 3 + * - 1 PML 2 */ .global page_map_level_4 page_map_level_4: .skip 512 * 8 -.global page_map_level_3_low -page_map_level_3_low: .skip 512 * 8 -.global page_map_level_3_high -page_map_level_3_high: .skip 512 * 8 - -.global page_map_level_2_low -page_map_level_2_low: .skip 512 * 8 -.global page_map_level_2_high -page_map_level_2_high: .skip 512 * 8 +.global page_map_level_3 +page_map_level_3: .skip 512 * 8 -/** - * Reserve some space for the Multiboot 2 information pointer. - */ -.global multiboot_information_pointer -multiboot_information_pointer: .skip 4 +.global page_map_level_2 +page_map_level_2: .skip 512 * 8 /** * Stack space for the bootstrapping process. @@ -86,6 +86,7 @@ global_descriptor_table_pointer: * We are going to print some messages in case we panic during boot, so we are * going to store them here as well */ +.global message_prefix_panic message_prefix_panic: .string "TeachOS Panic: " message_not_loaded_by_multiboot2: @@ -113,6 +114,12 @@ vga_buffer_pointer: .long 0xb8000 .align 16 .code32 +.global halt +halt: +1: + hlt + jmp 1b + /** * Print a given panic message and then halt the machine. * @@ -133,7 +140,7 @@ _panic: call _print add $8, %esp - hlt + call halt /** * Print a message via the VGA buffer. @@ -193,7 +200,7 @@ _start: lgdt (global_descriptor_table_pointer) jmp $global_descriptor_table_code,$_transition_to_long_mode - hlt + call halt /** * Assert that the CPU supports going into long mode. @@ -306,31 +313,23 @@ enable_sse: * * We map all physical memory we were loaded in plus one additional page. The * mapping is done in terms of huge pages (2 MiB per page) to save on required - * page map entries. Note that we also map memory both in the low and high - * virtual address ranges, giving us two ways of accessing it. We need to do - * this, because the bootstrapping code lives in low memory, while the rest of - * the kernel will reside on the high end. + * page map entries. */ prepare_page_maps: - /* Add an entry to the PML4, pointing to the low PML3 */ - mov $page_map_level_3_low, %eax - or $0x3, %eax - mov %eax, (page_map_level_4 + ((0x0000000000100000 >> 39) & 0x1ff) * 8) - - /* Add an entry to the PML4, pointing to the high PML3 */ - mov $page_map_level_3_high, %eax - or $0x3, %eax - mov %eax, (page_map_level_4 + ((0xffffffff80100000 >> 39) & 0x1ff) * 8) + /* Map the P4 table recursively */ + mov $page_map_level_4, %eax + or $0b11, %eax /* Write present + writable flags into eax register */ + mov %eax, (page_map_level_4 + 511 * 8) - /* Add an entry to the low PML3, pointing to the low PML2 */ - mov $page_map_level_2_low, %eax + /* Add an entry to the PML4, pointing to the PML3 */ + mov $page_map_level_3, %eax or $0x3, %eax - mov %eax, (page_map_level_3_low + ((0x0000000000100000 >> 30) & 0x1ff) * 8) + mov %eax, (page_map_level_4 + ((0x0000000000100000 >> 39) & 0x1ff) * 8) - /* Add an entry to the high PML3, pointing to the high PML2 */ - mov $page_map_level_2_high, %eax + /* Add an entry to the PML3, pointing to the PML2 */ + mov $page_map_level_2, %eax or $0x3, %eax - mov %eax, (page_map_level_3_high + ((0xffffffff80100000 >> 30) & 0x1ff) * 8) + mov %eax, (page_map_level_3 + ((0x0000000000100000 >> 30) & 0x1ff) * 8) xor %ecx, %ecx @@ -342,8 +341,7 @@ prepare_page_maps: mov $(1 << 21), %eax mul %ecx or $((1 << 0) | (1 << 1) | (1 << 7)), %eax - mov %eax, page_map_level_2_low(,%ecx,8) - mov %eax, page_map_level_2_high(,%ecx,8) + mov %eax, page_map_level_2(,%ecx,8) inc %ecx cmp %esi, %ecx @@ -367,4 +365,4 @@ _transition_to_long_mode: call _init call kernel_main - hlt + call halt diff --git a/arch/x86_64/src/exception_handling/abort.cpp b/arch/x86_64/src/exception_handling/abort.cpp new file mode 100644 index 0000000..e12e4cb --- /dev/null +++ b/arch/x86_64/src/exception_handling/abort.cpp @@ -0,0 +1,15 @@ +#include "arch/exception_handling/panic.hpp" + +#include <cstdlib> + +namespace teachos::arch::exception_handling +{ + /** + * @brief Override for the newlib abort function. + * + * @note newlib defines @p ::abort as a weak symbol, thus allowing implementations to override it by simply providing + * a matching implementation. Since the default implemenatation calls a number of functions the kernel does not + * currently implement, @p ::abort gets overridden to simply panic. + */ + extern "C" auto abort() -> void { panic("Terminate was called, possibly due to an unhandled exception"); } +} // namespace teachos::arch::exception_handling diff --git a/arch/x86_64/src/exception_handling/assert.cpp b/arch/x86_64/src/exception_handling/assert.cpp new file mode 100644 index 0000000..b2963de --- /dev/null +++ b/arch/x86_64/src/exception_handling/assert.cpp @@ -0,0 +1,15 @@ +#include "arch/exception_handling/assert.hpp" + +#include "arch/exception_handling/panic.hpp" + +namespace teachos::arch::exception_handling +{ + auto assert(bool condition, char const * message) -> void + { + if (condition) + { + return; + } + panic("Assertion Violation: ", message); + } +} // namespace teachos::arch::exception_handling diff --git a/arch/x86_64/src/exception_handling/panic.cpp b/arch/x86_64/src/exception_handling/panic.cpp new file mode 100644 index 0000000..8e3802a --- /dev/null +++ b/arch/x86_64/src/exception_handling/panic.cpp @@ -0,0 +1,22 @@ +#include "arch/exception_handling/panic.hpp" + +#include "arch/kernel/halt.hpp" +#include "arch/video/vga/text.hpp" + +namespace teachos::arch::exception_handling +{ + extern "C" char const message_prefix_panic[]; + + auto panic(char const * reason) -> void { panic(message_prefix_panic, reason); } + + auto panic(char const * prefix, char const * reason) -> void + { + using video::vga::text::common_attributes::white_on_red; + + video::vga::text::newline(); + video::vga::text::write(prefix, white_on_red); + video::vga::text::write(reason, white_on_red); + + kernel::halt(); + }; +} // namespace teachos::arch::exception_handling diff --git a/arch/x86_64/src/exception_handling/pure_virtual.cpp b/arch/x86_64/src/exception_handling/pure_virtual.cpp new file mode 100644 index 0000000..67772f7 --- /dev/null +++ b/arch/x86_64/src/exception_handling/pure_virtual.cpp @@ -0,0 +1,6 @@ +#include "arch/exception_handling/panic.hpp" + +extern "C" auto __cxa_pure_virtual() -> void +{ + teachos::arch::exception_handling::panic("Runtime", "Tried to call a pure virtual function!"); +} diff --git a/arch/x86_64/src/kernel/main.cpp b/arch/x86_64/src/kernel/main.cpp index 0e90264..681f960 100644 --- a/arch/x86_64/src/kernel/main.cpp +++ b/arch/x86_64/src/kernel/main.cpp @@ -1,15 +1,71 @@ #include "arch/kernel/main.hpp" +#include "arch/memory/heap/bump_allocator.hpp" +#include "arch/memory/heap/concept.hpp" +#include "arch/memory/heap/linked_list_allocator.hpp" +#include "arch/memory/main.hpp" +#include "arch/memory/multiboot/reader.hpp" #include "arch/video/vga/text.hpp" namespace teachos::arch::kernel { + auto stack_overflow_test(int count) -> int + { + int test[5000] = {}; + if (test[0] == 0xFFFF) + { + return count; + } + count = stack_overflow_test(count); + return count++; + } + + auto heap_test() -> void + { + memory::heap::linked_list_allocator heap_allocator{memory::heap::HEAP_START, + memory::heap::HEAP_START + memory::heap::HEAP_SIZE}; + auto test = heap_allocator.allocate(1024); + auto test2 = new (test) memory::multiboot::memory_information{}; + auto test3 = new (static_cast<void *>(static_cast<memory::multiboot::memory_information *>(test) + 1)) + memory::multiboot::memory_information{}; + auto test4 = *test2; + auto test5 = *test3; + test4.kernel_end = 5000; + test5.kernel_end = 3000; + auto test6 = test4.kernel_end; + auto test7 = test5.kernel_end; + auto test8 = memory::multiboot::read_multiboot2(); + if (test6 && test7 && test8.kernel_end) + { + video::vga::text::write("Heap test successful", video::vga::text::common_attributes::green_on_black); + } + test2->kernel_end = 2000; + test2->kernel_start = 1000; + test2->multiboot_start = 2000; + heap_allocator.deallocate(test, 1024); + + auto test9 = heap_allocator.allocate(1024); + auto test10 = heap_allocator.allocate(1024); + auto test11 = heap_allocator.allocate(1024); + heap_allocator.deallocate(test9, 1024); + auto test12 = heap_allocator.allocate(1024); + auto test13 = heap_allocator.allocate(1024); + heap_allocator.deallocate(test11, 1024); + heap_allocator.deallocate(test10, 1024); + heap_allocator.deallocate(test13, 1024); + heap_allocator.deallocate(test12, 1024); + } + auto main() -> void { - using namespace video::vga; + video::vga::text::clear(); + video::vga::text::cursor(false); + video::vga::text::write("TeachOS is starting up...", video::vga::text::common_attributes::green_on_black); + video::vga::text::newline(); + + memory::initialize_memory_management(); - text::clear(); - text::cursor(false); - text::write("TeachOS is starting up...", text::common_attributes::green_on_black); + // stack_overflow_test(0); + heap_test(); } } // namespace teachos::arch::kernel diff --git a/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp b/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp new file mode 100644 index 0000000..cb4fefa --- /dev/null +++ b/arch/x86_64/src/memory/allocator/area_frame_allocator.cpp @@ -0,0 +1,85 @@ +#include "arch/memory/allocator/area_frame_allocator.hpp" + +#include "arch/exception_handling/assert.hpp" + +#include <algorithm> +#include <array> +#include <ranges> + +namespace teachos::arch::memory::allocator +{ + area_frame_allocator::area_frame_allocator(multiboot::memory_information const & mem_info) + : next_free_frame(0U) + , 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)) + { + choose_next_area(); + } + + auto area_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 area_frame_allocator::allocate_frame() -> std::optional<physical_frame> + { + // Only try to allocate memory if current_area is not null, because + // the current_area is null if there is no more available memory. + if (!current_area.has_value()) + { + return std::nullopt; + } + + auto const address = current_area.value().base_address + current_area.value().area_length - 1; + physical_frame current_area_last_frame = physical_frame::containing_address(address); + + if (next_free_frame > current_area_last_frame) + { + // All frames of current area are used, switch to next area. + choose_next_area(); + } + else 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; + return next_free_frame; + } + + // `physical_frame` was not valid, try it again with the updated `next_free_frame`. + return allocate_frame(); + } + + auto area_frame_allocator::deallocate_frame(physical_frame const & physical_frame) -> void { (void)physical_frame; } +} // namespace teachos::arch::memory::allocator diff --git a/arch/x86_64/src/memory/allocator/physical_frame.cpp b/arch/x86_64/src/memory/allocator/physical_frame.cpp new file mode 100644 index 0000000..ec387a1 --- /dev/null +++ b/arch/x86_64/src/memory/allocator/physical_frame.cpp @@ -0,0 +1,24 @@ +#include "arch/memory/allocator/physical_frame.hpp" + +namespace teachos::arch::memory::allocator +{ + auto physical_frame::containing_address(physical_address address) -> physical_frame + { + return physical_frame{address / PAGE_FRAME_SIZE}; + } + + auto physical_frame::start_address() const -> physical_address { return frame_number * PAGE_FRAME_SIZE; } + + auto physical_frame::operator++(int) -> physical_frame + { + physical_frame const old_value = *this; + ++frame_number; + return old_value; + } + + auto physical_frame::operator++() -> physical_frame & + { + ++frame_number; + return *this; + } +} // namespace teachos::arch::memory::allocator diff --git a/arch/x86_64/src/memory/allocator/tiny_frame_allocator.cpp b/arch/x86_64/src/memory/allocator/tiny_frame_allocator.cpp new file mode 100644 index 0000000..3cdf9c7 --- /dev/null +++ b/arch/x86_64/src/memory/allocator/tiny_frame_allocator.cpp @@ -0,0 +1,34 @@ +#include "arch/memory/allocator/tiny_frame_allocator.hpp" + +#include "arch/exception_handling/panic.hpp" + +namespace teachos::arch::memory::allocator +{ + auto tiny_frame_allocator::allocate_frame() -> std::optional<physical_frame> + { + for (auto & frame_option : frames) + { + if (frame_option.has_value()) + { + auto value = frame_option; + frame_option.reset(); + return value; + } + } + return std::nullopt; + } + + auto tiny_frame_allocator::deallocate_frame(physical_frame const & physical_frame) -> void + { + for (auto & frame_option : frames) + { + if (!frame_option.has_value()) + { + frame_option.emplace(physical_frame); + return; + } + } + exception_handling::panic( + "[Tiny Frame Allocator] Attempted to deallocate more than the 3 frames, that can be held"); + } +} // namespace teachos::arch::memory::allocator diff --git a/arch/x86_64/src/memory/cpu/control_register.cpp b/arch/x86_64/src/memory/cpu/control_register.cpp new file mode 100644 index 0000000..298874f --- /dev/null +++ b/arch/x86_64/src/memory/cpu/control_register.cpp @@ -0,0 +1,74 @@ +#include "arch/memory/cpu/control_register.hpp" + +#include "arch/exception_handling/assert.hpp" + +#include <type_traits> + +namespace teachos::arch::memory::cpu +{ + auto read_control_register(control_register cr) -> uint64_t + { + uint64_t current_value; + switch (cr) + { + case control_register::CR0: + asm volatile("mov %%cr0, %[output]" : [output] "=r"(current_value)); + break; + case control_register::CR2: + asm volatile("mov %%cr2, %[output]" : [output] "=r"(current_value)); + break; + case control_register::CR3: + asm volatile("mov %%cr3, %[output]" : [output] "=r"(current_value)); + break; + case control_register::CR4: + asm volatile("mov %%cr4, %[output]" : [output] "=r"(current_value)); + break; + default: + exception_handling::assert(false, + "[Control Register] Attempted to read non-existent or reserved control register"); + break; + } + return current_value; + } + + auto write_control_register(control_register cr, uint64_t new_value) -> void + { + switch (cr) + { + case control_register::CR0: + asm volatile("mov %[input], %%cr0" + : /* no output from call */ + : [input] "r"(new_value) + : "memory"); + break; + case control_register::CR2: + asm volatile("mov %[input], %%cr2" + : /* no output from call */ + : [input] "r"(new_value) + : "memory"); + break; + case control_register::CR3: + asm volatile("mov %[input], %%cr3" + : /* no output from call */ + : [input] "r"(new_value) + : "memory"); + break; + case control_register::CR4: + asm volatile("mov %[input], %%cr4" + : /* no output from call */ + : [input] "r"(new_value) + : "memory"); + break; + default: + exception_handling::assert(false, + "[Control Register] Attempted to write non-existent or reserved control register"); + break; + } + } + + auto set_cr0_bit(cr0_flags flag) -> void + { + auto const cr0 = read_control_register(control_register::CR0); + write_control_register(control_register::CR0, static_cast<std::underlying_type<cr0_flags>::type>(flag) | cr0); + } +} // namespace teachos::arch::memory::cpu diff --git a/arch/x86_64/src/memory/cpu/msr.cpp b/arch/x86_64/src/memory/cpu/msr.cpp new file mode 100644 index 0000000..b83f902 --- /dev/null +++ b/arch/x86_64/src/memory/cpu/msr.cpp @@ -0,0 +1,31 @@ +#include "arch/memory/cpu/msr.hpp" + +namespace teachos::arch::memory::cpu +{ + namespace + { + auto constexpr IA32_EFER_ADDRESS = 0xC0000080; + } + + auto read_msr(uint32_t msr) -> uint64_t + { + uint32_t low, high; + asm volatile("rdmsr" : "=a"(low), "=d"(high) : "c"(msr)); + return (static_cast<uint64_t>(high) << 32) | low; + } + + auto write_msr(uint32_t msr, uint64_t value) -> void + { + uint32_t low = value & 0xFFFFFFFF; + uint32_t high = value >> 32; + asm volatile("wrmsr" + : /* no output from call */ + : "c"(msr), "a"(low), "d"(high)); + } + + auto set_efer_bit(efer_flags flag) -> void + { + auto const efer = read_msr(IA32_EFER_ADDRESS); + write_msr(IA32_EFER_ADDRESS, static_cast<std::underlying_type<efer_flags>::type>(flag) | efer); + } +} // namespace teachos::arch::memory::cpu diff --git a/arch/x86_64/src/memory/cpu/tlb.cpp b/arch/x86_64/src/memory/cpu/tlb.cpp new file mode 100644 index 0000000..591d9fc --- /dev/null +++ b/arch/x86_64/src/memory/cpu/tlb.cpp @@ -0,0 +1,16 @@ +#include "arch/memory/cpu/tlb.hpp" + +#include "arch/memory/cpu/control_register.hpp" + +namespace teachos::arch::memory::cpu +{ + auto tlb_flush(paging::virtual_address address) -> void + { + asm volatile("invlpg (%[input])" : /* no output from call */ : [input] "r"(address) : "memory"); + } + + auto tlb_flush_all() -> void + { + write_control_register(cpu::control_register::CR3, read_control_register(cpu::control_register::CR3)); + } +} // namespace teachos::arch::memory::cpu diff --git a/arch/x86_64/src/memory/heap/bump_allocator.cpp b/arch/x86_64/src/memory/heap/bump_allocator.cpp new file mode 100644 index 0000000..bbf2021 --- /dev/null +++ b/arch/x86_64/src/memory/heap/bump_allocator.cpp @@ -0,0 +1,52 @@ +#include "arch/memory/heap/bump_allocator.hpp" + +#include "arch/exception_handling/assert.hpp" + +#include <limits> +#include <type_traits> + +namespace teachos::arch::memory::heap +{ + namespace + { + template<typename T> + auto saturating_add(T x, T y) -> T + requires std::is_unsigned_v<T> + { + if (x > std::numeric_limits<T>::max() - y) + { + return std::numeric_limits<T>::max(); + } + T result = x + y; + return result; + } + } // namespace + + auto bump_allocator::allocate(std::size_t size) -> void * + { + // Repeat allocation until it succeeds, has to be done, because another allocator could overtake it at any time + // causing the value to differ and the calculation to have to be redone. + for (;;) + { + auto alloc_start = next.load(std::memory_order::relaxed); + auto const alloc_end = saturating_add(alloc_start, size); + arch::exception_handling::assert(alloc_end <= heap_end, "[Heap Allocator] Out of memory"); + // Check if the atomic value is still the one initally loaded, if it isn't we have been overtaken by another + // thread and need to redo the calculation. Spurious failure by weak can be ignored, because the whole allocation + // is wrapped in an infinite for loop so a failure that wasn't actually one will simply be retried until it works. + auto const updated = next.compare_exchange_weak(alloc_start, alloc_end, std::memory_order::relaxed); + if (updated) + { + return reinterpret_cast<void *>(alloc_start); + } + } + } + + auto bump_allocator::deallocate(void * pointer, std::size_t size) -> void + { + if (pointer || size) + { + } + } + +} // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp new file mode 100644 index 0000000..e5bae21 --- /dev/null +++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp @@ -0,0 +1,168 @@ +#include "arch/memory/heap/linked_list_allocator.hpp" + +#include "arch/exception_handling/assert.hpp" +#include "arch/exception_handling/panic.hpp" + +namespace teachos::arch::memory::heap +{ + linked_list_allocator::linked_list_allocator(std::size_t heap_start, std::size_t heap_end) + : heap_start(heap_start) + , heap_end(heap_end) + , first(nullptr) + , mutex{shared::mutex{}} + { + auto const heap_size = heap_end - heap_start; + exception_handling::assert( + heap_size > min_allocatable_size(), + "[Linked List Allocator] Total heap size can not be smaller than minimum of 16 bytes to hold " + "atleast one memory hole entry"); + first = new (reinterpret_cast<void *>(heap_start)) memory_block(heap_size, nullptr); + } + + auto linked_list_allocator::allocate(std::size_t size) -> void * + { + exception_handling::assert(size > min_allocatable_size(), + "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes"); + mutex.lock(); + + memory_block * previous = nullptr; + auto current = first; + + while (current != nullptr) + { + if (current->size == size) + { + auto const memory_address = remove_free_memory_block(previous, current); + mutex.unlock(); + return memory_address; + } + else if (current->size >= size + min_allocatable_size()) + { + auto const memory_address = split_free_memory_block(previous, current, size); + mutex.unlock(); + return memory_address; + } + + previous = current; + current = current->next; + } + + exception_handling::panic("[Linked List Allocator] Out of memory"); + } + + auto linked_list_allocator::deallocate(void * pointer, std::size_t size) -> void + { + exception_handling::assert(size > min_allocatable_size(), + "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes"); + mutex.lock(); + + auto const start_address = reinterpret_cast<std::size_t>(pointer); + auto const end_address = start_address + size; + + memory_block * previous = nullptr; + auto current = first; + + while (current != nullptr) + { + // Current address of the free memory block now points to an address that is after our block to deallocate in heap + // memory space. + if (reinterpret_cast<std::size_t>(current) >= end_address) + { + break; + } + + previous = current; + current = current->next; + } + + coalesce_free_memory_block(previous, current, pointer, size); + mutex.unlock(); + } + + auto linked_list_allocator::remove_free_memory_block(memory_block * previous_block, + memory_block * current_block) -> void * + { + return replace_free_memory_block(previous_block, current_block, current_block->next); + } + + auto linked_list_allocator::split_free_memory_block(memory_block * previous_block, memory_block * current_block, + std::size_t size) -> void * + { + auto const end_address = reinterpret_cast<std::size_t>(current_block) + size; + auto const new_block = + new (reinterpret_cast<void *>(end_address)) memory_block(current_block->size - size, current_block->next); + return replace_free_memory_block(previous_block, current_block, new_block); + } + + auto linked_list_allocator::replace_free_memory_block(memory_block * previous_block, memory_block * current_block, + memory_block * new_block) -> void * + { + auto const start_address = reinterpret_cast<std::size_t>(current_block); + // If we want to allocate into the first block that is before any other free block, then there exists no previous + // free block (nullptr). Therefore we have to overwrite the first block instead of overwriting its next value. + if (previous_block == nullptr) + { + first = new_block; + } + else + { + previous_block->next = new_block; + } + current_block->~memory_block(); + return reinterpret_cast<void *>(start_address); + } + + auto linked_list_allocator::coalesce_free_memory_block(memory_block * previous_block, memory_block * current_block, + void * pointer, std::size_t size) -> void + { + auto const start_address = reinterpret_cast<std::size_t>(pointer); + auto const end_address = start_address + size; + + // Inital values if there are no adjacent blocks either before or after, meaning we have to simply create a free + // memory block that is placed in between the previous and next block. + auto block_size = size; + auto next_block = current_block; + + // If the block we want to deallocate is before another free block and we can therefore combine both into one. + // This is done by deleting the current free block and creating a new block at the start address of the block to + // deallocate with both the size of the block to deallcoate and the free block next to it. + if (end_address == reinterpret_cast<std::size_t>(current_block)) + { + block_size += current_block->size; + next_block = current_block->next; + current_block->~memory_block(); + } + + // If the block we want to deallocate is behind another free block and we can therefore combine both into one. + // This is done by simply changin the size of the previous block to include the size of the block to deallocate. + // This is done, because the previous block might still be referencered by the next field of other memory blocks. + if (previous_block != nullptr && + start_address == (reinterpret_cast<std::size_t>(previous_block) + previous_block->size)) + { + block_size += previous_block->size; + + previous_block->size = block_size; + previous_block->next = next_block; + return; + } + + // Check if the block we want to deallocate is contained in the previous block, because if it is it can only mean + // that the block has already been deallocated and we therefore attempted a double free. + exception_handling::assert(previous_block == nullptr || + start_address >= + (reinterpret_cast<std::size_t>(previous_block) + previous_block->size), + "[Linked List Allocator] Attempted double free detected"); + + auto const new_block = new (pointer) memory_block(block_size, next_block); + // If we want to deallocate the first block that is before any other free block, then there exists no previous free + // block (nullptr). Therefore we have to overwrite the first block instead of overwriting its + // next value. + if (previous_block == nullptr) + { + first = new_block; + return; + } + previous_block->next = new_block; + } + +} // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/src/memory/heap/memory_block.cpp b/arch/x86_64/src/memory/heap/memory_block.cpp new file mode 100644 index 0000000..446cd96 --- /dev/null +++ b/arch/x86_64/src/memory/heap/memory_block.cpp @@ -0,0 +1,15 @@ +#include "arch/memory/heap/memory_block.hpp" + +#include <string.h> + +namespace teachos::arch::memory::heap +{ + memory_block::memory_block(std::size_t size, memory_block * next) + { + memset(static_cast<void *>(this), 0, size); + this->size = size; + this->next = next; + } + + memory_block::~memory_block() { memset(static_cast<void *>(this), 0, sizeof(memory_block)); } +} // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/src/memory/main.cpp b/arch/x86_64/src/memory/main.cpp new file mode 100644 index 0000000..b978319 --- /dev/null +++ b/arch/x86_64/src/memory/main.cpp @@ -0,0 +1,53 @@ +#include "arch/memory/main.hpp" + +#include "arch/exception_handling/assert.hpp" +#include "arch/memory/allocator/area_frame_allocator.hpp" +#include "arch/memory/cpu/control_register.hpp" +#include "arch/memory/cpu/msr.hpp" +#include "arch/memory/heap/concept.hpp" +#include "arch/memory/paging/active_page_table.hpp" +#include "arch/memory/paging/kernel_mapper.hpp" + +namespace teachos::arch::memory +{ + namespace + { + auto remap_heap(allocator::area_frame_allocator 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 = + ++(paging::virtual_page::containing_address(memory::heap::HEAP_START + memory::heap::HEAP_SIZE - 1)); + paging::page_container::iterator const begin{start_page}; + paging::page_container::iterator const end{end_page}; + paging::page_container const pages{begin, end}; + + for (auto const & page : pages) + { + active_table.map_page_to_next_free_frame(allocator, page, paging::entry::WRITABLE); + } + } + } // namespace + + auto initialize_memory_management() -> void + { + static bool has_been_called = false; + arch::exception_handling::assert(!has_been_called, + "[Initialization] Memory management has already been initialized"); + has_been_called = true; + + auto const memory_information = multiboot::read_multiboot2(); + allocator::area_frame_allocator allocator(memory_information); + + cpu::set_cr0_bit(memory::cpu::cr0_flags::WRITE_PROTECT); + cpu::set_efer_bit(memory::cpu::efer_flags::NXE); + + paging::kernel_mapper kernel(allocator, memory_information); + auto & active_table = kernel.remap_kernel(); + video::vga::text::write("Kernel remapping successful", video::vga::text::common_attributes::green_on_black); + video::vga::text::newline(); + + remap_heap(allocator, active_table); + video::vga::text::write("Heap remapping successful", video::vga::text::common_attributes::green_on_black); + video::vga::text::newline(); + } +} // namespace teachos::arch::memory diff --git a/arch/x86_64/src/memory/multiboot/elf_symbols_section.cpp b/arch/x86_64/src/memory/multiboot/elf_symbols_section.cpp new file mode 100644 index 0000000..f5d126b --- /dev/null +++ b/arch/x86_64/src/memory/multiboot/elf_symbols_section.cpp @@ -0,0 +1,13 @@ +#include "arch/memory/multiboot/elf_symbols_section.hpp" + +namespace teachos::arch::memory::multiboot +{ + auto elf_section_flags::contains_flags(std::bitset<64U> other) const -> bool { return (flags & other) == other; } + + auto elf_section_header::is_null() const -> bool + { + return name_table_index == 0U && type == elf_section_type::INACTIVE && flags == elf_section_flags(0U) && + physical_address == 0U && file_offset == 0U && additional_information == 0U && address_alignment == 0U && + fixed_table_entry_size == 0U; + } +} // namespace teachos::arch::memory::multiboot diff --git a/arch/x86_64/src/memory/multiboot/reader.cpp b/arch/x86_64/src/memory/multiboot/reader.cpp new file mode 100644 index 0000000..2bf5b25 --- /dev/null +++ b/arch/x86_64/src/memory/multiboot/reader.cpp @@ -0,0 +1,131 @@ +#include "arch/memory/multiboot/reader.hpp" + +#include "arch/boot/pointers.hpp" +#include "arch/exception_handling/assert.hpp" +#include "arch/memory/multiboot/elf_symbols_section.hpp" +#include "arch/memory/multiboot/info.hpp" + +#include <algorithm> +#include <ranges> + +namespace teachos::arch::memory::multiboot +{ + namespace + { + template<typename T> + requires std::is_pointer<T>::value + auto align_to_8_byte_boundary(T ptr, uint32_t size) -> T + { + return reinterpret_cast<T>(reinterpret_cast<uint8_t *>(ptr) + ((size + 7) & ~7)); + } + + auto process_memory_map(memory_map_header * mminfo) -> memory_area_container + { + auto const expected_entry_size = mminfo->entry_size; + auto constexpr actual_entry_size = sizeof(memory_area); + exception_handling::assert(expected_entry_size == actual_entry_size, + "[Multiboot Reader] Unexpected memory area entry size"); + + auto const total_size = mminfo->info.size; + auto const total_entries_size = total_size - sizeof(memory_map_header) + actual_entry_size; + auto const number_of_entries = total_entries_size / actual_entry_size; + + auto const begin = memory_area_container::iterator{&mminfo->entries}; + auto const end = begin + number_of_entries; + return memory_area_container{begin, end}; + } + + auto process_elf_sections(elf_symbols_section_header * symbol, std::size_t & kernel_start, + std::size_t & kernel_end) -> elf_section_header_container + { + auto const expected_entry_size = symbol->entry_size; + auto constexpr actual_entry_size = sizeof(elf_section_header); + exception_handling::assert(expected_entry_size == actual_entry_size, + "[Multiboot Reader] Unexpected elf section header entry size"); + + auto const expected_total_size = symbol->info.size; + auto const actual_total_entry_size = actual_entry_size * symbol->number_of_sections; + auto constexpr actual_total_section_size = sizeof(elf_symbols_section_header) - sizeof(uint32_t); + auto const actual_total_size = actual_total_entry_size + actual_total_section_size; + exception_handling::assert(expected_total_size == actual_total_size, + "[Multiboot Reader] Unexpected elf symbols section header total size"); + + auto const begin = elf_section_header_container::iterator{reinterpret_cast<elf_section_header *>(&symbol->end)}; + auto const end = begin + symbol->number_of_sections; + exception_handling::assert(begin->is_null(), + "[Multiboot Reader] Elf symbols section not starting with SHT_NULL section"); + + elf_section_header_container sections{begin, end}; + + auto allocated_sections = sections | std::views::filter([](auto const & section) { + return section.flags.contains_flags(elf_section_flags::OCCUPIES_MEMORY); + }); + + auto const elf_section_with_lowest_physical_address = std::ranges::min_element( + allocated_sections, [](auto const & a, auto const & b) { return a.physical_address < b.physical_address; }); + + auto const elf_section_with_highest_physical_address = + std::ranges::max_element(allocated_sections, [](auto const & a, auto const & b) { + auto a_physical_address_end = a.physical_address + a.section_size; + auto b_physical_address_end = b.physical_address + b.section_size; + return a_physical_address_end < b_physical_address_end; + }); + + auto const symbol_table_section_count = std::ranges::count_if(sections, [](auto const & section) { + return section.type == elf_section_type::DYNAMIC_SYMBOL_TABLE || section.type == elf_section_type::SYMBOL_TABLE; + }); + auto const dynamic_section_count = std::ranges::count_if( + sections, [](auto const & section) { return section.type == elf_section_type::DYNAMIC; }); + + exception_handling::assert( + symbol_table_section_count == 1U, + "[Multiboot Reader] ELF Specifications allows only (1) symbol table section, but got more"); + exception_handling::assert( + dynamic_section_count <= 1U, + "[Multiboot Reader] ELF Specifications allows only (1) or less dynamic sections, but got more"); + + auto const lowest_elf_section = *elf_section_with_lowest_physical_address; + kernel_start = lowest_elf_section.physical_address; + + auto const highest_elf_section = *elf_section_with_highest_physical_address; + kernel_end = highest_elf_section.physical_address + highest_elf_section.section_size; + + return sections; + } + } // namespace + + auto read_multiboot2() -> memory_information + { + memory_information mem_info{UINT64_MAX, + 0U, + elf_section_header_container{}, + boot::multiboot_information_pointer, + 0U, + memory_area_container{}}; + + auto const multiboot_information_pointer = reinterpret_cast<info_header *>(boot::multiboot_information_pointer); + auto const multiboot_tag = &multiboot_information_pointer->tags; + mem_info.multiboot_end = mem_info.multiboot_start + multiboot_information_pointer->total_size; + + for (auto tag = multiboot_tag; tag->type != tag_type::END; tag = align_to_8_byte_boundary(tag, tag->size)) + { + switch (tag->type) + { + case tag_type::ELF_SECTIONS: { + auto const symbol = reinterpret_cast<elf_symbols_section_header *>(tag); + mem_info.sections = process_elf_sections(symbol, mem_info.kernel_start, mem_info.kernel_end); + break; + } + case tag_type::MEMORY_MAP: { + auto const mminfo = reinterpret_cast<memory_map_header *>(tag); + mem_info.areas = process_memory_map(mminfo); + break; + } + default: + // All other cases are not important and can be ignored. + break; + } + } + return mem_info; + } +} // namespace teachos::arch::memory::multiboot diff --git a/arch/x86_64/src/memory/paging/active_page_table.cpp b/arch/x86_64/src/memory/paging/active_page_table.cpp new file mode 100644 index 0000000..0113869 --- /dev/null +++ b/arch/x86_64/src/memory/paging/active_page_table.cpp @@ -0,0 +1,98 @@ +#include "arch/memory/paging/active_page_table.hpp" + +namespace teachos::arch::memory::paging +{ + namespace + { + paging::virtual_address constexpr PAGE_TABLE_LEVEL_4_ADDRESS = 0xffffffff'fffff000; + } + + auto active_page_table::create_or_get() -> active_page_table & + { + static page_table_handle active_handle{reinterpret_cast<page_table *>(PAGE_TABLE_LEVEL_4_ADDRESS), + page_table_handle::LEVEL4}; + static active_page_table active_page{active_handle}; + return active_page; + } + + auto active_page_table::operator[](std::size_t index) -> entry & { return active_handle[index]; } + + auto active_page_table::translate_address(virtual_address address) -> std::optional<allocator::physical_address> + { + auto const offset = address % allocator::PAGE_FRAME_SIZE; + auto const page = virtual_page::containing_address(address); + auto const frame = translate_page(page); + + if (frame.has_value()) + { + return frame.value().frame_number * allocator::PAGE_FRAME_SIZE + offset; + } + + return std::nullopt; + } + + auto active_page_table::translate_page(virtual_page page) -> std::optional<allocator::physical_frame> + { + auto current_handle = active_handle; + + for (auto level = page_table_handle::LEVEL4; level != page_table_handle::LEVEL1; --level) + { + auto const next_handle = current_handle.next_table(page.get_level_index(level)); + // If the next table method failed then it is highly likely that it was a huge page and we therefore have to + // parse the table differently. Therefore, we attempt to parse it using the method required by huge pages. + if (!next_handle.has_value()) + { + return translate_huge_page(page); + } + current_handle = next_handle.value(); + } + + auto const level1_index = page.get_level_index(page_table_handle::LEVEL1); + auto const level1_entry = current_handle[level1_index]; + return level1_entry.calculate_pointed_to_frame(); + } + + auto active_page_table::translate_huge_page(virtual_page page) -> std::optional<allocator::physical_frame> + { + auto current_handle = active_handle; + auto level3_handle = current_handle.next_table(page.get_level_index(page_table_handle::LEVEL4)); + + if (!level3_handle.has_value()) + { + return std::nullopt; + } + + auto const level3_entry = level3_handle.value()[page.get_level_index(page_table_handle::LEVEL3)]; + auto const level3_frame = level3_entry.calculate_pointed_to_frame(); + if (level3_frame.has_value() && level3_entry.contains_flags(entry::HUGE_PAGE)) + { + exception_handling::assert( + level3_frame.value().frame_number % (PAGE_TABLE_ENTRY_COUNT * PAGE_TABLE_ENTRY_COUNT) == 0U, + "[Page Mapper] Physical address must be 1 GiB aligned"); + return allocator::physical_frame{level3_frame.value().frame_number + + page.get_level_index(page_table_handle::LEVEL2) * PAGE_TABLE_ENTRY_COUNT + + page.get_level_index(page_table_handle::LEVEL1)}; + } + + auto level2_handle = level3_handle.value().next_table(page.get_level_index(page_table_handle::LEVEL3)); + if (level2_handle.has_value()) + { + auto const level2_entry = level2_handle.value()[page.get_level_index(page_table_handle::LEVEL2)]; + auto const level2_frame = level2_entry.calculate_pointed_to_frame(); + if (level2_frame.has_value() && level2_entry.contains_flags(entry::HUGE_PAGE)) + { + exception_handling::assert(level2_frame.value().frame_number % PAGE_TABLE_ENTRY_COUNT == 0U, + "[Page Mapper] Physical address must be 2 MiB aligned"); + return allocator::physical_frame{level2_frame.value().frame_number + + page.get_level_index(page_table_handle::LEVEL1)}; + } + } + return std::nullopt; + } + + active_page_table::active_page_table(page_table_handle active_handle) + : active_handle(active_handle) + { + // Nothing to do + } +} // namespace teachos::arch::memory::paging diff --git a/arch/x86_64/src/memory/paging/inactive_page_table.cpp b/arch/x86_64/src/memory/paging/inactive_page_table.cpp new file mode 100644 index 0000000..4e0610e --- /dev/null +++ b/arch/x86_64/src/memory/paging/inactive_page_table.cpp @@ -0,0 +1,20 @@ +#include "arch/memory/paging/inactive_page_table.hpp" + +namespace teachos::arch::memory::paging +{ + inactive_page_table::inactive_page_table(allocator::physical_frame frame) + : page_table_level_4_frame{frame} + { + // Nothing to do + } + + inactive_page_table::inactive_page_table(allocator::physical_frame frame, active_page_table & active_page_table, + temporary_page & temporary_page) + : page_table_level_4_frame{frame} + { + auto table = temporary_page.map_table_frame(page_table_level_4_frame, active_page_table); + table.zero_entries(); + table[511].set_entry(page_table_level_4_frame, entry::PRESENT | entry::WRITABLE); + temporary_page.unmap_page(active_page_table); + } +} // namespace teachos::arch::memory::paging diff --git a/arch/x86_64/src/memory/paging/page_entry.cpp b/arch/x86_64/src/memory/paging/page_entry.cpp new file mode 100644 index 0000000..5aa0982 --- /dev/null +++ b/arch/x86_64/src/memory/paging/page_entry.cpp @@ -0,0 +1,58 @@ +#include "arch/memory/paging/page_entry.hpp" + +#include "arch/exception_handling/assert.hpp" + +namespace teachos::arch::memory::paging +{ + namespace + { + std::size_t constexpr PHYSICAL_ADDRESS_MASK = 0x000fffff'fffff000; + } // namespace + + entry::entry(uint64_t flags) + : flags(flags) + { + // Nothing to do. + } + + entry::entry(multiboot::elf_section_flags elf_flags) + { + if (elf_flags.contains_flags(multiboot::elf_section_flags::OCCUPIES_MEMORY)) + { + flags |= entry::PRESENT; + } + if (elf_flags.contains_flags(multiboot::elf_section_flags::WRITABLE)) + { + flags |= entry::WRITABLE; + } + if (!elf_flags.contains_flags(multiboot::elf_section_flags::EXECUTABLE_CODE)) + { + flags |= entry::EXECUTING_CODE_FORBIDDEN; + } + } + + auto entry::is_unused() const -> bool { return flags == 0U; } + + auto entry::set_unused() -> void { flags = 0U; } + + auto entry::calculate_pointed_to_frame() const -> std::optional<allocator::physical_frame> + { + if (contains_flags(PRESENT)) + { + auto const address = flags.to_ulong() & PHYSICAL_ADDRESS_MASK; + return allocator::physical_frame::containing_address(address); + } + return std::nullopt; + } + + auto entry::contains_flags(std::bitset<64U> other) const -> bool { return (flags & other) == other; } + + auto entry::set_entry(allocator::physical_frame frame, std::bitset<64U> additional_flags) -> void + { + exception_handling::assert((frame.start_address() & ~PHYSICAL_ADDRESS_MASK) == 0, + "[Paging Entry] Start address is not aligned with page"); + flags = frame.start_address() | additional_flags.to_ulong(); + } + + auto entry::get_flags() const -> std::bitset<64U> { return flags.to_ulong() & ~PHYSICAL_ADDRESS_MASK; } +} // namespace teachos::arch::memory::paging diff --git a/arch/x86_64/src/memory/paging/page_table.cpp b/arch/x86_64/src/memory/paging/page_table.cpp new file mode 100644 index 0000000..eb11810 --- /dev/null +++ b/arch/x86_64/src/memory/paging/page_table.cpp @@ -0,0 +1,128 @@ +#include "arch/memory/paging/page_table.hpp" + +#include <algorithm> +#include <array> +#include <memory> + +/* + * This is a linker variable reference. This referenc cannot reside inside a namespace, because in + * that case the compiler would try to find arch::memory::paging::_end_of_image inside the ELF file. + */ +extern char _end_of_image; + +namespace teachos::arch::memory::paging +{ + /** + * @brief A Page table containing 512 entries. + */ + struct page_table + { + auto zero_entries() -> void; + + auto is_empty() const -> bool; + + auto next_table(std::size_t table_index) const -> std::optional<page_table *>; + + auto operator[](std::size_t index) -> entry &; + + auto operator[](std::size_t index) const -> entry const &; + + private: + /** + * @brief Calculates the address of the next page table level for the given table index. + * + * @note The next page table address is only valid if the corresponding entry is present and not a huge page. + * Meaning we use an index into a Level 4 page table to get the according Level 3 page table address. + * + * @param table_index Index of this page table in the page table one level higher. + * @return An optional of the address of the next page table or null. + */ + auto next_table_address(std::size_t table_index) const -> std::optional<std::size_t>; + + std::array<entry, PAGE_TABLE_ENTRY_COUNT> entries = + {}; ///< Entries containing addresses to page tables of a level below or + ///< actual virtual addresses for the level 1 page table. + }; + + auto page_table::zero_entries() -> void + { + std::ranges::for_each(entries, [](auto & entry) { entry.set_unused(); }); + } + + auto page_table::is_empty() const -> bool + { + return std::all_of(entries.begin(), entries.end(), [](entry const & entry) { return entry.is_unused(); }); + } + + auto page_table::next_table(std::size_t table_index) const -> std::optional<page_table *> + { + auto const address = next_table_address(table_index); + if (address.has_value()) + { + return reinterpret_cast<page_table *>(address.value()); + } + return std::nullopt; + } + + auto page_table::operator[](std::size_t index) -> entry & + { + exception_handling::assert(index < PAGE_TABLE_ENTRY_COUNT, "[Page Table] Index out of bounds"); + return entries[index]; + } + + auto page_table::operator[](std::size_t index) const -> entry const & + { + exception_handling::assert(index < PAGE_TABLE_ENTRY_COUNT, "[Page Table] Index out of bounds"); + return entries[index]; + } + + auto page_table::next_table_address(std::size_t table_index) const -> std::optional<std::size_t> + { + auto const entry = this->operator[](table_index); + + if (entry.contains_flags(entry::PRESENT) && !entry.contains_flags(entry::HUGE_PAGE)) + { + auto const table_address = reinterpret_cast<std::size_t>(this); + return ((table_address << 9) | (table_index << 12)); + } + return std::nullopt; + } + + page_table_handle::page_table_handle(page_table * table, page_table_handle::level table_level) + : table(table) + , table_level(table_level) + { + exception_handling::assert(table != nullptr, + "[Page Table] Attempted to pass nullptr as table to page table table method"); + } + + auto page_table_handle::zero_entries() -> void { table->zero_entries(); } + + auto page_table_handle::is_empty() const -> bool { return table->is_empty(); } + + auto page_table_handle::next_table(std::size_t table_index) const -> std::optional<page_table_handle> + { + exception_handling::assert(table_level != page_table_handle::LEVEL1, + "[Page Table] Attempted to call next_table on level 1 page table"); + auto const next_table = table->next_table(table_index); + if (next_table.has_value()) + { + auto const new_level = static_cast<page_table_handle::level>(table_level - 1); + return page_table_handle{next_table.value(), new_level}; + } + return std::nullopt; + } + + auto page_table_handle::get_level() const -> page_table_handle::level { return table_level; } + + auto page_table_handle::operator[](std::size_t index) -> entry & { return table->operator[](index); } + + auto operator--(page_table_handle::level & value) -> page_table_handle::level & + { + exception_handling::assert(value != page_table_handle::LEVEL1, + "[Page table] Attempted to decrement enum to value outside of range"); + auto new_value = static_cast<std::underlying_type<page_table_handle::level>::type>(value); + value = static_cast<page_table_handle::level>(--new_value); + return value; + } +} // namespace teachos::arch::memory::paging diff --git a/arch/x86_64/src/memory/paging/temporary_page.cpp b/arch/x86_64/src/memory/paging/temporary_page.cpp new file mode 100644 index 0000000..152241d --- /dev/null +++ b/arch/x86_64/src/memory/paging/temporary_page.cpp @@ -0,0 +1,29 @@ +#include "arch/memory/paging/temporary_page.hpp" + +#include "arch/memory/paging/page_entry.hpp" + +namespace teachos::arch::memory::paging +{ + auto temporary_page::map_table_frame(allocator::physical_frame frame, + active_page_table & active_table) -> page_table_handle + { + page_table_handle handle{reinterpret_cast<page_table *>(map_to_frame(frame, active_table)), + page_table_handle::LEVEL1}; + return handle; + } + + auto temporary_page::map_to_frame(allocator::physical_frame frame, + active_page_table & active_table) -> virtual_address + { + exception_handling::assert(!active_table.translate_page(page).has_value(), + "[Temporary page] Page is already mapped"); + + active_table.map_page_to_frame(allocator, page, frame, entry::WRITABLE); + return page.start_address(); + } + + auto temporary_page::unmap_page(active_page_table & active_table) -> void + { + active_table.unmap_page(allocator, page); + } +} // namespace teachos::arch::memory::paging diff --git a/arch/x86_64/src/memory/paging/virtual_page.cpp b/arch/x86_64/src/memory/paging/virtual_page.cpp new file mode 100644 index 0000000..d374156 --- /dev/null +++ b/arch/x86_64/src/memory/paging/virtual_page.cpp @@ -0,0 +1,33 @@ +#include "arch/memory/paging/virtual_page.hpp" + +#include "arch/exception_handling/assert.hpp" + +namespace teachos::arch::memory::paging +{ + auto virtual_page::containing_address(virtual_address address) -> virtual_page + { + exception_handling::assert(address < 0x00008000'00000000 || address >= 0xffff8000'00000000, + "[Virtual Page] Attempted to create virtual page from invalid address"); + return virtual_page{address / allocator::PAGE_FRAME_SIZE}; + } + + auto virtual_page::start_address() const -> virtual_address { return page_number * allocator::PAGE_FRAME_SIZE; } + + auto virtual_page::get_level_index(page_table_handle::level level) const -> size_t + { + return (page_number >> (level * 9U)) & 0x1FF; + } + + auto virtual_page::operator++(int) -> virtual_page + { + virtual_page const old_value = *this; + ++page_number; + return old_value; + } + + auto virtual_page::operator++() -> virtual_page & + { + ++page_number; + return *this; + } +} // namespace teachos::arch::memory::paging diff --git a/arch/x86_64/src/shared/mutex.cpp b/arch/x86_64/src/shared/mutex.cpp new file mode 100644 index 0000000..6598255 --- /dev/null +++ b/arch/x86_64/src/shared/mutex.cpp @@ -0,0 +1,16 @@ +#include "arch/shared/mutex.hpp" + +namespace teachos::arch::shared +{ + auto mutex::lock() -> void + { + while (!try_lock()) + { + // Nothing to do + } + } + + auto mutex::try_lock() -> bool { return !locked.exchange(true, std::memory_order_acquire); } + + auto mutex::unlock() -> void { locked.store(false, std::memory_order_release); } +} // namespace teachos::arch::shared diff --git a/arch/x86_64/src/video/vga/text.cpp b/arch/x86_64/src/video/vga/text.cpp index f1e7412..0137ddb 100644 --- a/arch/x86_64/src/video/vga/text.cpp +++ b/arch/x86_64/src/video/vga/text.cpp @@ -1,6 +1,5 @@ #include "arch/video/vga/text.hpp" -#include "arch/boot/pointers.hpp" #include "arch/video/vga/io.hpp" #include "memory/asm_pointer.hpp" @@ -10,24 +9,18 @@ namespace teachos::arch::video::vga::text { - namespace { - auto constexpr default_text_buffer_address = 0xb8000; + auto constexpr DEFAULT_TEXT_BUFFER_WIDTH = 80U; + auto constexpr DEFAULT_TEXT_BUFFER_HEIGHT = 25U; extern "C" std::pair<char, attribute> * vga_buffer_pointer; auto constinit text_buffer = teachos::memory::asm_pointer{vga_buffer_pointer}; - - auto write(char code_point, attribute attribute) -> void - { - auto & p = *text_buffer; - (*p++) = std::pair{code_point, attribute}; - }; } // namespace auto clear(attribute attribute) -> void { - *text_buffer = reinterpret_cast<decltype(text_buffer)::pointer>(default_text_buffer_address); + *text_buffer = reinterpret_cast<decltype(text_buffer)::pointer>(DEFAULT_VGA_TEXT_BUFFER_ADDRESS); std::ranges::fill_n(*text_buffer, 2000, std::pair{' ', attribute}); } @@ -39,9 +32,34 @@ namespace teachos::arch::video::vga::text crtc::data_port::write(vga::crtc::data_port::read() | cursor_disable_byte); } - auto write(std::string_view code_points, attribute attribute) -> void + auto newline() -> void { - std::ranges::for_each(code_points, [&](auto code_point) { write(code_point, attribute); }); + auto base = reinterpret_cast<decltype(text_buffer)::pointer>(DEFAULT_VGA_TEXT_BUFFER_ADDRESS); + auto & raw_buffer = *text_buffer; + auto current_line = (raw_buffer - base) / DEFAULT_TEXT_BUFFER_WIDTH; + auto next_line = current_line + 1; + + if (next_line >= DEFAULT_TEXT_BUFFER_HEIGHT) + { + auto begin = base + DEFAULT_TEXT_BUFFER_WIDTH; + auto end = base + DEFAULT_TEXT_BUFFER_WIDTH * DEFAULT_TEXT_BUFFER_HEIGHT; + std::ranges::move(begin, end, base); + raw_buffer = base + current_line * DEFAULT_TEXT_BUFFER_WIDTH; + } + else + { + raw_buffer = base + next_line * DEFAULT_TEXT_BUFFER_WIDTH; + } } + auto write_char(char code_point, attribute attribute) -> void + { + auto & p = *text_buffer; + (*p++) = std::pair{code_point, attribute}; + }; + + auto write(std::string_view code_points, attribute attribute) -> void + { + std::ranges::for_each(code_points, [&](auto code_point) { write_char(code_point, attribute); }); + } } // namespace teachos::arch::video::vga::text |