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