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