From 2b8e6e7e10f084a9a9ba5c0b79a041f4d1ac459b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= Date: Sat, 15 Mar 2025 11:29:26 +0000 Subject: implement loading of gdtr register --- arch/x86_64/src/memory/heap/linked_list_allocator.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'arch/x86_64/src/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 index a824c8a..5101ab2 100644 --- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp +++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp @@ -11,7 +11,7 @@ namespace teachos::arch::memory::heap : heap_start(heap_start) , heap_end(heap_end) , first(nullptr) - , mutex{shared::mutex{}} + , mutex{stl::mutex{}} { auto const heap_size = heap_end - heap_start; exception_handling::assert( -- cgit v1.2.3 From 5f149faeb9d41bb56733075b0e56908b3731d38d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= Date: Sun, 27 Apr 2025 09:32:59 +0000 Subject: Move gnu function attributes to header file --- arch/x86_64/src/memory/heap/bump_allocator.cpp | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'arch/x86_64/src/memory/heap') diff --git a/arch/x86_64/src/memory/heap/bump_allocator.cpp b/arch/x86_64/src/memory/heap/bump_allocator.cpp index df95346..525f45c 100644 --- a/arch/x86_64/src/memory/heap/bump_allocator.cpp +++ b/arch/x86_64/src/memory/heap/bump_allocator.cpp @@ -24,11 +24,13 @@ namespace teachos::arch::memory::heap auto bump_allocator::allocate(std::size_t size) -> void * { + // Reading the value only has to be done once, because compare_exchange_weak updates the value as well if the + // exchange failed, becuase the value was not the expected one. + auto alloc_start = next.load(std::memory_order::relaxed); // 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 -- cgit v1.2.3 From be32189323ba8c46091d6deaf091cf41147426b4 Mon Sep 17 00:00:00 2001 From: Fabian Imhof Date: Wed, 7 May 2025 14:06:25 +0000 Subject: wip custom heap allocation functions for user mode --- .../src/memory/heap/global_heap_allocator.cpp | 54 +++++++++++++++------- 1 file changed, 37 insertions(+), 17 deletions(-) (limited to 'arch/x86_64/src/memory/heap') diff --git a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp index c1ca160..51f6261 100644 --- a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp +++ b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp @@ -6,15 +6,20 @@ namespace teachos::arch::memory::heap { - heap_allocator * global_heap_allocator::allocator_instance = nullptr; + heap_allocator * global_heap_allocator::kernel_allocator_instance = nullptr; + heap_allocator * global_heap_allocator::user_allocator_instance = nullptr; - auto global_heap_allocator::allocate(std::size_t size) -> void * { return get().allocate(size); } + auto global_heap_allocator::kmalloc(std::size_t size) -> void * { return kernel().allocate(size); } - auto global_heap_allocator::deallocate(void * pointer) noexcept -> void { get().deallocate(pointer); } + auto global_heap_allocator::kfree(void * pointer) noexcept -> void { kernel().deallocate(pointer); } + + auto global_heap_allocator::malloc(std::size_t size) -> void * { return user().allocate(size); } + + auto global_heap_allocator::free(void * pointer) noexcept -> void { user().deallocate(pointer); } auto global_heap_allocator::register_heap_allocator(heap_allocator_type new_type) -> void { - exception_handling::assert(allocator_instance == nullptr, + exception_handling::assert(kernel_allocator_instance == nullptr, "Calling register_heap_allocator_type can only be done once."); switch (new_type) @@ -23,56 +28,71 @@ namespace teachos::arch::memory::heap // Nothing to do break; case heap_allocator_type::BUMP: { - static bump_allocator allocator{HEAP_START, HEAP_START + HEAP_SIZE}; - allocator_instance = &allocator; + static bump_allocator kernel_allocator{KERNEL_HEAP_START, KERNEL_HEAP_START + KERNEL_HEAP_SIZE}; + kernel_allocator_instance = &kernel_allocator; + + static bump_allocator user_allocator{USER_HEAP_START, USER_HEAP_START + USER_HEAP_SIZE}; + user_allocator_instance = &user_allocator; break; } case heap_allocator_type::LINKED_LIST: { - static linked_list_allocator allocator{HEAP_START, HEAP_START + HEAP_SIZE}; - allocator_instance = &allocator; + static linked_list_allocator kernel_allocator{KERNEL_HEAP_START, KERNEL_HEAP_START + KERNEL_HEAP_SIZE}; + kernel_allocator_instance = &kernel_allocator; + + static linked_list_allocator user_allocator{USER_HEAP_START, USER_HEAP_START + USER_HEAP_SIZE}; + user_allocator_instance = &user_allocator; break; } } } - auto global_heap_allocator::get() -> heap_allocator & + auto global_heap_allocator::kernel() -> heap_allocator & + { + exception_handling::assert(kernel_allocator_instance != nullptr, + "Attempted to allocate or deallocate using the global_heap_allocator before " + "register_heap_allocation_type was called."); + + return *kernel_allocator_instance; + } + + auto global_heap_allocator::user() -> heap_allocator & { - exception_handling::assert(allocator_instance != nullptr, + exception_handling::assert(user_allocator_instance != nullptr, "Attempted to allocate or deallocate using the global_heap_allocator before " "register_heap_allocation_type was called."); - return *allocator_instance; + return *user_allocator_instance; } } // namespace teachos::arch::memory::heap auto operator new(std::size_t size) -> void * { - return teachos::arch::memory::heap::global_heap_allocator::allocate(size); + return teachos::arch::memory::heap::global_heap_allocator::kmalloc(size); } auto operator delete(void * pointer) noexcept -> void { - teachos::arch::memory::heap::global_heap_allocator::deallocate(pointer); + teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); } auto operator delete(void * pointer, std::size_t size) noexcept -> void { (void)size; - teachos::arch::memory::heap::global_heap_allocator::deallocate(pointer); + teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); } auto operator new[](std::size_t size) -> void * { - return teachos::arch::memory::heap::global_heap_allocator::allocate(size); + return teachos::arch::memory::heap::global_heap_allocator::kmalloc(size); } auto operator delete[](void * pointer) noexcept -> void { - teachos::arch::memory::heap::global_heap_allocator::deallocate(pointer); + teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); } auto operator delete[](void * pointer, std::size_t size) noexcept -> void { (void)size; - teachos::arch::memory::heap::global_heap_allocator::deallocate(pointer); + teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); } -- cgit v1.2.3 From 0b62fdb3fe657d056a42d7567b67951ba3468738 Mon Sep 17 00:00:00 2001 From: Fabian Imhof Date: Thu, 8 May 2025 08:51:52 +0000 Subject: wip allocating heap memory in user mode --- .../src/memory/heap/global_heap_allocator.cpp | 20 ++++---- .../x86_64/src/memory/heap/user_heap_allocator.cpp | 55 ++++++++++++++++++++++ 2 files changed, 64 insertions(+), 11 deletions(-) create mode 100644 arch/x86_64/src/memory/heap/user_heap_allocator.cpp (limited to 'arch/x86_64/src/memory/heap') diff --git a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp index 51f6261..acba02d 100644 --- a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp +++ b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp @@ -3,11 +3,12 @@ #include "arch/exception_handling/assert.hpp" #include "arch/memory/heap/bump_allocator.hpp" #include "arch/memory/heap/linked_list_allocator.hpp" +#include "arch/memory/heap/user_heap_allocator.hpp" namespace teachos::arch::memory::heap { heap_allocator * global_heap_allocator::kernel_allocator_instance = nullptr; - heap_allocator * global_heap_allocator::user_allocator_instance = nullptr; + user_heap_allocator * global_heap_allocator::user_allocator_instance = nullptr; auto global_heap_allocator::kmalloc(std::size_t size) -> void * { return kernel().allocate(size); } @@ -30,20 +31,17 @@ namespace teachos::arch::memory::heap case heap_allocator_type::BUMP: { static bump_allocator kernel_allocator{KERNEL_HEAP_START, KERNEL_HEAP_START + KERNEL_HEAP_SIZE}; kernel_allocator_instance = &kernel_allocator; - - static bump_allocator user_allocator{USER_HEAP_START, USER_HEAP_START + USER_HEAP_SIZE}; - user_allocator_instance = &user_allocator; break; } case heap_allocator_type::LINKED_LIST: { static linked_list_allocator kernel_allocator{KERNEL_HEAP_START, KERNEL_HEAP_START + KERNEL_HEAP_SIZE}; kernel_allocator_instance = &kernel_allocator; - - static linked_list_allocator user_allocator{USER_HEAP_START, USER_HEAP_START + USER_HEAP_SIZE}; - user_allocator_instance = &user_allocator; break; } } + + static user_heap_allocator user_allocator{USER_HEAP_START, USER_HEAP_START + USER_HEAP_SIZE}; + user_allocator_instance = &user_allocator; } auto global_heap_allocator::kernel() -> heap_allocator & @@ -55,11 +53,11 @@ namespace teachos::arch::memory::heap return *kernel_allocator_instance; } - auto global_heap_allocator::user() -> heap_allocator & + auto global_heap_allocator::user() -> user_heap_allocator & { - exception_handling::assert(user_allocator_instance != nullptr, - "Attempted to allocate or deallocate using the global_heap_allocator before " - "register_heap_allocation_type was called."); + // exception_handling::assert(user_allocator_instance != nullptr, + // "Attempted to allocate or deallocate using the global_heap_allocator before " + // "register_heap_allocation_type was called."); return *user_allocator_instance; } diff --git a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp new file mode 100644 index 0000000..f09811d --- /dev/null +++ b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp @@ -0,0 +1,55 @@ +#include "arch/memory/heap/user_heap_allocator.hpp" + +#include "arch/exception_handling/assert.hpp" + +#include +#include + +namespace teachos::arch::memory::heap +{ + namespace + { + template + [[gnu::section(".user_text")]] + auto saturating_add(T x, T y) -> T + requires std::is_unsigned_v + { + if (x > std::numeric_limits::max() - y) + { + return std::numeric_limits::max(); + } + T result = x + y; + return result; + } + } // namespace + + auto user_heap_allocator::allocate(std::size_t size) -> void * + { + // Reading the value only has to be done once, because compare_exchange_weak updates the value as well if the + // exchange failed, becuase the value was not the expected one. + auto alloc_start = next.load(std::memory_order::relaxed); + // 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 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(alloc_start); + } + } + } + + auto user_heap_allocator::deallocate(void * pointer) noexcept -> void + { + if (pointer) + { + } + } + +} // namespace teachos::arch::memory::heap -- cgit v1.2.3 From d80ecf29baada6242c5181adaec0d1500707cad0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= Date: Fri, 9 May 2025 12:00:23 +0000 Subject: Move necessary code into user text --- arch/x86_64/src/memory/heap/global_heap_allocator.cpp | 3 +++ arch/x86_64/src/memory/heap/user_heap_allocator.cpp | 5 ++++- 2 files changed, 7 insertions(+), 1 deletion(-) (limited to 'arch/x86_64/src/memory/heap') diff --git a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp index acba02d..23e2458 100644 --- a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp +++ b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp @@ -40,6 +40,7 @@ namespace teachos::arch::memory::heap } } + [[gnu::section(".user_data")]] static user_heap_allocator user_allocator{USER_HEAP_START, USER_HEAP_START + USER_HEAP_SIZE}; user_allocator_instance = &user_allocator; } @@ -55,6 +56,8 @@ namespace teachos::arch::memory::heap auto global_heap_allocator::user() -> user_heap_allocator & { + // TODO: Assert Method does not exist in .user_text meaning this causes a Page Fault when accessed, Make it into a + // syscall instead // exception_handling::assert(user_allocator_instance != nullptr, // "Attempted to allocate or deallocate using the global_heap_allocator before " // "register_heap_allocation_type was called."); diff --git a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp index f09811d..eefcab5 100644 --- a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp +++ b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp @@ -25,7 +25,10 @@ namespace teachos::arch::memory::heap auto user_heap_allocator::allocate(std::size_t size) -> void * { - // Reading the value only has to be done once, because compare_exchange_weak updates the value as well if the + // TODO: .load() crashes because it is only in the kernel .text section and not the user one? How would you fix + // Similarly assert cause a crash here it is easier though simply create a syscall for the assert method. + + // that? Reading the value only has to be done once, because compare_exchange_weak updates the value as well if the // exchange failed, becuase the value was not the expected one. auto alloc_start = next.load(std::memory_order::relaxed); // Repeat allocation until it succeeds, has to be done, because another allocator could overtake it at any time -- cgit v1.2.3 From a5812be4fa8ecc208219682204b14969d7b718b0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= Date: Fri, 9 May 2025 13:15:58 +0000 Subject: Switch uer heap to linked list allocator --- .../x86_64/src/memory/heap/user_heap_allocator.cpp | 186 +++++++++++++++++---- 1 file changed, 154 insertions(+), 32 deletions(-) (limited to 'arch/x86_64/src/memory/heap') diff --git a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp index eefcab5..6843d66 100644 --- a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp +++ b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp @@ -1,58 +1,180 @@ #include "arch/memory/heap/user_heap_allocator.hpp" #include "arch/exception_handling/assert.hpp" +#include "arch/exception_handling/panic.hpp" -#include -#include +#include namespace teachos::arch::memory::heap { - namespace + user_heap_allocator::user_heap_allocator(std::size_t heap_start, std::size_t heap_end) + : heap_start(heap_start) + , heap_end(heap_end) + , first(nullptr) + , mutex{stl::mutex{}} { - template - [[gnu::section(".user_text")]] - auto saturating_add(T x, T y) -> T - requires std::is_unsigned_v + 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(heap_start)) memory_block(heap_size, nullptr); + } + + auto user_heap_allocator::allocate(std::size_t size) -> void * + { + // Add size of size_t to the total allocated size, because we add a header that includes the size of the allocated + // block, to allow for deallocation without the need to call with the corresponding size + auto const total_size = size + sizeof(std::size_t); + mutex.lock(); + + memory_block * previous = nullptr; + auto current = first; + + while (current != nullptr) { - if (x > std::numeric_limits::max() - y) + // TODO: Can not access current pointer. Results in a General Protection Fault? + if (current->size == total_size) { - return std::numeric_limits::max(); + auto const memory_address = remove_free_memory_block(previous, current); + new (memory_address) std::size_t(total_size); + mutex.unlock(); + return reinterpret_cast(reinterpret_cast(memory_address) + sizeof(std::size_t)); } - T result = x + y; - return result; + else if (current->size >= total_size + min_allocatable_size()) + { + // Ensure that the allocated size block is atleast 16 bytes (required because if we free the hole afterwards + // there needs to be enough space for a memory block). Therefore we allocate more than is actually required if + // the total size was less and simply deallocate it as well + auto const max_size = std::max(total_size, min_allocatable_size()); + auto const memory_address = split_free_memory_block(previous, current, max_size); + new (memory_address) std::size_t(max_size); + mutex.unlock(); + return reinterpret_cast(reinterpret_cast(memory_address) + sizeof(std::size_t)); + } + + previous = current; + current = current->next; } - } // namespace - auto user_heap_allocator::allocate(std::size_t size) -> void * + exception_handling::panic("[Linked List Allocator] Out of memory"); + } + + auto user_heap_allocator::deallocate(void * pointer) noexcept -> void { - // TODO: .load() crashes because it is only in the kernel .text section and not the user one? How would you fix - // Similarly assert cause a crash here it is easier though simply create a syscall for the assert method. - - // that? Reading the value only has to be done once, because compare_exchange_weak updates the value as well if the - // exchange failed, becuase the value was not the expected one. - auto alloc_start = next.load(std::memory_order::relaxed); - // 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 (;;) + mutex.lock(); + + // Read configured header size of the complete allocated block + auto const header_pointer = reinterpret_cast(reinterpret_cast(pointer) - sizeof(std::size_t)); + auto const total_size = *reinterpret_cast(header_pointer); + + auto const start_address = reinterpret_cast(header_pointer); + auto const end_address = start_address + total_size; + + memory_block * previous = nullptr; + auto current = first; + + while (current != nullptr) { - 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) + // 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(current) >= end_address) { - return reinterpret_cast(alloc_start); + break; } + + previous = current; + current = current->next; } + + coalesce_free_memory_block(previous, current, header_pointer, total_size); + mutex.unlock(); } - auto user_heap_allocator::deallocate(void * pointer) noexcept -> void + auto user_heap_allocator::remove_free_memory_block(memory_block * previous_block, memory_block * current_block) + -> void * { - if (pointer) + return replace_free_memory_block(previous_block, current_block, current_block->next); + } + + auto user_heap_allocator::split_free_memory_block(memory_block * previous_block, memory_block * current_block, + std::size_t size) -> void * + { + auto const end_address = reinterpret_cast(current_block) + size; + auto const new_block = + new (reinterpret_cast(end_address)) memory_block(current_block->size - size, current_block->next); + return replace_free_memory_block(previous_block, current_block, new_block); + } + + auto user_heap_allocator::replace_free_memory_block(memory_block * previous_block, memory_block * current_block, + memory_block * new_block) -> void * + { + auto const start_address = reinterpret_cast(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(start_address); + } + + auto user_heap_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(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(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(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(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 -- cgit v1.2.3 From 833cd6446d9981a262959749c0e248e33b54c174 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= Date: Sun, 11 May 2025 08:48:57 +0000 Subject: Adjust user heap allocator with expanding heap functionality --- .../x86_64/src/memory/heap/user_heap_allocator.cpp | 41 +++++++++++++++++++++- 1 file changed, 40 insertions(+), 1 deletion(-) (limited to 'arch/x86_64/src/memory/heap') diff --git a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp index 6843d66..ce8b0fa 100644 --- a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp +++ b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp @@ -1,5 +1,6 @@ #include "arch/memory/heap/user_heap_allocator.hpp" +#include "arch/context_switching/syscall/main.hpp" #include "arch/exception_handling/assert.hpp" #include "arch/exception_handling/panic.hpp" @@ -18,7 +19,7 @@ namespace teachos::arch::memory::heap 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(heap_start)) memory_block(heap_size, nullptr); + // first = new (reinterpret_cast(heap_start)) memory_block(heap_size, nullptr); } auto user_heap_allocator::allocate(std::size_t size) -> void * @@ -57,6 +58,30 @@ namespace teachos::arch::memory::heap current = current->next; } + current = expand_heap_if_full(); + + if (current != nullptr) + { + if (current->size == total_size) + { + auto const memory_address = remove_free_memory_block(previous, current); + new (memory_address) std::size_t(total_size); + mutex.unlock(); + return reinterpret_cast(reinterpret_cast(memory_address) + sizeof(std::size_t)); + } + else if (current->size >= total_size + min_allocatable_size()) + { + // Ensure that the allocated size block is atleast 16 bytes (required because if we free the hole afterwards + // there needs to be enough space for a memory block). Therefore we allocate more than is actually required if + // the total size was less and simply deallocate it as well + auto const max_size = std::max(total_size, min_allocatable_size()); + auto const memory_address = split_free_memory_block(previous, current, max_size); + new (memory_address) std::size_t(max_size); + mutex.unlock(); + return reinterpret_cast(reinterpret_cast(memory_address) + sizeof(std::size_t)); + } + } + exception_handling::panic("[Linked List Allocator] Out of memory"); } @@ -91,6 +116,20 @@ namespace teachos::arch::memory::heap mutex.unlock(); } + auto user_heap_allocator::expand_heap_if_full() -> memory_block * + { + context_switching::syscall::arguments args{}; + auto const result = context_switching::syscall::syscall(context_switching::syscall::type::EXPAND_HEAP, args); + + if (!result.error_code) + { + uint64_t const heap_start = result.values.arg_0; + uint64_t const heap_size = result.values.arg_1; + return new (reinterpret_cast(heap_start)) memory_block(heap_size, nullptr); + } + return nullptr; + } + auto user_heap_allocator::remove_free_memory_block(memory_block * previous_block, memory_block * current_block) -> void * { -- cgit v1.2.3 From ef156dd6430855434b54275b22cd43ee3cedcfdc Mon Sep 17 00:00:00 2001 From: Fabian Imhof Date: Sun, 11 May 2025 09:29:56 +0000 Subject: make frame_allocator and active_page_table statically available --- arch/x86_64/src/memory/heap/memory_block.cpp | 1 + 1 file changed, 1 insertion(+) (limited to 'arch/x86_64/src/memory/heap') diff --git a/arch/x86_64/src/memory/heap/memory_block.cpp b/arch/x86_64/src/memory/heap/memory_block.cpp index 446cd96..9f1fea8 100644 --- a/arch/x86_64/src/memory/heap/memory_block.cpp +++ b/arch/x86_64/src/memory/heap/memory_block.cpp @@ -6,6 +6,7 @@ namespace teachos::arch::memory::heap { memory_block::memory_block(std::size_t size, memory_block * next) { + // TODO: Figure out why this memset fails memset(static_cast(this), 0, size); this->size = size; this->next = next; -- cgit v1.2.3 From ee4c61f7313fedd23d01c69ea5036fa38ef6248a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= Date: Mon, 12 May 2025 08:50:12 +0000 Subject: Adjust user heap to lazy allocate heap --- arch/x86_64/src/memory/heap/global_heap_allocator.cpp | 2 +- arch/x86_64/src/memory/heap/linked_list_allocator.cpp | 4 +--- arch/x86_64/src/memory/heap/memory_block.cpp | 4 ++-- arch/x86_64/src/memory/heap/user_heap_allocator.cpp | 14 -------------- 4 files changed, 4 insertions(+), 20 deletions(-) (limited to 'arch/x86_64/src/memory/heap') diff --git a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp index 23e2458..e6c268a 100644 --- a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp +++ b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp @@ -41,7 +41,7 @@ namespace teachos::arch::memory::heap } [[gnu::section(".user_data")]] - static user_heap_allocator user_allocator{USER_HEAP_START, USER_HEAP_START + USER_HEAP_SIZE}; + static user_heap_allocator user_allocator{}; user_allocator_instance = &user_allocator; } diff --git a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp index 5101ab2..63a6111 100644 --- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp +++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp @@ -8,9 +8,7 @@ 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) + : first(nullptr) , mutex{stl::mutex{}} { auto const heap_size = heap_end - heap_start; diff --git a/arch/x86_64/src/memory/heap/memory_block.cpp b/arch/x86_64/src/memory/heap/memory_block.cpp index 9f1fea8..6ee675a 100644 --- a/arch/x86_64/src/memory/heap/memory_block.cpp +++ b/arch/x86_64/src/memory/heap/memory_block.cpp @@ -7,10 +7,10 @@ namespace teachos::arch::memory::heap memory_block::memory_block(std::size_t size, memory_block * next) { // TODO: Figure out why this memset fails - memset(static_cast(this), 0, size); + // memset(static_cast(this), 0, size); this->size = size; this->next = next; } - memory_block::~memory_block() { memset(static_cast(this), 0, sizeof(memory_block)); } + memory_block::~memory_block() { /*memset(static_cast(this), 0, sizeof(memory_block));*/ } } // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp index ce8b0fa..9cb6c17 100644 --- a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp +++ b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp @@ -8,20 +8,6 @@ namespace teachos::arch::memory::heap { - user_heap_allocator::user_heap_allocator(std::size_t heap_start, std::size_t heap_end) - : heap_start(heap_start) - , heap_end(heap_end) - , first(nullptr) - , mutex{stl::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(heap_start)) memory_block(heap_size, nullptr); - } - auto user_heap_allocator::allocate(std::size_t size) -> void * { // Add size of size_t to the total allocated size, because we add a header that includes the size of the allocated -- cgit v1.2.3 From 29e067867e7a437d12351b481024d4bab431b202 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= Date: Mon, 12 May 2025 13:51:12 +0000 Subject: Fix crashes because of are frame allocator copy --- arch/x86_64/src/memory/heap/memory_block.cpp | 5 ++--- arch/x86_64/src/memory/heap/user_heap_allocator.cpp | 13 ++++--------- 2 files changed, 6 insertions(+), 12 deletions(-) (limited to 'arch/x86_64/src/memory/heap') diff --git a/arch/x86_64/src/memory/heap/memory_block.cpp b/arch/x86_64/src/memory/heap/memory_block.cpp index 6ee675a..bc97bd6 100644 --- a/arch/x86_64/src/memory/heap/memory_block.cpp +++ b/arch/x86_64/src/memory/heap/memory_block.cpp @@ -6,11 +6,10 @@ namespace teachos::arch::memory::heap { memory_block::memory_block(std::size_t size, memory_block * next) { - // TODO: Figure out why this memset fails - // memset(static_cast(this), 0, size); + memset(static_cast(this), 0U, size); this->size = size; this->next = next; } - memory_block::~memory_block() { /*memset(static_cast(this), 0, sizeof(memory_block));*/ } + memory_block::~memory_block() { memset(static_cast(this), 0U, sizeof(memory_block)); } } // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp index 9cb6c17..f3fe1c2 100644 --- a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp +++ b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp @@ -104,16 +104,11 @@ namespace teachos::arch::memory::heap auto user_heap_allocator::expand_heap_if_full() -> memory_block * { - context_switching::syscall::arguments args{}; - auto const result = context_switching::syscall::syscall(context_switching::syscall::type::EXPAND_HEAP, args); + auto const result = context_switching::syscall::syscall(context_switching::syscall::type::EXPAND_HEAP); - if (!result.error_code) - { - uint64_t const heap_start = result.values.arg_0; - uint64_t const heap_size = result.values.arg_1; - return new (reinterpret_cast(heap_start)) memory_block(heap_size, nullptr); - } - return nullptr; + uint64_t const heap_start = result.values.arg_0; + uint64_t const heap_size = result.values.arg_1; + return !result.error_code ? new (reinterpret_cast(heap_start)) memory_block(heap_size, nullptr) : nullptr; } auto user_heap_allocator::remove_free_memory_block(memory_block * previous_block, memory_block * current_block) -- cgit v1.2.3 From 8d39f3f67734bf39cada370c39243e6ef33bf4a0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= Date: Sun, 18 May 2025 14:45:05 +0000 Subject: Make new usable for both kernel and user calls --- .../src/memory/heap/global_heap_allocator.cpp | 66 +++++++++++++++++----- 1 file changed, 51 insertions(+), 15 deletions(-) (limited to 'arch/x86_64/src/memory/heap') diff --git a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp index e6c268a..35cd623 100644 --- a/arch/x86_64/src/memory/heap/global_heap_allocator.cpp +++ b/arch/x86_64/src/memory/heap/global_heap_allocator.cpp @@ -1,12 +1,29 @@ #include "arch/memory/heap/global_heap_allocator.hpp" +#include "arch/context_switching/syscall/main.hpp" #include "arch/exception_handling/assert.hpp" +#include "arch/kernel/cpu/segment_register.hpp" #include "arch/memory/heap/bump_allocator.hpp" #include "arch/memory/heap/linked_list_allocator.hpp" #include "arch/memory/heap/user_heap_allocator.hpp" namespace teachos::arch::memory::heap { + namespace + { + constexpr char NOT_REGISTRED_ERROR_MESSAGE[] = + "Attempted to allocate or deallocate using the global_heap_allocator before " + "register_heap_allocation_type was called."; + constexpr uint16_t KERNEL_CODE_INDEX = 1U; + + [[gnu::section(".user_text")]] + auto os_in_kernel_mode() -> bool + { + auto const cs = teachos::arch::kernel::cpu::read_code_segment_register(); + return cs.get_index() == KERNEL_CODE_INDEX; + } + } // namespace + heap_allocator * global_heap_allocator::kernel_allocator_instance = nullptr; user_heap_allocator * global_heap_allocator::user_allocator_instance = nullptr; @@ -47,53 +64,72 @@ namespace teachos::arch::memory::heap auto global_heap_allocator::kernel() -> heap_allocator & { - exception_handling::assert(kernel_allocator_instance != nullptr, - "Attempted to allocate or deallocate using the global_heap_allocator before " - "register_heap_allocation_type was called."); + exception_handling::assert(kernel_allocator_instance != nullptr, NOT_REGISTRED_ERROR_MESSAGE); return *kernel_allocator_instance; } auto global_heap_allocator::user() -> user_heap_allocator & { - // TODO: Assert Method does not exist in .user_text meaning this causes a Page Fault when accessed, Make it into a - // syscall instead - // exception_handling::assert(user_allocator_instance != nullptr, - // "Attempted to allocate or deallocate using the global_heap_allocator before " - // "register_heap_allocation_type was called."); - + context_switching::syscall::syscall( + context_switching::syscall::type::ASSERT, + {user_allocator_instance != nullptr, reinterpret_cast(&NOT_REGISTRED_ERROR_MESSAGE)}); return *user_allocator_instance; } } // namespace teachos::arch::memory::heap auto operator new(std::size_t size) -> void * { - return teachos::arch::memory::heap::global_heap_allocator::kmalloc(size); + if (teachos::arch::memory::heap::os_in_kernel_mode()) + { + return teachos::arch::memory::heap::global_heap_allocator::kmalloc(size); + } + return teachos::arch::memory::heap::global_heap_allocator::malloc(size); } auto operator delete(void * pointer) noexcept -> void { - teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); + if (teachos::arch::memory::heap::os_in_kernel_mode()) + { + teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); + } + teachos::arch::memory::heap::global_heap_allocator::free(pointer); } auto operator delete(void * pointer, std::size_t size) noexcept -> void { (void)size; - teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); + if (teachos::arch::memory::heap::os_in_kernel_mode()) + { + teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); + } + teachos::arch::memory::heap::global_heap_allocator::free(pointer); } auto operator new[](std::size_t size) -> void * { - return teachos::arch::memory::heap::global_heap_allocator::kmalloc(size); + if (teachos::arch::memory::heap::os_in_kernel_mode()) + { + return teachos::arch::memory::heap::global_heap_allocator::kmalloc(size); + } + return teachos::arch::memory::heap::global_heap_allocator::malloc(size); } auto operator delete[](void * pointer) noexcept -> void { - teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); + if (teachos::arch::memory::heap::os_in_kernel_mode()) + { + teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); + } + teachos::arch::memory::heap::global_heap_allocator::free(pointer); } auto operator delete[](void * pointer, std::size_t size) noexcept -> void { (void)size; - teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); + if (teachos::arch::memory::heap::os_in_kernel_mode()) + { + teachos::arch::memory::heap::global_heap_allocator::kfree(pointer); + } + teachos::arch::memory::heap::global_heap_allocator::free(pointer); } -- cgit v1.2.3 From 8a6a9a3a159ce1b960721eb921b8e8d81b15b718 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Matteo=20Gm=C3=BCr?= Date: Tue, 20 May 2025 12:29:09 +0000 Subject: Improve syscalls and user heap allocator --- .../x86_64/src/memory/heap/user_heap_allocator.cpp | 80 +++++++++++----------- 1 file changed, 40 insertions(+), 40 deletions(-) (limited to 'arch/x86_64/src/memory/heap') diff --git a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp index f3fe1c2..427a68a 100644 --- a/arch/x86_64/src/memory/heap/user_heap_allocator.cpp +++ b/arch/x86_64/src/memory/heap/user_heap_allocator.cpp @@ -1,8 +1,6 @@ #include "arch/memory/heap/user_heap_allocator.hpp" #include "arch/context_switching/syscall/main.hpp" -#include "arch/exception_handling/assert.hpp" -#include "arch/exception_handling/panic.hpp" #include @@ -20,24 +18,10 @@ namespace teachos::arch::memory::heap while (current != nullptr) { - // TODO: Can not access current pointer. Results in a General Protection Fault? - if (current->size == total_size) + auto memory = allocate_into_memory_block_if_big_enough(current, previous, total_size); + if (memory.has_value()) { - auto const memory_address = remove_free_memory_block(previous, current); - new (memory_address) std::size_t(total_size); - mutex.unlock(); - return reinterpret_cast(reinterpret_cast(memory_address) + sizeof(std::size_t)); - } - else if (current->size >= total_size + min_allocatable_size()) - { - // Ensure that the allocated size block is atleast 16 bytes (required because if we free the hole afterwards - // there needs to be enough space for a memory block). Therefore we allocate more than is actually required if - // the total size was less and simply deallocate it as well - auto const max_size = std::max(total_size, min_allocatable_size()); - auto const memory_address = split_free_memory_block(previous, current, max_size); - new (memory_address) std::size_t(max_size); - mutex.unlock(); - return reinterpret_cast(reinterpret_cast(memory_address) + sizeof(std::size_t)); + return memory.value(); } previous = current; @@ -48,27 +32,17 @@ namespace teachos::arch::memory::heap if (current != nullptr) { - if (current->size == total_size) - { - auto const memory_address = remove_free_memory_block(previous, current); - new (memory_address) std::size_t(total_size); - mutex.unlock(); - return reinterpret_cast(reinterpret_cast(memory_address) + sizeof(std::size_t)); - } - else if (current->size >= total_size + min_allocatable_size()) + auto memory = allocate_into_memory_block_if_big_enough(current, previous, total_size); + if (memory.has_value()) { - // Ensure that the allocated size block is atleast 16 bytes (required because if we free the hole afterwards - // there needs to be enough space for a memory block). Therefore we allocate more than is actually required if - // the total size was less and simply deallocate it as well - auto const max_size = std::max(total_size, min_allocatable_size()); - auto const memory_address = split_free_memory_block(previous, current, max_size); - new (memory_address) std::size_t(max_size); - mutex.unlock(); - return reinterpret_cast(reinterpret_cast(memory_address) + sizeof(std::size_t)); + return memory.value(); } } - exception_handling::panic("[Linked List Allocator] Out of memory"); + char constexpr OUT_OF_MEMORY_ERROR_MESSAGE[] = "[Linked List Allocator] Out of memory"; + context_switching::syscall::syscall(context_switching::syscall::type::ASSERT, + {false, reinterpret_cast(&OUT_OF_MEMORY_ERROR_MESSAGE)}); + return nullptr; } auto user_heap_allocator::deallocate(void * pointer) noexcept -> void @@ -102,6 +76,30 @@ namespace teachos::arch::memory::heap mutex.unlock(); } + auto user_heap_allocator::allocate_into_memory_block_if_big_enough(memory_block * current, memory_block * previous, + std::size_t total_size) -> std::optional + { + if (current->size == total_size) + { + auto const memory_address = remove_free_memory_block(previous, current); + new (memory_address) std::size_t(total_size); + mutex.unlock(); + return reinterpret_cast(reinterpret_cast(memory_address) + sizeof(std::size_t)); + } + else if (current->size >= total_size + min_allocatable_size()) + { + // Ensure that the allocated size block is atleast 16 bytes (required because if we free the hole afterwards + // there needs to be enough space for a memory block). Therefore we allocate more than is actually required if + // the total size was less and simply deallocate it as well + auto const max_size = std::max(total_size, min_allocatable_size()); + auto const memory_address = split_free_memory_block(previous, current, max_size); + new (memory_address) std::size_t(max_size); + mutex.unlock(); + return reinterpret_cast(reinterpret_cast(memory_address) + sizeof(std::size_t)); + } + return std::nullopt; + } + auto user_heap_allocator::expand_heap_if_full() -> memory_block * { auto const result = context_switching::syscall::syscall(context_switching::syscall::type::EXPAND_HEAP); @@ -180,10 +178,12 @@ namespace teachos::arch::memory::heap // 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(previous_block) + previous_block->size), - "[Linked List Allocator] Attempted double free detected"); + char constexpr DOUBLE_FREE_ERROR_MESSAGE[] = "[Linked List Allocator] Attempted double free detected"; + context_switching::syscall::syscall( + context_switching::syscall::type::ASSERT, + {previous_block == nullptr || + start_address >= (reinterpret_cast(previous_block) + previous_block->size), + reinterpret_cast(&DOUBLE_FREE_ERROR_MESSAGE)}); 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 -- cgit v1.2.3