Refactor of Histogram related code

base/metrics/histogram.h

 // 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).
 
 // It supports calls to accumulate either time intervals (which are processed
 // as integral number of milliseconds), or arbitrary integral units.
 
-// The default layout of buckets is exponential.  For example, buckets might
-// contain (sequentially) the count of values in the following intervals:
+// For Histogram(exponential histogram), LinearHistogram and CustomHistogram,
+// the minimum for a declared range is 1 (instead of 0), while the maximum is
+// (HistogramBase::kSampleType_MAX - 1). Currently you can declare histograms
+// with ranges exceeding those limits (e.g. 0 as minimal or
+// HistogramBase::kSampleType_MAX as maximal), but those excesses will be
+// silently clamped to those limits (for backwards compatibility with existing
+// code). Best practice is to not exceed the limits.
+
+// For Histogram and LinearHistogram, the maximum for a declared range should
+// always be larger (not equal) than minmal range. Zero and
+// HistogramBase::kSampleType_MAX are implicitly added as first and last ranges,
+// so the smallest legal bucket_count is 3. However CustomHistogram can have
+// bucket count as 2 (when you give a custom ranges vector containing only 1
+// range).
+// For these 3 kinds of histograms, the max bucket count is always
+// (Histogram::kBucketCount_MAX - 1).
+
+// The buckets layout of class Histogram is exponential. For example, buckets
+// might contain (sequentially) the count of values in the following intervals:
 // [0,1), [1,2), [2,4), [4,8), [8,16), [16,32), [32,64), [64,infinity)
 // That bucket allocation would actually result from construction of a histogram
 // for values between 1 and 64, with 8 buckets, such as:
-// Histogram count(L"some name", 1, 64, 8);
+// Histogram count("some name", 1, 64, 8);
 // Note that the underflow bucket [0,1) and the overflow bucket [64,infinity)
-// are not counted by the constructor in the user supplied "bucket_count"
+// are also counted by the constructor in the user supplied "bucket_count"
 // argument.
 // The above example has an exponential ratio of 2 (doubling the bucket width
 // in each consecutive bucket.  The Histogram class automatically calculates
 // the smallest ratio that it can use to construct the number of buckets
 // selected in the constructor.  An another example, if you had 50 buckets,
 // and millisecond time values from 1 to 10000, then the ratio between
 // consecutive bucket widths will be approximately somewhere around the 50th
 // root of 10000.  This approach provides very fine grain (narrow) buckets
 // at the low end of the histogram scale, but allows the histogram to cover a
 // gigantic range with the addition of very few buckets.
 
-// Histograms use a pattern involving a function static variable, that is a
-// pointer to a histogram.  This static is explicitly initialized on any thread
+// Usually we use macros to define and use a histogram. These macros use a
+// pattern involving a function static variable, that is a pointer to a
+// histogram.  This static is explicitly initialized on any thread
 // that detects a uninitialized (NULL) pointer.  The potentially racy
 // initialization is not a problem as it is always set to point to the same
 // value (i.e., the FactoryGet always returns the same value).  FactoryGet
 // is also completely thread safe, which results in a completely thread safe,
 // and relatively fast, set of counters.  To avoid races at shutdown, the static
 // pointer is NOT deleted, and we leak the histograms at process termination.
 
 #ifndef BASE_METRICS_HISTOGRAM_H_
 #define BASE_METRICS_HISTOGRAM_H_
 
@@ skipping 127 matching lines @@
 // problems down the line if you add additional buckets to the histogram.  Note
 // also that, despite explicitly setting the minimum bucket value to |1| below,
 // it is fine for enumerated histograms to be 0-indexed -- this is because
 // enumerated histograms should never have underflow.
 #define HISTOGRAM_ENUMERATION(name, sample, boundary_value) \
     STATIC_HISTOGRAM_POINTER_BLOCK(name, Add(sample), \
         base::LinearHistogram::FactoryGet(name, 1, boundary_value, \
             boundary_value + 1, base::Histogram::kNoFlags))
 
 // Support histograming of an enumerated value. Samples should be one of the
-// std::vector<int> list provided via |custom_ranges|. You can use the helper
-// function |base::CustomHistogram::ArrayToCustomRanges(samples, num_samples)|
-// to transform a C-style array of valid sample values to a std::vector<int>.
+// std::vector<int> list provided via |custom_ranges|. See comments above
+// CustomRanges::FactoryGet about the requirement of |custom_ranges|.
+// You can use the helper function CustomHistogram::ArrayToCustomRanges to
+// transform a C-style array of valid sample values to a std::vector<int>.
 #define HISTOGRAM_CUSTOM_ENUMERATION(name, sample, custom_ranges) \
     STATIC_HISTOGRAM_POINTER_BLOCK(name, Add(sample), \
         base::CustomHistogram::FactoryGet(name, custom_ranges, \
                                           base::Histogram::kNoFlags))
 
 //------------------------------------------------------------------------------
 // Define Debug vs non-debug flavors of macros.
 #ifndef NDEBUG
 
 #define DHISTOGRAM_TIMES(name, sample) HISTOGRAM_TIMES(name, sample)
@@ skipping 138 matching lines @@
 
   typedef std::vector<Count> Counts;
 
   // These enums are used to facilitate deserialization of renderer histograms
   // into the browser.
   enum ClassType {
     HISTOGRAM,
     LINEAR_HISTOGRAM,
     BOOLEAN_HISTOGRAM,
     CUSTOM_HISTOGRAM,
-    NOT_VALID_IN_RENDERER
+    NOT_VALID_IN_RENDERER,
   };
 
   enum BucketLayout {
     EXPONENTIAL,
     LINEAR,
-    CUSTOM
+    CUSTOM,
   };
 
   enum Flags {
     kNoFlags = 0,
     kUmaTargetedHistogramFlag = 0x1,  // Histogram should be UMA uploaded.
 
     // Indicate that the histogram was pickled to be sent across an IPC Channel.
     // If we observe this flag on a histogram being aggregated into after IPC,
     // then we are running in a single process mode, and the aggregation should
     // not take place (as we would be aggregating back into the source
@@ skipping 16 matching lines @@
   struct DescriptionPair {
     Sample sample;
     const char* description;  // Null means end of a list of pairs.
   };
 
   //----------------------------------------------------------------------------
   // Statistic values, developed over the life of the histogram.
 
   class BASE_EXPORT SampleSet {
    public:
-    explicit SampleSet();
+    explicit SampleSet(size_t size);
+    SampleSet();
     ~SampleSet();
 
-    // Adjust size of counts_ for use with given histogram.
-    void Resize(const Histogram& histogram);
-    void CheckSize(const Histogram& histogram) const;
+    void Resize(size_t size);
 
     // Accessor for histogram to make routine additions.
     void Accumulate(Sample value, Count count, size_t index);
 
     // Accessor methods.
+    size_t size() const { return counts_.size(); }
     Count counts(size_t i) const { return counts_[i]; }
     Count TotalCount() const;
     int64 sum() const { return sum_; }
     int64 redundant_count() const { return redundant_count_; }
 
     // Arithmetic manipulation of corresponding elements of the set.
     void Add(const SampleSet& other);
     void Subtract(const SampleSet& other);
 
     bool Serialize(Pickle* pickle) const;
@@ skipping 35 matching lines @@
   static Histogram* FactoryGet(const std::string& name,
                                Sample minimum,
                                Sample maximum,
                                size_t bucket_count,
                                Flags flags);
   static Histogram* FactoryTimeGet(const std::string& name,
                                    base::TimeDelta minimum,
                                    base::TimeDelta maximum,
                                    size_t bucket_count,
                                    Flags flags);
+
   // Time call for use with DHISTOGRAM*.
   // Returns TimeTicks::Now() in debug and TimeTicks() in release build.
   static TimeTicks DebugNow();
 
+  static void InitializeBucketRanges(Sample minimum,
+                                     Sample maximum,
+                                     size_t bucket_count,
+                                     BucketRanges* ranges);
+
   virtual void Add(Sample value) OVERRIDE;
 
   // This method is an interface, used only by BooleanHistogram.
   virtual void AddBoolean(bool value);
 
   // Accept a TimeDelta to increment.
   void AddTime(TimeDelta time) {
     Add(static_cast<int>(time.InMilliseconds()));
   }
 
@@ skipping 36 matching lines @@
   // have memory over-writes, or DRAM failures).
   virtual Inconsistencies FindCorruption(const SampleSet& snapshot) const;
 
   //----------------------------------------------------------------------------
   // Accessors for factory constuction, serialization and testing.
   //----------------------------------------------------------------------------
   virtual ClassType histogram_type() const;
   Sample declared_min() const { return declared_min_; }
   Sample declared_max() const { return declared_max_; }
   virtual Sample ranges(size_t i) const;
-  uint32 range_checksum() const { return range_checksum_; }
   virtual size_t bucket_count() const;
-  BucketRanges* bucket_ranges() const { return bucket_ranges_; }
-  void set_bucket_ranges(BucketRanges* bucket_ranges) {
-    bucket_ranges_ = bucket_ranges;
-  }
+  const BucketRanges* bucket_ranges() const { return bucket_ranges_; }
+
   // Snapshot the current complete set of sample data.
   // Override with atomic/locked snapshot if needed.
   virtual void SnapshotSample(SampleSet* sample) const;
 
-  virtual bool HasConstructorArguments(Sample minimum, Sample maximum,
-                                       size_t bucket_count);
-
-  virtual bool HasConstructorTimeDeltaArguments(TimeDelta minimum,
-                                                TimeDelta maximum,
-                                                size_t bucket_count);
-  // Return true iff the range_checksum_ matches current |ranges_| vector in
-  // |bucket_ranges_|.
-  bool HasValidRangeChecksum() const;
-
+  virtual bool HasConstructionArguments(Sample minimum,
+                                        Sample maximum,
+                                        size_t bucket_count);
  protected:
-  Histogram(const std::string& name, Sample minimum,
-            Sample maximum, size_t bucket_count);
-  Histogram(const std::string& name, TimeDelta minimum,
-            TimeDelta maximum, size_t bucket_count);
+  // |bucket_count| and |ranges| should contain the underflow and overflow
+  // buckets. See top comments for example.
+  Histogram(const std::string& name,
+            Sample minimum,
+            Sample maximum,
+            size_t bucket_count,
+            const BucketRanges* ranges);
 
   virtual ~Histogram();
 
+  // This function validates histogram construction arguments. It returns false
+  // if some of the arguments are totally bad.
+  // Note. Currently it allow some bad input, e.g. 0 as minimum, but silently
+  // converts it to good input: 1.
+  // TODO(kaiwang): Be more restrict and return false for any bad input, and
+  // make this a readonly validating function.
+  static bool InspectConstructionArguments(const std::string& name,
+                                           Sample* minimum,
+                                           Sample* maximum,
+                                           size_t* bucket_count);
+
   // Serialize the histogram's ranges to |*pickle|, returning true on success.
   // Most subclasses can leave this no-op implementation, but some will want to
   // override it, especially if the ranges cannot be re-derived from other
   // serialized parameters.
   virtual bool SerializeRanges(Pickle* pickle) const;
 
-  // Initialize ranges_ mapping in bucket_ranges_.
-  void InitializeBucketRange();
-
   // Method to override to skip the display of the i'th bucket if it's empty.
   virtual bool PrintEmptyBucket(size_t index) const;
 
   //----------------------------------------------------------------------------
   // Methods to override to create histogram with different bucket widths.
   //----------------------------------------------------------------------------
   // Find bucket to increment for sample value.
   virtual size_t BucketIndex(Sample value) const;
   // Get normalized size, relative to the ranges(i).
   virtual double GetBucketSize(Count current, size_t i) const;
 
-  // Recalculate range_checksum_.
-  void ResetRangeChecksum();
-
   // Return a string description of what goes in a given bucket.
   // Most commonly this is the numeric value, but in derived classes it may
   // be a name (or string description) given to the bucket.
   virtual const std::string GetAsciiBucketRange(size_t it) const;
 
   //----------------------------------------------------------------------------
   // Methods to override to create thread safe histogram.
   //----------------------------------------------------------------------------
   // Update all our internal data, including histogram
   virtual void Accumulate(Sample value, Count count, size_t index);
 
-  //----------------------------------------------------------------------------
-  // Accessors for derived classes.
-  //----------------------------------------------------------------------------
-  void SetBucketRange(size_t i, Sample value);
-
-  // Validate that ranges_ in bucket_ranges_ was created sensibly (top and
-  // bottom range values relate properly to the declared_min_ and
-  // declared_max_).
-  bool ValidateBucketRanges() const;
-
-  virtual uint32 CalculateRangeChecksum() const;
-
  private:
   // Allow tests to corrupt our innards for testing purposes.
   FRIEND_TEST_ALL_PREFIXES(HistogramTest, CorruptBucketBounds);
   FRIEND_TEST_ALL_PREFIXES(HistogramTest, CorruptSampleCounts);
   FRIEND_TEST_ALL_PREFIXES(HistogramTest, Crc32SampleHash);
   FRIEND_TEST_ALL_PREFIXES(HistogramTest, Crc32TableTest);
 
   friend class StatisticsRecorder;  // To allow it to delete duplicates.
-
-  // Post constructor initialization.
-  void Initialize();
-
-  // Checksum function for accumulating range values into a checksum.
-  static uint32 Crc32(uint32 sum, Sample range);
+  friend class StatisticsRecorderTest;
 
   //----------------------------------------------------------------------------
   // Helpers for emitting Ascii graphic.  Each method appends data to output.
 
   void WriteAsciiImpl(bool graph_it,
                       const std::string& newline,
                       std::string* output) const;
 
   // Find out how large the (graphically) the largest bucket will appear to be.
   double GetPeakBucketSize(const SampleSet& snapshot) const;
@@ skipping 10 matching lines @@
 
   // Write textual description of the bucket contents (relative to histogram).
   // Output is the count in the buckets, as well as the percentage.
   void WriteAsciiBucketValue(Count current, double scaled_sum,
                              std::string* output) const;
 
   // Produce actual graph (set of blank vs non blank char's) for a bucket.
   void WriteAsciiBucketGraph(double current_size, double max_size,
                              std::string* output) const;
 
-  //----------------------------------------------------------------------------
-  // Table for generating Crc32 values.
-  static const uint32 kCrcTable[256];
-  //----------------------------------------------------------------------------
-  // Invariant values set at/near construction time
+  // Does not own this object. Should get from StatisticsRecorder.
+  const BucketRanges* bucket_ranges_;
 
   Sample declared_min_;  // Less than this goes into counts_[0]
   Sample declared_max_;  // Over this goes into counts_[bucket_count_ - 1].
   size_t bucket_count_;  // Dimension of counts_[].
 
   // Flag the histogram for recording by UMA via metric_services.h.
   Flags flags_;
 
-  // For each index, show the least value that can be stored in the
-  // corresponding bucket. We also append one extra element in this array,
-  // containing kSampleType_MAX, to make calculations easy.
-  // The dimension of ranges_ in bucket_ranges_ is bucket_count + 1.
-  BucketRanges* bucket_ranges_;
-
-  // For redundancy, we store a checksum of all the sample ranges when ranges
-  // are generated.  If ever there is ever a difference, then the histogram must
-  // have been corrupted.
-  uint32 range_checksum_;
-
   // Finally, provide the state that changes with the addition of each new
   // sample.
   SampleSet sample_;
 
   DISALLOW_COPY_AND_ASSIGN(Histogram);
 };
 
 //------------------------------------------------------------------------------
 
 // LinearHistogram is a more traditional histogram, with evenly spaced
 // buckets.
 class BASE_EXPORT LinearHistogram : public Histogram {
  public:
   virtual ~LinearHistogram();
 
   /* minimum should start from 1. 0 is as minimum is invalid. 0 is an implicit
      default underflow bucket. */
   static Histogram* FactoryGet(const std::string& name,
                                Sample minimum,
                                Sample maximum,
                                size_t bucket_count,
                                Flags flags);
   static Histogram* FactoryTimeGet(const std::string& name,
                                    TimeDelta minimum,
                                    TimeDelta maximum,
                                    size_t bucket_count,
                                    Flags flags);
 
+  static void InitializeBucketRanges(Sample minimum,
+                                     Sample maximum,
+                                     size_t bucket_count,
+                                     BucketRanges* ranges);
+
   // Overridden from Histogram:
   virtual ClassType histogram_type() const OVERRIDE;
 
   // Store a list of number/text values for use in rendering the histogram.
   // The last element in the array has a null in its "description" slot.
   virtual void SetRangeDescriptions(
       const DescriptionPair descriptions[]) OVERRIDE;
 
  protected:
-  LinearHistogram(const std::string& name, Sample minimum,
-                  Sample maximum, size_t bucket_count);
+  LinearHistogram(const std::string& name,
+                  Sample minimum,
+                  Sample maximum,
+                  size_t bucket_count,
+                  const BucketRanges* ranges);
 
-  LinearHistogram(const std::string& name, TimeDelta minimum,
-                  TimeDelta maximum, size_t bucket_count);
-
-  // Initialize ranges_ mapping in bucket_ranges_.
-  void InitializeBucketRange();
   virtual double GetBucketSize(Count current, size_t i) const OVERRIDE;
 
   // If we have a description for a bucket, then return that.  Otherwise
   // let parent class provide a (numeric) description.
   virtual const std::string GetAsciiBucketRange(size_t i) const OVERRIDE;
 
   // Skip printing of name for numeric range if we have a name (and if this is
   // an empty bucket).
   virtual bool PrintEmptyBucket(size_t index) const OVERRIDE;
 
@@ skipping 12 matching lines @@
 // BooleanHistogram is a histogram for booleans.
 class BASE_EXPORT BooleanHistogram : public LinearHistogram {
  public:
   static Histogram* FactoryGet(const std::string& name, Flags flags);
 
   virtual ClassType histogram_type() const OVERRIDE;
 
   virtual void AddBoolean(bool value) OVERRIDE;
 
  private:
-  explicit BooleanHistogram(const std::string& name);
+  BooleanHistogram(const std::string& name, const BucketRanges* ranges);
 
   DISALLOW_COPY_AND_ASSIGN(BooleanHistogram);
 };
 
 //------------------------------------------------------------------------------
 
 // CustomHistogram is a histogram for a set of custom integers.
 class BASE_EXPORT CustomHistogram : public Histogram {
  public:
-
+  // |custom_ranges| contains a vector of limits on ranges. Each limit should be
+  // > 0 and < kSampleType_MAX. (Currently 0 is still accepted for backward
+  // compatibility). The limits can be unordered or contain duplication, but
+  // client should not depend on this.
   static Histogram* FactoryGet(const std::string& name,
                                const std::vector<Sample>& custom_ranges,
                                Flags flags);
 
   // Overridden from Histogram:
   virtual ClassType histogram_type() const OVERRIDE;
 
   // Helper method for transforming an array of valid enumeration values
   // to the std::vector<int> expected by HISTOGRAM_CUSTOM_ENUMERATION.
   // This function ensures that a guard bucket exists right after any
   // valid sample value (unless the next higher sample is also a valid value),
   // so that invalid samples never fall into the same bucket as valid samples.
+  // TODO(kaiwang): Change name to ArrayToCustomEnumRanges.
   static std::vector<Sample> ArrayToCustomRanges(const Sample* values,
                                                  size_t num_values);
 
   // Helper for deserializing CustomHistograms.  |*ranges| should already be
   // correctly sized before this call.  Return true on success.
   static bool DeserializeRanges(PickleIterator* iter,
-                                std::vector<Histogram::Sample>* ranges);
-
-
+                                std::vector<Sample>* ranges);
  protected:
   CustomHistogram(const std::string& name,
-                  const std::vector<Sample>& custom_ranges);
+                  const BucketRanges* ranges);
 
   virtual bool SerializeRanges(Pickle* pickle) const OVERRIDE;
 
-  // Initialize ranges_ mapping in bucket_ranges_.
-  void InitializedCustomBucketRange(const std::vector<Sample>& custom_ranges);
   virtual double GetBucketSize(Count current, size_t i) const OVERRIDE;
 
+ private:
+  static bool ValidateCustomRanges(const std::vector<Sample>& custom_ranges);
+  static BucketRanges* CreateBucketRangesFromCustomRanges(
+      const std::vector<Sample>& custom_ranges);
+
   DISALLOW_COPY_AND_ASSIGN(CustomHistogram);
 };
 
 }  // namespace base
 
 #endif  // BASE_METRICS_HISTOGRAM_H_