New disk cache eviction algorithm.

net/disk_cache/rankings.cc

 // 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/rankings.h"
 
 #include "base/histogram.h"
 #include "net/disk_cache/backend_impl.h"
 #include "net/disk_cache/entry_impl.h"
 #include "net/disk_cache/errors.h"
@@ skipping 156 matching lines @@
       NOTREACHED();
       return;
   }
 #endif  // NDEBUG
 }
 
 }  // namespace
 
 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();
 
   if (control_data_->transaction)
     CompleteTransaction();
 
   init_ = true;
   return true;
 }
@@ skipping 79 matching lines @@
 
   Time now = Time::Now();
   node->Data()->last_used = now.ToInternalValue();
   if (modified)
     node->Data()->last_modified = now.ToInternalValue();
   node->Store();
   GenerateCrash(ON_INSERT_3);
 
   // The last thing to do is move our head to point to a node already stored.
   WriteHead(list);
+  IncrementCounter(list);
   GenerateCrash(ON_INSERT_4);
 }
 
 // If a, b and r are elements on the list, and we want to remove r, the possible
 // states for the objects if a crash happens are (where y(x, z) means for object
 // y, prev is x and next is z):
 // A. One element:
 //    1. r(r, r), head(r), tail(r)                    initial state
 //    2. r(r, r), head(0), tail(r)                    WriteHead()
 //    3. r(r, r), head(0), tail(0)                    WriteTail()
@@ skipping 76 matching lines @@
   node->Data()->next = 0;
   node->Data()->prev = 0;
 
   // The last thing to get to disk is the node itself, so before that there is
   // enough info to recover.
   next.Store();
   GenerateCrash(ON_REMOVE_7);
   prev.Store();
   GenerateCrash(ON_REMOVE_8);
   node->Store();
+  DecrementCounter(list);
   UpdateIterators(&next);
   UpdateIterators(&prev);
 }
 
 // A crash in between Remove and Insert will lead to a dirty entry not on the
 // list. We want to avoid that case as much as we can (as while waiting for IO),
 // but the net effect is just an assert on debug when attempting to remove the
 // entry. Otherwise we'll need reentrant transactions, which is an overkill.
 void Rankings::UpdateRank(CacheRankingsBlock* node, bool modified, List list) {
   Time start = Time::Now();
@@ skipping 350 matching lines @@
   for (IteratorList::iterator it = iterators_.begin(); it != iterators_.end();
        ++it) {
     if (it->first == address) {
       CacheRankingsBlock* other = it->second;
       other->Data()->next = node->Data()->next;
       other->Data()->prev = node->Data()->prev;
     }
   }
 }
 
+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