Home | History | Annotate | Download | only in dmtracedump 
      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  */
     40 int 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 
     51 char *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 
     91 char *htmlFooter = "\n</body>\n</html>\n";
     92 char *profileSeparator =
     93     "======================================================================";
     94 
     95 const 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 
    106 const 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  */
    119 typedef 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  */
    130 typedef struct ThreadEntry {
    131     int         threadId;
    132     const char* threadName;
    133 } ThreadEntry;
    134 
    135 struct MethodEntry;
    136 typedef struct TimedMethod {
    137     struct TimedMethod *next;
    138     uint64_t elapsedInclusive;
    139     int numCalls;
    140     struct MethodEntry *method;
    141 } TimedMethod;
    142 
    143 typedef 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 
    151 typedef 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  */
    161 typedef 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  */
    183 typedef 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 
    195 typedef struct StackEntry {
    196     MethodEntry *method;
    197     uint64_t    entryTime;
    198 } StackEntry;
    199 
    200 typedef struct CallStack {
    201     int         top;
    202     StackEntry  calls[MAX_STACK_DEPTH];
    203     uint64_t    lastEventTime;
    204     uint64_t    threadStartTime;
    205 } CallStack;
    206 
    207 typedef 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
    217 typedef 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 
    228 typedef 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 
    237 static 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  */
    247 char *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  */
    300 void 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  */
    329 int 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  */
    367 int 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  */
    406 int 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  */
    447 int 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  */
    469 int 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  */
    506 int 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  */
    534 int 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  */
    567 void 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  */
    586 int 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  */
    606 int 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  */
    628 int 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  */
    654 long 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  */
    709 long 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  */
    763 long 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  */
    875 long 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  */
    898 static int compareThreads(const void* thread1, const void* thread2)
    899 {
    900     return ((const ThreadEntry*) thread1)->threadId -
    901             ((const ThreadEntry*) thread2)->threadId;
    902 }
    903 
    904 void 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  */
    913 static 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 
    926 void 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  */
    935 DataKeys* 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 
   1018 fail:
   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  */
   1031 unsigned int read2LE(FILE* fp)
   1032 {
   1033     unsigned int val;
   1034 
   1035     val = getc(fp);
   1036     val |= getc(fp) << 8;
   1037     return val;
   1038 }
   1039 unsigned 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 }
   1049 unsigned 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  */
   1069 int 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  */
   1102 MethodEntry* 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  */
   1131 int 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  */
   1168 void 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 
   1271 bail:
   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  */
   1283 void 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  */
   1369 TimedMethod *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() */
   1397 static 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  */
   1402 void 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 
   1481 void 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 
   1492 void 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 
   1508 void 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 
   1520 void 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 
   1530 void 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 */
   1615 int 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 
   1623 void 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 
   1643 void 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 
   1660 void 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 
   1691 void 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 
   1790 void 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  */
   1870 void 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 
   1893 void 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 
   2058 void 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 
   2129 void 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  */
   2293 DataKeys* 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 
   2477 bail:
   2478     if (dataFp != NULL)
   2479         fclose(dataFp);
   2480 
   2481     return dataKeys;
   2482 }
   2483 
   2484 MethodEntry** 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  */
   2504 void 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 
   2526 int 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 
   2545 int 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 
   2566 int 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 
   2582 int 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 
   2598 void 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 
   2624 void 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 
   2804 int 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
   2819 int 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  */
   2857 int 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 \"%s\".\n", gOptions.traceFileName);
   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         if (d2 == NULL) {
   2891             fprintf(stderr, "Cannot read \"%s\".\n", gOptions.diffFileName);
   2892             exit(1);
   2893         }
   2894 
   2895         createDiff(d2, sum2, dataKeys, sumThreadTime);
   2896 
   2897         freeDataKeys(d2);
   2898     } else {
   2899         MethodEntry** methods = parseMethodEntries(dataKeys);
   2900         profileTrace(&data1, methods, dataKeys->numMethods, sumThreadTime);
   2901         if (gOptions.graphFileName != NULL) {
   2902             createInclusiveProfileGraphNew(dataKeys);
   2903         }
   2904         free(methods);
   2905     }
   2906 
   2907     freeDataKeys(dataKeys);
   2908 
   2909     return 0;
   2910 }
   2911