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