Home | History | Annotate | Download | only in gpu 
      1 /*
      2  * Copyright 2014 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 
      9 #include "GrResourceCache.h"
     10 
     11 #include "GrCaps.h"
     12 #include "GrGpuResourceCacheAccess.h"
     13 #include "GrTracing.h"
     14 #include "SkGr.h"
     15 #include "SkMessageBus.h"
     16 #include "SkOpts.h"
     17 #include "SkTSort.h"
     18 
     19 DECLARE_SKMESSAGEBUS_MESSAGE(GrUniqueKeyInvalidatedMessage);
     20 
     21 //////////////////////////////////////////////////////////////////////////////
     22 
     23 GrScratchKey::ResourceType GrScratchKey::GenerateResourceType() {
     24     static int32_t gType = INHERITED::kInvalidDomain + 1;
     25 
     26     int32_t type = sk_atomic_inc(&gType);
     27     if (type > SK_MaxU16) {
     28         SkFAIL("Too many Resource Types");
     29     }
     30 
     31     return static_cast<ResourceType>(type);
     32 }
     33 
     34 GrUniqueKey::Domain GrUniqueKey::GenerateDomain() {
     35     static int32_t gDomain = INHERITED::kInvalidDomain + 1;
     36 
     37     int32_t domain = sk_atomic_inc(&gDomain);
     38     if (domain > SK_MaxU16) {
     39         SkFAIL("Too many GrUniqueKey Domains");
     40     }
     41 
     42     return static_cast<Domain>(domain);
     43 }
     44 
     45 uint32_t GrResourceKeyHash(const uint32_t* data, size_t size) {
     46     return SkOpts::hash(data, size);
     47 }
     48 
     49 //////////////////////////////////////////////////////////////////////////////
     50 
     51 class GrResourceCache::AutoValidate : ::SkNoncopyable {
     52 public:
     53     AutoValidate(GrResourceCache* cache) : fCache(cache) { cache->validate(); }
     54     ~AutoValidate() { fCache->validate(); }
     55 private:
     56     GrResourceCache* fCache;
     57 };
     58 
     59  //////////////////////////////////////////////////////////////////////////////
     60 
     61 
     62 GrResourceCache::GrResourceCache(const GrCaps* caps)
     63     : fTimestamp(0)
     64     , fMaxCount(kDefaultMaxCount)
     65     , fMaxBytes(kDefaultMaxSize)
     66     , fMaxUnusedFlushes(kDefaultMaxUnusedFlushes)
     67 #if GR_CACHE_STATS
     68     , fHighWaterCount(0)
     69     , fHighWaterBytes(0)
     70     , fBudgetedHighWaterCount(0)
     71     , fBudgetedHighWaterBytes(0)
     72 #endif
     73     , fBytes(0)
     74     , fBudgetedCount(0)
     75     , fBudgetedBytes(0)
     76     , fRequestFlush(false)
     77     , fExternalFlushCnt(0)
     78     , fPreferVRAMUseOverFlushes(caps->preferVRAMUseOverFlushes()) {
     79     SkDEBUGCODE(fCount = 0;)
     80     SkDEBUGCODE(fNewlyPurgeableResourceForValidation = nullptr;)
     81 }
     82 
     83 GrResourceCache::~GrResourceCache() {
     84     this->releaseAll();
     85 }
     86 
     87 void GrResourceCache::setLimits(int count, size_t bytes, int maxUnusedFlushes) {
     88     fMaxCount = count;
     89     fMaxBytes = bytes;
     90     fMaxUnusedFlushes = maxUnusedFlushes;
     91     this->purgeAsNeeded();
     92 }
     93 
     94 void GrResourceCache::insertResource(GrGpuResource* resource) {
     95     SkASSERT(resource);
     96     SkASSERT(!this->isInCache(resource));
     97     SkASSERT(!resource->wasDestroyed());
     98     SkASSERT(!resource->isPurgeable());
     99 
    100     // We must set the timestamp before adding to the array in case the timestamp wraps and we wind
    101     // up iterating over all the resources that already have timestamps.
    102     resource->cacheAccess().setTimestamp(this->getNextTimestamp());
    103 
    104     this->addToNonpurgeableArray(resource);
    105 
    106     size_t size = resource->gpuMemorySize();
    107     SkDEBUGCODE(++fCount;)
    108     fBytes += size;
    109 #if GR_CACHE_STATS
    110     fHighWaterCount = SkTMax(this->getResourceCount(), fHighWaterCount);
    111     fHighWaterBytes = SkTMax(fBytes, fHighWaterBytes);
    112 #endif
    113     if (SkBudgeted::kYes == resource->resourcePriv().isBudgeted()) {
    114         ++fBudgetedCount;
    115         fBudgetedBytes += size;
    116         TRACE_COUNTER2(TRACE_DISABLED_BY_DEFAULT("skia.gpu.cache"), "skia budget", "used",
    117                        fBudgetedBytes, "free", fMaxBytes - fBudgetedBytes);
    118 #if GR_CACHE_STATS
    119         fBudgetedHighWaterCount = SkTMax(fBudgetedCount, fBudgetedHighWaterCount);
    120         fBudgetedHighWaterBytes = SkTMax(fBudgetedBytes, fBudgetedHighWaterBytes);
    121 #endif
    122     }
    123     if (resource->resourcePriv().getScratchKey().isValid() &&
    124         !resource->getUniqueKey().isValid()) {
    125         SkASSERT(!resource->resourcePriv().refsWrappedObjects());
    126         fScratchMap.insert(resource->resourcePriv().getScratchKey(), resource);
    127     }
    128 
    129     this->purgeAsNeeded();
    130 }
    131 
    132 void GrResourceCache::removeResource(GrGpuResource* resource) {
    133     this->validate();
    134     SkASSERT(this->isInCache(resource));
    135 
    136     if (resource->isPurgeable()) {
    137         fPurgeableQueue.remove(resource);
    138     } else {
    139         this->removeFromNonpurgeableArray(resource);
    140     }
    141 
    142     size_t size = resource->gpuMemorySize();
    143     SkDEBUGCODE(--fCount;)
    144     fBytes -= size;
    145     if (SkBudgeted::kYes == resource->resourcePriv().isBudgeted()) {
    146         --fBudgetedCount;
    147         fBudgetedBytes -= size;
    148         TRACE_COUNTER2(TRACE_DISABLED_BY_DEFAULT("skia.gpu.cache"), "skia budget", "used",
    149                        fBudgetedBytes, "free", fMaxBytes - fBudgetedBytes);
    150     }
    151 
    152     if (resource->resourcePriv().getScratchKey().isValid() &&
    153         !resource->getUniqueKey().isValid()) {
    154         fScratchMap.remove(resource->resourcePriv().getScratchKey(), resource);
    155     }
    156     if (resource->getUniqueKey().isValid()) {
    157         fUniqueHash.remove(resource->getUniqueKey());
    158     }
    159     this->validate();
    160 }
    161 
    162 void GrResourceCache::abandonAll() {
    163     AutoValidate av(this);
    164 
    165     while (fNonpurgeableResources.count()) {
    166         GrGpuResource* back = *(fNonpurgeableResources.end() - 1);
    167         SkASSERT(!back->wasDestroyed());
    168         back->cacheAccess().abandon();
    169     }
    170 
    171     while (fPurgeableQueue.count()) {
    172         GrGpuResource* top = fPurgeableQueue.peek();
    173         SkASSERT(!top->wasDestroyed());
    174         top->cacheAccess().abandon();
    175     }
    176 
    177     SkASSERT(!fScratchMap.count());
    178     SkASSERT(!fUniqueHash.count());
    179     SkASSERT(!fCount);
    180     SkASSERT(!this->getResourceCount());
    181     SkASSERT(!fBytes);
    182     SkASSERT(!fBudgetedCount);
    183     SkASSERT(!fBudgetedBytes);
    184 }
    185 
    186 void GrResourceCache::releaseAll() {
    187     AutoValidate av(this);
    188 
    189     while(fNonpurgeableResources.count()) {
    190         GrGpuResource* back = *(fNonpurgeableResources.end() - 1);
    191         SkASSERT(!back->wasDestroyed());
    192         back->cacheAccess().release();
    193     }
    194 
    195     while (fPurgeableQueue.count()) {
    196         GrGpuResource* top = fPurgeableQueue.peek();
    197         SkASSERT(!top->wasDestroyed());
    198         top->cacheAccess().release();
    199     }
    200 
    201     SkASSERT(!fScratchMap.count());
    202     SkASSERT(!fUniqueHash.count());
    203     SkASSERT(!fCount);
    204     SkASSERT(!this->getResourceCount());
    205     SkASSERT(!fBytes);
    206     SkASSERT(!fBudgetedCount);
    207     SkASSERT(!fBudgetedBytes);
    208 }
    209 
    210 class GrResourceCache::AvailableForScratchUse {
    211 public:
    212     AvailableForScratchUse(bool rejectPendingIO) : fRejectPendingIO(rejectPendingIO) { }
    213 
    214     bool operator()(const GrGpuResource* resource) const {
    215         SkASSERT(!resource->getUniqueKey().isValid() &&
    216                  resource->resourcePriv().getScratchKey().isValid());
    217         if (resource->internalHasRef() || !resource->cacheAccess().isScratch()) {
    218             return false;
    219         }
    220         return !fRejectPendingIO || !resource->internalHasPendingIO();
    221     }
    222 
    223 private:
    224     bool fRejectPendingIO;
    225 };
    226 
    227 GrGpuResource* GrResourceCache::findAndRefScratchResource(const GrScratchKey& scratchKey,
    228                                                           size_t resourceSize,
    229                                                           uint32_t flags) {
    230     SkASSERT(scratchKey.isValid());
    231 
    232     GrGpuResource* resource;
    233     if (flags & (kPreferNoPendingIO_ScratchFlag | kRequireNoPendingIO_ScratchFlag)) {
    234         resource = fScratchMap.find(scratchKey, AvailableForScratchUse(true));
    235         if (resource) {
    236             this->refAndMakeResourceMRU(resource);
    237             this->validate();
    238             return resource;
    239         } else if (flags & kRequireNoPendingIO_ScratchFlag) {
    240             return nullptr;
    241         }
    242         // We would prefer to consume more available VRAM rather than flushing
    243         // immediately, but on ANGLE this can lead to starving of the GPU.
    244         if (fPreferVRAMUseOverFlushes && this->wouldFit(resourceSize)) {
    245             // kPrefer is specified, we didn't find a resource without pending io,
    246             // but there is still space in our budget for the resource so force
    247             // the caller to allocate a new resource.
    248             return nullptr;
    249         }
    250     }
    251     resource = fScratchMap.find(scratchKey, AvailableForScratchUse(false));
    252     if (resource) {
    253         this->refAndMakeResourceMRU(resource);
    254         this->validate();
    255     }
    256     return resource;
    257 }
    258 
    259 void GrResourceCache::willRemoveScratchKey(const GrGpuResource* resource) {
    260     SkASSERT(resource->resourcePriv().getScratchKey().isValid());
    261     if (!resource->getUniqueKey().isValid()) {
    262         fScratchMap.remove(resource->resourcePriv().getScratchKey(), resource);
    263     }
    264 }
    265 
    266 void GrResourceCache::removeUniqueKey(GrGpuResource* resource) {
    267     // Someone has a ref to this resource in order to have removed the key. When the ref count
    268     // reaches zero we will get a ref cnt notification and figure out what to do with it.
    269     if (resource->getUniqueKey().isValid()) {
    270         SkASSERT(resource == fUniqueHash.find(resource->getUniqueKey()));
    271         fUniqueHash.remove(resource->getUniqueKey());
    272     }
    273     resource->cacheAccess().removeUniqueKey();
    274 
    275     if (resource->resourcePriv().getScratchKey().isValid()) {
    276         fScratchMap.insert(resource->resourcePriv().getScratchKey(), resource);
    277     }
    278 
    279     this->validate();
    280 }
    281 
    282 void GrResourceCache::changeUniqueKey(GrGpuResource* resource, const GrUniqueKey& newKey) {
    283     SkASSERT(resource);
    284     SkASSERT(this->isInCache(resource));
    285 
    286     // If another resource has the new key, remove its key then install the key on this resource.
    287     if (newKey.isValid()) {
    288         // Remove the entry for this resource if it already has a unique key.
    289         if (resource->getUniqueKey().isValid()) {
    290             SkASSERT(resource == fUniqueHash.find(resource->getUniqueKey()));
    291             fUniqueHash.remove(resource->getUniqueKey());
    292             SkASSERT(nullptr == fUniqueHash.find(resource->getUniqueKey()));
    293         } else {
    294             // 'resource' didn't have a valid unique key before so it is switching sides. Remove it
    295             // from the ScratchMap
    296             if (resource->resourcePriv().getScratchKey().isValid()) {
    297                 fScratchMap.remove(resource->resourcePriv().getScratchKey(), resource);
    298             }
    299         }
    300 
    301         if (GrGpuResource* old = fUniqueHash.find(newKey)) {
    302             // If the old resource using the key is purgeable and is unreachable, then remove it.
    303             if (!old->resourcePriv().getScratchKey().isValid() && old->isPurgeable()) {
    304                 // release may call validate() which will assert that resource is in fUniqueHash
    305                 // if it has a valid key. So in debug reset the key here before we assign it.
    306                 SkDEBUGCODE(resource->cacheAccess().removeUniqueKey();)
    307                 old->cacheAccess().release();
    308             } else {
    309                 this->removeUniqueKey(old);
    310             }
    311         }
    312         SkASSERT(nullptr == fUniqueHash.find(newKey));
    313         resource->cacheAccess().setUniqueKey(newKey);
    314         fUniqueHash.add(resource);
    315     } else {
    316         this->removeUniqueKey(resource);
    317     }
    318 
    319     this->validate();
    320 }
    321 
    322 void GrResourceCache::refAndMakeResourceMRU(GrGpuResource* resource) {
    323     SkASSERT(resource);
    324     SkASSERT(this->isInCache(resource));
    325 
    326     if (resource->isPurgeable()) {
    327         // It's about to become unpurgeable.
    328         fPurgeableQueue.remove(resource);
    329         this->addToNonpurgeableArray(resource);
    330     }
    331     resource->ref();
    332 
    333     resource->cacheAccess().setTimestamp(this->getNextTimestamp());
    334     this->validate();
    335 }
    336 
    337 void GrResourceCache::notifyCntReachedZero(GrGpuResource* resource, uint32_t flags) {
    338     SkASSERT(resource);
    339     SkASSERT(!resource->wasDestroyed());
    340     SkASSERT(flags);
    341     SkASSERT(this->isInCache(resource));
    342     // This resource should always be in the nonpurgeable array when this function is called. It
    343     // will be moved to the queue if it is newly purgeable.
    344     SkASSERT(fNonpurgeableResources[*resource->cacheAccess().accessCacheIndex()] == resource);
    345 
    346     if (SkToBool(ResourceAccess::kRefCntReachedZero_RefNotificationFlag & flags)) {
    347 #ifdef SK_DEBUG
    348         // When the timestamp overflows validate() is called. validate() checks that resources in
    349         // the nonpurgeable array are indeed not purgeable. However, the movement from the array to
    350         // the purgeable queue happens just below in this function. So we mark it as an exception.
    351         if (resource->isPurgeable()) {
    352             fNewlyPurgeableResourceForValidation = resource;
    353         }
    354 #endif
    355         resource->cacheAccess().setTimestamp(this->getNextTimestamp());
    356         SkDEBUGCODE(fNewlyPurgeableResourceForValidation = nullptr);
    357     }
    358 
    359     if (!SkToBool(ResourceAccess::kAllCntsReachedZero_RefNotificationFlag & flags)) {
    360         SkASSERT(!resource->isPurgeable());
    361         return;
    362     }
    363 
    364     SkASSERT(resource->isPurgeable());
    365     this->removeFromNonpurgeableArray(resource);
    366     fPurgeableQueue.insert(resource);
    367     resource->cacheAccess().setFlushCntWhenResourceBecamePurgeable(fExternalFlushCnt);
    368     resource->cacheAccess().setTimeWhenResourceBecomePurgeable();
    369 
    370     if (SkBudgeted::kNo == resource->resourcePriv().isBudgeted()) {
    371         // Check whether this resource could still be used as a scratch resource.
    372         if (!resource->resourcePriv().refsWrappedObjects() &&
    373             resource->resourcePriv().getScratchKey().isValid()) {
    374             // We won't purge an existing resource to make room for this one.
    375             if (fBudgetedCount < fMaxCount &&
    376                 fBudgetedBytes + resource->gpuMemorySize() <= fMaxBytes) {
    377                 resource->resourcePriv().makeBudgeted();
    378                 return;
    379             }
    380         }
    381     } else {
    382         // Purge the resource immediately if we're over budget
    383         // Also purge if the resource has neither a valid scratch key nor a unique key.
    384         bool noKey = !resource->resourcePriv().getScratchKey().isValid() &&
    385                      !resource->getUniqueKey().isValid();
    386         if (!this->overBudget() && !noKey) {
    387             return;
    388         }
    389     }
    390 
    391     SkDEBUGCODE(int beforeCount = this->getResourceCount();)
    392     resource->cacheAccess().release();
    393     // We should at least free this resource, perhaps dependent resources as well.
    394     SkASSERT(this->getResourceCount() < beforeCount);
    395     this->validate();
    396 }
    397 
    398 void GrResourceCache::didChangeGpuMemorySize(const GrGpuResource* resource, size_t oldSize) {
    399     // SkASSERT(!fPurging); GrPathRange increases size during flush. :(
    400     SkASSERT(resource);
    401     SkASSERT(this->isInCache(resource));
    402 
    403     ptrdiff_t delta = resource->gpuMemorySize() - oldSize;
    404 
    405     fBytes += delta;
    406 #if GR_CACHE_STATS
    407     fHighWaterBytes = SkTMax(fBytes, fHighWaterBytes);
    408 #endif
    409     if (SkBudgeted::kYes == resource->resourcePriv().isBudgeted()) {
    410         fBudgetedBytes += delta;
    411         TRACE_COUNTER2(TRACE_DISABLED_BY_DEFAULT("skia.gpu.cache"), "skia budget", "used",
    412                        fBudgetedBytes, "free", fMaxBytes - fBudgetedBytes);
    413 #if GR_CACHE_STATS
    414         fBudgetedHighWaterBytes = SkTMax(fBudgetedBytes, fBudgetedHighWaterBytes);
    415 #endif
    416     }
    417 
    418     this->purgeAsNeeded();
    419     this->validate();
    420 }
    421 
    422 void GrResourceCache::didChangeBudgetStatus(GrGpuResource* resource) {
    423     SkASSERT(resource);
    424     SkASSERT(this->isInCache(resource));
    425 
    426     size_t size = resource->gpuMemorySize();
    427 
    428     if (SkBudgeted::kYes == resource->resourcePriv().isBudgeted()) {
    429         ++fBudgetedCount;
    430         fBudgetedBytes += size;
    431 #if GR_CACHE_STATS
    432         fBudgetedHighWaterBytes = SkTMax(fBudgetedBytes, fBudgetedHighWaterBytes);
    433         fBudgetedHighWaterCount = SkTMax(fBudgetedCount, fBudgetedHighWaterCount);
    434 #endif
    435         this->purgeAsNeeded();
    436     } else {
    437         --fBudgetedCount;
    438         fBudgetedBytes -= size;
    439     }
    440     TRACE_COUNTER2(TRACE_DISABLED_BY_DEFAULT("skia.gpu.cache"), "skia budget", "used",
    441                    fBudgetedBytes, "free", fMaxBytes - fBudgetedBytes);
    442 
    443     this->validate();
    444 }
    445 
    446 void GrResourceCache::purgeAsNeeded() {
    447     SkTArray<GrUniqueKeyInvalidatedMessage> invalidKeyMsgs;
    448     fInvalidUniqueKeyInbox.poll(&invalidKeyMsgs);
    449     if (invalidKeyMsgs.count()) {
    450         this->processInvalidUniqueKeys(invalidKeyMsgs);
    451     }
    452 
    453     if (fMaxUnusedFlushes > 0) {
    454         // We want to know how many complete flushes have occurred without the resource being used.
    455         // If the resource was tagged when fExternalFlushCnt was N then this means it became
    456         // purgeable during activity that became the N+1th flush. So when the flush count is N+2
    457         // it has sat in the purgeable queue for one entire flush.
    458         uint32_t oldestAllowedFlushCnt = fExternalFlushCnt - fMaxUnusedFlushes - 1;
    459         // check for underflow
    460         if (oldestAllowedFlushCnt < fExternalFlushCnt) {
    461             while (fPurgeableQueue.count()) {
    462                 uint32_t flushWhenResourceBecamePurgeable =
    463                         fPurgeableQueue.peek()->cacheAccess().flushCntWhenResourceBecamePurgeable();
    464                 if (oldestAllowedFlushCnt < flushWhenResourceBecamePurgeable) {
    465                     // Resources were given both LRU timestamps and tagged with a flush cnt when
    466                     // they first became purgeable. The LRU timestamp won't change again until the
    467                     // resource is made non-purgeable again. So, at this point all the remaining
    468                     // resources in the timestamp-sorted queue will have a flush count >= to this
    469                     // one.
    470                     break;
    471                 }
    472                 GrGpuResource* resource = fPurgeableQueue.peek();
    473                 SkASSERT(resource->isPurgeable());
    474                 resource->cacheAccess().release();
    475             }
    476         }
    477     }
    478 
    479     bool stillOverbudget = this->overBudget();
    480     while (stillOverbudget && fPurgeableQueue.count()) {
    481         GrGpuResource* resource = fPurgeableQueue.peek();
    482         SkASSERT(resource->isPurgeable());
    483         resource->cacheAccess().release();
    484         stillOverbudget = this->overBudget();
    485     }
    486 
    487     this->validate();
    488 
    489     if (stillOverbudget) {
    490         // Set this so that GrDrawingManager will issue a flush to free up resources with pending
    491         // IO that we were unable to purge in this pass.
    492         fRequestFlush = true;
    493     }
    494 }
    495 
    496 void GrResourceCache::purgeAllUnlocked() {
    497     // We could disable maintaining the heap property here, but it would add a lot of complexity.
    498     // Moreover, this is rarely called.
    499     while (fPurgeableQueue.count()) {
    500         GrGpuResource* resource = fPurgeableQueue.peek();
    501         SkASSERT(resource->isPurgeable());
    502         resource->cacheAccess().release();
    503     }
    504 
    505     this->validate();
    506 }
    507 
    508 void GrResourceCache::purgeResourcesNotUsedSince(GrStdSteadyClock::time_point purgeTime) {
    509     while (fPurgeableQueue.count()) {
    510         const GrStdSteadyClock::time_point resourceTime =
    511                 fPurgeableQueue.peek()->cacheAccess().timeWhenResourceBecamePurgeable();
    512         if (resourceTime >= purgeTime) {
    513             // Resources were given both LRU timestamps and tagged with a frame number when
    514             // they first became purgeable. The LRU timestamp won't change again until the
    515             // resource is made non-purgeable again. So, at this point all the remaining
    516             // resources in the timestamp-sorted queue will have a frame number >= to this
    517             // one.
    518             break;
    519         }
    520         GrGpuResource* resource = fPurgeableQueue.peek();
    521         SkASSERT(resource->isPurgeable());
    522         resource->cacheAccess().release();
    523     }
    524 }
    525 
    526 void GrResourceCache::processInvalidUniqueKeys(
    527     const SkTArray<GrUniqueKeyInvalidatedMessage>& msgs) {
    528     for (int i = 0; i < msgs.count(); ++i) {
    529         GrGpuResource* resource = this->findAndRefUniqueResource(msgs[i].key());
    530         if (resource) {
    531             resource->resourcePriv().removeUniqueKey();
    532             resource->unref(); // If this resource is now purgeable, the cache will be notified.
    533         }
    534     }
    535 }
    536 
    537 void GrResourceCache::addToNonpurgeableArray(GrGpuResource* resource) {
    538     int index = fNonpurgeableResources.count();
    539     *fNonpurgeableResources.append() = resource;
    540     *resource->cacheAccess().accessCacheIndex() = index;
    541 }
    542 
    543 void GrResourceCache::removeFromNonpurgeableArray(GrGpuResource* resource) {
    544     int* index = resource->cacheAccess().accessCacheIndex();
    545     // Fill the whole we will create in the array with the tail object, adjust its index, and
    546     // then pop the array
    547     GrGpuResource* tail = *(fNonpurgeableResources.end() - 1);
    548     SkASSERT(fNonpurgeableResources[*index] == resource);
    549     fNonpurgeableResources[*index] = tail;
    550     *tail->cacheAccess().accessCacheIndex() = *index;
    551     fNonpurgeableResources.pop();
    552     SkDEBUGCODE(*index = -1);
    553 }
    554 
    555 uint32_t GrResourceCache::getNextTimestamp() {
    556     // If we wrap then all the existing resources will appear older than any resources that get
    557     // a timestamp after the wrap.
    558     if (0 == fTimestamp) {
    559         int count = this->getResourceCount();
    560         if (count) {
    561             // Reset all the timestamps. We sort the resources by timestamp and then assign
    562             // sequential timestamps beginning with 0. This is O(n*lg(n)) but it should be extremely
    563             // rare.
    564             SkTDArray<GrGpuResource*> sortedPurgeableResources;
    565             sortedPurgeableResources.setReserve(fPurgeableQueue.count());
    566 
    567             while (fPurgeableQueue.count()) {
    568                 *sortedPurgeableResources.append() = fPurgeableQueue.peek();
    569                 fPurgeableQueue.pop();
    570             }
    571 
    572             SkTQSort(fNonpurgeableResources.begin(), fNonpurgeableResources.end() - 1,
    573                      CompareTimestamp);
    574 
    575             // Pick resources out of the purgeable and non-purgeable arrays based on lowest
    576             // timestamp and assign new timestamps.
    577             int currP = 0;
    578             int currNP = 0;
    579             while (currP < sortedPurgeableResources.count() &&
    580                    currNP < fNonpurgeableResources.count()) {
    581                 uint32_t tsP = sortedPurgeableResources[currP]->cacheAccess().timestamp();
    582                 uint32_t tsNP = fNonpurgeableResources[currNP]->cacheAccess().timestamp();
    583                 SkASSERT(tsP != tsNP);
    584                 if (tsP < tsNP) {
    585                     sortedPurgeableResources[currP++]->cacheAccess().setTimestamp(fTimestamp++);
    586                 } else {
    587                     // Correct the index in the nonpurgeable array stored on the resource post-sort.
    588                     *fNonpurgeableResources[currNP]->cacheAccess().accessCacheIndex() = currNP;
    589                     fNonpurgeableResources[currNP++]->cacheAccess().setTimestamp(fTimestamp++);
    590                 }
    591             }
    592 
    593             // The above loop ended when we hit the end of one array. Finish the other one.
    594             while (currP < sortedPurgeableResources.count()) {
    595                 sortedPurgeableResources[currP++]->cacheAccess().setTimestamp(fTimestamp++);
    596             }
    597             while (currNP < fNonpurgeableResources.count()) {
    598                 *fNonpurgeableResources[currNP]->cacheAccess().accessCacheIndex() = currNP;
    599                 fNonpurgeableResources[currNP++]->cacheAccess().setTimestamp(fTimestamp++);
    600             }
    601 
    602             // Rebuild the queue.
    603             for (int i = 0; i < sortedPurgeableResources.count(); ++i) {
    604                 fPurgeableQueue.insert(sortedPurgeableResources[i]);
    605             }
    606 
    607             this->validate();
    608             SkASSERT(count == this->getResourceCount());
    609 
    610             // count should be the next timestamp we return.
    611             SkASSERT(fTimestamp == SkToU32(count));
    612         }
    613     }
    614     return fTimestamp++;
    615 }
    616 
    617 void GrResourceCache::notifyFlushOccurred(FlushType type) {
    618     switch (type) {
    619         case FlushType::kImmediateMode:
    620             break;
    621         case FlushType::kCacheRequested:
    622             SkASSERT(fRequestFlush);
    623             fRequestFlush = false;
    624             break;
    625         case FlushType::kExternal:
    626             ++fExternalFlushCnt;
    627             if (0 == fExternalFlushCnt) {
    628                 // When this wraps just reset all the purgeable resources' last used flush state.
    629                 for (int i = 0; i < fPurgeableQueue.count(); ++i) {
    630                     fPurgeableQueue.at(i)->cacheAccess().setFlushCntWhenResourceBecamePurgeable(0);
    631                 }
    632             }
    633             break;
    634     }
    635     this->purgeAsNeeded();
    636 }
    637 
    638 void GrResourceCache::dumpMemoryStatistics(SkTraceMemoryDump* traceMemoryDump) const {
    639     for (int i = 0; i < fNonpurgeableResources.count(); ++i) {
    640         fNonpurgeableResources[i]->dumpMemoryStatistics(traceMemoryDump);
    641     }
    642     for (int i = 0; i < fPurgeableQueue.count(); ++i) {
    643         fPurgeableQueue.at(i)->dumpMemoryStatistics(traceMemoryDump);
    644     }
    645 }
    646 
    647 #ifdef SK_DEBUG
    648 void GrResourceCache::validate() const {
    649     // Reduce the frequency of validations for large resource counts.
    650     static SkRandom gRandom;
    651     int mask = (SkNextPow2(fCount + 1) >> 5) - 1;
    652     if (~mask && (gRandom.nextU() & mask)) {
    653         return;
    654     }
    655 
    656     struct Stats {
    657         size_t fBytes;
    658         int fBudgetedCount;
    659         size_t fBudgetedBytes;
    660         int fLocked;
    661         int fScratch;
    662         int fCouldBeScratch;
    663         int fContent;
    664         const ScratchMap* fScratchMap;
    665         const UniqueHash* fUniqueHash;
    666 
    667         Stats(const GrResourceCache* cache) {
    668             memset(this, 0, sizeof(*this));
    669             fScratchMap = &cache->fScratchMap;
    670             fUniqueHash = &cache->fUniqueHash;
    671         }
    672 
    673         void update(GrGpuResource* resource) {
    674             fBytes += resource->gpuMemorySize();
    675 
    676             if (!resource->isPurgeable()) {
    677                 ++fLocked;
    678             }
    679 
    680             const GrScratchKey& scratchKey = resource->resourcePriv().getScratchKey();
    681             const GrUniqueKey& uniqueKey = resource->getUniqueKey();
    682 
    683             if (resource->cacheAccess().isScratch()) {
    684                 SkASSERT(!uniqueKey.isValid());
    685                 ++fScratch;
    686                 SkASSERT(fScratchMap->countForKey(scratchKey));
    687                 SkASSERT(!resource->resourcePriv().refsWrappedObjects());
    688             } else if (scratchKey.isValid()) {
    689                 SkASSERT(SkBudgeted::kNo == resource->resourcePriv().isBudgeted() ||
    690                          uniqueKey.isValid());
    691                 if (!uniqueKey.isValid()) {
    692                     ++fCouldBeScratch;
    693                     SkASSERT(fScratchMap->countForKey(scratchKey));
    694                 }
    695                 SkASSERT(!resource->resourcePriv().refsWrappedObjects());
    696             }
    697             if (uniqueKey.isValid()) {
    698                 ++fContent;
    699                 SkASSERT(fUniqueHash->find(uniqueKey) == resource);
    700                 SkASSERT(!resource->resourcePriv().refsWrappedObjects());
    701                 SkASSERT(SkBudgeted::kYes == resource->resourcePriv().isBudgeted());
    702 
    703                 if (scratchKey.isValid()) {
    704                     SkASSERT(!fScratchMap->has(resource, scratchKey));
    705                 }
    706             }
    707 
    708             if (SkBudgeted::kYes == resource->resourcePriv().isBudgeted()) {
    709                 ++fBudgetedCount;
    710                 fBudgetedBytes += resource->gpuMemorySize();
    711             }
    712         }
    713     };
    714 
    715     {
    716         ScratchMap::ConstIter iter(&fScratchMap);
    717 
    718         int count = 0;
    719         for ( ; !iter.done(); ++iter) {
    720             const GrGpuResource* resource = *iter;
    721             SkASSERT(resource->resourcePriv().getScratchKey().isValid());
    722             SkASSERT(!resource->getUniqueKey().isValid());
    723             count++;
    724         }
    725         SkASSERT(count == fScratchMap.count()); // ensure the iterator is working correctly
    726     }
    727 
    728     Stats stats(this);
    729 
    730     for (int i = 0; i < fNonpurgeableResources.count(); ++i) {
    731         SkASSERT(!fNonpurgeableResources[i]->isPurgeable() ||
    732                  fNewlyPurgeableResourceForValidation == fNonpurgeableResources[i]);
    733         SkASSERT(*fNonpurgeableResources[i]->cacheAccess().accessCacheIndex() == i);
    734         SkASSERT(!fNonpurgeableResources[i]->wasDestroyed());
    735         stats.update(fNonpurgeableResources[i]);
    736     }
    737     for (int i = 0; i < fPurgeableQueue.count(); ++i) {
    738         SkASSERT(fPurgeableQueue.at(i)->isPurgeable());
    739         SkASSERT(*fPurgeableQueue.at(i)->cacheAccess().accessCacheIndex() == i);
    740         SkASSERT(!fPurgeableQueue.at(i)->wasDestroyed());
    741         stats.update(fPurgeableQueue.at(i));
    742     }
    743 
    744     SkASSERT(fCount == this->getResourceCount());
    745     SkASSERT(fBudgetedCount <= fCount);
    746     SkASSERT(fBudgetedBytes <= fBytes);
    747     SkASSERT(stats.fBytes == fBytes);
    748     SkASSERT(stats.fBudgetedBytes == fBudgetedBytes);
    749     SkASSERT(stats.fBudgetedCount == fBudgetedCount);
    750 #if GR_CACHE_STATS
    751     SkASSERT(fBudgetedHighWaterCount <= fHighWaterCount);
    752     SkASSERT(fBudgetedHighWaterBytes <= fHighWaterBytes);
    753     SkASSERT(fBytes <= fHighWaterBytes);
    754     SkASSERT(fCount <= fHighWaterCount);
    755     SkASSERT(fBudgetedBytes <= fBudgetedHighWaterBytes);
    756     SkASSERT(fBudgetedCount <= fBudgetedHighWaterCount);
    757 #endif
    758     SkASSERT(stats.fContent == fUniqueHash.count());
    759     SkASSERT(stats.fScratch + stats.fCouldBeScratch == fScratchMap.count());
    760 
    761     // This assertion is not currently valid because we can be in recursive notifyCntReachedZero()
    762     // calls. This will be fixed when subresource registration is explicit.
    763     // bool overBudget = budgetedBytes > fMaxBytes || budgetedCount > fMaxCount;
    764     // SkASSERT(!overBudget || locked == count || fPurging);
    765 }
    766 
    767 bool GrResourceCache::isInCache(const GrGpuResource* resource) const {
    768     int index = *resource->cacheAccess().accessCacheIndex();
    769     if (index < 0) {
    770         return false;
    771     }
    772     if (index < fPurgeableQueue.count() && fPurgeableQueue.at(index) == resource) {
    773         return true;
    774     }
    775     if (index < fNonpurgeableResources.count() && fNonpurgeableResources[index] == resource) {
    776         return true;
    777     }
    778     SkDEBUGFAIL("Resource index should be -1 or the resource should be in the cache.");
    779     return false;
    780 }
    781 
    782 #endif
    783