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