Make GrResourceCache use a priority queue of purgeable resources.
Review URL: https://codereview.chromium.org/921323002
diff --git a/src/core/SkTDPQueue.h b/src/core/SkTDPQueue.h
index 9efde01..ae9dc25 100644
--- a/src/core/SkTDPQueue.h
+++ b/src/core/SkTDPQueue.h
@@ -92,6 +92,10 @@
this->validate();
}
+#ifdef SK_DEBUG
+ T at(int i) const { return fArray[i]; }
+#endif
+
private:
static int LeftOf(int x) { SkASSERT(x >= 0); return 2 * x + 1; }
static int ParentOf(int x) { SkASSERT(x > 0); return (x - 1) >> 1; }
diff --git a/src/gpu/GrGpuResource.cpp b/src/gpu/GrGpuResource.cpp
index dbf5d8c..d86ec7c 100644
--- a/src/gpu/GrGpuResource.cpp
+++ b/src/gpu/GrGpuResource.cpp
@@ -23,6 +23,7 @@
, fGpuMemorySize(kInvalidGpuMemorySize)
, fLifeCycle(lifeCycle)
, fUniqueID(CreateUniqueID()) {
+ SkDEBUGCODE(fCacheArrayIndex = -1);
}
void GrGpuResource::registerWithCache() {
diff --git a/src/gpu/GrGpuResourceCacheAccess.h b/src/gpu/GrGpuResourceCacheAccess.h
index 922e3b3..52294ce 100644
--- a/src/gpu/GrGpuResourceCacheAccess.h
+++ b/src/gpu/GrGpuResourceCacheAccess.h
@@ -55,6 +55,11 @@
}
}
+ uint32_t timestamp() const { return fResource->fTimestamp; }
+ void setTimestamp(uint32_t ts) { fResource->fTimestamp = ts; }
+
+ int* accessCacheIndex() const { return &fResource->fCacheArrayIndex; }
+
CacheAccess(GrGpuResource* resource) : fResource(resource) {}
CacheAccess(const CacheAccess& that) : fResource(that.fResource) {}
CacheAccess& operator=(const CacheAccess&); // unimpl
diff --git a/src/gpu/GrResourceCache.cpp b/src/gpu/GrResourceCache.cpp
index 5cb1dd2..d87e1a5 100644
--- a/src/gpu/GrResourceCache.cpp
+++ b/src/gpu/GrResourceCache.cpp
@@ -58,7 +58,8 @@
static const size_t kDefaultMaxSize = 96 * (1 << 20);
GrResourceCache::GrResourceCache()
- : fMaxCount(kDefaultMaxCount)
+ : fTimestamp(0)
+ , fMaxCount(kDefaultMaxCount)
, fMaxBytes(kDefaultMaxSize)
#if GR_CACHE_STATS
, fHighWaterCount(0)
@@ -70,8 +71,6 @@
, fBytes(0)
, fBudgetedCount(0)
, fBudgetedBytes(0)
- , fPurging(false)
- , fNewlyPurgeableResourceWhilePurging(false)
, fOverBudgetCB(NULL)
, fOverBudgetData(NULL) {
}
@@ -90,7 +89,6 @@
SkASSERT(resource);
SkASSERT(!resource->wasDestroyed());
SkASSERT(!this->isInCache(resource));
- SkASSERT(!fPurging);
fResources.addToHead(resource);
size_t size = resource->gpuMemorySize();
@@ -112,13 +110,20 @@
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);
+ }
+
size_t size = resource->gpuMemorySize();
--fCount;
fBytes -= size;
@@ -140,7 +145,6 @@
void GrResourceCache::abandonAll() {
AutoValidate av(this);
- SkASSERT(!fPurging);
while (GrGpuResource* head = fResources.head()) {
SkASSERT(!head->wasDestroyed());
head->cacheAccess().abandon();
@@ -158,7 +162,6 @@
void GrResourceCache::releaseAll() {
AutoValidate av(this);
- SkASSERT(!fPurging);
while (GrGpuResource* head = fResources.head()) {
SkASSERT(!head->wasDestroyed());
head->cacheAccess().release();
@@ -188,16 +191,14 @@
};
GrGpuResource* GrResourceCache::findAndRefScratchResource(const GrScratchKey& scratchKey,
- uint32_t flags) {
- SkASSERT(!fPurging);
+ uint32_t flags) {
SkASSERT(scratchKey.isValid());
GrGpuResource* resource;
if (flags & (kPreferNoPendingIO_ScratchFlag | kRequireNoPendingIO_ScratchFlag)) {
resource = fScratchMap.find(scratchKey, AvailableForScratchUse(true));
if (resource) {
- resource->ref();
- this->makeResourceMRU(resource);
+ this->refAndMakeResourceMRU(resource);
this->validate();
return resource;
} else if (flags & kRequireNoPendingIO_ScratchFlag) {
@@ -208,8 +209,7 @@
}
resource = fScratchMap.find(scratchKey, AvailableForScratchUse(false));
if (resource) {
- resource->ref();
- this->makeResourceMRU(resource);
+ this->refAndMakeResourceMRU(resource);
this->validate();
}
return resource;
@@ -228,7 +228,6 @@
}
bool GrResourceCache::didSetContentKey(GrGpuResource* resource) {
- SkASSERT(!fPurging);
SkASSERT(resource);
SkASSERT(this->isInCache(resource));
SkASSERT(resource->getContentKey().isValid());
@@ -243,12 +242,16 @@
return true;
}
-void GrResourceCache::makeResourceMRU(GrGpuResource* resource) {
- SkASSERT(!fPurging);
+void GrResourceCache::refAndMakeResourceMRU(GrGpuResource* resource) {
SkASSERT(resource);
SkASSERT(this->isInCache(resource));
- fResources.remove(resource);
- fResources.addToHead(resource);
+ if (resource->isPurgeable()) {
+ // It's about to become unpurgeable.
+ fPurgeableQueue.remove(resource);
+ }
+ resource->ref();
+ resource->cacheAccess().setTimestamp(fTimestamp++);
+ SkASSERT(!resource->isPurgeable());
}
void GrResourceCache::notifyPurgeable(GrGpuResource* resource) {
@@ -256,49 +259,37 @@
SkASSERT(this->isInCache(resource));
SkASSERT(resource->isPurgeable());
- // We can't purge if in the middle of purging because purge is iterating. Instead record
- // that additional resources became purgeable.
- if (fPurging) {
- fNewlyPurgeableResourceWhilePurging = true;
- return;
- }
+ SkASSERT(-1 == *resource->cacheAccess().accessCacheIndex());
+ fPurgeableQueue.insert(resource);
- bool release = false;
-
- if (resource->cacheAccess().isWrapped()) {
- release = true;
- } else if (!resource->resourcePriv().isBudgeted()) {
+ if (!resource->resourcePriv().isBudgeted()) {
// Check whether this resource could still be used as a scratch resource.
- if (resource->resourcePriv().getScratchKey().isValid()) {
+ if (!resource->cacheAccess().isWrapped() &&
+ resource->resourcePriv().getScratchKey().isValid()) {
// We won't purge an existing resource to make room for this one.
bool underBudget = fBudgetedCount < fMaxCount &&
fBudgetedBytes + resource->gpuMemorySize() <= fMaxBytes;
if (underBudget) {
resource->resourcePriv().makeBudgeted();
- } else {
- release = true;
+ return;
}
- } else {
- release = true;
}
} else {
- // Purge the resource if we're over budget
+ // Purge the resource immediately if we're over budget
bool overBudget = fBudgetedCount > fMaxCount || fBudgetedBytes > fMaxBytes;
// Also purge if the resource has neither a valid scratch key nor a content key.
bool noKey = !resource->resourcePriv().getScratchKey().isValid() &&
- !resource->getContentKey().isValid();
- if (overBudget || noKey) {
- release = true;
+ !resource->getContentKey().isValid();
+ if (!overBudget && !noKey) {
+ return;
}
}
- if (release) {
- SkDEBUGCODE(int beforeCount = fCount;)
- resource->cacheAccess().release();
- // We should at least free this resource, perhaps dependent resources as well.
- SkASSERT(fCount < beforeCount);
- }
+ SkDEBUGCODE(int beforeCount = fCount;)
+ resource->cacheAccess().release();
+ // We should at least free this resource, perhaps dependent resources as well.
+ SkASSERT(fCount < beforeCount);
this->validate();
}
@@ -325,7 +316,6 @@
}
void GrResourceCache::didChangeBudgetStatus(GrGpuResource* resource) {
- SkASSERT(!fPurging);
SkASSERT(resource);
SkASSERT(this->isInCache(resource));
@@ -348,67 +338,38 @@
}
void GrResourceCache::internalPurgeAsNeeded() {
- SkASSERT(!fPurging);
- SkASSERT(!fNewlyPurgeableResourceWhilePurging);
SkASSERT(fBudgetedCount > fMaxCount || fBudgetedBytes > fMaxBytes);
- fPurging = true;
-
- bool overBudget = true;
- do {
- fNewlyPurgeableResourceWhilePurging = false;
- ResourceList::Iter resourceIter;
- GrGpuResource* resource = resourceIter.init(fResources,
- ResourceList::Iter::kTail_IterStart);
-
- while (resource) {
- GrGpuResource* prev = resourceIter.prev();
- if (resource->isPurgeable()) {
- resource->cacheAccess().release();
- }
- resource = prev;
- if (fBudgetedCount <= fMaxCount && fBudgetedBytes <= fMaxBytes) {
- overBudget = false;
- resource = NULL;
- }
+ bool stillOverbudget = true;
+ while (fPurgeableQueue.count()) {
+ GrGpuResource* resource = fPurgeableQueue.peek();
+ SkASSERT(resource->isPurgeable());
+ resource->cacheAccess().release();
+ if (fBudgetedCount <= fMaxCount && fBudgetedBytes <= fMaxBytes) {
+ stillOverbudget = false;
+ break;
}
+ }
- if (!fNewlyPurgeableResourceWhilePurging && overBudget && fOverBudgetCB) {
- // Despite the purge we're still over budget. Call our over budget callback.
- (*fOverBudgetCB)(fOverBudgetData);
- }
- } while (overBudget && fNewlyPurgeableResourceWhilePurging);
-
- fNewlyPurgeableResourceWhilePurging = false;
- fPurging = false;
this->validate();
+
+ if (stillOverbudget) {
+ // Despite the purge we're still over budget. Call our over budget callback. If this frees
+ // any resources then we'll get notifyPurgeable() calls and take appropriate action.
+ (*fOverBudgetCB)(fOverBudgetData);
+ this->validate();
+ }
}
void GrResourceCache::purgeAllUnlocked() {
- SkASSERT(!fPurging);
- SkASSERT(!fNewlyPurgeableResourceWhilePurging);
+ // We could disable maintaining the heap property here, but it would add a lot of complexity.
+ // Moreover, this is rarely called.
+ while (fPurgeableQueue.count()) {
+ GrGpuResource* resource = fPurgeableQueue.peek();
+ SkASSERT(resource->isPurgeable());
+ resource->cacheAccess().release();
+ }
- fPurging = true;
-
- do {
- fNewlyPurgeableResourceWhilePurging = false;
- ResourceList::Iter resourceIter;
- GrGpuResource* resource =
- resourceIter.init(fResources, ResourceList::Iter::kTail_IterStart);
-
- while (resource) {
- GrGpuResource* prev = resourceIter.prev();
- if (resource->isPurgeable()) {
- resource->cacheAccess().release();
- }
- resource = prev;
- }
-
- if (!fNewlyPurgeableResourceWhilePurging && fCount && fOverBudgetCB) {
- (*fOverBudgetCB)(fOverBudgetData);
- }
- } while (fNewlyPurgeableResourceWhilePurging);
- fPurging = false;
this->validate();
}
@@ -475,8 +436,17 @@
++budgetedCount;
budgetedBytes += resource->gpuMemorySize();
}
+
+ if (!resource->isPurgeable()) {
+ SkASSERT(-1 == *resource->cacheAccess().accessCacheIndex());
+ }
}
+ for (int i = 0; i < fPurgeableQueue.count(); ++i) {
+ SkASSERT(fPurgeableQueue.at(i)->isPurgeable());
+ }
+
+ SkASSERT(fCount - locked == fPurgeableQueue.count());
SkASSERT(fBudgetedCount <= fCount);
SkASSERT(fBudgetedBytes <= fBudgetedBytes);
SkASSERT(bytes == fBytes);
diff --git a/src/gpu/GrResourceCache.h b/src/gpu/GrResourceCache.h
index 3e4eded..b5984f2 100644
--- a/src/gpu/GrResourceCache.h
+++ b/src/gpu/GrResourceCache.h
@@ -10,11 +10,13 @@
#define GrResourceCache_DEFINED
#include "GrGpuResource.h"
+#include "GrGpuResourceCacheAccess.h"
#include "GrGpuResourcePriv.h"
#include "GrResourceKey.h"
#include "SkMessageBus.h"
#include "SkRefCnt.h"
#include "SkTArray.h"
+#include "SkTDPQueue.h"
#include "SkTInternalLList.h"
#include "SkTMultiMap.h"
@@ -117,8 +119,7 @@
GrGpuResource* findAndRefContentResource(const GrContentKey& contentKey) {
GrGpuResource* resource = fContentHash.find(contentKey);
if (resource) {
- resource->ref();
- this->makeResourceMRU(resource);
+ this->refAndMakeResourceMRU(resource);
}
return resource;
}
@@ -138,7 +139,7 @@
if (invalidKeyMsgs.count()) {
this->processInvalidContentKeys(invalidKeyMsgs);
}
- if (fPurging || (fBudgetedCount <= fMaxCount && fBudgetedBytes <= fMaxBytes)) {
+ if (fBudgetedCount <= fMaxCount && fBudgetedBytes <= fMaxBytes) {
return;
}
this->internalPurgeAsNeeded();
@@ -179,7 +180,7 @@
void willRemoveScratchKey(const GrGpuResource*);
void willRemoveContentKey(const GrGpuResource*);
void didChangeBudgetStatus(GrGpuResource*);
- void makeResourceMRU(GrGpuResource*);
+ void refAndMakeResourceMRU(GrGpuResource*);
/// @}
void internalPurgeAsNeeded();
@@ -216,9 +217,26 @@
typedef SkTInternalLList<GrGpuResource> ResourceList;
- typedef SkMessageBus<GrContentKeyInvalidatedMessage>::Inbox InvalidContentKeyInbox;
+ static bool CompareTimestamp(GrGpuResource* const& a, GrGpuResource* const& b) {
+ return a->cacheAccess().timestamp() < b->cacheAccess().timestamp();
+ }
+ static int* AccessResourceIndex(GrGpuResource* const& res) {
+ return res->cacheAccess().accessCacheIndex();
+ }
+
+ typedef SkMessageBus<GrContentKeyInvalidatedMessage>::Inbox InvalidContentKeyInbox;
+ typedef SkTDPQueue<GrGpuResource*, CompareTimestamp, AccessResourceIndex> PurgeableQueue;
+
+ // Whenever a resource is added to the cache or the result of a cache lookup, fTimestamp is
+ // assigned as the resource's timestamp and then incremented. fPurgeableQueue orders the
+ // purgeable resources by this value, and thus is used to purge resources in LRU order.
+ uint32_t fTimestamp;
+ PurgeableQueue fPurgeableQueue;
+
+ // TODO: Replace this with an array of nonpurgeable resources
ResourceList fResources;
+
// This map holds all resources that can be used as scratch resources.
ScratchMap fScratchMap;
// This holds all resources that have content keys.
@@ -243,15 +261,10 @@
int fBudgetedCount;
size_t fBudgetedBytes;
- // prevents recursive purging
- bool fPurging;
- bool fNewlyPurgeableResourceWhilePurging;
-
PFOverBudgetCB fOverBudgetCB;
void* fOverBudgetData;
InvalidContentKeyInbox fInvalidContentKeyInbox;
-
};
class GrResourceCache::ResourceAccess {