tracked_objects.cc revision 201ade2fbba22bfb27ae029f4d23fca6ded109a0
1// Copyright (c) 2010 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include "base/tracked_objects.h" 6 7#include <math.h> 8 9#include "base/format_macros.h" 10#include "base/message_loop.h" 11#include "base/string_util.h" 12#include "base/stringprintf.h" 13#include "base/thread_restrictions.h" 14 15using base::TimeDelta; 16 17namespace tracked_objects { 18 19// A TLS slot to the TrackRegistry for the current thread. 20// static 21TLSSlot ThreadData::tls_index_(base::LINKER_INITIALIZED); 22 23// A global state variable to prevent repeated initialization during tests. 24// static 25AutoTracking::State AutoTracking::state_ = AutoTracking::kNeverBeenRun; 26 27//------------------------------------------------------------------------------ 28// Death data tallies durations when a death takes place. 29 30void DeathData::RecordDeath(const TimeDelta& duration) { 31 ++count_; 32 life_duration_ += duration; 33 int64 milliseconds = duration.InMilliseconds(); 34 square_duration_ += milliseconds * milliseconds; 35} 36 37int DeathData::AverageMsDuration() const { 38 return static_cast<int>(life_duration_.InMilliseconds() / count_); 39} 40 41double DeathData::StandardDeviation() const { 42 double average = AverageMsDuration(); 43 double variance = static_cast<float>(square_duration_)/count_ 44 - average * average; 45 return sqrt(variance); 46} 47 48 49void DeathData::AddDeathData(const DeathData& other) { 50 count_ += other.count_; 51 life_duration_ += other.life_duration_; 52 square_duration_ += other.square_duration_; 53} 54 55void DeathData::Write(std::string* output) const { 56 if (!count_) 57 return; 58 if (1 == count_) { 59 base::StringAppendF(output, "(1)Life in %dms ", AverageMsDuration()); 60 } else { 61 base::StringAppendF(output, "(%d)Lives %dms/life ", 62 count_, AverageMsDuration()); 63 } 64} 65 66void DeathData::Clear() { 67 count_ = 0; 68 life_duration_ = TimeDelta(); 69 square_duration_ = 0; 70} 71 72//------------------------------------------------------------------------------ 73BirthOnThread::BirthOnThread(const Location& location) 74 : location_(location), 75 birth_thread_(ThreadData::current()) { } 76 77//------------------------------------------------------------------------------ 78Births::Births(const Location& location) 79 : BirthOnThread(location), 80 birth_count_(1) { } 81 82//------------------------------------------------------------------------------ 83// ThreadData maintains the central data for all births and death. 84 85// static 86ThreadData* ThreadData::first_ = NULL; 87// static 88Lock ThreadData::list_lock_; 89 90// static 91ThreadData::Status ThreadData::status_ = ThreadData::UNINITIALIZED; 92 93ThreadData::ThreadData() : next_(NULL) { 94 // This shouldn't use the MessageLoop::current() LazyInstance since this might 95 // be used on a non-joinable thread. 96 // http://crbug.com/62728 97 base::ThreadRestrictions::ScopedAllowSingleton scoped_allow_singleton; 98 message_loop_ = MessageLoop::current(); 99} 100 101ThreadData::~ThreadData() {} 102 103// static 104ThreadData* ThreadData::current() { 105 if (!tls_index_.initialized()) 106 return NULL; 107 108 ThreadData* registry = static_cast<ThreadData*>(tls_index_.Get()); 109 if (!registry) { 110 // We have to create a new registry for ThreadData. 111 bool too_late_to_create = false; 112 { 113 registry = new ThreadData; 114 AutoLock lock(list_lock_); 115 // Use lock to insure we have most recent status. 116 if (!IsActive()) { 117 too_late_to_create = true; 118 } else { 119 // Use lock to insert into list. 120 registry->next_ = first_; 121 first_ = registry; 122 } 123 } // Release lock. 124 if (too_late_to_create) { 125 delete registry; 126 registry = NULL; 127 } else { 128 tls_index_.Set(registry); 129 } 130 } 131 return registry; 132} 133 134// Do mininimal fixups for searching function names. 135static std::string UnescapeQuery(const std::string& query) { 136 std::string result; 137 for (size_t i = 0; i < query.size(); i++) { 138 char next = query[i]; 139 if ('%' == next && i + 2 < query.size()) { 140 std::string hex = query.substr(i + 1, 2); 141 char replacement = '\0'; 142 // Only bother with "<", ">", and " ". 143 if (LowerCaseEqualsASCII(hex, "3c")) 144 replacement ='<'; 145 else if (LowerCaseEqualsASCII(hex, "3e")) 146 replacement = '>'; 147 else if (hex == "20") 148 replacement = ' '; 149 if (replacement) { 150 next = replacement; 151 i += 2; 152 } 153 } 154 result.push_back(next); 155 } 156 return result; 157} 158 159// static 160void ThreadData::WriteHTML(const std::string& query, std::string* output) { 161 if (!ThreadData::IsActive()) 162 return; // Not yet initialized. 163 164 DCHECK(ThreadData::current()); 165 166 output->append("<html><head><title>About Tasks"); 167 std::string escaped_query = UnescapeQuery(query); 168 if (!escaped_query.empty()) 169 output->append(" - " + escaped_query); 170 output->append("</title></head><body><pre>"); 171 172 DataCollector collected_data; // Gather data. 173 collected_data.AddListOfLivingObjects(); // Add births that are still alive. 174 175 // Data Gathering is complete. Now to sort/process/render. 176 DataCollector::Collection* collection = collected_data.collection(); 177 178 // Create filtering and sort comparison object. 179 Comparator comparator; 180 comparator.ParseQuery(escaped_query); 181 182 // Filter out acceptable (matching) instances. 183 DataCollector::Collection match_array; 184 for (DataCollector::Collection::iterator it = collection->begin(); 185 it != collection->end(); ++it) { 186 if (comparator.Acceptable(*it)) 187 match_array.push_back(*it); 188 } 189 190 comparator.Sort(&match_array); 191 192 WriteHTMLTotalAndSubtotals(match_array, comparator, output); 193 194 comparator.Clear(); // Delete tiebreaker_ instances. 195 196 output->append("</pre>"); 197 198 const char* help_string = "The following are the keywords that can be used to" 199 "sort and aggregate the data, or to select data.<br><ul>" 200 "<li><b>count</b> Number of instances seen." 201 "<li><b>duration</b> Duration in ms from construction to descrution." 202 "<li><b>birth</b> Thread on which the task was constructed." 203 "<li><b>death</b> Thread on which the task was run and deleted." 204 "<li><b>file</b> File in which the task was contructed." 205 "<li><b>function</b> Function in which the task was constructed." 206 "<li><b>line</b> Line number of the file in which the task was constructed." 207 "</ul><br>" 208 "As examples:<ul>" 209 "<li><b>about:tasks/file</b> would sort the above data by file, and" 210 " aggregate data on a per-file basis." 211 "<li><b>about:tasks/file=Dns</b> would only list data for tasks constructed" 212 " in a file containing the text |Dns|." 213 "<li><b>about:tasks/birth/death</b> would sort the above list by birth" 214 " thread, and then by death thread, and would aggregate data for each pair" 215 " of lifetime events." 216 "</ul>" 217 " The data can be reset to zero (discarding all births, deaths, etc.) using" 218 " <b>about:tasks/reset</b>. The existing stats will be displayed, but the" 219 " internal stats will be set to zero, and start accumulating afresh. This" 220 " option is very helpful if you only wish to consider tasks created after" 221 " some point in time.<br><br>" 222 "If you wish to monitor Renderer events, be sure to run in --single-process" 223 " mode."; 224 output->append(help_string); 225 output->append("</body></html>"); 226} 227 228// static 229void ThreadData::WriteHTMLTotalAndSubtotals( 230 const DataCollector::Collection& match_array, 231 const Comparator& comparator, 232 std::string* output) { 233 if (!match_array.size()) { 234 output->append("There were no tracked matches."); 235 } else { 236 // Aggregate during printing 237 Aggregation totals; 238 for (size_t i = 0; i < match_array.size(); ++i) { 239 totals.AddDeathSnapshot(match_array[i]); 240 } 241 output->append("Aggregate Stats: "); 242 totals.Write(output); 243 output->append("<hr><hr>"); 244 245 Aggregation subtotals; 246 for (size_t i = 0; i < match_array.size(); ++i) { 247 if (0 == i || !comparator.Equivalent(match_array[i - 1], 248 match_array[i])) { 249 // Print group's defining characteristics. 250 comparator.WriteSortGrouping(match_array[i], output); 251 output->append("<br><br>"); 252 } 253 comparator.WriteSnapshot(match_array[i], output); 254 output->append("<br>"); 255 subtotals.AddDeathSnapshot(match_array[i]); 256 if (i + 1 >= match_array.size() || 257 !comparator.Equivalent(match_array[i], 258 match_array[i + 1])) { 259 // Print aggregate stats for the group. 260 output->append("<br>"); 261 subtotals.Write(output); 262 output->append("<br><hr><br>"); 263 subtotals.Clear(); 264 } 265 } 266 } 267} 268 269Births* ThreadData::TallyABirth(const Location& location) { 270 { 271 // This shouldn't use the MessageLoop::current() LazyInstance since this 272 // might be used on a non-joinable thread. 273 // http://crbug.com/62728 274 base::ThreadRestrictions::ScopedAllowSingleton scoped_allow_singleton; 275 if (!message_loop_) // In case message loop wasn't yet around... 276 message_loop_ = MessageLoop::current(); // Find it now. 277 } 278 279 BirthMap::iterator it = birth_map_.find(location); 280 if (it != birth_map_.end()) { 281 it->second->RecordBirth(); 282 return it->second; 283 } 284 285 Births* tracker = new Births(location); 286 // Lock since the map may get relocated now, and other threads sometimes 287 // snapshot it (but they lock before copying it). 288 AutoLock lock(lock_); 289 birth_map_[location] = tracker; 290 return tracker; 291} 292 293void ThreadData::TallyADeath(const Births& lifetimes, 294 const TimeDelta& duration) { 295 { 296 // http://crbug.com/62728 297 base::ThreadRestrictions::ScopedAllowSingleton scoped_allow_singleton; 298 if (!message_loop_) // In case message loop wasn't yet around... 299 message_loop_ = MessageLoop::current(); // Find it now. 300 } 301 302 DeathMap::iterator it = death_map_.find(&lifetimes); 303 if (it != death_map_.end()) { 304 it->second.RecordDeath(duration); 305 return; 306 } 307 308 AutoLock lock(lock_); // Lock since the map may get relocated now. 309 death_map_[&lifetimes].RecordDeath(duration); 310} 311 312// static 313ThreadData* ThreadData::first() { 314 AutoLock lock(list_lock_); 315 return first_; 316} 317 318const std::string ThreadData::ThreadName() const { 319 if (message_loop_) 320 return message_loop_->thread_name(); 321 return "ThreadWithoutMessageLoop"; 322} 323 324// This may be called from another thread. 325void ThreadData::SnapshotBirthMap(BirthMap *output) const { 326 AutoLock lock(lock_); 327 for (BirthMap::const_iterator it = birth_map_.begin(); 328 it != birth_map_.end(); ++it) 329 (*output)[it->first] = it->second; 330} 331 332// This may be called from another thread. 333void ThreadData::SnapshotDeathMap(DeathMap *output) const { 334 AutoLock lock(lock_); 335 for (DeathMap::const_iterator it = death_map_.begin(); 336 it != death_map_.end(); ++it) 337 (*output)[it->first] = it->second; 338} 339 340// static 341void ThreadData::ResetAllThreadData() { 342 ThreadData* my_list = ThreadData::current()->first(); 343 344 for (ThreadData* thread_data = my_list; 345 thread_data; 346 thread_data = thread_data->next()) 347 thread_data->Reset(); 348} 349 350void ThreadData::Reset() { 351 AutoLock lock(lock_); 352 for (DeathMap::iterator it = death_map_.begin(); 353 it != death_map_.end(); ++it) 354 it->second.Clear(); 355 for (BirthMap::iterator it = birth_map_.begin(); 356 it != birth_map_.end(); ++it) 357 it->second->Clear(); 358} 359 360#ifdef OS_WIN 361// A class used to count down which is accessed by several threads. This is 362// used to make sure RunOnAllThreads() actually runs a task on the expected 363// count of threads. 364class ThreadData::ThreadSafeDownCounter { 365 public: 366 // Constructor sets the count, once and for all. 367 explicit ThreadSafeDownCounter(size_t count); 368 369 // Decrement the count, and return true if we hit zero. Also delete this 370 // instance automatically when we hit zero. 371 bool LastCaller(); 372 373 private: 374 size_t remaining_count_; 375 Lock lock_; // protect access to remaining_count_. 376}; 377 378ThreadData::ThreadSafeDownCounter::ThreadSafeDownCounter(size_t count) 379 : remaining_count_(count) { 380 DCHECK_GT(remaining_count_, 0u); 381} 382 383bool ThreadData::ThreadSafeDownCounter::LastCaller() { 384 { 385 AutoLock lock(lock_); 386 if (--remaining_count_) 387 return false; 388 } // Release lock, so we can delete everything in this instance. 389 delete this; 390 return true; 391} 392 393// A Task class that runs a static method supplied, and checks to see if this 394// is the last tasks instance (on last thread) that will run the method. 395// IF this is the last run, then the supplied event is signalled. 396class ThreadData::RunTheStatic : public Task { 397 public: 398 typedef void (*FunctionPointer)(); 399 RunTheStatic(FunctionPointer function, 400 HANDLE completion_handle, 401 ThreadSafeDownCounter* counter); 402 // Run the supplied static method, and optionally set the event. 403 void Run(); 404 405 private: 406 FunctionPointer function_; 407 HANDLE completion_handle_; 408 // Make sure enough tasks are called before completion is signaled. 409 ThreadSafeDownCounter* counter_; 410 411 DISALLOW_COPY_AND_ASSIGN(RunTheStatic); 412}; 413 414ThreadData::RunTheStatic::RunTheStatic(FunctionPointer function, 415 HANDLE completion_handle, 416 ThreadSafeDownCounter* counter) 417 : function_(function), 418 completion_handle_(completion_handle), 419 counter_(counter) { 420} 421 422void ThreadData::RunTheStatic::Run() { 423 function_(); 424 if (counter_->LastCaller()) 425 SetEvent(completion_handle_); 426} 427 428// TODO(jar): This should use condition variables, and be cross platform. 429void ThreadData::RunOnAllThreads(void (*function)()) { 430 ThreadData* list = first(); // Get existing list. 431 432 std::vector<MessageLoop*> message_loops; 433 for (ThreadData* it = list; it; it = it->next()) { 434 if (current() != it && it->message_loop()) 435 message_loops.push_back(it->message_loop()); 436 } 437 438 ThreadSafeDownCounter* counter = 439 new ThreadSafeDownCounter(message_loops.size() + 1); // Extra one for us! 440 441 HANDLE completion_handle = CreateEvent(NULL, false, false, NULL); 442 // Tell all other threads to run. 443 for (size_t i = 0; i < message_loops.size(); ++i) 444 message_loops[i]->PostTask( 445 FROM_HERE, new RunTheStatic(function, completion_handle, counter)); 446 447 // Also run Task on our thread. 448 RunTheStatic local_task(function, completion_handle, counter); 449 local_task.Run(); 450 451 WaitForSingleObject(completion_handle, INFINITE); 452 int ret_val = CloseHandle(completion_handle); 453 DCHECK(ret_val); 454} 455#endif 456 457// static 458bool ThreadData::StartTracking(bool status) { 459#ifndef TRACK_ALL_TASK_OBJECTS 460 return false; // Not compiled in. 461#endif 462 463 if (!status) { 464 AutoLock lock(list_lock_); 465 DCHECK(status_ == ACTIVE || status_ == SHUTDOWN); 466 status_ = SHUTDOWN; 467 return true; 468 } 469 AutoLock lock(list_lock_); 470 DCHECK(status_ == UNINITIALIZED); 471 CHECK(tls_index_.Initialize(NULL)); 472 status_ = ACTIVE; 473 return true; 474} 475 476// static 477bool ThreadData::IsActive() { 478 return status_ == ACTIVE; 479} 480 481#ifdef OS_WIN 482// static 483void ThreadData::ShutdownMultiThreadTracking() { 484 // Using lock, guarantee that no new ThreadData instances will be created. 485 if (!StartTracking(false)) 486 return; 487 488 RunOnAllThreads(ShutdownDisablingFurtherTracking); 489 490 // Now the *only* threads that might change the database are the threads with 491 // no messages loops. They might still be adding data to their birth records, 492 // but since no objects are deleted on those threads, there will be no further 493 // access to to cross-thread data. 494 // We could do a cleanup on all threads except for the ones without 495 // MessageLoops, but we won't bother doing cleanup (destruction of data) yet. 496 return; 497} 498#endif 499 500// static 501void ThreadData::ShutdownSingleThreadedCleanup() { 502 // We must be single threaded... but be careful anyway. 503 if (!StartTracking(false)) 504 return; 505 ThreadData* thread_data_list; 506 { 507 AutoLock lock(list_lock_); 508 thread_data_list = first_; 509 first_ = NULL; 510 } 511 512 while (thread_data_list) { 513 ThreadData* next_thread_data = thread_data_list; 514 thread_data_list = thread_data_list->next(); 515 516 for (BirthMap::iterator it = next_thread_data->birth_map_.begin(); 517 next_thread_data->birth_map_.end() != it; ++it) 518 delete it->second; // Delete the Birth Records. 519 next_thread_data->birth_map_.clear(); 520 next_thread_data->death_map_.clear(); 521 delete next_thread_data; // Includes all Death Records. 522 } 523 524 CHECK(tls_index_.initialized()); 525 tls_index_.Free(); 526 DCHECK(!tls_index_.initialized()); 527 status_ = UNINITIALIZED; 528} 529 530// static 531void ThreadData::ShutdownDisablingFurtherTracking() { 532 // Redundantly set status SHUTDOWN on this thread. 533 if (!StartTracking(false)) 534 return; 535} 536 537//------------------------------------------------------------------------------ 538// Individual 3-tuple of birth (place and thread) along with death thread, and 539// the accumulated stats for instances (DeathData). 540 541Snapshot::Snapshot(const BirthOnThread& birth_on_thread, 542 const ThreadData& death_thread, 543 const DeathData& death_data) 544 : birth_(&birth_on_thread), 545 death_thread_(&death_thread), 546 death_data_(death_data) { 547} 548 549Snapshot::Snapshot(const BirthOnThread& birth_on_thread, int count) 550 : birth_(&birth_on_thread), 551 death_thread_(NULL), 552 death_data_(DeathData(count)) { 553} 554 555const std::string Snapshot::DeathThreadName() const { 556 if (death_thread_) 557 return death_thread_->ThreadName(); 558 return "Still_Alive"; 559} 560 561void Snapshot::Write(std::string* output) const { 562 death_data_.Write(output); 563 base::StringAppendF(output, "%s->%s ", 564 birth_->birth_thread()->ThreadName().c_str(), 565 death_thread_->ThreadName().c_str()); 566 birth_->location().Write(true, true, output); 567} 568 569void Snapshot::Add(const Snapshot& other) { 570 death_data_.AddDeathData(other.death_data_); 571} 572 573//------------------------------------------------------------------------------ 574// DataCollector 575 576DataCollector::DataCollector() { 577 DCHECK(ThreadData::IsActive()); 578 579 // Get an unchanging copy of a ThreadData list. 580 ThreadData* my_list = ThreadData::current()->first(); 581 582 count_of_contributing_threads_ = 0; 583 for (ThreadData* thread_data = my_list; 584 thread_data; 585 thread_data = thread_data->next()) { 586 ++count_of_contributing_threads_; 587 } 588 589 // Gather data serially. A different constructor could be used to do in 590 // parallel, and then invoke an OnCompletion task. 591 // This hackish approach *can* get some slighly corrupt tallies, as we are 592 // grabbing values without the protection of a lock, but it has the advantage 593 // of working even with threads that don't have message loops. If a user 594 // sees any strangeness, they can always just run their stats gathering a 595 // second time. 596 // TODO(jar): Provide version that gathers stats safely via PostTask in all 597 // cases where thread_data supplies a message_loop to post to. Be careful to 598 // handle message_loops that are destroyed!?! 599 for (ThreadData* thread_data = my_list; 600 thread_data; 601 thread_data = thread_data->next()) { 602 Append(*thread_data); 603 } 604} 605 606DataCollector::~DataCollector() { 607} 608 609void DataCollector::Append(const ThreadData& thread_data) { 610 // Get copy of data (which is done under ThreadData's lock). 611 ThreadData::BirthMap birth_map; 612 thread_data.SnapshotBirthMap(&birth_map); 613 ThreadData::DeathMap death_map; 614 thread_data.SnapshotDeathMap(&death_map); 615 616 // Use our lock to protect our accumulation activity. 617 AutoLock lock(accumulation_lock_); 618 619 DCHECK(count_of_contributing_threads_); 620 621 for (ThreadData::DeathMap::const_iterator it = death_map.begin(); 622 it != death_map.end(); ++it) { 623 collection_.push_back(Snapshot(*it->first, thread_data, it->second)); 624 global_birth_count_[it->first] -= it->first->birth_count(); 625 } 626 627 for (ThreadData::BirthMap::const_iterator it = birth_map.begin(); 628 it != birth_map.end(); ++it) { 629 global_birth_count_[it->second] += it->second->birth_count(); 630 } 631 632 --count_of_contributing_threads_; 633} 634 635DataCollector::Collection* DataCollector::collection() { 636 DCHECK(!count_of_contributing_threads_); 637 return &collection_; 638} 639 640void DataCollector::AddListOfLivingObjects() { 641 DCHECK(!count_of_contributing_threads_); 642 for (BirthCount::iterator it = global_birth_count_.begin(); 643 it != global_birth_count_.end(); ++it) { 644 if (it->second > 0) 645 collection_.push_back(Snapshot(*it->first, it->second)); 646 } 647} 648 649//------------------------------------------------------------------------------ 650// Aggregation 651 652Aggregation::Aggregation() 653 : birth_count_(0) { 654} 655 656Aggregation::~Aggregation() { 657} 658 659void Aggregation::AddDeathSnapshot(const Snapshot& snapshot) { 660 AddBirth(snapshot.birth()); 661 death_threads_[snapshot.death_thread()]++; 662 AddDeathData(snapshot.death_data()); 663} 664 665void Aggregation::AddBirths(const Births& births) { 666 AddBirth(births); 667 birth_count_ += births.birth_count(); 668} 669void Aggregation::AddBirth(const BirthOnThread& birth) { 670 AddBirthPlace(birth.location()); 671 birth_threads_[birth.birth_thread()]++; 672} 673 674void Aggregation::AddBirthPlace(const Location& location) { 675 locations_[location]++; 676 birth_files_[location.file_name()]++; 677} 678 679void Aggregation::Write(std::string* output) const { 680 if (locations_.size() == 1) { 681 locations_.begin()->first.Write(true, true, output); 682 } else { 683 base::StringAppendF(output, "%" PRIuS " Locations. ", locations_.size()); 684 if (birth_files_.size() > 1) { 685 base::StringAppendF(output, "%" PRIuS " Files. ", birth_files_.size()); 686 } else { 687 base::StringAppendF(output, "All born in %s. ", 688 birth_files_.begin()->first.c_str()); 689 } 690 } 691 692 if (birth_threads_.size() > 1) { 693 base::StringAppendF(output, "%" PRIuS " BirthingThreads. ", 694 birth_threads_.size()); 695 } else { 696 base::StringAppendF(output, "All born on %s. ", 697 birth_threads_.begin()->first->ThreadName().c_str()); 698 } 699 700 if (death_threads_.size() > 1) { 701 base::StringAppendF(output, "%" PRIuS " DeathThreads. ", 702 death_threads_.size()); 703 } else { 704 if (death_threads_.begin()->first) { 705 base::StringAppendF(output, "All deleted on %s. ", 706 death_threads_.begin()->first->ThreadName().c_str()); 707 } else { 708 output->append("All these objects are still alive."); 709 } 710 } 711 712 if (birth_count_ > 1) 713 base::StringAppendF(output, "Births=%d ", birth_count_); 714 715 DeathData::Write(output); 716} 717 718void Aggregation::Clear() { 719 birth_count_ = 0; 720 birth_files_.clear(); 721 locations_.clear(); 722 birth_threads_.clear(); 723 DeathData::Clear(); 724 death_threads_.clear(); 725} 726 727//------------------------------------------------------------------------------ 728// Comparison object for sorting. 729 730Comparator::Comparator() 731 : selector_(NIL), 732 tiebreaker_(NULL), 733 combined_selectors_(0), 734 use_tiebreaker_for_sort_only_(false) {} 735 736void Comparator::Clear() { 737 if (tiebreaker_) { 738 tiebreaker_->Clear(); 739 delete tiebreaker_; 740 tiebreaker_ = NULL; 741 } 742 use_tiebreaker_for_sort_only_ = false; 743 selector_ = NIL; 744} 745 746void Comparator::Sort(DataCollector::Collection* collection) const { 747 std::sort(collection->begin(), collection->end(), *this); 748} 749 750 751bool Comparator::operator()(const Snapshot& left, 752 const Snapshot& right) const { 753 switch (selector_) { 754 case BIRTH_THREAD: 755 if (left.birth_thread() != right.birth_thread() && 756 left.birth_thread()->ThreadName() != 757 right.birth_thread()->ThreadName()) 758 return left.birth_thread()->ThreadName() < 759 right.birth_thread()->ThreadName(); 760 break; 761 762 case DEATH_THREAD: 763 if (left.death_thread() != right.death_thread() && 764 left.DeathThreadName() != 765 right.DeathThreadName()) { 766 if (!left.death_thread()) 767 return true; 768 if (!right.death_thread()) 769 return false; 770 return left.DeathThreadName() < 771 right.DeathThreadName(); 772 } 773 break; 774 775 case BIRTH_FILE: 776 if (left.location().file_name() != right.location().file_name()) { 777 int comp = strcmp(left.location().file_name(), 778 right.location().file_name()); 779 if (comp) 780 return 0 > comp; 781 } 782 break; 783 784 case BIRTH_FUNCTION: 785 if (left.location().function_name() != right.location().function_name()) { 786 int comp = strcmp(left.location().function_name(), 787 right.location().function_name()); 788 if (comp) 789 return 0 > comp; 790 } 791 break; 792 793 case BIRTH_LINE: 794 if (left.location().line_number() != right.location().line_number()) 795 return left.location().line_number() < 796 right.location().line_number(); 797 break; 798 799 case COUNT: 800 if (left.count() != right.count()) 801 return left.count() > right.count(); // Sort large at front of vector. 802 break; 803 804 case AVERAGE_DURATION: 805 if (!left.count() || !right.count()) 806 break; 807 if (left.AverageMsDuration() != right.AverageMsDuration()) 808 return left.AverageMsDuration() > right.AverageMsDuration(); 809 break; 810 811 default: 812 break; 813 } 814 if (tiebreaker_) 815 return tiebreaker_->operator()(left, right); 816 return false; 817} 818 819bool Comparator::Equivalent(const Snapshot& left, 820 const Snapshot& right) const { 821 switch (selector_) { 822 case BIRTH_THREAD: 823 if (left.birth_thread() != right.birth_thread() && 824 left.birth_thread()->ThreadName() != 825 right.birth_thread()->ThreadName()) 826 return false; 827 break; 828 829 case DEATH_THREAD: 830 if (left.death_thread() != right.death_thread() && 831 left.DeathThreadName() != right.DeathThreadName()) 832 return false; 833 break; 834 835 case BIRTH_FILE: 836 if (left.location().file_name() != right.location().file_name()) { 837 int comp = strcmp(left.location().file_name(), 838 right.location().file_name()); 839 if (comp) 840 return false; 841 } 842 break; 843 844 case BIRTH_FUNCTION: 845 if (left.location().function_name() != right.location().function_name()) { 846 int comp = strcmp(left.location().function_name(), 847 right.location().function_name()); 848 if (comp) 849 return false; 850 } 851 break; 852 853 case COUNT: 854 if (left.count() != right.count()) 855 return false; 856 break; 857 858 case AVERAGE_DURATION: 859 if (left.life_duration() != right.life_duration()) 860 return false; 861 break; 862 863 default: 864 break; 865 } 866 if (tiebreaker_ && !use_tiebreaker_for_sort_only_) 867 return tiebreaker_->Equivalent(left, right); 868 return true; 869} 870 871bool Comparator::Acceptable(const Snapshot& sample) const { 872 if (required_.size()) { 873 switch (selector_) { 874 case BIRTH_THREAD: 875 if (sample.birth_thread()->ThreadName().find(required_) == 876 std::string::npos) 877 return false; 878 break; 879 880 case DEATH_THREAD: 881 if (sample.DeathThreadName().find(required_) == std::string::npos) 882 return false; 883 break; 884 885 case BIRTH_FILE: 886 if (!strstr(sample.location().file_name(), required_.c_str())) 887 return false; 888 break; 889 890 case BIRTH_FUNCTION: 891 if (!strstr(sample.location().function_name(), required_.c_str())) 892 return false; 893 break; 894 895 default: 896 break; 897 } 898 } 899 if (tiebreaker_ && !use_tiebreaker_for_sort_only_) 900 return tiebreaker_->Acceptable(sample); 901 return true; 902} 903 904void Comparator::SetTiebreaker(Selector selector, const std::string& required) { 905 if (selector == selector_ || NIL == selector) 906 return; 907 combined_selectors_ |= selector; 908 if (NIL == selector_) { 909 selector_ = selector; 910 if (required.size()) 911 required_ = required; 912 return; 913 } 914 if (tiebreaker_) { 915 if (use_tiebreaker_for_sort_only_) { 916 Comparator* temp = new Comparator; 917 temp->tiebreaker_ = tiebreaker_; 918 tiebreaker_ = temp; 919 } 920 } else { 921 tiebreaker_ = new Comparator; 922 DCHECK(!use_tiebreaker_for_sort_only_); 923 } 924 tiebreaker_->SetTiebreaker(selector, required); 925} 926 927bool Comparator::IsGroupedBy(Selector selector) const { 928 return 0 != (selector & combined_selectors_); 929} 930 931void Comparator::SetSubgroupTiebreaker(Selector selector) { 932 if (selector == selector_ || NIL == selector) 933 return; 934 if (!tiebreaker_) { 935 use_tiebreaker_for_sort_only_ = true; 936 tiebreaker_ = new Comparator; 937 tiebreaker_->SetTiebreaker(selector, ""); 938 } else { 939 tiebreaker_->SetSubgroupTiebreaker(selector); 940 } 941} 942 943void Comparator::ParseKeyphrase(const std::string& key_phrase) { 944 typedef std::map<const std::string, Selector> KeyMap; 945 static KeyMap key_map; 946 static bool initialized = false; 947 if (!initialized) { 948 initialized = true; 949 // Sorting and aggretation keywords, which specify how to sort the data, or 950 // can specify a required match from the specified field in the record. 951 key_map["count"] = COUNT; 952 key_map["duration"] = AVERAGE_DURATION; 953 key_map["birth"] = BIRTH_THREAD; 954 key_map["death"] = DEATH_THREAD; 955 key_map["file"] = BIRTH_FILE; 956 key_map["function"] = BIRTH_FUNCTION; 957 key_map["line"] = BIRTH_LINE; 958 959 // Immediate commands that do not involve setting sort order. 960 key_map["reset"] = RESET_ALL_DATA; 961 } 962 963 std::string required; 964 // Watch for: "sort_key=value" as we parse. 965 size_t equal_offset = key_phrase.find('=', 0); 966 if (key_phrase.npos != equal_offset) { 967 // There is a value that must be matched for the data to display. 968 required = key_phrase.substr(equal_offset + 1, key_phrase.npos); 969 } 970 std::string keyword(key_phrase.substr(0, equal_offset)); 971 keyword = StringToLowerASCII(keyword); 972 KeyMap::iterator it = key_map.find(keyword); 973 if (key_map.end() == it) 974 return; // Unknown keyword. 975 if (it->second == RESET_ALL_DATA) 976 ThreadData::ResetAllThreadData(); 977 else 978 SetTiebreaker(key_map[keyword], required); 979} 980 981bool Comparator::ParseQuery(const std::string& query) { 982 // Parse each keyphrase between consecutive slashes. 983 for (size_t i = 0; i < query.size();) { 984 size_t slash_offset = query.find('/', i); 985 ParseKeyphrase(query.substr(i, slash_offset - i)); 986 if (query.npos == slash_offset) 987 break; 988 i = slash_offset + 1; 989 } 990 991 // Select subgroup ordering (if we want to display the subgroup) 992 SetSubgroupTiebreaker(COUNT); 993 SetSubgroupTiebreaker(AVERAGE_DURATION); 994 SetSubgroupTiebreaker(BIRTH_THREAD); 995 SetSubgroupTiebreaker(DEATH_THREAD); 996 SetSubgroupTiebreaker(BIRTH_FUNCTION); 997 SetSubgroupTiebreaker(BIRTH_FILE); 998 SetSubgroupTiebreaker(BIRTH_LINE); 999 1000 return true; 1001} 1002 1003bool Comparator::WriteSortGrouping(const Snapshot& sample, 1004 std::string* output) const { 1005 bool wrote_data = false; 1006 switch (selector_) { 1007 case BIRTH_THREAD: 1008 base::StringAppendF(output, "All new on %s ", 1009 sample.birth_thread()->ThreadName().c_str()); 1010 wrote_data = true; 1011 break; 1012 1013 case DEATH_THREAD: 1014 if (sample.death_thread()) { 1015 base::StringAppendF(output, "All deleted on %s ", 1016 sample.DeathThreadName().c_str()); 1017 } else { 1018 output->append("All still alive "); 1019 } 1020 wrote_data = true; 1021 break; 1022 1023 case BIRTH_FILE: 1024 base::StringAppendF(output, "All born in %s ", 1025 sample.location().file_name()); 1026 break; 1027 1028 case BIRTH_FUNCTION: 1029 output->append("All born in "); 1030 sample.location().WriteFunctionName(output); 1031 output->push_back(' '); 1032 break; 1033 1034 default: 1035 break; 1036 } 1037 if (tiebreaker_ && !use_tiebreaker_for_sort_only_) { 1038 wrote_data |= tiebreaker_->WriteSortGrouping(sample, output); 1039 } 1040 return wrote_data; 1041} 1042 1043void Comparator::WriteSnapshot(const Snapshot& sample, 1044 std::string* output) const { 1045 sample.death_data().Write(output); 1046 if (!(combined_selectors_ & BIRTH_THREAD) || 1047 !(combined_selectors_ & DEATH_THREAD)) 1048 base::StringAppendF(output, "%s->%s ", 1049 (combined_selectors_ & BIRTH_THREAD) ? "*" : 1050 sample.birth().birth_thread()->ThreadName().c_str(), 1051 (combined_selectors_ & DEATH_THREAD) ? "*" : 1052 sample.DeathThreadName().c_str()); 1053 sample.birth().location().Write(!(combined_selectors_ & BIRTH_FILE), 1054 !(combined_selectors_ & BIRTH_FUNCTION), 1055 output); 1056} 1057 1058} // namespace tracked_objects 1059