The Tor Browser: tools/trace-malloc/spacetrace.h@ac0c01689b40 (annotated)

tools/trace-malloc/spacetrace.h@ac0c01689b40 (annotated)

tools/trace-malloc/spacetrace.h

Thu, 15 Jan 2015 15:59:08 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Thu, 15 Jan 2015 15:59:08 +0100
branch: TOR_BUG_9701
changeset 10: ac0c01689b40
permissions: -rw-r--r--

Implement a real Private Browsing Mode condition by changing the API/ABI;
This solves Tor bug #9701, complying with disk avoidance documented in
https://www.torproject.org/projects/torbrowser/design/#disk-avoidance.

 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  *
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 #ifndef spacetrace_h__
 #define spacetrace_h__
 /*
 ** spacetrace.h
 **
 ** SpaceTrace is meant to take the output of trace-malloc and present
 **   a picture of allocations over the run of the application.
 */
 /*
 ** Required includes.
 */
 #include <stdint.h>
 #include "nspr.h"
 #include "prlock.h"
 #include "prrwlock.h"
 #include "nsTraceMalloc.h"
 #include "tmreader.h"
 #include "formdata.h"
 /*
 ** Turn on to attempt adding support for graphs on your platform.
 */
 #if defined(HAVE_BOUTELL_GD)
 #define ST_WANT_GRAPHS 1
 #endif /* HAVE_BOUTELL_GD */
 #if !defined(ST_WANT_GRAPHS)
 #define ST_WANT_GRAPHS 0
 #endif
 /*
 ** REPORT_ERROR
 ** REPORT_INFO
 **
 ** Just report errors and stuff in a consistent manner.
 */
 #define REPORT_ERROR(code, function) \
         PR_fprintf(PR_STDERR, "error(%d):\t%s\n", code, #function)
 #define REPORT_ERROR_MSG(code, msg) \
         PR_fprintf(PR_STDERR, "error(%d):\t%s\n", code, msg)
 #define REPORT_INFO(msg) \
         PR_fprintf(PR_STDOUT, "%s: %s\n", globals.mProgramName, (msg))
 #if defined(DEBUG_blythe) && 1
 #define REPORT_blythe(code, msg) \
         PR_fprintf(PR_STDOUT, "gab(%d):\t%s\n", code, msg)
 #else
 #define REPORT_blythe(code, msg)
 #endif /* DEBUG_blythe */
 /*
 ** CALLSITE_RUN
 **
 ** How to get a callsite run.
 ** Allows for further indirection if needed later.
 */
 #define CALLSITE_RUN(callsite) \
         ((STRun*)((callsite)->data))
 /*
 ** ST_PERMS
 ** ST_FLAGS
 **
 ** File permissions we desire.
 ** 0644
 */
 #define ST_PERMS (PR_IRUSR | PR_IWUSR | PR_IRGRP | PR_IROTH)
 #define ST_FLAGS (PR_WRONLY | PR_CREATE_FILE | PR_TRUNCATE)
 /*
 ** Sorting order
 */
 #define ST_WEIGHT   0 /* size * timeval */
 #define ST_SIZE     1
 #define ST_TIMEVAL  2
 #define ST_COUNT    3
 #define ST_HEAPCOST 4
 /*
 ** Callsite loop direction flags.
 */
 #define ST_FOLLOW_SIBLINGS   0
 #define ST_FOLLOW_PARENTS    1
 /*
 ** Graph data.
 */
 #define STGD_WIDTH           640
 #define STGD_HEIGHT          480
 #define STGD_MARGIN          75
 #define STGD_SPACE_X         (STGD_WIDTH - (2 * STGD_MARGIN))
 #define STGD_SPACE_Y         (STGD_HEIGHT - (2 * STGD_MARGIN))
 /*
 ** Minimum lifetime default, in seconds.
 */
 #define ST_DEFAULT_LIFETIME_MIN 10
 /*
 **  Allocations fall to this boundry size by default.
 **  Overhead is taken after alignment.
 **
 **  The msvcrt malloc has an alignment of 16 with an overhead of 8.
 **  The win32 HeapAlloc has an alignment of 8 with an overhead of 8.
 */
 #define ST_DEFAULT_ALIGNMENT_SIZE 16
 #define ST_DEFAULT_OVERHEAD_SIZE 8
 /*
 ** Numer of substring match specifications to allow.
 */
 #define ST_SUBSTRING_MATCH_MAX 5
 /*
 ** Max Number of patterns per rule
 */
 #define ST_MAX_PATTERNS_PER_RULE 16
 /*
 ** Rule pointers and child pointers are allocated in steps of ST_ALLOC_STEP
 */
 #define ST_ALLOC_STEP 16
 /*
 ** Name of the root category. Appears in UI.
 */
 #define ST_ROOT_CATEGORY_NAME "All"
 /*
 **  Size of our option string buffers.
 */
 #define ST_OPTION_STRING_MAX 256
 /*
 ** Set the desired resolution of the timevals.
 ** The resolution is just mimicking what is recorded in the trace-malloc
 **  output, and that is currently milliseconds.
 */
 #define ST_TIMEVAL_RESOLUTION 1000
 #define ST_TIMEVAL_FORMAT "%.3f"
 #define ST_TIMEVAL_PRINTABLE(timeval) ((double)(timeval) / (double)ST_TIMEVAL_RESOLUTION)
 #define ST_TIMEVAL_PRINTABLE64(timeval) ((double)((int64_t)(timeval)) / (double)ST_TIMEVAL_RESOLUTION)
 #define ST_TIMEVAL_MAX ((uint32_t)-1 - ((uint32_t)-1 % ST_TIMEVAL_RESOLUTION))
 #define ST_MICROVAL_RESOLUTION 1000000
 #define ST_MICROVAL_FORMAT "%.6f"
 #define ST_MICROVAL_PRINTABLE(timeval) ((double)(timeval) / (double)ST_MICROVAL_RESOLUTION)
 #define ST_MICROVAL_PRINTABLE64(timeval) ((double)((int64_t)(timeval)) / (double)ST_MICROVAL_RESOLUTION)
 #define ST_MICROVAL_MAX ((uint32_t)-1 - ((uint32_t)-1 % ST_MICROVAL_RESOLUTION))
 /*
 ** Forward Declaration
 */
 typedef struct __struct_STCategoryNode STCategoryNode;
 typedef struct __struct_STCategoryRule STCategoryRule;
 /*
 ** STAllocEvent
 **
 ** An event that happens to an allocation (malloc, free, et. al.)
 */
 typedef struct __struct_STAllocEvent
 {
         /*
         ** The type of allocation event.
         ** This maps directly to the trace malloc events (i.e. TM_EVENT_MALLOC)
         */
         char mEventType;
         /*
         ** Each event, foremost, has a chronologically increasing ID in
         **  relation to other allocation events.  This is a time stamp
         **  of sorts.
         */
         uint32_t mTimeval;
         /*
         ** Every event has a heap ID (pointer).
         ** In the event of a realloc, this is the new heap ID.
         ** In the event of a free, this is the previous heap ID value.
         */
         uint32_t mHeapID;
         /*
         ** Every event, along with the heap ID, tells of the size.
         ** In the event of a realloc, this is the new size.
         ** In th event of a free, this is the previous size.
         */
         uint32_t mHeapSize;
         /*
         ** Every event has a callsite/stack backtrace.
         ** In the event of a realloc, this is the new callsite.
         ** In the event of a free, this is the previous call site.
         */
         tmcallsite* mCallsite;
 } STAllocEvent;
 /*
 ** STAllocation
 **
 ** An allocation is a temporal entity in the heap.
 ** It possibly lives under different heap IDs (pointers) and different
 **  sizes during its given time.
 ** An allocation is defined by the events during its lifetime.
 ** An allocation's lifetime is defined by the range of event IDs it holds.
 */
 typedef struct __struct_STAllocation
 {
         /*
         ** The array of events.
         */
         uint32_t mEventCount;
         STAllocEvent* mEvents;
         /*
         ** The lifetime/lifespan of the allocation.
         */
         uint32_t mMinTimeval;
         uint32_t mMaxTimeval;
         /*
         ** Index of this allocation in the global run.
         */
         uint32_t mRunIndex;
         /*
         ** The runtime cost of heap events in this allocation.
         ** The cost is defined as the number of time units recorded as being
         **  spent in heap code (time of malloc, free, et al.).
         ** We do not track individual event cost in order to save space.
         */
         uint32_t mHeapRuntimeCost;
 } STAllocation;
 /*
 ** STCallsiteStats
 **
 ** Stats regarding a run, kept mainly for callsite runs.
 */
 typedef struct __struct_STCallsiteStats
 {
         /*
         ** Sum timeval of the allocations.
         ** Callsite runs total all allocations below the callsite.
         */
         uint64_t mTimeval64;
         /*
         ** Sum weight of the allocations.
         ** Callsite runs total all allocations below the callsite.
         */
         uint64_t mWeight64;
         /*
         ** Sum size of the allocations.
         ** Callsite runs total all allocations below the callsite.
         */
         uint32_t mSize;
         /*
         ** A stamp, indicated the relevance of the run.
         ** If the stamp does not match the origin value, the
         **  data contained here-in is considered invalid.
         */
         uint32_t mStamp;
         /*
         ** A sum total of allocations (note, not sizes)  below the callsite.
         ** This is NOT the same as STRun::mAllocationCount which
         **  tracks the STRun::mAllocations array size.
         */
         uint32_t mCompositeCount;
         /*
         ** A sum total runtime cost of heap operations below the calliste.
         ** The cost is defined as the number of time units recorded as being
         **  spent in heap code (time of malloc, free, et al.).
         */
         uint32_t mHeapRuntimeCost;
 } STCallsiteStats;
 /*
 ** STRun
 **
 ** A run is a closed set of allocations.
 ** Given a run, we can deduce information about the contained allocations.
 ** We can also determine if an allocation lives beyond a run (leak).
 **
 ** A run might be used to represent allocations for an entire application.
 ** A run might also be used to represent allocations from a single callstack.
 */
 typedef struct __struct_STRun
 {
         /*
         ** The array of allocations.
         */
         uint32_t mAllocationCount;
         STAllocation** mAllocations;
         /*
         ** Callsites like to keep some information.
         ** As callsites are possibly shared between all contexts, each
         **      different context needs to keep different stats.
         */
         STCallsiteStats *mStats;
 } STRun;
 /*
 ** Categorize allocations
 **
 ** The objective is to have a tree of categories with each leaf node of the tree
 ** matching a set of callsites that belong to the category. Each category can
 ** signify a functional area like say css and hence the user can browse this
 ** tree looking for how much of each of these are live at an instant.
 */
 /*
 ** STCategoryNode
 */
 struct __struct_STCategoryNode
 {
         /*
         ** Category name
         */
         const char *categoryName;
         /*
         ** Pointer to parent node. NULL for Root.
         */
         STCategoryNode *parent;
         /*
         ** For non-leaf nodes, an array of children node pointers.
         ** NULL if leaf node.
         */
         STCategoryNode** children;
         uint32_t nchildren;
         /*
         ** The Run(s). Valid for both leaf and parent nodes.
         ** One run per --Context to handle multiple data sets.
         ** The relevant index for the particular request will be
         **      mIndex stored by the mContext of the request.
         */
         STRun **runs;
 };
 struct __struct_STCategoryRule
 {
         /*
         ** The pattern for the rule. Patterns are an array of strings.
         ** A callsite needs to pass substring match for all the strings.
         */
         char* pats[ST_MAX_PATTERNS_PER_RULE];
         uint32_t patlen[ST_MAX_PATTERNS_PER_RULE];
         uint32_t npats;
         /*
         ** Category name that this rule belongs to
         */
         const char* categoryName;
         /*
         ** The node this should be categorized into
         */
         STCategoryNode* node;
 };
 /*
 ** CategoryName to Node mapping table
 */
 typedef struct __struct_STCategoryMapEntry {
     STCategoryNode* node;
     const char * categoryName;
 } STCategoryMapEntry;
 /*
 **  Option genres.
 **
 **  This helps to determine what functionality each option effects.
 **  In specific, this will help use determine when and when not to
 **      totally recaclulate the sorted run and categories.
 **  Be very aware that adding things to a particular genre, or adding a genre,
 **      may completely screw up the caching algorithms of SpaceTrace.
 **  See contextLookup() or ask someone that knows if you are in doubt.
 */
 typedef enum __enum_STOptionGenre
 {
     CategoryGenre = 0,
     DataSortGenre,
     DataSetGenre,
     DataSizeGenre,
     UIGenre,
     ServerGenre,
     BatchModeGenre,
     /*
     **  Last one please.
     */
     MaxGenres
 }
 STOptionGenre;
 /*
 **  STOptions
 **
 **  Structure containing the varios options for the code.
 **  The definition of these options exists in a different file.
 **  We access that definition via macros to inline our structure definition.
 */
 #define ST_CMD_OPTION_BOOL(option_name, option_genre, option_help) PRBool m##option_name;
 #define ST_CMD_OPTION_STRING(option_name, option_genre, default_value, option_help) char m##option_name[ST_OPTION_STRING_MAX];
 #define ST_CMD_OPTION_STRING_ARRAY(option_name, option_genre, array_size, option_help) char m##option_name[array_size][ST_OPTION_STRING_MAX];
 #define ST_CMD_OPTION_STRING_PTR_ARRAY(option_name, option_genre, option_help) const char** m##option_name; uint32_t m##option_name##Count;
 #define ST_CMD_OPTION_UINT32(option_name, option_genre, default_value, multiplier, option_help) uint32_t m##option_name;
 #define ST_CMD_OPTION_UINT64(option_name, option_genre, default_value, multiplier, option_help) uint64_t m##option_name##64;
 typedef struct __struct_STOptions
 {
 #include "stoptions.h"
 }
 STOptions;
 typedef struct __struct_STContext
 /*
 **  A per request, thread safe, manner of accessing the contained members.
 **  A reader/writer lock ensures that the data is properly initialized before
 **      readers of the data begin their work.
 **
 **  mRWLock             reader/writer lock.
 **                      writer lock is held to ensure initialization, though
 **                          others can be attempting to acquire read locks
 **                          at that time.
 **                      writer lock is also used in destruction to make sure
 **                          there are no more readers of data contained herein.
 **                      reader lock is to allow multiple clients to read the
 **                          data at the same time; implies is they must not
 **                          write anything.
 **  mIndex              Consider this much like thread private data or thread
 **                          local storage in a few places.
 **                      The index is specifically reserved for this context's
 **                          usage in other data structure array's provided
 **                          for the particular thread/client/context.
 **                      This should not be modified after initialization.
 **  mSortedRun          A pre sorted run taken from the global run, with our
 **                          options applied.
 **  mImageLock          An overly simplistic locking mechanism to protect the
 **                          shared image cache.
 **                      The proper implementation would have a reader/writer
 **                          lock per cached image data.
 **                      However, this will prove to be simpler for the time
 **                          being.
 **  mFootprintCached    Whether or not YData contains something useful.
 **  mTimevalCached      Whether or not YData contains something useful.
 **  mLifespanCached     Whether or not YData contains something useful.
 **  mWeightCached       Whether or not YData contains something useful.
 **  mFootprintYData     Precomputed cached graph data.
 **  mTimevalYData       Precomputed cached graph data.
 **  mLifespanYData      Precomputed cached graph data.
 **  mWeightYData        Precomputed cached graph data.
 */
 {
     PRRWLock* mRWLock;
     uint32_t mIndex;
     STRun* mSortedRun;
 #if ST_WANT_GRAPHS
     PRLock* mImageLock;
     PRBool mFootprintCached;
     PRBool mTimevalCached;
     PRBool mLifespanCached;
     PRBool mWeightCached;
     uint32_t mFootprintYData[STGD_SPACE_X];
     uint32_t mTimevalYData[STGD_SPACE_X];
     uint32_t mLifespanYData[STGD_SPACE_X];
     uint64_t mWeightYData64[STGD_SPACE_X];
 #endif
 }
 STContext;
 typedef struct __struct_STContextCacheItem
 /*
 **  This basically pools the common items that the context cache will
 **      want to track on a per context basis.
 **
 **  mOptions        What options this item represents.
 **  mContext        State/data this cache item is wrapping.
 **  mReferenceCount A count of clients currently using this item.
 **                  Should this item be 0, then the cache might
 **                      decide to evict this context.
 **                  Should this item not be 0, once it reaches
 **                      zero a condition variable in the context cache
 **                      will be signaled to notify the availability.
 **  mLastAccessed   A timestamp of when this item was last accessed/released.
 **                  Ignore this unless the reference count is 0,
 **                  This is used to evict the oldest unused item from
 **                      the context cache.
 **  mInUse          Mainly PR_FALSE only at the beginning of the process,
 **                      but this indicates that the item has not yet been
 **                      used at all, and thus shouldn't be evaluated for
 **                      a cache hit.
 */
 {
     STOptions mOptions;
     STContext mContext;
     int32_t mReferenceCount;
     PRIntervalTime mLastAccessed;
     PRBool mInUse;
 }
 STContextCacheItem;
 typedef struct __struct_STContextCache
 /*
 **  A thread safe, possibly blocking, cache of context items.
 **
 **  mLock       Must hold the lock to read/access/write to this struct, as
 **                  well as any items it holds.
 **  mCacheMiss  All items are busy and there were no cache matches.
 **              This condition variable is used to wait until an item becomes
 **                  "available" to be evicted from the cache.
 **  mItems      Array of items.
 **  mItemCount  Number of items in array.
 **              This is generally the same as the global option's command line
 **                  mContexts....
 */
 {
     PRLock* mLock;
     PRCondVar* mCacheMiss;
     STContextCacheItem* mItems;
     uint32_t mItemCount;
 }
 STContextCache;
 /*
 ** STRequest
 **
 ** Things specific to a request.
 */
 typedef struct __struct_STRequest
 {
         /*
         ** Sink/where to output.
         */
         PRFileDesc* mFD;
         /*
         ** The filename requested.
         */
         const char* mGetFileName;
         /*
         **  The GET form data, if any.
         */
         const FormData* mGetData;
         /*
         **  Options specific to this request.
         */
         STOptions mOptions;
         /*
         **  The context/data/state of the request.
         */
         STContext* mContext;
 } STRequest;
 /*
 ** STGlobals
 **
 ** Various globals we keep around.
 */
 typedef struct __struct_STGlobals
 {
         /*
         ** The string which identifies this program.
         */
         const char* mProgramName;
         /*
         **  Options derived from the command line.
         **  These are used as defaults, and should remain static during
         **      the run of the application.
         */
         STOptions mCommandLineOptions;
         /*
         **  Context cache.
         **  As clients come in, based on their options, a different context
         **      will be used to service them.
         */
         STContextCache mContextCache;
         /*
         ** Various counters for different types of events.
         */
         uint32_t mMallocCount;
         uint32_t mCallocCount;
         uint32_t mReallocCount;
         uint32_t mFreeCount;
         /*
         ** Total events, operation counter.
         */
         uint32_t mOperationCount;
         /*
         ** The "run" of the input.
         */
         STRun mRun;
         /*
         ** Operation minimum/maximum timevals.
         ** So that we can determine the overall timeval of the run.
         ** NOTE:  These are NOT the options to control the data set.
         */
         uint32_t mMinTimeval;
         uint32_t mMaxTimeval;
         /*
         ** Calculates peak allocation overall for all allocations.
         */
         uint32_t mPeakMemoryUsed;
         uint32_t mMemoryUsed;
         /*
         ** A list of rules for categorization read in from the mCategoryFile
         */
        STCategoryRule** mCategoryRules;
        uint32_t mNRules;
        /*
        ** CategoryName to Node mapping table
        */
        STCategoryMapEntry** mCategoryMap;
        uint32_t mNCategoryMap;
        /*
        ** Categorized allocations. For now we support only one tree.
        */
        STCategoryNode mCategoryRoot;
        /*
        **   tmreader hash tables.
        **   Moved into globals since we need to destroy these only after all
        **       client threads are finishes (after PR_Cleanup).
        */
        tmreader* mTMR;
 } STGlobals;
 /*
 ** Function prototypes
 */
 extern STRun* createRun(STContext* inContext, uint32_t aStamp);
 extern void freeRun(STRun* aRun);
 extern int initCategories(STGlobals* g);
 extern int categorizeRun(STOptions* inOptions, STContext* inContext, const STRun* aRun, STGlobals* g);
 extern STCategoryNode* findCategoryNode(const char *catName, STGlobals *g);
 extern int freeCategories(STGlobals* g);
 extern int displayCategoryReport(STRequest* inRequest, STCategoryNode *root, int depth);
 extern int recalculateAllocationCost(STOptions* inOptions, STContext* inContext, STRun* aRun, STAllocation* aAllocation, PRBool updateParent);
 extern void htmlHeader(STRequest* inRequest, const char* aTitle);
 extern void htmlFooter(STRequest* inRequest);
 extern void htmlAnchor(STRequest* inRequest,
                        const char* aHref,
                        const char* aText,
                        const char* aTarget,
                        const char* aClass,
                        STOptions* inOptions);
 extern char *FormatNumber(int32_t num);
 /*
 ** shared globals
 */
 extern STGlobals globals;
 #endif /* spacetrace_h__ */

The Tor Browser / annotate

tools/trace-malloc/spacetrace.h@ac0c01689b40 (annotated)

tools/trace-malloc/spacetrace.h