net/disk_cache/eviction.cc

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