net/disk_cache/eviction.cc

   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.h"
  35 #include "base/strings/string_util.h"
  36 #include "base/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