diff options
Diffstat (limited to 'chromium/net/disk_cache/blockfile/rankings.cc')
| -rw-r--r-- | chromium/net/disk_cache/blockfile/rankings.cc | 925 |
1 files changed, 925 insertions, 0 deletions
diff --git a/chromium/net/disk_cache/blockfile/rankings.cc b/chromium/net/disk_cache/blockfile/rankings.cc new file mode 100644 index 00000000000..7c93b431bcb --- /dev/null +++ b/chromium/net/disk_cache/blockfile/rankings.cc @@ -0,0 +1,925 @@ +// Copyright (c) 2012 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "net/disk_cache/blockfile/rankings.h" + +#include "base/metrics/histogram.h" +#include "net/disk_cache/blockfile/backend_impl.h" +#include "net/disk_cache/blockfile/disk_format.h" +#include "net/disk_cache/blockfile/entry_impl.h" +#include "net/disk_cache/blockfile/errors.h" +#include "net/disk_cache/blockfile/histogram_macros.h" +#include "net/disk_cache/blockfile/stress_support.h" + +// Provide a BackendImpl object to macros from histogram_macros.h. +#define CACHE_UMA_BACKEND_IMPL_OBJ backend_ + +using base::Time; +using base::TimeTicks; + +namespace disk_cache { +// This is used by crash_cache.exe to generate unit test files. +NET_EXPORT_PRIVATE RankCrashes g_rankings_crash = NO_CRASH; +} + +namespace { + +enum Operation { + INSERT = 1, + REMOVE +}; + +// This class provides a simple lock for the LRU list of rankings. Whenever an +// entry is to be inserted or removed from the list, a transaction object should +// be created to keep track of the operation. If the process crashes before +// finishing the operation, the transaction record (stored as part of the user +// data on the file header) can be used to finish the operation. +class Transaction { + public: + // addr is the cache addres of the node being inserted or removed. We want to + // avoid having the compiler doing optimizations on when to read or write + // from user_data because it is the basis of the crash detection. Maybe + // volatile is not enough for that, but it should be a good hint. + Transaction(volatile disk_cache::LruData* data, disk_cache::Addr addr, + Operation op, int list); + ~Transaction(); + private: + volatile disk_cache::LruData* data_; + DISALLOW_COPY_AND_ASSIGN(Transaction); +}; + +Transaction::Transaction(volatile disk_cache::LruData* data, + disk_cache::Addr addr, Operation op, int list) + : data_(data) { + DCHECK(!data_->transaction); + DCHECK(addr.is_initialized()); + data_->operation = op; + data_->operation_list = list; + data_->transaction = addr.value(); +} + +Transaction::~Transaction() { + DCHECK(data_->transaction); + data_->transaction = 0; + data_->operation = 0; + data_->operation_list = 0; +} + +// Code locations that can generate crashes. +enum CrashLocation { + ON_INSERT_1, ON_INSERT_2, ON_INSERT_3, ON_INSERT_4, ON_REMOVE_1, ON_REMOVE_2, + ON_REMOVE_3, ON_REMOVE_4, ON_REMOVE_5, ON_REMOVE_6, ON_REMOVE_7, ON_REMOVE_8 +}; + +#ifndef NDEBUG +void TerminateSelf() { +#if defined(OS_WIN) + // Windows does more work on _exit() than we would like, so we force exit. + TerminateProcess(GetCurrentProcess(), 0); +#elif defined(OS_POSIX) + // On POSIX, _exit() will terminate the process with minimal cleanup, + // and it is cleaner than killing. + _exit(0); +#endif +} +#endif // NDEBUG + +// Generates a crash on debug builds, acording to the value of g_rankings_crash. +// This used by crash_cache.exe to generate unit-test files. +void GenerateCrash(CrashLocation location) { +#ifndef NDEBUG + if (disk_cache::NO_CRASH == disk_cache::g_rankings_crash) + return; + switch (location) { + case ON_INSERT_1: + switch (disk_cache::g_rankings_crash) { + case disk_cache::INSERT_ONE_1: + case disk_cache::INSERT_LOAD_1: + TerminateSelf(); + default: + break; + } + break; + case ON_INSERT_2: + if (disk_cache::INSERT_EMPTY_1 == disk_cache::g_rankings_crash) + TerminateSelf(); + break; + case ON_INSERT_3: + switch (disk_cache::g_rankings_crash) { + case disk_cache::INSERT_EMPTY_2: + case disk_cache::INSERT_ONE_2: + case disk_cache::INSERT_LOAD_2: + TerminateSelf(); + default: + break; + } + break; + case ON_INSERT_4: + switch (disk_cache::g_rankings_crash) { + case disk_cache::INSERT_EMPTY_3: + case disk_cache::INSERT_ONE_3: + TerminateSelf(); + default: + break; + } + break; + case ON_REMOVE_1: + switch (disk_cache::g_rankings_crash) { + case disk_cache::REMOVE_ONE_1: + case disk_cache::REMOVE_HEAD_1: + case disk_cache::REMOVE_TAIL_1: + case disk_cache::REMOVE_LOAD_1: + TerminateSelf(); + default: + break; + } + break; + case ON_REMOVE_2: + if (disk_cache::REMOVE_ONE_2 == disk_cache::g_rankings_crash) + TerminateSelf(); + break; + case ON_REMOVE_3: + if (disk_cache::REMOVE_ONE_3 == disk_cache::g_rankings_crash) + TerminateSelf(); + break; + case ON_REMOVE_4: + if (disk_cache::REMOVE_HEAD_2 == disk_cache::g_rankings_crash) + TerminateSelf(); + break; + case ON_REMOVE_5: + if (disk_cache::REMOVE_TAIL_2 == disk_cache::g_rankings_crash) + TerminateSelf(); + break; + case ON_REMOVE_6: + if (disk_cache::REMOVE_TAIL_3 == disk_cache::g_rankings_crash) + TerminateSelf(); + break; + case ON_REMOVE_7: + switch (disk_cache::g_rankings_crash) { + case disk_cache::REMOVE_ONE_4: + case disk_cache::REMOVE_LOAD_2: + case disk_cache::REMOVE_HEAD_3: + TerminateSelf(); + default: + break; + } + break; + case ON_REMOVE_8: + switch (disk_cache::g_rankings_crash) { + case disk_cache::REMOVE_HEAD_4: + case disk_cache::REMOVE_LOAD_3: + TerminateSelf(); + default: + break; + } + break; + default: + NOTREACHED(); + return; + } +#endif // NDEBUG +} + +// Update the timestamp fields of |node|. +void UpdateTimes(disk_cache::CacheRankingsBlock* node, bool modified) { + base::Time now = base::Time::Now(); + node->Data()->last_used = now.ToInternalValue(); + if (modified) + node->Data()->last_modified = now.ToInternalValue(); +} + +} // namespace + +namespace disk_cache { + +Rankings::ScopedRankingsBlock::ScopedRankingsBlock() : rankings_(NULL) {} + +Rankings::ScopedRankingsBlock::ScopedRankingsBlock(Rankings* rankings) + : rankings_(rankings) {} + +Rankings::ScopedRankingsBlock::ScopedRankingsBlock( + Rankings* rankings, CacheRankingsBlock* node) + : scoped_ptr<CacheRankingsBlock>(node), rankings_(rankings) {} + +Rankings::Iterator::Iterator(Rankings* rankings) { + memset(this, 0, sizeof(Iterator)); + my_rankings = rankings; +} + +Rankings::Iterator::~Iterator() { + for (int i = 0; i < 3; i++) + ScopedRankingsBlock(my_rankings, nodes[i]); +} + +Rankings::Rankings() : init_(false) {} + +Rankings::~Rankings() {} + +bool Rankings::Init(BackendImpl* backend, bool count_lists) { + DCHECK(!init_); + if (init_) + return false; + + backend_ = backend; + control_data_ = backend_->GetLruData(); + count_lists_ = count_lists; + + ReadHeads(); + ReadTails(); + + if (control_data_->transaction) + CompleteTransaction(); + + init_ = true; + return true; +} + +void Rankings::Reset() { + init_ = false; + for (int i = 0; i < LAST_ELEMENT; i++) { + heads_[i].set_value(0); + tails_[i].set_value(0); + } + control_data_ = NULL; +} + +void Rankings::Insert(CacheRankingsBlock* node, bool modified, List list) { + Trace("Insert 0x%x l %d", node->address().value(), list); + DCHECK(node->HasData()); + Addr& my_head = heads_[list]; + Addr& my_tail = tails_[list]; + Transaction lock(control_data_, node->address(), INSERT, list); + CacheRankingsBlock head(backend_->File(my_head), my_head); + if (my_head.is_initialized()) { + if (!GetRanking(&head)) + return; + + if (head.Data()->prev != my_head.value() && // Normal path. + head.Data()->prev != node->address().value()) { // FinishInsert(). + backend_->CriticalError(ERR_INVALID_LINKS); + return; + } + + head.Data()->prev = node->address().value(); + head.Store(); + GenerateCrash(ON_INSERT_1); + UpdateIterators(&head); + } + + node->Data()->next = my_head.value(); + node->Data()->prev = node->address().value(); + my_head.set_value(node->address().value()); + + if (!my_tail.is_initialized() || my_tail.value() == node->address().value()) { + my_tail.set_value(node->address().value()); + node->Data()->next = my_tail.value(); + WriteTail(list); + GenerateCrash(ON_INSERT_2); + } + + UpdateTimes(node, modified); + node->Store(); + GenerateCrash(ON_INSERT_3); + + // The last thing to do is move our head to point to a node already stored. + WriteHead(list); + IncrementCounter(list); + GenerateCrash(ON_INSERT_4); + backend_->FlushIndex(); +} + +// If a, b and r are elements on the list, and we want to remove r, the possible +// states for the objects if a crash happens are (where y(x, z) means for object +// y, prev is x and next is z): +// A. One element: +// 1. r(r, r), head(r), tail(r) initial state +// 2. r(r, r), head(0), tail(r) WriteHead() +// 3. r(r, r), head(0), tail(0) WriteTail() +// 4. r(0, 0), head(0), tail(0) next.Store() +// +// B. Remove a random element: +// 1. a(x, r), r(a, b), b(r, y), head(x), tail(y) initial state +// 2. a(x, r), r(a, b), b(a, y), head(x), tail(y) next.Store() +// 3. a(x, b), r(a, b), b(a, y), head(x), tail(y) prev.Store() +// 4. a(x, b), r(0, 0), b(a, y), head(x), tail(y) node.Store() +// +// C. Remove head: +// 1. r(r, b), b(r, y), head(r), tail(y) initial state +// 2. r(r, b), b(r, y), head(b), tail(y) WriteHead() +// 3. r(r, b), b(b, y), head(b), tail(y) next.Store() +// 4. r(0, 0), b(b, y), head(b), tail(y) prev.Store() +// +// D. Remove tail: +// 1. a(x, r), r(a, r), head(x), tail(r) initial state +// 2. a(x, r), r(a, r), head(x), tail(a) WriteTail() +// 3. a(x, a), r(a, r), head(x), tail(a) prev.Store() +// 4. a(x, a), r(0, 0), head(x), tail(a) next.Store() +void Rankings::Remove(CacheRankingsBlock* node, List list, bool strict) { + Trace("Remove 0x%x (0x%x 0x%x) l %d", node->address().value(), + node->Data()->next, node->Data()->prev, list); + DCHECK(node->HasData()); + if (strict) + InvalidateIterators(node); + + Addr next_addr(node->Data()->next); + Addr prev_addr(node->Data()->prev); + if (!next_addr.is_initialized() || next_addr.is_separate_file() || + !prev_addr.is_initialized() || prev_addr.is_separate_file()) { + if (next_addr.is_initialized() || prev_addr.is_initialized()) { + LOG(ERROR) << "Invalid rankings info."; + STRESS_NOTREACHED(); + } + return; + } + + CacheRankingsBlock next(backend_->File(next_addr), next_addr); + CacheRankingsBlock prev(backend_->File(prev_addr), prev_addr); + if (!GetRanking(&next) || !GetRanking(&prev)) { + STRESS_NOTREACHED(); + return; + } + + if (!CheckLinks(node, &prev, &next, &list)) + return; + + Transaction lock(control_data_, node->address(), REMOVE, list); + prev.Data()->next = next.address().value(); + next.Data()->prev = prev.address().value(); + GenerateCrash(ON_REMOVE_1); + + CacheAddr node_value = node->address().value(); + Addr& my_head = heads_[list]; + Addr& my_tail = tails_[list]; + if (node_value == my_head.value() || node_value == my_tail.value()) { + if (my_head.value() == my_tail.value()) { + my_head.set_value(0); + my_tail.set_value(0); + + WriteHead(list); + GenerateCrash(ON_REMOVE_2); + WriteTail(list); + GenerateCrash(ON_REMOVE_3); + } else if (node_value == my_head.value()) { + my_head.set_value(next.address().value()); + next.Data()->prev = next.address().value(); + + WriteHead(list); + GenerateCrash(ON_REMOVE_4); + } else if (node_value == my_tail.value()) { + my_tail.set_value(prev.address().value()); + prev.Data()->next = prev.address().value(); + + WriteTail(list); + GenerateCrash(ON_REMOVE_5); + + // Store the new tail to make sure we can undo the operation if we crash. + prev.Store(); + GenerateCrash(ON_REMOVE_6); + } + } + + // Nodes out of the list can be identified by invalid pointers. + node->Data()->next = 0; + node->Data()->prev = 0; + + // The last thing to get to disk is the node itself, so before that there is + // enough info to recover. + next.Store(); + GenerateCrash(ON_REMOVE_7); + prev.Store(); + GenerateCrash(ON_REMOVE_8); + node->Store(); + DecrementCounter(list); + UpdateIterators(&next); + UpdateIterators(&prev); + backend_->FlushIndex(); +} + +// A crash in between Remove and Insert will lead to a dirty entry not on the +// list. We want to avoid that case as much as we can (as while waiting for IO), +// but the net effect is just an assert on debug when attempting to remove the +// entry. Otherwise we'll need reentrant transactions, which is an overkill. +void Rankings::UpdateRank(CacheRankingsBlock* node, bool modified, List list) { + Addr& my_head = heads_[list]; + if (my_head.value() == node->address().value()) { + UpdateTimes(node, modified); + node->set_modified(); + return; + } + + TimeTicks start = TimeTicks::Now(); + Remove(node, list, true); + Insert(node, modified, list); + CACHE_UMA(AGE_MS, "UpdateRank", 0, start); +} + +CacheRankingsBlock* Rankings::GetNext(CacheRankingsBlock* node, List list) { + ScopedRankingsBlock next(this); + if (!node) { + Addr& my_head = heads_[list]; + if (!my_head.is_initialized()) + return NULL; + next.reset(new CacheRankingsBlock(backend_->File(my_head), my_head)); + } else { + if (!node->HasData()) + node->Load(); + Addr& my_tail = tails_[list]; + if (!my_tail.is_initialized()) + return NULL; + if (my_tail.value() == node->address().value()) + return NULL; + Addr address(node->Data()->next); + if (address.value() == node->address().value()) + return NULL; // Another tail? fail it. + next.reset(new CacheRankingsBlock(backend_->File(address), address)); + } + + TrackRankingsBlock(next.get(), true); + + if (!GetRanking(next.get())) + return NULL; + + ConvertToLongLived(next.get()); + if (node && !CheckSingleLink(node, next.get())) + return NULL; + + return next.release(); +} + +CacheRankingsBlock* Rankings::GetPrev(CacheRankingsBlock* node, List list) { + ScopedRankingsBlock prev(this); + if (!node) { + Addr& my_tail = tails_[list]; + if (!my_tail.is_initialized()) + return NULL; + prev.reset(new CacheRankingsBlock(backend_->File(my_tail), my_tail)); + } else { + if (!node->HasData()) + node->Load(); + Addr& my_head = heads_[list]; + if (!my_head.is_initialized()) + return NULL; + if (my_head.value() == node->address().value()) + return NULL; + Addr address(node->Data()->prev); + if (address.value() == node->address().value()) + return NULL; // Another head? fail it. + prev.reset(new CacheRankingsBlock(backend_->File(address), address)); + } + + TrackRankingsBlock(prev.get(), true); + + if (!GetRanking(prev.get())) + return NULL; + + ConvertToLongLived(prev.get()); + if (node && !CheckSingleLink(prev.get(), node)) + return NULL; + + return prev.release(); +} + +void Rankings::FreeRankingsBlock(CacheRankingsBlock* node) { + TrackRankingsBlock(node, false); +} + +void Rankings::TrackRankingsBlock(CacheRankingsBlock* node, + bool start_tracking) { + if (!node) + return; + + IteratorPair current(node->address().value(), node); + + if (start_tracking) + iterators_.push_back(current); + else + iterators_.remove(current); +} + +int Rankings::SelfCheck() { + int total = 0; + int error = 0; + for (int i = 0; i < LAST_ELEMENT; i++) { + int partial = CheckList(static_cast<List>(i)); + if (partial < 0 && !error) + error = partial; + else if (partial > 0) + total += partial; + } + + return error ? error : total; +} + +bool Rankings::SanityCheck(CacheRankingsBlock* node, bool from_list) const { + if (!node->VerifyHash()) + return false; + + const RankingsNode* data = node->Data(); + + if ((!data->next && data->prev) || (data->next && !data->prev)) + return false; + + // Both pointers on zero is a node out of the list. + if (!data->next && !data->prev && from_list) + return false; + + List list = NO_USE; // Initialize it to something. + if ((node->address().value() == data->prev) && !IsHead(data->prev, &list)) + return false; + + if ((node->address().value() == data->next) && !IsTail(data->next, &list)) + return false; + + if (!data->next && !data->prev) + return true; + + Addr next_addr(data->next); + Addr prev_addr(data->prev); + if (!next_addr.SanityCheckV2() || next_addr.file_type() != RANKINGS || + !prev_addr.SanityCheckV2() || prev_addr.file_type() != RANKINGS) + return false; + + return true; +} + +bool Rankings::DataSanityCheck(CacheRankingsBlock* node, bool from_list) const { + const RankingsNode* data = node->Data(); + if (!data->contents) + return false; + + // It may have never been inserted. + if (from_list && (!data->last_used || !data->last_modified)) + return false; + + return true; +} + +void Rankings::SetContents(CacheRankingsBlock* node, CacheAddr address) { + node->Data()->contents = address; + node->Store(); +} + +void Rankings::ReadHeads() { + for (int i = 0; i < LAST_ELEMENT; i++) + heads_[i] = Addr(control_data_->heads[i]); +} + +void Rankings::ReadTails() { + for (int i = 0; i < LAST_ELEMENT; i++) + tails_[i] = Addr(control_data_->tails[i]); +} + +void Rankings::WriteHead(List list) { + control_data_->heads[list] = heads_[list].value(); +} + +void Rankings::WriteTail(List list) { + control_data_->tails[list] = tails_[list].value(); +} + +bool Rankings::GetRanking(CacheRankingsBlock* rankings) { + if (!rankings->address().is_initialized()) + return false; + + TimeTicks start = TimeTicks::Now(); + if (!rankings->Load()) + return false; + + if (!SanityCheck(rankings, true)) { + backend_->CriticalError(ERR_INVALID_LINKS); + return false; + } + + backend_->OnEvent(Stats::OPEN_RANKINGS); + + // Note that if the cache is in read_only mode, open entries are not marked + // as dirty, except when an entry is doomed. We have to look for open entries. + if (!backend_->read_only() && !rankings->Data()->dirty) + return true; + + EntryImpl* entry = backend_->GetOpenEntry(rankings); + if (!entry) { + if (backend_->read_only()) + return true; + + // We cannot trust this entry, but we cannot initiate a cleanup from this + // point (we may be in the middle of a cleanup already). The entry will be + // deleted when detected from a regular open/create path. + rankings->Data()->dirty = backend_->GetCurrentEntryId() - 1; + if (!rankings->Data()->dirty) + rankings->Data()->dirty--; + return true; + } + + // Note that we should not leave this module without deleting rankings first. + rankings->SetData(entry->rankings()->Data()); + + CACHE_UMA(AGE_MS, "GetRankings", 0, start); + return true; +} + +void Rankings::ConvertToLongLived(CacheRankingsBlock* rankings) { + if (rankings->own_data()) + return; + + // We cannot return a shared node because we are not keeping a reference + // to the entry that owns the buffer. Make this node a copy of the one that + // we have, and let the iterator logic update it when the entry changes. + CacheRankingsBlock temp(NULL, Addr(0)); + *temp.Data() = *rankings->Data(); + rankings->StopSharingData(); + *rankings->Data() = *temp.Data(); +} + +void Rankings::CompleteTransaction() { + Addr node_addr(static_cast<CacheAddr>(control_data_->transaction)); + if (!node_addr.is_initialized() || node_addr.is_separate_file()) { + NOTREACHED(); + LOG(ERROR) << "Invalid rankings info."; + return; + } + + Trace("CompleteTransaction 0x%x", node_addr.value()); + + CacheRankingsBlock node(backend_->File(node_addr), node_addr); + if (!node.Load()) + return; + + node.Store(); + + Addr& my_head = heads_[control_data_->operation_list]; + Addr& my_tail = tails_[control_data_->operation_list]; + + // We want to leave the node inside the list. The entry must me marked as + // dirty, and will be removed later. Otherwise, we'll get assertions when + // attempting to remove the dirty entry. + if (INSERT == control_data_->operation) { + Trace("FinishInsert h:0x%x t:0x%x", my_head.value(), my_tail.value()); + FinishInsert(&node); + } else if (REMOVE == control_data_->operation) { + Trace("RevertRemove h:0x%x t:0x%x", my_head.value(), my_tail.value()); + RevertRemove(&node); + } else { + NOTREACHED(); + LOG(ERROR) << "Invalid operation to recover."; + } +} + +void Rankings::FinishInsert(CacheRankingsBlock* node) { + control_data_->transaction = 0; + control_data_->operation = 0; + Addr& my_head = heads_[control_data_->operation_list]; + Addr& my_tail = tails_[control_data_->operation_list]; + if (my_head.value() != node->address().value()) { + if (my_tail.value() == node->address().value()) { + // This part will be skipped by the logic of Insert. + node->Data()->next = my_tail.value(); + } + + Insert(node, true, static_cast<List>(control_data_->operation_list)); + } + + // Tell the backend about this entry. + backend_->RecoveredEntry(node); +} + +void Rankings::RevertRemove(CacheRankingsBlock* node) { + Addr next_addr(node->Data()->next); + Addr prev_addr(node->Data()->prev); + if (!next_addr.is_initialized() || !prev_addr.is_initialized()) { + // The operation actually finished. Nothing to do. + control_data_->transaction = 0; + return; + } + if (next_addr.is_separate_file() || prev_addr.is_separate_file()) { + NOTREACHED(); + LOG(WARNING) << "Invalid rankings info."; + control_data_->transaction = 0; + return; + } + + CacheRankingsBlock next(backend_->File(next_addr), next_addr); + CacheRankingsBlock prev(backend_->File(prev_addr), prev_addr); + if (!next.Load() || !prev.Load()) + return; + + CacheAddr node_value = node->address().value(); + DCHECK(prev.Data()->next == node_value || + prev.Data()->next == prev_addr.value() || + prev.Data()->next == next.address().value()); + DCHECK(next.Data()->prev == node_value || + next.Data()->prev == next_addr.value() || + next.Data()->prev == prev.address().value()); + + if (node_value != prev_addr.value()) + prev.Data()->next = node_value; + if (node_value != next_addr.value()) + next.Data()->prev = node_value; + + List my_list = static_cast<List>(control_data_->operation_list); + Addr& my_head = heads_[my_list]; + Addr& my_tail = tails_[my_list]; + if (!my_head.is_initialized() || !my_tail.is_initialized()) { + my_head.set_value(node_value); + my_tail.set_value(node_value); + WriteHead(my_list); + WriteTail(my_list); + } else if (my_head.value() == next.address().value()) { + my_head.set_value(node_value); + prev.Data()->next = next.address().value(); + WriteHead(my_list); + } else if (my_tail.value() == prev.address().value()) { + my_tail.set_value(node_value); + next.Data()->prev = prev.address().value(); + WriteTail(my_list); + } + + next.Store(); + prev.Store(); + control_data_->transaction = 0; + control_data_->operation = 0; + backend_->FlushIndex(); +} + +bool Rankings::CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev, + CacheRankingsBlock* next, List* list) { + CacheAddr node_addr = node->address().value(); + if (prev->Data()->next == node_addr && + next->Data()->prev == node_addr) { + // A regular linked node. + return true; + } + + Trace("CheckLinks 0x%x (0x%x 0x%x)", node_addr, + prev->Data()->next, next->Data()->prev); + + if (node_addr != prev->address().value() && + node_addr != next->address().value() && + prev->Data()->next == next->address().value() && + next->Data()->prev == prev->address().value()) { + // The list is actually ok, node is wrong. + Trace("node 0x%x out of list %d", node_addr, list); + node->Data()->next = 0; + node->Data()->prev = 0; + node->Store(); + return false; + } + + if (prev->Data()->next == node_addr || + next->Data()->prev == node_addr) { + // Only one link is weird, lets double check. + if (prev->Data()->next != node_addr && IsHead(node_addr, list)) + return true; + + if (next->Data()->prev != node_addr && IsTail(node_addr, list)) + return true; + } + + LOG(ERROR) << "Inconsistent LRU."; + STRESS_NOTREACHED(); + + backend_->CriticalError(ERR_INVALID_LINKS); + return false; +} + +bool Rankings::CheckSingleLink(CacheRankingsBlock* prev, + CacheRankingsBlock* next) { + if (prev->Data()->next != next->address().value() || + next->Data()->prev != prev->address().value()) { + LOG(ERROR) << "Inconsistent LRU."; + + backend_->CriticalError(ERR_INVALID_LINKS); + return false; + } + + return true; +} + +int Rankings::CheckList(List list) { + Addr last1, last2; + int head_items; + int rv = CheckListSection(list, last1, last2, true, // Head to tail. + &last1, &last2, &head_items); + if (rv == ERR_NO_ERROR) + return head_items; + + return rv; +} + +// Note that the returned error codes assume a forward walk (from head to tail) +// so they have to be adjusted accordingly by the caller. We use two stop values +// to be able to detect a corrupt node at the end that is not linked going back. +int Rankings::CheckListSection(List list, Addr end1, Addr end2, bool forward, + Addr* last, Addr* second_last, int* num_items) { + Addr current = forward ? heads_[list] : tails_[list]; + *last = *second_last = current; + *num_items = 0; + if (!current.is_initialized()) + return ERR_NO_ERROR; + + if (!current.SanityCheckForRankings()) + return ERR_INVALID_HEAD; + + scoped_ptr<CacheRankingsBlock> node; + Addr prev_addr(current); + do { + node.reset(new CacheRankingsBlock(backend_->File(current), current)); + node->Load(); + if (!SanityCheck(node.get(), true)) + return ERR_INVALID_ENTRY; + + CacheAddr next = forward ? node->Data()->next : node->Data()->prev; + CacheAddr prev = forward ? node->Data()->prev : node->Data()->next; + + if (prev != prev_addr.value()) + return ERR_INVALID_PREV; + + Addr next_addr(next); + if (!next_addr.SanityCheckForRankings()) + return ERR_INVALID_NEXT; + + prev_addr = current; + current = next_addr; + *second_last = *last; + *last = current; + (*num_items)++; + + if (next_addr == prev_addr) { + Addr last = forward ? tails_[list] : heads_[list]; + if (next_addr == last) + return ERR_NO_ERROR; + return ERR_INVALID_TAIL; + } + } while (current != end1 && current != end2); + return ERR_NO_ERROR; +} + +bool Rankings::IsHead(CacheAddr addr, List* list) const { + for (int i = 0; i < LAST_ELEMENT; i++) { + if (addr == heads_[i].value()) { + if (*list != i) + Trace("Changing list %d to %d", *list, i); + *list = static_cast<List>(i); + return true; + } + } + return false; +} + +bool Rankings::IsTail(CacheAddr addr, List* list) const { + for (int i = 0; i < LAST_ELEMENT; i++) { + if (addr == tails_[i].value()) { + if (*list != i) + Trace("Changing list %d to %d", *list, i); + *list = static_cast<List>(i); + return true; + } + } + return false; +} + +// We expect to have just a few iterators at any given time, maybe two or three, +// But we could have more than one pointing at the same mode. We walk the list +// of cache iterators and update all that are pointing to the given node. +void Rankings::UpdateIterators(CacheRankingsBlock* node) { + CacheAddr address = node->address().value(); + for (IteratorList::iterator it = iterators_.begin(); it != iterators_.end(); + ++it) { + if (it->first == address && it->second->HasData()) { + CacheRankingsBlock* other = it->second; + *other->Data() = *node->Data(); + } + } +} + +void Rankings::InvalidateIterators(CacheRankingsBlock* node) { + CacheAddr address = node->address().value(); + for (IteratorList::iterator it = iterators_.begin(); it != iterators_.end(); + ++it) { + if (it->first == address) { + DLOG(INFO) << "Invalidating iterator at 0x" << std::hex << address; + it->second->Discard(); + } + } +} + +void Rankings::IncrementCounter(List list) { + if (!count_lists_) + return; + + DCHECK(control_data_->sizes[list] < kint32max); + if (control_data_->sizes[list] < kint32max) + control_data_->sizes[list]++; +} + +void Rankings::DecrementCounter(List list) { + if (!count_lists_) + return; + + DCHECK(control_data_->sizes[list] > 0); + if (control_data_->sizes[list] > 0) + control_data_->sizes[list]--; +} + +} // namespace disk_cache |