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 #include "GrMemoryPool.h"
9 #include "SkMalloc.h"
10 #ifdef SK_DEBUG
11 #include "SkAtomics.h"
12 #endif
13
14 #ifdef SK_DEBUG
15 #define VALIDATE this->validate()
16 #else
17 #define VALIDATE
18 #endif
19
20 constexpr size_t GrMemoryPool::kSmallestMinAllocSize;
21
GrMemoryPool(size_t preallocSize,size_t minAllocSize)22 GrMemoryPool::GrMemoryPool(size_t preallocSize, size_t minAllocSize) {
23 SkDEBUGCODE(fAllocationCnt = 0);
24 SkDEBUGCODE(fAllocBlockCnt = 0);
25
26 minAllocSize = SkTMax<size_t>(GrSizeAlignUp(minAllocSize, kAlignment), kSmallestMinAllocSize);
27 preallocSize = SkTMax<size_t>(GrSizeAlignUp(preallocSize, kAlignment), minAllocSize);
28
29 fMinAllocSize = minAllocSize;
30 fSize = 0;
31
32 fHead = CreateBlock(preallocSize);
33 fTail = fHead;
34 fHead->fNext = nullptr;
35 fHead->fPrev = nullptr;
36 VALIDATE;
37 };
38
~GrMemoryPool()39 GrMemoryPool::~GrMemoryPool() {
40 VALIDATE;
41 #ifdef SK_DEBUG
42 int i = 0;
43 int n = fAllocatedIDs.count();
44 fAllocatedIDs.foreach([&i, n] (int32_t id) {
45 if (++i == 1) {
46 SkDebugf("Leaked IDs (in no particular order): %d", id);
47 } else if (i < 11) {
48 SkDebugf(", %d%s", id, (n == i ? "\n" : ""));
49 } else if (i == 11) {
50 SkDebugf(", ...\n");
51 }
52 });
53 #endif
54 SkASSERT(0 == fAllocationCnt);
55 SkASSERT(fHead == fTail);
56 SkASSERT(0 == fHead->fLiveCount);
57 DeleteBlock(fHead);
58 };
59
allocate(size_t size)60 void* GrMemoryPool::allocate(size_t size) {
61 VALIDATE;
62 size += kPerAllocPad;
63 size = GrSizeAlignUp(size, kAlignment);
64 if (fTail->fFreeSize < size) {
65 size_t blockSize = size + kHeaderSize;
66 blockSize = SkTMax<size_t>(blockSize, fMinAllocSize);
67 BlockHeader* block = CreateBlock(blockSize);
68
69 block->fPrev = fTail;
70 block->fNext = nullptr;
71 SkASSERT(nullptr == fTail->fNext);
72 fTail->fNext = block;
73 fTail = block;
74 fSize += block->fSize;
75 SkDEBUGCODE(++fAllocBlockCnt);
76 }
77 SkASSERT(kAssignedMarker == fTail->fBlockSentinal);
78 SkASSERT(fTail->fFreeSize >= size);
79 intptr_t ptr = fTail->fCurrPtr;
80 // We stash a pointer to the block header, just before the allocated space,
81 // so that we can decrement the live count on delete in constant time.
82 AllocHeader* allocData = reinterpret_cast<AllocHeader*>(ptr);
83 SkDEBUGCODE(allocData->fSentinal = kAssignedMarker);
84 SkDEBUGCODE(allocData->fID = []{static int32_t gID; return sk_atomic_inc(&gID) + 1;}());
85 // You can set a breakpoint here when a leaked ID is allocated to see the stack frame.
86 SkDEBUGCODE(fAllocatedIDs.add(allocData->fID));
87 allocData->fHeader = fTail;
88 ptr += kPerAllocPad;
89 fTail->fPrevPtr = fTail->fCurrPtr;
90 fTail->fCurrPtr += size;
91 fTail->fFreeSize -= size;
92 fTail->fLiveCount += 1;
93 SkDEBUGCODE(++fAllocationCnt);
94 VALIDATE;
95 return reinterpret_cast<void*>(ptr);
96 }
97
release(void * p)98 void GrMemoryPool::release(void* p) {
99 VALIDATE;
100 intptr_t ptr = reinterpret_cast<intptr_t>(p) - kPerAllocPad;
101 AllocHeader* allocData = reinterpret_cast<AllocHeader*>(ptr);
102 SkASSERT(kAssignedMarker == allocData->fSentinal);
103 SkDEBUGCODE(allocData->fSentinal = kFreedMarker);
104 SkDEBUGCODE(fAllocatedIDs.remove(allocData->fID));
105 BlockHeader* block = allocData->fHeader;
106 SkASSERT(kAssignedMarker == block->fBlockSentinal);
107 if (1 == block->fLiveCount) {
108 // the head block is special, it is reset rather than deleted
109 if (fHead == block) {
110 fHead->fCurrPtr = reinterpret_cast<intptr_t>(fHead) + kHeaderSize;
111 fHead->fLiveCount = 0;
112 fHead->fFreeSize = fHead->fSize - kHeaderSize;
113 } else {
114 BlockHeader* prev = block->fPrev;
115 BlockHeader* next = block->fNext;
116 SkASSERT(prev);
117 prev->fNext = next;
118 if (next) {
119 next->fPrev = prev;
120 } else {
121 SkASSERT(fTail == block);
122 fTail = prev;
123 }
124 fSize -= block->fSize;
125 DeleteBlock(block);
126 SkDEBUGCODE(fAllocBlockCnt--);
127 }
128 } else {
129 --block->fLiveCount;
130 // Trivial reclaim: if we're releasing the most recent allocation, reuse it
131 if (block->fPrevPtr == ptr) {
132 block->fFreeSize += (block->fCurrPtr - block->fPrevPtr);
133 block->fCurrPtr = block->fPrevPtr;
134 }
135 }
136 SkDEBUGCODE(--fAllocationCnt);
137 VALIDATE;
138 }
139
CreateBlock(size_t blockSize)140 GrMemoryPool::BlockHeader* GrMemoryPool::CreateBlock(size_t blockSize) {
141 blockSize = SkTMax<size_t>(blockSize, kHeaderSize);
142 BlockHeader* block =
143 reinterpret_cast<BlockHeader*>(sk_malloc_throw(blockSize));
144 // we assume malloc gives us aligned memory
145 SkASSERT(!(reinterpret_cast<intptr_t>(block) % kAlignment));
146 SkDEBUGCODE(block->fBlockSentinal = kAssignedMarker);
147 block->fLiveCount = 0;
148 block->fFreeSize = blockSize - kHeaderSize;
149 block->fCurrPtr = reinterpret_cast<intptr_t>(block) + kHeaderSize;
150 block->fPrevPtr = 0; // gcc warns on assigning nullptr to an intptr_t.
151 block->fSize = blockSize;
152 return block;
153 }
154
DeleteBlock(BlockHeader * block)155 void GrMemoryPool::DeleteBlock(BlockHeader* block) {
156 SkASSERT(kAssignedMarker == block->fBlockSentinal);
157 SkDEBUGCODE(block->fBlockSentinal = kFreedMarker); // FWIW
158 sk_free(block);
159 }
160
validate()161 void GrMemoryPool::validate() {
162 #ifdef SK_DEBUG
163 BlockHeader* block = fHead;
164 BlockHeader* prev = nullptr;
165 SkASSERT(block);
166 int allocCount = 0;
167 do {
168 SkASSERT(kAssignedMarker == block->fBlockSentinal);
169 allocCount += block->fLiveCount;
170 SkASSERT(prev == block->fPrev);
171 if (prev) {
172 SkASSERT(prev->fNext == block);
173 }
174
175 intptr_t b = reinterpret_cast<intptr_t>(block);
176 size_t ptrOffset = block->fCurrPtr - b;
177 size_t totalSize = ptrOffset + block->fFreeSize;
178 intptr_t userStart = b + kHeaderSize;
179
180 SkASSERT(!(b % kAlignment));
181 SkASSERT(!(totalSize % kAlignment));
182 SkASSERT(!(block->fCurrPtr % kAlignment));
183 if (fHead != block) {
184 SkASSERT(block->fLiveCount);
185 SkASSERT(totalSize >= fMinAllocSize);
186 } else {
187 SkASSERT(totalSize == block->fSize);
188 }
189 if (!block->fLiveCount) {
190 SkASSERT(ptrOffset == kHeaderSize);
191 SkASSERT(userStart == block->fCurrPtr);
192 } else {
193 AllocHeader* allocData = reinterpret_cast<AllocHeader*>(userStart);
194 SkASSERT(allocData->fSentinal == kAssignedMarker ||
195 allocData->fSentinal == kFreedMarker);
196 SkASSERT(block == allocData->fHeader);
197 }
198
199 prev = block;
200 } while ((block = block->fNext));
201 SkASSERT(allocCount == fAllocationCnt);
202 SkASSERT(fAllocationCnt == fAllocatedIDs.count());
203 SkASSERT(prev == fTail);
204 SkASSERT(fAllocBlockCnt != 0 || fSize == 0);
205 #endif
206 }
207