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 603