Disk cache: First implementation of TrimDeleted() and a few...

net/disk_cache/eviction.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.
 
 // 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
@@ skipping 191 matching lines @@
     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)
+  if (!empty && Rankings::LAST_ELEMENT == list) {
     list = SelectListByLenght();
+    // Make sure that frequently used items are kept for a minimum time.
+    if (Rankings::HIGH_USE == list &&
+        !NodeIsOldEnough(next[Rankings::HIGH_USE].get(), 0))

[Nicolas Sylvain, 2009/03/18 17:17:35]

the zero here, it should not be "list" ?

[rvargas (doing something else), 2009/03/18 17:32:13]

no 'cause NodeIsOldEnough(next[2], 2) was already tested to be false. What i
want to do is make sure that even if the target time is 4x, I'm not removing it
if it is less than 1x (without hard coding the value here). I'll improve the
comment before checking in.

+      list = 0;
+  }
 
   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)
+  if (empty) {
+    TrimDeleted(true);
+  } else if (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));
 }
 
@@ skipping 69 matching lines @@
 
   if (!info->reuse_count)
     return Rankings::NO_USE;
 
   if (info->reuse_count < kHighUse)
     return Rankings::LOW_USE;
 
   return Rankings::HIGH_USE;
 }
 
+// This is a minimal implementation that just discards the oldest nodes.
+// TODO(rvargas): Do something better here.
 void Eviction::TrimDeleted(bool empty) {
+  Trace("*** Trim Deleted ***");
+  if (backend_->disabled_)
+    return;
+
+  Time start = Time::Now();
+  Rankings::ScopedRankingsBlock node(rankings_);
+  Rankings::ScopedRankingsBlock next(rankings_,
+    rankings_->GetPrev(node.get(), Rankings::DELETED));
+  DCHECK(next.get());
+  for (int i = 0; (i < 4 || empty) && next.get(); i++) {
+    node.reset(next.release());
+    next.reset(rankings_->GetPrev(node.get(), Rankings::DELETED));
+    RemoveDeletedNode(node.get());
+  }
+
+  if (header_->lru.sizes[Rankings::DELETED] > header_->num_entries / 4)
+    MessageLoop::current()->PostTask(FROM_HERE,
+        factory_.NewRunnableMethod(&Eviction::TrimDeleted, false));
+
+  UMA_HISTOGRAM_TIMES("DiskCache.TotalTrimDeletedTime", Time::Now() - start);
+  Trace("*** Trim Deleted end ***");
+  return;
+}
+
+bool Eviction::RemoveDeletedNode(CacheRankingsBlock* node) {
+  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);
+  }
+  entry->entry()->Data()->state = ENTRY_DOOMED;
+  entry->Doom();
+  entry->Release();
+  return true;
 }
 
 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() {
+  int data_entries = header_->num_entries -
+                     header_->lru.sizes[Rankings::DELETED];
   // Start by having each list to be roughly the same size.
-  if (header_->lru.sizes[0] > header_->num_entries / 4)
+  if (header_->lru.sizes[0] > data_entries / 3)
     return 0;
-  if (header_->lru.sizes[1] > header_->num_entries / 4)
+  if (header_->lru.sizes[1] > data_entries / 3)
     return 1;
   return 2;
 }
 
 }  // namespace disk_cache