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