cc: Start using raster/eviction iterators.

cc/resources/tile_manager.h

Index: cc/resources/tile_manager.h
diff --git a/cc/resources/tile_manager.h b/cc/resources/tile_manager.h
index 5ad80910f8e8aed434edc19e2a04571ce3d62781..a772f160e403f96764071fd27f411a2334429c3a 100644
--- a/cc/resources/tile_manager.h
+++ b/cc/resources/tile_manager.h
@@ -17,22 +17,24 @@
 #include "cc/base/ref_counted_managed.h"
 #include "cc/base/unique_notifier.h"
 #include "cc/debug/rendering_stats_instrumentation.h"
-#include "cc/layers/picture_layer_impl.h"
 #include "cc/resources/managed_tile_state.h"
 #include "cc/resources/memory_history.h"
 #include "cc/resources/picture_pile_impl.h"
-#include "cc/resources/prioritized_tile_set.h"
 #include "cc/resources/rasterizer.h"
 #include "cc/resources/resource_pool.h"
 #include "cc/resources/tile.h"
+#include "cc/resources/tile_priority_queue.h"
 
 namespace cc {
+class PictureLayerImpl;
 class ResourceProvider;
 
 class CC_EXPORT TileManagerClient {
  public:
   // Returns the set of layers that the tile manager should consider for raster.
-  virtual const std::vector<PictureLayerImpl*>& GetPictureLayers() = 0;
+  // TODO(vmpstr): Change the way we determine if we are ready to activate, so
+  // that this can be removed.
+  virtual const std::vector<PictureLayerImpl*>& GetPictureLayers() const = 0;
 
   // Called when all tiles marked as required for activation are ready to draw.
   virtual void NotifyReadyToActivate() = 0;
@@ -44,6 +46,10 @@ class CC_EXPORT TileManagerClient {
   // - Tile marked for on-demand raster.
   virtual void NotifyTileStateChanged(const Tile* tile) = 0;
 
+  virtual TilePriorityQueue* RebuildRasterQueue(TreePriority tree_priority) = 0;
+  virtual TilePriorityQueue* RebuildEvictionQueue(
+      TreePriority tree_priority) = 0;

[reveman, 2014/07/14 15:52:38]

This API is not perfectly clear. What happens if I call RebuildRasterQueue
twice? Does that invalidate the first queue returned? Will the pointer returned
always be the same?

I can think of two options to make this cleaner. We can me make the lifetime of
the queue explicit:

scoped_ptr<TilePriorityQueue> CreateRasterQueue(TreePriority priority);

or if you want to avoid allocation of a new queue each time I think the API
should be something like this:

void BuildRasterQueue(RasterTilePriorityQueue* queue,
                      TreePriority priority);

where the tile manager owns the RasterTilePriorityQueue instance.

[vmpstr, 2014/07/14 18:10:44]

Yes, I'd like to avoid allocations of a new queue. The second approach limits
what we can maintain in the raster queue. That is, if we do come up with a way
to maintain a persistent queue, then having tile manager own it limits that. Is
it possible to address this with either a function rename or maybe an explicit
comment here?

[reveman, 2014/07/14 19:09:46]

We can't maintain a persistent queue with the current design, as it's a priority
queue and the only way to use it, is to destroy it. Making it persistent in a
way that's not obvious to the tile manager would be a big mistake imo. Except
maybe [1].

We need to expose a generic collection to the tile manager that can be iterated
if we want to leave the door open to a persistent data type. I think the current
priority queue approach is fine even though it limits the optimizations that can
be done. But I'm also OK with a collection/iterator approach that allows us to
make it persistent in the future but the collection should in that case be
passed to the tile manager ctor and the tile manager should not have to be aware
of the fact that something needs to be rebuilt from scratch when priorities
change.

Just to be clear. If we stick with the current priority queue approach but move
the queue ownership to the tile manager, usage would look something like this:

raster_priority_queue_.Reset();
client_->BuildRasterQueue(&raster_priority_queue_);

I like this as it makes it explicit that we're reusing existing queue storage to
avoid unnecessary allocations and it's consistent with existing code that does
the same. ie. usage of RasterTaskQueue and TaskGraph..


[1] We could allow a persistent queue if the tile manager was responsible for
pushing all elements back on the queue in the same order they were pop-ed.

+
  protected:
   virtual ~TileManagerClient() {}
 };
@@ -64,105 +70,6 @@ scoped_ptr<base::Value> RasterTaskCompletionStatsAsValue(
 class CC_EXPORT TileManager : public RasterizerClient,
                               public RefCountedManager<Tile> {
  public:
-  struct CC_EXPORT PairedPictureLayer {
-    PairedPictureLayer();
-    ~PairedPictureLayer();
-
-    PictureLayerImpl* active_layer;
-    PictureLayerImpl* pending_layer;
-  };
-
-  class CC_EXPORT RasterTileIterator {
-   public:
-    RasterTileIterator(TileManager* tile_manager, TreePriority tree_priority);
-    ~RasterTileIterator();
-
-    RasterTileIterator& operator++();
-    operator bool() const;
-    Tile* operator*();
-
-   private:
-    struct PairedPictureLayerIterator {
-      PairedPictureLayerIterator();
-      ~PairedPictureLayerIterator();
-
-      Tile* PeekTile(TreePriority tree_priority);
-      void PopTile(TreePriority tree_priority);
-
-      std::pair<PictureLayerImpl::LayerRasterTileIterator*, WhichTree>
-          NextTileIterator(TreePriority tree_priority);
-
-      PictureLayerImpl::LayerRasterTileIterator active_iterator;
-      PictureLayerImpl::LayerRasterTileIterator pending_iterator;
-
-      std::vector<Tile*> returned_shared_tiles;
-    };
-
-    class RasterOrderComparator {
-     public:
-      explicit RasterOrderComparator(TreePriority tree_priority);
-
-      bool operator()(PairedPictureLayerIterator* a,
-                      PairedPictureLayerIterator* b) const;
-
-     private:
-      TreePriority tree_priority_;
-    };
-
-    std::vector<PairedPictureLayerIterator> paired_iterators_;
-    std::vector<PairedPictureLayerIterator*> iterator_heap_;
-    TreePriority tree_priority_;
-    RasterOrderComparator comparator_;
-
-    DISALLOW_COPY_AND_ASSIGN(RasterTileIterator);
-  };
-
-  struct CC_EXPORT EvictionTileIterator {
-   public:
-    EvictionTileIterator();
-    EvictionTileIterator(TileManager* tile_manager, TreePriority tree_priority);
-    ~EvictionTileIterator();
-
-    EvictionTileIterator& operator++();
-    operator bool() const;
-    Tile* operator*();
-
-   private:
-    struct PairedPictureLayerIterator {
-      PairedPictureLayerIterator();
-      ~PairedPictureLayerIterator();
-
-      Tile* PeekTile(TreePriority tree_priority);
-      void PopTile(TreePriority tree_priority);
-
-      PictureLayerImpl::LayerEvictionTileIterator* NextTileIterator(
-          TreePriority tree_priority);
-
-      PictureLayerImpl::LayerEvictionTileIterator active_iterator;
-      PictureLayerImpl::LayerEvictionTileIterator pending_iterator;
-
-      std::vector<Tile*> returned_shared_tiles;
-    };
-
-    class EvictionOrderComparator {
-     public:
-      explicit EvictionOrderComparator(TreePriority tree_priority);
-
-      bool operator()(PairedPictureLayerIterator* a,
-                      PairedPictureLayerIterator* b) const;
-
-     private:
-      TreePriority tree_priority_;
-    };
-
-    std::vector<PairedPictureLayerIterator> paired_iterators_;
-    std::vector<PairedPictureLayerIterator*> iterator_heap_;
-    TreePriority tree_priority_;
-    EvictionOrderComparator comparator_;
-
-    DISALLOW_COPY_AND_ASSIGN(EvictionTileIterator);
-  };
-
   static scoped_ptr<TileManager> Create(
       TileManagerClient* client,
       base::SequencedTaskRunner* task_runner,
@@ -191,18 +98,14 @@ class CC_EXPORT TileManager : public RasterizerClient,
     return memory_stats_from_last_assign_;
   }
 
-  void GetPairedPictureLayers(std::vector<PairedPictureLayer>* layers) const;
-
   void InitializeTilesWithResourcesForTesting(const std::vector<Tile*>& tiles) {
     for (size_t i = 0; i < tiles.size(); ++i) {
       ManagedTileState& mts = tiles[i]->managed_state();
       ManagedTileState::TileVersion& tile_version =
           mts.tile_versions[HIGH_QUALITY_RASTER_MODE];
 
-      tile_version.resource_ = resource_pool_->AcquireResource(gfx::Size(1, 1));
-
-      bytes_releasable_ += BytesConsumedIfAllocated(tiles[i]);
-      ++resources_releasable_;
+      tile_version.resource_ =
+          resource_pool_->AcquireResource(tiles[i]->size());
     }
   }
 
@@ -217,12 +120,7 @@ class CC_EXPORT TileManager : public RasterizerClient,
 
   void SetGlobalStateForTesting(
       const GlobalStateThatImpactsTilePriority& state) {
-    // Soft limit is used for resource pool such that
-    // memory returns to soft limit after going over.
-    if (state != global_state_) {
-      global_state_ = state;
-      prioritized_tiles_dirty_ = true;
-    }
+    global_state_ = state;
   }
 
   void SetRasterizerForTesting(Rasterizer* rasterizer);
@@ -236,13 +134,10 @@ class CC_EXPORT TileManager : public RasterizerClient,
               Rasterizer* rasterizer,
               RenderingStatsInstrumentation* rendering_stats_instrumentation);
 
-  // Methods called by Tile
-  friend class Tile;
-  void DidChangeTilePriority(Tile* tile);
-
   void CleanUpReleasedTiles();
 
   // Overriden from RefCountedManager<Tile>:
+  friend class Tile;
   virtual void Release(Tile* tile) OVERRIDE;
 
   // Overriden from RasterizerClient:
@@ -257,11 +152,30 @@ class CC_EXPORT TileManager : public RasterizerClient,
   virtual void ScheduleTasks(
       const TileVector& tiles_that_need_to_be_rasterized);
 
-  void AssignGpuMemoryToTiles(PrioritizedTileSet* tiles,
-                              TileVector* tiles_that_need_to_be_rasterized);
-  void GetTilesWithAssignedBins(PrioritizedTileSet* tiles);
+  void AssignGpuMemoryToTiles(TileVector* tiles_that_need_to_be_rasterized);
 
  private:
+  class MemoryUsage {
+   public:
+    MemoryUsage();
+    MemoryUsage(int64 memory_bytes, int resource_count);
+
+    static MemoryUsage FromConfig(const gfx::Size& size, ResourceFormat format);
+    static MemoryUsage FromTile(const Tile* tile);
+
+    MemoryUsage& operator+=(const MemoryUsage& other);
+    MemoryUsage& operator-=(const MemoryUsage& other);
+    MemoryUsage operator-(const MemoryUsage& other);
+
+    bool Exceeds(const MemoryUsage& limit) const;
+
+    int64 memory_bytes() const { return memory_bytes_; }
+
+   private:
+    int64 memory_bytes_;
+    int resource_count_;
+  };
+
   void OnImageDecodeTaskCompleted(int layer_id,
                                   SkPixelRef* pixel_ref,
                                   bool was_canceled);
@@ -271,11 +185,6 @@ class CC_EXPORT TileManager : public RasterizerClient,
                              const PicturePileImpl::Analysis& analysis,
                              bool was_canceled);
 
-  inline size_t BytesConsumedIfAllocated(const Tile* tile) const {
-    return Resource::MemorySizeBytes(tile->size(),
-                                     resource_pool_->resource_format());
-  }
-
   void FreeResourceForTile(Tile* tile, RasterMode mode);
   void FreeResourcesForTile(Tile* tile);
   void FreeUnusedResourcesForTile(Tile* tile);
@@ -283,8 +192,16 @@ class CC_EXPORT TileManager : public RasterizerClient,
   scoped_refptr<ImageDecodeTask> CreateImageDecodeTask(Tile* tile,
                                                        SkPixelRef* pixel_ref);
   scoped_refptr<RasterTask> CreateRasterTask(Tile* tile);
-  void UpdatePrioritizedTileSetIfNeeded();
 
+  bool FreeTileResourcesUntilUsageIsWithinLimit(TilePriorityQueue* queue,
+                                                const MemoryUsage& limit,
+                                                MemoryUsage* usage);
+  bool FreeTileResourcesWithLowerPriorityUntilUsageIsWithinLimit(
+      TilePriorityQueue* queue,
+      const MemoryUsage& limit,
+      const TilePriority& other_priority,
+      MemoryUsage* usage);
+  bool TilePriorityViolatesMemoryPolicy(const TilePriority& priority);
   bool IsReadyToActivate() const;
   void CheckIfReadyToActivate();
 
@@ -297,16 +214,8 @@ class CC_EXPORT TileManager : public RasterizerClient,
   typedef base::hash_map<Tile::Id, Tile*> TileMap;
   TileMap tiles_;
 
-  PrioritizedTileSet prioritized_tiles_;
-  bool prioritized_tiles_dirty_;
-
-  bool all_tiles_that_need_to_be_rasterized_have_memory_;
-  bool all_tiles_required_for_activation_have_memory_;
-
-  size_t bytes_releasable_;
-  size_t resources_releasable_;
+  bool all_tiles_that_need_to_be_rasterized_are_scheduled_;
 
-  bool ever_exceeded_memory_budget_;
   MemoryHistory::Entry memory_stats_from_last_assign_;
 
   RenderingStatsInstrumentation* rendering_stats_instrumentation_;