eviction.cc revision 90dce4d38c5ff5333bea97d859d4e484e27edf0c
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 43using base::Time; 44using base::TimeTicks; 45 46namespace { 47 48const int kCleanUpMargin = 1024 * 1024; 49const int kHighUse = 10; // Reuse count to be on the HIGH_USE list. 50const int kTargetTime = 24 * 7; // Time to be evicted (hours since last use). 51const int kMaxDelayedTrims = 60; 52 53int LowWaterAdjust(int high_water) { 54 if (high_water < kCleanUpMargin) 55 return 0; 56 57 return high_water - kCleanUpMargin; 58} 59 60bool FallingBehind(int current_size, int max_size) { 61 return current_size > max_size - kCleanUpMargin * 20; 62} 63 64} // namespace 65 66namespace disk_cache { 67 68// The real initialization happens during Init(), init_ is the only member that 69// has to be initialized here. 70Eviction::Eviction() 71 : backend_(NULL), 72 init_(false), 73 ptr_factory_(this) { 74} 75 76Eviction::~Eviction() { 77} 78 79void 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 96void 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 109void 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 base::MessageLoop::current()->PostTask( 146 FROM_HERE, 147 base::Bind(&Eviction::TrimCache, ptr_factory_.GetWeakPtr(), false)); 148 break; 149 } 150 } 151 152 if (empty) { 153 CACHE_UMA(AGE_MS, "TotalClearTimeV1", 0, start); 154 } else { 155 CACHE_UMA(AGE_MS, "TotalTrimTimeV1", 0, start); 156 } 157 CACHE_UMA(COUNTS, "TrimItemsV1", 0, deleted_entries); 158 159 trimming_ = false; 160 Trace("*** Trim Cache end ***"); 161 return; 162} 163 164void Eviction::UpdateRank(EntryImpl* entry, bool modified) { 165 if (new_eviction_) 166 return UpdateRankV2(entry, modified); 167 168 rankings_->UpdateRank(entry->rankings(), modified, GetListForEntry(entry)); 169} 170 171void Eviction::OnOpenEntry(EntryImpl* entry) { 172 if (new_eviction_) 173 return OnOpenEntryV2(entry); 174} 175 176void Eviction::OnCreateEntry(EntryImpl* entry) { 177 if (new_eviction_) 178 return OnCreateEntryV2(entry); 179 180 rankings_->Insert(entry->rankings(), true, GetListForEntry(entry)); 181} 182 183void Eviction::OnDoomEntry(EntryImpl* entry) { 184 if (new_eviction_) 185 return OnDoomEntryV2(entry); 186 187 if (entry->LeaveRankingsBehind()) 188 return; 189 190 rankings_->Remove(entry->rankings(), GetListForEntry(entry), true); 191} 192 193void Eviction::OnDestroyEntry(EntryImpl* entry) { 194 if (new_eviction_) 195 return OnDestroyEntryV2(entry); 196} 197 198void Eviction::SetTestMode() { 199 test_mode_ = true; 200} 201 202void Eviction::TrimDeletedList(bool empty) { 203 DCHECK(test_mode_ && new_eviction_); 204 TrimDeleted(empty); 205} 206 207void Eviction::PostDelayedTrim() { 208 // Prevent posting multiple tasks. 209 if (delay_trim_) 210 return; 211 delay_trim_ = true; 212 trim_delays_++; 213 base::MessageLoop::current()->PostDelayedTask( 214 FROM_HERE, 215 base::Bind(&Eviction::DelayedTrim, ptr_factory_.GetWeakPtr()), 216 base::TimeDelta::FromMilliseconds(1000)); 217} 218 219void Eviction::DelayedTrim() { 220 delay_trim_ = false; 221 if (trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded()) 222 return PostDelayedTrim(); 223 224 TrimCache(false); 225} 226 227bool Eviction::ShouldTrim() { 228 if (!FallingBehind(header_->num_bytes, max_size_) && 229 trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded()) { 230 return false; 231 } 232 233 UMA_HISTOGRAM_COUNTS("DiskCache.TrimDelays", trim_delays_); 234 trim_delays_ = 0; 235 return true; 236} 237 238bool Eviction::ShouldTrimDeleted() { 239 int index_load = header_->num_entries * 100 / index_size_; 240 241 // If the index is not loaded, the deleted list will tend to double the size 242 // of the other lists 3 lists (40% of the total). Otherwise, all lists will be 243 // about the same size. 244 int max_length = (index_load < 25) ? header_->num_entries * 2 / 5 : 245 header_->num_entries / 4; 246 return (!test_mode_ && header_->lru.sizes[Rankings::DELETED] > max_length); 247} 248 249void Eviction::ReportTrimTimes(EntryImpl* entry) { 250 if (first_trim_) { 251 first_trim_ = false; 252 if (backend_->ShouldReportAgain()) { 253 CACHE_UMA(AGE, "TrimAge", 0, entry->GetLastUsed()); 254 ReportListStats(); 255 } 256 257 if (header_->lru.filled) 258 return; 259 260 header_->lru.filled = 1; 261 262 if (header_->create_time) { 263 // This is the first entry that we have to evict, generate some noise. 264 backend_->FirstEviction(); 265 } else { 266 // This is an old file, but we may want more reports from this user so 267 // lets save some create_time. 268 Time::Exploded old = {0}; 269 old.year = 2009; 270 old.month = 3; 271 old.day_of_month = 1; 272 header_->create_time = Time::FromLocalExploded(old).ToInternalValue(); 273 } 274 } 275} 276 277Rankings::List Eviction::GetListForEntry(EntryImpl* entry) { 278 return Rankings::NO_USE; 279} 280 281bool Eviction::EvictEntry(CacheRankingsBlock* node, bool empty, 282 Rankings::List list) { 283 EntryImpl* entry = backend_->GetEnumeratedEntry(node, list); 284 if (!entry) { 285 Trace("NewEntry failed on Trim 0x%x", node->address().value()); 286 return false; 287 } 288 289 ReportTrimTimes(entry); 290 if (empty || !new_eviction_) { 291 entry->DoomImpl(); 292 } else { 293 entry->DeleteEntryData(false); 294 EntryStore* info = entry->entry()->Data(); 295 DCHECK_EQ(ENTRY_NORMAL, info->state); 296 297 rankings_->Remove(entry->rankings(), GetListForEntryV2(entry), true); 298 info->state = ENTRY_EVICTED; 299 entry->entry()->Store(); 300 rankings_->Insert(entry->rankings(), true, Rankings::DELETED); 301 } 302 if (!empty) 303 backend_->OnEvent(Stats::TRIM_ENTRY); 304 305 entry->Release(); 306 307 return true; 308} 309 310// ----------------------------------------------------------------------- 311 312void Eviction::TrimCacheV2(bool empty) { 313 Trace("*** Trim Cache ***"); 314 trimming_ = true; 315 TimeTicks start = TimeTicks::Now(); 316 317 const int kListsToSearch = 3; 318 Rankings::ScopedRankingsBlock next[kListsToSearch]; 319 int list = Rankings::LAST_ELEMENT; 320 321 // Get a node from each list. 322 for (int i = 0; i < kListsToSearch; i++) { 323 bool done = false; 324 next[i].set_rankings(rankings_); 325 if (done) 326 continue; 327 next[i].reset(rankings_->GetPrev(NULL, static_cast<Rankings::List>(i))); 328 if (!empty && NodeIsOldEnough(next[i].get(), i)) { 329 list = static_cast<Rankings::List>(i); 330 done = true; 331 } 332 } 333 334 // If we are not meeting the time targets lets move on to list length. 335 if (!empty && Rankings::LAST_ELEMENT == list) 336 list = SelectListByLength(next); 337 338 if (empty) 339 list = 0; 340 341 Rankings::ScopedRankingsBlock node(rankings_); 342 int deleted_entries = 0; 343 int target_size = empty ? 0 : max_size_; 344 345 for (; list < kListsToSearch; list++) { 346 while ((header_->num_bytes > target_size || test_mode_) && 347 next[list].get()) { 348 // The iterator could be invalidated within EvictEntry(). 349 if (!next[list]->HasData()) 350 break; 351 node.reset(next[list].release()); 352 next[list].reset(rankings_->GetPrev(node.get(), 353 static_cast<Rankings::List>(list))); 354 if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) { 355 // This entry is not being used by anybody. 356 // Do NOT use node as an iterator after this point. 357 rankings_->TrackRankingsBlock(node.get(), false); 358 if (EvictEntry(node.get(), empty, static_cast<Rankings::List>(list))) 359 deleted_entries++; 360 361 if (!empty && test_mode_) 362 break; 363 } 364 if (!empty && (deleted_entries > 20 || 365 (TimeTicks::Now() - start).InMilliseconds() > 20)) { 366 base::MessageLoop::current()->PostTask( 367 FROM_HERE, 368 base::Bind(&Eviction::TrimCache, ptr_factory_.GetWeakPtr(), false)); 369 break; 370 } 371 } 372 if (!empty) 373 list = kListsToSearch; 374 } 375 376 if (empty) { 377 TrimDeleted(true); 378 } else if (ShouldTrimDeleted()) { 379 base::MessageLoop::current()->PostTask( 380 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 396void Eviction::UpdateRankV2(EntryImpl* entry, bool modified) { 397 rankings_->UpdateRank(entry->rankings(), modified, GetListForEntryV2(entry)); 398} 399 400void 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 421void 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 450void 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 468void Eviction::OnDestroyEntryV2(EntryImpl* entry) { 469 if (entry->LeaveRankingsBehind()) 470 return; 471 472 rankings_->Remove(entry->rankings(), Rankings::DELETED, true); 473} 474 475Rankings::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. 490void 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 base::MessageLoop::current()->PostTask( 513 FROM_HERE, 514 base::Bind(&Eviction::TrimDeleted, ptr_factory_.GetWeakPtr(), false)); 515 } 516 517 CACHE_UMA(AGE_MS, "TotalTrimDeletedTime", 0, start); 518 CACHE_UMA(COUNTS, "TrimDeletedItems", 0, deleted_entries); 519 Trace("*** Trim Deleted end ***"); 520 return; 521} 522 523bool Eviction::RemoveDeletedNode(CacheRankingsBlock* node) { 524 EntryImpl* entry = backend_->GetEnumeratedEntry(node, Rankings::DELETED); 525 if (!entry) { 526 Trace("NewEntry failed on Trim 0x%x", node->address().value()); 527 return false; 528 } 529 530 bool doomed = (entry->entry()->Data()->state == ENTRY_DOOMED); 531 entry->entry()->Data()->state = ENTRY_DOOMED; 532 entry->DoomImpl(); 533 entry->Release(); 534 return !doomed; 535} 536 537bool Eviction::NodeIsOldEnough(CacheRankingsBlock* node, int list) { 538 if (!node) 539 return false; 540 541 // If possible, we want to keep entries on each list at least kTargetTime 542 // hours. Each successive list on the enumeration has 2x the target time of 543 // the previous list. 544 Time used = Time::FromInternalValue(node->Data()->last_used); 545 int multiplier = 1 << list; 546 return (Time::Now() - used).InHours() > kTargetTime * multiplier; 547} 548 549int Eviction::SelectListByLength(Rankings::ScopedRankingsBlock* next) { 550 int data_entries = header_->num_entries - 551 header_->lru.sizes[Rankings::DELETED]; 552 // Start by having each list to be roughly the same size. 553 if (header_->lru.sizes[0] > data_entries / 3) 554 return 0; 555 556 int list = (header_->lru.sizes[1] > data_entries / 3) ? 1 : 2; 557 558 // Make sure that frequently used items are kept for a minimum time; we know 559 // that this entry is not older than its current target, but it must be at 560 // least older than the target for list 0 (kTargetTime), as long as we don't 561 // exhaust list 0. 562 if (!NodeIsOldEnough(next[list].get(), 0) && 563 header_->lru.sizes[0] > data_entries / 10) 564 list = 0; 565 566 return list; 567} 568 569void Eviction::ReportListStats() { 570 if (!new_eviction_) 571 return; 572 573 Rankings::ScopedRankingsBlock last1(rankings_, 574 rankings_->GetPrev(NULL, Rankings::NO_USE)); 575 Rankings::ScopedRankingsBlock last2(rankings_, 576 rankings_->GetPrev(NULL, Rankings::LOW_USE)); 577 Rankings::ScopedRankingsBlock last3(rankings_, 578 rankings_->GetPrev(NULL, Rankings::HIGH_USE)); 579 Rankings::ScopedRankingsBlock last4(rankings_, 580 rankings_->GetPrev(NULL, Rankings::DELETED)); 581 582 if (last1.get()) 583 CACHE_UMA(AGE, "NoUseAge", 0, 584 Time::FromInternalValue(last1.get()->Data()->last_used)); 585 if (last2.get()) 586 CACHE_UMA(AGE, "LowUseAge", 0, 587 Time::FromInternalValue(last2.get()->Data()->last_used)); 588 if (last3.get()) 589 CACHE_UMA(AGE, "HighUseAge", 0, 590 Time::FromInternalValue(last3.get()->Data()->last_used)); 591 if (last4.get()) 592 CACHE_UMA(AGE, "DeletedAge", 0, 593 Time::FromInternalValue(last4.get()->Data()->last_used)); 594} 595 596} // namespace disk_cache 597