Home | History | Annotate | Download | only in gpu 
      1 
      2 /*
      3  * Copyright 2014 Google Inc.
      4  *
      5  * Use of this source code is governed by a BSD-style license that can be
      6  * found in the LICENSE file.
      7  */
      8 
      9 
     10 #include "GrResourceCache.h"
     11 #include "GrGpuResourceCacheAccess.h"
     12 #include "GrTracing.h"
     13 #include "SkChecksum.h"
     14 #include "SkGr.h"
     15 #include "SkMessageBus.h"
     16 #include "SkTSort.h"
     17 
     18 DECLARE_SKMESSAGEBUS_MESSAGE(GrUniqueKeyInvalidatedMessage);
     19 
     20 //////////////////////////////////////////////////////////////////////////////
     21 
     22 GrScratchKey::ResourceType GrScratchKey::GenerateResourceType() {
     23     static int32_t gType = INHERITED::kInvalidDomain + 1;
     24 
     25     int32_t type = sk_atomic_inc(&gType);
     26     if (type > SK_MaxU16) {
     27         SkFAIL("Too many Resource Types");
     28     }
     29 
     30     return static_cast<ResourceType>(type);
     31 }
     32 
     33 GrUniqueKey::Domain GrUniqueKey::GenerateDomain() {
     34     static int32_t gDomain = INHERITED::kInvalidDomain + 1;
     35 
     36     int32_t domain = sk_atomic_inc(&gDomain);
     37     if (domain > SK_MaxU16) {
     38         SkFAIL("Too many GrUniqueKey Domains");
     39     }
     40 
     41     return static_cast<Domain>(domain);
     42 }
     43 
     44 uint32_t GrResourceKeyHash(const uint32_t* data, size_t size) {
     45     return SkChecksum::Compute(data, size);
     46 }
     47 
     48 //////////////////////////////////////////////////////////////////////////////
     49 
     50 class GrResourceCache::AutoValidate : ::SkNoncopyable {
     51 public:
     52     AutoValidate(GrResourceCache* cache) : fCache(cache) { cache->validate(); }
     53     ~AutoValidate() { fCache->validate(); }
     54 private:
     55     GrResourceCache* fCache;
     56 };
     57 
     58  //////////////////////////////////////////////////////////////////////////////
     59 
     60 
     61 GrResourceCache::GrResourceCache()
     62     : fTimestamp(0)
     63     , fMaxCount(kDefaultMaxCount)
     64     , fMaxBytes(kDefaultMaxSize)
     65     , fMaxUnusedFlushes(kDefaultMaxUnusedFlushes)
     66 #if GR_CACHE_STATS
     67     , fHighWaterCount(0)
     68     , fHighWaterBytes(0)
     69     , fBudgetedHighWaterCount(0)
     70     , fBudgetedHighWaterBytes(0)
     71 #endif
     72     , fBytes(0)
     73     , fBudgetedCount(0)
     74     , fBudgetedBytes(0)
     75     , fOverBudgetCB(NULL)
     76     , fOverBudgetData(NULL)
     77     , fFlushTimestamps(NULL)
     78     , fLastFlushTimestampIndex(0){
     79     SkDEBUGCODE(fCount = 0;)
     80     SkDEBUGCODE(fNewlyPurgeableResourceForValidation = NULL;)
     81     this->resetFlushTimestamps();
     82 }
     83 
     84 GrResourceCache::~GrResourceCache() {
     85     this->releaseAll();
     86     SkDELETE_ARRAY(fFlushTimestamps);
     87 }
     88 
     89 void GrResourceCache::setLimits(int count, size_t bytes, int maxUnusedFlushes) {
     90     fMaxCount = count;
     91     fMaxBytes = bytes;
     92     fMaxUnusedFlushes = maxUnusedFlushes;
     93     this->resetFlushTimestamps();
     94     this->purgeAsNeeded();
     95 }
     96 
     97 void GrResourceCache::resetFlushTimestamps() {
     98     SkDELETE_ARRAY(fFlushTimestamps);
     99 
    100     // We assume this number is a power of two when wrapping indices into the timestamp array.
    101     fMaxUnusedFlushes = SkNextPow2(fMaxUnusedFlushes);
    102 
    103     // Since our implementation is to store the timestamps of the last fMaxUnusedFlushes flush calls
    104     // we just turn the feature off if that array would be large.
    105     static const int kMaxSupportedTimestampHistory = 128;
    106 
    107     if (fMaxUnusedFlushes > kMaxSupportedTimestampHistory) {
    108         fFlushTimestamps = NULL;
    109         return;
    110     }
    111 
    112     fFlushTimestamps = SkNEW_ARRAY(uint32_t, fMaxUnusedFlushes);
    113     fLastFlushTimestampIndex = 0;
    114     // Set all the historical flush timestamps to initially be at the beginning of time (timestamp
    115     // 0).
    116     sk_bzero(fFlushTimestamps, fMaxUnusedFlushes * sizeof(uint32_t));
    117 }
    118 
    119 void GrResourceCache::insertResource(GrGpuResource* resource) {
    120     SkASSERT(resource);
    121     SkASSERT(!this->isInCache(resource));
    122     SkASSERT(!resource->wasDestroyed());
    123     SkASSERT(!resource->isPurgeable());
    124 
    125     // We must set the timestamp before adding to the array in case the timestamp wraps and we wind
    126     // up iterating over all the resources that already have timestamps.
    127     resource->cacheAccess().setTimestamp(this->getNextTimestamp());
    128 
    129     this->addToNonpurgeableArray(resource);
    130 
    131     size_t size = resource->gpuMemorySize();
    132     SkDEBUGCODE(++fCount;)
    133     fBytes += size;
    134 #if GR_CACHE_STATS
    135     fHighWaterCount = SkTMax(this->getResourceCount(), fHighWaterCount);
    136     fHighWaterBytes = SkTMax(fBytes, fHighWaterBytes);
    137 #endif
    138     if (resource->resourcePriv().isBudgeted()) {
    139         ++fBudgetedCount;
    140         fBudgetedBytes += size;
    141         TRACE_COUNTER2(TRACE_DISABLED_BY_DEFAULT("skia.gpu.cache"), "skia budget", "used",
    142                        fBudgetedBytes, "free", fMaxBytes - fBudgetedBytes);
    143 #if GR_CACHE_STATS
    144         fBudgetedHighWaterCount = SkTMax(fBudgetedCount, fBudgetedHighWaterCount);
    145         fBudgetedHighWaterBytes = SkTMax(fBudgetedBytes, fBudgetedHighWaterBytes);
    146 #endif
    147     }
    148     if (resource->resourcePriv().getScratchKey().isValid()) {
    149         SkASSERT(!resource->cacheAccess().isWrapped());
    150         fScratchMap.insert(resource->resourcePriv().getScratchKey(), resource);
    151     }
    152 
    153     this->purgeAsNeeded();
    154 }
    155 
    156 void GrResourceCache::removeResource(GrGpuResource* resource) {
    157     this->validate();
    158     SkASSERT(this->isInCache(resource));
    159 
    160     if (resource->isPurgeable()) {
    161         fPurgeableQueue.remove(resource);
    162     } else {
    163         this->removeFromNonpurgeableArray(resource);
    164     }
    165 
    166     size_t size = resource->gpuMemorySize();
    167     SkDEBUGCODE(--fCount;)
    168     fBytes -= size;
    169     if (resource->resourcePriv().isBudgeted()) {
    170         --fBudgetedCount;
    171         fBudgetedBytes -= size;
    172         TRACE_COUNTER2(TRACE_DISABLED_BY_DEFAULT("skia.gpu.cache"), "skia budget", "used",
    173                        fBudgetedBytes, "free", fMaxBytes - fBudgetedBytes);
    174     }
    175 
    176     if (resource->resourcePriv().getScratchKey().isValid()) {
    177         fScratchMap.remove(resource->resourcePriv().getScratchKey(), resource);
    178     }
    179     if (resource->getUniqueKey().isValid()) {
    180         fUniqueHash.remove(resource->getUniqueKey());
    181     }
    182     this->validate();
    183 }
    184 
    185 void GrResourceCache::abandonAll() {
    186     AutoValidate av(this);
    187 
    188     while (fNonpurgeableResources.count()) {
    189         GrGpuResource* back = *(fNonpurgeableResources.end() - 1);
    190         SkASSERT(!back->wasDestroyed());
    191         back->cacheAccess().abandon();
    192     }
    193 
    194     while (fPurgeableQueue.count()) {
    195         GrGpuResource* top = fPurgeableQueue.peek();
    196         SkASSERT(!top->wasDestroyed());
    197         top->cacheAccess().abandon();
    198     }
    199 
    200     SkASSERT(!fScratchMap.count());
    201     SkASSERT(!fUniqueHash.count());
    202     SkASSERT(!fCount);
    203     SkASSERT(!this->getResourceCount());
    204     SkASSERT(!fBytes);
    205     SkASSERT(!fBudgetedCount);
    206     SkASSERT(!fBudgetedBytes);
    207 }
    208 
    209 void GrResourceCache::releaseAll() {
    210     AutoValidate av(this);
    211 
    212     while(fNonpurgeableResources.count()) {
    213         GrGpuResource* back = *(fNonpurgeableResources.end() - 1);
    214         SkASSERT(!back->wasDestroyed());
    215         back->cacheAccess().release();
    216     }
    217 
    218     while (fPurgeableQueue.count()) {
    219         GrGpuResource* top = fPurgeableQueue.peek();
    220         SkASSERT(!top->wasDestroyed());
    221         top->cacheAccess().release();
    222     }
    223 
    224     SkASSERT(!fScratchMap.count());
    225     SkASSERT(!fUniqueHash.count());
    226     SkASSERT(!fCount);
    227     SkASSERT(!this->getResourceCount());
    228     SkASSERT(!fBytes);
    229     SkASSERT(!fBudgetedCount);
    230     SkASSERT(!fBudgetedBytes);
    231 }
    232 
    233 class GrResourceCache::AvailableForScratchUse {
    234 public:
    235     AvailableForScratchUse(bool rejectPendingIO) : fRejectPendingIO(rejectPendingIO) { }
    236 
    237     bool operator()(const GrGpuResource* resource) const {
    238         if (resource->internalHasRef() || !resource->cacheAccess().isScratch()) {
    239             return false;
    240         }
    241         return !fRejectPendingIO || !resource->internalHasPendingIO();
    242     }
    243 
    244 private:
    245     bool fRejectPendingIO;
    246 };
    247 
    248 GrGpuResource* GrResourceCache::findAndRefScratchResource(const GrScratchKey& scratchKey,
    249                                                           uint32_t flags) {
    250     SkASSERT(scratchKey.isValid());
    251 
    252     GrGpuResource* resource;
    253     if (flags & (kPreferNoPendingIO_ScratchFlag | kRequireNoPendingIO_ScratchFlag)) {
    254         resource = fScratchMap.find(scratchKey, AvailableForScratchUse(true));
    255         if (resource) {
    256             this->refAndMakeResourceMRU(resource);
    257             this->validate();
    258             return resource;
    259         } else if (flags & kRequireNoPendingIO_ScratchFlag) {
    260             return NULL;
    261         }
    262         // TODO: fail here when kPrefer is specified, we didn't find a resource without pending io,
    263         // but there is still space in our budget for the resource.
    264     }
    265     resource = fScratchMap.find(scratchKey, AvailableForScratchUse(false));
    266     if (resource) {
    267         this->refAndMakeResourceMRU(resource);
    268         this->validate();
    269     }
    270     return resource;
    271 }
    272 
    273 void GrResourceCache::willRemoveScratchKey(const GrGpuResource* resource) {
    274     SkASSERT(resource->resourcePriv().getScratchKey().isValid());
    275     fScratchMap.remove(resource->resourcePriv().getScratchKey(), resource);
    276 }
    277 
    278 void GrResourceCache::removeUniqueKey(GrGpuResource* resource) {
    279     // Someone has a ref to this resource in order to have removed the key. When the ref count
    280     // reaches zero we will get a ref cnt notification and figure out what to do with it.
    281     if (resource->getUniqueKey().isValid()) {
    282         SkASSERT(resource == fUniqueHash.find(resource->getUniqueKey()));
    283         fUniqueHash.remove(resource->getUniqueKey());
    284     }
    285     resource->cacheAccess().removeUniqueKey();
    286     this->validate();
    287 }
    288 
    289 void GrResourceCache::changeUniqueKey(GrGpuResource* resource, const GrUniqueKey& newKey) {
    290     SkASSERT(resource);
    291     SkASSERT(this->isInCache(resource));
    292 
    293     // Remove the entry for this resource if it already has a unique key.
    294     if (resource->getUniqueKey().isValid()) {
    295         SkASSERT(resource == fUniqueHash.find(resource->getUniqueKey()));
    296         fUniqueHash.remove(resource->getUniqueKey());
    297         SkASSERT(NULL == fUniqueHash.find(resource->getUniqueKey()));
    298     }
    299 
    300     // If another resource has the new key, remove its key then install the key on this resource.
    301     if (newKey.isValid()) {
    302         if (GrGpuResource* old = fUniqueHash.find(newKey)) {
    303             // If the old resource using the key is purgeable and is unreachable, then remove it.
    304             if (!old->resourcePriv().getScratchKey().isValid() && old->isPurgeable()) {
    305                 // release may call validate() which will assert that resource is in fUniqueHash
    306                 // if it has a valid key. So in debug reset the key here before we assign it.
    307                 SkDEBUGCODE(resource->cacheAccess().removeUniqueKey();)
    308                 old->cacheAccess().release();
    309             } else {
    310                 fUniqueHash.remove(newKey);
    311                 old->cacheAccess().removeUniqueKey();
    312             }
    313         }
    314         SkASSERT(NULL == fUniqueHash.find(newKey));
    315         resource->cacheAccess().setUniqueKey(newKey);
    316         fUniqueHash.add(resource);
    317     } else {
    318         resource->cacheAccess().removeUniqueKey();
    319     }
    320 
    321     this->validate();
    322 }
    323 
    324 void GrResourceCache::refAndMakeResourceMRU(GrGpuResource* resource) {
    325     SkASSERT(resource);
    326     SkASSERT(this->isInCache(resource));
    327 
    328     if (resource->isPurgeable()) {
    329         // It's about to become unpurgeable.
    330         fPurgeableQueue.remove(resource);
    331         this->addToNonpurgeableArray(resource);
    332     }
    333     resource->ref();
    334 
    335     resource->cacheAccess().setTimestamp(this->getNextTimestamp());
    336     this->validate();
    337 }
    338 
    339 void GrResourceCache::notifyCntReachedZero(GrGpuResource* resource, uint32_t flags) {
    340     SkASSERT(resource);
    341     SkASSERT(!resource->wasDestroyed());
    342     SkASSERT(flags);
    343     SkASSERT(this->isInCache(resource));
    344     // This resource should always be in the nonpurgeable array when this function is called. It
    345     // will be moved to the queue if it is newly purgeable.
    346     SkASSERT(fNonpurgeableResources[*resource->cacheAccess().accessCacheIndex()] == resource);
    347 
    348     if (SkToBool(ResourceAccess::kRefCntReachedZero_RefNotificationFlag & flags)) {
    349 #ifdef SK_DEBUG
    350         // When the timestamp overflows validate() is called. validate() checks that resources in
    351         // the nonpurgeable array are indeed not purgeable. However, the movement from the array to
    352         // the purgeable queue happens just below in this function. So we mark it as an exception.
    353         if (resource->isPurgeable()) {
    354             fNewlyPurgeableResourceForValidation = resource;
    355         }
    356 #endif
    357         resource->cacheAccess().setTimestamp(this->getNextTimestamp());
    358         SkDEBUGCODE(fNewlyPurgeableResourceForValidation = NULL);
    359     }
    360 
    361     if (!SkToBool(ResourceAccess::kAllCntsReachedZero_RefNotificationFlag & flags)) {
    362         SkASSERT(!resource->isPurgeable());
    363         return;
    364     }
    365 
    366     SkASSERT(resource->isPurgeable());
    367     this->removeFromNonpurgeableArray(resource);
    368     fPurgeableQueue.insert(resource);
    369 
    370     if (!resource->resourcePriv().isBudgeted()) {
    371         // Check whether this resource could still be used as a scratch resource.
    372         if (!resource->cacheAccess().isWrapped() &&
    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 (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 (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 (fFlushTimestamps) {
    454         // Assuming kNumFlushesToDeleteUnusedResource is a power of 2.
    455         SkASSERT(SkIsPow2(fMaxUnusedFlushes));
    456         int oldestFlushIndex = (fLastFlushTimestampIndex + 1) & (fMaxUnusedFlushes - 1);
    457 
    458         uint32_t oldestAllowedTimestamp = fFlushTimestamps[oldestFlushIndex];
    459         while (fPurgeableQueue.count()) {
    460             uint32_t oldestResourceTimestamp = fPurgeableQueue.peek()->cacheAccess().timestamp();
    461             if (oldestAllowedTimestamp < oldestResourceTimestamp) {
    462                 break;
    463             }
    464             GrGpuResource* resource = fPurgeableQueue.peek();
    465             SkASSERT(resource->isPurgeable());
    466             resource->cacheAccess().release();
    467         }
    468     }
    469 
    470     bool stillOverbudget = this->overBudget();
    471     while (stillOverbudget && fPurgeableQueue.count()) {
    472         GrGpuResource* resource = fPurgeableQueue.peek();
    473         SkASSERT(resource->isPurgeable());
    474         resource->cacheAccess().release();
    475         stillOverbudget = this->overBudget();
    476     }
    477 
    478     this->validate();
    479 
    480     if (stillOverbudget) {
    481         // Despite the purge we're still over budget. Call our over budget callback. If this frees
    482         // any resources then we'll get notified and take appropriate action.
    483         (*fOverBudgetCB)(fOverBudgetData);
    484         this->validate();
    485     }
    486 }
    487 
    488 void GrResourceCache::purgeAllUnlocked() {
    489     // We could disable maintaining the heap property here, but it would add a lot of complexity.
    490     // Moreover, this is rarely called.
    491     while (fPurgeableQueue.count()) {
    492         GrGpuResource* resource = fPurgeableQueue.peek();
    493         SkASSERT(resource->isPurgeable());
    494         resource->cacheAccess().release();
    495     }
    496 
    497     this->validate();
    498 }
    499 
    500 void GrResourceCache::processInvalidUniqueKeys(
    501     const SkTArray<GrUniqueKeyInvalidatedMessage>& msgs) {
    502     for (int i = 0; i < msgs.count(); ++i) {
    503         GrGpuResource* resource = this->findAndRefUniqueResource(msgs[i].key());
    504         if (resource) {
    505             resource->resourcePriv().removeUniqueKey();
    506             resource->unref(); // If this resource is now purgeable, the cache will be notified.
    507         }
    508     }
    509 }
    510 
    511 void GrResourceCache::addToNonpurgeableArray(GrGpuResource* resource) {
    512     int index = fNonpurgeableResources.count();
    513     *fNonpurgeableResources.append() = resource;
    514     *resource->cacheAccess().accessCacheIndex() = index;
    515 }
    516 
    517 void GrResourceCache::removeFromNonpurgeableArray(GrGpuResource* resource) {
    518     int* index = resource->cacheAccess().accessCacheIndex();
    519     // Fill the whole we will create in the array with the tail object, adjust its index, and
    520     // then pop the array
    521     GrGpuResource* tail = *(fNonpurgeableResources.end() - 1);
    522     SkASSERT(fNonpurgeableResources[*index] == resource);
    523     fNonpurgeableResources[*index] = tail;
    524     *tail->cacheAccess().accessCacheIndex() = *index;
    525     fNonpurgeableResources.pop();
    526     SkDEBUGCODE(*index = -1);
    527 }
    528 
    529 uint32_t GrResourceCache::getNextTimestamp() {
    530     // If we wrap then all the existing resources will appear older than any resources that get
    531     // a timestamp after the wrap.
    532     if (0 == fTimestamp) {
    533         int count = this->getResourceCount();
    534         if (count) {
    535             // Reset all the timestamps. We sort the resources by timestamp and then assign
    536             // sequential timestamps beginning with 0. This is O(n*lg(n)) but it should be extremely
    537             // rare.
    538             SkTDArray<GrGpuResource*> sortedPurgeableResources;
    539             sortedPurgeableResources.setReserve(fPurgeableQueue.count());
    540 
    541             while (fPurgeableQueue.count()) {
    542                 *sortedPurgeableResources.append() = fPurgeableQueue.peek();
    543                 fPurgeableQueue.pop();
    544             }
    545 
    546             struct Less {
    547                 bool operator()(GrGpuResource* a, GrGpuResource* b) {
    548                     return CompareTimestamp(a,b);
    549                 }
    550             };
    551             Less less;
    552             SkTQSort(fNonpurgeableResources.begin(), fNonpurgeableResources.end() - 1, less);
    553 
    554             // Pick resources out of the purgeable and non-purgeable arrays based on lowest
    555             // timestamp and assign new timestamps.
    556             int currP = 0;
    557             int currNP = 0;
    558             while (currP < sortedPurgeableResources.count() &&
    559                    currNP < fNonpurgeableResources.count()) {
    560                 uint32_t tsP = sortedPurgeableResources[currP]->cacheAccess().timestamp();
    561                 uint32_t tsNP = fNonpurgeableResources[currNP]->cacheAccess().timestamp();
    562                 SkASSERT(tsP != tsNP);
    563                 if (tsP < tsNP) {
    564                     sortedPurgeableResources[currP++]->cacheAccess().setTimestamp(fTimestamp++);
    565                 } else {
    566                     // Correct the index in the nonpurgeable array stored on the resource post-sort.
    567                     *fNonpurgeableResources[currNP]->cacheAccess().accessCacheIndex() = currNP;
    568                     fNonpurgeableResources[currNP++]->cacheAccess().setTimestamp(fTimestamp++);
    569                 }
    570             }
    571 
    572             // The above loop ended when we hit the end of one array. Finish the other one.
    573             while (currP < sortedPurgeableResources.count()) {
    574                 sortedPurgeableResources[currP++]->cacheAccess().setTimestamp(fTimestamp++);
    575             }
    576             while (currNP < fNonpurgeableResources.count()) {
    577                 *fNonpurgeableResources[currNP]->cacheAccess().accessCacheIndex() = currNP;
    578                 fNonpurgeableResources[currNP++]->cacheAccess().setTimestamp(fTimestamp++);
    579             }
    580 
    581             // Rebuild the queue.
    582             for (int i = 0; i < sortedPurgeableResources.count(); ++i) {
    583                 fPurgeableQueue.insert(sortedPurgeableResources[i]);
    584             }
    585 
    586             this->validate();
    587             SkASSERT(count == this->getResourceCount());
    588 
    589             // count should be the next timestamp we return.
    590             SkASSERT(fTimestamp == SkToU32(count));
    591 
    592             // The historical timestamps of flushes are now invalid.
    593             this->resetFlushTimestamps();
    594         }
    595     }
    596     return fTimestamp++;
    597 }
    598 
    599 void GrResourceCache::notifyFlushOccurred() {
    600     if (fFlushTimestamps) {
    601         SkASSERT(SkIsPow2(fMaxUnusedFlushes));
    602         fLastFlushTimestampIndex = (fLastFlushTimestampIndex + 1) & (fMaxUnusedFlushes - 1);
    603         // get the timestamp before accessing fFlushTimestamps because getNextTimestamp will
    604         // reallocate fFlushTimestamps on timestamp overflow.
    605         uint32_t timestamp = this->getNextTimestamp();
    606         fFlushTimestamps[fLastFlushTimestampIndex] = timestamp;
    607         this->purgeAsNeeded();
    608     }
    609 }
    610 
    611 #ifdef SK_DEBUG
    612 void GrResourceCache::validate() const {
    613     // Reduce the frequency of validations for large resource counts.
    614     static SkRandom gRandom;
    615     int mask = (SkNextPow2(fCount + 1) >> 5) - 1;
    616     if (~mask && (gRandom.nextU() & mask)) {
    617         return;
    618     }
    619 
    620     struct Stats {
    621         size_t fBytes;
    622         int fBudgetedCount;
    623         size_t fBudgetedBytes;
    624         int fLocked;
    625         int fScratch;
    626         int fCouldBeScratch;
    627         int fContent;
    628         const ScratchMap* fScratchMap;
    629         const UniqueHash* fUniqueHash;
    630 
    631         Stats(const GrResourceCache* cache) {
    632             memset(this, 0, sizeof(*this));
    633             fScratchMap = &cache->fScratchMap;
    634             fUniqueHash = &cache->fUniqueHash;
    635         }
    636 
    637         void update(GrGpuResource* resource) {
    638             fBytes += resource->gpuMemorySize();
    639 
    640             if (!resource->isPurgeable()) {
    641                 ++fLocked;
    642             }
    643 
    644             if (resource->cacheAccess().isScratch()) {
    645                 SkASSERT(!resource->getUniqueKey().isValid());
    646                 ++fScratch;
    647                 SkASSERT(fScratchMap->countForKey(resource->resourcePriv().getScratchKey()));
    648                 SkASSERT(!resource->cacheAccess().isWrapped());
    649             } else if (resource->resourcePriv().getScratchKey().isValid()) {
    650                 SkASSERT(!resource->resourcePriv().isBudgeted() ||
    651                          resource->getUniqueKey().isValid());
    652                 ++fCouldBeScratch;
    653                 SkASSERT(fScratchMap->countForKey(resource->resourcePriv().getScratchKey()));
    654                 SkASSERT(!resource->cacheAccess().isWrapped());
    655             }
    656             const GrUniqueKey& uniqueKey = resource->getUniqueKey();
    657             if (uniqueKey.isValid()) {
    658                 ++fContent;
    659                 SkASSERT(fUniqueHash->find(uniqueKey) == resource);
    660                 SkASSERT(!resource->cacheAccess().isWrapped());
    661                 SkASSERT(resource->resourcePriv().isBudgeted());
    662             }
    663 
    664             if (resource->resourcePriv().isBudgeted()) {
    665                 ++fBudgetedCount;
    666                 fBudgetedBytes += resource->gpuMemorySize();
    667             }
    668         }
    669     };
    670 
    671     Stats stats(this);
    672 
    673     for (int i = 0; i < fNonpurgeableResources.count(); ++i) {
    674         SkASSERT(!fNonpurgeableResources[i]->isPurgeable() ||
    675                  fNewlyPurgeableResourceForValidation == fNonpurgeableResources[i]);
    676         SkASSERT(*fNonpurgeableResources[i]->cacheAccess().accessCacheIndex() == i);
    677         SkASSERT(!fNonpurgeableResources[i]->wasDestroyed());
    678         stats.update(fNonpurgeableResources[i]);
    679     }
    680     for (int i = 0; i < fPurgeableQueue.count(); ++i) {
    681         SkASSERT(fPurgeableQueue.at(i)->isPurgeable());
    682         SkASSERT(*fPurgeableQueue.at(i)->cacheAccess().accessCacheIndex() == i);
    683         SkASSERT(!fPurgeableQueue.at(i)->wasDestroyed());
    684         stats.update(fPurgeableQueue.at(i));
    685     }
    686 
    687     SkASSERT(fCount == this->getResourceCount());
    688     SkASSERT(fBudgetedCount <= fCount);
    689     SkASSERT(fBudgetedBytes <= fBytes);
    690     SkASSERT(stats.fBytes == fBytes);
    691     SkASSERT(stats.fBudgetedBytes == fBudgetedBytes);
    692     SkASSERT(stats.fBudgetedCount == fBudgetedCount);
    693 #if GR_CACHE_STATS
    694     SkASSERT(fBudgetedHighWaterCount <= fHighWaterCount);
    695     SkASSERT(fBudgetedHighWaterBytes <= fHighWaterBytes);
    696     SkASSERT(fBytes <= fHighWaterBytes);
    697     SkASSERT(fCount <= fHighWaterCount);
    698     SkASSERT(fBudgetedBytes <= fBudgetedHighWaterBytes);
    699     SkASSERT(fBudgetedCount <= fBudgetedHighWaterCount);
    700 #endif
    701     SkASSERT(stats.fContent == fUniqueHash.count());
    702     SkASSERT(stats.fScratch + stats.fCouldBeScratch == fScratchMap.count());
    703 
    704     // This assertion is not currently valid because we can be in recursive notifyCntReachedZero()
    705     // calls. This will be fixed when subresource registration is explicit.
    706     // bool overBudget = budgetedBytes > fMaxBytes || budgetedCount > fMaxCount;
    707     // SkASSERT(!overBudget || locked == count || fPurging);
    708 }
    709 
    710 bool GrResourceCache::isInCache(const GrGpuResource* resource) const {
    711     int index = *resource->cacheAccess().accessCacheIndex();
    712     if (index < 0) {
    713         return false;
    714     }
    715     if (index < fPurgeableQueue.count() && fPurgeableQueue.at(index) == resource) {
    716         return true;
    717     }
    718     if (index < fNonpurgeableResources.count() && fNonpurgeableResources[index] == resource) {
    719         return true;
    720     }
    721     SkDEBUGFAIL("Resource index should be -1 or the resource should be in the cache.");
    722     return false;
    723 }
    724 
    725 #endif
    726