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 {
 
 TilingSetEvictionQueue::TilingSetEvictionQueue()
     : tiling_set_(nullptr),
+      tree_(ACTIVE_TREE),
       tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
-      current_category_(PictureLayerTiling::EVENTUALLY),
+      skip_all_shared_tiles_(false),
+      skip_shared_out_of_order_tiles_(false),
+      processing_soon_border_rect_(false),
+      processing_tiling_with_required_for_activation_tiles_(false),
+      tiling_index_with_required_for_activation_tiles_(0u),
+      current_priority_bin_(TilePriority::EVENTUALLY),
       current_tiling_index_(0u),
       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_(tiling_set->client()->GetTree()),
       tree_priority_(tree_priority),
-      current_category_(PictureLayerTiling::EVENTUALLY),
+      skip_all_shared_tiles_(
+          skip_shared_out_of_order_tiles &&
+          tree_priority == (tree_ == ACTIVE_TREE ? NEW_CONTENT_TAKES_PRIORITY
+                                                 : SMOOTHNESS_TAKES_PRIORITY)),
+      skip_shared_out_of_order_tiles_(skip_shared_out_of_order_tiles),
+      processing_soon_border_rect_(false),
+      processing_tiling_with_required_for_activation_tiles_(false),
+      tiling_index_with_required_for_activation_tiles_(0u),
+      current_priority_bin_(TilePriority::EVENTUALLY),
       current_tiling_index_(0u),
       current_tiling_range_type_(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES),
       current_eviction_tile_(nullptr),
-      eviction_tiles_(nullptr),
-      next_eviction_tile_index_(0u) {
-  DCHECK(tiling_set_);
-
+      next_unoccluded_now_tile_index_(0u) {
   // Early out if the layer has no tilings.
   if (!tiling_set_->num_tilings())
     return;
 
+  tiling_index_with_required_for_activation_tiles_ =
+      TilingIndexWithRequiredForActivationTiles();
+
   current_tiling_index_ = CurrentTilingRange().start - 1u;
   AdvanceToNextValidTiling();
 }
 
 TilingSetEvictionQueue::~TilingSetEvictionQueue() {
 }
 
 bool TilingSetEvictionQueue::IsEmpty() const {
   return !current_eviction_tile_;
 }
 
 void TilingSetEvictionQueue::Pop() {
   DCHECK(!IsEmpty());
 
   if (!AdvanceToNextEvictionTile())
     AdvanceToNextValidTiling();
 }
 
 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.
+
+  bool required_for_activation =
+      processing_tiling_with_required_for_activation_tiles_;
+
+  for (;;) {
+    while (spiral_iterator_) {
+      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 (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tile))
+        continue;
+      if (tile->required_for_activation() == required_for_activation) {

[vmpstr, 2014/12/10 18:01:15]

nit: for consistency, you might as well have

if (tile->rfa() != rfa)
  continue;
current_eviction_tile = tile;
return true;

but that's really up to you.

[USE eero AT chromium.org, 2014/12/11 15:22:00]

Done. That makes sense now that this does not have to keep track of tiling with
rfa tiles. I changed other loop similarly, too.

+        current_eviction_tile_ = tile;
+        return true;
+      }
+    }
+    if (processing_soon_border_rect_) {
+      // Advance from soon border rect to skewport rect.
+      processing_soon_border_rect_ = false;
+      if (current_tiling_->has_skewport_rect_tiles_) {
+        spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+            &current_tiling_->tiling_data_,
+            current_tiling_->current_skewport_rect_,
+            current_tiling_->current_visible_rect_,
+            current_tiling_->current_visible_rect_);
+        continue;
+      }
+    }
+    break;
+  }
+
+  if (visible_iterator_) {
+    TilePriority::PriorityBin max_tile_priority_bin =

[vmpstr, 2014/12/10 18:01:15]

If we move this outside of the if, the whole thing becomes

getter
while (visible_iterator_) {
  ...
}

instead of

if (visible_iterator_) {
 getter
 do {
   ...
 } while(visible_iterator_);
}

Unless I missed something... If that's equivalent can you change it to that
please?

[USE eero AT chromium.org, 2014/12/11 15:22:00]

[...]
Done. There used to be quite a many variables which were needed only while
iterating the visible iterator. Now there is only one, so it makes hardly a
difference.

+        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) {

[vmpstr, 2014/12/10 18:01:15]

Put a comment here explaining this block please (ie, why do we only check rfa
for pending tree only when max priority is now).

[USE eero AT chromium.org, 2014/12/11 15:22:00]

Done.

+        if (tree_ == PENDING_TREE &&
+            current_tiling_->IsTileRequiredForActivationIfVisible(tile) !=
+                required_for_activation) {
+          continue;
+        }
+        if (!current_tiling_->IsTileOccluded(tile)) {
+          unoccluded_now_tiles_.push_back(tile);
+          continue;
+        }
+      }
+      current_tiling_->UpdateTileAndTwinPriority(tile);
+      if (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tile))
+        continue;
+      if (tile->required_for_activation() == required_for_activation) {
+        current_eviction_tile_ = tile;
+        return true;
+      }
+    } while (visible_iterator_);
+  }
+
+  if (!unoccluded_now_tiles_.empty()) {
+    while (next_unoccluded_now_tile_index_ < unoccluded_now_tiles_.size()) {

[vmpstr, 2014/12/10 18:01:15]

I'm thinking it might be cleaner to just pop_front (if you change this to a
deque) or pop_back (if you keep this a vector) and use the front tile always.

This would eliminate the index, and the clear and the if check just becomes
while (!empty) check.

[USE eero AT chromium.org, 2014/12/11 15:22:00]

Done.

+      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 (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tile))
+        continue;
+      if (tile->required_for_activation() == required_for_activation) {
+        current_eviction_tile_ = tile;
+        return true;
+      }
+    }
+    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);
 
-  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_tiling_with_required_for_activation_tiles_ &&
+          tiling_index_with_required_for_activation_tiles_ <
+              tiling_set_->num_tilings()) {
+        processing_tiling_with_required_for_activation_tiles_ = true;
+        return true;
+      }
+      processing_tiling_with_required_for_activation_tiles_ = 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;
+    }
   }
 }
 
 PictureLayerTilingSet::TilingRange
 TilingSetEvictionQueue::CurrentTilingRange() const {
+  if (processing_tiling_with_required_for_activation_tiles_)
+    return PictureLayerTilingSet::TilingRange(
+        tiling_index_with_required_for_activation_tiles_,
+        tiling_index_with_required_for_activation_tiles_ + 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 (!tile->is_shared())
+    return false;
+
+  switch (tree_priority_) {
+    case SMOOTHNESS_TAKES_PRIORITY:
+      DCHECK_EQ(ACTIVE_TREE, tree_);
+      return false;
+    case NEW_CONTENT_TAKES_PRIORITY:
+      DCHECK_EQ(PENDING_TREE, tree_);
+      return false;
+    case SAME_PRIORITY_FOR_BOTH_TREES:
+      break;
+    case NUM_TREE_PRIORITIES:
+      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 twin_tree = tree_ == ACTIVE_TREE ? PENDING_TREE : ACTIVE_TREE;
+  const TilePriority& priority = tile->priority(tree_);
+  const TilePriority& twin_priority = tile->priority(twin_tree);
+  if (priority.priority_bin != twin_priority.priority_bin)
+    return priority.priority_bin < twin_priority.priority_bin;
+  const bool occluded = tile->is_occluded(tree_);
+  const bool twin_occluded = tile->is_occluded(twin_tree);
+  if (occluded != twin_occluded)
+    return !occluded;
+  if (priority.distance_to_visible != twin_priority.distance_to_visible)
+    return priority.distance_to_visible < twin_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;
 }
+
+size_t TilingSetEvictionQueue::TilingIndexWithRequiredForActivationTiles()
+    const {
+  // Returns the tiling index of the tiling with requuired for activation tiles.
+  // If no such tiling exists, returns the past-the-last index (num_tilings).
+  size_t num_tilings = tiling_set_->num_tilings();
+
+  if (tree_ == PENDING_TREE) {
+    // For the pending tree, the tiling with required for activation tiles is
+    // the high res one.
+    PictureLayerTilingSet::TilingRange high_res_tiling_range =
+        tiling_set_->GetTilingRange(PictureLayerTilingSet::HIGH_RES);
+    if (high_res_tiling_range.start != high_res_tiling_range.end)
+      return high_res_tiling_range.start;
+  } else {
+    DCHECK_EQ(ACTIVE_TREE, tree_);
+    // Only pending tree tiles can be required for activation. They can appear
+    // also in the active tree only if they are shared. If we skip all shared
+    // tiles, there is no need to find them as they will not be returned.
+    if (skip_all_shared_tiles_)
+      return num_tilings;
+
+    // For the active tree, the tiling with required for activation tiles is
+    // the one whose twin tiling is the high res pending tiling.
+    for (size_t i = 0; i < num_tilings; ++i) {
+      const PictureLayerTiling* tiling = tiling_set_->tiling_at(i);
+      const PictureLayerTiling* pending_tiling =
+          tiling_set_->client()->GetPendingOrActiveTwinTiling(tiling);
+      if (pending_tiling && pending_tiling->resolution() == HIGH_RESOLUTION)
+        return i;
+    }
+  }
+
+  return num_tilings;
+}
+
+}  // namespace cc