1
2/*
3 * Copyright 2012 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9#include "SkBitmapHeap.h"
10
11#include "SkBitmap.h"
12#include "SkReadBuffer.h"
13#include "SkWriteBuffer.h"
14#include "SkTSearch.h"
15
16SkBitmapHeapEntry::SkBitmapHeapEntry()
17    : fSlot(-1)
18    , fRefCount(0)
19    , fBytesAllocated(0) {
20}
21
22SkBitmapHeapEntry::~SkBitmapHeapEntry() {
23    SkASSERT(0 == fRefCount);
24}
25
26void SkBitmapHeapEntry::addReferences(int count) {
27    if (0 == fRefCount) {
28        // If there are no current owners then the heap manager
29        // will be the only one able to modify it, so it does not
30        // need to be an atomic operation.
31        fRefCount = count;
32    } else {
33        sk_atomic_add(&fRefCount, count);
34    }
35}
36
37///////////////////////////////////////////////////////////////////////////////
38
39static bool operator<(const SkIPoint& a, const SkIPoint& b) {
40    return *(const int64_t*)&a < *(const int64_t*)&b;
41}
42
43static bool operator>(const SkIPoint& a, const SkIPoint& b) {
44    return *(const int64_t*)&a > *(const int64_t*)&b;
45}
46
47bool SkBitmapHeap::LookupEntry::Less(const SkBitmapHeap::LookupEntry& a,
48                                     const SkBitmapHeap::LookupEntry& b) {
49    if (a.fGenerationId < b.fGenerationId) {
50        return true;
51    } else if (a.fGenerationId > b.fGenerationId) {
52        return false;
53    } else if (a.fPixelOrigin < b.fPixelOrigin) {
54        return true;
55    } else if (a.fPixelOrigin > b.fPixelOrigin) {
56        return false;
57    } else if (a.fWidth < b.fWidth) {
58        return true;
59    } else if (a.fWidth > b.fWidth) {
60        return false;
61    } else if (a.fHeight < b.fHeight) {
62        return true;
63    }
64    return false;
65}
66
67///////////////////////////////////////////////////////////////////////////////
68
69SkBitmapHeap::SkBitmapHeap(int32_t preferredSize, int32_t ownerCount)
70    : INHERITED()
71    , fExternalStorage(NULL)
72    , fMostRecentlyUsed(NULL)
73    , fLeastRecentlyUsed(NULL)
74    , fPreferredCount(preferredSize)
75    , fOwnerCount(ownerCount)
76    , fBytesAllocated(0)
77    , fDeferAddingOwners(false) {
78}
79
80SkBitmapHeap::SkBitmapHeap(ExternalStorage* storage, int32_t preferredSize)
81    : INHERITED()
82    , fExternalStorage(storage)
83    , fMostRecentlyUsed(NULL)
84    , fLeastRecentlyUsed(NULL)
85    , fPreferredCount(preferredSize)
86    , fOwnerCount(IGNORE_OWNERS)
87    , fBytesAllocated(0)
88    , fDeferAddingOwners(false) {
89    SkSafeRef(storage);
90}
91
92SkBitmapHeap::~SkBitmapHeap() {
93    SkDEBUGCODE(
94    for (int i = 0; i < fStorage.count(); i++) {
95        bool unused = false;
96        for (int j = 0; j < fUnusedSlots.count(); j++) {
97            if (fUnusedSlots[j] == fStorage[i]->fSlot) {
98                unused = true;
99                break;
100            }
101        }
102        if (!unused) {
103            fBytesAllocated -= fStorage[i]->fBytesAllocated;
104        }
105    }
106    fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry));
107    )
108    SkASSERT(0 == fBytesAllocated);
109    fStorage.deleteAll();
110    SkSafeUnref(fExternalStorage);
111    fLookupTable.deleteAll();
112}
113
114void SkBitmapHeap::removeFromLRU(SkBitmapHeap::LookupEntry* entry) {
115    if (fMostRecentlyUsed == entry) {
116        fMostRecentlyUsed = entry->fLessRecentlyUsed;
117        if (NULL == fMostRecentlyUsed) {
118            SkASSERT(fLeastRecentlyUsed == entry);
119            fLeastRecentlyUsed = NULL;
120        } else {
121            fMostRecentlyUsed->fMoreRecentlyUsed = NULL;
122        }
123    } else {
124        // Remove entry from its prior place, and make sure to cover the hole.
125        if (fLeastRecentlyUsed == entry) {
126            SkASSERT(entry->fMoreRecentlyUsed != NULL);
127            fLeastRecentlyUsed = entry->fMoreRecentlyUsed;
128        }
129        // Since we have already considered the case where entry is the most recently used, it must
130        // have a more recently used at this point.
131        SkASSERT(entry->fMoreRecentlyUsed != NULL);
132        entry->fMoreRecentlyUsed->fLessRecentlyUsed = entry->fLessRecentlyUsed;
133
134        if (entry->fLessRecentlyUsed != NULL) {
135            SkASSERT(fLeastRecentlyUsed != entry);
136            entry->fLessRecentlyUsed->fMoreRecentlyUsed = entry->fMoreRecentlyUsed;
137        }
138    }
139    entry->fMoreRecentlyUsed = NULL;
140}
141
142void SkBitmapHeap::appendToLRU(SkBitmapHeap::LookupEntry* entry) {
143    if (fMostRecentlyUsed != NULL) {
144        SkASSERT(NULL == fMostRecentlyUsed->fMoreRecentlyUsed);
145        fMostRecentlyUsed->fMoreRecentlyUsed = entry;
146        entry->fLessRecentlyUsed = fMostRecentlyUsed;
147    }
148    fMostRecentlyUsed = entry;
149    if (NULL == fLeastRecentlyUsed) {
150        fLeastRecentlyUsed = entry;
151    }
152}
153
154// iterate through our LRU cache and try to find an entry to evict
155SkBitmapHeap::LookupEntry* SkBitmapHeap::findEntryToReplace(const SkBitmap& replacement) {
156    SkASSERT(fPreferredCount != UNLIMITED_SIZE);
157    SkASSERT(fStorage.count() >= fPreferredCount);
158
159    SkBitmapHeap::LookupEntry* iter = fLeastRecentlyUsed;
160    while (iter != NULL) {
161        SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot];
162        if (heapEntry->fRefCount > 0) {
163            // If the least recently used bitmap has not been unreferenced
164            // by its owner, then according to our LRU specifications a more
165            // recently used one can not have used all its references yet either.
166            return NULL;
167        }
168        if (replacement.getGenerationID() == iter->fGenerationId) {
169            // Do not replace a bitmap with a new one using the same
170            // pixel ref. Instead look for a different one that will
171            // potentially free up more space.
172            iter = iter->fMoreRecentlyUsed;
173        } else {
174            return iter;
175        }
176    }
177    return NULL;
178}
179
180size_t SkBitmapHeap::freeMemoryIfPossible(size_t bytesToFree) {
181    if (UNLIMITED_SIZE == fPreferredCount) {
182        return 0;
183    }
184    LookupEntry* iter = fLeastRecentlyUsed;
185    size_t origBytesAllocated = fBytesAllocated;
186    // Purge starting from LRU until a non-evictable bitmap is found or until
187    // everything is evicted.
188    while (iter != NULL) {
189        SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot];
190        if (heapEntry->fRefCount > 0) {
191            break;
192        }
193        LookupEntry* next = iter->fMoreRecentlyUsed;
194        this->removeEntryFromLookupTable(iter);
195        // Free the pixel memory. removeEntryFromLookupTable already reduced
196        // fBytesAllocated properly.
197        heapEntry->fBitmap.reset();
198        // Add to list of unused slots which can be reused in the future.
199        fUnusedSlots.push(heapEntry->fSlot);
200        iter = next;
201        if (origBytesAllocated - fBytesAllocated >= bytesToFree) {
202            break;
203        }
204    }
205
206    if (fLeastRecentlyUsed != iter) {
207        // There was at least one eviction.
208        fLeastRecentlyUsed = iter;
209        if (NULL == fLeastRecentlyUsed) {
210            // Everything was evicted
211            fMostRecentlyUsed = NULL;
212            fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry));
213            fStorage.deleteAll();
214            fUnusedSlots.reset();
215            SkASSERT(0 == fBytesAllocated);
216        } else {
217            fLeastRecentlyUsed->fLessRecentlyUsed = NULL;
218        }
219    }
220
221    return origBytesAllocated - fBytesAllocated;
222}
223
224int SkBitmapHeap::findInLookupTable(const LookupEntry& indexEntry, SkBitmapHeapEntry** entry) {
225    int index = SkTSearch<const LookupEntry, LookupEntry::Less>(
226                                             (const LookupEntry**)fLookupTable.begin(),
227                                             fLookupTable.count(),
228                                             &indexEntry, sizeof(void*));
229
230    if (index < 0) {
231        // insert ourselves into the bitmapIndex
232        index = ~index;
233        *fLookupTable.insert(index) = SkNEW_ARGS(LookupEntry, (indexEntry));
234    } else if (entry != NULL) {
235        // populate the entry if needed
236        *entry = fStorage[fLookupTable[index]->fStorageSlot];
237    }
238
239    return index;
240}
241
242bool SkBitmapHeap::copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap) {
243    SkASSERT(!fExternalStorage);
244
245    // If the bitmap is mutable, we need to do a deep copy, since the
246    // caller may modify it afterwards.
247    if (originalBitmap.isImmutable()) {
248        copiedBitmap = originalBitmap;
249// TODO if we have the pixel ref in the heap we could pass it here to avoid a potential deep copy
250//    else if (sharedPixelRef != NULL) {
251//        copiedBitmap = orig;
252//        copiedBitmap.setPixelRef(sharedPixelRef, originalBitmap.pixelRefOffset());
253    } else if (originalBitmap.empty()) {
254        copiedBitmap.reset();
255    } else if (!originalBitmap.deepCopyTo(&copiedBitmap)) {
256        return false;
257    }
258    copiedBitmap.setImmutable();
259    return true;
260}
261
262int SkBitmapHeap::removeEntryFromLookupTable(LookupEntry* entry) {
263    // remove the bitmap index for the deleted entry
264    SkDEBUGCODE(int count = fLookupTable.count();)
265    int index = this->findInLookupTable(*entry, NULL);
266    // Verify that findInLookupTable found an existing entry rather than adding
267    // a new entry to the lookup table.
268    SkASSERT(count == fLookupTable.count());
269    fBytesAllocated -= fStorage[entry->fStorageSlot]->fBytesAllocated;
270    SkDELETE(fLookupTable[index]);
271    fLookupTable.remove(index);
272    return index;
273}
274
275int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) {
276    SkBitmapHeapEntry* entry = NULL;
277    int searchIndex = this->findInLookupTable(LookupEntry(originalBitmap), &entry);
278
279    if (entry) {
280        // Already had a copy of the bitmap in the heap.
281        if (fOwnerCount != IGNORE_OWNERS) {
282            if (fDeferAddingOwners) {
283                *fDeferredEntries.append() = entry->fSlot;
284            } else {
285                entry->addReferences(fOwnerCount);
286            }
287        }
288        if (fPreferredCount != UNLIMITED_SIZE) {
289            LookupEntry* lookupEntry = fLookupTable[searchIndex];
290            if (lookupEntry != fMostRecentlyUsed) {
291                this->removeFromLRU(lookupEntry);
292                this->appendToLRU(lookupEntry);
293            }
294        }
295        return entry->fSlot;
296    }
297
298    // decide if we need to evict an existing heap entry or create a new one
299    if (fPreferredCount != UNLIMITED_SIZE && fStorage.count() >= fPreferredCount) {
300        // iterate through our LRU cache and try to find an entry to evict
301        LookupEntry* lookupEntry = this->findEntryToReplace(originalBitmap);
302        if (lookupEntry != NULL) {
303            // we found an entry to evict
304            entry = fStorage[lookupEntry->fStorageSlot];
305            // Remove it from the LRU. The new entry will be added to the LRU later.
306            this->removeFromLRU(lookupEntry);
307            int index = this->removeEntryFromLookupTable(lookupEntry);
308
309            // update the current search index now that we have removed one
310            if (index < searchIndex) {
311                searchIndex--;
312            }
313        }
314    }
315
316    // if we didn't have an entry yet we need to create one
317    if (!entry) {
318        if (fPreferredCount != UNLIMITED_SIZE && fUnusedSlots.count() > 0) {
319            int slot;
320            fUnusedSlots.pop(&slot);
321            entry = fStorage[slot];
322        } else {
323            entry = SkNEW(SkBitmapHeapEntry);
324            fStorage.append(1, &entry);
325            entry->fSlot = fStorage.count() - 1;
326            fBytesAllocated += sizeof(SkBitmapHeapEntry);
327        }
328    }
329
330    // create a copy of the bitmap
331    bool copySucceeded;
332    if (fExternalStorage) {
333        copySucceeded = fExternalStorage->insert(originalBitmap, entry->fSlot);
334    } else {
335        copySucceeded = copyBitmap(originalBitmap, entry->fBitmap);
336    }
337
338    // if the copy failed then we must abort
339    if (!copySucceeded) {
340        // delete the index
341        SkDELETE(fLookupTable[searchIndex]);
342        fLookupTable.remove(searchIndex);
343        // If entry is the last slot in storage, it is safe to delete it.
344        if (fStorage.count() - 1 == entry->fSlot) {
345            // free the slot
346            fStorage.remove(entry->fSlot);
347            fBytesAllocated -= sizeof(SkBitmapHeapEntry);
348            SkDELETE(entry);
349        } else {
350            fUnusedSlots.push(entry->fSlot);
351        }
352        return INVALID_SLOT;
353    }
354
355    // update the index with the appropriate slot in the heap
356    fLookupTable[searchIndex]->fStorageSlot = entry->fSlot;
357
358    // compute the space taken by this entry
359    // TODO if there is a shared pixel ref don't count it
360    // If the SkBitmap does not share an SkPixelRef with an SkBitmap already
361    // in the SharedHeap, also include the size of its pixels.
362    entry->fBytesAllocated = originalBitmap.getSize();
363
364    // add the bytes from this entry to the total count
365    fBytesAllocated += entry->fBytesAllocated;
366
367    if (fOwnerCount != IGNORE_OWNERS) {
368        if (fDeferAddingOwners) {
369            *fDeferredEntries.append() = entry->fSlot;
370        } else {
371            entry->addReferences(fOwnerCount);
372        }
373    }
374    if (fPreferredCount != UNLIMITED_SIZE) {
375        this->appendToLRU(fLookupTable[searchIndex]);
376    }
377    return entry->fSlot;
378}
379
380void SkBitmapHeap::deferAddingOwners() {
381    fDeferAddingOwners = true;
382}
383
384void SkBitmapHeap::endAddingOwnersDeferral(bool add) {
385    if (add) {
386        for (int i = 0; i < fDeferredEntries.count(); i++) {
387            SkASSERT(fOwnerCount != IGNORE_OWNERS);
388            SkBitmapHeapEntry* heapEntry = this->getEntry(fDeferredEntries[i]);
389            SkASSERT(heapEntry != NULL);
390            heapEntry->addReferences(fOwnerCount);
391        }
392    }
393    fDeferAddingOwners = false;
394    fDeferredEntries.reset();
395}
396