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