This post is part of my Memory Management Series.
In part 1 of this series I showed how to implement a memory allocator that allocates fix-sized pages and blocks. Part 2 is going to cover how to implement a C-style interface like malloc
and free
that can deal with variable-sized memory allocation using this allocator. In the end, I’ll also show a way to add syntactic sugar by creating C++ function templates.
The C-Style Interface
So far, our allocator can only allocate fix-sized pages and blocks. Therefore, we need at least one individual allocator object for one specific block size. So how are we going to deal with variable-sized memory allocation? Well, we are not going to modify the allocator. Instead, we’re going to have a collection of allocators that allocate a wide range of different-sized memory blocks, and we will also build a look-up table to efficiently determine which allocator to use based on the memory block size requested by the client. This look-up table approach was inspired by a Randy Gaul, one of my classmates at DigiPen. You can check out his implementation here: header / source.
This is the interface we will be implementing:
// allocates variable-sized memory blocks void *Allocate(unsigned size); // frees variable-sized memory blocks void Free(void *p, unsigned size);
And the client code uses this interface like this. Note the use of C-style casts.
// allocate memory unsigned *i = (unsigned *) Allocate(sizeof(unsigned); // manipulate memory *i = 0u; // free memory Free(i, sizeof(unsigned));
Block Size Look-Up Table
In order to build the look-up table for different block sizes, we need an array of different block sizes. This information is something the client doesn’t need to know, and is local to the translation unit (i.e. the source file), so we’re going to use static data. The choice of block sizes depends on your application.
// sorted from smallest to largest static const unsigned k_blockSizes[] = { // 4-increments 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, // 32-increments 128, 160, 192, 224, 256, 288, 320, 352, 384, 416, 448, 480, 512, 544, 576, 608, 640, // 64-increments 704, 768, 832, 896, 960, 1024 };
Here I use the prefix k_
to denote constant data; on the other hand, the prefix s_
is used for static non-constant data. I picked up this naming convention recently, and I like it because it is Intellisense friendly: in Visual Studio, I can type the prefix to quickly filter out unwanted code hints.
Several extra constants are defined to aid the allocator initialization:
static const unsigned k_pageSize = 8192; static const unsigned k_alignment = 4; // number of elements in the block size array static const unsigned k_numBlockSizes = sizeof(k_blockSizes) / sizeof(k_blockSizes[0]); // largest valid block size static const unsigned k_maxBlockSize = k_blockSizes[k_numBlockSizes - 1];
Next, we store the look-up table as a static array, and we create a static array of allocators corresponding to the block size array:
static unsigned *s_blockSizeLookup = nullptr; static Allocator s_allocators[k_numBlockSizes];
The Look-Up Helper Function
We can now implement a helper function for looking up the appropriate allocator with a requested data size. The allocator returned by this function is the one that allocates the smallest block size that is no less than the requested data size. Since this function is also for internal use only, we declare it as static. If the requested data size is too large, we fall back to using malloc
. You can of course choose to dynamically create allocators to handle larger data sizes, but here I just want to keep things simple and easier to manage.
static Allocator *LookUpAllocator(unsigned size) { // one-time initialization static bool s_initialized = false; if (!s_initialized) { // initialize block size lookup s_blockSizeLookup = new unsigned[k_maxBlockSize + 1]; unsigned j = 0; for (unsigned i = 0; i <= k_maxBlockSize; ++i) { if (i > k_blockSizes[j]) ++j; s_blockSizeLookup[i] = j; } // initialize allocators for (unsigned i = 0; i < k_numBlockSizes; ++i) { s_allocators[i].Reset (k_blockSizes[i], k_pageSize, k_alignment); } s_initialized = true; } // check eligibility for lookup if (size <= k_maxBlockSize) return s_allocators + s_blockSizeLookup[size]; else return nullptr; }
The Allocate
& Free
Functions
Finally, the Allocate
and Free
functions are as simple as calling LookUpAllocator
to retrieve the proper allocator or falling back to malloc
and free
if the requested data size is too large.
void *Allocate(unsigned size) { Allocator *alloc = LookupAllocator(size); if (alloc) return alloc->Allocate(); else return std::malloc(size); } void Free(void *p, unsigned size) { Allocator *alloc = LookupAllocator(size); if (alloc) alloc->Free(p); else std::free(p); }
Syntactic Sugar
The Allocate
and Free
functions still use void
pointers. Also, a data size is required by the Free
function. Woudn’t it be nice if we don’t have to perform type casts and provide type sizes in the client code? Here I’m going to show one way to achieve such syntactic sugar by creating function templates.
This is what we’d expect:
// allocate memory unsigned *i = New<unsigned>(); // manipulate memory *i = 0u; // free memory Delete(i);
We can always choose to overload the new
and delete
operators so that existing client code is not affected. But I’m just going to go ahead to show the function template approach, and you may base the overloaded operators on top of that.
The New
function templates uses the placement new operator and passes the correct data size using the sizeof
operator to the Allocate
function. Without C++ 11, you’ll need multiple templates for different number of constructor arguments. With C++ 11, you can just have one variadic template.
// 0 argument template <typename T> T *New(void) { return new (Allocate(sizeof(T))) T(); } // 1 argument template <typename T, typename A0> T *New(A0 a0) { return new (Allocate(sizeof(T))) T(a0); } // 2 arguments template <typename T, typename A0, typename A1> T *New(A0 a0, A1 a1) { return new (Allocate(sizeof(T))) T(a0, a1); } // ...and so on
The function template for Delete
invokes the destructor based on the type of pointers passed in, and then forward the pointer to the Free
function.
template <typename T> void Delete(T *p) { reinterpret_cast<T *>(p)->~T(); Free(p, sizeof(T)); }
Done!
This concludes the second part of this series. See you in part 3 🙂