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