TraceDump.c revision 9f640af99bebc6e96f6e1e9903557e2c8f567483 
1/* //device/tools/dmtracedump/TraceDump.c
2**
3** Copyright 2006, The Android Open Source Project
4**
5** Licensed under the Apache License, Version 2.0 (the "License");
6** you may not use this file except in compliance with the License.
7** You may obtain a copy of the License at
8**
9**     http://www.apache.org/licenses/LICENSE-2.0
10**
11** Unless required by applicable law or agreed to in writing, software
12** distributed under the License is distributed on an "AS IS" BASIS,
13** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14** See the License for the specific language governing permissions and
15** limitations under the License.
16*/
17
18/*
19 * Process dmtrace output.
20 *
21 * This is the wrong way to go about it -- C is a clumsy language for
22 * shuffling data around.  It'll do for a first pass.
23 */
24#define NOT_VM
25#include "Profile.h"        // from VM header
26
27#include <stdio.h>
28#include <stdlib.h>
29#include <string.h>
30#include <unistd.h>
31#include <inttypes.h>
32#include <time.h>
33#include <errno.h>
34#include <assert.h>
35
36/* Version number in the key file.
37 * Version 1 uses one byte for the thread id.
38 * Version 2 uses two bytes for the thread ids.
39 * Version 3 encodes the record size and adds an optional extra timestamp field.
40 */
41int versionNumber;
42
43/* arbitrarily limit indentation */
44#define MAX_STACK_DEPTH 10000
45
46/* thread list in key file is not reliable, so just max out */
47#define MAX_THREADS     32768
48
49/* Size of temporary buffers for escaping html strings */
50#define HTML_BUFSIZE 10240
51
52/* Size of methodId->method cache */
53#define METHOD_CACHE_SIZE 2048
54#define METHOD_CACHE_SIZE_MASK (METHOD_CACHE_SIZE - 1)
55
56/* Some filter constants */
57#define FILTER_TAG '*'
58#define FILTER_FLAG_THREAD '+'
59#define FILTER_TYPE_CLASS 0
60#define FILTER_TYPE_METHOD 1
61
62#define DEFAULT_ACTIVE_THREADS 8
63
64char *htmlHeader =
65"<html>\n<head>\n<script type=\"text/javascript\" src=\"%ssortable.js\"></script>\n"
66"<script langugage=\"javascript\">\n"
67"function toggle(item) {\n"
68"    obj=document.getElementById(item);\n"
69"    visible=(obj.style.display!=\"none\" && obj.style.display!=\"\");\n"
70"    key=document.getElementById(\"x\" + item);\n"
71"    if (visible) {\n"
72"        obj.style.display=\"none\";\n"
73"        key.innerHTML=\"+\";\n"
74"    } else {\n"
75"        obj.style.display=\"block\";\n"
76"        key.innerHTML=\"-\";\n"
77"    }\n"
78"}\n"
79"function onMouseOver(obj) {\n"
80"    obj.style.background=\"lightblue\";\n"
81"}\n"
82"function onMouseOut(obj) {\n"
83"    obj.style.background=\"white\";\n"
84"}\n"
85"</script>\n"
86"<style type=\"text/css\">\n"
87"div { font-family: courier; font-size: 13 }\n"
88"div.parent { margin-left: 15; display: none }\n"
89"div.leaf { margin-left: 10 }\n"
90"div.header { margin-left: 10 }\n"
91"div.link { margin-left: 10; cursor: move }\n"
92"span.parent { padding-right: 10; }\n"
93"span.leaf { padding-right: 10; }\n"
94"a img { border: 0;}\n"
95"table.sortable th { border-width: 0px 1px 1px 1px; background-color: #ccc;}\n"
96"a { text-decoration: none; }\n"
97"a:hover { text-decoration: underline; }\n"
98"table.sortable th, table.sortable td { text-align: left;}"
99"table.sortable tr.odd td { background-color: #ddd; }\n"
100"table.sortable tr.even td { background-color: #fff; }\n"
101"</style>\n"
102"</head><body>\n\n";
103
104char *htmlFooter = "\n</body>\n</html>\n";
105char *profileSeparator =
106    "======================================================================";
107
108const char* tableHeader =
109    "<table class='sortable' id='%s'><tr>\n"
110    "<th>Method</th>\n"
111    "<th>Run 1 (us)</th>\n"
112    "<th>Run 2 (us)</th>\n"
113    "<th>Diff (us)</th>\n"
114    "<th>Diff (%%)</th>\n"
115    "<th>1: # calls</th>\n"
116    "<th>2: # calls</th>\n"
117    "</tr>\n";
118
119const char* tableHeaderMissing =
120    "<table class='sortable' id='%s'>\n"
121    "<th>Method</th>\n"
122    "<th>Exclusive</th>\n"
123    "<th>Inclusive</th>\n"
124    "<th># calls</th>\n";
125
126#define GRAPH_LABEL_VISITED 0x0001
127#define GRAPH_NODE_VISITED  0x0002
128
129/*
130 * Values from the header of the data file.
131 */
132typedef struct DataHeader {
133    unsigned int magic;
134    short version;
135    short offsetToData;
136    long long startWhen;
137    short recordSize;
138} DataHeader;
139
140/*
141 * Entry from the thread list.
142 */
143typedef struct ThreadEntry {
144    int         threadId;
145    const char* threadName;
146    uint64_t    elapsedTime;
147} ThreadEntry;
148
149struct MethodEntry;
150typedef struct TimedMethod {
151    struct TimedMethod *next;
152    uint64_t elapsedInclusive;
153    int numCalls;
154    struct MethodEntry *method;
155} TimedMethod;
156
157typedef struct ClassEntry {
158    const char *className;
159    uint64_t elapsedExclusive;
160    int numMethods;
161    struct MethodEntry **methods;       /* list of methods in this class */
162    int numCalls[2];                    /* 0=normal, 1=recursive */
163} ClassEntry;
164
165typedef struct UniqueMethodEntry {
166    uint64_t elapsedExclusive;
167    int numMethods;
168    struct MethodEntry **methods;       /* list of methods with same name */
169    int numCalls[2];                    /* 0=normal, 1=recursive */
170} UniqueMethodEntry;
171
172/*
173 * Entry from the method list.
174 */
175typedef struct MethodEntry {
176    unsigned int methodId;
177    const char* className;
178    const char* methodName;
179    const char* signature;
180    const char* fileName;
181    int lineNum;
182    uint64_t elapsedExclusive;
183    uint64_t elapsedInclusive;
184    uint64_t topExclusive;              /* non-recursive exclusive time */
185    uint64_t recursiveInclusive;
186    struct TimedMethod *parents[2];     /* 0=normal, 1=recursive */
187    struct TimedMethod *children[2];    /* 0=normal, 1=recursive */
188    int numCalls[2];                    /* 0=normal, 1=recursive */
189    int index;                  /* used after sorting to number methods */
190    int recursiveEntries;       /* number of entries on the stack */
191    int graphState;             /* used when graphing to see if this method has been visited before */
192} MethodEntry;
193
194/*
195 * The parsed contents of the key file.
196 */
197typedef struct DataKeys {
198    char*        fileData;      /* contents of the entire file */
199    long         fileLen;
200    int          numThreads;
201    ThreadEntry* threads;
202    int          numMethods;
203    MethodEntry* methods;       /* 2 extra methods: "toplevel" and "unknown" */
204    int*         methodCache;   /* methodId->methodIndex mapping */
205    // TODO change to map methodId->method itself
206} DataKeys;
207
208#define TOPLEVEL_INDEX 0
209#define UNKNOWN_INDEX 1
210
211typedef struct StackEntry {
212    MethodEntry *method;
213    uint64_t    entryTime;
214} StackEntry;
215
216typedef struct CallStack {
217    int           top;
218    StackEntry    calls[MAX_STACK_DEPTH];
219    uint64_t      lastEventTime;
220    uint64_t      threadStartTime;
221    uint64_t*     remTimes;
222    // Note: remTimes keeps a sum of 'un-allocated' time for each thread, in case
223    // we need to allocate it to one (or many) filter later. This would happen when
224    // we see a method exit that maches a filter, but whose entry we hadn't seen.
225    // TODO: consider moving remTimes into FilterTimes and change logic appropriately
226} CallStack;
227
228typedef struct DiffEntry {
229    MethodEntry* method1;
230    MethodEntry* method2;
231    int64_t differenceExclusive;
232    int64_t differenceInclusive;
233    double differenceExclusivePercentage;
234    double differenceInclusivePercentage;
235} DiffEntry;
236
237// Global options
238typedef struct Options {
239    const char* traceFileName;
240    const char* diffFileName;
241    const char* graphFileName;
242    const char* filterFileName;
243    int keepDotFile;
244    int dump;
245    int outputHtml;
246    const char* sortableUrl;
247    int threshold;
248} Options;
249
250typedef struct TraceData {
251    int numClasses;
252    ClassEntry *classes;
253    CallStack *stacks[MAX_THREADS];
254    int depth[MAX_THREADS];
255    int numUniqueMethods;
256    UniqueMethodEntry *uniqueMethods;
257} TraceData;
258
259typedef struct FilterKey {
260    int       type[2];    /* 0=class, 1=method; 2 needed for start and end keys */
261    uint32_t  flags;      /* 1st bit = include cross-thread time */
262    char*     keys[2];    /* 2 needed for start and end keys */
263} FilterKey;
264
265typedef struct FilterTimes {
266    uint64_t   totalWaitTime;
267    uint64_t*  threadWaitTimes;
268    uint64_t*  threadExecutionTimesWhileWaiting;
269    uint64_t*  threadExecutionTimes;
270} FilterTimes;
271
272typedef struct Filter {
273    char*       filterName;
274    FilterKey*  filterKeys;
275    int         numKeys;
276    int         activeCount;
277    int*        activeThreads;
278    int*        activationKeys;
279    FilterTimes times;
280} Filter;
281
282int numFilters = 0; // global
283
284static Options gOptions;
285
286/* Escapes characters in the source string that are html special entities.
287 * The escaped string is written to "dest" which must be large enough to
288 * hold the result.  A pointer to "dest" is returned.  The characters and
289 * their corresponding escape sequences are:
290 *  '<'  &lt;
291 *  '>'  &gt;
292 *  '&'  &amp;
293 */
294char *htmlEscape(const char *src, char *dest, int len)
295{
296    char *destStart = dest;
297
298    if (src == NULL)
299        return NULL;
300
301    int nbytes = 0;
302    while (*src) {
303        if (*src == '<') {
304            nbytes += 4;
305            if (nbytes >= len)
306                break;
307            *dest++ = '&';
308            *dest++ = 'l';
309            *dest++ = 't';
310            *dest++ = ';';
311        } else if (*src == '>') {
312            nbytes += 4;
313            if (nbytes >= len)
314                break;
315            *dest++ = '&';
316            *dest++ = 'g';
317            *dest++ = 't';
318            *dest++ = ';';
319        } else if (*src == '&') {
320            nbytes += 5;
321            if (nbytes >= len)
322                break;
323            *dest++ = '&';
324            *dest++ = 'a';
325            *dest++ = 'm';
326            *dest++ = 'p';
327            *dest++ = ';';
328        } else {
329            nbytes += 1;
330            if (nbytes >= len)
331                break;
332            *dest++ = *src;
333        }
334        src += 1;
335    }
336    if (nbytes >= len) {
337        fprintf(stderr, "htmlEscape(): buffer overflow\n");
338        exit(1);
339    }
340    *dest = 0;
341
342    return destStart;
343}
344
345/* Initializes a MethodEntry
346 */
347void initMethodEntry(MethodEntry *method, unsigned int methodId,
348                     const char *className, const char *methodName,
349                     const char *signature, const char* fileName,
350                     const char* lineNumStr)
351{
352    method->methodId = methodId;
353    method->className = className;
354    method->methodName = methodName;
355    method->signature = signature;
356    method->fileName = fileName;
357    method->lineNum = (lineNumStr != NULL) ? atoi(lineNumStr) : -1;
358    method->elapsedExclusive = 0;
359    method->elapsedInclusive = 0;
360    method->topExclusive = 0;
361    method->recursiveInclusive = 0;
362    method->parents[0] = NULL;
363    method->parents[1] = NULL;
364    method->children[0] = NULL;
365    method->children[1] = NULL;
366    method->numCalls[0] = 0;
367    method->numCalls[1] = 0;
368    method->index = 0;
369    method->recursiveEntries = 0;
370}
371
372/*
373 * This comparison function is called from qsort() to sort
374 * methods into decreasing order of exclusive elapsed time.
375 */
376int compareElapsedExclusive(const void *a, const void *b) {
377    uint64_t elapsed1, elapsed2;
378    int result;
379
380    const MethodEntry *methodA = *(const MethodEntry**)a;
381    const MethodEntry *methodB = *(const MethodEntry**)b;
382    elapsed1 = methodA->elapsedExclusive;
383    elapsed2 = methodB->elapsedExclusive;
384    if (elapsed1 < elapsed2)
385        return 1;
386    if (elapsed1 > elapsed2)
387        return -1;
388
389    /* If the elapsed times of two methods are equal, then sort them
390     * into alphabetical order.
391     */
392    result = strcmp(methodA->className, methodB->className);
393    if (result == 0) {
394        if (methodA->methodName == NULL || methodB->methodName == NULL) {
395            unsigned int idA = methodA->methodId;
396            unsigned int idB = methodB->methodId;
397            if (idA < idB)
398                return -1;
399            if (idA > idB)
400                return 1;
401            return 0;
402        }
403        result = strcmp(methodA->methodName, methodB->methodName);
404        if (result == 0)
405            result = strcmp(methodA->signature, methodB->signature);
406    }
407    return result;
408}
409
410/*
411 * This comparison function is called from qsort() to sort
412 * methods into decreasing order of inclusive elapsed time.
413 */
414int compareElapsedInclusive(const void *a, const void *b) {
415    const MethodEntry *methodA, *methodB;
416    uint64_t elapsed1, elapsed2;
417    int result;
418
419    methodA = *(MethodEntry const **)a;
420    methodB = *(MethodEntry const **)b;
421    elapsed1 = methodA->elapsedInclusive;
422    elapsed2 = methodB->elapsedInclusive;
423    if (elapsed1 < elapsed2)
424        return 1;
425    if (elapsed1 > elapsed2)
426        return -1;
427
428    /* If the elapsed times of two methods are equal, then sort them
429     * into alphabetical order.
430     */
431    result = strcmp(methodA->className, methodB->className);
432    if (result == 0) {
433        if (methodA->methodName == NULL || methodB->methodName == NULL) {
434            unsigned int idA = methodA->methodId;
435            unsigned int idB = methodB->methodId;
436            if (idA < idB)
437                return -1;
438            if (idA > idB)
439                return 1;
440            return 0;
441        }
442        result = strcmp(methodA->methodName, methodB->methodName);
443        if (result == 0)
444            result = strcmp(methodA->signature, methodB->signature);
445    }
446    return result;
447}
448
449/*
450 * This comparison function is called from qsort() to sort
451 * threads into decreasing order of elapsed time.
452 */
453int compareElapsed(const void *a, const void *b) {
454    const ThreadEntry *threadA, *threadB;
455    uint64_t elapsed1, elapsed2;
456    int result = 0;
457
458    threadA = (ThreadEntry const *)a;
459    threadB = (ThreadEntry const *)b;
460    elapsed1 = threadA->elapsedTime;
461    elapsed2 = threadB->elapsedTime;
462    if (elapsed1 < elapsed2)
463        return 1;
464    if (elapsed1 > elapsed2)
465        return -1;
466
467    /* If the elapsed times of two threads are equal, then sort them
468     * by thread id.
469     */
470    int idA = threadA->threadId;
471    int idB = threadB->threadId;
472    if (idA < idB)
473        result = -1;
474    if (idA > idB)
475        result = 1;
476
477    return result;
478}
479
480/*
481 * This comparison function is called from qsort() to sort
482 * TimedMethods into decreasing order of inclusive elapsed time.
483 */
484int compareTimedMethod(const void *a, const void *b) {
485    const TimedMethod *timedA, *timedB;
486    uint64_t elapsed1, elapsed2;
487    int result;
488
489    timedA = (TimedMethod const *)a;
490    timedB = (TimedMethod const *)b;
491    elapsed1 = timedA->elapsedInclusive;
492    elapsed2 = timedB->elapsedInclusive;
493    if (elapsed1 < elapsed2)
494        return 1;
495    if (elapsed1 > elapsed2)
496        return -1;
497
498    /* If the elapsed times of two methods are equal, then sort them
499     * into alphabetical order.
500     */
501    MethodEntry *methodA = timedA->method;
502    MethodEntry *methodB = timedB->method;
503    result = strcmp(methodA->className, methodB->className);
504    if (result == 0) {
505        if (methodA->methodName == NULL || methodB->methodName == NULL) {
506            unsigned int idA = methodA->methodId;
507            unsigned int idB = methodB->methodId;
508            if (idA < idB)
509                return -1;
510            if (idA > idB)
511                return 1;
512            return 0;
513        }
514        result = strcmp(methodA->methodName, methodB->methodName);
515        if (result == 0)
516            result = strcmp(methodA->signature, methodB->signature);
517    }
518    return result;
519}
520
521/*
522 * This comparison function is called from qsort() to sort
523 * MethodEntry pointers into alphabetical order of class names.
524 */
525int compareClassNames(const void *a, const void *b) {
526    int result;
527
528    const MethodEntry *methodA = *(const MethodEntry**)a;
529    const MethodEntry *methodB = *(const MethodEntry**)b;
530    result = strcmp(methodA->className, methodB->className);
531    if (result == 0) {
532        unsigned int idA = methodA->methodId;
533        unsigned int idB = methodB->methodId;
534        if (idA < idB)
535            return -1;
536        if (idA > idB)
537            return 1;
538        return 0;
539    }
540    return result;
541}
542
543/*
544 * This comparison function is called from qsort() to sort
545 * classes into decreasing order of exclusive elapsed time.
546 */
547int compareClassExclusive(const void *a, const void *b) {
548    uint64_t elapsed1, elapsed2;
549    int result;
550
551    const ClassEntry *classA = *(const ClassEntry**)a;
552    const ClassEntry *classB = *(const ClassEntry**)b;
553    elapsed1 = classA->elapsedExclusive;
554    elapsed2 = classB->elapsedExclusive;
555    if (elapsed1 < elapsed2)
556        return 1;
557    if (elapsed1 > elapsed2)
558        return -1;
559
560    /* If the elapsed times of two classs are equal, then sort them
561     * into alphabetical order.
562     */
563    result = strcmp(classA->className, classB->className);
564    if (result == 0) {
565        /* Break ties with the first method id.  This is probably not
566         * needed.
567         */
568        unsigned int idA = classA->methods[0]->methodId;
569        unsigned int idB = classB->methods[0]->methodId;
570        if (idA < idB)
571            return -1;
572        if (idA > idB)
573            return 1;
574        return 0;
575    }
576    return result;
577}
578
579/*
580 * This comparison function is called from qsort() to sort
581 * MethodEntry pointers into alphabetical order by method name,
582 * then by class name.
583 */
584int compareMethodNames(const void *a, const void *b) {
585    int result;
586
587    const MethodEntry *methodA = *(const MethodEntry**)a;
588    const MethodEntry *methodB = *(const MethodEntry**)b;
589    if (methodA->methodName == NULL || methodB->methodName == NULL) {
590        return compareClassNames(a, b);
591    }
592    result = strcmp(methodA->methodName, methodB->methodName);
593    if (result == 0) {
594        result = strcmp(methodA->className, methodB->className);
595        if (result == 0) {
596            unsigned int idA = methodA->methodId;
597            unsigned int idB = methodB->methodId;
598            if (idA < idB)
599                return -1;
600            if (idA > idB)
601                return 1;
602            return 0;
603        }
604    }
605    return result;
606}
607
608/*
609 * This comparison function is called from qsort() to sort
610 * unique methods into decreasing order of exclusive elapsed time.
611 */
612int compareUniqueExclusive(const void *a, const void *b) {
613    uint64_t elapsed1, elapsed2;
614    int result;
615
616    const UniqueMethodEntry *uniqueA = *(const UniqueMethodEntry**)a;
617    const UniqueMethodEntry *uniqueB = *(const UniqueMethodEntry**)b;
618    elapsed1 = uniqueA->elapsedExclusive;
619    elapsed2 = uniqueB->elapsedExclusive;
620    if (elapsed1 < elapsed2)
621        return 1;
622    if (elapsed1 > elapsed2)
623        return -1;
624
625    /* If the elapsed times of two methods are equal, then sort them
626     * into alphabetical order.
627     */
628    result = strcmp(uniqueA->methods[0]->className,
629                    uniqueB->methods[0]->className);
630    if (result == 0) {
631        unsigned int idA = uniqueA->methods[0]->methodId;
632        unsigned int idB = uniqueB->methods[0]->methodId;
633        if (idA < idB)
634            return -1;
635        if (idA > idB)
636            return 1;
637        return 0;
638    }
639    return result;
640}
641
642/*
643 * Free a DataKeys struct.
644 */
645void freeDataKeys(DataKeys* pKeys)
646{
647    if (pKeys == NULL)
648        return;
649
650    free(pKeys->fileData);
651    free(pKeys->threads);
652    free(pKeys->methods);
653    free(pKeys->methodCache);
654    free(pKeys);
655}
656
657/*
658 * Find the offset to the next occurrence of the specified character.
659 *
660 * "data" should point somewhere within the current line.  "len" is the
661 * number of bytes left in the buffer.
662 *
663 * Returns -1 if we hit the end of the buffer.
664 */
665int findNextChar(const char* data, int len, char lookFor)
666{
667    const char* start = data;
668
669    while (len > 0) {
670        if (*data == lookFor)
671            return data - start;
672
673        data++;
674        len--;
675    }
676
677    return -1;
678}
679
680int countLinesToChar(const char* data, int len, const char toFind)
681{
682    int count = 0;
683    int next;
684
685    while (*data != toFind) {
686        next = findNextChar(data, len, '\n');
687        if (next < 0)
688	    return count;
689        count++;
690        data += next+1;
691        len -= next+1;
692    }
693
694    return count;
695}
696
697/*
698 * Count the number of lines until the next token.
699 *
700 * Returns 0 if none found before EOF.
701 */
702int countLinesToToken(const char* data, int len)
703{
704    return countLinesToChar(data, len, TOKEN_CHAR);
705}
706
707/*
708 * Make sure we're at the start of the right section.
709 *
710 * Returns the length of the token line, or -1 if something is wrong.
711 */
712int checkToken(const char* data, int len, const char* cmpStr)
713{
714    int cmpLen = strlen(cmpStr);
715    int next;
716
717    if (*data != TOKEN_CHAR) {
718        fprintf(stderr,
719            "ERROR: not at start of %s (found '%.10s')\n", cmpStr, data);
720        return -1;
721    }
722
723    next = findNextChar(data, len, '\n');
724    if (next < cmpLen+1)
725        return -1;
726
727    if (strncmp(data+1, cmpStr, cmpLen) != 0) {
728        fprintf(stderr, "ERROR: '%s' not found (got '%.7s')\n", cmpStr, data+1);
729        return -1;
730    }
731
732    return next+1;
733}
734
735/*
736 * Parse the "*version" section.
737 */
738long parseVersion(DataKeys* pKeys, long offset, int verbose)
739{
740    char* data;
741    char* dataEnd;
742    int i, count, next;
743
744    if (offset < 0)
745        return -1;
746
747    data = pKeys->fileData + offset;
748    dataEnd = pKeys->fileData + pKeys->fileLen;
749    next = checkToken(data, dataEnd - data, "version");
750    if (next <= 0)
751        return -1;
752
753    data += next;
754
755    /*
756     * Count the number of items in the "version" section.
757     */
758    count = countLinesToToken(data, dataEnd - data);
759    if (count <= 0) {
760        fprintf(stderr,
761            "ERROR: failed while reading version (found %d)\n", count);
762        return -1;
763    }
764
765    /* find the end of the line */
766    next = findNextChar(data, dataEnd - data, '\n');
767    if (next < 0)
768        return -1;
769
770    data[next] = '\0';
771    versionNumber = strtoul(data, NULL, 0);
772    if (verbose)
773        printf("VERSION: %d\n", versionNumber);
774
775    data += next+1;
776
777    /* skip over the rest of the stuff, which is "name=value" lines */
778    for (i = 1; i < count; i++) {
779        next = findNextChar(data, dataEnd - data, '\n');
780        if (next < 0)
781            return -1;
782        //data[next] = '\0';
783        //printf("IGNORING: '%s'\n", data);
784        data += next+1;
785    }
786
787    return data - pKeys->fileData;
788}
789
790/*
791 * Parse the "*threads" section.
792 */
793long parseThreads(DataKeys* pKeys, long offset)
794{
795    char* data;
796    char* dataEnd;
797    int i, next, tab, count;
798
799    if (offset < 0)
800        return -1;
801
802    data = pKeys->fileData + offset;
803    dataEnd = pKeys->fileData + pKeys->fileLen;
804    next = checkToken(data, dataEnd - data, "threads");
805
806    data += next;
807
808    /*
809     * Count the number of thread entries (one per line).
810     */
811    count = countLinesToToken(data, dataEnd - data);
812    if (count <= 0) {
813        fprintf(stderr,
814            "ERROR: failed while reading threads (found %d)\n", count);
815        return -1;
816    }
817
818    //printf("+++ found %d threads\n", count);
819    pKeys->threads = (ThreadEntry*) malloc(sizeof(ThreadEntry) * count);
820    if (pKeys->threads == NULL)
821        return -1;
822
823    /*
824     * Extract all entries.
825     */
826    for (i = 0; i < count; i++) {
827        next = findNextChar(data, dataEnd - data, '\n');
828        assert(next > 0);
829        data[next] = '\0';
830
831        tab = findNextChar(data, next, '\t');
832        data[tab] = '\0';
833
834        pKeys->threads[i].threadId = atoi(data);
835        pKeys->threads[i].threadName = data + tab +1;
836
837        data += next+1;
838    }
839
840    pKeys->numThreads = count;
841    return data - pKeys->fileData;
842}
843
844/*
845 * Parse the "*methods" section.
846 */
847long parseMethods(DataKeys* pKeys, long offset)
848{
849    char* data;
850    char* dataEnd;
851    int i, next, count;
852
853    if (offset < 0)
854        return -1;
855
856    data = pKeys->fileData + offset;
857    dataEnd = pKeys->fileData + pKeys->fileLen;
858    next = checkToken(data, dataEnd - data, "methods");
859    if (next < 0)
860        return -1;
861
862    data += next;
863
864    /*
865     * Count the number of method entries (one per line).
866     */
867    count = countLinesToToken(data, dataEnd - data);
868    if (count <= 0) {
869        fprintf(stderr,
870            "ERROR: failed while reading methods (found %d)\n", count);
871        return -1;
872    }
873
874    /* Reserve an extra method at location 0 for the "toplevel" method,
875     * and another extra method for all other "unknown" methods.
876     */
877    count += 2;
878    pKeys->methods = (MethodEntry*) malloc(sizeof(MethodEntry) * count);
879    if (pKeys->methods == NULL)
880        return -1;
881    initMethodEntry(&pKeys->methods[TOPLEVEL_INDEX], 0, "(toplevel)",
882        NULL, NULL, NULL, NULL);
883    initMethodEntry(&pKeys->methods[UNKNOWN_INDEX], 0, "(unknown)",
884        NULL, NULL, NULL, NULL);
885
886    /*
887     * Extract all entries, starting with index 2.
888     */
889    for (i = UNKNOWN_INDEX + 1; i < count; i++) {
890        int tab1, tab2, tab3, tab4, tab5;
891        unsigned int id;
892        char* endptr;
893
894        next = findNextChar(data, dataEnd - data, '\n');
895        assert(next > 0);
896        data[next] = '\0';
897
898        tab1 = findNextChar(data, next, '\t');
899        tab2 = findNextChar(data+(tab1+1), next-(tab1+1), '\t');
900        tab3 = findNextChar(data+(tab1+tab2+2), next-(tab1+tab2+2), '\t');
901        tab4 = findNextChar(data+(tab1+tab2+tab3+3),
902                            next-(tab1+tab2+tab3+3), '\t');
903        tab5 = findNextChar(data+(tab1+tab2+tab3+tab4+4),
904                            next-(tab1+tab2+tab3+tab4+4), '\t');
905        if (tab1 < 0) {
906            fprintf(stderr, "ERROR: missing field on method line: '%s'\n",
907                    data);
908            return -1;
909        }
910        assert(data[tab1] == '\t');
911        data[tab1] = '\0';
912
913        id = strtoul(data, &endptr, 0);
914        if (*endptr != '\0') {
915            fprintf(stderr, "ERROR: bad method ID '%s'\n", data);
916            return -1;
917        }
918
919        // Allow files that specify just a function name, instead of requiring
920        // "class \t method \t signature"
921        if (tab2 > 0 && tab3 > 0) {
922            tab2 += tab1+1;
923            tab3 += tab2+1;
924            assert(data[tab2] == '\t');
925            assert(data[tab3] == '\t');
926            data[tab2] = data[tab3] = '\0';
927
928            // This is starting to get awkward.  Allow filename and line #.
929            if (tab4 > 0 && tab5 > 0) {
930                tab4 += tab3+1;
931                tab5 += tab4+1;
932
933                assert(data[tab4] == '\t');
934                assert(data[tab5] == '\t');
935                data[tab4] = data[tab5] = '\0';
936
937                initMethodEntry(&pKeys->methods[i], id, data + tab1 +1,
938                        data + tab2 +1, data + tab3 +1, data + tab4 +1,
939                        data + tab5 +1);
940            } else {
941                initMethodEntry(&pKeys->methods[i], id, data + tab1 +1,
942                        data + tab2 +1, data + tab3 +1, NULL, NULL);
943            }
944        } else {
945            initMethodEntry(&pKeys->methods[i], id, data + tab1 +1,
946                NULL, NULL, NULL, NULL);
947        }
948
949        data += next+1;
950    }
951
952    pKeys->numMethods = count;
953    return data - pKeys->fileData;
954}
955
956/*
957 * Parse the "*end" section.
958 */
959long parseEnd(DataKeys* pKeys, long offset)
960{
961    char* data;
962    char* dataEnd;
963    int next;
964
965    if (offset < 0)
966        return -1;
967
968    data = pKeys->fileData + offset;
969    dataEnd = pKeys->fileData + pKeys->fileLen;
970    next = checkToken(data, dataEnd - data, "end");
971    if (next < 0)
972        return -1;
973
974    data += next;
975
976    return data - pKeys->fileData;
977}
978
979/*
980 * Sort the thread list entries.
981 */
982static int compareThreads(const void* thread1, const void* thread2)
983{
984    return ((const ThreadEntry*) thread1)->threadId -
985            ((const ThreadEntry*) thread2)->threadId;
986}
987
988void sortThreadList(DataKeys* pKeys)
989{
990    qsort(pKeys->threads, pKeys->numThreads, sizeof(pKeys->threads[0]),
991        compareThreads);
992}
993
994/*
995 * Sort the method list entries.
996 */
997static int compareMethods(const void* meth1, const void* meth2)
998{
999    unsigned int id1, id2;
1000
1001    id1 = ((const MethodEntry*) meth1)->methodId;
1002    id2 = ((const MethodEntry*) meth2)->methodId;
1003    if (id1 < id2)
1004        return -1;
1005    if (id1 > id2)
1006        return 1;
1007    return 0;
1008}
1009
1010void sortMethodList(DataKeys* pKeys)
1011{
1012    qsort(pKeys->methods, pKeys->numMethods, sizeof(MethodEntry),
1013        compareMethods);
1014}
1015
1016/*
1017 * Parse the key section, and return a copy of the parsed contents.
1018 */
1019DataKeys* parseKeys(FILE *fp, int verbose)
1020{
1021    DataKeys* pKeys = NULL;
1022    long offset;
1023    int i;
1024
1025    pKeys = (DataKeys*) calloc(1, sizeof(DataKeys));
1026    if (pKeys == NULL)
1027        goto fail;
1028
1029    /*
1030     * We load the entire file into memory.  We do this, rather than memory-
1031     * mapping it, because we want to change some whitespace to NULs.
1032     */
1033    if (fseek(fp, 0L, SEEK_END) != 0) {
1034        perror("fseek");
1035        goto fail;
1036    }
1037    pKeys->fileLen = ftell(fp);
1038    if (pKeys->fileLen == 0) {
1039        fprintf(stderr, "Key file is empty.\n");
1040        goto fail;
1041    }
1042    rewind(fp);
1043
1044    pKeys->fileData = (char*) malloc(pKeys->fileLen);
1045    if (pKeys->fileData == NULL) {
1046        fprintf(stderr, "ERROR: unable to alloc %ld bytes\n", pKeys->fileLen);
1047        goto fail;
1048    }
1049
1050    if (fread(pKeys->fileData, 1, pKeys->fileLen, fp) != (size_t) pKeys->fileLen)
1051    {
1052        fprintf(stderr, "ERROR: unable to read %ld bytes from trace file\n",
1053            pKeys->fileLen);
1054        goto fail;
1055    }
1056
1057    offset = 0;
1058
1059    offset = parseVersion(pKeys, offset, verbose);
1060    offset = parseThreads(pKeys, offset);
1061    offset = parseMethods(pKeys, offset);
1062    offset = parseEnd(pKeys, offset);
1063    if (offset < 0)
1064        goto fail;
1065
1066    /* Leave fp pointing to the beginning of the data section. */
1067    fseek(fp, offset, SEEK_SET);
1068
1069    sortThreadList(pKeys);
1070    sortMethodList(pKeys);
1071
1072    /*
1073     * Dump list of threads.
1074     */
1075    if (verbose) {
1076        printf("Threads (%d):\n", pKeys->numThreads);
1077        for (i = 0; i < pKeys->numThreads; i++) {
1078            printf("%2d %s\n",
1079                   pKeys->threads[i].threadId, pKeys->threads[i].threadName);
1080        }
1081    }
1082
1083#if 0
1084    /*
1085     * Dump list of methods.
1086     */
1087    if (verbose) {
1088        printf("Methods (%d):\n", pKeys->numMethods);
1089        for (i = 0; i < pKeys->numMethods; i++) {
1090            printf("0x%08x %s : %s : %s\n",
1091                   pKeys->methods[i].methodId >> 2, pKeys->methods[i].className,
1092                   pKeys->methods[i].methodName, pKeys->methods[i].signature);
1093        }
1094    }
1095#endif
1096
1097    return pKeys;
1098
1099fail:
1100    freeDataKeys(pKeys);
1101    return NULL;
1102}
1103
1104
1105/*
1106 * Read values from the binary data file.
1107 */
1108
1109/* Make the return value "unsigned int" instead of "unsigned short" so that
1110 * we can detect EOF.
1111 */
1112unsigned int read2LE(FILE* fp)
1113{
1114    unsigned int val;
1115
1116    val = getc(fp);
1117    val |= getc(fp) << 8;
1118    return val;
1119}
1120unsigned int read4LE(FILE* fp)
1121{
1122    unsigned int val;
1123
1124    val = getc(fp);
1125    val |= getc(fp) << 8;
1126    val |= getc(fp) << 16;
1127    val |= getc(fp) << 24;
1128    return val;
1129}
1130unsigned long long read8LE(FILE* fp)
1131{
1132    unsigned long long val;
1133
1134    val = getc(fp);
1135    val |= (unsigned long long) getc(fp) << 8;
1136    val |= (unsigned long long) getc(fp) << 16;
1137    val |= (unsigned long long) getc(fp) << 24;
1138    val |= (unsigned long long) getc(fp) << 32;
1139    val |= (unsigned long long) getc(fp) << 40;
1140    val |= (unsigned long long) getc(fp) << 48;
1141    val |= (unsigned long long) getc(fp) << 56;
1142    return val;
1143}
1144
1145/*
1146 * Parse the header of the data section.
1147 *
1148 * Returns with the file positioned at the start of the record data.
1149 */
1150int parseDataHeader(FILE *fp, DataHeader* pHeader)
1151{
1152    int bytesToRead;
1153
1154    pHeader->magic = read4LE(fp);
1155    pHeader->version = read2LE(fp);
1156    pHeader->offsetToData = read2LE(fp);
1157    pHeader->startWhen = read8LE(fp);
1158    bytesToRead = pHeader->offsetToData - 16;
1159    if (pHeader->version == 1) {
1160        pHeader->recordSize = 9;
1161    } else if (pHeader->version == 2) {
1162        pHeader->recordSize = 10;
1163    } else if (pHeader->version == 3) {
1164        pHeader->recordSize = read2LE(fp);
1165        bytesToRead -= 2;
1166    } else {
1167        fprintf(stderr, "Unsupported trace file version: %d\n", pHeader->version);
1168        return -1;
1169    }
1170
1171    if (fseek(fp, bytesToRead, SEEK_CUR) != 0) {
1172        return -1;
1173    }
1174
1175    return 0;
1176}
1177
1178/*
1179 * Look up a method by its method ID (using binary search).
1180 *
1181 * Returns NULL if no matching method was found.
1182 */
1183MethodEntry* lookupMethod(DataKeys* pKeys, unsigned int methodId)
1184{
1185    int hi, lo, mid;
1186    unsigned int id;
1187    int hashedId;
1188
1189    /* Create cache if it doesn't already exist */
1190    if (pKeys->methodCache == NULL) {
1191        pKeys->methodCache = (int*) calloc(METHOD_CACHE_SIZE, sizeof(int));
1192    }
1193
1194    // ids are multiples of 4, so shift
1195    hashedId = (methodId >> 2) & METHOD_CACHE_SIZE_MASK;
1196    if (pKeys->methodCache[hashedId]) /* cache hit */
1197        if (pKeys->methods[pKeys->methodCache[hashedId]].methodId == methodId)
1198	    return &pKeys->methods[pKeys->methodCache[hashedId]];
1199
1200    lo = 0;
1201    hi = pKeys->numMethods - 1;
1202
1203    while (hi >= lo) {
1204        mid = (hi + lo) / 2;
1205
1206        id = pKeys->methods[mid].methodId;
1207        if (id == methodId) {         /* match, put in cache */
1208	    hashedId = (methodId >> 2) & METHOD_CACHE_SIZE_MASK;
1209	    pKeys->methodCache[hashedId] = mid;
1210	    return &pKeys->methods[mid];
1211	} else if (id < methodId)       /* too low */
1212            lo = mid + 1;
1213        else                          /* too high */
1214            hi = mid - 1;
1215    }
1216
1217    return NULL;
1218}
1219
1220/*
1221 * Reads the next data record, and assigns the data values to threadId,
1222 * methodVal and elapsedTime.  On end-of-file, the threadId, methodVal,
1223 * and elapsedTime are unchanged.  Returns 1 on end-of-file, otherwise
1224 * returns 0.
1225 */
1226int readDataRecord(FILE *dataFp, DataHeader* dataHeader,
1227        int *threadId, unsigned int *methodVal, uint64_t *elapsedTime)
1228{
1229    int id;
1230    int bytesToRead;
1231
1232    bytesToRead = dataHeader->recordSize;
1233    if (dataHeader->version == 1) {
1234        id = getc(dataFp);
1235        bytesToRead -= 1;
1236    } else {
1237        id = read2LE(dataFp);
1238        bytesToRead -= 2;
1239    }
1240    if (id == EOF)
1241        return 1;
1242    *threadId = id;
1243
1244    *methodVal = read4LE(dataFp);
1245    *elapsedTime = read4LE(dataFp);
1246    bytesToRead -= 8;
1247
1248    while (bytesToRead-- > 0) {
1249        getc(dataFp);
1250    }
1251
1252    if (feof(dataFp)) {
1253        fprintf(stderr, "WARNING: hit EOF mid-record\n");
1254        return 1;
1255    }
1256    return 0;
1257}
1258
1259/*
1260 * Read the key file and use it to produce formatted output from the
1261 * data file.
1262 */
1263void dumpTrace()
1264{
1265    static const char* actionStr[] = { "ent", "xit", "unr", "???" };
1266    MethodEntry bogusMethod = { 0, "???", "???", "???", "???", -1, 0, 0, 0, 0,
1267                                {NULL, NULL}, {NULL, NULL}, {0, 0}, 0, 0, -1 };
1268    char bogusBuf[80];
1269    char spaces[MAX_STACK_DEPTH+1];
1270    FILE* dataFp = NULL;
1271    DataHeader dataHeader;
1272    DataKeys* pKeys = NULL;
1273    int i;
1274    TraceData traceData;
1275
1276    //printf("Dumping '%s' '%s'\n", dataFileName, keyFileName);
1277
1278    memset(spaces, '.', MAX_STACK_DEPTH);
1279    spaces[MAX_STACK_DEPTH] = '\0';
1280
1281    for (i = 0; i < MAX_THREADS; i++)
1282        traceData.depth[i] = 2;       // adjust for return from start function
1283
1284    dataFp = fopen(gOptions.traceFileName, "r");
1285    if (dataFp == NULL)
1286        goto bail;
1287
1288    if ((pKeys = parseKeys(dataFp, 1)) == NULL)
1289        goto bail;
1290
1291    if (parseDataHeader(dataFp, &dataHeader) < 0)
1292        goto bail;
1293
1294    printf("Trace (threadID action usecs class.method signature):\n");
1295
1296    while (1) {
1297        MethodEntry* method;
1298        int threadId;
1299        unsigned int methodVal;
1300        uint64_t elapsedTime;
1301        int action, printDepth;
1302        unsigned int methodId, lastEnter = 0;
1303        int mismatch = 0;
1304        char depthNote;
1305
1306        /*
1307         * Extract values from file.
1308         */
1309        if (readDataRecord(dataFp, &dataHeader, &threadId, &methodVal, &elapsedTime))
1310            break;
1311
1312        action = METHOD_ACTION(methodVal);
1313        methodId = METHOD_ID(methodVal);
1314
1315        /*
1316         * Generate a line of output.
1317         */
1318        if (action == METHOD_TRACE_ENTER) {
1319            traceData.depth[threadId]++;
1320            lastEnter = methodId;
1321        } else {
1322            /* quick test for mismatched adjacent enter/exit */
1323            if (lastEnter != 0 && lastEnter != methodId)
1324                mismatch = 1;
1325        }
1326
1327        printDepth = traceData.depth[threadId];
1328        depthNote = ' ';
1329        if (printDepth < 0) {
1330            printDepth = 0;
1331            depthNote = '-';
1332        } else if (printDepth > MAX_STACK_DEPTH) {
1333            printDepth = MAX_STACK_DEPTH;
1334            depthNote = '+';
1335        }
1336
1337        method = lookupMethod(pKeys, methodId);
1338        if (method == NULL) {
1339            method = &bogusMethod;
1340            sprintf(bogusBuf, "methodId: 0x%x", methodId);
1341            method->signature = bogusBuf;
1342        }
1343
1344	if (method->methodName) {
1345	    printf("%2d %s%c %8lld%c%s%s.%s %s\n", threadId,
1346		   actionStr[action], mismatch ? '!' : ' ',
1347		   elapsedTime, depthNote,
1348		   spaces + (MAX_STACK_DEPTH - printDepth),
1349		   method->className, method->methodName, method->signature);
1350	} else {
1351	    printf("%2d %s%c %8lld%c%s%s\n", threadId,
1352		   actionStr[action], mismatch ? '!' : ' ',
1353		   elapsedTime, depthNote,
1354		   spaces + (MAX_STACK_DEPTH - printDepth),
1355		   method->className);
1356	}
1357
1358        if (action != METHOD_TRACE_ENTER) {
1359            traceData.depth[threadId]--;  /* METHOD_TRACE_EXIT or METHOD_TRACE_UNROLL */
1360            lastEnter = 0;
1361        }
1362
1363        mismatch = 0;
1364    }
1365
1366bail:
1367    if (dataFp != NULL)
1368        fclose(dataFp);
1369    if (pKeys != NULL)
1370        freeDataKeys(pKeys);
1371}
1372
1373/* This routine adds the given time to the parent and child methods.
1374 * This is called when the child routine exits, after the child has
1375 * been popped from the stack.  The elapsedTime parameter is the
1376 * duration of the child routine, including time spent in called routines.
1377 */
1378void addInclusiveTime(MethodEntry *parent, MethodEntry *child,
1379                      uint64_t elapsedTime)
1380{
1381    TimedMethod *pTimed;
1382
1383#if 0
1384    bool verbose = false;
1385    if (strcmp(child->className, debugClassName) == 0)
1386        verbose = true;
1387#endif
1388
1389    int childIsRecursive = (child->recursiveEntries > 0);
1390    int parentIsRecursive = (parent->recursiveEntries > 1);
1391
1392    if (child->recursiveEntries == 0) {
1393        child->elapsedInclusive += elapsedTime;
1394    } else if (child->recursiveEntries == 1) {
1395        child->recursiveInclusive += elapsedTime;
1396    }
1397    child->numCalls[childIsRecursive] += 1;
1398
1399#if 0
1400    if (verbose) {
1401        fprintf(stderr,
1402                "%s %d elapsedTime: %lld eI: %lld, rI: %lld\n",
1403                child->className, child->recursiveEntries,
1404                elapsedTime, child->elapsedInclusive,
1405                child->recursiveInclusive);
1406    }
1407#endif
1408
1409    /* Find the child method in the parent */
1410    TimedMethod *children = parent->children[parentIsRecursive];
1411    for (pTimed = children; pTimed; pTimed = pTimed->next) {
1412        if (pTimed->method == child) {
1413            pTimed->elapsedInclusive += elapsedTime;
1414            pTimed->numCalls += 1;
1415            break;
1416        }
1417    }
1418    if (pTimed == NULL) {
1419        /* Allocate a new TimedMethod */
1420        pTimed = (TimedMethod *) malloc(sizeof(TimedMethod));
1421        pTimed->elapsedInclusive = elapsedTime;
1422        pTimed->numCalls = 1;
1423        pTimed->method = child;
1424
1425        /* Add it to the front of the list */
1426        pTimed->next = children;
1427        parent->children[parentIsRecursive] = pTimed;
1428    }
1429
1430    /* Find the parent method in the child */
1431    TimedMethod *parents = child->parents[childIsRecursive];
1432    for (pTimed = parents; pTimed; pTimed = pTimed->next) {
1433        if (pTimed->method == parent) {
1434            pTimed->elapsedInclusive += elapsedTime;
1435            pTimed->numCalls += 1;
1436            break;
1437        }
1438    }
1439    if (pTimed == NULL) {
1440        /* Allocate a new TimedMethod */
1441        pTimed = (TimedMethod *) malloc(sizeof(TimedMethod));
1442        pTimed->elapsedInclusive = elapsedTime;
1443        pTimed->numCalls = 1;
1444        pTimed->method = parent;
1445
1446        /* Add it to the front of the list */
1447        pTimed->next = parents;
1448        child->parents[childIsRecursive] = pTimed;
1449    }
1450
1451#if 0
1452    if (verbose) {
1453        fprintf(stderr,
1454                "  %s %d eI: %lld\n",
1455                parent->className, parent->recursiveEntries,
1456                pTimed->elapsedInclusive);
1457    }
1458#endif
1459}
1460
1461/* Sorts a linked list and returns a newly allocated array containing
1462 * the sorted entries.
1463 */
1464TimedMethod *sortTimedMethodList(TimedMethod *list, int *num)
1465{
1466    int ii;
1467    TimedMethod *pTimed, *sorted;
1468
1469    /* Count the elements */
1470    int num_entries = 0;
1471    for (pTimed = list; pTimed; pTimed = pTimed->next)
1472        num_entries += 1;
1473    *num = num_entries;
1474    if (num_entries == 0)
1475        return NULL;
1476
1477    /* Copy all the list elements to a new array and sort them */
1478    sorted = (TimedMethod *) malloc(sizeof(TimedMethod) * num_entries);
1479    for (ii = 0, pTimed = list; pTimed; pTimed = pTimed->next, ++ii)
1480        memcpy(&sorted[ii], pTimed, sizeof(TimedMethod));
1481    qsort(sorted, num_entries, sizeof(TimedMethod), compareTimedMethod);
1482
1483    /* Fix up the "next" pointers so that they work. */
1484    for (ii = 0; ii < num_entries - 1; ++ii)
1485        sorted[ii].next = &sorted[ii + 1];
1486    sorted[num_entries - 1].next = NULL;
1487
1488    return sorted;
1489}
1490
1491/* Define flag values for printInclusiveMethod() */
1492static const int kIsRecursive = 1;
1493
1494/* This prints the inclusive stats for all the parents or children of a
1495 * method, depending on the list that is passed in.
1496 */
1497void printInclusiveMethod(MethodEntry *method, TimedMethod *list, int numCalls,
1498                          int flags)
1499{
1500    int num;
1501    TimedMethod *pTimed;
1502    char buf[80];
1503    char *anchor_close;
1504    char *spaces = "      ";    /* 6 spaces */
1505    int num_spaces = strlen(spaces);
1506    char *space_ptr = &spaces[num_spaces];
1507    char *className, *methodName, *signature;
1508    char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
1509    char signatureBuf[HTML_BUFSIZE];
1510
1511    anchor_close = "";
1512    if (gOptions.outputHtml)
1513        anchor_close = "</a>";
1514
1515    TimedMethod *sorted = sortTimedMethodList(list,  &num);
1516    double methodTotal = method->elapsedInclusive;
1517    for (pTimed = sorted; pTimed; pTimed = pTimed->next) {
1518        MethodEntry *relative = pTimed->method;
1519        className = (char*)(relative->className);
1520        methodName = (char*)(relative->methodName);
1521        signature = (char*)(relative->signature);
1522        double per = 100.0 * pTimed->elapsedInclusive / methodTotal;
1523        sprintf(buf, "[%d]", relative->index);
1524        if (gOptions.outputHtml) {
1525            int len = strlen(buf);
1526            if (len > num_spaces)
1527                len = num_spaces;
1528            sprintf(buf, "<a href=\"#m%d\">[%d]",
1529                    relative->index, relative->index);
1530            space_ptr = &spaces[len];
1531            className = htmlEscape(className, classBuf, HTML_BUFSIZE);
1532            methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
1533            signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
1534        }
1535        int nCalls = numCalls;
1536        if (nCalls == 0)
1537            nCalls = relative->numCalls[0] + relative->numCalls[1];
1538        if (relative->methodName) {
1539            if (flags & kIsRecursive) {
1540                // Don't display percentages for recursive functions
1541                printf("%6s %5s   %6s %s%6s%s %6d/%-6d %9llu %s.%s %s\n",
1542                       "", "", "",
1543                       space_ptr, buf, anchor_close,
1544                       pTimed->numCalls, nCalls,
1545                       pTimed->elapsedInclusive,
1546                       className, methodName, signature);
1547            } else {
1548                printf("%6s %5s   %5.1f%% %s%6s%s %6d/%-6d %9llu %s.%s %s\n",
1549                       "", "", per,
1550                       space_ptr, buf, anchor_close,
1551                       pTimed->numCalls, nCalls,
1552                       pTimed->elapsedInclusive,
1553                       className, methodName, signature);
1554            }
1555        } else {
1556            if (flags & kIsRecursive) {
1557                // Don't display percentages for recursive functions
1558                printf("%6s %5s   %6s %s%6s%s %6d/%-6d %9llu %s\n",
1559                       "", "", "",
1560                       space_ptr, buf, anchor_close,
1561                       pTimed->numCalls, nCalls,
1562                       pTimed->elapsedInclusive,
1563                       className);
1564            } else {
1565                printf("%6s %5s   %5.1f%% %s%6s%s %6d/%-6d %9llu %s\n",
1566                       "", "", per,
1567                       space_ptr, buf, anchor_close,
1568                       pTimed->numCalls, nCalls,
1569                       pTimed->elapsedInclusive,
1570                       className);
1571            }
1572        }
1573    }
1574}
1575
1576void countRecursiveEntries(CallStack *pStack, int top, MethodEntry *method)
1577{
1578    int ii;
1579
1580    method->recursiveEntries = 0;
1581    for (ii = 0; ii < top; ++ii) {
1582        if (pStack->calls[ii].method == method)
1583            method->recursiveEntries += 1;
1584    }
1585}
1586
1587void stackDump(CallStack *pStack, int top)
1588{
1589    int ii;
1590
1591    for (ii = 0; ii < top; ++ii) {
1592        MethodEntry *method = pStack->calls[ii].method;
1593        uint64_t entryTime = pStack->calls[ii].entryTime;
1594        if (method->methodName) {
1595            fprintf(stderr, "  %2d: %8llu %s.%s %s\n", ii, entryTime,
1596                   method->className, method->methodName, method->signature);
1597        } else {
1598            fprintf(stderr, "  %2d: %8llu %s\n", ii, entryTime, method->className);
1599        }
1600    }
1601}
1602
1603void outputTableOfContents()
1604{
1605    printf("<a name=\"contents\"></a>\n");
1606    printf("<h2>Table of Contents</h2>\n");
1607    printf("<ul>\n");
1608    printf("  <li><a href=\"#exclusive\">Exclusive profile</a></li>\n");
1609    printf("  <li><a href=\"#inclusive\">Inclusive profile</a></li>\n");
1610    printf("  <li><a href=\"#thread\">Thread profile</a></li>\n");
1611    printf("  <li><a href=\"#class\">Class/method profile</a></li>\n");
1612    printf("  <li><a href=\"#method\">Method/class profile</a></li>\n");
1613    printf("</ul>\n\n");
1614}
1615
1616void outputNavigationBar()
1617{
1618    printf("<a href=\"#contents\">[Top]</a>\n");
1619    printf("<a href=\"#exclusive\">[Exclusive]</a>\n");
1620    printf("<a href=\"#inclusive\">[Inclusive]</a>\n");
1621    printf("<a href=\"#thread\">[Thread]</a>\n");
1622    printf("<a href=\"#class\">[Class]</a>\n");
1623    printf("<a href=\"#method\">[Method]</a>\n");
1624    printf("<br><br>\n");
1625}
1626
1627void printExclusiveProfile(MethodEntry **pMethods, int numMethods,
1628                           uint64_t sumThreadTime)
1629{
1630    int ii;
1631    MethodEntry* method;
1632    double total, sum, per, sum_per;
1633    char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
1634    char signatureBuf[HTML_BUFSIZE];
1635    char anchor_buf[80];
1636    char *anchor_close = "";
1637
1638    total = sumThreadTime;
1639    anchor_buf[0] = 0;
1640    if (gOptions.outputHtml) {
1641        anchor_close = "</a>";
1642        printf("<a name=\"exclusive\"></a>\n");
1643        printf("<hr>\n");
1644        outputNavigationBar();
1645    } else {
1646        printf("\n%s\n", profileSeparator);
1647    }
1648
1649    /* First, sort the methods into decreasing order of inclusive
1650     * elapsed time so that we can assign the method indices.
1651     */
1652    qsort(pMethods, numMethods, sizeof(MethodEntry*), compareElapsedInclusive);
1653
1654    for (ii = 0; ii < numMethods; ++ii)
1655        pMethods[ii]->index = ii;
1656
1657    /* Sort the methods into decreasing order of exclusive elapsed time.
1658     */
1659    qsort(pMethods, numMethods, sizeof(MethodEntry*),
1660          compareElapsedExclusive);
1661
1662    printf("Total cycles: %llu\n\n", sumThreadTime);
1663    if (gOptions.outputHtml) {
1664        printf("<br><br>\n");
1665    }
1666    printf("Exclusive elapsed times for each method, not including time spent in\n");
1667    printf("children, sorted by exclusive time.\n\n");
1668    if (gOptions.outputHtml) {
1669        printf("<br><br>\n<pre>\n");
1670    }
1671
1672    printf("    Usecs  self %%  sum %%  Method\n");
1673    sum = 0;
1674
1675    for (ii = 0; ii < numMethods; ++ii) {
1676        char *className, *methodName, *signature;
1677
1678        method = pMethods[ii];
1679        /* Don't show methods with zero cycles */
1680        if (method->elapsedExclusive == 0)
1681            break;
1682        className = (char*)(method->className);
1683        methodName = (char*)(method->methodName);
1684        signature = (char*)(method->signature);
1685        sum += method->elapsedExclusive;
1686        per = 100.0 * method->elapsedExclusive / total;
1687        sum_per = 100.0 * sum / total;
1688        if (gOptions.outputHtml) {
1689            sprintf(anchor_buf, "<a href=\"#m%d\">", method->index);
1690            className = htmlEscape(className, classBuf, HTML_BUFSIZE);
1691            methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
1692            signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
1693        }
1694        if (method->methodName) {
1695            printf("%9llu  %6.2f %6.2f  %s[%d]%s %s.%s %s\n",
1696                   method->elapsedExclusive, per, sum_per,
1697                   anchor_buf, method->index, anchor_close,
1698                   className, methodName, signature);
1699        } else {
1700            printf("%9llu  %6.2f %6.2f  %s[%d]%s %s\n",
1701                   method->elapsedExclusive, per, sum_per,
1702                   anchor_buf, method->index, anchor_close,
1703                   className);
1704        }
1705    }
1706    if (gOptions.outputHtml) {
1707        printf("</pre>\n");
1708    }
1709}
1710
1711/* check to make sure that the child method meets the threshold of the parent */
1712int checkThreshold(MethodEntry* parent, MethodEntry* child)
1713{
1714    double parentTime = parent->elapsedInclusive;
1715    double childTime = child->elapsedInclusive;
1716    int64_t percentage = (childTime / parentTime) * 100.0;
1717    return (percentage < gOptions.threshold) ? 0 : 1;
1718}
1719
1720void createLabels(FILE* file, MethodEntry* method)
1721{
1722    fprintf(file, "node%d[label = \"[%d] %s.%s (%llu, %llu, %d)\"]\n",
1723             method->index, method->index, method->className, method->methodName,
1724             method->elapsedInclusive / 1000,
1725             method->elapsedExclusive / 1000,
1726             method->numCalls[0]);
1727
1728    method->graphState = GRAPH_LABEL_VISITED;
1729
1730    TimedMethod* child;
1731    for (child = method->children[0] ; child ; child = child->next) {
1732        MethodEntry* childMethod = child->method;
1733
1734        if ((childMethod->graphState & GRAPH_LABEL_VISITED) == 0 && checkThreshold(method, childMethod)) {
1735            createLabels(file, child->method);
1736        }
1737    }
1738}
1739
1740void createLinks(FILE* file, MethodEntry* method)
1741{
1742    method->graphState |= GRAPH_NODE_VISITED;
1743
1744    TimedMethod* child;
1745    for (child = method->children[0] ; child ; child = child->next) {
1746        MethodEntry* childMethod = child->method;
1747        if (checkThreshold(method, child->method)) {
1748            fprintf(file, "node%d -> node%d\n", method->index, child->method->index);
1749            // only visit children that haven't been visited before
1750            if ((childMethod->graphState & GRAPH_NODE_VISITED) == 0) {
1751                createLinks(file, child->method);
1752            }
1753        }
1754    }
1755}
1756
1757void createInclusiveProfileGraphNew(DataKeys* dataKeys)
1758{
1759    // create a temporary file in /tmp
1760    char path[FILENAME_MAX];
1761    if (gOptions.keepDotFile) {
1762        snprintf(path, FILENAME_MAX, "%s.dot", gOptions.graphFileName);
1763    } else {
1764        snprintf(path, FILENAME_MAX, "/tmp/dot-%d-%d.dot", (int)time(NULL), rand());
1765    }
1766
1767    FILE* file = fopen(path, "w+");
1768
1769    fprintf(file, "digraph g {\nnode [shape = record,height=.1];\n");
1770
1771    createLabels(file, dataKeys->methods);
1772    createLinks(file, dataKeys->methods);
1773
1774    fprintf(file, "}");
1775    fclose(file);
1776
1777    // now that we have the dot file generate the image
1778    char command[1024];
1779    snprintf(command, 1024, "dot -Tpng -o '%s' '%s'", gOptions.graphFileName, path);
1780
1781    system(command);
1782
1783    if (! gOptions.keepDotFile) {
1784        remove(path);
1785    }
1786}
1787
1788void printInclusiveProfile(MethodEntry **pMethods, int numMethods,
1789                           uint64_t sumThreadTime)
1790{
1791    int ii;
1792    MethodEntry* method;
1793    double total, sum, per, sum_per;
1794    char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
1795    char signatureBuf[HTML_BUFSIZE];
1796    char anchor_buf[80];
1797
1798    total = sumThreadTime;
1799    anchor_buf[0] = 0;
1800    if (gOptions.outputHtml) {
1801        printf("<a name=\"inclusive\"></a>\n");
1802        printf("<hr>\n");
1803        outputNavigationBar();
1804    } else {
1805        printf("\n%s\n", profileSeparator);
1806    }
1807
1808    /* Sort the methods into decreasing order of inclusive elapsed time. */
1809    qsort(pMethods, numMethods, sizeof(MethodEntry*),
1810          compareElapsedInclusive);
1811
1812    printf("\nInclusive elapsed times for each method and its parents and children,\n");
1813    printf("sorted by inclusive time.\n\n");
1814
1815    if (gOptions.outputHtml) {
1816        printf("<br><br>\n<pre>\n");
1817    }
1818
1819    printf("index  %%/total %%/self  index     calls         usecs name\n");
1820    for (ii = 0; ii < numMethods; ++ii) {
1821        int num;
1822        TimedMethod *pTimed;
1823        double excl_per;
1824        char buf[40];
1825        char *className, *methodName, *signature;
1826
1827        method = pMethods[ii];
1828        /* Don't show methods with zero cycles */
1829        if (method->elapsedInclusive == 0)
1830            break;
1831
1832        className = (char*)(method->className);
1833        methodName = (char*)(method->methodName);
1834        signature = (char*)(method->signature);
1835
1836        if (gOptions.outputHtml) {
1837            printf("<a name=\"m%d\"></a>", method->index);
1838            className = htmlEscape(className, classBuf, HTML_BUFSIZE);
1839            methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
1840            signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
1841        }
1842        printf("----------------------------------------------------\n");
1843
1844        /* Sort and print the parents */
1845        int numCalls = method->numCalls[0] + method->numCalls[1];
1846        printInclusiveMethod(method, method->parents[0], numCalls, 0);
1847        if (method->parents[1]) {
1848            printf("               +++++++++++++++++++++++++\n");
1849            printInclusiveMethod(method, method->parents[1], numCalls,
1850                                 kIsRecursive);
1851        }
1852
1853        per = 100.0 * method->elapsedInclusive / total;
1854        sprintf(buf, "[%d]", ii);
1855        if (method->methodName) {
1856            printf("%-6s %5.1f%%   %5s %6s %6d+%-6d %9llu %s.%s %s\n",
1857                   buf,
1858                   per, "", "", method->numCalls[0], method->numCalls[1],
1859                   method->elapsedInclusive,
1860                   className, methodName, signature);
1861        } else {
1862            printf("%-6s %5.1f%%   %5s %6s %6d+%-6d %9llu %s\n",
1863                   buf,
1864                   per, "", "", method->numCalls[0], method->numCalls[1],
1865                   method->elapsedInclusive,
1866                   className);
1867        }
1868        excl_per = 100.0 * method->topExclusive / method->elapsedInclusive;
1869        printf("%6s %5s   %5.1f%% %6s %6s %6s %9llu\n",
1870               "", "", excl_per, "excl", "", "", method->topExclusive);
1871
1872        /* Sort and print the children */
1873        printInclusiveMethod(method, method->children[0], 0, 0);
1874        if (method->children[1]) {
1875            printf("               +++++++++++++++++++++++++\n");
1876            printInclusiveMethod(method, method->children[1], 0,
1877                                 kIsRecursive);
1878        }
1879    }
1880    if (gOptions.outputHtml) {
1881        printf("</pre>\n");
1882    }
1883}
1884
1885void printThreadProfile(ThreadEntry *pThreads, int numThreads, uint64_t sumThreadTime, Filter** filters)
1886{
1887    int ii, jj;
1888    ThreadEntry thread;
1889    double total, per, sum_per;
1890    uint64_t sum;
1891    char threadBuf[HTML_BUFSIZE];
1892    char anchor_buf[80];
1893    int drawTable;
1894
1895    total = sumThreadTime;
1896    anchor_buf[0] = 0;
1897    if (gOptions.outputHtml) {
1898        printf("<a name=\"thread\"></a>\n");
1899        printf("<hr>\n");
1900        outputNavigationBar();
1901    } else {
1902        printf("\n%s\n", profileSeparator);
1903    }
1904
1905    /* Sort the threads into decreasing order of elapsed time. */
1906    qsort(pThreads, numThreads, sizeof(ThreadEntry), compareElapsed);
1907
1908    printf("\nElapsed times for each thread, sorted by elapsed time.\n");
1909    printf("Also includes percentage of time spent during the <i>execution</i> of any filters.\n\n");
1910
1911    if (gOptions.outputHtml) {
1912        printf("<br><br>\n<pre>\n");
1913    }
1914
1915    printf("    Usecs   self %%  sum %%");
1916    for (ii = 0; ii < numFilters; ++ii) {
1917        printf("  %s %%", filters[ii]->filterName);
1918    }
1919    printf("  tid   ThreadName\n");
1920    sum = 0;
1921
1922    for (ii = 0; ii < numThreads; ++ii) {
1923        int threadId;
1924        char *threadName;
1925        uint64_t time;
1926
1927        thread = pThreads[ii];
1928
1929        threadId = thread.threadId;
1930        threadName = (char*)(thread.threadName);
1931        time = thread.elapsedTime;
1932
1933        sum += time;
1934        per = 100.0 * time / total;
1935        sum_per = 100.0 * sum / total;
1936
1937        if (gOptions.outputHtml) {
1938	    threadName = htmlEscape(threadName, threadBuf, HTML_BUFSIZE);
1939        }
1940
1941	printf("%9llu  %6.2f %6.2f", time, per, sum_per);
1942	for (jj = 0; jj < numFilters; jj++) {
1943	    printf(" %6.2f", 100.0 * filters[jj]->times.threadExecutionTimes[threadId] / time);
1944	}
1945	printf("    %3d %s\n", threadId, threadName);
1946    }
1947
1948    if (gOptions.outputHtml)
1949        printf("</pre><br />");
1950
1951    printf("\n\nBreak-down of portion of time spent by each thread while waiting on a filter method.\n");
1952
1953    for (ii = 0; ii < numFilters; ++ii) {
1954        // Draw a table for each filter that measures wait time
1955        drawTable = 0;
1956	for (jj = 0; jj < filters[ii]->numKeys; jj++)
1957	    if (filters[ii]->filterKeys[jj].flags == 1)
1958	        drawTable = 1;
1959
1960	if (drawTable) {
1961
1962	    if (gOptions.outputHtml)
1963	        printf("<br/><br/>\n<pre>\n");
1964	    printf("Filter: %s\n", filters[ii]->filterName);
1965	    printf("Total waiting cycles: %llu (%6.2f%% of total)\n",
1966		   filters[ii]->times.totalWaitTime,
1967		   100.0 * filters[ii]->times.totalWaitTime / sum);
1968
1969	    if (filters[ii]->times.totalWaitTime > 0) {
1970
1971	        printf("Details: \n\n");
1972
1973		printf(" Waiting cycles    %% of total waiting time   execution time while waiting    thread name\n");
1974
1975		for (jj = 0; jj < numThreads; jj++) {
1976
1977		    thread = pThreads[jj];
1978
1979		    char *threadName;
1980		    threadName = (char*) thread.threadName;
1981		    if (gOptions.outputHtml) {
1982		        threadName = htmlEscape(threadName, threadBuf, HTML_BUFSIZE);
1983		    }
1984
1985		    printf(" %9llu                   %6.2f                     %6.2f               %s\n",
1986			   filters[ii]->times.threadWaitTimes[thread.threadId],
1987			   100.0 * filters[ii]->times.threadWaitTimes[thread.threadId] / filters[ii]->times.totalWaitTime,
1988			   100.0 * filters[ii]->times.threadExecutionTimesWhileWaiting[thread.threadId] / filters[ii]->times.totalWaitTime,
1989			   threadName);
1990		}
1991	    }
1992
1993	    if (gOptions.outputHtml)
1994	        printf("</pre>\n");
1995
1996	}
1997    }
1998
1999}
2000
2001void createClassList(TraceData* traceData, MethodEntry **pMethods, int numMethods)
2002{
2003    int ii;
2004
2005    /* Sort the methods into alphabetical order to find the unique class
2006     * names.
2007     */
2008    qsort(pMethods, numMethods, sizeof(MethodEntry*), compareClassNames);
2009
2010    /* Count the number of unique class names. */
2011    const char *currentClassName = "";
2012    const char *firstClassName = NULL;
2013    traceData->numClasses = 0;
2014    for (ii = 0; ii < numMethods; ++ii) {
2015        if (pMethods[ii]->methodName == NULL) {
2016            continue;
2017        }
2018        if (strcmp(pMethods[ii]->className, currentClassName) != 0) {
2019            // Remember the first one
2020            if (firstClassName == NULL) {
2021                firstClassName = pMethods[ii]->className;
2022            }
2023            traceData->numClasses += 1;
2024            currentClassName = pMethods[ii]->className;
2025        }
2026    }
2027
2028    if (traceData->numClasses == 0) {
2029        traceData->classes = NULL;
2030        return;
2031    }
2032
2033    /* Allocate space for all of the unique class names */
2034    traceData->classes = (ClassEntry *) malloc(sizeof(ClassEntry) * traceData->numClasses);
2035
2036    /* Initialize the classes array */
2037    memset(traceData->classes, 0, sizeof(ClassEntry) * traceData->numClasses);
2038    ClassEntry *pClass = traceData->classes;
2039    pClass->className = currentClassName = firstClassName;
2040    int prevNumMethods = 0;
2041    for (ii = 0; ii < numMethods; ++ii) {
2042        if (pMethods[ii]->methodName == NULL) {
2043            continue;
2044        }
2045        if (strcmp(pMethods[ii]->className, currentClassName) != 0) {
2046            pClass->numMethods = prevNumMethods;
2047            (++pClass)->className = currentClassName = pMethods[ii]->className;
2048            prevNumMethods = 0;
2049        }
2050        prevNumMethods += 1;
2051    }
2052    pClass->numMethods = prevNumMethods;
2053
2054    /* Create the array of MethodEntry pointers for each class */
2055    pClass = NULL;
2056    currentClassName = "";
2057    int nextMethod = 0;
2058    for (ii = 0; ii < numMethods; ++ii) {
2059        if (pMethods[ii]->methodName == NULL) {
2060            continue;
2061        }
2062        if (strcmp(pMethods[ii]->className, currentClassName) != 0) {
2063            currentClassName = pMethods[ii]->className;
2064            if (pClass == NULL)
2065                pClass = traceData->classes;
2066            else
2067                pClass++;
2068            /* Allocate space for the methods array */
2069            int nbytes = sizeof(MethodEntry*) * pClass->numMethods;
2070            pClass->methods = (MethodEntry**) malloc(nbytes);
2071            nextMethod = 0;
2072        }
2073        pClass->methods[nextMethod++] = pMethods[ii];
2074    }
2075}
2076
2077/* Prints a number of html non-breaking spaces according so that the length
2078 * of the string "buf" is at least "width" characters wide.  If width is
2079 * negative, then trailing spaces are added instead of leading spaces.
2080 */
2081void printHtmlField(char *buf, int width)
2082{
2083    int ii;
2084
2085    int leadingSpaces = 1;
2086    if (width < 0) {
2087        width = -width;
2088        leadingSpaces = 0;
2089    }
2090    int len = strlen(buf);
2091    int numSpaces = width - len;
2092    if (numSpaces <= 0) {
2093        printf("%s", buf);
2094        return;
2095    }
2096    if (leadingSpaces == 0)
2097        printf("%s", buf);
2098    for (ii = 0; ii < numSpaces; ++ii)
2099        printf("&nbsp;");
2100    if (leadingSpaces == 1)
2101        printf("%s", buf);
2102}
2103
2104void printClassProfiles(TraceData* traceData, uint64_t sumThreadTime)
2105{
2106    int ii, jj;
2107    MethodEntry* method;
2108    double total, sum, per, sum_per;
2109    char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
2110    char signatureBuf[HTML_BUFSIZE];
2111
2112    total = sumThreadTime;
2113    if (gOptions.outputHtml) {
2114        printf("<a name=\"class\"></a>\n");
2115        printf("<hr>\n");
2116        outputNavigationBar();
2117    } else {
2118        printf("\n%s\n", profileSeparator);
2119    }
2120
2121    if (traceData->numClasses == 0) {
2122        printf("\nNo classes.\n");
2123        if (gOptions.outputHtml) {
2124            printf("<br><br>\n");
2125        }
2126        return;
2127    }
2128
2129    printf("\nExclusive elapsed time for each class, summed over all the methods\n");
2130    printf("in the class.\n\n");
2131    if (gOptions.outputHtml) {
2132        printf("<br><br>\n");
2133    }
2134
2135    /* For each class, sum the exclusive times in all of the methods
2136     * in that class.  Also sum the number of method calls.  Also
2137     * sort the methods so the most expensive appear at the top.
2138     */
2139    ClassEntry *pClass = traceData->classes;
2140    for (ii = 0; ii < traceData->numClasses; ++ii, ++pClass) {
2141        //printf("%s %d methods\n", pClass->className, pClass->numMethods);
2142        int numMethods = pClass->numMethods;
2143        for (jj = 0; jj < numMethods; ++jj) {
2144            method = pClass->methods[jj];
2145            pClass->elapsedExclusive += method->elapsedExclusive;
2146            pClass->numCalls[0] += method->numCalls[0];
2147            pClass->numCalls[1] += method->numCalls[1];
2148        }
2149
2150        /* Sort the methods into decreasing order of exclusive time */
2151        qsort(pClass->methods, numMethods, sizeof(MethodEntry*),
2152              compareElapsedExclusive);
2153    }
2154
2155    /* Allocate an array of pointers to the classes for more efficient
2156     * sorting.
2157     */
2158    ClassEntry **pClasses;
2159    pClasses = (ClassEntry**) malloc(sizeof(ClassEntry*) * traceData->numClasses);
2160    for (ii = 0; ii < traceData->numClasses; ++ii)
2161        pClasses[ii] = &traceData->classes[ii];
2162
2163    /* Sort the classes into decreasing order of exclusive time */
2164    qsort(pClasses, traceData->numClasses, sizeof(ClassEntry*), compareClassExclusive);
2165
2166    if (gOptions.outputHtml) {
2167        printf("<div class=\"header\"><span class=\"parent\">&nbsp;</span>&nbsp;&nbsp;&nbsp;");
2168        printf("Cycles %%/total Cumul.%% &nbsp;Calls+Recur&nbsp; Class</div>\n");
2169    } else {
2170        printf("   Cycles %%/total Cumul.%%  Calls+Recur  Class\n");
2171    }
2172
2173    sum = 0;
2174    for (ii = 0; ii < traceData->numClasses; ++ii) {
2175        char *className, *methodName, *signature;
2176
2177        /* Skip classes with zero cycles */
2178        pClass = pClasses[ii];
2179        if (pClass->elapsedExclusive == 0)
2180            break;
2181
2182        per = 100.0 * pClass->elapsedExclusive / total;
2183        sum += pClass->elapsedExclusive;
2184        sum_per = 100.0 * sum / total;
2185        className = (char*)(pClass->className);
2186        if (gOptions.outputHtml) {
2187            char buf[80];
2188
2189            className = htmlEscape(className, classBuf, HTML_BUFSIZE);
2190            printf("<div class=\"link\" onClick=\"javascript:toggle('d%d')\" onMouseOver=\"javascript:onMouseOver(this)\" onMouseOut=\"javascript:onMouseOut(this)\"><span class=\"parent\" id=\"xd%d\">+</span>", ii, ii);
2191            sprintf(buf, "%llu", pClass->elapsedExclusive);
2192            printHtmlField(buf, 9);
2193            printf(" ");
2194            sprintf(buf, "%.1f", per);
2195            printHtmlField(buf, 7);
2196            printf(" ");
2197            sprintf(buf, "%.1f", sum_per);
2198            printHtmlField(buf, 7);
2199            printf(" ");
2200            sprintf(buf, "%d", pClass->numCalls[0]);
2201            printHtmlField(buf, 6);
2202            printf("+");
2203            sprintf(buf, "%d", pClass->numCalls[1]);
2204            printHtmlField(buf, -6);
2205            printf(" ");
2206            printf("%s", className);
2207            printf("</div>\n");
2208            printf("<div class=\"parent\" id=\"d%d\">\n", ii);
2209        } else {
2210            printf("---------------------------------------------\n");
2211            printf("%9llu %7.1f %7.1f %6d+%-6d %s\n",
2212                   pClass->elapsedExclusive, per, sum_per,
2213                   pClass->numCalls[0], pClass->numCalls[1],
2214                   className);
2215        }
2216
2217        int numMethods = pClass->numMethods;
2218        double classExclusive = pClass->elapsedExclusive;
2219        double sumMethods = 0;
2220        for (jj = 0; jj < numMethods; ++jj) {
2221            method = pClass->methods[jj];
2222            methodName = (char*)(method->methodName);
2223            signature = (char*)(method->signature);
2224            per = 100.0 * method->elapsedExclusive / classExclusive;
2225            sumMethods += method->elapsedExclusive;
2226            sum_per = 100.0 * sumMethods / classExclusive;
2227            if (gOptions.outputHtml) {
2228                char buf[80];
2229
2230                methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
2231                signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
2232                printf("<div class=\"leaf\"><span class=\"leaf\">&nbsp;</span>");
2233                sprintf(buf, "%llu", method->elapsedExclusive);
2234                printHtmlField(buf, 9);
2235                printf("&nbsp;");
2236                sprintf(buf, "%llu", method->elapsedInclusive);
2237                printHtmlField(buf, 9);
2238                printf("&nbsp;");
2239                sprintf(buf, "%.1f", per);
2240                printHtmlField(buf, 7);
2241                printf("&nbsp;");
2242                sprintf(buf, "%.1f", sum_per);
2243                printHtmlField(buf, 7);
2244                printf("&nbsp;");
2245                sprintf(buf, "%d", method->numCalls[0]);
2246                printHtmlField(buf, 6);
2247                printf("+");
2248                sprintf(buf, "%d", method->numCalls[1]);
2249                printHtmlField(buf, -6);
2250                printf("&nbsp;");
2251                printf("<a href=\"#m%d\">[%d]</a>&nbsp;%s&nbsp;%s",
2252                       method->index, method->index, methodName, signature);
2253                printf("</div>\n");
2254            } else {
2255                printf("%9llu %9llu %7.1f %7.1f %6d+%-6d [%d] %s %s\n",
2256                       method->elapsedExclusive,
2257                       method->elapsedInclusive,
2258                       per, sum_per,
2259                       method->numCalls[0], method->numCalls[1],
2260                       method->index, methodName, signature);
2261            }
2262        }
2263        if (gOptions.outputHtml) {
2264            printf("</div>\n");
2265        }
2266    }
2267}
2268
2269void createUniqueMethodList(TraceData* traceData, MethodEntry **pMethods, int numMethods)
2270{
2271    int ii;
2272
2273    /* Sort the methods into alphabetical order of method names
2274     * to find the unique method names.
2275     */
2276    qsort(pMethods, numMethods, sizeof(MethodEntry*), compareMethodNames);
2277
2278    /* Count the number of unique method names, ignoring class and
2279     * signature.
2280     */
2281    const char *currentMethodName = "";
2282    traceData->numUniqueMethods = 0;
2283    for (ii = 0; ii < numMethods; ++ii) {
2284        if (pMethods[ii]->methodName == NULL)
2285            continue;
2286        if (strcmp(pMethods[ii]->methodName, currentMethodName) != 0) {
2287            traceData->numUniqueMethods += 1;
2288            currentMethodName = pMethods[ii]->methodName;
2289        }
2290    }
2291    if (traceData->numUniqueMethods == 0)
2292        return;
2293
2294    /* Allocate space for pointers to all of the unique methods */
2295    int nbytes = sizeof(UniqueMethodEntry) * traceData->numUniqueMethods;
2296    traceData->uniqueMethods = (UniqueMethodEntry *) malloc(nbytes);
2297
2298    /* Initialize the uniqueMethods array */
2299    memset(traceData->uniqueMethods, 0, nbytes);
2300    UniqueMethodEntry *pUnique = traceData->uniqueMethods;
2301    currentMethodName = NULL;
2302    int prevNumMethods = 0;
2303    for (ii = 0; ii < numMethods; ++ii) {
2304        if (pMethods[ii]->methodName == NULL)
2305            continue;
2306        if (currentMethodName == NULL)
2307            currentMethodName = pMethods[ii]->methodName;
2308        if (strcmp(pMethods[ii]->methodName, currentMethodName) != 0) {
2309            currentMethodName = pMethods[ii]->methodName;
2310            pUnique->numMethods = prevNumMethods;
2311            pUnique++;
2312            prevNumMethods = 0;
2313        }
2314        prevNumMethods += 1;
2315    }
2316    pUnique->numMethods = prevNumMethods;
2317
2318    /* Create the array of MethodEntry pointers for each unique method */
2319    pUnique = NULL;
2320    currentMethodName = "";
2321    int nextMethod = 0;
2322    for (ii = 0; ii < numMethods; ++ii) {
2323        if (pMethods[ii]->methodName == NULL)
2324            continue;
2325        if (strcmp(pMethods[ii]->methodName, currentMethodName) != 0) {
2326            currentMethodName = pMethods[ii]->methodName;
2327            if (pUnique == NULL)
2328                pUnique = traceData->uniqueMethods;
2329            else
2330                pUnique++;
2331            /* Allocate space for the methods array */
2332            int nbytes = sizeof(MethodEntry*) * pUnique->numMethods;
2333            pUnique->methods = (MethodEntry**) malloc(nbytes);
2334            nextMethod = 0;
2335        }
2336        pUnique->methods[nextMethod++] = pMethods[ii];
2337    }
2338}
2339
2340void printMethodProfiles(TraceData* traceData, uint64_t sumThreadTime)
2341{
2342    int ii, jj;
2343    MethodEntry* method;
2344    double total, sum, per, sum_per;
2345    char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
2346    char signatureBuf[HTML_BUFSIZE];
2347
2348    if (traceData->numUniqueMethods == 0)
2349        return;
2350
2351    total = sumThreadTime;
2352    if (gOptions.outputHtml) {
2353        printf("<a name=\"method\"></a>\n");
2354        printf("<hr>\n");
2355        outputNavigationBar();
2356    } else {
2357        printf("\n%s\n", profileSeparator);
2358    }
2359
2360    printf("\nExclusive elapsed time for each method, summed over all the classes\n");
2361    printf("that contain a method with the same name.\n\n");
2362    if (gOptions.outputHtml) {
2363        printf("<br><br>\n");
2364    }
2365
2366    /* For each unique method, sum the exclusive times in all of the methods
2367     * with the same name.  Also sum the number of method calls.  Also
2368     * sort the methods so the most expensive appear at the top.
2369     */
2370    UniqueMethodEntry *pUnique = traceData->uniqueMethods;
2371    for (ii = 0; ii < traceData->numUniqueMethods; ++ii, ++pUnique) {
2372        int numMethods = pUnique->numMethods;
2373        for (jj = 0; jj < numMethods; ++jj) {
2374            method = pUnique->methods[jj];
2375            pUnique->elapsedExclusive += method->elapsedExclusive;
2376            pUnique->numCalls[0] += method->numCalls[0];
2377            pUnique->numCalls[1] += method->numCalls[1];
2378        }
2379
2380        /* Sort the methods into decreasing order of exclusive time */
2381        qsort(pUnique->methods, numMethods, sizeof(MethodEntry*),
2382              compareElapsedExclusive);
2383    }
2384
2385    /* Allocate an array of pointers to the methods for more efficient
2386     * sorting.
2387     */
2388    UniqueMethodEntry **pUniqueMethods;
2389    int nbytes = sizeof(UniqueMethodEntry*) * traceData->numUniqueMethods;
2390    pUniqueMethods = (UniqueMethodEntry**) malloc(nbytes);
2391    for (ii = 0; ii < traceData->numUniqueMethods; ++ii)
2392        pUniqueMethods[ii] = &traceData->uniqueMethods[ii];
2393
2394    /* Sort the methods into decreasing order of exclusive time */
2395    qsort(pUniqueMethods, traceData->numUniqueMethods, sizeof(UniqueMethodEntry*),
2396          compareUniqueExclusive);
2397
2398    if (gOptions.outputHtml) {
2399        printf("<div class=\"header\"><span class=\"parent\">&nbsp;</span>&nbsp;&nbsp;&nbsp;");
2400        printf("Cycles %%/total Cumul.%% &nbsp;Calls+Recur&nbsp; Method</div>\n");
2401    } else {
2402        printf("   Cycles %%/total Cumul.%%  Calls+Recur  Method\n");
2403    }
2404
2405    sum = 0;
2406    for (ii = 0; ii < traceData->numUniqueMethods; ++ii) {
2407        char *className, *methodName, *signature;
2408
2409        /* Skip methods with zero cycles */
2410        pUnique = pUniqueMethods[ii];
2411        if (pUnique->elapsedExclusive == 0)
2412            break;
2413
2414        per = 100.0 * pUnique->elapsedExclusive / total;
2415        sum += pUnique->elapsedExclusive;
2416        sum_per = 100.0 * sum / total;
2417        methodName = (char*)(pUnique->methods[0]->methodName);
2418        if (gOptions.outputHtml) {
2419            char buf[80];
2420
2421            methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
2422            printf("<div class=\"link\" onClick=\"javascript:toggle('e%d')\" onMouseOver=\"javascript:onMouseOver(this)\" onMouseOut=\"javascript:onMouseOut(this)\"><span class=\"parent\" id=\"xe%d\">+</span>", ii, ii);
2423            sprintf(buf, "%llu", pUnique->elapsedExclusive);
2424            printHtmlField(buf, 9);
2425            printf(" ");
2426            sprintf(buf, "%.1f", per);
2427            printHtmlField(buf, 7);
2428            printf(" ");
2429            sprintf(buf, "%.1f", sum_per);
2430            printHtmlField(buf, 7);
2431            printf(" ");
2432            sprintf(buf, "%d", pUnique->numCalls[0]);
2433            printHtmlField(buf, 6);
2434            printf("+");
2435            sprintf(buf, "%d", pUnique->numCalls[1]);
2436            printHtmlField(buf, -6);
2437            printf(" ");
2438            printf("%s", methodName);
2439            printf("</div>\n");
2440            printf("<div class=\"parent\" id=\"e%d\">\n", ii);
2441        } else {
2442            printf("---------------------------------------------\n");
2443            printf("%9llu %7.1f %7.1f %6d+%-6d %s\n",
2444                   pUnique->elapsedExclusive, per, sum_per,
2445                   pUnique->numCalls[0], pUnique->numCalls[1],
2446                   methodName);
2447        }
2448        int numMethods = pUnique->numMethods;
2449        double methodExclusive = pUnique->elapsedExclusive;
2450        double sumMethods = 0;
2451        for (jj = 0; jj < numMethods; ++jj) {
2452            method = pUnique->methods[jj];
2453            className = (char*)(method->className);
2454            signature = (char*)(method->signature);
2455            per = 100.0 * method->elapsedExclusive / methodExclusive;
2456            sumMethods += method->elapsedExclusive;
2457            sum_per = 100.0 * sumMethods / methodExclusive;
2458            if (gOptions.outputHtml) {
2459                char buf[80];
2460
2461                className = htmlEscape(className, classBuf, HTML_BUFSIZE);
2462                signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
2463                printf("<div class=\"leaf\"><span class=\"leaf\">&nbsp;</span>");
2464                sprintf(buf, "%llu", method->elapsedExclusive);
2465                printHtmlField(buf, 9);
2466                printf("&nbsp;");
2467                sprintf(buf, "%llu", method->elapsedInclusive);
2468                printHtmlField(buf, 9);
2469                printf("&nbsp;");
2470                sprintf(buf, "%.1f", per);
2471                printHtmlField(buf, 7);
2472                printf("&nbsp;");
2473                sprintf(buf, "%.1f", sum_per);
2474                printHtmlField(buf, 7);
2475                printf("&nbsp;");
2476                sprintf(buf, "%d", method->numCalls[0]);
2477                printHtmlField(buf, 6);
2478                printf("+");
2479                sprintf(buf, "%d", method->numCalls[1]);
2480                printHtmlField(buf, -6);
2481                printf("&nbsp;");
2482                printf("<a href=\"#m%d\">[%d]</a>&nbsp;%s.%s&nbsp;%s",
2483                       method->index, method->index,
2484                       className, methodName, signature);
2485                printf("</div>\n");
2486            } else {
2487                printf("%9llu %9llu %7.1f %7.1f %6d+%-6d [%d] %s.%s %s\n",
2488                       method->elapsedExclusive,
2489                       method->elapsedInclusive,
2490                       per, sum_per,
2491                       method->numCalls[0], method->numCalls[1],
2492                       method->index, className, methodName, signature);
2493            }
2494        }
2495        if (gOptions.outputHtml) {
2496            printf("</div>\n");
2497        }
2498    }
2499}
2500
2501/*
2502 * Determines whether the given FilterKey matches the method. The FilterKey's
2503 * key that is used to match against the method is determined by index.
2504 */
2505int keyMatchesMethod(FilterKey filterKey, MethodEntry* method, int index)
2506{
2507    if (filterKey.type[index] == 0) { // Class
2508#if 0
2509        fprintf(stderr, "  class is %s; filter key is %s\n", method->className, filterKey.keys[index]);
2510#endif
2511        if (strcmp(method->className, filterKey.keys[index]) == 0) {
2512	    return 1;
2513	}
2514    } else { // Method
2515        if (method->methodName != NULL) {
2516	    // Get fully-qualified name
2517            // TODO: parse class name and method name an put them in structure to avoid
2518            // allocating memory here
2519	    char* str = malloc ((strlen(method->className) + strlen(method->methodName) + 2) * sizeof(char));
2520	    strcpy(str, method->className);
2521	    strcat(str, ".");
2522	    strcat(str, method->methodName);
2523#if 0
2524	    fprintf(stderr, "  method is %s; filter key is %s\n", str, filterKey.keys[index]);
2525#endif
2526	    if (strcmp(str, filterKey.keys[index]) == 0) {
2527	        free(str);
2528	        return 1;
2529	    }
2530	    free(str);
2531	}
2532    }
2533    return 0;
2534}
2535
2536/*
2537 * Adds the appropriate times to the given filter based on the given method. Activates and
2538 * de-activates filters as necessary.
2539 *
2540 * A filter is activated when the given method matches the 'entry' key of one of its FilterKeys.
2541 * It is de-activated when the method matches the 'exit' key of the same FilterKey that activated it
2542 * in the first place. Thus, a filter may be active more than once on the same thread (activated by
2543 * different FilterKeys). A filter may also be active on different threads at the same time.
2544 *
2545 * While the filter is active on thread 1, elapsed time is allocated to different buckets which
2546 * include: thread execution time (i.e., time thread 1 spent executing while filter was active),
2547 * thread waiting time (i.e., time thread 1 waited while other threads executed), and execution
2548 * time while waiting (i.e., time thread x spent executing while thread 1 was waiting). We also
2549 * keep track of the total waiting time for a given filter.
2550 *
2551 * Lastly, we keep track of remaining (un-allocated) time for cases in which we exit a method we
2552 * had not entered before, and that method happens to match the 'exit' key of a FilterKey.
2553 */
2554int filterMethod(MethodEntry* method, Filter* filter, int entry, int threadId, int numThreads,
2555		 uint64_t elapsed, uint64_t remTime)
2556{
2557    int ii, jj;
2558    int activeCount, addedWaitTimeThreadsCount;
2559    int* activeThreads;
2560    int* activationKeys;
2561    int* addedWaitTimeThreads;
2562
2563    // flags
2564    int addWaitTime = 0;
2565    int deactivation = 0;
2566    int addedExecutionTime = 0;
2567    int addedExecutionTimeWhileWaiting = 0;
2568    int addedWaitTime;
2569    int addedRemTime = 0;
2570    int threadKeyPairActive = 0;
2571
2572    if (filter->times.threadWaitTimes == NULL && filter->times.threadExecutionTimes == NULL &&
2573	filter->times.threadExecutionTimesWhileWaiting == NULL) {
2574        filter->times.threadWaitTimes = (uint64_t*) calloc(MAX_THREADS, sizeof(uint64_t));
2575	filter->times.threadExecutionTimesWhileWaiting =
2576          (uint64_t*) calloc(MAX_THREADS, sizeof(uint64_t));
2577	filter->times.threadExecutionTimes = (uint64_t*) calloc(MAX_THREADS, sizeof(uint64_t));
2578    }
2579
2580    int verbose = 0;
2581
2582    if (verbose)
2583        fprintf(stderr,
2584                "Running %s filter for class %s method %s, thread %d; activeCount: %d time: %llu\n",
2585                filter->filterName, method->className, method->methodName, threadId,
2586                filter->activeCount, elapsed);
2587
2588    // If active on some thread
2589    if (filter->activeCount > 0) {
2590
2591        // Initialize active structures in case there are any de-activations
2592        activeThreads = (int*) calloc(filter->activeCount, sizeof(int));
2593	activationKeys = (int*) calloc(filter->activeCount, sizeof(int));
2594	activeCount = 0;
2595
2596	// Initialize structure to help us determine which threads we've already added wait time to
2597	addedWaitTimeThreads = (int*) calloc(filter->activeCount, sizeof(int));
2598	addedWaitTimeThreadsCount = 0;
2599
2600        // Add times to appropriate sums and de-activate (if necessary)
2601        for (ii = 0; ii < filter->activeCount; ii++) {
2602
2603	    if (verbose) {
2604	        fprintf(stderr, "  Analyzing active thread with id %d, activated by key [%s, %s]\n",
2605			filter->activeThreads[ii],
2606                        filter->filterKeys[filter->activationKeys[ii]].keys[0],
2607			filter->filterKeys[filter->activationKeys[ii]].keys[1]);
2608	    }
2609
2610	    // If active on THIS thread -> add to execution time (only add once!)
2611	    if (filter->activeThreads[ii] == threadId && !addedExecutionTime) {
2612	        if (verbose)
2613		    fprintf(stderr, "  Adding execution time to this thead\n");
2614	        filter->times.threadExecutionTimes[threadId] += elapsed;
2615		addedExecutionTime = 1;
2616	    }
2617
2618	    // If active on ANOTHER thread (or this one too) with CROSS_THREAD_FLAG -> add to
2619            // both thread's waiting time + total
2620	    if (filter->filterKeys[filter->activationKeys[ii]].flags == 1) {
2621
2622	        // Add time to thread that is waiting (add to each waiting thread at most once!)
2623	        addedWaitTime = 0;
2624		for (jj = 0; jj < addedWaitTimeThreadsCount; jj++) {
2625		    if (addedWaitTimeThreads[jj] == filter->activeThreads[ii])
2626		        addedWaitTime = 1;
2627		}
2628	        if (!addedWaitTime) {
2629		    if (verbose)
2630		        fprintf(stderr, "  Adding wait time to waiting thread\n");
2631		    filter->times.threadWaitTimes[filter->activeThreads[ii]] += elapsed;
2632		    addedWaitTimeThreads[addedWaitTimeThreadsCount++] = filter->activeThreads[ii];
2633		}
2634
2635                // Add execution time to this thread while the other is waiting (only add once!)
2636                // [Flag is needed only because outside for loop might iterate through same
2637                // thread twice?] TODO: verify
2638		if (!addedExecutionTimeWhileWaiting) {
2639		    if (verbose)
2640		        fprintf(stderr, "  Adding exec time to this thread while thread waits\n");
2641		    filter->times.threadExecutionTimesWhileWaiting[threadId] += elapsed;
2642		    addedExecutionTimeWhileWaiting = 1;
2643		}
2644
2645		addWaitTime = 1;
2646	    }
2647
2648	    // If a method exit matches the EXIT method of an ACTIVE key -> de-activate
2649            // the KEY (not the entire filter!!)
2650	    if (!entry && keyMatchesMethod(filter->filterKeys[filter->activationKeys[ii]],
2651					   method, 1)) {
2652	        if (verbose)
2653		    fprintf(stderr, "  Exit key matched!\n");
2654
2655	        // Deactivate by removing (NOT adding) entries from activeThreads and activationKeys
2656	        deactivation = 1; // singal that lists should be replaced
2657	    } else {
2658	        // No de-activation -> copy old entries into new lists
2659	        activeThreads[activeCount] = filter->activeThreads[ii];
2660		activationKeys[activeCount++] = filter->activationKeys[ii];
2661	    }
2662	}
2663
2664	// If waiting on ANY thread, add wait time to total (but only ONCE!)
2665	if (addWaitTime) {
2666	    filter->times.totalWaitTime += elapsed;
2667	}
2668
2669	// If de-activation occurred, replace lists
2670	if (deactivation) {
2671	    // TODO: Free memory from old lists
2672
2673	    // Set new lists
2674	    filter->activeThreads = activeThreads;
2675	    filter->activationKeys = activationKeys;
2676	    filter->activeCount = activeCount;
2677	} else {
2678	    // TODO: Free memory from new lists
2679	}
2680
2681    }  // Else, continue (we might be activating the filter on a different thread)
2682
2683
2684    if (entry) { // ENTRY
2685        if (verbose)
2686	    fprintf(stderr, "  Here at the entry\n");
2687        // If method matches entry key -> activate thread (do not add time since it's a new entry!)
2688        for (ii = 0; ii < filter->numKeys; ii++) {
2689	    if (keyMatchesMethod(filter->filterKeys[ii], method, 0)) {
2690	        if (verbose)
2691		    fprintf(stderr, "  Entry key matched!\n");
2692	        // Activate thread only if thread/key pair is not already active
2693	        for (jj = 0; jj < filter->activeCount; jj++) {
2694		    if (filter->activeThreads[jj] == threadId && filter->activationKeys[jj] == ii)
2695		        threadKeyPairActive = 1;
2696		}
2697	        // TODO: WORRY ABOUT MEMORY WHEN ACTIVE_COUNT > DEFAULT_ACTIVE_THREAD (unlikely)
2698	        // TODO: what if the same thread is active multiple times by different keys?
2699		// nothing, we just have to make sure we dont double-add, and we dont..
2700		if (!threadKeyPairActive) {
2701		    filter->activeThreads[filter->activeCount] = threadId;
2702		    filter->activationKeys[filter->activeCount++] = ii;
2703		}
2704	    }
2705	}
2706    } else { // EXIT
2707        // If method matches a terminal key -> add remTime to total (no need to active/de-activate)
2708        for (ii = 0; ii < filter->numKeys; ii++) {
2709	    if (!deactivation && keyMatchesMethod(filter->filterKeys[ii], method, 1) &&
2710		keyMatchesMethod(filter->filterKeys[ii], method, 0)) {
2711	        // Add remTime(s)
2712	        // TODO: think about how we should add remTimes.. should we add remTime to threads
2713	        // that were waiting or being waited on? for now, keep it simple and just add the
2714	        // execution time to the current thread.
2715	        filter->times.threadExecutionTimes[threadId] += remTime;
2716		addedRemTime = 1;
2717	    }
2718	}
2719    }
2720
2721    return addedExecutionTime | (addedRemTime << 1);
2722}
2723
2724void dumpFilters(Filter** filters) {
2725    int i;
2726    for (i = 0; i < numFilters; i++) {
2727        int j;
2728	fprintf(stderr, "FILTER %s\n", filters[i]->filterName);
2729	for (j = 0; j < filters[i]->numKeys; j++) {
2730	    fprintf(stderr, "Keys: %s, type %d", filters[i]->filterKeys[j].keys[0],
2731		    filters[i]->filterKeys[j].type[0]);
2732	    if (filters[i]->filterKeys[j].keys[1] != NULL) {
2733	        fprintf(stderr, " AND %s, type %d", filters[i]->filterKeys[j].keys[1],
2734			filters[i]->filterKeys[j].type[1]);
2735	    }
2736	    fprintf(stderr, "; flags: %d\n", filters[i]->filterKeys[j].flags);
2737	}
2738    }
2739}
2740
2741/*
2742 * See parseFilters for required data format.
2743 * 'data' must point to the beginning of a filter definition.
2744 */
2745char* parseFilter(char* data, char* dataEnd, Filter** filters, int num) {
2746
2747    Filter* filter;
2748    int next, count, i;
2749    int tmpOffset, tmpKeyLen;
2750    char* tmpKey;
2751    char* key1;
2752    char* key2;
2753
2754    filter = (Filter*) malloc(sizeof(Filter));
2755    filter->activeCount = 0;
2756    filter->activeThreads = (int*) calloc(DEFAULT_ACTIVE_THREADS, sizeof(int));
2757    filter->activationKeys = (int*) calloc(DEFAULT_ACTIVE_THREADS, sizeof(int));
2758
2759    next = findNextChar(data + 1, dataEnd - data - 1, '\n');
2760    if (next < 0) {
2761        // TODO: what should we do here?
2762        // End of file reached...
2763    }
2764    data[next+1] = '\0';
2765    filter->filterName = data + 1;
2766    data += next + 2; // Careful
2767
2768    /*
2769     * Count the number of keys (one per line).
2770     */
2771    count = countLinesToChar(data, dataEnd - data, FILTER_TAG);
2772    if (count <= 0) {
2773        fprintf(stderr,
2774		"ERROR: failed while parsing filter %s (found %d keys)\n",
2775		filter->filterName, count);
2776	return NULL; // TODO: Should do something else
2777	// Could return filter with 0 keys instead (probably better to avoid random segfaults)
2778    }
2779
2780    filter->filterKeys = (FilterKey*) malloc(sizeof(FilterKey) * count);
2781
2782    /*
2783     * Extract all entries.
2784     */
2785    tmpOffset = 0;
2786    for (i = 0; i < count; i++) {
2787        next = findNextChar(data, dataEnd - data, '\n');
2788	//        assert(next > 0); // TODO: revise... (skip if next == 0 ?)
2789        data[next] = '\0';
2790	tmpKey = data;
2791
2792        if (*data == FILTER_FLAG_THREAD) {
2793            filter->filterKeys[i].flags = 1;
2794            tmpKey++;
2795	} else {
2796            filter->filterKeys[i].flags = 0;
2797	}
2798
2799	tmpOffset = findNextChar(tmpKey, next, ',');
2800
2801        if (tmpOffset < 0) {
2802            // No comma, so only 1 key
2803            key1 = tmpKey;
2804	    key2 = tmpKey;
2805
2806	    // Get type for key1
2807            filter->filterKeys[i].type[0] = FILTER_TYPE_CLASS; // default
2808            tmpOffset = findNextChar(key1, next, '(');
2809	    if (tmpOffset > 0) {
2810	        if (findNextChar(key1, next, ')') == tmpOffset + 1) {
2811		    filter->filterKeys[i].type[0] = FILTER_TYPE_METHOD;
2812		    filter->filterKeys[i].type[1] = FILTER_TYPE_METHOD;
2813		}
2814		key1[tmpOffset] = '\0';
2815	    }
2816	} else {
2817	    // Pair of keys
2818	    tmpKey[tmpOffset] = '\0';
2819	    key1 = tmpKey;
2820	    key2 = tmpKey + tmpOffset + 1;
2821
2822	    // Get type for key1
2823	    filter->filterKeys[i].type[0] = FILTER_TYPE_CLASS;
2824	    tmpKeyLen = tmpOffset;
2825            tmpOffset = findNextChar(key1, tmpKeyLen, '(');
2826	    if (tmpOffset > 0) {
2827	        if (findNextChar(key1, tmpKeyLen, ')') == tmpOffset + 1) {
2828		    filter->filterKeys[i].type[0] = FILTER_TYPE_METHOD;
2829		}
2830		key1[tmpOffset] = '\0';
2831	    }
2832
2833	    // Get type for key2
2834	    filter->filterKeys[i].type[1] = FILTER_TYPE_CLASS;
2835            tmpOffset = findNextChar(key2, next - tmpKeyLen, '(');
2836	    if (tmpOffset > 0) {
2837	        if (findNextChar(key2, next - tmpKeyLen, ')') == tmpOffset + 1) {
2838		    filter->filterKeys[i].type[1] = FILTER_TYPE_METHOD;
2839		}
2840		key2[tmpOffset] = '\0';
2841	    }
2842	}
2843
2844	filter->filterKeys[i].keys[0] = key1;
2845	filter->filterKeys[i].keys[1] = key2;
2846        data += next+1;
2847    }
2848
2849    filter->numKeys = count;
2850    filters[num] = filter;
2851
2852    return data;
2853}
2854
2855/*
2856 * Parses filters from given file. The file must follow the following format:
2857 *
2858 * *FilterName    <- creates a new filter with keys to follow
2859 * A.method()     <- key that triggers whenever A.method() enters/exit
2860 * Class          <- key that triggers whenever any method from Class enters/exits
2861 * +CrossThread   <- same as above, but keeps track of execution times accross threads
2862 * B.m(),C.m()    <- key that triggers filter on when B.m() enters and off when C.m() exits
2863 *
2864 * TODO: add concrete example to make things clear
2865 */
2866Filter** parseFilters(const char* filterFileName) {
2867
2868    Filter** filters = NULL;
2869    FILE* fp = NULL;
2870    long len;
2871    char* data;
2872    char* dataEnd;
2873    char* dataStart;
2874    int i, next, count;
2875
2876    fp = fopen(filterFileName, "r");
2877    if (fp == NULL)
2878        goto bail;
2879
2880    if (fseek(fp, 0L, SEEK_END) != 0) {
2881        perror("fseek");
2882        goto bail;
2883    }
2884
2885    len = ftell(fp);
2886    if (len == 0) {
2887        fprintf(stderr, "WARNING: Filter file is empty.\n");
2888        goto bail;
2889    }
2890    rewind(fp);
2891
2892    data = (char*) malloc(len);
2893    if (data == NULL) {
2894        fprintf(stderr, "ERROR: unable to alloc %ld bytes for filter file\n", len);
2895        goto bail;
2896    }
2897
2898    // Read file into memory
2899    if (fread(data, 1, len, fp) != (size_t) len) {
2900        fprintf(stderr, "ERROR: unable to read %ld bytes from filter file\n", len);
2901        goto bail;
2902    }
2903
2904    dataStart = data;
2905    dataEnd = data + len;
2906
2907    // Figure out how many filters there are
2908    numFilters = 0;
2909    next = -1;
2910
2911    while (1) {
2912        if (*data == FILTER_TAG)
2913	    numFilters++;
2914        next = findNextChar(data, len, '\n');
2915        if (next < 0)
2916            break;
2917        data += next+1;
2918        len -= next+1;
2919    }
2920
2921    if (numFilters == 0) {
2922        fprintf(stderr, "WARNING: no filters found. Continuing without filters\n");
2923        goto bail;
2924    }
2925
2926    filters = (Filter**) calloc(numFilters, sizeof(Filter *));
2927    if (filters == NULL) {
2928        fprintf(stderr, "ERROR: unable to alloc memory for filters");
2929        goto bail;
2930    }
2931
2932    data = dataStart;
2933    for (i = 0; i < numFilters; i++) {
2934        data = parseFilter(data, dataEnd, filters, i);
2935    }
2936
2937    return filters;
2938
2939bail:
2940    if (fp != NULL)
2941        fclose(fp);
2942
2943    return NULL;
2944
2945}
2946
2947
2948/*
2949 * Read the key and data files and return the MethodEntries for those files
2950 */
2951DataKeys* parseDataKeys(TraceData* traceData, const char* traceFileName,
2952			uint64_t* threadTime, Filter** filters)
2953{
2954    DataKeys* dataKeys = NULL;
2955    MethodEntry **pMethods = NULL;
2956    MethodEntry* method;
2957    FILE* dataFp = NULL;
2958    DataHeader dataHeader;
2959    int ii, jj, numThreads;
2960    uint64_t currentTime;
2961    MethodEntry* caller;
2962
2963    dataFp = fopen(traceFileName, "r");
2964    if (dataFp == NULL)
2965        goto bail;
2966
2967    if ((dataKeys = parseKeys(dataFp, 0)) == NULL)
2968       goto bail;
2969
2970    if (parseDataHeader(dataFp, &dataHeader) < 0)
2971        goto bail;
2972
2973    numThreads = dataKeys->numThreads;
2974
2975#if 0
2976    FILE *dumpStream = fopen("debug", "w");
2977#endif
2978    while (1) {
2979        int threadId;
2980        unsigned int methodVal;
2981        int action;
2982        unsigned int methodId;
2983        CallStack *pStack;
2984
2985        /*
2986         * Extract values from file.
2987         */
2988        if (readDataRecord(dataFp, &dataHeader, &threadId, &methodVal, &currentTime))
2989            break;
2990
2991        action = METHOD_ACTION(methodVal);
2992        methodId = METHOD_ID(methodVal);
2993
2994        /* Get the call stack for this thread */
2995        pStack = traceData->stacks[threadId];
2996
2997        /* If there is no call stack yet for this thread, then allocate one */
2998        if (pStack == NULL) {
2999            pStack = malloc(sizeof(CallStack));
3000            pStack->top = 0;
3001            pStack->lastEventTime = currentTime;
3002            pStack->threadStartTime = currentTime;
3003	    pStack->remTimes = (uint64_t*) calloc(numFilters, sizeof(uint64_t));
3004            traceData->stacks[threadId] = pStack;
3005        }
3006
3007        /* Lookup the current method */
3008        method = lookupMethod(dataKeys, methodId);
3009        if (method == NULL)
3010            method = &dataKeys->methods[UNKNOWN_INDEX];
3011
3012#if 0
3013        if (method->methodName) {
3014	    fprintf(dumpStream, "%2d %-8llu %d %8llu r %d c %d %s.%s %s\n",
3015	           threadId, currentTime, action, pStack->threadStartTime,
3016	           method->recursiveEntries,
3017	           pStack->top, method->className, method->methodName,
3018	           method->signature);
3019        } else {
3020	    printf(dumpStream, "%2d %-8llu %d %8llu r %d c %d %s\n",
3021	           threadId, currentTime, action, pStack->threadStartTime,
3022	           method->recursiveEntries,
3023	           pStack->top, method->className);
3024        }
3025#endif
3026
3027        if (action == METHOD_TRACE_ENTER) {
3028            /* This is a method entry */
3029            if (pStack->top >= MAX_STACK_DEPTH) {
3030                fprintf(stderr, "Stack overflow (exceeded %d frames)\n",
3031                        MAX_STACK_DEPTH);
3032                exit(1);
3033            }
3034
3035            /* Get the caller method */
3036            if (pStack->top >= 1)
3037                caller = pStack->calls[pStack->top - 1].method;
3038            else
3039                caller = &dataKeys->methods[TOPLEVEL_INDEX];
3040            countRecursiveEntries(pStack, pStack->top, caller);
3041            caller->elapsedExclusive += currentTime - pStack->lastEventTime;
3042#if 0
3043            if (caller->elapsedExclusive > 10000000)
3044                fprintf(dumpStream, "%llu current %llu last %llu diff %llu\n",
3045                        caller->elapsedExclusive, currentTime,
3046                        pStack->lastEventTime,
3047                        currentTime - pStack->lastEventTime);
3048#endif
3049            if (caller->recursiveEntries <= 1) {
3050                caller->topExclusive += currentTime - pStack->lastEventTime;
3051            }
3052
3053            /* Push the method on the stack for this thread */
3054            pStack->calls[pStack->top].method = method;
3055            pStack->calls[pStack->top++].entryTime = currentTime;
3056
3057	    // For each filter
3058	    int result = 0;
3059	    for (ii = 0; ii < numFilters; ii++) {
3060	        result = filterMethod(method, filters[ii], 1, threadId, numThreads,
3061				       currentTime - pStack->lastEventTime, pStack->remTimes[ii]);
3062
3063		// TODO: make remTimes work properly
3064		// Consider moving remTimes handling together with the rest
3065		// of time handling and clean up the return codes
3066		/*
3067		if (result == 0) { // no time added, no remTime added
3068		    pStack->remTimes[ii] += currentTime - pStack->lastEventTime;
3069		} else if (result == 3 || result == 4) { // remTime added
3070		    // Reset remTime, since it's been added
3071		    pStack->remTimes[ii] = 0;
3072		}
3073		*/
3074	    }
3075
3076        } else {
3077            /* This is a method exit */
3078            uint64_t entryTime = 0;
3079
3080            /* Pop the method off the stack for this thread */
3081            if (pStack->top > 0) {
3082                pStack->top -= 1;
3083                entryTime = pStack->calls[pStack->top].entryTime;
3084                if (method != pStack->calls[pStack->top].method) {
3085                    if (method->methodName) {
3086                        fprintf(stderr,
3087                            "Exit from method %s.%s %s does not match stack:\n",
3088                            method->className, method->methodName,
3089                            method->signature);
3090                    } else {
3091                        fprintf(stderr,
3092                            "Exit from method %s does not match stack:\n",
3093                            method->className);
3094                    }
3095                    stackDump(pStack, pStack->top + 1);
3096                    exit(1);
3097                }
3098            }
3099
3100            /* Get the caller method */
3101            if (pStack->top >= 1)
3102                caller = pStack->calls[pStack->top - 1].method;
3103            else
3104                caller = &dataKeys->methods[TOPLEVEL_INDEX];
3105            countRecursiveEntries(pStack, pStack->top, caller);
3106            countRecursiveEntries(pStack, pStack->top, method);
3107            uint64_t elapsed = currentTime - entryTime;
3108            addInclusiveTime(caller, method, elapsed);
3109            method->elapsedExclusive += currentTime - pStack->lastEventTime;
3110            if (method->recursiveEntries == 0) {
3111                method->topExclusive += currentTime - pStack->lastEventTime;
3112            }
3113
3114	    // For each filter
3115	    int result = 0;
3116	    for (ii = 0; ii < numFilters; ii++) {
3117	        result = filterMethod(method, filters[ii], 0, threadId, numThreads,
3118				       currentTime - pStack->lastEventTime, pStack->remTimes[ii]);
3119
3120		// TODO: make remTimes work properly
3121		/*
3122		if (result == 0) { // no time added, no remTime added
3123		    pStack->remTimes[ii] += currentTime - pStack->lastEventTime;
3124		} else if (result == 3 || result == 4) { // remTime added
3125		    // Reset remTime, since it's been added
3126		    pStack->remTimes[ii] = 0;
3127		}
3128		*/
3129	    }
3130
3131        }
3132        /* Remember the time of the last entry or exit event */
3133        pStack->lastEventTime = currentTime;
3134    }
3135
3136    /* If we have calls on the stack when the trace ends, then clean
3137     * up the stack and add time to the callers by pretending that we
3138     * are exiting from their methods now.
3139     */
3140    CallStack *pStack;
3141    int threadId;
3142    uint64_t elapsedTime = 0;
3143    uint64_t sumThreadTime = 0;
3144    for (threadId = 0; threadId < MAX_THREADS; ++threadId) {
3145
3146        pStack = traceData->stacks[threadId];
3147
3148        /* If this thread never existed, then continue with next thread */
3149        if (pStack == NULL)
3150            continue;
3151
3152        /* Calculate times spent in thread, and add it to total time */
3153        elapsedTime = pStack->lastEventTime - pStack->threadStartTime;
3154        sumThreadTime += elapsedTime;
3155
3156        for (ii = 0; ii < pStack->top; ++ii) {
3157	  //printf("in loop\n");
3158
3159            if (ii == 0)
3160                caller = &dataKeys->methods[TOPLEVEL_INDEX];
3161            else
3162                caller = pStack->calls[ii - 1].method;
3163            method = pStack->calls[ii].method;
3164            countRecursiveEntries(pStack, ii, caller);
3165            countRecursiveEntries(pStack, ii, method);
3166
3167            uint64_t entryTime = pStack->calls[ii].entryTime;
3168            uint64_t elapsed = pStack->lastEventTime - entryTime;
3169            addInclusiveTime(caller, method, elapsed);
3170
3171	    // For each filter
3172	    int result = 0;
3173	    for (ii = 0; ii < numFilters; ii++) {
3174	        result = filterMethod(method, filters[ii], 0, threadId, numThreads,
3175				       currentTime - pStack->lastEventTime, pStack->remTimes[ii]);
3176
3177		// TODO: make remTimes work properly
3178		/*
3179		if (result == 0) { // no time added, no remTime added
3180		    pStack->remTimes[ii] += currentTime - pStack->lastEventTime;
3181		} else if (result == 3 || result == 4) { // remTime added
3182		    // Reset remTime, since it's been added
3183		    pStack->remTimes[ii] = 0;
3184		}
3185		*/
3186	    }
3187        }
3188
3189	/* Save the per-thread elapsed time in the DataKeys struct */
3190	for (ii = 0; ii < dataKeys->numThreads; ++ii) {
3191	    if (dataKeys->threads[ii].threadId == threadId) {
3192                dataKeys->threads[ii].elapsedTime = elapsedTime;
3193	    }
3194	}
3195
3196
3197    }
3198    caller = &dataKeys->methods[TOPLEVEL_INDEX];
3199    caller->elapsedInclusive = sumThreadTime;
3200
3201#if 0
3202    fclose(dumpStream);
3203#endif
3204
3205    if (threadTime != NULL) {
3206        *threadTime = sumThreadTime;
3207    }
3208
3209bail:
3210    if (dataFp != NULL)
3211        fclose(dataFp);
3212
3213    return dataKeys;
3214}
3215
3216MethodEntry** parseMethodEntries(DataKeys* dataKeys)
3217{
3218    int ii;
3219    /* Create a new array of pointers to the methods and sort the pointers
3220     * instead of the actual MethodEntry structs.  We need to do this
3221     * because there are other lists that contain pointers to the
3222     * MethodEntry structs.
3223     */
3224    MethodEntry** pMethods = (MethodEntry**) malloc(sizeof(MethodEntry*) * dataKeys->numMethods);
3225    for (ii = 0; ii < dataKeys->numMethods; ++ii) {
3226        MethodEntry* entry = &dataKeys->methods[ii];
3227        pMethods[ii] = entry;
3228    }
3229
3230    return pMethods;
3231}
3232
3233
3234/*
3235 * Produce a function profile from the following methods
3236 */
3237void profileTrace(TraceData* traceData, MethodEntry **pMethods, int numMethods, uint64_t sumThreadTime,
3238                  ThreadEntry *pThreads, int numThreads, Filter** filters)
3239{
3240   /* Print the html header, if necessary */
3241    if (gOptions.outputHtml) {
3242        printf(htmlHeader, gOptions.sortableUrl);
3243        outputTableOfContents();
3244    }
3245
3246    printExclusiveProfile(pMethods, numMethods, sumThreadTime);
3247    printInclusiveProfile(pMethods, numMethods, sumThreadTime);
3248
3249    printThreadProfile(pThreads, numThreads, sumThreadTime, filters);
3250
3251    createClassList(traceData, pMethods, numMethods);
3252    printClassProfiles(traceData, sumThreadTime);
3253
3254    createUniqueMethodList(traceData, pMethods, numMethods);
3255    printMethodProfiles(traceData, sumThreadTime);
3256
3257    if (gOptions.outputHtml) {
3258        printf("%s", htmlFooter);
3259    }
3260}
3261
3262int compareMethodNamesForDiff(const void *a, const void *b)
3263{
3264    int result;
3265
3266    const MethodEntry *methodA = *(const MethodEntry**)a;
3267    const MethodEntry *methodB = *(const MethodEntry**)b;
3268    if (methodA->methodName == NULL || methodB->methodName == NULL) {
3269        return compareClassNames(a, b);
3270    }
3271    result = strcmp(methodA->methodName, methodB->methodName);
3272    if (result == 0) {
3273        result = strcmp(methodA->signature, methodB->signature);
3274        if (result == 0) {
3275           return strcmp(methodA->className, methodB->className);
3276        }
3277    }
3278    return result;
3279}
3280
3281int findMatch(MethodEntry** methods, int size, MethodEntry* matchThis)
3282{
3283    int i;
3284
3285    for (i = 0 ; i < size ; i++) {
3286        MethodEntry* method = methods[i];
3287
3288        if (method != NULL && !compareMethodNamesForDiff(&method, &matchThis)) {
3289//            printf("%s.%s == %s.%s<br>\n", matchThis->className, matchThis->methodName,
3290  //              method->className, method->methodName);
3291
3292            return i;
3293/*            if (!compareMethodNames(&method, &matchThis)) {
3294                return i;
3295            }
3296*/        }
3297    }
3298
3299    return -1;
3300}
3301
3302int compareDiffEntriesExculsive(const void *a, const void *b)
3303{
3304    int result;
3305
3306    const DiffEntry* entryA = (const DiffEntry*)a;
3307    const DiffEntry* entryB = (const DiffEntry*)b;
3308
3309    if (entryA->differenceExclusive < entryB->differenceExclusive) {
3310        return 1;
3311    } else if (entryA->differenceExclusive > entryB->differenceExclusive) {
3312        return -1;
3313    }
3314
3315    return 0;
3316}
3317
3318int compareDiffEntriesInculsive(const void *a, const void *b)
3319{
3320    int result;
3321
3322    const DiffEntry* entryA = (const DiffEntry*)a;
3323    const DiffEntry* entryB = (const DiffEntry*)b;
3324
3325    if (entryA->differenceInclusive < entryB->differenceInclusive) {
3326        return 1;
3327    } else if (entryA->differenceInclusive > entryB->differenceInclusive) {
3328        return -1;
3329    }
3330
3331    return 0;
3332}
3333
3334void printMissingMethod(MethodEntry* method)
3335{
3336    char classBuf[HTML_BUFSIZE];
3337    char methodBuf[HTML_BUFSIZE];
3338    char* className;
3339    char* methodName;
3340
3341    className = htmlEscape(method->className, classBuf, HTML_BUFSIZE);
3342    methodName = htmlEscape(method->methodName, methodBuf, HTML_BUFSIZE);
3343
3344    if (gOptions.outputHtml) printf("<tr><td>\n");
3345
3346    printf("%s.%s ", className, methodName);
3347    if (gOptions.outputHtml) printf("</td><td>");
3348
3349    printf("%lld ", method->elapsedExclusive);
3350    if (gOptions.outputHtml) printf("</td><td>");
3351
3352    printf("%lld ", method->elapsedInclusive);
3353    if (gOptions.outputHtml) printf("</td><td>");
3354
3355    printf("%d\n", method->numCalls[0]);
3356    if (gOptions.outputHtml) printf("</td><td>\n");
3357}
3358
3359
3360void createDiff(DataKeys* d1, uint64_t sum1, DataKeys* d2, uint64_t sum2)
3361{
3362    MethodEntry** methods1 = parseMethodEntries(d1);
3363    MethodEntry** methods2 = parseMethodEntries(d2);
3364
3365    // sort and assign the indicies
3366    int i;
3367    qsort(methods1, d1->numMethods, sizeof(MethodEntry*), compareElapsedInclusive);
3368    for (i = 0; i < d1->numMethods; ++i) {
3369        methods1[i]->index = i;
3370    }
3371
3372    qsort(methods2, d2->numMethods, sizeof(MethodEntry*), compareElapsedInclusive);
3373    for (i = 0; i < d2->numMethods; ++i) {
3374        methods2[i]->index = i;
3375    }
3376
3377    int max = (d1->numMethods < d2->numMethods) ? d2->numMethods : d1->numMethods;
3378    max++;
3379    DiffEntry* diffs = (DiffEntry*)malloc(max * sizeof(DiffEntry));
3380    memset(diffs, 0, max * sizeof(DiffEntry));
3381    DiffEntry* ptr = diffs;
3382
3383//    printf("<br>d1->numMethods: %d d1->numMethods: %d<br>\n", d1->numMethods, d2->numMethods);
3384
3385    int matches = 0;
3386
3387    for (i = 0 ; i < d1->numMethods ; i++) {
3388        int match = findMatch(methods2, d2->numMethods, methods1[i]);
3389        if (match >= 0) {
3390            ptr->method1 = methods1[i];
3391            ptr->method2 = methods2[match];
3392
3393            uint64_t e1 = ptr->method1->elapsedExclusive;
3394            uint64_t e2 = ptr->method2->elapsedExclusive;
3395            if (e1 > 0) {
3396                ptr->differenceExclusive = e2 - e1;
3397                ptr->differenceExclusivePercentage = ((double)e2 / (double)e1) * 100.0;
3398            }
3399
3400            uint64_t i1 = ptr->method1->elapsedInclusive;
3401            uint64_t i2 = ptr->method2->elapsedInclusive;
3402            if (i1 > 0) {
3403                ptr->differenceInclusive = i2 - i1;
3404                ptr->differenceInclusivePercentage = ((double)i2 / (double)i1) * 100.0;
3405            }
3406
3407            // clear these out so we don't find them again and we know which ones
3408            // we have left over
3409            methods1[i] = NULL;
3410            methods2[match] = NULL;
3411            ptr++;
3412
3413            matches++;
3414        }
3415    }
3416    ptr->method1 = NULL;
3417    ptr->method2 = NULL;
3418
3419    qsort(diffs, matches, sizeof(DiffEntry), compareDiffEntriesExculsive);
3420    ptr = diffs;
3421
3422    if (gOptions.outputHtml) {
3423        printf(htmlHeader, gOptions.sortableUrl);
3424        printf("<h3>Table of Contents</h3>\n");
3425        printf("<ul>\n");
3426        printf("<li><a href='#exclusive'>Exclusive</a>\n");
3427        printf("<li><a href='#inclusive'>Inclusive</a>\n");
3428        printf("</ul>\n");
3429        printf("Run 1: %s<br>\n", gOptions.diffFileName);
3430        printf("Run 2: %s<br>\n", gOptions.traceFileName);
3431        printf("<a name=\"exclusive\"></a><h3 id=\"exclusive\">Exclusive</h3>\n");
3432        printf(tableHeader, "exclusive_table");
3433    }
3434
3435    char classBuf[HTML_BUFSIZE];
3436    char methodBuf[HTML_BUFSIZE];
3437    char* className;
3438    char* methodName;
3439
3440    while (ptr->method1 != NULL && ptr->method2 != NULL) {
3441        if (gOptions.outputHtml) printf("<tr><td>\n");
3442
3443        className = htmlEscape(ptr->method1->className, classBuf, HTML_BUFSIZE);
3444        methodName = htmlEscape(ptr->method1->methodName, methodBuf, HTML_BUFSIZE);
3445
3446        printf("%s.%s ", className, methodName);
3447        if (gOptions.outputHtml) printf("</td><td>");
3448
3449        printf("%lld ", ptr->method1->elapsedExclusive);
3450        if (gOptions.outputHtml) printf("</td><td>");
3451
3452        printf("%llu ", ptr->method2->elapsedExclusive);
3453        if (gOptions.outputHtml) printf("</td><td>");
3454
3455        printf("%lld ", ptr->differenceExclusive);
3456        if (gOptions.outputHtml) printf("</td><td>");
3457
3458        printf("%.2f\n", ptr->differenceExclusivePercentage);
3459        if (gOptions.outputHtml) printf("</td><td>\n");
3460
3461        printf("%d\n", ptr->method1->numCalls[0]);
3462        if (gOptions.outputHtml) printf("</td><td>\n");
3463
3464        printf("%d\n", ptr->method2->numCalls[0]);
3465        if (gOptions.outputHtml) printf("</td></tr>\n");
3466
3467        ptr++;
3468    }
3469
3470    if (gOptions.outputHtml) printf("</table>\n");
3471
3472    if (gOptions.outputHtml) {
3473        printf(htmlHeader, gOptions.sortableUrl);
3474        printf("Run 1: %s<br>\n", gOptions.diffFileName);
3475        printf("Run 2: %s<br>\n", gOptions.traceFileName);
3476        printf("<a name=\"inclusive\"></a><h3 id=\"inculisve\">Inclusive</h3>\n");
3477        printf(tableHeader, "inclusive_table");
3478    }
3479
3480    qsort(diffs, matches, sizeof(DiffEntry), compareDiffEntriesInculsive);
3481    ptr = diffs;
3482
3483    while (ptr->method1 != NULL && ptr->method2 != NULL) {
3484        if (gOptions.outputHtml) printf("<tr><td>\n");
3485
3486        className = htmlEscape(ptr->method1->className, classBuf, HTML_BUFSIZE);
3487        methodName = htmlEscape(ptr->method1->methodName, methodBuf, HTML_BUFSIZE);
3488
3489        printf("%s.%s ", className, methodName);
3490        if (gOptions.outputHtml) printf("</td><td>");
3491
3492        printf("%lld ", ptr->method1->elapsedInclusive);
3493        if (gOptions.outputHtml) printf("</td><td>");
3494
3495        printf("%llu ", ptr->method2->elapsedInclusive);
3496        if (gOptions.outputHtml) printf("</td><td>");
3497
3498        printf("%lld ", ptr->differenceInclusive);
3499        if (gOptions.outputHtml) printf("</td><td>");
3500
3501        printf("%.2f\n", ptr->differenceInclusivePercentage);
3502        if (gOptions.outputHtml) printf("</td><td>\n");
3503
3504        printf("%d\n", ptr->method1->numCalls[0]);
3505        if (gOptions.outputHtml) printf("</td><td>\n");
3506
3507        printf("%d\n", ptr->method2->numCalls[0]);
3508        if (gOptions.outputHtml) printf("</td></tr>\n");
3509
3510        ptr++;
3511    }
3512
3513    if (gOptions.outputHtml) {
3514        printf("</table>\n");
3515        printf("<h3>Run 1 methods not found in Run 2</h3>");
3516        printf(tableHeaderMissing);
3517    }
3518
3519    for (i = 0; i < d1->numMethods; ++i) {
3520        if (methods1[i] != NULL) {
3521           printMissingMethod(methods1[i]);
3522        }
3523    }
3524
3525    if (gOptions.outputHtml) {
3526        printf("</table>\n");
3527        printf("<h3>Run 2 methods not found in Run 1</h3>");
3528        printf(tableHeaderMissing);
3529    }
3530
3531    for (i = 0; i < d2->numMethods; ++i) {
3532        if (methods2[i] != NULL) {
3533            printMissingMethod(methods2[i]);
3534        }
3535    }
3536
3537    if (gOptions.outputHtml) printf("</body></html\n");
3538}
3539
3540int usage(const char *program)
3541{
3542    fprintf(stderr, "usage: %s [-ho] [-s sortable] [-d trace-file-name] [-g outfile] [-f filter-file] trace-file-name\n", program);
3543    fprintf(stderr, "  -d trace-file-name  - Diff with this trace\n");
3544    fprintf(stderr, "  -g outfile          - Write graph to 'outfile'\n");
3545    fprintf(stderr, "  -f filter-file      - Filter functions as specified in file\n");
3546    fprintf(stderr, "  -k                  - When writing a graph, keep the intermediate DOT file\n");
3547    fprintf(stderr, "  -h                  - Turn on HTML output\n");
3548    fprintf(stderr, "  -o                  - Dump the dmtrace file instead of profiling\n");
3549    fprintf(stderr, "  -s                  - URL base to where the sortable javascript file\n");
3550    fprintf(stderr, "  -t threshold        - Threshold percentage for including nodes in the graph\n");
3551    return 2;
3552}
3553
3554// Returns true if there was an error
3555int parseOptions(int argc, char **argv)
3556{
3557    while (1) {
3558        int opt = getopt(argc, argv, "d:hg:kos:t:f:");
3559        if (opt == -1)
3560            break;
3561        switch (opt) {
3562            case 'd':
3563                gOptions.diffFileName = optarg;
3564                break;
3565            case 'g':
3566                gOptions.graphFileName = optarg;
3567                break;
3568            case 'f':
3569	        gOptions.filterFileName = optarg;
3570                break;
3571            case 'k':
3572                gOptions.keepDotFile = 1;
3573                break;
3574            case 'h':
3575                gOptions.outputHtml = 1;
3576                break;
3577            case 'o':
3578                gOptions.dump = 1;
3579                break;
3580            case 's':
3581                gOptions.sortableUrl = optarg;
3582                break;
3583            case 't':
3584                gOptions.threshold = atoi(optarg);
3585                break;
3586            default:
3587                return 1;
3588        }
3589    }
3590    return 0;
3591}
3592
3593/*
3594 * Parse args.
3595 */
3596int main(int argc, char** argv)
3597{
3598
3599    gOptions.threshold = -1;
3600
3601    // Parse the options
3602    if (parseOptions(argc, argv) || argc - optind != 1)
3603        return usage(argv[0]);
3604
3605    gOptions.traceFileName = argv[optind];
3606
3607    if (gOptions.threshold < 0 || 100 <= gOptions.threshold) {
3608        gOptions.threshold = 20;
3609    }
3610
3611    if (gOptions.dump) {
3612        dumpTrace();
3613        return 0;
3614    }
3615
3616    uint64_t sumThreadTime = 0;
3617
3618    Filter** filters = NULL;
3619    if (gOptions.filterFileName != NULL) {
3620        filters = parseFilters(gOptions.filterFileName);
3621    }
3622
3623    TraceData data1;
3624    memset(&data1, 0, sizeof(data1));
3625    DataKeys* dataKeys = parseDataKeys(&data1, gOptions.traceFileName,
3626                                       &sumThreadTime, filters);
3627    if (dataKeys == NULL) {
3628        fprintf(stderr, "Cannot read trace.\n");
3629        exit(1);
3630    }
3631
3632    if (gOptions.diffFileName != NULL) {
3633        uint64_t sum2;
3634        TraceData data2;
3635        DataKeys* d2 = parseDataKeys(&data2, gOptions.diffFileName, &sum2, filters);
3636
3637        createDiff(d2, sum2, dataKeys, sumThreadTime);
3638
3639        freeDataKeys(d2);
3640    } else {
3641        MethodEntry** methods = parseMethodEntries(dataKeys);
3642        profileTrace(&data1, methods, dataKeys->numMethods, sumThreadTime,
3643                     dataKeys->threads, dataKeys->numThreads, filters);
3644        if (gOptions.graphFileName != NULL) {
3645            createInclusiveProfileGraphNew(dataKeys);
3646        }
3647        free(methods);
3648    }
3649
3650    freeDataKeys(dataKeys);
3651
3652    return 0;
3653}
3654