src/stackstash.c

   1 /* Sysprof -- Sampling, systemwide CPU profiler
   2  * Copyright 2004, Red Hat, Inc.
   3  * Copyright 2004, 2005, Soeren Sandmann
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18  */
  19
  20 #include "stackstash.h"
  21
  22 struct StackStash
  23 {
  24     int                 ref_count;
  25     StackNode *         root;
  26     GHashTable *        nodes_by_data;
  27     GDestroyNotify      destroy;
  28
  29     StackNode *         cached_nodes;
  30     GPtrArray *         blocks;
  31 };
  32
  33 StackNode *
  34 stack_node_new (StackStash *stash)
  35 {
  36     StackNode *node;
  37
  38     if (!stash->cached_nodes)
  39     {
  40 #define BLOCK_SIZE 32768
  41 #define N_NODES (BLOCK_SIZE / sizeof (StackNode))
  42
  43         StackNode *block = g_malloc (BLOCK_SIZE);
  44         int i;
  45
  46         for (i = 0; i < N_NODES; ++i)
  47         {
  48             block[i].next = stash->cached_nodes;
  49             stash->cached_nodes = &(block[i]);
  50         }
  51
  52         g_ptr_array_add (stash->blocks, block);
  53     }
  54
  55     node = stash->cached_nodes;
  56     stash->cached_nodes = node->next;
  57
  58     node->siblings = NULL;
  59     node->children = NULL;
  60     node->address = NULL;
  61     node->parent = NULL;
  62     node->size = 0;
  63     node->next = NULL;
  64     node->total = 0;
  65
  66     return node;
  67 }
  68
  69 /* "destroy", if non-NULL, is called once on every address */
  70 static StackStash *
  71 create_stack_stash (GDestroyNotify destroy)
  72 {
  73     StackStash *stash = g_new (StackStash, 1);
  74
  75     stash->root = NULL;
  76     stash->nodes_by_data = g_hash_table_new (g_direct_hash, g_direct_equal);
  77     stash->ref_count = 1;
  78     stash->destroy = destroy;
  79
  80     stash->cached_nodes = NULL;
  81     stash->blocks = g_ptr_array_new ();
  82
  83     return stash;
  84 }
  85
  86 /* Stach */
  87 StackStash *
  88 stack_stash_new (GDestroyNotify destroy)
  89 {
  90     return create_stack_stash (destroy);
  91 }
  92
  93
  94 static void
  95 free_key (gpointer key,
  96           gpointer value,
  97           gpointer data)
  98 {
  99     GDestroyNotify destroy = data;
 100
 101     destroy (key);
 102 }
 103
 104 static void
 105 stack_stash_free (StackStash *stash)
 106 {
 107     int i;
 108
 109     if (stash->destroy)
 110     {
 111         g_hash_table_foreach (stash->nodes_by_data, free_key,
 112                               stash->destroy);
 113     }
 114
 115     g_hash_table_destroy (stash->nodes_by_data);
 116
 117     for (i = 0; i < stash->blocks->len; ++i)
 118         g_free (stash->blocks->pdata[i]);
 119
 120     g_ptr_array_free (stash->blocks, TRUE);
 121
 122     g_free (stash);
 123 }
 124
 125 static void
 126 decorate_node (StackStash *stash,
 127                StackNode  *node)
 128 {
 129     StackNode *n;
 130     gboolean toplevel = TRUE;
 131
 132     /* FIXME: we will probably want to do this lazily,
 133      * and more efficiently (only walk the tree once).
 134      */
 135     for (n = node->parent; n != NULL; n = n->parent)
 136     {
 137         if (n->address == node->address)
 138         {
 139             toplevel = FALSE;
 140             break;
 141         }
 142     }
 143
 144     node->toplevel = toplevel;
 145
 146     node->next = g_hash_table_lookup (
 147         stash->nodes_by_data, node->address);
 148     g_hash_table_insert (
 149         stash->nodes_by_data, node->address, node);
 150 }
 151
 152 StackNode *
 153 stack_stash_add_trace (StackStash *stash,
 154                        gpointer     *addrs,
 155                        int         n_addrs,
 156                        int         size)
 157 {
 158     StackNode **location = &(stash->root);
 159     StackNode *parent = NULL;
 160     int i;
 161
 162     if (!n_addrs)
 163         return NULL;
 164
 165     for (i = n_addrs - 1; i >= 0; --i)
 166     {
 167         StackNode *match = NULL;
 168         StackNode *n;
 169
 170         for (n = *location; n != NULL; n = n->siblings)
 171         {
 172             if (n->address == (gpointer)addrs[i])
 173             {
 174                 match = n;
 175                 break;
 176             }
 177         }
 178
 179         if (!match)
 180         {
 181             match = stack_node_new (stash);
 182             match->address = (gpointer)addrs[i];
 183             match->siblings = *location;
 184             match->parent = parent;
 185             *location = match;
 186
 187             decorate_node (stash, match);
 188         }
 189
 190         match->total += size;
 191
 192         location = &(match->children);
 193         parent = match;
 194     }
 195
 196     parent->size += size;
 197
 198     return parent;
 199 }
 200
 201 static void
 202 do_callback (StackNode *node,
 203              GList *trace,
 204              StackFunction func,
 205              gpointer data)
 206 {
 207     GList link;
 208
 209     if (trace)
 210         trace->prev = &link;
 211
 212     link.next = trace;
 213     link.prev = NULL;
 214
 215     while (node)
 216     {
 217         link.data = node->address;
 218
 219         if (node->size)
 220             func (&link, node->size, data);
 221
 222         do_callback (node->children, &link, func, data);
 223
 224         node = node->siblings;
 225     }
 226
 227     if (trace)
 228         trace->prev = NULL;
 229 }
 230
 231 void
 232 stack_stash_foreach   (StackStash      *stash,
 233                        StackFunction    stack_func,
 234                        gpointer         data)
 235 {
 236     do_callback (stash->root, NULL, stack_func, data);
 237 }
 238
 239 void
 240 stack_node_foreach_trace (StackNode     *node,
 241                           StackFunction  func,
 242                           gpointer       data)
 243 {
 244     GList link;
 245
 246     link.next = NULL;
 247     link.data = node->address;
 248     link.prev = NULL;
 249
 250     if (node->size)
 251         func (&link, node->size, data);
 252
 253     do_callback (node->children, &link, func, data);
 254 }
 255
 256 void
 257 stack_stash_unref (StackStash *stash)
 258 {
 259     stash->ref_count--;
 260     if (stash->ref_count == 0)
 261         stack_stash_free (stash);
 262 }
 263
 264 StackStash *
 265 stack_stash_ref (StackStash *stash)
 266 {
 267     stash->ref_count++;
 268     return stash;
 269 }
 270
 271 StackNode *
 272 stack_stash_find_node (StackStash      *stash,
 273                        gpointer         data)
 274 {
 275     g_return_val_if_fail (stash != NULL, NULL);
 276
 277     return g_hash_table_lookup (stash->nodes_by_data, data);
 278 }
 279
 280 typedef struct
 281 {
 282     StackNodeFunc func;
 283     gpointer      data;
 284 } Info;
 285
 286 static void
 287 do_foreach (gpointer key, gpointer value, gpointer data)
 288 {
 289     Info *info = data;
 290
 291     info->func (value, info->data);
 292 }
 293
 294 void
 295 stack_stash_foreach_by_address (StackStash *stash,
 296                                 StackNodeFunc func,
 297                                 gpointer      data)
 298 {
 299     Info info;
 300     info.func = func;
 301     info.data = data;
 302
 303     g_hash_table_foreach (stash->nodes_by_data, do_foreach, &info);
 304 }
 305
 306 StackNode  *
 307 stack_stash_get_root   (StackStash *stash)
 308 {
 309     return stash->root;
 310 }
 311
 312 static void
 313 build_hash_table (StackNode *node,
 314                   StackStash *stash)
 315 {
 316     if (!node)
 317         return;
 318
 319     build_hash_table (node->siblings, stash);
 320     build_hash_table (node->children, stash);
 321
 322     node->next = g_hash_table_lookup (
 323         stash->nodes_by_data, node->address);
 324     g_hash_table_insert (
 325         stash->nodes_by_data, node->address, node);
 326 }
 327
 328 void
 329 stack_stash_set_root (StackStash     *stash,
 330                       StackNode      *root)
 331 {
 332     g_return_if_fail (stash->root == NULL);
 333     g_return_if_fail (g_hash_table_size (stash->nodes_by_data) == 0);
 334
 335     stash->root = root;
 336     build_hash_table (stash->root, stash);
 337 }