histogram.cc revision 72a454cd3513ac24fbdd0e0cb9ad70b86a99b801 
1// Copyright (c) 2010 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/logging.h"
18#include "base/pickle.h"
19#include "base/stringprintf.h"
20#include "base/synchronization/lock.h"
21
22namespace base {
23
24typedef Histogram::Count Count;
25
26scoped_refptr<Histogram> Histogram::FactoryGet(const std::string& name,
27    Sample minimum, Sample maximum, size_t bucket_count, Flags flags) {
28  scoped_refptr<Histogram> histogram(NULL);
29
30  // Defensive code.
31  if (minimum < 1)
32    minimum = 1;
33  if (maximum > kSampleType_MAX - 1)
34    maximum = kSampleType_MAX - 1;
35
36  if (!StatisticsRecorder::FindHistogram(name, &histogram)) {
37    histogram = new Histogram(name, minimum, maximum, bucket_count);
38    StatisticsRecorder::FindHistogram(name, &histogram);
39  }
40
41  DCHECK_EQ(HISTOGRAM, histogram->histogram_type());
42  DCHECK(histogram->HasConstructorArguments(minimum, maximum, bucket_count));
43  histogram->SetFlags(flags);
44  return histogram;
45}
46
47scoped_refptr<Histogram> Histogram::FactoryTimeGet(const std::string& name,
48                                                   TimeDelta minimum,
49                                                   TimeDelta maximum,
50                                                   size_t bucket_count,
51                                                   Flags flags) {
52  return FactoryGet(name, minimum.InMilliseconds(), maximum.InMilliseconds(),
53                    bucket_count, flags);
54}
55
56void Histogram::Add(int value) {
57  if (value > kSampleType_MAX - 1)
58    value = kSampleType_MAX - 1;
59  if (value < 0)
60    value = 0;
61  size_t index = BucketIndex(value);
62  DCHECK_GE(value, ranges(index));
63  DCHECK_LT(value, ranges(index + 1));
64  Accumulate(value, 1, index);
65}
66
67void Histogram::AddBoolean(bool value) {
68  DCHECK(false);
69}
70
71void Histogram::AddSampleSet(const SampleSet& sample) {
72  sample_.Add(sample);
73}
74
75void Histogram::SetRangeDescriptions(const DescriptionPair descriptions[]) {
76  DCHECK(false);
77}
78
79// The following methods provide a graphical histogram display.
80void Histogram::WriteHTMLGraph(std::string* output) const {
81  // TBD(jar) Write a nice HTML bar chart, with divs an mouse-overs etc.
82  output->append("<PRE>");
83  WriteAscii(true, "<br>", output);
84  output->append("</PRE>");
85}
86
87void Histogram::WriteAscii(bool graph_it, const std::string& newline,
88                           std::string* output) const {
89  // Get local (stack) copies of all effectively volatile class data so that we
90  // are consistent across our output activities.
91  SampleSet snapshot;
92  SnapshotSample(&snapshot);
93  Count sample_count = snapshot.TotalCount();
94
95  WriteAsciiHeader(snapshot, sample_count, output);
96  output->append(newline);
97
98  // Prepare to normalize graphical rendering of bucket contents.
99  double max_size = 0;
100  if (graph_it)
101    max_size = GetPeakBucketSize(snapshot);
102
103  // Calculate space needed to print bucket range numbers.  Leave room to print
104  // nearly the largest bucket range without sliding over the histogram.
105  size_t largest_non_empty_bucket = bucket_count() - 1;
106  while (0 == snapshot.counts(largest_non_empty_bucket)) {
107    if (0 == largest_non_empty_bucket)
108      break;  // All buckets are empty.
109    --largest_non_empty_bucket;
110  }
111
112  // Calculate largest print width needed for any of our bucket range displays.
113  size_t print_width = 1;
114  for (size_t i = 0; i < bucket_count(); ++i) {
115    if (snapshot.counts(i)) {
116      size_t width = GetAsciiBucketRange(i).size() + 1;
117      if (width > print_width)
118        print_width = width;
119    }
120  }
121
122  int64 remaining = sample_count;
123  int64 past = 0;
124  // Output the actual histogram graph.
125  for (size_t i = 0; i < bucket_count(); ++i) {
126    Count current = snapshot.counts(i);
127    if (!current && !PrintEmptyBucket(i))
128      continue;
129    remaining -= current;
130    std::string range = GetAsciiBucketRange(i);
131    output->append(range);
132    for (size_t j = 0; range.size() + j < print_width + 1; ++j)
133      output->push_back(' ');
134    if (0 == current && i < bucket_count() - 1 && 0 == snapshot.counts(i + 1)) {
135      while (i < bucket_count() - 1 && 0 == snapshot.counts(i + 1))
136        ++i;
137      output->append("... ");
138      output->append(newline);
139      continue;  // No reason to plot emptiness.
140    }
141    double current_size = GetBucketSize(current, i);
142    if (graph_it)
143      WriteAsciiBucketGraph(current_size, max_size, output);
144    WriteAsciiBucketContext(past, current, remaining, i, output);
145    output->append(newline);
146    past += current;
147  }
148  DCHECK_EQ(sample_count, past);
149}
150
151// static
152std::string Histogram::SerializeHistogramInfo(const Histogram& histogram,
153                                              const SampleSet& snapshot) {
154  DCHECK_NE(NOT_VALID_IN_RENDERER, histogram.histogram_type());
155
156  Pickle pickle;
157  pickle.WriteString(histogram.histogram_name());
158  pickle.WriteInt(histogram.declared_min());
159  pickle.WriteInt(histogram.declared_max());
160  pickle.WriteSize(histogram.bucket_count());
161  pickle.WriteInt(histogram.range_checksum());
162  pickle.WriteInt(histogram.histogram_type());
163  pickle.WriteInt(histogram.flags());
164
165  snapshot.Serialize(&pickle);
166  return std::string(static_cast<const char*>(pickle.data()), pickle.size());
167}
168
169// static
170bool Histogram::DeserializeHistogramInfo(const std::string& histogram_info) {
171  if (histogram_info.empty()) {
172      return false;
173  }
174
175  Pickle pickle(histogram_info.data(),
176                static_cast<int>(histogram_info.size()));
177  std::string histogram_name;
178  int declared_min;
179  int declared_max;
180  size_t bucket_count;
181  int range_checksum;
182  int histogram_type;
183  int pickle_flags;
184  SampleSet sample;
185
186  void* iter = NULL;
187  if (!pickle.ReadString(&iter, &histogram_name) ||
188      !pickle.ReadInt(&iter, &declared_min) ||
189      !pickle.ReadInt(&iter, &declared_max) ||
190      !pickle.ReadSize(&iter, &bucket_count) ||
191      !pickle.ReadInt(&iter, &range_checksum) ||
192      !pickle.ReadInt(&iter, &histogram_type) ||
193      !pickle.ReadInt(&iter, &pickle_flags) ||
194      !sample.Histogram::SampleSet::Deserialize(&iter, pickle)) {
195    LOG(ERROR) << "Pickle error decoding Histogram: " << histogram_name;
196    return false;
197  }
198  DCHECK(pickle_flags & kIPCSerializationSourceFlag);
199  // Since these fields may have come from an untrusted renderer, do additional
200  // checks above and beyond those in Histogram::Initialize()
201  if (declared_max <= 0 || declared_min <= 0 || declared_max < declared_min ||
202      INT_MAX / sizeof(Count) <= bucket_count || bucket_count < 2) {
203    LOG(ERROR) << "Values error decoding Histogram: " << histogram_name;
204    return false;
205  }
206
207  Flags flags = static_cast<Flags>(pickle_flags & ~kIPCSerializationSourceFlag);
208
209  DCHECK_NE(NOT_VALID_IN_RENDERER, histogram_type);
210
211  scoped_refptr<Histogram> render_histogram(NULL);
212
213  if (histogram_type == HISTOGRAM) {
214    render_histogram = Histogram::FactoryGet(
215        histogram_name, declared_min, declared_max, bucket_count, flags);
216  } else if (histogram_type == LINEAR_HISTOGRAM) {
217    render_histogram = LinearHistogram::FactoryGet(
218        histogram_name, declared_min, declared_max, bucket_count, flags);
219  } else if (histogram_type == BOOLEAN_HISTOGRAM) {
220    render_histogram = BooleanHistogram::FactoryGet(histogram_name, flags);
221  } else {
222    LOG(ERROR) << "Error Deserializing Histogram Unknown histogram_type: "
223               << histogram_type;
224    return false;
225  }
226
227  DCHECK_EQ(render_histogram->declared_min(), declared_min);
228  DCHECK_EQ(render_histogram->declared_max(), declared_max);
229  DCHECK_EQ(render_histogram->bucket_count(), bucket_count);
230  DCHECK_EQ(render_histogram->range_checksum(), range_checksum);
231  DCHECK_EQ(render_histogram->histogram_type(), histogram_type);
232
233  if (render_histogram->flags() & kIPCSerializationSourceFlag) {
234    DVLOG(1) << "Single process mode, histogram observed and not copied: "
235             << histogram_name;
236  } else {
237    DCHECK_EQ(flags & render_histogram->flags(), flags);
238    render_histogram->AddSampleSet(sample);
239  }
240
241  return true;
242}
243
244//------------------------------------------------------------------------------
245// Methods for the validating a sample and a related histogram.
246//------------------------------------------------------------------------------
247
248Histogram::Inconsistencies Histogram::FindCorruption(
249    const SampleSet& snapshot) const {
250  int inconsistencies = NO_INCONSISTENCIES;
251  Sample previous_range = -1;  // Bottom range is always 0.
252  Sample checksum = 0;
253  int64 count = 0;
254  for (size_t index = 0; index < bucket_count(); ++index) {
255    count += snapshot.counts(index);
256    int new_range = ranges(index);
257    checksum += new_range;
258    if (previous_range >= new_range)
259      inconsistencies |= BUCKET_ORDER_ERROR;
260    previous_range = new_range;
261  }
262
263  if (checksum != range_checksum_)
264    inconsistencies |= RANGE_CHECKSUM_ERROR;
265
266  int64 delta64 = snapshot.redundant_count() - count;
267  if (delta64 != 0) {
268    int delta = static_cast<int>(delta64);
269    if (delta != delta64)
270      delta = INT_MAX;  // Flag all giant errors as INT_MAX.
271    // Since snapshots of histograms are taken asynchronously relative to
272    // sampling (and snapped from different threads), it is pretty likely that
273    // we'll catch a redundant count that doesn't match the sample count.  We
274    // allow for a certain amount of slop before flagging this as an
275    // inconsistency.  Even with an inconsistency, we'll snapshot it again (for
276    // UMA in about a half hour, so we'll eventually get the data, if it was
277    // not the result of a corruption.  If histograms show that 1 is "too tight"
278    // then we may try to use 2 or 3 for this slop value.
279    const int kCommonRaceBasedCountMismatch = 1;
280    if (delta > 0) {
281      UMA_HISTOGRAM_COUNTS("Histogram.InconsistentCountHigh", delta);
282      if (delta > kCommonRaceBasedCountMismatch)
283        inconsistencies |= COUNT_HIGH_ERROR;
284    } else {
285      DCHECK_GT(0, delta);
286      UMA_HISTOGRAM_COUNTS("Histogram.InconsistentCountLow", -delta);
287      if (-delta > kCommonRaceBasedCountMismatch)
288        inconsistencies |= COUNT_LOW_ERROR;
289    }
290  }
291  return static_cast<Inconsistencies>(inconsistencies);
292}
293
294Histogram::ClassType Histogram::histogram_type() const {
295  return HISTOGRAM;
296}
297
298Histogram::Sample Histogram::ranges(size_t i) const {
299  return ranges_[i];
300}
301
302size_t Histogram::bucket_count() const {
303  return bucket_count_;
304}
305
306// Do a safe atomic snapshot of sample data.
307// This implementation assumes we are on a safe single thread.
308void Histogram::SnapshotSample(SampleSet* sample) const {
309  // Note locking not done in this version!!!
310  *sample = sample_;
311}
312
313bool Histogram::HasConstructorArguments(Sample minimum,
314                                        Sample maximum,
315                                        size_t bucket_count) {
316  return ((minimum == declared_min_) && (maximum == declared_max_) &&
317          (bucket_count == bucket_count_));
318}
319
320bool Histogram::HasConstructorTimeDeltaArguments(TimeDelta minimum,
321                                                 TimeDelta maximum,
322                                                 size_t bucket_count) {
323  return ((minimum.InMilliseconds() == declared_min_) &&
324          (maximum.InMilliseconds() == declared_max_) &&
325          (bucket_count == bucket_count_));
326}
327
328Histogram::Histogram(const std::string& name, Sample minimum,
329                     Sample maximum, size_t bucket_count)
330  : histogram_name_(name),
331    declared_min_(minimum),
332    declared_max_(maximum),
333    bucket_count_(bucket_count),
334    flags_(kNoFlags),
335    ranges_(bucket_count + 1, 0),
336    range_checksum_(0),
337    sample_() {
338  Initialize();
339}
340
341Histogram::Histogram(const std::string& name, TimeDelta minimum,
342                     TimeDelta maximum, size_t bucket_count)
343  : histogram_name_(name),
344    declared_min_(static_cast<int> (minimum.InMilliseconds())),
345    declared_max_(static_cast<int> (maximum.InMilliseconds())),
346    bucket_count_(bucket_count),
347    flags_(kNoFlags),
348    ranges_(bucket_count + 1, 0),
349    range_checksum_(0),
350    sample_() {
351  Initialize();
352}
353
354Histogram::~Histogram() {
355  if (StatisticsRecorder::dump_on_exit()) {
356    std::string output;
357    WriteAscii(true, "\n", &output);
358    LOG(INFO) << output;
359  }
360
361  // Just to make sure most derived class did this properly...
362  DCHECK(ValidateBucketRanges());
363  DCHECK(HasValidRangeChecksum());
364}
365
366bool Histogram::PrintEmptyBucket(size_t index) const {
367  return true;
368}
369
370// Calculate what range of values are held in each bucket.
371// We have to be careful that we don't pick a ratio between starting points in
372// consecutive buckets that is sooo small, that the integer bounds are the same
373// (effectively making one bucket get no values).  We need to avoid:
374//   ranges_[i] == ranges_[i + 1]
375// To avoid that, we just do a fine-grained bucket width as far as we need to
376// until we get a ratio that moves us along at least 2 units at a time.  From
377// that bucket onward we do use the exponential growth of buckets.
378void Histogram::InitializeBucketRange() {
379  double log_max = log(static_cast<double>(declared_max()));
380  double log_ratio;
381  double log_next;
382  size_t bucket_index = 1;
383  Sample current = declared_min();
384  SetBucketRange(bucket_index, current);
385  while (bucket_count() > ++bucket_index) {
386    double log_current;
387    log_current = log(static_cast<double>(current));
388    // Calculate the count'th root of the range.
389    log_ratio = (log_max - log_current) / (bucket_count() - bucket_index);
390    // See where the next bucket would start.
391    log_next = log_current + log_ratio;
392    int next;
393    next = static_cast<int>(floor(exp(log_next) + 0.5));
394    if (next > current)
395      current = next;
396    else
397      ++current;  // Just do a narrow bucket, and keep trying.
398    SetBucketRange(bucket_index, current);
399  }
400  ResetRangeChecksum();
401
402  DCHECK_EQ(bucket_count(), bucket_index);
403}
404
405size_t Histogram::BucketIndex(Sample value) const {
406  // Use simple binary search.  This is very general, but there are better
407  // approaches if we knew that the buckets were linearly distributed.
408  DCHECK_LE(ranges(0), value);
409  DCHECK_GT(ranges(bucket_count()), value);
410  size_t under = 0;
411  size_t over = bucket_count();
412  size_t mid;
413
414  do {
415    DCHECK_GE(over, under);
416    mid = (over + under)/2;
417    if (mid == under)
418      break;
419    if (ranges(mid) <= value)
420      under = mid;
421    else
422      over = mid;
423  } while (true);
424
425  DCHECK_LE(ranges(mid), value);
426  DCHECK_GT(ranges(mid+1), value);
427  return mid;
428}
429
430// Use the actual bucket widths (like a linear histogram) until the widths get
431// over some transition value, and then use that transition width.  Exponentials
432// get so big so fast (and we don't expect to see a lot of entries in the large
433// buckets), so we need this to make it possible to see what is going on and
434// not have 0-graphical-height buckets.
435double Histogram::GetBucketSize(Count current, size_t i) const {
436  DCHECK_GT(ranges(i + 1), ranges(i));
437  static const double kTransitionWidth = 5;
438  double denominator = ranges(i + 1) - ranges(i);
439  if (denominator > kTransitionWidth)
440    denominator = kTransitionWidth;  // Stop trying to normalize.
441  return current/denominator;
442}
443
444void Histogram::ResetRangeChecksum() {
445  range_checksum_ = CalculateRangeChecksum();
446}
447
448const std::string Histogram::GetAsciiBucketRange(size_t i) const {
449  std::string result;
450  if (kHexRangePrintingFlag & flags_)
451    StringAppendF(&result, "%#x", ranges(i));
452  else
453    StringAppendF(&result, "%d", ranges(i));
454  return result;
455}
456
457// Update histogram data with new sample.
458void Histogram::Accumulate(Sample value, Count count, size_t index) {
459  // Note locking not done in this version!!!
460  sample_.Accumulate(value, count, index);
461}
462
463void Histogram::SetBucketRange(size_t i, Sample value) {
464  DCHECK_GT(bucket_count_, i);
465  ranges_[i] = value;
466}
467
468bool Histogram::ValidateBucketRanges() const {
469  // Standard assertions that all bucket ranges should satisfy.
470  DCHECK_EQ(bucket_count_ + 1, ranges_.size());
471  DCHECK_EQ(0, ranges_[0]);
472  DCHECK_EQ(declared_min(), ranges_[1]);
473  DCHECK_EQ(declared_max(), ranges_[bucket_count_ - 1]);
474  DCHECK_EQ(kSampleType_MAX, ranges_[bucket_count_]);
475  return true;
476}
477
478void Histogram::Initialize() {
479  sample_.Resize(*this);
480  if (declared_min_ < 1)
481    declared_min_ = 1;
482  if (declared_max_ > kSampleType_MAX - 1)
483    declared_max_ = kSampleType_MAX - 1;
484  DCHECK_LE(declared_min_, declared_max_);
485  DCHECK_GT(bucket_count_, 1u);
486  size_t maximal_bucket_count = declared_max_ - declared_min_ + 2;
487  DCHECK_LE(bucket_count_, maximal_bucket_count);
488  DCHECK_EQ(0, ranges_[0]);
489  ranges_[bucket_count_] = kSampleType_MAX;
490  InitializeBucketRange();
491  DCHECK(ValidateBucketRanges());
492  StatisticsRecorder::Register(this);
493}
494
495bool Histogram::HasValidRangeChecksum() const {
496  return CalculateRangeChecksum() == range_checksum_;
497}
498
499Histogram::Sample Histogram::CalculateRangeChecksum() const {
500  DCHECK_EQ(ranges_.size(), bucket_count() + 1);
501  Sample checksum = 0;
502  for (size_t index = 0; index < bucket_count(); ++index) {
503    checksum += ranges(index);
504  }
505  return checksum;
506}
507
508//------------------------------------------------------------------------------
509// Private methods
510
511double Histogram::GetPeakBucketSize(const SampleSet& snapshot) const {
512  double max = 0;
513  for (size_t i = 0; i < bucket_count() ; ++i) {
514    double current_size = GetBucketSize(snapshot.counts(i), i);
515    if (current_size > max)
516      max = current_size;
517  }
518  return max;
519}
520
521void Histogram::WriteAsciiHeader(const SampleSet& snapshot,
522                                 Count sample_count,
523                                 std::string* output) const {
524  StringAppendF(output,
525                "Histogram: %s recorded %d samples",
526                histogram_name().c_str(),
527                sample_count);
528  if (0 == sample_count) {
529    DCHECK_EQ(snapshot.sum(), 0);
530  } else {
531    double average = static_cast<float>(snapshot.sum()) / sample_count;
532    double variance = static_cast<float>(snapshot.square_sum())/sample_count
533                      - average * average;
534    double standard_deviation = sqrt(variance);
535
536    StringAppendF(output,
537                  ", average = %.1f, standard deviation = %.1f",
538                  average, standard_deviation);
539  }
540  if (flags_ & ~kHexRangePrintingFlag)
541    StringAppendF(output, " (flags = 0x%x)", flags_ & ~kHexRangePrintingFlag);
542}
543
544void Histogram::WriteAsciiBucketContext(const int64 past,
545                                        const Count current,
546                                        const int64 remaining,
547                                        const size_t i,
548                                        std::string* output) const {
549  double scaled_sum = (past + current + remaining) / 100.0;
550  WriteAsciiBucketValue(current, scaled_sum, output);
551  if (0 < i) {
552    double percentage = past / scaled_sum;
553    StringAppendF(output, " {%3.1f%%}", percentage);
554  }
555}
556
557void Histogram::WriteAsciiBucketValue(Count current, double scaled_sum,
558                                      std::string* output) const {
559  StringAppendF(output, " (%d = %3.1f%%)", current, current/scaled_sum);
560}
561
562void Histogram::WriteAsciiBucketGraph(double current_size, double max_size,
563                                      std::string* output) const {
564  const int k_line_length = 72;  // Maximal horizontal width of graph.
565  int x_count = static_cast<int>(k_line_length * (current_size / max_size)
566                                 + 0.5);
567  int x_remainder = k_line_length - x_count;
568
569  while (0 < x_count--)
570    output->append("-");
571  output->append("O");
572  while (0 < x_remainder--)
573    output->append(" ");
574}
575
576//------------------------------------------------------------------------------
577// Methods for the Histogram::SampleSet class
578//------------------------------------------------------------------------------
579
580Histogram::SampleSet::SampleSet()
581    : counts_(),
582      sum_(0),
583      square_sum_(0),
584      redundant_count_(0) {
585}
586
587Histogram::SampleSet::~SampleSet() {
588}
589
590void Histogram::SampleSet::Resize(const Histogram& histogram) {
591  counts_.resize(histogram.bucket_count(), 0);
592}
593
594void Histogram::SampleSet::CheckSize(const Histogram& histogram) const {
595  DCHECK_EQ(histogram.bucket_count(), counts_.size());
596}
597
598
599void Histogram::SampleSet::Accumulate(Sample value,  Count count,
600                                      size_t index) {
601  DCHECK(count == 1 || count == -1);
602  counts_[index] += count;
603  sum_ += count * value;
604  square_sum_ += (count * value) * static_cast<int64>(value);
605  redundant_count_ += count;
606  DCHECK_GE(counts_[index], 0);
607  DCHECK_GE(sum_, 0);
608  DCHECK_GE(square_sum_, 0);
609  DCHECK_GE(redundant_count_, 0);
610}
611
612Count Histogram::SampleSet::TotalCount() const {
613  Count total = 0;
614  for (Counts::const_iterator it = counts_.begin();
615       it != counts_.end();
616       ++it) {
617    total += *it;
618  }
619  return total;
620}
621
622void Histogram::SampleSet::Add(const SampleSet& other) {
623  DCHECK_EQ(counts_.size(), other.counts_.size());
624  sum_ += other.sum_;
625  square_sum_ += other.square_sum_;
626  redundant_count_ += other.redundant_count_;
627  for (size_t index = 0; index < counts_.size(); ++index)
628    counts_[index] += other.counts_[index];
629}
630
631void Histogram::SampleSet::Subtract(const SampleSet& other) {
632  DCHECK_EQ(counts_.size(), other.counts_.size());
633  // Note: Race conditions in snapshotting a sum or square_sum may lead to
634  // (temporary) negative values when snapshots are later combined (and deltas
635  // calculated).  As a result, we don't currently CHCEK() for positive values.
636  sum_ -= other.sum_;
637  square_sum_ -= other.square_sum_;
638  redundant_count_ -= other.redundant_count_;
639  for (size_t index = 0; index < counts_.size(); ++index) {
640    counts_[index] -= other.counts_[index];
641    DCHECK_GE(counts_[index], 0);
642  }
643}
644
645bool Histogram::SampleSet::Serialize(Pickle* pickle) const {
646  pickle->WriteInt64(sum_);
647  pickle->WriteInt64(square_sum_);
648  pickle->WriteInt64(redundant_count_);
649  pickle->WriteSize(counts_.size());
650
651  for (size_t index = 0; index < counts_.size(); ++index) {
652    pickle->WriteInt(counts_[index]);
653  }
654
655  return true;
656}
657
658bool Histogram::SampleSet::Deserialize(void** iter, const Pickle& pickle) {
659  DCHECK_EQ(counts_.size(), 0u);
660  DCHECK_EQ(sum_, 0);
661  DCHECK_EQ(square_sum_, 0);
662  DCHECK_EQ(redundant_count_, 0);
663
664  size_t counts_size;
665
666  if (!pickle.ReadInt64(iter, &sum_) ||
667      !pickle.ReadInt64(iter, &square_sum_) ||
668      !pickle.ReadInt64(iter, &redundant_count_) ||
669      !pickle.ReadSize(iter, &counts_size)) {
670    return false;
671  }
672
673  if (counts_size == 0)
674    return false;
675
676  int count = 0;
677  for (size_t index = 0; index < counts_size; ++index) {
678    int i;
679    if (!pickle.ReadInt(iter, &i))
680      return false;
681    counts_.push_back(i);
682    count += i;
683  }
684  DCHECK_EQ(count, redundant_count_);
685  return count == redundant_count_;
686}
687
688//------------------------------------------------------------------------------
689// LinearHistogram: This histogram uses a traditional set of evenly spaced
690// buckets.
691//------------------------------------------------------------------------------
692
693LinearHistogram::~LinearHistogram() {
694}
695
696scoped_refptr<Histogram> LinearHistogram::FactoryGet(const std::string& name,
697                                                     Sample minimum,
698                                                     Sample maximum,
699                                                     size_t bucket_count,
700                                                     Flags flags) {
701  scoped_refptr<Histogram> histogram(NULL);
702
703  if (minimum < 1)
704    minimum = 1;
705  if (maximum > kSampleType_MAX - 1)
706    maximum = kSampleType_MAX - 1;
707
708  if (!StatisticsRecorder::FindHistogram(name, &histogram)) {
709    histogram = new LinearHistogram(name, minimum, maximum, bucket_count);
710    StatisticsRecorder::FindHistogram(name, &histogram);
711  }
712
713  DCHECK_EQ(LINEAR_HISTOGRAM, histogram->histogram_type());
714  DCHECK(histogram->HasConstructorArguments(minimum, maximum, bucket_count));
715  histogram->SetFlags(flags);
716  return histogram;
717}
718
719scoped_refptr<Histogram> LinearHistogram::FactoryTimeGet(
720    const std::string& name,
721    TimeDelta minimum,
722    TimeDelta maximum,
723    size_t bucket_count,
724    Flags flags) {
725  return FactoryGet(name, minimum.InMilliseconds(), maximum.InMilliseconds(),
726                    bucket_count, flags);
727}
728
729Histogram::ClassType LinearHistogram::histogram_type() const {
730  return LINEAR_HISTOGRAM;
731}
732
733void LinearHistogram::SetRangeDescriptions(
734    const DescriptionPair descriptions[]) {
735  for (int i =0; descriptions[i].description; ++i) {
736    bucket_description_[descriptions[i].sample] = descriptions[i].description;
737  }
738}
739
740LinearHistogram::LinearHistogram(const std::string& name,
741                                 Sample minimum,
742                                 Sample maximum,
743                                 size_t bucket_count)
744    : Histogram(name, minimum >= 1 ? minimum : 1, maximum, bucket_count) {
745  InitializeBucketRange();
746  DCHECK(ValidateBucketRanges());
747}
748
749LinearHistogram::LinearHistogram(const std::string& name,
750                                 TimeDelta minimum,
751                                 TimeDelta maximum,
752                                 size_t bucket_count)
753    : Histogram(name, minimum >= TimeDelta::FromMilliseconds(1) ?
754                                 minimum : TimeDelta::FromMilliseconds(1),
755                maximum, bucket_count) {
756  // Do a "better" (different) job at init than a base classes did...
757  InitializeBucketRange();
758  DCHECK(ValidateBucketRanges());
759}
760
761void LinearHistogram::InitializeBucketRange() {
762  DCHECK_GT(declared_min(), 0);  // 0 is the underflow bucket here.
763  double min = declared_min();
764  double max = declared_max();
765  size_t i;
766  for (i = 1; i < bucket_count(); ++i) {
767    double linear_range = (min * (bucket_count() -1 - i) + max * (i - 1)) /
768                          (bucket_count() - 2);
769    SetBucketRange(i, static_cast<int> (linear_range + 0.5));
770  }
771  ResetRangeChecksum();
772}
773
774double LinearHistogram::GetBucketSize(Count current, size_t i) const {
775  DCHECK_GT(ranges(i + 1), ranges(i));
776  // Adjacent buckets with different widths would have "surprisingly" many (few)
777  // samples in a histogram if we didn't normalize this way.
778  double denominator = ranges(i + 1) - ranges(i);
779  return current/denominator;
780}
781
782const std::string LinearHistogram::GetAsciiBucketRange(size_t i) const {
783  int range = ranges(i);
784  BucketDescriptionMap::const_iterator it = bucket_description_.find(range);
785  if (it == bucket_description_.end())
786    return Histogram::GetAsciiBucketRange(i);
787  return it->second;
788}
789
790bool LinearHistogram::PrintEmptyBucket(size_t index) const {
791  return bucket_description_.find(ranges(index)) == bucket_description_.end();
792}
793
794
795//------------------------------------------------------------------------------
796// This section provides implementation for BooleanHistogram.
797//------------------------------------------------------------------------------
798
799scoped_refptr<Histogram> BooleanHistogram::FactoryGet(const std::string& name,
800                                                      Flags flags) {
801  scoped_refptr<Histogram> histogram(NULL);
802
803  if (!StatisticsRecorder::FindHistogram(name, &histogram)) {
804    histogram = new BooleanHistogram(name);
805    StatisticsRecorder::FindHistogram(name, &histogram);
806  }
807
808  DCHECK_EQ(BOOLEAN_HISTOGRAM, histogram->histogram_type());
809  histogram->SetFlags(flags);
810  return histogram;
811}
812
813Histogram::ClassType BooleanHistogram::histogram_type() const {
814  return BOOLEAN_HISTOGRAM;
815}
816
817void BooleanHistogram::AddBoolean(bool value) {
818  Add(value ? 1 : 0);
819}
820
821BooleanHistogram::BooleanHistogram(const std::string& name)
822    : LinearHistogram(name, 1, 2, 3) {
823}
824
825//------------------------------------------------------------------------------
826// CustomHistogram:
827//------------------------------------------------------------------------------
828
829scoped_refptr<Histogram> CustomHistogram::FactoryGet(
830    const std::string& name,
831    const std::vector<Sample>& custom_ranges,
832    Flags flags) {
833  scoped_refptr<Histogram> histogram(NULL);
834
835  // Remove the duplicates in the custom ranges array.
836  std::vector<int> ranges = custom_ranges;
837  ranges.push_back(0);  // Ensure we have a zero value.
838  std::sort(ranges.begin(), ranges.end());
839  ranges.erase(std::unique(ranges.begin(), ranges.end()), ranges.end());
840  if (ranges.size() <= 1) {
841    DCHECK(false);
842    // Note that we pushed a 0 in above, so for defensive code....
843    ranges.push_back(1);  // Put in some data so we can index to [1].
844  }
845
846  DCHECK_LT(ranges.back(), kSampleType_MAX);
847
848  if (!StatisticsRecorder::FindHistogram(name, &histogram)) {
849    histogram = new CustomHistogram(name, ranges);
850    StatisticsRecorder::FindHistogram(name, &histogram);
851  }
852
853  DCHECK_EQ(histogram->histogram_type(), CUSTOM_HISTOGRAM);
854  DCHECK(histogram->HasConstructorArguments(ranges[1], ranges.back(),
855                                            ranges.size()));
856  histogram->SetFlags(flags);
857  return histogram;
858}
859
860Histogram::ClassType CustomHistogram::histogram_type() const {
861  return CUSTOM_HISTOGRAM;
862}
863
864CustomHistogram::CustomHistogram(const std::string& name,
865                                 const std::vector<Sample>& custom_ranges)
866    : Histogram(name, custom_ranges[1], custom_ranges.back(),
867                custom_ranges.size()) {
868  DCHECK_GT(custom_ranges.size(), 1u);
869  DCHECK_EQ(custom_ranges[0], 0);
870  ranges_vector_ = &custom_ranges;
871  InitializeBucketRange();
872  ranges_vector_ = NULL;
873  DCHECK(ValidateBucketRanges());
874}
875
876void CustomHistogram::InitializeBucketRange() {
877  DCHECK_LE(ranges_vector_->size(), bucket_count());
878  for (size_t index = 0; index < ranges_vector_->size(); ++index)
879    SetBucketRange(index, (*ranges_vector_)[index]);
880  ResetRangeChecksum();
881}
882
883double CustomHistogram::GetBucketSize(Count current, size_t i) const {
884  return 1;
885}
886
887//------------------------------------------------------------------------------
888// The next section handles global (central) support for all histograms, as well
889// as startup/teardown of this service.
890//------------------------------------------------------------------------------
891
892// This singleton instance should be started during the single threaded portion
893// of main(), and hence it is not thread safe.  It initializes globals to
894// provide support for all future calls.
895StatisticsRecorder::StatisticsRecorder() {
896  DCHECK(!histograms_);
897  if (lock_ == NULL) {
898    // This will leak on purpose. It's the only way to make sure we won't race
899    // against the static uninitialization of the module while one of our
900    // static methods relying on the lock get called at an inappropriate time
901    // during the termination phase. Since it's a static data member, we will
902    // leak one per process, which would be similar to the instance allocated
903    // during static initialization and released only on  process termination.
904    lock_ = new base::Lock;
905  }
906  base::AutoLock auto_lock(*lock_);
907  histograms_ = new HistogramMap;
908}
909
910StatisticsRecorder::~StatisticsRecorder() {
911  DCHECK(histograms_ && lock_);
912
913  if (dump_on_exit_) {
914    std::string output;
915    WriteGraph("", &output);
916    LOG(INFO) << output;
917  }
918  // Clean up.
919  HistogramMap* histograms = NULL;
920  {
921    base::AutoLock auto_lock(*lock_);
922    histograms = histograms_;
923    histograms_ = NULL;
924  }
925  delete histograms;
926  // We don't delete lock_ on purpose to avoid having to properly protect
927  // against it going away after we checked for NULL in the static methods.
928}
929
930// static
931bool StatisticsRecorder::IsActive() {
932  if (lock_ == NULL)
933    return false;
934  base::AutoLock auto_lock(*lock_);
935  return NULL != histograms_;
936}
937
938// Note: We can't accept a ref_ptr to |histogram| because we *might* not keep a
939// reference, and we are called while in the Histogram constructor. In that
940// scenario, a ref_ptr would have incremented the ref count when the histogram
941// was passed to us, decremented it when we returned, and the instance would be
942// destroyed before assignment (when value was returned by new).
943// static
944void StatisticsRecorder::Register(Histogram* histogram) {
945  if (lock_ == NULL)
946    return;
947  base::AutoLock auto_lock(*lock_);
948  if (!histograms_)
949    return;
950  const std::string name = histogram->histogram_name();
951  // Avoid overwriting a previous registration.
952  if (histograms_->end() == histograms_->find(name))
953    (*histograms_)[name] = histogram;
954}
955
956// static
957void StatisticsRecorder::WriteHTMLGraph(const std::string& query,
958                                        std::string* output) {
959  if (!IsActive())
960    return;
961  output->append("<html><head><title>About Histograms");
962  if (!query.empty())
963    output->append(" - " + query);
964  output->append("</title>"
965                 // We'd like the following no-cache... but it doesn't work.
966                 // "<META HTTP-EQUIV=\"Pragma\" CONTENT=\"no-cache\">"
967                 "</head><body>");
968
969  Histograms snapshot;
970  GetSnapshot(query, &snapshot);
971  for (Histograms::iterator it = snapshot.begin();
972       it != snapshot.end();
973       ++it) {
974    (*it)->WriteHTMLGraph(output);
975    output->append("<br><hr><br>");
976  }
977  output->append("</body></html>");
978}
979
980// static
981void StatisticsRecorder::WriteGraph(const std::string& query,
982                                    std::string* output) {
983  if (!IsActive())
984    return;
985  if (query.length())
986    StringAppendF(output, "Collections of histograms for %s\n", query.c_str());
987  else
988    output->append("Collections of all histograms\n");
989
990  Histograms snapshot;
991  GetSnapshot(query, &snapshot);
992  for (Histograms::iterator it = snapshot.begin();
993       it != snapshot.end();
994       ++it) {
995    (*it)->WriteAscii(true, "\n", output);
996    output->append("\n");
997  }
998}
999
1000// static
1001void StatisticsRecorder::GetHistograms(Histograms* output) {
1002  if (lock_ == NULL)
1003    return;
1004  base::AutoLock auto_lock(*lock_);
1005  if (!histograms_)
1006    return;
1007  for (HistogramMap::iterator it = histograms_->begin();
1008       histograms_->end() != it;
1009       ++it) {
1010    DCHECK_EQ(it->first, it->second->histogram_name());
1011    output->push_back(it->second);
1012  }
1013}
1014
1015bool StatisticsRecorder::FindHistogram(const std::string& name,
1016                                       scoped_refptr<Histogram>* histogram) {
1017  if (lock_ == NULL)
1018    return false;
1019  base::AutoLock auto_lock(*lock_);
1020  if (!histograms_)
1021    return false;
1022  HistogramMap::iterator it = histograms_->find(name);
1023  if (histograms_->end() == it)
1024    return false;
1025  *histogram = it->second;
1026  return true;
1027}
1028
1029// private static
1030void StatisticsRecorder::GetSnapshot(const std::string& query,
1031                                     Histograms* snapshot) {
1032  if (lock_ == NULL)
1033    return;
1034  base::AutoLock auto_lock(*lock_);
1035  if (!histograms_)
1036    return;
1037  for (HistogramMap::iterator it = histograms_->begin();
1038       histograms_->end() != it;
1039       ++it) {
1040    if (it->first.find(query) != std::string::npos)
1041      snapshot->push_back(it->second);
1042  }
1043}
1044
1045// static
1046StatisticsRecorder::HistogramMap* StatisticsRecorder::histograms_ = NULL;
1047// static
1048base::Lock* StatisticsRecorder::lock_ = NULL;
1049// static
1050bool StatisticsRecorder::dump_on_exit_ = false;
1051
1052}  // namespace base
1053