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/CMakeLists.txt | 2 +- .../include/kernel/memory/block_list_allocator.hpp | 80 +++++++++ .../include/kernel/memory/free_list_allocator.hpp | 80 --------- kernel/src/memory.cpp | 4 +- kernel/src/memory/block_list_allocator.cpp | 182 +++++++++++++++++++++ kernel/src/memory/free_list_allocator.cpp | 182 --------------------- 6 files changed, 265 insertions(+), 265 deletions(-) create mode 100644 kernel/include/kernel/memory/block_list_allocator.hpp delete mode 100644 kernel/include/kernel/memory/free_list_allocator.hpp create mode 100644 kernel/src/memory/block_list_allocator.cpp delete mode 100644 kernel/src/memory/free_list_allocator.cpp diff --git a/kernel/CMakeLists.txt b/kernel/CMakeLists.txt index 566ab9e..02e517c 100644 --- a/kernel/CMakeLists.txt +++ b/kernel/CMakeLists.txt @@ -11,7 +11,7 @@ add_executable("kernel" # Kernel Implementation "src/main.cpp" "src/memory/bitmap_allocator.cpp" - "src/memory/free_list_allocator.cpp" + "src/memory/block_list_allocator.cpp" "src/memory/operators.cpp" "src/memory.cpp" ) diff --git a/kernel/include/kernel/memory/block_list_allocator.hpp b/kernel/include/kernel/memory/block_list_allocator.hpp new file mode 100644 index 0000000..977ce89 --- /dev/null +++ b/kernel/include/kernel/memory/block_list_allocator.hpp @@ -0,0 +1,80 @@ +#ifndef TEACHOS_KERNEL_MEMORY_BLOCK_LIST_ALLOCATOR_HPP +#define TEACHOS_KERNEL_MEMORY_BLOCK_LIST_ALLOCATOR_HPP + +#include "kapi/memory.hpp" + +#include "kernel/memory/heap_allocator.hpp" + +#include + +#include +#include + +namespace kernel::memory +{ + + //! A simple, dynamically sized heap allocator. + //! + //! This allocator is designed to perform first-fit allocation using an intrusive doubly-linked list. The heap is + //! expanded as needed. + struct block_list_allocator final : heap_allocator + { + //! Construct a new free list allocator with the given base address. + explicit block_list_allocator(kapi::memory::linear_address base) noexcept; + + block_list_allocator(block_list_allocator const &) = delete; + block_list_allocator(block_list_allocator &&) = delete; + auto operator=(block_list_allocator const &) -> block_list_allocator & = delete; + auto operator=(block_list_allocator &&) -> block_list_allocator & = delete; + + //! Allocate a block of memory with the given alignment. + //! + //! @param size The size of the block to allocate + //! @param alignment The desired alignment of the allocated block + //! @return A pointer to the beginning of the block on success, @p nullptr otherwise. + [[nodiscard]] auto allocate(std::size_t size, std::align_val_t alignment) noexcept -> void * override; + + //! Deallocate a block of memory previously allocated. + //! + //! @param block The pointer to the block to free. + auto deallocate(void * block) noexcept -> void override; + + private: + struct block_header final + { + std::size_t size; + bool free; + block_header * next; + block_header * prev; + }; + + //! Try to expand the heap to accommodate the given size. + //! + //! @param delta The size to expand the heap by. + //! @return @p true if the heap was expanded, @p false otherwise. + auto expand(std::size_t delta) noexcept -> bool; + + //! Split a given free block to accommodate and allocation. + //! + //! The newly split free block is inserted into the free list. + //! + //! @param block The block to split. + //! @param size The size of the allocation. + //! @param padding The amount of padding to apply. + auto split(block_header * block, std::size_t size, std::size_t padding) noexcept -> void; + + //! Try to coalesce a given block with it's preceding and/or following block. + //! + //! @param block The block to coalesce. + auto coalesce(block_header * block) noexcept -> void; + + kapi::memory::linear_address m_base; + kapi::memory::linear_address m_frontier; + block_header * m_block_list; + + kstd::mutex m_lock; + }; + +} // namespace kernel::memory + +#endif \ No newline at end of file diff --git a/kernel/include/kernel/memory/free_list_allocator.hpp b/kernel/include/kernel/memory/free_list_allocator.hpp deleted file mode 100644 index 53a7b61..0000000 --- a/kernel/include/kernel/memory/free_list_allocator.hpp +++ /dev/null @@ -1,80 +0,0 @@ -#ifndef TEACHOS_KERNEL_MEMORY_FREE_LIST_ALLOCATOR_HPP -#define TEACHOS_KERNEL_MEMORY_FREE_LIST_ALLOCATOR_HPP - -#include "kapi/memory.hpp" - -#include "kernel/memory/heap_allocator.hpp" - -#include - -#include -#include - -namespace kernel::memory -{ - - //! A simple, dynamically sized heap allocator. - //! - //! This allocator is designed to perform first-fit allocation using an intrusive doubly-linked list. The heap is - //! expanded as needed. - struct free_list_allocator final : heap_allocator - { - //! Construct a new free list allocator with the given base address. - explicit free_list_allocator(kapi::memory::linear_address base) noexcept; - - free_list_allocator(free_list_allocator const &) = delete; - free_list_allocator(free_list_allocator &&) = delete; - auto operator=(free_list_allocator const &) -> free_list_allocator & = delete; - auto operator=(free_list_allocator &&) -> free_list_allocator & = delete; - - //! Allocate a block of memory with the given alignment. - //! - //! @param size The size of the block to allocate - //! @param alignment The desired alignment of the allocated block - //! @return A pointer to the beginning of the block on success, @p nullptr otherwise. - [[nodiscard]] auto allocate(std::size_t size, std::align_val_t alignment) noexcept -> void * override; - - //! Deallocate a block of memory previously allocated. - //! - //! @param block The pointer to the block to free. - auto deallocate(void * block) noexcept -> void override; - - private: - struct block_header final - { - std::size_t size; - bool free; - block_header * next; - block_header * prev; - }; - - //! Try to expand the heap to accommodate the given size. - //! - //! @param delta The size to expand the heap by. - //! @return @p true if the heap was expanded, @p false otherwise. - auto expand(std::size_t delta) noexcept -> bool; - - //! Split a given free block to accommodate and allocation. - //! - //! The newly split free block is inserted into the free list. - //! - //! @param block The block to split. - //! @param size The size of the allocation. - //! @param padding The amount of padding to apply. - auto split(block_header * block, std::size_t size, std::size_t padding) noexcept -> void; - - //! Try to coalesce a given block with it's preceding and/or following block. - //! - //! @param block The block to coalesce. - auto coalesce(block_header * block) noexcept -> void; - - kapi::memory::linear_address m_base; - kapi::memory::linear_address m_frontier; - block_header * m_free_list; - - kstd::mutex m_lock; - }; - -} // namespace kernel::memory - -#endif \ No newline at end of file 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