cc: Implement geometry-based tile eviction

cc/resources/tiling_set_eviction_queue.cc

 // Copyright 2014 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 <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.
   if (!tiling_set_->num_tilings())
     return;
 
   current_tiling_index_ = CurrentTilingRange().start - 1u;
   AdvanceToNextValidTiling();
 }
 
@@ skipping 14 matching lines @@
 Tile* TilingSetEvictionQueue::Top() {
   DCHECK(!IsEmpty());
   return current_eviction_tile_;
 }
 
 const Tile* TilingSetEvictionQueue::Top() const {
   DCHECK(!IsEmpty());
   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.
+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.
+
+  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);
+
+  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_category_) {
-    case PictureLayerTiling::EVENTUALLY:
-      current_category_ =
-          PictureLayerTiling::EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION;
+  switch (current_priority_bin_) {
+    case TilePriority::EVENTUALLY:
+      current_priority_bin_ = TilePriority::SOON;
       return true;
-    case PictureLayerTiling::EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
-      current_category_ = PictureLayerTiling::SOON;
+    case TilePriority::SOON:
+      current_priority_bin_ = TilePriority::NOW;
       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:
+    case TilePriority::NOW:
       return false;
   }
   NOTREACHED();
   return false;
 }
 
-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()) {
-      current_eviction_tile_ = tile;
-      return true;
-    }
-  }
-
-  current_eviction_tile_ = nullptr;
-  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_) {
     case PictureLayerTilingSet::HIGHER_THAN_HIGH_RES:
       current_tiling_range_type_ = PictureLayerTilingSet::LOWER_THAN_LOW_RES;
       return true;
     case PictureLayerTilingSet::LOWER_THAN_LOW_RES:
       current_tiling_range_type_ =
           PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES;
       return true;
     case PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES:
       current_tiling_range_type_ = PictureLayerTilingSet::LOW_RES;
       return true;
     case PictureLayerTilingSet::LOW_RES:
       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;
       return true;
   }
   NOTREACHED();
   return false;
 }
 
 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);
 
   for (;;) {
     ++current_tiling_index_;
     while (current_tiling_index_ == CurrentTilingRange().end) {
       if (!AdvanceToNextTilingRangeType())
         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_);
 }
 
 size_t TilingSetEvictionQueue::CurrentTilingIndex() const {
   DCHECK_NE(current_tiling_index_, CurrentTilingRange().end);
   switch (current_tiling_range_type_) {
     case PictureLayerTilingSet::HIGHER_THAN_HIGH_RES:
     case PictureLayerTilingSet::LOW_RES:
     case PictureLayerTilingSet::HIGH_RES:
       return current_tiling_index_;
     // Tilings in the following ranges are accessed in reverse order.
     case PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES:
     case PictureLayerTilingSet::LOWER_THAN_LOW_RES: {
       PictureLayerTilingSet::TilingRange tiling_range = CurrentTilingRange();
       size_t current_tiling_range_offset =
           current_tiling_index_ - tiling_range.start;
       return tiling_range.end - 1 - current_tiling_range_offset;
     }
   }
   NOTREACHED();
   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