cc/resources/tiling_set_eviction_queue.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include <utility>
   6
   7 #include "cc/resources/tiling_set_eviction_queue.h"
   8
   9 namespace cc {
  10 namespace {
  11
  12 bool IsSharedOutOfOrderTile(WhichTree tree, const Tile* tile) {
  13   if (!tile->is_shared())
  14     return false;
  15
  16   // The priority for tile priority of a shared tile will be a combined
  17   // priority thus return shared tiles from a higher priority tree as
  18   // it is out of order for a lower priority tree.
  19   WhichTree twin_tree = tree == ACTIVE_TREE ? PENDING_TREE : ACTIVE_TREE;
  20   const TilePriority& priority = tile->priority(tree);
  21   const TilePriority& twin_priority = tile->priority(twin_tree);
  22   if (priority.priority_bin != twin_priority.priority_bin)
  23     return priority.priority_bin > twin_priority.priority_bin;
  24   const bool occluded = tile->is_occluded(tree);
  25   const bool twin_occluded = tile->is_occluded(twin_tree);
  26   if (occluded != twin_occluded)
  27     return occluded;
  28   if (priority.distance_to_visible != twin_priority.distance_to_visible)
  29     return priority.distance_to_visible > twin_priority.distance_to_visible;
  30
  31   // If priorities are the same, it does not matter which tree returns
  32   // the tile. Let's pick the pending tree.
  33   return tree != PENDING_TREE;
  34 }
  35
  36 }  // namespace
  37
  38 TilingSetEvictionQueue::TilingSetEvictionQueue(
  39     PictureLayerTilingSet* tiling_set,
  40     bool skip_shared_out_of_order_tiles)
  41     : tiling_set_(tiling_set),
  42       tree_(tiling_set->client()->GetTree()),
  43       skip_shared_out_of_order_tiles_(skip_shared_out_of_order_tiles),
  44       processing_soon_border_rect_(false),
  45       processing_required_for_activation_tiles_(false),
  46       current_priority_bin_(TilePriority::EVENTUALLY),
  47       current_tiling_index_(0u),
  48       current_tiling_range_type_(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES),
  49       current_eviction_tile_(nullptr) {
  50   // Early out if the layer has no tilings.
  51   if (!tiling_set_->num_tilings())
  52     return;
  53
  54   current_tiling_index_ = CurrentTilingRange().start - 1u;
  55   AdvanceToNextValidTiling();
  56 }
  57
  58 TilingSetEvictionQueue::~TilingSetEvictionQueue() {
  59 }
  60
  61 bool TilingSetEvictionQueue::IsEmpty() const {
  62   return !current_eviction_tile_;
  63 }
  64
  65 void TilingSetEvictionQueue::Pop() {
  66   DCHECK(!IsEmpty());
  67
  68   if (!AdvanceToNextEvictionTile())
  69     AdvanceToNextValidTiling();
  70 }
  71
  72 Tile* TilingSetEvictionQueue::Top() {
  73   DCHECK(!IsEmpty());
  74   return current_eviction_tile_;
  75 }
  76
  77 const Tile* TilingSetEvictionQueue::Top() const {
  78   DCHECK(!IsEmpty());
  79   return current_eviction_tile_;
  80 }
  81
  82 bool TilingSetEvictionQueue::AdvanceToNextEvictionTile() {
  83   // Advance to the next eviction tile within the current priority bin and
  84   // tiling. This is done while advancing to a new tiling and while popping
  85   // the current tile.
  86
  87   bool required_for_activation = processing_required_for_activation_tiles_;
  88
  89   for (;;) {
  90     while (spiral_iterator_) {
  91       std::pair<int, int> next_index = spiral_iterator_.index();
  92       Tile* tile = current_tiling_->TileAt(next_index.first, next_index.second);
  93       ++spiral_iterator_;
  94       if (!tile || !tile->HasResource())
  95         continue;
  96       current_tiling_->UpdateTileAndTwinPriority(tile);
  97       if (skip_shared_out_of_order_tiles_ &&
  98           IsSharedOutOfOrderTile(tree_, tile))
  99         continue;
 100       DCHECK_EQ(tile->required_for_activation(), required_for_activation);
 101       current_eviction_tile_ = tile;
 102       return true;
 103     }
 104     if (processing_soon_border_rect_) {
 105       // Advance from soon border rect to skewport rect.
 106       processing_soon_border_rect_ = false;
 107       if (current_tiling_->has_skewport_rect_tiles_) {
 108         spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 109             &current_tiling_->tiling_data_,
 110             current_tiling_->current_skewport_rect_,
 111             current_tiling_->current_visible_rect_,
 112             current_tiling_->current_visible_rect_);
 113         continue;
 114       }
 115     }
 116     break;
 117   }
 118
 119   TilePriority::PriorityBin max_tile_priority_bin =
 120       current_tiling_->client_->GetMaxTilePriorityBin();
 121   while (visible_iterator_) {
 122     std::pair<int, int> next_index = visible_iterator_.index();
 123     Tile* tile = current_tiling_->TileAt(next_index.first, next_index.second);
 124     ++visible_iterator_;
 125     if (!tile || !tile->HasResource())
 126       continue;
 127     // If the max tile priority is not NOW, updated priorities for tiles
 128     // returned by the visible iterator will not have NOW (but EVENTUALLY)
 129     // priority bin and cannot therefore be required for activation tiles nor
 130     // occluded NOW tiles in the current tiling.
 131     if (max_tile_priority_bin <= TilePriority::NOW) {
 132       // If the current tiling is a pending tree tiling, required for
 133       // activation tiles can be detected without updating tile priorities.
 134       if (tree_ == PENDING_TREE &&
 135           current_tiling_->IsTileRequiredForActivationIfVisible(tile) !=
 136               required_for_activation) {
 137         continue;
 138       }
 139       // Unoccluded NOW tiles should be evicted (and thus returned) only after
 140       // all occluded NOW tiles.
 141       if (!current_tiling_->IsTileOccluded(tile)) {
 142         unoccluded_now_tiles_.push_back(tile);
 143         continue;
 144       }
 145     }
 146     current_tiling_->UpdateTileAndTwinPriority(tile);
 147     if (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tree_, tile))
 148       continue;
 149     if (tile->required_for_activation() != required_for_activation)
 150       continue;
 151     current_eviction_tile_ = tile;
 152     return true;
 153   }
 154
 155   while (!unoccluded_now_tiles_.empty()) {
 156     // All (unoccluded) NOW tiles have the same priority bin (NOW) and the same
 157     // distance to visible (0.0), so it does not matter that tiles are popped
 158     // in reversed (FILO) order.
 159     Tile* tile = unoccluded_now_tiles_.back();
 160     unoccluded_now_tiles_.pop_back();
 161     DCHECK(tile);
 162     if (!tile->HasResource())
 163       continue;
 164     current_tiling_->UpdateTileAndTwinPriority(tile);
 165     if (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tree_, tile))
 166       continue;
 167     if (tile->required_for_activation() != required_for_activation)
 168       continue;
 169     current_eviction_tile_ = tile;
 170     return true;
 171   }
 172
 173   current_eviction_tile_ = nullptr;
 174   return false;
 175 }
 176
 177 bool TilingSetEvictionQueue::AdvanceToNextPriorityBin() {
 178   // Advance to the next priority bin. This is done only after all tiling range
 179   // types (including the required for activation tiling) within the previous
 180   // priority bin have been gone through.
 181   DCHECK_EQ(current_tiling_range_type_, PictureLayerTilingSet::HIGH_RES);
 182
 183   switch (current_priority_bin_) {
 184     case TilePriority::EVENTUALLY:
 185       current_priority_bin_ = TilePriority::SOON;
 186       return true;
 187     case TilePriority::SOON:
 188       current_priority_bin_ = TilePriority::NOW;
 189       return true;
 190     case TilePriority::NOW:
 191       return false;
 192   }
 193   NOTREACHED();
 194   return false;
 195 }
 196
 197 bool TilingSetEvictionQueue::AdvanceToNextTilingRangeType() {
 198   // Advance to the next tiling range type within the current priority bin, to
 199   // the required for activation tiling range type within the current priority
 200   // bin or to the first tiling range type within the next priority bin. This
 201   // is done only after all tilings within the previous tiling range type have
 202   // been gone through.
 203   DCHECK_EQ(current_tiling_index_, CurrentTilingRange().end);
 204
 205   switch (current_tiling_range_type_) {
 206     case PictureLayerTilingSet::HIGHER_THAN_HIGH_RES:
 207       current_tiling_range_type_ = PictureLayerTilingSet::LOWER_THAN_LOW_RES;
 208       return true;
 209     case PictureLayerTilingSet::LOWER_THAN_LOW_RES:
 210       current_tiling_range_type_ =
 211           PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES;
 212       return true;
 213     case PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES:
 214       current_tiling_range_type_ = PictureLayerTilingSet::LOW_RES;
 215       return true;
 216     case PictureLayerTilingSet::LOW_RES:
 217       current_tiling_range_type_ = PictureLayerTilingSet::HIGH_RES;
 218       return true;
 219     case PictureLayerTilingSet::HIGH_RES:
 220       // Process required for activation tiles (unless that has already been
 221       // done). Only pending tree NOW tiles may be required for activation.
 222       if (!processing_required_for_activation_tiles_ &&
 223           current_priority_bin_ == TilePriority::NOW && tree_ == PENDING_TREE) {
 224         processing_required_for_activation_tiles_ = true;
 225         return true;
 226       }
 227       processing_required_for_activation_tiles_ = false;
 228
 229       if (!AdvanceToNextPriorityBin())
 230         return false;
 231
 232       current_tiling_range_type_ = PictureLayerTilingSet::HIGHER_THAN_HIGH_RES;
 233       return true;
 234   }
 235   NOTREACHED();
 236   return false;
 237 }
 238
 239 bool TilingSetEvictionQueue::AdvanceToNextValidTiling() {
 240   // Advance to the next tiling within current tiling range type or to
 241   // the first tiling within the next tiling range type or priority bin until
 242   // the next eviction tile is found. This is done only after all eviction
 243   // tiles within the previous tiling within the current priority bin and
 244   // tiling range type have been gone through.
 245   DCHECK(!current_eviction_tile_);
 246   DCHECK_NE(current_tiling_index_, CurrentTilingRange().end);
 247
 248   for (;;) {
 249     ++current_tiling_index_;
 250     while (current_tiling_index_ == CurrentTilingRange().end) {
 251       if (!AdvanceToNextTilingRangeType())
 252         return false;
 253       current_tiling_index_ = CurrentTilingRange().start;
 254     }
 255     current_tiling_ = tiling_set_->tiling_at(CurrentTilingIndex());
 256
 257     switch (current_priority_bin_) {
 258       case TilePriority::EVENTUALLY:
 259         if (current_tiling_->has_eventually_rect_tiles_) {
 260           spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 261               &current_tiling_->tiling_data_,
 262               current_tiling_->current_eventually_rect_,
 263               current_tiling_->current_skewport_rect_,
 264               current_tiling_->current_soon_border_rect_);
 265           if (AdvanceToNextEvictionTile())
 266             return true;
 267         }
 268         break;
 269       case TilePriority::SOON:
 270         if (current_tiling_->has_skewport_rect_tiles_ ||
 271             current_tiling_->has_soon_border_rect_tiles_) {
 272           processing_soon_border_rect_ = true;
 273           if (current_tiling_->has_soon_border_rect_tiles_)
 274             spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 275                 &current_tiling_->tiling_data_,
 276                 current_tiling_->current_soon_border_rect_,
 277                 current_tiling_->current_skewport_rect_,
 278                 current_tiling_->current_visible_rect_);
 279           if (AdvanceToNextEvictionTile())
 280             return true;
 281         }
 282         break;
 283       case TilePriority::NOW:
 284         if (current_tiling_->has_visible_rect_tiles_) {
 285           visible_iterator_ =
 286               TilingData::Iterator(&current_tiling_->tiling_data_,
 287                                    current_tiling_->current_visible_rect_,
 288                                    false /* include_borders */);
 289           if (AdvanceToNextEvictionTile())
 290             return true;
 291         }
 292         break;
 293     }
 294   }
 295 }
 296
 297 PictureLayerTilingSet::TilingRange
 298 TilingSetEvictionQueue::CurrentTilingRange() const {
 299   return tiling_set_->GetTilingRange(current_tiling_range_type_);
 300 }
 301
 302 size_t TilingSetEvictionQueue::CurrentTilingIndex() const {
 303   DCHECK_NE(current_tiling_index_, CurrentTilingRange().end);
 304   switch (current_tiling_range_type_) {
 305     case PictureLayerTilingSet::HIGHER_THAN_HIGH_RES:
 306     case PictureLayerTilingSet::LOW_RES:
 307     case PictureLayerTilingSet::HIGH_RES:
 308       return current_tiling_index_;
 309     // Tilings in the following ranges are accessed in reverse order.
 310     case PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES:
 311     case PictureLayerTilingSet::LOWER_THAN_LOW_RES: {
 312       PictureLayerTilingSet::TilingRange tiling_range = CurrentTilingRange();
 313       size_t current_tiling_range_offset =
 314           current_tiling_index_ - tiling_range.start;
 315       return tiling_range.end - 1 - current_tiling_range_offset;
 316     }
 317   }
 318   NOTREACHED();
 319   return 0;
 320 }
 321
 322 }  // namespace cc