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
48using base::Time;
49using base::TimeTicks;
50
51namespace {
52
53const int kCleanUpMargin = 1024 * 1024;
54const int kHighUse = 10;  // Reuse count to be on the HIGH_USE list.
55const int kTargetTime = 24 * 7;  // Time to be evicted (hours since last use).
56const int kMaxDelayedTrims = 60;
57
58int LowWaterAdjust(int high_water) {
59  if (high_water < kCleanUpMargin)
60    return 0;
61
62  return high_water - kCleanUpMargin;
63}
64
65bool FallingBehind(int current_size, int max_size) {
66  return current_size > max_size - kCleanUpMargin * 20;
67}
68
69}  // namespace
70
71namespace disk_cache {
72
73// The real initialization happens during Init(), init_ is the only member that
74// has to be initialized here.
75Eviction::Eviction()
76    : backend_(NULL),
77      init_(false),
78      ptr_factory_(this) {
79}
80
81Eviction::~Eviction() {
82}
83
84void 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
101void 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
114void 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
169void 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
176void Eviction::OnOpenEntry(EntryImpl* entry) {
177  if (new_eviction_)
178    return OnOpenEntryV2(entry);
179}
180
181void Eviction::OnCreateEntry(EntryImpl* entry) {
182  if (new_eviction_)
183    return OnCreateEntryV2(entry);
184
185  rankings_->Insert(entry->rankings(), true, GetListForEntry(entry));
186}
187
188void 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
198void Eviction::OnDestroyEntry(EntryImpl* entry) {
199  if (new_eviction_)
200    return OnDestroyEntryV2(entry);
201}
202
203void Eviction::SetTestMode() {
204  test_mode_ = true;
205}
206
207void Eviction::TrimDeletedList(bool empty) {
208  DCHECK(test_mode_ && new_eviction_);
209  TrimDeleted(empty);
210}
211
212void 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
224void Eviction::DelayedTrim() {
225  delay_trim_ = false;
226  if (trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded())
227    return PostDelayedTrim();
228
229  TrimCache(false);
230}
231
232bool 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
243bool 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
254void 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
282Rankings::List Eviction::GetListForEntry(EntryImpl* entry) {
283  return Rankings::NO_USE;
284}
285
286bool 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
318void 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
402void Eviction::UpdateRankV2(EntryImpl* entry, bool modified) {
403  rankings_->UpdateRank(entry->rankings(), modified, GetListForEntryV2(entry));
404}
405
406void 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
427void 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
456void 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
474void Eviction::OnDestroyEntryV2(EntryImpl* entry) {
475  if (entry->LeaveRankingsBehind())
476    return;
477
478  rankings_->Remove(entry->rankings(), Rankings::DELETED, true);
479}
480
481Rankings::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.
496void 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
529bool 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
543bool 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
555int 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
575void 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