The concept of an allocator is to control memory flow using a model or strategy, it abstract the data and function to objects that will manage the memory or just call malloc/free function inside them. This is a good practice in C++, creating allocators to support the system you are making. It is common in game engine, for example, to create different heap allocators for target platforms instead of using global static functions to allocate/deallocate. And as a type it can be used in generic types or instances in an object to be able to allocate memory inside the system that requires it.
So, in the previous post, I showed you global simple functions to allocate/free memory, and these can be adapted to an simple allocator.
#define UNUSED(X) (void)X
class WindowsAllocator
{
public:
void* Allocate(size_t Size, size_t Alignment = sizeof(std::align_t))
{
// return malloc(Size);
return _aligned_malloc(Size, Alignment);
}
void Deallocate(void* Ptr, size_t Size)
{
UNUSED(Size);
//free(Ptr);
_aligned_free(Ptr);
}
};
This is a simple way to make it just to we sort of visualize the design. Here’s a WindowsAllocator allocator design to handle allocation/deallocate based in windows aligned api. When the allocator is done we can apply it to containers or other classes that will need it.
template < typename T, typename TAllocator >
class DynamicArrayImpl
{
T* mData{};
TAllocator mAllocator{};
/* REST OF THE CODE */
};
#if _WIN32
using PlatformAllocator = WindowsAllocator;
template < typename T, typename TAllocator = PlatformAllocator >
using DynamicArray = DynamicArrayImpl<T, TAllocator>;
#endif
template < typename TAllocator = PlatformAllocator >
class Texture2DAllocator : private TAllocator
{
void* mData = TAllocator::Allocate(1024*1024*64);
};
template < typename TAllocator = Texture2DAllocator >
class Texture2D
{
};
Here’s an exemple of an allocator inside a dynamic array container, and after there is an auto setup of dynamic array type and a platform allocator compiled just for windows os.
By design its good to allocator be composable, so it can be used inside other allocators. I’ll show and talk about some allocators that I believe to be useful and interesting.
Here’s the list:
Fallback
A fallback allocator basically is a template class that has two type names for allocators, the first is the main one, and the second is the one that runs when the main one doesn’t run correctly.
struct MemoryBlock
{
uint8_t* Ptr;
size_t Size;
};
template < typename TFirstAllocator, typename TSecondAllocator >
class FallbackAllocator : private TFirstAllocator, private TSecondAllocator
{
public:
MemoryBlock Allocate(size_t Size, size_t Alignment = sizeof(std::max_align_t))
{
MemoryBlock lMemoryBlock = TFirstAllocator::Allocate(Size, Alignment);
if(!lMemoryBlock.Ptr) lMemoryBlock = TSecondAllocator::Allocate(Size, Alignment);
return lMemoryBlock;
}
void Deallocate(MemoryBlock Mb)
{
if(TFirstAllocator::Owns(Mb)) TFirstAllocator::Deallocate(Mb);
else TSecondAllocator::Deallocate(Mb);
}
[[nodiscard]] bool Owns(MemoryBlock Mb) const
{
return TFirstAllocator::Owns(Mb) || TSecondAllocator::Owns(Mb);
}
};
The Allocate function calls Allocate from first allocator if the allocation was successful, otherwise, it calls Allocate from second allocator.
The Owns function checks if an allocator owns a memory block.
The Deallocate function checks if memory block is owned by first allocator, if so, it calls Deallocate, otherwise, it calls Deallocate from second allocator.
This is a very powerful composable allocator, we can even stack up allocators.
using Allocator = FallbackAllocator<FallbackAllocator<LinearAllocator, Sallocator>, Mallocator>;
In this case, the allocations will occur from LinearAllocator until the buffer is full, after Sallocator until the buffer is full, at last, it will use malloc from Mallocator.
Mallocator
A mallocator follows the same design above but with malloc/free functions.
class Mallocator
{
public:
MemoryBlock Allocate(size_t Size, size_t Alignment = sizeof(std::max_align_t))
{
UNUSED(Alignment);
return MemoryBlock{static_cast<uint8_t*>(malloc(Size)), Size};
}
void Deallocate(MemoryBlock& Mb)
{
free(Mb.Ptr);
Mb = {};
}
[[nodiscard]] bool Owns(MemoryBlock Mb) const { return true; }
};
So we can also make a platform mallocator.
class WindowsMallocator
{
public:
MemoryBlock Allocate(size_t Size, size_t Alignment = sizeof(std::max_align_t))
{
return MemoryBlock{static_cast<uint8_t*>(_aligned_malloc(Size, Alignment)), Size};
}
void Deallocate(MemoryBlock& Mb)
{
_aligned_free(Mb.Ptr);
Mb = {};
}
[[nodiscard]] bool Owns(MemoryBlock Mb) const { return true; }
};
#if _WIN32
using PlatformMallocator = WindowsMallocator;
#endif
Sallocator
A stack allocator has a fixed memory buffer allocated in stack and a cursor, every allocation the cursor is moved forward.
template < size_t N >
class StackAllocator
{
uint8_t mData[N] = {};
uint8_t* mCursor{}, *mEnd{};
public:
StackAllocator() : mCursor{mData}, mEnd{mData + N} {}
public:
MemoryBlock Allocate(size_t Size, size_t Alignment = sizeof(std::max_align_t))
{
const auto lAlignedSize = RoundToAligned(Size, Alignment);
if(lAlignedSize > (mEnd - mCursor))
{
return MemoryBlock{};
}
void* lPtr = mCursor;
mCursor += lAlignedSize;
return MemoryBlock{lPtr, Size};
}
void Deallocate(MemoryBlock& Mb)
{
if(Mb.Ptr + RoundToAligned(Mb.Size) == mCursor)
{
mCursor = Mb.Ptr;
}
Mb = {};
}
void DeallocateAll()
{
mCursor = mData;
}
[[nodiscard]] bool Owns(MemoryBlock Mb) const
{
return Mb.Ptr >= mData && Mb.Ptr < mEnd;
}
private:
static size_t RoundToAligned(size_t Size, size_t Alignment)
{
return ((Size + (Alignment - 1)) & ~(Alignment - 1));
}
};
Notice that the deallocation only works for the last allocated block. The allocation occurs if rounded aligned size is greater than the remaining size from the buffer.
That’s it for the basic allocators. In the part 2 I will talk about and implement pool allocators, free list allocator and others useful ones.