Disk Cache: Add more corruption tracking histograms.

BUG=none
TEST=none

Review URL: http://codereview.chromium.org/10148001

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@134678 0039d316-1c4b-4281-b951-d872f2087c98

7 files changed, 154 insertions, 53 deletions

diff --git a/net/disk_cache/addr.cc b/net/disk_cache/addr.cc
index c4b95ef..ac924e9 100644
--- a/net/disk_cache/addr.cc
+++ b/net/disk_cache/addr.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// 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.
 
@@ -40,4 +40,24 @@ bool Addr::SanityCheck() const {
   return !(value_ & kReservedBitsMask);
 }
 
+bool Addr::SanityCheckForEntry() const {
+  if (!SanityCheck() || !is_initialized())
+    return false;
+
+  if (is_separate_file() || file_type() != BLOCK_256)
+    return false;
+
+  return true;
+}
+
+bool Addr::SanityCheckForRankings() const {
+  if (!SanityCheck() || !is_initialized())
+    return false;
+
+  if (is_separate_file() || file_type() != RANKINGS || num_blocks() != 1)
+    return false;
+
+  return true;
+}
+
 }  // namespace disk_cache
diff --git a/net/disk_cache/addr.h b/net/disk_cache/addr.h
index aa81a16..b398934 100644
--- a/net/disk_cache/addr.h
+++ b/net/disk_cache/addr.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// 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.
 
@@ -94,6 +94,14 @@ class NET_EXPORT_PRIVATE Addr {
     return BlockSizeForFileType(file_type());
   }
 
+  bool operator==(Addr other) const {
+    return value_ == other.value_;
+  }
+
+  bool operator!=(Addr other) const {
+    return value_ != other.value_;
+  }
+
   static int BlockSizeForFileType(FileType file_type) {
     switch (file_type) {
       case RANKINGS:
@@ -122,6 +130,8 @@ class NET_EXPORT_PRIVATE Addr {
 
   // Returns true if this address looks like a valid one.
   bool SanityCheck() const;
+  bool SanityCheckForEntry() const;
+  bool SanityCheckForRankings() const;
 
  private:
   static const uint32 kInitializedMask    = 0x80000000;
diff --git a/net/disk_cache/backend_impl.cc b/net/disk_cache/backend_impl.cc
index 20fd40f..d4ccd24 100644
--- a/net/disk_cache/backend_impl.cc
+++ b/net/disk_cache/backend_impl.cc
@@ -450,6 +450,9 @@ int BackendImpl::SyncInit() {
     return net::ERR_FAILED;
   }
 
+  if (create_files || !data_->header.num_entries)
+    ReportError(ERR_CACHE_CREATED);
+
   if (!(user_flags_ & kNoRandom) &&
       cache_type_ == net::DISK_CACHE && !InitExperiment(&data_->header))
     return net::ERR_FAILED;
@@ -465,7 +468,7 @@ int BackendImpl::SyncInit() {
   if (data_->header.crash) {
     ReportError(ERR_PREVIOUS_CRASH);
   } else {
-    ReportError(0);
+    ReportError(ERR_NO_ERROR);
     data_->header.crash = 1;
   }
 
@@ -487,6 +490,9 @@ int BackendImpl::SyncInit() {
 
   disabled_ = !rankings_.Init(this, new_eviction_);
 
+  if (!disabled_ && !(user_flags_ & kNoRandom) && base::RandInt(0, 99) < 2)
+    rankings_.SelfCheck();  // Ignore return value for now.
+
 #if defined(STRESS_CACHE_EXTENDED_VALIDATION)
   trace_object_->EnableTracing(false);
   int sc = SelfCheck();
@@ -1553,8 +1559,7 @@ int BackendImpl::NewEntry(Addr address, EntryImpl** entry) {
 
   STRESS_DCHECK(block_files_.IsValid(address));
 
-  if (!address.is_initialized() || address.is_separate_file() ||
-      address.file_type() != BLOCK_256) {
+  if (!address.SanityCheckForEntry()) {
     LOG(WARNING) << "Wrong entry address.";
     STRESS_NOTREACHED();
     return ERR_INVALID_ADDRESS;
diff --git a/net/disk_cache/entry_impl.cc b/net/disk_cache/entry_impl.cc
index 922a56b..4991375 100644
--- a/net/disk_cache/entry_impl.cc
+++ b/net/disk_cache/entry_impl.cc
@@ -577,21 +577,16 @@ bool EntryImpl::SanityCheck() {
     return false;
 
   Addr rankings_addr(stored->rankings_node);
-  if (!rankings_addr.is_initialized() || rankings_addr.is_separate_file() ||
-      rankings_addr.file_type() != RANKINGS || rankings_addr.num_blocks() != 1)
+  if (!rankings_addr.SanityCheckForRankings())
     return false;
 
   Addr next_addr(stored->next);
-  if (next_addr.is_initialized() &&
-      (next_addr.is_separate_file() || next_addr.file_type() != BLOCK_256)) {
+  if (next_addr.is_initialized() && !next_addr.SanityCheckForEntry()) {
     STRESS_NOTREACHED();
     return false;
   }
   STRESS_DCHECK(next_addr.value() != entry_.address().value());
 
-  if (!rankings_addr.SanityCheck() || !next_addr.SanityCheck())
-    return false;
-
   if (stored->state > ENTRY_DOOMED || stored->state < ENTRY_NORMAL)
     return false;
 
diff --git a/net/disk_cache/errors.h b/net/disk_cache/errors.h
index 68c0a1a..af4043a 100644
--- a/net/disk_cache/errors.h
+++ b/net/disk_cache/errors.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
+// 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.
 
@@ -11,6 +11,7 @@
 namespace disk_cache {
 
 enum {
+  ERR_NO_ERROR = 0,
   ERR_INIT_FAILED = -1,
   ERR_INVALID_TAIL = -2,
   ERR_INVALID_HEAD = -3,
@@ -24,7 +25,8 @@ enum {
   ERR_PREVIOUS_CRASH = -11,
   ERR_STORAGE_ERROR = -12,
   ERR_INVALID_MASK = -13,
-  ERR_CACHE_DOOMED = -14  // Not really an error condition
+  ERR_CACHE_DOOMED = -14,   // Not really an error condition.
+  ERR_CACHE_CREATED = -15   // Not really an error condition.
 };
 
 }  // namespace disk_cache
diff --git a/net/disk_cache/rankings.cc b/net/disk_cache/rankings.cc
index a5ef839..515e23d 100644
--- a/net/disk_cache/rankings.cc
+++ b/net/disk_cache/rankings.cc
@@ -724,14 +724,6 @@ void Rankings::RevertRemove(CacheRankingsBlock* node) {
   control_data_->operation = 0;
 }
 
-bool Rankings::CheckEntry(CacheRankingsBlock* rankings) {
-  if (rankings->VerifyHash())
-    return true;
-
-  // If this entry is not dirty, it is a serious problem.
-  return backend_->GetCurrentEntryId() != rankings->Data()->dirty;
-}
-
 bool Rankings::CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev,
                           CacheRankingsBlock* next, List* list) {
   CacheAddr node_addr = node->address().value();
@@ -787,44 +779,119 @@ bool Rankings::CheckSingleLink(CacheRankingsBlock* prev,
 }
 
 int Rankings::CheckList(List list) {
-  Addr& my_head = heads_[list];
-  Addr& my_tail = tails_[list];
-  if (!my_head.is_initialized()) {
-    if (!my_tail.is_initialized())
-      return 0;
-    // If there is no head, having a tail is an error.
-    return ERR_INVALID_TAIL;
+  Addr last1, last2;
+  int head_items;
+  int rv = CheckListSection(list, last1, last2, true,  // Head to tail.
+                            &last1, &last2, &head_items);
+  if (rv == 0)
+    return head_items;
+
+  Addr last3, last4;
+  int tail_items;
+  int rv2 = CheckListSection(list, last1, last2, false,  // Tail to head.
+                             &last3, &last4, &tail_items);
+
+  if (!head_items && rv != ERR_INVALID_NEXT)
+    rv = ERR_INVALID_HEAD;
+
+  if (!tail_items && rv2 != ERR_INVALID_NEXT)
+    rv2 = ERR_INVALID_HEAD;
+
+  int expected = control_data_->sizes[list];
+  int total_items = head_items + tail_items;
+
+  if (!count_lists_) {
+    // There's no expected value, so we'll use something else. If it looks like
+    // we can rebuild the list, we lost at least one entry.
+    if (last3 == last1 || last3 == last2 || last4 == last1 || last4 == last2)
+      expected = total_items + 1;
+  }
+
+  if (expected) {
+    // This histogram has an offset so that we can see small negative values. In
+    // practice, it is linear from -9 to +8.
+    UMA_HISTOGRAM_CUSTOM_COUNTS("DiskCache.LostItems(Plus10)",
+                                expected - total_items + 10, 0, 2000, 75);
   }
-  // If there is no tail, having a head is an error.
-  if (!my_tail.is_initialized())
-    return ERR_INVALID_HEAD;
 
-  if (my_tail.is_separate_file())
-    return ERR_INVALID_TAIL;
+  const int kInvalidHead = 1;
+  const int kInvalidTail = 2;
+  const int kInvalidHeadAndTail = 3;
+  const int kOneInvalidEntry = 4;
+  const int kTwoInvalidEntries = 5;
+  const int kOneInvalidLink = 6;
+  const int kTwoInvalidLinks = 7;
+  const int kOneInvalidEntryOneInvalidLink = 8;
+
+  int error = list * 10;
+  if (rv == ERR_INVALID_HEAD && rv2 != ERR_INVALID_HEAD) {
+    error += kInvalidHead;
+  } else if (rv == ERR_INVALID_HEAD && rv2 == ERR_INVALID_HEAD) {
+    error += kInvalidHeadAndTail;
+  } else if (rv != ERR_INVALID_HEAD && rv2 == ERR_INVALID_HEAD) {
+    error += kInvalidTail;
+  } else if (rv == ERR_INVALID_ENTRY && rv2 == ERR_INVALID_ENTRY) {
+    error += kTwoInvalidEntries;
+  } else if (rv == ERR_INVALID_ENTRY && rv2 == 0) {
+    error += kOneInvalidEntry;
+  } else if (rv == ERR_INVALID_ENTRY || rv2 == ERR_INVALID_ENTRY) {
+    error += kOneInvalidEntryOneInvalidLink;
+  } else if (rv2 != 0) {
+    error += kTwoInvalidLinks;
+  } else {
+    error += kOneInvalidLink;
+  }
+  CACHE_UMA(CACHE_ERROR, "ListErrorWithListId", 0, error);
+
+  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 (my_head.is_separate_file())
+  if (!current.SanityCheckForRankings())
     return ERR_INVALID_HEAD;
 
-  int num_items = 0;
-  Addr address(my_head.value());
-  Addr prev(my_head.value());
   scoped_ptr<CacheRankingsBlock> node;
+  Addr prev_addr(current);
   do {
-    node.reset(new CacheRankingsBlock(backend_->File(address), address));
+    node.reset(new CacheRankingsBlock(backend_->File(current), current));
     node->Load();
-    if (node->Data()->prev != prev.value())
-      return ERR_INVALID_PREV;
-    if (!CheckEntry(node.get()))
+    if (!SanityCheck(node.get(), true))
       return ERR_INVALID_ENTRY;
 
-    prev.set_value(address.value());
-    address.set_value(node->Data()->next);
-    if (!address.is_initialized() || address.is_separate_file())
+    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;
 
-    num_items++;
-  } while (node->address().value() != address.value());
-  return num_items;
+    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 {
diff --git a/net/disk_cache/rankings.h b/net/disk_cache/rankings.h
index b5f6daa..b20e3f1 100644
--- a/net/disk_cache/rankings.h
+++ b/net/disk_cache/rankings.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// 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.
 
@@ -164,10 +164,6 @@ class Rankings {
   void FinishInsert(CacheRankingsBlock* rankings);
   void RevertRemove(CacheRankingsBlock* rankings);
 
-  // Returns false if this entry will not be recognized as dirty (called during
-  // selfcheck).
-  bool CheckEntry(CacheRankingsBlock* rankings);
-
   // Returns false if node is not properly linked. This method may change the
   // provided |list| to reflect the list where this node is actually stored.
   bool CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev,
@@ -180,6 +176,12 @@ class Rankings {
   // error code (negative value).
   int CheckList(List list);
 
+  // Walks a list in the desired direction until the nodes |end1| or |end2| are
+  // reached. Returns an error code (0 on success), the number of items verified
+  // and the addresses of the last nodes visited.
+  int CheckListSection(List list, Addr end1, Addr end2, bool forward,
+                       Addr* last, Addr* second_last, int* num_items);
+
   // 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) const;