From ccad1abdcb0951a7e30eee536c546e5d77ab4b33 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Mon, 16 Mar 2026 08:35:14 +0100 Subject: x86_64/pre: remove old heap implementation --- arch/x86_64/pre/src/memory/heap/bump_allocator.cpp | 54 ------ .../pre/src/memory/heap/global_heap_allocator.cpp | 148 --------------- .../pre/src/memory/heap/linked_list_allocator.cpp | 177 ------------------ arch/x86_64/pre/src/memory/heap/memory_block.cpp | 18 -- .../pre/src/memory/heap/user_heap_allocator.cpp | 200 --------------------- 5 files changed, 597 deletions(-) delete mode 100644 arch/x86_64/pre/src/memory/heap/bump_allocator.cpp delete mode 100644 arch/x86_64/pre/src/memory/heap/global_heap_allocator.cpp delete mode 100644 arch/x86_64/pre/src/memory/heap/linked_list_allocator.cpp delete mode 100644 arch/x86_64/pre/src/memory/heap/memory_block.cpp delete mode 100644 arch/x86_64/pre/src/memory/heap/user_heap_allocator.cpp (limited to 'arch/x86_64/pre/src') diff --git a/arch/x86_64/pre/src/memory/heap/bump_allocator.cpp b/arch/x86_64/pre/src/memory/heap/bump_allocator.cpp deleted file mode 100644 index 525f45c..0000000 --- a/arch/x86_64/pre/src/memory/heap/bump_allocator.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include "arch/memory/heap/bump_allocator.hpp" - -#include "arch/exception_handling/assert.hpp" - -#include -#include - -namespace teachos::arch::memory::heap -{ - namespace - { - template - 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 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 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 bump_allocator::deallocate(void * pointer) noexcept -> void - { - if (pointer) - { - } - } - -} // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/pre/src/memory/heap/global_heap_allocator.cpp b/arch/x86_64/pre/src/memory/heap/global_heap_allocator.cpp deleted file mode 100644 index 709cda1..0000000 --- a/arch/x86_64/pre/src/memory/heap/global_heap_allocator.cpp +++ /dev/null @@ -1,148 +0,0 @@ -#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; - - auto global_heap_allocator::kmalloc(std::size_t size) -> void * - { - return kernel().allocate(size); - } - - 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(kernel_allocator_instance == nullptr, - "Calling register_heap_allocator_type can only be done once."); - - switch (new_type) - { - case heap_allocator_type::NONE: - // Nothing to do - break; - case heap_allocator_type::BUMP: - { - bump_allocator static kernel_allocator{KERNEL_HEAP_START, KERNEL_HEAP_START + KERNEL_HEAP_SIZE}; - kernel_allocator_instance = &kernel_allocator; - break; - } - case heap_allocator_type::LINKED_LIST: - { - linked_list_allocator static kernel_allocator{KERNEL_HEAP_START, KERNEL_HEAP_START + KERNEL_HEAP_SIZE}; - kernel_allocator_instance = &kernel_allocator; - break; - } - } - - [[gnu::section(".user_data")]] user_heap_allocator static user_allocator{}; - user_allocator_instance = &user_allocator; - } - - auto global_heap_allocator::kernel() -> heap_allocator & - { - exception_handling::assert(kernel_allocator_instance != nullptr, NOT_REGISTRED_ERROR_MESSAGE); - - return *kernel_allocator_instance; - } - - auto global_heap_allocator::user() -> user_heap_allocator & - { - 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 * -{ - 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 -{ - 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; - 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 * -{ - 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 -{ - 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; - 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); -} diff --git a/arch/x86_64/pre/src/memory/heap/linked_list_allocator.cpp b/arch/x86_64/pre/src/memory/heap/linked_list_allocator.cpp deleted file mode 100644 index 00ca366..0000000 --- a/arch/x86_64/pre/src/memory/heap/linked_list_allocator.cpp +++ /dev/null @@ -1,177 +0,0 @@ -#include "arch/memory/heap/linked_list_allocator.hpp" - -#include "arch/exception_handling/assert.hpp" -#include "arch/exception_handling/panic.hpp" - -#include - -namespace teachos::arch::memory::heap -{ - linked_list_allocator::linked_list_allocator(std::size_t heap_start, std::size_t heap_end) - : first(nullptr) - , mutex{kstd::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 linked_list_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 (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)); - } - - previous = current; - current = current->next; - } - - exception_handling::panic("[Linked List Allocator] Out of memory"); - } - - auto linked_list_allocator::deallocate(void * pointer) noexcept -> void - { - 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) - { - // 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) - { - break; - } - - previous = current; - current = current->next; - } - - coalesce_free_memory_block(previous, current, header_pointer, total_size); - mutex.unlock(); - } - - auto linked_list_allocator::remove_free_memory_block(memory_block * previous_block, memory_block * current_block) - -> void * - { - return replace_free_memory_block(previous_block, current_block, current_block->next); - } - - auto linked_list_allocator::split_free_memory_block(memory_block * previous_block, memory_block * current_block, - std::size_t size) -> void * - { - auto const end_address = reinterpret_cast(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 linked_list_allocator::replace_free_memory_block(memory_block * previous_block, memory_block * current_block, - memory_block * new_block) -> void * - { - auto const start_address = reinterpret_cast(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 linked_list_allocator::coalesce_free_memory_block(memory_block * previous_block, memory_block * current_block, - void * pointer, std::size_t size) -> void - { - auto const start_address = reinterpret_cast(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 diff --git a/arch/x86_64/pre/src/memory/heap/memory_block.cpp b/arch/x86_64/pre/src/memory/heap/memory_block.cpp deleted file mode 100644 index 4c07454..0000000 --- a/arch/x86_64/pre/src/memory/heap/memory_block.cpp +++ /dev/null @@ -1,18 +0,0 @@ -#include "arch/memory/heap/memory_block.hpp" - -#include - -namespace teachos::arch::memory::heap -{ - memory_block::memory_block(std::size_t size, memory_block * next) - { - memset(static_cast(this), 0U, size); - this->size = size; - this->next = next; - } - - memory_block::~memory_block() - { - memset(static_cast(this), 0U, sizeof(memory_block)); - } -} // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/pre/src/memory/heap/user_heap_allocator.cpp b/arch/x86_64/pre/src/memory/heap/user_heap_allocator.cpp deleted file mode 100644 index 96de005..0000000 --- a/arch/x86_64/pre/src/memory/heap/user_heap_allocator.cpp +++ /dev/null @@ -1,200 +0,0 @@ -#include "arch/memory/heap/user_heap_allocator.hpp" - -#include "arch/context_switching/syscall/main.hpp" - -#include - -namespace teachos::arch::memory::heap -{ - 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) - { - auto memory = allocate_into_memory_block_if_big_enough(current, previous, total_size); - if (memory.has_value()) - { - return memory.value(); - } - - previous = current; - current = current->next; - } - - current = expand_heap_if_full(); - - if (current != nullptr) - { - auto memory = allocate_into_memory_block_if_big_enough(current, previous, total_size); - if (memory.has_value()) - { - return memory.value(); - } - } - - constexpr char 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 - { - 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) - { - // 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) - { - break; - } - - previous = current; - current = current->next; - } - - coalesce_free_memory_block(previous, current, header_pointer, total_size); - 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); - - 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) - -> void * - { - 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. - constexpr char 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 - // 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