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