Handle the case when the GrResourceCache timestamp wraps.

src/gpu/GrResourceCache.cpp

 
 /*
  * Copyright 2014 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 
 #include "GrResourceCache.h"
 #include "GrGpuResourceCacheAccess.h"
 #include "SkChecksum.h"
 #include "SkGr.h"
 #include "SkMessageBus.h"
+#include "SkTSort.h"
 
 DECLARE_SKMESSAGEBUS_MESSAGE(GrUniqueKeyInvalidatedMessage);
 
 //////////////////////////////////////////////////////////////////////////////
 
 GrScratchKey::ResourceType GrScratchKey::GenerateResourceType() {
     static int32_t gType = INHERITED::kInvalidDomain + 1;
 
     int32_t type = sk_atomic_inc(&gType);
     if (type > SK_MaxU16) {
@@ skipping 58 matching lines @@
     fMaxCount = count;
     fMaxBytes = bytes;
     this->purgeAsNeeded();
 }
 
 void GrResourceCache::insertResource(GrGpuResource* resource) {
     SkASSERT(resource);
     SkASSERT(!this->isInCache(resource));
     SkASSERT(!resource->wasDestroyed());
     SkASSERT(!resource->isPurgeable());
+
+    // We must set the timestamp before adding to the array in case the timestamp wraps and we wind
+    // up iterating over all the resources that already have timestamps.
+    resource->cacheAccess().setTimestamp(this->getNextTimestamp());
+
     this->addToNonpurgeableArray(resource);
 
     size_t size = resource->gpuMemorySize();
     SkDEBUGCODE(++fCount;)
     fBytes += size;
 #if GR_CACHE_STATS
     fHighWaterCount = SkTMax(this->getResourceCount(), fHighWaterCount);
     fHighWaterBytes = SkTMax(fBytes, fHighWaterBytes);
 #endif
     if (resource->resourcePriv().isBudgeted()) {
         ++fBudgetedCount;
         fBudgetedBytes += size;
 #if GR_CACHE_STATS
         fBudgetedHighWaterCount = SkTMax(fBudgetedCount, fBudgetedHighWaterCount);
         fBudgetedHighWaterBytes = SkTMax(fBudgetedBytes, fBudgetedHighWaterBytes);
 #endif
     }
     if (resource->resourcePriv().getScratchKey().isValid()) {
         SkASSERT(!resource->cacheAccess().isWrapped());
         fScratchMap.insert(resource->resourcePriv().getScratchKey(), resource);
     }
 
-    resource->cacheAccess().setTimestamp(fTimestamp++);
-
     this->purgeAsNeeded();
 }
 
 void GrResourceCache::removeResource(GrGpuResource* resource) {
     this->validate();
     SkASSERT(this->isInCache(resource));
 
     if (resource->isPurgeable()) {
         fPurgeableQueue.remove(resource);
     } else {
@@ skipping 152 matching lines @@
     } else {
         resource->cacheAccess().removeUniqueKey();
     }
 
     this->validate();
 }
 
 void GrResourceCache::refAndMakeResourceMRU(GrGpuResource* resource) {
     SkASSERT(resource);
     SkASSERT(this->isInCache(resource));
+
     if (resource->isPurgeable()) {
         // It's about to become unpurgeable.
         fPurgeableQueue.remove(resource);
         this->addToNonpurgeableArray(resource);
     }
     resource->ref();
-    resource->cacheAccess().setTimestamp(fTimestamp++);
+
+    resource->cacheAccess().setTimestamp(this->getNextTimestamp());
     this->validate();
 }
 
 void GrResourceCache::notifyPurgeable(GrGpuResource* resource) {
     SkASSERT(resource);
     SkASSERT(this->isInCache(resource));
     SkASSERT(resource->isPurgeable());
 
     this->removeFromNonpurgeableArray(resource);
     fPurgeableQueue.insert(resource);
@@ skipping 128 matching lines @@
     // Fill the whole we will create in the array with the tail object, adjust its index, and
     // then pop the array
     GrGpuResource* tail = *(fNonpurgeableResources.end() - 1);
     SkASSERT(fNonpurgeableResources[*index] == resource);
     fNonpurgeableResources[*index] = tail;
     *tail->cacheAccess().accessCacheIndex() = *index;
     fNonpurgeableResources.pop();
     SkDEBUGCODE(*index = -1);
 }
 
+uint32_t GrResourceCache::getNextTimestamp() {
+    // If we wrap then all the existing resources will appear older than any resources that get
+    // a timestamp after the wrap.
+    if (0 == fTimestamp) {
+        int count = this->getResourceCount();
+        if (count) {
+            // Reset all the timestamps. We sort the resources by timestamp and then assign
+            // sequential timestamps beginning with 0. This is O(n*lg(n)) but it should be extremely
+            // rare.
+            SkTDArray<GrGpuResource*> sortedPurgeableResources;
+            sortedPurgeableResources.setReserve(fPurgeableQueue.count());
+
+            while (fPurgeableQueue.count()) {
+                *sortedPurgeableResources.append() = fPurgeableQueue.peek();
+                fPurgeableQueue.pop();
+            }
+
+            struct Less {
+                bool operator()(GrGpuResource* a, GrGpuResource* b) {
+                    return CompareTimestamp(a,b);
+                }
+            };
+            Less less;
+            SkTQSort(fNonpurgeableResources.begin(), fNonpurgeableResources.end() - 1, less);
+
+            // Pick resources out of the purgeable and non-purgeable arrays based on lowest
+            // timestamp and assign new timestamps.
+            int currP = 0;
+            int currNP = 0;
+            while (currP < sortedPurgeableResources.count() &&
+                   currNP < fNonpurgeableResources.count()) {                
+                uint32_t tsP = sortedPurgeableResources[currP]->cacheAccess().timestamp();
+                uint32_t tsNP = fNonpurgeableResources[currNP]->cacheAccess().timestamp();
+                SkASSERT(tsP != tsNP);
+                if (tsP < tsNP) {
+                    sortedPurgeableResources[currP++]->cacheAccess().setTimestamp(fTimestamp++);
+                } else {
+                    // Correct the index in the nonpurgeable array stored on the resource post-sort.
+                    *fNonpurgeableResources[currNP]->cacheAccess().accessCacheIndex() = currNP;
+                    fNonpurgeableResources[currNP++]->cacheAccess().setTimestamp(fTimestamp++);
+                }
+            }
+
+            // The above loop ended when we hit the end of one array. Finish the other one.
+            while (currP < sortedPurgeableResources.count()) {
+                sortedPurgeableResources[currP++]->cacheAccess().setTimestamp(fTimestamp++);
+            }
+            while (currNP < fNonpurgeableResources.count()) {
+                *fNonpurgeableResources[currNP]->cacheAccess().accessCacheIndex() = currNP;
+                fNonpurgeableResources[currNP++]->cacheAccess().setTimestamp(fTimestamp++);
+            }
+
+            // Rebuild the queue.
+            for (int i = 0; i < sortedPurgeableResources.count(); ++i) {
+                fPurgeableQueue.insert(sortedPurgeableResources[i]);
+            }
+
+            this->validate();
+            SkASSERT(count == this->getResourceCount());
+
+            // count should be the next timestamp we return.
+            SkASSERT(fTimestamp == SkToU32(count));
+        }        
+    }
+    return fTimestamp++;
+}
+
 #ifdef SK_DEBUG
 void GrResourceCache::validate() const {
     // Reduce the frequency of validations for large resource counts.
     static SkRandom gRandom;
     int mask = (SkNextPow2(fCount + 1) >> 5) - 1;
     if (~mask && (gRandom.nextU() & mask)) {
         return;
     }
 
     struct Stats {
@@ skipping 94 matching lines @@
         return true;
     }
     if (index < fNonpurgeableResources.count() && fNonpurgeableResources[index] == resource) {
         return true;
     }
     SkDEBUGFAIL("Resource index should be -1 or the resource should be in the cache.");
     return false;
 }
 
 #endif