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