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
18DECLARE_SKMESSAGEBUS_MESSAGE(GrUniqueKeyInvalidatedMessage);
19
20//////////////////////////////////////////////////////////////////////////////
21
22GrScratchKey::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
33GrUniqueKey::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
44uint32_t GrResourceKeyHash(const uint32_t* data, size_t size) {
45    return SkChecksum::Compute(data, size);
46}
47
48//////////////////////////////////////////////////////////////////////////////
49
50class GrResourceCache::AutoValidate : ::SkNoncopyable {
51public:
52    AutoValidate(GrResourceCache* cache) : fCache(cache) { cache->validate(); }
53    ~AutoValidate() { fCache->validate(); }
54private:
55    GrResourceCache* fCache;
56};
57
58 //////////////////////////////////////////////////////////////////////////////
59
60
61GrResourceCache::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
84GrResourceCache::~GrResourceCache() {
85    this->releaseAll();
86    SkDELETE_ARRAY(fFlushTimestamps);
87}
88
89void 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
97void 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
119void 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
156void 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
185void 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
209void 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
233class GrResourceCache::AvailableForScratchUse {
234public:
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
244private:
245    bool fRejectPendingIO;
246};
247
248GrGpuResource* 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
273void GrResourceCache::willRemoveScratchKey(const GrGpuResource* resource) {
274    SkASSERT(resource->resourcePriv().getScratchKey().isValid());
275    fScratchMap.remove(resource->resourcePriv().getScratchKey(), resource);
276}
277
278void 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
289void 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
324void 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
339void 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
398void 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
422void 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
446void 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
488void 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
500void 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
511void GrResourceCache::addToNonpurgeableArray(GrGpuResource* resource) {
512    int index = fNonpurgeableResources.count();
513    *fNonpurgeableResources.append() = resource;
514    *resource->cacheAccess().accessCacheIndex() = index;
515}
516
517void 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
529uint32_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
599void 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
612void 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
710bool 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