New disk cache eviction algorithm (partial implementation).

Disabled by a #def. When enabled, file format 2.1 is used,
with a possible update from ver 2.0. If a version with this
code disabled is run after the upgrade, it will just
discard the file and go back to 2.0.

We now put some of those extra list to use! Entries are
separated into various lists depending on how often are
used, and we keep track of previously evicted entries.

If the new algorithm is not enabled, most of the code just
goes through a different path (with the old code instead of
the new one). One notable exception is OpenFollowingEntry,
used to enumerate the entries on the cache; the code changed
significantly to support the new version of the "cache
iterator", but functionally should do the same as the current
code.


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

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

13 files changed, 638 insertions, 110 deletions

diff --git a/net/disk_cache/backend_impl.cc b/net/disk_cache/backend_impl.cc
index 52d8f65..9f560cc 100644
--- a/net/disk_cache/backend_impl.cc
+++ b/net/disk_cache/backend_impl.cc
@@ -17,6 +17,9 @@
 #include "net/disk_cache/hash.h"
 #include "net/disk_cache/file.h"
 
+// Uncomment this to use the new eviction algorithm.
+// #define USE_NEW_EVICTION
+
 using base::Time;
 using base::TimeDelta;
 
@@ -184,6 +187,10 @@ bool BackendImpl::Init() {
   if (init_)
     return false;
 
+#ifdef USE_NEW_EVICTION
+  new_eviction_ = true;
+#endif
+
   bool create_files = false;
   if (!InitBackingStore(&create_files)) {
     ReportError(ERR_STORAGE_ERROR);
@@ -231,7 +238,7 @@ bool BackendImpl::Init() {
   if (!stats_.Init(this, &data_->header.stats))
     return false;
 
-  disabled_ = !rankings_.Init(this);
+  disabled_ = !rankings_.Init(this, new_eviction_);
   eviction_.Init(this);
 
   return !disabled_;
@@ -256,7 +263,16 @@ BackendImpl::~BackendImpl() {
 int32 BackendImpl::GetEntryCount() const {
   if (!index_)
     return 0;
-  return data_->header.num_entries;
+  // num_entries includes entries already evicted.
+  int32 not_deleted = data_->header.num_entries -
+                      data_->header.lru.sizes[Rankings::DELETED];
+
+  if (not_deleted < 0) {
+    NOTREACHED();
+    not_deleted = 0;
+  }
+
+  return not_deleted;
 }
 
 bool BackendImpl::OpenEntry(const std::string& key, Entry** entry) {
@@ -272,6 +288,13 @@ bool BackendImpl::OpenEntry(const std::string& key, Entry** entry) {
     return false;
   }
 
+  if (ENTRY_NORMAL != cache_entry->entry()->Data()->state) {
+    // The entry was already evicted.
+    cache_entry->Release();
+    stats_.OnEvent(Stats::OPEN_MISS);
+    return false;
+  }
+
   eviction_.OnOpenEntry(cache_entry);
   DCHECK(entry);
   *entry = cache_entry;
@@ -285,16 +308,24 @@ bool BackendImpl::CreateEntry(const std::string& key, Entry** entry) {
   if (disabled_ || key.empty())
     return false;
 
+  DCHECK(entry);
+  *entry = NULL;
+
   Time start = Time::Now();
   uint32 hash = Hash(key);
 
   scoped_refptr<EntryImpl> parent;
   Addr entry_address(data_->table[hash & mask_]);
   if (entry_address.is_initialized()) {
+    // We have an entry already. It could be the one we are looking for, or just
+    // a hash conflict.
+    EntryImpl* old_entry = MatchEntry(key, hash, false);
+    if (old_entry)
+      return ResurrectEntry(old_entry, entry);
+
     EntryImpl* parent_entry = MatchEntry(key, hash, true);
     if (!parent_entry) {
-      stats_.OnEvent(Stats::CREATE_MISS);
-      Trace("create entry miss ");
+      NOTREACHED();
       return false;
     }
     parent.swap(&parent_entry);
@@ -339,14 +370,11 @@ bool BackendImpl::CreateEntry(const std::string& key, Entry** entry) {
   block_files_.GetFile(entry_address)->Store(cache_entry->entry());
   block_files_.GetFile(node_address)->Store(cache_entry->rankings());
 
-  data_->header.num_entries++;
-  DCHECK(data_->header.num_entries > 0);
+  IncreaseNumEntries();
   eviction_.OnCreateEntry(cache_entry);
   if (!parent.get())
     data_->table[hash & mask_] = entry_address.value();
 
-  DCHECK(entry);
-  *entry = NULL;
   cache_entry.swap(reinterpret_cast<EntryImpl**>(entry));
 
   UMA_HISTOGRAM_TIMES("DiskCache.CreateTime", Time::Now() - start);
@@ -451,8 +479,8 @@ bool BackendImpl::OpenNextEntry(void** iter, Entry** next_entry) {
 }
 
 void BackendImpl::EndEnumeration(void** iter) {
-  Rankings::ScopedRankingsBlock rankings(&rankings_,
-      reinterpret_cast<CacheRankingsBlock*>(*iter));
+  scoped_ptr<Rankings::Iterator> iterator(
+      reinterpret_cast<Rankings::Iterator*>(*iter));
   *iter = NULL;
 }
 
@@ -600,11 +628,26 @@ void BackendImpl::InternalDoomEntry(EntryImpl* entry) {
     data_->table[hash & mask_] = child;
   }
 
-  data_->header.num_entries--;
-  DCHECK(data_->header.num_entries >= 0);
+  if (!new_eviction_) {
+    DecreaseNumEntries();
+  }
+
   stats_.OnEvent(Stats::DOOM_ENTRY);
 }
 
+// An entry may be linked on the DELETED list for a while after being doomed.
+// This function is called when we want to remove it.
+void BackendImpl::RemoveEntry(EntryImpl* entry) {
+  if (!new_eviction_)
+    return;
+
+  DCHECK(ENTRY_DOOMED == entry->entry()->Data()->state);
+
+  Trace("Remove entry 0x%p", entry);
+  eviction_.OnDestroyEntry(entry);
+  DecreaseNumEntries();
+}
+
 void BackendImpl::CacheEntryDestroyed() {
   DecreaseNumRefs();
 }
@@ -742,6 +785,10 @@ bool BackendImpl::CreateBackingStore(disk_cache::File* file) {
   IndexHeader header;
   header.table_len = DesiredIndexTableLen(max_size_);
 
+  // We need file version 2.1 for the new eviction algorithm.
+  if (new_eviction_)
+    header.version = 0x20001;
+
   if (!file->Write(&header, sizeof(header), 0))
     return false;
 
@@ -962,49 +1009,153 @@ bool BackendImpl::OpenFollowingEntry(bool forward, void** iter,
   if (disabled_)
     return false;
 
-  Rankings::ScopedRankingsBlock rankings(&rankings_,
-      reinterpret_cast<CacheRankingsBlock*>(*iter));
-  CacheRankingsBlock* next_block = forward ?
-      rankings_.GetNext(rankings.get(), Rankings::NO_USE) :
-      rankings_.GetPrev(rankings.get(), Rankings::NO_USE);
-  Rankings::ScopedRankingsBlock next(&rankings_, next_block);
+  DCHECK(iter);
+  DCHECK(next_entry);
   *next_entry = NULL;
+
+  const int kListsToSearch = 3;
+  scoped_refptr<EntryImpl> entries[kListsToSearch];
+  scoped_ptr<Rankings::Iterator> iterator(
+      reinterpret_cast<Rankings::Iterator*>(*iter));
   *iter = NULL;
-  if (!next.get())
+
+  if (!iterator.get()) {
+    iterator.reset(new Rankings::Iterator(&rankings_));
+    bool ret = false;
+
+    // Get an entry from each list.
+    for (int i = 0; i < kListsToSearch; i++) {
+      EntryImpl* temp = NULL;
+      ret |= OpenFollowingEntryFromList(forward, static_cast<Rankings::List>(i),
+                                        &iterator->nodes[i], &temp);
+      entries[i].swap(&temp);  // The entry was already addref'd.
+    }
+    if (!ret)
+      return false;
+  } else {
+    // Get the next entry from the last list, and the actual entries for the
+    // elements on the other lists.
+    for (int i = 0; i < kListsToSearch; i++) {
+      EntryImpl* temp = NULL;
+      if (iterator->list == i) {
+          OpenFollowingEntryFromList(forward, iterator->list,
+                                     &iterator->nodes[i], &temp);
+      } else {
+        temp = GetEnumeratedEntry(iterator->nodes[i]);
+      }
+
+      entries[i].swap(&temp);  // The entry was already addref'd.
+    }
+  }
+
+  int newest = -1;
+  int oldest = -1;
+  Time access_times[kListsToSearch];
+  for (int i = 0; i < kListsToSearch; i++) {
+    if (entries[i].get()) {
+      access_times[i] = entries[i]->GetLastUsed();
+      if (newest < 0) {
+        DCHECK(oldest < 0);
+        newest = oldest = i;
+        continue;
+      }
+      if (access_times[i] > access_times[newest])
+        newest = i;
+      if (access_times[i] < access_times[oldest])
+        oldest = i;
+    }
+  }
+
+  if (newest < 0 || oldest < 0)
+    return false;
+
+  if (forward) {
+    entries[newest].swap(reinterpret_cast<EntryImpl**>(next_entry));
+    iterator->list = static_cast<Rankings::List>(newest);
+  } else {
+    entries[oldest].swap(reinterpret_cast<EntryImpl**>(next_entry));
+    iterator->list = static_cast<Rankings::List>(oldest);
+  }
+
+  *iter = iterator.release();
+  return true;
+}
+
+bool BackendImpl::OpenFollowingEntryFromList(bool forward, Rankings::List list,
+                                             CacheRankingsBlock** from_entry,
+                                             EntryImpl** next_entry) {
+  if (disabled_)
+    return false;
+
+  if (!new_eviction_ && Rankings::NO_USE != list)
+    return false;
+
+  Rankings::ScopedRankingsBlock rankings(&rankings_, *from_entry);
+  CacheRankingsBlock* next_block = forward ?
+      rankings_.GetNext(rankings.get(), list) :
+      rankings_.GetPrev(rankings.get(), list);
+  Rankings::ScopedRankingsBlock next(&rankings_, next_block);
+  *from_entry = NULL;
+
+  *next_entry = GetEnumeratedEntry(next.get());
+  if (!*next_entry)
     return false;
 
+  *from_entry = next.release();
+  return true;
+}
+
+EntryImpl* BackendImpl::GetEnumeratedEntry(CacheRankingsBlock* next) {
+  if (!next)
+    return NULL;
+
   scoped_refptr<EntryImpl> entry;
+  EntryImpl* temp = NULL;
+
   if (next->Data()->pointer) {
     entry = reinterpret_cast<EntryImpl*>(next->Data()->pointer);
-  } else {
-    bool dirty;
-    EntryImpl* temp = NULL;
-    if (NewEntry(Addr(next->Data()->contents), &temp, &dirty))
-      return false;
     entry.swap(&temp);
+    return temp;
+  }
 
-    if (dirty) {
-      // We cannot trust this entry. Call MatchEntry to go through the regular
-      // path and take the appropriate action.
-      std::string key = entry->GetKey();
-      uint32 hash = entry->GetHash();
-      entry = NULL;  // Release the entry.
-      temp = MatchEntry(key, hash, false);
-      if (temp)
-        temp->Release();
+  bool dirty;
+  if (NewEntry(Addr(next->Data()->contents), &temp, &dirty))
+    return NULL;
+  entry.swap(&temp);
+
+  if (dirty) {
+    // We cannot trust this entry. Call MatchEntry to go through the regular
+    // path and take the appropriate action.
+    std::string key = entry->GetKey();
+    uint32 hash = entry->GetHash();
+    entry = NULL;  // Release the entry.
+    temp = MatchEntry(key, hash, false);
+    if (temp)
+      temp->Release();
 
-      return false;
-    }
+    return NULL;
+  }
 
-    entry.swap(&temp);
-    temp = EntryImpl::Update(temp);  // Update returns an adref'd entry.
-    entry.swap(&temp);
-    if (!entry.get())
-      return false;
+  entry.swap(&temp);
+  return EntryImpl::Update(temp);  // Update returns an adref'd entry.
+}
+
+bool BackendImpl::ResurrectEntry(EntryImpl* deleted_entry, Entry** entry) {
+  if (ENTRY_NORMAL == deleted_entry->entry()->Data()->state) {
+    deleted_entry->Release();
+    stats_.OnEvent(Stats::CREATE_MISS);
+    Trace("create entry miss ");
+    return false;
   }
 
-  entry.swap(reinterpret_cast<EntryImpl**>(next_entry));
-  *iter = next.release();
+  // We are attempting to create an entry and found out that the entry was
+  // previously deleted.
+
+  eviction_.OnCreateEntry(deleted_entry);
+  *entry = deleted_entry;
+
+  stats_.OnEvent(Stats::CREATE_HIT);
+  Trace("Resurrect entry hit ");
   return true;
 }
 
@@ -1017,8 +1168,8 @@ void BackendImpl::DestroyInvalidEntry(Addr address, EntryImpl* entry) {
   eviction_.OnDoomEntry(entry);
   entry->InternalDoom();
 
-  data_->header.num_entries--;
-  DCHECK(data_->header.num_entries >= 0);
+  if (!new_eviction_)
+    DecreaseNumEntries();
   stats_.OnEvent(Stats::INVALID_ENTRY);
 }
 
@@ -1049,6 +1200,19 @@ void BackendImpl::DecreaseNumRefs() {
     RestartCache();
 }
 
+void BackendImpl::IncreaseNumEntries() {
+  data_->header.num_entries++;
+  DCHECK(data_->header.num_entries > 0);
+}
+
+void BackendImpl::DecreaseNumEntries() {
+  data_->header.num_entries--;
+  if (data_->header.num_entries < 0) {
+    NOTREACHED();
+    data_->header.num_entries = 0;
+  }
+}
+
 void BackendImpl::LogStats() {
   StatsItems stats;
   GetStats(&stats);
@@ -1058,6 +1222,14 @@ void BackendImpl::LogStats() {
   }
 }
 
+void BackendImpl::UpgradeTo2_1() {
+  // 2.1 is basically the same as 2.0, except that new fields are actually
+  // updated by the new eviction algorithm.
+  DCHECK(0x20000 == data_->header.version);
+  data_->header.version = 0x20001;
+  data_->header.lru.sizes[Rankings::NO_USE] = data_->header.num_entries;
+}
+
 bool BackendImpl::CheckIndex() {
   if (!data_) {
     LOG(ERROR) << "Unable to map Index file";
@@ -1070,10 +1242,23 @@ bool BackendImpl::CheckIndex() {
     return false;
   }
 
-  if (kIndexMagic != data_->header.magic ||
-      kCurrentVersion != data_->header.version) {
-    LOG(ERROR) << "Invalid file version or magic";
-    return false;
+  if (new_eviction_) {
+    // We support versions 2.0 and 2.1, upgrading 2.0 to 2.1.
+    if (kIndexMagic != data_->header.magic ||
+        kCurrentVersion >> 16 != data_->header.version >> 16) {
+      LOG(ERROR) << "Invalid file version or magic";
+      return false;
+    }
+    if (kCurrentVersion == data_->header.version) {
+      // We need file version 2.1 for the new eviction algorithm.
+      UpgradeTo2_1();
+    }
+  } else {
+    if (kIndexMagic != data_->header.magic ||
+        kCurrentVersion != data_->header.version) {
+      LOG(ERROR) << "Invalid file version or magic";
+      return false;
+    }
   }
 
   if (!data_->header.table_len) {
diff --git a/net/disk_cache/backend_impl.h b/net/disk_cache/backend_impl.h
index 89be795..f2ec98d 100644
--- a/net/disk_cache/backend_impl.h
+++ b/net/disk_cache/backend_impl.h
@@ -4,8 +4,8 @@
 
 // See net/disk_cache/disk_cache.h for the public interface of the cache.
 
-#ifndef NET_DISK_CACHE_BACKEND_IMPL_H__
-#define NET_DISK_CACHE_BACKEND_IMPL_H__
+#ifndef NET_DISK_CACHE_BACKEND_IMPL_H_
+#define NET_DISK_CACHE_BACKEND_IMPL_H_
 
 #include "base/timer.h"
 #include "net/disk_cache/block_files.h"
@@ -24,11 +24,13 @@ class BackendImpl : public Backend {
  public:
   explicit BackendImpl(const std::wstring& path)
       : path_(path), block_files_(path), mask_(0), max_size_(0), init_(false),
-        restarted_(false), unit_test_(false), read_only_(false) {}
+        restarted_(false), unit_test_(false), read_only_(false),
+        new_eviction_(false) {}
   // mask can be used to limit the usable size of the hash table, for testing.
   BackendImpl(const std::wstring& path, uint32 mask)
       : path_(path), block_files_(path), mask_(mask), max_size_(0),
-        init_(false), restarted_(false), unit_test_(false), read_only_(false) {}
+        init_(false), restarted_(false), unit_test_(false), read_only_(false),
+        new_eviction_(false) {}
   ~BackendImpl();
 
   // Performs general initialization for this current instance of the cache.
@@ -77,9 +79,12 @@ class BackendImpl : public Backend {
   // method checks it and takes the appropriate action.
   void RecoveredEntry(CacheRankingsBlock* rankings);
 
-  // Permanently deletes an entry.
+  // Permanently deletes an entry, but still keeps track of it.
   void InternalDoomEntry(EntryImpl* entry);
 
+  // Removes all references to this entry.
+  void RemoveEntry(EntryImpl* entry);
+
   // This method must be called whenever an entry is released for the last time.
   void CacheEntryDestroyed();
 
@@ -144,12 +149,24 @@ class BackendImpl : public Backend {
   // Returns a given entry from the cache. The entry to match is determined by
   // key and hash, and the returned entry may be the matched one or it's parent
   // on the list of entries with the same hash (or bucket).
-  EntryImpl* MatchEntry(const std::string& key, uint32 hash,
-                         bool find_parent);
+  EntryImpl* MatchEntry(const std::string& key, uint32 hash, bool find_parent);
 
   // Opens the next or previous entry on a cache iteration.
   bool OpenFollowingEntry(bool forward, void** iter, Entry** next_entry);
 
+  // Opens the next or previous entry on a single list. If successfull,
+  // |from_entry| will be updated to point to the new entry, otherwise it will
+  // be set to NULL; in other words, it is used as an explicit iterator.
+  bool OpenFollowingEntryFromList(bool forward, Rankings::List list,
+                                  CacheRankingsBlock** from_entry,
+                                  EntryImpl** next_entry);
+
+  // Returns the entry that is pointed by |next|.
+  EntryImpl* GetEnumeratedEntry(CacheRankingsBlock* next);
+
+  // Re-opens an entry that was previously deleted.
+  bool ResurrectEntry(EntryImpl* deleted_entry, Entry** entry);
+
   void DestroyInvalidEntry(Addr address, EntryImpl* entry);
 
   // Handles the used storage count.
@@ -159,10 +176,15 @@ class BackendImpl : public Backend {
   // Update the number of referenced cache entries.
   void IncreaseNumRefs();
   void DecreaseNumRefs();
+  void IncreaseNumEntries();
+  void DecreaseNumEntries();
 
   // Dumps current cache statistics to the log.
   void LogStats();
 
+  // Upgrades the index file to version 2.1.
+  void UpgradeTo2_1();
+
   // Performs basic checks on the index file. Returns false on failure.
   bool CheckIndex();
 
@@ -181,13 +203,14 @@ class BackendImpl : public Backend {
   int32 max_size_;  // Maximum data size for this instance.
   Eviction eviction_;  // Handler of the eviction algorithm.
   int num_refs_;  // Number of referenced cache entries.
-  int max_refs_;  // Max number of eferenced cache entries.
+  int max_refs_;  // Max number of referenced cache entries.
   int num_pending_io_;  // Number of pending IO operations;
   bool init_;  // controls the initialization of the system.
   bool restarted_;
   bool unit_test_;
   bool read_only_;  // Prevents updates of the rankings data (used by tools).
   bool disabled_;
+  bool new_eviction_;  // What eviction algorithm should be used.
 
   Stats stats_;  // Usage statistcs.
   base::RepeatingTimer<BackendImpl> timer_;  // Usage timer.
@@ -198,5 +221,5 @@ class BackendImpl : public Backend {
 
 }  // namespace disk_cache
 
-#endif  // NET_DISK_CACHE_BACKEND_IMPL_H__
+#endif  // NET_DISK_CACHE_BACKEND_IMPL_H_
 
diff --git a/net/disk_cache/backend_unittest.cc b/net/disk_cache/backend_unittest.cc
index 3c9b166..5e09a63 100644
--- a/net/disk_cache/backend_unittest.cc
+++ b/net/disk_cache/backend_unittest.cc
@@ -259,11 +259,7 @@ void DiskCacheBackendTest::BackendSetSize() {
 
   SetMaxSize(cache_size);
 
-  // Verify that the cache is 95% full.
-  ASSERT_TRUE(cache_->OpenEntry(first, &entry));
-  EXPECT_EQ(cache_size * 3 / 4, entry->GetDataSize(0));
-  EXPECT_EQ(cache_size / 5, entry->GetDataSize(1));
-  entry->Close();
+  // The cache is 95% full.
 
   ASSERT_TRUE(cache_->CreateEntry(second, &entry));
   EXPECT_EQ(cache_size / 10, entry->WriteData(0, 0, buffer, cache_size / 10,
@@ -692,6 +688,8 @@ void DiskCacheBackendTest::BackendDoomBetween() {
 
   ASSERT_TRUE(cache_->CreateEntry("fourth", &entry));
   entry->Close();
+  ASSERT_TRUE(cache_->OpenEntry("fourth", &entry));
+  entry->Close();
 
   PlatformThread::Sleep(20);
   Time final = Time::Now();
diff --git a/net/disk_cache/disk_cache.h b/net/disk_cache/disk_cache.h
index 7d6e41a..5173ab9 100644
--- a/net/disk_cache/disk_cache.h
+++ b/net/disk_cache/disk_cache.h
@@ -3,10 +3,10 @@
 // found in the LICENSE file.
 
 // Defines the public interface of the disk cache. For more details see
-// http://wiki/Main/ChromeDiskCacheBackend
+// http://dev.chromium.org/developers/design-documents/disk-cache
 
-#ifndef NET_DISK_CACHE_DISK_CACHE_H__
-#define NET_DISK_CACHE_DISK_CACHE_H__
+#ifndef NET_DISK_CACHE_DISK_CACHE_H_
+#define NET_DISK_CACHE_DISK_CACHE_H_
 
 #include <string>
 #include <vector>
@@ -183,5 +183,5 @@ class Entry {
 
 }  // namespace disk_cache
 
-#endif  // NET_DISK_CACHE_DISK_CACHE_H__
+#endif  // NET_DISK_CACHE_DISK_CACHE_H_
 
diff --git a/net/disk_cache/disk_format.h b/net/disk_cache/disk_format.h
index 7dc2e7c..f089d7b 100644
--- a/net/disk_cache/disk_format.h
+++ b/net/disk_cache/disk_format.h
@@ -52,8 +52,8 @@
 // being currently used, it means that the entry was not properly closed on a
 // previous run, so it is discarded.
 
-#ifndef NET_DISK_CACHE_DISK_FORMAT_H__
-#define NET_DISK_CACHE_DISK_FORMAT_H__
+#ifndef NET_DISK_CACHE_DISK_FORMAT_H_
+#define NET_DISK_CACHE_DISK_FORMAT_H_
 
 #include "base/basictypes.h"
 
@@ -66,12 +66,14 @@ const uint32 kIndexMagic = 0xC103CAC3;
 const uint32 kCurrentVersion = 0x20000;  // Version 2.0.
 
 struct LruData {
+  int32     pad1[3];
+  int32     sizes[5];
   CacheAddr heads[5];
   CacheAddr tails[5];
   CacheAddr transaction;     // In-flight operation target.
   int32     operation;       // Actual in-flight operation.
   int32     operation_list;  // In-flight operation list.
-  int32     pad[7];
+  int32     pad2[7];
 };
 
 // Header for the master index file.
@@ -86,7 +88,7 @@ struct IndexHeader {
   int32       table_len;     // Actual size of the table (0 == kIndexTablesize).
   int32       crash;         // Signals a previous crash.
   int32       experiment;    // Id of an ongoing test.
-  int32       pad[62];
+  int32       pad[54];
   LruData     lru;           // Eviction control data.
   IndexHeader() {
     memset(this, 0, sizeof(*this));
@@ -188,5 +190,5 @@ COMPILE_ASSERT(sizeof(BlockFileHeader) == kBlockHeaderSize, bad_header);
 
 }  // namespace disk_cache
 
-#endif  // NET_DISK_CACHE_DISK_FORMAT_H__
+#endif  // NET_DISK_CACHE_DISK_FORMAT_H_
 
diff --git a/net/disk_cache/entry_impl.cc b/net/disk_cache/entry_impl.cc
index 9db5647..361a7ee 100644
--- a/net/disk_cache/entry_impl.cc
+++ b/net/disk_cache/entry_impl.cc
@@ -92,27 +92,7 @@ EntryImpl::EntryImpl(BackendImpl* backend, Addr address)
 // written before).
 EntryImpl::~EntryImpl() {
   if (doomed_) {
-    UMA_HISTOGRAM_COUNTS("DiskCache.DeleteHeader", GetDataSize(0));
-    UMA_HISTOGRAM_COUNTS("DiskCache.DeleteData", GetDataSize(1));
-    for (int index = 0; index < NUM_STREAMS; index++) {
-      Addr address(entry_.Data()->data_addr[index]);
-      if (address.is_initialized()) {
-        DeleteData(address, index);
-        backend_->ModifyStorageSize(entry_.Data()->data_size[index] -
-                                        unreported_size_[index], 0);
-      }
-    }
-    Addr address(entry_.Data()->long_key);
-    DeleteData(address, kKeyFileIndex);
-    backend_->ModifyStorageSize(entry_.Data()->key_len, 0);
-
-    memset(node_.buffer(), 0, node_.size());
-    memset(entry_.buffer(), 0, entry_.size());
-    node_.Store();
-    entry_.Store();
-
-    backend_->DeleteBlock(node_.address(), false);
-    backend_->DeleteBlock(entry_.address(), false);
+    DeleteEntryData(true);
   } else {
     bool ret = true;
     for (int index = 0; index < NUM_STREAMS; index++) {
@@ -474,6 +454,39 @@ void EntryImpl::InternalDoom() {
   doomed_ = true;
 }
 
+void EntryImpl::DeleteEntryData(bool everything) {
+  DCHECK(doomed_ || !everything);
+
+  UMA_HISTOGRAM_COUNTS("DiskCache.DeleteHeader", GetDataSize(0));
+  UMA_HISTOGRAM_COUNTS("DiskCache.DeleteData", GetDataSize(1));
+  for (int index = 0; index < NUM_STREAMS; index++) {
+    Addr address(entry_.Data()->data_addr[index]);
+    if (address.is_initialized()) {
+      DeleteData(address, index);
+      backend_->ModifyStorageSize(entry_.Data()->data_size[index] -
+                                      unreported_size_[index], 0);
+    }
+  }
+
+  if (!everything)
+    return;
+
+  // Remove all traces of this entry.
+  backend_->RemoveEntry(this);
+
+  Addr address(entry_.Data()->long_key);
+  DeleteData(address, kKeyFileIndex);
+  backend_->ModifyStorageSize(entry_.Data()->key_len, 0);
+
+  memset(node_.buffer(), 0, node_.size());
+  memset(entry_.buffer(), 0, entry_.size());
+  node_.Store();
+  entry_.Store();
+
+  backend_->DeleteBlock(node_.address(), false);
+  backend_->DeleteBlock(entry_.address(), false);
+}
+
 CacheAddr EntryImpl::GetNextAddress() {
   return entry_.Data()->next;
 }
diff --git a/net/disk_cache/entry_impl.h b/net/disk_cache/entry_impl.h
index 6d3d614..5a467e4 100644
--- a/net/disk_cache/entry_impl.h
+++ b/net/disk_cache/entry_impl.h
@@ -2,8 +2,8 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#ifndef NET_DISK_CACHE_ENTRY_IMPL_H__
-#define NET_DISK_CACHE_ENTRY_IMPL_H__
+#ifndef NET_DISK_CACHE_ENTRY_IMPL_H_
+#define NET_DISK_CACHE_ENTRY_IMPL_H_
 
 #include "net/disk_cache/disk_cache.h"
 #include "net/disk_cache/storage_block.h"
@@ -52,9 +52,13 @@ class EntryImpl : public Entry, public base::RefCounted<EntryImpl> {
   // Returns true if this entry matches the lookup arguments.
   bool IsSameEntry(const std::string& key, uint32 hash);
 
-  // Permamently destroys this entry
+  // Permamently destroys this entry.
   void InternalDoom();
 
+  // Deletes this entry from disk. If |everything| is false, only the user data
+  // will be removed, leaving the key and control data intact.
+  void DeleteEntryData(bool everything);
+
   // Returns the address of the next entry on the list of entries with the same
   // hash.
   CacheAddr GetNextAddress();
@@ -148,5 +152,5 @@ class EntryImpl : public Entry, public base::RefCounted<EntryImpl> {
 
 }  // namespace disk_cache
 
-#endif  // NET_DISK_CACHE_ENTRY_IMPL_H__
+#endif  // NET_DISK_CACHE_ENTRY_IMPL_H_
 
diff --git a/net/disk_cache/eviction.cc b/net/disk_cache/eviction.cc
index 11bce72..a7eb9fc 100644
--- a/net/disk_cache/eviction.cc
+++ b/net/disk_cache/eviction.cc
@@ -2,6 +2,30 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+// The eviction policy is a very simple pure LRU, so the elements at the end of
+// the list are evicted until kCleanUpMargin free space is available. There is
+// only one list in use (Rankings::NO_USE), and elements are sent to the front
+// of the list whenever they are accessed.
+
+// The new (in-development) eviction policy ads re-use as a factor to evict
+// an entry. The story so far:
+
+// Entries are linked on separate lists depending on how often they are used.
+// When we see an element for the first time, it goes to the NO_USE list; if
+// the object is reused later on, we move it to the LOW_USE list, until it is
+// used kHighUse times, at which point it is moved to the HIGH_USE list.
+// Whenever an element is evicted, we move it to the DELETED list so that if the
+// element is accessed again, we remember the fact that it was already stored
+// and maybe in the future we don't evict that element.
+
+// When we have to evict an element, first we try to use the last element from
+// the NO_USE list, then we move to the LOW_USE and only then we evict an entry
+// from the HIGH_USE. We attempt to keep entries on the cache for at least
+// kTargetTime hours (with frequently accessed items stored for longer periods),
+// but if we cannot do that, we fall-back to keep each list roughly the same
+// size so that we have a chance to see an element again and move it to another
+// list.
+
 #include "net/disk_cache/eviction.h"
 
 #include "base/logging.h"
@@ -17,6 +41,8 @@ using base::Time;
 namespace {
 
 const int kCleanUpMargin = 1024 * 1024;
+const int kHighUse = 10;  // Reuse count to be on the HIGH_USE list.
+const int kTargetTime = 24 * 7;  // Time to be evicted (hours since last use).
 
 int LowWaterAdjust(int high_water) {
   if (high_water < kCleanUpMargin)
@@ -36,9 +62,13 @@ void Eviction::Init(BackendImpl* backend) {
   rankings_ = &backend->rankings_;
   header_ = &backend_->data_->header;
   max_size_ = LowWaterAdjust(backend_->max_size_);
+  new_eviction_ = backend->new_eviction_;
 }
 
 void Eviction::TrimCache(bool empty) {
+  if (new_eviction_)
+    return TrimCacheV2(empty);
+
   Trace("*** Trim Cache ***");
   if (backend_->disabled_)
     return;
@@ -55,19 +85,9 @@ void Eviction::TrimCache(bool empty) {
     next.reset(rankings_->GetPrev(node.get(), Rankings::NO_USE));
     if (!node->Data()->pointer || empty) {
       // This entry is not being used by anybody.
-      EntryImpl* entry;
-      bool dirty;
-      if (backend_->NewEntry(Addr(node->Data()->contents), &entry, &dirty)) {
-        Trace("NewEntry failed on Trim 0x%x", node->address().value());
+      if (!EvictEntry(node.get(), empty))
         continue;
-      }
 
-      if (node->Data()->pointer) {
-        entry = EntryImpl::Update(entry);
-      }
-      ReportTrimTimes(entry);
-      entry->Doom();
-      entry->Release();
       if (!empty)
         backend_->OnEvent(Stats::TRIM_ENTRY);
       if (++deleted == 4 && !empty) {
@@ -86,21 +106,34 @@ void Eviction::TrimCache(bool empty) {
 }
 
 void Eviction::UpdateRank(EntryImpl* entry, bool modified) {
+  if (new_eviction_)
+    return UpdateRankV2(entry, modified);
+
   rankings_->UpdateRank(entry->rankings(), modified, GetListForEntry(entry));
 }
 
 void Eviction::OnOpenEntry(EntryImpl* entry) {
+  if (new_eviction_)
+    return OnOpenEntryV2(entry);
 }
 
 void Eviction::OnCreateEntry(EntryImpl* entry) {
+  if (new_eviction_)
+    return OnCreateEntryV2(entry);
+
   rankings_->Insert(entry->rankings(), true, GetListForEntry(entry));
 }
 
 void Eviction::OnDoomEntry(EntryImpl* entry) {
+  if (new_eviction_)
+    return OnDoomEntryV2(entry);
+
   rankings_->Remove(entry->rankings(), GetListForEntry(entry));
 }
 
 void Eviction::OnDestroyEntry(EntryImpl* entry) {
+  if (new_eviction_)
+    return OnDestroyEntryV2(entry);
 }
 
 void Eviction::ReportTrimTimes(EntryImpl* entry) {
@@ -119,4 +152,208 @@ Rankings::List Eviction::GetListForEntry(EntryImpl* entry) {
   return Rankings::NO_USE;
 }
 
+bool Eviction::EvictEntry(CacheRankingsBlock* node, bool empty) {
+  EntryImpl* entry;
+  bool dirty;
+  if (backend_->NewEntry(Addr(node->Data()->contents), &entry, &dirty)) {
+    Trace("NewEntry failed on Trim 0x%x", node->address().value());
+    return false;
+  }
+
+  if (node->Data()->pointer) {
+    entry = EntryImpl::Update(entry);
+  }
+  ReportTrimTimes(entry);
+  if (empty || !new_eviction_) {
+    entry->Doom();
+  } else {
+    entry->DeleteEntryData(false);
+    EntryStore* info = entry->entry()->Data();
+    DCHECK(ENTRY_NORMAL == info->state);
+
+    rankings_->Remove(entry->rankings(), GetListForEntryV2(entry));
+    info->state = ENTRY_EVICTED;
+    entry->entry()->Store();
+    rankings_->Insert(entry->rankings(), true, Rankings::DELETED);
+    backend_->OnEvent(Stats::TRIM_ENTRY);
+  }
+  entry->Release();
+
+  return true;
+}
+
+// -----------------------------------------------------------------------
+
+void Eviction::TrimCacheV2(bool empty) {
+  Trace("*** Trim Cache ***");
+  if (backend_->disabled_)
+    return;
+
+  Time start = Time::Now();
+
+  const int kListsToSearch = 3;
+  Rankings::ScopedRankingsBlock next[kListsToSearch];
+  int list = Rankings::LAST_ELEMENT;
+
+  // Get a node from each list.
+  for (int i = 0; i < kListsToSearch; i++) {
+    bool done = false;
+    next[i].set_rankings(rankings_);
+    if (done)
+      continue;
+    next[i].reset(rankings_->GetPrev(NULL, static_cast<Rankings::List>(i)));
+    if (!empty && NodeIsOldEnough(next[i].get(), i)) {
+      list = static_cast<Rankings::List>(i);
+      done = true;
+    }
+  }
+
+  // If we are not meeting the time targets lets move on to list length.
+  if (!empty && Rankings::LAST_ELEMENT == list)
+    list = SelectListByLenght();
+
+  if (empty)
+    list = 0;
+
+  Rankings::ScopedRankingsBlock node(rankings_);
+
+  int target_size = empty ? 0 : max_size_;
+  int deleted = 0;
+  for (; list < kListsToSearch; list++) {
+    while (header_->num_bytes > target_size && next[list].get()) {
+      node.reset(next[list].release());
+      next[list].reset(rankings_->GetPrev(node.get(),
+                                          static_cast<Rankings::List>(list)));
+      if (!node->Data()->pointer || empty) {
+        // This entry is not being used by anybody.
+        if (!EvictEntry(node.get(), empty))
+          continue;
+
+        if (++deleted == 4 && !empty) {
+          MessageLoop::current()->PostTask(FROM_HERE,
+              factory_.NewRunnableMethod(&Eviction::TrimCache, false));
+          break;
+        }
+      }
+    }
+    if (!empty)
+      list = kListsToSearch;
+  }
+
+  if (empty || header_->lru.sizes[Rankings::DELETED] > header_->num_entries / 4)
+    MessageLoop::current()->PostTask(FROM_HERE,
+        factory_.NewRunnableMethod(&Eviction::TrimDeleted, empty));
+
+  UMA_HISTOGRAM_TIMES("DiskCache.TotalTrimTime", Time::Now() - start);
+  Trace("*** Trim Cache end ***");
+  return;
+}
+
+void Eviction::UpdateRankV2(EntryImpl* entry, bool modified) {
+  rankings_->UpdateRank(entry->rankings(), modified, GetListForEntryV2(entry));
+}
+
+void Eviction::OnOpenEntryV2(EntryImpl* entry) {
+  EntryStore* info = entry->entry()->Data();
+  DCHECK(ENTRY_NORMAL == info->state);
+
+  if (info->reuse_count < kint32max) {
+    info->reuse_count++;
+    entry->entry()->set_modified();
+
+    // We may need to move this to a new list.
+    if (1 == info->reuse_count) {
+      rankings_->Remove(entry->rankings(), Rankings::NO_USE);
+      rankings_->Insert(entry->rankings(), false, Rankings::LOW_USE);
+      entry->entry()->Store();
+    } else if (kHighUse == info->reuse_count) {
+      rankings_->Remove(entry->rankings(), Rankings::LOW_USE);
+      rankings_->Insert(entry->rankings(), false, Rankings::HIGH_USE);
+      entry->entry()->Store();
+    }
+  }
+}
+
+void Eviction::OnCreateEntryV2(EntryImpl* entry) {
+  EntryStore* info = entry->entry()->Data();
+  switch (info->state) {
+    case ENTRY_NORMAL: {
+      DCHECK(!info->reuse_count);
+      DCHECK(!info->refetch_count);
+      break;
+    };
+    case ENTRY_EVICTED: {
+      if (info->refetch_count < kint32max)
+        info->refetch_count++;
+
+      if (info->refetch_count > kHighUse && info->reuse_count < kHighUse) {
+        info->reuse_count = kHighUse;
+      } else {
+        info->reuse_count++;
+      }
+      info->state = ENTRY_NORMAL;
+      entry->entry()->Store();
+      rankings_->Remove(entry->rankings(), Rankings::DELETED);
+      break;
+    };
+    default:
+      NOTREACHED();
+  }
+
+  rankings_->Insert(entry->rankings(), true, GetListForEntryV2(entry));
+}
+
+void Eviction::OnDoomEntryV2(EntryImpl* entry) {
+  EntryStore* info = entry->entry()->Data();
+  if (ENTRY_NORMAL != info->state)
+    return;
+
+  rankings_->Remove(entry->rankings(), GetListForEntryV2(entry));
+
+  info->state = ENTRY_DOOMED;
+  entry->entry()->Store();
+  rankings_->Insert(entry->rankings(), true, Rankings::DELETED);
+}
+
+void Eviction::OnDestroyEntryV2(EntryImpl* entry) {
+  rankings_->Remove(entry->rankings(), Rankings::DELETED);
+}
+
+Rankings::List Eviction::GetListForEntryV2(EntryImpl* entry) {
+  EntryStore* info = entry->entry()->Data();
+  DCHECK(ENTRY_NORMAL == info->state);
+
+  if (!info->reuse_count)
+    return Rankings::NO_USE;
+
+  if (info->reuse_count < kHighUse)
+    return Rankings::LOW_USE;
+
+  return Rankings::HIGH_USE;
+}
+
+void Eviction::TrimDeleted(bool empty) {
+}
+
+bool Eviction::NodeIsOldEnough(CacheRankingsBlock* node, int list) {
+  if (!node)
+    return false;
+
+  // If possible, we want to keep entries on each list at least kTargetTime
+  // hours. Each successive list on the enumeration has 2x the target time of
+  // the previous list.
+  Time used = Time::FromInternalValue(node->Data()->last_used);
+  int multiplier = 1 << list;
+  return (Time::Now() - used).InHours() > kTargetTime * multiplier;
+}
+
+int Eviction::SelectListByLenght() {
+  // Start by having each list to be roughly the same size.
+  if (header_->lru.sizes[0] > header_->num_entries / 4)
+    return 0;
+  if (header_->lru.sizes[1] > header_->num_entries / 4)
+    return 1;
+  return 2;
+}
+
 }  // namespace disk_cache
diff --git a/net/disk_cache/eviction.h b/net/disk_cache/eviction.h
index dd4e467..2496357 100644
--- a/net/disk_cache/eviction.h
+++ b/net/disk_cache/eviction.h
@@ -42,11 +42,28 @@ class Eviction {
  private:
   void ReportTrimTimes(EntryImpl* entry);
   Rankings::List GetListForEntry(EntryImpl* entry);
+  bool EvictEntry(CacheRankingsBlock* node, bool empty);
+
+  // We'll just keep for a while a separate set of methods that implement the
+  // new eviction algorithm. This code will replace the original methods when
+  // finished.
+  void TrimCacheV2(bool empty);
+  void UpdateRankV2(EntryImpl* entry, bool modified);
+  void OnOpenEntryV2(EntryImpl* entry);
+  void OnCreateEntryV2(EntryImpl* entry);
+  void OnDoomEntryV2(EntryImpl* entry);
+  void OnDestroyEntryV2(EntryImpl* entry);
+  Rankings::List GetListForEntryV2(EntryImpl* entry);
+  void TrimDeleted(bool empty);
+  
+  bool NodeIsOldEnough(CacheRankingsBlock* node, int list);
+  int SelectListByLenght();
 
   BackendImpl* backend_;
   Rankings* rankings_;
   IndexHeader* header_;
   int max_size_;
+  bool new_eviction_;
   ScopedRunnableMethodFactory<Eviction> factory_;
 
   DISALLOW_COPY_AND_ASSIGN(Eviction);
diff --git a/net/disk_cache/rankings.cc b/net/disk_cache/rankings.cc
index 01a7222..962563b 100644
--- a/net/disk_cache/rankings.cc
+++ b/net/disk_cache/rankings.cc
@@ -174,14 +174,14 @@ void GenerateCrash(CrashLocation location) {
 
 namespace disk_cache {
 
-bool Rankings::Init(BackendImpl* backend) {
+bool Rankings::Init(BackendImpl* backend, bool count_lists) {
   DCHECK(!init_);
   if (init_)
     return false;
 
   backend_ = backend;
-
   control_data_ = backend_->GetLruData();
+  count_lists_ = count_lists;
 
   ReadHeads();
   ReadTails();
@@ -281,6 +281,7 @@ void Rankings::Insert(CacheRankingsBlock* node, bool modified, List list) {
 
   // The last thing to do is move our head to point to a node already stored.
   WriteHead(list);
+  IncrementCounter(list);
   GenerateCrash(ON_INSERT_4);
 }
 
@@ -377,6 +378,7 @@ void Rankings::Remove(CacheRankingsBlock* node, List list) {
   prev.Store();
   GenerateCrash(ON_REMOVE_8);
   node->Store();
+  DecrementCounter(list);
   UpdateIterators(&next);
   UpdateIterators(&prev);
 }
@@ -747,4 +749,22 @@ void Rankings::UpdateIterators(CacheRankingsBlock* node) {
   }
 }
 
+void Rankings::IncrementCounter(List list) {
+  if (!count_lists_)
+    return;
+
+  DCHECK(control_data_->sizes[list] < kint32max);
+  if (control_data_->sizes[list] < kint32max)
+    control_data_->sizes[list]++;
+}
+
+void Rankings::DecrementCounter(List list) {
+  if (!count_lists_)
+    return;
+
+  DCHECK(control_data_->sizes[list] > 0);
+  if (control_data_->sizes[list] > 0)
+    control_data_->sizes[list]--;
+}
+
 }  // namespace disk_cache
diff --git a/net/disk_cache/rankings.h b/net/disk_cache/rankings.h
index d4c10afd..906a5b7 100644
--- a/net/disk_cache/rankings.h
+++ b/net/disk_cache/rankings.h
@@ -54,6 +54,7 @@ class Rankings {
     NO_USE = 0,   // List of entries that have not been reused.
     LOW_USE,      // List of entries with low reuse.
     HIGH_USE,     // List of entries with high reuse.
+    RESERVED,     // Reserved for future use.
     DELETED,      // List of recently deleted or doomed entries.
     LAST_ELEMENT
   };
@@ -63,6 +64,7 @@ class Rankings {
   // iterators that may go stale.
   class ScopedRankingsBlock : public scoped_ptr<CacheRankingsBlock> {
    public:
+    ScopedRankingsBlock() : rankings_(NULL) {}
     explicit ScopedRankingsBlock(Rankings* rankings) : rankings_(rankings) {}
     ScopedRankingsBlock(Rankings* rankings, CacheRankingsBlock* node)
         : scoped_ptr<CacheRankingsBlock>(node), rankings_(rankings) {}
@@ -71,6 +73,10 @@ class Rankings {
       rankings_->FreeRankingsBlock(get());
     }
 
+    void set_rankings(Rankings* rankings) {
+      rankings_ = rankings;
+    }
+
     // scoped_ptr::reset will delete the object.
     void reset(CacheRankingsBlock* p = NULL) {
       if (p != get())
@@ -83,10 +89,26 @@ class Rankings {
     DISALLOW_EVIL_CONSTRUCTORS(ScopedRankingsBlock);
   };
 
+  // If we have multiple lists, we have to iterate through all at the same time.
+  // This structure keeps track of where we are on the iteration.
+  struct Iterator {
+    List list;                     // Which entry was returned to the user.
+    CacheRankingsBlock* nodes[3];  // Nodes on the first three lists.
+    Rankings* my_rankings;
+    Iterator(Rankings* rankings) {
+      memset(this, 0, sizeof(Iterator));
+      my_rankings = rankings;
+    }
+    ~Iterator() {
+      for (int i = 0; i < 3; i++)
+        ScopedRankingsBlock(my_rankings, nodes[i]);
+    }
+  };
+
   Rankings() : init_(false) {}
   ~Rankings() {}
 
-  bool Init(BackendImpl* backend);
+  bool Init(BackendImpl* backend, bool count_lists);
 
   // Restores original state, leaving the object ready for initialization.
   void Reset();
@@ -155,7 +177,12 @@ class Rankings {
   // Updates the iterators whenever node is being changed.
   void UpdateIterators(CacheRankingsBlock* node);
 
+  // Keeps track of the number of entries on a list.
+  void IncrementCounter(List list);
+  void DecrementCounter(List list);
+
   bool init_;
+  bool count_lists_;
   Addr heads_[LAST_ELEMENT];
   Addr tails_[LAST_ELEMENT];
   BackendImpl* backend_;
diff --git a/net/disk_cache/stats.cc b/net/disk_cache/stats.cc
index a6733cb..6047c5c 100644
--- a/net/disk_cache/stats.cc
+++ b/net/disk_cache/stats.cc
@@ -40,6 +40,7 @@ static const char* kCounterNames[] = {
   "Open hit",
   "Create miss",
   "Create hit",
+  "Resurrect hit",
   "Create error",
   "Trim entry",
   "Doom entry",
diff --git a/net/disk_cache/stats.h b/net/disk_cache/stats.h
index a811e3f..6d8043e 100644
--- a/net/disk_cache/stats.h
+++ b/net/disk_cache/stats.h
@@ -28,6 +28,7 @@ class Stats {
     OPEN_HIT,
     CREATE_MISS,
     CREATE_HIT,
+    RESURRECT_HIT,
     CREATE_ERROR,
     TRIM_ENTRY,
     DOOM_ENTRY,