cc: Start using raster/eviction iterators.

cc/resources/tile_manager.cc

 // Copyright 2012 The Chromium Authors. All rights reserved.

[vmpstr, 2014/07/02 23:51:29]

Most changes here are a part of the original patch, with the exception of lazy
eviction iterators.

 // 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>
 
 #include "base/bind.h"
@@ skipping 208 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) {
-  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()
     : 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 17 matching lines @@
 TileManager::TileManager(
     TileManagerClient* client,
     base::SequencedTaskRunner* task_runner,
     ResourcePool* resource_pool,
     Rasterizer* rasterizer,
     RenderingStatsInstrumentation* rendering_stats_instrumentation)
     : client_(client),
       task_runner_(task_runner),
       resource_pool_(resource_pool),
       rasterizer_(rasterizer),
-      prioritized_tiles_dirty_(false),
-      all_tiles_that_need_to_be_rasterized_have_memory_(true),
-      all_tiles_required_for_activation_have_memory_(true),
-      bytes_releasable_(0),
-      resources_releasable_(0),
-      ever_exceeded_memory_budget_(false),
+      all_tiles_that_need_to_be_rasterized_are_scheduled_(true),
       rendering_stats_instrumentation_(rendering_stats_instrumentation),
       did_initialize_visible_tile_(false),
       did_check_for_completed_tasks_since_last_schedule_tasks_(true),
       ready_to_activate_check_notifier_(
           task_runner_,
           base::Bind(&TileManager::CheckIfReadyToActivate,
                      base::Unretained(this))) {
   rasterizer_->SetClient(this);
 }
 
 TileManager::~TileManager() {
   // Reset global state and manage. This should cause
   // our memory usage to drop to zero.
   global_state_ = GlobalStateThatImpactsTilePriority();
 
   CleanUpReleasedTiles();
   DCHECK_EQ(0u, tiles_.size());
 
   RasterTaskQueue empty;
   rasterizer_->ScheduleTasks(&empty);
   orphan_raster_tasks_.clear();
 
   // This should finish all pending tasks and release any uninitialized
   // resources.
   rasterizer_->Shutdown();
   rasterizer_->CheckForCompletedTasks();
-
-  DCHECK_EQ(0u, bytes_releasable_);
-  DCHECK_EQ(0u, resources_releasable_);
 }
 
 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_ &&
+  if (all_tiles_that_need_to_be_rasterized_are_scheduled_ &&
       !memory_usage_above_limit)
     return;
 
   rasterizer_->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 20 matching lines @@
       tile_version.set_rasterize_on_demand();
       client_->NotifyTileStateChanged(tile);
     }
   }
 
   DCHECK(IsReadyToActivate());
   ready_to_activate_check_notifier_.Schedule();
 }
 
 void TileManager::DidFinishRunningTasksRequiredForActivation() {
-  // This is only a true indication that all tiles required for
-  // 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;
-
   ready_to_activate_check_notifier_.Schedule();
 }
 
-void TileManager::GetTilesWithAssignedBins(PrioritizedTileSet* tiles) {
-  TRACE_EVENT0("cc", "TileManager::GetTilesWithAssignedBins");
-
-  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 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;
-
-    ManagedTileBin tree_bin[NUM_TREES];
-    tree_bin[ACTIVE_TREE] = kBinPolicyMap[memory_policy][active_bin];
-    tree_bin[PENDING_TREE] = kBinPolicyMap[memory_policy][pending_bin];
-
-    // 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)
-      tree_bin[PENDING_TREE] = std::max(tree_bin[PENDING_TREE], EVENTUALLY_BIN);
-
-    TilePriority tile_priority;
-    switch (tree_priority) {
-      case SAME_PRIORITY_FOR_BOTH_TREES:
-        mts.bin = std::min(tree_bin[ACTIVE_TREE], tree_bin[PENDING_TREE]);
-        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;
-
-    // Tiles that are required for activation shouldn't be in NEVER_BIN unless
-    // smoothness takes priority or memory policy allows nothing to be
-    // initialized.
-    DCHECK(!mts.required_for_activation || mts.bin != NEVER_BIN ||
-           tree_priority == SMOOTHNESS_TAKES_PRIORITY ||
-           memory_policy == ALLOW_NOTHING);
-
-    // 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_) {
-      FreeResourcesForTileAndNotifyClientIfTileWasReadyToDraw(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;
 
   // 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_->CheckForCompletedTasks();
     did_check_for_completed_tasks_since_last_schedule_tasks_ = true;
   }
 
-  UpdatePrioritizedTileSetIfNeeded();
+  // TODO(vmpstr): See if we still need to keep tiles alive when layers release
+  // them.
+  CleanUpReleasedTiles();
 
   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 32 matching lines @@
 }
 
 scoped_ptr<base::Value> TileManager::AllTilesAsValue() const {
   scoped_ptr<base::ListValue> state(new base::ListValue());
   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
     state->Append(it->second->AsValue().release());
 
   return state.PassAs<base::Value>();
 }
 
+bool TileManager::FreeTileResourcesUntilUsageIsWithinLimit(
+    EvictionTileIterator* iterator,
+    const MemoryUsage& limit,
+    MemoryUsage* usage) {
+  while (usage->Exceeds(limit)) {
+    if (!*iterator)
+      return false;
+
+    Tile* tile = **iterator;
+
+    *usage -= MemoryUsage::FromTile(tile);
+    FreeResourcesForTileAndNotifyClientIfTileWasReadyToDraw(tile);
+    ++(*iterator);
+  }
+  return true;
+}
+
+bool TileManager::FreeTileResourcesWithLowerPriorityUntilUsageIsWithinLimit(
+    EvictionTileIterator* iterator,
+    const MemoryUsage& limit,
+    const TilePriority& other_priority,
+    MemoryUsage* usage) {
+  while (usage->Exceeds(limit)) {
+    if (!*iterator)
+      return false;
+
+    Tile* tile = **iterator;
+    if (!other_priority.IsHigherPriorityThan(
+            tile->priority_for_tree_priority(global_state_.tree_priority))) {
+      return false;
+    }
+
+    *usage -= MemoryUsage::FromTile(tile);
+    FreeResourcesForTileAndNotifyClientIfTileWasReadyToDraw(tile);
+    ++(*iterator);
+  }
+  return true;
+}
+
+bool TileManager::TilePriorityViolatesMemoryPolicy(
+    const TilePriority& priority) {
+  switch (global_state_.memory_limit_policy) {
+    case ALLOW_NOTHING:
+      return true;
+    case ALLOW_ABSOLUTE_MINIMUM:
+      return priority.priority_bin > TilePriority::NOW;
+    case ALLOW_PREPAINT_ONLY:
+      return priority.priority_bin > TilePriority::SOON;
+    case ALLOW_ANYTHING:
+      return priority.distance_to_visible ==
+             std::numeric_limits<float>::infinity();
+  }
+  NOTREACHED();
+  return true;
+}
+
 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;
+  all_tiles_that_need_to_be_rasterized_are_scheduled_ = 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 -
-                            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);
+  MemoryUsage hard_memory_limit(global_state_.hard_memory_limit_in_bytes,
+                                global_state_.num_resources_limit);
+  MemoryUsage soft_memory_limit(global_state_.soft_memory_limit_in_bytes,
+                                global_state_.num_resources_limit);
+  MemoryUsage memory_usage(resource_pool_->acquired_memory_usage_bytes(),
+                           resource_pool_->acquired_resource_count());
 
-  size_t bytes_that_exceeded_memory_budget = 0;
-  size_t soft_bytes_left = soft_bytes_allocatable;
-  size_t hard_bytes_left = hard_bytes_allocatable;
+  EvictionTileIterator eviction_it(this, global_state_.tree_priority);
 
-  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.
+  bool had_enough_memory_to_schedule_tiles_needed_now = true;
 
   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);
+
+    if (TilePriorityViolatesMemoryPolicy(priority))
+      break;
+
+    // We won't be able to schedule this tile, so break out early.
+    if (tiles_that_need_to_be_rasterized->size() >=
+        kScheduledRasterTasksLimit) {
+      all_tiles_that_need_to_be_rasterized_are_scheduled_ = false;
+      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())
-      continue;
+    DCHECK(!tile_version.IsReadyToDraw());
 
-    // If the tile is not needed, free it up.
-    if (mts.bin == NEVER_BIN) {
-      FreeResourcesForTileAndNotifyClientIfTileWasReadyToDraw(tile);
-      continue;
+    // If the tile already has a raster_task, then the memory used by it is
+    // already accounted for in memory_usage. Otherwise, we'll have to acquire
+    // more memory to create a raster task.
+    MemoryUsage memory_required_by_tile_to_be_scheduled;
+    if (!tile_version.raster_task_) {
+      memory_required_by_tile_to_be_scheduled = MemoryUsage::FromConfig(
+          tile->size(), resource_pool_->resource_format());
     }
 
-    const bool tile_uses_hard_limit = mts.bin <= NOW_BIN;
-    const size_t bytes_if_allocated = BytesConsumedIfAllocated(tile);
-    const size_t tile_bytes_left =
-        (tile_uses_hard_limit) ? hard_bytes_left : soft_bytes_left;
+    bool tile_is_needed_now = priority.priority_bin == TilePriority::NOW;
 
-    // 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;
+    // This is the memory limit that will be used by this tile. Depending on
+    // the tile priority, it will be one of hard_memory_limit or
+    // soft_memory_limit.
+    MemoryUsage& tile_memory_limit =
+        tile_is_needed_now ? hard_memory_limit : soft_memory_limit;
 
-    size_t tile_bytes = 0;
-    size_t tile_resources = 0;
+    bool memory_usage_is_within_limit =
+        FreeTileResourcesWithLowerPriorityUntilUsageIsWithinLimit(
+            &eviction_it,
+            tile_memory_limit - memory_required_by_tile_to_be_scheduled,
+            priority,
+            &memory_usage);
 
-    // 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++;
-      }
+    // If we couldn't fit the tile into our current memory limit, then we're
+    // done.
+    if (!memory_usage_is_within_limit) {
+      if (tile_is_needed_now)
+        had_enough_memory_to_schedule_tiles_needed_now = false;
+      all_tiles_that_need_to_be_rasterized_are_scheduled_ = false;
+      break;
     }
 
-    // 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++;
-      }
-    }
-
-    // Tile is OOM.
-    if (tile_bytes > tile_bytes_left || tile_resources > resources_left) {
-      bool was_ready_to_draw = tile->IsReadyToDraw();
-
-      FreeResourcesForTile(tile);
-
-      // 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)
-        tile_version.set_rasterize_on_demand();
-
-      if (was_ready_to_draw)
-        client_->NotifyTileStateChanged(tile);
-
-      oomed_soft = true;
-      if (tile_uses_hard_limit) {
-        oomed_hard = true;
-        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;
-      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 && !reached_scheduled_raster_tasks_limit;
-
-    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;
-    }
-
+    memory_usage += memory_required_by_tile_to_be_scheduled;
     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",
-                      "over_memory_budget",
-                      this,
-                      "budget",
-                      global_state_.hard_memory_limit_in_bytes,
-                      "over",
-                      bytes_that_exceeded_memory_budget);
-  }
+  // Note that we should try and further reduce memory in case the above loop
+  // didn't reduce memory. This ensures that we always release as many resources
+  // as possible to stay within the memory limit.
+  FreeTileResourcesUntilUsageIsWithinLimit(
+      &eviction_it, hard_memory_limit, &memory_usage);
+
+  // Update memory_stats_from_last_assign_, which is used to display HUD
+  // information.
   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;
-  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;
+  memory_stats_from_last_assign_.total_bytes_used = memory_usage.memory_bytes();
+  memory_stats_from_last_assign_.had_enough_memory =
+      had_enough_memory_to_schedule_tiles_needed_now;
 }
 
 void TileManager::FreeResourceForTile(Tile* tile, RasterMode mode) {
   ManagedTileState& mts = tile->managed_state();
-  if (mts.tile_versions[mode].resource_) {
+  if (mts.tile_versions[mode].resource_)
     resource_pool_->ReleaseResource(mts.tile_versions[mode].resource_.Pass());
-
-    DCHECK_GE(bytes_releasable_, BytesConsumedIfAllocated(tile));
-    DCHECK_GE(resources_releasable_, 1u);
-
-    bytes_releasable_ -= BytesConsumedIfAllocated(tile);
-    --resources_releasable_;
-  }
 }
 
 void TileManager::FreeResourcesForTile(Tile* tile) {
   for (int mode = 0; mode < NUM_RASTER_MODES; ++mode) {
     FreeResourceForTile(tile, static_cast<RasterMode>(mode));
   }
 }
 
 void TileManager::FreeUnusedResourcesForTile(Tile* tile) {
   DCHECK(tile->IsReadyToDraw());
@@ skipping 181 matching lines @@
   }
 
   ++update_visible_tiles_stats_.completed_count;
 
   if (analysis.is_solid_color) {
     tile_version.set_solid_color(analysis.solid_color);
     resource_pool_->ReleaseResource(resource.Pass());
   } else {
     tile_version.set_use_resource();
     tile_version.resource_ = resource.Pass();
-
-    bytes_releasable_ += BytesConsumedIfAllocated(tile);
-    ++resources_releasable_;
   }
 
   FreeUnusedResourcesForTile(tile);
   if (tile->priority(ACTIVE_TREE).distance_to_visible == 0.f)
     did_initialize_visible_tile_ = true;
 
   client_->NotifyTileStateChanged(tile);
 }
 
 scoped_refptr<Tile> TileManager::CreateTile(PicturePileImpl* picture_pile,
@@ skipping 10 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::GetPairedPictureLayers(
     std::vector<PairedPictureLayer>* paired_layers) const {
   const std::vector<PictureLayerImpl*>& layers = client_->GetPictureLayers();
 
   paired_layers->clear();
   // Reserve a maximum possible paired layers.
   paired_layers->reserve(layers.size());
@@ skipping 225 matching lines @@
     if (prioritize_low_res)
       return b_priority.resolution == LOW_RESOLUTION;
 
     return b_priority.resolution == HIGH_RESOLUTION;
   }
 
   return b_priority.IsHigherPriorityThan(a_priority);
 }
 
 TileManager::EvictionTileIterator::EvictionTileIterator()
-    : comparator_(SAME_PRIORITY_FOR_BOTH_TREES) {}
+    : comparator_(SAME_PRIORITY_FOR_BOTH_TREES),
+      tile_manager_(NULL),
+      initialized_(true) {
+}
 
 TileManager::EvictionTileIterator::EvictionTileIterator(
     TileManager* tile_manager,
     TreePriority tree_priority)
-    : tree_priority_(tree_priority), comparator_(tree_priority) {
+    : tree_priority_(tree_priority),
+      comparator_(tree_priority),
+      tile_manager_(tile_manager),
+      initialized_(false) {
+}
+
+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++() {
+  if (!initialized_)

[enne (OOO), 2014/07/07 19:41:59]

Is this to avoid doing too much work in the constructor?

[vmpstr, 2014/07/07 23:24:47]

Yeah, this also ensures that we don't do any hard work if we remain within
memory budget.

+    Initialize();
+
   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();

[reveman, 2014/07/07 20:48:13]

This feels like the wrong approach.

Is the general problem that we're trying to implement iterators using a heap?
Are these iterators supposed to be priority queues instead? Implementing a
priority queue using a heap makes sense and that would allow you to only
re-build the heap when absolutely necessary. ie. when the top priority tile of a
layer has changed.

[vmpstr, 2014/07/07 23:24:47]

I buy that there are cases where this is unnecessary in that we will breach the
memory limit and initialize the iterator. At the same time though, there are
tons of examples where we always stay within the memory limit (note that we
still "evict" tiles by clipping all live tiles to the interest rect in the
tiling, so if all tiles fit within the interest rect budget, then we never
initialize the eviction iterator). This provides a substantial savings in terms
of time on "regular" pages, whatever that may mean. Without this approach, there
are only one option that I can think of and that is making eviction at the
tiling level super cheap. Without one of those two things, the iterators will
simply be too slow.

Maybe a prioritized tile set for tiling eviction? :P
The way that I use a heap here is really a priority queue. After making the
initial heap, I pop the top element, modify it (by consuming a tile), and
reinsert it back if it still has tiles. I think that's equivalent to priority
queue's top, pop, and push, no? Note that I think I can just change it to be the
actual std::priority_queue adapter if that would make it more readable?

[reveman, 2014/07/08 00:13:12]

I don't understand this comment. Is this still relevant if we go with the
priority queue approach discussed below?
 
Yes, it looks like the interface used for raster/eviction should be a priority
queue. And a heap is used to implement this interface. Maybe better to use your
own priority queue interface as "Push" doesn't have to be exposed to the
raster/eviction code.

+
   return !iterator_heap_.empty();
 }
 
 Tile* TileManager::EvictionTileIterator::operator*() {
+  if (!initialized_)
+    Initialize();
+
   DCHECK(*this);
   return iterator_heap_.front()->PeekTile(tree_priority_);
 }
 
 TileManager::EvictionTileIterator::PairedPictureLayerIterator::
     PairedPictureLayerIterator() {}
 
 TileManager::EvictionTileIterator::PairedPictureLayerIterator::
     ~PairedPictureLayerIterator() {}
 
@@ skipping 128 matching lines @@
 void TileManager::CheckIfReadyToActivate() {
   TRACE_EVENT0("cc", "TileManager::CheckIfReadyToActivate");
 
   rasterizer_->CheckForCompletedTasks();
   did_check_for_completed_tasks_since_last_schedule_tasks_ = true;
 
   if (IsReadyToActivate())
     client_->NotifyReadyToActivate();
 }
 
+TileManager::MemoryUsage::MemoryUsage() : memory_bytes_(0), resource_count_(0) {
+}
+
+TileManager::MemoryUsage::MemoryUsage(int64 memory_bytes, int resource_count)
+    : memory_bytes_(memory_bytes), resource_count_(resource_count) {
+}
+
+// static
+TileManager::MemoryUsage TileManager::MemoryUsage::FromConfig(
+    const gfx::Size& size,
+    ResourceFormat format) {
+  return MemoryUsage(Resource::MemorySizeBytes(size, format), 1);
+}
+
+// static
+TileManager::MemoryUsage TileManager::MemoryUsage::FromTile(const Tile* tile) {
+  const ManagedTileState& mts = tile->managed_state();
+  MemoryUsage total_usage;
+  for (int mode = 0; mode < NUM_RASTER_MODES; ++mode) {
+    if (mts.tile_versions[mode].resource_) {
+      total_usage += MemoryUsage::FromConfig(
+          tile->size(), mts.tile_versions[mode].resource_->format());
+    }
+  }
+  return total_usage;
+}
+
+TileManager::MemoryUsage& TileManager::MemoryUsage::operator+=(
+    const MemoryUsage& other) {
+  memory_bytes_ += other.memory_bytes_;
+  resource_count_ += other.resource_count_;
+  return *this;
+}
+
+TileManager::MemoryUsage& TileManager::MemoryUsage::operator-=(
+    const MemoryUsage& other) {
+  memory_bytes_ -= other.memory_bytes_;
+  resource_count_ -= other.resource_count_;
+  return *this;
+}
+
+TileManager::MemoryUsage TileManager::MemoryUsage::operator-(
+    const MemoryUsage& other) {
+  MemoryUsage result = *this;
+  result -= other;
+  return result;
+}
+
+bool TileManager::MemoryUsage::Exceeds(const MemoryUsage& limit) const {
+  return memory_bytes_ > limit.memory_bytes_ ||
+         resource_count_ > limit.resource_count_;
+}
+
 }  // namespace cc