Pool.h

Go to the documentation of this file.

// Honeycomb, Copyright (C) 2015 NewGamePlus Inc.  Distributed under the Boost Software License v1.0.
#pragma once

#include "Honey/Misc/MtMap.h"
#include "Honey/Thread/Lock/Spin.h"

namespace honey
{

namespace lockfree { template<class> class FreeList; }



class MemPool : mt::NoCopy
{
    template<class> friend class lockfree::FreeList;
public:
    MemPool(const vector<tuple<szt,szt>>& buckets, const Id& id = idnull, szt align = alignof(double));
    
    void* alloc(szt size, uint8 align = 1, const char* srcFile = nullptr, int srcLine = 0);
    void free(void* ptr_);

    szt allocBytes() const;
    szt usedBytes() const;
    szt freeBytes() const                                   { return allocBytes() - usedBytes(); }

    #ifdef DEBUG
        void validate() const;
        String printStats() const;
        String printUsed() const;
    #else
        void validate() const                               {}
        String printStats() const                           { return ""; }
        String printUsed() const                            { return ""; }
    #endif

    const Id& id() const                                    { return _id; }

private:
    class Bucket
    {
    public:

        struct Handle
        {
            //divide max swappable into 2 parts, index and tag
            typedef mt::uintBySize<sizeof(atomic::SwapMaxType)/2>::type Int;
            
            Handle()                                        : index(-1) {}
            Handle(nullptr_t)                               : Handle() {}
            Handle(uint8 chunk, Int block)                  : index((block << 8) | chunk) {}
            
            bool operator==(Handle rhs) const               { return index == rhs.index; }
            bool operator!=(Handle rhs) const               { return !operator==(rhs); }
            explicit operator bool() const                  { return index != Int(-1); }
            
            uint8 chunk() const                             { return index & 0xFF; }
            Int block() const                               { return index >> 8; }
            
            Int index;
        };
        
        struct TaggedHandle : Handle
        {
            TaggedHandle()                                  : tag(0) {}
            TaggedHandle(Handle handle, Int tag)            : Handle(handle), tag(tag) {}
            
            TaggedHandle& operator=(Handle rhs)             { Handle::operator=(rhs); return *this; }
            
            bool operator==(TaggedHandle rhs) const         { return Handle::operator==(rhs) && tag == rhs.tag; }
            bool operator!=(TaggedHandle rhs) const         { return !operator==(rhs); }
            
            const Handle& handle() const                    { return *this; }
            Handle& handle()                                { return *this; }
            Int nextTag() const                             { return tag+1; }
            
            Int tag;
        };
        
        struct BlockHeader
        {
            struct Debug
            {
                static const int sigFree = 0xB10CF8EE;  
                static const int sigUsed = 0x05EDB10C;  
            
                szt             size;
                int             srcLine;
                const char*     srcFile;
                Handle          prev;
                int             sig;    
            };

            uint8& bucket()                                 { return *(reinterpret_cast<uint8*>(this) + sizeof(BlockHeader) - 1); }
            
            #ifdef DEBUG
                void validate(int sig)                      { assert(debug.sig == sig, "Error: invalid block signature. Block overwritten by overflow or in unexpected state (eg. freed twice)."); }
            #else
                void validate(int) {}
            #endif

            #ifdef DEBUG
                Debug       debug;
            #endif
            Handle          handle;
            Handle          next;
            uint8           offset;     
            uint8           reserved;   
        };
        
        static BlockHeader* blockHeader(uint8* data)        { return reinterpret_cast<BlockHeader*>(data - sizeof(BlockHeader)); }
        static uint8* blockData(BlockHeader* header)        { return reinterpret_cast<uint8*>(header) + sizeof(BlockHeader); }
        
        Bucket(MemPool& pool, szt blockSize, szt blockCount) :
            _pool(pool),
            _bucketIndex(-1),
            _blockSize(blockSize),
            _blockCountInit(blockCount),
            _blockCount(0),
            _chunkCount(0),
            _chunkSizeTotal(0),
            _freeHead(TaggedHandle()),
            _freeCount(0),
            _usedCount(0),
            _usedSize(0)
        {}

        ~Bucket()
        {
            //Delete all expansion chunks. The first chunk is the initial pool allocation, we don't own it.
            for (auto i : range(1, _chunkCount.load())) delete_(_chunks[i].data());
        }

        void initChunk(uint8* chunk, szt chunkSize, szt blockCount);
        void* alloc(szt size, uint8 align, const char* srcFile, int srcLine);
        void reserve(szt capacity);
        void expand();
        void free(BlockHeader* header);

        szt blockOffsetMax() const                          { return _pool._blockAlign-1; }
        szt blockStride() const                             { return (szt)(intptr_t)alignCeil((void*)(_blockSize + sizeof(BlockHeader)), _pool._blockAlign); }
        
        BlockHeader* deref(Handle handle) const
        {
            assert(handle && handle.chunk() < _chunkCount);
            auto& chunk = _chunks[handle.chunk()];
            assert(blockStride()*handle.block() < chunk.size());
            uint8* blockData = alignCeil(chunk.data() + sizeof(BlockHeader), _pool._blockAlign);
            return blockHeader(blockData + blockStride()*handle.block());
        }
        
        MemPool&                _pool;
        uint8                   _bucketIndex;
        const szt               _blockSize;
        const szt               _blockCountInit;
        szt                     _blockCount;
        array<Buffer<uint8>, numeral<uint64>().sizeBits> _chunks;    
        Atomic<uint8>           _chunkCount;
        Atomic<szt>             _chunkSizeTotal;    
        Atomic<TaggedHandle>    _freeHead;          
        Atomic<szt>             _freeCount;
        TaggedHandle            _usedHead;          
        Atomic<szt>             _usedCount;
        szt                     _usedSize;          
        SpinLock                _lock;
    };

    class Heap
    {
    public:
        struct BlockHeader
        {
            struct Debug
            {
                int             srcLine;
                const char*     srcFile;
                BlockHeader*    prev;
                int             sig;        
            };

            static const uint8 heapTag = -1;
            
            uint8& tag()                                    { return *(reinterpret_cast<uint8*>(this) + sizeof(BlockHeader) - 1); }
            
            #ifdef DEBUG
                void validate(int sig)                      { assert(debug.sig == sig, "Error: invalid block signature. Block overwritten by overflow or in unexpected state (eg. freed twice)."); }
            #else
                void validate(int) {}
            #endif
            
            #ifdef DEBUG
                Debug           debug;
            #endif
            BlockHeader*        next;
            szt                 size;
            uint8               offset;     
            uint8               reserved;   
        };

        static BlockHeader* blockHeader(uint8* data)        { return reinterpret_cast<BlockHeader*>(data - sizeof(BlockHeader)); }
        static uint8* blockData(BlockHeader* header)        { return reinterpret_cast<uint8*>(header) + sizeof(BlockHeader); }

        Heap(MemPool& pool) :
            _pool(pool),
            _allocTotal(0),
            _usedHead(nullptr),
            _usedCount(0)
        {}

        void* alloc(szt size, uint8 align, const char* srcFile, int srcLine);
        void free(BlockHeader* header);

        MemPool&            _pool;
        Atomic<szt>         _allocTotal;        
        BlockHeader*        _usedHead;          
        Atomic<szt>         _usedCount;
        SpinLock            _lock;
    };

    #ifdef DEBUG
        void lock() const;
        void unlock() const;
    #endif
    
    Id                          _id;
    const szt                   _blockAlign;        
    szt                         _blockSizeMax;
    vector<UniquePtr<Bucket>>   _buckets;
    std::map<szt, Bucket*>      _bucketMap;         
    UniquePtr<uint8>            _bucketChunk;       
    UniquePtr<Heap>             _heap;
};


template<template<class> class Subclass, class T>
class MemPoolAllocator : public Allocator<Subclass, T>
{
    typedef Allocator<Subclass, T> Super;
public:
    using typename Super::pointer;
    using typename Super::size_type;
    
    pointer allocate(size_type n, const void* = 0)          { return static_cast<pointer>(this->subc().pool().alloc(sizeof(T)*n)); }
    pointer allocate(size_type n, const char* srcFile, int srcLine, const void* = 0)
                                                            { return static_cast<pointer>(this->subc().pool().alloc(sizeof(T)*n, 1, srcFile, srcLine)); }
    void deallocate(pointer p, size_type)                   { this->subc().pool().free(p); }
};


}