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/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 ----- 4 files changed, 56 insertions(+), 23 deletions(-) create mode 100644 arch/x86_64/src/memory/heap/memory_block.cpp delete mode 100644 arch/x86_64/src/memory/heap/memory_hole.cpp (limited to 'arch/x86_64/src') 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