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