// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef BASE_TRACKED_OBJECTS_H_
#define BASE_TRACKED_OBJECTS_H_

#include <map>
#include <string>
#include <vector>

#include "base/lock.h"
#include "base/task.h"
#include "base/thread_local_storage.h"
#include "base/tracked.h"

class MessageLoop;

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_COPY_AND_ASSIGN(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_COPY_AND_ASSIGN(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 base::TimeDelta& duration);

  // Metrics accessors.
  int count() const { return count_; }
  base::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.
  base::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(); }
  base::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 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<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_COPY_AND_ASSIGN(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_COPY_AND_ASSIGN(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 base::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();

#ifdef OS_WIN
  // 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();
#endif

  // 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_.
  };

#ifdef OS_WIN
  // 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_COPY_AND_ASSIGN(RunTheStatic);
  };
#endif

  // 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_COPY_AND_ASSIGN(ThreadData);
};


//------------------------------------------------------------------------------
// Provide simple way to to start global tracking, and to tear down tracking
// when done.  Note that construction and destruction of this object must be
// done when running in single threaded mode (before spawning a lot of threads
// for construction, and after shutting down all the threads for destruction).

class AutoTracking {
 public:
  AutoTracking() { ThreadData::StartTracking(true); }

  ~AutoTracking() {
#ifndef NDEBUG  // Don't call these in a Release build: they just waste time.
    // The following should ONLY be called when in single threaded mode. It is
    // unsafe to do this cleanup if other threads are still active.
    // It is also very unnecessary, so I'm only doing this in debug to satisfy
    // purify (if we need to!).
    ThreadData::ShutdownSingleThreadedCleanup();
#endif
  }

 private:
  DISALLOW_COPY_AND_ASSIGN(AutoTracking);
};


}  // namespace tracked_objects

#endif  // BASE_TRACKED_OBJECTS_H_