Home | History | Annotate | Download | only in disk_cache 
      1 // Copyright (c) 2012 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 adds 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/bind.h"
     32 #include "base/compiler_specific.h"
     33 #include "base/logging.h"
     34 #include "base/message_loop/message_loop.h"
     35 #include "base/strings/string_util.h"
     36 #include "base/time/time.h"
     37 #include "net/disk_cache/backend_impl.h"
     38 #include "net/disk_cache/disk_format.h"
     39 #include "net/disk_cache/entry_impl.h"
     40 #include "net/disk_cache/experiments.h"
     41 #include "net/disk_cache/histogram_macros.h"
     42 #include "net/disk_cache/trace.h"
     43 
     44 using base::Time;
     45 using base::TimeTicks;
     46 
     47 namespace {
     48 
     49 const int kCleanUpMargin = 1024 * 1024;
     50 const int kHighUse = 10;  // Reuse count to be on the HIGH_USE list.
     51 const int kTargetTime = 24 * 7;  // Time to be evicted (hours since last use).
     52 const int kMaxDelayedTrims = 60;
     53 
     54 int LowWaterAdjust(int high_water) {
     55   if (high_water < kCleanUpMargin)
     56     return 0;
     57 
     58   return high_water - kCleanUpMargin;
     59 }
     60 
     61 bool FallingBehind(int current_size, int max_size) {
     62   return current_size > max_size - kCleanUpMargin * 20;
     63 }
     64 
     65 }  // namespace
     66 
     67 namespace disk_cache {
     68 
     69 // The real initialization happens during Init(), init_ is the only member that
     70 // has to be initialized here.
     71 Eviction::Eviction()
     72     : backend_(NULL),
     73       init_(false),
     74       ptr_factory_(this) {
     75 }
     76 
     77 Eviction::~Eviction() {
     78 }
     79 
     80 void Eviction::Init(BackendImpl* backend) {
     81   // We grab a bunch of info from the backend to make the code a little cleaner
     82   // when we're actually doing work.
     83   backend_ = backend;
     84   rankings_ = &backend->rankings_;
     85   header_ = &backend_->data_->header;
     86   max_size_ = LowWaterAdjust(backend_->max_size_);
     87   index_size_ = backend->mask_ + 1;
     88   new_eviction_ = backend->new_eviction_;
     89   first_trim_ = true;
     90   trimming_ = false;
     91   delay_trim_ = false;
     92   trim_delays_ = 0;
     93   init_ = true;
     94   test_mode_ = false;
     95 }
     96 
     97 void Eviction::Stop() {
     98   // It is possible for the backend initialization to fail, in which case this
     99   // object was never initialized... and there is nothing to do.
    100   if (!init_)
    101     return;
    102 
    103   // We want to stop further evictions, so let's pretend that we are busy from
    104   // this point on.
    105   DCHECK(!trimming_);
    106   trimming_ = true;
    107   ptr_factory_.InvalidateWeakPtrs();
    108 }
    109 
    110 void Eviction::TrimCache(bool empty) {
    111   if (backend_->disabled_ || trimming_)
    112     return;
    113 
    114   if (!empty && !ShouldTrim())
    115     return PostDelayedTrim();
    116 
    117   if (new_eviction_)
    118     return TrimCacheV2(empty);
    119 
    120   Trace("*** Trim Cache ***");
    121   trimming_ = true;
    122   TimeTicks start = TimeTicks::Now();
    123   Rankings::ScopedRankingsBlock node(rankings_);
    124   Rankings::ScopedRankingsBlock next(
    125       rankings_, rankings_->GetPrev(node.get(), Rankings::NO_USE));
    126   int deleted_entries = 0;
    127   int target_size = empty ? 0 : max_size_;
    128   while ((header_->num_bytes > target_size || test_mode_) && next.get()) {
    129     // The iterator could be invalidated within EvictEntry().
    130     if (!next->HasData())
    131       break;
    132     node.reset(next.release());
    133     next.reset(rankings_->GetPrev(node.get(), Rankings::NO_USE));
    134     if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) {
    135       // This entry is not being used by anybody.
    136       // Do NOT use node as an iterator after this point.
    137       rankings_->TrackRankingsBlock(node.get(), false);
    138       if (EvictEntry(node.get(), empty, Rankings::NO_USE) && !test_mode_)
    139         deleted_entries++;
    140 
    141       if (!empty && test_mode_)
    142         break;
    143     }
    144     if (!empty && (deleted_entries > 20 ||
    145                    (TimeTicks::Now() - start).InMilliseconds() > 20)) {
    146       base::MessageLoop::current()->PostTask(
    147           FROM_HERE,
    148           base::Bind(&Eviction::TrimCache, ptr_factory_.GetWeakPtr(), false));
    149       break;
    150     }
    151   }
    152 
    153   if (empty) {
    154     CACHE_UMA(AGE_MS, "TotalClearTimeV1", 0, start);
    155   } else {
    156     CACHE_UMA(AGE_MS, "TotalTrimTimeV1", 0, start);
    157   }
    158   CACHE_UMA(COUNTS, "TrimItemsV1", 0, deleted_entries);
    159 
    160   trimming_ = false;
    161   Trace("*** Trim Cache end ***");
    162   return;
    163 }
    164 
    165 void Eviction::UpdateRank(EntryImpl* entry, bool modified) {
    166   if (new_eviction_)
    167     return UpdateRankV2(entry, modified);
    168 
    169   rankings_->UpdateRank(entry->rankings(), modified, GetListForEntry(entry));
    170 }
    171 
    172 void Eviction::OnOpenEntry(EntryImpl* entry) {
    173   if (new_eviction_)
    174     return OnOpenEntryV2(entry);
    175 }
    176 
    177 void Eviction::OnCreateEntry(EntryImpl* entry) {
    178   if (new_eviction_)
    179     return OnCreateEntryV2(entry);
    180 
    181   rankings_->Insert(entry->rankings(), true, GetListForEntry(entry));
    182 }
    183 
    184 void Eviction::OnDoomEntry(EntryImpl* entry) {
    185   if (new_eviction_)
    186     return OnDoomEntryV2(entry);
    187 
    188   if (entry->LeaveRankingsBehind())
    189     return;
    190 
    191   rankings_->Remove(entry->rankings(), GetListForEntry(entry), true);
    192 }
    193 
    194 void Eviction::OnDestroyEntry(EntryImpl* entry) {
    195   if (new_eviction_)
    196     return OnDestroyEntryV2(entry);
    197 }
    198 
    199 void Eviction::SetTestMode() {
    200   test_mode_ = true;
    201 }
    202 
    203 void Eviction::TrimDeletedList(bool empty) {
    204   DCHECK(test_mode_ && new_eviction_);
    205   TrimDeleted(empty);
    206 }
    207 
    208 void Eviction::PostDelayedTrim() {
    209   // Prevent posting multiple tasks.
    210   if (delay_trim_)
    211     return;
    212   delay_trim_ = true;
    213   trim_delays_++;
    214   base::MessageLoop::current()->PostDelayedTask(
    215       FROM_HERE,
    216       base::Bind(&Eviction::DelayedTrim, ptr_factory_.GetWeakPtr()),
    217       base::TimeDelta::FromMilliseconds(1000));
    218 }
    219 
    220 void Eviction::DelayedTrim() {
    221   delay_trim_ = false;
    222   if (trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded())
    223     return PostDelayedTrim();
    224 
    225   TrimCache(false);
    226 }
    227 
    228 bool Eviction::ShouldTrim() {
    229   if (!FallingBehind(header_->num_bytes, max_size_) &&
    230       trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded()) {
    231     return false;
    232   }
    233 
    234   UMA_HISTOGRAM_COUNTS("DiskCache.TrimDelays", trim_delays_);
    235   trim_delays_ = 0;
    236   return true;
    237 }
    238 
    239 bool Eviction::ShouldTrimDeleted() {
    240   int index_load = header_->num_entries * 100 / index_size_;
    241 
    242   // If the index is not loaded, the deleted list will tend to double the size
    243   // of the other lists 3 lists (40% of the total). Otherwise, all lists will be
    244   // about the same size.
    245   int max_length = (index_load < 25) ? header_->num_entries * 2 / 5 :
    246                                        header_->num_entries / 4;
    247   return (!test_mode_ && header_->lru.sizes[Rankings::DELETED] > max_length);
    248 }
    249 
    250 void Eviction::ReportTrimTimes(EntryImpl* entry) {
    251   if (first_trim_) {
    252     first_trim_ = false;
    253     if (backend_->ShouldReportAgain()) {
    254       CACHE_UMA(AGE, "TrimAge", 0, entry->GetLastUsed());
    255       ReportListStats();
    256     }
    257 
    258     if (header_->lru.filled)
    259       return;
    260 
    261     header_->lru.filled = 1;
    262 
    263     if (header_->create_time) {
    264       // This is the first entry that we have to evict, generate some noise.
    265       backend_->FirstEviction();
    266     } else {
    267       // This is an old file, but we may want more reports from this user so
    268       // lets save some create_time.
    269       Time::Exploded old = {0};
    270       old.year = 2009;
    271       old.month = 3;
    272       old.day_of_month = 1;
    273       header_->create_time = Time::FromLocalExploded(old).ToInternalValue();
    274     }
    275   }
    276 }
    277 
    278 Rankings::List Eviction::GetListForEntry(EntryImpl* entry) {
    279   return Rankings::NO_USE;
    280 }
    281 
    282 bool Eviction::EvictEntry(CacheRankingsBlock* node, bool empty,
    283                           Rankings::List list) {
    284   EntryImpl* entry = backend_->GetEnumeratedEntry(node, list);
    285   if (!entry) {
    286     Trace("NewEntry failed on Trim 0x%x", node->address().value());
    287     return false;
    288   }
    289 
    290   ReportTrimTimes(entry);
    291   if (empty || !new_eviction_) {
    292     entry->DoomImpl();
    293   } else {
    294     entry->DeleteEntryData(false);
    295     EntryStore* info = entry->entry()->Data();
    296     DCHECK_EQ(ENTRY_NORMAL, info->state);
    297 
    298     rankings_->Remove(entry->rankings(), GetListForEntryV2(entry), true);
    299     info->state = ENTRY_EVICTED;
    300     entry->entry()->Store();
    301     rankings_->Insert(entry->rankings(), true, Rankings::DELETED);
    302   }
    303   if (!empty)
    304     backend_->OnEvent(Stats::TRIM_ENTRY);
    305 
    306   entry->Release();
    307 
    308   return true;
    309 }
    310 
    311 // -----------------------------------------------------------------------
    312 
    313 void Eviction::TrimCacheV2(bool empty) {
    314   Trace("*** Trim Cache ***");
    315   trimming_ = true;
    316   TimeTicks start = TimeTicks::Now();
    317 
    318   const int kListsToSearch = 3;
    319   Rankings::ScopedRankingsBlock next[kListsToSearch];
    320   int list = Rankings::LAST_ELEMENT;
    321 
    322   // Get a node from each list.
    323   for (int i = 0; i < kListsToSearch; i++) {
    324     bool done = false;
    325     next[i].set_rankings(rankings_);
    326     if (done)
    327       continue;
    328     next[i].reset(rankings_->GetPrev(NULL, static_cast<Rankings::List>(i)));
    329     if (!empty && NodeIsOldEnough(next[i].get(), i)) {
    330       list = static_cast<Rankings::List>(i);
    331       done = true;
    332     }
    333   }
    334 
    335   // If we are not meeting the time targets lets move on to list length.
    336   if (!empty && Rankings::LAST_ELEMENT == list)
    337     list = SelectListByLength(next);
    338 
    339   if (empty)
    340     list = 0;
    341 
    342   Rankings::ScopedRankingsBlock node(rankings_);
    343   int deleted_entries = 0;
    344   int target_size = empty ? 0 : max_size_;
    345 
    346   for (; list < kListsToSearch; list++) {
    347     while ((header_->num_bytes > target_size || test_mode_) &&
    348            next[list].get()) {
    349       // The iterator could be invalidated within EvictEntry().
    350       if (!next[list]->HasData())
    351         break;
    352       node.reset(next[list].release());
    353       next[list].reset(rankings_->GetPrev(node.get(),
    354                                           static_cast<Rankings::List>(list)));
    355       if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) {
    356         // This entry is not being used by anybody.
    357         // Do NOT use node as an iterator after this point.
    358         rankings_->TrackRankingsBlock(node.get(), false);
    359         if (EvictEntry(node.get(), empty, static_cast<Rankings::List>(list)))
    360           deleted_entries++;
    361 
    362         if (!empty && test_mode_)
    363           break;
    364       }
    365       if (!empty && (deleted_entries > 20 ||
    366                      (TimeTicks::Now() - start).InMilliseconds() > 20)) {
    367         base::MessageLoop::current()->PostTask(
    368             FROM_HERE,
    369             base::Bind(&Eviction::TrimCache, ptr_factory_.GetWeakPtr(), false));
    370         break;
    371       }
    372     }
    373     if (!empty)
    374       list = kListsToSearch;
    375   }
    376 
    377   if (empty) {
    378     TrimDeleted(true);
    379   } else if (ShouldTrimDeleted()) {
    380     base::MessageLoop::current()->PostTask(
    381         FROM_HERE,
    382         base::Bind(&Eviction::TrimDeleted, ptr_factory_.GetWeakPtr(), empty));
    383   }
    384 
    385   if (empty) {
    386     CACHE_UMA(AGE_MS, "TotalClearTimeV2", 0, start);
    387   } else {
    388     CACHE_UMA(AGE_MS, "TotalTrimTimeV2", 0, start);
    389   }
    390   CACHE_UMA(COUNTS, "TrimItemsV2", 0, deleted_entries);
    391 
    392   Trace("*** Trim Cache end ***");
    393   trimming_ = false;
    394   return;
    395 }
    396 
    397 void Eviction::UpdateRankV2(EntryImpl* entry, bool modified) {
    398   rankings_->UpdateRank(entry->rankings(), modified, GetListForEntryV2(entry));
    399 }
    400 
    401 void Eviction::OnOpenEntryV2(EntryImpl* entry) {
    402   EntryStore* info = entry->entry()->Data();
    403   DCHECK_EQ(ENTRY_NORMAL, info->state);
    404 
    405   if (info->reuse_count < kint32max) {
    406     info->reuse_count++;
    407     entry->entry()->set_modified();
    408 
    409     // We may need to move this to a new list.
    410     if (1 == info->reuse_count) {
    411       rankings_->Remove(entry->rankings(), Rankings::NO_USE, true);
    412       rankings_->Insert(entry->rankings(), false, Rankings::LOW_USE);
    413       entry->entry()->Store();
    414     } else if (kHighUse == info->reuse_count) {
    415       rankings_->Remove(entry->rankings(), Rankings::LOW_USE, true);
    416       rankings_->Insert(entry->rankings(), false, Rankings::HIGH_USE);
    417       entry->entry()->Store();
    418     }
    419   }
    420 }
    421 
    422 void Eviction::OnCreateEntryV2(EntryImpl* entry) {
    423   EntryStore* info = entry->entry()->Data();
    424   switch (info->state) {
    425     case ENTRY_NORMAL: {
    426       DCHECK(!info->reuse_count);
    427       DCHECK(!info->refetch_count);
    428       break;
    429     };
    430     case ENTRY_EVICTED: {
    431       if (info->refetch_count < kint32max)
    432         info->refetch_count++;
    433 
    434       if (info->refetch_count > kHighUse && info->reuse_count < kHighUse) {
    435         info->reuse_count = kHighUse;
    436       } else {
    437         info->reuse_count++;
    438       }
    439       info->state = ENTRY_NORMAL;
    440       entry->entry()->Store();
    441       rankings_->Remove(entry->rankings(), Rankings::DELETED, true);
    442       break;
    443     };
    444     default:
    445       NOTREACHED();
    446   }
    447 
    448   rankings_->Insert(entry->rankings(), true, GetListForEntryV2(entry));
    449 }
    450 
    451 void Eviction::OnDoomEntryV2(EntryImpl* entry) {
    452   EntryStore* info = entry->entry()->Data();
    453   if (ENTRY_NORMAL != info->state)
    454     return;
    455 
    456   if (entry->LeaveRankingsBehind()) {
    457     info->state = ENTRY_DOOMED;
    458     entry->entry()->Store();
    459     return;
    460   }
    461 
    462   rankings_->Remove(entry->rankings(), GetListForEntryV2(entry), true);
    463 
    464   info->state = ENTRY_DOOMED;
    465   entry->entry()->Store();
    466   rankings_->Insert(entry->rankings(), true, Rankings::DELETED);
    467 }
    468 
    469 void Eviction::OnDestroyEntryV2(EntryImpl* entry) {
    470   if (entry->LeaveRankingsBehind())
    471     return;
    472 
    473   rankings_->Remove(entry->rankings(), Rankings::DELETED, true);
    474 }
    475 
    476 Rankings::List Eviction::GetListForEntryV2(EntryImpl* entry) {
    477   EntryStore* info = entry->entry()->Data();
    478   DCHECK_EQ(ENTRY_NORMAL, info->state);
    479 
    480   if (!info->reuse_count)
    481     return Rankings::NO_USE;
    482 
    483   if (info->reuse_count < kHighUse)
    484     return Rankings::LOW_USE;
    485 
    486   return Rankings::HIGH_USE;
    487 }
    488 
    489 // This is a minimal implementation that just discards the oldest nodes.
    490 // TODO(rvargas): Do something better here.
    491 void Eviction::TrimDeleted(bool empty) {
    492   Trace("*** Trim Deleted ***");
    493   if (backend_->disabled_)
    494     return;
    495 
    496   TimeTicks start = TimeTicks::Now();
    497   Rankings::ScopedRankingsBlock node(rankings_);
    498   Rankings::ScopedRankingsBlock next(
    499     rankings_, rankings_->GetPrev(node.get(), Rankings::DELETED));
    500   int deleted_entries = 0;
    501   while (next.get() &&
    502          (empty || (deleted_entries < 20 &&
    503                     (TimeTicks::Now() - start).InMilliseconds() < 20))) {
    504     node.reset(next.release());
    505     next.reset(rankings_->GetPrev(node.get(), Rankings::DELETED));
    506     if (RemoveDeletedNode(node.get()))
    507       deleted_entries++;
    508     if (test_mode_)
    509       break;
    510   }
    511 
    512   if (deleted_entries && !empty && ShouldTrimDeleted()) {
    513     base::MessageLoop::current()->PostTask(
    514         FROM_HERE,
    515         base::Bind(&Eviction::TrimDeleted, ptr_factory_.GetWeakPtr(), false));
    516   }
    517 
    518   CACHE_UMA(AGE_MS, "TotalTrimDeletedTime", 0, start);
    519   CACHE_UMA(COUNTS, "TrimDeletedItems", 0, deleted_entries);
    520   Trace("*** Trim Deleted end ***");
    521   return;
    522 }
    523 
    524 bool Eviction::RemoveDeletedNode(CacheRankingsBlock* node) {
    525   EntryImpl* entry = backend_->GetEnumeratedEntry(node, Rankings::DELETED);
    526   if (!entry) {
    527     Trace("NewEntry failed on Trim 0x%x", node->address().value());
    528     return false;
    529   }
    530 
    531   bool doomed = (entry->entry()->Data()->state == ENTRY_DOOMED);
    532   entry->entry()->Data()->state = ENTRY_DOOMED;
    533   entry->DoomImpl();
    534   entry->Release();
    535   return !doomed;
    536 }
    537 
    538 bool Eviction::NodeIsOldEnough(CacheRankingsBlock* node, int list) {
    539   if (!node)
    540     return false;
    541 
    542   // If possible, we want to keep entries on each list at least kTargetTime
    543   // hours. Each successive list on the enumeration has 2x the target time of
    544   // the previous list.
    545   Time used = Time::FromInternalValue(node->Data()->last_used);
    546   int multiplier = 1 << list;
    547   return (Time::Now() - used).InHours() > kTargetTime * multiplier;
    548 }
    549 
    550 int Eviction::SelectListByLength(Rankings::ScopedRankingsBlock* next) {
    551   int data_entries = header_->num_entries -
    552                      header_->lru.sizes[Rankings::DELETED];
    553   // Start by having each list to be roughly the same size.
    554   if (header_->lru.sizes[0] > data_entries / 3)
    555     return 0;
    556 
    557   int list = (header_->lru.sizes[1] > data_entries / 3) ? 1 : 2;
    558 
    559   // Make sure that frequently used items are kept for a minimum time; we know
    560   // that this entry is not older than its current target, but it must be at
    561   // least older than the target for list 0 (kTargetTime), as long as we don't
    562   // exhaust list 0.
    563   if (!NodeIsOldEnough(next[list].get(), 0) &&
    564       header_->lru.sizes[0] > data_entries / 10)
    565     list = 0;
    566 
    567   return list;
    568 }
    569 
    570 void Eviction::ReportListStats() {
    571   if (!new_eviction_)
    572     return;
    573 
    574   Rankings::ScopedRankingsBlock last1(rankings_,
    575       rankings_->GetPrev(NULL, Rankings::NO_USE));
    576   Rankings::ScopedRankingsBlock last2(rankings_,
    577       rankings_->GetPrev(NULL, Rankings::LOW_USE));
    578   Rankings::ScopedRankingsBlock last3(rankings_,
    579       rankings_->GetPrev(NULL, Rankings::HIGH_USE));
    580   Rankings::ScopedRankingsBlock last4(rankings_,
    581       rankings_->GetPrev(NULL, Rankings::DELETED));
    582 
    583   if (last1.get())
    584     CACHE_UMA(AGE, "NoUseAge", 0,
    585               Time::FromInternalValue(last1.get()->Data()->last_used));
    586   if (last2.get())
    587     CACHE_UMA(AGE, "LowUseAge", 0,
    588               Time::FromInternalValue(last2.get()->Data()->last_used));
    589   if (last3.get())
    590     CACHE_UMA(AGE, "HighUseAge", 0,
    591               Time::FromInternalValue(last3.get()->Data()->last_used));
    592   if (last4.get())
    593     CACHE_UMA(AGE, "DeletedAge", 0,
    594               Time::FromInternalValue(last4.get()->Data()->last_used));
    595 }
    596 
    597 }  // namespace disk_cache
    598