Disk cache: move eviction code to a separate file.

There should be no change in behavior with this CL.

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

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

8 files changed, 212 insertions, 87 deletions

diff --git a/net/build/net.vcproj b/net/build/net.vcproj
index ae6c956..c304043 100644
--- a/net/build/net.vcproj
+++ b/net/build/net.vcproj
@@ -905,6 +905,14 @@
 				>
 			</File>
 			<File
+				RelativePath="..\disk_cache\eviction.cc"
+				>
+			</File>
+			<File
+				RelativePath="..\disk_cache\eviction.h"
+				>
+			</File>
+			<File
 				RelativePath="..\disk_cache\file.h"
 				>
 			</File>
diff --git a/net/disk_cache/backend_impl.cc b/net/disk_cache/backend_impl.cc
index 23b0f9dc..710f8bd 100644
--- a/net/disk_cache/backend_impl.cc
+++ b/net/disk_cache/backend_impl.cc
@@ -23,7 +23,6 @@ using base::TimeDelta;
 namespace {
 
 const wchar_t* kIndexName = L"index";
-const int kCleanUpMargin = 1024 * 1024;
 const int kMaxOldFolders = 100;
 
 // Seems like ~240 MB correspond to less than 50k entries for 99% of the people.
@@ -54,13 +53,6 @@ size_t GetIndexSize(int table_len) {
   return sizeof(disk_cache::IndexHeader) + table_size;
 }
 
-int LowWaterAdjust(int high_water) {
-  if (high_water < kCleanUpMargin)
-    return 0;
-
-  return high_water - kCleanUpMargin;
-}
-
 // ------------------------------------------------------------------------
 
 // Returns a fully qualified name from path and name, using a given name prefix
@@ -248,6 +240,7 @@ bool BackendImpl::Init() {
     return false;
 
   disabled_ = !rankings_.Init(this);
+  eviction_.Init(this);
 
   return !disabled_;
 }
@@ -287,6 +280,7 @@ bool BackendImpl::OpenEntry(const std::string& key, Entry** entry) {
     return false;
   }
 
+  eviction_.OnOpenEntry(cache_entry);
   DCHECK(entry);
   *entry = cache_entry;
 
@@ -355,7 +349,7 @@ bool BackendImpl::CreateEntry(const std::string& key, Entry** entry) {
 
   data_->header.num_entries++;
   DCHECK(data_->header.num_entries > 0);
-  rankings_.Insert(cache_entry->rankings(), true, Rankings::NO_USE);
+  eviction_.OnCreateEntry(cache_entry);
   if (!parent.get())
     data_->table[hash & mask_] = entry_address.value();
 
@@ -394,7 +388,7 @@ bool BackendImpl::DoomAllEntries() {
     if (disabled_)
       return false;
 
-    TrimCache(true);
+    eviction_.TrimCache(true);
     stats_.OnEvent(Stats::DOOM_CACHE);
     return true;
   }
@@ -575,7 +569,7 @@ LruData* BackendImpl::GetLruData() {
 
 void BackendImpl::UpdateRank(EntryImpl* entry, bool modified) {
   if (!read_only_) {
-    rankings_.UpdateRank(entry->rankings(), modified, Rankings::NO_USE);
+    eviction_.UpdateRank(entry, modified);
   }
 }
 
@@ -604,8 +598,7 @@ void BackendImpl::InternalDoomEntry(EntryImpl* entry) {
 
   Trace("Doom entry 0x%p", entry);
 
-  rankings_.Remove(entry->rankings(), Rankings::NO_USE);
-
+  eviction_.OnDoomEntry(entry);
   entry->InternalDoom();
 
   if (parent_entry) {
@@ -1020,9 +1013,9 @@ void BackendImpl::DestroyInvalidEntry(Addr address, EntryImpl* entry) {
   LOG(WARNING) << "Destroying invalid entry.";
   Trace("Destroying invalid entry 0x%p", entry);
 
-  rankings_.Remove(entry->rankings(), Rankings::NO_USE);
   entry->SetPointerForInvalidEntry(GetCurrentEntryId());
 
+  eviction_.OnDoomEntry(entry);
   entry->InternalDoom();
 
   data_->header.num_entries--;
@@ -1030,71 +1023,12 @@ void BackendImpl::DestroyInvalidEntry(Addr address, EntryImpl* entry) {
   stats_.OnEvent(Stats::INVALID_ENTRY);
 }
 
-void BackendImpl::TrimCache(bool empty) {
-  Trace("*** Trim Cache ***");
-  if (disabled_)
-    return;
-
-  Time start = Time::Now();
-  Rankings::ScopedRankingsBlock node(&rankings_);
-  Rankings::ScopedRankingsBlock next(&rankings_,
-      rankings_.GetPrev(node.get(), Rankings::NO_USE));
-  DCHECK(next.get());
-  int target_size = empty ? 0 : LowWaterAdjust(max_size_);
-  int deleted = 0;
-  while (data_->header.num_bytes > target_size && next.get()) {
-    node.reset(next.release());
-    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 (NewEntry(Addr(node->Data()->contents), &entry, &dirty)) {
-        Trace("NewEntry failed on Trim 0x%x", node->address().value());
-        continue;
-      }
-
-      if (node->Data()->pointer) {
-        entry = EntryImpl::Update(entry);
-      }
-      ReportTrimTimes(entry);
-      entry->Doom();
-      entry->Release();
-      if (!empty)
-        stats_.OnEvent(Stats::TRIM_ENTRY);
-      if (++deleted == 4 && !empty) {
-#if defined(OS_WIN)
-        MessageLoop::current()->PostTask(FROM_HERE,
-            factory_.NewRunnableMethod(&BackendImpl::TrimCache, false));
-        break;
-#endif
-      }
-    }
-  }
-
-  UMA_HISTOGRAM_TIMES(L"DiskCache.TotalTrimTime", Time::Now() - start);
-  Trace("*** Trim Cache end ***");
-  return;
-}
-
-void BackendImpl::ReportTrimTimes(EntryImpl* entry) {
-  static bool first_time = true;
-  if (first_time) {
-    first_time = false;
-    std::wstring name(StringPrintf(L"DiskCache.TrimAge_%d",
-                                   data_->header.experiment));
-    static Histogram counter(name.c_str(), 1, 10000, 50);
-    counter.SetFlags(kUmaTargetedHistogramFlag);
-    counter.Add((Time::Now() - entry->GetLastUsed()).InHours());
-  }
-}
-
 void BackendImpl::AddStorageSize(int32 bytes) {
   data_->header.num_bytes += bytes;
   DCHECK(data_->header.num_bytes >= 0);
 
   if (data_->header.num_bytes > max_size_)
-    TrimCache(false);
+    eviction_.TrimCache(false);
 }
 
 void BackendImpl::SubstractStorageSize(int32 bytes) {
diff --git a/net/disk_cache/backend_impl.h b/net/disk_cache/backend_impl.h
index 4725fe3..89be795 100644
--- a/net/disk_cache/backend_impl.h
+++ b/net/disk_cache/backend_impl.h
@@ -7,10 +7,10 @@
 #ifndef NET_DISK_CACHE_BACKEND_IMPL_H__
 #define NET_DISK_CACHE_BACKEND_IMPL_H__
 
-#include "base/compiler_specific.h"
 #include "base/timer.h"
 #include "net/disk_cache/block_files.h"
 #include "net/disk_cache/disk_cache.h"
+#include "net/disk_cache/eviction.h"
 #include "net/disk_cache/rankings.h"
 #include "net/disk_cache/stats.h"
 #include "net/disk_cache/trace.h"
@@ -20,16 +20,15 @@ namespace disk_cache {
 // This class implements the Backend interface. An object of this
 // class handles the operations of the cache for a particular profile.
 class BackendImpl : public Backend {
+  friend class Eviction;
  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),
-        ALLOW_THIS_IN_INITIALIZER_LIST(factory_(this)) {}
+      : path_(path), block_files_(path), mask_(0), max_size_(0), init_(false),
+        restarted_(false), unit_test_(false), read_only_(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),
-        ALLOW_THIS_IN_INITIALIZER_LIST(factory_(this)) {}
+        init_(false), restarted_(false), unit_test_(false), read_only_(false) {}
   ~BackendImpl();
 
   // Performs general initialization for this current instance of the cache.
@@ -153,12 +152,6 @@ class BackendImpl : public Backend {
 
   void DestroyInvalidEntry(Addr address, EntryImpl* entry);
 
-  // Deletes entries from the cache until the current size is below the limit.
-  // If empty is true, the whole cache will be trimmed, regardless of being in
-  // use.
-  void TrimCache(bool empty);
-  void ReportTrimTimes(EntryImpl* entry);
-  
   // Handles the used storage count.
   void AddStorageSize(int32 bytes);
   void SubstractStorageSize(int32 bytes);
@@ -186,6 +179,7 @@ class BackendImpl : public Backend {
   Rankings rankings_;  // Rankings to be able to trim the cache.
   uint32 mask_;  // Binary mask to map a hash to the hash table.
   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 num_pending_io_;  // Number of pending IO operations;
@@ -198,7 +192,6 @@ class BackendImpl : public Backend {
   Stats stats_;  // Usage statistcs.
   base::RepeatingTimer<BackendImpl> timer_;  // Usage timer.
   TraceObject trace_object_;  // Inits and destroys internal tracing.
-  ScopedRunnableMethodFactory<BackendImpl> factory_;
 
   DISALLOW_EVIL_CONSTRUCTORS(BackendImpl);
 };
diff --git a/net/disk_cache/eviction.cc b/net/disk_cache/eviction.cc
new file mode 100644
index 0000000..11ff969
--- /dev/null
+++ b/net/disk_cache/eviction.cc
@@ -0,0 +1,122 @@
+// Copyright (c) 2006-2008 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 "net/disk_cache/eviction.h"
+
+#include "base/logging.h"
+#include "base/message_loop.h"
+#include "base/string_util.h"
+#include "base/time.h"
+#include "net/disk_cache/backend_impl.h"
+#include "net/disk_cache/entry_impl.h"
+#include "net/disk_cache/trace.h"
+
+using base::Time;
+
+namespace {
+
+const int kCleanUpMargin = 1024 * 1024;
+
+int LowWaterAdjust(int high_water) {
+  if (high_water < kCleanUpMargin)
+    return 0;
+
+  return high_water - kCleanUpMargin;
+}
+
+}  // namespace
+
+namespace disk_cache {
+
+void Eviction::Init(BackendImpl* backend) {
+  // We grab a bunch of info from the backend to make the code a little cleaner
+  // when we're actually doing work.
+  backend_ = backend;
+  rankings_ = &backend->rankings_;
+  header_ = &backend_->data_->header;
+  max_size_ = LowWaterAdjust(backend_->max_size_);
+}
+
+void Eviction::TrimCache(bool empty) {
+  Trace("*** Trim Cache ***");
+  if (backend_->disabled_)
+    return;
+
+  Time start = Time::Now();
+  Rankings::ScopedRankingsBlock node(rankings_);
+  Rankings::ScopedRankingsBlock next(rankings_,
+      rankings_->GetPrev(node.get(), Rankings::NO_USE));
+  DCHECK(next.get());
+  int target_size = empty ? 0 : max_size_;
+  int deleted = 0;
+  while (header_->num_bytes > target_size && next.get()) {
+    node.reset(next.release());
+    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());
+        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) {
+#if defined(OS_WIN)
+        MessageLoop::current()->PostTask(FROM_HERE,
+            factory_.NewRunnableMethod(&Eviction::TrimCache, false));
+        break;
+#endif
+      }
+    }
+  }
+
+  UMA_HISTOGRAM_TIMES(L"DiskCache.TotalTrimTime", Time::Now() - start);
+  Trace("*** Trim Cache end ***");
+  return;
+}
+
+void Eviction::UpdateRank(EntryImpl* entry, bool modified) {
+  rankings_->UpdateRank(entry->rankings(), modified, GetListForEntry(entry));
+}
+
+void Eviction::OnOpenEntry(EntryImpl* entry) {
+}
+
+void Eviction::OnCreateEntry(EntryImpl* entry) {
+  rankings_->Insert(entry->rankings(), true, GetListForEntry(entry));
+}
+
+void Eviction::OnDoomEntry(EntryImpl* entry) {
+  rankings_->Remove(entry->rankings(), GetListForEntry(entry));
+}
+
+void Eviction::OnDestroyEntry(EntryImpl* entry) {
+}
+
+void Eviction::ReportTrimTimes(EntryImpl* entry) {
+  static bool first_time = true;
+  if (first_time) {
+    first_time = false;
+    std::wstring name(StringPrintf(L"DiskCache.TrimAge_%d",
+                                   header_->experiment));
+    static Histogram counter(name.c_str(), 1, 10000, 50);
+    counter.SetFlags(kUmaTargetedHistogramFlag);
+    counter.Add((Time::Now() - entry->GetLastUsed()).InHours());
+  }
+}
+
+Rankings::List Eviction::GetListForEntry(EntryImpl* entry) {
+  return Rankings::NO_USE;
+}
+
+}  // namespace disk_cache
diff --git a/net/disk_cache/eviction.h b/net/disk_cache/eviction.h
new file mode 100644
index 0000000..dd4e467
--- /dev/null
+++ b/net/disk_cache/eviction.h
@@ -0,0 +1,57 @@
+// Copyright (c) 2006-2008 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 NET_DISK_CACHE_EVICTION_H_
+#define NET_DISK_CACHE_EVICTION_H_
+
+#include "base/basictypes.h"
+#include "base/compiler_specific.h"
+#include "base/task.h"
+#include "net/disk_cache/disk_format.h"
+#include "net/disk_cache/rankings.h"
+
+namespace disk_cache {
+
+class BackendImpl;
+class EntryImpl;
+
+// This class implements the eviction algorithm for the cache and it is tightly
+// integrated with BackendImpl.
+class Eviction {
+ public:
+  Eviction() : backend_(NULL), ALLOW_THIS_IN_INITIALIZER_LIST(factory_(this)) {}
+  ~Eviction() {}
+
+  void Init(BackendImpl* backend);
+
+  // Deletes entries from the cache until the current size is below the limit.
+  // If empty is true, the whole cache will be trimmed, regardless of being in
+  // use.
+  void TrimCache(bool empty);
+
+  // Updates the ranking information for an entry.
+  void UpdateRank(EntryImpl* entry, bool modified);
+
+  // Notifications of interesting events for a given entry.
+  void OnOpenEntry(EntryImpl* entry);
+  void OnCreateEntry(EntryImpl* entry);
+  void OnDoomEntry(EntryImpl* entry);
+  void OnDestroyEntry(EntryImpl* entry);
+
+ private:
+  void ReportTrimTimes(EntryImpl* entry);
+  Rankings::List GetListForEntry(EntryImpl* entry);
+
+  BackendImpl* backend_;
+  Rankings* rankings_;
+  IndexHeader* header_;
+  int max_size_;
+  ScopedRunnableMethodFactory<Eviction> factory_;
+
+  DISALLOW_COPY_AND_ASSIGN(Eviction);
+};
+
+}  // namespace disk_cache
+
+#endif  // NET_DISK_CACHE_EVICTION_H_
diff --git a/net/disk_cache/rankings.cc b/net/disk_cache/rankings.cc
index 286998e..e3ff489 100644
--- a/net/disk_cache/rankings.cc
+++ b/net/disk_cache/rankings.cc
@@ -495,6 +495,8 @@ CacheRankingsBlock* Rankings::GetNext(CacheRankingsBlock* node, List list) {
     if (my_tail.value() == node->address().value())
       return NULL;
     Addr address(node->Data()->next);
+    if (address.value() == node->address().value())
+      return NULL;  // Another tail? fail it.
     next.reset(new CacheRankingsBlock(backend_->File(address), address));
   }
 
@@ -523,6 +525,8 @@ CacheRankingsBlock* Rankings::GetPrev(CacheRankingsBlock* node, List list) {
     if (my_head.value() == node->address().value())
       return NULL;
     Addr address(node->Data()->prev);
+    if (address.value() == node->address().value())
+      return NULL;  // Another head? fail it.
     prev.reset(new CacheRankingsBlock(backend_->File(address), address));
   }
 
diff --git a/net/net.xcodeproj/project.pbxproj b/net/net.xcodeproj/project.pbxproj
index ee6a70c..8a85e0a 100644
--- a/net/net.xcodeproj/project.pbxproj
+++ b/net/net.xcodeproj/project.pbxproj
@@ -166,6 +166,7 @@
 		A5AB7BFC0EB7DBA10070A7D3 /* file_stream_unittest.cc in Sources */ = {isa = PBXBuildFile; fileRef = A5AB7BFB0EB7DBA10070A7D3 /* file_stream_unittest.cc */; };
 		B5F622260E805FC40076681A /* url_request_job_manager.cc in Sources */ = {isa = PBXBuildFile; fileRef = 7BED33A30E5A198600A747DB /* url_request_job_manager.cc */; };
 		BAA46E3B0E5CE99A00E77460 /* net_util_unittest.cc in Sources */ = {isa = PBXBuildFile; fileRef = 7BED329F0E5A181C00A747DB /* net_util_unittest.cc */; };
+		DFC96EFA0EF9BC5D003C335B /* eviction.cc in Sources */ = {isa = PBXBuildFile; fileRef = DFC96EF80EF9BC5D003C335B /* eviction.cc */; };
 		DFEE18270E882E3600666107 /* stats_histogram.cc in Sources */ = {isa = PBXBuildFile; fileRef = DFEE18250E882E3600666107 /* stats_histogram.cc */; };
 		E4005E3A0E9FA63B0055B38E /* url_request_file_job.cc in Sources */ = {isa = PBXBuildFile; fileRef = 7BED33B00E5A198600A747DB /* url_request_file_job.cc */; };
 		E45449720ECA0264000DFA6E /* url_request_filter.cc in Sources */ = {isa = PBXBuildFile; fileRef = 7BED33B90E5A198600A747DB /* url_request_filter.cc */; };
@@ -684,6 +685,8 @@
 		936882DC0E9154E200043405 /* file_stream.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = file_stream.h; sourceTree = "<group>"; };
 		93D11DCD0E91463000C36437 /* file_stream_posix.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = file_stream_posix.cc; sourceTree = "<group>"; };
 		A5AB7BFB0EB7DBA10070A7D3 /* file_stream_unittest.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = file_stream_unittest.cc; sourceTree = "<group>"; };
+		DFC96EF80EF9BC5D003C335B /* eviction.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = eviction.cc; sourceTree = "<group>"; };
+		DFC96EF90EF9BC5D003C335B /* eviction.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = eviction.h; sourceTree = "<group>"; };
 		DFEE18250E882E3600666107 /* stats_histogram.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = stats_histogram.cc; sourceTree = "<group>"; };
 		DFEE18260E882E3600666107 /* stats_histogram.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = stats_histogram.h; sourceTree = "<group>"; };
 		E47E933E0E8924DC00CA613E /* tcp_client_socket_libevent.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = tcp_client_socket_libevent.cc; sourceTree = "<group>"; };
@@ -1022,6 +1025,8 @@
 				7BED32F20E5A190600A747DB /* entry_impl.h */,
 				7BED32E40E5A190600A747DB /* entry_unittest.cc */,
 				7BED32E30E5A190600A747DB /* errors.h */,
+				DFC96EF80EF9BC5D003C335B /* eviction.cc */,
+				DFC96EF90EF9BC5D003C335B /* eviction.h */,
 				7BED32E20E5A190600A747DB /* file.h */,
 				7BED32E10E5A190600A747DB /* file_block.h */,
 				7BED32FF0E5A190600A747DB /* file_lock.cc */,
@@ -1474,6 +1479,7 @@
 				7B8504100E5B2DF000730B43 /* entry_impl.cc in Sources */,
 				7B8504120E5B2DF000730B43 /* escape.cc in Sources */,
 				825C2FCC0E5C968B00FDEAB7 /* ev_root_ca_metadata.cc in Sources */,
+				DFC96EFA0EF9BC5D003C335B /* eviction.cc in Sources */,
 				7B8504140E5B2DF000730B43 /* file_lock.cc in Sources */,
 				7B8504150E5B2DF000730B43 /* file_posix.cc in Sources */,
 				93D11DCE0E91463000C36437 /* file_stream_posix.cc in Sources */,
diff --git a/net/net_lib.scons b/net/net_lib.scons
index 61a8a10..4f96264 100644
--- a/net/net_lib.scons
+++ b/net/net_lib.scons
@@ -54,6 +54,7 @@ input_files = [
     'disk_cache/backend_impl.cc',
     'disk_cache/block_files.cc',
     'disk_cache/entry_impl.cc',
+    'disk_cache/eviction.cc',
     'disk_cache/file_lock.cc',
     'disk_cache/hash.cc',
     'disk_cache/mem_backend_impl.cc',