Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(303)

Side by Side Diff: net/disk_cache/v3/eviction_v3.cc

Issue 121643003: Reorganize net/disk_cache into backend specific directories. (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/src
Patch Set: fix ios breakage Created 6 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « net/disk_cache/v3/eviction_v3.h ('k') | net/disk_cache/v3/histogram_macros.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // The eviction policy is a very simple pure LRU, so the elements at the end of
6 // the list are evicted until kCleanUpMargin free space is available. There is
7 // only one list in use (Rankings::NO_USE), and elements are sent to the front
8 // of the list whenever they are accessed.
9
10 // The new (in-development) eviction policy adds re-use as a factor to evict
11 // an entry. The story so far:
12
13 // Entries are linked on separate lists depending on how often they are used.
14 // When we see an element for the first time, it goes to the NO_USE list; if
15 // the object is reused later on, we move it to the LOW_USE list, until it is
16 // used kHighUse times, at which point it is moved to the HIGH_USE list.
17 // Whenever an element is evicted, we move it to the DELETED list so that if the
18 // element is accessed again, we remember the fact that it was already stored
19 // and maybe in the future we don't evict that element.
20
21 // When we have to evict an element, first we try to use the last element from
22 // the NO_USE list, then we move to the LOW_USE and only then we evict an entry
23 // from the HIGH_USE. We attempt to keep entries on the cache for at least
24 // kTargetTime hours (with frequently accessed items stored for longer periods),
25 // but if we cannot do that, we fall-back to keep each list roughly the same
26 // size so that we have a chance to see an element again and move it to another
27 // list.
28
29 #include "net/disk_cache/v3/eviction_v3.h"
30
31 #include "base/bind.h"
32 #include "base/compiler_specific.h"
33 #include "base/logging.h"
34 #include "base/message_loop/message_loop.h"
35 #include "base/strings/string_util.h"
36 #include "base/time/time.h"
37 #include "net/disk_cache/experiments.h"
38 #include "net/disk_cache/trace.h"
39 #include "net/disk_cache/v3/backend_impl_v3.h"
40 #include "net/disk_cache/v3/entry_impl_v3.h"
41 #include "net/disk_cache/v3/histogram_macros.h"
42
43 // Define CACHE_UMA_BACKEND_IMPL_OBJ to be a disk_cache::BackendImpl* in order
44 // to use the CACHE_UMA histogram macro.
45 #define CACHE_UMA_BACKEND_IMPL_OBJ backend_
46
47 using base::Time;
48 using base::TimeTicks;
49
50 namespace {
51
52 const int kCleanUpMargin = 1024 * 1024;
53
54 #if defined(V3_NOT_JUST_YET_READY)
55 const int kHighUse = 10; // Reuse count to be on the HIGH_USE list.
56 const int kTargetTime = 24 * 7; // Time to be evicted (hours since last use).
57 const int kMaxDelayedTrims = 60;
58 #endif // defined(V3_NOT_JUST_YET_READY).
59
60 int LowWaterAdjust(int high_water) {
61 if (high_water < kCleanUpMargin)
62 return 0;
63
64 return high_water - kCleanUpMargin;
65 }
66
67 #if defined(V3_NOT_JUST_YET_READY)
68 bool FallingBehind(int current_size, int max_size) {
69 return current_size > max_size - kCleanUpMargin * 20;
70 }
71 #endif // defined(V3_NOT_JUST_YET_READY).
72
73 } // namespace
74
75 namespace disk_cache {
76
77 // The real initialization happens during Init(), init_ is the only member that
78 // has to be initialized here.
79 EvictionV3::EvictionV3()
80 : backend_(NULL),
81 index_(NULL),
82 header_(NULL),
83 init_(false),
84 ptr_factory_(this) {
85 }
86
87 EvictionV3::~EvictionV3() {
88 }
89
90 void EvictionV3::Init(BackendImplV3* backend) {
91 // We grab a bunch of info from the backend to make the code a little cleaner
92 // when we're actually doing work.
93 backend_ = backend;
94 index_ = &backend_->index_;
95 header_ = index_->header();
96 max_size_ = LowWaterAdjust(backend_->max_size_);
97 lru_ = backend->lru_eviction_;
98 first_trim_ = true;
99 trimming_ = false;
100 delay_trim_ = false;
101 trim_delays_ = 0;
102 init_ = true;
103 test_mode_ = false;
104 }
105
106 void EvictionV3::Stop() {
107 // It is possible for the backend initialization to fail, in which case this
108 // object was never initialized... and there is nothing to do.
109 if (!init_)
110 return;
111
112 // We want to stop further evictions, so let's pretend that we are busy from
113 // this point on.
114 DCHECK(!trimming_);
115 trimming_ = true;
116 ptr_factory_.InvalidateWeakPtrs();
117 }
118
119 #if defined(V3_NOT_JUST_YET_READY)
120 void EvictionV3::TrimCache() {
121 if (backend_->disabled_ || trimming_)
122 return;
123
124 if (!empty && !ShouldTrim())
125 return PostDelayedTrim();
126
127 if (new_eviction_)
128 return TrimCacheV2(empty);
129
130 Trace("*** Trim Cache ***");
131 trimming_ = true;
132 TimeTicks start = TimeTicks::Now();
133 Rankings::ScopedRankingsBlock node(rankings_);
134 Rankings::ScopedRankingsBlock next(
135 rankings_, rankings_->GetPrev(node.get(), Rankings::NO_USE));
136 int deleted_entries = 0;
137 int target_size = empty ? 0 : max_size_;
138 while ((header_->num_bytes > target_size || test_mode_) && next.get()) {
139 // The iterator could be invalidated within EvictEntry().
140 if (!next->HasData())
141 break;
142 node.reset(next.release());
143 next.reset(rankings_->GetPrev(node.get(), Rankings::NO_USE));
144 if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) {
145 // This entry is not being used by anybody.
146 // Do NOT use node as an iterator after this point.
147 rankings_->TrackRankingsBlock(node.get(), false);
148 if (EvictEntry(node.get(), empty, Rankings::NO_USE) && !test_mode_)
149 deleted_entries++;
150
151 if (!empty && test_mode_)
152 break;
153 }
154 if (!empty && (deleted_entries > 20 ||
155 (TimeTicks::Now() - start).InMilliseconds() > 20)) {
156 base::MessageLoop::current()->PostTask(
157 FROM_HERE,
158 base::Bind(&EvictionV3::TrimCache, ptr_factory_.GetWeakPtr(), false));
159 break;
160 }
161 }
162
163 if (empty) {
164 CACHE_UMA(AGE_MS, "TotalClearTimeV1", 0, start);
165 } else {
166 CACHE_UMA(AGE_MS, "TotalTrimTimeV1", 0, start);
167 }
168 CACHE_UMA(COUNTS, "TrimItemsV1", 0, deleted_entries);
169
170 trimming_ = false;
171 Trace("*** Trim Cache end ***");
172 return;
173 }
174
175 void EvictionV3::OnOpenEntry(EntryImplV3* entry) {
176 EntryStore* info = entry->entry()->Data();
177 DCHECK_EQ(ENTRY_NORMAL, info->state);
178
179 if (info->reuse_count < kint32max) {
180 info->reuse_count++;
181 entry->entry()->set_modified();
182
183 // We may need to move this to a new list.
184 if (1 == info->reuse_count) {
185 rankings_->Remove(entry->rankings(), Rankings::NO_USE, true);
186 rankings_->Insert(entry->rankings(), false, Rankings::LOW_USE);
187 entry->entry()->Store();
188 } else if (kHighUse == info->reuse_count) {
189 rankings_->Remove(entry->rankings(), Rankings::LOW_USE, true);
190 rankings_->Insert(entry->rankings(), false, Rankings::HIGH_USE);
191 entry->entry()->Store();
192 }
193 }
194 }
195
196 void EvictionV3::OnCreateEntry(EntryImplV3* entry) {
197 EntryStore* info = entry->entry()->Data();
198 switch (info->state) {
199 case ENTRY_NORMAL: {
200 DCHECK(!info->reuse_count);
201 DCHECK(!info->refetch_count);
202 break;
203 };
204 case ENTRY_EVICTED: {
205 if (info->refetch_count < kint32max)
206 info->refetch_count++;
207
208 if (info->refetch_count > kHighUse && info->reuse_count < kHighUse) {
209 info->reuse_count = kHighUse;
210 } else {
211 info->reuse_count++;
212 }
213 info->state = ENTRY_NORMAL;
214 entry->entry()->Store();
215 rankings_->Remove(entry->rankings(), Rankings::DELETED, true);
216 break;
217 };
218 default:
219 NOTREACHED();
220 }
221
222 rankings_->Insert(entry->rankings(), true, GetListForEntryV2(entry));
223 }
224
225 void EvictionV3::SetTestMode() {
226 test_mode_ = true;
227 }
228
229 void EvictionV3::TrimDeletedList(bool empty) {
230 DCHECK(test_mode_ && new_eviction_);
231 TrimDeleted(empty);
232 }
233
234 // -----------------------------------------------------------------------
235
236 void EvictionV3::PostDelayedTrim() {
237 // Prevent posting multiple tasks.
238 if (delay_trim_)
239 return;
240 delay_trim_ = true;
241 trim_delays_++;
242 base::MessageLoop::current()->PostDelayedTask(
243 FROM_HERE,
244 base::Bind(&EvictionV3::DelayedTrim, ptr_factory_.GetWeakPtr()),
245 base::TimeDelta::FromMilliseconds(1000));
246 }
247
248 void EvictionV3::DelayedTrim() {
249 delay_trim_ = false;
250 if (trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded())
251 return PostDelayedTrim();
252
253 TrimCache(false);
254 }
255
256 bool EvictionV3::ShouldTrim() {
257 if (!FallingBehind(header_->num_bytes, max_size_) &&
258 trim_delays_ < kMaxDelayedTrims && backend_->IsLoaded()) {
259 return false;
260 }
261
262 UMA_HISTOGRAM_COUNTS("DiskCache.TrimDelays", trim_delays_);
263 trim_delays_ = 0;
264 return true;
265 }
266
267 bool EvictionV3::ShouldTrimDeleted() {
268 int index_load = header_->num_entries * 100 / index_size_;
269
270 // If the index is not loaded, the deleted list will tend to double the size
271 // of the other lists 3 lists (40% of the total). Otherwise, all lists will be
272 // about the same size.
273 int max_length = (index_load < 25) ? header_->num_entries * 2 / 5 :
274 header_->num_entries / 4;
275 return (!test_mode_ && header_->lru.sizes[Rankings::DELETED] > max_length);
276 }
277
278 bool Eviction::EvictEntry(CacheRankingsBlock* node, bool empty,
279 Rankings::List list) {
280 EntryImplV3* entry = backend_->GetEnumeratedEntry(node, list);
281 if (!entry) {
282 Trace("NewEntry failed on Trim 0x%x", node->address().value());
283 return false;
284 }
285
286 ReportTrimTimes(entry);
287 if (empty || !new_eviction_) {
288 entry->DoomImpl();
289 } else {
290 entry->DeleteEntryData(false);
291 EntryStore* info = entry->entry()->Data();
292 DCHECK_EQ(ENTRY_NORMAL, info->state);
293
294 rankings_->Remove(entry->rankings(), GetListForEntryV2(entry), true);
295 info->state = ENTRY_EVICTED;
296 entry->entry()->Store();
297 rankings_->Insert(entry->rankings(), true, Rankings::DELETED);
298 }
299 if (!empty)
300 backend_->OnEvent(Stats::TRIM_ENTRY);
301
302 entry->Release();
303
304 return true;
305 }
306
307 void EvictionV3::TrimCacheV2(bool empty) {
308 Trace("*** Trim Cache ***");
309 trimming_ = true;
310 TimeTicks start = TimeTicks::Now();
311
312 const int kListsToSearch = 3;
313 Rankings::ScopedRankingsBlock next[kListsToSearch];
314 int list = Rankings::LAST_ELEMENT;
315
316 // Get a node from each list.
317 for (int i = 0; i < kListsToSearch; i++) {
318 bool done = false;
319 next[i].set_rankings(rankings_);
320 if (done)
321 continue;
322 next[i].reset(rankings_->GetPrev(NULL, static_cast<Rankings::List>(i)));
323 if (!empty && NodeIsOldEnough(next[i].get(), i)) {
324 list = static_cast<Rankings::List>(i);
325 done = true;
326 }
327 }
328
329 // If we are not meeting the time targets lets move on to list length.
330 if (!empty && Rankings::LAST_ELEMENT == list)
331 list = SelectListByLength(next);
332
333 if (empty)
334 list = 0;
335
336 Rankings::ScopedRankingsBlock node(rankings_);
337 int deleted_entries = 0;
338 int target_size = empty ? 0 : max_size_;
339
340 for (; list < kListsToSearch; list++) {
341 while ((header_->num_bytes > target_size || test_mode_) &&
342 next[list].get()) {
343 // The iterator could be invalidated within EvictEntry().
344 if (!next[list]->HasData())
345 break;
346 node.reset(next[list].release());
347 next[list].reset(rankings_->GetPrev(node.get(),
348 static_cast<Rankings::List>(list)));
349 if (node->Data()->dirty != backend_->GetCurrentEntryId() || empty) {
350 // This entry is not being used by anybody.
351 // Do NOT use node as an iterator after this point.
352 rankings_->TrackRankingsBlock(node.get(), false);
353 if (EvictEntry(node.get(), empty, static_cast<Rankings::List>(list)))
354 deleted_entries++;
355
356 if (!empty && test_mode_)
357 break;
358 }
359 if (!empty && (deleted_entries > 20 ||
360 (TimeTicks::Now() - start).InMilliseconds() > 20)) {
361 base::MessageLoop::current()->PostTask(
362 FROM_HERE,
363 base::Bind(&Eviction::TrimCache, ptr_factory_.GetWeakPtr(), false));
364 break;
365 }
366 }
367 if (!empty)
368 list = kListsToSearch;
369 }
370
371 if (empty) {
372 TrimDeleted(true);
373 } else if (ShouldTrimDeleted()) {
374 base::MessageLoop::current()->PostTask(
375 FROM_HERE,
376 base::Bind(&EvictionV3::TrimDeleted, ptr_factory_.GetWeakPtr(), empty));
377 }
378
379 if (empty) {
380 CACHE_UMA(AGE_MS, "TotalClearTimeV2", 0, start);
381 } else {
382 CACHE_UMA(AGE_MS, "TotalTrimTimeV2", 0, start);
383 }
384 CACHE_UMA(COUNTS, "TrimItemsV2", 0, deleted_entries);
385
386 Trace("*** Trim Cache end ***");
387 trimming_ = false;
388 return;
389 }
390
391 // This is a minimal implementation that just discards the oldest nodes.
392 // TODO(rvargas): Do something better here.
393 void EvictionV3::TrimDeleted(bool empty) {
394 Trace("*** Trim Deleted ***");
395 if (backend_->disabled_)
396 return;
397
398 TimeTicks start = TimeTicks::Now();
399 Rankings::ScopedRankingsBlock node(rankings_);
400 Rankings::ScopedRankingsBlock next(
401 rankings_, rankings_->GetPrev(node.get(), Rankings::DELETED));
402 int deleted_entries = 0;
403 while (next.get() &&
404 (empty || (deleted_entries < 20 &&
405 (TimeTicks::Now() - start).InMilliseconds() < 20))) {
406 node.reset(next.release());
407 next.reset(rankings_->GetPrev(node.get(), Rankings::DELETED));
408 if (RemoveDeletedNode(node.get()))
409 deleted_entries++;
410 if (test_mode_)
411 break;
412 }
413
414 if (deleted_entries && !empty && ShouldTrimDeleted()) {
415 base::MessageLoop::current()->PostTask(
416 FROM_HERE,
417 base::Bind(&EvictionV3::TrimDeleted, ptr_factory_.GetWeakPtr(), false));
418 }
419
420 CACHE_UMA(AGE_MS, "TotalTrimDeletedTime", 0, start);
421 CACHE_UMA(COUNTS, "TrimDeletedItems", 0, deleted_entries);
422 Trace("*** Trim Deleted end ***");
423 return;
424 }
425
426 void EvictionV3::ReportTrimTimes(EntryImplV3* entry) {
427 if (first_trim_) {
428 first_trim_ = false;
429 if (backend_->ShouldReportAgain()) {
430 CACHE_UMA(AGE, "TrimAge", 0, entry->GetLastUsed());
431 ReportListStats();
432 }
433
434 if (header_->lru.filled)
435 return;
436
437 header_->lru.filled = 1;
438
439 if (header_->create_time) {
440 // This is the first entry that we have to evict, generate some noise.
441 backend_->FirstEviction();
442 } else {
443 // This is an old file, but we may want more reports from this user so
444 // lets save some create_time.
445 Time::Exploded old = {0};
446 old.year = 2009;
447 old.month = 3;
448 old.day_of_month = 1;
449 header_->create_time = Time::FromLocalExploded(old).ToInternalValue();
450 }
451 }
452 }
453
454 bool EvictionV3::NodeIsOldEnough(CacheRankingsBlock* node, int list) {
455 if (!node)
456 return false;
457
458 // If possible, we want to keep entries on each list at least kTargetTime
459 // hours. Each successive list on the enumeration has 2x the target time of
460 // the previous list.
461 Time used = Time::FromInternalValue(node->Data()->last_used);
462 int multiplier = 1 << list;
463 return (Time::Now() - used).InHours() > kTargetTime * multiplier;
464 }
465
466 int EvictionV3::SelectListByLength(Rankings::ScopedRankingsBlock* next) {
467 int data_entries = header_->num_entries -
468 header_->lru.sizes[Rankings::DELETED];
469 // Start by having each list to be roughly the same size.
470 if (header_->lru.sizes[0] > data_entries / 3)
471 return 0;
472
473 int list = (header_->lru.sizes[1] > data_entries / 3) ? 1 : 2;
474
475 // Make sure that frequently used items are kept for a minimum time; we know
476 // that this entry is not older than its current target, but it must be at
477 // least older than the target for list 0 (kTargetTime), as long as we don't
478 // exhaust list 0.
479 if (!NodeIsOldEnough(next[list].get(), 0) &&
480 header_->lru.sizes[0] > data_entries / 10)
481 list = 0;
482
483 return list;
484 }
485
486 void EvictionV3::ReportListStats() {
487 if (!new_eviction_)
488 return;
489
490 Rankings::ScopedRankingsBlock last1(rankings_,
491 rankings_->GetPrev(NULL, Rankings::NO_USE));
492 Rankings::ScopedRankingsBlock last2(rankings_,
493 rankings_->GetPrev(NULL, Rankings::LOW_USE));
494 Rankings::ScopedRankingsBlock last3(rankings_,
495 rankings_->GetPrev(NULL, Rankings::HIGH_USE));
496 Rankings::ScopedRankingsBlock last4(rankings_,
497 rankings_->GetPrev(NULL, Rankings::DELETED));
498
499 if (last1.get())
500 CACHE_UMA(AGE, "NoUseAge", 0,
501 Time::FromInternalValue(last1.get()->Data()->last_used));
502 if (last2.get())
503 CACHE_UMA(AGE, "LowUseAge", 0,
504 Time::FromInternalValue(last2.get()->Data()->last_used));
505 if (last3.get())
506 CACHE_UMA(AGE, "HighUseAge", 0,
507 Time::FromInternalValue(last3.get()->Data()->last_used));
508 if (last4.get())
509 CACHE_UMA(AGE, "DeletedAge", 0,
510 Time::FromInternalValue(last4.get()->Data()->last_used));
511 }
512 #endif // defined(V3_NOT_JUST_YET_READY).
513
514 } // namespace disk_cache
OLDNEW
« no previous file with comments | « net/disk_cache/v3/eviction_v3.h ('k') | net/disk_cache/v3/histogram_macros.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698