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