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