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_(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_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_(ACTIVE_TREE),
       tree_priority_(tree_priority),
-      current_category_(PictureLayerTiling::EVENTUALLY),
+      skip_all_shared_tiles_(false),
+      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),
       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;
 
+  const PictureLayerTilingClient* client = tiling_set_->tiling_at(0)->client_;

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

tiling_set has a client as well (and it's the same client), so
tiling_set_->client() would work here.

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

Done.

+  tree_ = client->GetTree();
+  skip_all_shared_tiles_ =
+      skip_shared_out_of_order_tiles_ &&
+      tree_priority_ == (tree_ == ACTIVE_TREE ? NEW_CONTENT_TAKES_PRIORITY
+                                              : SMOOTHNESS_TAKES_PRIORITY);
+
   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_required_for_activation_tiling_;
+
+  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) {
+        current_eviction_tile_ = tile;
+        return true;
+      }
+      SetCurrentRequiredForActivationTilingIndex(current_tiling_index_);

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

This is the part that is confusing to me. I think if we compute the tiling ahead
of time, then I won't have to wonder things like "ok, if all required for
activation tiles don't have resources, would this ever hit here, since we
continue above?"

I think once we start the iteration (and all the calls to Advance*), we
shouldn't be trying to figure out which tiling is which at the same time. This
should be done ahead of time (in the ctor).

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

Done.

+    }
+    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 =
+        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 (skip_shared_out_of_order_tiles_ && 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 (skip_shared_out_of_order_tiles_ && 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;
+    }
   }
 }
 
 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 (!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;
+    default:

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

Don't put a default case (if a new case is added, it will be a compiler error
rather than a run time error)

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

Done. Had to add case for NUM_TREE_PRIORITIES, though.

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

Ok, that's fine. We can remove NUM_TREE_PRIORITIES in a follow-up. It seems to
be only be used in tests.

+      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 other_tree = tree_ == ACTIVE_TREE ? PENDING_TREE : ACTIVE_TREE;
+  const TilePriority& priority = tile->priority(tree_);
+  const TilePriority& other_priority = tile->priority(other_tree);

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

nit: twin_tree/twin_priority

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

Done.

+  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