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

base/metrics/histogram.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.
 
 // Histogram is an object that aggregates statistics, and can summarize them in
 // various forms, including ASCII graphical, HTML, and numerically (as a
 // vector of numbers corresponding to each of the aggregating buckets).
 // See header file for details and examples.
 
 #include "base/metrics/histogram.h"
 
 #include <math.h>
 
 #include <algorithm>
 #include <string>
 
 #include "base/logging.h"
 #include "base/pickle.h"
 #include "base/stringprintf.h"
 #include "base/synchronization/lock.h"
 
 namespace base {
 
+// Static table of checksums for all possible 8 bit bytes.
+const uint32 Histogram::kCrcTable[256] = {0x0, 0x77073096L, 0xee0e612cL,

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

this table is duplicated in src/third_party/zlib/crc32.h.

(and several other places)

can we include only one?

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

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:

+0x990951baL, 0x76dc419L, 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0xedb8832L,
+0x79dcb8a4L, 0xe0d5e91eL, 0x97d2d988L, 0x9b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
+0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL, 0x1adad47dL,
+0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L, 0x646ba8c0L, 0xfd62f97aL,
+0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L, 0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L,
+0x4c69105eL, 0xd56041e4L, 0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL,
+0xa50ab56bL, 0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
+0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL, 0xc8d75180L,
+0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L, 0xb8bda50fL, 0x2802b89eL,
+0x5f058808L, 0xc60cd9b2L, 0xb10be924L, 0x2f6f7c87L, 0x58684c11L, 0xc1611dabL,
+0xb6662d3dL, 0x76dc4190L, 0x1db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L,
+0x6b6b51fL, 0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0xf00f934L, 0x9609a88eL,
+0xe10e9818L, 0x7f6a0dbbL, 0x86d3d2dL, 0x91646c97L, 0xe6635c01L, 0x6b6b51f4L,
+0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL, 0x1b01a57bL, 0x8208f4c1L,
+0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L, 0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL,
+0x15da2d49L, 0x8cd37cf3L, 0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L,
+0xd4bb30e2L, 0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
+0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L, 0xaa0a4c5fL,
+0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L, 0xc90c2086L, 0x5768b525L,
+0x206f85b3L, 0xb966d409L, 0xce61e49fL, 0x5edef90eL, 0x29d9c998L, 0xb0d09822L,
+0xc7d7a8b4L, 0x59b33d17L, 0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L,
+0x9abfb3b6L, 0x3b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x4db2615L,
+0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0xd6d6a3eL, 0x7a6a5aa8L, 0xe40ecf0bL,
+0x9309ff9dL, 0xa00ae27L, 0x7d079eb1L, 0xf00f9344L, 0x8708a3d2L, 0x1e01f268L,
+0x6906c2feL, 0xf762575dL, 0x806567cbL, 0x196c3671L, 0x6e6b06e7L, 0xfed41b76L,
+0x89d32be0L, 0x10da7a5aL, 0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L,
+0x60b08ed5L, 0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
+0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL, 0x36034af6L,
+0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL, 0x4669be79L, 0xcb61b38cL,
+0xbc66831aL, 0x256fd2a0L, 0x5268e236L, 0xcc0c7795L, 0xbb0b4703L, 0x220216b9L,
+0x5505262fL, 0xc5ba3bbeL, 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L,
+0xb5d0cf31L, 0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
+0x26d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x5005713L, 0x95bf4a82L,
+0xe2b87a14L, 0x7bb12baeL, 0xcb61b38L, 0x92d28e9bL, 0xe5d5be0dL, 0x7cdcefb7L,
+0xbdbdf21L, 0x86d3d2d4L, 0xf1d4e242L, 0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL,
+0xf6b9265bL, 0x6fb077e1L, 0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL,
+0x11010b5cL, 0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
+0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L, 0x4969474dL,
+0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L, 0x37d83bf0L, 0xa9bcae53L,
+0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L, 0xbdbdf21cL, 0xcabac28aL, 0x53b39330L,
+0x24b4a3a6L, 0xbad03605L, 0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL,
+0xc4614ab8L, 0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
+0x2d02ef8dL,
+};
+
 typedef Histogram::Count Count;
 
 // static
 const size_t Histogram::kBucketCount_MAX = 10000u;
 
 scoped_refptr<Histogram> Histogram::FactoryGet(const std::string& name,
     Sample minimum, Sample maximum, size_t bucket_count, Flags flags) {
   scoped_refptr<Histogram> histogram(NULL);
 
   // Defensive code.
@@ skipping 120 matching lines @@
 // static
 std::string Histogram::SerializeHistogramInfo(const Histogram& histogram,
                                               const SampleSet& snapshot) {
   DCHECK_NE(NOT_VALID_IN_RENDERER, histogram.histogram_type());
 
   Pickle pickle;
   pickle.WriteString(histogram.histogram_name());
   pickle.WriteInt(histogram.declared_min());
   pickle.WriteInt(histogram.declared_max());
   pickle.WriteSize(histogram.bucket_count());
-  pickle.WriteInt(histogram.range_checksum());
+  pickle.WriteUInt32(histogram.range_checksum());
   pickle.WriteInt(histogram.histogram_type());
   pickle.WriteInt(histogram.flags());
 
   snapshot.Serialize(&pickle);
   return std::string(static_cast<const char*>(pickle.data()), pickle.size());
 }
 
 // static
 bool Histogram::DeserializeHistogramInfo(const std::string& histogram_info) {
   if (histogram_info.empty()) {
       return false;
   }
 
   Pickle pickle(histogram_info.data(),
                 static_cast<int>(histogram_info.size()));
   std::string histogram_name;
   int declared_min;
   int declared_max;
   size_t bucket_count;
-  int range_checksum;
+  uint32 range_checksum;
   int histogram_type;
   int pickle_flags;
   SampleSet sample;
 
   void* iter = NULL;
   if (!pickle.ReadString(&iter, &histogram_name) ||
       !pickle.ReadInt(&iter, &declared_min) ||
       !pickle.ReadInt(&iter, &declared_max) ||
       !pickle.ReadSize(&iter, &bucket_count) ||
-      !pickle.ReadInt(&iter, &range_checksum) ||
+      !pickle.ReadUInt32(&iter, &range_checksum) ||
       !pickle.ReadInt(&iter, &histogram_type) ||
       !pickle.ReadInt(&iter, &pickle_flags) ||
       !sample.Histogram::SampleSet::Deserialize(&iter, pickle)) {
     LOG(ERROR) << "Pickle error decoding Histogram: " << histogram_name;
     return false;
   }
   DCHECK(pickle_flags & kIPCSerializationSourceFlag);
   // Since these fields may have come from an untrusted renderer, do additional
   // checks above and beyond those in Histogram::Initialize()
   if (declared_max <= 0 || declared_min <= 0 || declared_max < declared_min ||
@@ skipping 40 matching lines @@
 }
 
 //------------------------------------------------------------------------------
 // Methods for the validating a sample and a related histogram.
 //------------------------------------------------------------------------------
 
 Histogram::Inconsistencies Histogram::FindCorruption(
     const SampleSet& snapshot) const {
   int inconsistencies = NO_INCONSISTENCIES;
   Sample previous_range = -1;  // Bottom range is always 0.
-  Sample checksum = 0;
   int64 count = 0;
   for (size_t index = 0; index < bucket_count(); ++index) {
     count += snapshot.counts(index);
     int new_range = ranges(index);
-    checksum += new_range;
     if (previous_range >= new_range)
       inconsistencies |= BUCKET_ORDER_ERROR;
     previous_range = new_range;
   }
 
-  if (checksum != range_checksum_)
+  if (CalculateRangeChecksum() != range_checksum_)
     inconsistencies |= RANGE_CHECKSUM_ERROR;
 
   int64 delta64 = snapshot.redundant_count() - count;
   if (delta64 != 0) {
     int delta = static_cast<int>(delta64);
     if (delta != delta64)
       delta = INT_MAX;  // Flag all giant errors as INT_MAX.
     // Since snapshots of histograms are taken asynchronously relative to
     // sampling (and snapped from different threads), it is pretty likely that
     // we'll catch a redundant count that doesn't match the sample count.  We
@@ skipping 216 matching lines @@
   ranges_[bucket_count_] = kSampleType_MAX;
   InitializeBucketRange();
   DCHECK(ValidateBucketRanges());
   StatisticsRecorder::Register(this);
 }
 
 bool Histogram::HasValidRangeChecksum() const {
   return CalculateRangeChecksum() == range_checksum_;
 }
 
-Histogram::Sample Histogram::CalculateRangeChecksum() const {
+uint32 Histogram::CalculateRangeChecksum() const {
   DCHECK_EQ(ranges_.size(), bucket_count() + 1);
-  Sample checksum = 0;
-  for (size_t index = 0; index < bucket_count(); ++index) {
-    checksum += ranges(index);
-  }
+  uint32 checksum = static_cast<uint32>(ranges_.size());  // Seed checksum.
+  for (size_t index = 0; index < bucket_count(); ++index)
+    checksum = Crc32(checksum, ranges(index));
   return checksum;
 }
 
+// We generate the CRC-32 using the low order bits to select whether to XOR in
+// the reversed polynomial 0xedb88320L.  This is nice and simple, and allows us
+// to keep the quotient in a uint32.  Since we're not concerned about the nature
+// of corruptions (i.e., we don't care about bit sequencing, since we are
+// handling memory changes, which are more grotesque) so we don't bother to
+// get the CRC correct for big-endian vs little-ending calculations.  All we
+// need is a nice hash, that tends to depend on all the bits of the sample, with
+// very little chance of changes in one place impacting changes in another
+// place.
+uint32 Histogram::Crc32(uint32 sum, Histogram::Sample range) {
+  union {
+    Histogram::Sample range;
+    char bytes[sizeof(Histogram::Sample)];
+  } converter;
+  converter.range = range;
+  for (size_t i = 0; i < sizeof(converter); ++i)
+    sum = kCrcTable[(sum & 0xff) ^ converter.bytes[i]] ^ (sum >> 8);

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

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?

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

Added "unsigned" to declaration of bytes per our discussion.

On 2011/02/25 01:21:18, Mike Belshe wrote:

+  return sum;
+

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

nit: blank line

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

Done.

+}
+
 //------------------------------------------------------------------------------
 // Private methods
 
 double Histogram::GetPeakBucketSize(const SampleSet& snapshot) const {
   double max = 0;
   for (size_t i = 0; i < bucket_count() ; ++i) {
     double current_size = GetBucketSize(snapshot.counts(i), i);
     if (current_size > max)
       max = current_size;
   }
@@ skipping 525 matching lines @@
 }
 
 // static
 StatisticsRecorder::HistogramMap* StatisticsRecorder::histograms_ = NULL;
 // static
 base::Lock* StatisticsRecorder::lock_ = NULL;
 // static
 bool StatisticsRecorder::dump_on_exit_ = false;
 
 }  // namespace base