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