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
  11 TilingSetEvictionQueue::TilingSetEvictionQueue()
  12     : tiling_set_(nullptr),
  13       tree_(ACTIVE_TREE),
  14       tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
  15       skip_all_shared_tiles_(false),
  16       skip_shared_out_of_order_tiles_(false),
  17       processing_soon_border_rect_(false),
  18       processing_tiling_with_required_for_activation_tiles_(false),
  19       tiling_index_with_required_for_activation_tiles_(0u),
  20       current_priority_bin_(TilePriority::EVENTUALLY),
  21       current_tiling_index_(0u),
  22       current_tiling_range_type_(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES),
  23       current_eviction_tile_(nullptr) {
  24 }
  25
  26 TilingSetEvictionQueue::TilingSetEvictionQueue(
  27     PictureLayerTilingSet* tiling_set,
  28     TreePriority tree_priority,
  29     bool skip_shared_out_of_order_tiles)
  30     : tiling_set_(tiling_set),
  31       tree_(tiling_set->client()->GetTree()),
  32       tree_priority_(tree_priority),
  33       skip_all_shared_tiles_(
  34           skip_shared_out_of_order_tiles &&
  35           tree_priority == (tree_ == ACTIVE_TREE ? NEW_CONTENT_TAKES_PRIORITY
  36                                                  : SMOOTHNESS_TAKES_PRIORITY)),
  37       skip_shared_out_of_order_tiles_(skip_shared_out_of_order_tiles),
  38       processing_soon_border_rect_(false),
  39       processing_tiling_with_required_for_activation_tiles_(false),
  40       tiling_index_with_required_for_activation_tiles_(0u),
  41       current_priority_bin_(TilePriority::EVENTUALLY),
  42       current_tiling_index_(0u),
  43       current_tiling_range_type_(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES),
  44       current_eviction_tile_(nullptr) {
  45   // Early out if the layer has no tilings.
  46   if (!tiling_set_->num_tilings())
  47     return;
  48
  49   tiling_index_with_required_for_activation_tiles_ =
  50       TilingIndexWithRequiredForActivationTiles();
  51
  52   current_tiling_index_ = CurrentTilingRange().start - 1u;
  53   AdvanceToNextValidTiling();
  54 }
  55
  56 TilingSetEvictionQueue::~TilingSetEvictionQueue() {
  57 }
  58
  59 bool TilingSetEvictionQueue::IsEmpty() const {
  60   return !current_eviction_tile_;
  61 }
  62
  63 void TilingSetEvictionQueue::Pop() {
  64   DCHECK(!IsEmpty());
  65
  66   if (!AdvanceToNextEvictionTile())
  67     AdvanceToNextValidTiling();
  68 }
  69
  70 Tile* TilingSetEvictionQueue::Top() {
  71   DCHECK(!IsEmpty());
  72   return current_eviction_tile_;
  73 }
  74
  75 const Tile* TilingSetEvictionQueue::Top() const {
  76   DCHECK(!IsEmpty());
  77   return current_eviction_tile_;
  78 }
  79
  80 bool TilingSetEvictionQueue::AdvanceToNextEvictionTile() {
  81   // Advance to the next eviction tile within the current priority bin and
  82   // tiling. This is done while advancing to a new tiling and while popping
  83   // the current tile.
  84
  85   bool required_for_activation =
  86       processing_tiling_with_required_for_activation_tiles_;
  87
  88   for (;;) {
  89     while (spiral_iterator_) {
  90       std::pair<int, int> next_index = spiral_iterator_.index();
  91       Tile* tile = current_tiling_->TileAt(next_index.first, next_index.second);
  92       ++spiral_iterator_;
  93       if (!tile || !tile->HasResource())
  94         continue;
  95       if (skip_all_shared_tiles_ && tile->is_shared())
  96         continue;
  97       current_tiling_->UpdateTileAndTwinPriority(tile);
  98       if (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tile))
  99         continue;
 100       if (tile->required_for_activation() != required_for_activation)
 101         continue;
 102       current_eviction_tile_ = tile;
 103       return true;
 104     }
 105     if (processing_soon_border_rect_) {
 106       // Advance from soon border rect to skewport rect.
 107       processing_soon_border_rect_ = false;
 108       if (current_tiling_->has_skewport_rect_tiles_) {
 109         spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 110             &current_tiling_->tiling_data_,
 111             current_tiling_->current_skewport_rect_,
 112             current_tiling_->current_visible_rect_,
 113             current_tiling_->current_visible_rect_);
 114         continue;
 115       }
 116     }
 117     break;
 118   }
 119
 120   TilePriority::PriorityBin max_tile_priority_bin =
 121       current_tiling_->client_->GetMaxTilePriorityBin();
 122   while (visible_iterator_) {
 123     std::pair<int, int> next_index = visible_iterator_.index();
 124     Tile* tile = current_tiling_->TileAt(next_index.first, next_index.second);
 125     ++visible_iterator_;
 126     if (!tile || !tile->HasResource())
 127       continue;
 128     if (skip_all_shared_tiles_ && tile->is_shared())
 129       continue;
 130     // If the max tile priority is not NOW, updated priorities for tiles
 131     // returned by the visible iterator will not have NOW (but EVENTUALLY)
 132     // priority bin and cannot therefore be required for activation tiles nor
 133     // occluded NOW tiles in the current tiling.
 134     if (max_tile_priority_bin <= TilePriority::NOW) {
 135       // If the current tiling is a pending tree tiling, required for
 136       // activation tiles can be detected without updating tile priorities.
 137       if (tree_ == PENDING_TREE &&
 138           current_tiling_->IsTileRequiredForActivationIfVisible(tile) !=
 139               required_for_activation) {
 140         continue;
 141       }
 142       // Unoccluded NOW tiles should be evicted (and thus returned) only after
 143       // all occluded NOW tiles.
 144       if (!current_tiling_->IsTileOccluded(tile)) {
 145         unoccluded_now_tiles_.push_back(tile);
 146         continue;
 147       }
 148     }
 149     current_tiling_->UpdateTileAndTwinPriority(tile);
 150     if (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tile))
 151       continue;
 152     if (tile->required_for_activation() != required_for_activation)
 153       continue;
 154     current_eviction_tile_ = tile;
 155     return true;
 156   }
 157
 158   while (!unoccluded_now_tiles_.empty()) {
 159     // All (unoccluded) NOW tiles have the same priority bin (NOW) and the same
 160     // distance to visible (0.0), so it does not matter that tiles are popped
 161     // in reversed (FILO) order.
 162     Tile* tile = unoccluded_now_tiles_.back();
 163     unoccluded_now_tiles_.pop_back();
 164     DCHECK(tile);
 165     if (!tile->HasResource())
 166       continue;
 167     current_tiling_->UpdateTileAndTwinPriority(tile);
 168     if (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tile))
 169       continue;
 170     if (tile->required_for_activation() != required_for_activation)
 171       continue;
 172     current_eviction_tile_ = tile;
 173     return true;
 174   }
 175
 176   current_eviction_tile_ = nullptr;
 177   return false;
 178 }
 179
 180 bool TilingSetEvictionQueue::AdvanceToNextPriorityBin() {
 181   // Advance to the next priority bin. This is done only after all tiling range
 182   // types (including the required for activation tiling) within the previous
 183   // priority bin have been gone through.
 184   DCHECK_EQ(current_tiling_range_type_, PictureLayerTilingSet::HIGH_RES);
 185
 186   switch (current_priority_bin_) {
 187     case TilePriority::EVENTUALLY:
 188       current_priority_bin_ = TilePriority::SOON;
 189       return true;
 190     case TilePriority::SOON:
 191       current_priority_bin_ = TilePriority::NOW;
 192       return true;
 193     case TilePriority::NOW:
 194       return false;
 195   }
 196   NOTREACHED();
 197   return false;
 198 }
 199
 200 bool TilingSetEvictionQueue::AdvanceToNextTilingRangeType() {
 201   // Advance to the next tiling range type within the current priority bin, to
 202   // the required for activation tiling range type within the current priority
 203   // bin or to the first tiling range type within the next priority bin. This
 204   // is done only after all tilings within the previous tiling range type have
 205   // been gone through.
 206   DCHECK_EQ(current_tiling_index_, CurrentTilingRange().end);
 207
 208   switch (current_tiling_range_type_) {
 209     case PictureLayerTilingSet::HIGHER_THAN_HIGH_RES:
 210       current_tiling_range_type_ = PictureLayerTilingSet::LOWER_THAN_LOW_RES;
 211       return true;
 212     case PictureLayerTilingSet::LOWER_THAN_LOW_RES:
 213       current_tiling_range_type_ =
 214           PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES;
 215       return true;
 216     case PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES:
 217       current_tiling_range_type_ = PictureLayerTilingSet::LOW_RES;
 218       return true;
 219     case PictureLayerTilingSet::LOW_RES:
 220       current_tiling_range_type_ = PictureLayerTilingSet::HIGH_RES;
 221       return true;
 222     case PictureLayerTilingSet::HIGH_RES:
 223       // Process required for activation tiles (unless that has already been
 224       // done for the current priority bin) if there is a tiling with required
 225       // for activation tiles and that tiling may have required for activation
 226       // tiles having the current priority bin (in the pending tree only NOW
 227       // tiles may be required for activation).
 228       if (!processing_tiling_with_required_for_activation_tiles_ &&
 229           tiling_index_with_required_for_activation_tiles_ <
 230               tiling_set_->num_tilings() &&
 231           (current_priority_bin_ == TilePriority::NOW ||
 232            tree_ == ACTIVE_TREE)) {
 233         processing_tiling_with_required_for_activation_tiles_ = true;
 234         return true;
 235       }
 236       processing_tiling_with_required_for_activation_tiles_ = false;
 237
 238       if (!AdvanceToNextPriorityBin())
 239         return false;
 240
 241       current_tiling_range_type_ = PictureLayerTilingSet::HIGHER_THAN_HIGH_RES;
 242       return true;
 243   }
 244   NOTREACHED();
 245   return false;
 246 }
 247
 248 bool TilingSetEvictionQueue::AdvanceToNextValidTiling() {
 249   // Advance to the next tiling within current tiling range type or to
 250   // the first tiling within the next tiling range type or priority bin until
 251   // the next eviction tile is found. This is done only after all eviction
 252   // tiles within the previous tiling within the current priority bin and
 253   // tiling range type have been gone through.
 254   DCHECK(!current_eviction_tile_);
 255   DCHECK_NE(current_tiling_index_, CurrentTilingRange().end);
 256
 257   for (;;) {
 258     ++current_tiling_index_;
 259     while (current_tiling_index_ == CurrentTilingRange().end) {
 260       if (!AdvanceToNextTilingRangeType())
 261         return false;
 262       current_tiling_index_ = CurrentTilingRange().start;
 263     }
 264     current_tiling_ = tiling_set_->tiling_at(CurrentTilingIndex());
 265
 266     switch (current_priority_bin_) {
 267       case TilePriority::EVENTUALLY:
 268         if (current_tiling_->has_eventually_rect_tiles_) {
 269           spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 270               &current_tiling_->tiling_data_,
 271               current_tiling_->current_eventually_rect_,
 272               current_tiling_->current_skewport_rect_,
 273               current_tiling_->current_soon_border_rect_);
 274           if (AdvanceToNextEvictionTile())
 275             return true;
 276         }
 277         break;
 278       case TilePriority::SOON:
 279         if (current_tiling_->has_skewport_rect_tiles_ ||
 280             current_tiling_->has_soon_border_rect_tiles_) {
 281           processing_soon_border_rect_ = true;
 282           if (current_tiling_->has_soon_border_rect_tiles_)
 283             spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 284                 &current_tiling_->tiling_data_,
 285                 current_tiling_->current_soon_border_rect_,
 286                 current_tiling_->current_skewport_rect_,
 287                 current_tiling_->current_visible_rect_);
 288           if (AdvanceToNextEvictionTile())
 289             return true;
 290         }
 291         break;
 292       case TilePriority::NOW:
 293         if (current_tiling_->has_visible_rect_tiles_) {
 294           visible_iterator_ =
 295               TilingData::Iterator(&current_tiling_->tiling_data_,
 296                                    current_tiling_->current_visible_rect_,
 297                                    false /* include_borders */);
 298           if (AdvanceToNextEvictionTile())
 299             return true;
 300         }
 301         break;
 302     }
 303   }
 304 }
 305
 306 PictureLayerTilingSet::TilingRange
 307 TilingSetEvictionQueue::CurrentTilingRange() const {
 308   if (processing_tiling_with_required_for_activation_tiles_)
 309     return PictureLayerTilingSet::TilingRange(
 310         tiling_index_with_required_for_activation_tiles_,
 311         tiling_index_with_required_for_activation_tiles_ + 1);
 312   return tiling_set_->GetTilingRange(current_tiling_range_type_);
 313 }
 314
 315 size_t TilingSetEvictionQueue::CurrentTilingIndex() const {
 316   DCHECK_NE(current_tiling_index_, CurrentTilingRange().end);
 317   switch (current_tiling_range_type_) {
 318     case PictureLayerTilingSet::HIGHER_THAN_HIGH_RES:
 319     case PictureLayerTilingSet::LOW_RES:
 320     case PictureLayerTilingSet::HIGH_RES:
 321       return current_tiling_index_;
 322     // Tilings in the following ranges are accessed in reverse order.
 323     case PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES:
 324     case PictureLayerTilingSet::LOWER_THAN_LOW_RES: {
 325       PictureLayerTilingSet::TilingRange tiling_range = CurrentTilingRange();
 326       size_t current_tiling_range_offset =
 327           current_tiling_index_ - tiling_range.start;
 328       return tiling_range.end - 1 - current_tiling_range_offset;
 329     }
 330   }
 331   NOTREACHED();
 332   return 0;
 333 }
 334
 335 bool TilingSetEvictionQueue::IsSharedOutOfOrderTile(const Tile* tile) const {
 336   if (!tile->is_shared())
 337     return false;
 338
 339   switch (tree_priority_) {
 340     case SMOOTHNESS_TAKES_PRIORITY:
 341       DCHECK_EQ(ACTIVE_TREE, tree_);
 342       return false;
 343     case NEW_CONTENT_TAKES_PRIORITY:
 344       DCHECK_EQ(PENDING_TREE, tree_);
 345       return false;
 346     case SAME_PRIORITY_FOR_BOTH_TREES:
 347       break;
 348     case NUM_TREE_PRIORITIES:
 349       NOTREACHED();
 350       break;
 351   }
 352
 353   // The priority for tile priority of a shared tile will be a combined
 354   // priority thus return shared tiles from a higher priority tree as
 355   // it is out of order for a lower priority tree.
 356   WhichTree twin_tree = tree_ == ACTIVE_TREE ? PENDING_TREE : ACTIVE_TREE;
 357   const TilePriority& priority = tile->priority(tree_);
 358   const TilePriority& twin_priority = tile->priority(twin_tree);
 359   if (priority.priority_bin != twin_priority.priority_bin)
 360     return priority.priority_bin > twin_priority.priority_bin;
 361   const bool occluded = tile->is_occluded(tree_);
 362   const bool twin_occluded = tile->is_occluded(twin_tree);
 363   if (occluded != twin_occluded)
 364     return occluded;
 365   if (priority.distance_to_visible != twin_priority.distance_to_visible)
 366     return priority.distance_to_visible > twin_priority.distance_to_visible;
 367
 368   // If priorities are the same, it does not matter which tree returns
 369   // the tile. Let's pick the pending tree.
 370   return tree_ != PENDING_TREE;
 371 }
 372
 373 size_t TilingSetEvictionQueue::TilingIndexWithRequiredForActivationTiles()
 374     const {
 375   // Returns the tiling index of the tiling with requuired for activation tiles.
 376   // If no such tiling exists, returns the past-the-last index (num_tilings).
 377   size_t num_tilings = tiling_set_->num_tilings();
 378
 379   if (tree_ == PENDING_TREE) {
 380     // For the pending tree, the tiling with required for activation tiles is
 381     // the high res one.
 382     PictureLayerTilingSet::TilingRange high_res_tiling_range =
 383         tiling_set_->GetTilingRange(PictureLayerTilingSet::HIGH_RES);
 384     if (high_res_tiling_range.start != high_res_tiling_range.end)
 385       return high_res_tiling_range.start;
 386   } else {
 387     DCHECK_EQ(ACTIVE_TREE, tree_);
 388     // Only pending tree tiles can be required for activation. They can appear
 389     // also in the active tree only if they are shared. If we skip all shared
 390     // tiles, there is no need to find them as they will not be returned.
 391     if (skip_all_shared_tiles_)
 392       return num_tilings;
 393
 394     // For the active tree, the tiling with required for activation tiles is
 395     // the one whose twin tiling is the high res pending tiling.
 396     for (size_t i = 0; i < num_tilings; ++i) {
 397       const PictureLayerTiling* tiling = tiling_set_->tiling_at(i);
 398       const PictureLayerTiling* pending_tiling =
 399           tiling_set_->client()->GetPendingOrActiveTwinTiling(tiling);
 400       if (pending_tiling && pending_tiling->resolution() == HIGH_RESOLUTION)
 401         return i;
 402     }
 403   }
 404
 405   return num_tilings;
 406 }
 407
 408 }  // namespace cc