cc: Start using raster/eviction iterators in tile manager

cc/resources/tile_manager.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/resources/tile_manager.h"
 
 #include <algorithm>
 #include <limits>
 #include <string>
 
@@ skipping 228 matching lines @@
   skia::RefPtr<SkPixelRef> pixel_ref_;
   int layer_id_;
   RenderingStatsInstrumentation* rendering_stats_;
   const base::Callback<void(bool was_canceled)> reply_;
 
   DISALLOW_COPY_AND_ASSIGN(ImageDecodeTaskImpl);
 };
 
 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()
     : completed_count(0u), canceled_count(0u) {}
 
 scoped_ptr<base::Value> RasterTaskCompletionStatsAsValue(
     const RasterTaskCompletionStats& stats) {
   scoped_ptr<base::DictionaryValue> state(new base::DictionaryValue());
   state->SetInteger("completed_count", stats.completed_count);
   state->SetInteger("canceled_count", stats.canceled_count);
@@ skipping 21 matching lines @@
 TileManager::TileManager(
     TileManagerClient* client,
     ResourcePool* resource_pool,
     Rasterizer* rasterizer,
     Rasterizer* gpu_rasterizer,
     size_t max_raster_usage_bytes,
     bool use_rasterize_on_demand,
     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),
       ever_exceeded_memory_budget_(false),
       rendering_stats_instrumentation_(rendering_stats_instrumentation),
       did_initialize_visible_tile_(false),
       did_check_for_completed_tasks_since_last_schedule_tasks_(true),
       use_rasterize_on_demand_(use_rasterize_on_demand) {
   Rasterizer* rasterizers[NUM_RASTERIZER_TYPES] = {
       rasterizer,      // RASTERIZER_TYPE_DEFAULT
@@ skipping 25 matching lines @@
 
   for (std::vector<PictureLayerImpl*>::iterator it = layers_.begin();
        it != layers_.end();
        ++it) {
     (*it)->DidUnregisterLayer();
   }
   layers_.clear();
 }
 
 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;
 }
 
 void TileManager::CleanUpReleasedTiles() {
   for (std::vector<Tile*>::iterator it = released_tiles_.begin();
        it != released_tiles_.end();
        ++it) {
     Tile* tile = *it;
     ManagedTileState& mts = tile->managed_state();
@@ skipping 13 matching lines @@
       used_layer_counts_.erase(layer_it);
       image_decode_tasks_.erase(tile->layer_id());
     }
 
     delete tile;
   }
 
   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");
 
   bool memory_usage_above_limit = resource_pool_->total_memory_usage_bytes() >
                                   global_state_.soft_memory_limit_in_bytes;
 
   // When OOM, keep re-assigning memory until we reach a steady state
   // where top-priority tiles are initialized.
   if (all_tiles_that_need_to_be_rasterized_have_memory_ &&
       !memory_usage_above_limit)
     return;
 
   rasterizer_delegate_->CheckForCompletedTasks();
   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.
   if (!tiles_that_need_to_be_rasterized.empty()) {
     ScheduleTasks(tiles_that_need_to_be_rasterized);
     return;
   }
 
   resource_pool_->ReduceResourceUsage();
 
@@ skipping 29 matching lines @@
   // activation are initialized when no tiles are OOM. We need to
   // wait for DidFinishRunningTasks() to be called, try to re-assign
   // memory and in worst case use on-demand raster when tiles
   // required for activation are OOM.
   if (!all_tiles_required_for_activation_have_memory_)
     return;
 
   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.
   if (!did_check_for_completed_tasks_since_last_schedule_tasks_) {
     rasterizer_delegate_->CheckForCompletedTasks();
     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);
 
   TRACE_EVENT_INSTANT1("cc",
                        "DidManage",
                        TRACE_EVENT_SCOPE_THREAD,
                        "state",
                        TracedValue::FromValue(BasicStateAsValue().release()));
 
@@ skipping 21 matching lines @@
 
   bool did_initialize_visible_tile = did_initialize_visible_tile_;
   did_initialize_visible_tile_ = false;
   return did_initialize_visible_tile;
 }
 
 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();
 }
 
 scoped_ptr<base::Value> TileManager::BasicStateAsValue() const {
   scoped_ptr<base::DictionaryValue> state(new base::DictionaryValue());
   state->SetInteger("tile_count", tiles_.size());
   state->Set("global_state", global_state_.AsValue().release());
   state->Set("memory_requirements", GetMemoryRequirementsAsValue().release());
   return state.PassAs<base::Value>();
@@ skipping 20 matching lines @@
                  &memory_used_bytes);
   requirements->SetInteger("memory_required_bytes", memory_required_bytes);
   requirements->SetInteger("memory_nice_to_have_bytes",
                            memory_nice_to_have_bytes);
   requirements->SetInteger("memory_allocated_bytes", memory_allocated_bytes);
   requirements->SetInteger("memory_used_bytes", memory_used_bytes);
   return requirements.PassAs<base::Value>();
 }
 
 void TileManager::AssignGpuMemoryToTiles(
-    PrioritizedTileSet* tiles,
     TileVector* tiles_that_need_to_be_rasterized) {
   TRACE_EVENT0("cc", "TileManager::AssignGpuMemoryToTiles");
 
   // Maintain the list of released resources that can potentially be re-used
   // or deleted.
   // If this operation becomes expensive too, only do this after some
   // resource(s) was returned. Note that in that case, one also need to
   // invalidate when releasing some resource from the pool.
   resource_pool_->CheckBusyResources();
 
   // Now give memory out to the tiles until we're out, and build
   // the needs-to-be-rasterized queue.
   all_tiles_that_need_to_be_rasterized_have_memory_ = true;
   all_tiles_required_for_activation_have_memory_ = true;
 
   // 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.
 
   // Memory we assign to raster tasks now will be deducted from our memory
   // in future iterations if priorities change. By assigning at most half
   // the raster limit, we will always have another 50% left even if priorities
   // change completely (assuming we check for completed/cancelled rasters
   // between each call to this function).
   size_t max_raster_bytes = max_raster_usage_bytes_ / 2;
   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++;
 
     mts.raster_mode = tile->DetermineOverallRasterMode();
 
     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
     // priority memory, and must be at the front of the list.
     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) {
       if (mts.tile_versions[mode].resource_) {
         tile_bytes += bytes_if_allocated;
         tile_resources++;
       }
     }
 
-    // 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.
       if (mts.visible_and_ready_to_draw && use_rasterize_on_demand_)
         tile_version.set_rasterize_on_demand();
 
       oomed_soft = true;
       if (tile_uses_hard_limit) {
         oomed_hard = true;
         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;
       if (tile_version.resource_)
         continue;
     }
 
     DCHECK(!tile_version.resource_);
 
     // Tile shouldn't be rasterized if |tiles_that_need_to_be_rasterized|
     // has reached it's limit or we've failed to assign gpu memory to this
     // or any higher priority tile. Preventing tiles that fit into memory
     // budget to be rasterized when higher priority tile is oom is
     // important for two reasons:
     // 1. Tile size should not impact raster priority.
     // 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 && raster_bytes_if_rastered <= max_raster_bytes &&
         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;
     }
 
     raster_bytes = raster_bytes_if_rastered;
     tiles_that_need_to_be_rasterized->push_back(tile);
   }
 
   // OOM reporting uses hard-limit, soft-OOM is normal depending on limit.
   ever_exceeded_memory_budget_ |= oomed_hard;
   if (ever_exceeded_memory_budget_) {
     TRACE_COUNTER_ID2("cc",
@@ skipping 264 matching lines @@
                                                          content_rect,
                                                          opaque_rect,
                                                          contents_scale,
                                                          layer_id,
                                                          source_frame_number,
                                                          flags));
   DCHECK(tiles_.find(tile->id()) == tiles_.end());
 
   tiles_[tile->id()] = tile;
   used_layer_counts_[tile->layer_id()]++;
-  prioritized_tiles_dirty_ = true;
   return tile;
 }
 
 void TileManager::RegisterPictureLayerImpl(PictureLayerImpl* layer) {
   DCHECK(std::find(layers_.begin(), layers_.end(), layer) == layers_.end());
   layers_.push_back(layer);
 }
 
 void TileManager::UnregisterPictureLayerImpl(PictureLayerImpl* layer) {
   std::vector<PictureLayerImpl*>::iterator it =
@@ skipping 76 matching lines @@
 
     if (paired_iterator.PeekTile(tree_priority_) != NULL) {
       paired_iterators_.push_back(paired_iterator);
       iterator_heap_.push_back(&paired_iterators_.back());
     }
   }
 
   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);
 
   std::pop_heap(iterator_heap_.begin(), iterator_heap_.end(), comparator_);
   PairedPictureLayerIterator* paired_iterator = iterator_heap_.back();
   iterator_heap_.pop_back();
 
   paired_iterator->PopTile(tree_priority_);
   if (paired_iterator->PeekTile(tree_priority_) != NULL) {
     iterator_heap_.push_back(paired_iterator);
@@ skipping 112 matching lines @@
 
   Tile* a_tile = **a_pair.first;
   Tile* b_tile = **b_pair.first;
 
   const TilePriority& a_priority =
       a_tile->priority_for_tree_priority(tree_priority_);
   const TilePriority& b_priority =
       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);
   }
 
   return b_priority.IsHigherPriorityThan(a_priority);
 }
 
 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());
   for (std::vector<TileManager::PairedPictureLayer>::iterator it =
            paired_layers.begin();
        it != paired_layers.end();
        ++it) {
     PairedPictureLayerIterator paired_iterator;
     if (it->active_layer) {
       paired_iterator.active_iterator =
           PictureLayerImpl::LayerEvictionTileIterator(it->active_layer,
                                                       tree_priority_);
     }
 
     if (it->pending_layer) {
       paired_iterator.pending_iterator =
           PictureLayerImpl::LayerEvictionTileIterator(it->pending_layer,
                                                       tree_priority_);
     }
 
     if (paired_iterator.PeekTile(tree_priority_) != NULL) {
       paired_iterators_.push_back(paired_iterator);
       iterator_heap_.push_back(&paired_iterators_.back());
     }
   }
 
   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();
 
   paired_iterator->PopTile(tree_priority_);
   if (paired_iterator->PeekTile(tree_priority_) != NULL) {
     iterator_heap_.push_back(paired_iterator);
     std::push_heap(iterator_heap_.begin(), iterator_heap_.end(), comparator_);
   }
   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_);
 }
 
 TileManager::EvictionTileIterator::PairedPictureLayerIterator::
     PairedPictureLayerIterator() {}
 
 TileManager::EvictionTileIterator::PairedPictureLayerIterator::
     ~PairedPictureLayerIterator() {}
 
@@ skipping 86 matching lines @@
 
   if (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);
   }
   return a_priority.IsHigherPriorityThan(b_priority);
 }
 
 }  // namespace cc