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