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