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