Fixed size Memory Pool Implementation

Question

Here is an attempt at implementing a fixed size Memory Pool¹:

pool.h

#ifndef Pool_h
#define Pool_h

template <typename T, size_t N>                             // memory type, number of blocks
class Pool
{
protected:
    typedef T* pointer_type;
    typedef const T* const_pointer_type;
    typedef size_t size_type;

public:
    Pool();                                                 // default constructor
    ~Pool();                                                // destructor

    pointer_type AddrFromIndex(size_type i) const;          // address of i-th block
    size_type IndexFromAddr(const_pointer_type ptr) const;  // subscript operator [ ]

    pointer_type get();                                     // get a memory block
    void free(pointer_type ptr, size_type size = 0);        // free a memory block

private:
    size_type num_of_blocks;                                // number of identical memory blocks
    size_type size_of_each_block;                           // size of each(every) memory block
    size_type num_of_free_blocks;                           // number of free blocks
    size_type num_of_init_blocks;                           // number of blocks been allocated

    pointer_type data;                                      // base(start) address of memory 
    pointer_type next;                                      // next free memory block
};

#include "pool_def.cpp"

#endif

pool_def.cpp

//----------------------------------------------------------------------

template <typename T, size_t N> 
Pool<T, N>::Pool()                                                       
    : num_of_blocks(N), size_of_each_block(sizeof(T)),
      num_of_free_blocks(N), num_of_init_blocks(0),
      data (new T[N]), next(data)
{

}

//----------------------------------------------------------------------

template <typename T, size_t N> 
Pool<T, N>::~Pool()                                                      
{
    delete [] data;
    data = nullptr;
}

//----------------------------------------------------------------------

template <typename T, size_t N> 
typename Pool<T, N>::pointer_type Pool<T, N>::AddrFromIndex(size_type i) const                
{ 
    return data + (i * size_of_each_block); 
}

//----------------------------------------------------------------------

template <typename T, size_t N> 
typename Pool<T, N>::size_type Pool<T, N>::IndexFromAddr(const_pointer_type ptr) const       
{ 
    return ((size_type)(ptr - data)) / size_of_each_block; 
}

//----------------------------------------------------------------------

template <typename T, size_t N> 
typename Pool<T, N>::pointer_type Pool<T, N>::get()                                          

{
    if (num_of_init_blocks < num_of_blocks)
    {
        pointer_type p = (pointer_type) AddrFromIndex(num_of_init_blocks);
        *p = num_of_init_blocks + 1;

        ++num_of_init_blocks;
    }

    pointer_type ptr = nullptr;

    if (num_of_free_blocks > 0)
    {
        ptr = next;
        --num_of_free_blocks;

        if (num_of_free_blocks != 0)
        {
            next = AddrFromIndex(*((pointer_type)next) );
        }
        else
        {
            next = nullptr;
        }
    }

    return ptr;
}

//----------------------------------------------------------------------

template <typename T, size_t N> 
void Pool<T, N>::free(pointer_type ptr, size_type size = 0)              
{
    if (next != nullptr)
    {
        (*(size_type*)ptr) = IndexFromAddr( next );
        next = (pointer_type)ptr;
    }
    else
    {
        *((size_type*)ptr) = num_of_blocks;
        next = (pointer_type)ptr;
    }

    ++num_of_free_blocks;
}

//----------------------------------------------------------------------

Any remarks and corrections are welcome.

Questions:

1. If I want to implement a data structure² based on dynamic array: When I allocate an array of type T, of let say N elements, I'm able to do it by calling get() only once. Then by using simple pointer arithmetic (or subscript operator[]) I can access all the elements without the use of get():

   #include <iostream>
   #include "Pool.h"
   
   int main()
   {
       Pool<int, 100> p2;
       int* ptr2 = p2.get();
   
       for (size_t i = 0; i < 100; i++)
       {
           // ptr2[i] = p2.get();   <-----------------?
           ptr2[i] = i; 
       }
   
       for (size_t i = 0; i < 100; i++)
       {
           std::cout << ptr2[i] <<" "; 
       }
   
       // for loop on every element of the array or just as it is?
       p2.free(ptr2);
   
   }
   

Is the above a correct/valid use of Pool or should I call get() on every next, ptr2[i], element before I assign it a value?

2. I use Pool::free() to deallocate the chunk of 100 ints, is it a valid use or should I apply it on every single element of the array?

---

Note: The Pool is meant to be used, in the context of embedded systems programming, as an alternative of system functions/operators like malloc() or new / new [] related to free store - fragmentation, speed, predictability.

^{1. Based on: "Fast Efficient Fixed-Size Memory Pool - no loops and no overhead." B. Kenwright}

^{2. Let say a simple vector.}

---

^{Note: The original code uses the first four bytes (unsigned int) of every free memory block to store the address of the following free block of memory. This address is used to update the variable next which is a pointer to the next free memory block. The stored value is not actually an address but the variable num_of_init_blocks, which, additionally, is used as an index of the sequence of allocation of free memory blocks. num_of_init_blocks is used as an offset from the data, which is the base address.}

Answer 1

Let's start off with the header file.

Access Modifiers

Why did you choose protected for your typedefs? Usually, you'd want them to be public since they appear as the argument and return types of your functions and sometimes you might want to use them directly, e.g. when instantiating another template (for example, making a vector of pointer_types). Another thing is member ordering: Usually, when choosing the class keyword (as opposed to struct), it is suggested that you write all your private members first (since all class members are private by default, thus making the keyword unnecessary), followed by all your other members.

Methods

Why do you have two methods that use pascal case if all you other methods and members use snake case? Consistency makes your code easier to read and easier to remember, so I would suggest renaming AddrFromIndex and IndexFromAddr to addr_from_index and index_from_addr, respectively.

On another note, both of these methods seem to fulfill a purpose only relevant to other methods of Pool, but not to anybody using the class, so they probably should be private.

In addition, your comment saying // subscript operator [ ] is misleading. Firstly, you aren't actually overloading the subscript operator and secondly, the method doesn't really do what you would expect operator[] to do (e.g. it returns size_type instead of T, it takes a pointer instead of a size_type etc.). Consider adjusting the comment.

Data Members

Nearly all you data members can and should be made const, since you don't modify them at all. Actually, all members besides num_of_free_blocks, num_of_init_blocks and next should be const.

size_t

Using size_t here is right, but using it without including an appropriate header is not. Most modern compilers seem to let this error slip rather easily, but in order for your program to be standard compliant, you should include cstddef or any other header that defines it (take a look at this for more information). Also, these headers are only guaranteed to define size_t in the namespace std, but not in the global namespace, so you should replace all occurrences of it with std::size_t.

typedefs

typedef size_t size_type;

does really seem redundant, especially if you think about what the t in size_t stands for. To my mind it would be better to just omit the typedef completely and stick with std::size_t. Also, if you're using c++11 or later, using should be preferred to typedef since it is easier to read and more versatile.

Files

Including a .cpp file just seems wrong, although doing the actual implementation in a separate file is completely valid. You should change the file type extension to something more appropriate such as .h, .ipp (as used in Boost), .impl etc. In addition, choosing a different file name for header and implementation is really confusing and generally discouraged, so consider renaming pool_def.cpp to pool.[your preferred extension here].

---

Moving on to pool_def.cpp.

Constructor

Although this is a really small nitpick, if you're using c++11 or later, consider using default member initializers for all your members since they don't depend on any data you pass to the constructor. This will make your constructor redundant and your code more concise.

Destructor

Setting data to nullptr achieves nothing, since the object it belonged to is gone anyway.

Pointer Arithmetic

This line

return ((size_type)(ptr - data)) / size_of_each_block;

does not do what you think it does. First, it subtracts data from ptr which gives you the difference in terms of the number of elements, not the byte count, which you then divide by the size of each element. Consider this example:

int* a = new int[5];
int* b = a + 3;
std::cout << (std::size_t) (b - a) / sizeof(int);

Assuming that sizeof(int) equals 4, what is this program going to print? The answer is 0. First, you subtract both pointers, yielding 3 (since b points to the int 3 ints away from a), then divide it by 4, which yields 0.

An analogous problem does also occur in AddrFromIndex, so please revisit your understanding of pointer arithmetic.

Casts

You have a lot of unnecessary casts, for example

pointer_type p = (pointer_type) AddrFromIndex(num_of_init_blocks);

or

next = (pointer_type)ptr;

which you can just omit. Also, you only use c-style casts which are generally disadvised against in favor of the c++-style casts (static_cast, const_cast, reinterpret_cast, dynamic_cast) which are a lot safer and more precise in their usage. You should seek to replace them.

Program Logic/General Design

You implementation has some severe flaws. Firstly, it won't work correctly for most cases for the reasons stated above under Pointer Arithmetic. Secondly, there are parts in your code that make no apparent sense and/or are completely redundant, such as

if (num_of_init_blocks < num_of_blocks)
{
    pointer_type p = (pointer_type) AddrFromIndex(num_of_init_blocks);
    *p = num_of_init_blocks + 1;

    ++num_of_init_blocks;
}

What purpose does p save here? Excluding ++num_of_init_blocks;, every line here is redundant. Also, why are you keeping so many redundant variables? There is no need to have both num_of_init_blocks and num_of_free_blocks since you have the overall number of blocks and could just subtract one to get the other. Why do you keep next around if all you do is linear allocation and next always equals data + num_of_init_blocks + 1? Please try to answer these questions for yourself, and if you cannot come up with a good answer, please reconsider your design.

While the logic of you get method is ok, albeit a little convoluted, your free method makes next to no sense. Why do you pass a parameter size that you never use? Why do you write code like this:

(*(size_type*)ptr) = IndexFromAddr( next );
next = (pointer_type)ptr;

which contains not only two nonsensical casts but also assigns an index to next which means that next will be completely useless afterwards, achieving nothing in the process? Why do you try to assign out-of-bounds memory to next in the else case (this is at least what I'm guessing what you are trying to do, because the code doesn't make any sense), although this is undefined behaviour?

E.: Although you pass a parameter size to free, you never use it, and should thus consider omitting it. Also, both casts of the form (*(size_type*)ptr) are incorrect and violate the strict aliasing rule (since you try to alias a pointer of type T* to a pointer of type size_type*, which is only correct if T equals size_type), meaning that your program contains undefined behaviour, which is very bad. In fact, you can leave the cast out entirely and just keep the dereference operator. The same is true for the casts of the form (pointer_type)ptr; since ptr is already of type pointer_type they do nothing.

What you have written is basically a convoluted implementation of std::array with the objects living on the heap and without all the commodities such as begin()/end() etc. You definitely should read up on what the purpose of a memory pool is and why they are used (Wikipedia might offer a good start). For a start, having block sizes equal to a single element and fixing the elements' type kind of defeats the purpose of a memory pool: Since the pool is thought of as a fast alternative to malloc/new, you should at least allow different element types, and the reason the memory is allocated in blocks is that you can have simplified memory tracking and allocation/deallocation. The idea is that you give block handles to your users and say: "Okay, here you have three block, each 2048 bytes in size, do with them what you want", mark those blocks as used in some kind of block list you have and forget about them until they are returned to your supervision. In the context of embedded programming especially you might have to replace your call to new with a static memory size (in which case the use of a template parameter would be justified).

E.: The biggest problem you implementation has is that it depends on the idea of being able to write a size_type into unused blocks, which is, however, forbidden by the strict alias rule, meaning that your program has undefined behavior. One possible option to fix this would be to use a compiler feature, e.g. gcc's -fno-strict-aliasing, but that would mean that your program would neither be very portable nor actually compliant with the c++ standard. The other possibility would be to step away from the concept of using a templated type T and switch to using char arrays instead, since they are explicitly allowed to alias, and work your way around with reinterpret_cast, making sure your buffers are aligned correctly. Furthermore, I would consider taking N as a constructor rather than as a template parameter, because having the class templated with it means that you will have separate code for every Pool with a different element count, leading to binary bloat (however, if you are using the class only once or twice, having N as a template parameter might actually enable some optimizations, so this is something you should think about).

---

Especially the last paragraph might seem harsh and unfriendly, but please don't see as me trying to insult you and your code, but as me trying to help you become better. After all, code review is hard and unforgiving.

Edit: After reading the paper on which this implementation is based, I realized that my idea of implementing a pool allocator was very different from your's and I didn't recognize you way of tackling the problem, for which I am deeply sorry. I crossed out all sections that do not apply anymore and added some new sections which are prefixed with a boldfaced E.:

Answer 2

1. Most of your comments all fall into at least one of these categories:

   1. Pure busywork (//---------------------------------------------------------------------- ...)
   2. Blatantly obvious (// default constructor // destructor ...)
   3. Pointing at the need to rename things (
      // get a memory block: get() => allocate()
// next free memory block: next => free_block
      ...)
   4. Or are wrong (// subscript operator [ ]

2. There's not so much function-implementation-details that I would split it off into its own extra-file (.tcc, .icc or _impl.h).
   Anyway, using the extension .cpp is ill-advised as it's not its own translation-unit.

3. You are implementing your own default-ctor and dtor, you know you have to implement matching copy- and/or move -ctor/-assignment?
   See: What is The Rule of Three?

4. AddrFromIndex() and IndexFromAddr() seem to be implementation-details, thus they should be private.

5. num_of_blocks and size_of_blocks duplicate constants of the class. In other words, they just waste space and time.

6. I don't see why you are allocating the space for your pool-entries separately from the heap instead of making them part of your object.
   This way making T and N template-arguments seems quite pointless...

   As a tip union{T data[N];}; would declare the space for N elements which won't be constructed or destroyed automatically.

7. You know that pointer-arithmetic is scaled properly for the pointer-type?

8. You don't make sure that size and alignemnt of T fits size_type.

9. You forgot to include a header defining size_t in global scope. Or at all.

10. Your protected typedefs are curious: They don't buy you anything the way you did them, they leak into the signatures of the public interface, but they aren't really part of it.
    Anyway, they aren't uncommon as public members.

11. You should restrict yourself to a single style for member-function-names. snake_case and camelCase are common, UpperCamelCase much less so.

Your extra-questions:

1. Your pool-allocator obviously only gives you leave to access the space for a single element of type T for each call to get().
   Reading / Writing / Indexing beyond that is breaking the contract, and while it might happen to work now might not work if the implementation ever changes.

2. Generally, you should do the corresponding de-allocation for every allocation you do.
   But pools are a special-case: Destroying the pool normally takes all outstanding allocations with it, which might be (part of) the reason for using it at all.