Reland code to detect corruption of histogram ranges

This code was reverted because it caused, or exposed
flakiness in sync unit test code (mostly on the Mac).
We need to monitor that closely as we re-land.


See the reviews and history in CLs:

http://codereview.chromium.org/6577013
and
http://codereview.chromium.org/6591052

This code generates CRC checksums for the histogram
bucket-range vectors, and guarantees they remain
intact when the histogram data is about to be
uploaded to UMA.  If the data is corrupted, then
we will fail on a CHECK().


r=mbelshe,rvargas
bug=73939

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

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

1 files changed, 131 insertions, 48 deletions

diff --git a/base/metrics/histogram.cc b/base/metrics/histogram.cc
index e94cef4..1d6f884 100644
--- a/base/metrics/histogram.cc
+++ b/base/metrics/histogram.cc
@@ -21,6 +21,53 @@
 
 namespace base {
 
+// Static table of checksums for all possible 8 bit bytes.
+const uint32 Histogram::kCrcTable[256] = {0x0, 0x77073096L, 0xee0e612cL,
+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
@@ -38,7 +85,8 @@ scoped_refptr<Histogram> Histogram::FactoryGet(const std::string& name,
 
   if (!StatisticsRecorder::FindHistogram(name, &histogram)) {
     histogram = new Histogram(name, minimum, maximum, bucket_count);
-    StatisticsRecorder::FindHistogram(name, &histogram);
+    histogram->InitializeBucketRange();
+    StatisticsRecorder::RegisterOrDiscardDuplicate(&histogram);
   }
 
   DCHECK_EQ(HISTOGRAM, histogram->histogram_type());
@@ -161,7 +209,7 @@ std::string Histogram::SerializeHistogramInfo(const Histogram& histogram,
   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());
 
@@ -181,7 +229,7 @@ bool Histogram::DeserializeHistogramInfo(const std::string& histogram_info) {
   int declared_min;
   int declared_max;
   size_t bucket_count;
-  int range_checksum;
+  uint32 range_checksum;
   int histogram_type;
   int pickle_flags;
   SampleSet sample;
@@ -191,7 +239,7 @@ bool Histogram::DeserializeHistogramInfo(const std::string& histogram_info) {
       !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)) {
@@ -252,18 +300,16 @@ 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 (!HasValidRangeChecksum())
     inconsistencies |= RANGE_CHECKSUM_ERROR;
 
   int64 delta64 = snapshot.redundant_count() - count;
@@ -328,6 +374,10 @@ bool Histogram::HasConstructorTimeDeltaArguments(TimeDelta minimum,
           (bucket_count == bucket_count_));
 }
 
+bool Histogram::HasValidRangeChecksum() const {
+  return CalculateRangeChecksum() == range_checksum_;
+}
+
 Histogram::Histogram(const std::string& name, Sample minimum,
                      Sample maximum, size_t bucket_count)
   : histogram_name_(name),
@@ -363,11 +413,6 @@ Histogram::~Histogram() {
 
   // Just to make sure most derived class did this properly...
   DCHECK(ValidateBucketRanges());
-  DCHECK(HasValidRangeChecksum());
-}
-
-bool Histogram::PrintEmptyBucket(size_t index) const {
-  return true;
 }
 
 // Calculate what range of values are held in each bucket.
@@ -405,6 +450,10 @@ void Histogram::InitializeBucketRange() {
   DCHECK_EQ(bucket_count(), bucket_index);
 }
 
+bool Histogram::PrintEmptyBucket(size_t index) const {
+  return true;
+}
+
 size_t Histogram::BucketIndex(Sample value) const {
   // Use simple binary search.  This is very general, but there are better
   // approaches if we knew that the buckets were linearly distributed.
@@ -478,6 +527,14 @@ bool Histogram::ValidateBucketRanges() const {
   return true;
 }
 
+uint32 Histogram::CalculateRangeChecksum() const {
+  DCHECK_EQ(ranges_.size(), bucket_count() + 1);
+  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;
+}
+
 void Histogram::Initialize() {
   sample_.Resize(*this);
   if (declared_min_ < 1)
@@ -491,22 +548,42 @@ void Histogram::Initialize() {
   DCHECK_LE(bucket_count_, maximal_bucket_count);
   DCHECK_EQ(0, ranges_[0]);
   ranges_[bucket_count_] = kSampleType_MAX;
-  InitializeBucketRange();
-  DCHECK(ValidateBucketRanges());
-  StatisticsRecorder::Register(this);
-}
-
-bool Histogram::HasValidRangeChecksum() const {
-  return CalculateRangeChecksum() == range_checksum_;
 }
 
-Histogram::Sample 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);
+// 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) {
+  const bool kUseRealCrc = true;  // TODO(jar): Switch to false and watch stats.
+  if (kUseRealCrc) {
+    union {
+      Histogram::Sample range;
+      unsigned 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);
+  } else {
+    // Use hash techniques provided in ReallyFastHash, except we don't care
+    // about "avalanching" (which would worsten the hash, and add collisions),
+    // and we don't care about edge cases since we have an even number of bytes.
+    union {
+      Histogram::Sample range;
+      uint16 ints[sizeof(Histogram::Sample) / 2];
+    } converter;
+    DCHECK_EQ(sizeof(Histogram::Sample), sizeof(converter));
+    converter.range = range;
+    sum += converter.ints[0];
+    sum = (sum << 16) ^ sum ^ (static_cast<uint32>(converter.ints[1]) << 11);
+    sum += sum >> 11;
   }
-  return checksum;
+  return sum;
 }
 
 //------------------------------------------------------------------------------
@@ -710,8 +787,11 @@ scoped_refptr<Histogram> LinearHistogram::FactoryGet(const std::string& name,
     maximum = kSampleType_MAX - 1;
 
   if (!StatisticsRecorder::FindHistogram(name, &histogram)) {
-    histogram = new LinearHistogram(name, minimum, maximum, bucket_count);
-    StatisticsRecorder::FindHistogram(name, &histogram);
+    LinearHistogram* linear_histogram =
+        new LinearHistogram(name, minimum, maximum, bucket_count);
+    linear_histogram->InitializeBucketRange();
+    histogram = linear_histogram;
+    StatisticsRecorder::RegisterOrDiscardDuplicate(&histogram);
   }
 
   DCHECK_EQ(LINEAR_HISTOGRAM, histogram->histogram_type());
@@ -746,8 +826,6 @@ LinearHistogram::LinearHistogram(const std::string& name,
                                  Sample maximum,
                                  size_t bucket_count)
     : Histogram(name, minimum >= 1 ? minimum : 1, maximum, bucket_count) {
-  InitializeBucketRange();
-  DCHECK(ValidateBucketRanges());
 }
 
 LinearHistogram::LinearHistogram(const std::string& name,
@@ -757,9 +835,6 @@ LinearHistogram::LinearHistogram(const std::string& name,
     : Histogram(name, minimum >= TimeDelta::FromMilliseconds(1) ?
                                  minimum : TimeDelta::FromMilliseconds(1),
                 maximum, bucket_count) {
-  // Do a "better" (different) job at init than a base classes did...
-  InitializeBucketRange();
-  DCHECK(ValidateBucketRanges());
 }
 
 void LinearHistogram::InitializeBucketRange() {
@@ -805,8 +880,10 @@ scoped_refptr<Histogram> BooleanHistogram::FactoryGet(const std::string& name,
   scoped_refptr<Histogram> histogram(NULL);
 
   if (!StatisticsRecorder::FindHistogram(name, &histogram)) {
-    histogram = new BooleanHistogram(name);
-    StatisticsRecorder::FindHistogram(name, &histogram);
+    BooleanHistogram* boolean_histogram = new BooleanHistogram(name);
+    boolean_histogram->InitializeBucketRange();
+    histogram = boolean_histogram;
+    StatisticsRecorder::RegisterOrDiscardDuplicate(&histogram);
   }
 
   DCHECK_EQ(BOOLEAN_HISTOGRAM, histogram->histogram_type());
@@ -850,8 +927,10 @@ scoped_refptr<Histogram> CustomHistogram::FactoryGet(
   DCHECK_LT(ranges.back(), kSampleType_MAX);
 
   if (!StatisticsRecorder::FindHistogram(name, &histogram)) {
-    histogram = new CustomHistogram(name, ranges);
-    StatisticsRecorder::FindHistogram(name, &histogram);
+    CustomHistogram* custom_histogram = new CustomHistogram(name, ranges);
+    custom_histogram->InitializedCustomBucketRange(ranges);
+    histogram = custom_histogram;
+    StatisticsRecorder::RegisterOrDiscardDuplicate(&histogram);
   }
 
   DCHECK_EQ(histogram->histogram_type(), CUSTOM_HISTOGRAM);
@@ -871,16 +950,15 @@ CustomHistogram::CustomHistogram(const std::string& name,
                 custom_ranges.size()) {
   DCHECK_GT(custom_ranges.size(), 1u);
   DCHECK_EQ(custom_ranges[0], 0);
-  ranges_vector_ = &custom_ranges;
-  InitializeBucketRange();
-  ranges_vector_ = NULL;
-  DCHECK(ValidateBucketRanges());
 }
 
-void CustomHistogram::InitializeBucketRange() {
-  DCHECK_LE(ranges_vector_->size(), bucket_count());
-  for (size_t index = 0; index < ranges_vector_->size(); ++index)
-    SetBucketRange(index, (*ranges_vector_)[index]);
+void CustomHistogram::InitializedCustomBucketRange(
+    const std::vector<Sample>& custom_ranges) {
+  DCHECK_GT(custom_ranges.size(), 1u);
+  DCHECK_EQ(custom_ranges[0], 0);
+  DCHECK_LE(custom_ranges.size(), bucket_count());
+  for (size_t index = 0; index < custom_ranges.size(); ++index)
+    SetBucketRange(index, custom_ranges[index]);
   ResetRangeChecksum();
 }
 
@@ -945,16 +1023,21 @@ bool StatisticsRecorder::IsActive() {
 // was passed to us, decremented it when we returned, and the instance would be
 // destroyed before assignment (when value was returned by new).
 // static
-void StatisticsRecorder::Register(Histogram* histogram) {
+void StatisticsRecorder::RegisterOrDiscardDuplicate(
+    scoped_refptr<Histogram>* histogram) {
+  DCHECK((*histogram)->HasValidRangeChecksum());
   if (lock_ == NULL)
     return;
   base::AutoLock auto_lock(*lock_);
   if (!histograms_)
     return;
-  const std::string name = histogram->histogram_name();
+  const std::string name = (*histogram)->histogram_name();
+  HistogramMap::iterator it = histograms_->find(name);
   // Avoid overwriting a previous registration.
-  if (histograms_->end() == histograms_->find(name))
-    (*histograms_)[name] = histogram;
+  if (histograms_->end() == it)
+    (*histograms_)[name] = *histogram;
+  else
+    *histogram = it->second;
 }
 
 // static