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::Murmur3(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(const GrCaps* caps)
     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(nullptr)
     76     , fOverBudgetData(nullptr)
     77     , fFlushTimestamps(nullptr)
     78     , fLastFlushTimestampIndex(0)
     79     , fPreferVRAMUseOverFlushes(caps->preferVRAMUseOverFlushes()) {
     80     SkDEBUGCODE(fCount = 0;)
     81     SkDEBUGCODE(fNewlyPurgeableResourceForValidation = nullptr;)
     82     this->resetFlushTimestamps();
     83 }
     84 
     85 GrResourceCache::~GrResourceCache() {
     86     this->releaseAll();
     87     delete[] fFlushTimestamps;
     88 }
     89 
     90 void GrResourceCache::setLimits(int count, size_t bytes, int maxUnusedFlushes) {
     91     fMaxCount = count;
     92     fMaxBytes = bytes;
     93     fMaxUnusedFlushes = maxUnusedFlushes;
     94     this->resetFlushTimestamps();
     95     this->purgeAsNeeded();
     96 }
     97 
     98 void GrResourceCache::resetFlushTimestamps() {
     99     delete[] fFlushTimestamps;
    100 
    101     // We assume this number is a power of two when wrapping indices into the timestamp array.
    102     fMaxUnusedFlushes = SkNextPow2(fMaxUnusedFlushes);
    103 
    104     // Since our implementation is to store the timestamps of the last fMaxUnusedFlushes flush calls
    105     // we just turn the feature off if that array would be large.
    106     static const int kMaxSupportedTimestampHistory = 128;
    107 
    108     if (fMaxUnusedFlushes > kMaxSupportedTimestampHistory) {
    109         fFlushTimestamps = nullptr;
    110         return;
    111     }
    112 
    113     fFlushTimestamps = new uint32_t[fMaxUnusedFlushes];
    114     fLastFlushTimestampIndex = 0;
    115     // Set all the historical flush timestamps to initially be at the beginning of time (timestamp
    116     // 0).
    117     sk_bzero(fFlushTimestamps, fMaxUnusedFlushes * sizeof(uint32_t));
    118 }
    119 
    120 void GrResourceCache::insertResource(GrGpuResource* resource) {
    121     SkASSERT(resource);
    122     SkASSERT(!this->isInCache(resource));
    123     SkASSERT(!resource->wasDestroyed());
    124     SkASSERT(!resource->isPurgeable());
    125 
    126     // We must set the timestamp before adding to the array in case the timestamp wraps and we wind
    127     // up iterating over all the resources that already have timestamps.
    128     resource->cacheAccess().setTimestamp(this->getNextTimestamp());
    129 
    130     this->addToNonpurgeableArray(resource);
    131 
    132     size_t size = resource->gpuMemorySize();
    133     SkDEBUGCODE(++fCount;)
    134     fBytes += size;
    135 #if GR_CACHE_STATS
    136     fHighWaterCount = SkTMax(this->getResourceCount(), fHighWaterCount);
    137     fHighWaterBytes = SkTMax(fBytes, fHighWaterBytes);
    138 #endif
    139     if (SkBudgeted::kYes == resource->resourcePriv().isBudgeted()) {
    140         ++fBudgetedCount;
    141         fBudgetedBytes += size;
    142         TRACE_COUNTER2(TRACE_DISABLED_BY_DEFAULT("skia.gpu.cache"), "skia budget", "used",
    143                        fBudgetedBytes, "free", fMaxBytes - fBudgetedBytes);
    144 #if GR_CACHE_STATS
    145         fBudgetedHighWaterCount = SkTMax(fBudgetedCount, fBudgetedHighWaterCount);
    146         fBudgetedHighWaterBytes = SkTMax(fBudgetedBytes, fBudgetedHighWaterBytes);
    147 #endif
    148     }
    149     if (resource->resourcePriv().getScratchKey().isValid()) {
    150         SkASSERT(!resource->cacheAccess().isExternal());
    151         fScratchMap.insert(resource->resourcePriv().getScratchKey(), resource);
    152     }
    153 
    154     this->purgeAsNeeded();
    155 }
    156 
    157 void GrResourceCache::removeResource(GrGpuResource* resource) {
    158     this->validate();
    159     SkASSERT(this->isInCache(resource));
    160 
    161     if (resource->isPurgeable()) {
    162         fPurgeableQueue.remove(resource);
    163     } else {
    164         this->removeFromNonpurgeableArray(resource);
    165     }
    166 
    167     size_t size = resource->gpuMemorySize();
    168     SkDEBUGCODE(--fCount;)
    169     fBytes -= size;
    170     if (SkBudgeted::kYes == resource->resourcePriv().isBudgeted()) {
    171         --fBudgetedCount;
    172         fBudgetedBytes -= size;
    173         TRACE_COUNTER2(TRACE_DISABLED_BY_DEFAULT("skia.gpu.cache"), "skia budget", "used",
    174                        fBudgetedBytes, "free", fMaxBytes - fBudgetedBytes);
    175     }
    176 
    177     if (resource->resourcePriv().getScratchKey().isValid()) {
    178         fScratchMap.remove(resource->resourcePriv().getScratchKey(), resource);
    179     }
    180     if (resource->getUniqueKey().isValid()) {
    181         fUniqueHash.remove(resource->getUniqueKey());
    182     }
    183     this->validate();
    184 }
    185 
    186 void GrResourceCache::abandonAll() {
    187     AutoValidate av(this);
    188 
    189     while (fNonpurgeableResources.count()) {
    190         GrGpuResource* back = *(fNonpurgeableResources.end() - 1);
    191         SkASSERT(!back->wasDestroyed());
    192         back->cacheAccess().abandon();
    193     }
    194 
    195     while (fPurgeableQueue.count()) {
    196         GrGpuResource* top = fPurgeableQueue.peek();
    197         SkASSERT(!top->wasDestroyed());
    198         top->cacheAccess().abandon();
    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 void GrResourceCache::releaseAll() {
    211     AutoValidate av(this);
    212 
    213     while(fNonpurgeableResources.count()) {
    214         GrGpuResource* back = *(fNonpurgeableResources.end() - 1);
    215         SkASSERT(!back->wasDestroyed());
    216         back->cacheAccess().release();
    217     }
    218 
    219     while (fPurgeableQueue.count()) {
    220         GrGpuResource* top = fPurgeableQueue.peek();
    221         SkASSERT(!top->wasDestroyed());
    222         top->cacheAccess().release();
    223     }
    224 
    225     SkASSERT(!fScratchMap.count());
    226     SkASSERT(!fUniqueHash.count());
    227     SkASSERT(!fCount);
    228     SkASSERT(!this->getResourceCount());
    229     SkASSERT(!fBytes);
    230     SkASSERT(!fBudgetedCount);
    231     SkASSERT(!fBudgetedBytes);
    232 }
    233 
    234 class GrResourceCache::AvailableForScratchUse {
    235 public:
    236     AvailableForScratchUse(bool rejectPendingIO) : fRejectPendingIO(rejectPendingIO) { }
    237 
    238     bool operator()(const GrGpuResource* resource) const {
    239         if (resource->internalHasRef() || !resource->cacheAccess().isScratch()) {
    240             return false;
    241         }
    242         return !fRejectPendingIO || !resource->internalHasPendingIO();
    243     }
    244 
    245 private:
    246     bool fRejectPendingIO;
    247 };
    248 
    249 GrGpuResource* GrResourceCache::findAndRefScratchResource(const GrScratchKey& scratchKey,
    250                                                           size_t resourceSize,
    251                                                           uint32_t flags) {
    252     SkASSERT(scratchKey.isValid());
    253 
    254     GrGpuResource* resource;
    255     if (flags & (kPreferNoPendingIO_ScratchFlag | kRequireNoPendingIO_ScratchFlag)) {
    256         resource = fScratchMap.find(scratchKey, AvailableForScratchUse(true));
    257         if (resource) {
    258             this->refAndMakeResourceMRU(resource);
    259             this->validate();
    260             return resource;
    261         } else if (flags & kRequireNoPendingIO_ScratchFlag) {
    262             return nullptr;
    263         }
    264         // We would prefer to consume more available VRAM rather than flushing
    265         // immediately, but on ANGLE this can lead to starving of the GPU.
    266         if (fPreferVRAMUseOverFlushes && this->wouldFit(resourceSize)) {
    267             // kPrefer is specified, we didn't find a resource without pending io,
    268             // but there is still space in our budget for the resource so force
    269             // the caller to allocate a new resource.
    270             return nullptr;
    271         }
    272     }
    273     resource = fScratchMap.find(scratchKey, AvailableForScratchUse(false));
    274     if (resource) {
    275         this->refAndMakeResourceMRU(resource);
    276         this->validate();
    277     }
    278     return resource;
    279 }
    280 
    281 void GrResourceCache::willRemoveScratchKey(const GrGpuResource* resource) {
    282     SkASSERT(resource->resourcePriv().getScratchKey().isValid());
    283     fScratchMap.remove(resource->resourcePriv().getScratchKey(), resource);
    284 }
    285 
    286 void GrResourceCache::removeUniqueKey(GrGpuResource* resource) {
    287     // Someone has a ref to this resource in order to have removed the key. When the ref count
    288     // reaches zero we will get a ref cnt notification and figure out what to do with it.
    289     if (resource->getUniqueKey().isValid()) {
    290         SkASSERT(resource == fUniqueHash.find(resource->getUniqueKey()));
    291         fUniqueHash.remove(resource->getUniqueKey());
    292     }
    293     resource->cacheAccess().removeUniqueKey();
    294     this->validate();
    295 }
    296 
    297 void GrResourceCache::changeUniqueKey(GrGpuResource* resource, const GrUniqueKey& newKey) {
    298     SkASSERT(resource);
    299     SkASSERT(this->isInCache(resource));
    300 
    301     // Remove the entry for this resource if it already has a unique key.
    302     if (resource->getUniqueKey().isValid()) {
    303         SkASSERT(resource == fUniqueHash.find(resource->getUniqueKey()));
    304         fUniqueHash.remove(resource->getUniqueKey());
    305         SkASSERT(nullptr == fUniqueHash.find(resource->getUniqueKey()));
    306     }
    307 
    308     // If another resource has the new key, remove its key then install the key on this resource.
    309     if (newKey.isValid()) {
    310         if (GrGpuResource* old = fUniqueHash.find(newKey)) {
    311             // If the old resource using the key is purgeable and is unreachable, then remove it.
    312             if (!old->resourcePriv().getScratchKey().isValid() && old->isPurgeable()) {
    313                 // release may call validate() which will assert that resource is in fUniqueHash
    314                 // if it has a valid key. So in debug reset the key here before we assign it.
    315                 SkDEBUGCODE(resource->cacheAccess().removeUniqueKey();)
    316                 old->cacheAccess().release();
    317             } else {
    318                 fUniqueHash.remove(newKey);
    319                 old->cacheAccess().removeUniqueKey();
    320             }
    321         }
    322         SkASSERT(nullptr == fUniqueHash.find(newKey));
    323         resource->cacheAccess().setUniqueKey(newKey);
    324         fUniqueHash.add(resource);
    325     } else {
    326         resource->cacheAccess().removeUniqueKey();
    327     }
    328 
    329     this->validate();
    330 }
    331 
    332 void GrResourceCache::refAndMakeResourceMRU(GrGpuResource* resource) {
    333     SkASSERT(resource);
    334     SkASSERT(this->isInCache(resource));
    335 
    336     if (resource->isPurgeable()) {
    337         // It's about to become unpurgeable.
    338         fPurgeableQueue.remove(resource);
    339         this->addToNonpurgeableArray(resource);
    340     }
    341     resource->ref();
    342 
    343     resource->cacheAccess().setTimestamp(this->getNextTimestamp());
    344     this->validate();
    345 }
    346 
    347 void GrResourceCache::notifyCntReachedZero(GrGpuResource* resource, uint32_t flags) {
    348     SkASSERT(resource);
    349     SkASSERT(!resource->wasDestroyed());
    350     SkASSERT(flags);
    351     SkASSERT(this->isInCache(resource));
    352     // This resource should always be in the nonpurgeable array when this function is called. It
    353     // will be moved to the queue if it is newly purgeable.
    354     SkASSERT(fNonpurgeableResources[*resource->cacheAccess().accessCacheIndex()] == resource);
    355 
    356     if (SkToBool(ResourceAccess::kRefCntReachedZero_RefNotificationFlag & flags)) {
    357 #ifdef SK_DEBUG
    358         // When the timestamp overflows validate() is called. validate() checks that resources in
    359         // the nonpurgeable array are indeed not purgeable. However, the movement from the array to
    360         // the purgeable queue happens just below in this function. So we mark it as an exception.
    361         if (resource->isPurgeable()) {
    362             fNewlyPurgeableResourceForValidation = resource;
    363         }
    364 #endif
    365         resource->cacheAccess().setTimestamp(this->getNextTimestamp());
    366         SkDEBUGCODE(fNewlyPurgeableResourceForValidation = nullptr);
    367     }
    368 
    369     if (!SkToBool(ResourceAccess::kAllCntsReachedZero_RefNotificationFlag & flags)) {
    370         SkASSERT(!resource->isPurgeable());
    371         return;
    372     }
    373 
    374     SkASSERT(resource->isPurgeable());
    375     this->removeFromNonpurgeableArray(resource);
    376     fPurgeableQueue.insert(resource);
    377 
    378     if (SkBudgeted::kNo == resource->resourcePriv().isBudgeted()) {
    379         // Check whether this resource could still be used as a scratch resource.
    380         if (!resource->cacheAccess().isExternal() &&
    381             resource->resourcePriv().getScratchKey().isValid()) {
    382             // We won't purge an existing resource to make room for this one.
    383             if (fBudgetedCount < fMaxCount &&
    384                 fBudgetedBytes + resource->gpuMemorySize() <= fMaxBytes) {
    385                 resource->resourcePriv().makeBudgeted();
    386                 return;
    387             }
    388         }
    389     } else {
    390         // Purge the resource immediately if we're over budget
    391         // Also purge if the resource has neither a valid scratch key nor a unique key.
    392         bool noKey = !resource->resourcePriv().getScratchKey().isValid() &&
    393                      !resource->getUniqueKey().isValid();
    394         if (!this->overBudget() && !noKey) {
    395             return;
    396         }
    397     }
    398 
    399     SkDEBUGCODE(int beforeCount = this->getResourceCount();)
    400     resource->cacheAccess().release();
    401     // We should at least free this resource, perhaps dependent resources as well.
    402     SkASSERT(this->getResourceCount() < beforeCount);
    403     this->validate();
    404 }
    405 
    406 void GrResourceCache::didChangeGpuMemorySize(const GrGpuResource* resource, size_t oldSize) {
    407     // SkASSERT(!fPurging); GrPathRange increases size during flush. :(
    408     SkASSERT(resource);
    409     SkASSERT(this->isInCache(resource));
    410 
    411     ptrdiff_t delta = resource->gpuMemorySize() - oldSize;
    412 
    413     fBytes += delta;
    414 #if GR_CACHE_STATS
    415     fHighWaterBytes = SkTMax(fBytes, fHighWaterBytes);
    416 #endif
    417     if (SkBudgeted::kYes == resource->resourcePriv().isBudgeted()) {
    418         fBudgetedBytes += delta;
    419         TRACE_COUNTER2(TRACE_DISABLED_BY_DEFAULT("skia.gpu.cache"), "skia budget", "used",
    420                        fBudgetedBytes, "free", fMaxBytes - fBudgetedBytes);
    421 #if GR_CACHE_STATS
    422         fBudgetedHighWaterBytes = SkTMax(fBudgetedBytes, fBudgetedHighWaterBytes);
    423 #endif
    424     }
    425 
    426     this->purgeAsNeeded();
    427     this->validate();
    428 }
    429 
    430 void GrResourceCache::didChangeBudgetStatus(GrGpuResource* resource) {
    431     SkASSERT(resource);
    432     SkASSERT(this->isInCache(resource));
    433 
    434     size_t size = resource->gpuMemorySize();
    435 
    436     if (SkBudgeted::kYes == resource->resourcePriv().isBudgeted()) {
    437         ++fBudgetedCount;
    438         fBudgetedBytes += size;
    439 #if GR_CACHE_STATS
    440         fBudgetedHighWaterBytes = SkTMax(fBudgetedBytes, fBudgetedHighWaterBytes);
    441         fBudgetedHighWaterCount = SkTMax(fBudgetedCount, fBudgetedHighWaterCount);
    442 #endif
    443         this->purgeAsNeeded();
    444     } else {
    445         --fBudgetedCount;
    446         fBudgetedBytes -= size;
    447     }
    448     TRACE_COUNTER2(TRACE_DISABLED_BY_DEFAULT("skia.gpu.cache"), "skia budget", "used",
    449                    fBudgetedBytes, "free", fMaxBytes - fBudgetedBytes);
    450 
    451     this->validate();
    452 }
    453 
    454 void GrResourceCache::purgeAsNeeded() {
    455     SkTArray<GrUniqueKeyInvalidatedMessage> invalidKeyMsgs;
    456     fInvalidUniqueKeyInbox.poll(&invalidKeyMsgs);
    457     if (invalidKeyMsgs.count()) {
    458         this->processInvalidUniqueKeys(invalidKeyMsgs);
    459     }
    460 
    461     if (fFlushTimestamps) {
    462         // Assuming kNumFlushesToDeleteUnusedResource is a power of 2.
    463         SkASSERT(SkIsPow2(fMaxUnusedFlushes));
    464         int oldestFlushIndex = (fLastFlushTimestampIndex + 1) & (fMaxUnusedFlushes - 1);
    465 
    466         uint32_t oldestAllowedTimestamp = fFlushTimestamps[oldestFlushIndex];
    467         while (fPurgeableQueue.count()) {
    468             uint32_t oldestResourceTimestamp = fPurgeableQueue.peek()->cacheAccess().timestamp();
    469             if (oldestAllowedTimestamp < oldestResourceTimestamp) {
    470                 break;
    471             }
    472             GrGpuResource* resource = fPurgeableQueue.peek();
    473             SkASSERT(resource->isPurgeable());
    474             resource->cacheAccess().release();
    475         }
    476     }
    477 
    478     bool stillOverbudget = this->overBudget();
    479     while (stillOverbudget && fPurgeableQueue.count()) {
    480         GrGpuResource* resource = fPurgeableQueue.peek();
    481         SkASSERT(resource->isPurgeable());
    482         resource->cacheAccess().release();
    483         stillOverbudget = this->overBudget();
    484     }
    485 
    486     this->validate();
    487 
    488     if (stillOverbudget) {
    489         // Despite the purge we're still over budget. Call our over budget callback. If this frees
    490         // any resources then we'll get notified and take appropriate action.
    491         (*fOverBudgetCB)(fOverBudgetData);
    492         this->validate();
    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::processInvalidUniqueKeys(
    509     const SkTArray<GrUniqueKeyInvalidatedMessage>& msgs) {
    510     for (int i = 0; i < msgs.count(); ++i) {
    511         GrGpuResource* resource = this->findAndRefUniqueResource(msgs[i].key());
    512         if (resource) {
    513             resource->resourcePriv().removeUniqueKey();
    514             resource->unref(); // If this resource is now purgeable, the cache will be notified.
    515         }
    516     }
    517 }
    518 
    519 void GrResourceCache::addToNonpurgeableArray(GrGpuResource* resource) {
    520     int index = fNonpurgeableResources.count();
    521     *fNonpurgeableResources.append() = resource;
    522     *resource->cacheAccess().accessCacheIndex() = index;
    523 }
    524 
    525 void GrResourceCache::removeFromNonpurgeableArray(GrGpuResource* resource) {
    526     int* index = resource->cacheAccess().accessCacheIndex();
    527     // Fill the whole we will create in the array with the tail object, adjust its index, and
    528     // then pop the array
    529     GrGpuResource* tail = *(fNonpurgeableResources.end() - 1);
    530     SkASSERT(fNonpurgeableResources[*index] == resource);
    531     fNonpurgeableResources[*index] = tail;
    532     *tail->cacheAccess().accessCacheIndex() = *index;
    533     fNonpurgeableResources.pop();
    534     SkDEBUGCODE(*index = -1);
    535 }
    536 
    537 uint32_t GrResourceCache::getNextTimestamp() {
    538     // If we wrap then all the existing resources will appear older than any resources that get
    539     // a timestamp after the wrap.
    540     if (0 == fTimestamp) {
    541         int count = this->getResourceCount();
    542         if (count) {
    543             // Reset all the timestamps. We sort the resources by timestamp and then assign
    544             // sequential timestamps beginning with 0. This is O(n*lg(n)) but it should be extremely
    545             // rare.
    546             SkTDArray<GrGpuResource*> sortedPurgeableResources;
    547             sortedPurgeableResources.setReserve(fPurgeableQueue.count());
    548 
    549             while (fPurgeableQueue.count()) {
    550                 *sortedPurgeableResources.append() = fPurgeableQueue.peek();
    551                 fPurgeableQueue.pop();
    552             }
    553 
    554             struct Less {
    555                 bool operator()(GrGpuResource* a, GrGpuResource* b) {
    556                     return CompareTimestamp(a,b);
    557                 }
    558             };
    559             Less less;
    560             SkTQSort(fNonpurgeableResources.begin(), fNonpurgeableResources.end() - 1, less);
    561 
    562             // Pick resources out of the purgeable and non-purgeable arrays based on lowest
    563             // timestamp and assign new timestamps.
    564             int currP = 0;
    565             int currNP = 0;
    566             while (currP < sortedPurgeableResources.count() &&
    567                    currNP < fNonpurgeableResources.count()) {
    568                 uint32_t tsP = sortedPurgeableResources[currP]->cacheAccess().timestamp();
    569                 uint32_t tsNP = fNonpurgeableResources[currNP]->cacheAccess().timestamp();
    570                 SkASSERT(tsP != tsNP);
    571                 if (tsP < tsNP) {
    572                     sortedPurgeableResources[currP++]->cacheAccess().setTimestamp(fTimestamp++);
    573                 } else {
    574                     // Correct the index in the nonpurgeable array stored on the resource post-sort.
    575                     *fNonpurgeableResources[currNP]->cacheAccess().accessCacheIndex() = currNP;
    576                     fNonpurgeableResources[currNP++]->cacheAccess().setTimestamp(fTimestamp++);
    577                 }
    578             }
    579 
    580             // The above loop ended when we hit the end of one array. Finish the other one.
    581             while (currP < sortedPurgeableResources.count()) {
    582                 sortedPurgeableResources[currP++]->cacheAccess().setTimestamp(fTimestamp++);
    583             }
    584             while (currNP < fNonpurgeableResources.count()) {
    585                 *fNonpurgeableResources[currNP]->cacheAccess().accessCacheIndex() = currNP;
    586                 fNonpurgeableResources[currNP++]->cacheAccess().setTimestamp(fTimestamp++);
    587             }
    588 
    589             // Rebuild the queue.
    590             for (int i = 0; i < sortedPurgeableResources.count(); ++i) {
    591                 fPurgeableQueue.insert(sortedPurgeableResources[i]);
    592             }
    593 
    594             this->validate();
    595             SkASSERT(count == this->getResourceCount());
    596 
    597             // count should be the next timestamp we return.
    598             SkASSERT(fTimestamp == SkToU32(count));
    599 
    600             // The historical timestamps of flushes are now invalid.
    601             this->resetFlushTimestamps();
    602         }
    603     }
    604     return fTimestamp++;
    605 }
    606 
    607 void GrResourceCache::notifyFlushOccurred() {
    608     if (fFlushTimestamps) {
    609         SkASSERT(SkIsPow2(fMaxUnusedFlushes));
    610         fLastFlushTimestampIndex = (fLastFlushTimestampIndex + 1) & (fMaxUnusedFlushes - 1);
    611         // get the timestamp before accessing fFlushTimestamps because getNextTimestamp will
    612         // reallocate fFlushTimestamps on timestamp overflow.
    613         uint32_t timestamp = this->getNextTimestamp();
    614         fFlushTimestamps[fLastFlushTimestampIndex] = timestamp;
    615         this->purgeAsNeeded();
    616     }
    617 }
    618 
    619 void GrResourceCache::dumpMemoryStatistics(SkTraceMemoryDump* traceMemoryDump) const {
    620     for (int i = 0; i < fNonpurgeableResources.count(); ++i) {
    621         fNonpurgeableResources[i]->dumpMemoryStatistics(traceMemoryDump);
    622     }
    623     for (int i = 0; i < fPurgeableQueue.count(); ++i) {
    624         fPurgeableQueue.at(i)->dumpMemoryStatistics(traceMemoryDump);
    625     }
    626 }
    627 
    628 #ifdef SK_DEBUG
    629 void GrResourceCache::validate() const {
    630     // Reduce the frequency of validations for large resource counts.
    631     static SkRandom gRandom;
    632     int mask = (SkNextPow2(fCount + 1) >> 5) - 1;
    633     if (~mask && (gRandom.nextU() & mask)) {
    634         return;
    635     }
    636 
    637     struct Stats {
    638         size_t fBytes;
    639         int fBudgetedCount;
    640         size_t fBudgetedBytes;
    641         int fLocked;
    642         int fScratch;
    643         int fCouldBeScratch;
    644         int fContent;
    645         const ScratchMap* fScratchMap;
    646         const UniqueHash* fUniqueHash;
    647 
    648         Stats(const GrResourceCache* cache) {
    649             memset(this, 0, sizeof(*this));
    650             fScratchMap = &cache->fScratchMap;
    651             fUniqueHash = &cache->fUniqueHash;
    652         }
    653 
    654         void update(GrGpuResource* resource) {
    655             fBytes += resource->gpuMemorySize();
    656 
    657             if (!resource->isPurgeable()) {
    658                 ++fLocked;
    659             }
    660 
    661             if (resource->cacheAccess().isScratch()) {
    662                 SkASSERT(!resource->getUniqueKey().isValid());
    663                 ++fScratch;
    664                 SkASSERT(fScratchMap->countForKey(resource->resourcePriv().getScratchKey()));
    665                 SkASSERT(!resource->cacheAccess().isExternal());
    666             } else if (resource->resourcePriv().getScratchKey().isValid()) {
    667                 SkASSERT(SkBudgeted::kNo == resource->resourcePriv().isBudgeted() ||
    668                          resource->getUniqueKey().isValid());
    669                 ++fCouldBeScratch;
    670                 SkASSERT(fScratchMap->countForKey(resource->resourcePriv().getScratchKey()));
    671                 SkASSERT(!resource->cacheAccess().isExternal());
    672             }
    673             const GrUniqueKey& uniqueKey = resource->getUniqueKey();
    674             if (uniqueKey.isValid()) {
    675                 ++fContent;
    676                 SkASSERT(fUniqueHash->find(uniqueKey) == resource);
    677                 SkASSERT(!resource->cacheAccess().isExternal());
    678                 SkASSERT(SkBudgeted::kYes == resource->resourcePriv().isBudgeted());
    679             }
    680 
    681             if (SkBudgeted::kYes == resource->resourcePriv().isBudgeted()) {
    682                 ++fBudgetedCount;
    683                 fBudgetedBytes += resource->gpuMemorySize();
    684             }
    685         }
    686     };
    687 
    688     Stats stats(this);
    689 
    690     for (int i = 0; i < fNonpurgeableResources.count(); ++i) {
    691         SkASSERT(!fNonpurgeableResources[i]->isPurgeable() ||
    692                  fNewlyPurgeableResourceForValidation == fNonpurgeableResources[i]);
    693         SkASSERT(*fNonpurgeableResources[i]->cacheAccess().accessCacheIndex() == i);
    694         SkASSERT(!fNonpurgeableResources[i]->wasDestroyed());
    695         stats.update(fNonpurgeableResources[i]);
    696     }
    697     for (int i = 0; i < fPurgeableQueue.count(); ++i) {
    698         SkASSERT(fPurgeableQueue.at(i)->isPurgeable());
    699         SkASSERT(*fPurgeableQueue.at(i)->cacheAccess().accessCacheIndex() == i);
    700         SkASSERT(!fPurgeableQueue.at(i)->wasDestroyed());
    701         stats.update(fPurgeableQueue.at(i));
    702     }
    703 
    704     SkASSERT(fCount == this->getResourceCount());
    705     SkASSERT(fBudgetedCount <= fCount);
    706     SkASSERT(fBudgetedBytes <= fBytes);
    707     SkASSERT(stats.fBytes == fBytes);
    708     SkASSERT(stats.fBudgetedBytes == fBudgetedBytes);
    709     SkASSERT(stats.fBudgetedCount == fBudgetedCount);
    710 #if GR_CACHE_STATS
    711     SkASSERT(fBudgetedHighWaterCount <= fHighWaterCount);
    712     SkASSERT(fBudgetedHighWaterBytes <= fHighWaterBytes);
    713     SkASSERT(fBytes <= fHighWaterBytes);
    714     SkASSERT(fCount <= fHighWaterCount);
    715     SkASSERT(fBudgetedBytes <= fBudgetedHighWaterBytes);
    716     SkASSERT(fBudgetedCount <= fBudgetedHighWaterCount);
    717 #endif
    718     SkASSERT(stats.fContent == fUniqueHash.count());
    719     SkASSERT(stats.fScratch + stats.fCouldBeScratch == fScratchMap.count());
    720 
    721     // This assertion is not currently valid because we can be in recursive notifyCntReachedZero()
    722     // calls. This will be fixed when subresource registration is explicit.
    723     // bool overBudget = budgetedBytes > fMaxBytes || budgetedCount > fMaxCount;
    724     // SkASSERT(!overBudget || locked == count || fPurging);
    725 }
    726 
    727 bool GrResourceCache::isInCache(const GrGpuResource* resource) const {
    728     int index = *resource->cacheAccess().accessCacheIndex();
    729     if (index < 0) {
    730         return false;
    731     }
    732     if (index < fPurgeableQueue.count() && fPurgeableQueue.at(index) == resource) {
    733         return true;
    734     }
    735     if (index < fNonpurgeableResources.count() && fNonpurgeableResources[index] == resource) {
    736         return true;
    737     }
    738     SkDEBUGFAIL("Resource index should be -1 or the resource should be in the cache.");
    739     return false;
    740 }
    741 
    742 #endif
    743