eviction.cc | Explore in Territory

// Copyright 2012 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/40284755): Remove this and spanify to fix the errors.
#pragma allow_unsafe_buffers
#endif

// 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/blockfile/eviction.h"

#include <stdint.h>

#include <limits>

#include "base/check_op.h"
#include "base/compiler_specific.h"
#include "base/functional/bind.h"
#include "base/location.h"
#include "base/metrics/histogram_macros.h"
#include "base/notreached.h"
#include "base/strings/string_util.h"
#include "base/task/single_thread_task_runner.h"
#include "base/time/time.h"
#include "net/base/tracing.h"
#include "net/disk_cache/blockfile/backend_impl.h"
#include "net/disk_cache/blockfile/disk_format.h"
#include "net/disk_cache/blockfile/entry_impl.h"
#include "net/disk_cache/blockfile/experiments.h"

Time;
TimeTicks;

namespace {

const int kCleanUpMargin = …;
const int kHighUse = …;  // Reuse count to be on the HIGH_USE list.
const int kTargetTime = …;  // Time to be evicted (hours since last use).
const int kMaxDelayedTrims = …;

int LowWaterAdjust(int high_water) { … }

bool FallingBehind(int current_size, int max_size) { … }

}  // namespace

namespace disk_cache {

// The real initialization happens during Init(), init_ is the only member that
// has to be initialized here.
Eviction::Eviction() = default;

Eviction::~Eviction() = default;

void Eviction::Init(BackendImpl* backend) { … }

void Eviction::Stop() { … }

void Eviction::TrimCache(bool empty) { … }

void Eviction::UpdateRank(EntryImpl* entry, bool modified) { … }

void Eviction::OnOpenEntry(EntryImpl* entry) { … }

void Eviction::OnCreateEntry(EntryImpl* entry) { … }

void Eviction::OnDoomEntry(EntryImpl* entry) { … }

void Eviction::OnDestroyEntry(EntryImpl* entry) { … }

void Eviction::SetTestMode() { … }

void Eviction::TrimDeletedList(bool empty) { … }

void Eviction::PostDelayedTrim() { … }

void Eviction::DelayedTrim() { … }

bool Eviction::ShouldTrim() { … }

bool Eviction::ShouldTrimDeleted() { … }

void Eviction::ReportTrimTimes(EntryImpl* entry) { … }

Rankings::List Eviction::GetListForEntry(EntryImpl* entry) { … }

bool Eviction::EvictEntry(CacheRankingsBlock* node, bool empty,
                          Rankings::List list) { … }

// -----------------------------------------------------------------------

void Eviction::TrimCacheV2(bool empty) { … }

void Eviction::UpdateRankV2(EntryImpl* entry, bool modified) { … }

void Eviction::OnOpenEntryV2(EntryImpl* entry) { … }

void Eviction::OnCreateEntryV2(EntryImpl* entry) { … }

void Eviction::OnDoomEntryV2(EntryImpl* entry) { … }

void Eviction::OnDestroyEntryV2(EntryImpl* entry) { … }

Rankings::List Eviction::GetListForEntryV2(EntryImpl* entry) { … }

// This is a minimal implementation that just discards the oldest nodes.
// TODO(rvargas): Do something better here.
void Eviction::TrimDeleted(bool empty) { … }

bool Eviction::RemoveDeletedNode(CacheRankingsBlock* node) { … }

bool Eviction::NodeIsOldEnough(CacheRankingsBlock* node, int list) { … }

int Eviction::SelectListByLength(Rankings::ScopedRankingsBlock* next) { … }

}  // namespace disk_cache
chromium/net/disk_cache/blockfile/eviction.cc
