tools/trace-malloc/spacetrace.h@97036ab72558
tools/trace-malloc/spacetrace.h
Tue, 06 Jan 2015 21:39:09 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Tue, 06 Jan 2015 21:39:09 +0100
- branch
- TOR_BUG_9701
- changeset 8
- 97036ab72558
- permissions
- -rw-r--r--
Conditionally force memory storage according to privacy.thirdparty.isolate;
This solves Tor bug #9701, complying with disk avoidance documented in
https://www.torproject.org/projects/torbrowser/design/#disk-avoidance.
1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 *
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #ifndef spacetrace_h__
8 #define spacetrace_h__
10 /*
11 ** spacetrace.h
12 **
13 ** SpaceTrace is meant to take the output of trace-malloc and present
14 ** a picture of allocations over the run of the application.
15 */
17 /*
18 ** Required includes.
19 */
20 #include <stdint.h>
21 #include "nspr.h"
22 #include "prlock.h"
23 #include "prrwlock.h"
24 #include "nsTraceMalloc.h"
25 #include "tmreader.h"
26 #include "formdata.h"
28 /*
29 ** Turn on to attempt adding support for graphs on your platform.
30 */
31 #if defined(HAVE_BOUTELL_GD)
32 #define ST_WANT_GRAPHS 1
33 #endif /* HAVE_BOUTELL_GD */
34 #if !defined(ST_WANT_GRAPHS)
35 #define ST_WANT_GRAPHS 0
36 #endif
38 /*
39 ** REPORT_ERROR
40 ** REPORT_INFO
41 **
42 ** Just report errors and stuff in a consistent manner.
43 */
44 #define REPORT_ERROR(code, function) \
45 PR_fprintf(PR_STDERR, "error(%d):\t%s\n", code, #function)
46 #define REPORT_ERROR_MSG(code, msg) \
47 PR_fprintf(PR_STDERR, "error(%d):\t%s\n", code, msg)
48 #define REPORT_INFO(msg) \
49 PR_fprintf(PR_STDOUT, "%s: %s\n", globals.mProgramName, (msg))
51 #if defined(DEBUG_blythe) && 1
52 #define REPORT_blythe(code, msg) \
53 PR_fprintf(PR_STDOUT, "gab(%d):\t%s\n", code, msg)
54 #else
55 #define REPORT_blythe(code, msg)
56 #endif /* DEBUG_blythe */
58 /*
59 ** CALLSITE_RUN
60 **
61 ** How to get a callsite run.
62 ** Allows for further indirection if needed later.
63 */
64 #define CALLSITE_RUN(callsite) \
65 ((STRun*)((callsite)->data))
67 /*
68 ** ST_PERMS
69 ** ST_FLAGS
70 **
71 ** File permissions we desire.
72 ** 0644
73 */
74 #define ST_PERMS (PR_IRUSR | PR_IWUSR | PR_IRGRP | PR_IROTH)
75 #define ST_FLAGS (PR_WRONLY | PR_CREATE_FILE | PR_TRUNCATE)
77 /*
78 ** Sorting order
79 */
80 #define ST_WEIGHT 0 /* size * timeval */
81 #define ST_SIZE 1
82 #define ST_TIMEVAL 2
83 #define ST_COUNT 3
84 #define ST_HEAPCOST 4
86 /*
87 ** Callsite loop direction flags.
88 */
89 #define ST_FOLLOW_SIBLINGS 0
90 #define ST_FOLLOW_PARENTS 1
92 /*
93 ** Graph data.
94 */
95 #define STGD_WIDTH 640
96 #define STGD_HEIGHT 480
97 #define STGD_MARGIN 75
98 #define STGD_SPACE_X (STGD_WIDTH - (2 * STGD_MARGIN))
99 #define STGD_SPACE_Y (STGD_HEIGHT - (2 * STGD_MARGIN))
101 /*
102 ** Minimum lifetime default, in seconds.
103 */
104 #define ST_DEFAULT_LIFETIME_MIN 10
106 /*
107 ** Allocations fall to this boundry size by default.
108 ** Overhead is taken after alignment.
109 **
110 ** The msvcrt malloc has an alignment of 16 with an overhead of 8.
111 ** The win32 HeapAlloc has an alignment of 8 with an overhead of 8.
112 */
113 #define ST_DEFAULT_ALIGNMENT_SIZE 16
114 #define ST_DEFAULT_OVERHEAD_SIZE 8
116 /*
117 ** Numer of substring match specifications to allow.
118 */
119 #define ST_SUBSTRING_MATCH_MAX 5
121 /*
122 ** Max Number of patterns per rule
123 */
124 #define ST_MAX_PATTERNS_PER_RULE 16
126 /*
127 ** Rule pointers and child pointers are allocated in steps of ST_ALLOC_STEP
128 */
129 #define ST_ALLOC_STEP 16
131 /*
132 ** Name of the root category. Appears in UI.
133 */
134 #define ST_ROOT_CATEGORY_NAME "All"
136 /*
137 ** Size of our option string buffers.
138 */
139 #define ST_OPTION_STRING_MAX 256
141 /*
142 ** Set the desired resolution of the timevals.
143 ** The resolution is just mimicking what is recorded in the trace-malloc
144 ** output, and that is currently milliseconds.
145 */
146 #define ST_TIMEVAL_RESOLUTION 1000
147 #define ST_TIMEVAL_FORMAT "%.3f"
148 #define ST_TIMEVAL_PRINTABLE(timeval) ((double)(timeval) / (double)ST_TIMEVAL_RESOLUTION)
149 #define ST_TIMEVAL_PRINTABLE64(timeval) ((double)((int64_t)(timeval)) / (double)ST_TIMEVAL_RESOLUTION)
150 #define ST_TIMEVAL_MAX ((uint32_t)-1 - ((uint32_t)-1 % ST_TIMEVAL_RESOLUTION))
152 #define ST_MICROVAL_RESOLUTION 1000000
153 #define ST_MICROVAL_FORMAT "%.6f"
154 #define ST_MICROVAL_PRINTABLE(timeval) ((double)(timeval) / (double)ST_MICROVAL_RESOLUTION)
155 #define ST_MICROVAL_PRINTABLE64(timeval) ((double)((int64_t)(timeval)) / (double)ST_MICROVAL_RESOLUTION)
156 #define ST_MICROVAL_MAX ((uint32_t)-1 - ((uint32_t)-1 % ST_MICROVAL_RESOLUTION))
158 /*
159 ** Forward Declaration
160 */
161 typedef struct __struct_STCategoryNode STCategoryNode;
162 typedef struct __struct_STCategoryRule STCategoryRule;
165 /*
166 ** STAllocEvent
167 **
168 ** An event that happens to an allocation (malloc, free, et. al.)
169 */
170 typedef struct __struct_STAllocEvent
171 {
172 /*
173 ** The type of allocation event.
174 ** This maps directly to the trace malloc events (i.e. TM_EVENT_MALLOC)
175 */
176 char mEventType;
178 /*
179 ** Each event, foremost, has a chronologically increasing ID in
180 ** relation to other allocation events. This is a time stamp
181 ** of sorts.
182 */
183 uint32_t mTimeval;
185 /*
186 ** Every event has a heap ID (pointer).
187 ** In the event of a realloc, this is the new heap ID.
188 ** In the event of a free, this is the previous heap ID value.
189 */
190 uint32_t mHeapID;
192 /*
193 ** Every event, along with the heap ID, tells of the size.
194 ** In the event of a realloc, this is the new size.
195 ** In th event of a free, this is the previous size.
196 */
197 uint32_t mHeapSize;
199 /*
200 ** Every event has a callsite/stack backtrace.
201 ** In the event of a realloc, this is the new callsite.
202 ** In the event of a free, this is the previous call site.
203 */
204 tmcallsite* mCallsite;
205 } STAllocEvent;
207 /*
208 ** STAllocation
209 **
210 ** An allocation is a temporal entity in the heap.
211 ** It possibly lives under different heap IDs (pointers) and different
212 ** sizes during its given time.
213 ** An allocation is defined by the events during its lifetime.
214 ** An allocation's lifetime is defined by the range of event IDs it holds.
215 */
216 typedef struct __struct_STAllocation
217 {
218 /*
219 ** The array of events.
220 */
221 uint32_t mEventCount;
222 STAllocEvent* mEvents;
224 /*
225 ** The lifetime/lifespan of the allocation.
226 */
227 uint32_t mMinTimeval;
228 uint32_t mMaxTimeval;
230 /*
231 ** Index of this allocation in the global run.
232 */
233 uint32_t mRunIndex;
235 /*
236 ** The runtime cost of heap events in this allocation.
237 ** The cost is defined as the number of time units recorded as being
238 ** spent in heap code (time of malloc, free, et al.).
239 ** We do not track individual event cost in order to save space.
240 */
241 uint32_t mHeapRuntimeCost;
242 } STAllocation;
244 /*
245 ** STCallsiteStats
246 **
247 ** Stats regarding a run, kept mainly for callsite runs.
248 */
249 typedef struct __struct_STCallsiteStats
250 {
251 /*
252 ** Sum timeval of the allocations.
253 ** Callsite runs total all allocations below the callsite.
254 */
255 uint64_t mTimeval64;
257 /*
258 ** Sum weight of the allocations.
259 ** Callsite runs total all allocations below the callsite.
260 */
261 uint64_t mWeight64;
263 /*
264 ** Sum size of the allocations.
265 ** Callsite runs total all allocations below the callsite.
266 */
267 uint32_t mSize;
269 /*
270 ** A stamp, indicated the relevance of the run.
271 ** If the stamp does not match the origin value, the
272 ** data contained here-in is considered invalid.
273 */
274 uint32_t mStamp;
276 /*
277 ** A sum total of allocations (note, not sizes) below the callsite.
278 ** This is NOT the same as STRun::mAllocationCount which
279 ** tracks the STRun::mAllocations array size.
280 */
281 uint32_t mCompositeCount;
283 /*
284 ** A sum total runtime cost of heap operations below the calliste.
285 ** The cost is defined as the number of time units recorded as being
286 ** spent in heap code (time of malloc, free, et al.).
287 */
288 uint32_t mHeapRuntimeCost;
289 } STCallsiteStats;
291 /*
292 ** STRun
293 **
294 ** A run is a closed set of allocations.
295 ** Given a run, we can deduce information about the contained allocations.
296 ** We can also determine if an allocation lives beyond a run (leak).
297 **
298 ** A run might be used to represent allocations for an entire application.
299 ** A run might also be used to represent allocations from a single callstack.
300 */
301 typedef struct __struct_STRun
302 {
303 /*
304 ** The array of allocations.
305 */
306 uint32_t mAllocationCount;
307 STAllocation** mAllocations;
309 /*
310 ** Callsites like to keep some information.
311 ** As callsites are possibly shared between all contexts, each
312 ** different context needs to keep different stats.
313 */
314 STCallsiteStats *mStats;
316 } STRun;
318 /*
319 ** Categorize allocations
320 **
321 ** The objective is to have a tree of categories with each leaf node of the tree
322 ** matching a set of callsites that belong to the category. Each category can
323 ** signify a functional area like say css and hence the user can browse this
324 ** tree looking for how much of each of these are live at an instant.
325 */
327 /*
328 ** STCategoryNode
329 */
331 struct __struct_STCategoryNode
332 {
333 /*
334 ** Category name
335 */
336 const char *categoryName;
338 /*
339 ** Pointer to parent node. NULL for Root.
340 */
341 STCategoryNode *parent;
343 /*
344 ** For non-leaf nodes, an array of children node pointers.
345 ** NULL if leaf node.
346 */
347 STCategoryNode** children;
348 uint32_t nchildren;
350 /*
351 ** The Run(s). Valid for both leaf and parent nodes.
352 ** One run per --Context to handle multiple data sets.
353 ** The relevant index for the particular request will be
354 ** mIndex stored by the mContext of the request.
355 */
356 STRun **runs;
357 };
360 struct __struct_STCategoryRule
361 {
362 /*
363 ** The pattern for the rule. Patterns are an array of strings.
364 ** A callsite needs to pass substring match for all the strings.
365 */
366 char* pats[ST_MAX_PATTERNS_PER_RULE];
367 uint32_t patlen[ST_MAX_PATTERNS_PER_RULE];
368 uint32_t npats;
370 /*
371 ** Category name that this rule belongs to
372 */
373 const char* categoryName;
375 /*
376 ** The node this should be categorized into
377 */
378 STCategoryNode* node;
379 };
382 /*
383 ** CategoryName to Node mapping table
384 */
385 typedef struct __struct_STCategoryMapEntry {
386 STCategoryNode* node;
387 const char * categoryName;
388 } STCategoryMapEntry;
390 /*
391 ** Option genres.
392 **
393 ** This helps to determine what functionality each option effects.
394 ** In specific, this will help use determine when and when not to
395 ** totally recaclulate the sorted run and categories.
396 ** Be very aware that adding things to a particular genre, or adding a genre,
397 ** may completely screw up the caching algorithms of SpaceTrace.
398 ** See contextLookup() or ask someone that knows if you are in doubt.
399 */
400 typedef enum __enum_STOptionGenre
401 {
402 CategoryGenre = 0,
403 DataSortGenre,
404 DataSetGenre,
405 DataSizeGenre,
406 UIGenre,
407 ServerGenre,
408 BatchModeGenre,
410 /*
411 ** Last one please.
412 */
413 MaxGenres
414 }
415 STOptionGenre;
417 /*
418 ** STOptions
419 **
420 ** Structure containing the varios options for the code.
421 ** The definition of these options exists in a different file.
422 ** We access that definition via macros to inline our structure definition.
423 */
424 #define ST_CMD_OPTION_BOOL(option_name, option_genre, option_help) PRBool m##option_name;
425 #define ST_CMD_OPTION_STRING(option_name, option_genre, default_value, option_help) char m##option_name[ST_OPTION_STRING_MAX];
426 #define ST_CMD_OPTION_STRING_ARRAY(option_name, option_genre, array_size, option_help) char m##option_name[array_size][ST_OPTION_STRING_MAX];
427 #define ST_CMD_OPTION_STRING_PTR_ARRAY(option_name, option_genre, option_help) const char** m##option_name; uint32_t m##option_name##Count;
428 #define ST_CMD_OPTION_UINT32(option_name, option_genre, default_value, multiplier, option_help) uint32_t m##option_name;
429 #define ST_CMD_OPTION_UINT64(option_name, option_genre, default_value, multiplier, option_help) uint64_t m##option_name##64;
431 typedef struct __struct_STOptions
432 {
433 #include "stoptions.h"
434 }
435 STOptions;
437 typedef struct __struct_STContext
438 /*
439 ** A per request, thread safe, manner of accessing the contained members.
440 ** A reader/writer lock ensures that the data is properly initialized before
441 ** readers of the data begin their work.
442 **
443 ** mRWLock reader/writer lock.
444 ** writer lock is held to ensure initialization, though
445 ** others can be attempting to acquire read locks
446 ** at that time.
447 ** writer lock is also used in destruction to make sure
448 ** there are no more readers of data contained herein.
449 ** reader lock is to allow multiple clients to read the
450 ** data at the same time; implies is they must not
451 ** write anything.
452 ** mIndex Consider this much like thread private data or thread
453 ** local storage in a few places.
454 ** The index is specifically reserved for this context's
455 ** usage in other data structure array's provided
456 ** for the particular thread/client/context.
457 ** This should not be modified after initialization.
458 ** mSortedRun A pre sorted run taken from the global run, with our
459 ** options applied.
460 ** mImageLock An overly simplistic locking mechanism to protect the
461 ** shared image cache.
462 ** The proper implementation would have a reader/writer
463 ** lock per cached image data.
464 ** However, this will prove to be simpler for the time
465 ** being.
466 ** mFootprintCached Whether or not YData contains something useful.
467 ** mTimevalCached Whether or not YData contains something useful.
468 ** mLifespanCached Whether or not YData contains something useful.
469 ** mWeightCached Whether or not YData contains something useful.
470 ** mFootprintYData Precomputed cached graph data.
471 ** mTimevalYData Precomputed cached graph data.
472 ** mLifespanYData Precomputed cached graph data.
473 ** mWeightYData Precomputed cached graph data.
474 */
475 {
476 PRRWLock* mRWLock;
477 uint32_t mIndex;
478 STRun* mSortedRun;
479 #if ST_WANT_GRAPHS
480 PRLock* mImageLock;
481 PRBool mFootprintCached;
482 PRBool mTimevalCached;
483 PRBool mLifespanCached;
484 PRBool mWeightCached;
485 uint32_t mFootprintYData[STGD_SPACE_X];
486 uint32_t mTimevalYData[STGD_SPACE_X];
487 uint32_t mLifespanYData[STGD_SPACE_X];
488 uint64_t mWeightYData64[STGD_SPACE_X];
489 #endif
490 }
491 STContext;
494 typedef struct __struct_STContextCacheItem
495 /*
496 ** This basically pools the common items that the context cache will
497 ** want to track on a per context basis.
498 **
499 ** mOptions What options this item represents.
500 ** mContext State/data this cache item is wrapping.
501 ** mReferenceCount A count of clients currently using this item.
502 ** Should this item be 0, then the cache might
503 ** decide to evict this context.
504 ** Should this item not be 0, once it reaches
505 ** zero a condition variable in the context cache
506 ** will be signaled to notify the availability.
507 ** mLastAccessed A timestamp of when this item was last accessed/released.
508 ** Ignore this unless the reference count is 0,
509 ** This is used to evict the oldest unused item from
510 ** the context cache.
511 ** mInUse Mainly PR_FALSE only at the beginning of the process,
512 ** but this indicates that the item has not yet been
513 ** used at all, and thus shouldn't be evaluated for
514 ** a cache hit.
515 */
516 {
517 STOptions mOptions;
518 STContext mContext;
519 int32_t mReferenceCount;
520 PRIntervalTime mLastAccessed;
521 PRBool mInUse;
522 }
523 STContextCacheItem;
526 typedef struct __struct_STContextCache
527 /*
528 ** A thread safe, possibly blocking, cache of context items.
529 **
530 ** mLock Must hold the lock to read/access/write to this struct, as
531 ** well as any items it holds.
532 ** mCacheMiss All items are busy and there were no cache matches.
533 ** This condition variable is used to wait until an item becomes
534 ** "available" to be evicted from the cache.
535 ** mItems Array of items.
536 ** mItemCount Number of items in array.
537 ** This is generally the same as the global option's command line
538 ** mContexts....
539 */
540 {
541 PRLock* mLock;
542 PRCondVar* mCacheMiss;
543 STContextCacheItem* mItems;
544 uint32_t mItemCount;
545 }
546 STContextCache;
549 /*
550 ** STRequest
551 **
552 ** Things specific to a request.
553 */
554 typedef struct __struct_STRequest
555 {
556 /*
557 ** Sink/where to output.
558 */
559 PRFileDesc* mFD;
561 /*
562 ** The filename requested.
563 */
564 const char* mGetFileName;
566 /*
567 ** The GET form data, if any.
568 */
569 const FormData* mGetData;
571 /*
572 ** Options specific to this request.
573 */
574 STOptions mOptions;
576 /*
577 ** The context/data/state of the request.
578 */
579 STContext* mContext;
580 } STRequest;
583 /*
584 ** STGlobals
585 **
586 ** Various globals we keep around.
587 */
588 typedef struct __struct_STGlobals
589 {
590 /*
591 ** The string which identifies this program.
592 */
593 const char* mProgramName;
595 /*
596 ** Options derived from the command line.
597 ** These are used as defaults, and should remain static during
598 ** the run of the application.
599 */
600 STOptions mCommandLineOptions;
602 /*
603 ** Context cache.
604 ** As clients come in, based on their options, a different context
605 ** will be used to service them.
606 */
607 STContextCache mContextCache;
609 /*
610 ** Various counters for different types of events.
611 */
612 uint32_t mMallocCount;
613 uint32_t mCallocCount;
614 uint32_t mReallocCount;
615 uint32_t mFreeCount;
617 /*
618 ** Total events, operation counter.
619 */
620 uint32_t mOperationCount;
622 /*
623 ** The "run" of the input.
624 */
625 STRun mRun;
627 /*
628 ** Operation minimum/maximum timevals.
629 ** So that we can determine the overall timeval of the run.
630 ** NOTE: These are NOT the options to control the data set.
631 */
632 uint32_t mMinTimeval;
633 uint32_t mMaxTimeval;
635 /*
636 ** Calculates peak allocation overall for all allocations.
637 */
638 uint32_t mPeakMemoryUsed;
639 uint32_t mMemoryUsed;
641 /*
642 ** A list of rules for categorization read in from the mCategoryFile
643 */
644 STCategoryRule** mCategoryRules;
645 uint32_t mNRules;
647 /*
648 ** CategoryName to Node mapping table
649 */
650 STCategoryMapEntry** mCategoryMap;
651 uint32_t mNCategoryMap;
653 /*
654 ** Categorized allocations. For now we support only one tree.
655 */
656 STCategoryNode mCategoryRoot;
658 /*
659 ** tmreader hash tables.
660 ** Moved into globals since we need to destroy these only after all
661 ** client threads are finishes (after PR_Cleanup).
662 */
663 tmreader* mTMR;
664 } STGlobals;
667 /*
668 ** Function prototypes
669 */
670 extern STRun* createRun(STContext* inContext, uint32_t aStamp);
671 extern void freeRun(STRun* aRun);
672 extern int initCategories(STGlobals* g);
673 extern int categorizeRun(STOptions* inOptions, STContext* inContext, const STRun* aRun, STGlobals* g);
674 extern STCategoryNode* findCategoryNode(const char *catName, STGlobals *g);
675 extern int freeCategories(STGlobals* g);
676 extern int displayCategoryReport(STRequest* inRequest, STCategoryNode *root, int depth);
678 extern int recalculateAllocationCost(STOptions* inOptions, STContext* inContext, STRun* aRun, STAllocation* aAllocation, PRBool updateParent);
679 extern void htmlHeader(STRequest* inRequest, const char* aTitle);
680 extern void htmlFooter(STRequest* inRequest);
681 extern void htmlAnchor(STRequest* inRequest,
682 const char* aHref,
683 const char* aText,
684 const char* aTarget,
685 const char* aClass,
686 STOptions* inOptions);
687 extern char *FormatNumber(int32_t num);
689 /*
690 ** shared globals
691 */
692 extern STGlobals globals;
694 #endif /* spacetrace_h__ */
