MaxOS::memory::allocator::BumpAllocator Class Reference

Basic doubly linked list bump memory allocator. More...

#include <bump.h>

Inheritance diagram for MaxOS::memory::allocator::BumpAllocator:

Public Member Functions
	BumpAllocator ()
	Creates a new bump memory allocator.
virtual	~BumpAllocator ()
	Destructs a Bump memory allocator.
void	setup_region (uintptr_t address, size_t length) final
	Setup a region to be bump memory managed, creates a free chunk represent the whole region.
void *	allocate (size_t size) final
	Allocates a block of memory.
void	unallocate (void *pointer) final
	Frees a block of memory.
size_t	amount_used () final
	Returns the amount of memory used.
size_t	align (size_t size) final
	Aligns the size to the chunk alignment.
Public Member Functions inherited from MaxOS::memory::allocator::MemoryAllocator
	MemoryAllocator ()
virtual	~MemoryAllocator ()

Detailed Description

Basic doubly linked list bump memory allocator.

Definition at line 47 of file bump.h.

Constructor & Destructor Documentation

BumpAllocator()

BumpAllocator::BumpAllocator

(

)

Creates a new bump memory allocator.

Definition at line 14 of file bump.cpp.

                             {
    static_assert(CHUNK_HEADER_SIZE == sizeof(chunk_header_t));
};

Member Function Documentation

align()

size_t BumpAllocator::align ( size_t  size )

finalvirtual

Aligns the size to the chunk alignment.

Parameters

size	The size to align

Returns

The aligned size

Reimplemented from MaxOS::memory::allocator::MemoryAllocator.

Definition at line 290 of file bump.cpp.

                                       {
 
    return (size + CHUNK_ALIGNMENT - 1) / CHUNK_ALIGNMENT * CHUNK_ALIGNMENT;
}

Referenced by allocate().

allocate()

void * BumpAllocator::allocate ( size_t  size )

finalvirtual

Allocates a block of memory.

Parameters

size	The size of the block to allocate

Returns

A pointer to the block, or nullptr if no block is available

Reimplemented from MaxOS::memory::allocator::MemoryAllocator.

Definition at line 144 of file bump.cpp.

                                         {
 
    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);
}

References align(), MaxOS::memory::allocator::ChunkHeader::allocated, MaxOS::memory::allocator::ChunkHeader::canary, MaxOS::memory::allocator::ChunkHeader::next, MaxOS::memory::allocator::ChunkHeader::next_chunk(), MaxOS::memory::allocator::ChunkHeader::prev, and MaxOS::memory::allocator::ChunkHeader::size.

Referenced by MaxOS::memory::MemoryManager::kmalloc(), MaxOS::memory::MemoryManager::malloc(), and MaxOS::processes::Thread::Thread().

amount_used()

size_t BumpAllocator::amount_used ( )

finalvirtual

Returns the amount of memory used.

Returns

The amount of memory used

Reimplemented from MaxOS::memory::allocator::MemoryAllocator.

Definition at line 272 of file bump.cpp.

                                  {
 
    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;
}

References MaxOS::memory::allocator::ChunkHeader::next_chunk().

setup_region()

void BumpAllocator::setup_region ( uintptr_t  address, size_t  length  )

finalvirtual

Setup a region to be bump memory managed, creates a free chunk represent the whole region.

Parameters

address	The start of the region
length	The length of the region

Reimplemented from MaxOS::memory::allocator::MemoryAllocator.

Definition at line 122 of file bump.cpp.

                                                                 {
 
    // 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;
 
}

References MaxOS::memory::allocator::ChunkHeader::allocated, MaxOS::memory::allocator::ChunkHeader::canary, MaxOS::memory::allocator::ChunkHeader::next, MaxOS::memory::allocator::ChunkHeader::prev, and MaxOS::memory::allocator::ChunkHeader::size.

Referenced by MaxOS::processes::resources::BridgeHandler::BridgeHandler(), and MaxOS::memory::BumpMemoryManager::BumpMemoryManager().

unallocate()

void BumpAllocator::unallocate ( void *  pointer )

finalvirtual

Frees a block of memory.

Parameters

pointer

A pointer to the block

Reimplemented from MaxOS::memory::allocator::MemoryAllocator.

Definition at line 212 of file bump.cpp.

                                            {
 
    // 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;
 
    }
}

References MaxOS::memory::allocator::ChunkHeader::prev_chunk(), and MaxOS::memory::allocator::ChunkHeader::size.

Referenced by MaxOS::memory::MemoryManager::free(), MaxOS::memory::MemoryManager::kfree(), and MaxOS::processes::resources::BridgeHandler::send_to_bridge().

---

The documentation for this class was generated from the following files:

• /home/runner/work/MaxOS/MaxOS/kernel/include/memory/allocator/bump.h
• /home/runner/work/MaxOS/MaxOS/kernel/src/memory/allocator/bump.cpp