change backing store cache to be memory-based rather than count

BUG=13763
TEST=none

Review URL: http://codereview.chromium.org/146095

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

7 files changed, 142 insertions, 44 deletions

diff --git a/base/gfx/size.h b/base/gfx/size.h
index bf0aa26..57e080b 100644
--- a/base/gfx/size.h
+++ b/base/gfx/size.h
@@ -30,6 +30,8 @@ class Size {
   int width() const { return width_; }
   int height() const { return height_; }
 
+  int GetArea() const { return width_ * height_; }
+
   void SetSize(int width, int height) {
     set_width(width);
     set_height(height);
diff --git a/chrome/browser/renderer_host/backing_store.h b/chrome/browser/renderer_host/backing_store.h
index 977553f..1114a18 100644
--- a/chrome/browser/renderer_host/backing_store.h
+++ b/chrome/browser/renderer_host/backing_store.h
@@ -49,6 +49,10 @@ class BackingStore {
   RenderWidgetHost* render_widget_host() const { return render_widget_host_; }
   const gfx::Size& size() { return size_; }
 
+  // The number of bytes that this backing store consumes.  This should roughly
+  // be size_.GetArea() * bytes per pixel.
+  size_t MemorySize();
+
 #if defined(OS_WIN)
   HDC hdc() { return hdc_; }
 
diff --git a/chrome/browser/renderer_host/backing_store_mac.cc b/chrome/browser/renderer_host/backing_store_mac.cc
index 0381f24..d87b292 100644
--- a/chrome/browser/renderer_host/backing_store_mac.cc
+++ b/chrome/browser/renderer_host/backing_store_mac.cc
@@ -20,6 +20,11 @@ BackingStore::BackingStore(RenderWidgetHost* widget, const gfx::Size& size)
 BackingStore::~BackingStore() {
 }
 
+size_t BackingStore::MemorySize() {
+  // Always 4 bytes per pixel.
+  return size_.GetArea() * 4;
+}
+
 void BackingStore::PaintRect(base::ProcessHandle process,
                              TransportDIB* bitmap,
                              const gfx::Rect& bitmap_rect) {
diff --git a/chrome/browser/renderer_host/backing_store_manager.cc b/chrome/browser/renderer_host/backing_store_manager.cc
index 7b16a43..449f0d4 100644
--- a/chrome/browser/renderer_host/backing_store_manager.cc
+++ b/chrome/browser/renderer_host/backing_store_manager.cc
@@ -10,30 +10,48 @@
 #include "chrome/browser/renderer_host/render_widget_host_painting_observer.h"
 #include "chrome/common/chrome_constants.h"
 
+
 namespace {
 
+// There are two separate caches, |large_cache| and |small_cache|.  large_cache
+// is meant for large items (tabs, popup windows), while small_cache is meant
+// for small items (extension toolstrips and buttons, etc.).  The idea is that
+// we'll almost always try to evict from large_cache first since small_cache
+// items will tend to be visible more of the time.
 typedef OwningMRUCache<RenderWidgetHost*, BackingStore*> BackingStoreCache;
-static BackingStoreCache* cache = NULL;
-
-// Returns the size of the backing store cache.
-static size_t GetBackingStoreCacheSize() {
-  // This uses a similar approach to GetMaxRendererProcessCount.  The goal
-  // is to reduce memory pressure and swapping on low-resource machines.
-  static const size_t kMaxDibCountByRamTier[] = {
-    2,  // less than 256MB
-    3,  // 256MB
-    4,  // 512MB
-    5   // 768MB and above
-  };
-
-  static size_t max_size = kMaxDibCountByRamTier[
-          std::min(base::SysInfo::AmountOfPhysicalMemoryMB() / 256,
-                   static_cast<int>(arraysize(kMaxDibCountByRamTier)) - 1)];
-  return max_size;
+static BackingStoreCache* large_cache = NULL;
+static BackingStoreCache* small_cache = NULL;
+
+// Threshold is based on a large-monitor width toolstrip.
+// TODO(erikkay) 32bpp assumption isn't great.
+const size_t kSmallThreshold = 4 * 32 * 1920;
+
+// Previously, the backing store cache was based on a set number of backing
+// stores, regardless of their size.  The numbers were chosen based on a user
+// with a maximized browser on a large monitor.  Now that the cache is based on
+// total memory size of the backing stores, we'll keep an approximation of the
+// numbers from the previous algorithm by choosing a large monitor backing store
+// size as our multiplier.
+// TODO(erikkay) Perhaps we should actually use monitor size?  That way we
+// could make an assertion like "worse case, there are two tabs in the cache".
+// However, the small_cache might mess up these calculations a bit.
+// TODO(erikkay) 32bpp assumption isn't great.
+const size_t kMemoryMultiplier = 4 * 1920 * 1200;  // ~9MB
+
+static size_t GetBackingStoreCacheMemorySize() {
+  // Compute in terms of the number of large monitor's worth of backing-store.
+  // Use a minimum of 2, and add one for each 256MB of physical memory you have.
+  // Cap at 5, the thinking being that even if you have a gigantic amount of
+  // RAM, there's a limit to how much caching helps beyond a certain number
+  // of tabs.
+  size_t mem_tier = std::min(5,
+      2 + (base::SysInfo::AmountOfPhysicalMemoryMB() / 256));
+  return mem_tier * kMemoryMultiplier;
 }
 
-// Expires the given backing store from the cache.
-void ExpireBackingStoreAt(BackingStoreCache::iterator backing_store) {
+// Expires the given |backing_store| from |cache|.
+void ExpireBackingStoreAt(BackingStoreCache* cache,
+                          BackingStoreCache::iterator backing_store) {
   RenderWidgetHost* rwh = backing_store->second->render_widget_host();
   if (rwh->painting_observer()) {
     rwh->painting_observer()->WidgetWillDestroyBackingStore(
@@ -43,6 +61,28 @@ void ExpireBackingStoreAt(BackingStoreCache::iterator backing_store) {
   cache->Erase(backing_store);
 }
 
+void CreateCacheSpace(size_t size) {
+  // Given a request for |size|, first free from the large cache (until there's
+  // only one item left) and then do the same from the small cache if we still
+  // don't have enough.
+  while (size > 0 && (large_cache->size() > 1 || small_cache->size() > 1)) {
+    BackingStoreCache* cache =
+        (large_cache->size() > 1) ? large_cache : small_cache;
+    while (size > 0 && cache->size() > 1) {
+      // Crazy C++ alert: rbegin.base() is a forward iterator pointing to end(),
+      // so we need to do -- to move one back to the actual last item.
+      BackingStoreCache::iterator entry = --cache->rbegin().base();
+      size_t entry_size = entry->second->MemorySize();
+      ExpireBackingStoreAt(cache, entry);
+      if (size > entry_size)
+        size -= entry_size;
+      else
+        size = 0;
+    }
+  }
+  DCHECK(size == 0);
+}
+
 // Creates the backing store for the host based on the dimensions passed in.
 // Removes the existing backing store if there is one.
 BackingStore* CreateBackingStore(RenderWidgetHost* host,
@@ -50,25 +90,31 @@ BackingStore* CreateBackingStore(RenderWidgetHost* host,
   // Remove any existing backing store in case we're replacing it.
   BackingStoreManager::RemoveBackingStore(host);
 
-  size_t max_cache_size = GetBackingStoreCacheSize();
-  if (max_cache_size > 0 && !cache)
-    cache = new BackingStoreCache(BackingStoreCache::NO_AUTO_EVICT);
+  if (!large_cache) {
+    large_cache = new BackingStoreCache(BackingStoreCache::NO_AUTO_EVICT);
+    small_cache = new BackingStoreCache(BackingStoreCache::NO_AUTO_EVICT);
+  }
 
-  if (cache->size() >= max_cache_size) {
-    // Need to remove an old backing store to make room for the new one. We
+  // TODO(erikkay) 32bpp is not always accurate
+  size_t new_mem = backing_store_size.GetArea() * 4;
+  size_t current_mem = BackingStoreManager::MemorySize();
+  size_t max_mem = GetBackingStoreCacheMemorySize();
+  DCHECK(new_mem < max_mem);
+  if (current_mem + new_mem > max_mem) {
+    // Need to remove old backing stores to make room for the new one. We
     // don't want to do this when the backing store is being replace by a new
     // one for the same tab, but this case won't get called then: we'll have
     // removed the onld one in the RemoveBackingStore above, and the cache
     // won't be over-sized.
-    //
-    // Crazy C++ alert: rbegin.base() is a forward iterator pointing to end(),
-    // so we need to do -- to move one back to the actual last item.
-    ExpireBackingStoreAt(--cache->rbegin().base());
+    CreateCacheSpace((current_mem + new_mem) - max_mem);
   }
+  DCHECK((BackingStoreManager::MemorySize() + new_mem) < max_mem);
 
   BackingStore* backing_store = host->AllocBackingStore(backing_store_size);
-  if (max_cache_size > 0)
-    cache->Put(host, backing_store);
+  if (new_mem > kSmallThreshold)
+    large_cache->Put(host, backing_store);
+  else
+    small_cache->Put(host, backing_store);
   return backing_store;
 }
 
@@ -119,9 +165,14 @@ BackingStore* BackingStoreManager::PrepareBackingStore(
 
 // static
 BackingStore* BackingStoreManager::Lookup(RenderWidgetHost* host) {
-  if (cache) {
-    BackingStoreCache::iterator it = cache->Peek(host);
-    if (it != cache->end())
+  if (large_cache) {
+    BackingStoreCache::iterator it = large_cache->Get(host);
+    if (it != large_cache->end())
+      return it->second;
+
+    // This moves host to the front of the MRU.
+    it = small_cache->Get(host);
+    if (it != small_cache->end())
       return it->second;
   }
   return NULL;
@@ -129,25 +180,47 @@ BackingStore* BackingStoreManager::Lookup(RenderWidgetHost* host) {
 
 // static
 void BackingStoreManager::RemoveBackingStore(RenderWidgetHost* host) {
-  if (!cache)
+  if (!large_cache)
     return;
 
+  BackingStoreCache* cache = large_cache;
   BackingStoreCache::iterator it = cache->Peek(host);
-  if (it == cache->end())
-    return;
-  cache->Erase(it);
-
-  if (cache->empty()) {
-    delete cache;
-    cache = NULL;
+  if (it == cache->end()) {
+    cache = small_cache;
+    it = cache->Peek(host);
+    if (it == cache->end())
+      return;
   }
+  cache->Erase(it);
 }
 
 // static
 bool BackingStoreManager::ExpireBackingStoreForTest(RenderWidgetHost* host) {
+  BackingStoreCache* cache = large_cache;
+
   BackingStoreCache::iterator it = cache->Peek(host);
-  if (it == cache->end())
-    return false;
-  ExpireBackingStoreAt(it);
+  if (it == cache->end()) {
+    cache = small_cache;
+    it = cache->Peek(host);
+    if (it == cache->end())
+      return false;
+  }
+  ExpireBackingStoreAt(cache, it);
   return true;
 }
+
+// static
+size_t BackingStoreManager::MemorySize() {
+  if (!large_cache)
+    return 0;
+
+  size_t mem = 0;
+  BackingStoreCache::iterator it;
+  for (it = large_cache->begin(); it != large_cache->end(); ++it)
+    mem += it->second->MemorySize();
+
+  for (it = small_cache->begin(); it != small_cache->end(); ++it)
+    mem += it->second->MemorySize();
+
+  return mem;
+}
diff --git a/chrome/browser/renderer_host/backing_store_manager.h b/chrome/browser/renderer_host/backing_store_manager.h
index 3078a93..625e87f 100644
--- a/chrome/browser/renderer_host/backing_store_manager.h
+++ b/chrome/browser/renderer_host/backing_store_manager.h
@@ -63,6 +63,9 @@ class BackingStoreManager {
   // removed, false if it wasn't found.
   static bool ExpireBackingStoreForTest(RenderWidgetHost* host);
 
+  // Current size in bytes of the backing store cache.
+  static size_t MemorySize();
+
  private:
   // Not intended for instantiation.
   BackingStoreManager() {}
diff --git a/chrome/browser/renderer_host/backing_store_win.cc b/chrome/browser/renderer_host/backing_store_win.cc
index 54b67c6..ef09f89 100644
--- a/chrome/browser/renderer_host/backing_store_win.cc
+++ b/chrome/browser/renderer_host/backing_store_win.cc
@@ -74,6 +74,10 @@ BackingStore::~BackingStore() {
   DeleteDC(hdc_);
 }
 
+size_t BackingStore::MemorySize() {
+  return size_.GetArea() * (color_depth_ / 8);
+}
+
 // static
 bool BackingStore::ColorManagementEnabled() {
   static bool enabled = false;
diff --git a/chrome/browser/renderer_host/backing_store_x.cc b/chrome/browser/renderer_host/backing_store_x.cc
index a2397a2..74c2203 100644
--- a/chrome/browser/renderer_host/backing_store_x.cc
+++ b/chrome/browser/renderer_host/backing_store_x.cc
@@ -77,6 +77,13 @@ BackingStore::~BackingStore() {
   XFreeGC(display_, static_cast<GC>(pixmap_gc_));
 }
 
+size_t BackingStore::MemorySize() {
+  if (!use_render_)
+    return size_.GetArea() * (pixmap_bpp_ / 8);
+  else
+    return size_.GetArea() * 4;
+}
+
 void BackingStore::PaintRectWithoutXrender(TransportDIB* bitmap,
                                            const gfx::Rect &bitmap_rect) {
   const int width = bitmap_rect.width();