Try to detect internal corruption of histogram instances....

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"
@@ skipping 43 matching lines @@
 }
 
 Histogram::Histogram(const std::string& name, Sample minimum,
                      Sample maximum, size_t bucket_count)
   : histogram_name_(name),
     declared_min_(minimum),
     declared_max_(maximum),
     bucket_count_(bucket_count),
     flags_(kNoFlags),
     ranges_(bucket_count + 1, 0),
+    range_checksum_(0),
     sample_() {
   Initialize();
 }
 
 Histogram::Histogram(const std::string& name, TimeDelta minimum,
                      TimeDelta maximum, size_t bucket_count)
   : histogram_name_(name),
     declared_min_(static_cast<int> (minimum.InMilliseconds())),
     declared_max_(static_cast<int> (maximum.InMilliseconds())),
     bucket_count_(bucket_count),
     flags_(kNoFlags),
     ranges_(bucket_count + 1, 0),
+    range_checksum_(0),
     sample_() {
   Initialize();
 }
 
 Histogram::~Histogram() {
   if (StatisticsRecorder::dump_on_exit()) {
     std::string output;
     WriteAscii(true, "\n", &output);
     LOG(INFO) << output;
   }
 
   // Just to make sure most derived class did this properly...
   DCHECK(ValidateBucketRanges());
+  DCHECK(HasValidRangeChecksum());
 }
 
 bool Histogram::PrintEmptyBucket(size_t index) const {
   return true;
 }
 
 void Histogram::Add(int value) {
   if (value > kSampleType_MAX - 1)
     value = kSampleType_MAX - 1;
   if (value < 0)
@@ skipping 112 matching lines @@
   ranges_[bucket_count_] = kSampleType_MAX;
   InitializeBucketRange();
   DCHECK(ValidateBucketRanges());
   StatisticsRecorder::Register(this);
 }
 
 // Calculate what range of values are held in each bucket.
 // We have to be careful that we don't pick a ratio between starting points in
 // consecutive buckets that is sooo small, that the integer bounds are the same
 // (effectively making one bucket get no values).  We need to avoid:
-// (ranges_[i] == ranges_[i + 1]
+//   ranges_[i] == ranges_[i + 1]
 // To avoid that, we just do a fine-grained bucket width as far as we need to
 // until we get a ratio that moves us along at least 2 units at a time.  From
 // that bucket onward we do use the exponential growth of buckets.
 void Histogram::InitializeBucketRange() {
   double log_max = log(static_cast<double>(declared_max()));
   double log_ratio;
   double log_next;
   size_t bucket_index = 1;
   Sample current = declared_min();
   SetBucketRange(bucket_index, current);
   while (bucket_count() > ++bucket_index) {
     double log_current;
     log_current = log(static_cast<double>(current));
     // Calculate the count'th root of the range.
     log_ratio = (log_max - log_current) / (bucket_count() - bucket_index);
     // See where the next bucket would start.
     log_next = log_current + log_ratio;
     int next;
     next = static_cast<int>(floor(exp(log_next) + 0.5));
     if (next > current)
       current = next;
     else
       ++current;  // Just do a narrow bucket, and keep trying.
     SetBucketRange(bucket_index, current);
   }
+  ResetRangeChecksum();
 
   DCHECK_EQ(bucket_count(), bucket_index);
 }
 
 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.
   DCHECK_LE(ranges(0), value);
   DCHECK_GT(ranges(bucket_count()), value);
   size_t under = 0;
@@ skipping 23 matching lines @@
 // not have 0-graphical-height buckets.
 double Histogram::GetBucketSize(Count current, size_t i) const {
   DCHECK_GT(ranges(i + 1), ranges(i));
   static const double kTransitionWidth = 5;
   double denominator = ranges(i + 1) - ranges(i);
   if (denominator > kTransitionWidth)
     denominator = kTransitionWidth;  // Stop trying to normalize.
   return current/denominator;
 }
 
+void Histogram::ResetRangeChecksum() {
+  range_checksum_ = CalculateRangeChecksum();
+}
+
+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);
+  }
+  return checksum;
+}
+
 //------------------------------------------------------------------------------
 // The following two methods can be overridden to provide a thread safe
 // version of this class.  The cost of locking is low... but an error in each
 // of these methods has minimal impact.  For now, I'll leave this unlocked,
 // and I don't believe I can loose more than a count or two.
 // The vectors are NOT reallocated, so there is no risk of them moving around.
 
 // Update histogram data with new sample.
 void Histogram::Accumulate(Sample value, Count count, size_t index) {
   // Note locking not done in this version!!!
@@ skipping 110 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.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()));
-  void* iter = NULL;
-  size_t bucket_count;
+  std::string histogram_name;
   int declared_min;
   int declared_max;
+  size_t bucket_count;
+  int range_checksum;
   int histogram_type;
   int pickle_flags;
-  std::string histogram_name;
   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.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 18 matching lines @@
     render_histogram = BooleanHistogram::FactoryGet(histogram_name, flags);
   } else {
     LOG(ERROR) << "Error Deserializing Histogram Unknown histogram_type: "
                << histogram_type;
     return false;
   }
 
   DCHECK_EQ(render_histogram->declared_min(), declared_min);
   DCHECK_EQ(render_histogram->declared_max(), declared_max);
   DCHECK_EQ(render_histogram->bucket_count(), bucket_count);
+  DCHECK_EQ(render_histogram->range_checksum(), range_checksum);
   DCHECK_EQ(render_histogram->histogram_type(), histogram_type);
 
   if (render_histogram->flags() & kIPCSerializationSourceFlag) {
     DVLOG(1) << "Single process mode, histogram observed and not copied: "
              << histogram_name;
   } else {
     DCHECK_EQ(flags & render_histogram->flags(), flags);
     render_histogram->AddSampleSet(sample);
   }
 
   return true;
 }
 
 //------------------------------------------------------------------------------
+// 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_)
+    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
+    // allow for a certain amount of slop before flagging this as an
+    // inconsistency.  Even with an inconsistency, we'll snapshot it again (for
+    // UMA in about a half hour, so we'll eventually get the data, if it was
+    // not the result of a corruption.  If histograms show that 1 is "too tight"
+    // then we may try to use 2 or 3 for this slop value.
+    const int kCommonRaceBasedCountMismatch = 1;
+    if (delta > 0) {
+      UMA_HISTOGRAM_COUNTS("Histogram.InconsistentCountHigh", delta);
+      if (delta > kCommonRaceBasedCountMismatch)
+        inconsistencies |= COUNT_HIGH_ERROR;
+    } else {
+      DCHECK_GT(0, delta);
+      UMA_HISTOGRAM_COUNTS("Histogram.InconsistentCountLow", -delta);
+      if (-delta > kCommonRaceBasedCountMismatch)
+        inconsistencies |= COUNT_LOW_ERROR;
+    }
+  }
+  return static_cast<Inconsistencies>(inconsistencies);
+}
+
+//------------------------------------------------------------------------------
 // Methods for the Histogram::SampleSet class
 //------------------------------------------------------------------------------
 
 Histogram::SampleSet::SampleSet()
     : counts_(),
       sum_(0),
-      square_sum_(0) {
+      square_sum_(0),
+      redundant_count_(0) {
 }
 
 Histogram::SampleSet::~SampleSet() {
 }
 
 void Histogram::SampleSet::Resize(const Histogram& histogram) {
   counts_.resize(histogram.bucket_count(), 0);
 }
 
 void Histogram::SampleSet::CheckSize(const Histogram& histogram) const {
   DCHECK_EQ(histogram.bucket_count(), counts_.size());
 }
 
 
 void Histogram::SampleSet::Accumulate(Sample value,  Count count,
                                       size_t index) {
   DCHECK(count == 1 || count == -1);
   counts_[index] += count;
   sum_ += count * value;
   square_sum_ += (count * value) * static_cast<int64>(value);
+  redundant_count_ += count;
   DCHECK_GE(counts_[index], 0);
   DCHECK_GE(sum_, 0);
   DCHECK_GE(square_sum_, 0);
+  DCHECK_GE(redundant_count_, 0);
 }
 
 Count Histogram::SampleSet::TotalCount() const {
   Count total = 0;
   for (Counts::const_iterator it = counts_.begin();
        it != counts_.end();
        ++it) {
     total += *it;
   }
+  DCHECK_EQ(total, redundant_count_);
   return total;
 }
 
 void Histogram::SampleSet::Add(const SampleSet& other) {
   DCHECK_EQ(counts_.size(), other.counts_.size());
   sum_ += other.sum_;
   square_sum_ += other.square_sum_;
+  redundant_count_ += other.redundant_count_;
   for (size_t index = 0; index < counts_.size(); ++index)
     counts_[index] += other.counts_[index];
 }
 
 void Histogram::SampleSet::Subtract(const SampleSet& other) {
   DCHECK_EQ(counts_.size(), other.counts_.size());
   // Note: Race conditions in snapshotting a sum or square_sum may lead to
   // (temporary) negative values when snapshots are later combined (and deltas
   // calculated).  As a result, we don't currently CHCEK() for positive values.
   sum_ -= other.sum_;
   square_sum_ -= other.square_sum_;
+  redundant_count_ -= other.redundant_count_;
   for (size_t index = 0; index < counts_.size(); ++index) {
     counts_[index] -= other.counts_[index];
     DCHECK_GE(counts_[index], 0);
   }
 }
 
 bool Histogram::SampleSet::Serialize(Pickle* pickle) const {
   pickle->WriteInt64(sum_);
   pickle->WriteInt64(square_sum_);
+  pickle->WriteInt64(redundant_count_);
   pickle->WriteSize(counts_.size());
 
   for (size_t index = 0; index < counts_.size(); ++index) {
     pickle->WriteInt(counts_[index]);
   }
 
   return true;
 }
 
 bool Histogram::SampleSet::Deserialize(void** iter, const Pickle& pickle) {
   DCHECK_EQ(counts_.size(), 0u);
   DCHECK_EQ(sum_, 0);
   DCHECK_EQ(square_sum_, 0);
+  DCHECK_EQ(redundant_count_, 0);
 
   size_t counts_size;
 
   if (!pickle.ReadInt64(iter, &sum_) ||
       !pickle.ReadInt64(iter, &square_sum_) ||
+      !pickle.ReadInt64(iter, &redundant_count_) ||
       !pickle.ReadSize(iter, &counts_size)) {
     return false;
   }
 
   if (counts_size == 0)
     return false;
 
+  int count = 0;
   for (size_t index = 0; index < counts_size; ++index) {
     int i;
     if (!pickle.ReadInt(iter, &i))
       return false;
     counts_.push_back(i);
+    count += i;
   }
-
-  return true;
+  DCHECK_EQ(count, redundant_count_);
+  return count == redundant_count_;
 }
 
 //------------------------------------------------------------------------------
 // LinearHistogram: This histogram uses a traditional set of evenly spaced
 // buckets.
 //------------------------------------------------------------------------------
 
 scoped_refptr<Histogram> LinearHistogram::FactoryGet(const std::string& name,
                                                      Sample minimum,
                                                      Sample maximum,
@@ skipping 78 matching lines @@
 void LinearHistogram::InitializeBucketRange() {
   DCHECK_GT(declared_min(), 0);  // 0 is the underflow bucket here.
   double min = declared_min();
   double max = declared_max();
   size_t i;
   for (i = 1; i < bucket_count(); ++i) {
     double linear_range = (min * (bucket_count() -1 - i) + max * (i - 1)) /
                           (bucket_count() - 2);
     SetBucketRange(i, static_cast<int> (linear_range + 0.5));
   }
+  ResetRangeChecksum();
 }
 
 double LinearHistogram::GetBucketSize(Count current, size_t i) const {
   DCHECK_GT(ranges(i + 1), ranges(i));
   // Adjacent buckets with different widths would have "surprisingly" many (few)
   // samples in a histogram if we didn't normalize this way.
   double denominator = ranges(i + 1) - ranges(i);
   return current/denominator;
 }
 
@@ skipping 26 matching lines @@
 BooleanHistogram::BooleanHistogram(const std::string& name)
     : LinearHistogram(name, 1, 2, 3) {
 }
 
 //------------------------------------------------------------------------------
 // CustomHistogram:
 //------------------------------------------------------------------------------
 
 scoped_refptr<Histogram> CustomHistogram::FactoryGet(
     const std::string& name,
-    const std::vector<int>& custom_ranges,
+    const std::vector<Sample>& custom_ranges,
     Flags flags) {
   scoped_refptr<Histogram> histogram(NULL);
 
   // Remove the duplicates in the custom ranges array.
   std::vector<int> ranges = custom_ranges;
   ranges.push_back(0);  // Ensure we have a zero value.
   std::sort(ranges.begin(), ranges.end());
   ranges.erase(std::unique(ranges.begin(), ranges.end()), ranges.end());
   if (ranges.size() <= 1) {
     DCHECK(false);
@@ skipping 13 matching lines @@
                                             ranges.size()));
   histogram->SetFlags(flags);
   return histogram;
 }
 
 Histogram::ClassType CustomHistogram::histogram_type() const {
   return CUSTOM_HISTOGRAM;
 }
 
 CustomHistogram::CustomHistogram(const std::string& name,
-                                 const std::vector<int>& custom_ranges)
+                                 const std::vector<Sample>& custom_ranges)
     : Histogram(name, custom_ranges[1], custom_ranges.back(),
                 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]);
+  ResetRangeChecksum();
 }
 
 double CustomHistogram::GetBucketSize(Count current, size_t i) const {
   return 1;
 }
 
 //------------------------------------------------------------------------------
 // The next section handles global (central) support for all histograms, as well
 // as startup/teardown of this service.
 //------------------------------------------------------------------------------
@@ skipping 125 matching lines @@
 }
 
 // static
 StatisticsRecorder::HistogramMap* StatisticsRecorder::histograms_ = NULL;
 // static
 Lock* StatisticsRecorder::lock_ = NULL;
 // static
 bool StatisticsRecorder::dump_on_exit_ = false;
 
 }  // namespace base