1 /*
2 * Copyright 2013 Google Inc.
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 "src/core/SkResourceCache.h"
9
10 #include "include/core/SkGraphics.h"
11 #include "include/core/SkString.h"
12 #include "include/core/SkTraceMemoryDump.h"
13 #include "include/core/SkTypes.h"
14 #include "include/private/base/SkAlign.h"
15 #include "include/private/base/SkDebug.h"
16 #include "include/private/base/SkMalloc.h"
17 #include "include/private/base/SkMath.h"
18 #include "include/private/base/SkMutex.h"
19 #include "include/private/base/SkTArray.h"
20 #include "include/private/base/SkTo.h"
21 #include "src/core/SkCachedData.h"
22 #include "src/core/SkChecksum.h"
23 #include "src/core/SkImageFilter_Base.h"
24 #include "src/core/SkMessageBus.h"
25 #include "src/core/SkTHash.h"
26
27 #if defined(SK_USE_DISCARDABLE_SCALEDIMAGECACHE)
28 #include "include/private/chromium/SkDiscardableMemory.h"
29 #endif
30
31 #include <algorithm>
32
33 using namespace skia_private;
34
DECLARE_SKMESSAGEBUS_MESSAGE(SkResourceCache::PurgeSharedIDMessage,uint32_t,true)35 DECLARE_SKMESSAGEBUS_MESSAGE(SkResourceCache::PurgeSharedIDMessage, uint32_t, true)
36
37 static inline bool SkShouldPostMessageToBus(
38 const SkResourceCache::PurgeSharedIDMessage&, uint32_t) {
39 // SkResourceCache is typically used as a singleton and we don't label Inboxes so all messages
40 // go to all inboxes.
41 return true;
42 }
43
44 // This can be defined by the caller's build system
45 //#define SK_USE_DISCARDABLE_SCALEDIMAGECACHE
46
47 #ifndef SK_DISCARDABLEMEMORY_SCALEDIMAGECACHE_COUNT_LIMIT
48 # define SK_DISCARDABLEMEMORY_SCALEDIMAGECACHE_COUNT_LIMIT 1024
49 #endif
50
51 #ifndef SK_DEFAULT_IMAGE_CACHE_LIMIT
52 #define SK_DEFAULT_IMAGE_CACHE_LIMIT (32 * 1024 * 1024)
53 #endif
54
init(void * nameSpace,uint64_t sharedID,size_t dataSize)55 void SkResourceCache::Key::init(void* nameSpace, uint64_t sharedID, size_t dataSize) {
56 SkASSERT(SkAlign4(dataSize) == dataSize);
57
58 // fCount32 and fHash are not hashed
59 static const int kUnhashedLocal32s = 2; // fCache32 + fHash
60 static const int kSharedIDLocal32s = 2; // fSharedID_lo + fSharedID_hi
61 static const int kHashedLocal32s = kSharedIDLocal32s + (sizeof(fNamespace) >> 2);
62 static const int kLocal32s = kUnhashedLocal32s + kHashedLocal32s;
63
64 static_assert(sizeof(Key) == (kLocal32s << 2), "unaccounted_key_locals");
65 static_assert(sizeof(Key) == offsetof(Key, fNamespace) + sizeof(fNamespace),
66 "namespace_field_must_be_last");
67
68 fCount32 = SkToS32(kLocal32s + (dataSize >> 2));
69 fSharedID_lo = (uint32_t)(sharedID & 0xFFFFFFFF);
70 fSharedID_hi = (uint32_t)(sharedID >> 32);
71 fNamespace = nameSpace;
72 // skip unhashed fields when computing the hash
73 fHash = SkChecksum::Hash32(this->as32() + kUnhashedLocal32s,
74 (fCount32 - kUnhashedLocal32s) << 2);
75 }
76
77 namespace {
78 struct HashTraits {
Hash__anon040879380111::HashTraits79 static uint32_t Hash(const SkResourceCache::Key& key) { return key.hash(); }
GetKey__anon040879380111::HashTraits80 static const SkResourceCache::Key& GetKey(const SkResourceCache::Rec* rec) {
81 return rec->getKey();
82 }
83 };
84 } // namespace
85
86 class SkResourceCache::Hash :
87 public THashTable<SkResourceCache::Rec*, SkResourceCache::Key, HashTraits> {};
88
89
90 ///////////////////////////////////////////////////////////////////////////////
91
init()92 void SkResourceCache::init() {
93 fHead = nullptr;
94 fTail = nullptr;
95 fHash = new Hash;
96 fTotalBytesUsed = 0;
97 fCount = 0;
98 fSingleAllocationByteLimit = 0;
99
100 // One of these should be explicit set by the caller after we return.
101 fTotalByteLimit = 0;
102 fDiscardableFactory = nullptr;
103 }
104
SkResourceCache(DiscardableFactory factory)105 SkResourceCache::SkResourceCache(DiscardableFactory factory)
106 : fPurgeSharedIDInbox(SK_InvalidUniqueID) {
107 this->init();
108 fDiscardableFactory = factory;
109 }
110
SkResourceCache(size_t byteLimit)111 SkResourceCache::SkResourceCache(size_t byteLimit)
112 : fPurgeSharedIDInbox(SK_InvalidUniqueID) {
113 this->init();
114 fTotalByteLimit = byteLimit;
115 }
116
~SkResourceCache()117 SkResourceCache::~SkResourceCache() {
118 Rec* rec = fHead;
119 while (rec) {
120 Rec* next = rec->fNext;
121 delete rec;
122 rec = next;
123 }
124 delete fHash;
125 }
126
127 ////////////////////////////////////////////////////////////////////////////////
128
find(const Key & key,FindVisitor visitor,void * context)129 bool SkResourceCache::find(const Key& key, FindVisitor visitor, void* context) {
130 this->checkMessages();
131
132 if (auto found = fHash->find(key)) {
133 Rec* rec = *found;
134 if (visitor(*rec, context)) {
135 this->moveToHead(rec); // for our LRU
136 return true;
137 } else {
138 this->remove(rec); // stale
139 return false;
140 }
141 }
142 return false;
143 }
144
make_size_str(size_t size,SkString * str)145 static void make_size_str(size_t size, SkString* str) {
146 const char suffix[] = { 'b', 'k', 'm', 'g', 't', 0 };
147 int i = 0;
148 while (suffix[i] && (size > 1024)) {
149 i += 1;
150 size >>= 10;
151 }
152 str->printf("%zu%c", size, suffix[i]);
153 }
154
155 static bool gDumpCacheTransactions;
156
add(Rec * rec,void * payload)157 void SkResourceCache::add(Rec* rec, void* payload) {
158 this->checkMessages();
159
160 SkASSERT(rec);
161 // See if we already have this key (racy inserts, etc.)
162 if (Rec** preexisting = fHash->find(rec->getKey())) {
163 Rec* prev = *preexisting;
164 if (prev->canBePurged()) {
165 // if it can be purged, the install may fail, so we have to remove it
166 this->remove(prev);
167 } else {
168 // if it cannot be purged, we reuse it and delete the new one
169 prev->postAddInstall(payload);
170 delete rec;
171 return;
172 }
173 }
174
175 this->addToHead(rec);
176 fHash->set(rec);
177 rec->postAddInstall(payload);
178
179 if (gDumpCacheTransactions) {
180 SkString bytesStr, totalStr;
181 make_size_str(rec->bytesUsed(), &bytesStr);
182 make_size_str(fTotalBytesUsed, &totalStr);
183 SkDebugf("RC: add %5s %12p key %08x -- total %5s, count %d\n",
184 bytesStr.c_str(), rec, rec->getHash(), totalStr.c_str(), fCount);
185 }
186
187 // since the new rec may push us over-budget, we perform a purge check now
188 this->purgeAsNeeded();
189 }
190
remove(Rec * rec)191 void SkResourceCache::remove(Rec* rec) {
192 SkASSERT(rec->canBePurged());
193 size_t used = rec->bytesUsed();
194 SkASSERT(used <= fTotalBytesUsed);
195
196 this->release(rec);
197 fHash->remove(rec->getKey());
198
199 fTotalBytesUsed -= used;
200 fCount -= 1;
201
202 //SkDebugf("-RC count [%3d] bytes %d\n", fCount, fTotalBytesUsed);
203
204 if (gDumpCacheTransactions) {
205 SkString bytesStr, totalStr;
206 make_size_str(used, &bytesStr);
207 make_size_str(fTotalBytesUsed, &totalStr);
208 SkDebugf("RC: remove %5s %12p key %08x -- total %5s, count %d\n",
209 bytesStr.c_str(), rec, rec->getHash(), totalStr.c_str(), fCount);
210 }
211
212 delete rec;
213 }
214
purgeAsNeeded(bool forcePurge)215 void SkResourceCache::purgeAsNeeded(bool forcePurge) {
216 size_t byteLimit;
217 int countLimit;
218
219 if (fDiscardableFactory) {
220 countLimit = SK_DISCARDABLEMEMORY_SCALEDIMAGECACHE_COUNT_LIMIT;
221 byteLimit = UINT32_MAX; // no limit based on bytes
222 } else {
223 countLimit = SK_MaxS32; // no limit based on count
224 byteLimit = fTotalByteLimit;
225 }
226
227 Rec* rec = fTail;
228 while (rec) {
229 if (!forcePurge && fTotalBytesUsed < byteLimit && fCount < countLimit) {
230 break;
231 }
232
233 Rec* prev = rec->fPrev;
234 if (rec->canBePurged()) {
235 this->remove(rec);
236 }
237 rec = prev;
238 }
239 }
240
241 //#define SK_TRACK_PURGE_SHAREDID_HITRATE
242
243 #ifdef SK_TRACK_PURGE_SHAREDID_HITRATE
244 static int gPurgeCallCounter;
245 static int gPurgeHitCounter;
246 #endif
247
purgeSharedID(uint64_t sharedID)248 void SkResourceCache::purgeSharedID(uint64_t sharedID) {
249 if (0 == sharedID) {
250 return;
251 }
252
253 #ifdef SK_TRACK_PURGE_SHAREDID_HITRATE
254 gPurgeCallCounter += 1;
255 bool found = false;
256 #endif
257 // go backwards, just like purgeAsNeeded, just to make the code similar.
258 // could iterate either direction and still be correct.
259 Rec* rec = fTail;
260 while (rec) {
261 Rec* prev = rec->fPrev;
262 if (rec->getKey().getSharedID() == sharedID) {
263 // even though the "src" is now dead, caches could still be in-flight, so
264 // we have to check if it can be removed.
265 if (rec->canBePurged()) {
266 this->remove(rec);
267 }
268 #ifdef SK_TRACK_PURGE_SHAREDID_HITRATE
269 found = true;
270 #endif
271 }
272 rec = prev;
273 }
274
275 #ifdef SK_TRACK_PURGE_SHAREDID_HITRATE
276 if (found) {
277 gPurgeHitCounter += 1;
278 }
279
280 SkDebugf("PurgeShared calls=%d hits=%d rate=%g\n", gPurgeCallCounter, gPurgeHitCounter,
281 gPurgeHitCounter * 100.0 / gPurgeCallCounter);
282 #endif
283 }
284
visitAll(Visitor visitor,void * context)285 void SkResourceCache::visitAll(Visitor visitor, void* context) {
286 // go backwards, just like purgeAsNeeded, just to make the code similar.
287 // could iterate either direction and still be correct.
288 Rec* rec = fTail;
289 while (rec) {
290 visitor(*rec, context);
291 rec = rec->fPrev;
292 }
293 }
294
295 ///////////////////////////////////////////////////////////////////////////////////////////////////
296
setTotalByteLimit(size_t newLimit)297 size_t SkResourceCache::setTotalByteLimit(size_t newLimit) {
298 size_t prevLimit = fTotalByteLimit;
299 fTotalByteLimit = newLimit;
300 if (newLimit < prevLimit) {
301 this->purgeAsNeeded();
302 }
303 return prevLimit;
304 }
305
newCachedData(size_t bytes)306 SkCachedData* SkResourceCache::newCachedData(size_t bytes) {
307 this->checkMessages();
308
309 if (fDiscardableFactory) {
310 SkDiscardableMemory* dm = fDiscardableFactory(bytes);
311 return dm ? new SkCachedData(bytes, dm) : nullptr;
312 } else {
313 return new SkCachedData(sk_malloc_throw(bytes), bytes);
314 }
315 }
316
317 ///////////////////////////////////////////////////////////////////////////////
318
release(Rec * rec)319 void SkResourceCache::release(Rec* rec) {
320 Rec* prev = rec->fPrev;
321 Rec* next = rec->fNext;
322
323 if (!prev) {
324 SkASSERT(fHead == rec);
325 fHead = next;
326 } else {
327 prev->fNext = next;
328 }
329
330 if (!next) {
331 fTail = prev;
332 } else {
333 next->fPrev = prev;
334 }
335
336 rec->fNext = rec->fPrev = nullptr;
337 }
338
moveToHead(Rec * rec)339 void SkResourceCache::moveToHead(Rec* rec) {
340 if (fHead == rec) {
341 return;
342 }
343
344 SkASSERT(fHead);
345 SkASSERT(fTail);
346
347 this->validate();
348
349 this->release(rec);
350
351 fHead->fPrev = rec;
352 rec->fNext = fHead;
353 fHead = rec;
354
355 this->validate();
356 }
357
addToHead(Rec * rec)358 void SkResourceCache::addToHead(Rec* rec) {
359 this->validate();
360
361 rec->fPrev = nullptr;
362 rec->fNext = fHead;
363 if (fHead) {
364 fHead->fPrev = rec;
365 }
366 fHead = rec;
367 if (!fTail) {
368 fTail = rec;
369 }
370 fTotalBytesUsed += rec->bytesUsed();
371 fCount += 1;
372
373 this->validate();
374 }
375
376 ///////////////////////////////////////////////////////////////////////////////
377
378 #ifdef SK_DEBUG
validate() const379 void SkResourceCache::validate() const {
380 if (nullptr == fHead) {
381 SkASSERT(nullptr == fTail);
382 SkASSERT(0 == fTotalBytesUsed);
383 return;
384 }
385
386 if (fHead == fTail) {
387 SkASSERT(nullptr == fHead->fPrev);
388 SkASSERT(nullptr == fHead->fNext);
389 SkASSERT(fHead->bytesUsed() == fTotalBytesUsed);
390 return;
391 }
392
393 SkASSERT(nullptr == fHead->fPrev);
394 SkASSERT(fHead->fNext);
395 SkASSERT(nullptr == fTail->fNext);
396 SkASSERT(fTail->fPrev);
397
398 size_t used = 0;
399 int count = 0;
400 const Rec* rec = fHead;
401 while (rec) {
402 count += 1;
403 used += rec->bytesUsed();
404 SkASSERT(used <= fTotalBytesUsed);
405 rec = rec->fNext;
406 }
407 SkASSERT(fCount == count);
408
409 rec = fTail;
410 while (rec) {
411 SkASSERT(count > 0);
412 count -= 1;
413 SkASSERT(used >= rec->bytesUsed());
414 used -= rec->bytesUsed();
415 rec = rec->fPrev;
416 }
417
418 SkASSERT(0 == count);
419 SkASSERT(0 == used);
420 }
421 #endif
422
dump() const423 void SkResourceCache::dump() const {
424 this->validate();
425
426 SkDebugf("SkResourceCache: count=%d bytes=%zu %s\n",
427 fCount, fTotalBytesUsed, fDiscardableFactory ? "discardable" : "malloc");
428 }
429
setSingleAllocationByteLimit(size_t newLimit)430 size_t SkResourceCache::setSingleAllocationByteLimit(size_t newLimit) {
431 size_t oldLimit = fSingleAllocationByteLimit;
432 fSingleAllocationByteLimit = newLimit;
433 return oldLimit;
434 }
435
getSingleAllocationByteLimit() const436 size_t SkResourceCache::getSingleAllocationByteLimit() const {
437 return fSingleAllocationByteLimit;
438 }
439
getEffectiveSingleAllocationByteLimit() const440 size_t SkResourceCache::getEffectiveSingleAllocationByteLimit() const {
441 // fSingleAllocationByteLimit == 0 means the caller is asking for our default
442 size_t limit = fSingleAllocationByteLimit;
443
444 // if we're not discardable (i.e. we are fixed-budget) then cap the single-limit
445 // to our budget.
446 if (nullptr == fDiscardableFactory) {
447 if (0 == limit) {
448 limit = fTotalByteLimit;
449 } else {
450 limit = std::min(limit, fTotalByteLimit);
451 }
452 }
453 return limit;
454 }
455
checkMessages()456 void SkResourceCache::checkMessages() {
457 TArray<PurgeSharedIDMessage> msgs;
458 fPurgeSharedIDInbox.poll(&msgs);
459 for (int i = 0; i < msgs.size(); ++i) {
460 this->purgeSharedID(msgs[i].fSharedID);
461 }
462 }
463
464 ///////////////////////////////////////////////////////////////////////////////
465
466 static SkResourceCache* gResourceCache = nullptr;
resource_cache_mutex()467 static SkMutex& resource_cache_mutex() {
468 static SkMutex& mutex = *(new SkMutex);
469 return mutex;
470 }
471
472 /** Must hold resource_cache_mutex() when calling. */
get_cache()473 static SkResourceCache* get_cache() {
474 // resource_cache_mutex() is always held when this is called, so we don't need to be fancy in here.
475 resource_cache_mutex().assertHeld();
476 if (nullptr == gResourceCache) {
477 #ifdef SK_USE_DISCARDABLE_SCALEDIMAGECACHE
478 gResourceCache = new SkResourceCache(SkDiscardableMemory::Create);
479 #else
480 gResourceCache = new SkResourceCache(SK_DEFAULT_IMAGE_CACHE_LIMIT);
481 #endif
482 }
483 return gResourceCache;
484 }
485
GetTotalBytesUsed()486 size_t SkResourceCache::GetTotalBytesUsed() {
487 SkAutoMutexExclusive am(resource_cache_mutex());
488 return get_cache()->getTotalBytesUsed();
489 }
490
GetTotalByteLimit()491 size_t SkResourceCache::GetTotalByteLimit() {
492 SkAutoMutexExclusive am(resource_cache_mutex());
493 return get_cache()->getTotalByteLimit();
494 }
495
SetTotalByteLimit(size_t newLimit)496 size_t SkResourceCache::SetTotalByteLimit(size_t newLimit) {
497 SkAutoMutexExclusive am(resource_cache_mutex());
498 return get_cache()->setTotalByteLimit(newLimit);
499 }
500
GetDiscardableFactory()501 SkResourceCache::DiscardableFactory SkResourceCache::GetDiscardableFactory() {
502 SkAutoMutexExclusive am(resource_cache_mutex());
503 return get_cache()->discardableFactory();
504 }
505
NewCachedData(size_t bytes)506 SkCachedData* SkResourceCache::NewCachedData(size_t bytes) {
507 SkAutoMutexExclusive am(resource_cache_mutex());
508 return get_cache()->newCachedData(bytes);
509 }
510
Dump()511 void SkResourceCache::Dump() {
512 SkAutoMutexExclusive am(resource_cache_mutex());
513 get_cache()->dump();
514 }
515
SetSingleAllocationByteLimit(size_t size)516 size_t SkResourceCache::SetSingleAllocationByteLimit(size_t size) {
517 SkAutoMutexExclusive am(resource_cache_mutex());
518 return get_cache()->setSingleAllocationByteLimit(size);
519 }
520
GetSingleAllocationByteLimit()521 size_t SkResourceCache::GetSingleAllocationByteLimit() {
522 SkAutoMutexExclusive am(resource_cache_mutex());
523 return get_cache()->getSingleAllocationByteLimit();
524 }
525
GetEffectiveSingleAllocationByteLimit()526 size_t SkResourceCache::GetEffectiveSingleAllocationByteLimit() {
527 SkAutoMutexExclusive am(resource_cache_mutex());
528 return get_cache()->getEffectiveSingleAllocationByteLimit();
529 }
530
PurgeAll()531 void SkResourceCache::PurgeAll() {
532 SkAutoMutexExclusive am(resource_cache_mutex());
533 return get_cache()->purgeAll();
534 }
535
CheckMessages()536 void SkResourceCache::CheckMessages() {
537 SkAutoMutexExclusive am(resource_cache_mutex());
538 return get_cache()->checkMessages();
539 }
540
Find(const Key & key,FindVisitor visitor,void * context)541 bool SkResourceCache::Find(const Key& key, FindVisitor visitor, void* context) {
542 SkAutoMutexExclusive am(resource_cache_mutex());
543 return get_cache()->find(key, visitor, context);
544 }
545
Add(Rec * rec,void * payload)546 void SkResourceCache::Add(Rec* rec, void* payload) {
547 SkAutoMutexExclusive am(resource_cache_mutex());
548 get_cache()->add(rec, payload);
549 }
550
VisitAll(Visitor visitor,void * context)551 void SkResourceCache::VisitAll(Visitor visitor, void* context) {
552 SkAutoMutexExclusive am(resource_cache_mutex());
553 get_cache()->visitAll(visitor, context);
554 }
555
PostPurgeSharedID(uint64_t sharedID)556 void SkResourceCache::PostPurgeSharedID(uint64_t sharedID) {
557 if (sharedID) {
558 SkMessageBus<PurgeSharedIDMessage, uint32_t>::Post(PurgeSharedIDMessage(sharedID));
559 }
560 }
561
562 ///////////////////////////////////////////////////////////////////////////////
563
GetResourceCacheTotalBytesUsed()564 size_t SkGraphics::GetResourceCacheTotalBytesUsed() {
565 return SkResourceCache::GetTotalBytesUsed();
566 }
567
GetResourceCacheTotalByteLimit()568 size_t SkGraphics::GetResourceCacheTotalByteLimit() {
569 return SkResourceCache::GetTotalByteLimit();
570 }
571
SetResourceCacheTotalByteLimit(size_t newLimit)572 size_t SkGraphics::SetResourceCacheTotalByteLimit(size_t newLimit) {
573 return SkResourceCache::SetTotalByteLimit(newLimit);
574 }
575
GetResourceCacheSingleAllocationByteLimit()576 size_t SkGraphics::GetResourceCacheSingleAllocationByteLimit() {
577 return SkResourceCache::GetSingleAllocationByteLimit();
578 }
579
SetResourceCacheSingleAllocationByteLimit(size_t newLimit)580 size_t SkGraphics::SetResourceCacheSingleAllocationByteLimit(size_t newLimit) {
581 return SkResourceCache::SetSingleAllocationByteLimit(newLimit);
582 }
583
PurgeResourceCache()584 void SkGraphics::PurgeResourceCache() {
585 SkImageFilter_Base::PurgeCache();
586 return SkResourceCache::PurgeAll();
587 }
588
589 /////////////
590
dump_visitor(const SkResourceCache::Rec & rec,void *)591 static void dump_visitor(const SkResourceCache::Rec& rec, void*) {
592 SkDebugf("RC: %12s bytes %9zu discardable %p\n",
593 rec.getCategory(), rec.bytesUsed(), rec.diagnostic_only_getDiscardable());
594 }
595
TestDumpMemoryStatistics()596 void SkResourceCache::TestDumpMemoryStatistics() {
597 VisitAll(dump_visitor, nullptr);
598 }
599
sk_trace_dump_visitor(const SkResourceCache::Rec & rec,void * context)600 static void sk_trace_dump_visitor(const SkResourceCache::Rec& rec, void* context) {
601 SkTraceMemoryDump* dump = static_cast<SkTraceMemoryDump*>(context);
602 SkString dumpName = SkStringPrintf("skia/sk_resource_cache/%s_%p", rec.getCategory(), &rec);
603 SkDiscardableMemory* discardable = rec.diagnostic_only_getDiscardable();
604 if (discardable) {
605 dump->setDiscardableMemoryBacking(dumpName.c_str(), *discardable);
606
607 // The discardable memory size will be calculated by dumper, but we also dump what we think
608 // the size of object in memory is irrespective of whether object is live or dead.
609 dump->dumpNumericValue(dumpName.c_str(), "discardable_size", "bytes", rec.bytesUsed());
610 } else {
611 dump->dumpNumericValue(dumpName.c_str(), "size", "bytes", rec.bytesUsed());
612 dump->setMemoryBacking(dumpName.c_str(), "malloc", nullptr);
613 }
614 }
615
DumpMemoryStatistics(SkTraceMemoryDump * dump)616 void SkResourceCache::DumpMemoryStatistics(SkTraceMemoryDump* dump) {
617 // Since resource could be backed by malloc or discardable, the cache always dumps detailed
618 // stats to be accurate.
619 VisitAll(sk_trace_dump_visitor, dump);
620 }
621