auto import from //depot/cupcake/@135843
diff --git a/tools/Android.mk b/tools/Android.mk
new file mode 100644
index 0000000..6571161
--- /dev/null
+++ b/tools/Android.mk
@@ -0,0 +1 @@
+include $(all-subdir-makefiles)
diff --git a/tools/deadcode.py b/tools/deadcode.py
new file mode 100755
index 0000000..eb71b7c
--- /dev/null
+++ b/tools/deadcode.py
@@ -0,0 +1,128 @@
+#!/usr/bin/env python
+
+import os
+import re
+import sys
+
+def SplitSections(buffer):
+ """Spin through the input buffer looking for section header lines.
+ When found, the name of the section is extracted. The entire contents
+ of that section is added to a result hashmap with the section name
+ as the key"""
+
+ # Match lines like
+ # |section_name:
+ # capturing section_name
+ headerPattern = re.compile(r'^\s+\|([a-z _]+)\:$', re.MULTILINE)
+
+ sections = {}
+ start = 0
+ anchor = -1
+ sectionName = ''
+
+ while True:
+ # Look for a section header
+ result = headerPattern.search(buffer, start)
+
+ # If there are no more, add a section from the last header to EOF
+ if result is None:
+ if anchor is not -1:
+ sections[sectionName] = buffer[anchor]
+ return sections
+
+ # Add the lines from the last header, to this one to the sections
+ # map indexed by the section name
+ if anchor is not -1:
+ sections[sectionName] = buffer[anchor:result.start()]
+
+ sectionName = result.group(1)
+ start = result.end()
+ anchor = start
+
+ return sections
+
+def FindMethods(section):
+ """Spin through the 'method code index' section and extract all
+ method signatures. When found, they are added to a result list."""
+
+ # Match lines like:
+ # |[abcd] com/example/app/Class.method:(args)return
+ # capturing the method signature
+ methodPattern = re.compile(r'^\s+\|\[\w{4}\] (.*)$', re.MULTILINE)
+
+ start = 0
+ methods = []
+
+ while True:
+ # Look for a method name
+ result = methodPattern.search(section, start)
+
+ if result is None:
+ return methods
+
+ # Add the captured signature to the method list
+ methods.append(result.group(1))
+ start = result.end()
+
+def CallsMethod(codes, method):
+ """Spin through all the input method signatures. For each one, return
+ whether or not there is method invokation line in the codes section that
+ lists the method as the target."""
+
+ start = 0
+
+ while True:
+ # Find the next reference to the method signature
+ match = codes.find(method, start)
+
+ if match is -1:
+ break;
+
+ # Find the beginning of the line the method reference is on
+ startOfLine = codes.rfind("\n", 0, match) + 1
+
+ # If the word 'invoke' comes between the beginning of the line
+ # and the method reference, then it is a call to that method rather
+ # than the beginning of the code section for that method.
+ if codes.find("invoke", startOfLine, match) is not -1:
+ return True
+
+ start = match + len(method)
+
+ return False
+
+
+
+def main():
+ if len(sys.argv) is not 2 or not sys.argv[1].endswith(".jar"):
+ print "Usage:", sys.argv[0], "<filename.jar>"
+ sys.exit()
+
+ command = 'dx --dex --dump-width=1000 --dump-to=-"" "%s"' % sys.argv[1]
+
+ pipe = os.popen(command)
+
+ # Read the whole dump file into memory
+ data = pipe.read()
+ sections = SplitSections(data)
+
+ pipe.close()
+ del(data)
+
+ methods = FindMethods(sections['method code index'])
+ codes = sections['codes']
+ del(sections)
+
+ print "Dead Methods:"
+ count = 0
+
+ for method in methods:
+ if not CallsMethod(codes, method):
+ print "\t", method
+ count += 1
+
+ if count is 0:
+ print "\tNone"
+
+if __name__ == '__main__':
+ main()
diff --git a/tools/dmtracedump/Android.mk b/tools/dmtracedump/Android.mk
new file mode 100644
index 0000000..ef9a9c2
--- /dev/null
+++ b/tools/dmtracedump/Android.mk
@@ -0,0 +1,24 @@
+#
+# Copyright 2006 The Android Open Source Project
+#
+# Java method trace dump tool
+#
+
+LOCAL_PATH:= $(call my-dir)
+
+
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := TraceDump.c
+LOCAL_CFLAGS += -O0 -g
+LOCAL_C_INCLUDES += dalvik/vm
+LOCAL_MODULE := dmtracedump
+include $(BUILD_HOST_EXECUTABLE)
+
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := CreateTestTrace.c
+LOCAL_CFLAGS += -O0 -g
+LOCAL_C_INCLUDES += dalvik/vm
+LOCAL_MODULE := create_test_dmtrace
+include $(BUILD_HOST_EXECUTABLE)
+
+
diff --git a/tools/dmtracedump/CreateTestTrace.c b/tools/dmtracedump/CreateTestTrace.c
new file mode 100644
index 0000000..256f21a
--- /dev/null
+++ b/tools/dmtracedump/CreateTestTrace.c
@@ -0,0 +1,474 @@
+/* //device/tools/dmtracedump/CreateTrace.c
+**
+** Copyright 2006, The Android Open Source Project
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+/*
+ * Create a test file in the format required by dmtrace.
+ */
+#define NOT_VM
+#include "Profile.h" // from VM header
+
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+#include <assert.h>
+#include <unistd.h>
+#include <sys/time.h>
+#include <time.h>
+#include <ctype.h>
+
+/*
+ * Values from the header of the data file.
+ */
+typedef struct DataHeader {
+ unsigned int magic;
+ short version;
+ short offsetToData;
+ long long startWhen;
+} DataHeader;
+
+#define VERSION 2
+int versionNumber = VERSION;
+
+DataHeader header = { 0x574f4c53, VERSION, sizeof(DataHeader), 0LL };
+
+char *versionHeader = "*version\n";
+char *clockDef = "clock=thread-cpu\n";
+
+char *keyThreads =
+"*threads\n"
+"1 main\n"
+"2 foo\n"
+"3 bar\n"
+"4 blah\n";
+
+char *keyEnd = "*end\n";
+
+typedef struct dataRecord {
+ unsigned int time;
+ int threadId;
+ unsigned int action; /* 0=entry, 1=exit, 2=exception exit */
+ char *fullName;
+ char *className;
+ char *methodName;
+ char *signature;
+ unsigned int methodId;
+} dataRecord;
+
+dataRecord *records;
+
+#define BUF_SIZE 1024
+char buf[BUF_SIZE];
+
+typedef struct stack {
+ dataRecord **frames;
+ int nextFrame;
+ int indentLevel;
+} stack;
+
+/* Mac OS doesn't have strndup(), so implement it here.
+ */
+char *strndup(const char *src, size_t len)
+{
+ char *dest = (char *) malloc(len + 1);
+ strncpy(dest, src, len);
+ dest[len] = 0;
+ return dest;
+}
+
+/*
+ * Parse the input file. It looks something like this:
+ * # This is a comment line
+ * 4 1 A
+ * 6 1 B
+ * 8 1 B
+ * 10 1 A
+ *
+ * where the first column is the time, the second column is the thread id,
+ * and the third column is the method (actually just the class name). The
+ * number of spaces between the 2nd and 3rd columns is the indentation and
+ * determines the call stack. Each called method must be indented by one
+ * more space. In the example above, A is called at time 4, A calls B at
+ * time 6, B returns at time 8, and A returns at time 10. Thread 1 is the
+ * only thread that is running.
+ *
+ * An alternative file format leaves out the first two columns:
+ * A
+ * B
+ * B
+ * A
+ *
+ * In this file format, the thread id is always 1, and the time starts at
+ * 2 and increments by 2 for each line.
+ */
+void parseInputFile(const char *inputFileName)
+{
+ unsigned int time = 0, threadId;
+ int len;
+ int linenum = 0;
+ int nextRecord = 0;
+ int indentLevel = 0;
+ stack *callStack;
+ int nextFrame = 0;
+
+ FILE *inputFp = fopen(inputFileName, "r");
+ if (inputFp == NULL) {
+ perror(inputFileName);
+ exit(1);
+ }
+
+ /* Count the number of lines in the buffer */
+ int numLines = 0;
+ int maxThreadId = 1;
+ while (fgets(buf, BUF_SIZE, inputFp)) {
+ char *cp = buf;
+ if (*cp == '#')
+ continue;
+ numLines += 1;
+ if (isdigit(*cp)) {
+ int time = strtoul(cp, &cp, 0);
+ while (isspace(*cp))
+ cp += 1;
+ int threadId = strtoul(cp, &cp, 0);
+ if (maxThreadId < threadId)
+ maxThreadId = threadId;
+ }
+ }
+ int numThreads = maxThreadId + 1;
+
+ /* Add space for a sentinel record at the end */
+ numLines += 1;
+ records = (dataRecord *) malloc(sizeof(dataRecord) * numLines);
+ callStack = (stack *) malloc(sizeof(stack) * numThreads);
+ int ii;
+ for (ii = 0; ii < numThreads; ++ii) {
+ callStack[ii].frames = NULL;
+ callStack[ii].nextFrame = 0;
+ }
+
+ rewind(inputFp);
+ while (fgets(buf, BUF_SIZE, inputFp)) {
+ int indent;
+ int action;
+ char *save_cp;
+
+ linenum += 1;
+ char *cp = buf;
+ /* Skip lines that start with '#' */
+ if (*cp == '#')
+ continue;
+ if (!isdigit(*cp)) {
+ /* If the line does not begin with a digit, then fill in
+ * default values for the time and threadId.
+ */
+ time += 2;
+ threadId = 1;
+ } else {
+ time = strtoul(cp, &cp, 0);
+ while (isspace(*cp))
+ cp += 1;
+ threadId = strtoul(cp, &cp, 0);
+ cp += 1;
+ }
+
+ // Allocate space for the thread stack, if necessary
+ if (callStack[threadId].frames == NULL) {
+ dataRecord **stk;
+ stk = (dataRecord **) malloc(sizeof(dataRecord *) * numLines);
+ callStack[threadId].frames = stk;
+ }
+ nextFrame = callStack[threadId].nextFrame;
+ indentLevel = callStack[threadId].indentLevel;
+
+ save_cp = cp;
+ while (isspace(*cp)) {
+ cp += 1;
+ }
+ indent = cp - save_cp + 1;
+ records[nextRecord].time = time;
+ records[nextRecord].threadId = threadId;
+
+ save_cp = cp;
+ while (*cp != '\n')
+ cp += 1;
+
+ /* Remove trailing spaces */
+ cp -= 1;
+ while (isspace(*cp))
+ cp -= 1;
+ cp += 1;
+ len = cp - save_cp;
+ records[nextRecord].fullName = strndup(save_cp, len);
+
+ /* Parse the name to support "class.method signature" */
+ records[nextRecord].className = NULL;
+ records[nextRecord].methodName = NULL;
+ records[nextRecord].signature = NULL;
+ cp = strchr(save_cp, '.');
+ if (cp) {
+ len = cp - save_cp;
+ if (len > 0)
+ records[nextRecord].className = strndup(save_cp, len);
+ save_cp = cp + 1;
+ cp = strchr(save_cp, ' ');
+ if (cp == NULL)
+ cp = strchr(save_cp, '\n');
+ if (cp && cp > save_cp) {
+ len = cp - save_cp;
+ records[nextRecord].methodName = strndup(save_cp, len);
+ save_cp = cp + 1;
+ cp = strchr(save_cp, ' ');
+ if (cp == NULL)
+ cp = strchr(save_cp, '\n');
+ if (cp && cp > save_cp) {
+ len = cp - save_cp;
+ records[nextRecord].signature = strndup(save_cp, len);
+ }
+ }
+ }
+
+ action = 0;
+ if (indent == indentLevel + 1) {
+ callStack[threadId].frames[nextFrame++] = &records[nextRecord];
+ } else if (indent == indentLevel) {
+ char *name = callStack[threadId].frames[nextFrame - 1]->fullName;
+ if (strcmp(name, records[nextRecord].fullName) == 0) {
+ nextFrame -= 1;
+ action = 1;
+ } else {
+ if (nextFrame == indentLevel) {
+ fprintf(stderr, "Error: line %d: %s", linenum, buf);
+ fprintf(stderr, " expected exit from %s\n",
+ callStack[threadId].frames[nextFrame - 1]->fullName);
+ exit(1);
+ } else {
+ callStack[threadId].frames[nextFrame++] = &records[nextRecord];
+ }
+ }
+ } else if (indent == indentLevel - 1) {
+ action = 1;
+ // Allow popping frames past the bottom of the stack.
+ if (nextFrame > 0) {
+ char *name = callStack[threadId].frames[nextFrame - 1]->fullName;
+ if (strcmp(name, records[nextRecord].fullName) == 0) {
+ nextFrame -= 1;
+ } else {
+ fprintf(stderr, "Error: line %d: %s", linenum, buf);
+ fprintf(stderr, " expected exit from %s\n",
+ callStack[threadId].frames[nextFrame - 1]->fullName);
+ exit(1);
+ }
+ }
+ } else {
+ if (nextRecord != 0) {
+ fprintf(stderr, "Error: line %d: %s", linenum, buf);
+ fprintf(stderr, " expected indentation %d +/- 1, found %d\n",
+ indentLevel, indent);
+ exit(1);
+ }
+
+ // This is the first line of data, so we allow a larger
+ // initial indent. This allows us to test popping off more
+ // frames than we entered.
+ callStack[threadId].frames[nextFrame++] = &records[nextRecord];
+ indentLevel = indent;
+ }
+ if (action == 0)
+ indentLevel += 1;
+ else
+ indentLevel -= 1;
+ records[nextRecord].action = action;
+ callStack[threadId].nextFrame = nextFrame;
+ callStack[threadId].indentLevel = indentLevel;
+
+ nextRecord += 1;
+ }
+
+ /* Mark the last record with a sentinel */
+ memset(&records[nextRecord], 0, sizeof(dataRecord));
+}
+
+
+/*
+ * Write values to the binary data file.
+ */
+void write2LE(FILE* fp, unsigned short val)
+{
+ putc(val & 0xff, fp);
+ putc(val >> 8, fp);
+}
+
+void write4LE(FILE* fp, unsigned int val)
+{
+ putc(val & 0xff, fp);
+ putc((val >> 8) & 0xff, fp);
+ putc((val >> 16) & 0xff, fp);
+ putc((val >> 24) & 0xff, fp);
+}
+
+void write8LE(FILE* fp, unsigned long long val)
+{
+ putc(val & 0xff, fp);
+ putc((val >> 8) & 0xff, fp);
+ putc((val >> 16) & 0xff, fp);
+ putc((val >> 24) & 0xff, fp);
+ putc((val >> 32) & 0xff, fp);
+ putc((val >> 40) & 0xff, fp);
+ putc((val >> 48) & 0xff, fp);
+ putc((val >> 56) & 0xff, fp);
+}
+
+void writeDataRecord(FILE *dataFp, int threadId, unsigned int methodVal,
+ unsigned int elapsedTime)
+{
+ if (versionNumber == 1)
+ putc(threadId, dataFp);
+ else
+ write2LE(dataFp, threadId);
+ write4LE(dataFp, methodVal);
+ write4LE(dataFp, elapsedTime);
+}
+
+void writeDataHeader(FILE *dataFp)
+{
+ struct timeval tv;
+ struct timezone tz;
+
+ gettimeofday(&tv, &tz);
+ unsigned long long startTime = tv.tv_sec;
+ startTime = (startTime << 32) | tv.tv_usec;
+ header.version = versionNumber;
+ write4LE(dataFp, header.magic);
+ write2LE(dataFp, header.version);
+ write2LE(dataFp, header.offsetToData);
+ write8LE(dataFp, startTime);
+}
+
+void writeKeyMethods(FILE *keyFp)
+{
+ dataRecord *pRecord, *pNext;
+ char *methodStr = "*methods\n";
+ fwrite(methodStr, strlen(methodStr), 1, keyFp);
+
+ /* Assign method ids in multiples of 4 */
+ unsigned int methodId = 0;
+ for (pRecord = records; pRecord->fullName; ++pRecord) {
+ if (pRecord->methodId)
+ continue;
+ unsigned int id = ++methodId << 2;
+ pRecord->methodId = id;
+
+ /* Assign this id to all the other records that have the
+ * same name.
+ */
+ for (pNext = pRecord + 1; pNext->fullName; ++pNext) {
+ if (pNext->methodId)
+ continue;
+ if (strcmp(pRecord->fullName, pNext->fullName) == 0)
+ pNext->methodId = id;
+ }
+ if (pRecord->className == NULL || pRecord->methodName == NULL) {
+ fprintf(keyFp, "0x%x %s m ()\n",
+ pRecord->methodId, pRecord->fullName);
+ } else if (pRecord->signature == NULL) {
+ fprintf(keyFp, "0x%x %s %s ()\n",
+ pRecord->methodId, pRecord->className,
+ pRecord->methodName);
+ } else {
+ fprintf(keyFp, "0x%x %s %s %s\n",
+ pRecord->methodId, pRecord->className,
+ pRecord->methodName, pRecord->signature);
+ }
+ }
+}
+
+void writeKeys(FILE *keyFp)
+{
+ fprintf(keyFp, "%s%d\n%s", versionHeader, versionNumber, clockDef);
+ fwrite(keyThreads, strlen(keyThreads), 1, keyFp);
+ writeKeyMethods(keyFp);
+ fwrite(keyEnd, strlen(keyEnd), 1, keyFp);
+}
+
+void writeDataRecords(FILE *dataFp)
+{
+ dataRecord *pRecord;
+
+ for (pRecord = records; pRecord->fullName; ++pRecord) {
+ unsigned int val = METHOD_COMBINE(pRecord->methodId, pRecord->action);
+ writeDataRecord(dataFp, pRecord->threadId, val, pRecord->time);
+ }
+}
+
+void writeTrace(const char* traceFileName)
+{
+ FILE *fp = fopen(traceFileName, "w");
+ if (fp == NULL) {
+ perror(traceFileName);
+ exit(1);
+ }
+ writeKeys(fp);
+ writeDataHeader(fp);
+ writeDataRecords(fp);
+ fclose(fp);
+}
+
+int parseOptions(int argc, char **argv)
+{
+ int err = 0;
+ while (1) {
+ int opt = getopt(argc, argv, "v:");
+ if (opt == -1)
+ break;
+ switch (opt) {
+ case 'v':
+ versionNumber = strtoul(optarg, NULL, 0);
+ if (versionNumber != 1 && versionNumber != 2) {
+ fprintf(stderr, "Error: version number (%d) must be 1 or 2\n",
+ versionNumber);
+ err = 1;
+ }
+ break;
+ default:
+ err = 1;
+ break;
+ }
+ }
+ return err;
+}
+
+int main(int argc, char** argv)
+{
+ char *inputFile;
+ char *traceFileName = NULL;
+ int len;
+
+ if (parseOptions(argc, argv) || argc - optind != 2) {
+ fprintf(stderr, "Usage: %s [-v version] input_file trace_prefix\n",
+ argv[0]);
+ exit(1);
+ }
+
+ inputFile = argv[optind++];
+ parseInputFile(inputFile);
+ traceFileName = argv[optind++];
+
+ writeTrace(traceFileName);
+
+ return 0;
+}
diff --git a/tools/dmtracedump/TraceDump.c b/tools/dmtracedump/TraceDump.c
new file mode 100644
index 0000000..ae56d4d
--- /dev/null
+++ b/tools/dmtracedump/TraceDump.c
@@ -0,0 +1,2883 @@
+/* //device/tools/dmtracedump/TraceDump.c
+**
+** Copyright 2006, The Android Open Source Project
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+/*
+ * Process dmtrace output.
+ *
+ * This is the wrong way to go about it -- C is a clumsy language for
+ * shuffling data around. It'll do for a first pass.
+ */
+#define NOT_VM
+#include "Profile.h" // from VM header
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <inttypes.h>
+#include <time.h>
+#include <errno.h>
+#include <assert.h>
+
+/* Version number in the key file. Version 1 uses one byte for the thread id.
+ * Version 2 uses two bytes for the thread ids.
+ */
+int versionNumber;
+
+/* arbitrarily limit indentation */
+#define MAX_STACK_DEPTH 10000
+
+/* thread list in key file is not reliable, so just max out */
+#define MAX_THREADS 32768
+
+/* Size of temporary buffers for escaping html strings */
+#define HTML_BUFSIZE 10240
+
+char *htmlHeader =
+"<html>\n<head>\n<script type=\"text/javascript\" src=\"%ssortable.js\"></script>\n"
+"<script langugage=\"javascript\">\n"
+"function toggle(item) {\n"
+" obj=document.getElementById(item);\n"
+" visible=(obj.style.display!=\"none\" && obj.style.display!=\"\");\n"
+" key=document.getElementById(\"x\" + item);\n"
+" if (visible) {\n"
+" obj.style.display=\"none\";\n"
+" key.innerHTML=\"+\";\n"
+" } else {\n"
+" obj.style.display=\"block\";\n"
+" key.innerHTML=\"-\";\n"
+" }\n"
+"}\n"
+"function onMouseOver(obj) {\n"
+" obj.style.background=\"lightblue\";\n"
+"}\n"
+"function onMouseOut(obj) {\n"
+" obj.style.background=\"white\";\n"
+"}\n"
+"</script>\n"
+"<style type=\"text/css\">\n"
+"div { font-family: courier; font-size: 13 }\n"
+"div.parent { margin-left: 15; display: none }\n"
+"div.leaf { margin-left: 10 }\n"
+"div.header { margin-left: 10 }\n"
+"div.link { margin-left: 10; cursor: move }\n"
+"span.parent { padding-right: 10; }\n"
+"span.leaf { padding-right: 10; }\n"
+"a img { border: 0;}\n"
+"table.sortable th { border-width: 0px 1px 1px 1px; background-color: #ccc;}\n"
+"a { text-decoration: none; }\n"
+"a:hover { text-decoration: underline; }\n"
+"table.sortable th, table.sortable td { text-align: left;}"
+"table.sortable tr.odd td { background-color: #ddd; }\n"
+"table.sortable tr.even td { background-color: #fff; }\n"
+"</style>\n"
+"</head><body>\n\n";
+
+char *htmlFooter = "\n</body>\n</html>\n";
+char *profileSeparator =
+ "======================================================================";
+
+const char* tableHeader =
+ "<table class='sortable' id='%s'><tr>\n"
+ "<th>Method</th>\n"
+ "<th>Run 1 (us)</th>\n"
+ "<th>Run 2 (us)</th>\n"
+ "<th>Diff (us)</th>\n"
+ "<th>Diff (%%)</th>\n"
+ "<th>1: # calls</th>\n"
+ "<th>2: # calls</th>\n"
+ "</tr>\n";
+
+const char* tableHeaderMissing =
+ "<table class='sortable' id='%s'>\n"
+ "<th>Method</th>\n"
+ "<th>Exclusive</th>\n"
+ "<th>Inclusive</th>\n"
+ "<th># calls</th>\n";
+
+#define GRAPH_LABEL_VISITED 0x0001
+#define GRAPH_NODE_VISITED 0x0002
+
+/*
+ * Values from the header of the data file.
+ */
+typedef struct DataHeader {
+ unsigned int magic;
+ short version;
+ short offsetToData;
+ long long startWhen;
+} DataHeader;
+
+/*
+ * Entry from the thread list.
+ */
+typedef struct ThreadEntry {
+ int threadId;
+ const char* threadName;
+} ThreadEntry;
+
+struct MethodEntry;
+typedef struct TimedMethod {
+ struct TimedMethod *next;
+ uint64_t elapsedInclusive;
+ int numCalls;
+ struct MethodEntry *method;
+} TimedMethod;
+
+typedef struct ClassEntry {
+ const char *className;
+ uint64_t elapsedExclusive;
+ int numMethods;
+ struct MethodEntry **methods; /* list of methods in this class */
+ int numCalls[2]; /* 0=normal, 1=recursive */
+} ClassEntry;
+
+typedef struct UniqueMethodEntry {
+ uint64_t elapsedExclusive;
+ int numMethods;
+ struct MethodEntry **methods; /* list of methods with same name */
+ int numCalls[2]; /* 0=normal, 1=recursive */
+} UniqueMethodEntry;
+
+/*
+ * Entry from the method list.
+ */
+typedef struct MethodEntry {
+ unsigned int methodId;
+ const char* className;
+ const char* methodName;
+ const char* signature;
+ const char* fileName;
+ int lineNum;
+ uint64_t elapsedExclusive;
+ uint64_t elapsedInclusive;
+ uint64_t topExclusive; /* non-recursive exclusive time */
+ uint64_t recursiveInclusive;
+ struct TimedMethod *parents[2]; /* 0=normal, 1=recursive */
+ struct TimedMethod *children[2]; /* 0=normal, 1=recursive */
+ int numCalls[2]; /* 0=normal, 1=recursive */
+ int index; /* used after sorting to number methods */
+ int recursiveEntries; /* number of entries on the stack */
+ int graphState; /* used when graphing to see if this method has been visited before */
+} MethodEntry;
+
+/*
+ * The parsed contents of the key file.
+ */
+typedef struct DataKeys {
+ char* fileData; /* contents of the entire file */
+ long fileLen;
+ int numThreads;
+ ThreadEntry* threads;
+ int numMethods;
+ MethodEntry* methods; /* 2 extra methods: "toplevel" and "unknown" */
+} DataKeys;
+
+#define TOPLEVEL_INDEX 0
+#define UNKNOWN_INDEX 1
+
+typedef struct StackEntry {
+ MethodEntry *method;
+ uint64_t entryTime;
+} StackEntry;
+
+typedef struct CallStack {
+ int top;
+ StackEntry calls[MAX_STACK_DEPTH];
+ uint64_t lastEventTime;
+ uint64_t threadStartTime;
+} CallStack;
+
+typedef struct DiffEntry {
+ MethodEntry* method1;
+ MethodEntry* method2;
+ int64_t differenceExclusive;
+ int64_t differenceInclusive;
+ double differenceExclusivePercentage;
+ double differenceInclusivePercentage;
+} DiffEntry;
+
+// Global options
+typedef struct Options {
+ const char* traceFileName;
+ const char* diffFileName;
+ const char* graphFileName;
+ int keepDotFile;
+ int dump;
+ int outputHtml;
+ const char* sortableUrl;
+ int threshold;
+} Options;
+
+typedef struct TraceData {
+ int numClasses;
+ ClassEntry *classes;
+ CallStack *stacks[MAX_THREADS];
+ int depth[MAX_THREADS];
+ int numUniqueMethods;
+ UniqueMethodEntry *uniqueMethods;
+} TraceData;
+
+static Options gOptions;
+
+/* Escapes characters in the source string that are html special entities.
+ * The escaped string is written to "dest" which must be large enough to
+ * hold the result. A pointer to "dest" is returned. The characters and
+ * their corresponding escape sequences are:
+ * '<' <
+ * '>' >
+ * '&' &
+ */
+char *htmlEscape(const char *src, char *dest, int len)
+{
+ char *destStart = dest;
+
+ if (src == NULL)
+ return NULL;
+
+ int nbytes = 0;
+ while (*src) {
+ if (*src == '<') {
+ nbytes += 4;
+ if (nbytes >= len)
+ break;
+ *dest++ = '&';
+ *dest++ = 'l';
+ *dest++ = 't';
+ *dest++ = ';';
+ } else if (*src == '>') {
+ nbytes += 4;
+ if (nbytes >= len)
+ break;
+ *dest++ = '&';
+ *dest++ = 'g';
+ *dest++ = 't';
+ *dest++ = ';';
+ } else if (*src == '&') {
+ nbytes += 5;
+ if (nbytes >= len)
+ break;
+ *dest++ = '&';
+ *dest++ = 'a';
+ *dest++ = 'm';
+ *dest++ = 'p';
+ *dest++ = ';';
+ } else {
+ nbytes += 1;
+ if (nbytes >= len)
+ break;
+ *dest++ = *src;
+ }
+ src += 1;
+ }
+ if (nbytes >= len) {
+ fprintf(stderr, "htmlEscape(): buffer overflow\n");
+ exit(1);
+ }
+ *dest = 0;
+
+ return destStart;
+}
+
+/* Initializes a MethodEntry
+ */
+void initMethodEntry(MethodEntry *method, unsigned int methodId,
+ const char *className, const char *methodName,
+ const char *signature, const char* fileName,
+ const char* lineNumStr)
+{
+ method->methodId = methodId;
+ method->className = className;
+ method->methodName = methodName;
+ method->signature = signature;
+ method->fileName = fileName;
+ method->lineNum = (lineNumStr != NULL) ? atoi(lineNumStr) : -1;
+ method->elapsedExclusive = 0;
+ method->elapsedInclusive = 0;
+ method->topExclusive = 0;
+ method->recursiveInclusive = 0;
+ method->parents[0] = NULL;
+ method->parents[1] = NULL;
+ method->children[0] = NULL;
+ method->children[1] = NULL;
+ method->numCalls[0] = 0;
+ method->numCalls[1] = 0;
+ method->index = 0;
+ method->recursiveEntries = 0;
+}
+
+/*
+ * This comparison function is called from qsort() to sort
+ * methods into decreasing order of exclusive elapsed time.
+ */
+int compareElapsedExclusive(const void *a, const void *b) {
+ uint64_t elapsed1, elapsed2;
+ int result;
+
+ const MethodEntry *methodA = *(const MethodEntry**)a;
+ const MethodEntry *methodB = *(const MethodEntry**)b;
+ elapsed1 = methodA->elapsedExclusive;
+ elapsed2 = methodB->elapsedExclusive;
+ if (elapsed1 < elapsed2)
+ return 1;
+ if (elapsed1 > elapsed2)
+ return -1;
+
+ /* If the elapsed times of two methods are equal, then sort them
+ * into alphabetical order.
+ */
+ result = strcmp(methodA->className, methodB->className);
+ if (result == 0) {
+ if (methodA->methodName == NULL || methodB->methodName == NULL) {
+ unsigned int idA = methodA->methodId;
+ unsigned int idB = methodB->methodId;
+ if (idA < idB)
+ return -1;
+ if (idA > idB)
+ return 1;
+ return 0;
+ }
+ result = strcmp(methodA->methodName, methodB->methodName);
+ if (result == 0)
+ result = strcmp(methodA->signature, methodB->signature);
+ }
+ return result;
+}
+
+/*
+ * This comparison function is called from qsort() to sort
+ * methods into decreasing order of inclusive elapsed time.
+ */
+int compareElapsedInclusive(const void *a, const void *b) {
+ const MethodEntry *methodA, *methodB;
+ uint64_t elapsed1, elapsed2;
+ int result;
+
+ methodA = *(MethodEntry const **)a;
+ methodB = *(MethodEntry const **)b;
+ elapsed1 = methodA->elapsedInclusive;
+ elapsed2 = methodB->elapsedInclusive;
+ if (elapsed1 < elapsed2)
+ return 1;
+ if (elapsed1 > elapsed2)
+ return -1;
+
+ /* If the elapsed times of two methods are equal, then sort them
+ * into alphabetical order.
+ */
+ result = strcmp(methodA->className, methodB->className);
+ if (result == 0) {
+ if (methodA->methodName == NULL || methodB->methodName == NULL) {
+ unsigned int idA = methodA->methodId;
+ unsigned int idB = methodB->methodId;
+ if (idA < idB)
+ return -1;
+ if (idA > idB)
+ return 1;
+ return 0;
+ }
+ result = strcmp(methodA->methodName, methodB->methodName);
+ if (result == 0)
+ result = strcmp(methodA->signature, methodB->signature);
+ }
+ return result;
+}
+
+/*
+ * This comparison function is called from qsort() to sort
+ * TimedMethods into decreasing order of inclusive elapsed time.
+ */
+int compareTimedMethod(const void *a, const void *b) {
+ const TimedMethod *timedA, *timedB;
+ uint64_t elapsed1, elapsed2;
+ int result;
+
+ timedA = (TimedMethod const *)a;
+ timedB = (TimedMethod const *)b;
+ elapsed1 = timedA->elapsedInclusive;
+ elapsed2 = timedB->elapsedInclusive;
+ if (elapsed1 < elapsed2)
+ return 1;
+ if (elapsed1 > elapsed2)
+ return -1;
+
+ /* If the elapsed times of two methods are equal, then sort them
+ * into alphabetical order.
+ */
+ MethodEntry *methodA = timedA->method;
+ MethodEntry *methodB = timedB->method;
+ result = strcmp(methodA->className, methodB->className);
+ if (result == 0) {
+ if (methodA->methodName == NULL || methodB->methodName == NULL) {
+ unsigned int idA = methodA->methodId;
+ unsigned int idB = methodB->methodId;
+ if (idA < idB)
+ return -1;
+ if (idA > idB)
+ return 1;
+ return 0;
+ }
+ result = strcmp(methodA->methodName, methodB->methodName);
+ if (result == 0)
+ result = strcmp(methodA->signature, methodB->signature);
+ }
+ return result;
+}
+
+/*
+ * This comparison function is called from qsort() to sort
+ * MethodEntry pointers into alphabetical order of class names.
+ */
+int compareClassNames(const void *a, const void *b) {
+ int result;
+
+ const MethodEntry *methodA = *(const MethodEntry**)a;
+ const MethodEntry *methodB = *(const MethodEntry**)b;
+ result = strcmp(methodA->className, methodB->className);
+ if (result == 0) {
+ unsigned int idA = methodA->methodId;
+ unsigned int idB = methodB->methodId;
+ if (idA < idB)
+ return -1;
+ if (idA > idB)
+ return 1;
+ return 0;
+ }
+ return result;
+}
+
+/*
+ * This comparison function is called from qsort() to sort
+ * classes into decreasing order of exclusive elapsed time.
+ */
+int compareClassExclusive(const void *a, const void *b) {
+ uint64_t elapsed1, elapsed2;
+ int result;
+
+ const ClassEntry *classA = *(const ClassEntry**)a;
+ const ClassEntry *classB = *(const ClassEntry**)b;
+ elapsed1 = classA->elapsedExclusive;
+ elapsed2 = classB->elapsedExclusive;
+ if (elapsed1 < elapsed2)
+ return 1;
+ if (elapsed1 > elapsed2)
+ return -1;
+
+ /* If the elapsed times of two classs are equal, then sort them
+ * into alphabetical order.
+ */
+ result = strcmp(classA->className, classB->className);
+ if (result == 0) {
+ /* Break ties with the first method id. This is probably not
+ * needed.
+ */
+ unsigned int idA = classA->methods[0]->methodId;
+ unsigned int idB = classB->methods[0]->methodId;
+ if (idA < idB)
+ return -1;
+ if (idA > idB)
+ return 1;
+ return 0;
+ }
+ return result;
+}
+
+/*
+ * This comparison function is called from qsort() to sort
+ * MethodEntry pointers into alphabetical order by method name,
+ * then by class name.
+ */
+int compareMethodNames(const void *a, const void *b) {
+ int result;
+
+ const MethodEntry *methodA = *(const MethodEntry**)a;
+ const MethodEntry *methodB = *(const MethodEntry**)b;
+ if (methodA->methodName == NULL || methodB->methodName == NULL) {
+ return compareClassNames(a, b);
+ }
+ result = strcmp(methodA->methodName, methodB->methodName);
+ if (result == 0) {
+ result = strcmp(methodA->className, methodB->className);
+ if (result == 0) {
+ unsigned int idA = methodA->methodId;
+ unsigned int idB = methodB->methodId;
+ if (idA < idB)
+ return -1;
+ if (idA > idB)
+ return 1;
+ return 0;
+ }
+ }
+ return result;
+}
+
+/*
+ * This comparison function is called from qsort() to sort
+ * unique methods into decreasing order of exclusive elapsed time.
+ */
+int compareUniqueExclusive(const void *a, const void *b) {
+ uint64_t elapsed1, elapsed2;
+ int result;
+
+ const UniqueMethodEntry *uniqueA = *(const UniqueMethodEntry**)a;
+ const UniqueMethodEntry *uniqueB = *(const UniqueMethodEntry**)b;
+ elapsed1 = uniqueA->elapsedExclusive;
+ elapsed2 = uniqueB->elapsedExclusive;
+ if (elapsed1 < elapsed2)
+ return 1;
+ if (elapsed1 > elapsed2)
+ return -1;
+
+ /* If the elapsed times of two methods are equal, then sort them
+ * into alphabetical order.
+ */
+ result = strcmp(uniqueA->methods[0]->className,
+ uniqueB->methods[0]->className);
+ if (result == 0) {
+ unsigned int idA = uniqueA->methods[0]->methodId;
+ unsigned int idB = uniqueB->methods[0]->methodId;
+ if (idA < idB)
+ return -1;
+ if (idA > idB)
+ return 1;
+ return 0;
+ }
+ return result;
+}
+
+/*
+ * Free a DataKeys struct.
+ */
+void freeDataKeys(DataKeys* pKeys)
+{
+ if (pKeys == NULL)
+ return;
+
+ free(pKeys->fileData);
+ free(pKeys->threads);
+ free(pKeys->methods);
+ free(pKeys);
+}
+
+/*
+ * Find the offset to the next occurrence of the specified character.
+ *
+ * "data" should point somewhere within the current line. "len" is the
+ * number of bytes left in the buffer.
+ *
+ * Returns -1 if we hit the end of the buffer.
+ */
+int findNextChar(const char* data, int len, char lookFor)
+{
+ const char* start = data;
+
+ while (len > 0) {
+ if (*data == lookFor)
+ return data - start;
+
+ data++;
+ len--;
+ }
+
+ return -1;
+}
+
+/*
+ * Count the number of lines until the next token.
+ *
+ * Returns -1 if none found before EOF.
+ */
+int countLinesToToken(const char* data, int len)
+{
+ int count = 0;
+ int next;
+
+ while (*data != TOKEN_CHAR) {
+ next = findNextChar(data, len, '\n');
+ if (next < 0)
+ return -1;
+ count++;
+ data += next+1;
+ len -= next+1;
+ }
+
+ return count;
+}
+
+/*
+ * Make sure we're at the start of the right section.
+ *
+ * Returns the length of the token line, or -1 if something is wrong.
+ */
+int checkToken(const char* data, int len, const char* cmpStr)
+{
+ int cmpLen = strlen(cmpStr);
+ int next;
+
+ if (*data != TOKEN_CHAR) {
+ fprintf(stderr,
+ "ERROR: not at start of %s (found '%.10s')\n", cmpStr, data);
+ return -1;
+ }
+
+ next = findNextChar(data, len, '\n');
+ if (next < cmpLen+1)
+ return -1;
+
+ if (strncmp(data+1, cmpStr, cmpLen) != 0) {
+ fprintf(stderr, "ERROR: '%s' not found (got '%.7s')\n", cmpStr, data+1);
+ return -1;
+ }
+
+ return next+1;
+}
+
+/*
+ * Parse the "*version" section.
+ */
+long parseVersion(DataKeys* pKeys, long offset, int verbose)
+{
+ char* data;
+ char* dataEnd;
+ int i, count, next;
+
+ if (offset < 0)
+ return -1;
+
+ data = pKeys->fileData + offset;
+ dataEnd = pKeys->fileData + pKeys->fileLen;
+ next = checkToken(data, dataEnd - data, "version");
+ if (next <= 0)
+ return -1;
+
+ data += next;
+
+ /*
+ * Count the number of items in the "version" section.
+ */
+ count = countLinesToToken(data, dataEnd - data);
+ if (count <= 0) {
+ fprintf(stderr,
+ "ERROR: failed while reading version (found %d)\n", count);
+ return -1;
+ }
+
+ /* find the end of the line */
+ next = findNextChar(data, dataEnd - data, '\n');
+ if (next < 0)
+ return -1;
+
+ data[next] = '\0';
+ versionNumber = strtoul(data, NULL, 0);
+ if (verbose)
+ printf("VERSION: %d\n", versionNumber);
+
+ data += next+1;
+
+ /* skip over the rest of the stuff, which is "name=value" lines */
+ for (i = 1; i < count; i++) {
+ next = findNextChar(data, dataEnd - data, '\n');
+ if (next < 0)
+ return -1;
+ //data[next] = '\0';
+ //printf("IGNORING: '%s'\n", data);
+ data += next+1;
+ }
+
+ return data - pKeys->fileData;
+}
+
+/*
+ * Parse the "*threads" section.
+ */
+long parseThreads(DataKeys* pKeys, long offset)
+{
+ char* data;
+ char* dataEnd;
+ int i, next, tab, count;
+
+ if (offset < 0)
+ return -1;
+
+ data = pKeys->fileData + offset;
+ dataEnd = pKeys->fileData + pKeys->fileLen;
+ next = checkToken(data, dataEnd - data, "threads");
+
+ data += next;
+
+ /*
+ * Count the number of thread entries (one per line).
+ */
+ count = countLinesToToken(data, dataEnd - data);
+ if (count <= 0) {
+ fprintf(stderr,
+ "ERROR: failed while reading threads (found %d)\n", count);
+ return -1;
+ }
+
+ //printf("+++ found %d threads\n", count);
+ pKeys->threads = (ThreadEntry*) malloc(sizeof(ThreadEntry) * count);
+ if (pKeys->threads == NULL)
+ return -1;
+
+ /*
+ * Extract all entries.
+ */
+ for (i = 0; i < count; i++) {
+ next = findNextChar(data, dataEnd - data, '\n');
+ assert(next > 0);
+ data[next] = '\0';
+
+ tab = findNextChar(data, next, '\t');
+ data[tab] = '\0';
+
+ pKeys->threads[i].threadId = atoi(data);
+ pKeys->threads[i].threadName = data + tab +1;
+
+ data += next+1;
+ }
+
+ pKeys->numThreads = count;
+ return data - pKeys->fileData;
+}
+
+/*
+ * Parse the "*methods" section.
+ */
+long parseMethods(DataKeys* pKeys, long offset)
+{
+ char* data;
+ char* dataEnd;
+ int i, next, count;
+
+ if (offset < 0)
+ return -1;
+
+ data = pKeys->fileData + offset;
+ dataEnd = pKeys->fileData + pKeys->fileLen;
+ next = checkToken(data, dataEnd - data, "methods");
+ if (next < 0)
+ return -1;
+
+ data += next;
+
+ /*
+ * Count the number of method entries (one per line).
+ */
+ count = countLinesToToken(data, dataEnd - data);
+ if (count <= 0) {
+ fprintf(stderr,
+ "ERROR: failed while reading methods (found %d)\n", count);
+ return -1;
+ }
+
+ /* Reserve an extra method at location 0 for the "toplevel" method,
+ * and another extra method for all other "unknown" methods.
+ */
+ count += 2;
+ pKeys->methods = (MethodEntry*) malloc(sizeof(MethodEntry) * count);
+ if (pKeys->methods == NULL)
+ return -1;
+ initMethodEntry(&pKeys->methods[TOPLEVEL_INDEX], 0, "(toplevel)",
+ NULL, NULL, NULL, NULL);
+ initMethodEntry(&pKeys->methods[UNKNOWN_INDEX], 0, "(unknown)",
+ NULL, NULL, NULL, NULL);
+
+ /*
+ * Extract all entries, starting with index 2.
+ */
+ for (i = UNKNOWN_INDEX + 1; i < count; i++) {
+ int tab1, tab2, tab3, tab4, tab5;
+ unsigned int id;
+ char* endptr;
+
+ next = findNextChar(data, dataEnd - data, '\n');
+ assert(next > 0);
+ data[next] = '\0';
+
+ tab1 = findNextChar(data, next, '\t');
+ tab2 = findNextChar(data+(tab1+1), next-(tab1+1), '\t');
+ tab3 = findNextChar(data+(tab1+tab2+2), next-(tab1+tab2+2), '\t');
+ tab4 = findNextChar(data+(tab1+tab2+tab3+3),
+ next-(tab1+tab2+tab3+3), '\t');
+ tab5 = findNextChar(data+(tab1+tab2+tab3+tab4+4),
+ next-(tab1+tab2+tab3+tab4+4), '\t');
+ if (tab1 < 0) {
+ fprintf(stderr, "ERROR: missing field on method line: '%s'\n",
+ data);
+ return -1;
+ }
+ assert(data[tab1] == '\t');
+ data[tab1] = '\0';
+
+ id = strtoul(data, &endptr, 0);
+ if (*endptr != '\0') {
+ fprintf(stderr, "ERROR: bad method ID '%s'\n", data);
+ return -1;
+ }
+
+ // Allow files that specify just a function name, instead of requiring
+ // "class \t method \t signature"
+ if (tab2 > 0 && tab3 > 0) {
+ tab2 += tab1+1;
+ tab3 += tab2+1;
+ assert(data[tab2] == '\t');
+ assert(data[tab3] == '\t');
+ data[tab2] = data[tab3] = '\0';
+
+ // This is starting to get awkward. Allow filename and line #.
+ if (tab4 > 0 && tab5 > 0) {
+ tab4 += tab3+1;
+ tab5 += tab4+1;
+
+ assert(data[tab4] == '\t');
+ assert(data[tab5] == '\t');
+ data[tab4] = data[tab5] = '\0';
+
+ initMethodEntry(&pKeys->methods[i], id, data + tab1 +1,
+ data + tab2 +1, data + tab3 +1, data + tab4 +1,
+ data + tab5 +1);
+ } else {
+ initMethodEntry(&pKeys->methods[i], id, data + tab1 +1,
+ data + tab2 +1, data + tab3 +1, NULL, NULL);
+ }
+ } else {
+ initMethodEntry(&pKeys->methods[i], id, data + tab1 +1,
+ NULL, NULL, NULL, NULL);
+ }
+
+ data += next+1;
+ }
+
+ pKeys->numMethods = count;
+ return data - pKeys->fileData;
+}
+
+/*
+ * Parse the "*end" section.
+ */
+long parseEnd(DataKeys* pKeys, long offset)
+{
+ char* data;
+ char* dataEnd;
+ int next;
+
+ if (offset < 0)
+ return -1;
+
+ data = pKeys->fileData + offset;
+ dataEnd = pKeys->fileData + pKeys->fileLen;
+ next = checkToken(data, dataEnd - data, "end");
+ if (next < 0)
+ return -1;
+
+ data += next;
+
+ return data - pKeys->fileData;
+}
+
+/*
+ * Sort the thread list entries.
+ */
+static int compareThreads(const void* thread1, const void* thread2)
+{
+ return ((const ThreadEntry*) thread1)->threadId -
+ ((const ThreadEntry*) thread2)->threadId;
+}
+
+void sortThreadList(DataKeys* pKeys)
+{
+ qsort(pKeys->threads, pKeys->numThreads, sizeof(pKeys->threads[0]),
+ compareThreads);
+}
+
+/*
+ * Sort the method list entries.
+ */
+static int compareMethods(const void* meth1, const void* meth2)
+{
+ unsigned int id1, id2;
+
+ id1 = ((const MethodEntry*) meth1)->methodId;
+ id2 = ((const MethodEntry*) meth2)->methodId;
+ if (id1 < id2)
+ return -1;
+ if (id1 > id2)
+ return 1;
+ return 0;
+}
+
+void sortMethodList(DataKeys* pKeys)
+{
+ qsort(pKeys->methods, pKeys->numMethods, sizeof(MethodEntry),
+ compareMethods);
+}
+
+/*
+ * Parse the key section, and return a copy of the parsed contents.
+ */
+DataKeys* parseKeys(FILE *fp, int verbose)
+{
+ DataKeys* pKeys = NULL;
+ long offset;
+ int i;
+
+ pKeys = (DataKeys*) calloc(1, sizeof(DataKeys));
+ if (pKeys == NULL)
+ goto fail;
+
+ /*
+ * We load the entire file into memory. We do this, rather than memory-
+ * mapping it, because we want to change some whitespace to NULs.
+ */
+ if (fseek(fp, 0L, SEEK_END) != 0) {
+ perror("fseek");
+ goto fail;
+ }
+ pKeys->fileLen = ftell(fp);
+ if (pKeys->fileLen == 0) {
+ fprintf(stderr, "Key file is empty.\n");
+ goto fail;
+ }
+ rewind(fp);
+
+ pKeys->fileData = (char*) malloc(pKeys->fileLen);
+ if (pKeys->fileData == NULL) {
+ fprintf(stderr, "ERROR: unable to alloc %ld bytes\n", pKeys->fileLen);
+ goto fail;
+ }
+
+ if (fread(pKeys->fileData, 1, pKeys->fileLen, fp) != (size_t) pKeys->fileLen)
+ {
+ fprintf(stderr, "ERROR: unable to read %ld bytes from trace file\n",
+ pKeys->fileLen);
+ goto fail;
+ }
+
+ offset = 0;
+
+ offset = parseVersion(pKeys, offset, verbose);
+ offset = parseThreads(pKeys, offset);
+ offset = parseMethods(pKeys, offset);
+ offset = parseEnd(pKeys, offset);
+ if (offset < 0)
+ goto fail;
+
+ /* Reduce our allocation now that we know where the end of the key section is. */
+ pKeys->fileData = (char *)realloc(pKeys->fileData, offset);
+ pKeys->fileLen = offset;
+ /* Leave fp pointing to the beginning of the data section. */
+ fseek(fp, offset, SEEK_SET);
+
+ sortThreadList(pKeys);
+ sortMethodList(pKeys);
+
+ /*
+ * Dump list of threads.
+ */
+ if (verbose) {
+ printf("Threads (%d):\n", pKeys->numThreads);
+ for (i = 0; i < pKeys->numThreads; i++) {
+ printf("%2d %s\n",
+ pKeys->threads[i].threadId, pKeys->threads[i].threadName);
+ }
+ }
+
+#if 0
+ /*
+ * Dump list of methods.
+ */
+ if (verbose) {
+ printf("Methods (%d):\n", pKeys->numMethods);
+ for (i = 0; i < pKeys->numMethods; i++) {
+ printf("0x%08x %s : %s : %s\n",
+ pKeys->methods[i].methodId, pKeys->methods[i].className,
+ pKeys->methods[i].methodName, pKeys->methods[i].signature);
+ }
+ }
+#endif
+
+ return pKeys;
+
+fail:
+ freeDataKeys(pKeys);
+ return NULL;
+}
+
+
+/*
+ * Read values from the binary data file.
+ */
+
+/* Make the return value "unsigned int" instead of "unsigned short" so that
+ * we can detect EOF.
+ */
+unsigned int read2LE(FILE* fp)
+{
+ unsigned int val;
+
+ val = getc(fp);
+ val |= getc(fp) << 8;
+ return val;
+}
+unsigned int read4LE(FILE* fp)
+{
+ unsigned int val;
+
+ val = getc(fp);
+ val |= getc(fp) << 8;
+ val |= getc(fp) << 16;
+ val |= getc(fp) << 24;
+ return val;
+}
+unsigned long long read8LE(FILE* fp)
+{
+ unsigned long long val;
+
+ val = getc(fp);
+ val |= (unsigned long long) getc(fp) << 8;
+ val |= (unsigned long long) getc(fp) << 16;
+ val |= (unsigned long long) getc(fp) << 24;
+ val |= (unsigned long long) getc(fp) << 32;
+ val |= (unsigned long long) getc(fp) << 40;
+ val |= (unsigned long long) getc(fp) << 48;
+ val |= (unsigned long long) getc(fp) << 56;
+ return val;
+}
+
+/*
+ * Parse the header of the data section.
+ *
+ * Returns with the file positioned at the start of the record data.
+ */
+int parseDataHeader(FILE *fp, DataHeader* pHeader)
+{
+ pHeader->magic = read4LE(fp);
+ pHeader->version = read2LE(fp);
+ pHeader->offsetToData = read2LE(fp);
+ pHeader->startWhen = read8LE(fp);
+
+ if (fseek(fp, pHeader->offsetToData - 16, SEEK_CUR) != 0) {
+ return -1;
+ }
+
+ return 0;
+}
+
+/*
+ * Look up a method by it's method ID.
+ *
+ * Returns NULL if no matching method was found.
+ */
+MethodEntry* lookupMethod(DataKeys* pKeys, unsigned int methodId)
+{
+ int hi, lo, mid;
+ unsigned int id;
+
+ lo = 0;
+ hi = pKeys->numMethods - 1;
+
+ while (hi >= lo) {
+ mid = (hi + lo) / 2;
+
+ id = pKeys->methods[mid].methodId;
+ if (id == methodId) /* match */
+ return &pKeys->methods[mid];
+ else if (id < methodId) /* too low */
+ lo = mid + 1;
+ else /* too high */
+ hi = mid - 1;
+ }
+
+ return NULL;
+}
+
+/*
+ * Reads the next data record, and assigns the data values to threadId,
+ * methodVal and elapsedTime. On end-of-file, the threadId, methodVal,
+ * and elapsedTime are unchanged. Returns 1 on end-of-file, otherwise
+ * returns 0.
+ */
+int readDataRecord(FILE *dataFp, int *threadId, unsigned int *methodVal,
+ uint64_t *elapsedTime)
+{
+ int id;
+
+ /*
+ * TODO:
+ * This SHOULD NOT be keyed off of the global version number! Use
+ * a name=value setting in the version area instead!
+ */
+ if (versionNumber == 1) {
+ id = getc(dataFp);
+ } else {
+ id = read2LE(dataFp);
+ }
+ if (id == EOF)
+ return 1;
+ *threadId = id;
+
+ *methodVal = read4LE(dataFp);
+ *elapsedTime = read4LE(dataFp);
+ if (feof(dataFp)) {
+ fprintf(stderr, "WARNING: hit EOF mid-record\n");
+ return 1;
+ }
+ return 0;
+}
+
+/*
+ * Read the key file and use it to produce formatted output from the
+ * data file.
+ */
+void dumpTrace()
+{
+ static const char* actionStr[] = { "ent", "xit", "unr", "???" };
+ MethodEntry bogusMethod = { 0, "???", "???", "???", "???", -1, 0, 0, 0, 0,
+ {NULL, NULL}, {NULL, NULL}, {0, 0}, 0, 0, -1 };
+ char bogusBuf[80];
+ char spaces[MAX_STACK_DEPTH+1];
+ FILE* dataFp = NULL;
+ DataHeader dataHeader;
+ DataKeys* pKeys = NULL;
+ int i;
+ TraceData traceData;
+
+ //printf("Dumping '%s' '%s'\n", dataFileName, keyFileName);
+
+ memset(spaces, '.', MAX_STACK_DEPTH);
+ spaces[MAX_STACK_DEPTH] = '\0';
+
+ for (i = 0; i < MAX_THREADS; i++)
+ traceData.depth[i] = 2; // adjust for return from start function
+
+ dataFp = fopen(gOptions.traceFileName, "r");
+ if (dataFp == NULL)
+ goto bail;
+
+ if ((pKeys = parseKeys(dataFp, 1)) == NULL)
+ goto bail;
+
+ if (parseDataHeader(dataFp, &dataHeader) < 0)
+ goto bail;
+
+ printf("Trace (threadID action usecs class.method signature):\n");
+
+ while (1) {
+ MethodEntry* method;
+ int threadId;
+ unsigned int methodVal;
+ uint64_t elapsedTime;
+ int action, printDepth;
+ unsigned int methodId, lastEnter = 0;
+ int mismatch = 0;
+ char depthNote;
+
+ /*
+ * Extract values from file.
+ */
+ if (readDataRecord(dataFp, &threadId, &methodVal, &elapsedTime))
+ break;
+
+ action = METHOD_ACTION(methodVal);
+ methodId = METHOD_ID(methodVal);
+
+ /*
+ * Generate a line of output.
+ */
+ if (action == METHOD_TRACE_ENTER) {
+ traceData.depth[threadId]++;
+ lastEnter = methodId;
+ } else {
+ /* quick test for mismatched adjacent enter/exit */
+ if (lastEnter != 0 && lastEnter != methodId)
+ mismatch = 1;
+ }
+
+ printDepth = traceData.depth[threadId];
+ depthNote = ' ';
+ if (printDepth < 0) {
+ printDepth = 0;
+ depthNote = '-';
+ } else if (printDepth > MAX_STACK_DEPTH) {
+ printDepth = MAX_STACK_DEPTH;
+ depthNote = '+';
+ }
+
+ method = lookupMethod(pKeys, methodId);
+ if (method == NULL) {
+ method = &bogusMethod;
+ sprintf(bogusBuf, "methodId: 0x%x", methodId);
+ method->signature = bogusBuf;
+ }
+
+ if (method->methodName) {
+ printf("%2d %s%c %8lld%c%s%s.%s %s\n", threadId,
+ actionStr[action], mismatch ? '!' : ' ',
+ elapsedTime, depthNote,
+ spaces + (MAX_STACK_DEPTH - printDepth),
+ method->className, method->methodName, method->signature);
+ } else {
+ printf("%2d %s%c %8lld%c%s%s\n", threadId,
+ actionStr[action], mismatch ? '!' : ' ',
+ elapsedTime, depthNote,
+ spaces + (MAX_STACK_DEPTH - printDepth),
+ method->className);
+ }
+
+ if (action != METHOD_TRACE_ENTER) {
+ traceData.depth[threadId]--; /* METHOD_TRACE_EXIT or METHOD_TRACE_UNROLL */
+ lastEnter = 0;
+ }
+
+ mismatch = 0;
+ }
+
+bail:
+ if (dataFp != NULL)
+ fclose(dataFp);
+ if (pKeys != NULL)
+ freeDataKeys(pKeys);
+}
+
+/* This routine adds the given time to the parent and child methods.
+ * This is called when the child routine exits, after the child has
+ * been popped from the stack. The elapsedTime parameter is the
+ * duration of the child routine, including time spent in called routines.
+ */
+void addInclusiveTime(MethodEntry *parent, MethodEntry *child,
+ uint64_t elapsedTime)
+{
+ TimedMethod *pTimed;
+
+#if 0
+ bool verbose = false;
+ if (strcmp(child->className, debugClassName) == 0)
+ verbose = true;
+#endif
+
+ int childIsRecursive = (child->recursiveEntries > 0);
+ int parentIsRecursive = (parent->recursiveEntries > 1);
+
+ if (child->recursiveEntries == 0) {
+ child->elapsedInclusive += elapsedTime;
+ } else if (child->recursiveEntries == 1) {
+ child->recursiveInclusive += elapsedTime;
+ }
+ child->numCalls[childIsRecursive] += 1;
+
+#if 0
+ if (verbose) {
+ fprintf(stderr,
+ "%s %d elapsedTime: %lld eI: %lld, rI: %lld\n",
+ child->className, child->recursiveEntries,
+ elapsedTime, child->elapsedInclusive,
+ child->recursiveInclusive);
+ }
+#endif
+
+ /* Find the child method in the parent */
+ TimedMethod *children = parent->children[parentIsRecursive];
+ for (pTimed = children; pTimed; pTimed = pTimed->next) {
+ if (pTimed->method == child) {
+ pTimed->elapsedInclusive += elapsedTime;
+ pTimed->numCalls += 1;
+ break;
+ }
+ }
+ if (pTimed == NULL) {
+ /* Allocate a new TimedMethod */
+ pTimed = (TimedMethod *) malloc(sizeof(TimedMethod));
+ pTimed->elapsedInclusive = elapsedTime;
+ pTimed->numCalls = 1;
+ pTimed->method = child;
+
+ /* Add it to the front of the list */
+ pTimed->next = children;
+ parent->children[parentIsRecursive] = pTimed;
+ }
+
+ /* Find the parent method in the child */
+ TimedMethod *parents = child->parents[childIsRecursive];
+ for (pTimed = parents; pTimed; pTimed = pTimed->next) {
+ if (pTimed->method == parent) {
+ pTimed->elapsedInclusive += elapsedTime;
+ pTimed->numCalls += 1;
+ break;
+ }
+ }
+ if (pTimed == NULL) {
+ /* Allocate a new TimedMethod */
+ pTimed = (TimedMethod *) malloc(sizeof(TimedMethod));
+ pTimed->elapsedInclusive = elapsedTime;
+ pTimed->numCalls = 1;
+ pTimed->method = parent;
+
+ /* Add it to the front of the list */
+ pTimed->next = parents;
+ child->parents[childIsRecursive] = pTimed;
+ }
+
+#if 0
+ if (verbose) {
+ fprintf(stderr,
+ " %s %d eI: %lld\n",
+ parent->className, parent->recursiveEntries,
+ pTimed->elapsedInclusive);
+ }
+#endif
+}
+
+/* Sorts a linked list and returns a newly allocated array containing
+ * the sorted entries.
+ */
+TimedMethod *sortTimedMethodList(TimedMethod *list, int *num)
+{
+ int ii;
+ TimedMethod *pTimed, *sorted;
+
+ /* Count the elements */
+ int num_entries = 0;
+ for (pTimed = list; pTimed; pTimed = pTimed->next)
+ num_entries += 1;
+ *num = num_entries;
+ if (num_entries == 0)
+ return NULL;
+
+ /* Copy all the list elements to a new array and sort them */
+ sorted = (TimedMethod *) malloc(sizeof(TimedMethod) * num_entries);
+ for (ii = 0, pTimed = list; pTimed; pTimed = pTimed->next, ++ii)
+ memcpy(&sorted[ii], pTimed, sizeof(TimedMethod));
+ qsort(sorted, num_entries, sizeof(TimedMethod), compareTimedMethod);
+
+ /* Fix up the "next" pointers so that they work. */
+ for (ii = 0; ii < num_entries - 1; ++ii)
+ sorted[ii].next = &sorted[ii + 1];
+ sorted[num_entries - 1].next = NULL;
+
+ return sorted;
+}
+
+/* Define flag values for printInclusiveMethod() */
+static const int kIsRecursive = 1;
+
+/* This prints the inclusive stats for all the parents or children of a
+ * method, depending on the list that is passed in.
+ */
+void printInclusiveMethod(MethodEntry *method, TimedMethod *list, int numCalls,
+ int flags)
+{
+ int num;
+ TimedMethod *pTimed;
+ char buf[80];
+ char *anchor_close;
+ char *spaces = " "; /* 6 spaces */
+ int num_spaces = strlen(spaces);
+ char *space_ptr = &spaces[num_spaces];
+ char *className, *methodName, *signature;
+ char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
+ char signatureBuf[HTML_BUFSIZE];
+
+ anchor_close = "";
+ if (gOptions.outputHtml)
+ anchor_close = "</a>";
+
+ TimedMethod *sorted = sortTimedMethodList(list, &num);
+ double methodTotal = method->elapsedInclusive;
+ for (pTimed = sorted; pTimed; pTimed = pTimed->next) {
+ MethodEntry *relative = pTimed->method;
+ className = (char*)(relative->className);
+ methodName = (char*)(relative->methodName);
+ signature = (char*)(relative->signature);
+ double per = 100.0 * pTimed->elapsedInclusive / methodTotal;
+ sprintf(buf, "[%d]", relative->index);
+ if (gOptions.outputHtml) {
+ int len = strlen(buf);
+ if (len > num_spaces)
+ len = num_spaces;
+ sprintf(buf, "<a href=\"#m%d\">[%d]",
+ relative->index, relative->index);
+ space_ptr = &spaces[len];
+ className = htmlEscape(className, classBuf, HTML_BUFSIZE);
+ methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
+ signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
+ }
+ int nCalls = numCalls;
+ if (nCalls == 0)
+ nCalls = relative->numCalls[0] + relative->numCalls[1];
+ if (relative->methodName) {
+ if (flags & kIsRecursive) {
+ // Don't display percentages for recursive functions
+ printf("%6s %5s %6s %s%6s%s %6d/%-6d %9llu %s.%s %s\n",
+ "", "", "",
+ space_ptr, buf, anchor_close,
+ pTimed->numCalls, nCalls,
+ pTimed->elapsedInclusive,
+ className, methodName, signature);
+ } else {
+ printf("%6s %5s %5.1f%% %s%6s%s %6d/%-6d %9llu %s.%s %s\n",
+ "", "", per,
+ space_ptr, buf, anchor_close,
+ pTimed->numCalls, nCalls,
+ pTimed->elapsedInclusive,
+ className, methodName, signature);
+ }
+ } else {
+ if (flags & kIsRecursive) {
+ // Don't display percentages for recursive functions
+ printf("%6s %5s %6s %s%6s%s %6d/%-6d %9llu %s\n",
+ "", "", "",
+ space_ptr, buf, anchor_close,
+ pTimed->numCalls, nCalls,
+ pTimed->elapsedInclusive,
+ className);
+ } else {
+ printf("%6s %5s %5.1f%% %s%6s%s %6d/%-6d %9llu %s\n",
+ "", "", per,
+ space_ptr, buf, anchor_close,
+ pTimed->numCalls, nCalls,
+ pTimed->elapsedInclusive,
+ className);
+ }
+ }
+ }
+}
+
+void countRecursiveEntries(CallStack *pStack, int top, MethodEntry *method)
+{
+ int ii;
+
+ method->recursiveEntries = 0;
+ for (ii = 0; ii < top; ++ii) {
+ if (pStack->calls[ii].method == method)
+ method->recursiveEntries += 1;
+ }
+}
+
+void stackDump(CallStack *pStack, int top)
+{
+ int ii;
+
+ for (ii = 0; ii < top; ++ii) {
+ MethodEntry *method = pStack->calls[ii].method;
+ uint64_t entryTime = pStack->calls[ii].entryTime;
+ if (method->methodName) {
+ fprintf(stderr, " %2d: %8llu %s.%s %s\n", ii, entryTime,
+ method->className, method->methodName, method->signature);
+ } else {
+ fprintf(stderr, " %2d: %8llu %s\n", ii, entryTime, method->className);
+ }
+ }
+}
+
+void outputTableOfContents()
+{
+ printf("<a name=\"contents\"></a>\n");
+ printf("<h2>Table of Contents</h2>\n");
+ printf("<ul>\n");
+ printf(" <li><a href=\"#exclusive\">Exclusive profile</a></li>\n");
+ printf(" <li><a href=\"#inclusive\">Inclusive profile</a></li>\n");
+ printf(" <li><a href=\"#class\">Class/method profile</a></li>\n");
+ printf(" <li><a href=\"#method\">Method/class profile</a></li>\n");
+ printf("</ul>\n\n");
+}
+
+void outputNavigationBar()
+{
+ printf("<a href=\"#contents\">[Top]</a>\n");
+ printf("<a href=\"#exclusive\">[Exclusive]</a>\n");
+ printf("<a href=\"#inclusive\">[Inclusive]</a>\n");
+ printf("<a href=\"#class\">[Class]</a>\n");
+ printf("<a href=\"#method\">[Method]</a>\n");
+ printf("<br><br>\n");
+}
+
+void printExclusiveProfile(MethodEntry **pMethods, int numMethods,
+ uint64_t sumThreadTime)
+{
+ int ii;
+ MethodEntry* method;
+ double total, sum, per, sum_per;
+ char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
+ char signatureBuf[HTML_BUFSIZE];
+ char anchor_buf[80];
+ char *anchor_close = "";
+
+ total = sumThreadTime;
+ anchor_buf[0] = 0;
+ if (gOptions.outputHtml) {
+ anchor_close = "</a>";
+ printf("<a name=\"exclusive\"></a>\n");
+ printf("<hr>\n");
+ outputNavigationBar();
+ } else {
+ printf("\n%s\n", profileSeparator);
+ }
+
+ /* First, sort the methods into decreasing order of inclusive
+ * elapsed time so that we can assign the method indices.
+ */
+ qsort(pMethods, numMethods, sizeof(MethodEntry*), compareElapsedInclusive);
+
+ for (ii = 0; ii < numMethods; ++ii)
+ pMethods[ii]->index = ii;
+
+ /* Sort the methods into decreasing order of exclusive elapsed time.
+ */
+ qsort(pMethods, numMethods, sizeof(MethodEntry*),
+ compareElapsedExclusive);
+
+ printf("Total cycles: %llu\n\n", sumThreadTime);
+ if (gOptions.outputHtml) {
+ printf("<br><br>\n");
+ }
+ printf("Exclusive elapsed times for each method, not including time spent in\n");
+ printf("children, sorted by exclusive time.\n\n");
+ if (gOptions.outputHtml) {
+ printf("<br><br>\n<pre>\n");
+ }
+
+ printf(" Usecs self %% sum %% Method\n");
+ sum = 0;
+
+ for (ii = 0; ii < numMethods; ++ii) {
+ char *className, *methodName, *signature;
+
+ method = pMethods[ii];
+ /* Don't show methods with zero cycles */
+ if (method->elapsedExclusive == 0)
+ break;
+ className = (char*)(method->className);
+ methodName = (char*)(method->methodName);
+ signature = (char*)(method->signature);
+ sum += method->elapsedExclusive;
+ per = 100.0 * method->elapsedExclusive / total;
+ sum_per = 100.0 * sum / total;
+ if (gOptions.outputHtml) {
+ sprintf(anchor_buf, "<a href=\"#m%d\">", method->index);
+ className = htmlEscape(className, classBuf, HTML_BUFSIZE);
+ methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
+ signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
+ }
+ if (method->methodName) {
+ printf("%9llu %6.2f %6.2f %s[%d]%s %s.%s %s\n",
+ method->elapsedExclusive, per, sum_per,
+ anchor_buf, method->index, anchor_close,
+ className, methodName, signature);
+ } else {
+ printf("%9llu %6.2f %6.2f %s[%d]%s %s\n",
+ method->elapsedExclusive, per, sum_per,
+ anchor_buf, method->index, anchor_close,
+ className);
+ }
+ }
+ if (gOptions.outputHtml) {
+ printf("</pre>\n");
+ }
+}
+
+/* check to make sure that the child method meets the threshold of the parent */
+int checkThreshold(MethodEntry* parent, MethodEntry* child)
+{
+ double parentTime = parent->elapsedInclusive;
+ double childTime = child->elapsedInclusive;
+ int64_t percentage = (childTime / parentTime) * 100.0;
+ return (percentage < gOptions.threshold) ? 0 : 1;
+}
+
+void createLabels(FILE* file, MethodEntry* method)
+{
+ fprintf(file, "node%d[label = \"[%d] %s.%s (%llu, %llu, %d)\"]\n",
+ method->index, method->index, method->className, method->methodName,
+ method->elapsedInclusive / 1000,
+ method->elapsedExclusive / 1000,
+ method->numCalls[0]);
+
+ method->graphState = GRAPH_LABEL_VISITED;
+
+ TimedMethod* child;
+ for (child = method->children[0] ; child ; child = child->next) {
+ MethodEntry* childMethod = child->method;
+
+ if ((childMethod->graphState & GRAPH_LABEL_VISITED) == 0 && checkThreshold(method, childMethod)) {
+ createLabels(file, child->method);
+ }
+ }
+}
+
+void createLinks(FILE* file, MethodEntry* method)
+{
+ method->graphState |= GRAPH_NODE_VISITED;
+
+ TimedMethod* child;
+ for (child = method->children[0] ; child ; child = child->next) {
+ MethodEntry* childMethod = child->method;
+ if (checkThreshold(method, child->method)) {
+ fprintf(file, "node%d -> node%d\n", method->index, child->method->index);
+ // only visit children that haven't been visited before
+ if ((childMethod->graphState & GRAPH_NODE_VISITED) == 0) {
+ createLinks(file, child->method);
+ }
+ }
+ }
+}
+
+void createInclusiveProfileGraphNew(DataKeys* dataKeys)
+{
+ // create a temporary file in /tmp
+ char path[FILENAME_MAX];
+ if (gOptions.keepDotFile) {
+ snprintf(path, FILENAME_MAX, "%s.dot", gOptions.graphFileName);
+ } else {
+ snprintf(path, FILENAME_MAX, "/tmp/dot-%d-%d.dot", (int)time(NULL), rand());
+ }
+
+ FILE* file = fopen(path, "w+");
+
+ fprintf(file, "digraph g {\nnode [shape = record,height=.1];\n");
+
+ createLabels(file, dataKeys->methods);
+ createLinks(file, dataKeys->methods);
+
+ fprintf(file, "}");
+ fclose(file);
+
+ // now that we have the dot file generate the image
+ char command[1024];
+ snprintf(command, 1024, "dot -Tpng -o '%s' '%s'", gOptions.graphFileName, path);
+
+ system(command);
+
+ if (! gOptions.keepDotFile) {
+ remove(path);
+ }
+}
+
+void printInclusiveProfile(MethodEntry **pMethods, int numMethods,
+ uint64_t sumThreadTime)
+{
+ int ii;
+ MethodEntry* method;
+ double total, sum, per, sum_per;
+ char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
+ char signatureBuf[HTML_BUFSIZE];
+ char anchor_buf[80];
+ char *anchor_close = "";
+
+ total = sumThreadTime;
+ anchor_buf[0] = 0;
+ if (gOptions.outputHtml) {
+ anchor_close = "</a>";
+ printf("<a name=\"inclusive\"></a>\n");
+ printf("<hr>\n");
+ outputNavigationBar();
+ } else {
+ printf("\n%s\n", profileSeparator);
+ }
+
+ /* Sort the methods into decreasing order of inclusive elapsed time. */
+ qsort(pMethods, numMethods, sizeof(MethodEntry*),
+ compareElapsedInclusive);
+
+ printf("\nInclusive elapsed times for each method and its parents and children,\n");
+ printf("sorted by inclusive time.\n\n");
+
+ if (gOptions.outputHtml) {
+ printf("<br><br>\n<pre>\n");
+ }
+
+ printf("index %%/total %%/self index calls usecs name\n");
+ for (ii = 0; ii < numMethods; ++ii) {
+ int num;
+ TimedMethod *pTimed;
+ double excl_per;
+ char buf[40];
+ char *className, *methodName, *signature;
+
+ method = pMethods[ii];
+ /* Don't show methods with zero cycles */
+ if (method->elapsedInclusive == 0)
+ break;
+
+ className = (char*)(method->className);
+ methodName = (char*)(method->methodName);
+ signature = (char*)(method->signature);
+
+ if (gOptions.outputHtml) {
+ printf("<a name=\"m%d\"></a>", method->index);
+ className = htmlEscape(className, classBuf, HTML_BUFSIZE);
+ methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
+ signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
+ }
+ printf("----------------------------------------------------\n");
+
+ /* Sort and print the parents */
+ int numCalls = method->numCalls[0] + method->numCalls[1];
+ printInclusiveMethod(method, method->parents[0], numCalls, 0);
+ if (method->parents[1]) {
+ printf(" +++++++++++++++++++++++++\n");
+ printInclusiveMethod(method, method->parents[1], numCalls,
+ kIsRecursive);
+ }
+
+ per = 100.0 * method->elapsedInclusive / total;
+ sprintf(buf, "[%d]", ii);
+ if (method->methodName) {
+ printf("%-6s %5.1f%% %5s %6s %6d+%-6d %9llu %s.%s %s\n",
+ buf,
+ per, "", "", method->numCalls[0], method->numCalls[1],
+ method->elapsedInclusive,
+ className, methodName, signature);
+ } else {
+ printf("%-6s %5.1f%% %5s %6s %6d+%-6d %9llu %s\n",
+ buf,
+ per, "", "", method->numCalls[0], method->numCalls[1],
+ method->elapsedInclusive,
+ className);
+ }
+ excl_per = 100.0 * method->topExclusive / method->elapsedInclusive;
+ printf("%6s %5s %5.1f%% %6s %6s %6s %9llu\n",
+ "", "", excl_per, "excl", "", "", method->topExclusive);
+
+ /* Sort and print the children */
+ printInclusiveMethod(method, method->children[0], 0, 0);
+ if (method->children[1]) {
+ printf(" +++++++++++++++++++++++++\n");
+ printInclusiveMethod(method, method->children[1], 0,
+ kIsRecursive);
+ }
+ }
+ if (gOptions.outputHtml) {
+ printf("</pre>\n");
+ }
+}
+
+void createClassList(TraceData* traceData, MethodEntry **pMethods, int numMethods)
+{
+ int ii;
+
+ /* Sort the methods into alphabetical order to find the unique class
+ * names.
+ */
+ qsort(pMethods, numMethods, sizeof(MethodEntry*), compareClassNames);
+
+ /* Count the number of unique class names. */
+ const char *currentClassName = "";
+ const char *firstClassName = NULL;
+ traceData->numClasses = 0;
+ for (ii = 0; ii < numMethods; ++ii) {
+ if (pMethods[ii]->methodName == NULL) {
+ continue;
+ }
+ if (strcmp(pMethods[ii]->className, currentClassName) != 0) {
+ // Remember the first one
+ if (firstClassName == NULL) {
+ firstClassName = pMethods[ii]->className;
+ }
+ traceData->numClasses += 1;
+ currentClassName = pMethods[ii]->className;
+ }
+ }
+
+ if (traceData->numClasses == 0) {
+ traceData->classes = NULL;
+ return;
+ }
+
+ /* Allocate space for all of the unique class names */
+ traceData->classes = (ClassEntry *) malloc(sizeof(ClassEntry) * traceData->numClasses);
+
+ /* Initialize the classes array */
+ memset(traceData->classes, 0, sizeof(ClassEntry) * traceData->numClasses);
+ ClassEntry *pClass = traceData->classes;
+ pClass->className = currentClassName = firstClassName;
+ int prevNumMethods = 0;
+ for (ii = 0; ii < numMethods; ++ii) {
+ if (pMethods[ii]->methodName == NULL) {
+ continue;
+ }
+ if (strcmp(pMethods[ii]->className, currentClassName) != 0) {
+ pClass->numMethods = prevNumMethods;
+ (++pClass)->className = currentClassName = pMethods[ii]->className;
+ prevNumMethods = 0;
+ }
+ prevNumMethods += 1;
+ }
+ pClass->numMethods = prevNumMethods;
+
+ /* Create the array of MethodEntry pointers for each class */
+ pClass = NULL;
+ currentClassName = "";
+ int nextMethod = 0;
+ for (ii = 0; ii < numMethods; ++ii) {
+ if (pMethods[ii]->methodName == NULL) {
+ continue;
+ }
+ if (strcmp(pMethods[ii]->className, currentClassName) != 0) {
+ currentClassName = pMethods[ii]->className;
+ if (pClass == NULL)
+ pClass = traceData->classes;
+ else
+ pClass++;
+ /* Allocate space for the methods array */
+ int nbytes = sizeof(MethodEntry*) * pClass->numMethods;
+ pClass->methods = (MethodEntry**) malloc(nbytes);
+ nextMethod = 0;
+ }
+ pClass->methods[nextMethod++] = pMethods[ii];
+ }
+}
+
+/* Prints a number of html non-breaking spaces according so that the length
+ * of the string "buf" is at least "width" characters wide. If width is
+ * negative, then trailing spaces are added instead of leading spaces.
+ */
+void printHtmlField(char *buf, int width)
+{
+ int ii;
+
+ int leadingSpaces = 1;
+ if (width < 0) {
+ width = -width;
+ leadingSpaces = 0;
+ }
+ int len = strlen(buf);
+ int numSpaces = width - len;
+ if (numSpaces <= 0) {
+ printf("%s", buf);
+ return;
+ }
+ if (leadingSpaces == 0)
+ printf("%s", buf);
+ for (ii = 0; ii < numSpaces; ++ii)
+ printf(" ");
+ if (leadingSpaces == 1)
+ printf("%s", buf);
+}
+
+void printClassProfiles(TraceData* traceData, uint64_t sumThreadTime)
+{
+ int ii, jj;
+ MethodEntry* method;
+ double total, sum, per, sum_per;
+ char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
+ char signatureBuf[HTML_BUFSIZE];
+
+ total = sumThreadTime;
+ if (gOptions.outputHtml) {
+ printf("<a name=\"class\"></a>\n");
+ printf("<hr>\n");
+ outputNavigationBar();
+ } else {
+ printf("\n%s\n", profileSeparator);
+ }
+
+ if (traceData->numClasses == 0) {
+ printf("\nNo classes.\n");
+ if (gOptions.outputHtml) {
+ printf("<br><br>\n");
+ }
+ return;
+ }
+
+ printf("\nExclusive elapsed time for each class, summed over all the methods\n");
+ printf("in the class.\n\n");
+ if (gOptions.outputHtml) {
+ printf("<br><br>\n");
+ }
+
+ /* For each class, sum the exclusive times in all of the methods
+ * in that class. Also sum the number of method calls. Also
+ * sort the methods so the most expensive appear at the top.
+ */
+ ClassEntry *pClass = traceData->classes;
+ for (ii = 0; ii < traceData->numClasses; ++ii, ++pClass) {
+ //printf("%s %d methods\n", pClass->className, pClass->numMethods);
+ int numMethods = pClass->numMethods;
+ for (jj = 0; jj < numMethods; ++jj) {
+ method = pClass->methods[jj];
+ pClass->elapsedExclusive += method->elapsedExclusive;
+ pClass->numCalls[0] += method->numCalls[0];
+ pClass->numCalls[1] += method->numCalls[1];
+ }
+
+ /* Sort the methods into decreasing order of exclusive time */
+ qsort(pClass->methods, numMethods, sizeof(MethodEntry*),
+ compareElapsedExclusive);
+ }
+
+ /* Allocate an array of pointers to the classes for more efficient
+ * sorting.
+ */
+ ClassEntry **pClasses;
+ pClasses = (ClassEntry**) malloc(sizeof(ClassEntry*) * traceData->numClasses);
+ for (ii = 0; ii < traceData->numClasses; ++ii)
+ pClasses[ii] = &traceData->classes[ii];
+
+ /* Sort the classes into decreasing order of exclusive time */
+ qsort(pClasses, traceData->numClasses, sizeof(ClassEntry*), compareClassExclusive);
+
+ if (gOptions.outputHtml) {
+ printf("<div class=\"header\"><span class=\"parent\"> </span> ");
+ printf("Cycles %%/total Cumul.%% Calls+Recur Class</div>\n");
+ } else {
+ printf(" Cycles %%/total Cumul.%% Calls+Recur Class\n");
+ }
+
+ sum = 0;
+ for (ii = 0; ii < traceData->numClasses; ++ii) {
+ char *className, *methodName, *signature;
+
+ /* Skip classes with zero cycles */
+ pClass = pClasses[ii];
+ if (pClass->elapsedExclusive == 0)
+ break;
+
+ per = 100.0 * pClass->elapsedExclusive / total;
+ sum += pClass->elapsedExclusive;
+ sum_per = 100.0 * sum / total;
+ className = (char*)(pClass->className);
+ if (gOptions.outputHtml) {
+ char buf[80];
+
+ className = htmlEscape(className, classBuf, HTML_BUFSIZE);
+ printf("<div class=\"link\" onClick=\"javascript:toggle('d%d')\" onMouseOver=\"javascript:onMouseOver(this)\" onMouseOut=\"javascript:onMouseOut(this)\"><span class=\"parent\" id=\"xd%d\">+</span>", ii, ii);
+ sprintf(buf, "%llu", pClass->elapsedExclusive);
+ printHtmlField(buf, 9);
+ printf(" ");
+ sprintf(buf, "%.1f", per);
+ printHtmlField(buf, 7);
+ printf(" ");
+ sprintf(buf, "%.1f", sum_per);
+ printHtmlField(buf, 7);
+ printf(" ");
+ sprintf(buf, "%d", pClass->numCalls[0]);
+ printHtmlField(buf, 6);
+ printf("+");
+ sprintf(buf, "%d", pClass->numCalls[1]);
+ printHtmlField(buf, -6);
+ printf(" ");
+ printf("%s", className);
+ printf("</div>\n");
+ printf("<div class=\"parent\" id=\"d%d\">\n", ii);
+ } else {
+ printf("---------------------------------------------\n");
+ printf("%9llu %7.1f %7.1f %6d+%-6d %s\n",
+ pClass->elapsedExclusive, per, sum_per,
+ pClass->numCalls[0], pClass->numCalls[1],
+ className);
+ }
+
+ int numMethods = pClass->numMethods;
+ double classExclusive = pClass->elapsedExclusive;
+ double sumMethods = 0;
+ for (jj = 0; jj < numMethods; ++jj) {
+ method = pClass->methods[jj];
+ methodName = (char*)(method->methodName);
+ signature = (char*)(method->signature);
+ per = 100.0 * method->elapsedExclusive / classExclusive;
+ sumMethods += method->elapsedExclusive;
+ sum_per = 100.0 * sumMethods / classExclusive;
+ if (gOptions.outputHtml) {
+ char buf[80];
+
+ methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
+ signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
+ printf("<div class=\"leaf\"><span class=\"leaf\"> </span>");
+ sprintf(buf, "%llu", method->elapsedExclusive);
+ printHtmlField(buf, 9);
+ printf(" ");
+ sprintf(buf, "%llu", method->elapsedInclusive);
+ printHtmlField(buf, 9);
+ printf(" ");
+ sprintf(buf, "%.1f", per);
+ printHtmlField(buf, 7);
+ printf(" ");
+ sprintf(buf, "%.1f", sum_per);
+ printHtmlField(buf, 7);
+ printf(" ");
+ sprintf(buf, "%d", method->numCalls[0]);
+ printHtmlField(buf, 6);
+ printf("+");
+ sprintf(buf, "%d", method->numCalls[1]);
+ printHtmlField(buf, -6);
+ printf(" ");
+ printf("<a href=\"#m%d\">[%d]</a> %s %s",
+ method->index, method->index, methodName, signature);
+ printf("</div>\n");
+ } else {
+ printf("%9llu %9llu %7.1f %7.1f %6d+%-6d [%d] %s %s\n",
+ method->elapsedExclusive,
+ method->elapsedInclusive,
+ per, sum_per,
+ method->numCalls[0], method->numCalls[1],
+ method->index, methodName, signature);
+ }
+ }
+ if (gOptions.outputHtml) {
+ printf("</div>\n");
+ }
+ }
+}
+
+void createUniqueMethodList(TraceData* traceData, MethodEntry **pMethods, int numMethods)
+{
+ int ii;
+
+ /* Sort the methods into alphabetical order of method names
+ * to find the unique method names.
+ */
+ qsort(pMethods, numMethods, sizeof(MethodEntry*), compareMethodNames);
+
+ /* Count the number of unique method names, ignoring class and
+ * signature.
+ */
+ const char *currentMethodName = "";
+ traceData->numUniqueMethods = 0;
+ for (ii = 0; ii < numMethods; ++ii) {
+ if (pMethods[ii]->methodName == NULL)
+ continue;
+ if (strcmp(pMethods[ii]->methodName, currentMethodName) != 0) {
+ traceData->numUniqueMethods += 1;
+ currentMethodName = pMethods[ii]->methodName;
+ }
+ }
+ if (traceData->numUniqueMethods == 0)
+ return;
+
+ /* Allocate space for pointers to all of the unique methods */
+ int nbytes = sizeof(UniqueMethodEntry) * traceData->numUniqueMethods;
+ traceData->uniqueMethods = (UniqueMethodEntry *) malloc(nbytes);
+
+ /* Initialize the uniqueMethods array */
+ memset(traceData->uniqueMethods, 0, nbytes);
+ UniqueMethodEntry *pUnique = traceData->uniqueMethods;
+ currentMethodName = NULL;
+ int prevNumMethods = 0;
+ for (ii = 0; ii < numMethods; ++ii) {
+ if (pMethods[ii]->methodName == NULL)
+ continue;
+ if (currentMethodName == NULL)
+ currentMethodName = pMethods[ii]->methodName;
+ if (strcmp(pMethods[ii]->methodName, currentMethodName) != 0) {
+ currentMethodName = pMethods[ii]->methodName;
+ pUnique->numMethods = prevNumMethods;
+ pUnique++;
+ prevNumMethods = 0;
+ }
+ prevNumMethods += 1;
+ }
+ pUnique->numMethods = prevNumMethods;
+
+ /* Create the array of MethodEntry pointers for each unique method */
+ pUnique = NULL;
+ currentMethodName = "";
+ int nextMethod = 0;
+ for (ii = 0; ii < numMethods; ++ii) {
+ if (pMethods[ii]->methodName == NULL)
+ continue;
+ if (strcmp(pMethods[ii]->methodName, currentMethodName) != 0) {
+ currentMethodName = pMethods[ii]->methodName;
+ if (pUnique == NULL)
+ pUnique = traceData->uniqueMethods;
+ else
+ pUnique++;
+ /* Allocate space for the methods array */
+ int nbytes = sizeof(MethodEntry*) * pUnique->numMethods;
+ pUnique->methods = (MethodEntry**) malloc(nbytes);
+ nextMethod = 0;
+ }
+ pUnique->methods[nextMethod++] = pMethods[ii];
+ }
+}
+
+void printMethodProfiles(TraceData* traceData, uint64_t sumThreadTime)
+{
+ int ii, jj;
+ MethodEntry* method;
+ double total, sum, per, sum_per;
+ char classBuf[HTML_BUFSIZE], methodBuf[HTML_BUFSIZE];
+ char signatureBuf[HTML_BUFSIZE];
+
+ if (traceData->numUniqueMethods == 0)
+ return;
+
+ total = sumThreadTime;
+ if (gOptions.outputHtml) {
+ printf("<a name=\"method\"></a>\n");
+ printf("<hr>\n");
+ outputNavigationBar();
+ } else {
+ printf("\n%s\n", profileSeparator);
+ }
+
+ printf("\nExclusive elapsed time for each method, summed over all the classes\n");
+ printf("that contain a method with the same name.\n\n");
+ if (gOptions.outputHtml) {
+ printf("<br><br>\n");
+ }
+
+ /* For each unique method, sum the exclusive times in all of the methods
+ * with the same name. Also sum the number of method calls. Also
+ * sort the methods so the most expensive appear at the top.
+ */
+ UniqueMethodEntry *pUnique = traceData->uniqueMethods;
+ for (ii = 0; ii < traceData->numUniqueMethods; ++ii, ++pUnique) {
+ int numMethods = pUnique->numMethods;
+ for (jj = 0; jj < numMethods; ++jj) {
+ method = pUnique->methods[jj];
+ pUnique->elapsedExclusive += method->elapsedExclusive;
+ pUnique->numCalls[0] += method->numCalls[0];
+ pUnique->numCalls[1] += method->numCalls[1];
+ }
+
+ /* Sort the methods into decreasing order of exclusive time */
+ qsort(pUnique->methods, numMethods, sizeof(MethodEntry*),
+ compareElapsedExclusive);
+ }
+
+ /* Allocate an array of pointers to the methods for more efficient
+ * sorting.
+ */
+ UniqueMethodEntry **pUniqueMethods;
+ int nbytes = sizeof(UniqueMethodEntry*) * traceData->numUniqueMethods;
+ pUniqueMethods = (UniqueMethodEntry**) malloc(nbytes);
+ for (ii = 0; ii < traceData->numUniqueMethods; ++ii)
+ pUniqueMethods[ii] = &traceData->uniqueMethods[ii];
+
+ /* Sort the methods into decreasing order of exclusive time */
+ qsort(pUniqueMethods, traceData->numUniqueMethods, sizeof(UniqueMethodEntry*),
+ compareUniqueExclusive);
+
+ if (gOptions.outputHtml) {
+ printf("<div class=\"header\"><span class=\"parent\"> </span> ");
+ printf("Cycles %%/total Cumul.%% Calls+Recur Method</div>\n");
+ } else {
+ printf(" Cycles %%/total Cumul.%% Calls+Recur Method\n");
+ }
+
+ sum = 0;
+ for (ii = 0; ii < traceData->numUniqueMethods; ++ii) {
+ char *className, *methodName, *signature;
+
+ /* Skip methods with zero cycles */
+ pUnique = pUniqueMethods[ii];
+ if (pUnique->elapsedExclusive == 0)
+ break;
+
+ per = 100.0 * pUnique->elapsedExclusive / total;
+ sum += pUnique->elapsedExclusive;
+ sum_per = 100.0 * sum / total;
+ methodName = (char*)(pUnique->methods[0]->methodName);
+ if (gOptions.outputHtml) {
+ char buf[80];
+
+ methodName = htmlEscape(methodName, methodBuf, HTML_BUFSIZE);
+ printf("<div class=\"link\" onClick=\"javascript:toggle('e%d')\" onMouseOver=\"javascript:onMouseOver(this)\" onMouseOut=\"javascript:onMouseOut(this)\"><span class=\"parent\" id=\"xe%d\">+</span>", ii, ii);
+ sprintf(buf, "%llu", pUnique->elapsedExclusive);
+ printHtmlField(buf, 9);
+ printf(" ");
+ sprintf(buf, "%.1f", per);
+ printHtmlField(buf, 7);
+ printf(" ");
+ sprintf(buf, "%.1f", sum_per);
+ printHtmlField(buf, 7);
+ printf(" ");
+ sprintf(buf, "%d", pUnique->numCalls[0]);
+ printHtmlField(buf, 6);
+ printf("+");
+ sprintf(buf, "%d", pUnique->numCalls[1]);
+ printHtmlField(buf, -6);
+ printf(" ");
+ printf("%s", methodName);
+ printf("</div>\n");
+ printf("<div class=\"parent\" id=\"e%d\">\n", ii);
+ } else {
+ printf("---------------------------------------------\n");
+ printf("%9llu %7.1f %7.1f %6d+%-6d %s\n",
+ pUnique->elapsedExclusive, per, sum_per,
+ pUnique->numCalls[0], pUnique->numCalls[1],
+ methodName);
+ }
+ int numMethods = pUnique->numMethods;
+ double methodExclusive = pUnique->elapsedExclusive;
+ double sumMethods = 0;
+ for (jj = 0; jj < numMethods; ++jj) {
+ method = pUnique->methods[jj];
+ className = (char*)(method->className);
+ signature = (char*)(method->signature);
+ per = 100.0 * method->elapsedExclusive / methodExclusive;
+ sumMethods += method->elapsedExclusive;
+ sum_per = 100.0 * sumMethods / methodExclusive;
+ if (gOptions.outputHtml) {
+ char buf[80];
+
+ className = htmlEscape(className, classBuf, HTML_BUFSIZE);
+ signature = htmlEscape(signature, signatureBuf, HTML_BUFSIZE);
+ printf("<div class=\"leaf\"><span class=\"leaf\"> </span>");
+ sprintf(buf, "%llu", method->elapsedExclusive);
+ printHtmlField(buf, 9);
+ printf(" ");
+ sprintf(buf, "%llu", method->elapsedInclusive);
+ printHtmlField(buf, 9);
+ printf(" ");
+ sprintf(buf, "%.1f", per);
+ printHtmlField(buf, 7);
+ printf(" ");
+ sprintf(buf, "%.1f", sum_per);
+ printHtmlField(buf, 7);
+ printf(" ");
+ sprintf(buf, "%d", method->numCalls[0]);
+ printHtmlField(buf, 6);
+ printf("+");
+ sprintf(buf, "%d", method->numCalls[1]);
+ printHtmlField(buf, -6);
+ printf(" ");
+ printf("<a href=\"#m%d\">[%d]</a> %s.%s %s",
+ method->index, method->index,
+ className, methodName, signature);
+ printf("</div>\n");
+ } else {
+ printf("%9llu %9llu %7.1f %7.1f %6d+%-6d [%d] %s.%s %s\n",
+ method->elapsedExclusive,
+ method->elapsedInclusive,
+ per, sum_per,
+ method->numCalls[0], method->numCalls[1],
+ method->index, className, methodName, signature);
+ }
+ }
+ if (gOptions.outputHtml) {
+ printf("</div>\n");
+ }
+ }
+}
+
+/*
+ * Read the key and data files and return the MethodEntries for those files
+ */
+DataKeys* parseDataKeys(TraceData* traceData, const char* traceFileName, uint64_t* threadTime)
+{
+ DataKeys* dataKeys = NULL;
+ MethodEntry **pMethods = NULL;
+ MethodEntry* method;
+ FILE* dataFp = NULL;
+ DataHeader dataHeader;
+ int ii;
+ uint64_t currentTime;
+ MethodEntry* caller;
+
+ dataFp = fopen(traceFileName, "r");
+ if (dataFp == NULL)
+ goto bail;
+
+ if ((dataKeys = parseKeys(dataFp, 0)) == NULL)
+ goto bail;
+
+ if (parseDataHeader(dataFp, &dataHeader) < 0)
+ goto bail;
+
+#if 0
+ FILE *dumpStream = fopen("debug", "w");
+#endif
+ while (1) {
+ int threadId;
+ unsigned int methodVal;
+ int action;
+ unsigned int methodId;
+ CallStack *pStack;
+ /*
+ * Extract values from file.
+ */
+ if (readDataRecord(dataFp, &threadId, &methodVal, ¤tTime))
+ break;
+
+ action = METHOD_ACTION(methodVal);
+ methodId = METHOD_ID(methodVal);
+
+ /* Get the call stack for this thread */
+ pStack = traceData->stacks[threadId];
+
+ /* If there is no call stack yet for this thread, then allocate one */
+ if (pStack == NULL) {
+ pStack = malloc(sizeof(CallStack));
+ pStack->top = 0;
+ pStack->lastEventTime = currentTime;
+ pStack->threadStartTime = currentTime;
+ traceData->stacks[threadId] = pStack;
+ }
+
+ /* Lookup the current method */
+ method = lookupMethod(dataKeys, methodId);
+ if (method == NULL)
+ method = &dataKeys->methods[UNKNOWN_INDEX];
+
+#if 0
+ if (method->methodName) {
+ fprintf(dumpStream, "%2d %-8llu %d %8llu r %d c %d %s.%s %s\n",
+ threadId, currentTime, action, pStack->threadStartTime,
+ method->recursiveEntries,
+ pStack->top, method->className, method->methodName,
+ method->signature);
+ } else {
+ fprintf(dumpStream, "%2d %-8llu %d %8llu r %d c %d %s\n",
+ threadId, currentTime, action, pStack->threadStartTime,
+ method->recursiveEntries,
+ pStack->top, method->className);
+ }
+#endif
+
+ if (action == METHOD_TRACE_ENTER) {
+ /* This is a method entry */
+ if (pStack->top >= MAX_STACK_DEPTH) {
+ fprintf(stderr, "Stack overflow (exceeded %d frames)\n",
+ MAX_STACK_DEPTH);
+ exit(1);
+ }
+
+ /* Get the caller method */
+ if (pStack->top >= 1)
+ caller = pStack->calls[pStack->top - 1].method;
+ else
+ caller = &dataKeys->methods[TOPLEVEL_INDEX];
+ countRecursiveEntries(pStack, pStack->top, caller);
+ caller->elapsedExclusive += currentTime - pStack->lastEventTime;
+#if 0
+ if (caller->elapsedExclusive > 10000000)
+ fprintf(dumpStream, "%llu current %llu last %llu diff %llu\n",
+ caller->elapsedExclusive, currentTime,
+ pStack->lastEventTime,
+ currentTime - pStack->lastEventTime);
+#endif
+ if (caller->recursiveEntries <= 1) {
+ caller->topExclusive += currentTime - pStack->lastEventTime;
+ }
+
+ /* Push the method on the stack for this thread */
+ pStack->calls[pStack->top].method = method;
+ pStack->calls[pStack->top++].entryTime = currentTime;
+ } else {
+ /* This is a method exit */
+ uint64_t entryTime = 0;
+
+ /* Pop the method off the stack for this thread */
+ if (pStack->top > 0) {
+ pStack->top -= 1;
+ entryTime = pStack->calls[pStack->top].entryTime;
+ if (method != pStack->calls[pStack->top].method) {
+ if (method->methodName) {
+ fprintf(stderr,
+ "Exit from method %s.%s %s does not match stack:\n",
+ method->className, method->methodName,
+ method->signature);
+ } else {
+ fprintf(stderr,
+ "Exit from method %s does not match stack:\n",
+ method->className);
+ }
+ stackDump(pStack, pStack->top + 1);
+ exit(1);
+ }
+ }
+
+ /* Get the caller method */
+ if (pStack->top >= 1)
+ caller = pStack->calls[pStack->top - 1].method;
+ else
+ caller = &dataKeys->methods[TOPLEVEL_INDEX];
+ countRecursiveEntries(pStack, pStack->top, caller);
+ countRecursiveEntries(pStack, pStack->top, method);
+ uint64_t elapsed = currentTime - entryTime;
+ addInclusiveTime(caller, method, elapsed);
+ method->elapsedExclusive += currentTime - pStack->lastEventTime;
+ if (method->recursiveEntries == 0) {
+ method->topExclusive += currentTime - pStack->lastEventTime;
+ }
+ }
+ /* Remember the time of the last entry or exit event */
+ pStack->lastEventTime = currentTime;
+ }
+
+ /* If we have calls on the stack when the trace ends, then clean
+ * up the stack and add time to the callers by pretending that we
+ * are exiting from their methods now.
+ */
+ CallStack *pStack;
+ int threadId;
+ uint64_t sumThreadTime = 0;
+ for (threadId = 0; threadId < MAX_THREADS; ++threadId) {
+ pStack = traceData->stacks[threadId];
+
+ /* If this thread never existed, then continue with next thread */
+ if (pStack == NULL)
+ continue;
+
+ /* Also, add up the time taken by all of the threads */
+ sumThreadTime += pStack->lastEventTime - pStack->threadStartTime;
+
+ for (ii = 0; ii < pStack->top; ++ii) {
+ if (ii == 0)
+ caller = &dataKeys->methods[TOPLEVEL_INDEX];
+ else
+ caller = pStack->calls[ii - 1].method;
+ method = pStack->calls[ii].method;
+ countRecursiveEntries(pStack, ii, caller);
+ countRecursiveEntries(pStack, ii, method);
+
+ uint64_t entryTime = pStack->calls[ii].entryTime;
+ uint64_t elapsed = pStack->lastEventTime - entryTime;
+ addInclusiveTime(caller, method, elapsed);
+ }
+ }
+ caller = &dataKeys->methods[TOPLEVEL_INDEX];
+ caller->elapsedInclusive = sumThreadTime;
+
+#if 0
+ fclose(dumpStream);
+#endif
+
+ if (threadTime != NULL) {
+ *threadTime = sumThreadTime;
+ }
+
+bail:
+ if (dataFp != NULL)
+ fclose(dataFp);
+
+ return dataKeys;
+}
+
+MethodEntry** parseMethodEntries(DataKeys* dataKeys)
+{
+ int ii;
+ /* Create a new array of pointers to the methods and sort the pointers
+ * instead of the actual MethodEntry structs. We need to do this
+ * because there are other lists that contain pointers to the
+ * MethodEntry structs.
+ */
+ MethodEntry** pMethods = (MethodEntry**) malloc(sizeof(MethodEntry*) * dataKeys->numMethods);
+ for (ii = 0; ii < dataKeys->numMethods; ++ii) {
+ MethodEntry* entry = &dataKeys->methods[ii];
+ pMethods[ii] = entry;
+ }
+
+ return pMethods;
+}
+
+/*
+ * Produce a function profile from the following methods
+ */
+void profileTrace(TraceData* traceData, MethodEntry **pMethods, int numMethods, uint64_t sumThreadTime)
+{
+ /* Print the html header, if necessary */
+ if (gOptions.outputHtml) {
+ printf(htmlHeader, gOptions.sortableUrl);
+ outputTableOfContents();
+ }
+
+ printExclusiveProfile(pMethods, numMethods, sumThreadTime);
+ printInclusiveProfile(pMethods, numMethods, sumThreadTime);
+
+ createClassList(traceData, pMethods, numMethods);
+ printClassProfiles(traceData, sumThreadTime);
+
+ createUniqueMethodList(traceData, pMethods, numMethods);
+ printMethodProfiles(traceData, sumThreadTime);
+
+ if (gOptions.outputHtml) {
+ printf("%s", htmlFooter);
+ }
+}
+
+int compareMethodNamesForDiff(const void *a, const void *b)
+{
+ int result;
+
+ const MethodEntry *methodA = *(const MethodEntry**)a;
+ const MethodEntry *methodB = *(const MethodEntry**)b;
+ if (methodA->methodName == NULL || methodB->methodName == NULL) {
+ return compareClassNames(a, b);
+ }
+ result = strcmp(methodA->methodName, methodB->methodName);
+ if (result == 0) {
+ result = strcmp(methodA->signature, methodB->signature);
+ if (result == 0) {
+ return strcmp(methodA->className, methodB->className);
+ }
+ }
+ return result;
+}
+
+int findMatch(MethodEntry** methods, int size, MethodEntry* matchThis)
+{
+ int i;
+
+ for (i = 0 ; i < size ; i++) {
+ MethodEntry* method = methods[i];
+
+ if (method != NULL && !compareMethodNamesForDiff(&method, &matchThis)) {
+// printf("%s.%s == %s.%s<br>\n", matchThis->className, matchThis->methodName,
+ // method->className, method->methodName);
+
+ return i;
+/* if (!compareMethodNames(&method, &matchThis)) {
+ return i;
+ }
+*/ }
+ }
+
+ return -1;
+}
+
+int compareDiffEntriesExculsive(const void *a, const void *b)
+{
+ int result;
+
+ const DiffEntry* entryA = (const DiffEntry*)a;
+ const DiffEntry* entryB = (const DiffEntry*)b;
+
+ if (entryA->differenceExclusive < entryB->differenceExclusive) {
+ return 1;
+ } else if (entryA->differenceExclusive > entryB->differenceExclusive) {
+ return -1;
+ }
+
+ return 0;
+}
+
+int compareDiffEntriesInculsive(const void *a, const void *b)
+{
+ int result;
+
+ const DiffEntry* entryA = (const DiffEntry*)a;
+ const DiffEntry* entryB = (const DiffEntry*)b;
+
+ if (entryA->differenceInclusive < entryB->differenceInclusive) {
+ return 1;
+ } else if (entryA->differenceInclusive > entryB->differenceInclusive) {
+ return -1;
+ }
+
+ return 0;
+}
+
+void printMissingMethod(MethodEntry* method)
+{
+ char classBuf[HTML_BUFSIZE];
+ char methodBuf[HTML_BUFSIZE];
+ char* className;
+ char* methodName;
+
+ className = htmlEscape(method->className, classBuf, HTML_BUFSIZE);
+ methodName = htmlEscape(method->methodName, methodBuf, HTML_BUFSIZE);
+
+ if (gOptions.outputHtml) printf("<tr><td>\n");
+
+ printf("%s.%s ", className, methodName);
+ if (gOptions.outputHtml) printf("</td><td>");
+
+ printf("%lld ", method->elapsedExclusive);
+ if (gOptions.outputHtml) printf("</td><td>");
+
+ printf("%lld ", method->elapsedInclusive);
+ if (gOptions.outputHtml) printf("</td><td>");
+
+ printf("%d\n", method->numCalls[0]);
+ if (gOptions.outputHtml) printf("</td><td>\n");
+}
+
+
+void createDiff(DataKeys* d1, uint64_t sum1, DataKeys* d2, uint64_t sum2)
+{
+ MethodEntry** methods1 = parseMethodEntries(d1);
+ MethodEntry** methods2 = parseMethodEntries(d2);
+
+ // sort and assign the indicies
+ int i;
+ qsort(methods1, d1->numMethods, sizeof(MethodEntry*), compareElapsedInclusive);
+ for (i = 0; i < d1->numMethods; ++i) {
+ methods1[i]->index = i;
+ }
+
+ qsort(methods2, d2->numMethods, sizeof(MethodEntry*), compareElapsedInclusive);
+ for (i = 0; i < d2->numMethods; ++i) {
+ methods2[i]->index = i;
+ }
+
+ int max = (d1->numMethods < d2->numMethods) ? d2->numMethods : d1->numMethods;
+ max++;
+ DiffEntry* diffs = (DiffEntry*)malloc(max * sizeof(DiffEntry));
+ memset(diffs, 0, max * sizeof(DiffEntry));
+ DiffEntry* ptr = diffs;
+
+// printf("<br>d1->numMethods: %d d1->numMethods: %d<br>\n", d1->numMethods, d2->numMethods);
+
+ int matches = 0;
+
+ for (i = 0 ; i < d1->numMethods ; i++) {
+ int match = findMatch(methods2, d2->numMethods, methods1[i]);
+ if (match >= 0) {
+ ptr->method1 = methods1[i];
+ ptr->method2 = methods2[match];
+
+ uint64_t e1 = ptr->method1->elapsedExclusive;
+ uint64_t e2 = ptr->method2->elapsedExclusive;
+ if (e1 > 0) {
+ ptr->differenceExclusive = e2 - e1;
+ ptr->differenceExclusivePercentage = ((double)e2 / (double)e1) * 100.0;
+ }
+
+ uint64_t i1 = ptr->method1->elapsedInclusive;
+ uint64_t i2 = ptr->method2->elapsedInclusive;
+ if (i1 > 0) {
+ ptr->differenceInclusive = i2 - i1;
+ ptr->differenceInclusivePercentage = ((double)i2 / (double)i1) * 100.0;
+ }
+
+ // clear these out so we don't find them again and we know which ones
+ // we have left over
+ methods1[i] = NULL;
+ methods2[match] = NULL;
+ ptr++;
+
+ matches++;
+ }
+ }
+ ptr->method1 = NULL;
+ ptr->method2 = NULL;
+
+ qsort(diffs, matches, sizeof(DiffEntry), compareDiffEntriesExculsive);
+ ptr = diffs;
+
+ if (gOptions.outputHtml) {
+ printf(htmlHeader, gOptions.sortableUrl);
+ printf("<h3>Table of Contents</h3>\n");
+ printf("<ul>\n");
+ printf("<li><a href='#exclusive'>Exclusive</a>\n");
+ printf("<li><a href='#inclusive'>Inclusive</a>\n");
+ printf("</ul>\n");
+ printf("Run 1: %s<br>\n", gOptions.diffFileName);
+ printf("Run 2: %s<br>\n", gOptions.traceFileName);
+ printf("<a name=\"exclusive\"></a><h3 id=\"exclusive\">Exclusive</h3>\n");
+ printf(tableHeader, "exclusive_table");
+ }
+
+ char classBuf[HTML_BUFSIZE];
+ char methodBuf[HTML_BUFSIZE];
+ char* className;
+ char* methodName;
+
+ while (ptr->method1 != NULL && ptr->method2 != NULL) {
+ if (gOptions.outputHtml) printf("<tr><td>\n");
+
+ className = htmlEscape(ptr->method1->className, classBuf, HTML_BUFSIZE);
+ methodName = htmlEscape(ptr->method1->methodName, methodBuf, HTML_BUFSIZE);
+
+ printf("%s.%s ", className, methodName);
+ if (gOptions.outputHtml) printf("</td><td>");
+
+ printf("%lld ", ptr->method1->elapsedExclusive);
+ if (gOptions.outputHtml) printf("</td><td>");
+
+ printf("%llu ", ptr->method2->elapsedExclusive);
+ if (gOptions.outputHtml) printf("</td><td>");
+
+ printf("%lld ", ptr->differenceExclusive);
+ if (gOptions.outputHtml) printf("</td><td>");
+
+ printf("%.2f\n", ptr->differenceExclusivePercentage);
+ if (gOptions.outputHtml) printf("</td><td>\n");
+
+ printf("%d\n", ptr->method1->numCalls[0]);
+ if (gOptions.outputHtml) printf("</td><td>\n");
+
+ printf("%d\n", ptr->method2->numCalls[0]);
+ if (gOptions.outputHtml) printf("</td></tr>\n");
+
+ ptr++;
+ }
+
+ if (gOptions.outputHtml) printf("</table>\n");
+
+ if (gOptions.outputHtml) {
+ printf(htmlHeader, gOptions.sortableUrl);
+ printf("Run 1: %s<br>\n", gOptions.diffFileName);
+ printf("Run 2: %s<br>\n", gOptions.traceFileName);
+ printf("<a name=\"inclusive\"></a><h3 id=\"inculisve\">Inclusive</h3>\n");
+ printf(tableHeader, "inclusive_table");
+ }
+
+ qsort(diffs, matches, sizeof(DiffEntry), compareDiffEntriesInculsive);
+ ptr = diffs;
+
+ while (ptr->method1 != NULL && ptr->method2 != NULL) {
+ if (gOptions.outputHtml) printf("<tr><td>\n");
+
+ className = htmlEscape(ptr->method1->className, classBuf, HTML_BUFSIZE);
+ methodName = htmlEscape(ptr->method1->methodName, methodBuf, HTML_BUFSIZE);
+
+ printf("%s.%s ", className, methodName);
+ if (gOptions.outputHtml) printf("</td><td>");
+
+ printf("%lld ", ptr->method1->elapsedInclusive);
+ if (gOptions.outputHtml) printf("</td><td>");
+
+ printf("%llu ", ptr->method2->elapsedInclusive);
+ if (gOptions.outputHtml) printf("</td><td>");
+
+ printf("%lld ", ptr->differenceInclusive);
+ if (gOptions.outputHtml) printf("</td><td>");
+
+ printf("%.2f\n", ptr->differenceInclusivePercentage);
+ if (gOptions.outputHtml) printf("</td><td>\n");
+
+ printf("%d\n", ptr->method1->numCalls[0]);
+ if (gOptions.outputHtml) printf("</td><td>\n");
+
+ printf("%d\n", ptr->method2->numCalls[0]);
+ if (gOptions.outputHtml) printf("</td></tr>\n");
+
+ ptr++;
+ }
+
+ if (gOptions.outputHtml) {
+ printf("</table>\n");
+ printf("<h3>Run 1 methods not found in Run 2</h3>");
+ printf(tableHeaderMissing);
+ }
+
+ for (i = 0; i < d1->numMethods; ++i) {
+ if (methods1[i] != NULL) {
+ printMissingMethod(methods1[i]);
+ }
+ }
+
+ if (gOptions.outputHtml) {
+ printf("</table>\n");
+ printf("<h3>Run 2 methods not found in Run 1</h3>");
+ printf(tableHeaderMissing);
+ }
+
+ for (i = 0; i < d2->numMethods; ++i) {
+ if (methods2[i] != NULL) {
+ printMissingMethod(methods2[i]);
+ }
+ }
+
+ if (gOptions.outputHtml) printf("</body></html\n");
+}
+
+int usage(const char *program)
+{
+ fprintf(stderr, "usage: %s [-ho] [-s sortable] [-d trace-file-name] [-g outfile] trace-file-name\n", program);
+ fprintf(stderr, " -d trace-file-name - Diff with this trace\n");
+ fprintf(stderr, " -g outfile - Write graph to 'outfile'\n");
+ fprintf(stderr, " -k - When writing a graph, keep the intermediate DOT file\n");
+ fprintf(stderr, " -h - Turn on HTML output\n");
+ fprintf(stderr, " -o - Dump the dmtrace file instead of profiling\n");
+ fprintf(stderr, " -s - URL base to where the sortable javascript file\n");
+ fprintf(stderr, " -t threshold - Threshold percentage for including nodes in the graph\n");
+ return 2;
+}
+
+// Returns true if there was an error
+int parseOptions(int argc, char **argv)
+{
+ while (1) {
+ int opt = getopt(argc, argv, "d:hg:kos:t:");
+ if (opt == -1)
+ break;
+ switch (opt) {
+ case 'd':
+ gOptions.diffFileName = optarg;
+ break;
+ case 'g':
+ gOptions.graphFileName = optarg;
+ break;
+ case 'k':
+ gOptions.keepDotFile = 1;
+ break;
+ case 'h':
+ gOptions.outputHtml = 1;
+ break;
+ case 'o':
+ gOptions.dump = 1;
+ break;
+ case 's':
+ gOptions.sortableUrl = optarg;
+ break;
+ case 't':
+ gOptions.threshold = atoi(optarg);
+ break;
+ default:
+ return 1;
+ }
+ }
+ return 0;
+}
+
+/*
+ * Parse args.
+ */
+int main(int argc, char** argv)
+{
+ gOptions.threshold = -1;
+
+ // Parse the options
+ if (parseOptions(argc, argv) || argc - optind != 1)
+ return usage(argv[0]);
+
+ gOptions.traceFileName = argv[optind];
+
+ if (gOptions.threshold < 0 || 100 <= gOptions.threshold) {
+ gOptions.threshold = 20;
+ }
+
+ if (gOptions.dump) {
+ dumpTrace();
+ return 0;
+ }
+
+ uint64_t sumThreadTime = 0;
+
+ TraceData data1;
+ DataKeys* dataKeys = parseDataKeys(&data1, gOptions.traceFileName,
+ &sumThreadTime);
+ if (dataKeys == NULL) {
+ fprintf(stderr, "Cannot read trace.\n");
+ exit(1);
+ }
+
+ if (gOptions.diffFileName != NULL) {
+ uint64_t sum2;
+ TraceData data2;
+ DataKeys* d2 = parseDataKeys(&data2, gOptions.diffFileName, &sum2);
+
+ createDiff(d2, sum2, dataKeys, sumThreadTime);
+
+ freeDataKeys(d2);
+ } else {
+ MethodEntry** methods = parseMethodEntries(dataKeys);
+ profileTrace(&data1, methods, dataKeys->numMethods, sumThreadTime);
+ if (gOptions.graphFileName != NULL) {
+ createInclusiveProfileGraphNew(dataKeys);
+ }
+ free(methods);
+ }
+
+ freeDataKeys(dataKeys);
+
+ return 0;
+}
diff --git a/tools/dmtracedump/dmtracedump.pl b/tools/dmtracedump/dmtracedump.pl
new file mode 100755
index 0000000..fbd00ac
--- /dev/null
+++ b/tools/dmtracedump/dmtracedump.pl
@@ -0,0 +1,20 @@
+#!/usr/bin/perl
+
+opendir(DIR, ".") || die "can't opendir $some_dir: $!";
+@traces = grep { /.*\.dmtrace\.data/ } readdir(DIR);
+
+foreach (@traces)
+{
+ $input = $_;
+ $input =~ s/\.data$//;
+
+ $output = "$input.html";
+
+ print("dmtracedump -h -p $input > $output\n");
+ system("dmtracedump -h -p '$input' > '$output'");
+
+}
+
+closedir DIR;
+
+
diff --git a/tools/dmtracedump/dumpdir.sh b/tools/dmtracedump/dumpdir.sh
new file mode 100644
index 0000000..34937d7
--- /dev/null
+++ b/tools/dmtracedump/dumpdir.sh
@@ -0,0 +1,12 @@
+#!/bin/bash
+
+FILES=`ls $1/*.data | sed "s/^\\(.*\\).data$/\\1/"`
+
+mkdir -p $2
+
+for F in $FILES
+do
+ G=$2/`echo $F | sed "s/.*\\///g"`.html
+ dmtracedump -h -p $F > $G
+done
+
diff --git a/tools/get-hprof b/tools/get-hprof
new file mode 100755
index 0000000..d56d7ad
--- /dev/null
+++ b/tools/get-hprof
@@ -0,0 +1,41 @@
+#!/bin/sh
+#
+# Copyright (C) 2007 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Grab an hprof file using adb. If an argument is specified, grab
+# the so-named file. If no argument is specified, grab the last such file
+# as found by using "ls".
+
+FILE_BASE="$1"
+if [ "x$FILE_BASE" = "x" ]; then
+ # Note: substr() is to get rid of the final carriage return.
+ FILE_BASE=`adb shell ls -l '/data/misc/heap-dump*.hprof' | tail -1 | \
+ awk '{ printf("%s", substr($7, 1, length($7) - 1)); }'`
+ if [ "x$FILE_BASE" = "x" ]; then
+ echo "No file base defined."
+ exit 1
+ fi
+fi
+
+FILE_BASE=/data/misc/${FILE_BASE}
+OUT_FILE=heap-dump.hprof
+
+adb pull "$FILE_BASE" "$OUT_FILE"
+if [ $? -ne 0 ]; then
+ echo "Failed pulling $FILE_BASE."
+ exit 1
+fi
+echo "hat $OUT_FILE"
+exit 0
diff --git a/tools/hprof-conv/Android.mk b/tools/hprof-conv/Android.mk
new file mode 100644
index 0000000..fbac5fa
--- /dev/null
+++ b/tools/hprof-conv/Android.mk
@@ -0,0 +1,21 @@
+# Copyright (C) 2009 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+LOCAL_PATH:= $(call my-dir)
+
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := HprofConv.c
+LOCAL_MODULE := hprof-conv
+include $(BUILD_HOST_EXECUTABLE)
+
diff --git a/tools/hprof-conv/HprofConv.c b/tools/hprof-conv/HprofConv.c
new file mode 100644
index 0000000..10f3d2c
--- /dev/null
+++ b/tools/hprof-conv/HprofConv.c
@@ -0,0 +1,719 @@
+/*
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/*
+ * Strip Android-specific records out of hprof data, back-converting from
+ * 1.0.3 to 1.0.2. This removes some useful information, but allows
+ * Android hprof data to be handled by widely-available tools (like "jhat").
+ */
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <errno.h>
+#include <assert.h>
+
+//#define VERBOSE_DEBUG
+#ifdef VERBOSE_DEBUG
+# define DBUG(...) fprintf(stderr, __VA_ARGS__)
+#else
+# define DBUG(...)
+#endif
+
+#ifndef FALSE
+# define FALSE 0
+# define TRUE (!FALSE)
+#endif
+
+typedef enum HprofBasicType {
+ HPROF_BASIC_OBJECT = 2,
+ HPROF_BASIC_BOOLEAN = 4,
+ HPROF_BASIC_CHAR = 5,
+ HPROF_BASIC_FLOAT = 6,
+ HPROF_BASIC_DOUBLE = 7,
+ HPROF_BASIC_BYTE = 8,
+ HPROF_BASIC_SHORT = 9,
+ HPROF_BASIC_INT = 10,
+ HPROF_BASIC_LONG = 11,
+} HprofBasicType;
+
+typedef enum HprofTag {
+ /* tags we must handle specially */
+ HPROF_TAG_HEAP_DUMP = 0x0c,
+ HPROF_TAG_HEAP_DUMP_SEGMENT = 0x1c,
+} HprofTag;
+
+typedef enum HprofHeapTag {
+ /* 1.0.2 tags */
+ HPROF_ROOT_UNKNOWN = 0xff,
+ HPROF_ROOT_JNI_GLOBAL = 0x01,
+ HPROF_ROOT_JNI_LOCAL = 0x02,
+ HPROF_ROOT_JAVA_FRAME = 0x03,
+ HPROF_ROOT_NATIVE_STACK = 0x04,
+ HPROF_ROOT_STICKY_CLASS = 0x05,
+ HPROF_ROOT_THREAD_BLOCK = 0x06,
+ HPROF_ROOT_MONITOR_USED = 0x07,
+ HPROF_ROOT_THREAD_OBJECT = 0x08,
+ HPROF_CLASS_DUMP = 0x20,
+ HPROF_INSTANCE_DUMP = 0x21,
+ HPROF_OBJECT_ARRAY_DUMP = 0x22,
+ HPROF_PRIMITIVE_ARRAY_DUMP = 0x23,
+
+ /* Android 1.0.3 tags */
+ HPROF_HEAP_DUMP_INFO = 0xfe,
+ HPROF_ROOT_INTERNED_STRING = 0x89,
+ HPROF_ROOT_FINALIZING = 0x8a,
+ HPROF_ROOT_DEBUGGER = 0x8b,
+ HPROF_ROOT_REFERENCE_CLEANUP = 0x8c,
+ HPROF_ROOT_VM_INTERNAL = 0x8d,
+ HPROF_ROOT_JNI_MONITOR = 0x8e,
+ HPROF_UNREACHABLE = 0x90,
+ HPROF_PRIMITIVE_ARRAY_NODATA_DUMP = 0xc3,
+} HprofHeapTag;
+
+#define kIdentSize 4
+#define kRecHdrLen 9
+
+
+/*
+ * ===========================================================================
+ * Expanding buffer
+ * ===========================================================================
+ */
+
+/* simple struct */
+typedef struct {
+ unsigned char* storage;
+ size_t curLen;
+ size_t maxLen;
+} ExpandBuf;
+
+/*
+ * Create an ExpandBuf.
+ */
+static ExpandBuf* ebAlloc(void)
+{
+ static const int kInitialSize = 64;
+
+ ExpandBuf* newBuf = (ExpandBuf*) malloc(sizeof(ExpandBuf));
+ if (newBuf == NULL)
+ return NULL;
+ newBuf->storage = (unsigned char*) malloc(kInitialSize);
+ newBuf->curLen = 0;
+ newBuf->maxLen = kInitialSize;
+
+ return newBuf;
+}
+
+/*
+ * Release the storage associated with an ExpandBuf.
+ */
+static void ebFree(ExpandBuf* pBuf)
+{
+ if (pBuf != NULL) {
+ free(pBuf->storage);
+ free(pBuf);
+ }
+}
+
+/*
+ * Return a pointer to the data buffer.
+ *
+ * The pointer may change as data is added to the buffer, so this value
+ * should not be cached.
+ */
+static inline unsigned char* ebGetBuffer(ExpandBuf* pBuf)
+{
+ return pBuf->storage;
+}
+
+/*
+ * Get the amount of data currently in the buffer.
+ */
+static inline size_t ebGetLength(ExpandBuf* pBuf)
+{
+ return pBuf->curLen;
+}
+
+/*
+ * Empty the buffer.
+ */
+static void ebClear(ExpandBuf* pBuf)
+{
+ pBuf->curLen = 0;
+}
+
+/*
+ * Ensure that the buffer can hold at least "size" additional bytes.
+ */
+static int ebEnsureCapacity(ExpandBuf* pBuf, int size)
+{
+ assert(size > 0);
+
+ if (pBuf->curLen + size > pBuf->maxLen) {
+ int newSize = pBuf->curLen + size + 128; /* oversize slightly */
+ unsigned char* newStorage = realloc(pBuf->storage, newSize);
+ if (newStorage == NULL) {
+ fprintf(stderr, "ERROR: realloc failed on size=%d\n", newSize);
+ return -1;
+ }
+
+ pBuf->storage = newStorage;
+ pBuf->maxLen = newSize;
+ }
+
+ assert(pBuf->curLen + size <= pBuf->maxLen);
+ return 0;
+}
+
+/*
+ * Add data to the buffer after ensuring it can hold it.
+ */
+static int ebAddData(ExpandBuf* pBuf, const void* data, size_t count)
+{
+ ebEnsureCapacity(pBuf, count);
+ memcpy(pBuf->storage + pBuf->curLen, data, count);
+ pBuf->curLen += count;
+ return 0;
+}
+
+/*
+ * Read a NULL-terminated string from the input.
+ */
+static int ebReadString(ExpandBuf* pBuf, FILE* in)
+{
+ int ic;
+
+ do {
+ ebEnsureCapacity(pBuf, 1);
+
+ ic = getc(in);
+ if (feof(in) || ferror(in)) {
+ fprintf(stderr, "ERROR: failed reading input\n");
+ return -1;
+ }
+
+ pBuf->storage[pBuf->curLen++] = (unsigned char) ic;
+ } while (ic != 0);
+
+ return 0;
+}
+
+/*
+ * Read some data, adding it to the expanding buffer.
+ *
+ * This will ensure that the buffer has enough space to hold the new data
+ * (plus the previous contents).
+ */
+static int ebReadData(ExpandBuf* pBuf, FILE* in, size_t count, int eofExpected)
+{
+ size_t actual;
+
+ assert(count > 0);
+
+ ebEnsureCapacity(pBuf, count);
+ actual = fread(pBuf->storage + pBuf->curLen, 1, count, in);
+ if (actual != count) {
+ if (eofExpected && feof(in) && !ferror(in)) {
+ /* return without reporting an error */
+ } else {
+ fprintf(stderr, "ERROR: read %d of %d bytes\n", actual, count);
+ return -1;
+ }
+ }
+
+ pBuf->curLen += count;
+ assert(pBuf->curLen <= pBuf->maxLen);
+
+ return 0;
+}
+
+/*
+ * Write the data from the buffer. Resets the data count to zero.
+ */
+static int ebWriteData(ExpandBuf* pBuf, FILE* out)
+{
+ size_t actual;
+
+ assert(pBuf->curLen > 0);
+ assert(pBuf->curLen <= pBuf->maxLen);
+
+ actual = fwrite(pBuf->storage, 1, pBuf->curLen, out);
+ if (actual != pBuf->curLen) {
+ fprintf(stderr, "ERROR: write %d of %d bytes\n", actual, pBuf->curLen);
+ return -1;
+ }
+
+ pBuf->curLen = 0;
+
+ return 0;
+}
+
+
+/*
+ * ===========================================================================
+ * Hprof stuff
+ * ===========================================================================
+ */
+
+/*
+ * Get a 2-byte value, in big-endian order, from memory.
+ */
+static uint16_t get2BE(const unsigned char* buf)
+{
+ uint16_t val;
+
+ val = (buf[0] << 8) | buf[1];
+ return val;
+}
+
+/*
+ * Get a 4-byte value, in big-endian order, from memory.
+ */
+static uint32_t get4BE(const unsigned char* buf)
+{
+ uint32_t val;
+
+ val = (buf[0] << 24) | (buf[1] << 16) | (buf[2] << 8) | buf[3];
+ return val;
+}
+
+/*
+ * Set a 4-byte value, in big-endian order.
+ */
+static void set4BE(unsigned char* buf, uint32_t val)
+{
+ buf[0] = val >> 24;
+ buf[1] = val >> 16;
+ buf[2] = val >> 8;
+ buf[3] = val;
+}
+
+/*
+ * Get the size, in bytes, of one of the "basic types".
+ */
+static int computeBasicLen(HprofBasicType basicType)
+{
+ static const int sizes[] = { -1, -1, 4, -1, 1, 2, 4, 8, 1, 2, 4, 8 };
+ static const size_t maxSize = sizeof(sizes) / sizeof(sizes[0]);
+
+ assert(basicType >= 0);
+ if (basicType >= maxSize)
+ return -1;
+ return sizes[basicType];
+}
+
+/*
+ * Compute the length of a HPROF_CLASS_DUMP block.
+ */
+static int computeClassDumpLen(const unsigned char* origBuf, int len)
+{
+ const unsigned char* buf = origBuf;
+ int blockLen = 0;
+ int i, count;
+
+ blockLen += kIdentSize * 7 + 8;
+ buf += blockLen;
+ len -= blockLen;
+
+ if (len < 0)
+ return -1;
+
+ count = get2BE(buf);
+ buf += 2;
+ len -= 2;
+ DBUG("CDL: 1st count is %d\n", count);
+ for (i = 0; i < count; i++) {
+ HprofBasicType basicType;
+ int basicLen;
+
+ basicType = buf[2];
+ basicLen = computeBasicLen(basicType);
+ if (basicLen < 0) {
+ DBUG("ERROR: invalid basicType %d\n", basicType);
+ return -1;
+ }
+
+ buf += 2 + 1 + basicLen;
+ len -= 2 + 1 + basicLen;
+ if (len < 0)
+ return -1;
+ }
+
+ count = get2BE(buf);
+ buf += 2;
+ len -= 2;
+ DBUG("CDL: 2nd count is %d\n", count);
+ for (i = 0; i < count; i++) {
+ HprofBasicType basicType;
+ int basicLen;
+
+ basicType = buf[kIdentSize];
+ basicLen = computeBasicLen(basicType);
+ if (basicLen < 0) {
+ fprintf(stderr, "ERROR: invalid basicType %d\n", basicType);
+ return -1;
+ }
+
+ buf += kIdentSize + 1 + basicLen;
+ len -= kIdentSize + 1 + basicLen;
+ if (len < 0)
+ return -1;
+ }
+
+ count = get2BE(buf);
+ buf += 2;
+ len -= 2;
+ DBUG("CDL: 3rd count is %d\n", count);
+ for (i = 0; i < count; i++) {
+ buf += kIdentSize + 1;
+ len -= kIdentSize + 1;
+ if (len < 0)
+ return -1;
+ }
+
+ DBUG("Total class dump len: %d\n", buf - origBuf);
+ return buf - origBuf;
+}
+
+/*
+ * Compute the length of a HPROF_INSTANCE_DUMP block.
+ */
+static int computeInstanceDumpLen(const unsigned char* origBuf, int len)
+{
+ int extraCount = get4BE(origBuf + kIdentSize * 2 + 4);
+ return kIdentSize * 2 + 8 + extraCount;
+}
+
+/*
+ * Compute the length of a HPROF_OBJECT_ARRAY_DUMP block.
+ */
+static int computeObjectArrayDumpLen(const unsigned char* origBuf, int len)
+{
+ int arrayCount = get4BE(origBuf + kIdentSize + 4);
+ return kIdentSize * 2 + 8 + arrayCount * kIdentSize;
+}
+
+/*
+ * Compute the length of a HPROF_PRIMITIVE_ARRAY_DUMP block.
+ */
+static int computePrimitiveArrayDumpLen(const unsigned char* origBuf, int len)
+{
+ int arrayCount = get4BE(origBuf + kIdentSize + 4);
+ HprofBasicType basicType = origBuf[kIdentSize + 8];
+ int basicLen = computeBasicLen(basicType);
+
+ return kIdentSize + 9 + arrayCount * basicLen;
+}
+
+/*
+ * Crunch through a heap dump record, writing the original or converted
+ * data to "out".
+ */
+static int processHeapDump(ExpandBuf* pBuf, FILE* out)
+{
+ ExpandBuf* pOutBuf = ebAlloc();
+ unsigned char* origBuf = ebGetBuffer(pBuf);
+ unsigned char* buf = origBuf;
+ int len = ebGetLength(pBuf);
+ int result = -1;
+
+ pBuf = NULL; /* we just use the raw pointer from here forward */
+
+ /* copy the original header to the output buffer */
+ if (ebAddData(pOutBuf, buf, kRecHdrLen) != 0)
+ goto bail;
+
+ buf += kRecHdrLen; /* skip past record header */
+ len -= kRecHdrLen;
+
+ while (len > 0) {
+ unsigned char subType = buf[0];
+ int justCopy = TRUE;
+ int subLen;
+
+ DBUG("--- 0x%02x ", subType);
+ switch (subType) {
+ /* 1.0.2 types */
+ case HPROF_ROOT_UNKNOWN:
+ subLen = kIdentSize;
+ break;
+ case HPROF_ROOT_JNI_GLOBAL:
+ subLen = kIdentSize * 2;
+ break;
+ case HPROF_ROOT_JNI_LOCAL:
+ subLen = kIdentSize + 8;
+ break;
+ case HPROF_ROOT_JAVA_FRAME:
+ subLen = kIdentSize + 8;
+ break;
+ case HPROF_ROOT_NATIVE_STACK:
+ subLen = kIdentSize + 4;
+ break;
+ case HPROF_ROOT_STICKY_CLASS:
+ subLen = kIdentSize;
+ break;
+ case HPROF_ROOT_THREAD_BLOCK:
+ subLen = kIdentSize + 4;
+ break;
+ case HPROF_ROOT_MONITOR_USED:
+ subLen = kIdentSize;
+ break;
+ case HPROF_ROOT_THREAD_OBJECT:
+ subLen = kIdentSize + 8;
+ break;
+ case HPROF_CLASS_DUMP:
+ subLen = computeClassDumpLen(buf+1, len-1);
+ break;
+ case HPROF_INSTANCE_DUMP:
+ subLen = computeInstanceDumpLen(buf+1, len-1);
+ break;
+ case HPROF_OBJECT_ARRAY_DUMP:
+ subLen = computeObjectArrayDumpLen(buf+1, len-1);
+ break;
+ case HPROF_PRIMITIVE_ARRAY_DUMP:
+ subLen = computePrimitiveArrayDumpLen(buf+1, len-1);
+ break;
+
+ /* these were added for Android in 1.0.3 */
+ case HPROF_HEAP_DUMP_INFO:
+ justCopy = FALSE;
+ subLen = kIdentSize + 4;
+ // no 1.0.2 equivalent for this
+ break;
+ case HPROF_ROOT_INTERNED_STRING:
+ buf[0] = HPROF_ROOT_UNKNOWN;
+ subLen = kIdentSize;
+ break;
+ case HPROF_ROOT_FINALIZING:
+ buf[0] = HPROF_ROOT_UNKNOWN;
+ subLen = kIdentSize;
+ break;
+ case HPROF_ROOT_DEBUGGER:
+ buf[0] = HPROF_ROOT_UNKNOWN;
+ subLen = kIdentSize;
+ break;
+ case HPROF_ROOT_REFERENCE_CLEANUP:
+ buf[0] = HPROF_ROOT_UNKNOWN;
+ subLen = kIdentSize;
+ break;
+ case HPROF_ROOT_VM_INTERNAL:
+ buf[0] = HPROF_ROOT_UNKNOWN;
+ subLen = kIdentSize;
+ break;
+ case HPROF_ROOT_JNI_MONITOR:
+ /* keep the ident, drop the next 8 bytes */
+ buf[0] = HPROF_ROOT_UNKNOWN;
+ justCopy = FALSE;
+ ebAddData(pOutBuf, buf, 1 + kIdentSize);
+ subLen = kIdentSize + 8;
+ break;
+ case HPROF_UNREACHABLE:
+ buf[0] = HPROF_ROOT_UNKNOWN;
+ subLen = kIdentSize;
+ break;
+ case HPROF_PRIMITIVE_ARRAY_NODATA_DUMP:
+ buf[0] = HPROF_PRIMITIVE_ARRAY_DUMP;
+ buf[5] = buf[6] = buf[7] = buf[8] = 0; /* set array len to 0 */
+ subLen = kIdentSize + 9;
+ break;
+
+ /* shouldn't get here */
+ default:
+ fprintf(stderr, "ERROR: unexpected subtype 0x%02x at offset %d\n",
+ subType, buf - origBuf);
+ goto bail;
+ }
+
+ if (justCopy) {
+ /* copy source data */
+ DBUG("(%d)\n", 1 + subLen);
+ ebAddData(pOutBuf, buf, 1 + subLen);
+ } else {
+ /* other data has been written, or the sub-record omitted */
+ DBUG("(adv %d)\n", 1 + subLen);
+ }
+
+ /* advance to next entry */
+ buf += 1 + subLen;
+ len -= 1 + subLen;
+ }
+
+ /*
+ * Update the record length.
+ */
+ set4BE(ebGetBuffer(pOutBuf) + 5, ebGetLength(pOutBuf) - kRecHdrLen);
+
+ if (ebWriteData(pOutBuf, out) != 0)
+ goto bail;
+
+ result = 0;
+
+bail:
+ ebFree(pOutBuf);
+ return result;
+}
+
+/*
+ * Filter an hprof data file.
+ */
+static int filterData(FILE* in, FILE* out)
+{
+ ExpandBuf* pBuf;
+ int result = -1;
+
+ pBuf = ebAlloc();
+ if (pBuf == NULL)
+ goto bail;
+
+ /*
+ * Start with the header.
+ */
+ if (ebReadString(pBuf, in) != 0)
+ goto bail;
+
+ if (strcmp((const char*)ebGetBuffer(pBuf), "JAVA PROFILE 1.0.3") != 0) {
+ fprintf(stderr, "ERROR: expecting 1.0.3\n");
+ goto bail;
+ }
+
+ /* downgrade to 1.0.2 */
+ (ebGetBuffer(pBuf))[17] = '2';
+ if (ebWriteData(pBuf, out) != 0)
+ goto bail;
+
+ /*
+ * Copy:
+ * (4b) identifier size, always 4
+ * (8b) file creation date
+ */
+ if (ebReadData(pBuf, in, 12, FALSE) != 0)
+ goto bail;
+ if (ebWriteData(pBuf, out) != 0)
+ goto bail;
+
+ /*
+ * Read records until we hit EOF. Each record begins with:
+ * (1b) type
+ * (4b) timestamp
+ * (4b) length of data that follows
+ */
+ while (1) {
+ assert(ebGetLength(pBuf) == 0);
+
+ /* read type char */
+ if (ebReadData(pBuf, in, 1, TRUE) != 0)
+ goto bail;
+ if (feof(in))
+ break;
+
+ /* read the rest of the header */
+ if (ebReadData(pBuf, in, kRecHdrLen-1, FALSE) != 0)
+ goto bail;
+
+ unsigned char* buf = ebGetBuffer(pBuf);
+ unsigned char type;
+ unsigned int timestamp, length;
+
+ type = buf[0];
+ timestamp = get4BE(buf + 1);
+ length = get4BE(buf + 5);
+ buf = NULL; /* ptr invalid after next read op */
+
+ /* read the record data */
+ if (length != 0) {
+ if (ebReadData(pBuf, in, length, FALSE) != 0)
+ goto bail;
+ }
+
+ if (type == HPROF_TAG_HEAP_DUMP ||
+ type == HPROF_TAG_HEAP_DUMP_SEGMENT)
+ {
+ DBUG("Processing heap dump 0x%02x (%d bytes)\n",
+ type, length);
+ if (processHeapDump(pBuf, out) != 0)
+ goto bail;
+ ebClear(pBuf);
+ } else {
+ /* keep */
+ DBUG("Keeping 0x%02x (%d bytes)\n", type, length);
+ if (ebWriteData(pBuf, out) != 0)
+ goto bail;
+ }
+ }
+
+ result = 0;
+
+bail:
+ ebFree(pBuf);
+ return result;
+}
+
+/*
+ * Get args.
+ */
+int main(int argc, char** argv)
+{
+ FILE* in = stdin;
+ FILE* out = stdout;
+ int cc;
+
+ if (argc != 3) {
+ fprintf(stderr, "Usage: hprof-conf infile outfile\n\n");
+ fprintf(stderr,
+ "Specify '-' for either or both to use stdin/stdout.\n\n");
+
+ fprintf(stderr,
+ "Copyright (C) 2009 The Android Open Source Project\n\n"
+ "This software is built from source code licensed under the "
+ "Apache License,\n"
+ "Version 2.0 (the \"License\"). You may obtain a copy of the "
+ "License at\n\n"
+ " http://www.apache.org/licenses/LICENSE-2.0\n\n"
+ "See the associated NOTICE file for this software for further "
+ "details.\n");
+
+ return 2;
+ }
+
+ if (strcmp(argv[1], "-") != 0) {
+ in = fopen(argv[1], "rb");
+ if (in == NULL) {
+ fprintf(stderr, "ERROR: failed to open input '%s': %s\n",
+ argv[1], strerror(errno));
+ return 1;
+ }
+ }
+ if (strcmp(argv[2], "-") != 0) {
+ out = fopen(argv[2], "wb");
+ if (out == NULL) {
+ fprintf(stderr, "ERROR: failed to open output '%s': %s\n",
+ argv[2], strerror(errno));
+ if (in != stdin)
+ fclose(in);
+ return 1;
+ }
+ }
+
+ cc = filterData(in, out);
+
+ if (in != stdin)
+ fclose(in);
+ if (out != stdout)
+ fclose(out);
+ return (cc != 0);
+}
+