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. --- .../include/kernel/memory/block_list_allocator.hpp | 80 ++++++++++++++++++++++ .../include/kernel/memory/free_list_allocator.hpp | 80 ---------------------- 2 files changed, 80 insertions(+), 80 deletions(-) create mode 100644 kernel/include/kernel/memory/block_list_allocator.hpp delete mode 100644 kernel/include/kernel/memory/free_list_allocator.hpp (limited to 'kernel/include') 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 -- cgit v1.2.3