net/disk_cache/rankings.cc

   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/rankings.h"
   6
   7 #include "base/metrics/histogram.h"
   8 #include "net/disk_cache/backend_impl.h"
   9 #include "net/disk_cache/disk_format.h"
  10 #include "net/disk_cache/entry_impl.h"
  11 #include "net/disk_cache/errors.h"
  12 #include "net/disk_cache/histogram_macros.h"
  13 #include "net/disk_cache/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