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