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