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