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