1 /* 2 * Copyright 2012 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #ifndef GrMemoryPool_DEFINED 9 #define GrMemoryPool_DEFINED 10 11 #include "GrTypes.h" 12 #ifdef SK_DEBUG 13 #include "SkTHash.h" 14 #endif 15 16 /** 17 * Allocates memory in blocks and parcels out space in the blocks for allocation 18 * requests. It is optimized for allocate / release speed over memory 19 * efficiency. The interface is designed to be used to implement operator new 20 * and delete overrides. All allocations are expected to be released before the 21 * pool's destructor is called. Allocations will be 8-byte aligned. 22 */ 23 class GrMemoryPool { 24 public: 25 /** 26 * Prealloc size is the amount of space to allocate at pool creation 27 * time and keep around until pool destruction. The min alloc size is 28 * the smallest allowed size of additional allocations. Both sizes are 29 * adjusted to ensure that: 30 * 1. they are are 8-byte aligned 31 * 2. minAllocSize >= kSmallestMinAllocSize 32 * 3. preallocSize >= minAllocSize 33 * 34 * Both sizes is what the pool will end up allocating from the system, and 35 * portions of the allocated memory is used for internal bookkeeping. 36 */ 37 GrMemoryPool(size_t preallocSize, size_t minAllocSize); 38 39 ~GrMemoryPool(); 40 41 /** 42 * Allocates memory. The memory must be freed with release(). 43 */ 44 void* allocate(size_t size); 45 46 /** 47 * p must have been returned by allocate() 48 */ 49 void release(void* p); 50 51 /** 52 * Returns true if there are no unreleased allocations. 53 */ isEmpty()54 bool isEmpty() const { return fTail == fHead && !fHead->fLiveCount; } 55 56 /** 57 * Returns the total allocated size of the GrMemoryPool minus any preallocated amount 58 */ size()59 size_t size() const { return fSize; } 60 61 /** 62 * Returns the preallocated size of the GrMemoryPool 63 */ preallocSize()64 size_t preallocSize() const { return fHead->fSize; } 65 66 /** 67 * Minimum value of minAllocSize constructor argument. 68 */ 69 constexpr static size_t kSmallestMinAllocSize = 1 << 10; 70 71 private: 72 struct BlockHeader; 73 74 static BlockHeader* CreateBlock(size_t size); 75 76 static void DeleteBlock(BlockHeader* block); 77 78 void validate(); 79 80 struct BlockHeader { 81 #ifdef SK_DEBUG 82 uint32_t fBlockSentinal; ///< known value to check for bad back pointers to blocks 83 #endif 84 BlockHeader* fNext; ///< doubly-linked list of blocks. 85 BlockHeader* fPrev; 86 int fLiveCount; ///< number of outstanding allocations in the 87 ///< block. 88 intptr_t fCurrPtr; ///< ptr to the start of blocks free space. 89 intptr_t fPrevPtr; ///< ptr to the last allocation made 90 size_t fFreeSize; ///< amount of free space left in the block. 91 size_t fSize; ///< total allocated size of the block 92 }; 93 94 static const uint32_t kAssignedMarker = 0xCDCDCDCD; 95 static const uint32_t kFreedMarker = 0xEFEFEFEF; 96 97 struct AllocHeader { 98 #ifdef SK_DEBUG 99 uint32_t fSentinal; ///< known value to check for memory stomping (e.g., (CD)*) 100 int32_t fID; ///< ID that can be used to track down leaks by clients. 101 #endif 102 BlockHeader* fHeader; ///< pointer back to the block header in which an alloc resides 103 }; 104 105 size_t fSize; 106 size_t fMinAllocSize; 107 BlockHeader* fHead; 108 BlockHeader* fTail; 109 #ifdef SK_DEBUG 110 int fAllocationCnt; 111 int fAllocBlockCnt; 112 SkTHashSet<int32_t> fAllocatedIDs; 113 #endif 114 115 protected: 116 enum { 117 // We assume this alignment is good enough for everybody. 118 kAlignment = 8, 119 kHeaderSize = GR_CT_ALIGN_UP(sizeof(BlockHeader), kAlignment), 120 kPerAllocPad = GR_CT_ALIGN_UP(sizeof(AllocHeader), kAlignment), 121 }; 122 }; 123 124 /** 125 * Variant of GrMemoryPool that can only allocate objects of a single type. It is 126 * not as flexible as GrMemoryPool, but it has more convenient allocate() method, 127 * and more importantly, it guarantees number of objects that are preallocated at 128 * construction or when adding a new memory block. I.e. 129 * 130 * GrMemoryPool pool(3 * sizeof(T), 1000 * sizeof(T)); 131 * pool.allocate(sizeof(T)); 132 * pool.allocate(sizeof(T)); 133 * pool.allocate(sizeof(T)); 134 * 135 * will preallocate 3 * sizeof(T) bytes and use some of those bytes for internal 136 * structures. Because of that, last allocate() call will end up allocating a new 137 * block of 1000 * sizeof(T) bytes. In contrast, 138 * 139 * GrObjectMemoryPool<T> pool(3, 1000); 140 * pool.allocate(); 141 * pool.allocate(); 142 * pool.allocate(); 143 * 144 * guarantees to preallocate enough memory for 3 objects of sizeof(T), so last 145 * allocate() will use preallocated memory and won't cause allocation of a new block. 146 * 147 * Same thing is true for the second (minAlloc) ctor argument: this class guarantees 148 * that a newly added block will have enough space for 1000 objects of sizeof(T), while 149 * GrMemoryPool does not. 150 */ 151 template <class T> 152 class GrObjectMemoryPool: public GrMemoryPool { 153 public: 154 /** 155 * Preallocates memory for preallocCount objects, and sets new block size to be 156 * enough to hold minAllocCount objects. 157 */ GrObjectMemoryPool(size_t preallocCount,size_t minAllocCount)158 GrObjectMemoryPool(size_t preallocCount, size_t minAllocCount) 159 : GrMemoryPool(CountToSize(preallocCount), 160 CountToSize(SkTMax(minAllocCount, kSmallestMinAllocCount))) { 161 } 162 163 /** 164 * Allocates memory for an object, but doesn't construct or otherwise initialize it. 165 * The memory must be freed with release(). 166 */ allocate()167 T* allocate() { return static_cast<T*>(GrMemoryPool::allocate(sizeof(T))); } 168 169 private: 170 constexpr static size_t kTotalObjectSize = 171 kPerAllocPad + GR_CT_ALIGN_UP(sizeof(T), kAlignment); 172 CountToSize(size_t count)173 constexpr static size_t CountToSize(size_t count) { 174 return kHeaderSize + count * kTotalObjectSize; 175 } 176 177 public: 178 /** 179 * Minimum value of minAllocCount constructor argument. 180 */ 181 constexpr static size_t kSmallestMinAllocCount = 182 (GrMemoryPool::kSmallestMinAllocSize - kHeaderSize + kTotalObjectSize - 1) / 183 kTotalObjectSize; 184 }; 185 186 template <class T> 187 constexpr size_t GrObjectMemoryPool<T>::kSmallestMinAllocCount; 188 189 #endif 190