Home | History | Annotate | Download | only in disk_cache 
      1 // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 // The eviction policy is a very simple pure LRU, so the elements at the end of
      6 // the list are evicted until kCleanUpMargin free space is available. There is
      7 // only one list in use (Rankings::NO_USE), and elements are sent to the front
      8 // of the list whenever they are accessed.
      9 
     10 // The new (in-development) eviction policy ads re-use as a factor to evict
     11 // an entry. The story so far:
     12 
     13 // Entries are linked on separate lists depending on how often they are used.
     14 // When we see an element for the first time, it goes to the NO_USE list; if
     15 // the object is reused later on, we move it to the LOW_USE list, until it is
     16 // used kHighUse times, at which point it is moved to the HIGH_USE list.
     17 // Whenever an element is evicted, we move it to the DELETED list so that if the
     18 // element is accessed again, we remember the fact that it was already stored
     19 // and maybe in the future we don't evict that element.
     20 
     21 // When we have to evict an element, first we try to use the last element from
     22 // the NO_USE list, then we move to the LOW_USE and only then we evict an entry
     23 // from the HIGH_USE. We attempt to keep entries on the cache for at least
     24 // kTargetTime hours (with frequently accessed items stored for longer periods),
     25 // but if we cannot do that, we fall-back to keep each list roughly the same
     26 // size so that we have a chance to see an element again and move it to another
     27 // list.
     28 
     29 #include "net/disk_cache/eviction.h"
     30 
     31 #include "base/logging.h"
     32 #include "base/message_loop.h"
     33 #include "base/string_util.h"
     34 #include "base/time.h"
     35 #include "net/disk_cache/backend_impl.h"
     36 #include "net/disk_cache/entry_impl.h"
     37 #include "net/disk_cache/histogram_macros.h"
     38 #include "net/disk_cache/trace.h"
     39 
     40 using base::Time;
     41 
     42 namespace {
     43 
     44 const int kCleanUpMargin = 1024 * 1024;
     45 const int kHighUse = 10;  // Reuse count to be on the HIGH_USE list.
     46 const int kTargetTime = 24 * 7;  // Time to be evicted (hours since last use).
     47 
     48 int LowWaterAdjust(int high_water) {
     49   if (high_water < kCleanUpMargin)
     50     return 0;
     51 
     52   return high_water - kCleanUpMargin;
     53 }
     54 
     55 }  // namespace
     56 
     57 namespace disk_cache {
     58 
     59 void Eviction::Init(BackendImpl* backend) {
     60   // We grab a bunch of info from the backend to make the code a little cleaner
     61   // when we're actually doing work.
     62   backend_ = backend;
     63   rankings_ = &backend->rankings_;
     64   header_ = &backend_->data_->header;
     65   max_size_ = LowWaterAdjust(backend_->max_size_);
     66   new_eviction_ = backend->new_eviction_;
     67   first_trim_ = true;
     68   trimming_ = false;
     69   delay_trim_ = false;
     70 }
     71 
     72 void Eviction::TrimCache(bool empty) {
     73   if (new_eviction_)
     74     return TrimCacheV2(empty);
     75 
     76   if (backend_->disabled_ || trimming_)
     77     return;
     78 
     79   if (!empty && backend_->IsLoaded())
     80     return PostDelayedTrim();
     81 
     82   Trace("*** Trim Cache ***");
     83   trimming_ = true;
     84   Time start = Time::Now();
     85   Rankings::ScopedRankingsBlock node(rankings_);
     86   Rankings::ScopedRankingsBlock next(rankings_,
     87       rankings_->GetPrev(node.get(), Rankings::NO_USE));
     88   int target_size = empty ? 0 : max_size_;
     89   while (header_->num_bytes > target_size && next.get()) {
     90     // The iterator could be invalidated within EvictEntry().
     91     if (!next->HasData())
     92       break;
     93     node.reset(next.release());
     94     next.reset(rankings_->GetPrev(node.get(), Rankings::NO_USE));
     95     if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) {
     96       // This entry is not being used by anybody.
     97       // Do NOT use node as an iterator after this point.
     98       rankings_->TrackRankingsBlock(node.get(), false);
     99       if (!EvictEntry(node.get(), empty))
    100         continue;
    101 
    102       if (!empty) {
    103         backend_->OnEvent(Stats::TRIM_ENTRY);
    104 
    105         if ((Time::Now() - start).InMilliseconds() > 20) {
    106           MessageLoop::current()->PostTask(FROM_HERE,
    107               factory_.NewRunnableMethod(&Eviction::TrimCache, false));
    108           break;
    109         }
    110       }
    111     }
    112   }
    113 
    114   CACHE_UMA(AGE_MS, "TotalTrimTime", backend_->GetSizeGroup(), start);
    115   trimming_ = false;
    116   Trace("*** Trim Cache end ***");
    117   return;
    118 }
    119 
    120 void Eviction::UpdateRank(EntryImpl* entry, bool modified) {
    121   if (new_eviction_)
    122     return UpdateRankV2(entry, modified);
    123 
    124   rankings_->UpdateRank(entry->rankings(), modified, GetListForEntry(entry));
    125 }
    126 
    127 void Eviction::OnOpenEntry(EntryImpl* entry) {
    128   if (new_eviction_)
    129     return OnOpenEntryV2(entry);
    130 }
    131 
    132 void Eviction::OnCreateEntry(EntryImpl* entry) {
    133   if (new_eviction_)
    134     return OnCreateEntryV2(entry);
    135 
    136   rankings_->Insert(entry->rankings(), true, GetListForEntry(entry));
    137 }
    138 
    139 void Eviction::OnDoomEntry(EntryImpl* entry) {
    140   if (new_eviction_)
    141     return OnDoomEntryV2(entry);
    142 
    143   rankings_->Remove(entry->rankings(), GetListForEntry(entry));
    144 }
    145 
    146 void Eviction::OnDestroyEntry(EntryImpl* entry) {
    147   if (new_eviction_)
    148     return OnDestroyEntryV2(entry);
    149 }
    150 
    151 void Eviction::PostDelayedTrim() {
    152   // Prevent posting multiple tasks.
    153   if (delay_trim_)
    154     return;
    155   delay_trim_ = true;
    156   MessageLoop::current()->PostDelayedTask(FROM_HERE,
    157       factory_.NewRunnableMethod(&Eviction::DelayedTrim), 1000);
    158 }
    159 
    160 void Eviction::DelayedTrim() {
    161   delay_trim_ = false;
    162   TrimCache(false);
    163 }
    164 
    165 void Eviction::ReportTrimTimes(EntryImpl* entry) {
    166   if (first_trim_) {
    167     first_trim_ = false;
    168     if (backend_->ShouldReportAgain()) {
    169       CACHE_UMA(AGE, "TrimAge", 0, entry->GetLastUsed());
    170       ReportListStats();
    171     }
    172 
    173     if (header_->lru.filled)
    174       return;
    175 
    176     header_->lru.filled = 1;
    177 
    178     if (header_->create_time) {
    179       // This is the first entry that we have to evict, generate some noise.
    180       backend_->FirstEviction();
    181     } else {
    182       // This is an old file, but we may want more reports from this user so
    183       // lets save some create_time.
    184       Time::Exploded old = {0};
    185       old.year = 2009;
    186       old.month = 3;
    187       old.day_of_month = 1;
    188       header_->create_time = Time::FromLocalExploded(old).ToInternalValue();
    189     }
    190   }
    191 }
    192 
    193 Rankings::List Eviction::GetListForEntry(EntryImpl* entry) {
    194   return Rankings::NO_USE;
    195 }
    196 
    197 bool Eviction::EvictEntry(CacheRankingsBlock* node, bool empty) {
    198   EntryImpl* entry = backend_->GetEnumeratedEntry(node, true);
    199   if (!entry) {
    200     Trace("NewEntry failed on Trim 0x%x", node->address().value());
    201     return false;
    202   }
    203 
    204   ReportTrimTimes(entry);
    205   if (empty || !new_eviction_) {
    206     entry->Doom();
    207   } else {
    208     entry->DeleteEntryData(false);
    209     EntryStore* info = entry->entry()->Data();
    210     DCHECK(ENTRY_NORMAL == info->state);
    211 
    212     rankings_->Remove(entry->rankings(), GetListForEntryV2(entry));
    213     info->state = ENTRY_EVICTED;
    214     entry->entry()->Store();
    215     rankings_->Insert(entry->rankings(), true, Rankings::DELETED);
    216     backend_->OnEvent(Stats::TRIM_ENTRY);
    217   }
    218   entry->Release();
    219 
    220   return true;
    221 }
    222 
    223 // -----------------------------------------------------------------------
    224 
    225 void Eviction::TrimCacheV2(bool empty) {
    226   if (backend_->disabled_ || trimming_)
    227     return;
    228 
    229   if (!empty && backend_->IsLoaded())
    230     return PostDelayedTrim();
    231 
    232   Trace("*** Trim Cache ***");
    233   trimming_ = true;
    234   Time start = Time::Now();
    235 
    236   const int kListsToSearch = 3;
    237   Rankings::ScopedRankingsBlock next[kListsToSearch];
    238   int list = Rankings::LAST_ELEMENT;
    239 
    240   // Get a node from each list.
    241   for (int i = 0; i < kListsToSearch; i++) {
    242     bool done = false;
    243     next[i].set_rankings(rankings_);
    244     if (done)
    245       continue;
    246     next[i].reset(rankings_->GetPrev(NULL, static_cast<Rankings::List>(i)));
    247     if (!empty && NodeIsOldEnough(next[i].get(), i)) {
    248       list = static_cast<Rankings::List>(i);
    249       done = true;
    250     }
    251   }
    252 
    253   // If we are not meeting the time targets lets move on to list length.
    254   if (!empty && Rankings::LAST_ELEMENT == list) {
    255     list = SelectListByLenght();
    256     // Make sure that frequently used items are kept for a minimum time; we know
    257     // that this entry is not older than its current target, but it must be at
    258     // least older than the target for list 0 (kTargetTime).
    259     if ((Rankings::HIGH_USE == list || Rankings::LOW_USE == list) &&
    260         !NodeIsOldEnough(next[list].get(), 0))
    261       list = 0;
    262   }
    263 
    264   if (empty)
    265     list = 0;
    266 
    267   Rankings::ScopedRankingsBlock node(rankings_);
    268 
    269   int target_size = empty ? 0 : max_size_;
    270   for (; list < kListsToSearch; list++) {
    271     while (header_->num_bytes > target_size && next[list].get()) {
    272       // The iterator could be invalidated within EvictEntry().
    273       if (!next[list]->HasData())
    274         break;
    275       node.reset(next[list].release());
    276       next[list].reset(rankings_->GetPrev(node.get(),
    277                                           static_cast<Rankings::List>(list)));
    278       if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) {
    279         // This entry is not being used by anybody.
    280         // Do NOT use node as an iterator after this point.
    281         rankings_->TrackRankingsBlock(node.get(), false);
    282         if (!EvictEntry(node.get(), empty))
    283           continue;
    284 
    285         if (!empty && (Time::Now() - start).InMilliseconds() > 20) {
    286           MessageLoop::current()->PostTask(FROM_HERE,
    287               factory_.NewRunnableMethod(&Eviction::TrimCache, false));
    288           break;
    289         }
    290       }
    291     }
    292     if (!empty)
    293       list = kListsToSearch;
    294   }
    295 
    296   if (empty) {
    297     TrimDeleted(true);
    298   } else if (header_->lru.sizes[Rankings::DELETED] > header_->num_entries / 4) {
    299     MessageLoop::current()->PostTask(FROM_HERE,
    300         factory_.NewRunnableMethod(&Eviction::TrimDeleted, empty));
    301   }
    302 
    303   CACHE_UMA(AGE_MS, "TotalTrimTime", backend_->GetSizeGroup(), start);
    304   Trace("*** Trim Cache end ***");
    305   trimming_ = false;
    306   return;
    307 }
    308 
    309 void Eviction::UpdateRankV2(EntryImpl* entry, bool modified) {
    310   rankings_->UpdateRank(entry->rankings(), modified, GetListForEntryV2(entry));
    311 }
    312 
    313 void Eviction::OnOpenEntryV2(EntryImpl* entry) {
    314   EntryStore* info = entry->entry()->Data();
    315   DCHECK(ENTRY_NORMAL == info->state);
    316 
    317   if (info->reuse_count < kint32max) {
    318     info->reuse_count++;
    319     entry->entry()->set_modified();
    320 
    321     // We may need to move this to a new list.
    322     if (1 == info->reuse_count) {
    323       rankings_->Remove(entry->rankings(), Rankings::NO_USE);
    324       rankings_->Insert(entry->rankings(), false, Rankings::LOW_USE);
    325       entry->entry()->Store();
    326     } else if (kHighUse == info->reuse_count) {
    327       rankings_->Remove(entry->rankings(), Rankings::LOW_USE);
    328       rankings_->Insert(entry->rankings(), false, Rankings::HIGH_USE);
    329       entry->entry()->Store();
    330     }
    331   }
    332 }
    333 
    334 void Eviction::OnCreateEntryV2(EntryImpl* entry) {
    335   EntryStore* info = entry->entry()->Data();
    336   switch (info->state) {
    337     case ENTRY_NORMAL: {
    338       DCHECK(!info->reuse_count);
    339       DCHECK(!info->refetch_count);
    340       break;
    341     };
    342     case ENTRY_EVICTED: {
    343       if (info->refetch_count < kint32max)
    344         info->refetch_count++;
    345 
    346       if (info->refetch_count > kHighUse && info->reuse_count < kHighUse) {
    347         info->reuse_count = kHighUse;
    348       } else {
    349         info->reuse_count++;
    350       }
    351       info->state = ENTRY_NORMAL;
    352       entry->entry()->Store();
    353       rankings_->Remove(entry->rankings(), Rankings::DELETED);
    354       break;
    355     };
    356     default:
    357       NOTREACHED();
    358   }
    359 
    360   rankings_->Insert(entry->rankings(), true, GetListForEntryV2(entry));
    361 }
    362 
    363 void Eviction::OnDoomEntryV2(EntryImpl* entry) {
    364   EntryStore* info = entry->entry()->Data();
    365   if (ENTRY_NORMAL != info->state)
    366     return;
    367 
    368   rankings_->Remove(entry->rankings(), GetListForEntryV2(entry));
    369 
    370   info->state = ENTRY_DOOMED;
    371   entry->entry()->Store();
    372   rankings_->Insert(entry->rankings(), true, Rankings::DELETED);
    373 }
    374 
    375 void Eviction::OnDestroyEntryV2(EntryImpl* entry) {
    376   rankings_->Remove(entry->rankings(), Rankings::DELETED);
    377 }
    378 
    379 Rankings::List Eviction::GetListForEntryV2(EntryImpl* entry) {
    380   EntryStore* info = entry->entry()->Data();
    381   DCHECK(ENTRY_NORMAL == info->state);
    382 
    383   if (!info->reuse_count)
    384     return Rankings::NO_USE;
    385 
    386   if (info->reuse_count < kHighUse)
    387     return Rankings::LOW_USE;
    388 
    389   return Rankings::HIGH_USE;
    390 }
    391 
    392 // This is a minimal implementation that just discards the oldest nodes.
    393 // TODO(rvargas): Do something better here.
    394 void Eviction::TrimDeleted(bool empty) {
    395   Trace("*** Trim Deleted ***");
    396   if (backend_->disabled_)
    397     return;
    398 
    399   Time start = Time::Now();
    400   Rankings::ScopedRankingsBlock node(rankings_);
    401   Rankings::ScopedRankingsBlock next(rankings_,
    402     rankings_->GetPrev(node.get(), Rankings::DELETED));
    403   for (int i = 0; (i < 4 || empty) && next.get(); i++) {
    404     node.reset(next.release());
    405     next.reset(rankings_->GetPrev(node.get(), Rankings::DELETED));
    406     RemoveDeletedNode(node.get());
    407   }
    408 
    409   if (header_->lru.sizes[Rankings::DELETED] > header_->num_entries / 4)
    410     MessageLoop::current()->PostTask(FROM_HERE,
    411         factory_.NewRunnableMethod(&Eviction::TrimDeleted, false));
    412 
    413   CACHE_UMA(AGE_MS, "TotalTrimDeletedTime", 0, start);
    414   Trace("*** Trim Deleted end ***");
    415   return;
    416 }
    417 
    418 bool Eviction::RemoveDeletedNode(CacheRankingsBlock* node) {
    419   EntryImpl* entry;
    420   bool dirty;
    421   if (backend_->NewEntry(Addr(node->Data()->contents), &entry, &dirty)) {
    422     Trace("NewEntry failed on Trim 0x%x", node->address().value());
    423     return false;
    424   }
    425 
    426   // TODO(rvargas): figure out how to deal with corruption at this point (dirty
    427   // entries that live in this list).
    428   if (node->Data()->dirty) {
    429     // We ignore the failure; we're removing the entry anyway.
    430     entry->Update();
    431   }
    432   entry->entry()->Data()->state = ENTRY_DOOMED;
    433   entry->Doom();
    434   entry->Release();
    435   return true;
    436 }
    437 
    438 bool Eviction::NodeIsOldEnough(CacheRankingsBlock* node, int list) {
    439   if (!node)
    440     return false;
    441 
    442   // If possible, we want to keep entries on each list at least kTargetTime
    443   // hours. Each successive list on the enumeration has 2x the target time of
    444   // the previous list.
    445   Time used = Time::FromInternalValue(node->Data()->last_used);
    446   int multiplier = 1 << list;
    447   return (Time::Now() - used).InHours() > kTargetTime * multiplier;
    448 }
    449 
    450 int Eviction::SelectListByLenght() {
    451   int data_entries = header_->num_entries -
    452                      header_->lru.sizes[Rankings::DELETED];
    453   // Start by having each list to be roughly the same size.
    454   if (header_->lru.sizes[0] > data_entries / 3)
    455     return 0;
    456   if (header_->lru.sizes[1] > data_entries / 3)
    457     return 1;
    458   return 2;
    459 }
    460 
    461 void Eviction::ReportListStats() {
    462   if (!new_eviction_)
    463     return;
    464 
    465   Rankings::ScopedRankingsBlock last1(rankings_,
    466       rankings_->GetPrev(NULL, Rankings::NO_USE));
    467   Rankings::ScopedRankingsBlock last2(rankings_,
    468       rankings_->GetPrev(NULL, Rankings::LOW_USE));
    469   Rankings::ScopedRankingsBlock last3(rankings_,
    470       rankings_->GetPrev(NULL, Rankings::HIGH_USE));
    471   Rankings::ScopedRankingsBlock last4(rankings_,
    472       rankings_->GetPrev(NULL, Rankings::DELETED));
    473 
    474   if (last1.get())
    475     CACHE_UMA(AGE, "NoUseAge", 0,
    476               Time::FromInternalValue(last1.get()->Data()->last_used));
    477   if (last2.get())
    478     CACHE_UMA(AGE, "LowUseAge", 0,
    479               Time::FromInternalValue(last2.get()->Data()->last_used));
    480   if (last3.get())
    481     CACHE_UMA(AGE, "HighUseAge", 0,
    482               Time::FromInternalValue(last3.get()->Data()->last_used));
    483   if (last4.get())
    484     CACHE_UMA(AGE, "DeletedAge", 0,
    485               Time::FromInternalValue(last4.get()->Data()->last_used));
    486 }
    487 
    488 }  // namespace disk_cache
    489