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