From eba6c94eed15b90ea8a09e4bc16ae1c0f1645dea Mon Sep 17 00:00:00 2001 From: Fabian Imhof Date: Sun, 1 Dec 2024 11:08:00 +0000 Subject: implement first half of linked list dallocation --- arch/x86_64/CMakeLists.txt | 2 +- .../include/arch/memory/heap/bump_allocator.hpp | 2 +- .../arch/memory/heap/linked_list_allocator.hpp | 12 ++--- .../include/arch/memory/heap/memory_block.hpp | 28 +++++++++++ .../include/arch/memory/heap/memory_hole.hpp | 28 ----------- arch/x86_64/src/memory/heap/bump_allocator.cpp | 2 +- .../src/memory/heap/linked_list_allocator.cpp | 55 +++++++++++++++++----- arch/x86_64/src/memory/heap/memory_block.cpp | 11 +++++ arch/x86_64/src/memory/heap/memory_hole.cpp | 11 ----- 9 files changed, 92 insertions(+), 59 deletions(-) create mode 100644 arch/x86_64/include/arch/memory/heap/memory_block.hpp delete mode 100644 arch/x86_64/include/arch/memory/heap/memory_hole.hpp create mode 100644 arch/x86_64/src/memory/heap/memory_block.cpp delete mode 100644 arch/x86_64/src/memory/heap/memory_hole.cpp diff --git a/arch/x86_64/CMakeLists.txt b/arch/x86_64/CMakeLists.txt index 4ba6590..4a02e15 100644 --- a/arch/x86_64/CMakeLists.txt +++ b/arch/x86_64/CMakeLists.txt @@ -57,7 +57,7 @@ target_sources("_memory" PRIVATE "src/memory/cpu/control_register.cpp" "src/memory/cpu/msr.cpp" "src/memory/heap/bump_allocator.cpp" - "src/memory/heap/memory_hole.cpp" + "src/memory/heap/memory_block.cpp" "src/memory/heap/linked_list_allocator.cpp" ) diff --git a/arch/x86_64/include/arch/memory/heap/bump_allocator.hpp b/arch/x86_64/include/arch/memory/heap/bump_allocator.hpp index 595eeea..545b72f 100644 --- a/arch/x86_64/include/arch/memory/heap/bump_allocator.hpp +++ b/arch/x86_64/include/arch/memory/heap/bump_allocator.hpp @@ -42,7 +42,7 @@ namespace teachos::arch::memory::heap * @param pointer Pointer to the location which should be deallocated. * @param size Size of the underlying memory area we want to deallocate. */ - auto deallocate(uint8_t * pointer, std::size_t size) -> void; + auto deallocate(void * pointer, std::size_t size) -> void; private: std::size_t heap_start; ///< Start of the allocatable heap area diff --git a/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp b/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp index 5f9a72b..99d0013 100644 --- a/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp +++ b/arch/x86_64/include/arch/memory/heap/linked_list_allocator.hpp @@ -1,7 +1,7 @@ #ifndef TEACHOS_ARCH_X86_64_MEMORY_HEAP_LINKED_LIST_ALLOCATOR_HPP #define TEACHOS_ARCH_X86_64_MEMORY_HEAP_LINKED_LIST_ALLOCATOR_HPP -#include "arch/memory/heap/memory_hole.hpp" +#include "arch/memory/heap/memory_block.hpp" #include @@ -37,7 +37,7 @@ namespace teachos::arch::memory::heap * @param pointer Pointer to the location which should be deallocated. * @param size Size of the underlying memory area we want to deallocate. */ - auto deallocate(uint8_t * pointer, std::size_t size) -> void; + auto deallocate(void * pointer, std::size_t size) -> void; private: /** @@ -45,22 +45,22 @@ namespace teachos::arch::memory::heap * * @return Smallest allocatable block of heap memory. */ - auto constexpr min_allocatable_size() -> std::size_t { return sizeof(memory_hole); } + auto constexpr min_allocatable_size() -> std::size_t { return sizeof(memory_block); } /** * @brief Splits the given hole into two, where the latter block keeps beeing free and the first part will be used * for the allocation. * - * @param current_hole Hole we want to split. + * @param current_block Hole we want to split. * @param size Size we want to allocate at the start of the hole. * * @return Address of the hole we just split. */ - auto split_hole(memory_hole *& current_hole, std::size_t size) -> void *; + auto split_free_memory_block(memory_block *& current_block, std::size_t size) -> void *; std::size_t heap_start; ///< Start of the allocatable heap area std::size_t heap_end; ///< End of the allocatable heap area - memory_hole * first; ///< First free entry in our memory + memory_block * first; ///< First free entry in our memory }; } // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/include/arch/memory/heap/memory_block.hpp b/arch/x86_64/include/arch/memory/heap/memory_block.hpp new file mode 100644 index 0000000..c48d0cd --- /dev/null +++ b/arch/x86_64/include/arch/memory/heap/memory_block.hpp @@ -0,0 +1,28 @@ +#ifndef TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_BLOCK_HPP +#define TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_BLOCK_HPP + +#include + +namespace teachos::arch::memory::heap +{ + /** + * @brief Block containing free memory, pointing to the next free hole (nullptr) if there is none. + * Forms a single linked list. + */ + struct memory_block + { + /** + * @brief Constructor, + * + * @param size Amount of free memory of this specific hole. + * @param next Optional pointer to the next free memory. + */ + memory_block(std::size_t size, memory_block * next); + + std::size_t size; ///< Amount of free memory this hole contains, has to always be atleast 16 bytes to hold the size + ///< variable and the pointer to the next hole. + memory_block * next; ///< Optional pointer to the next free memory, holds nullptr if there is none. + }; +} // namespace teachos::arch::memory::heap + +#endif // TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_BLOCK_HPP diff --git a/arch/x86_64/include/arch/memory/heap/memory_hole.hpp b/arch/x86_64/include/arch/memory/heap/memory_hole.hpp deleted file mode 100644 index e017599..0000000 --- a/arch/x86_64/include/arch/memory/heap/memory_hole.hpp +++ /dev/null @@ -1,28 +0,0 @@ -#ifndef TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_HOLE_HPP -#define TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_HOLE_HPP - -#include - -namespace teachos::arch::memory::heap -{ - /** - * @brief Block containing free memory, pointing to the next free hole (nullptr) if there is none. - * Forms a single linked list. - */ - struct memory_hole - { - /** - * @brief Constructor, - * - * @param size Amount of free memory of this specific hole. - * @param next Optional pointer to the next free memory. - */ - memory_hole(std::size_t size, memory_hole * next); - - std::size_t size; ///< Amount of free memory this hole contains, has to always be atleast 16 bytes to hold the size - ///< variable and the pointer to the next hole. - memory_hole * next; ///< Optional pointer to the next free memory, holds nullptr if there is none. - }; -} // namespace teachos::arch::memory::heap - -#endif // TEACHOS_ARCH_X86_64_MEMORY_HEAP_MEMORY_HOLE_HPP diff --git a/arch/x86_64/src/memory/heap/bump_allocator.cpp b/arch/x86_64/src/memory/heap/bump_allocator.cpp index 8807645..bbf2021 100644 --- a/arch/x86_64/src/memory/heap/bump_allocator.cpp +++ b/arch/x86_64/src/memory/heap/bump_allocator.cpp @@ -42,7 +42,7 @@ namespace teachos::arch::memory::heap } } - auto bump_allocator::deallocate(uint8_t * pointer, std::size_t size) -> void + auto bump_allocator::deallocate(void * pointer, std::size_t size) -> void { if (pointer || size) { 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 a2a8c79..9b27f70 100644 --- a/arch/x86_64/src/memory/heap/linked_list_allocator.cpp +++ b/arch/x86_64/src/memory/heap/linked_list_allocator.cpp @@ -17,20 +17,24 @@ 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_hole(heap_size, nullptr); + first = new (reinterpret_cast(heap_start)) memory_block(heap_size, nullptr); } auto linked_list_allocator::allocate(std::size_t size) -> void * { + exception_handling::assert(size < min_allocatable_size(), + "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes"); + auto & previous = first; auto & current = first; + while (current != nullptr) { - if (current->size > size) + if (current->size >= size + min_allocatable_size()) { - return split_hole(current, size); + return split_free_memory_block(current, size); } - else if (current->size == size) + else if (current->size >= size) { if (previous != current) { @@ -40,30 +44,59 @@ namespace teachos::arch::memory::heap { current = current->next; } + delete current; return static_cast(current); } + previous = current; current = current->next; } exception_handling::panic("[Linked List Allocator] Out of memory"); } - auto linked_list_allocator::deallocate(uint8_t * pointer, std::size_t size) -> void + auto linked_list_allocator::deallocate(void * pointer, std::size_t size) -> void { - auto const deallocate_size = std::max(size, min_allocatable_size()); - if (pointer || deallocate_size) + exception_handling::assert(size < min_allocatable_size(), + "[Linked List Allocator] Allocated memory cannot be smaller than 16 bytes"); + + auto & previous = first; + auto & current = first; + + while (current != nullptr) { + // if pointer + size < current + // create memory block + auto const previous_address = reinterpret_cast(pointer); + auto const new_address = previous_address + size; + + if (new_address != reinterpret_cast(current) && + previous_address != (reinterpret_cast(previous) + previous->size)) + { + auto new_block = new (pointer) memory_block(size, current); + previous->next = new_block; + return; + } + + // elseif pointer + size == current + // combine memory block with current + // combine(previous, pointer, current) + + previous = current; + current = current->next; } } - auto split_hole(memory_hole *& current_hole, std::size_t size) -> void * + auto linked_list_allocator::split_free_memory_block(memory_block *& current_block, std::size_t size) -> void * { - auto const previous_address = reinterpret_cast(current_hole); + auto const previous_address = reinterpret_cast(current_block); auto const new_address = previous_address + size; - current_hole = - new (reinterpret_cast(new_address)) memory_hole(current_hole->size - size, current_hole->next); + current_block = + new (reinterpret_cast(new_address)) memory_block(current_block->size - size, current_block->next); return reinterpret_cast(previous_address); } + // auto linked_list_allocator::combine_free_memory_block(memory_block *& previous_block, memory_block *& + // current_block, std::size_t size) -> void * + } // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/src/memory/heap/memory_block.cpp b/arch/x86_64/src/memory/heap/memory_block.cpp new file mode 100644 index 0000000..b68dd6d --- /dev/null +++ b/arch/x86_64/src/memory/heap/memory_block.cpp @@ -0,0 +1,11 @@ +#include "arch/memory/heap/memory_block.hpp" + +namespace teachos::arch::memory::heap +{ + memory_block::memory_block(std::size_t size, memory_block * next) + : size(size) + , next(next) + { + // Nothing to do + } +} // namespace teachos::arch::memory::heap diff --git a/arch/x86_64/src/memory/heap/memory_hole.cpp b/arch/x86_64/src/memory/heap/memory_hole.cpp deleted file mode 100644 index 7590610..0000000 --- a/arch/x86_64/src/memory/heap/memory_hole.cpp +++ /dev/null @@ -1,11 +0,0 @@ -#include "arch/memory/heap/memory_hole.hpp" - -namespace teachos::arch::memory::heap -{ - memory_hole::memory_hole(std::size_t size, memory_hole * next) - : size(size) - , next(next) - { - // Nothing to do - } -} // namespace teachos::arch::memory::heap -- cgit v1.2.3