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