michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "leaky.h"
michael@0: #include "intcnt.h"
michael@0: 
michael@0: #include <sys/types.h>
michael@0: #include <sys/mman.h>
michael@0: #include <sys/stat.h>
michael@0: #include <fcntl.h>
michael@0: #include <unistd.h>
michael@0: #include <string.h>
michael@0: #ifndef NTO
michael@0: #include <getopt.h>
michael@0: #endif
michael@0: #include <assert.h>
michael@0: #include <stdlib.h>
michael@0: #include <stdio.h>
michael@0: 
michael@0: #ifdef NTO
michael@0: #include <mem.h>
michael@0: #endif
michael@0: 
michael@0: #ifndef FALSE
michael@0: #define FALSE 0
michael@0: #endif
michael@0: #ifndef TRUE
michael@0: #define TRUE 1
michael@0: #endif
michael@0: 
michael@0: static const u_int DefaultBuckets = 10007;	// arbitrary, but prime
michael@0: static const u_int MaxBuckets = 1000003;	// arbitrary, but prime
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: int main(int argc, char** argv)
michael@0: {
michael@0:   leaky* l = new leaky;
michael@0: 
michael@0:   l->initialize(argc, argv);
michael@0:   l->outputfd = stdout;
michael@0: 
michael@0:   for (int i = 0; i < l->numLogFiles; i++) {
michael@0:     if (l->output_dir || l->numLogFiles > 1) {
michael@0:       char name[2048]; // XXX fix
michael@0:       if (l->output_dir)
michael@0:         snprintf(name,sizeof(name),"%s/%s.html",l->output_dir,argv[l->logFileIndex + i]);
michael@0:       else
michael@0:         snprintf(name,sizeof(name),"%s.html",argv[l->logFileIndex + i]);
michael@0: 
michael@0:       fprintf(stderr,"opening %s\n",name);
michael@0:       l->outputfd = fopen(name,"w");
michael@0:       // if an error we won't process the file
michael@0:     }
michael@0:     if (l->outputfd) { // paranoia
michael@0:       l->open(argv[l->logFileIndex + i]);
michael@0: 
michael@0:       if (l->outputfd != stderr) {
michael@0:         fclose(l->outputfd);
michael@0:         l->outputfd = nullptr;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   return 0;
michael@0: }
michael@0: 
michael@0: char *
michael@0: htmlify(const char *in)
michael@0: {
michael@0:   const char *p = in;
michael@0:   char *out, *q;
michael@0:   int n = 0;
michael@0:   size_t newlen;
michael@0: 
michael@0:   // Count the number of '<' and '>' in the input.
michael@0:   while ((p = strpbrk(p, "<>")))
michael@0:   {
michael@0:     ++n;
michael@0:     ++p;
michael@0:   }
michael@0: 
michael@0:   // Knowing the number of '<' and '>', we can calculate the space
michael@0:   // needed for the output string.
michael@0:   newlen = strlen(in) + n * 3 + 1;
michael@0:   out = new char[newlen];
michael@0: 
michael@0:   // Copy the input to the output, with substitutions.
michael@0:   p = in;
michael@0:   q = out;
michael@0:   do
michael@0:   {
michael@0:     if (*p == '<') 
michael@0:     {
michael@0:       strcpy(q, "&lt;");
michael@0:       q += 4;
michael@0:     }
michael@0:     else if (*p == '>')
michael@0:     {
michael@0:       strcpy(q, "&gt;");
michael@0:       q += 4;
michael@0:     }
michael@0:     else
michael@0:     {
michael@0:       *q++ = *p;
michael@0:     }
michael@0:     p++;
michael@0:   } while (*p);
michael@0:   *q = '\0';
michael@0: 
michael@0:   return out;
michael@0: }
michael@0: 
michael@0: leaky::leaky()
michael@0: {
michael@0:   applicationName = nullptr;
michael@0:   progFile = nullptr;
michael@0: 
michael@0:   quiet = true;
michael@0:   showAddress = false;
michael@0:   showThreads = false;
michael@0:   stackDepth = 100000;
michael@0:   onlyThread = 0;
michael@0:   cleo = false;
michael@0: 
michael@0:   mappedLogFile = -1;
michael@0:   firstLogEntry = lastLogEntry = 0;
michael@0: 
michael@0:   sfd = -1;
michael@0:   externalSymbols = 0;
michael@0:   usefulSymbols = 0;
michael@0:   numExternalSymbols = 0;
michael@0:   lowestSymbolAddr = 0;
michael@0:   highestSymbolAddr = 0;
michael@0: 
michael@0:   loadMap = nullptr;
michael@0: 
michael@0:   collect_last  = false;
michael@0:   collect_start = -1;
michael@0:   collect_end   = -1;
michael@0: }
michael@0: 
michael@0: leaky::~leaky()
michael@0: {
michael@0: }
michael@0: 
michael@0: void leaky::usageError()
michael@0: {
michael@0:   fprintf(stderr, "Usage: %s [-v] [-t] [-e exclude] [-i include] [-s stackdepth] [--last] [--all] [--start n [--end m]] [--cleo] [--output-dir dir] prog log [log2 ...]\n", (char*) applicationName);
michael@0:   fprintf(stderr, 
michael@0:           "\t-v: verbose\n"
michael@0:           "\t-t | --threads: split threads\n"
michael@0:           "\t--only-thread n: only profile thread N\n"
michael@0:           "\t-i include-id: stack must include specified id\n"
michael@0:           "\t-e exclude-id: stack must NOT include specified id\n"
michael@0:           "\t-s stackdepth: Limit depth looked at from captured stack frames\n"
michael@0:           "\t--last: only profile the last capture section\n"
michael@0:           "\t--start n [--end m]: profile n to m (or end) capture sections\n"
michael@0:           "\t--cleo: format output for 'cleopatra' display\n"
michael@0:           "\t--output-dir dir: write output files to dir\n"
michael@0:           "\tIf there's one log, output goes to stdout unless --output-dir is set\n"
michael@0:           "\tIf there are more than one log, output files will be named with .html added\n"
michael@0:           );
michael@0:   exit(-1);
michael@0: }
michael@0: 
michael@0: static struct option longopts[] = {
michael@0:     { "threads", 0, nullptr, 't' },
michael@0:     { "only-thread", 1, nullptr, 'T' },
michael@0:     { "last", 0, nullptr, 'l' },
michael@0:     { "start", 1, nullptr, 'x' },
michael@0:     { "end", 1, nullptr, 'n' },
michael@0:     { "cleo",0, nullptr, 'c' },
michael@0:     { "output-dir", 1, nullptr, 'd' },
michael@0:     { nullptr, 0, nullptr, 0 },
michael@0: };
michael@0: 
michael@0: void leaky::initialize(int argc, char** argv)
michael@0: {
michael@0:   applicationName = argv[0];
michael@0:   applicationName = strrchr(applicationName, '/');
michael@0:   if (!applicationName) {
michael@0:     applicationName = argv[0];
michael@0:   } else {
michael@0:     applicationName++;
michael@0:   }
michael@0: 
michael@0:   int arg;
michael@0:   int errflg = 0;
michael@0:   int longindex = 0;
michael@0: 
michael@0:   onlyThread = 0;
michael@0:   output_dir = nullptr;
michael@0:   cleo = false;
michael@0: 
michael@0:   // XXX tons of cruft here left over from tracemalloc
michael@0:   // XXX The -- options shouldn't need short versions, or they should be documented
michael@0:   while (((arg = getopt_long(argc, argv, "adEe:gh:i:r:Rs:tT:qvx:ln:",longopts,&longindex)) != -1)) {
michael@0:     switch (arg) {
michael@0:       case '?':
michael@0:       default:
michael@0:         fprintf(stderr,"error: unknown option %c\n",optopt);
michael@0: 	errflg++;
michael@0: 	break;
michael@0:       case 'a':
michael@0: 	break;
michael@0:       case 'A': // not implemented
michael@0: 	showAddress = true;
michael@0: 	break;
michael@0:       case 'c':
michael@0:         cleo = true;
michael@0:         break;
michael@0:       case 'd':
michael@0:         output_dir = optarg; // reference to an argv pointer
michael@0: 	break;
michael@0:       case 'R':
michael@0: 	break;
michael@0:       case 'e':
michael@0: 	exclusions.add(optarg);
michael@0: 	break;
michael@0:       case 'g':
michael@0: 	break;
michael@0:       case 'r': // not implemented
michael@0: 	roots.add(optarg);
michael@0: 	if (!includes.IsEmpty()) {
michael@0: 	  errflg++;
michael@0: 	}
michael@0: 	break;
michael@0:       case 'i':
michael@0: 	includes.add(optarg);
michael@0: 	if (!roots.IsEmpty()) {
michael@0: 	  errflg++;
michael@0: 	}
michael@0: 	break;
michael@0:       case 'h':
michael@0: 	break;
michael@0:       case 's':
michael@0: 	stackDepth = atoi(optarg);
michael@0: 	if (stackDepth < 2) {
michael@0: 	  stackDepth = 2;
michael@0: 	}
michael@0: 	break;
michael@0:       case 'x':
michael@0:         // --start
michael@0:         collect_start = atoi(optarg);
michael@0: 	break;
michael@0:       case 'n':
michael@0:         // --end
michael@0:         collect_end = atoi(optarg);
michael@0:         break;
michael@0:       case 'l':
michael@0:         // --last
michael@0:         collect_last = true;
michael@0:         break;
michael@0:       case 'q':
michael@0:         break;
michael@0:       case 'v':
michael@0:         quiet = !quiet;
michael@0:         break;
michael@0:       case 't':
michael@0:         showThreads = true;
michael@0: 	break;
michael@0:       case 'T':
michael@0:         showThreads = true;
michael@0:         onlyThread = atoi(optarg);
michael@0: 	break;
michael@0:     }
michael@0:   }
michael@0:   if (errflg || ((argc - optind) < 2)) {
michael@0:     usageError();
michael@0:   }
michael@0:   progFile = argv[optind++];
michael@0:   logFileIndex = optind;
michael@0:   numLogFiles  = argc - optind;
michael@0:   if (!quiet)
michael@0:     fprintf(stderr,"numlogfiles = %d\n",numLogFiles);
michael@0: }
michael@0: 
michael@0: static void* mapFile(int fd, u_int flags, off_t* sz)
michael@0: {
michael@0:   struct stat sb;
michael@0:   if (fstat(fd, &sb) < 0) {
michael@0:     perror("fstat");
michael@0:     exit(-1);
michael@0:   }
michael@0:   void* base = mmap(0, (int)sb.st_size, flags, MAP_PRIVATE, fd, 0);
michael@0:   if (!base) {
michael@0:     perror("mmap");
michael@0:     exit(-1);
michael@0:   }
michael@0:   *sz = sb.st_size;
michael@0:   return base;
michael@0: }
michael@0: 
michael@0: void leaky::LoadMap()
michael@0: {
michael@0:   malloc_map_entry mme;
michael@0:   char name[1000];
michael@0: 
michael@0:   if (!loadMap) {
michael@0:     // all files use the same map
michael@0:     int fd = ::open(M_MAPFILE, O_RDONLY);
michael@0:     if (fd < 0) {
michael@0:       perror("open: " M_MAPFILE);
michael@0:       exit(-1);
michael@0:     }
michael@0:     for (;;) {
michael@0:       int nb = read(fd, &mme, sizeof(mme));
michael@0:       if (nb != sizeof(mme)) break;
michael@0:       nb = read(fd, name, mme.nameLen);
michael@0:       if (nb != (int)mme.nameLen) break;
michael@0:       name[mme.nameLen] = 0;
michael@0:       if (!quiet) {
michael@0:         fprintf(stderr,"%s @ %lx\n", name, mme.address);
michael@0:       }
michael@0: 
michael@0:       LoadMapEntry* lme = new LoadMapEntry;
michael@0:       lme->address = mme.address;
michael@0:       lme->name = strdup(name);
michael@0:       lme->next = loadMap;
michael@0:       loadMap = lme;
michael@0:     }
michael@0:     close(fd);
michael@0:   }
michael@0: }
michael@0: 
michael@0: void leaky::open(char *logFile)
michael@0: {
michael@0:   int threadArray[100]; // should auto-expand
michael@0:   int last_thread = -1;
michael@0:   int numThreads = 0;
michael@0:   int section = -1;
michael@0:   bool collecting = false;
michael@0: 
michael@0:   LoadMap();
michael@0: 
michael@0:   setupSymbols(progFile);
michael@0: 
michael@0:   // open up the log file
michael@0:   if (mappedLogFile)
michael@0:     ::close(mappedLogFile);
michael@0: 
michael@0:   mappedLogFile = ::open(logFile, O_RDONLY);
michael@0:   if (mappedLogFile < 0) {
michael@0:     perror("open");
michael@0:     exit(-1);
michael@0:   }
michael@0:   off_t size;
michael@0:   firstLogEntry = (malloc_log_entry*) mapFile(mappedLogFile, PROT_READ, &size);
michael@0:   lastLogEntry = (malloc_log_entry*)((char*)firstLogEntry + size);
michael@0: 
michael@0:   if (!collect_last || collect_start < 0) {
michael@0:     collecting = true;
michael@0:   }
michael@0: 
michael@0:   // First, restrict it to the capture sections specified (all, last, start/end)
michael@0:   // This loop walks through all the call stacks we recorded
michael@0:   for (malloc_log_entry* lep=firstLogEntry;
michael@0:        lep < lastLogEntry;
michael@0:        lep = reinterpret_cast<malloc_log_entry*>(&lep->pcs[lep->numpcs])) {
michael@0: 
michael@0:     if (lep->flags & JP_FIRST_AFTER_PAUSE) {
michael@0:       section++;
michael@0:       if (collect_last) {
michael@0:         firstLogEntry = lep;
michael@0:         numThreads = 0;
michael@0:         collecting = true;
michael@0:       }
michael@0:       if (collect_start == section) {
michael@0:         collecting = true;
michael@0:         firstLogEntry = lep;
michael@0:       }
michael@0:       if (collect_end == section) {
michael@0:         collecting = false;
michael@0:         lastLogEntry = lep;
michael@0:       }
michael@0:       if (!quiet)
michael@0:         fprintf(stderr,"New section %d: first=%p, last=%p, collecting=%d\n",
michael@0:                 section,(void*)firstLogEntry,(void*)lastLogEntry,collecting);
michael@0:     }
michael@0: 
michael@0:     // Capture thread info at the same time
michael@0: 
michael@0:     // Find all the threads captured
michael@0: 
michael@0:     // pthread/linux docs say the signal can be delivered to any thread in
michael@0:     // the process.  In practice, it appears in Linux that it's always
michael@0:     // delivered to the thread that called setitimer(), and each thread can
michael@0:     // have a separate itimer.  There's a support library for gprof that
michael@0:     // overlays pthread_create() to set timers in any threads you spawn.
michael@0:     if (showThreads && collecting) {
michael@0:       if (lep->thread != last_thread)
michael@0:       {
michael@0:         int i;
michael@0:         for (i=0; i<numThreads; i++)
michael@0:         {
michael@0:           if (lep->thread == threadArray[i])
michael@0:             break;
michael@0:         }
michael@0:         if (i == numThreads &&
michael@0:             i < (int) (sizeof(threadArray)/sizeof(threadArray[0])))
michael@0:         {
michael@0:           threadArray[i] = lep->thread;
michael@0:           numThreads++;
michael@0:           if (!quiet)
michael@0:             fprintf(stderr,"new thread %d\n",lep->thread);
michael@0:         }
michael@0:       }
michael@0:     }
michael@0:   }  
michael@0:   if (!quiet)
michael@0:     fprintf(stderr,"Done collecting: sections %d: first=%p, last=%p, numThreads=%d\n",
michael@0:             section,(void*)firstLogEntry,(void*)lastLogEntry,numThreads);
michael@0: 
michael@0:   if (!cleo) {
michael@0:     fprintf(outputfd,"<html><head><title>Jprof Profile Report</title></head><body>\n");
michael@0:     fprintf(outputfd,"<h1><center>Jprof Profile Report</center></h1>\n");
michael@0:   }
michael@0: 
michael@0:   if (showThreads)
michael@0:   {
michael@0:     fprintf(stderr,"Num threads %d\n",numThreads);
michael@0: 
michael@0:     if (!cleo) {
michael@0:       fprintf(outputfd,"<hr>Threads:<p><pre>\n");
michael@0:       for (int i=0; i<numThreads; i++)
michael@0:       {
michael@0:         fprintf(outputfd,"   <a href=\"#thread_%d\">%d</a>  ",
michael@0:                 threadArray[i],threadArray[i]);
michael@0:         if ((i+1)%10 == 0)
michael@0:           fprintf(outputfd,"<br>\n");
michael@0:       }
michael@0:       fprintf(outputfd,"</pre>");
michael@0:     }
michael@0: 
michael@0:     for (int i=0; i<numThreads; i++)
michael@0:     {
michael@0:       if (!onlyThread || onlyThread == threadArray[i])
michael@0:         analyze(threadArray[i]);
michael@0:     }
michael@0:   }
michael@0:   else
michael@0:   {
michael@0:     analyze(0);
michael@0:   }
michael@0: 
michael@0:   if (!cleo)
michael@0:     fprintf(outputfd,"</pre></body></html>\n");
michael@0: }
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: 
michael@0: static int symbolOrder(void const* a, void const* b)
michael@0: {
michael@0:   Symbol const** ap = (Symbol const **)a;
michael@0:   Symbol const** bp = (Symbol const **)b;
michael@0:   return (*ap)->address == (*bp)->address ? 0 :
michael@0:     ((*ap)->address > (*bp)->address ? 1 : -1);
michael@0: }
michael@0: 
michael@0: void leaky::ReadSharedLibrarySymbols()
michael@0: {
michael@0:   LoadMapEntry* lme = loadMap;
michael@0:   while (nullptr != lme) {
michael@0:     ReadSymbols(lme->name, lme->address);
michael@0:     lme = lme->next;
michael@0:   }
michael@0: }
michael@0: 
michael@0: void leaky::setupSymbols(const char *fileName)
michael@0: {
michael@0:   if (usefulSymbols == 0) {
michael@0:     // only read once!
michael@0: 
michael@0:     // Read in symbols from the program
michael@0:     ReadSymbols(fileName, 0);
michael@0: 
michael@0:     // Read in symbols from the .so's
michael@0:     ReadSharedLibrarySymbols();
michael@0: 
michael@0:     if (!quiet) {
michael@0:       fprintf(stderr,"A total of %d symbols were loaded\n", usefulSymbols);
michael@0:     }
michael@0: 
michael@0:     // Now sort them
michael@0:     qsort(externalSymbols, usefulSymbols, sizeof(Symbol *), symbolOrder);
michael@0:     lowestSymbolAddr = externalSymbols[0]->address;
michael@0:     highestSymbolAddr = externalSymbols[usefulSymbols-1]->address;
michael@0:   }
michael@0: }
michael@0: 
michael@0: // Binary search the table, looking for a symbol that covers this
michael@0: // address.
michael@0: int leaky::findSymbolIndex(u_long addr)
michael@0: {
michael@0:   u_int base = 0;
michael@0:   u_int limit = usefulSymbols - 1;
michael@0:   Symbol** end = &externalSymbols[limit];
michael@0:   while (base <= limit) {
michael@0:     u_int midPoint = (base + limit)>>1;
michael@0:     Symbol** sp = &externalSymbols[midPoint];
michael@0:     if (addr < (*sp)->address) {
michael@0:       if (midPoint == 0) {
michael@0: 	return -1;
michael@0:       }
michael@0:       limit = midPoint - 1;
michael@0:     } else {
michael@0:       if (sp+1 < end) {
michael@0: 	if (addr < (*(sp+1))->address) {
michael@0: 	  return midPoint;
michael@0: 	}
michael@0:       } else {
michael@0: 	return midPoint;
michael@0:       }
michael@0:       base = midPoint + 1;
michael@0:     }
michael@0:   }
michael@0:   return -1;
michael@0: }
michael@0: 
michael@0: Symbol* leaky::findSymbol(u_long addr)
michael@0: {
michael@0:   int idx = findSymbolIndex(addr);
michael@0: 
michael@0:   if(idx<0) {
michael@0:     return nullptr;
michael@0:   } else {
michael@0:     return externalSymbols[idx];
michael@0:   }
michael@0: }
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: bool leaky::excluded(malloc_log_entry* lep)
michael@0: {
michael@0:   if (exclusions.IsEmpty()) {
michael@0:     return false;
michael@0:   }
michael@0: 
michael@0:   char** pcp = &lep->pcs[0];
michael@0:   u_int n = lep->numpcs;
michael@0:   for (u_int i = 0; i < n; i++, pcp++) {
michael@0:     Symbol* sp = findSymbol((u_long) *pcp);
michael@0:     if (sp && exclusions.contains(sp->name)) {
michael@0:       return true;
michael@0:     }
michael@0:   }
michael@0:   return false;
michael@0: }
michael@0: 
michael@0: bool leaky::included(malloc_log_entry* lep)
michael@0: {
michael@0:   if (includes.IsEmpty()) {
michael@0:     return true;
michael@0:   }
michael@0: 
michael@0:   char** pcp = &lep->pcs[0];
michael@0:   u_int n = lep->numpcs;
michael@0:   for (u_int i = 0; i < n; i++, pcp++) {
michael@0:     Symbol* sp = findSymbol((u_long) *pcp);
michael@0:     if (sp && includes.contains(sp->name)) {
michael@0:       return true;
michael@0:     }
michael@0:   }
michael@0:   return false;
michael@0: }
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: void leaky::displayStackTrace(FILE* out, malloc_log_entry* lep)
michael@0: {
michael@0:   char** pcp = &lep->pcs[0];
michael@0:   u_int n = (lep->numpcs < stackDepth) ? lep->numpcs : stackDepth;
michael@0:   for (u_int i = 0; i < n; i++, pcp++) {
michael@0:     u_long addr = (u_long) *pcp;
michael@0:     Symbol* sp = findSymbol(addr);
michael@0:     if (sp) {
michael@0:       fputs(sp->name, out);
michael@0:       if (showAddress) {
michael@0: 	fprintf(out, "[%p]", (char*)addr);
michael@0:       }
michael@0:     }
michael@0:     else {
michael@0:       fprintf(out, "<%p>", (char*)addr);
michael@0:     }
michael@0:     fputc(' ', out);
michael@0:   }
michael@0:   fputc('\n', out);
michael@0: }
michael@0: 
michael@0: void leaky::dumpEntryToLog(malloc_log_entry* lep)
michael@0: {
michael@0:   printf("%ld\t", lep->delTime);
michael@0:   printf(" --> ");
michael@0:   displayStackTrace(outputfd, lep);
michael@0: }
michael@0: 
michael@0: void leaky::generateReportHTML(FILE *fp, int *countArray, int count, int thread)
michael@0: {
michael@0:   fprintf(fp,"<center>");
michael@0:   if (showThreads)
michael@0:   {
michael@0:     fprintf(fp,"<hr><A NAME=thread_%d><b>Thread: %d</b></A><p>",
michael@0:             thread,thread);
michael@0:   }
michael@0:   fprintf(fp,"<A href=#flat_%d>flat</A><b> | </b><A href=#hier_%d>hierarchical</A>",
michael@0:           thread,thread);
michael@0:   fprintf(fp,"</center><P><P><P>\n");
michael@0: 
michael@0:   int totalTimerHits = count;
michael@0:   int *rankingTable = new int[usefulSymbols];
michael@0: 
michael@0:   for(int cnt=usefulSymbols; --cnt>=0; rankingTable[cnt]=cnt);
michael@0: 
michael@0:   // Drat.  I would use ::qsort() but I would need a global variable and my
michael@0:   // intro-pascal professor threatened to flunk anyone who used globals.
michael@0:   // She damaged me for life :-) (That was 1986.  See how much influence
michael@0:   // she had.  I don't remember her name but I always feel guilty about globals)
michael@0: 
michael@0:   // Shell Sort. 581130733 is the max 31 bit value of h = 3h+1
michael@0:   int mx, i, h;
michael@0:   for(mx=usefulSymbols/9, h=581130733; h>0; h/=3) {
michael@0:     if(h<mx) {
michael@0:       for(i = h-1; i<usefulSymbols; i++) {
michael@0:         int j, tmp=rankingTable[i], val = countArray[tmp];
michael@0: 	for(j = i; (j>=h) && (countArray[rankingTable[j-h]]<val); j-=h) {
michael@0: 	  rankingTable[j] = rankingTable[j-h];
michael@0: 	}
michael@0: 	rankingTable[j] = tmp;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // Ok, We are sorted now.  Let's go through the table until we get to
michael@0:   // functions that were never called.  Right now we don't do much inside
michael@0:   // this loop.  Later we can get callers and callees into it like gprof
michael@0:   // does
michael@0:   fprintf(fp,
michael@0:           "<h2><A NAME=hier_%d></A><center><a href=\"http://mxr.mozilla.org/mozilla-central/source/tools/jprof/README.html#hier\">Hierarchical Profile</a></center></h2><hr>\n",
michael@0:           thread);
michael@0:   fprintf(fp, "<pre>\n");
michael@0:   fprintf(fp, "%6s %6s         %4s      %s\n",
michael@0:           "index", "Count", "Hits", "Function Name");
michael@0: 
michael@0:   for(i=0; i<usefulSymbols && countArray[rankingTable[i]]>0; i++) {
michael@0:     Symbol **sp=&externalSymbols[rankingTable[i]];
michael@0:     
michael@0:     (*sp)->cntP.printReport(fp, this, rankingTable[i], totalTimerHits);
michael@0: 
michael@0:     char *symname = htmlify((*sp)->name);
michael@0:     fprintf(fp, "%6d %6d (%3.1f%%)%s <a name=%d>%8d (%3.1f%%)</a>%s <b>%s</b>\n", 
michael@0:             rankingTable[i],
michael@0:             (*sp)->timerHit, ((*sp)->timerHit*1000/totalTimerHits)/10.0,
michael@0:             ((*sp)->timerHit*1000/totalTimerHits)/10.0 >= 10.0 ? "" : " ",
michael@0:             rankingTable[i], countArray[rankingTable[i]],
michael@0:             (countArray[rankingTable[i]]*1000/totalTimerHits)/10.0,
michael@0:             (countArray[rankingTable[i]]*1000/totalTimerHits)/10.0 >= 10.0 ? "" : " ",
michael@0:             symname);
michael@0:     delete [] symname;
michael@0: 
michael@0:     (*sp)->cntC.printReport(fp, this, rankingTable[i], totalTimerHits);
michael@0: 
michael@0:     fprintf(fp, "<hr>\n");
michael@0:   }
michael@0:   fprintf(fp,"</pre>\n");
michael@0: 
michael@0:   // OK, Now we want to print the flat profile.  To do this we resort on
michael@0:   // the hit count.
michael@0: 
michael@0:   // Cut-N-Paste Shell sort from above.  The Ranking Table has already been
michael@0:   // populated, so we do not have to reinitialize it.
michael@0:   for(mx=usefulSymbols/9, h=581130733; h>0; h/=3) {
michael@0:     if(h<mx) {
michael@0:       for(i = h-1; i<usefulSymbols; i++) {
michael@0: 	int j, tmp=rankingTable[i], val = externalSymbols[tmp]->timerHit;
michael@0: 	for(j = i;
michael@0: 	  (j>=h) && (externalSymbols[rankingTable[j-h]]->timerHit<val); j-=h) {
michael@0: 	  rankingTable[j] = rankingTable[j-h];
michael@0: 	}
michael@0: 	rankingTable[j] = tmp;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // Pre-count up total counter hits, to get a percentage.
michael@0:   // I wanted the total before walking the list, if this
michael@0:   // double-pass over externalSymbols gets slow we can
michael@0:   // do single-pass and print this out after the loop finishes.
michael@0:   totalTimerHits = 0;
michael@0:   for(i=0;
michael@0:       i<usefulSymbols && externalSymbols[rankingTable[i]]->timerHit>0; i++) {
michael@0:     Symbol **sp=&externalSymbols[rankingTable[i]];
michael@0:     totalTimerHits += (*sp)->timerHit;
michael@0:   }
michael@0:   if (totalTimerHits == 0)
michael@0:     totalTimerHits = 1;
michael@0: 
michael@0:   if (totalTimerHits != count)
michael@0:     fprintf(stderr,"Hit count mismatch: count=%d; totalTimerHits=%d",
michael@0:             count,totalTimerHits);
michael@0: 
michael@0:   fprintf(fp,"<h2><A NAME=flat_%d></A><center><a href=\"http://mxr.mozilla.org/mozilla-central/source/tools/jprof/README.html#flat\">Flat Profile</a></center></h2><br>\n",
michael@0:           thread);
michael@0:   fprintf(fp, "<pre>\n");
michael@0: 
michael@0:   fprintf(fp, "Total hit count: %d\n", totalTimerHits);
michael@0:   fprintf(fp, "Count %%Total  Function Name\n");
michael@0:   // Now loop for as long as we have timer hits
michael@0:   for(i=0;
michael@0:       i<usefulSymbols && externalSymbols[rankingTable[i]]->timerHit>0; i++) {
michael@0: 
michael@0:     Symbol **sp=&externalSymbols[rankingTable[i]];
michael@0:     
michael@0:     char *symname = htmlify((*sp)->name);
michael@0:     fprintf(fp, "<a href=\"#%d\">%3d   %-2.1f     %s</a>\n",
michael@0:             rankingTable[i], (*sp)->timerHit,
michael@0:             ((float)(*sp)->timerHit/(float)totalTimerHits)*100.0, symname);
michael@0:     delete [] symname;
michael@0:   }
michael@0: }
michael@0: 
michael@0: void leaky::analyze(int thread)
michael@0: {
michael@0:   int *countArray = new int[usefulSymbols];
michael@0:   int *flagArray  = new int[usefulSymbols];
michael@0: 
michael@0:   //Zero our function call counter
michael@0:   memset(countArray, 0, sizeof(countArray[0])*usefulSymbols);
michael@0: 
michael@0:   // reset hit counts
michael@0:   for(int i=0; i<usefulSymbols; i++) {
michael@0:     externalSymbols[i]->timerHit = 0;
michael@0:     externalSymbols[i]->regClear();
michael@0:   }
michael@0: 
michael@0:   // The flag array is used to prevent counting symbols multiple times
michael@0:   // if functions are called recursively.  In order to keep from having
michael@0:   // to zero it on each pass through the loop, we mark it with the value
michael@0:   // of stacks on each trip through the loop.  This means we can determine
michael@0:   // if we have seen this symbol for this stack trace w/o having to reset
michael@0:   // from the prior stacktrace.
michael@0:   memset(flagArray, -1, sizeof(flagArray[0])*usefulSymbols);
michael@0: 
michael@0:   if (cleo)
michael@0:     fprintf(outputfd,"m-Start\n");
michael@0: 
michael@0:   // This loop walks through all the call stacks we recorded
michael@0:   // --last, --start and --end can restrict it, as can excludes/includes
michael@0:   stacks = 0;
michael@0:   for(malloc_log_entry* lep=firstLogEntry; 
michael@0:     lep < lastLogEntry;
michael@0:     lep = reinterpret_cast<malloc_log_entry*>(&lep->pcs[lep->numpcs])) {
michael@0: 
michael@0:     if ((thread != 0 && lep->thread != thread) ||
michael@0:         excluded(lep) || !included(lep))
michael@0:     {
michael@0:       continue;
michael@0:     }
michael@0: 
michael@0:     ++stacks; // How many stack frames did we collect
michael@0: 
michael@0:     u_int n = (lep->numpcs < stackDepth) ? lep->numpcs : stackDepth;
michael@0:     char** pcp = &lep->pcs[n-1];
michael@0:     int idx=-1, parrentIdx=-1;  // Init idx incase n==0
michael@0:     if (cleo) {
michael@0:       // This loop walks through every symbol in the call stack.  By walking it
michael@0:       // backwards we know who called the function when we get there.
michael@0:       char type = 's';
michael@0:       for (int i=n-1; i>=0; --i, --pcp) {
michael@0:         idx = findSymbolIndex(reinterpret_cast<u_long>(*pcp));
michael@0: 
michael@0:         if(idx>=0) {
michael@0:           // Skip over bogus __restore_rt frames that realtime profiling
michael@0:           // can introduce.
michael@0:           if (i > 0 && !strcmp(externalSymbols[idx]->name, "__restore_rt")) {
michael@0:             --pcp;
michael@0:             --i;
michael@0:             idx = findSymbolIndex(reinterpret_cast<u_long>(*pcp));
michael@0:             if (idx < 0) {
michael@0:               continue;
michael@0:             }
michael@0:           }
michael@0:           Symbol **sp=&externalSymbols[idx];
michael@0:           char *symname = htmlify((*sp)->name);
michael@0:           fprintf(outputfd,"%c-%s\n",type,symname);
michael@0:           delete [] symname;
michael@0:         }
michael@0:         // else can't find symbol - ignore
michael@0:         type = 'c';
michael@0:       }
michael@0:     } else {
michael@0:       // This loop walks through every symbol in the call stack.  By walking it
michael@0:       // backwards we know who called the function when we get there.
michael@0:       for (int i=n-1; i>=0; --i, --pcp) {
michael@0:         idx = findSymbolIndex(reinterpret_cast<u_long>(*pcp));
michael@0: 
michael@0:         if(idx>=0) {
michael@0:           // Skip over bogus __restore_rt frames that realtime profiling
michael@0:           // can introduce.
michael@0:           if (i > 0 && !strcmp(externalSymbols[idx]->name, "__restore_rt")) {
michael@0:             --pcp;
michael@0:             --i;
michael@0:             idx = findSymbolIndex(reinterpret_cast<u_long>(*pcp));
michael@0:             if (idx < 0) {
michael@0:               continue;
michael@0:             }
michael@0:           }
michael@0: 	
michael@0:           // If we have not seen this symbol before count it and mark it as seen
michael@0:           if(flagArray[idx]!=stacks && ((flagArray[idx]=stacks) || true)) {
michael@0:             ++countArray[idx];
michael@0:           }
michael@0: 
michael@0:           // We know who we are and we know who our parrent is.  Count this
michael@0:           if(parrentIdx>=0) {
michael@0:             externalSymbols[parrentIdx]->regChild(idx);
michael@0:             externalSymbols[idx]->regParrent(parrentIdx);
michael@0:           }
michael@0:           // inside if() so an unknown in the middle of a stack won't break
michael@0:           // the link!
michael@0:           parrentIdx=idx;
michael@0:         }
michael@0:       }
michael@0: 
michael@0:       // idx should be the function that we were in when we received the signal.
michael@0:       if(idx>=0) {
michael@0:         ++externalSymbols[idx]->timerHit;
michael@0:       }
michael@0: 
michael@0:     }
michael@0:   }
michael@0:   if (!cleo)
michael@0:     generateReportHTML(outputfd, countArray, stacks, thread);
michael@0: }
michael@0: 
michael@0: void FunctionCount::printReport(FILE *fp, leaky *lk, int parent, int total)
michael@0: {
michael@0:     const char *fmt = "                      <A href=\"#%d\">%8d (%3.1f%%)%s %s</A>%s\n";
michael@0: 
michael@0:     int nmax, tmax=((~0U)>>1);
michael@0:     
michael@0:     do {
michael@0: 	nmax=0;
michael@0: 	for(int j=getSize(); --j>=0;) {
michael@0: 	    int cnt = getCount(j);
michael@0: 	    if(cnt==tmax) {
michael@0: 		int idx = getIndex(j);
michael@0: 		char *symname = htmlify(lk->indexToName(idx));
michael@0:                 fprintf(fp, fmt, idx, getCount(j),
michael@0:                         getCount(j)*100.0/total,
michael@0:                         getCount(j)*100.0/total >= 10.0 ? "" : " ",
michael@0:                         symname,
michael@0:                         parent == idx ? " (self)" : "");
michael@0: 		delete [] symname;
michael@0: 	    } else if(cnt<tmax && cnt>nmax) {
michael@0: 	        nmax=cnt;
michael@0: 	    }
michael@0: 	}
michael@0:     } while((tmax=nmax)>0);
michael@0: }