cc: Implement geometry-based tile eviction

cc/resources/tiling_set_eviction_queue.cc

Index: cc/resources/tiling_set_eviction_queue.cc
diff --git a/cc/resources/tiling_set_eviction_queue.cc b/cc/resources/tiling_set_eviction_queue.cc
index 8c5ff52f127099626c584429508b404d4ffce5e1..58619aebd98d69d79c909a6946704b10344e3316 100644
--- a/cc/resources/tiling_set_eviction_queue.cc
+++ b/cc/resources/tiling_set_eviction_queue.cc
@@ -2,32 +2,45 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include <utility>
+
 #include "cc/resources/tiling_set_eviction_queue.h"
 
 namespace cc {
 
+namespace {
+const size_t kNullTilingIndex = ~static_cast<size_t>(0u);
+}
+
 TilingSetEvictionQueue::TilingSetEvictionQueue()
     : tiling_set_(nullptr),
       tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
-      current_category_(PictureLayerTiling::EVENTUALLY),
+      skip_shared_out_of_order_tiles_(false),
+      processing_required_for_activation_tiling_(false),
+      processing_soon_border_rect_(false),
+      current_priority_bin_(TilePriority::EVENTUALLY),
       current_tiling_index_(0u),
+      current_required_for_activation_tiling_index_(kNullTilingIndex),
       current_tiling_range_type_(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES),
       current_eviction_tile_(nullptr),
-      eviction_tiles_(nullptr),
-      next_eviction_tile_index_(0u) {
+      next_unoccluded_now_tile_index_(0u) {
 }
 
 TilingSetEvictionQueue::TilingSetEvictionQueue(
     PictureLayerTilingSet* tiling_set,
-    TreePriority tree_priority)
+    TreePriority tree_priority,
+    bool skip_shared_out_of_order_tiles)
     : tiling_set_(tiling_set),
       tree_priority_(tree_priority),
-      current_category_(PictureLayerTiling::EVENTUALLY),
+      skip_shared_out_of_order_tiles_(skip_shared_out_of_order_tiles),
+      processing_required_for_activation_tiling_(false),
+      processing_soon_border_rect_(false),
+      current_priority_bin_(TilePriority::EVENTUALLY),
       current_tiling_index_(0u),
+      current_required_for_activation_tiling_index_(kNullTilingIndex),

[vmpstr, 2014/12/09 02:10:58]

Can we just find the high res tiling index directly? I'm not sure if there are
more uses of this, or is it just used as a high res index?

[USE eero AT chromium.org, 2014/12/09 18:44:15]

The other reason is not to process the tiling having RFA tiles for the second
time (on the first time RFA tiles are skipped) if we do not see any RFA tiles
(because there aren't any or because they are skipped and to be returned by the
thin queue).
And while it is easy to get the tiling index in the case of the pending tree (in
which case it is always the high res tiling), I think it is more complex in the
case of the active tree. Usually the twin tiling of the pending high res tiling
is active high res tiling but is it guaranteed to be so?

[vmpstr, 2014/12/09 19:47:55]

It's not guaranteed, but I don't think it's that much more complicated, you just
have to find a twin tiling with HIGH_RESOLUTION and then find an index of the
tiling in this set that has the same scale. The point is that this would
simplify the rest of the code by ensuring that
current_required_for_activation_tiling_index_ (or what should probably be
renamed to tiling_index_with_required_for_activation_tiles_) is always correct.

[USE eero AT chromium.org, 2014/12/10 12:35:45]

Done.

       current_tiling_range_type_(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES),
       current_eviction_tile_(nullptr),
-      eviction_tiles_(nullptr),
-      next_eviction_tile_index_(0u) {
+      next_unoccluded_now_tile_index_(0u) {
   DCHECK(tiling_set_);
 
   // Early out if the layer has no tilings.
@@ -62,60 +75,122 @@ const Tile* TilingSetEvictionQueue::Top() const {
   return current_eviction_tile_;
 }
 
-bool TilingSetEvictionQueue::AdvanceToNextCategory() {
-  // Advance to the next category. This is done only after all tiling range
-  // types within the previous category have been gone through.
-  DCHECK_EQ(current_tiling_range_type_, PictureLayerTilingSet::HIGH_RES);
+bool TilingSetEvictionQueue::AdvanceToNextEvictionTile() {
+  // Advance to the next eviction tile within the current priority bin and
+  // tiling. This is done while advancing to a new tiling and while popping
+  // the current tile.
 
-  switch (current_category_) {
-    case PictureLayerTiling::EVENTUALLY:
-      current_category_ =
-          PictureLayerTiling::EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION;
-      return true;
-    case PictureLayerTiling::EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
-      current_category_ = PictureLayerTiling::SOON;
-      return true;
-    case PictureLayerTiling::SOON:
-      current_category_ = PictureLayerTiling::SOON_AND_REQUIRED_FOR_ACTIVATION;
-      return true;
-    case PictureLayerTiling::SOON_AND_REQUIRED_FOR_ACTIVATION:
-      current_category_ = PictureLayerTiling::NOW;
-      return true;
-    case PictureLayerTiling::NOW:
-      current_category_ = PictureLayerTiling::NOW_AND_REQUIRED_FOR_ACTIVATION;
-      return true;
-    case PictureLayerTiling::NOW_AND_REQUIRED_FOR_ACTIVATION:
-      return false;
-  }
-  NOTREACHED();
-  return false;
-}
+  WhichTree tree = current_tiling_->client_->GetTree();

[vmpstr, 2014/12/09 02:10:58]

You can take this as a ctor argument, since it won't change during iteration.

[USE eero AT chromium.org, 2014/12/09 18:44:14]

Done.

+  bool required_for_activation = processing_required_for_activation_tiling_;
+  bool skip_all_shared_tiles =

[vmpstr, 2014/12/09 02:10:58]

likewise, this can be determined at ctor time

[USE eero AT chromium.org, 2014/12/09 18:44:15]

Done.

+      skip_shared_out_of_order_tiles_ &&
+      tree_priority_ == (tree == ACTIVE_TREE ? NEW_CONTENT_TAKES_PRIORITY
+                                             : SMOOTHNESS_TAKES_PRIORITY);
 
-bool TilingSetEvictionQueue::AdvanceToNextEvictionTile() {
-  // Advance to the next eviction tile within the current category and tiling.
-  // This is done while advancing to a new tiling (in which case the next
-  // eviction tile index is 0) and while popping the current tile (in which
-  // case the next eviction tile index is greater than 0).
-  DCHECK_EQ(next_eviction_tile_index_ > 0, current_eviction_tile_ != nullptr);
-
-  while (next_eviction_tile_index_ < eviction_tiles_->size()) {
-    Tile* tile = (*eviction_tiles_)[next_eviction_tile_index_];
-    ++next_eviction_tile_index_;
-    if (tile->HasResources()) {
+  while (spiral_iterator_ ||

[vmpstr, 2014/12/09 02:10:58]

can we maybe split this into a nested loop? something like the following:

while (true) {
 while (spiral_iterator_) {
   ...
 }

 if (processing_soon_border_rect_) {
   AdvanceToSkewport();
   processing_soon_border_rect_ = false;
 } else {
   break;
 }
}

Wdyt?
It's a bit difficult for me to reason about this at a glance otherwise.

[USE eero AT chromium.org, 2014/12/09 18:44:15]

Done.

+         (processing_soon_border_rect_ && AdvanceToSkewport())) {
+    std::pair<int, int> next_index = spiral_iterator_.index();
+    Tile* tile = current_tiling_->TileAt(next_index.first, next_index.second);
+    ++spiral_iterator_;
+    if (!tile || !tile->HasResources())
+      continue;
+    if (skip_all_shared_tiles && tile->is_shared())
+      continue;
+    current_tiling_->UpdateTileAndTwinPriority(tile);
+    if (IsSharedOutOfOrderTile(tile))

[vmpstr, 2014/12/09 02:10:58]

For symmetry, maybe this should be

if (skip_shared_out_of_order_tiles && IsSharedOutOfOrderTile(tile))

It's a bit confusing that IsSharedOutOfOrderTile returns false if we don't have
to skip them. That is, the tile is either share out of order or it's not, and
that shouldn't depend on whether we're required to skip them.

[USE eero AT chromium.org, 2014/12/09 18:44:15]

Done.

+      continue;
+    if (tile->required_for_activation() == required_for_activation) {
       current_eviction_tile_ = tile;
       return true;
     }
+    SetCurrentRequiredForActivationTilingIndex(current_tiling_index_);
+  }
+
+  if (visible_iterator_) {
+    TilePriority::PriorityBin max_tile_priority_bin =
+        current_tiling_->client_->GetMaxTilePriorityBin();
+    do {
+      std::pair<int, int> next_index = visible_iterator_.index();
+      Tile* tile = current_tiling_->TileAt(next_index.first, next_index.second);
+      ++visible_iterator_;
+      if (!tile || !tile->HasResources())
+        continue;
+      if (skip_all_shared_tiles && tile->is_shared())
+        continue;
+      if (max_tile_priority_bin <= TilePriority::NOW) {
+        if (tree == PENDING_TREE &&
+            current_tiling_->IsTileRequiredForActivationIfVisible(tile) !=
+                required_for_activation) {
+          SetCurrentRequiredForActivationTilingIndex(current_tiling_index_);
+          continue;
+        }
+        if (!current_tiling_->IsTileOccluded(tile)) {
+          unoccluded_now_tiles_.push_back(tile);
+          continue;
+        }
+      }
+      current_tiling_->UpdateTileAndTwinPriority(tile);
+      if (IsSharedOutOfOrderTile(tile))
+        continue;
+      if (tile->required_for_activation() == required_for_activation) {
+        current_eviction_tile_ = tile;
+        return true;
+      }
+      SetCurrentRequiredForActivationTilingIndex(current_tiling_index_);
+    } while (visible_iterator_);
+  }
+
+  if (!unoccluded_now_tiles_.empty()) {
+    while (next_unoccluded_now_tile_index_ < unoccluded_now_tiles_.size()) {
+      Tile* tile = unoccluded_now_tiles_[next_unoccluded_now_tile_index_];
+      ++next_unoccluded_now_tile_index_;
+      DCHECK(tile);
+      if (!tile->HasResources())
+        continue;
+      current_tiling_->UpdateTileAndTwinPriority(tile);
+      if (IsSharedOutOfOrderTile(tile))
+        continue;
+      if (tile->required_for_activation() == required_for_activation) {
+        current_eviction_tile_ = tile;
+        return true;
+      }
+      SetCurrentRequiredForActivationTilingIndex(current_tiling_index_);
+    }
+    unoccluded_now_tiles_.clear();
+    next_unoccluded_now_tile_index_ = 0u;
   }
 
   current_eviction_tile_ = nullptr;
   return false;
 }
 
+bool TilingSetEvictionQueue::AdvanceToNextPriorityBin() {
+  // Advance to the next priority bin. This is done only after all tiling range
+  // types (including the required for activation tiling) within the previous
+  // priority bin have been gone through.
+  DCHECK_EQ(current_tiling_range_type_, PictureLayerTilingSet::HIGH_RES);
+  DCHECK_EQ(current_required_for_activation_tiling_index_, kNullTilingIndex);
+
+  switch (current_priority_bin_) {
+    case TilePriority::EVENTUALLY:
+      current_priority_bin_ = TilePriority::SOON;
+      return true;
+    case TilePriority::SOON:
+      current_priority_bin_ = TilePriority::NOW;
+      return true;
+    case TilePriority::NOW:
+      return false;
+  }
+  NOTREACHED();
+  return false;
+}
+
 bool TilingSetEvictionQueue::AdvanceToNextTilingRangeType() {
-  // Advance to the next tiling range type within the current category or to
-  // the first tiling range type within the next category. This is done only
-  // after all tilings within the previous tiling range type have been gone
-  // through.
+  // Advance to the next tiling range type within the current priority bin, to
+  // the required for activation tiling range type within the current priority
+  // bin or to the first tiling range type within the next priority bin. This
+  // is done only after all tilings within the previous tiling range type have
+  // been gone through.
   DCHECK_EQ(current_tiling_index_, CurrentTilingRange().end);
 
   switch (current_tiling_range_type_) {
@@ -133,7 +208,15 @@ bool TilingSetEvictionQueue::AdvanceToNextTilingRangeType() {
       current_tiling_range_type_ = PictureLayerTilingSet::HIGH_RES;
       return true;
     case PictureLayerTilingSet::HIGH_RES:
-      if (!AdvanceToNextCategory())
+      if (!processing_required_for_activation_tiling_ &&
+          current_required_for_activation_tiling_index_ != kNullTilingIndex) {
+        processing_required_for_activation_tiling_ = true;
+        return true;
+      }
+      SetCurrentRequiredForActivationTilingIndex(kNullTilingIndex);
+      processing_required_for_activation_tiling_ = false;
+
+      if (!AdvanceToNextPriorityBin())
         return false;
 
       current_tiling_range_type_ = PictureLayerTilingSet::HIGHER_THAN_HIGH_RES;
@@ -145,10 +228,10 @@ bool TilingSetEvictionQueue::AdvanceToNextTilingRangeType() {
 
 bool TilingSetEvictionQueue::AdvanceToNextValidTiling() {
   // Advance to the next tiling within current tiling range type or to
-  // the first tiling within the next tiling range type or category until
+  // the first tiling within the next tiling range type or priority bin until
   // the next eviction tile is found. This is done only after all eviction
-  // tiles within the previous tiling within the current category and tiling
-  // range type have been gone through.
+  // tiles within the previous tiling within the current priority bin and
+  // tiling range type have been gone through.
   DCHECK(!current_eviction_tile_);
   DCHECK_NE(current_tiling_index_, CurrentTilingRange().end);
 
@@ -159,18 +242,73 @@ bool TilingSetEvictionQueue::AdvanceToNextValidTiling() {
         return false;
       current_tiling_index_ = CurrentTilingRange().start;
     }
+    current_tiling_ = tiling_set_->tiling_at(CurrentTilingIndex());
 
-    PictureLayerTiling* tiling = tiling_set_->tiling_at(CurrentTilingIndex());
-    eviction_tiles_ =
-        tiling->GetEvictionTiles(tree_priority_, current_category_);
-    next_eviction_tile_index_ = 0u;
-    if (AdvanceToNextEvictionTile())
-      return true;
+    switch (current_priority_bin_) {
+      case TilePriority::EVENTUALLY:
+        if (current_tiling_->has_eventually_rect_tiles_) {
+          spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+              &current_tiling_->tiling_data_,
+              current_tiling_->current_eventually_rect_,
+              current_tiling_->current_skewport_rect_,
+              current_tiling_->current_soon_border_rect_);
+          if (AdvanceToNextEvictionTile())
+            return true;
+        }
+        break;
+      case TilePriority::SOON:
+        if (current_tiling_->has_skewport_rect_tiles_ ||
+            current_tiling_->has_soon_border_rect_tiles_) {
+          processing_soon_border_rect_ = true;
+          if (current_tiling_->has_soon_border_rect_tiles_)
+            spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+                &current_tiling_->tiling_data_,
+                current_tiling_->current_soon_border_rect_,
+                current_tiling_->current_skewport_rect_,
+                current_tiling_->current_visible_rect_);
+          if (AdvanceToNextEvictionTile())
+            return true;
+        }
+        break;
+      case TilePriority::NOW:
+        if (current_tiling_->has_visible_rect_tiles_) {
+          visible_iterator_ =
+              TilingData::Iterator(&current_tiling_->tiling_data_,
+                                   current_tiling_->current_visible_rect_,
+                                   false /* include_borders */);
+          if (AdvanceToNextEvictionTile())
+            return true;
+        }
+        break;
+    }
   }
 }
 
+bool TilingSetEvictionQueue::AdvanceToSkewport() {
+  // Advance from soon border rect to skewport rect.
+  // This is done only after all soon border rect tiles have been gone through.
+  DCHECK_EQ(TilePriority::SOON, current_priority_bin_);
+  DCHECK(processing_soon_border_rect_);
+  DCHECK(!spiral_iterator_);
+
+  processing_soon_border_rect_ = false;
+
+  if (!current_tiling_->has_skewport_rect_tiles_)
+    return false;
+
+  spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+      &current_tiling_->tiling_data_, current_tiling_->current_skewport_rect_,
+      current_tiling_->current_visible_rect_,
+      current_tiling_->current_visible_rect_);
+  return !!spiral_iterator_;
+}
+
 PictureLayerTilingSet::TilingRange
 TilingSetEvictionQueue::CurrentTilingRange() const {
+  if (processing_required_for_activation_tiling_)
+    return PictureLayerTilingSet::TilingRange(
+        current_required_for_activation_tiling_index_,
+        current_required_for_activation_tiling_index_ + 1);
   return tiling_set_->GetTilingRange(current_tiling_range_type_);
 }
 
@@ -194,4 +332,55 @@ size_t TilingSetEvictionQueue::CurrentTilingIndex() const {
   return 0;
 }
 
+bool TilingSetEvictionQueue::IsSharedOutOfOrderTile(const Tile* tile) const {
+  if (!skip_shared_out_of_order_tiles_)
+    return false;
+
+  if (!tile->is_shared())
+    return false;
+
+  switch (tree_priority_) {
+    case SMOOTHNESS_TAKES_PRIORITY:
+      DCHECK_EQ(ACTIVE_TREE, current_tiling_->client_->GetTree());
+      return false;
+    case NEW_CONTENT_TAKES_PRIORITY:
+      DCHECK_EQ(PENDING_TREE, current_tiling_->client_->GetTree());
+      return false;
+    case SAME_PRIORITY_FOR_BOTH_TREES:
+      break;
+    default:
+      NOTREACHED();
+  }
+
+  // The priority for tile priority of a shared tile will be a combined
+  // priority thus return shared tiles from a higher priority tree.
+  WhichTree tree = current_tiling_->client_->GetTree();
+  WhichTree other_tree = tree == ACTIVE_TREE ? PENDING_TREE : ACTIVE_TREE;
+  const TilePriority& priority = tile->priority(tree);
+  const TilePriority& other_priority = tile->priority(other_tree);
+  if (priority.priority_bin != other_priority.priority_bin)
+    return priority.priority_bin < other_priority.priority_bin;
+  const bool occluded = tile->is_occluded(tree);
+  const bool other_occluded = tile->is_occluded(other_tree);
+  if (occluded != other_occluded)
+    return !occluded;
+  if (priority.distance_to_visible != other_priority.distance_to_visible)
+    return priority.distance_to_visible < other_priority.distance_to_visible;
+
+  // If priorities are the same, it does not matter which tree returns
+  // the tile. Let's pick the pending tree.
+  return tree == PENDING_TREE;
+}
+
+void TilingSetEvictionQueue::SetCurrentRequiredForActivationTilingIndex(
+    size_t index) {
+  // A tiling can have required for activation tiles only if the tiling is
+  // pending high-res tiling or its twin tiling. There can thus be at most one
+  // such tiling in a tiling set.
+  DCHECK(current_required_for_activation_tiling_index_ == index ||
+         current_required_for_activation_tiling_index_ == kNullTilingIndex ||
+         index == kNullTilingIndex);
+  current_required_for_activation_tiling_index_ = index;
 }
+
+}  // namespace cc