TraceDump.c revision 949c3ec207a7720fb47f7b3ca1f84dfcfd70aaa9 
1/*
2 * Copyright (C) 2006 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17/*
18 * Process dmtrace output.
19 *
20 * This is the wrong way to go about it -- C is a clumsy language for
21 * shuffling data around.  It'll do for a first pass.
22 */
23#define NOT_VM
24#include "Profile.h"        // from VM header
25
26#include <stdio.h>
27#include <stdlib.h>
28#include <string.h>
29#include <unistd.h>
30#include <inttypes.h>
31#include <time.h>
32#include <errno.h>
33#include <assert.h>
34
35/* Version number in the key file.
36 * Version 1 uses one byte for the thread id.
37 * Version 2 uses two bytes for the thread ids.
38 * Version 3 encodes the record size and adds an optional extra timestamp field.
39 */
40int versionNumber;
41
42/* arbitrarily limit indentation */
43#define MAX_STACK_DEPTH 10000
44
45/* thread list in key file is not reliable, so just max out */
46#define MAX_THREADS     32768
47
48/* Size of temporary buffers for escaping html strings */
49#define HTML_BUFSIZE 10240
50
51char *htmlHeader =
52"<html>\n<head>\n<script type=\"text/javascript\" src=\"%ssortable.js\"></script>\n"
53"<script langugage=\"javascript\">\n"
54"function toggle(item) {\n"
55"    obj=document.getElementById(item);\n"
56"    visible=(obj.style.display!=\"none\" && obj.style.display!=\"\");\n"
57"    key=document.getElementById(\"x\" + item);\n"
58"    if (visible) {\n"
59"        obj.style.display=\"none\";\n"
60"        key.innerHTML=\"+\";\n"
61"    } else {\n"
62"        obj.style.display=\"block\";\n"
63"        key.innerHTML=\"-\";\n"
64"    }\n"
65"}\n"
66"function onMouseOver(obj) {\n"
67"    obj.style.background=\"lightblue\";\n"
68"}\n"
69"function onMouseOut(obj) {\n"
70"    obj.style.background=\"white\";\n"
71"}\n"
72"</script>\n"
73"<style type=\"text/css\">\n"
74"div { font-family: courier; font-size: 13 }\n"
75"div.parent { margin-left: 15; display: none }\n"
76"div.leaf { margin-left: 10 }\n"
77"div.header { margin-left: 10 }\n"
78"div.link { margin-left: 10; cursor: move }\n"
79"span.parent { padding-right: 10; }\n"
80"span.leaf { padding-right: 10; }\n"
81"a img { border: 0;}\n"
82"table.sortable th { border-width: 0px 1px 1px 1px; background-color: #ccc;}\n"
83"a { text-decoration: none; }\n"
84"a:hover { text-decoration: underline; }\n"
85"table.sortable th, table.sortable td { text-align: left;}"
86"table.sortable tr.odd td { background-color: #ddd; }\n"
87"table.sortable tr.even td { background-color: #fff; }\n"
88"</style>\n"
89"</head><body>\n\n";
90
91char *htmlFooter = "\n</body>\n</html>\n";
92char *profileSeparator =
93    "======================================================================";
94
95const char* tableHeader =
96    "<table class='sortable' id='%s'><tr>\n"
97    "<th>Method</th>\n"
98    "<th>Run 1 (us)</th>\n"
99    "<th>Run 2 (us)</th>\n"
100    "<th>Diff (us)</th>\n"
101    "<th>Diff (%%)</th>\n"
102    "<th>1: # calls</th>\n"
103    "<th>2: # calls</th>\n"
104    "</tr>\n";
105
106const char* tableHeaderMissing =
107    "<table class='sortable' id='%s'>\n"
108    "<th>Method</th>\n"
109    "<th>Exclusive</th>\n"
110    "<th>Inclusive</th>\n"
111    "<th># calls</th>\n";
112
113#define GRAPH_LABEL_VISITED 0x0001
114#define GRAPH_NODE_VISITED  0x0002
115
116/*
117 * Values from the header of the data file.
118 */
119typedef struct DataHeader {
120    unsigned int magic;
121    short version;
122    short offsetToData;
123    long long startWhen;
124    short recordSize;
125} DataHeader;
126
127/*
128 * Entry from the thread list.
129 */
130typedef struct ThreadEntry {
131    int         threadId;
132    const char* threadName;
133} ThreadEntry;
134
135struct MethodEntry;
136typedef struct TimedMethod {
137    struct TimedMethod *next;
138    uint64_t elapsedInclusive;
139    int numCalls;
140    struct MethodEntry *method;
141} TimedMethod;
142
143typedef struct ClassEntry {
144    const char *className;
145    uint64_t elapsedExclusive;
146    int numMethods;
147    struct MethodEntry **methods;       /* list of methods in this class */
148    int numCalls[2];                    /* 0=normal, 1=recursive */
149} ClassEntry;
150
151typedef struct UniqueMethodEntry {
152    uint64_t elapsedExclusive;
153    int numMethods;
154    struct MethodEntry **methods;       /* list of methods with same name */
155    int numCalls[2];                    /* 0=normal, 1=recursive */
156} UniqueMethodEntry;
157
158/*
159 * Entry from the method list.
160 */
161typedef struct MethodEntry {
162    unsigned int methodId;
163    const char* className;
164    const char* methodName;
165    const char* signature;
166    const char* fileName;
167    int lineNum;
168    uint64_t elapsedExclusive;
169    uint64_t elapsedInclusive;
170    uint64_t topExclusive;              /* non-recursive exclusive time */
171    uint64_t recursiveInclusive;
172    struct TimedMethod *parents[2];     /* 0=normal, 1=recursive */
173    struct TimedMethod *children[2];    /* 0=normal, 1=recursive */
174    int numCalls[2];                    /* 0=normal, 1=recursive */
175    int index;                  /* used after sorting to number methods */
176    int recursiveEntries;       /* number of entries on the stack */
177    int graphState;             /* used when graphing to see if this method has been visited before */
178} MethodEntry;
179
180/*
181 * The parsed contents of the key file.
182 */
183typedef struct DataKeys {
184    char*        fileData;      /* contents of the entire file */
185    long         fileLen;
186    int          numThreads;
187    ThreadEntry* threads;
188    int          numMethods;
189    MethodEntry* methods;       /* 2 extra methods: "toplevel" and "unknown" */
190} DataKeys;
191
192#define TOPLEVEL_INDEX 0
193#define UNKNOWN_INDEX 1
194
195typedef struct StackEntry {
196    MethodEntry *method;
197    uint64_t    entryTime;
198} StackEntry;
199
200typedef struct CallStack {
201    int         top;
202    StackEntry  calls[MAX_STACK_DEPTH];
203    uint64_t    lastEventTime;
204    uint64_t    threadStartTime;
205} CallStack;
206
207typedef struct DiffEntry {
208    MethodEntry* method1;
209    MethodEntry* method2;
210    int64_t differenceExclusive;
211    int64_t differenceInclusive;
212    double differenceExclusivePercentage;
213    double differenceInclusivePercentage;
214} DiffEntry;
215
216// Global options
217typedef struct Options {
218    const char* traceFileName;
219    const char* diffFileName;
220    const char* graphFileName;
221    int keepDotFile;
222    int dump;
223    int outputHtml;
224    const char* sortableUrl;
225    int threshold;
226} Options;
227
228typedef struct TraceData {
229    int numClasses;
230    ClassEntry *classes;
231    CallStack *stacks[MAX_THREADS];
232    int depth[MAX_THREADS];
233    int numUniqueMethods;
234    UniqueMethodEntry *uniqueMethods;
235} TraceData;
236
237static Options gOptions;
238
239/* Escapes characters in the source string that are html special entities.
240 * The escaped string is written to "dest" which must be large enough to
241 * hold the result.  A pointer to "dest" is returned.  The characters and
242 * their corresponding escape sequences are:
243 *  '<'  &lt;
244 *  '>'  &gt;
245 *  '&'  &amp;
246 */
247char *htmlEscape(const char *src, char *dest, int len)
248{
249    char *destStart = dest;
250
251    if (src == NULL)
252        return NULL;
253
254    int nbytes = 0;
255    while (*src) {
256        if (*src == '<') {
257            nbytes += 4;
258            if (nbytes >= len)
259                break;
260            *dest++ = '&';
261            *dest++ = 'l';
262            *dest++ = 't';
263            *dest++ = ';';
264        } else if (*src == '>') {
265            nbytes += 4;
266            if (nbytes >= len)
267                break;
268            *dest++ = '&';
269            *dest++ = 'g';
270            *dest++ = 't';
271            *dest++ = ';';
272        } else if (*src == '&') {
273            nbytes += 5;
274            if (nbytes >= len)
275                break;
276            *dest++ = '&';
277            *dest++ = 'a';
278            *dest++ = 'm';
279            *dest++ = 'p';
280            *dest++ = ';';
281        } else {
282            nbytes += 1;
283            if (nbytes >= len)
284                break;
285            *dest++ = *src;
286        }
287        src += 1;
288    }
289    if (nbytes >= len) {
290        fprintf(stderr, "htmlEscape(): buffer overflow\n");
291        exit(1);
292    }
293    *dest = 0;
294
295    return destStart;
296}
297
298/* Initializes a MethodEntry
299 */
300void initMethodEntry(MethodEntry *method, unsigned int methodId,
301                     const char *className, const char *methodName,
302                     const char *signature, const char* fileName,
303                     const char* lineNumStr)
304{
305    method->methodId = methodId;
306    method->className = className;
307    method->methodName = methodName;
308    method->signature = signature;
309    method->fileName = fileName;
310    method->lineNum = (lineNumStr != NULL) ? atoi(lineNumStr) : -1;
311    method->elapsedExclusive = 0;
312    method->elapsedInclusive = 0;
313    method->topExclusive = 0;
314    method->recursiveInclusive = 0;
315    method->parents[0] = NULL;
316    method->parents[1] = NULL;
317    method->children[0] = NULL;
318    method->children[1] = NULL;
319    method->numCalls[0] = 0;
320    method->numCalls[1] = 0;
321    method->index = 0;
322    method->recursiveEntries = 0;
323}
324
325/*
326 * This comparison function is called from qsort() to sort
327 * methods into decreasing order of exclusive elapsed time.
328 */
329int compareElapsedExclusive(const void *a, const void *b) {
330    uint64_t elapsed1, elapsed2;
331    int result;
332
333    const MethodEntry *methodA = *(const MethodEntry**)a;
334    const MethodEntry *methodB = *(const MethodEntry**)b;
335    elapsed1 = methodA->elapsedExclusive;
336    elapsed2 = methodB->elapsedExclusive;
337    if (elapsed1 < elapsed2)
338        return 1;
339    if (elapsed1 > elapsed2)
340        return -1;
341
342    /* If the elapsed times of two methods are equal, then sort them
343     * into alphabetical order.
344     */
345    result = strcmp(methodA->className, methodB->className);
346    if (result == 0) {
347        if (methodA->methodName == NULL || methodB->methodName == NULL) {
348            unsigned int idA = methodA->methodId;
349            unsigned int idB = methodB->methodId;
350            if (idA < idB)
351                return -1;
352            if (idA > idB)
353                return 1;
354            return 0;
355        }
356        result = strcmp(methodA->methodName, methodB->methodName);
357        if (result == 0)
358            result = strcmp(methodA->signature, methodB->signature);
359    }
360    return result;
361}
362
363/*
364 * This comparison function is called from qsort() to sort
365 * methods into decreasing order of inclusive elapsed time.
366 */
367int compareElapsedInclusive(const void *a, const void *b) {
368    const MethodEntry *methodA, *methodB;
369    uint64_t elapsed1, elapsed2;
370    int result;
371
372    methodA = *(MethodEntry const **)a;
373    methodB = *(MethodEntry const **)b;
374    elapsed1 = methodA->elapsedInclusive;
375    elapsed2 = methodB->elapsedInclusive;
376    if (elapsed1 < elapsed2)
377        return 1;
378    if (elapsed1 > elapsed2)
379        return -1;
380
381    /* If the elapsed times of two methods are equal, then sort them
382     * into alphabetical order.
383     */
384    result = strcmp(methodA->className, methodB->className);
385    if (result == 0) {
386        if (methodA->methodName == NULL || methodB->methodName == NULL) {
387            unsigned int idA = methodA->methodId;
388            unsigned int idB = methodB->methodId;
389            if (idA < idB)
390                return -1;
391            if (idA > idB)
392                return 1;
393            return 0;
394        }
395        result = strcmp(methodA->methodName, methodB->methodName);
396        if (result == 0)
397            result = strcmp(methodA->signature, methodB->signature);
398    }
399    return result;
400}
401
402/*
403 * This comparison function is called from qsort() to sort
404 * TimedMethods into decreasing order of inclusive elapsed time.
405 */
406int compareTimedMethod(const void *a, const void *b) {
407    const TimedMethod *timedA, *timedB;
408    uint64_t elapsed1, elapsed2;
409    int result;
410
411    timedA = (TimedMethod const *)a;
412    timedB = (TimedMethod const *)b;
413    elapsed1 = timedA->elapsedInclusive;
414    elapsed2 = timedB->elapsedInclusive;
415    if (elapsed1 < elapsed2)
416        return 1;
417    if (elapsed1 > elapsed2)
418        return -1;
419
420    /* If the elapsed times of two methods are equal, then sort them
421     * into alphabetical order.
422     */
423    MethodEntry *methodA = timedA->method;
424    MethodEntry *methodB = timedB->method;
425    result = strcmp(methodA->className, methodB->className);
426    if (result == 0) {
427        if (methodA->methodName == NULL || methodB->methodName == NULL) {
428            unsigned int idA = methodA->methodId;
429            unsigned int idB = methodB->methodId;
430            if (idA < idB)
431                return -1;
432            if (idA > idB)
433                return 1;
434            return 0;
435        }
436        result = strcmp(methodA->methodName, methodB->methodName);
437        if (result == 0)
438            result = strcmp(methodA->signature, methodB->signature);
439    }
440    return result;
441}
442
443/*
444 * This comparison function is called from qsort() to sort
445 * MethodEntry pointers into alphabetical order of class names.
446 */
447int compareClassNames(const void *a, const void *b) {
448    int result;
449
450    const MethodEntry *methodA = *(const MethodEntry**)a;
451    const MethodEntry *methodB = *(const MethodEntry**)b;
452    result = strcmp(methodA->className, methodB->className);
453    if (result == 0) {
454        unsigned int idA = methodA->methodId;
455        unsigned int idB = methodB->methodId;
456        if (idA < idB)
457            return -1;
458        if (idA > idB)
459            return 1;
460        return 0;
461    }
462    return result;
463}
464
465/*
466 * This comparison function is called from qsort() to sort
467 * classes into decreasing order of exclusive elapsed time.
468 */
469int compareClassExclusive(const void *a, const void *b) {
470    uint64_t elapsed1, elapsed2;
471    int result;
472
473    const ClassEntry *classA = *(const ClassEntry**)a;
474    const ClassEntry *classB = *(const ClassEntry**)b;
475    elapsed1 = classA->elapsedExclusive;
476    elapsed2 = classB->elapsedExclusive;
477    if (elapsed1 < elapsed2)
478        return 1;
479    if (elapsed1 > elapsed2)
480        return -1;
481
482    /* If the elapsed times of two classs are equal, then sort them
483     * into alphabetical order.
484     */
485    result = strcmp(classA->className, classB->className);
486    if (result == 0) {
487        /* Break ties with the first method id.  This is probably not
488         * needed.
489         */
490        unsigned int idA = classA->methods[0]->methodId;
491        unsigned int idB = classB->methods[0]->methodId;
492        if (idA < idB)
493            return -1;
494        if (idA > idB)
495            return 1;
496        return 0;
497    }
498    return result;
499}
500
501/*
502 * This comparison function is called from qsort() to sort
503 * MethodEntry pointers into alphabetical order by method name,
504 * then by class name.
505 */
506int compareMethodNames(const void *a, const void *b) {
507    int result;
508
509    const MethodEntry *methodA = *(const MethodEntry**)a;
510    const MethodEntry *methodB = *(const MethodEntry**)b;
511    if (methodA->methodName == NULL || methodB->methodName == NULL) {
512        return compareClassNames(a, b);
513    }
514    result = strcmp(methodA->methodName, methodB->methodName);
515    if (result == 0) {
516        result = strcmp(methodA->className, methodB->className);
517        if (result == 0) {
518            unsigned int idA = methodA->methodId;
519            unsigned int idB = methodB->methodId;
520            if (idA < idB)
521                return -1;
522            if (idA > idB)
523                return 1;
524            return 0;
525        }
526    }
527    return result;
528}
529
530/*
531 * This comparison function is called from qsort() to sort
532 * unique methods into decreasing order of exclusive elapsed time.
533 */
534int compareUniqueExclusive(const void *a, const void *b) {
535    uint64_t elapsed1, elapsed2;
536    int result;
537
538    const UniqueMethodEntry *uniqueA = *(const UniqueMethodEntry**)a;
539    const UniqueMethodEntry *uniqueB = *(const UniqueMethodEntry**)b;
540    elapsed1 = uniqueA->elapsedExclusive;
541    elapsed2 = uniqueB->elapsedExclusive;
542    if (elapsed1 < elapsed2)
543        return 1;
544    if (elapsed1 > elapsed2)
545        return -1;
546
547    /* If the elapsed times of two methods are equal, then sort them
548     * into alphabetical order.
549     */
550    result = strcmp(uniqueA->methods[0]->className,
551                    uniqueB->methods[0]->className);
552    if (result == 0) {
553        unsigned int idA = uniqueA->methods[0]->methodId;
554        unsigned int idB = uniqueB->methods[0]->methodId;
555        if (idA < idB)
556            return -1;
557        if (idA > idB)
558            return 1;
559        return 0;
560    }
561    return result;
562}
563
564/*
565 * Free a DataKeys struct.
566 */
567void freeDataKeys(DataKeys* pKeys)
568{
569    if (pKeys == NULL)
570        return;
571
572    free(pKeys->fileData);
573    free(pKeys->threads);
574    free(pKeys->methods);
575    free(pKeys);
576}
577
578/*
579 * Find the offset to the next occurrence of the specified character.
580 *
581 * "data" should point somewhere within the current line.  "len" is the
582 * number of bytes left in the buffer.
583 *
584 * Returns -1 if we hit the end of the buffer.
585 */
586int findNextChar(const char* data, int len, char lookFor)
587{
588    const char* start = data;
589
590    while (len > 0) {
591        if (*data == lookFor)
592            return data - start;
593
594        data++;
595        len--;
596    }
597
598    return -1;
599}
600
601/*
602 * Count the number of lines until the next token.
603 *
604 * Returns -1 if none found before EOF.
605 */
606int countLinesToToken(const char* data, int len)
607{
608    int count = 0;
609    int next;
610
611    while (*data != TOKEN_CHAR) {
612        next = findNextChar(data, len, '\n');
613        if (next < 0)
614            return -1;
615        count++;
616        data += next+1;
617        len -= next+1;
618    }
619
620    return count;
621}
622
623/*
624 * Make sure we're at the start of the right section.
625 *
626 * Returns the length of the token line, or -1 if something is wrong.
627 */
628int checkToken(const char* data, int len, const char* cmpStr)
629{
630    int cmpLen = strlen(cmpStr);
631    int next;
632
633    if (*data != TOKEN_CHAR) {
634        fprintf(stderr,
635            "ERROR: not at start of %s (found '%.10s')\n", cmpStr, data);
636        return -1;
637    }
638
639    next = findNextChar(data, len, '\n');
640    if (next < cmpLen+1)
641        return -1;
642
643    if (strncmp(data+1, cmpStr, cmpLen) != 0) {
644        fprintf(stderr, "ERROR: '%s' not found (got '%.7s')\n", cmpStr, data+1);
645        return -1;
646    }
647
648    return next+1;
649}
650
651/*
652 * Parse the "*version" section.
653 */
654long parseVersion(DataKeys* pKeys, long offset, int verbose)
655{
656    char* data;
657    char* dataEnd;
658    int i, count, next;
659
660    if (offset < 0)
661        return -1;
662
663    data = pKeys->fileData + offset;
664    dataEnd = pKeys->fileData + pKeys->fileLen;
665    next = checkToken(data, dataEnd - data, "version");
666    if (next <= 0)
667        return -1;
668
669    data += next;
670
671    /*
672     * Count the number of items in the "version" section.
673     */
674    count = countLinesToToken(data, dataEnd - data);
675    if (count <= 0) {
676        fprintf(stderr,
677            "ERROR: failed while reading version (found %d)\n", count);
678        return -1;
679    }
680
681    /* find the end of the line */
682    next = findNextChar(data, dataEnd - data, '\n');
683    if (next < 0)
684        return -1;
685
686    data[next] = '\0';
687    versionNumber = strtoul(data, NULL, 0);
688    if (verbose)
689        printf("VERSION: %d\n", versionNumber);
690
691    data += next+1;
692
693    /* skip over the rest of the stuff, which is "name=value" lines */
694    for (i = 1; i < count; i++) {
695        next = findNextChar(data, dataEnd - data, '\n');
696        if (next < 0)
697            return -1;
698        //data[next] = '\0';
699        //printf("IGNORING: '%s'\n", data);
700        data += next+1;
701    }
702
703    return data - pKeys->fileData;
704}
705
706/*
707 * Parse the "*threads" section.
708 */
709long parseThreads(DataKeys* pKeys, long offset)
710{
711    char* data;
712    char* dataEnd;
713    int i, next, tab, count;
714
715    if (offset < 0)
716        return -1;
717
718    data = pKeys->fileData + offset;
719    dataEnd = pKeys->fileData + pKeys->fileLen;
720    next = checkToken(data, dataEnd - data, "threads");
721
722    data += next;
723
724    /*
725     * Count the number of thread entries (one per line).
726     */
727    count = countLinesToToken(data, dataEnd - data);
728    if (count <= 0) {
729        fprintf(stderr,
730            "ERROR: failed while reading threads (found %d)\n", count);
731        return -1;
732    }
733
734    //printf("+++ found %d threads\n", count);
735    pKeys->threads = (ThreadEntry*) malloc(sizeof(ThreadEntry) * count);
736    if (pKeys->threads == NULL)
737        return -1;
738
739    /*
740     * Extract all entries.
741     */
742    for (i = 0; i < count; i++) {
743        next = findNextChar(data, dataEnd - data, '\n');
744        assert(next > 0);
745        data[next] = '\0';
746
747        tab = findNextChar(data, next, '\t');
748        data[tab] = '\0';
749
750        pKeys->threads[i].threadId = atoi(data);
751        pKeys->threads[i].threadName = data + tab +1;
752
753        data += next+1;
754    }
755
756    pKeys->numThreads = count;
757    return data - pKeys->fileData;
758}
759
760/*
761 * Parse the "*methods" section.
762 */
763long parseMethods(DataKeys* pKeys, long offset)
764{
765    char* data;
766    char* dataEnd;
767    int i, next, count;
768
769    if (offset < 0)
770        return -1;
771
772    data = pKeys->fileData + offset;
773    dataEnd = pKeys->fileData + pKeys->fileLen;
774    next = checkToken(data, dataEnd - data, "methods");
775    if (next < 0)
776        return -1;
777
778    data += next;
779
780    /*
781     * Count the number of method entries (one per line).
782     */
783    count = countLinesToToken(data, dataEnd - data);
784    if (count <= 0) {
785        fprintf(stderr,
786            "ERROR: failed while reading methods (found %d)\n", count);
787        return -1;
788    }
789
790    /* Reserve an extra method at location 0 for the "toplevel" method,
791     * and another extra method for all other "unknown" methods.
792     */
793    count += 2;
794    pKeys->methods = (MethodEntry*) malloc(sizeof(MethodEntry) * count);
795    if (pKeys->methods == NULL)
796        return -1;
797    initMethodEntry(&pKeys->methods[TOPLEVEL_INDEX], 0, "(toplevel)",
798        NULL, NULL, NULL, NULL);
799    initMethodEntry(&pKeys->methods[UNKNOWN_INDEX], 0, "(unknown)",
800        NULL, NULL, NULL, NULL);
801
802    /*
803     * Extract all entries, starting with index 2.
804     */
805    for (i = UNKNOWN_INDEX + 1; i < count; i++) {
806        int tab1, tab2, tab3, tab4, tab5;
807        unsigned int id;
808        char* endptr;
809
810        next = findNextChar(data, dataEnd - data, '\n');
811        assert(next > 0);
812        data[next] = '\0';
813
814        tab1 = findNextChar(data, next, '\t');
815        tab2 = findNextChar(data+(tab1+1), next-(tab1+1), '\t');
816        tab3 = findNextChar(data+(tab1+tab2+2), next-(tab1+tab2+2), '\t');
817        tab4 = findNextChar(data+(tab1+tab2+tab3+3),
818                            next-(tab1+tab2+tab3+3), '\t');
819        tab5 = findNextChar(data+(tab1+tab2+tab3+tab4+4),
820                            next-(tab1+tab2+tab3+tab4+4), '\t');
821        if (tab1 < 0) {
822            fprintf(stderr, "ERROR: missing field on method line: '%s'\n",
823                    data);
824            return -1;
825        }
826        assert(data[tab1] == '\t');
827        data[tab1] = '\0';
828
829        id = strtoul(data, &endptr, 0);
830        if (*endptr != '\0') {
831            fprintf(stderr, "ERROR: bad method ID '%s'\n", data);
832            return -1;
833        }
834
835        // Allow files that specify just a function name, instead of requiring
836        // "class \t method \t signature"
837        if (tab2 > 0 && tab3 > 0) {
838            tab2 += tab1+1;
839            tab3 += tab2+1;
840            assert(data[tab2] == '\t');
841            assert(data[tab3] == '\t');
842            data[tab2] = data[tab3] = '\0';
843
844            // This is starting to get awkward.  Allow filename and line #.
845            if (tab4 > 0 && tab5 > 0) {
846                tab4 += tab3+1;
847                tab5 += tab4+1;
848
849                assert(data[tab4] == '\t');
850                assert(data[tab5] == '\t');
851                data[tab4] = data[tab5] = '\0';
852
853                initMethodEntry(&pKeys->methods[i], id, data + tab1 +1,
854                        data + tab2 +1, data + tab3 +1, data + tab4 +1,
855                        data + tab5 +1);
856            } else {
857                initMethodEntry(&pKeys->methods[i], id, data + tab1 +1,
858                        data + tab2 +1, data + tab3 +1, NULL, NULL);
859            }
860        } else {
861            initMethodEntry(&pKeys->methods[i], id, data + tab1 +1,
862                NULL, NULL, NULL, NULL);
863        }
864
865        data += next+1;
866    }
867
868    pKeys->numMethods = count;
869    return data - pKeys->fileData;
870}
871
872/*
873 * Parse the "*end" section.
874 */
875long parseEnd(DataKeys* pKeys, long offset)
876{
877    char* data;
878    char* dataEnd;
879    int next;
880
881    if (offset < 0)
882        return -1;
883
884    data = pKeys->fileData + offset;
885    dataEnd = pKeys->fileData + pKeys->fileLen;
886    next = checkToken(data, dataEnd - data, "end");
887    if (next < 0)
888        return -1;
889
890    data += next;
891
892    return data - pKeys->fileData;
893}
894
895/*
896 * Sort the thread list entries.
897 */
898static int compareThreads(const void* thread1, const void* thread2)
899{
900    return ((const ThreadEntry*) thread1)->threadId -
901            ((const ThreadEntry*) thread2)->threadId;
902}
903
904void sortThreadList(DataKeys* pKeys)
905{
906    qsort(pKeys->threads, pKeys->numThreads, sizeof(pKeys->threads[0]),
907        compareThreads);
908}
909
910/*
911 * Sort the method list entries.
912 */
913static int compareMethods(const void* meth1, const void* meth2)
914{
915    unsigned int id1, id2;
916
917    id1 = ((const MethodEntry*) meth1)->methodId;
918    id2 = ((const MethodEntry*) meth2)->methodId;
919    if (id1 < id2)
920        return -1;
921    if (id1 > id2)
922        return 1;
923    return 0;
924}
925
926void sortMethodList(DataKeys* pKeys)
927{
928    qsort(pKeys->methods, pKeys->numMethods, sizeof(MethodEntry),
929        compareMethods);
930}
931
932/*
933 * Parse the key section, and return a copy of the parsed contents.
934 */
935DataKeys* parseKeys(FILE *fp, int verbose)
936{
937    DataKeys* pKeys = NULL;
938    long offset;
939    int i;
940
941    pKeys = (DataKeys*) calloc(1, sizeof(DataKeys));
942    if (pKeys == NULL)
943        goto fail;
944
945    /*
946     * We load the entire file into memory.  We do this, rather than memory-
947     * mapping it, because we want to change some whitespace to NULs.
948     */
949    if (fseek(fp, 0L, SEEK_END) != 0) {
950        perror("fseek");
951        goto fail;
952    }
953    pKeys->fileLen = ftell(fp);
954    if (pKeys->fileLen == 0) {
955        fprintf(stderr, "Key file is empty.\n");
956        goto fail;
957    }
958    rewind(fp);
959
960    pKeys->fileData = (char*) malloc(pKeys->fileLen);
961    if (pKeys->fileData == NULL) {
962        fprintf(stderr, "ERROR: unable to alloc %ld bytes\n", pKeys->fileLen);
963        goto fail;
964    }
965
966    if (fread(pKeys->fileData, 1, pKeys->fileLen, fp) != (size_t) pKeys->fileLen)
967    {
968        fprintf(stderr, "ERROR: unable to read %ld bytes from trace file\n",
969            pKeys->fileLen);
970        goto fail;
971    }
972
973    offset = 0;
974
975    offset = parseVersion(pKeys, offset, verbose);
976    offset = parseThreads(pKeys, offset);
977    offset = parseMethods(pKeys, offset);
978    offset = parseEnd(pKeys, offset);
979    if (offset < 0)
980        goto fail;
981
982    /* Reduce our allocation now that we know where the end of the key section is. */
983    pKeys->fileData = (char *)realloc(pKeys->fileData, offset);
984    pKeys->fileLen = offset;
985    /* Leave fp pointing to the beginning of the data section. */
986    fseek(fp, offset, SEEK_SET);
987
988    sortThreadList(pKeys);
989    sortMethodList(pKeys);
990
991    /*
992     * Dump list of threads.
993     */
994    if (verbose) {
995        printf("Threads (%d):\n", pKeys->numThreads);
996        for (i = 0; i < pKeys->numThreads; i++) {
997            printf("%2d %s\n",
998                   pKeys->threads[i].threadId, pKeys->threads[i].threadName);
999        }
1000    }
1001
1002#if 0
1003    /*
1004     * Dump list of methods.
1005     */
1006    if (verbose) {
1007        printf("Methods (%d):\n", pKeys->numMethods);
1008        for (i = 0; i < pKeys->numMethods; i++) {
1009            printf("0x%08x %s : %s : %s\n",
1010                   pKeys->methods[i].methodId, pKeys->methods[i].className,
1011                   pKeys->methods[i].methodName, pKeys->methods[i].signature);
1012        }
1013    }
1014#endif
1015
1016    return pKeys;
1017
1018fail:
1019    freeDataKeys(pKeys);
1020    return NULL;
1021}
1022
1023
1024/*
1025 * Read values from the binary data file.
1026 */
1027
1028/* Make the return value "unsigned int" instead of "unsigned short" so that
1029 * we can detect EOF.
1030 */
1031unsigned int read2LE(FILE* fp)
1032{
1033    unsigned int val;
1034
1035    val = getc(fp);
1036    val |= getc(fp) << 8;
1037    return val;
1038}
1039unsigned int read4LE(FILE* fp)
1040{
1041    unsigned int val;
1042
1043    val = getc(fp);
1044    val |= getc(fp) << 8;
1045    val |= getc(fp) << 16;
1046    val |= getc(fp) << 24;
1047    return val;
1048}
1049unsigned long long read8LE(FILE* fp)
1050{
1051    unsigned long long val;
1052
1053    val = getc(fp);
1054    val |= (unsigned long long) getc(fp) << 8;
1055    val |= (unsigned long long) getc(fp) << 16;
1056    val |= (unsigned long long) getc(fp) << 24;
1057    val |= (unsigned long long) getc(fp) << 32;
1058    val |= (unsigned long long) getc(fp) << 40;
1059    val |= (unsigned long long) getc(fp) << 48;
1060    val |= (unsigned long long) getc(fp) << 56;
1061    return val;
1062}
1063
1064/*
1065 * Parse the header of the data section.
1066 *
1067 * Returns with the file positioned at the start of the record data.
1068 */
1069int parseDataHeader(FILE *fp, DataHeader* pHeader)
1070{
1071    int bytesToRead;
1072
1073    pHeader->magic = read4LE(fp);
1074    pHeader->version = read2LE(fp);
1075    pHeader->offsetToData = read2LE(fp);
1076    pHeader->startWhen = read8LE(fp);
1077    bytesToRead = pHeader->offsetToData - 16;
1078    if (pHeader->version == 1) {
1079        pHeader->recordSize = 9;
1080    } else if (pHeader->version == 2) {
1081        pHeader->recordSize = 10;
1082    } else if (pHeader->version == 3) {
1083        pHeader->recordSize = read2LE(fp);
1084        bytesToRead -= 2;
1085    } else {
1086        fprintf(stderr, "Unsupported trace file version: %d\n", pHeader->version);
1087        return -1;
1088    }
1089
1090    if (fseek(fp, bytesToRead, SEEK_CUR) != 0) {
1091        return -1;
1092    }
1093
1094    return 0;
1095}
1096
1097/*
1098 * Look up a method by it's method ID.
1099 *
1100 * Returns NULL if no matching method was found.
1101 */
1102MethodEntry* lookupMethod(DataKeys* pKeys, unsigned int methodId)
1103{
1104    int hi, lo, mid;
1105    unsigned int id;
1106
1107    lo = 0;
1108    hi = pKeys->numMethods - 1;
1109
1110    while (hi >= lo) {
1111        mid = (hi + lo) / 2;
1112
1113        id = pKeys->methods[mid].methodId;
1114        if (id == methodId)           /* match */
1115            return &pKeys->methods[mid];
1116        else if (id < methodId)       /* too low */
1117            lo = mid + 1;
1118        else                          /* too high */
1119            hi = mid - 1;
1120    }
1121
1122    return NULL;
1123}
1124
1125/*
1126 * Reads the next data record, and assigns the data values to threadId,
1127 * methodVal and elapsedTime.  On end-of-file, the threadId, methodVal,
1128 * and elapsedTime are unchanged.  Returns 1 on end-of-file, otherwise
1129 * returns 0.
1130 */
1131int readDataRecord(FILE *dataFp, DataHeader* dataHeader,
1132        int *threadId, unsigned int *methodVal, uint64_t *elapsedTime)
1133{
1134    int id;
1135    int bytesToRead;
1136
1137    bytesToRead = dataHeader->recordSize;
1138    if (dataHeader->version == 1) {
1139        id = getc(dataFp);
1140        bytesToRead -= 1;
1141    } else {
1142        id = read2LE(dataFp);
1143        bytesToRead -= 2;
1144    }
1145    if (id == EOF)
1146        return 1;
1147    *threadId = id;
1148
1149    *methodVal = read4LE(dataFp);
1150    *elapsedTime = read4LE(dataFp);
1151    bytesToRead -= 8;
1152
1153    while (bytesToRead-- > 0) {
1154        getc(dataFp);
1155    }
1156
1157    if (feof(dataFp)) {
1158        fprintf(stderr, "WARNING: hit EOF mid-record\n");
1159        return 1;
1160    }
1161    return 0;
1162}
1163
1164/*
1165 * Read the key file and use it to produce formatted output from the
1166 * data file.
1167 */
1168void dumpTrace()
1169{
1170    static const char* actionStr[] = { "ent", "xit", "unr", "???" };
1171    MethodEntry bogusMethod = { 0, "???", "???", "???", "???", -1, 0, 0, 0, 0,
1172                                {NULL, NULL}, {NULL, NULL}, {0, 0}, 0, 0, -1 };
1173    char bogusBuf[80];
1174    char spaces[MAX_STACK_DEPTH+1];
1175    FILE* dataFp = NULL;
1176    DataHeader dataHeader;
1177    DataKeys* pKeys = NULL;
1178    int i;
1179    TraceData traceData;
1180
1181    //printf("Dumping '%s' '%s'\n", dataFileName, keyFileName);
1182
1183    memset(spaces, '.', MAX_STACK_DEPTH);
1184    spaces[MAX_STACK_DEPTH] = '\0';
1185
1186    for (i = 0; i < MAX_THREADS; i++)
1187        traceData.depth[i] = 2;       // adjust for return from start function
1188
1189    dataFp = fopen(gOptions.traceFileName, "r");
1190    if (dataFp == NULL)
1191        goto bail;
1192
1193    if ((pKeys = parseKeys(dataFp, 1)) == NULL)
1194        goto bail;
1195
1196    if (parseDataHeader(dataFp, &dataHeader) < 0)
1197        goto bail;
1198
1199    printf("Trace (threadID action usecs class.method signature):\n");
1200
1201    while (1) {
1202        MethodEntry* method;
1203        int threadId;
1204        unsigned int methodVal;
1205        uint64_t elapsedTime;
1206        int action, printDepth;
1207        unsigned int methodId, lastEnter = 0;
1208        int mismatch = 0;
1209        char depthNote;
1210
1211        /*
1212         * Extract values from file.
1213         */
1214        if (readDataRecord(dataFp, &dataHeader, &threadId, &methodVal, &elapsedTime))
1215            break;
1216
1217        action = METHOD_ACTION(methodVal);
1218        methodId = METHOD_ID(methodVal);
1219
1220        /*
1221         * Generate a line of output.
1222         */
1223        if (action == METHOD_TRACE_ENTER) {
1224            traceData.depth[threadId]++;
1225            lastEnter = methodId;
1226        } else {
1227            /* quick test for mismatched adjacent enter/exit */
1228            if (lastEnter != 0 && lastEnter != methodId)
1229                mismatch = 1;
1230        }
1231
1232        printDepth = traceData.depth[threadId];
1233        depthNote = ' ';
1234        if (printDepth < 0) {
1235            printDepth = 0;
1236            depthNote = '-';
1237        } else if (printDepth > MAX_STACK_DEPTH) {
1238            printDepth = MAX_STACK_DEPTH;
1239            depthNote = '+';
1240        }
1241
1242        method = lookupMethod(pKeys, methodId);
1243        if (method == NULL) {
1244            method = &bogusMethod;
1245            sprintf(bogusBuf, "methodId: %#x", methodId);
1246            method->signature = bogusBuf;
1247        }
1248
1249	if (method->methodName) {
1250	    printf("%2d %s%c %8lld%c%s%s.%s %s\n", threadId,
1251		   actionStr[action], mismatch ? '!' : ' ',
1252		   elapsedTime, depthNote,
1253		   spaces + (MAX_STACK_DEPTH - printDepth),
1254		   method->className, method->methodName, method->signature);
1255	} else {
1256	    printf("%2d %s%c %8lld%c%s%s\n", threadId,
1257		   actionStr[action], mismatch ? '!' : ' ',
1258		   elapsedTime, depthNote,
1259		   spaces + (MAX_STACK_DEPTH - printDepth),
1260		   method->className);
1261	}
1262
1263        if (action != METHOD_TRACE_ENTER) {
1264            traceData.depth[threadId]--;  /* METHOD_TRACE_EXIT or METHOD_TRACE_UNROLL */
1265            lastEnter = 0;
1266        }
1267
1268        mismatch = 0;
1269    }
1270
1271bail:
1272    if (dataFp != NULL)
1273        fclose(dataFp);
1274    if (pKeys != NULL)
1275        freeDataKeys(pKeys);
1276}
1277
1278/* This routine adds the given time to the parent and child methods.
1279 * This is called when the child routine exits, after the child has
1280 * been popped from the stack.  The elapsedTime parameter is the
1281 * duration of the child routine, including time spent in called routines.
1282 */
1283void addInclusiveTime(MethodEntry *parent, MethodEntry *child,
1284                      uint64_t elapsedTime)
1285{
1286    TimedMethod *pTimed;
1287
1288#if 0
1289    bool verbose = false;
1290    if (strcmp(child->className, debugClassName) == 0)
1291        verbose = true;
1292#endif
1293
1294    int childIsRecursive = (child->recursiveEntries > 0);
1295    int parentIsRecursive = (parent->recursiveEntries > 1);
1296
1297    if (child->recursiveEntries == 0) {
1298        child->elapsedInclusive += elapsedTime;
1299    } else if (child->recursiveEntries == 1) {
1300        child->recursiveInclusive += elapsedTime;
1301    }
1302    child->numCalls[childIsRecursive] += 1;
1303
1304#if 0
1305    if (verbose) {
1306        fprintf(stderr,
1307                "%s %d elapsedTime: %lld eI: %lld, rI: %lld\n",
1308                child->className, child->recursiveEntries,
1309                elapsedTime, child->elapsedInclusive,
1310                child->recursiveInclusive);
1311    }
1312#endif
1313
1314    /* Find the child method in the parent */
1315    TimedMethod *children = parent->children[parentIsRecursive];
1316    for (pTimed = children; pTimed; pTimed = pTimed->next) {
1317        if (pTimed->method == child) {
1318            pTimed->elapsedInclusive += elapsedTime;
1319            pTimed->numCalls += 1;
1320            break;
1321        }
1322    }
1323    if (pTimed == NULL) {
1324        /* Allocate a new TimedMethod */
1325        pTimed = (TimedMethod *) malloc(sizeof(TimedMethod));
1326        pTimed->elapsedInclusive = elapsedTime;
1327        pTimed->numCalls = 1;
1328        pTimed->method = child;
1329
1330        /* Add it to the front of the list */
1331        pTimed->next = children;
1332        parent->children[parentIsRecursive] = pTimed;
1333    }
1334
1335    /* Find the parent method in the child */
1336    TimedMethod *parents = child->parents[childIsRecursive];
1337    for (pTimed = parents; pTimed; pTimed = pTimed->next) {
1338        if (pTimed->method == parent) {
1339            pTimed->elapsedInclusive += elapsedTime;
1340            pTimed->numCalls += 1;
1341            break;
1342        }
1343    }
1344    if (pTimed == NULL) {
1345        /* Allocate a new TimedMethod */
1346        pTimed = (TimedMethod *) malloc(sizeof(TimedMethod));
1347        pTimed->elapsedInclusive = elapsedTime;
1348        pTimed->numCalls = 1;
1349        pTimed->method = parent;
1350
1351        /* Add it to the front of the list */
1352        pTimed->next = parents;
1353        child->parents[childIsRecursive] = pTimed;
1354    }
1355
1356#if 0
1357    if (verbose) {
1358        fprintf(stderr,
1359                "  %s %d eI: %lld\n",
1360                parent->className, parent->recursiveEntries,
1361                pTimed->elapsedInclusive);
1362    }
1363#endif
1364}
1365
1366/* Sorts a linked list and returns a newly allocated array containing
1367 * the sorted entries.
1368 */
1369TimedMethod *sortTimedMethodList(TimedMethod *list, int *num)
1370{
1371    int ii;
1372    TimedMethod *pTimed, *sorted;
1373
1374    /* Count the elements */
1375    int num_entries = 0;
1376    for (pTimed = list; pTimed; pTimed = pTimed->next)
1377        num_entries += 1;
1378    *num = num_entries;
1379    if (num_entries == 0)
1380        return NULL;
1381
1382    /* Copy all the list elements to a new array and sort them */
1383    sorted = (TimedMethod *) malloc(sizeof(TimedMethod) * num_entries);
1384    for (ii = 0, pTimed = list; pTimed; pTimed = pTimed->next, ++ii)
1385        memcpy(&sorted[ii], pTimed, sizeof(TimedMethod));
1386    qsort(sorted, num_entries, sizeof(TimedMethod), compareTimedMethod);
1387
1388    /* Fix up the "next" pointers so that they work. */
1389    for (ii = 0; ii < num_entries - 1; ++ii)
1390        sorted[ii].next = &sorted[ii + 1];
1391    sorted[num_entries - 1].next = NULL;
1392
1393    return sorted;
1394}
1395
1396/* Define flag values for printInclusiveMethod() */
1397static const int kIsRecursive = 1;
1398
1399/* This prints the inclusive stats for all the parents or children of a
1400 * method, depending on the list that is passed in.
1401 */
1402void printInclusiveMethod(MethodEntry *method, TimedMethod *list, int numCalls,
1403                          int flags)
1404{
1405    int num;
1406    TimedMethod *pTimed;
1407    char buf[80];
1408    char *anchor_close;
1409    char *spaces = "      ";    /* 6 spaces */
1410    int num_spaces = strlen(spaces);
1411    char *space_ptr = &spaces[num_spaces];
1412    char *className, *methodName, *signature;
1413    char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
1414    char signatureBuf[HTML_BUFSIZE];
1415
1416    anchor_close = "";
1417    if (gOptions.outputHtml)
1418        anchor_close = "</a>";
1419
1420    TimedMethod *sorted = sortTimedMethodList(list,  &num);
1421    double methodTotal = method->elapsedInclusive;
1422    for (pTimed = sorted; pTimed; pTimed = pTimed->next) {
1423        MethodEntry *relative = pTimed->method;
1424        className = (char*)(relative->className);
1425        methodName = (char*)(relative->methodName);
1426        signature = (char*)(relative->signature);
1427        double per = 100.0 * pTimed->elapsedInclusive / methodTotal;
1428        sprintf(buf, "[%d]", relative->index);
1429        if (gOptions.outputHtml) {
1430            int len = strlen(buf);
1431            if (len > num_spaces)
1432                len = num_spaces;
1433            sprintf(buf, "<a href=\"#m%d\">[%d]",
1434                    relative->index, relative->index);
1435            space_ptr = &spaces[len];
1436            className = htmlEscape(className, classBuf, HTML_BUFSIZE);
1437            methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
1438            signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
1439        }
1440        int nCalls = numCalls;
1441        if (nCalls == 0)
1442            nCalls = relative->numCalls[0] + relative->numCalls[1];
1443        if (relative->methodName) {
1444            if (flags & kIsRecursive) {
1445                // Don't display percentages for recursive functions
1446                printf("%6s %5s   %6s %s%6s%s %6d/%-6d %9llu %s.%s %s\n",
1447                       "", "", "",
1448                       space_ptr, buf, anchor_close,
1449                       pTimed->numCalls, nCalls,
1450                       pTimed->elapsedInclusive,
1451                       className, methodName, signature);
1452            } else {
1453                printf("%6s %5s   %5.1f%% %s%6s%s %6d/%-6d %9llu %s.%s %s\n",
1454                       "", "", per,
1455                       space_ptr, buf, anchor_close,
1456                       pTimed->numCalls, nCalls,
1457                       pTimed->elapsedInclusive,
1458                       className, methodName, signature);
1459            }
1460        } else {
1461            if (flags & kIsRecursive) {
1462                // Don't display percentages for recursive functions
1463                printf("%6s %5s   %6s %s%6s%s %6d/%-6d %9llu %s\n",
1464                       "", "", "",
1465                       space_ptr, buf, anchor_close,
1466                       pTimed->numCalls, nCalls,
1467                       pTimed->elapsedInclusive,
1468                       className);
1469            } else {
1470                printf("%6s %5s   %5.1f%% %s%6s%s %6d/%-6d %9llu %s\n",
1471                       "", "", per,
1472                       space_ptr, buf, anchor_close,
1473                       pTimed->numCalls, nCalls,
1474                       pTimed->elapsedInclusive,
1475                       className);
1476            }
1477        }
1478    }
1479}
1480
1481void countRecursiveEntries(CallStack *pStack, int top, MethodEntry *method)
1482{
1483    int ii;
1484
1485    method->recursiveEntries = 0;
1486    for (ii = 0; ii < top; ++ii) {
1487        if (pStack->calls[ii].method == method)
1488            method->recursiveEntries += 1;
1489    }
1490}
1491
1492void stackDump(CallStack *pStack, int top)
1493{
1494    int ii;
1495
1496    for (ii = 0; ii < top; ++ii) {
1497        MethodEntry *method = pStack->calls[ii].method;
1498        uint64_t entryTime = pStack->calls[ii].entryTime;
1499        if (method->methodName) {
1500            fprintf(stderr, "  %2d: %8llu %s.%s %s\n", ii, entryTime,
1501                   method->className, method->methodName, method->signature);
1502        } else {
1503            fprintf(stderr, "  %2d: %8llu %s\n", ii, entryTime, method->className);
1504        }
1505    }
1506}
1507
1508void outputTableOfContents()
1509{
1510    printf("<a name=\"contents\"></a>\n");
1511    printf("<h2>Table of Contents</h2>\n");
1512    printf("<ul>\n");
1513    printf("  <li><a href=\"#exclusive\">Exclusive profile</a></li>\n");
1514    printf("  <li><a href=\"#inclusive\">Inclusive profile</a></li>\n");
1515    printf("  <li><a href=\"#class\">Class/method profile</a></li>\n");
1516    printf("  <li><a href=\"#method\">Method/class profile</a></li>\n");
1517    printf("</ul>\n\n");
1518}
1519
1520void outputNavigationBar()
1521{
1522    printf("<a href=\"#contents\">[Top]</a>\n");
1523    printf("<a href=\"#exclusive\">[Exclusive]</a>\n");
1524    printf("<a href=\"#inclusive\">[Inclusive]</a>\n");
1525    printf("<a href=\"#class\">[Class]</a>\n");
1526    printf("<a href=\"#method\">[Method]</a>\n");
1527    printf("<br><br>\n");
1528}
1529
1530void printExclusiveProfile(MethodEntry **pMethods, int numMethods,
1531                           uint64_t sumThreadTime)
1532{
1533    int ii;
1534    MethodEntry* method;
1535    double total, sum, per, sum_per;
1536    char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
1537    char signatureBuf[HTML_BUFSIZE];
1538    char anchor_buf[80];
1539    char *anchor_close = "";
1540
1541    total = sumThreadTime;
1542    anchor_buf[0] = 0;
1543    if (gOptions.outputHtml) {
1544        anchor_close = "</a>";
1545        printf("<a name=\"exclusive\"></a>\n");
1546        printf("<hr>\n");
1547        outputNavigationBar();
1548    } else {
1549        printf("\n%s\n", profileSeparator);
1550    }
1551
1552    /* First, sort the methods into decreasing order of inclusive
1553     * elapsed time so that we can assign the method indices.
1554     */
1555    qsort(pMethods, numMethods, sizeof(MethodEntry*), compareElapsedInclusive);
1556
1557    for (ii = 0; ii < numMethods; ++ii)
1558        pMethods[ii]->index = ii;
1559
1560    /* Sort the methods into decreasing order of exclusive elapsed time.
1561     */
1562    qsort(pMethods, numMethods, sizeof(MethodEntry*),
1563          compareElapsedExclusive);
1564
1565    printf("Total cycles: %llu\n\n", sumThreadTime);
1566    if (gOptions.outputHtml) {
1567        printf("<br><br>\n");
1568    }
1569    printf("Exclusive elapsed times for each method, not including time spent in\n");
1570    printf("children, sorted by exclusive time.\n\n");
1571    if (gOptions.outputHtml) {
1572        printf("<br><br>\n<pre>\n");
1573    }
1574
1575    printf("    Usecs  self %%  sum %%  Method\n");
1576    sum = 0;
1577
1578    for (ii = 0; ii < numMethods; ++ii) {
1579        char *className, *methodName, *signature;
1580
1581        method = pMethods[ii];
1582        /* Don't show methods with zero cycles */
1583        if (method->elapsedExclusive == 0)
1584            break;
1585        className = (char*)(method->className);
1586        methodName = (char*)(method->methodName);
1587        signature = (char*)(method->signature);
1588        sum += method->elapsedExclusive;
1589        per = 100.0 * method->elapsedExclusive / total;
1590        sum_per = 100.0 * sum / total;
1591        if (gOptions.outputHtml) {
1592            sprintf(anchor_buf, "<a href=\"#m%d\">", method->index);
1593            className = htmlEscape(className, classBuf, HTML_BUFSIZE);
1594            methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
1595            signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
1596        }
1597        if (method->methodName) {
1598            printf("%9llu  %6.2f %6.2f  %s[%d]%s %s.%s %s\n",
1599                   method->elapsedExclusive, per, sum_per,
1600                   anchor_buf, method->index, anchor_close,
1601                   className, methodName, signature);
1602        } else {
1603            printf("%9llu  %6.2f %6.2f  %s[%d]%s %s\n",
1604                   method->elapsedExclusive, per, sum_per,
1605                   anchor_buf, method->index, anchor_close,
1606                   className);
1607        }
1608    }
1609    if (gOptions.outputHtml) {
1610        printf("</pre>\n");
1611    }
1612}
1613
1614/* check to make sure that the child method meets the threshold of the parent */
1615int checkThreshold(MethodEntry* parent, MethodEntry* child)
1616{
1617    double parentTime = parent->elapsedInclusive;
1618    double childTime = child->elapsedInclusive;
1619    int64_t percentage = (childTime / parentTime) * 100.0;
1620    return (percentage < gOptions.threshold) ? 0 : 1;
1621}
1622
1623void createLabels(FILE* file, MethodEntry* method)
1624{
1625    fprintf(file, "node%d[label = \"[%d] %s.%s (%llu, %llu, %d)\"]\n",
1626             method->index, method->index, method->className, method->methodName,
1627             method->elapsedInclusive / 1000,
1628             method->elapsedExclusive / 1000,
1629             method->numCalls[0]);
1630
1631    method->graphState = GRAPH_LABEL_VISITED;
1632
1633    TimedMethod* child;
1634    for (child = method->children[0] ; child ; child = child->next) {
1635        MethodEntry* childMethod = child->method;
1636
1637        if ((childMethod->graphState & GRAPH_LABEL_VISITED) == 0 && checkThreshold(method, childMethod)) {
1638            createLabels(file, child->method);
1639        }
1640    }
1641}
1642
1643void createLinks(FILE* file, MethodEntry* method)
1644{
1645    method->graphState |= GRAPH_NODE_VISITED;
1646
1647    TimedMethod* child;
1648    for (child = method->children[0] ; child ; child = child->next) {
1649        MethodEntry* childMethod = child->method;
1650        if (checkThreshold(method, child->method)) {
1651            fprintf(file, "node%d -> node%d\n", method->index, child->method->index);
1652            // only visit children that haven't been visited before
1653            if ((childMethod->graphState & GRAPH_NODE_VISITED) == 0) {
1654                createLinks(file, child->method);
1655            }
1656        }
1657    }
1658}
1659
1660void createInclusiveProfileGraphNew(DataKeys* dataKeys)
1661{
1662    // create a temporary file in /tmp
1663    char path[FILENAME_MAX];
1664    if (gOptions.keepDotFile) {
1665        snprintf(path, FILENAME_MAX, "%s.dot", gOptions.graphFileName);
1666    } else {
1667        snprintf(path, FILENAME_MAX, "/tmp/dot-%d-%d.dot", (int)time(NULL), rand());
1668    }
1669
1670    FILE* file = fopen(path, "w+");
1671
1672    fprintf(file, "digraph g {\nnode [shape = record,height=.1];\n");
1673
1674    createLabels(file, dataKeys->methods);
1675    createLinks(file, dataKeys->methods);
1676
1677    fprintf(file, "}");
1678    fclose(file);
1679
1680    // now that we have the dot file generate the image
1681    char command[1024];
1682    snprintf(command, 1024, "dot -Tpng -o '%s' '%s'", gOptions.graphFileName, path);
1683
1684    system(command);
1685
1686    if (! gOptions.keepDotFile) {
1687        remove(path);
1688    }
1689}
1690
1691void printInclusiveProfile(MethodEntry **pMethods, int numMethods,
1692                           uint64_t sumThreadTime)
1693{
1694    int ii;
1695    MethodEntry* method;
1696    double total, sum, per, sum_per;
1697    char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
1698    char signatureBuf[HTML_BUFSIZE];
1699    char anchor_buf[80];
1700    char *anchor_close = "";
1701
1702    total = sumThreadTime;
1703    anchor_buf[0] = 0;
1704    if (gOptions.outputHtml) {
1705        anchor_close = "</a>";
1706        printf("<a name=\"inclusive\"></a>\n");
1707        printf("<hr>\n");
1708        outputNavigationBar();
1709    } else {
1710        printf("\n%s\n", profileSeparator);
1711    }
1712
1713    /* Sort the methods into decreasing order of inclusive elapsed time. */
1714    qsort(pMethods, numMethods, sizeof(MethodEntry*),
1715          compareElapsedInclusive);
1716
1717    printf("\nInclusive elapsed times for each method and its parents and children,\n");
1718    printf("sorted by inclusive time.\n\n");
1719
1720    if (gOptions.outputHtml) {
1721        printf("<br><br>\n<pre>\n");
1722    }
1723
1724    printf("index  %%/total %%/self  index     calls         usecs name\n");
1725    for (ii = 0; ii < numMethods; ++ii) {
1726        int num;
1727        TimedMethod *pTimed;
1728        double excl_per;
1729        char buf[40];
1730        char *className, *methodName, *signature;
1731
1732        method = pMethods[ii];
1733        /* Don't show methods with zero cycles */
1734        if (method->elapsedInclusive == 0)
1735            break;
1736
1737        className = (char*)(method->className);
1738        methodName = (char*)(method->methodName);
1739        signature = (char*)(method->signature);
1740
1741        if (gOptions.outputHtml) {
1742            printf("<a name=\"m%d\"></a>", method->index);
1743            className = htmlEscape(className, classBuf, HTML_BUFSIZE);
1744            methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
1745            signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
1746        }
1747        printf("----------------------------------------------------\n");
1748
1749        /* Sort and print the parents */
1750        int numCalls = method->numCalls[0] + method->numCalls[1];
1751        printInclusiveMethod(method, method->parents[0], numCalls, 0);
1752        if (method->parents[1]) {
1753            printf("               +++++++++++++++++++++++++\n");
1754            printInclusiveMethod(method, method->parents[1], numCalls,
1755                                 kIsRecursive);
1756        }
1757
1758        per = 100.0 * method->elapsedInclusive / total;
1759        sprintf(buf, "[%d]", ii);
1760        if (method->methodName) {
1761            printf("%-6s %5.1f%%   %5s %6s %6d+%-6d %9llu %s.%s %s\n",
1762                   buf,
1763                   per, "", "", method->numCalls[0], method->numCalls[1],
1764                   method->elapsedInclusive,
1765                   className, methodName, signature);
1766        } else {
1767            printf("%-6s %5.1f%%   %5s %6s %6d+%-6d %9llu %s\n",
1768                   buf,
1769                   per, "", "", method->numCalls[0], method->numCalls[1],
1770                   method->elapsedInclusive,
1771                   className);
1772        }
1773        excl_per = 100.0 * method->topExclusive / method->elapsedInclusive;
1774        printf("%6s %5s   %5.1f%% %6s %6s %6s %9llu\n",
1775               "", "", excl_per, "excl", "", "", method->topExclusive);
1776
1777        /* Sort and print the children */
1778        printInclusiveMethod(method, method->children[0], 0, 0);
1779        if (method->children[1]) {
1780            printf("               +++++++++++++++++++++++++\n");
1781            printInclusiveMethod(method, method->children[1], 0,
1782                                 kIsRecursive);
1783        }
1784    }
1785    if (gOptions.outputHtml) {
1786        printf("</pre>\n");
1787    }
1788}
1789
1790void createClassList(TraceData* traceData, MethodEntry **pMethods, int numMethods)
1791{
1792    int ii;
1793
1794    /* Sort the methods into alphabetical order to find the unique class
1795     * names.
1796     */
1797    qsort(pMethods, numMethods, sizeof(MethodEntry*), compareClassNames);
1798
1799    /* Count the number of unique class names. */
1800    const char *currentClassName = "";
1801    const char *firstClassName = NULL;
1802    traceData->numClasses = 0;
1803    for (ii = 0; ii < numMethods; ++ii) {
1804        if (pMethods[ii]->methodName == NULL) {
1805            continue;
1806        }
1807        if (strcmp(pMethods[ii]->className, currentClassName) != 0) {
1808            // Remember the first one
1809            if (firstClassName == NULL) {
1810                firstClassName = pMethods[ii]->className;
1811            }
1812            traceData->numClasses += 1;
1813            currentClassName = pMethods[ii]->className;
1814        }
1815    }
1816
1817    if (traceData->numClasses == 0) {
1818        traceData->classes = NULL;
1819        return;
1820    }
1821
1822    /* Allocate space for all of the unique class names */
1823    traceData->classes = (ClassEntry *) malloc(sizeof(ClassEntry) * traceData->numClasses);
1824
1825    /* Initialize the classes array */
1826    memset(traceData->classes, 0, sizeof(ClassEntry) * traceData->numClasses);
1827    ClassEntry *pClass = traceData->classes;
1828    pClass->className = currentClassName = firstClassName;
1829    int prevNumMethods = 0;
1830    for (ii = 0; ii < numMethods; ++ii) {
1831        if (pMethods[ii]->methodName == NULL) {
1832            continue;
1833        }
1834        if (strcmp(pMethods[ii]->className, currentClassName) != 0) {
1835            pClass->numMethods = prevNumMethods;
1836            (++pClass)->className = currentClassName = pMethods[ii]->className;
1837            prevNumMethods = 0;
1838        }
1839        prevNumMethods += 1;
1840    }
1841    pClass->numMethods = prevNumMethods;
1842
1843    /* Create the array of MethodEntry pointers for each class */
1844    pClass = NULL;
1845    currentClassName = "";
1846    int nextMethod = 0;
1847    for (ii = 0; ii < numMethods; ++ii) {
1848        if (pMethods[ii]->methodName == NULL) {
1849            continue;
1850        }
1851        if (strcmp(pMethods[ii]->className, currentClassName) != 0) {
1852            currentClassName = pMethods[ii]->className;
1853            if (pClass == NULL)
1854                pClass = traceData->classes;
1855            else
1856                pClass++;
1857            /* Allocate space for the methods array */
1858            int nbytes = sizeof(MethodEntry*) * pClass->numMethods;
1859            pClass->methods = (MethodEntry**) malloc(nbytes);
1860            nextMethod = 0;
1861        }
1862        pClass->methods[nextMethod++] = pMethods[ii];
1863    }
1864}
1865
1866/* Prints a number of html non-breaking spaces according so that the length
1867 * of the string "buf" is at least "width" characters wide.  If width is
1868 * negative, then trailing spaces are added instead of leading spaces.
1869 */
1870void printHtmlField(char *buf, int width)
1871{
1872    int ii;
1873
1874    int leadingSpaces = 1;
1875    if (width < 0) {
1876        width = -width;
1877        leadingSpaces = 0;
1878    }
1879    int len = strlen(buf);
1880    int numSpaces = width - len;
1881    if (numSpaces <= 0) {
1882        printf("%s", buf);
1883        return;
1884    }
1885    if (leadingSpaces == 0)
1886        printf("%s", buf);
1887    for (ii = 0; ii < numSpaces; ++ii)
1888        printf("&nbsp;");
1889    if (leadingSpaces == 1)
1890        printf("%s", buf);
1891}
1892
1893void printClassProfiles(TraceData* traceData, uint64_t sumThreadTime)
1894{
1895    int ii, jj;
1896    MethodEntry* method;
1897    double total, sum, per, sum_per;
1898    char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
1899    char signatureBuf[HTML_BUFSIZE];
1900
1901    total = sumThreadTime;
1902    if (gOptions.outputHtml) {
1903        printf("<a name=\"class\"></a>\n");
1904        printf("<hr>\n");
1905        outputNavigationBar();
1906    } else {
1907        printf("\n%s\n", profileSeparator);
1908    }
1909
1910    if (traceData->numClasses == 0) {
1911        printf("\nNo classes.\n");
1912        if (gOptions.outputHtml) {
1913            printf("<br><br>\n");
1914        }
1915        return;
1916    }
1917
1918    printf("\nExclusive elapsed time for each class, summed over all the methods\n");
1919    printf("in the class.\n\n");
1920    if (gOptions.outputHtml) {
1921        printf("<br><br>\n");
1922    }
1923
1924    /* For each class, sum the exclusive times in all of the methods
1925     * in that class.  Also sum the number of method calls.  Also
1926     * sort the methods so the most expensive appear at the top.
1927     */
1928    ClassEntry *pClass = traceData->classes;
1929    for (ii = 0; ii < traceData->numClasses; ++ii, ++pClass) {
1930        //printf("%s %d methods\n", pClass->className, pClass->numMethods);
1931        int numMethods = pClass->numMethods;
1932        for (jj = 0; jj < numMethods; ++jj) {
1933            method = pClass->methods[jj];
1934            pClass->elapsedExclusive += method->elapsedExclusive;
1935            pClass->numCalls[0] += method->numCalls[0];
1936            pClass->numCalls[1] += method->numCalls[1];
1937        }
1938
1939        /* Sort the methods into decreasing order of exclusive time */
1940        qsort(pClass->methods, numMethods, sizeof(MethodEntry*),
1941              compareElapsedExclusive);
1942    }
1943
1944    /* Allocate an array of pointers to the classes for more efficient
1945     * sorting.
1946     */
1947    ClassEntry **pClasses;
1948    pClasses = (ClassEntry**) malloc(sizeof(ClassEntry*) * traceData->numClasses);
1949    for (ii = 0; ii < traceData->numClasses; ++ii)
1950        pClasses[ii] = &traceData->classes[ii];
1951
1952    /* Sort the classes into decreasing order of exclusive time */
1953    qsort(pClasses, traceData->numClasses, sizeof(ClassEntry*), compareClassExclusive);
1954
1955    if (gOptions.outputHtml) {
1956        printf("<div class=\"header\"><span class=\"parent\">&nbsp;</span>&nbsp;&nbsp;&nbsp;");
1957        printf("Cycles %%/total Cumul.%% &nbsp;Calls+Recur&nbsp; Class</div>\n");
1958    } else {
1959        printf("   Cycles %%/total Cumul.%%  Calls+Recur  Class\n");
1960    }
1961
1962    sum = 0;
1963    for (ii = 0; ii < traceData->numClasses; ++ii) {
1964        char *className, *methodName, *signature;
1965
1966        /* Skip classes with zero cycles */
1967        pClass = pClasses[ii];
1968        if (pClass->elapsedExclusive == 0)
1969            break;
1970
1971        per = 100.0 * pClass->elapsedExclusive / total;
1972        sum += pClass->elapsedExclusive;
1973        sum_per = 100.0 * sum / total;
1974        className = (char*)(pClass->className);
1975        if (gOptions.outputHtml) {
1976            char buf[80];
1977
1978            className = htmlEscape(className, classBuf, HTML_BUFSIZE);
1979            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);
1980            sprintf(buf, "%llu", pClass->elapsedExclusive);
1981            printHtmlField(buf, 9);
1982            printf(" ");
1983            sprintf(buf, "%.1f", per);
1984            printHtmlField(buf, 7);
1985            printf(" ");
1986            sprintf(buf, "%.1f", sum_per);
1987            printHtmlField(buf, 7);
1988            printf(" ");
1989            sprintf(buf, "%d", pClass->numCalls[0]);
1990            printHtmlField(buf, 6);
1991            printf("+");
1992            sprintf(buf, "%d", pClass->numCalls[1]);
1993            printHtmlField(buf, -6);
1994            printf(" ");
1995            printf("%s", className);
1996            printf("</div>\n");
1997            printf("<div class=\"parent\" id=\"d%d\">\n", ii);
1998        } else {
1999            printf("---------------------------------------------\n");
2000            printf("%9llu %7.1f %7.1f %6d+%-6d %s\n",
2001                   pClass->elapsedExclusive, per, sum_per,
2002                   pClass->numCalls[0], pClass->numCalls[1],
2003                   className);
2004        }
2005
2006        int numMethods = pClass->numMethods;
2007        double classExclusive = pClass->elapsedExclusive;
2008        double sumMethods = 0;
2009        for (jj = 0; jj < numMethods; ++jj) {
2010            method = pClass->methods[jj];
2011            methodName = (char*)(method->methodName);
2012            signature = (char*)(method->signature);
2013            per = 100.0 * method->elapsedExclusive / classExclusive;
2014            sumMethods += method->elapsedExclusive;
2015            sum_per = 100.0 * sumMethods / classExclusive;
2016            if (gOptions.outputHtml) {
2017                char buf[80];
2018
2019                methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
2020                signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
2021                printf("<div class=\"leaf\"><span class=\"leaf\">&nbsp;</span>");
2022                sprintf(buf, "%llu", method->elapsedExclusive);
2023                printHtmlField(buf, 9);
2024                printf("&nbsp;");
2025                sprintf(buf, "%llu", method->elapsedInclusive);
2026                printHtmlField(buf, 9);
2027                printf("&nbsp;");
2028                sprintf(buf, "%.1f", per);
2029                printHtmlField(buf, 7);
2030                printf("&nbsp;");
2031                sprintf(buf, "%.1f", sum_per);
2032                printHtmlField(buf, 7);
2033                printf("&nbsp;");
2034                sprintf(buf, "%d", method->numCalls[0]);
2035                printHtmlField(buf, 6);
2036                printf("+");
2037                sprintf(buf, "%d", method->numCalls[1]);
2038                printHtmlField(buf, -6);
2039                printf("&nbsp;");
2040                printf("<a href=\"#m%d\">[%d]</a>&nbsp;%s&nbsp;%s",
2041                       method->index, method->index, methodName, signature);
2042                printf("</div>\n");
2043            } else {
2044                printf("%9llu %9llu %7.1f %7.1f %6d+%-6d [%d] %s %s\n",
2045                       method->elapsedExclusive,
2046                       method->elapsedInclusive,
2047                       per, sum_per,
2048                       method->numCalls[0], method->numCalls[1],
2049                       method->index, methodName, signature);
2050            }
2051        }
2052        if (gOptions.outputHtml) {
2053            printf("</div>\n");
2054        }
2055    }
2056}
2057
2058void createUniqueMethodList(TraceData* traceData, MethodEntry **pMethods, int numMethods)
2059{
2060    int ii;
2061
2062    /* Sort the methods into alphabetical order of method names
2063     * to find the unique method names.
2064     */
2065    qsort(pMethods, numMethods, sizeof(MethodEntry*), compareMethodNames);
2066
2067    /* Count the number of unique method names, ignoring class and
2068     * signature.
2069     */
2070    const char *currentMethodName = "";
2071    traceData->numUniqueMethods = 0;
2072    for (ii = 0; ii < numMethods; ++ii) {
2073        if (pMethods[ii]->methodName == NULL)
2074            continue;
2075        if (strcmp(pMethods[ii]->methodName, currentMethodName) != 0) {
2076            traceData->numUniqueMethods += 1;
2077            currentMethodName = pMethods[ii]->methodName;
2078        }
2079    }
2080    if (traceData->numUniqueMethods == 0)
2081        return;
2082
2083    /* Allocate space for pointers to all of the unique methods */
2084    int nbytes = sizeof(UniqueMethodEntry) * traceData->numUniqueMethods;
2085    traceData->uniqueMethods = (UniqueMethodEntry *) malloc(nbytes);
2086
2087    /* Initialize the uniqueMethods array */
2088    memset(traceData->uniqueMethods, 0, nbytes);
2089    UniqueMethodEntry *pUnique = traceData->uniqueMethods;
2090    currentMethodName = NULL;
2091    int prevNumMethods = 0;
2092    for (ii = 0; ii < numMethods; ++ii) {
2093        if (pMethods[ii]->methodName == NULL)
2094            continue;
2095        if (currentMethodName == NULL)
2096            currentMethodName = pMethods[ii]->methodName;
2097        if (strcmp(pMethods[ii]->methodName, currentMethodName) != 0) {
2098            currentMethodName = pMethods[ii]->methodName;
2099            pUnique->numMethods = prevNumMethods;
2100            pUnique++;
2101            prevNumMethods = 0;
2102        }
2103        prevNumMethods += 1;
2104    }
2105    pUnique->numMethods = prevNumMethods;
2106
2107    /* Create the array of MethodEntry pointers for each unique method */
2108    pUnique = NULL;
2109    currentMethodName = "";
2110    int nextMethod = 0;
2111    for (ii = 0; ii < numMethods; ++ii) {
2112        if (pMethods[ii]->methodName == NULL)
2113            continue;
2114        if (strcmp(pMethods[ii]->methodName, currentMethodName) != 0) {
2115            currentMethodName = pMethods[ii]->methodName;
2116            if (pUnique == NULL)
2117                pUnique = traceData->uniqueMethods;
2118            else
2119                pUnique++;
2120            /* Allocate space for the methods array */
2121            int nbytes = sizeof(MethodEntry*) * pUnique->numMethods;
2122            pUnique->methods = (MethodEntry**) malloc(nbytes);
2123            nextMethod = 0;
2124        }
2125        pUnique->methods[nextMethod++] = pMethods[ii];
2126    }
2127}
2128
2129void printMethodProfiles(TraceData* traceData, uint64_t sumThreadTime)
2130{
2131    int ii, jj;
2132    MethodEntry* method;
2133    double total, sum, per, sum_per;
2134    char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
2135    char signatureBuf[HTML_BUFSIZE];
2136
2137    if (traceData->numUniqueMethods == 0)
2138        return;
2139
2140    total = sumThreadTime;
2141    if (gOptions.outputHtml) {
2142        printf("<a name=\"method\"></a>\n");
2143        printf("<hr>\n");
2144        outputNavigationBar();
2145    } else {
2146        printf("\n%s\n", profileSeparator);
2147    }
2148
2149    printf("\nExclusive elapsed time for each method, summed over all the classes\n");
2150    printf("that contain a method with the same name.\n\n");
2151    if (gOptions.outputHtml) {
2152        printf("<br><br>\n");
2153    }
2154
2155    /* For each unique method, sum the exclusive times in all of the methods
2156     * with the same name.  Also sum the number of method calls.  Also
2157     * sort the methods so the most expensive appear at the top.
2158     */
2159    UniqueMethodEntry *pUnique = traceData->uniqueMethods;
2160    for (ii = 0; ii < traceData->numUniqueMethods; ++ii, ++pUnique) {
2161        int numMethods = pUnique->numMethods;
2162        for (jj = 0; jj < numMethods; ++jj) {
2163            method = pUnique->methods[jj];
2164            pUnique->elapsedExclusive += method->elapsedExclusive;
2165            pUnique->numCalls[0] += method->numCalls[0];
2166            pUnique->numCalls[1] += method->numCalls[1];
2167        }
2168
2169        /* Sort the methods into decreasing order of exclusive time */
2170        qsort(pUnique->methods, numMethods, sizeof(MethodEntry*),
2171              compareElapsedExclusive);
2172    }
2173
2174    /* Allocate an array of pointers to the methods for more efficient
2175     * sorting.
2176     */
2177    UniqueMethodEntry **pUniqueMethods;
2178    int nbytes = sizeof(UniqueMethodEntry*) * traceData->numUniqueMethods;
2179    pUniqueMethods = (UniqueMethodEntry**) malloc(nbytes);
2180    for (ii = 0; ii < traceData->numUniqueMethods; ++ii)
2181        pUniqueMethods[ii] = &traceData->uniqueMethods[ii];
2182
2183    /* Sort the methods into decreasing order of exclusive time */
2184    qsort(pUniqueMethods, traceData->numUniqueMethods, sizeof(UniqueMethodEntry*),
2185          compareUniqueExclusive);
2186
2187    if (gOptions.outputHtml) {
2188        printf("<div class=\"header\"><span class=\"parent\">&nbsp;</span>&nbsp;&nbsp;&nbsp;");
2189        printf("Cycles %%/total Cumul.%% &nbsp;Calls+Recur&nbsp; Method</div>\n");
2190    } else {
2191        printf("   Cycles %%/total Cumul.%%  Calls+Recur  Method\n");
2192    }
2193
2194    sum = 0;
2195    for (ii = 0; ii < traceData->numUniqueMethods; ++ii) {
2196        char *className, *methodName, *signature;
2197
2198        /* Skip methods with zero cycles */
2199        pUnique = pUniqueMethods[ii];
2200        if (pUnique->elapsedExclusive == 0)
2201            break;
2202
2203        per = 100.0 * pUnique->elapsedExclusive / total;
2204        sum += pUnique->elapsedExclusive;
2205        sum_per = 100.0 * sum / total;
2206        methodName = (char*)(pUnique->methods[0]->methodName);
2207        if (gOptions.outputHtml) {
2208            char buf[80];
2209
2210            methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
2211            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);
2212            sprintf(buf, "%llu", pUnique->elapsedExclusive);
2213            printHtmlField(buf, 9);
2214            printf(" ");
2215            sprintf(buf, "%.1f", per);
2216            printHtmlField(buf, 7);
2217            printf(" ");
2218            sprintf(buf, "%.1f", sum_per);
2219            printHtmlField(buf, 7);
2220            printf(" ");
2221            sprintf(buf, "%d", pUnique->numCalls[0]);
2222            printHtmlField(buf, 6);
2223            printf("+");
2224            sprintf(buf, "%d", pUnique->numCalls[1]);
2225            printHtmlField(buf, -6);
2226            printf(" ");
2227            printf("%s", methodName);
2228            printf("</div>\n");
2229            printf("<div class=\"parent\" id=\"e%d\">\n", ii);
2230        } else {
2231            printf("---------------------------------------------\n");
2232            printf("%9llu %7.1f %7.1f %6d+%-6d %s\n",
2233                   pUnique->elapsedExclusive, per, sum_per,
2234                   pUnique->numCalls[0], pUnique->numCalls[1],
2235                   methodName);
2236        }
2237        int numMethods = pUnique->numMethods;
2238        double methodExclusive = pUnique->elapsedExclusive;
2239        double sumMethods = 0;
2240        for (jj = 0; jj < numMethods; ++jj) {
2241            method = pUnique->methods[jj];
2242            className = (char*)(method->className);
2243            signature = (char*)(method->signature);
2244            per = 100.0 * method->elapsedExclusive / methodExclusive;
2245            sumMethods += method->elapsedExclusive;
2246            sum_per = 100.0 * sumMethods / methodExclusive;
2247            if (gOptions.outputHtml) {
2248                char buf[80];
2249
2250                className = htmlEscape(className, classBuf, HTML_BUFSIZE);
2251                signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
2252                printf("<div class=\"leaf\"><span class=\"leaf\">&nbsp;</span>");
2253                sprintf(buf, "%llu", method->elapsedExclusive);
2254                printHtmlField(buf, 9);
2255                printf("&nbsp;");
2256                sprintf(buf, "%llu", method->elapsedInclusive);
2257                printHtmlField(buf, 9);
2258                printf("&nbsp;");
2259                sprintf(buf, "%.1f", per);
2260                printHtmlField(buf, 7);
2261                printf("&nbsp;");
2262                sprintf(buf, "%.1f", sum_per);
2263                printHtmlField(buf, 7);
2264                printf("&nbsp;");
2265                sprintf(buf, "%d", method->numCalls[0]);
2266                printHtmlField(buf, 6);
2267                printf("+");
2268                sprintf(buf, "%d", method->numCalls[1]);
2269                printHtmlField(buf, -6);
2270                printf("&nbsp;");
2271                printf("<a href=\"#m%d\">[%d]</a>&nbsp;%s.%s&nbsp;%s",
2272                       method->index, method->index,
2273                       className, methodName, signature);
2274                printf("</div>\n");
2275            } else {
2276                printf("%9llu %9llu %7.1f %7.1f %6d+%-6d [%d] %s.%s %s\n",
2277                       method->elapsedExclusive,
2278                       method->elapsedInclusive,
2279                       per, sum_per,
2280                       method->numCalls[0], method->numCalls[1],
2281                       method->index, className, methodName, signature);
2282            }
2283        }
2284        if (gOptions.outputHtml) {
2285            printf("</div>\n");
2286        }
2287    }
2288}
2289
2290/*
2291 * Read the key and data files and return the MethodEntries for those files
2292 */
2293DataKeys* parseDataKeys(TraceData* traceData, const char* traceFileName, uint64_t* threadTime)
2294{
2295    DataKeys* dataKeys = NULL;
2296    MethodEntry **pMethods = NULL;
2297    MethodEntry* method;
2298    FILE* dataFp = NULL;
2299    DataHeader dataHeader;
2300    int ii;
2301    uint64_t currentTime;
2302    MethodEntry* caller;
2303
2304    dataFp = fopen(traceFileName, "r");
2305    if (dataFp == NULL)
2306        goto bail;
2307
2308    if ((dataKeys = parseKeys(dataFp, 0)) == NULL)
2309        goto bail;
2310
2311    if (parseDataHeader(dataFp, &dataHeader) < 0)
2312        goto bail;
2313
2314#if 0
2315    FILE *dumpStream = fopen("debug", "w");
2316#endif
2317    while (1) {
2318        int threadId;
2319        unsigned int methodVal;
2320        int action;
2321        unsigned int methodId;
2322        CallStack *pStack;
2323        /*
2324         * Extract values from file.
2325         */
2326        if (readDataRecord(dataFp, &dataHeader, &threadId, &methodVal, &currentTime))
2327            break;
2328
2329        action = METHOD_ACTION(methodVal);
2330        methodId = METHOD_ID(methodVal);
2331
2332        /* Get the call stack for this thread */
2333        pStack = traceData->stacks[threadId];
2334
2335        /* If there is no call stack yet for this thread, then allocate one */
2336        if (pStack == NULL) {
2337            pStack = malloc(sizeof(CallStack));
2338            pStack->top = 0;
2339            pStack->lastEventTime = currentTime;
2340            pStack->threadStartTime = currentTime;
2341            traceData->stacks[threadId] = pStack;
2342        }
2343
2344        /* Lookup the current method */
2345        method = lookupMethod(dataKeys, methodId);
2346        if (method == NULL)
2347            method = &dataKeys->methods[UNKNOWN_INDEX];
2348
2349#if 0
2350        if (method->methodName) {
2351            fprintf(dumpStream, "%2d %-8llu %d %8llu r %d c %d %s.%s %s\n",
2352                    threadId, currentTime, action, pStack->threadStartTime,
2353                    method->recursiveEntries,
2354                    pStack->top, method->className, method->methodName,
2355                    method->signature);
2356        } else {
2357            fprintf(dumpStream, "%2d %-8llu %d %8llu r %d c %d %s\n",
2358                    threadId, currentTime, action, pStack->threadStartTime,
2359                    method->recursiveEntries,
2360                    pStack->top, method->className);
2361        }
2362#endif
2363
2364        if (action == METHOD_TRACE_ENTER) {
2365            /* This is a method entry */
2366            if (pStack->top >= MAX_STACK_DEPTH) {
2367                fprintf(stderr, "Stack overflow (exceeded %d frames)\n",
2368                        MAX_STACK_DEPTH);
2369                exit(1);
2370            }
2371
2372            /* Get the caller method */
2373            if (pStack->top >= 1)
2374                caller = pStack->calls[pStack->top - 1].method;
2375            else
2376                caller = &dataKeys->methods[TOPLEVEL_INDEX];
2377            countRecursiveEntries(pStack, pStack->top, caller);
2378            caller->elapsedExclusive += currentTime - pStack->lastEventTime;
2379#if 0
2380            if (caller->elapsedExclusive > 10000000)
2381                fprintf(dumpStream, "%llu current %llu last %llu diff %llu\n",
2382                        caller->elapsedExclusive, currentTime,
2383                        pStack->lastEventTime,
2384                        currentTime - pStack->lastEventTime);
2385#endif
2386            if (caller->recursiveEntries <= 1) {
2387                caller->topExclusive += currentTime - pStack->lastEventTime;
2388            }
2389
2390            /* Push the method on the stack for this thread */
2391            pStack->calls[pStack->top].method = method;
2392            pStack->calls[pStack->top++].entryTime = currentTime;
2393        } else {
2394            /* This is a method exit */
2395            uint64_t entryTime = 0;
2396
2397            /* Pop the method off the stack for this thread */
2398            if (pStack->top > 0) {
2399                pStack->top -= 1;
2400                entryTime = pStack->calls[pStack->top].entryTime;
2401                if (method != pStack->calls[pStack->top].method) {
2402                    if (method->methodName) {
2403                        fprintf(stderr,
2404                            "Exit from method %s.%s %s does not match stack:\n",
2405                            method->className, method->methodName,
2406                            method->signature);
2407                    } else {
2408                        fprintf(stderr,
2409                            "Exit from method %s does not match stack:\n",
2410                            method->className);
2411                    }
2412                    stackDump(pStack, pStack->top + 1);
2413                    exit(1);
2414                }
2415            }
2416
2417            /* Get the caller method */
2418            if (pStack->top >= 1)
2419                caller = pStack->calls[pStack->top - 1].method;
2420            else
2421                caller = &dataKeys->methods[TOPLEVEL_INDEX];
2422            countRecursiveEntries(pStack, pStack->top, caller);
2423            countRecursiveEntries(pStack, pStack->top, method);
2424            uint64_t elapsed = currentTime - entryTime;
2425            addInclusiveTime(caller, method, elapsed);
2426            method->elapsedExclusive += currentTime - pStack->lastEventTime;
2427            if (method->recursiveEntries == 0) {
2428                method->topExclusive += currentTime - pStack->lastEventTime;
2429            }
2430        }
2431        /* Remember the time of the last entry or exit event */
2432        pStack->lastEventTime = currentTime;
2433    }
2434
2435    /* If we have calls on the stack when the trace ends, then clean
2436     * up the stack and add time to the callers by pretending that we
2437     * are exiting from their methods now.
2438     */
2439    CallStack *pStack;
2440    int threadId;
2441    uint64_t sumThreadTime = 0;
2442    for (threadId = 0; threadId < MAX_THREADS; ++threadId) {
2443        pStack = traceData->stacks[threadId];
2444
2445        /* If this thread never existed, then continue with next thread */
2446        if (pStack == NULL)
2447            continue;
2448
2449        /* Also, add up the time taken by all of the threads */
2450        sumThreadTime += pStack->lastEventTime - pStack->threadStartTime;
2451
2452        for (ii = 0; ii < pStack->top; ++ii) {
2453            if (ii == 0)
2454                caller = &dataKeys->methods[TOPLEVEL_INDEX];
2455            else
2456                caller = pStack->calls[ii - 1].method;
2457            method = pStack->calls[ii].method;
2458            countRecursiveEntries(pStack, ii, caller);
2459            countRecursiveEntries(pStack, ii, method);
2460
2461            uint64_t entryTime = pStack->calls[ii].entryTime;
2462            uint64_t elapsed = pStack->lastEventTime - entryTime;
2463            addInclusiveTime(caller, method, elapsed);
2464        }
2465    }
2466    caller = &dataKeys->methods[TOPLEVEL_INDEX];
2467    caller->elapsedInclusive = sumThreadTime;
2468
2469#if 0
2470    fclose(dumpStream);
2471#endif
2472
2473    if (threadTime != NULL) {
2474        *threadTime = sumThreadTime;
2475    }
2476
2477bail:
2478    if (dataFp != NULL)
2479        fclose(dataFp);
2480
2481    return dataKeys;
2482}
2483
2484MethodEntry** parseMethodEntries(DataKeys* dataKeys)
2485{
2486    int ii;
2487    /* Create a new array of pointers to the methods and sort the pointers
2488     * instead of the actual MethodEntry structs.  We need to do this
2489     * because there are other lists that contain pointers to the
2490     * MethodEntry structs.
2491     */
2492    MethodEntry** pMethods = (MethodEntry**) malloc(sizeof(MethodEntry*) * dataKeys->numMethods);
2493    for (ii = 0; ii < dataKeys->numMethods; ++ii) {
2494        MethodEntry* entry = &dataKeys->methods[ii];
2495        pMethods[ii] = entry;
2496    }
2497
2498    return pMethods;
2499}
2500
2501/*
2502 * Produce a function profile from the following methods
2503 */
2504void profileTrace(TraceData* traceData, MethodEntry **pMethods, int numMethods, uint64_t sumThreadTime)
2505{
2506    /* Print the html header, if necessary */
2507    if (gOptions.outputHtml) {
2508        printf(htmlHeader, gOptions.sortableUrl);
2509        outputTableOfContents();
2510    }
2511
2512    printExclusiveProfile(pMethods, numMethods, sumThreadTime);
2513    printInclusiveProfile(pMethods, numMethods, sumThreadTime);
2514
2515    createClassList(traceData, pMethods, numMethods);
2516    printClassProfiles(traceData, sumThreadTime);
2517
2518    createUniqueMethodList(traceData, pMethods, numMethods);
2519    printMethodProfiles(traceData, sumThreadTime);
2520
2521    if (gOptions.outputHtml) {
2522        printf("%s", htmlFooter);
2523    }
2524}
2525
2526int compareMethodNamesForDiff(const void *a, const void *b)
2527{
2528    int result;
2529
2530    const MethodEntry *methodA = *(const MethodEntry**)a;
2531    const MethodEntry *methodB = *(const MethodEntry**)b;
2532    if (methodA->methodName == NULL || methodB->methodName == NULL) {
2533        return compareClassNames(a, b);
2534    }
2535    result = strcmp(methodA->methodName, methodB->methodName);
2536    if (result == 0) {
2537        result = strcmp(methodA->signature, methodB->signature);
2538        if (result == 0) {
2539           return strcmp(methodA->className, methodB->className);
2540        }
2541    }
2542    return result;
2543}
2544
2545int findMatch(MethodEntry** methods, int size, MethodEntry* matchThis)
2546{
2547    int i;
2548
2549    for (i = 0 ; i < size ; i++) {
2550        MethodEntry* method = methods[i];
2551
2552        if (method != NULL && !compareMethodNamesForDiff(&method, &matchThis)) {
2553//            printf("%s.%s == %s.%s<br>\n", matchThis->className, matchThis->methodName,
2554  //              method->className, method->methodName);
2555
2556            return i;
2557/*            if (!compareMethodNames(&method, &matchThis)) {
2558                return i;
2559            }
2560*/        }
2561    }
2562
2563    return -1;
2564}
2565
2566int compareDiffEntriesExculsive(const void *a, const void *b)
2567{
2568    int result;
2569
2570    const DiffEntry* entryA = (const DiffEntry*)a;
2571    const DiffEntry* entryB = (const DiffEntry*)b;
2572
2573    if (entryA->differenceExclusive < entryB->differenceExclusive) {
2574        return 1;
2575    } else if (entryA->differenceExclusive > entryB->differenceExclusive) {
2576        return -1;
2577    }
2578
2579    return 0;
2580}
2581
2582int compareDiffEntriesInculsive(const void *a, const void *b)
2583{
2584    int result;
2585
2586    const DiffEntry* entryA = (const DiffEntry*)a;
2587    const DiffEntry* entryB = (const DiffEntry*)b;
2588
2589    if (entryA->differenceInclusive < entryB->differenceInclusive) {
2590        return 1;
2591    } else if (entryA->differenceInclusive > entryB->differenceInclusive) {
2592        return -1;
2593    }
2594
2595    return 0;
2596}
2597
2598void printMissingMethod(MethodEntry* method)
2599{
2600    char classBuf[HTML_BUFSIZE];
2601    char methodBuf[HTML_BUFSIZE];
2602    char* className;
2603    char* methodName;
2604
2605    className = htmlEscape(method->className, classBuf, HTML_BUFSIZE);
2606    methodName = htmlEscape(method->methodName, methodBuf, HTML_BUFSIZE);
2607
2608    if (gOptions.outputHtml) printf("<tr><td>\n");
2609
2610    printf("%s.%s ", className, methodName);
2611    if (gOptions.outputHtml) printf("</td><td>");
2612
2613    printf("%lld ", method->elapsedExclusive);
2614    if (gOptions.outputHtml) printf("</td><td>");
2615
2616    printf("%lld ", method->elapsedInclusive);
2617    if (gOptions.outputHtml) printf("</td><td>");
2618
2619    printf("%d\n", method->numCalls[0]);
2620    if (gOptions.outputHtml) printf("</td><td>\n");
2621}
2622
2623
2624void createDiff(DataKeys* d1, uint64_t sum1, DataKeys* d2, uint64_t sum2)
2625{
2626    MethodEntry** methods1 = parseMethodEntries(d1);
2627    MethodEntry** methods2 = parseMethodEntries(d2);
2628
2629    // sort and assign the indicies
2630    int i;
2631    qsort(methods1, d1->numMethods, sizeof(MethodEntry*), compareElapsedInclusive);
2632    for (i = 0; i < d1->numMethods; ++i) {
2633        methods1[i]->index = i;
2634    }
2635
2636    qsort(methods2, d2->numMethods, sizeof(MethodEntry*), compareElapsedInclusive);
2637    for (i = 0; i < d2->numMethods; ++i) {
2638        methods2[i]->index = i;
2639    }
2640
2641    int max = (d1->numMethods < d2->numMethods) ? d2->numMethods : d1->numMethods;
2642    max++;
2643    DiffEntry* diffs = (DiffEntry*)malloc(max * sizeof(DiffEntry));
2644    memset(diffs, 0, max * sizeof(DiffEntry));
2645    DiffEntry* ptr = diffs;
2646
2647//    printf("<br>d1->numMethods: %d d1->numMethods: %d<br>\n", d1->numMethods, d2->numMethods);
2648
2649    int matches = 0;
2650
2651    for (i = 0 ; i < d1->numMethods ; i++) {
2652        int match = findMatch(methods2, d2->numMethods, methods1[i]);
2653        if (match >= 0) {
2654            ptr->method1 = methods1[i];
2655            ptr->method2 = methods2[match];
2656
2657            uint64_t e1 = ptr->method1->elapsedExclusive;
2658            uint64_t e2 = ptr->method2->elapsedExclusive;
2659            if (e1 > 0) {
2660                ptr->differenceExclusive = e2 - e1;
2661                ptr->differenceExclusivePercentage = ((double)e2 / (double)e1) * 100.0;
2662            }
2663
2664            uint64_t i1 = ptr->method1->elapsedInclusive;
2665            uint64_t i2 = ptr->method2->elapsedInclusive;
2666            if (i1 > 0) {
2667                ptr->differenceInclusive = i2 - i1;
2668                ptr->differenceInclusivePercentage = ((double)i2 / (double)i1) * 100.0;
2669            }
2670
2671            // clear these out so we don't find them again and we know which ones
2672            // we have left over
2673            methods1[i] = NULL;
2674            methods2[match] = NULL;
2675            ptr++;
2676
2677            matches++;
2678        }
2679    }
2680    ptr->method1 = NULL;
2681    ptr->method2 = NULL;
2682
2683    qsort(diffs, matches, sizeof(DiffEntry), compareDiffEntriesExculsive);
2684    ptr = diffs;
2685
2686    if (gOptions.outputHtml) {
2687        printf(htmlHeader, gOptions.sortableUrl);
2688        printf("<h3>Table of Contents</h3>\n");
2689        printf("<ul>\n");
2690        printf("<li><a href='#exclusive'>Exclusive</a>\n");
2691        printf("<li><a href='#inclusive'>Inclusive</a>\n");
2692        printf("</ul>\n");
2693        printf("Run 1: %s<br>\n", gOptions.diffFileName);
2694        printf("Run 2: %s<br>\n", gOptions.traceFileName);
2695        printf("<a name=\"exclusive\"></a><h3 id=\"exclusive\">Exclusive</h3>\n");
2696        printf(tableHeader, "exclusive_table");
2697    }
2698
2699    char classBuf[HTML_BUFSIZE];
2700    char methodBuf[HTML_BUFSIZE];
2701    char* className;
2702    char* methodName;
2703
2704    while (ptr->method1 != NULL && ptr->method2 != NULL) {
2705        if (gOptions.outputHtml) printf("<tr><td>\n");
2706
2707        className = htmlEscape(ptr->method1->className, classBuf, HTML_BUFSIZE);
2708        methodName = htmlEscape(ptr->method1->methodName, methodBuf, HTML_BUFSIZE);
2709
2710        printf("%s.%s ", className, methodName);
2711        if (gOptions.outputHtml) printf("</td><td>");
2712
2713        printf("%lld ", ptr->method1->elapsedExclusive);
2714        if (gOptions.outputHtml) printf("</td><td>");
2715
2716        printf("%llu ", ptr->method2->elapsedExclusive);
2717        if (gOptions.outputHtml) printf("</td><td>");
2718
2719        printf("%lld ", ptr->differenceExclusive);
2720        if (gOptions.outputHtml) printf("</td><td>");
2721
2722        printf("%.2f\n", ptr->differenceExclusivePercentage);
2723        if (gOptions.outputHtml) printf("</td><td>\n");
2724
2725        printf("%d\n", ptr->method1->numCalls[0]);
2726        if (gOptions.outputHtml) printf("</td><td>\n");
2727
2728        printf("%d\n", ptr->method2->numCalls[0]);
2729        if (gOptions.outputHtml) printf("</td></tr>\n");
2730
2731        ptr++;
2732    }
2733
2734    if (gOptions.outputHtml) printf("</table>\n");
2735
2736    if (gOptions.outputHtml) {
2737        printf(htmlHeader, gOptions.sortableUrl);
2738        printf("Run 1: %s<br>\n", gOptions.diffFileName);
2739        printf("Run 2: %s<br>\n", gOptions.traceFileName);
2740        printf("<a name=\"inclusive\"></a><h3 id=\"inculisve\">Inclusive</h3>\n");
2741        printf(tableHeader, "inclusive_table");
2742    }
2743
2744    qsort(diffs, matches, sizeof(DiffEntry), compareDiffEntriesInculsive);
2745    ptr = diffs;
2746
2747    while (ptr->method1 != NULL && ptr->method2 != NULL) {
2748        if (gOptions.outputHtml) printf("<tr><td>\n");
2749
2750        className = htmlEscape(ptr->method1->className, classBuf, HTML_BUFSIZE);
2751        methodName = htmlEscape(ptr->method1->methodName, methodBuf, HTML_BUFSIZE);
2752
2753        printf("%s.%s ", className, methodName);
2754        if (gOptions.outputHtml) printf("</td><td>");
2755
2756        printf("%lld ", ptr->method1->elapsedInclusive);
2757        if (gOptions.outputHtml) printf("</td><td>");
2758
2759        printf("%llu ", ptr->method2->elapsedInclusive);
2760        if (gOptions.outputHtml) printf("</td><td>");
2761
2762        printf("%lld ", ptr->differenceInclusive);
2763        if (gOptions.outputHtml) printf("</td><td>");
2764
2765        printf("%.2f\n", ptr->differenceInclusivePercentage);
2766        if (gOptions.outputHtml) printf("</td><td>\n");
2767
2768        printf("%d\n", ptr->method1->numCalls[0]);
2769        if (gOptions.outputHtml) printf("</td><td>\n");
2770
2771        printf("%d\n", ptr->method2->numCalls[0]);
2772        if (gOptions.outputHtml) printf("</td></tr>\n");
2773
2774        ptr++;
2775    }
2776
2777    if (gOptions.outputHtml) {
2778        printf("</table>\n");
2779        printf("<h3>Run 1 methods not found in Run 2</h3>");
2780        printf(tableHeaderMissing, "?");
2781    }
2782
2783    for (i = 0; i < d1->numMethods; ++i) {
2784        if (methods1[i] != NULL) {
2785           printMissingMethod(methods1[i]);
2786        }
2787    }
2788
2789    if (gOptions.outputHtml) {
2790        printf("</table>\n");
2791        printf("<h3>Run 2 methods not found in Run 1</h3>");
2792        printf(tableHeaderMissing, "?");
2793    }
2794
2795    for (i = 0; i < d2->numMethods; ++i) {
2796        if (methods2[i] != NULL) {
2797            printMissingMethod(methods2[i]);
2798        }
2799    }
2800
2801    if (gOptions.outputHtml) printf("</body></html\n");
2802}
2803
2804int usage(const char *program)
2805{
2806    fprintf(stderr, "Copyright (C) 2006 The Android Open Source Project\n\n");
2807    fprintf(stderr, "usage: %s [-ho] [-s sortable] [-d trace-file-name] [-g outfile] trace-file-name\n", program);
2808    fprintf(stderr, "  -d trace-file-name  - Diff with this trace\n");
2809    fprintf(stderr, "  -g outfile          - Write graph to 'outfile'\n");
2810    fprintf(stderr, "  -k                  - When writing a graph, keep the intermediate DOT file\n");
2811    fprintf(stderr, "  -h                  - Turn on HTML output\n");
2812    fprintf(stderr, "  -o                  - Dump the dmtrace file instead of profiling\n");
2813    fprintf(stderr, "  -s                  - URL base to where the sortable javascript file\n");
2814    fprintf(stderr, "  -t threshold        - Threshold percentage for including nodes in the graph\n");
2815    return 2;
2816}
2817
2818// Returns true if there was an error
2819int parseOptions(int argc, char **argv)
2820{
2821    while (1) {
2822        int opt = getopt(argc, argv, "d:hg:kos:t:");
2823        if (opt == -1)
2824            break;
2825        switch (opt) {
2826            case 'd':
2827                gOptions.diffFileName = optarg;
2828                break;
2829            case 'g':
2830                gOptions.graphFileName = optarg;
2831                break;
2832            case 'k':
2833                gOptions.keepDotFile = 1;
2834                break;
2835            case 'h':
2836                gOptions.outputHtml = 1;
2837                break;
2838            case 'o':
2839                gOptions.dump = 1;
2840                break;
2841            case 's':
2842                gOptions.sortableUrl = optarg;
2843                break;
2844            case 't':
2845                gOptions.threshold = atoi(optarg);
2846                break;
2847            default:
2848                return 1;
2849        }
2850    }
2851    return 0;
2852}
2853
2854/*
2855 * Parse args.
2856 */
2857int main(int argc, char** argv)
2858{
2859    gOptions.threshold = -1;
2860
2861    // Parse the options
2862    if (parseOptions(argc, argv) || argc - optind != 1)
2863        return usage(argv[0]);
2864
2865    gOptions.traceFileName = argv[optind];
2866
2867    if (gOptions.threshold < 0 || 100 <= gOptions.threshold) {
2868        gOptions.threshold = 20;
2869    }
2870
2871    if (gOptions.dump) {
2872        dumpTrace();
2873        return 0;
2874    }
2875
2876    uint64_t sumThreadTime = 0;
2877
2878    TraceData data1;
2879    DataKeys* dataKeys = parseDataKeys(&data1, gOptions.traceFileName,
2880                                       &sumThreadTime);
2881    if (dataKeys == NULL) {
2882        fprintf(stderr, "Cannot read trace.\n");
2883        exit(1);
2884    }
2885
2886    if (gOptions.diffFileName != NULL) {
2887        uint64_t sum2;
2888        TraceData data2;
2889        DataKeys* d2 = parseDataKeys(&data2, gOptions.diffFileName, &sum2);
2890
2891        createDiff(d2, sum2, dataKeys, sumThreadTime);
2892
2893        freeDataKeys(d2);
2894    } else {
2895        MethodEntry** methods = parseMethodEntries(dataKeys);
2896        profileTrace(&data1, methods, dataKeys->numMethods, sumThreadTime);
2897        if (gOptions.graphFileName != NULL) {
2898            createInclusiveProfileGraphNew(dataKeys);
2899        }
2900        free(methods);
2901    }
2902
2903    freeDataKeys(dataKeys);
2904
2905    return 0;
2906}
2907