blob: 1934afba47b90a1e9a18e6ed133c9cccc533f06c [file] [log] [blame]
// 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_