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(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 926