From b67872907249bed3bad141fae97350959bffb009 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Mon, 16 Mar 2026 08:52:08 +0100 Subject: kernel/memory: rename free list allocator It is not really a free list allocator, but rather a block list allocator, since it contains both free and used blocks in the same list. --- kernel/src/memory.cpp | 4 +- kernel/src/memory/block_list_allocator.cpp | 182 +++++++++++++++++++++++++++++ kernel/src/memory/free_list_allocator.cpp | 182 ----------------------------- 3 files changed, 184 insertions(+), 184 deletions(-) create mode 100644 kernel/src/memory/block_list_allocator.cpp delete mode 100644 kernel/src/memory/free_list_allocator.cpp (limited to 'kernel/src') diff --git a/kernel/src/memory.cpp b/kernel/src/memory.cpp index 14bedf1..3bc86f3 100644 --- a/kernel/src/memory.cpp +++ b/kernel/src/memory.cpp @@ -3,7 +3,7 @@ #include "kapi/memory.hpp" #include "kapi/system.hpp" -#include "kernel/memory/free_list_allocator.hpp" +#include "kernel/memory/block_list_allocator.hpp" #include "kernel/memory/heap_allocator.hpp" #include @@ -31,7 +31,7 @@ namespace kernel::memory constinit null_allocator null_allocator::instance{}; auto constinit active_heap_allocator = std::optional{&null_allocator::instance}; - auto constinit basic_allocator = std::optional{}; + auto constinit basic_allocator = std::optional{}; } // namespace auto get_heap_allocator() -> heap_allocator & diff --git a/kernel/src/memory/block_list_allocator.cpp b/kernel/src/memory/block_list_allocator.cpp new file mode 100644 index 0000000..cc91304 --- /dev/null +++ b/kernel/src/memory/block_list_allocator.cpp @@ -0,0 +1,182 @@ +#include "kernel/memory/block_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 + + block_list_allocator::block_list_allocator(kapi::memory::linear_address base) noexcept + : heap_allocator{} + , m_base{base} + , m_frontier{base} + , m_block_list{} + , m_lock{} + {} + + auto block_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_block_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 block_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 block_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); + + m_frontier += frames_needed * kapi::memory::frame::size; + + if (!m_block_list) + { + m_block_list = block; + } + else + { + auto current = m_block_list; + while (current->next) + { + current = current->next; + } + current->next = block; + block->prev = current; + } + + coalesce(block); + return true; + } + + auto block_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 block_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/free_list_allocator.cpp b/kernel/src/memory/free_list_allocator.cpp deleted file mode 100644 index 66b6bdb..0000000 --- a/kernel/src/memory/free_list_allocator.cpp +++ /dev/null @@ -1,182 +0,0 @@ -#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); - - 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 -- cgit v1.2.3