180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2012 Google Inc. 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "GrMemoryPool.h" 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#if GR_DEBUG 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru #define VALIDATE this->validate() 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#else 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru #define VALIDATE 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruGrMemoryPool::GrMemoryPool(size_t preallocSize, size_t minAllocSize) { 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GR_DEBUGCODE(fAllocationCnt = 0); 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru minAllocSize = GrMax<size_t>(minAllocSize, 1 << 10); 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fMinAllocSize = GrSizeAlignUp(minAllocSize + kPerAllocPad, kAlignment), 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fPreallocSize = GrSizeAlignUp(preallocSize + kPerAllocPad, kAlignment); 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fPreallocSize = GrMax(fPreallocSize, fMinAllocSize); 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHead = CreateBlock(fPreallocSize); 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fTail = fHead; 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHead->fNext = NULL; 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHead->fPrev = NULL; 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru VALIDATE; 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruGrMemoryPool::~GrMemoryPool() { 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru VALIDATE; 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(0 == fAllocationCnt); 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(fHead == fTail); 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(0 == fHead->fLiveCount); 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru DeleteBlock(fHead); 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid* GrMemoryPool::allocate(size_t size) { 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru VALIDATE; 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size = GrSizeAlignUp(size, kAlignment); 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size += kPerAllocPad; 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (fTail->fFreeSize < size) { 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int blockSize = size; 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru blockSize = GrMax<size_t>(blockSize, fMinAllocSize); 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru BlockHeader* block = CreateBlock(blockSize); 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fPrev = fTail; 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fNext = NULL; 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(NULL == fTail->fNext); 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fTail->fNext = block; 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fTail = block; 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(fTail->fFreeSize >= size); 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru intptr_t ptr = fTail->fCurrPtr; 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // We stash a pointer to the block header, just before the allocated space, 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // so that we can decrement the live count on delete in constant time. 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *reinterpret_cast<BlockHeader**>(ptr) = fTail; 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ptr += kPerAllocPad; 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fTail->fPrevPtr = fTail->fCurrPtr; 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fTail->fCurrPtr += size; 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fTail->fFreeSize -= size; 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fTail->fLiveCount += 1; 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GR_DEBUGCODE(++fAllocationCnt); 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru VALIDATE; 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return reinterpret_cast<void*>(ptr); 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid GrMemoryPool::release(void* p) { 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru VALIDATE; 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru intptr_t ptr = reinterpret_cast<intptr_t>(p) - kPerAllocPad; 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru BlockHeader* block = *reinterpret_cast<BlockHeader**>(ptr); 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (1 == block->fLiveCount) { 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // the head block is special, it is reset rather than deleted 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (fHead == block) { 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHead->fCurrPtr = reinterpret_cast<intptr_t>(fHead) + 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru kHeaderSize; 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHead->fLiveCount = 0; 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHead->fFreeSize = fPreallocSize; 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru BlockHeader* prev = block->fPrev; 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru BlockHeader* next = block->fNext; 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(prev); 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru prev->fNext = next; 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (next) { 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru next->fPrev = prev; 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(fTail == block); 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fTail = prev; 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru DeleteBlock(block); 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru --block->fLiveCount; 9580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Trivial reclaim: if we're releasing the most recent allocation, reuse it 9680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (block->fPrevPtr == ptr) { 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fFreeSize += (block->fCurrPtr - block->fPrevPtr); 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fCurrPtr = block->fPrevPtr; 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GR_DEBUGCODE(--fAllocationCnt); 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru VALIDATE; 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruGrMemoryPool::BlockHeader* GrMemoryPool::CreateBlock(size_t size) { 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru BlockHeader* block = 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru reinterpret_cast<BlockHeader*>(GrMalloc(size + kHeaderSize)); 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // we assume malloc gives us aligned memory 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(!(reinterpret_cast<intptr_t>(block) % kAlignment)); 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fLiveCount = 0; 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fFreeSize = size; 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fCurrPtr = reinterpret_cast<intptr_t>(block) + kHeaderSize; 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru block->fPrevPtr = 0; // gcc warns on assigning NULL to an intptr_t. 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return block; 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid GrMemoryPool::DeleteBlock(BlockHeader* block) { 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrFree(block); 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 12080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid GrMemoryPool::validate() { 122d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger#ifdef SK_DEBUG 12380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru BlockHeader* block = fHead; 12480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru BlockHeader* prev = NULL; 12580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(block); 12680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int allocCount = 0; 12780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru do { 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru allocCount += block->fLiveCount; 12980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(prev == block->fPrev); 13080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (NULL != prev) { 13180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(prev->fNext == block); 13280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 13380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru intptr_t b = reinterpret_cast<intptr_t>(block); 13580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t ptrOffset = block->fCurrPtr - b; 13680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t totalSize = ptrOffset + block->fFreeSize; 13780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t userSize = totalSize - kHeaderSize; 13880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru intptr_t userStart = b + kHeaderSize; 13980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 14080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(!(b % kAlignment)); 14180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(!(totalSize % kAlignment)); 14280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(!(userSize % kAlignment)); 14380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(!(block->fCurrPtr % kAlignment)); 14480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (fHead != block) { 14580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(block->fLiveCount); 14680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(userSize >= fMinAllocSize); 14780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 14880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(userSize == fPreallocSize); 14980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 15080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (!block->fLiveCount) { 15180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(ptrOffset == kHeaderSize); 15280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(userStart == block->fCurrPtr); 15380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 15480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(block == *reinterpret_cast<BlockHeader**>(userStart)); 15580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 15680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru prev = block; 15780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } while ((block = block->fNext)); 15880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(allocCount == fAllocationCnt); 15980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru GrAssert(prev == fTail); 160d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger#endif 16180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 162