Source code
Revision control
Copy as Markdown
Other Tools
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
// Copyright (c) 2011 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:
// [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);
// 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"
// 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
// 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_
#pragma once
#include "mozilla/Atomics.h"
#include "mozilla/MemoryReporting.h"
#include <map>
#include <string>
#include "base/time.h"
#include "nsTArray.h"
namespace base {
//------------------------------------------------------------------------------
class BooleanHistogram;
class CustomHistogram;
class Histogram;
class LinearHistogram;
class Histogram {
public:
typedef int Sample; // Used for samples (and ranges of samples).
typedef int Count; // Used to count samples in a bucket.
static const Sample kSampleType_MAX = INT_MAX;
// Initialize maximum number of buckets in histograms as 16,384.
static const size_t kBucketCount_MAX;
typedef nsTArray<Count> Counts;
typedef const Sample* Ranges;
// These enums are used to facilitate deserialization of renderer histograms
// into the browser.
enum ClassType {
HISTOGRAM,
LINEAR_HISTOGRAM,
BOOLEAN_HISTOGRAM,
FLAG_HISTOGRAM,
COUNT_HISTOGRAM,
CUSTOM_HISTOGRAM,
NOT_VALID_IN_RENDERER
};
enum BucketLayout { EXPONENTIAL, LINEAR, CUSTOM };
enum Flags {
kNoFlags = 0,
kUmaTargetedHistogramFlag = 0x1, // Histogram should be UMA uploaded.
kHexRangePrintingFlag = 0x8000 // Fancy bucket-naming supported.
};
enum Inconsistencies {
NO_INCONSISTENCIES = 0x0,
RANGE_CHECKSUM_ERROR = 0x1,
BUCKET_ORDER_ERROR = 0x2,
COUNT_HIGH_ERROR = 0x4,
COUNT_LOW_ERROR = 0x8,
NEVER_EXCEEDED_VALUE = 0x10
};
struct DescriptionPair {
Sample sample;
const char* description; // Null means end of a list of pairs.
};
size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf);
bool is_empty() const {
return this->sample_.counts(0) == 0 && this->sample_.sum() == 0;
}
//----------------------------------------------------------------------------
// Statistic values, developed over the life of the histogram.
class SampleSet {
public:
explicit SampleSet();
~SampleSet();
SampleSet(SampleSet&&) = default;
// None of the methods in this class are thread-safe. Callers
// must deal with locking themselves.
// Adjust size of counts_ for use with given histogram.
void Resize(const Histogram& histogram);
// Accessor for histogram to make routine additions.
void Accumulate(Sample value, Count count, size_t index);
// Arithmetic manipulation of corresponding elements of the set.
void Add(const SampleSet& other);
size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf);
Count counts(size_t i) const { return counts_[i]; }
Count TotalCount() const;
int64_t sum() const { return sum_; }
int64_t redundant_count() const { return redundant_count_; }
size_t size() const { return counts_.Length(); }
SampleSet Clone() const {
SampleSet result;
result.counts_ = counts_.Clone();
result.sum_ = sum_;
result.redundant_count_ = redundant_count_;
return result;
}
void Clear() {
sum_ = 0;
redundant_count_ = 0;
for (int& i : counts_) {
i = 0;
}
}
protected:
// Actual histogram data is stored in buckets, showing the count of values
// that fit into each bucket.
Counts counts_;
// Save simple stats locally. Note that this MIGHT get done in base class
// without shared memory at some point.
int64_t sum_; // sum of samples.
// To help identify memory corruption, we reduntantly save the number of
// samples we've accumulated into all of our buckets. We can compare this
// count to the sum of the counts in all buckets, and detect problems. Note
// that due to races in histogram accumulation (if a histogram is indeed
// updated on several threads simultaneously), the tallies might mismatch,
// and also the snapshotting code may asynchronously get a mismatch (though
// generally either race based mismatch cause is VERY rare).
int64_t redundant_count_;
};
//----------------------------------------------------------------------------
// minimum should start from 1. 0 is invalid as a minimum. 0 is an implicit
// default underflow bucket.
static Histogram* FactoryGet(Sample minimum, Sample maximum,
size_t bucket_count, Flags flags,
const int* buckets);
virtual ~Histogram();
void Add(int value);
void Subtract(int value);
// 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())); }
virtual void AddSampleSet(const SampleSet& sample);
virtual void Clear();
// This method is an interface, used only by LinearHistogram.
virtual void SetRangeDescriptions(const DescriptionPair descriptions[]);
// Support generic flagging of Histograms.
// 0x1 Currently used to mark this histogram to be recorded by UMA..
// 0x8000 means print ranges in hex.
void SetFlags(Flags flags) { flags_ = static_cast<Flags>(flags_ | flags); }
void ClearFlags(Flags flags) { flags_ = static_cast<Flags>(flags_ & ~flags); }
int flags() const { return flags_; }
// Check to see if bucket ranges, counts and tallies in the snapshot are
// consistent with the bucket ranges and checksums in our histogram. This can
// produce a false-alarm if a race occurred in the reading of the data during
// a SnapShot process, but should otherwise be false at all times (unless we
// 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_t range_checksum() const { return range_checksum_; }
virtual size_t bucket_count() const;
virtual SampleSet SnapshotSample() 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.
bool HasValidRangeChecksum() const;
protected:
Histogram(Sample minimum, Sample maximum, size_t bucket_count);
Histogram(TimeDelta minimum, TimeDelta maximum, size_t bucket_count);
// Initialize ranges_ mapping from raw data.
void InitializeBucketRangeFromData(const int* buckets);
// 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);
// Validate that ranges_ was created sensibly (top and bottom range
// values relate properly to the declared_min_ and declared_max_)..
bool ValidateBucketRanges() const;
virtual uint32_t CalculateRangeChecksum() const;
// Finally, provide the state that changes with the addition of each new
// sample.
SampleSet sample_;
private:
// Post constructor initialization.
void Initialize();
// Checksum function for accumulating range values into a checksum.
static uint32_t Crc32(uint32_t sum, Sample range);
//----------------------------------------------------------------------------
// Helpers for emitting Ascii graphic. Each method appends data to output.
// Find out how large the (graphically) the largest bucket will appear to be.
double GetPeakBucketSize(const SampleSet& snapshot) const;
//----------------------------------------------------------------------------
// Table for generating Crc32 values.
static const uint32_t kCrcTable[256];
//----------------------------------------------------------------------------
// Invariant values set at/near construction time
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_ is bucket_count + 1.
Ranges 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_t range_checksum_;
DISALLOW_COPY_AND_ASSIGN(Histogram);
};
//------------------------------------------------------------------------------
// LinearHistogram is a more traditional histogram, with evenly spaced
// buckets.
class 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(Sample minimum, Sample maximum,
size_t bucket_count, Flags flags,
const int* buckets);
// Overridden from Histogram:
virtual ClassType histogram_type() const override;
virtual void Accumulate(Sample value, Count count, size_t index) 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(Sample minimum, Sample maximum, size_t bucket_count);
LinearHistogram(TimeDelta minimum, TimeDelta maximum, size_t bucket_count);
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;
private:
// For some ranges, we store a printable description of a bucket range.
// If there is no desciption, then GetAsciiBucketRange() uses parent class
// to provide a description.
typedef std::map<Sample, std::string> BucketDescriptionMap;
BucketDescriptionMap bucket_description_;
DISALLOW_COPY_AND_ASSIGN(LinearHistogram);
};
//------------------------------------------------------------------------------
// BooleanHistogram is a histogram for booleans.
class BooleanHistogram : public LinearHistogram {
public:
static Histogram* FactoryGet(Flags flags, const int* buckets);
virtual ClassType histogram_type() const override;
virtual void AddBoolean(bool value) override;
virtual void Accumulate(Sample value, Count count, size_t index) override;
protected:
explicit BooleanHistogram();
DISALLOW_COPY_AND_ASSIGN(BooleanHistogram);
};
//------------------------------------------------------------------------------
// FlagHistogram is like boolean histogram, but only allows a single off/on
// value.
class FlagHistogram : public BooleanHistogram {
public:
static Histogram* FactoryGet(Flags flags, const int* buckets);
virtual ClassType histogram_type() const override;
virtual void Accumulate(Sample value, Count count, size_t index) override;
virtual void AddSampleSet(const SampleSet& sample) override;
virtual void Clear() override;
private:
explicit FlagHistogram();
bool mSwitched;
DISALLOW_COPY_AND_ASSIGN(FlagHistogram);
};
// CountHistogram only allows a single monotic counter value.
class CountHistogram : public LinearHistogram {
public:
static Histogram* FactoryGet(Flags flags, const int* buckets);
virtual ClassType histogram_type() const override;
virtual void Accumulate(Sample value, Count count, size_t index) override;
virtual void AddSampleSet(const SampleSet& sample) override;
private:
explicit CountHistogram();
DISALLOW_COPY_AND_ASSIGN(CountHistogram);
};
} // namespace base
#endif // BASE_METRICS_HISTOGRAM_H_