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