[histogram] Make histograms more resistant to overflows.

base/metrics/histogram.cc

 // Copyright (c) 2012 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 396 matching lines @@
 
   if (!check_okay) {
     UMA_HISTOGRAM_SPARSE_SLOWLY("Histogram.BadConstructionArguments",
                                 static_cast<Sample>(HashMetricName(name)));
   }
 
   return check_okay;
 }
 
 uint64_t Histogram::name_hash() const {
-  return samples_->id();
+  return unlogged_samples_->id();
 }
 
 HistogramType Histogram::GetHistogramType() const {
   return HISTOGRAM;
 }
 
 bool Histogram::HasConstructionArguments(Sample expected_minimum,
                                          Sample expected_maximum,
                                          uint32_t expected_bucket_count) const {
   return ((expected_minimum == declared_min_) &&
@@ skipping 10 matching lines @@
   DCHECK_EQ(kSampleType_MAX, ranges(bucket_count()));
 
   if (value > kSampleType_MAX - 1)
     value = kSampleType_MAX - 1;
   if (value < 0)
     value = 0;
   if (count <= 0) {
     NOTREACHED();
     return;
   }
-  samples_->Accumulate(value, count);
+  unlogged_samples_->Accumulate(value, count);
 
   FindAndRunCallback(value);
 }
 
 std::unique_ptr<HistogramSamples> Histogram::SnapshotSamples() const {
-  return SnapshotSampleVector();
+  return SnapshotAllSamples();
 }
 
 std::unique_ptr<HistogramSamples> Histogram::SnapshotDelta() {
   DCHECK(!final_delta_created_);
 
-  std::unique_ptr<HistogramSamples> snapshot = SnapshotSampleVector();
-  if (!logged_samples_) {
-    // If nothing has been previously logged, save this one as
-    // |logged_samples_| and gather another snapshot to return.
-    logged_samples_.swap(snapshot);
-    return SnapshotSampleVector();
-  }
+  // This code takes unlogged samples, adds them to logged samples,
+  // resets them and returns them.
+  // Correctness of this code relies on unlogged_samples being thread-safe
+  // due to atomic integer operations. Snapshot is taken by atomically copying
+  // all existing samples. Reset is implemented by subtracting copied snapshot,
+  // leaving samples added concurrently from another thread in unlogged_samples
+  // to be reported by the next call to SnapshotDelta.

[Alexei Svitkine (slow), 2017/05/11 13:54:35]

Maybe call out the function names where the atomicity happens?

e.g. for Subtract(), it's in SampleVectorBase::AddSubtractImpl().

Maybe also worth discussing why it's OK with the single bucket optimization
(where we don't allocate the full counts array until a 2nd bucket is needed).
Basically, discuss the case where we can go from single bucket to full counts
array in the middle of any of these operations (including in the middle of
Subtract) - and clearly point out why that's correct.

bcwhite@ can answer questions about how that works.

[bcwhite, 2017/05/11 17:34:52]

Basically, every individual operation is atomic but there's no synchronization
between them, hence the "eventually consistent" design.  You might read 5 but
have it (externally) incremented to 50 before that count is removed and dropping
it to 45.

The snapshot sum/count could also be off because of timing between updates and
reads.  We just live with that.

The single-bucket optimization is contained in SampleVector and its transition
from one-sample to many-sample is also atomic and "eventually consistent".  At
the SampleVectorBase API, there is no apparent difference.

[altimin, 2017/05/11 17:55:43]

I think that does not belong here. We should mention that SampleVector::Subtract
and SampleVector::Accumulate are thread-safe and maybe add a comment in
SampleVector explaining the details.

 
-  // Subtract what was previously logged and update that information.
-  snapshot->Subtract(*logged_samples_);
+  std::unique_ptr<HistogramSamples> snapshot = SnapshotUnloggedSamples();
+  unlogged_samples_->Subtract(*snapshot);
   logged_samples_->Add(*snapshot);
+
   return snapshot;
 }
 
 std::unique_ptr<HistogramSamples> Histogram::SnapshotFinalDelta() const {
   DCHECK(!final_delta_created_);
   final_delta_created_ = true;
 
-  std::unique_ptr<HistogramSamples> snapshot = SnapshotSampleVector();
-
-  // Subtract what was previously logged and then return.
-  if (logged_samples_)
-    snapshot->Subtract(*logged_samples_);
-  return snapshot;
+  return SnapshotUnloggedSamples();
 }
 
 void Histogram::AddSamples(const HistogramSamples& samples) {
-  samples_->Add(samples);
+  unlogged_samples_->Add(samples);
 }
 
 bool Histogram::AddSamplesFromPickle(PickleIterator* iter) {
-  return samples_->AddFromPickle(iter);
+  return unlogged_samples_->AddFromPickle(iter);
 }
 
 // The following methods provide a graphical histogram display.
 void Histogram::WriteHTMLGraph(std::string* output) const {
   // TBD(jar) Write a nice HTML bar chart, with divs an mouse-overs etc.
   output->append("<PRE>");
   WriteAsciiImpl(true, "<br>", output);
   output->append("</PRE>");
 }
 
@@ skipping 12 matching lines @@
 }
 
 Histogram::Histogram(const std::string& name,
                      Sample minimum,
                      Sample maximum,
                      const BucketRanges* ranges)
   : HistogramBase(name),
     bucket_ranges_(ranges),
     declared_min_(minimum),
     declared_max_(maximum) {
-  if (ranges)
-    samples_.reset(new SampleVector(HashMetricName(name), ranges));
+  if (ranges) {
+    unlogged_samples_.reset(new SampleVector(HashMetricName(name), ranges));
+    logged_samples_.reset(new SampleVector(unlogged_samples_->id(), ranges));
+  }
 }
 
 Histogram::Histogram(const std::string& name,
                      Sample minimum,
                      Sample maximum,
                      const BucketRanges* ranges,
                      const DelayedPersistentAllocation& counts,
                      const DelayedPersistentAllocation& logged_counts,
                      HistogramSamples::Metadata* meta,
                      HistogramSamples::Metadata* logged_meta)
     : HistogramBase(name),
       bucket_ranges_(ranges),
       declared_min_(minimum),
       declared_max_(maximum) {
   if (ranges) {
-    samples_.reset(
+    unlogged_samples_.reset(
         new PersistentSampleVector(HashMetricName(name), ranges, meta, counts));
     logged_samples_.reset(new PersistentSampleVector(
-        samples_->id(), ranges, logged_meta, logged_counts));
+        unlogged_samples_->id(), ranges, logged_meta, logged_counts));
   }
 }
 
 Histogram::~Histogram() {
 }
 
 bool Histogram::PrintEmptyBucket(uint32_t index) const {
   return true;
 }
 
@@ skipping 36 matching lines @@
   HistogramBase* histogram = Histogram::FactoryGet(
       histogram_name, declared_min, declared_max, bucket_count, flags);
 
   if (!ValidateRangeChecksum(*histogram, range_checksum)) {
     // The serialized histogram might be corrupted.
     return NULL;
   }
   return histogram;
 }
 
-std::unique_ptr<SampleVector> Histogram::SnapshotSampleVector() const {
-  std::unique_ptr<SampleVector> samples(
-      new SampleVector(samples_->id(), bucket_ranges()));
-  samples->Add(*samples_);
+std::unique_ptr<SampleVector> Histogram::SnapshotAllSamples() const {
+  std::unique_ptr<SampleVector> samples = SnapshotUnloggedSamples();
+  samples->Add(*logged_samples_);
   return samples;
 }
 
+std::unique_ptr<SampleVector> Histogram::SnapshotUnloggedSamples() const {
+  std::unique_ptr<SampleVector> samples(
+      new SampleVector(unlogged_samples_->id(), bucket_ranges()));
+  samples->Add(*unlogged_samples_);
+  return samples;
+}
+
 void Histogram::WriteAsciiImpl(bool graph_it,
                                const std::string& newline,
                                std::string* output) const {
   // Get local (stack) copies of all effectively volatile class data so that we
   // are consistent across our output activities.
-  std::unique_ptr<SampleVector> snapshot = SnapshotSampleVector();
+  std::unique_ptr<SampleVector> snapshot = SnapshotAllSamples();
   Count sample_count = snapshot->TotalCount();
 
   WriteAsciiHeader(*snapshot, sample_count, output);
   output->append(newline);
 
   // Prepare to normalize graphical rendering of bucket contents.
   double max_size = 0;
   if (graph_it)
     max_size = GetPeakBucketSize(*snapshot);
 
@@ skipping 91 matching lines @@
 void Histogram::GetParameters(DictionaryValue* params) const {
   params->SetString("type", HistogramTypeToString(GetHistogramType()));
   params->SetInteger("min", declared_min());
   params->SetInteger("max", declared_max());
   params->SetInteger("bucket_count", static_cast<int>(bucket_count()));
 }
 
 void Histogram::GetCountAndBucketData(Count* count,
                                       int64_t* sum,
                                       ListValue* buckets) const {
-  std::unique_ptr<SampleVector> snapshot = SnapshotSampleVector();
+  std::unique_ptr<SampleVector> snapshot = SnapshotAllSamples();
   *count = snapshot->TotalCount();
   *sum = snapshot->sum();
   uint32_t index = 0;
   for (uint32_t i = 0; i < bucket_count(); ++i) {
     Sample count_at_index = snapshot->GetCountAtIndex(i);
     if (count_at_index > 0) {
       std::unique_ptr<DictionaryValue> bucket_value(new DictionaryValue());
       bucket_value->SetInteger("low", ranges(i));
       if (i != bucket_count() - 1)
         bucket_value->SetInteger("high", ranges(i + 1));
@@ skipping 467 matching lines @@
     Sample sample = custom_ranges[i];
     if (sample < 0 || sample > HistogramBase::kSampleType_MAX - 1)
       return false;
     if (sample != 0)
       has_valid_range = true;
   }
   return has_valid_range;
 }
 
 }  // namespace base