tracked_objects.cc revision 3f50c38dc070f4bb515c1b64450dae14f316474e 
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/threading/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
21base::ThreadLocalStorage::Slot 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