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