Updating trunk VERSION from 1010.0 to 1011.0
[chromium-blink-merge.git] / net / disk_cache / eviction.cc
blob2e50db9d080d4cd1e2b110e490ce9ed531a42509
1 // Copyright (c) 2011 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.
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.
10 // The new (in-development) eviction policy adds re-use as a factor to evict
11 // an entry. The story so far:
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.
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.
29 #include "net/disk_cache/eviction.h"
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"
43 using base::Time;
44 using base::TimeTicks;
46 namespace {
48 const int kCleanUpMargin = 1024 * 1024;
49 const int kHighUse = 10; // Reuse count to be on the HIGH_USE list.
50 const int kTargetTime = 24 * 7; // Time to be evicted (hours since last use).
51 const int kMaxDelayedTrims = 60;
53 int LowWaterAdjust(int high_water) {
54 if (high_water < kCleanUpMargin)
55 return 0;
57 return high_water - kCleanUpMargin;
60 } // namespace
62 namespace disk_cache {
64 Eviction::Eviction()
65 : backend_(NULL),
66 init_(false),
67 ALLOW_THIS_IN_INITIALIZER_LIST(ptr_factory_(this)) {
70 Eviction::~Eviction() {
73 void Eviction::Init(BackendImpl* backend) {
74 // We grab a bunch of info from the backend to make the code a little cleaner
75 // when we're actually doing work.
76 backend_ = backend;
77 rankings_ = &backend->rankings_;
78 header_ = &backend_->data_->header;
79 max_size_ = LowWaterAdjust(backend_->max_size_);
80 new_eviction_ = backend->new_eviction_;
81 first_trim_ = true;
82 trimming_ = false;
83 delay_trim_ = false;
84 trim_delays_ = 0;
85 init_ = true;
86 test_mode_ = false;
87 in_experiment_ = (header_->experiment == EXPERIMENT_DELETED_LIST_IN);
90 void Eviction::Stop() {
91 // It is possible for the backend initialization to fail, in which case this
92 // object was never initialized... and there is nothing to do.
93 if (!init_)
94 return;
96 // We want to stop further evictions, so let's pretend that we are busy from
97 // this point on.
98 DCHECK(!trimming_);
99 trimming_ = true;
100 ptr_factory_.InvalidateWeakPtrs();
103 void Eviction::TrimCache(bool empty) {
104 if (backend_->disabled_ || trimming_)
105 return;
107 if (!empty && !ShouldTrim())
108 return PostDelayedTrim();
110 if (new_eviction_)
111 return TrimCacheV2(empty);
113 Trace("*** Trim Cache ***");
114 trimming_ = true;
115 TimeTicks start = TimeTicks::Now();
116 Rankings::ScopedRankingsBlock node(rankings_);
117 Rankings::ScopedRankingsBlock next(
118 rankings_, rankings_->GetPrev(node.get(), Rankings::NO_USE));
119 int deleted_entries = 0;
120 int target_size = empty ? 0 : max_size_;
121 while ((header_->num_bytes > target_size || test_mode_) && next.get()) {
122 // The iterator could be invalidated within EvictEntry().
123 if (!next->HasData())
124 break;
125 node.reset(next.release());
126 next.reset(rankings_->GetPrev(node.get(), Rankings::NO_USE));
127 if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) {
128 // This entry is not being used by anybody.
129 // Do NOT use node as an iterator after this point.
130 rankings_->TrackRankingsBlock(node.get(), false);
131 if (EvictEntry(node.get(), empty, Rankings::NO_USE) && !test_mode_)
132 deleted_entries++;
134 if (!empty && test_mode_)
135 break;
137 if (!empty && (deleted_entries > 20 ||
138 (TimeTicks::Now() - start).InMilliseconds() > 20)) {
139 MessageLoop::current()->PostTask(FROM_HERE, base::Bind(
140 &Eviction::TrimCache, ptr_factory_.GetWeakPtr(), false));
141 break;
145 if (empty) {
146 CACHE_UMA(AGE_MS, "TotalClearTimeV1", 0, start);
147 } else {
148 CACHE_UMA(AGE_MS, "TotalTrimTimeV1", 0, start);
150 CACHE_UMA(COUNTS, "TrimItemsV1", 0, deleted_entries);
152 trimming_ = false;
153 Trace("*** Trim Cache end ***");
154 return;
157 void Eviction::UpdateRank(EntryImpl* entry, bool modified) {
158 if (new_eviction_)
159 return UpdateRankV2(entry, modified);
161 rankings_->UpdateRank(entry->rankings(), modified, GetListForEntry(entry));
164 void Eviction::OnOpenEntry(EntryImpl* entry) {
165 if (new_eviction_)
166 return OnOpenEntryV2(entry);
169 void Eviction::OnCreateEntry(EntryImpl* entry) {
170 if (new_eviction_)
171 return OnCreateEntryV2(entry);
173 rankings_->Insert(entry->rankings(), true, GetListForEntry(entry));
176 void Eviction::OnDoomEntry(EntryImpl* entry) {
177 if (new_eviction_)
178 return OnDoomEntryV2(entry);
180 if (entry->LeaveRankingsBehind())
181 return;
183 rankings_->Remove(entry->rankings(), GetListForEntry(entry), true);
186 void Eviction::OnDestroyEntry(EntryImpl* entry) {
187 if (new_eviction_)
188 return OnDestroyEntryV2(entry);
191 void Eviction::SetTestMode() {
192 test_mode_ = true;
195 void Eviction::TrimDeletedList(bool empty) {
196 DCHECK(test_mode_ && new_eviction_);
197 TrimDeleted(empty);
200 void Eviction::PostDelayedTrim() {
201 // Prevent posting multiple tasks.
202 if (delay_trim_)
203 return;
204 delay_trim_ = true;
205 trim_delays_++;
206 MessageLoop::current()->PostDelayedTask(FROM_HERE,
207 base::Bind(&Eviction::DelayedTrim, ptr_factory_.GetWeakPtr()), 1000);
210 void Eviction::DelayedTrim() {
211 delay_trim_ = false;
212 if (trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded())
213 return PostDelayedTrim();
215 TrimCache(false);
218 bool Eviction::ShouldTrim() {
219 if (trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded())
220 return false;
222 UMA_HISTOGRAM_COUNTS("DiskCache.TrimDelays", trim_delays_);
223 trim_delays_ = 0;
224 return true;
227 bool Eviction::ShouldTrimDeleted() {
228 // Normally we use 25% for each list. The experiment doubles the number of
229 // deleted entries, so the total number of entries increases by 25%. Using
230 // 40% of that value for deleted entries leaves the size of the other three
231 // lists intact.
232 int max_length = in_experiment_ ? header_->num_entries * 2 / 5 :
233 header_->num_entries / 4;
234 return (!test_mode_ && header_->lru.sizes[Rankings::DELETED] > max_length);
237 void Eviction::ReportTrimTimes(EntryImpl* entry) {
238 if (first_trim_) {
239 first_trim_ = false;
240 if (backend_->ShouldReportAgain()) {
241 CACHE_UMA(AGE, "TrimAge", 0, entry->GetLastUsed());
242 ReportListStats();
245 if (header_->lru.filled)
246 return;
248 header_->lru.filled = 1;
250 if (header_->create_time) {
251 // This is the first entry that we have to evict, generate some noise.
252 backend_->FirstEviction();
253 in_experiment_ = (header_->experiment == EXPERIMENT_DELETED_LIST_IN);
254 } else {
255 // This is an old file, but we may want more reports from this user so
256 // lets save some create_time.
257 Time::Exploded old = {0};
258 old.year = 2009;
259 old.month = 3;
260 old.day_of_month = 1;
261 header_->create_time = Time::FromLocalExploded(old).ToInternalValue();
266 Rankings::List Eviction::GetListForEntry(EntryImpl* entry) {
267 return Rankings::NO_USE;
270 bool Eviction::EvictEntry(CacheRankingsBlock* node, bool empty,
271 Rankings::List list) {
272 EntryImpl* entry = backend_->GetEnumeratedEntry(node, list);
273 if (!entry) {
274 Trace("NewEntry failed on Trim 0x%x", node->address().value());
275 return false;
278 ReportTrimTimes(entry);
279 if (empty || !new_eviction_) {
280 entry->DoomImpl();
281 if (!empty)
282 backend_->OnEvent(Stats::TRIM_ENTRY);
283 } else {
284 entry->DeleteEntryData(false);
285 EntryStore* info = entry->entry()->Data();
286 DCHECK_EQ(ENTRY_NORMAL, info->state);
288 rankings_->Remove(entry->rankings(), GetListForEntryV2(entry), true);
289 info->state = ENTRY_EVICTED;
290 entry->entry()->Store();
291 rankings_->Insert(entry->rankings(), true, Rankings::DELETED);
292 backend_->OnEvent(Stats::TRIM_ENTRY);
294 entry->Release();
296 return true;
299 // -----------------------------------------------------------------------
301 void Eviction::TrimCacheV2(bool empty) {
302 Trace("*** Trim Cache ***");
303 trimming_ = true;
304 TimeTicks start = TimeTicks::Now();
306 const int kListsToSearch = 3;
307 Rankings::ScopedRankingsBlock next[kListsToSearch];
308 int list = Rankings::LAST_ELEMENT;
310 // Get a node from each list.
311 for (int i = 0; i < kListsToSearch; i++) {
312 bool done = false;
313 next[i].set_rankings(rankings_);
314 if (done)
315 continue;
316 next[i].reset(rankings_->GetPrev(NULL, static_cast<Rankings::List>(i)));
317 if (!empty && NodeIsOldEnough(next[i].get(), i)) {
318 list = static_cast<Rankings::List>(i);
319 done = true;
323 // If we are not meeting the time targets lets move on to list length.
324 if (!empty && Rankings::LAST_ELEMENT == list)
325 list = SelectListByLength(next);
327 if (empty)
328 list = 0;
330 Rankings::ScopedRankingsBlock node(rankings_);
331 int deleted_entries = 0;
332 int target_size = empty ? 0 : max_size_;
334 for (; list < kListsToSearch; list++) {
335 while ((header_->num_bytes > target_size || test_mode_) &&
336 next[list].get()) {
337 // The iterator could be invalidated within EvictEntry().
338 if (!next[list]->HasData())
339 break;
340 node.reset(next[list].release());
341 next[list].reset(rankings_->GetPrev(node.get(),
342 static_cast<Rankings::List>(list)));
343 if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) {
344 // This entry is not being used by anybody.
345 // Do NOT use node as an iterator after this point.
346 rankings_->TrackRankingsBlock(node.get(), false);
347 if (EvictEntry(node.get(), empty, static_cast<Rankings::List>(list)))
348 deleted_entries++;
350 if (!empty && test_mode_)
351 break;
353 if (!empty && (deleted_entries > 20 ||
354 (TimeTicks::Now() - start).InMilliseconds() > 20)) {
355 MessageLoop::current()->PostTask(FROM_HERE, base::Bind(
356 &Eviction::TrimCache, ptr_factory_.GetWeakPtr(), false));
357 break;
360 if (!empty)
361 list = kListsToSearch;
364 if (empty) {
365 TrimDeleted(true);
366 } else if (ShouldTrimDeleted()) {
367 MessageLoop::current()->PostTask(FROM_HERE,
368 base::Bind(&Eviction::TrimDeleted, ptr_factory_.GetWeakPtr(), empty));
371 if (empty) {
372 CACHE_UMA(AGE_MS, "TotalClearTimeV2", 0, start);
373 } else {
374 CACHE_UMA(AGE_MS, "TotalTrimTimeV2", 0, start);
376 CACHE_UMA(COUNTS, "TrimItemsV2", 0, deleted_entries);
378 Trace("*** Trim Cache end ***");
379 trimming_ = false;
380 return;
383 void Eviction::UpdateRankV2(EntryImpl* entry, bool modified) {
384 rankings_->UpdateRank(entry->rankings(), modified, GetListForEntryV2(entry));
387 void Eviction::OnOpenEntryV2(EntryImpl* entry) {
388 EntryStore* info = entry->entry()->Data();
389 DCHECK_EQ(ENTRY_NORMAL, info->state);
391 if (info->reuse_count < kint32max) {
392 info->reuse_count++;
393 entry->entry()->set_modified();
395 // We may need to move this to a new list.
396 if (1 == info->reuse_count) {
397 rankings_->Remove(entry->rankings(), Rankings::NO_USE, true);
398 rankings_->Insert(entry->rankings(), false, Rankings::LOW_USE);
399 entry->entry()->Store();
400 } else if (kHighUse == info->reuse_count) {
401 rankings_->Remove(entry->rankings(), Rankings::LOW_USE, true);
402 rankings_->Insert(entry->rankings(), false, Rankings::HIGH_USE);
403 entry->entry()->Store();
408 void Eviction::OnCreateEntryV2(EntryImpl* entry) {
409 EntryStore* info = entry->entry()->Data();
410 switch (info->state) {
411 case ENTRY_NORMAL: {
412 DCHECK(!info->reuse_count);
413 DCHECK(!info->refetch_count);
414 break;
416 case ENTRY_EVICTED: {
417 if (info->refetch_count < kint32max)
418 info->refetch_count++;
420 if (info->refetch_count > kHighUse && info->reuse_count < kHighUse) {
421 info->reuse_count = kHighUse;
422 } else {
423 info->reuse_count++;
425 info->state = ENTRY_NORMAL;
426 entry->entry()->Store();
427 rankings_->Remove(entry->rankings(), Rankings::DELETED, true);
428 break;
430 default:
431 NOTREACHED();
434 rankings_->Insert(entry->rankings(), true, GetListForEntryV2(entry));
437 void Eviction::OnDoomEntryV2(EntryImpl* entry) {
438 EntryStore* info = entry->entry()->Data();
439 if (ENTRY_NORMAL != info->state)
440 return;
442 if (entry->LeaveRankingsBehind()) {
443 info->state = ENTRY_DOOMED;
444 entry->entry()->Store();
445 return;
448 rankings_->Remove(entry->rankings(), GetListForEntryV2(entry), true);
450 info->state = ENTRY_DOOMED;
451 entry->entry()->Store();
452 rankings_->Insert(entry->rankings(), true, Rankings::DELETED);
455 void Eviction::OnDestroyEntryV2(EntryImpl* entry) {
456 if (entry->LeaveRankingsBehind())
457 return;
459 rankings_->Remove(entry->rankings(), Rankings::DELETED, true);
462 Rankings::List Eviction::GetListForEntryV2(EntryImpl* entry) {
463 EntryStore* info = entry->entry()->Data();
464 DCHECK_EQ(ENTRY_NORMAL, info->state);
466 if (!info->reuse_count)
467 return Rankings::NO_USE;
469 if (info->reuse_count < kHighUse)
470 return Rankings::LOW_USE;
472 return Rankings::HIGH_USE;
475 // This is a minimal implementation that just discards the oldest nodes.
476 // TODO(rvargas): Do something better here.
477 void Eviction::TrimDeleted(bool empty) {
478 Trace("*** Trim Deleted ***");
479 if (backend_->disabled_)
480 return;
482 TimeTicks start = TimeTicks::Now();
483 Rankings::ScopedRankingsBlock node(rankings_);
484 Rankings::ScopedRankingsBlock next(
485 rankings_, rankings_->GetPrev(node.get(), Rankings::DELETED));
486 int deleted_entries = 0;
487 while (next.get() &&
488 (empty || (deleted_entries < 20 &&
489 (TimeTicks::Now() - start).InMilliseconds() < 20))) {
490 node.reset(next.release());
491 next.reset(rankings_->GetPrev(node.get(), Rankings::DELETED));
492 if (RemoveDeletedNode(node.get()))
493 deleted_entries++;
494 if (test_mode_)
495 break;
498 if (deleted_entries && !empty && ShouldTrimDeleted()) {
499 MessageLoop::current()->PostTask(FROM_HERE,
500 base::Bind(&Eviction::TrimDeleted, ptr_factory_.GetWeakPtr(), false));
503 CACHE_UMA(AGE_MS, "TotalTrimDeletedTime", 0, start);
504 CACHE_UMA(COUNTS, "TrimDeletedItems", 0, deleted_entries);
505 Trace("*** Trim Deleted end ***");
506 return;
509 bool Eviction::RemoveDeletedNode(CacheRankingsBlock* node) {
510 EntryImpl* entry = backend_->GetEnumeratedEntry(node, Rankings::DELETED);
511 if (!entry) {
512 Trace("NewEntry failed on Trim 0x%x", node->address().value());
513 return false;
516 bool doomed = (entry->entry()->Data()->state == ENTRY_DOOMED);
517 entry->entry()->Data()->state = ENTRY_DOOMED;
518 entry->DoomImpl();
519 entry->Release();
520 return !doomed;
523 bool Eviction::NodeIsOldEnough(CacheRankingsBlock* node, int list) {
524 if (!node)
525 return false;
527 // If possible, we want to keep entries on each list at least kTargetTime
528 // hours. Each successive list on the enumeration has 2x the target time of
529 // the previous list.
530 Time used = Time::FromInternalValue(node->Data()->last_used);
531 int multiplier = 1 << list;
532 return (Time::Now() - used).InHours() > kTargetTime * multiplier;
535 int Eviction::SelectListByLength(Rankings::ScopedRankingsBlock* next) {
536 int data_entries = header_->num_entries -
537 header_->lru.sizes[Rankings::DELETED];
538 // Start by having each list to be roughly the same size.
539 if (header_->lru.sizes[0] > data_entries / 3)
540 return 0;
542 int list = (header_->lru.sizes[1] > data_entries / 3) ? 1 : 2;
544 // Make sure that frequently used items are kept for a minimum time; we know
545 // that this entry is not older than its current target, but it must be at
546 // least older than the target for list 0 (kTargetTime), as long as we don't
547 // exhaust list 0.
548 if (!NodeIsOldEnough(next[list].get(), 0) &&
549 header_->lru.sizes[0] > data_entries / 10)
550 list = 0;
552 return list;
555 void Eviction::ReportListStats() {
556 if (!new_eviction_)
557 return;
559 Rankings::ScopedRankingsBlock last1(rankings_,
560 rankings_->GetPrev(NULL, Rankings::NO_USE));
561 Rankings::ScopedRankingsBlock last2(rankings_,
562 rankings_->GetPrev(NULL, Rankings::LOW_USE));
563 Rankings::ScopedRankingsBlock last3(rankings_,
564 rankings_->GetPrev(NULL, Rankings::HIGH_USE));
565 Rankings::ScopedRankingsBlock last4(rankings_,
566 rankings_->GetPrev(NULL, Rankings::DELETED));
568 if (last1.get())
569 CACHE_UMA(AGE, "NoUseAge", 0,
570 Time::FromInternalValue(last1.get()->Data()->last_used));
571 if (last2.get())
572 CACHE_UMA(AGE, "LowUseAge", 0,
573 Time::FromInternalValue(last2.get()->Data()->last_used));
574 if (last3.get())
575 CACHE_UMA(AGE, "HighUseAge", 0,
576 Time::FromInternalValue(last3.get()->Data()->last_used));
577 if (last4.get())
578 CACHE_UMA(AGE, "DeletedAge", 0,
579 Time::FromInternalValue(last4.get()->Data()->last_used));
582 } // namespace disk_cache