tools/trace-malloc/spacecategory.c

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  *
   3  * ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is spacecategory.c code, released
  17  * Apr 12, 2002.
  18  *
  19  * The Initial Developer of the Original Code is
  20  * Netscape Communications Corporation.
  21  * Portions created by the Initial Developer are Copyright (C) 2001
  22  * the Initial Developer. All Rights Reserved.
  23  *
  24  * Contributor(s):
  25  *   Suresh Duddi <dp@netscape.com>, 12-April-2002
  26  *
  27  * Alternatively, the contents of this file may be used under the terms of
  28  * either the GNU General Public License Version 2 or later (the "GPL"), or
  29  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  30  * in which case the provisions of the GPL or the LGPL are applicable instead
  31  * of those above. If you wish to allow use of your version of this file only
  32  * under the terms of either the GPL or the LGPL, and not to allow others to
  33  * use your version of this file under the terms of the MPL, indicate your
  34  * decision by deleting the provisions above and replace them with the notice
  35  * and other provisions required by the GPL or the LGPL. If you do not delete
  36  * the provisions above, a recipient may use your version of this file under
  37  * the terms of any one of the MPL, the GPL or the LGPL.
  38  *
  39  * ***** END LICENSE BLOCK ***** */
  40
  41 /*
  42 ** spacecategory.c
  43 **
  44 ** Cagtegorizes each allocation using a predefined set of rules
  45 ** and presents a tree of categories for browsing.
  46 */
  47
  48 /*
  49 ** Required include files.
  50 */
  51 #include "spacetrace.h"
  52 #include <ctype.h>
  53 #include <string.h>
  54
  55 /*
  56 ** Ugh, MSVC6's qsort is too slow...
  57 */
  58 #include "nsQuickSort.h"
  59
  60 #if defined(HAVE_BOUTELL_GD)
  61 /*
  62 ** See http://www.boutell.com/gd for the GD graphics library.
  63 ** Ports for many platorms exist.
  64 ** Your box may already have the lib (mine did, redhat 7.1 workstation).
  65 */
  66 #include <gd.h>
  67 #include <gdfontt.h>
  68 #include <gdfonts.h>
  69 #include <gdfontmb.h>
  70 #endif /* HAVE_BOUTELL_GD */
  71
  72 /*
  73 ** AddRule
  74 **
  75 ** Add a rule into the list of rules maintainted in global
  76 */
  77 int
  78 AddRule(STGlobals * g, STCategoryRule * rule)
  79 {
  80     if (g->mNRules % ST_ALLOC_STEP == 0) {
  81         /* Need more space */
  82         STCategoryRule **newrules;
  83
  84         newrules = (STCategoryRule **) realloc(g->mCategoryRules,
  85                                                (g->mNRules +
  86                                                 ST_ALLOC_STEP) *
  87                                                sizeof(STCategoryRule *));
  88         if (!newrules) {
  89             REPORT_ERROR(__LINE__, AddRule_No_Memory);
  90             return -1;
  91         }
  92         g->mCategoryRules = newrules;
  93     }
  94     g->mCategoryRules[g->mNRules++] = rule;
  95     return 0;
  96 }
  97
  98 /*
  99 ** AddChild
 100 **
 101 ** Add the node as a child of the parent node
 102 */
 103 int
 104 AddChild(STCategoryNode * parent, STCategoryNode * child)
 105 {
 106     if (parent->nchildren % ST_ALLOC_STEP == 0) {
 107         /* need more space */
 108         STCategoryNode **newnodes;
 109
 110         newnodes = (STCategoryNode **) realloc(parent->children,
 111                                                (parent->nchildren +
 112                                                 ST_ALLOC_STEP) *
 113                                                sizeof(STCategoryNode *));
 114         if (!newnodes) {
 115             REPORT_ERROR(__LINE__, AddChild_No_Memory);
 116             return -1;
 117         }
 118         parent->children = newnodes;
 119     }
 120     parent->children[parent->nchildren++] = child;
 121     return 0;
 122 }
 123
 124 int
 125 ReParent(STCategoryNode * parent, STCategoryNode * child)
 126 {
 127     PRUint32 i;
 128
 129     if (child->parent == parent)
 130         return 0;
 131
 132     /* Remove child from old parent */
 133     if (child->parent) {
 134         for (i = 0; i < child->parent->nchildren; i++) {
 135             if (child->parent->children[i] == child) {
 136                 /* Remove child from list */
 137                 if (i + 1 < child->parent->nchildren)
 138                     memmove(&child->parent->children[i],
 139                             &child->parent->children[i + 1],
 140                             (child->parent->nchildren - i -
 141                              1) * sizeof(STCategoryNode *));
 142                 child->parent->nchildren--;
 143                 break;
 144             }
 145         }
 146     }
 147
 148     /* Add child into new parent */
 149     AddChild(parent, child);
 150
 151     return 0;
 152 }
 153
 154 /*
 155 ** findCategoryNode
 156 **
 157 ** Given a category name, finds the Node corresponding to the category
 158 */
 159 STCategoryNode *
 160 findCategoryNode(const char *catName, STGlobals * g)
 161 {
 162     PRUint32 i;
 163
 164     for (i = 0; i < g->mNCategoryMap; i++) {
 165         if (!strcmp(g->mCategoryMap[i]->categoryName, catName))
 166             return g->mCategoryMap[i]->node;
 167     }
 168
 169     /* Check if we are looking for the root node */
 170     if (!strcmp(catName, ST_ROOT_CATEGORY_NAME))
 171         return &g->mCategoryRoot;
 172
 173     return NULL;
 174 }
 175
 176 /*
 177 ** AddCategoryNode
 178 **
 179 ** Adds a mapping between a category and its Node into the categoryMap
 180 */
 181 int
 182 AddCategoryNode(STCategoryNode * node, STGlobals * g)
 183 {
 184     if (g->mNCategoryMap % ST_ALLOC_STEP == 0) {
 185         /* Need more space */
 186         STCategoryMapEntry **newmap =
 187             (STCategoryMapEntry **) realloc(g->mCategoryMap,
 188                                             (g->mNCategoryMap +
 189                                              ST_ALLOC_STEP) *
 190                                             sizeof(STCategoryMapEntry *));
 191         if (!newmap) {
 192             REPORT_ERROR(__LINE__, AddCategoryNode_No_Memory);
 193             return -1;
 194         }
 195         g->mCategoryMap = newmap;
 196
 197     }
 198     g->mCategoryMap[g->mNCategoryMap] =
 199         (STCategoryMapEntry *) calloc(1, sizeof(STCategoryMapEntry));
 200     if (!g->mCategoryMap[g->mNCategoryMap]) {
 201         REPORT_ERROR(__LINE__, AddCategoryNode_No_Memory);
 202         return -1;
 203     }
 204     g->mCategoryMap[g->mNCategoryMap]->categoryName = node->categoryName;
 205     g->mCategoryMap[g->mNCategoryMap]->node = node;
 206     g->mNCategoryMap++;
 207     return 0;
 208 }
 209
 210 /*
 211 ** NewCategoryNode
 212 **
 213 ** Creates a new category node for category name 'catname' and makes
 214 ** 'parent' its parent.
 215 */
 216 STCategoryNode *
 217 NewCategoryNode(const char *catName, STCategoryNode * parent, STGlobals * g)
 218 {
 219     STCategoryNode *node;
 220
 221     node = (STCategoryNode *) calloc(1, sizeof(STCategoryNode));
 222     if (!node)
 223         return NULL;
 224
 225     node->runs =
 226         (STRun **) calloc(g->mCommandLineOptions.mContexts, sizeof(STRun *));
 227     if (NULL == node->runs) {
 228         free(node);
 229         return NULL;
 230     }
 231
 232     node->categoryName = catName;
 233
 234     /* Set parent of child */
 235     node->parent = parent;
 236
 237     /* Set child in parent */
 238     AddChild(parent, node);
 239
 240     /* Add node into mapping table */
 241     AddCategoryNode(node, g);
 242
 243     return node;
 244 }
 245
 246 /*
 247 ** ProcessCategoryLeafRule
 248 **
 249 ** Add this into the tree as a leaf node. It doesn't know who its parent is. For now we make
 250 ** root as its parent
 251 */
 252 int
 253 ProcessCategoryLeafRule(STCategoryRule * leafRule, STCategoryNode * root,
 254                         STGlobals * g)
 255 {
 256     STCategoryRule *rule;
 257     STCategoryNode *node;
 258
 259     rule = (STCategoryRule *) calloc(1, sizeof(STCategoryRule));
 260     if (!rule)
 261         return -1;
 262
 263     /* Take ownership of all elements of rule */
 264     *rule = *leafRule;
 265
 266     /* Find/Make a STCategoryNode and add it into the tree */
 267     node = findCategoryNode(rule->categoryName, g);
 268     if (!node)
 269         node = NewCategoryNode(rule->categoryName, root, g);
 270
 271     /* Make sure rule knows which node to access */
 272     rule->node = node;
 273
 274     /* Add rule into rulelist */
 275     AddRule(g, rule);
 276
 277     return 0;
 278 }
 279
 280 /*
 281 ** ProcessCategoryParentRule
 282 **
 283 ** Rule has all the children of category as patterns. Sets up the tree so that
 284 ** the parent child relationship is honored.
 285 */
 286 int
 287 ProcessCategoryParentRule(STCategoryRule * parentRule, STCategoryNode * root,
 288                           STGlobals * g)
 289 {
 290     STCategoryNode *node;
 291     STCategoryNode *child;
 292     PRUint32 i;
 293
 294     /* Find the parent node in the tree. If not make one and add it into the tree */
 295     node = findCategoryNode(parentRule->categoryName, g);
 296     if (!node) {
 297         node = NewCategoryNode(parentRule->categoryName, root, g);
 298         if (!node)
 299             return -1;
 300     }
 301
 302     /* For every child node, Find/Create it and make it the child of this node */
 303     for (i = 0; i < parentRule->npats; i++) {
 304         child = findCategoryNode(parentRule->pats[i], g);
 305         if (!child) {
 306             child = NewCategoryNode(parentRule->pats[i], node, g);
 307             if (!child)
 308                 return -1;
 309         }
 310         else {
 311             /* Reparent child to node. This is because when we created the node
 312              ** we would have created it as the child of root. Now we need to
 313              ** remove it from root's child list and add it into this node
 314              */
 315             ReParent(node, child);
 316         }
 317     }
 318
 319     return 0;
 320 }
 321
 322 /*
 323 ** initCategories
 324 **
 325 ** Initialize all categories. This reads in a file that says how to categorize
 326 ** each callsite, creates a tree of these categories and makes a list of these
 327 ** patterns in order for matching
 328 */
 329 int
 330 initCategories(STGlobals * g)
 331 {
 332     FILE *fp;
 333     char buf[1024], *in;
 334     int n;
 335     PRBool inrule, leaf;
 336     STCategoryRule rule;
 337
 338     fp = fopen(g->mCommandLineOptions.mCategoryFile, "r");
 339     if (!fp) {
 340         /* It isn't an error to not have a categories file */
 341         REPORT_INFO("No categories file.");
 342         return -1;
 343     }
 344
 345     inrule = PR_FALSE;
 346     leaf = PR_FALSE;
 347
 348     memset(&rule, 0, sizeof(rule));
 349
 350     while (fgets(buf, sizeof(buf), fp) != NULL) {
 351         /* Lose the \n */
 352         n = strlen(buf);
 353         if (buf[n - 1] == '\n')
 354             buf[--n] = '\0';
 355         in = buf;
 356
 357         /* skip comments */
 358         if (*in == '#')
 359             continue;
 360
 361         /* skip empty lines. If we are in a rule, end the rule. */
 362         while (*in && isspace(*in))
 363             in++;
 364         if (*in == '\0') {
 365             if (inrule) {
 366                 /* End the rule : leaf or non-leaf */
 367                 if (leaf)
 368                     ProcessCategoryLeafRule(&rule, &g->mCategoryRoot, g);
 369                 else
 370                     /* non-leaf */
 371                     ProcessCategoryParentRule(&rule, &g->mCategoryRoot, g);
 372                 inrule = PR_FALSE;
 373                 memset(&rule, 0, sizeof(rule));
 374             }
 375             continue;
 376         }
 377
 378         /* if we are in a rule acculumate */
 379         if (inrule) {
 380             rule.pats[rule.npats] = strdup(in);
 381             rule.patlen[rule.npats++] = strlen(in);
 382         }
 383         else if (*in == '<') {
 384             /* Start a category */
 385             inrule = PR_TRUE;
 386             leaf = PR_TRUE;
 387
 388             /* Get the category name */
 389             in++;
 390             n = strlen(in);
 391             if (in[n - 1] == '>')
 392                 in[n - 1] = '\0';
 393             rule.categoryName = strdup(in);
 394         }
 395         else {
 396             /* this is a non-leaf category. Should be of the form CategoryName
 397              ** followed by list of child category names one per line
 398              */
 399             inrule = PR_TRUE;
 400             leaf = PR_FALSE;
 401             rule.categoryName = strdup(in);
 402         }
 403     }
 404
 405     /* If we were in a rule when processing the last line, end the rule */
 406     if (inrule) {
 407         /* End the rule : leaf or non-leaf */
 408         if (leaf)
 409             ProcessCategoryLeafRule(&rule, &g->mCategoryRoot, g);
 410         else
 411             /* non-leaf */
 412             ProcessCategoryParentRule(&rule, &g->mCategoryRoot, g);
 413     }
 414
 415     /* Add the final "uncategorized" category. We make new memory locations
 416      ** for all these to conform to the general principle of all strings are allocated
 417      ** so it makes release logic very simple.
 418      */
 419     memset(&rule, 0, sizeof(rule));
 420     rule.categoryName = strdup("uncategorized");
 421     rule.pats[0] = strdup("");
 422     rule.patlen[0] = 0;
 423     rule.npats = 1;
 424     ProcessCategoryLeafRule(&rule, &g->mCategoryRoot, g);
 425
 426     return 0;
 427 }
 428
 429 /*
 430 ** callsiteMatchesRule
 431 **
 432 ** Returns the corresponding node if callsite matches the rule. Rule is a sequence
 433 ** of patterns that must match contiguously the callsite.
 434 */
 435 int
 436 callsiteMatchesRule(tmcallsite * aCallsite, STCategoryRule * aRule)
 437 {
 438     PRUint32 patnum = 0;
 439     const char *methodName = NULL;
 440
 441     while (patnum < aRule->npats && aCallsite && aCallsite->method) {
 442         methodName = tmmethodnode_name(aCallsite->method);
 443         if (!methodName)
 444             return 0;
 445         if (!*aRule->pats[patnum]
 446             || !strncmp(methodName, aRule->pats[patnum],
 447                         aRule->patlen[patnum])) {
 448             /* We have matched so far. Proceed up the stack and to the next pattern */
 449             patnum++;
 450             aCallsite = aCallsite->parent;
 451         }
 452         else {
 453             /* Deal with mismatch */
 454             if (patnum > 0) {
 455                 /* contiguous mismatch. Stop */
 456                 return 0;
 457             }
 458             /* We still haven't matched the first pattern. Proceed up the stack without
 459              ** moving to the next pattern.
 460              */
 461             aCallsite = aCallsite->parent;
 462         }
 463     }
 464
 465     if (patnum == aRule->npats) {
 466         /* all patterns matched. We have a winner. */
 467 #if defined(DEBUG_dp) && 0
 468         fprintf(stderr, "[%s] match\n", aRule->categoryName);
 469 #endif
 470         return 1;
 471     }
 472
 473     return 0;
 474 }
 475
 476 #ifdef DEBUG_dp
 477 PRIntervalTime _gMatchTime = 0;
 478 PRUint32 _gMatchCount = 0;
 479 PRUint32 _gMatchRules = 0;
 480 #endif
 481
 482 /*
 483 ** matchAllocation
 484 **
 485 ** Runs through all rules and returns the node corresponding to
 486 ** a match of the allocation.
 487 */
 488 STCategoryNode *
 489 matchAllocation(STGlobals * g, STAllocation * aAllocation)
 490 {
 491 #ifdef DEBUG_dp
 492     PRIntervalTime start = PR_IntervalNow();
 493 #endif
 494     PRUint32 rulenum;
 495     STCategoryNode *node = NULL;
 496     STCategoryRule *rule;
 497
 498     for (rulenum = 0; rulenum < g->mNRules; rulenum++) {
 499 #ifdef DEBUG_dp
 500         _gMatchRules++;
 501 #endif
 502         rule = g->mCategoryRules[rulenum];
 503         if (callsiteMatchesRule(aAllocation->mEvents[0].mCallsite, rule)) {
 504             node = rule->node;
 505             break;
 506         }
 507     }
 508 #ifdef DEBUG_dp
 509     _gMatchCount++;
 510     _gMatchTime += PR_IntervalNow() - start;
 511 #endif
 512     return node;
 513 }
 514
 515 /*
 516 ** categorizeAllocation
 517 **
 518 ** Given an allocation, it adds it into the category tree at the right spot
 519 ** by comparing the allocation to the rules and adding into the right node.
 520 ** Also, does propogation of cost upwards in the tree.
 521 ** The root of the tree is in the globls as the tree is dependent on the
 522 ** category file (options) rather than the run.
 523 */
 524 int
 525 categorizeAllocation(STOptions * inOptions, STContext * inContext,
 526                      STAllocation * aAllocation, STGlobals * g)
 527 {
 528     /* Run through the rules in order to see if this allcation matches
 529      ** any of them.
 530      */
 531     STCategoryNode *node;
 532
 533     node = matchAllocation(g, aAllocation);
 534     if (!node) {
 535         /* ugh! it should atleast go into the "uncategorized" node. wierd!
 536          */
 537         REPORT_ERROR(__LINE__, categorizeAllocation);
 538         return -1;
 539     }
 540
 541     /* Create run for node if not already */
 542     if (!node->runs[inContext->mIndex]) {
 543         /*
 544          ** Create run with positive timestamp as we can harvest it later
 545          ** for callsite details summarization
 546          */
 547         node->runs[inContext->mIndex] =
 548             createRun(inContext, PR_IntervalNow());
 549         if (!node->runs[inContext->mIndex]) {
 550             REPORT_ERROR(__LINE__, categorizeAllocation_No_Memory);
 551             return -1;
 552         }
 553     }
 554
 555     /* Add allocation into node. We expand the table of allocations in steps */
 556     if (node->runs[inContext->mIndex]->mAllocationCount % ST_ALLOC_STEP == 0) {
 557         /* Need more space */
 558         STAllocation **allocs;
 559
 560         allocs =
 561             (STAllocation **) realloc(node->runs[inContext->mIndex]->
 562                                       mAllocations,
 563                                       (node->runs[inContext->mIndex]->
 564                                        mAllocationCount +
 565                                        ST_ALLOC_STEP) *
 566                                       sizeof(STAllocation *));
 567         if (!allocs) {
 568             REPORT_ERROR(__LINE__, categorizeAllocation_No_Memory);
 569             return -1;
 570         }
 571         node->runs[inContext->mIndex]->mAllocations = allocs;
 572     }
 573     node->runs[inContext->mIndex]->mAllocations[node->
 574                                                 runs[inContext->mIndex]->
 575                                                 mAllocationCount++] =
 576         aAllocation;
 577
 578     /*
 579      ** Make sure run's stats are calculated. We don't go update the parents of allocation
 580      ** at this time. That will happen when we focus on this category. This updating of
 581      ** stats will provide us fast categoryreports.
 582      */
 583     recalculateAllocationCost(inOptions, inContext,
 584                               node->runs[inContext->mIndex], aAllocation,
 585                               PR_FALSE);
 586
 587     /* Propagate upwards the statistics */
 588     /* XXX */
 589 #if defined(DEBUG_dp) && 0
 590     fprintf(stderr, "DEBUG: [%s] match\n", node->categoryName);
 591 #endif
 592     return 0;
 593 }
 594
 595 typedef PRBool STCategoryNodeProcessor(STRequest * inRequest,
 596                                        STOptions * inOptions,
 597                                        STContext * inContext,
 598                                        void *clientData,
 599                                        STCategoryNode * node);
 600
 601 PRBool
 602 freeNodeRunProcessor(STRequest * inRequest, STOptions * inOptions,
 603                      STContext * inContext, void *clientData,
 604                      STCategoryNode * node)
 605 {
 606     if (node->runs && node->runs[inContext->mIndex]) {
 607         freeRun(node->runs[inContext->mIndex]);
 608         node->runs[inContext->mIndex] = NULL;
 609     }
 610     return PR_TRUE;
 611 }
 612
 613 PRBool
 614 freeNodeRunsProcessor(STRequest * inRequest, STOptions * inOptions,
 615                       STContext * inContext, void *clientData,
 616                       STCategoryNode * node)
 617 {
 618     if (node->runs) {
 619         PRUint32 loop = 0;
 620
 621         for (loop = 0; loop < globals.mCommandLineOptions.mContexts; loop++) {
 622             if (node->runs[loop]) {
 623                 freeRun(node->runs[loop]);
 624                 node->runs[loop] = NULL;
 625             }
 626         }
 627
 628         free(node->runs);
 629         node->runs = NULL;
 630     }
 631
 632     return PR_TRUE;
 633 }
 634
 635 #if defined(DEBUG_dp)
 636 PRBool
 637 printNodeProcessor(STRequest * inRequest, STOptions * inOptions,
 638                    STContext * inContext, void *clientData,
 639                    STCategoryNode * node)
 640 {
 641     STCategoryNode *root = (STCategoryNode *) clientData;
 642
 643     fprintf(stderr, "%-25s [ %9s size", node->categoryName,
 644             FormatNumber(node->run ? node->run->mStats[inContext->mIndex].
 645                          mSize : 0));
 646     fprintf(stderr, ", %5.1f%%",
 647             node->run ? ((double) node->run->mStats[inContext->mIndex].mSize /
 648                          root->run->mStats[inContext->mIndex].mSize *
 649                          100) : 0);
 650     fprintf(stderr, ", %7s allocations ]\n",
 651             FormatNumber(node->run ? node->run->mStats[inContext->mIndex].
 652                          mCompositeCount : 0));
 653     return PR_TRUE;
 654 }
 655
 656 #endif
 657
 658 typedef struct __struct_optcon
 659 {
 660     STOptions *mOptions;
 661     STContext *mContext;
 662 }
 663 optcon;
 664
 665 /*
 666 ** compareNode
 667 **
 668 ** qsort callback.
 669 ** Compare the nodes as specified by the options.
 670 */
 671 int
 672 compareNode(const void *aNode1, const void *aNode2, void *aContext)
 673 {
 674     int retval = 0;
 675     STCategoryNode *node1, *node2;
 676     PRUint32 a, b;
 677     optcon *oc = (optcon *) aContext;
 678
 679     if (!aNode1 || !aNode2 || !oc->mOptions || !oc->mContext)
 680         return 0;
 681
 682     node1 = *((STCategoryNode **) aNode1);
 683     node2 = *((STCategoryNode **) aNode2);
 684
 685     if (node1 && node2) {
 686         if (oc->mOptions->mOrderBy == ST_COUNT) {
 687             a = (node1->runs[oc->mContext->mIndex]) ? node1->runs[oc->
 688                                                                   mContext->
 689                                                                   mIndex]->
 690                 mStats[oc->mContext->mIndex].mCompositeCount : 0;
 691             b = (node2->runs[oc->mContext->mIndex]) ? node2->runs[oc->
 692                                                                   mContext->
 693                                                                   mIndex]->
 694                 mStats[oc->mContext->mIndex].mCompositeCount : 0;
 695         }
 696         else {
 697             /* Default is by size */
 698             a = (node1->runs[oc->mContext->mIndex]) ? node1->runs[oc->
 699                                                                   mContext->
 700                                                                   mIndex]->
 701                 mStats[oc->mContext->mIndex].mSize : 0;
 702             b = (node2->runs[oc->mContext->mIndex]) ? node2->runs[oc->
 703                                                                   mContext->
 704                                                                   mIndex]->
 705                 mStats[oc->mContext->mIndex].mSize : 0;
 706         }
 707         if (a < b)
 708             retval = __LINE__;
 709         else
 710             retval = -__LINE__;
 711     }
 712     return retval;
 713 }
 714
 715 PRBool
 716 sortNodeProcessor(STRequest * inRequest, STOptions * inOptions,
 717                   STContext * inContext, void *clientData,
 718                   STCategoryNode * node)
 719 {
 720     if (node->nchildren) {
 721         optcon context;
 722
 723         context.mOptions = inOptions;
 724         context.mContext = inContext;
 725
 726         NS_QuickSort(node->children, node->nchildren,
 727                      sizeof(STCategoryNode *), compareNode, &context);
 728     }
 729
 730     return PR_TRUE;
 731 }
 732
 733
 734 /*
 735 ** walkTree
 736 **
 737 ** General purpose tree walker. Issues callback for each node.
 738 ** If 'maxdepth' > 0, then stops after processing that depth. Root is
 739 ** depth 0, the nodes below it are depth 1 etc...
 740 */
 741 #define MODINC(n, mod) ((n+1) % mod)
 742
 743 void
 744 walkTree(STCategoryNode * root, STCategoryNodeProcessor func,
 745          STRequest * inRequest, STOptions * inOptions, STContext * inContext,
 746          void *clientData, int maxdepth)
 747 {
 748     STCategoryNode *nodes[1024], *node;
 749     PRUint32 begin, end, i;
 750     int ret = 0;
 751     int curdepth = 0, ncurdepth = 0;
 752
 753     nodes[0] = root;
 754     begin = 0;
 755     end = 1;
 756     ncurdepth = 1;
 757     while (begin != end) {
 758         node = nodes[begin];
 759         ret = (*func) (inRequest, inOptions, inContext, clientData, node);
 760         if (ret == PR_FALSE) {
 761             /* Abort */
 762             break;
 763         }
 764         begin = MODINC(begin, 1024);
 765         for (i = 0; i < node->nchildren; i++) {
 766             nodes[end] = node->children[i];
 767             end = MODINC(end, 1024);
 768         }
 769         /* Depth tracking. Do it only if walkTree is contrained by a maxdepth */
 770         if (maxdepth > 0 && --ncurdepth == 0) {
 771             /*
 772              ** No more children in current depth. The rest of the nodes
 773              ** we have in our list should be nodes in the depth below us.
 774              */
 775             ncurdepth = (begin < end) ? (end - begin) : (1024 - begin + end);
 776             if (++curdepth > maxdepth) {
 777                 /*
 778                  ** Gone too deep. Stop.
 779                  */
 780                 break;
 781             }
 782         }
 783     }
 784     return;
 785 }
 786
 787 int
 788 freeRule(STCategoryRule * rule)
 789 {
 790     PRUint32 i;
 791     char *p = (char *) rule->categoryName;
 792
 793     PR_FREEIF(p);
 794
 795     for (i = 0; i < rule->npats; i++)
 796         free(rule->pats[i]);
 797
 798     free(rule);
 799     return 0;
 800 }
 801
 802 void
 803 freeNodeRuns(STCategoryNode * root)
 804 {
 805     walkTree(root, freeNodeRunsProcessor, NULL, NULL, NULL, NULL, 0);
 806 }
 807
 808 void
 809 freeNodeMap(STGlobals * g)
 810 {
 811     PRUint32 i;
 812
 813     /* all nodes are in the map table. Just delete all of those. */
 814     for (i = 0; i < g->mNCategoryMap; i++) {
 815         free(g->mCategoryMap[i]->node);
 816         free(g->mCategoryMap[i]);
 817     }
 818     free(g->mCategoryMap);
 819 }
 820
 821 int
 822 freeCategories(STGlobals * g)
 823 {
 824     PRUint32 i;
 825
 826     /*
 827      ** walk the tree and free runs held in nodes
 828      */
 829     freeNodeRuns(&g->mCategoryRoot);
 830
 831     /*
 832      ** delete nodemap. This is the where nodes get deleted.
 833      */
 834     freeNodeMap(g);
 835
 836     /*
 837      ** delete rule stuff
 838      */
 839     for (i = 0; i < g->mNRules; i++) {
 840         freeRule(g->mCategoryRules[i]);
 841     }
 842     free(g->mCategoryRules);
 843
 844     return 0;
 845 }
 846
 847
 848 /*
 849 ** categorizeRun
 850 **
 851 ** categorize all the allocations of the run using the rules into
 852 ** a tree rooted at globls.mCategoryRoot
 853 */
 854 int
 855 categorizeRun(STOptions * inOptions, STContext * inContext,
 856               const STRun * aRun, STGlobals * g)
 857 {
 858     PRUint32 i;
 859
 860 #if defined(DEBUG_dp)
 861     PRIntervalTime start = PR_IntervalNow();
 862
 863     fprintf(stderr, "DEBUG: categorizing run...\n");
 864 #endif
 865
 866     /*
 867      ** First, cleanup our tree
 868      */
 869     walkTree(&g->mCategoryRoot, freeNodeRunProcessor, NULL, inOptions,
 870              inContext, NULL, 0);
 871
 872     if (g->mNCategoryMap > 0) {
 873         for (i = 0; i < aRun->mAllocationCount; i++) {
 874             categorizeAllocation(inOptions, inContext, aRun->mAllocations[i],
 875                                  g);
 876         }
 877     }
 878
 879     /*
 880      ** the run is always going to be the one corresponding to the root node
 881      */
 882     g->mCategoryRoot.runs[inContext->mIndex] = (STRun *) aRun;
 883     g->mCategoryRoot.categoryName = ST_ROOT_CATEGORY_NAME;
 884
 885 #if defined(DEBUG_dp)
 886     fprintf(stderr,
 887             "DEBUG: categorizing ends: %dms [%d rules, %d allocations]\n",
 888             PR_IntervalToMilliseconds(PR_IntervalNow() - start), g->mNRules,
 889             aRun->mAllocationCount);
 890     fprintf(stderr, "DEBUG: match : %dms [%d calls, %d rule-compares]\n",
 891             PR_IntervalToMilliseconds(_gMatchTime), _gMatchCount,
 892             _gMatchRules);
 893 #endif
 894
 895     /*
 896      ** sort the tree based on our sort criterion
 897      */
 898     walkTree(&g->mCategoryRoot, sortNodeProcessor, NULL, inOptions, inContext,
 899              NULL, 0);
 900
 901 #if defined(DEBUG_dp)
 902     walkTree(&g->mCategoryRoot, printNodeProcessor, NULL, inOptions,
 903              inContext, &g->mCategoryRoot, 0);
 904 #endif
 905
 906     return 0;
 907 }
 908
 909
 910 /*
 911 ** displayCategoryReport
 912 **
 913 ** Generate the category report - a list of all categories and details about each
 914 ** depth parameter controls how deep we traverse the category tree.
 915 */
 916 PRBool
 917 displayCategoryNodeProcessor(STRequest * inRequest, STOptions * inOptions,
 918                              STContext * inContext, void *clientData,
 919                              STCategoryNode * node)
 920 {
 921     STCategoryNode *root = (STCategoryNode *) clientData;
 922     PRUint32 byteSize = 0, heapCost = 0, count = 0;
 923     double percent = 0;
 924     STOptions customOps;
 925
 926     if (node->runs[inContext->mIndex]) {
 927         /*
 928          ** Byte size
 929          */
 930         byteSize =
 931             node->runs[inContext->mIndex]->mStats[inContext->mIndex].mSize;
 932
 933         /*
 934          ** Composite count
 935          */
 936         count =
 937             node->runs[inContext->mIndex]->mStats[inContext->mIndex].
 938             mCompositeCount;
 939
 940         /*
 941          ** Heap operation cost
 942          **/
 943         heapCost =
 944             node->runs[inContext->mIndex]->mStats[inContext->mIndex].
 945             mHeapRuntimeCost;
 946
 947         /*
 948          ** % of total size
 949          */
 950         if (root->runs[inContext->mIndex]) {
 951             percent =
 952                 ((double) byteSize) /
 953                 root->runs[inContext->mIndex]->mStats[inContext->mIndex].
 954                 mSize * 100;
 955         }
 956     }
 957
 958     PR_fprintf(inRequest->mFD, " <tr>\n" "  <td>");
 959
 960     /* a link to topcallsites report with focus on category */
 961     memcpy(&customOps, inOptions, sizeof(customOps));
 962     PR_snprintf(customOps.mCategoryName, sizeof(customOps.mCategoryName),
 963                 "%s", node->categoryName);
 964
 965     htmlAnchor(inRequest, "top_callsites.html", node->categoryName, NULL,
 966                "category-callsites", &customOps);
 967     PR_fprintf(inRequest->mFD,
 968                "</td>\n" "  <td align=right>%u</td>\n"
 969                "  <td align=right>%4.1f%%</td>\n"
 970                "  <td align=right>%u</td>\n" "  <td align=right>"
 971                ST_MICROVAL_FORMAT "</td>\n" " </tr>\n", byteSize, percent,
 972                count, ST_MICROVAL_PRINTABLE(heapCost));
 973
 974     return PR_TRUE;
 975 }
 976
 977
 978 int
 979 displayCategoryReport(STRequest * inRequest, STCategoryNode * root, int depth)
 980 {
 981     PR_fprintf(inRequest->mFD,
 982                "<table class=\"category-list data\">\n"
 983                " <tr class=\"row-header\">\n"
 984                "  <th>Category</th>\n"
 985                "  <th>Composite Byte Size</th>\n"
 986                "  <th>%% of Total Size</th>\n"
 987                "  <th>Heap Object Count</th>\n"
 988                "  <th>Composite Heap Operations Seconds</th>\n" " </tr>\n");
 989
 990     walkTree(root, displayCategoryNodeProcessor, inRequest,
 991              &inRequest->mOptions, inRequest->mContext, root, depth);
 992
 993     PR_fprintf(inRequest->mFD, "</table>\n");
 994
 995     return 0;
 996 }