Home | History | Annotate | Download | only in metrics
      1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 // Histogram is an object that aggregates statistics, and can summarize them in
      6 // various forms, including ASCII graphical, HTML, and numerically (as a
      7 // vector of numbers corresponding to each of the aggregating buckets).
      8 // See header file for details and examples.
      9 
     10 #include "base/metrics/histogram.h"
     11 
     12 #include <limits.h>
     13 #include <math.h>
     14 
     15 #include <algorithm>
     16 #include <string>
     17 
     18 #include "base/compiler_specific.h"
     19 #include "base/debug/alias.h"
     20 #include "base/logging.h"
     21 #include "base/metrics/histogram_macros.h"
     22 #include "base/metrics/metrics_hashes.h"
     23 #include "base/metrics/sample_vector.h"
     24 #include "base/metrics/statistics_recorder.h"
     25 #include "base/pickle.h"
     26 #include "base/strings/string_util.h"
     27 #include "base/strings/stringprintf.h"
     28 #include "base/synchronization/lock.h"
     29 #include "base/values.h"
     30 
     31 namespace base {
     32 
     33 namespace {
     34 
     35 bool ReadHistogramArguments(PickleIterator* iter,
     36                             std::string* histogram_name,
     37                             int* flags,
     38                             int* declared_min,
     39                             int* declared_max,
     40                             size_t* bucket_count,
     41                             uint32_t* range_checksum) {
     42   if (!iter->ReadString(histogram_name) ||
     43       !iter->ReadInt(flags) ||
     44       !iter->ReadInt(declared_min) ||
     45       !iter->ReadInt(declared_max) ||
     46       !iter->ReadSizeT(bucket_count) ||
     47       !iter->ReadUInt32(range_checksum)) {
     48     DLOG(ERROR) << "Pickle error decoding Histogram: " << *histogram_name;
     49     return false;
     50   }
     51 
     52   // Since these fields may have come from an untrusted renderer, do additional
     53   // checks above and beyond those in Histogram::Initialize()
     54   if (*declared_max <= 0 ||
     55       *declared_min <= 0 ||
     56       *declared_max < *declared_min ||
     57       INT_MAX / sizeof(HistogramBase::Count) <= *bucket_count ||
     58       *bucket_count < 2) {
     59     DLOG(ERROR) << "Values error decoding Histogram: " << histogram_name;
     60     return false;
     61   }
     62 
     63   // We use the arguments to find or create the local version of the histogram
     64   // in this process, so we need to clear the IPC flag.
     65   DCHECK(*flags & HistogramBase::kIPCSerializationSourceFlag);
     66   *flags &= ~HistogramBase::kIPCSerializationSourceFlag;
     67 
     68   return true;
     69 }
     70 
     71 bool ValidateRangeChecksum(const HistogramBase& histogram,
     72                            uint32_t range_checksum) {
     73   const Histogram& casted_histogram =
     74       static_cast<const Histogram&>(histogram);
     75 
     76   return casted_histogram.bucket_ranges()->checksum() == range_checksum;
     77 }
     78 
     79 }  // namespace
     80 
     81 typedef HistogramBase::Count Count;
     82 typedef HistogramBase::Sample Sample;
     83 
     84 // static
     85 const size_t Histogram::kBucketCount_MAX = 16384u;
     86 
     87 HistogramBase* Histogram::FactoryGet(const std::string& name,
     88                                      Sample minimum,
     89                                      Sample maximum,
     90                                      size_t bucket_count,
     91                                      int32_t flags) {
     92   bool valid_arguments =
     93       InspectConstructionArguments(name, &minimum, &maximum, &bucket_count);
     94   DCHECK(valid_arguments);
     95 
     96   HistogramBase* histogram = StatisticsRecorder::FindHistogram(name);
     97   if (!histogram) {
     98     // To avoid racy destruction at shutdown, the following will be leaked.
     99     BucketRanges* ranges = new BucketRanges(bucket_count + 1);
    100     InitializeBucketRanges(minimum, maximum, ranges);
    101     const BucketRanges* registered_ranges =
    102         StatisticsRecorder::RegisterOrDeleteDuplicateRanges(ranges);
    103 
    104     Histogram* tentative_histogram =
    105         new Histogram(name, minimum, maximum, registered_ranges);
    106 
    107     tentative_histogram->SetFlags(flags);
    108     histogram =
    109         StatisticsRecorder::RegisterOrDeleteDuplicate(tentative_histogram);
    110   }
    111 
    112   DCHECK_EQ(HISTOGRAM, histogram->GetHistogramType());
    113   if (!histogram->HasConstructionArguments(minimum, maximum, bucket_count)) {
    114     // The construction arguments do not match the existing histogram.  This can
    115     // come about if an extension updates in the middle of a chrome run and has
    116     // changed one of them, or simply by bad code within Chrome itself.  We
    117     // return NULL here with the expectation that bad code in Chrome will crash
    118     // on dereference, but extension/Pepper APIs will guard against NULL and not
    119     // crash.
    120     LOG(ERROR) << "Histogram " << name << " has bad construction arguments";
    121     return NULL;
    122   }
    123   return histogram;
    124 }
    125 
    126 HistogramBase* Histogram::FactoryTimeGet(const std::string& name,
    127                                          TimeDelta minimum,
    128                                          TimeDelta maximum,
    129                                          size_t bucket_count,
    130                                          int32_t flags) {
    131   return FactoryGet(name, static_cast<Sample>(minimum.InMilliseconds()),
    132                     static_cast<Sample>(maximum.InMilliseconds()), bucket_count,
    133                     flags);
    134 }
    135 
    136 HistogramBase* Histogram::FactoryGet(const char* name,
    137                                      Sample minimum,
    138                                      Sample maximum,
    139                                      size_t bucket_count,
    140                                      int32_t flags) {
    141   return FactoryGet(std::string(name), minimum, maximum, bucket_count, flags);
    142 }
    143 
    144 HistogramBase* Histogram::FactoryTimeGet(const char* name,
    145                                          TimeDelta minimum,
    146                                          TimeDelta maximum,
    147                                          size_t bucket_count,
    148                                          int32_t flags) {
    149   return FactoryTimeGet(std::string(name), minimum, maximum, bucket_count,
    150                         flags);
    151 }
    152 
    153 // Calculate what range of values are held in each bucket.
    154 // We have to be careful that we don't pick a ratio between starting points in
    155 // consecutive buckets that is sooo small, that the integer bounds are the same
    156 // (effectively making one bucket get no values).  We need to avoid:
    157 //   ranges(i) == ranges(i + 1)
    158 // To avoid that, we just do a fine-grained bucket width as far as we need to
    159 // until we get a ratio that moves us along at least 2 units at a time.  From
    160 // that bucket onward we do use the exponential growth of buckets.
    161 //
    162 // static
    163 void Histogram::InitializeBucketRanges(Sample minimum,
    164                                        Sample maximum,
    165                                        BucketRanges* ranges) {
    166   double log_max = log(static_cast<double>(maximum));
    167   double log_ratio;
    168   double log_next;
    169   size_t bucket_index = 1;
    170   Sample current = minimum;
    171   ranges->set_range(bucket_index, current);
    172   size_t bucket_count = ranges->bucket_count();
    173   while (bucket_count > ++bucket_index) {
    174     double log_current;
    175     log_current = log(static_cast<double>(current));
    176     // Calculate the count'th root of the range.
    177     log_ratio = (log_max - log_current) / (bucket_count - bucket_index);
    178     // See where the next bucket would start.
    179     log_next = log_current + log_ratio;
    180     Sample next;
    181     next = static_cast<int>(floor(exp(log_next) + 0.5));
    182     if (next > current)
    183       current = next;
    184     else
    185       ++current;  // Just do a narrow bucket, and keep trying.
    186     ranges->set_range(bucket_index, current);
    187   }
    188   ranges->set_range(ranges->bucket_count(), HistogramBase::kSampleType_MAX);
    189   ranges->ResetChecksum();
    190 }
    191 
    192 // static
    193 const int Histogram::kCommonRaceBasedCountMismatch = 5;
    194 
    195 int Histogram::FindCorruption(const HistogramSamples& samples) const {
    196   int inconsistencies = NO_INCONSISTENCIES;
    197   Sample previous_range = -1;  // Bottom range is always 0.
    198   for (size_t index = 0; index < bucket_count(); ++index) {
    199     int new_range = ranges(index);
    200     if (previous_range >= new_range)
    201       inconsistencies |= BUCKET_ORDER_ERROR;
    202     previous_range = new_range;
    203   }
    204 
    205   if (!bucket_ranges()->HasValidChecksum())
    206     inconsistencies |= RANGE_CHECKSUM_ERROR;
    207 
    208   int64_t delta64 = samples.redundant_count() - samples.TotalCount();
    209   if (delta64 != 0) {
    210     int delta = static_cast<int>(delta64);
    211     if (delta != delta64)
    212       delta = INT_MAX;  // Flag all giant errors as INT_MAX.
    213     if (delta > 0) {
    214       UMA_HISTOGRAM_COUNTS("Histogram.InconsistentCountHigh", delta);
    215       if (delta > kCommonRaceBasedCountMismatch)
    216         inconsistencies |= COUNT_HIGH_ERROR;
    217     } else {
    218       DCHECK_GT(0, delta);
    219       UMA_HISTOGRAM_COUNTS("Histogram.InconsistentCountLow", -delta);
    220       if (-delta > kCommonRaceBasedCountMismatch)
    221         inconsistencies |= COUNT_LOW_ERROR;
    222     }
    223   }
    224   return inconsistencies;
    225 }
    226 
    227 Sample Histogram::ranges(size_t i) const {
    228   return bucket_ranges_->range(i);
    229 }
    230 
    231 size_t Histogram::bucket_count() const {
    232   return bucket_ranges_->bucket_count();
    233 }
    234 
    235 // static
    236 bool Histogram::InspectConstructionArguments(const std::string& name,
    237                                              Sample* minimum,
    238                                              Sample* maximum,
    239                                              size_t* bucket_count) {
    240   // Defensive code for backward compatibility.
    241   if (*minimum < 1) {
    242     DVLOG(1) << "Histogram: " << name << " has bad minimum: " << *minimum;
    243     *minimum = 1;
    244   }
    245   if (*maximum >= kSampleType_MAX) {
    246     DVLOG(1) << "Histogram: " << name << " has bad maximum: " << *maximum;
    247     *maximum = kSampleType_MAX - 1;
    248   }
    249   if (*bucket_count >= kBucketCount_MAX) {
    250     DVLOG(1) << "Histogram: " << name << " has bad bucket_count: "
    251              << *bucket_count;
    252     *bucket_count = kBucketCount_MAX - 1;
    253   }
    254 
    255   if (*minimum >= *maximum)
    256     return false;
    257   if (*bucket_count < 3)
    258     return false;
    259   if (*bucket_count > static_cast<size_t>(*maximum - *minimum + 2))
    260     return false;
    261   return true;
    262 }
    263 
    264 uint64_t Histogram::name_hash() const {
    265   return samples_->id();
    266 }
    267 
    268 HistogramType Histogram::GetHistogramType() const {
    269   return HISTOGRAM;
    270 }
    271 
    272 bool Histogram::HasConstructionArguments(Sample expected_minimum,
    273                                          Sample expected_maximum,
    274                                          size_t expected_bucket_count) const {
    275   return ((expected_minimum == declared_min_) &&
    276           (expected_maximum == declared_max_) &&
    277           (expected_bucket_count == bucket_count()));
    278 }
    279 
    280 void Histogram::Add(int value) {
    281   AddCount(value, 1);
    282 }
    283 
    284 void Histogram::AddCount(int value, int count) {
    285   DCHECK_EQ(0, ranges(0));
    286   DCHECK_EQ(kSampleType_MAX, ranges(bucket_count()));
    287 
    288   if (value > kSampleType_MAX - 1)
    289     value = kSampleType_MAX - 1;
    290   if (value < 0)
    291     value = 0;
    292   if (count <= 0) {
    293     NOTREACHED();
    294     return;
    295   }
    296   samples_->Accumulate(value, count);
    297 
    298   FindAndRunCallback(value);
    299 }
    300 
    301 scoped_ptr<HistogramSamples> Histogram::SnapshotSamples() const {
    302   return SnapshotSampleVector();
    303 }
    304 
    305 void Histogram::AddSamples(const HistogramSamples& samples) {
    306   samples_->Add(samples);
    307 }
    308 
    309 bool Histogram::AddSamplesFromPickle(PickleIterator* iter) {
    310   return samples_->AddFromPickle(iter);
    311 }
    312 
    313 // The following methods provide a graphical histogram display.
    314 void Histogram::WriteHTMLGraph(std::string* output) const {
    315   // TBD(jar) Write a nice HTML bar chart, with divs an mouse-overs etc.
    316   output->append("<PRE>");
    317   WriteAsciiImpl(true, "<br>", output);
    318   output->append("</PRE>");
    319 }
    320 
    321 void Histogram::WriteAscii(std::string* output) const {
    322   WriteAsciiImpl(true, "\n", output);
    323 }
    324 
    325 bool Histogram::SerializeInfoImpl(Pickle* pickle) const {
    326   DCHECK(bucket_ranges()->HasValidChecksum());
    327   return pickle->WriteString(histogram_name()) &&
    328       pickle->WriteInt(flags()) &&
    329       pickle->WriteInt(declared_min()) &&
    330       pickle->WriteInt(declared_max()) &&
    331       pickle->WriteSizeT(bucket_count()) &&
    332       pickle->WriteUInt32(bucket_ranges()->checksum());
    333 }
    334 
    335 Histogram::Histogram(const std::string& name,
    336                      Sample minimum,
    337                      Sample maximum,
    338                      const BucketRanges* ranges)
    339   : HistogramBase(name),
    340     bucket_ranges_(ranges),
    341     declared_min_(minimum),
    342     declared_max_(maximum) {
    343   if (ranges)
    344     samples_.reset(new SampleVector(HashMetricName(name), ranges));
    345 }
    346 
    347 Histogram::~Histogram() {
    348 }
    349 
    350 bool Histogram::PrintEmptyBucket(size_t /* index */) const {
    351   return true;
    352 }
    353 
    354 // Use the actual bucket widths (like a linear histogram) until the widths get
    355 // over some transition value, and then use that transition width.  Exponentials
    356 // get so big so fast (and we don't expect to see a lot of entries in the large
    357 // buckets), so we need this to make it possible to see what is going on and
    358 // not have 0-graphical-height buckets.
    359 double Histogram::GetBucketSize(Count current, size_t i) const {
    360   DCHECK_GT(ranges(i + 1), ranges(i));
    361   static const double kTransitionWidth = 5;
    362   double denominator = ranges(i + 1) - ranges(i);
    363   if (denominator > kTransitionWidth)
    364     denominator = kTransitionWidth;  // Stop trying to normalize.
    365   return current/denominator;
    366 }
    367 
    368 const std::string Histogram::GetAsciiBucketRange(size_t i) const {
    369   return GetSimpleAsciiBucketRange(ranges(i));
    370 }
    371 
    372 //------------------------------------------------------------------------------
    373 // Private methods
    374 
    375 // static
    376 HistogramBase* Histogram::DeserializeInfoImpl(PickleIterator* iter) {
    377   std::string histogram_name;
    378   int flags;
    379   int declared_min;
    380   int declared_max;
    381   size_t bucket_count;
    382   uint32_t range_checksum;
    383 
    384   if (!ReadHistogramArguments(iter, &histogram_name, &flags, &declared_min,
    385                               &declared_max, &bucket_count, &range_checksum)) {
    386     return NULL;
    387   }
    388 
    389   // Find or create the local version of the histogram in this process.
    390   HistogramBase* histogram = Histogram::FactoryGet(
    391       histogram_name, declared_min, declared_max, bucket_count, flags);
    392 
    393   if (!ValidateRangeChecksum(*histogram, range_checksum)) {
    394     // The serialized histogram might be corrupted.
    395     return NULL;
    396   }
    397   return histogram;
    398 }
    399 
    400 scoped_ptr<SampleVector> Histogram::SnapshotSampleVector() const {
    401   scoped_ptr<SampleVector> samples(
    402       new SampleVector(samples_->id(), bucket_ranges()));
    403   samples->Add(*samples_);
    404   return samples;
    405 }
    406 
    407 void Histogram::WriteAsciiImpl(bool graph_it,
    408                                const std::string& newline,
    409                                std::string* output) const {
    410   // Get local (stack) copies of all effectively volatile class data so that we
    411   // are consistent across our output activities.
    412   scoped_ptr<SampleVector> snapshot = SnapshotSampleVector();
    413   Count sample_count = snapshot->TotalCount();
    414 
    415   WriteAsciiHeader(*snapshot, sample_count, output);
    416   output->append(newline);
    417 
    418   // Prepare to normalize graphical rendering of bucket contents.
    419   double max_size = 0;
    420   if (graph_it)
    421     max_size = GetPeakBucketSize(*snapshot);
    422 
    423   // Calculate space needed to print bucket range numbers.  Leave room to print
    424   // nearly the largest bucket range without sliding over the histogram.
    425   size_t largest_non_empty_bucket = bucket_count() - 1;
    426   while (0 == snapshot->GetCountAtIndex(largest_non_empty_bucket)) {
    427     if (0 == largest_non_empty_bucket)
    428       break;  // All buckets are empty.
    429     --largest_non_empty_bucket;
    430   }
    431 
    432   // Calculate largest print width needed for any of our bucket range displays.
    433   size_t print_width = 1;
    434   for (size_t i = 0; i < bucket_count(); ++i) {
    435     if (snapshot->GetCountAtIndex(i)) {
    436       size_t width = GetAsciiBucketRange(i).size() + 1;
    437       if (width > print_width)
    438         print_width = width;
    439     }
    440   }
    441 
    442   int64_t remaining = sample_count;
    443   int64_t past = 0;
    444   // Output the actual histogram graph.
    445   for (size_t i = 0; i < bucket_count(); ++i) {
    446     Count current = snapshot->GetCountAtIndex(i);
    447     if (!current && !PrintEmptyBucket(i))
    448       continue;
    449     remaining -= current;
    450     std::string range = GetAsciiBucketRange(i);
    451     output->append(range);
    452     for (size_t j = 0; range.size() + j < print_width + 1; ++j)
    453       output->push_back(' ');
    454     if (0 == current && i < bucket_count() - 1 &&
    455         0 == snapshot->GetCountAtIndex(i + 1)) {
    456       while (i < bucket_count() - 1 &&
    457              0 == snapshot->GetCountAtIndex(i + 1)) {
    458         ++i;
    459       }
    460       output->append("... ");
    461       output->append(newline);
    462       continue;  // No reason to plot emptiness.
    463     }
    464     double current_size = GetBucketSize(current, i);
    465     if (graph_it)
    466       WriteAsciiBucketGraph(current_size, max_size, output);
    467     WriteAsciiBucketContext(past, current, remaining, i, output);
    468     output->append(newline);
    469     past += current;
    470   }
    471   DCHECK_EQ(sample_count, past);
    472 }
    473 
    474 double Histogram::GetPeakBucketSize(const SampleVector& samples) const {
    475   double max = 0;
    476   for (size_t i = 0; i < bucket_count() ; ++i) {
    477     double current_size = GetBucketSize(samples.GetCountAtIndex(i), i);
    478     if (current_size > max)
    479       max = current_size;
    480   }
    481   return max;
    482 }
    483 
    484 void Histogram::WriteAsciiHeader(const SampleVector& samples,
    485                                  Count sample_count,
    486                                  std::string* output) const {
    487   StringAppendF(output,
    488                 "Histogram: %s recorded %d samples",
    489                 histogram_name().c_str(),
    490                 sample_count);
    491   if (0 == sample_count) {
    492     DCHECK_EQ(samples.sum(), 0);
    493   } else {
    494     double average = static_cast<float>(samples.sum()) / sample_count;
    495 
    496     StringAppendF(output, ", average = %.1f", average);
    497   }
    498   if (flags() & ~kHexRangePrintingFlag)
    499     StringAppendF(output, " (flags = 0x%x)", flags() & ~kHexRangePrintingFlag);
    500 }
    501 
    502 void Histogram::WriteAsciiBucketContext(const int64_t past,
    503                                         const Count current,
    504                                         const int64_t remaining,
    505                                         const size_t i,
    506                                         std::string* output) const {
    507   double scaled_sum = (past + current + remaining) / 100.0;
    508   WriteAsciiBucketValue(current, scaled_sum, output);
    509   if (0 < i) {
    510     double percentage = past / scaled_sum;
    511     StringAppendF(output, " {%3.1f%%}", percentage);
    512   }
    513 }
    514 
    515 void Histogram::GetParameters(DictionaryValue* params) const {
    516   params->SetString("type", HistogramTypeToString(GetHistogramType()));
    517   params->SetInteger("min", declared_min());
    518   params->SetInteger("max", declared_max());
    519   params->SetInteger("bucket_count", static_cast<int>(bucket_count()));
    520 }
    521 
    522 void Histogram::GetCountAndBucketData(Count* count,
    523                                       int64_t* sum,
    524                                       ListValue* buckets) const {
    525   scoped_ptr<SampleVector> snapshot = SnapshotSampleVector();
    526   *count = snapshot->TotalCount();
    527   *sum = snapshot->sum();
    528   size_t index = 0;
    529   for (size_t i = 0; i < bucket_count(); ++i) {
    530     Sample count_at_index = snapshot->GetCountAtIndex(i);
    531     if (count_at_index > 0) {
    532       scoped_ptr<DictionaryValue> bucket_value(new DictionaryValue());
    533       bucket_value->SetInteger("low", ranges(i));
    534       if (i != bucket_count() - 1)
    535         bucket_value->SetInteger("high", ranges(i + 1));
    536       bucket_value->SetInteger("count", count_at_index);
    537       buckets->Set(index, bucket_value.release());
    538       ++index;
    539     }
    540   }
    541 }
    542 
    543 //------------------------------------------------------------------------------
    544 // LinearHistogram: This histogram uses a traditional set of evenly spaced
    545 // buckets.
    546 //------------------------------------------------------------------------------
    547 
    548 LinearHistogram::~LinearHistogram() {}
    549 
    550 HistogramBase* LinearHistogram::FactoryGet(const std::string& name,
    551                                            Sample minimum,
    552                                            Sample maximum,
    553                                            size_t bucket_count,
    554                                            int32_t flags) {
    555   return FactoryGetWithRangeDescription(
    556       name, minimum, maximum, bucket_count, flags, NULL);
    557 }
    558 
    559 HistogramBase* LinearHistogram::FactoryTimeGet(const std::string& name,
    560                                                TimeDelta minimum,
    561                                                TimeDelta maximum,
    562                                                size_t bucket_count,
    563                                                int32_t flags) {
    564   return FactoryGet(name, static_cast<Sample>(minimum.InMilliseconds()),
    565                     static_cast<Sample>(maximum.InMilliseconds()), bucket_count,
    566                     flags);
    567 }
    568 
    569 HistogramBase* LinearHistogram::FactoryGet(const char* name,
    570                                            Sample minimum,
    571                                            Sample maximum,
    572                                            size_t bucket_count,
    573                                            int32_t flags) {
    574   return FactoryGet(std::string(name), minimum, maximum, bucket_count, flags);
    575 }
    576 
    577 HistogramBase* LinearHistogram::FactoryTimeGet(const char* name,
    578                                                TimeDelta minimum,
    579                                                TimeDelta maximum,
    580                                                size_t bucket_count,
    581                                                int32_t flags) {
    582   return FactoryTimeGet(std::string(name),  minimum, maximum, bucket_count,
    583                         flags);
    584 }
    585 
    586 HistogramBase* LinearHistogram::FactoryGetWithRangeDescription(
    587     const std::string& name,
    588     Sample minimum,
    589     Sample maximum,
    590     size_t bucket_count,
    591     int32_t flags,
    592     const DescriptionPair descriptions[]) {
    593   bool valid_arguments = Histogram::InspectConstructionArguments(
    594       name, &minimum, &maximum, &bucket_count);
    595   DCHECK(valid_arguments);
    596 
    597   HistogramBase* histogram = StatisticsRecorder::FindHistogram(name);
    598   if (!histogram) {
    599     // To avoid racy destruction at shutdown, the following will be leaked.
    600     BucketRanges* ranges = new BucketRanges(bucket_count + 1);
    601     InitializeBucketRanges(minimum, maximum, ranges);
    602     const BucketRanges* registered_ranges =
    603         StatisticsRecorder::RegisterOrDeleteDuplicateRanges(ranges);
    604 
    605     LinearHistogram* tentative_histogram =
    606         new LinearHistogram(name, minimum, maximum, registered_ranges);
    607 
    608     // Set range descriptions.
    609     if (descriptions) {
    610       for (int i = 0; descriptions[i].description; ++i) {
    611         tentative_histogram->bucket_description_[descriptions[i].sample] =
    612             descriptions[i].description;
    613       }
    614     }
    615 
    616     tentative_histogram->SetFlags(flags);
    617     histogram =
    618         StatisticsRecorder::RegisterOrDeleteDuplicate(tentative_histogram);
    619   }
    620 
    621   DCHECK_EQ(LINEAR_HISTOGRAM, histogram->GetHistogramType());
    622   if (!histogram->HasConstructionArguments(minimum, maximum, bucket_count)) {
    623     // The construction arguments do not match the existing histogram.  This can
    624     // come about if an extension updates in the middle of a chrome run and has
    625     // changed one of them, or simply by bad code within Chrome itself.  We
    626     // return NULL here with the expectation that bad code in Chrome will crash
    627     // on dereference, but extension/Pepper APIs will guard against NULL and not
    628     // crash.
    629     LOG(ERROR) << "Histogram " << name << " has bad construction arguments";
    630     return NULL;
    631   }
    632   return histogram;
    633 }
    634 
    635 HistogramType LinearHistogram::GetHistogramType() const {
    636   return LINEAR_HISTOGRAM;
    637 }
    638 
    639 LinearHistogram::LinearHistogram(const std::string& name,
    640                                  Sample minimum,
    641                                  Sample maximum,
    642                                  const BucketRanges* ranges)
    643     : Histogram(name, minimum, maximum, ranges) {
    644 }
    645 
    646 double LinearHistogram::GetBucketSize(Count current, size_t i) const {
    647   DCHECK_GT(ranges(i + 1), ranges(i));
    648   // Adjacent buckets with different widths would have "surprisingly" many (few)
    649   // samples in a histogram if we didn't normalize this way.
    650   double denominator = ranges(i + 1) - ranges(i);
    651   return current/denominator;
    652 }
    653 
    654 const std::string LinearHistogram::GetAsciiBucketRange(size_t i) const {
    655   int range = ranges(i);
    656   BucketDescriptionMap::const_iterator it = bucket_description_.find(range);
    657   if (it == bucket_description_.end())
    658     return Histogram::GetAsciiBucketRange(i);
    659   return it->second;
    660 }
    661 
    662 bool LinearHistogram::PrintEmptyBucket(size_t index) const {
    663   return bucket_description_.find(ranges(index)) == bucket_description_.end();
    664 }
    665 
    666 // static
    667 void LinearHistogram::InitializeBucketRanges(Sample minimum,
    668                                              Sample maximum,
    669                                              BucketRanges* ranges) {
    670   double min = minimum;
    671   double max = maximum;
    672   size_t bucket_count = ranges->bucket_count();
    673   for (size_t i = 1; i < bucket_count; ++i) {
    674     double linear_range =
    675         (min * (bucket_count - 1 - i) + max * (i - 1)) / (bucket_count - 2);
    676     ranges->set_range(i, static_cast<Sample>(linear_range + 0.5));
    677   }
    678   ranges->set_range(ranges->bucket_count(), HistogramBase::kSampleType_MAX);
    679   ranges->ResetChecksum();
    680 }
    681 
    682 // static
    683 HistogramBase* LinearHistogram::DeserializeInfoImpl(PickleIterator* iter) {
    684   std::string histogram_name;
    685   int flags;
    686   int declared_min;
    687   int declared_max;
    688   size_t bucket_count;
    689   uint32_t range_checksum;
    690 
    691   if (!ReadHistogramArguments(iter, &histogram_name, &flags, &declared_min,
    692                               &declared_max, &bucket_count, &range_checksum)) {
    693     return NULL;
    694   }
    695 
    696   HistogramBase* histogram = LinearHistogram::FactoryGet(
    697       histogram_name, declared_min, declared_max, bucket_count, flags);
    698   if (!ValidateRangeChecksum(*histogram, range_checksum)) {
    699     // The serialized histogram might be corrupted.
    700     return NULL;
    701   }
    702   return histogram;
    703 }
    704 
    705 //------------------------------------------------------------------------------
    706 // This section provides implementation for BooleanHistogram.
    707 //------------------------------------------------------------------------------
    708 
    709 HistogramBase* BooleanHistogram::FactoryGet(const std::string& name,
    710                                             int32_t flags) {
    711   HistogramBase* histogram = StatisticsRecorder::FindHistogram(name);
    712   if (!histogram) {
    713     // To avoid racy destruction at shutdown, the following will be leaked.
    714     BucketRanges* ranges = new BucketRanges(4);
    715     LinearHistogram::InitializeBucketRanges(1, 2, ranges);
    716     const BucketRanges* registered_ranges =
    717         StatisticsRecorder::RegisterOrDeleteDuplicateRanges(ranges);
    718 
    719     BooleanHistogram* tentative_histogram =
    720         new BooleanHistogram(name, registered_ranges);
    721 
    722     tentative_histogram->SetFlags(flags);
    723     histogram =
    724         StatisticsRecorder::RegisterOrDeleteDuplicate(tentative_histogram);
    725   }
    726 
    727   DCHECK_EQ(BOOLEAN_HISTOGRAM, histogram->GetHistogramType());
    728   return histogram;
    729 }
    730 
    731 HistogramBase* BooleanHistogram::FactoryGet(const char* name, int32_t flags) {
    732   return FactoryGet(std::string(name), flags);
    733 }
    734 
    735 HistogramType BooleanHistogram::GetHistogramType() const {
    736   return BOOLEAN_HISTOGRAM;
    737 }
    738 
    739 BooleanHistogram::BooleanHistogram(const std::string& name,
    740                                    const BucketRanges* ranges)
    741     : LinearHistogram(name, 1, 2, ranges) {}
    742 
    743 HistogramBase* BooleanHistogram::DeserializeInfoImpl(PickleIterator* iter) {
    744   std::string histogram_name;
    745   int flags;
    746   int declared_min;
    747   int declared_max;
    748   size_t bucket_count;
    749   uint32_t range_checksum;
    750 
    751   if (!ReadHistogramArguments(iter, &histogram_name, &flags, &declared_min,
    752                               &declared_max, &bucket_count, &range_checksum)) {
    753     return NULL;
    754   }
    755 
    756   HistogramBase* histogram = BooleanHistogram::FactoryGet(
    757       histogram_name, flags);
    758   if (!ValidateRangeChecksum(*histogram, range_checksum)) {
    759     // The serialized histogram might be corrupted.
    760     return NULL;
    761   }
    762   return histogram;
    763 }
    764 
    765 //------------------------------------------------------------------------------
    766 // CustomHistogram:
    767 //------------------------------------------------------------------------------
    768 
    769 HistogramBase* CustomHistogram::FactoryGet(
    770     const std::string& name,
    771     const std::vector<Sample>& custom_ranges,
    772     int32_t flags) {
    773   CHECK(ValidateCustomRanges(custom_ranges));
    774 
    775   HistogramBase* histogram = StatisticsRecorder::FindHistogram(name);
    776   if (!histogram) {
    777     BucketRanges* ranges = CreateBucketRangesFromCustomRanges(custom_ranges);
    778     const BucketRanges* registered_ranges =
    779         StatisticsRecorder::RegisterOrDeleteDuplicateRanges(ranges);
    780 
    781     // To avoid racy destruction at shutdown, the following will be leaked.
    782     CustomHistogram* tentative_histogram =
    783         new CustomHistogram(name, registered_ranges);
    784 
    785     tentative_histogram->SetFlags(flags);
    786 
    787     histogram =
    788         StatisticsRecorder::RegisterOrDeleteDuplicate(tentative_histogram);
    789   }
    790 
    791   DCHECK_EQ(histogram->GetHistogramType(), CUSTOM_HISTOGRAM);
    792   return histogram;
    793 }
    794 
    795 HistogramBase* CustomHistogram::FactoryGet(
    796     const char* name,
    797     const std::vector<Sample>& custom_ranges,
    798     int32_t flags) {
    799   return FactoryGet(std::string(name), custom_ranges, flags);
    800 }
    801 
    802 HistogramType CustomHistogram::GetHistogramType() const {
    803   return CUSTOM_HISTOGRAM;
    804 }
    805 
    806 // static
    807 std::vector<Sample> CustomHistogram::ArrayToCustomRanges(
    808     const Sample* values, size_t num_values) {
    809   std::vector<Sample> all_values;
    810   for (size_t i = 0; i < num_values; ++i) {
    811     Sample value = values[i];
    812     all_values.push_back(value);
    813 
    814     // Ensure that a guard bucket is added. If we end up with duplicate
    815     // values, FactoryGet will take care of removing them.
    816     all_values.push_back(value + 1);
    817   }
    818   return all_values;
    819 }
    820 
    821 CustomHistogram::CustomHistogram(const std::string& name,
    822                                  const BucketRanges* ranges)
    823     : Histogram(name,
    824                 ranges->range(1),
    825                 ranges->range(ranges->bucket_count() - 1),
    826                 ranges) {}
    827 
    828 bool CustomHistogram::SerializeInfoImpl(Pickle* pickle) const {
    829   if (!Histogram::SerializeInfoImpl(pickle))
    830     return false;
    831 
    832   // Serialize ranges. First and last ranges are alwasy 0 and INT_MAX, so don't
    833   // write them.
    834   for (size_t i = 1; i < bucket_ranges()->bucket_count(); ++i) {
    835     if (!pickle->WriteInt(bucket_ranges()->range(i)))
    836       return false;
    837   }
    838   return true;
    839 }
    840 
    841 double CustomHistogram::GetBucketSize(Count /* current */,
    842                                       size_t /* i */) const {
    843   return 1;
    844 }
    845 
    846 // static
    847 HistogramBase* CustomHistogram::DeserializeInfoImpl(PickleIterator* iter) {
    848   std::string histogram_name;
    849   int flags;
    850   int declared_min;
    851   int declared_max;
    852   size_t bucket_count;
    853   uint32_t range_checksum;
    854 
    855   if (!ReadHistogramArguments(iter, &histogram_name, &flags, &declared_min,
    856                               &declared_max, &bucket_count, &range_checksum)) {
    857     return NULL;
    858   }
    859 
    860   // First and last ranges are not serialized.
    861   std::vector<Sample> sample_ranges(bucket_count - 1);
    862 
    863   for (size_t i = 0; i < sample_ranges.size(); ++i) {
    864     if (!iter->ReadInt(&sample_ranges[i]))
    865       return NULL;
    866   }
    867 
    868   HistogramBase* histogram = CustomHistogram::FactoryGet(
    869       histogram_name, sample_ranges, flags);
    870   if (!ValidateRangeChecksum(*histogram, range_checksum)) {
    871     // The serialized histogram might be corrupted.
    872     return NULL;
    873   }
    874   return histogram;
    875 }
    876 
    877 // static
    878 bool CustomHistogram::ValidateCustomRanges(
    879     const std::vector<Sample>& custom_ranges) {
    880   bool has_valid_range = false;
    881   for (size_t i = 0; i < custom_ranges.size(); i++) {
    882     Sample sample = custom_ranges[i];
    883     if (sample < 0 || sample > HistogramBase::kSampleType_MAX - 1)
    884       return false;
    885     if (sample != 0)
    886       has_valid_range = true;
    887   }
    888   return has_valid_range;
    889 }
    890 
    891 // static
    892 BucketRanges* CustomHistogram::CreateBucketRangesFromCustomRanges(
    893       const std::vector<Sample>& custom_ranges) {
    894   // Remove the duplicates in the custom ranges array.
    895   std::vector<int> ranges = custom_ranges;
    896   ranges.push_back(0);  // Ensure we have a zero value.
    897   ranges.push_back(HistogramBase::kSampleType_MAX);
    898   std::sort(ranges.begin(), ranges.end());
    899   ranges.erase(std::unique(ranges.begin(), ranges.end()), ranges.end());
    900 
    901   BucketRanges* bucket_ranges = new BucketRanges(ranges.size());
    902   for (size_t i = 0; i < ranges.size(); i++) {
    903     bucket_ranges->set_range(i, ranges[i]);
    904   }
    905   bucket_ranges->ResetChecksum();
    906   return bucket_ranges;
    907 }
    908 
    909 }  // namespace base
    910