10a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen// Copyright (c) 2011 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 103345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick// The new (in-development) eviction policy adds 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 313345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick#include "base/compiler_specific.h" 32c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "base/logging.h" 33c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "base/message_loop.h" 34c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "base/string_util.h" 35c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "base/time.h" 36c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "net/disk_cache/backend_impl.h" 37c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "net/disk_cache/entry_impl.h" 383345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick#include "net/disk_cache/experiments.h" 39c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "net/disk_cache/histogram_macros.h" 40c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "net/disk_cache/trace.h" 41c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 42c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottusing base::Time; 43c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochusing base::TimeTicks; 44c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 45c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottnamespace { 46c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 47c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottconst int kCleanUpMargin = 1024 * 1024; 48c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottconst int kHighUse = 10; // Reuse count to be on the HIGH_USE list. 49c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottconst int kTargetTime = 24 * 7; // Time to be evicted (hours since last use). 50c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochconst int kMaxDelayedTrims = 60; 51c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 52c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottint LowWaterAdjust(int high_water) { 53c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (high_water < kCleanUpMargin) 54c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return 0; 55c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 56c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return high_water - kCleanUpMargin; 57c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 58c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 59c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} // namespace 60c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 61c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottnamespace disk_cache { 62c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 633345a6884c488ff3a535c2c9acdd33d74b37e311Iain MerrickEviction::Eviction() 643345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick : backend_(NULL), 653345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick init_(false), 663345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick ALLOW_THIS_IN_INITIALIZER_LIST(factory_(this)) { 673345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick} 683345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 693345a6884c488ff3a535c2c9acdd33d74b37e311Iain MerrickEviction::~Eviction() { 703345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick} 713345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 72c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::Init(BackendImpl* backend) { 73c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // We grab a bunch of info from the backend to make the code a little cleaner 74c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // when we're actually doing work. 75c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_ = backend; 76c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_ = &backend->rankings_; 77c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott header_ = &backend_->data_->header; 78c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott max_size_ = LowWaterAdjust(backend_->max_size_); 79c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott new_eviction_ = backend->new_eviction_; 80c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott first_trim_ = true; 81c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott trimming_ = false; 82c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott delay_trim_ = false; 83c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch trim_delays_ = 0; 84c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch init_ = true; 8572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen test_mode_ = false; 863345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick in_experiment_ = (header_->experiment == EXPERIMENT_DELETED_LIST_IN); 87c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 88c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 89c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid Eviction::Stop() { 90c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // It is possible for the backend initialization to fail, in which case this 91c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // object was never initialized... and there is nothing to do. 92c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!init_) 93c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return; 94c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 95c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // We want to stop further evictions, so let's pretend that we are busy from 96c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // this point on. 97c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch DCHECK(!trimming_); 98c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch trimming_ = true; 993345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick factory_.RevokeAll(); 100c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 101c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 102c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid Eviction::TrimCache(bool empty) { 103c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (backend_->disabled_ || trimming_) 104c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 105c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 106c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!empty && !ShouldTrim()) 107c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return PostDelayedTrim(); 108c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 109c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (new_eviction_) 110c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return TrimCacheV2(empty); 111c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 112c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Trace("*** Trim Cache ***"); 113c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott trimming_ = true; 114c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch TimeTicks start = TimeTicks::Now(); 115c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Rankings::ScopedRankingsBlock node(rankings_); 116c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Rankings::ScopedRankingsBlock next(rankings_, 117c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->GetPrev(node.get(), Rankings::NO_USE)); 118c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int target_size = empty ? 0 : max_size_; 119ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen while ((header_->num_bytes > target_size || test_mode_) && next.get()) { 120c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // The iterator could be invalidated within EvictEntry(). 121c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!next->HasData()) 122c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 123c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node.reset(next.release()); 124c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.reset(rankings_->GetPrev(node.get(), Rankings::NO_USE)); 125c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) { 126c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // This entry is not being used by anybody. 127c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Do NOT use node as an iterator after this point. 128c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->TrackRankingsBlock(node.get(), false); 129ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen if (!EvictEntry(node.get(), empty, Rankings::NO_USE) && !test_mode_) 130c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott continue; 131c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 132c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!empty) { 133c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_->OnEvent(Stats::TRIM_ENTRY); 13472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (test_mode_) 13572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen break; 136c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 137c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if ((TimeTicks::Now() - start).InMilliseconds() > 20) { 138c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott MessageLoop::current()->PostTask(FROM_HERE, 139c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott factory_.NewRunnableMethod(&Eviction::TrimCache, false)); 140c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 141c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 142c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 143c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 144c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 145c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 146c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (empty) { 147c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch CACHE_UMA(AGE_MS, "TotalClearTimeV1", 0, start); 148c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } else { 149c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch CACHE_UMA(AGE_MS, "TotalTrimTimeV1", backend_->GetSizeGroup(), start); 150c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 151c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 152c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott trimming_ = false; 153c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Trace("*** Trim Cache end ***"); 154c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 155c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 156c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 157c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::UpdateRank(EntryImpl* entry, bool modified) { 158c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (new_eviction_) 159c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return UpdateRankV2(entry, modified); 160c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 161c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->UpdateRank(entry->rankings(), modified, GetListForEntry(entry)); 162c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 163c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 164c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::OnOpenEntry(EntryImpl* entry) { 165c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (new_eviction_) 166c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return OnOpenEntryV2(entry); 167c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 168c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 169c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::OnCreateEntry(EntryImpl* entry) { 170c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (new_eviction_) 171c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return OnCreateEntryV2(entry); 172c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 173c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->Insert(entry->rankings(), true, GetListForEntry(entry)); 174c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 175c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 176c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::OnDoomEntry(EntryImpl* entry) { 177c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (new_eviction_) 178c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return OnDoomEntryV2(entry); 179c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 180ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen if (entry->LeaveRankingsBehind()) 181ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen return; 182ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen 183ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen rankings_->Remove(entry->rankings(), GetListForEntry(entry), true); 184c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 185c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 186c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::OnDestroyEntry(EntryImpl* entry) { 187c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (new_eviction_) 188c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return OnDestroyEntryV2(entry); 189c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 190c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 19172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsenvoid Eviction::SetTestMode() { 19272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen test_mode_ = true; 19372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen} 19472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 19572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsenvoid Eviction::TrimDeletedList(bool empty) { 19672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen DCHECK(test_mode_ && new_eviction_); 19772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen TrimDeleted(empty); 19872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen} 19972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 200c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::PostDelayedTrim() { 201c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Prevent posting multiple tasks. 202c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (delay_trim_) 203c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 204c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott delay_trim_ = true; 205c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch trim_delays_++; 206c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott MessageLoop::current()->PostDelayedTask(FROM_HERE, 207c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott factory_.NewRunnableMethod(&Eviction::DelayedTrim), 1000); 208c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 209c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 210c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::DelayedTrim() { 211c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott delay_trim_ = false; 212c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded()) 213c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return PostDelayedTrim(); 214c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 215c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TrimCache(false); 216c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 217c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 218c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool Eviction::ShouldTrim() { 219c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded()) 220c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 221c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 222c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch UMA_HISTOGRAM_COUNTS("DiskCache.TrimDelays", trim_delays_); 223c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch trim_delays_ = 0; 224c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 225c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 226c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 227c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::ReportTrimTimes(EntryImpl* entry) { 228c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (first_trim_) { 229c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott first_trim_ = false; 230c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (backend_->ShouldReportAgain()) { 231c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CACHE_UMA(AGE, "TrimAge", 0, entry->GetLastUsed()); 232c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ReportListStats(); 233c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 234c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 235c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (header_->lru.filled) 236c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 237c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 238c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott header_->lru.filled = 1; 239c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 240c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (header_->create_time) { 241c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // This is the first entry that we have to evict, generate some noise. 242c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_->FirstEviction(); 243c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else { 244c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // This is an old file, but we may want more reports from this user so 245c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // lets save some create_time. 246c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Time::Exploded old = {0}; 247c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott old.year = 2009; 248c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott old.month = 3; 249c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott old.day_of_month = 1; 250c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott header_->create_time = Time::FromLocalExploded(old).ToInternalValue(); 251c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 252c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 253c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 254c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 255c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottRankings::List Eviction::GetListForEntry(EntryImpl* entry) { 256c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return Rankings::NO_USE; 257c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 258c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 259ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsenbool Eviction::EvictEntry(CacheRankingsBlock* node, bool empty, 260ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen Rankings::List list) { 261ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen EntryImpl* entry = backend_->GetEnumeratedEntry(node, list); 262c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!entry) { 263c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Trace("NewEntry failed on Trim 0x%x", node->address().value()); 264c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 265c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 266c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 267c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ReportTrimTimes(entry); 268c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (empty || !new_eviction_) { 269c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch entry->DoomImpl(); 270c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else { 271c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott entry->DeleteEntryData(false); 272c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EntryStore* info = entry->entry()->Data(); 273c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(ENTRY_NORMAL == info->state); 274c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 275ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen rankings_->Remove(entry->rankings(), GetListForEntryV2(entry), true); 276c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott info->state = ENTRY_EVICTED; 277c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott entry->entry()->Store(); 278c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->Insert(entry->rankings(), true, Rankings::DELETED); 279c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_->OnEvent(Stats::TRIM_ENTRY); 280c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 281c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott entry->Release(); 282c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 283c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 284c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 285c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 286c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// ----------------------------------------------------------------------- 287c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 288c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::TrimCacheV2(bool empty) { 289c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Trace("*** Trim Cache ***"); 290c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott trimming_ = true; 291c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch TimeTicks start = TimeTicks::Now(); 292c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 293c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const int kListsToSearch = 3; 294c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Rankings::ScopedRankingsBlock next[kListsToSearch]; 295c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int list = Rankings::LAST_ELEMENT; 296c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 297c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Get a node from each list. 298c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < kListsToSearch; i++) { 299c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bool done = false; 300c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next[i].set_rankings(rankings_); 301c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (done) 302c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott continue; 303c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next[i].reset(rankings_->GetPrev(NULL, static_cast<Rankings::List>(i))); 304c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!empty && NodeIsOldEnough(next[i].get(), i)) { 305c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott list = static_cast<Rankings::List>(i); 306c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott done = true; 307c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 308c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 309c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 310c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // If we are not meeting the time targets lets move on to list length. 3110a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen if (!empty && Rankings::LAST_ELEMENT == list) 3120a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen list = SelectListByLength(next); 313c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 314c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (empty) 315c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott list = 0; 316c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 317c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Rankings::ScopedRankingsBlock node(rankings_); 318c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 319c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int target_size = empty ? 0 : max_size_; 320c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (; list < kListsToSearch; list++) { 321ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen while ((header_->num_bytes > target_size || test_mode_) && 322ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen next[list].get()) { 323c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // The iterator could be invalidated within EvictEntry(). 324c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!next[list]->HasData()) 325c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 326c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node.reset(next[list].release()); 327c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next[list].reset(rankings_->GetPrev(node.get(), 328c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott static_cast<Rankings::List>(list))); 329c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) { 330c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // This entry is not being used by anybody. 331c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Do NOT use node as an iterator after this point. 332c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->TrackRankingsBlock(node.get(), false); 333ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen if (!EvictEntry(node.get(), empty, static_cast<Rankings::List>(list)) && 334ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen !test_mode_) 335c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott continue; 336c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 33772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (!empty && test_mode_) 33872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen break; 33972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 340c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!empty && (TimeTicks::Now() - start).InMilliseconds() > 20) { 341c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott MessageLoop::current()->PostTask(FROM_HERE, 342c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott factory_.NewRunnableMethod(&Eviction::TrimCache, false)); 343c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 344c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 345c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 346c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 347c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!empty) 348c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott list = kListsToSearch; 349c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 350c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 351c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (empty) { 352c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TrimDeleted(true); 35372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } else if (header_->lru.sizes[Rankings::DELETED] > header_->num_entries / 4 && 35472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen !test_mode_) { 355c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott MessageLoop::current()->PostTask(FROM_HERE, 356c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott factory_.NewRunnableMethod(&Eviction::TrimDeleted, empty)); 357c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 358c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 359c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (empty) { 360c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch CACHE_UMA(AGE_MS, "TotalClearTimeV2", 0, start); 361c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } else { 362c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch CACHE_UMA(AGE_MS, "TotalTrimTimeV2", backend_->GetSizeGroup(), start); 363c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 364c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 365c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Trace("*** Trim Cache end ***"); 366c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott trimming_ = false; 367c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 368c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 369c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 370c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::UpdateRankV2(EntryImpl* entry, bool modified) { 371c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->UpdateRank(entry->rankings(), modified, GetListForEntryV2(entry)); 372c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 373c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 374c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::OnOpenEntryV2(EntryImpl* entry) { 375c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EntryStore* info = entry->entry()->Data(); 376c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(ENTRY_NORMAL == info->state); 377c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 378c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (info->reuse_count < kint32max) { 379c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott info->reuse_count++; 380c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott entry->entry()->set_modified(); 381c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 382c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // We may need to move this to a new list. 383c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (1 == info->reuse_count) { 384ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen rankings_->Remove(entry->rankings(), Rankings::NO_USE, true); 385c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->Insert(entry->rankings(), false, Rankings::LOW_USE); 386c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott entry->entry()->Store(); 387c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else if (kHighUse == info->reuse_count) { 388ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen rankings_->Remove(entry->rankings(), Rankings::LOW_USE, true); 389c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->Insert(entry->rankings(), false, Rankings::HIGH_USE); 390c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott entry->entry()->Store(); 391c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 392c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 393c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 394c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 395c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::OnCreateEntryV2(EntryImpl* entry) { 396c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EntryStore* info = entry->entry()->Data(); 397c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (info->state) { 398c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ENTRY_NORMAL: { 399c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(!info->reuse_count); 400c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(!info->refetch_count); 401c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 402c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott }; 403c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ENTRY_EVICTED: { 404c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (info->refetch_count < kint32max) 405c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott info->refetch_count++; 406c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 407c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (info->refetch_count > kHighUse && info->reuse_count < kHighUse) { 408c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott info->reuse_count = kHighUse; 409c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else { 410c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott info->reuse_count++; 411c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 412c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott info->state = ENTRY_NORMAL; 413c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott entry->entry()->Store(); 414ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen rankings_->Remove(entry->rankings(), Rankings::DELETED, true); 415c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 416c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott }; 417c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 418c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott NOTREACHED(); 419c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 420c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 421c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->Insert(entry->rankings(), true, GetListForEntryV2(entry)); 422c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 423c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 424c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::OnDoomEntryV2(EntryImpl* entry) { 425c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EntryStore* info = entry->entry()->Data(); 426c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (ENTRY_NORMAL != info->state) 427c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 428c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 429ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen if (entry->LeaveRankingsBehind()) { 430ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen info->state = ENTRY_DOOMED; 431ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen entry->entry()->Store(); 432ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen return; 433ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen } 434ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen 435ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen rankings_->Remove(entry->rankings(), GetListForEntryV2(entry), true); 436c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 437c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott info->state = ENTRY_DOOMED; 438c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott entry->entry()->Store(); 439c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->Insert(entry->rankings(), true, Rankings::DELETED); 440c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 441c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 442c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::OnDestroyEntryV2(EntryImpl* entry) { 443ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen if (entry->LeaveRankingsBehind()) 444ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen return; 445ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen 446ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen rankings_->Remove(entry->rankings(), Rankings::DELETED, true); 447c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 448c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 449c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottRankings::List Eviction::GetListForEntryV2(EntryImpl* entry) { 450c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EntryStore* info = entry->entry()->Data(); 451c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(ENTRY_NORMAL == info->state); 452c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 453c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!info->reuse_count) 454c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return Rankings::NO_USE; 455c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 456c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (info->reuse_count < kHighUse) 457c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return Rankings::LOW_USE; 458c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 459c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return Rankings::HIGH_USE; 460c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 461c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 462c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// This is a minimal implementation that just discards the oldest nodes. 463c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// TODO(rvargas): Do something better here. 464c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::TrimDeleted(bool empty) { 465c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Trace("*** Trim Deleted ***"); 466c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (backend_->disabled_) 467c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 468c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 469c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch TimeTicks start = TimeTicks::Now(); 470c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Rankings::ScopedRankingsBlock node(rankings_); 471c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Rankings::ScopedRankingsBlock next(rankings_, 472c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->GetPrev(node.get(), Rankings::DELETED)); 473c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bool deleted = false; 474ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen while (next.get() && 475ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen (empty || (TimeTicks::Now() - start).InMilliseconds() < 20)) { 476c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node.reset(next.release()); 477c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.reset(rankings_->GetPrev(node.get(), Rankings::DELETED)); 478c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch deleted |= RemoveDeletedNode(node.get()); 47972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (test_mode_) 48072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen break; 481c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 482c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 4833345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick // Normally we use 25% for each list. The experiment doubles the number of 4843345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick // deleted entries, so the total number of entries increases by 25%. Using 4853345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick // 40% of that value for deleted entries leaves the size of the other three 4863345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick // lists intact. 4873345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick int max_length = in_experiment_ ? header_->num_entries * 2 / 5 : 4883345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick header_->num_entries / 4; 48972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (deleted && !empty && !test_mode_ && 49072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen header_->lru.sizes[Rankings::DELETED] > max_length) { 491c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott MessageLoop::current()->PostTask(FROM_HERE, 492c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott factory_.NewRunnableMethod(&Eviction::TrimDeleted, false)); 49372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } 494c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 495c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CACHE_UMA(AGE_MS, "TotalTrimDeletedTime", 0, start); 496c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Trace("*** Trim Deleted end ***"); 497c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 498c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 499c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 500c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Eviction::RemoveDeletedNode(CacheRankingsBlock* node) { 501ae2796cabb52f6a27c50818b78107d3ebc858e0cKristian Monsen EntryImpl* entry = backend_->GetEnumeratedEntry(node, Rankings::DELETED); 50272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (!entry) { 503c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Trace("NewEntry failed on Trim 0x%x", node->address().value()); 504c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 505c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 506c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 507c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bool doomed = (entry->entry()->Data()->state == ENTRY_DOOMED); 508c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott entry->entry()->Data()->state = ENTRY_DOOMED; 509c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch entry->DoomImpl(); 510c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott entry->Release(); 511c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return !doomed; 512c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 513c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 514c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Eviction::NodeIsOldEnough(CacheRankingsBlock* node, int list) { 515c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!node) 516c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 517c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 518c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // If possible, we want to keep entries on each list at least kTargetTime 519c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // hours. Each successive list on the enumeration has 2x the target time of 520c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // the previous list. 521c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Time used = Time::FromInternalValue(node->Data()->last_used); 522c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int multiplier = 1 << list; 523c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return (Time::Now() - used).InHours() > kTargetTime * multiplier; 524c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 525c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 5260a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsenint Eviction::SelectListByLength(Rankings::ScopedRankingsBlock* next) { 527c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int data_entries = header_->num_entries - 528c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott header_->lru.sizes[Rankings::DELETED]; 529c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Start by having each list to be roughly the same size. 530c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (header_->lru.sizes[0] > data_entries / 3) 531c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return 0; 5320a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen 5330a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen int list = (header_->lru.sizes[1] > data_entries / 3) ? 1 : 2; 5340a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen 5350a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen // Make sure that frequently used items are kept for a minimum time; we know 5360a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen // that this entry is not older than its current target, but it must be at 5370a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen // least older than the target for list 0 (kTargetTime), as long as we don't 5380a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen // exhaust list 0. 5390a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen if (!NodeIsOldEnough(next[list].get(), 0) && 5400a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen header_->lru.sizes[0] > data_entries / 10) 5410a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen list = 0; 5420a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen 5430a9239c3bca6d8a7147c80243b17a02340fe6d31Kristian Monsen return list; 544c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 545c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 546c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Eviction::ReportListStats() { 547c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!new_eviction_) 548c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 549c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 550c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Rankings::ScopedRankingsBlock last1(rankings_, 551c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->GetPrev(NULL, Rankings::NO_USE)); 552c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Rankings::ScopedRankingsBlock last2(rankings_, 553c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->GetPrev(NULL, Rankings::LOW_USE)); 554c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Rankings::ScopedRankingsBlock last3(rankings_, 555c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->GetPrev(NULL, Rankings::HIGH_USE)); 556c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Rankings::ScopedRankingsBlock last4(rankings_, 557c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings_->GetPrev(NULL, Rankings::DELETED)); 558c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 559c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (last1.get()) 560c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CACHE_UMA(AGE, "NoUseAge", 0, 561c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Time::FromInternalValue(last1.get()->Data()->last_used)); 562c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (last2.get()) 563c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CACHE_UMA(AGE, "LowUseAge", 0, 564c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Time::FromInternalValue(last2.get()->Data()->last_used)); 565c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (last3.get()) 566c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CACHE_UMA(AGE, "HighUseAge", 0, 567c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Time::FromInternalValue(last3.get()->Data()->last_used)); 568c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (last4.get()) 569c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CACHE_UMA(AGE, "DeletedAge", 0, 570c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Time::FromInternalValue(last4.get()->Data()->last_used)); 571c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 572c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 573c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} // namespace disk_cache 574