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
13using base::Time;
14
15// This is used by crash_cache.exe to generate unit test files.
16disk_cache::RankCrashes g_rankings_crash = disk_cache::NO_CRASH;
17
18namespace {
19
20enum 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.
30class 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
44Transaction::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
54Transaction::~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.
62enum 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
67void 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.
80void 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
176namespace disk_cache {
177
178bool 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
197void 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
206bool 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
245void 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
258void 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()
331void 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.
408void 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
415void 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
450void 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
468void 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
525CacheRankingsBlock* 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
558CacheRankingsBlock* 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
591void Rankings::FreeRankingsBlock(CacheRankingsBlock* node) {
592  TrackRankingsBlock(node, false);
593}
594
595void 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
608int 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
619bool 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
644void Rankings::ReadHeads() {
645  for (int i = 0; i < LAST_ELEMENT; i++)
646    heads_[i] = Addr(control_data_->heads[i]);
647}
648
649void Rankings::ReadTails() {
650  for (int i = 0; i < LAST_ELEMENT; i++)
651    tails_[i] = Addr(control_data_->tails[i]);
652}
653
654void Rankings::WriteHead(List list) {
655  control_data_->heads[list] = heads_[list].value();
656}
657
658void Rankings::WriteTail(List list) {
659  control_data_->tails[list] = tails_[list].value();
660}
661
662bool 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
670bool 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
693bool 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
706int 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
747bool 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
754bool 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.
764void 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
775void 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
786void 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
795void 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