From ae2796cabb52f6a27c50818b78107d3ebc858e0c Mon Sep 17 00:00:00 2001 From: Kristian Monsen Date: Tue, 1 Nov 2011 18:10:25 +0000 Subject: Part of fix for bug 5523834, backporting cache fixes Cherry-picking CL http://src.chromium.org/viewvc/chrome?view=rev&revision=103323 Did not cherry-pick the changes in trunk/src/net/disk_cache/backend_unittest.cc as we are not running the tests on Android. Change-Id: I4e04bf061bdb6746030f3a93501cff9b384c58df --- net/disk_cache/backend_impl.cc | 65 +++++++++++++++++++++++++++-------- net/disk_cache/backend_impl.h | 4 +-- net/disk_cache/block_files.cc | 6 ++-- net/disk_cache/entry_impl.cc | 59 ++++++++++++++++++++++++++----- net/disk_cache/entry_impl.h | 8 +++++ net/disk_cache/eviction.cc | 47 ++++++++++++++++--------- net/disk_cache/eviction.h | 2 +- net/disk_cache/in_flight_backend_io.h | 4 ++- net/disk_cache/rankings.cc | 35 +++++++++++++------ net/disk_cache/rankings.h | 18 +++++++--- 10 files changed, 187 insertions(+), 61 deletions(-) diff --git a/net/disk_cache/backend_impl.cc b/net/disk_cache/backend_impl.cc index e5d889f..117f20b 100644 --- a/net/disk_cache/backend_impl.cc +++ b/net/disk_cache/backend_impl.cc @@ -723,6 +723,19 @@ EntryImpl* BackendImpl::CreateEntryImpl(const std::string& key) { } } + // The general flow is to allocate disk space and initialize the entry data, + // followed by saving that to disk, then linking the entry though the index + // and finally through the lists. If there is a crash in this process, we may + // end up with: + // a. Used, unreferenced empty blocks on disk (basically just garbage). + // b. Used, unreferenced but meaningful data on disk (more garbage). + // c. A fully formed entry, reachable only through the index. + // d. A fully formed entry, also reachable through the lists, but still dirty. + // + // Anything after (b) can be automatically cleaned up. We may consider saving + // the current operation (as we do while manipulating the lists) so that we + // can detect and cleanup (a) and (b). + int num_blocks = EntryImpl::NumBlocksForEntry(key.size()); if (!block_files_.CreateBlock(BLOCK_256, num_blocks, &entry_address)) { LOG(ERROR) << "Create entry failed " << key.c_str(); @@ -755,17 +768,21 @@ EntryImpl* BackendImpl::CreateEntryImpl(const std::string& key) { // We are not failing the operation; let's add this to the map. open_entries_[entry_address.value()] = cache_entry; - if (parent.get()) - parent->SetNextAddress(entry_address); - + // Save the entry. block_files_.GetFile(entry_address)->Store(cache_entry->entry()); block_files_.GetFile(node_address)->Store(cache_entry->rankings()); - IncreaseNumEntries(); - eviction_.OnCreateEntry(cache_entry); entry_count_++; - if (!parent.get()) + + // Link this entry through the index. + if (parent.get()) { + parent->SetNextAddress(entry_address); + } else { data_->table[hash & mask_] = entry_address.value(); + } + + // Link this entry through the lists. + eviction_.OnCreateEntry(cache_entry); CACHE_UMA(AGE_MS, "CreateTime", GetSizeGroup(), start); stats_.OnEvent(Stats::CREATE_HIT); @@ -1516,8 +1533,22 @@ int BackendImpl::NewEntry(Addr address, EntryImpl** entry) { // Prevent overwriting the dirty flag on the destructor. cache_entry->SetDirtyFlag(GetCurrentEntryId()); - if (!rankings_.SanityCheck(cache_entry->rankings(), false)) - return ERR_INVALID_LINKS; + if (!rankings_.SanityCheck(cache_entry->rankings(), false)) { + cache_entry->SetDirtyFlag(0); + // Don't remove this from the list (it is not linked properly). Instead, + // break the link back to the entry because it is going away, and leave the + // rankings node to be deleted if we find it through a list. + rankings_.SetContents(cache_entry->rankings(), 0); + } else if (!rankings_.DataSanityCheck(cache_entry->rankings(), false)) { + cache_entry->SetDirtyFlag(0); + rankings_.SetContents(cache_entry->rankings(), address.value()); + } + + if (!cache_entry->DataSanityCheck()) { + LOG(WARNING) << "Messed up entry found."; + cache_entry->SetDirtyFlag(0); + cache_entry->FixForDelete(); + } if (cache_entry->dirty()) { Trace("Dirty entry 0x%p 0x%x", reinterpret_cast(cache_entry.get()), @@ -1667,7 +1698,8 @@ EntryImpl* BackendImpl::OpenFollowingEntry(bool forward, void** iter) { OpenFollowingEntryFromList(forward, iterator->list, &iterator->nodes[i], &temp); } else { - temp = GetEnumeratedEntry(iterator->nodes[i]); + temp = GetEnumeratedEntry(iterator->nodes[i], + static_cast(i)); } entries[i].swap(&temp); // The entry was already addref'd. @@ -1724,7 +1756,7 @@ bool BackendImpl::OpenFollowingEntryFromList(bool forward, Rankings::List list, Rankings::ScopedRankingsBlock next(&rankings_, next_block); *from_entry = NULL; - *next_entry = GetEnumeratedEntry(next.get()); + *next_entry = GetEnumeratedEntry(next.get(), list); if (!*next_entry) return false; @@ -1732,14 +1764,19 @@ bool BackendImpl::OpenFollowingEntryFromList(bool forward, Rankings::List list, return true; } -EntryImpl* BackendImpl::GetEnumeratedEntry(CacheRankingsBlock* next) { +EntryImpl* BackendImpl::GetEnumeratedEntry(CacheRankingsBlock* next, + Rankings::List list) { if (!next || disabled_) return NULL; EntryImpl* entry; - if (NewEntry(Addr(next->Data()->contents), &entry)) { - // TODO(rvargas) bug 73102: We should remove this node from the list, and - // maybe do a better cleanup. + int rv = NewEntry(Addr(next->Data()->contents), &entry); + if (rv) { + rankings_.Remove(next, list, false); + if (rv == ERR_INVALID_ADDRESS) { + // There is nothing linked from the index. Delete the rankings node. + DeleteBlock(next->address(), true); + } return NULL; } diff --git a/net/disk_cache/backend_impl.h b/net/disk_cache/backend_impl.h index 92d207b..67e7734 100644 --- a/net/disk_cache/backend_impl.h +++ b/net/disk_cache/backend_impl.h @@ -300,8 +300,8 @@ class BackendImpl : public Backend { CacheRankingsBlock** from_entry, EntryImpl** next_entry); - // Returns the entry that is pointed by |next|. - EntryImpl* GetEnumeratedEntry(CacheRankingsBlock* next); + // Returns the entry that is pointed by |next|, from the given |list|. + EntryImpl* GetEnumeratedEntry(CacheRankingsBlock* next, Rankings::List list); // Re-opens an entry that was previously deleted. EntryImpl* ResurrectEntry(EntryImpl* deleted_entry); diff --git a/net/disk_cache/block_files.cc b/net/disk_cache/block_files.cc index e39ca13..17677f1 100644 --- a/net/disk_cache/block_files.cc +++ b/net/disk_cache/block_files.cc @@ -287,15 +287,15 @@ void BlockFiles::DeleteBlock(Addr address, bool deep) { Trace("DeleteBlock 0x%x", address.value()); - BlockFileHeader* header = reinterpret_cast(file->buffer()); - DeleteMapBlock(address.start_block(), address.num_blocks(), header); - size_t size = address.BlockSize() * address.num_blocks(); size_t offset = address.start_block() * address.BlockSize() + kBlockHeaderSize; if (deep) file->Write(zero_buffer_, size, offset); + BlockFileHeader* header = reinterpret_cast(file->buffer()); + DeleteMapBlock(address.start_block(), address.num_blocks(), header); + if (!header->num_entries) { // This file is now empty. Let's try to delete it. FileType type = Addr::RequiredFileType(header->entry_size); diff --git a/net/disk_cache/entry_impl.cc b/net/disk_cache/entry_impl.cc index 0dbfc94..dac9c59 100644 --- a/net/disk_cache/entry_impl.cc +++ b/net/disk_cache/entry_impl.cc @@ -496,17 +496,17 @@ void EntryImpl::DeleteEntryData(bool everything) { // Remove all traces of this entry. backend_->RemoveEntry(this); + // Note that at this point node_ and entry_ are just two blocks of data, and + // even if they reference each other, nobody should be referencing them. + Addr address(entry_.Data()->long_key); DeleteData(address, kKeyFileIndex); backend_->ModifyStorageSize(entry_.Data()->key_len, 0); - memset(node_.buffer(), 0, node_.size()); - memset(entry_.buffer(), 0, entry_.size()); - node_.Store(); - entry_.Store(); + backend_->DeleteBlock(entry_.address(), true); - backend_->DeleteBlock(node_.address(), false); - backend_->DeleteBlock(entry_.address(), false); + if (!LeaveRankingsBehind()) + backend_->DeleteBlock(node_.address(), true); } CacheAddr EntryImpl::GetNextAddress() { @@ -551,6 +551,9 @@ void EntryImpl::SetDirtyFlag(int32 current_id) { if (node_.Data()->dirty && current_id != node_.Data()->dirty) dirty_ = true; + + if (!current_id) + dirty_ = true; } void EntryImpl::SetPointerForInvalidEntry(int32 new_id) { @@ -559,6 +562,14 @@ void EntryImpl::SetPointerForInvalidEntry(int32 new_id) { node_.Store(); } +bool EntryImpl::LeaveRankingsBehind() { + return !node_.Data()->contents; +} + +// This only includes checks that relate to the first block of the entry (the +// first 256 bytes), and values that should be set from the entry creation. +// Basically, even if there is something wrong with this entry, we want to see +// if it is possible to load the rankings node and delete them together. bool EntryImpl::SanityCheck() { EntryStore* stored = entry_.Data(); if (!stored->rankings_node || stored->key_len <= 0) @@ -569,7 +580,7 @@ bool EntryImpl::SanityCheck() { Addr rankings_addr(stored->rankings_node); if (!rankings_addr.is_initialized() || rankings_addr.is_separate_file() || - rankings_addr.file_type() != RANKINGS) + rankings_addr.file_type() != RANKINGS || rankings_addr.num_blocks() != 1) return false; Addr next_addr(stored->next); @@ -600,6 +611,13 @@ bool EntryImpl::SanityCheck() { if (entry_.address().num_blocks() != num_blocks) return false; + return true; +} + +bool EntryImpl::DataSanityCheck() { + EntryStore* stored = entry_.Data(); + Addr key_addr(stored->long_key); + // The key must be NULL terminated. if (!key_addr.is_initialized() && stored->key[stored->key_len]) return false; @@ -623,10 +641,35 @@ bool EntryImpl::SanityCheck() { if (data_size > kMaxBlockSize && data_addr.is_block_file()) return false; } - return true; } +void EntryImpl::FixForDelete() { + EntryStore* stored = entry_.Data(); + Addr key_addr(stored->long_key); + + if (!key_addr.is_initialized()) + stored->key[stored->key_len] = '\0'; + + for (int i = 0; i < kNumStreams; i++) { + Addr data_addr(stored->data_addr[i]); + int data_size = stored->data_size[i]; + if (data_addr.is_initialized()) { + if ((data_size <= kMaxBlockSize && data_addr.is_separate_file()) || + (data_size > kMaxBlockSize && data_addr.is_block_file()) || + !data_addr.SanityCheck()) { + // The address is weird so don't attempt to delete it. + stored->data_addr[i] = 0; + // In general, trust the stored size as it should be in sync with the + // total size tracked by the backend. + } + } + if (data_size < 0) + stored->data_size[i] = 0; + } + entry_.Store(); +} + void EntryImpl::IncrementIoCount() { backend_->IncrementIoCount(); } diff --git a/net/disk_cache/entry_impl.h b/net/disk_cache/entry_impl.h index 16f9e07..4beaa63 100644 --- a/net/disk_cache/entry_impl.h +++ b/net/disk_cache/entry_impl.h @@ -102,8 +102,16 @@ class EntryImpl : public Entry, public base::RefCounted { // Fixes this entry so it can be treated as valid (to delete it). void SetPointerForInvalidEntry(int32 new_id); + // Returns true if this entry is so meesed up that not everything is going to + // be removed. + bool LeaveRankingsBehind(); + // Returns false if the entry is clearly invalid. bool SanityCheck(); + bool DataSanityCheck(); + + // Attempts to make this entry reachable though the key. + void FixForDelete(); // Handle the pending asynchronous IO count. void IncrementIoCount(); diff --git a/net/disk_cache/eviction.cc b/net/disk_cache/eviction.cc index f061622..ada2424 100644 --- a/net/disk_cache/eviction.cc +++ b/net/disk_cache/eviction.cc @@ -116,7 +116,7 @@ void Eviction::TrimCache(bool empty) { Rankings::ScopedRankingsBlock next(rankings_, rankings_->GetPrev(node.get(), Rankings::NO_USE)); int target_size = empty ? 0 : max_size_; - while ((header_->num_bytes > target_size && next.get()) || test_mode_) { + while ((header_->num_bytes > target_size || test_mode_) && next.get()) { // The iterator could be invalidated within EvictEntry(). if (!next->HasData()) break; @@ -126,7 +126,7 @@ void Eviction::TrimCache(bool empty) { // This entry is not being used by anybody. // Do NOT use node as an iterator after this point. rankings_->TrackRankingsBlock(node.get(), false); - if (!EvictEntry(node.get(), empty) && !test_mode_) + if (!EvictEntry(node.get(), empty, Rankings::NO_USE) && !test_mode_) continue; if (!empty) { @@ -177,7 +177,10 @@ void Eviction::OnDoomEntry(EntryImpl* entry) { if (new_eviction_) return OnDoomEntryV2(entry); - rankings_->Remove(entry->rankings(), GetListForEntry(entry)); + if (entry->LeaveRankingsBehind()) + return; + + rankings_->Remove(entry->rankings(), GetListForEntry(entry), true); } void Eviction::OnDestroyEntry(EntryImpl* entry) { @@ -253,8 +256,9 @@ Rankings::List Eviction::GetListForEntry(EntryImpl* entry) { return Rankings::NO_USE; } -bool Eviction::EvictEntry(CacheRankingsBlock* node, bool empty) { - EntryImpl* entry = backend_->GetEnumeratedEntry(node); +bool Eviction::EvictEntry(CacheRankingsBlock* node, bool empty, + Rankings::List list) { + EntryImpl* entry = backend_->GetEnumeratedEntry(node, list); if (!entry) { Trace("NewEntry failed on Trim 0x%x", node->address().value()); return false; @@ -268,7 +272,7 @@ bool Eviction::EvictEntry(CacheRankingsBlock* node, bool empty) { EntryStore* info = entry->entry()->Data(); DCHECK(ENTRY_NORMAL == info->state); - rankings_->Remove(entry->rankings(), GetListForEntryV2(entry)); + rankings_->Remove(entry->rankings(), GetListForEntryV2(entry), true); info->state = ENTRY_EVICTED; entry->entry()->Store(); rankings_->Insert(entry->rankings(), true, Rankings::DELETED); @@ -314,8 +318,8 @@ void Eviction::TrimCacheV2(bool empty) { int target_size = empty ? 0 : max_size_; for (; list < kListsToSearch; list++) { - while ((header_->num_bytes > target_size && next[list].get()) || - test_mode_) { + while ((header_->num_bytes > target_size || test_mode_) && + next[list].get()) { // The iterator could be invalidated within EvictEntry(). if (!next[list]->HasData()) break; @@ -326,7 +330,8 @@ void Eviction::TrimCacheV2(bool empty) { // This entry is not being used by anybody. // Do NOT use node as an iterator after this point. rankings_->TrackRankingsBlock(node.get(), false); - if (!EvictEntry(node.get(), empty) && !test_mode_) + if (!EvictEntry(node.get(), empty, static_cast(list)) && + !test_mode_) continue; if (!empty && test_mode_) @@ -376,11 +381,11 @@ void Eviction::OnOpenEntryV2(EntryImpl* entry) { // We may need to move this to a new list. if (1 == info->reuse_count) { - rankings_->Remove(entry->rankings(), Rankings::NO_USE); + rankings_->Remove(entry->rankings(), Rankings::NO_USE, true); rankings_->Insert(entry->rankings(), false, Rankings::LOW_USE); entry->entry()->Store(); } else if (kHighUse == info->reuse_count) { - rankings_->Remove(entry->rankings(), Rankings::LOW_USE); + rankings_->Remove(entry->rankings(), Rankings::LOW_USE, true); rankings_->Insert(entry->rankings(), false, Rankings::HIGH_USE); entry->entry()->Store(); } @@ -406,7 +411,7 @@ void Eviction::OnCreateEntryV2(EntryImpl* entry) { } info->state = ENTRY_NORMAL; entry->entry()->Store(); - rankings_->Remove(entry->rankings(), Rankings::DELETED); + rankings_->Remove(entry->rankings(), Rankings::DELETED, true); break; }; default: @@ -421,7 +426,13 @@ void Eviction::OnDoomEntryV2(EntryImpl* entry) { if (ENTRY_NORMAL != info->state) return; - rankings_->Remove(entry->rankings(), GetListForEntryV2(entry)); + if (entry->LeaveRankingsBehind()) { + info->state = ENTRY_DOOMED; + entry->entry()->Store(); + return; + } + + rankings_->Remove(entry->rankings(), GetListForEntryV2(entry), true); info->state = ENTRY_DOOMED; entry->entry()->Store(); @@ -429,7 +440,10 @@ void Eviction::OnDoomEntryV2(EntryImpl* entry) { } void Eviction::OnDestroyEntryV2(EntryImpl* entry) { - rankings_->Remove(entry->rankings(), Rankings::DELETED); + if (entry->LeaveRankingsBehind()) + return; + + rankings_->Remove(entry->rankings(), Rankings::DELETED, true); } Rankings::List Eviction::GetListForEntryV2(EntryImpl* entry) { @@ -457,7 +471,8 @@ void Eviction::TrimDeleted(bool empty) { Rankings::ScopedRankingsBlock next(rankings_, rankings_->GetPrev(node.get(), Rankings::DELETED)); bool deleted = false; - for (int i = 0; (i < 4 || empty) && next.get(); i++) { + while (next.get() && + (empty || (TimeTicks::Now() - start).InMilliseconds() < 20)) { node.reset(next.release()); next.reset(rankings_->GetPrev(node.get(), Rankings::DELETED)); deleted |= RemoveDeletedNode(node.get()); @@ -483,7 +498,7 @@ void Eviction::TrimDeleted(bool empty) { } bool Eviction::RemoveDeletedNode(CacheRankingsBlock* node) { - EntryImpl* entry = backend_->GetEnumeratedEntry(node); + EntryImpl* entry = backend_->GetEnumeratedEntry(node, Rankings::DELETED); if (!entry) { Trace("NewEntry failed on Trim 0x%x", node->address().value()); return false; diff --git a/net/disk_cache/eviction.h b/net/disk_cache/eviction.h index dd69b71..dbf87c3 100644 --- a/net/disk_cache/eviction.h +++ b/net/disk_cache/eviction.h @@ -50,7 +50,7 @@ class Eviction { bool ShouldTrim(); void ReportTrimTimes(EntryImpl* entry); Rankings::List GetListForEntry(EntryImpl* entry); - bool EvictEntry(CacheRankingsBlock* node, bool empty); + bool EvictEntry(CacheRankingsBlock* node, bool empty, Rankings::List list); // We'll just keep for a while a separate set of methods that implement the // new eviction algorithm. This code will replace the original methods when diff --git a/net/disk_cache/in_flight_backend_io.h b/net/disk_cache/in_flight_backend_io.h index 89fe3c1..cedc8df 100644 --- a/net/disk_cache/in_flight_backend_io.h +++ b/net/disk_cache/in_flight_backend_io.h @@ -10,14 +10,16 @@ #include #include "base/message_loop_proxy.h" +#include "base/time.h" #include "net/base/completion_callback.h" #include "net/base/io_buffer.h" -#include "net/disk_cache/entry_impl.h" #include "net/disk_cache/in_flight_io.h" namespace disk_cache { class BackendImpl; +class Entry; +class EntryImpl; // This class represents a single asynchronous disk cache IO operation while it // is being bounced between threads. diff --git a/net/disk_cache/rankings.cc b/net/disk_cache/rankings.cc index bd3f165..902db1c 100644 --- a/net/disk_cache/rankings.cc +++ b/net/disk_cache/rankings.cc @@ -298,11 +298,13 @@ void Rankings::Insert(CacheRankingsBlock* node, bool modified, List list) { // 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) { +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() || @@ -386,7 +388,7 @@ void Rankings::UpdateRank(CacheRankingsBlock* node, bool modified, List list) { } TimeTicks start = TimeTicks::Now(); - Remove(node, list); + Remove(node, list, true); Insert(node, modified, list); CACHE_UMA(AGE_MS, "UpdateRank", 0, start); } @@ -485,14 +487,8 @@ int Rankings::SelfCheck() { return total; } -bool Rankings::SanityCheck(CacheRankingsBlock* node, bool from_list) { +bool Rankings::SanityCheck(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; if ((!data->next && data->prev) || (data->next && !data->prev)) return false; @@ -520,6 +516,23 @@ bool Rankings::SanityCheck(CacheRankingsBlock* node, bool from_list) { 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]); @@ -801,7 +814,7 @@ int Rankings::CheckList(List list) { return num_items; } -bool Rankings::IsHead(CacheAddr addr, List* list) { +bool Rankings::IsHead(CacheAddr addr, List* list) const { for (int i = 0; i < LAST_ELEMENT; i++) { if (addr == heads_[i].value()) { if (*list != i) @@ -813,7 +826,7 @@ bool Rankings::IsHead(CacheAddr addr, List* list) { return false; } -bool Rankings::IsTail(CacheAddr addr, List* list) { +bool Rankings::IsTail(CacheAddr addr, List* list) const { for (int i = 0; i < LAST_ELEMENT; i++) { if (addr == tails_[i].value()) { if (*list != i) diff --git a/net/disk_cache/rankings.h b/net/disk_cache/rankings.h index f78c97e..b5f6daa 100644 --- a/net/disk_cache/rankings.h +++ b/net/disk_cache/rankings.h @@ -112,8 +112,12 @@ class Rankings { // Inserts a given entry at the head of the queue. void Insert(CacheRankingsBlock* node, bool modified, List list); - // Removes a given entry from the LRU list. - void Remove(CacheRankingsBlock* node, List list); + // Removes a given entry from the LRU list. If |strict| is true, this method + // assumes that |node| is not pointed to by an active iterator. On the other + // hand, removing that restriction allows the current "head" of an iterator + // to be removed from the list (basically without control of the code that is + // performing the iteration), so it should be used with extra care. + void Remove(CacheRankingsBlock* node, List list, bool strict); // Moves a given entry to the head. void UpdateRank(CacheRankingsBlock* node, bool modified, List list); @@ -132,7 +136,11 @@ class Rankings { // Returns false if the entry is clearly invalid. from_list is true if the // node comes from the LRU list. - bool SanityCheck(CacheRankingsBlock* node, bool from_list); + bool SanityCheck(CacheRankingsBlock* node, bool from_list) const; + bool DataSanityCheck(CacheRankingsBlock* node, bool from_list) const; + + // Sets the |contents| field of |node| to |address|. + void SetContents(CacheRankingsBlock* node, CacheAddr address); private: typedef std::pair IteratorPair; @@ -174,8 +182,8 @@ class Rankings { // Returns true if addr is the head or tail of any list. When there is a // match |list| will contain the list number for |addr|. - bool IsHead(CacheAddr addr, List* list); - bool IsTail(CacheAddr addr, List* list); + bool IsHead(CacheAddr addr, List* list) const; + bool IsTail(CacheAddr addr, List* list) const; // Updates the iterators whenever node is being changed. void UpdateIterators(CacheRankingsBlock* node); -- cgit v1.1