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