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