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, 28 insertions, 1 deletions

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_;