1 /*
2  * Copyright 2006 The Android Open Source Project
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 "SkChunkAlloc.h"
9 
10 // Don't malloc any chunks smaller than this
11 #define MIN_CHUNKALLOC_BLOCK_SIZE   1024
12 
13 // Return the new min blocksize given the current value
increase_next_size(size_t size)14 static size_t increase_next_size(size_t size) {
15     return size + (size >> 1);
16 }
17 
18 ///////////////////////////////////////////////////////////////////////////////
19 
20 struct SkChunkAlloc::Block {
21     Block*  fNext;
22     size_t  fFreeSize;
23     char*   fFreePtr;
24     // data[] follows
25 
blockSizeSkChunkAlloc::Block26     size_t blockSize() {
27         char* start = this->startOfData();
28         size_t bytes = fFreePtr - start;
29         return fFreeSize + bytes;
30     }
31 
resetSkChunkAlloc::Block32     void reset() {
33         fNext = NULL;
34         fFreeSize = this->blockSize();
35         fFreePtr = this->startOfData();
36     }
37 
startOfDataSkChunkAlloc::Block38     char* startOfData() {
39         return reinterpret_cast<char*>(this + 1);
40     }
41 
FreeChainSkChunkAlloc::Block42     static void FreeChain(Block* block) {
43         while (block) {
44             Block* next = block->fNext;
45             sk_free(block);
46             block = next;
47         }
48     };
49 
containsSkChunkAlloc::Block50     bool contains(const void* addr) const {
51         const char* ptr = reinterpret_cast<const char*>(addr);
52         return ptr >= (const char*)(this + 1) && ptr < fFreePtr;
53     }
54 };
55 
56 ///////////////////////////////////////////////////////////////////////////////
57 
SkChunkAlloc(size_t minSize)58 SkChunkAlloc::SkChunkAlloc(size_t minSize) {
59     if (minSize < MIN_CHUNKALLOC_BLOCK_SIZE) {
60         minSize = MIN_CHUNKALLOC_BLOCK_SIZE;
61     }
62 
63     fBlock = NULL;
64     fMinSize = minSize;
65     fChunkSize = fMinSize;
66     fTotalCapacity = 0;
67     fTotalUsed = 0;
68     SkDEBUGCODE(fTotalLost = 0;)
69     SkDEBUGCODE(fBlockCount = 0;)
70 }
71 
~SkChunkAlloc()72 SkChunkAlloc::~SkChunkAlloc() {
73     this->reset();
74 }
75 
reset()76 void SkChunkAlloc::reset() {
77     Block::FreeChain(fBlock);
78     fBlock = NULL;
79     fChunkSize = fMinSize;  // reset to our initial minSize
80     fTotalCapacity = 0;
81     fTotalUsed = 0;
82     SkDEBUGCODE(fTotalLost = 0;)
83     SkDEBUGCODE(fBlockCount = 0;)
84 }
85 
rewind()86 void SkChunkAlloc::rewind() {
87     SkDEBUGCODE(this->validate();)
88 
89     Block* largest = fBlock;
90 
91     if (largest) {
92         Block* next;
93         for (Block* cur = largest->fNext; cur; cur = next) {
94             next = cur->fNext;
95             if (cur->blockSize() > largest->blockSize()) {
96                 sk_free(largest);
97                 largest = cur;
98             } else {
99                 sk_free(cur);
100             }
101         }
102 
103         largest->reset();
104         fTotalCapacity = largest->blockSize();
105         SkDEBUGCODE(fBlockCount = 1;)
106     } else {
107         fTotalCapacity = 0;
108         SkDEBUGCODE(fBlockCount = 0;)
109     }
110 
111     fBlock = largest;
112     fChunkSize = fMinSize;  // reset to our initial minSize
113     fTotalUsed = 0;
114     SkDEBUGCODE(fTotalLost = 0;)
115     SkDEBUGCODE(this->validate();)
116 }
117 
newBlock(size_t bytes,AllocFailType ftype)118 SkChunkAlloc::Block* SkChunkAlloc::newBlock(size_t bytes, AllocFailType ftype) {
119     size_t size = bytes;
120     if (size < fChunkSize) {
121         size = fChunkSize;
122     }
123 
124     Block* block = (Block*)sk_malloc_flags(sizeof(Block) + size,
125                         ftype == kThrow_AllocFailType ? SK_MALLOC_THROW : 0);
126 
127     if (block) {
128         block->fFreeSize = size;
129         block->fFreePtr = block->startOfData();
130 
131         fTotalCapacity += size;
132         SkDEBUGCODE(fBlockCount += 1;)
133 
134         fChunkSize = increase_next_size(fChunkSize);
135     }
136     return block;
137 }
138 
addBlockIfNecessary(size_t bytes,AllocFailType ftype)139 SkChunkAlloc::Block* SkChunkAlloc::addBlockIfNecessary(size_t bytes, AllocFailType ftype) {
140     SkASSERT(SkIsAlign4(bytes));
141 
142     if (!fBlock || bytes > fBlock->fFreeSize) {
143         Block* block = this->newBlock(bytes, ftype);
144         if (!block) {
145             return NULL;
146         }
147 #ifdef SK_DEBUG
148         if (fBlock) {
149             fTotalLost += fBlock->fFreeSize;
150         }
151 #endif
152         block->fNext = fBlock;
153         fBlock = block;
154     }
155 
156     SkASSERT(fBlock && bytes <= fBlock->fFreeSize);
157     return fBlock;
158 }
159 
alloc(size_t bytes,AllocFailType ftype)160 void* SkChunkAlloc::alloc(size_t bytes, AllocFailType ftype) {
161     SkDEBUGCODE(this->validate();)
162 
163     bytes = SkAlign4(bytes);
164 
165     Block* block = this->addBlockIfNecessary(bytes, ftype);
166     if (!block) {
167         return NULL;
168     }
169 
170     char* ptr = block->fFreePtr;
171 
172     fTotalUsed += bytes;
173     block->fFreeSize -= bytes;
174     block->fFreePtr = ptr + bytes;
175     SkDEBUGCODE(this->validate();)
176     return ptr;
177 }
178 
unalloc(void * ptr)179 size_t SkChunkAlloc::unalloc(void* ptr) {
180     SkDEBUGCODE(this->validate();)
181 
182     size_t bytes = 0;
183     Block* block = fBlock;
184     if (block) {
185         char* cPtr = reinterpret_cast<char*>(ptr);
186         char* start = block->startOfData();
187         if (start <= cPtr && cPtr < block->fFreePtr) {
188             bytes = block->fFreePtr - cPtr;
189             fTotalUsed -= bytes;
190             block->fFreeSize += bytes;
191             block->fFreePtr = cPtr;
192         }
193     }
194     SkDEBUGCODE(this->validate();)
195     return bytes;
196 }
197 
contains(const void * addr) const198 bool SkChunkAlloc::contains(const void* addr) const {
199     const Block* block = fBlock;
200     while (block) {
201         if (block->contains(addr)) {
202             return true;
203         }
204         block = block->fNext;
205     }
206     return false;
207 }
208 
209 #ifdef SK_DEBUG
validate()210 void SkChunkAlloc::validate() {
211     int numBlocks = 0;
212     size_t totCapacity = 0;
213     size_t totUsed = 0;
214     size_t totLost = 0;
215     size_t totAvailable = 0;
216 
217     for (Block* temp = fBlock; temp; temp = temp->fNext) {
218         ++numBlocks;
219         totCapacity += temp->blockSize();
220         totUsed += temp->fFreePtr - temp->startOfData();
221         if (temp == fBlock) {
222             totAvailable += temp->fFreeSize;
223         } else {
224             totLost += temp->fFreeSize;
225         }
226     }
227 
228     SkASSERT(fBlockCount == numBlocks);
229     SkASSERT(fTotalCapacity == totCapacity);
230     SkASSERT(fTotalUsed == totUsed);
231     SkASSERT(fTotalLost == totLost);
232     SkASSERT(totCapacity == totUsed + totLost + totAvailable);
233 }
234 #endif
235 
236