I've spent quite a while (and probably far longer than I actually should) trying to design an allocator system. I've bounced ideas around to various people in the past, but never really gotten something satisfactory.
Basically, the requirements I'm trying to target are:
- Composability -- allocators that seamlessly allocate from memory allocated by other allocators. This helps me to do things like, for example, write an allocator that pads allocations from its parent allocator with bit patterns to detect heap corruption. It also allows me to easily create spillovers, or optionally assert on overflow with specialized fallbacks.
- Handling the fact that some allocators have different interfaces than others in an elegant way. For example, a regular allocator might have Allocate/Deallocate, but a linear allocator can't do itemized deallocation (but can deallocate everything at once).
- I want to be able to tell how much I've allocated, and how much of that is actually being used. I also want to be able to bucket that on subsystem, but as far as I can tell, that doesn't really impact the design outside of adding a new parameter to allocate calls.
Note: I'm avoiding implementation of allocation buckets and alignment from this, since it's largely orthogonal to what I'm asking and can be done with any of the designs.
To meet those three requirements, I've come up with the following solutions, all of which have significant drawbacks.
Static Policy-Based Allocators
I originally built this off of this talk.
Examples;
struct AllocBlock
{
std::byte* ptr;
size_t size;
};
class Mallocator
{
size_t allocatedMemory;
public:
Mallocator();
AllocBlock Allocate(size_t size);
void Deallocate(AllocBlock blk);
};
template <typename BackingAllocator, size_t allocSize>
class LinearAllocator : BackingAllocator
{
AllocBlock baseMemory;
char* ptr;
char* end;
public:
LinearAllocator() : baseMemory(BackingAllocator::Allocate(allocSize)) { /* stuff */ }
AllocBlock Allocate(size_t size);
};
template <typename BackingAllocator, size_t allocSize>
class PoolAllocator : BackingAllocator
{
AllocBlock baseMemory;
char* currentHead;
public:
PoolAllocator() : baseMemory(BackingAllocator::Allocate(allocSize)) { /* stuff */ }
void* Allocate(); // note the different signature.
void Deallocate(void*);
};
// ex: auto allocator = PoolAllocator<Mallocator, size>;Advantages:
- SFINAE gives me a pseudo-duck-typing thing. I don't need any kind of common interfaces, and I'll get a compile-time error if I try to do something like create a LinearAllocator backed by a PoolAllocator.
- It's composable.
Disadvantages:
- Composability is type composability, meaning every allocator I create has an independent chain of compositions. This makes tracking memory usage pretty hard, and presumably can cause me external fragmentation issues. I might able to get around this with some kind of singleton kung-fu, but I'm unsure as I don't really have any experience with them.
- Owing to the above, all of my customization points have to be template parameters because the concept relies on empty constructors. This isn't a huge issue, but it makes defining allocators cumbersome.
Dynamic Allocator Dependency
This is probably just the strategy pattern, but then again everything involving polymorphic type composition looks like the strategy pattern to me. ?
Examples:
struct AllocBlock
{
std::byte* ptr;
size_t size;
};
class Allocator
{
virtual AllocBlock Allocate(size_t) = 0;
virtual void Deallocate(AllocBlock) = 0;
};
class Mallocator : Allocator
{
size_t allocatedMemory;
public:
Mallocator();
AllocBlock Allocate(size_t size);
void Deallocate(AllocBlock blk);
};
class LinearAllocator
{
Allocator* backingAllocator;
AllocBlock baseMemory;
char* ptr;
char* end;
public:
LinearAllocator(Allocator* backingAllocator, size_t allocSize)
: backingAllocator(backingAllocator) { baseMemory = backingAllocator->Allocate(allocSize); /* stuff */ }
AllocBlock Allocate(size_t size);
};
class PoolAllocator
{
Allocator* backingAllocator;
AllocBlock baseMemory;
char* currentHead;
public:
PoolAllocator(Allocator* backingAllocator, size_t allocSize)
: backingAllocator(backingAllocator) { baseMemory = backingAllocator->Allocate(allocSize); /* stuff */ }
void* Allocate(); // note the different signature.
void Deallocate(void*);
};
// ex: auto allocator = PoolAllocator(someGlobalMallocator, size);There's an obvious problem with the above: Namely that PoolAllocator and LinearAllocator don't inherit from the generic Allocator interface. They can't, because their interfaces provide different semantics. There's to ways I can solve this:
- Inherit from Allocator anyway and assert on unsupported operations (delegates composition failure to runtime errors, which I'd rather avoid).
- As above: Don't inherit and just deal with the fact that some composability is lost (not ideal, because it means you can't do things like back a pool allocator with a linear allocator)
As for the overall structure, I think it looks something like this:
Advantages:
- Memory usage tracking is easy, since I can use the top-level mallocator(s) to keep track of total memory allocated, and all of the leaf allocators to track of used memory. How to do that in particular is outside the scope of what I'm asking about, but I've got some ideas.
- I still have composability
Disadvantages:
- The interface issues above. There's no duck-typing-like mechanism to help here, and I'm strongly of the opinion that programmer errors in construction like that should fail at compile-time, not runtime.
Composition on Allocated Memory instead of Allocators
This is probably going to be somewhat buggy and poorly thought, since it's just an idea rather than something I've actually tried.
Examples:
struct AllocBlock
{
void* ptr;
size_t size;
std::function<void()> dealloc;
}
class Mallocator
{
size_t allocatedMemory;
public:
Mallocator();
AllocBlock Allocate(size_t size) { void* ptr = malloc(size); return {ptr, size, [ptr](){ free(ptr); }}; }
};
class LinearAllocator
{
AllocBlock baseMemory;
char* ptr;
char* end;
public:
LinearAllocator(AllocBlock baseMemory) : baseMemory(baseMemory) {end = ptr = baseMemory.ptr;}
AllocBlock Allocate(size_t);
};
class PoolAllocator
{
AllocBlock baseMemory;
char* head;
public:
PoolAllocator(AllocBlock baseMemory) : baseMemory(baseMemory) { /* stuff */ }
void* Allocate();
};
// ex: auto allocator = PoolAllocator(someGlobalMallocator.Allocate(size));
I don't really like this design at first blush, but I haven't really tried it.
Advantages:
- "Composable", since we've delegated most of what composition entails into the memory block rather than the allocator.
- Tracking memory is a bit more complex, but I *think* it's still doable.
Disadvantages:
- Makes the interface more complex, since we have to allocate first and then pass that block into our "child" allocator.
- Can't do specialized deallocation (i.e. stack deallocation) since the memory blocks don't know anything about their parent allocation pool. I might be able to get around this though.
I've done a lot of research against all of the source-available engines I can find, and it seems like most of them either have very small allocator systems or simply don't try to make them composable at all (CryEngine does this, for example). That said, it seems like something that should have a lot of good examples, but I can't find a whole lot. Does anyone have any good feedback/suggestions on this, or is composability in general just a pipe dream?
