ShmAllocator.h

Go to the documentation of this file.

#ifndef __MYALLOC_H
#define __MYALLOC_H

#include <iostream>
#include <memory>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include "SemaphoreSet.h"
#include "ExceptionBase.h"

using namespace std;
using namespace SemSet;

namespace ShmAllocator 
{
    class MemException : public ExceptionBase
    {
    public:
        MemException() : ExceptionBase() {}

        MemException(const char* mess) : ExceptionBase(mess) {}

        ~MemException() {}
    };


    #define ALIGN_SEGMENT(n)    (((n-1)|3)+1)

    #define MAX(a,b)            ((a) >= (b) ? (a) : (b))

    #define ATTR_TO_TYPE(T,A,P) ((T*)((char*)(P)-offsetof(T,A)))

    class BlocksList
    {
        struct Node
        {
            Node(const size_t length, Node* next = 0) : length(length), next(next) {}
            size_t length;
            Node* next;
        };
        struct ReturnedBlock
        {
            size_t size;
            char block[0];
        };

    private:
        Node* head;             //the head of the list
        size_t totalSize;       //the total size of the block
        size_t freeSize;        //the free space left
        int numOfBlocks;        //number of nodes in the list
        void* blockStart;       //start address of the block
        void* blockEnd;         //first address not in the block

    public:
        BlocksList(size_t totalSize, void* blockStart) : totalSize(totalSize), blockStart(blockStart)
        {
            //create a one node list
            (char*)blockEnd = (char*)blockStart + totalSize;
            freeSize = totalSize;
            head = (Node*)blockStart;
            new(head) Node(freeSize);
            numOfBlocks = 1;
        }

        ~BlocksList() {}

        void* getBlock(size_t n)
        {
            size_t newSize;
            Node* tmpNode;
            Node* prevNode;
            Node* newNext;
            ReturnedBlock* returnedBlock;

            //get the real size to allocate
            n = MAX(ALIGN_SEGMENT(n + sizeof(ReturnedBlock)), sizeof(Node));
            prevNode = NULL;

            //find available space
            for (tmpNode = head; tmpNode; tmpNode = tmpNode->next)
            {
                if (tmpNode->length >= n)
                {
                    //found block
                    returnedBlock = (ReturnedBlock*)tmpNode;
                    freeSize -= n;
                    if ((tmpNode->length > n) && (tmpNode->length - n >= sizeof(Node)))
                    {
                        newSize = tmpNode->length - n;
                        newNext = tmpNode->next;
                        if (prevNode == NULL)
                        {
                            //first link
                            (char*)head = (char*)head + n;
                            new(head) Node(newSize, newNext);
                        }
                        else
                        {
                            //other link
                            (char*)tmpNode = (char*)tmpNode + n;
                            new(tmpNode) Node(newSize, newNext);
                            prevNode->next = tmpNode;
                        }
                    }
                    else 
                    {
                        //use whole block
                        n = tmpNode->length;
                        numOfBlocks--;
                        if (prevNode == NULL)
                            head = head->next;
                        else
                            prevNode->next = tmpNode->next;
                    }
                    //write down the size given and return
                    returnedBlock->size = n;
                    return returnedBlock->block;
                }

                prevNode = tmpNode;
            }

            //found no free space
            return NULL;
        }

        void returnBlock(void *p) throw(MemException)
        {
            ReturnedBlock* returnedBlock;
            void* curBlockEndAddress;
            Node* tmpNode;
            Node* prevNode;
            Node* returnedNode;

            returnedBlock = ATTR_TO_TYPE(ReturnedBlock, block, p);
            (char*)curBlockEndAddress = (char*)returnedBlock + returnedBlock->size;
            //sanity check
            if (((char*)returnedBlock < (char*)blockStart) || 
                ((char*)curBlockEndAddress > (char*)blockEnd))
                throw MemException("Returning memory not allocated");

            freeSize += returnedBlock->size;
            prevNode = NULL;

            //handle adding first node case
            if (head == NULL)
            {
                head = (Node*)returnedBlock;
                new(head) Node(returnedBlock->size);
                return;
            }

            //find the position to keep list sorted
            for (tmpNode = head; tmpNode; tmpNode = tmpNode->next)
            {
                if ((char*)returnedBlock < (char*)tmpNode)
                {
                    returnedNode = (Node*)returnedBlock;
                    numOfBlocks++;
                    if (prevNode == NULL)
                    {
                        //adding before the head
                        new(returnedNode) Node(returnedBlock->size, head);
                        head = returnedNode;
                    }
                    else
                    {
                        //regular add
                        prevNode->next = returnedNode;
                        new(returnedNode) Node(returnedBlock->size, tmpNode);
                    }
                    //connect to previous node if necessary
                    if ((prevNode) && ((char*)prevNode + prevNode->length == (char*)returnedNode))
                    {
                        prevNode->length += returnedNode->length;
                        prevNode->next = returnedNode->next;
                        returnedNode = prevNode;        //to check if we need to connect to next node
                        numOfBlocks--;
                    }
                    //connect to next node if necessary
                    if ((returnedNode->next) && ((char*)returnedNode + returnedNode->length == (char*)returnedNode->next))
                    {
                        returnedNode->length += returnedNode->next->length;
                        returnedNode->next = returnedNode->next->next;
                        numOfBlocks--;
                    }
                    return;
                }

                prevNode = tmpNode;
            }

            //add new last node case
            returnedNode = (Node*)returnedBlock;
            numOfBlocks++;
            prevNode->next = returnedNode;
            new(returnedNode) Node(returnedBlock->size);
            //connect to previous node if necessary
            if ((char*)prevNode + prevNode->length == (char*)returnedNode)
            {
                prevNode->length += returnedNode->length;
                prevNode->next = returnedNode->next;
                numOfBlocks--;
            }
            return;
        }

        size_t accumFreeMemorySize()
        {
            Node* tmpNode;
            size_t totalFree = 0;

            for (tmpNode = head; tmpNode; tmpNode = tmpNode->next)
                totalFree += tmpNode->length;

            return totalFree;
        }

        size_t getTotalSize()
        {
            return totalSize;
        }

        size_t getFreeSize()
        {
            return freeSize;
        }

        size_t getNumOfBlocks()
        {
            return numOfBlocks;
        }
    };


    class MemAlloc
    {
    private:
        static void *chunk;         //pointer to the shared memory block
        static int shmId;           //shared memory identifier
        static SemaphoreSet* sem;   //block associated semaphore
        static bool freeMemoryFlag; //indicates whether we want to really free the memory (time consuming)
    
    public:
        static BlocksList* bl;      //free blocks list

        static void initialize(unsigned sizeBits, bool freeMemory = false) throw(MemException);

        static void MemAlloc::destroy();

        static void* allocate(size_t size) throw(MemException);
    
        static void deallocate(void* p);
    };


    class ObjectFactory
    {
    private:

    public:
        template <typename T>
        static T* getNewObject()
        {
            T* ret = (T*)MemAlloc::allocate(sizeof(T));
            new(ret) T();

            return ret;
        }

        template <typename T>
        static void returnObject(T* obj)
        {
            obj->~T();
            MemAlloc::deallocate(obj);
        }
    };

    template <typename T>
    class Allocator
    {
    private:
    
    public:
        typedef size_t size_type;               
        typedef ptrdiff_t difference_type;      
        typedef T* pointer;                     
        typedef const T* const_pointer;         
        typedef T& reference;                   
        typedef const T& const_reference;       
        typedef T value_type;                   
        template <typename T1>
            struct rebind
            { 
                typedef Allocator<T1> other; 
            };
    
        Allocator() {}

        Allocator(const Allocator&) {}

        template <typename T1>
            Allocator(const Allocator<T1>&) {}

        ~Allocator() {}
    
        pointer address(reference x) const { return &x; }
    
        const_pointer address(const_reference x) const { return &x; }


        pointer allocate(size_type n, const void* = 0)
        {
            T* ret = NULL;
            if (n) 
                ret = (pointer)MemAlloc::allocate(n * sizeof(value_type));
            return ret;
        }
    
        void deallocate(pointer p, size_type n)
        {
            if (n != 0)
                MemAlloc::deallocate(p);
        }
    
        size_type max_size() const { return size_t(-1) / sizeof(T); }
    
        void construct(pointer p, const T& val) { new(p) T(val); }

        void destroy(pointer p) { p->~T(); }
    };

}

#endif //__MYALLOC_H

---