diff options
author | vmpstr <vmpstr@chromium.org> | 2015-04-08 14:56:42 -0700 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2015-04-08 21:57:08 +0000 |
commit | 58d6a71707faa1ca205cfcd8de181ef13fe6b7a8 (patch) | |
tree | 9ee60587ac88078feab5d2e778b0535780a37dbf | |
parent | b05eee2385af9905d04b350b27f89255833fa4b3 (diff) | |
download | chromium_src-58d6a71707faa1ca205cfcd8de181ef13fe6b7a8.zip chromium_src-58d6a71707faa1ca205cfcd8de181ef13fe6b7a8.tar.gz chromium_src-58d6a71707faa1ca205cfcd8de181ef13fe6b7a8.tar.bz2 |
cc: Rework tiling set eviction iterator.
This patch changes the way the tiling set eviction iterators work. It mostly
restructures how each phase is processed in order to allow easier changes
in the future.
High level summary of changes:
- Create helper iterators that can process individual phases
- Preprocess the order in which tilings are processed
- Define explicit enums for combinations of phases, instead of an enum + flags
R=enne, danakj
Review URL: https://codereview.chromium.org/1038793002
Cr-Commit-Position: refs/heads/master@{#324290}
-rw-r--r-- | cc/resources/picture_layer_tiling.h | 1 | ||||
-rw-r--r-- | cc/resources/picture_layer_tiling_set.h | 6 | ||||
-rw-r--r-- | cc/resources/picture_layer_tiling_set_unittest.cc | 66 | ||||
-rw-r--r-- | cc/resources/tiling_set_eviction_queue.cc | 607 | ||||
-rw-r--r-- | cc/resources/tiling_set_eviction_queue.h | 216 |
5 files changed, 561 insertions, 335 deletions
diff --git a/cc/resources/picture_layer_tiling.h b/cc/resources/picture_layer_tiling.h index c05185a..34e7def 100644 --- a/cc/resources/picture_layer_tiling.h +++ b/cc/resources/picture_layer_tiling.h @@ -91,6 +91,7 @@ class CC_EXPORT PictureLayerTiling { gfx::Rect live_tiles_rect() const { return live_tiles_rect_; } gfx::Size tile_size() const { return tiling_data_.max_texture_size(); } float contents_scale() const { return contents_scale_; } + const TilingData* tiling_data() const { return &tiling_data_; } Tile* TileAt(int i, int j) const { TileMap::const_iterator iter = tiles_.find(TileMapKey(i, j)); diff --git a/cc/resources/picture_layer_tiling_set.h b/cc/resources/picture_layer_tiling_set.h index d4d55a3..cf95935 100644 --- a/cc/resources/picture_layer_tiling_set.h +++ b/cc/resources/picture_layer_tiling_set.h @@ -31,10 +31,10 @@ class CC_EXPORT PictureLayerTilingSet { LOWER_THAN_LOW_RES }; struct TilingRange { - TilingRange(size_t start, size_t end) : start(start), end(end) {} + TilingRange(int start, int end) : start(start), end(end) {} - size_t start; - size_t end; + int start; + int end; }; static scoped_ptr<PictureLayerTilingSet> Create( diff --git a/cc/resources/picture_layer_tiling_set_unittest.cc b/cc/resources/picture_layer_tiling_set_unittest.cc index 2eceb71..7c68611 100644 --- a/cc/resources/picture_layer_tiling_set_unittest.cc +++ b/cc/resources/picture_layer_tiling_set_unittest.cc @@ -86,26 +86,26 @@ TEST(PictureLayerTilingSetTest, TilingRange) { higher_than_high_res_range = set->GetTilingRange(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES); - EXPECT_EQ(0u, higher_than_high_res_range.start); - EXPECT_EQ(1u, higher_than_high_res_range.end); + EXPECT_EQ(0, higher_than_high_res_range.start); + EXPECT_EQ(1, higher_than_high_res_range.end); high_res_range = set->GetTilingRange(PictureLayerTilingSet::HIGH_RES); - EXPECT_EQ(1u, high_res_range.start); - EXPECT_EQ(2u, high_res_range.end); + EXPECT_EQ(1, high_res_range.start); + EXPECT_EQ(2, high_res_range.end); between_high_and_low_res_range = set->GetTilingRange(PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES); - EXPECT_EQ(2u, between_high_and_low_res_range.start); - EXPECT_EQ(3u, between_high_and_low_res_range.end); + EXPECT_EQ(2, between_high_and_low_res_range.start); + EXPECT_EQ(3, between_high_and_low_res_range.end); low_res_range = set->GetTilingRange(PictureLayerTilingSet::LOW_RES); - EXPECT_EQ(3u, low_res_range.start); - EXPECT_EQ(4u, low_res_range.end); + EXPECT_EQ(3, low_res_range.start); + EXPECT_EQ(4, low_res_range.end); lower_than_low_res_range = set->GetTilingRange(PictureLayerTilingSet::LOWER_THAN_LOW_RES); - EXPECT_EQ(4u, lower_than_low_res_range.start); - EXPECT_EQ(5u, lower_than_low_res_range.end); + EXPECT_EQ(4, lower_than_low_res_range.start); + EXPECT_EQ(5, lower_than_low_res_range.end); scoped_ptr<PictureLayerTilingSet> set_without_low_res = CreateTilingSet(&client); @@ -117,26 +117,26 @@ TEST(PictureLayerTilingSetTest, TilingRange) { higher_than_high_res_range = set_without_low_res->GetTilingRange( PictureLayerTilingSet::HIGHER_THAN_HIGH_RES); - EXPECT_EQ(0u, higher_than_high_res_range.start); - EXPECT_EQ(1u, higher_than_high_res_range.end); + EXPECT_EQ(0, higher_than_high_res_range.start); + EXPECT_EQ(1, higher_than_high_res_range.end); high_res_range = set_without_low_res->GetTilingRange(PictureLayerTilingSet::HIGH_RES); - EXPECT_EQ(1u, high_res_range.start); - EXPECT_EQ(2u, high_res_range.end); + EXPECT_EQ(1, high_res_range.start); + EXPECT_EQ(2, high_res_range.end); between_high_and_low_res_range = set_without_low_res->GetTilingRange( PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES); - EXPECT_EQ(2u, between_high_and_low_res_range.start); - EXPECT_EQ(4u, between_high_and_low_res_range.end); + EXPECT_EQ(2, between_high_and_low_res_range.start); + EXPECT_EQ(4, between_high_and_low_res_range.end); low_res_range = set_without_low_res->GetTilingRange(PictureLayerTilingSet::LOW_RES); - EXPECT_EQ(0u, low_res_range.end - low_res_range.start); + EXPECT_EQ(0, low_res_range.end - low_res_range.start); lower_than_low_res_range = set_without_low_res->GetTilingRange( PictureLayerTilingSet::LOWER_THAN_LOW_RES); - EXPECT_EQ(0u, lower_than_low_res_range.end - lower_than_low_res_range.start); + EXPECT_EQ(0, lower_than_low_res_range.end - lower_than_low_res_range.start); scoped_ptr<PictureLayerTilingSet> set_with_only_high_and_low_res = CreateTilingSet(&client); @@ -147,28 +147,28 @@ TEST(PictureLayerTilingSetTest, TilingRange) { higher_than_high_res_range = set_with_only_high_and_low_res->GetTilingRange( PictureLayerTilingSet::HIGHER_THAN_HIGH_RES); - EXPECT_EQ(0u, + EXPECT_EQ(0, higher_than_high_res_range.end - higher_than_high_res_range.start); high_res_range = set_with_only_high_and_low_res->GetTilingRange( PictureLayerTilingSet::HIGH_RES); - EXPECT_EQ(0u, high_res_range.start); - EXPECT_EQ(1u, high_res_range.end); + EXPECT_EQ(0, high_res_range.start); + EXPECT_EQ(1, high_res_range.end); between_high_and_low_res_range = set_with_only_high_and_low_res->GetTilingRange( PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES); - EXPECT_EQ(0u, between_high_and_low_res_range.end - - between_high_and_low_res_range.start); + EXPECT_EQ(0, between_high_and_low_res_range.end - + between_high_and_low_res_range.start); low_res_range = set_with_only_high_and_low_res->GetTilingRange( PictureLayerTilingSet::LOW_RES); - EXPECT_EQ(1u, low_res_range.start); - EXPECT_EQ(2u, low_res_range.end); + EXPECT_EQ(1, low_res_range.start); + EXPECT_EQ(2, low_res_range.end); lower_than_low_res_range = set_with_only_high_and_low_res->GetTilingRange( PictureLayerTilingSet::LOWER_THAN_LOW_RES); - EXPECT_EQ(0u, lower_than_low_res_range.end - lower_than_low_res_range.start); + EXPECT_EQ(0, lower_than_low_res_range.end - lower_than_low_res_range.start); scoped_ptr<PictureLayerTilingSet> set_with_only_high_res = CreateTilingSet(&client); @@ -177,26 +177,26 @@ TEST(PictureLayerTilingSetTest, TilingRange) { higher_than_high_res_range = set_with_only_high_res->GetTilingRange( PictureLayerTilingSet::HIGHER_THAN_HIGH_RES); - EXPECT_EQ(0u, + EXPECT_EQ(0, higher_than_high_res_range.end - higher_than_high_res_range.start); high_res_range = set_with_only_high_res->GetTilingRange(PictureLayerTilingSet::HIGH_RES); - EXPECT_EQ(0u, high_res_range.start); - EXPECT_EQ(1u, high_res_range.end); + EXPECT_EQ(0, high_res_range.start); + EXPECT_EQ(1, high_res_range.end); between_high_and_low_res_range = set_with_only_high_res->GetTilingRange( PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES); - EXPECT_EQ(0u, between_high_and_low_res_range.end - - between_high_and_low_res_range.start); + EXPECT_EQ(0, between_high_and_low_res_range.end - + between_high_and_low_res_range.start); low_res_range = set_with_only_high_res->GetTilingRange(PictureLayerTilingSet::LOW_RES); - EXPECT_EQ(0u, low_res_range.end - low_res_range.start); + EXPECT_EQ(0, low_res_range.end - low_res_range.start); lower_than_low_res_range = set_with_only_high_res->GetTilingRange( PictureLayerTilingSet::LOWER_THAN_LOW_RES); - EXPECT_EQ(0u, lower_than_low_res_range.end - lower_than_low_res_range.start); + EXPECT_EQ(0, lower_than_low_res_range.end - lower_than_low_res_range.start); } class PictureLayerTilingSetTestWithResources : public testing::Test { diff --git a/cc/resources/tiling_set_eviction_queue.cc b/cc/resources/tiling_set_eviction_queue.cc index 5ee678b..43d085b 100644 --- a/cc/resources/tiling_set_eviction_queue.cc +++ b/cc/resources/tiling_set_eviction_queue.cc @@ -38,285 +38,432 @@ bool IsSharedOutOfOrderTile(WhichTree tree, const Tile* tile) { TilingSetEvictionQueue::TilingSetEvictionQueue( PictureLayerTilingSet* tiling_set, bool skip_shared_out_of_order_tiles) - : tiling_set_(tiling_set), - tree_(tiling_set->client()->GetTree()), + : tree_(tiling_set->client()->GetTree()), skip_shared_out_of_order_tiles_(skip_shared_out_of_order_tiles), - processing_soon_border_rect_(false), - processing_required_for_activation_tiles_(false), - current_priority_bin_(TilePriority::EVENTUALLY), - current_tiling_index_(0u), - current_tiling_range_type_(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES), - current_eviction_tile_(nullptr) { + phase_(EVENTUALLY_RECT), + current_tile_(nullptr) { // Early out if the layer has no tilings. - if (!tiling_set_->num_tilings()) + if (!tiling_set->num_tilings()) return; - - current_tiling_index_ = CurrentTilingRange().start - 1u; - AdvanceToNextValidTiling(); + GenerateTilingOrder(tiling_set); + eventually_iterator_ = EventuallyTilingIterator( + &tilings_, tree_, skip_shared_out_of_order_tiles_); + if (eventually_iterator_.done()) { + AdvancePhase(); + return; + } + current_tile_ = *eventually_iterator_; } TilingSetEvictionQueue::~TilingSetEvictionQueue() { } -bool TilingSetEvictionQueue::IsEmpty() const { - return !current_eviction_tile_; +void TilingSetEvictionQueue::GenerateTilingOrder( + PictureLayerTilingSet* tiling_set) { + tilings_.reserve(tiling_set->num_tilings()); + // Generate all of the tilings in the order described in the header comment + // for this class. + auto range = + tiling_set->GetTilingRange(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES); + for (int i = range.start; i < range.end; ++i) + tilings_.push_back(tiling_set->tiling_at(i)); + + range = tiling_set->GetTilingRange(PictureLayerTilingSet::LOWER_THAN_LOW_RES); + for (int i = range.end - 1; i >= range.start; --i) + tilings_.push_back(tiling_set->tiling_at(i)); + + range = tiling_set->GetTilingRange( + PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES); + for (int i = range.end - 1; i >= range.start; --i) + tilings_.push_back(tiling_set->tiling_at(i)); + + range = tiling_set->GetTilingRange(PictureLayerTilingSet::LOW_RES); + for (int i = range.start; i < range.end; ++i) + tilings_.push_back(tiling_set->tiling_at(i)); + + range = tiling_set->GetTilingRange(PictureLayerTilingSet::HIGH_RES); + for (int i = range.start; i < range.end; ++i) + tilings_.push_back(tiling_set->tiling_at(i)); + DCHECK_EQ(tiling_set->num_tilings(), tilings_.size()); } -void TilingSetEvictionQueue::Pop() { - DCHECK(!IsEmpty()); +void TilingSetEvictionQueue::AdvancePhase() { + current_tile_ = nullptr; + while (!current_tile_ && + phase_ != VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED) { + phase_ = static_cast<Phase>(phase_ + 1); + switch (phase_) { + case EVENTUALLY_RECT: + NOTREACHED(); + break; + case SOON_BORDER_RECT: + soon_iterator_ = SoonBorderTilingIterator( + &tilings_, tree_, skip_shared_out_of_order_tiles_); + if (!soon_iterator_.done()) + current_tile_ = *soon_iterator_; + break; + case SKEWPORT_RECT: + skewport_iterator_ = SkewportTilingIterator( + &tilings_, tree_, skip_shared_out_of_order_tiles_); + if (!skewport_iterator_.done()) + current_tile_ = *skewport_iterator_; + break; + case VISIBLE_RECT_OCCLUDED: + visible_iterator_ = VisibleTilingIterator( + &tilings_, tree_, skip_shared_out_of_order_tiles_, + true /* return occluded tiles */, + false /* return required for activation tiles */); + if (!visible_iterator_.done()) + current_tile_ = *visible_iterator_; + break; + case VISIBLE_RECT_UNOCCLUDED: + visible_iterator_ = VisibleTilingIterator( + &tilings_, tree_, skip_shared_out_of_order_tiles_, + false /* return occluded tiles */, + false /* return required for activation tiles */); + if (!visible_iterator_.done()) + current_tile_ = *visible_iterator_; + break; + case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED: + visible_iterator_ = VisibleTilingIterator( + &tilings_, tree_, skip_shared_out_of_order_tiles_, + true /* return occluded tiles */, + true /* return required for activation tiles */); + if (!visible_iterator_.done()) + current_tile_ = *visible_iterator_; + break; + case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED: + visible_iterator_ = VisibleTilingIterator( + &tilings_, tree_, skip_shared_out_of_order_tiles_, + false /* return occluded tiles */, + true /* return required for activation tiles */); + if (!visible_iterator_.done()) + current_tile_ = *visible_iterator_; + break; + } + } +} - if (!AdvanceToNextEvictionTile()) - AdvanceToNextValidTiling(); +bool TilingSetEvictionQueue::IsEmpty() const { + return !current_tile_; } Tile* TilingSetEvictionQueue::Top() { DCHECK(!IsEmpty()); - return current_eviction_tile_; + return current_tile_; } const Tile* TilingSetEvictionQueue::Top() const { DCHECK(!IsEmpty()); - return current_eviction_tile_; + return current_tile_; } -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_tiles_; - - 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->HasResource()) - continue; - current_tiling_->UpdateTileAndTwinPriority(tile); - if (skip_shared_out_of_order_tiles_ && - IsSharedOutOfOrderTile(tree_, tile)) - continue; - DCHECK_EQ(tile->required_for_activation(), required_for_activation); - current_eviction_tile_ = tile; - return true; - } - 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( - ¤t_tiling_->tiling_data_, - current_tiling_->current_skewport_rect_, - current_tiling_->current_visible_rect_, - current_tiling_->current_visible_rect_); - continue; - } +void TilingSetEvictionQueue::Pop() { + DCHECK(!IsEmpty()); + current_tile_ = nullptr; + switch (phase_) { + case EVENTUALLY_RECT: + ++eventually_iterator_; + if (!eventually_iterator_.done()) + current_tile_ = *eventually_iterator_; + break; + case SOON_BORDER_RECT: + ++soon_iterator_; + if (!soon_iterator_.done()) + current_tile_ = *soon_iterator_; + break; + case SKEWPORT_RECT: + ++skewport_iterator_; + if (!skewport_iterator_.done()) + current_tile_ = *skewport_iterator_; + break; + case VISIBLE_RECT_OCCLUDED: + case VISIBLE_RECT_UNOCCLUDED: + case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED: + case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED: + ++visible_iterator_; + if (!visible_iterator_.done()) + current_tile_ = *visible_iterator_; + break; + } + if (!current_tile_) + AdvancePhase(); +} + +// EvictionRectIterator +TilingSetEvictionQueue::EvictionRectIterator::EvictionRectIterator() + : tile_(nullptr), + tilings_(nullptr), + tree_(ACTIVE_TREE), + skip_shared_out_of_order_tiles_(false), + tiling_index_(0) { +} + +TilingSetEvictionQueue::EvictionRectIterator::EvictionRectIterator( + std::vector<PictureLayerTiling*>* tilings, + WhichTree tree, + bool skip_shared_out_of_order_tiles) + : tile_(nullptr), + tilings_(tilings), + tree_(tree), + skip_shared_out_of_order_tiles_(skip_shared_out_of_order_tiles), + tiling_index_(0) { +} + +template <typename TilingIteratorType> +bool TilingSetEvictionQueue::EvictionRectIterator::AdvanceToNextTile( + TilingIteratorType* iterator) { + bool found_tile = false; + while (!found_tile) { + ++(*iterator); + if (!(*iterator)) { + tile_ = nullptr; + break; } - break; + found_tile = GetFirstTileAndCheckIfValid(iterator); } + return found_tile; +} + +template <typename TilingIteratorType> +bool TilingSetEvictionQueue::EvictionRectIterator::GetFirstTileAndCheckIfValid( + TilingIteratorType* iterator) { + tile_ = (*tilings_)[tiling_index_]->TileAt(iterator->index_x(), + iterator->index_y()); + // If there's nothing to evict, return false. + if (!tile_ || !tile_->HasResource()) + return false; + (*tilings_)[tiling_index_]->UpdateTileAndTwinPriority(tile_); + // If the tile is out of order, return false. + if (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tree_, tile_)) + return false; + // In other cases, the tile we got is a viable candidate, return true. + return true; +} - TilePriority::PriorityBin max_tile_priority_bin = - current_tiling_->client_->GetMaxTilePriorityBin(); - while (visible_iterator_) { - 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->HasResource()) +// EventuallyTilingIterator +TilingSetEvictionQueue::EventuallyTilingIterator::EventuallyTilingIterator( + std::vector<PictureLayerTiling*>* tilings, + WhichTree tree, + bool skip_shared_out_of_order_tiles) + : EvictionRectIterator(tilings, tree, skip_shared_out_of_order_tiles) { + // Find the first tiling with a tile. + while (tiling_index_ < tilings_->size()) { + if (!((*tilings_))[tiling_index_]->has_eventually_rect_tiles()) { + ++tiling_index_; continue; - // If the max tile priority is not NOW, updated priorities for tiles - // returned by the visible iterator will not have NOW (but EVENTUALLY) - // priority bin and cannot therefore be required for activation tiles nor - // occluded NOW tiles in the current tiling. - if (max_tile_priority_bin <= TilePriority::NOW) { - // If the current tiling is a pending tree tiling, required for - // activation tiles can be detected without updating tile priorities. - if (tree_ == PENDING_TREE && - current_tiling_->IsTileRequiredForActivationIfVisible(tile) != - required_for_activation) { - continue; - } - // Unoccluded NOW tiles should be evicted (and thus returned) only after - // all occluded NOW tiles. - if (!current_tiling_->IsTileOccluded(tile)) { - unoccluded_now_tiles_.push_back(tile); - continue; - } } - current_tiling_->UpdateTileAndTwinPriority(tile); - if (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tree_, tile)) - continue; - if (tile->required_for_activation() != required_for_activation) + iterator_ = TilingData::ReverseSpiralDifferenceIterator( + ((*tilings_))[tiling_index_]->tiling_data(), + ((*tilings_))[tiling_index_]->current_eventually_rect(), + ((*tilings_))[tiling_index_]->current_skewport_rect(), + ((*tilings_))[tiling_index_]->current_soon_border_rect()); + if (!iterator_) { + ++tiling_index_; continue; - current_eviction_tile_ = tile; - return true; + } + break; } + if (tiling_index_ >= tilings_->size()) + return; + if (!GetFirstTileAndCheckIfValid(&iterator_)) + ++(*this); +} - while (!unoccluded_now_tiles_.empty()) { - // All (unoccluded) NOW tiles have the same priority bin (NOW) and the same - // distance to visible (0.0), so it does not matter that tiles are popped - // in reversed (FILO) order. - Tile* tile = unoccluded_now_tiles_.back(); - unoccluded_now_tiles_.pop_back(); - DCHECK(tile); - if (!tile->HasResource()) - continue; - current_tiling_->UpdateTileAndTwinPriority(tile); - if (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tree_, tile)) +TilingSetEvictionQueue::EventuallyTilingIterator& + TilingSetEvictionQueue::EventuallyTilingIterator:: + operator++() { + bool found_tile = AdvanceToNextTile(&iterator_); + while (!found_tile && (tiling_index_ + 1) < tilings_->size()) { + ++tiling_index_; + if (!((*tilings_))[tiling_index_]->has_eventually_rect_tiles()) continue; - if (tile->required_for_activation() != required_for_activation) + iterator_ = TilingData::ReverseSpiralDifferenceIterator( + ((*tilings_))[tiling_index_]->tiling_data(), + ((*tilings_))[tiling_index_]->current_eventually_rect(), + ((*tilings_))[tiling_index_]->current_skewport_rect(), + ((*tilings_))[tiling_index_]->current_soon_border_rect()); + if (!iterator_) continue; - current_eviction_tile_ = tile; - return true; + found_tile = GetFirstTileAndCheckIfValid(&iterator_); + if (!found_tile) + found_tile = AdvanceToNextTile(&iterator_); } - - current_eviction_tile_ = nullptr; - return false; + return *this; } -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); - - switch (current_priority_bin_) { - case TilePriority::EVENTUALLY: - current_priority_bin_ = TilePriority::SOON; - return true; - case TilePriority::SOON: - current_priority_bin_ = TilePriority::NOW; - return true; - case TilePriority::NOW: - return false; +// SoonBorderTilingIterator +TilingSetEvictionQueue::SoonBorderTilingIterator::SoonBorderTilingIterator( + std::vector<PictureLayerTiling*>* tilings, + WhichTree tree, + bool skip_shared_out_of_order_tiles) + : EvictionRectIterator(tilings, tree, skip_shared_out_of_order_tiles) { + // Find the first tiling with a tile. + while (tiling_index_ < tilings_->size()) { + if (!((*tilings_))[tiling_index_]->has_soon_border_rect_tiles()) { + ++tiling_index_; + continue; + } + iterator_ = TilingData::ReverseSpiralDifferenceIterator( + ((*tilings_))[tiling_index_]->tiling_data(), + ((*tilings_))[tiling_index_]->current_soon_border_rect(), + ((*tilings_))[tiling_index_]->current_skewport_rect(), + ((*tilings_))[tiling_index_]->current_visible_rect()); + if (!iterator_) { + ++tiling_index_; + continue; + } + break; } - NOTREACHED(); - return false; + if (tiling_index_ >= tilings_->size()) + return; + if (!GetFirstTileAndCheckIfValid(&iterator_)) + ++(*this); } -bool TilingSetEvictionQueue::AdvanceToNextTilingRangeType() { - // 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: - // Process required for activation tiles (unless that has already been - // done). Only pending tree NOW tiles may be required for activation. - if (!processing_required_for_activation_tiles_ && - current_priority_bin_ == TilePriority::NOW && tree_ == PENDING_TREE) { - processing_required_for_activation_tiles_ = true; - return true; - } - processing_required_for_activation_tiles_ = false; - - if (!AdvanceToNextPriorityBin()) - return false; - - current_tiling_range_type_ = PictureLayerTilingSet::HIGHER_THAN_HIGH_RES; - return true; +TilingSetEvictionQueue::SoonBorderTilingIterator& + TilingSetEvictionQueue::SoonBorderTilingIterator:: + operator++() { + bool found_tile = AdvanceToNextTile(&iterator_); + while (!found_tile && (tiling_index_ + 1) < tilings_->size()) { + ++tiling_index_; + if (!((*tilings_))[tiling_index_]->has_soon_border_rect_tiles()) + continue; + iterator_ = TilingData::ReverseSpiralDifferenceIterator( + ((*tilings_))[tiling_index_]->tiling_data(), + ((*tilings_))[tiling_index_]->current_soon_border_rect(), + ((*tilings_))[tiling_index_]->current_skewport_rect(), + ((*tilings_))[tiling_index_]->current_visible_rect()); + if (!iterator_) + continue; + found_tile = GetFirstTileAndCheckIfValid(&iterator_); + if (!found_tile) + found_tile = AdvanceToNextTile(&iterator_); } - NOTREACHED(); - return false; + return *this; } -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 priority bin until - // the next eviction tile is found. This is done only after all eviction - // 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; +// SkewportTilingIterator +TilingSetEvictionQueue::SkewportTilingIterator::SkewportTilingIterator( + std::vector<PictureLayerTiling*>* tilings, + WhichTree tree, + bool skip_shared_out_of_order_tiles) + : EvictionRectIterator(tilings, tree, skip_shared_out_of_order_tiles) { + // Find the first tiling with a tile. + while (tiling_index_ < tilings_->size()) { + if (!((*tilings_))[tiling_index_]->has_skewport_rect_tiles()) { + ++tiling_index_; + continue; } - current_tiling_ = tiling_set_->tiling_at(CurrentTilingIndex()); - - switch (current_priority_bin_) { - case TilePriority::EVENTUALLY: - if (current_tiling_->has_eventually_rect_tiles_) { - spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator( - ¤t_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( - ¤t_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(¤t_tiling_->tiling_data_, - current_tiling_->current_visible_rect_, - false /* include_borders */); - if (AdvanceToNextEvictionTile()) - return true; - } - break; + iterator_ = TilingData::ReverseSpiralDifferenceIterator( + ((*tilings_))[tiling_index_]->tiling_data(), + ((*tilings_))[tiling_index_]->current_skewport_rect(), + ((*tilings_))[tiling_index_]->current_visible_rect(), + ((*tilings_))[tiling_index_]->current_visible_rect()); + if (!iterator_) { + ++tiling_index_; + continue; } + break; } + if (tiling_index_ >= tilings_->size()) + return; + if (!GetFirstTileAndCheckIfValid(&iterator_)) + ++(*this); } -PictureLayerTilingSet::TilingRange -TilingSetEvictionQueue::CurrentTilingRange() const { - return tiling_set_->GetTilingRange(current_tiling_range_type_); +TilingSetEvictionQueue::SkewportTilingIterator& + TilingSetEvictionQueue::SkewportTilingIterator:: + operator++() { + bool found_tile = AdvanceToNextTile(&iterator_); + while (!found_tile && (tiling_index_ + 1) < tilings_->size()) { + ++tiling_index_; + if (!((*tilings_))[tiling_index_]->has_skewport_rect_tiles()) + continue; + iterator_ = TilingData::ReverseSpiralDifferenceIterator( + ((*tilings_))[tiling_index_]->tiling_data(), + ((*tilings_))[tiling_index_]->current_skewport_rect(), + ((*tilings_))[tiling_index_]->current_visible_rect(), + ((*tilings_))[tiling_index_]->current_visible_rect()); + if (!iterator_) + continue; + found_tile = GetFirstTileAndCheckIfValid(&iterator_); + if (!found_tile) + found_tile = AdvanceToNextTile(&iterator_); + } + return *this; } -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; +// VisibleTilingIterator +TilingSetEvictionQueue::VisibleTilingIterator::VisibleTilingIterator( + std::vector<PictureLayerTiling*>* tilings, + WhichTree tree, + bool skip_shared_out_of_order_tiles, + bool return_occluded_tiles, + bool return_required_for_activation_tiles) + : EvictionRectIterator(tilings, tree, skip_shared_out_of_order_tiles), + return_occluded_tiles_(return_occluded_tiles), + return_required_for_activation_tiles_( + return_required_for_activation_tiles) { + // Find the first tiling with a tile. + while (tiling_index_ < tilings_->size()) { + if (!((*tilings_))[tiling_index_]->has_visible_rect_tiles()) { + ++tiling_index_; + continue; + } + iterator_ = TilingData::Iterator( + ((*tilings_))[tiling_index_]->tiling_data(), + ((*tilings_))[tiling_index_]->current_visible_rect(), false); + if (!iterator_) { + ++tiling_index_; + continue; } + break; + } + if (tiling_index_ >= tilings_->size()) + return; + if (!GetFirstTileAndCheckIfValid(&iterator_)) { + ++(*this); + return; } - NOTREACHED(); - return 0; + if (!TileMatchesRequiredFlags(tile_)) { + ++(*this); + return; + } +} + +TilingSetEvictionQueue::VisibleTilingIterator& + TilingSetEvictionQueue::VisibleTilingIterator:: + operator++() { + bool found_tile = AdvanceToNextTile(&iterator_); + while (found_tile && !TileMatchesRequiredFlags(tile_)) + found_tile = AdvanceToNextTile(&iterator_); + + while (!found_tile && (tiling_index_ + 1) < tilings_->size()) { + ++tiling_index_; + if (!((*tilings_))[tiling_index_]->has_visible_rect_tiles()) + continue; + iterator_ = TilingData::Iterator( + ((*tilings_))[tiling_index_]->tiling_data(), + ((*tilings_))[tiling_index_]->current_visible_rect(), false); + if (!iterator_) + continue; + found_tile = GetFirstTileAndCheckIfValid(&iterator_); + if (!found_tile) + found_tile = AdvanceToNextTile(&iterator_); + while (found_tile && !TileMatchesRequiredFlags(tile_)) + found_tile = AdvanceToNextTile(&iterator_); + } + return *this; +} + +bool TilingSetEvictionQueue::VisibleTilingIterator::TileMatchesRequiredFlags( + const Tile* tile) const { + bool activation_flag_matches = + tile->required_for_activation() == return_required_for_activation_tiles_; + bool occluded_flag_matches = + tile->is_occluded(tree_) == return_occluded_tiles_; + return activation_flag_matches && occluded_flag_matches; } } // namespace cc diff --git a/cc/resources/tiling_set_eviction_queue.h b/cc/resources/tiling_set_eviction_queue.h index 6662a75..439bdbb 100644 --- a/cc/resources/tiling_set_eviction_queue.h +++ b/cc/resources/tiling_set_eviction_queue.h @@ -13,58 +13,51 @@ namespace cc { // This eviction queue returned tiles from all tilings in a tiling set in -// the following order: -// 1) Eventually rect tiles (EVENTUALLY tiles). -// 1) Eventually rect tiles not required for activation from each tiling in -// the tiling set, in turn, in the following order: -// 1) the first higher than high res tiling, the second one and so on -// 2) the first lower than low res tiling, the second one and so on -// 3) the first between high and low res tiling, the second one and so on -// 4) low res tiling -// 5) high res tiling -// 2) Eventually rect tiles required for activation from the tiling with -// required for activation tiles. In the case of a pending tree tiling -// set that is the high res tiling. In the case of an active tree tiling -// set that is a tiling whose twin tiling is a pending tree high res -// tiling. -// 2) Soon border rect and skewport rect tiles (whose priority bin is SOON -// unless the max tile priority bin is lowered by PictureLayerTilingClient). -// 1) Soon border rect and skewport rect tiles not required for activation -// from each tiling in the tiling set. -// * Tilings are iterated in the same order as in the case of eventually -// rect tiles not required for activation. -// * For each tiling, first soon border rect tiles and then skewport -// rect tiles are returned. -// 2) Soon border rect and skewport rect tiles required for activation from -// the tiling with required for activation tiles. -// * First soon border rect tiles and then skewport rect tiles are -// returned. -// 3) Visible rect tiles (whose priority bin is NOW unless the max tile -// priority bin is lowered by PictureLayerTilingClient). -// 1) Visible rect tiles not required for activation from each tiling in -// the tiling set. -// * Tilings are iterated in the same order as in the case of eventually -// rect tiles not required for activation. -// * For each tiling, first occluded tiles and then unoccluded tiles -// are returned. -// 2) Visible rect tiles required for activation from the tiling with -// required for activation tiles. -// * First occluded tiles and then unoccluded tiles are returned. -// If the max tile priority bin is lowered by PictureLayerTilingClient, -// occlusion is not taken into account as occlusion is meaningful only for -// NOW tiles. +// the order in which the tiles should be evicted. It can be thought of as the +// following: +// for all phases: +// for all ordered tilings: +// yield the next tile for the given phase from the given tiling // -// Within each tiling and tile priority rect, tiles are returned in reverse -// spiral order i.e. in (mostly) decreasing distance-to-visible order. +// Phases are the following (in order in which they are processed): +// EVENTUALLY_RECT - Tiles in the eventually region of the tiling. +// SOON_BORDER_RECT - Tiles in the prepainting skirt of the tiling. +// SKEWPORT_RECT - Tiles in the skewport of the tiling. +// VISIBLE_RECT_OCCLUDED - Occluded, not required for activation, visible tiles. +// VISIBLE_RECT_UNOCCLUDED - Unoccluded, not required for activation, visible +// tiles. +// VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED - Occluded, but required for +// activation, visible tiles. This can happen when an active tree tile is +// occluded, but is not occluded on the pending tree (and is required for +// activation). +// VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED - Unoccluded, required for +// activation, tiles. // -// If the skip_shared_out_of_order_tiles value passed to the constructor is -// true (like it should be when there is a twin layer with a twin tiling set), -// eviction queue does not return shared which are out of order because their -// priority for tree priority is lowered or raised by a twin layer. -// This happens for a tile specific lower priority tree eviction queue -// (because eviction priority the combined priority). -// Those skipped shared out of order tiles are when returned only by the twin -// eviction queue. +// The tilings are ordered as follows. Suppose we have tilings with the scales +// below: +// 2.0 1.5 1.0(HR) 0.8 0.5 0.25(LR) 0.2 0.1 +// With HR referring to high res tiling and LR referring to low res tiling, +// then tilings are processed in this order: +// 2.0 1.5 0.1 0.2 0.5 0.8 0.25(LR) 1.0(HR). +// +// To put it differently: +// 1. Process the highest scale tiling down to, but not including, high res +// tiling. +// 2. Process the lowest scale tiling up to, but not including, the low res +// tiling. In cases without a low res tiling, this is an empty set. +// 3. Process low res tiling up to high res tiling, including neither high +// nor low res tilings. In cases without a low res tiling, this set +// includes all tilings with a lower scale than the high res tiling. +// 4. Process the low res tiling. +// 5. Process the high res tiling. +// +// Additional notes: +// Since eventually the tiles are considered to have the priority which is the +// higher of the two trees, we might visit a tile that should actually be +// returned by its twin. In those situations, the tiles are not returned. That +// is, since the twin has higher priority, it should return it when it gets to +// it. This ensures that we don't block raster because we've returned a tile +// with low priority on one tree, but high combined priority. class CC_EXPORT TilingSetEvictionQueue { public: TilingSetEvictionQueue(PictureLayerTilingSet* tiling_set, @@ -77,29 +70,114 @@ class CC_EXPORT TilingSetEvictionQueue { bool IsEmpty() const; private: - bool AdvanceToNextEvictionTile(); - bool AdvanceToNextPriorityBin(); - bool AdvanceToNextTilingRangeType(); - bool AdvanceToNextValidTiling(); + enum Phase { + EVENTUALLY_RECT, + SOON_BORDER_RECT, + SKEWPORT_RECT, + VISIBLE_RECT_OCCLUDED, + VISIBLE_RECT_UNOCCLUDED, + VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED, + VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED + }; + + void GenerateTilingOrder(PictureLayerTilingSet* tiling_set); + + // Helper base class for individual region iterators. + class EvictionRectIterator { + public: + EvictionRectIterator(); + EvictionRectIterator(std::vector<PictureLayerTiling*>* tilings, + WhichTree tree, + bool skip_shared_out_of_order_tiles); + + bool done() const { return !tile_; } + Tile* operator*() const { return tile_; } + + protected: + ~EvictionRectIterator() = default; + + template <typename TilingIteratorType> + bool AdvanceToNextTile(TilingIteratorType* iterator); + template <typename TilingIteratorType> + bool GetFirstTileAndCheckIfValid(TilingIteratorType* iterator); + + Tile* tile_; + std::vector<PictureLayerTiling*>* tilings_; + WhichTree tree_; + bool skip_shared_out_of_order_tiles_; + size_t tiling_index_; + }; + + class VisibleTilingIterator : public EvictionRectIterator { + public: + VisibleTilingIterator() = default; + VisibleTilingIterator(std::vector<PictureLayerTiling*>* tilings, + WhichTree tree, + bool skip_shared_out_of_order_tiles, + bool return_occluded_tiles, + bool return_required_for_activation_tiles); + + VisibleTilingIterator& operator++(); + + private: + bool TileMatchesRequiredFlags(const Tile* tile) const; - PictureLayerTilingSet::TilingRange CurrentTilingRange() const; - size_t CurrentTilingIndex() const; + TilingData::Iterator iterator_; + bool return_occluded_tiles_; + bool return_required_for_activation_tiles_; + }; + + class SkewportTilingIterator : public EvictionRectIterator { + public: + SkewportTilingIterator() = default; + SkewportTilingIterator(std::vector<PictureLayerTiling*>* tilings, + WhichTree tree, + bool skip_shared_out_of_order_tiles); + + SkewportTilingIterator& operator++(); + + private: + TilingData::ReverseSpiralDifferenceIterator iterator_; + }; + + class SoonBorderTilingIterator : public EvictionRectIterator { + public: + SoonBorderTilingIterator() = default; + SoonBorderTilingIterator(std::vector<PictureLayerTiling*>* tilings, + WhichTree tree, + bool skip_shared_out_of_order_tiles); + + SoonBorderTilingIterator& operator++(); + + private: + TilingData::ReverseSpiralDifferenceIterator iterator_; + }; + + class EventuallyTilingIterator : public EvictionRectIterator { + public: + EventuallyTilingIterator() = default; + EventuallyTilingIterator(std::vector<PictureLayerTiling*>* tilings, + WhichTree tree, + bool skip_shared_out_of_order_tiles); + + EventuallyTilingIterator& operator++(); + + private: + TilingData::ReverseSpiralDifferenceIterator iterator_; + }; + + void AdvancePhase(); - PictureLayerTilingSet* tiling_set_; WhichTree tree_; bool skip_shared_out_of_order_tiles_; - bool processing_soon_border_rect_; - bool processing_required_for_activation_tiles_; - - TilePriority::PriorityBin current_priority_bin_; - PictureLayerTiling* current_tiling_; - size_t current_tiling_index_; - PictureLayerTilingSet::TilingRangeType current_tiling_range_type_; - Tile* current_eviction_tile_; - - TilingData::ReverseSpiralDifferenceIterator spiral_iterator_; - TilingData::Iterator visible_iterator_; - std::vector<Tile*> unoccluded_now_tiles_; + Phase phase_; + Tile* current_tile_; + std::vector<PictureLayerTiling*> tilings_; + + EventuallyTilingIterator eventually_iterator_; + SoonBorderTilingIterator soon_iterator_; + SkewportTilingIterator skewport_iterator_; + VisibleTilingIterator visible_iterator_; }; } // namespace cc |