cc/tiles/tiling_set_eviction_queue.h

   1 // Copyright 2014 The Chromium Authors
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef CC_TILES_TILING_SET_EVICTION_QUEUE_H_
   6 #define CC_TILES_TILING_SET_EVICTION_QUEUE_H_
   7
   8 #include <stddef.h>
   9
  10 #include <vector>
  11
  12 #include "base/memory/raw_ptr_exclusion.h"
  13 #include "cc/cc_export.h"
  14 #include "cc/tiles/picture_layer_tiling_set.h"
  15 #include "cc/tiles/prioritized_tile.h"
  16
  17 namespace cc {
  18
  19 // This eviction queue returned tiles from all tilings in a tiling set in
  20 // the order in which the tiles should be evicted. It can be thought of as the
  21 // following:
  22 //  for all phases:
  23 //    for all ordered tilings:
  24 //      yield the next tile for the given phase from the given tiling
  25 //
  26 // Phases are the following (in order in which they are processed):
  27 // EVENTUALLY_RECT - Tiles in the eventually region of the tiling.
  28 // SOON_BORDER_RECT - Tiles in the prepainting skirt of the tiling.
  29 // SKEWPORT_RECT - Tiles in the skewport of the tiling.
  30 // PENDING_VISIBLE_RECT - Tiles that will be visible upon activation, not
  31 //     required for activation.
  32 // PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION - Tiles that will be visible
  33 //     upon activation, required for activation.
  34 // VISIBLE_RECT_OCCLUDED - Occluded, not required for activation, visible tiles.
  35 // VISIBLE_RECT_UNOCCLUDED - Unoccluded, not required for activation, visible
  36 //     tiles.
  37 // VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED - Occluded, but required for
  38 //     activation, visible tiles. This can happen when an active tree tile is
  39 //     occluded, but is not occluded on the pending tree (and is required for
  40 //     activation).
  41 // VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED - Unoccluded, required for
  42 //     activation, tiles.
  43 //
  44 // The tilings are ordered as follows. Suppose we have tilings with the scales
  45 // below:
  46 // 2.0   1.5   1.0(HR)   0.8   0.5   0.25(LR)   0.2   0.1
  47 // With HR referring to high res tiling and LR referring to low res tiling,
  48 // then tilings are processed in this order:
  49 // 2.0   1.5   0.1   0.2   0.5   0.8   0.25(LR)   1.0(HR).
  50 //
  51 // To put it differently:
  52 //  1. Process the highest scale tiling down to, but not including, high res
  53 //     tiling.
  54 //  2. Process the lowest scale tiling up to, but not including, the low res
  55 //     tiling. In cases without a low res tiling, this is an empty set.
  56 //  3. Process low res tiling up to high res tiling, including neither high
  57 //     nor low res tilings. In cases without a low res tiling, this set
  58 //     includes all tilings with a lower scale than the high res tiling.
  59 //  4. Process the low res tiling.
  60 //  5. Process the high res tiling.
  61 //
  62 // Additional notes:
  63 // Since eventually the tiles are considered to have the priority which is the
  64 // higher of the two trees, we might visit a tile that should actually be
  65 // returned by its twin. In those situations, the tiles are not returned. That
  66 // is, since the twin has higher priority, it should return it when it gets to
  67 // it. This ensures that we don't block raster because we've returned a tile
  68 // with low priority on one tree, but high combined priority.
  69 class CC_EXPORT TilingSetEvictionQueue {
  70  public:
  71   explicit TilingSetEvictionQueue(PictureLayerTilingSet* tiling_set,
  72                                   bool is_drawing_layer);
  73   ~TilingSetEvictionQueue();
  74
  75   const PrioritizedTile& Top() const;
  76   void Pop();
  77   bool IsEmpty() const;
  78   bool is_drawing_layer() const { return is_drawing_layer_; }
  79
  80  private:
  81   enum Phase {
  82     EVENTUALLY_RECT,
  83     SOON_BORDER_RECT,
  84     SKEWPORT_RECT,
  85     PENDING_VISIBLE_RECT,
  86     PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION,
  87     VISIBLE_RECT_OCCLUDED,
  88     VISIBLE_RECT_UNOCCLUDED,
  89     VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED,
  90     VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED
  91   };
  92
  93   void GenerateTilingOrder(PictureLayerTilingSet* tiling_set);
  94
  95   // Helper base class for individual region iterators.
  96   class EvictionRectIterator {
  97    public:
  98     EvictionRectIterator();
  99     EvictionRectIterator(
 100         std::vector<PictureLayerTiling*>* tilings,
 101         WhichTree tree,
 102         PictureLayerTiling::PriorityRectType priority_rect_type);
 103
 104     bool done() const { return !prioritized_tile_.tile(); }
 105     const PrioritizedTile& operator*() const { return prioritized_tile_; }
 106
 107    protected:
 108     ~EvictionRectIterator() = default;
 109
 110     template <typename TilingIteratorType>
 111     bool AdvanceToNextTile(TilingIteratorType* iterator);
 112     template <typename TilingIteratorType>
 113     bool GetFirstTileAndCheckIfValid(TilingIteratorType* iterator);
 114
 115     PrioritizedTile prioritized_tile_;
 116
 117     // `tilings_` is not a raw_ptr<...> for performance reasons (based on
 118     // analysis of sampling profiler data and tab_search:top100:2020).
 119     RAW_PTR_EXCLUSION std::vector<PictureLayerTiling*>* tilings_;
 120
 121     WhichTree tree_;
 122     PictureLayerTiling::PriorityRectType priority_rect_type_;
 123     size_t tiling_index_;
 124   };
 125
 126   class PendingVisibleTilingIterator : public EvictionRectIterator {
 127    public:
 128     PendingVisibleTilingIterator() = default;
 129     PendingVisibleTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 130                                  WhichTree tree,
 131                                  bool return_required_for_activation_tiles);
 132
 133     PendingVisibleTilingIterator& operator++();
 134
 135    private:
 136     bool TileMatchesRequiredFlags(const PrioritizedTile& tile) const;
 137
 138     TilingData::DifferenceIterator iterator_;
 139     bool return_required_for_activation_tiles_;
 140   };
 141
 142   class VisibleTilingIterator : public EvictionRectIterator {
 143    public:
 144     VisibleTilingIterator() = default;
 145     VisibleTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 146                           WhichTree tree,
 147                           bool return_occluded_tiles,
 148                           bool return_required_for_activation_tiles);
 149
 150     VisibleTilingIterator& operator++();
 151
 152    private:
 153     bool TileMatchesRequiredFlags(const PrioritizedTile& tile) const;
 154
 155     TilingData::Iterator iterator_;
 156     bool return_occluded_tiles_;
 157     bool return_required_for_activation_tiles_;
 158   };
 159
 160   class SkewportTilingIterator : public EvictionRectIterator {
 161    public:
 162     SkewportTilingIterator() = default;
 163     SkewportTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 164                            WhichTree tree);
 165
 166     SkewportTilingIterator& operator++();
 167
 168    private:
 169     TilingData::ReverseSpiralDifferenceIterator iterator_;
 170   };
 171
 172   class SoonBorderTilingIterator : public EvictionRectIterator {
 173    public:
 174     SoonBorderTilingIterator() = default;
 175     SoonBorderTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 176                              WhichTree tree);
 177
 178     SoonBorderTilingIterator& operator++();
 179
 180    private:
 181     TilingData::ReverseSpiralDifferenceIterator iterator_;
 182   };
 183
 184   class EventuallyTilingIterator : public EvictionRectIterator {
 185    public:
 186     EventuallyTilingIterator() = default;
 187     EventuallyTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 188                              WhichTree tree);
 189
 190     EventuallyTilingIterator& operator++();
 191
 192    private:
 193     TilingData::ReverseSpiralDifferenceIterator iterator_;
 194   };
 195
 196   void AdvancePhase();
 197
 198   WhichTree tree_;
 199   Phase phase_;
 200   PrioritizedTile current_tile_;
 201   std::vector<PictureLayerTiling*> tilings_;
 202
 203   EventuallyTilingIterator eventually_iterator_;
 204   SoonBorderTilingIterator soon_iterator_;
 205   SkewportTilingIterator skewport_iterator_;
 206   PendingVisibleTilingIterator pending_visible_iterator_;
 207   VisibleTilingIterator visible_iterator_;
 208   bool is_drawing_layer_;
 209 };
 210
 211 }  // namespace cc
 212
 213 #endif  // CC_TILES_TILING_SET_EVICTION_QUEUE_H_