1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // Histogram is an object that aggregates statistics, and can summarize them in 6 // various forms, including ASCII graphical, HTML, and numerically (as a 7 // vector of numbers corresponding to each of the aggregating buckets). 8 // See header file for details and examples. 9 10 #include "base/metrics/histogram.h" 11 12 #include <limits.h> 13 #include <math.h> 14 15 #include <algorithm> 16 #include <string> 17 18 #include "base/compiler_specific.h" 19 #include "base/debug/alias.h" 20 #include "base/logging.h" 21 #include "base/memory/ptr_util.h" 22 #include "base/metrics/histogram_macros.h" 23 #include "base/metrics/metrics_hashes.h" 24 #include "base/metrics/persistent_histogram_allocator.h" 25 #include "base/metrics/persistent_memory_allocator.h" 26 #include "base/metrics/sample_vector.h" 27 #include "base/metrics/statistics_recorder.h" 28 #include "base/pickle.h" 29 #include "base/strings/string_util.h" 30 #include "base/strings/stringprintf.h" 31 #include "base/synchronization/lock.h" 32 #include "base/values.h" 33 34 namespace base { 35 36 namespace { 37 38 bool ReadHistogramArguments(PickleIterator* iter, 39 std::string* histogram_name, 40 int* flags, 41 int* declared_min, 42 int* declared_max, 43 uint32_t* bucket_count, 44 uint32_t* range_checksum) { 45 if (!iter->ReadString(histogram_name) || 46 !iter->ReadInt(flags) || 47 !iter->ReadInt(declared_min) || 48 !iter->ReadInt(declared_max) || 49 !iter->ReadUInt32(bucket_count) || 50 !iter->ReadUInt32(range_checksum)) { 51 DLOG(ERROR) << "Pickle error decoding Histogram: " << *histogram_name; 52 return false; 53 } 54 55 // Since these fields may have come from an untrusted renderer, do additional 56 // checks above and beyond those in Histogram::Initialize() 57 if (*declared_max <= 0 || 58 *declared_min <= 0 || 59 *declared_max < *declared_min || 60 INT_MAX / sizeof(HistogramBase::Count) <= *bucket_count || 61 *bucket_count < 2) { 62 DLOG(ERROR) << "Values error decoding Histogram: " << histogram_name; 63 return false; 64 } 65 66 // We use the arguments to find or create the local version of the histogram 67 // in this process, so we need to clear any IPC flag. 68 *flags &= ~HistogramBase::kIPCSerializationSourceFlag; 69 70 return true; 71 } 72 73 bool ValidateRangeChecksum(const HistogramBase& histogram, 74 uint32_t range_checksum) { 75 const Histogram& casted_histogram = 76 static_cast<const Histogram&>(histogram); 77 78 return casted_histogram.bucket_ranges()->checksum() == range_checksum; 79 } 80 81 } // namespace 82 83 typedef HistogramBase::Count Count; 84 typedef HistogramBase::Sample Sample; 85 86 // static 87 const uint32_t Histogram::kBucketCount_MAX = 16384u; 88 89 class Histogram::Factory { 90 public: 91 Factory(const std::string& name, 92 HistogramBase::Sample minimum, 93 HistogramBase::Sample maximum, 94 uint32_t bucket_count, 95 int32_t flags) 96 : Factory(name, HISTOGRAM, minimum, maximum, bucket_count, flags) {} 97 virtual ~Factory() = default; 98 99 // Create histogram based on construction parameters. Caller takes 100 // ownership of the returned object. 101 HistogramBase* Build(); 102 103 protected: 104 Factory(const std::string& name, 105 HistogramType histogram_type, 106 HistogramBase::Sample minimum, 107 HistogramBase::Sample maximum, 108 uint32_t bucket_count, 109 int32_t flags) 110 : name_(name), 111 histogram_type_(histogram_type), 112 minimum_(minimum), 113 maximum_(maximum), 114 bucket_count_(bucket_count), 115 flags_(flags) {} 116 117 // Create a BucketRanges structure appropriate for this histogram. 118 virtual BucketRanges* CreateRanges() { 119 BucketRanges* ranges = new BucketRanges(bucket_count_ + 1); 120 Histogram::InitializeBucketRanges(minimum_, maximum_, ranges); 121 return ranges; 122 } 123 124 // Allocate the correct Histogram object off the heap (in case persistent 125 // memory is not available). 126 virtual std::unique_ptr<HistogramBase> HeapAlloc(const BucketRanges* ranges) { 127 return WrapUnique(new Histogram(name_, minimum_, maximum_, ranges)); 128 } 129 130 // Perform any required datafill on the just-created histogram. If 131 // overridden, be sure to call the "super" version -- this method may not 132 // always remain empty. 133 virtual void FillHistogram(HistogramBase* /*histogram*/) {} 134 135 // These values are protected (instead of private) because they need to 136 // be accessible to methods of sub-classes in order to avoid passing 137 // unnecessary parameters everywhere. 138 const std::string& name_; 139 const HistogramType histogram_type_; 140 HistogramBase::Sample minimum_; 141 HistogramBase::Sample maximum_; 142 uint32_t bucket_count_; 143 int32_t flags_; 144 145 private: 146 DISALLOW_COPY_AND_ASSIGN(Factory); 147 }; 148 149 HistogramBase* Histogram::Factory::Build() { 150 HistogramBase* histogram = StatisticsRecorder::FindHistogram(name_); 151 if (!histogram) { 152 // To avoid racy destruction at shutdown, the following will be leaked. 153 const BucketRanges* created_ranges = CreateRanges(); 154 const BucketRanges* registered_ranges = 155 StatisticsRecorder::RegisterOrDeleteDuplicateRanges(created_ranges); 156 157 // In most cases, the bucket-count, minimum, and maximum values are known 158 // when the code is written and so are passed in explicitly. In other 159 // cases (such as with a CustomHistogram), they are calculated dynamically 160 // at run-time. In the latter case, those ctor parameters are zero and 161 // the results extracted from the result of CreateRanges(). 162 if (bucket_count_ == 0) { 163 bucket_count_ = static_cast<uint32_t>(registered_ranges->bucket_count()); 164 minimum_ = registered_ranges->range(1); 165 maximum_ = registered_ranges->range(bucket_count_ - 1); 166 } 167 168 // Try to create the histogram using a "persistent" allocator. As of 169 // 2016-02-25, the availability of such is controlled by a base::Feature 170 // that is off by default. If the allocator doesn't exist or if 171 // allocating from it fails, code below will allocate the histogram from 172 // the process heap. 173 PersistentHistogramAllocator::Reference histogram_ref = 0; 174 std::unique_ptr<HistogramBase> tentative_histogram; 175 PersistentHistogramAllocator* allocator = GlobalHistogramAllocator::Get(); 176 if (allocator) { 177 tentative_histogram = allocator->AllocateHistogram( 178 histogram_type_, 179 name_, 180 minimum_, 181 maximum_, 182 registered_ranges, 183 flags_, 184 &histogram_ref); 185 } 186 187 // Handle the case where no persistent allocator is present or the 188 // persistent allocation fails (perhaps because it is full). 189 if (!tentative_histogram) { 190 DCHECK(!histogram_ref); // Should never have been set. 191 DCHECK(!allocator); // Shouldn't have failed. 192 flags_ &= ~HistogramBase::kIsPersistent; 193 tentative_histogram = HeapAlloc(registered_ranges); 194 tentative_histogram->SetFlags(flags_); 195 } 196 197 FillHistogram(tentative_histogram.get()); 198 199 // Register this histogram with the StatisticsRecorder. Keep a copy of 200 // the pointer value to tell later whether the locally created histogram 201 // was registered or deleted. The type is "void" because it could point 202 // to released memory after the following line. 203 const void* tentative_histogram_ptr = tentative_histogram.get(); 204 histogram = StatisticsRecorder::RegisterOrDeleteDuplicate( 205 tentative_histogram.release()); 206 207 // Persistent histograms need some follow-up processing. 208 if (histogram_ref) { 209 allocator->FinalizeHistogram(histogram_ref, 210 histogram == tentative_histogram_ptr); 211 } 212 213 // Update report on created histograms. 214 ReportHistogramActivity(*histogram, HISTOGRAM_CREATED); 215 } else { 216 // Update report on lookup histograms. 217 ReportHistogramActivity(*histogram, HISTOGRAM_LOOKUP); 218 } 219 220 DCHECK_EQ(histogram_type_, histogram->GetHistogramType()) << name_; 221 if (bucket_count_ != 0 && 222 !histogram->HasConstructionArguments(minimum_, maximum_, bucket_count_)) { 223 // The construction arguments do not match the existing histogram. This can 224 // come about if an extension updates in the middle of a chrome run and has 225 // changed one of them, or simply by bad code within Chrome itself. We 226 // return NULL here with the expectation that bad code in Chrome will crash 227 // on dereference, but extension/Pepper APIs will guard against NULL and not 228 // crash. 229 DLOG(ERROR) << "Histogram " << name_ << " has bad construction arguments"; 230 return nullptr; 231 } 232 return histogram; 233 } 234 235 HistogramBase* Histogram::FactoryGet(const std::string& name, 236 Sample minimum, 237 Sample maximum, 238 uint32_t bucket_count, 239 int32_t flags) { 240 bool valid_arguments = 241 InspectConstructionArguments(name, &minimum, &maximum, &bucket_count); 242 DCHECK(valid_arguments); 243 244 return Factory(name, minimum, maximum, bucket_count, flags).Build(); 245 } 246 247 HistogramBase* Histogram::FactoryTimeGet(const std::string& name, 248 TimeDelta minimum, 249 TimeDelta maximum, 250 uint32_t bucket_count, 251 int32_t flags) { 252 return FactoryGet(name, static_cast<Sample>(minimum.InMilliseconds()), 253 static_cast<Sample>(maximum.InMilliseconds()), bucket_count, 254 flags); 255 } 256 257 HistogramBase* Histogram::FactoryGet(const char* name, 258 Sample minimum, 259 Sample maximum, 260 uint32_t bucket_count, 261 int32_t flags) { 262 return FactoryGet(std::string(name), minimum, maximum, bucket_count, flags); 263 } 264 265 HistogramBase* Histogram::FactoryTimeGet(const char* name, 266 TimeDelta minimum, 267 TimeDelta maximum, 268 uint32_t bucket_count, 269 int32_t flags) { 270 return FactoryTimeGet(std::string(name), minimum, maximum, bucket_count, 271 flags); 272 } 273 274 std::unique_ptr<HistogramBase> Histogram::PersistentCreate( 275 const std::string& name, 276 Sample minimum, 277 Sample maximum, 278 const BucketRanges* ranges, 279 HistogramBase::AtomicCount* counts, 280 HistogramBase::AtomicCount* logged_counts, 281 uint32_t counts_size, 282 HistogramSamples::Metadata* meta, 283 HistogramSamples::Metadata* logged_meta) { 284 return WrapUnique(new Histogram(name, minimum, maximum, ranges, counts, 285 logged_counts, counts_size, meta, 286 logged_meta)); 287 } 288 289 // Calculate what range of values are held in each bucket. 290 // We have to be careful that we don't pick a ratio between starting points in 291 // consecutive buckets that is sooo small, that the integer bounds are the same 292 // (effectively making one bucket get no values). We need to avoid: 293 // ranges(i) == ranges(i + 1) 294 // To avoid that, we just do a fine-grained bucket width as far as we need to 295 // until we get a ratio that moves us along at least 2 units at a time. From 296 // that bucket onward we do use the exponential growth of buckets. 297 // 298 // static 299 void Histogram::InitializeBucketRanges(Sample minimum, 300 Sample maximum, 301 BucketRanges* ranges) { 302 double log_max = log(static_cast<double>(maximum)); 303 double log_ratio; 304 double log_next; 305 size_t bucket_index = 1; 306 Sample current = minimum; 307 ranges->set_range(bucket_index, current); 308 size_t bucket_count = ranges->bucket_count(); 309 while (bucket_count > ++bucket_index) { 310 double log_current; 311 log_current = log(static_cast<double>(current)); 312 // Calculate the count'th root of the range. 313 log_ratio = (log_max - log_current) / (bucket_count - bucket_index); 314 // See where the next bucket would start. 315 log_next = log_current + log_ratio; 316 Sample next; 317 next = static_cast<int>(floor(exp(log_next) + 0.5)); 318 if (next > current) 319 current = next; 320 else 321 ++current; // Just do a narrow bucket, and keep trying. 322 ranges->set_range(bucket_index, current); 323 } 324 ranges->set_range(ranges->bucket_count(), HistogramBase::kSampleType_MAX); 325 ranges->ResetChecksum(); 326 } 327 328 // static 329 const int Histogram::kCommonRaceBasedCountMismatch = 5; 330 331 uint32_t Histogram::FindCorruption(const HistogramSamples& samples) const { 332 int inconsistencies = NO_INCONSISTENCIES; 333 Sample previous_range = -1; // Bottom range is always 0. 334 for (uint32_t index = 0; index < bucket_count(); ++index) { 335 int new_range = ranges(index); 336 if (previous_range >= new_range) 337 inconsistencies |= BUCKET_ORDER_ERROR; 338 previous_range = new_range; 339 } 340 341 if (!bucket_ranges()->HasValidChecksum()) 342 inconsistencies |= RANGE_CHECKSUM_ERROR; 343 344 int64_t delta64 = samples.redundant_count() - samples.TotalCount(); 345 if (delta64 != 0) { 346 int delta = static_cast<int>(delta64); 347 if (delta != delta64) 348 delta = INT_MAX; // Flag all giant errors as INT_MAX. 349 if (delta > 0) { 350 UMA_HISTOGRAM_COUNTS("Histogram.InconsistentCountHigh", delta); 351 if (delta > kCommonRaceBasedCountMismatch) 352 inconsistencies |= COUNT_HIGH_ERROR; 353 } else { 354 DCHECK_GT(0, delta); 355 UMA_HISTOGRAM_COUNTS("Histogram.InconsistentCountLow", -delta); 356 if (-delta > kCommonRaceBasedCountMismatch) 357 inconsistencies |= COUNT_LOW_ERROR; 358 } 359 } 360 return inconsistencies; 361 } 362 363 Sample Histogram::ranges(uint32_t i) const { 364 return bucket_ranges_->range(i); 365 } 366 367 uint32_t Histogram::bucket_count() const { 368 return static_cast<uint32_t>(bucket_ranges_->bucket_count()); 369 } 370 371 // static 372 bool Histogram::InspectConstructionArguments(const std::string& name, 373 Sample* minimum, 374 Sample* maximum, 375 uint32_t* bucket_count) { 376 // Defensive code for backward compatibility. 377 if (*minimum < 1) { 378 DVLOG(1) << "Histogram: " << name << " has bad minimum: " << *minimum; 379 *minimum = 1; 380 } 381 if (*maximum >= kSampleType_MAX) { 382 DVLOG(1) << "Histogram: " << name << " has bad maximum: " << *maximum; 383 *maximum = kSampleType_MAX - 1; 384 } 385 if (*bucket_count >= kBucketCount_MAX) { 386 DVLOG(1) << "Histogram: " << name << " has bad bucket_count: " 387 << *bucket_count; 388 *bucket_count = kBucketCount_MAX - 1; 389 } 390 391 if (*minimum >= *maximum) 392 return false; 393 if (*bucket_count < 3) 394 return false; 395 if (*bucket_count > static_cast<uint32_t>(*maximum - *minimum + 2)) 396 return false; 397 return true; 398 } 399 400 uint64_t Histogram::name_hash() const { 401 return samples_->id(); 402 } 403 404 HistogramType Histogram::GetHistogramType() const { 405 return HISTOGRAM; 406 } 407 408 bool Histogram::HasConstructionArguments(Sample expected_minimum, 409 Sample expected_maximum, 410 uint32_t expected_bucket_count) const { 411 return ((expected_minimum == declared_min_) && 412 (expected_maximum == declared_max_) && 413 (expected_bucket_count == bucket_count())); 414 } 415 416 void Histogram::Add(int value) { 417 AddCount(value, 1); 418 } 419 420 void Histogram::AddCount(int value, int count) { 421 DCHECK_EQ(0, ranges(0)); 422 DCHECK_EQ(kSampleType_MAX, ranges(bucket_count())); 423 424 if (value > kSampleType_MAX - 1) 425 value = kSampleType_MAX - 1; 426 if (value < 0) 427 value = 0; 428 if (count <= 0) { 429 NOTREACHED(); 430 return; 431 } 432 samples_->Accumulate(value, count); 433 434 FindAndRunCallback(value); 435 } 436 437 std::unique_ptr<HistogramSamples> Histogram::SnapshotSamples() const { 438 return SnapshotSampleVector(); 439 } 440 441 std::unique_ptr<HistogramSamples> Histogram::SnapshotDelta() { 442 DCHECK(!final_delta_created_); 443 444 std::unique_ptr<HistogramSamples> snapshot = SnapshotSampleVector(); 445 if (!logged_samples_) { 446 // If nothing has been previously logged, save this one as 447 // |logged_samples_| and gather another snapshot to return. 448 logged_samples_.swap(snapshot); 449 return SnapshotSampleVector(); 450 } 451 452 // Subtract what was previously logged and update that information. 453 snapshot->Subtract(*logged_samples_); 454 logged_samples_->Add(*snapshot); 455 return snapshot; 456 } 457 458 std::unique_ptr<HistogramSamples> Histogram::SnapshotFinalDelta() const { 459 DCHECK(!final_delta_created_); 460 final_delta_created_ = true; 461 462 std::unique_ptr<HistogramSamples> snapshot = SnapshotSampleVector(); 463 464 // Subtract what was previously logged and then return. 465 if (logged_samples_) 466 snapshot->Subtract(*logged_samples_); 467 return snapshot; 468 } 469 470 void Histogram::AddSamples(const HistogramSamples& samples) { 471 samples_->Add(samples); 472 } 473 474 bool Histogram::AddSamplesFromPickle(PickleIterator* iter) { 475 return samples_->AddFromPickle(iter); 476 } 477 478 // The following methods provide a graphical histogram display. 479 void Histogram::WriteHTMLGraph(std::string* output) const { 480 // TBD(jar) Write a nice HTML bar chart, with divs an mouse-overs etc. 481 output->append("<PRE>"); 482 WriteAsciiImpl(true, "<br>", output); 483 output->append("</PRE>"); 484 } 485 486 void Histogram::WriteAscii(std::string* output) const { 487 WriteAsciiImpl(true, "\n", output); 488 } 489 490 bool Histogram::SerializeInfoImpl(Pickle* pickle) const { 491 DCHECK(bucket_ranges()->HasValidChecksum()); 492 return pickle->WriteString(histogram_name()) && 493 pickle->WriteInt(flags()) && 494 pickle->WriteInt(declared_min()) && 495 pickle->WriteInt(declared_max()) && 496 pickle->WriteUInt32(bucket_count()) && 497 pickle->WriteUInt32(bucket_ranges()->checksum()); 498 } 499 500 Histogram::Histogram(const std::string& name, 501 Sample minimum, 502 Sample maximum, 503 const BucketRanges* ranges) 504 : HistogramBase(name), 505 bucket_ranges_(ranges), 506 declared_min_(minimum), 507 declared_max_(maximum) { 508 if (ranges) 509 samples_.reset(new SampleVector(HashMetricName(name), ranges)); 510 } 511 512 Histogram::Histogram(const std::string& name, 513 Sample minimum, 514 Sample maximum, 515 const BucketRanges* ranges, 516 HistogramBase::AtomicCount* counts, 517 HistogramBase::AtomicCount* logged_counts, 518 uint32_t counts_size, 519 HistogramSamples::Metadata* meta, 520 HistogramSamples::Metadata* logged_meta) 521 : HistogramBase(name), 522 bucket_ranges_(ranges), 523 declared_min_(minimum), 524 declared_max_(maximum) { 525 if (ranges) { 526 samples_.reset(new SampleVector(HashMetricName(name), 527 counts, counts_size, meta, ranges)); 528 logged_samples_.reset(new SampleVector(samples_->id(), logged_counts, 529 counts_size, logged_meta, ranges)); 530 } 531 } 532 533 Histogram::~Histogram() { 534 } 535 536 bool Histogram::PrintEmptyBucket(uint32_t /*index*/) const { 537 return true; 538 } 539 540 // Use the actual bucket widths (like a linear histogram) until the widths get 541 // over some transition value, and then use that transition width. Exponentials 542 // get so big so fast (and we don't expect to see a lot of entries in the large 543 // buckets), so we need this to make it possible to see what is going on and 544 // not have 0-graphical-height buckets. 545 double Histogram::GetBucketSize(Count current, uint32_t i) const { 546 DCHECK_GT(ranges(i + 1), ranges(i)); 547 static const double kTransitionWidth = 5; 548 double denominator = ranges(i + 1) - ranges(i); 549 if (denominator > kTransitionWidth) 550 denominator = kTransitionWidth; // Stop trying to normalize. 551 return current/denominator; 552 } 553 554 const std::string Histogram::GetAsciiBucketRange(uint32_t i) const { 555 return GetSimpleAsciiBucketRange(ranges(i)); 556 } 557 558 //------------------------------------------------------------------------------ 559 // Private methods 560 561 // static 562 HistogramBase* Histogram::DeserializeInfoImpl(PickleIterator* iter) { 563 std::string histogram_name; 564 int flags; 565 int declared_min; 566 int declared_max; 567 uint32_t bucket_count; 568 uint32_t range_checksum; 569 570 if (!ReadHistogramArguments(iter, &histogram_name, &flags, &declared_min, 571 &declared_max, &bucket_count, &range_checksum)) { 572 return NULL; 573 } 574 575 // Find or create the local version of the histogram in this process. 576 HistogramBase* histogram = Histogram::FactoryGet( 577 histogram_name, declared_min, declared_max, bucket_count, flags); 578 579 if (!ValidateRangeChecksum(*histogram, range_checksum)) { 580 // The serialized histogram might be corrupted. 581 return NULL; 582 } 583 return histogram; 584 } 585 586 std::unique_ptr<SampleVector> Histogram::SnapshotSampleVector() const { 587 std::unique_ptr<SampleVector> samples( 588 new SampleVector(samples_->id(), bucket_ranges())); 589 samples->Add(*samples_); 590 return samples; 591 } 592 593 void Histogram::WriteAsciiImpl(bool graph_it, 594 const std::string& newline, 595 std::string* output) const { 596 // Get local (stack) copies of all effectively volatile class data so that we 597 // are consistent across our output activities. 598 std::unique_ptr<SampleVector> snapshot = SnapshotSampleVector(); 599 Count sample_count = snapshot->TotalCount(); 600 601 WriteAsciiHeader(*snapshot, sample_count, output); 602 output->append(newline); 603 604 // Prepare to normalize graphical rendering of bucket contents. 605 double max_size = 0; 606 if (graph_it) 607 max_size = GetPeakBucketSize(*snapshot); 608 609 // Calculate space needed to print bucket range numbers. Leave room to print 610 // nearly the largest bucket range without sliding over the histogram. 611 uint32_t largest_non_empty_bucket = bucket_count() - 1; 612 while (0 == snapshot->GetCountAtIndex(largest_non_empty_bucket)) { 613 if (0 == largest_non_empty_bucket) 614 break; // All buckets are empty. 615 --largest_non_empty_bucket; 616 } 617 618 // Calculate largest print width needed for any of our bucket range displays. 619 size_t print_width = 1; 620 for (uint32_t i = 0; i < bucket_count(); ++i) { 621 if (snapshot->GetCountAtIndex(i)) { 622 size_t width = GetAsciiBucketRange(i).size() + 1; 623 if (width > print_width) 624 print_width = width; 625 } 626 } 627 628 int64_t remaining = sample_count; 629 int64_t past = 0; 630 // Output the actual histogram graph. 631 for (uint32_t i = 0; i < bucket_count(); ++i) { 632 Count current = snapshot->GetCountAtIndex(i); 633 if (!current && !PrintEmptyBucket(i)) 634 continue; 635 remaining -= current; 636 std::string range = GetAsciiBucketRange(i); 637 output->append(range); 638 for (size_t j = 0; range.size() + j < print_width + 1; ++j) 639 output->push_back(' '); 640 if (0 == current && i < bucket_count() - 1 && 641 0 == snapshot->GetCountAtIndex(i + 1)) { 642 while (i < bucket_count() - 1 && 643 0 == snapshot->GetCountAtIndex(i + 1)) { 644 ++i; 645 } 646 output->append("... "); 647 output->append(newline); 648 continue; // No reason to plot emptiness. 649 } 650 double current_size = GetBucketSize(current, i); 651 if (graph_it) 652 WriteAsciiBucketGraph(current_size, max_size, output); 653 WriteAsciiBucketContext(past, current, remaining, i, output); 654 output->append(newline); 655 past += current; 656 } 657 DCHECK_EQ(sample_count, past); 658 } 659 660 double Histogram::GetPeakBucketSize(const SampleVector& samples) const { 661 double max = 0; 662 for (uint32_t i = 0; i < bucket_count() ; ++i) { 663 double current_size = GetBucketSize(samples.GetCountAtIndex(i), i); 664 if (current_size > max) 665 max = current_size; 666 } 667 return max; 668 } 669 670 void Histogram::WriteAsciiHeader(const SampleVector& samples, 671 Count sample_count, 672 std::string* output) const { 673 StringAppendF(output, 674 "Histogram: %s recorded %d samples", 675 histogram_name().c_str(), 676 sample_count); 677 if (0 == sample_count) { 678 DCHECK_EQ(samples.sum(), 0); 679 } else { 680 double average = static_cast<float>(samples.sum()) / sample_count; 681 682 StringAppendF(output, ", average = %.1f", average); 683 } 684 if (flags() & ~kHexRangePrintingFlag) 685 StringAppendF(output, " (flags = 0x%x)", flags() & ~kHexRangePrintingFlag); 686 } 687 688 void Histogram::WriteAsciiBucketContext(const int64_t past, 689 const Count current, 690 const int64_t remaining, 691 const uint32_t i, 692 std::string* output) const { 693 double scaled_sum = (past + current + remaining) / 100.0; 694 WriteAsciiBucketValue(current, scaled_sum, output); 695 if (0 < i) { 696 double percentage = past / scaled_sum; 697 StringAppendF(output, " {%3.1f%%}", percentage); 698 } 699 } 700 701 void Histogram::GetParameters(DictionaryValue* params) const { 702 params->SetString("type", HistogramTypeToString(GetHistogramType())); 703 params->SetInteger("min", declared_min()); 704 params->SetInteger("max", declared_max()); 705 params->SetInteger("bucket_count", static_cast<int>(bucket_count())); 706 } 707 708 void Histogram::GetCountAndBucketData(Count* count, 709 int64_t* sum, 710 ListValue* buckets) const { 711 std::unique_ptr<SampleVector> snapshot = SnapshotSampleVector(); 712 *count = snapshot->TotalCount(); 713 *sum = snapshot->sum(); 714 uint32_t index = 0; 715 for (uint32_t i = 0; i < bucket_count(); ++i) { 716 Sample count_at_index = snapshot->GetCountAtIndex(i); 717 if (count_at_index > 0) { 718 std::unique_ptr<DictionaryValue> bucket_value(new DictionaryValue()); 719 bucket_value->SetInteger("low", ranges(i)); 720 if (i != bucket_count() - 1) 721 bucket_value->SetInteger("high", ranges(i + 1)); 722 bucket_value->SetInteger("count", count_at_index); 723 buckets->Set(index, bucket_value.release()); 724 ++index; 725 } 726 } 727 } 728 729 //------------------------------------------------------------------------------ 730 // LinearHistogram: This histogram uses a traditional set of evenly spaced 731 // buckets. 732 //------------------------------------------------------------------------------ 733 734 class LinearHistogram::Factory : public Histogram::Factory { 735 public: 736 Factory(const std::string& name, 737 HistogramBase::Sample minimum, 738 HistogramBase::Sample maximum, 739 uint32_t bucket_count, 740 int32_t flags, 741 const DescriptionPair* descriptions) 742 : Histogram::Factory(name, LINEAR_HISTOGRAM, minimum, maximum, 743 bucket_count, flags) { 744 descriptions_ = descriptions; 745 } 746 ~Factory() override = default; 747 748 protected: 749 BucketRanges* CreateRanges() override { 750 BucketRanges* ranges = new BucketRanges(bucket_count_ + 1); 751 LinearHistogram::InitializeBucketRanges(minimum_, maximum_, ranges); 752 return ranges; 753 } 754 755 std::unique_ptr<HistogramBase> HeapAlloc( 756 const BucketRanges* ranges) override { 757 return WrapUnique( 758 new LinearHistogram(name_, minimum_, maximum_, ranges)); 759 } 760 761 void FillHistogram(HistogramBase* base_histogram) override { 762 Histogram::Factory::FillHistogram(base_histogram); 763 LinearHistogram* histogram = static_cast<LinearHistogram*>(base_histogram); 764 // Set range descriptions. 765 if (descriptions_) { 766 for (int i = 0; descriptions_[i].description; ++i) { 767 histogram->bucket_description_[descriptions_[i].sample] = 768 descriptions_[i].description; 769 } 770 } 771 } 772 773 private: 774 const DescriptionPair* descriptions_; 775 776 DISALLOW_COPY_AND_ASSIGN(Factory); 777 }; 778 779 LinearHistogram::~LinearHistogram() {} 780 781 HistogramBase* LinearHistogram::FactoryGet(const std::string& name, 782 Sample minimum, 783 Sample maximum, 784 uint32_t bucket_count, 785 int32_t flags) { 786 return FactoryGetWithRangeDescription( 787 name, minimum, maximum, bucket_count, flags, NULL); 788 } 789 790 HistogramBase* LinearHistogram::FactoryTimeGet(const std::string& name, 791 TimeDelta minimum, 792 TimeDelta maximum, 793 uint32_t bucket_count, 794 int32_t flags) { 795 return FactoryGet(name, static_cast<Sample>(minimum.InMilliseconds()), 796 static_cast<Sample>(maximum.InMilliseconds()), bucket_count, 797 flags); 798 } 799 800 HistogramBase* LinearHistogram::FactoryGet(const char* name, 801 Sample minimum, 802 Sample maximum, 803 uint32_t bucket_count, 804 int32_t flags) { 805 return FactoryGet(std::string(name), minimum, maximum, bucket_count, flags); 806 } 807 808 HistogramBase* LinearHistogram::FactoryTimeGet(const char* name, 809 TimeDelta minimum, 810 TimeDelta maximum, 811 uint32_t bucket_count, 812 int32_t flags) { 813 return FactoryTimeGet(std::string(name), minimum, maximum, bucket_count, 814 flags); 815 } 816 817 std::unique_ptr<HistogramBase> LinearHistogram::PersistentCreate( 818 const std::string& name, 819 Sample minimum, 820 Sample maximum, 821 const BucketRanges* ranges, 822 HistogramBase::AtomicCount* counts, 823 HistogramBase::AtomicCount* logged_counts, 824 uint32_t counts_size, 825 HistogramSamples::Metadata* meta, 826 HistogramSamples::Metadata* logged_meta) { 827 return WrapUnique(new LinearHistogram(name, minimum, maximum, ranges, 828 counts, logged_counts, 829 counts_size, meta, logged_meta)); 830 } 831 832 HistogramBase* LinearHistogram::FactoryGetWithRangeDescription( 833 const std::string& name, 834 Sample minimum, 835 Sample maximum, 836 uint32_t bucket_count, 837 int32_t flags, 838 const DescriptionPair descriptions[]) { 839 bool valid_arguments = Histogram::InspectConstructionArguments( 840 name, &minimum, &maximum, &bucket_count); 841 DCHECK(valid_arguments); 842 843 return Factory(name, minimum, maximum, bucket_count, flags, descriptions) 844 .Build(); 845 } 846 847 HistogramType LinearHistogram::GetHistogramType() const { 848 return LINEAR_HISTOGRAM; 849 } 850 851 LinearHistogram::LinearHistogram(const std::string& name, 852 Sample minimum, 853 Sample maximum, 854 const BucketRanges* ranges) 855 : Histogram(name, minimum, maximum, ranges) { 856 } 857 858 LinearHistogram::LinearHistogram(const std::string& name, 859 Sample minimum, 860 Sample maximum, 861 const BucketRanges* ranges, 862 HistogramBase::AtomicCount* counts, 863 HistogramBase::AtomicCount* logged_counts, 864 uint32_t counts_size, 865 HistogramSamples::Metadata* meta, 866 HistogramSamples::Metadata* logged_meta) 867 : Histogram(name, minimum, maximum, ranges, counts, logged_counts, 868 counts_size, meta, logged_meta) {} 869 870 double LinearHistogram::GetBucketSize(Count current, uint32_t i) const { 871 DCHECK_GT(ranges(i + 1), ranges(i)); 872 // Adjacent buckets with different widths would have "surprisingly" many (few) 873 // samples in a histogram if we didn't normalize this way. 874 double denominator = ranges(i + 1) - ranges(i); 875 return current/denominator; 876 } 877 878 const std::string LinearHistogram::GetAsciiBucketRange(uint32_t i) const { 879 int range = ranges(i); 880 BucketDescriptionMap::const_iterator it = bucket_description_.find(range); 881 if (it == bucket_description_.end()) 882 return Histogram::GetAsciiBucketRange(i); 883 return it->second; 884 } 885 886 bool LinearHistogram::PrintEmptyBucket(uint32_t index) const { 887 return bucket_description_.find(ranges(index)) == bucket_description_.end(); 888 } 889 890 // static 891 void LinearHistogram::InitializeBucketRanges(Sample minimum, 892 Sample maximum, 893 BucketRanges* ranges) { 894 double min = minimum; 895 double max = maximum; 896 size_t bucket_count = ranges->bucket_count(); 897 for (size_t i = 1; i < bucket_count; ++i) { 898 double linear_range = 899 (min * (bucket_count - 1 - i) + max * (i - 1)) / (bucket_count - 2); 900 ranges->set_range(i, static_cast<Sample>(linear_range + 0.5)); 901 // TODO(bcwhite): Remove once crbug/586622 is fixed. 902 base::debug::Alias(&linear_range); 903 } 904 ranges->set_range(ranges->bucket_count(), HistogramBase::kSampleType_MAX); 905 ranges->ResetChecksum(); 906 } 907 908 // static 909 HistogramBase* LinearHistogram::DeserializeInfoImpl(PickleIterator* iter) { 910 std::string histogram_name; 911 int flags; 912 int declared_min; 913 int declared_max; 914 uint32_t bucket_count; 915 uint32_t range_checksum; 916 917 if (!ReadHistogramArguments(iter, &histogram_name, &flags, &declared_min, 918 &declared_max, &bucket_count, &range_checksum)) { 919 return NULL; 920 } 921 922 HistogramBase* histogram = LinearHistogram::FactoryGet( 923 histogram_name, declared_min, declared_max, bucket_count, flags); 924 if (!ValidateRangeChecksum(*histogram, range_checksum)) { 925 // The serialized histogram might be corrupted. 926 return NULL; 927 } 928 return histogram; 929 } 930 931 //------------------------------------------------------------------------------ 932 // This section provides implementation for BooleanHistogram. 933 //------------------------------------------------------------------------------ 934 935 class BooleanHistogram::Factory : public Histogram::Factory { 936 public: 937 Factory(const std::string& name, int32_t flags) 938 : Histogram::Factory(name, BOOLEAN_HISTOGRAM, 1, 2, 3, flags) {} 939 ~Factory() override = default; 940 941 protected: 942 BucketRanges* CreateRanges() override { 943 BucketRanges* ranges = new BucketRanges(3 + 1); 944 LinearHistogram::InitializeBucketRanges(1, 2, ranges); 945 return ranges; 946 } 947 948 std::unique_ptr<HistogramBase> HeapAlloc( 949 const BucketRanges* ranges) override { 950 return WrapUnique(new BooleanHistogram(name_, ranges)); 951 } 952 953 private: 954 DISALLOW_COPY_AND_ASSIGN(Factory); 955 }; 956 957 HistogramBase* BooleanHistogram::FactoryGet(const std::string& name, 958 int32_t flags) { 959 return Factory(name, flags).Build(); 960 } 961 962 HistogramBase* BooleanHistogram::FactoryGet(const char* name, int32_t flags) { 963 return FactoryGet(std::string(name), flags); 964 } 965 966 std::unique_ptr<HistogramBase> BooleanHistogram::PersistentCreate( 967 const std::string& name, 968 const BucketRanges* ranges, 969 HistogramBase::AtomicCount* counts, 970 HistogramBase::AtomicCount* logged_counts, 971 HistogramSamples::Metadata* meta, 972 HistogramSamples::Metadata* logged_meta) { 973 return WrapUnique(new BooleanHistogram( 974 name, ranges, counts, logged_counts, meta, logged_meta)); 975 } 976 977 HistogramType BooleanHistogram::GetHistogramType() const { 978 return BOOLEAN_HISTOGRAM; 979 } 980 981 BooleanHistogram::BooleanHistogram(const std::string& name, 982 const BucketRanges* ranges) 983 : LinearHistogram(name, 1, 2, ranges) {} 984 985 BooleanHistogram::BooleanHistogram(const std::string& name, 986 const BucketRanges* ranges, 987 HistogramBase::AtomicCount* counts, 988 HistogramBase::AtomicCount* logged_counts, 989 HistogramSamples::Metadata* meta, 990 HistogramSamples::Metadata* logged_meta) 991 : LinearHistogram(name, 1, 2, ranges, counts, logged_counts, 2, meta, 992 logged_meta) {} 993 994 HistogramBase* BooleanHistogram::DeserializeInfoImpl(PickleIterator* iter) { 995 std::string histogram_name; 996 int flags; 997 int declared_min; 998 int declared_max; 999 uint32_t bucket_count; 1000 uint32_t range_checksum; 1001 1002 if (!ReadHistogramArguments(iter, &histogram_name, &flags, &declared_min, 1003 &declared_max, &bucket_count, &range_checksum)) { 1004 return NULL; 1005 } 1006 1007 HistogramBase* histogram = BooleanHistogram::FactoryGet( 1008 histogram_name, flags); 1009 if (!ValidateRangeChecksum(*histogram, range_checksum)) { 1010 // The serialized histogram might be corrupted. 1011 return NULL; 1012 } 1013 return histogram; 1014 } 1015 1016 //------------------------------------------------------------------------------ 1017 // CustomHistogram: 1018 //------------------------------------------------------------------------------ 1019 1020 class CustomHistogram::Factory : public Histogram::Factory { 1021 public: 1022 Factory(const std::string& name, 1023 const std::vector<Sample>* custom_ranges, 1024 int32_t flags) 1025 : Histogram::Factory(name, CUSTOM_HISTOGRAM, 0, 0, 0, flags) { 1026 custom_ranges_ = custom_ranges; 1027 } 1028 ~Factory() override = default; 1029 1030 protected: 1031 BucketRanges* CreateRanges() override { 1032 // Remove the duplicates in the custom ranges array. 1033 std::vector<int> ranges = *custom_ranges_; 1034 ranges.push_back(0); // Ensure we have a zero value. 1035 ranges.push_back(HistogramBase::kSampleType_MAX); 1036 std::sort(ranges.begin(), ranges.end()); 1037 ranges.erase(std::unique(ranges.begin(), ranges.end()), ranges.end()); 1038 1039 BucketRanges* bucket_ranges = new BucketRanges(ranges.size()); 1040 for (uint32_t i = 0; i < ranges.size(); i++) { 1041 bucket_ranges->set_range(i, ranges[i]); 1042 } 1043 bucket_ranges->ResetChecksum(); 1044 return bucket_ranges; 1045 } 1046 1047 std::unique_ptr<HistogramBase> HeapAlloc( 1048 const BucketRanges* ranges) override { 1049 return WrapUnique(new CustomHistogram(name_, ranges)); 1050 } 1051 1052 private: 1053 const std::vector<Sample>* custom_ranges_; 1054 1055 DISALLOW_COPY_AND_ASSIGN(Factory); 1056 }; 1057 1058 HistogramBase* CustomHistogram::FactoryGet( 1059 const std::string& name, 1060 const std::vector<Sample>& custom_ranges, 1061 int32_t flags) { 1062 CHECK(ValidateCustomRanges(custom_ranges)); 1063 1064 return Factory(name, &custom_ranges, flags).Build(); 1065 } 1066 1067 HistogramBase* CustomHistogram::FactoryGet( 1068 const char* name, 1069 const std::vector<Sample>& custom_ranges, 1070 int32_t flags) { 1071 return FactoryGet(std::string(name), custom_ranges, flags); 1072 } 1073 1074 std::unique_ptr<HistogramBase> CustomHistogram::PersistentCreate( 1075 const std::string& name, 1076 const BucketRanges* ranges, 1077 HistogramBase::AtomicCount* counts, 1078 HistogramBase::AtomicCount* logged_counts, 1079 uint32_t counts_size, 1080 HistogramSamples::Metadata* meta, 1081 HistogramSamples::Metadata* logged_meta) { 1082 return WrapUnique(new CustomHistogram( 1083 name, ranges, counts, logged_counts, counts_size, meta, logged_meta)); 1084 } 1085 1086 HistogramType CustomHistogram::GetHistogramType() const { 1087 return CUSTOM_HISTOGRAM; 1088 } 1089 1090 // static 1091 std::vector<Sample> CustomHistogram::ArrayToCustomRanges( 1092 const Sample* values, uint32_t num_values) { 1093 std::vector<Sample> all_values; 1094 for (uint32_t i = 0; i < num_values; ++i) { 1095 Sample value = values[i]; 1096 all_values.push_back(value); 1097 1098 // Ensure that a guard bucket is added. If we end up with duplicate 1099 // values, FactoryGet will take care of removing them. 1100 all_values.push_back(value + 1); 1101 } 1102 return all_values; 1103 } 1104 1105 CustomHistogram::CustomHistogram(const std::string& name, 1106 const BucketRanges* ranges) 1107 : Histogram(name, 1108 ranges->range(1), 1109 ranges->range(ranges->bucket_count() - 1), 1110 ranges) {} 1111 1112 CustomHistogram::CustomHistogram(const std::string& name, 1113 const BucketRanges* ranges, 1114 HistogramBase::AtomicCount* counts, 1115 HistogramBase::AtomicCount* logged_counts, 1116 uint32_t counts_size, 1117 HistogramSamples::Metadata* meta, 1118 HistogramSamples::Metadata* logged_meta) 1119 : Histogram(name, 1120 ranges->range(1), 1121 ranges->range(ranges->bucket_count() - 1), 1122 ranges, 1123 counts, 1124 logged_counts, 1125 counts_size, 1126 meta, 1127 logged_meta) {} 1128 1129 bool CustomHistogram::SerializeInfoImpl(Pickle* pickle) const { 1130 if (!Histogram::SerializeInfoImpl(pickle)) 1131 return false; 1132 1133 // Serialize ranges. First and last ranges are alwasy 0 and INT_MAX, so don't 1134 // write them. 1135 for (uint32_t i = 1; i < bucket_ranges()->bucket_count(); ++i) { 1136 if (!pickle->WriteInt(bucket_ranges()->range(i))) 1137 return false; 1138 } 1139 return true; 1140 } 1141 1142 double CustomHistogram::GetBucketSize(Count /*current*/, uint32_t /*i*/) const { 1143 return 1; 1144 } 1145 1146 // static 1147 HistogramBase* CustomHistogram::DeserializeInfoImpl(PickleIterator* iter) { 1148 std::string histogram_name; 1149 int flags; 1150 int declared_min; 1151 int declared_max; 1152 uint32_t bucket_count; 1153 uint32_t range_checksum; 1154 1155 if (!ReadHistogramArguments(iter, &histogram_name, &flags, &declared_min, 1156 &declared_max, &bucket_count, &range_checksum)) { 1157 return NULL; 1158 } 1159 1160 // First and last ranges are not serialized. 1161 std::vector<Sample> sample_ranges(bucket_count - 1); 1162 1163 for (uint32_t i = 0; i < sample_ranges.size(); ++i) { 1164 if (!iter->ReadInt(&sample_ranges[i])) 1165 return NULL; 1166 } 1167 1168 HistogramBase* histogram = CustomHistogram::FactoryGet( 1169 histogram_name, sample_ranges, flags); 1170 if (!ValidateRangeChecksum(*histogram, range_checksum)) { 1171 // The serialized histogram might be corrupted. 1172 return NULL; 1173 } 1174 return histogram; 1175 } 1176 1177 // static 1178 bool CustomHistogram::ValidateCustomRanges( 1179 const std::vector<Sample>& custom_ranges) { 1180 bool has_valid_range = false; 1181 for (uint32_t i = 0; i < custom_ranges.size(); i++) { 1182 Sample sample = custom_ranges[i]; 1183 if (sample < 0 || sample > HistogramBase::kSampleType_MAX - 1) 1184 return false; 1185 if (sample != 0) 1186 has_valid_range = true; 1187 } 1188 return has_valid_range; 1189 } 1190 1191 } // namespace base 1192