1 // Copyright (c) 2006-2008 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 #include "net/disk_cache/rankings.h"
6
7 #include "base/histogram.h"
8 #include "net/disk_cache/backend_impl.h"
9 #include "net/disk_cache/entry_impl.h"
10 #include "net/disk_cache/errors.h"
11 #include "net/disk_cache/histogram_macros.h"
12
13 using base::Time;
14
15 // This is used by crash_cache.exe to generate unit test files.
16 disk_cache::RankCrashes g_rankings_crash = disk_cache::NO_CRASH;
17
18 namespace {
19
20 enum Operation {
21 INSERT = 1,
22 REMOVE
23 };
24
25 // This class provides a simple lock for the LRU list of rankings. Whenever an
26 // entry is to be inserted or removed from the list, a transaction object should
27 // be created to keep track of the operation. If the process crashes before
28 // finishing the operation, the transaction record (stored as part of the user
29 // data on the file header) can be used to finish the operation.
30 class Transaction {
31 public:
32 // addr is the cache addres of the node being inserted or removed. We want to
33 // avoid having the compiler doing optimizations on when to read or write
34 // from user_data because it is the basis of the crash detection. Maybe
35 // volatile is not enough for that, but it should be a good hint.
36 Transaction(volatile disk_cache::LruData* data, disk_cache::Addr addr,
37 Operation op, int list);
38 ~Transaction();
39 private:
40 volatile disk_cache::LruData* data_;
41 DISALLOW_COPY_AND_ASSIGN(Transaction);
42 };
43
Transaction(volatile disk_cache::LruData * data,disk_cache::Addr addr,Operation op,int list)44 Transaction::Transaction(volatile disk_cache::LruData* data,
45 disk_cache::Addr addr, Operation op, int list)
46 : data_(data) {
47 DCHECK(!data_->transaction);
48 DCHECK(addr.is_initialized());
49 data_->operation = op;
50 data_->operation_list = list;
51 data_->transaction = addr.value();
52 }
53
~Transaction()54 Transaction::~Transaction() {
55 DCHECK(data_->transaction);
56 data_->transaction = 0;
57 data_->operation = 0;
58 data_->operation_list = 0;
59 }
60
61 // Code locations that can generate crashes.
62 enum CrashLocation {
63 ON_INSERT_1, ON_INSERT_2, ON_INSERT_3, ON_INSERT_4, ON_REMOVE_1, ON_REMOVE_2,
64 ON_REMOVE_3, ON_REMOVE_4, ON_REMOVE_5, ON_REMOVE_6, ON_REMOVE_7, ON_REMOVE_8
65 };
66
TerminateSelf()67 void TerminateSelf() {
68 #if defined(OS_WIN)
69 // Windows does more work on _exit() than we would like, so we force exit.
70 TerminateProcess(GetCurrentProcess(), 0);
71 #elif defined(OS_POSIX)
72 // On POSIX, _exit() will terminate the process with minimal cleanup,
73 // and it is cleaner than killing.
74 _exit(0);
75 #endif
76 }
77
78 // Generates a crash on debug builds, acording to the value of g_rankings_crash.
79 // This used by crash_cache.exe to generate unit-test files.
GenerateCrash(CrashLocation location)80 void GenerateCrash(CrashLocation location) {
81 #ifndef NDEBUG
82 if (disk_cache::NO_CRASH == g_rankings_crash)
83 return;
84 switch (location) {
85 case ON_INSERT_1:
86 switch (g_rankings_crash) {
87 case disk_cache::INSERT_ONE_1:
88 case disk_cache::INSERT_LOAD_1:
89 TerminateSelf();
90 default:
91 break;
92 }
93 break;
94 case ON_INSERT_2:
95 if (disk_cache::INSERT_EMPTY_1 == g_rankings_crash)
96 TerminateSelf();
97 break;
98 case ON_INSERT_3:
99 switch (g_rankings_crash) {
100 case disk_cache::INSERT_EMPTY_2:
101 case disk_cache::INSERT_ONE_2:
102 case disk_cache::INSERT_LOAD_2:
103 TerminateSelf();
104 default:
105 break;
106 }
107 break;
108 case ON_INSERT_4:
109 switch (g_rankings_crash) {
110 case disk_cache::INSERT_EMPTY_3:
111 case disk_cache::INSERT_ONE_3:
112 TerminateSelf();
113 default:
114 break;
115 }
116 break;
117 case ON_REMOVE_1:
118 switch (g_rankings_crash) {
119 case disk_cache::REMOVE_ONE_1:
120 case disk_cache::REMOVE_HEAD_1:
121 case disk_cache::REMOVE_TAIL_1:
122 case disk_cache::REMOVE_LOAD_1:
123 TerminateSelf();
124 default:
125 break;
126 }
127 break;
128 case ON_REMOVE_2:
129 if (disk_cache::REMOVE_ONE_2 == g_rankings_crash)
130 TerminateSelf();
131 break;
132 case ON_REMOVE_3:
133 if (disk_cache::REMOVE_ONE_3 == g_rankings_crash)
134 TerminateSelf();
135 break;
136 case ON_REMOVE_4:
137 if (disk_cache::REMOVE_HEAD_2 == g_rankings_crash)
138 TerminateSelf();
139 break;
140 case ON_REMOVE_5:
141 if (disk_cache::REMOVE_TAIL_2 == g_rankings_crash)
142 TerminateSelf();
143 break;
144 case ON_REMOVE_6:
145 if (disk_cache::REMOVE_TAIL_3 == g_rankings_crash)
146 TerminateSelf();
147 break;
148 case ON_REMOVE_7:
149 switch (g_rankings_crash) {
150 case disk_cache::REMOVE_ONE_4:
151 case disk_cache::REMOVE_LOAD_2:
152 case disk_cache::REMOVE_HEAD_3:
153 TerminateSelf();
154 default:
155 break;
156 }
157 break;
158 case ON_REMOVE_8:
159 switch (g_rankings_crash) {
160 case disk_cache::REMOVE_HEAD_4:
161 case disk_cache::REMOVE_LOAD_3:
162 TerminateSelf();
163 default:
164 break;
165 }
166 break;
167 default:
168 NOTREACHED();
169 return;
170 }
171 #endif // NDEBUG
172 }
173
174 } // namespace
175
176 namespace disk_cache {
177
Init(BackendImpl * backend,bool count_lists)178 bool Rankings::Init(BackendImpl* backend, bool count_lists) {
179 DCHECK(!init_);
180 if (init_)
181 return false;
182
183 backend_ = backend;
184 control_data_ = backend_->GetLruData();
185 count_lists_ = count_lists;
186
187 ReadHeads();
188 ReadTails();
189
190 if (control_data_->transaction)
191 CompleteTransaction();
192
193 init_ = true;
194 return true;
195 }
196
Reset()197 void Rankings::Reset() {
198 init_ = false;
199 for (int i = 0; i < LAST_ELEMENT; i++) {
200 heads_[i].set_value(0);
201 tails_[i].set_value(0);
202 }
203 control_data_ = NULL;
204 }
205
GetRanking(CacheRankingsBlock * rankings)206 bool Rankings::GetRanking(CacheRankingsBlock* rankings) {
207 if (!rankings->address().is_initialized())
208 return false;
209
210 Time start = Time::Now();
211 if (!rankings->Load())
212 return false;
213
214 if (!SanityCheck(rankings, true)) {
215 backend_->CriticalError(ERR_INVALID_LINKS);
216 return false;
217 }
218
219 backend_->OnEvent(Stats::OPEN_RANKINGS);
220
221 // "dummy" is the old "pointer" value, so it has to be 0.
222 if (!rankings->Data()->dirty && !rankings->Data()->dummy)
223 return true;
224
225 EntryImpl* entry = backend_->GetOpenEntry(rankings);
226 if (backend_->GetCurrentEntryId() != rankings->Data()->dirty || !entry) {
227 // We cannot trust this entry, but we cannot initiate a cleanup from this
228 // point (we may be in the middle of a cleanup already). Just get rid of
229 // the invalid pointer and continue; the entry will be deleted when detected
230 // from a regular open/create path.
231 rankings->Data()->dummy = 0;
232 rankings->Data()->dirty = backend_->GetCurrentEntryId() - 1;
233 if (!rankings->Data()->dirty)
234 rankings->Data()->dirty--;
235 return true;
236 }
237
238 // Note that we should not leave this module without deleting rankings first.
239 rankings->SetData(entry->rankings()->Data());
240
241 CACHE_UMA(AGE_MS, "GetRankings", 0, start);
242 return true;
243 }
244
ConvertToLongLived(CacheRankingsBlock * rankings)245 void Rankings::ConvertToLongLived(CacheRankingsBlock* rankings) {
246 if (rankings->own_data())
247 return;
248
249 // We cannot return a shared node because we are not keeping a reference
250 // to the entry that owns the buffer. Make this node a copy of the one that
251 // we have, and let the iterator logic update it when the entry changes.
252 CacheRankingsBlock temp(NULL, Addr(0));
253 *temp.Data() = *rankings->Data();
254 rankings->StopSharingData();
255 *rankings->Data() = *temp.Data();
256 }
257
Insert(CacheRankingsBlock * node,bool modified,List list)258 void Rankings::Insert(CacheRankingsBlock* node, bool modified, List list) {
259 Trace("Insert 0x%x", node->address().value());
260 DCHECK(node->HasData());
261 Addr& my_head = heads_[list];
262 Addr& my_tail = tails_[list];
263 Transaction lock(control_data_, node->address(), INSERT, list);
264 CacheRankingsBlock head(backend_->File(my_head), my_head);
265 if (my_head.is_initialized()) {
266 if (!GetRanking(&head))
267 return;
268
269 if (head.Data()->prev != my_head.value() && // Normal path.
270 head.Data()->prev != node->address().value()) { // FinishInsert().
271 backend_->CriticalError(ERR_INVALID_LINKS);
272 return;
273 }
274
275 head.Data()->prev = node->address().value();
276 head.Store();
277 GenerateCrash(ON_INSERT_1);
278 UpdateIterators(&head);
279 }
280
281 node->Data()->next = my_head.value();
282 node->Data()->prev = node->address().value();
283 my_head.set_value(node->address().value());
284
285 if (!my_tail.is_initialized() || my_tail.value() == node->address().value()) {
286 my_tail.set_value(node->address().value());
287 node->Data()->next = my_tail.value();
288 WriteTail(list);
289 GenerateCrash(ON_INSERT_2);
290 }
291
292 Time now = Time::Now();
293 node->Data()->last_used = now.ToInternalValue();
294 if (modified)
295 node->Data()->last_modified = now.ToInternalValue();
296 node->Store();
297 GenerateCrash(ON_INSERT_3);
298
299 // The last thing to do is move our head to point to a node already stored.
300 WriteHead(list);
301 IncrementCounter(list);
302 GenerateCrash(ON_INSERT_4);
303 }
304
305 // If a, b and r are elements on the list, and we want to remove r, the possible
306 // states for the objects if a crash happens are (where y(x, z) means for object
307 // y, prev is x and next is z):
308 // A. One element:
309 // 1. r(r, r), head(r), tail(r) initial state
310 // 2. r(r, r), head(0), tail(r) WriteHead()
311 // 3. r(r, r), head(0), tail(0) WriteTail()
312 // 4. r(0, 0), head(0), tail(0) next.Store()
313 //
314 // B. Remove a random element:
315 // 1. a(x, r), r(a, b), b(r, y), head(x), tail(y) initial state
316 // 2. a(x, r), r(a, b), b(a, y), head(x), tail(y) next.Store()
317 // 3. a(x, b), r(a, b), b(a, y), head(x), tail(y) prev.Store()
318 // 4. a(x, b), r(0, 0), b(a, y), head(x), tail(y) node.Store()
319 //
320 // C. Remove head:
321 // 1. r(r, b), b(r, y), head(r), tail(y) initial state
322 // 2. r(r, b), b(r, y), head(b), tail(y) WriteHead()
323 // 3. r(r, b), b(b, y), head(b), tail(y) next.Store()
324 // 4. r(0, 0), b(b, y), head(b), tail(y) prev.Store()
325 //
326 // D. Remove tail:
327 // 1. a(x, r), r(a, r), head(x), tail(r) initial state
328 // 2. a(x, r), r(a, r), head(x), tail(a) WriteTail()
329 // 3. a(x, a), r(a, r), head(x), tail(a) prev.Store()
330 // 4. a(x, a), r(0, 0), head(x), tail(a) next.Store()
Remove(CacheRankingsBlock * node,List list)331 void Rankings::Remove(CacheRankingsBlock* node, List list) {
332 Trace("Remove 0x%x (0x%x 0x%x)", node->address().value(), node->Data()->next,
333 node->Data()->prev);
334 DCHECK(node->HasData());
335 InvalidateIterators(node);
336 Addr next_addr(node->Data()->next);
337 Addr prev_addr(node->Data()->prev);
338 if (!next_addr.is_initialized() || next_addr.is_separate_file() ||
339 !prev_addr.is_initialized() || prev_addr.is_separate_file()) {
340 LOG(WARNING) << "Invalid rankings info.";
341 return;
342 }
343
344 CacheRankingsBlock next(backend_->File(next_addr), next_addr);
345 CacheRankingsBlock prev(backend_->File(prev_addr), prev_addr);
346 if (!GetRanking(&next) || !GetRanking(&prev))
347 return;
348
349 if (!CheckLinks(node, &prev, &next, list))
350 return;
351
352 Transaction lock(control_data_, node->address(), REMOVE, list);
353 prev.Data()->next = next.address().value();
354 next.Data()->prev = prev.address().value();
355 GenerateCrash(ON_REMOVE_1);
356
357 CacheAddr node_value = node->address().value();
358 Addr& my_head = heads_[list];
359 Addr& my_tail = tails_[list];
360 if (node_value == my_head.value() || node_value == my_tail.value()) {
361 if (my_head.value() == my_tail.value()) {
362 my_head.set_value(0);
363 my_tail.set_value(0);
364
365 WriteHead(list);
366 GenerateCrash(ON_REMOVE_2);
367 WriteTail(list);
368 GenerateCrash(ON_REMOVE_3);
369 } else if (node_value == my_head.value()) {
370 my_head.set_value(next.address().value());
371 next.Data()->prev = next.address().value();
372
373 WriteHead(list);
374 GenerateCrash(ON_REMOVE_4);
375 } else if (node_value == my_tail.value()) {
376 my_tail.set_value(prev.address().value());
377 prev.Data()->next = prev.address().value();
378
379 WriteTail(list);
380 GenerateCrash(ON_REMOVE_5);
381
382 // Store the new tail to make sure we can undo the operation if we crash.
383 prev.Store();
384 GenerateCrash(ON_REMOVE_6);
385 }
386 }
387
388 // Nodes out of the list can be identified by invalid pointers.
389 node->Data()->next = 0;
390 node->Data()->prev = 0;
391
392 // The last thing to get to disk is the node itself, so before that there is
393 // enough info to recover.
394 next.Store();
395 GenerateCrash(ON_REMOVE_7);
396 prev.Store();
397 GenerateCrash(ON_REMOVE_8);
398 node->Store();
399 DecrementCounter(list);
400 UpdateIterators(&next);
401 UpdateIterators(&prev);
402 }
403
404 // A crash in between Remove and Insert will lead to a dirty entry not on the
405 // list. We want to avoid that case as much as we can (as while waiting for IO),
406 // but the net effect is just an assert on debug when attempting to remove the
407 // entry. Otherwise we'll need reentrant transactions, which is an overkill.
UpdateRank(CacheRankingsBlock * node,bool modified,List list)408 void Rankings::UpdateRank(CacheRankingsBlock* node, bool modified, List list) {
409 Time start = Time::Now();
410 Remove(node, list);
411 Insert(node, modified, list);
412 CACHE_UMA(AGE_MS, "UpdateRank", 0, start);
413 }
414
CompleteTransaction()415 void Rankings::CompleteTransaction() {
416 Addr node_addr(static_cast<CacheAddr>(control_data_->transaction));
417 if (!node_addr.is_initialized() || node_addr.is_separate_file()) {
418 NOTREACHED();
419 LOG(ERROR) << "Invalid rankings info.";
420 return;
421 }
422
423 Trace("CompleteTransaction 0x%x", node_addr.value());
424
425 CacheRankingsBlock node(backend_->File(node_addr), node_addr);
426 if (!node.Load())
427 return;
428
429 node.Data()->dummy = 0;
430 node.Store();
431
432 Addr& my_head = heads_[control_data_->operation_list];
433 Addr& my_tail = tails_[control_data_->operation_list];
434
435 // We want to leave the node inside the list. The entry must me marked as
436 // dirty, and will be removed later. Otherwise, we'll get assertions when
437 // attempting to remove the dirty entry.
438 if (INSERT == control_data_->operation) {
439 Trace("FinishInsert h:0x%x t:0x%x", my_head.value(), my_tail.value());
440 FinishInsert(&node);
441 } else if (REMOVE == control_data_->operation) {
442 Trace("RevertRemove h:0x%x t:0x%x", my_head.value(), my_tail.value());
443 RevertRemove(&node);
444 } else {
445 NOTREACHED();
446 LOG(ERROR) << "Invalid operation to recover.";
447 }
448 }
449
FinishInsert(CacheRankingsBlock * node)450 void Rankings::FinishInsert(CacheRankingsBlock* node) {
451 control_data_->transaction = 0;
452 control_data_->operation = 0;
453 Addr& my_head = heads_[control_data_->operation_list];
454 Addr& my_tail = tails_[control_data_->operation_list];
455 if (my_head.value() != node->address().value()) {
456 if (my_tail.value() == node->address().value()) {
457 // This part will be skipped by the logic of Insert.
458 node->Data()->next = my_tail.value();
459 }
460
461 Insert(node, true, static_cast<List>(control_data_->operation_list));
462 }
463
464 // Tell the backend about this entry.
465 backend_->RecoveredEntry(node);
466 }
467
RevertRemove(CacheRankingsBlock * node)468 void Rankings::RevertRemove(CacheRankingsBlock* node) {
469 Addr next_addr(node->Data()->next);
470 Addr prev_addr(node->Data()->prev);
471 if (!next_addr.is_initialized() || !prev_addr.is_initialized()) {
472 // The operation actually finished. Nothing to do.
473 control_data_->transaction = 0;
474 return;
475 }
476 if (next_addr.is_separate_file() || prev_addr.is_separate_file()) {
477 NOTREACHED();
478 LOG(WARNING) << "Invalid rankings info.";
479 control_data_->transaction = 0;
480 return;
481 }
482
483 CacheRankingsBlock next(backend_->File(next_addr), next_addr);
484 CacheRankingsBlock prev(backend_->File(prev_addr), prev_addr);
485 if (!next.Load() || !prev.Load())
486 return;
487
488 CacheAddr node_value = node->address().value();
489 DCHECK(prev.Data()->next == node_value ||
490 prev.Data()->next == prev_addr.value() ||
491 prev.Data()->next == next.address().value());
492 DCHECK(next.Data()->prev == node_value ||
493 next.Data()->prev == next_addr.value() ||
494 next.Data()->prev == prev.address().value());
495
496 if (node_value != prev_addr.value())
497 prev.Data()->next = node_value;
498 if (node_value != next_addr.value())
499 next.Data()->prev = node_value;
500
501 List my_list = static_cast<List>(control_data_->operation_list);
502 Addr& my_head = heads_[my_list];
503 Addr& my_tail = tails_[my_list];
504 if (!my_head.is_initialized() || !my_tail.is_initialized()) {
505 my_head.set_value(node_value);
506 my_tail.set_value(node_value);
507 WriteHead(my_list);
508 WriteTail(my_list);
509 } else if (my_head.value() == next.address().value()) {
510 my_head.set_value(node_value);
511 prev.Data()->next = next.address().value();
512 WriteHead(my_list);
513 } else if (my_tail.value() == prev.address().value()) {
514 my_tail.set_value(node_value);
515 next.Data()->prev = prev.address().value();
516 WriteTail(my_list);
517 }
518
519 next.Store();
520 prev.Store();
521 control_data_->transaction = 0;
522 control_data_->operation = 0;
523 }
524
GetNext(CacheRankingsBlock * node,List list)525 CacheRankingsBlock* Rankings::GetNext(CacheRankingsBlock* node, List list) {
526 ScopedRankingsBlock next(this);
527 if (!node) {
528 Addr& my_head = heads_[list];
529 if (!my_head.is_initialized())
530 return NULL;
531 next.reset(new CacheRankingsBlock(backend_->File(my_head), my_head));
532 } else {
533 if (!node->HasData())
534 node->Load();
535 Addr& my_tail = tails_[list];
536 if (!my_tail.is_initialized())
537 return NULL;
538 if (my_tail.value() == node->address().value())
539 return NULL;
540 Addr address(node->Data()->next);
541 if (address.value() == node->address().value())
542 return NULL; // Another tail? fail it.
543 next.reset(new CacheRankingsBlock(backend_->File(address), address));
544 }
545
546 TrackRankingsBlock(next.get(), true);
547
548 if (!GetRanking(next.get()))
549 return NULL;
550
551 ConvertToLongLived(next.get());
552 if (node && !CheckSingleLink(node, next.get()))
553 return NULL;
554
555 return next.release();
556 }
557
GetPrev(CacheRankingsBlock * node,List list)558 CacheRankingsBlock* Rankings::GetPrev(CacheRankingsBlock* node, List list) {
559 ScopedRankingsBlock prev(this);
560 if (!node) {
561 Addr& my_tail = tails_[list];
562 if (!my_tail.is_initialized())
563 return NULL;
564 prev.reset(new CacheRankingsBlock(backend_->File(my_tail), my_tail));
565 } else {
566 if (!node->HasData())
567 node->Load();
568 Addr& my_head = heads_[list];
569 if (!my_head.is_initialized())
570 return NULL;
571 if (my_head.value() == node->address().value())
572 return NULL;
573 Addr address(node->Data()->prev);
574 if (address.value() == node->address().value())
575 return NULL; // Another head? fail it.
576 prev.reset(new CacheRankingsBlock(backend_->File(address), address));
577 }
578
579 TrackRankingsBlock(prev.get(), true);
580
581 if (!GetRanking(prev.get()))
582 return NULL;
583
584 ConvertToLongLived(prev.get());
585 if (node && !CheckSingleLink(prev.get(), node))
586 return NULL;
587
588 return prev.release();
589 }
590
FreeRankingsBlock(CacheRankingsBlock * node)591 void Rankings::FreeRankingsBlock(CacheRankingsBlock* node) {
592 TrackRankingsBlock(node, false);
593 }
594
TrackRankingsBlock(CacheRankingsBlock * node,bool start_tracking)595 void Rankings::TrackRankingsBlock(CacheRankingsBlock* node,
596 bool start_tracking) {
597 if (!node)
598 return;
599
600 IteratorPair current(node->address().value(), node);
601
602 if (start_tracking)
603 iterators_.push_back(current);
604 else
605 iterators_.remove(current);
606 }
607
SelfCheck()608 int Rankings::SelfCheck() {
609 int total = 0;
610 for (int i = 0; i < LAST_ELEMENT; i++) {
611 int partial = CheckList(static_cast<List>(i));
612 if (partial < 0)
613 return partial;
614 total += partial;
615 }
616 return total;
617 }
618
SanityCheck(CacheRankingsBlock * node,bool from_list)619 bool Rankings::SanityCheck(CacheRankingsBlock* node, bool from_list) {
620 const RankingsNode* data = node->Data();
621 if (!data->contents)
622 return false;
623
624 // It may have never been inserted.
625 if (from_list && (!data->last_used || !data->last_modified))
626 return false;
627
628 if ((!data->next && data->prev) || (data->next && !data->prev))
629 return false;
630
631 // Both pointers on zero is a node out of the list.
632 if (!data->next && !data->prev && from_list)
633 return false;
634
635 if ((node->address().value() == data->prev) && !IsHead(data->prev))
636 return false;
637
638 if ((node->address().value() == data->next) && !IsTail(data->next))
639 return false;
640
641 return true;
642 }
643
ReadHeads()644 void Rankings::ReadHeads() {
645 for (int i = 0; i < LAST_ELEMENT; i++)
646 heads_[i] = Addr(control_data_->heads[i]);
647 }
648
ReadTails()649 void Rankings::ReadTails() {
650 for (int i = 0; i < LAST_ELEMENT; i++)
651 tails_[i] = Addr(control_data_->tails[i]);
652 }
653
WriteHead(List list)654 void Rankings::WriteHead(List list) {
655 control_data_->heads[list] = heads_[list].value();
656 }
657
WriteTail(List list)658 void Rankings::WriteTail(List list) {
659 control_data_->tails[list] = tails_[list].value();
660 }
661
CheckEntry(CacheRankingsBlock * rankings)662 bool Rankings::CheckEntry(CacheRankingsBlock* rankings) {
663 if (!rankings->Data()->dummy)
664 return true;
665
666 // If this entry is not dirty, it is a serious problem.
667 return backend_->GetCurrentEntryId() != rankings->Data()->dirty;
668 }
669
CheckLinks(CacheRankingsBlock * node,CacheRankingsBlock * prev,CacheRankingsBlock * next,List list)670 bool Rankings::CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev,
671 CacheRankingsBlock* next, List list) {
672 if ((prev->Data()->next != node->address().value() &&
673 heads_[list].value() != node->address().value()) ||
674 (next->Data()->prev != node->address().value() &&
675 tails_[list].value() != node->address().value())) {
676 LOG(ERROR) << "Inconsistent LRU.";
677
678 if (prev->Data()->next == next->address().value() &&
679 next->Data()->prev == prev->address().value()) {
680 // The list is actually ok, node is wrong.
681 node->Data()->next = 0;
682 node->Data()->prev = 0;
683 node->Store();
684 return false;
685 }
686 backend_->CriticalError(ERR_INVALID_LINKS);
687 return false;
688 }
689
690 return true;
691 }
692
CheckSingleLink(CacheRankingsBlock * prev,CacheRankingsBlock * next)693 bool Rankings::CheckSingleLink(CacheRankingsBlock* prev,
694 CacheRankingsBlock* next) {
695 if (prev->Data()->next != next->address().value() ||
696 next->Data()->prev != prev->address().value()) {
697 LOG(ERROR) << "Inconsistent LRU.";
698
699 backend_->CriticalError(ERR_INVALID_LINKS);
700 return false;
701 }
702
703 return true;
704 }
705
CheckList(List list)706 int Rankings::CheckList(List list) {
707 Addr& my_head = heads_[list];
708 Addr& my_tail = tails_[list];
709 if (!my_head.is_initialized()) {
710 if (!my_tail.is_initialized())
711 return 0;
712 // If there is no head, having a tail is an error.
713 return ERR_INVALID_TAIL;
714 }
715 // If there is no tail, having a head is an error.
716 if (!my_tail.is_initialized())
717 return ERR_INVALID_HEAD;
718
719 if (my_tail.is_separate_file())
720 return ERR_INVALID_TAIL;
721
722 if (my_head.is_separate_file())
723 return ERR_INVALID_HEAD;
724
725 int num_items = 0;
726 Addr address(my_head.value());
727 Addr prev(my_head.value());
728 scoped_ptr<CacheRankingsBlock> node;
729 do {
730 node.reset(new CacheRankingsBlock(backend_->File(address), address));
731 node->Load();
732 if (node->Data()->prev != prev.value())
733 return ERR_INVALID_PREV;
734 if (!CheckEntry(node.get()))
735 return ERR_INVALID_ENTRY;
736
737 prev.set_value(address.value());
738 address.set_value(node->Data()->next);
739 if (!address.is_initialized() || address.is_separate_file())
740 return ERR_INVALID_NEXT;
741
742 num_items++;
743 } while (node->address().value() != address.value());
744 return num_items;
745 }
746
IsHead(CacheAddr addr)747 bool Rankings::IsHead(CacheAddr addr) {
748 for (int i = 0; i < LAST_ELEMENT; i++)
749 if (addr == heads_[i].value())
750 return true;
751 return false;
752 }
753
IsTail(CacheAddr addr)754 bool Rankings::IsTail(CacheAddr addr) {
755 for (int i = 0; i < LAST_ELEMENT; i++)
756 if (addr == tails_[i].value())
757 return true;
758 return false;
759 }
760
761 // We expect to have just a few iterators at any given time, maybe two or three,
762 // But we could have more than one pointing at the same mode. We walk the list
763 // of cache iterators and update all that are pointing to the given node.
UpdateIterators(CacheRankingsBlock * node)764 void Rankings::UpdateIterators(CacheRankingsBlock* node) {
765 CacheAddr address = node->address().value();
766 for (IteratorList::iterator it = iterators_.begin(); it != iterators_.end();
767 ++it) {
768 if (it->first == address && it->second->HasData()) {
769 CacheRankingsBlock* other = it->second;
770 *other->Data() = *node->Data();
771 }
772 }
773 }
774
InvalidateIterators(CacheRankingsBlock * node)775 void Rankings::InvalidateIterators(CacheRankingsBlock* node) {
776 CacheAddr address = node->address().value();
777 for (IteratorList::iterator it = iterators_.begin(); it != iterators_.end();
778 ++it) {
779 if (it->first == address) {
780 LOG(WARNING) << "Invalidating iterator at 0x" << std::hex << address;
781 it->second->Discard();
782 }
783 }
784 }
785
IncrementCounter(List list)786 void Rankings::IncrementCounter(List list) {
787 if (!count_lists_)
788 return;
789
790 DCHECK(control_data_->sizes[list] < kint32max);
791 if (control_data_->sizes[list] < kint32max)
792 control_data_->sizes[list]++;
793 }
794
DecrementCounter(List list)795 void Rankings::DecrementCounter(List list) {
796 if (!count_lists_)
797 return;
798
799 DCHECK(control_data_->sizes[list] > 0);
800 if (control_data_->sizes[list] > 0)
801 control_data_->sizes[list]--;
802 }
803
804 } // namespace disk_cache
805