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

net/disk_cache/backend_impl.cc

 // Copyright (c) 2010 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/backend_impl.h"
 
 #include "base/file_path.h"
 #include "base/file_util.h"
 #include "base/message_loop.h"
 #include "base/metrics/field_trial.h"
@@ skipping 660 matching lines @@
 }
 
 EntryImpl* BackendImpl::OpenEntryImpl(const std::string& key) {
   if (disabled_)
     return NULL;
 
   TimeTicks start = TimeTicks::Now();
   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;
   }
 
   if (ENTRY_NORMAL != cache_entry->entry()->Data()->state) {
     // The entry was already evicted.
     cache_entry->Release();
     stats_.OnEvent(Stats::OPEN_MISS);
     return NULL;
@@ skipping 13 matching lines @@
 
   TimeTicks start = TimeTicks::Now();
   uint32 hash = Hash(key);
   Trace("Create hash 0x%x", hash);
 
   scoped_refptr<EntryImpl> parent;
   Addr entry_address(data_->table[hash & mask_]);
   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_]) {
       // We should have corrected the problem.
       NOTREACHED();
       return NULL;
     }
   }
 
   int num_blocks;
@@ skipping 164 matching lines @@
   // Anything on the table means that this entry is there.
   if (data_->table[hash & mask_])
     return;
 
   data_->table[hash & mask_] = address.value();
 }
 
 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);
 
   eviction_.OnDoomEntry(entry);
   entry->InternalDoom();
 
   if (parent_entry) {
     parent_entry->SetNextAddress(Addr(child));
     parent_entry->Release();
-  } else {
+  } else if (!error) {
     data_->table[hash & mask_] = child;
   }
 
   if (!new_eviction_) {
     DecreaseNumEntries();
   }
 
   stats_.OnEvent(Stats::DOOM_ENTRY);
 }
 
@@ skipping 304 matching lines @@
   return net::ERR_IO_PENDING;
 }
 
 void BackendImpl::ThrottleRequestsForTest(bool throttle) {
   if (throttle)
     background_queue_.StartQueingOperations();
   else
     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";
     return ERR_INIT_FAILED;
   }
 
   int num_entries = rankings_.SelfCheck();
   if (num_entries < 0) {
     LOG(ERROR) << "Invalid rankings list, error " << num_entries;
     return num_entries;
@@ skipping 296 matching lines @@
     // We only add clean entries to the map.
     open_entries_[address.value()] = cache_entry;
   }
 
   cache_entry->BeginLogging(net_log_, false);
   cache_entry.swap(entry);
   return 0;
 }
 
 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;
       break;
     }
 
     bool dirty;
     int error = NewEntry(address, &tmp, &dirty);
     cache_entry.swap(&tmp);
 
@@ skipping 15 matching lines @@
         // It is important to call DestroyInvalidEntry after removing this
         // entry from the table.
         DestroyInvalidEntry(cache_entry);
         cache_entry = NULL;
       } else {
         Trace("NewEntry failed on MatchEntry 0x%x", address.value());
       }
 
       // Restart the search.
       address.set_value(data_->table[hash & mask_]);
+      visited.clear();
       continue;
     }
 
     DCHECK_EQ(hash & mask_, cache_entry->entry()->Data()->hash & mask_);
     if (cache_entry->IsSameEntry(key, hash)) {
       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())
       cache_entry = NULL;
     parent_entry = cache_entry;
     cache_entry = NULL;
     if (!parent_entry)
       break;
 
     address.set_value(parent_entry->GetNextAddress());
@@ skipping 37 matching lines @@
       return NULL;
   } else {
     // Get the next entry from the last list, and the actual entries for the
     // elements on the other lists.
     for (int i = 0; i < kListsToSearch; i++) {
       EntryImpl* temp = NULL;
       if (iterator->list == i) {
           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.
     }
   }
 
   int newest = -1;
   int oldest = -1;
   Time access_times[kListsToSearch];
   for (int i = 0; i < kListsToSearch; i++) {
@@ skipping 36 matching lines @@
   if (!new_eviction_ && Rankings::NO_USE != list)
     return false;
 
   Rankings::ScopedRankingsBlock rankings(&rankings_, *from_entry);
   CacheRankingsBlock* next_block = forward ?
       rankings_.GetNext(rankings.get(), list) :
       rankings_.GetPrev(rankings.get(), list);
   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;
 
   *from_entry = next.release();
   return true;
 }
 
-EntryImpl* BackendImpl::GetEnumeratedEntry(CacheRankingsBlock* next,
-                                           bool to_evict) {
+EntryImpl* BackendImpl::GetEnumeratedEntry(CacheRankingsBlock* next) {
   if (!next || disabled_)
     return NULL;
 
   EntryImpl* entry;
   bool dirty;
   if (NewEntry(Addr(next->Data()->contents), &entry, &dirty))
     return NULL;
 
   if (dirty) {
     // We cannot trust this entry. This code also releases the reference.
     DestroyInvalidEntryFromEnumeration(entry);
     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();
 
   return entry;
 }
 
 EntryImpl* BackendImpl::ResurrectEntry(EntryImpl* deleted_entry) {
   if (ENTRY_NORMAL == deleted_entry->entry()->Data()->state) {
     deleted_entry->Release();
     stats_.OnEvent(Stats::CREATE_MISS);
@@ skipping 31 matching lines @@
 // deleting it twice (if all fields are right, and when looking up the parent of
 // chained entries wee see this one... and we delete it because it is dirty). If
 // we ignore it, we may leave it here forever. So we're going to attempt to
 // delete it through the provided object, without touching the index table
 // (because we cannot jus call MatchEntry()), and also attempt to delete it from
 // the table through the key: this may find a new entry (too bad), or an entry
 // that was just deleted and consider it a very corrupt entry.
 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();
   }
   SyncDoomEntry(key);
 
   if (!next_entry)
     return;
 
   // We have a chained entry so instead of destroying first this entry and then
@@ skipping 280 matching lines @@
     if (total_memory > kMaxBuffersSize || total_memory <= 0)
       total_memory = kMaxBuffersSize;
 
     done = true;
   }
 
   return static_cast<int>(total_memory);
 }
 
 }  // namespace disk_cache