Disk Cache: Add more corruption tracking histograms.

net/disk_cache/rankings.cc

Index: net/disk_cache/rankings.cc
===================================================================
--- net/disk_cache/rankings.cc	(revision 133063)
+++ net/disk_cache/rankings.cc	(working copy)
@@ -724,14 +724,6 @@
   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 @@
 }
 
 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 num_items;
+  int rv = CheckListSection(list, last1, last2, FORWARD,
+                            &last1, &last2, &num_items);
+  if (rv == 0)
+    return num_items;
+
+  Addr last3, last4;

[gavinp, 2012/04/26 15:46:54]

Don't we mean "first" and "second" here?

[rvargas (doing something else), 2012/04/27 00:18:10]

I'm sorry I don't follow you here. What is first and second?. This is the third
and fourth values that this function receives from calling CheckListSection...
so we have up to two nodes seen in each direction, but this code really doesn't
have a need (so far) to differentiate between them. We may need that in the
future if we attempt to fix the list.

So that's what I have four generic names, because they are just four generic
nodes.

[gavinp, 2012/04/30 18:57:15]

If I'm moving backwards, then when I reach the end, isn't that the beginning?

On 2012/04/27 00:18:10, rvargas wrote:

[rvargas (doing something else), 2012/04/30 22:03:00]

sort of... but that would confuse me. The returned values would be the closest
nodes to the head that were seen by that function, but that doesn't really make
them the beginning (or first nodes). I'm happy to rename them but I have yet not
found what would they be.

Consider that the list may be completely broken, not just by a misplaced node,
but by whole pages not reaching disk... so there's no relationship between
last1/2 and last3/4, as in there's no way to tell which nodes are really closer
to the head or tail... they may reflect just two views (in time) of the list,
and adding too much meaning to what they are (other than the "last node seen by
a given search") may be misleading.

+  int num_items2;

[gavinp, 2012/04/26 15:46:54]

num_items_backwards ?

+  int rv2 = CheckListSection(list, last1, last2, BACKWARD,
+                             &last3, &last4, &num_items2);
+
+  if (!num_items && rv != ERR_INVALID_NEXT)
+    rv = ERR_INVALID_HEAD;
+
+  if (!num_items2 && rv2 != ERR_INVALID_NEXT)
+    rv2 = ERR_INVALID_HEAD;
+
+  int expected = control_data_->sizes[list];
+  int total_items = num_items + num_items2;
+
+  if (!count_lists_) {
+    // There's no expected value, so we'll use something else.

[gavinp, 2012/04/26 15:46:54]

So, if the second element is the last element or the second last element, or the
first element is the last or second last, we expected one more than we had? 
Why?

[rvargas (doing something else), 2012/04/27 00:18:10]

Not an exact science, but if the two searches overlap, it means that we are not
missing anything... but there is at least one item that we'll discard
(otherwise, there should be no error). If the searches don't overlap we have no
idea how many elements are missing.

+    if (last3 == last1 || last3 == last2 || last4 == last1 || last4 == last2)
+      expected = total_items + 1;
   }
-  // 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;
+  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",

[gavinp, 2012/04/26 15:46:54]

So if I understand the comment, the range is  -9 to +8.   The name says it's the
number of lost items.  The call to HISTOGRAM_CUSTOM_COUNTS puts the minimum as
0, which is histogramspeak for 1, which is really 0 since all underflow will be
0.  The maximum is given as 2000, and 75 buckets are allocated, even though we
just said we only want 18.

UMA_HISTOGRAM_ENUMERATION("DiskCache.LostItemsPlus10", expected - total_items +
10, 18);  // comment justifying 18.

[rvargas (doing something else), 2012/04/27 00:18:10]

Nope. IMO, the histogram ranges (log ones) are kind of broken, and it boils down
to "try something until it looks like what you want". What I want is a log scale
with enough range to see if we miss 1000 items on a list, to see if we miss the
stop markers (even though we have two to reduce that chance), and get a
reasonable resolution around 0.

The comment states that the range is linear from -9 to +8.. that means that all
buckets are storing just one value... -10 (aka 0) is the negative overflow, and
I don't really know what it means... probably that the counter is wrong, maybe
that we really missed the markers. From 19 to 2000 we have a log scale... and we
need 75 buckets in order to have that many linear buckets close to 0.

From the point of view of seeing results, it's quite easy: just subtract 10 from
the bucket that you're looking at.

Note that the actual histogram description is where the "user" should know
what's being measured.

[gavinp, 2012/04/30 18:57:15]

Aha!  This is right on the cusp (so it's probably not worth it), but in a
situation like this a custom range can be great; we could reduce the 55 buckets
you have used to extend the range up to 2000 to something like 20; saving some
ram in each client that's reporting this histogram.  But to save 55 buckets, the
code would have to be awfully short.

[rvargas (doing something else), 2012/04/30 22:03:00]

Note that I'm actually happy with the usual 50 buckets that we have (in terms of
enough resolution and uniformity). In this case, I was also looking for that,
except with a custom range that went somewhat into the negative numbers...
ideally, [-x, x] should generate log shaped scales into the positive and
negative numbers... but it doesn't. I discussed this briefly with jar while
writing this code, and he didn't seem too inclined to actually fix the default
behavior (and in any case that was not going to happen before landing this CL).

So going to 75 buckets and a single histogram seemed better than 100 buckets
split into two histograms... especially because I don't really think we need the
same resolution in the negative side (I would have used something like [-20,
2000] if that worked).

On 2012/04/30 18:57:15, gavinp wrote:

+                                expected - total_items + 10, 0, 2000, 75);
+  }
 
-  if (my_head.is_separate_file())
+  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;

[gavinp, 2012/04/26 15:46:54]

10?  And not 9?

[rvargas (doing something else), 2012/04/27 00:18:10]

I'm going for something that is easier to read (when looking at the histogram),
so decimal system works better. This is just a standard "packed" value, in
decimal.

[gavinp, 2012/04/30 18:57:15]

Yeah, I thought as much.  It's a shame we can't put that in the name, at least
of the histogram at least... It's not just an error, it's the type of the list
too.  ListErrorWithType ?

On 2012/04/27 00:18:10, rvargas wrote:

[rvargas (doing something else), 2012/04/30 22:03:00]

I was thinking over lunch.. sure, ...ErrorWithList (it's not really a type of
error, it is the list in which the error occurred)... but then that would make
it DiskCache.ListErrorWithList, and that looks pretty bad. (..AndList looks
equally bad to me)

On 2012/04/30 18:57:15, gavinp wrote:

+  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, "ListError", 0, error);

[gavinp, 2012/04/26 15:46:54]

"ListTypeAndError" ??

[rvargas (doing something else), 2012/04/27 00:18:10]

ListType sounds unrelated to ListError, so ListTypeAndError doesn't tell me at
all what's being displayed... not that it really matters, because I have to read
the description to know what it's about. But I'd always forget to look under
"Type" when looking for "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 stop1, Addr stop2,
+                               ListDirection dir,
+                               Addr* last1, Addr* last2, int* num_items) {
+  Addr current = (dir == FORWARD) ? heads_[list] : tails_[list];
+  *last1 = *last2 = current;
+  *num_items = 0;
+  if (!current.is_initialized())
+    return 0;
+
+  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 = (dir == FORWARD) ? node->Data()->next : node->Data()->prev;

[gavinp, 2012/04/26 15:46:54]

This is really pessimal, including dir == FORWARD everywhere.  I realise it was
a bool, and I pushed hard for the parameter to be a bool, but why not have it
both ways?

const bool is_forward = (dir == FORWARD); 

hen we have an interface that makes callers readable, and usage is readable.

[rvargas (doing something else), 2012/04/27 00:18:10]

This is getting ridiculous. The natural value is bool, not an enum... if you
really want an enum, then live with it. I strongly believe that the previous
version is better than this one, and having even more noise around to try and
fix the issues introduced by that decision is not "the right thing to do".

On 2012/04/26 15:46:54, gavinp wrote:

[gavinp, 2012/04/30 18:57:15]

OK, so what motivates me on this is that I want callers to be obvious and easy
to read, and I want the executing code to be easy to read.  Adding an automatic
with a simple definition susceptible to the optimizer can really help with
that..

But you're right, this is not getting ridiculous, it is ridiculous we can go
back to calling the bool "is_forward" or something if both callers do it, since
it is private.  But these (dir == FORWARD) have got to go!

On 2012/04/27 00:18:10, rvargas wrote:

[rvargas (doing something else), 2012/04/30 22:03:00]

as you wish.

On 2012/04/30 18:57:15, gavinp wrote:

+    CacheAddr prev = (dir == 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;
+    *last2 = *last1;
+    *last1 = current;
+    (*num_items)++;
+
+    if (next_addr == prev_addr) {
+      Addr last = (dir == FORWARD) ? tails_[list] : heads_[list];
+      if (next_addr == last)
+        return 0;
+      return ERR_INVALID_TAIL;
+    }
+  } while (current != stop1 && current != stop2);
+  return 0;

[gavinp, 2012/04/26 15:46:54]

return OK;

 }
 
 bool Rankings::IsHead(CacheAddr addr, List* list) const {