Disk cache: Prevent obscure file corruption and deal...

net/disk_cache/backend_impl.cc

Index: net/disk_cache/backend_impl.cc
===================================================================
--- net/disk_cache/backend_impl.cc	(revision 71365)
+++ net/disk_cache/backend_impl.cc	(working copy)
@@ -678,7 +678,8 @@
   uint32 hash = Hash(key);
   Trace("Open hash 0x%x", hash);
 
-  EntryImpl* cache_entry = MatchEntry(key, hash, false);
+  bool error;
+  EntryImpl* cache_entry = MatchEntry(key, hash, false, Addr(), &error);
   if (!cache_entry) {
     stats_.OnEvent(Stats::OPEN_MISS);
     return NULL;
@@ -712,11 +713,13 @@
   if (entry_address.is_initialized()) {
     // We have an entry already. It could be the one we are looking for, or just
     // a hash conflict.
-    EntryImpl* old_entry = MatchEntry(key, hash, false);
+    bool error;
+    EntryImpl* old_entry = MatchEntry(key, hash, false, Addr(), &error);
     if (old_entry)
       return ResurrectEntry(old_entry);
 
-    EntryImpl* parent_entry = MatchEntry(key, hash, true);
+    EntryImpl* parent_entry = MatchEntry(key, hash, true, Addr(), &error);
+    DCHECK(!error);
     if (parent_entry) {
       parent.swap(&parent_entry);
     } else if (data_->table[hash & mask_]) {
@@ -901,7 +904,9 @@
 void BackendImpl::InternalDoomEntry(EntryImpl* entry) {
   uint32 hash = entry->GetHash();
   std::string key = entry->GetKey();
-  EntryImpl* parent_entry = MatchEntry(key, hash, true);
+  Addr entry_addr = entry->entry()->address();
+  bool error;
+  EntryImpl* parent_entry = MatchEntry(key, hash, true, entry_addr, &error);
   CacheAddr child(entry->GetNextAddress());
 
   Trace("Doom entry 0x%p", entry);
@@ -912,7 +917,7 @@
   if (parent_entry) {
     parent_entry->SetNextAddress(Addr(child));
     parent_entry->Release();
-  } else {
+  } else if (!error) {
     data_->table[hash & mask_] = child;
   }
 
@@ -1237,6 +1242,16 @@
     background_queue_.StopQueingOperations();
 }
 
+void BackendImpl::TrimForTest(bool empty) {
+  eviction_.SetTestMode();
+  eviction_.TrimCache(empty);
+}
+
+void BackendImpl::TrimDeletedListForTest(bool empty) {
+  eviction_.SetTestMode();
+  eviction_.TrimDeletedList(empty);
+}
+
 int BackendImpl::SelfCheck() {
   if (!init_) {
     LOG(ERROR) << "Init failed";
@@ -1553,16 +1568,28 @@
 }
 
 EntryImpl* BackendImpl::MatchEntry(const std::string& key, uint32 hash,
-                                   bool find_parent) {
+                                   bool find_parent, Addr entry_addr,
+                                   bool* match_error) {

[gavinp, 2011/01/25 20:23:51]

I'm concerned this function is doing too much.  The call sites really show it:
most of them set find_parent to false, and cons up an Addr() and a bool just for
show.  I don't like seeing that pattern too much, since it pollutes the call
sites.

My hope is that we could write a new method MatchEntryParent in terms of
MatchEntry or a MatchEntryPrivate?  Could we perhaps write MatchEntryPrivate
that always finds both a parent and an element, and the two callers return a
different one?  That'd simplify the loop (no calls to if (find_parent)
everywhere, we just always grab it), and I think the call sites would look
better too?

[rvargas (doing something else), 2011/01/25 20:47:53]

Yeah, I thought about that too. In fact, I initially wrote the change thinking
that we could get rid of find_parent and just use the address as an indication
that there is a child already (so we need the parent), but there is a caller
that is not happy with that pattern.

The other thing that I don't particularly like is that when we create a new
entry we basically go through the loop twice, once looking for the entry and
once looking for the parent (if needed). In other words, changing the way this
method works sounds like a good thing... and it looks like it won't be so much a
splitting of the function but rather making this function do a little more, but
adding small wrappers.

Do you mind if we leave that change for another CL?


On 2011/01/25 20:23:51, gavinp wrote:

   Addr address(data_->table[hash & mask_]);
   scoped_refptr<EntryImpl> cache_entry, parent_entry;
   EntryImpl* tmp = NULL;
   bool found = false;
+  std::set<CacheAddr> visited;
+  *match_error = false;
 
   for (;;) {
     if (disabled_)
       break;
 
+    if (visited.find(address.value()) != visited.end()) {
+      // It's possible for a buggy version of the code to write a loop. Just
+      // break it.
+      Trace("Hash collision loop 0x%x", address.value());
+      address.set_value(0);
+      parent_entry->SetNextAddress(address);
+    }
+    visited.insert(address.value());
+
     if (!address.is_initialized()) {
       if (find_parent)
         found = true;
@@ -1598,6 +1625,7 @@
 
       // Restart the search.
       address.set_value(data_->table[hash & mask_]);
+      visited.clear();
       continue;
     }
 
@@ -1606,6 +1634,11 @@
       if (!cache_entry->Update())
         cache_entry = NULL;
       found = true;
+      if (find_parent && entry_addr.value() != address.value()) {
+        Trace("Entry not on the index 0x%x", address.value());
+        *match_error = true;
+        parent_entry = NULL;
+      }
       break;
     }
     if (!cache_entry->Update())
@@ -1663,7 +1696,7 @@
           OpenFollowingEntryFromList(forward, iterator->list,
                                      &iterator->nodes[i], &temp);
       } else {
-        temp = GetEnumeratedEntry(iterator->nodes[i], false);
+        temp = GetEnumeratedEntry(iterator->nodes[i]);
       }
 
       entries[i].swap(&temp);  // The entry was already addref'd.
@@ -1720,7 +1753,7 @@
   Rankings::ScopedRankingsBlock next(&rankings_, next_block);
   *from_entry = NULL;
 
-  *next_entry = GetEnumeratedEntry(next.get(), false);
+  *next_entry = GetEnumeratedEntry(next.get());
   if (!*next_entry)
     return false;
 
@@ -1728,8 +1761,7 @@
   return true;
 }
 
-EntryImpl* BackendImpl::GetEnumeratedEntry(CacheRankingsBlock* next,
-                                           bool to_evict) {
+EntryImpl* BackendImpl::GetEnumeratedEntry(CacheRankingsBlock* next) {
   if (!next || disabled_)
     return NULL;
 
@@ -1744,12 +1776,19 @@
     return NULL;
   }
 
-  // There is no need to store the entry to disk if we want to delete it.
-  if (!to_evict && !entry->Update()) {
+  if (!entry->Update()) {
     entry->Release();
     return NULL;
   }
 
+  // Note that it is unfortunate (but possible) for this entry to be clean, but
+  // not actually the real entry. In other words, we could have lost this entry
+  // from the index, and it could have been replaced with a newer one. It's not
+  // worth checking that this entry is "the real one", so we just return it and
+  // let the enumeration continue; this entry will be evicted at some point, and
+  // the regular path will work with the real entry. With time, this problem
+  // will disasappear because this scenario is just a bug.
+
   // Make sure that we save the key for later.
   entry->GetKey();
 
@@ -1801,7 +1840,7 @@
 void BackendImpl::DestroyInvalidEntryFromEnumeration(EntryImpl* entry) {
   std::string key = entry->GetKey();
   entry->SetPointerForInvalidEntry(GetCurrentEntryId());
-  CacheAddr next_entry = entry->entry()->Data()->next;
+  CacheAddr next_entry = entry->GetNextAddress();
   if (!next_entry) {
     DestroyInvalidEntry(entry);
     entry->Release();