From 9f2d1571ed1f0ed579e5d7779c46a90e20f30f22 Mon Sep 17 00:00:00 2001 From: bsalomon Date: Tue, 17 Feb 2015 11:47:40 -0800 Subject: Make GrResourceCache use a priority queue of purgeable resources. Review URL: https://codereview.chromium.org/921323002 --- src/core/SkTDPQueue.h | 4 + src/gpu/GrGpuResource.cpp | 1 + src/gpu/GrGpuResourceCacheAccess.h | 5 ++ src/gpu/GrResourceCache.cpp | 164 +++++++++++++++---------------------- src/gpu/GrResourceCache.h | 31 +++++-- 5 files changed, 99 insertions(+), 106 deletions(-) (limited to 'src') diff --git a/src/core/SkTDPQueue.h b/src/core/SkTDPQueue.h index 9efde01b66..ae9dc25227 100644 --- a/src/core/SkTDPQueue.h +++ b/src/core/SkTDPQueue.h @@ -92,6 +92,10 @@ public: 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 dbf5d8c2bb..d86ec7cafd 100644 --- a/src/gpu/GrGpuResource.cpp +++ b/src/gpu/GrGpuResource.cpp @@ -23,6 +23,7 @@ GrGpuResource::GrGpuResource(GrGpu* gpu, LifeCycle lifeCycle) , 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 922e3b36b5..52294cef90 100644 --- a/src/gpu/GrGpuResourceCacheAccess.h +++ b/src/gpu/GrGpuResourceCacheAccess.h @@ -55,6 +55,11 @@ private: } } + 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 5cb1dd2a94..d87e1a5b58 100644 --- a/src/gpu/GrResourceCache.cpp +++ b/src/gpu/GrResourceCache.cpp @@ -58,7 +58,8 @@ static const int kDefaultMaxCount = 2 * (1 << 10); 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 @@ GrResourceCache::GrResourceCache() , fBytes(0) , fBudgetedCount(0) , fBudgetedBytes(0) - , fPurging(false) - , fNewlyPurgeableResourceWhilePurging(false) , fOverBudgetCB(NULL) , fOverBudgetData(NULL) { } @@ -90,7 +89,6 @@ void GrResourceCache::insertResource(GrGpuResource* resource) { SkASSERT(resource); SkASSERT(!resource->wasDestroyed()); SkASSERT(!this->isInCache(resource)); - SkASSERT(!fPurging); fResources.addToHead(resource); size_t size = resource->gpuMemorySize(); @@ -112,13 +110,20 @@ void GrResourceCache::insertResource(GrGpuResource* resource) { 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::removeResource(GrGpuResource* resource) { 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::abandonAll() { void GrResourceCache::releaseAll() { AutoValidate av(this); - SkASSERT(!fPurging); while (GrGpuResource* head = fResources.head()) { SkASSERT(!head->wasDestroyed()); head->cacheAccess().release(); @@ -188,16 +191,14 @@ private: }; 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 @@ GrGpuResource* GrResourceCache::findAndRefScratchResource(const GrScratchKey& sc } resource = fScratchMap.find(scratchKey, AvailableForScratchUse(false)); if (resource) { - resource->ref(); - this->makeResourceMRU(resource); + this->refAndMakeResourceMRU(resource); this->validate(); } return resource; @@ -228,7 +228,6 @@ void GrResourceCache::willRemoveContentKey(const GrGpuResource* resource) { } bool GrResourceCache::didSetContentKey(GrGpuResource* resource) { - SkASSERT(!fPurging); SkASSERT(resource); SkASSERT(this->isInCache(resource)); SkASSERT(resource->getContentKey().isValid()); @@ -243,12 +242,16 @@ bool GrResourceCache::didSetContentKey(GrGpuResource* resource) { 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 @@ void GrResourceCache::notifyPurgeable(GrGpuResource* resource) { 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; - } - - bool release = false; + SkASSERT(-1 == *resource->cacheAccess().accessCacheIndex()); + fPurgeableQueue.insert(resource); - 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::didChangeGpuMemorySize(const GrGpuResource* resource, size } void GrResourceCache::didChangeBudgetStatus(GrGpuResource* resource) { - SkASSERT(!fPurging); SkASSERT(resource); SkASSERT(this->isInCache(resource)); @@ -348,67 +338,38 @@ void GrResourceCache::didChangeBudgetStatus(GrGpuResource* resource) { } 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; - } - } - - if (!fNewlyPurgeableResourceWhilePurging && overBudget && fOverBudgetCB) { - // Despite the purge we're still over budget. Call our over budget callback. - (*fOverBudgetCB)(fOverBudgetData); + bool stillOverbudget = true; + while (fPurgeableQueue.count()) { + GrGpuResource* resource = fPurgeableQueue.peek(); + SkASSERT(resource->isPurgeable()); + resource->cacheAccess().release(); + if (fBudgetedCount <= fMaxCount && fBudgetedBytes <= fMaxBytes) { + stillOverbudget = false; + break; } - } 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); - - 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; - } + // 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(); + } - if (!fNewlyPurgeableResourceWhilePurging && fCount && fOverBudgetCB) { - (*fOverBudgetCB)(fOverBudgetData); - } - } while (fNewlyPurgeableResourceWhilePurging); - fPurging = false; this->validate(); } @@ -475,8 +436,17 @@ void GrResourceCache::validate() const { ++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 3e4ededc9e..b5984f2344 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 @@ public: 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 @@ public: if (invalidKeyMsgs.count()) { this->processInvalidContentKeys(invalidKeyMsgs); } - if (fPurging || (fBudgetedCount <= fMaxCount && fBudgetedBytes <= fMaxBytes)) { + if (fBudgetedCount <= fMaxCount && fBudgetedBytes <= fMaxBytes) { return; } this->internalPurgeAsNeeded(); @@ -179,7 +180,7 @@ private: void willRemoveScratchKey(const GrGpuResource*); void willRemoveContentKey(const GrGpuResource*); void didChangeBudgetStatus(GrGpuResource*); - void makeResourceMRU(GrGpuResource*); + void refAndMakeResourceMRU(GrGpuResource*); /// @} void internalPurgeAsNeeded(); @@ -216,9 +217,26 @@ private: typedef SkTInternalLList ResourceList; + 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::Inbox InvalidContentKeyInbox; + typedef SkTDPQueue 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 @@ private: int fBudgetedCount; size_t fBudgetedBytes; - // prevents recursive purging - bool fPurging; - bool fNewlyPurgeableResourceWhilePurging; - PFOverBudgetCB fOverBudgetCB; void* fOverBudgetData; InvalidContentKeyInbox fInvalidContentKeyInbox; - }; class GrResourceCache::ResourceAccess { -- cgit v1.2.3