michael@0: /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  *
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: /*
michael@0: ** spacecategory.c
michael@0: **
michael@0: ** Cagtegorizes each allocation using a predefined set of rules
michael@0: ** and presents a tree of categories for browsing.
michael@0: */
michael@0: 
michael@0: /*
michael@0: ** Required include files.
michael@0: */
michael@0: #include "spacetrace.h"
michael@0: #include <ctype.h>
michael@0: #include <string.h>
michael@0: 
michael@0: #include "nsQuickSort.h"
michael@0: 
michael@0: #if defined(HAVE_BOUTELL_GD)
michael@0: /*
michael@0: ** See http://www.boutell.com/gd for the GD graphics library.
michael@0: ** Ports for many platorms exist.
michael@0: ** Your box may already have the lib (mine did, redhat 7.1 workstation).
michael@0: */
michael@0: #include <gd.h>
michael@0: #include <gdfontt.h>
michael@0: #include <gdfonts.h>
michael@0: #include <gdfontmb.h>
michael@0: #endif /* HAVE_BOUTELL_GD */
michael@0: 
michael@0: /*
michael@0: ** AddRule
michael@0: **
michael@0: ** Add a rule into the list of rules maintainted in global
michael@0: */
michael@0: int
michael@0: AddRule(STGlobals * g, STCategoryRule * rule)
michael@0: {
michael@0:     if (g->mNRules % ST_ALLOC_STEP == 0) {
michael@0:         /* Need more space */
michael@0:         STCategoryRule **newrules;
michael@0: 
michael@0:         newrules = (STCategoryRule **) realloc(g->mCategoryRules,
michael@0:                                                (g->mNRules +
michael@0:                                                 ST_ALLOC_STEP) *
michael@0:                                                sizeof(STCategoryRule *));
michael@0:         if (!newrules) {
michael@0:             REPORT_ERROR(__LINE__, AddRule_No_Memory);
michael@0:             return -1;
michael@0:         }
michael@0:         g->mCategoryRules = newrules;
michael@0:     }
michael@0:     g->mCategoryRules[g->mNRules++] = rule;
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: /*
michael@0: ** AddChild
michael@0: **
michael@0: ** Add the node as a child of the parent node
michael@0: */
michael@0: int
michael@0: AddChild(STCategoryNode * parent, STCategoryNode * child)
michael@0: {
michael@0:     if (parent->nchildren % ST_ALLOC_STEP == 0) {
michael@0:         /* need more space */
michael@0:         STCategoryNode **newnodes;
michael@0: 
michael@0:         newnodes = (STCategoryNode **) realloc(parent->children,
michael@0:                                                (parent->nchildren +
michael@0:                                                 ST_ALLOC_STEP) *
michael@0:                                                sizeof(STCategoryNode *));
michael@0:         if (!newnodes) {
michael@0:             REPORT_ERROR(__LINE__, AddChild_No_Memory);
michael@0:             return -1;
michael@0:         }
michael@0:         parent->children = newnodes;
michael@0:     }
michael@0:     parent->children[parent->nchildren++] = child;
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: int
michael@0: Reparent(STCategoryNode * parent, STCategoryNode * child)
michael@0: {
michael@0:     uint32_t i;
michael@0: 
michael@0:     if (child->parent == parent)
michael@0:         return 0;
michael@0: 
michael@0:     /* Remove child from old parent */
michael@0:     if (child->parent) {
michael@0:         for (i = 0; i < child->parent->nchildren; i++) {
michael@0:             if (child->parent->children[i] == child) {
michael@0:                 /* Remove child from list */
michael@0:                 if (i + 1 < child->parent->nchildren)
michael@0:                     memmove(&child->parent->children[i],
michael@0:                             &child->parent->children[i + 1],
michael@0:                             (child->parent->nchildren - i -
michael@0:                              1) * sizeof(STCategoryNode *));
michael@0:                 child->parent->nchildren--;
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* Add child into new parent */
michael@0:     AddChild(parent, child);
michael@0: 
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: /*
michael@0: ** findCategoryNode
michael@0: **
michael@0: ** Given a category name, finds the Node corresponding to the category
michael@0: */
michael@0: STCategoryNode *
michael@0: findCategoryNode(const char *catName, STGlobals * g)
michael@0: {
michael@0:     uint32_t i;
michael@0: 
michael@0:     for (i = 0; i < g->mNCategoryMap; i++) {
michael@0:         if (!strcmp(g->mCategoryMap[i]->categoryName, catName))
michael@0:             return g->mCategoryMap[i]->node;
michael@0:     }
michael@0: 
michael@0:     /* Check if we are looking for the root node */
michael@0:     if (!strcmp(catName, ST_ROOT_CATEGORY_NAME))
michael@0:         return &g->mCategoryRoot;
michael@0: 
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: /*
michael@0: ** AddCategoryNode
michael@0: **
michael@0: ** Adds a mapping between a category and its Node into the categoryMap
michael@0: */
michael@0: int
michael@0: AddCategoryNode(STCategoryNode * node, STGlobals * g)
michael@0: {
michael@0:     if (g->mNCategoryMap % ST_ALLOC_STEP == 0) {
michael@0:         /* Need more space */
michael@0:         STCategoryMapEntry **newmap =
michael@0:             (STCategoryMapEntry **) realloc(g->mCategoryMap,
michael@0:                                             (g->mNCategoryMap +
michael@0:                                              ST_ALLOC_STEP) *
michael@0:                                             sizeof(STCategoryMapEntry *));
michael@0:         if (!newmap) {
michael@0:             REPORT_ERROR(__LINE__, AddCategoryNode_No_Memory);
michael@0:             return -1;
michael@0:         }
michael@0:         g->mCategoryMap = newmap;
michael@0: 
michael@0:     }
michael@0:     g->mCategoryMap[g->mNCategoryMap] =
michael@0:         (STCategoryMapEntry *) calloc(1, sizeof(STCategoryMapEntry));
michael@0:     if (!g->mCategoryMap[g->mNCategoryMap]) {
michael@0:         REPORT_ERROR(__LINE__, AddCategoryNode_No_Memory);
michael@0:         return -1;
michael@0:     }
michael@0:     g->mCategoryMap[g->mNCategoryMap]->categoryName = node->categoryName;
michael@0:     g->mCategoryMap[g->mNCategoryMap]->node = node;
michael@0:     g->mNCategoryMap++;
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: /*
michael@0: ** NewCategoryNode
michael@0: **
michael@0: ** Creates a new category node for category name 'catname' and makes
michael@0: ** 'parent' its parent.
michael@0: */
michael@0: STCategoryNode *
michael@0: NewCategoryNode(const char *catName, STCategoryNode * parent, STGlobals * g)
michael@0: {
michael@0:     STCategoryNode *node;
michael@0: 
michael@0:     node = (STCategoryNode *) calloc(1, sizeof(STCategoryNode));
michael@0:     if (!node)
michael@0:         return NULL;
michael@0: 
michael@0:     node->runs =
michael@0:         (STRun **) calloc(g->mCommandLineOptions.mContexts, sizeof(STRun *));
michael@0:     if (NULL == node->runs) {
michael@0:         free(node);
michael@0:         return NULL;
michael@0:     }
michael@0: 
michael@0:     node->categoryName = catName;
michael@0: 
michael@0:     /* Set parent of child */
michael@0:     node->parent = parent;
michael@0: 
michael@0:     /* Set child in parent */
michael@0:     AddChild(parent, node);
michael@0: 
michael@0:     /* Add node into mapping table */
michael@0:     AddCategoryNode(node, g);
michael@0: 
michael@0:     return node;
michael@0: }
michael@0: 
michael@0: /*
michael@0: ** ProcessCategoryLeafRule
michael@0: **
michael@0: ** Add this into the tree as a leaf node. It doesn't know who its parent is. For now we make
michael@0: ** root as its parent
michael@0: */
michael@0: int
michael@0: ProcessCategoryLeafRule(STCategoryRule * leafRule, STCategoryNode * root,
michael@0:                         STGlobals * g)
michael@0: {
michael@0:     STCategoryRule *rule;
michael@0:     STCategoryNode *node;
michael@0: 
michael@0:     rule = (STCategoryRule *) calloc(1, sizeof(STCategoryRule));
michael@0:     if (!rule)
michael@0:         return -1;
michael@0: 
michael@0:     /* Take ownership of all elements of rule */
michael@0:     *rule = *leafRule;
michael@0: 
michael@0:     /* Find/Make a STCategoryNode and add it into the tree */
michael@0:     node = findCategoryNode(rule->categoryName, g);
michael@0:     if (!node)
michael@0:         node = NewCategoryNode(rule->categoryName, root, g);
michael@0: 
michael@0:     /* Make sure rule knows which node to access */
michael@0:     rule->node = node;
michael@0: 
michael@0:     /* Add rule into rulelist */
michael@0:     AddRule(g, rule);
michael@0: 
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: /*
michael@0: ** ProcessCategoryParentRule
michael@0: **
michael@0: ** Rule has all the children of category as patterns. Sets up the tree so that
michael@0: ** the parent child relationship is honored.
michael@0: */
michael@0: int
michael@0: ProcessCategoryParentRule(STCategoryRule * parentRule, STCategoryNode * root,
michael@0:                           STGlobals * g)
michael@0: {
michael@0:     STCategoryNode *node;
michael@0:     STCategoryNode *child;
michael@0:     uint32_t i;
michael@0: 
michael@0:     /* Find the parent node in the tree. If not make one and add it into the tree */
michael@0:     node = findCategoryNode(parentRule->categoryName, g);
michael@0:     if (!node) {
michael@0:         node = NewCategoryNode(parentRule->categoryName, root, g);
michael@0:         if (!node)
michael@0:             return -1;
michael@0:     }
michael@0: 
michael@0:     /* For every child node, Find/Create it and make it the child of this node */
michael@0:     for (i = 0; i < parentRule->npats; i++) {
michael@0:         child = findCategoryNode(parentRule->pats[i], g);
michael@0:         if (!child) {
michael@0:             child = NewCategoryNode(parentRule->pats[i], node, g);
michael@0:             if (!child)
michael@0:                 return -1;
michael@0:         }
michael@0:         else {
michael@0:             /* Reparent child to node. This is because when we created the node
michael@0:              ** we would have created it as the child of root. Now we need to
michael@0:              ** remove it from root's child list and add it into this node
michael@0:              */
michael@0:             Reparent(node, child);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: /*
michael@0: ** initCategories
michael@0: **
michael@0: ** Initialize all categories. This reads in a file that says how to categorize
michael@0: ** each callsite, creates a tree of these categories and makes a list of these
michael@0: ** patterns in order for matching
michael@0: */
michael@0: int
michael@0: initCategories(STGlobals * g)
michael@0: {
michael@0:     FILE *fp;
michael@0:     char buf[1024], *in;
michael@0:     int n;
michael@0:     PRBool inrule, leaf;
michael@0:     STCategoryRule rule;
michael@0: 
michael@0:     fp = fopen(g->mCommandLineOptions.mCategoryFile, "r");
michael@0:     if (!fp) {
michael@0:         /* It isn't an error to not have a categories file */
michael@0:         REPORT_INFO("No categories file.");
michael@0:         return -1;
michael@0:     }
michael@0: 
michael@0:     inrule = PR_FALSE;
michael@0:     leaf = PR_FALSE;
michael@0: 
michael@0:     memset(&rule, 0, sizeof(rule));
michael@0: 
michael@0:     while (fgets(buf, sizeof(buf), fp) != NULL) {
michael@0:         /* Lose the \n */
michael@0:         n = strlen(buf);
michael@0:         if (buf[n - 1] == '\n')
michael@0:             buf[--n] = '\0';
michael@0:         in = buf;
michael@0: 
michael@0:         /* skip comments */
michael@0:         if (*in == '#')
michael@0:             continue;
michael@0: 
michael@0:         /* skip empty lines. If we are in a rule, end the rule. */
michael@0:         while (*in && isspace(*in))
michael@0:             in++;
michael@0:         if (*in == '\0') {
michael@0:             if (inrule) {
michael@0:                 /* End the rule : leaf or non-leaf */
michael@0:                 if (leaf)
michael@0:                     ProcessCategoryLeafRule(&rule, &g->mCategoryRoot, g);
michael@0:                 else
michael@0:                     /* non-leaf */
michael@0:                     ProcessCategoryParentRule(&rule, &g->mCategoryRoot, g);
michael@0:                 inrule = PR_FALSE;
michael@0:                 memset(&rule, 0, sizeof(rule));
michael@0:             }
michael@0:             continue;
michael@0:         }
michael@0: 
michael@0:         /* if we are in a rule acculumate */
michael@0:         if (inrule) {
michael@0:             rule.pats[rule.npats] = strdup(in);
michael@0:             rule.patlen[rule.npats++] = strlen(in);
michael@0:         }
michael@0:         else if (*in == '<') {
michael@0:             /* Start a category */
michael@0:             inrule = PR_TRUE;
michael@0:             leaf = PR_TRUE;
michael@0: 
michael@0:             /* Get the category name */
michael@0:             in++;
michael@0:             n = strlen(in);
michael@0:             if (in[n - 1] == '>')
michael@0:                 in[n - 1] = '\0';
michael@0:             rule.categoryName = strdup(in);
michael@0:         }
michael@0:         else {
michael@0:             /* this is a non-leaf category. Should be of the form CategoryName
michael@0:              ** followed by list of child category names one per line
michael@0:              */
michael@0:             inrule = PR_TRUE;
michael@0:             leaf = PR_FALSE;
michael@0:             rule.categoryName = strdup(in);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* If we were in a rule when processing the last line, end the rule */
michael@0:     if (inrule) {
michael@0:         /* End the rule : leaf or non-leaf */
michael@0:         if (leaf)
michael@0:             ProcessCategoryLeafRule(&rule, &g->mCategoryRoot, g);
michael@0:         else
michael@0:             /* non-leaf */
michael@0:             ProcessCategoryParentRule(&rule, &g->mCategoryRoot, g);
michael@0:     }
michael@0: 
michael@0:     /* Add the final "uncategorized" category. We make new memory locations
michael@0:      ** for all these to conform to the general principle of all strings are allocated
michael@0:      ** so it makes release logic very simple.
michael@0:      */
michael@0:     memset(&rule, 0, sizeof(rule));
michael@0:     rule.categoryName = strdup("uncategorized");
michael@0:     rule.pats[0] = strdup("");
michael@0:     rule.patlen[0] = 0;
michael@0:     rule.npats = 1;
michael@0:     ProcessCategoryLeafRule(&rule, &g->mCategoryRoot, g);
michael@0: 
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: /*
michael@0: ** callsiteMatchesRule
michael@0: **
michael@0: ** Returns the corresponding node if callsite matches the rule. Rule is a sequence
michael@0: ** of patterns that must match contiguously the callsite.
michael@0: */
michael@0: int
michael@0: callsiteMatchesRule(tmcallsite * aCallsite, STCategoryRule * aRule)
michael@0: {
michael@0:     uint32_t patnum = 0;
michael@0:     const char *methodName = NULL;
michael@0: 
michael@0:     while (patnum < aRule->npats && aCallsite && aCallsite->method) {
michael@0:         methodName = tmmethodnode_name(aCallsite->method);
michael@0:         if (!methodName)
michael@0:             return 0;
michael@0:         if (!*aRule->pats[patnum]
michael@0:             || !strncmp(methodName, aRule->pats[patnum],
michael@0:                         aRule->patlen[patnum])) {
michael@0:             /* We have matched so far. Proceed up the stack and to the next pattern */
michael@0:             patnum++;
michael@0:             aCallsite = aCallsite->parent;
michael@0:         }
michael@0:         else {
michael@0:             /* Deal with mismatch */
michael@0:             if (patnum > 0) {
michael@0:                 /* contiguous mismatch. Stop */
michael@0:                 return 0;
michael@0:             }
michael@0:             /* We still haven't matched the first pattern. Proceed up the stack without
michael@0:              ** moving to the next pattern.
michael@0:              */
michael@0:             aCallsite = aCallsite->parent;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (patnum == aRule->npats) {
michael@0:         /* all patterns matched. We have a winner. */
michael@0: #if defined(DEBUG_dp) && 0
michael@0:         fprintf(stderr, "[%s] match\n", aRule->categoryName);
michael@0: #endif
michael@0:         return 1;
michael@0:     }
michael@0: 
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: #ifdef DEBUG_dp
michael@0: PRIntervalTime _gMatchTime = 0;
michael@0: uint32_t _gMatchCount = 0;
michael@0: uint32_t _gMatchRules = 0;
michael@0: #endif
michael@0: 
michael@0: /*
michael@0: ** matchAllocation
michael@0: **
michael@0: ** Runs through all rules and returns the node corresponding to
michael@0: ** a match of the allocation.
michael@0: */
michael@0: STCategoryNode *
michael@0: matchAllocation(STGlobals * g, STAllocation * aAllocation)
michael@0: {
michael@0: #ifdef DEBUG_dp
michael@0:     PRIntervalTime start = PR_IntervalNow();
michael@0: #endif
michael@0:     uint32_t rulenum;
michael@0:     STCategoryNode *node = NULL;
michael@0:     STCategoryRule *rule;
michael@0: 
michael@0:     for (rulenum = 0; rulenum < g->mNRules; rulenum++) {
michael@0: #ifdef DEBUG_dp
michael@0:         _gMatchRules++;
michael@0: #endif
michael@0:         rule = g->mCategoryRules[rulenum];
michael@0:         if (callsiteMatchesRule(aAllocation->mEvents[0].mCallsite, rule)) {
michael@0:             node = rule->node;
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0: #ifdef DEBUG_dp
michael@0:     _gMatchCount++;
michael@0:     _gMatchTime += PR_IntervalNow() - start;
michael@0: #endif
michael@0:     return node;
michael@0: }
michael@0: 
michael@0: /*
michael@0: ** categorizeAllocation
michael@0: **
michael@0: ** Given an allocation, it adds it into the category tree at the right spot
michael@0: ** by comparing the allocation to the rules and adding into the right node.
michael@0: ** Also, does propogation of cost upwards in the tree.
michael@0: ** The root of the tree is in the globls as the tree is dependent on the
michael@0: ** category file (options) rather than the run.
michael@0: */
michael@0: int
michael@0: categorizeAllocation(STOptions * inOptions, STContext * inContext,
michael@0:                      STAllocation * aAllocation, STGlobals * g)
michael@0: {
michael@0:     /* Run through the rules in order to see if this allcation matches
michael@0:      ** any of them.
michael@0:      */
michael@0:     STCategoryNode *node;
michael@0: 
michael@0:     node = matchAllocation(g, aAllocation);
michael@0:     if (!node) {
michael@0:         /* ugh! it should atleast go into the "uncategorized" node. wierd!
michael@0:          */
michael@0:         REPORT_ERROR(__LINE__, categorizeAllocation);
michael@0:         return -1;
michael@0:     }
michael@0: 
michael@0:     /* Create run for node if not already */
michael@0:     if (!node->runs[inContext->mIndex]) {
michael@0:         /*
michael@0:          ** Create run with positive timestamp as we can harvest it later
michael@0:          ** for callsite details summarization
michael@0:          */
michael@0:         node->runs[inContext->mIndex] =
michael@0:             createRun(inContext, PR_IntervalNow());
michael@0:         if (!node->runs[inContext->mIndex]) {
michael@0:             REPORT_ERROR(__LINE__, categorizeAllocation_No_Memory);
michael@0:             return -1;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* Add allocation into node. We expand the table of allocations in steps */
michael@0:     if (node->runs[inContext->mIndex]->mAllocationCount % ST_ALLOC_STEP == 0) {
michael@0:         /* Need more space */
michael@0:         STAllocation **allocs;
michael@0: 
michael@0:         allocs =
michael@0:             (STAllocation **) realloc(node->runs[inContext->mIndex]->
michael@0:                                       mAllocations,
michael@0:                                       (node->runs[inContext->mIndex]->
michael@0:                                        mAllocationCount +
michael@0:                                        ST_ALLOC_STEP) *
michael@0:                                       sizeof(STAllocation *));
michael@0:         if (!allocs) {
michael@0:             REPORT_ERROR(__LINE__, categorizeAllocation_No_Memory);
michael@0:             return -1;
michael@0:         }
michael@0:         node->runs[inContext->mIndex]->mAllocations = allocs;
michael@0:     }
michael@0:     node->runs[inContext->mIndex]->mAllocations[node->
michael@0:                                                 runs[inContext->mIndex]->
michael@0:                                                 mAllocationCount++] =
michael@0:         aAllocation;
michael@0: 
michael@0:     /*
michael@0:      ** Make sure run's stats are calculated. We don't go update the parents of allocation
michael@0:      ** at this time. That will happen when we focus on this category. This updating of
michael@0:      ** stats will provide us fast categoryreports.
michael@0:      */
michael@0:     recalculateAllocationCost(inOptions, inContext,
michael@0:                               node->runs[inContext->mIndex], aAllocation,
michael@0:                               PR_FALSE);
michael@0: 
michael@0:     /* Propagate upwards the statistics */
michael@0:     /* XXX */
michael@0: #if defined(DEBUG_dp) && 0
michael@0:     fprintf(stderr, "DEBUG: [%s] match\n", node->categoryName);
michael@0: #endif
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: typedef PRBool STCategoryNodeProcessor(STRequest * inRequest,
michael@0:                                        STOptions * inOptions,
michael@0:                                        STContext * inContext,
michael@0:                                        void *clientData,
michael@0:                                        STCategoryNode * node);
michael@0: 
michael@0: PRBool
michael@0: freeNodeRunProcessor(STRequest * inRequest, STOptions * inOptions,
michael@0:                      STContext * inContext, void *clientData,
michael@0:                      STCategoryNode * node)
michael@0: {
michael@0:     if (node->runs && node->runs[inContext->mIndex]) {
michael@0:         freeRun(node->runs[inContext->mIndex]);
michael@0:         node->runs[inContext->mIndex] = NULL;
michael@0:     }
michael@0:     return PR_TRUE;
michael@0: }
michael@0: 
michael@0: PRBool
michael@0: freeNodeRunsProcessor(STRequest * inRequest, STOptions * inOptions,
michael@0:                       STContext * inContext, void *clientData,
michael@0:                       STCategoryNode * node)
michael@0: {
michael@0:     if (node->runs) {
michael@0:         uint32_t loop = 0;
michael@0: 
michael@0:         for (loop = 0; loop < globals.mCommandLineOptions.mContexts; loop++) {
michael@0:             if (node->runs[loop]) {
michael@0:                 freeRun(node->runs[loop]);
michael@0:                 node->runs[loop] = NULL;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         free(node->runs);
michael@0:         node->runs = NULL;
michael@0:     }
michael@0: 
michael@0:     return PR_TRUE;
michael@0: }
michael@0: 
michael@0: #if defined(DEBUG_dp)
michael@0: PRBool
michael@0: printNodeProcessor(STRequest * inRequest, STOptions * inOptions,
michael@0:                    STContext * inContext, void *clientData,
michael@0:                    STCategoryNode * node)
michael@0: {
michael@0:     STCategoryNode *root = (STCategoryNode *) clientData;
michael@0: 
michael@0:     fprintf(stderr, "%-25s [ %9s size", node->categoryName,
michael@0:             FormatNumber(node->run ? node->run->mStats[inContext->mIndex].
michael@0:                          mSize : 0));
michael@0:     fprintf(stderr, ", %5.1f%%",
michael@0:             node->run ? ((double) node->run->mStats[inContext->mIndex].mSize /
michael@0:                          root->run->mStats[inContext->mIndex].mSize *
michael@0:                          100) : 0);
michael@0:     fprintf(stderr, ", %7s allocations ]\n",
michael@0:             FormatNumber(node->run ? node->run->mStats[inContext->mIndex].
michael@0:                          mCompositeCount : 0));
michael@0:     return PR_TRUE;
michael@0: }
michael@0: 
michael@0: #endif
michael@0: 
michael@0: typedef struct __struct_optcon
michael@0: {
michael@0:     STOptions *mOptions;
michael@0:     STContext *mContext;
michael@0: }
michael@0: optcon;
michael@0: 
michael@0: /*
michael@0: ** compareNode
michael@0: **
michael@0: ** qsort callback.
michael@0: ** Compare the nodes as specified by the options.
michael@0: */
michael@0: int
michael@0: compareNode(const void *aNode1, const void *aNode2, void *aContext)
michael@0: {
michael@0:     int retval = 0;
michael@0:     STCategoryNode *node1, *node2;
michael@0:     uint32_t a, b;
michael@0:     optcon *oc = (optcon *) aContext;
michael@0: 
michael@0:     if (!aNode1 || !aNode2 || !oc->mOptions || !oc->mContext)
michael@0:         return 0;
michael@0: 
michael@0:     node1 = *((STCategoryNode **) aNode1);
michael@0:     node2 = *((STCategoryNode **) aNode2);
michael@0: 
michael@0:     if (node1 && node2) {
michael@0:         if (oc->mOptions->mOrderBy == ST_COUNT) {
michael@0:             a = (node1->runs[oc->mContext->mIndex]) ? node1->runs[oc->
michael@0:                                                                   mContext->
michael@0:                                                                   mIndex]->
michael@0:                 mStats[oc->mContext->mIndex].mCompositeCount : 0;
michael@0:             b = (node2->runs[oc->mContext->mIndex]) ? node2->runs[oc->
michael@0:                                                                   mContext->
michael@0:                                                                   mIndex]->
michael@0:                 mStats[oc->mContext->mIndex].mCompositeCount : 0;
michael@0:         }
michael@0:         else {
michael@0:             /* Default is by size */
michael@0:             a = (node1->runs[oc->mContext->mIndex]) ? node1->runs[oc->
michael@0:                                                                   mContext->
michael@0:                                                                   mIndex]->
michael@0:                 mStats[oc->mContext->mIndex].mSize : 0;
michael@0:             b = (node2->runs[oc->mContext->mIndex]) ? node2->runs[oc->
michael@0:                                                                   mContext->
michael@0:                                                                   mIndex]->
michael@0:                 mStats[oc->mContext->mIndex].mSize : 0;
michael@0:         }
michael@0:         if (a < b)
michael@0:             retval = __LINE__;
michael@0:         else
michael@0:             retval = -__LINE__;
michael@0:     }
michael@0:     return retval;
michael@0: }
michael@0: 
michael@0: PRBool
michael@0: sortNodeProcessor(STRequest * inRequest, STOptions * inOptions,
michael@0:                   STContext * inContext, void *clientData,
michael@0:                   STCategoryNode * node)
michael@0: {
michael@0:     if (node->nchildren) {
michael@0:         optcon context;
michael@0: 
michael@0:         context.mOptions = inOptions;
michael@0:         context.mContext = inContext;
michael@0: 
michael@0:         NS_QuickSort(node->children, node->nchildren,
michael@0:                      sizeof(STCategoryNode *), compareNode, &context);
michael@0:     }
michael@0: 
michael@0:     return PR_TRUE;
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0: ** walkTree
michael@0: **
michael@0: ** General purpose tree walker. Issues callback for each node.
michael@0: ** If 'maxdepth' > 0, then stops after processing that depth. Root is
michael@0: ** depth 0, the nodes below it are depth 1 etc...
michael@0: */
michael@0: #define MODINC(n, mod) ((n+1) % mod)
michael@0: 
michael@0: void
michael@0: walkTree(STCategoryNode * root, STCategoryNodeProcessor func,
michael@0:          STRequest * inRequest, STOptions * inOptions, STContext * inContext,
michael@0:          void *clientData, int maxdepth)
michael@0: {
michael@0:     STCategoryNode *nodes[1024], *node;
michael@0:     uint32_t begin, end, i;
michael@0:     int ret = 0;
michael@0:     int curdepth = 0, ncurdepth = 0;
michael@0: 
michael@0:     nodes[0] = root;
michael@0:     begin = 0;
michael@0:     end = 1;
michael@0:     ncurdepth = 1;
michael@0:     while (begin != end) {
michael@0:         node = nodes[begin];
michael@0:         ret = (*func) (inRequest, inOptions, inContext, clientData, node);
michael@0:         if (!ret) {
michael@0:             /* Abort */
michael@0:             break;
michael@0:         }
michael@0:         begin = MODINC(begin, 1024);
michael@0:         for (i = 0; i < node->nchildren; i++) {
michael@0:             nodes[end] = node->children[i];
michael@0:             end = MODINC(end, 1024);
michael@0:         }
michael@0:         /* Depth tracking. Do it only if walkTree is contrained by a maxdepth */
michael@0:         if (maxdepth > 0 && --ncurdepth == 0) {
michael@0:             /*
michael@0:              ** No more children in current depth. The rest of the nodes
michael@0:              ** we have in our list should be nodes in the depth below us.
michael@0:              */
michael@0:             ncurdepth = (begin < end) ? (end - begin) : (1024 - begin + end);
michael@0:             if (++curdepth > maxdepth) {
michael@0:                 /*
michael@0:                  ** Gone too deep. Stop.
michael@0:                  */
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     return;
michael@0: }
michael@0: 
michael@0: int
michael@0: freeRule(STCategoryRule * rule)
michael@0: {
michael@0:     uint32_t i;
michael@0:     char *p = (char *) rule->categoryName;
michael@0: 
michael@0:     PR_FREEIF(p);
michael@0: 
michael@0:     for (i = 0; i < rule->npats; i++)
michael@0:         free(rule->pats[i]);
michael@0: 
michael@0:     free(rule);
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: void
michael@0: freeNodeRuns(STCategoryNode * root)
michael@0: {
michael@0:     walkTree(root, freeNodeRunsProcessor, NULL, NULL, NULL, NULL, 0);
michael@0: }
michael@0: 
michael@0: void
michael@0: freeNodeMap(STGlobals * g)
michael@0: {
michael@0:     uint32_t i;
michael@0: 
michael@0:     /* all nodes are in the map table. Just delete all of those. */
michael@0:     for (i = 0; i < g->mNCategoryMap; i++) {
michael@0:         free(g->mCategoryMap[i]->node);
michael@0:         free(g->mCategoryMap[i]);
michael@0:     }
michael@0:     free(g->mCategoryMap);
michael@0: }
michael@0: 
michael@0: int
michael@0: freeCategories(STGlobals * g)
michael@0: {
michael@0:     uint32_t i;
michael@0: 
michael@0:     /*
michael@0:      ** walk the tree and free runs held in nodes
michael@0:      */
michael@0:     freeNodeRuns(&g->mCategoryRoot);
michael@0: 
michael@0:     /*
michael@0:      ** delete nodemap. This is the where nodes get deleted.
michael@0:      */
michael@0:     freeNodeMap(g);
michael@0: 
michael@0:     /*
michael@0:      ** delete rule stuff
michael@0:      */
michael@0:     for (i = 0; i < g->mNRules; i++) {
michael@0:         freeRule(g->mCategoryRules[i]);
michael@0:     }
michael@0:     free(g->mCategoryRules);
michael@0: 
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0: ** categorizeRun
michael@0: **
michael@0: ** categorize all the allocations of the run using the rules into
michael@0: ** a tree rooted at globls.mCategoryRoot
michael@0: */
michael@0: int
michael@0: categorizeRun(STOptions * inOptions, STContext * inContext,
michael@0:               const STRun * aRun, STGlobals * g)
michael@0: {
michael@0:     uint32_t i;
michael@0: 
michael@0: #if defined(DEBUG_dp)
michael@0:     PRIntervalTime start = PR_IntervalNow();
michael@0: 
michael@0:     fprintf(stderr, "DEBUG: categorizing run...\n");
michael@0: #endif
michael@0: 
michael@0:     /*
michael@0:      ** First, cleanup our tree
michael@0:      */
michael@0:     walkTree(&g->mCategoryRoot, freeNodeRunProcessor, NULL, inOptions,
michael@0:              inContext, NULL, 0);
michael@0: 
michael@0:     if (g->mNCategoryMap > 0) {
michael@0:         for (i = 0; i < aRun->mAllocationCount; i++) {
michael@0:             categorizeAllocation(inOptions, inContext, aRun->mAllocations[i],
michael@0:                                  g);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      ** the run is always going to be the one corresponding to the root node
michael@0:      */
michael@0:     g->mCategoryRoot.runs[inContext->mIndex] = (STRun *) aRun;
michael@0:     g->mCategoryRoot.categoryName = ST_ROOT_CATEGORY_NAME;
michael@0: 
michael@0: #if defined(DEBUG_dp)
michael@0:     fprintf(stderr,
michael@0:             "DEBUG: categorizing ends: %dms [%d rules, %d allocations]\n",
michael@0:             PR_IntervalToMilliseconds(PR_IntervalNow() - start), g->mNRules,
michael@0:             aRun->mAllocationCount);
michael@0:     fprintf(stderr, "DEBUG: match : %dms [%d calls, %d rule-compares]\n",
michael@0:             PR_IntervalToMilliseconds(_gMatchTime), _gMatchCount,
michael@0:             _gMatchRules);
michael@0: #endif
michael@0: 
michael@0:     /*
michael@0:      ** sort the tree based on our sort criterion
michael@0:      */
michael@0:     walkTree(&g->mCategoryRoot, sortNodeProcessor, NULL, inOptions, inContext,
michael@0:              NULL, 0);
michael@0: 
michael@0: #if defined(DEBUG_dp)
michael@0:     walkTree(&g->mCategoryRoot, printNodeProcessor, NULL, inOptions,
michael@0:              inContext, &g->mCategoryRoot, 0);
michael@0: #endif
michael@0: 
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0: ** displayCategoryReport
michael@0: **
michael@0: ** Generate the category report - a list of all categories and details about each
michael@0: ** depth parameter controls how deep we traverse the category tree.
michael@0: */
michael@0: PRBool
michael@0: displayCategoryNodeProcessor(STRequest * inRequest, STOptions * inOptions,
michael@0:                              STContext * inContext, void *clientData,
michael@0:                              STCategoryNode * node)
michael@0: {
michael@0:     STCategoryNode *root = (STCategoryNode *) clientData;
michael@0:     uint32_t byteSize = 0, heapCost = 0, count = 0;
michael@0:     double percent = 0;
michael@0:     STOptions customOps;
michael@0: 
michael@0:     if (node->runs[inContext->mIndex]) {
michael@0:         /*
michael@0:          ** Byte size
michael@0:          */
michael@0:         byteSize =
michael@0:             node->runs[inContext->mIndex]->mStats[inContext->mIndex].mSize;
michael@0: 
michael@0:         /*
michael@0:          ** Composite count
michael@0:          */
michael@0:         count =
michael@0:             node->runs[inContext->mIndex]->mStats[inContext->mIndex].
michael@0:             mCompositeCount;
michael@0: 
michael@0:         /*
michael@0:          ** Heap operation cost
michael@0:          **/
michael@0:         heapCost =
michael@0:             node->runs[inContext->mIndex]->mStats[inContext->mIndex].
michael@0:             mHeapRuntimeCost;
michael@0: 
michael@0:         /*
michael@0:          ** % of total size
michael@0:          */
michael@0:         if (root->runs[inContext->mIndex]) {
michael@0:             percent =
michael@0:                 ((double) byteSize) /
michael@0:                 root->runs[inContext->mIndex]->mStats[inContext->mIndex].
michael@0:                 mSize * 100;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     PR_fprintf(inRequest->mFD, " <tr>\n" "  <td>");
michael@0: 
michael@0:     /* a link to topcallsites report with focus on category */
michael@0:     memcpy(&customOps, inOptions, sizeof(customOps));
michael@0:     PR_snprintf(customOps.mCategoryName, sizeof(customOps.mCategoryName),
michael@0:                 "%s", node->categoryName);
michael@0: 
michael@0:     htmlAnchor(inRequest, "top_callsites.html", node->categoryName, NULL,
michael@0:                "category-callsites", &customOps);
michael@0:     PR_fprintf(inRequest->mFD,
michael@0:                "</td>\n" "  <td align=right>%u</td>\n"
michael@0:                "  <td align=right>%4.1f%%</td>\n"
michael@0:                "  <td align=right>%u</td>\n" "  <td align=right>"
michael@0:                ST_MICROVAL_FORMAT "</td>\n" " </tr>\n", byteSize, percent,
michael@0:                count, ST_MICROVAL_PRINTABLE(heapCost));
michael@0: 
michael@0:     return PR_TRUE;
michael@0: }
michael@0: 
michael@0: 
michael@0: int
michael@0: displayCategoryReport(STRequest * inRequest, STCategoryNode * root, int depth)
michael@0: {
michael@0:     PR_fprintf(inRequest->mFD,
michael@0:                "<table class=\"category-list data\">\n"
michael@0:                " <tr class=\"row-header\">\n"
michael@0:                "  <th>Category</th>\n"
michael@0:                "  <th>Composite Byte Size</th>\n"
michael@0:                "  <th>%% of Total Size</th>\n"
michael@0:                "  <th>Heap Object Count</th>\n"
michael@0:                "  <th>Composite Heap Operations Seconds</th>\n" " </tr>\n");
michael@0: 
michael@0:     walkTree(root, displayCategoryNodeProcessor, inRequest,
michael@0:              &inRequest->mOptions, inRequest->mContext, root, depth);
michael@0: 
michael@0:     PR_fprintf(inRequest->mFD, "</table>\n");
michael@0: 
michael@0:     return 0;
michael@0: }