PoolAllocator.h

// WARNING: Changes to this file must be contributed back to Sawyer or else they will
//          be clobbered by the next update from Sawyer.  The Sawyer repository is at
//          https://github.com/matzke1/sawyer.
 
 
 
 
#ifndef Sawyer_PoolAllocator_H
#define Sawyer_PoolAllocator_H
 
#include <boost/version.hpp>
#include <boost/foreach.hpp>
#include <boost/static_assert.hpp>
#include <boost/cstdint.hpp>
#include <list>
#include <Sawyer/Assert.h>
#include <Sawyer/Interval.h>
#include <Sawyer/IntervalMap.h>
#include <Sawyer/Sawyer.h>
#include <Sawyer/Synchronization.h>
#include <vector>
 
namespace Sawyer {
 
template<size_t smallestCell, size_t sizeDelta, size_t nPools, size_t chunkSize, typename Sync>
class PoolAllocatorBase {
public:
    enum { SMALLEST_CELL = smallestCell };
    enum { SIZE_DELTA = sizeDelta };
    enum { N_POOLS = nPools };
    enum { CHUNK_SIZE = chunkSize };
    enum { N_FREE_LISTS = 32 };                          // number of free lists per pool
 
private:
 
    // Singly-linked list of cells (units of object backing store) that are not being used by the caller.
    struct FreeCell { FreeCell *next; };
 
    typedef Sawyer::Container::Interval<boost::uint64_t> ChunkAddressInterval;
 
    //                                  Basic unit of allocation.
private:
    class Chunk {
        unsigned char data_[chunkSize];
    public:
        BOOST_STATIC_ASSERT(chunkSize >= sizeof(FreeCell));
 
        FreeCell* fill(size_t cellSize) {               // create a free list for this chunk
            ASSERT_require(cellSize >= sizeof(FreeCell));
            ASSERT_require(cellSize <= chunkSize);
            FreeCell *retval = NULL;
            size_t n = chunkSize / cellSize;
            for (size_t i=n; i>0; --i) {                // free list in address order is easier to debug at no extra expense
                FreeCell *cell = reinterpret_cast<FreeCell*>(data_+(i-1)*cellSize);
                cell->next = retval;
                retval = cell;
            }
            return retval;
        }
 
        ChunkAddressInterval extent() const {
            return ChunkAddressInterval::hull(reinterpret_cast<boost::uint64_t>(data_),
                                              reinterpret_cast<boost::uint64_t>(data_+chunkSize-1));
        }
    };
 
    //                                  Interesting info about a chunk
private:
    struct ChunkInfo {
        const Chunk *chunk;
        size_t nUsed;
        ChunkInfo(): chunk(NULL), nUsed(0) {}
        ChunkInfo(const Chunk *chunk, size_t nUsed): chunk(chunk), nUsed(nUsed) {}
        bool operator==(const ChunkInfo &other) const {
            return chunk==other.chunk && nUsed==other.nUsed;
        }
    };
 
    typedef Sawyer::Container::IntervalMap<ChunkAddressInterval, ChunkInfo> ChunkInfoMap;
 
    class Pool;
 
    // Aquire all locks for a pool.
    class LockEverything {
        SAWYER_THREAD_TRAITS::Mutex *freeListMutexes_, &chunkMutex_;
        size_t nLocked_;
    public:
        LockEverything(SAWYER_THREAD_TRAITS::Mutex *freeListMutexes, SAWYER_THREAD_TRAITS::Mutex &chunkMutex)
            : freeListMutexes_(freeListMutexes), chunkMutex_(chunkMutex), nLocked_(0) {
            while (nLocked_ < N_FREE_LISTS) {
                freeListMutexes_[nLocked_].lock();
                ++nLocked_;
            }
            chunkMutex_.lock();
        }
 
        ~LockEverything() {
            while (nLocked_ > 0) {
                freeListMutexes_[nLocked_-1].unlock();
                --nLocked_;
            }
            chunkMutex_.unlock();
        }
    };
 
    //                                  Pool of single-sized cells; collection of chunks
    class Pool {
        size_t cellSize_;                               // only modified immediately after construction
 
        // Multiple free-lists for parallelism reduces the contention on the pool. The aquire and release methods select a
        // free-list uniformly at random in order to keep the sizes of the free-lists relatively equal. There is no requirement
        // that an object allocated from one free-list be released back to the same free-list. Each free-list has its own
        // mutex. When locking multiple free-lists, the locks should be aquired in order of their indexes.
        SAWYER_THREAD_TRAITS::Mutex freeListMutexes_[N_FREE_LISTS];
        FreeCell *freeLists_[N_FREE_LISTS];
 
        // The chunk-list stores the memory allocated for objects.  The chunk-list is protected by a mutex. When locking
        // free-list(s) and the chunk-list, the free-list locks should be aquired first.
        mutable SAWYER_THREAD_TRAITS::Mutex chunkMutex_;
        std::list<Chunk*> chunks_;
 
    private:
        Pool(const Pool&);                              // nonsense
 
    public:
        Pool(): cellSize_(0) {
            memset(freeLists_, 0, sizeof freeLists_);
        }
 
        void init(size_t cellSize) {
            assert(cellSize_ == 0);
            assert(cellSize > 0);
            cellSize_ = cellSize;
        }
        
    public:
        ~Pool() {
            for (typename std::list<Chunk*>::iterator ci=chunks_.begin(); ci!=chunks_.end(); ++ci)
                delete *ci;
        }
 
        bool isEmpty() const {
            SAWYER_THREAD_TRAITS::LockGuard lock(chunkMutex_);
            return chunks_.empty();
        }
 
        // Obtains the cell at the front of the free list, allocating more space if necessary.
        void* aquire() {                                // hot
            const size_t freeListIdx = fastRandomIndex(N_FREE_LISTS);
            SAWYER_THREAD_TRAITS::LockGuard lock(freeListMutexes_[freeListIdx]);
            if (!freeLists_[freeListIdx]) {
                Chunk *chunk = new Chunk;
                freeLists_[freeListIdx] = chunk->fill(cellSize_);
                SAWYER_THREAD_TRAITS::LockGuard lock(chunkMutex_);
                chunks_.push_back(chunk);
            }
            ASSERT_not_null(freeLists_[freeListIdx]);
            FreeCell *cell = freeLists_[freeListIdx];
            freeLists_[freeListIdx] = freeLists_[freeListIdx]->next;
            cell->next = NULL;                          // optional
            return cell;
        }
 
        // Returns an cell to the front of the free list.
        void release(void *cell) {                      // hot
            const size_t freeListIdx = fastRandomIndex(N_FREE_LISTS);
            SAWYER_THREAD_TRAITS::LockGuard lock(freeListMutexes_[freeListIdx]);
            ASSERT_not_null(cell);
            FreeCell *freedCell = reinterpret_cast<FreeCell*>(cell);
            freedCell->next = freeLists_[freeListIdx];
            freeLists_[freeListIdx] = freedCell;
        }
 
        // Information about each chunk.
        ChunkInfoMap chunkInfoNS() const {
            ChunkInfoMap map;
            BOOST_FOREACH (const Chunk* chunk, chunks_)
                map.insert(chunk->extent(), ChunkInfo(chunk, chunkSize / cellSize_));
            for (size_t freeListIdx = 0; freeListIdx < N_FREE_LISTS; ++freeListIdx) {
                for (FreeCell *cell=freeLists_[freeListIdx]; cell!=NULL; cell=cell->next) {
                    typename ChunkInfoMap::ValueIterator found = map.find(reinterpret_cast<boost::uint64_t>(cell));
                    ASSERT_require2(found!=map.values().end(), "each freelist item must be some chunk cell");
                    ASSERT_require2(found->nUsed > 0, "freelist must be consistent with chunk capacities");
                    --found->nUsed;
                }
            }
            return map;
        }
 
        // Reserve objects to satisfy future allocation requests.
        void reserve(size_t nObjects) {
            LockEverything guard(freeListMutexes_, chunkMutex_);
            size_t nFree = 0;
            for (size_t freeListIdx = 0; freeListIdx < N_FREE_LISTS; ++freeListIdx) {
                for (FreeCell *cell = freeLists_[freeListIdx]; cell != NULL; cell = cell->next) {
                    ++nFree;
                    if (nFree >= nObjects)
                        return;
                }
            }
 
            size_t freeListIdx = fastRandomIndex(N_FREE_LISTS);
            size_t nNeeded = nObjects - nFree;
            const size_t cellsPerChunk = chunkSize / cellSize_;
            while (1) {
                // Allocate a new chunk of object cells
                Chunk *chunk = new Chunk;
                FreeCell *newCells = chunk->fill(cellSize_);
                chunks_.push_back(chunk);
 
                // Insert the new object cells into the free lists in round-robin order
                while (newCells) {
                    FreeCell *cell = newCells;
                    newCells = cell->next;
                    cell->next = freeLists_[freeListIdx];
                    freeLists_[freeListIdx] = cell;
                    if (++freeListIdx >= N_FREE_LISTS)
                        freeListIdx = 0;
                }
 
                if (nNeeded < cellsPerChunk)
                    return;
            }
        }
        
        // Free unused chunks
        void vacuum() {
            // We must aquire all the free list-locks plus the chunks-lock before we call chunkInfoNS. Free-list locks must be
            // aquired before the chunk-list lock.
            LockEverything guard(freeListMutexes_, chunkMutex_);
            ChunkInfoMap map = chunkInfoNS();
 
            // Scan the free lists, creating new free lists in the process.  For any cell on an old free list, if the cell
            // belongs to a chunk that we're keeping, then copy the cell to a new free list.  The cells are copied round-robin
            // to the new free lists so that the lists stay balanced.
            FreeCell *newFreeLists[N_FREE_LISTS];
            memset(newFreeLists, 0, sizeof newFreeLists);
            size_t newFreeListIdx = 0;
            for (size_t oldFreeListIdx=0; oldFreeListIdx<N_FREE_LISTS; ++oldFreeListIdx) {
                FreeCell *next = NULL;
                for (FreeCell *cell = freeLists_[oldFreeListIdx]; cell != NULL; cell = next) {
                    next = cell->next;
                    boost::uint64_t cellAddr = reinterpret_cast<boost::uint64_t>(cell);
                    if (map[cellAddr].nUsed != 0) {
                        // Keep this cell by round-robin inserting it into a new free list.
                        cell->next = newFreeLists[newFreeListIdx];
                        newFreeLists[newFreeListIdx] = cell;
                        if (++newFreeListIdx >= N_FREE_LISTS)
                            newFreeListIdx = 0;
                    }
                }
            }
            memcpy(freeLists_, newFreeLists, sizeof newFreeLists);
 
            // Delete chunks that have no used cells.
            typename std::list<Chunk*>::iterator iter = chunks_.begin();
            while (iter!=chunks_.end()) {
                Chunk *chunk = *iter;
                boost::uint64_t cellAddr = chunk->extent().least(); // any cell will do
                if (map[cellAddr].nUsed == 0) {
                    delete chunk;
                    iter = chunks_.erase(iter);
                } else {
                    ++iter;
                }
            }
        }
 
        size_t showInfo(std::ostream &out) const {
            ChunkInfoMap cim;
            {
                LockEverything guard(const_cast<SAWYER_THREAD_TRAITS::Mutex*>(freeListMutexes_), chunkMutex_);
                cim = chunkInfoNS();
            }
 
            const size_t nCells = chunkSize / cellSize_;
            size_t totalUsed=0;
            BOOST_FOREACH (const ChunkInfo &info, cim.values()) {
                out <<"  chunk " <<info.chunk <<"\t" <<info.nUsed <<"/" <<nCells <<"\t= " <<100.0*info.nUsed/nCells <<"%\n";
                totalUsed += info.nUsed;
            }
            return totalUsed;
        }
 
        std::pair<size_t, size_t> nAllocated() const {
            ChunkInfoMap cim;
            {
                LockEverything guard(const_cast<SAWYER_THREAD_TRAITS::Mutex*>(freeListMutexes_), chunkMutex_);
                cim = chunkInfoNS();
            }
 
            const size_t nCells = chunkSize / cellSize_;
            size_t nReserved = nCells * cim.nIntervals();
            size_t nAllocated = 0;
            BOOST_FOREACH (const ChunkInfo &info, cim.values())
                nAllocated += info.nUsed;
            return std::make_pair(nAllocated, nReserved);
        }
    };
 
    //                                  Private data members and methods
private:
    Pool *pools_;                                       // modified only in constructors and destructor
 
    // Called only by constructors
    void init() {
        pools_ = new Pool[nPools];
        for (size_t i=0; i<nPools; ++i)
            pools_[i].init(cellSize(i));
    }
 
    //                                  Construction
public:
    PoolAllocatorBase() {
        init();
    }
 
    PoolAllocatorBase(const PoolAllocatorBase&) {
        init();
    }
 
private:
    // Assignment is nonsensical
    PoolAllocatorBase& operator=(const PoolAllocatorBase&);
 
public:
    virtual ~PoolAllocatorBase() {
        delete[] pools_;
    }
 
    //                                  Public methods
public:
    static size_t poolNumber(size_t size) {
        return size <= smallestCell ? 0 : (size - smallestCell + sizeDelta - 1) / sizeDelta;
    }
 
    static size_t cellSize(size_t poolNumber) {
        return smallestCell + poolNumber * sizeDelta;
    }
 
    static size_t nCells(size_t poolNumber) {
        return chunkSize / cellSize(poolNumber);
    }
 
    void *allocate(size_t size) {                       // hot
        ASSERT_require(size>0);
        size_t pn = poolNumber(size);
        return pn < nPools ? pools_[pn].aquire() : ::operator new(size);
    }
 
    void reserve(size_t objectSize, size_t nObjects) {
        ASSERT_always_require(objectSize > 0); // so objectSize is always used
        size_t pn = poolNumber(nObjects);
        if (pn >= nPools)
            return;
        pools_[pn].reserve(nObjects);
    }
    
    std::pair<size_t, size_t> nAllocated() const {
        size_t nAllocated = 0, nReserved = 0;
        for (size_t pn=0; pn<nPools; ++pn) {
            std::pair<size_t, size_t> pp = pools_[pn].nAllocated();
            nAllocated += pp.first;
            nReserved += pp.second;
        }
        return std::make_pair(nAllocated, nReserved);
    }
    
    void deallocate(void *addr, size_t size) {          // hot
        if (addr) {
            ASSERT_require(size>0);
            size_t pn = poolNumber(size);
            if (pn < nPools) {
                pools_[pn].release(addr);
            } else {
                ::operator delete(addr);
            }
        }
    }
 
    void vacuum() {
        for (size_t pn=0; pn<nPools; ++pn)
            pools_[pn].vacuum();
    }
 
    void showInfo(std::ostream &out) const {
        for (size_t pn=0; pn<nPools; ++pn) {
            if (!pools_[pn].isEmpty()) {
                out <<"  pool #" <<pn <<"; cellSize = " <<cellSize(pn) <<" bytes:\n";
                size_t nUsed = pools_[pn].showInfo(out);
                out <<"    total objects in use: " <<nUsed <<"\n";
            }
        }
    }
};
 
typedef PoolAllocatorBase<sizeof(void*), 4, 32, 40960, SingleThreadedTag> UnsynchronizedPoolAllocator;
 
typedef PoolAllocatorBase<sizeof(void*), 4, 32, 40960, MultiThreadedTag> SynchronizedPoolAllocator;
 
} // namespace
#endif