tools/trace-malloc/spacecategory.c

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