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 CHECK_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 (sample_count == 0) { 678 DCHECK_EQ(samples.sum(), 0); 679 } else { 680 double mean = static_cast<float>(samples.sum()) / sample_count; 681 StringAppendF(output, ", mean = %.1f", mean); 682 } 683 if (flags()) 684 StringAppendF(output, " (flags = 0x%x)", flags()); 685 } 686 687 void Histogram::WriteAsciiBucketContext(const int64_t past, 688 const Count current, 689 const int64_t remaining, 690 const uint32_t i, 691 std::string* output) const { 692 double scaled_sum = (past + current + remaining) / 100.0; 693 WriteAsciiBucketValue(current, scaled_sum, output); 694 if (0 < i) { 695 double percentage = past / scaled_sum; 696 StringAppendF(output, " {%3.1f%%}", percentage); 697 } 698 } 699 700 void Histogram::GetParameters(DictionaryValue* params) const { 701 params->SetString("type", HistogramTypeToString(GetHistogramType())); 702 params->SetInteger("min", declared_min()); 703 params->SetInteger("max", declared_max()); 704 params->SetInteger("bucket_count", static_cast<int>(bucket_count())); 705 } 706 707 void Histogram::GetCountAndBucketData(Count* count, 708 int64_t* sum, 709 ListValue* buckets) const { 710 std::unique_ptr<SampleVector> snapshot = SnapshotSampleVector(); 711 *count = snapshot->TotalCount(); 712 *sum = snapshot->sum(); 713 uint32_t index = 0; 714 for (uint32_t i = 0; i < bucket_count(); ++i) { 715 Sample count_at_index = snapshot->GetCountAtIndex(i); 716 if (count_at_index > 0) { 717 std::unique_ptr<DictionaryValue> bucket_value(new DictionaryValue()); 718 bucket_value->SetInteger("low", ranges(i)); 719 if (i != bucket_count() - 1) 720 bucket_value->SetInteger("high", ranges(i + 1)); 721 bucket_value->SetInteger("count", count_at_index); 722 buckets->Set(index, bucket_value.release()); 723 ++index; 724 } 725 } 726 } 727 728 //------------------------------------------------------------------------------ 729 // LinearHistogram: This histogram uses a traditional set of evenly spaced 730 // buckets. 731 //------------------------------------------------------------------------------ 732 733 class LinearHistogram::Factory : public Histogram::Factory { 734 public: 735 Factory(const std::string& name, 736 HistogramBase::Sample minimum, 737 HistogramBase::Sample maximum, 738 uint32_t bucket_count, 739 int32_t flags, 740 const DescriptionPair* descriptions) 741 : Histogram::Factory(name, LINEAR_HISTOGRAM, minimum, maximum, 742 bucket_count, flags) { 743 descriptions_ = descriptions; 744 } 745 ~Factory() override = default; 746 747 protected: 748 BucketRanges* CreateRanges() override { 749 BucketRanges* ranges = new BucketRanges(bucket_count_ + 1); 750 LinearHistogram::InitializeBucketRanges(minimum_, maximum_, ranges); 751 return ranges; 752 } 753 754 std::unique_ptr<HistogramBase> HeapAlloc( 755 const BucketRanges* ranges) override { 756 return WrapUnique(new LinearHistogram(name_, minimum_, maximum_, ranges)); 757 } 758 759 void FillHistogram(HistogramBase* base_histogram) override { 760 Histogram::Factory::FillHistogram(base_histogram); 761 LinearHistogram* histogram = static_cast<LinearHistogram*>(base_histogram); 762 // Set range descriptions. 763 if (descriptions_) { 764 for (int i = 0; descriptions_[i].description; ++i) { 765 histogram->bucket_description_[descriptions_[i].sample] = 766 descriptions_[i].description; 767 } 768 } 769 } 770 771 private: 772 const DescriptionPair* descriptions_; 773 774 DISALLOW_COPY_AND_ASSIGN(Factory); 775 }; 776 777 LinearHistogram::~LinearHistogram() {} 778 779 HistogramBase* LinearHistogram::FactoryGet(const std::string& name, 780 Sample minimum, 781 Sample maximum, 782 uint32_t bucket_count, 783 int32_t flags) { 784 return FactoryGetWithRangeDescription( 785 name, minimum, maximum, bucket_count, flags, NULL); 786 } 787 788 HistogramBase* LinearHistogram::FactoryTimeGet(const std::string& name, 789 TimeDelta minimum, 790 TimeDelta maximum, 791 uint32_t bucket_count, 792 int32_t flags) { 793 return FactoryGet(name, static_cast<Sample>(minimum.InMilliseconds()), 794 static_cast<Sample>(maximum.InMilliseconds()), bucket_count, 795 flags); 796 } 797 798 HistogramBase* LinearHistogram::FactoryGet(const char* name, 799 Sample minimum, 800 Sample maximum, 801 uint32_t bucket_count, 802 int32_t flags) { 803 return FactoryGet(std::string(name), minimum, maximum, bucket_count, flags); 804 } 805 806 HistogramBase* LinearHistogram::FactoryTimeGet(const char* name, 807 TimeDelta minimum, 808 TimeDelta maximum, 809 uint32_t bucket_count, 810 int32_t flags) { 811 return FactoryTimeGet(std::string(name), minimum, maximum, bucket_count, 812 flags); 813 } 814 815 std::unique_ptr<HistogramBase> LinearHistogram::PersistentCreate( 816 const std::string& name, 817 Sample minimum, 818 Sample maximum, 819 const BucketRanges* ranges, 820 HistogramBase::AtomicCount* counts, 821 HistogramBase::AtomicCount* logged_counts, 822 uint32_t counts_size, 823 HistogramSamples::Metadata* meta, 824 HistogramSamples::Metadata* logged_meta) { 825 return WrapUnique(new LinearHistogram(name, minimum, maximum, ranges, 826 counts, logged_counts, 827 counts_size, meta, logged_meta)); 828 } 829 830 HistogramBase* LinearHistogram::FactoryGetWithRangeDescription( 831 const std::string& name, 832 Sample minimum, 833 Sample maximum, 834 uint32_t bucket_count, 835 int32_t flags, 836 const DescriptionPair descriptions[]) { 837 bool valid_arguments = Histogram::InspectConstructionArguments( 838 name, &minimum, &maximum, &bucket_count); 839 DCHECK(valid_arguments); 840 841 return Factory(name, minimum, maximum, bucket_count, flags, descriptions) 842 .Build(); 843 } 844 845 HistogramType LinearHistogram::GetHistogramType() const { 846 return LINEAR_HISTOGRAM; 847 } 848 849 LinearHistogram::LinearHistogram(const std::string& name, 850 Sample minimum, 851 Sample maximum, 852 const BucketRanges* ranges) 853 : Histogram(name, minimum, maximum, ranges) { 854 } 855 856 LinearHistogram::LinearHistogram(const std::string& name, 857 Sample minimum, 858 Sample maximum, 859 const BucketRanges* ranges, 860 HistogramBase::AtomicCount* counts, 861 HistogramBase::AtomicCount* logged_counts, 862 uint32_t counts_size, 863 HistogramSamples::Metadata* meta, 864 HistogramSamples::Metadata* logged_meta) 865 : Histogram(name, minimum, maximum, ranges, counts, logged_counts, 866 counts_size, meta, logged_meta) {} 867 868 double LinearHistogram::GetBucketSize(Count current, uint32_t i) const { 869 DCHECK_GT(ranges(i + 1), ranges(i)); 870 // Adjacent buckets with different widths would have "surprisingly" many (few) 871 // samples in a histogram if we didn't normalize this way. 872 double denominator = ranges(i + 1) - ranges(i); 873 return current/denominator; 874 } 875 876 const std::string LinearHistogram::GetAsciiBucketRange(uint32_t i) const { 877 int range = ranges(i); 878 BucketDescriptionMap::const_iterator it = bucket_description_.find(range); 879 if (it == bucket_description_.end()) 880 return Histogram::GetAsciiBucketRange(i); 881 return it->second; 882 } 883 884 bool LinearHistogram::PrintEmptyBucket(uint32_t index) const { 885 return bucket_description_.find(ranges(index)) == bucket_description_.end(); 886 } 887 888 // static 889 void LinearHistogram::InitializeBucketRanges(Sample minimum, 890 Sample maximum, 891 BucketRanges* ranges) { 892 double min = minimum; 893 double max = maximum; 894 size_t bucket_count = ranges->bucket_count(); 895 for (size_t i = 1; i < bucket_count; ++i) { 896 double linear_range = 897 (min * (bucket_count - 1 - i) + max * (i - 1)) / (bucket_count - 2); 898 ranges->set_range(i, static_cast<Sample>(linear_range + 0.5)); 899 // TODO(bcwhite): Remove once crbug/586622 is fixed. 900 base::debug::Alias(&linear_range); 901 } 902 ranges->set_range(ranges->bucket_count(), HistogramBase::kSampleType_MAX); 903 ranges->ResetChecksum(); 904 } 905 906 // static 907 HistogramBase* LinearHistogram::DeserializeInfoImpl(PickleIterator* iter) { 908 std::string histogram_name; 909 int flags; 910 int declared_min; 911 int declared_max; 912 uint32_t bucket_count; 913 uint32_t range_checksum; 914 915 if (!ReadHistogramArguments(iter, &histogram_name, &flags, &declared_min, 916 &declared_max, &bucket_count, &range_checksum)) { 917 return NULL; 918 } 919 920 HistogramBase* histogram = LinearHistogram::FactoryGet( 921 histogram_name, declared_min, declared_max, bucket_count, flags); 922 if (!ValidateRangeChecksum(*histogram, range_checksum)) { 923 // The serialized histogram might be corrupted. 924 return NULL; 925 } 926 return histogram; 927 } 928 929 //------------------------------------------------------------------------------ 930 // This section provides implementation for BooleanHistogram. 931 //------------------------------------------------------------------------------ 932 933 class BooleanHistogram::Factory : public Histogram::Factory { 934 public: 935 Factory(const std::string& name, int32_t flags) 936 : Histogram::Factory(name, BOOLEAN_HISTOGRAM, 1, 2, 3, flags) {} 937 ~Factory() override = default; 938 939 protected: 940 BucketRanges* CreateRanges() override { 941 BucketRanges* ranges = new BucketRanges(3 + 1); 942 LinearHistogram::InitializeBucketRanges(1, 2, ranges); 943 return ranges; 944 } 945 946 std::unique_ptr<HistogramBase> HeapAlloc( 947 const BucketRanges* ranges) override { 948 return WrapUnique(new BooleanHistogram(name_, ranges)); 949 } 950 951 private: 952 DISALLOW_COPY_AND_ASSIGN(Factory); 953 }; 954 955 HistogramBase* BooleanHistogram::FactoryGet(const std::string& name, 956 int32_t flags) { 957 return Factory(name, flags).Build(); 958 } 959 960 HistogramBase* BooleanHistogram::FactoryGet(const char* name, int32_t flags) { 961 return FactoryGet(std::string(name), flags); 962 } 963 964 std::unique_ptr<HistogramBase> BooleanHistogram::PersistentCreate( 965 const std::string& name, 966 const BucketRanges* ranges, 967 HistogramBase::AtomicCount* counts, 968 HistogramBase::AtomicCount* logged_counts, 969 HistogramSamples::Metadata* meta, 970 HistogramSamples::Metadata* logged_meta) { 971 return WrapUnique(new BooleanHistogram( 972 name, ranges, counts, logged_counts, meta, logged_meta)); 973 } 974 975 HistogramType BooleanHistogram::GetHistogramType() const { 976 return BOOLEAN_HISTOGRAM; 977 } 978 979 BooleanHistogram::BooleanHistogram(const std::string& name, 980 const BucketRanges* ranges) 981 : LinearHistogram(name, 1, 2, ranges) {} 982 983 BooleanHistogram::BooleanHistogram(const std::string& name, 984 const BucketRanges* ranges, 985 HistogramBase::AtomicCount* counts, 986 HistogramBase::AtomicCount* logged_counts, 987 HistogramSamples::Metadata* meta, 988 HistogramSamples::Metadata* logged_meta) 989 : LinearHistogram(name, 1, 2, ranges, counts, logged_counts, 2, meta, 990 logged_meta) {} 991 992 HistogramBase* BooleanHistogram::DeserializeInfoImpl(PickleIterator* iter) { 993 std::string histogram_name; 994 int flags; 995 int declared_min; 996 int declared_max; 997 uint32_t bucket_count; 998 uint32_t range_checksum; 999 1000 if (!ReadHistogramArguments(iter, &histogram_name, &flags, &declared_min, 1001 &declared_max, &bucket_count, &range_checksum)) { 1002 return NULL; 1003 } 1004 1005 HistogramBase* histogram = BooleanHistogram::FactoryGet( 1006 histogram_name, flags); 1007 if (!ValidateRangeChecksum(*histogram, range_checksum)) { 1008 // The serialized histogram might be corrupted. 1009 return NULL; 1010 } 1011 return histogram; 1012 } 1013 1014 //------------------------------------------------------------------------------ 1015 // CustomHistogram: 1016 //------------------------------------------------------------------------------ 1017 1018 class CustomHistogram::Factory : public Histogram::Factory { 1019 public: 1020 Factory(const std::string& name, 1021 const std::vector<Sample>* custom_ranges, 1022 int32_t flags) 1023 : Histogram::Factory(name, CUSTOM_HISTOGRAM, 0, 0, 0, flags) { 1024 custom_ranges_ = custom_ranges; 1025 } 1026 ~Factory() override = default; 1027 1028 protected: 1029 BucketRanges* CreateRanges() override { 1030 // Remove the duplicates in the custom ranges array. 1031 std::vector<int> ranges = *custom_ranges_; 1032 ranges.push_back(0); // Ensure we have a zero value. 1033 ranges.push_back(HistogramBase::kSampleType_MAX); 1034 std::sort(ranges.begin(), ranges.end()); 1035 ranges.erase(std::unique(ranges.begin(), ranges.end()), ranges.end()); 1036 1037 BucketRanges* bucket_ranges = new BucketRanges(ranges.size()); 1038 for (uint32_t i = 0; i < ranges.size(); i++) { 1039 bucket_ranges->set_range(i, ranges[i]); 1040 } 1041 bucket_ranges->ResetChecksum(); 1042 return bucket_ranges; 1043 } 1044 1045 std::unique_ptr<HistogramBase> HeapAlloc( 1046 const BucketRanges* ranges) override { 1047 return WrapUnique(new CustomHistogram(name_, ranges)); 1048 } 1049 1050 private: 1051 const std::vector<Sample>* custom_ranges_; 1052 1053 DISALLOW_COPY_AND_ASSIGN(Factory); 1054 }; 1055 1056 HistogramBase* CustomHistogram::FactoryGet( 1057 const std::string& name, 1058 const std::vector<Sample>& custom_ranges, 1059 int32_t flags) { 1060 CHECK(ValidateCustomRanges(custom_ranges)); 1061 1062 return Factory(name, &custom_ranges, flags).Build(); 1063 } 1064 1065 HistogramBase* CustomHistogram::FactoryGet( 1066 const char* name, 1067 const std::vector<Sample>& custom_ranges, 1068 int32_t flags) { 1069 return FactoryGet(std::string(name), custom_ranges, flags); 1070 } 1071 1072 std::unique_ptr<HistogramBase> CustomHistogram::PersistentCreate( 1073 const std::string& name, 1074 const BucketRanges* ranges, 1075 HistogramBase::AtomicCount* counts, 1076 HistogramBase::AtomicCount* logged_counts, 1077 uint32_t counts_size, 1078 HistogramSamples::Metadata* meta, 1079 HistogramSamples::Metadata* logged_meta) { 1080 return WrapUnique(new CustomHistogram( 1081 name, ranges, counts, logged_counts, counts_size, meta, logged_meta)); 1082 } 1083 1084 HistogramType CustomHistogram::GetHistogramType() const { 1085 return CUSTOM_HISTOGRAM; 1086 } 1087 1088 // static 1089 std::vector<Sample> CustomHistogram::ArrayToCustomRanges( 1090 const Sample* values, uint32_t num_values) { 1091 std::vector<Sample> all_values; 1092 for (uint32_t i = 0; i < num_values; ++i) { 1093 Sample value = values[i]; 1094 all_values.push_back(value); 1095 1096 // Ensure that a guard bucket is added. If we end up with duplicate 1097 // values, FactoryGet will take care of removing them. 1098 all_values.push_back(value + 1); 1099 } 1100 return all_values; 1101 } 1102 1103 CustomHistogram::CustomHistogram(const std::string& name, 1104 const BucketRanges* ranges) 1105 : Histogram(name, 1106 ranges->range(1), 1107 ranges->range(ranges->bucket_count() - 1), 1108 ranges) {} 1109 1110 CustomHistogram::CustomHistogram(const std::string& name, 1111 const BucketRanges* ranges, 1112 HistogramBase::AtomicCount* counts, 1113 HistogramBase::AtomicCount* logged_counts, 1114 uint32_t counts_size, 1115 HistogramSamples::Metadata* meta, 1116 HistogramSamples::Metadata* logged_meta) 1117 : Histogram(name, 1118 ranges->range(1), 1119 ranges->range(ranges->bucket_count() - 1), 1120 ranges, 1121 counts, 1122 logged_counts, 1123 counts_size, 1124 meta, 1125 logged_meta) {} 1126 1127 bool CustomHistogram::SerializeInfoImpl(Pickle* pickle) const { 1128 if (!Histogram::SerializeInfoImpl(pickle)) 1129 return false; 1130 1131 // Serialize ranges. First and last ranges are alwasy 0 and INT_MAX, so don't 1132 // write them. 1133 for (uint32_t i = 1; i < bucket_ranges()->bucket_count(); ++i) { 1134 if (!pickle->WriteInt(bucket_ranges()->range(i))) 1135 return false; 1136 } 1137 return true; 1138 } 1139 1140 double CustomHistogram::GetBucketSize(Count current, uint32_t i) const { 1141 // If this is a histogram of enum values, normalizing the bucket count 1142 // by the bucket range is not helpful, so just return the bucket count. 1143 return current; 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
