slang-memory-arena.cpp
#include "slang-memory-arena.h"
namespace Slang {
MemoryArena::MemoryArena()
{
// Mark as invalid so any alloc call will fail
m_blockAlignment = 0;
m_blockAllocSize = 0;
// Set up as empty
m_usedOddBlocks = nullptr;
m_availableBlocks = nullptr;
_resetCurrentBlock();
m_blockFreeList.init(sizeof(Block), sizeof(void*), 16);
}
MemoryArena::~MemoryArena()
{
reset();
}
MemoryArena::MemoryArena(size_t blockPayloadSize, size_t blockAlignment)
{
_initialize(blockPayloadSize, blockAlignment);
}
void MemoryArena::init(size_t blockPayloadSize, size_t blockAlignment)
{
reset();
_initialize(blockPayloadSize, blockAlignment);
}
void MemoryArena::_initialize(size_t blockPayloadSize, size_t alignment)
{
// Alignment must be a power of 2
assert(((alignment - 1) & alignment) == 0);
// Must be at least sizeof(void*) in size, as that is the minimum the backing allocator will be
alignment = (alignment < kMinAlignment) ? kMinAlignment : alignment;
m_blockPayloadSize = blockPayloadSize;
size_t blockAllocSize = blockPayloadSize;
// If alignment required is larger then the backing allocators then
// make larger to ensure when alignment correction takes place it will be aligned
if (alignment > kMinAlignment)
{
blockAllocSize += alignment;
}
m_blockAllocSize = blockAllocSize;
m_blockAlignment = alignment;
m_availableBlocks = nullptr;
m_usedOddBlocks = nullptr;
m_blockFreeList.init(sizeof(Block), sizeof(void*), 16);
_resetCurrentBlock();
}
void MemoryArena::_resetCurrentBlock()
{
m_start = nullptr;
m_end = nullptr;
m_current = nullptr;
m_usedBlocks = nullptr;
}
void MemoryArena::_addCurrentBlock(Block* block)
{
// Set up for allocation from
m_end = block->m_end;
m_start = block->m_start;
m_current = m_start;
// Add to linked list of used block, making it the top used block
block->m_next = m_usedBlocks;
m_usedBlocks = block;
}
void MemoryArena::_deallocateBlocksPayload(Block* start)
{
Block* cur = start;
while (cur)
{
// Deallocate the block
::free(cur->m_alloc);
cur = cur->m_next;
}
}
void MemoryArena::_deallocateBlocks(Block* start)
{
Block* cur = start;
while (cur)
{
Block* next = cur->m_next;
// Deallocate the block
::free(cur->m_alloc);
m_blockFreeList.deallocate(cur);
cur = next;
}
}
/* static */MemoryArena::Block* MemoryArena::_joinBlocks(Block* pre, Block* post)
{
if (pre && post)
{
// If both are actual lists, concat post at end of pre
Block* cur = pre;
while (cur->m_next)
{
cur = cur->m_next;
}
// Attach post to end of pre
cur->m_next = post;
}
return pre ? pre : post;
}
void MemoryArena::deallocateAll()
{
// Free all oversized
_deallocateBlocks(m_usedOddBlocks);
m_usedOddBlocks = nullptr;
// We want to put used blocks onto the start of the available list
m_availableBlocks = _joinBlocks(m_usedBlocks, m_availableBlocks);
// Reset current block
_resetCurrentBlock();
}
void MemoryArena::reset()
{
_deallocateBlocksPayload(m_usedOddBlocks);
_deallocateBlocksPayload(m_usedBlocks);
_deallocateBlocksPayload(m_availableBlocks);
m_blockFreeList.reset();
m_usedOddBlocks = nullptr;
m_availableBlocks = nullptr;
_resetCurrentBlock();
}
const MemoryArena::Block* MemoryArena::_findNonCurrent(const void* data, size_t size) const
{
// It must either be m_usedOversizedBlocks or after m_usedBlocks (because m_usedBlocks is m_current)
const Block* block = _findInBlocks(m_usedOddBlocks, data, size);
if (block)
{
return block;
}
return m_usedBlocks ? _findInBlocks(m_usedBlocks->m_next, data, size) : nullptr;
}
const MemoryArena::Block* MemoryArena::_findInBlocks(const Block* block, const void* data, size_t size) const
{
const uint8_t* ptr = (const uint8_t*)data;
while (block)
{
if (ptr >= block->m_start && ptr + size <= block->m_end)
{
return block;
}
block = block->m_next;
}
return nullptr;
}
MemoryArena::Block* MemoryArena::_newNormalBlock()
{
if (m_availableBlocks)
{
// We have an available block..
Block* block = m_availableBlocks;
m_availableBlocks = block->m_next;
return block;
}
return _newBlock(m_blockAllocSize, m_blockAlignment);
}
MemoryArena::Block* MemoryArena::_newBlock(size_t allocSize, size_t alignment)
{
assert(alignment >= m_blockAlignment);
// Allocate block
Block* block = (Block*)m_blockFreeList.allocate();
if (!block)
{
return nullptr;
}
// Allocate the memory
uint8_t* alloc = (uint8_t*)::malloc(allocSize);
if (!alloc)
{
m_blockFreeList.deallocate(block);
return nullptr;
}
const size_t alignMask = alignment - 1;
// Do the alignment on the allocation
uint8_t* const start = (uint8_t*)((size_t(alloc) + alignMask) & ~alignMask);
// Setup the block
block->m_alloc = alloc;
block->m_start = start;
block->m_end = alloc + allocSize;
block->m_next = nullptr;
return block;
}
void* MemoryArena::_allocateAlignedFromNewBlockAndZero(size_t sizeInBytes, size_t alignment)
{
void* mem = _allocateAlignedFromNewBlock(sizeInBytes, alignment);
if (mem)
{
::memset(mem, 0, sizeInBytes);
}
return mem;
}
void* MemoryArena::_allocateAlignedFromNewBlock(size_t size, size_t alignment)
{
// Make sure init has been called (or has been set up in parameterized constructor)
assert(m_blockAllocSize > 0);
// Alignment must be a power of 2
assert(((alignment - 1) & alignment) == 0);
// Alignment must at a minimum be block alignment (such if reused the constraints hold)
alignment = (alignment < m_blockAlignment) ? m_blockAlignment : alignment;
const size_t alignMask = alignment - 1;
// The size of the block must be at least large enough to take into account alignment
size_t allocSize = (alignment <= kMinAlignment) ? size : (size + alignment);
const size_t currentRemainSize = size_t(m_end - m_current);
// a) Allocate a new normal block and make current
// b) Allocate a new normal block (leave current)
// c) Allocate a new 'oversized' block (leave current)
//
// We only bother with a and c here, as b is only really usable if size is close to m_blockAllocSize
// If there is > 1/3 of block remaining, or the block required is too big to fit use an 'oversized' block
if ((currentRemainSize * 3 > m_blockPayloadSize) || (allocSize > m_blockAllocSize))
{
// We don't change current because there is enough remaining
Block* block = _newBlock(allocSize, alignment);
if (!block)
{
return nullptr;
}
// Add to odd used blocks list
block->m_next = m_usedOddBlocks;
m_usedOddBlocks = block;
// NOTE! We are keeping the previous m_current current, so any remaining space can still be used
// Return the address
return block->m_start;
}
// Must be allocatable within a normal block
assert(allocSize <= m_blockAllocSize);
Block* block = _newNormalBlock();
if (!block)
{
return nullptr;
}
// It's a new regular block...
_addCurrentBlock(block);
// Do the aligned allocation (which must fit) by aligning the pointer
uint8_t* memory = (uint8_t*)((size_t(m_current) + alignMask) & ~alignMask);
// It must fit if the previous code is correct...
assert(memory + size <= m_end);
// Move the current pointer
m_current = memory + size;
return memory;
}
size_t MemoryArena::_calcBlocksUsedMemory(const Block* block) const
{
size_t total = 0;
while (block)
{
total += size_t(block->m_end - block->m_start);
block = block->m_next;
}
return total;
}
size_t MemoryArena::_calcBlocksAllocatedMemory(const Block* block) const
{
size_t total = 0;
while (block)
{
total += size_t(block->m_end - block->m_alloc);
block = block->m_next;
}
return total;
}
size_t MemoryArena::calcTotalMemoryUsed() const
{
return _calcBlocksUsedMemory(m_usedOddBlocks)
+ (m_usedBlocks ? _calcBlocksUsedMemory(m_usedBlocks->m_next) : 0) +
size_t(m_current - m_start);
}
size_t MemoryArena::calcTotalMemoryAllocated() const
{
return _calcBlocksAllocatedMemory(m_usedOddBlocks) +
_calcBlocksAllocatedMemory(m_usedBlocks) +
_calcBlocksAllocatedMemory(m_availableBlocks);
}
} // namespace Slang