15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The eviction policy is a very simple pure LRU, so the elements at the end of 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the list are evicted until kCleanUpMargin free space is available. There is 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// only one list in use (Rankings::NO_USE), and elements are sent to the front 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// of the list whenever they are accessed. 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The new (in-development) eviction policy adds re-use as a factor to evict 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// an entry. The story so far: 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Entries are linked on separate lists depending on how often they are used. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// When we see an element for the first time, it goes to the NO_USE list; if 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the object is reused later on, we move it to the LOW_USE list, until it is 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// used kHighUse times, at which point it is moved to the HIGH_USE list. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Whenever an element is evicted, we move it to the DELETED list so that if the 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// element is accessed again, we remember the fact that it was already stored 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// and maybe in the future we don't evict that element. 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// When we have to evict an element, first we try to use the last element from 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the NO_USE list, then we move to the LOW_USE and only then we evict an entry 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// from the HIGH_USE. We attempt to keep entries on the cache for at least 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// kTargetTime hours (with frequently accessed items stored for longer periods), 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// but if we cannot do that, we fall-back to keep each list roughly the same 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// size so that we have a chance to see an element again and move it to another 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// list. 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 29a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/eviction.h" 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/bind.h" 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/compiler_specific.h" 335821806d5e7f356e8fa4b058a389a808ea183019Torne (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.h" 38a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/disk_format.h" 39a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/entry_impl.h" 40a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/experiments.h" 41a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/histogram_macros.h" 42a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/trace.h" 4346d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)#include "net/disk_cache/blockfile/webfonts_histogram.h" 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Provide a BackendImpl object to macros from histogram_macros.h. 465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#define CACHE_UMA_BACKEND_IMPL_OBJ backend_ 475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using base::Time; 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using base::TimeTicks; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int kCleanUpMargin = 1024 * 1024; 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int kHighUse = 10; // Reuse count to be on the HIGH_USE list. 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int kTargetTime = 24 * 7; // Time to be evicted (hours since last use). 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int kMaxDelayedTrims = 60; 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int LowWaterAdjust(int high_water) { 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (high_water < kCleanUpMargin) 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return high_water - kCleanUpMargin; 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)bool FallingBehind(int current_size, int max_size) { 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return current_size > max_size - kCleanUpMargin * 20; 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace disk_cache { 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The real initialization happens during Init(), init_ is the only member that 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// has to be initialized here. 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Eviction::Eviction() 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : backend_(NULL), 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) init_(false), 78c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ptr_factory_(this) { 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Eviction::~Eviction() { 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::Init(BackendImpl* backend) { 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We grab a bunch of info from the backend to make the code a little cleaner 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // when we're actually doing work. 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) backend_ = backend; 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_ = &backend->rankings_; 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) header_ = &backend_->data_->header; 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_size_ = LowWaterAdjust(backend_->max_size_); 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) index_size_ = backend->mask_ + 1; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_eviction_ = backend->new_eviction_; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) first_trim_ = true; 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) trimming_ = false; 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delay_trim_ = false; 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) trim_delays_ = 0; 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) init_ = true; 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) test_mode_ = false; 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::Stop() { 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // It is possible for the backend initialization to fail, in which case this 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // object was never initialized... and there is nothing to do. 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!init_) 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We want to stop further evictions, so let's pretend that we are busy from 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this point on. 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(!trimming_); 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) trimming_ = true; 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ptr_factory_.InvalidateWeakPtrs(); 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::TrimCache(bool empty) { 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (backend_->disabled_ || trimming_) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!empty && !ShouldTrim()) 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return PostDelayedTrim(); 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (new_eviction_) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return TrimCacheV2(empty); 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Trace("*** Trim Cache ***"); 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) trimming_ = true; 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TimeTicks start = TimeTicks::Now(); 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Rankings::ScopedRankingsBlock node(rankings_); 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Rankings::ScopedRankingsBlock next( 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_, rankings_->GetPrev(node.get(), Rankings::NO_USE)); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int deleted_entries = 0; 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int target_size = empty ? 0 : max_size_; 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while ((header_->num_bytes > target_size || test_mode_) && next.get()) { 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The iterator could be invalidated within EvictEntry(). 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!next->HasData()) 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node.reset(next.release()); 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next.reset(rankings_->GetPrev(node.get(), Rankings::NO_USE)); 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) { 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This entry is not being used by anybody. 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Do NOT use node as an iterator after this point. 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->TrackRankingsBlock(node.get(), false); 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (EvictEntry(node.get(), empty, Rankings::NO_USE) && !test_mode_) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deleted_entries++; 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!empty && test_mode_) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!empty && (deleted_entries > 20 || 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (TimeTicks::Now() - start).InMilliseconds() > 20)) { 15090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) base::MessageLoop::current()->PostTask( 15190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) FROM_HERE, 15290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) base::Bind(&Eviction::TrimCache, ptr_factory_.GetWeakPtr(), false)); 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (empty) { 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CACHE_UMA(AGE_MS, "TotalClearTimeV1", 0, start); 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CACHE_UMA(AGE_MS, "TotalTrimTimeV1", 0, start); 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CACHE_UMA(COUNTS, "TrimItemsV1", 0, deleted_entries); 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) trimming_ = false; 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Trace("*** Trim Cache end ***"); 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::UpdateRank(EntryImpl* entry, bool modified) { 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (new_eviction_) 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return UpdateRankV2(entry, modified); 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->UpdateRank(entry->rankings(), modified, GetListForEntry(entry)); 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::OnOpenEntry(EntryImpl* entry) { 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (new_eviction_) 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OnOpenEntryV2(entry); 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::OnCreateEntry(EntryImpl* entry) { 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (new_eviction_) 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OnCreateEntryV2(entry); 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->Insert(entry->rankings(), true, GetListForEntry(entry)); 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::OnDoomEntry(EntryImpl* entry) { 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (new_eviction_) 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OnDoomEntryV2(entry); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (entry->LeaveRankingsBehind()) 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->Remove(entry->rankings(), GetListForEntry(entry), true); 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::OnDestroyEntry(EntryImpl* entry) { 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (new_eviction_) 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OnDestroyEntryV2(entry); 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::SetTestMode() { 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) test_mode_ = true; 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::TrimDeletedList(bool empty) { 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(test_mode_ && new_eviction_); 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TrimDeleted(empty); 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::PostDelayedTrim() { 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Prevent posting multiple tasks. 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (delay_trim_) 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delay_trim_ = true; 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) trim_delays_++; 21890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) base::MessageLoop::current()->PostDelayedTask( 21990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) FROM_HERE, 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::Bind(&Eviction::DelayedTrim, ptr_factory_.GetWeakPtr()), 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::TimeDelta::FromMilliseconds(1000)); 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::DelayedTrim() { 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delay_trim_ = false; 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded()) 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return PostDelayedTrim(); 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TrimCache(false); 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Eviction::ShouldTrim() { 2332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!FallingBehind(header_->num_bytes, max_size_) && 2342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded()) { 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) UMA_HISTOGRAM_COUNTS("DiskCache.TrimDelays", trim_delays_); 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) trim_delays_ = 0; 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Eviction::ShouldTrimDeleted() { 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int index_load = header_->num_entries * 100 / index_size_; 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the index is not loaded, the deleted list will tend to double the size 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // of the other lists 3 lists (40% of the total). Otherwise, all lists will be 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // about the same size. 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_length = (index_load < 25) ? header_->num_entries * 2 / 5 : 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) header_->num_entries / 4; 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (!test_mode_ && header_->lru.sizes[Rankings::DELETED] > max_length); 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::ReportTrimTimes(EntryImpl* entry) { 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (first_trim_) { 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) first_trim_ = false; 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (backend_->ShouldReportAgain()) { 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CACHE_UMA(AGE, "TrimAge", 0, entry->GetLastUsed()); 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ReportListStats(); 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (header_->lru.filled) 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) header_->lru.filled = 1; 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (header_->create_time) { 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is the first entry that we have to evict, generate some noise. 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) backend_->FirstEviction(); 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is an old file, but we may want more reports from this user so 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // lets save some create_time. 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Time::Exploded old = {0}; 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) old.year = 2009; 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) old.month = 3; 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) old.day_of_month = 1; 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) header_->create_time = Time::FromLocalExploded(old).ToInternalValue(); 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Rankings::List Eviction::GetListForEntry(EntryImpl* entry) { 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Rankings::NO_USE; 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Eviction::EvictEntry(CacheRankingsBlock* node, bool empty, 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Rankings::List list) { 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EntryImpl* entry = backend_->GetEnumeratedEntry(node, list); 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!entry) { 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Trace("NewEntry failed on Trim 0x%x", node->address().value()); 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 29446d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) web_fonts_histogram::RecordEviction(entry); 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ReportTrimTimes(entry); 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (empty || !new_eviction_) { 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->DoomImpl(); 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->DeleteEntryData(false); 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EntryStore* info = entry->entry()->Data(); 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_EQ(ENTRY_NORMAL, info->state); 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->Remove(entry->rankings(), GetListForEntryV2(entry), true); 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) info->state = ENTRY_EVICTED; 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->entry()->Store(); 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->Insert(entry->rankings(), true, Rankings::DELETED); 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 30890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (!empty) 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) backend_->OnEvent(Stats::TRIM_ENTRY); 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->Release(); 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------- 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::TrimCacheV2(bool empty) { 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Trace("*** Trim Cache ***"); 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) trimming_ = true; 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TimeTicks start = TimeTicks::Now(); 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int kListsToSearch = 3; 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Rankings::ScopedRankingsBlock next[kListsToSearch]; 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int list = Rankings::LAST_ELEMENT; 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Get a node from each list. 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < kListsToSearch; i++) { 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool done = false; 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next[i].set_rankings(rankings_); 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (done) 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next[i].reset(rankings_->GetPrev(NULL, static_cast<Rankings::List>(i))); 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!empty && NodeIsOldEnough(next[i].get(), i)) { 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list = static_cast<Rankings::List>(i); 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) done = true; 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we are not meeting the time targets lets move on to list length. 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!empty && Rankings::LAST_ELEMENT == list) 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list = SelectListByLength(next); 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (empty) 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list = 0; 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Rankings::ScopedRankingsBlock node(rankings_); 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int deleted_entries = 0; 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int target_size = empty ? 0 : max_size_; 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (; list < kListsToSearch; list++) { 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while ((header_->num_bytes > target_size || test_mode_) && 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next[list].get()) { 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The iterator could be invalidated within EvictEntry(). 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!next[list]->HasData()) 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node.reset(next[list].release()); 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next[list].reset(rankings_->GetPrev(node.get(), 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_cast<Rankings::List>(list))); 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) { 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This entry is not being used by anybody. 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Do NOT use node as an iterator after this point. 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->TrackRankingsBlock(node.get(), false); 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (EvictEntry(node.get(), empty, static_cast<Rankings::List>(list))) 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deleted_entries++; 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!empty && test_mode_) 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!empty && (deleted_entries > 20 || 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (TimeTicks::Now() - start).InMilliseconds() > 20)) { 37290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) base::MessageLoop::current()->PostTask( 37390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) FROM_HERE, 37490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) base::Bind(&Eviction::TrimCache, ptr_factory_.GetWeakPtr(), false)); 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!empty) 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list = kListsToSearch; 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (empty) { 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TrimDeleted(true); 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (ShouldTrimDeleted()) { 38590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) base::MessageLoop::current()->PostTask( 38690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) FROM_HERE, 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::Bind(&Eviction::TrimDeleted, ptr_factory_.GetWeakPtr(), empty)); 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (empty) { 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CACHE_UMA(AGE_MS, "TotalClearTimeV2", 0, start); 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CACHE_UMA(AGE_MS, "TotalTrimTimeV2", 0, start); 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CACHE_UMA(COUNTS, "TrimItemsV2", 0, deleted_entries); 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Trace("*** Trim Cache end ***"); 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) trimming_ = false; 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::UpdateRankV2(EntryImpl* entry, bool modified) { 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->UpdateRank(entry->rankings(), modified, GetListForEntryV2(entry)); 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::OnOpenEntryV2(EntryImpl* entry) { 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EntryStore* info = entry->entry()->Data(); 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_EQ(ENTRY_NORMAL, info->state); 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (info->reuse_count < kint32max) { 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) info->reuse_count++; 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->entry()->set_modified(); 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We may need to move this to a new list. 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (1 == info->reuse_count) { 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->Remove(entry->rankings(), Rankings::NO_USE, true); 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->Insert(entry->rankings(), false, Rankings::LOW_USE); 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->entry()->Store(); 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (kHighUse == info->reuse_count) { 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->Remove(entry->rankings(), Rankings::LOW_USE, true); 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->Insert(entry->rankings(), false, Rankings::HIGH_USE); 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->entry()->Store(); 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::OnCreateEntryV2(EntryImpl* entry) { 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EntryStore* info = entry->entry()->Data(); 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (info->state) { 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case ENTRY_NORMAL: { 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(!info->reuse_count); 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(!info->refetch_count); 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case ENTRY_EVICTED: { 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (info->refetch_count < kint32max) 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) info->refetch_count++; 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (info->refetch_count > kHighUse && info->reuse_count < kHighUse) { 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) info->reuse_count = kHighUse; 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) info->reuse_count++; 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) info->state = ENTRY_NORMAL; 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->entry()->Store(); 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->Remove(entry->rankings(), Rankings::DELETED, true); 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) default: 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NOTREACHED(); 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->Insert(entry->rankings(), true, GetListForEntryV2(entry)); 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::OnDoomEntryV2(EntryImpl* entry) { 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EntryStore* info = entry->entry()->Data(); 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (ENTRY_NORMAL != info->state) 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (entry->LeaveRankingsBehind()) { 4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) info->state = ENTRY_DOOMED; 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->entry()->Store(); 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->Remove(entry->rankings(), GetListForEntryV2(entry), true); 4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) info->state = ENTRY_DOOMED; 4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->entry()->Store(); 4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->Insert(entry->rankings(), true, Rankings::DELETED); 4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::OnDestroyEntryV2(EntryImpl* entry) { 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (entry->LeaveRankingsBehind()) 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->Remove(entry->rankings(), Rankings::DELETED, true); 4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Rankings::List Eviction::GetListForEntryV2(EntryImpl* entry) { 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EntryStore* info = entry->entry()->Data(); 4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_EQ(ENTRY_NORMAL, info->state); 4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!info->reuse_count) 4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Rankings::NO_USE; 4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (info->reuse_count < kHighUse) 4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Rankings::LOW_USE; 4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Rankings::HIGH_USE; 4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This is a minimal implementation that just discards the oldest nodes. 4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// TODO(rvargas): Do something better here. 4965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::TrimDeleted(bool empty) { 4975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Trace("*** Trim Deleted ***"); 4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (backend_->disabled_) 4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TimeTicks start = TimeTicks::Now(); 5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Rankings::ScopedRankingsBlock node(rankings_); 5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Rankings::ScopedRankingsBlock next( 5045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_, rankings_->GetPrev(node.get(), Rankings::DELETED)); 5055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int deleted_entries = 0; 5065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (next.get() && 5075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (empty || (deleted_entries < 20 && 5085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (TimeTicks::Now() - start).InMilliseconds() < 20))) { 5095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node.reset(next.release()); 5105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next.reset(rankings_->GetPrev(node.get(), Rankings::DELETED)); 5115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (RemoveDeletedNode(node.get())) 5125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deleted_entries++; 5135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (test_mode_) 5145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 5155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (deleted_entries && !empty && ShouldTrimDeleted()) { 51890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) base::MessageLoop::current()->PostTask( 51990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) FROM_HERE, 5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::Bind(&Eviction::TrimDeleted, ptr_factory_.GetWeakPtr(), false)); 5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CACHE_UMA(AGE_MS, "TotalTrimDeletedTime", 0, start); 5245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CACHE_UMA(COUNTS, "TrimDeletedItems", 0, deleted_entries); 5255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Trace("*** Trim Deleted end ***"); 5265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 5275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Eviction::RemoveDeletedNode(CacheRankingsBlock* node) { 5305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EntryImpl* entry = backend_->GetEnumeratedEntry(node, Rankings::DELETED); 5315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!entry) { 5325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Trace("NewEntry failed on Trim 0x%x", node->address().value()); 5335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 5345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool doomed = (entry->entry()->Data()->state == ENTRY_DOOMED); 5375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->entry()->Data()->state = ENTRY_DOOMED; 5385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->DoomImpl(); 5395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry->Release(); 5405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return !doomed; 5415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Eviction::NodeIsOldEnough(CacheRankingsBlock* node, int list) { 5445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!node) 5455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 5465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If possible, we want to keep entries on each list at least kTargetTime 5485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // hours. Each successive list on the enumeration has 2x the target time of 5495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the previous list. 5505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Time used = Time::FromInternalValue(node->Data()->last_used); 5515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int multiplier = 1 << list; 5525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (Time::Now() - used).InHours() > kTargetTime * multiplier; 5535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int Eviction::SelectListByLength(Rankings::ScopedRankingsBlock* next) { 5565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int data_entries = header_->num_entries - 5575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) header_->lru.sizes[Rankings::DELETED]; 5585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Start by having each list to be roughly the same size. 5595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (header_->lru.sizes[0] > data_entries / 3) 5605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 5615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int list = (header_->lru.sizes[1] > data_entries / 3) ? 1 : 2; 5635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Make sure that frequently used items are kept for a minimum time; we know 5655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // that this entry is not older than its current target, but it must be at 5665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // least older than the target for list 0 (kTargetTime), as long as we don't 5675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // exhaust list 0. 5685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!NodeIsOldEnough(next[list].get(), 0) && 5695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) header_->lru.sizes[0] > data_entries / 10) 5705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list = 0; 5715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return list; 5735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Eviction::ReportListStats() { 5765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!new_eviction_) 5775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 5785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Rankings::ScopedRankingsBlock last1(rankings_, 5805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->GetPrev(NULL, Rankings::NO_USE)); 5815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Rankings::ScopedRankingsBlock last2(rankings_, 5825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->GetPrev(NULL, Rankings::LOW_USE)); 5835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Rankings::ScopedRankingsBlock last3(rankings_, 5845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->GetPrev(NULL, Rankings::HIGH_USE)); 5855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Rankings::ScopedRankingsBlock last4(rankings_, 5865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rankings_->GetPrev(NULL, Rankings::DELETED)); 5875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (last1.get()) 5895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CACHE_UMA(AGE, "NoUseAge", 0, 5905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Time::FromInternalValue(last1.get()->Data()->last_used)); 5915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (last2.get()) 5925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CACHE_UMA(AGE, "LowUseAge", 0, 5935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Time::FromInternalValue(last2.get()->Data()->last_used)); 5945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (last3.get()) 5955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CACHE_UMA(AGE, "HighUseAge", 0, 5965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Time::FromInternalValue(last3.get()->Data()->last_used)); 5975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (last4.get()) 5985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CACHE_UMA(AGE, "DeletedAge", 0, 5995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Time::FromInternalValue(last4.get()->Data()->last_used)); 6005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace disk_cache 603