From 64bf7fcf58ced023be1701ed4508e38f746d40b8 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Mon, 16 Mar 2026 08:34:13 +0100 Subject: kernel/memory: implement basic free-list heap --- kernel/src/memory/free_list_allocator.cpp | 187 ++++++++++++++++++++++++++++++ kernel/src/memory/operators.cpp | 66 +++++++++++ 2 files changed, 253 insertions(+) create mode 100644 kernel/src/memory/free_list_allocator.cpp create mode 100644 kernel/src/memory/operators.cpp (limited to 'kernel/src/memory') diff --git a/kernel/src/memory/free_list_allocator.cpp b/kernel/src/memory/free_list_allocator.cpp new file mode 100644 index 0000000..255e643 --- /dev/null +++ b/kernel/src/memory/free_list_allocator.cpp @@ -0,0 +1,187 @@ +#include "kernel/memory/free_list_allocator.hpp" + +#include "kapi/memory.hpp" +#include "kapi/system.hpp" + +#include "kernel/memory/heap_allocator.hpp" + +#include + +#include +#include +#include +#include +#include + +namespace kernel::memory +{ + + namespace + { + [[nodiscard]] constexpr auto align_up(std::uintptr_t value, std::size_t alignment) noexcept -> std::uintptr_t + { + auto const remainder = value % alignment; + return remainder == 0 ? value : value + alignment - remainder; + } + } // namespace + + free_list_allocator::free_list_allocator(kapi::memory::linear_address base) noexcept + : heap_allocator{} + , m_base{base} + , m_frontier{base} + , m_free_list{} + , m_lock{} + {} + + auto free_list_allocator::allocate(std::size_t size, std::align_val_t alignment) noexcept -> void * + { + kstd::lock_guard guard{m_lock}; + + auto const alignment_value = static_cast(alignment); + auto const search_size = size + alignment_value + sizeof(block_header *); + + for (auto attempt = 0uz; attempt < 2uz; ++attempt) + { + auto current = m_free_list; + while (current != nullptr) + { + if (current->free && current->size >= search_size) + { + auto const payload_start = std::bit_cast(current) + sizeof(block_header); + auto const aligned_pointer = align_up(payload_start + sizeof(block_header *), alignment_value); + auto const padding = aligned_pointer - payload_start; + + split(current, size, padding); + current->free = false; + + auto back_pointer = std::bit_cast(aligned_pointer - sizeof(block_header *)); + *back_pointer = current; + + return std::bit_cast(aligned_pointer); + } + current = current->next; + } + + if (attempt == 0uz && !expand(search_size)) + { + return nullptr; + } + } + + return nullptr; + } + + auto free_list_allocator::deallocate(void * ptr) noexcept -> void + { + if (!ptr) + { + return; + } + + kstd::lock_guard guard{m_lock}; + + auto const aligned_pointer = std::bit_cast(ptr); + auto back_pointer = std::bit_cast(aligned_pointer - sizeof(block_header *)); + auto block = *back_pointer; + + block->free = true; + coalesce(block); + } + + auto free_list_allocator::expand(std::size_t size) noexcept -> bool + { + auto const total_required_size = size + sizeof(block_header); + auto const frames_needed = (total_required_size + kapi::memory::frame::size - 1) / kapi::memory::frame::size; + + auto const flags = kapi::memory::page_mapper::flags::writable | kapi::memory::page_mapper::flags::supervisor_only; + + for (auto i = 0uz; i < frames_needed; ++i) + { + auto frame = kapi::memory::allocate_frame(); + if (!frame) + { + kapi::system::panic("[OS:Heap] OOM when expanding heap."); + return false; + } + + auto page = kapi::memory::page::containing(m_frontier + i * kapi::memory::page::size); + kapi::memory::map(page, *frame, flags); + } + + auto block = std::bit_cast(m_frontier.raw()); + // std::construct_at(block, frames_needed * kapi::memory::frame::size - sizeof(block_header), true, nullptr, + // nullptr); + block->size = frames_needed * kapi::memory::frame::size - sizeof(block_header); + block->free = true; + block->next = nullptr; + block->prev = nullptr; + + m_frontier += frames_needed * kapi::memory::frame::size; + + if (!m_free_list) + { + m_free_list = block; + } + else + { + auto current = m_free_list; + while (current->next) + { + current = current->next; + } + current->next = block; + block->prev = current; + } + + coalesce(block); + return true; + } + + auto free_list_allocator::coalesce(block_header * block) noexcept -> void + { + if (block->next && block->next->free) + { + auto follower = block->next; + block->size += follower->size + sizeof(block_header); + block->next = follower->next; + if (block->next) + { + block->next->prev = block; + } + std::destroy_at(follower); + } + + if (block->prev && block->prev->free) + { + auto leader = block->prev; + leader->size += block->size + sizeof(block_header); + leader->next = block->next; + if (block->next) + { + block->next->prev = leader; + } + std::destroy_at(block); + } + } + + auto free_list_allocator::split(block_header * block, std::size_t size, std::size_t padding) noexcept -> void + { + auto const allocation_size = size + padding; + + if (block->size > allocation_size + sizeof(block_header) + 16uz) + { + auto new_block = + std::bit_cast(std::bit_cast(block) + sizeof(block_header) + allocation_size); + std::construct_at(new_block, block->size - allocation_size - sizeof(block_header), true, block->next, block); + + if (new_block->next) + { + new_block->next->prev = new_block; + } + + block->size = allocation_size; + block->next = new_block; + } + } + +} // namespace kernel::memory \ No newline at end of file diff --git a/kernel/src/memory/operators.cpp b/kernel/src/memory/operators.cpp new file mode 100644 index 0000000..1422133 --- /dev/null +++ b/kernel/src/memory/operators.cpp @@ -0,0 +1,66 @@ +#include "kapi/system.hpp" + +#include "kernel/memory.hpp" + +#include +#include + +[[nodiscard]] auto operator new(std::size_t size) -> void * +{ + auto & allocator = kernel::memory::get_heap_allocator(); + auto pointer = allocator.allocate(size, std::align_val_t{__STDCPP_DEFAULT_NEW_ALIGNMENT__}); + + if (pointer == nullptr) + { + kapi::system::panic("[OS:Heap] Out of memory!"); + } + + return pointer; +} + +[[nodiscard]] auto operator new[](std::size_t size) -> void * +{ + return ::operator new(size); +} + +[[nodiscard]] auto operator new(std::size_t size, std::align_val_t alignment) -> void * +{ + auto & allocator = kernel::memory::get_heap_allocator(); + auto pointer = allocator.allocate(size, alignment); + + if (pointer == nullptr) + { + kapi::system::panic("[OS:Heap] Out of memory!"); + } + + return pointer; +} + +auto operator delete(void * pointer) noexcept -> void +{ + if (pointer != nullptr) + { + auto & allocator = kernel::memory::get_heap_allocator(); + allocator.deallocate(pointer); + } +} + +auto operator delete(void * pointer, [[maybe_unused]] std::size_t size) noexcept -> void +{ + ::operator delete(pointer); +} + +auto operator delete[](void * pointer) noexcept -> void +{ + ::operator delete(pointer); +} + +auto operator delete[](void * pointer, [[maybe_unused]] std::size_t size) noexcept -> void +{ + ::operator delete(pointer); +} + +auto operator delete(void * pointer, [[maybe_unused]] std::align_val_t alignment) noexcept -> void +{ + ::operator delete(pointer); +} \ No newline at end of file -- cgit v1.2.3