1868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 2868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 3868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// found in the LICENSE file. 4868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 5868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// The eviction policy is a very simple pure LRU, so the elements at the end of 6868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// the list are evicted until kCleanUpMargin free space is available. There is 7868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// only one list in use (Rankings::NO_USE), and elements are sent to the front 8868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// of the list whenever they are accessed. 9868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 10868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// The new (in-development) eviction policy adds re-use as a factor to evict 11868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// an entry. The story so far: 12868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 13868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Entries are linked on separate lists depending on how often they are used. 14868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// When we see an element for the first time, it goes to the NO_USE list; if 15868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// the object is reused later on, we move it to the LOW_USE list, until it is 16868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// used kHighUse times, at which point it is moved to the HIGH_USE list. 17868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Whenever an element is evicted, we move it to the DELETED list so that if the 18868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// element is accessed again, we remember the fact that it was already stored 19868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// and maybe in the future we don't evict that element. 20868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 21868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// When we have to evict an element, first we try to use the last element from 22868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// the NO_USE list, then we move to the LOW_USE and only then we evict an entry 23868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// from the HIGH_USE. We attempt to keep entries on the cache for at least 24868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// kTargetTime hours (with frequently accessed items stored for longer periods), 25868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// but if we cannot do that, we fall-back to keep each list roughly the same 26868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// size so that we have a chance to see an element again and move it to another 27868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// list. 28868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 29a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/eviction_v3.h" 30868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 31868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/bind.h" 32868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/compiler_specific.h" 33868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/logging.h" 349ab5563a3196760eb381d102cbb2bc0f7abc6a50Ben Murdoch#include "base/message_loop/message_loop.h" 355e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles)#include "base/strings/string_util.h" 36eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "base/time/time.h" 37a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/backend_impl_v3.h" 38a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/entry_impl_v3.h" 39a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/experiments.h" 40a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/histogram_macros_v3.h" 41a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/trace.h" 42a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#define CACHE_UMA_BACKEND_IMPL_OBJ backend_ 44868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 45868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)using base::Time; 46868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)using base::TimeTicks; 47868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 48868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)namespace { 49868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 50868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)const int kCleanUpMargin = 1024 * 1024; 515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#if defined(V3_NOT_JUST_YET_READY) 53868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)const int kHighUse = 10; // Reuse count to be on the HIGH_USE list. 54868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)const int kTargetTime = 24 * 7; // Time to be evicted (hours since last use). 55868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)const int kMaxDelayedTrims = 60; 565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#endif // defined(V3_NOT_JUST_YET_READY). 57868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 58868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)int LowWaterAdjust(int high_water) { 59868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (high_water < kCleanUpMargin) 60868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return 0; 61868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 62868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return high_water - kCleanUpMargin; 63868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 64868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#if defined(V3_NOT_JUST_YET_READY) 66868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)bool FallingBehind(int current_size, int max_size) { 67868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return current_size > max_size - kCleanUpMargin * 20; 68868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#endif // defined(V3_NOT_JUST_YET_READY). 70868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 71868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} // namespace 72868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 73868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)namespace disk_cache { 74868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 75868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// The real initialization happens during Init(), init_ is the only member that 76868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// has to be initialized here. 775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EvictionV3::EvictionV3() 78868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) : backend_(NULL), 795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) index_(NULL), 805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_(NULL), 81868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) init_(false), 82868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) ptr_factory_(this) { 83868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 84868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EvictionV3::~EvictionV3() { 86868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 87868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EvictionV3::Init(BackendImplV3* backend) { 89868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // We grab a bunch of info from the backend to make the code a little cleaner 90868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // when we're actually doing work. 91868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) backend_ = backend; 925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) index_ = &backend_->index_; 935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_ = index_->header(); 94868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) max_size_ = LowWaterAdjust(backend_->max_size_); 955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) lru_ = backend->lru_eviction_; 96868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) first_trim_ = true; 97868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) trimming_ = false; 98868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) delay_trim_ = false; 99868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) trim_delays_ = 0; 100868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) init_ = true; 101868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) test_mode_ = false; 102868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 103868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 1045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EvictionV3::Stop() { 105868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // It is possible for the backend initialization to fail, in which case this 106868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // object was never initialized... and there is nothing to do. 107868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!init_) 108868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return; 109868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 110868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // We want to stop further evictions, so let's pretend that we are busy from 111868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // this point on. 112868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) DCHECK(!trimming_); 113868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) trimming_ = true; 114868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) ptr_factory_.InvalidateWeakPtrs(); 115868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 116868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 1175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#if defined(V3_NOT_JUST_YET_READY) 1185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EvictionV3::TrimCache() { 119868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (backend_->disabled_ || trimming_) 120868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return; 121868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 122868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!empty && !ShouldTrim()) 123868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return PostDelayedTrim(); 124868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 125868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (new_eviction_) 126868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return TrimCacheV2(empty); 127868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 128868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Trace("*** Trim Cache ***"); 129868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) trimming_ = true; 130868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) TimeTicks start = TimeTicks::Now(); 131868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Rankings::ScopedRankingsBlock node(rankings_); 132868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Rankings::ScopedRankingsBlock next( 133868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_, rankings_->GetPrev(node.get(), Rankings::NO_USE)); 134868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int deleted_entries = 0; 135868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int target_size = empty ? 0 : max_size_; 136868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) while ((header_->num_bytes > target_size || test_mode_) && next.get()) { 137868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // The iterator could be invalidated within EvictEntry(). 138868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!next->HasData()) 139868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) break; 140868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) node.reset(next.release()); 141868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) next.reset(rankings_->GetPrev(node.get(), Rankings::NO_USE)); 142868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) { 143868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // This entry is not being used by anybody. 144868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // Do NOT use node as an iterator after this point. 145868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->TrackRankingsBlock(node.get(), false); 146868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (EvictEntry(node.get(), empty, Rankings::NO_USE) && !test_mode_) 147868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) deleted_entries++; 148868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 149868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!empty && test_mode_) 150868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) break; 151868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 152868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!empty && (deleted_entries > 20 || 153868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) (TimeTicks::Now() - start).InMilliseconds() > 20)) { 154868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) base::MessageLoop::current()->PostTask( 155868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) FROM_HERE, 1565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::Bind(&EvictionV3::TrimCache, ptr_factory_.GetWeakPtr(), false)); 157868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) break; 158868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 159868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 160868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 161868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (empty) { 162868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) CACHE_UMA(AGE_MS, "TotalClearTimeV1", 0, start); 163868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } else { 164868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) CACHE_UMA(AGE_MS, "TotalTrimTimeV1", 0, start); 165868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 166868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) CACHE_UMA(COUNTS, "TrimItemsV1", 0, deleted_entries); 167868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 168868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) trimming_ = false; 169868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Trace("*** Trim Cache end ***"); 170868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return; 171868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 172868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 1735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EvictionV3::OnOpenEntry(EntryImplV3* entry) { 174868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) EntryStore* info = entry->entry()->Data(); 175868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) DCHECK_EQ(ENTRY_NORMAL, info->state); 176868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 177868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (info->reuse_count < kint32max) { 178868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) info->reuse_count++; 179868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) entry->entry()->set_modified(); 180868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 181868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // We may need to move this to a new list. 182868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (1 == info->reuse_count) { 183868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->Remove(entry->rankings(), Rankings::NO_USE, true); 184868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->Insert(entry->rankings(), false, Rankings::LOW_USE); 185868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) entry->entry()->Store(); 186868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } else if (kHighUse == info->reuse_count) { 187868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->Remove(entry->rankings(), Rankings::LOW_USE, true); 188868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->Insert(entry->rankings(), false, Rankings::HIGH_USE); 189868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) entry->entry()->Store(); 190868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 191868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 192868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 193868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 1945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EvictionV3::OnCreateEntry(EntryImplV3* entry) { 195868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) EntryStore* info = entry->entry()->Data(); 196868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) switch (info->state) { 197868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) case ENTRY_NORMAL: { 198868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) DCHECK(!info->reuse_count); 199868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) DCHECK(!info->refetch_count); 200868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) break; 201868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) }; 202868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) case ENTRY_EVICTED: { 203868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (info->refetch_count < kint32max) 204868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) info->refetch_count++; 205868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 206868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (info->refetch_count > kHighUse && info->reuse_count < kHighUse) { 207868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) info->reuse_count = kHighUse; 208868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } else { 209868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) info->reuse_count++; 210868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 211868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) info->state = ENTRY_NORMAL; 212868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) entry->entry()->Store(); 213868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->Remove(entry->rankings(), Rankings::DELETED, true); 214868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) break; 215868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) }; 216868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) default: 217868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) NOTREACHED(); 218868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 219868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 220868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->Insert(entry->rankings(), true, GetListForEntryV2(entry)); 221868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 222868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 2235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EvictionV3::SetTestMode() { 224868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) test_mode_ = true; 225868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 226868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 2275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EvictionV3::TrimDeletedList(bool empty) { 228868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) DCHECK(test_mode_ && new_eviction_); 229868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) TrimDeleted(empty); 230868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 231868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 232868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// ----------------------------------------------------------------------- 233868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 2345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EvictionV3::PostDelayedTrim() { 235868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // Prevent posting multiple tasks. 236868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (delay_trim_) 237868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return; 238868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) delay_trim_ = true; 239868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) trim_delays_++; 240868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) base::MessageLoop::current()->PostDelayedTask( 241868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) FROM_HERE, 2425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::Bind(&EvictionV3::DelayedTrim, ptr_factory_.GetWeakPtr()), 243868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) base::TimeDelta::FromMilliseconds(1000)); 244868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 245868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 2465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EvictionV3::DelayedTrim() { 247868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) delay_trim_ = false; 248868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded()) 249868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return PostDelayedTrim(); 250868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 251868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) TrimCache(false); 252868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 253868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 2545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)bool EvictionV3::ShouldTrim() { 255868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!FallingBehind(header_->num_bytes, max_size_) && 256868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded()) { 257868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return false; 258868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 259868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 260868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) UMA_HISTOGRAM_COUNTS("DiskCache.TrimDelays", trim_delays_); 261868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) trim_delays_ = 0; 262868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return true; 263868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 264868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 2655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)bool EvictionV3::ShouldTrimDeleted() { 266868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int index_load = header_->num_entries * 100 / index_size_; 267868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 268868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // If the index is not loaded, the deleted list will tend to double the size 269868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // of the other lists 3 lists (40% of the total). Otherwise, all lists will be 270868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // about the same size. 271868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int max_length = (index_load < 25) ? header_->num_entries * 2 / 5 : 272868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) header_->num_entries / 4; 273868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return (!test_mode_ && header_->lru.sizes[Rankings::DELETED] > max_length); 274868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 275868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 276868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)bool Eviction::EvictEntry(CacheRankingsBlock* node, bool empty, 277868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Rankings::List list) { 2785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntryImplV3* entry = backend_->GetEnumeratedEntry(node, list); 279868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!entry) { 280868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Trace("NewEntry failed on Trim 0x%x", node->address().value()); 281868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return false; 282868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 283868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 284868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) ReportTrimTimes(entry); 285868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (empty || !new_eviction_) { 286868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) entry->DoomImpl(); 287868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } else { 288868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) entry->DeleteEntryData(false); 289868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) EntryStore* info = entry->entry()->Data(); 290868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) DCHECK_EQ(ENTRY_NORMAL, info->state); 291868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 292868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->Remove(entry->rankings(), GetListForEntryV2(entry), true); 293868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) info->state = ENTRY_EVICTED; 294868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) entry->entry()->Store(); 295868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->Insert(entry->rankings(), true, Rankings::DELETED); 296868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 297868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!empty) 298868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) backend_->OnEvent(Stats::TRIM_ENTRY); 299868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 300868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) entry->Release(); 301868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 302868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return true; 303868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 304868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 3055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EvictionV3::TrimCacheV2(bool empty) { 306868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Trace("*** Trim Cache ***"); 307868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) trimming_ = true; 308868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) TimeTicks start = TimeTicks::Now(); 309868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 310868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) const int kListsToSearch = 3; 311868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Rankings::ScopedRankingsBlock next[kListsToSearch]; 312868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int list = Rankings::LAST_ELEMENT; 313868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 314868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // Get a node from each list. 315868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) for (int i = 0; i < kListsToSearch; i++) { 316868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) bool done = false; 317868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) next[i].set_rankings(rankings_); 318868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (done) 319868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) continue; 320868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) next[i].reset(rankings_->GetPrev(NULL, static_cast<Rankings::List>(i))); 321868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!empty && NodeIsOldEnough(next[i].get(), i)) { 322868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) list = static_cast<Rankings::List>(i); 323868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) done = true; 324868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 325868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 326868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 327868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // If we are not meeting the time targets lets move on to list length. 328868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!empty && Rankings::LAST_ELEMENT == list) 329868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) list = SelectListByLength(next); 330868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 331868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (empty) 332868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) list = 0; 333868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 334868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Rankings::ScopedRankingsBlock node(rankings_); 335868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int deleted_entries = 0; 336868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int target_size = empty ? 0 : max_size_; 337868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 338868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) for (; list < kListsToSearch; list++) { 339868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) while ((header_->num_bytes > target_size || test_mode_) && 340868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) next[list].get()) { 341868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // The iterator could be invalidated within EvictEntry(). 342868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!next[list]->HasData()) 343868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) break; 344868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) node.reset(next[list].release()); 345868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) next[list].reset(rankings_->GetPrev(node.get(), 346868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) static_cast<Rankings::List>(list))); 347868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) { 348868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // This entry is not being used by anybody. 349868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // Do NOT use node as an iterator after this point. 350868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->TrackRankingsBlock(node.get(), false); 351868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (EvictEntry(node.get(), empty, static_cast<Rankings::List>(list))) 352868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) deleted_entries++; 353868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 354868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!empty && test_mode_) 355868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) break; 356868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 357868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!empty && (deleted_entries > 20 || 358868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) (TimeTicks::Now() - start).InMilliseconds() > 20)) { 359868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) base::MessageLoop::current()->PostTask( 360868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) FROM_HERE, 361868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) base::Bind(&Eviction::TrimCache, ptr_factory_.GetWeakPtr(), false)); 362868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) break; 363868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 364868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 365868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!empty) 366868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) list = kListsToSearch; 367868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 368868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 369868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (empty) { 370868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) TrimDeleted(true); 371868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } else if (ShouldTrimDeleted()) { 372868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) base::MessageLoop::current()->PostTask( 373868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) FROM_HERE, 3745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::Bind(&EvictionV3::TrimDeleted, ptr_factory_.GetWeakPtr(), empty)); 375868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 376868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 377868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (empty) { 378868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) CACHE_UMA(AGE_MS, "TotalClearTimeV2", 0, start); 379868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } else { 380868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) CACHE_UMA(AGE_MS, "TotalTrimTimeV2", 0, start); 381868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 382868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) CACHE_UMA(COUNTS, "TrimItemsV2", 0, deleted_entries); 383868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 384868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Trace("*** Trim Cache end ***"); 385868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) trimming_ = false; 386868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return; 387868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 388868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 389868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// This is a minimal implementation that just discards the oldest nodes. 390868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// TODO(rvargas): Do something better here. 3915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EvictionV3::TrimDeleted(bool empty) { 392868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Trace("*** Trim Deleted ***"); 393868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (backend_->disabled_) 394868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return; 395868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 396868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) TimeTicks start = TimeTicks::Now(); 397868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Rankings::ScopedRankingsBlock node(rankings_); 398868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Rankings::ScopedRankingsBlock next( 399868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_, rankings_->GetPrev(node.get(), Rankings::DELETED)); 400868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int deleted_entries = 0; 401868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) while (next.get() && 402868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) (empty || (deleted_entries < 20 && 403868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) (TimeTicks::Now() - start).InMilliseconds() < 20))) { 404868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) node.reset(next.release()); 405868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) next.reset(rankings_->GetPrev(node.get(), Rankings::DELETED)); 406868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (RemoveDeletedNode(node.get())) 407868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) deleted_entries++; 408868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (test_mode_) 409868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) break; 410868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 411868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 412868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (deleted_entries && !empty && ShouldTrimDeleted()) { 413868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) base::MessageLoop::current()->PostTask( 414868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) FROM_HERE, 4155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::Bind(&EvictionV3::TrimDeleted, ptr_factory_.GetWeakPtr(), false)); 416868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 417868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 418868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) CACHE_UMA(AGE_MS, "TotalTrimDeletedTime", 0, start); 419868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) CACHE_UMA(COUNTS, "TrimDeletedItems", 0, deleted_entries); 420868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Trace("*** Trim Deleted end ***"); 421868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return; 422868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 423868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 4245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EvictionV3::ReportTrimTimes(EntryImplV3* entry) { 425868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (first_trim_) { 426868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) first_trim_ = false; 427868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (backend_->ShouldReportAgain()) { 428868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) CACHE_UMA(AGE, "TrimAge", 0, entry->GetLastUsed()); 429868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) ReportListStats(); 430868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 431868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 432868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (header_->lru.filled) 433868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return; 434868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 435868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) header_->lru.filled = 1; 436868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 437868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (header_->create_time) { 438868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // This is the first entry that we have to evict, generate some noise. 439868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) backend_->FirstEviction(); 440868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } else { 441868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // This is an old file, but we may want more reports from this user so 442868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // lets save some create_time. 443868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Time::Exploded old = {0}; 444868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) old.year = 2009; 445868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) old.month = 3; 446868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) old.day_of_month = 1; 447868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) header_->create_time = Time::FromLocalExploded(old).ToInternalValue(); 448868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 449868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 450868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 451868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 4525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)bool EvictionV3::NodeIsOldEnough(CacheRankingsBlock* node, int list) { 453868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!node) 454868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return false; 455868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 456868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // If possible, we want to keep entries on each list at least kTargetTime 457868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // hours. Each successive list on the enumeration has 2x the target time of 458868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // the previous list. 459868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Time used = Time::FromInternalValue(node->Data()->last_used); 460868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int multiplier = 1 << list; 461868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return (Time::Now() - used).InHours() > kTargetTime * multiplier; 462868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 463868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 4645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)int EvictionV3::SelectListByLength(Rankings::ScopedRankingsBlock* next) { 465868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int data_entries = header_->num_entries - 466868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) header_->lru.sizes[Rankings::DELETED]; 467868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // Start by having each list to be roughly the same size. 468868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (header_->lru.sizes[0] > data_entries / 3) 469868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return 0; 470868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 471868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int list = (header_->lru.sizes[1] > data_entries / 3) ? 1 : 2; 472868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 473868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // Make sure that frequently used items are kept for a minimum time; we know 474868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // that this entry is not older than its current target, but it must be at 475868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // least older than the target for list 0 (kTargetTime), as long as we don't 476868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // exhaust list 0. 477868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!NodeIsOldEnough(next[list].get(), 0) && 478868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) header_->lru.sizes[0] > data_entries / 10) 479868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) list = 0; 480868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 481868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return list; 482868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 483868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 4845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EvictionV3::ReportListStats() { 485868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!new_eviction_) 486868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return; 487868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 488868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Rankings::ScopedRankingsBlock last1(rankings_, 489868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->GetPrev(NULL, Rankings::NO_USE)); 490868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Rankings::ScopedRankingsBlock last2(rankings_, 491868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->GetPrev(NULL, Rankings::LOW_USE)); 492868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Rankings::ScopedRankingsBlock last3(rankings_, 493868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->GetPrev(NULL, Rankings::HIGH_USE)); 494868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Rankings::ScopedRankingsBlock last4(rankings_, 495868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) rankings_->GetPrev(NULL, Rankings::DELETED)); 496868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 497868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (last1.get()) 498868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) CACHE_UMA(AGE, "NoUseAge", 0, 499868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Time::FromInternalValue(last1.get()->Data()->last_used)); 500868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (last2.get()) 501868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) CACHE_UMA(AGE, "LowUseAge", 0, 502868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Time::FromInternalValue(last2.get()->Data()->last_used)); 503868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (last3.get()) 504868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) CACHE_UMA(AGE, "HighUseAge", 0, 505868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Time::FromInternalValue(last3.get()->Data()->last_used)); 506868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (last4.get()) 507868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) CACHE_UMA(AGE, "DeletedAge", 0, 508868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Time::FromInternalValue(last4.get()->Data()->last_used)); 509868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 5105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#endif // defined(V3_NOT_JUST_YET_READY). 511868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 512868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} // namespace disk_cache 513