Add base to the repository.

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@8 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 509 insertions, 0 deletions

diff --git a/base/tracked_objects.h b/base/tracked_objects.h
new file mode 100644
index 0000000..23638e1
--- /dev/null
+++ b/base/tracked_objects.h
@@ -0,0 +1,509 @@
+// Copyright 2008, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//    * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//    * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//    * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#ifndef BASE_TRACKED_OBJECTS_H_
+#define BASE_TRACKED_OBJECTS_H_
+
+//------------------------------------------------------------------------------
+#include <map>
+#include <string>
+#include <vector>
+
+#include "base/lock.h"
+#include "base/message_loop.h"
+#include "base/thread_local_storage.h"
+#include "base/tracked.h"
+
+
+namespace tracked_objects {
+
+//------------------------------------------------------------------------------
+// For a specific thread, and a specific birth place, the collection of all
+// death info (with tallies for each death thread, to prevent access conflicts).
+class ThreadData;
+class BirthOnThread {
+ public:
+  explicit BirthOnThread(const Location& location);
+
+  const Location location() const { return location_; }
+  const ThreadData* birth_thread() const { return birth_thread_; }
+
+ private:
+  // File/lineno of birth.  This defines the essence of the type, as the context
+  // of the birth (construction) often tell what the item is for.  This field
+  // is const, and hence safe to access from any thread.
+  const Location location_;
+
+  // The thread that records births into this object.  Only this thread is
+  // allowed to access birth_count_ (which changes over time).
+  const ThreadData* birth_thread_;  // The thread this birth took place on.
+
+  DISALLOW_EVIL_CONSTRUCTORS(BirthOnThread);
+};
+
+//------------------------------------------------------------------------------
+// A class for accumulating counts of births (without bothering with a map<>).
+
+class Births: public BirthOnThread {
+ public:
+  explicit Births(const Location& location);
+
+  int birth_count() const { return birth_count_; }
+
+  // When we have a birth we update the count for this BirhPLace.
+  void RecordBirth() { ++birth_count_; }
+
+  // When a birthplace is changed (updated), we need to decrement the counter
+  // for the old instance.
+  void ForgetBirth() { --birth_count_; }  // We corrected a birth place.
+
+ private:
+  // The number of births on this thread for our location_.
+  int birth_count_;
+
+  DISALLOW_EVIL_CONSTRUCTORS(Births);
+};
+
+//------------------------------------------------------------------------------
+// Basic info summarizing multiple destructions of an object with a single
+// birthplace (fixed Location).  Used both on specific threads, and also used
+// in snapshots when integrating assembled data.
+
+class DeathData {
+ public:
+  // Default initializer.
+  DeathData() : count_(0), square_duration_(0) {}
+
+  // When deaths have not yet taken place, and we gather data from all the
+  // threads, we create DeathData stats that tally the number of births without
+  // a corrosponding death.
+  explicit DeathData(int count) : count_(count), square_duration_(0) {}
+
+  void RecordDeath(const TimeDelta& duration);
+
+  // Metrics accessors.
+  int count() const { return count_; }
+  TimeDelta life_duration() const { return life_duration_; }
+  int64 square_duration() const { return square_duration_; }
+  int AverageMsDuration() const;
+  double StandardDeviation() const;
+
+  // Accumulate metrics from other into this.
+  void AddDeathData(const DeathData& other);
+
+  // Simple print of internal state.
+  void Write(std::string* output) const;
+
+  void Clear();
+
+ private:
+  int count_;                // Number of destructions.
+  TimeDelta life_duration_;    // Sum of all lifetime durations.
+  int64 square_duration_;  // Sum of squares in milliseconds.
+};
+
+//------------------------------------------------------------------------------
+// A temporary collection of data that can be sorted and summarized.  It is
+// gathered (carefully) from many threads.  Instances are held in arrays and
+// processed, filtered, and rendered.
+// The source of this data was collected on many threads, and is asynchronously
+// changing.  The data in this instance is not asynchronously changing.
+
+class Snapshot {
+ public:
+  // When snapshotting a full life cycle set (birth-to-death), use this:
+  Snapshot(const BirthOnThread& birth_on_thread, const ThreadData& death_thread,
+           const DeathData& death_data);
+
+  // When snapshotting a birth, with no death yet, use this:
+  Snapshot(const BirthOnThread& birth_on_thread, int count);
+
+
+  const ThreadData* birth_thread() const { return birth_->birth_thread(); }
+  const Location location() const { return birth_->location(); }
+  const BirthOnThread& birth() const { return *birth_; }
+  const ThreadData* death_thread() const {return death_thread_; }
+  const DeathData& death_data() const { return death_data_; }
+  const std::string DeathThreadName() const;
+
+  int count() const { return death_data_.count(); }
+  TimeDelta life_duration() const { return death_data_.life_duration(); }
+  int64 square_duration() const { return death_data_.square_duration(); }
+  int AverageMsDuration() const { return death_data_.AverageMsDuration(); }
+
+  void Snapshot::Write(std::string* output) const;
+
+  void Add(const Snapshot& other);
+
+ private:
+  const BirthOnThread* birth_;  // Includes Location and birth_thread.
+  const ThreadData* death_thread_;
+  DeathData death_data_;
+};
+//------------------------------------------------------------------------------
+// DataCollector is a container class for Snapshot and BirthOnThread count
+// items.  It protects the gathering under locks, so that it could be called via
+// Posttask on any threads, such as all the target threads in parallel.
+
+class DataCollector {
+ public:
+  typedef std::vector<const Snapshot> Collection;
+
+  // Construct with a list of how many threads should contribute.  This helps us
+  // determine (in the async case) when we are done with all contributions.
+  DataCollector();
+
+  // Add all stats from the indicated thread into our arrays.  This function is
+  // mutex protected, and *could* be called from any threads (although current
+  // implementation serialized calls to Append).
+  void Append(const ThreadData& thread_data);
+
+  // After the accumulation phase, the following access is to process data.
+  Collection* collection();
+
+  // After collection of death data is complete, we can add entries for all the
+  // remaining living objects.
+  void AddListOfLivingObjects();
+
+ private:
+  // This instance may be provided to several threads to contribute data.  The
+  // following counter tracks how many more threads will contribute.  When it is
+  // zero, then all asynchronous contributions are complete, and locked access
+  // is no longer needed.
+  int count_of_contributing_threads_;
+
+  // The array that we collect data into.
+  Collection collection_;
+
+  // The total number of births recorded at each location for which we have not
+  // seen a death count.
+  typedef std::map<const BirthOnThread*, int> BirthCount;
+  BirthCount global_birth_count_;
+
+  Lock accumulation_lock_;  // Protects access during accumulation phase.
+
+  DISALLOW_EVIL_CONSTRUCTORS(DataCollector);
+};
+
+//------------------------------------------------------------------------------
+// Aggregation contains summaries (totals and subtotals) of groups of Snapshot
+// instances to provide printing of these collections on a single line.
+
+class Aggregation: public DeathData {
+ public:
+  Aggregation() : birth_count_(0) {}
+
+  void AddDeathSnapshot(const Snapshot& snapshot);
+  void AddBirths(const Births& births);
+  void AddBirth(const BirthOnThread& birth);
+  void AddBirthPlace(const Location& location);
+  void Write(std::string* output) const;
+  void Clear();
+
+ private:
+  int birth_count_;
+  std::map<std::string, int> birth_files_;
+  std::map<Location, int> locations_;
+  std::map<const ThreadData*, int> birth_threads_;
+  DeathData death_data_;
+  std::map<const ThreadData*, int> death_threads_;
+
+  DISALLOW_EVIL_CONSTRUCTORS(Aggregation);
+};
+
+//------------------------------------------------------------------------------
+// Comparator does the comparison of Snapshot instances.  It is
+// used to order the instances in a vector.  It orders them into groups (for
+// aggregation), and can also order instances within the groups (for detailed
+// rendering of the instances).
+
+class Comparator {
+ public:
+  enum Selector {
+    NIL = 0,
+    BIRTH_THREAD = 1,
+    DEATH_THREAD = 2,
+    BIRTH_FILE = 4,
+    BIRTH_FUNCTION = 8,
+    BIRTH_LINE = 16,
+    COUNT = 32,
+    AVERAGE_DURATION = 64,
+    TOTAL_DURATION = 128,
+  };
+
+  explicit Comparator();
+
+  // Reset the comparator to a NIL selector.  Reset() and recursively delete any
+  // tiebreaker_ entries.  NOTE: We can't use a standard destructor, because
+  // the sort algorithm makes copies of this object, and then deletes them,
+  // which would cause problems (either we'd make expensive deep copies, or we'd
+  // do more thna one delete on a tiebreaker_.
+  void Clear();
+
+  // The less() operator for sorting the array via std::sort().
+  bool operator()(const Snapshot& left, const Snapshot& right) const;
+
+  void Sort(DataCollector::Collection* collection) const;
+
+  // Check to see if the items are sort equivalents (should be aggregated).
+  bool Equivalent(const Snapshot& left, const Snapshot& right) const;
+
+  // Check to see if all required fields are present in the given sample.
+  bool Acceptable(const Snapshot& sample) const;
+
+  // A comparator can be refined by specifying what to do if the selected basis
+  // for comparison is insufficient to establish an ordering.  This call adds
+  // the indicated attribute as the new "least significant" basis of comparison.
+  void SetTiebreaker(Selector selector, const std::string required);
+
+  // Indicate if this instance is set up to sort by the given Selector, thereby
+  // putting that information in the SortGrouping, so it is not needed in each
+  // printed line.
+  bool IsGroupedBy(Selector selector) const;
+
+  // Using the tiebreakers as set above, we mostly get an ordering, which
+  // equivalent groups.  If those groups are displayed (rather than just being
+  // aggregated, then the following is used to order them (within the group).
+  void SetSubgroupTiebreaker(Selector selector);
+
+  // Translate a keyword and restriction in URL path to a selector for sorting.
+  void ParseKeyphrase(const std::string key_phrase);
+
+  // Parse a query in an about:objects URL to decide on sort ordering.
+  bool ParseQuery(const std::string query);
+
+  // Output a header line that can be used to indicated what items will be
+  // collected in the group.  It lists all (potentially) tested attributes and
+  // their values (in the sample item).
+  bool WriteSortGrouping(const Snapshot& sample, std::string* output) const;
+
+  // Output a sample, with SortGroup details not displayed.
+  void WriteSnapshot(const Snapshot& sample, std::string* output) const;
+
+ private:
+  // The selector directs this instance to compare based on the specified
+  // members of the tested elements.
+  enum Selector selector_;
+
+  // For filtering into acceptable and unacceptable snapshot instance, the
+  // following is required to be a substring of the selector_ field.
+  std::string required_;
+
+  // If this instance can't decide on an ordering, we can consult a tie-breaker
+  // which may have a different basis of comparison.
+  Comparator* tiebreaker_;
+
+  // We or together all the selectors we sort on (not counting sub-group
+  // selectors), so that we can tell if we've decided to group on any given
+  // criteria.
+  int combined_selectors_;
+
+  // Some tiebreakrs are for subgroup ordering, and not for basic ordering (in
+  // preparation for aggregation).  The subgroup tiebreakers are not consulted
+  // when deciding if two items are in equivalent groups.  This flag tells us
+  // to ignore the tiebreaker when doing Equivalent() testing.
+  bool use_tiebreaker_for_sort_only_;
+};
+
+
+//------------------------------------------------------------------------------
+// For each thread, we have a ThreadData that stores all tracking info generated
+// on this thread.  This prevents the need for locking as data accumulates.
+
+class ThreadData {
+ public:
+  typedef std::map<Location, Births*> BirthMap;
+  typedef std::map<const Births*, DeathData> DeathMap;
+
+  ThreadData();
+
+  // Using Thread Local Store, find the current instance for collecting data.
+  // If an instance does not exist, construct one (and remember it for use on
+  // this thread.
+  // If shutdown has already started, and we don't yet have an instance, then
+  // return null.
+  static ThreadData* current();
+
+  // For a given about:objects URL, develop resulting HTML, and append to
+  // output.
+  static void WriteHTML(const std::string& query, std::string* output);
+
+  // For a given accumulated array of results, use the comparator to sort and
+  // subtotal, writing the results to the output.
+  static void WriteHTMLTotalAndSubtotals(
+      const DataCollector::Collection& match_array,
+      const Comparator& comparator, std::string* output);
+
+  // In this thread's data, find a place to record a new birth.
+  Births* FindLifetime(const Location& location);
+
+  // Find a place to record a death on this thread.
+  void TallyADeath(const Births& lifetimes, const TimeDelta& duration);
+
+  // (Thread safe) Get start of list of instances.
+  static ThreadData* first();
+  // Iterate through the null terminated list of instances.
+  ThreadData* next() const { return next_; }
+
+  MessageLoop* message_loop() const { return message_loop_; }
+  const std::string ThreadName() const;
+
+  // Using our lock, make a copy of the specified maps.  These calls may arrive
+  // from non-local threads.
+  void SnapshotBirthMap(BirthMap *output) const;
+  void SnapshotDeathMap(DeathMap *output) const;
+
+  static void RunOnAllThreads(void (*Func)());
+
+  // Set internal status_ to either become ACTIVE, or later, to be SHUTDOWN,
+  // based on argument being true or false respectively.
+  // IF tracking is not compiled in, this function will return false.
+  static bool StartTracking(bool status);
+  static bool IsActive();
+
+  // WARNING: ONLY call this function when all MessageLoops are still intact for
+  // all registered threads.  IF you call it later, you will crash.
+  // Note: You don't need to call it at all, and you can wait till you are
+  // single threaded (again) to do the cleanup via
+  // ShutdownSingleThreadedCleanup().
+  // Start the teardown (shutdown) process in a multi-thread mode by disabling
+  // further additions to thread database on all threads.  First it makes a
+  // local (locked) change to prevent any more threads from registering.  Then
+  // it Posts a Task to all registered threads to be sure they are aware that no
+  // more accumulation can take place.
+  static void ShutdownMultiThreadTracking();
+
+  // WARNING: ONLY call this function when you are running single threaded
+  // (again) and all message loops and threads have terminated.  Until that
+  // point some threads may still attempt to write into our data structures.
+  // Delete recursively all data structures, starting with the list of
+  // ThreadData instances.
+  static void ShutdownSingleThreadedCleanup();
+
+ private:
+  // Current allowable states of the tracking system.  The states always
+  // proceed towards SHUTDOWN, and never go backwards.
+  enum Status {
+    UNINITIALIZED,
+    ACTIVE,
+    SHUTDOWN,
+  };
+
+  // A class used to count down which is accessed by several threads.  This is
+  // used to make sure RunOnAllThreads() actually runs a task on the expected
+  // count of threads.
+  class ThreadSafeDownCounter {
+   public:
+    // Constructor sets the count, once and for all.
+    explicit ThreadSafeDownCounter(size_t count);
+
+    // Decrement the count, and return true if we hit zero.  Also delete this
+    // instance automatically when we hit zero.
+    bool LastCaller();
+
+   private:
+    size_t remaining_count_;
+    Lock lock_;  // protect access to remaining_count_.
+  };
+
+  // A Task class that runs a static method supplied, and checks to see if this
+  // is the last tasks instance (on last thread) that will run the method.
+  // IF this is the last run, then the supplied event is signalled.
+  class RunTheStatic : public Task {
+   public:
+    typedef void (*FunctionPointer)();
+    RunTheStatic(FunctionPointer function,
+                 HANDLE completion_handle,
+                 ThreadSafeDownCounter* counter);
+    // Run the supplied static method, and optionally set the event.
+    void Run();
+
+   private:
+    FunctionPointer function_;
+    HANDLE completion_handle_;
+    // Make sure enough tasks are called before completion is signaled.
+    ThreadSafeDownCounter* counter_;
+
+    DISALLOW_EVIL_CONSTRUCTORS(RunTheStatic);
+  };
+
+  // Each registered thread is called to set status_ to SHUTDOWN.
+  // This is done redundantly on every registered thread because it is not
+  // protected by a mutex.  Running on all threads guarantees we get the
+  // notification into the memory cache of all possible threads.
+  static void ShutdownDisablingFurtherTracking();
+
+  // We use thread local store to identify which ThreadData to interact with.
+  static TLSSlot tls_index_ ;
+
+  // Link to the most recently created instance (starts a null terminated list).
+  static ThreadData* first_;
+  // Protection for access to first_.
+  static Lock list_lock_;
+
+
+  // We set status_ to SHUTDOWN when we shut down the tracking service. This
+  // setting is redundantly established by all participating
+  // threads so that we are *guaranteed* (without locking) that all threads
+  // can "see" the status and avoid additional calls into the  service.
+  static Status status_;
+
+  // Link to next instance (null terminated list). Used to globally track all
+  // registered instances (corresponds to all registered threads where we keep
+  // data).
+  ThreadData* next_;
+
+  // The message loop where tasks needing to access this instance's private data
+  // should be directed.  Since some threads have no message loop, some
+  // instances have data that can't be (safely) modified externally.
+  MessageLoop* message_loop_;
+
+  // A map used on each thread to keep track of Births on this thread.
+  // This map should only be accessed on the thread it was constructed on.
+  // When a snapshot is needed, this structure can be locked in place for the
+  // duration of the snapshotting activity.
+  BirthMap birth_map_;
+
+  // Similar to birth_map_, this records informations about death of tracked
+  // instances (i.e., when a tracked instance was destroyed on this thread).
+  DeathMap death_map_;
+
+  // Lock to protect *some* access to BirthMap and DeathMap.  We only use
+  // locking protection when we are growing the maps, or using an iterator.  We
+  // only do writes to members from this thread, so the updates of values are
+  // atomic.  Folks can read from other threads, and get (via races) new or old
+  // data, but that is considered acceptable errors (mis-information).
+  Lock lock_;
+
+  DISALLOW_EVIL_CONSTRUCTORS(ThreadData);
+};
+
+}  // namespace tracked_objects
+
+#endif  // BASE_TRACKED_OBJECTS_H_