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  // 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.
83void 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|.
178void 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
187namespace disk_cache {
188
189Rankings::Iterator::Iterator(Rankings* rankings) {
190  memset(this, 0, sizeof(Iterator));
191  my_rankings = rankings;
192}
193
194Rankings::Iterator::~Iterator() {
195  for (int i = 0; i < 3; i++)
196    ScopedRankingsBlock(my_rankings, nodes[i]);
197}
198
199Rankings::Rankings() : init_(false) {}
200
201Rankings::~Rankings() {}
202
203bool 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
222void 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
231void 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()
301void Rankings::Remove(CacheRankingsBlock* node, List list, bool strict) {
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  if (strict)
306  InvalidateIterators(node);
307
308  Addr next_addr(node->Data()->next);
309  Addr prev_addr(node->Data()->prev);
310  if (!next_addr.is_initialized() || next_addr.is_separate_file() ||
311      !prev_addr.is_initialized() || prev_addr.is_separate_file()) {
312    if (next_addr.is_initialized() || prev_addr.is_initialized()) {
313      LOG(ERROR) << "Invalid rankings info.";
314    }
315    return;
316  }
317
318  CacheRankingsBlock next(backend_->File(next_addr), next_addr);
319  CacheRankingsBlock prev(backend_->File(prev_addr), prev_addr);
320  if (!GetRanking(&next) || !GetRanking(&prev))
321    return;
322
323  if (!CheckLinks(node, &prev, &next, &list))
324    return;
325
326  Transaction lock(control_data_, node->address(), REMOVE, list);
327  prev.Data()->next = next.address().value();
328  next.Data()->prev = prev.address().value();
329  GenerateCrash(ON_REMOVE_1);
330
331  CacheAddr node_value = node->address().value();
332  Addr& my_head = heads_[list];
333  Addr& my_tail = tails_[list];
334  if (node_value == my_head.value() || node_value == my_tail.value()) {
335    if (my_head.value() == my_tail.value()) {
336      my_head.set_value(0);
337      my_tail.set_value(0);
338
339      WriteHead(list);
340      GenerateCrash(ON_REMOVE_2);
341      WriteTail(list);
342      GenerateCrash(ON_REMOVE_3);
343    } else if (node_value == my_head.value()) {
344      my_head.set_value(next.address().value());
345      next.Data()->prev = next.address().value();
346
347      WriteHead(list);
348      GenerateCrash(ON_REMOVE_4);
349    } else if (node_value == my_tail.value()) {
350      my_tail.set_value(prev.address().value());
351      prev.Data()->next = prev.address().value();
352
353      WriteTail(list);
354      GenerateCrash(ON_REMOVE_5);
355
356      // Store the new tail to make sure we can undo the operation if we crash.
357      prev.Store();
358      GenerateCrash(ON_REMOVE_6);
359    }
360  }
361
362  // Nodes out of the list can be identified by invalid pointers.
363  node->Data()->next = 0;
364  node->Data()->prev = 0;
365
366  // The last thing to get to disk is the node itself, so before that there is
367  // enough info to recover.
368  next.Store();
369  GenerateCrash(ON_REMOVE_7);
370  prev.Store();
371  GenerateCrash(ON_REMOVE_8);
372  node->Store();
373  DecrementCounter(list);
374  UpdateIterators(&next);
375  UpdateIterators(&prev);
376}
377
378// A crash in between Remove and Insert will lead to a dirty entry not on the
379// list. We want to avoid that case as much as we can (as while waiting for IO),
380// but the net effect is just an assert on debug when attempting to remove the
381// entry. Otherwise we'll need reentrant transactions, which is an overkill.
382void Rankings::UpdateRank(CacheRankingsBlock* node, bool modified, List list) {
383  Addr& my_head = heads_[list];
384  if (my_head.value() == node->address().value()) {
385    UpdateTimes(node, modified);
386    node->set_modified();
387    return;
388  }
389
390  TimeTicks start = TimeTicks::Now();
391  Remove(node, list, true);
392  Insert(node, modified, list);
393  CACHE_UMA(AGE_MS, "UpdateRank", 0, start);
394}
395
396CacheRankingsBlock* Rankings::GetNext(CacheRankingsBlock* node, List list) {
397  ScopedRankingsBlock next(this);
398  if (!node) {
399    Addr& my_head = heads_[list];
400    if (!my_head.is_initialized())
401      return NULL;
402    next.reset(new CacheRankingsBlock(backend_->File(my_head), my_head));
403  } else {
404    if (!node->HasData())
405      node->Load();
406    Addr& my_tail = tails_[list];
407    if (!my_tail.is_initialized())
408      return NULL;
409    if (my_tail.value() == node->address().value())
410      return NULL;
411    Addr address(node->Data()->next);
412    if (address.value() == node->address().value())
413      return NULL;  // Another tail? fail it.
414    next.reset(new CacheRankingsBlock(backend_->File(address), address));
415  }
416
417  TrackRankingsBlock(next.get(), true);
418
419  if (!GetRanking(next.get()))
420    return NULL;
421
422  ConvertToLongLived(next.get());
423  if (node && !CheckSingleLink(node, next.get()))
424    return NULL;
425
426  return next.release();
427}
428
429CacheRankingsBlock* Rankings::GetPrev(CacheRankingsBlock* node, List list) {
430  ScopedRankingsBlock prev(this);
431  if (!node) {
432    Addr& my_tail = tails_[list];
433    if (!my_tail.is_initialized())
434      return NULL;
435    prev.reset(new CacheRankingsBlock(backend_->File(my_tail), my_tail));
436  } else {
437    if (!node->HasData())
438      node->Load();
439    Addr& my_head = heads_[list];
440    if (!my_head.is_initialized())
441      return NULL;
442    if (my_head.value() == node->address().value())
443      return NULL;
444    Addr address(node->Data()->prev);
445    if (address.value() == node->address().value())
446      return NULL;  // Another head? fail it.
447    prev.reset(new CacheRankingsBlock(backend_->File(address), address));
448  }
449
450  TrackRankingsBlock(prev.get(), true);
451
452  if (!GetRanking(prev.get()))
453    return NULL;
454
455  ConvertToLongLived(prev.get());
456  if (node && !CheckSingleLink(prev.get(), node))
457    return NULL;
458
459  return prev.release();
460}
461
462void Rankings::FreeRankingsBlock(CacheRankingsBlock* node) {
463  TrackRankingsBlock(node, false);
464}
465
466void Rankings::TrackRankingsBlock(CacheRankingsBlock* node,
467                                  bool start_tracking) {
468  if (!node)
469    return;
470
471  IteratorPair current(node->address().value(), node);
472
473  if (start_tracking)
474    iterators_.push_back(current);
475  else
476    iterators_.remove(current);
477}
478
479int Rankings::SelfCheck() {
480  int total = 0;
481  for (int i = 0; i < LAST_ELEMENT; i++) {
482    int partial = CheckList(static_cast<List>(i));
483    if (partial < 0)
484      return partial;
485    total += partial;
486  }
487  return total;
488}
489
490bool Rankings::SanityCheck(CacheRankingsBlock* node, bool from_list) const {
491  const RankingsNode* data = node->Data();
492
493  if ((!data->next && data->prev) || (data->next && !data->prev))
494    return false;
495
496  // Both pointers on zero is a node out of the list.
497  if (!data->next && !data->prev && from_list)
498    return false;
499
500  List list = NO_USE;  // Initialize it to something.
501  if ((node->address().value() == data->prev) && !IsHead(data->prev, &list))
502    return false;
503
504  if ((node->address().value() == data->next) && !IsTail(data->next, &list))
505    return false;
506
507  if (!data->next && !data->prev)
508    return true;
509
510  Addr next_addr(data->next);
511  Addr prev_addr(data->prev);
512  if (!next_addr.SanityCheck() || next_addr.file_type() != RANKINGS ||
513      !prev_addr.SanityCheck() || prev_addr.file_type() != RANKINGS)
514    return false;
515
516  return true;
517}
518
519bool Rankings::DataSanityCheck(CacheRankingsBlock* node, bool from_list) const {
520  const RankingsNode* data = node->Data();
521  if (!data->contents)
522    return false;
523
524  // It may have never been inserted.
525  if (from_list && (!data->last_used || !data->last_modified))
526    return false;
527
528  return true;
529}
530
531void Rankings::SetContents(CacheRankingsBlock* node, CacheAddr address) {
532  node->Data()->contents = address;
533  node->Store();
534}
535
536void Rankings::ReadHeads() {
537  for (int i = 0; i < LAST_ELEMENT; i++)
538    heads_[i] = Addr(control_data_->heads[i]);
539}
540
541void Rankings::ReadTails() {
542  for (int i = 0; i < LAST_ELEMENT; i++)
543    tails_[i] = Addr(control_data_->tails[i]);
544}
545
546void Rankings::WriteHead(List list) {
547  control_data_->heads[list] = heads_[list].value();
548}
549
550void Rankings::WriteTail(List list) {
551  control_data_->tails[list] = tails_[list].value();
552}
553
554bool Rankings::GetRanking(CacheRankingsBlock* rankings) {
555  if (!rankings->address().is_initialized())
556    return false;
557
558  TimeTicks start = TimeTicks::Now();
559  if (!rankings->Load())
560    return false;
561
562  if (!SanityCheck(rankings, true)) {
563    backend_->CriticalError(ERR_INVALID_LINKS);
564    return false;
565  }
566
567  backend_->OnEvent(Stats::OPEN_RANKINGS);
568
569  // "dummy" is the old "pointer" value, so it has to be 0.
570  if (!rankings->Data()->dirty && !rankings->Data()->dummy)
571    return true;
572
573  EntryImpl* entry = backend_->GetOpenEntry(rankings);
574  if (!entry) {
575    // We cannot trust this entry, but we cannot initiate a cleanup from this
576    // point (we may be in the middle of a cleanup already). Just get rid of
577    // the invalid pointer and continue; the entry will be deleted when detected
578    // from a regular open/create path.
579    rankings->Data()->dummy = 0;
580    rankings->Data()->dirty = backend_->GetCurrentEntryId() - 1;
581    if (!rankings->Data()->dirty)
582      rankings->Data()->dirty--;
583    return true;
584  }
585
586  // Note that we should not leave this module without deleting rankings first.
587  rankings->SetData(entry->rankings()->Data());
588
589  CACHE_UMA(AGE_MS, "GetRankings", 0, start);
590  return true;
591}
592
593void Rankings::ConvertToLongLived(CacheRankingsBlock* rankings) {
594  if (rankings->own_data())
595    return;
596
597  // We cannot return a shared node because we are not keeping a reference
598  // to the entry that owns the buffer. Make this node a copy of the one that
599  // we have, and let the iterator logic update it when the entry changes.
600  CacheRankingsBlock temp(NULL, Addr(0));
601  *temp.Data() = *rankings->Data();
602  rankings->StopSharingData();
603  *rankings->Data() = *temp.Data();
604}
605
606void Rankings::CompleteTransaction() {
607  Addr node_addr(static_cast<CacheAddr>(control_data_->transaction));
608  if (!node_addr.is_initialized() || node_addr.is_separate_file()) {
609    NOTREACHED();
610    LOG(ERROR) << "Invalid rankings info.";
611    return;
612  }
613
614  Trace("CompleteTransaction 0x%x", node_addr.value());
615
616  CacheRankingsBlock node(backend_->File(node_addr), node_addr);
617  if (!node.Load())
618    return;
619
620  node.Data()->dummy = 0;
621  node.Store();
622
623  Addr& my_head = heads_[control_data_->operation_list];
624  Addr& my_tail = tails_[control_data_->operation_list];
625
626  // We want to leave the node inside the list. The entry must me marked as
627  // dirty, and will be removed later. Otherwise, we'll get assertions when
628  // attempting to remove the dirty entry.
629  if (INSERT == control_data_->operation) {
630    Trace("FinishInsert h:0x%x t:0x%x", my_head.value(), my_tail.value());
631    FinishInsert(&node);
632  } else if (REMOVE == control_data_->operation) {
633    Trace("RevertRemove h:0x%x t:0x%x", my_head.value(), my_tail.value());
634    RevertRemove(&node);
635  } else {
636    NOTREACHED();
637    LOG(ERROR) << "Invalid operation to recover.";
638  }
639}
640
641void Rankings::FinishInsert(CacheRankingsBlock* node) {
642  control_data_->transaction = 0;
643  control_data_->operation = 0;
644  Addr& my_head = heads_[control_data_->operation_list];
645  Addr& my_tail = tails_[control_data_->operation_list];
646  if (my_head.value() != node->address().value()) {
647    if (my_tail.value() == node->address().value()) {
648      // This part will be skipped by the logic of Insert.
649      node->Data()->next = my_tail.value();
650    }
651
652    Insert(node, true, static_cast<List>(control_data_->operation_list));
653  }
654
655  // Tell the backend about this entry.
656  backend_->RecoveredEntry(node);
657}
658
659void Rankings::RevertRemove(CacheRankingsBlock* node) {
660  Addr next_addr(node->Data()->next);
661  Addr prev_addr(node->Data()->prev);
662  if (!next_addr.is_initialized() || !prev_addr.is_initialized()) {
663    // The operation actually finished. Nothing to do.
664    control_data_->transaction = 0;
665    return;
666  }
667  if (next_addr.is_separate_file() || prev_addr.is_separate_file()) {
668    NOTREACHED();
669    LOG(WARNING) << "Invalid rankings info.";
670    control_data_->transaction = 0;
671    return;
672  }
673
674  CacheRankingsBlock next(backend_->File(next_addr), next_addr);
675  CacheRankingsBlock prev(backend_->File(prev_addr), prev_addr);
676  if (!next.Load() || !prev.Load())
677    return;
678
679  CacheAddr node_value = node->address().value();
680  DCHECK(prev.Data()->next == node_value ||
681         prev.Data()->next == prev_addr.value() ||
682         prev.Data()->next == next.address().value());
683  DCHECK(next.Data()->prev == node_value ||
684         next.Data()->prev == next_addr.value() ||
685         next.Data()->prev == prev.address().value());
686
687  if (node_value != prev_addr.value())
688    prev.Data()->next = node_value;
689  if (node_value != next_addr.value())
690    next.Data()->prev = node_value;
691
692  List my_list = static_cast<List>(control_data_->operation_list);
693  Addr& my_head = heads_[my_list];
694  Addr& my_tail = tails_[my_list];
695  if (!my_head.is_initialized() || !my_tail.is_initialized()) {
696    my_head.set_value(node_value);
697    my_tail.set_value(node_value);
698    WriteHead(my_list);
699    WriteTail(my_list);
700  } else if (my_head.value() == next.address().value()) {
701    my_head.set_value(node_value);
702    prev.Data()->next = next.address().value();
703    WriteHead(my_list);
704  } else if (my_tail.value() == prev.address().value()) {
705    my_tail.set_value(node_value);
706    next.Data()->prev = prev.address().value();
707    WriteTail(my_list);
708  }
709
710  next.Store();
711  prev.Store();
712  control_data_->transaction = 0;
713  control_data_->operation = 0;
714}
715
716bool Rankings::CheckEntry(CacheRankingsBlock* rankings) {
717  if (!rankings->Data()->dummy)
718    return true;
719
720  // If this entry is not dirty, it is a serious problem.
721  return backend_->GetCurrentEntryId() != rankings->Data()->dirty;
722}
723
724bool Rankings::CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev,
725                          CacheRankingsBlock* next, List* list) {
726  CacheAddr node_addr = node->address().value();
727  if (prev->Data()->next == node_addr &&
728      next->Data()->prev == node_addr) {
729    // A regular linked node.
730    return true;
731  }
732
733  Trace("CheckLinks 0x%x (0x%x 0x%x)", node_addr,
734        prev->Data()->next, next->Data()->prev);
735
736  if (node_addr != prev->address().value() &&
737      node_addr != next->address().value() &&
738      prev->Data()->next == next->address().value() &&
739      next->Data()->prev == prev->address().value()) {
740    // The list is actually ok, node is wrong.
741    Trace("node 0x%x out of list %d", node_addr, list);
742    node->Data()->next = 0;
743    node->Data()->prev = 0;
744    node->Store();
745    return false;
746  }
747
748  if (prev->Data()->next == node_addr ||
749      next->Data()->prev == node_addr) {
750    // Only one link is weird, lets double check.
751    if (prev->Data()->next != node_addr && IsHead(node_addr, list))
752      return true;
753
754    if (next->Data()->prev != node_addr && IsTail(node_addr, list))
755      return true;
756  }
757
758  LOG(ERROR) << "Inconsistent LRU.";
759  backend_->CriticalError(ERR_INVALID_LINKS);
760  return false;
761}
762
763bool Rankings::CheckSingleLink(CacheRankingsBlock* prev,
764                               CacheRankingsBlock* next) {
765  if (prev->Data()->next != next->address().value() ||
766      next->Data()->prev != prev->address().value()) {
767    LOG(ERROR) << "Inconsistent LRU.";
768
769    backend_->CriticalError(ERR_INVALID_LINKS);
770    return false;
771  }
772
773  return true;
774}
775
776int Rankings::CheckList(List list) {
777  Addr& my_head = heads_[list];
778  Addr& my_tail = tails_[list];
779  if (!my_head.is_initialized()) {
780    if (!my_tail.is_initialized())
781      return 0;
782    // If there is no head, having a tail is an error.
783    return ERR_INVALID_TAIL;
784  }
785  // If there is no tail, having a head is an error.
786  if (!my_tail.is_initialized())
787    return ERR_INVALID_HEAD;
788
789  if (my_tail.is_separate_file())
790    return ERR_INVALID_TAIL;
791
792  if (my_head.is_separate_file())
793    return ERR_INVALID_HEAD;
794
795  int num_items = 0;
796  Addr address(my_head.value());
797  Addr prev(my_head.value());
798  scoped_ptr<CacheRankingsBlock> node;
799  do {
800    node.reset(new CacheRankingsBlock(backend_->File(address), address));
801    node->Load();
802    if (node->Data()->prev != prev.value())
803      return ERR_INVALID_PREV;
804    if (!CheckEntry(node.get()))
805      return ERR_INVALID_ENTRY;
806
807    prev.set_value(address.value());
808    address.set_value(node->Data()->next);
809    if (!address.is_initialized() || address.is_separate_file())
810      return ERR_INVALID_NEXT;
811
812    num_items++;
813  } while (node->address().value() != address.value());
814  return num_items;
815}
816
817bool Rankings::IsHead(CacheAddr addr, List* list) const {
818  for (int i = 0; i < LAST_ELEMENT; i++) {
819    if (addr == heads_[i].value()) {
820      if (*list != i)
821        Trace("Changing list %d to %d", *list, i);
822      *list = static_cast<List>(i);
823      return true;
824    }
825  }
826  return false;
827}
828
829bool Rankings::IsTail(CacheAddr addr, List* list) const {
830  for (int i = 0; i < LAST_ELEMENT; i++) {
831    if (addr == tails_[i].value()) {
832      if (*list != i)
833        Trace("Changing list %d to %d", *list, i);
834      *list = static_cast<List>(i);
835      return true;
836    }
837  }
838  return false;
839}
840
841// We expect to have just a few iterators at any given time, maybe two or three,
842// But we could have more than one pointing at the same mode. We walk the list
843// of cache iterators and update all that are pointing to the given node.
844void Rankings::UpdateIterators(CacheRankingsBlock* node) {
845  CacheAddr address = node->address().value();
846  for (IteratorList::iterator it = iterators_.begin(); it != iterators_.end();
847       ++it) {
848    if (it->first == address && it->second->HasData()) {
849      CacheRankingsBlock* other = it->second;
850      *other->Data() = *node->Data();
851    }
852  }
853}
854
855void Rankings::InvalidateIterators(CacheRankingsBlock* node) {
856  CacheAddr address = node->address().value();
857  for (IteratorList::iterator it = iterators_.begin(); it != iterators_.end();
858       ++it) {
859    if (it->first == address) {
860#ifndef ANDROID
861// Confirmed with chromium developers that this is normal, and removing from
862// Android to close bug 3239659
863      LOG(WARNING) << "Invalidating iterator at 0x" << std::hex << address;
864#endif
865      it->second->Discard();
866    }
867  }
868}
869
870void Rankings::IncrementCounter(List list) {
871  if (!count_lists_)
872    return;
873
874  DCHECK(control_data_->sizes[list] < kint32max);
875  if (control_data_->sizes[list] < kint32max)
876    control_data_->sizes[list]++;
877}
878
879void Rankings::DecrementCounter(List list) {
880  if (!count_lists_)
881    return;
882
883  DCHECK(control_data_->sizes[list] > 0);
884  if (control_data_->sizes[list] > 0)
885    control_data_->sizes[list]--;
886}
887
888}  // namespace disk_cache
889