base/metrics/histogram.cc

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