Revert 278654 "cc: Start using raster/eviction iterators in tile..."

> cc: Start using raster/eviction iterators in tile manager
> 
> This patch is a part of the series that enables raster
> and eviction iterators in cc. In particular, this patch
> actually starts using the iterators that have landed
> previously. There should be a perf improvement for the
> manage tiles case. Other than that, there should be no perf
> impact.
> 
> This patch's main contribution is that it opens the door for
> more optimizations to be done in the future. As well, it
> simplifies the logic we have in tile manager.
> 
> BUG=329686
> R=enne, reveman
> 
> Review URL: https://codereview.chromium.org/246673005

BUG=329686, 387669, 387652
TBR=vmpstr@chromium.org

Review URL: https://codereview.chromium.org/354463002

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@279160 0039d316-1c4b-4281-b951-d872f2087c98

17 files changed, 1839 insertions, 235 deletions

diff --git a/cc/BUILD.gn b/cc/BUILD.gn
index 2afc012..4d7a9b5 100644
--- a/cc/BUILD.gn
+++ b/cc/BUILD.gn
@@ -342,6 +342,8 @@ component("cc") {
     "resources/prioritized_resource.h",
     "resources/prioritized_resource_manager.cc",
     "resources/prioritized_resource_manager.h",
+    "resources/prioritized_tile_set.cc",
+    "resources/prioritized_tile_set.h",
     "resources/priority_calculator.cc",
     "resources/priority_calculator.h",
     "resources/raster_mode.cc",
@@ -706,6 +708,7 @@ test("cc_unittests") {
     "resources/picture_pile_unittest.cc",
     "resources/picture_unittest.cc",
     "resources/prioritized_resource_unittest.cc",
+    "resources/prioritized_tile_set_unittest.cc",
     "resources/raster_worker_pool_unittest.cc",
     "resources/resource_provider_unittest.cc",
     "resources/resource_update_controller_unittest.cc",
diff --git a/cc/cc.gyp b/cc/cc.gyp
index c39d442..46f7d48 100644
--- a/cc/cc.gyp
+++ b/cc/cc.gyp
@@ -369,6 +369,8 @@
         'resources/prioritized_resource.h',
         'resources/prioritized_resource_manager.cc',
         'resources/prioritized_resource_manager.h',
+        'resources/prioritized_tile_set.cc',
+        'resources/prioritized_tile_set.h',
         'resources/priority_calculator.cc',
         'resources/priority_calculator.h',
         'resources/raster_mode.cc',
diff --git a/cc/cc_tests.gyp b/cc/cc_tests.gyp
index fa96cd6..72aab12 100644
--- a/cc/cc_tests.gyp
+++ b/cc/cc_tests.gyp
@@ -75,6 +75,7 @@
       'resources/picture_pile_unittest.cc',
       'resources/picture_unittest.cc',
       'resources/prioritized_resource_unittest.cc',
+      'resources/prioritized_tile_set_unittest.cc',
       'resources/raster_worker_pool_unittest.cc',
       'resources/resource_provider_unittest.cc',
       'resources/resource_update_controller_unittest.cc',
diff --git a/cc/layers/heads_up_display_layer_impl.cc b/cc/layers/heads_up_display_layer_impl.cc
index e11a278..5c8e2e50 100644
--- a/cc/layers/heads_up_display_layer_impl.cc
+++ b/cc/layers/heads_up_display_layer_impl.cc
@@ -458,7 +458,7 @@ SkRect HeadsUpDisplayLayerImpl::DrawMemoryDisplay(SkCanvas* canvas,
                                                   int right,
                                                   int top,
                                                   int width) const {
-  if (!memory_entry_.total_bytes_used)
+  if (!memory_entry_.bytes_total())
     return SkRect::MakeEmpty();
 
   const int kPadding = 4;
@@ -468,7 +468,7 @@ SkRect HeadsUpDisplayLayerImpl::DrawMemoryDisplay(SkCanvas* canvas,
   const int left = bounds().width() - width - right;
   const SkRect area = SkRect::MakeXYWH(left, top, width, height);
 
-  const double kMegabyte = 1024.0 * 1024.0;
+  const double megabyte = 1024.0 * 1024.0;
 
   SkPaint paint = CreatePaint();
   DrawGraphBackground(canvas, &paint, area);
@@ -487,14 +487,20 @@ SkRect HeadsUpDisplayLayerImpl::DrawMemoryDisplay(SkCanvas* canvas,
            kFontHeight,
            title_pos);
 
-  std::string text = base::StringPrintf(
-      "%6.1f MB used", memory_entry_.total_bytes_used / kMegabyte);
+  std::string text =
+      base::StringPrintf("%6.1f MB used",
+                         (memory_entry_.bytes_unreleasable +
+                          memory_entry_.bytes_allocated) / megabyte);
   DrawText(canvas, &paint, text, SkPaint::kRight_Align, kFontHeight, stat1_pos);
 
-  if (!memory_entry_.had_enough_memory)
+  if (memory_entry_.bytes_over) {
     paint.setColor(SK_ColorRED);
-  text = base::StringPrintf("%6.1f MB max ",
-                            memory_entry_.total_budget_in_bytes / kMegabyte);
+    text = base::StringPrintf("%6.1f MB over",
+                              memory_entry_.bytes_over / megabyte);
+  } else {
+    text = base::StringPrintf("%6.1f MB max ",
+                              memory_entry_.total_budget_in_bytes / megabyte);
+  }
   DrawText(canvas, &paint, text, SkPaint::kRight_Align, kFontHeight, stat2_pos);
 
   return area;
diff --git a/cc/resources/memory_history.cc b/cc/resources/memory_history.cc
index 4dc49c8..a2f8b6e 100644
--- a/cc/resources/memory_history.cc
+++ b/cc/resources/memory_history.cc
@@ -24,7 +24,7 @@ void MemoryHistory::GetMinAndMax(size_t* min, size_t* max) const {
   *max = 0;
 
   for (RingBufferType::Iterator it = ring_buffer_.Begin(); it; ++it) {
-    size_t bytes_total = it->total_bytes_used;
+    size_t bytes_total = it->bytes_total();
 
     if (bytes_total < *min)
       *min = bytes_total;
diff --git a/cc/resources/memory_history.h b/cc/resources/memory_history.h
index 570a3d0..daca10f 100644
--- a/cc/resources/memory_history.h
+++ b/cc/resources/memory_history.h
@@ -22,12 +22,17 @@ class MemoryHistory {
   struct Entry {
     Entry()
         : total_budget_in_bytes(0),
-          total_bytes_used(0),
-          had_enough_memory(false) {}
+          bytes_allocated(0),
+          bytes_unreleasable(0),
+          bytes_over(0) {}
 
     size_t total_budget_in_bytes;
-    size_t total_bytes_used;
-    bool had_enough_memory;
+    size_t bytes_allocated;
+    size_t bytes_unreleasable;
+    size_t bytes_over;
+    size_t bytes_total() const {
+      return bytes_allocated + bytes_unreleasable + bytes_over;
+    }
   };
 
   void SaveEntry(const Entry& entry);
diff --git a/cc/resources/prioritized_tile_set.cc b/cc/resources/prioritized_tile_set.cc
new file mode 100644
index 0000000..b7b3b5a
--- /dev/null
+++ b/cc/resources/prioritized_tile_set.cc
@@ -0,0 +1,140 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "cc/resources/prioritized_tile_set.h"
+
+#include <algorithm>
+
+#include "cc/resources/managed_tile_state.h"
+#include "cc/resources/tile.h"
+
+namespace cc {
+
+class BinComparator {
+ public:
+  bool operator()(const Tile* a,
+                  const Tile* b) const {
+    const ManagedTileState& ams = a->managed_state();
+    const ManagedTileState& bms = b->managed_state();
+
+    if (ams.priority_bin != bms.priority_bin)
+      return ams.priority_bin < bms.priority_bin;
+
+    if (ams.required_for_activation != bms.required_for_activation)
+      return ams.required_for_activation;
+
+    if (ams.resolution != bms.resolution)
+      return ams.resolution < bms.resolution;
+
+    if (ams.distance_to_visible != bms.distance_to_visible)
+      return ams.distance_to_visible < bms.distance_to_visible;
+
+    gfx::Rect a_rect = a->content_rect();
+    gfx::Rect b_rect = b->content_rect();
+    if (a_rect.y() != b_rect.y())
+      return a_rect.y() < b_rect.y();
+    return a_rect.x() < b_rect.x();
+  }
+};
+
+namespace {
+
+typedef std::vector<Tile*> TileVector;
+
+void SortBinTiles(ManagedTileBin bin, TileVector* tiles) {
+  switch (bin) {
+    case NOW_AND_READY_TO_DRAW_BIN:
+    case NEVER_BIN:
+      break;
+    case NOW_BIN:
+    case SOON_BIN:
+    case EVENTUALLY_AND_ACTIVE_BIN:
+    case EVENTUALLY_BIN:
+    case AT_LAST_AND_ACTIVE_BIN:
+    case AT_LAST_BIN:
+      std::sort(tiles->begin(), tiles->end(), BinComparator());
+      break;
+    default:
+      NOTREACHED();
+  }
+}
+
+}  // namespace
+
+PrioritizedTileSet::PrioritizedTileSet() {
+  for (int bin = 0; bin < NUM_BINS; ++bin)
+    bin_sorted_[bin] = true;
+}
+
+PrioritizedTileSet::~PrioritizedTileSet() {}
+
+void PrioritizedTileSet::InsertTile(Tile* tile, ManagedTileBin bin) {
+  tiles_[bin].push_back(tile);
+  bin_sorted_[bin] = false;
+}
+
+void PrioritizedTileSet::Clear() {
+  for (int bin = 0; bin < NUM_BINS; ++bin) {
+    tiles_[bin].clear();
+    bin_sorted_[bin] = true;
+  }
+}
+
+void PrioritizedTileSet::SortBinIfNeeded(ManagedTileBin bin) {
+  if (!bin_sorted_[bin]) {
+    SortBinTiles(bin, &tiles_[bin]);
+    bin_sorted_[bin] = true;
+  }
+}
+
+PrioritizedTileSet::Iterator::Iterator(
+    PrioritizedTileSet* tile_set, bool use_priority_ordering)
+    : tile_set_(tile_set),
+      current_bin_(NOW_AND_READY_TO_DRAW_BIN),
+      use_priority_ordering_(use_priority_ordering) {
+  if (use_priority_ordering_)
+    tile_set_->SortBinIfNeeded(current_bin_);
+  iterator_ = tile_set->tiles_[current_bin_].begin();
+  if (iterator_ == tile_set_->tiles_[current_bin_].end())
+    AdvanceList();
+}
+
+PrioritizedTileSet::Iterator::~Iterator() {}
+
+void PrioritizedTileSet::Iterator::DisablePriorityOrdering() {
+  use_priority_ordering_ = false;
+}
+
+PrioritizedTileSet::Iterator&
+PrioritizedTileSet::Iterator::operator++() {
+  // We can't increment past the end of the tiles.
+  DCHECK(iterator_ != tile_set_->tiles_[current_bin_].end());
+
+  ++iterator_;
+  if (iterator_ == tile_set_->tiles_[current_bin_].end())
+    AdvanceList();
+  return *this;
+}
+
+Tile* PrioritizedTileSet::Iterator::operator*() {
+  DCHECK(iterator_ != tile_set_->tiles_[current_bin_].end());
+  return *iterator_;
+}
+
+void PrioritizedTileSet::Iterator::AdvanceList() {
+  DCHECK(iterator_ == tile_set_->tiles_[current_bin_].end());
+
+  while (current_bin_ != NEVER_BIN) {
+    current_bin_ = static_cast<ManagedTileBin>(current_bin_ + 1);
+
+    if (use_priority_ordering_)
+      tile_set_->SortBinIfNeeded(current_bin_);
+
+    iterator_ = tile_set_->tiles_[current_bin_].begin();
+    if (iterator_ != tile_set_->tiles_[current_bin_].end())
+      break;
+  }
+}
+
+}  // namespace cc
diff --git a/cc/resources/prioritized_tile_set.h b/cc/resources/prioritized_tile_set.h
new file mode 100644
index 0000000..15d0e4f
--- /dev/null
+++ b/cc/resources/prioritized_tile_set.h
@@ -0,0 +1,59 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CC_RESOURCES_PRIORITIZED_TILE_SET_H_
+#define CC_RESOURCES_PRIORITIZED_TILE_SET_H_
+
+#include <vector>
+
+#include "cc/base/cc_export.h"
+#include "cc/resources/managed_tile_state.h"
+
+namespace cc {
+class Tile;
+
+class CC_EXPORT PrioritizedTileSet {
+ public:
+  PrioritizedTileSet();
+  ~PrioritizedTileSet();
+
+  void InsertTile(Tile* tile, ManagedTileBin bin);
+  void Clear();
+
+  class CC_EXPORT Iterator {
+   public:
+    Iterator(PrioritizedTileSet* set, bool use_priority_ordering);
+
+    ~Iterator();
+
+    void DisablePriorityOrdering();
+
+    Iterator& operator++();
+    Tile* operator->() { return *(*this); }
+    Tile* operator*();
+    operator bool() const {
+      return iterator_ != tile_set_->tiles_[current_bin_].end();
+    }
+
+   private:
+    void AdvanceList();
+
+    PrioritizedTileSet* tile_set_;
+    ManagedTileBin current_bin_;
+    std::vector<Tile*>::iterator iterator_;
+    bool use_priority_ordering_;
+  };
+
+ private:
+  friend class Iterator;
+
+  void SortBinIfNeeded(ManagedTileBin bin);
+
+  std::vector<Tile*> tiles_[NUM_BINS];
+  bool bin_sorted_[NUM_BINS];
+};
+
+}  // namespace cc
+
+#endif  // CC_RESOURCES_PRIORITIZED_TILE_SET_H_
diff --git a/cc/resources/prioritized_tile_set_unittest.cc b/cc/resources/prioritized_tile_set_unittest.cc
new file mode 100644
index 0000000..f0a01d2
--- /dev/null
+++ b/cc/resources/prioritized_tile_set_unittest.cc
@@ -0,0 +1,732 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <algorithm>
+#include <vector>
+
+#include "cc/resources/managed_tile_state.h"
+#include "cc/resources/prioritized_tile_set.h"
+#include "cc/resources/tile.h"
+#include "cc/test/fake_output_surface.h"
+#include "cc/test/fake_output_surface_client.h"
+#include "cc/test/fake_picture_pile_impl.h"
+#include "cc/test/fake_tile_manager.h"
+#include "cc/test/fake_tile_manager_client.h"
+#include "cc/test/test_shared_bitmap_manager.h"
+#include "cc/test/test_tile_priorities.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace cc {
+
+class BinComparator {
+ public:
+  bool operator()(const scoped_refptr<Tile>& a,
+                  const scoped_refptr<Tile>& b) const {
+    const ManagedTileState& ams = a->managed_state();
+    const ManagedTileState& bms = b->managed_state();
+
+    if (ams.priority_bin != bms.priority_bin)
+      return ams.priority_bin < bms.priority_bin;
+
+    if (ams.required_for_activation != bms.required_for_activation)
+      return ams.required_for_activation;
+
+    if (ams.resolution != bms.resolution)
+      return ams.resolution < bms.resolution;
+
+    if (ams.distance_to_visible != bms.distance_to_visible)
+      return ams.distance_to_visible < bms.distance_to_visible;
+
+    gfx::Rect a_rect = a->content_rect();
+    gfx::Rect b_rect = b->content_rect();
+    if (a_rect.y() != b_rect.y())
+      return a_rect.y() < b_rect.y();
+    return a_rect.x() < b_rect.x();
+  }
+};
+
+namespace {
+
+class PrioritizedTileSetTest : public testing::Test {
+ public:
+  PrioritizedTileSetTest() {
+    output_surface_ = FakeOutputSurface::Create3d().Pass();
+    CHECK(output_surface_->BindToClient(&output_surface_client_));
+
+    shared_bitmap_manager_.reset(new TestSharedBitmapManager());
+    resource_provider_ =
+        ResourceProvider::Create(
+            output_surface_.get(), shared_bitmap_manager_.get(), 0, false, 1,
+            false)
+            .Pass();
+    resource_pool_ = ResourcePool::Create(
+        resource_provider_.get(), GL_TEXTURE_2D, RGBA_8888);
+    tile_manager_.reset(
+        new FakeTileManager(&tile_manager_client_, resource_pool_.get()));
+    picture_pile_ = FakePicturePileImpl::CreateInfiniteFilledPile();
+  }
+
+  scoped_refptr<Tile> CreateTile() {
+    return tile_manager_->CreateTile(picture_pile_.get(),
+                                     settings_.default_tile_size,
+                                     gfx::Rect(),
+                                     gfx::Rect(),
+                                     1.0,
+                                     0,
+                                     0,
+                                     0);
+  }
+
+ private:
+  LayerTreeSettings settings_;
+  FakeOutputSurfaceClient output_surface_client_;
+  scoped_ptr<FakeOutputSurface> output_surface_;
+  scoped_ptr<SharedBitmapManager> shared_bitmap_manager_;
+  scoped_ptr<ResourceProvider> resource_provider_;
+  scoped_ptr<ResourcePool> resource_pool_;
+  FakeTileManagerClient tile_manager_client_;
+  scoped_ptr<FakeTileManager> tile_manager_;
+  scoped_refptr<FakePicturePileImpl> picture_pile_;
+};
+
+TEST_F(PrioritizedTileSetTest, EmptyIterator) {
+  // Creating an iterator to an empty set should work (but create iterator that
+  // isn't valid).
+
+  PrioritizedTileSet set;
+
+  PrioritizedTileSet::Iterator it(&set, true);
+  EXPECT_FALSE(it);
+}
+
+TEST_F(PrioritizedTileSetTest, NonEmptyIterator) {
+  PrioritizedTileSet set;
+  scoped_refptr<Tile> tile = CreateTile();
+  set.InsertTile(tile, NOW_BIN);
+
+  PrioritizedTileSet::Iterator it(&set, true);
+  EXPECT_TRUE(it);
+  EXPECT_TRUE(*it == tile.get());
+  ++it;
+  EXPECT_FALSE(it);
+}
+
+TEST_F(PrioritizedTileSetTest, NowAndReadyToDrawBin) {
+  // Ensure that tiles in NOW_AND_READY_TO_DRAW_BIN aren't sorted.
+
+  PrioritizedTileSet set;
+  TilePriority priorities[4] = {
+      TilePriorityForEventualBin(),
+      TilePriorityForNowBin(),
+      TilePriority(),
+      TilePriorityForSoonBin()};
+
+  std::vector<scoped_refptr<Tile> > tiles;
+  for (int priority = 0; priority < 4; ++priority) {
+    for (int i = 0; i < 5; ++i) {
+      scoped_refptr<Tile> tile = CreateTile();
+      tile->SetPriority(ACTIVE_TREE, priorities[priority]);
+      tile->SetPriority(PENDING_TREE, priorities[priority]);
+      tiles.push_back(tile);
+      set.InsertTile(tile, NOW_AND_READY_TO_DRAW_BIN);
+    }
+  }
+
+  // Tiles should appear in the same order as inserted.
+  int i = 0;
+  for (PrioritizedTileSet::Iterator it(&set, true);
+       it;
+       ++it) {
+    EXPECT_TRUE(*it == tiles[i].get());
+    ++i;
+  }
+  EXPECT_EQ(20, i);
+}
+
+TEST_F(PrioritizedTileSetTest, NowBin) {
+  // Ensure that tiles in NOW_BIN are sorted according to BinComparator.
+
+  PrioritizedTileSet set;
+  TilePriority priorities[4] = {
+      TilePriorityForEventualBin(),
+      TilePriorityForNowBin(),
+      TilePriority(),
+      TilePriorityForSoonBin()};
+
+  std::vector<scoped_refptr<Tile> > tiles;
+  for (int priority = 0; priority < 4; ++priority) {
+    for (int i = 0; i < 5; ++i) {
+      scoped_refptr<Tile> tile = CreateTile();
+      tile->SetPriority(ACTIVE_TREE, priorities[priority]);
+      tile->SetPriority(PENDING_TREE, priorities[priority]);
+      tiles.push_back(tile);
+      set.InsertTile(tile, NOW_BIN);
+    }
+  }
+
+  // Tiles should appear in BinComparator order.
+  std::sort(tiles.begin(), tiles.end(), BinComparator());
+
+  int i = 0;
+  for (PrioritizedTileSet::Iterator it(&set, true);
+       it;
+       ++it) {
+    EXPECT_TRUE(*it == tiles[i].get());
+    ++i;
+  }
+  EXPECT_EQ(20, i);
+}
+
+TEST_F(PrioritizedTileSetTest, SoonBin) {
+  // Ensure that tiles in SOON_BIN are sorted according to BinComparator.
+
+  PrioritizedTileSet set;
+  TilePriority priorities[4] = {
+      TilePriorityForEventualBin(),
+      TilePriorityForNowBin(),
+      TilePriority(),
+      TilePriorityForSoonBin()};
+
+  std::vector<scoped_refptr<Tile> > tiles;
+  for (int priority = 0; priority < 4; ++priority) {
+    for (int i = 0; i < 5; ++i) {
+      scoped_refptr<Tile> tile = CreateTile();
+      tile->SetPriority(ACTIVE_TREE, priorities[priority]);
+      tile->SetPriority(PENDING_TREE, priorities[priority]);
+      tiles.push_back(tile);
+      set.InsertTile(tile, SOON_BIN);
+    }
+  }
+
+  // Tiles should appear in BinComparator order.
+  std::sort(tiles.begin(), tiles.end(), BinComparator());
+
+  int i = 0;
+  for (PrioritizedTileSet::Iterator it(&set, true);
+       it;
+       ++it) {
+    EXPECT_TRUE(*it == tiles[i].get());
+    ++i;
+  }
+  EXPECT_EQ(20, i);
+}
+
+TEST_F(PrioritizedTileSetTest, SoonBinNoPriority) {
+  // Ensure that when not using priority iterator, SOON_BIN tiles
+  // are not sorted.
+
+  PrioritizedTileSet set;
+  TilePriority priorities[4] = {
+      TilePriorityForEventualBin(),
+      TilePriorityForNowBin(),
+      TilePriority(),
+      TilePriorityForSoonBin()};
+
+  std::vector<scoped_refptr<Tile> > tiles;
+  for (int priority = 0; priority < 4; ++priority) {
+    for (int i = 0; i < 5; ++i) {
+      scoped_refptr<Tile> tile = CreateTile();
+      tile->SetPriority(ACTIVE_TREE, priorities[priority]);
+      tile->SetPriority(PENDING_TREE, priorities[priority]);
+      tiles.push_back(tile);
+      set.InsertTile(tile, SOON_BIN);
+    }
+  }
+
+  int i = 0;
+  for (PrioritizedTileSet::Iterator it(&set, false);
+       it;
+       ++it) {
+    EXPECT_TRUE(*it == tiles[i].get());
+    ++i;
+  }
+  EXPECT_EQ(20, i);
+}
+
+TEST_F(PrioritizedTileSetTest, EventuallyAndActiveBin) {
+  // Ensure that EVENTUALLY_AND_ACTIVE_BIN tiles are sorted.
+
+  PrioritizedTileSet set;
+  TilePriority priorities[4] = {
+      TilePriorityForEventualBin(),
+      TilePriorityForNowBin(),
+      TilePriority(),
+      TilePriorityForSoonBin()};
+
+  std::vector<scoped_refptr<Tile> > tiles;
+  for (int priority = 0; priority < 4; ++priority) {
+    for (int i = 0; i < 5; ++i) {
+      scoped_refptr<Tile> tile = CreateTile();
+      tile->SetPriority(ACTIVE_TREE, priorities[priority]);
+      tile->SetPriority(PENDING_TREE, priorities[priority]);
+      tiles.push_back(tile);
+      set.InsertTile(tile, EVENTUALLY_AND_ACTIVE_BIN);
+    }
+  }
+
+  // Tiles should appear in BinComparator order.
+  std::sort(tiles.begin(), tiles.end(), BinComparator());
+
+  int i = 0;
+  for (PrioritizedTileSet::Iterator it(&set, true);
+       it;
+       ++it) {
+    EXPECT_TRUE(*it == tiles[i].get());
+    ++i;
+  }
+  EXPECT_EQ(20, i);
+}
+
+TEST_F(PrioritizedTileSetTest, EventuallyBin) {
+  // Ensure that EVENTUALLY_BIN tiles are sorted.
+
+  PrioritizedTileSet set;
+  TilePriority priorities[4] = {
+      TilePriorityForEventualBin(),
+      TilePriorityForNowBin(),
+      TilePriority(),
+      TilePriorityForSoonBin()};
+
+  std::vector<scoped_refptr<Tile> > tiles;
+  for (int priority = 0; priority < 4; ++priority) {
+    for (int i = 0; i < 5; ++i) {
+      scoped_refptr<Tile> tile = CreateTile();
+      tile->SetPriority(ACTIVE_TREE, priorities[priority]);
+      tile->SetPriority(PENDING_TREE, priorities[priority]);
+      tiles.push_back(tile);
+      set.InsertTile(tile, EVENTUALLY_BIN);
+    }
+  }
+
+  // Tiles should appear in BinComparator order.
+  std::sort(tiles.begin(), tiles.end(), BinComparator());
+
+  int i = 0;
+  for (PrioritizedTileSet::Iterator it(&set, true);
+       it;
+       ++it) {
+    EXPECT_TRUE(*it == tiles[i].get());
+    ++i;
+  }
+  EXPECT_EQ(20, i);
+}
+
+TEST_F(PrioritizedTileSetTest, AtLastAndActiveBin) {
+  // Ensure that AT_LAST_AND_ACTIVE_BIN tiles are sorted.
+
+  PrioritizedTileSet set;
+  TilePriority priorities[4] = {
+      TilePriorityForEventualBin(),
+      TilePriorityForNowBin(),
+      TilePriority(),
+      TilePriorityForSoonBin()};
+
+  std::vector<scoped_refptr<Tile> > tiles;
+  for (int priority = 0; priority < 4; ++priority) {
+    for (int i = 0; i < 5; ++i) {
+      scoped_refptr<Tile> tile = CreateTile();
+      tile->SetPriority(ACTIVE_TREE, priorities[priority]);
+      tile->SetPriority(PENDING_TREE, priorities[priority]);
+      tiles.push_back(tile);
+      set.InsertTile(tile, AT_LAST_AND_ACTIVE_BIN);
+    }
+  }
+
+  // Tiles should appear in BinComparator order.
+  std::sort(tiles.begin(), tiles.end(), BinComparator());
+
+  int i = 0;
+  for (PrioritizedTileSet::Iterator it(&set, true);
+       it;
+       ++it) {
+    EXPECT_TRUE(*it == tiles[i].get());
+    ++i;
+  }
+  EXPECT_EQ(20, i);
+}
+
+TEST_F(PrioritizedTileSetTest, AtLastBin) {
+  // Ensure that AT_LAST_BIN tiles are sorted.
+
+  PrioritizedTileSet set;
+  TilePriority priorities[4] = {
+      TilePriorityForEventualBin(),
+      TilePriorityForNowBin(),
+      TilePriority(),
+      TilePriorityForSoonBin()};
+
+  std::vector<scoped_refptr<Tile> > tiles;
+  for (int priority = 0; priority < 4; ++priority) {
+    for (int i = 0; i < 5; ++i) {
+      scoped_refptr<Tile> tile = CreateTile();
+      tile->SetPriority(ACTIVE_TREE, priorities[priority]);
+      tile->SetPriority(PENDING_TREE, priorities[priority]);
+      tiles.push_back(tile);
+      set.InsertTile(tile, AT_LAST_BIN);
+    }
+  }
+
+  // Tiles should appear in BinComparator order.
+  std::sort(tiles.begin(), tiles.end(), BinComparator());
+
+  int i = 0;
+  for (PrioritizedTileSet::Iterator it(&set, true);
+       it;
+       ++it) {
+    EXPECT_TRUE(*it == tiles[i].get());
+    ++i;
+  }
+  EXPECT_EQ(20, i);
+}
+
+TEST_F(PrioritizedTileSetTest, TilesForEachBin) {
+  // Aggregate test with one tile for each of the bins, which
+  // should appear in order of the bins.
+
+  scoped_refptr<Tile> now_and_ready_to_draw_bin = CreateTile();
+  scoped_refptr<Tile> now_bin = CreateTile();
+  scoped_refptr<Tile> soon_bin = CreateTile();
+  scoped_refptr<Tile> eventually_and_active_bin = CreateTile();
+  scoped_refptr<Tile> eventually_bin = CreateTile();
+  scoped_refptr<Tile> at_last_bin = CreateTile();
+  scoped_refptr<Tile> at_last_and_active_bin = CreateTile();
+
+  PrioritizedTileSet set;
+  set.InsertTile(soon_bin, SOON_BIN);
+  set.InsertTile(at_last_and_active_bin, AT_LAST_AND_ACTIVE_BIN);
+  set.InsertTile(eventually_bin, EVENTUALLY_BIN);
+  set.InsertTile(now_bin, NOW_BIN);
+  set.InsertTile(eventually_and_active_bin, EVENTUALLY_AND_ACTIVE_BIN);
+  set.InsertTile(at_last_bin, AT_LAST_BIN);
+  set.InsertTile(now_and_ready_to_draw_bin, NOW_AND_READY_TO_DRAW_BIN);
+
+  // Tiles should appear in order.
+  PrioritizedTileSet::Iterator it(&set, true);
+  EXPECT_TRUE(*it == now_and_ready_to_draw_bin.get());
+  ++it;
+  EXPECT_TRUE(*it == now_bin.get());
+  ++it;
+  EXPECT_TRUE(*it == soon_bin.get());
+  ++it;
+  EXPECT_TRUE(*it == eventually_and_active_bin.get());
+  ++it;
+  EXPECT_TRUE(*it == eventually_bin.get());
+  ++it;
+  EXPECT_TRUE(*it == at_last_and_active_bin.get());
+  ++it;
+  EXPECT_TRUE(*it == at_last_bin.get());
+  ++it;
+  EXPECT_FALSE(it);
+}
+
+TEST_F(PrioritizedTileSetTest, ManyTilesForEachBin) {
+  // Aggregate test with many tiles in each of the bins of various
+  // priorities. Ensure that they are all returned in a sorted order.
+
+  std::vector<scoped_refptr<Tile> > now_and_ready_to_draw_bins;
+  std::vector<scoped_refptr<Tile> > now_bins;
+  std::vector<scoped_refptr<Tile> > soon_bins;
+  std::vector<scoped_refptr<Tile> > eventually_and_active_bins;
+  std::vector<scoped_refptr<Tile> > eventually_bins;
+  std::vector<scoped_refptr<Tile> > at_last_bins;
+  std::vector<scoped_refptr<Tile> > at_last_and_active_bins;
+
+  TilePriority priorities[4] = {
+      TilePriorityForEventualBin(),
+      TilePriorityForNowBin(),
+      TilePriority(),
+      TilePriorityForSoonBin()};
+
+  PrioritizedTileSet set;
+  for (int priority = 0; priority < 4; ++priority) {
+    for (int i = 0; i < 5; ++i) {
+      scoped_refptr<Tile> tile = CreateTile();
+      tile->SetPriority(ACTIVE_TREE, priorities[priority]);
+      tile->SetPriority(PENDING_TREE, priorities[priority]);
+
+      now_and_ready_to_draw_bins.push_back(tile);
+      now_bins.push_back(tile);
+      soon_bins.push_back(tile);
+      eventually_and_active_bins.push_back(tile);
+      eventually_bins.push_back(tile);
+      at_last_bins.push_back(tile);
+      at_last_and_active_bins.push_back(tile);
+
+      set.InsertTile(tile, NOW_AND_READY_TO_DRAW_BIN);
+      set.InsertTile(tile, NOW_BIN);
+      set.InsertTile(tile, SOON_BIN);
+      set.InsertTile(tile, EVENTUALLY_AND_ACTIVE_BIN);
+      set.InsertTile(tile, EVENTUALLY_BIN);
+      set.InsertTile(tile, AT_LAST_BIN);
+      set.InsertTile(tile, AT_LAST_AND_ACTIVE_BIN);
+    }
+  }
+
+  PrioritizedTileSet::Iterator it(&set, true);
+  std::vector<scoped_refptr<Tile> >::iterator vector_it;
+
+  // Now and ready are not sorted.
+  for (vector_it = now_and_ready_to_draw_bins.begin();
+       vector_it != now_and_ready_to_draw_bins.end();
+       ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  // Now bins are sorted.
+  std::sort(now_bins.begin(), now_bins.end(), BinComparator());
+  for (vector_it = now_bins.begin(); vector_it != now_bins.end(); ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  // Soon bins are sorted.
+  std::sort(soon_bins.begin(), soon_bins.end(), BinComparator());
+  for (vector_it = soon_bins.begin(); vector_it != soon_bins.end();
+       ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  // Eventually and active bins are sorted.
+  std::sort(eventually_and_active_bins.begin(),
+            eventually_and_active_bins.end(),
+            BinComparator());
+  for (vector_it = eventually_and_active_bins.begin();
+       vector_it != eventually_and_active_bins.end();
+       ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  // Eventually bins are sorted.
+  std::sort(eventually_bins.begin(), eventually_bins.end(), BinComparator());
+  for (vector_it = eventually_bins.begin(); vector_it != eventually_bins.end();
+       ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  // At last and active bins are sorted.
+  std::sort(at_last_and_active_bins.begin(),
+            at_last_and_active_bins.end(),
+            BinComparator());
+  for (vector_it = at_last_and_active_bins.begin();
+       vector_it != at_last_and_active_bins.end();
+       ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  // At last bins are sorted.
+  std::sort(at_last_bins.begin(), at_last_bins.end(), BinComparator());
+  for (vector_it = at_last_bins.begin(); vector_it != at_last_bins.end();
+       ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  EXPECT_FALSE(it);
+}
+
+TEST_F(PrioritizedTileSetTest, ManyTilesForEachBinDisablePriority) {
+  // Aggregate test with many tiles for each of the bins. Tiles should
+  // appear in order, until DisablePriorityOrdering is called. After that
+  // tiles should appear in the order they were inserted.
+
+  std::vector<scoped_refptr<Tile> > now_and_ready_to_draw_bins;
+  std::vector<scoped_refptr<Tile> > now_bins;
+  std::vector<scoped_refptr<Tile> > soon_bins;
+  std::vector<scoped_refptr<Tile> > eventually_and_active_bins;
+  std::vector<scoped_refptr<Tile> > eventually_bins;
+  std::vector<scoped_refptr<Tile> > at_last_bins;
+  std::vector<scoped_refptr<Tile> > at_last_and_active_bins;
+
+  TilePriority priorities[4] = {
+      TilePriorityForEventualBin(),
+      TilePriorityForNowBin(),
+      TilePriority(),
+      TilePriorityForSoonBin()};
+
+  PrioritizedTileSet set;
+  for (int priority = 0; priority < 4; ++priority) {
+    for (int i = 0; i < 5; ++i) {
+      scoped_refptr<Tile> tile = CreateTile();
+      tile->SetPriority(ACTIVE_TREE, priorities[priority]);
+      tile->SetPriority(PENDING_TREE, priorities[priority]);
+
+      now_and_ready_to_draw_bins.push_back(tile);
+      now_bins.push_back(tile);
+      soon_bins.push_back(tile);
+      eventually_and_active_bins.push_back(tile);
+      eventually_bins.push_back(tile);
+      at_last_bins.push_back(tile);
+      at_last_and_active_bins.push_back(tile);
+
+      set.InsertTile(tile, NOW_AND_READY_TO_DRAW_BIN);
+      set.InsertTile(tile, NOW_BIN);
+      set.InsertTile(tile, SOON_BIN);
+      set.InsertTile(tile, EVENTUALLY_AND_ACTIVE_BIN);
+      set.InsertTile(tile, EVENTUALLY_BIN);
+      set.InsertTile(tile, AT_LAST_BIN);
+      set.InsertTile(tile, AT_LAST_AND_ACTIVE_BIN);
+    }
+  }
+
+  PrioritizedTileSet::Iterator it(&set, true);
+  std::vector<scoped_refptr<Tile> >::iterator vector_it;
+
+  // Now and ready are not sorted.
+  for (vector_it = now_and_ready_to_draw_bins.begin();
+       vector_it != now_and_ready_to_draw_bins.end();
+       ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  // Now bins are sorted.
+  std::sort(now_bins.begin(), now_bins.end(), BinComparator());
+  for (vector_it = now_bins.begin(); vector_it != now_bins.end(); ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  // Soon bins are sorted.
+  std::sort(soon_bins.begin(), soon_bins.end(), BinComparator());
+  for (vector_it = soon_bins.begin(); vector_it != soon_bins.end();
+       ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  // After we disable priority ordering, we already have sorted the next vector.
+  it.DisablePriorityOrdering();
+
+  // Eventually and active bins are sorted.
+  std::sort(eventually_and_active_bins.begin(),
+            eventually_and_active_bins.end(),
+            BinComparator());
+  for (vector_it = eventually_and_active_bins.begin();
+       vector_it != eventually_and_active_bins.end();
+       ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  // Eventually bins are not sorted.
+  for (vector_it = eventually_bins.begin(); vector_it != eventually_bins.end();
+       ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  // At last and active bins are not sorted.
+  for (vector_it = at_last_and_active_bins.begin();
+       vector_it != at_last_and_active_bins.end();
+       ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  // At last bins are not sorted.
+  for (vector_it = at_last_bins.begin(); vector_it != at_last_bins.end();
+       ++vector_it) {
+    EXPECT_TRUE(*vector_it == *it);
+    ++it;
+  }
+
+  EXPECT_FALSE(it);
+}
+
+TEST_F(PrioritizedTileSetTest, TilesForFirstAndLastBins) {
+  // Make sure that if we have empty lists between two non-empty lists,
+  // we just get two tiles from the iterator.
+
+  scoped_refptr<Tile> now_and_ready_to_draw_bin = CreateTile();
+  scoped_refptr<Tile> at_last_bin = CreateTile();
+
+  PrioritizedTileSet set;
+  set.InsertTile(at_last_bin, AT_LAST_BIN);
+  set.InsertTile(now_and_ready_to_draw_bin, NOW_AND_READY_TO_DRAW_BIN);
+
+  // Only two tiles should appear and they should appear in order.
+  PrioritizedTileSet::Iterator it(&set, true);
+  EXPECT_TRUE(*it == now_and_ready_to_draw_bin.get());
+  ++it;
+  EXPECT_TRUE(*it == at_last_bin.get());
+  ++it;
+  EXPECT_FALSE(it);
+}
+
+TEST_F(PrioritizedTileSetTest, MultipleIterators) {
+  // Ensure that multiple iterators don't interfere with each other.
+
+  scoped_refptr<Tile> now_and_ready_to_draw_bin = CreateTile();
+  scoped_refptr<Tile> now_bin = CreateTile();
+  scoped_refptr<Tile> soon_bin = CreateTile();
+  scoped_refptr<Tile> eventually_bin = CreateTile();
+  scoped_refptr<Tile> at_last_bin = CreateTile();
+
+  PrioritizedTileSet set;
+  set.InsertTile(soon_bin, SOON_BIN);
+  set.InsertTile(eventually_bin, EVENTUALLY_BIN);
+  set.InsertTile(now_bin, NOW_BIN);
+  set.InsertTile(at_last_bin, AT_LAST_BIN);
+  set.InsertTile(now_and_ready_to_draw_bin, NOW_AND_READY_TO_DRAW_BIN);
+
+  // Tiles should appear in order.
+  PrioritizedTileSet::Iterator it(&set, true);
+  EXPECT_TRUE(*it == now_and_ready_to_draw_bin.get());
+  ++it;
+  EXPECT_TRUE(*it == now_bin.get());
+  ++it;
+  EXPECT_TRUE(*it == soon_bin.get());
+  ++it;
+  EXPECT_TRUE(*it == eventually_bin.get());
+  ++it;
+  EXPECT_TRUE(*it == at_last_bin.get());
+  ++it;
+  EXPECT_FALSE(it);
+
+  // Creating multiple iterators shouldn't affect old iterators.
+  PrioritizedTileSet::Iterator second_it(&set, true);
+  EXPECT_TRUE(second_it);
+  EXPECT_FALSE(it);
+
+  ++second_it;
+  EXPECT_TRUE(second_it);
+  ++second_it;
+  EXPECT_TRUE(second_it);
+  EXPECT_FALSE(it);
+
+  PrioritizedTileSet::Iterator third_it(&set, true);
+  EXPECT_TRUE(third_it);
+  ++second_it;
+  ++second_it;
+  EXPECT_TRUE(second_it);
+  EXPECT_TRUE(third_it);
+  EXPECT_FALSE(it);
+
+  ++third_it;
+  ++third_it;
+  EXPECT_TRUE(third_it);
+  EXPECT_TRUE(*third_it == soon_bin.get());
+  EXPECT_TRUE(second_it);
+  EXPECT_TRUE(*second_it == at_last_bin.get());
+  EXPECT_FALSE(it);
+
+  ++second_it;
+  EXPECT_TRUE(third_it);
+  EXPECT_FALSE(second_it);
+  EXPECT_FALSE(it);
+
+  set.Clear();
+
+  PrioritizedTileSet::Iterator empty_it(&set, true);
+  EXPECT_FALSE(empty_it);
+}
+
+}  // namespace
+}  // namespace cc
+
diff --git a/cc/resources/tile.cc b/cc/resources/tile.cc
index 16252ed..d59dc02 100644
--- a/cc/resources/tile.cc
+++ b/cc/resources/tile.cc
@@ -25,6 +25,7 @@ Tile::Tile(TileManager* tile_manager,
            int source_frame_number,
            int flags)
     : RefCountedManaged<Tile>(tile_manager),
+      tile_manager_(tile_manager),
       tile_size_(tile_size),
       content_rect_(content_rect),
       contents_scale_(contents_scale),
@@ -43,11 +44,19 @@ Tile::~Tile() {
 }
 
 void Tile::SetPriority(WhichTree tree, const TilePriority& priority) {
+  if (priority == priority_[tree])
+    return;
+
   priority_[tree] = priority;
+  tile_manager_->DidChangeTilePriority(this);
 }
 
 void Tile::MarkRequiredForActivation() {
+  if (priority_[PENDING_TREE].required_for_activation)
+    return;
+
   priority_[PENDING_TREE].required_for_activation = true;
+  tile_manager_->DidChangeTilePriority(this);
 }
 
 scoped_ptr<base::Value> Tile::AsValue() const {
diff --git a/cc/resources/tile.h b/cc/resources/tile.h
index 38469b6..69ef56f 100644
--- a/cc/resources/tile.h
+++ b/cc/resources/tile.h
@@ -151,6 +151,7 @@ class CC_EXPORT Tile : public RefCountedManaged<Tile> {
   const ManagedTileState& managed_state() const { return managed_state_; }
   RasterMode DetermineRasterModeForResolution(TileResolution resolution) const;
 
+  TileManager* tile_manager_;
   scoped_refptr<PicturePileImpl> picture_pile_;
   gfx::Rect tile_size_;
   gfx::Rect content_rect_;
diff --git a/cc/resources/tile_manager.cc b/cc/resources/tile_manager.cc
index b47491d..d508f6a 100644
--- a/cc/resources/tile_manager.cc
+++ b/cc/resources/tile_manager.cc
@@ -227,6 +227,110 @@ class ImageDecodeTaskImpl : public ImageDecodeTask {
 
 const size_t kScheduledRasterTasksLimit = 32u;
 
+// Memory limit policy works by mapping some bin states to the NEVER bin.
+const ManagedTileBin kBinPolicyMap[NUM_TILE_MEMORY_LIMIT_POLICIES][NUM_BINS] = {
+    // [ALLOW_NOTHING]
+    {NEVER_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
+     NEVER_BIN,  // [NOW_BIN]
+     NEVER_BIN,  // [SOON_BIN]
+     NEVER_BIN,  // [EVENTUALLY_AND_ACTIVE_BIN]
+     NEVER_BIN,  // [EVENTUALLY_BIN]
+     NEVER_BIN,  // [AT_LAST_AND_ACTIVE_BIN]
+     NEVER_BIN,  // [AT_LAST_BIN]
+     NEVER_BIN   // [NEVER_BIN]
+    },
+    // [ALLOW_ABSOLUTE_MINIMUM]
+    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
+     NOW_BIN,                    // [NOW_BIN]
+     NEVER_BIN,                  // [SOON_BIN]
+     NEVER_BIN,                  // [EVENTUALLY_AND_ACTIVE_BIN]
+     NEVER_BIN,                  // [EVENTUALLY_BIN]
+     NEVER_BIN,                  // [AT_LAST_AND_ACTIVE_BIN]
+     NEVER_BIN,                  // [AT_LAST_BIN]
+     NEVER_BIN                   // [NEVER_BIN]
+    },
+    // [ALLOW_PREPAINT_ONLY]
+    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
+     NOW_BIN,                    // [NOW_BIN]
+     SOON_BIN,                   // [SOON_BIN]
+     NEVER_BIN,                  // [EVENTUALLY_AND_ACTIVE_BIN]
+     NEVER_BIN,                  // [EVENTUALLY_BIN]
+     NEVER_BIN,                  // [AT_LAST_AND_ACTIVE_BIN]
+     NEVER_BIN,                  // [AT_LAST_BIN]
+     NEVER_BIN                   // [NEVER_BIN]
+    },
+    // [ALLOW_ANYTHING]
+    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
+     NOW_BIN,                    // [NOW_BIN]
+     SOON_BIN,                   // [SOON_BIN]
+     EVENTUALLY_AND_ACTIVE_BIN,  // [EVENTUALLY_AND_ACTIVE_BIN]
+     EVENTUALLY_BIN,             // [EVENTUALLY_BIN]
+     AT_LAST_AND_ACTIVE_BIN,     // [AT_LAST_AND_ACTIVE_BIN]
+     AT_LAST_BIN,                // [AT_LAST_BIN]
+     NEVER_BIN                   // [NEVER_BIN]
+    }};
+
+// Ready to draw works by mapping NOW_BIN to NOW_AND_READY_TO_DRAW_BIN.
+const ManagedTileBin kBinReadyToDrawMap[2][NUM_BINS] = {
+    // Not ready
+    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
+     NOW_BIN,                    // [NOW_BIN]
+     SOON_BIN,                   // [SOON_BIN]
+     EVENTUALLY_AND_ACTIVE_BIN,  // [EVENTUALLY_AND_ACTIVE_BIN]
+     EVENTUALLY_BIN,             // [EVENTUALLY_BIN]
+     AT_LAST_AND_ACTIVE_BIN,     // [AT_LAST_AND_ACTIVE_BIN]
+     AT_LAST_BIN,                // [AT_LAST_BIN]
+     NEVER_BIN                   // [NEVER_BIN]
+    },
+    // Ready
+    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
+     NOW_AND_READY_TO_DRAW_BIN,  // [NOW_BIN]
+     SOON_BIN,                   // [SOON_BIN]
+     EVENTUALLY_AND_ACTIVE_BIN,  // [EVENTUALLY_AND_ACTIVE_BIN]
+     EVENTUALLY_BIN,             // [EVENTUALLY_BIN]
+     AT_LAST_AND_ACTIVE_BIN,     // [AT_LAST_AND_ACTIVE_BIN]
+     AT_LAST_BIN,                // [AT_LAST_BIN]
+     NEVER_BIN                   // [NEVER_BIN]
+    }};
+
+// Active works by mapping some bin stats to equivalent _ACTIVE_BIN state.
+const ManagedTileBin kBinIsActiveMap[2][NUM_BINS] = {
+    // Inactive
+    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
+     NOW_BIN,                    // [NOW_BIN]
+     SOON_BIN,                   // [SOON_BIN]
+     EVENTUALLY_AND_ACTIVE_BIN,  // [EVENTUALLY_AND_ACTIVE_BIN]
+     EVENTUALLY_BIN,             // [EVENTUALLY_BIN]
+     AT_LAST_AND_ACTIVE_BIN,     // [AT_LAST_AND_ACTIVE_BIN]
+     AT_LAST_BIN,                // [AT_LAST_BIN]
+     NEVER_BIN                   // [NEVER_BIN]
+    },
+    // Active
+    {NOW_AND_READY_TO_DRAW_BIN,  // [NOW_AND_READY_TO_DRAW_BIN]
+     NOW_BIN,                    // [NOW_BIN]
+     SOON_BIN,                   // [SOON_BIN]
+     EVENTUALLY_AND_ACTIVE_BIN,  // [EVENTUALLY_AND_ACTIVE_BIN]
+     EVENTUALLY_AND_ACTIVE_BIN,  // [EVENTUALLY_BIN]
+     AT_LAST_AND_ACTIVE_BIN,     // [AT_LAST_AND_ACTIVE_BIN]
+     AT_LAST_AND_ACTIVE_BIN,     // [AT_LAST_BIN]
+     NEVER_BIN                   // [NEVER_BIN]
+    }};
+
+// Determine bin based on three categories of tiles: things we need now,
+// things we need soon, and eventually.
+inline ManagedTileBin BinFromTilePriority(const TilePriority& prio) {
+  if (prio.priority_bin == TilePriority::NOW)
+    return NOW_BIN;
+
+  if (prio.priority_bin == TilePriority::SOON)
+    return SOON_BIN;
+
+  if (prio.distance_to_visible == std::numeric_limits<float>::infinity())
+    return NEVER_BIN;
+
+  return EVENTUALLY_BIN;
+}
+
 }  // namespace
 
 RasterTaskCompletionStats::RasterTaskCompletionStats()
@@ -264,7 +368,12 @@ TileManager::TileManager(
       task_runner_(task_runner),
       resource_pool_(resource_pool),
       rasterizer_(rasterizer),
-      all_tiles_that_need_to_be_rasterized_are_scheduled_(true),
+      prioritized_tiles_dirty_(false),
+      all_tiles_that_need_to_be_rasterized_have_memory_(true),
+      all_tiles_required_for_activation_have_memory_(true),
+      bytes_releasable_(0),
+      resources_releasable_(0),
+      ever_exceeded_memory_budget_(false),
       rendering_stats_instrumentation_(rendering_stats_instrumentation),
       did_initialize_visible_tile_(false),
       did_check_for_completed_tasks_since_last_schedule_tasks_(true),
@@ -291,12 +400,20 @@ TileManager::~TileManager() {
   // resources.
   rasterizer_->Shutdown();
   rasterizer_->CheckForCompletedTasks();
+
+  DCHECK_EQ(0u, bytes_releasable_);
+  DCHECK_EQ(0u, resources_releasable_);
 }
 
 void TileManager::Release(Tile* tile) {
+  prioritized_tiles_dirty_ = true;
   released_tiles_.push_back(tile);
 }
 
+void TileManager::DidChangeTilePriority(Tile* tile) {
+  prioritized_tiles_dirty_ = true;
+}
+
 bool TileManager::ShouldForceTasksRequiredForActivationToComplete() const {
   return global_state_.tree_priority != SMOOTHNESS_TAKES_PRIORITY;
 }
@@ -330,6 +447,17 @@ void TileManager::CleanUpReleasedTiles() {
   released_tiles_.clear();
 }
 
+void TileManager::UpdatePrioritizedTileSetIfNeeded() {
+  if (!prioritized_tiles_dirty_)
+    return;
+
+  CleanUpReleasedTiles();
+
+  prioritized_tiles_.Clear();
+  GetTilesWithAssignedBins(&prioritized_tiles_);
+  prioritized_tiles_dirty_ = false;
+}
+
 void TileManager::DidFinishRunningTasks() {
   TRACE_EVENT0("cc", "TileManager::DidFinishRunningTasks");
 
@@ -338,7 +466,7 @@ void TileManager::DidFinishRunningTasks() {
 
   // When OOM, keep re-assigning memory until we reach a steady state
   // where top-priority tiles are initialized.
-  if (all_tiles_that_need_to_be_rasterized_are_scheduled_ &&
+  if (all_tiles_that_need_to_be_rasterized_have_memory_ &&
       !memory_usage_above_limit)
     return;
 
@@ -346,7 +474,8 @@ void TileManager::DidFinishRunningTasks() {
   did_check_for_completed_tasks_since_last_schedule_tasks_ = true;
 
   TileVector tiles_that_need_to_be_rasterized;
-  AssignGpuMemoryToTiles(&tiles_that_need_to_be_rasterized);
+  AssignGpuMemoryToTiles(&prioritized_tiles_,
+                         &tiles_that_need_to_be_rasterized);
 
   // |tiles_that_need_to_be_rasterized| will be empty when we reach a
   // steady memory state. Keep scheduling tasks until we reach this state.
@@ -387,13 +516,134 @@ void TileManager::DidFinishRunningTasks() {
 }
 
 void TileManager::DidFinishRunningTasksRequiredForActivation() {
+  // This is only a true indication that all tiles required for
+  // activation are initialized when no tiles are OOM. We need to
+  // wait for DidFinishRunningTasks() to be called, try to re-assign
+  // memory and in worst case use on-demand raster when tiles
+  // required for activation are OOM.
+  if (!all_tiles_required_for_activation_have_memory_)
+    return;
+
   ready_to_activate_check_notifier_.Schedule();
 }
 
+void TileManager::GetTilesWithAssignedBins(PrioritizedTileSet* tiles) {
+  TRACE_EVENT0("cc", "TileManager::GetTilesWithAssignedBins");
+
+  const TileMemoryLimitPolicy memory_policy = global_state_.memory_limit_policy;
+  const TreePriority tree_priority = global_state_.tree_priority;
+
+  // For each tree, bin into different categories of tiles.
+  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
+    Tile* tile = it->second;
+    ManagedTileState& mts = tile->managed_state();
+
+    const ManagedTileState::TileVersion& tile_version =
+        tile->GetTileVersionForDrawing();
+    bool tile_is_ready_to_draw = tile_version.IsReadyToDraw();
+    bool tile_is_active = tile_is_ready_to_draw ||
+                          mts.tile_versions[mts.raster_mode].raster_task_;
+
+    // Get the active priority and bin.
+    TilePriority active_priority = tile->priority(ACTIVE_TREE);
+    ManagedTileBin active_bin = BinFromTilePriority(active_priority);
+
+    // Get the pending priority and bin.
+    TilePriority pending_priority = tile->priority(PENDING_TREE);
+    ManagedTileBin pending_bin = BinFromTilePriority(pending_priority);
+
+    bool pending_is_low_res = pending_priority.resolution == LOW_RESOLUTION;
+    bool pending_is_non_ideal =
+        pending_priority.resolution == NON_IDEAL_RESOLUTION;
+    bool active_is_non_ideal =
+        active_priority.resolution == NON_IDEAL_RESOLUTION;
+
+    // Adjust bin state based on if ready to draw.
+    active_bin = kBinReadyToDrawMap[tile_is_ready_to_draw][active_bin];
+    pending_bin = kBinReadyToDrawMap[tile_is_ready_to_draw][pending_bin];
+
+    // Adjust bin state based on if active.
+    active_bin = kBinIsActiveMap[tile_is_active][active_bin];
+    pending_bin = kBinIsActiveMap[tile_is_active][pending_bin];
+
+    // We never want to paint new non-ideal tiles, as we always have
+    // a high-res tile covering that content (paint that instead).
+    if (!tile_is_ready_to_draw && active_is_non_ideal)
+      active_bin = NEVER_BIN;
+    if (!tile_is_ready_to_draw && pending_is_non_ideal)
+      pending_bin = NEVER_BIN;
+
+    ManagedTileBin tree_bin[NUM_TREES];
+    tree_bin[ACTIVE_TREE] = kBinPolicyMap[memory_policy][active_bin];
+    tree_bin[PENDING_TREE] = kBinPolicyMap[memory_policy][pending_bin];
+
+    // Adjust pending bin state for low res tiles. This prevents pending tree
+    // low-res tiles from being initialized before high-res tiles.
+    if (pending_is_low_res)
+      tree_bin[PENDING_TREE] = std::max(tree_bin[PENDING_TREE], EVENTUALLY_BIN);
+
+    TilePriority tile_priority;
+    switch (tree_priority) {
+      case SAME_PRIORITY_FOR_BOTH_TREES:
+        mts.bin = std::min(tree_bin[ACTIVE_TREE], tree_bin[PENDING_TREE]);
+        tile_priority = tile->combined_priority();
+        break;
+      case SMOOTHNESS_TAKES_PRIORITY:
+        mts.bin = tree_bin[ACTIVE_TREE];
+        tile_priority = active_priority;
+        break;
+      case NEW_CONTENT_TAKES_PRIORITY:
+        mts.bin = tree_bin[PENDING_TREE];
+        tile_priority = pending_priority;
+        break;
+    }
+
+    // Bump up the priority if we determined it's NEVER_BIN on one tree,
+    // but is still required on the other tree.
+    bool is_in_never_bin_on_both_trees = tree_bin[ACTIVE_TREE] == NEVER_BIN &&
+                                         tree_bin[PENDING_TREE] == NEVER_BIN;
+
+    if (mts.bin == NEVER_BIN && !is_in_never_bin_on_both_trees)
+      mts.bin = tile_is_active ? AT_LAST_AND_ACTIVE_BIN : AT_LAST_BIN;
+
+    mts.resolution = tile_priority.resolution;
+    mts.priority_bin = tile_priority.priority_bin;
+    mts.distance_to_visible = tile_priority.distance_to_visible;
+    mts.required_for_activation = tile_priority.required_for_activation;
+
+    mts.visible_and_ready_to_draw =
+        tree_bin[ACTIVE_TREE] == NOW_AND_READY_TO_DRAW_BIN;
+
+    // Tiles that are required for activation shouldn't be in NEVER_BIN unless
+    // smoothness takes priority or memory policy allows nothing to be
+    // initialized.
+    DCHECK(!mts.required_for_activation || mts.bin != NEVER_BIN ||
+           tree_priority == SMOOTHNESS_TAKES_PRIORITY ||
+           memory_policy == ALLOW_NOTHING);
+
+    // If the tile is in NEVER_BIN and it does not have an active task, then we
+    // can release the resources early. If it does have the task however, we
+    // should keep it in the prioritized tile set to ensure that AssignGpuMemory
+    // can visit it.
+    if (mts.bin == NEVER_BIN &&
+        !mts.tile_versions[mts.raster_mode].raster_task_) {
+      FreeResourcesForTileAndNotifyClientIfTileWasReadyToDraw(tile);
+      continue;
+    }
+
+    // Insert the tile into a priority set.
+    tiles->InsertTile(tile, mts.bin);
+  }
+}
+
 void TileManager::ManageTiles(const GlobalStateThatImpactsTilePriority& state) {
   TRACE_EVENT0("cc", "TileManager::ManageTiles");
 
-  global_state_ = state;
+  // Update internal state.
+  if (state != global_state_) {
+    global_state_ = state;
+    prioritized_tiles_dirty_ = true;
+  }
 
   // We need to call CheckForCompletedTasks() once in-between each call
   // to ScheduleTasks() to prevent canceled tasks from being scheduled.
@@ -402,12 +652,11 @@ void TileManager::ManageTiles(const GlobalStateThatImpactsTilePriority& state) {
     did_check_for_completed_tasks_since_last_schedule_tasks_ = true;
   }
 
-  // TODO(vmpstr): See if we still need to keep tiles alive when layers release
-  // them.
-  CleanUpReleasedTiles();
+  UpdatePrioritizedTileSetIfNeeded();
 
   TileVector tiles_that_need_to_be_rasterized;
-  AssignGpuMemoryToTiles(&tiles_that_need_to_be_rasterized);
+  AssignGpuMemoryToTiles(&prioritized_tiles_,
+                         &tiles_that_need_to_be_rasterized);
 
   // Finally, schedule rasterizer tasks.
   ScheduleTasks(tiles_that_need_to_be_rasterized);
@@ -460,63 +709,8 @@ scoped_ptr<base::Value> TileManager::AllTilesAsValue() const {
   return state.PassAs<base::Value>();
 }
 
-bool TileManager::FreeTileResourcesUntilUsageIsWithinLimit(
-    EvictionTileIterator* iterator,
-    const MemoryUsage& limit,
-    MemoryUsage* usage) {
-  while (usage->Exceeds(limit)) {
-    if (!*iterator)
-      return false;
-
-    Tile* tile = **iterator;
-
-    *usage -= MemoryUsage::FromTile(tile);
-    FreeResourcesForTileAndNotifyClientIfTileWasReadyToDraw(tile);
-    ++(*iterator);
-  }
-  return true;
-}
-
-bool TileManager::FreeTileResourcesWithLowerPriorityUntilUsageIsWithinLimit(
-    EvictionTileIterator* iterator,
-    const MemoryUsage& limit,
-    const TilePriority& other_priority,
-    MemoryUsage* usage) {
-  while (usage->Exceeds(limit)) {
-    if (!*iterator)
-      return false;
-
-    Tile* tile = **iterator;
-    if (!other_priority.IsHigherPriorityThan(
-            tile->priority_for_tree_priority(global_state_.tree_priority))) {
-      return false;
-    }
-
-    *usage -= MemoryUsage::FromTile(tile);
-    FreeResourcesForTileAndNotifyClientIfTileWasReadyToDraw(tile);
-    ++(*iterator);
-  }
-  return true;
-}
-
-bool TileManager::TilePriorityViolatesMemoryPolicy(
-    const TilePriority& priority) {
-  switch (global_state_.memory_limit_policy) {
-    case ALLOW_NOTHING:
-      return true;
-    case ALLOW_ABSOLUTE_MINIMUM:
-      return priority.priority_bin > TilePriority::NOW;
-    case ALLOW_PREPAINT_ONLY:
-      return priority.priority_bin > TilePriority::SOON;
-    case ALLOW_ANYTHING:
-      return priority.distance_to_visible ==
-             std::numeric_limits<float>::infinity();
-  }
-  NOTREACHED();
-  return true;
-}
-
 void TileManager::AssignGpuMemoryToTiles(
+    PrioritizedTileSet* tiles,
     TileVector* tiles_that_need_to_be_rasterized) {
   TRACE_EVENT0("cc", "TileManager::AssignGpuMemoryToTiles");
 
@@ -529,99 +723,178 @@ void TileManager::AssignGpuMemoryToTiles(
 
   // Now give memory out to the tiles until we're out, and build
   // the needs-to-be-rasterized queue.
-  all_tiles_that_need_to_be_rasterized_are_scheduled_ = true;
-
-  MemoryUsage hard_memory_limit(global_state_.hard_memory_limit_in_bytes,
-                                global_state_.num_resources_limit);
-  MemoryUsage soft_memory_limit(global_state_.soft_memory_limit_in_bytes,
-                                global_state_.num_resources_limit);
-  MemoryUsage memory_usage(resource_pool_->acquired_memory_usage_bytes(),
-                           resource_pool_->acquired_resource_count());
-
-  EvictionTileIterator eviction_it(this, global_state_.tree_priority);
-
-  bool had_enough_memory_to_schedule_tiles_needed_now = true;
+  all_tiles_that_need_to_be_rasterized_have_memory_ = true;
+  all_tiles_required_for_activation_have_memory_ = true;
+
+  // Cast to prevent overflow.
+  int64 soft_bytes_available =
+      static_cast<int64>(bytes_releasable_) +
+      static_cast<int64>(global_state_.soft_memory_limit_in_bytes) -
+      static_cast<int64>(resource_pool_->acquired_memory_usage_bytes());
+  int64 hard_bytes_available =
+      static_cast<int64>(bytes_releasable_) +
+      static_cast<int64>(global_state_.hard_memory_limit_in_bytes) -
+      static_cast<int64>(resource_pool_->acquired_memory_usage_bytes());
+  int resources_available = resources_releasable_ +
+                            global_state_.num_resources_limit -
+                            resource_pool_->acquired_resource_count();
+  size_t soft_bytes_allocatable =
+      std::max(static_cast<int64>(0), soft_bytes_available);
+  size_t hard_bytes_allocatable =
+      std::max(static_cast<int64>(0), hard_bytes_available);
+  size_t resources_allocatable = std::max(0, resources_available);
+
+  size_t bytes_that_exceeded_memory_budget = 0;
+  size_t soft_bytes_left = soft_bytes_allocatable;
+  size_t hard_bytes_left = hard_bytes_allocatable;
+
+  size_t resources_left = resources_allocatable;
+  bool oomed_soft = false;
+  bool oomed_hard = false;
+  bool have_hit_soft_memory = false;  // Soft memory comes after hard.
 
   unsigned schedule_priority = 1u;
-  for (RasterTileIterator it(this, global_state_.tree_priority); it; ++it) {
+  for (PrioritizedTileSet::Iterator it(tiles, true); it; ++it) {
     Tile* tile = *it;
-    TilePriority priority =
-        tile->priority_for_tree_priority(global_state_.tree_priority);
-
-    if (TilePriorityViolatesMemoryPolicy(priority))
-      break;
-
-    // We won't be able to schedule this tile, so break out early.
-    if (tiles_that_need_to_be_rasterized->size() >=
-        kScheduledRasterTasksLimit) {
-      all_tiles_that_need_to_be_rasterized_are_scheduled_ = false;
-      break;
-    }
-
     ManagedTileState& mts = tile->managed_state();
+
     mts.scheduled_priority = schedule_priority++;
+
     mts.raster_mode = tile->DetermineOverallRasterMode();
+
     ManagedTileState::TileVersion& tile_version =
         mts.tile_versions[mts.raster_mode];
 
-    DCHECK(!tile_version.IsReadyToDraw());
+    // If this tile doesn't need a resource, then nothing to do.
+    if (!tile_version.requires_resource())
+      continue;
 
-    // If the tile already has a raster_task, then the memory used by it is
-    // already accounted for in memory_usage. Otherwise, we'll have to acquire
-    // more memory to create a raster task.
-    MemoryUsage memory_required_by_tile_to_be_scheduled;
-    if (!tile_version.raster_task_) {
-      memory_required_by_tile_to_be_scheduled = MemoryUsage::FromConfig(
-          tile->size(), resource_pool_->resource_format());
+    // If the tile is not needed, free it up.
+    if (mts.bin == NEVER_BIN) {
+      FreeResourcesForTileAndNotifyClientIfTileWasReadyToDraw(tile);
+      continue;
     }
 
-    bool tile_is_needed_now = priority.priority_bin == TilePriority::NOW;
-
-    // This is the memory limit that will be used by this tile. Depending on
-    // the tile priority, it will be one of hard_memory_limit or
-    // soft_memory_limit.
-    MemoryUsage& tile_memory_limit =
-        tile_is_needed_now ? hard_memory_limit : soft_memory_limit;
-
-    bool memory_usage_is_within_limit =
-        FreeTileResourcesWithLowerPriorityUntilUsageIsWithinLimit(
-            &eviction_it,
-            tile_memory_limit - memory_required_by_tile_to_be_scheduled,
-            priority,
-            &memory_usage);
-
-    // If we couldn't fit the tile into our current memory limit, then we're
-    // done.
-    if (!memory_usage_is_within_limit) {
-      if (tile_is_needed_now)
-        had_enough_memory_to_schedule_tiles_needed_now = false;
-      all_tiles_that_need_to_be_rasterized_are_scheduled_ = false;
-      break;
+    const bool tile_uses_hard_limit = mts.bin <= NOW_BIN;
+    const size_t bytes_if_allocated = BytesConsumedIfAllocated(tile);
+    const size_t tile_bytes_left =
+        (tile_uses_hard_limit) ? hard_bytes_left : soft_bytes_left;
+
+    // Hard-limit is reserved for tiles that would cause a calamity
+    // if they were to go away, so by definition they are the highest
+    // priority memory, and must be at the front of the list.
+    DCHECK(!(have_hit_soft_memory && tile_uses_hard_limit));
+    have_hit_soft_memory |= !tile_uses_hard_limit;
+
+    size_t tile_bytes = 0;
+    size_t tile_resources = 0;
+
+    // It costs to maintain a resource.
+    for (int mode = 0; mode < NUM_RASTER_MODES; ++mode) {
+      if (mts.tile_versions[mode].resource_) {
+        tile_bytes += bytes_if_allocated;
+        tile_resources++;
+      }
+    }
+
+    // Allow lower priority tiles with initialized resources to keep
+    // their memory by only assigning memory to new raster tasks if
+    // they can be scheduled.
+    bool reached_scheduled_raster_tasks_limit =
+        tiles_that_need_to_be_rasterized->size() >= kScheduledRasterTasksLimit;
+    if (!reached_scheduled_raster_tasks_limit) {
+      // If we don't have the required version, and it's not in flight
+      // then we'll have to pay to create a new task.
+      if (!tile_version.resource_ && !tile_version.raster_task_) {
+        tile_bytes += bytes_if_allocated;
+        tile_resources++;
+      }
+    }
+
+    // Tile is OOM.
+    if (tile_bytes > tile_bytes_left || tile_resources > resources_left) {
+      bool was_ready_to_draw = tile->IsReadyToDraw();
+
+      FreeResourcesForTile(tile);
+
+      // This tile was already on screen and now its resources have been
+      // released. In order to prevent checkerboarding, set this tile as
+      // rasterize on demand immediately.
+      if (mts.visible_and_ready_to_draw)
+        tile_version.set_rasterize_on_demand();
+
+      if (was_ready_to_draw)
+        client_->NotifyTileStateChanged(tile);
+
+      oomed_soft = true;
+      if (tile_uses_hard_limit) {
+        oomed_hard = true;
+        bytes_that_exceeded_memory_budget += tile_bytes;
+      }
+    } else {
+      resources_left -= tile_resources;
+      hard_bytes_left -= tile_bytes;
+      soft_bytes_left =
+          (soft_bytes_left > tile_bytes) ? soft_bytes_left - tile_bytes : 0;
+      if (tile_version.resource_)
+        continue;
+    }
+
+    DCHECK(!tile_version.resource_);
+
+    // Tile shouldn't be rasterized if |tiles_that_need_to_be_rasterized|
+    // has reached it's limit or we've failed to assign gpu memory to this
+    // or any higher priority tile. Preventing tiles that fit into memory
+    // budget to be rasterized when higher priority tile is oom is
+    // important for two reasons:
+    // 1. Tile size should not impact raster priority.
+    // 2. Tiles with existing raster task could otherwise incorrectly
+    //    be added as they are not affected by |bytes_allocatable|.
+    bool can_schedule_tile =
+        !oomed_soft && !reached_scheduled_raster_tasks_limit;
+
+    if (!can_schedule_tile) {
+      all_tiles_that_need_to_be_rasterized_have_memory_ = false;
+      if (tile->required_for_activation())
+        all_tiles_required_for_activation_have_memory_ = false;
+      it.DisablePriorityOrdering();
+      continue;
     }
 
-    memory_usage += memory_required_by_tile_to_be_scheduled;
     tiles_that_need_to_be_rasterized->push_back(tile);
   }
 
-  // Note that we should try and further reduce memory in case the above loop
-  // didn't reduce memory. This ensures that we always release as many resources
-  // as possible to stay within the memory limit.
-  FreeTileResourcesUntilUsageIsWithinLimit(
-      &eviction_it, hard_memory_limit, &memory_usage);
-
-  // Update memory_stats_from_last_assign_, which is used to display HUD
-  // information.
+  // OOM reporting uses hard-limit, soft-OOM is normal depending on limit.
+  ever_exceeded_memory_budget_ |= oomed_hard;
+  if (ever_exceeded_memory_budget_) {
+    TRACE_COUNTER_ID2("cc",
+                      "over_memory_budget",
+                      this,
+                      "budget",
+                      global_state_.hard_memory_limit_in_bytes,
+                      "over",
+                      bytes_that_exceeded_memory_budget);
+  }
   memory_stats_from_last_assign_.total_budget_in_bytes =
       global_state_.hard_memory_limit_in_bytes;
-  memory_stats_from_last_assign_.total_bytes_used = memory_usage.memory_bytes();
-  memory_stats_from_last_assign_.had_enough_memory =
-      had_enough_memory_to_schedule_tiles_needed_now;
+  memory_stats_from_last_assign_.bytes_allocated =
+      hard_bytes_allocatable - hard_bytes_left;
+  memory_stats_from_last_assign_.bytes_unreleasable =
+      resource_pool_->acquired_memory_usage_bytes() - bytes_releasable_;
+  memory_stats_from_last_assign_.bytes_over = bytes_that_exceeded_memory_budget;
 }
 
 void TileManager::FreeResourceForTile(Tile* tile, RasterMode mode) {
   ManagedTileState& mts = tile->managed_state();
-  if (mts.tile_versions[mode].resource_)
+  if (mts.tile_versions[mode].resource_) {
     resource_pool_->ReleaseResource(mts.tile_versions[mode].resource_.Pass());
+
+    DCHECK_GE(bytes_releasable_, BytesConsumedIfAllocated(tile));
+    DCHECK_GE(resources_releasable_, 1u);
+
+    bytes_releasable_ -= BytesConsumedIfAllocated(tile);
+    --resources_releasable_;
+  }
 }
 
 void TileManager::FreeResourcesForTile(Tile* tile) {
@@ -823,6 +1096,9 @@ void TileManager::OnRasterTaskCompleted(
   } else {
     tile_version.set_use_resource();
     tile_version.resource_ = resource.Pass();
+
+    bytes_releasable_ += BytesConsumedIfAllocated(tile);
+    ++resources_releasable_;
   }
 
   FreeUnusedResourcesForTile(tile);
@@ -853,6 +1129,7 @@ scoped_refptr<Tile> TileManager::CreateTile(PicturePileImpl* picture_pile,
 
   tiles_[tile->id()] = tile;
   used_layer_counts_[tile->layer_id()]++;
+  prioritized_tiles_dirty_ = true;
   return tile;
 }
 
@@ -1305,57 +1582,4 @@ void TileManager::CheckIfReadyToActivate() {
     client_->NotifyReadyToActivate();
 }
 
-TileManager::MemoryUsage::MemoryUsage() : memory_bytes_(0), resource_count_(0) {
-}
-
-TileManager::MemoryUsage::MemoryUsage(int64 memory_bytes, int resource_count)
-    : memory_bytes_(memory_bytes), resource_count_(resource_count) {
-}
-
-// static
-TileManager::MemoryUsage TileManager::MemoryUsage::FromConfig(
-    const gfx::Size& size,
-    ResourceFormat format) {
-  return MemoryUsage(Resource::MemorySizeBytes(size, format), 1);
-}
-
-// static
-TileManager::MemoryUsage TileManager::MemoryUsage::FromTile(const Tile* tile) {
-  const ManagedTileState& mts = tile->managed_state();
-  MemoryUsage total_usage;
-  for (int mode = 0; mode < NUM_RASTER_MODES; ++mode) {
-    if (mts.tile_versions[mode].resource_) {
-      total_usage += MemoryUsage::FromConfig(
-          tile->size(), mts.tile_versions[mode].resource_->format());
-    }
-  }
-  return total_usage;
-}
-
-TileManager::MemoryUsage& TileManager::MemoryUsage::operator+=(
-    const MemoryUsage& other) {
-  memory_bytes_ += other.memory_bytes_;
-  resource_count_ += other.resource_count_;
-  return *this;
-}
-
-TileManager::MemoryUsage& TileManager::MemoryUsage::operator-=(
-    const MemoryUsage& other) {
-  memory_bytes_ -= other.memory_bytes_;
-  resource_count_ -= other.resource_count_;
-  return *this;
-}
-
-TileManager::MemoryUsage TileManager::MemoryUsage::operator-(
-    const MemoryUsage& other) {
-  MemoryUsage result = *this;
-  result -= other;
-  return result;
-}
-
-bool TileManager::MemoryUsage::Exceeds(const MemoryUsage& limit) const {
-  return memory_bytes_ > limit.memory_bytes_ ||
-         resource_count_ > limit.resource_count_;
-}
-
 }  // namespace cc
diff --git a/cc/resources/tile_manager.h b/cc/resources/tile_manager.h
index fb53cab..5ad8091 100644
--- a/cc/resources/tile_manager.h
+++ b/cc/resources/tile_manager.h
@@ -21,6 +21,7 @@
 #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"
@@ -198,8 +199,10 @@ class CC_EXPORT TileManager : public RasterizerClient,
       ManagedTileState::TileVersion& tile_version =
           mts.tile_versions[HIGH_QUALITY_RASTER_MODE];
 
-      tile_version.resource_ =
-          resource_pool_->AcquireResource(tiles[i]->size());
+      tile_version.resource_ = resource_pool_->AcquireResource(gfx::Size(1, 1));
+
+      bytes_releasable_ += BytesConsumedIfAllocated(tiles[i]);
+      ++resources_releasable_;
     }
   }
 
@@ -214,7 +217,12 @@ class CC_EXPORT TileManager : public RasterizerClient,
 
   void SetGlobalStateForTesting(
       const GlobalStateThatImpactsTilePriority& state) {
-    global_state_ = 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;
+    }
   }
 
   void SetRasterizerForTesting(Rasterizer* rasterizer);
@@ -228,10 +236,13 @@ 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:
@@ -246,30 +257,11 @@ class CC_EXPORT TileManager : public RasterizerClient,
   virtual void ScheduleTasks(
       const TileVector& tiles_that_need_to_be_rasterized);
 
-  void AssignGpuMemoryToTiles(TileVector* tiles_that_need_to_be_rasterized);
+  void AssignGpuMemoryToTiles(PrioritizedTileSet* tiles,
+                              TileVector* tiles_that_need_to_be_rasterized);
+  void GetTilesWithAssignedBins(PrioritizedTileSet* tiles);
 
  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);
@@ -279,6 +271,11 @@ 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);
@@ -286,16 +283,8 @@ 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(EvictionTileIterator* iterator,
-                                                const MemoryUsage& limit,
-                                                MemoryUsage* usage);
-  bool FreeTileResourcesWithLowerPriorityUntilUsageIsWithinLimit(
-      EvictionTileIterator* iterator,
-      const MemoryUsage& limit,
-      const TilePriority& other_priority,
-      MemoryUsage* usage);
-  bool TilePriorityViolatesMemoryPolicy(const TilePriority& priority);
   bool IsReadyToActivate() const;
   void CheckIfReadyToActivate();
 
@@ -308,8 +297,16 @@ class CC_EXPORT TileManager : public RasterizerClient,
   typedef base::hash_map<Tile::Id, Tile*> TileMap;
   TileMap tiles_;
 
-  bool all_tiles_that_need_to_be_rasterized_are_scheduled_;
+  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 ever_exceeded_memory_budget_;
   MemoryHistory::Entry memory_stats_from_last_assign_;
 
   RenderingStatsInstrumentation* rendering_stats_instrumentation_;
diff --git a/cc/resources/tile_manager_unittest.cc b/cc/resources/tile_manager_unittest.cc
index 0d878cd..f894c4f 100644
--- a/cc/resources/tile_manager_unittest.cc
+++ b/cc/resources/tile_manager_unittest.cc
@@ -20,6 +20,410 @@
 namespace cc {
 namespace {
 
+class TileManagerTest : public testing::TestWithParam<bool>,
+                        public TileManagerClient {
+ public:
+  typedef std::vector<scoped_refptr<Tile> > TileVector;
+
+  TileManagerTest()
+      : memory_limit_policy_(ALLOW_ANYTHING),
+        max_tiles_(0),
+        ready_to_activate_(false) {}
+
+  void Initialize(int max_tiles,
+                  TileMemoryLimitPolicy memory_limit_policy,
+                  TreePriority tree_priority) {
+    output_surface_ = FakeOutputSurface::Create3d();
+    CHECK(output_surface_->BindToClient(&output_surface_client_));
+
+    shared_bitmap_manager_.reset(new TestSharedBitmapManager());
+    resource_provider_ = ResourceProvider::Create(
+        output_surface_.get(), shared_bitmap_manager_.get(), 0, false, 1,
+        false);
+    resource_pool_ = ResourcePool::Create(
+        resource_provider_.get(), GL_TEXTURE_2D, RGBA_8888);
+    tile_manager_ =
+        make_scoped_ptr(new FakeTileManager(this, resource_pool_.get()));
+
+    memory_limit_policy_ = memory_limit_policy;
+    max_tiles_ = max_tiles;
+    picture_pile_ = FakePicturePileImpl::CreateInfiniteFilledPile();
+
+    SetTreePriority(tree_priority);
+  }
+
+  void SetTreePriority(TreePriority tree_priority) {
+    GlobalStateThatImpactsTilePriority state;
+    gfx::Size tile_size = settings_.default_tile_size;
+
+    if (UsingMemoryLimit()) {
+      state.soft_memory_limit_in_bytes =
+          max_tiles_ * 4 * tile_size.width() * tile_size.height();
+      state.num_resources_limit = 100;
+    } else {
+      state.soft_memory_limit_in_bytes = 100 * 1000 * 1000;
+      state.num_resources_limit = max_tiles_;
+    }
+    state.hard_memory_limit_in_bytes = state.soft_memory_limit_in_bytes * 2;
+    state.memory_limit_policy = memory_limit_policy_;
+    state.tree_priority = tree_priority;
+
+    global_state_ = state;
+    resource_pool_->SetResourceUsageLimits(state.soft_memory_limit_in_bytes,
+                                           state.soft_memory_limit_in_bytes,
+                                           state.num_resources_limit);
+    tile_manager_->SetGlobalStateForTesting(state);
+  }
+
+  virtual void TearDown() OVERRIDE {
+    tile_manager_.reset(NULL);
+    picture_pile_ = NULL;
+
+    testing::Test::TearDown();
+  }
+
+  // TileManagerClient implementation.
+  virtual const std::vector<PictureLayerImpl*>& GetPictureLayers() OVERRIDE {
+    return picture_layers_;
+  }
+  virtual void NotifyReadyToActivate() OVERRIDE { ready_to_activate_ = true; }
+  virtual void NotifyTileStateChanged(const Tile* tile) OVERRIDE {}
+
+  TileVector CreateTilesWithSize(int count,
+                                 TilePriority active_priority,
+                                 TilePriority pending_priority,
+                                 const gfx::Size& tile_size) {
+    TileVector tiles;
+    for (int i = 0; i < count; ++i) {
+      scoped_refptr<Tile> tile = tile_manager_->CreateTile(picture_pile_.get(),
+                                                           tile_size,
+                                                           gfx::Rect(),
+                                                           gfx::Rect(),
+                                                           1.0,
+                                                           0,
+                                                           0,
+                                                           0);
+      tile->SetPriority(ACTIVE_TREE, active_priority);
+      tile->SetPriority(PENDING_TREE, pending_priority);
+      tiles.push_back(tile);
+    }
+    return tiles;
+  }
+
+  TileVector CreateTiles(int count,
+                         TilePriority active_priority,
+                         TilePriority pending_priority) {
+    return CreateTilesWithSize(
+        count, active_priority, pending_priority, settings_.default_tile_size);
+  }
+
+  FakeTileManager* tile_manager() { return tile_manager_.get(); }
+
+  int AssignedMemoryCount(const TileVector& tiles) {
+    int has_memory_count = 0;
+    for (TileVector::const_iterator it = tiles.begin(); it != tiles.end();
+         ++it) {
+      if (tile_manager_->HasBeenAssignedMemory(*it))
+        ++has_memory_count;
+    }
+    return has_memory_count;
+  }
+
+  bool ready_to_activate() const { return ready_to_activate_; }
+
+  // The parametrization specifies whether the max tile limit should
+  // be applied to memory or resources.
+  bool UsingResourceLimit() { return !GetParam(); }
+  bool UsingMemoryLimit() { return GetParam(); }
+
+ protected:
+  GlobalStateThatImpactsTilePriority global_state_;
+
+ private:
+  LayerTreeSettings settings_;
+  scoped_ptr<FakeTileManager> tile_manager_;
+  scoped_refptr<FakePicturePileImpl> picture_pile_;
+  FakeOutputSurfaceClient output_surface_client_;
+  scoped_ptr<FakeOutputSurface> output_surface_;
+  scoped_ptr<SharedBitmapManager> shared_bitmap_manager_;
+  scoped_ptr<ResourceProvider> resource_provider_;
+  scoped_ptr<ResourcePool> resource_pool_;
+  TileMemoryLimitPolicy memory_limit_policy_;
+  int max_tiles_;
+  bool ready_to_activate_;
+  std::vector<PictureLayerImpl*> picture_layers_;
+};
+
+TEST_P(TileManagerTest, EnoughMemoryAllowAnything) {
+  // A few tiles of each type of priority, with enough memory for all tiles.
+
+  Initialize(10, ALLOW_ANYTHING, SMOOTHNESS_TAKES_PRIORITY);
+  TileVector active_now =
+      CreateTiles(3, TilePriorityForNowBin(), TilePriority());
+  TileVector pending_now =
+      CreateTiles(3, TilePriority(), TilePriorityForNowBin());
+  TileVector active_pending_soon =
+      CreateTiles(3, TilePriorityForSoonBin(), TilePriorityForSoonBin());
+  TileVector never_bin = CreateTiles(1, TilePriority(), TilePriority());
+
+  tile_manager()->AssignMemoryToTiles(global_state_);
+
+  EXPECT_EQ(3, AssignedMemoryCount(active_now));
+  EXPECT_EQ(3, AssignedMemoryCount(pending_now));
+  EXPECT_EQ(3, AssignedMemoryCount(active_pending_soon));
+  EXPECT_EQ(0, AssignedMemoryCount(never_bin));
+}
+
+TEST_P(TileManagerTest, EnoughMemoryAllowPrepaintOnly) {
+  // A few tiles of each type of priority, with enough memory for all tiles,
+  // with the exception of never bin.
+
+  Initialize(10, ALLOW_PREPAINT_ONLY, SMOOTHNESS_TAKES_PRIORITY);
+  TileVector active_now =
+      CreateTiles(3, TilePriorityForNowBin(), TilePriority());
+  TileVector pending_now =
+      CreateTiles(3, TilePriority(), TilePriorityForNowBin());
+  TileVector active_pending_soon =
+      CreateTiles(3, TilePriorityForSoonBin(), TilePriorityForSoonBin());
+  TileVector never_bin = CreateTiles(1, TilePriority(), TilePriority());
+
+  tile_manager()->AssignMemoryToTiles(global_state_);
+
+  EXPECT_EQ(3, AssignedMemoryCount(active_now));
+  EXPECT_EQ(3, AssignedMemoryCount(pending_now));
+  EXPECT_EQ(3, AssignedMemoryCount(active_pending_soon));
+  EXPECT_EQ(0, AssignedMemoryCount(never_bin));
+}
+
+TEST_P(TileManagerTest, EnoughMemoryPendingLowResAllowAbsoluteMinimum) {
+  // A few low-res tiles required for activation, with enough memory for all
+  // tiles.
+
+  Initialize(5, ALLOW_ABSOLUTE_MINIMUM, SAME_PRIORITY_FOR_BOTH_TREES);
+  TileVector pending_low_res =
+      CreateTiles(5, TilePriority(), TilePriorityLowRes());
+
+  tile_manager()->AssignMemoryToTiles(global_state_);
+
+  EXPECT_EQ(5, AssignedMemoryCount(pending_low_res));
+}
+
+TEST_P(TileManagerTest, EnoughMemoryAllowAbsoluteMinimum) {
+  // A few tiles of each type of priority, with enough memory for all tiles,
+  // with the exception of never and soon bins.
+
+  Initialize(10, ALLOW_ABSOLUTE_MINIMUM, SMOOTHNESS_TAKES_PRIORITY);
+  TileVector active_now =
+      CreateTiles(3, TilePriorityForNowBin(), TilePriority());
+  TileVector pending_now =
+      CreateTiles(3, TilePriority(), TilePriorityForNowBin());
+  TileVector active_pending_soon =
+      CreateTiles(3, TilePriorityForSoonBin(), TilePriorityForSoonBin());
+  TileVector never_bin = CreateTiles(1, TilePriority(), TilePriority());
+
+  tile_manager()->AssignMemoryToTiles(global_state_);
+
+  EXPECT_EQ(3, AssignedMemoryCount(active_now));
+  EXPECT_EQ(3, AssignedMemoryCount(pending_now));
+  EXPECT_EQ(0, AssignedMemoryCount(active_pending_soon));
+  EXPECT_EQ(0, AssignedMemoryCount(never_bin));
+}
+
+TEST_P(TileManagerTest, EnoughMemoryAllowNothing) {
+  // A few tiles of each type of priority, with enough memory for all tiles,
+  // but allow nothing should not assign any memory.
+
+  Initialize(10, ALLOW_NOTHING, SMOOTHNESS_TAKES_PRIORITY);
+  TileVector active_now =
+      CreateTiles(3, TilePriorityForNowBin(), TilePriority());
+  TileVector pending_now =
+      CreateTiles(3, TilePriority(), TilePriorityForNowBin());
+  TileVector active_pending_soon =
+      CreateTiles(3, TilePriorityForSoonBin(), TilePriorityForSoonBin());
+  TileVector never_bin = CreateTiles(1, TilePriority(), TilePriority());
+
+  tile_manager()->AssignMemoryToTiles(global_state_);
+
+  EXPECT_EQ(0, AssignedMemoryCount(active_now));
+  EXPECT_EQ(0, AssignedMemoryCount(pending_now));
+  EXPECT_EQ(0, AssignedMemoryCount(active_pending_soon));
+  EXPECT_EQ(0, AssignedMemoryCount(never_bin));
+}
+
+TEST_P(TileManagerTest, PartialOOMMemoryToPending) {
+  // 5 tiles on active tree eventually bin, 5 tiles on pending tree that are
+  // required for activation, but only enough memory for 8 tiles. The result
+  // is all pending tree tiles get memory, and 3 of the active tree tiles
+  // get memory. None of these tiles is needed to avoid calimity (flickering or
+  // raster-on-demand) so the soft memory limit is used.
+
+  Initialize(8, ALLOW_ANYTHING, SMOOTHNESS_TAKES_PRIORITY);
+  TileVector active_tree_tiles =
+      CreateTiles(5, TilePriorityForEventualBin(), TilePriority());
+  TileVector pending_tree_tiles =
+      CreateTiles(5, TilePriority(), TilePriorityRequiredForActivation());
+  tile_manager()->AssignMemoryToTiles(global_state_);
+
+  EXPECT_EQ(5, AssignedMemoryCount(active_tree_tiles));
+  EXPECT_EQ(3, AssignedMemoryCount(pending_tree_tiles));
+
+  SetTreePriority(SAME_PRIORITY_FOR_BOTH_TREES);
+  tile_manager()->AssignMemoryToTiles(global_state_);
+
+  EXPECT_EQ(3, AssignedMemoryCount(active_tree_tiles));
+  EXPECT_EQ(5, AssignedMemoryCount(pending_tree_tiles));
+}
+
+TEST_P(TileManagerTest, PartialOOMMemoryToActive) {
+  // 5 tiles on active tree eventually bin, 5 tiles on pending tree now bin,
+  // but only enough memory for 8 tiles. The result is all active tree tiles
+  // get memory, and 3 of the pending tree tiles get memory.
+  // The pending tiles are not needed to avoid calimity (flickering or
+  // raster-on-demand) and the active tiles fit, so the soft limit is used.
+
+  Initialize(8, ALLOW_ANYTHING, SMOOTHNESS_TAKES_PRIORITY);
+  TileVector active_tree_tiles =
+      CreateTiles(5, TilePriorityForNowBin(), TilePriority());
+  TileVector pending_tree_tiles =
+      CreateTiles(5, TilePriority(), TilePriorityForNowBin());
+
+  tile_manager()->AssignMemoryToTiles(global_state_);
+
+  EXPECT_EQ(5, AssignedMemoryCount(active_tree_tiles));
+  EXPECT_EQ(3, AssignedMemoryCount(pending_tree_tiles));
+}
+
+TEST_P(TileManagerTest, TotalOOMMemoryToPending) {
+  // 10 tiles on active tree eventually bin, 10 tiles on pending tree that are
+  // required for activation, but only enough tiles for 4 tiles. The result
+  // is 4 pending tree tiles get memory, and none of the active tree tiles
+  // get memory.
+
+  Initialize(4, ALLOW_ANYTHING, SMOOTHNESS_TAKES_PRIORITY);
+  TileVector active_tree_tiles =
+      CreateTiles(10, TilePriorityForEventualBin(), TilePriority());
+  TileVector pending_tree_tiles =
+      CreateTiles(10, TilePriority(), TilePriorityRequiredForActivation());
+
+  tile_manager()->AssignMemoryToTiles(global_state_);
+
+  EXPECT_EQ(4, AssignedMemoryCount(active_tree_tiles));
+  EXPECT_EQ(0, AssignedMemoryCount(pending_tree_tiles));
+
+  SetTreePriority(SAME_PRIORITY_FOR_BOTH_TREES);
+  tile_manager()->AssignMemoryToTiles(global_state_);
+
+  if (UsingResourceLimit()) {
+    EXPECT_EQ(0, AssignedMemoryCount(active_tree_tiles));
+    EXPECT_EQ(4, AssignedMemoryCount(pending_tree_tiles));
+  } else {
+    // Pending tiles are now required to avoid calimity (flickering or
+    // raster-on-demand). Hard-limit is used and double the tiles fit.
+    EXPECT_EQ(0, AssignedMemoryCount(active_tree_tiles));
+    EXPECT_EQ(8, AssignedMemoryCount(pending_tree_tiles));
+  }
+}
+
+TEST_P(TileManagerTest, TotalOOMActiveSoonMemoryToPending) {
+  // 10 tiles on active tree soon bin, 10 tiles on pending tree that are
+  // required for activation, but only enough tiles for 4 tiles. The result
+  // is 4 pending tree tiles get memory, and none of the active tree tiles
+  // get memory.
+
+  Initialize(4, ALLOW_ANYTHING, SMOOTHNESS_TAKES_PRIORITY);
+  TileVector active_tree_tiles =
+      CreateTiles(10, TilePriorityForSoonBin(), TilePriority());
+  TileVector pending_tree_tiles =
+      CreateTiles(10, TilePriority(), TilePriorityRequiredForActivation());
+
+  tile_manager()->AssignMemoryToTiles(global_state_);
+
+  EXPECT_EQ(4, AssignedMemoryCount(active_tree_tiles));
+  EXPECT_EQ(0, AssignedMemoryCount(pending_tree_tiles));
+
+  SetTreePriority(SAME_PRIORITY_FOR_BOTH_TREES);
+  tile_manager()->AssignMemoryToTiles(global_state_);
+
+  if (UsingResourceLimit()) {
+    EXPECT_EQ(0, AssignedMemoryCount(active_tree_tiles));
+    EXPECT_EQ(4, AssignedMemoryCount(pending_tree_tiles));
+  } else {
+    // Pending tiles are now required to avoid calimity (flickering or
+    // raster-on-demand). Hard-limit is used and double the tiles fit.
+    EXPECT_EQ(0, AssignedMemoryCount(active_tree_tiles));
+    EXPECT_EQ(8, AssignedMemoryCount(pending_tree_tiles));
+  }
+}
+
+TEST_P(TileManagerTest, TotalOOMMemoryToActive) {
+  // 10 tiles on active tree eventually bin, 10 tiles on pending tree now bin,
+  // but only enough memory for 4 tiles. The result is 4 active tree tiles
+  // get memory, and none of the pending tree tiles get memory.
+
+  Initialize(4, ALLOW_ANYTHING, SMOOTHNESS_TAKES_PRIORITY);
+  TileVector active_tree_tiles =
+      CreateTiles(10, TilePriorityForNowBin(), TilePriority());
+  TileVector pending_tree_tiles =
+      CreateTiles(10, TilePriority(), TilePriorityForNowBin());
+
+  tile_manager()->AssignMemoryToTiles(global_state_);
+
+  if (UsingResourceLimit()) {
+    EXPECT_EQ(4, AssignedMemoryCount(active_tree_tiles));
+    EXPECT_EQ(0, AssignedMemoryCount(pending_tree_tiles));
+  } else {
+    // Active tiles are required to avoid calimity (flickering or
+    // raster-on-demand). Hard-limit is used and double the tiles fit.
+    EXPECT_EQ(8, AssignedMemoryCount(active_tree_tiles));
+    EXPECT_EQ(0, AssignedMemoryCount(pending_tree_tiles));
+  }
+}
+
+TEST_P(TileManagerTest, TotalOOMMemoryToNewContent) {
+  // 10 tiles on active tree now bin, 10 tiles on pending tree now bin,
+  // but only enough memory for 8 tiles. Any tile missing would cause
+  // a calamity (flickering or raster-on-demand). Depending on mode,
+  // we should use varying amounts of the higher hard memory limit.
+  if (UsingResourceLimit())
+    return;
+
+  Initialize(8, ALLOW_ANYTHING, SMOOTHNESS_TAKES_PRIORITY);
+  TileVector active_tree_tiles =
+      CreateTiles(10, TilePriorityForNowBin(), TilePriority());
+  TileVector pending_tree_tiles =
+      CreateTiles(10, TilePriority(), TilePriorityForNowBin());
+
+  // Active tiles are required to avoid calimity. The hard-limit is used and all
+  // active-tiles fit. No pending tiles are needed to avoid calamity so only 10
+  // tiles total are used.
+  tile_manager()->AssignMemoryToTiles(global_state_);
+  EXPECT_EQ(10, AssignedMemoryCount(active_tree_tiles));
+  EXPECT_EQ(0, AssignedMemoryCount(pending_tree_tiles));
+
+  // Even the hard-limit won't save us now. All tiles are required to avoid
+  // a clamity but we only have 16. The tiles will be distribted randomly
+  // given they are identical, in practice depending on their screen location.
+  SetTreePriority(SAME_PRIORITY_FOR_BOTH_TREES);
+  tile_manager()->AssignMemoryToTiles(global_state_);
+  EXPECT_EQ(16,
+            AssignedMemoryCount(active_tree_tiles) +
+                AssignedMemoryCount(pending_tree_tiles));
+
+  // The pending tree is now more important. Active tiles will take higher
+  // priority if they are ready-to-draw in practice. Importantly though,
+  // pending tiles also utilize the hard-limit.
+  SetTreePriority(NEW_CONTENT_TAKES_PRIORITY);
+  tile_manager()->AssignMemoryToTiles(global_state_);
+  EXPECT_EQ(0, AssignedMemoryCount(active_tree_tiles));
+  EXPECT_EQ(10, AssignedMemoryCount(pending_tree_tiles));
+}
+
+// If true, the max tile limit should be applied as bytes; if false,
+// as num_resources_limit.
+INSTANTIATE_TEST_CASE_P(TileManagerTests,
+                        TileManagerTest,
+                        ::testing::Values(true, false));
+
 class TileManagerTileIteratorTest : public testing::Test {
  public:
   TileManagerTileIteratorTest()
diff --git a/cc/resources/tile_priority.h b/cc/resources/tile_priority.h
index 1556b4e..f8ac9c6 100644
--- a/cc/resources/tile_priority.h
+++ b/cc/resources/tile_priority.h
@@ -122,6 +122,11 @@ enum TileMemoryLimitPolicy {
 
   // You're the only thing in town. Go crazy.
   ALLOW_ANYTHING = 3,  // Venti.
+
+  NUM_TILE_MEMORY_LIMIT_POLICIES = 4,
+
+  // NOTE: Be sure to update TreePriorityAsValue and kBinPolicyMap when adding
+  // or reordering fields.
 };
 scoped_ptr<base::Value> TileMemoryLimitPolicyAsValue(
     TileMemoryLimitPolicy policy);
@@ -130,6 +135,8 @@ enum TreePriority {
   SAME_PRIORITY_FOR_BOTH_TREES,
   SMOOTHNESS_TAKES_PRIORITY,
   NEW_CONTENT_TAKES_PRIORITY
+
+  // Be sure to update TreePriorityAsValue when adding new fields.
 };
 scoped_ptr<base::Value> TreePriorityAsValue(TreePriority prio);
 
@@ -150,6 +157,17 @@ class GlobalStateThatImpactsTilePriority {
 
   TreePriority tree_priority;
 
+  bool operator==(const GlobalStateThatImpactsTilePriority& other) const {
+    return memory_limit_policy == other.memory_limit_policy &&
+           soft_memory_limit_in_bytes == other.soft_memory_limit_in_bytes &&
+           hard_memory_limit_in_bytes == other.hard_memory_limit_in_bytes &&
+           num_resources_limit == other.num_resources_limit &&
+           tree_priority == other.tree_priority;
+  }
+  bool operator!=(const GlobalStateThatImpactsTilePriority& other) const {
+    return !(*this == other);
+  }
+
   scoped_ptr<base::Value> AsValue() const;
 };
 
diff --git a/cc/test/fake_tile_manager.cc b/cc/test/fake_tile_manager.cc
index 60f7532..1fc2e43 100644
--- a/cc/test/fake_tile_manager.cc
+++ b/cc/test/fake_tile_manager.cc
@@ -81,9 +81,11 @@ FakeTileManager::~FakeTileManager() {}
 void FakeTileManager::AssignMemoryToTiles(
     const GlobalStateThatImpactsTilePriority& state) {
   tiles_for_raster.clear();
+  all_tiles.Clear();
 
   SetGlobalStateForTesting(state);
-  AssignGpuMemoryToTiles(&tiles_for_raster);
+  GetTilesWithAssignedBins(&all_tiles);
+  AssignGpuMemoryToTiles(&all_tiles, &tiles_for_raster);
 }
 
 bool FakeTileManager::HasBeenAssignedMemory(Tile* tile) {
diff --git a/cc/test/fake_tile_manager.h b/cc/test/fake_tile_manager.h
index cbb8d6b..05dbe61 100644
--- a/cc/test/fake_tile_manager.h
+++ b/cc/test/fake_tile_manager.h
@@ -27,6 +27,7 @@ class FakeTileManager : public TileManager {
   virtual void Release(Tile* tile) OVERRIDE;
 
   std::vector<Tile*> tiles_for_raster;
+  PrioritizedTileSet all_tiles;
 };
 
 }  // namespace cc