cc: Start using raster/eviction iterators in tile manager

cc/resources/tile_manager.cc

Index: cc/resources/tile_manager.cc
diff --git a/cc/resources/tile_manager.cc b/cc/resources/tile_manager.cc
index 9494586e2e8bbe139731351ff9809f7587712096..e5701bd62fc857f28ebd7fdce252a0feefcfd8bb 100644
--- a/cc/resources/tile_manager.cc
+++ b/cc/resources/tile_manager.cc
@@ -245,110 +245,6 @@ class ImageDecodeTaskImpl : public ImageDecodeTask {
 
 const size_t kScheduledRasterTasksLimit = 32u;
 
-// Memory limit policy works by mapping some bin states to the NEVER bin.
-const ManagedTileBin kBinPolicyMap[NUM_TILE_MEMORY_LIMIT_POLICIES][NUM_BINS] = {
-    // [ALLOW_NOTHING]
-    {NEVER_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
-     NEVER_BIN,  // [NOW_BIN]
-     NEVER_BIN,  // [SOON_BIN]
-     NEVER_BIN,  // [EVENTUALLY_AND_ACTIVE_BIN]
-     NEVER_BIN,  // [EVENTUALLY_BIN]
-     NEVER_BIN,  // [AT_LAST_AND_ACTIVE_BIN]
-     NEVER_BIN,  // [AT_LAST_BIN]
-     NEVER_BIN   // [NEVER_BIN]
-    },
-    // [ALLOW_ABSOLUTE_MINIMUM]
-    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
-     NOW_BIN,                    // [NOW_BIN]
-     NEVER_BIN,                  // [SOON_BIN]
-     NEVER_BIN,                  // [EVENTUALLY_AND_ACTIVE_BIN]
-     NEVER_BIN,                  // [EVENTUALLY_BIN]
-     NEVER_BIN,                  // [AT_LAST_AND_ACTIVE_BIN]
-     NEVER_BIN,                  // [AT_LAST_BIN]
-     NEVER_BIN                   // [NEVER_BIN]
-    },
-    // [ALLOW_PREPAINT_ONLY]
-    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
-     NOW_BIN,                    // [NOW_BIN]
-     SOON_BIN,                   // [SOON_BIN]
-     NEVER_BIN,                  // [EVENTUALLY_AND_ACTIVE_BIN]
-     NEVER_BIN,                  // [EVENTUALLY_BIN]
-     NEVER_BIN,                  // [AT_LAST_AND_ACTIVE_BIN]
-     NEVER_BIN,                  // [AT_LAST_BIN]
-     NEVER_BIN                   // [NEVER_BIN]
-    },
-    // [ALLOW_ANYTHING]
-    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
-     NOW_BIN,                    // [NOW_BIN]
-     SOON_BIN,                   // [SOON_BIN]
-     EVENTUALLY_AND_ACTIVE_BIN,  // [EVENTUALLY_AND_ACTIVE_BIN]
-     EVENTUALLY_BIN,             // [EVENTUALLY_BIN]
-     AT_LAST_AND_ACTIVE_BIN,     // [AT_LAST_AND_ACTIVE_BIN]
-     AT_LAST_BIN,                // [AT_LAST_BIN]
-     NEVER_BIN                   // [NEVER_BIN]
-    }};
-
-// Ready to draw works by mapping NOW_BIN to NOW_AND_READY_TO_DRAW_BIN.
-const ManagedTileBin kBinReadyToDrawMap[2][NUM_BINS] = {
-    // Not ready
-    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
-     NOW_BIN,                    // [NOW_BIN]
-     SOON_BIN,                   // [SOON_BIN]
-     EVENTUALLY_AND_ACTIVE_BIN,  // [EVENTUALLY_AND_ACTIVE_BIN]
-     EVENTUALLY_BIN,             // [EVENTUALLY_BIN]
-     AT_LAST_AND_ACTIVE_BIN,     // [AT_LAST_AND_ACTIVE_BIN]
-     AT_LAST_BIN,                // [AT_LAST_BIN]
-     NEVER_BIN                   // [NEVER_BIN]
-    },
-    // Ready
-    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
-     NOW_AND_READY_TO_DRAW_BIN,  // [NOW_BIN]
-     SOON_BIN,                   // [SOON_BIN]
-     EVENTUALLY_AND_ACTIVE_BIN,  // [EVENTUALLY_AND_ACTIVE_BIN]
-     EVENTUALLY_BIN,             // [EVENTUALLY_BIN]
-     AT_LAST_AND_ACTIVE_BIN,     // [AT_LAST_AND_ACTIVE_BIN]
-     AT_LAST_BIN,                // [AT_LAST_BIN]
-     NEVER_BIN                   // [NEVER_BIN]
-    }};
-
-// Active works by mapping some bin stats to equivalent _ACTIVE_BIN state.
-const ManagedTileBin kBinIsActiveMap[2][NUM_BINS] = {
-    // Inactive
-    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
-     NOW_BIN,                    // [NOW_BIN]
-     SOON_BIN,                   // [SOON_BIN]
-     EVENTUALLY_AND_ACTIVE_BIN,  // [EVENTUALLY_AND_ACTIVE_BIN]
-     EVENTUALLY_BIN,             // [EVENTUALLY_BIN]
-     AT_LAST_AND_ACTIVE_BIN,     // [AT_LAST_AND_ACTIVE_BIN]
-     AT_LAST_BIN,                // [AT_LAST_BIN]
-     NEVER_BIN                   // [NEVER_BIN]
-    },
-    // Active
-    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
-     NOW_BIN,                    // [NOW_BIN]
-     SOON_BIN,                   // [SOON_BIN]
-     EVENTUALLY_AND_ACTIVE_BIN,  // [EVENTUALLY_AND_ACTIVE_BIN]
-     EVENTUALLY_AND_ACTIVE_BIN,  // [EVENTUALLY_BIN]
-     AT_LAST_AND_ACTIVE_BIN,     // [AT_LAST_AND_ACTIVE_BIN]
-     AT_LAST_AND_ACTIVE_BIN,     // [AT_LAST_BIN]
-     NEVER_BIN                   // [NEVER_BIN]
-    }};
-
-// Determine bin based on three categories of tiles: things we need now,
-// things we need soon, and eventually.
-inline ManagedTileBin BinFromTilePriority(const TilePriority& prio) {
-  if (prio.priority_bin == TilePriority::NOW)
-    return NOW_BIN;
-
-  if (prio.priority_bin == TilePriority::SOON)
-    return SOON_BIN;
-
-  if (prio.distance_to_visible == std::numeric_limits<float>::infinity())
-    return NEVER_BIN;
-
-  return EVENTUALLY_BIN;
-}
-
 }  // namespace
 
 RasterTaskCompletionStats::RasterTaskCompletionStats()
@@ -387,11 +283,8 @@ TileManager::TileManager(
     RenderingStatsInstrumentation* rendering_stats_instrumentation)
     : client_(client),
       resource_pool_(resource_pool),
-      prioritized_tiles_dirty_(false),
       all_tiles_that_need_to_be_rasterized_have_memory_(true),
       all_tiles_required_for_activation_have_memory_(true),
-      memory_required_bytes_(0),
-      memory_nice_to_have_bytes_(0),
       bytes_releasable_(0),
       resources_releasable_(0),
       ever_exceeded_memory_budget_(false),
@@ -436,14 +329,9 @@ TileManager::~TileManager() {
 }
 
 void TileManager::Release(Tile* tile) {
-  prioritized_tiles_dirty_ = true;
   released_tiles_.push_back(tile);
 }
 
-void TileManager::DidChangeTilePriority(Tile* tile) {
-  prioritized_tiles_dirty_ = true;
-}
-
 bool TileManager::ShouldForceTasksRequiredForActivationToComplete() const {
   return global_state_.tree_priority != SMOOTHNESS_TAKES_PRIORITY;
 }
@@ -477,17 +365,6 @@ void TileManager::CleanUpReleasedTiles() {
   released_tiles_.clear();
 }
 
-void TileManager::UpdatePrioritizedTileSetIfNeeded() {
-  if (!prioritized_tiles_dirty_)
-    return;
-
-  CleanUpReleasedTiles();
-
-  prioritized_tiles_.Clear();
-  GetTilesWithAssignedBins(&prioritized_tiles_);
-  prioritized_tiles_dirty_ = false;
-}
-
 void TileManager::DidFinishRunningTasks() {
   TRACE_EVENT0("cc", "TileManager::DidFinishRunningTasks");
 
@@ -504,8 +381,7 @@ void TileManager::DidFinishRunningTasks() {
   did_check_for_completed_tasks_since_last_schedule_tasks_ = true;
 
   TileVector tiles_that_need_to_be_rasterized;
-  AssignGpuMemoryToTiles(&prioritized_tiles_,
-                         &tiles_that_need_to_be_rasterized);
+  AssignGpuMemoryToTiles(&tiles_that_need_to_be_rasterized);
 
   // |tiles_that_need_to_be_rasterized| will be empty when we reach a
   // steady memory state. Keep scheduling tasks until we reach this state.
@@ -555,128 +431,6 @@ void TileManager::DidFinishRunningTasksRequiredForActivation() {
   client_->NotifyReadyToActivate();
 }
 
-void TileManager::GetTilesWithAssignedBins(PrioritizedTileSet* tiles) {
-  TRACE_EVENT0("cc", "TileManager::GetTilesWithAssignedBins");
-
-  // Compute new stats to be return by GetMemoryStats().
-  memory_required_bytes_ = 0;
-  memory_nice_to_have_bytes_ = 0;
-
-  const TileMemoryLimitPolicy memory_policy = global_state_.memory_limit_policy;
-  const TreePriority tree_priority = global_state_.tree_priority;
-
-  // For each tree, bin into different categories of tiles.
-  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
-    Tile* tile = it->second;
-    ManagedTileState& mts = tile->managed_state();
-
-    const ManagedTileState::TileVersion& tile_version =
-        tile->GetTileVersionForDrawing();
-    bool tile_is_ready_to_draw = tile_version.IsReadyToDraw();
-    bool tile_is_active = tile_is_ready_to_draw ||
-                          mts.tile_versions[mts.raster_mode].raster_task_;
-
-    // Get the active priority and bin.
-    TilePriority active_priority = tile->priority(ACTIVE_TREE);
-    ManagedTileBin active_bin = BinFromTilePriority(active_priority);
-
-    // Get the pending priority and bin.
-    TilePriority pending_priority = tile->priority(PENDING_TREE);
-    ManagedTileBin pending_bin = BinFromTilePriority(pending_priority);
-
-    bool pending_is_low_res = pending_priority.resolution == LOW_RESOLUTION;
-    bool pending_is_non_ideal =
-        pending_priority.resolution == NON_IDEAL_RESOLUTION;
-    bool active_is_non_ideal =
-        active_priority.resolution == NON_IDEAL_RESOLUTION;
-
-    // Adjust pending bin state for low res tiles. This prevents
-    // pending tree low-res tiles from being initialized before
-    // high-res tiles.
-    if (pending_is_low_res)
-      pending_bin = std::max(pending_bin, EVENTUALLY_BIN);
-
-    // Adjust bin state based on if ready to draw.
-    active_bin = kBinReadyToDrawMap[tile_is_ready_to_draw][active_bin];
-    pending_bin = kBinReadyToDrawMap[tile_is_ready_to_draw][pending_bin];
-
-    // Adjust bin state based on if active.
-    active_bin = kBinIsActiveMap[tile_is_active][active_bin];
-    pending_bin = kBinIsActiveMap[tile_is_active][pending_bin];
-
-    // We never want to paint new non-ideal tiles, as we always have
-    // a high-res tile covering that content (paint that instead).
-    if (!tile_is_ready_to_draw && active_is_non_ideal)
-      active_bin = NEVER_BIN;
-    if (!tile_is_ready_to_draw && pending_is_non_ideal)
-      pending_bin = NEVER_BIN;
-
-    // Compute combined bin.
-    ManagedTileBin combined_bin = std::min(active_bin, pending_bin);
-
-    if (!tile_is_ready_to_draw || tile_version.requires_resource()) {
-      // The bin that the tile would have if the GPU memory manager had
-      // a maximally permissive policy, send to the GPU memory manager
-      // to determine policy.
-      ManagedTileBin gpu_memmgr_stats_bin = combined_bin;
-      if ((gpu_memmgr_stats_bin == NOW_BIN) ||
-          (gpu_memmgr_stats_bin == NOW_AND_READY_TO_DRAW_BIN))
-        memory_required_bytes_ += BytesConsumedIfAllocated(tile);
-      if (gpu_memmgr_stats_bin != NEVER_BIN)
-        memory_nice_to_have_bytes_ += BytesConsumedIfAllocated(tile);
-    }
-
-    ManagedTileBin tree_bin[NUM_TREES];
-    tree_bin[ACTIVE_TREE] = kBinPolicyMap[memory_policy][active_bin];
-    tree_bin[PENDING_TREE] = kBinPolicyMap[memory_policy][pending_bin];
-
-    TilePriority tile_priority;
-    switch (tree_priority) {
-      case SAME_PRIORITY_FOR_BOTH_TREES:
-        mts.bin = kBinPolicyMap[memory_policy][combined_bin];
-        tile_priority = tile->combined_priority();
-        break;
-      case SMOOTHNESS_TAKES_PRIORITY:
-        mts.bin = tree_bin[ACTIVE_TREE];
-        tile_priority = active_priority;
-        break;
-      case NEW_CONTENT_TAKES_PRIORITY:
-        mts.bin = tree_bin[PENDING_TREE];
-        tile_priority = pending_priority;
-        break;
-    }
-
-    // Bump up the priority if we determined it's NEVER_BIN on one tree,
-    // but is still required on the other tree.
-    bool is_in_never_bin_on_both_trees = tree_bin[ACTIVE_TREE] == NEVER_BIN &&
-                                         tree_bin[PENDING_TREE] == NEVER_BIN;
-
-    if (mts.bin == NEVER_BIN && !is_in_never_bin_on_both_trees)
-      mts.bin = tile_is_active ? AT_LAST_AND_ACTIVE_BIN : AT_LAST_BIN;
-
-    mts.resolution = tile_priority.resolution;
-    mts.priority_bin = tile_priority.priority_bin;
-    mts.distance_to_visible = tile_priority.distance_to_visible;
-    mts.required_for_activation = tile_priority.required_for_activation;
-
-    mts.visible_and_ready_to_draw =
-        tree_bin[ACTIVE_TREE] == NOW_AND_READY_TO_DRAW_BIN;
-
-    // If the tile is in NEVER_BIN and it does not have an active task, then we
-    // can release the resources early. If it does have the task however, we
-    // should keep it in the prioritized tile set to ensure that AssignGpuMemory
-    // can visit it.
-    if (mts.bin == NEVER_BIN &&
-        !mts.tile_versions[mts.raster_mode].raster_task_) {
-      FreeResourcesForTile(tile);
-      continue;
-    }
-
-    // Insert the tile into a priority set.
-    tiles->InsertTile(tile, mts.bin);
-  }
-}
-
 void TileManager::CleanUpLayers() {
   for (size_t i = 0; i < layers_.size(); ++i) {
     if (layers_[i]->IsDrawnRenderSurfaceLayerListMember())
@@ -686,7 +440,6 @@ void TileManager::CleanUpLayers() {
     std::swap(layers_[i], layers_.back());
     layers_.pop_back();
     --i;
-    prioritized_tiles_dirty_ = true;
   }
 }
 
@@ -694,13 +447,14 @@ void TileManager::ManageTiles(const GlobalStateThatImpactsTilePriority& state) {
   TRACE_EVENT0("cc", "TileManager::ManageTiles");
 
   // Update internal state.
-  if (state != global_state_) {
-    global_state_ = state;
-    prioritized_tiles_dirty_ = true;
-  }
+  global_state_ = state;
 
   CleanUpLayers();
 
+  // TODO(vmpstr): See if we still need to keep tiles alive when layers release
+  // them.
+  CleanUpReleasedTiles();
+
   // We need to call CheckForCompletedTasks() once in-between each call
   // to ScheduleTasks() to prevent canceled tasks from being scheduled.
   if (!did_check_for_completed_tasks_since_last_schedule_tasks_) {
@@ -708,11 +462,8 @@ void TileManager::ManageTiles(const GlobalStateThatImpactsTilePriority& state) {
     did_check_for_completed_tasks_since_last_schedule_tasks_ = true;
   }
 
-  UpdatePrioritizedTileSetIfNeeded();
-
   TileVector tiles_that_need_to_be_rasterized;
-  AssignGpuMemoryToTiles(&prioritized_tiles_,
-                         &tiles_that_need_to_be_rasterized);
+  AssignGpuMemoryToTiles(&tiles_that_need_to_be_rasterized);
 
   // Finally, schedule rasterizer tasks.
   ScheduleTasks(tiles_that_need_to_be_rasterized);
@@ -754,8 +505,8 @@ void TileManager::GetMemoryStats(size_t* memory_required_bytes,
                                  size_t* memory_nice_to_have_bytes,
                                  size_t* memory_allocated_bytes,
                                  size_t* memory_used_bytes) const {
-  *memory_required_bytes = memory_required_bytes_;
-  *memory_nice_to_have_bytes = memory_nice_to_have_bytes_;
+  *memory_required_bytes = resource_pool_->total_memory_usage_bytes();
+  *memory_nice_to_have_bytes = resource_pool_->total_memory_usage_bytes();
   *memory_allocated_bytes = resource_pool_->total_memory_usage_bytes();
   *memory_used_bytes = resource_pool_->acquired_memory_usage_bytes();
 }
@@ -795,8 +546,47 @@ scoped_ptr<base::Value> TileManager::GetMemoryRequirementsAsValue() const {
   return requirements.PassAs<base::Value>();
 }
 
+bool TileManager::EvictTiles(EvictionTileIterator* eviction_iterator,

[reveman, 2014/05/20 23:01:00]

Could you rename this in a way that makes it more clear what it does?
FreeTileResourcesUntilUsageIsWithinBudget? And maybe return true on success,
false otherwise.

[vmpstr, 2014/05/27 22:41:32]

Done on the rename. It already returns a bool when it evicts rfa tiles. I guess
we can change that since we'll be checking for activation independently of this.

+                             const MemoryBudget& required_budget,
+                             MemoryBudget* current_budget,

[reveman, 2014/05/20 23:01:00]

I think it's a bit confusing with a budget that is being adjusted. It would be
much easier to understand if we were reducing our usage until we're within a
budget. What would it take to change that?

[vmpstr, 2014/05/27 22:41:32]

We still somehow need to know how much we actually released. It tries to be
within budget, it might fail, or it might release a lot (way more than the
needed budget). I mean it still needs to know the current budget in order to
meet the required budget, so I could pass it by copy, but still adjust it (just
hiding the information from the caller). 

I kind of prefer to have it this way to avoid recalculating how much we actually
evicted from the call site.

[reveman, 2014/05/28 16:04:12]

I think the system where we have a budget that we keep adjusting is a bit
backwards and a side effect of how the tile manager has evolved. I think this is
a good time to fix this.

IMO, it makes more sense to have a current usage and a budget that we need to
stay within. A simplified version of AssignGpuMemoryToTiles would ideally look
something like this:

while (raster_it) {
  Tile* tile = *raster_it;

  MemoryUsage tile_memory_usage = tile->MemoryRequiredToInitialize();
  if (!FreeTileResourcesUntilWithinBudget(budget_ - tile_memory_usage))
    break;

  AppendRasterTask(raster_queue, tile);
  ++raster_it;
}

Maybe just get rid of the temporary tiles_that_need_to_be_rasterized vector and
build the raster queue directly in AssignGpuMemoryToTiles. Let's chat offline.

+                             const TilePriority& raster_priority,

[reveman, 2014/05/20 23:01:00]

"max_priority"?

[vmpstr, 2014/05/27 22:41:32]

Done.

+                             bool evict_unconditionally) {

[reveman, 2014/05/20 23:01:00]

Instead of having evict_unconditionally, could you pass the highest possible
priority as max_priority?

[vmpstr, 2014/05/27 22:41:32]

It's in some sense max priority + 1, as in equal priorities aren't evicted (as
this will cause us to evict and rerasterize tiles of the same priority --
something we want to avoid).

+  bool evicted_tiles_required_for_activation = false;
+  while (required_budget.Exceeds(*current_budget)) {

[reveman, 2014/05/20 23:01:00]

Would it be a bit cleaner and more consistent with the raster iterator loop if
you have a for loop here that advance the iterator and instead early out of the
loop when within budget?

[vmpstr, 2014/05/27 22:41:32]

That would cause us to actually initialize the eviction iterator even if we're
already within budget (which is relatively expensive). Conceptually I think the
loop says the intent "while we're not within budget, evict" instead of "for all
eviction tiles, if we're already within budget, break"...

+    if (!*eviction_iterator)
+      break;
+
+    Tile* eviction_tile = **eviction_iterator;
+    DCHECK(eviction_tile);
+
+    TilePriority eviction_priority =
+        eviction_tile->priority_for_tree_priority(global_state_.tree_priority);
+
+    if (!evict_unconditionally &&
+        !raster_priority.IsHigherPriorityThan(eviction_priority))
+      break;

[reveman, 2014/05/20 23:01:00]

it would be nice if you flip this around and make it:

if (priority.IsHigherPriorityThan(max_priority))
  break;

max_priority is not the same as |raster_priority| so this might not work if we
really need this to not pass if priority is equal. Which brings me to:

Are we currently allowing a "distance_to_visible -
std::numeric_limits<float>::epsilon()" tile that need raster to evict an
initialized tile with "distance_to_visible"? And in that case, do we want that?
Should we be worried that some floating point inexactness will cause us to
alternative between tiles and raster forever? Would it make sense to define a
minimal TilePriority delta that is required between raster and eviction?

[vmpstr, 2014/05/27 22:41:32]

I definitely think we should not allow equal priorities to pass here. As for the
epsilon case, we could make that a part of "IsHigherPriorityThan" if it's a
concern. In practice I don't think there will be many cases like that, since one
will be biased to be better, but I don't see them alternating since the
calculation doesn't change...

+
+    size_t eviction_bytes_if_allocated =
+        BytesConsumedIfAllocated(eviction_tile);
+    ManagedTileState& eviction_mts = eviction_tile->managed_state();
+    for (int mode = 0; mode < NUM_RASTER_MODES; ++mode) {
+      if (eviction_mts.tile_versions[mode].resource_) {
+        current_budget->hard_memory_bytes += eviction_bytes_if_allocated;
+        if (eviction_priority.priority_bin != TilePriority::NOW)
+          current_budget->soft_memory_bytes += eviction_bytes_if_allocated;

[reveman, 2014/05/20 23:01:00]

Hard to see if this is always doing the right thing. I think it would be easier
to understand if this function was simply reducing the usage until within a
specified limit and the idea of a soft/hard limit was restricted to
AssignGpuMemoryToTiles.

[vmpstr, 2014/05/27 22:41:32]

This would mean that ASsignGpuMemoryToTiles would have to recalculate these
budgets again, which is something I'd like to avoid... Also, the whole concept
of Exceeds takes into account soft/hard limits, so I'm not too sure this
function can be made to work with just one memory limit and still be clean in
its usage.

[reveman, 2014/05/28 16:04:12]

I find this pretty confusing. Why do we care what priority a tile is when
evicting it and adjusting the budget? What if the tile priority changes? Does
that mess up the our budget calculations? This is part of what I think can be
much simpler if we switch to a model where we have a current usage and instead
adjusted the usage to to stay within the budget needed to be able to raster a
tile but let's chat more about this offline.

+        current_budget->resource_count++;
+      }
+    }
+    FreeResourcesForTile(eviction_tile);
+    ++(*eviction_iterator);
+
+    evicted_tiles_required_for_activation |=
+        eviction_tile->required_for_activation();
+  }
+  return evicted_tiles_required_for_activation;
+}
+
 void TileManager::AssignGpuMemoryToTiles(
-    PrioritizedTileSet* tiles,
     TileVector* tiles_that_need_to_be_rasterized) {
   TRACE_EVENT0("cc", "TileManager::AssignGpuMemoryToTiles");
 
@@ -812,36 +602,65 @@ void TileManager::AssignGpuMemoryToTiles(
   all_tiles_that_need_to_be_rasterized_have_memory_ = true;
   all_tiles_required_for_activation_have_memory_ = true;
 
+  MemoryBudget budget;
   // Cast to prevent overflow.
-  int64 soft_bytes_available =
-      static_cast<int64>(bytes_releasable_) +
+  budget.soft_memory_bytes =
       static_cast<int64>(global_state_.soft_memory_limit_in_bytes) -
       static_cast<int64>(resource_pool_->acquired_memory_usage_bytes());
-  int64 hard_bytes_available =
-      static_cast<int64>(bytes_releasable_) +
+  budget.hard_memory_bytes =
       static_cast<int64>(global_state_.hard_memory_limit_in_bytes) -
       static_cast<int64>(resource_pool_->acquired_memory_usage_bytes());
-  int resources_available = resources_releasable_ +
-                            global_state_.num_resources_limit -
-                            resource_pool_->acquired_resource_count();
-  size_t soft_bytes_allocatable =
-      std::max(static_cast<int64>(0), soft_bytes_available);
-  size_t hard_bytes_allocatable =
-      std::max(static_cast<int64>(0), hard_bytes_available);
-  size_t resources_allocatable = std::max(0, resources_available);
+  budget.resource_count = global_state_.num_resources_limit -
+                          resource_pool_->acquired_resource_count();
+
+  MemoryBudget initial_budget = budget;
+
+  EvictionTileIterator eviction_it(this, global_state_.tree_priority);
+
+  MemoryBudget required_budget;
+  required_budget.soft_memory_bytes = 0;
+  required_budget.hard_memory_bytes = 0;
+  required_budget.resource_count = 0;
+
+  bool evicted_tiles_required_for_activation =
+      EvictTiles(&eviction_it, required_budget, &budget, TilePriority(), true);

[reveman, 2014/05/20 23:01:00]

I think it would make more sense to evict tiles if we're still above the limit
after the loop below instead of before it.

[vmpstr, 2014/05/27 22:41:32]

We kind of create the budget and the iterator here, so I think it makes sense...
I mean if you really insist, I can change this, but to me "Make sure you're
within budget before you start assigning memory" makes as much as sense to me as
"Ensure once more you're within budget after assigning everything"

 
   size_t bytes_that_exceeded_memory_budget = 0;
-  size_t soft_bytes_left = soft_bytes_allocatable;
-  size_t hard_bytes_left = hard_bytes_allocatable;
 
-  size_t resources_left = resources_allocatable;
   bool oomed_soft = false;
   bool oomed_hard = false;
   bool have_hit_soft_memory = false;  // Soft memory comes after hard.
 
   unsigned schedule_priority = 1u;
-  for (PrioritizedTileSet::Iterator it(tiles, true); it; ++it) {
+  for (RasterTileIterator it(this, global_state_.tree_priority); it; ++it) {
     Tile* tile = *it;
+    TilePriority priority =
+        tile->priority_for_tree_priority(global_state_.tree_priority);
+
+    bool tile_violates_memory_policy = false;

[reveman, 2014/05/20 23:01:00]

Please add a TileViolatesMemoryPolicy helper function instead of this variable.

[vmpstr, 2014/05/27 22:41:32]

Done.

+    switch (global_state_.memory_limit_policy) {
+      case ALLOW_NOTHING:
+        tile_violates_memory_policy = true;
+        break;
+      case ALLOW_ABSOLUTE_MINIMUM:
+        tile_violates_memory_policy = priority.priority_bin > TilePriority::NOW;
+        break;
+      case ALLOW_PREPAINT_ONLY:
+        tile_violates_memory_policy =
+            priority.priority_bin > TilePriority::SOON;
+        break;
+      case ALLOW_ANYTHING:
+        tile_violates_memory_policy = priority.distance_to_visible ==
+                                      std::numeric_limits<float>::infinity();
+        break;
+      case NUM_TILE_MEMORY_LIMIT_POLICIES:
+        NOTREACHED();
+        break;
+    }
+
+    if (tile_violates_memory_policy)
+      break;
+
     ManagedTileState& mts = tile->managed_state();
 
     mts.scheduled_priority = schedule_priority++;
@@ -851,20 +670,13 @@ void TileManager::AssignGpuMemoryToTiles(
     ManagedTileState::TileVersion& tile_version =
         mts.tile_versions[mts.raster_mode];
 
-    // If this tile doesn't need a resource, then nothing to do.
-    if (!tile_version.requires_resource())
+    // If this tile version is ready to draw, then nothing to do.
+    if (tile_version.IsReadyToDraw())
       continue;
 
-    // If the tile is not needed, free it up.
-    if (mts.bin == NEVER_BIN) {
-      FreeResourcesForTile(tile);
-      continue;
-    }
-
-    const bool tile_uses_hard_limit = mts.bin <= NOW_BIN;
+    const bool tile_uses_hard_limit =
+        priority.priority_bin == TilePriority::NOW;
     const size_t bytes_if_allocated = BytesConsumedIfAllocated(tile);
-    const size_t tile_bytes_left =
-        (tile_uses_hard_limit) ? hard_bytes_left : soft_bytes_left;
 
     // Hard-limit is reserved for tiles that would cause a calamity
     // if they were to go away, so by definition they are the highest
@@ -872,8 +684,8 @@ void TileManager::AssignGpuMemoryToTiles(
     DCHECK(!(have_hit_soft_memory && tile_uses_hard_limit));
     have_hit_soft_memory |= !tile_uses_hard_limit;
 
-    size_t tile_bytes = 0;
-    size_t tile_resources = 0;
+    int64 tile_bytes = 0;
+    int tile_resources = 0;
 
     // It costs to maintain a resource.
     for (int mode = 0; mode < NUM_RASTER_MODES; ++mode) {
@@ -883,22 +695,28 @@ void TileManager::AssignGpuMemoryToTiles(
       }
     }
 
-    // Allow lower priority tiles with initialized resources to keep
-    // their memory by only assigning memory to new raster tasks if
-    // they can be scheduled.
-    bool reached_scheduled_raster_tasks_limit =
-        tiles_that_need_to_be_rasterized->size() >= kScheduledRasterTasksLimit;
-    if (!reached_scheduled_raster_tasks_limit) {
-      // If we don't have the required version, and it's not in flight
-      // then we'll have to pay to create a new task.
-      if (!tile_version.resource_ && !tile_version.raster_task_) {
-        tile_bytes += bytes_if_allocated;
-        tile_resources++;
-      }
+    // If we don't have the required version, and it's not in flight
+    // then we'll have to pay to create a new task.
+    if (!tile_version.resource_ && !tile_version.raster_task_) {
+      tile_bytes += bytes_if_allocated;
+      tile_resources++;
     }
 
-    // Tile is OOM.
-    if (tile_bytes > tile_bytes_left || tile_resources > resources_left) {
+    required_budget.soft_memory_bytes = 0;
+    required_budget.hard_memory_bytes = 0;
+    required_budget.resource_count = tile_resources;
+    if (tile_uses_hard_limit)
+      required_budget.hard_memory_bytes = tile_bytes;
+    else
+      required_budget.soft_memory_bytes = tile_bytes;
+
+    // Handle OOM tiles.
+    evicted_tiles_required_for_activation =
+        EvictTiles(&eviction_it, required_budget, &budget, priority, false) ||
+        evicted_tiles_required_for_activation;
+
+    // Tile is still OOM.
+    if (required_budget.Exceeds(budget)) {
       FreeResourcesForTile(tile);
 
       // This tile was already on screen and now its resources have been
@@ -913,10 +731,11 @@ void TileManager::AssignGpuMemoryToTiles(
         bytes_that_exceeded_memory_budget += tile_bytes;
       }
     } else {
-      resources_left -= tile_resources;
-      hard_bytes_left -= tile_bytes;
-      soft_bytes_left =
-          (soft_bytes_left > tile_bytes) ? soft_bytes_left - tile_bytes : 0;
+      budget.resource_count -= tile_resources;
+      budget.hard_memory_bytes -= tile_bytes;
+      budget.soft_memory_bytes = (budget.soft_memory_bytes > tile_bytes)
+                                     ? budget.soft_memory_bytes - tile_bytes
+                                     : 0;
       if (tile_version.resource_)
         continue;
     }
@@ -932,14 +751,15 @@ void TileManager::AssignGpuMemoryToTiles(
     // 2. Tiles with existing raster task could otherwise incorrectly
     //    be added as they are not affected by |bytes_allocatable|.
     bool can_schedule_tile =
-        !oomed_soft && !reached_scheduled_raster_tasks_limit;
+        !oomed_soft &&
+        tiles_that_need_to_be_rasterized->size() < kScheduledRasterTasksLimit;
 
     if (!can_schedule_tile) {
       all_tiles_that_need_to_be_rasterized_have_memory_ = false;
-      if (tile->required_for_activation())
-        all_tiles_required_for_activation_have_memory_ = false;
-      it.DisablePriorityOrdering();
-      continue;
+      all_tiles_required_for_activation_have_memory_ =
+          !it.HasTilesRequiredForActivation() &&
+          !evicted_tiles_required_for_activation;
+      break;
     }
 
     tiles_that_need_to_be_rasterized->push_back(tile);
@@ -959,7 +779,7 @@ void TileManager::AssignGpuMemoryToTiles(
   memory_stats_from_last_assign_.total_budget_in_bytes =
       global_state_.hard_memory_limit_in_bytes;
   memory_stats_from_last_assign_.bytes_allocated =
-      hard_bytes_allocatable - hard_bytes_left;
+      initial_budget.hard_memory_bytes - budget.hard_memory_bytes;
   memory_stats_from_last_assign_.bytes_unreleasable =
       resource_pool_->acquired_memory_usage_bytes() - bytes_releasable_;
   memory_stats_from_last_assign_.bytes_over = bytes_that_exceeded_memory_budget;
@@ -1225,7 +1045,6 @@ scoped_refptr<Tile> TileManager::CreateTile(PicturePileImpl* picture_pile,
 
   tiles_[tile->id()] = tile;
   used_layer_counts_[tile->layer_id()]++;
-  prioritized_tiles_dirty_ = true;
   return tile;
 }
 
@@ -1324,6 +1143,20 @@ TileManager::RasterTileIterator::RasterTileIterator(TileManager* tile_manager,
 
 TileManager::RasterTileIterator::~RasterTileIterator() {}
 
+bool TileManager::RasterTileIterator::HasTilesRequiredForActivation() const {
+  for (std::vector<PairedPictureLayerIterator*>::const_iterator it =
+           iterator_heap_.begin();
+       it != iterator_heap_.end();
+       ++it) {
+    const PairedPictureLayerIterator* pair = *it;
+
+    // Tiles required for activation can only come from pending layers.
+    if (pair->pending_iterator.HasTilesRequiredForActivation())
+      return true;
+  }
+  return false;
+}
+
 TileManager::RasterTileIterator& TileManager::RasterTileIterator::operator++() {
   DCHECK(*this);
 
@@ -1456,7 +1289,8 @@ bool TileManager::RasterTileIterator::RasterOrderComparator::operator()(
       b_tile->priority_for_tree_priority(tree_priority_);
   bool prioritize_low_res = tree_priority_ == SMOOTHNESS_TAKES_PRIORITY;
 
-  if (b_priority.resolution != a_priority.resolution) {
+  if (b_priority.priority_bin == a_priority.priority_bin &&
+      b_priority.resolution != a_priority.resolution) {
     return (prioritize_low_res && b_priority.resolution == LOW_RESOLUTION) ||
            (!prioritize_low_res && b_priority.resolution == HIGH_RESOLUTION) ||
            (a_priority.resolution == NON_IDEAL_RESOLUTION);
@@ -1466,15 +1300,24 @@ bool TileManager::RasterTileIterator::RasterOrderComparator::operator()(
 }
 
 TileManager::EvictionTileIterator::EvictionTileIterator()
-    : comparator_(SAME_PRIORITY_FOR_BOTH_TREES) {}
+    : initialized_(true),
+      tile_manager_(NULL),
+      comparator_(SAME_PRIORITY_FOR_BOTH_TREES) {
+}
 
 TileManager::EvictionTileIterator::EvictionTileIterator(
     TileManager* tile_manager,
     TreePriority tree_priority)
-    : tree_priority_(tree_priority), comparator_(tree_priority) {
+    : initialized_(false),
+      tile_manager_(tile_manager),
+      tree_priority_(tree_priority),
+      comparator_(tree_priority) {
+}
+
+void TileManager::EvictionTileIterator::Initialize() {
   std::vector<TileManager::PairedPictureLayer> paired_layers;
 
-  tile_manager->GetPairedPictureLayers(&paired_layers);
+  tile_manager_->GetPairedPictureLayers(&paired_layers);
 
   paired_iterators_.reserve(paired_layers.size());
   iterator_heap_.reserve(paired_layers.size());
@@ -1502,12 +1345,15 @@ TileManager::EvictionTileIterator::EvictionTileIterator(
   }
 
   std::make_heap(iterator_heap_.begin(), iterator_heap_.end(), comparator_);
+  initialized_ = true;
 }
 
 TileManager::EvictionTileIterator::~EvictionTileIterator() {}
 
 TileManager::EvictionTileIterator& TileManager::EvictionTileIterator::
 operator++() {
+  DCHECK(initialized_);
+
   std::pop_heap(iterator_heap_.begin(), iterator_heap_.end(), comparator_);
   PairedPictureLayerIterator* paired_iterator = iterator_heap_.back();
   iterator_heap_.pop_back();
@@ -1520,11 +1366,15 @@ operator++() {
   return *this;
 }
 
-TileManager::EvictionTileIterator::operator bool() const {
+TileManager::EvictionTileIterator::operator bool() {
+  if (!initialized_)
+    Initialize();
+
   return !iterator_heap_.empty();
 }
 
 Tile* TileManager::EvictionTileIterator::operator*() {
+  DCHECK(initialized_);
   DCHECK(*this);
   return iterator_heap_.front()->PeekTile(tree_priority_);
 }