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

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<void*>(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<Rankings::List>(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<BlockFileHeader*>(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<BlockFileHeader*>(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<EntryImpl> {
   // 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<Rankings::List>(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 <string>
 
 #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<CacheAddr, CacheRankingsBlock*> 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);