diff options
| author | Felix Morgner <felix.morgner@ost.ch> | 2026-03-30 11:20:08 +0200 |
|---|---|---|
| committer | Felix Morgner <felix.morgner@ost.ch> | 2026-03-30 11:20:08 +0200 |
| commit | 706f529722520429860ce60237d4ef71b2b27601 (patch) | |
| tree | a5a4e89ae3ed25b0af521249134e524a0142814f | |
| parent | 2864e0b061f923a3c73c608b9c27ca4a7116e27c (diff) | |
| parent | 3070bb45b9741165d786b2c5a018ee55c1a82db8 (diff) | |
| download | kernel-706f529722520429860ce60237d4ef71b2b27601.tar.xz kernel-706f529722520429860ce60237d4ef71b2b27601.zip | |
Merge branch 'fmorgner/interrupt-handling' into develop-BA-FS26
45 files changed, 1450 insertions, 891 deletions
diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml index 2231956..0b933c4 100644 --- a/.gitlab-ci.yml +++ b/.gitlab-ci.yml @@ -6,10 +6,7 @@ build: stage: build - image: registry.gitlab.ost.ch:45023/teachos/devcontainers/x86-64:15.2.0-4 - before_script: - - apt update - - apt install -y clang-tidy cmake grub2-common grub-pc mtools ninja-build xorriso + image: registry.gitlab.ost.ch:45023/teachos/devcontainers/x86-64.ci:latest script: - cmake --preset $PLATFORM - cmake --build --preset $PLATFORM-$TYPE @@ -20,14 +17,12 @@ build: - kernel.elf - kernel.sym - kernel.iso + expire_in: 1 week <<: *build_matrix bht: stage: build - image: registry.gitlab.ost.ch:45023/teachos/devcontainers/x86-64:15.2.0-4 - before_script: - - apt update - - apt install -y build-essential cmake ninja-build lcov libcatch2-dev gcovr + image: registry.gitlab.ost.ch:45023/teachos/devcontainers/bht.ci:latest script: - cmake --preset bht - cmake --build --preset bht-dbg @@ -38,7 +33,7 @@ bht: - gcovr --root . --cobertura-pretty --output coverage/cobertura-coverage.xml after_script: - echo "CoverageReport public URL - https://teachos.pages.ost.ch/-/kernel/-/jobs/$CI_JOB_ID/artifacts/coverage/index.html" - coverage: '/Total:\|\s*(\d+(\.\d+)?)\%/' + coverage: '/Total:\|\s*(\d+(?:\.\d+)?)\%/' artifacts: paths: - coverage.info @@ -1,5 +1,5 @@ exclude = /usr/include/* -exclude = build/_deps/* +exclude = build/bht/_deps/* exclude = tests/* ignore_errors = unused,empty,inconsistent
\ No newline at end of file diff --git a/CMakeLists.txt b/CMakeLists.txt index febcf0e..6cc8a2f 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -18,15 +18,17 @@ include("GenerateBootableIso") include("FetchContent") -FetchContent_Declare( - "Catch2" - URL "https://github.com/catchorg/Catch2/archive/refs/tags/v3.7.1.tar.gz" - URL_HASH "SHA256=c991b247a1a0d7bb9c39aa35faf0fe9e19764213f28ffba3109388e62ee0269c" - EXCLUDE_FROM_ALL - FIND_PACKAGE_ARGS -) +if (NOT CMAKE_CROSSCOMPILING) + FetchContent_Declare( + "Catch2" + URL "https://github.com/catchorg/Catch2/archive/refs/tags/v3.7.1.tar.gz" + URL_HASH "SHA256=c991b247a1a0d7bb9c39aa35faf0fe9e19764213f28ffba3109388e62ee0269c" + EXCLUDE_FROM_ALL + FIND_PACKAGE_ARGS + ) -FetchContent_MakeAvailable("Catch2") + FetchContent_MakeAvailable("Catch2") +endif() #[============================================================================[ # Global Build System Options @@ -39,6 +41,10 @@ option(TEACHOS_GENERATE_DOCS "Generate documentation during build" ON) # Global Build System Configuration #]============================================================================] +if(POLICY CMP0209) + cmake_policy(SET CMP0209 NEW) +endif() + set(CMAKE_RUNTIME_OUTPUT_DIRECTORY "${PROJECT_BINARY_DIR}/bin") set(CMAKE_ARCHIVE_OUTPUT_DIRECTORY "${PROJECT_BINARY_DIR}/lib") set(CMAKE_INTERPROCEDURAL_OPTIMIZATION YES) diff --git a/arch/x86_64/CMakeLists.txt b/arch/x86_64/CMakeLists.txt index 89d9bc0..4427e4c 100644 --- a/arch/x86_64/CMakeLists.txt +++ b/arch/x86_64/CMakeLists.txt @@ -15,6 +15,7 @@ target_sources("x86_64" PRIVATE "kapi/boot_modules.cpp" "kapi/cio.cpp" "kapi/cpu.cpp" + "kapi/interrupts.cpp" "kapi/memory.cpp" "kapi/system.cpp" diff --git a/arch/x86_64/include/arch/cpu/interrupts.hpp b/arch/x86_64/include/arch/cpu/interrupts.hpp index 8f156a4..b9adb6e 100644 --- a/arch/x86_64/include/arch/cpu/interrupts.hpp +++ b/arch/x86_64/include/arch/cpu/interrupts.hpp @@ -1,6 +1,8 @@ #ifndef TEACHOS_X86_64_CPU_INTERRUPTS_HPP #define TEACHOS_X86_64_CPU_INTERRUPTS_HPP +#include "kapi/memory.hpp" + #include "arch/cpu/segment_selector.hpp" #include <array> @@ -57,36 +59,36 @@ namespace arch::cpu { struct { - std::uint64_t r15; - std::uint64_t r14; - std::uint64_t r13; - std::uint64_t r12; - std::uint64_t r11; - std::uint64_t r10; - std::uint64_t r9; - std::uint64_t r8; - std::uint64_t rdi; - std::uint64_t rsi; - std::uint64_t rbp; - std::uint64_t rdx; - std::uint64_t rcx; - std::uint64_t rbx; - std::uint64_t rax; + std::uint64_t r15{}; + std::uint64_t r14{}; + std::uint64_t r13{}; + std::uint64_t r12{}; + std::uint64_t r11{}; + std::uint64_t r10{}; + std::uint64_t r9{}; + std::uint64_t r8{}; + std::uint64_t rdi{}; + std::uint64_t rsi{}; + std::uint64_t rbp{}; + std::uint64_t rdx{}; + std::uint64_t rcx{}; + std::uint64_t rbx{}; + std::uint64_t rax{}; } handler_saved; struct { - std::uint64_t number; - std::uint64_t error_code; + std::uint64_t number{}; + std::uint64_t error_code{}; } interrupt; struct { - std::uint64_t rip; - std::uint64_t cs; - std::uint64_t rflags; - std::uint64_t rsp; - std::uint64_t ss; + kapi::memory::linear_address rip{}; + std::uint64_t cs{}; + std::uint64_t rflags{}; + kapi::memory::linear_address rsp{}; + std::uint64_t ss{}; } cpu_saved; }; @@ -109,9 +111,6 @@ namespace arch::cpu auto static read() -> interrupt_descriptor_table_register; }; - auto enable_interrupts() -> void; - auto disable_interrupts() -> void; - } // namespace arch::cpu #endif
\ No newline at end of file diff --git a/arch/x86_64/kapi/cpu.cpp b/arch/x86_64/kapi/cpu.cpp index 2a0f8f7..12edb0f 100644 --- a/arch/x86_64/kapi/cpu.cpp +++ b/arch/x86_64/kapi/cpu.cpp @@ -1,8 +1,27 @@ #include "kapi/cpu.hpp" +#include "kapi/system.hpp" + +#include "arch/cpu/initialization.hpp" + +#include <atomic> + namespace kapi::cpu { + auto init() -> void + { + auto static constinit is_initialized = std::atomic_flag{}; + + if (is_initialized.test_and_set()) + { + system::panic("[x86_64] CPU has already been initialized."); + } + + arch::cpu::initialize_descriptors(); + arch::cpu::initialize_legacy_interrupts(); + } + auto halt() -> void { asm volatile("1: hlt\njmp 1b"); diff --git a/arch/x86_64/kapi/interrupts.cpp b/arch/x86_64/kapi/interrupts.cpp new file mode 100644 index 0000000..cf1defa --- /dev/null +++ b/arch/x86_64/kapi/interrupts.cpp @@ -0,0 +1,16 @@ +#include "kapi/interrupts.hpp" + +namespace kapi::interrupts +{ + + auto enable() -> void + { + asm volatile("sti"); + } + + auto disable() -> void + { + asm volatile("cli"); + } + +} // namespace kapi::interrupts
\ No newline at end of file diff --git a/arch/x86_64/kapi/system.cpp b/arch/x86_64/kapi/system.cpp index 301169f..09c7152 100644 --- a/arch/x86_64/kapi/system.cpp +++ b/arch/x86_64/kapi/system.cpp @@ -1,16 +1,8 @@ #include "kapi/system.hpp" -#include "arch/cpu/initialization.hpp" -#include "arch/cpu/interrupts.hpp" - namespace kapi::system { - auto memory_initialized() -> void - { - arch::cpu::initialize_descriptors(); - arch::cpu::initialize_legacy_interrupts(); - arch::cpu::enable_interrupts(); - } + auto memory_initialized() -> void {} } // namespace kapi::system
\ No newline at end of file diff --git a/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/gate_descriptor.hpp b/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/gate_descriptor.hpp deleted file mode 100644 index 07110c8..0000000 --- a/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/gate_descriptor.hpp +++ /dev/null @@ -1,69 +0,0 @@ -#ifndef TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_GATE_DESCRIPTOR_HPP -#define TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_GATE_DESCRIPTOR_HPP - -#include "arch/context_switching/interrupt_descriptor_table/idt_flags.hpp" -#include "arch/context_switching/interrupt_descriptor_table/ist_offset.hpp" -#include "arch/context_switching/interrupt_descriptor_table/segment_selector.hpp" - -#include <bitset> -#include <cstdint> - -namespace teachos::arch::context_switching::interrupt_descriptor_table -{ - __extension__ typedef __int128 int128_t; - __extension__ typedef unsigned __int128 uint128_t; - - /** - * @brief Defines helper function for all states and the actual data the gate descriptor can have. - */ - struct [[gnu::packed]] gate_descriptor - { - /** - * @brief Default Constructor. - */ - gate_descriptor() = default; - - /** - * @brief Constructor. - * - * @note Created gate descriptor copies the given bytes into these components ending with a 32 bit reserved - * field that has to be used, because the 64-bit gate descriptor needs to be big enough for two 32-bit gate - * descriptor. - * - 16 bit Segment Selector - * - 3 bit Interrupt Stack Table Offset - * - 8 bit Type and Flags - * - 64 bit Offset - * - * @param flags Copies the bits set from the given data into the individual components of a gate - * descriptor. - */ - explicit gate_descriptor(uint128_t flags); - - /** - * @brief Constructor. - * - * @param selector, ist, flags, offset Copies the bits set from the given data into the individual components of - * a gate descriptor. - */ - gate_descriptor(segment_selector selector, ist_offset ist, idt_flags flags, uint64_t offset); - - /** - * @brief Allows to compare the underlying bits of two instances. - * - * @param other Other instance that we want to compare with. - * @return Whether the underlying set bits of both types are the same. - */ - auto operator==(gate_descriptor const & other) const -> bool = default; - - private: - // The order in private variables starts for the first variable being the rightmost bit. - uint16_t _offset_1 = {}; ///< Lower 16 bits of handler function address (0 - 15) - segment_selector _selector = {}; ///< Segment selector (16 - 31) - ist_offset _ist = {}; ///< Interrupt Stack Table offset (32 - 39) - idt_flags _flags = {}; ///< Gate Type and Flags (40 - 47) - uint64_t _offset_2 : 48 = {}; ///< Upper 48 bits of handler function address (48 - 95) - uint32_t : 32; ///< Reserved field used to ensure this struct is 128 bits big (96 - 127) - }; -} // namespace teachos::arch::context_switching::interrupt_descriptor_table - -#endif // TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_GATE_DESCRIPTOR_HPP diff --git a/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/idt_flags.hpp b/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/idt_flags.hpp deleted file mode 100644 index 5104c36..0000000 --- a/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/idt_flags.hpp +++ /dev/null @@ -1,81 +0,0 @@ - -#ifndef TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_IDT_FLAGS_HPP -#define TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_IDT_FLAGS_HPP - -#include <bitset> -#include <cstdint> - -namespace teachos::arch::context_switching::interrupt_descriptor_table -{ - /** - * @brief Defines helper function for all states that the access byte field of a segment descriptor can - * have. - */ - struct [[gnu::packed]] idt_flags - { - /** - * @brief Possible set bits in our underlying bits and the meaning when they are set. - */ - enum bitset : uint8_t - { - INTERRUPT_GATE = 0b01110, ///< The actual type of gate segment is a interrupt gate. - TRAP_GATE = 0b01111, ///< The actual type of gate segment is a trap gate. - DESCRIPTOR_LEVEL_KERNEL = - 0U << 5U, ///< Highest privileged level used by the kernel to allow for full access of resources. - DESCRIPTOR_LEVEL_ADMIN = - 1U << 5U, ///< Restricts access to own application and thoose of lower privilege. Should only be used if more - ///< than two privilege levels are required, otherwise using Level 3 and Level 0 is recommended. - DESCRIPTOR_LEVEL_PRIVILEGED_USER = - 2U << 5U, ///< Restricts access to own application and thoose of lower privilege. Should only be used if more - ///< than two privilege levels are required, otherwise using Level 3 and Level 0 is recommended. - DESCRIPTOR_LEVEL_USER = 3U << 5U, ///< Restricts access to only application and their specific memory. - PRESENT = 1U << 7U, ///< Present bit; Allows an entry to refer to a valid segment. - ///< Must be set (1) for any valid segment. - }; - - /** - * @brief Default Constructor. - */ - idt_flags() = default; - - /** - * @brief Constructor. - * - * @param flags Allows to set flags for the access byte field using the unscoped enum contained in this class, used - * to allow for direct integer conversion. This value is saved and can later be used to check whether certain flags - * are enabled or not using contains_flags method. - */ - idt_flags(uint8_t flags); - - /** - * @brief Checks if the given std::bitset is a subset or equivalent to the underlying data. - * - * @note Meaning that all bits that are set in the given std::bitset also have to be set in the underlyng - * data. Any additional bits that are set are not relevant. - * - * @param other Flags that we want to compare against and check if the underlying data has the same bits set. - * @return Whether the given flags are a subset or equivalent with the underlying data. - */ - auto contains_flags(std::bitset<8U> other) const -> bool; - - /** - * @brief Allows to compare the underlying bits of two instances. - * - * @param other Other instance that we want to compare with. - * @return Whether the underlying set bits of both types are the same. - */ - auto operator==(idt_flags const & other) const -> bool = default; - - /** - * @brief Combines all bits that are set in the std::bitset flags with the bits already set in the underlying data. - * - * @param other Additional bits that should be set. - */ - auto operator|=(std::bitset<8U> other) -> void; - - private: - uint8_t _flags = {}; ///< Underlying bits used to read the flags from. - }; -} // namespace teachos::arch::context_switching::interrupt_descriptor_table - -#endif // TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_IDT_FLAGS_HPP
\ No newline at end of file diff --git a/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/interrupt_descriptor_table.hpp b/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/interrupt_descriptor_table.hpp deleted file mode 100644 index b388e0e..0000000 --- a/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/interrupt_descriptor_table.hpp +++ /dev/null @@ -1,24 +0,0 @@ -#ifndef TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_INTERRUPT_DESCRIPTOR_TABLE_HPP -#define TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_INTERRUPT_DESCRIPTOR_TABLE_HPP - -#include "arch/context_switching/interrupt_descriptor_table/interrupt_descriptor_table_pointer.hpp" - -namespace teachos::arch::context_switching::interrupt_descriptor_table -{ - /** - * @brief Updates the IDTR with the created interrupt descriptor table. If it has not been created yet this - * method will create it. - */ - auto update_interrupt_descriptor_table_register() -> void; - - /** - * @brief Creates the interrupt descriptor table, with the minimum required configuration. If this method is called - * more than once, the previously created instance is returned instead. - * - * @return Reference to the created interrupt_descriptor_table. - */ - auto get_or_create_interrupt_descriptor_table() -> interrupt_descriptor_table &; - -} // namespace teachos::arch::context_switching::interrupt_descriptor_table - -#endif // TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_INTERRUPT_DESCRIPTOR_TABLE_HPP diff --git a/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/interrupt_descriptor_table_pointer.hpp b/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/interrupt_descriptor_table_pointer.hpp deleted file mode 100644 index 7fe933b..0000000 --- a/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/interrupt_descriptor_table_pointer.hpp +++ /dev/null @@ -1,40 +0,0 @@ -#ifndef TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_INTERRUPT_DESCRIPTOR_TABLE_POINTER_HPP -#define TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_INTERRUPT_DESCRIPTOR_TABLE_POINTER_HPP - -#include "arch/context_switching/interrupt_descriptor_table/gate_descriptor.hpp" -#include "arch/stl/vector.hpp" - -namespace teachos::arch::context_switching::interrupt_descriptor_table -{ - using interrupt_descriptor_table = stl::vector<gate_descriptor>; - - /** - * @brief Represents a pointer to the Interrupt Descriptor Table (IDT). - * - * This structure is used to store the base address and length of the IDT. - */ - struct [[gnu::packed]] interrupt_descriptor_table_pointer - { - /** - * @brief Default constructor. - */ - interrupt_descriptor_table_pointer() = default; - - /** - * @brief Constructor. - */ - interrupt_descriptor_table_pointer(uint16_t table_length, gate_descriptor * address); - - /** - * @brief Defaulted three-way comparsion operator. - */ - auto operator<=>(interrupt_descriptor_table_pointer const & other) const -> std::strong_ordering = default; - - private: - uint16_t table_length = {}; ///< The amount of segment descriptor entries in the global descriptor table - 1. - gate_descriptor * address = {}; ///< Non-owning pointer to the IDT base address. - }; - -} // namespace teachos::arch::context_switching::interrupt_descriptor_table - -#endif // TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_INTERRUPT_DESCRIPTOR_TABLE_POINTER_HPP diff --git a/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/ist_offset.hpp b/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/ist_offset.hpp deleted file mode 100644 index e45bcf4..0000000 --- a/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/ist_offset.hpp +++ /dev/null @@ -1,45 +0,0 @@ -#ifndef TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_IST_OFFSET_HPP -#define TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_IST_OFFSET_HPP - -#include <bitset> -#include <cstdint> - -namespace teachos::arch::context_switching::interrupt_descriptor_table -{ - /** - * @brief Defines helper function for all states that the interrupt stack table offset field of a gate descriptor can - * have. Is automatically increased to one byte in size, to include the following 5 reserved bits in the gate - * descriptor. - */ - struct [[gnu::packed]] ist_offset - { - /** - * @brief Default Constructor. - */ - ist_offset() = default; - - /** - * @brief Constructor. - * - * @param offset Offset into the interrupt stack table. A value of of 0 means we do not switch stacks, whereas 1 - 7 - * mean we switch to the n-th stack in the Interrupt Stack Table, contained in the TSS if the gate descriptor that - * contains this field is called. - */ - ist_offset(uint8_t offset); - - /** - * @brief Allows to compare the underlying set bits of two instances. - * - * @param other Other instance that we want to compare with. - * @return Whether the underlying set bits of both types are the same. - */ - auto operator==(ist_offset const & other) const -> bool = default; - - private: - uint8_t _ist : 3 = {}; ///< Offset into the interrupt stack table. A value of of 0 means we do not switch stacks, - ///< whereas 1 - 7 mean we switch to the n-th stack in the Interrupt Stack Table, contained - ///< in the TSS if the gate descriptor that contains this field is called. - }; -} // namespace teachos::arch::context_switching::interrupt_descriptor_table - -#endif // TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_IST_OFFSET_HPP diff --git a/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/segment_selector.hpp b/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/segment_selector.hpp deleted file mode 100644 index ea8c145..0000000 --- a/arch/x86_64/pre/include/arch/context_switching/interrupt_descriptor_table/segment_selector.hpp +++ /dev/null @@ -1,105 +0,0 @@ -#ifndef TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_SEGMENT_SELECTOR_HPP -#define TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_SEGMENT_SELECTOR_HPP - -#include <bitset> -#include <cstdint> - -namespace teachos::arch::context_switching::interrupt_descriptor_table -{ - /** - * @brief Represents a segment selector in the x86_64 architecture, which points to a valid code segment in the global - * descriptor table. - * - * A segment selector is a 16-bit identifier used to select a segment descriptor - * from the Global Descriptor Table (GDT) or the Local Descriptor Table (LDT). - * It contains an index, a table indicator (TI), and a requested privilege level (RPL). - */ - struct [[gnu::packed]] segment_selector - { - /** - * @brief Possible set bits in our underlying bits and the meaning when they are set. - */ - enum bitset : uint8_t - { - REQUEST_LEVEL_KERNEL = - 0U << 0U, ///< Highest privileged level used by the kernel to allow for full access of resources. - REQUEST_LEVEL_ADMIN = - 1U << 0U, ///< Restricts access to own application and thoose of lower privilege. Should only be used if more - ///< than two privilege levels are required, otherwise using Level 3 and Level 0 is recommended. - REQUEST_LEVEL_PRIVILEGED_USER = - 2U << 0U, ///< Restricts access to own application and thoose of lower privilege. Should only be used if more - ///< than two privilege levels are required, otherwise using Level 3 and Level 0 is recommended. - REQUEST_LEVEL_USER = 3U << 0U, ///< Restricts access to only application and their specific memory. - LOCAL_DESCRIPTOR_TABLE = 1U << 2U, ///< Wheter the index referes to an entry in the local or global descriptor - ///< table. If enabled the index points to a local descriptor table, if it is - ///< cleared it referes to a global descriptor table instead. - }; - - /** - * @brief Default constructor. - */ - segment_selector() = default; - - /** - * @brief Constructor. - * - * @param index Index into the local or global descriptor table. Processor multiplies the index value by 8 (number - * of bytes in 32-bit segment descriptor) and adds the result to the base GDT or LDT address. - * @param flags Allows to set flags for the flags field using the unscoped enum contained in this class, used to - * allow for direct integer conversion. - */ - constexpr segment_selector(uint16_t index, uint8_t flags) - : _flags(flags) - , _index(index) - { - // Nothing to do. - } - - /** - * @brief Checks if the given std::bitset is a subset or equivalent to the underlying data. - * - * @note Meaning that all bits that are set in the given std::bitset also have to be set in the underlyng - * data. Any additional bits that are set are not relevant. - * - * @param other Flags that we want to compare against and check if the underlying data has the same bits set. - * @return Whether the given flags are a subset or equivalent with the underlying data. - */ - auto contains_flags(std::bitset<3U> other) const -> bool; - - /** - * @brief Gets the index into the global descriptor table or the local descriptor table this segment selector is - * pointing too. - * - * @return Underlying value of the index field, bit 3 - 16. - */ - [[gnu::section(".user_text")]] - auto get_index() const -> uint16_t; - - /** - * @brief Defaulted three-way comparsion operator. - */ - auto operator<=>(segment_selector const & other) const -> std::strong_ordering = default; - - /** - * @brief Combines all bits that are set in the std::bitset flags with the bits already set in the underlying data. - * - * @param other Additional bits that should be set. - */ - auto operator|=(std::bitset<3U> other) -> void; - - /** - * @brief Cast the underlying data into a combined 16-bit form, that contains all data. - * - * @return Underlying value combined into it's full size. - */ - operator uint16_t() const; - - private: - uint8_t _flags : 3 = {}; ///< Underlying bits used to read the flags from. - uint16_t _index - : 13 = {}; ///< Index into the local or global descriptor table. Processor multiplies the index value by 16 - ///< (number of bytes in segment descriptor) and adds the result to the base address. - }; -} // namespace teachos::arch::context_switching::interrupt_descriptor_table - -#endif // TEACHOS_ARCH_X86_64_CONTEXT_SWITCHING_INTERRUPT_DESCRIPTOR_TABLE_SEGMENT_SELECTOR_HPP diff --git a/arch/x86_64/pre/include/arch/interrupt_handling/generic_interrupt_handler.hpp b/arch/x86_64/pre/include/arch/interrupt_handling/generic_interrupt_handler.hpp deleted file mode 100644 index 15b35c1..0000000 --- a/arch/x86_64/pre/include/arch/interrupt_handling/generic_interrupt_handler.hpp +++ /dev/null @@ -1,34 +0,0 @@ -#ifndef TEACHOS_ARCH_X86_64_INTERRUPT_HANDLING_GENERIC_INTERRUPT_HANDLER_HPP -#define TEACHOS_ARCH_X86_64_INTERRUPT_HANDLING_GENERIC_INTERRUPT_HANDLER_HPP - -#include <cstdint> - -namespace teachos::arch::interrupt_handling -{ - /** - * @brief Represents the CPU state during an interrupt. - * - * Some interrupts push an error code, while others do not. The full list - * of which vector number contains the error code can be found here: https://wiki.osdev.org/Exceptions - */ - struct [[gnu::packed]] interrupt_frame - { - // uint64_t error_code; ///< Error code only pushed by some exceptions, therefore it is commented out. - uint64_t ip; ///< Instruction pointer at the time of the interrupt. - uint64_t cs; ///< Code segment selector indicating privilege level. - uint64_t flags; ///< CPU flags (RFLAGS) storing processor state. - uint64_t sp; ///< Stack pointer at the time of the interrupt. - uint64_t ss; ///< Stack segment selector, usually unused in 64-bit mode. - }; - - /** - * @brief Generic interrupt handler function. - * - * @param frame Pointer to the interrupt frame containing CPU state. - */ - [[gnu::interrupt]] - auto generic_interrupt_handler(interrupt_frame * frame) -> void; - -} // namespace teachos::arch::interrupt_handling - -#endif // TEACHOS_ARCH_X86_64_INTERRUPT_HANDLING_GENERIC_INTERRUPT_HANDLER_HPP diff --git a/arch/x86_64/pre/include/arch/kernel/cpu/call.hpp b/arch/x86_64/pre/include/arch/kernel/cpu/call.hpp deleted file mode 100644 index 3c43304..0000000 --- a/arch/x86_64/pre/include/arch/kernel/cpu/call.hpp +++ /dev/null @@ -1,30 +0,0 @@ -#ifndef TEACHOS_ARCH_X86_64_KERNEL_CPU_JMP_HPP -#define TEACHOS_ARCH_X86_64_KERNEL_CPU_JMP_HPP - -#include "arch/context_switching/interrupt_descriptor_table/segment_selector.hpp" - -#include <cstdint> - -namespace teachos::arch::kernel::cpu -{ - /** - * @brief Far Pointer. Address to function located in another code segment. - */ - struct far_pointer - { - void (*function)(); ///< Address of the function we want to call. (0-63) - context_switching::interrupt_descriptor_table::segment_selector - selector; ///< Segment selector pointing to the GDT entry we want to load into register CS. (64-79) - }; - - /** - * @brief Far call - A call to an instruction located in a different segment than the current code segment but at the - * same privilege level. - * - * @param pointer 64-bit operand size far pointer that we want to call. - */ - auto call(far_pointer pointer) -> void; - -} // namespace teachos::arch::kernel::cpu - -#endif // TEACHOS_ARCH_X86_64_KERNEL_CPU_JMP_HPP diff --git a/arch/x86_64/pre/include/arch/kernel/cpu/idtr.hpp b/arch/x86_64/pre/include/arch/kernel/cpu/idtr.hpp deleted file mode 100644 index cb800d0..0000000 --- a/arch/x86_64/pre/include/arch/kernel/cpu/idtr.hpp +++ /dev/null @@ -1,27 +0,0 @@ -#ifndef TEACHOS_ARCH_X86_64_KERNEL_CPU_IDTR_HPP -#define TEACHOS_ARCH_X86_64_KERNEL_CPU_IDTR_HPP - -#include "arch/context_switching/interrupt_descriptor_table/interrupt_descriptor_table_pointer.hpp" - -#include <bitset> -#include <cstdint> - -namespace teachos::arch::kernel::cpu -{ - /** - * @brief Returns the value in the IDTR register. - * - * @return Value of IDTR register. - */ - auto store_interrupt_descriptor_table() - -> context_switching::interrupt_descriptor_table::interrupt_descriptor_table_pointer; - - /** - * @brief Loads the interrupt_descriptor_table_pointer into the interrupt descriptor table register (IDTR). - */ - auto load_interrupt_descriptor_table( - context_switching::interrupt_descriptor_table::interrupt_descriptor_table_pointer const & idt_pointer) -> void; - -} // namespace teachos::arch::kernel::cpu - -#endif // TEACHOS_ARCH_X86_64_KERNEL_CPU_IDTR_HPP diff --git a/arch/x86_64/pre/include/arch/kernel/cpu/if.hpp b/arch/x86_64/pre/include/arch/kernel/cpu/if.hpp deleted file mode 100644 index 48707dc..0000000 --- a/arch/x86_64/pre/include/arch/kernel/cpu/if.hpp +++ /dev/null @@ -1,21 +0,0 @@ -#ifndef TEACHOS_ARCH_X86_64_KERNEL_CPU_IF_HPP -#define TEACHOS_ARCH_X86_64_KERNEL_CPU_IF_HPP - -namespace teachos::arch::kernel::cpu -{ - /** - * @brief Sets the interrupt flag (IF) in the EFLAGS register. - * This allows the processor to respond to maskable hardware interrupts. - */ - auto set_interrupt_flag() -> void; - - /** - * @brief Clears the interrupt flag (IF) in the EFLAGS register. - * This will stop the processor to respond to maskable hardware interrupts and needs to be done before changing the - * Interrupt Descriptor Table with lidt. - */ - auto clear_interrupt_flag() -> void; - -} // namespace teachos::arch::kernel::cpu - -#endif // TEACHOS_ARCH_X86_64_KERNEL_CPU_IF_HPP diff --git a/arch/x86_64/pre/include/arch/kernel/cpu/msr.hpp b/arch/x86_64/pre/include/arch/kernel/cpu/msr.hpp deleted file mode 100644 index 99d6378..0000000 --- a/arch/x86_64/pre/include/arch/kernel/cpu/msr.hpp +++ /dev/null @@ -1,64 +0,0 @@ -#ifndef TEACHOS_ARCH_X86_64_KERNEL_CPU_NXE_HPP -#define TEACHOS_ARCH_X86_64_KERNEL_CPU_NXE_HPP - -#include <bitset> -#include <cstdint> - -namespace teachos::arch::kernel::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::kernel::cpu - -#endif // TEACHOS_ARCH_X86_64_KERNEL_CPU_NXE_HPP
\ No newline at end of file diff --git a/arch/x86_64/pre/include/arch/kernel/cpu/tr.hpp b/arch/x86_64/pre/include/arch/kernel/cpu/tr.hpp deleted file mode 100644 index 7c856f1..0000000 --- a/arch/x86_64/pre/include/arch/kernel/cpu/tr.hpp +++ /dev/null @@ -1,24 +0,0 @@ -#ifndef TEACHOS_ARCH_X86_64_KERNEL_CPU_TR_HPP -#define TEACHOS_ARCH_X86_64_KERNEL_CPU_TR_HPP - -#include <bitset> -#include <cstdint> - -namespace teachos::arch::kernel::cpu -{ - - /** - * @brief Returns the value in the LTR register. - * - * @return Value of LTR register. - */ - auto store_task_register() -> uint16_t; - - /** - * @brief Loads the gdt offset to the tss segment descriptor into the task register (TR). - */ - auto load_task_register(uint16_t gdt_offset) -> void; - -} // namespace teachos::arch::kernel::cpu - -#endif // TEACHOS_ARCH_X86_64_KERNEL_CPU_TR_HPP diff --git a/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/gate_descriptor.cpp b/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/gate_descriptor.cpp deleted file mode 100644 index 28f289c..0000000 --- a/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/gate_descriptor.cpp +++ /dev/null @@ -1,24 +0,0 @@ -#include "arch/context_switching/interrupt_descriptor_table/gate_descriptor.hpp" - -namespace teachos::arch::context_switching::interrupt_descriptor_table -{ - gate_descriptor::gate_descriptor(uint128_t flags) - : _offset_1(flags) - , _selector(flags >> 19U, flags >> 16U) - , _ist(flags >> 32U) - , _flags(flags >> 40U) - , _offset_2(flags >> 48U) - { - // Nothing to do. - } - - gate_descriptor::gate_descriptor(segment_selector selector, ist_offset ist, idt_flags flags, uint64_t offset) - : _offset_1(offset) - , _selector(selector) - , _ist(ist) - , _flags(flags) - , _offset_2(offset >> 16U) - { - // Nothing to do. - } -} // namespace teachos::arch::context_switching::interrupt_descriptor_table diff --git a/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/idt_flags.cpp b/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/idt_flags.cpp deleted file mode 100644 index f3b9d5e..0000000 --- a/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/idt_flags.cpp +++ /dev/null @@ -1,20 +0,0 @@ -#include "arch/context_switching/interrupt_descriptor_table/idt_flags.hpp" - -namespace teachos::arch::context_switching::interrupt_descriptor_table -{ - idt_flags::idt_flags(uint8_t flags) - : _flags(flags) - { - // Nothing to do. - } - - auto idt_flags::contains_flags(std::bitset<8U> other) const -> bool - { - return (std::bitset<8U>{_flags} & other) == other; - } - - auto idt_flags::operator|=(std::bitset<8U> other) -> void - { - _flags |= other.to_ulong(); - } -} // namespace teachos::arch::context_switching::interrupt_descriptor_table diff --git a/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/interrupt_descriptor_table.cpp b/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/interrupt_descriptor_table.cpp deleted file mode 100644 index 8640385..0000000 --- a/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/interrupt_descriptor_table.cpp +++ /dev/null @@ -1,53 +0,0 @@ -#include "arch/context_switching/interrupt_descriptor_table/interrupt_descriptor_table.hpp" - -#include "arch/exception_handling/assert.hpp" -#include "arch/interrupt_handling/generic_interrupt_handler.hpp" -#include "arch/kernel/cpu/idtr.hpp" - -namespace teachos::arch::context_switching::interrupt_descriptor_table -{ - namespace - { - /// @brief Amount of currently reserved interrupt indicies. - /// See https://wiki.osdev.org/Interrupt_Descriptor_Table#IDT_items for more information. - constexpr uint16_t RESERVED_INTERRUPT_COUNT = 256U; - - auto create_interrupt_descriptor_table() -> interrupt_descriptor_table - { - interrupt_descriptor_table interrupt_descriptor_table{RESERVED_INTERRUPT_COUNT}; - - uint64_t offset = reinterpret_cast<uint64_t>(interrupt_handling::generic_interrupt_handler); - segment_selector selector{1U, segment_selector::REQUEST_LEVEL_KERNEL}; - ist_offset ist{0U}; - idt_flags flags{idt_flags::DESCRIPTOR_LEVEL_KERNEL | idt_flags::INTERRUPT_GATE | idt_flags::PRESENT}; - - for (std::size_t i = 0; i < interrupt_descriptor_table.size(); i++) - { - interrupt_descriptor_table.at(i) = {selector, ist, flags, offset}; - } - - return interrupt_descriptor_table; - } - } // namespace - - auto get_or_create_interrupt_descriptor_table() -> interrupt_descriptor_table & - { - // Interrupt Descriptor Table needs to be kept alive - interrupt_descriptor_table static idt = create_interrupt_descriptor_table(); - return idt; - } - - auto update_interrupt_descriptor_table_register() -> void - { - decltype(auto) idt = get_or_create_interrupt_descriptor_table(); - - interrupt_descriptor_table_pointer idt_pointer{static_cast<uint16_t>((idt.size() * sizeof(gate_descriptor)) - 1), - idt.data()}; - kernel::cpu::load_interrupt_descriptor_table(idt_pointer); - - auto const stored_gdt_pointer = kernel::cpu::store_interrupt_descriptor_table(); - arch::exception_handling::assert( - idt_pointer == stored_gdt_pointer, - "[Interrupt Descriptor Table] Loaded IDTR value is not the same as the stored value."); - } -} // namespace teachos::arch::context_switching::interrupt_descriptor_table diff --git a/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/interrupt_descriptor_table_pointer.cpp b/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/interrupt_descriptor_table_pointer.cpp deleted file mode 100644 index 7bcbae6..0000000 --- a/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/interrupt_descriptor_table_pointer.cpp +++ /dev/null @@ -1,13 +0,0 @@ -#include "arch/context_switching/interrupt_descriptor_table/interrupt_descriptor_table_pointer.hpp" - -namespace teachos::arch::context_switching::interrupt_descriptor_table -{ - interrupt_descriptor_table_pointer::interrupt_descriptor_table_pointer(uint16_t table_length, - gate_descriptor * address) - : table_length(table_length) - , address(address) - { - // Nothing to do. - } - -} // namespace teachos::arch::context_switching::interrupt_descriptor_table diff --git a/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/ist_offset.cpp b/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/ist_offset.cpp deleted file mode 100644 index a70e75d..0000000 --- a/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/ist_offset.cpp +++ /dev/null @@ -1,10 +0,0 @@ -#include "arch/context_switching/interrupt_descriptor_table/ist_offset.hpp" - -namespace teachos::arch::context_switching::interrupt_descriptor_table -{ - ist_offset::ist_offset(uint8_t index) - : _ist(index) - { - // Nothing to do. - } -} // namespace teachos::arch::context_switching::interrupt_descriptor_table diff --git a/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/segment_selector.cpp b/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/segment_selector.cpp deleted file mode 100644 index 25ba859..0000000 --- a/arch/x86_64/pre/src/context_switching/interrupt_descriptor_table/segment_selector.cpp +++ /dev/null @@ -1,24 +0,0 @@ -#include "arch/context_switching/interrupt_descriptor_table/segment_selector.hpp" - -namespace teachos::arch::context_switching::interrupt_descriptor_table -{ - auto segment_selector::contains_flags(std::bitset<3U> other) const -> bool - { - return (std::bitset<3U>{_flags} & other) == other; - } - - auto segment_selector::get_index() const -> uint16_t - { - return _index; - } - - auto segment_selector::operator|=(std::bitset<3U> other) -> void - { - _flags |= other.to_ulong(); - } - - segment_selector::operator uint16_t() const - { - return *reinterpret_cast<uint16_t const *>(this); - } -} // namespace teachos::arch::context_switching::interrupt_descriptor_table diff --git a/arch/x86_64/pre/src/interrupt_handling/generic_interrupt_handler.cpp b/arch/x86_64/pre/src/interrupt_handling/generic_interrupt_handler.cpp deleted file mode 100644 index 9d061a8..0000000 --- a/arch/x86_64/pre/src/interrupt_handling/generic_interrupt_handler.cpp +++ /dev/null @@ -1,13 +0,0 @@ -#include "arch/interrupt_handling/generic_interrupt_handler.hpp" - -#include "arch/video/vga/text.hpp" - -namespace teachos::arch::interrupt_handling -{ - auto generic_interrupt_handler(interrupt_frame * frame) -> void - { - (void)frame; - video::vga::text::write("An Interrupt occurred.", video::vga::text::common_attributes::green_on_black); - video::vga::text::newline(); - } -} // namespace teachos::arch::interrupt_handling diff --git a/arch/x86_64/pre/src/kernel/cpu/call.cpp b/arch/x86_64/pre/src/kernel/cpu/call.cpp deleted file mode 100644 index 98fa248..0000000 --- a/arch/x86_64/pre/src/kernel/cpu/call.cpp +++ /dev/null @@ -1,9 +0,0 @@ -#include "arch/kernel/cpu/call.hpp" - -namespace teachos::arch::kernel::cpu -{ - auto call(far_pointer pointer) -> void - { - asm volatile("rex64 lcall *%[input]" : /* no output from call */ : [input] "m"(pointer)); - } -} // namespace teachos::arch::kernel::cpu diff --git a/arch/x86_64/pre/src/kernel/cpu/idtr.cpp b/arch/x86_64/pre/src/kernel/cpu/idtr.cpp deleted file mode 100644 index 7aa20c1..0000000 --- a/arch/x86_64/pre/src/kernel/cpu/idtr.cpp +++ /dev/null @@ -1,18 +0,0 @@ -#include "arch/kernel/cpu/idtr.hpp" - -namespace teachos::arch::kernel::cpu -{ - auto store_interrupt_descriptor_table() - -> context_switching::interrupt_descriptor_table::interrupt_descriptor_table_pointer - { - context_switching::interrupt_descriptor_table::interrupt_descriptor_table_pointer current_value{}; - asm("sidt %[output]" : [output] "=m"(current_value)); - return current_value; - } - - auto load_interrupt_descriptor_table( - context_switching::interrupt_descriptor_table::interrupt_descriptor_table_pointer const & idt_pointer) -> void - { - asm volatile("lidt %[input]" : /* no output from call */ : [input] "m"(idt_pointer)); - } -} // namespace teachos::arch::kernel::cpu diff --git a/arch/x86_64/pre/src/kernel/cpu/if.cpp b/arch/x86_64/pre/src/kernel/cpu/if.cpp deleted file mode 100644 index 5d056fc..0000000 --- a/arch/x86_64/pre/src/kernel/cpu/if.cpp +++ /dev/null @@ -1,13 +0,0 @@ -namespace teachos::arch::kernel::cpu -{ - auto set_interrupt_flag() -> void - { - asm volatile("sti"); - } - - auto clear_interrupt_flag() -> void - { - asm volatile("cli"); - } - -} // namespace teachos::arch::kernel::cpu diff --git a/arch/x86_64/pre/src/kernel/cpu/tr.cpp b/arch/x86_64/pre/src/kernel/cpu/tr.cpp deleted file mode 100644 index a435540..0000000 --- a/arch/x86_64/pre/src/kernel/cpu/tr.cpp +++ /dev/null @@ -1,16 +0,0 @@ -#include "arch/kernel/cpu/tr.hpp" - -namespace teachos::arch::kernel::cpu -{ - auto store_task_register() -> uint16_t - { - uint16_t current_value{}; - asm("str %[output]" : [output] "=r"(current_value)); - return current_value; - } - - auto load_task_register(uint16_t gdt_offset) -> void - { - asm volatile("ltr %[input]" : /* no output from call */ : [input] "m"(gdt_offset)); - } -} // namespace teachos::arch::kernel::cpu diff --git a/arch/x86_64/src/cpu/interrupts.cpp b/arch/x86_64/src/cpu/interrupts.cpp index 048c461..907f289 100644 --- a/arch/x86_64/src/cpu/interrupts.cpp +++ b/arch/x86_64/src/cpu/interrupts.cpp @@ -1,6 +1,8 @@ #include "arch/cpu/interrupts.hpp" #include "kapi/cpu.hpp" +#include "kapi/interrupts.hpp" +#include "kapi/memory.hpp" #include "arch/cpu/legacy_pic.hpp" #include "arch/cpu/segment_selector.hpp" @@ -14,38 +16,113 @@ namespace arch::cpu namespace { - constexpr auto isr_number_page_fault = 0x0e; - constexpr auto isr_number_legacy_start = 0x20; - constexpr auto isr_number_legacy_end = 0x29; - constexpr auto isr_number_cascade_start = 0x2c; - constexpr auto isr_number_cascade_end = 0x2f; + enum struct exception + { + divide_error, + debug_exception, + non_maskable_interrupt, + breakpoint, + overflow, + bound_range_exceeded, + invalid_opcode, + device_not_available, + double_fault, + coprocessor_segment_overrun, + invalid_tss, + segment_not_present, + stack_segment_fault, + general_protection_fault, + page_fault, + x87_fpu_floating_point_error = 16, + alignment_check, + machine_check, + simd_floating_point_error, + virtualization_exception, + control_protection_exception, + hypervisor_injection_exception = 28, + vmm_communication_exception, + security_exception, + }; + + constexpr auto number_of_exception_vectors = 32u; + + constexpr auto pic_master_irq_start = 0x20; + constexpr auto pic_master_irq_end = pic_master_irq_start + 8; + constexpr auto pic_slave_irq_start = pic_master_irq_end; + + constexpr auto to_exception_type(exception e) + { + switch (e) + { + case exception::divide_error: + case exception::x87_fpu_floating_point_error: + case exception::simd_floating_point_error: + return kapi::cpu::exception::type::arithmetic_error; + case exception::breakpoint: + return kapi::cpu::exception::type::breakpoint; + case exception::invalid_opcode: + return kapi::cpu::exception::type::illegal_instruction; + case exception::stack_segment_fault: + return kapi::cpu::exception::type::memory_access_fault; + case exception::general_protection_fault: + return kapi::cpu::exception::type::privilege_violation; + case exception::page_fault: + return kapi::cpu::exception::type::page_fault; + case exception::alignment_check: + return kapi::cpu::exception::type::alignment_fault; + default: + return kapi::cpu::exception::type::unknown; + } + } - auto handle_page_fault(interrupt_frame * frame) -> void + constexpr auto has_error_code(exception e) { - auto fault_address = std::uintptr_t{}; - asm volatile("mov %%cr2, %0" : "=r"(fault_address)); - - auto const present = (frame->interrupt.error_code & 0x1) != 0; - auto const write = (frame->interrupt.error_code & 0x2) != 0; - auto const user = (frame->interrupt.error_code & 0x4) != 0; - - kstd::println(kstd::print_sink::stderr, "[x86_64:MMU] PAGE FAULT!"); - kstd::println(kstd::print_sink::stderr, "\tFault address: {:#018x}", fault_address); - kstd::println(kstd::print_sink::stderr, "\tPresent: {}", present); - kstd::println(kstd::print_sink::stderr, "\tWrite: {}", write); - kstd::println(kstd::print_sink::stderr, "\tUser: {}", user); - kstd::println(kstd::print_sink::stderr, "\tRIP: {:#018x}", frame->cpu_saved.rip); - kstd::println(kstd::print_sink::stderr, "\tHalting the system now!"); - - kapi::cpu::halt(); + switch (e) + { + case exception::double_fault: + case exception::invalid_tss: + case exception::segment_not_present: + case exception::stack_segment_fault: + case exception::general_protection_fault: + case exception::page_fault: + case exception::alignment_check: + case exception::control_protection_exception: + case exception::security_exception: + return true; + default: + return false; + } } - auto handle_legacy_interrupt(interrupt_frame * frame) -> void + auto dispatch_exception(interrupt_frame * frame) -> bool { - kstd::println("[x86_64:SYS] Ignoring 8259 legacy interrupt {:#04x}", frame->interrupt.number); + auto type = to_exception_type(static_cast<exception>(frame->interrupt.number)); + auto fault_address = kapi::memory::linear_address{}; + auto instruction_pointer = frame->cpu_saved.rip; + + switch (type) + { + case kapi::cpu::exception::type::page_fault: + { + asm volatile("mov %%cr2, %0" : "=r"(fault_address)); + auto present = (frame->interrupt.error_code & 0x1) != 0; + auto write = (frame->interrupt.error_code & 0x2) != 0; + auto user = (frame->interrupt.error_code & 0x4) != 0; + + return kapi::cpu::dispatch({type, instruction_pointer, fault_address, present, write, user}); + } + default: + return kapi::cpu::dispatch({type, instruction_pointer}); + } + } + auto acknowledge_pic_interrupt(interrupt_frame * frame) -> void + { + if (frame->interrupt.number >= pic_slave_irq_start) + { + pic_slave_control_port::write(pic_end_of_interrupt); + } pic_master_control_port::write(pic_end_of_interrupt); - pic_slave_control_port::write(pic_end_of_interrupt); } } // namespace @@ -55,22 +132,34 @@ namespace arch::cpu auto interrupt_dispatch(interrupt_frame * frame) -> void { - if ((frame->interrupt.number >= isr_number_legacy_start && frame->interrupt.number <= isr_number_legacy_end) || - (frame->interrupt.number >= isr_number_cascade_start && frame->interrupt.number <= isr_number_cascade_end)) + auto [number, code] = frame->interrupt; + + if (number < number_of_exception_vectors) { - handle_legacy_interrupt(frame); - return; + if (!dispatch_exception(frame)) + { + if (has_error_code(static_cast<exception>(number))) + { + kstd::println(kstd::print_sink::stderr, + "[x86_64:CPU] Unhandled exception number {:#04x} received with code {:#04x}", number, code); + } + else + { + kstd::println(kstd::print_sink::stderr, "[x86_64:CPU] Unhandled exception number {:#04x} received", number); + } + } } - - switch (frame->interrupt.number) + else { - case isr_number_page_fault: - handle_page_fault(frame); - break; - default: - kstd::println(kstd::print_sink::stderr, "[x86_64:SYS] Unhandled interrupt {:#04x} received with code {:#04x}", - frame->interrupt.number, frame->interrupt.error_code); - kapi::cpu::halt(); + auto irq_number = number - number_of_exception_vectors; + + if (kapi::interrupts::dispatch(irq_number) == kapi::interrupts::status::unhandled) + { + kstd::println(kstd::print_sink::stderr, "[x86_64:CPU] Unhandled interrupt {:#04x} (IRQ{})", number, + irq_number); + } + + acknowledge_pic_interrupt(frame); } } } @@ -83,7 +172,7 @@ namespace arch::cpu .offset_low = static_cast<std::uint16_t>(isr_stub_table[i] & 0xffff), // NOLINT(readability-magic-numbers) .m_code_segment = segment_selector{0, false, 1}, .interrupt_stack_table_selector = 0, - .gate_type = gate_type::interrupt_gate, + .gate_type = (i < 32 && i != 2) ? gate_type::trap_gate : gate_type::interrupt_gate, .descriptor_privilege_level = 0, .present = true, .offset_middle = @@ -111,14 +200,4 @@ namespace arch::cpu return idtr; } - auto enable_interrupts() -> void - { - asm volatile("sti"); - } - - auto disable_interrupts() -> void - { - asm volatile("cli"); - } - } // namespace arch::cpu
\ No newline at end of file diff --git a/kapi/CMakeLists.txt b/kapi/CMakeLists.txt index b239adb..c9aa23f 100644 --- a/kapi/CMakeLists.txt +++ b/kapi/CMakeLists.txt @@ -1,22 +1,13 @@ add_library("kapi" INTERFACE) add_library("os::kapi" ALIAS "kapi") +file(GLOB_RECURSE KAPI_HEADERS RELATIVE ${CMAKE_CURRENT_SOURCE_DIR} "include/**.hpp") + target_sources("kapi" PUBLIC FILE_SET HEADERS BASE_DIRS "include" FILES - "include/kapi/boot_modules.hpp" - "include/kapi/boot.hpp" - "include/kapi/cio.hpp" - "include/kapi/boot_module/boot_module.hpp" - "include/kapi/boot_module/boot_module_registry.hpp" - "include/kapi/memory.hpp" - "include/kapi/memory/address.hpp" - "include/kapi/memory/frame_allocator.hpp" - "include/kapi/memory/frame.hpp" - "include/kapi/memory/page_mapper.hpp" - "include/kapi/memory/page.hpp" - "include/kapi/system.hpp" + ${KAPI_HEADERS} ) target_include_directories("kapi" INTERFACE diff --git a/kapi/include/kapi/cpu.hpp b/kapi/include/kapi/cpu.hpp index 05b84b7..c6aa6ff 100644 --- a/kapi/include/kapi/cpu.hpp +++ b/kapi/include/kapi/cpu.hpp @@ -1,13 +1,117 @@ #ifndef TEACHOS_KAPI_CPU_HPP #define TEACHOS_KAPI_CPU_HPP +#include "kapi/memory.hpp" + +#include <kstd/format> + +#include <cstdint> + namespace kapi::cpu { + + //! An exception originating from the CPU directly. + //! + //! Exception generally model interrupts that are synchronous to the instruction stream. This means that they do not + //! originate from external hardware, but rather are a product of program execution. + struct exception + { + //! The type of the exception, which identifies the reason for it being raised. + enum class type : std::uint8_t + { + //! The reason for the exception is unknown or platform-specific + unknown, + //! A page fault occurred + page_fault, + //! A memory access (either in the data or instruction stream) violated it's alignment constraints. + alignment_fault, + //! A memory access (either in the data or instruction stream) violated it's permissions. + memory_access_fault, + //! An invalid instruction was present in the instruction stream. + illegal_instruction, + //! The preconditions for the execution of an instruction were not met. + privilege_violation, + //! An arithmetic error occurred. + arithmetic_error, + //! A breakpoint was hit in the instruction stream. + breakpoint, + //! The CPU is single-stepping through the instruction stream. + single_step, + }; + + //! The type of this exception. + type type{}; + + //! The value of the instruction pointer at the time this exception was raised. + kapi::memory::linear_address instruction_pointer{}; + + //! The memory address that caused this exception. + kapi::memory::linear_address access_address{}; + + //! Whether the page was present at the time of the exception. + bool is_present{}; + + //! Whether the exception was caused by a write access. + bool is_write_access{}; + + //! Whether the exception was caused by a user mode access. + bool is_user_mode{}; + }; + //! @qualifier platform-defined //! Halt the CPU. //! //! This function terminates execution of the kernel. [[noreturn]] auto halt() -> void; + + //! @qualifier platform-defined + //! Perform early CPU initialization. + //! + //! When this function returns, the CPU is in a state where interrupt could be enabled. This function must not enable + //! interrupts itself. + auto init() -> void; + + //! @qualifier kernel-defined + //! Dispatch an exception to the appropriate handler. + //! + //! @param context The exception context. + //! @return Whether the exception was handled. + [[nodiscard]] auto dispatch(exception const & context) -> bool; + } // namespace kapi::cpu +template<> +struct kstd::formatter<enum kapi::cpu::exception::type> +{ + constexpr auto parse(kstd::format_parse_context & ctx) -> decltype(ctx.begin()) + { + return ctx.begin(); + } + + constexpr auto format(enum kapi::cpu::exception::type type, kstd::format_context & ctx) const -> void + { + switch (type) + { + case kapi::cpu::exception::type::unknown: + return ctx.push("unknown"); + case kapi::cpu::exception::type::page_fault: + return ctx.push("page fault"); + case kapi::cpu::exception::type::alignment_fault: + return ctx.push("alignment fault"); + case kapi::cpu::exception::type::memory_access_fault: + return ctx.push("memory access fault"); + case kapi::cpu::exception::type::illegal_instruction: + return ctx.push("illegal instruction"); + case kapi::cpu::exception::type::privilege_violation: + return ctx.push("privilege violation"); + case kapi::cpu::exception::type::arithmetic_error: + return ctx.push("arithmetic error"); + case kapi::cpu::exception::type::breakpoint: + return ctx.push("breakpoint"); + case kapi::cpu::exception::type::single_step: + return ctx.push("single step"); + } + } +}; + #endif diff --git a/kapi/include/kapi/interrupts.hpp b/kapi/include/kapi/interrupts.hpp new file mode 100644 index 0000000..f72ef8c --- /dev/null +++ b/kapi/include/kapi/interrupts.hpp @@ -0,0 +1,61 @@ +#ifndef TEACHOS_KAPI_INTERRUPTS_HPP +#define TEACHOS_KAPI_INTERRUPTS_HPP + +#include <cstdint> + +namespace kapi::interrupts +{ + + enum class status : bool + { + unhandled, + handled, + }; + + //! The interface for all interrupt handlers. + struct handler + { + virtual ~handler() = default; + + //! Handle an interrupt with the given IRQ number. + // + //! This function will be called by the kernel in an interrupt context. As such, the function should complete its + //! task quickly and must take care when acquiring globally shared locks. + //! + //! @param irq_number The identifier of the interrupt request that triggered the handler. + //! @return status::handled if the handler successfully handled the interrupt, status::unhandled otherwise. + virtual auto handle_interrupt(std::uint32_t irq_number) -> status = 0; + }; + + //! @qualifier platform-defined + //! Enable external interrupts. + auto enable() -> void; + + //! @qualifier platform-defined + //! Disable external interrupts. + auto disable() -> void; + + //! @qualifier kernel-defined + //! Register an interrupt handler for the given IRQ number. + //! + //! @param irq_number The IRQ number to register the handler for. + //! @param handler The interrupt handler to register. + auto register_handler(std::uint32_t irq_number, handler & handler) -> void; + + //! @qualifier kernel-defined + //! Unregister a previously registered interrupt handler. + //! + //! @param irq_number The IRQ number to unregister the handler for. + //! @param handler The interrupt handler to unregister. + auto unregister_handler(std::uint32_t irq_number, handler & handler) -> void; + + //! @qualifier kernel-defined + //! Dispatch an interrupt to all registered handlers. + //! + //! @param irq_number The IRQ number to dispatch. + //! @return status::handled if the interrupt was handled by at least one handler, status::unhandled otherwise. + auto dispatch(std::uint32_t irq_number) -> status; + +} // namespace kapi::interrupts + +#endif
\ No newline at end of file diff --git a/kernel/CMakeLists.txt b/kernel/CMakeLists.txt index eb762ac..cadc373 100644 --- a/kernel/CMakeLists.txt +++ b/kernel/CMakeLists.txt @@ -2,6 +2,8 @@ add_executable("kernel" # Platform-independent KAPI implementation "kapi/boot_modules.cpp" "kapi/cio.cpp" + "kapi/cpu.cpp" + "kapi/interrupts.cpp" "kapi/memory.cpp" "kapi/system.cpp" @@ -60,6 +62,15 @@ set_property(TARGET "kernel" "${KERNEL_LINKER_SCRIPT}" ) +file(GLOB_RECURSE KERNEL_HEADERS RELATIVE ${CMAKE_CURRENT_SOURCE_DIR} "include/**.hpp") + +target_sources("kernel" PUBLIC + FILE_SET HEADERS + BASE_DIRS "include" + FILES + ${KERNEL_HEADERS} +) + target_disassemble("kernel") target_extract_debug_symbols("kernel") target_strip("kernel") diff --git a/kernel/kapi/cpu.cpp b/kernel/kapi/cpu.cpp new file mode 100644 index 0000000..13de584 --- /dev/null +++ b/kernel/kapi/cpu.cpp @@ -0,0 +1,35 @@ +#include "kapi/cpu.hpp" + +#include "kapi/system.hpp" + +#include <kstd/print> + +namespace kapi::cpu +{ + + namespace + { + auto handle_page_fault(kapi::cpu::exception const & context) -> bool + { + kstd::println(kstd::print_sink::stderr, "\tFault address: {:#018x}", context.access_address); + kstd::println(kstd::print_sink::stderr, "\tPresent: {}", context.is_present); + kstd::println(kstd::print_sink::stderr, "\tWrite: {}", context.is_write_access); + kstd::println(kstd::print_sink::stderr, "\tUser: {}", context.is_user_mode); + + kapi::system::panic("Halting the system due to an unrecoverable page fault."); + } + } // namespace + + auto dispatch(exception const & context) -> bool + { + kstd::println(kstd::print_sink::stderr, "[OS:CPU] {} @ {:#018x}", context.type, context.instruction_pointer); + switch (context.type) + { + case kapi::cpu::exception::type::page_fault: + return handle_page_fault(context); + default: + return false; + } + } + +} // namespace kapi::cpu
\ No newline at end of file diff --git a/kernel/kapi/interrupts.cpp b/kernel/kapi/interrupts.cpp new file mode 100644 index 0000000..0e37bc3 --- /dev/null +++ b/kernel/kapi/interrupts.cpp @@ -0,0 +1,65 @@ +#include "kapi/interrupts.hpp" + +#include <kstd/flat_map> +#include <kstd/print> +#include <kstd/vector> + +#include <algorithm> +#include <cstdint> + +namespace kapi::interrupts +{ + + namespace + { + auto constinit handlers = kstd::flat_map<std::uint32_t, kstd::vector<handler *>>{}; + } // namespace + + auto register_handler(std::uint32_t irq_number, handler & handler) -> void + { + if (handlers.contains(irq_number)) + { + auto & handler_list = handlers.at(irq_number); + handler_list.push_back(&handler); + } + else + { + handlers.emplace(irq_number, kstd::vector{&handler}); + } + } + + auto unregister_handler(std::uint32_t irq_number, handler & handler) -> void + { + auto & handler_list = handlers.at(irq_number); + auto [first, last] = std::ranges::remove(handler_list, &handler); + handler_list.erase(first, last); + } + + auto dispatch(std::uint32_t irq_number) -> status + { + if (!handlers.contains(irq_number)) + { + kstd::println(kstd::print_sink::stderr, "[OS:interrupts] No handler for IRQ{}", irq_number); + return status::unhandled; + } + + auto & handler_list = handlers.at(irq_number); + + if (handler_list.empty()) + { + kstd::println(kstd::print_sink::stderr, "[OS:interrupts] No handler for IRQ{}", irq_number); + return status::unhandled; + } + + for (auto handler : handler_list) + { + if (handler && handler->handle_interrupt(irq_number) == status::handled) + { + return status::handled; + } + } + + return status::unhandled; + } + +} // namespace kapi::interrupts
\ No newline at end of file diff --git a/kernel/src/main.cpp b/kernel/src/main.cpp index 98c88f2..bb6d57d 100644 --- a/kernel/src/main.cpp +++ b/kernel/src/main.cpp @@ -1,5 +1,7 @@ #include "kapi/boot_modules.hpp" #include "kapi/cio.hpp" +#include "kapi/cpu.hpp" +#include "kapi/interrupts.hpp" #include "kapi/memory.hpp" #include "kapi/system.hpp" @@ -169,6 +171,9 @@ auto main() -> int kapi::cio::init(); kstd::println("[OS] IO subsystem initialized."); + kapi::cpu::init(); + kapi::interrupts::enable(); + kapi::memory::init(); kernel::memory::init_heap(kapi::memory::heap_base); kstd::println("[OS] Memory subsystem initialized."); diff --git a/libs/kstd/CMakeLists.txt b/libs/kstd/CMakeLists.txt index d4f415f..7169aa8 100644 --- a/libs/kstd/CMakeLists.txt +++ b/libs/kstd/CMakeLists.txt @@ -44,6 +44,7 @@ endif() if(NOT CMAKE_CROSSCOMPILING) add_executable("kstd_tests" + "tests/src/flat_map.cpp" "tests/src/vector.cpp" "tests/src/os_panic.cpp" "tests/src/string.cpp" diff --git a/libs/kstd/include/kstd/bits/flat_map.hpp b/libs/kstd/include/kstd/bits/flat_map.hpp new file mode 100644 index 0000000..903841e --- /dev/null +++ b/libs/kstd/include/kstd/bits/flat_map.hpp @@ -0,0 +1,82 @@ +#ifndef KSTD_BITS_FLAT_MAP_HPP +#define KSTD_BITS_FLAT_MAP_HPP + +#include <cstddef> +#include <iterator> +#include <utility> + +namespace kstd::bits +{ + + template<typename KeyType, typename MappedType, typename KeyIterator, typename MappedIterator> + struct flat_map_iterator + { + using iterator_category = std::random_access_iterator_tag; + using value_type = std::pair<KeyType, MappedType>; + using difference_type = std::ptrdiff_t; + using reference = std::pair<KeyType const &, MappedType &>; + using pointer = void; + + constexpr flat_map_iterator(KeyIterator key_iterator, MappedIterator mapped_iterator) + : m_key_iterator{key_iterator} + , m_mapped_iterator{mapped_iterator} + {} + + [[nodiscard]] auto key_iterator() const noexcept -> KeyIterator + { + return m_key_iterator; + } + + [[nodiscard]] constexpr auto operator*() const noexcept -> reference + { + return {*m_key_iterator, *m_mapped_iterator}; + } + + constexpr auto operator++() noexcept -> flat_map_iterator & + { + ++m_key_iterator; + ++m_mapped_iterator; + return *this; + } + + constexpr auto operator++(int) noexcept -> flat_map_iterator + { + auto copy = *this; + ++(*this); + return copy; + } + + constexpr auto operator--() noexcept -> flat_map_iterator & + { + --m_key_iterator; + --m_mapped_iterator; + return *this; + } + + constexpr auto operator--(int) noexcept -> flat_map_iterator + { + auto copy = *this; + --(*this); + return copy; + } + + [[nodiscard]] constexpr auto operator+(difference_type offset) const noexcept -> flat_map_iterator + { + return {m_key_iterator + offset, m_mapped_iterator + offset}; + } + + [[nodiscard]] constexpr auto operator-(flat_map_iterator const & other) const noexcept -> difference_type + { + return m_key_iterator - other.m_key_iterator; + } + + [[nodiscard]] constexpr auto operator<=>(flat_map_iterator const & other) const noexcept = default; + + private: + KeyIterator m_key_iterator{}; + MappedIterator m_mapped_iterator{}; + }; + +} // namespace kstd::bits + +#endif
\ No newline at end of file diff --git a/libs/kstd/include/kstd/flat_map b/libs/kstd/include/kstd/flat_map new file mode 100644 index 0000000..6ffbbcf --- /dev/null +++ b/libs/kstd/include/kstd/flat_map @@ -0,0 +1,320 @@ +#ifndef KSTD_FLAT_MAP_HPP +#define KSTD_FLAT_MAP_HPP + +#include <kstd/bits/flat_map.hpp> +#include <kstd/os/error.hpp> +#include <kstd/vector> + +#include <algorithm> +#include <concepts> +#include <cstddef> +#include <functional> +#include <iterator> +#include <utility> + +namespace kstd +{ + + template<typename KeyType, typename MappedType, typename KeyCompare = std::less<KeyType>, + typename KeyContainerType = kstd::vector<KeyType>, typename MappedContainerType = kstd::vector<MappedType>> + struct flat_map + { + using key_container_type = KeyContainerType; + using mapped_container_type = MappedContainerType; + using key_type = KeyType; + using mapped_type = MappedType; + using value_type = std::pair<key_type, mapped_type>; + using key_compare = KeyCompare; + using reference = std::pair<key_type const &, mapped_type &>; + using const_reference = std::pair<key_type const &, mapped_type const &>; + using size_type = std::size_t; + using difference_type = std::ptrdiff_t; + using iterator = bits::flat_map_iterator<KeyType, MappedType, typename key_container_type::iterator, + typename mapped_container_type::iterator>; + using const_iterator = + bits::flat_map_iterator<KeyType, MappedType const, typename key_container_type::const_iterator, + typename mapped_container_type::const_iterator>; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + using containers = struct + { + key_container_type keys; + mapped_container_type values; + }; + + //! Compare two object of type value_type. + struct value_compare + { + constexpr auto operator()(const_reference lhs, const_reference rhs) const -> bool + { + return lhs.first < rhs.first; + } + }; + + //! Construct an empty flat map. + constexpr flat_map() + : flat_map{key_compare{}} + {} + + //! Construct an empty flat map using the given custom comparator. + //! + //! @param comparator The comparator to use for comparing keys. + constexpr explicit flat_map(key_compare const & comparator) + : m_containers{} + , m_comparator{comparator} + {} + + //! Get a reference to the mapped value associated with the given key. + //! + //! @warning This function will panic if the key is not found. + //! @param key The key to look up. + //! @return A reference to the mapped value. + [[nodiscard]] constexpr auto at(key_type const & key) -> mapped_type & + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key)) + { + auto offset = std::distance(m_containers.keys.begin(), found); + return *(m_containers.values.begin() + offset); + } + os::panic("[kstd::flat_map] Key not found"); + } + + //! Get a reference to the mapped value associated with the given key. + //! + //! @warning This function will panic if the key is not found. + //! @param key The key to look up. + //! @return A const reference to the mapped value. + [[nodiscard]] constexpr auto at(key_type const & key) const -> mapped_type const & + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key)) + { + auto offset = std::distance(m_containers.keys.cbegin(), found); + return *(m_containers.values.cbegin() + offset); + } + os::panic("[kstd::flat_map] Key not found"); + } + + //! Get a reference to the mapped value associated with the given key. + //! + //! @note This overload only participates in overload resolution if the key compare type is transparent. + //! @warning This function will panic if the key is not found. + //! @param x The key to look up. + //! @return A reference to the mapped value. + template<typename K> + requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; } + [[nodiscard]] constexpr auto at(K const & x) -> mapped_type & + { + auto found = find(x); + if (found != end()) + { + auto offset = std::distance(m_containers.keys.begin(), found.key_iterator()); + return *(m_containers.values.begin() + offset); + } + os::panic("[kstd::flat_map] Key not found"); + } + + //! Get a reference to the mapped value associated with the given key. + //! @note This overload only participates in overload resolution if the key compare type is transparent. + //! @warning This function will panic if the key is not found. + //! @param x The key to look up. + //! @return A const reference to the mapped value. + template<typename K> + requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; } + [[nodiscard]] auto at(K const & x) const -> mapped_type const & + { + auto found = find(x); + if (found != end()) + { + auto offset = std::distance(m_containers.keys.cbegin(), found.key_iterator()); + return *(m_containers.values.cbegin() + offset); + } + os::panic("[kstd::flat_map] Key not found"); + } + + //! Get an iterator to the first element. + [[nodiscard]] auto begin() noexcept -> iterator + { + return iterator{m_containers.keys.begin(), m_containers.values.begin()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto begin() const noexcept -> const_iterator + { + return const_iterator{m_containers.keys.cbegin(), m_containers.values.cbegin()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto cbegin() const noexcept -> const_iterator + { + return const_iterator{m_containers.keys.cbegin(), m_containers.values.cbegin()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto end() noexcept -> iterator + { + return iterator{m_containers.keys.end(), m_containers.values.end()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto end() const noexcept -> const_iterator + { + return const_iterator{m_containers.keys.cend(), m_containers.values.cend()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto cend() const noexcept -> const_iterator + { + return const_iterator{m_containers.keys.cend(), m_containers.values.cend()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto rbegin() noexcept -> reverse_iterator + { + return reverse_iterator{end()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto rbegin() const noexcept -> const_reverse_iterator + { + return const_reverse_iterator{cend()}; + } + + //! Get an iterator to the first element. + [[nodiscard]] auto crbegin() const noexcept -> const_reverse_iterator + { + return const_reverse_iterator{cend()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto rend() noexcept -> reverse_iterator + { + return reverse_iterator{begin()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto rend() const noexcept -> const_reverse_iterator + { + return const_reverse_iterator{cbegin()}; + } + + //! Get an iterator to the element past the last element. + [[nodiscard]] auto crend() const noexcept -> const_reverse_iterator + { + return const_reverse_iterator{cbegin()}; + } + + //! Try to insert a new key-value pair into the map. + //! + //! @param args Arguments to use for constructing the key-value pair. + //! @return A pair of an iterator to the inserted element and a boolean indicating whether the insertion took place. + template<typename... Args> + auto emplace(Args &&... args) -> std::pair<iterator, bool> + requires std::constructible_from<value_type, Args...> + { + auto value = value_type{std::forward<Args>(args)...}; + auto found = std::ranges::lower_bound(m_containers.keys, value.first, m_comparator); + + if (found != m_containers.keys.cend() && !m_comparator(value.first, *found) && !m_comparator(*found, value.first)) + { + auto offset = std::distance(m_containers.keys.begin(), found); + return { + iterator{m_containers.keys.begin() + offset, m_containers.values.begin() + offset}, + false + }; + } + + auto offset = std::distance(m_containers.keys.begin(), found); + auto key_iterator = m_containers.keys.begin() + offset; + auto mapped_iterator = m_containers.values.begin() + offset; + + auto inserted_key = m_containers.keys.insert(key_iterator, std::move(value.first)); + auto inserted_mapped = m_containers.values.insert(mapped_iterator, std::move(value.second)); + + return { + iterator{inserted_key, inserted_mapped}, + true + }; + } + + //! Find an element with an equivalent key. + //! + //! @param key The key to look up. + //! @return An iterator to the element with the equivalent key, or end() if no such element is found. + [[nodiscard]] auto find(key_type const & key) noexcept -> iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key)) + { + auto offset = std::distance(m_containers.keys.begin(), found); + return iterator{m_containers.keys.begin() + offset, m_containers.values.begin() + offset}; + } + return end(); + } + + //! Find an element with an equivalent key. + //! + //! @param key The key to look up. + //! @return An iterator to the element with the equivalent key, or end() if no such element is found. + [[nodiscard]] auto find(key_type const & key) const noexcept -> const_iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, key, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(key, *found) && !m_comparator(*found, key)) + { + auto offset = std::distance(m_containers.keys.cbegin(), found); + return const_iterator{m_containers.keys.cbegin() + offset, m_containers.values.cbegin() + offset}; + } + return cend(); + } + + //! Find an element with an equivalent key. + //! @note This overload only participates in overload resolution if the key compare type is transparent. + //! @param x The key to look up. + //! @return An iterator to the element with the equivalent key, or end() if no such element is found. + template<typename K> + requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; } + [[nodiscard]] auto find(K const & x) noexcept -> iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, x, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(x, *found) && !m_comparator(*found, x)) + { + auto offset = std::distance(m_containers.keys.begin(), found); + return iterator{m_containers.keys.begin() + offset, m_containers.values.begin() + offset}; + } + return end(); + } + + //! Find an element with an equivalent key. + //! @note This overload only participates in overload resolution if the key compare type is transparent. + //! @param x The key to look up. + //! @return An iterator to the element with the equivalent key, or end() if no such element is found. + template<typename K> + requires requires(K const & k, key_type const & l) { typename key_compare::is_transparent; } + [[nodiscard]] auto find(K const & x) const noexcept -> const_iterator + { + auto found = std::ranges::lower_bound(m_containers.keys, x, m_comparator); + if (found != m_containers.keys.cend() && !m_comparator(x, *found) && !m_comparator(*found, x)) + { + auto offset = std::distance(m_containers.keys.cbegin(), found); + return const_iterator{m_containers.keys.cbegin() + offset, m_containers.values.cbegin() + offset}; + } + return cend(); + } + + //! Check if the map contains the given key. + //! + //! @param key The key to check. + //! @return true iff. the key is found, false otherwise. + [[nodiscard]] constexpr auto contains(key_type const & key) const noexcept -> bool + { + return find(key) != cend(); + } + + private: + containers m_containers; + key_compare m_comparator; + }; +} // namespace kstd + +#endif
\ No newline at end of file diff --git a/libs/kstd/include/kstd/vector b/libs/kstd/include/kstd/vector index 0d4aac8..9e41cb6 100644 --- a/libs/kstd/include/kstd/vector +++ b/libs/kstd/include/kstd/vector @@ -548,7 +548,6 @@ namespace kstd if (new_capacity > max_size()) { kstd::os::panic("[kstd:vector] Tried to reserve more space than theoretically possible."); - return; } auto new_data = allocate_n(new_capacity); @@ -690,6 +689,50 @@ namespace kstd return begin() + prefix_size; } + //! Erase an element at a given position. + //! + //! @note This function will panic if position == end() + //! + //! @param position An interator pointing to the element to delete + //! @return An iterator pointing to the element after the deleted element + constexpr auto erase(const_iterator position) -> iterator + { + if (position == end()) + { + os::panic("[kstd:vector] Attempted to erase end()!"); + } + + auto prefix_size = std::ranges::distance(cbegin(), position); + + std::ranges::move(begin() + prefix_size + 1, end(), begin() + prefix_size); + std::allocator_traits<allocator_type>::destroy(m_allocator, end() - 1); + --m_size; + + return begin() + prefix_size; + } + + //! Erase a range of elements from this vector. + //! + //! @param first The start of the range to erase. + //! @param last The end of the range to erase. + //! @return An iterator pointing to the element after the last deleted element. + constexpr auto erase(const_iterator first, const_iterator last) -> iterator + { + if (first == last) + { + return begin() + std::ranges::distance(cbegin(), first); + } + + auto prefix_size = std::ranges::distance(cbegin(), first); + auto element_count = std::ranges::distance(first, last); + + std::ranges::move(begin() + prefix_size + element_count, end(), begin() + prefix_size); + destroy_n(end() - element_count, element_count); + m_size -= element_count; + + return begin() + prefix_size; + } + //! Append a given element to this vector via copy construction. constexpr auto push_back(value_type const & value) -> void { diff --git a/libs/kstd/tests/src/flat_map.cpp b/libs/kstd/tests/src/flat_map.cpp new file mode 100644 index 0000000..cde136a --- /dev/null +++ b/libs/kstd/tests/src/flat_map.cpp @@ -0,0 +1,288 @@ +#include <kstd/flat_map> +#include <kstd/tests/os_panic.hpp> + +#include <catch2/catch_test_macros.hpp> + +#include <functional> + +SCENARIO("Flat Map initialization and construction", "[flat_map]") +{ + GIVEN("An empty context") + { + WHEN("constructing by default") + { + auto map = kstd::flat_map<int, int>{}; + + THEN("the Flat Map does not contain elements") + { + REQUIRE_FALSE(map.contains(1)); + } + } + } +} + +SCENARIO("Flat Map modifiers", "[flat_map]") +{ + GIVEN("An empty Flat Map") + { + auto map = kstd::flat_map<int, int>{}; + + WHEN("emplacing a new element") + { + auto [it, inserted] = map.emplace(1, 100); + + THEN("the map contains the new element") + { + REQUIRE(inserted); + REQUIRE(map.contains(1)); + } + } + + WHEN("emplacing an existing element") + { + map.emplace(1, 100); + auto [it, inserted] = map.emplace(1, 200); + + THEN("the map does not insert the duplicate") + { + REQUIRE_FALSE(inserted); + REQUIRE(map.contains(1)); + } + } + } +} + +SCENARIO("Flat Map element access", "[flat_map]") +{ + GIVEN("A populated Flat Map") + { + auto map = kstd::flat_map<int, int>{}; + map.emplace(1, 10); + map.emplace(2, 20); + map.emplace(3, 30); + + WHEN("accessing an existing element with at()") + { + auto & val = map.at(2); + + THEN("it returns a reference to the mapped value") + { + REQUIRE(val == 20); + } + + THEN("the mapped value can be modified") + { + val = 200; + REQUIRE(map.at(2) == 200); + } + } + + WHEN("accessing a non-existent element with at()") + { + THEN("it panics") + { + REQUIRE_THROWS_AS(map.at(4), kstd::tests::os_panic); + } + } + } + + GIVEN("A const populated Flat Map") + { + auto map_builder = kstd::flat_map<int, int>{}; + map_builder.emplace(1, 10); + map_builder.emplace(2, 20); + auto const map = map_builder; + + WHEN("accessing an existing element with const at()") + { + auto const & val = map.at(2); + + THEN("it returns a const reference to the mapped value") + { + REQUIRE(val == 20); + } + } + + WHEN("accessing a non-existent element with const at()") + { + THEN("it panics") + { + REQUIRE_THROWS_AS(map.at(4), kstd::tests::os_panic); + } + } + } +} + +SCENARIO("Flat Map iterators", "[flat_map]") +{ + GIVEN("A populated Flat Map") + { + auto map = kstd::flat_map<int, int>{}; + map.emplace(1, 10); + map.emplace(2, 20); + map.emplace(3, 30); + + WHEN("using forward iterators") + { + THEN("they navigate the elements in the correct forward order") + { + auto it = map.begin(); + REQUIRE(it != map.end()); + REQUIRE((*it).first == 1); + + ++it; + REQUIRE(it != map.end()); + REQUIRE((*it).first == 2); + + ++it; + REQUIRE(it != map.end()); + REQUIRE((*it).first == 3); + + ++it; + REQUIRE(it == map.end()); + } + + THEN("const forward iterators provide correct access") + { + auto it = map.cbegin(); + REQUIRE(it != map.cend()); + REQUIRE((*it).first == 1); + + ++it; + REQUIRE(it != map.cend()); + REQUIRE((*it).first == 2); + + ++it; + REQUIRE(it != map.cend()); + REQUIRE((*it).first == 3); + + ++it; + REQUIRE(it == map.cend()); + } + } + + WHEN("using reverse iterators") + { + THEN("they navigate the elements in the correct reverse order") + { + auto it = map.rbegin(); + REQUIRE(it != map.rend()); + REQUIRE((*it).first == 3); + + ++it; + REQUIRE(it != map.rend()); + REQUIRE((*it).first == 2); + + ++it; + REQUIRE(it != map.rend()); + REQUIRE((*it).first == 1); + + ++it; + REQUIRE(it == map.rend()); + } + + THEN("const reverse iterators provide correct access") + { + auto it = map.crbegin(); + REQUIRE(it != map.crend()); + REQUIRE((*it).first == 3); + + ++it; + REQUIRE(it != map.crend()); + REQUIRE((*it).first == 2); + + ++it; + REQUIRE(it != map.crend()); + REQUIRE((*it).first == 1); + + ++it; + REQUIRE(it == map.crend()); + } + } + } + + GIVEN("an empty Flat Map") + { + auto map = kstd::flat_map<int, int>{}; + + WHEN("getting iterators") + { + THEN("begin() equals end() and cbegin() equals cend()") + { + REQUIRE(map.begin() == map.end()); + REQUIRE(map.cbegin() == map.cend()); + } + + THEN("rbegin() equals rend() and crbegin() equals crend()") + { + REQUIRE(map.rbegin() == map.rend()); + REQUIRE(map.crbegin() == map.crend()); + } + } + } +} + +SCENARIO("Flat Map heterogeneous element access", "[flat_map]") +{ + GIVEN("A populated Flat Map with a transparent comparator") + { + auto map = kstd::flat_map<int, int, std::less<void>>{}; + map.emplace(1, 10); + map.emplace(2, 20); + map.emplace(3, 30); + + WHEN("accessing an existing element with a different key type via at()") + { + long const key = 2L; + auto & val = map.at(key); + + THEN("it returns a reference to the mapped value") + { + REQUIRE(val == 20); + } + + THEN("the mapped value can be modified") + { + val = 200; + REQUIRE(map.at(2L) == 200); + } + } + + WHEN("accessing a non-existent element with a different key type via at()") + { + long const key = 4L; + THEN("it panics") + { + REQUIRE_THROWS_AS(map.at(key), kstd::tests::os_panic); + } + } + } + + GIVEN("A const populated Flat Map with a transparent comparator") + { + auto map_builder = kstd::flat_map<int, int, std::less<void>>{}; + map_builder.emplace(1, 10); + map_builder.emplace(2, 20); + auto const map = map_builder; + + WHEN("accessing an existing element with a different key type via const at()") + { + long const key = 2L; + auto const & val = map.at(key); + + THEN("it returns a const reference to the mapped value") + { + REQUIRE(val == 20); + } + } + + WHEN("accessing a non-existent element with a different key type via const at()") + { + long const key = 4L; + THEN("it panics") + { + REQUIRE_THROWS_AS(map.at(key), kstd::tests::os_panic); + } + } + } +} diff --git a/libs/kstd/tests/src/vector.cpp b/libs/kstd/tests/src/vector.cpp index 0735c9a..b7971f4 100644 --- a/libs/kstd/tests/src/vector.cpp +++ b/libs/kstd/tests/src/vector.cpp @@ -475,6 +475,20 @@ SCENARIO("Vector modifiers", "[vector]") REQUIRE(it == v.begin()); } } + + WHEN("inserting an lvalue element") + { + auto const value = 42; + auto it = v.insert(v.cbegin(), value); + + THEN("the size and capacity increase and the element is inserted") + { + REQUIRE(v.size() == 1); + REQUIRE(v.capacity() >= 1); + REQUIRE(v[0] == 42); + REQUIRE(it == v.begin()); + } + } } GIVEN("A populated vector") @@ -597,6 +611,22 @@ SCENARIO("Vector modifiers", "[vector]") } } + WHEN("inserting an lvalue at the end") + { + auto const value = 40; + auto it = v.insert(v.cend(), value); + + THEN("the element is inserted at the back") + { + REQUIRE(v.size() == 4); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 20); + REQUIRE(v[2] == 30); + REQUIRE(v[3] == 40); + REQUIRE(it == v.begin() + 3); + } + } + WHEN("inserting when capacity is sufficient") { v.reserve(10); @@ -649,6 +679,114 @@ SCENARIO("Vector modifiers", "[vector]") REQUIRE(it == v.begin() + 1); } } + + WHEN("inserting an rvalue reference to an existing element with reallocation") + { + v.shrink_to_fit(); + REQUIRE(v.capacity() == v.size()); + auto it = v.insert(v.cbegin() + 1, std::move(v[2])); + + THEN("the element is correctly moved and inserted") + { + REQUIRE(v.size() == 4); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 30); + REQUIRE(v[2] == 20); + REQUIRE(v[3] == 30); + REQUIRE(it == v.begin() + 1); + } + } + + WHEN("inserting an rvalue reference to an existing element without reallocation") + { + v.reserve(10); + REQUIRE(v.capacity() > v.size()); + auto it = v.insert(v.cbegin() + 1, std::move(v[2])); + + THEN("the element is correctly moved and inserted") + { + REQUIRE(v.size() == 4); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 30); + REQUIRE(v[2] == 20); + REQUIRE(v[3] == 30); + REQUIRE(it == v.begin() + 1); + } + } + + WHEN("erasing the first element") + { + auto it = v.erase(v.cbegin()); + + THEN("the first element is removed and the size decreases") + { + REQUIRE(v.size() == 2); + REQUIRE(v[0] == 20); + REQUIRE(v[1] == 30); + REQUIRE(it == v.begin()); + } + } + + WHEN("erasing a middle element") + { + auto it = v.erase(v.cbegin() + 1); + + THEN("the middle element is removed and the size decreases") + { + REQUIRE(v.size() == 2); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 30); + REQUIRE(it == v.begin() + 1); + } + } + + WHEN("erasing the last element") + { + auto it = v.erase(v.cend() - 1); + + THEN("the last element is removed and the size decreases") + { + REQUIRE(v.size() == 2); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 20); + REQUIRE(it == v.end()); + } + } + + WHEN("erasing the end() iterator") + { + THEN("a panic is triggered") + { + REQUIRE_THROWS_AS(v.erase(v.end()), kstd::tests::os_panic); + } + } + + WHEN("erasing a range of elements") + { + auto it = v.erase(v.cbegin() + 1, v.cend() - 1); + + THEN("the specified range is removed and the size decreases") + { + REQUIRE(v.size() == 2); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 30); + REQUIRE(it == v.begin() + 1); + } + } + + WHEN("erasing an empty range") + { + auto it = v.erase(v.cbegin() + 1, v.cbegin() + 1); + + THEN("the vector is unchanged") + { + REQUIRE(v.size() == 3); + REQUIRE(v[0] == 10); + REQUIRE(v[1] == 20); + REQUIRE(v[2] == 30); + REQUIRE(it == v.begin() + 1); + } + } } } @@ -868,6 +1006,91 @@ SCENARIO("Vector modifier move semantics", "[vector]") REQUIRE(v[3].was_moved); } } + + WHEN("erasing an element in the middle") + { + for (auto & elem : v) + { + elem.was_copied = false; + elem.was_moved = false; + } + + auto it = v.erase(v.cbegin() + 1); + + THEN("the subsequent elements are move-assigned leftwards") + { + REQUIRE(v.size() == 2); + + REQUIRE(v[0].value == 10); + REQUIRE_FALSE(v[0].was_moved); + REQUIRE_FALSE(v[0].was_copied); + + REQUIRE(v[1].value == 30); + REQUIRE(v[1].was_moved); + REQUIRE_FALSE(v[1].was_copied); + + REQUIRE(it == v.begin() + 1); + } + } + + WHEN("erasing the last element") + { + for (auto & elem : v) + { + elem.was_copied = false; + elem.was_moved = false; + } + + auto it = v.erase(v.cend() - 1); + + THEN("no elements are moved, just the last element destroyed") + { + REQUIRE(v.size() == 2); + + REQUIRE(v[0].value == 10); + REQUIRE_FALSE(v[0].was_moved); + REQUIRE_FALSE(v[0].was_copied); + + REQUIRE(v[1].value == 20); + REQUIRE_FALSE(v[1].was_moved); + REQUIRE_FALSE(v[1].was_copied); + + REQUIRE(it == v.end()); + } + } + + WHEN("erasing a range of elements in the middle") + { + v.emplace_back(40); + v.emplace_back(50); + + for (auto & elem : v) + { + elem.was_copied = false; + elem.was_moved = false; + } + + auto it = v.erase(v.cbegin() + 1, v.cbegin() + 3); + + THEN("the specified elements are destroyed and subsequent elements are move-assigned leftwards") + { + REQUIRE(v.size() == 3); + + REQUIRE(v[0].value == 10); + REQUIRE_FALSE(v[0].was_moved); + REQUIRE_FALSE(v[0].was_copied); + + REQUIRE(v[1].value == 40); + REQUIRE(v[1].was_moved); + REQUIRE_FALSE(v[1].was_copied); + + REQUIRE(v[2].value == 50); + REQUIRE(v[2].was_moved); + REQUIRE_FALSE(v[2].was_copied); + + REQUIRE(it == v.begin() + 1); + } + } } } |
