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