Disk cache: Reference CL for the implementation of file format version 3.

net/disk_cache/v3/eviction_v3.cc

+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// The eviction policy is a very simple pure LRU, so the elements at the end of
+// the list are evicted until kCleanUpMargin free space is available. There is
+// only one list in use (Rankings::NO_USE), and elements are sent to the front
+// of the list whenever they are accessed.
+
+// The new (in-development) eviction policy adds re-use as a factor to evict
+// an entry. The story so far:
+
+// Entries are linked on separate lists depending on how often they are used.
+// When we see an element for the first time, it goes to the NO_USE list; if
+// the object is reused later on, we move it to the LOW_USE list, until it is
+// used kHighUse times, at which point it is moved to the HIGH_USE list.
+// Whenever an element is evicted, we move it to the DELETED list so that if the
+// element is accessed again, we remember the fact that it was already stored
+// and maybe in the future we don't evict that element.
+
+// When we have to evict an element, first we try to use the last element from
+// the NO_USE list, then we move to the LOW_USE and only then we evict an entry
+// from the HIGH_USE. We attempt to keep entries on the cache for at least
+// kTargetTime hours (with frequently accessed items stored for longer periods),
+// but if we cannot do that, we fall-back to keep each list roughly the same
+// size so that we have a chance to see an element again and move it to another
+// list.
+
+#include "net/disk_cache/v3/eviction_v3.h"
+
+#include "base/bind.h"
+#include "base/compiler_specific.h"
+#include "base/logging.h"
+#include "base/message_loop.h"
+#include "base/string_util.h"
+#include "base/time.h"
+#include "net/base/net_errors.h"
+#include "net/disk_cache/experiments.h"
+#include "net/disk_cache/histogram_macros.h"
+#include "net/disk_cache/trace.h"
+#include "net/disk_cache/v3/backend_impl_v3.h"
+#include "net/disk_cache/v3/entry_impl_v3.h"
+#include "net/disk_cache/v3/index_table.h"
+
+
+using base::Time;
+using base::TimeDelta;
+using base::TimeTicks;
+
+namespace {
+
+const int kCleanUpMargin = 1024 * 1024;
+const int kHighUse = 10;  // Reuse count to be on the HIGH_USE list.
+const int kTargetTime = 24 * 7;  // Time to be evicted (hours since last use).
+const int kMaxDelayedTrims = 60;
+
+int LowWaterAdjust(int high_water) {
+  if (high_water < kCleanUpMargin)
+    return 0;
+
+  return high_water - kCleanUpMargin;
+}
+
+bool FallingBehind(int current_size, int max_size) {
+  return current_size > max_size - kCleanUpMargin * 20;
+}
+
+Time TimeFromTimestamp(int timestamp, int64 base_time) {
+  return Time::FromInternalValue(base_time) + TimeDelta::FromSeconds(timestamp);
+}
+
+}  // namespace
+
+namespace disk_cache {
+
+// The real initialization happens during Init(), init_ is the only member that
+// has to be initialized here.
+EvictionV3::EvictionV3()
+    : backend_(NULL),
+      index_(NULL),
+      header_(NULL),
+      init_(false),
+      cells_to_evict_(NULL),
+      ptr_factory_(this) {
+}
+
+EvictionV3::~EvictionV3() {
+}
+
+void EvictionV3::Init(BackendImplV3* backend) {
+  // We grab a bunch of info from the backend to make the code a little cleaner
+  // when we're actually doing work.
+  backend_ = backend;
+  index_ = &backend_->index_;
+  header_ = index_->header();
+  max_size_ = LowWaterAdjust(backend_->max_size_);
+  index_size_ = 1;//?
+  lru_ = backend->lru_eviction_;
+  first_trim_ = true;
+  trimming_ = false;
+  delay_trim_ = false;
+  trim_delays_ = 0;
+  init_ = true;
+  test_mode_ = false;
+  empty_ = false;
+}
+
+void EvictionV3::Stop() {
+  // It is possible for the backend initialization to fail, in which case this
+  // object was never initialized... and there is nothing to do.
+  if (!init_)
+    return;
+
+  // We want to stop further evictions, so let's pretend that we are busy from
+  // this point on.
+  DCHECK(!trimming_);//cannot do
+  trimming_ = true;
+  ptr_factory_.InvalidateWeakPtrs();
+}
+
+void EvictionV3::TrimCache() {
+  if (trimming_)
+    return;
+
+  if (!ShouldTrim())
+    return PostDelayedTrim();
+
+  Trace("*** Trim Cache ***");
+  trimming_ = true;
+
+  if (!TrimCacheImpl()) {
+    trimming_ = false;
+    Trace("*** Trim Cache end ***");
+  }
+}
+
+int EvictionV3::TrimAllCache(const net::CompletionCallback& callback) {
+  if (!callback_.is_null())
+    return net::ERR_FAILED;
+
+  empty_ = true;
+  trimming_ = true;
+  Trace("*** Trim All Cache ***");
+
+  if (!TrimCacheImpl())
+    return net::OK;
+
+  callback_ = callback;
+  return net::ERR_IO_PENDING;
+}
+
+void EvictionV3::OnOpenEntry(EntryImplV3* entry) {
+  if (lru_)
+    return;
+
+  EntryCell cell = index_->FindEntryCell(entry->GetHash(), entry->GetAddress());
+  DCHECK_NE(cell.group(), ENTRY_EVICTED);
+  int reuse_count = entry->GetReuseCounter();
+
+  if (reuse_count < 256) {
+    reuse_count++;
+    entry->SetReuseCounter(reuse_count);
+
+    // We may need to move this to a new list.
+    if (1 == reuse_count) {
+      DCHECK_EQ(cell.group(), ENTRY_NO_USE);
+      cell.set_group(ENTRY_LOW_USE);
+    } else if (kHighUse == reuse_count) {
+      DCHECK_EQ(cell.group(), ENTRY_LOW_USE);
+      cell.set_group(ENTRY_HIGH_USE);
+    }
+    if (reuse_count < 16) {
+      cell.set_reuse(reuse_count);
+      index_->Save(&cell);
+    }
+  }
+}
+
+void EvictionV3::OnCreateEntry(EntryImplV3* entry) {
+  EntryCell cell = index_->FindEntryCell(entry->GetHash(), entry->GetAddress());
+  DCHECK_EQ(cell.group(), ENTRY_NO_USE);
+  DCHECK(!entry->GetReuseCounter());
+  DCHECK(!entry->GetRefetchCounter());
+}
+
+void EvictionV3::OnResurrectEntry(EntryImplV3* entry) {
+  DCHECK(!lru_);
+  EntryCell cell = index_->FindEntryCell(entry->GetHash(), entry->GetAddress());
+  DCHECK_EQ(cell.group(), ENTRY_NO_USE);
+  int reuse_count = entry->GetReuseCounter();
+  int refetch_count = entry->GetRefetchCounter();
+
+  if (refetch_count < 256) {
+    refetch_count++;
+    entry->SetRefetchCounter(refetch_count);
+  }
+
+  if (refetch_count > kHighUse && reuse_count < kHighUse) {
+    reuse_count = kHighUse;
+  } else if (reuse_count < 256) {
+    reuse_count++;
+  }
+  entry->SetReuseCounter(reuse_count);
+
+  if (reuse_count >= kHighUse)
+    cell.set_group(ENTRY_HIGH_USE);
+  else
+    cell.set_group(ENTRY_LOW_USE);
+
+  if (reuse_count < 16)
+    cell.set_reuse(reuse_count);
+
+  index_->Save(&cell);
+}
+
+void EvictionV3::OnEvictEntryComplete() {
+  if (!test_mode_ && TrimCacheImpl())
+    return;
+
+  trimming_ = false;
+  Trace("*** Trim Cache end ***");
+
+  if (!callback_.is_null())
+    callback_.Run(net::OK);
+}
+
+void EvictionV3::SetTestMode() {
+  test_mode_ = true;
+}
+
+void EvictionV3::TrimDeletedList(bool empty) {
+  DCHECK(test_mode_ && !lru_);
+  TrimDeleted(empty);
+}
+
+// -----------------------------------------------------------------------
+
+void EvictionV3::PostDelayedTrim() {
+  // Prevent posting multiple tasks.
+  if (delay_trim_)
+    return;
+  delay_trim_ = true;
+  trim_delays_++;
+  MessageLoop::current()->PostDelayedTask(FROM_HERE,
+      base::Bind(&EvictionV3::DelayedTrim, ptr_factory_.GetWeakPtr()),
+      base::TimeDelta::FromMilliseconds(1000));
+}
+
+void EvictionV3::DelayedTrim() {
+  delay_trim_ = false;
+  if (trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded())
+    return PostDelayedTrim();
+
+  TrimCache();
+}
+
+bool EvictionV3::ShouldTrim() {
+  if (!FallingBehind(header_->num_bytes, max_size_) &&
+      trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded()) {
+    return false;
+  }
+
+  UMA_HISTOGRAM_COUNTS("DiskCache.TrimDelays", trim_delays_);
+  trim_delays_ = 0;
+  return true;
+}
+
+bool EvictionV3::ShouldTrimDeleted() {
+  int index_load = header_->num_entries * 100 / index_size_;
+
+  // If the index is not loaded, the deleted list will tend to double the size
+  // of the other lists 3 lists (40% of the total). Otherwise, all lists will be
+  // about the same size.
+  int max_length = (index_load < 25) ? header_->num_entries * 2 / 5 :
+                                       header_->num_entries / 4;
+  return false;//(!test_mode_ && header_->lru.sizes[Rankings::DELETED] > max_length);
+}
+
+int EvictionV3::EvictEntry(uint32 hash, Addr address) {
+  if (empty_) {
+    EntryImplV3* entry = backend_->GetOpenEntry(address);
+    if (entry) {
+      entry->Doom();
+      entry->Close();
+      return net::OK;
+    }
+  }
+
+  if (backend_->EvictEntry(hash, address))
+    return net::ERR_IO_PENDING;
+
+  return net::ERR_FAILED;
+}
+
+bool EvictionV3::TrimCacheImpl() {
+  int target_size = empty_ ? 0 : max_size_;
+
+  if (!cells_to_evict_ || cells_to_evict_->empty()) {
+    // See if we are done.
+    if (header_->num_bytes < target_size && !test_mode_)
+      return false;
+
+    EntryGroup group = ENTRY_RESERVED;
+    index_->GetOldest(&no_use_cells_, &low_use_cells_, &high_use_cells_);
+
+    int timestamps[ENTRY_HIGH_USE + 1];
+    timestamps[ENTRY_NO_USE] = GetTimestampForGoup(ENTRY_NO_USE);
+    timestamps[ENTRY_LOW_USE] = GetTimestampForGoup(ENTRY_LOW_USE);
+    timestamps[ENTRY_HIGH_USE] = GetTimestampForGoup(ENTRY_HIGH_USE);
+
+    if (CellIsOldEnough(no_use_cells_, 1))
+      group = ENTRY_NO_USE;
+    else if (CellIsOldEnough(low_use_cells_, 2))
+      group = ENTRY_LOW_USE;
+    else if (CellIsOldEnough(high_use_cells_, 4))
+      group = ENTRY_HIGH_USE;
+    else
+      group = SelectListByLength();
+    
+    if (group == ENTRY_NO_USE) {
+      cells_to_evict_ = &no_use_cells_;
+      low_use_cells_.clear();
+      high_use_cells_.clear();
+    } else if (group == ENTRY_LOW_USE) {
+      cells_to_evict_ = &low_use_cells_;
+      no_use_cells_.clear();
+      high_use_cells_.clear();
+    } else if (group == ENTRY_HIGH_USE) {
+      cells_to_evict_ = &high_use_cells_;
+      no_use_cells_.clear();
+      low_use_cells_.clear();
+    } else {
+      return false;
+    }
+
+    if (first_trim_) {
+      first_trim_ = false;
+      if (backend_->ShouldReportAgain()) {
+        int64 base_time = index_->header()->base_time;
+        CACHE_UMA(AGE, "TrimAge", 0,
+                  TimeFromTimestamp(timestamps[group], base_time));
+        ReportListStats(timestamps[ENTRY_NO_USE], timestamps[ENTRY_LOW_USE],
+                        timestamps[ENTRY_HIGH_USE]);
+      }
+
+      if (!(header_->flags & CACHE_EVICTED)) {
+        // This is the first entry that we have to evict, generate some noise.
+        backend_->FirstEviction();
+      }
+    }
+    
+
+    DCHECK(!cells_to_evict_->empty());
+  }
+
+  int rv = net::OK;
+  while (!cells_to_evict_->empty()) {
+    rv = EvictEntry(cells_to_evict_->back().hash,
+                    cells_to_evict_->back().address);
+    cells_to_evict_->pop_back();
+    if (rv != net::ERR_FAILED) {
+      if (!empty_)
+        backend_->OnEvent(Stats::TRIM_ENTRY);
+      if (rv == net::ERR_IO_PENDING)
+        break;
+    }
+  }
+
+  if (test_mode_ || rv != net::ERR_IO_PENDING)
+    return false;
+
+  return true;
+}
+
+// This is a minimal implementation that just discards the oldest nodes.
+// TODO(rvargas): Do something better here.
+void EvictionV3::TrimDeleted(bool empty) {
+  Trace("*** Trim Deleted ***");
+  if (backend_->disabled_)
+    return;
+
+  /*TimeTicks start = TimeTicks::Now();
+  Rankings::ScopedRankingsBlock node(rankings_);
+  Rankings::ScopedRankingsBlock next(
+    rankings_, rankings_->GetPrev(node.get(), Rankings::DELETED));
+  int deleted_entries = 0;
+  while (next.get() &&
+         (empty || (deleted_entries < 20 &&
+                    (TimeTicks::Now() - start).InMilliseconds() < 20))) {
+    node.reset(next.release());
+    next.reset(rankings_->GetPrev(node.get(), Rankings::DELETED));
+    if (RemoveDeletedNode(node.get()))
+      deleted_entries++;
+    if (test_mode_)
+      break;
+  }
+
+  if (deleted_entries && !empty && ShouldTrimDeleted()) {
+    MessageLoop::current()->PostTask(FROM_HERE,
+        base::Bind(&EvictionV3::TrimDeleted, ptr_factory_.GetWeakPtr(), false));
+  }
+
+  CACHE_UMA(AGE_MS, "TotalTrimDeletedTime", 0, start);
+  CACHE_UMA(COUNTS, "TrimDeletedItems", 0, deleted_entries);*/
+  Trace("*** Trim Deleted end ***");
+  return;
+}
+
+int EvictionV3::GetTimestampForGoup(int group) {
+  CellList* cells = NULL;
+  switch (group) {
+    case ENTRY_NO_USE:
+      cells = &no_use_cells_;
+      break;
+    case ENTRY_LOW_USE:
+      cells = &low_use_cells_;
+      break;
+    case ENTRY_HIGH_USE:
+      cells = &high_use_cells_;
+      break;
+    default:
+      NOTREACHED();
+  }
+  if (cells->empty())
+    return 0;
+  EntryCell cell = index_->FindEntryCell(cells->begin()->hash,
+                                         cells->begin()->address);
+  return cell.GetTimestamp();
+}
+
+bool EvictionV3::CellIsOldEnough(const CellList& cells, int multiplier) {
+  if (cells.empty())
+    return false;
+
+  if (lru_)
+    return true;
+
+  EntryCell cell = index_->FindEntryCell(cells.begin()->hash,
+                                         cells.begin()->address);
+
+  Time used = Time::FromInternalValue(header_->base_time) +
+              TimeDelta::FromMinutes(cell.GetTimestamp());
+
+  // If possible, we want to keep entries on each list at least kTargetTime
+  // hours. Each successive list on the enumeration has 2x the target time of
+  // the previous list.
+  return (backend_->GetCurrentTime() - used).InHours() >
+         kTargetTime * multiplier;
+}
+
+EntryGroup EvictionV3::SelectListByLength() {
+  int data_entries = header_->num_entries - header_->num_evicted_entries;
+
+  // Start by having each list to be roughly the same size.
+  if (header_->num_no_use_entries > data_entries / 3) {
+    DCHECK(!no_use_cells_.empty());
+    return ENTRY_NO_USE;
+  }
+
+  // Make sure that frequently used items are kept for a minimum time; we know
+  // that this entry is not older than its current target, but it must be at
+  // least older than the target for unused entries (kTargetTime), as long as we
+  // don't exhaust that list.
+
+  bool could_delete_no_used = header_->num_no_use_entries > data_entries / 10 ||
+                              (!no_use_cells_.empty() && empty_);
+
+  if (header_->num_low_use_entries > data_entries / 3 &&
+      (CellIsOldEnough(low_use_cells_, 1) || !could_delete_no_used)) {
+    DCHECK(!low_use_cells_.empty());
+    return ENTRY_LOW_USE;
+  }
+
+  if (header_->num_high_use_entries > data_entries / 3 &&
+      (CellIsOldEnough(high_use_cells_, 1) || !could_delete_no_used)) {
+    DCHECK(!high_use_cells_.empty());
+    return ENTRY_HIGH_USE;
+  }
+
+  if (could_delete_no_used)
+    return ENTRY_NO_USE;
+
+  if (!low_use_cells_.empty() && empty_)
+    return ENTRY_LOW_USE;
+
+  if (!high_use_cells_.empty() && empty_)
+    return ENTRY_HIGH_USE;
+
+  return ENTRY_RESERVED;
+}
+
+void EvictionV3::ReportListStats(int time1, int time2, int time3) {
+  if (lru_)
+    return;
+
+  int64 base_time = index_->header()->base_time;
+
+  if (time1)
+    CACHE_UMA(AGE, "NoUseAge", 0, TimeFromTimestamp(time1, base_time));
+
+  if (time2)
+    CACHE_UMA(AGE, "LowUseAge", 0, TimeFromTimestamp(time2, base_time));
+
+  if (time3)
+    CACHE_UMA(AGE, "HighUseAge", 0, TimeFromTimestamp(time3, base_time));
+}
+
+}  // namespace disk_cache