bump.cpp

//
// Created by 98max on 8/07/2026.
//
 
#include <memory/allocator/bump.h>
 
using namespace MaxOS;
using namespace MaxOS::memory;
using namespace MaxOS::memory::allocator;
 
BumpAllocator::BumpAllocator() {
    static_assert(CHUNK_HEADER_SIZE == sizeof(chunk_header_t));
};
 
BumpAllocator::~BumpAllocator() = default;
 
void* BumpAllocator::allocate_extra_space(size_t requested_size, size_t& actual_size) {
    return nullptr;
}
 
bool ChunkHeader::is_valid() {
    return canary == EXPECTED_CANARY;
}
 
chunk_header_t* ChunkHeader::prev_chunk() {
 
    // Make sure the chunk is not poiting to garbage
    if (!is_valid())
        ASSERT(false, "Invalid memory chunk detected (possible buffer overflow)\n");
 
    return prev;
}
 
 
chunk_header_t* ChunkHeader::next_chunk() {
 
    // Make sure the chunk is not poiting to garbage
    if (!is_valid())
        ASSERT(false, "Invalid memory chunk detected (possible buffer overflow)\n");
 
    return next;
}
 
void* BumpAllocator::expand_heap(size_t size) {
 
    // Create a new chunk of memory
    size_t actual_size;
    auto* chunk = (chunk_header_t*)allocate_extra_space(CHUNK_HEADER_SIZE + size, actual_size);
    if (chunk == nullptr)
        return nullptr;
 
    // Set the chunk's properties
    chunk->allocated = false;
    chunk->size = actual_size - CHUNK_HEADER_SIZE;
    chunk->next = nullptr;
    chunk->canary = EXPECTED_CANARY;
 
    // Insert the chunk into the linked list
    m_last_memory_chunk->next = chunk;
    chunk->prev = m_last_memory_chunk;
    m_last_memory_chunk = chunk;
 
    // If it is possible to merge the new chunk with the previous chunk then do so (note: this happens if the
    // previous chunk is free but cant contain the size required)
    chunk_header_t* prev_chunk = chunk->prev_chunk();
    bool adjacent = (uintptr_t)prev_chunk + CHUNK_HEADER_SIZE + prev_chunk->size == (uintptr_t)chunk;
    if (!prev_chunk->allocated && adjacent) {
 
        // The new chunk gets merged into the previous one (its header stops existing), so hand back the merged chunk
        chunk_header_t* merged = chunk->prev_chunk();
        unallocate((void*)((size_t)chunk + CHUNK_HEADER_SIZE));
        return merged;
    }
 
    return chunk;
}
 
void BumpAllocator::setup_region(uintptr_t address, size_t length) {
 
    // Create a free chunk that covers the entire region
    this->m_first_memory_chunk = (chunk_header_t*)address;
    m_first_memory_chunk->allocated = false;
    m_first_memory_chunk->prev = nullptr;
    m_first_memory_chunk->next = nullptr;
    m_first_memory_chunk->size = length - CHUNK_HEADER_SIZE;
    m_first_memory_chunk->canary = EXPECTED_CANARY;
 
    m_last_memory_chunk = m_first_memory_chunk;
    m_setup = true;
 
}
 
 
void* BumpAllocator::allocate(size_t size) {
 
    chunk_header_t* result = nullptr;
 
    // Nothing to allocate
    if (size == 0)
        return nullptr;
 
    size = align(size);
 
    // Find the next free chunk that is big enough
    for (chunk_header_t* chunk = m_first_memory_chunk; chunk != nullptr && result == nullptr; chunk = chunk->next_chunk()) {
 
        ASSERT(chunk->is_valid(),"Invalid allocator chunk canary\n");
        ASSERT(chunk->allocated <= 1, "Invalid allocator allocation state\n");
 
        if (chunk->size >= size && chunk->allocated == 0)
            result = chunk;
    }
 
    // If there is no free chunk then make more room
    if (result == nullptr)
        result = (chunk_header_t*)expand_heap(size);
 
    // No space to expand heap
    if (result == nullptr)
        return nullptr;
 
    // If there is not left over space to store extra chunks there is no need to split the chunk
    if (result->size < size + CHUNK_HEADER_SIZE + CHUNK_ALIGNMENT) {
        result->allocated = true;
        void* p = (void*)(((size_t)result) + CHUNK_HEADER_SIZE);
        return p;
    }
 
    // Split the chunk into: what was requested + free overflow space for future allocates
    //  - This prevents waste in the event that a big free chunk was found but the requested size would only use a portion of that
    auto* extra = (chunk_header_t*)((size_t)result + CHUNK_HEADER_SIZE + size);
    extra->allocated = false;
    extra->size = result->size - size - CHUNK_HEADER_SIZE;
    extra->prev = result;
    extra->canary = EXPECTED_CANARY;
 
    // Add to the linked list
    extra->next = result->next;
    if (extra->next != nullptr)
        extra->next->prev = extra;
 
    // Requested chunk is now allocated exactly to the size requested and points to the free (split) block of memory that
    // it did not use
    result->size = size;
    result->allocated = true;
    result->next = extra;
    result->canary = EXPECTED_CANARY;
 
    // Update the last memory chunk if necessary
    if (result == m_last_memory_chunk)
        m_last_memory_chunk = extra;
 
    return (void*)(((size_t)result) + CHUNK_HEADER_SIZE);
}
 
 
void BumpAllocator::unallocate(void* pointer) {
 
    // Cant free unallocated memory
    if (pointer == nullptr)
        return;
 
    // Check bounds
    auto heap_start = (uintptr_t)m_first_memory_chunk;
    auto heap_end = (uintptr_t)m_last_memory_chunk + CHUNK_HEADER_SIZE + m_last_memory_chunk->size;
    if ((uintptr_t)pointer < heap_start || (uintptr_t)pointer > heap_end)
        return;
 
    // Get the chunk information from the pointer
    auto* chunk = (chunk_header_t*)((size_t)pointer - CHUNK_HEADER_SIZE);
    chunk->allocated = false;
 
    // If there is a free chunk before this chunk then merge them
    if (chunk->prev_chunk() != nullptr && !chunk->prev_chunk()->allocated && (uintptr_t)chunk->prev_chunk() + CHUNK_HEADER_SIZE + chunk->prev_chunk()->size == (uintptr_t)chunk) {
 
        // If this chunk is the last one then the one it merges into is now the last one
        if (chunk == m_last_memory_chunk)
            m_last_memory_chunk = chunk->prev_chunk();
 
        // Grow the chunk behind this one so that it now contains the freed one
        chunk->prev_chunk()->size += chunk->size + CHUNK_HEADER_SIZE;
        chunk->prev_chunk()->next = chunk->next_chunk();
 
        // The chunk in front of the freed one now needs to point to the merged chunk
        if (chunk->next_chunk() != nullptr)
            chunk->next_chunk()->prev = chunk->prev_chunk();
 
        // Freed chunk doesn't exist anymore so now working with the merged chunk
        chunk = chunk->prev_chunk();
 
    }
 
    // If there is a free chunk after this chunk then merge them
    if (chunk->next_chunk() != nullptr && !chunk->next_chunk()->allocated && (uintptr_t)chunk + CHUNK_HEADER_SIZE + chunk->size == (uintptr_t)chunk->next_chunk()) {
 
        // Merging with the last mem chunk means this chunk is now the last mem chunk
        if (chunk->next_chunk() == m_last_memory_chunk)
            m_last_memory_chunk = chunk;
 
        // Grow this chunk so that it now contains the free chunk in front of the old (now freed) one
        chunk->size += chunk->next_chunk()->size + CHUNK_HEADER_SIZE;
 
        // Now that this chunk contains the next one, it has to point to the one in front of what has just been merged
        // and that has to point to this
        chunk->next = chunk->next_chunk()->next_chunk();
        if (chunk->next_chunk() != nullptr)
            chunk->next_chunk()->prev = chunk;
 
    }
}
 
size_t BumpAllocator::amount_used() {
 
    size_t result = 0;
 
    // Loop through all the chunks and add up the size of the allocated chunks
    for (chunk_header_t* chunk = m_first_memory_chunk; chunk != nullptr; chunk = chunk->next_chunk())
        if (chunk->allocated)
            result += chunk->size;
 
    return result;
}
 
size_t BumpAllocator::align(size_t size) {
 
    return (size + CHUNK_ALIGNMENT - 1) / CHUNK_ALIGNMENT * CHUNK_ALIGNMENT;
}