diff options
Diffstat (limited to 'stackstash.c')
| -rw-r--r-- | stackstash.c | 427 |
1 files changed, 298 insertions, 129 deletions
diff --git a/stackstash.c b/stackstash.c index 9f66f15..44912e4 100644 --- a/stackstash.c +++ b/stackstash.c @@ -19,200 +19,369 @@ #include "stackstash.h" -typedef struct StackNode StackNode; - -struct StackNode +struct StackStash { - StackNode * parent; - gpointer address; - StackNode * siblings; - StackNode * children; - StackNode * next; /* next leaf with the same pid */ - int size; + int ref_count; + StackNode * root; + GHashTable * nodes_by_data; + GDestroyNotify destroy; + + StackNode * cached_nodes; + GPtrArray * blocks; }; -struct StackStash +static void +decorate_node (StackNode *node, + StackStash *stash) { - StackNode *root; - GHashTable *leaves_by_process; -}; + StackNode *n; + + if (!node) + return; + + decorate_node (node->siblings, stash); + decorate_node (node->children, stash); + + node->next = g_hash_table_lookup (stash->nodes_by_data, &node->data); + g_hash_table_insert (stash->nodes_by_data, &node->data, node); + + /* FIXME: This could be done more efficiently + * by keeping track of the ancestors we have seen. + */ + node->toplevel = TRUE; + for (n = node->parent; n != NULL; n = n->parent) + { + if (n->data == node->data) + { + node->toplevel = FALSE; + break; + } + } +} + +static unsigned int +address_hash (gconstpointer key) +{ + const uint64_t *addr = key; + + return *addr; +} + +static gboolean +address_equal (gconstpointer key1, gconstpointer key2) +{ + const uint64_t *addr1 = key1; + const uint64_t *addr2 = key2; + + return *addr1 == *addr2; +} + +static void +stack_stash_decorate (StackStash *stash) +{ + if (stash->nodes_by_data) + return; + + stash->nodes_by_data = g_hash_table_new (address_hash, address_equal); + + decorate_node (stash->root, stash); +} + +static void +free_key (gpointer key, + gpointer value, + gpointer data) +{ + GDestroyNotify destroy = data; + uint64_t u64 = *(uint64_t *)key; + + destroy (U64_TO_POINTER (u64)); +} -static StackNode * -stack_node_new (void) +static void +stack_stash_undecorate (StackStash *stash) +{ + if (stash->nodes_by_data) + { + if (stash->destroy) + { + g_hash_table_foreach ( + stash->nodes_by_data, free_key, stash->destroy); + } + + g_hash_table_destroy (stash->nodes_by_data); + stash->nodes_by_data = NULL; + } +} + +static GHashTable * +get_nodes_by_data (StackStash *stash) { - StackNode *node = g_new (StackNode, 1); + if (!stash->nodes_by_data) + stack_stash_decorate (stash); + + return stash->nodes_by_data; +} + +StackNode * +stack_node_new (StackStash *stash) +{ + StackNode *node; + + if (!stash->cached_nodes) + { +#define BLOCK_SIZE 32768 +#define N_NODES (BLOCK_SIZE / sizeof (StackNode)) + + StackNode *block = g_malloc (BLOCK_SIZE); + int i; + + for (i = 0; i < N_NODES; ++i) + { + block[i].next = stash->cached_nodes; + stash->cached_nodes = &(block[i]); + } + + g_ptr_array_add (stash->blocks, block); + } + + node = stash->cached_nodes; + stash->cached_nodes = node->next; + node->siblings = NULL; node->children = NULL; - node->address = NULL; + node->data = 0; node->parent = NULL; - node->next = NULL; node->size = 0; + node->next = NULL; + node->total = 0; + return node; } -static void -stack_node_destroy (gpointer p) +/* "destroy", if non-NULL, is called once on every address */ +static StackStash * +create_stack_stash (GDestroyNotify destroy) { - StackNode *node = p; - if (node) - { - stack_node_destroy (node->siblings); - stack_node_destroy (node->children); - g_free (node); - } + StackStash *stash = g_new (StackStash, 1); + + stash->root = NULL; + stash->nodes_by_data = NULL; + stash->ref_count = 1; + stash->destroy = destroy; + + stash->cached_nodes = NULL; + stash->blocks = g_ptr_array_new (); + + return stash; } /* Stach */ StackStash * -stack_stash_new (void) +stack_stash_new (GDestroyNotify destroy) { - StackStash *stash = g_new (StackStash, 1); + return create_stack_stash (destroy); +} - stash->leaves_by_process = - g_hash_table_new (g_direct_hash, g_direct_equal); - stash->root = NULL; - return stash; + +static void +stack_stash_free (StackStash *stash) +{ + int i; + + stack_stash_undecorate (stash); + + for (i = 0; i < stash->blocks->len; ++i) + g_free (stash->blocks->pdata[i]); + + g_ptr_array_free (stash->blocks, TRUE); + + g_free (stash); } -static StackNode * -stack_node_add_trace (StackNode *node, - GList *bottom, - gint size, - StackNode **leaf) +StackNode * +stack_stash_add_trace (StackStash *stash, + uint64_t *addrs, + int n_addrs, + int size) { - StackNode *match; - StackNode *n; + StackNode **location = &(stash->root); + StackNode *parent = NULL; + int i; - if (!bottom) - { - *leaf = NULL; - return node; - } + if (!n_addrs) + return NULL; - if (!bottom->next) + if (stash->nodes_by_data) + stack_stash_undecorate (stash); + + for (i = n_addrs - 1; i >= 0; --i) { - /* A leaf must always be separate, so pids can - * point to them + StackNode *match = NULL; + StackNode *prev; + + /* FIXME: On x86-64 we don't get proper stacktraces which means + * each node can have tons of children. That makes this loop + * here show up on profiles. + * + * Not sure what can be done about it aside from actually fixing + * x86-64 to get stacktraces. */ - match = NULL; - } - else - { - for (match = node; match != NULL; match = match->siblings) + prev = NULL; + for (match = *location; match; prev = match, match = match->siblings) { - if (match->address == bottom->data) + if (match->data == addrs[i]) + { + if (prev) + { + /* move to front */ + prev->siblings = match->siblings; + match->siblings = *location; + *location = match; + } + break; + } } - } - if (!match) - { - match = stack_node_new (); - match->address = bottom->data; - match->siblings = node; - node = match; + if (!match) + { + match = stack_node_new (stash); + match->data = addrs[i]; + match->siblings = *location; + match->parent = parent; + *location = match; + } + + match->total += size; + + location = &(match->children); + parent = match; } - match->children = - stack_node_add_trace (match->children, bottom->next, size, leaf); + parent->size += size; - for (n = match->children; n; n = n->siblings) - n->parent = match; + return parent; +} + +static void +do_callback (StackNode *node, + StackLink *trace, + StackFunction func, + gpointer data) +{ + StackLink link; + + if (trace) + trace->prev = &link; + + link.next = trace; + link.prev = NULL; - if (!bottom->next) + while (node) { - match->size += size; - *leaf = match; + link.data = node->data; + + if (node->size) + func (&link, node->size, data); + + do_callback (node->children, &link, func, data); + + node = node->siblings; } - return node; + if (trace) + trace->prev = NULL; } void -stack_stash_add_trace (StackStash *stash, - Process *process, - gulong *addrs, - int n_addrs, - int size) +stack_stash_foreach (StackStash *stash, + StackFunction stack_func, + gpointer data) { - GList *trace; - StackNode *leaf; - int i; + do_callback (stash->root, NULL, stack_func, data); +} - if (!n_addrs) - return; - - trace = NULL; - for (i = 0; i < n_addrs; ++i) - trace = g_list_prepend (trace, GINT_TO_POINTER (addrs[i])); +void +stack_node_foreach_trace (StackNode *node, + StackFunction func, + gpointer data) +{ + StackLink link; - stash->root = stack_node_add_trace (stash->root, trace, size, &leaf); + link.next = NULL; + link.data = node->data; + link.prev = NULL; - leaf->next = g_hash_table_lookup ( - stash->leaves_by_process, process); - g_hash_table_insert ( - stash->leaves_by_process, process, leaf); + if (node->size) + func (&link, node->size, data); + + do_callback (node->children, &link, func, data); +} - g_list_free (trace); +void +stack_stash_unref (StackStash *stash) +{ + stash->ref_count--; + if (stash->ref_count == 0) + stack_stash_free (stash); } -typedef struct CallbackInfo +StackStash * +stack_stash_ref (StackStash *stash) { - StackFunction func; - gpointer data; -} CallbackInfo; + stash->ref_count++; + return stash; +} -static void -do_callback (gpointer key, gpointer value, gpointer data) +StackNode * +stack_stash_find_node (StackStash *stash, + gpointer data) { - CallbackInfo *info = data; - Process *process = key; - StackNode *n; - StackNode *leaf = value; - while (leaf) - { - GSList *trace; + uint64_t u64 = POINTER_TO_U64 (data); + + g_return_val_if_fail (stash != NULL, NULL); + + return g_hash_table_lookup (get_nodes_by_data (stash), &u64); +} - trace = NULL; - for (n = leaf; n; n = n->parent) - trace = g_slist_prepend (trace, n->address); +typedef struct +{ + StackNodeFunc func; + gpointer data; +} Info; - info->func (process, trace, leaf->size, info->data); +static void +do_foreach (gpointer key, gpointer value, gpointer data) +{ + Info *info = data; - g_slist_free (trace); - - leaf = leaf->next; - } + info->func (value, info->data); } void -stack_stash_foreach (StackStash *stash, - StackFunction stack_func, - gpointer data) +stack_stash_foreach_by_address (StackStash *stash, + StackNodeFunc func, + gpointer data) { - CallbackInfo info; - info.func = stack_func; + Info info; + info.func = func; info.data = data; - g_hash_table_foreach (stash->leaves_by_process, do_callback, &info); + g_hash_table_foreach (get_nodes_by_data (stash), do_foreach, &info); } -static void -stack_node_free (StackNode *node) +StackNode * +stack_stash_get_root (StackStash *stash) { - if (!node) - return; - - stack_node_free (node->siblings); - stack_node_free (node->children); - - g_free (node); + return stash->root; } void -stack_stash_free (StackStash *stash) +stack_stash_set_root (StackStash *stash, + StackNode *root) { - stack_node_free (stash->root); - g_hash_table_destroy (stash->leaves_by_process); - g_free (stash); + g_return_if_fail (stash->root == NULL); + + stash->root = root; } |