Implement own memory pool

Question

I want to allocate a certain amount of memory upfront and use that memory for the rest of the program. The program will basically be allocating memory for a few strings and structs. How do I implement this? What data structures are used to store the pointers and how do I use it to give me a specific amount?

For example, if I malloc 1 MB of space and have it in a pointer p, how do I carve out a 250 KB piece from it ?

This is just meant to be a quick and dirty implementation.

Answer 1

Memory Management using Memory Pool -

Memory Pool is the way to pre-allocate the blocks of memory of the same size. For example, various objects of the same class. Thus, it is more about designing the 'Memory Model' ofyour software.

Example - An animated gif has various frames. Let's say each frame needs maximum 1024 KB only. Also, if we know that we can have maximum two frames only, then we can avoid fragmentation by pre-allocating the memory for each frame.

[note] - Memory Pool is more applicable where we know the behaviour of the system at design time. Thus, memory pool concept is not applicable everywhere. //============================================================================ // Name : MemoryPool.cpp // Author : // Version : // Copyright : SHREYAS JOSHI // Description : //============================================================================

#include <iostream>
#include <malloc.h>

struct memPool
{

private:

    char *m_poolPtr;
    char *m_nextAvailAddr;
    char *m_endAddr;

public:
    /** Methods for the structure **/
    void poolCreate(size_t size);
    void poolDestroy();
    void * poolAlloc(size_t size);

    memPool():m_poolPtr(NULL),m_nextAvailAddr(NULL),m_endAddr(NULL)
    {
        std::cout<<"memPool constructor Invoked"<<std::endl;
    }

    ~memPool()
    {
        std::cout<<"memPool Destructor Invoked"<<std::endl;
        m_poolPtr = NULL;
        m_nextAvailAddr = NULL;
        m_endAddr = NULL;
    }

};

/** Create a Pool of memory - makes a program hassle free of doing malloc multiple times **/
/** Also, Fragmentation can be avoided with the Memory Pool concept **/
/** A pool concept is useful, when you know at design time.how much memory is required for
the similar type of objects in total**/

void memPool::poolCreate(size_t size)
{
    m_poolPtr = (char *) malloc(size);

    if(m_poolPtr == NULL)
    {
        std::cout<<"Pool Create Failed"<<std::endl;
        //printf("Pool Create Failed \r\n");
    }

    m_nextAvailAddr = m_poolPtr;
    /** note the addressing starts from zero - thus you have already counted zero**/
    m_endAddr = m_poolPtr + size - 1;

    //printf("The Pool Head Pointer = %p \r\n",m_poolPtr);
    std::cout<<"Pool Head Pointer = "<<static_cast<void *>(m_poolPtr)<<std::endl;
    //printf("The Pool m_nextAvailAddr = %p \r\n",m_nextAvailAddr);
    std::cout<<"Pool m_nextAvailAddr = "<<static_cast<void *>(m_nextAvailAddr)<<std::endl;
    //printf("The Pool m_endAddr = %p \r\n",m_endAddr);
    std::cout<<"Pool m_endAddr = "<<static_cast<void *>(m_endAddr)<<std::endl;
}


/** Destroy the entire pool in one shot ********/
void memPool::poolDestroy()
{
    free(m_poolPtr);
    /** Remember free first then assign to NULL **/
    m_poolPtr = NULL;

    /** Update Housekeeping--data structure **/
    m_nextAvailAddr = NULL;
    m_endAddr = NULL;
}

/** Allocate some space from the pool ********/
/** Check if the space is available or not **/
/** Do the housekeeping - update the nextAvail Addr in the structure**/
void * memPool::poolAlloc(size_t size)
{
    void *mem = NULL;

    if( (m_endAddr != NULL) && (m_nextAvailAddr != NULL))
    {

        /** This is according to fencing problem - add 1 when you are find a difference of sequence to calculate the space within **/
        size_t availableSize = m_endAddr - m_nextAvailAddr + 1;

        /** check for the availability **/
        if(size > availableSize )
        {
            //std::cout<<"Warning!! the available size = "<<availableSize<< "requested size = "<<size<<std::endl;
            printf("Warning!! the available size = %u and requested size = %u \r\n",availableSize, size);
            mem = NULL;
        }
        else
        {
            /** store the available pointer to the user**/
            mem = m_nextAvailAddr;
            //printf("The user return pointer is = %p \r\n ",mem);
            std::cout<<"The user return pointer is = "<<static_cast <void *>(mem)<<std::endl;
            /*** advance the next available pointer **/
            m_nextAvailAddr += size;
            //printf("The next available pointer is = %p \r\n ",m_nextAvailAddr);
            std::cout<<"The next available pointer is = "<<static_cast<void *>(m_nextAvailAddr)<<std::endl;
        }

    }

    return mem;
}

int main(int argc, char *argv[])
{
    memPool gifAnimatedImageFramesBlk;

    /** Let's say each frame needs 512 kb **/
    char *gifFrame1 = NULL;
    char *gifFrame2 = NULL;

    char *gifFrame3 = NULL;

    /** 1 MB Pool for the GIF IMAGE FRAMES **/
    gifAnimatedImageFramesBlk.poolCreate(1024*1024*1024);
    /*** 512 KB **/
    gifFrame1 = (char *)gifAnimatedImageFramesBlk.poolAlloc(512*1024*1024);
    //printf("Got the gifFrame1..pointer- == %p \r\n ",gifFrame1);
    std::cout<<"Got the gifFrame1..pointer- == "<<static_cast<void *>(gifFrame1)<<std::endl;


    /** again 512 MB **/
    gifFrame2 = (char *)gifAnimatedImageFramesBlk.poolAlloc(512*1024*1024);

    std::cout<<"Got the gifFrame2..pointer- == "<<static_cast<void *>(gifFrame2)<<std::endl;

    //printf("Got the gifFrame2..pointer- == %p \r\n ",gifFrame2);

    /*************Exhausted the pool memory now **************/

    /** This will fail ****************/
    gifFrame3 = (char *)gifAnimatedImageFramesBlk.poolAlloc(1);

    std::cout<<"Got the gifFrame3..pointer- == "<<static_cast<void *>(gifFrame3)<<std::endl;
    //printf("Got the gifFrame3..pointer- == %p \r\n ",gifFrame3);

    /*****Destroy the Pool now *****************/
    gifAnimatedImageFramesBlk.poolDestroy();

    gifFrame3 = (char *)gifAnimatedImageFramesBlk.poolAlloc(1);

    std::cout<<"Got the gifFrame3..pointer- == "<<static_cast<void *>(gifFrame3)<<std::endl;

    //printf("Got the gifFrame3..pointer- == %p \r\n ",gifFrame3);

    gifFrame3 = (char *)gifAnimatedImageFramesBlk.poolAlloc(1);

    std::cout<<"Got the gifFrame3..pointer- == "<<static_cast<void *>(gifFrame3)<<std::endl;
    //printf("Got the gifFrame3..pointer- == %p \r\n ",gifFrame3);


    return 0;
}

[note] - In order to print the value of char * in C++ using ostream::operator<<, the char * should be typecasted to void * using static_cast (pointer_Name). The problem is that if the C++ compiler sees the char *, then it looks for the NULL terminator - '\0'. In this case, there is no NULL terminator '\0'. So, you will see an undefined behaviour.

Advantages of Memory Pool

1. You can avoid fragmentation of memory. Even if the system has required memory space, the malloc() will fail when the desired contigous block size is not available.
2. The space is reserved, and the frequent malloc() and free() is avoided. This will save time.
3. When malloc() is called for many sub-blocks, the administrative/meta data is associated with each allocated sub-blocks. This will consume unnecessary space. Instead, one big block allocation will avoid the multiple administrative/meta data.
4. If the memory space is restricted, then it is easy to investigate for the memory leaks. If memory is exhausted in Pool, then memory pool will return NULL. Thus, you can isolate a memory leak problem easily.

Answer 2

If you want to be able to return memory to the pool, it gets more complicated. However, for the quick and not-quite-so-dirty approach, you may want to implement some code that you can use again...

typedef struct pool
{
  char * next;
  char * end;
} POOL;

POOL * pool_create( size_t size ) {
    POOL * p = (POOL*)malloc( size + sizeof(POOL) );
    p->next = (char*)&p[1];
    p->end = p->next + size;
    return p;
}

void pool_destroy( POOL *p ) {
    free(p);
}

size_t pool_available( POOL *p ) {
    return p->end - p->next;
}

void * pool_alloc( POOL *p, size_t size ) {
    if( pool_available(p) < size ) return NULL;
    void *mem = (void*)p->next;
    p->next += size;
    return mem;
}

In my experience, when using pools like this to allocate many objects, I want to precalculate how much memory will be needed so that I'm not wasteful, but I also don't want to make any mistakes (like not allocating enoudh). So I put all the allocation code inside a loop, and set up my pool allocation functions to accept a flag that performs a 'dummy' allocation on an empty pool. The second time around the loop, I have already calculated the size of the pool so I can create the pool and do the real allocations all with the same function calls and no duplicate code. You'd need to change my suggested pool code, because you can't do this with pointer arithmetic if the memory hasn't been allocated.