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