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