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

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

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

Powered by Google App Engine
This is Rietveld 408576698