src/gpu/GrResourceAllocator.cpp - skia - Git at Google

 /*
  * Copyright 2017 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */

 #include "src/gpu/GrResourceAllocator.h"

 #include "src/gpu/GrDirectContextPriv.h"
 #include "src/gpu/GrGpuResourcePriv.h"
 #include "src/gpu/GrOpsTask.h"
 #include "src/gpu/GrRenderTargetProxy.h"
 #include "src/gpu/GrResourceProvider.h"
 #include "src/gpu/GrSurfaceProxy.h"
 #include "src/gpu/GrSurfaceProxyPriv.h"

 #ifdef SK_DEBUG
 #include <atomic>

 uint32_t GrResourceAllocator::Interval::CreateUniqueID() {
     static std::atomic<uint32_t> nextID{1};
     uint32_t id;
     do {
         id = nextID.fetch_add(1, std::memory_order_relaxed);
     } while (id == SK_InvalidUniqueID);
     return id;
 }

 uint32_t GrResourceAllocator::Register::CreateUniqueID() {
     static std::atomic<uint32_t> nextID{1};
     uint32_t id;
     do {
         id = nextID.fetch_add(1, std::memory_order_relaxed);
     } while (id == SK_InvalidUniqueID);
     return id;
 }
 #endif

 GrResourceAllocator::~GrResourceAllocator() {
     SkASSERT(fFailedInstantiation || fIntvlList.empty());
     SkASSERT(fActiveIntvls.empty());
     SkASSERT(!fIntvlHash.count());
 }

 void GrResourceAllocator::addInterval(GrSurfaceProxy* proxy, unsigned int start, unsigned int end,
                                       ActualUse actualUse
                                       SkDEBUGCODE(, bool isDirectDstRead)) {
     SkASSERT(start <= end);
     SkASSERT(!fAssigned);  // We shouldn't be adding any intervals after (or during) assignment

     if (proxy->canSkipResourceAllocator()) {
         return;
     }

     // If a proxy is read only it must refer to a texture with specific content that cannot be
     // recycled. We don't need to assign a texture to it and no other proxy can be instantiated
     // with the same texture.
     if (proxy->readOnly()) {
         auto resourceProvider = fDContext->priv().resourceProvider();
         if (proxy->isLazy() && !proxy->priv().doLazyInstantiation(resourceProvider)) {
             fFailedInstantiation = true;
         } else {
             // Since we aren't going to add an interval we won't revisit this proxy in assign(). So
             // must already be instantiated or it must be a lazy proxy that we instantiated above.
             SkASSERT(proxy->isInstantiated());
         }
         return;
     }
     uint32_t proxyID = proxy->uniqueID().asUInt();
     if (Interval** intvlPtr = fIntvlHash.find(proxyID)) {
         // Revise the interval for an existing use
         Interval* intvl = *intvlPtr;
 #ifdef SK_DEBUG
         if (0 == start && 0 == end) {
             // This interval is for the initial upload to a deferred proxy. Due to the vagaries
             // of how deferred proxies are collected they can appear as uploads multiple times
             // in a single opsTasks' list and as uploads in several opsTasks.
             SkASSERT(0 == intvl->start());
         } else if (isDirectDstRead) {
             // Direct reads from the render target itself should occur w/in the existing
             // interval
             SkASSERT(intvl->start() <= start && intvl->end() >= end);
         } else {
             SkASSERT(intvl->end() <= start && intvl->end() <= end);
         }
 #endif
         if (ActualUse::kYes == actualUse) {
             intvl->addUse();
         }
         intvl->extendEnd(end);
         return;
     }
     Interval* newIntvl = fInternalAllocator.make<Interval>(proxy, start, end);

     if (ActualUse::kYes == actualUse) {
         newIntvl->addUse();
     }
     fIntvlList.insertByIncreasingStart(newIntvl);
     fIntvlHash.set(proxyID, newIntvl);
 }

 // Tragically we have cases where we always have to make new textures.
 static bool can_proxy_use_scratch(const GrCaps& caps, GrSurfaceProxy* proxy) {
     return caps.reuseScratchTextures() || proxy->asRenderTargetProxy();
 }

 GrResourceAllocator::Register::Register(GrSurfaceProxy* originatingProxy,
                                         GrScratchKey scratchKey,
                                         GrResourceProvider* provider)
         : fOriginatingProxy(originatingProxy)
         , fScratchKey(std::move(scratchKey)) {
     SkASSERT(originatingProxy);
     SkASSERT(!originatingProxy->isInstantiated());
     SkASSERT(!originatingProxy->isLazy());
     SkDEBUGCODE(fUniqueID = CreateUniqueID();)
     if (scratchKey.isValid()) {
         if (can_proxy_use_scratch(*provider->caps(), originatingProxy)) {
             fExistingSurface = provider->findAndRefScratchTexture(fScratchKey);
         }
     } else {
         SkASSERT(this->uniqueKey().isValid());
         fExistingSurface = provider->findByUniqueKey<GrSurface>(this->uniqueKey());
     }
 }

 bool GrResourceAllocator::Register::isRecyclable(const GrCaps& caps,
                                                  GrSurfaceProxy* proxy,
                                                  int knownUseCount) const {
     if (!can_proxy_use_scratch(caps, proxy)) {
         return false;
     }

     if (!this->scratchKey().isValid()) {
         return false; // no scratch key, no free pool
     }
     if (this->uniqueKey().isValid()) {
         return false; // rely on the resource cache to hold onto uniquely-keyed surfaces.
     }
     // If all the refs on the proxy are known to the resource allocator then no one
     // should be holding onto it outside of Ganesh.
     return !proxy->refCntGreaterThan(knownUseCount);
 }

 bool GrResourceAllocator::Register::instantiateSurface(GrSurfaceProxy* proxy,
                                                        GrResourceProvider* resourceProvider) {
     SkASSERT(!proxy->peekSurface());

     sk_sp<GrSurface> newSurface;
     if (!fExistingSurface) {
         if (proxy == fOriginatingProxy) {
             newSurface = proxy->priv().createSurface(resourceProvider);
         } else {
             newSurface = sk_ref_sp(fOriginatingProxy->peekSurface());
         }
     }
     if (!fExistingSurface && !newSurface) {
         return false;
     }

     GrSurface* surface = newSurface ? newSurface.get() : fExistingSurface.get();
     // Make surface budgeted if this proxy is budgeted.
     if (SkBudgeted::kYes == proxy->isBudgeted() &&
         GrBudgetedType::kBudgeted != surface->resourcePriv().budgetedType()) {
         // This gets the job done but isn't quite correct. It would be better to try to
         // match budgeted proxies w/ budgeted surfaces and unbudgeted w/ unbudgeted.
         surface->resourcePriv().makeBudgeted();
     }

     // Propagate the proxy unique key to the surface if we have one.
     if (const auto& uniqueKey = proxy->getUniqueKey(); uniqueKey.isValid()) {
         if (!surface->getUniqueKey().isValid()) {
             resourceProvider->assignUniqueKeyToResource(uniqueKey, surface);
         }
         SkASSERT(surface->getUniqueKey() == uniqueKey);
     }
     proxy->priv().assign(fExistingSurface ? fExistingSurface : std::move(newSurface));
     return true;
 }

 GrResourceAllocator::Interval* GrResourceAllocator::IntervalList::popHead() {
     SkDEBUGCODE(this->validate());

     Interval* temp = fHead;
     if (temp) {
         fHead = temp->next();
         if (!fHead) {
             fTail = nullptr;
         }
         temp->setNext(nullptr);
     }

     SkDEBUGCODE(this->validate());
     return temp;
 }

 // TODO: fuse this with insertByIncreasingEnd
 void GrResourceAllocator::IntervalList::insertByIncreasingStart(Interval* intvl) {
     SkDEBUGCODE(this->validate());
     SkASSERT(!intvl->next());

     if (!fHead) {
         // 14%
         fHead = fTail = intvl;
     } else if (intvl->start() <= fHead->start()) {
         // 3%
         intvl->setNext(fHead);
         fHead = intvl;
     } else if (fTail->start() <= intvl->start()) {
         // 83%
         fTail->setNext(intvl);
         fTail = intvl;
     } else {
         // almost never
         Interval* prev = fHead;
         Interval* next = prev->next();
         for (; intvl->start() > next->start(); prev = next, next = next->next()) {
         }

         SkASSERT(next);
         intvl->setNext(next);
         prev->setNext(intvl);
     }

     SkDEBUGCODE(this->validate());
 }

 // TODO: fuse this with insertByIncreasingStart
 void GrResourceAllocator::IntervalList::insertByIncreasingEnd(Interval* intvl) {
     SkDEBUGCODE(this->validate());
     SkASSERT(!intvl->next());

     if (!fHead) {
         // 14%
         fHead = fTail = intvl;
     } else if (intvl->end() <= fHead->end()) {
         // 64%
         intvl->setNext(fHead);
         fHead = intvl;
     } else if (fTail->end() <= intvl->end()) {
         // 3%
         fTail->setNext(intvl);
         fTail = intvl;
     } else {
         // 19% but 81% of those land right after the list's head
         Interval* prev = fHead;
         Interval* next = prev->next();
         for (; intvl->end() > next->end(); prev = next, next = next->next()) {
         }

         SkASSERT(next);
         intvl->setNext(next);
         prev->setNext(intvl);
     }

     SkDEBUGCODE(this->validate());
 }

 #ifdef SK_DEBUG
 void GrResourceAllocator::IntervalList::validate() const {
     SkASSERT(SkToBool(fHead) == SkToBool(fTail));

     Interval* prev = nullptr;
     for (Interval* cur = fHead; cur; prev = cur, cur = cur->next()) {
     }

     SkASSERT(fTail == prev);
 }
 #endif

 // First try to reuse one of the recently allocated/used registers in the free pool.
 GrResourceAllocator::Register* GrResourceAllocator::findOrCreateRegisterFor(GrSurfaceProxy* proxy) {
     auto resourceProvider = fDContext->priv().resourceProvider();
     // Handle uniquely keyed proxies
     if (const auto& uniqueKey = proxy->getUniqueKey(); uniqueKey.isValid()) {
         if (auto p = fUniqueKeyRegisters.find(uniqueKey)) {
             return *p;
         }
         // No need for a scratch key. These don't go in the free pool.
         Register* r = fInternalAllocator.make<Register>(proxy, GrScratchKey(), resourceProvider);
         fUniqueKeyRegisters.set(uniqueKey, r);
         return r;
     }

     // Then look in the free pool
     GrScratchKey scratchKey;
     proxy->priv().computeScratchKey(*fDContext->priv().caps(), &scratchKey);

     auto filter = [] (const Register* r) {
         return true;
     };
     if (Register* r = fFreePool.findAndRemove(scratchKey, filter)) {
         return r;
     }

     return fInternalAllocator.make<Register>(proxy, std::move(scratchKey), resourceProvider);
 }

 // Remove any intervals that end before the current index. Add their registers
 // to the free pool if possible.
 void GrResourceAllocator::expire(unsigned int curIndex) {
     while (!fActiveIntvls.empty() && fActiveIntvls.peekHead()->end() < curIndex) {
         Interval* intvl = fActiveIntvls.popHead();
         SkASSERT(!intvl->next());

         Register* r = intvl->getRegister();
         if (r && r->isRecyclable(*fDContext->priv().caps(), intvl->proxy(), intvl->uses())) {
 #if GR_ALLOCATION_SPEW
             SkDebugf("putting register %d back into pool\n", r->uniqueID());
 #endif
             // TODO: fix this insertion so we get a more LRU-ish behavior
             fFreePool.insert(r->scratchKey(), r);
         }
         fFinishedIntvls.insertByIncreasingStart(intvl);
     }
 }

 bool GrResourceAllocator::planAssignment() {
     fIntvlHash.reset(); // we don't need the interval hash anymore

     SkASSERT(!fPlanned && !fAssigned);
     SkDEBUGCODE(fPlanned = true;)

 #if GR_ALLOCATION_SPEW
     SkDebugf("assigning %d ops\n", fNumOps);
     this->dumpIntervals();
 #endif

     auto resourceProvider = fDContext->priv().resourceProvider();
     while (Interval* cur = fIntvlList.popHead()) {
         this->expire(cur->start());
         fActiveIntvls.insertByIncreasingEnd(cur);

         // Already-instantiated proxies and lazy proxies don't use registers.
         if (cur->proxy()->isInstantiated()) {
             continue;
         }

         // Instantiate fully-lazy proxies immediately. Ignore other lazy proxies at this stage.
         if (cur->proxy()->isLazy()) {
             if (cur->proxy()->isFullyLazy()) {
                 fFailedInstantiation = !cur->proxy()->priv().doLazyInstantiation(resourceProvider);
                 if (fFailedInstantiation) {
                     break;
                 }
             }
             continue;
         }

         Register* r = this->findOrCreateRegisterFor(cur->proxy());
 #if GR_ALLOCATION_SPEW
         SkDebugf("Assigning register %d to %d\n",
              r->uniqueID(),
              cur->proxy()->uniqueID().asUInt());
 #endif
         SkASSERT(!cur->proxy()->peekSurface());
         cur->setRegister(r);
     }

     // expire all the remaining intervals to drain the active interval list
     this->expire(std::numeric_limits<unsigned int>::max());
     return !fFailedInstantiation;
 }

 bool GrResourceAllocator::makeBudgetHeadroom() {
     SkASSERT(fPlanned);
     SkASSERT(!fFailedInstantiation);
     size_t additionalBytesNeeded = 0;
     for (Interval* cur = fFinishedIntvls.peekHead(); cur; cur = cur->next()) {
         GrSurfaceProxy* proxy = cur->proxy();
         if (SkBudgeted::kNo == proxy->isBudgeted() || proxy->isInstantiated()) {
             continue;
         }

         // N.B Fully-lazy proxies were already instantiated in planAssignment
         if (proxy->isLazy()) {
             additionalBytesNeeded += proxy->gpuMemorySize();
         } else {
             Register* r = cur->getRegister();
             SkASSERT(r);
             if (!r->accountedForInBudget() && !r->existingSurface()) {
                 additionalBytesNeeded += proxy->gpuMemorySize();
             }
             r->setAccountedForInBudget();
         }
     }
     return fDContext->priv().getResourceCache()->purgeToMakeHeadroom(additionalBytesNeeded);
 }

 void GrResourceAllocator::reset() {
     // NOTE: We do not reset the failedInstantiation flag because we currently do not attempt
     // to recover from failed instantiations. The user is responsible for checking this flag and
     // bailing early.
     SkDEBUGCODE(fPlanned = false;)
     SkDEBUGCODE(fAssigned = false;)
     SkASSERT(fActiveIntvls.empty());
     fFinishedIntvls = IntervalList();
     fIntvlList = IntervalList();
     fIntvlHash.reset();
     fUniqueKeyRegisters.reset();
     fFreePool.reset();
     fInternalAllocator.reset();
 }

 bool GrResourceAllocator::assign() {
     if (fFailedInstantiation) {
         return false;
     }
     SkASSERT(fPlanned && !fAssigned);
     SkDEBUGCODE(fAssigned = true;)
     auto resourceProvider = fDContext->priv().resourceProvider();
     while (Interval* cur = fFinishedIntvls.popHead()) {
         if (fFailedInstantiation) {
             break;
         }
         if (cur->proxy()->isInstantiated()) {
             continue;
         }
         if (cur->proxy()->isLazy()) {
             fFailedInstantiation = !cur->proxy()->priv().doLazyInstantiation(resourceProvider);
             continue;
         }
         Register* r = cur->getRegister();
         SkASSERT(r);
         fFailedInstantiation = !r->instantiateSurface(cur->proxy(), resourceProvider);
     }
     return !fFailedInstantiation;
 }

 #if GR_ALLOCATION_SPEW
 void GrResourceAllocator::dumpIntervals() {
     // Print all the intervals while computing their range
     SkDebugf("------------------------------------------------------------\n");
     unsigned int min = std::numeric_limits<unsigned int>::max();
     unsigned int max = 0;
     for(const Interval* cur = fIntvlList.peekHead(); cur; cur = cur->next()) {
         SkDebugf("{ %3d,%3d }: [%2d, %2d] - refProxys:%d surfaceRefs:%d\n",
                  cur->proxy()->uniqueID().asUInt(),
                  cur->proxy()->isInstantiated() ? cur->proxy()->underlyingUniqueID().asUInt() : -1,
                  cur->start(),
                  cur->end(),
                  cur->proxy()->priv().getProxyRefCnt(),
                  cur->proxy()->testingOnly_getBackingRefCnt());
         min = std::min(min, cur->start());
         max = std::max(max, cur->end());
     }

     // Draw a graph of the useage intervals
     for(const Interval* cur = fIntvlList.peekHead(); cur; cur = cur->next()) {
         SkDebugf("{ %3d,%3d }: ",
                  cur->proxy()->uniqueID().asUInt(),
                  cur->proxy()->isInstantiated() ? cur->proxy()->underlyingUniqueID().asUInt() : -1);
         for (unsigned int i = min; i <= max; ++i) {
             if (i >= cur->start() && i <= cur->end()) {
                 SkDebugf("x");
             } else {
                 SkDebugf(" ");
             }
         }
         SkDebugf("\n");
     }
 }
 #endif
	/*
	* Copyright 2017 Google Inc.
	*
	* Use of this source code is governed by a BSD-style license that can be
	* found in the LICENSE file.
	*/

	#include "src/gpu/GrResourceAllocator.h"

	#include "src/gpu/GrDirectContextPriv.h"
	#include "src/gpu/GrGpuResourcePriv.h"
	#include "src/gpu/GrOpsTask.h"
	#include "src/gpu/GrRenderTargetProxy.h"
	#include "src/gpu/GrResourceProvider.h"
	#include "src/gpu/GrSurfaceProxy.h"
	#include "src/gpu/GrSurfaceProxyPriv.h"

	#ifdef SK_DEBUG
	#include <atomic>

	uint32_t GrResourceAllocator::Interval::CreateUniqueID() {
	static std::atomic<uint32_t> nextID{1};
	uint32_t id;
	do {
	id = nextID.fetch_add(1, std::memory_order_relaxed);
	} while (id == SK_InvalidUniqueID);
	return id;
	}

	uint32_t GrResourceAllocator::Register::CreateUniqueID() {
	static std::atomic<uint32_t> nextID{1};
	uint32_t id;
	do {
	id = nextID.fetch_add(1, std::memory_order_relaxed);
	} while (id == SK_InvalidUniqueID);
	return id;
	}
	#endif

	GrResourceAllocator::~GrResourceAllocator() {
	SkASSERT(fFailedInstantiation \|\| fIntvlList.empty());
	SkASSERT(fActiveIntvls.empty());
	SkASSERT(!fIntvlHash.count());
	}

	void GrResourceAllocator::addInterval(GrSurfaceProxy* proxy, unsigned int start, unsigned int end,
	ActualUse actualUse
	SkDEBUGCODE(, bool isDirectDstRead)) {
	SkASSERT(start <= end);
	SkASSERT(!fAssigned); // We shouldn't be adding any intervals after (or during) assignment

	if (proxy->canSkipResourceAllocator()) {
	return;
	}

	// If a proxy is read only it must refer to a texture with specific content that cannot be
	// recycled. We don't need to assign a texture to it and no other proxy can be instantiated
	// with the same texture.
	if (proxy->readOnly()) {
	auto resourceProvider = fDContext->priv().resourceProvider();
	if (proxy->isLazy() && !proxy->priv().doLazyInstantiation(resourceProvider)) {
	fFailedInstantiation = true;
	} else {
	// Since we aren't going to add an interval we won't revisit this proxy in assign(). So
	// must already be instantiated or it must be a lazy proxy that we instantiated above.
	SkASSERT(proxy->isInstantiated());
	}
	return;
	}
	uint32_t proxyID = proxy->uniqueID().asUInt();
	if (Interval** intvlPtr = fIntvlHash.find(proxyID)) {
	// Revise the interval for an existing use
	Interval* intvl = *intvlPtr;
	#ifdef SK_DEBUG
	if (0 == start && 0 == end) {
	// This interval is for the initial upload to a deferred proxy. Due to the vagaries
	// of how deferred proxies are collected they can appear as uploads multiple times
	// in a single opsTasks' list and as uploads in several opsTasks.
	SkASSERT(0 == intvl->start());
	} else if (isDirectDstRead) {
	// Direct reads from the render target itself should occur w/in the existing
	// interval
	SkASSERT(intvl->start() <= start && intvl->end() >= end);
	} else {
	SkASSERT(intvl->end() <= start && intvl->end() <= end);
	}
	#endif
	if (ActualUse::kYes == actualUse) {
	intvl->addUse();
	}
	intvl->extendEnd(end);
	return;
	}
	Interval* newIntvl = fInternalAllocator.make<Interval>(proxy, start, end);

	if (ActualUse::kYes == actualUse) {
	newIntvl->addUse();
	}
	fIntvlList.insertByIncreasingStart(newIntvl);
	fIntvlHash.set(proxyID, newIntvl);
	}

	// Tragically we have cases where we always have to make new textures.
	static bool can_proxy_use_scratch(const GrCaps& caps, GrSurfaceProxy* proxy) {
	return caps.reuseScratchTextures() \|\| proxy->asRenderTargetProxy();
	}

	GrResourceAllocator::Register::Register(GrSurfaceProxy* originatingProxy,
	GrScratchKey scratchKey,
	GrResourceProvider* provider)
	: fOriginatingProxy(originatingProxy)
	, fScratchKey(std::move(scratchKey)) {
	SkASSERT(originatingProxy);
	SkASSERT(!originatingProxy->isInstantiated());
	SkASSERT(!originatingProxy->isLazy());
	SkDEBUGCODE(fUniqueID = CreateUniqueID();)
	if (scratchKey.isValid()) {
	if (can_proxy_use_scratch(*provider->caps(), originatingProxy)) {
	fExistingSurface = provider->findAndRefScratchTexture(fScratchKey);
	}
	} else {
	SkASSERT(this->uniqueKey().isValid());
	fExistingSurface = provider->findByUniqueKey<GrSurface>(this->uniqueKey());
	}
	}

	bool GrResourceAllocator::Register::isRecyclable(const GrCaps& caps,
	GrSurfaceProxy* proxy,
	int knownUseCount) const {
	if (!can_proxy_use_scratch(caps, proxy)) {
	return false;
	}

	if (!this->scratchKey().isValid()) {
	return false; // no scratch key, no free pool
	}
	if (this->uniqueKey().isValid()) {
	return false; // rely on the resource cache to hold onto uniquely-keyed surfaces.
	}
	// If all the refs on the proxy are known to the resource allocator then no one
	// should be holding onto it outside of Ganesh.
	return !proxy->refCntGreaterThan(knownUseCount);
	}

	bool GrResourceAllocator::Register::instantiateSurface(GrSurfaceProxy* proxy,
	GrResourceProvider* resourceProvider) {
	SkASSERT(!proxy->peekSurface());

	sk_sp<GrSurface> newSurface;
	if (!fExistingSurface) {
	if (proxy == fOriginatingProxy) {
	newSurface = proxy->priv().createSurface(resourceProvider);
	} else {
	newSurface = sk_ref_sp(fOriginatingProxy->peekSurface());
	}
	}
	if (!fExistingSurface && !newSurface) {
	return false;
	}

	GrSurface* surface = newSurface ? newSurface.get() : fExistingSurface.get();
	// Make surface budgeted if this proxy is budgeted.
	if (SkBudgeted::kYes == proxy->isBudgeted() &&
	GrBudgetedType::kBudgeted != surface->resourcePriv().budgetedType()) {
	// This gets the job done but isn't quite correct. It would be better to try to
	// match budgeted proxies w/ budgeted surfaces and unbudgeted w/ unbudgeted.
	surface->resourcePriv().makeBudgeted();
	}

	// Propagate the proxy unique key to the surface if we have one.
	if (const auto& uniqueKey = proxy->getUniqueKey(); uniqueKey.isValid()) {
	if (!surface->getUniqueKey().isValid()) {
	resourceProvider->assignUniqueKeyToResource(uniqueKey, surface);
	}
	SkASSERT(surface->getUniqueKey() == uniqueKey);
	}
	proxy->priv().assign(fExistingSurface ? fExistingSurface : std::move(newSurface));
	return true;
	}

	GrResourceAllocator::Interval* GrResourceAllocator::IntervalList::popHead() {
	SkDEBUGCODE(this->validate());

	Interval* temp = fHead;
	if (temp) {
	fHead = temp->next();
	if (!fHead) {
	fTail = nullptr;
	}
	temp->setNext(nullptr);
	}

	SkDEBUGCODE(this->validate());
	return temp;
	}

	// TODO: fuse this with insertByIncreasingEnd
	void GrResourceAllocator::IntervalList::insertByIncreasingStart(Interval* intvl) {
	SkDEBUGCODE(this->validate());
	SkASSERT(!intvl->next());

	if (!fHead) {
	// 14%
	fHead = fTail = intvl;
	} else if (intvl->start() <= fHead->start()) {
	// 3%
	intvl->setNext(fHead);
	fHead = intvl;
	} else if (fTail->start() <= intvl->start()) {
	// 83%
	fTail->setNext(intvl);
	fTail = intvl;
	} else {
	// almost never
	Interval* prev = fHead;
	Interval* next = prev->next();
	for (; intvl->start() > next->start(); prev = next, next = next->next()) {
	}

	SkASSERT(next);
	intvl->setNext(next);
	prev->setNext(intvl);
	}

	SkDEBUGCODE(this->validate());
	}

	// TODO: fuse this with insertByIncreasingStart
	void GrResourceAllocator::IntervalList::insertByIncreasingEnd(Interval* intvl) {
	SkDEBUGCODE(this->validate());
	SkASSERT(!intvl->next());

	if (!fHead) {
	// 14%
	fHead = fTail = intvl;
	} else if (intvl->end() <= fHead->end()) {
	// 64%
	intvl->setNext(fHead);
	fHead = intvl;
	} else if (fTail->end() <= intvl->end()) {
	// 3%
	fTail->setNext(intvl);
	fTail = intvl;
	} else {
	// 19% but 81% of those land right after the list's head
	Interval* prev = fHead;
	Interval* next = prev->next();
	for (; intvl->end() > next->end(); prev = next, next = next->next()) {
	}

	SkASSERT(next);
	intvl->setNext(next);
	prev->setNext(intvl);
	}

	SkDEBUGCODE(this->validate());
	}

	#ifdef SK_DEBUG
	void GrResourceAllocator::IntervalList::validate() const {
	SkASSERT(SkToBool(fHead) == SkToBool(fTail));

	Interval* prev = nullptr;
	for (Interval* cur = fHead; cur; prev = cur, cur = cur->next()) {
	}

	SkASSERT(fTail == prev);
	}
	#endif

	// First try to reuse one of the recently allocated/used registers in the free pool.
	GrResourceAllocator::Register* GrResourceAllocator::findOrCreateRegisterFor(GrSurfaceProxy* proxy) {
	auto resourceProvider = fDContext->priv().resourceProvider();
	// Handle uniquely keyed proxies
	if (const auto& uniqueKey = proxy->getUniqueKey(); uniqueKey.isValid()) {
	if (auto p = fUniqueKeyRegisters.find(uniqueKey)) {
	return *p;
	}
	// No need for a scratch key. These don't go in the free pool.
	Register* r = fInternalAllocator.make<Register>(proxy, GrScratchKey(), resourceProvider);
	fUniqueKeyRegisters.set(uniqueKey, r);
	return r;
	}

	// Then look in the free pool
	GrScratchKey scratchKey;
	proxy->priv().computeScratchKey(*fDContext->priv().caps(), &scratchKey);

	auto filter = [] (const Register* r) {
	return true;
	};
	if (Register* r = fFreePool.findAndRemove(scratchKey, filter)) {
	return r;
	}

	return fInternalAllocator.make<Register>(proxy, std::move(scratchKey), resourceProvider);
	}

	// Remove any intervals that end before the current index. Add their registers
	// to the free pool if possible.
	void GrResourceAllocator::expire(unsigned int curIndex) {
	while (!fActiveIntvls.empty() && fActiveIntvls.peekHead()->end() < curIndex) {
	Interval* intvl = fActiveIntvls.popHead();
	SkASSERT(!intvl->next());

	Register* r = intvl->getRegister();
	if (r && r->isRecyclable(*fDContext->priv().caps(), intvl->proxy(), intvl->uses())) {
	#if GR_ALLOCATION_SPEW
	SkDebugf("putting register %d back into pool\n", r->uniqueID());
	#endif
	// TODO: fix this insertion so we get a more LRU-ish behavior
	fFreePool.insert(r->scratchKey(), r);
	}
	fFinishedIntvls.insertByIncreasingStart(intvl);
	}
	}

	bool GrResourceAllocator::planAssignment() {
	fIntvlHash.reset(); // we don't need the interval hash anymore

	SkASSERT(!fPlanned && !fAssigned);
	SkDEBUGCODE(fPlanned = true;)

	#if GR_ALLOCATION_SPEW
	SkDebugf("assigning %d ops\n", fNumOps);
	this->dumpIntervals();
	#endif

	auto resourceProvider = fDContext->priv().resourceProvider();
	while (Interval* cur = fIntvlList.popHead()) {
	this->expire(cur->start());
	fActiveIntvls.insertByIncreasingEnd(cur);

	// Already-instantiated proxies and lazy proxies don't use registers.
	if (cur->proxy()->isInstantiated()) {
	continue;
	}

	// Instantiate fully-lazy proxies immediately. Ignore other lazy proxies at this stage.
	if (cur->proxy()->isLazy()) {
	if (cur->proxy()->isFullyLazy()) {
	fFailedInstantiation = !cur->proxy()->priv().doLazyInstantiation(resourceProvider);
	if (fFailedInstantiation) {
	break;
	}
	}
	continue;
	}

	Register* r = this->findOrCreateRegisterFor(cur->proxy());
	#if GR_ALLOCATION_SPEW
	SkDebugf("Assigning register %d to %d\n",
	r->uniqueID(),
	cur->proxy()->uniqueID().asUInt());
	#endif
	SkASSERT(!cur->proxy()->peekSurface());
	cur->setRegister(r);
	}

	// expire all the remaining intervals to drain the active interval list
	this->expire(std::numeric_limits<unsigned int>::max());
	return !fFailedInstantiation;
	}

	bool GrResourceAllocator::makeBudgetHeadroom() {
	SkASSERT(fPlanned);
	SkASSERT(!fFailedInstantiation);
	size_t additionalBytesNeeded = 0;
	for (Interval* cur = fFinishedIntvls.peekHead(); cur; cur = cur->next()) {
	GrSurfaceProxy* proxy = cur->proxy();
	if (SkBudgeted::kNo == proxy->isBudgeted() \|\| proxy->isInstantiated()) {
	continue;
	}

	// N.B Fully-lazy proxies were already instantiated in planAssignment
	if (proxy->isLazy()) {
	additionalBytesNeeded += proxy->gpuMemorySize();
	} else {
	Register* r = cur->getRegister();
	SkASSERT(r);
	if (!r->accountedForInBudget() && !r->existingSurface()) {
	additionalBytesNeeded += proxy->gpuMemorySize();
	}
	r->setAccountedForInBudget();
	}
	}
	return fDContext->priv().getResourceCache()->purgeToMakeHeadroom(additionalBytesNeeded);
	}

	void GrResourceAllocator::reset() {
	// NOTE: We do not reset the failedInstantiation flag because we currently do not attempt
	// to recover from failed instantiations. The user is responsible for checking this flag and
	// bailing early.
	SkDEBUGCODE(fPlanned = false;)
	SkDEBUGCODE(fAssigned = false;)
	SkASSERT(fActiveIntvls.empty());
	fFinishedIntvls = IntervalList();
	fIntvlList = IntervalList();
	fIntvlHash.reset();
	fUniqueKeyRegisters.reset();
	fFreePool.reset();
	fInternalAllocator.reset();
	}

	bool GrResourceAllocator::assign() {
	if (fFailedInstantiation) {
	return false;
	}
	SkASSERT(fPlanned && !fAssigned);
	SkDEBUGCODE(fAssigned = true;)
	auto resourceProvider = fDContext->priv().resourceProvider();
	while (Interval* cur = fFinishedIntvls.popHead()) {
	if (fFailedInstantiation) {
	break;
	}
	if (cur->proxy()->isInstantiated()) {
	continue;
	}
	if (cur->proxy()->isLazy()) {
	fFailedInstantiation = !cur->proxy()->priv().doLazyInstantiation(resourceProvider);
	continue;
	}
	Register* r = cur->getRegister();
	SkASSERT(r);
	fFailedInstantiation = !r->instantiateSurface(cur->proxy(), resourceProvider);
	}
	return !fFailedInstantiation;
	}

	#if GR_ALLOCATION_SPEW
	void GrResourceAllocator::dumpIntervals() {
	// Print all the intervals while computing their range
	SkDebugf("------------------------------------------------------------\n");
	unsigned int min = std::numeric_limits<unsigned int>::max();
	unsigned int max = 0;
	for(const Interval* cur = fIntvlList.peekHead(); cur; cur = cur->next()) {
	SkDebugf("{ %3d,%3d }: [%2d, %2d] - refProxys:%d surfaceRefs:%d\n",
	cur->proxy()->uniqueID().asUInt(),
	cur->proxy()->isInstantiated() ? cur->proxy()->underlyingUniqueID().asUInt() : -1,
	cur->start(),
	cur->end(),
	cur->proxy()->priv().getProxyRefCnt(),
	cur->proxy()->testingOnly_getBackingRefCnt());
	min = std::min(min, cur->start());
	max = std::max(max, cur->end());
	}

	// Draw a graph of the useage intervals
	for(const Interval* cur = fIntvlList.peekHead(); cur; cur = cur->next()) {
	SkDebugf("{ %3d,%3d }: ",
	cur->proxy()->uniqueID().asUInt(),
	cur->proxy()->isInstantiated() ? cur->proxy()->underlyingUniqueID().asUInt() : -1);
	for (unsigned int i = min; i <= max; ++i) {
	if (i >= cur->start() && i <= cur->end()) {
	SkDebugf("x");
	} else {
	SkDebugf(" ");
	}
	}
	SkDebugf("\n");
	}
	}
	#endif