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