Crash when we notice a corruption of the histogram range-vector...

Crash when we notice a corruption of the histogram range-vector

The range vector is calculated once when a histogram is 
constructed, and should never change over the lifetime of the
histogram.  When it does change, it means that memory is being
overwritten.  We now crash (via CHECK) when there is any 
detected corruption of the range vector.

This CL uses a more robust check-sum algorithm to detect corruption 
of the vector.  The previous algorithm just did a sum, and was
too easilly tricked by small (offsetting) changes in several
ranges.  Hopefully, this CRC-32 implementation will not be
so easilly fooled.  

I had to refactor the class to ensure that each histogram was completely
constructed before I registered it.  The old code could sometimes
register a base class (tradtional Histogram, with exponential
bucket spread) and then run the derived constructor (such as
when creating a LinearHistogram, with a second construction 
of the ranges and checksum).  I now carefully avoid
generating the checksum until fully constructing the instance,
 and then I run InitializeBuckets only once on
the instance before registering it.

bug=73939
r=mbelshe

Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=76239

[jar (doing other things), 2011-02-25 00:48:17]

If you care about the details of the CRC code, you can see very similarly
structured code on http://www.w3.org/TR/PNG/#D-CRCAppendix.  Wikipedia also
discusses the justification for the approach.

[Mike Belshe, 2011-02-25 01:21:18]

http://codereview.chromium.org/6577013/diff/6010/base/metrics/histogram.cc
File base/metrics/histogram.cc (right):

http://codereview.chromium.org/6577013/diff/6010/base/metrics/histogram.cc#ne...
base/metrics/histogram.cc:25: const uint32 Histogram::kCrcTable[256] = {0x0,
0x77073096L, 0xee0e612cL,
this table is duplicated in src/third_party/zlib/crc32.h.

(and several other places)

can we include only one?

http://codereview.chromium.org/6577013/diff/6010/base/metrics/histogram.cc#ne...
base/metrics/histogram.cc:572: sum = kCrcTable[(sum & 0xff) ^
converter.bytes[i]] ^ (sum >> 8);
I think this line must be wrong.

kCrcTable is only 256 entries long, but you can easily fly off the end of this
array.

Correct should be:
  kCrcTable[(sum ^ converter.bytes[i]) & 0xff]

Right?

http://codereview.chromium.org/6577013/diff/6010/base/metrics/histogram.cc#ne...
base/metrics/histogram.cc:574: 
nit: blank line

[jar (doing other things), 2011-02-26 17:19:55]

Ricardo: I refactored construction of a histogram, vs initialization of the
buckets, and this change is reflected in a change in the FactoryGet method. 
Please review changes to stats_histograms.  WARNING: svn is currently not
showing revision 21 (or greater), and that revision has extra code to help
validate the upcast that you perform.  If you can't see that change, I may need
to create a new CL, as perchance svn limits (me?) to 20 deltas.

Mike: This includes comments and responses to your request.  As noted below,
there is now the option of switching to more compact check-summing (no table
needed... but it is not as mathematically guaranteed good).  I'd like to see
stats for crashes with the true CRC before trying to use the more compact
SuperFastHash based approach.  The reference to the hash was provided by
Ricardo, and is apparently used elsewhere in webkit, and our code, for other
purposes.  Note that version 21 and later contained only changes to
histogram_stats, so you should be able to review all the histogram.* changes in
whatever delta 20 (or later).

http://codereview.chromium.org/6577013/diff/6010/base/metrics/histogram.cc
File base/metrics/histogram.cc (right):

http://codereview.chromium.org/6577013/diff/6010/base/metrics/histogram.cc#ne...
base/metrics/histogram.cc:25: const uint32 Histogram::kCrcTable[256] = {0x0,
0x77073096L, 0xee0e612cL,
Reaching from base into the third party libraries is probably wrong, since I
don't want to add a dependency.  I'm not sure if I should modify thirdparty to
use this table in our base either (as it will be an ongoing integration issue). 


I could switch to a more compact algorithm that does not use a table. 
ReallyFastHash could be culled down to about 6 lines (with no table), but I'd
rather leave this in place to be be sure I have a top-notch hash.  If you'd
like, I'll put in either a TODO() or the actual code (protected by const bool,
so it won't compile in).  Note that if this static is never referenced, it
should be compiled out of the source code.  If you want me to be EXTRA sure, I
can move this table definition into a block inside the code that will clearly
become dead when I flip the bool.  Your choice.

I've added the "probably good enough" hash function to the CRC code below.

On 2011/02/25 01:21:18, Mike Belshe wrote:
> this table is duplicated in src/third_party/zlib/crc32.h.
> 
> (and several other places)
> 
> can we include only one?

http://codereview.chromium.org/6577013/diff/6010/base/metrics/histogram.cc#ne...
base/metrics/histogram.cc:572: sum = kCrcTable[(sum & 0xff) ^
converter.bytes[i]] ^ (sum >> 8);
Added "unsigned" to declaration of bytes per our discussion.

On 2011/02/25 01:21:18, Mike Belshe wrote:
> I think this line must be wrong.
> 
> kCrcTable is only 256 entries long, but you can easily fly off the end of this
> array.
> 
> Correct should be:
>   kCrcTable[(sum ^ converter.bytes[i]) & 0xff]
> 
> Right?

http://codereview.chromium.org/6577013/diff/6010/base/metrics/histogram.cc#ne...
base/metrics/histogram.cc:574: 
On 2011/02/25 01:21:18, Mike Belshe wrote:
> nit: blank line

Done.

[jar (doing other things), 2011-02-26 17:28:49]

SVN appears to have returned to its senses, and either of you can review version
21 in all its glory now.

[Mike Belshe, 2011-02-28 17:19:13]

lgtm

http://codereview.chromium.org/6577013/diff/10017/base/metrics/histogram.cc
File base/metrics/histogram.cc (right):

http://codereview.chromium.org/6577013/diff/10017/base/metrics/histogram.cc#n...
base/metrics/histogram.cc:564: if (kUseRealCrc) {
nit: funky space

[jar (doing other things), 2011-02-28 18:20:09]

Corrected style nits per mbelesh's comment.

[commit-bot: I haz the power, 2011-02-28 18:34:19]

Try job failure for 6577013-10025 on win:
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=win&number...

[rvargas (doing something else), 2011-02-28 19:50:53]

http://codereview.chromium.org/6577013/diff/10025/base/metrics/histogram.h
File base/metrics/histogram.h (right):

http://codereview.chromium.org/6577013/diff/10025/base/metrics/histogram.h#ne...
base/metrics/histogram.h:660: static void Register(scoped_refptr<Histogram>*
histogram);
In general, I would consider this to be unexpected behavior given the function
name. I suggest changing the name to reflecting the new behavior.

http://codereview.chromium.org/6577013/diff/10025/net/disk_cache/stats_histog...
File net/disk_cache/stats_histogram.cc (right):

http://codereview.chromium.org/6577013/diff/10025/net/disk_cache/stats_histog...
net/disk_cache/stats_histogram.cc:35: StatsHistogram* stats_histogram = new
StatsHistogram(name, minimum, maximum,
Why use a temp variable at all?

[jar (doing other things), 2011-02-28 22:11:44]

http://codereview.chromium.org/6577013/diff/10025/base/metrics/histogram.h
File base/metrics/histogram.h (right):

http://codereview.chromium.org/6577013/diff/10025/base/metrics/histogram.h#ne...
base/metrics/histogram.h:660: static void Register(scoped_refptr<Histogram>*
histogram);
On 2011/02/28 19:50:53, rvargas wrote:
> In general, I would consider this to be unexpected behavior given the function
> name. I suggest changing the name to reflecting the new behavior.

I landed the code this morning... so.... 
I've changed the name in a separate CL, 6591052, along with
a few other small items.  I'll send you a review request shortly.

http://codereview.chromium.org/6577013/diff/10025/net/disk_cache/stats_histog...
File net/disk_cache/stats_histogram.cc (right):

http://codereview.chromium.org/6577013/diff/10025/net/disk_cache/stats_histog...
net/disk_cache/stats_histogram.cc:35: StatsHistogram* stats_histogram = new
StatsHistogram(name, minimum, maximum,
On 2011/02/28 19:50:53, rvargas wrote:
> Why use a temp variable at all?

This is subtle, and perchance worth a comment.

If I put it directly into histogram, then it is implicitly down-cast to a
Histogram type.  At that point, I'm no longer allowed to call the protected
InitializeBucketRange method.  I have to remain as a derived type until after
that call, and then I can down-cast to a Histogram and Register().

[rvargas (doing something else), 2011-02-28 23:05:33]

http://codereview.chromium.org/6577013/diff/10025/net/disk_cache/stats_histog...
File net/disk_cache/stats_histogram.cc (right):

http://codereview.chromium.org/6577013/diff/10025/net/disk_cache/stats_histog...
net/disk_cache/stats_histogram.cc:35: StatsHistogram* stats_histogram = new
StatsHistogram(name, minimum, maximum,
On 2011/02/28 22:11:44, jar wrote:
> On 2011/02/28 19:50:53, rvargas wrote:
> > Why use a temp variable at all?
> 
> This is subtle, and perchance worth a comment. I was missing that this is a
static method
> 
> If I put it directly into histogram, then it is implicitly down-cast to a
> Histogram type.  At that point, I'm no longer allowed to call the protected
> InitializeBucketRange method.  I have to remain as a derived type until after
> that call, and then I can down-cast to a Histogram and Register().

Thanks for the explanation. Wouldn't it be better just to make histogram a
StatsHistogram, and also get rid of return_histogram? Just thinking out loud.

[jar (doing other things), 2011-03-01 00:21:18]

http://codereview.chromium.org/6577013/diff/10025/net/disk_cache/stats_histog...
File net/disk_cache/stats_histogram.cc (right):

http://codereview.chromium.org/6577013/diff/10025/net/disk_cache/stats_histog...
net/disk_cache/stats_histogram.cc:35: StatsHistogram* stats_histogram = new
StatsHistogram(name, minimum, maximum,
On 2011/02/28 23:05:33, rvargas wrote:
> Wouldn't it be better just to make histogram a
> StatsHistogram, and also get rid of return_histogram?

You're code was fairly special (starting around lines 47) where you manually
up-cast to a derived class.  The pattern I used here (leading to line 42) mimics
what I did in the other derived class (which didn't need an upcast).

The original call to FindHistogram() handles only the base class type, and can't
accept a StatsHistogram* (or smart pointer).  The Register() function also has
to take a base-class type (now that it too can do an assignment to the
referenced argument), so it too can't take a StatsHistogram.

By keeping the pattern more similar in this derived class, I figured it would be
easier (in the future, if necessary) to merge future changes.