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

1 files changed, 248 insertions, 11 deletions

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