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     : tree_(tiling_set->client()->GetTree()),
  42       skip_shared_out_of_order_tiles_(skip_shared_out_of_order_tiles),
  43       phase_(EVENTUALLY_RECT),
  44       current_tile_(nullptr) {
  45   // Early out if the layer has no tilings.
  46   if (!tiling_set->num_tilings())
  47     return;
  48   GenerateTilingOrder(tiling_set);
  49   eventually_iterator_ = EventuallyTilingIterator(
  50       &tilings_, tree_, skip_shared_out_of_order_tiles_);
  51   if (eventually_iterator_.done()) {
  52     AdvancePhase();
  53     return;
  54   }
  55   current_tile_ = *eventually_iterator_;
  56 }
  57
  58 TilingSetEvictionQueue::~TilingSetEvictionQueue() {
  59 }
  60
  61 void TilingSetEvictionQueue::GenerateTilingOrder(
  62     PictureLayerTilingSet* tiling_set) {
  63   tilings_.reserve(tiling_set->num_tilings());
  64   // Generate all of the tilings in the order described in the header comment
  65   // for this class.
  66   auto range =
  67       tiling_set->GetTilingRange(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES);
  68   for (int i = range.start; i < range.end; ++i)
  69     tilings_.push_back(tiling_set->tiling_at(i));
  70
  71   range = tiling_set->GetTilingRange(PictureLayerTilingSet::LOWER_THAN_LOW_RES);
  72   for (int i = range.end - 1; i >= range.start; --i)
  73     tilings_.push_back(tiling_set->tiling_at(i));
  74
  75   range = tiling_set->GetTilingRange(
  76       PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES);
  77   for (int i = range.end - 1; i >= range.start; --i)
  78     tilings_.push_back(tiling_set->tiling_at(i));
  79
  80   range = tiling_set->GetTilingRange(PictureLayerTilingSet::LOW_RES);
  81   for (int i = range.start; i < range.end; ++i)
  82     tilings_.push_back(tiling_set->tiling_at(i));
  83
  84   range = tiling_set->GetTilingRange(PictureLayerTilingSet::HIGH_RES);
  85   for (int i = range.start; i < range.end; ++i)
  86     tilings_.push_back(tiling_set->tiling_at(i));
  87   DCHECK_EQ(tiling_set->num_tilings(), tilings_.size());
  88 }
  89
  90 void TilingSetEvictionQueue::AdvancePhase() {
  91   current_tile_ = nullptr;
  92   while (!current_tile_ &&
  93          phase_ != VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED) {
  94     phase_ = static_cast<Phase>(phase_ + 1);
  95     switch (phase_) {
  96       case EVENTUALLY_RECT:
  97         NOTREACHED();
  98         break;
  99       case SOON_BORDER_RECT:
 100         soon_iterator_ = SoonBorderTilingIterator(
 101             &tilings_, tree_, skip_shared_out_of_order_tiles_);
 102         if (!soon_iterator_.done())
 103           current_tile_ = *soon_iterator_;
 104         break;
 105       case SKEWPORT_RECT:
 106         skewport_iterator_ = SkewportTilingIterator(
 107             &tilings_, tree_, skip_shared_out_of_order_tiles_);
 108         if (!skewport_iterator_.done())
 109           current_tile_ = *skewport_iterator_;
 110         break;
 111       case VISIBLE_RECT_OCCLUDED:
 112         visible_iterator_ = VisibleTilingIterator(
 113             &tilings_, tree_, skip_shared_out_of_order_tiles_,
 114             true /* return occluded tiles */,
 115             false /* return required for activation tiles */);
 116         if (!visible_iterator_.done())
 117           current_tile_ = *visible_iterator_;
 118         break;
 119       case VISIBLE_RECT_UNOCCLUDED:
 120         visible_iterator_ = VisibleTilingIterator(
 121             &tilings_, tree_, skip_shared_out_of_order_tiles_,
 122             false /* return occluded tiles */,
 123             false /* return required for activation tiles */);
 124         if (!visible_iterator_.done())
 125           current_tile_ = *visible_iterator_;
 126         break;
 127       case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED:
 128         visible_iterator_ = VisibleTilingIterator(
 129             &tilings_, tree_, skip_shared_out_of_order_tiles_,
 130             true /* return occluded tiles */,
 131             true /* return required for activation tiles */);
 132         if (!visible_iterator_.done())
 133           current_tile_ = *visible_iterator_;
 134         break;
 135       case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED:
 136         visible_iterator_ = VisibleTilingIterator(
 137             &tilings_, tree_, skip_shared_out_of_order_tiles_,
 138             false /* return occluded tiles */,
 139             true /* return required for activation tiles */);
 140         if (!visible_iterator_.done())
 141           current_tile_ = *visible_iterator_;
 142         break;
 143     }
 144   }
 145 }
 146
 147 bool TilingSetEvictionQueue::IsEmpty() const {
 148   return !current_tile_;
 149 }
 150
 151 Tile* TilingSetEvictionQueue::Top() {
 152   DCHECK(!IsEmpty());
 153   return current_tile_;
 154 }
 155
 156 const Tile* TilingSetEvictionQueue::Top() const {
 157   DCHECK(!IsEmpty());
 158   return current_tile_;
 159 }
 160
 161 void TilingSetEvictionQueue::Pop() {
 162   DCHECK(!IsEmpty());
 163   current_tile_ = nullptr;
 164   switch (phase_) {
 165     case EVENTUALLY_RECT:
 166       ++eventually_iterator_;
 167       if (!eventually_iterator_.done())
 168         current_tile_ = *eventually_iterator_;
 169       break;
 170     case SOON_BORDER_RECT:
 171       ++soon_iterator_;
 172       if (!soon_iterator_.done())
 173         current_tile_ = *soon_iterator_;
 174       break;
 175     case SKEWPORT_RECT:
 176       ++skewport_iterator_;
 177       if (!skewport_iterator_.done())
 178         current_tile_ = *skewport_iterator_;
 179       break;
 180     case VISIBLE_RECT_OCCLUDED:
 181     case VISIBLE_RECT_UNOCCLUDED:
 182     case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED:
 183     case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED:
 184       ++visible_iterator_;
 185       if (!visible_iterator_.done())
 186         current_tile_ = *visible_iterator_;
 187       break;
 188   }
 189   if (!current_tile_)
 190     AdvancePhase();
 191 }
 192
 193 // EvictionRectIterator
 194 TilingSetEvictionQueue::EvictionRectIterator::EvictionRectIterator()
 195     : tile_(nullptr),
 196       tilings_(nullptr),
 197       tree_(ACTIVE_TREE),
 198       skip_shared_out_of_order_tiles_(false),
 199       tiling_index_(0) {
 200 }
 201
 202 TilingSetEvictionQueue::EvictionRectIterator::EvictionRectIterator(
 203     std::vector<PictureLayerTiling*>* tilings,
 204     WhichTree tree,
 205     bool skip_shared_out_of_order_tiles)
 206     : tile_(nullptr),
 207       tilings_(tilings),
 208       tree_(tree),
 209       skip_shared_out_of_order_tiles_(skip_shared_out_of_order_tiles),
 210       tiling_index_(0) {
 211 }
 212
 213 template <typename TilingIteratorType>
 214 bool TilingSetEvictionQueue::EvictionRectIterator::AdvanceToNextTile(
 215     TilingIteratorType* iterator) {
 216   bool found_tile = false;
 217   while (!found_tile) {
 218     ++(*iterator);
 219     if (!(*iterator)) {
 220       tile_ = nullptr;
 221       break;
 222     }
 223     found_tile = GetFirstTileAndCheckIfValid(iterator);
 224   }
 225   return found_tile;
 226 }
 227
 228 template <typename TilingIteratorType>
 229 bool TilingSetEvictionQueue::EvictionRectIterator::GetFirstTileAndCheckIfValid(
 230     TilingIteratorType* iterator) {
 231   tile_ = (*tilings_)[tiling_index_]->TileAt(iterator->index_x(),
 232                                              iterator->index_y());
 233   // If there's nothing to evict, return false.
 234   if (!tile_ || !tile_->HasResource())
 235     return false;
 236   (*tilings_)[tiling_index_]->UpdateTileAndTwinPriority(tile_);
 237   // If the tile is out of order, return false.
 238   if (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tree_, tile_))
 239     return false;
 240   // In other cases, the tile we got is a viable candidate, return true.
 241   return true;
 242 }
 243
 244 // EventuallyTilingIterator
 245 TilingSetEvictionQueue::EventuallyTilingIterator::EventuallyTilingIterator(
 246     std::vector<PictureLayerTiling*>* tilings,
 247     WhichTree tree,
 248     bool skip_shared_out_of_order_tiles)
 249     : EvictionRectIterator(tilings, tree, skip_shared_out_of_order_tiles) {
 250   // Find the first tiling with a tile.
 251   while (tiling_index_ < tilings_->size()) {
 252     if (!((*tilings_))[tiling_index_]->has_eventually_rect_tiles()) {
 253       ++tiling_index_;
 254       continue;
 255     }
 256     iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 257         ((*tilings_))[tiling_index_]->tiling_data(),
 258         ((*tilings_))[tiling_index_]->current_eventually_rect(),
 259         ((*tilings_))[tiling_index_]->current_skewport_rect(),
 260         ((*tilings_))[tiling_index_]->current_soon_border_rect());
 261     if (!iterator_) {
 262       ++tiling_index_;
 263       continue;
 264     }
 265     break;
 266   }
 267   if (tiling_index_ >= tilings_->size())
 268     return;
 269   if (!GetFirstTileAndCheckIfValid(&iterator_))
 270     ++(*this);
 271 }
 272
 273 TilingSetEvictionQueue::EventuallyTilingIterator&
 274     TilingSetEvictionQueue::EventuallyTilingIterator::
 275     operator++() {
 276   bool found_tile = AdvanceToNextTile(&iterator_);
 277   while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
 278     ++tiling_index_;
 279     if (!((*tilings_))[tiling_index_]->has_eventually_rect_tiles())
 280       continue;
 281     iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 282         ((*tilings_))[tiling_index_]->tiling_data(),
 283         ((*tilings_))[tiling_index_]->current_eventually_rect(),
 284         ((*tilings_))[tiling_index_]->current_skewport_rect(),
 285         ((*tilings_))[tiling_index_]->current_soon_border_rect());
 286     if (!iterator_)
 287       continue;
 288     found_tile = GetFirstTileAndCheckIfValid(&iterator_);
 289     if (!found_tile)
 290       found_tile = AdvanceToNextTile(&iterator_);
 291   }
 292   return *this;
 293 }
 294
 295 // SoonBorderTilingIterator
 296 TilingSetEvictionQueue::SoonBorderTilingIterator::SoonBorderTilingIterator(
 297     std::vector<PictureLayerTiling*>* tilings,
 298     WhichTree tree,
 299     bool skip_shared_out_of_order_tiles)
 300     : EvictionRectIterator(tilings, tree, skip_shared_out_of_order_tiles) {
 301   // Find the first tiling with a tile.
 302   while (tiling_index_ < tilings_->size()) {
 303     if (!((*tilings_))[tiling_index_]->has_soon_border_rect_tiles()) {
 304       ++tiling_index_;
 305       continue;
 306     }
 307     iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 308         ((*tilings_))[tiling_index_]->tiling_data(),
 309         ((*tilings_))[tiling_index_]->current_soon_border_rect(),
 310         ((*tilings_))[tiling_index_]->current_skewport_rect(),
 311         ((*tilings_))[tiling_index_]->current_visible_rect());
 312     if (!iterator_) {
 313       ++tiling_index_;
 314       continue;
 315     }
 316     break;
 317   }
 318   if (tiling_index_ >= tilings_->size())
 319     return;
 320   if (!GetFirstTileAndCheckIfValid(&iterator_))
 321     ++(*this);
 322 }
 323
 324 TilingSetEvictionQueue::SoonBorderTilingIterator&
 325     TilingSetEvictionQueue::SoonBorderTilingIterator::
 326     operator++() {
 327   bool found_tile = AdvanceToNextTile(&iterator_);
 328   while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
 329     ++tiling_index_;
 330     if (!((*tilings_))[tiling_index_]->has_soon_border_rect_tiles())
 331       continue;
 332     iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 333         ((*tilings_))[tiling_index_]->tiling_data(),
 334         ((*tilings_))[tiling_index_]->current_soon_border_rect(),
 335         ((*tilings_))[tiling_index_]->current_skewport_rect(),
 336         ((*tilings_))[tiling_index_]->current_visible_rect());
 337     if (!iterator_)
 338       continue;
 339     found_tile = GetFirstTileAndCheckIfValid(&iterator_);
 340     if (!found_tile)
 341       found_tile = AdvanceToNextTile(&iterator_);
 342   }
 343   return *this;
 344 }
 345
 346 // SkewportTilingIterator
 347 TilingSetEvictionQueue::SkewportTilingIterator::SkewportTilingIterator(
 348     std::vector<PictureLayerTiling*>* tilings,
 349     WhichTree tree,
 350     bool skip_shared_out_of_order_tiles)
 351     : EvictionRectIterator(tilings, tree, skip_shared_out_of_order_tiles) {
 352   // Find the first tiling with a tile.
 353   while (tiling_index_ < tilings_->size()) {
 354     if (!((*tilings_))[tiling_index_]->has_skewport_rect_tiles()) {
 355       ++tiling_index_;
 356       continue;
 357     }
 358     iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 359         ((*tilings_))[tiling_index_]->tiling_data(),
 360         ((*tilings_))[tiling_index_]->current_skewport_rect(),
 361         ((*tilings_))[tiling_index_]->current_visible_rect(),
 362         ((*tilings_))[tiling_index_]->current_visible_rect());
 363     if (!iterator_) {
 364       ++tiling_index_;
 365       continue;
 366     }
 367     break;
 368   }
 369   if (tiling_index_ >= tilings_->size())
 370     return;
 371   if (!GetFirstTileAndCheckIfValid(&iterator_))
 372     ++(*this);
 373 }
 374
 375 TilingSetEvictionQueue::SkewportTilingIterator&
 376     TilingSetEvictionQueue::SkewportTilingIterator::
 377     operator++() {
 378   bool found_tile = AdvanceToNextTile(&iterator_);
 379   while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
 380     ++tiling_index_;
 381     if (!((*tilings_))[tiling_index_]->has_skewport_rect_tiles())
 382       continue;
 383     iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 384         ((*tilings_))[tiling_index_]->tiling_data(),
 385         ((*tilings_))[tiling_index_]->current_skewport_rect(),
 386         ((*tilings_))[tiling_index_]->current_visible_rect(),
 387         ((*tilings_))[tiling_index_]->current_visible_rect());
 388     if (!iterator_)
 389       continue;
 390     found_tile = GetFirstTileAndCheckIfValid(&iterator_);
 391     if (!found_tile)
 392       found_tile = AdvanceToNextTile(&iterator_);
 393   }
 394   return *this;
 395 }
 396
 397 // VisibleTilingIterator
 398 TilingSetEvictionQueue::VisibleTilingIterator::VisibleTilingIterator(
 399     std::vector<PictureLayerTiling*>* tilings,
 400     WhichTree tree,
 401     bool skip_shared_out_of_order_tiles,
 402     bool return_occluded_tiles,
 403     bool return_required_for_activation_tiles)
 404     : EvictionRectIterator(tilings, tree, skip_shared_out_of_order_tiles),
 405       return_occluded_tiles_(return_occluded_tiles),
 406       return_required_for_activation_tiles_(
 407           return_required_for_activation_tiles) {
 408   // Find the first tiling with a tile.
 409   while (tiling_index_ < tilings_->size()) {
 410     if (!((*tilings_))[tiling_index_]->has_visible_rect_tiles()) {
 411       ++tiling_index_;
 412       continue;
 413     }
 414     iterator_ = TilingData::Iterator(
 415         ((*tilings_))[tiling_index_]->tiling_data(),
 416         ((*tilings_))[tiling_index_]->current_visible_rect(), false);
 417     if (!iterator_) {
 418       ++tiling_index_;
 419       continue;
 420     }
 421     break;
 422   }
 423   if (tiling_index_ >= tilings_->size())
 424     return;
 425   if (!GetFirstTileAndCheckIfValid(&iterator_)) {
 426     ++(*this);
 427     return;
 428   }
 429   if (!TileMatchesRequiredFlags(tile_)) {
 430     ++(*this);
 431     return;
 432   }
 433 }
 434
 435 TilingSetEvictionQueue::VisibleTilingIterator&
 436     TilingSetEvictionQueue::VisibleTilingIterator::
 437     operator++() {
 438   bool found_tile = AdvanceToNextTile(&iterator_);
 439   while (found_tile && !TileMatchesRequiredFlags(tile_))
 440     found_tile = AdvanceToNextTile(&iterator_);
 441
 442   while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
 443     ++tiling_index_;
 444     if (!((*tilings_))[tiling_index_]->has_visible_rect_tiles())
 445       continue;
 446     iterator_ = TilingData::Iterator(
 447         ((*tilings_))[tiling_index_]->tiling_data(),
 448         ((*tilings_))[tiling_index_]->current_visible_rect(), false);
 449     if (!iterator_)
 450       continue;
 451     found_tile = GetFirstTileAndCheckIfValid(&iterator_);
 452     if (!found_tile)
 453       found_tile = AdvanceToNextTile(&iterator_);
 454     while (found_tile && !TileMatchesRequiredFlags(tile_))
 455       found_tile = AdvanceToNextTile(&iterator_);
 456   }
 457   return *this;
 458 }
 459
 460 bool TilingSetEvictionQueue::VisibleTilingIterator::TileMatchesRequiredFlags(
 461     const Tile* tile) const {
 462   bool activation_flag_matches =
 463       tile->required_for_activation() == return_required_for_activation_tiles_;
 464   bool occluded_flag_matches =
 465       tile->is_occluded(tree_) == return_occluded_tiles_;
 466   return activation_flag_matches && occluded_flag_matches;
 467 }
 468
 469 }  // namespace cc