cc: TileManager eviction tile iterator.

This patch adds tile manager eviction tile iterator.

BUG=

Review URL: https://codereview.chromium.org/225183021

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@263358 0039d316-1c4b-4281-b951-d872f2087c98

11 files changed, 458 insertions, 75 deletions

diff --git a/cc/layers/picture_layer_impl.cc b/cc/layers/picture_layer_impl.cc
index 7dac994..4f2491f 100644
--- a/cc/layers/picture_layer_impl.cc
+++ b/cc/layers/picture_layer_impl.cc
@@ -1393,7 +1393,8 @@ PictureLayerImpl::LayerEvictionTileIterator::LayerEvictionTileIterator()
       layer_(NULL) {}
 
 PictureLayerImpl::LayerEvictionTileIterator::LayerEvictionTileIterator(
-    PictureLayerImpl* layer)
+    PictureLayerImpl* layer,
+    TreePriority tree_priority)
     : iterator_index_(0),
       iteration_stage_(TilePriority::EVENTUALLY),
       required_for_activation_(false),
@@ -1401,9 +1402,6 @@ PictureLayerImpl::LayerEvictionTileIterator::LayerEvictionTileIterator(
   if (!layer_->tilings_ || !layer_->tilings_->num_tilings())
     return;
 
-  WhichTree tree =
-      layer_->layer_tree_impl()->IsActiveTree() ? ACTIVE_TREE : PENDING_TREE;
-
   size_t high_res_tiling_index = layer_->tilings_->num_tilings();
   size_t low_res_tiling_index = layer_->tilings_->num_tilings();
   for (size_t i = 0; i < layer_->tilings_->num_tilings(); ++i) {
@@ -1419,7 +1417,7 @@ PictureLayerImpl::LayerEvictionTileIterator::LayerEvictionTileIterator(
   // Higher resolution non-ideal goes first.
   for (size_t i = 0; i < high_res_tiling_index; ++i) {
     iterators_.push_back(PictureLayerTiling::TilingEvictionTileIterator(
-        layer_->tilings_->tiling_at(i), tree));
+        layer_->tilings_->tiling_at(i), tree_priority));
   }
 
   // Lower resolution non-ideal goes next.
@@ -1431,19 +1429,19 @@ PictureLayerImpl::LayerEvictionTileIterator::LayerEvictionTileIterator(
       continue;
 
     iterators_.push_back(
-        PictureLayerTiling::TilingEvictionTileIterator(tiling, tree));
+        PictureLayerTiling::TilingEvictionTileIterator(tiling, tree_priority));
   }
 
   // Now, put the low res tiling if we have one.
   if (low_res_tiling_index < layer_->tilings_->num_tilings()) {
     iterators_.push_back(PictureLayerTiling::TilingEvictionTileIterator(
-        layer_->tilings_->tiling_at(low_res_tiling_index), tree));
+        layer_->tilings_->tiling_at(low_res_tiling_index), tree_priority));
   }
 
   // Finally, put the high res tiling if we have one.
   if (high_res_tiling_index < layer_->tilings_->num_tilings()) {
     iterators_.push_back(PictureLayerTiling::TilingEvictionTileIterator(
-        layer_->tilings_->tiling_at(high_res_tiling_index), tree));
+        layer_->tilings_->tiling_at(high_res_tiling_index), tree_priority));
   }
 
   DCHECK_GT(iterators_.size(), 0u);
diff --git a/cc/layers/picture_layer_impl.h b/cc/layers/picture_layer_impl.h
index dc171fc..dcaee12 100644
--- a/cc/layers/picture_layer_impl.h
+++ b/cc/layers/picture_layer_impl.h
@@ -58,7 +58,8 @@ class CC_EXPORT PictureLayerImpl
   class CC_EXPORT LayerEvictionTileIterator {
    public:
     LayerEvictionTileIterator();
-    explicit LayerEvictionTileIterator(PictureLayerImpl* layer);
+    LayerEvictionTileIterator(PictureLayerImpl* layer,
+                              TreePriority tree_priority);
     ~LayerEvictionTileIterator();
 
     Tile* operator*();
diff --git a/cc/layers/picture_layer_impl_unittest.cc b/cc/layers/picture_layer_impl_unittest.cc
index 15a439c..b5ac6f1 100644
--- a/cc/layers/picture_layer_impl_unittest.cc
+++ b/cc/layers/picture_layer_impl_unittest.cc
@@ -2068,7 +2068,8 @@ TEST_F(PictureLayerImplTest, LayerEvictionTileIterator) {
   EXPECT_FALSE(it);
 
   // Tiles don't have resources yet.
-  it = PictureLayerImpl::LayerEvictionTileIterator(pending_layer_);
+  it = PictureLayerImpl::LayerEvictionTileIterator(
+      pending_layer_, SAME_PRIORITY_FOR_BOTH_TREES);
   EXPECT_FALSE(it);
 
   host_impl_.tile_manager()->InitializeTilesWithResourcesForTesting(all_tiles);
@@ -2079,7 +2080,9 @@ TEST_F(PictureLayerImplTest, LayerEvictionTileIterator) {
   bool reached_visible = false;
   bool reached_required = false;
   Tile* last_tile = NULL;
-  for (it = PictureLayerImpl::LayerEvictionTileIterator(pending_layer_); it;
+  for (it = PictureLayerImpl::LayerEvictionTileIterator(
+           pending_layer_, SAME_PRIORITY_FOR_BOTH_TREES);
+       it;
        ++it) {
     Tile* tile = *it;
     if (!last_tile)
diff --git a/cc/resources/picture_layer_tiling.cc b/cc/resources/picture_layer_tiling.cc
index 955c097..26e27da 100644
--- a/cc/resources/picture_layer_tiling.cc
+++ b/cc/resources/picture_layer_tiling.cc
@@ -22,12 +22,15 @@ namespace {
 
 class TileEvictionOrder {
  public:
-  explicit TileEvictionOrder(WhichTree tree) : tree_(tree) {}
+  explicit TileEvictionOrder(TreePriority tree_priority)
+      : tree_priority_(tree_priority) {}
   ~TileEvictionOrder() {}
 
   bool operator()(const Tile* a, const Tile* b) {
-    const TilePriority& a_priority = a->priority(tree_);
-    const TilePriority& b_priority = b->priority(tree_);
+    const TilePriority& a_priority =
+        a->priority_for_tree_priority(tree_priority_);
+    const TilePriority& b_priority =
+        b->priority_for_tree_priority(tree_priority_);
 
     if (a_priority.priority_bin == b_priority.priority_bin &&
         a->required_for_activation() != b->required_for_activation()) {
@@ -37,7 +40,7 @@ class TileEvictionOrder {
   }
 
  private:
-  WhichTree tree_;
+  TreePriority tree_priority_;
 };
 }  // namespace
 
@@ -59,7 +62,8 @@ PictureLayerTiling::PictureLayerTiling(float contents_scale,
       client_(client),
       tiling_data_(gfx::Size(), gfx::Size(), true),
       last_impl_frame_time_in_seconds_(0.0),
-      eviction_tiles_cache_valid_(false) {
+      eviction_tiles_cache_valid_(false),
+      eviction_cache_tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES) {
   gfx::Size content_bounds =
       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
@@ -768,8 +772,10 @@ gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
   return result;
 }
 
-void PictureLayerTiling::UpdateEvictionCacheIfNeeded(WhichTree tree) {
-  if (eviction_tiles_cache_valid_)
+void PictureLayerTiling::UpdateEvictionCacheIfNeeded(
+    TreePriority tree_priority) {
+  if (eviction_tiles_cache_valid_ &&
+      eviction_cache_tree_priority_ == tree_priority)
     return;
 
   eviction_tiles_cache_.clear();
@@ -782,8 +788,9 @@ void PictureLayerTiling::UpdateEvictionCacheIfNeeded(WhichTree tree) {
 
   std::sort(eviction_tiles_cache_.begin(),
             eviction_tiles_cache_.end(),
-            TileEvictionOrder(tree));
+            TileEvictionOrder(tree_priority));
   eviction_tiles_cache_valid_ = true;
+  eviction_cache_tree_priority_ = tree_priority;
 }
 
 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator()
@@ -886,8 +893,8 @@ PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator()
 
 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator(
     PictureLayerTiling* tiling,
-    WhichTree tree)
-    : is_valid_(false), tiling_(tiling), tree_(tree) {}
+    TreePriority tree_priority)
+    : is_valid_(false), tiling_(tiling), tree_priority_(tree_priority) {}
 
 PictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() {}
 
@@ -922,7 +929,7 @@ void PictureLayerTiling::TilingEvictionTileIterator::Initialize() {
   if (!tiling_)
     return;
 
-  tiling_->UpdateEvictionCacheIfNeeded(tree_);
+  tiling_->UpdateEvictionCacheIfNeeded(tree_priority_);
   tile_iterator_ = tiling_->eviction_tiles_cache_.begin();
   is_valid_ = true;
   if (tile_iterator_ != tiling_->eviction_tiles_cache_.end() &&
diff --git a/cc/resources/picture_layer_tiling.h b/cc/resources/picture_layer_tiling.h
index fe6fb7d..bd442de 100644
--- a/cc/resources/picture_layer_tiling.h
+++ b/cc/resources/picture_layer_tiling.h
@@ -92,7 +92,8 @@ class CC_EXPORT PictureLayerTiling {
   class CC_EXPORT TilingEvictionTileIterator {
    public:
     TilingEvictionTileIterator();
-    TilingEvictionTileIterator(PictureLayerTiling* tiling, WhichTree tree);
+    TilingEvictionTileIterator(PictureLayerTiling* tiling,
+                               TreePriority tree_priority);
     ~TilingEvictionTileIterator();
 
     operator bool();
@@ -100,7 +101,9 @@ class CC_EXPORT PictureLayerTiling {
     TilingEvictionTileIterator& operator++();
     TilePriority::PriorityBin get_type() {
       DCHECK(*this);
-      return (*tile_iterator_)->priority(tree_).priority_bin;
+      const TilePriority& priority =
+          (*tile_iterator_)->priority_for_tree_priority(tree_priority_);
+      return priority.priority_bin;
     }
 
    private:
@@ -109,7 +112,7 @@ class CC_EXPORT PictureLayerTiling {
 
     bool is_valid_;
     PictureLayerTiling* tiling_;
-    WhichTree tree_;
+    TreePriority tree_priority_;
     std::vector<Tile*>::iterator tile_iterator_;
   };
 
@@ -276,7 +279,7 @@ class CC_EXPORT PictureLayerTiling {
                             const gfx::Rect& visible_rect_in_content_space)
       const;
 
-  void UpdateEvictionCacheIfNeeded(WhichTree tree);
+  void UpdateEvictionCacheIfNeeded(TreePriority tree_priority);
   void DoInvalidate(const Region& layer_region, bool recreate_tiles);
 
   // Given properties.
@@ -300,6 +303,7 @@ class CC_EXPORT PictureLayerTiling {
 
   std::vector<Tile*> eviction_tiles_cache_;
   bool eviction_tiles_cache_valid_;
+  TreePriority eviction_cache_tree_priority_;
 
  private:
   DISALLOW_ASSIGN(PictureLayerTiling);
diff --git a/cc/resources/picture_layer_tiling_unittest.cc b/cc/resources/picture_layer_tiling_unittest.cc
index 46e6dcc..16b68c1 100644
--- a/cc/resources/picture_layer_tiling_unittest.cc
+++ b/cc/resources/picture_layer_tiling_unittest.cc
@@ -949,7 +949,8 @@ TEST(PictureLayerTilingTest, TilingEvictionTileIteratorStaticViewport) {
 
   std::vector<Tile*> all_tiles = tiling->AllTilesForTesting();
 
-  PictureLayerTiling::TilingEvictionTileIterator it(tiling.get(), ACTIVE_TREE);
+  PictureLayerTiling::TilingEvictionTileIterator it(tiling.get(),
+                                                    SMOOTHNESS_TAKES_PRIORITY);
 
   // Tiles don't have resources to evict.
   EXPECT_FALSE(it);
@@ -961,8 +962,8 @@ TEST(PictureLayerTilingTest, TilingEvictionTileIteratorStaticViewport) {
 
   std::set<Tile*> all_tiles_set(all_tiles.begin(), all_tiles.end());
 
-  it =
-      PictureLayerTiling::TilingEvictionTileIterator(tiling.get(), ACTIVE_TREE);
+  it = PictureLayerTiling::TilingEvictionTileIterator(
+      tiling.get(), SMOOTHNESS_TAKES_PRIORITY);
   EXPECT_TRUE(it);
 
   std::set<Tile*> eviction_tiles;
diff --git a/cc/resources/tile.cc b/cc/resources/tile.cc
index 65a1738..f976cfe 100644
--- a/cc/resources/tile.cc
+++ b/cc/resources/tile.cc
@@ -24,16 +24,16 @@ Tile::Tile(TileManager* tile_manager,
            int layer_id,
            int source_frame_number,
            int flags)
-  : RefCountedManaged<Tile>(tile_manager),
-    tile_manager_(tile_manager),
-    tile_size_(tile_size),
-    content_rect_(content_rect),
-    contents_scale_(contents_scale),
-    opaque_rect_(opaque_rect),
-    layer_id_(layer_id),
-    source_frame_number_(source_frame_number),
-    flags_(flags),
-    id_(s_next_id_++) {
+    : RefCountedManaged<Tile>(tile_manager),
+      tile_manager_(tile_manager),
+      tile_size_(tile_size),
+      content_rect_(content_rect),
+      contents_scale_(contents_scale),
+      opaque_rect_(opaque_rect),
+      layer_id_(layer_id),
+      source_frame_number_(source_frame_number),
+      flags_(flags),
+      id_(s_next_id_++) {
   set_picture_pile(picture_pile);
 }
 
diff --git a/cc/resources/tile.h b/cc/resources/tile.h
index 7df43e0..a1e1c35 100644
--- a/cc/resources/tile.h
+++ b/cc/resources/tile.h
@@ -43,6 +43,19 @@ class CC_EXPORT Tile : public RefCountedManaged<Tile> {
     return priority_[tree];
   }
 
+  TilePriority priority_for_tree_priority(TreePriority tree_priority) const {
+    switch (tree_priority) {
+      case SMOOTHNESS_TAKES_PRIORITY:
+        return priority_[ACTIVE_TREE];
+      case NEW_CONTENT_TAKES_PRIORITY:
+        return priority_[PENDING_TREE];
+      case SAME_PRIORITY_FOR_BOTH_TREES:
+        return combined_priority();
+    }
+    NOTREACHED();
+    return TilePriority();
+  }
+
   TilePriority combined_priority() const {
     return TilePriority(priority_[ACTIVE_TREE],
                         priority_[PENDING_TREE]);
diff --git a/cc/resources/tile_manager.cc b/cc/resources/tile_manager.cc
index 494453e..16b8a3d 100644
--- a/cc/resources/tile_manager.cc
+++ b/cc/resources/tile_manager.cc
@@ -1289,10 +1289,8 @@ void TileManager::GetPairedPictureLayers(
        ++it) {
     PictureLayerImpl* layer = *it;
 
-    // This is a recycle tree layer, so it shouldn't be included in the raster
-    // tile generation.
-    // TODO(vmpstr): We need these layers for eviction, so they should probably
-    // go into a separate vector as an output.
+    // This is a recycle tree layer, we can safely skip since the tiles on this
+    // layer have to be accessible via the active tree.
     if (!layer->IsOnActiveOrPendingTree())
       continue;
 
@@ -1473,19 +1471,6 @@ TileManager::RasterTileIterator::RasterOrderComparator::RasterOrderComparator(
     TreePriority tree_priority)
     : tree_priority_(tree_priority) {}
 
-bool TileManager::RasterTileIterator::RasterOrderComparator::ComparePriorities(
-    const TilePriority& a_priority,
-    const TilePriority& b_priority,
-    bool prioritize_low_res) const {
-  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 b_priority.IsHigherPriorityThan(a_priority);
-}
-
 bool TileManager::RasterTileIterator::RasterOrderComparator::operator()(
     PairedPictureLayerIterator* a,
     PairedPictureLayerIterator* b) const {
@@ -1502,24 +1487,184 @@ bool TileManager::RasterTileIterator::RasterOrderComparator::operator()(
   Tile* a_tile = **a_pair.first;
   Tile* b_tile = **b_pair.first;
 
-  switch (tree_priority_) {
-    case SMOOTHNESS_TAKES_PRIORITY:
-      return ComparePriorities(a_tile->priority(ACTIVE_TREE),
-                               b_tile->priority(ACTIVE_TREE),
-                               true /* prioritize low res */);
-    case NEW_CONTENT_TAKES_PRIORITY:
-      return ComparePriorities(a_tile->priority(PENDING_TREE),
-                               b_tile->priority(PENDING_TREE),
-                               false /* prioritize low res */);
-    case SAME_PRIORITY_FOR_BOTH_TREES:
-      return ComparePriorities(a_tile->priority(a_pair.second),
-                               b_tile->priority(b_pair.second),
-                               false /* prioritize low res */);
+  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) {
+    return (prioritize_low_res && b_priority.resolution == LOW_RESOLUTION) ||
+           (!prioritize_low_res && b_priority.resolution == HIGH_RESOLUTION) ||
+           (a_priority.resolution == NON_IDEAL_RESOLUTION);
   }
 
-  NOTREACHED();
-  // Keep the compiler happy.
-  return false;
+  return b_priority.IsHigherPriorityThan(a_priority);
+}
+
+TileManager::EvictionTileIterator::EvictionTileIterator()
+    : comparator_(SAME_PRIORITY_FOR_BOTH_TREES) {}
+
+TileManager::EvictionTileIterator::EvictionTileIterator(
+    TileManager* tile_manager,
+    TreePriority tree_priority)
+    : tree_priority_(tree_priority), comparator_(tree_priority) {
+  std::vector<TileManager::PairedPictureLayer> 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_);
+}
+
+TileManager::EvictionTileIterator::~EvictionTileIterator() {}
+
+TileManager::EvictionTileIterator& TileManager::EvictionTileIterator::
+operator++() {
+  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 {
+  return !iterator_heap_.empty();
+}
+
+Tile* TileManager::EvictionTileIterator::operator*() {
+  DCHECK(*this);
+  return iterator_heap_.front()->PeekTile(tree_priority_);
+}
+
+TileManager::EvictionTileIterator::PairedPictureLayerIterator::
+    PairedPictureLayerIterator() {}
+
+TileManager::EvictionTileIterator::PairedPictureLayerIterator::
+    ~PairedPictureLayerIterator() {}
+
+Tile* TileManager::EvictionTileIterator::PairedPictureLayerIterator::PeekTile(
+    TreePriority tree_priority) {
+  PictureLayerImpl::LayerEvictionTileIterator* next_iterator =
+      NextTileIterator(tree_priority);
+  if (!next_iterator)
+    return NULL;
+
+  DCHECK(*next_iterator);
+  DCHECK(std::find(returned_shared_tiles.begin(),
+                   returned_shared_tiles.end(),
+                   **next_iterator) == returned_shared_tiles.end());
+  return **next_iterator;
+}
+
+void TileManager::EvictionTileIterator::PairedPictureLayerIterator::PopTile(
+    TreePriority tree_priority) {
+  PictureLayerImpl::LayerEvictionTileIterator* next_iterator =
+      NextTileIterator(tree_priority);
+  DCHECK(next_iterator);
+  DCHECK(*next_iterator);
+  returned_shared_tiles.push_back(**next_iterator);
+  ++(*next_iterator);
+
+  next_iterator = NextTileIterator(tree_priority);
+  while (next_iterator &&
+         std::find(returned_shared_tiles.begin(),
+                   returned_shared_tiles.end(),
+                   **next_iterator) != returned_shared_tiles.end()) {
+    ++(*next_iterator);
+    next_iterator = NextTileIterator(tree_priority);
+  }
+}
+
+PictureLayerImpl::LayerEvictionTileIterator*
+TileManager::EvictionTileIterator::PairedPictureLayerIterator::NextTileIterator(
+    TreePriority tree_priority) {
+  // If both iterators are out of tiles, return NULL.
+  if (!active_iterator && !pending_iterator)
+    return NULL;
+
+  // If we only have one iterator with tiles, return it.
+  if (!active_iterator)
+    return &pending_iterator;
+  if (!pending_iterator)
+    return &active_iterator;
+
+  Tile* active_tile = *active_iterator;
+  Tile* pending_tile = *pending_iterator;
+  if (active_tile == pending_tile)
+    return &active_iterator;
+
+  const TilePriority& active_priority =
+      active_tile->priority_for_tree_priority(tree_priority);
+  const TilePriority& pending_priority =
+      pending_tile->priority_for_tree_priority(tree_priority);
+
+  if (pending_priority.IsHigherPriorityThan(active_priority))
+    return &active_iterator;
+  return &pending_iterator;
+}
+
+TileManager::EvictionTileIterator::EvictionOrderComparator::
+    EvictionOrderComparator(TreePriority tree_priority)
+    : tree_priority_(tree_priority) {}
+
+bool TileManager::EvictionTileIterator::EvictionOrderComparator::operator()(
+    PairedPictureLayerIterator* a,
+    PairedPictureLayerIterator* b) const {
+  PictureLayerImpl::LayerEvictionTileIterator* a_iterator =
+      a->NextTileIterator(tree_priority_);
+  DCHECK(a_iterator);
+  DCHECK(*a_iterator);
+
+  PictureLayerImpl::LayerEvictionTileIterator* b_iterator =
+      b->NextTileIterator(tree_priority_);
+  DCHECK(b_iterator);
+  DCHECK(*b_iterator);
+
+  Tile* a_tile = **a_iterator;
+  Tile* b_tile = **b_iterator;
+
+  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) {
+    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
diff --git a/cc/resources/tile_manager.h b/cc/resources/tile_manager.h
index ab937bf..60e6374 100644
--- a/cc/resources/tile_manager.h
+++ b/cc/resources/tile_manager.h
@@ -5,6 +5,7 @@
 #ifndef CC_RESOURCES_TILE_MANAGER_H_
 #define CC_RESOURCES_TILE_MANAGER_H_
 
+#include <deque>
 #include <queue>
 #include <set>
 #include <utility>
@@ -94,9 +95,6 @@ class CC_EXPORT TileManager : public RasterizerClient,
                       PairedPictureLayerIterator* b) const;
 
      private:
-      bool ComparePriorities(const TilePriority& a_priority,
-                             const TilePriority& b_priority,
-                             bool prioritize_low_res) const;
       TreePriority tree_priority_;
     };
 
@@ -106,6 +104,50 @@ class CC_EXPORT TileManager : public RasterizerClient,
     RasterOrderComparator comparator_;
   };
 
+  struct CC_EXPORT EvictionTileIterator {
+   public:
+    EvictionTileIterator();
+    EvictionTileIterator(TileManager* tile_manager, TreePriority tree_priority);
+    ~EvictionTileIterator();
+
+    EvictionTileIterator& operator++();
+    operator bool() const;
+    Tile* operator*();
+
+   private:
+    struct PairedPictureLayerIterator {
+      PairedPictureLayerIterator();
+      ~PairedPictureLayerIterator();
+
+      Tile* PeekTile(TreePriority tree_priority);
+      void PopTile(TreePriority tree_priority);
+
+      PictureLayerImpl::LayerEvictionTileIterator* NextTileIterator(
+          TreePriority tree_priority);
+
+      PictureLayerImpl::LayerEvictionTileIterator active_iterator;
+      PictureLayerImpl::LayerEvictionTileIterator pending_iterator;
+
+      std::vector<Tile*> returned_shared_tiles;
+    };
+
+    class EvictionOrderComparator {
+     public:
+      explicit EvictionOrderComparator(TreePriority tree_priority);
+
+      bool operator()(PairedPictureLayerIterator* a,
+                      PairedPictureLayerIterator* b) const;
+
+     private:
+      TreePriority tree_priority_;
+    };
+
+    std::vector<PairedPictureLayerIterator> paired_iterators_;
+    std::vector<PairedPictureLayerIterator*> iterator_heap_;
+    TreePriority tree_priority_;
+    EvictionOrderComparator comparator_;
+  };
+
   static scoped_ptr<TileManager> Create(
       TileManagerClient* client,
       ResourceProvider* resource_provider,
@@ -161,6 +203,15 @@ class CC_EXPORT TileManager : public RasterizerClient,
     }
   }
 
+  void ReleaseTileResourcesForTesting(const std::vector<Tile*>& tiles) {
+    for (size_t i = 0; i < tiles.size(); ++i) {
+      Tile* tile = tiles[i];
+      for (int mode = 0; mode < NUM_RASTER_MODES; ++mode) {
+        FreeResourceForTile(tile, static_cast<RasterMode>(mode));
+      }
+    }
+  }
+
   void SetGlobalStateForTesting(
       const GlobalStateThatImpactsTilePriority& state) {
     // Soft limit is used for resource pool such that
diff --git a/cc/resources/tile_manager_unittest.cc b/cc/resources/tile_manager_unittest.cc
index 849f4a7..1fac2b4 100644
--- a/cc/resources/tile_manager_unittest.cc
+++ b/cc/resources/tile_manager_unittest.cc
@@ -971,5 +971,165 @@ TEST_F(TileManagerTileIteratorTest, RasterTileIterator) {
   EXPECT_GT(increasing_distance_tiles, 3 * tile_count / 4);
 }
 
+TEST_F(TileManagerTileIteratorTest, EvictionTileIterator) {
+  SetupDefaultTrees(gfx::Size(1000, 1000));
+  TileManager* tile_manager = TileManagerTileIteratorTest::tile_manager();
+  EXPECT_TRUE(tile_manager);
+
+  active_layer_->CreateDefaultTilingsAndTiles();
+  pending_layer_->CreateDefaultTilingsAndTiles();
+
+  std::vector<TileManager::PairedPictureLayer> paired_layers;
+  tile_manager->GetPairedPictureLayers(&paired_layers);
+  EXPECT_EQ(1u, paired_layers.size());
+
+  TileManager::EvictionTileIterator it(tile_manager,
+                                       SAME_PRIORITY_FOR_BOTH_TREES);
+  EXPECT_FALSE(it);
+  std::set<Tile*> all_tiles;
+  size_t tile_count = 0;
+
+  for (TileManager::RasterTileIterator raster_it(tile_manager,
+                                                 SAME_PRIORITY_FOR_BOTH_TREES);
+       raster_it;
+       ++raster_it) {
+    ++tile_count;
+    EXPECT_TRUE(*raster_it);
+    all_tiles.insert(*raster_it);
+  }
+
+  EXPECT_EQ(tile_count, all_tiles.size());
+  EXPECT_EQ(17u, tile_count);
+
+  tile_manager->InitializeTilesWithResourcesForTesting(
+      std::vector<Tile*>(all_tiles.begin(), all_tiles.end()));
+
+  it = TileManager::EvictionTileIterator(tile_manager,
+                                         SAME_PRIORITY_FOR_BOTH_TREES);
+  EXPECT_TRUE(it);
+
+  // Sanity check, all tiles should be visible.
+  std::set<Tile*> smoothness_tiles;
+  for (TileManager::EvictionTileIterator it(tile_manager,
+                                            SMOOTHNESS_TAKES_PRIORITY);
+       it;
+       ++it) {
+    Tile* tile = *it;
+    EXPECT_TRUE(tile);
+    EXPECT_EQ(TilePriority::NOW, tile->priority(ACTIVE_TREE).priority_bin);
+    EXPECT_EQ(TilePriority::NOW, tile->priority(PENDING_TREE).priority_bin);
+    EXPECT_TRUE(tile->HasResources());
+    smoothness_tiles.insert(tile);
+  }
+  EXPECT_EQ(all_tiles, smoothness_tiles);
+
+  tile_manager->ReleaseTileResourcesForTesting(
+      std::vector<Tile*>(all_tiles.begin(), all_tiles.end()));
+
+  Region invalidation(gfx::Rect(0, 0, 500, 500));
+
+  // Invalidate the pending tree.
+  pending_layer_->set_invalidation(invalidation);
+  pending_layer_->HighResTiling()->Invalidate(invalidation);
+  pending_layer_->LowResTiling()->Invalidate(invalidation);
+
+  active_layer_->ResetAllTilesPriorities();
+  pending_layer_->ResetAllTilesPriorities();
+
+  // Renew all of the tile priorities.
+  gfx::Rect viewport(50, 50, 100, 100);
+  pending_layer_->HighResTiling()->UpdateTilePriorities(
+      PENDING_TREE, viewport, 1.0f, 1.0);
+  pending_layer_->LowResTiling()->UpdateTilePriorities(
+      PENDING_TREE, viewport, 1.0f, 1.0);
+  active_layer_->HighResTiling()->UpdateTilePriorities(
+      ACTIVE_TREE, viewport, 1.0f, 1.0);
+  active_layer_->LowResTiling()->UpdateTilePriorities(
+      ACTIVE_TREE, viewport, 1.0f, 1.0);
+
+  // Populate all tiles directly from the tilings.
+  all_tiles.clear();
+  std::vector<Tile*> pending_high_res_tiles =
+      pending_layer_->HighResTiling()->AllTilesForTesting();
+  for (size_t i = 0; i < pending_high_res_tiles.size(); ++i)
+    all_tiles.insert(pending_high_res_tiles[i]);
+
+  std::vector<Tile*> pending_low_res_tiles =
+      pending_layer_->LowResTiling()->AllTilesForTesting();
+  for (size_t i = 0; i < pending_low_res_tiles.size(); ++i)
+    all_tiles.insert(pending_low_res_tiles[i]);
+
+  std::vector<Tile*> active_high_res_tiles =
+      active_layer_->HighResTiling()->AllTilesForTesting();
+  for (size_t i = 0; i < active_high_res_tiles.size(); ++i)
+    all_tiles.insert(active_high_res_tiles[i]);
+
+  std::vector<Tile*> active_low_res_tiles =
+      active_layer_->LowResTiling()->AllTilesForTesting();
+  for (size_t i = 0; i < active_low_res_tiles.size(); ++i)
+    all_tiles.insert(active_low_res_tiles[i]);
+
+  tile_manager->InitializeTilesWithResourcesForTesting(
+      std::vector<Tile*>(all_tiles.begin(), all_tiles.end()));
+
+  Tile* last_tile = NULL;
+  smoothness_tiles.clear();
+  tile_count = 0;
+  // Here we expect to get increasing ACTIVE_TREE priority_bin.
+  for (TileManager::EvictionTileIterator it(tile_manager,
+                                            SMOOTHNESS_TAKES_PRIORITY);
+       it;
+       ++it) {
+    Tile* tile = *it;
+    EXPECT_TRUE(tile);
+    EXPECT_TRUE(tile->HasResources());
+
+    if (!last_tile)
+      last_tile = tile;
+
+    EXPECT_GE(last_tile->priority(ACTIVE_TREE).priority_bin,
+              tile->priority(ACTIVE_TREE).priority_bin);
+    if (last_tile->priority(ACTIVE_TREE).priority_bin ==
+        tile->priority(ACTIVE_TREE).priority_bin) {
+      EXPECT_GE(last_tile->priority(ACTIVE_TREE).distance_to_visible,
+                tile->priority(ACTIVE_TREE).distance_to_visible);
+    }
+
+    last_tile = tile;
+    ++tile_count;
+    smoothness_tiles.insert(tile);
+  }
+
+  EXPECT_EQ(tile_count, smoothness_tiles.size());
+  EXPECT_EQ(all_tiles, smoothness_tiles);
+
+  std::set<Tile*> new_content_tiles;
+  last_tile = NULL;
+  // Here we expect to get increasing PENDING_TREE priority_bin.
+  for (TileManager::EvictionTileIterator it(tile_manager,
+                                            NEW_CONTENT_TAKES_PRIORITY);
+       it;
+       ++it) {
+    Tile* tile = *it;
+    EXPECT_TRUE(tile);
+
+    if (!last_tile)
+      last_tile = tile;
+
+    EXPECT_GE(last_tile->priority(PENDING_TREE).priority_bin,
+              tile->priority(PENDING_TREE).priority_bin);
+    if (last_tile->priority(PENDING_TREE).priority_bin ==
+        tile->priority(PENDING_TREE).priority_bin) {
+      EXPECT_GE(last_tile->priority(PENDING_TREE).distance_to_visible,
+                tile->priority(PENDING_TREE).distance_to_visible);
+    }
+
+    last_tile = tile;
+    new_content_tiles.insert(tile);
+  }
+
+  EXPECT_EQ(tile_count, new_content_tiles.size());
+  EXPECT_EQ(all_tiles, new_content_tiles);
+}
 }  // namespace
 }  // namespace cc