src/profile.c

   1 /* MemProf -- memory profiler and leak detector
   2  * Copyright 2002, Soeren Sandmann
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17  */
  18
  19 /*=====*/
  20
  21 #include "profile.h"
  22 #include <errno.h>
  23 #include <glib.h>
  24 #include <glib/gi18n.h>
  25
  26 static GList *
  27 block_create_stack_list (Block *block, MPProcess *process, GHashTable *skip_hash)
  28 {
  29     StackNode *element;
  30     GList *stack = NULL;
  31
  32     for (element = block->stack; element != NULL; element = element->parent)
  33     {
  34         const char *symbol = process_locate_symbol (process, (guint)element->address);
  35
  36         if (symbol && g_hash_table_lookup (skip_hash, symbol))
  37             continue;
  38
  39         stack = g_list_prepend (stack, element);
  40     }
  41
  42     return stack;
  43 }
  44
  45 static void
  46 profile_add_stack_trace (Profile *profile, GList *stack, guint size)
  47 {
  48     GList *list;
  49     GPtrArray *roots = profile->roots;
  50     ProfileNode *parent = NULL;
  51     GHashTable *seen_symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
  52                                                       (GDestroyNotify)symbol_free, NULL);
  53
  54     for (list = stack; list != NULL; list = list->next)
  55     {
  56         StackNode *element = list->data;
  57         ProfileNode *match = NULL;
  58         const char *symbol =
  59             process_locate_symbol (profile->process, GPOINTER_TO_SIZE(element->address));
  60         int i;
  61
  62         for (i = 0; i < roots->len; ++i)
  63         {
  64             ProfileNode *node = roots->pdata[i];
  65
  66             if (symbol_equal (node->symbol, symbol))
  67                 match = node;
  68         }
  69
  70         if (!match)
  71         {
  72             ProfileNode *next_node;
  73
  74             match = g_new (ProfileNode, 1);
  75
  76             match->symbol = symbol_copy (symbol);
  77             match->total = 0;
  78             match->self = 0;
  79
  80             if (g_hash_table_lookup (seen_symbols, symbol))
  81                 match->toplevel = FALSE;
  82             else
  83                 match->toplevel = TRUE;
  84
  85             next_node = g_hash_table_lookup (profile->nodes_by_symbol, symbol);
  86             if (next_node)
  87                 match->next = next_node;
  88             else
  89                 match->next = NULL;
  90             g_hash_table_insert (profile->nodes_by_symbol, symbol_copy (symbol), match);
  91
  92             match->children = g_ptr_array_new ();
  93             match->parent = parent;
  94
  95             g_ptr_array_add (roots, match);
  96         }
  97
  98         g_hash_table_insert (seen_symbols, symbol_copy (symbol), GINT_TO_POINTER (1));
  99
 100         match->total += size;
 101         if (!list->next)
 102             match->self += size;
 103
 104         parent = match;
 105         roots = match->children;
 106     }
 107
 108     g_hash_table_destroy (seen_symbols);
 109 }
 110
 111 static void
 112 profile_build_tree (Profile *profile, GList *blocks, GSList *skip_funcs)
 113 {
 114     GHashTable *skip_hash = g_hash_table_new (g_str_hash, g_str_equal);
 115     GList *list;
 116     GSList *slist;
 117
 118     for (slist = skip_funcs; slist != NULL; slist = slist->next)
 119         g_hash_table_insert (skip_hash, slist->data, "");
 120
 121     for (list = blocks; list != NULL; list = list->next)
 122     {
 123         Block *block = list->data;
 124         GList *stack = block_create_stack_list (block, profile->process, skip_hash);
 125
 126         profile_add_stack_trace (profile, stack, block->size);
 127
 128         g_list_free (stack);
 129     }
 130
 131     g_hash_table_destroy (skip_hash);
 132 }
 133
 134 static void
 135 add_function (gpointer key, gpointer value, gpointer data)
 136 {
 137     ProfileFunc *func;
 138     ProfileNode *node;
 139     Profile *profile = data;
 140
 141     node = value;
 142
 143     func = g_new (ProfileFunc, 1);
 144     func->node = node;
 145     func->total = 0;
 146     func->self = 0;
 147
 148     while (node)
 149     {
 150         func->self += node->self;
 151         if (node->toplevel)
 152             func->total += node->total;
 153
 154         node = node->next;
 155     }
 156
 157     g_ptr_array_add (profile->functions, func);
 158 }
 159
 160 static void
 161 add_block_to_list (Block *block, gpointer data)
 162 {
 163     GList **blocks = data;
 164
 165     *blocks = g_list_prepend (*blocks, block);
 166 }
 167
 168 Profile *
 169 profile_create (MPProcess *process, GSList *skip_funcs)
 170 {
 171     Profile *profile;
 172     GList *blocks = NULL;
 173     GList *list;
 174
 175     process_block_foreach (process, add_block_to_list, &blocks);
 176
 177     profile = g_new (Profile, 1);
 178     profile->roots = g_ptr_array_new ();
 179     profile->functions = g_ptr_array_new ();
 180     profile->n_bytes = 0;
 181     profile->process = process;
 182     profile->nodes_by_symbol = g_hash_table_new_full (symbol_hash, symbol_equal,
 183                                                       (GDestroyNotify)symbol_free, NULL);
 184
 185     profile_build_tree (profile, blocks, skip_funcs);
 186
 187     for (list = blocks; list != NULL; list = list->next)
 188     {
 189         Block *block = list->data;
 190
 191         profile->n_bytes += block->size;
 192     }
 193
 194     g_hash_table_foreach (profile->nodes_by_symbol, add_function, profile);
 195
 196     g_list_free (blocks);
 197     return profile;
 198 }
 199
 200 static void
 201 profile_node_free (ProfileNode *node)
 202 {
 203     int i;
 204
 205     for (i = 0; i < node->children->len; ++i)
 206         profile_node_free (node->children->pdata[i]);
 207     if (node->symbol)
 208         symbol_free (node->symbol);
 209     g_ptr_array_free (node->children, TRUE);
 210     g_free (node);
 211 }
 212
 213 void
 214 profile_free (Profile *profile)
 215 {
 216     int i;
 217
 218     for (i = 0; i < profile->roots->len; ++i)
 219         profile_node_free (profile->roots->pdata[i]);
 220     g_ptr_array_free (profile->roots, TRUE);
 221
 222     for (i = 0; i < profile->functions->len; ++i)
 223         g_free (profile->functions->pdata[i]);
 224     g_ptr_array_free (profile->functions, TRUE);
 225
 226     g_hash_table_destroy (profile->nodes_by_symbol);
 227     g_free (profile);
 228 }
 229
 230 static void
 231 node_list_leaves (ProfileNode *node, GList **leaves)
 232 {
 233     int i;
 234
 235     if (node->self > 0)
 236         *leaves = g_list_prepend (*leaves, node);
 237
 238     for (i = 0; i < node->children->len; ++i)
 239         node_list_leaves (node->children->pdata[i], leaves);
 240 }
 241
 242 static void
 243 add_trace_to_tree (GPtrArray *roots, GList *trace, guint size)
 244 {
 245     GList *list;
 246     GList *nodes_to_unmark = NULL;
 247     GList *nodes_to_unmark_recursive = NULL;
 248     ProfileDescendantTreeNode *parent = NULL;
 249
 250     GHashTable *seen_symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
 251                                                       (GDestroyNotify)symbol_free, NULL);
 252
 253     for (list = trace; list != NULL; list = list->next)
 254     {
 255         int i;
 256         ProfileNode *node = list->data;
 257         ProfileDescendantTreeNode *match = NULL;
 258
 259         for (i = 0; i < roots->len; ++i)
 260         {
 261             ProfileDescendantTreeNode *tree_node = roots->pdata[i];
 262
 263             if (symbol_equal (tree_node->symbol, node->symbol))
 264                 match = tree_node;
 265         }
 266
 267         if (!match)
 268         {
 269             ProfileDescendantTreeNode *seen_tree_node;
 270
 271             seen_tree_node = g_hash_table_lookup (seen_symbols, node->symbol);
 272
 273             if (seen_tree_node)
 274             {
 275                 ProfileDescendantTreeNode *node;
 276
 277                 g_assert (parent);
 278
 279                 for (node = parent; node != seen_tree_node->parent; node = node->parent)
 280                 {
 281                     node->non_recursion -= size;
 282                     --node->marked_non_recursive;
 283                 }
 284
 285                 match = seen_tree_node;
 286
 287                 g_hash_table_destroy (seen_symbols);
 288                 seen_symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
 289                                                       (GDestroyNotify)symbol_free, NULL);
 290
 291                 for (node = match; node != NULL; node = node->parent)
 292                     g_hash_table_insert (seen_symbols, symbol_copy (node->symbol), node);
 293
 294             }
 295         }
 296
 297         if (!match)
 298         {
 299             match = g_new (ProfileDescendantTreeNode, 1);
 300
 301             match->symbol = symbol_copy (node->symbol);
 302             match->non_recursion = 0;
 303             match->total = 0;
 304             match->self = 0;
 305             match->children = g_ptr_array_new ();
 306             match->marked_non_recursive = 0;
 307             match->marked_total = FALSE;
 308             match->parent = parent;
 309
 310             g_ptr_array_add (roots, match);
 311         }
 312
 313         if (!match->marked_non_recursive)
 314         {
 315             nodes_to_unmark = g_list_prepend (nodes_to_unmark, match);
 316             match->non_recursion += size;
 317             ++match->marked_non_recursive;
 318         }
 319
 320         if (!match->marked_total)
 321         {
 322             nodes_to_unmark_recursive = g_list_prepend (
 323                 nodes_to_unmark_recursive, match);
 324
 325             match->total += size;
 326             match->marked_total = TRUE;
 327         }
 328
 329         if (!list->next)
 330             match->self += size;
 331
 332         g_hash_table_insert (seen_symbols, symbol_copy (node->symbol), match);
 333
 334         roots = match->children;
 335         parent = match;
 336     }
 337
 338     g_hash_table_destroy (seen_symbols);
 339
 340     for (list = nodes_to_unmark; list != NULL; list = list->next)
 341     {
 342         ProfileDescendantTreeNode *tree_node = list->data;
 343
 344         tree_node->marked_non_recursive = 0;
 345     }
 346
 347     for (list = nodes_to_unmark_recursive; list != NULL; list = list->next)
 348     {
 349         ProfileDescendantTreeNode *tree_node = list->data;
 350
 351         tree_node->marked_total = FALSE;
 352     }
 353
 354     g_list_free (nodes_to_unmark);
 355 }
 356
 357 static void
 358 add_leaf_to_tree (ProfileDescendantTree *tree, ProfileNode *leaf, ProfileNode *top)
 359 {
 360     ProfileNode *node;
 361     GList *trace = NULL;
 362
 363
 364     /*
 365      * XXX: FIXME: node->parent should always lead to a valid frame
 366      * but it does not and more work needs to be done to figure out
 367      * why this is the case. This can be easily reproduced with the
 368      * GtkLauncher of WebKit/GTK+.
 369      */
 370     for (node = leaf; node && node != top->parent; node = node->parent)
 371         trace = g_list_prepend (trace, node);
 372
 373     add_trace_to_tree (tree->roots, trace, leaf->self);
 374
 375     g_list_free (trace);
 376 }
 377
 378 ProfileDescendantTree *
 379 profile_func_create_descendant_tree (ProfileFunc           *func)
 380 {
 381     ProfileDescendantTree *tree = g_new (ProfileDescendantTree, 1);
 382     ProfileNode *node;
 383
 384     tree->roots = g_ptr_array_new ();
 385
 386     for (node = func->node; node != NULL; node = node->next)
 387         if (node->toplevel)
 388         {
 389             GList *leaves = NULL;
 390             GList *list;
 391
 392             node_list_leaves (node, &leaves);
 393
 394             for (list = leaves; list != NULL; list = list->next)
 395                 add_leaf_to_tree (tree, list->data, node);
 396
 397             g_list_free (leaves);
 398         }
 399
 400     return tree;
 401 }
 402
 403 static void
 404 profile_descendant_tree_node_free (ProfileDescendantTreeNode *node)
 405 {
 406     int i;
 407
 408     for (i = 0; i < node->children->len; ++i)
 409     {
 410         ProfileDescendantTreeNode *child = node->children->pdata[i];
 411
 412         profile_descendant_tree_node_free (child);
 413     }
 414
 415     g_ptr_array_free (node->children, TRUE);
 416     g_free (node);
 417 }
 418
 419 void
 420 profile_descendant_tree_free (ProfileDescendantTree *descendant_tree)
 421 {
 422     int i;
 423
 424     for (i = 0; i < descendant_tree->roots->len; ++i)
 425     {
 426         ProfileDescendantTreeNode *node = descendant_tree->roots->pdata[i];
 427
 428         profile_descendant_tree_node_free (node);
 429     }
 430     g_ptr_array_free (descendant_tree->roots, TRUE);
 431     g_free (descendant_tree);
 432 }
 433
 434 GPtrArray *
 435 profile_func_create_caller_list     (ProfileFunc             *func)
 436 {
 437     GPtrArray *result = g_ptr_array_new ();
 438     GHashTable *callers_by_symbol = g_hash_table_new_full (
 439         symbol_hash, symbol_equal,
 440         (GDestroyNotify)symbol_free, NULL);
 441     GHashTable *marked_callers = g_hash_table_new (g_direct_hash, g_direct_equal);
 442     ProfileFunc *spontaneous = NULL;
 443     ProfileNode *node;
 444
 445     for (node = func->node; node != NULL; node = node->next)
 446     {
 447         if (node->parent)
 448         {
 449             if (!g_hash_table_lookup (callers_by_symbol, node->parent->symbol))
 450             {
 451                 ProfileFunc *caller = g_new (ProfileFunc, 1);
 452
 453                 caller->total = 0;
 454                 caller->self = 0;
 455                 caller->node = node->parent;
 456
 457                 g_hash_table_insert (
 458                     callers_by_symbol, symbol_copy (node->parent->symbol), caller);
 459                 g_ptr_array_add (result, caller);
 460             }
 461         }
 462         else
 463         {
 464             if (!spontaneous)
 465             {
 466                 spontaneous = g_new (ProfileFunc, 1);
 467                 spontaneous->total = 0;
 468                 spontaneous->self = 0;
 469                 spontaneous->node = NULL;
 470                 g_ptr_array_add (result, spontaneous);
 471             }
 472         }
 473     }
 474
 475     for (node = func->node; node != NULL; node = node->next)
 476     {
 477         ProfileNode *top_caller_node;
 478         ProfileNode *top_callee_node;
 479         ProfileFunc *caller;
 480         ProfileNode *n;
 481
 482         if (!node->parent)
 483         {
 484             g_assert (spontaneous);
 485             caller = spontaneous;
 486         }
 487         else
 488             caller = g_hash_table_lookup (callers_by_symbol, node->parent->symbol);
 489
 490         /* find topmost node/parent pair identical to this node/parent */
 491         top_caller_node = node->parent;
 492         top_callee_node = node;
 493         for (n = node->parent; n && n->parent != NULL; n = n->parent)
 494         {
 495             if (symbol_equal (n->symbol, node->symbol) &&
 496                 symbol_equal (n->parent->symbol, top_caller_node->symbol))
 497             {
 498                 top_caller_node = n->parent;
 499                 top_callee_node = n;
 500             }
 501         }
 502         if (!g_hash_table_lookup (marked_callers, top_caller_node))
 503         {
 504             caller->total += top_callee_node->total;
 505
 506             g_hash_table_insert (marked_callers, top_caller_node, GINT_TO_POINTER (1));
 507         }
 508
 509         if (node->self > 0)
 510             caller->self += node->self;
 511     }
 512
 513     g_hash_table_destroy (marked_callers);
 514     g_hash_table_destroy (callers_by_symbol);
 515
 516     return result;
 517 }
 518
 519 void
 520 profile_caller_list_free             (GPtrArray              *caller_list)
 521 {
 522     int i;
 523
 524     for (i = 0; i < caller_list->len; ++i)
 525         g_free (caller_list->pdata[i]);
 526
 527     g_ptr_array_free (caller_list, TRUE);
 528 }
 529
 530 static gint
 531 compare_profile_funcs (gconstpointer a, gconstpointer b)
 532 {
 533         const ProfileFunc *pa = * (const ProfileFunc**) a;
 534         const ProfileFunc *pb = * (const ProfileFunc**) b;
 535         if (pa->total > pb->total)
 536                 return -1;
 537         if (pa->total < pb->total)
 538                 return 1;
 539         return 0;
 540 }
 541
 542 static GPtrArray *
 543 create_sorted_profile_funcs (GPtrArray *funcs)
 544 {
 545         int i;
 546         GPtrArray *functions;
 547
 548         functions = g_ptr_array_sized_new (funcs->len);
 549
 550         for (i = 0; i < funcs->len; ++i)
 551                 g_ptr_array_add (functions, funcs->pdata [i]);
 552
 553         g_ptr_array_sort (functions, compare_profile_funcs);
 554
 555         return functions;
 556 }
 557
 558 static gint
 559 compare_descendant_tree_nodes (gconstpointer a, gconstpointer b)
 560 {
 561         const ProfileDescendantTreeNode *pa = * (const ProfileDescendantTreeNode **) a;
 562         const ProfileDescendantTreeNode *pb = * (const ProfileDescendantTreeNode **) b;
 563         if (pa->total > pb->total)
 564                 return -1;
 565         if (pa->total < pb->total)
 566                 return 1;
 567         return 0;
 568 }
 569
 570 static GPtrArray *
 571 create_sorted_descendant_tree_nodes (GPtrArray *funcs)
 572 {
 573         int i;
 574         GPtrArray *functions;
 575
 576         functions = g_ptr_array_sized_new (funcs->len);
 577
 578         for (i = 0; i < funcs->len; ++i)
 579                 g_ptr_array_add (functions, funcs->pdata [i]);
 580
 581         g_ptr_array_sort (functions, compare_descendant_tree_nodes);
 582
 583         return functions;
 584 }
 585
 586 static void
 587 output_callers (FILE* out, ProfileFunc *func)
 588 {
 589         int i;
 590         GPtrArray *profile_callers, *callers;
 591
 592         profile_callers = profile_func_create_caller_list (func);
 593         callers         = create_sorted_profile_funcs (profile_callers);
 594
 595         fprintf (out, "  Callers (with count) that contribute at least for 1%%:\n");
 596
 597         for (i = 0; i < callers->len; ++i) {
 598                 const gchar* name;
 599                 unsigned int percent;
 600                 ProfileFunc *caller = callers->pdata [i];
 601
 602                 if (caller->node) {
 603                         if (caller->node->symbol)
 604                                 name = caller->node->symbol;
 605                         else
 606                                 name = "???";
 607                 }
 608                 else
 609                         name = "<spontaneous>";
 610                 percent = (caller->total * 100)/ func->total;
 611                 if (percent < 1)
 612                         continue;
 613                 fprintf (out, "    %10d %10d %3d %% %s\n",
 614                                 caller->self, caller->total, percent, name);
 615         }
 616
 617         profile_caller_list_free (profile_callers);
 618         g_ptr_array_free (callers, 1);
 619 }
 620
 621 static void
 622 output_descendants (FILE* out, ProfileFunc *func)
 623 {
 624         int i;
 625         ProfileDescendantTree *descendant_tree;
 626         ProfileDescendantTreeNode *node;
 627         GPtrArray *children;
 628
 629         descendant_tree = profile_func_create_descendant_tree (func);
 630         node            = descendant_tree->roots->pdata [0];
 631         children        = create_sorted_descendant_tree_nodes (node->children);
 632
 633         fprintf (out, "  Descendants (with count) that contribute at least for 1%%:\n");
 634
 635         for (i = 0; i < children->len; ++i) {
 636                 const gchar* name;
 637                 unsigned int percent;
 638                 ProfileDescendantTreeNode *child = children->pdata [i];
 639
 640                 if (child->symbol) {
 641                         name = child->symbol;
 642                 }
 643                 else
 644                         name = "???";
 645                 percent = (child->total * 100)/ node->total;
 646                 if (percent < 1)
 647                         continue;
 648                 fprintf (out, "    %10d %10d %3d %% %s\n",
 649                                 child->self, child->total, percent, name);
 650         }
 651
 652         profile_descendant_tree_free (descendant_tree);
 653         g_ptr_array_free (children, 1);
 654 }
 655
 656 static void
 657 output_profile_summary (FILE *out, guint n_bytes, GPtrArray *functions)
 658 {
 659         int i;
 660
 661         fprintf (out, "      self      total total %% symbol\n");
 662         fprintf (out, " --------- ---------- ------- ------------\n");
 663
 664         for (i = 0; i < functions->len; ++i) {
 665                 const gchar *name;
 666                 ProfileFunc *func = functions->pdata [i];
 667                 if (func->node->symbol)
 668                         name = func->node->symbol;
 669                 else
 670                         name = "???";
 671                 fprintf (out, "%10d %10d %5.2f %% %s\n",
 672                                 func->self, func->total,
 673                                 func->total * 100.0 / (double) n_bytes,
 674                                 name);
 675         }
 676 }
 677
 678 static void
 679 output_profile_details (FILE *out, guint n_bytes, GPtrArray *functions)
 680 {
 681         int i;
 682
 683         for (i = 0; i < functions->len; ++i) {
 684                 const gchar *name;
 685                 ProfileFunc *func = functions->pdata [i];
 686                 if (func->node->symbol)
 687                         name = func->node->symbol;
 688                 else
 689                         name = "???";
 690                 fprintf (out, "########################\n");
 691                 fprintf (out, "%10d %10d %5.2f %% %s\n",
 692                                 func->self, func->total,
 693                                 func->total * 100.0 / (double) n_bytes,
 694                                 name);
 695                 output_callers (out, func);
 696                 output_descendants (out, func);
 697         }
 698 }
 699
 700 void
 701 profile_write (Profile *profile, const gchar *outfile)
 702 {
 703         FILE *out;
 704         GPtrArray *functions;
 705
 706         out = fopen (outfile, "w");
 707         if (!out) {
 708                 show_error (NULL, ERROR_MODAL, _("Cannot open output file: %s\n"),
 709                 g_strerror (errno));
 710                 return;
 711         }
 712
 713         functions = create_sorted_profile_funcs (profile->functions);
 714
 715         fprintf (out, "Total number of bytes profiled: %u\n", profile->n_bytes);
 716
 717         output_profile_summary (out, profile->n_bytes, functions);
 718         output_profile_details (out, profile->n_bytes, functions);
 719
 720         g_ptr_array_free (functions, 1);
 721         fclose (out);
 722 }
 723