base/tracked_objects.cc

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