6
\$\begingroup\$

Here is an attempt at implementing a fixed size Memory Pool1:

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 structure2 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?

  1. 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Why would you have your typedefs protected? \$\endgroup\$ – Ben Steffan May 25 '17 at 13:20
  • \$\begingroup\$ @BenSteffan that is good point, some of them are used as returning types in the member functions, so probably they need to be public. \$\endgroup\$ – Ziezi May 25 '17 at 13:44
  • 1
    \$\begingroup\$ There are some implementations already, such as this (not really, but pretty close). \$\endgroup\$ – Incomputable May 25 '17 at 13:55
  • \$\begingroup\$ @Incomputable you are right. As far as I understood, it implements an Allocator based on Pool. I've read it (upvote it) in the past few days. The use of std::vector as a member (which implicitly uses the operators Pool is created as an alternative to) confused me. \$\endgroup\$ – Ziezi May 25 '17 at 14:19
  • 1
    \$\begingroup\$ @Ziezi, well it stores chunks of memories in a vector. Every time one chunk is exhausted, new one is allocated and placed on the back of the vector. The real problem with it is that the allocator itself owns the objects, which is not really good, since it is not a factory. \$\endgroup\$ – Incomputable May 25 '17 at 16:03
3
\$\begingroup\$

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.:

\$\endgroup\$
  • \$\begingroup\$ I think that focusing on the code would make it less offensive (I wouldn't say it is very offensive now, but on a bad mood it might get so). May be using some passive voice will help. \$\endgroup\$ – Incomputable May 25 '17 at 17:25
  • \$\begingroup\$ Before writing a complete comment to your answer: The tone is OK, if someone has any concerns - please, don't. I'm using the paper mentioned at the end and fully share most of your observations and remarks, related to redundant code, C - style casting, etc. \$\endgroup\$ – Ziezi May 25 '17 at 17:36
  • 1
    \$\begingroup\$ @LokiAstari, I'm on Ben's side. Personally I like it more since I write a lot of standard library compatible code. I would like to save CamelCase for template parameters, which hopefully will become concepts. May be CamelCase can be used to signal that it is not meant to be compatible with standard library. \$\endgroup\$ – Incomputable May 25 '17 at 18:13
  • 1
    \$\begingroup\$ @Ziezi This line casts ptr first to a pointer of type size_type (which it isn't, it's of type T) and then writes the index obtained through IndexFromAddr to the location it points to, which actually violates the strict aliasing rule and is thus undefined behaviour. I have just begun looking thorugh the paper and its implementation, and the reason that a such a cast is used there is because they didn't use a template, but pass around a void* instead which they assume to point to uint32_t. Still, what they have written is more like c than c++, so I wouldn't use it as orientation. \$\endgroup\$ – Ben Steffan May 25 '17 at 20:28
  • 1
    \$\begingroup\$ @Ziezi After reading up on the paper, I realized that I misunderstood the way you were trying to implement the memory pool, so I decided to edit my answer and basically rewrite the complete last section. I am terribly sorry for this mistake, but for the next time you ask, please be so kind and explain the algorithm you are trying to implement shortly in the question. It will make the reviewer's job a whole lot easier. \$\endgroup\$ – Ben Steffan May 25 '17 at 21:42
2
\$\begingroup\$
  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.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your time and for the complete answer! Focusing on the extra questions: so, in the example I give in the first question: if I were to implement a data structure (e.g. a vector), should Pool be used to allocate memory for the whole data structure as a single element, i.e. one Pool block == memory for one vector, or element-wise, i.e. one Pool block == one vector element? \$\endgroup\$ – Ziezi May 26 '17 at 7:00
  • 1
    \$\begingroup\$ As I said, the pool is designed for allocating space for single elements, it has nothing to do with vectors or arrays. \$\endgroup\$ – Deduplicator May 26 '17 at 12:15
  • \$\begingroup\$ I understand, just the fact that I'm supposed to use it instead of malloc(), but for single elements confuses me... \$\endgroup\$ – Ziezi May 26 '17 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.