1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tools/trace-malloc/spacecategory.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,959 @@
1.4 +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + *
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +/*
1.11 +** spacecategory.c
1.12 +**
1.13 +** Cagtegorizes each allocation using a predefined set of rules
1.14 +** and presents a tree of categories for browsing.
1.15 +*/
1.16 +
1.17 +/*
1.18 +** Required include files.
1.19 +*/
1.20 +#include "spacetrace.h"
1.21 +#include <ctype.h>
1.22 +#include <string.h>
1.23 +
1.24 +#include "nsQuickSort.h"
1.25 +
1.26 +#if defined(HAVE_BOUTELL_GD)
1.27 +/*
1.28 +** See http://www.boutell.com/gd for the GD graphics library.
1.29 +** Ports for many platorms exist.
1.30 +** Your box may already have the lib (mine did, redhat 7.1 workstation).
1.31 +*/
1.32 +#include <gd.h>
1.33 +#include <gdfontt.h>
1.34 +#include <gdfonts.h>
1.35 +#include <gdfontmb.h>
1.36 +#endif /* HAVE_BOUTELL_GD */
1.37 +
1.38 +/*
1.39 +** AddRule
1.40 +**
1.41 +** Add a rule into the list of rules maintainted in global
1.42 +*/
1.43 +int
1.44 +AddRule(STGlobals * g, STCategoryRule * rule)
1.45 +{
1.46 + if (g->mNRules % ST_ALLOC_STEP == 0) {
1.47 + /* Need more space */
1.48 + STCategoryRule **newrules;
1.49 +
1.50 + newrules = (STCategoryRule **) realloc(g->mCategoryRules,
1.51 + (g->mNRules +
1.52 + ST_ALLOC_STEP) *
1.53 + sizeof(STCategoryRule *));
1.54 + if (!newrules) {
1.55 + REPORT_ERROR(__LINE__, AddRule_No_Memory);
1.56 + return -1;
1.57 + }
1.58 + g->mCategoryRules = newrules;
1.59 + }
1.60 + g->mCategoryRules[g->mNRules++] = rule;
1.61 + return 0;
1.62 +}
1.63 +
1.64 +/*
1.65 +** AddChild
1.66 +**
1.67 +** Add the node as a child of the parent node
1.68 +*/
1.69 +int
1.70 +AddChild(STCategoryNode * parent, STCategoryNode * child)
1.71 +{
1.72 + if (parent->nchildren % ST_ALLOC_STEP == 0) {
1.73 + /* need more space */
1.74 + STCategoryNode **newnodes;
1.75 +
1.76 + newnodes = (STCategoryNode **) realloc(parent->children,
1.77 + (parent->nchildren +
1.78 + ST_ALLOC_STEP) *
1.79 + sizeof(STCategoryNode *));
1.80 + if (!newnodes) {
1.81 + REPORT_ERROR(__LINE__, AddChild_No_Memory);
1.82 + return -1;
1.83 + }
1.84 + parent->children = newnodes;
1.85 + }
1.86 + parent->children[parent->nchildren++] = child;
1.87 + return 0;
1.88 +}
1.89 +
1.90 +int
1.91 +Reparent(STCategoryNode * parent, STCategoryNode * child)
1.92 +{
1.93 + uint32_t i;
1.94 +
1.95 + if (child->parent == parent)
1.96 + return 0;
1.97 +
1.98 + /* Remove child from old parent */
1.99 + if (child->parent) {
1.100 + for (i = 0; i < child->parent->nchildren; i++) {
1.101 + if (child->parent->children[i] == child) {
1.102 + /* Remove child from list */
1.103 + if (i + 1 < child->parent->nchildren)
1.104 + memmove(&child->parent->children[i],
1.105 + &child->parent->children[i + 1],
1.106 + (child->parent->nchildren - i -
1.107 + 1) * sizeof(STCategoryNode *));
1.108 + child->parent->nchildren--;
1.109 + break;
1.110 + }
1.111 + }
1.112 + }
1.113 +
1.114 + /* Add child into new parent */
1.115 + AddChild(parent, child);
1.116 +
1.117 + return 0;
1.118 +}
1.119 +
1.120 +/*
1.121 +** findCategoryNode
1.122 +**
1.123 +** Given a category name, finds the Node corresponding to the category
1.124 +*/
1.125 +STCategoryNode *
1.126 +findCategoryNode(const char *catName, STGlobals * g)
1.127 +{
1.128 + uint32_t i;
1.129 +
1.130 + for (i = 0; i < g->mNCategoryMap; i++) {
1.131 + if (!strcmp(g->mCategoryMap[i]->categoryName, catName))
1.132 + return g->mCategoryMap[i]->node;
1.133 + }
1.134 +
1.135 + /* Check if we are looking for the root node */
1.136 + if (!strcmp(catName, ST_ROOT_CATEGORY_NAME))
1.137 + return &g->mCategoryRoot;
1.138 +
1.139 + return NULL;
1.140 +}
1.141 +
1.142 +/*
1.143 +** AddCategoryNode
1.144 +**
1.145 +** Adds a mapping between a category and its Node into the categoryMap
1.146 +*/
1.147 +int
1.148 +AddCategoryNode(STCategoryNode * node, STGlobals * g)
1.149 +{
1.150 + if (g->mNCategoryMap % ST_ALLOC_STEP == 0) {
1.151 + /* Need more space */
1.152 + STCategoryMapEntry **newmap =
1.153 + (STCategoryMapEntry **) realloc(g->mCategoryMap,
1.154 + (g->mNCategoryMap +
1.155 + ST_ALLOC_STEP) *
1.156 + sizeof(STCategoryMapEntry *));
1.157 + if (!newmap) {
1.158 + REPORT_ERROR(__LINE__, AddCategoryNode_No_Memory);
1.159 + return -1;
1.160 + }
1.161 + g->mCategoryMap = newmap;
1.162 +
1.163 + }
1.164 + g->mCategoryMap[g->mNCategoryMap] =
1.165 + (STCategoryMapEntry *) calloc(1, sizeof(STCategoryMapEntry));
1.166 + if (!g->mCategoryMap[g->mNCategoryMap]) {
1.167 + REPORT_ERROR(__LINE__, AddCategoryNode_No_Memory);
1.168 + return -1;
1.169 + }
1.170 + g->mCategoryMap[g->mNCategoryMap]->categoryName = node->categoryName;
1.171 + g->mCategoryMap[g->mNCategoryMap]->node = node;
1.172 + g->mNCategoryMap++;
1.173 + return 0;
1.174 +}
1.175 +
1.176 +/*
1.177 +** NewCategoryNode
1.178 +**
1.179 +** Creates a new category node for category name 'catname' and makes
1.180 +** 'parent' its parent.
1.181 +*/
1.182 +STCategoryNode *
1.183 +NewCategoryNode(const char *catName, STCategoryNode * parent, STGlobals * g)
1.184 +{
1.185 + STCategoryNode *node;
1.186 +
1.187 + node = (STCategoryNode *) calloc(1, sizeof(STCategoryNode));
1.188 + if (!node)
1.189 + return NULL;
1.190 +
1.191 + node->runs =
1.192 + (STRun **) calloc(g->mCommandLineOptions.mContexts, sizeof(STRun *));
1.193 + if (NULL == node->runs) {
1.194 + free(node);
1.195 + return NULL;
1.196 + }
1.197 +
1.198 + node->categoryName = catName;
1.199 +
1.200 + /* Set parent of child */
1.201 + node->parent = parent;
1.202 +
1.203 + /* Set child in parent */
1.204 + AddChild(parent, node);
1.205 +
1.206 + /* Add node into mapping table */
1.207 + AddCategoryNode(node, g);
1.208 +
1.209 + return node;
1.210 +}
1.211 +
1.212 +/*
1.213 +** ProcessCategoryLeafRule
1.214 +**
1.215 +** Add this into the tree as a leaf node. It doesn't know who its parent is. For now we make
1.216 +** root as its parent
1.217 +*/
1.218 +int
1.219 +ProcessCategoryLeafRule(STCategoryRule * leafRule, STCategoryNode * root,
1.220 + STGlobals * g)
1.221 +{
1.222 + STCategoryRule *rule;
1.223 + STCategoryNode *node;
1.224 +
1.225 + rule = (STCategoryRule *) calloc(1, sizeof(STCategoryRule));
1.226 + if (!rule)
1.227 + return -1;
1.228 +
1.229 + /* Take ownership of all elements of rule */
1.230 + *rule = *leafRule;
1.231 +
1.232 + /* Find/Make a STCategoryNode and add it into the tree */
1.233 + node = findCategoryNode(rule->categoryName, g);
1.234 + if (!node)
1.235 + node = NewCategoryNode(rule->categoryName, root, g);
1.236 +
1.237 + /* Make sure rule knows which node to access */
1.238 + rule->node = node;
1.239 +
1.240 + /* Add rule into rulelist */
1.241 + AddRule(g, rule);
1.242 +
1.243 + return 0;
1.244 +}
1.245 +
1.246 +/*
1.247 +** ProcessCategoryParentRule
1.248 +**
1.249 +** Rule has all the children of category as patterns. Sets up the tree so that
1.250 +** the parent child relationship is honored.
1.251 +*/
1.252 +int
1.253 +ProcessCategoryParentRule(STCategoryRule * parentRule, STCategoryNode * root,
1.254 + STGlobals * g)
1.255 +{
1.256 + STCategoryNode *node;
1.257 + STCategoryNode *child;
1.258 + uint32_t i;
1.259 +
1.260 + /* Find the parent node in the tree. If not make one and add it into the tree */
1.261 + node = findCategoryNode(parentRule->categoryName, g);
1.262 + if (!node) {
1.263 + node = NewCategoryNode(parentRule->categoryName, root, g);
1.264 + if (!node)
1.265 + return -1;
1.266 + }
1.267 +
1.268 + /* For every child node, Find/Create it and make it the child of this node */
1.269 + for (i = 0; i < parentRule->npats; i++) {
1.270 + child = findCategoryNode(parentRule->pats[i], g);
1.271 + if (!child) {
1.272 + child = NewCategoryNode(parentRule->pats[i], node, g);
1.273 + if (!child)
1.274 + return -1;
1.275 + }
1.276 + else {
1.277 + /* Reparent child to node. This is because when we created the node
1.278 + ** we would have created it as the child of root. Now we need to
1.279 + ** remove it from root's child list and add it into this node
1.280 + */
1.281 + Reparent(node, child);
1.282 + }
1.283 + }
1.284 +
1.285 + return 0;
1.286 +}
1.287 +
1.288 +/*
1.289 +** initCategories
1.290 +**
1.291 +** Initialize all categories. This reads in a file that says how to categorize
1.292 +** each callsite, creates a tree of these categories and makes a list of these
1.293 +** patterns in order for matching
1.294 +*/
1.295 +int
1.296 +initCategories(STGlobals * g)
1.297 +{
1.298 + FILE *fp;
1.299 + char buf[1024], *in;
1.300 + int n;
1.301 + PRBool inrule, leaf;
1.302 + STCategoryRule rule;
1.303 +
1.304 + fp = fopen(g->mCommandLineOptions.mCategoryFile, "r");
1.305 + if (!fp) {
1.306 + /* It isn't an error to not have a categories file */
1.307 + REPORT_INFO("No categories file.");
1.308 + return -1;
1.309 + }
1.310 +
1.311 + inrule = PR_FALSE;
1.312 + leaf = PR_FALSE;
1.313 +
1.314 + memset(&rule, 0, sizeof(rule));
1.315 +
1.316 + while (fgets(buf, sizeof(buf), fp) != NULL) {
1.317 + /* Lose the \n */
1.318 + n = strlen(buf);
1.319 + if (buf[n - 1] == '\n')
1.320 + buf[--n] = '\0';
1.321 + in = buf;
1.322 +
1.323 + /* skip comments */
1.324 + if (*in == '#')
1.325 + continue;
1.326 +
1.327 + /* skip empty lines. If we are in a rule, end the rule. */
1.328 + while (*in && isspace(*in))
1.329 + in++;
1.330 + if (*in == '\0') {
1.331 + if (inrule) {
1.332 + /* End the rule : leaf or non-leaf */
1.333 + if (leaf)
1.334 + ProcessCategoryLeafRule(&rule, &g->mCategoryRoot, g);
1.335 + else
1.336 + /* non-leaf */
1.337 + ProcessCategoryParentRule(&rule, &g->mCategoryRoot, g);
1.338 + inrule = PR_FALSE;
1.339 + memset(&rule, 0, sizeof(rule));
1.340 + }
1.341 + continue;
1.342 + }
1.343 +
1.344 + /* if we are in a rule acculumate */
1.345 + if (inrule) {
1.346 + rule.pats[rule.npats] = strdup(in);
1.347 + rule.patlen[rule.npats++] = strlen(in);
1.348 + }
1.349 + else if (*in == '<') {
1.350 + /* Start a category */
1.351 + inrule = PR_TRUE;
1.352 + leaf = PR_TRUE;
1.353 +
1.354 + /* Get the category name */
1.355 + in++;
1.356 + n = strlen(in);
1.357 + if (in[n - 1] == '>')
1.358 + in[n - 1] = '\0';
1.359 + rule.categoryName = strdup(in);
1.360 + }
1.361 + else {
1.362 + /* this is a non-leaf category. Should be of the form CategoryName
1.363 + ** followed by list of child category names one per line
1.364 + */
1.365 + inrule = PR_TRUE;
1.366 + leaf = PR_FALSE;
1.367 + rule.categoryName = strdup(in);
1.368 + }
1.369 + }
1.370 +
1.371 + /* If we were in a rule when processing the last line, end the rule */
1.372 + if (inrule) {
1.373 + /* End the rule : leaf or non-leaf */
1.374 + if (leaf)
1.375 + ProcessCategoryLeafRule(&rule, &g->mCategoryRoot, g);
1.376 + else
1.377 + /* non-leaf */
1.378 + ProcessCategoryParentRule(&rule, &g->mCategoryRoot, g);
1.379 + }
1.380 +
1.381 + /* Add the final "uncategorized" category. We make new memory locations
1.382 + ** for all these to conform to the general principle of all strings are allocated
1.383 + ** so it makes release logic very simple.
1.384 + */
1.385 + memset(&rule, 0, sizeof(rule));
1.386 + rule.categoryName = strdup("uncategorized");
1.387 + rule.pats[0] = strdup("");
1.388 + rule.patlen[0] = 0;
1.389 + rule.npats = 1;
1.390 + ProcessCategoryLeafRule(&rule, &g->mCategoryRoot, g);
1.391 +
1.392 + return 0;
1.393 +}
1.394 +
1.395 +/*
1.396 +** callsiteMatchesRule
1.397 +**
1.398 +** Returns the corresponding node if callsite matches the rule. Rule is a sequence
1.399 +** of patterns that must match contiguously the callsite.
1.400 +*/
1.401 +int
1.402 +callsiteMatchesRule(tmcallsite * aCallsite, STCategoryRule * aRule)
1.403 +{
1.404 + uint32_t patnum = 0;
1.405 + const char *methodName = NULL;
1.406 +
1.407 + while (patnum < aRule->npats && aCallsite && aCallsite->method) {
1.408 + methodName = tmmethodnode_name(aCallsite->method);
1.409 + if (!methodName)
1.410 + return 0;
1.411 + if (!*aRule->pats[patnum]
1.412 + || !strncmp(methodName, aRule->pats[patnum],
1.413 + aRule->patlen[patnum])) {
1.414 + /* We have matched so far. Proceed up the stack and to the next pattern */
1.415 + patnum++;
1.416 + aCallsite = aCallsite->parent;
1.417 + }
1.418 + else {
1.419 + /* Deal with mismatch */
1.420 + if (patnum > 0) {
1.421 + /* contiguous mismatch. Stop */
1.422 + return 0;
1.423 + }
1.424 + /* We still haven't matched the first pattern. Proceed up the stack without
1.425 + ** moving to the next pattern.
1.426 + */
1.427 + aCallsite = aCallsite->parent;
1.428 + }
1.429 + }
1.430 +
1.431 + if (patnum == aRule->npats) {
1.432 + /* all patterns matched. We have a winner. */
1.433 +#if defined(DEBUG_dp) && 0
1.434 + fprintf(stderr, "[%s] match\n", aRule->categoryName);
1.435 +#endif
1.436 + return 1;
1.437 + }
1.438 +
1.439 + return 0;
1.440 +}
1.441 +
1.442 +#ifdef DEBUG_dp
1.443 +PRIntervalTime _gMatchTime = 0;
1.444 +uint32_t _gMatchCount = 0;
1.445 +uint32_t _gMatchRules = 0;
1.446 +#endif
1.447 +
1.448 +/*
1.449 +** matchAllocation
1.450 +**
1.451 +** Runs through all rules and returns the node corresponding to
1.452 +** a match of the allocation.
1.453 +*/
1.454 +STCategoryNode *
1.455 +matchAllocation(STGlobals * g, STAllocation * aAllocation)
1.456 +{
1.457 +#ifdef DEBUG_dp
1.458 + PRIntervalTime start = PR_IntervalNow();
1.459 +#endif
1.460 + uint32_t rulenum;
1.461 + STCategoryNode *node = NULL;
1.462 + STCategoryRule *rule;
1.463 +
1.464 + for (rulenum = 0; rulenum < g->mNRules; rulenum++) {
1.465 +#ifdef DEBUG_dp
1.466 + _gMatchRules++;
1.467 +#endif
1.468 + rule = g->mCategoryRules[rulenum];
1.469 + if (callsiteMatchesRule(aAllocation->mEvents[0].mCallsite, rule)) {
1.470 + node = rule->node;
1.471 + break;
1.472 + }
1.473 + }
1.474 +#ifdef DEBUG_dp
1.475 + _gMatchCount++;
1.476 + _gMatchTime += PR_IntervalNow() - start;
1.477 +#endif
1.478 + return node;
1.479 +}
1.480 +
1.481 +/*
1.482 +** categorizeAllocation
1.483 +**
1.484 +** Given an allocation, it adds it into the category tree at the right spot
1.485 +** by comparing the allocation to the rules and adding into the right node.
1.486 +** Also, does propogation of cost upwards in the tree.
1.487 +** The root of the tree is in the globls as the tree is dependent on the
1.488 +** category file (options) rather than the run.
1.489 +*/
1.490 +int
1.491 +categorizeAllocation(STOptions * inOptions, STContext * inContext,
1.492 + STAllocation * aAllocation, STGlobals * g)
1.493 +{
1.494 + /* Run through the rules in order to see if this allcation matches
1.495 + ** any of them.
1.496 + */
1.497 + STCategoryNode *node;
1.498 +
1.499 + node = matchAllocation(g, aAllocation);
1.500 + if (!node) {
1.501 + /* ugh! it should atleast go into the "uncategorized" node. wierd!
1.502 + */
1.503 + REPORT_ERROR(__LINE__, categorizeAllocation);
1.504 + return -1;
1.505 + }
1.506 +
1.507 + /* Create run for node if not already */
1.508 + if (!node->runs[inContext->mIndex]) {
1.509 + /*
1.510 + ** Create run with positive timestamp as we can harvest it later
1.511 + ** for callsite details summarization
1.512 + */
1.513 + node->runs[inContext->mIndex] =
1.514 + createRun(inContext, PR_IntervalNow());
1.515 + if (!node->runs[inContext->mIndex]) {
1.516 + REPORT_ERROR(__LINE__, categorizeAllocation_No_Memory);
1.517 + return -1;
1.518 + }
1.519 + }
1.520 +
1.521 + /* Add allocation into node. We expand the table of allocations in steps */
1.522 + if (node->runs[inContext->mIndex]->mAllocationCount % ST_ALLOC_STEP == 0) {
1.523 + /* Need more space */
1.524 + STAllocation **allocs;
1.525 +
1.526 + allocs =
1.527 + (STAllocation **) realloc(node->runs[inContext->mIndex]->
1.528 + mAllocations,
1.529 + (node->runs[inContext->mIndex]->
1.530 + mAllocationCount +
1.531 + ST_ALLOC_STEP) *
1.532 + sizeof(STAllocation *));
1.533 + if (!allocs) {
1.534 + REPORT_ERROR(__LINE__, categorizeAllocation_No_Memory);
1.535 + return -1;
1.536 + }
1.537 + node->runs[inContext->mIndex]->mAllocations = allocs;
1.538 + }
1.539 + node->runs[inContext->mIndex]->mAllocations[node->
1.540 + runs[inContext->mIndex]->
1.541 + mAllocationCount++] =
1.542 + aAllocation;
1.543 +
1.544 + /*
1.545 + ** Make sure run's stats are calculated. We don't go update the parents of allocation
1.546 + ** at this time. That will happen when we focus on this category. This updating of
1.547 + ** stats will provide us fast categoryreports.
1.548 + */
1.549 + recalculateAllocationCost(inOptions, inContext,
1.550 + node->runs[inContext->mIndex], aAllocation,
1.551 + PR_FALSE);
1.552 +
1.553 + /* Propagate upwards the statistics */
1.554 + /* XXX */
1.555 +#if defined(DEBUG_dp) && 0
1.556 + fprintf(stderr, "DEBUG: [%s] match\n", node->categoryName);
1.557 +#endif
1.558 + return 0;
1.559 +}
1.560 +
1.561 +typedef PRBool STCategoryNodeProcessor(STRequest * inRequest,
1.562 + STOptions * inOptions,
1.563 + STContext * inContext,
1.564 + void *clientData,
1.565 + STCategoryNode * node);
1.566 +
1.567 +PRBool
1.568 +freeNodeRunProcessor(STRequest * inRequest, STOptions * inOptions,
1.569 + STContext * inContext, void *clientData,
1.570 + STCategoryNode * node)
1.571 +{
1.572 + if (node->runs && node->runs[inContext->mIndex]) {
1.573 + freeRun(node->runs[inContext->mIndex]);
1.574 + node->runs[inContext->mIndex] = NULL;
1.575 + }
1.576 + return PR_TRUE;
1.577 +}
1.578 +
1.579 +PRBool
1.580 +freeNodeRunsProcessor(STRequest * inRequest, STOptions * inOptions,
1.581 + STContext * inContext, void *clientData,
1.582 + STCategoryNode * node)
1.583 +{
1.584 + if (node->runs) {
1.585 + uint32_t loop = 0;
1.586 +
1.587 + for (loop = 0; loop < globals.mCommandLineOptions.mContexts; loop++) {
1.588 + if (node->runs[loop]) {
1.589 + freeRun(node->runs[loop]);
1.590 + node->runs[loop] = NULL;
1.591 + }
1.592 + }
1.593 +
1.594 + free(node->runs);
1.595 + node->runs = NULL;
1.596 + }
1.597 +
1.598 + return PR_TRUE;
1.599 +}
1.600 +
1.601 +#if defined(DEBUG_dp)
1.602 +PRBool
1.603 +printNodeProcessor(STRequest * inRequest, STOptions * inOptions,
1.604 + STContext * inContext, void *clientData,
1.605 + STCategoryNode * node)
1.606 +{
1.607 + STCategoryNode *root = (STCategoryNode *) clientData;
1.608 +
1.609 + fprintf(stderr, "%-25s [ %9s size", node->categoryName,
1.610 + FormatNumber(node->run ? node->run->mStats[inContext->mIndex].
1.611 + mSize : 0));
1.612 + fprintf(stderr, ", %5.1f%%",
1.613 + node->run ? ((double) node->run->mStats[inContext->mIndex].mSize /
1.614 + root->run->mStats[inContext->mIndex].mSize *
1.615 + 100) : 0);
1.616 + fprintf(stderr, ", %7s allocations ]\n",
1.617 + FormatNumber(node->run ? node->run->mStats[inContext->mIndex].
1.618 + mCompositeCount : 0));
1.619 + return PR_TRUE;
1.620 +}
1.621 +
1.622 +#endif
1.623 +
1.624 +typedef struct __struct_optcon
1.625 +{
1.626 + STOptions *mOptions;
1.627 + STContext *mContext;
1.628 +}
1.629 +optcon;
1.630 +
1.631 +/*
1.632 +** compareNode
1.633 +**
1.634 +** qsort callback.
1.635 +** Compare the nodes as specified by the options.
1.636 +*/
1.637 +int
1.638 +compareNode(const void *aNode1, const void *aNode2, void *aContext)
1.639 +{
1.640 + int retval = 0;
1.641 + STCategoryNode *node1, *node2;
1.642 + uint32_t a, b;
1.643 + optcon *oc = (optcon *) aContext;
1.644 +
1.645 + if (!aNode1 || !aNode2 || !oc->mOptions || !oc->mContext)
1.646 + return 0;
1.647 +
1.648 + node1 = *((STCategoryNode **) aNode1);
1.649 + node2 = *((STCategoryNode **) aNode2);
1.650 +
1.651 + if (node1 && node2) {
1.652 + if (oc->mOptions->mOrderBy == ST_COUNT) {
1.653 + a = (node1->runs[oc->mContext->mIndex]) ? node1->runs[oc->
1.654 + mContext->
1.655 + mIndex]->
1.656 + mStats[oc->mContext->mIndex].mCompositeCount : 0;
1.657 + b = (node2->runs[oc->mContext->mIndex]) ? node2->runs[oc->
1.658 + mContext->
1.659 + mIndex]->
1.660 + mStats[oc->mContext->mIndex].mCompositeCount : 0;
1.661 + }
1.662 + else {
1.663 + /* Default is by size */
1.664 + a = (node1->runs[oc->mContext->mIndex]) ? node1->runs[oc->
1.665 + mContext->
1.666 + mIndex]->
1.667 + mStats[oc->mContext->mIndex].mSize : 0;
1.668 + b = (node2->runs[oc->mContext->mIndex]) ? node2->runs[oc->
1.669 + mContext->
1.670 + mIndex]->
1.671 + mStats[oc->mContext->mIndex].mSize : 0;
1.672 + }
1.673 + if (a < b)
1.674 + retval = __LINE__;
1.675 + else
1.676 + retval = -__LINE__;
1.677 + }
1.678 + return retval;
1.679 +}
1.680 +
1.681 +PRBool
1.682 +sortNodeProcessor(STRequest * inRequest, STOptions * inOptions,
1.683 + STContext * inContext, void *clientData,
1.684 + STCategoryNode * node)
1.685 +{
1.686 + if (node->nchildren) {
1.687 + optcon context;
1.688 +
1.689 + context.mOptions = inOptions;
1.690 + context.mContext = inContext;
1.691 +
1.692 + NS_QuickSort(node->children, node->nchildren,
1.693 + sizeof(STCategoryNode *), compareNode, &context);
1.694 + }
1.695 +
1.696 + return PR_TRUE;
1.697 +}
1.698 +
1.699 +
1.700 +/*
1.701 +** walkTree
1.702 +**
1.703 +** General purpose tree walker. Issues callback for each node.
1.704 +** If 'maxdepth' > 0, then stops after processing that depth. Root is
1.705 +** depth 0, the nodes below it are depth 1 etc...
1.706 +*/
1.707 +#define MODINC(n, mod) ((n+1) % mod)
1.708 +
1.709 +void
1.710 +walkTree(STCategoryNode * root, STCategoryNodeProcessor func,
1.711 + STRequest * inRequest, STOptions * inOptions, STContext * inContext,
1.712 + void *clientData, int maxdepth)
1.713 +{
1.714 + STCategoryNode *nodes[1024], *node;
1.715 + uint32_t begin, end, i;
1.716 + int ret = 0;
1.717 + int curdepth = 0, ncurdepth = 0;
1.718 +
1.719 + nodes[0] = root;
1.720 + begin = 0;
1.721 + end = 1;
1.722 + ncurdepth = 1;
1.723 + while (begin != end) {
1.724 + node = nodes[begin];
1.725 + ret = (*func) (inRequest, inOptions, inContext, clientData, node);
1.726 + if (!ret) {
1.727 + /* Abort */
1.728 + break;
1.729 + }
1.730 + begin = MODINC(begin, 1024);
1.731 + for (i = 0; i < node->nchildren; i++) {
1.732 + nodes[end] = node->children[i];
1.733 + end = MODINC(end, 1024);
1.734 + }
1.735 + /* Depth tracking. Do it only if walkTree is contrained by a maxdepth */
1.736 + if (maxdepth > 0 && --ncurdepth == 0) {
1.737 + /*
1.738 + ** No more children in current depth. The rest of the nodes
1.739 + ** we have in our list should be nodes in the depth below us.
1.740 + */
1.741 + ncurdepth = (begin < end) ? (end - begin) : (1024 - begin + end);
1.742 + if (++curdepth > maxdepth) {
1.743 + /*
1.744 + ** Gone too deep. Stop.
1.745 + */
1.746 + break;
1.747 + }
1.748 + }
1.749 + }
1.750 + return;
1.751 +}
1.752 +
1.753 +int
1.754 +freeRule(STCategoryRule * rule)
1.755 +{
1.756 + uint32_t i;
1.757 + char *p = (char *) rule->categoryName;
1.758 +
1.759 + PR_FREEIF(p);
1.760 +
1.761 + for (i = 0; i < rule->npats; i++)
1.762 + free(rule->pats[i]);
1.763 +
1.764 + free(rule);
1.765 + return 0;
1.766 +}
1.767 +
1.768 +void
1.769 +freeNodeRuns(STCategoryNode * root)
1.770 +{
1.771 + walkTree(root, freeNodeRunsProcessor, NULL, NULL, NULL, NULL, 0);
1.772 +}
1.773 +
1.774 +void
1.775 +freeNodeMap(STGlobals * g)
1.776 +{
1.777 + uint32_t i;
1.778 +
1.779 + /* all nodes are in the map table. Just delete all of those. */
1.780 + for (i = 0; i < g->mNCategoryMap; i++) {
1.781 + free(g->mCategoryMap[i]->node);
1.782 + free(g->mCategoryMap[i]);
1.783 + }
1.784 + free(g->mCategoryMap);
1.785 +}
1.786 +
1.787 +int
1.788 +freeCategories(STGlobals * g)
1.789 +{
1.790 + uint32_t i;
1.791 +
1.792 + /*
1.793 + ** walk the tree and free runs held in nodes
1.794 + */
1.795 + freeNodeRuns(&g->mCategoryRoot);
1.796 +
1.797 + /*
1.798 + ** delete nodemap. This is the where nodes get deleted.
1.799 + */
1.800 + freeNodeMap(g);
1.801 +
1.802 + /*
1.803 + ** delete rule stuff
1.804 + */
1.805 + for (i = 0; i < g->mNRules; i++) {
1.806 + freeRule(g->mCategoryRules[i]);
1.807 + }
1.808 + free(g->mCategoryRules);
1.809 +
1.810 + return 0;
1.811 +}
1.812 +
1.813 +
1.814 +/*
1.815 +** categorizeRun
1.816 +**
1.817 +** categorize all the allocations of the run using the rules into
1.818 +** a tree rooted at globls.mCategoryRoot
1.819 +*/
1.820 +int
1.821 +categorizeRun(STOptions * inOptions, STContext * inContext,
1.822 + const STRun * aRun, STGlobals * g)
1.823 +{
1.824 + uint32_t i;
1.825 +
1.826 +#if defined(DEBUG_dp)
1.827 + PRIntervalTime start = PR_IntervalNow();
1.828 +
1.829 + fprintf(stderr, "DEBUG: categorizing run...\n");
1.830 +#endif
1.831 +
1.832 + /*
1.833 + ** First, cleanup our tree
1.834 + */
1.835 + walkTree(&g->mCategoryRoot, freeNodeRunProcessor, NULL, inOptions,
1.836 + inContext, NULL, 0);
1.837 +
1.838 + if (g->mNCategoryMap > 0) {
1.839 + for (i = 0; i < aRun->mAllocationCount; i++) {
1.840 + categorizeAllocation(inOptions, inContext, aRun->mAllocations[i],
1.841 + g);
1.842 + }
1.843 + }
1.844 +
1.845 + /*
1.846 + ** the run is always going to be the one corresponding to the root node
1.847 + */
1.848 + g->mCategoryRoot.runs[inContext->mIndex] = (STRun *) aRun;
1.849 + g->mCategoryRoot.categoryName = ST_ROOT_CATEGORY_NAME;
1.850 +
1.851 +#if defined(DEBUG_dp)
1.852 + fprintf(stderr,
1.853 + "DEBUG: categorizing ends: %dms [%d rules, %d allocations]\n",
1.854 + PR_IntervalToMilliseconds(PR_IntervalNow() - start), g->mNRules,
1.855 + aRun->mAllocationCount);
1.856 + fprintf(stderr, "DEBUG: match : %dms [%d calls, %d rule-compares]\n",
1.857 + PR_IntervalToMilliseconds(_gMatchTime), _gMatchCount,
1.858 + _gMatchRules);
1.859 +#endif
1.860 +
1.861 + /*
1.862 + ** sort the tree based on our sort criterion
1.863 + */
1.864 + walkTree(&g->mCategoryRoot, sortNodeProcessor, NULL, inOptions, inContext,
1.865 + NULL, 0);
1.866 +
1.867 +#if defined(DEBUG_dp)
1.868 + walkTree(&g->mCategoryRoot, printNodeProcessor, NULL, inOptions,
1.869 + inContext, &g->mCategoryRoot, 0);
1.870 +#endif
1.871 +
1.872 + return 0;
1.873 +}
1.874 +
1.875 +
1.876 +/*
1.877 +** displayCategoryReport
1.878 +**
1.879 +** Generate the category report - a list of all categories and details about each
1.880 +** depth parameter controls how deep we traverse the category tree.
1.881 +*/
1.882 +PRBool
1.883 +displayCategoryNodeProcessor(STRequest * inRequest, STOptions * inOptions,
1.884 + STContext * inContext, void *clientData,
1.885 + STCategoryNode * node)
1.886 +{
1.887 + STCategoryNode *root = (STCategoryNode *) clientData;
1.888 + uint32_t byteSize = 0, heapCost = 0, count = 0;
1.889 + double percent = 0;
1.890 + STOptions customOps;
1.891 +
1.892 + if (node->runs[inContext->mIndex]) {
1.893 + /*
1.894 + ** Byte size
1.895 + */
1.896 + byteSize =
1.897 + node->runs[inContext->mIndex]->mStats[inContext->mIndex].mSize;
1.898 +
1.899 + /*
1.900 + ** Composite count
1.901 + */
1.902 + count =
1.903 + node->runs[inContext->mIndex]->mStats[inContext->mIndex].
1.904 + mCompositeCount;
1.905 +
1.906 + /*
1.907 + ** Heap operation cost
1.908 + **/
1.909 + heapCost =
1.910 + node->runs[inContext->mIndex]->mStats[inContext->mIndex].
1.911 + mHeapRuntimeCost;
1.912 +
1.913 + /*
1.914 + ** % of total size
1.915 + */
1.916 + if (root->runs[inContext->mIndex]) {
1.917 + percent =
1.918 + ((double) byteSize) /
1.919 + root->runs[inContext->mIndex]->mStats[inContext->mIndex].
1.920 + mSize * 100;
1.921 + }
1.922 + }
1.923 +
1.924 + PR_fprintf(inRequest->mFD, " <tr>\n" " <td>");
1.925 +
1.926 + /* a link to topcallsites report with focus on category */
1.927 + memcpy(&customOps, inOptions, sizeof(customOps));
1.928 + PR_snprintf(customOps.mCategoryName, sizeof(customOps.mCategoryName),
1.929 + "%s", node->categoryName);
1.930 +
1.931 + htmlAnchor(inRequest, "top_callsites.html", node->categoryName, NULL,
1.932 + "category-callsites", &customOps);
1.933 + PR_fprintf(inRequest->mFD,
1.934 + "</td>\n" " <td align=right>%u</td>\n"
1.935 + " <td align=right>%4.1f%%</td>\n"
1.936 + " <td align=right>%u</td>\n" " <td align=right>"
1.937 + ST_MICROVAL_FORMAT "</td>\n" " </tr>\n", byteSize, percent,
1.938 + count, ST_MICROVAL_PRINTABLE(heapCost));
1.939 +
1.940 + return PR_TRUE;
1.941 +}
1.942 +
1.943 +
1.944 +int
1.945 +displayCategoryReport(STRequest * inRequest, STCategoryNode * root, int depth)
1.946 +{
1.947 + PR_fprintf(inRequest->mFD,
1.948 + "<table class=\"category-list data\">\n"
1.949 + " <tr class=\"row-header\">\n"
1.950 + " <th>Category</th>\n"
1.951 + " <th>Composite Byte Size</th>\n"
1.952 + " <th>%% of Total Size</th>\n"
1.953 + " <th>Heap Object Count</th>\n"
1.954 + " <th>Composite Heap Operations Seconds</th>\n" " </tr>\n");
1.955 +
1.956 + walkTree(root, displayCategoryNodeProcessor, inRequest,
1.957 + &inRequest->mOptions, inRequest->mContext, root, depth);
1.958 +
1.959 + PR_fprintf(inRequest->mFD, "</table>\n");
1.960 +
1.961 + return 0;
1.962 +}
