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..b1b560843bf491cc9b4016b979f37a2a76b5cf9d 100644
--- a/cc/resources/tile_manager.h
+++ b/cc/resources/tile_manager.h
@@ -21,10 +21,10 @@
 #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 ResourceProvider;
@@ -32,7 +32,7 @@ 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;
+  virtual const std::vector<PictureLayerImpl*>& GetPictureLayers() const = 0;

[reveman, 2014/07/09 02:21:09]

Note: this was added with the assumption that we'd use it for this patch. Now
that this is no longer the case, I think we should somehow merge it with
NotifyReadyToActivate function and not expose layers to the tile manager but
that can be done in a separate follow-up patch. Maybe just add a TODO here for
now.

[vmpstr, 2014/07/09 18:35:38]

Done.

 
   // Called when all tiles marked as required for activation are ready to draw.
   virtual void NotifyReadyToActivate() = 0;
@@ -44,6 +44,9 @@ class CC_EXPORT TileManagerClient {
   // - Tile marked for on-demand raster.
   virtual void NotifyTileStateChanged(const Tile* tile) = 0;
 
+  virtual RasterTileQueue* GetRasterQueue(TreePriority tree_priority) = 0;
+  virtual EvictionTileQueue* GetEvictionQueue(TreePriority tree_priority) = 0;

[reveman, 2014/07/09 02:21:09]

Can we pass these queues to the ctor instead? If the tree priority changes,
maybe the priority queues given to the tile manager could just automatically
reflect that. Or we have one queue for each tree priority type but that seems a
bit overkill.

Btw, I don't think tree_priority is something that the tile manager should cache
and only update when ManageTiles is called anymore. That made sense when the
tile manager was in control over the raster order and could prevent it from
changing between calls to ManageTiles. So GlobalStateThatImpactsTilePriority
should probably be retrieved using a client function instead of being passed to
ManageTiles. We can change this in a follow-up patch if you prefer though.

[vmpstr, 2014/07/09 18:35:38]

In the constructor of tile manager? That change would require us to prepare the
queues whenever layers/priorities change (see last comment), which is something
I want to avoid at least for this patch, since I think it might be a bit error
prone to determine exactly when to do the preparation (hence the TODO in the
implementations of those functions).
That seems a bit out of scope for this patch, let's do that as a follow-up.

[reveman, 2014/07/09 20:47:51]

Yes, having the tile manager call Prepare() would be wrong. That's not what I
was suggesting.

From the tile managers pov, there are 2 queues (or maybe 6 if we decide to use
one for each tree priority) and they are always up to date. Tile manager
shouldn't have to call Prepare or GetRasterQueue to get an up to date version of
a queue. Hence, we should be able to pass each queue to the tile manager ctor
and the tile manager should just be able to use them as it likes.

For efficiency it makes sense to lazy update the queue as needed when
IsEmpty/Top/Pop is called. We can make this lazy update mechanism optimal in the
future (delay as much work as possible and never do more work than necessary)
but for now it might be good enough to have LTHI mark each queue as in need of
lazy prepare work before calling ManageTiles or when a layer is added/removed.
LTHI would only mark the queue as in need of work and not actually do it. The
work would only be done if one of the queue API functions are called by the tile
manager.

Wdyt?

[vmpstr, 2014/07/09 22:46:50]

Let's assume that we're going to work with 2 queues, as having 6 of them is a
bit bulky, I think. In theory, I like the approach you are suggesting. There's a
few details that make this approach awkward/fragile or at least that need to be
addressed. In particular, when we call manage tiles, we pop off some raster
tiles, turn them into tasks, and schedule them to be rasterized. This means that
these tiles are not in the raster queue, but also are not yet rasterized. At a
later time, we can ScheduleMoreWork (or whatever it's called nowadays) and if
those tiles were not yet rasterized, we expect to see them again. I know that
schedule more work is technically should only be called when we complete all
scheduled work, but I think that makes the interaction somewhat fragile and
non-obvious.

If we accept that schedule more tiles can be called regardless of the status of
previously scheduled work, then we somehow need to inform the queue that it
needs to do something before AssignGpuMem call. Since this call can happen
independently of LTHI or anything outside the tile manager, I don't see how we
can get away with having a member queue pointer in tile manager (passed in
ctor), and only call one of Top/Pop/IsEmpty. 

Note that I'm OK with assuming that schedule more work is only called when all
tiles complete, but that's something that we have to consciously decide.

Wdyt?

[reveman, 2014/07/10 11:28:23]

Ah! I forgot the reason we were using iterators and not a priority queue in the
tile manager. To be able to cancel tasks, of course. I think that's very useful
and something we should keep. Sorry for all this priority queue stuff.

Not all to waste though, I hope. Doing lazy work as part of the underlying data
type instead of the iterator still makes sense. I guess the data type is some
sort of lazy initializing collection of tiles that are ordered by priority.
Makes sense for the tile manager to use an iterator to access it but the logic
for lazy initialization should probably be in the collection rather than the
iterator.

Let's chat offline today when you have time.

+
  protected:
   virtual ~TileManagerClient() {}
 };
@@ -64,105 +67,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 +95,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 +117,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 +131,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 +149,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 +182,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 +189,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(EvictionTileQueue* queue,
+                                                const MemoryUsage& limit,
+                                                MemoryUsage* usage);
+  bool FreeTileResourcesWithLowerPriorityUntilUsageIsWithinLimit(
+      EvictionTileQueue* queue,
+      const MemoryUsage& limit,
+      const TilePriority& other_priority,
+      MemoryUsage* usage);
+  bool TilePriorityViolatesMemoryPolicy(const TilePriority& priority);
   bool IsReadyToActivate() const;
   void CheckIfReadyToActivate();
 
@@ -297,16 +211,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_;