diff options
Diffstat (limited to 'arch/x86_64/include')
| -rw-r--r-- | arch/x86_64/include/arch/memory/heap/user_heap_allocator.hpp | 118 |
1 files changed, 97 insertions, 21 deletions
diff --git a/arch/x86_64/include/arch/memory/heap/user_heap_allocator.hpp b/arch/x86_64/include/arch/memory/heap/user_heap_allocator.hpp index 9d00c19..d698888 100644 --- a/arch/x86_64/include/arch/memory/heap/user_heap_allocator.hpp +++ b/arch/x86_64/include/arch/memory/heap/user_heap_allocator.hpp @@ -1,16 +1,14 @@ #ifndef TEACHOS_ARCH_X86_64_MEMORY_HEAP_USER_HEAP_ALLOCATOR_HPP #define TEACHOS_ARCH_X86_64_MEMORY_HEAP_USER_HEAP_ALLOCATOR_HPP -#include "arch/memory/heap/heap_allocator.hpp" - -#include <atomic> -#include <cstdint> +#include "arch/memory/heap/memory_block.hpp" +#include "arch/stl/mutex.hpp" namespace teachos::arch::memory::heap { /** - * @brief Simple heap allocator, which allocates linearly and leaks all allocated memory, because it does not really - * deallocate anything. + * @brief Sorted by address list of memory holes (free memory). Uses free holes itself to save the information, + * containing the size and pointer to the next hole. Resulting in a singly linked list. */ struct user_heap_allocator { @@ -20,31 +18,109 @@ namespace teachos::arch::memory::heap * @param heap_start Start of the allocatable heap area * @param heap_end End of the allocatable heap area (Start + Size) */ - user_heap_allocator(std::size_t heap_start, std::size_t heap_end) - : heap_start{heap_start} - , heap_end{heap_end} - , next{heap_start} - { - // Nothing to do - } + user_heap_allocator(std::size_t heap_start, std::size_t heap_end); + /** + * @copybrief heap_allocator::allocate + * + * @note The specified size is used to find a free memory block with the exact same size, meaning we can remove that + * free memory block from the free list and simply return its address. Or it has to be big enough to hold the size + * and alteast enough memory for another free memory block entry (16 bytes). If the amount of memory of that free + * memory block is in between we cannot use it for our allocation, because we could only return it to the user, but + * the additional bytes, could not be used to create a free memory block. Additionaly the user couldn't know + * they received more memory than wanted. Therefore the memory would simply be unused and because it is neither + * allocated nor deallocated would never be indexed by the free memory list. We would therefore permanently loose + * that memory, to prevent that allocation into free memory blocks like that are impossible. + */ [[gnu::section(".user_text")]] auto allocate(std::size_t size) -> void *; + [[gnu::section(".user_text")]] + auto deallocate(void * pointer) noexcept -> void; + + private: /** - * @copybrief heap_allocator::deallocate + * @brief Returns the smallest allocatable block of heap memory. * - * @note Simply does nothing, because this allocator leaks all memory + * @return Smallest allocatable block of heap memory. + */ + [[gnu::section(".user_text")]] auto constexpr min_allocatable_size() -> std::size_t { return sizeof(memory_block); } + + /** + * @brief Removes a free memory block from the free list and returns its address so the caller can allocate into it. + * + * @param previous_block Free memory block before the block to allocate in our heap memory. Was to small to + * allocate the required size into. + * @param current_block Free memory block we want to remove from the free list and return for the allocation. + * + * @return Previous start address of the memory block we removed, because it can now be used for the allocation. */ [[gnu::section(".user_text")]] - auto deallocate(void * pointer) noexcept -> void; + auto remove_free_memory_block(memory_block * previous_block, memory_block * current_block) -> void *; - private: - std::size_t heap_start; ///< Start of the allocatable heap area - std::size_t heap_end; ///< End of the allocatable heap area - std::atomic_uint64_t next; ///< Current address, which is the start of still unused allocatable heap area - }; + /** + * @brief Splits the given free memory block into two, where the latter block keeps being free and the first + * part will be used for the allocation. + * + * @param previous_block Free memory block before the block to allocate in our heap memory. Was to small to + * allocate the required size into. + * @param current_block Free memory block we want to split into a size part for the allocation and the rest for + * future allocations. + * @param size Size we want to allocate at the start of the free memory block. + * + * @return Previous start address of the memory block we just split, because it can now be used for the allocation. + */ + [[gnu::section(".user_text")]] + auto split_free_memory_block(memory_block * previous_block, memory_block * current_block, std::size_t size) + -> void *; + /** + * @brief Removes a free memory block from the free list and returns its address so the caller can allocate into it. + * + * @param previous_block Free memory block before the block to allocate in our heap memory. Was to small to + * allocate the required size into. + * @param current_block Free memory block we want to remove from the free list and return for the allocation. + * @param new_block Replaces the current block with the given new block can be nullptr, meaning the free list will + * end here. + * + * @return Previous start address of the memory block we removed, because it can now be used for the allocation. + */ + [[gnu::section(".user_text")]] + auto replace_free_memory_block(memory_block * previous_block, memory_block * current_block, + memory_block * new_block) -> void *; + + /** + * @brief Combines multiple free memory blocks into one if they are adjacent. + * + * @note The internal algorithm for recombination functions like this: + * 1. Check if there is even any memory left, if not the first entry of our linked list should be a nullptr and + * we can therefore set the first entry to our newly created entry. This entry is created in the now deallocated + * memory area. + * 2. If there are more blocks but neither the previous nor the current block are adjacent, we simply create a + * new free memory block of the given size and set the previous next to our block and the next of our block to + * the current block. + * 3. If the current block is adjacent the start address of the newly created block stays the same, but the size + * increases by the amount in the current memory block header. After reading it we also clear the header. + * 4. If the previous block is adjacent the size of the previous block simply increases to include the given + * size as well. + * 5. If the previous block is directly in our start address, so they overlap then it has to mean some or all of + * the region we are trying to deallocate has been freed before. Which would result in a double free therefore + * we halt the execution of the program. + * + * @param previous_block Free memory block before the block to deallocate in our heap memory. + * @param current_block Free memory block after the block to deallocate in our heap memory. + * @param pointer Block to deallocate. + * @param size Size of the block we want to deallocate. + */ + [[gnu::section(".user_text")]] + auto coalesce_free_memory_block(memory_block * previous_block, memory_block * current_block, void * pointer, + std::size_t size) -> void; + + std::size_t heap_start; ///< Start of the allocatable heap area. + std::size_t heap_end; ///< End of the allocatable heap area. + memory_block * first; ///< First free entry in our memory. + stl::mutex mutex; ///< Mutex to ensure only one thread calls allocate or deallocate at once. + }; } // namespace teachos::arch::memory::heap #endif // TEACHOS_ARCH_X86_64_MEMORY_HEAP_USER_HEAP_ALLOCATOR_HPP |