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