diff options
| -rw-r--r-- | tools/perf/util/callchain.c | 122 |
1 files changed, 90 insertions, 32 deletions
diff --git a/tools/perf/util/callchain.c b/tools/perf/util/callchain.c index 6568cb198ba6..440db12c6359 100644 --- a/tools/perf/util/callchain.c +++ b/tools/perf/util/callchain.c @@ -4,6 +4,9 @@ * Handle the callchains from the stream in an ad-hoc radix tree and then * sort them in an rbtree. * + * Using a radix for code path provides a fast retrieval and factorizes + * memory use. Also that lets us use the paths in a hierarchical graph view. + * */ #include <stdlib.h> @@ -14,7 +17,8 @@ #include "callchain.h" -static void rb_insert_callchain(struct rb_root *root, struct callchain_node *chain) +static void +rb_insert_callchain(struct rb_root *root, struct callchain_node *chain) { struct rb_node **p = &root->rb_node; struct rb_node *parent = NULL; @@ -49,7 +53,12 @@ void sort_chain_to_rbtree(struct rb_root *rb_root, struct callchain_node *node) rb_insert_callchain(rb_root, node); } -static struct callchain_node *create_child(struct callchain_node *parent) +/* + * Create a child for a parent. If inherit_children, then the new child + * will become the new parent of it's parent children + */ +static struct callchain_node * +create_child(struct callchain_node *parent, bool inherit_children) { struct callchain_node *new; @@ -61,14 +70,27 @@ static struct callchain_node *create_child(struct callchain_node *parent) new->parent = parent; INIT_LIST_HEAD(&new->children); INIT_LIST_HEAD(&new->val); + + if (inherit_children) { + struct callchain_node *next; + + list_splice(&parent->children, &new->children); + INIT_LIST_HEAD(&parent->children); + + list_for_each_entry(next, &new->children, brothers) + next->parent = new; + } list_add_tail(&new->brothers, &parent->children); return new; } +/* + * Fill the node with callchain values + */ static void -fill_node(struct callchain_node *node, struct ip_callchain *chain, int start, - struct symbol **syms) +fill_node(struct callchain_node *node, struct ip_callchain *chain, + int start, struct symbol **syms) { int i; @@ -84,54 +106,80 @@ fill_node(struct callchain_node *node, struct ip_callchain *chain, int start, call->sym = syms[i]; list_add_tail(&call->list, &node->val); } - node->val_nr = i - start; + node->val_nr = chain->nr - start; + if (!node->val_nr) + printf("Warning: empty node in callchain tree\n"); } -static void add_child(struct callchain_node *parent, struct ip_callchain *chain, - struct symbol **syms) +static void +add_child(struct callchain_node *parent, struct ip_callchain *chain, + int start, struct symbol **syms) { struct callchain_node *new; - new = create_child(parent); - fill_node(new, chain, parent->val_nr, syms); + new = create_child(parent, false); + fill_node(new, chain, start, syms); new->hit = 1; } +/* + * Split the parent in two parts (a new child is created) and + * give a part of its callchain to the created child. + * Then create another child to host the given callchain of new branch + */ static void split_add_child(struct callchain_node *parent, struct ip_callchain *chain, - struct callchain_list *to_split, int idx, struct symbol **syms) + struct callchain_list *to_split, int idx_parents, int idx_local, + struct symbol **syms) { struct callchain_node *new; + struct list_head *old_tail; + int idx_total = idx_parents + idx_local; /* split */ - new = create_child(parent); - list_move_tail(&to_split->list, &new->val); - new->hit = parent->hit; - parent->hit = 0; - parent->val_nr = idx; + new = create_child(parent, true); + + /* split the callchain and move a part to the new child */ + old_tail = parent->val.prev; + list_del_range(&to_split->list, old_tail); + new->val.next = &to_split->list; + new->val.prev = old_tail; + to_split->list.prev = &new->val; + old_tail->next = &new->val; - /* create the new one */ - add_child(parent, chain, syms); + /* split the hits */ + new->hit = parent->hit; + new->val_nr = parent->val_nr - idx_local; + parent->val_nr = idx_local; + + /* create a new child for the new branch if any */ + if (idx_total < chain->nr) { + parent->hit = 0; + add_child(parent, chain, idx_total, syms); + } else { + parent->hit = 1; + } } static int __append_chain(struct callchain_node *root, struct ip_callchain *chain, int start, struct symbol **syms); -static int +static void __append_chain_children(struct callchain_node *root, struct ip_callchain *chain, - struct symbol **syms) + struct symbol **syms, int start) { struct callchain_node *rnode; /* lookup in childrens */ list_for_each_entry(rnode, &root->children, brothers) { - int ret = __append_chain(rnode, chain, root->val_nr, syms); + int ret = __append_chain(rnode, chain, start, syms); if (!ret) - return 0; + return; } - return -1; + /* nothing in children, add to the current node */ + add_child(root, chain, start, syms); } static int @@ -142,14 +190,22 @@ __append_chain(struct callchain_node *root, struct ip_callchain *chain, int i = start; bool found = false; - /* lookup in the current node */ + /* + * Lookup in the current node + * If we have a symbol, then compare the start to match + * anywhere inside a function. + */ list_for_each_entry(cnode, &root->val, list) { - if (cnode->ip != chain->ips[i++]) + if (i == chain->nr) + break; + if (cnode->sym && syms[i]) { + if (cnode->sym->start != syms[i]->start) + break; + } else if (cnode->ip != chain->ips[i]) break; if (!found) found = true; - if (i == chain->nr) - break; + i++; } /* matches not, relay on the parent */ @@ -157,23 +213,25 @@ __append_chain(struct callchain_node *root, struct ip_callchain *chain, return -1; /* we match only a part of the node. Split it and add the new chain */ - if (i < root->val_nr) { - split_add_child(root, chain, cnode, i, syms); + if (i - start < root->val_nr) { + split_add_child(root, chain, cnode, start, i - start, syms); return 0; } /* we match 100% of the path, increment the hit */ - if (i == root->val_nr) { + if (i - start == root->val_nr && i == chain->nr) { root->hit++; return 0; } - return __append_chain_children(root, chain, syms); + /* We match the node and still have a part remaining */ + __append_chain_children(root, chain, syms, i); + + return 0; } void append_chain(struct callchain_node *root, struct ip_callchain *chain, struct symbol **syms) { - if (__append_chain_children(root, chain, syms) == -1) - add_child(root, chain, syms); + __append_chain_children(root, chain, syms, 0); } |