Custom memory allocators are a very popular solution to the problem of memory management in C++. Unfortunately, operator new isn’t ideally suited to this strategy. In this article I will discuss some of the practical issues that arise when using custom allocators in conjunction with new, and outline the requirements for the implementation I developed for my hobby projects.
The interface of a typical allocator will probably look something like this:
class Allocator { public: virtual ~Allocator (); virtual void* Allocate (usize size, usize align) = 0; virtual void Deallocate(void* ptr) = 0; };
As an unrepentant template enthusiast, I ended up with something more along these lines:
class Allocator { public: virtual ~Allocator (); template <class T> T* Allocate (usize size = sizeof(T), usize align = alignof(T)) { return (T*)OnAllocate(size, align); } template <class T> void Deallocate(T*& ptr) { OnDeallocate(ptr); ptr = 0; } template <class T> void Deallocate (const T*& ptr) { Deallocate(const_cast<T*&>(ptr)); } private: virtual void* OnAllocate (size_t size, size_t align) = 0; virtual void OnDeallocate(void* ptr) = 0; };
Now, the most obvious way to initialize an object returned by such an allocator is to use placement new as follows:
Foo* foo = new(allocator.Allocate<Foo>()) Foo(10); // foo around a bit... foo->~Foo(); allocator.Deallocate(foo);
This isn’t too terribly heartbreaking at first sight, but it’s not exactly elegant either. However, let’s take a closer look at some of the problems this approach introduces.
First, the placement new expression is a bit unwieldy. You may start to wish I had slimmed down my method name to alloc() just to condense things a bit. But the real problem here is that we have to specify Foo twice to get what we want – both enough space in memory, and the correct constructor. Sooner or later, someone will Allocate<Foo>() then proceed to construct Bar(10, 20) instead. Congratulations, someone! You are now the proud father of a brand new baby bug! And, Junior probably just vomited 20 all over some very important allocator metadata, or possibly even the next object’s precious vtable.
Second, we have to remember to both explicitly call the destructor, and deallocate the memory. Worse, we had better remember to do both of those things on every code path that exits the local scope. So, we’ve actually conceived a whole family of future bugs here. We now have all the problems we would normally have with delete, but we’ve managed to make the equivalent expression substantially more complex, increasing the odds that someone will forget or break one of these two constraints.
Third, we have to ensure that we use the same allocator to acquire and release foo. Now, this doesn’t seem so egregious here at the local scope level, but how do we maintain this invariant when we want to return foo, e.g. from a factory method?
Mo Methods, Mo Problems
On the BitSquid blog, fellow #AltDev Niklas Frykholm suggests a solution to the expression complexity problems from the first two points above. You could add some helper methods to our base Allocator class:
class Allocator { public: template <class T, class P1> T* New (const P1& p1) { return new (Allocate<T>()) T(p1); } template <class T> void Delete(T *ptr) { if (ptr) { ptr->~T(); Deallocate(ptr); } } };
Which would tidy up our earlier example:
Foo* foo = allocator.New<Foo>(10); // foo around a bit... allocator.Delete(foo);
Unfortunately, Allocator::New<T,…>(…) is actually a family of methods, and a rather large family at that. Since you need both overloads of this method, where n is the maximum number of constructor arguments you are willing to support.
With some clever macros, you can make this semi-manageable, but this really doesn’t solve many of our original problems. In fact, this solution is still worse than good old-fashioned new and delete, when we had only a single shared heap to deal with.
Our allocators don’t distinguish between objects and arrays, so we need to avoid applying Delete() to a pointer allocated as an array. Another devilish detail you may not notice immediately is that New() and Delete() cannot be used to call private or protected constructors or destructors (e.g. private nested classes) unless those classes explicitly befriend our Allocator.
Have no fear, Underdog is here
Ideally, we would like an implementation that will:
- Provide a simple, concise new-like mechanism capable of invoking constructors with arbitrary argument lists, regardless of the enclosing protection scope;
- Formalize the relationship between the pointer itself, and the allocator that produced it;
- Ensure that allocated memory is subsequently deallocated by the appropriate allocator along any code path;
- Clearly indicate cases where the lifetime responsibility for a returned pointer is being passed to the caller;
- Distinguish between object pointers and array pointers;
- Not require any additional storage per pointer;
Clearly, the solution is an:
Next time I will get into the implementation details. Don’t worry, I managed to keep the template and macro magic reasonably simple.
As for Mike’s challenge to face my fear of looking stupid… that’s what I’ve been doing here from day one :)