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 f9fafbbca09b5943bf4a63a516f153181802e3c0..b8df7f32bd9e7ee4acb30c0bb4e572f127d343c7 100644
--- a/cc/resources/tile_manager.cc
+++ b/cc/resources/tile_manager.cc
@@ -246,113 +246,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) {
-  const float kBackflingGuardDistancePixels = 314.0f;
-
-  if (prio.priority_bin == TilePriority::NOW)
-    return NOW_BIN;
-
-  if (prio.priority_bin == TilePriority::SOON ||
-      prio.distance_to_visible < kBackflingGuardDistancePixels)
-    return SOON_BIN;
-
-  if (prio.distance_to_visible == std::numeric_limits<float>::infinity())
-    return NEVER_BIN;
-
-  return EVENTUALLY_BIN;
-}
-
 }  // namespace
 
 RasterTaskCompletionStats::RasterTaskCompletionStats()
@@ -394,11 +287,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),
       max_raster_usage_bytes_(max_raster_usage_bytes),
@@ -444,14 +334,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;
 }
@@ -485,17 +370,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");
 
@@ -512,8 +386,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.
@@ -563,136 +436,15 @@ 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::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;
+
+  // 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.
@@ -701,11 +453,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);
@@ -747,8 +496,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();

[reveman, 2014/04/28 19:39:18]

what's our plan for computing these properly?

[vmpstr, 2014/04/28 20:56:42]

That's a good question. There's no good way for us to know what is nice to have
at this point, short of either querying the iterators (like required for
activation is currently is in this patch), iterating the raster iterators all
the way to the end, or somehow asking layers for this information. Suggestions
are more than welcome.

For the required bytes, we can estimate the usage based on required for
activation counts, but it would not account for active layer visible tiles. 

[reveman, 2014/04/28 21:43:15]

The end result is that these values are used by the global gpu memory manager to
determine how much memory we should have. "Required for activation" is something
temporary and should probably not be used to determine any of these values.

I don't think the tile manager should be involved in this anymore. How about we
compute all this in UpdateTilePriorities to the best of our ability?
nice_to_have_bytes might be hard to compute accurately but we can probably
produce some number that is relevant to the current page..

[vmpstr, 2014/04/28 22:44:38]

Yeah that's the thing that always made me a bit hesitant: I'm not sure how exact
these values need to be. As it stands now, I can say how much memory is being
used and maybe if the next tile we didn't rasterize was prepaint or visible.
Would this be sufficient to just say nice to have is "currently used + some
buffer for what we know we still didn't do"? Or does this need to be more like
"currently used + number_of_tiles_left_to_do * tile_bytes for those tiles"?

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

Doesn't have to be precise. I don't think memory_required_bytes and
memory_nice_to_have_bytes should at all be based on how much we currently use
(initialized or with pending raster tasks).

   *memory_allocated_bytes = resource_pool_->total_memory_usage_bytes();
   *memory_used_bytes = resource_pool_->acquired_memory_usage_bytes();
 }
@@ -789,7 +538,6 @@ scoped_ptr<base::Value> TileManager::GetMemoryRequirementsAsValue() const {
 }
 
 void TileManager::AssignGpuMemoryToTiles(
-    PrioritizedTileSet* tiles,
     TileVector* tiles_that_need_to_be_rasterized) {
   TRACE_EVENT0("cc", "TileManager::AssignGpuMemoryToTiles");
 
@@ -807,27 +555,52 @@ void TileManager::AssignGpuMemoryToTiles(
 
   // Cast to prevent overflow.
   int64 soft_bytes_available =
-      static_cast<int64>(bytes_releasable_) +
       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_) +
       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 -
+  int resources_available = 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);
+
+  EvictionTileIterator eviction_it(this, global_state_.tree_priority);
+  bool evicted_tiles_required_for_activation = false;
+
+  // Evict resources if we're OOM before processing any tiles.
+  while (hard_bytes_available < 0 || resources_available < 0) {

[reveman, 2014/04/28 19:39:18]

can you fold this into the loop below instead of duplicating all the logic here?

[vmpstr, 2014/04/28 20:56:42]

It has to be outside of the loop since the raster tile iterator might return
false immediately meaning we don't enter the loop at all. I can try to make this
a separate function called here and in the loop, but the difference is that here
we unconditionally evict to get into the budget, whereas in the loop we evict as
long as the eviction tile priority is less than that of the raster tile.

The signature for the function would be something like the following:

// Returns true if evicted tiles required for activation
bool TileManager::EvictTiles(
    EvictionTileIterator* eviction_iterator,
    int64 extra_memory_needed,
    int extra_resources_needed,
    const TilePriority& raster_priority,
    bool evict_unconditionally);

with the logic being similar to this with something like the following:

if (!evict_unconditionally &&
    !raster_priority.IsHigherPriorityThan(eviction_priority))
  break;

Does that sound reasonable?

[reveman, 2014/04/28 21:43:15]

It's not clear to me why these eviction cases need to be considered different.
Maybe some pseudo code that describes the general process here would help. I'm
thinking that what we want here is something like the following but I'm probably
missing something:

RasterTileIterator raster_it = ..
EvictionTileIterator eviction_it = ..
do {
  bool needs_eviction = resources_available < 0 || ...

  if (needs_eviction) {
    if (!eviction_it)
      break;

    // Eviction code...
    ++eviction_it;
    continue;
  }

  // Assign gpu memory code...
  ++raster_it;
} while (raster_it);

[vmpstr, 2014/04/28 22:44:38]

I kind of reworked this a bit (I put the memory limits / budgets into a struct).
I like the solution I have right now, since it's fairly compact and easy to
reason about.

I don't like making the main loop here a do-while, because the first iteration
would basically just have "if (!raster_it) break" in the middle of it. That is,
in the cases where we don't have a single raster tile, we need to not run the
assign gpu memory code. This, to me, is a red flag that a do-while is not the
right approach...

+    if (!eviction_it)
+      break;
+
+    Tile* eviction_tile = *eviction_it;
+    const TilePriority& eviction_priority =
+        eviction_tile->priority_for_tree_priority(global_state_.tree_priority);
+    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_) {
+        hard_bytes_available += eviction_bytes_if_allocated;
+        if (eviction_priority.priority_bin != TilePriority::NOW)
+          soft_bytes_available += eviction_bytes_if_allocated;
+        resources_available++;
+      }
+    }
+    FreeResourcesForTile(eviction_tile);
+    ++eviction_it;
+
+    evicted_tiles_required_for_activation |=
+        eviction_tile->required_for_activation();
+  }
+
+  int64 soft_bytes_allocatable = soft_bytes_available;
+  int64 hard_bytes_allocatable = hard_bytes_available;
+  int resources_allocatable = resources_available;
 
   size_t bytes_that_exceeded_memory_budget = 0;
-  size_t soft_bytes_left = soft_bytes_allocatable;
-  size_t hard_bytes_left = hard_bytes_allocatable;
+  int64 soft_bytes_left = soft_bytes_allocatable;
+  int64 hard_bytes_left = hard_bytes_allocatable;
 
-  size_t resources_left = resources_allocatable;
+  int* resources_left = &resources_allocatable;
   bool oomed_soft = false;
   bool oomed_hard = false;
   bool have_hit_soft_memory = false;  // Soft memory comes after hard.
@@ -841,8 +614,31 @@ void TileManager::AssignGpuMemoryToTiles(
   size_t raster_bytes = 0;
 
   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;
+    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:
+      case NUM_TILE_MEMORY_LIMIT_POLICIES:
+        break;
+    }
+
+    if (tile_violates_memory_policy)
+      break;
+
     ManagedTileState& mts = tile->managed_state();
 
     mts.scheduled_priority = schedule_priority++;
@@ -852,21 +648,17 @@ 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 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 =
+        priority.priority_bin == TilePriority::NOW;
 
-    const bool tile_uses_hard_limit = mts.bin <= NOW_BIN;
     const size_t bytes_if_allocated = BytesConsumedIfAllocated(tile);
     const size_t raster_bytes_if_rastered = raster_bytes + bytes_if_allocated;
-    const size_t tile_bytes_left =
-        (tile_uses_hard_limit) ? hard_bytes_left : soft_bytes_left;
+    int64* 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
@@ -874,8 +666,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) {
@@ -885,22 +677,51 @@ 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.
-    if (raster_bytes_if_rastered <= max_raster_bytes) {
-      // 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) {
-      FreeResourcesForTile(tile);
+    // Handle OOM tiles.
+    while (tile_bytes > *tile_bytes_left || tile_resources > *resources_left) {
+      if (!eviction_it)
+        break;
+
+      Tile* eviction_tile = *eviction_it;
+      DCHECK(eviction_tile);
+
+      TilePriority eviction_priority =
+          eviction_tile->priority_for_tree_priority(
+              global_state_.tree_priority);
 
+      if (!priority.IsHigherPriorityThan(eviction_priority))
+        break;
+
+      size_t eviction_tile_bytes = 0;
+      size_t eviction_tile_resources = 0;
+      size_t eviction_bytes_if_allocated = BytesConsumedIfAllocated(tile);
+      ManagedTileState& eviction_mts = eviction_tile->managed_state();
+      for (int mode = 0; mode < NUM_RASTER_MODES; ++mode) {
+        if (eviction_mts.tile_versions[mode].resource_) {
+          eviction_tile_bytes += eviction_bytes_if_allocated;
+          eviction_tile_resources++;
+        }
+      }
+
+      FreeResourcesForTile(eviction_tile);
+      ++eviction_it;
+
+      evicted_tiles_required_for_activation |=
+          eviction_tile->required_for_activation();
+
+      *tile_bytes_left += eviction_tile_bytes;
+      *resources_left += eviction_tile_resources;
+    }
+
+    // Tile is still OOM.
+    if (tile_bytes > *tile_bytes_left || tile_resources > *resources_left) {
       // This tile was already on screen and now its resources have been
       // released. In order to prevent checkerboarding, set this tile as
       // rasterize on demand immediately.
@@ -913,7 +734,7 @@ void TileManager::AssignGpuMemoryToTiles(
         bytes_that_exceeded_memory_budget += tile_bytes;
       }
     } else {
-      resources_left -= tile_resources;
+      *resources_left -= tile_resources;
       hard_bytes_left -= tile_bytes;
       soft_bytes_left =
           (soft_bytes_left > tile_bytes) ? soft_bytes_left - tile_bytes : 0;
@@ -937,10 +758,10 @@ void TileManager::AssignGpuMemoryToTiles(
 
     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;
     }
 
     raster_bytes = raster_bytes_if_rastered;
@@ -1225,7 +1046,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;
 }
 
@@ -1322,8 +1142,43 @@ TileManager::RasterTileIterator::RasterTileIterator(TileManager* tile_manager,
   std::make_heap(iterator_heap_.begin(), iterator_heap_.end(), comparator_);
 }
 
+TileManager::RasterTileIterator::RasterTileIterator(
+    const RasterTileIterator& other)
+    : comparator_(other.comparator_) {
+  *this = other;
+}
+
+TileManager::RasterTileIterator& TileManager::RasterTileIterator::operator=(
+    const RasterTileIterator& other) {
+  paired_iterators_ = other.paired_iterators_;
+  tree_priority_ = other.tree_priority_;
+  comparator_ = other.comparator_;
+
+  iterator_heap_.reserve(paired_iterators_.size());
+  for (size_t i = 0; i < paired_iterators_.size(); ++i) {
+    if (paired_iterators_[i].PeekTile(tree_priority_) != NULL)
+      iterator_heap_.push_back(&paired_iterators_[i]);
+  }
+  std::make_heap(iterator_heap_.begin(), iterator_heap_.end(), comparator_);
+  return *this;
+}
+
 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 +1311,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 +1322,47 @@ 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(
+    const EvictionTileIterator& other)
+    : comparator_(other.comparator_) {
+  *this = other;
+}
+
+TileManager::EvictionTileIterator& TileManager::EvictionTileIterator::operator=(
+    const EvictionTileIterator& other) {
+  paired_iterators_ = other.paired_iterators_;
+  tree_priority_ = other.tree_priority_;
+  comparator_ = other.comparator_;
+  initialized_ = other.initialized_;
+  tile_manager_ = other.tile_manager_;
+
+  iterator_heap_.reserve(paired_iterators_.size());
+  for (size_t i = 0; i < paired_iterators_.size(); ++i) {
+    if (paired_iterators_[i].PeekTile(tree_priority_) != NULL)
+      iterator_heap_.push_back(&paired_iterators_[i]);
+  }
+  std::make_heap(iterator_heap_.begin(), iterator_heap_.end(), comparator_);
+  return *this;
+}
 
 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 +1390,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 +1411,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_);
 }