cc/prioritized_resource_manager.cc - chromium/src - Git at Google

 // Copyright 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "cc/prioritized_resource_manager.h"

 #include "base/debug/trace_event.h"
 #include "base/stl_util.h"
 #include "cc/prioritized_resource.h"
 #include "cc/priority_calculator.h"
 #include "cc/proxy.h"
 #include <algorithm>

 using namespace std;

 namespace cc {

 PrioritizedResourceManager::PrioritizedResourceManager(int pool, const Proxy* proxy)
     : m_proxy(proxy)
     , m_maxMemoryLimitBytes(defaultMemoryAllocationLimit())
     , m_externalPriorityCutoff(PriorityCalculator::allowEverythingCutoff())
     , m_memoryUseBytes(0)
     , m_memoryAboveCutoffBytes(0)
     , m_memoryAvailableBytes(0)
     , m_pool(pool)
     , m_backingsTailNotSorted(false)
     , m_memoryVisibleBytes(0)
     , m_memoryVisibleAndNearbyBytes(0)
     , m_memoryVisibleLastPushedBytes(0)
     , m_memoryVisibleAndNearbyLastPushedBytes(0)
 {
 }

 PrioritizedResourceManager::~PrioritizedResourceManager()
 {
     while (m_textures.size() > 0)
         unregisterTexture(*m_textures.begin());

     deleteAllEvictedBackings();
     DCHECK(m_evictedBackings.empty());

     // Each remaining backing is a leaked opengl texture. There should be none.
     DCHECK(m_backings.empty());
 }

 size_t PrioritizedResourceManager::memoryVisibleBytes() const
 {
     DCHECK(m_proxy->isImplThread());
     return m_memoryVisibleLastPushedBytes;
 }

 size_t PrioritizedResourceManager::memoryVisibleAndNearbyBytes() const
 {
     DCHECK(m_proxy->isImplThread());
     return m_memoryVisibleAndNearbyLastPushedBytes;
 }

 void PrioritizedResourceManager::prioritizeTextures()
 {
     TRACE_EVENT0("cc", "PrioritizedResourceManager::prioritizeTextures");
     DCHECK(m_proxy->isMainThread());

     // Sorting textures in this function could be replaced by a slightly
     // modified O(n) quick-select to partition textures rather than
     // sort them (if performance of the sort becomes an issue).

     TextureVector& sortedTextures = m_tempTextureVector;
     sortedTextures.clear();

     // Copy all textures into a vector, sort them, and collect memory requirements statistics.
     m_memoryVisibleBytes = 0;
     m_memoryVisibleAndNearbyBytes = 0;
     for (TextureSet::iterator it = m_textures.begin(); it != m_textures.end(); ++it) {
         PrioritizedResource* texture = (*it);
         sortedTextures.push_back(texture);
         if (PriorityCalculator::priorityIsHigher(texture->requestPriority(), PriorityCalculator::allowVisibleOnlyCutoff()))
             m_memoryVisibleBytes += texture->bytes();
         if (PriorityCalculator::priorityIsHigher(texture->requestPriority(), PriorityCalculator::allowVisibleAndNearbyCutoff()))
             m_memoryVisibleAndNearbyBytes += texture->bytes();
     }
     std::sort(sortedTextures.begin(), sortedTextures.end(), compareTextures);

     // Compute a priority cutoff based on memory pressure
     m_memoryAvailableBytes = m_maxMemoryLimitBytes;
     m_priorityCutoff = m_externalPriorityCutoff;
     size_t memoryBytes = 0;
     for (TextureVector::iterator it = sortedTextures.begin(); it != sortedTextures.end(); ++it) {
         if ((*it)->isSelfManaged()) {
             // Account for self-managed memory immediately by reducing the memory
             // available (since it never gets acquired).
             size_t newMemoryBytes = memoryBytes + (*it)->bytes();
             if (newMemoryBytes > m_memoryAvailableBytes) {
                 m_priorityCutoff = (*it)->requestPriority();
                 m_memoryAvailableBytes = memoryBytes;
                 break;
             }
             m_memoryAvailableBytes -= (*it)->bytes();
         } else {
             size_t newMemoryBytes = memoryBytes + (*it)->bytes();
             if (newMemoryBytes > m_memoryAvailableBytes) {
                 m_priorityCutoff = (*it)->requestPriority();
                 break;
             }
             memoryBytes = newMemoryBytes;
         }
     }

     // Disallow any textures with priority below the external cutoff to have backings.
     for (TextureVector::iterator it = sortedTextures.begin(); it != sortedTextures.end(); ++it) {
         PrioritizedResource* texture = (*it);
         if (!PriorityCalculator::priorityIsHigher(texture->requestPriority(), m_externalPriorityCutoff) &&
             texture->haveBackingTexture())
             texture->unlink();
     }

     // Only allow textures if they are higher than the cutoff. All textures
     // of the same priority are accepted or rejected together, rather than
     // being partially allowed randomly.
     m_memoryAboveCutoffBytes = 0;
     for (TextureVector::iterator it = sortedTextures.begin(); it != sortedTextures.end(); ++it) {
         bool isAbovePriorityCutoff = PriorityCalculator::priorityIsHigher((*it)->requestPriority(), m_priorityCutoff);
         (*it)->setAbovePriorityCutoff(isAbovePriorityCutoff);
         if (isAbovePriorityCutoff && !(*it)->isSelfManaged())
             m_memoryAboveCutoffBytes += (*it)->bytes();
     }
     sortedTextures.clear();

     DCHECK(m_memoryAboveCutoffBytes <= m_memoryAvailableBytes);
     DCHECK(memoryAboveCutoffBytes() <= maxMemoryLimitBytes());
 }

 void PrioritizedResourceManager::pushTexturePrioritiesToBackings()
 {
     TRACE_EVENT0("cc", "PrioritizedResourceManager::pushTexturePrioritiesToBackings");
     DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());

     assertInvariants();
     for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it)
         (*it)->updatePriority();
     sortBackings();
     assertInvariants();

     // Push memory requirements to the impl thread structure.
     m_memoryVisibleLastPushedBytes = m_memoryVisibleBytes;
     m_memoryVisibleAndNearbyLastPushedBytes = m_memoryVisibleAndNearbyBytes;
 }

 void PrioritizedResourceManager::updateBackingsInDrawingImplTree()
 {
     TRACE_EVENT0("cc", "PrioritizedResourceManager::updateBackingsInDrawingImplTree");
     DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());

     assertInvariants();
     for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
         PrioritizedResource::Backing* backing = (*it);
         backing->updateInDrawingImplTree();
     }
     sortBackings();
     assertInvariants();
 }

 void PrioritizedResourceManager::sortBackings()
 {
     TRACE_EVENT0("cc", "PrioritizedResourceManager::sortBackings");
     DCHECK(m_proxy->isImplThread());

     // Put backings in eviction/recycling order.
     m_backings.sort(compareBackings);
     m_backingsTailNotSorted = false;
 }

 void PrioritizedResourceManager::clearPriorities()
 {
     DCHECK(m_proxy->isMainThread());
     for (TextureSet::iterator it = m_textures.begin(); it != m_textures.end(); ++it) {
         // FIXME: We should remove this and just set all priorities to
         //        PriorityCalculator::lowestPriority() once we have priorities
         //        for all textures (we can't currently calculate distances for
         //        off-screen textures).
         (*it)->setRequestPriority(PriorityCalculator::lingeringPriority((*it)->requestPriority()));
     }
 }

 bool PrioritizedResourceManager::requestLate(PrioritizedResource* texture)
 {
     DCHECK(m_proxy->isMainThread());

     // This is already above cutoff, so don't double count it's memory below.
     if (texture->isAbovePriorityCutoff())
         return true;

     // Allow textures that have priority equal to the cutoff, but not strictly lower.
     if (PriorityCalculator::priorityIsLower(texture->requestPriority(), m_priorityCutoff))
         return false;

     // Disallow textures that do not have a priority strictly higher than the external cutoff.
     if (!PriorityCalculator::priorityIsHigher(texture->requestPriority(), m_externalPriorityCutoff))
         return false;

     size_t newMemoryBytes = m_memoryAboveCutoffBytes + texture->bytes();
     if (newMemoryBytes > m_memoryAvailableBytes)
         return false;

     m_memoryAboveCutoffBytes = newMemoryBytes;
     texture->setAbovePriorityCutoff(true);
     return true;
 }

 void PrioritizedResourceManager::acquireBackingTextureIfNeeded(PrioritizedResource* texture, ResourceProvider* resourceProvider)
 {
     DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());
     DCHECK(!texture->isSelfManaged());
     DCHECK(texture->isAbovePriorityCutoff());
     if (texture->backing() || !texture->isAbovePriorityCutoff())
         return;

     // Find a backing below, by either recycling or allocating.
     PrioritizedResource::Backing* backing = 0;

     // First try to recycle
     for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
         if (!(*it)->canBeRecycled())
             break;
         if ((*it)->size() == texture->size() && (*it)->format() == texture->format()) {
             backing = (*it);
             m_backings.erase(it);
             break;
         }
     }

     // Otherwise reduce memory and just allocate a new backing texures.
     if (!backing) {
         evictBackingsToReduceMemory(m_memoryAvailableBytes - texture->bytes(),
                                     PriorityCalculator::allowEverythingCutoff(),
                                     EvictOnlyRecyclable,
                                     DoNotUnlinkBackings,
                                     resourceProvider);
         backing = createBacking(texture->size(), texture->format(), resourceProvider);
     }

     // Move the used backing to the end of the eviction list, and note that
     // the tail is not sorted.
     if (backing->owner())
         backing->owner()->unlink();
     texture->link(backing);
     m_backings.push_back(backing);
     m_backingsTailNotSorted = true;

     // Update the backing's priority from its new owner.
     backing->updatePriority();
 }

 bool PrioritizedResourceManager::evictBackingsToReduceMemory(size_t limitBytes,
                                                              int priorityCutoff,
                                                              EvictionPolicy evictionPolicy,
                                                              UnlinkPolicy unlinkPolicy,
                                                              ResourceProvider* resourceProvider)
 {
     DCHECK(m_proxy->isImplThread());
     if (unlinkPolicy == UnlinkBackings)
         DCHECK(m_proxy->isMainThreadBlocked());
     if (memoryUseBytes() <= limitBytes && PriorityCalculator::allowEverythingCutoff() == priorityCutoff)
         return false;

     // Destroy backings until we are below the limit,
     // or until all backings remaining are above the cutoff.
     while (m_backings.size() > 0) {
         PrioritizedResource::Backing* backing = m_backings.front();
         if (memoryUseBytes() <= limitBytes &&
             PriorityCalculator::priorityIsHigher(backing->requestPriorityAtLastPriorityUpdate(), priorityCutoff))
             break;
         if (evictionPolicy == EvictOnlyRecyclable && !backing->canBeRecycled())
             break;
         if (unlinkPolicy == UnlinkBackings && backing->owner())
             backing->owner()->unlink();
         evictFirstBackingResource(resourceProvider);
     }
     return true;
 }

 void PrioritizedResourceManager::reduceMemory(ResourceProvider* resourceProvider)
 {
     DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());
     evictBackingsToReduceMemory(m_memoryAvailableBytes,
                                 PriorityCalculator::allowEverythingCutoff(),
                                 EvictAnything,
                                 UnlinkBackings,
                                 resourceProvider);
     DCHECK(memoryUseBytes() <= m_memoryAvailableBytes);

     // We currently collect backings from deleted textures for later recycling.
     // However, if we do that forever we will always use the max limit even if
     // we really need very little memory. This should probably be solved by reducing the
     // limit externally, but until then this just does some "clean up" of unused
     // backing textures (any more than 10%).
     size_t wastedMemory = 0;
     for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
         if ((*it)->owner())
             break;
         wastedMemory += (*it)->bytes();
     }
     size_t tenPercentOfMemory = m_memoryAvailableBytes / 10;
     if (wastedMemory > tenPercentOfMemory)
         evictBackingsToReduceMemory(memoryUseBytes() - (wastedMemory - tenPercentOfMemory),
                                     PriorityCalculator::allowEverythingCutoff(),
                                     EvictOnlyRecyclable,
                                     UnlinkBackings,
                                     resourceProvider);

     // Unlink all evicted backings
     for (BackingList::const_iterator it = m_evictedBackings.begin(); it != m_evictedBackings.end(); ++it) {
         if ((*it)->owner())
             (*it)->owner()->unlink();
     }

     // And clear the list of evicted backings
     deleteAllEvictedBackings();
 }

 void PrioritizedResourceManager::clearAllMemory(ResourceProvider* resourceProvider)
 {
     DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());
     DCHECK(resourceProvider);
     evictBackingsToReduceMemory(0,
                                 PriorityCalculator::allowEverythingCutoff(),
                                 EvictAnything,
                                 DoNotUnlinkBackings,
                                 resourceProvider);
 }

 bool PrioritizedResourceManager::reduceMemoryOnImplThread(size_t limitBytes, int priorityCutoff, ResourceProvider* resourceProvider)
 {
     DCHECK(m_proxy->isImplThread());
     DCHECK(resourceProvider);
     // If we are in the process of uploading a new frame then the backings at the very end of
     // the list are not sorted by priority. Sort them before doing the eviction.
     if (m_backingsTailNotSorted)
         sortBackings();
     return evictBackingsToReduceMemory(limitBytes,
                                        priorityCutoff,
                                        EvictAnything,
                                        DoNotUnlinkBackings,
                                        resourceProvider);
 }

 void PrioritizedResourceManager::getEvictedBackings(BackingList& evictedBackings)
 {
     DCHECK(m_proxy->isImplThread());
     evictedBackings.clear();
     evictedBackings.insert(evictedBackings.begin(), m_evictedBackings.begin(), m_evictedBackings.end());
     for (BackingList::const_iterator it = evictedBackings.begin(); it != evictedBackings.end(); ++it) {
         PrioritizedResource::Backing* backing = (*it);
         CHECK(!backing->m_inMainThreadEvictedList);
         backing->m_inMainThreadEvictedList = true;
     }
 }

 void PrioritizedResourceManager::unlinkEvictedBackings(const BackingList& evictedBackings)
 {
     DCHECK(m_proxy->isMainThread());
     for (BackingList::const_iterator it = evictedBackings.begin(); it != evictedBackings.end(); ++it) {
         PrioritizedResource::Backing* backing = (*it);
         CHECK(backing->m_inMainThreadEvictedList);
         backing->m_inMainThreadEvictedList = false;
         if (backing->owner()) {
             CHECK(backing->owner()->backing());
             CHECK(backing->owner()->backing() == backing);
             backing->owner()->unlink();
         }
     }
 }

 void PrioritizedResourceManager::deleteAllEvictedBackings()
 {
     DCHECK(m_proxy->isMainThread() || (m_proxy->isImplThread() && m_proxy->isMainThreadBlocked()));
     for (BackingList::const_iterator it = m_evictedBackings.begin(); it != m_evictedBackings.end(); ++it) {
         PrioritizedResource::Backing* backing = (*it);
         CHECK(!backing->owner());
         delete backing;
     }
     m_evictedBackings.clear();
 }

 bool PrioritizedResourceManager::linkedEvictedBackingsExist() const
 {
     for (BackingList::const_iterator it = m_evictedBackings.begin(); it != m_evictedBackings.end(); ++it) {
         if ((*it)->owner())
             return true;
     }
     return false;
 }

 void PrioritizedResourceManager::registerTexture(PrioritizedResource* texture)
 {
     DCHECK(m_proxy->isMainThread());
     DCHECK(texture);
     DCHECK(!texture->resourceManager());
     DCHECK(!texture->backing());
     DCHECK(!ContainsKey(m_textures, texture));

     texture->setManagerInternal(this);
     m_textures.insert(texture);

 }

 void PrioritizedResourceManager::unregisterTexture(PrioritizedResource* texture)
 {
     DCHECK(m_proxy->isMainThread() || (m_proxy->isImplThread() && m_proxy->isMainThreadBlocked()));
     DCHECK(texture);
     DCHECK(ContainsKey(m_textures, texture));

     returnBackingTexture(texture);
     texture->setManagerInternal(0);
     m_textures.erase(texture);
     texture->setAbovePriorityCutoff(false);
 }

 void PrioritizedResourceManager::returnBackingTexture(PrioritizedResource* texture)
 {
     DCHECK(m_proxy->isMainThread() || (m_proxy->isImplThread() && m_proxy->isMainThreadBlocked()));
     if (texture->backing())
         texture->unlink();
 }

 PrioritizedResource::Backing* PrioritizedResourceManager::createBacking(gfx::Size size, GLenum format, ResourceProvider* resourceProvider)
 {
     DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());
     DCHECK(resourceProvider);
     ResourceProvider::ResourceId resourceId = resourceProvider->createResource(m_pool, size, format, ResourceProvider::TextureUsageAny);
     PrioritizedResource::Backing* backing = new PrioritizedResource::Backing(resourceId, resourceProvider, size, format);
     m_memoryUseBytes += backing->bytes();
     return backing;
 }

 void PrioritizedResourceManager::evictFirstBackingResource(ResourceProvider* resourceProvider)
 {
     DCHECK(m_proxy->isImplThread());
     DCHECK(resourceProvider);
     DCHECK(!m_backings.empty());
     PrioritizedResource::Backing* backing = m_backings.front();

     // Note that we create a backing and its resource at the same time, but we
     // delete the backing structure and its resource in two steps. This is because
     // we can delete the resource while the main thread is running, but we cannot
     // unlink backings while the main thread is running.
     backing->deleteResource(resourceProvider);
     m_memoryUseBytes -= backing->bytes();
     m_backings.pop_front();
     m_evictedBackings.push_back(backing);
 }

 void PrioritizedResourceManager::assertInvariants()
 {
 #ifndef NDEBUG
     DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());

     // If we hit any of these asserts, there is a bug in this class. To see
     // where the bug is, call this function at the beginning and end of
     // every public function.

     // Backings/textures must be doubly-linked and only to other backings/textures in this manager.
     for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
         if ((*it)->owner()) {
             DCHECK(ContainsKey(m_textures, (*it)->owner()));
             DCHECK((*it)->owner()->backing() == (*it));
         }
     }
     for (TextureSet::iterator it = m_textures.begin(); it != m_textures.end(); ++it) {
         PrioritizedResource* texture = (*it);
         PrioritizedResource::Backing* backing = texture->backing();
         if (backing) {
             if (backing->resourceHasBeenDeleted()) {
                 DCHECK(std::find(m_backings.begin(), m_backings.end(), backing) == m_backings.end());
                 DCHECK(std::find(m_evictedBackings.begin(), m_evictedBackings.end(), backing) != m_evictedBackings.end());
             } else {
                 DCHECK(std::find(m_backings.begin(), m_backings.end(), backing) != m_backings.end());
                 DCHECK(std::find(m_evictedBackings.begin(), m_evictedBackings.end(), backing) == m_evictedBackings.end());
             }
             DCHECK(backing->owner() == texture);
         }
     }

     // At all times, backings that can be evicted must always come before
     // backings that can't be evicted in the backing texture list (otherwise
     // reduceMemory will not find all textures available for eviction/recycling).
     bool reachedUnrecyclable = false;
     PrioritizedResource::Backing* previous_backing = NULL;
     for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
         PrioritizedResource::Backing* backing = *it;
         if (previous_backing && (!m_backingsTailNotSorted || !backing->wasAbovePriorityCutoffAtLastPriorityUpdate()))
             DCHECK(compareBackings(previous_backing, backing));
         if (!backing->canBeRecycled())
             reachedUnrecyclable = true;
         if (reachedUnrecyclable)
             DCHECK(!backing->canBeRecycled());
         else
             DCHECK(backing->canBeRecycled());
         previous_backing = backing;
     }
 #endif
 }

 const Proxy* PrioritizedResourceManager::proxyForDebug() const
 {
     return m_proxy;
 }

 }  // namespace cc
	// Copyright 2012 The Chromium Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "cc/prioritized_resource_manager.h"

	#include "base/debug/trace_event.h"
	#include "base/stl_util.h"
	#include "cc/prioritized_resource.h"
	#include "cc/priority_calculator.h"
	#include "cc/proxy.h"
	#include <algorithm>

	using namespace std;

	namespace cc {

	PrioritizedResourceManager::PrioritizedResourceManager(int pool, const Proxy* proxy)
	: m_proxy(proxy)
	, m_maxMemoryLimitBytes(defaultMemoryAllocationLimit())
	, m_externalPriorityCutoff(PriorityCalculator::allowEverythingCutoff())
	, m_memoryUseBytes(0)
	, m_memoryAboveCutoffBytes(0)
	, m_memoryAvailableBytes(0)
	, m_pool(pool)
	, m_backingsTailNotSorted(false)
	, m_memoryVisibleBytes(0)
	, m_memoryVisibleAndNearbyBytes(0)
	, m_memoryVisibleLastPushedBytes(0)
	, m_memoryVisibleAndNearbyLastPushedBytes(0)
	{
	}

	PrioritizedResourceManager::~PrioritizedResourceManager()
	{
	while (m_textures.size() > 0)
	unregisterTexture(*m_textures.begin());

	deleteAllEvictedBackings();
	DCHECK(m_evictedBackings.empty());

	// Each remaining backing is a leaked opengl texture. There should be none.
	DCHECK(m_backings.empty());
	}

	size_t PrioritizedResourceManager::memoryVisibleBytes() const
	{
	DCHECK(m_proxy->isImplThread());
	return m_memoryVisibleLastPushedBytes;
	}

	size_t PrioritizedResourceManager::memoryVisibleAndNearbyBytes() const
	{
	DCHECK(m_proxy->isImplThread());
	return m_memoryVisibleAndNearbyLastPushedBytes;
	}

	void PrioritizedResourceManager::prioritizeTextures()
	{
	TRACE_EVENT0("cc", "PrioritizedResourceManager::prioritizeTextures");
	DCHECK(m_proxy->isMainThread());

	// Sorting textures in this function could be replaced by a slightly
	// modified O(n) quick-select to partition textures rather than
	// sort them (if performance of the sort becomes an issue).

	TextureVector& sortedTextures = m_tempTextureVector;
	sortedTextures.clear();

	// Copy all textures into a vector, sort them, and collect memory requirements statistics.
	m_memoryVisibleBytes = 0;
	m_memoryVisibleAndNearbyBytes = 0;
	for (TextureSet::iterator it = m_textures.begin(); it != m_textures.end(); ++it) {
	PrioritizedResource* texture = (*it);
	sortedTextures.push_back(texture);
	if (PriorityCalculator::priorityIsHigher(texture->requestPriority(), PriorityCalculator::allowVisibleOnlyCutoff()))
	m_memoryVisibleBytes += texture->bytes();
	if (PriorityCalculator::priorityIsHigher(texture->requestPriority(), PriorityCalculator::allowVisibleAndNearbyCutoff()))
	m_memoryVisibleAndNearbyBytes += texture->bytes();
	}
	std::sort(sortedTextures.begin(), sortedTextures.end(), compareTextures);

	// Compute a priority cutoff based on memory pressure
	m_memoryAvailableBytes = m_maxMemoryLimitBytes;
	m_priorityCutoff = m_externalPriorityCutoff;
	size_t memoryBytes = 0;
	for (TextureVector::iterator it = sortedTextures.begin(); it != sortedTextures.end(); ++it) {
	if ((*it)->isSelfManaged()) {
	// Account for self-managed memory immediately by reducing the memory
	// available (since it never gets acquired).
	size_t newMemoryBytes = memoryBytes + (*it)->bytes();
	if (newMemoryBytes > m_memoryAvailableBytes) {
	m_priorityCutoff = (*it)->requestPriority();
	m_memoryAvailableBytes = memoryBytes;
	break;
	}
	m_memoryAvailableBytes -= (*it)->bytes();
	} else {
	size_t newMemoryBytes = memoryBytes + (*it)->bytes();
	if (newMemoryBytes > m_memoryAvailableBytes) {
	m_priorityCutoff = (*it)->requestPriority();
	break;
	}
	memoryBytes = newMemoryBytes;
	}
	}

	// Disallow any textures with priority below the external cutoff to have backings.
	for (TextureVector::iterator it = sortedTextures.begin(); it != sortedTextures.end(); ++it) {
	PrioritizedResource* texture = (*it);
	if (!PriorityCalculator::priorityIsHigher(texture->requestPriority(), m_externalPriorityCutoff) &&
	texture->haveBackingTexture())
	texture->unlink();
	}

	// Only allow textures if they are higher than the cutoff. All textures
	// of the same priority are accepted or rejected together, rather than
	// being partially allowed randomly.
	m_memoryAboveCutoffBytes = 0;
	for (TextureVector::iterator it = sortedTextures.begin(); it != sortedTextures.end(); ++it) {
	bool isAbovePriorityCutoff = PriorityCalculator::priorityIsHigher((*it)->requestPriority(), m_priorityCutoff);
	(*it)->setAbovePriorityCutoff(isAbovePriorityCutoff);
	if (isAbovePriorityCutoff && !(*it)->isSelfManaged())
	m_memoryAboveCutoffBytes += (*it)->bytes();
	}
	sortedTextures.clear();

	DCHECK(m_memoryAboveCutoffBytes <= m_memoryAvailableBytes);
	DCHECK(memoryAboveCutoffBytes() <= maxMemoryLimitBytes());
	}

	void PrioritizedResourceManager::pushTexturePrioritiesToBackings()
	{
	TRACE_EVENT0("cc", "PrioritizedResourceManager::pushTexturePrioritiesToBackings");
	DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());

	assertInvariants();
	for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it)
	(*it)->updatePriority();
	sortBackings();
	assertInvariants();

	// Push memory requirements to the impl thread structure.
	m_memoryVisibleLastPushedBytes = m_memoryVisibleBytes;
	m_memoryVisibleAndNearbyLastPushedBytes = m_memoryVisibleAndNearbyBytes;
	}

	void PrioritizedResourceManager::updateBackingsInDrawingImplTree()
	{
	TRACE_EVENT0("cc", "PrioritizedResourceManager::updateBackingsInDrawingImplTree");
	DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());

	assertInvariants();
	for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
	PrioritizedResource::Backing* backing = (*it);
	backing->updateInDrawingImplTree();
	}
	sortBackings();
	assertInvariants();
	}

	void PrioritizedResourceManager::sortBackings()
	{
	TRACE_EVENT0("cc", "PrioritizedResourceManager::sortBackings");
	DCHECK(m_proxy->isImplThread());

	// Put backings in eviction/recycling order.
	m_backings.sort(compareBackings);
	m_backingsTailNotSorted = false;
	}

	void PrioritizedResourceManager::clearPriorities()
	{
	DCHECK(m_proxy->isMainThread());
	for (TextureSet::iterator it = m_textures.begin(); it != m_textures.end(); ++it) {
	// FIXME: We should remove this and just set all priorities to
	// PriorityCalculator::lowestPriority() once we have priorities
	// for all textures (we can't currently calculate distances for
	// off-screen textures).
	(it)->setRequestPriority(PriorityCalculator::lingeringPriority((it)->requestPriority()));
	}
	}

	bool PrioritizedResourceManager::requestLate(PrioritizedResource* texture)
	{
	DCHECK(m_proxy->isMainThread());

	// This is already above cutoff, so don't double count it's memory below.
	if (texture->isAbovePriorityCutoff())
	return true;

	// Allow textures that have priority equal to the cutoff, but not strictly lower.
	if (PriorityCalculator::priorityIsLower(texture->requestPriority(), m_priorityCutoff))
	return false;

	// Disallow textures that do not have a priority strictly higher than the external cutoff.
	if (!PriorityCalculator::priorityIsHigher(texture->requestPriority(), m_externalPriorityCutoff))
	return false;

	size_t newMemoryBytes = m_memoryAboveCutoffBytes + texture->bytes();
	if (newMemoryBytes > m_memoryAvailableBytes)
	return false;

	m_memoryAboveCutoffBytes = newMemoryBytes;
	texture->setAbovePriorityCutoff(true);
	return true;
	}

	void PrioritizedResourceManager::acquireBackingTextureIfNeeded(PrioritizedResource* texture, ResourceProvider* resourceProvider)
	{
	DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());
	DCHECK(!texture->isSelfManaged());
	DCHECK(texture->isAbovePriorityCutoff());
	if (texture->backing() \|\| !texture->isAbovePriorityCutoff())
	return;

	// Find a backing below, by either recycling or allocating.
	PrioritizedResource::Backing* backing = 0;

	// First try to recycle
	for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
	if (!(*it)->canBeRecycled())
	break;
	if ((it)->size() == texture->size() && (it)->format() == texture->format()) {
	backing = (*it);
	m_backings.erase(it);
	break;
	}
	}

	// Otherwise reduce memory and just allocate a new backing texures.
	if (!backing) {
	evictBackingsToReduceMemory(m_memoryAvailableBytes - texture->bytes(),
	PriorityCalculator::allowEverythingCutoff(),
	EvictOnlyRecyclable,
	DoNotUnlinkBackings,
	resourceProvider);
	backing = createBacking(texture->size(), texture->format(), resourceProvider);
	}

	// Move the used backing to the end of the eviction list, and note that
	// the tail is not sorted.
	if (backing->owner())
	backing->owner()->unlink();
	texture->link(backing);
	m_backings.push_back(backing);
	m_backingsTailNotSorted = true;

	// Update the backing's priority from its new owner.
	backing->updatePriority();
	}

	bool PrioritizedResourceManager::evictBackingsToReduceMemory(size_t limitBytes,
	int priorityCutoff,
	EvictionPolicy evictionPolicy,
	UnlinkPolicy unlinkPolicy,
	ResourceProvider* resourceProvider)
	{
	DCHECK(m_proxy->isImplThread());
	if (unlinkPolicy == UnlinkBackings)
	DCHECK(m_proxy->isMainThreadBlocked());
	if (memoryUseBytes() <= limitBytes && PriorityCalculator::allowEverythingCutoff() == priorityCutoff)
	return false;

	// Destroy backings until we are below the limit,
	// or until all backings remaining are above the cutoff.
	while (m_backings.size() > 0) {
	PrioritizedResource::Backing* backing = m_backings.front();
	if (memoryUseBytes() <= limitBytes &&
	PriorityCalculator::priorityIsHigher(backing->requestPriorityAtLastPriorityUpdate(), priorityCutoff))
	break;
	if (evictionPolicy == EvictOnlyRecyclable && !backing->canBeRecycled())
	break;
	if (unlinkPolicy == UnlinkBackings && backing->owner())
	backing->owner()->unlink();
	evictFirstBackingResource(resourceProvider);
	}
	return true;
	}

	void PrioritizedResourceManager::reduceMemory(ResourceProvider* resourceProvider)
	{
	DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());
	evictBackingsToReduceMemory(m_memoryAvailableBytes,
	PriorityCalculator::allowEverythingCutoff(),
	EvictAnything,
	UnlinkBackings,
	resourceProvider);
	DCHECK(memoryUseBytes() <= m_memoryAvailableBytes);

	// We currently collect backings from deleted textures for later recycling.
	// However, if we do that forever we will always use the max limit even if
	// we really need very little memory. This should probably be solved by reducing the
	// limit externally, but until then this just does some "clean up" of unused
	// backing textures (any more than 10%).
	size_t wastedMemory = 0;
	for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
	if ((*it)->owner())
	break;
	wastedMemory += (*it)->bytes();
	}
	size_t tenPercentOfMemory = m_memoryAvailableBytes / 10;
	if (wastedMemory > tenPercentOfMemory)
	evictBackingsToReduceMemory(memoryUseBytes() - (wastedMemory - tenPercentOfMemory),
	PriorityCalculator::allowEverythingCutoff(),
	EvictOnlyRecyclable,
	UnlinkBackings,
	resourceProvider);

	// Unlink all evicted backings
	for (BackingList::const_iterator it = m_evictedBackings.begin(); it != m_evictedBackings.end(); ++it) {
	if ((*it)->owner())
	(*it)->owner()->unlink();
	}

	// And clear the list of evicted backings
	deleteAllEvictedBackings();
	}

	void PrioritizedResourceManager::clearAllMemory(ResourceProvider* resourceProvider)
	{
	DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());
	DCHECK(resourceProvider);
	evictBackingsToReduceMemory(0,
	PriorityCalculator::allowEverythingCutoff(),
	EvictAnything,
	DoNotUnlinkBackings,
	resourceProvider);
	}

	bool PrioritizedResourceManager::reduceMemoryOnImplThread(size_t limitBytes, int priorityCutoff, ResourceProvider* resourceProvider)
	{
	DCHECK(m_proxy->isImplThread());
	DCHECK(resourceProvider);
	// If we are in the process of uploading a new frame then the backings at the very end of
	// the list are not sorted by priority. Sort them before doing the eviction.
	if (m_backingsTailNotSorted)
	sortBackings();
	return evictBackingsToReduceMemory(limitBytes,
	priorityCutoff,
	EvictAnything,
	DoNotUnlinkBackings,
	resourceProvider);
	}

	void PrioritizedResourceManager::getEvictedBackings(BackingList& evictedBackings)
	{
	DCHECK(m_proxy->isImplThread());
	evictedBackings.clear();
	evictedBackings.insert(evictedBackings.begin(), m_evictedBackings.begin(), m_evictedBackings.end());
	for (BackingList::const_iterator it = evictedBackings.begin(); it != evictedBackings.end(); ++it) {
	PrioritizedResource::Backing* backing = (*it);
	CHECK(!backing->m_inMainThreadEvictedList);
	backing->m_inMainThreadEvictedList = true;
	}
	}

	void PrioritizedResourceManager::unlinkEvictedBackings(const BackingList& evictedBackings)
	{
	DCHECK(m_proxy->isMainThread());
	for (BackingList::const_iterator it = evictedBackings.begin(); it != evictedBackings.end(); ++it) {
	PrioritizedResource::Backing* backing = (*it);
	CHECK(backing->m_inMainThreadEvictedList);
	backing->m_inMainThreadEvictedList = false;
	if (backing->owner()) {
	CHECK(backing->owner()->backing());
	CHECK(backing->owner()->backing() == backing);
	backing->owner()->unlink();
	}
	}
	}

	void PrioritizedResourceManager::deleteAllEvictedBackings()
	{
	DCHECK(m_proxy->isMainThread() \|\| (m_proxy->isImplThread() && m_proxy->isMainThreadBlocked()));
	for (BackingList::const_iterator it = m_evictedBackings.begin(); it != m_evictedBackings.end(); ++it) {
	PrioritizedResource::Backing* backing = (*it);
	CHECK(!backing->owner());
	delete backing;
	}
	m_evictedBackings.clear();
	}

	bool PrioritizedResourceManager::linkedEvictedBackingsExist() const
	{
	for (BackingList::const_iterator it = m_evictedBackings.begin(); it != m_evictedBackings.end(); ++it) {
	if ((*it)->owner())
	return true;
	}
	return false;
	}

	void PrioritizedResourceManager::registerTexture(PrioritizedResource* texture)
	{
	DCHECK(m_proxy->isMainThread());
	DCHECK(texture);
	DCHECK(!texture->resourceManager());
	DCHECK(!texture->backing());
	DCHECK(!ContainsKey(m_textures, texture));

	texture->setManagerInternal(this);
	m_textures.insert(texture);

	}

	void PrioritizedResourceManager::unregisterTexture(PrioritizedResource* texture)
	{
	DCHECK(m_proxy->isMainThread() \|\| (m_proxy->isImplThread() && m_proxy->isMainThreadBlocked()));
	DCHECK(texture);
	DCHECK(ContainsKey(m_textures, texture));

	returnBackingTexture(texture);
	texture->setManagerInternal(0);
	m_textures.erase(texture);
	texture->setAbovePriorityCutoff(false);
	}

	void PrioritizedResourceManager::returnBackingTexture(PrioritizedResource* texture)
	{
	DCHECK(m_proxy->isMainThread() \|\| (m_proxy->isImplThread() && m_proxy->isMainThreadBlocked()));
	if (texture->backing())
	texture->unlink();
	}

	PrioritizedResource::Backing* PrioritizedResourceManager::createBacking(gfx::Size size, GLenum format, ResourceProvider* resourceProvider)
	{
	DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());
	DCHECK(resourceProvider);
	ResourceProvider::ResourceId resourceId = resourceProvider->createResource(m_pool, size, format, ResourceProvider::TextureUsageAny);
	PrioritizedResource::Backing* backing = new PrioritizedResource::Backing(resourceId, resourceProvider, size, format);
	m_memoryUseBytes += backing->bytes();
	return backing;
	}

	void PrioritizedResourceManager::evictFirstBackingResource(ResourceProvider* resourceProvider)
	{
	DCHECK(m_proxy->isImplThread());
	DCHECK(resourceProvider);
	DCHECK(!m_backings.empty());
	PrioritizedResource::Backing* backing = m_backings.front();

	// Note that we create a backing and its resource at the same time, but we
	// delete the backing structure and its resource in two steps. This is because
	// we can delete the resource while the main thread is running, but we cannot
	// unlink backings while the main thread is running.
	backing->deleteResource(resourceProvider);
	m_memoryUseBytes -= backing->bytes();
	m_backings.pop_front();
	m_evictedBackings.push_back(backing);
	}

	void PrioritizedResourceManager::assertInvariants()
	{
	#ifndef NDEBUG
	DCHECK(m_proxy->isImplThread() && m_proxy->isMainThreadBlocked());

	// If we hit any of these asserts, there is a bug in this class. To see
	// where the bug is, call this function at the beginning and end of
	// every public function.

	// Backings/textures must be doubly-linked and only to other backings/textures in this manager.
	for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
	if ((*it)->owner()) {
	DCHECK(ContainsKey(m_textures, (*it)->owner()));
	DCHECK((it)->owner()->backing() == (it));
	}
	}
	for (TextureSet::iterator it = m_textures.begin(); it != m_textures.end(); ++it) {
	PrioritizedResource* texture = (*it);
	PrioritizedResource::Backing* backing = texture->backing();
	if (backing) {
	if (backing->resourceHasBeenDeleted()) {
	DCHECK(std::find(m_backings.begin(), m_backings.end(), backing) == m_backings.end());
	DCHECK(std::find(m_evictedBackings.begin(), m_evictedBackings.end(), backing) != m_evictedBackings.end());
	} else {
	DCHECK(std::find(m_backings.begin(), m_backings.end(), backing) != m_backings.end());
	DCHECK(std::find(m_evictedBackings.begin(), m_evictedBackings.end(), backing) == m_evictedBackings.end());
	}
	DCHECK(backing->owner() == texture);
	}
	}

	// At all times, backings that can be evicted must always come before
	// backings that can't be evicted in the backing texture list (otherwise
	// reduceMemory will not find all textures available for eviction/recycling).
	bool reachedUnrecyclable = false;
	PrioritizedResource::Backing* previous_backing = NULL;
	for (BackingList::iterator it = m_backings.begin(); it != m_backings.end(); ++it) {
	PrioritizedResource::Backing* backing = *it;
	if (previous_backing && (!m_backingsTailNotSorted \|\| !backing->wasAbovePriorityCutoffAtLastPriorityUpdate()))
	DCHECK(compareBackings(previous_backing, backing));
	if (!backing->canBeRecycled())
	reachedUnrecyclable = true;
	if (reachedUnrecyclable)
	DCHECK(!backing->canBeRecycled());
	else
	DCHECK(backing->canBeRecycled());
	previous_backing = backing;
	}
	#endif
	}

	const Proxy* PrioritizedResourceManager::proxyForDebug() const
	{
	return m_proxy;
	}

	} // namespace cc