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