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